[Patch] Reimplment regex matcher using DFS

[Jonathan Wakely]

On 23 July 2013 15:06, Stephen M. Webb wrote:
> On 07/23/2013 09:07 AM, Tim Shen wrote:
>> This is the most exciting patch from me so far! XD
>>
>> Here I temporarily shadow the Thompson NFA matcher[1](original
>> _Grep_matcher), and use the Depth-First Search(DFS, or backtracking)
>> approach instead.
>>
>> Yes, DFS is *exponentially slow* :( However we need it, because when
>> encountering the feature "back-reference", like "\1" in "([A-Z])\1*",
>> DFS is the best choice[1].
>
> One of the philosophies behind C++ is the "pay only for what you use" concept.  Always using DFS is a steep price to pay
> for something rarely used (ie. back references).  In fact, some of the supported regex grammars (extended, awk, and
> egrep in particular) do not allow backreferences, although the boost implementation provides this as a "compatible
> extension".  Would it be better to prescan the regex to determine which matcher to build?
>
> Also, in the absence of back references, a DFA can be considerably faster than an NFA or a DFS.  We should consider
> constructing a DFA if a prescan says there are no back references and the regex_constants::optimize flag is set.

Yes, I believe GNU grep uses a similar NFA/DFA hybrid approach based
on whether back-references are actually used.

>> By the way, probably I shouldn't add too much comment in the code(what
>> if it's changed for reasons?). At the final section of my GSoC
>> participation, I'll spend all time adding documents and comments.
>
> Me, I would prefer more comment in the code and the comments be maintained with the code, because (a) you could get hit
> by an asteroid and be unable to finish you work, and regex implementation is complex enough that every little bit helps
> when someone is trying to understand what was written, and (2) you could run out of time.  I don't take the lack of
> comments and documentation throughout the library as an exemplar.  Others may have differing opinions.

Comments in the code are welcome, most of the library has one obvious
way to implement it, whereas regex engines are complex and there are
many implementation and optimisation choices which are non-obvious.