Hacker News Reader

Comment by thomasahle | Hacker News Reader

> The Avira Browser Safety extension contains a website allowlist with 30k+ regular expressions. When the user navigates to a new page Avira checks if the page URL is in that allowlist

I wonder who thought that would be a good idea... Sounds like something that could be significantly improved by compiling all patterns into a single statemachine.

View on HN

That's what Safari does for its ad blocker plugin API. Also allows for greater privacy since the browser can apply a static list and the plugin never knows what you sites you browsed to. Google is trying to move to enforce the same model but it's limiting in some ways and generated massive uproar.

Yeah, back when I was doing similar matching on a big bunch of regexes, it was vastly faster to match on all of them lumped together in a group with the ‘or’ operator. And I learned of this more than fifteen years ago from a server-side lib that deduced the exact browser from the user-agent: it had a huge regex with various placeholders and a long list of ‘if/elseif’ checks to extract the values.

Exactly. If your regex engine compiles to a DFA, you can have arbitrary many or clauses with no overhead. It's pretty neat.

FYI: content blockers like uBlock Origin or Ghostery use block lists of tens of thousands of rules as well (can be up to 100k depending on lists enabled) and there are ways to make this matching very efficient[1].

[1] https://news.ycombinator.com/item?id=19175003

Reply on news.ycombinator.com