7 files changed, 361 insertions, 41 deletions

diff --git a/crates/libanalysis/Cargo.toml b/crates/libanalysis/Cargo.toml
index 4d565e95f..4c92951b1 100644
--- a/crates/libanalysis/Cargo.toml
+++ b/crates/libanalysis/Cargo.toml
@@ -11,6 +11,7 @@ parking_lot = "0.6.3"
 once_cell = "0.1.5"
 rayon = "1.0.2"
 fst = "0.3.1"
+im = "12.0.0"
 libsyntax2 = { path = "../libsyntax2" }
 libeditor = { path = "../libeditor" }
 
diff --git a/crates/libanalysis/src/db.rs b/crates/libanalysis/src/db.rs
new file mode 100644
index 000000000..335c79e76
--- /dev/null
+++ b/crates/libanalysis/src/db.rs
@@ -0,0 +1,121 @@
+use std::{
+    hash::Hash,
+    sync::Arc,
+};
+use libsyntax2::{File};
+use im;
+use {
+    FileId,
+    imp::{FileResolverImp},
+};
+
+#[derive(Clone)]
+pub(crate) struct Db {
+    file_resolver: FileResolverImp,
+    files: im::HashMap<FileId, Arc<String>>,
+}
+
+impl Db {
+    pub(crate) fn new() -> Db {
+        Db {
+            file_resolver: FileResolverImp::default(),
+            files: im::HashMap::new(),
+        }
+    }
+    pub(crate) fn change_file(&mut self, file_id: FileId, text: Option<String>) {
+        match text {
+            None => {
+                self.files.remove(&file_id);
+            }
+            Some(text) => {
+                self.files.insert(file_id, Arc::new(text));
+            }
+        }
+    }
+    pub(crate) fn set_file_resolver(&mut self, file_resolver: FileResolverImp) {
+        self.file_resolver = file_resolver
+    }
+    pub(crate) fn query_ctx(&self) -> QueryCtx {
+        QueryCtx { db: self.clone() }
+    }
+}
+
+pub(crate) struct QueryCtx {
+    db: Db
+}
+
+impl QueryCtx {
+    pub(crate) fn get<Q: Get>(&self, params: &Q::Params) -> Q::Output {
+        Q::get(self, params)
+    }
+}
+
+pub(crate) trait Query {
+    const ID: u32;
+    type Params: Hash;
+    type Output;
+}
+
+pub(crate) trait Get: Query {
+    fn get(ctx: &QueryCtx, params: &Self::Params) -> Self::Output;
+}
+
+impl<T: Eval> Get for T {
+    fn get(ctx: &QueryCtx, params: &Self::Params) -> Self::Output {
+        Self::eval(ctx, params)
+    }
+}
+
+pub(crate) trait Eval: Query {
+    fn eval(ctx: &QueryCtx, params: &Self::Params) -> Self::Output;
+}
+
+pub(crate) struct DbFiles {
+    db: Db,
+}
+
+impl DbFiles {
+    pub(crate) fn iter<'a>(&'a self) -> impl Iterator<Item=FileId> + 'a {
+        self.db.files.keys().cloned()
+    }
+    pub(crate) fn file_resolver(&self) -> FileResolverImp {
+        self.db.file_resolver.clone()
+    }
+}
+
+pub(crate) enum Files {}
+impl Query for Files {
+    const ID: u32 = 1;
+    type Params = ();
+    type Output = DbFiles;
+}
+impl Get for Files {
+    fn get(ctx: &QueryCtx, _params: &()) -> DbFiles {
+        DbFiles { db: ctx.db.clone() }
+    }
+}
+
+enum FileText {}
+impl Query for FileText {
+    const ID: u32 = 10;
+    type Params = FileId;
+    type Output = Arc<String>;
+}
+impl Get for FileText {
+    fn get(ctx: &QueryCtx, file_id: &FileId) -> Arc<String> {
+        ctx.db.files[file_id].clone()
+    }
+}
+
+pub(crate) enum FileSyntax {}
+impl Query for FileSyntax {
+    const ID: u32 = 20;
+    type Params = FileId;
+    type Output = File;
+}
+impl Eval for FileSyntax {
+    fn eval(ctx: &QueryCtx, file_id: &FileId) -> File {
+        let text = ctx.get::<FileText>(file_id);
+        File::parse(&text)
+    }
+}
diff --git a/crates/libanalysis/src/lib.rs b/crates/libanalysis/src/lib.rs
index 80cde079f..68cf31e08 100644
--- a/crates/libanalysis/src/lib.rs
+++ b/crates/libanalysis/src/lib.rs
@@ -9,12 +9,15 @@ extern crate rayon;
 extern crate relative_path;
 #[macro_use]
 extern crate crossbeam_channel;
+extern crate im;
 
 mod symbol_index;
 mod module_map;
+mod module_map_db;
 mod imp;
 mod job;
 mod roots;
+mod db;
 
 use std::{
     sync::Arc,
diff --git a/crates/libanalysis/src/module_map.rs b/crates/libanalysis/src/module_map.rs
index 9acebd6e2..79b88cac2 100644
--- a/crates/libanalysis/src/module_map.rs
+++ b/crates/libanalysis/src/module_map.rs
@@ -244,31 +244,38 @@ impl Link {
             self.points_to = Vec::new();
             return;
         }
+        let (points_to, problem) = resolve_submodule(self.owner.0, &self.name(), file_resolver);
+        self.problem = problem;
+        self.points_to = points_to.into_iter().map(ModuleId).collect();
+    }
+}
 
-        let mod_name = file_resolver.file_stem(self.owner.0);
-        let is_dir_owner =
-            mod_name == "mod" || mod_name == "lib" || mod_name == "main";
+pub(crate) 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", self.name()));
-        let dir_mod = RelativePathBuf::from(format!("../{}/mod.rs", self.name()));
-        if is_dir_owner {
-            self.points_to = [&file_mod, &dir_mod].iter()
-                .filter_map(|path| file_resolver.resolve(self.owner.0, path))
-                .map(ModuleId)
-                .collect();
-            self.problem = if self.points_to.is_empty() {
-                Some(Problem::UnresolvedModule {
-                    candidate: file_mod,
-                })
-            } else {
-                None
-            }
-        } else {
-            self.points_to = Vec::new();
-            self.problem = Some(Problem::NotDirOwner {
-                move_to: RelativePathBuf::from(format!("../{}/mod.rs", mod_name)),
+    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/module_map_db.rs b/crates/libanalysis/src/module_map_db.rs
new file mode 100644
index 000000000..1ef87ab3f
--- /dev/null
+++ b/crates/libanalysis/src/module_map_db.rs
@@ -0,0 +1,189 @@
+use std::sync::Arc;
+use {
+    FileId,
+    db::{Query, Eval, QueryCtx, FileSyntax, Files},
+    module_map::resolve_submodule,
+};
+
+enum ModuleDescr {}
+impl Query for ModuleDescr {
+    const ID: u32 = 30;
+    type Params = FileId;
+    type Output = Arc<descr::ModuleDescr>;
+}
+
+enum ResolveSubmodule {}
+impl Query for ResolveSubmodule {
+    const ID: u32 = 31;
+    type Params = (FileId, descr::Submodule);
+    type Output = Arc<Vec<FileId>>;
+}
+
+enum ParentModule {}
+impl Query for ParentModule {
+    const ID: u32 = 40;
+    type Params = FileId;
+    type Output = Arc<Vec<FileId>>;
+}
+
+impl Eval for ModuleDescr {
+    fn eval(ctx: &QueryCtx, file_id: &FileId) -> Arc<descr::ModuleDescr> {
+        let file = ctx.get::<FileSyntax>(file_id);
+        Arc::new(descr::ModuleDescr::new(file.ast()))
+    }
+}
+
+impl Eval for ResolveSubmodule {
+    fn eval(ctx: &QueryCtx, &(file_id, ref submodule): &(FileId, descr::Submodule)) -> Arc<Vec<FileId>> {
+        let files = ctx.get::<Files>(&());
+        let res = resolve_submodule(file_id, &submodule.name, &files.file_resolver()).0;
+        Arc::new(res)
+    }
+}
+
+impl Eval for ParentModule {
+    fn eval(ctx: &QueryCtx, file_id: &FileId) -> Arc<Vec<FileId>> {
+        let files = ctx.get::<Files>(&());
+        let res = files.iter()
+            .map(|parent_id| (parent_id, ctx.get::<ModuleDescr>(&parent_id)))
+            .filter(|(parent_id, descr)| {
+                descr.submodules.iter()
+                    .any(|subm| {
+                        ctx.get::<ResolveSubmodule>(&(*parent_id, subm.clone()))
+                            .iter()
+                            .any(|it| it == file_id)
+                    })
+            })
+            .map(|(id, _)| id)
+            .collect();
+        Arc::new(res)
+    }
+}
+
+mod descr {
+    use libsyntax2::{
+        SmolStr,
+        ast::{self, NameOwner},
+    };
+
+    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)]
+    pub struct Submodule {
+        pub name: SmolStr,
+    }
+
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use im;
+    use relative_path::{RelativePath, RelativePathBuf};
+    use {
+        db::Db,
+        imp::FileResolverImp,
+        FileId, FileResolver,
+    };
+
+    #[derive(Debug)]
+    struct FileMap(im::HashMap<FileId, RelativePathBuf>);
+
+    impl FileResolver for FileMap {
+        fn file_stem(&self, file_id: FileId) -> String {
+            self.0[&file_id].file_stem().unwrap().to_string()
+        }
+        fn resolve(&self, file_id: FileId, rel: &RelativePath) -> Option<FileId> {
+            let path = self.0[&file_id].join(rel).normalize();
+            self.0.iter()
+                .filter_map(|&(id, ref p)| Some(id).filter(|_| p == &path))
+                .next()
+        }
+    }
+
+    struct Fixture {
+        next_file_id: u32,
+        fm: im::HashMap<FileId, RelativePathBuf>,
+        db: Db,
+    }
+
+    impl Fixture {
+        fn new() -> Fixture {
+            Fixture {
+                next_file_id: 1,
+                fm: im::HashMap::new(),
+                db: Db::new(),
+            }
+        }
+        fn add_file(&mut self, path: &str, text: &str) -> FileId {
+            assert!(path.starts_with("/"));
+            let file_id = FileId(self.next_file_id);
+            self.next_file_id += 1;
+            self.fm.insert(file_id, RelativePathBuf::from(&path[1..]));
+            self.db.change_file(file_id, Some(text.to_string()));
+            self.db.set_file_resolver(FileResolverImp::new(
+                Arc::new(FileMap(self.fm.clone()))
+            ));
+
+            file_id
+        }
+        fn remove_file(&mut self, file_id: FileId) {
+            self.fm.remove(&file_id);
+            self.db.change_file(file_id, None);
+            self.db.set_file_resolver(FileResolverImp::new(
+                Arc::new(FileMap(self.fm.clone()))
+            ))
+        }
+        fn change_file(&mut self, file_id: FileId, new_text: &str) {
+            self.db.change_file(file_id, Some(new_text.to_string()));
+        }
+        fn check_parent_modules(&self, file_id: FileId, expected: &[FileId]) {
+            let ctx = self.db.query_ctx();
+            let actual = ctx.get::<ParentModule>(&file_id);
+            assert_eq!(actual.as_slice(), expected);
+        }
+    }
+
+    #[test]
+    fn test_parent_module() {
+        let mut f = Fixture::new();
+        let foo = f.add_file("/foo.rs", "");
+        f.check_parent_modules(foo, &[]);
+
+        let lib = f.add_file("/lib.rs", "mod foo;");
+        f.check_parent_modules(foo, &[lib]);
+
+        f.change_file(lib, "");
+        f.check_parent_modules(foo, &[]);
+
+        f.change_file(lib, "mod foo;");
+        f.check_parent_modules(foo, &[lib]);
+
+        f.change_file(lib, "mod bar;");
+        f.check_parent_modules(foo, &[]);
+
+        f.change_file(lib, "mod foo;");
+        f.check_parent_modules(foo, &[lib]);
+
+        f.remove_file(lib);
+        f.check_parent_modules(foo, &[]);
+    }
+
+}
diff --git a/crates/libanalysis/tests/tests.rs b/crates/libanalysis/tests/tests.rs
index 00efe059c..547f85958 100644
--- a/crates/libanalysis/tests/tests.rs
+++ b/crates/libanalysis/tests/tests.rs
@@ -14,24 +14,6 @@ use test_utils::assert_eq_dbg;
 #[derive(Debug)]
 struct FileMap(Vec<(FileId, RelativePathBuf)>);
 
-fn analysis_host(files: &'static [(&'static str, &'static str)]) -> AnalysisHost {
-    let mut host = AnalysisHost::new();
-    let mut file_map = Vec::new();
-    for (id, &(path, contents)) in files.iter().enumerate() {
-        let file_id = FileId((id + 1) as u32);
-        assert!(path.starts_with('/'));
-        let path = RelativePathBuf::from_path(&path[1..]).unwrap();
-        host.change_file(file_id, Some(contents.to_string()));
-        file_map.push((file_id, path));
-    }
-    host.set_file_resolver(Arc::new(FileMap(file_map)));
-    host
-}
-
-fn analysis(files: &'static [(&'static str, &'static str)]) -> Analysis {
-    analysis_host(files).analysis()
-}
-
 impl FileMap {
     fn iter<'a>(&'a self) -> impl Iterator<Item=(FileId, &'a RelativePath)> + 'a {
         self.0.iter().map(|(id, path)| (*id, path.as_relative_path()))
@@ -56,6 +38,23 @@ impl FileResolver for FileMap {
     }
 }
 
+fn analysis_host(files: &'static [(&'static str, &'static str)]) -> AnalysisHost {
+    let mut host = AnalysisHost::new();
+    let mut file_map = Vec::new();
+    for (id, &(path, contents)) in files.iter().enumerate() {
+        let file_id = FileId((id + 1) as u32);
+        assert!(path.starts_with('/'));
+        let path = RelativePathBuf::from_path(&path[1..]).unwrap();
+        host.change_file(file_id, Some(contents.to_string()));
+        file_map.push((file_id, path));
+    }
+    host.set_file_resolver(Arc::new(FileMap(file_map)));
+    host
+}
+
+fn analysis(files: &'static [(&'static str, &'static str)]) -> Analysis {
+    analysis_host(files).analysis()
+}
 
 #[test]
 fn test_resolve_module() {
diff --git a/crates/server/Cargo.toml b/crates/server/Cargo.toml
index 9aeea9a9b..fc20730b8 100644
--- a/crates/server/Cargo.toml
+++ b/crates/server/Cargo.toml
@@ -17,7 +17,7 @@ log = "0.4.3"
 url_serde = "0.2.0"
 languageserver-types = "0.49.0"
 walkdir = "2.2.0"
-im = { version = "11.0.1", features = ["arc"] }
+im = "12.0.0"
 cargo_metadata = "0.6.0"
 text_unit = { version = "0.1.2", features = ["serde"] }
 smol_str = { version = "0.1.5", features = ["serde"] }