Merge #237

237: This moves parts of completion from ad-hockery to descriptors-based resolve r=matklad a=matklad



Co-authored-by: Aleksey Kladov <[email protected]>

9 files changed, 262 insertions, 166 deletions

diff --git a/crates/ra_analysis/src/completion/mod.rs b/crates/ra_analysis/src/completion/mod.rs
index a8a752fc7..c7717ab61 100644
--- a/crates/ra_analysis/src/completion/mod.rs
+++ b/crates/ra_analysis/src/completion/mod.rs
@@ -221,6 +221,20 @@ mod tests {
     }
 
     #[test]
+    fn test_completion_self_path() {
+        check_scope_completion(
+            r"
+            use self::m::<|>;
+
+            mod m {
+                struct Bar;
+            }
+            ",
+            r#"[CompletionItem { label: "Bar", lookup: None, snippet: None }]"#,
+        );
+    }
+
+    #[test]
     fn test_completion_mod_scope_nested() {
         check_scope_completion(
             r"
diff --git a/crates/ra_analysis/src/completion/reference_completion.rs b/crates/ra_analysis/src/completion/reference_completion.rs
index 84383b547..d301a3c02 100644
--- a/crates/ra_analysis/src/completion/reference_completion.rs
+++ b/crates/ra_analysis/src/completion/reference_completion.rs
@@ -10,8 +10,11 @@ use ra_syntax::{
 use crate::{
     db::RootDatabase,
     completion::CompletionItem,
-    descriptors::module::{ModuleDescriptor},
-    descriptors::function::FnScopes,
+    descriptors::{
+        module::{ModuleDescriptor},
+        function::FnScopes,
+        Path,
+    },
     Cancelable
 };
 
@@ -55,7 +58,7 @@ pub(super) fn completions(
                     }),
             );
         }
-        NameRefKind::CratePath(path) => complete_path(acc, db, module, path)?,
+        NameRefKind::Path(path) => complete_path(acc, db, module, path)?,
         NameRefKind::BareIdentInMod => {
             let name_range = name_ref.syntax().range();
             let top_node = name_ref
@@ -79,8 +82,8 @@ enum NameRefKind<'a> {
     LocalRef {
         enclosing_fn: Option<ast::FnDef<'a>>,
     },
-    /// NameRef is the last segment in crate:: path
-    CratePath(Vec<ast::NameRef<'a>>),
+    /// NameRef is the last segment in some path
+    Path(Path),
     /// NameRef is bare identifier at the module's root.
     /// Used for keyword completion
     BareIdentInMod,
@@ -102,8 +105,10 @@ fn classify_name_ref(name_ref: ast::NameRef) -> Option<NameRefKind> {
     let parent = name_ref.syntax().parent()?;
     if let Some(segment) = ast::PathSegment::cast(parent) {
         let path = segment.parent_path();
-        if let Some(crate_path) = crate_path(path) {
-            return Some(NameRefKind::CratePath(crate_path));
+        if let Some(path) = Path::from_ast(path) {
+            if !path.is_ident() {
+                return Some(NameRefKind::Path(path));
+            }
         }
         if path.qualifier().is_none() {
             let enclosing_fn = name_ref
@@ -117,32 +122,6 @@ fn classify_name_ref(name_ref: ast::NameRef) -> Option<NameRefKind> {
     None
 }
 
-fn crate_path(mut path: ast::Path) -> Option<Vec<ast::NameRef>> {
-    let mut res = Vec::new();
-    loop {
-        let segment = path.segment()?;
-        match segment.kind()? {
-            ast::PathSegmentKind::Name(name) => res.push(name),
-            ast::PathSegmentKind::CrateKw => break,
-            ast::PathSegmentKind::SelfKw | ast::PathSegmentKind::SuperKw => return None,
-        }
-        path = qualifier(path)?;
-    }
-    res.reverse();
-    return Some(res);
-
-    fn qualifier(path: ast::Path) -> Option<ast::Path> {
-        if let Some(q) = path.qualifier() {
-            return Some(q);
-        }
-        // TODO: this bottom up traversal is not too precise.
-        // Should we handle do a top-down analysiss, recording results?
-        let use_tree_list = path.syntax().ancestors().find_map(ast::UseTreeList::cast)?;
-        let use_tree = use_tree_list.parent_use_tree();
-        use_tree.path()
-    }
-}
-
 fn complete_fn(name_ref: ast::NameRef, scopes: &FnScopes, acc: &mut Vec<CompletionItem>) {
     let mut shadowed = FxHashSet::default();
     acc.extend(
@@ -169,9 +148,13 @@ fn complete_path(
     acc: &mut Vec<CompletionItem>,
     db: &RootDatabase,
     module: &ModuleDescriptor,
-    crate_path: Vec<ast::NameRef>,
+    mut path: Path,
 ) -> Cancelable<()> {
-    let target_module = match find_target_module(module, crate_path) {
+    if path.segments.is_empty() {
+        return Ok(());
+    }
+    path.segments.pop();
+    let target_module = match module.resolve_path(path) {
         None => return Ok(()),
         Some(it) => it,
     };
@@ -188,18 +171,6 @@ fn complete_path(
     Ok(())
 }
 
-fn find_target_module(
-    module: &ModuleDescriptor,
-    mut crate_path: Vec<ast::NameRef>,
-) -> Option<ModuleDescriptor> {
-    crate_path.pop();
-    let mut target_module = module.crate_root();
-    for name in crate_path {
-        target_module = target_module.child(name.text().as_str())?;
-    }
-    Some(target_module)
-}
-
 fn complete_mod_item_snippets(acc: &mut Vec<CompletionItem>) {
     acc.push(CompletionItem {
         label: "tfn".to_string(),
diff --git a/crates/ra_analysis/src/descriptors/mod.rs b/crates/ra_analysis/src/descriptors/mod.rs
index 6b56d92e1..97750ea64 100644
--- a/crates/ra_analysis/src/descriptors/mod.rs
+++ b/crates/ra_analysis/src/descriptors/mod.rs
@@ -1,10 +1,11 @@
 pub(crate) mod function;
 pub(crate) mod module;
+mod path;
 
 use std::sync::Arc;
 
 use ra_syntax::{
-    ast::{self, AstNode, FnDefNode},
+    ast::{self, FnDefNode, AstNode},
     TextRange,
 };
 
@@ -18,6 +19,8 @@ use crate::{
     Cancelable,
 };
 
+pub(crate) use self::path::{Path, PathKind};
+
 salsa::query_group! {
     pub(crate) trait DescriptorDatabase: SyntaxDatabase + IdDatabase {
         fn fn_scopes(fn_id: FnId) -> Arc<FnScopes> {
diff --git a/crates/ra_analysis/src/descriptors/module/mod.rs b/crates/ra_analysis/src/descriptors/module/mod.rs
index cfdffcdbc..acc6c1c5a 100644
--- a/crates/ra_analysis/src/descriptors/module/mod.rs
+++ b/crates/ra_analysis/src/descriptors/module/mod.rs
@@ -14,11 +14,11 @@ use relative_path::RelativePathBuf;
 
 use crate::{
     db::SyntaxDatabase, syntax_ptr::SyntaxPtr, FileId, FilePosition, Cancelable,
-    descriptors::DescriptorDatabase,
+    descriptors::{Path, PathKind, DescriptorDatabase},
     input::SourceRootId
 };
 
-pub(crate) use self::{nameres::ModuleScope};
+pub(crate) use self::nameres::ModuleScope;
 
 /// `ModuleDescriptor` is API entry point to get all the information
 /// about a particular module.
@@ -110,6 +110,7 @@ impl ModuleDescriptor {
     }
 
     /// `name` is `None` for the crate's root module
+    #[allow(unused)]
     pub fn name(&self) -> Option<SmolStr> {
         let link = self.module_id.parent_link(&self.tree)?;
         Some(link.name(&self.tree))
@@ -131,6 +132,19 @@ impl ModuleDescriptor {
         Ok(res)
     }
 
+    pub(crate) fn resolve_path(&self, path: Path) -> Option<ModuleDescriptor> {
+        let mut curr = match path.kind {
+            PathKind::Crate => self.crate_root(),
+            PathKind::Self_ | PathKind::Plain => self.clone(),
+            PathKind::Super => self.parent()?,
+        };
+        let segments = path.segments;
+        for name in segments {
+            curr = curr.child(&name)?;
+        }
+        Some(curr)
+    }
+
     pub fn problems(&self, db: &impl DescriptorDatabase) -> Vec<(SyntaxNode, Problem)> {
         self.module_id.problems(&self.tree, db)
     }
diff --git a/crates/ra_analysis/src/descriptors/module/nameres.rs b/crates/ra_analysis/src/descriptors/module/nameres.rs
index c5bf467ca..4c555421d 100644
--- a/crates/ra_analysis/src/descriptors/module/nameres.rs
+++ b/crates/ra_analysis/src/descriptors/module/nameres.rs
@@ -1,4 +1,19 @@
-//! Name resolution algorithm
+//! Name resolution algorithm. The end result of the algorithm is `ItemMap`: a
+//! map with maps each module to it's scope: the set of items, visible in the
+//! module. That is, we only resolve imports here, name resolution of item
+//! bodies will be done in a separate step.
+//!
+//! Like Rustc, we use an interative per-crate algorithm: we start with scopes
+//! containing only directly defined items, and then iteratively resolve
+//! imports.
+//!
+//! To make this work nicely in the IDE scenarios, we place `InputModuleItems`
+//! in between raw syntax and name resolution. `InputModuleItems` are computed
+//! using only the module's syntax, and it is all directly defined items plus
+//! imports. The plain is to make `InputModuleItems` independent of local
+//! modifications (that is, typing inside a function shold not change IMIs),
+//! such that the results of name resolution can be preserved unless the module
+//! structure itself is modified.
 use std::{
     sync::Arc,
     time::Instant,
@@ -8,13 +23,14 @@ use rustc_hash::FxHashMap;
 
 use ra_syntax::{
     SmolStr, SyntaxKind::{self, *},
-    ast::{self, AstNode, ModuleItemOwner}
+    ast::{self, ModuleItemOwner}
 };
 
 use crate::{
     Cancelable,
     loc2id::{DefId, DefLoc},
     descriptors::{
+        Path, PathKind,
         DescriptorDatabase,
         module::{ModuleId, ModuleTree, ModuleSourceNode},
     },
@@ -32,7 +48,6 @@ pub(crate) struct ItemMap {
 #[derive(Debug, Default, PartialEq, Eq, Clone)]
 pub(crate) struct ModuleScope {
     pub(crate) items: FxHashMap<SmolStr, Resolution>,
-    pub(crate) import_resolutions: FxHashMap<LocalSyntaxPtr, DefId>,
 }
 
 /// A set of items and imports declared inside a module, without relation to
@@ -44,22 +59,20 @@ pub(crate) struct ModuleScope {
 #[derive(Debug, Default, PartialEq, Eq)]
 pub(crate) struct InputModuleItems {
     items: Vec<ModuleItem>,
-    glob_imports: Vec<Path>,
-    imports: Vec<Path>,
+    imports: Vec<Import>,
 }
 
 #[derive(Debug, Clone, PartialEq, Eq)]
-struct Path {
-    kind: PathKind,
-    segments: Vec<(LocalSyntaxPtr, SmolStr)>,
+struct Import {
+    path: Path,
+    kind: ImportKind,
 }
 
-#[derive(Debug, Clone, Copy, PartialEq, Eq)]
-enum PathKind {
-    Abs,
-    Self_,
-    Super,
-    Crate,
+#[derive(Debug, Clone, PartialEq, Eq)]
+enum ImportKind {
+    Glob,
+    // TODO: make offset independent
+    Named(LocalSyntaxPtr),
 }
 
 pub(crate) fn input_module_items(
@@ -182,86 +195,16 @@ impl InputModuleItems {
     }
 
     fn add_use_item(&mut self, item: ast::UseItem) {
-        if let Some(tree) = item.use_tree() {
-            self.add_use_tree(None, tree);
-        }
-    }
-
-    fn add_use_tree(&mut self, prefix: Option<Path>, tree: ast::UseTree) {
-        if let Some(use_tree_list) = tree.use_tree_list() {
-            let prefix = match tree.path() {
-                None => prefix,
-                Some(path) => match convert_path(prefix, path) {
-                    Some(it) => Some(it),
-                    None => return, // TODO: report errors somewhere
-                },
+        Path::expand_use_item(item, |path, ptr| {
+            let kind = match ptr {
+                None => ImportKind::Glob,
+                Some(ptr) => ImportKind::Named(ptr),
             };
-            for tree in use_tree_list.use_trees() {
-                self.add_use_tree(prefix.clone(), tree);
-            }
-        } else {
-            if let Some(path) = tree.path() {
-                if let Some(path) = convert_path(prefix, path) {
-                    if tree.has_star() {
-                        &mut self.glob_imports
-                    } else {
-                        &mut self.imports
-                    }
-                    .push(path);
-                }
-            }
-        }
+            self.imports.push(Import { kind, path })
+        })
     }
 }
 
-fn convert_path(prefix: Option<Path>, path: ast::Path) -> Option<Path> {
-    let prefix = if let Some(qual) = path.qualifier() {
-        Some(convert_path(prefix, qual)?)
-    } else {
-        None
-    };
-    let segment = path.segment()?;
-    let res = match segment.kind()? {
-        ast::PathSegmentKind::Name(name) => {
-            let mut res = prefix.unwrap_or_else(|| Path {
-                kind: PathKind::Abs,
-                segments: Vec::with_capacity(1),
-            });
-            let ptr = LocalSyntaxPtr::new(name.syntax());
-            res.segments.push((ptr, name.text()));
-            res
-        }
-        ast::PathSegmentKind::CrateKw => {
-            if prefix.is_some() {
-                return None;
-            }
-            Path {
-                kind: PathKind::Crate,
-                segments: Vec::new(),
-            }
-        }
-        ast::PathSegmentKind::SelfKw => {
-            if prefix.is_some() {
-                return None;
-            }
-            Path {
-                kind: PathKind::Self_,
-                segments: Vec::new(),
-            }
-        }
-        ast::PathSegmentKind::SuperKw => {
-            if prefix.is_some() {
-                return None;
-            }
-            Path {
-                kind: PathKind::Super,
-                segments: Vec::new(),
-            }
-        }
-    };
-    Some(res)
-}
-
 impl ModuleItem {
     fn new<'a>(item: impl ast::NameOwner<'a>) -> Option<ModuleItem> {
         let name = item.name()?.text();
@@ -308,14 +251,16 @@ where
         let mut module_items = ModuleScope::default();
 
         for import in input.imports.iter() {
-            if let Some((ptr, name)) = import.segments.last() {
-                module_items.items.insert(
-                    name.clone(),
-                    Resolution {
-                        def_id: None,
-                        import_name: Some(*ptr),
-                    },
-                );
+            if let Some(name) = import.path.segments.iter().last() {
+                if let ImportKind::Named(ptr) = import.kind {
+                    module_items.items.insert(
+                        name.clone(),
+                        Resolution {
+                            def_id: None,
+                            import_name: Some(ptr),
+                        },
+                    );
+                }
             }
         }
 
@@ -356,10 +301,15 @@ where
         }
     }
 
-    fn resolve_import(&mut self, module_id: ModuleId, import: &Path) {
-        let mut curr = match import.kind {
+    fn resolve_import(&mut self, module_id: ModuleId, import: &Import) {
+        let ptr = match import.kind {
+            ImportKind::Glob => return,
+            ImportKind::Named(ptr) => ptr,
+        };
+
+        let mut curr = match import.path.kind {
             // TODO: handle extern crates
-            PathKind::Abs => return,
+            PathKind::Plain => return,
             PathKind::Self_ => module_id,
             PathKind::Super => {
                 match module_id.parent(&self.module_tree) {
@@ -371,8 +321,8 @@ where
             PathKind::Crate => module_id.crate_root(&self.module_tree),
         };
 
-        for (i, (ptr, name)) in import.segments.iter().enumerate() {
-            let is_last = i == import.segments.len() - 1;
+        for (i, name) in import.path.segments.iter().enumerate() {
+            let is_last = i == import.path.segments.len() - 1;
 
             let def_id = match self.result.per_module[&curr].items.get(name) {
                 None => return,
@@ -382,10 +332,6 @@ where
                 },
             };
 
-            self.update(module_id, |items| {
-                items.import_resolutions.insert(*ptr, def_id);
-            });
-
             if !is_last {
                 curr = match self.db.id_maps().def_loc(def_id) {
                     DefLoc::Module { id, .. } => id,
@@ -395,7 +341,7 @@ where
                 self.update(module_id, |items| {
                     let res = Resolution {
                         def_id: Some(def_id),
-                        import_name: Some(*ptr),
+                        import_name: Some(ptr),
                     };
                     items.items.insert(name.clone(), res);
                 })
diff --git a/crates/ra_analysis/src/descriptors/path.rs b/crates/ra_analysis/src/descriptors/path.rs
new file mode 100644
index 000000000..99fca18b1
--- /dev/null
+++ b/crates/ra_analysis/src/descriptors/path.rs
@@ -0,0 +1,153 @@
+use ra_syntax::{SmolStr, ast, AstNode};
+
+use crate::syntax_ptr::LocalSyntaxPtr;
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub(crate) struct Path {
+    pub(crate) kind: PathKind,
+    pub(crate) segments: Vec<SmolStr>,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub(crate) enum PathKind {
+    Plain,
+    Self_,
+    Super,
+    Crate,
+}
+
+impl Path {
+    /// Calls `cb` with all paths, represented by this use item.
+    pub(crate) fn expand_use_item(
+        item: ast::UseItem,
+        mut cb: impl FnMut(Path, Option<LocalSyntaxPtr>),
+    ) {
+        if let Some(tree) = item.use_tree() {
+            expand_use_tree(None, tree, &mut cb);
+        }
+    }
+
+    /// Converts an `ast::Path` to `Path`. Works with use trees.
+    pub(crate) fn from_ast(mut path: ast::Path) -> Option<Path> {
+        let mut kind = PathKind::Plain;
+        let mut segments = Vec::new();
+        loop {
+            let segment = path.segment()?;
+            match segment.kind()? {
+                ast::PathSegmentKind::Name(name) => segments.push(name.text()),
+                ast::PathSegmentKind::CrateKw => {
+                    kind = PathKind::Crate;
+                    break;
+                }
+                ast::PathSegmentKind::SelfKw => {
+                    kind = PathKind::Self_;
+                    break;
+                }
+                ast::PathSegmentKind::SuperKw => {
+                    kind = PathKind::Super;
+                    break;
+                }
+            }
+            path = match qualifier(path) {
+                Some(it) => it,
+                None => break,
+            };
+        }
+        segments.reverse();
+        return Some(Path { kind, segments });
+
+        fn qualifier(path: ast::Path) -> Option<ast::Path> {
+            if let Some(q) = path.qualifier() {
+                return Some(q);
+            }
+            // TODO: this bottom up traversal is not too precise.
+            // Should we handle do a top-down analysiss, recording results?
+            let use_tree_list = path.syntax().ancestors().find_map(ast::UseTreeList::cast)?;
+            let use_tree = use_tree_list.parent_use_tree();
+            use_tree.path()
+        }
+    }
+
+    /// `true` is this path is a single identifier, like `foo`
+    pub(crate) fn is_ident(&self) -> bool {
+        self.kind == PathKind::Plain && self.segments.len() == 1
+    }
+}
+
+fn expand_use_tree(
+    prefix: Option<Path>,
+    tree: ast::UseTree,
+    cb: &mut impl FnMut(Path, Option<LocalSyntaxPtr>),
+) {
+    if let Some(use_tree_list) = tree.use_tree_list() {
+        let prefix = match tree.path() {
+            None => prefix,
+            Some(path) => match convert_path(prefix, path) {
+                Some(it) => Some(it),
+                None => return, // TODO: report errors somewhere
+            },
+        };
+        for tree in use_tree_list.use_trees() {
+            expand_use_tree(prefix.clone(), tree, cb);
+        }
+    } else {
+        if let Some(ast_path) = tree.path() {
+            if let Some(path) = convert_path(prefix, ast_path) {
+                let ptr = if tree.has_star() {
+                    None
+                } else {
+                    let ptr = LocalSyntaxPtr::new(ast_path.segment().unwrap().syntax());
+                    Some(ptr)
+                };
+                cb(path, ptr)
+            }
+        }
+    }
+}
+
+fn convert_path(prefix: Option<Path>, path: ast::Path) -> Option<Path> {
+    let prefix = if let Some(qual) = path.qualifier() {
+        Some(convert_path(prefix, qual)?)
+    } else {
+        None
+    };
+    let segment = path.segment()?;
+    let res = match segment.kind()? {
+        ast::PathSegmentKind::Name(name) => {
+            let mut res = prefix.unwrap_or_else(|| Path {
+                kind: PathKind::Plain,
+                segments: Vec::with_capacity(1),
+            });
+            res.segments.push(name.text());
+            res
+        }
+        ast::PathSegmentKind::CrateKw => {
+            if prefix.is_some() {
+                return None;
+            }
+            Path {
+                kind: PathKind::Crate,
+                segments: Vec::new(),
+            }
+        }
+        ast::PathSegmentKind::SelfKw => {
+            if prefix.is_some() {
+                return None;
+            }
+            Path {
+                kind: PathKind::Self_,
+                segments: Vec::new(),
+            }
+        }
+        ast::PathSegmentKind::SuperKw => {
+            if prefix.is_some() {
+                return None;
+            }
+            Path {
+                kind: PathKind::Super,
+                segments: Vec::new(),
+            }
+        }
+    };
+    Some(res)
+}
diff --git a/crates/ra_editor/src/lib.rs b/crates/ra_editor/src/lib.rs
index ff4e8303d..c6b116159 100644
--- a/crates/ra_editor/src/lib.rs
+++ b/crates/ra_editor/src/lib.rs
@@ -148,12 +148,7 @@ pub fn find_node_at_offset<'a, N: AstNode<'a>>(
     syntax: SyntaxNodeRef<'a>,
     offset: TextUnit,
 ) -> Option<N> {
-    let leaves = find_leaf_at_offset(syntax, offset);
-    let leaf = leaves
-        .clone()
-        .find(|leaf| !leaf.kind().is_trivia())
-        .or_else(|| leaves.right_biased())?;
-    leaf.ancestors().filter_map(N::cast).next()
+    find_leaf_at_offset(syntax, offset).find_map(|leaf| leaf.ancestors().find_map(N::cast))
 }
 
 #[cfg(test)]
diff --git a/crates/ra_syntax/src/grammar/items/mod.rs b/crates/ra_syntax/src/grammar/items/mod.rs
index 06c6b5e6e..682266908 100644
--- a/crates/ra_syntax/src/grammar/items/mod.rs
+++ b/crates/ra_syntax/src/grammar/items/mod.rs
@@ -29,7 +29,7 @@ pub(super) enum ItemFlavor {
     Trait,
 }
 
-const ITEM_RECOVERY_SET: TokenSet = token_set![
+pub(super) const ITEM_RECOVERY_SET: TokenSet = token_set![
     FN_KW, STRUCT_KW, ENUM_KW, IMPL_KW, TRAIT_KW, CONST_KW, STATIC_KW, LET_KW, MOD_KW, PUB_KW,
     CRATE_KW
 ];
diff --git a/crates/ra_syntax/src/grammar/paths.rs b/crates/ra_syntax/src/grammar/paths.rs
index a35a339cc..33a11886c 100644
--- a/crates/ra_syntax/src/grammar/paths.rs
+++ b/crates/ra_syntax/src/grammar/paths.rs
@@ -78,7 +78,7 @@ fn path_segment(p: &mut Parser, mode: Mode, first: bool) {
             // use crate::foo;
             SELF_KW | SUPER_KW | CRATE_KW => p.bump(),
             _ => {
-                p.err_and_bump("expected identifier");
+                p.err_recover("expected identifier", items::ITEM_RECOVERY_SET);
             }
         };
     }