today we have a bunch of rules that rely on substring features, sometimes many of them, like compiled-with-rust. matching these features requires doing a regex match against every string encountered in the program, which we suspect is expensive.
to make this cheaper, we could introduce a filtering pass first:
when encountering a string feature, check the filter first to see if it might possibly match any regexes in any rule. only if that filter passes are the regexes run.
the filter might be implemented as: extract a prefix literal from the regex/substring, and then use Aho-Corasick automaton to check if the literal is present anywhere in the string. this should be very fast, much faster than repeatedly running regex against the string. from wikipedia:
It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all strings simultaneously. The complexity of the algorithm is linear in the length of the strings plus the length of the searched text plus the number of output matches.
today we have a bunch of rules that rely on substring features, sometimes many of them, like compiled-with-rust. matching these features requires doing a regex match against every string encountered in the program, which we suspect is expensive.
to make this cheaper, we could introduce a filtering pass first:
when encountering a string feature, check the filter first to see if it might possibly match any regexes in any rule. only if that filter passes are the regexes run.
the filter might be implemented as: extract a prefix literal from the regex/substring, and then use Aho-Corasick automaton to check if the literal is present anywhere in the string. this should be very fast, much faster than repeatedly running regex against the string. from wikipedia: