Merge #467

467: move function to code_model_api r=matklad a=matklad Co-authored-by: Aleksey Kladov <[email protected]>
author: bors[bot] <bors[bot]@users.noreply.github.com> 2019-01-08 17:35:08 +0000
committer: bors[bot] <bors[bot]@users.noreply.github.com> 2019-01-08 17:35:08 +0000
commit: 1c25bf05d714680c048d250a5d39e8a4c25f0c31 (patch)
tree: 9879fc268f2812576839118cf7e4c88df180a30b /crates/ra_hir/src/code_model_impl/function/scope.rs
parent: 3b166aee3c116762c817f1acd0f5e01e48452932 (diff)
parent: ac92973a6c5934377c6eca9906f3b7f17e220d4e (diff)
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 @@
+use std::sync::Arc;
+use rustc_hash::{FxHashMap, FxHashSet};
+use ra_syntax::{
+    AstNode, SyntaxNode, TextUnit, TextRange,
+    algo::generate,
+    ast,
+};
+use ra_arena::{Arena, RawId, impl_arena_id};
+use ra_db::LocalSyntaxPtr;
+use crate::{Name, AsName, expr::{PatId, ExprId, Pat, Expr, Body, Statement, BodySyntaxMapping}};
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct ScopeId(RawId);
+impl_arena_id!(ScopeId);
+#[derive(Debug, PartialEq, Eq)]
+pub struct FnScopes {
+    body: Arc<Body>,
+    scopes: Arena<ScopeId, ScopeData>,
+    scope_for: FxHashMap<ExprId, ScopeId>,
+}
+#[derive(Debug, PartialEq, Eq)]
+pub struct ScopeEntry {
+    name: Name,
+    pat: PatId,
+}
+#[derive(Debug, PartialEq, Eq)]
+pub struct ScopeData {
+    parent: Option<ScopeId>,
+    entries: Vec<ScopeEntry>,
+}
+impl FnScopes {
+    pub(crate) fn new(body: Arc<Body>) -> FnScopes {
+        let mut scopes = FnScopes {
+            body: body.clone(),
+            scopes: Arena::default(),
+            scope_for: FxHashMap::default(),
+        };
+        let root = scopes.root_scope();
+        scopes.add_params_bindings(root, body.args());
+        compute_expr_scopes(body.body_expr(), &body, &mut scopes, root);
+        scopes
+    }
+    pub fn entries(&self, scope: ScopeId) -> &[ScopeEntry] {
+        &self.scopes[scope].entries
+    }
+    pub fn scope_chain_for<'a>(&'a self, expr: ExprId) -> impl Iterator<Item = ScopeId> + 'a {
+        generate(self.scope_for(expr), move |&scope| {
+            self.scopes[scope].parent
+        })
+    }
+    pub fn resolve_local_name<'a>(
+        &'a self,
+        context_expr: ExprId,
+        name: Name,
+    ) -> Option<&'a ScopeEntry> {
+        let mut shadowed = FxHashSet::default();
+        let ret = self
+            .scope_chain_for(context_expr)
+            .flat_map(|scope| self.entries(scope).iter())
+            .filter(|entry| shadowed.insert(entry.name()))
+            .find(|entry| entry.name() == &name);
+        ret
+    }
+    fn root_scope(&mut self) -> ScopeId {
+        self.scopes.alloc(ScopeData {
+            parent: None,
+            entries: vec![],
+        })
+    }
+    fn new_scope(&mut self, parent: ScopeId) -> ScopeId {
+        self.scopes.alloc(ScopeData {
+            parent: Some(parent),
+            entries: vec![],
+        })
+    }
+    fn add_bindings(&mut self, body: &Body, scope: ScopeId, pat: PatId) {
+        match &body[pat] {
+            Pat::Bind { name } => self.scopes[scope].entries.push(ScopeEntry {
+                name: name.clone(),
+                pat,
+            }),
+            p => p.walk_child_pats(|pat| self.add_bindings(body, scope, pat)),
+        }
+    }
+    fn add_params_bindings(&mut self, scope: ScopeId, params: &[PatId]) {
+        let body = Arc::clone(&self.body);
+        params
+            .into_iter()
+            .for_each(|pat| self.add_bindings(&body, scope, *pat));
+    }
+    fn set_scope(&mut self, node: ExprId, scope: ScopeId) {
+        self.scope_for.insert(node, scope);
+    }
+    fn scope_for(&self, expr: ExprId) -> Option<ScopeId> {
+        self.scope_for.get(&expr).map(|&scope| scope)
+    }
+}
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct ScopesWithSyntaxMapping {
+    pub syntax_mapping: Arc<BodySyntaxMapping>,
+    pub scopes: Arc<FnScopes>,
+}
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct ScopeEntryWithSyntax {
+    name: Name,
+    ptr: LocalSyntaxPtr,
+}
+impl ScopeEntryWithSyntax {
+    pub fn name(&self) -> &Name {
+        &self.name
+    }
+    pub fn ptr(&self) -> LocalSyntaxPtr {
+        self.ptr
+    }
+}
+impl ScopesWithSyntaxMapping {
+    pub fn scope_chain<'a>(&'a self, node: &SyntaxNode) -> impl Iterator<Item = ScopeId> + 'a {
+        generate(self.scope_for(node), move |&scope| {
+            self.scopes.scopes[scope].parent
+        })
+    }
+    pub fn scope_chain_for_offset<'a>(
+        &'a self,
+        offset: TextUnit,
+    ) -> impl Iterator<Item = ScopeId> + 'a {
+        let scope = self
+            .scopes
+            .scope_for
+            .iter()
+            .filter_map(|(id, scope)| Some((self.syntax_mapping.expr_syntax(*id)?, scope)))
+            // find containing scope
+            .min_by_key(|(ptr, _scope)| {
+                (
+                    !(ptr.range().start() <= offset && offset <= ptr.range().end()),
+                    ptr.range().len(),
+                )
+            })
+            .map(|(ptr, scope)| self.adjust(ptr, *scope, offset));
+        generate(scope, move |&scope| self.scopes.scopes[scope].parent)
+    }
+    // XXX: during completion, cursor might be outside of any particular
+    // expression. Try to figure out the correct scope...
+    fn adjust(&self, ptr: LocalSyntaxPtr, original_scope: ScopeId, offset: TextUnit) -> ScopeId {
+        let r = ptr.range();
+        let child_scopes = self
+            .scopes
+            .scope_for
+            .iter()
+            .filter_map(|(id, scope)| Some((self.syntax_mapping.expr_syntax(*id)?, scope)))
+            .map(|(ptr, scope)| (ptr.range(), scope))
+            .filter(|(range, _)| range.start() <= offset && range.is_subrange(&r) && *range != r);
+        child_scopes
+            .max_by(|(r1, _), (r2, _)| {
+                if r2.is_subrange(&r1) {
+                    std::cmp::Ordering::Greater
+                } else if r1.is_subrange(&r2) {
+                    std::cmp::Ordering::Less
+                } else {
+                    r1.start().cmp(&r2.start())
+                }
+            })
+            .map(|(_ptr, scope)| *scope)
+            .unwrap_or(original_scope)
+    }
+    pub fn resolve_local_name(&self, name_ref: &ast::NameRef) -> Option<ScopeEntryWithSyntax> {
+        let mut shadowed = FxHashSet::default();
+        let name = name_ref.as_name();
+        let ret = self
+            .scope_chain(name_ref.syntax())
+            .flat_map(|scope| self.scopes.entries(scope).iter())
+            .filter(|entry| shadowed.insert(entry.name()))
+            .filter(|entry| entry.name() == &name)
+            .nth(0);
+        ret.and_then(|entry| {
+            Some(ScopeEntryWithSyntax {
+                name: entry.name().clone(),
+                ptr: self.syntax_mapping.pat_syntax(entry.pat())?,
+            })
+        })
+    }
+    pub fn find_all_refs(&self, pat: &ast::BindPat) -> Vec<ReferenceDescriptor> {
+        let fn_def = pat.syntax().ancestors().find_map(ast::FnDef::cast).unwrap();
+        let name_ptr = LocalSyntaxPtr::new(pat.syntax());
+        fn_def
+            .syntax()
+            .descendants()
+            .filter_map(ast::NameRef::cast)
+            .filter(|name_ref| match self.resolve_local_name(*name_ref) {
+                None => false,
+                Some(entry) => entry.ptr() == name_ptr,
+            })
+            .map(|name_ref| ReferenceDescriptor {
+                name: name_ref.syntax().text().to_string(),
+                range: name_ref.syntax().range(),
+            })
+            .collect()
+    }
+    fn scope_for(&self, node: &SyntaxNode) -> Option<ScopeId> {
+        node.ancestors()
+            .map(LocalSyntaxPtr::new)
+            .filter_map(|ptr| self.syntax_mapping.syntax_expr(ptr))
+            .find_map(|it| self.scopes.scope_for(it))
+    }
+}
+impl ScopeEntry {
+    pub fn name(&self) -> &Name {
+        &self.name
+    }
+    pub fn pat(&self) -> PatId {
+        self.pat
+    }
+}
+fn compute_block_scopes(
+    statements: &[Statement],
+    tail: Option<ExprId>,
+    body: &Body,
+    scopes: &mut FnScopes,
+    mut scope: ScopeId,
+) {
+    for stmt in statements {
+        match stmt {
+            Statement::Let {
+                pat, initializer, ..
+            } => {
+                if let Some(expr) = initializer {
+                    scopes.set_scope(*expr, scope);
+                    compute_expr_scopes(*expr, body, scopes, scope);
+                }
+                scope = scopes.new_scope(scope);
+                scopes.add_bindings(body, scope, *pat);
+            }
+            Statement::Expr(expr) => {
+                scopes.set_scope(*expr, scope);
+                compute_expr_scopes(*expr, body, scopes, scope);
+            }
+        }
+    }
+    if let Some(expr) = tail {
+        compute_expr_scopes(expr, body, scopes, scope);
+    }
+}
+fn compute_expr_scopes(expr: ExprId, body: &Body, scopes: &mut FnScopes, scope: ScopeId) {
+    scopes.set_scope(expr, scope);
+    match &body[expr] {
+        Expr::Block { statements, tail } => {
+            compute_block_scopes(&statements, *tail, body, scopes, scope);
+        }
+        Expr::For {
+            iterable,
+            pat,
+            body: body_expr,
+        } => {
+            compute_expr_scopes(*iterable, body, scopes, scope);
+            let scope = scopes.new_scope(scope);
+            scopes.add_bindings(body, scope, *pat);
+            compute_expr_scopes(*body_expr, body, scopes, scope);
+        }
+        Expr::Lambda {
+            args,
+            body: body_expr,
+            ..
+        } => {
+            let scope = scopes.new_scope(scope);
+            scopes.add_params_bindings(scope, &args);
+            compute_expr_scopes(*body_expr, body, scopes, scope);
+        }
+        Expr::Match { expr, arms } => {
+            compute_expr_scopes(*expr, body, scopes, scope);
+            for arm in arms {
+                let scope = scopes.new_scope(scope);
+                for pat in &arm.pats {
+                    scopes.add_bindings(body, scope, *pat);
+                }
+                scopes.set_scope(arm.expr, scope);
+                compute_expr_scopes(arm.expr, body, scopes, scope);
+            }
+        }
+        e => e.walk_child_exprs(|e| compute_expr_scopes(e, body, scopes, scope)),
+    };
+}
+#[derive(Debug)]
+pub struct ReferenceDescriptor {
+    pub range: TextRange,
+    pub name: String,
+}
+#[cfg(test)]
+mod tests {
+    use ra_editor::find_node_at_offset;
+    use ra_syntax::SourceFile;
+    use test_utils::{extract_offset, assert_eq_text};
+    use crate::expr;
+    use super::*;
+    fn do_check(code: &str, expected: &[&str]) {
+        let (off, code) = extract_offset(code);
+        let code = {
+            let mut buf = String::new();
+            let off = u32::from(off) as usize;
+            buf.push_str(&code[..off]);
+            buf.push_str("marker");
+            buf.push_str(&code[off..]);
+            buf
+        };
+        let file = SourceFile::parse(&code);
+        let marker: &ast::PathExpr = find_node_at_offset(file.syntax(), off).unwrap();
+        let fn_def: &ast::FnDef = find_node_at_offset(file.syntax(), off).unwrap();
+        let body_hir = expr::collect_fn_body_syntax(fn_def);
+        let scopes = FnScopes::new(Arc::clone(body_hir.body()));
+        let scopes = ScopesWithSyntaxMapping {
+            scopes: Arc::new(scopes),
+            syntax_mapping: Arc::new(body_hir),
+        };
+        let actual = scopes
+            .scope_chain(marker.syntax())
+            .flat_map(|scope| scopes.scopes.entries(scope))
+            .map(|it| it.name().to_string())
+            .collect::<Vec<_>>()
+            .join("\n");
+        let expected = expected.join("\n");
+        assert_eq_text!(&expected, &actual);
+    }
+    #[test]
+    fn test_lambda_scope() {
+        do_check(
+            r"
+            fn quux(foo: i32) {
+                let f = |bar, baz: i32| {
+                    <|>
+                };
+            }",
+            &["bar", "baz", "foo"],
+        );
+    }
+    #[test]
+    fn test_call_scope() {
+        do_check(
+            r"
+            fn quux() {
+                f(|x| <|> );
+            }",
+            &["x"],
+        );
+    }
+    #[test]
+    fn test_method_call_scope() {
+        do_check(
+            r"
+            fn quux() {
+                z.f(|x| <|> );
+            }",
+            &["x"],
+        );
+    }
+    #[test]
+    fn test_loop_scope() {
+        do_check(
+            r"
+            fn quux() {
+                loop {
+                    let x = ();
+                    <|>
+                };
+            }",
+            &["x"],
+        );
+    }
+    #[test]
+    fn test_match() {
+        do_check(
+            r"
+            fn quux() {
+                match () {
+                    Some(x) => {
+                        <|>
+                    }
+                };
+            }",
+            &["x"],
+        );
+    }
+    #[test]
+    fn test_shadow_variable() {
+        do_check(
+            r"
+            fn foo(x: String) {
+                let x : &str = &x<|>;
+            }",
+            &["x"],
+        );
+    }
+    fn do_check_local_name(code: &str, expected_offset: u32) {
+        let (off, code) = extract_offset(code);
+        let file = SourceFile::parse(&code);
+        let fn_def: &ast::FnDef = find_node_at_offset(file.syntax(), off).unwrap();
+        let name_ref: &ast::NameRef = find_node_at_offset(file.syntax(), off).unwrap();
+        let body_hir = expr::collect_fn_body_syntax(fn_def);
+        let scopes = FnScopes::new(Arc::clone(body_hir.body()));
+        let scopes = ScopesWithSyntaxMapping {
+            scopes: Arc::new(scopes),
+            syntax_mapping: Arc::new(body_hir),
+        };
+        let local_name_entry = scopes.resolve_local_name(name_ref).unwrap();
+        let local_name = local_name_entry.ptr();
+        let expected_name =
+            find_node_at_offset::<ast::Name>(file.syntax(), expected_offset.into()).unwrap();
+        assert_eq!(local_name.range(), expected_name.syntax().range());
+    }
+    #[test]
+    fn test_resolve_local_name() {
+        do_check_local_name(
+            r#"
+            fn foo(x: i32, y: u32) {
+                {
+                    let z = x * 2;
+                }
+                {
+                    let t = x<|> * 3;
+                }
+            }"#,
+            21,
+        );
+    }
+    #[test]
+    fn test_resolve_local_name_declaration() {
+        do_check_local_name(
+            r#"
+            fn foo(x: String) {
+                let x : &str = &x<|>;
+            }"#,
+            21,
+        );
+    }
+    #[test]
+    fn test_resolve_local_name_shadow() {
+        do_check_local_name(
+            r"
+        fn foo(x: String) {
+            let x : &str = &x;
+            x<|>
+        }",
+            46,
+        );
+    }
+}
author	bors[bot] <bors[bot]@users.noreply.github.com>	2019-01-08 17:35:08 +0000
committer	bors[bot] <bors[bot]@users.noreply.github.com>	2019-01-08 17:35:08 +0000
commit	1c25bf05d714680c048d250a5d39e8a4c25f0c31 (patch)
tree	9879fc268f2812576839118cf7e4c88df180a30b /crates/ra_hir/src/code_model_impl/function/scope.rs
parent	3b166aee3c116762c817f1acd0f5e01e48452932 (diff)
parent	ac92973a6c5934377c6eca9906f3b7f17e220d4e (diff)

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	}