如何使用类型系统在解析树中编码父子约束？

Question

我正在为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 Node {
    parent: Node,
    data: NodeData,
    children: Vec<Node>,
}

这种方法有效，直到我们决定为构建树的方式添加一些约束，如：

• 持有A的节点只能有B和C作为孩子。
• 持有B的节点可以有A和D
• 持有C的节点不能有孩子
• 持有D的节点只能有A ..

一般来说 - 一个变体只能拥有自己独特的enum NodeData子集作为孩子。

我尝试了以下方法：

• 我可以在运行时对这些约束进行编码，但是这会产生额外的性能开销，并且仍然可能会创建一个无效的树（例如，由于逻辑中的错误）
• 我尝试使用结构和特征而不是枚举。 （例如特质CanHaveA适用于B和D）。虽然表面上看起来似乎是可行的，但我注意到我将无法访问特征背后的具体类型（我需要它，因为它是一个具体的语法树），与Scala不同，我不能使用match将特征结构化为特定类型。

我希望得到的解决方案应该允许在编译时编码这些约束，并仍然提供对具体类型的访问。

Answer 1

与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标准库内部使用了大量宏来实现此目的。