aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAleksey Kladov <[email protected]>2018-11-25 16:02:14 +0000
committerAleksey Kladov <[email protected]>2018-11-25 16:02:14 +0000
commitb6fcd462781826795e6ab32a69cd332496b537c2 (patch)
treebb44eaedf546e20a8b29b9b421fb0c3accc1ce74
parent8f5fb8341314e94b1d91afa50ca895f78180f948 (diff)
Codify Arena pattern
-rw-r--r--crates/ra_analysis/src/arena.rs96
-rw-r--r--crates/ra_analysis/src/db.rs3
-rw-r--r--crates/ra_analysis/src/descriptors/function/scope.rs36
-rw-r--r--crates/ra_analysis/src/descriptors/module/imp.rs11
-rw-r--r--crates/ra_analysis/src/descriptors/module/mod.rs76
-rw-r--r--crates/ra_analysis/src/lib.rs1
6 files changed, 145 insertions, 78 deletions
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 @@
1//! A simple id-based arena, similar to https://github.com/fitzgen/id-arena.
2//! We use our own version for more compact id's and to allow inherent impls
3//! on Ids.
4
5use std::{
6 fmt,
7 ops::{Index, IndexMut},
8 hash::{Hash, Hasher},
9 marker::PhantomData,
10};
11
12pub(crate) struct Id<T> {
13 idx: u32,
14 _ty: PhantomData<fn() -> T>,
15}
16
17impl<T> fmt::Debug for Id<T> {
18 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
19 f.debug_tuple("Id").field(&self.idx).finish()
20 }
21}
22impl<T> Copy for Id<T> {}
23impl<T> Clone for Id<T> {
24 fn clone(&self) -> Id<T> {
25 *self
26 }
27}
28
29impl<T> PartialEq for Id<T> {
30 fn eq(&self, other: &Id<T>) -> bool {
31 self.idx == other.idx
32 }
33}
34
35impl<T> Eq for Id<T> {}
36
37impl<T> Hash for Id<T> {
38 fn hash<H: Hasher>(&self, h: &mut H) {
39 self.idx.hash(h);
40 }
41}
42
43#[derive(Debug, PartialEq, Eq)]
44pub(crate) struct Arena<T> {
45 data: Vec<T>,
46}
47
48impl<T> Default for Arena<T> {
49 fn default() -> Arena<T> {
50 Arena { data: Vec::new() }
51 }
52}
53
54impl<T> Arena<T> {
55 pub(crate) fn push(&mut self, value: T) -> Id<T> {
56 let id = self.data.len() as u32;
57 self.data.push(value);
58 Id {
59 idx: id as u32,
60 _ty: PhantomData,
61 }
62 }
63
64 pub(crate) fn keys<'a>(&'a self) -> impl Iterator<Item = Id<T>> + 'a {
65 (0..(self.data.len() as u32)).into_iter().map(|idx| Id {
66 idx,
67 _ty: PhantomData,
68 })
69 }
70
71 pub(crate) fn items<'a>(&'a self) -> impl Iterator<Item = (Id<T>, &T)> + 'a {
72 self.data.iter().enumerate().map(|(idx, item)| {
73 let idx = idx as u32;
74 (
75 Id {
76 idx,
77 _ty: PhantomData,
78 },
79 item,
80 )
81 })
82 }
83}
84
85impl<T> Index<Id<T>> for Arena<T> {
86 type Output = T;
87 fn index(&self, id: Id<T>) -> &T {
88 &self.data[id.idx as usize]
89 }
90}
91
92impl<T> IndexMut<Id<T>> for Arena<T> {
93 fn index_mut(&mut self, id: Id<T>) -> &mut T {
94 &mut self.data[id.idx as usize]
95 }
96}
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 @@
1use std::sync::Arc; 1use std::sync::Arc;
2 2#[cfg(test)]
3use parking_lot::Mutex; 3use parking_lot::Mutex;
4use ra_editor::LineIndex; 4use ra_editor::LineIndex;
5use ra_syntax::{SourceFileNode, SyntaxNode}; 5use ra_syntax::{SourceFileNode, SyntaxNode};
@@ -33,6 +33,7 @@ impl salsa::Database for RootDatabase {
33 &self.runtime 33 &self.runtime
34 } 34 }
35 35
36 #[allow(unused)]
36 fn salsa_event(&self, event: impl Fn() -> salsa::Event<RootDatabase>) { 37 fn salsa_event(&self, event: impl Fn() -> salsa::Event<RootDatabase>) {
37 #[cfg(test)] 38 #[cfg(test)]
38 { 39 {
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::{
6 AstNode, SmolStr, SyntaxNodeRef, 6 AstNode, SmolStr, SyntaxNodeRef,
7}; 7};
8 8
9use crate::syntax_ptr::LocalSyntaxPtr; 9use crate::{
10 syntax_ptr::LocalSyntaxPtr,
11 arena::{Arena, Id},
12};
10 13
11#[derive(Clone, Copy, PartialEq, Eq, Debug)] 14pub(crate) type ScopeId = Id<ScopeData>;
12pub(crate) struct ScopeId(u32);
13 15
14#[derive(Debug, PartialEq, Eq)] 16#[derive(Debug, PartialEq, Eq)]
15pub struct FnScopes { 17pub struct FnScopes {
16 pub(crate) self_param: Option<LocalSyntaxPtr>, 18 pub(crate) self_param: Option<LocalSyntaxPtr>,
17 scopes: Vec<ScopeData>, 19 scopes: Arena<ScopeData>,
18 scope_for: FxHashMap<LocalSyntaxPtr, ScopeId>, 20 scope_for: FxHashMap<LocalSyntaxPtr, ScopeId>,
19} 21}
20 22
@@ -25,7 +27,7 @@ pub struct ScopeEntry {
25} 27}
26 28
27#[derive(Debug, PartialEq, Eq)] 29#[derive(Debug, PartialEq, Eq)]
28struct ScopeData { 30pub(crate) struct ScopeData {
29 parent: Option<ScopeId>, 31 parent: Option<ScopeId>,
30 entries: Vec<ScopeEntry>, 32 entries: Vec<ScopeEntry>,
31} 33}
@@ -37,7 +39,7 @@ impl FnScopes {
37 .param_list() 39 .param_list()
38 .and_then(|it| it.self_param()) 40 .and_then(|it| it.self_param())
39 .map(|it| LocalSyntaxPtr::new(it.syntax())), 41 .map(|it| LocalSyntaxPtr::new(it.syntax())),
40 scopes: Vec::new(), 42 scopes: Arena::default(),
41 scope_for: FxHashMap::default(), 43 scope_for: FxHashMap::default(),
42 }; 44 };
43 let root = scopes.root_scope(); 45 let root = scopes.root_scope();
@@ -48,26 +50,24 @@ impl FnScopes {
48 scopes 50 scopes
49 } 51 }
50 pub(crate) fn entries(&self, scope: ScopeId) -> &[ScopeEntry] { 52 pub(crate) fn entries(&self, scope: ScopeId) -> &[ScopeEntry] {
51 &self.get(scope).entries 53 &self.scopes[scope].entries
52 } 54 }
53 pub fn scope_chain<'a>(&'a self, node: SyntaxNodeRef) -> impl Iterator<Item = ScopeId> + 'a { 55 pub fn scope_chain<'a>(&'a self, node: SyntaxNodeRef) -> impl Iterator<Item = ScopeId> + 'a {
54 generate(self.scope_for(node), move |&scope| self.get(scope).parent) 56 generate(self.scope_for(node), move |&scope| {
57 self.scopes[scope].parent
58 })
55 } 59 }
56 fn root_scope(&mut self) -> ScopeId { 60 fn root_scope(&mut self) -> ScopeId {
57 let res = ScopeId(self.scopes.len() as u32);
58 self.scopes.push(ScopeData { 61 self.scopes.push(ScopeData {
59 parent: None, 62 parent: None,
60 entries: vec![], 63 entries: vec![],
61 }); 64 })
62 res
63 } 65 }
64 fn new_scope(&mut self, parent: ScopeId) -> ScopeId { 66 fn new_scope(&mut self, parent: ScopeId) -> ScopeId {
65 let res = ScopeId(self.scopes.len() as u32);
66 self.scopes.push(ScopeData { 67 self.scopes.push(ScopeData {
67 parent: Some(parent), 68 parent: Some(parent),
68 entries: vec![], 69 entries: vec![],
69 }); 70 })
70 res
71 } 71 }
72 fn add_bindings(&mut self, scope: ScopeId, pat: ast::Pat) { 72 fn add_bindings(&mut self, scope: ScopeId, pat: ast::Pat) {
73 let entries = pat 73 let entries = pat
@@ -75,7 +75,7 @@ impl FnScopes {
75 .descendants() 75 .descendants()
76 .filter_map(ast::BindPat::cast) 76 .filter_map(ast::BindPat::cast)
77 .filter_map(ScopeEntry::new); 77 .filter_map(ScopeEntry::new);
78 self.get_mut(scope).entries.extend(entries); 78 self.scopes[scope].entries.extend(entries);
79 } 79 }
80 fn add_params_bindings(&mut self, scope: ScopeId, params: Option<ast::ParamList>) { 80 fn add_params_bindings(&mut self, scope: ScopeId, params: Option<ast::ParamList>) {
81 params 81 params
@@ -93,12 +93,6 @@ impl FnScopes {
93 .filter_map(|it| self.scope_for.get(&it).map(|&scope| scope)) 93 .filter_map(|it| self.scope_for.get(&it).map(|&scope| scope))
94 .next() 94 .next()
95 } 95 }
96 fn get(&self, scope: ScopeId) -> &ScopeData {
97 &self.scopes[scope.0 as usize]
98 }
99 fn get_mut(&mut self, scope: ScopeId) -> &mut ScopeData {
100 &mut self.scopes[scope.0 as usize]
101 }
102} 96}
103 97
104impl ScopeEntry { 98impl 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>(
94 db: &impl DescriptorDatabase, 94 db: &impl DescriptorDatabase,
95 source_root: SourceRootId, 95 source_root: SourceRootId,
96) -> Cancelable<ModuleTree> { 96) -> Cancelable<ModuleTree> {
97 let mut tree = ModuleTree { 97 let mut tree = ModuleTree::default();
98 mods: Vec::new(),
99 links: Vec::new(),
100 };
101 98
102 let mut roots = FxHashMap::default(); 99 let mut roots = FxHashMap::default();
103 let mut visited = FxHashSet::default(); 100 let mut visited = FxHashSet::default();
@@ -154,7 +151,7 @@ fn build_subtree(
154 .into_iter() 151 .into_iter()
155 .map(|file_id| match roots.remove(&file_id) { 152 .map(|file_id| match roots.remove(&file_id) {
156 Some(module_id) => { 153 Some(module_id) => {
157 tree.module_mut(module_id).parent = Some(link); 154 tree.mods[module_id].parent = Some(link);
158 Ok(module_id) 155 Ok(module_id)
159 } 156 }
160 None => build_subtree( 157 None => build_subtree(
@@ -184,8 +181,8 @@ fn build_subtree(
184 } 181 }
185 }; 182 };
186 183
187 tree.link_mut(link).points_to = points_to; 184 tree.links[link].points_to = points_to;
188 tree.link_mut(link).problem = problem; 185 tree.links[link].problem = problem;
189 } 186 }
190 Ok(id) 187 Ok(id)
191} 188}
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;
15use crate::{ 15use crate::{
16 db::SyntaxDatabase, syntax_ptr::SyntaxPtr, FileId, FilePosition, Cancelable, 16 db::SyntaxDatabase, syntax_ptr::SyntaxPtr, FileId, FilePosition, Cancelable,
17 descriptors::{Path, PathKind, DescriptorDatabase}, 17 descriptors::{Path, PathKind, DescriptorDatabase},
18 input::SourceRootId 18 input::SourceRootId,
19 arena::{Arena, Id},
19}; 20};
20 21
21pub(crate) use self::nameres::ModuleScope; 22pub(crate) use self::nameres::ModuleScope;
@@ -157,26 +158,22 @@ impl ModuleDescriptor {
157/// Module encapsulate the logic of transitioning from the fuzzy world of files 158/// Module encapsulate the logic of transitioning from the fuzzy world of files
158/// (which can have multiple parents) to the precise world of modules (which 159/// (which can have multiple parents) to the precise world of modules (which
159/// always have one parent). 160/// always have one parent).
160#[derive(Debug, PartialEq, Eq, Hash)] 161#[derive(Default, Debug, PartialEq, Eq)]
161pub(crate) struct ModuleTree { 162pub(crate) struct ModuleTree {
162 mods: Vec<ModuleData>, 163 mods: Arena<ModuleData>,
163 links: Vec<LinkData>, 164 links: Arena<LinkData>,
164} 165}
165 166
166impl ModuleTree { 167impl ModuleTree {
167 fn modules<'a>(&'a self) -> impl Iterator<Item = ModuleId> + 'a { 168 fn modules<'a>(&'a self) -> impl Iterator<Item = ModuleId> + 'a {
168 self.mods 169 self.mods.keys()
169 .iter()
170 .enumerate()
171 .map(|(idx, _)| ModuleId(idx as u32))
172 } 170 }
173 171
174 fn modules_for_source(&self, source: ModuleSource) -> Vec<ModuleId> { 172 fn modules_for_source(&self, source: ModuleSource) -> Vec<ModuleId> {
175 self.mods 173 self.mods
176 .iter() 174 .items()
177 .enumerate()
178 .filter(|(_idx, it)| it.source == source) 175 .filter(|(_idx, it)| it.source == source)
179 .map(|(idx, _)| ModuleId(idx as u32)) 176 .map(|(idx, _)| idx)
180 .collect() 177 .collect()
181 } 178 }
182 179
@@ -201,11 +198,8 @@ enum ModuleSourceNode {
201 Module(ast::ModuleNode), 198 Module(ast::ModuleNode),
202} 199}
203 200
204#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)] 201pub(crate) type ModuleId = Id<ModuleData>;
205pub(crate) struct ModuleId(u32); 202type LinkId = Id<LinkData>;
206
207#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
208struct LinkId(u32);
209 203
210#[derive(Clone, Debug, Hash, PartialEq, Eq)] 204#[derive(Clone, Debug, Hash, PartialEq, Eq)]
211pub enum Problem { 205pub enum Problem {
@@ -220,14 +214,14 @@ pub enum Problem {
220 214
221impl ModuleId { 215impl ModuleId {
222 fn source(self, tree: &ModuleTree) -> ModuleSource { 216 fn source(self, tree: &ModuleTree) -> ModuleSource {
223 tree.module(self).source 217 tree.mods[self].source
224 } 218 }
225 fn parent_link(self, tree: &ModuleTree) -> Option<LinkId> { 219 fn parent_link(self, tree: &ModuleTree) -> Option<LinkId> {
226 tree.module(self).parent 220 tree.mods[self].parent
227 } 221 }
228 fn parent(self, tree: &ModuleTree) -> Option<ModuleId> { 222 fn parent(self, tree: &ModuleTree) -> Option<ModuleId> {
229 let link = self.parent_link(tree)?; 223 let link = self.parent_link(tree)?;
230 Some(tree.link(link).owner) 224 Some(tree.links[link].owner)
231 } 225 }
232 fn crate_root(self, tree: &ModuleTree) -> ModuleId { 226 fn crate_root(self, tree: &ModuleTree) -> ModuleId {
233 generate(Some(self), move |it| it.parent(tree)) 227 generate(Some(self), move |it| it.parent(tree))
@@ -235,27 +229,26 @@ impl ModuleId {
235 .unwrap() 229 .unwrap()
236 } 230 }
237 fn child(self, tree: &ModuleTree, name: &str) -> Option<ModuleId> { 231 fn child(self, tree: &ModuleTree, name: &str) -> Option<ModuleId> {
238 let link = tree 232 let link = tree.mods[self]
239 .module(self)
240 .children 233 .children
241 .iter() 234 .iter()
242 .map(|&it| tree.link(it)) 235 .map(|&it| &tree.links[it])
243 .find(|it| it.name == name)?; 236 .find(|it| it.name == name)?;
244 Some(*link.points_to.first()?) 237 Some(*link.points_to.first()?)
245 } 238 }
246 fn children<'a>(self, tree: &'a ModuleTree) -> impl Iterator<Item = (SmolStr, ModuleId)> + 'a { 239 fn children<'a>(self, tree: &'a ModuleTree) -> impl Iterator<Item = (SmolStr, ModuleId)> + 'a {
247 tree.module(self).children.iter().filter_map(move |&it| { 240 tree.mods[self].children.iter().filter_map(move |&it| {
248 let link = tree.link(it); 241 let link = &tree.links[it];
249 let module = *link.points_to.first()?; 242 let module = *link.points_to.first()?;
250 Some((link.name.clone(), module)) 243 Some((link.name.clone(), module))
251 }) 244 })
252 } 245 }
253 fn problems(self, tree: &ModuleTree, db: &impl SyntaxDatabase) -> Vec<(SyntaxNode, Problem)> { 246 fn problems(self, tree: &ModuleTree, db: &impl SyntaxDatabase) -> Vec<(SyntaxNode, Problem)> {
254 tree.module(self) 247 tree.mods[self]
255 .children 248 .children
256 .iter() 249 .iter()
257 .filter_map(|&it| { 250 .filter_map(|&it| {
258 let p = tree.link(it).problem.clone()?; 251 let p = tree.links[it].problem.clone()?;
259 let s = it.bind_source(tree, db); 252 let s = it.bind_source(tree, db);
260 let s = s.borrowed().name().unwrap().syntax().owned(); 253 let s = s.borrowed().name().unwrap().syntax().owned();
261 Some((s, p)) 254 Some((s, p))
@@ -266,17 +259,17 @@ impl ModuleId {
266 259
267impl LinkId { 260impl LinkId {
268 fn owner(self, tree: &ModuleTree) -> ModuleId { 261 fn owner(self, tree: &ModuleTree) -> ModuleId {
269 tree.link(self).owner 262 tree.links[self].owner
270 } 263 }
271 fn name(self, tree: &ModuleTree) -> SmolStr { 264 fn name(self, tree: &ModuleTree) -> SmolStr {
272 tree.link(self).name.clone() 265 tree.links[self].name.clone()
273 } 266 }
274 fn bind_source<'a>(self, tree: &ModuleTree, db: &impl SyntaxDatabase) -> ast::ModuleNode { 267 fn bind_source<'a>(self, tree: &ModuleTree, db: &impl SyntaxDatabase) -> ast::ModuleNode {
275 let owner = self.owner(tree); 268 let owner = self.owner(tree);
276 match owner.source(tree).resolve(db) { 269 match owner.source(tree).resolve(db) {
277 ModuleSourceNode::SourceFile(root) => { 270 ModuleSourceNode::SourceFile(root) => {
278 let ast = imp::modules(root.borrowed()) 271 let ast = imp::modules(root.borrowed())
279 .find(|(name, _)| name == &tree.link(self).name) 272 .find(|(name, _)| name == &tree.links[self].name)
280 .unwrap() 273 .unwrap()
281 .1; 274 .1;
282 ast.owned() 275 ast.owned()
@@ -287,7 +280,7 @@ impl LinkId {
287} 280}
288 281
289#[derive(Debug, PartialEq, Eq, Hash)] 282#[derive(Debug, PartialEq, Eq, Hash)]
290struct ModuleData { 283pub(crate) struct ModuleData {
291 source: ModuleSource, 284 source: ModuleSource,
292 parent: Option<LinkId>, 285 parent: Option<LinkId>,
293 children: Vec<LinkId>, 286 children: Vec<LinkId>,
@@ -339,28 +332,13 @@ struct LinkData {
339} 332}
340 333
341impl ModuleTree { 334impl ModuleTree {
342 fn module(&self, id: ModuleId) -> &ModuleData {
343 &self.mods[id.0 as usize]
344 }
345 fn module_mut(&mut self, id: ModuleId) -> &mut ModuleData {
346 &mut self.mods[id.0 as usize]
347 }
348 fn link(&self, id: LinkId) -> &LinkData {
349 &self.links[id.0 as usize]
350 }
351 fn link_mut(&mut self, id: LinkId) -> &mut LinkData {
352 &mut self.links[id.0 as usize]
353 }
354
355 fn push_mod(&mut self, data: ModuleData) -> ModuleId { 335 fn push_mod(&mut self, data: ModuleData) -> ModuleId {
356 let id = ModuleId(self.mods.len() as u32); 336 self.mods.push(data)
357 self.mods.push(data);
358 id
359 } 337 }
360 fn push_link(&mut self, data: LinkData) -> LinkId { 338 fn push_link(&mut self, data: LinkData) -> LinkId {
361 let id = LinkId(self.links.len() as u32); 339 let owner = data.owner;
362 self.mods[data.owner.0 as usize].children.push(id); 340 let id = self.links.push(data);
363 self.links.push(data); 341 self.mods[owner].children.push(id);
364 id 342 id
365 } 343 }
366} 344}
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;
9extern crate rustc_hash; 9extern crate rustc_hash;
10extern crate salsa; 10extern crate salsa;
11 11
12mod arena;
12mod db; 13mod db;
13mod loc2id; 14mod loc2id;
14mod input; 15mod input;