Linter: Add probabilistic symbol lookups

With the first PR in the stack of perf optimizations for automatically detecting node types merged, I started thinking about possible future optimizations once all of the possible rules that apply to node types have been optimized. I'm not actively thinking about working on this, but I wanted to write it down while it's fresh in my mind.

Other than node types, one of the most commonly used data in lint rules is the symbol table. Lint rules will often iterate over the symbol table and check how each symbol is referenced or check if a specific symbol is one of the ones that we're linting for.

For example, these are some rules based around symbol lookup:

• https://oxc.rs/docs/guide/usage/linter/rules/eslint/no-shadow-restricted-names.html
• https://oxc.rs/docs/guide/usage/linter/rules/eslint/no-extend-native.html

Optimization

Similar to what we did for node types, we can do for symbols: generate a list of symbols that a rule acts on, then skip any files that don't contain any of those symbols.

Okay, getting the list of symbols used in a rule can be done automatically or manually (now that we have infra for this in place), but how do we check if a file contains a given symbol?

Probabilistic data structures

It would be expensive to save a hash set of every symbol in a file, both in terms of memory and CPU.

However, the main insight here is that false positives are okay. No harm comes from running a lint rule on a file that will never emit a diagnostic. So, it's fine if any optimization results in too many lint rules running. The important thing is that any runtime optimization needs to be not too costly in CPU cycles and memory in order for it to outweigh the cost of setting it up in the first place. So, any new lookup we add for symbols needs to be memory efficient and fast, since we will have lots of symbols normally.

A bloom filter is a space efficient, probabilistic data structure for checking if a set either "probably contains" or "definitely does not contain" a given element. This means that false positives can happen, but false negatives (missing an element when it's actually there) are impossible.

Suppose that we use a bloom filter as the initial check for if a file contains a given symbol. As we construct the semantic info, we hash each symbol (need not be cryptographic, or even the whole string) and insert it into the bloom filter. Then, the filter can tell us if a file probably contains a given symbol, or definitely does not include it.

If a file doesn't include the symbol for a specific lint rule, we can skip it with 0 percent chance of a false negative. False positives can occur, but will just result in some extra work but shouldn't add any new diagnostics.

Start by reading the linked no-shadow-restricted-names and no-extend-native rule documentation, then inspect the existing node-type optimization work mentioned in the issue. Define the symbol data collected during semantic-info construction and how lint rules would consume it. Done means irrelevant files can be skipped without false negatives while keeping CPU and memory costs low.