aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir_def/src/find_path.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_hir_def/src/find_path.rs')
-rw-r--r--crates/ra_hir_def/src/find_path.rs691
1 files changed, 0 insertions, 691 deletions
diff --git a/crates/ra_hir_def/src/find_path.rs b/crates/ra_hir_def/src/find_path.rs
deleted file mode 100644
index 06701a830..000000000
--- a/crates/ra_hir_def/src/find_path.rs
+++ /dev/null
@@ -1,691 +0,0 @@
1//! An algorithm to find a path to refer to a certain item.
2
3use hir_expand::name::{known, AsName, Name};
4use ra_prof::profile;
5use rustc_hash::FxHashSet;
6use test_utils::mark;
7
8use crate::{
9 db::DefDatabase,
10 item_scope::ItemInNs,
11 path::{ModPath, PathKind},
12 visibility::Visibility,
13 ModuleDefId, ModuleId,
14};
15
16// FIXME: handle local items
17
18/// Find a path that can be used to refer to a certain item. This can depend on
19/// *from where* you're referring to the item, hence the `from` parameter.
20pub fn find_path(db: &dyn DefDatabase, item: ItemInNs, from: ModuleId) -> Option<ModPath> {
21 let _p = profile("find_path");
22 find_path_inner(db, item, from, MAX_PATH_LEN)
23}
24
25const MAX_PATH_LEN: usize = 15;
26
27impl ModPath {
28 fn starts_with_std(&self) -> bool {
29 self.segments.first() == Some(&known::std)
30 }
31
32 // When std library is present, paths starting with `std::`
33 // should be preferred over paths starting with `core::` and `alloc::`
34 fn can_start_with_std(&self) -> bool {
35 let first_segment = self.segments.first();
36 first_segment == Some(&known::alloc) || first_segment == Some(&known::core)
37 }
38}
39
40fn find_path_inner(
41 db: &dyn DefDatabase,
42 item: ItemInNs,
43 from: ModuleId,
44 max_len: usize,
45) -> Option<ModPath> {
46 if max_len == 0 {
47 return None;
48 }
49
50 // Base cases:
51
52 // - if the item is already in scope, return the name under which it is
53 let def_map = db.crate_def_map(from.krate);
54 let from_scope: &crate::item_scope::ItemScope = &def_map.modules[from.local_id].scope;
55 if let Some((name, _)) = from_scope.name_of(item) {
56 return Some(ModPath::from_segments(PathKind::Plain, vec![name.clone()]));
57 }
58
59 // - if the item is the crate root, return `crate`
60 if item
61 == ItemInNs::Types(ModuleDefId::ModuleId(ModuleId {
62 krate: from.krate,
63 local_id: def_map.root,
64 }))
65 {
66 return Some(ModPath::from_segments(PathKind::Crate, Vec::new()));
67 }
68
69 // - if the item is the module we're in, use `self`
70 if item == ItemInNs::Types(from.into()) {
71 return Some(ModPath::from_segments(PathKind::Super(0), Vec::new()));
72 }
73
74 // - if the item is the parent module, use `super` (this is not used recursively, since `super::super` is ugly)
75 if let Some(parent_id) = def_map.modules[from.local_id].parent {
76 if item
77 == ItemInNs::Types(ModuleDefId::ModuleId(ModuleId {
78 krate: from.krate,
79 local_id: parent_id,
80 }))
81 {
82 return Some(ModPath::from_segments(PathKind::Super(1), Vec::new()));
83 }
84 }
85
86 // - if the item is the crate root of a dependency crate, return the name from the extern prelude
87 for (name, def_id) in &def_map.extern_prelude {
88 if item == ItemInNs::Types(*def_id) {
89 return Some(ModPath::from_segments(PathKind::Plain, vec![name.clone()]));
90 }
91 }
92
93 // - if the item is in the prelude, return the name from there
94 if let Some(prelude_module) = def_map.prelude {
95 let prelude_def_map = db.crate_def_map(prelude_module.krate);
96 let prelude_scope: &crate::item_scope::ItemScope =
97 &prelude_def_map.modules[prelude_module.local_id].scope;
98 if let Some((name, vis)) = prelude_scope.name_of(item) {
99 if vis.is_visible_from(db, from) {
100 return Some(ModPath::from_segments(PathKind::Plain, vec![name.clone()]));
101 }
102 }
103 }
104
105 // - if the item is a builtin, it's in scope
106 if let ItemInNs::Types(ModuleDefId::BuiltinType(builtin)) = item {
107 return Some(ModPath::from_segments(PathKind::Plain, vec![builtin.as_name()]));
108 }
109
110 // Recursive case:
111 // - if the item is an enum variant, refer to it via the enum
112 if let Some(ModuleDefId::EnumVariantId(variant)) = item.as_module_def_id() {
113 if let Some(mut path) = find_path(db, ItemInNs::Types(variant.parent.into()), from) {
114 let data = db.enum_data(variant.parent);
115 path.segments.push(data.variants[variant.local_id].name.clone());
116 return Some(path);
117 }
118 // If this doesn't work, it seems we have no way of referring to the
119 // enum; that's very weird, but there might still be a reexport of the
120 // variant somewhere
121 }
122
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 };
126 let crate_attrs = db.attrs(crate_root.into());
127 let prefer_no_std = crate_attrs.by_key("no_std").exists();
128 let mut best_path = None;
129 let mut best_path_len = max_len;
130
131 if item.krate(db) == Some(from.krate) {
132 // Item was defined in the same crate that wants to import it. It cannot be found in any
133 // dependency in this case.
134
135 let local_imports = find_local_import_locations(db, item, from);
136 for (module_id, name) in local_imports {
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.import_info_for(item).and_then(|info| {
163 // Determine best path for containing module and append last segment from `info`.
164 let mut path = find_path_inner(
165 db,
166 ItemInNs::Types(ModuleDefId::ModuleId(info.container)),
167 from,
168 best_path_len - 1,
169 )?;
170 path.segments.push(info.path.segments.last().unwrap().clone());
171 Some(path)
172 })
173 });
174
175 for path in extern_paths {
176 let new_path = if let Some(best_path) = best_path {
177 select_best_path(best_path, path, prefer_no_std)
178 } else {
179 path
180 };
181 best_path = Some(new_path);
182 }
183 }
184
185 best_path
186}
187
188fn select_best_path(old_path: ModPath, new_path: ModPath, prefer_no_std: bool) -> ModPath {
189 if old_path.starts_with_std() && new_path.can_start_with_std() {
190 if prefer_no_std {
191 mark::hit!(prefer_no_std_paths);
192 new_path
193 } else {
194 mark::hit!(prefer_std_paths);
195 old_path
196 }
197 } else if new_path.starts_with_std() && old_path.can_start_with_std() {
198 if prefer_no_std {
199 mark::hit!(prefer_no_std_paths);
200 old_path
201 } else {
202 mark::hit!(prefer_std_paths);
203 new_path
204 }
205 } else if new_path.len() < old_path.len() {
206 new_path
207 } else {
208 old_path
209 }
210}
211
212/// Finds locations in `from.krate` from which `item` can be imported by `from`.
213fn find_local_import_locations(
214 db: &dyn DefDatabase,
215 item: ItemInNs,
216 from: ModuleId,
217) -> Vec<(ModuleId, Name)> {
218 let _p = profile("find_local_import_locations");
219
220 // `from` can import anything below `from` with visibility of at least `from`, and anything
221 // above `from` with any visibility. That means we do not need to descend into private siblings
222 // of `from` (and similar).
223
224 let def_map = db.crate_def_map(from.krate);
225
226 // Compute the initial worklist. We start with all direct child modules of `from` as well as all
227 // of its (recursive) parent modules.
228 let data = &def_map.modules[from.local_id];
229 let mut worklist = data
230 .children
231 .values()
232 .map(|child| ModuleId { krate: from.krate, local_id: *child })
233 .collect::<Vec<_>>();
234 let mut parent = data.parent;
235 while let Some(p) = parent {
236 worklist.push(ModuleId { krate: from.krate, local_id: p });
237 parent = def_map.modules[p].parent;
238 }
239
240 let mut seen: FxHashSet<_> = FxHashSet::default();
241
242 let mut locations = Vec::new();
243 while let Some(module) = worklist.pop() {
244 if !seen.insert(module) {
245 continue; // already processed this module
246 }
247
248 let ext_def_map;
249 let data = if module.krate == from.krate {
250 &def_map[module.local_id]
251 } else {
252 // The crate might reexport a module defined in another crate.
253 ext_def_map = db.crate_def_map(module.krate);
254 &ext_def_map[module.local_id]
255 };
256
257 if let Some((name, vis)) = data.scope.name_of(item) {
258 if vis.is_visible_from(db, from) {
259 let is_private = if let Visibility::Module(private_to) = vis {
260 private_to.local_id == module.local_id
261 } else {
262 false
263 };
264 let is_original_def = if let Some(module_def_id) = item.as_module_def_id() {
265 data.scope.declarations().any(|it| it == module_def_id)
266 } else {
267 false
268 };
269
270 // Ignore private imports. these could be used if we are
271 // in a submodule of this module, but that's usually not
272 // what the user wants; and if this module can import
273 // the item and we're a submodule of it, so can we.
274 // Also this keeps the cached data smaller.
275 if !is_private || is_original_def {
276 locations.push((module, name.clone()));
277 }
278 }
279 }
280
281 // Descend into all modules visible from `from`.
282 for (_, per_ns) in data.scope.entries() {
283 if let Some((ModuleDefId::ModuleId(module), vis)) = per_ns.take_types_vis() {
284 if vis.is_visible_from(db, from) {
285 worklist.push(module);
286 }
287 }
288 }
289 }
290
291 locations
292}
293
294#[cfg(test)]
295mod tests {
296 use hir_expand::hygiene::Hygiene;
297 use ra_db::fixture::WithFixture;
298 use ra_syntax::ast::AstNode;
299 use test_utils::mark;
300
301 use crate::test_db::TestDB;
302
303 use super::*;
304
305 /// `code` needs to contain a cursor marker; checks that `find_path` for the
306 /// item the `path` refers to returns that same path when called from the
307 /// module the cursor is in.
308 fn check_found_path(ra_fixture: &str, path: &str) {
309 let (db, pos) = TestDB::with_position(ra_fixture);
310 let module = db.module_for_file(pos.file_id);
311 let parsed_path_file = ra_syntax::SourceFile::parse(&format!("use {};", path));
312 let ast_path = parsed_path_file
313 .syntax_node()
314 .descendants()
315 .find_map(ra_syntax::ast::Path::cast)
316 .unwrap();
317 let mod_path = ModPath::from_src(ast_path, &Hygiene::new_unhygienic()).unwrap();
318
319 let crate_def_map = db.crate_def_map(module.krate);
320 let resolved = crate_def_map
321 .resolve_path(
322 &db,
323 module.local_id,
324 &mod_path,
325 crate::item_scope::BuiltinShadowMode::Module,
326 )
327 .0
328 .take_types()
329 .unwrap();
330
331 let found_path = find_path(&db, ItemInNs::Types(resolved), module);
332
333 assert_eq!(found_path, Some(mod_path));
334 }
335
336 #[test]
337 fn same_module() {
338 let code = r#"
339 //- /main.rs
340 struct S;
341 <|>
342 "#;
343 check_found_path(code, "S");
344 }
345
346 #[test]
347 fn enum_variant() {
348 let code = r#"
349 //- /main.rs
350 enum E { A }
351 <|>
352 "#;
353 check_found_path(code, "E::A");
354 }
355
356 #[test]
357 fn sub_module() {
358 let code = r#"
359 //- /main.rs
360 mod foo {
361 pub struct S;
362 }
363 <|>
364 "#;
365 check_found_path(code, "foo::S");
366 }
367
368 #[test]
369 fn super_module() {
370 let code = r#"
371 //- /main.rs
372 mod foo;
373 //- /foo.rs
374 mod bar;
375 struct S;
376 //- /foo/bar.rs
377 <|>
378 "#;
379 check_found_path(code, "super::S");
380 }
381
382 #[test]
383 fn self_module() {
384 let code = r#"
385 //- /main.rs
386 mod foo;
387 //- /foo.rs
388 <|>
389 "#;
390 check_found_path(code, "self");
391 }
392
393 #[test]
394 fn crate_root() {
395 let code = r#"
396 //- /main.rs
397 mod foo;
398 //- /foo.rs
399 <|>
400 "#;
401 check_found_path(code, "crate");
402 }
403
404 #[test]
405 fn same_crate() {
406 let code = r#"
407 //- /main.rs
408 mod foo;
409 struct S;
410 //- /foo.rs
411 <|>
412 "#;
413 check_found_path(code, "crate::S");
414 }
415
416 #[test]
417 fn different_crate() {
418 let code = r#"
419 //- /main.rs crate:main deps:std
420 <|>
421 //- /std.rs crate:std
422 pub struct S;
423 "#;
424 check_found_path(code, "std::S");
425 }
426
427 #[test]
428 fn different_crate_renamed() {
429 let code = r#"
430 //- /main.rs crate:main deps:std
431 extern crate std as std_renamed;
432 <|>
433 //- /std.rs crate:std
434 pub struct S;
435 "#;
436 check_found_path(code, "std_renamed::S");
437 }
438
439 #[test]
440 fn partially_imported() {
441 // Tests that short paths are used even for external items, when parts of the path are
442 // already in scope.
443 check_found_path(
444 r#"
445 //- /main.rs crate:main deps:ra_syntax
446
447 use ra_syntax::ast;
448 <|>
449
450 //- /lib.rs crate:ra_syntax
451 pub mod ast {
452 pub enum ModuleItem {
453 A, B, C,
454 }
455 }
456 "#,
457 "ast::ModuleItem",
458 );
459
460 check_found_path(
461 r#"
462 //- /main.rs crate:main deps:ra_syntax
463
464 <|>
465
466 //- /lib.rs crate:ra_syntax
467 pub mod ast {
468 pub enum ModuleItem {
469 A, B, C,
470 }
471 }
472 "#,
473 "ra_syntax::ast::ModuleItem",
474 );
475 }
476
477 #[test]
478 fn same_crate_reexport() {
479 let code = r#"
480 //- /main.rs
481 mod bar {
482 mod foo { pub(super) struct S; }
483 pub(crate) use foo::*;
484 }
485 <|>
486 "#;
487 check_found_path(code, "bar::S");
488 }
489
490 #[test]
491 fn same_crate_reexport_rename() {
492 let code = r#"
493 //- /main.rs
494 mod bar {
495 mod foo { pub(super) struct S; }
496 pub(crate) use foo::S as U;
497 }
498 <|>
499 "#;
500 check_found_path(code, "bar::U");
501 }
502
503 #[test]
504 fn different_crate_reexport() {
505 let code = r#"
506 //- /main.rs crate:main deps:std
507 <|>
508 //- /std.rs crate:std deps:core
509 pub use core::S;
510 //- /core.rs crate:core
511 pub struct S;
512 "#;
513 check_found_path(code, "std::S");
514 }
515
516 #[test]
517 fn prelude() {
518 let code = r#"
519 //- /main.rs crate:main deps:std
520 <|>
521 //- /std.rs crate:std
522 pub mod prelude { pub struct S; }
523 #[prelude_import]
524 pub use prelude::*;
525 "#;
526 check_found_path(code, "S");
527 }
528
529 #[test]
530 fn enum_variant_from_prelude() {
531 let code = r#"
532 //- /main.rs crate:main deps:std
533 <|>
534 //- /std.rs crate:std
535 pub mod prelude {
536 pub enum Option<T> { Some(T), None }
537 pub use Option::*;
538 }
539 #[prelude_import]
540 pub use prelude::*;
541 "#;
542 check_found_path(code, "None");
543 check_found_path(code, "Some");
544 }
545
546 #[test]
547 fn shortest_path() {
548 let code = r#"
549 //- /main.rs
550 pub mod foo;
551 pub mod baz;
552 struct S;
553 <|>
554 //- /foo.rs
555 pub mod bar { pub struct S; }
556 //- /baz.rs
557 pub use crate::foo::bar::S;
558 "#;
559 check_found_path(code, "baz::S");
560 }
561
562 #[test]
563 fn discount_private_imports() {
564 let code = r#"
565 //- /main.rs
566 mod foo;
567 pub mod bar { pub struct S; }
568 use bar::S;
569 //- /foo.rs
570 <|>
571 "#;
572 // crate::S would be shorter, but using private imports seems wrong
573 check_found_path(code, "crate::bar::S");
574 }
575
576 #[test]
577 fn import_cycle() {
578 let code = r#"
579 //- /main.rs
580 pub mod foo;
581 pub mod bar;
582 pub mod baz;
583 //- /bar.rs
584 <|>
585 //- /foo.rs
586 pub use super::baz;
587 pub struct S;
588 //- /baz.rs
589 pub use super::foo;
590 "#;
591 check_found_path(code, "crate::foo::S");
592 }
593
594 #[test]
595 fn prefer_std_paths_over_alloc() {
596 mark::check!(prefer_std_paths);
597 let code = r#"
598 //- /main.rs crate:main deps:alloc,std
599 <|>
600
601 //- /std.rs crate:std deps:alloc
602 pub mod sync {
603 pub use alloc::sync::Arc;
604 }
605
606 //- /zzz.rs crate:alloc
607 pub mod sync {
608 pub struct Arc;
609 }
610 "#;
611 check_found_path(code, "std::sync::Arc");
612 }
613
614 #[test]
615 fn prefer_core_paths_over_std() {
616 mark::check!(prefer_no_std_paths);
617 let code = r#"
618 //- /main.rs crate:main deps:core,std
619 #![no_std]
620
621 <|>
622
623 //- /std.rs crate:std deps:core
624
625 pub mod fmt {
626 pub use core::fmt::Error;
627 }
628
629 //- /zzz.rs crate:core
630
631 pub mod fmt {
632 pub struct Error;
633 }
634 "#;
635 check_found_path(code, "core::fmt::Error");
636 }
637
638 #[test]
639 fn prefer_alloc_paths_over_std() {
640 let code = r#"
641 //- /main.rs crate:main deps:alloc,std
642 #![no_std]
643
644 <|>
645
646 //- /std.rs crate:std deps:alloc
647
648 pub mod sync {
649 pub use alloc::sync::Arc;
650 }
651
652 //- /zzz.rs crate:alloc
653
654 pub mod sync {
655 pub struct Arc;
656 }
657 "#;
658 check_found_path(code, "alloc::sync::Arc");
659 }
660
661 #[test]
662 fn prefer_shorter_paths_if_not_alloc() {
663 let code = r#"
664 //- /main.rs crate:main deps:megaalloc,std
665 <|>
666
667 //- /std.rs crate:std deps:megaalloc
668 pub mod sync {
669 pub use megaalloc::sync::Arc;
670 }
671
672 //- /zzz.rs crate:megaalloc
673 pub struct Arc;
674 "#;
675 check_found_path(code, "megaalloc::Arc");
676 }
677
678 #[test]
679 fn builtins_are_in_scope() {
680 let code = r#"
681 //- /main.rs
682 <|>
683
684 pub mod primitive {
685 pub use u8;
686 }
687 "#;
688 check_found_path(code, "u8");
689 check_found_path(code, "u16");
690 }
691}
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-19 11:18:55 +0100