3 files changed, 163 insertions, 0 deletions

diff --git a/crates/ra_analysis/src/descriptors/module/mod.rs b/crates/ra_analysis/src/descriptors/module/mod.rs
index 091c150e5..958487541 100644
--- a/crates/ra_analysis/src/descriptors/module/mod.rs
+++ b/crates/ra_analysis/src/descriptors/module/mod.rs
@@ -1,5 +1,6 @@
 pub(super) mod imp;
 mod scope;
+mod nameres;
 
 use std::sync::Arc;
 
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..137aa8b17
--- /dev/null
+++ b/crates/ra_analysis/src/descriptors/module/nameres.rs
@@ -0,0 +1,156 @@
+//! Name resolution algorithm
+use rustc_hash::FxHashMap;
+
+use ra_syntax::{
+    SmolStr, SyntaxKind,
+    ast::{self, NameOwner}
+};
+
+use crate::{
+    descriptors::module::ModuleId,
+    syntax_ptr::LocalSyntaxPtr,
+};
+
+/// 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)]
+struct InputModuleItems {
+    items: Vec<ModuleItem>,
+    glob_imports: Vec<Path>,
+    imports: Vec<Path>,
+}
+
+#[derive(Debug, Clone)]
+struct Path {
+    kind: PathKind,
+    segments: Vec<SmolStr>,
+}
+
+#[derive(Debug, Clone, Copy)]
+enum PathKind {
+    Abs,
+    Self_,
+    Super,
+    Crate,
+}
+
+#[derive(Debug)]
+struct ItemMap {
+    per_module: FxHashMap<ModuleId, ModuleItems>,
+}
+
+#[derive(Debug)]
+struct ModuleItems {
+    items: FxHashMap<SmolStr, PerNs<ModuleItem>>,
+}
+
+#[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)]
+struct ModuleItem {
+    ptr: LocalSyntaxPtr,
+    name: SmolStr,
+    kind: SyntaxKind,
+    vis: Vis,
+}
+
+#[derive(Debug)]
+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(it) => {
+                // impls don't define items
+            }
+            ast::ModuleItem::UseItem(it) => self.add_use_item(it),
+            ast::ModuleItem::ExternCrateItem(it) => (),
+            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> {
+    prefix
+}
+
+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)
+    }
+}
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()