Module ide_db::symbol_index
source · Expand description
This module handles fuzzy-searching of functions, structs and other symbols by name across the whole workspace and dependencies.
It works by building an incrementally-updated text-search index of all
symbols. The backbone of the index is the awesome fst crate by
@BurntSushi.
In a nutshell, you give a set of strings to fst, and it builds a
finite state machine describing this set of strings. The strings which
could fuzzy-match a pattern can also be described by a finite state machine.
What is freaking cool is that you can now traverse both state machines in
lock-step to enumerate the strings which are both in the input set and
fuzz-match the query. Or, more formally, given two languages described by
FSTs, one can build a product FST which describes the intersection of the
languages.
fst does not support cheap updating of the index, but it supports unioning
of state machines. So, to account for changing source code, we build an FST
for each library (which is assumed to never change) and an FST for each Rust
file in the current workspace, and run a query against the union of all
those FSTs.
Structs§
- Representative struct for the query group.