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

cstree 实现是 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构建时，cstree包含一个用于Syntax的推导宏。使用此宏，上面的Syntax特质实现可以通过简单地添加#[derive(Syntax)]到SyntaxKind来替换。

解析到绿色树

解决了这些问题之后，我们可以开始编写我们的表达式解析器。为了介绍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节点不会关心它是否有子节点。同样，如果用户正在删除字段，而源代码中目前包含一个遗留的字段名，这个额外的标识符可以成为结构体节点的一部分，而不需要修改语法树定义。这一特性是CSTs作为无损输入表示形式非常适合的关键，这要求语法树反映AST项周围的特定用户布局的空白和注释。

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

为了解决这个问题，GreenNodeBuilder 提供了 checkpoint 方法，我们可以调用它来“记住”输入中的当前位置。例如，我们可以在解析器解析第一个 1 之前创建一个检查点。稍后，当它看到接下来的 + 时，它可以使用 start_node_at 创建整个表达式的 Expr 节点。

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(())
}

获取解析器结果

我们的解析器现在可以解析我们的简单算术语言，但是它的方法不返回任何内容。那么我们如何获取我们的语法树呢？答案在于 GreenNodeBuilder::finish，它最终返回我们辛苦构建的树。

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())
    }
}

finish 还返回用于去重树节点和标记的缓存，因此您可以重新用于解析相关输入（例如，来自同一crate的不同源文件可能共享许多常见的函数和类型名称，可以进行去重）。有关更多信息，请参阅 GreenNodeBuilder 的文档，特别是 with_cache 和 from_cache 方法。对我们来说最重要的是，我们可以从缓存中提取包含树标记源文本的 Interner，这对于我们想要查找变量名或计算器中数字的值是必需的。

要处理语法树，您需要将其升级到SyntaxNode，使用SyntaxNode::new_root。您还可以使用SyntaxNode::new_root_with_resolver来结合树和词法分析器，这使得您可以直接检索源文本，并使节点实现Display和Debug。通过调用带有Resolver的debug或display方法，可以从SyntaxNode生成相同的输出。要可视化整个语法树，请在debug中将recursive参数设置为true，或者简单地打印ResolvedNode的调试信息。

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);

AST层

虽然cstree是为具体语法树构建的，但应用程序可以很容易地处理CST或AST表示，或者在这两者之间自由切换。为此，使用cstree构建语法和底层绿色树，并为您的不同类型的节点提供AST包装器。如何实现此操作的示例可以在这里和这里（注意，后一个文件是由一个任务自动生成的）查看。

许可证

cstree主要在MIT许可证和Apache许可证（版本2.0）的条款下分发。

有关详细信息，请参阅LICENSE-APACHE和LICENSE-MIT。