<regex>: Avoid generating unnecessary single-branch _N_if nodes (#5539)

muellerj2 · web-flow · commit 1b1f5b0b402e · 2025-05-28T15:23:26.000-07:00
diff --git a/stl/inc/regex b/stl/inc/regex
@@ -4125,6 +4125,9 @@ _BidIt _Matcher2<_BidIt, _Elem, _RxTraits, _It, _Alloc>::_Skip(_BidIt _First_arg
                 // GH-5452: If this node has two or more branches,
                 // examining all these branches has quadratic worst-case complexity.
                 // Thus, we only continue if this node has a single branch only.
+                // TRANSITION, ABI: After GH-5539, the parser no longer generates single-branch _N_if nodes.
+                // But we have to retain this special handling to avoid performance regression
+                // when an old parser gets mixed with a new matcher.
                 _Node_if* _Node = static_cast<_Node_if*>(_Nx);
 
                 if (_Node->_Child) {
@@ -4903,15 +4906,17 @@ void _Parser2<_FwdIt, _Elem, _RxTraits>::_Disjunction() { // check for valid dis
         _Nfa._End_group(_Pos3);
     }
 
-    _Node_base* _Pos2 = _Nfa._Begin_if(_Pos1);
-    while (_Mchar == _Meta_bar) { // append terms as long as we keep finding | characters
-        _Next();
-        if (!_Alternative()) { // zero-length trailing alternative
-            _Node_base* _Pos3 = _Nfa._Begin_group();
-            _Nfa._End_group(_Pos3);
-        }
+    if (_Mchar == _Meta_bar) {
+        _Node_base* _Pos2 = _Nfa._Begin_if(_Pos1);
+        do { // append terms as long as we keep finding | characters
+            _Next();
+            if (!_Alternative()) { // zero-length trailing alternative
+                _Node_base* _Pos3 = _Nfa._Begin_group();
+                _Nfa._End_group(_Pos3);
+            }
 
-        _Nfa._Else_if(_Pos1, _Pos2);
+            _Nfa._Else_if(_Pos1, _Pos2);
+        } while (_Mchar == _Meta_bar);
     }
 }
 
@@ -4979,17 +4984,26 @@ void _Parser2<_FwdIt, _Elem, _RxTraits>::_Calculate_loop_simplicity(
                 }
             }
             break;
+
+        case _N_group:
+        case _N_capture:
+            // TRANSITION, requires more research to decide on the subset of loops that we can make simple:
+            // - Simple mode can square the running time when matching a regex to an input string in the current matcher
+            // - The optimal subset of simple loops for a non-recursive rewrite of the matcher aren't clear yet
+            if (_Outer_rep) {
+                _Outer_rep->_Simple_loop = 0;
+            }
+            break;
+
         case _N_none:
         case _N_nop:
         case _N_bol:
         case _N_eol:
         case _N_wbound:
         case _N_dot:
         case _N_str:
-        case _N_group:
         case _N_end_group:
         case _N_end_assert:
-        case _N_capture:
         case _N_end_capture:
         case _N_back:
         case _N_endif:
