diff options
author | Jonas Schievink <[email protected]> | 2020-06-04 18:30:29 +0100 |
---|---|---|
committer | Jonas Schievink <[email protected]> | 2020-06-04 18:33:01 +0100 |
commit | 3c496f7fa7afe78102ea2c7ee5f7e006a66629d4 (patch) | |
tree | 5c88e48492b514d14b8fa183a4474c2aaf49d7ec /crates/ra_hir_def/src/find_path.rs | |
parent | d08c63cb9e3574fa97374a8529136814530bf416 (diff) |
Use `ImportMap` in `find_path`, remove old queries
Diffstat (limited to 'crates/ra_hir_def/src/find_path.rs')
-rw-r--r-- | crates/ra_hir_def/src/find_path.rs | 199 |
1 files changed, 119 insertions, 80 deletions
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] |