From a549da7e3ea66fd336de331c7c8d62b186051521 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Wed, 4 Mar 2020 12:05:14 +0100 Subject: Move SearchScope --- crates/ra_ide_db/src/lib.rs | 1 + crates/ra_ide_db/src/search.rs | 147 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 148 insertions(+) create mode 100644 crates/ra_ide_db/src/search.rs (limited to 'crates/ra_ide_db/src') diff --git a/crates/ra_ide_db/src/lib.rs b/crates/ra_ide_db/src/lib.rs index aa312c140..79f48c9e3 100644 --- a/crates/ra_ide_db/src/lib.rs +++ b/crates/ra_ide_db/src/lib.rs @@ -9,6 +9,7 @@ pub mod feature_flags; pub mod symbol_index; pub mod change; pub mod defs; +pub mod search; pub mod imports_locator; mod wasm_shims; diff --git a/crates/ra_ide_db/src/search.rs b/crates/ra_ide_db/src/search.rs new file mode 100644 index 000000000..add63b870 --- /dev/null +++ b/crates/ra_ide_db/src/search.rs @@ -0,0 +1,147 @@ +//! Generally, `search_scope` returns files that might contain references for the element. +//! For `pub(crate)` things it's a crate, for `pub` things it's a crate and dependant crates. +//! In some cases, the location of the references is known to within a `TextRange`, +//! e.g. for things like local variables. +use std::mem; + +use hir::{DefWithBody, HasSource, ModuleSource}; +use ra_db::{FileId, SourceDatabaseExt}; +use ra_prof::profile; +use ra_syntax::{AstNode, TextRange}; +use rustc_hash::FxHashMap; + +use crate::{defs::Definition, RootDatabase}; + +pub struct SearchScope { + entries: FxHashMap>, +} + +impl SearchScope { + fn new(entries: FxHashMap>) -> SearchScope { + SearchScope { entries } + } + + pub fn empty() -> SearchScope { + SearchScope::new(FxHashMap::default()) + } + + pub fn single_file(file: FileId) -> SearchScope { + SearchScope::new(std::iter::once((file, None)).collect()) + } + + pub fn for_def(def: &Definition, db: &RootDatabase) -> SearchScope { + let _p = profile("search_scope"); + let module = match def.module(db) { + Some(it) => it, + None => return SearchScope::empty(), + }; + let module_src = module.definition_source(db); + let file_id = module_src.file_id.original_file(db); + + if let Definition::Local(var) = def { + let range = match var.parent(db) { + DefWithBody::Function(f) => f.source(db).value.syntax().text_range(), + DefWithBody::Const(c) => c.source(db).value.syntax().text_range(), + DefWithBody::Static(s) => s.source(db).value.syntax().text_range(), + }; + let mut res = FxHashMap::default(); + res.insert(file_id, Some(range)); + return SearchScope::new(res); + } + + let vis = def.visibility(db).as_ref().map(|v| v.syntax().to_string()).unwrap_or_default(); + + if vis.as_str() == "pub(super)" { + if let Some(parent_module) = module.parent(db) { + let mut res = FxHashMap::default(); + let parent_src = parent_module.definition_source(db); + let file_id = parent_src.file_id.original_file(db); + + match parent_src.value { + ModuleSource::Module(m) => { + let range = Some(m.syntax().text_range()); + res.insert(file_id, range); + } + ModuleSource::SourceFile(_) => { + res.insert(file_id, None); + res.extend(parent_module.children(db).map(|m| { + let src = m.definition_source(db); + (src.file_id.original_file(db), None) + })); + } + } + return SearchScope::new(res); + } + } + + if vis.as_str() != "" { + let source_root_id = db.file_source_root(file_id); + let source_root = db.source_root(source_root_id); + let mut res = source_root.walk().map(|id| (id, None)).collect::>(); + + // FIXME: add "pub(in path)" + + if vis.as_str() == "pub(crate)" { + return SearchScope::new(res); + } + if vis.as_str() == "pub" { + let krate = module.krate(); + for rev_dep in krate.reverse_dependencies(db) { + let root_file = rev_dep.root_file(db); + let source_root_id = db.file_source_root(root_file); + let source_root = db.source_root(source_root_id); + res.extend(source_root.walk().map(|id| (id, None))); + } + return SearchScope::new(res); + } + } + + let mut res = FxHashMap::default(); + let range = match module_src.value { + ModuleSource::Module(m) => Some(m.syntax().text_range()), + ModuleSource::SourceFile(_) => None, + }; + res.insert(file_id, range); + SearchScope::new(res) + } + + pub fn intersection(&self, other: &SearchScope) -> SearchScope { + let (mut small, mut large) = (&self.entries, &other.entries); + if small.len() > large.len() { + mem::swap(&mut small, &mut large) + } + + let res = small + .iter() + .filter_map(|(file_id, r1)| { + let r2 = large.get(file_id)?; + let r = intersect_ranges(*r1, *r2)?; + Some((*file_id, r)) + }) + .collect(); + + return SearchScope::new(res); + + fn intersect_ranges( + r1: Option, + r2: Option, + ) -> Option> { + match (r1, r2) { + (None, r) | (r, None) => Some(r), + (Some(r1), Some(r2)) => { + let r = r1.intersection(&r2)?; + Some(Some(r)) + } + } + } + } +} + +impl IntoIterator for SearchScope { + type Item = (FileId, Option); + type IntoIter = std::collections::hash_map::IntoIter>; + + fn into_iter(self) -> Self::IntoIter { + self.entries.into_iter() + } +} -- cgit v1.2.3 From 1874b6738ab4b849e5cbcb37fe2019192f950e5e Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Wed, 4 Mar 2020 12:06:37 +0100 Subject: Move ReferenceKind --- crates/ra_ide_db/src/search.rs | 21 ++++++++++++++++++++- 1 file changed, 20 insertions(+), 1 deletion(-) (limited to 'crates/ra_ide_db/src') diff --git a/crates/ra_ide_db/src/search.rs b/crates/ra_ide_db/src/search.rs index add63b870..ca458388c 100644 --- a/crates/ra_ide_db/src/search.rs +++ b/crates/ra_ide_db/src/search.rs @@ -5,13 +5,32 @@ use std::mem; use hir::{DefWithBody, HasSource, ModuleSource}; -use ra_db::{FileId, SourceDatabaseExt}; +use ra_db::{FileId, FileRange, SourceDatabaseExt}; use ra_prof::profile; use ra_syntax::{AstNode, TextRange}; use rustc_hash::FxHashMap; use crate::{defs::Definition, RootDatabase}; +#[derive(Debug, Clone)] +pub struct Reference { + pub file_range: FileRange, + pub kind: ReferenceKind, + pub access: Option, +} + +#[derive(Debug, Clone, PartialEq)] +pub enum ReferenceKind { + StructLiteral, + Other, +} + +#[derive(Debug, Copy, Clone, PartialEq)] +pub enum ReferenceAccess { + Read, + Write, +} + pub struct SearchScope { entries: FxHashMap>, } -- cgit v1.2.3 From f79719b8ae4d1929acaa940802a1e293f7dd7a6b Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Wed, 4 Mar 2020 12:14:48 +0100 Subject: Move find_refs_to_def --- crates/ra_ide_db/src/search.rs | 149 ++++++++++++++++++++++++++++++++++++++++- 1 file changed, 146 insertions(+), 3 deletions(-) (limited to 'crates/ra_ide_db/src') diff --git a/crates/ra_ide_db/src/search.rs b/crates/ra_ide_db/src/search.rs index ca458388c..efd43f4c1 100644 --- a/crates/ra_ide_db/src/search.rs +++ b/crates/ra_ide_db/src/search.rs @@ -4,13 +4,19 @@ //! e.g. for things like local variables. use std::mem; -use hir::{DefWithBody, HasSource, ModuleSource}; +use hir::{DefWithBody, HasSource, ModuleSource, Semantics}; +use once_cell::unsync::Lazy; use ra_db::{FileId, FileRange, SourceDatabaseExt}; use ra_prof::profile; -use ra_syntax::{AstNode, TextRange}; +use ra_syntax::{ + algo::find_node_at_offset, ast, match_ast, AstNode, TextRange, TextUnit, TokenAtOffset, +}; use rustc_hash::FxHashMap; -use crate::{defs::Definition, RootDatabase}; +use crate::{ + defs::{classify_name_ref, Definition}, + RootDatabase, +}; #[derive(Debug, Clone)] pub struct Reference { @@ -164,3 +170,140 @@ impl IntoIterator for SearchScope { self.entries.into_iter() } } + +pub fn find_refs_to_def( + db: &RootDatabase, + def: &Definition, + search_scope: Option, +) -> Vec { + let _p = profile("find_refs_to_def"); + + let search_scope = { + let base = SearchScope::for_def(&def, db); + match search_scope { + None => base, + Some(scope) => base.intersection(&scope), + } + }; + + let name = match def.name(db) { + None => return Vec::new(), + Some(it) => it.to_string(), + }; + + let pat = name.as_str(); + let mut refs = vec![]; + + for (file_id, search_range) in search_scope { + let text = db.file_text(file_id); + let search_range = + search_range.unwrap_or(TextRange::offset_len(0.into(), TextUnit::of_str(&text))); + + let sema = Semantics::new(db); + let tree = Lazy::new(|| sema.parse(file_id).syntax().clone()); + + for (idx, _) in text.match_indices(pat) { + let offset = TextUnit::from_usize(idx); + if !search_range.contains_inclusive(offset) { + // tested_by!(search_filters_by_range); + continue; + } + + let name_ref = + if let Some(name_ref) = find_node_at_offset::(&tree, offset) { + name_ref + } else { + // Handle macro token cases + let token = match tree.token_at_offset(offset) { + TokenAtOffset::None => continue, + TokenAtOffset::Single(t) => t, + TokenAtOffset::Between(_, t) => t, + }; + let expanded = sema.descend_into_macros(token); + match ast::NameRef::cast(expanded.parent()) { + Some(name_ref) => name_ref, + _ => continue, + } + }; + + // FIXME: reuse sb + // See https://github.com/rust-lang/rust/pull/68198#issuecomment-574269098 + + if let Some(d) = classify_name_ref(&sema, &name_ref) { + let d = d.definition(); + if &d == def { + let kind = + if is_record_lit_name_ref(&name_ref) || is_call_expr_name_ref(&name_ref) { + ReferenceKind::StructLiteral + } else { + ReferenceKind::Other + }; + + let file_range = sema.original_range(name_ref.syntax()); + refs.push(Reference { + file_range, + kind, + access: reference_access(&d, &name_ref), + }); + } + } + } + } + refs +} + +fn reference_access(def: &Definition, name_ref: &ast::NameRef) -> Option { + // Only Locals and Fields have accesses for now. + match def { + Definition::Local(_) | Definition::StructField(_) => {} + _ => return None, + }; + + let mode = name_ref.syntax().ancestors().find_map(|node| { + match_ast! { + match (node) { + ast::BinExpr(expr) => { + if expr.op_kind()?.is_assignment() { + // If the variable or field ends on the LHS's end then it's a Write (covers fields and locals). + // FIXME: This is not terribly accurate. + if let Some(lhs) = expr.lhs() { + if lhs.syntax().text_range().end() == name_ref.syntax().text_range().end() { + return Some(ReferenceAccess::Write); + } + } + } + Some(ReferenceAccess::Read) + }, + _ => {None} + } + } + }); + + // Default Locals and Fields to read + mode.or(Some(ReferenceAccess::Read)) +} + +fn is_call_expr_name_ref(name_ref: &ast::NameRef) -> bool { + name_ref + .syntax() + .ancestors() + .find_map(ast::CallExpr::cast) + .and_then(|c| match c.expr()? { + ast::Expr::PathExpr(p) => { + Some(p.path()?.segment()?.name_ref().as_ref() == Some(name_ref)) + } + _ => None, + }) + .unwrap_or(false) +} + +fn is_record_lit_name_ref(name_ref: &ast::NameRef) -> bool { + name_ref + .syntax() + .ancestors() + .find_map(ast::RecordLit::cast) + .and_then(|l| l.path()) + .and_then(|p| p.segment()) + .map(|p| p.name_ref().as_ref() == Some(name_ref)) + .unwrap_or(false) +} -- cgit v1.2.3 From 994000b5ddfd5bb3b7dc7d66aabe02a0f337770f Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Wed, 4 Mar 2020 12:17:41 +0100 Subject: Use method instead of a free function --- crates/ra_ide_db/src/search.rs | 125 +++++++++++++++++++++-------------------- 1 file changed, 64 insertions(+), 61 deletions(-) (limited to 'crates/ra_ide_db/src') diff --git a/crates/ra_ide_db/src/search.rs b/crates/ra_ide_db/src/search.rs index efd43f4c1..23dd278b5 100644 --- a/crates/ra_ide_db/src/search.rs +++ b/crates/ra_ide_db/src/search.rs @@ -171,85 +171,88 @@ impl IntoIterator for SearchScope { } } -pub fn find_refs_to_def( - db: &RootDatabase, - def: &Definition, - search_scope: Option, -) -> Vec { - let _p = profile("find_refs_to_def"); - - let search_scope = { - let base = SearchScope::for_def(&def, db); - match search_scope { - None => base, - Some(scope) => base.intersection(&scope), - } - }; +impl Definition { + pub fn find_usages( + &self, + db: &RootDatabase, + search_scope: Option, + ) -> Vec { + let _p = profile("Definition::find_usages"); + + let search_scope = { + let base = SearchScope::for_def(self, db); + match search_scope { + None => base, + Some(scope) => base.intersection(&scope), + } + }; - let name = match def.name(db) { - None => return Vec::new(), - Some(it) => it.to_string(), - }; + let name = match self.name(db) { + None => return Vec::new(), + Some(it) => it.to_string(), + }; - let pat = name.as_str(); - let mut refs = vec![]; + let pat = name.as_str(); + let mut refs = vec![]; - for (file_id, search_range) in search_scope { - let text = db.file_text(file_id); - let search_range = - search_range.unwrap_or(TextRange::offset_len(0.into(), TextUnit::of_str(&text))); + for (file_id, search_range) in search_scope { + let text = db.file_text(file_id); + let search_range = + search_range.unwrap_or(TextRange::offset_len(0.into(), TextUnit::of_str(&text))); - let sema = Semantics::new(db); - let tree = Lazy::new(|| sema.parse(file_id).syntax().clone()); + let sema = Semantics::new(db); + let tree = Lazy::new(|| sema.parse(file_id).syntax().clone()); - for (idx, _) in text.match_indices(pat) { - let offset = TextUnit::from_usize(idx); - if !search_range.contains_inclusive(offset) { - // tested_by!(search_filters_by_range); - continue; - } + for (idx, _) in text.match_indices(pat) { + let offset = TextUnit::from_usize(idx); + if !search_range.contains_inclusive(offset) { + // tested_by!(search_filters_by_range); + continue; + } - let name_ref = - if let Some(name_ref) = find_node_at_offset::(&tree, offset) { - name_ref - } else { - // Handle macro token cases - let token = match tree.token_at_offset(offset) { - TokenAtOffset::None => continue, - TokenAtOffset::Single(t) => t, - TokenAtOffset::Between(_, t) => t, + let name_ref = + if let Some(name_ref) = find_node_at_offset::(&tree, offset) { + name_ref + } else { + // Handle macro token cases + let token = match tree.token_at_offset(offset) { + TokenAtOffset::None => continue, + TokenAtOffset::Single(t) => t, + TokenAtOffset::Between(_, t) => t, + }; + let expanded = sema.descend_into_macros(token); + match ast::NameRef::cast(expanded.parent()) { + Some(name_ref) => name_ref, + _ => continue, + } }; - let expanded = sema.descend_into_macros(token); - match ast::NameRef::cast(expanded.parent()) { - Some(name_ref) => name_ref, - _ => continue, - } - }; - // FIXME: reuse sb - // See https://github.com/rust-lang/rust/pull/68198#issuecomment-574269098 + // FIXME: reuse sb + // See https://github.com/rust-lang/rust/pull/68198#issuecomment-574269098 - if let Some(d) = classify_name_ref(&sema, &name_ref) { - let d = d.definition(); - if &d == def { - let kind = - if is_record_lit_name_ref(&name_ref) || is_call_expr_name_ref(&name_ref) { + if let Some(d) = classify_name_ref(&sema, &name_ref) { + let d = d.definition(); + if &d == self { + let kind = if is_record_lit_name_ref(&name_ref) + || is_call_expr_name_ref(&name_ref) + { ReferenceKind::StructLiteral } else { ReferenceKind::Other }; - let file_range = sema.original_range(name_ref.syntax()); - refs.push(Reference { - file_range, - kind, - access: reference_access(&d, &name_ref), - }); + let file_range = sema.original_range(name_ref.syntax()); + refs.push(Reference { + file_range, + kind, + access: reference_access(&d, &name_ref), + }); + } } } } + refs } - refs } fn reference_access(def: &Definition, name_ref: &ast::NameRef) -> Option { -- cgit v1.2.3 From 072ec1a8ae7271324a907ea082521226a6f3d1d4 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Wed, 4 Mar 2020 12:20:32 +0100 Subject: Fix tests --- crates/ra_ide_db/src/marks.rs | 1 + crates/ra_ide_db/src/search.rs | 3 ++- 2 files changed, 3 insertions(+), 1 deletion(-) (limited to 'crates/ra_ide_db/src') diff --git a/crates/ra_ide_db/src/marks.rs b/crates/ra_ide_db/src/marks.rs index d088fa257..4f0a22af0 100644 --- a/crates/ra_ide_db/src/marks.rs +++ b/crates/ra_ide_db/src/marks.rs @@ -6,4 +6,5 @@ test_utils::marks![ goto_def_for_fields goto_def_for_record_fields goto_def_for_field_init_shorthand + search_filters_by_range ]; diff --git a/crates/ra_ide_db/src/search.rs b/crates/ra_ide_db/src/search.rs index 23dd278b5..0963ea257 100644 --- a/crates/ra_ide_db/src/search.rs +++ b/crates/ra_ide_db/src/search.rs @@ -12,6 +12,7 @@ use ra_syntax::{ algo::find_node_at_offset, ast, match_ast, AstNode, TextRange, TextUnit, TokenAtOffset, }; use rustc_hash::FxHashMap; +use test_utils::tested_by; use crate::{ defs::{classify_name_ref, Definition}, @@ -206,7 +207,7 @@ impl Definition { for (idx, _) in text.match_indices(pat) { let offset = TextUnit::from_usize(idx); if !search_range.contains_inclusive(offset) { - // tested_by!(search_filters_by_range); + tested_by!(search_filters_by_range; force); continue; } -- cgit v1.2.3 From 98d68fa6beec87020b89d01c060288794dc948f1 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Wed, 4 Mar 2020 12:46:40 +0100 Subject: Cleanup API --- crates/ra_ide_db/src/search.rs | 94 +++++++++++++++++++++--------------------- 1 file changed, 47 insertions(+), 47 deletions(-) (limited to 'crates/ra_ide_db/src') diff --git a/crates/ra_ide_db/src/search.rs b/crates/ra_ide_db/src/search.rs index 0963ea257..7bd99d4cc 100644 --- a/crates/ra_ide_db/src/search.rs +++ b/crates/ra_ide_db/src/search.rs @@ -55,16 +55,58 @@ impl SearchScope { SearchScope::new(std::iter::once((file, None)).collect()) } - pub fn for_def(def: &Definition, db: &RootDatabase) -> SearchScope { + pub fn intersection(&self, other: &SearchScope) -> SearchScope { + let (mut small, mut large) = (&self.entries, &other.entries); + if small.len() > large.len() { + mem::swap(&mut small, &mut large) + } + + let res = small + .iter() + .filter_map(|(file_id, r1)| { + let r2 = large.get(file_id)?; + let r = intersect_ranges(*r1, *r2)?; + Some((*file_id, r)) + }) + .collect(); + + return SearchScope::new(res); + + fn intersect_ranges( + r1: Option, + r2: Option, + ) -> Option> { + match (r1, r2) { + (None, r) | (r, None) => Some(r), + (Some(r1), Some(r2)) => { + let r = r1.intersection(&r2)?; + Some(Some(r)) + } + } + } + } +} + +impl IntoIterator for SearchScope { + type Item = (FileId, Option); + type IntoIter = std::collections::hash_map::IntoIter>; + + fn into_iter(self) -> Self::IntoIter { + self.entries.into_iter() + } +} + +impl Definition { + fn search_scope(&self, db: &RootDatabase) -> SearchScope { let _p = profile("search_scope"); - let module = match def.module(db) { + let module = match self.module(db) { Some(it) => it, None => return SearchScope::empty(), }; let module_src = module.definition_source(db); let file_id = module_src.file_id.original_file(db); - if let Definition::Local(var) = def { + if let Definition::Local(var) = self { let range = match var.parent(db) { DefWithBody::Function(f) => f.source(db).value.syntax().text_range(), DefWithBody::Const(c) => c.source(db).value.syntax().text_range(), @@ -75,7 +117,7 @@ impl SearchScope { return SearchScope::new(res); } - let vis = def.visibility(db).as_ref().map(|v| v.syntax().to_string()).unwrap_or_default(); + let vis = self.visibility(db).as_ref().map(|v| v.syntax().to_string()).unwrap_or_default(); if vis.as_str() == "pub(super)" { if let Some(parent_module) = module.parent(db) { @@ -131,48 +173,6 @@ impl SearchScope { SearchScope::new(res) } - pub fn intersection(&self, other: &SearchScope) -> SearchScope { - let (mut small, mut large) = (&self.entries, &other.entries); - if small.len() > large.len() { - mem::swap(&mut small, &mut large) - } - - let res = small - .iter() - .filter_map(|(file_id, r1)| { - let r2 = large.get(file_id)?; - let r = intersect_ranges(*r1, *r2)?; - Some((*file_id, r)) - }) - .collect(); - - return SearchScope::new(res); - - fn intersect_ranges( - r1: Option, - r2: Option, - ) -> Option> { - match (r1, r2) { - (None, r) | (r, None) => Some(r), - (Some(r1), Some(r2)) => { - let r = r1.intersection(&r2)?; - Some(Some(r)) - } - } - } - } -} - -impl IntoIterator for SearchScope { - type Item = (FileId, Option); - type IntoIter = std::collections::hash_map::IntoIter>; - - fn into_iter(self) -> Self::IntoIter { - self.entries.into_iter() - } -} - -impl Definition { pub fn find_usages( &self, db: &RootDatabase, @@ -181,7 +181,7 @@ impl Definition { let _p = profile("Definition::find_usages"); let search_scope = { - let base = SearchScope::for_def(self, db); + let base = self.search_scope(db); match search_scope { None => base, Some(scope) => base.intersection(&scope), -- cgit v1.2.3 From 4f50a3718762c9272b1929162ce62415a75eec8f Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Wed, 4 Mar 2020 12:48:50 +0100 Subject: Fix docs --- crates/ra_ide_db/src/search.rs | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) (limited to 'crates/ra_ide_db/src') diff --git a/crates/ra_ide_db/src/search.rs b/crates/ra_ide_db/src/search.rs index 7bd99d4cc..6f198df04 100644 --- a/crates/ra_ide_db/src/search.rs +++ b/crates/ra_ide_db/src/search.rs @@ -1,7 +1,9 @@ -//! Generally, `search_scope` returns files that might contain references for the element. -//! For `pub(crate)` things it's a crate, for `pub` things it's a crate and dependant crates. -//! In some cases, the location of the references is known to within a `TextRange`, -//! e.g. for things like local variables. +//! Implementation of find-usages functionality. +//! +//! It is based on the standard ide trick: first, we run a fast text search to +//! get a super-set of matches. Then, we we confirm each match using precise +//! name resolution. + use std::mem; use hir::{DefWithBody, HasSource, ModuleSource, Semantics}; @@ -38,6 +40,10 @@ pub enum ReferenceAccess { Write, } +/// Generally, `search_scope` returns files that might contain references for the element. +/// For `pub(crate)` things it's a crate, for `pub` things it's a crate and dependant crates. +/// In some cases, the location of the references is known to within a `TextRange`, +/// e.g. for things like local variables. pub struct SearchScope { entries: FxHashMap>, } -- cgit v1.2.3