4 files changed, 227 insertions, 111 deletions

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)
+}