investigate skipping reverse NFA compilation if regex is anchored

[BurntSushi]

If the regex is anchored and a match is found in the forwards direction, then the reverse NFA is never needed to find the start position because the start position must necessarily be 0 as a result of the anchor.

See this comment for a little more context: #1095 (comment)

[BurntSushi]

If someone wanted to work on this, it would be a pretty cool optimization to have.

I think the right way to do this is to add a new implementation of the internal Strategy trait for the meta regex engine:

regex/regex-automata/src/meta/strategy.rs

Lines 40 to 41 in 2cbd342

	pub(super) trait Strategy:
	Debug + Send + Sync + RefUnwindSafe + UnwindSafe + 'static

And then create an instance of that implementation here:

regex/regex-automata/src/meta/strategy.rs

Line 104 in 2cbd342

None

It's important to avoid building a Core, since that will compile a reverse NFA. You'll want to short circuit a build what is essentially a near copy of Core, but a simpler version of it that never builds a reverse NFA. I suspect there may be a fair bit of code duplication. I'm not quite sure if it makes sense to try and reduce that duplication since I imagine it could complicate things.

The other unfortunate thing is that you won't be able to reuse, for example, the HybridEngine wrapper:

regex/regex-automata/src/meta/wrappers.rs

Lines 555 to 559 in 2cbd342

	#[derive(Debug)]
	pub(crate) struct HybridEngine(
	#[cfg(feature = "hybrid")] hybrid::regex::Regex,
	#[cfg(not(feature = "hybrid"))] (),
	);

Since that wrapper unconditionally builds a reverse lazy DFA from a reverse NFA. Indeed, its constructor requires a reverse NFA. So we'll need a new wrapper for that (and the same applies to the fully compiled DFA wrapper too).