cpp: Parser.Parse does not return on a 20-byte input (the action-cell transaction finds no version, then two relex steps undo each other) #1558

A 20-byte C++ input makes Parser.Parse loop without end on the plain (DFA lexer) route. The input is ;e s d>f(T);template. With no parser timeout, the process was still looping after 60 s, at 100,000,000 turns of the loop, and the state sampled at every power of ten was the same. I expect it never returns; I observed 60 s. Locked C parses the same 20 bytes in 0.025 ms. The registered token source returns a tree for it in under 3 ms.

The 1 KB C++ input from a review of the action-cell transaction work (a mutation of upstream corpus case concepts_002.cpp) is the same loop. Its parse stops at iteration 146 whether the timeout is 1 s or 40 s, because the loop does not count iterations. Delta debugging shrinks all four inputs that timed out in that review to 20 to 43 bytes. The four originals and the 20-byte input spin in the same two places; I did not instrument the other three minimized inputs.

Lane: Legacy fixes (Q item). The loop sits on the fall-through of the C-order action-cell transaction: it needs the transaction path (packed version order) and no C recovery port, so it concerns the Q-transaction work (see "Is the transaction involved?").

Measurements

Main f015f68. Go 1.25.14, linux/amd64 (20 host CPUs, container limit 4 CPUs and 6 GiB), Docker image gotreesitter/cgo-harness:go1.25-local. Locked C: tree-sitter runtime 0.27.1, grammar tree-sitter-cpp at c0092228, through cgo_harness at f015f68. "Plain" is Parser.Parse. "Registry" is ParseWithTokenSource with the cpp TokenSourceFactory, which is what grammars.ParseFile and LangEntry.Parse do.

The 1,068-byte input. concepts_002.cpp (1,069 bytes) with byte 593 deleted, so line 18 reads template<typename T requires Addable<T> && Subtractable<T> with no closing >. SHA-256 adc49fc9a0b999deb02bd0509cff651dda7d86ed2723033583c4dcc8e8f51297. It is cpp_concepts_002_del1_5of9.cpp in an earlier run's results (stress.jsonl, sweepS1.main.cpp.jsonl).

• Registry is 5.0 times (min) and 8.1 times (median) the C time on this input.
• Plain was never faster than the limit. Against C's median it is at least 196,000 times slower at 40 s, and there is no upper bound.

The four inputs that timed out in the review, plain route, 2 s limit. All four finish on the registry route.

Minimized. Delta debugging with the predicate "the plain route times out at 500 ms" (538 to 1,419 parses each):

The 20-byte input (;e s d>f(T);template, SHA-256 2453cceeb12cc6e13f6cf2240c68087d8a98f2ce1f6ba61e6b268d0ab07e5a8f):

What triggers it. Each row is ;e s d>f(T); plus the text shown; 300 ms limit, plain route. Dropping the leading ; or any other part of the prefix makes the parse finish.

Twelve keywords trigger it. The type keyword int and the identifier x do not: they stop the parse with no_stacks_alive at once. I did not work out what separates the two groups.

Cause

I counted every goto retryAction in parseInternal with a debug overlay on a scratch copy (main stays untouched). On all five inputs, two sites account for every turn, in lockstep:

• The stack is always the second of two (si=1, stacks=2), in state 113. The token bytes never change.
• At the 1 s mark each site had run 1,000,000 times or more, on each of the four larger inputs.
• On the 20-byte input the entry to retryAction (parser.go:6492) was reached 100,000,000 times in 60 s.
• Nothing counts or bounds these turns. Iterations stays at 11. The zeroWidthRescueBudget bounds only the zero-width rescue.
• Goroutine dumps of the 20-byte input at 2, 3 and 4 s show parseInternal in the reduce step (cAppendReductionActionVersions), in relexTokenForStackLexState (inside Lexer.scanInto) and in tryRelexCurrentStateDFA (inside promoteKeyword). That fits a loop with one reduce step and two relex steps per turn.
• The CPU profile of the 1,068-byte input at 10 s has 99.8% of its samples inside retryFullParseForOrigin. So in the 1 KB case the loop is reached in a retry pass. In the 20-byte case it is reached in the first pass (no retry frame in the dumps). Cumulative shares:

Why the actions are rejected on each turn, and why the relex helpers each believe the other reading has an action, I did not establish.

Is the transaction involved?

Yes. The loop needs the transaction path. Each turn calls the transaction once and gets nothing back, and the two relex steps then flip the token.

Times are the first parse in a fresh process, so they include warm-up.

The route into the loop is in the code. For an action cell that needs the transaction (more than one action, or a reduce), parseInternal calls cAppendActionCellReductionVersions (parser.go:6544). When no version survives and there is no terminal action, it sets actions = nil and continues "through the ordinary no-action path so keyword repair, re-lexing, and recovery retain their existing ownership" (parser.go:6611 to 6615). That path holds both goto retryAction sites above. The cell in state 113 has two actions for each of the two readings: a reduce to translation_unit_repeat1 and a shift to state 1962 or 1207. With the packed order off, the ordinary dispatch applies them as GLR forks and the parse survives.

I printed what the transaction call at parser.go:6544 returns on each turn. Of the first 1,000,000 calls, 999,976 on the 20-byte input and 998,932 on the 1,068-byte input have one shape: the second of two stacks, state 113, a cell with two actions, and the call returns no terminal action (terminalOrdinal=-1) and no new version (lastReductionVersion=-1). So on every turn the transaction finds nothing for that cell, the code drops into the no-action path, and the two relex steps flip the token. The same call finds nothing for the first dispatch of the keyword too (calls 22 and 25 on the 20-byte input).

Why the transaction finds nothing for a cell that holds a shift, I did not establish.

An earlier profile said the time is in relex and retry. That is where the CPU goes. The data here adds that the loop only exists on the transaction path. The Q-transaction work does not change it: an earlier run's stress.jsonl records the same timeout and the same digest on main and on its qabcd variant. I also applied the shipping variant qa-wave-scratch to main through -overlay (its two files differ from main by exactly the variant's 176 changed lines). The three inputs above still time out at 500 ms with the same iteration counts (11, 11 and 14), and the 1,068-byte input still stops at iteration 146 after 2 s.

Reproduction

The inputs, harness and probe sources, and raw outputs are in issue-cpp-parse-livelock-f015f6802.tar.gz (SHA-256 in issue-cpp-parse-livelock-f015f6802.sha256 next to it).

1. Use a source copy of main f015f68 as the module github.com/odvcencio/gotreesitter (the files in repro/go.mod use a replace directive).
2. Build the standalone program (repro/b_livelock/main.go in the evidence archive): go build -tags grammar_subset,grammar_subset_cpp -o b_livelock ./b_livelock.
3. Run ./b_livelock. The input is ;e s d>f(T);template, the timeout is 2 s. Expected: the registry line shows stop=no_stacks_alive after about 20 ms (the first parse in the process). The plain line shows stop=timeout wall=2000.x ms iterations=11.
4. Run ./b_livelock -timeout 0 -watchdog 20. Expected: the registry line, then WATCHDOG: Parse did not return within 20 s and exit status 9.
5. For the 1 KB input and the profile: run bin/oak probe -lang cpp -file b/inputs/stress_concepts_002_del1.cpp -route plain -timeout-ms 10000 -cpuprofile cpu.pprof, then go tool pprof -top -cum bin/oak cpu.pprof. The harness sources are in the archive.
6. For the loop counters: build the harness with the overlay ov/dbg.json (the diffs are in the archive) and run it with OAK_LOOP=1. It prints a line each time a site's count reaches a power of ten.

Lane

Legacy fixes (Q item). The loop sits on the fall-through of the C-order action-cell transaction, the path the Q-transaction work changes. Two places could stop it, and I tested neither:

• Make the transaction return a version for the two-action cell, as the ordinary dispatch does.
• Bound the fall-through: a limit on relex retries for one stack and one token, so the two relex steps cannot undo each other without end.

Constraints from the design: no language-name test (D6); report counters before and after in the PR (D10). The cpp rows in the counter ledger do not exercise this path, so I expect no ledger change.

Not the Core lane unless the owner decides the compact route (D1) makes a legacy fix pointless. I did not test the compact route.

Related issues

I searched issues and pull requests (open and closed) for: infinite loop, livelock, hang, tryRelexCurrentStateDFA, relexTokenForStackLexState, retryAction, "parse timeout cpp", template hang. Nothing covers this. Closest:

• # field reports from downstream user (Windows GUI toolkit, pure-Go editor widget, multiple syntaxes) on latest release versions #454 (downstream field reports, open): mentions cpp coverage and timing, not this loop.
• c: large designated-initializer arrays parse ~100-400x slower than expected (v0.51.0) #1100 (closed): c large designated-initializer arrays parse 100 to 400 times slower than expected. Different cause.
• fix(parser): Share one timeout deadline across parse routes #1131 (merged): shared one timeout deadline across parse routes. Earlier work on the same timeout; not about this loop.

A possible link to #1559 (cpp truncation)

In #1559, two of the five files first differ from the registry token stream at a word that the registry source returns as a keyword (default) and the plain route returns as an identifier. Here the loop flips a word between its keyword and identifier readings. Both may come from keyword handling in the DFA token source (promoteKeyword). I did not test that.

What I did not verify

• Other languages. The harness has only cpp built in. Any language with a keyword capture token and the DFA relex steps could loop the same way.
• The compact route.
• Whether the loop is reachable through the registry route. Twelve keyword spellings after the same prefix all finish there, but I did not search further.
• A fix. I did not change engine code.
• The cold first-parse times. The registry column shows the first parse of a process, which includes warm-up, next to warmed numbers where I have them.
• Timings come from a shared host and are directional. A 40 s timeout against a 0.2 ms parse is far outside any load effect.
• Every Go result here comes from an unmodified source copy of main f015f68.