Unnamed repository; edit this file 'description' to name the repository.
Diffstat (limited to 'crates/hir/src/term_search/mod.rs')
| -rw-r--r-- | crates/hir/src/term_search/mod.rs | 67 |
1 files changed, 64 insertions, 3 deletions
diff --git a/crates/hir/src/term_search/mod.rs b/crates/hir/src/term_search/mod.rs index b1e616e004..6ea5b105de 100644 --- a/crates/hir/src/term_search/mod.rs +++ b/crates/hir/src/term_search/mod.rs @@ -12,25 +12,45 @@ pub use type_tree::TypeTree; mod tactics; +/// # Maximum amount of variations to take per type +/// +/// This is to speed up term search as there may be huge amount of variations of arguments for +/// function, even when the return type is always the same. The idea is to take first n and call it +/// a day. const MAX_VARIATIONS: usize = 10; +/// Key for lookup table to query new types reached. #[derive(Debug, Hash, PartialEq, Eq)] enum NewTypesKey { ImplMethod, StructProjection, } -/// Lookup table for term search +/// # Lookup table for term search +/// +/// Lookup table keeps all the state during term search. +/// This means it knows what types and how are reachable. +/// +/// The secondary functionality for lookup table is to keep track of new types reached since last +/// iteration as well as keeping track of which `ScopeDef` items have been used. +/// Both of them are to speed up the term search by leaving out types / ScopeDefs that likely do +/// not produce any new results. #[derive(Default, Debug)] struct LookupTable { + /// All the `TypeTree`s in "value" produce the type of "key" data: FxHashMap<Type, FxHashSet<TypeTree>>, + /// New types reached since last query by the `NewTypesKey` new_types: FxHashMap<NewTypesKey, Vec<Type>>, + /// ScopeDefs that are not interesting any more exhausted_scopedefs: FxHashSet<ScopeDef>, + /// ScopeDefs that were used in current round round_scopedef_hits: FxHashSet<ScopeDef>, - scopedef_hits: FxHashMap<ScopeDef, u32>, + /// Amount of rounds since scopedef was first used. + rounds_since_sopedef_hit: FxHashMap<ScopeDef, u32>, } impl LookupTable { + /// Initialize lookup table fn new() -> Self { let mut res: Self = Default::default(); res.new_types.insert(NewTypesKey::ImplMethod, Vec::new()); @@ -38,6 +58,7 @@ impl LookupTable { res } + /// Find all `TypeTree`s that unify with the `ty` fn find(&self, db: &dyn HirDatabase, ty: &Type) -> Option<Vec<TypeTree>> { self.data .iter() @@ -45,6 +66,10 @@ impl LookupTable { .map(|(_, tts)| tts.iter().cloned().collect()) } + /// Same as find but automatically creates shared reference of types in the lookup + /// + /// For example if we have type `i32` in data and we query for `&i32` it map all the type + /// trees we have for `i32` with `TypeTree::Reference` and returns them. fn find_autoref(&self, db: &dyn HirDatabase, ty: &Type) -> Option<Vec<TypeTree>> { self.data .iter() @@ -62,6 +87,11 @@ impl LookupTable { }) } + /// Insert new type trees for type + /// + /// Note that the types have to be the same, unification is not enough as unification is not + /// transitive. For example Vec<i32> and FxHashSet<i32> both unify with Iterator<Item = i32>, + /// but they clearly do not unify themselves. fn insert(&mut self, ty: Type, trees: impl Iterator<Item = TypeTree>) { match self.data.get_mut(&ty) { Some(it) => it.extend(trees.take(MAX_VARIATIONS)), @@ -74,10 +104,14 @@ impl LookupTable { } } + /// Iterate all the reachable types fn iter_types(&self) -> impl Iterator<Item = Type> + '_ { self.data.keys().cloned() } + /// Query new types reached since last query by key + /// + /// Create new key if you wish to query it to avoid conflicting with existing queries. fn new_types(&mut self, key: NewTypesKey) -> Vec<Type> { match self.new_types.get_mut(&key) { Some(it) => std::mem::take(it), @@ -85,17 +119,24 @@ impl LookupTable { } } + /// Mark `ScopeDef` as exhausted meaning it is not interesting for us any more fn mark_exhausted(&mut self, def: ScopeDef) { self.exhausted_scopedefs.insert(def); } + /// Mark `ScopeDef` as used meaning we managed to produce something useful from it fn mark_fulfilled(&mut self, def: ScopeDef) { self.round_scopedef_hits.insert(def); } + /// Start new round (meant to be called at the beginning of iteration in `term_search`) + /// + /// This functions marks some `ScopeDef`s as exhausted if there have been + /// `MAX_ROUNDS_AFTER_HIT` rounds after first using a `ScopeDef`. fn new_round(&mut self) { for def in &self.round_scopedef_hits { - let hits = self.scopedef_hits.entry(*def).and_modify(|n| *n += 1).or_insert(0); + let hits = + self.rounds_since_sopedef_hit.entry(*def).and_modify(|n| *n += 1).or_insert(0); const MAX_ROUNDS_AFTER_HIT: u32 = 2; if *hits > MAX_ROUNDS_AFTER_HIT { self.exhausted_scopedefs.insert(*def); @@ -104,6 +145,7 @@ impl LookupTable { self.round_scopedef_hits.clear(); } + /// Get exhausted `ScopeDef`s fn exhausted_scopedefs(&self) -> &FxHashSet<ScopeDef> { &self.exhausted_scopedefs } @@ -117,6 +159,22 @@ impl LookupTable { /// * `sema` - Semantics for the program /// * `scope` - Semantic scope, captures context for the term search /// * `goal` - Target / expected output type +/// +/// Internally this function uses Breadth First Search to find path to `goal` type. +/// The general idea is following: +/// 1. Populate lookup (frontier for BFS) from values (local variables, statics, constants, etc) +/// as well as from well knows values (such as `true/false` and `()`) +/// 2. Iteratively expand the frontier (or contents of the lookup) by trying different type +/// transformation tactics. For example functions take as from set of types (arguments) to some +/// type (return type). Other transformations include methods on type, type constructors and +/// projections to struct fields (field access). +/// 3. Once we manage to find path to type we are interested in we continue for single round to see +/// if we can find more paths that take us to the `goal` type. +/// 4. Return all the paths (type trees) that take us to the `goal` type. +/// +/// Note that there are usually more ways we can get to the `goal` type but some are discarded to +/// reduce the memory consumption. It is also unlikely anyone is willing ti browse through +/// thousands of possible responses so we currently take first 10 from every tactic. pub fn term_search<DB: HirDatabase>( sema: &Semantics<'_, DB>, scope: &SemanticsScope<'_>, @@ -135,6 +193,7 @@ pub fn term_search<DB: HirDatabase>( // Try trivial tactic first, also populates lookup table let mut solutions: Vec<TypeTree> = tactics::trivial(sema.db, &defs, &mut lookup, goal).collect(); + // Use well known types tactic before iterations as it does not depend on other tactics solutions.extend(tactics::famous_types(sema.db, &module, &defs, &mut lookup, goal)); let mut solution_found = !solutions.is_empty(); @@ -147,12 +206,14 @@ pub fn term_search<DB: HirDatabase>( solutions.extend(tactics::impl_method(sema.db, &module, &defs, &mut lookup, goal)); solutions.extend(tactics::struct_projection(sema.db, &module, &defs, &mut lookup, goal)); + // Break after 1 round after successful solution if solution_found { break; } solution_found = !solutions.is_empty(); + // Discard not interesting `ScopeDef`s for speedup for def in lookup.exhausted_scopedefs() { defs.remove(def); } |