add skeleton for macro-aware name resolutions

8 files changed, 773 insertions, 9 deletions

diff --git a/crates/ra_db/src/input.rs b/crates/ra_db/src/input.rs
index e45a510b3..2b1001d48 100644
--- a/crates/ra_db/src/input.rs
+++ b/crates/ra_db/src/input.rs
@@ -124,6 +124,10 @@ impl CrateGraph {
         self.arena.is_empty()
     }
 
+    pub fn iter<'a>(&'a self) -> impl Iterator<Item = CrateId> + 'a {
+        self.arena.keys().map(|it| *it)
+    }
+
     pub fn crate_root(&self, crate_id: CrateId) -> FileId {
         self.arena[&crate_id].file_id
     }
diff --git a/crates/ra_hir/src/ids.rs b/crates/ra_hir/src/ids.rs
index 5b00330c6..e805ddcba 100644
--- a/crates/ra_hir/src/ids.rs
+++ b/crates/ra_hir/src/ids.rs
@@ -200,8 +200,14 @@ pub(crate) trait AstItemDef<N: AstNode>: ArenaId + Clone {
     fn interner(interner: &HirInterner) -> &LocationIntener<ItemLoc<N>, Self>;
     fn from_ast(ctx: LocationCtx<&impl PersistentHirDatabase>, ast: &N) -> Self {
         let items = ctx.db.file_items(ctx.file_id);
-        let raw =
-            SourceItemId { file_id: ctx.file_id, item_id: items.id_of(ctx.file_id, ast.syntax()) };
+        let item_id = items.id_of(ctx.file_id, ast.syntax());
+        Self::from_source_item_id_unchecked(ctx, item_id)
+    }
+    fn from_source_item_id_unchecked(
+        ctx: LocationCtx<&impl PersistentHirDatabase>,
+        item_id: SourceFileItemId,
+    ) -> Self {
+        let raw = SourceItemId { file_id: ctx.file_id, item_id };
         let loc = ItemLoc { module: ctx.module, raw, _ty: PhantomData };
 
         Self::interner(ctx.db.as_ref()).loc2id(&loc)
@@ -309,9 +315,7 @@ impl SourceFileItems {
         file_id: HirFileId,
     ) -> Arc<SourceFileItems> {
         let source_file = db.hir_parse(file_id);
-        let mut res = SourceFileItems { file_id, arena: Arena::default() };
-        res.init(&source_file);
-        Arc::new(res)
+        Arc::new(SourceFileItems::from_source_file(&source_file, file_id))
     }
 
     pub(crate) fn file_item_query(
@@ -324,18 +328,23 @@ impl SourceFileItems {
             .to_owned()
     }
 
-    fn init(&mut self, source_file: &SourceFile) {
+    pub(crate) fn from_source_file(
+        source_file: &SourceFile,
+        file_id: HirFileId,
+    ) -> SourceFileItems {
+        let mut res = SourceFileItems { file_id, arena: Arena::default() };
         // By walking the tree in bread-first order we make sure that parents
         // get lower ids then children. That is, adding a new child does not
         // change parent's id. This means that, say, adding a new function to a
         // trait does not change ids of top-level items, which helps caching.
         bfs(source_file.syntax(), |it| {
             if let Some(module_item) = ast::ModuleItem::cast(it) {
-                self.alloc(module_item.syntax());
+                res.alloc(module_item.syntax());
             } else if let Some(macro_call) = ast::MacroCall::cast(it) {
-                self.alloc(macro_call.syntax());
+                res.alloc(macro_call.syntax());
             }
-        })
+        });
+        res
     }
 
     fn alloc(&mut self, item: &SyntaxNode) -> SourceFileItemId {
diff --git a/crates/ra_hir/src/module_tree.rs b/crates/ra_hir/src/module_tree.rs
index 99c2115e1..4d0f40e85 100644
--- a/crates/ra_hir/src/module_tree.rs
+++ b/crates/ra_hir/src/module_tree.rs
@@ -289,6 +289,15 @@ impl LinkId {
     }
 }
 
+pub(crate) fn resolve_module_declaration(
+    db: &impl PersistentHirDatabase,
+    file_id: HirFileId,
+    name: &Name,
+    is_root: bool,
+) -> Option<FileId> {
+    resolve_submodule(db, file_id, name, is_root).0.first().map(|it| *it)
+}
+
 fn resolve_submodule(
     db: &impl PersistentHirDatabase,
     file_id: HirFileId,
diff --git a/crates/ra_hir/src/name.rs b/crates/ra_hir/src/name.rs
index 8d786d2ac..06bafa6f0 100644
--- a/crates/ra_hir/src/name.rs
+++ b/crates/ra_hir/src/name.rs
@@ -64,6 +64,7 @@ impl Name {
             "str" => KnownName::Str,
             "Self" => KnownName::SelfType,
             "self" => KnownName::SelfParam,
+            "macro_rules" => KnownName::MacroRules,
             _ => return None,
         };
         Some(name)
@@ -122,4 +123,6 @@ pub(crate) enum KnownName {
 
     SelfType,
     SelfParam,
+
+    MacroRules,
 }
diff --git a/crates/ra_hir/src/nameres.rs b/crates/ra_hir/src/nameres.rs
index 73919ee37..6f98ac071 100644
--- a/crates/ra_hir/src/nameres.rs
+++ b/crates/ra_hir/src/nameres.rs
@@ -15,6 +15,7 @@
 //! so that the results of name resolution can be preserved unless the module
 //! structure itself is modified.
 pub(crate) mod lower;
+mod crate_def_map;
 
 use std::{time, sync::Arc};
 
diff --git a/crates/ra_hir/src/nameres/crate_def_map.rs b/crates/ra_hir/src/nameres/crate_def_map.rs
new file mode 100644
index 000000000..ea9b4fb50
--- /dev/null
+++ b/crates/ra_hir/src/nameres/crate_def_map.rs
@@ -0,0 +1,204 @@
+/// This module implements new import-resolution/macro expansion algorithm.
+///
+/// The result of this module is `CrateDefMap`: a datastructure which contains:
+///
+///   * a tree of modules for the crate
+///   * for each module, a set of items visible in the module (directly declared
+///     or imported)
+///
+/// Note that `CrateDefMap` contains fully macro expanded code.
+///
+/// Computing `CrateDefMap` can be partitioned into several logically
+/// independent "phases". The phases are mutually recursive though, there's no
+/// stric ordering.
+///
+/// ## Collecting RawItems
+///
+///  This happens in the `raw` module, which parses a single source file into a
+///  set of top-level items. Nested importa are desugared to flat imports in
+///  this phase. Macro calls are represented as a triple of (Path, Option<Name>,
+///  TokenTree).
+///
+/// ## Collecting Modules
+///
+/// This happens in the `collector` module. In this phase, we recursively walk
+/// tree of modules, collect raw items from submodules, populate module scopes
+/// with defined items (so, we assign item ids in this phase) and record the set
+/// of unresovled imports and macros.
+///
+/// While we walk tree of modules, we also record macro_rules defenitions and
+/// expand calls to macro_rules defined macros.
+///
+/// ## Resolving Imports
+///
+/// TBD
+///
+/// ## Resolving Macros
+///
+/// While macro_rules from the same crate use a global mutable namespace, macros
+/// from other crates (including proc-macros) can be used with `foo::bar!`
+/// syntax.
+///
+/// TBD;
+mod raw;
+mod collector;
+
+use rustc_hash::FxHashMap;
+use ra_arena::{Arena};
+
+use crate::{
+    Name,
+    module_tree::ModuleId,
+    nameres::ModuleScope,
+};
+
+#[derive(Default, Debug)]
+struct ModuleData {
+    parent: Option<ModuleId>,
+    children: FxHashMap<Name, ModuleId>,
+    scope: ModuleScope,
+}
+
+/// Contans all top-level defs from a macro-expanded crate
+#[derive(Debug)]
+pub(crate) struct CrateDefMap {
+    root: ModuleId,
+    modules: Arena<ModuleId, ModuleData>,
+}
+
+#[cfg(test)]
+mod tests {
+    use std::sync::Arc;
+
+    use ra_db::SourceDatabase;
+    use insta::assert_snapshot_matches;
+
+    use crate::{Crate, mock::MockDatabase, nameres::Resolution};
+
+    use super::*;
+
+    fn compute_crate_def_map(fixture: &str) -> Arc<CrateDefMap> {
+        let db = MockDatabase::with_files(fixture);
+        let crate_id = db.crate_graph().iter().next().unwrap();
+        let krate = Crate { crate_id };
+        collector::crate_def_map_query(&db, krate)
+    }
+
+    fn render_crate_def_map(map: &CrateDefMap) -> String {
+        let mut buf = String::new();
+        go(&mut buf, map, "\ncrate", map.root);
+        return buf;
+
+        fn go(buf: &mut String, map: &CrateDefMap, path: &str, module: ModuleId) {
+            *buf += path;
+            *buf += "\n";
+            for (name, res) in map.modules[module].scope.items.iter() {
+                *buf += &format!("{}: {}\n", name, dump_resolution(res))
+            }
+            for (name, child) in map.modules[module].children.iter() {
+                let path = path.to_string() + &format!("::{}", name);
+                go(buf, map, &path, *child);
+            }
+        }
+
+        fn dump_resolution(resolution: &Resolution) -> &'static str {
+            match (resolution.def.types.is_some(), resolution.def.values.is_some()) {
+                (true, true) => "t v",
+                (true, false) => "t",
+                (false, true) => "v",
+                (false, false) => "_",
+            }
+        }
+    }
+
+    fn def_map(fixtute: &str) -> String {
+        let dm = compute_crate_def_map(fixtute);
+        render_crate_def_map(&dm)
+    }
+
+    #[test]
+    fn crate_def_map_smoke_test() {
+        let map = def_map(
+            "
+            //- /lib.rs
+            mod foo;
+            struct S;
+
+            //- /foo/mod.rs
+            pub mod bar;
+            fn f() {}
+
+            //- /foo/bar.rs
+            pub struct Baz;
+            enum E { V }
+        ",
+        );
+        assert_snapshot_matches!(
+        map,
+            @r###"
+crate
+S: t v
+
+crate::foo
+f: v
+
+crate::foo::bar
+Baz: t v
+E: t
+"###
+        )
+    }
+
+    #[test]
+    fn macro_rules_are_globally_visible() {
+        let map = def_map(
+            "
+            //- /lib.rs
+            macro_rules! structs {
+                ($($i:ident),*) => {
+                    $(struct $i { field: u32 } )*
+                }
+            }
+            structs!(Foo);
+            mod nested;
+
+            //- /nested.rs
+            structs!(Bar, Baz);
+        ",
+        );
+        assert_snapshot_matches!(map, @r###"
+crate
+Foo: t v
+
+crate::nested
+Bar: t v
+Baz: t v
+"###);
+    }
+
+    #[test]
+    fn macro_rules_can_define_modules() {
+        let map = def_map(
+            "
+            //- /lib.rs
+            macro_rules! m {
+                ($name:ident) => { mod $name;  }
+            }
+            m!(n1);
+
+            //- /n1.rs
+            m!(n2)
+            //- /n1/n2.rs
+            struct X;
+        ",
+        );
+        assert_snapshot_matches!(map, @r###"
+crate
+
+crate::n1
+
+crate::n1::n2
+X: t v
+"###);
+    }
+}
diff --git a/crates/ra_hir/src/nameres/crate_def_map/collector.rs b/crates/ra_hir/src/nameres/crate_def_map/collector.rs
new file mode 100644
index 000000000..46bef3dbe
--- /dev/null
+++ b/crates/ra_hir/src/nameres/crate_def_map/collector.rs
@@ -0,0 +1,256 @@
+use std::sync::Arc;
+
+use rustc_hash::FxHashMap;
+use ra_arena::Arena;
+
+use crate::{
+    Function, Module, Struct, Enum, Const, Static, Trait, TypeAlias,
+    Crate, PersistentHirDatabase, HirFileId, Name, Path,
+    KnownName,
+    nameres::{Resolution, PerNs, ModuleDef, ReachedFixedPoint},
+    ids::{AstItemDef, LocationCtx, MacroCallLoc, SourceItemId, MacroCallId},
+    module_tree::resolve_module_declaration,
+};
+
+use super::{CrateDefMap, ModuleId, ModuleData, raw};
+
+#[allow(unused)]
+pub(crate) fn crate_def_map_query(
+    db: &impl PersistentHirDatabase,
+    krate: Crate,
+) -> Arc<CrateDefMap> {
+    let mut modules: Arena<ModuleId, ModuleData> = Arena::default();
+    let root = modules.alloc(ModuleData::default());
+    let mut collector = DefCollector {
+        db,
+        krate,
+        def_map: CrateDefMap { modules, root },
+        unresolved_imports: Vec::new(),
+        unexpanded_macros: Vec::new(),
+        global_macro_scope: FxHashMap::default(),
+    };
+    collector.collect();
+    let def_map = collector.finish();
+    Arc::new(def_map)
+}
+
+/// Walks the tree of module recursively
+struct DefCollector<DB> {
+    db: DB,
+    krate: Crate,
+    def_map: CrateDefMap,
+    unresolved_imports: Vec<(ModuleId, raw::Import)>,
+    unexpanded_macros: Vec<(ModuleId, MacroCallId, tt::Subtree)>,
+    global_macro_scope: FxHashMap<Name, mbe::MacroRules>,
+}
+
+/// Walks a single module, populating defs, imports and macros
+struct ModCollector<'a, D> {
+    def_collector: D,
+    module_id: ModuleId,
+    file_id: HirFileId,
+    raw_items: &'a raw::RawItems,
+}
+
+impl<'a, DB> DefCollector<&'a DB>
+where
+    DB: PersistentHirDatabase,
+{
+    fn collect(&mut self) {
+        let crate_graph = self.db.crate_graph();
+        let file_id = crate_graph.crate_root(self.krate.crate_id());
+        let raw_items = raw::RawItems::raw_items_query(self.db, file_id);
+        let module_id = self.def_map.root;
+        ModCollector {
+            def_collector: &mut *self,
+            module_id,
+            file_id: file_id.into(),
+            raw_items: &raw_items,
+        }
+        .collect(raw_items.items());
+
+        // main name resolution fixed-point loop.
+        let mut i = 0;
+        loop {
+            match (self.resolve_imports(), self.resolve_macros()) {
+                (ReachedFixedPoint::Yes, ReachedFixedPoint::Yes) => break,
+                _ => i += 1,
+            }
+            if i == 1000 {
+                log::error!("diverging name resolution");
+                break;
+            }
+        }
+    }
+
+    fn define_macro(&mut self, name: Name, tt: &tt::Subtree) {
+        if let Ok(rules) = mbe::MacroRules::parse(tt) {
+            self.global_macro_scope.insert(name, rules);
+        }
+    }
+
+    fn alloc_module(&mut self) -> ModuleId {
+        self.def_map.modules.alloc(ModuleData::default())
+    }
+
+    fn resolve_imports(&mut self) -> ReachedFixedPoint {
+        // Resolves imports, filling-in module scopes
+        ReachedFixedPoint::Yes
+    }
+
+    fn resolve_macros(&mut self) -> ReachedFixedPoint {
+        // Resolve macros, calling into `expand_macro` to actually do the
+        // expansion.
+        ReachedFixedPoint::Yes
+    }
+
+    #[allow(unused)]
+    fn expand_macro(&mut self, idx: usize, rules: &mbe::MacroRules) {
+        let (module_id, call_id, arg) = self.unexpanded_macros.swap_remove(idx);
+        if let Ok(tt) = rules.expand(&arg) {
+            self.collect_macro_expansion(module_id, call_id, tt);
+        }
+    }
+
+    fn collect_macro_expansion(
+        &mut self,
+        module_id: ModuleId,
+        macro_call_id: MacroCallId,
+        expansion: tt::Subtree,
+    ) {
+        // XXX: this **does not** go through a database, because we can't
+        // identify macro_call without adding the whole state of name resolution
+        // as a parameter to the query.
+        //
+        // So, we run the queries "manually" and we must ensure that
+        // `db.hir_parse(macro_call_id)` returns the same source_file.
+        let file_id: HirFileId = macro_call_id.into();
+        let source_file = mbe::token_tree_to_ast_item_list(&expansion);
+
+        let raw_items = raw::RawItems::from_source_file(&source_file, file_id);
+        ModCollector { def_collector: &mut *self, file_id, module_id, raw_items: &raw_items }
+            .collect(raw_items.items())
+    }
+
+    fn finish(self) -> CrateDefMap {
+        self.def_map
+    }
+}
+
+impl<DB> ModCollector<'_, &'_ mut DefCollector<&'_ DB>>
+where
+    DB: PersistentHirDatabase,
+{
+    fn collect(&mut self, items: &[raw::RawItem]) {
+        for item in items {
+            match *item {
+                raw::RawItem::Module(m) => self.collect_module(&self.raw_items[m]),
+                raw::RawItem::Import(import) => {
+                    self.def_collector.unresolved_imports.push((self.module_id, import))
+                }
+                raw::RawItem::Def(def) => self.define_def(&self.raw_items[def]),
+                raw::RawItem::Macro(mac) => self.collect_macro(&self.raw_items[mac]),
+            }
+        }
+    }
+
+    fn collect_module(&mut self, module: &raw::ModuleData) {
+        match module {
+            // inline module, just recurse
+            raw::ModuleData::Definition { name, items } => {
+                let module_id = self.push_child_module(name.clone());
+                ModCollector {
+                    def_collector: &mut *self.def_collector,
+                    module_id,
+                    file_id: self.file_id,
+                    raw_items: self.raw_items,
+                }
+                .collect(&*items);
+            }
+            // out of line module, resovle, parse and recurse
+            raw::ModuleData::Declaration { name } => {
+                let module_id = self.push_child_module(name.clone());
+                let is_root = self.def_collector.def_map.modules[self.module_id].parent.is_none();
+                if let Some(file_id) =
+                    resolve_module_declaration(self.def_collector.db, self.file_id, name, is_root)
+                {
+                    let raw_items = raw::RawItems::raw_items_query(self.def_collector.db, file_id);
+                    ModCollector {
+                        def_collector: &mut *self.def_collector,
+                        module_id,
+                        file_id: file_id.into(),
+                        raw_items: &raw_items,
+                    }
+                    .collect(raw_items.items())
+                }
+            }
+        }
+    }
+
+    fn push_child_module(&mut self, name: Name) -> ModuleId {
+        let res = self.def_collector.alloc_module();
+        self.def_collector.def_map.modules[res].parent = Some(self.module_id);
+        self.def_collector.def_map.modules[self.module_id].children.insert(name, res);
+        res
+    }
+
+    fn define_def(&mut self, def: &raw::DefData) {
+        let module = Module { krate: self.def_collector.krate, module_id: self.module_id };
+        let ctx = LocationCtx::new(self.def_collector.db, module, self.file_id.into());
+        macro_rules! id {
+            () => {
+                AstItemDef::from_source_item_id_unchecked(ctx, def.source_item_id)
+            };
+        }
+        let name = def.name.clone();
+        let def: PerNs<ModuleDef> = match def.kind {
+            raw::DefKind::Function => PerNs::values(Function { id: id!() }.into()),
+            raw::DefKind::Struct => {
+                let s = Struct { id: id!() }.into();
+                PerNs::both(s, s)
+            }
+            raw::DefKind::Enum => PerNs::types(Enum { id: id!() }.into()),
+            raw::DefKind::Const => PerNs::values(Const { id: id!() }.into()),
+            raw::DefKind::Static => PerNs::values(Static { id: id!() }.into()),
+            raw::DefKind::Trait => PerNs::types(Trait { id: id!() }.into()),
+            raw::DefKind::TypeAlias => PerNs::types(TypeAlias { id: id!() }.into()),
+        };
+        let resolution = Resolution { def, import: None };
+        self.def_collector.def_map.modules[self.module_id].scope.items.insert(name, resolution);
+    }
+
+    fn collect_macro(&mut self, mac: &raw::MacroData) {
+        // Case 1: macro rules, define a macro in crate-global mutable scope
+        if is_macro_rules(&mac.path) {
+            if let Some(name) = &mac.name {
+                self.def_collector.define_macro(name.clone(), &mac.arg)
+            }
+            return;
+        }
+
+        let source_item_id = SourceItemId { file_id: self.file_id, item_id: mac.source_item_id };
+        let macro_call_id = MacroCallLoc {
+            module: Module { krate: self.def_collector.krate, module_id: self.module_id },
+            source_item_id,
+        }
+        .id(self.def_collector.db);
+
+        // Case 2: try to expand macro_rules from this crate, triggering
+        // recursive item collection.
+        if let Some(rules) =
+            mac.path.as_ident().and_then(|name| self.def_collector.global_macro_scope.get(name))
+        {
+            if let Ok(tt) = rules.expand(&mac.arg) {
+                self.def_collector.collect_macro_expansion(self.module_id, macro_call_id, tt);
+            }
+            return;
+        }
+
+        // Case 3: path to a macro from another crate, expand during name resolution
+        self.def_collector.unexpanded_macros.push((self.module_id, macro_call_id, mac.arg.clone()))
+    }
+}
+
+fn is_macro_rules(path: &Path) -> bool {
+    path.as_ident().and_then(Name::as_known_name) == Some(KnownName::MacroRules)
+}
diff --git a/crates/ra_hir/src/nameres/crate_def_map/raw.rs b/crates/ra_hir/src/nameres/crate_def_map/raw.rs
new file mode 100644
index 000000000..cec2484eb
--- /dev/null
+++ b/crates/ra_hir/src/nameres/crate_def_map/raw.rs
@@ -0,0 +1,278 @@
+use std::{
+    sync::Arc,
+    ops::Index,
+};
+
+use ra_db::FileId;
+use ra_arena::{Arena, impl_arena_id, RawId};
+use ra_syntax::{
+    AstNode, SourceFile,
+    ast::{self, NameOwner, AttrsOwner},
+};
+
+use crate::{
+    PersistentHirDatabase, Name, AsName, Path, HirFileId,
+    ids::{SourceFileItemId, SourceFileItems},
+};
+
+#[derive(Default, PartialEq, Eq)]
+pub(crate) struct RawItems {
+    modules: Arena<Module, ModuleData>,
+    imports: Arena<Import, ImportData>,
+    defs: Arena<Def, DefData>,
+    macros: Arena<Macro, MacroData>,
+    /// items for top-level module
+    items: Vec<RawItem>,
+}
+
+impl RawItems {
+    pub(crate) fn items(&self) -> &[RawItem] {
+        &self.items
+    }
+
+    pub(crate) fn raw_items_query(db: &impl PersistentHirDatabase, file_id: FileId) -> RawItems {
+        let mut collector = RawItemsCollector {
+            raw_items: RawItems::default(),
+            source_file_items: db.file_items(file_id.into()),
+        };
+        let source_file = db.parse(file_id);
+        collector.process_module(None, &*source_file);
+        collector.raw_items
+    }
+
+    // We can't use queries during name resolution for fear of cycles, so this
+    // is a query-less variant of the above function.
+    pub(crate) fn from_source_file(source_file: &SourceFile, file_id: HirFileId) -> RawItems {
+        let source_file_items = SourceFileItems::from_source_file(source_file, file_id);
+        let mut collector = RawItemsCollector {
+            raw_items: RawItems::default(),
+            source_file_items: Arc::new(source_file_items),
+        };
+        collector.process_module(None, &*source_file);
+        collector.raw_items
+    }
+}
+
+impl Index<Module> for RawItems {
+    type Output = ModuleData;
+    fn index(&self, idx: Module) -> &ModuleData {
+        &self.modules[idx]
+    }
+}
+
+impl Index<Import> for RawItems {
+    type Output = ImportData;
+    fn index(&self, idx: Import) -> &ImportData {
+        &self.imports[idx]
+    }
+}
+
+impl Index<Def> for RawItems {
+    type Output = DefData;
+    fn index(&self, idx: Def) -> &DefData {
+        &self.defs[idx]
+    }
+}
+
+impl Index<Macro> for RawItems {
+    type Output = MacroData;
+    fn index(&self, idx: Macro) -> &MacroData {
+        &self.macros[idx]
+    }
+}
+
+#[derive(PartialEq, Eq, Clone, Copy)]
+pub(crate) enum RawItem {
+    Module(Module),
+    Import(Import),
+    Def(Def),
+    Macro(Macro),
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Hash)]
+pub(crate) struct Module(RawId);
+impl_arena_id!(Module);
+
+#[derive(PartialEq, Eq)]
+pub(crate) enum ModuleData {
+    Declaration { name: Name },
+    Definition { name: Name, items: Vec<RawItem> },
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub(crate) struct Import(RawId);
+impl_arena_id!(Import);
+
+#[derive(PartialEq, Eq)]
+pub(crate) struct ImportData {
+    path: Path,
+    alias: Option<Name>,
+    is_glob: bool,
+    is_prelude: bool,
+    is_extern_crate: bool,
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Hash)]
+pub(crate) struct Def(RawId);
+impl_arena_id!(Def);
+
+#[derive(PartialEq, Eq)]
+pub(crate) struct DefData {
+    pub(crate) source_item_id: SourceFileItemId,
+    pub(crate) name: Name,
+    pub(crate) kind: DefKind,
+}
+
+#[derive(Debug, PartialEq, Eq, Clone, Copy)]
+pub(crate) enum DefKind {
+    Function,
+    Struct,
+    Enum,
+    Const,
+    Static,
+    Trait,
+    TypeAlias,
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Hash)]
+pub(crate) struct Macro(RawId);
+impl_arena_id!(Macro);
+
+#[derive(PartialEq, Eq)]
+pub(crate) struct MacroData {
+    pub(crate) source_item_id: SourceFileItemId,
+    pub(crate) path: Path,
+    pub(crate) name: Option<Name>,
+    pub(crate) arg: tt::Subtree,
+}
+
+struct RawItemsCollector {
+    raw_items: RawItems,
+    source_file_items: Arc<SourceFileItems>,
+}
+
+impl RawItemsCollector {
+    fn process_module(&mut self, current_module: Option<Module>, body: &impl ast::ModuleItemOwner) {
+        for item_or_macro in body.items_with_macros() {
+            match item_or_macro {
+                ast::ItemOrMacro::Macro(m) => self.add_macro(current_module, m),
+                ast::ItemOrMacro::Item(item) => self.add_item(current_module, item),
+            }
+        }
+    }
+
+    fn add_item(&mut self, current_module: Option<Module>, item: &ast::ModuleItem) {
+        let (kind, name) = match item.kind() {
+            ast::ModuleItemKind::Module(module) => {
+                self.add_module(current_module, module);
+                return;
+            }
+            ast::ModuleItemKind::UseItem(use_item) => {
+                self.add_use_item(current_module, use_item);
+                return;
+            }
+            ast::ModuleItemKind::ExternCrateItem(extern_crate) => {
+                self.add_extern_crate_item(current_module, extern_crate);
+                return;
+            }
+            ast::ModuleItemKind::ImplBlock(_) => {
+                // impls don't participate in name resolution
+                return;
+            }
+            ast::ModuleItemKind::StructDef(it) => (DefKind::Struct, it.name()),
+            ast::ModuleItemKind::EnumDef(it) => (DefKind::Enum, it.name()),
+            ast::ModuleItemKind::FnDef(it) => (DefKind::Function, it.name()),
+            ast::ModuleItemKind::TraitDef(it) => (DefKind::Trait, it.name()),
+            ast::ModuleItemKind::TypeAliasDef(it) => (DefKind::TypeAlias, it.name()),
+            ast::ModuleItemKind::ConstDef(it) => (DefKind::Const, it.name()),
+            ast::ModuleItemKind::StaticDef(it) => (DefKind::Static, it.name()),
+        };
+        if let Some(name) = name {
+            let name = name.as_name();
+            let source_item_id = self.source_file_items.id_of_unchecked(item.syntax());
+            let def = self.raw_items.defs.alloc(DefData { name, kind, source_item_id });
+            self.push_item(current_module, RawItem::Def(def))
+        }
+    }
+
+    fn add_module(&mut self, current_module: Option<Module>, module: &ast::Module) {
+        let name = match module.name() {
+            Some(it) => it.as_name(),
+            None => return,
+        };
+        if module.has_semi() {
+            let item = self.raw_items.modules.alloc(ModuleData::Declaration { name });
+            self.push_item(current_module, RawItem::Module(item));
+            return;
+        }
+
+        if let Some(item_list) = module.item_list() {
+            let item =
+                self.raw_items.modules.alloc(ModuleData::Definition { name, items: Vec::new() });
+            self.process_module(Some(item), item_list);
+            self.push_item(current_module, RawItem::Module(item));
+        }
+    }
+
+    fn add_use_item(&mut self, current_module: Option<Module>, use_item: &ast::UseItem) {
+        let is_prelude = use_item
+            .attrs()
+            .any(|attr| attr.as_atom().map(|s| s == "prelude_import").unwrap_or(false));
+
+        Path::expand_use_item(use_item, |path, segment, alias| {
+            let import = self.raw_items.imports.alloc(ImportData {
+                path,
+                alias,
+                is_glob: segment.is_none(),
+                is_prelude,
+                is_extern_crate: false,
+            });
+            self.push_item(current_module, RawItem::Import(import))
+        })
+    }
+
+    fn add_extern_crate_item(
+        &mut self,
+        current_module: Option<Module>,
+        extern_crate: &ast::ExternCrateItem,
+    ) {
+        if let Some(name_ref) = extern_crate.name_ref() {
+            let path = Path::from_name_ref(name_ref);
+            let alias = extern_crate.alias().and_then(|a| a.name()).map(AsName::as_name);
+            let import = self.raw_items.imports.alloc(ImportData {
+                path,
+                alias,
+                is_glob: false,
+                is_prelude: false,
+                is_extern_crate: true,
+            });
+            self.push_item(current_module, RawItem::Import(import))
+        }
+    }
+
+    fn add_macro(&mut self, current_module: Option<Module>, m: &ast::MacroCall) {
+        let (path, arg) = match (
+            m.path().and_then(Path::from_ast),
+            m.token_tree().and_then(mbe::ast_to_token_tree),
+        ) {
+            (Some(path), Some((token_tree, _token_map))) => (path, token_tree),
+            _ => return,
+        };
+
+        let name = m.name().map(|it| it.as_name());
+        let source_item_id = self.source_file_items.id_of_unchecked(m.syntax());
+        let m = self.raw_items.macros.alloc(MacroData { source_item_id, path, arg, name });
+        self.push_item(current_module, RawItem::Macro(m));
+    }
+
+    fn push_item(&mut self, current_module: Option<Module>, item: RawItem) {
+        match current_module {
+            Some(module) => match &mut self.raw_items.modules[module] {
+                ModuleData::Definition { items, .. } => items,
+                ModuleData::Declaration { .. } => unreachable!(),
+            },
+            None => &mut self.raw_items.items,
+        }
+        .push(item)
+    }
+}