diff options
Diffstat (limited to 'crates/ra_analysis/src/hir/function/scope.rs')
-rw-r--r-- | crates/ra_analysis/src/hir/function/scope.rs | 424 |
1 files changed, 424 insertions, 0 deletions
diff --git a/crates/ra_analysis/src/hir/function/scope.rs b/crates/ra_analysis/src/hir/function/scope.rs new file mode 100644 index 000000000..5307a0a8e --- /dev/null +++ b/crates/ra_analysis/src/hir/function/scope.rs | |||
@@ -0,0 +1,424 @@ | |||
1 | use rustc_hash::{FxHashMap, FxHashSet}; | ||
2 | |||
3 | use ra_syntax::{ | ||
4 | algo::generate, | ||
5 | ast::{self, ArgListOwner, LoopBodyOwner, NameOwner}, | ||
6 | AstNode, SmolStr, SyntaxNodeRef, | ||
7 | }; | ||
8 | |||
9 | use crate::{ | ||
10 | syntax_ptr::LocalSyntaxPtr, | ||
11 | arena::{Arena, Id}, | ||
12 | }; | ||
13 | |||
14 | pub(crate) type ScopeId = Id<ScopeData>; | ||
15 | |||
16 | #[derive(Debug, PartialEq, Eq)] | ||
17 | pub struct FnScopes { | ||
18 | pub(crate) self_param: Option<LocalSyntaxPtr>, | ||
19 | scopes: Arena<ScopeData>, | ||
20 | scope_for: FxHashMap<LocalSyntaxPtr, ScopeId>, | ||
21 | } | ||
22 | |||
23 | #[derive(Debug, PartialEq, Eq)] | ||
24 | pub struct ScopeEntry { | ||
25 | name: SmolStr, | ||
26 | ptr: LocalSyntaxPtr, | ||
27 | } | ||
28 | |||
29 | #[derive(Debug, PartialEq, Eq)] | ||
30 | pub(crate) struct ScopeData { | ||
31 | parent: Option<ScopeId>, | ||
32 | entries: Vec<ScopeEntry>, | ||
33 | } | ||
34 | |||
35 | impl FnScopes { | ||
36 | pub(crate) fn new(fn_def: ast::FnDef) -> FnScopes { | ||
37 | let mut scopes = FnScopes { | ||
38 | self_param: fn_def | ||
39 | .param_list() | ||
40 | .and_then(|it| it.self_param()) | ||
41 | .map(|it| LocalSyntaxPtr::new(it.syntax())), | ||
42 | scopes: Arena::default(), | ||
43 | scope_for: FxHashMap::default(), | ||
44 | }; | ||
45 | let root = scopes.root_scope(); | ||
46 | scopes.add_params_bindings(root, fn_def.param_list()); | ||
47 | if let Some(body) = fn_def.body() { | ||
48 | compute_block_scopes(body, &mut scopes, root) | ||
49 | } | ||
50 | scopes | ||
51 | } | ||
52 | pub(crate) fn entries(&self, scope: ScopeId) -> &[ScopeEntry] { | ||
53 | &self.scopes[scope].entries | ||
54 | } | ||
55 | pub fn scope_chain<'a>(&'a self, node: SyntaxNodeRef) -> impl Iterator<Item = ScopeId> + 'a { | ||
56 | generate(self.scope_for(node), move |&scope| { | ||
57 | self.scopes[scope].parent | ||
58 | }) | ||
59 | } | ||
60 | fn root_scope(&mut self) -> ScopeId { | ||
61 | self.scopes.alloc(ScopeData { | ||
62 | parent: None, | ||
63 | entries: vec![], | ||
64 | }) | ||
65 | } | ||
66 | fn new_scope(&mut self, parent: ScopeId) -> ScopeId { | ||
67 | self.scopes.alloc(ScopeData { | ||
68 | parent: Some(parent), | ||
69 | entries: vec![], | ||
70 | }) | ||
71 | } | ||
72 | fn add_bindings(&mut self, scope: ScopeId, pat: ast::Pat) { | ||
73 | let entries = pat | ||
74 | .syntax() | ||
75 | .descendants() | ||
76 | .filter_map(ast::BindPat::cast) | ||
77 | .filter_map(ScopeEntry::new); | ||
78 | self.scopes[scope].entries.extend(entries); | ||
79 | } | ||
80 | fn add_params_bindings(&mut self, scope: ScopeId, params: Option<ast::ParamList>) { | ||
81 | params | ||
82 | .into_iter() | ||
83 | .flat_map(|it| it.params()) | ||
84 | .filter_map(|it| it.pat()) | ||
85 | .for_each(|it| self.add_bindings(scope, it)); | ||
86 | } | ||
87 | fn set_scope(&mut self, node: SyntaxNodeRef, scope: ScopeId) { | ||
88 | self.scope_for.insert(LocalSyntaxPtr::new(node), scope); | ||
89 | } | ||
90 | fn scope_for(&self, node: SyntaxNodeRef) -> Option<ScopeId> { | ||
91 | node.ancestors() | ||
92 | .map(LocalSyntaxPtr::new) | ||
93 | .filter_map(|it| self.scope_for.get(&it).map(|&scope| scope)) | ||
94 | .next() | ||
95 | } | ||
96 | } | ||
97 | |||
98 | impl ScopeEntry { | ||
99 | fn new(pat: ast::BindPat) -> Option<ScopeEntry> { | ||
100 | let name = pat.name()?; | ||
101 | let res = ScopeEntry { | ||
102 | name: name.text(), | ||
103 | ptr: LocalSyntaxPtr::new(pat.syntax()), | ||
104 | }; | ||
105 | Some(res) | ||
106 | } | ||
107 | pub(crate) fn name(&self) -> &SmolStr { | ||
108 | &self.name | ||
109 | } | ||
110 | pub(crate) fn ptr(&self) -> LocalSyntaxPtr { | ||
111 | self.ptr | ||
112 | } | ||
113 | } | ||
114 | |||
115 | fn compute_block_scopes(block: ast::Block, scopes: &mut FnScopes, mut scope: ScopeId) { | ||
116 | for stmt in block.statements() { | ||
117 | match stmt { | ||
118 | ast::Stmt::LetStmt(stmt) => { | ||
119 | if let Some(expr) = stmt.initializer() { | ||
120 | scopes.set_scope(expr.syntax(), scope); | ||
121 | compute_expr_scopes(expr, scopes, scope); | ||
122 | } | ||
123 | scope = scopes.new_scope(scope); | ||
124 | if let Some(pat) = stmt.pat() { | ||
125 | scopes.add_bindings(scope, pat); | ||
126 | } | ||
127 | } | ||
128 | ast::Stmt::ExprStmt(expr_stmt) => { | ||
129 | if let Some(expr) = expr_stmt.expr() { | ||
130 | scopes.set_scope(expr.syntax(), scope); | ||
131 | compute_expr_scopes(expr, scopes, scope); | ||
132 | } | ||
133 | } | ||
134 | } | ||
135 | } | ||
136 | if let Some(expr) = block.expr() { | ||
137 | scopes.set_scope(expr.syntax(), scope); | ||
138 | compute_expr_scopes(expr, scopes, scope); | ||
139 | } | ||
140 | } | ||
141 | |||
142 | fn compute_expr_scopes(expr: ast::Expr, scopes: &mut FnScopes, scope: ScopeId) { | ||
143 | match expr { | ||
144 | ast::Expr::IfExpr(e) => { | ||
145 | let cond_scope = e | ||
146 | .condition() | ||
147 | .and_then(|cond| compute_cond_scopes(cond, scopes, scope)); | ||
148 | if let Some(block) = e.then_branch() { | ||
149 | compute_block_scopes(block, scopes, cond_scope.unwrap_or(scope)); | ||
150 | } | ||
151 | if let Some(block) = e.else_branch() { | ||
152 | compute_block_scopes(block, scopes, scope); | ||
153 | } | ||
154 | } | ||
155 | ast::Expr::BlockExpr(e) => { | ||
156 | if let Some(block) = e.block() { | ||
157 | compute_block_scopes(block, scopes, scope); | ||
158 | } | ||
159 | } | ||
160 | ast::Expr::LoopExpr(e) => { | ||
161 | if let Some(block) = e.loop_body() { | ||
162 | compute_block_scopes(block, scopes, scope); | ||
163 | } | ||
164 | } | ||
165 | ast::Expr::WhileExpr(e) => { | ||
166 | let cond_scope = e | ||
167 | .condition() | ||
168 | .and_then(|cond| compute_cond_scopes(cond, scopes, scope)); | ||
169 | if let Some(block) = e.loop_body() { | ||
170 | compute_block_scopes(block, scopes, cond_scope.unwrap_or(scope)); | ||
171 | } | ||
172 | } | ||
173 | ast::Expr::ForExpr(e) => { | ||
174 | if let Some(expr) = e.iterable() { | ||
175 | compute_expr_scopes(expr, scopes, scope); | ||
176 | } | ||
177 | let mut scope = scope; | ||
178 | if let Some(pat) = e.pat() { | ||
179 | scope = scopes.new_scope(scope); | ||
180 | scopes.add_bindings(scope, pat); | ||
181 | } | ||
182 | if let Some(block) = e.loop_body() { | ||
183 | compute_block_scopes(block, scopes, scope); | ||
184 | } | ||
185 | } | ||
186 | ast::Expr::LambdaExpr(e) => { | ||
187 | let scope = scopes.new_scope(scope); | ||
188 | scopes.add_params_bindings(scope, e.param_list()); | ||
189 | if let Some(body) = e.body() { | ||
190 | scopes.set_scope(body.syntax(), scope); | ||
191 | compute_expr_scopes(body, scopes, scope); | ||
192 | } | ||
193 | } | ||
194 | ast::Expr::CallExpr(e) => { | ||
195 | compute_call_scopes(e.expr(), e.arg_list(), scopes, scope); | ||
196 | } | ||
197 | ast::Expr::MethodCallExpr(e) => { | ||
198 | compute_call_scopes(e.expr(), e.arg_list(), scopes, scope); | ||
199 | } | ||
200 | ast::Expr::MatchExpr(e) => { | ||
201 | if let Some(expr) = e.expr() { | ||
202 | compute_expr_scopes(expr, scopes, scope); | ||
203 | } | ||
204 | for arm in e.match_arm_list().into_iter().flat_map(|it| it.arms()) { | ||
205 | let scope = scopes.new_scope(scope); | ||
206 | for pat in arm.pats() { | ||
207 | scopes.add_bindings(scope, pat); | ||
208 | } | ||
209 | if let Some(expr) = arm.expr() { | ||
210 | compute_expr_scopes(expr, scopes, scope); | ||
211 | } | ||
212 | } | ||
213 | } | ||
214 | _ => expr | ||
215 | .syntax() | ||
216 | .children() | ||
217 | .filter_map(ast::Expr::cast) | ||
218 | .for_each(|expr| compute_expr_scopes(expr, scopes, scope)), | ||
219 | }; | ||
220 | |||
221 | fn compute_call_scopes( | ||
222 | receiver: Option<ast::Expr>, | ||
223 | arg_list: Option<ast::ArgList>, | ||
224 | scopes: &mut FnScopes, | ||
225 | scope: ScopeId, | ||
226 | ) { | ||
227 | arg_list | ||
228 | .into_iter() | ||
229 | .flat_map(|it| it.args()) | ||
230 | .chain(receiver) | ||
231 | .for_each(|expr| compute_expr_scopes(expr, scopes, scope)); | ||
232 | } | ||
233 | |||
234 | fn compute_cond_scopes( | ||
235 | cond: ast::Condition, | ||
236 | scopes: &mut FnScopes, | ||
237 | scope: ScopeId, | ||
238 | ) -> Option<ScopeId> { | ||
239 | if let Some(expr) = cond.expr() { | ||
240 | compute_expr_scopes(expr, scopes, scope); | ||
241 | } | ||
242 | if let Some(pat) = cond.pat() { | ||
243 | let s = scopes.new_scope(scope); | ||
244 | scopes.add_bindings(s, pat); | ||
245 | Some(s) | ||
246 | } else { | ||
247 | None | ||
248 | } | ||
249 | } | ||
250 | } | ||
251 | |||
252 | pub fn resolve_local_name<'a>( | ||
253 | name_ref: ast::NameRef, | ||
254 | scopes: &'a FnScopes, | ||
255 | ) -> Option<&'a ScopeEntry> { | ||
256 | let mut shadowed = FxHashSet::default(); | ||
257 | let ret = scopes | ||
258 | .scope_chain(name_ref.syntax()) | ||
259 | .flat_map(|scope| scopes.entries(scope).iter()) | ||
260 | .filter(|entry| shadowed.insert(entry.name())) | ||
261 | .filter(|entry| entry.name() == &name_ref.text()) | ||
262 | .nth(0); | ||
263 | ret | ||
264 | } | ||
265 | |||
266 | #[cfg(test)] | ||
267 | mod tests { | ||
268 | use ra_editor::find_node_at_offset; | ||
269 | use ra_syntax::SourceFileNode; | ||
270 | use test_utils::extract_offset; | ||
271 | |||
272 | use super::*; | ||
273 | |||
274 | fn do_check(code: &str, expected: &[&str]) { | ||
275 | let (off, code) = extract_offset(code); | ||
276 | let code = { | ||
277 | let mut buf = String::new(); | ||
278 | let off = u32::from(off) as usize; | ||
279 | buf.push_str(&code[..off]); | ||
280 | buf.push_str("marker"); | ||
281 | buf.push_str(&code[off..]); | ||
282 | buf | ||
283 | }; | ||
284 | let file = SourceFileNode::parse(&code); | ||
285 | let marker: ast::PathExpr = find_node_at_offset(file.syntax(), off).unwrap(); | ||
286 | let fn_def: ast::FnDef = find_node_at_offset(file.syntax(), off).unwrap(); | ||
287 | let scopes = FnScopes::new(fn_def); | ||
288 | let actual = scopes | ||
289 | .scope_chain(marker.syntax()) | ||
290 | .flat_map(|scope| scopes.entries(scope)) | ||
291 | .map(|it| it.name()) | ||
292 | .collect::<Vec<_>>(); | ||
293 | assert_eq!(actual.as_slice(), expected); | ||
294 | } | ||
295 | |||
296 | #[test] | ||
297 | fn test_lambda_scope() { | ||
298 | do_check( | ||
299 | r" | ||
300 | fn quux(foo: i32) { | ||
301 | let f = |bar, baz: i32| { | ||
302 | <|> | ||
303 | }; | ||
304 | }", | ||
305 | &["bar", "baz", "foo"], | ||
306 | ); | ||
307 | } | ||
308 | |||
309 | #[test] | ||
310 | fn test_call_scope() { | ||
311 | do_check( | ||
312 | r" | ||
313 | fn quux() { | ||
314 | f(|x| <|> ); | ||
315 | }", | ||
316 | &["x"], | ||
317 | ); | ||
318 | } | ||
319 | |||
320 | #[test] | ||
321 | fn test_metod_call_scope() { | ||
322 | do_check( | ||
323 | r" | ||
324 | fn quux() { | ||
325 | z.f(|x| <|> ); | ||
326 | }", | ||
327 | &["x"], | ||
328 | ); | ||
329 | } | ||
330 | |||
331 | #[test] | ||
332 | fn test_loop_scope() { | ||
333 | do_check( | ||
334 | r" | ||
335 | fn quux() { | ||
336 | loop { | ||
337 | let x = (); | ||
338 | <|> | ||
339 | }; | ||
340 | }", | ||
341 | &["x"], | ||
342 | ); | ||
343 | } | ||
344 | |||
345 | #[test] | ||
346 | fn test_match() { | ||
347 | do_check( | ||
348 | r" | ||
349 | fn quux() { | ||
350 | match () { | ||
351 | Some(x) => { | ||
352 | <|> | ||
353 | } | ||
354 | }; | ||
355 | }", | ||
356 | &["x"], | ||
357 | ); | ||
358 | } | ||
359 | |||
360 | #[test] | ||
361 | fn test_shadow_variable() { | ||
362 | do_check( | ||
363 | r" | ||
364 | fn foo(x: String) { | ||
365 | let x : &str = &x<|>; | ||
366 | }", | ||
367 | &["x"], | ||
368 | ); | ||
369 | } | ||
370 | |||
371 | fn do_check_local_name(code: &str, expected_offset: u32) { | ||
372 | let (off, code) = extract_offset(code); | ||
373 | let file = SourceFileNode::parse(&code); | ||
374 | let fn_def: ast::FnDef = find_node_at_offset(file.syntax(), off).unwrap(); | ||
375 | let name_ref: ast::NameRef = find_node_at_offset(file.syntax(), off).unwrap(); | ||
376 | |||
377 | let scopes = FnScopes::new(fn_def); | ||
378 | |||
379 | let local_name_entry = resolve_local_name(name_ref, &scopes).unwrap(); | ||
380 | let local_name = local_name_entry.ptr().resolve(&file); | ||
381 | let expected_name = | ||
382 | find_node_at_offset::<ast::Name>(file.syntax(), expected_offset.into()).unwrap(); | ||
383 | assert_eq!(local_name.range(), expected_name.syntax().range()); | ||
384 | } | ||
385 | |||
386 | #[test] | ||
387 | fn test_resolve_local_name() { | ||
388 | do_check_local_name( | ||
389 | r#" | ||
390 | fn foo(x: i32, y: u32) { | ||
391 | { | ||
392 | let z = x * 2; | ||
393 | } | ||
394 | { | ||
395 | let t = x<|> * 3; | ||
396 | } | ||
397 | }"#, | ||
398 | 21, | ||
399 | ); | ||
400 | } | ||
401 | |||
402 | #[test] | ||
403 | fn test_resolve_local_name_declaration() { | ||
404 | do_check_local_name( | ||
405 | r#" | ||
406 | fn foo(x: String) { | ||
407 | let x : &str = &x<|>; | ||
408 | }"#, | ||
409 | 21, | ||
410 | ); | ||
411 | } | ||
412 | |||
413 | #[test] | ||
414 | fn test_resolve_local_name_shadow() { | ||
415 | do_check_local_name( | ||
416 | r" | ||
417 | fn foo(x: String) { | ||
418 | let x : &str = &x; | ||
419 | x<|> | ||
420 | }", | ||
421 | 46, | ||
422 | ); | ||
423 | } | ||
424 | } | ||