Module map implementation

3 files changed, 222 insertions, 40 deletions

diff --git a/crates/libanalysis/src/lib.rs b/crates/libanalysis/src/lib.rs
index 63c4c77cf..d01144627 100644
--- a/crates/libanalysis/src/lib.rs
+++ b/crates/libanalysis/src/lib.rs
@@ -10,16 +10,18 @@ extern crate fst;
 extern crate rayon;
 
 mod symbol_index;
+mod module_map;
 
 use once_cell::sync::OnceCell;
 use rayon::prelude::*;
 
 use std::{
     fmt,
-    path::{Path, PathBuf},
+    mem,
+    path::{Path},
     sync::{
         Arc,
-        atomic::{AtomicUsize, Ordering::SeqCst},
+        atomic::{AtomicBool, Ordering::SeqCst},
     },
     collections::hash_map::HashMap,
     time::Instant,
@@ -32,7 +34,10 @@ use libsyntax2::{
 };
 use libeditor::{LineIndex, FileSymbol, find_node};
 
-use self::symbol_index::FileSymbols;
+use self::{
+    symbol_index::FileSymbols,
+    module_map::ModuleMap,
+};
 pub use self::symbol_index::Query;
 
 pub type Result<T> = ::std::result::Result<T, ::failure::Error>;
@@ -42,11 +47,12 @@ pub type FileResolver = dyn Fn(FileId, &Path) -> Option<FileId> + Send + Sync;
 
 #[derive(Debug)]
 pub struct WorldState {
+    updates: Vec<FileId>,
     data: Arc<WorldData>
 }
 
-#[derive(Clone)]
 pub struct World {
+    needs_reindex: AtomicBool,
     file_resolver: Arc<FileResolver>,
     data: Arc<WorldData>,
 }
@@ -57,18 +63,48 @@ impl fmt::Debug for World {
     }
 }
 
+impl Clone for World {
+    fn clone(&self) -> World {
+        World {
+            needs_reindex: AtomicBool::new(self.needs_reindex.load(SeqCst)),
+            file_resolver: Arc::clone(&self.file_resolver),
+            data: Arc::clone(&self.data),
+        }
+    }
+}
+
 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub struct FileId(pub u32);
 
 impl WorldState {
     pub fn new() -> WorldState {
         WorldState {
-            data: Arc::new(WorldData::default())
+            updates: Vec::new(),
+            data: Arc::new(WorldData::default()),
         }
     }
 
-    pub fn snapshot(&self, file_resolver: impl Fn(FileId, &Path) -> Option<FileId> + 'static + Send + Sync) -> World {
+    pub fn snapshot(
+        &mut self,
+        file_resolver: impl Fn(FileId, &Path) -> Option<FileId> + 'static + Send + Sync,
+    ) -> World {
+        let needs_reindex = self.updates.len() >= INDEXING_THRESHOLD;
+        if !self.updates.is_empty() {
+            let updates = mem::replace(&mut self.updates, Vec::new());
+            let data = self.data_mut();
+            for file_id in updates {
+                let syntax = data.file_map
+                    .get(&file_id)
+                    .map(|it| it.syntax());
+                data.module_map.update_file(
+                    file_id,
+                    syntax,
+                    &file_resolver,
+                );
+            }
+        }
         World {
+            needs_reindex: AtomicBool::new(needs_reindex),
             file_resolver: Arc::new(file_resolver),
             data: self.data.clone()
         }
@@ -79,28 +115,28 @@ impl WorldState {
     }
 
     pub fn change_files(&mut self, changes: impl Iterator<Item=(FileId, Option<String>)>) {
-        let data = self.data_mut();
-        let mut cnt = 0;
-        for (id, text) in changes {
-            cnt += 1;
-            data.file_map.remove(&id);
-            if let Some(text) = text {
-                let file_data = FileData::new(text);
-                data.file_map.insert(id, Arc::new(file_data));
-            } else {
-                data.file_map.remove(&id);
+        let mut updates = Vec::new();
+        {
+            let data = self.data_mut();
+            for (file_id, text) in changes {
+                data.file_map.remove(&file_id);
+                if let Some(text) = text {
+                    let file_data = FileData::new(text);
+                    data.file_map.insert(file_id, Arc::new(file_data));
+                } else {
+                    data.file_map.remove(&file_id);
+                }
+                updates.push(file_id);
             }
         }
-        *data.unindexed.get_mut() += cnt;
+        self.updates.extend(updates)
     }
 
     fn data_mut(&mut self) -> &mut WorldData {
         if Arc::get_mut(&mut self.data).is_none() {
             self.data = Arc::new(WorldData {
-                unindexed: AtomicUsize::new(
-                    self.data.unindexed.load(SeqCst)
-                ),
                 file_map: self.data.file_map.clone(),
+                module_map: self.data.module_map.clone(),
             });
         }
         Arc::get_mut(&mut self.data).unwrap()
@@ -131,6 +167,24 @@ impl World {
             .collect()
     }
 
+    pub fn parent_module(&self, id: FileId) -> Vec<(FileId, FileSymbol)> {
+        let module_map = &self.data.module_map;
+        let id = module_map.file2module(id);
+        module_map
+            .parent_modules(id)
+            .into_iter()
+            .map(|(id, m)| {
+                let id = module_map.module2file(id);
+                let sym = FileSymbol {
+                    name: m.name().unwrap().text(),
+                    node_range: m.syntax().range(),
+                    kind: MODULE,
+                };
+                (id, sym)
+            })
+            .collect()
+    }
+
     pub fn approximately_resolve_symbol(
         &self,
         id: FileId,
@@ -178,32 +232,22 @@ impl World {
             Some(name) => name.text(),
             None => return Vec::new(),
         };
-        let paths = &[
-            PathBuf::from(format!("../{}.rs", name)),
-            PathBuf::from(format!("../{}/mod.rs", name)),
-        ];
-        paths.iter()
-            .filter_map(|path| self.resolve_relative_path(id, path))
+        let module_map = &self.data.module_map;
+        let id = module_map.file2module(id);
+        module_map
+            .child_module_by_name(id, name.as_str())
+            .into_iter()
+            .map(|id| module_map.module2file(id))
             .collect()
     }
 
-    fn resolve_relative_path(&self, id: FileId, path: &Path) -> Option<FileId> {
-        (self.file_resolver)(id, path)
-    }
-
     fn reindex(&self) {
-        let data = &*self.data;
-        let unindexed = data.unindexed.load(SeqCst);
-        if unindexed < INDEXING_THRESHOLD {
-            return;
-        }
-        if unindexed == data.unindexed.compare_and_swap(unindexed, 0, SeqCst) {
+        if self.needs_reindex.compare_and_swap(false, true, SeqCst) {
             let now = Instant::now();
+            let data = &*self.data;
             data.file_map
                 .par_iter()
-                .for_each(|(_, data)| {
-                    data.symbols();
-                });
+                .for_each(|(_, data)| drop(data.symbols()));
             info!("parallel indexing took {:?}", now.elapsed());
         }
     }
@@ -218,8 +262,8 @@ impl World {
 
 #[derive(Default, Debug)]
 struct WorldData {
-    unindexed: AtomicUsize,
     file_map: HashMap<FileId, Arc<FileData>>,
+    module_map: ModuleMap,
 }
 
 #[derive(Debug)]
diff --git a/crates/libanalysis/src/module_map.rs b/crates/libanalysis/src/module_map.rs
new file mode 100644
index 000000000..9b4c778b6
--- /dev/null
+++ b/crates/libanalysis/src/module_map.rs
@@ -0,0 +1,117 @@
+use std::{
+    path::{PathBuf},
+};
+
+use libsyntax2::{
+    ast::{self, AstNode, NameOwner},
+    SyntaxNode, ParsedFile, SmolStr,
+};
+use {FileId, FileResolver};
+
+#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
+pub struct ModuleId(FileId);
+
+#[derive(Clone, Debug, Default)]
+pub struct ModuleMap {
+    links: Vec<Link>,
+}
+
+#[derive(Clone, Debug)]
+struct Link {
+    owner: ModuleId,
+    syntax: SyntaxNode,
+    points_to: Vec<ModuleId>,
+}
+
+impl ModuleMap {
+    pub fn update_file(
+        &mut self,
+        file_id: FileId,
+        syntax: Option<&ParsedFile>,
+        file_resolver: &FileResolver,
+    ) {
+        let mod_id = ModuleId(file_id);
+        self.links.retain(|link| link.owner != mod_id);
+        match syntax {
+            None => {
+                for link in self.links.iter_mut() {
+                    link.points_to.retain(|&x| x != mod_id);
+                }
+            }
+            Some(syntax) => {
+                self.links.extend(
+                    syntax.ast().modules().filter_map(|it| {
+                        Link::new(mod_id, it)
+                    })
+                )
+            }
+        }
+        self.links.iter_mut().for_each(|link| {
+            link.resolve(file_resolver)
+        })
+    }
+
+    pub fn module2file(&self, m: ModuleId) -> FileId {
+        m.0
+    }
+
+    pub fn file2module(&self, file_id: FileId) -> ModuleId {
+        ModuleId(file_id)
+    }
+
+    pub fn child_module_by_name(&self, parent_mod: ModuleId, child_mod: &str) -> Vec<ModuleId> {
+        self.links
+            .iter()
+            .filter(|link| link.owner == parent_mod)
+            .filter(|link| link.name() == child_mod)
+            .filter_map(|it| it.points_to.first())
+            .map(|&it| it)
+            .collect()
+    }
+
+    pub fn parent_modules<'a>(&'a self, m: ModuleId) -> impl Iterator<Item=(ModuleId, ast::Module<'a>)> + 'a {
+        self.links
+            .iter()
+            .filter(move |link| link.points_to.iter().any(|&it| it == m))
+            .map(|link| {
+                (link.owner, link.ast())
+            })
+    }
+}
+
+impl Link {
+    fn new(owner: ModuleId, module: ast::Module) -> Option<Link> {
+        if module.name().is_none() {
+            return None;
+        }
+        let link = Link {
+            owner,
+            syntax: module.syntax().owned(),
+            points_to: Vec::new(),
+        };
+        Some(link)
+    }
+
+    fn name(&self) -> SmolStr {
+        self.ast().name()
+            .unwrap()
+            .text()
+    }
+
+    fn ast(&self) -> ast::Module {
+        ast::Module::cast(self.syntax.borrowed())
+            .unwrap()
+    }
+
+    fn resolve(&mut self, file_resolver: &FileResolver) {
+        let name = self.name();
+        let paths = &[
+            PathBuf::from(format!("../{}.rs", name)),
+            PathBuf::from(format!("../{}/mod.rs", name)),
+        ];
+        self.points_to = paths.iter()
+            .filter_map(|path| file_resolver(self.owner.0, path))
+            .map(ModuleId)
+            .collect();
+    }
+}
diff --git a/crates/libanalysis/tests/tests.rs b/crates/libanalysis/tests/tests.rs
index 9ef5200af..931ab4183 100644
--- a/crates/libanalysis/tests/tests.rs
+++ b/crates/libanalysis/tests/tests.rs
@@ -43,3 +43,24 @@ fn test_resolve_module() {
         &symbols,
     );
 }
+
+#[test]
+fn test_resolve_parent_module() {
+    let mut world = WorldState::new();
+    world.change_file(FileId(1), Some("mod foo;".to_string()));
+    world.change_file(FileId(2), Some("".to_string()));
+
+    let snap = world.snapshot(|id, path| {
+        assert_eq!(id, FileId(1));
+        if path == PathBuf::from("../foo/mod.rs") {
+            return None;
+        }
+        assert_eq!(path, PathBuf::from("../foo.rs"));
+        Some(FileId(2))
+    });
+    let symbols = snap.parent_module(FileId(2));
+    assert_eq_dbg(
+        r#"[(FileId(1), FileSymbol { name: "foo", node_range: [0; 8), kind: MODULE })]"#,
+        &symbols,
+    );
+}