From dc477db757247d5184250bffe9dd0c38dd867778 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Tue, 23 Oct 2018 19:15:31 +0300 Subject: Introduce ModuleId Previously, module was synonym with a file, and so a module could have had several parents. This commit introduces a separate module concept, such that each module has only one parent, but a single file can correspond to different modules. --- crates/ra_analysis/src/descriptors/module/imp.rs | 146 +++++++++++++++++++ crates/ra_analysis/src/descriptors/module/mod.rs | 176 +++++++++++++++++++++++ 2 files changed, 322 insertions(+) create mode 100644 crates/ra_analysis/src/descriptors/module/imp.rs create mode 100644 crates/ra_analysis/src/descriptors/module/mod.rs (limited to 'crates/ra_analysis/src/descriptors/module') diff --git a/crates/ra_analysis/src/descriptors/module/imp.rs b/crates/ra_analysis/src/descriptors/module/imp.rs new file mode 100644 index 000000000..22e4bd785 --- /dev/null +++ b/crates/ra_analysis/src/descriptors/module/imp.rs @@ -0,0 +1,146 @@ +use std::sync::Arc; + +use relative_path::RelativePathBuf; +use rustc_hash::{FxHashMap, FxHashSet}; +use ra_syntax::{ + SmolStr, + ast::{self, NameOwner}, +}; + +use crate::{ + FileId, Cancelable, FileResolverImp, + db, +}; + +use super::{ + ModuleData, ModuleTree, ModuleId, LinkId, LinkData, Problem, ModulesDatabase +}; + + +pub(super) fn submodules(db: &impl ModulesDatabase, file_id: FileId) -> Cancelable>> { + db::check_canceled(db)?; + let file = db.file_syntax(file_id); + let root = file.ast(); + let submodules = modules(root).map(|(name, _)| name).collect(); + Ok(Arc::new(submodules)) +} + +pub(super) fn modules(root: ast::Root<'_>) -> impl Iterator)> { + root.modules().filter_map(|module| { + let name = module.name()?.text(); + if !module.has_semi() { + return None; + } + Some((name, module)) + }) +} + +pub(super) fn module_tree(db: &impl ModulesDatabase) -> Cancelable> { + db::check_canceled(db)?; + let res = create_module_tree(db)?; + Ok(Arc::new(res)) +} + + +#[derive(Clone, Hash, PartialEq, Eq, Debug)] +pub struct Submodule { + pub name: SmolStr, +} + + +fn create_module_tree<'a>( + db: &impl ModulesDatabase, +) -> Cancelable { + let mut tree = ModuleTree { + mods: Vec::new(), + links: Vec::new(), + }; + + let mut roots = FxHashMap::default(); + let mut visited = FxHashSet::default(); + + for &file_id in db.file_set().files.iter() { + if visited.contains(&file_id) { + continue; // TODO: use explicit crate_roots here + } + assert!(!roots.contains_key(&file_id)); + let module_id = build_subtree(db, &mut tree, &mut visited, &mut roots, None, file_id)?; + roots.insert(file_id, module_id); + } + Ok(tree) +} + +fn build_subtree( + db: &impl ModulesDatabase, + tree: &mut ModuleTree, + visited: &mut FxHashSet, + roots: &mut FxHashMap, + parent: Option, + file_id: FileId, +) -> Cancelable { + visited.insert(file_id); + let id = tree.push_mod(ModuleData { + file_id, + parent, + children: Vec::new(), + }); + let file_set = db.file_set(); + let file_resolver = &file_set.resolver; + for name in db.submodules(file_id)?.iter() { + let (points_to, problem) = resolve_submodule(file_id, name, file_resolver); + let link = tree.push_link(LinkData { + name: name.clone(), + owner: id, + points_to: Vec::new(), + problem: None, + }); + + let points_to = points_to + .into_iter() + .map(|file_id| match roots.remove(&file_id) { + Some(module_id) => { + tree.module_mut(module_id).parent = Some(link); + Ok(module_id) + } + None => build_subtree(db, tree, visited, roots, Some(link), file_id), + }) + .collect::>>()?; + tree.link_mut(link).points_to = points_to; + tree.link_mut(link).problem = problem; + } + Ok(id) +} + +fn resolve_submodule( + file_id: FileId, + name: &SmolStr, + file_resolver: &FileResolverImp, +) -> (Vec, Option) { + let mod_name = file_resolver.file_stem(file_id); + let is_dir_owner = mod_name == "mod" || mod_name == "lib" || mod_name == "main"; + + let file_mod = RelativePathBuf::from(format!("../{}.rs", name)); + let dir_mod = RelativePathBuf::from(format!("../{}/mod.rs", name)); + let points_to: Vec; + let problem: Option; + if is_dir_owner { + points_to = [&file_mod, &dir_mod] + .iter() + .filter_map(|path| file_resolver.resolve(file_id, path)) + .collect(); + problem = if points_to.is_empty() { + Some(Problem::UnresolvedModule { + candidate: file_mod, + }) + } else { + None + } + } else { + points_to = Vec::new(); + problem = Some(Problem::NotDirOwner { + move_to: RelativePathBuf::from(format!("../{}/mod.rs", mod_name)), + candidate: file_mod, + }); + } + (points_to, problem) +} diff --git a/crates/ra_analysis/src/descriptors/module/mod.rs b/crates/ra_analysis/src/descriptors/module/mod.rs new file mode 100644 index 000000000..52da650b3 --- /dev/null +++ b/crates/ra_analysis/src/descriptors/module/mod.rs @@ -0,0 +1,176 @@ +mod imp; + +use std::sync::Arc; + +use relative_path::RelativePathBuf; +use ra_syntax::{ast::{self, NameOwner, AstNode}, SmolStr, SyntaxNode}; + +use crate::{ + FileId, Cancelable, + db::SyntaxDatabase, +}; + +salsa::query_group! { + pub(crate) trait ModulesDatabase: SyntaxDatabase { + fn module_tree() -> Cancelable> { + type ModuleTreeQuery; + use fn imp::module_tree; + } + fn submodules(file_id: FileId) -> Cancelable>> { + type SubmodulesQuery; + use fn imp::submodules; + } + } +} + + +#[derive(Debug, PartialEq, Eq, Hash)] +pub(crate) struct ModuleTree { + mods: Vec, + links: Vec, +} + +impl ModuleTree { + pub(crate) fn modules_for_file(&self, file_id: FileId) -> Vec { + self.mods.iter() + .enumerate() + .filter(|(_idx, it)| it.file_id == file_id).map(|(idx, _)| ModuleId(idx as u32)) + .collect() + } + + pub(crate) fn any_module_for_file(&self, file_id: FileId) -> Option { + self.modules_for_file(file_id).pop() + } +} + +#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)] +pub(crate) struct ModuleId(u32); + +#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)] +pub(crate) struct LinkId(u32); + +#[derive(Clone, Debug, Hash, PartialEq, Eq)] +pub enum Problem { + UnresolvedModule { + candidate: RelativePathBuf, + }, + NotDirOwner { + move_to: RelativePathBuf, + candidate: RelativePathBuf, + }, +} + +impl ModuleId { + pub(crate) fn file_id(self, tree: &ModuleTree) -> FileId { + tree.module(self).file_id + } + pub(crate) fn parent_link(self, tree: &ModuleTree) -> Option { + tree.module(self).parent + } + pub(crate) fn parent(self, tree: &ModuleTree) -> Option { + let link = self.parent_link(tree)?; + Some(tree.link(link).owner) + } + pub(crate) fn root(self, tree: &ModuleTree) -> ModuleId { + let mut curr = self; + let mut i = 0; + while let Some(next) = curr.parent(tree) { + curr = next; + i += 1; + if i > 100 { + return self; + } + } + curr + } + pub(crate) fn child(self, tree: &ModuleTree, name: &str) -> Option { + let link = tree.module(self) + .children + .iter() + .map(|&it| tree.link(it)) + .find(|it| it.name == name)?; + Some(*link.points_to.first()?) + } + pub(crate) fn problems( + self, + tree: &ModuleTree, + root: ast::Root, + ) -> Vec<(SyntaxNode, Problem)> { + tree.module(self) + .children + .iter() + .filter_map(|&it| { + let p = tree.link(it).problem.clone()?; + let s = it.bind_source(tree, root); + let s = s.name().unwrap().syntax().owned(); + Some((s, p)) + }) + .collect() + } +} + +impl LinkId { + pub(crate) fn name(self, tree: &ModuleTree) -> SmolStr { + tree.link(self).name.clone() + } + pub(crate) fn owner(self, tree: &ModuleTree) -> ModuleId { + tree.link(self).owner + } + fn points_to(self, tree: &ModuleTree) -> &[ModuleId] { + &tree.link(self).points_to + } + pub(crate) fn bind_source<'a>( + self, + tree: &ModuleTree, + root: ast::Root<'a>, + ) -> ast::Module<'a> { + imp::modules(root) + .find(|(name, _)| name == &tree.link(self).name) + .unwrap() + .1 + } +} + +#[derive(Debug, PartialEq, Eq, Hash)] +struct ModuleData { + file_id: FileId, + parent: Option, + children: Vec, +} + +#[derive(Hash, Debug, PartialEq, Eq)] +struct LinkData { + owner: ModuleId, + name: SmolStr, + points_to: Vec, + problem: Option, +} + + +impl ModuleTree { + fn module(&self, id: ModuleId) -> &ModuleData { + &self.mods[id.0 as usize] + } + fn module_mut(&mut self, id: ModuleId) -> &mut ModuleData { + &mut self.mods[id.0 as usize] + } + fn link(&self, id: LinkId) -> &LinkData { + &self.links[id.0 as usize] + } + fn link_mut(&mut self, id: LinkId) -> &mut LinkData { + &mut self.links[id.0 as usize] + } + + fn push_mod(&mut self, data: ModuleData) -> ModuleId { + let id = ModuleId(self.mods.len() as u32); + self.mods.push(data); + id + } + fn push_link(&mut self, data: LinkData) -> LinkId { + let id = LinkId(self.links.len() as u32); + self.mods[data.owner.0 as usize].children.push(id); + self.links.push(data); + id + } +} + -- cgit v1.2.3