alecthomas / alecthomas/chroma

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

Open
#1,377 1 comment 0 reactions 0 assignees View on GitHub
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.