diff options
Diffstat (limited to 'crates/ra_hir_def/src/find_path.rs')
-rw-r--r-- | crates/ra_hir_def/src/find_path.rs | 455 |
1 files changed, 455 insertions, 0 deletions
diff --git a/crates/ra_hir_def/src/find_path.rs b/crates/ra_hir_def/src/find_path.rs new file mode 100644 index 000000000..f7dc8acb7 --- /dev/null +++ b/crates/ra_hir_def/src/find_path.rs | |||
@@ -0,0 +1,455 @@ | |||
1 | //! An algorithm to find a path to refer to a certain item. | ||
2 | |||
3 | use crate::{ | ||
4 | db::DefDatabase, | ||
5 | item_scope::ItemInNs, | ||
6 | path::{ModPath, PathKind}, | ||
7 | visibility::Visibility, | ||
8 | CrateId, ModuleDefId, ModuleId, | ||
9 | }; | ||
10 | use hir_expand::name::Name; | ||
11 | |||
12 | const MAX_PATH_LEN: usize = 15; | ||
13 | |||
14 | // FIXME: handle local items | ||
15 | |||
16 | /// Find a path that can be used to refer to a certain item. This can depend on | ||
17 | /// *from where* you're referring to the item, hence the `from` parameter. | ||
18 | pub fn find_path(db: &impl DefDatabase, item: ItemInNs, from: ModuleId) -> Option<ModPath> { | ||
19 | find_path_inner(db, item, from, MAX_PATH_LEN) | ||
20 | } | ||
21 | |||
22 | fn find_path_inner( | ||
23 | db: &impl DefDatabase, | ||
24 | item: ItemInNs, | ||
25 | from: ModuleId, | ||
26 | max_len: usize, | ||
27 | ) -> Option<ModPath> { | ||
28 | if max_len == 0 { | ||
29 | return None; | ||
30 | } | ||
31 | |||
32 | // Base cases: | ||
33 | |||
34 | // - if the item is already in scope, return the name under which it is | ||
35 | let def_map = db.crate_def_map(from.krate); | ||
36 | let from_scope: &crate::item_scope::ItemScope = &def_map.modules[from.local_id].scope; | ||
37 | if let Some((name, _)) = from_scope.name_of(item) { | ||
38 | return Some(ModPath::from_simple_segments(PathKind::Plain, vec![name.clone()])); | ||
39 | } | ||
40 | |||
41 | // - if the item is the crate root, return `crate` | ||
42 | if item | ||
43 | == ItemInNs::Types(ModuleDefId::ModuleId(ModuleId { | ||
44 | krate: from.krate, | ||
45 | local_id: def_map.root, | ||
46 | })) | ||
47 | { | ||
48 | return Some(ModPath::from_simple_segments(PathKind::Crate, Vec::new())); | ||
49 | } | ||
50 | |||
51 | // - if the item is the module we're in, use `self` | ||
52 | if item == ItemInNs::Types(from.into()) { | ||
53 | return Some(ModPath::from_simple_segments(PathKind::Super(0), Vec::new())); | ||
54 | } | ||
55 | |||
56 | // - if the item is the parent module, use `super` (this is not used recursively, since `super::super` is ugly) | ||
57 | if let Some(parent_id) = def_map.modules[from.local_id].parent { | ||
58 | if item | ||
59 | == ItemInNs::Types(ModuleDefId::ModuleId(ModuleId { | ||
60 | krate: from.krate, | ||
61 | local_id: parent_id, | ||
62 | })) | ||
63 | { | ||
64 | return Some(ModPath::from_simple_segments(PathKind::Super(1), Vec::new())); | ||
65 | } | ||
66 | } | ||
67 | |||
68 | // - if the item is the crate root of a dependency crate, return the name from the extern prelude | ||
69 | for (name, def_id) in &def_map.extern_prelude { | ||
70 | if item == ItemInNs::Types(*def_id) { | ||
71 | return Some(ModPath::from_simple_segments(PathKind::Plain, vec![name.clone()])); | ||
72 | } | ||
73 | } | ||
74 | |||
75 | // - if the item is in the prelude, return the name from there | ||
76 | if let Some(prelude_module) = def_map.prelude { | ||
77 | let prelude_def_map = db.crate_def_map(prelude_module.krate); | ||
78 | let prelude_scope: &crate::item_scope::ItemScope = | ||
79 | &prelude_def_map.modules[prelude_module.local_id].scope; | ||
80 | if let Some((name, vis)) = prelude_scope.name_of(item) { | ||
81 | if vis.is_visible_from(db, from) { | ||
82 | return Some(ModPath::from_simple_segments(PathKind::Plain, vec![name.clone()])); | ||
83 | } | ||
84 | } | ||
85 | } | ||
86 | |||
87 | // Recursive case: | ||
88 | // - if the item is an enum variant, refer to it via the enum | ||
89 | if let Some(ModuleDefId::EnumVariantId(variant)) = item.as_module_def_id() { | ||
90 | if let Some(mut path) = find_path(db, ItemInNs::Types(variant.parent.into()), from) { | ||
91 | let data = db.enum_data(variant.parent); | ||
92 | path.segments.push(data.variants[variant.local_id].name.clone()); | ||
93 | return Some(path); | ||
94 | } | ||
95 | // If this doesn't work, it seems we have no way of referring to the | ||
96 | // enum; that's very weird, but there might still be a reexport of the | ||
97 | // variant somewhere | ||
98 | } | ||
99 | |||
100 | // - otherwise, look for modules containing (reexporting) it and import it from one of those | ||
101 | let importable_locations = find_importable_locations(db, item, from); | ||
102 | let mut best_path = None; | ||
103 | let mut best_path_len = max_len; | ||
104 | for (module_id, name) in importable_locations { | ||
105 | let mut path = match find_path_inner( | ||
106 | db, | ||
107 | ItemInNs::Types(ModuleDefId::ModuleId(module_id)), | ||
108 | from, | ||
109 | best_path_len - 1, | ||
110 | ) { | ||
111 | None => continue, | ||
112 | Some(path) => path, | ||
113 | }; | ||
114 | path.segments.push(name); | ||
115 | if path_len(&path) < best_path_len { | ||
116 | best_path_len = path_len(&path); | ||
117 | best_path = Some(path); | ||
118 | } | ||
119 | } | ||
120 | best_path | ||
121 | } | ||
122 | |||
123 | fn path_len(path: &ModPath) -> usize { | ||
124 | path.segments.len() | ||
125 | + match path.kind { | ||
126 | PathKind::Plain => 0, | ||
127 | PathKind::Super(i) => i as usize, | ||
128 | PathKind::Crate => 1, | ||
129 | PathKind::Abs => 0, | ||
130 | PathKind::DollarCrate(_) => 1, | ||
131 | } | ||
132 | } | ||
133 | |||
134 | fn find_importable_locations( | ||
135 | db: &impl DefDatabase, | ||
136 | item: ItemInNs, | ||
137 | from: ModuleId, | ||
138 | ) -> Vec<(ModuleId, Name)> { | ||
139 | let crate_graph = db.crate_graph(); | ||
140 | let mut result = Vec::new(); | ||
141 | // We only look in the crate from which we are importing, and the direct | ||
142 | // dependencies. We cannot refer to names from transitive dependencies | ||
143 | // directly (only through reexports in direct dependencies). | ||
144 | for krate in Some(from.krate) | ||
145 | .into_iter() | ||
146 | .chain(crate_graph.dependencies(from.krate).map(|dep| dep.crate_id)) | ||
147 | { | ||
148 | result.extend( | ||
149 | importable_locations_in_crate(db, item, krate) | ||
150 | .iter() | ||
151 | .filter(|(_, _, vis)| vis.is_visible_from(db, from)) | ||
152 | .map(|(m, n, _)| (*m, n.clone())), | ||
153 | ); | ||
154 | } | ||
155 | result | ||
156 | } | ||
157 | |||
158 | /// Collects all locations from which we might import the item in a particular | ||
159 | /// crate. These include the original definition of the item, and any | ||
160 | /// non-private `use`s. | ||
161 | /// | ||
162 | /// Note that the crate doesn't need to be the one in which the item is defined; | ||
163 | /// it might be re-exported in other crates. | ||
164 | fn importable_locations_in_crate( | ||
165 | db: &impl DefDatabase, | ||
166 | item: ItemInNs, | ||
167 | krate: CrateId, | ||
168 | ) -> Vec<(ModuleId, Name, Visibility)> { | ||
169 | let def_map = db.crate_def_map(krate); | ||
170 | let mut result = Vec::new(); | ||
171 | for (local_id, data) in def_map.modules.iter() { | ||
172 | if let Some((name, vis)) = data.scope.name_of(item) { | ||
173 | let is_private = if let Visibility::Module(private_to) = vis { | ||
174 | private_to.local_id == local_id | ||
175 | } else { | ||
176 | false | ||
177 | }; | ||
178 | let is_original_def = if let Some(module_def_id) = item.as_module_def_id() { | ||
179 | data.scope.declarations().any(|it| it == module_def_id) | ||
180 | } else { | ||
181 | false | ||
182 | }; | ||
183 | if is_private && !is_original_def { | ||
184 | // Ignore private imports. these could be used if we are | ||
185 | // in a submodule of this module, but that's usually not | ||
186 | // what the user wants; and if this module can import | ||
187 | // the item and we're a submodule of it, so can we. | ||
188 | // Also this keeps the cached data smaller. | ||
189 | continue; | ||
190 | } | ||
191 | result.push((ModuleId { krate, local_id }, name.clone(), vis)); | ||
192 | } | ||
193 | } | ||
194 | result | ||
195 | } | ||
196 | |||
197 | #[cfg(test)] | ||
198 | mod tests { | ||
199 | use super::*; | ||
200 | use crate::test_db::TestDB; | ||
201 | use hir_expand::hygiene::Hygiene; | ||
202 | use ra_db::fixture::WithFixture; | ||
203 | use ra_syntax::ast::AstNode; | ||
204 | |||
205 | /// `code` needs to contain a cursor marker; checks that `find_path` for the | ||
206 | /// item the `path` refers to returns that same path when called from the | ||
207 | /// module the cursor is in. | ||
208 | fn check_found_path(code: &str, path: &str) { | ||
209 | let (db, pos) = TestDB::with_position(code); | ||
210 | let module = db.module_for_file(pos.file_id); | ||
211 | let parsed_path_file = ra_syntax::SourceFile::parse(&format!("use {};", path)); | ||
212 | let ast_path = parsed_path_file | ||
213 | .syntax_node() | ||
214 | .descendants() | ||
215 | .find_map(ra_syntax::ast::Path::cast) | ||
216 | .unwrap(); | ||
217 | let mod_path = ModPath::from_src(ast_path, &Hygiene::new_unhygienic()).unwrap(); | ||
218 | |||
219 | let crate_def_map = db.crate_def_map(module.krate); | ||
220 | let resolved = crate_def_map | ||
221 | .resolve_path( | ||
222 | &db, | ||
223 | module.local_id, | ||
224 | &mod_path, | ||
225 | crate::item_scope::BuiltinShadowMode::Module, | ||
226 | ) | ||
227 | .0 | ||
228 | .take_types() | ||
229 | .unwrap(); | ||
230 | |||
231 | let found_path = find_path(&db, ItemInNs::Types(resolved), module); | ||
232 | |||
233 | assert_eq!(found_path, Some(mod_path)); | ||
234 | } | ||
235 | |||
236 | #[test] | ||
237 | fn same_module() { | ||
238 | let code = r#" | ||
239 | //- /main.rs | ||
240 | struct S; | ||
241 | <|> | ||
242 | "#; | ||
243 | check_found_path(code, "S"); | ||
244 | } | ||
245 | |||
246 | #[test] | ||
247 | fn enum_variant() { | ||
248 | let code = r#" | ||
249 | //- /main.rs | ||
250 | enum E { A } | ||
251 | <|> | ||
252 | "#; | ||
253 | check_found_path(code, "E::A"); | ||
254 | } | ||
255 | |||
256 | #[test] | ||
257 | fn sub_module() { | ||
258 | let code = r#" | ||
259 | //- /main.rs | ||
260 | mod foo { | ||
261 | pub struct S; | ||
262 | } | ||
263 | <|> | ||
264 | "#; | ||
265 | check_found_path(code, "foo::S"); | ||
266 | } | ||
267 | |||
268 | #[test] | ||
269 | fn super_module() { | ||
270 | let code = r#" | ||
271 | //- /main.rs | ||
272 | mod foo; | ||
273 | //- /foo.rs | ||
274 | mod bar; | ||
275 | struct S; | ||
276 | //- /foo/bar.rs | ||
277 | <|> | ||
278 | "#; | ||
279 | check_found_path(code, "super::S"); | ||
280 | } | ||
281 | |||
282 | #[test] | ||
283 | fn self_module() { | ||
284 | let code = r#" | ||
285 | //- /main.rs | ||
286 | mod foo; | ||
287 | //- /foo.rs | ||
288 | <|> | ||
289 | "#; | ||
290 | check_found_path(code, "self"); | ||
291 | } | ||
292 | |||
293 | #[test] | ||
294 | fn crate_root() { | ||
295 | let code = r#" | ||
296 | //- /main.rs | ||
297 | mod foo; | ||
298 | //- /foo.rs | ||
299 | <|> | ||
300 | "#; | ||
301 | check_found_path(code, "crate"); | ||
302 | } | ||
303 | |||
304 | #[test] | ||
305 | fn same_crate() { | ||
306 | let code = r#" | ||
307 | //- /main.rs | ||
308 | mod foo; | ||
309 | struct S; | ||
310 | //- /foo.rs | ||
311 | <|> | ||
312 | "#; | ||
313 | check_found_path(code, "crate::S"); | ||
314 | } | ||
315 | |||
316 | #[test] | ||
317 | fn different_crate() { | ||
318 | let code = r#" | ||
319 | //- /main.rs crate:main deps:std | ||
320 | <|> | ||
321 | //- /std.rs crate:std | ||
322 | pub struct S; | ||
323 | "#; | ||
324 | check_found_path(code, "std::S"); | ||
325 | } | ||
326 | |||
327 | #[test] | ||
328 | fn different_crate_renamed() { | ||
329 | let code = r#" | ||
330 | //- /main.rs crate:main deps:std | ||
331 | extern crate std as std_renamed; | ||
332 | <|> | ||
333 | //- /std.rs crate:std | ||
334 | pub struct S; | ||
335 | "#; | ||
336 | check_found_path(code, "std_renamed::S"); | ||
337 | } | ||
338 | |||
339 | #[test] | ||
340 | fn same_crate_reexport() { | ||
341 | let code = r#" | ||
342 | //- /main.rs | ||
343 | mod bar { | ||
344 | mod foo { pub(super) struct S; } | ||
345 | pub(crate) use foo::*; | ||
346 | } | ||
347 | <|> | ||
348 | "#; | ||
349 | check_found_path(code, "bar::S"); | ||
350 | } | ||
351 | |||
352 | #[test] | ||
353 | fn same_crate_reexport_rename() { | ||
354 | let code = r#" | ||
355 | //- /main.rs | ||
356 | mod bar { | ||
357 | mod foo { pub(super) struct S; } | ||
358 | pub(crate) use foo::S as U; | ||
359 | } | ||
360 | <|> | ||
361 | "#; | ||
362 | check_found_path(code, "bar::U"); | ||
363 | } | ||
364 | |||
365 | #[test] | ||
366 | fn different_crate_reexport() { | ||
367 | let code = r#" | ||
368 | //- /main.rs crate:main deps:std | ||
369 | <|> | ||
370 | //- /std.rs crate:std deps:core | ||
371 | pub use core::S; | ||
372 | //- /core.rs crate:core | ||
373 | pub struct S; | ||
374 | "#; | ||
375 | check_found_path(code, "std::S"); | ||
376 | } | ||
377 | |||
378 | #[test] | ||
379 | fn prelude() { | ||
380 | let code = r#" | ||
381 | //- /main.rs crate:main deps:std | ||
382 | <|> | ||
383 | //- /std.rs crate:std | ||
384 | pub mod prelude { pub struct S; } | ||
385 | #[prelude_import] | ||
386 | pub use prelude::*; | ||
387 | "#; | ||
388 | check_found_path(code, "S"); | ||
389 | } | ||
390 | |||
391 | #[test] | ||
392 | fn enum_variant_from_prelude() { | ||
393 | let code = r#" | ||
394 | //- /main.rs crate:main deps:std | ||
395 | <|> | ||
396 | //- /std.rs crate:std | ||
397 | pub mod prelude { | ||
398 | pub enum Option<T> { Some(T), None } | ||
399 | pub use Option::*; | ||
400 | } | ||
401 | #[prelude_import] | ||
402 | pub use prelude::*; | ||
403 | "#; | ||
404 | check_found_path(code, "None"); | ||
405 | check_found_path(code, "Some"); | ||
406 | } | ||
407 | |||
408 | #[test] | ||
409 | fn shortest_path() { | ||
410 | let code = r#" | ||
411 | //- /main.rs | ||
412 | pub mod foo; | ||
413 | pub mod baz; | ||
414 | struct S; | ||
415 | <|> | ||
416 | //- /foo.rs | ||
417 | pub mod bar { pub struct S; } | ||
418 | //- /baz.rs | ||
419 | pub use crate::foo::bar::S; | ||
420 | "#; | ||
421 | check_found_path(code, "baz::S"); | ||
422 | } | ||
423 | |||
424 | #[test] | ||
425 | fn discount_private_imports() { | ||
426 | let code = r#" | ||
427 | //- /main.rs | ||
428 | mod foo; | ||
429 | pub mod bar { pub struct S; } | ||
430 | use bar::S; | ||
431 | //- /foo.rs | ||
432 | <|> | ||
433 | "#; | ||
434 | // crate::S would be shorter, but using private imports seems wrong | ||
435 | check_found_path(code, "crate::bar::S"); | ||
436 | } | ||
437 | |||
438 | #[test] | ||
439 | fn import_cycle() { | ||
440 | let code = r#" | ||
441 | //- /main.rs | ||
442 | pub mod foo; | ||
443 | pub mod bar; | ||
444 | pub mod baz; | ||
445 | //- /bar.rs | ||
446 | <|> | ||
447 | //- /foo.rs | ||
448 | pub use super::baz; | ||
449 | pub struct S; | ||
450 | //- /baz.rs | ||
451 | pub use super::foo; | ||
452 | "#; | ||
453 | check_found_path(code, "crate::foo::S"); | ||
454 | } | ||
455 | } | ||