Why can a regex engine that advances a set of states in one pass not support backreferences?
answer
- the set remembers pattern positions
- not the characters matched so far
- a repeat of arbitrary earlier text
- outside the regular languages entirely
- membership becomes NP-complete
basics
~20 sA live state set records where the pattern is, not what the text matched. A backreference demands that an arbitrarily long captured substring occur again, and no fixed set of machine states can carry that text forward.
solid answer
~40 sThe one-pass architecture works because the set of live states is bounded by the pattern's size: it forgets how it arrived, keeping only where it is. A backreference needs the opposite - the actual characters an earlier group captured, compared against input arriving later. A pattern such as `(.*)\1` denotes the strings that are some text repeated twice, and no finite-state machine accepts that language; deciding a match for patterns with backreferences is NP-complete in general. A backtracking engine can offer the feature only because it is mid-execution on one candidate match and therefore holds the captured text. Capture *positions* are a different ask: they can be carried alongside the state set without leaving the one-pass model.
go deeper
Know that not every pattern feature works in every engine, and that referring back to text a pattern already matched is the feature most often missing.
Explain that the live set stores pattern positions rather than matched characters, and that a pattern repeating an arbitrary captured substring describes a language no finite-state machine accepts.
Audit a pattern set for the features it actually uses before assuming it can move to a one-pass engine, and decide whether unsupported patterns are rejected or routed to a separate path.
Decide whether the pattern language your platform exposes should contain features that cost the worst-case guarantee at all; removing one feature can be worth more than any tuning.
## What the live set actually knows A one-pass engine holds **the set of positions inside the pattern that the input read so far is consistent with**. That is the entire memory of the match. It is bounded by the number of states in the compiled pattern, which is why the per-character cost is bounded - and it is bounded precisely because **paths merge**. Two completely different prefixes that land on the same pattern position become one entry, and the difference between them is gone for good. That merging is the architecture's whole economic basis, and it is also the exact reason a backreference cannot ride on it. ## A backreference asks for the text, not the position A backreference says: *whatever the earlier group captured, match that again here*. The captured text can be arbitrarily long, so honouring it requires carrying an arbitrary amount of input forward - unbounded memory, in a model whose defining property is bounded memory. The formal consequence is sharp: - The pattern `(.*)\1` denotes exactly the strings of the form `ww` - some text followed by an identical copy. That set of strings is **not regular**, so no finite-state machine accepts it, however many states you give it. - Beyond expressiveness, the cost changes class too: deciding whether a pattern with backreferences matches a given string is **NP-complete** in general. It is not merely a slower version of the same problem. A backtracking engine can offer backreferences only because it is executing **one candidate match at a time** and therefore still holds the captured span. That is the same property that costs it its worst-case bound. ## Capture groups are not the same request A common confusion is to assume that if backreferences are impossible, capture groups must be too. They are not. Reporting **where** each group began and ended can be done in a one-pass engine by carrying tag positions alongside each live state and resolving them when a match completes. It costs memory and implementation complexity, and it makes the state comparison richer, but it does not leave the regular class - because positions are bounded data, while captured text is not. ## Lookaround is the interesting middle case An assertion over a **regular** sub-pattern does not leave the regular class at all: the regular languages are closed under intersection and complement, so in principle a one-pass machine can carry lookahead and lookbehind. The obstacle is constructive rather than theoretical - complementing a machine means determinising it first, which can blow the state count up, and combining assertions with the rest of the pattern complicates an engine built around a simple step function. So implementations genuinely differ: some one-pass engines offer bounded lookaround, others omit it entirely and route such patterns elsewhere. ## Recursive patterns go further still A pattern that can invoke itself to match nested structure needs a stack, not a set - unbounded nesting depth is outside finite state altogether. This is the same reason a pattern language alone cannot validate arbitrarily nested delimiters. ## Feature by feature | Feature | Needs the matched text? | Can a one-pass engine carry it? | |---|---|---| | Alternation, repetition, classes | No | Yes, natively | | Capture group positions | No - positions only | Yes, with tags alongside the state set | | Anchors and zero-width boundaries | No | Yes, from local context | | Lookaround over regular sub-patterns | No | In principle yes; costly to construct, so support differs | | Backreference | Yes | No - the language is not regular | | Recursive sub-pattern | Needs a stack | No - finite state cannot count nesting | ## What an engine should do with a pattern it cannot run There are two respectable behaviours and one bad one. Respectable: **reject the pattern at compile time** with an error naming the unsupported feature, or **dispatch that pattern to a backtracking matcher** while the rest of the pattern set stays on the one-pass path. The bad behaviour is silently accepting the pattern and matching something subtly different, because nobody reads a filter rule twice after it deploys. For a system that accepts patterns from outside the team, this is the design question that matters more than raw speed: a compile-time gate turns 'we reviewed the patterns' into something the platform enforces, and it is the same gate that keeps the worst case bounded.
- Is lookaround also impossible in a one-pass engine?No. An assertion over a regular sub-pattern keeps the language regular, because the regular languages are closed under intersection and complement, so a one-pass machine can in principle carry it. The barrier is constructive - complementation means determinising, which can blow up the state count - so implementations differ, some offering bounded lookaround and others none.
- Do capture groups themselves force backtracking?No. Reporting the start and end offsets of each group can be done in one pass by carrying tag positions alongside the live states and resolving them at the end. It costs memory and complexity, not the linear bound. What leaves the regular class is comparing later input against the captured text.
- What should an engine do when handed a pattern feature it cannot run?Either reject it at compile time with an error naming the feature, or route that one pattern to a backtracking matcher while the rest stay on the one-pass path. The failure to avoid is accepting the pattern silently and matching something slightly different from what its author intended.
saying these in an interview costs you the question
- Says backreferences are merely slow, not a different class of problem.
- Thinks a bigger state machine could remember the captured text.
- Claims capture groups cannot work without a backtracking engine.
- Believes lookaround is provably impossible in a one-pass engine.
- Assumes every engine accepts every pattern it is handed.