3 ms·
You don't need to throw out your favorite regex features—backreferences aren't stupid, they're useful and usually harmless! Rather, a good regex engine should s
by pcwalton 11y ago
You don't need to throw out your favorite regex features—backreferences aren't stupid, they're useful and usually harmless! Rather, a good regex engine should start with recursive backtracking (ideally JIT'd) and fall back to the Thompson NFA if the regex supports it and the recursive backtracking approach is taking too long. Think of it like the adaptive sorting algorithms that switch between insertion sort and quicksort based on the size of the collection.
This approach gives you the best of both worlds: speedy operation in the common cases in which recursive backtracking beats the Thompson NFA, all the regex features you know and love, and worst case polynomial running time for regexes that the Thompson NFA supports.
I don't think it would have prevented this bug, though, because I don't think the Thompson NFA supports the recursive backreference thing that this regex uses.
- mwcampbell 11y agoDo you know if any major regex implementations use the adaptive approach you're suggesting?
- pcwalton 11y agoI don't know of any that can actually switch during regex execution, but TRE at least will choose Thompson NFA if it can and fall back to recursive backtracking if backreferences are used.