[patch v2 3/4][libstdc++]: Reject impossible regex DFS starts early [PR126274]

[Tamar Christina]

Ah, I forgot to add https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88947 to the changelog.

I've modified the commit message locally.

Thanks,
Tamar

> -----Original Message-----
> From: Tamar Christina <tamar.christina@arm.com>
> Sent: 29 July 2026 15:35
> To: gcc-patches@gcc.gnu.org
> Cc: nd <nd@arm.com>; libstdc++@gcc.gnu.org; jwakely@redhat.com;
> tkaminsk@redhat.com; ppalka@redhat.com
> Subject: [patch v2 3/4][libstdc++]: Reject impossible regex DFS starts early
> [PR126274]
> 
> This patch add a conservative first-character precheck for DFS prefix search.
> regex_search and regex_token_iterator try the pattern at each possible input
> position. However for many regexp some of those positions can be rejected by
> looking through the front (without consuming state) before building th full
> DFS state which can be expensive to build only to realize that nothing matches.
> 
> The pre-check only returns false when every inspected path reaches a first
> consuming match state that rejects *_M_current, or reaches a dead end.  It
> returns true for unsupported or context-sensitive states such as backrefs
> and lookahead, so true means "run the normal executor" and false means
> "this start position cannot match".
> 
> This mainly helps IPv4-style scans where most positions are non-digits and
> only a few positions can start a match.
> 
> Benchmarks improvements compared to GCC previous patch in series:
> 
>  at -O2:
> 
>   email: +2.4%
>   URI: +3.6%
>   IPv4 +43.9%
> 
>  at -O3:
> 
>   email: +0.1%,
>   URI: +1.4%
>   IPv4: +42.7%
> 
> Bootstrapped Regtested on aarch64-none-linux-gnu,
> arm-none-linux-gnueabihf, x86_64-pc-linux-gnu
> -m32, -m64 and no issues.
> 
> Ok for master?
> 
> Thanks,
> Tamar
> 
> libstdc++-v3/ChangeLog:
> 
> 	PR libstdc++/126274
> 	* include/bits/regex_executor.h (_M_search_from_first): Avoid
> needless
> 	recursions.
> 	(_M_maybe_start_match): New.
> 	* include/bits/regex_executor.tcc (_M_maybe_start_match): New.
> 
> ---
> diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-
> v3/include/bits/regex_executor.h
> index
> a11410f0762441aeeaa32778c1d4676c92020e19..023f62e8a89d5f493228
> 64ab286d743f8f3cb7ed 100644
> --- a/libstdc++-v3/include/bits/regex_executor.h
> +++ b/libstdc++-v3/include/bits/regex_executor.h
> @@ -112,6 +112,28 @@ namespace __detail
>        _M_search_from_first()
>        {
>  	_M_current = _M_begin;
> +	// Fast reject for DFS prefix search.  regex_search and
> +	// regex_token_iterator try the pattern at each possible starting
> +	// position.  If the regex can only start with a digit, running the full
> +	// DFS executor at a space, letter, or punctuation character only builds
> +	// frames to discover the first match state rejects that character.
> +	//
> +	// Example: for the IPv4 pattern
> +	//   (?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}...
> +	// a current input character of 'x' cannot match any first consuming
> +	// state.  _M_maybe_start_match returns false and this starting
> position
> +	// is skipped.  At '2' it returns true, because at least one branch
> +	// might match, so the normal executor still decides the complete
> +	// result.
> +	//
> +	// This is intentionally disabled for backreferences.  Pruning the
> +	// search space for DFS reduces the number of frames we build and
> the
> +	// time to find an actual match.
> +	if (_M_search_mode == _Search_mode::_Dfs
> +	    && !_M_nfa._M_has_backref
> +	    && _M_current != _M_end
> +	    && !_M_maybe_start_match(_M_start, 0))
> +	  return false;
>  	return _M_main(_Match_mode::_Prefix);
>        }
> 
> diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-
> v3/include/bits/regex_executor.tcc
> index
> 6f885321a69d685d7085e89653a02177c8b251a6..b1a87da5afee4d854708
> 207906d119f4b5b151b4 100644
> --- a/libstdc++-v3/include/bits/regex_executor.tcc
> +++ b/libstdc++-v3/include/bits/regex_executor.tcc
> @@ -169,6 +169,101 @@ namespace __detail
>        return _M_has_sol;
>      }
> 
> +  // Return whether a prefix search at _M_current might still match after
> +  // looking only through the non-consuming front of the NFA.
> +  //
> +  // This is not a general implementation.  It is deliberately small and
> +  // conservative: when it reaches a construct whose first consuming
> character
> +  // is hard to know cheaply, it returns true and lets the normal executor run.
> +  // The important fast paths are the common negative cases.
> +  //
> +  // Examples:
> +  // * Pattern "[0-9]+" at input 'x': the first _S_opcode_match rejects 'x',
> +  //   so a full DFS search would only allocate/pop frames to fail.  Return
> +  //   false and let regex_search advance the starting position.
> +  //
> +  // * Pattern "[01]?[0-9]" at input '9': the optional [01] branch rejects,
> +  //   but the skip branch can consume '9'.  Return true and let DFS decide
> +  //   the full match.
> +  //
> +  // * Pattern "foo|bar" at input 'b': one alternative rejects, the other can
> +  //   start with 'b'.  Return true.
> +  template<typename _BiIter, typename _Alloc, typename _TraitsT>
> +    bool _Executor<_BiIter, _Alloc, _TraitsT>::
> +    _M_maybe_start_match(_StateIdT __i, size_t __depth)
> +    {
> +      // Depth is bounded by the NFA size so epsilon cycles cannot make the
> +      // precheck recurse forever.  Hitting the bound means "unknown", not
> +      // "no match", so stay conservative and run the real executor.  This is
> +      // important for patterns such as "(a*)*" where epsilon paths can cycle
> +      // before a consuming state is reached.
> +      if (__depth > _M_nfa.size())
> +	return true;
> +
> +      // An invalid edge is a real dead end for the explored path.
> +      if (__i == _S_invalid_state_id)
> +	return false;
> +
> +      const auto& __state = _M_nfa[__i];
> +      switch (__state._M_opcode())
> +	{
> +	case _S_opcode_match:
> +	  return __state._M_matches(*_M_current);
> +
> +	case _S_opcode_accept:
> +	  // Empty matches are possible, so the full executor must decide.
> +	  return true;
> +
> +	case _S_opcode_subexpr_begin:
> +	case _S_opcode_subexpr_end:
> +	case _S_opcode_dummy:
> +	  // Captures and dummy states do not consume input, so they cannot
> +	  // affect the first-character decision.  Continue along the only
> +	  // successor.
> +	  return _M_maybe_start_match(__state._M_next, __depth + 1);
> +
> +	case _S_opcode_line_begin_assertion:
> +	  // Assertions do not consume characters, but they can reject the
> +	  // current position.  For "^abc" at a non-begin position, there is no
> +	  // need to run DFS merely to discover that ^ fails.
> +	  return _M_at_begin()
> +		 && _M_maybe_start_match(__state._M_next, __depth + 1);
> +
> +	case _S_opcode_line_end_assertion:
> +	  // Same idea for "$": if the assertion does not hold here, this
> +	  // starting position cannot match via this path.
> +	  return _M_at_end()
> +		 && _M_maybe_start_match(__state._M_next, __depth + 1);
> +
> +	case _S_opcode_word_boundary:
> +	  // Word-boundary assertions are also checked before the first
> +	  // consuming state.  For "\bfoo" in the middle of "xfoo", this path
> +	  // rejects before testing 'f'.
> +	  return _M_word_boundary() == !__state._M_neg
> +		 && _M_maybe_start_match(__state._M_next, __depth + 1);
> +
> +	case _S_opcode_alternative:
> +	  // A branch might match if either arm can start with *_M_current.
> +	  // Example: "foo|bar" at 'b' rejects the "foo" arm but keeps the
> +	  // search because the "bar" arm is viable.
> +	  return _M_maybe_start_match(__state._M_alt, __depth + 1)
> +		 || _M_maybe_start_match(__state._M_next, __depth + 1);
> +
> +	case _S_opcode_repeat:
> +	  // Repeats can either enter the body or skip to the exit, so inspect
> +	  // both paths.  This matters for constructs such as "[01]?[0-9]": at
> +	  // '9' the optional first digit can be skipped, while at 'x' both
> +	  // paths reject.
> +	  return _M_maybe_start_match(__state._M_alt, __depth + 1)
> +		 || _M_maybe_start_match(__state._M_next, __depth + 1);
> +
> +	case _S_opcode_backref:
> +	case _S_opcode_subexpr_lookahead:
> +	default:
> +	  return true;
> +	}
> +    }
> +
>    // ------------------------------------------------------------
>    //
>    // BFS mode:
> 
> 
> --