ModuleTreeDescriptor

8 files changed, 306 insertions, 138 deletions

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<FileId>, 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<LineIndex> {
+        ctx.get(FILE_LINES, file_id)
+    }
 
     pub(super) const FILE_SYNTAX: Query<FileId, File> = Query(16, |ctx, file_id: &FileId| {
         let text = file_text(ctx, *file_id);
         File::parse(&*text)
     });
+    pub(super) const FILE_LINES: Query<FileId, LineIndex> = 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<Submodule>
+}
+
+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<Item=(SmolStr, ast::Module<'a>)> {
+    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<NodeData>,
+    links: Vec<LinkData>,
+    file_id2node: BTreeMap<FileId, Node>,
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Hash)]
+struct Node(usize);
+#[derive(Hash)]
+struct NodeData {
+    file_id: FileId,
+    links: Vec<Link>,
+    parents: Vec<Link>
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Hash)]
+pub(crate) struct Link(usize);
+#[derive(Hash)]
+struct LinkData {
+    owner: Node,
+    name: SmolStr,
+    points_to: Vec<Node>,
+    problem: Option<Problem>,
+}
+
+
+#[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<Item=(FileId, &'a ModuleDescriptor)> + Clone,
+        file_resolver: &FileResolverImp,
+    ) -> ModuleTreeDescriptor {
+        let mut file_id2node = BTreeMap::new();
+        let mut nodes: Vec<NodeData> = 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<Link> {
+        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<FileId> {
+        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<FileId>, Option<Problem>) {
+    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<FileId>;
+    let problem: Option<Problem>;
+    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<CrateId> {
-        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::<ast::NameRef>(syntax, offset) {
@@ -206,7 +204,7 @@ impl AnalysisImpl {
         if let Some(name) = find_node_at_offset::<ast::Name>(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<Diagnostic> {
         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::<Vec<_>>();
 
-        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<FileId> {
+    fn resolve_module(&self, module_tree: &ModuleTreeDescriptor, file_id: FileId, module: ast::Module) -> Vec<FileId> {
         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<Submodule>
-}
-
-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<ModuleTreeDescriptor> {
+    ctx.get(MODULE_TREE, ())
 }
 
 impl<'a> QueryCtx<'a> {
-    fn module_descr(&self, file_id: FileId) -> Arc<descr::ModuleDescr> {
+    fn module_descr(&self, file_id: FileId) -> Arc<ModuleDescriptor> {
         self.get(MODULE_DESCR, file_id)
     }
-    fn resolve_submodule(&self, file_id: FileId, submod: descr::Submodule) -> Arc<Vec<FileId>> {
-        self.get(RESOLVE_SUBMODULE, (file_id, submod))
-    }
 }
 
-const MODULE_DESCR: Query<FileId, descr::ModuleDescr> = Query(30, |ctx, &file_id| {
+const MODULE_DESCR: Query<FileId, ModuleDescriptor> = 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<FileId>> = Query(31, |ctx, params| {
-    let files = file_set(ctx);
-    resolve_submodule(params.0, &params.1.name, &files.1).0
-});
-
-const PARENT_MODULE: Query<FileId, Vec<FileId>> = 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<ModuleTreeDescriptor> {
+        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<TextUnit>,
 }