Infer if backtracking is needed

[nielsenko]

Problem to Solve

The PathTrie (and hence Router) supports backtracking. You can override it per lookup with the optional backtrack flag, which default true.

But if back-tracking is ever needed is really a function of the registered paths/routes.

The user can choose wrong without knowing - either paying for backtracking when not needed, or fail lookup when backtracking would have found a match.

Proposal

Let PathTrie calculate a _needsBacktracking as paths are added, removed or sub-tries injected.
Use this in place of backtracking.

Use Case

Simplifies the interface for the enduser without leaving performance on the table.

Alternatives

Live with current situation.

Additional context

No response

How experienced are you with this library?

Expert - Experienced and comfortable with using this library in complex projects

Are you interested in working on a PR for this?

• I want to work on this

[nielsenko]

Due to the way we attach works, such as allowing sub-tries to be modified after the attach, and to be attached at multiple places, this is tricky to get right (see review of #375). Also, given the better-safe-than-sorry semantics needed the optimization is probably rarely hit in practice. A user who knows what they are doing can still avoid backtracking by passing the flag explicitly.

This is just to say that this may not be worth the effort, unless an elegant idea emerge (I already considered union_find).