diff options
author | Aleksey Kladov <[email protected]> | 2019-01-08 17:11:13 +0000 |
---|---|---|
committer | Aleksey Kladov <[email protected]> | 2019-01-08 17:11:13 +0000 |
commit | ac92973a6c5934377c6eca9906f3b7f17e220d4e (patch) | |
tree | 9879fc268f2812576839118cf7e4c88df180a30b /crates/ra_hir/src/code_model_impl/function/scope.rs | |
parent | 3b166aee3c116762c817f1acd0f5e01e48452932 (diff) |
move function to code_model_api
Diffstat (limited to 'crates/ra_hir/src/code_model_impl/function/scope.rs')
-rw-r--r-- | crates/ra_hir/src/code_model_impl/function/scope.rs | 481 |
1 files changed, 481 insertions, 0 deletions
diff --git a/crates/ra_hir/src/code_model_impl/function/scope.rs b/crates/ra_hir/src/code_model_impl/function/scope.rs new file mode 100644 index 000000000..699784f71 --- /dev/null +++ b/crates/ra_hir/src/code_model_impl/function/scope.rs | |||
@@ -0,0 +1,481 @@ | |||
1 | use std::sync::Arc; | ||
2 | |||
3 | use rustc_hash::{FxHashMap, FxHashSet}; | ||
4 | |||
5 | use ra_syntax::{ | ||
6 | AstNode, SyntaxNode, TextUnit, TextRange, | ||
7 | algo::generate, | ||
8 | ast, | ||
9 | }; | ||
10 | use ra_arena::{Arena, RawId, impl_arena_id}; | ||
11 | use ra_db::LocalSyntaxPtr; | ||
12 | |||
13 | use crate::{Name, AsName, expr::{PatId, ExprId, Pat, Expr, Body, Statement, BodySyntaxMapping}}; | ||
14 | |||
15 | #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] | ||
16 | pub struct ScopeId(RawId); | ||
17 | impl_arena_id!(ScopeId); | ||
18 | |||
19 | #[derive(Debug, PartialEq, Eq)] | ||
20 | pub struct FnScopes { | ||
21 | body: Arc<Body>, | ||
22 | scopes: Arena<ScopeId, ScopeData>, | ||
23 | scope_for: FxHashMap<ExprId, ScopeId>, | ||
24 | } | ||
25 | |||
26 | #[derive(Debug, PartialEq, Eq)] | ||
27 | pub struct ScopeEntry { | ||
28 | name: Name, | ||
29 | pat: PatId, | ||
30 | } | ||
31 | |||
32 | #[derive(Debug, PartialEq, Eq)] | ||
33 | pub struct ScopeData { | ||
34 | parent: Option<ScopeId>, | ||
35 | entries: Vec<ScopeEntry>, | ||
36 | } | ||
37 | |||
38 | impl FnScopes { | ||
39 | pub(crate) fn new(body: Arc<Body>) -> FnScopes { | ||
40 | let mut scopes = FnScopes { | ||
41 | body: body.clone(), | ||
42 | scopes: Arena::default(), | ||
43 | scope_for: FxHashMap::default(), | ||
44 | }; | ||
45 | let root = scopes.root_scope(); | ||
46 | scopes.add_params_bindings(root, body.args()); | ||
47 | compute_expr_scopes(body.body_expr(), &body, &mut scopes, root); | ||
48 | scopes | ||
49 | } | ||
50 | pub fn entries(&self, scope: ScopeId) -> &[ScopeEntry] { | ||
51 | &self.scopes[scope].entries | ||
52 | } | ||
53 | pub fn scope_chain_for<'a>(&'a self, expr: ExprId) -> impl Iterator<Item = ScopeId> + 'a { | ||
54 | generate(self.scope_for(expr), move |&scope| { | ||
55 | self.scopes[scope].parent | ||
56 | }) | ||
57 | } | ||
58 | |||
59 | pub fn resolve_local_name<'a>( | ||
60 | &'a self, | ||
61 | context_expr: ExprId, | ||
62 | name: Name, | ||
63 | ) -> Option<&'a ScopeEntry> { | ||
64 | let mut shadowed = FxHashSet::default(); | ||
65 | let ret = self | ||
66 | .scope_chain_for(context_expr) | ||
67 | .flat_map(|scope| self.entries(scope).iter()) | ||
68 | .filter(|entry| shadowed.insert(entry.name())) | ||
69 | .find(|entry| entry.name() == &name); | ||
70 | ret | ||
71 | } | ||
72 | |||
73 | fn root_scope(&mut self) -> ScopeId { | ||
74 | self.scopes.alloc(ScopeData { | ||
75 | parent: None, | ||
76 | entries: vec![], | ||
77 | }) | ||
78 | } | ||
79 | fn new_scope(&mut self, parent: ScopeId) -> ScopeId { | ||
80 | self.scopes.alloc(ScopeData { | ||
81 | parent: Some(parent), | ||
82 | entries: vec![], | ||
83 | }) | ||
84 | } | ||
85 | fn add_bindings(&mut self, body: &Body, scope: ScopeId, pat: PatId) { | ||
86 | match &body[pat] { | ||
87 | Pat::Bind { name } => self.scopes[scope].entries.push(ScopeEntry { | ||
88 | name: name.clone(), | ||
89 | pat, | ||
90 | }), | ||
91 | p => p.walk_child_pats(|pat| self.add_bindings(body, scope, pat)), | ||
92 | } | ||
93 | } | ||
94 | fn add_params_bindings(&mut self, scope: ScopeId, params: &[PatId]) { | ||
95 | let body = Arc::clone(&self.body); | ||
96 | params | ||
97 | .into_iter() | ||
98 | .for_each(|pat| self.add_bindings(&body, scope, *pat)); | ||
99 | } | ||
100 | fn set_scope(&mut self, node: ExprId, scope: ScopeId) { | ||
101 | self.scope_for.insert(node, scope); | ||
102 | } | ||
103 | fn scope_for(&self, expr: ExprId) -> Option<ScopeId> { | ||
104 | self.scope_for.get(&expr).map(|&scope| scope) | ||
105 | } | ||
106 | } | ||
107 | |||
108 | #[derive(Debug, Clone, PartialEq, Eq)] | ||
109 | pub struct ScopesWithSyntaxMapping { | ||
110 | pub syntax_mapping: Arc<BodySyntaxMapping>, | ||
111 | pub scopes: Arc<FnScopes>, | ||
112 | } | ||
113 | |||
114 | #[derive(Debug, Clone, PartialEq, Eq)] | ||
115 | pub struct ScopeEntryWithSyntax { | ||
116 | name: Name, | ||
117 | ptr: LocalSyntaxPtr, | ||
118 | } | ||
119 | |||
120 | impl ScopeEntryWithSyntax { | ||
121 | pub fn name(&self) -> &Name { | ||
122 | &self.name | ||
123 | } | ||
124 | pub fn ptr(&self) -> LocalSyntaxPtr { | ||
125 | self.ptr | ||
126 | } | ||
127 | } | ||
128 | |||
129 | impl ScopesWithSyntaxMapping { | ||
130 | pub fn scope_chain<'a>(&'a self, node: &SyntaxNode) -> impl Iterator<Item = ScopeId> + 'a { | ||
131 | generate(self.scope_for(node), move |&scope| { | ||
132 | self.scopes.scopes[scope].parent | ||
133 | }) | ||
134 | } | ||
135 | pub fn scope_chain_for_offset<'a>( | ||
136 | &'a self, | ||
137 | offset: TextUnit, | ||
138 | ) -> impl Iterator<Item = ScopeId> + 'a { | ||
139 | let scope = self | ||
140 | .scopes | ||
141 | .scope_for | ||
142 | .iter() | ||
143 | .filter_map(|(id, scope)| Some((self.syntax_mapping.expr_syntax(*id)?, scope))) | ||
144 | // find containing scope | ||
145 | .min_by_key(|(ptr, _scope)| { | ||
146 | ( | ||
147 | !(ptr.range().start() <= offset && offset <= ptr.range().end()), | ||
148 | ptr.range().len(), | ||
149 | ) | ||
150 | }) | ||
151 | .map(|(ptr, scope)| self.adjust(ptr, *scope, offset)); | ||
152 | |||
153 | generate(scope, move |&scope| self.scopes.scopes[scope].parent) | ||
154 | } | ||
155 | // XXX: during completion, cursor might be outside of any particular | ||
156 | // expression. Try to figure out the correct scope... | ||
157 | fn adjust(&self, ptr: LocalSyntaxPtr, original_scope: ScopeId, offset: TextUnit) -> ScopeId { | ||
158 | let r = ptr.range(); | ||
159 | let child_scopes = self | ||
160 | .scopes | ||
161 | .scope_for | ||
162 | .iter() | ||
163 | .filter_map(|(id, scope)| Some((self.syntax_mapping.expr_syntax(*id)?, scope))) | ||
164 | .map(|(ptr, scope)| (ptr.range(), scope)) | ||
165 | .filter(|(range, _)| range.start() <= offset && range.is_subrange(&r) && *range != r); | ||
166 | |||
167 | child_scopes | ||
168 | .max_by(|(r1, _), (r2, _)| { | ||
169 | if r2.is_subrange(&r1) { | ||
170 | std::cmp::Ordering::Greater | ||
171 | } else if r1.is_subrange(&r2) { | ||
172 | std::cmp::Ordering::Less | ||
173 | } else { | ||
174 | r1.start().cmp(&r2.start()) | ||
175 | } | ||
176 | }) | ||
177 | .map(|(_ptr, scope)| *scope) | ||
178 | .unwrap_or(original_scope) | ||
179 | } | ||
180 | |||
181 | pub fn resolve_local_name(&self, name_ref: &ast::NameRef) -> Option<ScopeEntryWithSyntax> { | ||
182 | let mut shadowed = FxHashSet::default(); | ||
183 | let name = name_ref.as_name(); | ||
184 | let ret = self | ||
185 | .scope_chain(name_ref.syntax()) | ||
186 | .flat_map(|scope| self.scopes.entries(scope).iter()) | ||
187 | .filter(|entry| shadowed.insert(entry.name())) | ||
188 | .filter(|entry| entry.name() == &name) | ||
189 | .nth(0); | ||
190 | ret.and_then(|entry| { | ||
191 | Some(ScopeEntryWithSyntax { | ||
192 | name: entry.name().clone(), | ||
193 | ptr: self.syntax_mapping.pat_syntax(entry.pat())?, | ||
194 | }) | ||
195 | }) | ||
196 | } | ||
197 | |||
198 | pub fn find_all_refs(&self, pat: &ast::BindPat) -> Vec<ReferenceDescriptor> { | ||
199 | let fn_def = pat.syntax().ancestors().find_map(ast::FnDef::cast).unwrap(); | ||
200 | let name_ptr = LocalSyntaxPtr::new(pat.syntax()); | ||
201 | fn_def | ||
202 | .syntax() | ||
203 | .descendants() | ||
204 | .filter_map(ast::NameRef::cast) | ||
205 | .filter(|name_ref| match self.resolve_local_name(*name_ref) { | ||
206 | None => false, | ||
207 | Some(entry) => entry.ptr() == name_ptr, | ||
208 | }) | ||
209 | .map(|name_ref| ReferenceDescriptor { | ||
210 | name: name_ref.syntax().text().to_string(), | ||
211 | range: name_ref.syntax().range(), | ||
212 | }) | ||
213 | .collect() | ||
214 | } | ||
215 | |||
216 | fn scope_for(&self, node: &SyntaxNode) -> Option<ScopeId> { | ||
217 | node.ancestors() | ||
218 | .map(LocalSyntaxPtr::new) | ||
219 | .filter_map(|ptr| self.syntax_mapping.syntax_expr(ptr)) | ||
220 | .find_map(|it| self.scopes.scope_for(it)) | ||
221 | } | ||
222 | } | ||
223 | |||
224 | impl ScopeEntry { | ||
225 | pub fn name(&self) -> &Name { | ||
226 | &self.name | ||
227 | } | ||
228 | pub fn pat(&self) -> PatId { | ||
229 | self.pat | ||
230 | } | ||
231 | } | ||
232 | |||
233 | fn compute_block_scopes( | ||
234 | statements: &[Statement], | ||
235 | tail: Option<ExprId>, | ||
236 | body: &Body, | ||
237 | scopes: &mut FnScopes, | ||
238 | mut scope: ScopeId, | ||
239 | ) { | ||
240 | for stmt in statements { | ||
241 | match stmt { | ||
242 | Statement::Let { | ||
243 | pat, initializer, .. | ||
244 | } => { | ||
245 | if let Some(expr) = initializer { | ||
246 | scopes.set_scope(*expr, scope); | ||
247 | compute_expr_scopes(*expr, body, scopes, scope); | ||
248 | } | ||
249 | scope = scopes.new_scope(scope); | ||
250 | scopes.add_bindings(body, scope, *pat); | ||
251 | } | ||
252 | Statement::Expr(expr) => { | ||
253 | scopes.set_scope(*expr, scope); | ||
254 | compute_expr_scopes(*expr, body, scopes, scope); | ||
255 | } | ||
256 | } | ||
257 | } | ||
258 | if let Some(expr) = tail { | ||
259 | compute_expr_scopes(expr, body, scopes, scope); | ||
260 | } | ||
261 | } | ||
262 | |||
263 | fn compute_expr_scopes(expr: ExprId, body: &Body, scopes: &mut FnScopes, scope: ScopeId) { | ||
264 | scopes.set_scope(expr, scope); | ||
265 | match &body[expr] { | ||
266 | Expr::Block { statements, tail } => { | ||
267 | compute_block_scopes(&statements, *tail, body, scopes, scope); | ||
268 | } | ||
269 | Expr::For { | ||
270 | iterable, | ||
271 | pat, | ||
272 | body: body_expr, | ||
273 | } => { | ||
274 | compute_expr_scopes(*iterable, body, scopes, scope); | ||
275 | let scope = scopes.new_scope(scope); | ||
276 | scopes.add_bindings(body, scope, *pat); | ||
277 | compute_expr_scopes(*body_expr, body, scopes, scope); | ||
278 | } | ||
279 | Expr::Lambda { | ||
280 | args, | ||
281 | body: body_expr, | ||
282 | .. | ||
283 | } => { | ||
284 | let scope = scopes.new_scope(scope); | ||
285 | scopes.add_params_bindings(scope, &args); | ||
286 | compute_expr_scopes(*body_expr, body, scopes, scope); | ||
287 | } | ||
288 | Expr::Match { expr, arms } => { | ||
289 | compute_expr_scopes(*expr, body, scopes, scope); | ||
290 | for arm in arms { | ||
291 | let scope = scopes.new_scope(scope); | ||
292 | for pat in &arm.pats { | ||
293 | scopes.add_bindings(body, scope, *pat); | ||
294 | } | ||
295 | scopes.set_scope(arm.expr, scope); | ||
296 | compute_expr_scopes(arm.expr, body, scopes, scope); | ||
297 | } | ||
298 | } | ||
299 | e => e.walk_child_exprs(|e| compute_expr_scopes(e, body, scopes, scope)), | ||
300 | }; | ||
301 | } | ||
302 | |||
303 | #[derive(Debug)] | ||
304 | pub struct ReferenceDescriptor { | ||
305 | pub range: TextRange, | ||
306 | pub name: String, | ||
307 | } | ||
308 | |||
309 | #[cfg(test)] | ||
310 | mod tests { | ||
311 | use ra_editor::find_node_at_offset; | ||
312 | use ra_syntax::SourceFile; | ||
313 | use test_utils::{extract_offset, assert_eq_text}; | ||
314 | |||
315 | use crate::expr; | ||
316 | |||
317 | use super::*; | ||
318 | |||
319 | fn do_check(code: &str, expected: &[&str]) { | ||
320 | let (off, code) = extract_offset(code); | ||
321 | let code = { | ||
322 | let mut buf = String::new(); | ||
323 | let off = u32::from(off) as usize; | ||
324 | buf.push_str(&code[..off]); | ||
325 | buf.push_str("marker"); | ||
326 | buf.push_str(&code[off..]); | ||
327 | buf | ||
328 | }; | ||
329 | let file = SourceFile::parse(&code); | ||
330 | let marker: &ast::PathExpr = find_node_at_offset(file.syntax(), off).unwrap(); | ||
331 | let fn_def: &ast::FnDef = find_node_at_offset(file.syntax(), off).unwrap(); | ||
332 | let body_hir = expr::collect_fn_body_syntax(fn_def); | ||
333 | let scopes = FnScopes::new(Arc::clone(body_hir.body())); | ||
334 | let scopes = ScopesWithSyntaxMapping { | ||
335 | scopes: Arc::new(scopes), | ||
336 | syntax_mapping: Arc::new(body_hir), | ||
337 | }; | ||
338 | let actual = scopes | ||
339 | .scope_chain(marker.syntax()) | ||
340 | .flat_map(|scope| scopes.scopes.entries(scope)) | ||
341 | .map(|it| it.name().to_string()) | ||
342 | .collect::<Vec<_>>() | ||
343 | .join("\n"); | ||
344 | let expected = expected.join("\n"); | ||
345 | assert_eq_text!(&expected, &actual); | ||
346 | } | ||
347 | |||
348 | #[test] | ||
349 | fn test_lambda_scope() { | ||
350 | do_check( | ||
351 | r" | ||
352 | fn quux(foo: i32) { | ||
353 | let f = |bar, baz: i32| { | ||
354 | <|> | ||
355 | }; | ||
356 | }", | ||
357 | &["bar", "baz", "foo"], | ||
358 | ); | ||
359 | } | ||
360 | |||
361 | #[test] | ||
362 | fn test_call_scope() { | ||
363 | do_check( | ||
364 | r" | ||
365 | fn quux() { | ||
366 | f(|x| <|> ); | ||
367 | }", | ||
368 | &["x"], | ||
369 | ); | ||
370 | } | ||
371 | |||
372 | #[test] | ||
373 | fn test_method_call_scope() { | ||
374 | do_check( | ||
375 | r" | ||
376 | fn quux() { | ||
377 | z.f(|x| <|> ); | ||
378 | }", | ||
379 | &["x"], | ||
380 | ); | ||
381 | } | ||
382 | |||
383 | #[test] | ||
384 | fn test_loop_scope() { | ||
385 | do_check( | ||
386 | r" | ||
387 | fn quux() { | ||
388 | loop { | ||
389 | let x = (); | ||
390 | <|> | ||
391 | }; | ||
392 | }", | ||
393 | &["x"], | ||
394 | ); | ||
395 | } | ||
396 | |||
397 | #[test] | ||
398 | fn test_match() { | ||
399 | do_check( | ||
400 | r" | ||
401 | fn quux() { | ||
402 | match () { | ||
403 | Some(x) => { | ||
404 | <|> | ||
405 | } | ||
406 | }; | ||
407 | }", | ||
408 | &["x"], | ||
409 | ); | ||
410 | } | ||
411 | |||
412 | #[test] | ||
413 | fn test_shadow_variable() { | ||
414 | do_check( | ||
415 | r" | ||
416 | fn foo(x: String) { | ||
417 | let x : &str = &x<|>; | ||
418 | }", | ||
419 | &["x"], | ||
420 | ); | ||
421 | } | ||
422 | |||
423 | fn do_check_local_name(code: &str, expected_offset: u32) { | ||
424 | let (off, code) = extract_offset(code); | ||
425 | let file = SourceFile::parse(&code); | ||
426 | let fn_def: &ast::FnDef = find_node_at_offset(file.syntax(), off).unwrap(); | ||
427 | let name_ref: &ast::NameRef = find_node_at_offset(file.syntax(), off).unwrap(); | ||
428 | |||
429 | let body_hir = expr::collect_fn_body_syntax(fn_def); | ||
430 | let scopes = FnScopes::new(Arc::clone(body_hir.body())); | ||
431 | let scopes = ScopesWithSyntaxMapping { | ||
432 | scopes: Arc::new(scopes), | ||
433 | syntax_mapping: Arc::new(body_hir), | ||
434 | }; | ||
435 | |||
436 | let local_name_entry = scopes.resolve_local_name(name_ref).unwrap(); | ||
437 | let local_name = local_name_entry.ptr(); | ||
438 | let expected_name = | ||
439 | find_node_at_offset::<ast::Name>(file.syntax(), expected_offset.into()).unwrap(); | ||
440 | assert_eq!(local_name.range(), expected_name.syntax().range()); | ||
441 | } | ||
442 | |||
443 | #[test] | ||
444 | fn test_resolve_local_name() { | ||
445 | do_check_local_name( | ||
446 | r#" | ||
447 | fn foo(x: i32, y: u32) { | ||
448 | { | ||
449 | let z = x * 2; | ||
450 | } | ||
451 | { | ||
452 | let t = x<|> * 3; | ||
453 | } | ||
454 | }"#, | ||
455 | 21, | ||
456 | ); | ||
457 | } | ||
458 | |||
459 | #[test] | ||
460 | fn test_resolve_local_name_declaration() { | ||
461 | do_check_local_name( | ||
462 | r#" | ||
463 | fn foo(x: String) { | ||
464 | let x : &str = &x<|>; | ||
465 | }"#, | ||
466 | 21, | ||
467 | ); | ||
468 | } | ||
469 | |||
470 | #[test] | ||
471 | fn test_resolve_local_name_shadow() { | ||
472 | do_check_local_name( | ||
473 | r" | ||
474 | fn foo(x: String) { | ||
475 | let x : &str = &x; | ||
476 | x<|> | ||
477 | }", | ||
478 | 46, | ||
479 | ); | ||
480 | } | ||
481 | } | ||