Why a Short Pattern Takes Thirty Seconds on One Line
Last timeCollapsing It to One State
Where the exponential comes from when an engine that backtracks meets an ambiguous repetition, counted attempt by attempt, with the three shapes that cause it and the three defences that work.
A validating pattern is usually written in a minute, tried against three
strings that should pass and two that should not, and then trusted. Its cost is
assumed to be roughly the length of the input, because that is what every other
piece of string handling costs and because the matching looked instant on the
examples. Then a line arrives that is forty characters long, the same pattern
spends about half a minute of processor time on it, and every worker in the
service is sitting inside the same function.
Nothing is broken. The engine is doing precisely what it was built to do, and
the number of steps it takes can be worked out in advance, on paper, from the
shape of the pattern and the length of one run of characters in the input. Here
is that arithmetic, because with the count written down the rules that are
otherwise folklore stop being folklore.
The one change that does it
Take the small pattern used throughout, which matches a literal a, then any
number of b or c characters, then a literal d, written .
Given an input it accepts, there is exactly one way for it to accept it,
because at each character inside the repetition only one branch of the choice
can take the character in hand: b goes left, c goes right, and nothing goes to
both.
Now make the two branches identical, giving . What the
pattern describes has barely changed, since both describe a run of one
character followed by a d. What has changed is the number of ways that
description can be satisfied, because every a can now be taken by either branch
and both choices leave the engine in the same position with the same work left
to do. The pattern has become ambiguous, and an engine that explores routes one
at a time pays for every route.
The input used throughout is a run of twenty five a characters with no d at the
end of it.
The engine that commits
There are two ways to run the machine a pattern compiles to. One keeps the set
of states the machine could be in and advances all of them a character at a
time, never reading a character twice, at a cost bounded by the number of
states times the length of the input. The other commits to one branch at each
choice, carries on, and when the rest of the pattern fails it undoes the last
choice and takes the next option.
Almost every engine in a standard library is the second kind. Committing to a
route is what lets an engine report where each captured group began and ended,
honour the difference between a greedy and a lazy repetition, and offer
features no finite machine can carry out at all. The price is that undoing a
choice means reading the same characters again, and how often that happens is
what the arithmetic below counts.
The lesson stops here
9 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents