Unnamed repository; edit this file 'description' to name the repository.
Add more documentation for term search
| -rw-r--r-- | crates/hir/src/term_search/mod.rs | 67 | ||||
| -rw-r--r-- | crates/hir/src/term_search/tactics.rs | 59 | ||||
| -rw-r--r-- | crates/hir/src/term_search/type_tree.rs | 7 |
3 files changed, 120 insertions, 13 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); } diff --git a/crates/hir/src/term_search/tactics.rs b/crates/hir/src/term_search/tactics.rs index 8726161737..34ff420a81 100644 --- a/crates/hir/src/term_search/tactics.rs +++ b/crates/hir/src/term_search/tactics.rs @@ -1,4 +1,12 @@ //! Tactics for term search +//! +//! All the tactics take following arguments +//! * `db` - HIR database +//! * `module` - Module where the term search target location +//! * `defs` - Set of items in scope at term search target location +//! * `lookup` - Lookup table for types +//! * `goal` - Term search target type +//! And they return iterator that yields type trees that unify with the `goal` type. use hir_def::generics::TypeOrConstParamData; use hir_ty::db::HirDatabase; @@ -16,10 +24,21 @@ use crate::term_search::TypeTree; use super::{LookupTable, NewTypesKey, MAX_VARIATIONS}; -/// Trivial tactic +/// # Trivial tactic /// /// Attempts to fulfill the goal by trying items in scope -/// Also works as a starting point to move all items in scope to lookup table +/// Also works as a starting point to move all items in scope to lookup table. +/// +/// # Arguments +/// * `db` - HIR database +/// * `defs` - Set of items in scope at term search target location +/// * `lookup` - Lookup table for types +/// * `goal` - Term search target type +/// +/// Returns iterator that yields elements that unify with `goal`. +/// +/// _Note that there is no use of calling this tactic in every iteration as the output does not +/// depend on the current state of `lookup`_ pub(super) fn trivial<'a>( db: &'a dyn HirDatabase, defs: &'a FxHashSet<ScopeDef>, @@ -67,10 +86,13 @@ pub(super) fn trivial<'a>( }) } -/// Type constructor tactic +/// # Type constructor tactic /// /// Attempts different type constructors for enums and structs in scope /// +/// Updates lookup by new types reached and returns iterator that yields +/// elements that unify with `goal`. +/// /// # Arguments /// * `db` - HIR database /// * `module` - Module where the term search target location @@ -255,9 +277,13 @@ pub(super) fn type_constructor<'a>( .flatten() } -/// Free function tactic +/// # Free function tactic /// -/// Attempts to call different functions in scope with parameters from lookup table +/// Attempts to call different functions in scope with parameters from lookup table. +/// Functions that include generics are not used for performance reasons. +/// +/// Updates lookup by new types reached and returns iterator that yields +/// elements that unify with `goal`. /// /// # Arguments /// * `db` - HIR database @@ -356,10 +382,15 @@ pub(super) fn free_function<'a>( .flatten() } -/// Impl method tactic +/// # Impl method tactic /// /// Attempts to to call methods on types from lookup table. /// This includes both functions from direct impl blocks as well as functions from traits. +/// Methods defined in impl blocks that are generic and methods that are themselves have +/// generics are ignored for performance reasons. +/// +/// Updates lookup by new types reached and returns iterator that yields +/// elements that unify with `goal`. /// /// # Arguments /// * `db` - HIR database @@ -484,9 +515,12 @@ pub(super) fn impl_method<'a>( .flatten() } -/// Struct projection tactic +/// # Struct projection tactic /// -/// Attempts different struct fields +/// Attempts different struct fields (`foo.bar.baz`) +/// +/// Updates lookup by new types reached and returns iterator that yields +/// elements that unify with `goal`. /// /// # Arguments /// * `db` - HIR database @@ -522,9 +556,14 @@ pub(super) fn struct_projection<'a>( .flatten() } -/// Famous types tactic +/// # Famous types tactic +/// +/// Attempts different values of well known types such as `true` or `false`. +/// +/// Updates lookup by new types reached and returns iterator that yields +/// elements that unify with `goal`. /// -/// Attempts different values of well known types such as `true` or `false` +/// _Note that there is no point of calling it iteratively as the output is always the same_ /// /// # Arguments /// * `db` - HIR database diff --git a/crates/hir/src/term_search/type_tree.rs b/crates/hir/src/term_search/type_tree.rs index 61b21c86ee..4178ba2d7d 100644 --- a/crates/hir/src/term_search/type_tree.rs +++ b/crates/hir/src/term_search/type_tree.rs @@ -9,6 +9,7 @@ use crate::{ Struct, StructKind, Trait, Type, Variant, }; +/// Helper function to prefix items with modules when required fn mod_item_path(db: &dyn HirDatabase, sema_scope: &SemanticsScope<'_>, def: &ModuleDef) -> String { // Account for locals shadowing items from module let name_hit_count = def.name(db).map(|def_name| { @@ -76,6 +77,11 @@ pub enum TypeTree { } impl TypeTree { + /// Generate source code for type tree. + /// + /// Note that trait imports are not added to generated code. + /// To make sure that the code is valid, callee has to also ensure that all the traits listed + /// by `traits_used` method are also imported. pub fn gen_source_code(&self, sema_scope: &SemanticsScope<'_>) -> String { let db = sema_scope.db; match self { @@ -222,6 +228,7 @@ impl TypeTree { } } + /// List the traits used in type tree pub fn traits_used(&self, db: &dyn HirDatabase) -> Vec<Trait> { let mut res = Vec::new(); |