skip to content

Why can a pattern that is able to match the empty string stall a global find-and-replace?

level: seniorimportance: nice to knowfreq 30%

answer

  1. the match end did not move
  2. scanning resumes at the previous end
  3. engines bump forward after empty
  4. an empty match at every position
  5. `*` may consume nothing, `+` cannot

basics

~20 s

A global scan continues from the end of the previous match. A zero-width match ends where it began, so the next attempt starts at the same position and succeeds again, forever — unless the engine forces the position forward by one.

solid answer

~50 s

Repeated matching is a loop: find a match, then resume scanning at its end offset. That loop only terminates because the offset grows. When a pattern can match the empty string — `a*`, an optional group, a bare lookahead — the match end equals the match start, so resuming at the end resumes at the same place and the same empty match is found again. Engines break the cycle by advancing the scan position one unit after a zero-width match, which is why a global replace of `a*` over `bbb` yields `XbXbXbX`: an empty match at each of the four positions. The behaviour is not a bug, but it is almost never what the author wanted. The fix is to make the empty match impossible — `+` instead of `*`, or a mandatory element in the pattern.

code

pseudocode · 11 lines
pseudocode
pos = 0
while pos <= length(text):
    m = first_match_starting_at_or_after(text, pos)
    if m is none:
        break
    emit replacement_for(m)
    if end(m) == start(m):          # zero-width match
        copy one character at end(m)
        pos = end(m) + 1            # forced bump; without it, pos never grows
    else:
        pos = end(m)

go deeper

for a junior

Know that a match can have length zero, and that a pattern using * may match nothing at all. + requires at least one character; * does not.

for a middle

Explain repeated matching as a loop that resumes at the previous match's end, and show why a zero-length span makes that position stop advancing until the engine forces it forward.

for a senior

Recognise the symptom in the wild — a replacement appearing between every character, or a split returning one piece per character — and fix the pattern rather than the loop around it.

for a principal

Where patterns are supplied as configuration, treat a zero-width match as an input-validation concern: probe a candidate pattern and reject one that matches empty, so a rule change cannot turn a rewrite pass into a per-character rewrite.

## What a global scan does between matches "Replace every match" is not a primitive. It is a loop over single matches, and the loop's only progress guarantee is that the next search starts where the previous match ended: 1. Search from the current scan position. 2. If there is no match, stop. 3. Emit the replacement for the matched span. 4. Set the scan position to the end offset of that match. 5. Go to step 1. Step 4 is the whole story. The loop terminates because the end offset of each match is strictly greater than the position it started from — which is true for every match that consumes at least one character, and false for one that consumes none. ## Zero width is a fixed point A **zero-width** (empty) match is a legitimate success whose span has length zero: start offset equals end offset. Feed one into the loop above and step 4 sets the scan position to exactly where it already was, so step 1 searches the same position, finds the same empty match, and the loop never advances. Nothing is wrong with the match; the loop's progress assumption is simply violated. Engines therefore carry a guard: **after a zero-width match, advance the scan position by one unit** (copying that unit through unchanged in a replacement). That turns a non-terminating loop into a terminating one with surprising output, which is how the behaviour usually reaches you. ## What you actually see Replace every match of `a*` with `X` in the subject `bbb`. The pattern can match zero `a`s anywhere, and there are four positions — before each `b` and after the last one: - position 0: empty match, emit `X`, copy `b`, bump to 1 - position 1: empty match, emit `X`, copy `b`, bump to 2 - position 2: empty match, emit `X`, copy `b`, bump to 3 - position 3 (end of subject): empty match, emit `X`, stop The result is `XbXbXbX`: four replacements for a subject containing no `a` at all. Splitting on such a pattern shows the same shape from the other side — a piece between every character. ## Where empty matches come from They are easy to write by accident: - A `*` or `{0,n}` repeat on the whole pattern, or on its only mandatory-looking part. - An alternation with one empty branch, often left behind by an edit: `(foo|)`. - A pattern made entirely of optional parts: `[a-z]*[0-9]*`. - Anchors, word boundaries, lookahead and lookbehind, which are zero-width **by definition** — a pattern that is only assertions matches empty everywhere it holds. - A group whose contents became optional after a refactor, so a pattern that used to consume no longer must. ## Fixing it 1. **Require a character.** `[a-z]+` instead of `[a-z]*` is the usual answer, and it is the honest one: a replacement of nothing with something is rarely the intent. 2. **Make one element mandatory** where the pattern is a chain of optionals, so the whole cannot collapse to empty. 3. **Attach the assertion to real text.** If a lookahead is doing the work, give the pattern something to consume alongside it. 4. **Check before shipping a pattern that a user supplies.** A configurable extraction rule that can match empty turns every input into a per-character rewrite; rejecting a pattern with a zero-width match on an empty probe input is a cheap guard. ## Where conventions differ One detail is genuinely not uniform: whether an empty match is permitted at the position immediately following a non-empty match. Some conventions allow it, producing an extra empty match right after each real one; others suppress it. Leading and trailing pieces from splitting on such a pattern vary the same way. Do not build behaviour on either choice — if the count of results matters, use a pattern that cannot match empty, and the question disappears. The idea to carry away is that a match is a span, and a span of length zero is a perfectly valid one. Every construct that iterates matches has to answer "what stops this?", and the answer is always "the span advanced" — so a pattern that can decline to consume anything is a pattern whose global behaviour you have to reason about explicitly.

  • How do you rewrite `[a-z]*` so a global scan cannot produce an empty match?
    Require at least one repetition: `[a-z]+`. If the pattern is a chain of optional parts, make one of them mandatory instead, so the whole pattern cannot collapse to a zero-length span. The point is to remove the empty match, not to work around it in the calling loop.
  • What does splitting a string on a pattern that can match the empty string produce?
    A piece between every unit of the subject — effectively the individual characters — because an empty separator is found at each position. Whether empty leading and trailing pieces appear varies by convention, which is another reason to use a separator pattern that must consume something.

Think of the scan position as a ruler laid between characters rather than on them. An empty match is a mark made without moving the ruler, so the next reading is taken at exactly the same place.

saying these in an interview costs you the question

  • Believes a pattern containing `*` always consumes at least one character
  • Thinks an empty match means no match was found
  • Blames the replacement text for the extra separators
  • Assumes anchors and lookaheads consume the text they test
  • Works around it in the calling loop instead of forbidding the empty match