`<regex>`: Avoid generating no-op NFA nodes

[muellerj2]

The NFA nodes of type _N_nop, _N_group and _N_end_group do not result in any changes to the match state in the matcher. However, processing them still requires some time. Going by the benchmarks in #5939, it seems about 2.5 ns are spent on my machine whenever when such a node is encountered by the matcher; see, e.g., the 37 % (relative) / 470 ns (absolute) increase in running time when matching the pattern (?:a)* to 100 a's compared to a*.

Note that these NFA nodes do usually serve some purpose during regex parsing, so resolving this issue requires some careful changes to the parser logic.

[muellerj2]

I guess nodes of type _N_endif count as well, but I suspect that one is even more intricate to remove than the other three no-ops.

[muellerj2]

After recent changes, only one type of no-op NFA node is still generated by the parser: _N_endif. But this is a far more complex affair than all the other no-op nodes.

First, it unfortunately turns out that this node is actually no longer a complete no-op in the matcher since my changes in #5456: _Find_first_inner_capture_group() uses such nodes to identify the end of a branch in the NFA.

Even so, I think we could still remove it and just null the _Endif member in _Node_if, because at first glance this does not seem to break the logic in _Find_first_inner_capture_group(). But it would negatively impact the performance of this function for old matchers (but on the other hand there would no longer be any _N_endif nodes for _Match_pat() to process, improving the performance there).

Second, this removal leads to major complications in the parser: The _N_endif node is a nice trick there to ensure that there is always only a single node the parser must keep track of for the end of a disjunction. This is no longer true if the node is omitted: The parser must keep track of all the last nodes in each individual branch so that it can connect them all to their successor node.

The parser also assumes in _Insert_node() that an NFA node has a single predecessor. This wasn't true before as well, but the generation of the _N_endif node made sure the violation of this assumption was isolated to these _N_endif nodes. If _N_endif is removed during parsing, all uses of _Insert_node() must be audited and replaced by an alternative logic that can handle multiple predecessors.

But we could also avoid major rework in the parser by adding a subsequent pass to the parser that removes these _N_endif nodes. This change is much simpler in that the parsing logic wouldn't really have to be touched at all, but it has the downside that the parser must keep allocating the _N_endif nodes at least temporarily.

So to make a long story short: All this seems to be a lot of effort for very limited gain. Therefore, I will not pursue this change any time soon. If there will ever be a vNext, that might be an appropriate opportunity to revisit this issue, as this will allow us get rid of one complication: We can drop _Find_first_inner_capture_group() from the matcher by making the parser compute its outputs already.

[muellerj2]

Even so, I think we could still remove it and just null the _Endif member in _Node_if, because at first glance this does not seem to break the logic in _Find_first_inner_capture_group().

I changed my mind here: Removing the _N_Endif node does break the algorithm in _Find_first_inner_capture_group(). It doesn't crash, but it might find an incorrect first capturing group, which would introduce a bug similar to #5365.

This means that the removal of the _N_endif nodes is necessarily vNext, at least for ECMAScript regexes.