Support Forward looking Regex used in uBO

[ryanbr]

/^https?:\/\/(?:[a-z]{2}\.)?[0-9a-z]{5,16}\.[a-z]{3,7}\/[a-z](?=[a-z]{0,25}[0-9A-Z])[0-9a-zA-Z]{3,26}\/\d{3,6}(?:[?&][_a-z0-9]+=[-0-9a-zA-Z]+)*$/$script,3p,redirect-rule=noop.js,match-case

The lookahead is unsupported: (?=[a-z]{0,25}[0-9A-Z])

Probably a seperate issue:

/\/[0-9a-z]{2}\/[0-9a-f]{32}\.js/$script,3p,match-case,method=get,from=~edu.ag|~edu.by|~edu.bz|~edu.ge|~edu.in|~edu.md|~edu.me|~edu.pe|~edu.pk|~edu.so|~edu.ws|~gov.ag|~gov.by|~gov.bz|~gov.ge|~gov.in|~gov.md|~gov.me|~gov.pk|~gov.sh|~gov.so|~gov.to|~gov.tv|~gov.ws|~palaugov.pw|~proton.me|~twitch.tv|ad|ag|app|bet|biz|blogspot.com|blue|boo|by|bz|casa|cash|cc|ceo|cfd|click|club|com.se|cx|cyou|dad|day|dev|download|forum|fun|gdn|ge|hair|homes|host|how|icu|in|info|is|lat|link|live|lol|ltd|md|me|media|mobi|moe|monster|one|onl|online|page|pe|pk|pro|pw|re|red|rest|sbs|sh|site|skin|space|stream|team|tel|to|today|top|tube|tv|wedding|world|ws|xyz,to=com

Believe the to=com is unsupported

[ryanbr]

If its possible, or if there is a perf issue with it, maybe support only in our own lists/brave settings.

[antonok-edm]

we could theoretically use fancy_regex for this, which would be more or less a drop-in replacement for the existing/normal regex crate.

However... the main concern is the following:

If your regex or parts of it does not use any special features, the matching is delegated to the regex crate. That means it has linear runtime. But if you use “fancy” features such as backreferences or look-around, an engine with backtracking needs to be used. In that case, the regex can be slow and take exponential time to run because of what is called “catastrophic backtracking”. This depends on the regex and the input.

It'd be great to support the special features without the performance impact if possible, since some uBO filters use them. To that end, we'll need to investigate how feasible it is to add some type of performance bound to the worst-case of each regex execution.

[ShivanKaul]

The perf is not looking good. Can we distinguish between regex filters that can be parsed by the regular regex crate vs ones that need fancy-regex? cc @boocmp

[ShivanKaul]

Maybe we also want to look at how uBO does it. They probably have similar perf penalties? Maybe they have some limitations that they're okay with it, and we can match that? (from discussion with @boocmp)