Prefilter based on http.path

[Dr-Emann]

I've been thinking of a way to speed things up for huge numbers of routes, by finding required prefixes for http.path for each expression, and using them to quickly narrow down the possible set of expressions to try, hopefully by a lot.

e.g. the following expressions:

[1]: net.dst.port == 9000
[2]: http.path ^= "/abc"
[3]: http.path ~ "^/foobar/(.*)$" && net.dst.port < 8000
[4]: http.path ~ "^/abc123" || http.path == "/123/456"
[5]: http.path ~ "^/123" && net.dst.port == 9001

We could preprocess that to have a mapping of possible prefixes to expressions to check:

(note that expression 1 can match regardless of the path, so it must always be considered)

"/abc" => [1, 2]
"/abc123" => [1, 2, 4]
"/foobar/" => [1, 3]
"/123" => [1, 5]
"/123/456" => [1, 4, 5]
otherwise => [1]

(where the longest prefix that is a prefix of the incoming context determines what expressions need to be checked)

This quick prefilter check should be able to reduce the number of required expression checks by quite a lot, with larger numbers of expressions, assuming most expressions are at least partly based on the http.path.

Rust's regex-syntax crate has the ability to extract required literal prefixes, so we can do that check even for regexes.

I've started working on a library to do exactly this, and results so far seem promising.

Is this something that would be interesting to integrate here?

[Oyami-Srk]

That's really a good idea! We previously discussed using something like a trie to speed up router matching by reducing the amount of execution.
The previous idea is that we can build a tree to group some conditions that conflict with each other, and even using trie for string matching. However, that would be very complex and may introduce some priority/matching order behavior change.