Lessons · Regex · a quantifier inside a quantifier
A quantifier inside a quantifier
(a+)+b lets the same characters be divided between the repetitions in many ways, and on a string that does not match, the engine tries all of them.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
This is a denial-of-service bug, not a slow line. The work doubles for every character added, so twenty is fine and thirty is a hung process.
How to think about it
Look for a quantified group whose contents are themselves quantified. Nearly every one has a flat equivalent that matches exactly the same strings.
Worked example
re.search(r'(a+)+b', 'aaab').group()It matches fine; the trouble is only ever on the strings that do NOT.
re.search(r'a+b', 'aaab').group()The flat version, same answer.
re.search(r'a+b', 'aaa')And this one gives up immediately, where the nested one would not.
Your turn
Write the flat version of (a+)+b.
ab
Test a pattern against real text
The trap
It passes every test you write, because the tests are strings that match. The failure lives entirely in the ones that do not.