Repository: rust-analyzer/rust-analyzer
Pull request #10863 (2021-11-25 23:23:29)

internal: build per-block `ItemTree`s
Fixes https://github.com/rust-analyzer/rust-analyzer/issues/7717
Fixes https://github.com/rust-analyzer/rust-analyzer/issues/8911
Fixes https://github.com/rust-analyzer/rust-analyzer/issues/8614

`ItemTree`s are now flat lists of items, so they should probably be renamed at some point.


Patch:
diff --git a/crates/hir_def/src/item_tree.rs b/crates/hir_def/src/item_tree.rs
index 73b00887e7..12fa34b73a 100644
--- a/crates/hir_def/src/item_tree.rs
+++ b/crates/hir_def/src/item_tree.rs
@@ -132,21 +132,6 @@ impl ItemTree {
                     // items.
                     ctx.lower_macro_stmts(stmts)
                 },
-                ast::Pat(_pat) => {
-                    // FIXME: This occurs because macros in pattern position are treated as inner
-                    // items and expanded during block DefMap computation
-                    return Default::default();
-                },
-                ast::Type(ty) => {
-                    // Types can contain inner items. We return an empty item tree in this case, but
-                    // still need to collect inner items.
-                    ctx.lower_inner_items(ty.syntax())
-                },
-                ast::Expr(e) => {
-                    // Macros can expand to expressions. We return an empty item tree in this case, but
-                    // still need to collect inner items.
-                    ctx.lower_inner_items(e.syntax())
-                },
                 _ => {
                     panic!("cannot create item tree from {:?} {}", syntax, syntax);
                 },
@@ -160,6 +145,14 @@ impl ItemTree {
         Arc::new(item_tree)
     }
 
+    fn block_item_tree(db: &dyn DefDatabase, block: BlockId) -> Arc<ItemTree> {
+        let loc = db.lookup_intern_block(block);
+        let block = loc.ast_id.to_node(db.upcast());
+        let hygiene = Hygiene::new(db.upcast(), loc.ast_id.file_id);
+        let ctx = lower::Ctx::new(db, hygiene.clone(), loc.ast_id.file_id);
+        Arc::new(ctx.lower_block(&block))
+    }
+
     fn shrink_to_fit(&mut self) {
         if let Some(data) = &mut self.data {
             let ItemTreeData {
@@ -183,7 +176,6 @@ impl ItemTree {
                 macro_rules,
                 macro_defs,
                 vis,
-                inner_items,
             } = &mut **data;
 
             imports.shrink_to_fit();
@@ -207,8 +199,6 @@ impl ItemTree {
             macro_defs.shrink_to_fit();
 
             vis.arena.shrink_to_fit();
-
-            inner_items.shrink_to_fit();
         }
     }
 
@@ -231,13 +221,6 @@ impl ItemTree {
         self.raw_attrs(of).clone().filter(db, krate)
     }
 
-    pub fn inner_items_of_block(&self, block: FileAstId<ast::BlockExpr>) -> &[ModItem] {
-        match &self.data {
-            Some(data) => data.inner_items.get(&block).map(|it| &**it).unwrap_or(&[]),
-            None => &[],
-        }
-    }
-
     pub fn pretty_print(&self) -> String {
         pretty::print_item_tree(self)
     }
@@ -297,8 +280,6 @@ struct ItemTreeData {
     macro_defs: Arena<MacroDef>,
 
     vis: ItemVisibilities,
-
-    inner_items: FxHashMap<FileAstId<ast::BlockExpr>, SmallVec<[ModItem; 1]>>,
 }
 
 #[derive(Debug, Eq, PartialEq, Hash)]
@@ -388,7 +369,7 @@ impl TreeId {
 
     pub(crate) fn item_tree(&self, db: &dyn DefDatabase) -> Arc<ItemTree> {
         match self.block {
-            Some(_) => unreachable!("per-block ItemTrees are not yet implemented"),
+            Some(block) => ItemTree::block_item_tree(db, block),
             None => db.file_item_tree(self.file),
         }
     }
@@ -396,6 +377,10 @@ impl TreeId {
     pub(crate) fn file_id(self) -> HirFileId {
         self.file
     }
+
+    pub(crate) fn is_block(self) -> bool {
+        self.block.is_some()
+    }
 }
 
 #[derive(Debug)]
diff --git a/crates/hir_def/src/item_tree/lower.rs b/crates/hir_def/src/item_tree/lower.rs
index 9381ca39f7..bb224f57b2 100644
--- a/crates/hir_def/src/item_tree/lower.rs
+++ b/crates/hir_def/src/item_tree/lower.rs
@@ -3,10 +3,7 @@
 use std::{collections::hash_map::Entry, mem, sync::Arc};
 
 use hir_expand::{ast_id_map::AstIdMap, hygiene::Hygiene, name::known, HirFileId};
-use syntax::{
-    ast::{self, HasModuleItem},
-    SyntaxNode, WalkEvent,
-};
+use syntax::ast::{self, HasModuleItem};
 
 use crate::{
     generics::{GenericParams, TypeParamData, TypeParamProvenance},
@@ -42,7 +39,7 @@ impl<'a> Ctx<'a> {
 
     pub(super) fn lower_module_items(mut self, item_owner: &dyn HasModuleItem) -> ItemTree {
         self.tree.top_level =
-            item_owner.items().flat_map(|item| self.lower_mod_item(&item, false)).collect();
+            item_owner.items().flat_map(|item| self.lower_mod_item(&item)).collect();
         self.tree
     }
 
@@ -62,26 +59,27 @@ impl<'a> Ctx<'a> {
                 },
                 _ => None,
             })
-            .flat_map(|item| self.lower_mod_item(&item, false))
+            .flat_map(|item| self.lower_mod_item(&item))
             .collect();
 
-        // Non-items need to have their inner items collected.
-        for stmt in stmts.statements() {
-            match stmt {
-                ast::Stmt::ExprStmt(_) | ast::Stmt::LetStmt(_) => {
-                    self.collect_inner_items(stmt.syntax())
-                }
-                _ => {}
-            }
-        }
-        if let Some(expr) = stmts.expr() {
-            self.collect_inner_items(expr.syntax());
-        }
         self.tree
     }
 
-    pub(super) fn lower_inner_items(mut self, within: &SyntaxNode) -> ItemTree {
-        self.collect_inner_items(within);
+    pub(super) fn lower_block(mut self, block: &ast::BlockExpr) -> ItemTree {
+        self.tree.top_level = block
+            .statements()
+            .filter_map(|stmt| match stmt {
+                ast::Stmt::Item(item) => self.lower_mod_item(&item),
+                // Macro calls can be both items and expressions. The syntax library always treats
+                // them as expressions here, so we undo that.
+                ast::Stmt::ExprStmt(es) => match es.expr()? {
+                    ast::Expr::MacroCall(call) => self.lower_mod_item(&call.into()),
+                    _ => None,
+                },
+                _ => None,
+            })
+            .collect();
+
         self.tree
     }
 
@@ -89,36 +87,7 @@ impl<'a> Ctx<'a> {
         self.tree.data_mut()
     }
 
-    fn lower_mod_item(&mut self, item: &ast::Item, inner: bool) -> Option<ModItem> {
-        // Collect inner items for 1-to-1-lowered items.
-        match item {
-            ast::Item::Struct(_)
-            | ast::Item::Union(_)
-            | ast::Item::Enum(_)
-            | ast::Item::Fn(_)
-            | ast::Item::TypeAlias(_)
-            | ast::Item::Const(_)
-            | ast::Item::Static(_) => {
-                // Skip this if we're already collecting inner items. We'll descend into all nodes
-                // already.
-                if !inner {
-                    self.collect_inner_items(item.syntax());
-                }
-            }
-
-            // These are handled in their respective `lower_X` method (since we can't just blindly
-            // walk them).
-            ast::Item::Trait(_) | ast::Item::Impl(_) | ast::Item::ExternBlock(_) => {}
-
-            // These don't have inner items.
-            ast::Item::Module(_)
-            | ast::Item::ExternCrate(_)
-            | ast::Item::Use(_)
-            | ast::Item::MacroCall(_)
-            | ast::Item::MacroRules(_)
-            | ast::Item::MacroDef(_) => {}
-        };
-
+    fn lower_mod_item(&mut self, item: &ast::Item) -> Option<ModItem> {
         let attrs = RawAttrs::new(self.db, item, &self.hygiene);
         let item: ModItem = match item {
             ast::Item::Struct(ast) => self.lower_struct(ast)?.into(),
@@ -155,47 +124,6 @@ impl<'a> Ctx<'a> {
         }
     }
 
-    fn collect_inner_items(&mut self, container: &SyntaxNode) {
-        let forced_vis = self.forced_visibility.take();
-
-        let mut block_stack = Vec::new();
-
-        // if container itself is block, add it to the stack
-        if let Some(block) = ast::BlockExpr::cast(container.clone()) {
-            block_stack.push(self.source_ast_id_map.ast_id(&block));
-        }
-
-        for event in container.preorder().skip(1) {
-            match event {
-                WalkEvent::Enter(node) => {
-                    match_ast! {
-                        match node {
-                            ast::BlockExpr(block) => {
-                                block_stack.push(self.source_ast_id_map.ast_id(&block));
-                            },
-                            ast::Item(item) => {
-                                // FIXME: This triggers for macro calls in expression/pattern/type position
-                                let mod_item = self.lower_mod_item(&item, true);
-                                let current_block = block_stack.last();
-                                if let (Some(mod_item), Some(block)) = (mod_item, current_block) {
-                                        self.data().inner_items.entry(*block).or_default().push(mod_item);
-                                }
-                            },
-                            _ => {}
-                        }
-                    }
-                }
-                WalkEvent::Leave(node) => {
-                    if ast::BlockExpr::cast(node).is_some() {
-                        block_stack.pop();
-                    }
-                }
-            }
-        }
-
-        self.forced_visibility = forced_vis;
-    }
-
     fn lower_assoc_item(&mut self, item: &ast::AssocItem) -> Option<AssocItem> {
         match item {
             ast::AssocItem::Fn(ast) => self.lower_function(ast).map(Into::into),
@@ -470,9 +398,7 @@ impl<'a> Ctx<'a> {
             ModKind::Inline {
                 items: module
                     .item_list()
-                    .map(|list| {
-                        list.items().flat_map(|item| self.lower_mod_item(&item, false)).collect()
-                    })
+                    .map(|list| list.items().flat_map(|item| self.lower_mod_item(&item)).collect())
                     .unwrap_or_else(|| {
                         cov_mark::hit!(name_res_works_for_broken_modules);
                         Box::new([]) as Box<[_]>
@@ -487,8 +413,7 @@ impl<'a> Ctx<'a> {
     fn lower_trait(&mut self, trait_def: &ast::Trait) -> Option<FileItemTreeId<Trait>> {
         let name = trait_def.name()?.as_name();
         let visibility = self.lower_visibility(trait_def);
-        let generic_params =
-            self.lower_generic_params_and_inner_items(GenericsOwner::Trait(trait_def), trait_def);
+        let generic_params = self.lower_generic_params(GenericsOwner::Trait(trait_def), trait_def);
         let is_auto = trait_def.auto_token().is_some();
         let is_unsafe = trait_def.unsafe_token().is_some();
         let items = trait_def.assoc_item_list().map(|list| {
@@ -497,7 +422,6 @@ impl<'a> Ctx<'a> {
                 list.assoc_items()
                     .filter_map(|item| {
                         let attrs = RawAttrs::new(db, &item, &this.hygiene);
-                        this.collect_inner_items(item.syntax());
                         this.lower_assoc_item(&item).map(|item| {
                             this.add_attrs(ModItem::from(item).into(), attrs);
                             item
@@ -520,8 +444,7 @@ impl<'a> Ctx<'a> {
     }
 
     fn lower_impl(&mut self, impl_def: &ast::Impl) -> Option<FileItemTreeId<Impl>> {
-        let generic_params =
-            self.lower_generic_params_and_inner_items(GenericsOwner::Impl, impl_def);
+        let generic_params = self.lower_generic_params(GenericsOwner::Impl, impl_def);
         // FIXME: If trait lowering fails, due to a non PathType for example, we treat this impl
         // as if it was an non-trait impl. Ideally we want to create a unique missing ref that only
         // equals itself.
@@ -535,7 +458,6 @@ impl<'a> Ctx<'a> {
             .into_iter()
             .flat_map(|it| it.assoc_items())
             .filter_map(|item| {
-                self.collect_inner_items(item.syntax());
                 let assoc = self.lower_assoc_item(&item)?;
                 let attrs = RawAttrs::new(self.db, &item, &self.hygiene);
                 self.add_attrs(ModItem::from(assoc).into(), attrs);
@@ -603,7 +525,6 @@ impl<'a> Ctx<'a> {
         let children: Box<[_]> = block.extern_item_list().map_or(Box::new([]), |list| {
             list.extern_items()
                 .filter_map(|item| {
-                    self.collect_inner_items(item.syntax());
                     let attrs = RawAttrs::new(self.db, &item, &self.hygiene);
                     let id: ModItem = match item {
                         ast::ExternItem::Fn(ast) => {
@@ -641,23 +562,6 @@ impl<'a> Ctx<'a> {
         id(self.data().extern_blocks.alloc(res))
     }
 
-    /// Lowers generics defined on `node` and collects inner items defined within.
-    fn lower_generic_params_and_inner_items(
-        &mut self,
-        owner: GenericsOwner<'_>,
-        node: &dyn ast::HasGenericParams,
-    ) -> Interned<GenericParams> {
-        // Generics are part of item headers and may contain inner items we need to collect.
-        if let Some(params) = node.generic_param_list() {
-            self.collect_inner_items(params.syntax());
-        }
-        if let Some(clause) = node.where_clause() {
-            self.collect_inner_items(clause.syntax());
-        }
-
-        self.lower_generic_params(owner, node)
-    }
-
     fn lower_generic_params(
         &mut self,
         owner: GenericsOwner<'_>,
diff --git a/crates/hir_def/src/nameres.rs b/crates/hir_def/src/nameres.rs
index d0b8248a34..882d54c996 100644
--- a/crates/hir_def/src/nameres.rs
+++ b/crates/hir_def/src/nameres.rs
@@ -69,6 +69,7 @@ use syntax::ast;
 use crate::{
     db::DefDatabase,
     item_scope::{BuiltinShadowMode, ItemScope},
+    item_tree::TreeId,
     nameres::{diagnostics::DefDiagnostic, path_resolution::ResolveMode},
     path::ModPath,
     per_ns::PerNs,
@@ -214,7 +215,11 @@ impl DefMap {
         let edition = crate_graph[krate].edition;
         let origin = ModuleOrigin::CrateRoot { definition: crate_graph[krate].root_file_id };
         let def_map = DefMap::empty(krate, edition, origin);
-        let def_map = collector::collect_defs(db, def_map, None);
+        let def_map = collector::collect_defs(
+            db,
+            def_map,
+            TreeId::new(crate_graph[krate].root_file_id.into(), None),
+        );
 
         Arc::new(def_map)
     }
@@ -225,8 +230,9 @@ impl DefMap {
     ) -> Option<Arc<DefMap>> {
         let block: BlockLoc = db.lookup_intern_block(block_id);
 
-        let item_tree = db.file_item_tree(block.ast_id.file_id);
-        if item_tree.inner_items_of_block(block.ast_id.value).is_empty() {
+        let tree_id = TreeId::new(block.ast_id.file_id, Some(block_id));
+        let item_tree = tree_id.item_tree(db);
+        if item_tree.top_level_items().is_empty() {
             return None;
         }
 
@@ -240,7 +246,7 @@ impl DefMap {
         );
         def_map.block = Some(block_info);
 
-        let def_map = collector::collect_defs(db, def_map, Some(block.ast_id));
+        let def_map = collector::collect_defs(db, def_map, tree_id);
         Some(Arc::new(def_map))
     }
 
diff --git a/crates/hir_def/src/nameres/collector.rs b/crates/hir_def/src/nameres/collector.rs
index 5673bef38b..9f69117805 100644
--- a/crates/hir_def/src/nameres/collector.rs
+++ b/crates/hir_def/src/nameres/collector.rs
@@ -53,11 +53,7 @@ static GLOB_RECURSION_LIMIT: Limit = Limit::new(100);
 static EXPANSION_DEPTH_LIMIT: Limit = Limit::new(128);
 static FIXED_POINT_LIMIT: Limit = Limit::new(8192);
 
-pub(super) fn collect_defs(
-    db: &dyn DefDatabase,
-    mut def_map: DefMap,
-    block: Option<AstId<ast::BlockExpr>>,
-) -> DefMap {
+pub(super) fn collect_defs(db: &dyn DefDatabase, mut def_map: DefMap, tree_id: TreeId) -> DefMap {
     let crate_graph = db.crate_graph();
 
     let mut deps = FxHashMap::default();
@@ -69,7 +65,7 @@ pub(super) fn collect_defs(
 
         deps.insert(dep.as_name(), dep_root.into());
 
-        if dep.is_prelude() && block.is_none() {
+        if dep.is_prelude() && !tree_id.is_block() {
             def_map.extern_prelude.insert(dep.as_name(), dep_root.into());
         }
     }
@@ -104,9 +100,10 @@ pub(super) fn collect_defs(
         registered_attrs: Default::default(),
         registered_tools: Default::default(),
     };
-    match block {
-        Some(block) => collector.seed_with_inner(block),
-        None => collector.seed_with_top_level(),
+    if tree_id.is_block() {
+        collector.seed_with_inner(tree_id);
+    } else {
+        collector.seed_with_top_level();
     }
     collector.collect();
     let mut def_map = collector.finish();
@@ -313,8 +310,8 @@ impl DefCollector<'_> {
         }
     }
 
-    fn seed_with_inner(&mut self, block: AstId<ast::BlockExpr>) {
-        let item_tree = self.db.file_item_tree(block.file_id);
+    fn seed_with_inner(&mut self, tree_id: TreeId) {
+        let item_tree = tree_id.item_tree(self.db);
         let module_id = self.def_map.root;
 
         let is_cfg_enabled = item_tree
@@ -326,12 +323,11 @@ impl DefCollector<'_> {
                 def_collector: self,
                 macro_depth: 0,
                 module_id,
-                // FIXME: populate block once we have per-block ItemTrees
-                tree_id: TreeId::new(block.file_id, None),
+                tree_id,
                 item_tree: &item_tree,
                 mod_dir: ModDir::root(),
             }
-            .collect(item_tree.inner_items_of_block(block.value));
+            .collect(item_tree.top_level_items());
         }
     }
 


Test patch:
diff --git a/crates/hir_def/src/body/tests/block.rs b/crates/hir_def/src/body/tests/block.rs
index bbf38fb636..da1e99c829 100644
--- a/crates/hir_def/src/body/tests/block.rs
+++ b/crates/hir_def/src/body/tests/block.rs
@@ -148,13 +148,11 @@ fn f() {
 }
     "#,
         expect![[r#"
-            BlockId(1) in ModuleId { krate: CrateId(0), block: Some(BlockId(0)), local_id: Idx::<ModuleData>(0) }
+            BlockId(1) in ModuleId { krate: CrateId(0), block: Some(BlockId(0)), local_id: Idx::<ModuleData>(1) }
             BlockId(0) in ModuleId { krate: CrateId(0), block: None, local_id: Idx::<ModuleData>(0) }
             crate scope
         "#]],
     );
-    // FIXME: The module nesting here is wrong!
-    // The first block map should be located in module #1 (`mod module`), not #0 (BlockId(0) root module)
 }
 
 #[test]
@@ -352,25 +350,18 @@ fn is_visible_from_same_def_map() {
     check_at(
         r#"
 fn outer() {
-    mod command {
-        use crate::name;
-    }
-
     mod tests {
         use super::*;
     }
+    use crate::name;
     $0
 }
         "#,
         expect![[r#"
             block scope
-            command: t
             name: _
             tests: t
 
-            block scope::command
-            name: _
-
             block scope::tests
             name: _
             outer: v
@@ -379,6 +370,4 @@ fn outer() {
             outer: v
         "#]],
     );
-    // FIXME: `name` should not be visible in the block scope. This happens because ItemTrees store
-    // inner items incorrectly.
 }