#1377·chroma

Infinite loop in LexerState.Iterator when a rule cycle never advances Pos

Author: eugenioenkoCreated Sep 11, 2026Updated Sep 11, 2026

LexerState.Iterator (regexp.go) has no guard against a rule that matches zero-width and mutates the state stack (push/pop) without advancing Pos. If two states form such a cycle, Tokenise / Iterator never returns — not slow, not eventually-consistent, an unconditional infinite loop that spins one CPU core at 100%.

This is a different failure mode from #410 (catastrophic regex backtracking inside a single match, fixed by the per-rule MatchTimeout). Here every individual regex match completes in microseconds — the outer loop is what never terminates, so MatchTimeout does not help.

Root cause (isolated, no dependency on any bundled lexer)

go
lexer := mustNewLexer(t, &Config{Name: "loopy"}, Rules{
	"root": {{`(?=\S)`, None, Push("a")}},
	"a":    {{`(?=\S)`, None, Push("b")}},
	"b":    {{``, None, Pop(1)}},
})
lexer.Tokenise(nil, "x") // .Tokens() never returns

root pushes a on a zero-width lookahead; a pushes b the same way; b's unconditional, pattern-less rule pops back to a. Every step is individually a valid, successful, zero-width match, so nothing ever trips an error — Pos just never leaves 0 and the stack oscillates [root,a][root,a,b] forever. The loop condition in Iterator (for l.Pos < end && len(l.Stack) > 0) has no check for "did Pos move since the last time we were at this stack depth."

Real-world trigger: the bundled Jungle lexer

lexers/embedded/jungle.xml's instruction state pushes var on (?=\S); var's catch-all rule (no pattern → always matches, zero-width) pops back to instruction whenever none of var's specific rules match. var only consumes . ; [ ] ( ) $ or [a-zA-Z_]\w* — any other character falls straight into the cycle above.

go
lx := lexers.Get("Jungle")
lx.Tokenise(nil, "/") // never returns

Confirmed hanging (with a live goroutine dump showing matchRules/regexp2 actively spinning, not blocked) on:

  • /, *, :, ", !, %, ' — any of these alone
  • tag v2.24.1 and the current v2 branch tip (976b215) — identical jungle.xml, identical Iterator loop shape
  • main/v3 as well (same grammar, same engine logic)

Practical impact: any consumer that calls lexers.Match()/lexers.Get("Jungle") on a file matching *.jungle and tokenises it hangs permanently the moment that content includes one of those characters — which is close to unavoidable for real Jungle (Garmin ConnectIQ) source. We hit this via a Go TUI editor that builds a Highlighter synchronously on file open.

A second, independent trigger: JSONata

Swept every bundled lexer (lexers.Names(false), ~200+) against every printable ASCII character, printable Latin Extended-A/B characters, and a handful of short common tokens (==, ->, [], etc.), each with a per-input timeout. Exactly two lexers hang: Jungle (above) and JSONata.

JSONata's grammar (lexers/embedded/jsonata.xml) is a simpler variant of the same defect: one state, no push/pop at all. Its final, catch-all rule uses * (zero-or-more) rather than +:

xml
<rule pattern="[a-zA-Z0-9_]*">
  <token type="Name"/>
</rule>

A lone " doesn't match any earlier rule (the string rules all require a closing quote), falls through to this catch-all, which matches zero characters and still counts as a successful match. Pos never advances, the same rule wins again next iteration, same state — no stack manipulation involved at all:

go
lx := lexers.Get("JSONata")
lx.Tokenise(nil, `"`) // never returns

This confirms the gap isn't specific to state-cycling grammars (Jungle) — a single self-repeating zero-width rule in one state is enough on its own. Two independently-authored lexers hit it, which points at a systemic engine gap rather than a one-off grammar mistake.

Reproduction tests

A companion PR adds two tests demonstrating the Jungle case (no fix proposed there — they use a goroutine + timeout so the test suite itself does not hang, and fail on purpose today):

  • TestZeroWidthPushPopCausesInfiniteLoop (root chroma package) — the minimal isolated grammar above.
  • TestJungleHangsOnUnhandledPunctuation (lexers package) — the real Jungle lexer, all 7 characters.

Happy to add a TestJSONataHangsOnLoneQuote alongside them if that's useful.

Draft PR: https://github.com/alecthomas/chroma/pull/1378

Possible fix direction

Track a counter of consecutive zero-width matches in Iterator's loop, reset whenever a match consumes ≥1 rune. If the streak exceeds len(l.Rules) (total distinct states), the automaton has revisited a state without progress and must be in a cycle — fall back to the existing "no match" convention a few lines above (emit an Error token for the byte at Pos, advance one rune) instead of looping. Happy to build this out if it's a direction you'd take — didn't want to presume the right trade-off (e.g. whether emitting Error vs. some other recovery is preferred) without checking first.