From b937262c9b75a361b95a6a27260a71c737e035bf Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Tue, 21 Aug 2018 18:30:10 +0300 Subject: Module map implementation --- crates/libanalysis/src/lib.rs | 124 ++++++++++++++++++++++----------- crates/libanalysis/src/module_map.rs | 117 +++++++++++++++++++++++++++++++ crates/libanalysis/tests/tests.rs | 21 ++++++ crates/libsyntax2/src/ast/generated.rs | 14 +++- crates/libsyntax2/src/grammar.ron | 10 ++- crates/server/src/main_loop/mod.rs | 6 +- crates/server/src/server_world.rs | 2 +- 7 files changed, 247 insertions(+), 47 deletions(-) create mode 100644 crates/libanalysis/src/module_map.rs (limited to 'crates') 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 = ::std::result::Result; @@ -42,11 +47,12 @@ pub type FileResolver = dyn Fn(FileId, &Path) -> Option + Send + Sync; #[derive(Debug)] pub struct WorldState { + updates: Vec, data: Arc } -#[derive(Clone)] pub struct World { + needs_reindex: AtomicBool, file_resolver: Arc, data: Arc, } @@ -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 + 'static + Send + Sync) -> World { + pub fn snapshot( + &mut self, + file_resolver: impl Fn(FileId, &Path) -> Option + '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)>) { - 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 { - (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>, + 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, +} + +#[derive(Clone, Debug)] +struct Link { + owner: ModuleId, + syntax: SyntaxNode, + points_to: Vec, +} + +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 { + 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)> + '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 { + 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, + ); +} diff --git a/crates/libsyntax2/src/ast/generated.rs b/crates/libsyntax2/src/ast/generated.rs index e8a87eba5..610b5198c 100644 --- a/crates/libsyntax2/src/ast/generated.rs +++ b/crates/libsyntax2/src/ast/generated.rs @@ -127,6 +127,12 @@ impl<'a> File<'a> { .children() .filter_map(FnDef::cast) } + + pub fn modules(self) -> impl Iterator> + 'a { + self.syntax() + .children() + .filter_map(Module::cast) + } } // FnDef @@ -239,7 +245,13 @@ impl<'a> AstNode<'a> for Module<'a> { impl<'a> ast::NameOwner<'a> for Module<'a> {} impl<'a> ast::AttrsOwner<'a> for Module<'a> {} -impl<'a> Module<'a> {} +impl<'a> Module<'a> { + pub fn modules(self) -> impl Iterator> + 'a { + self.syntax() + .children() + .filter_map(Module::cast) + } +} // Name #[derive(Debug, Clone, Copy)] diff --git a/crates/libsyntax2/src/grammar.ron b/crates/libsyntax2/src/grammar.ron index abeffb2c3..8e644d3c4 100644 --- a/crates/libsyntax2/src/grammar.ron +++ b/crates/libsyntax2/src/grammar.ron @@ -218,7 +218,8 @@ Grammar( ast: { "File": ( collections: [ - ["functions", "FnDef"] + ["functions", "FnDef"], + ["modules", "Module"], ] ), "FnDef": ( traits: ["NameOwner", "AttrsOwner"] ), @@ -231,7 +232,12 @@ Grammar( "NamedField": ( traits: ["NameOwner", "AttrsOwner"] ), "EnumDef": ( traits: ["NameOwner", "AttrsOwner"] ), "TraitDef": ( traits: ["NameOwner", "AttrsOwner"] ), - "Module": ( traits: ["NameOwner", "AttrsOwner"] ), + "Module": ( + traits: ["NameOwner", "AttrsOwner"], + collections: [ + ["modules", "Module"] + ] + ), "ConstDef": ( traits: ["NameOwner", "AttrsOwner"] ), "StaticDef": ( traits: ["NameOwner", "AttrsOwner"] ), "TypeDef": ( traits: ["NameOwner", "AttrsOwner"] ), diff --git a/crates/server/src/main_loop/mod.rs b/crates/server/src/main_loop/mod.rs index ad7c480dc..12a903dac 100644 --- a/crates/server/src/main_loop/mod.rs +++ b/crates/server/src/main_loop/mod.rs @@ -94,7 +94,7 @@ pub(super) fn main_loop( Event::Msg(msg) => { match msg { RawMsg::Request(req) => { - if !on_request(io, &state, pool, &task_sender, req)? { + if !on_request(io, &mut state, pool, &task_sender, req)? { return Ok(()); } } @@ -114,7 +114,7 @@ pub(super) fn main_loop( fn on_request( io: &mut Io, - world: &ServerWorldState, + world: &mut ServerWorldState, pool: &ThreadPool, sender: &Sender, req: RawRequest, @@ -252,7 +252,7 @@ fn on_notification( fn handle_request_on_threadpool( req: &mut Option, pool: &ThreadPool, - world: &ServerWorldState, + world: &mut ServerWorldState, sender: &Sender, f: fn(ServerWorld, R::Params) -> Result, ) -> Result<()> diff --git a/crates/server/src/server_world.rs b/crates/server/src/server_world.rs index c0d2efb86..9850822cd 100644 --- a/crates/server/src/server_world.rs +++ b/crates/server/src/server_world.rs @@ -86,7 +86,7 @@ impl ServerWorldState { Ok(()) } - pub fn snapshot(&self) -> ServerWorld { + pub fn snapshot(&mut self) -> ServerWorld { let pm = self.path_map.clone(); ServerWorld { analysis: self.analysis.snapshot(move |id, path| { -- cgit v1.2.3