Module trigram 

Trigram inverted index — the hippocampus (fast pattern separation).

Inspired by Google Code Search (Russ Cox, 2012): build a posting list of trigrams (3-character substrings) at index time. At query time, extract trigrams from query terms, intersect posting lists to narrow candidates from O(all_nodes) to O(matching_nodes).

How it works

Each node’s haystack (id + title + summary + aliases + query_examples, lowercased) is split into overlapping 3-char trigrams. A HashMap<Trigram, RoaringBitSet<NodeIndex>> maps each trigram to the set of nodes that contain it.

At query time: each stemmed query term produces a set of trigrams. The intersection of posting lists for those trigrams gives the set of nodes whose haystack contains that term (as a substring, matching the existing haystack.contains(term) semantics exactly).

Eval-byte-identical guarantee

The trigram index only NARROWS the candidate set — it doesn’t change which nodes get scored. A node is a candidate if and only if its haystack contains at least one query term as a substring. The trigram intersection is a necessary-but-not-sufficient condition: if a node’s haystack contains a term, it necessarily contains all the term’s trigrams. So the index never misses a real candidate (no false negatives), and the final contains() check eliminates false positives (nodes that have the trigrams but not the actual term).

Result: identical scoring, dramatically less work on large graphs.

Structs

TrigramIndex

The trigram inverted index: maps each trigram to the set of node indices that contain it.