Merge #236

236: WIP: Module name resolution r=matklad a=matklad

work towards #231 

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

13 files changed, 556 insertions, 179 deletions

diff --git a/.travis.yml b/.travis.yml
index 36fd746dd..012453497 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -9,7 +9,7 @@ env:
 
 build: &rust_build
   language: rust
-  rust: beta
+  rust: beta-2018-11-19
   script:
     - cargo gen-tests --verify
     - cargo gen-syntax --verify
diff --git a/crates/ra_analysis/src/completion/mod.rs b/crates/ra_analysis/src/completion/mod.rs
index 5e3ee79dd..a8a752fc7 100644
--- a/crates/ra_analysis/src/completion/mod.rs
+++ b/crates/ra_analysis/src/completion/mod.rs
@@ -204,9 +204,9 @@ mod tests {
                 <|>
             }
             ",
-            r#"[CompletionItem { label: "Foo", lookup: None, snippet: None },
-                   CompletionItem { label: "Baz", lookup: None, snippet: None },
-                   CompletionItem { label: "quux", lookup: None, snippet: None }]"#,
+            r#"[CompletionItem { label: "quux", lookup: None, snippet: None },
+                CompletionItem { label: "Foo", lookup: None, snippet: None },
+                CompletionItem { label: "Baz", lookup: None, snippet: None }]"#,
         );
     }
 
@@ -230,8 +230,8 @@ mod tests {
                 fn quux() { <|> }
             }
             ",
-            r#"[CompletionItem { label: "Bar", lookup: None, snippet: None },
-                   CompletionItem { label: "quux", lookup: None, snippet: None }]"#,
+            r#"[CompletionItem { label: "quux", lookup: None, snippet: None },
+                CompletionItem { label: "Bar", lookup: None, snippet: None }]"#,
         );
     }
 
diff --git a/crates/ra_analysis/src/completion/reference_completion.rs b/crates/ra_analysis/src/completion/reference_completion.rs
index c94d9af75..84383b547 100644
--- a/crates/ra_analysis/src/completion/reference_completion.rs
+++ b/crates/ra_analysis/src/completion/reference_completion.rs
@@ -39,14 +39,17 @@ pub(super) fn completions(
             let module_scope = module.scope(db)?;
             acc.extend(
                 module_scope
-                    .entries()
+                    .items
                     .iter()
-                    .filter(|entry| {
+                    .filter(|(_name, res)| {
                         // Don't expose this item
-                        !entry.ptr().range().is_subrange(&name_ref.syntax().range())
+                        match res.import_name {
+                            None => true,
+                            Some(ptr) => !ptr.range().is_subrange(&name_ref.syntax().range()),
+                        }
                     })
-                    .map(|entry| CompletionItem {
-                        label: entry.name().to_string(),
+                    .map(|(name, _res)| CompletionItem {
+                        label: name.to_string(),
                         lookup: None,
                         snippet: None,
                     }),
@@ -173,11 +176,14 @@ fn complete_path(
         Some(it) => it,
     };
     let module_scope = target_module.scope(db)?;
-    let completions = module_scope.entries().iter().map(|entry| CompletionItem {
-        label: entry.name().to_string(),
-        lookup: None,
-        snippet: None,
-    });
+    let completions = module_scope
+        .items
+        .iter()
+        .map(|(name, _res)| CompletionItem {
+            label: name.to_string(),
+            lookup: None,
+            snippet: None,
+        });
     acc.extend(completions);
     Ok(())
 }
diff --git a/crates/ra_analysis/src/db.rs b/crates/ra_analysis/src/db.rs
index 8133b7875..887d687ea 100644
--- a/crates/ra_analysis/src/db.rs
+++ b/crates/ra_analysis/src/db.rs
@@ -7,8 +7,8 @@ use salsa::{self, Database};
 use crate::{
     db,
     descriptors::{
-        DescriptorDatabase, FnScopesQuery, FnSyntaxQuery, ModuleScopeQuery, ModuleTreeQuery,
-        SubmodulesQuery,
+        DescriptorDatabase, FnScopesQuery, FnSyntaxQuery, ModuleTreeQuery,
+        SubmodulesQuery, ItemMapQuery, InputModuleItemsQuery,
     },
     symbol_index::SymbolIndex,
     syntax_ptr::SyntaxPtr,
@@ -85,8 +85,9 @@ salsa::database_storage! {
         }
         impl DescriptorDatabase {
             fn module_tree() for ModuleTreeQuery;
-            fn module_scope() for ModuleScopeQuery;
             fn fn_scopes() for FnScopesQuery;
+            fn _input_module_items() for InputModuleItemsQuery;
+            fn _item_map() for ItemMapQuery;
             fn _fn_syntax() for FnSyntaxQuery;
             fn _submodules() for SubmodulesQuery;
         }
diff --git a/crates/ra_analysis/src/descriptors/mod.rs b/crates/ra_analysis/src/descriptors/mod.rs
index a8489f89c..6b56d92e1 100644
--- a/crates/ra_analysis/src/descriptors/mod.rs
+++ b/crates/ra_analysis/src/descriptors/mod.rs
@@ -11,7 +11,7 @@ use ra_syntax::{
 use crate::{
     db::SyntaxDatabase,
     descriptors::function::{resolve_local_name, FnId, FnScopes},
-    descriptors::module::{ModuleId, ModuleScope, ModuleTree, ModuleSource},
+    descriptors::module::{ModuleId, ModuleTree, ModuleSource, nameres::{ItemMap, InputModuleItems}},
     input::SourceRootId,
     loc2id::IdDatabase,
     syntax_ptr::LocalSyntaxPtr,
@@ -25,14 +25,18 @@ salsa::query_group! {
             use fn function::imp::fn_scopes;
         }
 
+        fn _input_module_items(source_root_id: SourceRootId, module_id: ModuleId) -> Cancelable<Arc<InputModuleItems>> {
+            type InputModuleItemsQuery;
+            use fn module::nameres::input_module_items;
+        }
+        fn _item_map(source_root_id: SourceRootId) -> Cancelable<Arc<ItemMap>> {
+            type ItemMapQuery;
+            use fn module::nameres::item_map;
+        }
         fn _module_tree(source_root_id: SourceRootId) -> Cancelable<Arc<ModuleTree>> {
             type ModuleTreeQuery;
             use fn module::imp::module_tree;
         }
-        fn _module_scope(source_root_id: SourceRootId, module_id: ModuleId) -> Cancelable<Arc<ModuleScope>> {
-            type ModuleScopeQuery;
-            use fn module::imp::module_scope;
-        }
         fn _fn_syntax(fn_id: FnId) -> FnDefNode {
             type FnSyntaxQuery;
             // Don't retain syntax trees in memory
diff --git a/crates/ra_analysis/src/descriptors/module/imp.rs b/crates/ra_analysis/src/descriptors/module/imp.rs
index defe87216..d4dce861f 100644
--- a/crates/ra_analysis/src/descriptors/module/imp.rs
+++ b/crates/ra_analysis/src/descriptors/module/imp.rs
@@ -1,7 +1,7 @@
 use std::sync::Arc;
 
 use ra_syntax::{
-    ast::{self, ModuleItemOwner, NameOwner},
+    ast::{self, NameOwner},
     SmolStr,
 };
 use relative_path::RelativePathBuf;
@@ -15,7 +15,7 @@ use crate::{
 };
 
 use super::{
-    LinkData, LinkId, ModuleData, ModuleId, ModuleScope, ModuleSource, ModuleSourceNode,
+    LinkData, LinkId, ModuleData, ModuleId, ModuleSource, ModuleSourceNode,
     ModuleTree, Problem,
 };
 
@@ -81,23 +81,6 @@ pub(crate) fn modules<'a>(
         })
 }
 
-pub(crate) fn module_scope(
-    db: &impl DescriptorDatabase,
-    source_root_id: SourceRootId,
-    module_id: ModuleId,
-) -> Cancelable<Arc<ModuleScope>> {
-    let tree = db._module_tree(source_root_id)?;
-    let source = module_id.source(&tree).resolve(db);
-    let res = match source {
-        ModuleSourceNode::SourceFile(it) => ModuleScope::new(it.borrowed().items()),
-        ModuleSourceNode::Module(it) => match it.borrowed().item_list() {
-            Some(items) => ModuleScope::new(items.items()),
-            None => ModuleScope::new(std::iter::empty()),
-        },
-    };
-    Ok(Arc::new(res))
-}
-
 pub(crate) fn module_tree(
     db: &impl DescriptorDatabase,
     source_root: SourceRootId,
diff --git a/crates/ra_analysis/src/descriptors/module/mod.rs b/crates/ra_analysis/src/descriptors/module/mod.rs
index 047454cff..cfdffcdbc 100644
--- a/crates/ra_analysis/src/descriptors/module/mod.rs
+++ b/crates/ra_analysis/src/descriptors/module/mod.rs
@@ -1,5 +1,5 @@
 pub(super) mod imp;
-pub(crate) mod scope;
+pub(super) mod nameres;
 
 use std::sync::Arc;
 
@@ -18,7 +18,7 @@ use crate::{
     input::SourceRootId
 };
 
-pub(crate) use self::scope::ModuleScope;
+pub(crate) use self::{nameres::ModuleScope};
 
 /// `ModuleDescriptor` is API entry point to get all the information
 /// about a particular module.
@@ -102,9 +102,11 @@ impl ModuleDescriptor {
 
     /// The root of the tree this module is part of
     pub fn crate_root(&self) -> ModuleDescriptor {
-        generate(Some(self.clone()), |it| it.parent())
-            .last()
-            .unwrap()
+        let root_id = self.module_id.crate_root(&self.tree);
+        ModuleDescriptor {
+            module_id: root_id,
+            ..self.clone()
+        }
     }
 
     /// `name` is `None` for the crate's root module
@@ -123,8 +125,10 @@ impl ModuleDescriptor {
     }
 
     /// Returns a `ModuleScope`: a set of items, visible in this module.
-    pub fn scope(&self, db: &impl DescriptorDatabase) -> Cancelable<Arc<ModuleScope>> {
-        db._module_scope(self.source_root_id, self.module_id)
+    pub(crate) fn scope(&self, db: &impl DescriptorDatabase) -> Cancelable<ModuleScope> {
+        let item_map = db._item_map(self.source_root_id)?;
+        let res = item_map.per_module[&self.module_id].clone();
+        Ok(res)
     }
 
     pub fn problems(&self, db: &impl DescriptorDatabase) -> Vec<(SyntaxNode, Problem)> {
@@ -146,6 +150,13 @@ pub(crate) struct ModuleTree {
 }
 
 impl ModuleTree {
+    fn modules<'a>(&'a self) -> impl Iterator<Item = ModuleId> + 'a {
+        self.mods
+            .iter()
+            .enumerate()
+            .map(|(idx, _)| ModuleId(idx as u32))
+    }
+
     fn modules_for_source(&self, source: ModuleSource) -> Vec<ModuleId> {
         self.mods
             .iter()
@@ -204,6 +215,11 @@ impl ModuleId {
         let link = self.parent_link(tree)?;
         Some(tree.link(link).owner)
     }
+    fn crate_root(self, tree: &ModuleTree) -> ModuleId {
+        generate(Some(self), move |it| it.parent(tree))
+            .last()
+            .unwrap()
+    }
     fn child(self, tree: &ModuleTree, name: &str) -> Option<ModuleId> {
         let link = tree
             .module(self)
@@ -213,6 +229,13 @@ impl ModuleId {
             .find(|it| it.name == name)?;
         Some(*link.points_to.first()?)
     }
+    fn children<'a>(self, tree: &'a ModuleTree) -> impl Iterator<Item = (SmolStr, ModuleId)> + 'a {
+        tree.module(self).children.iter().filter_map(move |&it| {
+            let link = tree.link(it);
+            let module = *link.points_to.first()?;
+            Some((link.name.clone(), module))
+        })
+    }
     fn problems(self, tree: &ModuleTree, db: &impl SyntaxDatabase) -> Vec<(SyntaxNode, Problem)> {
         tree.module(self)
             .children
diff --git a/crates/ra_analysis/src/descriptors/module/nameres.rs b/crates/ra_analysis/src/descriptors/module/nameres.rs
new file mode 100644
index 000000000..c5bf467ca
--- /dev/null
+++ b/crates/ra_analysis/src/descriptors/module/nameres.rs
@@ -0,0 +1,453 @@
+//! Name resolution algorithm
+use std::{
+    sync::Arc,
+    time::Instant,
+};
+
+use rustc_hash::FxHashMap;
+
+use ra_syntax::{
+    SmolStr, SyntaxKind::{self, *},
+    ast::{self, AstNode, ModuleItemOwner}
+};
+
+use crate::{
+    Cancelable,
+    loc2id::{DefId, DefLoc},
+    descriptors::{
+        DescriptorDatabase,
+        module::{ModuleId, ModuleTree, ModuleSourceNode},
+    },
+    syntax_ptr::{LocalSyntaxPtr},
+    input::SourceRootId,
+};
+
+/// Item map is the result of the name resolution. Item map contains, for each
+/// module, the set of visible items.
+#[derive(Default, Debug, PartialEq, Eq)]
+pub(crate) struct ItemMap {
+    pub(crate) per_module: FxHashMap<ModuleId, ModuleScope>,
+}
+
+#[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
+/// other modules.
+///
+/// This stands in-between raw syntax and name resolution and alow us to avoid
+/// recomputing name res: if `InputModuleItems` are the same, we can avoid
+/// running name resolution.
+#[derive(Debug, Default, PartialEq, Eq)]
+pub(crate) struct InputModuleItems {
+    items: Vec<ModuleItem>,
+    glob_imports: Vec<Path>,
+    imports: Vec<Path>,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+struct Path {
+    kind: PathKind,
+    segments: Vec<(LocalSyntaxPtr, SmolStr)>,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+enum PathKind {
+    Abs,
+    Self_,
+    Super,
+    Crate,
+}
+
+pub(crate) fn input_module_items(
+    db: &impl DescriptorDatabase,
+    source_root: SourceRootId,
+    module_id: ModuleId,
+) -> Cancelable<Arc<InputModuleItems>> {
+    let module_tree = db._module_tree(source_root)?;
+    let source = module_id.source(&module_tree);
+    let res = match source.resolve(db) {
+        ModuleSourceNode::SourceFile(it) => {
+            let items = it.borrowed().items();
+            InputModuleItems::new(items)
+        }
+        ModuleSourceNode::Module(it) => {
+            let items = it
+                .borrowed()
+                .item_list()
+                .into_iter()
+                .flat_map(|it| it.items());
+            InputModuleItems::new(items)
+        }
+    };
+    Ok(Arc::new(res))
+}
+
+pub(crate) fn item_map(
+    db: &impl DescriptorDatabase,
+    source_root: SourceRootId,
+) -> Cancelable<Arc<ItemMap>> {
+    let start = Instant::now();
+    let module_tree = db._module_tree(source_root)?;
+    let input = module_tree
+        .modules()
+        .map(|id| {
+            let items = db._input_module_items(source_root, id)?;
+            Ok((id, items))
+        })
+        .collect::<Cancelable<FxHashMap<_, _>>>()?;
+
+    let mut resolver = Resolver {
+        db: db,
+        input: &input,
+        source_root,
+        module_tree,
+        result: ItemMap::default(),
+    };
+    resolver.resolve()?;
+    let res = resolver.result;
+    let elapsed = start.elapsed();
+    log::info!("item_map: {:?}", elapsed);
+    Ok(Arc::new(res))
+}
+
+/// Resolution is basically `DefId` atm, but it should account for stuff like
+/// multiple namespaces, ambiguity and errors.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub(crate) struct Resolution {
+    /// None for unresolved
+    pub(crate) def_id: Option<DefId>,
+    /// ident by whitch this is imported into local scope.
+    /// TODO: make this offset-independent.
+    pub(crate) import_name: Option<LocalSyntaxPtr>,
+}
+
+// #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
+// enum Namespace {
+//     Types,
+//     Values,
+// }
+
+// #[derive(Debug)]
+// struct PerNs<T> {
+//     types: Option<T>,
+//     values: Option<T>,
+// }
+
+#[derive(Debug, PartialEq, Eq)]
+struct ModuleItem {
+    ptr: LocalSyntaxPtr,
+    name: SmolStr,
+    kind: SyntaxKind,
+    vis: Vis,
+}
+
+#[derive(Debug, PartialEq, Eq)]
+enum Vis {
+    // Priv,
+    Other,
+}
+
+impl InputModuleItems {
+    fn new<'a>(items: impl Iterator<Item = ast::ModuleItem<'a>>) -> InputModuleItems {
+        let mut res = InputModuleItems::default();
+        for item in items {
+            res.add_item(item);
+        }
+        res
+    }
+
+    fn add_item(&mut self, item: ast::ModuleItem) -> Option<()> {
+        match item {
+            ast::ModuleItem::StructDef(it) => self.items.push(ModuleItem::new(it)?),
+            ast::ModuleItem::EnumDef(it) => self.items.push(ModuleItem::new(it)?),
+            ast::ModuleItem::FnDef(it) => self.items.push(ModuleItem::new(it)?),
+            ast::ModuleItem::TraitDef(it) => self.items.push(ModuleItem::new(it)?),
+            ast::ModuleItem::TypeDef(it) => self.items.push(ModuleItem::new(it)?),
+            ast::ModuleItem::ImplItem(_) => {
+                // impls don't define items
+            }
+            ast::ModuleItem::UseItem(it) => self.add_use_item(it),
+            ast::ModuleItem::ExternCrateItem(_) => {
+                // TODO
+            }
+            ast::ModuleItem::ConstDef(it) => self.items.push(ModuleItem::new(it)?),
+            ast::ModuleItem::StaticDef(it) => self.items.push(ModuleItem::new(it)?),
+            ast::ModuleItem::Module(it) => self.items.push(ModuleItem::new(it)?),
+        }
+        Some(())
+    }
+
+    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
+                },
+            };
+            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);
+                }
+            }
+        }
+    }
+}
+
+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();
+        let ptr = LocalSyntaxPtr::new(item.syntax());
+        let kind = item.syntax().kind();
+        let vis = Vis::Other;
+        let res = ModuleItem {
+            ptr,
+            name,
+            kind,
+            vis,
+        };
+        Some(res)
+    }
+}
+
+struct Resolver<'a, DB> {
+    db: &'a DB,
+    input: &'a FxHashMap<ModuleId, Arc<InputModuleItems>>,
+    source_root: SourceRootId,
+    module_tree: Arc<ModuleTree>,
+    result: ItemMap,
+}
+
+impl<'a, DB> Resolver<'a, DB>
+where
+    DB: DescriptorDatabase,
+{
+    fn resolve(&mut self) -> Cancelable<()> {
+        for (&module_id, items) in self.input.iter() {
+            self.populate_module(module_id, items)
+        }
+
+        for &module_id in self.input.keys() {
+            crate::db::check_canceled(self.db)?;
+            self.resolve_imports(module_id);
+        }
+        Ok(())
+    }
+
+    fn populate_module(&mut self, module_id: ModuleId, input: &InputModuleItems) {
+        let file_id = module_id.source(&self.module_tree).file_id();
+
+        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),
+                    },
+                );
+            }
+        }
+
+        for item in input.items.iter() {
+            if item.kind == MODULE {
+                // handle submodules separatelly
+                continue;
+            }
+            let ptr = item.ptr.into_global(file_id);
+            let def_loc = DefLoc::Item { ptr };
+            let def_id = self.db.id_maps().def_id(def_loc);
+            let resolution = Resolution {
+                def_id: Some(def_id),
+                import_name: None,
+            };
+            module_items.items.insert(item.name.clone(), resolution);
+        }
+
+        for (name, mod_id) in module_id.children(&self.module_tree) {
+            let def_loc = DefLoc::Module {
+                id: mod_id,
+                source_root: self.source_root,
+            };
+            let def_id = self.db.id_maps().def_id(def_loc);
+            let resolution = Resolution {
+                def_id: Some(def_id),
+                import_name: None,
+            };
+            module_items.items.insert(name, resolution);
+        }
+
+        self.result.per_module.insert(module_id, module_items);
+    }
+
+    fn resolve_imports(&mut self, module_id: ModuleId) {
+        for import in self.input[&module_id].imports.iter() {
+            self.resolve_import(module_id, import);
+        }
+    }
+
+    fn resolve_import(&mut self, module_id: ModuleId, import: &Path) {
+        let mut curr = match import.kind {
+            // TODO: handle extern crates
+            PathKind::Abs => return,
+            PathKind::Self_ => module_id,
+            PathKind::Super => {
+                match module_id.parent(&self.module_tree) {
+                    Some(it) => it,
+                    // TODO: error
+                    None => return,
+                }
+            }
+            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;
+
+            let def_id = match self.result.per_module[&curr].items.get(name) {
+                None => return,
+                Some(res) => match res.def_id {
+                    Some(it) => it,
+                    None => return,
+                },
+            };
+
+            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,
+                    _ => return,
+                }
+            } else {
+                self.update(module_id, |items| {
+                    let res = Resolution {
+                        def_id: Some(def_id),
+                        import_name: Some(*ptr),
+                    };
+                    items.items.insert(name.clone(), res);
+                })
+            }
+        }
+    }
+
+    fn update(&mut self, module_id: ModuleId, f: impl FnOnce(&mut ModuleScope)) {
+        let module_items = self.result.per_module.get_mut(&module_id).unwrap();
+        f(module_items)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::{
+        mock_analysis::analysis_and_position,
+        descriptors::{DescriptorDatabase, module::ModuleDescriptor},
+        input::FilesDatabase,
+};
+    use super::*;
+
+    fn item_map(fixture: &str) -> (Arc<ItemMap>, ModuleId) {
+        let (analysis, pos) = analysis_and_position(fixture);
+        let db = analysis.imp.db;
+        let source_root = db.file_source_root(pos.file_id);
+        let descr = ModuleDescriptor::guess_from_position(&*db, pos)
+            .unwrap()
+            .unwrap();
+        let module_id = descr.module_id;
+        (db._item_map(source_root).unwrap(), module_id)
+    }
+
+    #[test]
+    fn test_item_map() {
+        let (item_map, module_id) = item_map(
+            "
+            //- /lib.rs
+            mod foo;
+
+            use crate::foo::bar::Baz;
+            <|>
+
+            //- /foo/mod.rs
+            pub mod bar;
+
+            //- /foo/bar.rs
+            pub struct Baz;
+        ",
+        );
+        let name = SmolStr::from("Baz");
+        let resolution = &item_map.per_module[&module_id].items[&name];
+        assert!(resolution.def_id.is_some());
+    }
+}
diff --git a/crates/ra_analysis/src/descriptors/module/scope.rs b/crates/ra_analysis/src/descriptors/module/scope.rs
deleted file mode 100644
index 4490228e4..000000000
--- a/crates/ra_analysis/src/descriptors/module/scope.rs
+++ /dev/null
@@ -1,124 +0,0 @@
-//! Backend for module-level scope resolution & completion
-
-use ra_syntax::{ast, AstNode, SmolStr};
-
-use crate::syntax_ptr::LocalSyntaxPtr;
-
-/// `ModuleScope` contains all named items declared in the scope.
-#[derive(Debug, PartialEq, Eq)]
-pub(crate) struct ModuleScope {
-    entries: Vec<Entry>,
-}
-
-/// `Entry` is a single named declaration iside a module.
-#[derive(Debug, PartialEq, Eq)]
-pub(crate) struct Entry {
-    ptr: LocalSyntaxPtr,
-    kind: EntryKind,
-    name: SmolStr,
-}
-
-#[derive(Debug, PartialEq, Eq)]
-enum EntryKind {
-    Item,
-    Import,
-}
-
-impl ModuleScope {
-    pub(super) fn new<'a>(items: impl Iterator<Item = ast::ModuleItem<'a>>) -> ModuleScope {
-        let mut entries = Vec::new();
-        for item in items {
-            let entry = match item {
-                ast::ModuleItem::StructDef(item) => Entry::new(item),
-                ast::ModuleItem::EnumDef(item) => Entry::new(item),
-                ast::ModuleItem::FnDef(item) => Entry::new(item),
-                ast::ModuleItem::ConstDef(item) => Entry::new(item),
-                ast::ModuleItem::StaticDef(item) => Entry::new(item),
-                ast::ModuleItem::TraitDef(item) => Entry::new(item),
-                ast::ModuleItem::TypeDef(item) => Entry::new(item),
-                ast::ModuleItem::Module(item) => Entry::new(item),
-                ast::ModuleItem::UseItem(item) => {
-                    if let Some(tree) = item.use_tree() {
-                        collect_imports(tree, &mut entries);
-                    }
-                    continue;
-                }
-                ast::ModuleItem::ExternCrateItem(_) | ast::ModuleItem::ImplItem(_) => continue,
-            };
-            entries.extend(entry)
-        }
-
-        ModuleScope { entries }
-    }
-
-    pub fn entries(&self) -> &[Entry] {
-        self.entries.as_slice()
-    }
-}
-
-impl Entry {
-    fn new<'a>(item: impl ast::NameOwner<'a>) -> Option<Entry> {
-        let name = item.name()?;
-        Some(Entry {
-            name: name.text(),
-            ptr: LocalSyntaxPtr::new(name.syntax()),
-            kind: EntryKind::Item,
-        })
-    }
-    fn new_import(path: ast::Path) -> Option<Entry> {
-        let name_ref = path.segment()?.name_ref()?;
-        Some(Entry {
-            name: name_ref.text(),
-            ptr: LocalSyntaxPtr::new(name_ref.syntax()),
-            kind: EntryKind::Import,
-        })
-    }
-    pub fn name(&self) -> &SmolStr {
-        &self.name
-    }
-    pub fn ptr(&self) -> LocalSyntaxPtr {
-        self.ptr
-    }
-}
-
-fn collect_imports(tree: ast::UseTree, acc: &mut Vec<Entry>) {
-    if let Some(use_tree_list) = tree.use_tree_list() {
-        return use_tree_list
-            .use_trees()
-            .for_each(|it| collect_imports(it, acc));
-    }
-    if let Some(path) = tree.path() {
-        acc.extend(Entry::new_import(path));
-    }
-}
-
-#[cfg(test)]
-mod tests {
-    use super::*;
-    use ra_syntax::{ast::ModuleItemOwner, SourceFileNode};
-
-    fn do_check(code: &str, expected: &[&str]) {
-        let file = SourceFileNode::parse(&code);
-        let scope = ModuleScope::new(file.ast().items());
-        let actual = scope.entries.iter().map(|it| it.name()).collect::<Vec<_>>();
-        assert_eq!(expected, actual.as_slice());
-    }
-
-    #[test]
-    fn test_module_scope() {
-        do_check(
-            "
-            struct Foo;
-            enum Bar {}
-            mod baz {}
-            fn quux() {}
-            use x::{
-                y::z,
-                t,
-            };
-            type T = ();
-        ",
-            &["Foo", "Bar", "baz", "quux", "z", "t", "T"],
-        )
-    }
-}
diff --git a/crates/ra_analysis/src/loc2id.rs b/crates/ra_analysis/src/loc2id.rs
index 8c297156a..e4b55f9b0 100644
--- a/crates/ra_analysis/src/loc2id.rs
+++ b/crates/ra_analysis/src/loc2id.rs
@@ -8,7 +8,9 @@ use std::{
 use rustc_hash::FxHashMap;
 
 use crate::{
+    descriptors::module::ModuleId,
     syntax_ptr::SyntaxPtr,
+    input::SourceRootId,
 };
 
 /// There are two principle ways to refer to things:
@@ -89,6 +91,21 @@ macro_rules! impl_numeric_id {
 pub(crate) struct FnId(u32);
 impl_numeric_id!(FnId);
 
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub(crate) struct DefId(u32);
+impl_numeric_id!(DefId);
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub(crate) enum DefLoc {
+    Module {
+        id: ModuleId,
+        source_root: SourceRootId,
+    },
+    Item {
+        ptr: SyntaxPtr,
+    },
+}
+
 pub(crate) trait IdDatabase: salsa::Database {
     fn id_maps(&self) -> &IdMaps;
 }
@@ -105,9 +122,17 @@ impl IdMaps {
     pub(crate) fn fn_ptr(&self, fn_id: FnId) -> SyntaxPtr {
         self.inner.fns.lock().id2loc(fn_id)
     }
+
+    pub(crate) fn def_id(&self, loc: DefLoc) -> DefId {
+        self.inner.defs.lock().loc2id(&loc)
+    }
+    pub(crate) fn def_loc(&self, def_id: DefId) -> DefLoc {
+        self.inner.defs.lock().id2loc(def_id)
+    }
 }
 
 #[derive(Debug, Default)]
 struct IdMapsInner {
     fns: Mutex<Loc2IdMap<SyntaxPtr, FnId>>,
+    defs: Mutex<Loc2IdMap<DefLoc, DefId>>,
 }
diff --git a/crates/ra_analysis/tests/tests.rs b/crates/ra_analysis/tests/tests.rs
index 719c166b5..72b2ebf97 100644
--- a/crates/ra_analysis/tests/tests.rs
+++ b/crates/ra_analysis/tests/tests.rs
@@ -447,8 +447,8 @@ fn test_complete_crate_path() {
     );
     let completions = analysis.completions(position).unwrap().unwrap();
     assert_eq_dbg(
-        r#"[CompletionItem { label: "foo", lookup: None, snippet: None },
-            CompletionItem { label: "Spam", lookup: None, snippet: None }]"#,
+        r#"[CompletionItem { label: "Spam", lookup: None, snippet: None },
+            CompletionItem { label: "foo", lookup: None, snippet: None }]"#,
         &completions,
     );
 }
@@ -466,8 +466,8 @@ fn test_complete_crate_path_with_braces() {
     );
     let completions = analysis.completions(position).unwrap().unwrap();
     assert_eq_dbg(
-        r#"[CompletionItem { label: "foo", lookup: None, snippet: None },
-            CompletionItem { label: "Spam", lookup: None, snippet: None }]"#,
+        r#"[CompletionItem { label: "Spam", lookup: None, snippet: None },
+            CompletionItem { label: "foo", lookup: None, snippet: None }]"#,
         &completions,
     );
 }
diff --git a/crates/ra_syntax/src/ast/mod.rs b/crates/ra_syntax/src/ast/mod.rs
index 7077e3492..91c67119f 100644
--- a/crates/ra_syntax/src/ast/mod.rs
+++ b/crates/ra_syntax/src/ast/mod.rs
@@ -315,6 +315,12 @@ impl<'a> PathSegment<'a> {
     }
 }
 
+impl<'a> UseTree<'a> {
+    pub fn has_star(self) -> bool {
+        self.syntax().children().any(|it| it.kind() == STAR)
+    }
+}
+
 impl<'a> UseTreeList<'a> {
     pub fn parent_use_tree(self) -> UseTree<'a> {
         self.syntax()
diff --git a/crates/tools/src/lib.rs b/crates/tools/src/lib.rs
index 8b8e9974e..e81761cf2 100644
--- a/crates/tools/src/lib.rs
+++ b/crates/tools/src/lib.rs
@@ -17,7 +17,7 @@ pub type Result<T> = ::std::result::Result<T, failure::Error>;
 pub const GRAMMAR: &str = "crates/ra_syntax/src/grammar.ron";
 pub const SYNTAX_KINDS: &str = "crates/ra_syntax/src/syntax_kinds/generated.rs.tera";
 pub const AST: &str = "crates/ra_syntax/src/ast/generated.rs.tera";
-const TOOLCHAIN: &str = "beta-2018-10-30";
+const TOOLCHAIN: &str = "beta-2018-11-19";
 
 #[derive(Debug)]
 pub struct Test {