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

[Hans Åberg]

> On 3 May 2018, at 20:42, Tim Shen <timshen91@gmail.com> wrote:
> 
> ... \1 always matches and only matches what (a+) captured. With the
> input "aaaa", it's possible that (a+) captures "aa", and therefore \1
> matches the rest "aa". With the input "aaa", this is not possible.

>>> Implementing back-reference matching requires the matches to be
>>> available during the match, not after the match.
> 
>> Please illuminate this.
> 
> Following the example above, at the point when doing the "\1" state, the
> algorithm has to know what "(a+)" already matched. In your description, the
> first pass "merely record the DFA states", but it's not sufficient to tell
> what "\1" state(s) transitions to.

This might be implemented by inserting a final state state after (a+), as my implementation computes the matches when a final state appears.