Re: [Patch] Reimplment regex matcher using DFS

2013-07-24 Thread Tim Shen
On Thu, Jul 25, 2013 at 12:13 AM, Paolo Carlini wrote: > Thanks. I added a few words to 57513 too. It would be nice to figure out > which specific change fixed the link-time issue (provided a definition for > the default constructor?) Comment added. -- Tim Shen

Re: [Patch] Reimplment regex matcher using DFS

2013-07-24 Thread Paolo Carlini
On 07/24/2013 05:18 PM, Jonathan Wakely wrote: Should I register a new bugzilla account to comment on these two bugs(53622 and 57173), or any other one will do this? I've added a comment to the bugs. With svn commit rights you should be able to receive email at @gcc.gnu.org and if you use that a

Re: [Patch] Reimplment regex matcher using DFS

2013-07-24 Thread Jonathan Wakely
On 24 July 2013 15:50, Tim Shen wrote: > > Committed. Thanks! > Should I register a new bugzilla account to comment on these two > bugs(53622 and 57173), or any other one will do this? I've added a comment to the bugs. With svn commit rights you should be able to receive email at @gcc.gnu.org a

Re: [Patch] Reimplment regex matcher using DFS

2013-07-24 Thread Paolo Carlini
On 07/24/2013 04:50 PM, Tim Shen wrote: On Wed, Jul 24, 2013 at 5:18 PM, Paolo Carlini wrote: Then we should also add something (by hand, unfortunately, as I explained) to the audit trails of those bugs, because we want the original submitters to double check the fixes with their own code, get

Re: [Patch] Reimplment regex matcher using DFS

2013-07-24 Thread Tim Shen
On Wed, Jul 24, 2013 at 5:18 PM, Paolo Carlini wrote: > Then we should also add something (by hand, unfortunately, as I explained) > to the audit trails of those bugs, because we want the original submitters > to double check the fixes with their own code, get as much feedback as > possible while

Re: [Patch] Reimplment regex matcher using DFS

2013-07-24 Thread Paolo Carlini
On 07/23/2013 05:31 PM, Tim Shen wrote: Revised version, with _M_dfs_* moved to the class definition, PR testcases, and some comments on _M_dfs(). I nobody has further comments, I think this is Ok to go in now. Let's make sure we don't forget the various comments about optimization, pre-scannin

Re: [Patch] Reimplment regex matcher using DFS

2013-07-23 Thread Tim Shen
Revised version, with _M_dfs_* moved to the class definition, PR testcases, and some comments on _M_dfs(). Thanks. -- Tim Shen dfs-matcher.patch Description: Binary data

Re: [Patch] Reimplment regex matcher using DFS

2013-07-23 Thread Paolo Carlini
Hi, >Is this naive or not? I don't know. For sure we don't want inline code in *.tcc headers. Paolo

Re: [Patch] Reimplment regex matcher using DFS

2013-07-23 Thread Tim Shen
On Tue, Jul 23, 2013 at 9:42 PM, Paolo Carlini wrote: > This doesn't make much sense to me: if the functions are inside a *.tcc file > why are marked inline? First blush seem indeed good candidates for inline, > but then should be in the *.h My view is like this : When I put something into the cl

Re: [Patch] Reimplment regex matcher using DFS

2013-07-23 Thread Paolo Carlini
.. not that, in general, *all* the testcases coming from a bug report in Bugzilla, should either be named after the bug # or have the information in a comment inside (or both, as I said already) Paolo.

Re: [Patch] Reimplment regex matcher using DFS

2013-07-23 Thread Paolo Carlini
On 07/23/2013 03:07 PM, Tim Shen wrote: + inline + bool _Grep_matcher:: + _M_dfs_match() + { return _M_dfs(_M_nfa->_M_start()); } + + inline + bool _Grep_matcher:: + _M_dfs_search_from_first() + { return _M_dfs(_M_nfa->_M_start()); } This doesn't make much sense to me: if the functions ar

Re: [Patch] Reimplment regex matcher using DFS

2013-07-23 Thread Paolo Carlini
Hi, On 07/23/2013 03:07 PM, Tim Shen wrote: 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? P

[Patch] Reimplment regex matcher using DFS

2013-07-23 Thread Tim Shen
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 "b