alecthomas / alecthomas/chroma
Infinite loop in LexerState.Iterator when a rule cycle never advances Pos
- Dominant language
- Go
- Stars
- 5k
- Forks
- 522
- Avg merge
- 1d 14h
- Merged PRs (30d)
- 11
Description
🤖
`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
```
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.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.