From 0e4b710af83844f4a7c471c5335c99aaaa25a90c Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Wed, 28 Nov 2018 03:42:26 +0300 Subject: introduce hir crate --- crates/ra_hir/src/module/nameres.rs | 444 ++++++++++++++++++++++++++++++++++++ 1 file changed, 444 insertions(+) create mode 100644 crates/ra_hir/src/module/nameres.rs (limited to 'crates/ra_hir/src/module/nameres.rs') diff --git a/crates/ra_hir/src/module/nameres.rs b/crates/ra_hir/src/module/nameres.rs new file mode 100644 index 000000000..513a37646 --- /dev/null +++ b/crates/ra_hir/src/module/nameres.rs @@ -0,0 +1,444 @@ +//! Name resolution algorithm. The end result of the algorithm is `ItemMap`: a +//! map with maps each module to it's scope: the set of items, visible in the +//! module. That is, we only resolve imports here, name resolution of item +//! bodies will be done in a separate step. +//! +//! Like Rustc, we use an interative per-crate algorithm: we start with scopes +//! containing only directly defined items, and then iteratively resolve +//! imports. +//! +//! To make this work nicely in the IDE scenarios, we place `InputModuleItems` +//! in between raw syntax and name resolution. `InputModuleItems` are computed +//! using only the module's syntax, and it is all directly defined items plus +//! imports. The plain is to make `InputModuleItems` independent of local +//! modifications (that is, typing inside a function shold not change IMIs), +//! such that the results of name resolution can be preserved unless the module +//! structure itself is modified. +use std::{ + sync::Arc, +}; + +use rustc_hash::FxHashMap; +use ra_syntax::{ + TextRange, + SmolStr, SyntaxKind::{self, *}, + ast::{self, AstNode} +}; +use ra_db::SourceRootId; + +use crate::{ + Cancelable, FileId, + DefId, DefLoc, + SourceItemId, SourceFileItemId, SourceFileItems, + Path, PathKind, + HirDatabase, + module::{ModuleId, ModuleTree}, +}; + +/// Item map is the result of the name resolution. Item map contains, for each +/// module, the set of visible items. +#[derive(Default, Debug, PartialEq, Eq)] +pub(crate) struct ItemMap { + pub(crate) per_module: FxHashMap, +} + +#[derive(Debug, Default, PartialEq, Eq, Clone)] +pub(crate) struct ModuleScope { + items: FxHashMap, +} + +impl ModuleScope { + pub(crate) fn entries<'a>(&'a self) -> impl Iterator + 'a { + self.items.iter() + } + pub(crate) fn get(&self, name: &SmolStr) -> Option<&Resolution> { + self.items.get(name) + } +} + +/// A set of items and imports declared inside a module, without relation to +/// other modules. +/// +/// This stands in-between raw syntax and name resolution and alow us to avoid +/// recomputing name res: if `InputModuleItems` are the same, we can avoid +/// running name resolution. +#[derive(Debug, Default, PartialEq, Eq)] +pub(crate) struct InputModuleItems { + items: Vec, + imports: Vec, +} + +#[derive(Debug, PartialEq, Eq)] +struct ModuleItem { + id: SourceFileItemId, + name: SmolStr, + kind: SyntaxKind, + vis: Vis, +} + +#[derive(Debug, PartialEq, Eq)] +enum Vis { + // Priv, + Other, +} + +#[derive(Debug, Clone, PartialEq, Eq)] +struct Import { + path: Path, + kind: ImportKind, +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub(crate) struct NamedImport { + file_item_id: SourceFileItemId, + relative_range: TextRange, +} + +impl NamedImport { + pub(crate) fn range(&self, db: &impl HirDatabase, file_id: FileId) -> TextRange { + let source_item_id = SourceItemId { + file_id, + item_id: self.file_item_id, + }; + let syntax = db.file_item(source_item_id); + let offset = syntax.borrowed().range().start(); + self.relative_range + offset + } +} + +#[derive(Debug, Clone, PartialEq, Eq)] +enum ImportKind { + Glob, + Named(NamedImport), +} + +/// Resolution is basically `DefId` atm, but it should account for stuff like +/// multiple namespaces, ambiguity and errors. +#[derive(Debug, Clone, PartialEq, Eq)] +pub(crate) struct Resolution { + /// None for unresolved + pub(crate) def_id: Option, + /// ident by whitch this is imported into local scope. + pub(crate) import: Option, +} + +// #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] +// enum Namespace { +// Types, +// Values, +// } + +// #[derive(Debug)] +// struct PerNs { +// types: Option, +// values: Option, +// } + +impl InputModuleItems { + pub(crate) fn new<'a>( + file_items: &SourceFileItems, + items: impl Iterator>, + ) -> InputModuleItems { + let mut res = InputModuleItems::default(); + for item in items { + res.add_item(file_items, item); + } + res + } + + fn add_item(&mut self, file_items: &SourceFileItems, item: ast::ModuleItem) -> Option<()> { + match item { + ast::ModuleItem::StructDef(it) => self.items.push(ModuleItem::new(file_items, it)?), + ast::ModuleItem::EnumDef(it) => self.items.push(ModuleItem::new(file_items, it)?), + ast::ModuleItem::FnDef(it) => self.items.push(ModuleItem::new(file_items, it)?), + ast::ModuleItem::TraitDef(it) => self.items.push(ModuleItem::new(file_items, it)?), + ast::ModuleItem::TypeDef(it) => self.items.push(ModuleItem::new(file_items, it)?), + ast::ModuleItem::ImplItem(_) => { + // impls don't define items + } + ast::ModuleItem::UseItem(it) => self.add_use_item(file_items, it), + ast::ModuleItem::ExternCrateItem(_) => { + // TODO + } + ast::ModuleItem::ConstDef(it) => self.items.push(ModuleItem::new(file_items, it)?), + ast::ModuleItem::StaticDef(it) => self.items.push(ModuleItem::new(file_items, it)?), + ast::ModuleItem::Module(it) => self.items.push(ModuleItem::new(file_items, it)?), + } + Some(()) + } + + fn add_use_item(&mut self, file_items: &SourceFileItems, item: ast::UseItem) { + let file_item_id = file_items.id_of(item.syntax()); + let start_offset = item.syntax().range().start(); + Path::expand_use_item(item, |path, range| { + let kind = match range { + None => ImportKind::Glob, + Some(range) => ImportKind::Named(NamedImport { + file_item_id, + relative_range: range - start_offset, + }), + }; + self.imports.push(Import { kind, path }) + }) + } +} + +impl ModuleItem { + fn new<'a>(file_items: &SourceFileItems, item: impl ast::NameOwner<'a>) -> Option { + let name = item.name()?.text(); + let kind = item.syntax().kind(); + let vis = Vis::Other; + let id = file_items.id_of(item.syntax()); + let res = ModuleItem { + id, + name, + kind, + vis, + }; + Some(res) + } +} + +pub(crate) struct Resolver<'a, DB> { + pub db: &'a DB, + pub input: &'a FxHashMap>, + pub source_root: SourceRootId, + pub module_tree: Arc, + pub result: ItemMap, +} + +impl<'a, DB> Resolver<'a, DB> +where + DB: HirDatabase, +{ + pub(crate) fn resolve(mut self) -> Cancelable { + for (&module_id, items) in self.input.iter() { + self.populate_module(module_id, items) + } + + for &module_id in self.input.keys() { + self.db.check_canceled()?; + self.resolve_imports(module_id); + } + Ok(self.result) + } + + fn populate_module(&mut self, module_id: ModuleId, input: &InputModuleItems) { + let file_id = module_id.source(&self.module_tree).file_id(); + + let mut module_items = ModuleScope::default(); + + for import in input.imports.iter() { + if let Some(name) = import.path.segments.iter().last() { + if let ImportKind::Named(import) = import.kind { + module_items.items.insert( + name.clone(), + Resolution { + def_id: None, + import: Some(import), + }, + ); + } + } + } + + for item in input.items.iter() { + if item.kind == MODULE { + // handle submodules separatelly + continue; + } + let def_loc = DefLoc::Item { + source_item_id: SourceItemId { + file_id, + item_id: item.id, + }, + }; + let def_id = def_loc.id(self.db); + let resolution = Resolution { + def_id: Some(def_id), + import: None, + }; + module_items.items.insert(item.name.clone(), resolution); + } + + for (name, mod_id) in module_id.children(&self.module_tree) { + let def_loc = DefLoc::Module { + id: mod_id, + source_root: self.source_root, + }; + let def_id = def_loc.id(self.db); + let resolution = Resolution { + def_id: Some(def_id), + import: None, + }; + module_items.items.insert(name, resolution); + } + + self.result.per_module.insert(module_id, module_items); + } + + fn resolve_imports(&mut self, module_id: ModuleId) { + for import in self.input[&module_id].imports.iter() { + self.resolve_import(module_id, import); + } + } + + fn resolve_import(&mut self, module_id: ModuleId, import: &Import) { + let ptr = match import.kind { + ImportKind::Glob => return, + ImportKind::Named(ptr) => ptr, + }; + + let mut curr = match import.path.kind { + // TODO: handle extern crates + PathKind::Plain => return, + PathKind::Self_ => module_id, + PathKind::Super => { + match module_id.parent(&self.module_tree) { + Some(it) => it, + // TODO: error + None => return, + } + } + PathKind::Crate => module_id.crate_root(&self.module_tree), + }; + + for (i, name) in import.path.segments.iter().enumerate() { + let is_last = i == import.path.segments.len() - 1; + + let def_id = match self.result.per_module[&curr].items.get(name) { + None => return, + Some(res) => match res.def_id { + Some(it) => it, + None => return, + }, + }; + + if !is_last { + curr = match def_id.loc(self.db) { + DefLoc::Module { id, .. } => id, + _ => return, + } + } else { + self.update(module_id, |items| { + let res = Resolution { + def_id: Some(def_id), + import: Some(ptr), + }; + items.items.insert(name.clone(), res); + }) + } + } + } + + fn update(&mut self, module_id: ModuleId, f: impl FnOnce(&mut ModuleScope)) { + let module_items = self.result.per_module.get_mut(&module_id).unwrap(); + f(module_items) + } +} + +#[cfg(test)] +mod tests { + use ra_db::FilesDatabase; + use crate::{ + AnalysisChange, + mock_analysis::{MockAnalysis, analysis_and_position}, + hir::{self, HirDatabase}, +}; + use super::*; + + fn item_map(fixture: &str) -> (Arc, ModuleId) { + let (analysis, pos) = analysis_and_position(fixture); + let db = analysis.imp.db; + let source_root = db.file_source_root(pos.file_id); + let descr = hir::Module::guess_from_position(&*db, pos) + .unwrap() + .unwrap(); + let module_id = descr.module_id; + (db.item_map(source_root).unwrap(), module_id) + } + + #[test] + fn test_item_map() { + let (item_map, module_id) = item_map( + " + //- /lib.rs + mod foo; + + use crate::foo::bar::Baz; + <|> + + //- /foo/mod.rs + pub mod bar; + + //- /foo/bar.rs + pub struct Baz; + ", + ); + let name = SmolStr::from("Baz"); + let resolution = &item_map.per_module[&module_id].items[&name]; + assert!(resolution.def_id.is_some()); + } + + #[test] + fn typing_inside_a_function_should_not_invalidate_item_map() { + let mock_analysis = MockAnalysis::with_files( + " + //- /lib.rs + mod foo; + + use crate::foo::bar::Baz; + + fn foo() -> i32 { + 1 + 1 + } + //- /foo/mod.rs + pub mod bar; + + //- /foo/bar.rs + pub struct Baz; + ", + ); + + let file_id = mock_analysis.id_of("/lib.rs"); + let mut host = mock_analysis.analysis_host(); + + let source_root = host.analysis().imp.db.file_source_root(file_id); + + { + let db = host.analysis().imp.db; + let events = db.log_executed(|| { + db.item_map(source_root).unwrap(); + }); + assert!(format!("{:?}", events).contains("item_map")) + } + + let mut change = AnalysisChange::new(); + + change.change_file( + file_id, + " + mod foo; + + use crate::foo::bar::Baz; + + fn foo() -> i32 { 92 } + " + .to_string(), + ); + + host.apply_change(change); + + { + let db = host.analysis().imp.db; + let events = db.log_executed(|| { + db.item_map(source_root).unwrap(); + }); + assert!( + !format!("{:?}", events).contains("_item_map"), + "{:#?}", + events + ) + } + } +} -- cgit v1.2.3