<regex>: Process disjunctions non-recursively
#5745
Merged
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Towards #997 and #1528.
We have to handle disjunctions (represented by
_N_ifnodes) differently depending on longest mode: When_Longestis true, we have to evaluate all alternatives during unwinding no matter if they matched successfully or not. Otherwise, we always may (and usually must) stop evaluating alternatives after one succeeded. The former is implemented by the case_Disjunction_eval_alt_always, the latter by_Disjunction_eval_alt_on_failure. We can implement the latter case by falling through to the former.During unwinding,
_Framealready holds the correct values to evaluate further alternatives in the disjunctions except for the NFA node it points to. So we can just update the node pointer and "push"_Frameon the stack again by incrementing_Frames_count.In longest mode,
_Match_pat()now returns false when matching the last evaluated alternative failed, even if some alternative evaluated earlier matched successfully._Matcher3::_Match()can deal with this behavior change by checking the member_Matchedas well, which is set to true in longest mode when the first successful match was found. (Note that in longest mode, the return value of_Match_pat()mostly doesn't matter when possible trajectories are evaluated by the matcher. The only exceptions are the_Match_pat(_Node->_Next)calls found in_Do_rep0(), which handles simple loops. But the return values of these calls are unaffected by this change in the evaluation of_N_ifnodes because simple loops are guaranteed to be branchless.)