The Backtracker's challenge: greedy, lazy and possessive

In the morning there's a black envelope wedged in the office door. Inside is a single card. The director holds it up to the light, then sets it down on the desk. "So he finally says hello. With a signature instead of a face."

^(a|aa)+$

이 패턴은 정답을 맞힌다. 그런데 왜 이렇게 느린가?
답은 패턴으로 보내라.
                                        (a+)+$

The card is in Korean. It reads: "This pattern gets the right answer. So why is it so slow? Send your answer as a pattern." Below it, the signature.

"You can only solve this if you know how a regex engine thinks," the director says. "Today we look inside the engine's head."

8-1. The engine tries from the front and backs up when it gets stuck (10 min)

A regex engine tries to fit the pattern onto the string one piece at a time, from left to right. When something doesn't fit, it doesn't give up right away. It undoes the choice it just made and tries another path. That's called backtracking.

In Lesson 3 you saw that quantifiers, by default, "eat as much as they can" (they're greedy). Here's what that does when you pull tags out of HTML.

html = "<b>bold</b> and <i>it</i>"
re.findall(r"<.+>", html)   # ['<b>bold</b> and <i>it</i>']

Instead of four tags, the whole line came back as one. Follow what the engine did:

1. < matches the first <.
2. .+ is greedy, so it eats everything to the end of the line.
3. Now the pattern's > has to match, but there are no characters left. Failure.
4. .+ gives back characters one at a time and tries again. The moment it gives back the final >, the match succeeds.

The result runs "from the outermost < to the very last >". The engine isn't wrong; the pattern is.

8-2. Lazy quantifiers: *? +? ?? {m,n}? (8 min)

Put a ? after a quantifier and it becomes a lazy quantifier that eats as little as possible. It starts with the minimum and only eats one more character when the rest of the pattern doesn't fit.

re.findall(r"<.+?>", html)          # ['<b>', '</b>', '<i>', '</i>']
re.findall(r"a+?", "aaa")           # ['a', 'a', 'a']
re.findall(r"a??", "a")             # ['', 'a', '']
re.search(r"\d{2,4}?", "12345").group()   # '12'

A lazy quantifier changes "where it stops". That makes it handy for grabbing short things with a clear end marker, like tags.

8-3. Same problem, three answers (4 min)

Here are the ways to pull out tags side by side.

<[^>]+> uses the negated class from Lesson 2 and only eats "characters that aren't >". It almost never has to back up, so it's the fastest, and its meaning is the clearest. As the director puts it: "Precise beats lazy."

8-4. Answering the challenge: too many paths to back up through (8 min)

Now look at the pattern on the card, ^(a|aa)+$. It finds "a whole string made of one or more a's". It means the same as ^a+$.

bool(re.fullmatch(r"^(a|aa)+$", "aaaa"))   # True
bool(re.fullmatch(r"^a+$", "aaaa"))        # True

The trouble starts when it meets a string that doesn't match. If there's a b at the end, as in aaaa…ab, the engine tries every way of splitting the a's into a and aa, one by one, before it admits failure. The number of ways to split them explodes as the a's get longer.

Here are times measured on the agency's computer (Python 3.14).

Every four extra a's make it about seven times slower. At that rate, 40 a's would take well over 10 seconds. A repeat with overlapping choices like this is the classic shape that makes backtracking explode. A repeat inside a repeat, like (a+)+, is the same kind of thing.

8-5. Quantifiers that never give back: *+ ++ ?+ {m,n}+ (6 min)

Since Python 3.11, putting a + after a quantifier makes it a possessive quantifier. Once it has eaten characters, it never gives them back, even if the rest of the pattern fails. It removes the paths to back up through altogether.

re.fullmatch(r"a*a", "aaa")    # <re.Match object; span=(0, 3), match='aaa'>
re.fullmatch(r"a*+a", "aaa")   # None

a*+a never matches any string. a*+ takes every a and won't give any back, so there's nothing left for the final a to match. Turned around, that same property lets us fix the card's pattern.

re.search(r"^(?:a|aa)++$", "a" * 28 + "b")   # None (finishes instantly)

++ makes the group's repeat possessive, so on failure it gives up at once instead of trying other ways to split.

8-6. Groups that give nothing back: (?>...) (4 min)

The atomic group (?>...) is also available since 3.11. Once the inside of the group has matched, that result is locked in as a whole, and the engine never backs up into it. A possessive quantifier is really shorthand for an atomic group: a++ is the same as (?>a+).

re.fullmatch(r"(?>a+)b", "aab")   # <re.Match object; span=(0, 3), match='aab'>
re.fullmatch(r"(?>a+)a", "aaa")   # None

Cracking the case (10 min)

You draft the reply with the director. There are three ways to fix a slow pattern.

1. Rewrite it so nothing overlaps. Make sure the same characters can't be split in more than one way: ^a+$ instead of ^(a|aa)+$.
2. Remove the paths to back up through. A possessive quantifier, ^(?:a|aa)++$, or an atomic group, ^(?>(?:a|aa)+)$.
3. Block it from the outside. Limit the input length, and run patterns from other people only somewhere with a time limit. This lab runs patterns in a separate process and stops them after 0.3 seconds; that's exactly this kind of safeguard. (The third-party regex package has a timeout argument.)

import time
text = "a" * 40 + "b"
start = time.perf_counter()
print(re.search(r"^a+$", text))             # None
print(time.perf_counter() - start < 0.01)   # True

The new detective writes ^a+$ on the back of the card and slips it into the envelope. The director nods. "Short, readable, fast. A good reply."

Exercises

1. Predict the result of re.findall(r'".+"', 'say "hi" and "yo"'), then fix it to grab one quoted string at a time in two ways (a lazy quantifier and a negated class).
2. Explain why (\d+)+$ is a dangerous shape, and write a safe pattern that means the same thing.
3. What do a{2,4}? and a{2,4}+ each return when you run them with findall on "aaaaa"? Check in the Evidence lab.