Как я могу кодировать родительско-дочерние ограничения в дереве разбора, используя систему типов? - PullRequest
Новая
       62

Как я могу кодировать родительско-дочерние ограничения в дереве разбора, используя систему типов?

0 голосов
/ 11 марта 2019

Я пишу парсер для org-mode.Я хочу использовать систему типов для кодирования родительско-дочерних отношений между узлами дерева разбора.Проблема может быть продемонстрирована на следующих примерах: 

enum NodeData {
    A {prop1, prop2},
    B {prop3},
    C,
    D {prop4}
//...and list goes on, each variant has its own set of props
}

Перечисление NodeData представляет набор возможных элементов синтаксиса - виды типов данных в дереве.

Следующее Node struct очень наивно представляет само дерево узлов 

struct Node {
    parent: Node,
    data: NodeData,
    children: Vec<Node>,
}

Этот подход работает до тех пор, пока мы не решим добавить некоторые ограничения в способ построения дерева, например:

  • Узел с A может иметь только B и C в качестве дочерних элементов.
  • Узел с B может иметь A и D
  • Узел с C не может иметь детей
  • Узел, который содержит D, может иметь только A ..

В общем случае - вариант может иметь только свое уникальное подмножество enum NodeData как дети.

Я пробовал следующие подходы:

  • Я могу кодировать эти ограничения во время выполнения, но это создает дополнительные накладные расходы производительности и все еще оставляет возможность создать недопустимое дерево(из-за ошибки в логиc например)
  • Я пытался использовать структуры и черты вместо enum.(например, черта CanHaveA применяется к B и D).Хотя это казалось возможным на первый взгляд, я заметил, что я потеряю доступ к конкретному типу за признаком (который мне нужен, поскольку это конкретное синтаксическое дерево), и в отличие от Scala, я не могу использовать match для деструктурирования признаков до определенногоtype.

Решение, которое я надеюсь получить, должно позволить кодировать эти ограничения во время компиляции и по-прежнему обеспечивать доступ к конкретному типу.

1 Ответ

1 голос
/ 11 марта 2019

и в отличие от Scala я не могу использовать match для деструктурирования черт до определенного типа

Возможно, это будет возможно в будущем (см. get_type_id), но я не вижу проблем с неуниверсальными структурами, такими как 

struct NodeA {
    props: NodeAProps,
    children: Vec<NodeAChildren>,
}
struct NodeAProps {}
enum NodeAChildren {
    B(NodeB),
    C(NodeC),
}

struct NodeB {
    props: NodeBProps,
    children: Vec<NodeBChildren>,
}
struct NodeC {}
struct NodeD {}

Таким образом можно безопасно хранить абстрактное синтаксическое дерево, и если вам нужно сделать что-то общее с его узлами, тогда легко реализовать все необходимые черты для них. Для этой цели стандартная библиотека Rust внутренне использует множество макросов.

...