diff options
-rw-r--r-- | crates/ra_hir_def/src/db.rs | 16 | ||||
-rw-r--r-- | crates/ra_hir_def/src/find_path.rs | 199 | ||||
-rw-r--r-- | crates/ra_hir_def/src/item_scope.rs | 22 |
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. |
2 | use std::sync::Arc; | 2 | use std::sync::Arc; |
3 | 3 | ||
4 | use hir_expand::{db::AstDatabase, name::Name, HirFileId}; | 4 | use hir_expand::{db::AstDatabase, HirFileId}; |
5 | use ra_db::{salsa, CrateId, SourceDatabase, Upcast}; | 5 | use ra_db::{salsa, CrateId, SourceDatabase, Upcast}; |
6 | use ra_prof::profile; | 6 | use ra_prof::profile; |
7 | use ra_syntax::SmolStr; | 7 | use 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 | ||
3 | use std::sync::Arc; | ||
4 | |||
5 | use hir_expand::name::{known, AsName, Name}; | 3 | use hir_expand::name::{known, AsName, Name}; |
6 | use ra_prof::profile; | 4 | use ra_prof::profile; |
7 | use test_utils::mark; | 5 | use 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 | }; |
14 | use 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. |
21 | pub fn find_path(db: &dyn DefDatabase, item: ItemInNs, from: ModuleId) -> Option<ModPath> { | 20 | pub 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 | ||
26 | const MAX_PATH_LEN: usize = 15; | 25 | const MAX_PATH_LEN: usize = 15; |
@@ -38,7 +37,7 @@ impl ModPath { | |||
38 | } | 37 | } |
39 | } | 38 | } |
40 | 39 | ||
41 | pub(crate) fn find_path_inner_query( | 40 | pub(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 | ||
177 | fn find_importable_locations( | 206 | /// Finds locations in `from.krate` from which `item` can be imported by `from`. |
207 | fn 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. | ||
215 | pub(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; | |||
6 | use rustc_hash::FxHashMap; | 6 | use rustc_hash::FxHashMap; |
7 | 7 | ||
8 | use crate::{ | 8 | use 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 | }; |
12 | use ra_db::CrateId; | ||
12 | 13 | ||
13 | #[derive(Debug, Default, PartialEq, Eq)] | 14 | #[derive(Debug, Default, PartialEq, Eq)] |
14 | pub struct ItemScope { | 15 | pub 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 | } |