How AST-grep Rewrote Tree-sitter in Rust and Made It 30% Faster

Appearance

How ast-grep Rewrote Tree-sitter in Rust and Made It 30% Faster

Part 1 of 4 — the complete adventure

ast-grep rewrote Tree-sitter's C core in Rust, with AI writing the code. The new core is faster at parsing, faster at reading the completed tree, and faster in ast-grep itself. (The title's “30%” is the parser-only number; end-to-end, ast-grep runs about 22% faster.)

Source repository: HerringtonDarkholme/tree-sitter.

Two quick introductions before the numbers. ast-grep — the structural code-search tool this blog belongs to — searches code by syntax rather than by text, so every file it touches must first become a syntax tree. Tree-sitter is the parser framework that builds that tree: you give it a grammar definition, and it generates a fast parser for that language. Born in the editor world, it now powers an enormous ecosystem of grammars and tools.

Performance and peak RSS. Throughput is normalized so the unmodified C build (“C / normal”) scores 100; higher is better. RSS is peak resident memory, and the raw-parsing row shows it as a range because it varies across the benchmark's language fixtures. The outline row is ast-grep's real workload: parse every file in a repository, then walk each completed tree to extract a structural outline.

| Benchmark | C / normal | Rust | Difference | |---|---|---|---| | Raw parsing | Throughput: 100 RSS: 8.48–21.41 MiB | Throughput: 129.74 RSS: 8.42–25.70 MiB | +29.74% throughput +20.0% RSS upper bound | | Tree traversal | Throughput: 100 RSS: 20.38 MiB | Throughput: 110.16 RSS: 22.20 MiB | +10.16% throughput +8.9% RSS | | Complete ast-grep outline | User CPU: 1.233 s RSS: 26.52 MiB | User CPU: 0.960 s RSS: 34.43 MiB | −22.2% user CPU +29.8% RSS |

Rust won every parser and traversal fixture, and ast-grep produced exactly the same outline. Memory is the tradeoff: the Rust build uses about 8 MiB more in the ast-grep run. On the much larger TypeScript stress corpus — the TypeScript compiler repository's test-baseline tree, this project's memory torture test — it peaks at 91.2 MiB. That figure is a triumph, not a confession: earlier in the project, the same corpus peaked above 1 GiB.

The result is not a 1:1 replacement for upstream Tree-sitter. It is a narrower runtime built for AI coding agents that analyze complete file snapshots:

• Existing generated languages and parsers remain compatible.
• Native loading of WebAssembly-compiled languages and incremental old-tree reuse were removed.
• Compatibility still requires many raw pointers and unsafe blocks.

That boundary keeps the grammar ecosystem useful for agentic coding while removing editor-specific machinery the target workload does not need.

That is the ending. Getting there was another matter.

Why Rewrite Tree-sitter?

Every serious ast-grep performance investigation eventually arrived at the same place: Tree-sitter.

ast-grep could make its rules faster. It could prune work, cache configuration, and avoid visiting irrelevant syntax. But every file still had to become a syntax tree first, and Tree-sitter built that tree. The parser was both the foundation and, increasingly, the ceiling.

I had dreamed about rewriting or deeply optimizing it for years. The dream usually lasted until I opened the runtime. There was a mature C implementation, binary compatibility, external scanners, error recovery, incremental parsing, ambiguous grammars, several language bindings, and a small matter of not breaking the enormous grammar ecosystem built on top of all of it.

For one person, this was not a weekend project. It was a Herculean task wearing a header file.

So nothing happened.

Then AI-assisted rewrite attempts started appearing everywhere—Bun, pgrust, and Roc among them. They did not prove that rewriting Tree-sitter was wise, make the runtime smaller, or make parser theory less strange. They showed that the experiment had become cheap enough for one person to attempt, giving me enough leverage to ask the unreasonable question and get an answer before the decade ended.

So I instructed ChatGPT to rewrite Tree-sitter's C core in Rust. The project moved from a compatibility-first translation, through a fast but unreadable optimization attempt, to a simpler runtime and real parser gains—only to discover that a faster parser could still make ast-grep slower.

The rest of this post follows that journey: what worked, what had to be reverted, and what it took to turn a parser benchmark win into an application win.

Tree-sitter's Parsing Architecture

Tree-sitter takes source code and produces a syntax tree. Each supported language begins as a grammar definition that Tree-sitter compiles into generated parsing tables and lexer code; when this series says “generated languages,” “generated grammars,” or “generated tables,” it means those artifacts. At runtime, a lexer turns characters into tokens such as identifier, +, and number. The parser then uses the generated table and a stack to decide what each token means.

Most of the time, the table requests one of two operations:

shift: consume a token and push it onto the parser stack; reduce: recognize that several syntax pieces form a larger grammar rule, replace them with one parent, and continue.

If every table entry had one valid answer, the parser could follow one history with one stack. That is the ordinary LR case. Programming-language grammars occasionally have genuine conflicts: more than one action may remain valid until additional input reveals which interpretation survives.

Tree-sitter therefore uses generalized LR (GLR). It can follow several histories at once while sharing their common past in a graph-structured stack. Think of one road that can briefly fork, then merge again. The graph is necessary when the grammar is ambiguous. It is considerably less charming when the parser constructs graph machinery for a road that remains straight.

The other central object is the subtree. A shifted token becomes a leaf; a reduction combines children into an internal syntax node. These values are created during parsing, shared across stack histories, published as the final tree, traversed by ast-grep, and eventually released. Optimizing only their birth while ignoring the rest of that lifetime would later produce a rather expensive lesson.

That is enough parser theory for the overview.

First Step: Preserve C Behavior in Rust

The first goal was not elegance. It was parity.

The rewrite contract was deliberately conservative:

Use the existing tests as the behavioral oracle. A plausible Rust implementation was not enough; it had to produce the same trees, recovery behavior, navigation results, and public API effects. Test the ecosystem, not only handwritten examples. Existing generated grammars and external scanners had to keep working without regeneration or source changes. Preserve the binary interface (ABI). Generated language tables, public C functions, layouts, symbols, and calling conventions remained compatible while the implementation behind them changed language. Translate before redesigning. The first Rust version intentionally resembled the C control flow so parity failures had a bounded search area.

In one sentence: preserve everything the ecosystem can observe, then make the inside replaceable.

I instructed ChatGPT to translate the runtime one part at a time: basic utilities, tree storage, lexing, the parser stack, tree navigation, and finally the parser loop. The agent read the C and Rust code, wrote patches, fixed compiler errors, ran tests, and investigated mismatches. I supplied the goals, constraints, objections, and decisions. The existing implementation and test suite supplied the answer key.

This distinction matters. I did not personally type a heroic Rust port and then ask AI to polish the comments. The implementation, profiling, instrumentation, and much of the experimental code were produced by the agent.