https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #22 from Hans Åberg ---
(In reply to Tim Shen from comment #16)
> ...I meant to observe whether the example triggers a O(k^2) behavior. It
> should be less than quadratic. ...
> Here is the updated example, to re-arrange the
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #21 from Hans Åberg ---
(In reply to Tim Shen from comment #20)
> (In reply to Hans Åberg from comment #18)
> > (In reply to Tim Shen from comment #14)
> > > I have a C++ test case for this:
> >
> > I get segmentation fault on the
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #20 from Tim Shen ---
(In reply to Hans Åberg from comment #18)
> (In reply to Tim Shen from comment #14)
> > I have a C++ test case for this:
>
> I get segmentation fault on the regex_match line with g++ 7.3.0.
On Linux I set
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #19 from Hans Åberg ---
(In reply to Tim Shen from comment #16)
> I set (kStart, kEnd) to be (1000, 2000), (1000, 3000), ..., (1000, 9000) to
> see how the time grows. ...
> Here are my numbers for end ranging 2000 to 9000, in ms:
>
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #18 from Hans Åberg ---
(In reply to Tim Shen from comment #14)
> I have a C++ test case for this:
I get segmentation fault on the regex_match line with g++ 7.3.0.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #17 from Hans Åberg ---
(In reply to Tim Shen from comment #16)
> (In reply to Hans Åberg from comment #15)
> > (In reply to Tim Shen from comment #14)
> > > How fast does your prototype run on the following example?
> > >
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #16 from Tim Shen ---
(In reply to Hans Åberg from comment #15)
> (In reply to Tim Shen from comment #14)
> > How fast does your prototype run on the following example?
> > ((10)|(11)|(12)|...|(98)|(99))* matching
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #15 from Hans Åberg ---
(In reply to Tim Shen from comment #14)
> How fast does your prototype run on the following example?
> ((10)|(11)|(12)|...|(98)|(99))* matching "10111213141516...9899"
> how about this:
>
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #14 from Tim Shen ---
How fast does your prototype run on the following example?
((10)|(11)|(12)|...|(98)|(99))* matching "10111213141516...9899"
how about this:
((100)|(101)|(102)|...|(998)|(999))* matching "100101102...998999"
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #13 from Hans Åberg ---
(In reply to Tim Shen from comment #11)
> If you think it's time and space efficiently doable, maybe you can develop a
> prototype first.
I put action number lists on the NFA transitions (no markup of the
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #12 from Hans Åberg ---
(In reply to Tim Shen from comment #11)
> > The problem is that #4 has an earlier capture, making it impossible to see
> > that it is left undefined later.
>
> I wouldn't say it's impossible. libc++
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #11 from Tim Shen ---
> The problem is that #4 has an earlier capture, making it impossible to see
> that it is left undefined later.
I wouldn't say it's impossible. libc++ implements it correctly at a cost.
Specifically, see
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #10 from Hans Åberg ---
(In reply to Tim Shen from comment #9)
> Ah with the example it's clear, thanks!
You are welcome.
> > The last line gives for #1 the sub-string "z" , and for #2 "aacbbbcac".
>
> This is not what ECMAScript
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #9 from Tim Shen ---
Ah with the example it's clear, thanks!
> The last line gives for #1 the sub-string "z" , and for #2 "aacbbbcac".
This is not what ECMAScript produces either. for capture #2, ECMAScriptn
produces "ac", the last
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #8 from Hans Åberg ---
(In reply to Tim Shen from comment #5)
> I'm not following the meaning of "action number" and "the partial reverse
> NFA is recorded".
>
> How many actions numbers are recorded? for regex_match(s, regex(re)),
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #7 from Hans Åberg ---
(In reply to Tim Shen from comment #5)
> (In reply to Hans Åberg from comment #4)
> > I wrote an NFA/DFA that computes all matches, it seems, in an efficient
> > manner: Action numbers are marked on the states
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #6 from Hans Åberg ---
(In reply to Tim Shen from comment #5)
> (In reply to Hans Åberg from comment #4)
> > I wrote an NFA/DFA that computes all matches, it seems, in an efficient
> > manner: Action numbers are marked on the states
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #5 from Tim Shen ---
(In reply to Hans Åberg from comment #4)
> (In reply to Tim Shen from comment #1)
> > I know exactly how libc++ produces this result. It creates an empty
> > match_result during each repetition ("*" operator).
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #4 from Hans Åberg ---
(In reply to Tim Shen from comment #1)
> I know exactly how libc++ produces this result. It creates an empty
> match_result during each repetition ("*" operator). It's less confusing but
> much slower.
I wrote
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #3 from Tim Shen ---
Conclusively, yes it is a bug, but it is hard to fix without regressing normal
case performance.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #2 from Tim Shen ---
My bad, I didn't realize that "(z)((a+)?(b+)?(c))*" is exactly an example
described in ECMAScript third edition 15.10.2.5. Therefore libstdc++ is not
conforming.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
Tim Shen changed:
What|Removed |Added
CC||timshen at gcc dot gnu.org
--- Comment #1
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
Jonathan Wakely changed:
What|Removed |Added
Status|UNCONFIRMED |NEW
Last reconfirmed|
23 matches
Mail list logo
