Infinite loop in LexerState.Iterator when a rule cycle never advances Pos
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)
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 returnsroot 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.
lx := lexers.Get("Jungle")
lx.Tokenise(nil, "/") // never returnsConfirmed hanging (with a live goroutine dump showing matchRules/regexp2 actively spinning, not blocked) on:
/,*,:,",!,%,'— any of these alone- tag
v2.24.1and the currentv2branch tip (976b215) — identicaljungle.xml, identicalIteratorloop 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 +:
<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:
lx := lexers.Get("JSONata")
lx.Tokenise(nil, `"`) // never returnsThis 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(rootchromapackage) — the minimal isolated grammar above.TestJungleHangsOnUnhandledPunctuation(lexerspackage) — 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.
Source: alecthomas/chroma