Node.next contains epsilon transitions now, so it becomes @[epsilon_transition_idx, epsilon_transition_idx, matchable_node_idx, epsilon_transition_idx, matchable_node_idx, matchable_node_idx, ...]
It potentially makes better use of CPU cache, or it should not be worse at least, and code is cleaner.
There is a perf regression in regexes like "(\w|\w)(?<=\w+)foo" where prior to this change the lookaround would only get evaluated once (for the first alternation cond) and now it's evaluated for every alternation cond. We could reorder the epsilon transitions to be evaluated after the matchable node like @[matchable_node_idx, epsilon_transition_idx] after. However, regexes where this matter (containing unbounded lookarounds) already run in quadratic time, so meh.
Remove this. Make NFA a seq[Node] again.
Node.nextcontains epsilon transitions now, so it becomes@[epsilon_transition_idx, epsilon_transition_idx, matchable_node_idx, epsilon_transition_idx, matchable_node_idx, matchable_node_idx, ...]It potentially makes better use of CPU cache, or it should not be worse at least, and code is cleaner.
There is a perf regression in regexes like
"(\w|\w)(?<=\w+)foo"where prior to this change the lookaround would only get evaluated once (for the first alternation cond) and now it's evaluated for every alternation cond. We could reorder the epsilon transitions to be evaluated after the matchable node like@[matchable_node_idx, epsilon_transition_idx]after. However, regexes where this matter (containing unbounded lookarounds) already run in quadratic time, so meh.