w.r.t. [Bug libstdc++/85472] Regex match bug

[Tim Shen]

Sorry... I got confused between my accounts. But they are both me. :)

On Thu, May 3, 2018 at 3:27 PM Tim Shen <timshen@google.com> wrote:

> On Thu, May 3, 2018 at 3:05 PM Hans Åberg <haberg-1@telia.com> wrote:
> > It computes all final state matches. An idea was as a replacement for
> Flex, where the same match chooses the rule that comes first. So put in a
> final state at all points where matches are needed, perform some action to
> modify the NFA.
>
> > > The NFA/DFA-based algorithm wouldn't work, as they are guaranteed
> > > polynomial. On the other hand, regex with back-references is proved to
> > > be NP-complete.
>
> > That is for static algorithms. Here, partial computation is fed back and
> modifying the NFA, branching into multiple ones.
>
> I'm not yet convinced that there is efficient way to implement the NFA
> modification approach, not efficient enough to fix PR 85472 without
> regressing the normal cases.
>
> Even in the DFS case, if I want to walk back the path to generate captures
> once hit a "final state" or "back-reference state", it still looks
> expensive to me. The reverse matching takes O(s.size()) amount of time, and
> I only want to do it once.
>
> It's indeed O(s.size()) if no back-references are included, we will do it
> for once at the end (as you suggested). It's also fine (from efficiency's
> perspective) if we leave the bug as it is, since all captures updates are
> amortized in _M_handle_subexpr_begin and _M_handle_subexpr_end.
>
> --
> Regards,
> Tim Shen
>