From 58674dc3c415142dbdd93b990d9f5b4fe10bef69 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Sat, 15 Sep 2018 20:29:22 +0300 Subject: ModuleTreeDescriptor --- crates/libanalysis/src/db/mod.rs | 12 +- crates/libanalysis/src/descriptors.rs | 217 ++++++++++++++++++++++++++ crates/libanalysis/src/imp.rs | 124 +++++++-------- crates/libanalysis/src/lib.rs | 1 + crates/libanalysis/src/module_map_db/descr.rs | 29 ---- crates/libanalysis/src/module_map_db/mod.rs | 47 ++---- crates/libanalysis/src/roots.rs | 12 +- crates/libeditor/src/line_index.rs | 2 +- 8 files changed, 306 insertions(+), 138 deletions(-) create mode 100644 crates/libanalysis/src/descriptors.rs delete mode 100644 crates/libanalysis/src/module_map_db/descr.rs (limited to 'crates') diff --git a/crates/libanalysis/src/db/mod.rs b/crates/libanalysis/src/db/mod.rs index a775b5f75..1111a4f87 100644 --- a/crates/libanalysis/src/db/mod.rs +++ b/crates/libanalysis/src/db/mod.rs @@ -68,22 +68,32 @@ pub(crate) fn file_set(ctx: QueryCtx) -> Arc<(Vec, FileResolverImp)> { pub(crate) use self::queries::file_syntax; mod queries { + use std::sync::Arc; use libsyntax2::File; + use libeditor::LineIndex; use {FileId}; use super::{Query, QueryCtx, QueryRegistry, file_text}; pub(crate) fn register_queries(reg: &mut QueryRegistry) { - reg.add(FILE_SYNTAX, "FILE_SYNTAX") + reg.add(FILE_SYNTAX, "FILE_SYNTAX"); + reg.add(FILE_LINES, "FILE_LINES"); } pub(crate) fn file_syntax(ctx: QueryCtx, file_id: FileId) -> File { (&*ctx.get(FILE_SYNTAX, file_id)).clone() } + pub(crate) fn file_lines(ctx: QueryCtx, file_id: FileId) -> Arc { + ctx.get(FILE_LINES, file_id) + } pub(super) const FILE_SYNTAX: Query = Query(16, |ctx, file_id: &FileId| { let text = file_text(ctx, *file_id); File::parse(&*text) }); + pub(super) const FILE_LINES: Query = Query(17, |ctx, file_id: &FileId| { + let text = file_text(ctx, *file_id); + LineIndex::new(&*text) + }); } impl QueryRegistry { diff --git a/crates/libanalysis/src/descriptors.rs b/crates/libanalysis/src/descriptors.rs new file mode 100644 index 000000000..e21ee728f --- /dev/null +++ b/crates/libanalysis/src/descriptors.rs @@ -0,0 +1,217 @@ +use std::{ + collections::BTreeMap, +}; +use relative_path::RelativePathBuf; +use libsyntax2::{ + SmolStr, + ast::{self, NameOwner}, +}; +use { + FileId, + imp::FileResolverImp, +}; + +#[derive(Debug, Hash)] +pub struct ModuleDescriptor { + pub submodules: Vec +} + +impl ModuleDescriptor { + pub fn new(root: ast::Root) -> ModuleDescriptor { + let submodules = modules(root) + .map(|(name, _)| Submodule { name }) + .collect(); + + ModuleDescriptor { submodules } } +} + +fn modules<'a>(root: ast::Root<'a>) -> impl Iterator)> { + root + .modules() + .filter_map(|module| { + let name = module.name()?.text(); + if !module.has_semi() { + return None; + } + Some((name, module)) + }) +} + +#[derive(Clone, Hash, PartialEq, Eq, Debug)] +pub struct Submodule { + pub name: SmolStr, +} + +#[derive(Hash)] +pub(crate) struct ModuleTreeDescriptor { + nodes: Vec, + links: Vec, + file_id2node: BTreeMap, +} + +#[derive(Clone, Copy, PartialEq, Eq, Hash)] +struct Node(usize); +#[derive(Hash)] +struct NodeData { + file_id: FileId, + links: Vec, + parents: Vec +} + +#[derive(Clone, Copy, PartialEq, Eq, Hash)] +pub(crate) struct Link(usize); +#[derive(Hash)] +struct LinkData { + owner: Node, + name: SmolStr, + points_to: Vec, + problem: Option, +} + + +#[derive(Clone, Debug, Hash)] +pub enum Problem { + UnresolvedModule { + candidate: RelativePathBuf, + }, + NotDirOwner { + move_to: RelativePathBuf, + candidate: RelativePathBuf, + } +} + +impl ModuleTreeDescriptor { + pub(crate) fn new<'a>( + files: impl Iterator + Clone, + file_resolver: &FileResolverImp, + ) -> ModuleTreeDescriptor { + let mut file_id2node = BTreeMap::new(); + let mut nodes: Vec = files.clone().enumerate() + .map(|(idx, (file_id, _))| { + file_id2node.insert(file_id, Node(idx)); + NodeData { + file_id, + links: Vec::new(), + parents: Vec::new(), + } + }) + .collect(); + let mut links = Vec::new(); + + for (idx, (file_id, descr)) in files.enumerate() { + let owner = Node(idx); + for sub in descr.submodules.iter() { + let link = Link(links.len()); + nodes[owner.0].links.push(link); + let (points_to, problem) = resolve_submodule(file_id, &sub.name, file_resolver); + let points_to = points_to + .into_iter() + .map(|file_id| { + let node = file_id2node[&file_id]; + nodes[node.0].parents.push(link); + node + }) + .collect(); + + links.push(LinkData { + owner, + name: sub.name.clone(), + points_to, + problem, + }) + + } + } + + ModuleTreeDescriptor { + nodes, links, file_id2node + } + } + + pub(crate) fn parent_modules(&self, file_id: FileId) -> Vec { + let node = self.file_id2node[&file_id]; + self.node(node) + .parents + .clone() + } + pub(crate) fn child_module_by_name(&self, file_id: FileId, name: &str) -> Vec { + let node = self.file_id2node[&file_id]; + self.node(node) + .links + .iter() + .filter(|it| it.name(self) == name) + .map(|link| link.owner(self)) + .collect() + } + pub(crate) fn problems<'a, 'b>(&'b self, file_id: FileId, root: ast::Root<'a>) -> Vec<(ast::Name<'a>, &'b Problem)> { + let node = self.file_id2node[&file_id]; + self.node(node) + .links + .iter() + .filter_map(|&link| { + let problem = self.link(link).problem.as_ref()?; + let name = link.bind_source(self, root).name()?; + Some((name, problem)) + }) + .collect() + } + + fn node(&self, node: Node) -> &NodeData { + &self.nodes[node.0] + } + fn link(&self, link: Link) -> &LinkData { + &self.links[link.0] + } +} + +impl Link { + pub(crate) fn name(self, tree: &ModuleTreeDescriptor) -> SmolStr { + tree.link(self).name.clone() + } + pub(crate) fn owner(self, tree: &ModuleTreeDescriptor) -> FileId { + let owner = tree.link(self).owner; + tree.node(owner).file_id + } + pub(crate) fn bind_source<'a>(self, tree: &ModuleTreeDescriptor, root: ast::Root<'a>) -> ast::Module<'a> { + modules(root) + .filter(|(name, _)| name == &tree.link(self).name) + .next() + .unwrap() + .1 + } +} + + +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/libanalysis/src/imp.rs b/crates/libanalysis/src/imp.rs index 3e65ee14a..8734813f4 100644 --- a/crates/libanalysis/src/imp.rs +++ b/crates/libanalysis/src/imp.rs @@ -18,8 +18,8 @@ use libsyntax2::{ use { FileId, FileResolver, Query, Diagnostic, SourceChange, SourceFileEdit, Position, FileSystemEdit, JobToken, CrateGraph, CrateId, - module_map::{ModuleMap, Problem}, roots::{SourceRoot, ReadonlySourceRoot, WritableSourceRoot}, + descriptors::{ModuleTreeDescriptor, Problem}, }; @@ -148,25 +148,24 @@ impl AnalysisImpl { } pub fn parent_module(&self, file_id: FileId) -> Vec<(FileId, FileSymbol)> { let root = self.root(file_id); - let module_map = root.module_map(); - let id = module_map.file2module(file_id); - module_map - .parent_modules(id, &|file_id| root.syntax(file_id)) - .into_iter() - .map(|(id, name, node)| { - let id = module_map.module2file(id); + let module_tree = root.module_tree(); + module_tree.parent_modules(file_id) + .iter() + .map(|link| { + let file_id = link.owner(&module_tree); + let syntax = root.syntax(file_id); + let decl = link.bind_source(&module_tree, syntax.ast()); let sym = FileSymbol { - name, - node_range: node.range(), + name: link.name(&module_tree), + node_range: decl.syntax().range(), kind: MODULE, }; - (id, sym) + (file_id, sym) }) .collect() } - pub fn crate_for(&self, file_id: FileId) -> Vec { - let module_map = self.root(file_id).module_map(); + let module_tree = self.root(file_id).module_tree(); let crate_graph = &self.data.crate_graph; let mut res = Vec::new(); let mut work = VecDeque::new(); @@ -177,11 +176,10 @@ impl AnalysisImpl { res.push(crate_id); continue; } - let mid = module_map.file2module(id); - let parents = module_map - .parent_module_ids(mid, &|file_id| self.file_syntax(file_id)) + let parents = module_tree + .parent_modules(id) .into_iter() - .map(|id| module_map.module2file(id)) + .map(|link| link.owner(&module_tree)) .filter(|&id| visited.insert(id)); work.extend(parents); } @@ -197,7 +195,7 @@ impl AnalysisImpl { token: &JobToken, ) -> Vec<(FileId, FileSymbol)> { let root = self.root(file_id); - let module_map = root.module_map(); + let module_tree = root.module_tree(); let file = root.syntax(file_id); let syntax = file.syntax(); if let Some(name_ref) = find_node_at_offset::(syntax, offset) { @@ -206,7 +204,7 @@ impl AnalysisImpl { if let Some(name) = find_node_at_offset::(syntax, offset) { if let Some(module) = name.syntax().parent().and_then(ast::Module::cast) { if module.has_semi() { - let file_ids = self.resolve_module(module_map, file_id, module); + let file_ids = self.resolve_module(&*module_tree, file_id, module); let res = file_ids.into_iter().map(|id| { let name = module.name() @@ -229,7 +227,7 @@ impl AnalysisImpl { pub fn diagnostics(&self, file_id: FileId) -> Vec { let root = self.root(file_id); - let module_map = root.module_map(); + let module_tree = root.module_tree(); let syntax = root.syntax(file_id); let mut res = libeditor::diagnostics(&syntax) @@ -237,47 +235,43 @@ impl AnalysisImpl { .map(|d| Diagnostic { range: d.range, message: d.msg, fix: None }) .collect::>(); - module_map.problems( - file_id, - &|file_id| self.file_syntax(file_id), - |name_node, problem| { - let diag = match problem { - Problem::UnresolvedModule { candidate } => { - let create_file = FileSystemEdit::CreateFile { - anchor: file_id, - path: candidate.clone(), - }; - let fix = SourceChange { - label: "create module".to_string(), - source_file_edits: Vec::new(), - file_system_edits: vec![create_file], - cursor_position: None, - }; - Diagnostic { - range: name_node.syntax().range(), - message: "unresolved module".to_string(), - fix: Some(fix), - } + for (name_node, problem) in module_tree.problems(file_id, syntax.ast()) { + let diag = match problem { + Problem::UnresolvedModule { candidate } => { + let create_file = FileSystemEdit::CreateFile { + anchor: file_id, + path: candidate.clone(), + }; + let fix = SourceChange { + label: "create module".to_string(), + source_file_edits: Vec::new(), + file_system_edits: vec![create_file], + cursor_position: None, + }; + Diagnostic { + range: name_node.syntax().range(), + message: "unresolved module".to_string(), + fix: Some(fix), } - Problem::NotDirOwner { move_to, candidate } => { - let move_file = FileSystemEdit::MoveFile { file: file_id, path: move_to.clone() }; - let create_file = FileSystemEdit::CreateFile { anchor: file_id, path: move_to.join(candidate) }; - let fix = SourceChange { - label: "move file and create module".to_string(), - source_file_edits: Vec::new(), - file_system_edits: vec![move_file, create_file], - cursor_position: None, - }; - Diagnostic { - range: name_node.syntax().range(), - message: "can't declare module at this location".to_string(), - fix: Some(fix), - } + } + Problem::NotDirOwner { move_to, candidate } => { + let move_file = FileSystemEdit::MoveFile { file: file_id, path: move_to.clone() }; + let create_file = FileSystemEdit::CreateFile { anchor: file_id, path: move_to.join(candidate) }; + let fix = SourceChange { + label: "move file and create module".to_string(), + source_file_edits: Vec::new(), + file_system_edits: vec![move_file, create_file], + cursor_position: None, + }; + Diagnostic { + range: name_node.syntax().range(), + message: "can't declare module at this location".to_string(), + fix: Some(fix), } - }; - res.push(diag) - } - ); + } + }; + res.push(diag) + } res } @@ -307,20 +301,12 @@ impl AnalysisImpl { self.world_symbols(query, token) } - fn resolve_module(&self, module_map: &ModuleMap, file_id: FileId, module: ast::Module) -> Vec { + fn resolve_module(&self, module_tree: &ModuleTreeDescriptor, file_id: FileId, module: ast::Module) -> Vec { let name = match module.name() { Some(name) => name.text(), None => return Vec::new(), }; - let id = module_map.file2module(file_id); - module_map - .child_module_by_name( - id, name.as_str(), - &|file_id| self.file_syntax(file_id), - ) - .into_iter() - .map(|id| module_map.module2file(id)) - .collect() + module_tree.child_module_by_name(file_id, name.as_str()) } fn reindex(&self) { diff --git a/crates/libanalysis/src/lib.rs b/crates/libanalysis/src/lib.rs index bca5d4c1d..ea3a28702 100644 --- a/crates/libanalysis/src/lib.rs +++ b/crates/libanalysis/src/lib.rs @@ -19,6 +19,7 @@ mod imp; mod job; mod roots; mod db; +mod descriptors; use std::{ sync::Arc, diff --git a/crates/libanalysis/src/module_map_db/descr.rs b/crates/libanalysis/src/module_map_db/descr.rs deleted file mode 100644 index fb298a315..000000000 --- a/crates/libanalysis/src/module_map_db/descr.rs +++ /dev/null @@ -1,29 +0,0 @@ -use libsyntax2::{ - SmolStr, - ast::{self, NameOwner}, -}; - -#[derive(Debug, Hash)] -pub struct ModuleDescr { - pub submodules: Vec -} - -impl ModuleDescr { - pub fn new(root: ast::Root) -> ModuleDescr { - let submodules = root - .modules() - .filter_map(|module| { - let name = module.name()?.text(); - if !module.has_semi() { - return None; - } - Some(Submodule { name }) - }).collect(); - - ModuleDescr { submodules } } -} - -#[derive(Clone, Hash, PartialEq, Eq, Debug)] -pub struct Submodule { - pub name: SmolStr, -} diff --git a/crates/libanalysis/src/module_map_db/mod.rs b/crates/libanalysis/src/module_map_db/mod.rs index 5560e4a34..adad943da 100644 --- a/crates/libanalysis/src/module_map_db/mod.rs +++ b/crates/libanalysis/src/module_map_db/mod.rs @@ -1,5 +1,3 @@ -mod descr; - use std::sync::Arc; use { FileId, @@ -7,49 +5,36 @@ use { Query, QueryRegistry, QueryCtx, file_syntax, file_set }, - module_map::resolve_submodule, + descriptors::{ModuleDescriptor, ModuleTreeDescriptor} }; pub(crate) fn register_queries(reg: &mut QueryRegistry) { reg.add(MODULE_DESCR, "MODULE_DESCR"); - reg.add(RESOLVE_SUBMODULE, "RESOLVE_SUBMODULE"); - reg.add(PARENT_MODULE, "PARENT_MODULE"); +} + +pub(crate) fn module_tree(ctx: QueryCtx) -> Arc { + ctx.get(MODULE_TREE, ()) } impl<'a> QueryCtx<'a> { - fn module_descr(&self, file_id: FileId) -> Arc { + fn module_descr(&self, file_id: FileId) -> Arc { self.get(MODULE_DESCR, file_id) } - fn resolve_submodule(&self, file_id: FileId, submod: descr::Submodule) -> Arc> { - self.get(RESOLVE_SUBMODULE, (file_id, submod)) - } } -const MODULE_DESCR: Query = Query(30, |ctx, &file_id| { +const MODULE_DESCR: Query = Query(30, |ctx, &file_id| { let file = file_syntax(ctx, file_id); - descr::ModuleDescr::new(file.ast()) + ModuleDescriptor::new(file.ast()) }); -const RESOLVE_SUBMODULE: Query<(FileId, descr::Submodule), Vec> = Query(31, |ctx, params| { - let files = file_set(ctx); - resolve_submodule(params.0, ¶ms.1.name, &files.1).0 -}); - -const PARENT_MODULE: Query> = Query(40, |ctx, file_id| { - let files = file_set(ctx); - let res = files.0.iter() - .map(|&parent_id| (parent_id, ctx.module_descr(parent_id))) - .filter(|(parent_id, descr)| { - descr.submodules.iter() - .any(|subm| { - ctx.resolve_submodule(*parent_id, subm.clone()) - .iter() - .any(|it| it == file_id) - }) - }) - .map(|(id, _)| id) - .collect(); - res +const MODULE_TREE: Query<(), ModuleTreeDescriptor> = Query(31, |ctx, _| { + let file_set = file_set(ctx); + let mut files = Vec::new(); + for &file_id in file_set.0.iter() { + let module_descr = ctx.get(MODULE_DESCR, file_id); + files.push((file_id, module_descr)); + } + ModuleTreeDescriptor::new(files.iter().map(|(file_id, descr)| (*file_id, &**descr)), &file_set.1) }); #[cfg(test)] diff --git a/crates/libanalysis/src/roots.rs b/crates/libanalysis/src/roots.rs index 629a697c5..b925fd24d 100644 --- a/crates/libanalysis/src/roots.rs +++ b/crates/libanalysis/src/roots.rs @@ -15,11 +15,15 @@ use { imp::FileResolverImp, module_map::{ModuleMap, ChangeKind}, symbol_index::SymbolIndex, + descriptors::ModuleTreeDescriptor, }; pub(crate) trait SourceRoot { fn contains(&self, file_id: FileId) -> bool; - fn module_map(&self) -> &ModuleMap; + fn module_tree(&self) -> Arc { + unimplemented!() + } + // fn module_map(&self) -> &ModuleMap; fn lines(&self, file_id: FileId) -> &LineIndex; fn syntax(&self, file_id: FileId) -> &File; fn symbols<'a>(&'a self, acc: &mut Vec<&'a SymbolIndex>); @@ -74,9 +78,6 @@ impl SourceRoot for WritableSourceRoot { fn contains(&self, file_id: FileId) -> bool { self.file_map.contains_key(&file_id) } - fn module_map(&self) -> &ModuleMap { - &self.module_map - } fn lines(&self, file_id: FileId) -> &LineIndex { self.data(file_id).lines() } @@ -175,9 +176,6 @@ impl SourceRoot for ReadonlySourceRoot { fn contains(&self, file_id: FileId) -> bool { self.file_map.contains_key(&file_id) } - fn module_map(&self) -> &ModuleMap { - &self.module_map - } fn lines(&self, file_id: FileId) -> &LineIndex { self.data(file_id).lines() } diff --git a/crates/libeditor/src/line_index.rs b/crates/libeditor/src/line_index.rs index 801726aa5..9cd8da3a8 100644 --- a/crates/libeditor/src/line_index.rs +++ b/crates/libeditor/src/line_index.rs @@ -1,7 +1,7 @@ use superslice::Ext; use ::TextUnit; -#[derive(Clone, Debug)] +#[derive(Clone, Debug, Hash)] pub struct LineIndex { newlines: Vec, } -- cgit v1.2.3