Rewriting Tree-sitter's C Core in Rust: Migration and Compatibility

Part 2 of 4 — migration, subtraction, and readability

The hard part began after the rewrite worked

Tree-sitter's C runtime is the kind of code you are not supposed to touch. Thousands of already-compiled grammars call into it and expect symbol names, layouts, and calling conventions to be exactly where they left them. The premise of this post is simple and slightly absurd: translate that runtime into Rust without any of those compiled binaries noticing—and then keep going.

One clarification before anything else, for readers arriving from a search engine: this is not upstream Tree-sitter. It is ast-grep's fork of the Tree-sitter runtime, rewritten for ast-grep's own workload; the adventure overview (Part 1) tells the complete story in one sitting. This post, Part 2 of 4, slows down on the rewrite itself: how the migration stayed compatible with existing grammars and their external scanners—the hand-written C lexer extensions grammars ship for context-sensitive tokens—what this branch deleted, and how the surviving runtime became Rust I could reason about.

I should also introduce my collaborator. I did not hand-type this rewrite: I set the direction and constraints, and ChatGPT wrote the code. My first instruction was deliberately boring—turn the C into Rust that behaves identically, keeping the existing tests green and everything compiled code can see unchanged. Where that led, and where it went sideways, takes the rest of this post. First, the next section establishes the small amount of LR and GLR vocabulary the story needs.

(The optional LR/GLR appendix sits after the conclusion as reference material: the full parser-theory walkthrough for the curious.)

Before rewriting it: what Tree-sitter actually runs

Tree-sitter is easy to encounter as an API: give it source code and a language, receive a concrete syntax tree. Under that API is a generated table interpreter.

A Tree-sitter language starts as a grammar. The generator compiles that grammar into lexer logic, parse tables, and static metadata. Those generated artifacts are distributed with the language. At runtime, the core library does not study the grammar again; it executes the tables against the source text.

The execution pipeline has two main parts. The lexer turns source bytes into tokens. The parser combines those tokens into syntax nodes. Tree-sitter's parser is based on LR parsing, which reads input left to right and recognizes larger grammar constructs bottom-up. It keeps a numbered parse state, looks at the next token—the lookahead—and uses (state, lookahead) to select one action: shift the token and enter another state, reduce a recognized sequence into one parent subtree, or accept the completed tree.

The stack is the parser's memory. It records both the states reached so far and the recognized syntax between them. A shift extends that history; a reduction walks backward over part of it, takes the corresponding syntax values as children, and pushes their new parent.

Programming-language grammars do not always offer one safe action. A table cell may permit several actions until more input resolves the choice. Generalized LR, or GLR, keeps those possibilities alive as separate stack versions. Their shared past is stored once in a graph-structured stack (GSS); versions fork at a conflict and can merge when they later reach a compatible state.

That creates two different node systems inside Tree-sitter. StackNodes belong to the parser's temporary control history. A Subtree is Tree-sitter's compact internal reference to recognized syntax: either a token or a parent built by a reduction. Stack links carry these references, and GLR versions may share both structures, but their ownership and allocation rules are different.

Upstream Tree-sitter also supports incremental tree reuse and grammar-provided external scanners. This runtime always parses fresh snapshots but retains external-scanner compatibility.

This was the machine being rewritten: lexer execution, generated-table lookup, LR actions, GLR histories, incremental reuse, external scanning, syntax construction, error recovery, and the public tree API. The algorithm could not be treated as a black box, because the later work would reach into almost every one of those subsystems.

First: change the language, not the behavior

Before ChatGPT translated the first subsystem, I gave the migration a narrow contract. The existing tests would remain unchanged and serve as the first behavioral oracle. Generated grammars and external scanners would keep working, which meant public layouts and calling conventions stayed exactly where compiled code expected them. And the first Rust implementation would resemble the C closely enough to debug failures by comparing the two, line against line.

The order mattered. First, reproduce the C runtime in Rust closely enough that a failing test still pointed somewhere useful. Redesigning ownership, control flow, and representation at the same time would have made every mismatch a murder mystery with three suspects and no witnesses. Only after parity would the private internals become code a human could reason about. The first pass protected behavior. The later pass protected the next engineer—including me. The performance campaign between them would demonstrate, rather forcefully, why both were necessary.

The unchanged suite gave the translation a fixed target, but it could not prove every promise to the ecosystem on its own. Later, once Rust took over the runtime—the cutover narrated in the next section—ChatGPT added Rust-versus-C comparisons over real language fixtures, binary-interface checks, and an ast-grep integration gate. Those tests asked whether generated grammars and downstream users still saw the same runtime, not merely whether its internal units passed. The tests themselves changed only much later, when this branch deliberately removed incremental parsing and native Wasm-language loading. Those edits recorded a new product decision, still ahead in this story; they did not make the original translation easier to pass.

I had ChatGPT migrate one subsystem at a time

The C runtime carried years of hard-won behavior: lexing, external scanners, error recovery, tree editing, included ranges (parsing only designated slices of a file), changed ranges (reporting which parts of a tree an edit touched), query execution (running syntax-pattern searches over a tree), and public navigation. Replacing all of it in one heroic commit was never a serious option.

I knew this because I had already tried broader AI-assisted rewrites. Without clear layers, the agent gradually lost its place in the system: translated pieces stopped agreeing about their assumptions, failures no longer pointed to one seam, and each follow-up prompt inherited a state neither of us could describe precisely. The rewrite became uncontrollable long before it became complete.

Layering was the correction, not the original plan. This time I had ChatGPT climb the runtime like a dependency ladder:

• Foundational values: allocation helpers, source positions and extents (Point, Length), recovery cost (ErrorCost), and Unicode decoding.
• Syntax storage: the compact Subtree value and the rules for storing, sharing, and releasing recognized syntax.
• Generated-language tables: grammar-specific symbols, states, actions, lexing functions, and metadata.
• Lexing: the runtime that consults those tables to produce tokens.
• The GLR stack: StackHead, StackNode, and StackLink, including active parse versions, shared histories, and the subtrees between parser states.
• The public tree: Tree, Node, TreeCursor, and changed-range computation.
• The parser and reduction loop: the final coordinator connecting lexing, table lookup, stack operations, syntax construction, recovery, and acceptance.

At each layer, the Rust initially stayed close to the C. This was not the final style, but it was a useful debugging instrument: recognizably equivalent control flow kept a parity failure inside a bounded search area.

Once the final parser layer crossed over, Rust owned the active runtime. The browser WebAssembly build—the whole library compiled to Wasm so it can run in a web page—followed, and this branch retired its obsolete pure-C build path. A different Wasm feature, native loading of grammars themselves compiled to WebAssembly, was later removed because the target workload did not use it. A narrow C compatibility layer remained, but parsing, lexing, tree operations, and storage now came from Rust.

The C boundary had to survive the Rust rewrite

Rust owning the runtime did not make the C boundary disappear. Generated Tree-sitter languages are already-compiled artifacts. They communicate with the runtime through an application binary interface (ABI): the exported symbol names, calling conventions, and exact layouts that compiled code expects to find. Changing the implementation from C to Rust did not grant permission to move that boundary; existing generated parsers, external scanners, and callers remain compiled consumers of it.

The parser, tree, and generated-language interfaces therefore kept their C ABI. Rust types crossing that boundary use #[repr(C)], and layout-sensitive structures are checked for the expected size. Behind the boundary, private Rust types are free to change. At the boundary, “more idiomatic” can mean “binary incompatible,” which is a remarkably expensive style preference.

There is a useful difference between “C-shaped because the agent has not cleaned it up” and “C-shaped because another binary has already baked this layout into its data.” The former invites another cleanup prompt. The latter invites a size assertion and respectful distance.

This guarantee applies to the interfaces the branch kept. Removing native Wasm-language loading was an explicit product and API change, not something hidden inside the C-to-Rust translation.

The benchmark crossed twenty percent. Then the parser crashed.

Once the port passed its compatibility gates, I gave ChatGPT a much broader instruction: /goal improve the perf by 20%. /goal is the command that hands the agent an objective and kicks off a long autonomous run: it plans, implements, measures, and keeps going without waiting for me. I supplied the major directions—profile the runtime, understand its data layouts, and consider algorithmic as well as local changes—and then largely got out of the way.

The run continued through several days and nights with little human supervision. ChatGPT profiled the runtime, implemented candidates, ran the gates, and used the results to choose the next change. In the narrow sense, it worked: the benchmark eventually crossed the twenty-percent target.

But each time I looked, the diff had grown another layer: new ownership paths, layout experiments, and fast paths grafted over the previous day's, each individually plausible, the whole accumulating faster than I could build a reliable model of it. Then, after days of green benchmarks, the parser began segfaulting. Not a Rust panic with a stack trace, not a failed assertion—the process simply died, somewhere inside code neither of us could fully explain. The autonomous run had produced a winning benchmark and an artifact I could not trust. A twenty-percent result is not an asset when nobody can explain which invariant bought it or which input will make it crash.

So I did not merely stop the performance work—I reverted it. Every commit from the /goal run came out of the branch, and the twenty percent left with them. When this Rust runtime later reached parity with C, that result was earned by the deletion and readability work below, not salvaged from the run that crashed. Before asking for another optimization, I needed to reduce the runtime's scope and make its remaining ownership rules locally understandable. The following work was not routine polish after the rewrite; it was how the rewrite regained a trustworthy baseline.

The feature list had to meet the actual workload

The adventure overview explains the product reasoning: editors benefit from incremental reuse, while this ast-grep branch parses complete file snapshots. That argument had existed from the start of the project; the crashed performance run is what made acting on it urgent, because a runtime I now had to re-understand from scratch should be the smallest one the product actually needed. Here, the interesting part is what the decision removed from the runtime.

I instructed ChatGPT to delete the incremental path while keeping old_tree in the parser API for compatibility. The parser no longer retains the previous root or computes included-range differences in preparation for reuse. Its ReusableNode cursor—which walked the old tree looking for a subtree valid at the current state and position—disappeared.

That deletion continued into the hot loop. Lookahead selection stopped asking whether an old subtree could replace fresh lexing. The special path for breaking a reusable parent back into stack entries disappeared, as did the incremental-only reduction path and the extra bookkeeping it required in the GLR stack. Fresh lexing and one ordinary reduction ownership path became the only way through the parser.

Dormant stack experiments, failed optimization scaffolding, obsolete build paths, and native Wasm-language loading followed. These were explicit product cuts, not advice for upstream Tree-sitter. If this branch returns to interactive editor use, incremental parsing must be designed back in rather than quietly assumed.

Then came the second rewrite: this one was for humans

Once behavior was stable, the C-shaped translation had completed its mission. It was now possible to make the code explain itself.

I did not ask for a grand redesign. Instead, I had ChatGPT make a long series of small, measured changes. Raw pointer conventions became ordinary Rust references, slices, return values, and explicit optional states where the ABI allowed it. Ownership operations gained names, mutation moved closer to the state it changed, and the parser's major responsibilities separated into focused modules.

The patches were intentionally small. Each could be reviewed, tested, benchmarked, and blamed. A sweeping “make this idiomatic” rewrite would have been much harder to trust—and this project had already tried that genre.

Gradually, the module structure began to tell the runtime story. The parser asks the lexer for a token, looks up actions through the language, manipulates histories through the stack, and builds subtrees. The accepted subtree becomes a tree; nodes and cursors expose public views over it. Recovery and balancing (a pass in which Tree-sitter rebalances deeply repeated subtrees after parsing) remain visible phases rather than surprising appendices inside one enormous function.

The goal was not maximum Rust flavor. It was local reasoning. A reader should be able to answer:

• Who owns this buffer?
• Is this subtree handle borrowed, copied, or moved?
• Does this function operate on one stack path or enumerate a graph?
• Which types are frozen by ABI and which are private implementation details?

When those answers became easier, performance work became easier too. The same refactor that hides pointer arithmetic behind a subtree handle also creates one place to measure handle resolution. The stack module makes version churn visible. The reduction module reveals the child-collection lifecycle. Readable code did not automatically run faster, but it made expensive behavior harder to disguise as inevitability.

Readability still had to answer to the stopwatch

Compact runtime types punish well-intentioned abstraction.

One experiment replaced the compact eight-byte Subtree representation—a C-style union whose field access required unsafe—with a direct, explicit Rust enum. It was pleasant to inspect and sixteen bytes wide. Parse time increased by 19.74%. The CPU was apparently unmoved by the improved semantic clarity.

The answer was not to abandon readable APIs. It was to separate interface from representation. Internal methods could expose meaningful operations while the hot handle remained compact and private.

That became the general rule for cleanup:

1. preserve the retained behavior and ABI;
2. compare the change with the immediately preceding Rust implementation;
3. keep clarity improvements that remain within noise;
4. isolate compact or unsafe representation code behind narrow interfaces; and
5. revert abstractions whose runtime cost overwhelms their maintenance value.

Rust-versus-C measurements answered a broad question: had the rewrite reached competitive performance? Rust-to-Rust measurements answered the local one: did this change help? Mix the two up and you end up judging a small Rust refactor against a distant C baseline—an elaborate way of flipping a coin.

What survived the rewrite

The strange part is that the performance campaign became useful only after I stopped and reverted it. Its failure exposed the missing prerequisite: a runtime whose behavior could be preserved and whose internals could be understood at the same time.

That is what survived this stage. The Rust core kept its promise to the ecosystem: existing generated grammars and external scanners still worked through the public C ABI. Incremental old-tree reuse and native loading of Wasm grammars remained explicit exclusions for this fresh-snapshot branch. Behind the ABI, the private machinery could finally be followed one subsystem at a time. And with nothing inherited from the reverted /goal run, the layered work had to earn the performance back on its own: at the last complete checkpoint before the later stack and arena work (an arena serves many allocations from one shared memory block), Rust and C were at practical parity when the tested languages were weighted equally.

That was enough to change the next question. I no longer had to ask, “Did the translation preserve Tree-sitter?” I could ask, “Why does this particular mechanism run on every parse?” The new module organization made allocations, ownership transfers, stack-version churn, and repeated table work visible enough to investigate rather than merely inherit.

The next post follows the first large answer. Profiling made stack allocation and reduction bookkeeping worth investigating; a runtime audit then found that 98.898% of released graph nodes had only one predecessor. The generalized stack was built for forks, but its measured released-node population was overwhelmingly linear. Continue with Improving Tree-sitter's GLR Algorithm and Memory Layout.

---

The story ends here; Part 3 picks it up. What follows is reference material for the curious: the LR and GLR theory behind everything above, built from one tiny expression. For the other half—how Tree-sitter's runtime actually implements this machinery with heads, nodes, and links—see Part 3's appendix.

Appendix: How LR and GLR work

The rewrite story above needs only the short model: generated tables choose parser actions, a stack records the recognized history, and GLR can preserve several histories when one answer is not yet safe. This appendix builds the complete model from one tiny expression; the runtime implementation side lives in Part 3's appendix.

A parser is a table interpreter with a stack

Source code does not become a syntax tree in one magical jump. First, the lexer groups characters into tokens. For this tiny expression:

1 + 2

the lexer might produce:

number("1")   "+"   number("2")   end-of-file

The parser then decides how those tokens fit the grammar. This toy grammar has two rules:

expression -> number
expression -> expression "+" number

An LR parser does not search those rules from scratch at runtime. A parser generator has already analyzed the grammar and compiled its decisions into two closely related tables:

• the action table says what to do with the next token: shift it, reduce a rule, accept the file, or report an error;
• the goto table says which state to enter after a reduction has produced a grammar symbol such as expression.

A parser state is a compact summary of the history that matters for the next decision. It is not a source position and it is not a syntax-tree node. A state means something closer to “I have recognized enough of these grammar rules that these tokens could legally come next.” The generated table assigns that summary a small integer because comparing prose in the hot loop would be an ambitious performance strategy.

At runtime the parser therefore needs only:

• one lookahead token, meaning the next token it has not consumed;
• one stack of numbered states; and
• syntax values representing the input already recognized.

For the toy grammar, an illustrative fragment of the generated tables could look like this. The exact state numbers do not matter; generated grammars choose them.

State	Next number	Next +	Next end-of-file	Goto expression
0	shift to 3	error	error	2
2	error	shift to 4	accept	—
3	error	reduce expression -> number	reduce expression -> number	—
4	shift to 5	error	error	—
5	error	reduce expression -> expression "+" number	reduce expression -> expression "+" number	—

The pair (top state, lookahead token) selects one action:

• shift: consume the lookahead, turn it into a leaf subtree, and push the state named by the table;
• reduce: pop the recognized right-hand side of a grammar rule, create one parent subtree, and use the goto table to push the rule's left-hand side;
• accept: return the finished tree; and
• recover: do something principled with invalid input instead of falling dramatically onto the floor.

A shift advances the input. A reduction does not. This distinction is the engine of LR parsing, so it is worth following the complete expression.

1. State 0 sees number("1"). The table says shift to 3. The parser consumes 1 and pushes its leaf subtree.
2. State 3 sees +. The table says reduce expression -> number. The parser pops one recognized symbol, wraps it in an expression, uncovers state 0, and asks goto(0, expression). The answer is state 2. The + is still waiting; reductions reorganize recognized input rather than consuming new input.
3. State 2 sees + and shifts to state 4.
4. State 4 sees number("2") and shifts to state 5.
5. State 5 sees end-of-file and reduces the three recognized symbols expression "+" number to one expression.
6. State 2 now sees end-of-file and accepts.

The stack is the parser's memory between those table lookups. Conceptually, it alternates states with recognized syntax:

state 0 -- expression("1") --> state 2 -- "+" --> state 4

The current state is at the right. A reduction walks left over as many grammar symbols as the rule contains, builds their parent, then follows one goto edge back to the right. A three-child rule pops three syntax values; it does not pop three bytes or necessarily three tokens, because one child may already represent a large expression.

The repeated lookaheads are the important part of the trace. Rows 1, 3, and 4 shift, so the lookahead changes in the following row. Rows 2 and 5 reduce, so + and end-of-file appear twice: once while the stack is reorganized and again for the next table decision. The stack column shows syntax values sandwiched between states, while the final column shows whether that action created a leaf or combined existing children into a parent.

Tree-sitter stores two different kinds of node

The first kind is the subtree defined back in the body: Tree-sitter's compact reference to recognized syntax. A leaf subtree might represent 2. An internal subtree might represent the entire 1 + 2.

The parser stack has nodes too, but they are not syntax nodes. A Tree-sitter stack node stores a parse state and bookkeeping about that point in the parse. Its backward link to the preceding stack node carries the subtree that was recognized between the two states. Physically, one linear history looks roughly like this:

current stack node (state 4)
    -- subtree "+" --> stack node (state 2)
    -- subtree expression("1") --> stack node (state 0)

That backward direction is useful: the parser constantly starts at the current head and pops toward older history. Parse states answer “what may happen next?” Syntax subtrees answer “what did I recognize to get here?” Mixing the two kinds of node produces extremely confusing conversations about allocation. I know because I held several.

GLR: when the table answers “both”

The toy action table has at most one answer in each cell. Real programming- language grammars occasionally refuse to be so cooperative. A table cell may contain a shift/reduce conflict—either consume the lookahead or finish a rule first—or a reduce/reduce conflict, where two rules could both finish.

Imagine the parser has recognized 1 + 2 and sees *. One interpretation reduces the addition first. Another shifts * first and lets multiplication bind more tightly. A conventional grammar usually resolves this example with precedence, but it illustrates the physical choice. Tree-sitter grammars can also declare conflicts intentionally, especially where a few more tokens will make the correct interpretation obvious.

A conflict does not necessarily mean the final source is ambiguous. It only means the parser cannot safely decide yet. One possibility may fail on the next token; two possibilities may later reach equivalent parser states; or both may survive until Tree-sitter compares precedence, error cost, and other parse quality information.

Generalized LR, or GLR, means following several valid LR histories at once. At a conflict, the parser performs every permitted action. A shift branch consumes the token. A reduction branch keeps the same lookahead, rewrites the top of its stack, and consults the table again. The branches are now at different states and may even be at different input positions.

Tree-sitter calls each active history a stack version. “Version” sounds like a complete copied stack, but it is mostly a head: a reference to the newest stack node plus metadata used to compare and manage that possibility.

Sharing history turns the stack into a graph

Copying the complete stack at every conflict would be expensive, so versions share their common history. The result is a graph-structured stack, or GSS: stack nodes point backward, several heads can share the same older nodes, and a later node can have more than one predecessor when compatible histories merge. A link between two stack nodes carries the subtree recognized by that transition.

Operationally, it is less mystical than its name:

• push creates a new head and links it to its predecessor;
• pop walks backward across links and collects their subtrees;
• fork gives two versions different heads over the same older prefix; and
• merge gives one compatible destination alternate predecessor links instead of keeping duplicate future work.

Read the arrows backward from each head. Before the conflict there is one chain. After it, two heads point into the same green prefix; the parser did not copy that prefix. When both histories later arrive at the same state and input position, one destination can retain links to both predecessors. The shape is now a graph even though every individual path through it is still an ordinary LR stack.

This changes reduction. In a linear stack, reducing a rule with three children has one obvious answer: walk back three links. In a graph-structured stack, there may be several three-link paths. The parser must enumerate them, build a parent for each valid child sequence, and merge equivalent destinations. The graph is what preserves correctness when syntax is genuinely uncertain.

It also explains the performance question taken up by the next post. Most real input spends very little time forked, yet an eager GLR implementation can still allocate graph nodes, maintain versions, probe for merges, and prepare for multiple pop paths on every deterministic shift and reduction.