[Patch] Reimplment regex matcher using DFS

[Stephen M. Webb]

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.

> At last, two bug reports(libstdc++/53622 and libstdc++/57173) said
> that there're regex grouping problems. It's relatively simple fix it
> in the DFS approach, and I added them to the testsuite. Shall I write
> PR in the ChangeLog? What does PR stand for?

PR == problem report.  It will never hurt to put PR numbers in the ChangeLog.  At the very least they should go in the
VCS commit message.

> 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.

-- 
Stephen M. Webb  <stephen.webb@bregmasoft.ca>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 899 bytes
Desc: OpenPGP digital signature
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20130723/7a3dc3df/attachment.sig>