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

Introduction

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.

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 under my direction. Without AI, this project would still be an idea I occasionally mentioned before wisely changing the subject.

The C core had become Rust. It compiled. It passed the tests. Existing grammars could use it. This was already the kind of result that had looked impossible when the project was sitting on the shelf. Naturally, I immediately asked for more.

Why the First Optimization Attempt Failed

The request was pure vibe coding - one line typed into a /goal command. The process behind it was more careful than that: I directed ChatGPT to use proper profiling tools, understand the runtime's data layouts and ownership, and look for algorithmic changes instead of merely polishing individual instructions.

The benchmarks duly crossed the requested line. Then I opened the code and could not follow it. Layers of overlapping AI-generated optimizations sat on top of a mechanical C-to-Rust translation, and soon the parser began segfaulting: no friendly Rust panic, no failed assertion, the process simply left. A parser that is twenty percent faster and occasionally disappears is not an optimization. It is a benchmark with a jump scare.

I reverted the optimization work entirely. The twenty percent went with it, and the performance the project eventually reached came later, from the clean, layered work described below. Part 2 tells this story in full. What matters here is how it reversed the project: I stopped asking ChatGPT to make the pile faster and started asking it to make the system explainable.

Second Step: Reduce Scope and Improve Readability

The cleanup had two parts:

• delete features and representations outside the target product;
• turn the retained C-style Rust into code whose ownership and control flow could be reasoned about locally.

Neither step promised a heroic benchmark. Both were prerequisites for trusting the next one.

Remove Incremental Parsing from the Target Runtime

At first, "rewrite Tree-sitter" implied preserving every feature. Then the target workload forced a better question: preserving it for whom? Upstream Tree-sitter is famously useful inside editors. A human inserts one character, deletes two more, and expects highlighting to update before the next frame. Incremental parsing lets the runtime reuse the old tree and rebuild only the affected region. In that world, reparsing the complete file after every keystroke is needless work.

That was not the world of this branch. ast-grep and the AI coding-agent tools I cared about operate on complete file snapshots: an agent reads a file, analyzes or rewrites it, and asks the tool to process the new snapshot. There is no editor-owned syntax tree advancing one keystroke at a time. A fresh parse is not a degraded fallback; it is the normal operation.

So I decided to remove incremental old-tree reuse and instructed ChatGPT to do it. The public parameter remains for compatibility, but this runtime parses fresh. The machinery for finding and reusing pieces of the old tree - and it reached into a surprising number of core structures - disappeared from the hot implementation; Part 2 inventories exactly what went.

A second, separate scope cut rode along with it: native loading of Wasm-compiled grammars. Tree-sitter can compile a grammar to WebAssembly and load it at runtime - a capability distinct from the browser Wasm build, which stayed. Native tools set this project's performance target, and runtime Wasm grammar loading was not part of that workload.

This is not a proposal that upstream Tree-sitter should abandon incremental parsing. It is a product decision for a narrower runtime aimed at file-at-a-time analysis and agent tooling. If this branch returns to interactive editor use, the decision must be reopened.

That was the rule: delete only behind a declared boundary, never because a feature happened to be inconvenient. Deletion turned out to be the first real optimization technique: remove work whose use case has already left the building.

Refactor the Retained Runtime for Maintainability

A line-by-line translation is only readable if the reader already knows the original line by line. I instructed ChatGPT to break the monolithic, pointer-heavy port into more idiomatic internal Rust-without making the ABI-facing types "idiomatic" in ways that would break existing grammars.

The cleanup was less a redesign than a long series of small promotions. Internal raw-pointer parameters became references or slices wherever their lifetimes were local and provable; a sentinel pointer meaning "no node here" became an honest Option. Out-parameters turned into return values where the C ABI did not demand them, large modules split by responsibility so mutation sat next to the state it changed, and the dense tricks that had to stay - compact indexes into the tree, pointer arithmetic - were hidden behind narrow, named operations. Where compatibility was real, the code stayed deliberately ugly: generated-language layouts and exported functions remained C-shaped, because another binary had already committed to that shape.

That cleanup made questions answerable: Who owns this piece of the tree? Can this reference survive when its storage grows? Why does one reduction create a temporary parser state only to delete it immediately? The important output was not prettier syntax. It was a runtime organized well enough that a segfault, invariant failure, or suspicious allocation had an address in the architecture.

GLR and Memory-Layout Optimizations

Once I could understand the runtime, I directed ChatGPT back toward reduction - the "reduce" from the architecture section above, and the operation the parser performs constantly. That small operation touches both major data structures. It removes the children from the parser's working stack, then stores them under a new parent in the syntax tree. The profile showed that Tree-sitter was doing much more work around those children than the ordinary case required.

The successful changes eventually fell into four simple principles:

• Avoid work for uncommon cases. About 99% of the observed parser stac