From 2195d1db6d70d64383bec82819fab02891d09744 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Wed, 13 Mar 2019 16:38:02 +0300 Subject: Replace module_tree with CrateDefMap --- crates/ra_hir/src/code_model_api.rs | 2 +- crates/ra_hir/src/code_model_impl/krate.rs | 4 +- crates/ra_hir/src/code_model_impl/module.rs | 97 ++++-- crates/ra_hir/src/db.rs | 21 +- crates/ra_hir/src/ids.rs | 6 + crates/ra_hir/src/lib.rs | 1 - crates/ra_hir/src/module_tree.rs | 340 --------------------- crates/ra_hir/src/nameres.rs | 23 +- crates/ra_hir/src/nameres/crate_def_map.rs | 118 +++++-- .../ra_hir/src/nameres/crate_def_map/collector.rs | 166 ++++++---- crates/ra_hir/src/nameres/crate_def_map/raw.rs | 51 ++-- crates/ra_hir/src/nameres/crate_def_map/tests.rs | 2 +- crates/ra_hir/src/nameres/tests.rs | 3 +- crates/ra_hir/src/source_binder.rs | 4 +- crates/ra_hir/src/ty/method_resolution.rs | 4 +- 15 files changed, 332 insertions(+), 510 deletions(-) (limited to 'crates/ra_hir/src') diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs index 87a7195e6..ef69ef96a 100644 --- a/crates/ra_hir/src/code_model_api.rs +++ b/crates/ra_hir/src/code_model_api.rs @@ -9,12 +9,12 @@ use crate::{ HirDatabase, PersistentHirDatabase, type_ref::TypeRef, nameres::{ModuleScope, Namespace, lower::ImportId}, + nameres::crate_def_map::ModuleId, expr::{Body, BodySourceMap}, ty::InferenceResult, adt::{EnumVariantId, StructFieldId, VariantDef}, generics::GenericParams, docs::{Documentation, Docs, docs_from_ast}, - module_tree::ModuleId, ids::{FunctionId, StructId, EnumId, AstItemDef, ConstId, StaticId, TraitId, TypeId}, impl_block::ImplBlock, resolve::Resolver, diff --git a/crates/ra_hir/src/code_model_impl/krate.rs b/crates/ra_hir/src/code_model_impl/krate.rs index 161ae6e18..cc87c6f14 100644 --- a/crates/ra_hir/src/code_model_impl/krate.rs +++ b/crates/ra_hir/src/code_model_impl/krate.rs @@ -18,9 +18,7 @@ impl Crate { .collect() } pub(crate) fn root_module_impl(&self, db: &impl PersistentHirDatabase) -> Option { - let module_tree = db.module_tree(*self); - let module_id = module_tree.modules().next()?; - + let module_id = db.crate_def_map(*self).root(); let module = Module { krate: *self, module_id }; Some(module) } diff --git a/crates/ra_hir/src/code_model_impl/module.rs b/crates/ra_hir/src/code_model_impl/module.rs index 437f96942..5d8f738b5 100644 --- a/crates/ra_hir/src/code_model_impl/module.rs +++ b/crates/ra_hir/src/code_model_impl/module.rs @@ -1,33 +1,62 @@ -use ra_syntax::{ast, SyntaxNode, TreeArc}; +use ra_db::FileId; +use ra_syntax::{ast, SyntaxNode, TreeArc, AstNode}; use crate::{ - Module, ModuleSource, Problem, - Name, - module_tree::ModuleId, + Module, ModuleSource, Problem, Name, + nameres::crate_def_map::ModuleId, nameres::lower::ImportId, HirDatabase, PersistentHirDatabase, - HirFileId + HirFileId, SourceItemId, }; +impl ModuleSource { + pub(crate) fn new( + db: &impl PersistentHirDatabase, + file_id: Option, + decl_id: Option, + ) -> ModuleSource { + match (file_id, decl_id) { + (Some(file_id), _) => { + let source_file = db.parse(file_id); + ModuleSource::SourceFile(source_file) + } + (None, Some(item_id)) => { + let module = db.file_item(item_id); + let module = ast::Module::cast(&*module).unwrap(); + assert!(module.item_list().is_some(), "expected inline module"); + ModuleSource::Module(module.to_owned()) + } + (None, None) => panic!(), + } + } +} + impl Module { fn with_module_id(&self, module_id: ModuleId) -> Module { Module { module_id, krate: self.krate } } pub(crate) fn name_impl(&self, db: &impl HirDatabase) -> Option { - let module_tree = db.module_tree(self.krate); - let link = self.module_id.parent_link(&module_tree)?; - Some(link.name(&module_tree).clone()) + let def_map = db.crate_def_map(self.krate); + let parent = def_map[self.module_id].parent?; + def_map[parent].children.iter().find_map(|(name, module_id)| { + if *module_id == self.module_id { + Some(name.clone()) + } else { + None + } + }) } pub(crate) fn definition_source_impl( &self, db: &impl PersistentHirDatabase, ) -> (HirFileId, ModuleSource) { - let module_tree = db.module_tree(self.krate); - let file_id = self.module_id.file_id(&module_tree); - let decl_id = self.module_id.decl_id(&module_tree); + let def_map = db.crate_def_map(self.krate); + let decl_id = def_map[self.module_id].declaration; + let file_id = def_map[self.module_id].definition; let module_source = ModuleSource::new(db, file_id, decl_id); + let file_id = file_id.map(HirFileId::from).unwrap_or_else(|| decl_id.unwrap().file_id); (file_id, module_source) } @@ -35,11 +64,11 @@ impl Module { &self, db: &impl HirDatabase, ) -> Option<(HirFileId, TreeArc)> { - let module_tree = db.module_tree(self.krate); - let link = self.module_id.parent_link(&module_tree)?; - let file_id = link.owner(&module_tree).file_id(&module_tree); - let src = link.source(&module_tree, db); - Some((file_id, src)) + let def_map = db.crate_def_map(self.krate); + let decl = def_map[self.module_id].declaration?; + let syntax_node = db.file_item(decl); + let ast = ast::Module::cast(&syntax_node).unwrap().to_owned(); + Some((decl.file_id, ast)) } pub(crate) fn import_source_impl( @@ -53,16 +82,15 @@ impl Module { } pub(crate) fn crate_root_impl(&self, db: &impl PersistentHirDatabase) -> Module { - let module_tree = db.module_tree(self.krate); - let module_id = self.module_id.crate_root(&module_tree); - self.with_module_id(module_id) + let def_map = db.crate_def_map(self.krate); + self.with_module_id(def_map.root()) } /// Finds a child module with the specified name. pub(crate) fn child_impl(&self, db: &impl HirDatabase, name: &Name) -> Option { - let module_tree = db.module_tree(self.krate); - let child_id = self.module_id.child(&module_tree, name)?; - Some(self.with_module_id(child_id)) + let def_map = db.crate_def_map(self.krate); + let child_id = def_map[self.module_id].children.get(name)?; + Some(self.with_module_id(*child_id)) } /// Iterates over all child modules. @@ -70,18 +98,18 @@ impl Module { &self, db: &impl PersistentHirDatabase, ) -> impl Iterator { - let module_tree = db.module_tree(self.krate); - let children = self - .module_id - .children(&module_tree) - .map(|(_, module_id)| self.with_module_id(module_id)) + let def_map = db.crate_def_map(self.krate); + let children = def_map[self.module_id] + .children + .iter() + .map(|(_, module_id)| self.with_module_id(*module_id)) .collect::>(); children.into_iter() } pub(crate) fn parent_impl(&self, db: &impl PersistentHirDatabase) -> Option { - let module_tree = db.module_tree(self.krate); - let parent_id = self.module_id.parent(&module_tree)?; + let def_map = db.crate_def_map(self.krate); + let parent_id = def_map[self.module_id].parent?; Some(self.with_module_id(parent_id)) } @@ -89,7 +117,14 @@ impl Module { &self, db: &impl HirDatabase, ) -> Vec<(TreeArc, Problem)> { - let module_tree = db.module_tree(self.krate); - self.module_id.problems(&module_tree, db) + let def_map = db.crate_def_map(self.krate); + let (my_file_id, _) = self.definition_source(db); + // FIXME: not entirely corret filterint by module + def_map + .problems() + .iter() + .filter(|(source_item_id, _problem)| my_file_id == source_item_id.file_id) + .map(|(source_item_id, problem)| (db.file_item(*source_item_id), problem.clone())) + .collect() } } diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs index 5ad9547f1..423922a57 100644 --- a/crates/ra_hir/src/db.rs +++ b/crates/ra_hir/src/db.rs @@ -1,7 +1,7 @@ use std::sync::Arc; use ra_syntax::{SyntaxNode, TreeArc, SourceFile}; -use ra_db::{SourceDatabase, salsa}; +use ra_db::{SourceDatabase, salsa, FileId}; use crate::{ MacroCallId, HirFileId, @@ -10,14 +10,11 @@ use crate::{ Struct, Enum, StructField, Const, ConstSignature, Static, macros::MacroExpansion, - module_tree::ModuleTree, - nameres::{ItemMap, lower::{LoweredModule, ImportSourceMap}}, + nameres::{Namespace, ItemMap, lower::{LoweredModule, ImportSourceMap}, crate_def_map::{RawItems, CrateDefMap}}, ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig}, adt::{StructData, EnumData}, impl_block::{ModuleImplBlocks, ImplSourceMap}, generics::{GenericParams, GenericDef}, - ids::SourceFileItemId, - nameres::Namespace, type_ref::TypeRef, }; @@ -41,13 +38,6 @@ pub trait PersistentHirDatabase: SourceDatabase + AsRef { #[salsa::invoke(crate::ids::SourceFileItems::file_item_query)] fn file_item(&self, source_item_id: SourceItemId) -> TreeArc; - #[salsa::invoke(crate::module_tree::Submodule::submodules_query)] - fn submodules( - &self, - file_id: HirFileId, - delc_id: Option, - ) -> Arc>; - #[salsa::invoke(crate::nameres::lower::LoweredModule::lower_module_with_source_map_query)] fn lower_module_with_source_map( &self, @@ -57,11 +47,14 @@ pub trait PersistentHirDatabase: SourceDatabase + AsRef { #[salsa::invoke(crate::nameres::lower::LoweredModule::lower_module_query)] fn lower_module(&self, module: Module) -> Arc; + #[salsa::invoke(RawItems::raw_items_query)] + fn raw_items(&self, file_id: FileId) -> Arc; + #[salsa::invoke(crate::nameres::ItemMap::item_map_query)] fn item_map(&self, krate: Crate) -> Arc; - #[salsa::invoke(crate::module_tree::ModuleTree::module_tree_query)] - fn module_tree(&self, krate: Crate) -> Arc; + #[salsa::invoke(CrateDefMap::crate_def_map_query)] + fn crate_def_map(&self, krate: Crate) -> Arc; #[salsa::invoke(crate::impl_block::impls_in_module)] fn impls_in_module(&self, module: Module) -> Arc; diff --git a/crates/ra_hir/src/ids.rs b/crates/ra_hir/src/ids.rs index e805ddcba..6ce00a372 100644 --- a/crates/ra_hir/src/ids.rs +++ b/crates/ra_hir/src/ids.rs @@ -296,6 +296,12 @@ impl AstItemDef for TypeId { pub struct SourceFileItemId(RawId); impl_arena_id!(SourceFileItemId); +impl SourceFileItemId { + pub(crate) fn with_file_id(self, file_id: HirFileId) -> SourceItemId { + SourceItemId { file_id, item_id: self } + } +} + #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] pub struct SourceItemId { pub(crate) file_id: HirFileId, diff --git a/crates/ra_hir/src/lib.rs b/crates/ra_hir/src/lib.rs index 4508a873e..61db4f6cc 100644 --- a/crates/ra_hir/src/lib.rs +++ b/crates/ra_hir/src/lib.rs @@ -26,7 +26,6 @@ pub mod source_binder; mod ids; mod macros; mod name; -mod module_tree; mod nameres; mod adt; mod type_alias; diff --git a/crates/ra_hir/src/module_tree.rs b/crates/ra_hir/src/module_tree.rs index 4d0f40e85..e69de29bb 100644 --- a/crates/ra_hir/src/module_tree.rs +++ b/crates/ra_hir/src/module_tree.rs @@ -1,340 +0,0 @@ -use std::sync::Arc; - -use arrayvec::ArrayVec; -use relative_path::RelativePathBuf; -use ra_db::{FileId, SourceRoot}; -use ra_syntax::{ - SyntaxNode, TreeArc, - algo::generate, - ast::{self, AstNode, NameOwner}, -}; -use ra_arena::{Arena, RawId, impl_arena_id}; -use test_utils::tested_by; - -use crate::{ - Name, AsName, HirDatabase, SourceItemId, HirFileId, Problem, SourceFileItems, ModuleSource, - PersistentHirDatabase, - Crate, - ids::SourceFileItemId, -}; - -impl ModuleSource { - pub(crate) fn new( - db: &impl PersistentHirDatabase, - file_id: HirFileId, - decl_id: Option, - ) -> ModuleSource { - match decl_id { - Some(item_id) => { - let module = db.file_item(SourceItemId { file_id, item_id }); - let module = ast::Module::cast(&*module).unwrap(); - assert!(module.item_list().is_some(), "expected inline module"); - ModuleSource::Module(module.to_owned()) - } - None => { - let source_file = db.hir_parse(file_id); - ModuleSource::SourceFile(source_file) - } - } - } -} - -#[derive(Clone, Hash, PartialEq, Eq, Debug)] -pub struct Submodule { - name: Name, - is_declaration: bool, - decl_id: SourceFileItemId, -} - -impl Submodule { - pub(crate) fn submodules_query( - db: &impl PersistentHirDatabase, - file_id: HirFileId, - decl_id: Option, - ) -> Arc> { - db.check_canceled(); - let file_items = db.file_items(file_id); - let module_source = ModuleSource::new(db, file_id, decl_id); - let submodules = match module_source { - ModuleSource::SourceFile(source_file) => { - collect_submodules(file_id, &file_items, &*source_file) - } - ModuleSource::Module(module) => { - collect_submodules(file_id, &file_items, module.item_list().unwrap()) - } - }; - - return Arc::new(submodules); - - fn collect_submodules( - file_id: HirFileId, - file_items: &SourceFileItems, - root: &impl ast::ModuleItemOwner, - ) -> Vec { - root.items() - .filter_map(|item| match item.kind() { - ast::ModuleItemKind::Module(m) => Some(m), - _ => None, - }) - .filter_map(|module| { - let name = module.name()?.as_name(); - if !module.has_semi() && module.item_list().is_none() { - tested_by!(name_res_works_for_broken_modules); - return None; - } - let sub = Submodule { - name, - is_declaration: module.has_semi(), - decl_id: file_items.id_of(file_id, module.syntax()), - }; - Some(sub) - }) - .collect() - } - } -} - -#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct ModuleId(RawId); -impl_arena_id!(ModuleId); - -#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct LinkId(RawId); -impl_arena_id!(LinkId); - -/// Physically, rust source is organized as a set of files, but logically it is -/// organized as a tree of modules. Usually, a single file corresponds to a -/// single module, but it is not neccessarily always the case. -/// -/// `ModuleTree` encapsulates the logic of transitioning from the fuzzy world of files -/// (which can have multiple parents) to the precise world of modules (which -/// always have one parent). -#[derive(Default, Debug, PartialEq, Eq)] -pub struct ModuleTree { - mods: Arena, - links: Arena, -} - -#[derive(Debug, PartialEq, Eq)] -pub struct ModuleData { - file_id: HirFileId, - /// Points to `ast::Module`, `None` for the whole file. - decl_id: Option, - parent: Option, - children: Vec, -} - -#[derive(Hash, Debug, PartialEq, Eq)] -struct LinkData { - source: SourceItemId, - owner: ModuleId, - name: Name, - points_to: Vec, - problem: Option, -} - -impl ModuleTree { - pub(crate) fn module_tree_query( - db: &impl PersistentHirDatabase, - krate: Crate, - ) -> Arc { - db.check_canceled(); - let mut res = ModuleTree::default(); - res.init_crate(db, krate); - Arc::new(res) - } - - pub(crate) fn modules<'a>(&'a self) -> impl Iterator + 'a { - self.mods.iter().map(|(id, _)| id) - } - - pub(crate) fn find_module_by_source( - &self, - file_id: HirFileId, - decl_id: Option, - ) -> Option { - let (res, _) = - self.mods.iter().find(|(_, m)| (m.file_id, m.decl_id) == (file_id, decl_id))?; - Some(res) - } - - fn init_crate(&mut self, db: &impl PersistentHirDatabase, krate: Crate) { - let crate_graph = db.crate_graph(); - let file_id = crate_graph.crate_root(krate.crate_id); - let source_root_id = db.file_source_root(file_id); - - let source_root = db.source_root(source_root_id); - self.init_subtree(db, &source_root, None, file_id.into(), None); - } - - fn init_subtree( - &mut self, - db: &impl PersistentHirDatabase, - source_root: &SourceRoot, - parent: Option, - file_id: HirFileId, - decl_id: Option, - ) -> ModuleId { - let is_root = parent.is_none(); - let id = self.alloc_mod(ModuleData { file_id, decl_id, parent, children: Vec::new() }); - for sub in db.submodules(file_id, decl_id).iter() { - let link = self.alloc_link(LinkData { - source: SourceItemId { file_id, item_id: sub.decl_id }, - name: sub.name.clone(), - owner: id, - points_to: Vec::new(), - problem: None, - }); - - let (points_to, problem) = if sub.is_declaration { - let (points_to, problem) = resolve_submodule(db, file_id, &sub.name, is_root); - let points_to = points_to - .into_iter() - .map(|file_id| { - self.init_subtree(db, source_root, Some(link), file_id.into(), None) - }) - .collect::>(); - (points_to, problem) - } else { - let points_to = - self.init_subtree(db, source_root, Some(link), file_id, Some(sub.decl_id)); - (vec![points_to], None) - }; - - self.links[link].points_to = points_to; - self.links[link].problem = problem; - } - id - } - - fn alloc_mod(&mut self, data: ModuleData) -> ModuleId { - self.mods.alloc(data) - } - - fn alloc_link(&mut self, data: LinkData) -> LinkId { - let owner = data.owner; - let id = self.links.alloc(data); - self.mods[owner].children.push(id); - id - } -} - -impl ModuleId { - pub(crate) fn file_id(self, tree: &ModuleTree) -> HirFileId { - tree.mods[self].file_id - } - pub(crate) fn decl_id(self, tree: &ModuleTree) -> Option { - tree.mods[self].decl_id - } - pub(crate) fn parent_link(self, tree: &ModuleTree) -> Option { - tree.mods[self].parent - } - pub(crate) fn parent(self, tree: &ModuleTree) -> Option { - let link = self.parent_link(tree)?; - Some(tree.links[link].owner) - } - pub(crate) fn crate_root(self, tree: &ModuleTree) -> ModuleId { - generate(Some(self), move |it| it.parent(tree)).last().unwrap() - } - pub(crate) fn child(self, tree: &ModuleTree, name: &Name) -> Option { - let link = tree.mods[self] - .children - .iter() - .map(|&it| &tree.links[it]) - .find(|it| it.name == *name)?; - Some(*link.points_to.first()?) - } - pub(crate) fn children<'a>( - self, - tree: &'a ModuleTree, - ) -> impl Iterator + 'a { - tree.mods[self].children.iter().filter_map(move |&it| { - let link = &tree.links[it]; - let module = *link.points_to.first()?; - Some((link.name.clone(), module)) - }) - } - pub(crate) fn problems( - self, - tree: &ModuleTree, - db: &impl HirDatabase, - ) -> Vec<(TreeArc, Problem)> { - tree.mods[self] - .children - .iter() - .filter_map(|&link| { - let p = tree.links[link].problem.clone()?; - let s = link.source(tree, db); - let s = s.name().unwrap().syntax().to_owned(); - Some((s, p)) - }) - .collect() - } -} - -impl LinkId { - pub(crate) fn owner(self, tree: &ModuleTree) -> ModuleId { - tree.links[self].owner - } - pub(crate) fn name(self, tree: &ModuleTree) -> &Name { - &tree.links[self].name - } - pub(crate) fn source( - self, - tree: &ModuleTree, - db: &impl PersistentHirDatabase, - ) -> TreeArc { - let syntax_node = db.file_item(tree.links[self].source); - ast::Module::cast(&syntax_node).unwrap().to_owned() - } -} - -pub(crate) fn resolve_module_declaration( - db: &impl PersistentHirDatabase, - file_id: HirFileId, - name: &Name, - is_root: bool, -) -> Option { - resolve_submodule(db, file_id, name, is_root).0.first().map(|it| *it) -} - -fn resolve_submodule( - db: &impl PersistentHirDatabase, - file_id: HirFileId, - name: &Name, - is_root: bool, -) -> (Vec, Option) { - // FIXME: handle submodules of inline modules properly - let file_id = file_id.original_file(db); - let source_root_id = db.file_source_root(file_id); - let path = db.file_relative_path(file_id); - let root = RelativePathBuf::default(); - let dir_path = path.parent().unwrap_or(&root); - let mod_name = path.file_stem().unwrap_or("unknown"); - let is_dir_owner = is_root || mod_name == "mod"; - - let file_mod = dir_path.join(format!("{}.rs", name)); - let dir_mod = dir_path.join(format!("{}/mod.rs", name)); - let file_dir_mod = dir_path.join(format!("{}/{}.rs", mod_name, name)); - let mut candidates = ArrayVec::<[_; 2]>::new(); - if is_dir_owner { - candidates.push(file_mod.clone()); - candidates.push(dir_mod); - } else { - candidates.push(file_dir_mod.clone()); - }; - let sr = db.source_root(source_root_id); - let points_to = candidates - .into_iter() - .filter_map(|path| sr.files.get(&path)) - .map(|&it| it) - .collect::>(); - let problem = if points_to.is_empty() { - Some(Problem::UnresolvedModule { - candidate: if is_dir_owner { file_mod } else { file_dir_mod }, - }) - } else { - None - }; - (points_to, problem) -} diff --git a/crates/ra_hir/src/nameres.rs b/crates/ra_hir/src/nameres.rs index 6f98ac071..baffbce6f 100644 --- a/crates/ra_hir/src/nameres.rs +++ b/crates/ra_hir/src/nameres.rs @@ -15,7 +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; +pub(crate) mod crate_def_map; use std::{time, sync::Arc}; @@ -29,8 +29,10 @@ use crate::{ Module, ModuleDef, Path, PathKind, PersistentHirDatabase, Crate, Name, - module_tree::{ModuleId, ModuleTree}, - nameres::lower::{ImportId, LoweredModule, ImportData}, + nameres::{ + crate_def_map::{CrateDefMap, ModuleId}, + lower::{ImportId, LoweredModule, ImportData} + }, }; /// `ItemMap` is the result of module name resolution. It contains, for each @@ -160,7 +162,7 @@ struct Resolver<'a, DB> { db: &'a DB, input: &'a FxHashMap>, krate: Crate, - module_tree: Arc, + def_map: Arc, processed_imports: FxHashSet<(ModuleId, ImportId)>, /// If module `a` has `use b::*`, then this contains the mapping b -> a (and the import) glob_imports: FxHashMap>, @@ -176,12 +178,11 @@ where input: &'a FxHashMap>, krate: Crate, ) -> Resolver<'a, DB> { - let module_tree = db.module_tree(krate); Resolver { db, input, krate, - module_tree, + def_map: db.crate_def_map(krate), processed_imports: FxHashSet::default(), glob_imports: FxHashMap::default(), result: ItemMap { @@ -254,9 +255,9 @@ where } // Populate modules - for (name, module_id) in module_id.children(&self.module_tree) { - let module = Module { module_id, krate: self.krate }; - self.add_module_item(&mut module_items, name, PerNs::types(module.into())); + for (name, module_id) in self.def_map[module_id].children.iter() { + let module = Module { module_id: *module_id, krate: self.krate }; + self.add_module_item(&mut module_items, name.clone(), PerNs::types(module.into())); } self.result.per_module.insert(module_id, module_items); @@ -479,8 +480,8 @@ enum ReachedFixedPoint { impl ItemMap { pub(crate) fn item_map_query(db: &impl PersistentHirDatabase, krate: Crate) -> Arc { let start = time::Instant::now(); - let module_tree = db.module_tree(krate); - let input = module_tree + let def_map = db.crate_def_map(krate); + let input = def_map .modules() .map(|module_id| (module_id, db.lower_module(Module { krate, module_id }))) .collect::>(); diff --git a/crates/ra_hir/src/nameres/crate_def_map.rs b/crates/ra_hir/src/nameres/crate_def_map.rs index 483878c78..d7ccb6584 100644 --- a/crates/ra_hir/src/nameres/crate_def_map.rs +++ b/crates/ra_hir/src/nameres/crate_def_map.rs @@ -48,25 +48,40 @@ mod tests; use rustc_hash::FxHashMap; use test_utils::tested_by; -use ra_arena::Arena; +use ra_arena::{Arena, RawId, impl_arena_id}; +use ra_db::FileId; + +use std::sync::Arc; use crate::{ - Name, Module, Path, PathKind, ModuleDef, Crate, + Name, Module, Path, PathKind, ModuleDef, Crate, Problem, HirFileId, PersistentHirDatabase, - module_tree::ModuleId, nameres::{ModuleScope, ResolveMode, ResolvePathResult, PerNs, Edition, ReachedFixedPoint}, + ids::{SourceItemId, SourceFileItemId}, }; -#[derive(Default, Debug)] -struct ModuleData { - parent: Option, - children: FxHashMap, - scope: ModuleScope, +pub(crate) use self::raw::RawItems; + +#[derive(Default, Debug, PartialEq, Eq)] +pub(crate) struct ModuleData { + pub(crate) parent: Option, + pub(crate) children: FxHashMap, + pub(crate) scope: ModuleScope, + /// None for root + pub(crate) declaration: Option, + /// None for inline modules. + /// + /// Note that non-inline modules, by definition, live inside non-macro file. + pub(crate) definition: Option, } +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub(crate) struct ModuleId(RawId); +impl_arena_id!(ModuleId); + /// Contans all top-level defs from a macro-expanded crate -#[derive(Debug)] -pub(crate) struct CrateDefMap { +#[derive(Debug, PartialEq, Eq)] +pub struct CrateDefMap { krate: Crate, edition: Edition, /// The prelude module for this crate. This either comes from an import @@ -77,19 +92,85 @@ pub(crate) struct CrateDefMap { root: ModuleId, modules: Arena, public_macros: FxHashMap, + problems: CrateDefMapProblems, +} + +#[derive(Default, Debug, PartialEq, Eq)] +pub(crate) struct CrateDefMapProblems { + problems: Vec<(SourceItemId, Problem)>, +} + +impl CrateDefMapProblems { + fn add(&mut self, source_item_id: SourceItemId, problem: Problem) { + self.problems.push((source_item_id, problem)) + } + + pub(crate) fn iter<'a>(&'a self) -> impl Iterator + 'a { + self.problems.iter().map(|(s, p)| (s, p)) + } } impl std::ops::Index for CrateDefMap { - type Output = ModuleScope; - fn index(&self, id: ModuleId) -> &ModuleScope { - &self.modules[id].scope + type Output = ModuleData; + fn index(&self, id: ModuleId) -> &ModuleData { + &self.modules[id] } } impl CrateDefMap { + pub(crate) fn crate_def_map_query( + db: &impl PersistentHirDatabase, + krate: Crate, + ) -> Arc { + let def_map = { + let edition = krate.edition(db); + let mut modules: Arena = Arena::default(); + let root = modules.alloc(ModuleData::default()); + CrateDefMap { + krate, + edition, + extern_prelude: FxHashMap::default(), + prelude: None, + root, + modules, + public_macros: FxHashMap::default(), + problems: CrateDefMapProblems::default(), + } + }; + let def_map = collector::collect_defs(db, def_map); + Arc::new(def_map) + } + + pub(crate) fn root(&self) -> ModuleId { + self.root + } + + pub(crate) fn problems(&self) -> &CrateDefMapProblems { + &self.problems + } + + pub(crate) fn modules<'a>(&'a self) -> impl Iterator + 'a { + self.modules.iter().map(|(id, _data)| id) + } + + pub(crate) fn find_module_by_source( + &self, + file_id: HirFileId, + decl_id: Option, + ) -> Option { + let decl_id = decl_id.map(|it| it.with_file_id(file_id)); + let (module_id, _module_data) = self.modules.iter().find(|(_module_id, module_data)| { + if decl_id.is_some() { + module_data.declaration == decl_id + } else { + module_data.definition.map(|it| it.into()) == Some(file_id) + } + })?; + Some(module_id) + } + // Returns Yes if we are sure that additions to `ItemMap` wouldn't change // the result. - #[allow(unused)] fn resolve_path_fp( &self, db: &impl PersistentHirDatabase, @@ -182,7 +263,7 @@ impl CrateDefMap { ); } - match self[module.module_id].items.get(&segment.name) { + match self[module.module_id].scope.items.get(&segment.name) { Some(res) if !res.def.is_none() => res.def, _ => { log::debug!("path segment {:?} not found", segment.name); @@ -225,7 +306,8 @@ impl CrateDefMap { } fn resolve_name_in_crate_root_or_extern_prelude(&self, name: &Name) -> PerNs { - let from_crate_root = self[self.root].items.get(name).map_or(PerNs::none(), |it| it.def); + let from_crate_root = + self[self.root].scope.items.get(name).map_or(PerNs::none(), |it| it.def); let from_extern_prelude = self.resolve_name_in_extern_prelude(name); from_crate_root.or(from_extern_prelude) @@ -241,7 +323,7 @@ impl CrateDefMap { // - current module / scope // - extern prelude // - std prelude - let from_scope = self[module].items.get(name).map_or(PerNs::none(), |it| it.def); + let from_scope = self[module].scope.items.get(name).map_or(PerNs::none(), |it| it.def); let from_extern_prelude = self.extern_prelude.get(name).map_or(PerNs::none(), |&it| PerNs::types(it)); let from_prelude = self.resolve_in_prelude(db, name); @@ -256,7 +338,7 @@ impl CrateDefMap { fn resolve_in_prelude(&self, db: &impl PersistentHirDatabase, name: &Name) -> PerNs { if let Some(prelude) = self.prelude { let resolution = if prelude.krate == self.krate { - self[prelude.module_id].items.get(name).cloned() + self[prelude.module_id].scope.items.get(name).cloned() } else { db.item_map(prelude.krate)[prelude.module_id].items.get(name).cloned() }; diff --git a/crates/ra_hir/src/nameres/crate_def_map/collector.rs b/crates/ra_hir/src/nameres/crate_def_map/collector.rs index cd328b755..2fbfa9e34 100644 --- a/crates/ra_hir/src/nameres/crate_def_map/collector.rs +++ b/crates/ra_hir/src/nameres/crate_def_map/collector.rs @@ -1,42 +1,25 @@ -use std::sync::Arc; - +use arrayvec::ArrayVec; use rustc_hash::FxHashMap; -use ra_arena::Arena; +use relative_path::RelativePathBuf; use test_utils::tested_by; +use ra_db::FileId; use crate::{ Function, Module, Struct, Enum, Const, Static, Trait, TypeAlias, - Crate, PersistentHirDatabase, HirFileId, Name, Path, + PersistentHirDatabase, HirFileId, Name, Path, Problem, KnownName, nameres::{Resolution, PerNs, ModuleDef, ReachedFixedPoint, ResolveMode}, 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( +pub(super) fn collect_defs( db: &impl PersistentHirDatabase, - krate: Crate, -) -> Arc { - let mut def_map = { - let edition = krate.edition(db); - let mut modules: Arena = Arena::default(); - let root = modules.alloc(ModuleData::default()); - CrateDefMap { - krate, - edition, - extern_prelude: FxHashMap::default(), - prelude: None, - root, - modules, - public_macros: FxHashMap::default(), - } - }; - + mut def_map: CrateDefMap, +) -> CrateDefMap { // populate external prelude - for dep in krate.dependencies(db) { + for dep in def_map.krate.dependencies(db) { log::debug!("crate dep {:?} -> {:?}", dep.name, dep.krate); if let Some(module) = dep.krate.root_module(db) { def_map.extern_prelude.insert(dep.name.clone(), module.into()); @@ -52,7 +35,6 @@ pub(crate) fn crate_def_map_query( let mut collector = DefCollector { db, - krate, def_map, glob_imports: FxHashMap::default(), unresolved_imports: Vec::new(), @@ -60,14 +42,12 @@ pub(crate) fn crate_def_map_query( global_macro_scope: FxHashMap::default(), }; collector.collect(); - let def_map = collector.finish(); - Arc::new(def_map) + collector.finish() } /// Walks the tree of module recursively struct DefCollector { db: DB, - krate: Crate, def_map: CrateDefMap, glob_imports: FxHashMap>, unresolved_imports: Vec<(ModuleId, raw::ImportId, raw::ImportData)>, @@ -75,23 +55,16 @@ struct DefCollector { global_macro_scope: FxHashMap, } -/// 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 file_id = crate_graph.crate_root(self.def_map.krate.crate_id()); + let raw_items = self.db.raw_items(file_id); let module_id = self.def_map.root; + self.def_map.modules[module_id].definition = Some(file_id); ModCollector { def_collector: &mut *self, module_id, @@ -123,10 +96,6 @@ where } } - fn alloc_module(&mut self) -> ModuleId { - self.def_map.modules.alloc(ModuleData::default()) - } - fn resolve_imports(&mut self) -> ReachedFixedPoint { let mut imports = std::mem::replace(&mut self.unresolved_imports, Vec::new()); let mut resolved = Vec::new(); @@ -184,7 +153,7 @@ where if import.is_prelude { tested_by!(std_prelude); self.def_map.prelude = Some(m); - } else if m.krate != self.krate { + } else if m.krate != self.def_map.krate { tested_by!(glob_across_crates); // glob import from other crate => we can just import everything once let item_map = self.db.item_map(m.krate); @@ -199,7 +168,7 @@ where // glob import from same crate => we do an initial // import, and then need to propagate any further // additions - let scope = &self.def_map[m.module_id]; + let scope = &self.def_map[m.module_id].scope; let items = scope .items .iter() @@ -243,11 +212,9 @@ where log::debug!("resolved import {:?} ({:?}) to {:?}", name, import, def); // extern crates in the crate root are special-cased to insert entries into the extern prelude: rust-lang/rust#54658 - if let Some(root_module) = self.krate.root_module(self.db) { - if import.is_extern_crate && module_id == root_module.module_id { - if let Some(def) = def.take_types() { - self.def_map.extern_prelude.insert(name.clone(), def); - } + if import.is_extern_crate && module_id == self.def_map.root { + if let Some(def) = def.take_types() { + self.def_map.extern_prelude.insert(name.clone(), def); } } let resolution = Resolution { def, import: Some(import_id) }; @@ -324,8 +291,7 @@ where Some(it) => it, _ => return true, }; - // FIXME: this should be a proper query - let def_map = crate_def_map_query(self.db, krate); + let def_map = self.db.crate_def_map(krate); let rules = def_map.public_macros.get(&path.segments[1].name).cloned(); resolved.push((*module_id, *call_id, rules, tt.clone())); false @@ -367,6 +333,14 @@ where } } +/// 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 ModCollector<'_, &'_ mut DefCollector<&'_ DB>> where DB: PersistentHirDatabase, @@ -389,8 +363,12 @@ where 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()); + raw::ModuleData::Definition { name, items, source_item_id } => { + let module_id = self.push_child_module( + name.clone(), + source_item_id.with_file_id(self.file_id), + None, + ); ModCollector { def_collector: &mut *self.def_collector, module_id, @@ -400,13 +378,20 @@ where .collect(&*items); } // out of line module, resovle, parse and recurse - raw::ModuleData::Declaration { name } => { - let module_id = self.push_child_module(name.clone()); + raw::ModuleData::Declaration { name, source_item_id } => { + let source_item_id = source_item_id.with_file_id(self.file_id); 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); + let (file_ids, problem) = + resolve_submodule(self.def_collector.db, self.file_id, name, is_root); + + if let Some(problem) = problem { + self.def_collector.def_map.problems.add(source_item_id, problem) + } + + if let Some(&file_id) = file_ids.first() { + let module_id = + self.push_child_module(name.clone(), source_item_id, Some(file_id)); + let raw_items = self.def_collector.db.raw_items(file_id); ModCollector { def_collector: &mut *self.def_collector, module_id, @@ -419,15 +404,23 @@ where } } - 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); + fn push_child_module( + &mut self, + name: Name, + declaration: SourceItemId, + definition: Option, + ) -> ModuleId { + let modules = &mut self.def_collector.def_map.modules; + let res = modules.alloc(ModuleData::default()); + modules[res].parent = Some(self.module_id); + modules[res].declaration = Some(declaration); + modules[res].definition = definition; + 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 module = Module { krate: self.def_collector.def_map.krate, module_id: self.module_id }; let ctx = LocationCtx::new(self.def_collector.db, module, self.file_id.into()); macro_rules! id { () => { @@ -462,7 +455,7 @@ where 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 }, + module: Module { krate: self.def_collector.def_map.krate, module_id: self.module_id }, source_item_id, } .id(self.def_collector.db); @@ -491,3 +484,44 @@ where fn is_macro_rules(path: &Path) -> bool { path.as_ident().and_then(Name::as_known_name) == Some(KnownName::MacroRules) } + +fn resolve_submodule( + db: &impl PersistentHirDatabase, + file_id: HirFileId, + name: &Name, + is_root: bool, +) -> (Vec, Option) { + // FIXME: handle submodules of inline modules properly + let file_id = file_id.original_file(db); + let source_root_id = db.file_source_root(file_id); + let path = db.file_relative_path(file_id); + let root = RelativePathBuf::default(); + let dir_path = path.parent().unwrap_or(&root); + let mod_name = path.file_stem().unwrap_or("unknown"); + let is_dir_owner = is_root || mod_name == "mod"; + + let file_mod = dir_path.join(format!("{}.rs", name)); + let dir_mod = dir_path.join(format!("{}/mod.rs", name)); + let file_dir_mod = dir_path.join(format!("{}/{}.rs", mod_name, name)); + let mut candidates = ArrayVec::<[_; 2]>::new(); + if is_dir_owner { + candidates.push(file_mod.clone()); + candidates.push(dir_mod); + } else { + candidates.push(file_dir_mod.clone()); + }; + let sr = db.source_root(source_root_id); + let points_to = candidates + .into_iter() + .filter_map(|path| sr.files.get(&path)) + .map(|&it| it) + .collect::>(); + let problem = if points_to.is_empty() { + Some(Problem::UnresolvedModule { + candidate: if is_dir_owner { file_mod } else { file_dir_mod }, + }) + } else { + None + }; + (points_to, problem) +} diff --git a/crates/ra_hir/src/nameres/crate_def_map/raw.rs b/crates/ra_hir/src/nameres/crate_def_map/raw.rs index fe832b8da..f064f722c 100644 --- a/crates/ra_hir/src/nameres/crate_def_map/raw.rs +++ b/crates/ra_hir/src/nameres/crate_def_map/raw.rs @@ -3,6 +3,7 @@ use std::{ ops::Index, }; +use test_utils::tested_by; use ra_db::FileId; use ra_arena::{Arena, impl_arena_id, RawId}; use ra_syntax::{ @@ -15,8 +16,8 @@ use crate::{ ids::{SourceFileItemId, SourceFileItems}, }; -#[derive(Default, PartialEq, Eq)] -pub(crate) struct RawItems { +#[derive(Debug, Default, PartialEq, Eq)] +pub struct RawItems { modules: Arena, imports: Arena, defs: Arena, @@ -26,18 +27,21 @@ pub(crate) struct RawItems { } impl RawItems { - pub(crate) fn items(&self) -> &[RawItem] { - &self.items - } - - pub(crate) fn raw_items_query(db: &impl PersistentHirDatabase, file_id: FileId) -> RawItems { + pub(crate) fn raw_items_query( + db: &impl PersistentHirDatabase, + file_id: FileId, + ) -> Arc { 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 + Arc::new(collector.raw_items) + } + + pub(crate) fn items(&self) -> &[RawItem] { + &self.items } // We can't use queries during name resolution for fear of cycles, so this @@ -81,7 +85,7 @@ impl Index for RawItems { } } -#[derive(PartialEq, Eq, Clone, Copy)] +#[derive(Debug, PartialEq, Eq, Clone, Copy)] pub(crate) enum RawItem { Module(Module), Import(ImportId), @@ -89,24 +93,24 @@ pub(crate) enum RawItem { Macro(Macro), } -#[derive(Clone, Copy, PartialEq, Eq, Hash)] +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] pub(crate) struct Module(RawId); impl_arena_id!(Module); -#[derive(PartialEq, Eq)] +#[derive(Debug, PartialEq, Eq)] pub(crate) enum ModuleData { - Declaration { name: Name }, - Definition { name: Name, items: Vec }, + Declaration { name: Name, source_item_id: SourceFileItemId }, + Definition { name: Name, source_item_id: SourceFileItemId, items: Vec }, } pub(crate) use crate::nameres::lower::ImportId; pub(super) use crate::nameres::lower::ImportData; -#[derive(Clone, Copy, PartialEq, Eq, Hash)] +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] pub(crate) struct Def(RawId); impl_arena_id!(Def); -#[derive(PartialEq, Eq)] +#[derive(Debug, PartialEq, Eq)] pub(crate) struct DefData { pub(crate) source_item_id: SourceFileItemId, pub(crate) name: Name, @@ -124,11 +128,11 @@ pub(crate) enum DefKind { TypeAlias, } -#[derive(Clone, Copy, PartialEq, Eq, Hash)] +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] pub(crate) struct Macro(RawId); impl_arena_id!(Macro); -#[derive(PartialEq, Eq)] +#[derive(Debug, PartialEq, Eq)] pub(crate) struct MacroData { pub(crate) source_item_id: SourceFileItemId, pub(crate) path: Path, @@ -191,18 +195,25 @@ impl RawItemsCollector { Some(it) => it.as_name(), None => return, }; + let source_item_id = self.source_file_items.id_of_unchecked(module.syntax()); if module.has_semi() { - let item = self.raw_items.modules.alloc(ModuleData::Declaration { name }); + let item = + self.raw_items.modules.alloc(ModuleData::Declaration { name, source_item_id }); 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() }); + let item = self.raw_items.modules.alloc(ModuleData::Definition { + name, + source_item_id, + items: Vec::new(), + }); self.process_module(Some(item), item_list); self.push_item(current_module, RawItem::Module(item)); + return; } + tested_by!(name_res_works_for_broken_modules); } fn add_use_item(&mut self, current_module: Option, use_item: &ast::UseItem) { diff --git a/crates/ra_hir/src/nameres/crate_def_map/tests.rs b/crates/ra_hir/src/nameres/crate_def_map/tests.rs index a56dbaf90..742a19e5c 100644 --- a/crates/ra_hir/src/nameres/crate_def_map/tests.rs +++ b/crates/ra_hir/src/nameres/crate_def_map/tests.rs @@ -15,7 +15,7 @@ fn compute_crate_def_map(fixture: &str, graph: Option) -> Arc } let crate_id = db.crate_graph().iter().next().unwrap(); let krate = Crate { crate_id }; - collector::crate_def_map_query(&db, krate) + db.crate_def_map(krate) } fn render_crate_def_map(map: &CrateDefMap) -> String { diff --git a/crates/ra_hir/src/nameres/tests.rs b/crates/ra_hir/src/nameres/tests.rs index 9b151bb0c..961e442a9 100644 --- a/crates/ra_hir/src/nameres/tests.rs +++ b/crates/ra_hir/src/nameres/tests.rs @@ -7,7 +7,7 @@ use crate::{ ItemMap, PersistentHirDatabase, mock::MockDatabase, - module_tree::ModuleId, + nameres::crate_def_map::ModuleId, }; use super::Resolution; @@ -359,6 +359,7 @@ fn std_prelude() { let main_id = db.file_id_of("/main.rs"); let module = crate::source_binder::module_from_file_id(&db, main_id).unwrap(); + eprintln!("module = {:?}", module); let krate = module.krate(&db).unwrap(); let item_map = db.item_map(krate); diff --git a/crates/ra_hir/src/source_binder.rs b/crates/ra_hir/src/source_binder.rs index 4a9921a85..62b699a64 100644 --- a/crates/ra_hir/src/source_binder.rs +++ b/crates/ra_hir/src/source_binder.rs @@ -80,8 +80,8 @@ fn module_from_source( let source_root_id = db.file_source_root(file_id.as_original_file()); db.source_root_crates(source_root_id).iter().map(|&crate_id| Crate { crate_id }).find_map( |krate| { - let module_tree = db.module_tree(krate); - let module_id = module_tree.find_module_by_source(file_id, decl_id)?; + let def_map = db.crate_def_map(krate); + let module_id = def_map.find_module_by_source(file_id, decl_id)?; Some(Module { krate, module_id }) }, ) diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs index 94b757af2..7c77474b0 100644 --- a/crates/ra_hir/src/ty/method_resolution.rs +++ b/crates/ra_hir/src/ty/method_resolution.rs @@ -7,10 +7,12 @@ use std::sync::Arc; use rustc_hash::FxHashMap; use crate::{ - HirDatabase, module_tree::ModuleId, Module, Crate, Name, Function, Trait, + HirDatabase, Module, Crate, Name, Function, Trait, ids::TraitId, impl_block::{ImplId, ImplBlock, ImplItem}, ty::{AdtDef, Ty}, + nameres::crate_def_map::ModuleId, + }; /// This is used as a key for indexing impls. -- cgit v1.2.3