aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir_def
diff options
context:
space:
mode:
authorJonas Schievink <[email protected]>2020-06-04 18:30:29 +0100
committerJonas Schievink <[email protected]>2020-06-04 18:33:01 +0100
commit3c496f7fa7afe78102ea2c7ee5f7e006a66629d4 (patch)
tree5c88e48492b514d14b8fa183a4474c2aaf49d7ec /crates/ra_hir_def
parentd08c63cb9e3574fa97374a8529136814530bf416 (diff)
Use `ImportMap` in `find_path`, remove old queries
Diffstat (limited to 'crates/ra_hir_def')
-rw-r--r--crates/ra_hir_def/src/db.rs16
-rw-r--r--crates/ra_hir_def/src/find_path.rs199
-rw-r--r--crates/ra_hir_def/src/item_scope.rs22
3 files changed, 140 insertions, 97 deletions
diff --git a/crates/ra_hir_def/src/db.rs b/crates/ra_hir_def/src/db.rs
index a23d65371..10cc26480 100644
--- a/crates/ra_hir_def/src/db.rs
+++ b/crates/ra_hir_def/src/db.rs
@@ -1,7 +1,7 @@
1//! Defines database & queries for name resolution. 1//! Defines database & queries for name resolution.
2use std::sync::Arc; 2use std::sync::Arc;
3 3
4use hir_expand::{db::AstDatabase, name::Name, HirFileId}; 4use hir_expand::{db::AstDatabase, HirFileId};
5use ra_db::{salsa, CrateId, SourceDatabase, Upcast}; 5use ra_db::{salsa, CrateId, SourceDatabase, Upcast};
6use ra_prof::profile; 6use ra_prof::profile;
7use ra_syntax::SmolStr; 7use ra_syntax::SmolStr;
@@ -12,14 +12,10 @@ use crate::{
12 body::{scope::ExprScopes, Body, BodySourceMap}, 12 body::{scope::ExprScopes, Body, BodySourceMap},
13 data::{ConstData, FunctionData, ImplData, StaticData, TraitData, TypeAliasData}, 13 data::{ConstData, FunctionData, ImplData, StaticData, TraitData, TypeAliasData},
14 docs::Documentation, 14 docs::Documentation,
15 find_path,
16 generics::GenericParams, 15 generics::GenericParams,
17 import_map::ImportMap, 16 import_map::ImportMap,
18 item_scope::ItemInNs,
19 lang_item::{LangItemTarget, LangItems}, 17 lang_item::{LangItemTarget, LangItems},
20 nameres::{raw::RawItems, CrateDefMap}, 18 nameres::{raw::RawItems, CrateDefMap},
21 path::ModPath,
22 visibility::Visibility,
23 AttrDefId, ConstId, ConstLoc, DefWithBodyId, EnumId, EnumLoc, FunctionId, FunctionLoc, 19 AttrDefId, ConstId, ConstLoc, DefWithBodyId, EnumId, EnumLoc, FunctionId, FunctionLoc,
24 GenericDefId, ImplId, ImplLoc, ModuleId, StaticId, StaticLoc, StructId, StructLoc, TraitId, 20 GenericDefId, ImplId, ImplLoc, ModuleId, StaticId, StaticLoc, StructId, StructLoc, TraitId,
25 TraitLoc, TypeAliasId, TypeAliasLoc, UnionId, UnionLoc, 21 TraitLoc, TypeAliasId, TypeAliasLoc, UnionId, UnionLoc,
@@ -114,16 +110,6 @@ pub trait DefDatabase: InternDatabase + AstDatabase + Upcast<dyn AstDatabase> {
114 #[salsa::invoke(Documentation::documentation_query)] 110 #[salsa::invoke(Documentation::documentation_query)]
115 fn documentation(&self, def: AttrDefId) -> Option<Documentation>; 111 fn documentation(&self, def: AttrDefId) -> Option<Documentation>;
116 112
117 #[salsa::invoke(find_path::importable_locations_of_query)]
118 fn importable_locations_of(
119 &self,
120 item: ItemInNs,
121 krate: CrateId,
122 ) -> Arc<[(ModuleId, Name, Visibility)]>;
123
124 #[salsa::invoke(find_path::find_path_inner_query)]
125 fn find_path_inner(&self, item: ItemInNs, from: ModuleId, max_len: usize) -> Option<ModPath>;
126
127 #[salsa::invoke(ImportMap::import_map_query)] 113 #[salsa::invoke(ImportMap::import_map_query)]
128 fn import_map(&self, krate: CrateId) -> Arc<ImportMap>; 114 fn import_map(&self, krate: CrateId) -> Arc<ImportMap>;
129} 115}
diff --git a/crates/ra_hir_def/src/find_path.rs b/crates/ra_hir_def/src/find_path.rs
index 088e8dd32..79f4afab6 100644
--- a/crates/ra_hir_def/src/find_path.rs
+++ b/crates/ra_hir_def/src/find_path.rs
@@ -1,7 +1,5 @@
1//! An algorithm to find a path to refer to a certain item. 1//! An algorithm to find a path to refer to a certain item.
2 2
3use std::sync::Arc;
4
5use hir_expand::name::{known, AsName, Name}; 3use hir_expand::name::{known, AsName, Name};
6use ra_prof::profile; 4use ra_prof::profile;
7use test_utils::mark; 5use test_utils::mark;
@@ -11,8 +9,9 @@ use crate::{
11 item_scope::ItemInNs, 9 item_scope::ItemInNs,
12 path::{ModPath, PathKind}, 10 path::{ModPath, PathKind},
13 visibility::Visibility, 11 visibility::Visibility,
14 CrateId, ModuleDefId, ModuleId, 12 ModuleDefId, ModuleId,
15}; 13};
14use rustc_hash::FxHashSet;
16 15
17// FIXME: handle local items 16// FIXME: handle local items
18 17
@@ -20,7 +19,7 @@ use crate::{
20/// *from where* you're referring to the item, hence the `from` parameter. 19/// *from where* you're referring to the item, hence the `from` parameter.
21pub fn find_path(db: &dyn DefDatabase, item: ItemInNs, from: ModuleId) -> Option<ModPath> { 20pub fn find_path(db: &dyn DefDatabase, item: ItemInNs, from: ModuleId) -> Option<ModPath> {
22 let _p = profile("find_path"); 21 let _p = profile("find_path");
23 db.find_path_inner(item, from, MAX_PATH_LEN) 22 find_path_inner(db, item, from, MAX_PATH_LEN)
24} 23}
25 24
26const MAX_PATH_LEN: usize = 15; 25const MAX_PATH_LEN: usize = 15;
@@ -38,7 +37,7 @@ impl ModPath {
38 } 37 }
39} 38}
40 39
41pub(crate) fn find_path_inner_query( 40pub(crate) fn find_path_inner(
42 db: &dyn DefDatabase, 41 db: &dyn DefDatabase,
43 item: ItemInNs, 42 item: ItemInNs,
44 from: ModuleId, 43 from: ModuleId,
@@ -122,31 +121,61 @@ pub(crate) fn find_path_inner_query(
122 } 121 }
123 122
124 // - otherwise, look for modules containing (reexporting) it and import it from one of those 123 // - otherwise, look for modules containing (reexporting) it and import it from one of those
124
125 let crate_root = ModuleId { local_id: def_map.root, krate: from.krate }; 125 let crate_root = ModuleId { local_id: def_map.root, krate: from.krate };
126 let crate_attrs = db.attrs(crate_root.into()); 126 let crate_attrs = db.attrs(crate_root.into());
127 let prefer_no_std = crate_attrs.by_key("no_std").exists(); 127 let prefer_no_std = crate_attrs.by_key("no_std").exists();
128 let importable_locations = find_importable_locations(db, item, from);
129 let mut best_path = None; 128 let mut best_path = None;
130 let mut best_path_len = max_len; 129 let mut best_path_len = max_len;
131 for (module_id, name) in importable_locations {
132 let mut path = match db.find_path_inner(
133 ItemInNs::Types(ModuleDefId::ModuleId(module_id)),
134 from,
135 best_path_len - 1,
136 ) {
137 None => continue,
138 Some(path) => path,
139 };
140 path.segments.push(name);
141 130
142 let new_path = if let Some(best_path) = best_path { 131 if item.defining_crate(db) == Some(from.krate) {
143 select_best_path(best_path, path, prefer_no_std) 132 // Item was defined in the same crate that wants to import it. It cannot be found in any
144 } else { 133 // dependency in this case.
145 path 134
146 }; 135 let local_imports = find_local_import_locations(db, item, from);
147 best_path_len = new_path.len(); 136 for (module_id, name) in local_imports {
148 best_path = Some(new_path); 137 if let Some(mut path) = find_path_inner(
138 db,
139 ItemInNs::Types(ModuleDefId::ModuleId(module_id)),
140 from,
141 best_path_len - 1,
142 ) {
143 path.segments.push(name);
144
145 let new_path = if let Some(best_path) = best_path {
146 select_best_path(best_path, path, prefer_no_std)
147 } else {
148 path
149 };
150 best_path_len = new_path.len();
151 best_path = Some(new_path);
152 }
153 }
154 } else {
155 // Item was defined in some upstream crate. This means that it must be exported from one,
156 // too (unless we can't name it at all). It could *also* be (re)exported by the same crate
157 // that wants to import it here, but we always prefer to use the external path here.
158
159 let crate_graph = db.crate_graph();
160 let extern_paths = crate_graph[from.krate].dependencies.iter().filter_map(|dep| {
161 let import_map = db.import_map(dep.crate_id);
162 import_map.path_of(item).map(|modpath| {
163 let mut modpath = modpath.clone();
164 modpath.segments.insert(0, dep.as_name());
165 modpath
166 })
167 });
168
169 for path in extern_paths {
170 let new_path = if let Some(best_path) = best_path {
171 select_best_path(best_path, path, prefer_no_std)
172 } else {
173 path
174 };
175 best_path = Some(new_path);
176 }
149 } 177 }
178
150 best_path 179 best_path
151} 180}
152 181
@@ -174,77 +203,86 @@ fn select_best_path(old_path: ModPath, new_path: ModPath, prefer_no_std: bool) -
174 } 203 }
175} 204}
176 205
177fn find_importable_locations( 206/// Finds locations in `from.krate` from which `item` can be imported by `from`.
207fn find_local_import_locations(
178 db: &dyn DefDatabase, 208 db: &dyn DefDatabase,
179 item: ItemInNs, 209 item: ItemInNs,
180 from: ModuleId, 210 from: ModuleId,
181) -> Vec<(ModuleId, Name)> { 211) -> Vec<(ModuleId, Name)> {
182 let crate_graph = db.crate_graph(); 212 let _p = profile("find_local_import_locations");
183 let mut result = Vec::new(); 213
184 214 // `from` can import anything below `from` with visibility of at least `from`, and anything
185 // We only look in the crate from which we are importing, and the direct 215 // above `from` with any visibility. That means we do not need to descend into private siblings
186 // dependencies. We cannot refer to names from transitive dependencies 216 // of `from` (and similar).
187 // directly (only through reexports in direct dependencies). 217
188 218 let def_map = db.crate_def_map(from.krate);
189 // For the crate from which we're importing, we have to check whether any 219
190 // module visible to `from` exports the item we're looking for. 220 // Compute the initial worklist. We start with all direct child modules of `from` as well as all
191 // For dependencies of the crate only `pub` items reachable through `pub` 221 // of its (recursive) parent modules.
192 // modules from the crate root are relevant. For that we precompute an 222 let data = &def_map.modules[from.local_id];
193 // import map that tells us the shortest path to any importable item with a 223 let mut worklist = data
194 // single lookup. 224 .children
195 for krate in Some(from.krate) 225 .values()
196 .into_iter() 226 .map(|child| ModuleId { krate: from.krate, local_id: *child })
197 .chain(crate_graph[from.krate].dependencies.iter().map(|dep| dep.crate_id)) 227 .collect::<Vec<_>>();
198 { 228 let mut parent = data.parent;
199 result.extend( 229 while let Some(p) = parent {
200 db.importable_locations_of(item, krate) 230 worklist.push(ModuleId { krate: from.krate, local_id: p });
201 .iter() 231 parent = def_map.modules[p].parent;
202 .filter(|(_, _, vis)| vis.is_visible_from(db, from)) 232 }
203 .map(|(m, n, _)| (*m, n.clone())), 233
204 ); 234 let mut seen: FxHashSet<_> = FxHashSet::default();
205 } 235
206 result 236 let mut locations = Vec::new();
207} 237 while let Some(module) = worklist.pop() {
238 if !seen.insert(module) {
239 continue; // already processed this module
240 }
241
242 let ext_def_map;
243 let data = if module.krate == from.krate {
244 &def_map[module.local_id]
245 } else {
246 // The crate might reexport a module defined in another crate.
247 ext_def_map = db.crate_def_map(module.krate);
248 &ext_def_map[module.local_id]
249 };
208 250
209/// Collects all locations from which we might import the item in a particular
210/// crate. These include the original definition of the item, and any
211/// non-private `use`s.
212///
213/// Note that the crate doesn't need to be the one in which the item is defined;
214/// it might be re-exported in other crates.
215pub(crate) fn importable_locations_of_query(
216 db: &dyn DefDatabase,
217 item: ItemInNs,
218 krate: CrateId,
219) -> Arc<[(ModuleId, Name, Visibility)]> {
220 let _p = profile("importable_locations_of_query");
221 let def_map = db.crate_def_map(krate);
222 let mut result = Vec::new();
223 for (local_id, data) in def_map.modules.iter() {
224 if let Some((name, vis)) = data.scope.name_of(item) { 251 if let Some((name, vis)) = data.scope.name_of(item) {
225 let is_private = if let Visibility::Module(private_to) = vis { 252 if vis.is_visible_from(db, from) {
226 private_to.local_id == local_id 253 let is_private = if let Visibility::Module(private_to) = vis {
227 } else { 254 private_to.local_id == module.local_id
228 false 255 } else {
229 }; 256 false
230 let is_original_def = if let Some(module_def_id) = item.as_module_def_id() { 257 };
231 data.scope.declarations().any(|it| it == module_def_id) 258 let is_original_def = if let Some(module_def_id) = item.as_module_def_id() {
232 } else { 259 data.scope.declarations().any(|it| it == module_def_id)
233 false 260 } else {
234 }; 261 false
235 if is_private && !is_original_def { 262 };
263
236 // Ignore private imports. these could be used if we are 264 // Ignore private imports. these could be used if we are
237 // in a submodule of this module, but that's usually not 265 // in a submodule of this module, but that's usually not
238 // what the user wants; and if this module can import 266 // what the user wants; and if this module can import
239 // the item and we're a submodule of it, so can we. 267 // the item and we're a submodule of it, so can we.
240 // Also this keeps the cached data smaller. 268 // Also this keeps the cached data smaller.
241 continue; 269 if !is_private || is_original_def {
270 locations.push((module, name.clone()));
271 }
272 }
273 }
274
275 // Descend into all modules visible from `from`.
276 for (_, per_ns) in data.scope.entries() {
277 if let Some((ModuleDefId::ModuleId(module), vis)) = per_ns.take_types_vis() {
278 if vis.is_visible_from(db, from) {
279 worklist.push(module);
280 }
242 } 281 }
243 result.push((ModuleId { krate, local_id }, name.clone(), vis));
244 } 282 }
245 } 283 }
246 284
247 Arc::from(result) 285 locations
248} 286}
249 287
250#[cfg(test)] 288#[cfg(test)]
@@ -382,6 +420,7 @@ mod tests {
382 420
383 #[test] 421 #[test]
384 fn different_crate_renamed() { 422 fn different_crate_renamed() {
423 // Even if a local path exists, if the item is defined externally, prefer an external path.
385 let code = r#" 424 let code = r#"
386 //- /main.rs crate:main deps:std 425 //- /main.rs crate:main deps:std
387 extern crate std as std_renamed; 426 extern crate std as std_renamed;
@@ -389,7 +428,7 @@ mod tests {
389 //- /std.rs crate:std 428 //- /std.rs crate:std
390 pub struct S; 429 pub struct S;
391 "#; 430 "#;
392 check_found_path(code, "std_renamed::S"); 431 check_found_path(code, "std::S");
393 } 432 }
394 433
395 #[test] 434 #[test]
diff --git a/crates/ra_hir_def/src/item_scope.rs b/crates/ra_hir_def/src/item_scope.rs
index fc15948ad..ede1aa045 100644
--- a/crates/ra_hir_def/src/item_scope.rs
+++ b/crates/ra_hir_def/src/item_scope.rs
@@ -6,9 +6,10 @@ use once_cell::sync::Lazy;
6use rustc_hash::FxHashMap; 6use rustc_hash::FxHashMap;
7 7
8use crate::{ 8use crate::{
9 per_ns::PerNs, visibility::Visibility, AdtId, BuiltinType, ImplId, MacroDefId, ModuleDefId, 9 db::DefDatabase, per_ns::PerNs, visibility::Visibility, AdtId, BuiltinType, HasModule, ImplId,
10 TraitId, 10 Lookup, MacroDefId, ModuleDefId, TraitId,
11}; 11};
12use ra_db::CrateId;
12 13
13#[derive(Debug, Default, PartialEq, Eq)] 14#[derive(Debug, Default, PartialEq, Eq)]
14pub struct ItemScope { 15pub struct ItemScope {
@@ -203,4 +204,21 @@ impl ItemInNs {
203 ItemInNs::Macros(_) => None, 204 ItemInNs::Macros(_) => None,
204 } 205 }
205 } 206 }
207
208 pub fn defining_crate(&self, db: &dyn DefDatabase) -> Option<CrateId> {
209 Some(match self {
210 ItemInNs::Types(did) | ItemInNs::Values(did) => match did {
211 ModuleDefId::ModuleId(id) => id.krate,
212 ModuleDefId::FunctionId(id) => id.lookup(db).module(db).krate,
213 ModuleDefId::AdtId(id) => id.module(db).krate,
214 ModuleDefId::EnumVariantId(id) => id.parent.lookup(db).container.module(db).krate,
215 ModuleDefId::ConstId(id) => id.lookup(db).container.module(db).krate,
216 ModuleDefId::StaticId(id) => id.lookup(db).container.module(db).krate,
217 ModuleDefId::TraitId(id) => id.lookup(db).container.module(db).krate,
218 ModuleDefId::TypeAliasId(id) => id.lookup(db).module(db).krate,
219 ModuleDefId::BuiltinType(_) => return None,
220 },
221 ItemInNs::Macros(id) => return id.krate,
222 })
223 }
206} 224}