Regular Expressions: The Greedy Dot, Missing Anchors and Nested Repetition

A regular expression is tested against the case it was written for, it matches, and it goes into production. What it does with the second case is a separate question, and the answer is often that it matches that one too – just not the part anyone intended.

The three mistakes below are the ones that survive review, because none of them fails. They return something, the something looks plausible in a spot check, and the difference shows up as data that is subtly wrong rather than as an error.

The Dot Is Greedy and the Dot Is Not a Character

.* takes everything it can and only gives back what it must. In a line with two links, href="(.*)" starts at the first href, runs to the end of the line, then backs up to the last quote it can find – and returns one match containing both links and the markup between them.

Two things fix it. The lazy quantifier .*? stops at the first quote that lets the rest of the pattern succeed. The negated class [^"]* cannot cross a quote at all, which says the same thing without any backtracking – and is the version worth writing, because it states the constraint instead of relying on how the engine unwinds.

A Negated Class Includes the Line Break

The dot does not match a newline unless the s flag is set. A negated character class does – [^&] means anything that is not an ampersand, and a line break is not an ampersand.

text     utm_source=newsletter
         utm_medium=email

^utm_([a-z_]+)=([^&]+)$      with the m flag: 2 matches
^utm_([a-z_]+)=([^&]+)       without it: 1 match spanning both lines
^utm_([a-z_]+)=([^&\s]+)     the fix: whitespace excluded as well

This is the failure that looks like a data problem. A pattern extracting parameters from a multi-line input returns one value that happens to contain everything after it, the value is written to a field, and the field looks like a very long campaign name rather than like a bug.

Anchors Say Where, Not Whether

Without anchors a pattern matches anywhere in the input, which is usually what is wanted for extraction and almost never what is wanted for validation. A check that a field contains only digits with [0-9]+ passes for abc123def, because the pattern was never asked about the rest.

Validation needs ^ and $ on both ends, and it needs to know what those mean in the flavour being used: without the multiline flag they mark the start and end of the whole input, with it every line. Which of the two is correct depends entirely on whether the input is one value or a list of them, and that is a question worth answering explicitly rather than by whichever default the library came with.

Nested Repetition Is a Different Class of Problem

The three mistakes above return the wrong answer. This one returns no answer at all. When a repeated group contains something that is itself repeatable – (a+)+, (\s*\w+)*, (.*,)* – the engine has exponentially many ways to divide the input among the repetitions, and it tries all of them before concluding that there is no match.

The dangerous property is that these patterns are fast on every input that matches. The blow-up only happens on inputs that fail, which means a validation pattern behaves perfectly for years and then meets one malformed submission and occupies a worker until it is killed.

The rule that avoids it is mechanical: no quantifier directly around a group whose contents are themselves quantified. Where that is unavoidable, a negated class usually expresses the same intent – [^,]+, instead of (.*,) – and removes the ambiguity that the backtracking was exploring.

What to Test Before Trusting a Pattern

Three inputs answer most of it. The case it was written for, to confirm it matches. A case with two occurrences, which is where greediness shows itself and a single-example test never will. And a case that must not match, which is where anchors and nested repetition both reveal themselves – one by matching anyway, the other by not finishing.

The third is the one that gets skipped, and it is the one that catches both of the problems that cannot be seen by reading the pattern. A test suite for a regular expression is three lines long, and it is the difference between an expression that works and an expression that has not yet been contradicted.