2 files changed, 322 insertions, 0 deletions

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<Arc<Vec<SmolStr>>> {
+    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<Item = (SmolStr, ast::Module<'_>)> {
+    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<Arc<ModuleTree>> {
+    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<ModuleTree> {
+    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<FileId>,
+    roots: &mut FxHashMap<FileId, ModuleId>,
+    parent: Option<LinkId>,
+    file_id: FileId,
+) -> Cancelable<ModuleId> {
+    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::<Cancelable<Vec<_>>>()?;
+        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<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/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<Arc<ModuleTree>> {
+            type ModuleTreeQuery;
+            use fn imp::module_tree;
+        }
+        fn submodules(file_id: FileId) -> Cancelable<Arc<Vec<SmolStr>>> {
+            type SubmodulesQuery;
+            use fn imp::submodules;
+        }
+    }
+}
+
+
+#[derive(Debug, PartialEq, Eq, Hash)]
+pub(crate) struct ModuleTree {
+    mods: Vec<ModuleData>,
+    links: Vec<LinkData>,
+}
+
+impl ModuleTree {
+    pub(crate) fn modules_for_file(&self, file_id: FileId) -> Vec<ModuleId> {
+        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<ModuleId> {
+        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<LinkId> {
+        tree.module(self).parent
+     }
+    pub(crate) fn parent(self, tree: &ModuleTree) -> Option<ModuleId> {
+        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<ModuleId> {
+        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<LinkId>,
+    children: Vec<LinkId>,
+}
+
+#[derive(Hash, Debug, PartialEq, Eq)]
+struct LinkData {
+    owner: ModuleId,
+    name: SmolStr,
+    points_to: Vec<ModuleId>,
+    problem: Option<Problem>,
+}
+
+
+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
+    }
+}
+