Tree-sitter and the AST: how tools read your code

Tree-sitter is a parser generator and an incremental parsing library: it turns source code into a syntax tree, updates that tree as you type, and keeps producing a usable tree when the code is broken. It is what sits underneath syntax highlighting in Neovim, code navigation on GitHub, and most tools that need to understand code structure without running a compiler.

What the tree looks like

For function add(a, b) { return a + b; } a tree-sitter tree contains afunction_declaration with a name, a formal_parameters node holding two identifiers, and a statement_block holding a return_statement holding a binary_expression. Every node carries its byte range in the file, so a node maps back to exactly the text it came from.

Strictly this is a concrete syntax tree: it keeps every token, including punctuation. Named nodes are the interesting ones, and most tools query those. The distinction from an abstract syntax tree matters when you are writing queries and wondering why a comma has a node.

The three properties that matter

• Incremental. Editing one line re-parses that region rather than the file, which is what makes per-keystroke use possible.
• Error tolerant. A missing brace produces a tree with an error node, not a failure. Half-written code still highlights and still indexes.
• Uniform across languages. One query language works over every grammar, so a tool supports a new language by adding a grammar rather than by writing a parser.

Queries

Tree-sitter ships an s-expression query language for matching patterns in the tree. Finding every function declaration with its name looks like this:

(function_declaration
  name: (identifier) @name
  body: (statement_block) @body)

That is the whole mechanism behind structural search, syntax highlighting and most code-mod tooling. See structural code search for what you can do with it.

What it does not do

Tree-sitter parses. It does not resolve types, imports or overloads, and it does not know that the foo in one file is the foo defined in another. Tools that need that build a resolution layer on top, or fall back to a language server. Knowing the boundary keeps expectations right: a syntax tree gives structure, and structure covers a surprising amount of what review and diffing need.

Where Aura uses it

Every file Aura indexes is parsed with tree-sitter, each node is hashed into a Merkle graph, and the graph is what the semantic diff, the impact analysis and the goal proof read from. Grammar packages differ in shape between languages, which is a common source of confusion; the TypeScript and Rust grammar note covers the two that trip people up most.