From b6fcd462781826795e6ab32a69cd332496b537c2 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Sun, 25 Nov 2018 19:02:14 +0300 Subject: Codify Arena pattern --- crates/ra_analysis/src/arena.rs | 96 ++++++++++++++++++++++ crates/ra_analysis/src/db.rs | 3 +- .../ra_analysis/src/descriptors/function/scope.rs | 36 ++++---- crates/ra_analysis/src/descriptors/module/imp.rs | 11 +-- crates/ra_analysis/src/descriptors/module/mod.rs | 76 ++++++----------- crates/ra_analysis/src/lib.rs | 1 + 6 files changed, 145 insertions(+), 78 deletions(-) create mode 100644 crates/ra_analysis/src/arena.rs (limited to 'crates/ra_analysis/src') diff --git a/crates/ra_analysis/src/arena.rs b/crates/ra_analysis/src/arena.rs new file mode 100644 index 000000000..98ed89274 --- /dev/null +++ b/crates/ra_analysis/src/arena.rs @@ -0,0 +1,96 @@ +//! A simple id-based arena, similar to https://github.com/fitzgen/id-arena. +//! We use our own version for more compact id's and to allow inherent impls +//! on Ids. + +use std::{ + fmt, + ops::{Index, IndexMut}, + hash::{Hash, Hasher}, + marker::PhantomData, +}; + +pub(crate) struct Id { + idx: u32, + _ty: PhantomData T>, +} + +impl fmt::Debug for Id { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_tuple("Id").field(&self.idx).finish() + } +} +impl Copy for Id {} +impl Clone for Id { + fn clone(&self) -> Id { + *self + } +} + +impl PartialEq for Id { + fn eq(&self, other: &Id) -> bool { + self.idx == other.idx + } +} + +impl Eq for Id {} + +impl Hash for Id { + fn hash(&self, h: &mut H) { + self.idx.hash(h); + } +} + +#[derive(Debug, PartialEq, Eq)] +pub(crate) struct Arena { + data: Vec, +} + +impl Default for Arena { + fn default() -> Arena { + Arena { data: Vec::new() } + } +} + +impl Arena { + pub(crate) fn push(&mut self, value: T) -> Id { + let id = self.data.len() as u32; + self.data.push(value); + Id { + idx: id as u32, + _ty: PhantomData, + } + } + + pub(crate) fn keys<'a>(&'a self) -> impl Iterator> + 'a { + (0..(self.data.len() as u32)).into_iter().map(|idx| Id { + idx, + _ty: PhantomData, + }) + } + + pub(crate) fn items<'a>(&'a self) -> impl Iterator, &T)> + 'a { + self.data.iter().enumerate().map(|(idx, item)| { + let idx = idx as u32; + ( + Id { + idx, + _ty: PhantomData, + }, + item, + ) + }) + } +} + +impl Index> for Arena { + type Output = T; + fn index(&self, id: Id) -> &T { + &self.data[id.idx as usize] + } +} + +impl IndexMut> for Arena { + fn index_mut(&mut self, id: Id) -> &mut T { + &mut self.data[id.idx as usize] + } +} diff --git a/crates/ra_analysis/src/db.rs b/crates/ra_analysis/src/db.rs index 7c28c9a2b..6b56f99ac 100644 --- a/crates/ra_analysis/src/db.rs +++ b/crates/ra_analysis/src/db.rs @@ -1,5 +1,5 @@ use std::sync::Arc; - +#[cfg(test)] use parking_lot::Mutex; use ra_editor::LineIndex; use ra_syntax::{SourceFileNode, SyntaxNode}; @@ -33,6 +33,7 @@ impl salsa::Database for RootDatabase { &self.runtime } + #[allow(unused)] fn salsa_event(&self, event: impl Fn() -> salsa::Event) { #[cfg(test)] { diff --git a/crates/ra_analysis/src/descriptors/function/scope.rs b/crates/ra_analysis/src/descriptors/function/scope.rs index bbe16947c..54d7fa456 100644 --- a/crates/ra_analysis/src/descriptors/function/scope.rs +++ b/crates/ra_analysis/src/descriptors/function/scope.rs @@ -6,15 +6,17 @@ use ra_syntax::{ AstNode, SmolStr, SyntaxNodeRef, }; -use crate::syntax_ptr::LocalSyntaxPtr; +use crate::{ + syntax_ptr::LocalSyntaxPtr, + arena::{Arena, Id}, +}; -#[derive(Clone, Copy, PartialEq, Eq, Debug)] -pub(crate) struct ScopeId(u32); +pub(crate) type ScopeId = Id; #[derive(Debug, PartialEq, Eq)] pub struct FnScopes { pub(crate) self_param: Option, - scopes: Vec, + scopes: Arena, scope_for: FxHashMap, } @@ -25,7 +27,7 @@ pub struct ScopeEntry { } #[derive(Debug, PartialEq, Eq)] -struct ScopeData { +pub(crate) struct ScopeData { parent: Option, entries: Vec, } @@ -37,7 +39,7 @@ impl FnScopes { .param_list() .and_then(|it| it.self_param()) .map(|it| LocalSyntaxPtr::new(it.syntax())), - scopes: Vec::new(), + scopes: Arena::default(), scope_for: FxHashMap::default(), }; let root = scopes.root_scope(); @@ -48,26 +50,24 @@ impl FnScopes { scopes } pub(crate) fn entries(&self, scope: ScopeId) -> &[ScopeEntry] { - &self.get(scope).entries + &self.scopes[scope].entries } pub fn scope_chain<'a>(&'a self, node: SyntaxNodeRef) -> impl Iterator + 'a { - generate(self.scope_for(node), move |&scope| self.get(scope).parent) + generate(self.scope_for(node), move |&scope| { + self.scopes[scope].parent + }) } fn root_scope(&mut self) -> ScopeId { - let res = ScopeId(self.scopes.len() as u32); self.scopes.push(ScopeData { parent: None, entries: vec![], - }); - res + }) } fn new_scope(&mut self, parent: ScopeId) -> ScopeId { - let res = ScopeId(self.scopes.len() as u32); self.scopes.push(ScopeData { parent: Some(parent), entries: vec![], - }); - res + }) } fn add_bindings(&mut self, scope: ScopeId, pat: ast::Pat) { let entries = pat @@ -75,7 +75,7 @@ impl FnScopes { .descendants() .filter_map(ast::BindPat::cast) .filter_map(ScopeEntry::new); - self.get_mut(scope).entries.extend(entries); + self.scopes[scope].entries.extend(entries); } fn add_params_bindings(&mut self, scope: ScopeId, params: Option) { params @@ -93,12 +93,6 @@ impl FnScopes { .filter_map(|it| self.scope_for.get(&it).map(|&scope| scope)) .next() } - fn get(&self, scope: ScopeId) -> &ScopeData { - &self.scopes[scope.0 as usize] - } - fn get_mut(&mut self, scope: ScopeId) -> &mut ScopeData { - &mut self.scopes[scope.0 as usize] - } } impl ScopeEntry { diff --git a/crates/ra_analysis/src/descriptors/module/imp.rs b/crates/ra_analysis/src/descriptors/module/imp.rs index d4dce861f..80892acb7 100644 --- a/crates/ra_analysis/src/descriptors/module/imp.rs +++ b/crates/ra_analysis/src/descriptors/module/imp.rs @@ -94,10 +94,7 @@ fn create_module_tree<'a>( db: &impl DescriptorDatabase, source_root: SourceRootId, ) -> Cancelable { - let mut tree = ModuleTree { - mods: Vec::new(), - links: Vec::new(), - }; + let mut tree = ModuleTree::default(); let mut roots = FxHashMap::default(); let mut visited = FxHashSet::default(); @@ -154,7 +151,7 @@ fn build_subtree( .into_iter() .map(|file_id| match roots.remove(&file_id) { Some(module_id) => { - tree.module_mut(module_id).parent = Some(link); + tree.mods[module_id].parent = Some(link); Ok(module_id) } None => build_subtree( @@ -184,8 +181,8 @@ fn build_subtree( } }; - tree.link_mut(link).points_to = points_to; - tree.link_mut(link).problem = problem; + tree.links[link].points_to = points_to; + tree.links[link].problem = problem; } Ok(id) } diff --git a/crates/ra_analysis/src/descriptors/module/mod.rs b/crates/ra_analysis/src/descriptors/module/mod.rs index acc6c1c5a..54ff95b66 100644 --- a/crates/ra_analysis/src/descriptors/module/mod.rs +++ b/crates/ra_analysis/src/descriptors/module/mod.rs @@ -15,7 +15,8 @@ use relative_path::RelativePathBuf; use crate::{ db::SyntaxDatabase, syntax_ptr::SyntaxPtr, FileId, FilePosition, Cancelable, descriptors::{Path, PathKind, DescriptorDatabase}, - input::SourceRootId + input::SourceRootId, + arena::{Arena, Id}, }; pub(crate) use self::nameres::ModuleScope; @@ -157,26 +158,22 @@ impl ModuleDescriptor { /// Module encapsulate the logic of transitioning from the fuzzy world of files /// (which can have multiple parents) to the precise world of modules (which /// always have one parent). -#[derive(Debug, PartialEq, Eq, Hash)] +#[derive(Default, Debug, PartialEq, Eq)] pub(crate) struct ModuleTree { - mods: Vec, - links: Vec, + mods: Arena, + links: Arena, } impl ModuleTree { fn modules<'a>(&'a self) -> impl Iterator + 'a { - self.mods - .iter() - .enumerate() - .map(|(idx, _)| ModuleId(idx as u32)) + self.mods.keys() } fn modules_for_source(&self, source: ModuleSource) -> Vec { self.mods - .iter() - .enumerate() + .items() .filter(|(_idx, it)| it.source == source) - .map(|(idx, _)| ModuleId(idx as u32)) + .map(|(idx, _)| idx) .collect() } @@ -201,11 +198,8 @@ enum ModuleSourceNode { Module(ast::ModuleNode), } -#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)] -pub(crate) struct ModuleId(u32); - -#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)] -struct LinkId(u32); +pub(crate) type ModuleId = Id; +type LinkId = Id; #[derive(Clone, Debug, Hash, PartialEq, Eq)] pub enum Problem { @@ -220,14 +214,14 @@ pub enum Problem { impl ModuleId { fn source(self, tree: &ModuleTree) -> ModuleSource { - tree.module(self).source + tree.mods[self].source } fn parent_link(self, tree: &ModuleTree) -> Option { - tree.module(self).parent + tree.mods[self].parent } fn parent(self, tree: &ModuleTree) -> Option { let link = self.parent_link(tree)?; - Some(tree.link(link).owner) + Some(tree.links[link].owner) } fn crate_root(self, tree: &ModuleTree) -> ModuleId { generate(Some(self), move |it| it.parent(tree)) @@ -235,27 +229,26 @@ impl ModuleId { .unwrap() } fn child(self, tree: &ModuleTree, name: &str) -> Option { - let link = tree - .module(self) + let link = tree.mods[self] .children .iter() - .map(|&it| tree.link(it)) + .map(|&it| &tree.links[it]) .find(|it| it.name == name)?; Some(*link.points_to.first()?) } fn children<'a>(self, tree: &'a ModuleTree) -> impl Iterator + 'a { - tree.module(self).children.iter().filter_map(move |&it| { - let link = tree.link(it); + tree.mods[self].children.iter().filter_map(move |&it| { + let link = &tree.links[it]; let module = *link.points_to.first()?; Some((link.name.clone(), module)) }) } fn problems(self, tree: &ModuleTree, db: &impl SyntaxDatabase) -> Vec<(SyntaxNode, Problem)> { - tree.module(self) + tree.mods[self] .children .iter() .filter_map(|&it| { - let p = tree.link(it).problem.clone()?; + let p = tree.links[it].problem.clone()?; let s = it.bind_source(tree, db); let s = s.borrowed().name().unwrap().syntax().owned(); Some((s, p)) @@ -266,17 +259,17 @@ impl ModuleId { impl LinkId { fn owner(self, tree: &ModuleTree) -> ModuleId { - tree.link(self).owner + tree.links[self].owner } fn name(self, tree: &ModuleTree) -> SmolStr { - tree.link(self).name.clone() + tree.links[self].name.clone() } fn bind_source<'a>(self, tree: &ModuleTree, db: &impl SyntaxDatabase) -> ast::ModuleNode { let owner = self.owner(tree); match owner.source(tree).resolve(db) { ModuleSourceNode::SourceFile(root) => { let ast = imp::modules(root.borrowed()) - .find(|(name, _)| name == &tree.link(self).name) + .find(|(name, _)| name == &tree.links[self].name) .unwrap() .1; ast.owned() @@ -287,7 +280,7 @@ impl LinkId { } #[derive(Debug, PartialEq, Eq, Hash)] -struct ModuleData { +pub(crate) struct ModuleData { source: ModuleSource, parent: Option, children: Vec, @@ -339,28 +332,13 @@ struct LinkData { } 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 + self.mods.push(data) } 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); + let owner = data.owner; + let id = self.links.push(data); + self.mods[owner].children.push(id); id } } diff --git a/crates/ra_analysis/src/lib.rs b/crates/ra_analysis/src/lib.rs index eccda84a7..cedbd1fc8 100644 --- a/crates/ra_analysis/src/lib.rs +++ b/crates/ra_analysis/src/lib.rs @@ -9,6 +9,7 @@ extern crate relative_path; extern crate rustc_hash; extern crate salsa; +mod arena; mod db; mod loc2id; mod input; -- cgit v1.2.3