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§

Traits§

Functions§