codeql/shared/yeast/doc/yeast.md

YEAST — YEAST Elaborates Abstract Syntax Trees

YEAST is a framework for transforming tree-sitter parse trees before they are extracted into a CodeQL database. It sits between the tree-sitter parser and the TRAP extractor, rewriting parts of the AST according to declarative rules.

Motivation

Tree-sitter grammars describe the concrete syntax of a language — every keyword, operator, and punctuation token appears in the parse tree. CodeQL analyses often prefer a simplified abstract syntax where syntactic sugar has been removed. YEAST bridges this gap by desugaring the tree-sitter output into a cleaner form before extraction.

For example, Ruby's for x in list do ... end is syntactic sugar for list.each { |x| ... }. A YEAST rule can rewrite the former into the latter so that CodeQL queries only need to reason about the .each form.

Architecture

Source code
    │
    ▼
┌──────────────┐
│  tree-sitter │  Parse source into a concrete syntax tree
│    parser    │
└──────┬───────┘
       │ tree_sitter::Tree
       ▼
┌──────────────┐
│    YEAST     │  Apply desugaring rules, producing a new AST
│   Runner     │
└──────┬───────┘
       │ yeast::Ast
       ▼
┌──────────────┐
│    TRAP      │  Walk the (possibly rewritten) AST and emit TRAP tuples
│  extractor   │
└──────────────┘

The entry point is extract() in the shared tree-sitter extractor. When called with a non-empty rules vector, the parsed tree is run through the YEAST Runner before TRAP extraction; with an empty rules vector the tree is extracted unchanged.

How desugaring works

A YEAST Rule has two parts:

1. A query that matches nodes in the AST using a tree-sitter-inspired pattern language.
2. A transform that produces replacement nodes from the match captures.

The Runner applies rules by walking the tree top-down. At each node, it tries each rule in order. If a rule's query matches, the node is replaced by the transform's output, and the rules are re-applied to the result. If no rule matches, the node is kept and its children are processed recursively.

A rule can replace one node with zero nodes (deletion), one node (rewriting), or multiple nodes (expansion).

By default a rule fires at most once on a given node: after firing, the engine will not re-try that same rule on the result root. Other rules may still fire on the result, and the rule may still fire on different nodes (including the result's children). To opt into iterative behaviour — when a rule's output is intentionally re-matched by the same rule — call .repeated() on the constructed Rule:

let r = yeast::rule!((foo ...) => (foo ...)).repeated();

Without .repeated(), a rule whose output happens to match its own query simply fires once and stops. With .repeated(), the rule is allowed to re-match indefinitely; the runner still enforces a global rewrite-depth limit (currently 100) as a safety net against accidental cycles.

Query language

Queries use a syntax inspired by tree-sitter queries, written inside the yeast::query!() proc macro.

Node patterns

// Match any named node
(_)

// Match a node of a specific kind
(assignment)

// Match an unnamed token by its text
("end")

Fields

// Match a node with specific fields
(assignment
    left: (identifier) @lhs
    right: (_) @rhs
)

Fields are matched by name. Unmentioned fields are ignored — the pattern (assignment left: (_) @x) matches any assignment node regardless of what's in right.

Captures

Captures bind matched nodes to names for use in the transform. A capture @name always follows the pattern it captures:

(identifier) @name          // capture an identifier node
(_) @value                  // capture any named node
(identifier)* @items        // capture each repeated match
("=") @op                   // capture an unnamed token by its text
"=" @op                     // shorthand for the line above
_ @anything                 // capture any node, named or unnamed

Named vs unnamed children

The two wildcard forms (_) and bare _ differ:

• (_) matches only named nodes. When used as a positional pattern, unnamed children (keywords, operators, punctuation) are skipped over.
• Bare _ matches any node, named or unnamed, taking whatever is next in the child list.

Bare child patterns are matched forward-scan: each pattern advances through the iterator until it finds a child that matches, skipping non-matching children along the way. So (foo ("baz")) against a foo whose children are [bar, baz] succeeds — the matcher scans past bar and matches baz. The iterator advances as it goes, so subsequent patterns can never match children that appear earlier in source order than already-matched ones.

For named-only patterns ((_), (some_kind ...)), the scan additionally skips past unnamed tokens without trying to match them, since they can never match anyway.

Anchors (.) for forcing immediate adjacency, like in tree-sitter queries, are not supported.

(for
    pattern: (_) @pat             // named field, captures any named node
    value: (in (_) @val)          // "in" wrapper is a named node here
    body: (do (_)* @body)         // "do" and "end" tokens skipped by (_)
)

Repetitions

(_)*                   // zero or more
(_)+                   // one or more
(_)?                   // zero or one
(identifier)* @names   // capture each repeated match

Template language

Templates construct new AST nodes using the tree! and trees! macros. All children in a template must be in named fields — output AST nodes are always fully fielded.

When used inside a rule! macro, the context is implicit — no explicit BuildCtx argument is needed. When used standalone, they take a BuildCtx as the first argument:

// Inside rule! — implicit context, captures are Rust variables
yeast::rule!(
    (assignment left: (_) @left right: (_) @right)
    =>
    (assignment left: {right} right: {left})
);

// Standalone — explicit context
let fresh = yeast::tree_builder::FreshScope::new();
let mut ctx = BuildCtx::new(ast, &captures, &fresh);
let id = yeast::tree!(ctx,
    (assignment
        left: {ctx.capture("lhs")}
        right: {ctx.capture("rhs")}
    )
);

tree! — build a single node

tree!(...) returns a single node Id:

yeast::tree!(ctx,
    (assignment
        left: {ctx.capture("lhs")}
        right: {ctx.capture("rhs")}
    )
)

trees! — build multiple nodes

trees!(...) returns Vec<Id>:

yeast::trees!(ctx,
    (assignment left: {tmp} right: {right})
    {body}
)

Literal nodes

(kind "text") creates a leaf node with fixed text content:

(identifier "each")          // an identifier node whose text is "each"

Computed literals

(kind #{expr}) creates a leaf node whose content is expr.to_string():

(integer #{i})               // an integer node with the value of i
(identifier #{name})         // an identifier from a Rust variable

Fresh identifiers

(kind $name) creates a leaf node with an auto-generated unique name. All occurrences of the same $name within one BuildCtx share the same value:

(block
    parameters: (block_parameters
        (identifier $tmp)         // generates e.g. "$tmp-0"
    )
    body: (block_body
        (assignment
            left: {pat}
            right: (identifier $tmp)   // same "$tmp-0" value
        )
    )
)

Embedded Rust expressions

{expr} embeds a Rust expression whose value is appended to the enclosing field (or to the rule body's id list). Dispatch happens via the [IntoFieldIds] trait, which is implemented for:

• Id — pushes the single id.
• Any IntoIterator<Item: Into<Id>> — extends with all yielded ids (covers Vec<Id>, Option<Id>, iterator chains, etc.).

So the same {expr} syntax handles single ids, splices, and zero-or-many options uniformly:

(assignment
    left: {some_node_id}       // a single Id
    right: {rhs}               // a captured value (inside rule!)
)

yeast::trees!(ctx,
    (assignment left: {tmp} right: {right})
    {extra_nodes}              // splices a Vec<Id>
)

The contents of {…} are treated as a Rust block, so multi-statement expressions (with let bindings) work too:

(assignment
    left: {tmp}
    right: {
        let lit = ctx.literal("integer", "0");
        tree!((binary_expr op: (operator "+") left: {tmp} right: {lit}))
    })

Inside rule!, captures are Rust variables — {name} works for single, optional, and repeated captures alike:

rule!(
    (assignment left: @lhs right: _* @parts)
    =>
    (assignment left: {lhs} right: (block stmt: {parts}))
)

Raw captures (@@name)

The default @name capture marker is auto-translated: in OneShot phases the macro recursively translates the captured node before binding it, so {name} in the output template splices a node that already conforms to the output schema.

For rules that need the raw (input-schema) capture — typically to read its source text or to translate it explicitly with mutable context state between calls — use @@name instead. The body sees the original input-schema Id. Because these rules always have a Rust block body, they use the annotation form (see the rule! macro section for the full grammar):

yeast::rule!(
    (assignment left: (_) @@raw_lhs right: (_) @rhs)
    =>
    call {
        // raw_lhs is untranslated: read its original source text.
        let text = ctx.ast.source_text(raw_lhs);
        // rhs is already translated by the auto-translate prefix.
        tree!((call
            method: (identifier #{text.as_str()})
            receiver: {rhs}))
    }
);

Mix @ and @@ freely in the same rule. In a Repeating phase both markers are equivalent (auto-translation is a no-op for repeating rules).

Complete example: for-loop desugaring

This rule rewrites Ruby's for pat in val do body end into val.each { |tmp| pat = tmp; body }:

let for_rule = yeast::rule!(
    (for
        pattern: (_) @pat
        value: (in (_) @val)
        body: (do (_)* @body)
    )
    =>
    (call
        receiver: {val}
        method: (identifier "each")
        block: (block
            parameters: (block_parameters
                (identifier $tmp)
            )
            body: (block_body
                (assignment
                    left: {pat}
                    right: (identifier $tmp)
                )
                {..body}
            )
        )
    )
);

Captures from the query (@pat, @val, @body) become Rust variables automatically: single captures bind as Id, repeated captures (after * or +) as Vec<Id>, and optional captures (after ?) as Option<Id>.

The rule! macro

rule! combines a query and a transform into a single declaration. There are three transform forms, each suited to a different level of rule complexity:

// 1. Template form — a tree literal describing the output.
yeast::rule!(
    (query_pattern field: (_) @capture)
    =>
    (output_template field: {capture})
)

// 2. Shorthand form — captures become fields on a bare output kind.
yeast::rule!(
    (query_pattern field: (_) @capture)
    => output_kind
)

// 3. Annotation form — a Rust block body preceded by the output kind.
yeast::rule!(
    (query_pattern child: (_)+ @@children)
    =>
    output_kind* {
        // arbitrary Rust; must evaluate to a value compatible with the
        // declared multiplicity (see below).
        let mut result = Vec::new();
        for child in children {
            result.extend(ctx.translate(child)?);
        }
        result
    }
)

The shorthand => kind form auto-generates the template, mapping each capture name to a field of the same name on the output node.

Annotation form

Rules that need imperative logic — mutating [BuildCtx] state per iteration, computing intermediate values, or looping over captures — use the annotation form. It has three shapes distinguished by a suffix on the output-kind identifier:

Syntax	Body must evaluate to	Meaning
=> kind { ... }	a single node id of kind	Emit exactly one node.
=> kind? { ... }	an Option of a node id of kind	Emit 0 or 1 nodes (None/Some).
=> kind* { ... }	an iterable of node ids of kind	Emit 0+ nodes; flattens into the enclosing splice slot.

The suffix mirrors the ? / * markers used elsewhere in the schema DSL (see ast_types.yml): bare identifier = required single, ? = optional single, * = repeated.

The annotation names the schema kind of the output, giving the macro enough information for future static analysis (e.g. computing the static output type of translated captures at their consumer sites).

Bare => { ... } block bodies are rejected — every Rust-block body must carry an annotation, so the output kind is always visible without having to inspect the block's expression.

Choosing between the forms

Prefer the simplest form that fits:

• If the whole transform is a tree literal, use the template form.
• If the transform is a template whose root matches a query capture 1:1, use the shorthand form.
• If the transform needs Rust logic (loops, let bindings, calls to ctx.translate, etc.), use the annotation form.

Integration with the extractor

A YEAST desugaring pass is configured with a [DesugaringConfig], which carries one or more named [Phase]s of rules and an optional output node-types schema (in YAML format). Each phase is a complete traversal that runs to completion before the next phase starts; only the current phase's rules are considered during that traversal. Attach the config to a language spec to enable rewriting:

let desugar = yeast::DesugaringConfig::new()
    .add_phase("cleanup", yeast::PhaseKind::Repeating, cleanup_rules())
    .add_phase("translate", yeast::PhaseKind::OneShot, translate_rules())
    .with_output_node_types_yaml(include_str!("output-node-types.yml"));

let lang = simple::LanguageSpec {
    prefix: "ruby",
    ts_language: tree_sitter_ruby::LANGUAGE.into(),
    node_types: tree_sitter_ruby::NODE_TYPES,
    desugar: Some(desugar),
    file_globs: vec!["*.rb".into()],
};

A single-phase config is just .add_phase(...) called once. Phase names appear in error messages so you can tell which phase failed.

There are two kinds of phases:

• Repeating: Each node is re-processed until none of the rules in the phase matches. When a node no longer matches any rules, its children are recursively processed. In practice this is used to desugar or simplify an AST, while staying mostly within the same schema.
• One-shot: Each node is processed by the first matching rule, and the engine panics if no rule matches. Rules are then recursively applied to every captured node. In practice this is used when translating from one AST schema to another, where an exhaustive match is required.

The same YAML node-types is used for both the runtime yeast Schema (so rules can refer to output-only kinds and fields) and TRAP validation (it is converted to JSON internally).

For the dbscheme/QL code generator, set Language::desugar to a DesugaringConfig carrying the same YAML; the generator converts it to JSON for downstream code generation. The phases field of the config is unused at code-generation time.

The rules! macro

The [rules!] macro bundles a list of rewrite rules with the input and output node-types schema paths. It's a drop-in replacement for the hand-written vec![rule!(...), rule!(...), ...] form and accepts a slightly looser syntax: bare rule bodies don't need an explicit rule!(...) wrapper.

let translation_rules: Vec<yeast::Rule> = yeast::rules! {
    input: "tree-sitter-swift/node-types.yml",
    output: "ast_types.yml",
    [
        (simple_identifier) @name
        =>
        (name_expr identifier: (identifier #{name})),

        (integer_literal) @lit
        =>
        (int_literal #{lit}),
    ]
};

Each comma-separated item in the bracketed list may be:

• A bare rule body (query) => (template) — no rule!(...) wrapper.
• An explicit rule!(...) invocation, with optional postfix calls such as rule!(...).repeated().
• Any other expression returning a Rule (helper functions, etc.).

Schema paths are resolved relative to the consuming crate's CARGO_MANIFEST_DIR (the same convention include_str! uses for relative paths). The resolved paths are emitted as include_str! references in the expansion so the consuming crate's incremental cache invalidates when a schema YAML changes — laying the groundwork for schema-aware compile-time checks on the rule bodies.

The Vec<Rule> produced by rules! flows into add_phase exactly as before.