crates/hir_def/src/find_path.rs

   1 //! An algorithm to find a path to refer to a certain item.
   2
   3 use hir_expand::name::{known, AsName, Name};
   4 use rustc_hash::FxHashSet;
   5 use test_utils::mark;
   6
   7 use crate::nameres::CrateDefMap;
   8 use 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.
  20 pub fn find_path(db: &dyn DefDatabase, item: ItemInNs, from: ModuleId) -> Option<ModPath> {
  21     let _p = profile::span("find_path");
  22     find_path_inner(db, item, from, MAX_PATH_LEN, None)
  23 }
  24
  25 pub fn find_path_prefixed(
  26     db: &dyn DefDatabase,
  27     item: ItemInNs,
  28     from: ModuleId,
  29     prefix_kind: PrefixKind,
  30 ) -> Option<ModPath> {
  31     let _p = profile::span("find_path_prefixed");
  32     find_path_inner(db, item, from, MAX_PATH_LEN, Some(prefix_kind))
  33 }
  34
  35 const MAX_PATH_LEN: usize = 15;
  36
  37 impl ModPath {
  38     fn starts_with_std(&self) -> bool {
  39         self.segments.first() == Some(&known::std)
  40     }
  41
  42     // When std library is present, paths starting with `std::`
  43     // should be preferred over paths starting with `core::` and `alloc::`
  44     fn can_start_with_std(&self) -> bool {
  45         let first_segment = self.segments.first();
  46         first_segment == Some(&known::alloc) || first_segment == Some(&known::core)
  47     }
  48 }
  49
  50 fn check_self_super(def_map: &CrateDefMap, item: ItemInNs, from: ModuleId) -> Option<ModPath> {
  51     if item == ItemInNs::Types(from.into()) {
  52         // - if the item is the module we're in, use `self`
  53         Some(ModPath::from_segments(PathKind::Super(0), Vec::new()))
  54     } else if let Some(parent_id) = def_map.modules[from.local_id].parent {
  55         // - if the item is the parent module, use `super` (this is not used recursively, since `super::super` is ugly)
  56         if item
  57             == ItemInNs::Types(ModuleDefId::ModuleId(ModuleId {
  58                 krate: from.krate,
  59                 local_id: parent_id,
  60             }))
  61         {
  62             Some(ModPath::from_segments(PathKind::Super(1), Vec::new()))
  63         } else {
  64             None
  65         }
  66     } else {
  67         None
  68     }
  69 }
  70
  71 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
  72 pub enum PrefixKind {
  73     /// Causes paths to always start with either `self`, `super`, `crate` or a crate-name.
  74     /// This is the same as plain, just that paths will start with `self` iprepended f the path
  75     /// starts with an identifier that is not a crate.
  76     BySelf,
  77     /// Causes paths to ignore imports in the local module.
  78     Plain,
  79     /// Causes paths to start with `crate` where applicable, effectively forcing paths to be absolute.
  80     ByCrate,
  81 }
  82
  83 impl PrefixKind {
  84     #[inline]
  85     fn prefix(self) -> PathKind {
  86         match self {
  87             PrefixKind::BySelf => PathKind::Super(0),
  88             PrefixKind::Plain => PathKind::Plain,
  89             PrefixKind::ByCrate => PathKind::Crate,
  90         }
  91     }
  92
  93     #[inline]
  94     fn is_absolute(&self) -> bool {
  95         self == &PrefixKind::ByCrate
  96     }
  97 }
  98
  99 fn find_path_inner(
 100     db: &dyn DefDatabase,
 101     item: ItemInNs,
 102     from: ModuleId,
 103     max_len: usize,
 104     prefixed: Option<PrefixKind>,
 105 ) -> Option<ModPath> {
 106     if max_len == 0 {
 107         return None;
 108     }
 109
 110     // Base cases:
 111
 112     // - if the item is already in scope, return the name under which it is
 113     let def_map = db.crate_def_map(from.krate);
 114     let from_scope: &crate::item_scope::ItemScope = &def_map.modules[from.local_id].scope;
 115     let scope_name =
 116         if let Some((name, _)) = from_scope.name_of(item) { Some(name.clone()) } else { None };
 117     if prefixed.is_none() && scope_name.is_some() {
 118         return scope_name
 119             .map(|scope_name| ModPath::from_segments(PathKind::Plain, vec![scope_name]));
 120     }
 121
 122     // - if the item is the crate root, return `crate`
 123     if item
 124         == ItemInNs::Types(ModuleDefId::ModuleId(ModuleId {
 125             krate: from.krate,
 126             local_id: def_map.root,
 127         }))
 128     {
 129         return Some(ModPath::from_segments(PathKind::Crate, Vec::new()));
 130     }
 131
 132     if prefixed.filter(PrefixKind::is_absolute).is_none() {
 133         if let modpath @ Some(_) = check_self_super(&def_map, item, from) {
 134             return modpath;
 135         }
 136     }
 137
 138     // - if the item is the crate root of a dependency crate, return the name from the extern prelude
 139     for (name, def_id) in &def_map.extern_prelude {
 140         if item == ItemInNs::Types(*def_id) {
 141             let name = scope_name.unwrap_or_else(|| name.clone());
 142             return Some(ModPath::from_segments(PathKind::Plain, vec![name]));
 143         }
 144     }
 145
 146     // - if the item is in the prelude, return the name from there
 147     if let Some(prelude_module) = def_map.prelude {
 148         let prelude_def_map = db.crate_def_map(prelude_module.krate);
 149         let prelude_scope: &crate::item_scope::ItemScope =
 150             &prelude_def_map.modules[prelude_module.local_id].scope;
 151         if let Some((name, vis)) = prelude_scope.name_of(item) {
 152             if vis.is_visible_from(db, from) {
 153                 return Some(ModPath::from_segments(PathKind::Plain, vec![name.clone()]));
 154             }
 155         }
 156     }
 157
 158     // - if the item is a builtin, it's in scope
 159     if let ItemInNs::Types(ModuleDefId::BuiltinType(builtin)) = item {
 160         return Some(ModPath::from_segments(PathKind::Plain, vec![builtin.as_name()]));
 161     }
 162
 163     // Recursive case:
 164     // - if the item is an enum variant, refer to it via the enum
 165     if let Some(ModuleDefId::EnumVariantId(variant)) = item.as_module_def_id() {
 166         if let Some(mut path) = find_path(db, ItemInNs::Types(variant.parent.into()), from) {
 167             let data = db.enum_data(variant.parent);
 168             path.segments.push(data.variants[variant.local_id].name.clone());
 169             return Some(path);
 170         }
 171         // If this doesn't work, it seems we have no way of referring to the
 172         // enum; that's very weird, but there might still be a reexport of the
 173         // variant somewhere
 174     }
 175
 176     // - otherwise, look for modules containing (reexporting) it and import it from one of those
 177
 178     let crate_root = ModuleId { local_id: def_map.root, krate: from.krate };
 179     let crate_attrs = db.attrs(crate_root.into());
 180     let prefer_no_std = crate_attrs.by_key("no_std").exists();
 181     let mut best_path = None;
 182     let mut best_path_len = max_len;
 183
 184     if item.krate(db) == Some(from.krate) {
 185         // Item was defined in the same crate that wants to import it. It cannot be found in any
 186         // dependency in this case.
 187
 188         let local_imports = find_local_import_locations(db, item, from);
 189         for (module_id, name) in local_imports {
 190             if let Some(mut path) = find_path_inner(
 191                 db,
 192                 ItemInNs::Types(ModuleDefId::ModuleId(module_id)),
 193                 from,
 194                 best_path_len - 1,
 195                 prefixed,
 196             ) {
 197                 path.segments.push(name);
 198
 199                 let new_path = if let Some(best_path) = best_path {
 200                     select_best_path(best_path, path, prefer_no_std)
 201                 } else {
 202                     path
 203                 };
 204                 best_path_len = new_path.len();
 205                 best_path = Some(new_path);
 206             }
 207         }
 208     } else {
 209         // Item was defined in some upstream crate. This means that it must be exported from one,
 210         // too (unless we can't name it at all). It could *also* be (re)exported by the same crate
 211         // that wants to import it here, but we always prefer to use the external path here.
 212
 213         let crate_graph = db.crate_graph();
 214         let extern_paths = crate_graph[from.krate].dependencies.iter().filter_map(|dep| {
 215             let import_map = db.import_map(dep.crate_id);
 216             import_map.import_info_for(item).and_then(|info| {
 217                 // Determine best path for containing module and append last segment from `info`.
 218                 let mut path = find_path_inner(
 219                     db,
 220                     ItemInNs::Types(ModuleDefId::ModuleId(info.container)),
 221                     from,
 222                     best_path_len - 1,
 223                     prefixed,
 224                 )?;
 225                 mark::hit!(partially_imported);
 226                 path.segments.push(info.path.segments.last().unwrap().clone());
 227                 Some(path)
 228             })
 229         });
 230
 231         for path in extern_paths {
 232             let new_path = if let Some(best_path) = best_path {
 233                 select_best_path(best_path, path, prefer_no_std)
 234             } else {
 235                 path
 236             };
 237             best_path = Some(new_path);
 238         }
 239     }
 240
 241     if let Some(prefix) = prefixed.map(PrefixKind::prefix) {
 242         best_path.or_else(|| {
 243             scope_name.map(|scope_name| ModPath::from_segments(prefix, vec![scope_name]))
 244         })
 245     } else {
 246         best_path
 247     }
 248 }
 249
 250 fn select_best_path(old_path: ModPath, new_path: ModPath, prefer_no_std: bool) -> ModPath {
 251     if old_path.starts_with_std() && new_path.can_start_with_std() {
 252         if prefer_no_std {
 253             mark::hit!(prefer_no_std_paths);
 254             new_path
 255         } else {
 256             mark::hit!(prefer_std_paths);
 257             old_path
 258         }
 259     } else if new_path.starts_with_std() && old_path.can_start_with_std() {
 260         if prefer_no_std {
 261             mark::hit!(prefer_no_std_paths);
 262             old_path
 263         } else {
 264             mark::hit!(prefer_std_paths);
 265             new_path
 266         }
 267     } else if new_path.len() < old_path.len() {
 268         new_path
 269     } else {
 270         old_path
 271     }
 272 }
 273
 274 /// Finds locations in `from.krate` from which `item` can be imported by `from`.
 275 fn find_local_import_locations(
 276     db: &dyn DefDatabase,
 277     item: ItemInNs,
 278     from: ModuleId,
 279 ) -> Vec<(ModuleId, Name)> {
 280     let _p = profile::span("find_local_import_locations");
 281
 282     // `from` can import anything below `from` with visibility of at least `from`, and anything
 283     // above `from` with any visibility. That means we do not need to descend into private siblings
 284     // of `from` (and similar).
 285
 286     let def_map = db.crate_def_map(from.krate);
 287
 288     // Compute the initial worklist. We start with all direct child modules of `from` as well as all
 289     // of its (recursive) parent modules.
 290     let data = &def_map.modules[from.local_id];
 291     let mut worklist = data
 292         .children
 293         .values()
 294         .map(|child| ModuleId { krate: from.krate, local_id: *child })
 295         .collect::<Vec<_>>();
 296     let mut parent = data.parent;
 297     while let Some(p) = parent {
 298         worklist.push(ModuleId { krate: from.krate, local_id: p });
 299         parent = def_map.modules[p].parent;
 300     }
 301
 302     let mut seen: FxHashSet<_> = FxHashSet::default();
 303
 304     let mut locations = Vec::new();
 305     while let Some(module) = worklist.pop() {
 306         if !seen.insert(module) {
 307             continue; // already processed this module
 308         }
 309
 310         let ext_def_map;
 311         let data = if module.krate == from.krate {
 312             &def_map[module.local_id]
 313         } else {
 314             // The crate might reexport a module defined in another crate.
 315             ext_def_map = db.crate_def_map(module.krate);
 316             &ext_def_map[module.local_id]
 317         };
 318
 319         if let Some((name, vis)) = data.scope.name_of(item) {
 320             if vis.is_visible_from(db, from) {
 321                 let is_private = if let Visibility::Module(private_to) = vis {
 322                     private_to.local_id == module.local_id
 323                 } else {
 324                     false
 325                 };
 326                 let is_original_def = if let Some(module_def_id) = item.as_module_def_id() {
 327                     data.scope.declarations().any(|it| it == module_def_id)
 328                 } else {
 329                     false
 330                 };
 331
 332                 // Ignore private imports. these could be used if we are
 333                 // in a submodule of this module, but that's usually not
 334                 // what the user wants; and if this module can import
 335                 // the item and we're a submodule of it, so can we.
 336                 // Also this keeps the cached data smaller.
 337                 if !is_private || is_original_def {
 338                     locations.push((module, name.clone()));
 339                 }
 340             }
 341         }
 342
 343         // Descend into all modules visible from `from`.
 344         for (_, per_ns) in data.scope.entries() {
 345             if let Some((ModuleDefId::ModuleId(module), vis)) = per_ns.take_types_vis() {
 346                 if vis.is_visible_from(db, from) {
 347                     worklist.push(module);
 348                 }
 349             }
 350         }
 351     }
 352
 353     locations
 354 }
 355
 356 #[cfg(test)]
 357 mod tests {
 358     use base_db::fixture::WithFixture;
 359     use hir_expand::hygiene::Hygiene;
 360     use syntax::ast::AstNode;
 361     use test_utils::mark;
 362
 363     use crate::test_db::TestDB;
 364
 365     use super::*;
 366
 367     /// `code` needs to contain a cursor marker; checks that `find_path` for the
 368     /// item the `path` refers to returns that same path when called from the
 369     /// module the cursor is in.
 370     fn check_found_path_(ra_fixture: &str, path: &str, prefix_kind: Option<PrefixKind>) {
 371         let (db, pos) = TestDB::with_position(ra_fixture);
 372         let module = db.module_for_file(pos.file_id);
 373         let parsed_path_file = syntax::SourceFile::parse(&format!("use {};", path));
 374         let ast_path =
 375             parsed_path_file.syntax_node().descendants().find_map(syntax::ast::Path::cast).unwrap();
 376         let mod_path = ModPath::from_src(ast_path, &Hygiene::new_unhygienic()).unwrap();
 377
 378         let crate_def_map = db.crate_def_map(module.krate);
 379         let resolved = crate_def_map
 380             .resolve_path(
 381                 &db,
 382                 module.local_id,
 383                 &mod_path,
 384                 crate::item_scope::BuiltinShadowMode::Module,
 385             )
 386             .0
 387             .take_types()
 388             .unwrap();
 389
 390         let found_path =
 391             find_path_inner(&db, ItemInNs::Types(resolved), module, MAX_PATH_LEN, prefix_kind);
 392         assert_eq!(found_path, Some(mod_path), "{:?}", prefix_kind);
 393     }
 394
 395     fn check_found_path(
 396         ra_fixture: &str,
 397         unprefixed: &str,
 398         prefixed: &str,
 399         absolute: &str,
 400         self_prefixed: &str,
 401     ) {
 402         check_found_path_(ra_fixture, unprefixed, None);
 403         check_found_path_(ra_fixture, prefixed, Some(PrefixKind::Plain));
 404         check_found_path_(ra_fixture, absolute, Some(PrefixKind::ByCrate));
 405         check_found_path_(ra_fixture, self_prefixed, Some(PrefixKind::BySelf));
 406     }
 407
 408     #[test]
 409     fn same_module() {
 410         let code = r#"
 411             //- /main.rs
 412             struct S;
 413             <|>
 414         "#;
 415         check_found_path(code, "S", "S", "crate::S", "self::S");
 416     }
 417
 418     #[test]
 419     fn enum_variant() {
 420         let code = r#"
 421             //- /main.rs
 422             enum E { A }
 423             <|>
 424         "#;
 425         check_found_path(code, "E::A", "E::A", "E::A", "E::A");
 426     }
 427
 428     #[test]
 429     fn sub_module() {
 430         let code = r#"
 431             //- /main.rs
 432             mod foo {
 433                 pub struct S;
 434             }
 435             <|>
 436         "#;
 437         check_found_path(code, "foo::S", "foo::S", "crate::foo::S", "self::foo::S");
 438     }
 439
 440     #[test]
 441     fn super_module() {
 442         let code = r#"
 443             //- /main.rs
 444             mod foo;
 445             //- /foo.rs
 446             mod bar;
 447             struct S;
 448             //- /foo/bar.rs
 449             <|>
 450         "#;
 451         check_found_path(code, "super::S", "super::S", "crate::foo::S", "super::S");
 452     }
 453
 454     #[test]
 455     fn self_module() {
 456         let code = r#"
 457             //- /main.rs
 458             mod foo;
 459             //- /foo.rs
 460             <|>
 461         "#;
 462         check_found_path(code, "self", "self", "crate::foo", "self");
 463     }
 464
 465     #[test]
 466     fn crate_root() {
 467         let code = r#"
 468             //- /main.rs
 469             mod foo;
 470             //- /foo.rs
 471             <|>
 472         "#;
 473         check_found_path(code, "crate", "crate", "crate", "crate");
 474     }
 475
 476     #[test]
 477     fn same_crate() {
 478         let code = r#"
 479             //- /main.rs
 480             mod foo;
 481             struct S;
 482             //- /foo.rs
 483             <|>
 484         "#;
 485         check_found_path(code, "crate::S", "crate::S", "crate::S", "crate::S");
 486     }
 487
 488     #[test]
 489     fn different_crate() {
 490         let code = r#"
 491             //- /main.rs crate:main deps:std
 492             <|>
 493             //- /std.rs crate:std
 494             pub struct S;
 495         "#;
 496         check_found_path(code, "std::S", "std::S", "std::S", "std::S");
 497     }
 498
 499     #[test]
 500     fn different_crate_renamed() {
 501         let code = r#"
 502             //- /main.rs crate:main deps:std
 503             extern crate std as std_renamed;
 504             <|>
 505             //- /std.rs crate:std
 506             pub struct S;
 507         "#;
 508         check_found_path(
 509             code,
 510             "std_renamed::S",
 511             "std_renamed::S",
 512             "std_renamed::S",
 513             "std_renamed::S",
 514         );
 515     }
 516
 517     #[test]
 518     fn partially_imported() {
 519         mark::check!(partially_imported);
 520         // Tests that short paths are used even for external items, when parts of the path are
 521         // already in scope.
 522         let code = r#"
 523             //- /main.rs crate:main deps:syntax
 524
 525             use syntax::ast;
 526             <|>
 527
 528             //- /lib.rs crate:syntax
 529             pub mod ast {
 530                 pub enum ModuleItem {
 531                     A, B, C,
 532                 }
 533             }
 534         "#;
 535         check_found_path(
 536             code,
 537             "ast::ModuleItem",
 538             "syntax::ast::ModuleItem",
 539             "syntax::ast::ModuleItem",
 540             "syntax::ast::ModuleItem",
 541         );
 542
 543         let code = r#"
 544             //- /main.rs crate:main deps:syntax
 545
 546             <|>
 547
 548             //- /lib.rs crate:syntax
 549             pub mod ast {
 550                 pub enum ModuleItem {
 551                     A, B, C,
 552                 }
 553             }
 554         "#;
 555         check_found_path(
 556             code,
 557             "syntax::ast::ModuleItem",
 558             "syntax::ast::ModuleItem",
 559             "syntax::ast::ModuleItem",
 560             "syntax::ast::ModuleItem",
 561         );
 562     }
 563
 564     #[test]
 565     fn same_crate_reexport() {
 566         let code = r#"
 567             //- /main.rs
 568             mod bar {
 569                 mod foo { pub(super) struct S; }
 570                 pub(crate) use foo::*;
 571             }
 572             <|>
 573         "#;
 574         check_found_path(code, "bar::S", "bar::S", "crate::bar::S", "self::bar::S");
 575     }
 576
 577     #[test]
 578     fn same_crate_reexport_rename() {
 579         let code = r#"
 580             //- /main.rs
 581             mod bar {
 582                 mod foo { pub(super) struct S; }
 583                 pub(crate) use foo::S as U;
 584             }
 585             <|>
 586         "#;
 587         check_found_path(code, "bar::U", "bar::U", "crate::bar::U", "self::bar::U");
 588     }
 589
 590     #[test]
 591     fn different_crate_reexport() {
 592         let code = r#"
 593             //- /main.rs crate:main deps:std
 594             <|>
 595             //- /std.rs crate:std deps:core
 596             pub use core::S;
 597             //- /core.rs crate:core
 598             pub struct S;
 599         "#;
 600         check_found_path(code, "std::S", "std::S", "std::S", "std::S");
 601     }
 602
 603     #[test]
 604     fn prelude() {
 605         let code = r#"
 606             //- /main.rs crate:main deps:std
 607             <|>
 608             //- /std.rs crate:std
 609             pub mod prelude { pub struct S; }
 610             #[prelude_import]
 611             pub use prelude::*;
 612         "#;
 613         check_found_path(code, "S", "S", "S", "S");
 614     }
 615
 616     #[test]
 617     fn enum_variant_from_prelude() {
 618         let code = r#"
 619             //- /main.rs crate:main deps:std
 620             <|>
 621             //- /std.rs crate:std
 622             pub mod prelude {
 623                 pub enum Option<T> { Some(T), None }
 624                 pub use Option::*;
 625             }
 626             #[prelude_import]
 627             pub use prelude::*;
 628         "#;
 629         check_found_path(code, "None", "None", "None", "None");
 630         check_found_path(code, "Some", "Some", "Some", "Some");
 631     }
 632
 633     #[test]
 634     fn shortest_path() {
 635         let code = r#"
 636             //- /main.rs
 637             pub mod foo;
 638             pub mod baz;
 639             struct S;
 640             <|>
 641             //- /foo.rs
 642             pub mod bar { pub struct S; }
 643             //- /baz.rs
 644             pub use crate::foo::bar::S;
 645         "#;
 646         check_found_path(code, "baz::S", "baz::S", "crate::baz::S", "self::baz::S");
 647     }
 648
 649     #[test]
 650     fn discount_private_imports() {
 651         let code = r#"
 652             //- /main.rs
 653             mod foo;
 654             pub mod bar { pub struct S; }
 655             use bar::S;
 656             //- /foo.rs
 657             <|>
 658         "#;
 659         // crate::S would be shorter, but using private imports seems wrong
 660         check_found_path(code, "crate::bar::S", "crate::bar::S", "crate::bar::S", "crate::bar::S");
 661     }
 662
 663     #[test]
 664     fn import_cycle() {
 665         let code = r#"
 666             //- /main.rs
 667             pub mod foo;
 668             pub mod bar;
 669             pub mod baz;
 670             //- /bar.rs
 671             <|>
 672             //- /foo.rs
 673             pub use super::baz;
 674             pub struct S;
 675             //- /baz.rs
 676             pub use super::foo;
 677         "#;
 678         check_found_path(code, "crate::foo::S", "crate::foo::S", "crate::foo::S", "crate::foo::S");
 679     }
 680
 681     #[test]
 682     fn prefer_std_paths_over_alloc() {
 683         mark::check!(prefer_std_paths);
 684         let code = r#"
 685         //- /main.rs crate:main deps:alloc,std
 686         <|>
 687
 688         //- /std.rs crate:std deps:alloc
 689         pub mod sync {
 690             pub use alloc::sync::Arc;
 691         }
 692
 693         //- /zzz.rs crate:alloc
 694         pub mod sync {
 695             pub struct Arc;
 696         }
 697         "#;
 698         check_found_path(
 699             code,
 700             "std::sync::Arc",
 701             "std::sync::Arc",
 702             "std::sync::Arc",
 703             "std::sync::Arc",
 704         );
 705     }
 706
 707     #[test]
 708     fn prefer_core_paths_over_std() {
 709         mark::check!(prefer_no_std_paths);
 710         let code = r#"
 711         //- /main.rs crate:main deps:core,std
 712         #![no_std]
 713
 714         <|>
 715
 716         //- /std.rs crate:std deps:core
 717
 718         pub mod fmt {
 719             pub use core::fmt::Error;
 720         }
 721
 722         //- /zzz.rs crate:core
 723
 724         pub mod fmt {
 725             pub struct Error;
 726         }
 727         "#;
 728         check_found_path(
 729             code,
 730             "core::fmt::Error",
 731             "core::fmt::Error",
 732             "core::fmt::Error",
 733             "core::fmt::Error",
 734         );
 735     }
 736
 737     #[test]
 738     fn prefer_alloc_paths_over_std() {
 739         let code = r#"
 740         //- /main.rs crate:main deps:alloc,std
 741         #![no_std]
 742
 743         <|>
 744
 745         //- /std.rs crate:std deps:alloc
 746
 747         pub mod sync {
 748             pub use alloc::sync::Arc;
 749         }
 750
 751         //- /zzz.rs crate:alloc
 752
 753         pub mod sync {
 754             pub struct Arc;
 755         }
 756         "#;
 757         check_found_path(
 758             code,
 759             "alloc::sync::Arc",
 760             "alloc::sync::Arc",
 761             "alloc::sync::Arc",
 762             "alloc::sync::Arc",
 763         );
 764     }
 765
 766     #[test]
 767     fn prefer_shorter_paths_if_not_alloc() {
 768         let code = r#"
 769         //- /main.rs crate:main deps:megaalloc,std
 770         <|>
 771
 772         //- /std.rs crate:std deps:megaalloc
 773         pub mod sync {
 774             pub use megaalloc::sync::Arc;
 775         }
 776
 777         //- /zzz.rs crate:megaalloc
 778         pub struct Arc;
 779         "#;
 780         check_found_path(
 781             code,
 782             "megaalloc::Arc",
 783             "megaalloc::Arc",
 784             "megaalloc::Arc",
 785             "megaalloc::Arc",
 786         );
 787     }
 788
 789     #[test]
 790     fn builtins_are_in_scope() {
 791         let code = r#"
 792         //- /main.rs
 793         <|>
 794
 795         pub mod primitive {
 796             pub use u8;
 797         }
 798         "#;
 799         check_found_path(code, "u8", "u8", "u8", "u8");
 800         check_found_path(code, "u16", "u16", "u16", "u16");
 801     }
 802 }