cstree 是一个用于创建和操作具体语法树（CST）的通用库。与“传统”的抽象语法树（AST）相比，AST 通常包含不同类型的节点，这些节点代表文档源文本的不同语法元素，并将信息减少到正确解释所需的最小数量。相比之下，CST 是整个输入的无损表示，其中所有树节点都表示为同质的（即，节点是无类型的），但用 RawSyntaxKind 标记来确定它们所代表的语法元素的类型。这种表示的一个重大优势是它不仅可以精确地重新创建原始源代码，而且非常适合表示 不完整或错误 的树，因此非常适合用于诸如 IDE 或任何其他用户正在 编辑 源文本的应用程序等环境中。cstree 语法树的概念和数据结构部分受到 Swift 的 libsyntax 的启发。树由两层组成：内部树（称为 绿色树）包含作为位置无关绿色节点的实际源文本。在源中出现多次的标记和节点在此表示中被去重，以便有效地存储树。这意味着绿色树实际上可能不是结构上的树。为了解决这个问题，真实的语法树作为二级树（称为 红色树）构建在绿色树之上，以表示精确的源结构。作为可能的第三层，可以在红色树之上构建一个强类型 AST （请参阅）。

cstree 实现是基于 Rust-analyzer 作者开发的优秀项目 rowan 的分支，作者在他们的代码库 rust-analyzer 中对其实现进行了概念性概述，并在 此处 提供了文档。与 rowan 相比，cstree 的显著差异如下：

• 语法树（红色树）是按需创建的，但具有持久性。一旦 cstree 创建了一个红色节点，它将保持分配。相比之下，rowan 在树的每次遍历中都会即时重新创建红色层。除了这里讨论的权衡之外，这有助于在提供以下功能的同时实现良好的树遍历速度：
• 语法（红色）节点是 Send 和 Sync，允许在多个线程之间共享已实现的树。这是通过原子地引用计数整个语法树来实现的，这也消除了对单独节点进行引用计数的需要。
• SyntaxNode 可以持有自定义数据。
• cstree 树是在内部字符串上的树。这意味着 cstree 将对具有相同源字符串的标记（如具有相同名称的标识符）的文本进行去重。在这种情况下，rowan 将每个标记的文本及其元数据存储为自定义 DST（动态大小类型）。
• cstree 包含一些针对树创建的性能优化：它只在节点不在缓存中时在堆上分配空间，并通过预先散列来避免递归散列子树。
• cstree 包含一些针对树遍历的性能优化：持久化红色节点允许树遍历方法返回引用而不是克隆节点，这涉及更新树的引用计数。您仍然可以 clone 引用来获取拥有节点，但您只需在需要时才支付这种成本。
• 提供线程安全的语法树的缺点是 cstree 无法为其 CST 提供任何可变 API。通过替换节点，树仍然可以更新为新树，但不能原地修改。

入门指南

如果您正在查看 cstree，那么您可能正在查看或已经编写了一个解析器，并正在考虑使用具体语法树作为其输出。我们将在下面更多讨论解析——首先，让我们看看从输入文本到 cstree 语法树需要发生什么。

1. 定义一个枚举，表示您在语法中想要有的标记（如关键字）和节点（如“一个表达式”）类型，并实现 Syntax

2. 创建一个 GreenNodeBuilder 并从您的解析器中调用 start_node、token 和 finish_node

3. 使用结果 GreenNode 调用 SyntaxNode::new_root 或 SyntaxNode::new_root_with_resolver 以获得可以遍历的语法树

让我们一步步解析一个（非常）简单的语言到 cstree 语法树。我们将仅支持整数的加法和减法，用户可以从这些操作中构建一个复合表达式。然而，用户可以使用括号编写嵌套表达式，例如 1 - (2 + 5)。

定义语言

首先，我们需要列出我们语言语法的不同部分。我们可以使用一个带有单元变体的枚举来实现这一点，该变体用于任何终端和非终端。这个枚举需要可以转换为 u32，因此我们使用 repr 属性来确保它使用正确的表示。

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[repr(u32)]
enum SyntaxKind {
    /* Tokens */
    Int,    // 42
    Plus,   // +
    Minus,  // -
    LParen, // (
    RParen, // )
    /* Nodes */
    Expr,
    Root,
}

为了在处理泛型 cstree 类型（如 SyntaxNode）时的方便，我们还将为整个语法命名，并为其添加一个类型别名。这样，我们可以使用原始名称匹配 SyntaxKind，但使用更具有描述性的 Node<Calculator> 来实例化 cstree 的类型。

type Calculator = SyntaxKind;

其中大部分是用于将输入字符串转换为标记的标记，如数字（Int）和运算符（Plus，Minus）。我们实际上只需要一种类型的节点；表达式。我们语法树的根节点将有特殊的类型 Root，所有其他节点都将包含一系列算术操作，这些操作可能包含进一步的嵌套表达式节点。

为了使用我们的 SyntaxKind 与 cstree 一起，我们需要通过实现 Syntax 特性来告诉它如何将其转换回一个简单的数字（我们添加的 #[repr(u32)]）。我们还可以通过特质的 static_text 方法告诉 cstree 关于始终具有相同文本的标记。这对于运算符和括号很有用，但对于数字则不可能，因为整数标记可能由输入 3、7 或 12 等其他数字产生。我们只是在空类型上实现 Syntax，这样我们就可以给它一个名字。

impl Syntax for Calculator { 
    fn from_raw(raw: RawSyntaxKind) -> Self {
        // This just needs to be the inverse of `into_raw`, but could also
        // be an `impl TryFrom<u32> for SyntaxKind` or any other conversion.
        match raw.0 {
            0 => SyntaxKind::Int,
            1 => SyntaxKind::Plus,
            2 => SyntaxKind::Minus,
            3 => SyntaxKind::LParen,
            4 => SyntaxKind::RParen,
            5 => SyntaxKind::Expr,
            6 => SyntaxKind::Root,
            n => panic!("Unknown raw syntax kind: {n}"),
        }
    }

    fn into_raw(self) -> RawSyntaxKind {
        RawSyntaxKind(self as u32)
    }

    fn static_text(self) -> Option<&'static str> {
        match self {
            SyntaxKind::Plus => Some("+"),
            SyntaxKind::Minus => Some("-"),
            SyntaxKind::LParen => Some("("),
            SyntaxKind::RParen => Some(")"),
            _ => None,
        }
    }
}

派生 Syntax

为了节省定义此转换（以及，也许更重要的是，在您的语言语法在变化时不断更新它）的麻烦，当使用 derive 功能构建时，cstree 包括一个用于 Syntax 的派生宏。使用该宏，上面的 Syntax 特性实现可以被简单地替换为在 SyntaxKind 上添加 #[derive(Syntax)]。

解析到绿色树

解决了这些问题后，我们可以开始编写我们的表达式解析器。在本介绍 cstree 的目的下，我将假设存在一个能够产生以下标记的词法分析器。

#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub enum Token<'input> {
    // Note that number strings are not yet parsed into actual numbers,
    // we just remember the slice of the input that contains their digits
    Int(&'input str),
    Plus,
    Minus,
    LParen,
    RParen,
    // A special token that indicates that we have reached the end of the file
    EoF,
}

一个简单的词法分析器，可以产生这样的标记，是完整 readme 示例的一部分，但我们将忙于结合 cstree 和实际的解析器，我们定义如下。

pub struct Parser<'input> {
             // `Peekable` is a standard library iterator adapter that allows
             // looking ahead at the next item without removing it from the iterator yet
    lexer:   Peekable<Lexer<'input>>,
    builder: GreenNodeBuilder<'static, 'static, Calculator>,
}

impl<'input> Parser<'input> {
    pub fn new(input: &'input str) -> Self {
        Self {
            // we get `peekable` from implementing `Iterator` on `Lexer`
            lexer:   Lexer::new(input).peekable(),
            builder: GreenNodeBuilder::new(),
        }
    }

    pub fn bump(&mut self) -> Option<Token<'input>> {
        self.lexer.next()
    }
}

与返回抽象语法树的解析器不同，在 cstree 中，语言语法中所有元素的语法树节点将具有相同的类型：GreenNode 用于内部（“绿色”）树，SyntaxNode 用于外部（“红色”）树。不同类型的节点（和标记）通过它们的 SyntaxKind 标签来区分，这是我们上面定义的。

您可以使用 cstree 实现许多类型的解析器。为了了解其工作原理，考虑一个典型的递归下降解析器。在更传统的 AST 中，人们会为结构体或函数定义、语句、表达式等定义不同的 AST 结构。在解析器内部，任何元素（如结构体的所有字段或函数内部的所有语句）的组件将首先被解析，然后解析器将它们包装在匹配的 AST 类型中，这些类型由相应的解析器函数返回。

由于 cstree 的语法树是无类型的，因此解析器不会构建显式的 AST 表示。相反，使用 GreenNodeBuilder 将 CST 解析得更加接近源代码，即您需要告诉 cstree 您每个新元素和解析器消耗的所有标记。因此，例如，要解析结构体定义，解析器首先“进入”结构体定义节点，然后解析 struct 关键字和类型名，然后解析每个字段，最后“完成”解析结构体节点。

最简单的情况是我们的解析器的根节点，它仅创建一个包含整个表达式的根节点（如果任何表达式都是一个节点，特别是如果我们将整数字面量标记包装在 Expr 节点中，我们可以不使用特定的根节点）。

pub fn parse(&mut self) -> Result<(), String> {
    self.builder.start_node(SyntaxKind::Root);
    self.parse_expr()?;
    self.builder.finish_node();
    Ok(())
}

由于没有静态的 AST 类型要返回，解析器在节点部分方面非常灵活。在先前的例子中，如果用户向结构体添加新字段且尚未输入字段的类型，结构体节点的 CST 并不关心是否为其提供了子节点。同样，如果用户正在删除字段，源代码当前包含遗留的字段名，这个额外的标识符可以成为结构体节点的一部分，而无需修改语法树定义。这一特性是 CST 作为无损输入表示形式的密钥，这要求语法树反映 AST 项周围的空白和注释的用户特定布局。

在我们的简单表达式语言的解析器中，我们还将必须处理以下事实：当我们看到一个数字时，解析器还不知道是否会有随后的操作。也就是说，在表达式 1 + 2 中，它只能在看到 + 后才能知道它正在解析一个二元操作。然而，cstree 中构建树的类似事件模型意味着，在达到 + 时，解析器必须已经进入了一个表达式节点，以便整个输入成为表达式的一部分。

fn parse_lhs(&mut self) -> Result<(), String> {
    // An expression may start either with a number, or with an opening parenthesis that is
    // the start of a parenthesized expression
    let next_token = *self.lexer.peek().unwrap();
    match next_token {
        Token::Int(n) => {
            self.bump();
            self.builder.token(SyntaxKind::Int, n);
        }
        Token::LParen => {
            // Wrap the grouped expression inside a node containing it and its parentheses
            self.builder.start_node(SyntaxKind::Expr);
            self.bump();
            self.builder.static_token(SyntaxKind::LParen);
            self.parse_expr()?; // Inner expression
            if self.bump() != Some(Token::RParen) {
                return Err("Missing ')'".to_string());
            }
            self.builder.static_token(SyntaxKind::RParen);
            self.builder.finish_node();
        }
        Token::EoF => return Err("Unexpected end of file: expected expression".to_string()),
        t => return Err(format!("Unexpected start of expression: '{t:?}'")),
    }
    Ok(())
}

fn parse_expr(&mut self) -> Result<(), String> {
    // Remember our current position
    let before_expr = self.builder.checkpoint();

    // Parse the start of the expression
    self.parse_lhs()?;

    // Check if the expression continues with `+ <more>` or `- <more>`
    let Some(next_token) = self.lexer.peek() else {
        return Ok(());
    };
    let op = match *next_token {
        Token::Plus => SyntaxKind::Plus,
        Token::Minus => SyntaxKind::Minus,
        Token::RParen | Token::EoF => return Ok(()),
        t => return Err(format!("Expected operator, found '{t:?}'")),
    };

    // If so, retroactively wrap the (already parsed) LHS and the following RHS
    // inside an `Expr` node
    self.builder.start_node_at(before_expr, SyntaxKind::Expr);
    self.bump();
    self.builder.static_token(op);
    self.parse_expr()?; // RHS
    self.builder.finish_node();
    Ok(())
}

impl Parser<'_> {
    pub fn finish(mut self) -> (GreenNode, impl Interner) {
        assert!(self.lexer.next().map(|t| t == Token::EoF).unwrap_or(true));
        let (tree, cache) = self.builder.finish();
        (tree, cache.unwrap().into_interner().unwrap())
    }
}

let input = "11 + 2-(5 + 4)";
let mut parser = Parser::new(input);
parser.parse().unwrap();
let (tree, interner) = parser.finish();
let root = SyntaxNode::<Calculator>::new_root_with_resolver(tree, interner);
dbg!(root);