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                 path.segments.push(info.path.segments.last().unwrap().clone());
 226                 Some(path)
 227             })
 228         });
 229
 230         for path in extern_paths {
 231             let new_path = if let Some(best_path) = best_path {
 232                 select_best_path(best_path, path, prefer_no_std)
 233             } else {
 234                 path
 235             };
 236             best_path = Some(new_path);
 237         }
 238     }
 239
 240     if let Some(prefix) = prefixed.map(PrefixKind::prefix) {
 241         best_path.or_else(|| {
 242             scope_name.map(|scope_name| ModPath::from_segments(prefix, vec![scope_name]))
 243         })
 244     } else {
 245         best_path
 246     }
 247 }
 248
 249 fn select_best_path(old_path: ModPath, new_path: ModPath, prefer_no_std: bool) -> ModPath {
 250     if old_path.starts_with_std() && new_path.can_start_with_std() {
 251         if prefer_no_std {
 252             mark::hit!(prefer_no_std_paths);
 253             new_path
 254         } else {
 255             mark::hit!(prefer_std_paths);
 256             old_path
 257         }
 258     } else if new_path.starts_with_std() && old_path.can_start_with_std() {
 259         if prefer_no_std {
 260             mark::hit!(prefer_no_std_paths);
 261             old_path
 262         } else {
 263             mark::hit!(prefer_std_paths);
 264             new_path
 265         }
 266     } else if new_path.len() < old_path.len() {
 267         new_path
 268     } else {
 269         old_path
 270     }
 271 }
 272
 273 /// Finds locations in `from.krate` from which `item` can be imported by `from`.
 274 fn find_local_import_locations(
 275     db: &dyn DefDatabase,
 276     item: ItemInNs,
 277     from: ModuleId,
 278 ) -> Vec<(ModuleId, Name)> {
 279     let _p = profile::span("find_local_import_locations");
 280
 281     // `from` can import anything below `from` with visibility of at least `from`, and anything
 282     // above `from` with any visibility. That means we do not need to descend into private siblings
 283     // of `from` (and similar).
 284
 285     let def_map = db.crate_def_map(from.krate);
 286
 287     // Compute the initial worklist. We start with all direct child modules of `from` as well as all
 288     // of its (recursive) parent modules.
 289     let data = &def_map.modules[from.local_id];
 290     let mut worklist = data
 291         .children
 292         .values()
 293         .map(|child| ModuleId { krate: from.krate, local_id: *child })
 294         .collect::<Vec<_>>();
 295     let mut parent = data.parent;
 296     while let Some(p) = parent {
 297         worklist.push(ModuleId { krate: from.krate, local_id: p });
 298         parent = def_map.modules[p].parent;
 299     }
 300
 301     let mut seen: FxHashSet<_> = FxHashSet::default();
 302
 303     let mut locations = Vec::new();
 304     while let Some(module) = worklist.pop() {
 305         if !seen.insert(module) {
 306             continue; // already processed this module
 307         }
 308
 309         let ext_def_map;
 310         let data = if module.krate == from.krate {
 311             &def_map[module.local_id]
 312         } else {
 313             // The crate might reexport a module defined in another crate.
 314             ext_def_map = db.crate_def_map(module.krate);
 315             &ext_def_map[module.local_id]
 316         };
 317
 318         if let Some((name, vis)) = data.scope.name_of(item) {
 319             if vis.is_visible_from(db, from) {
 320                 let is_private = if let Visibility::Module(private_to) = vis {
 321                     private_to.local_id == module.local_id
 322                 } else {
 323                     false
 324                 };
 325                 let is_original_def = if let Some(module_def_id) = item.as_module_def_id() {
 326                     data.scope.declarations().any(|it| it == module_def_id)
 327                 } else {
 328                     false
 329                 };
 330
 331                 // Ignore private imports. these could be used if we are
 332                 // in a submodule of this module, but that's usually not
 333                 // what the user wants; and if this module can import
 334                 // the item and we're a submodule of it, so can we.
 335                 // Also this keeps the cached data smaller.
 336                 if !is_private || is_original_def {
 337                     locations.push((module, name.clone()));
 338                 }
 339             }
 340         }
 341
 342         // Descend into all modules visible from `from`.
 343         for (_, per_ns) in data.scope.entries() {
 344             if let Some((ModuleDefId::ModuleId(module), vis)) = per_ns.take_types_vis() {
 345                 if vis.is_visible_from(db, from) {
 346                     worklist.push(module);
 347                 }
 348             }
 349         }
 350     }
 351
 352     locations
 353 }
 354
 355 #[cfg(test)]
 356 mod tests {
 357     use base_db::fixture::WithFixture;
 358     use hir_expand::hygiene::Hygiene;
 359     use syntax::ast::AstNode;
 360     use test_utils::mark;
 361
 362     use crate::test_db::TestDB;
 363
 364     use super::*;
 365
 366     /// `code` needs to contain a cursor marker; checks that `find_path` for the
 367     /// item the `path` refers to returns that same path when called from the
 368     /// module the cursor is in.
 369     fn check_found_path_(ra_fixture: &str, path: &str, prefix_kind: Option<PrefixKind>) {
 370         let (db, pos) = TestDB::with_position(ra_fixture);
 371         let module = db.module_for_file(pos.file_id);
 372         let parsed_path_file = syntax::SourceFile::parse(&format!("use {};", path));
 373         let ast_path =
 374             parsed_path_file.syntax_node().descendants().find_map(syntax::ast::Path::cast).unwrap();
 375         let mod_path = ModPath::from_src(ast_path, &Hygiene::new_unhygienic()).unwrap();
 376
 377         let crate_def_map = db.crate_def_map(module.krate);
 378         let resolved = crate_def_map
 379             .resolve_path(
 380                 &db,
 381                 module.local_id,
 382                 &mod_path,
 383                 crate::item_scope::BuiltinShadowMode::Module,
 384             )
 385             .0
 386             .take_types()
 387             .unwrap();
 388
 389         let found_path =
 390             find_path_inner(&db, ItemInNs::Types(resolved), module, MAX_PATH_LEN, prefix_kind);
 391         assert_eq!(found_path, Some(mod_path), "{:?}", prefix_kind);
 392     }
 393
 394     fn check_found_path(
 395         ra_fixture: &str,
 396         unprefixed: &str,
 397         prefixed: &str,
 398         absolute: &str,
 399         self_prefixed: &str,
 400     ) {
 401         check_found_path_(ra_fixture, unprefixed, None);
 402         check_found_path_(ra_fixture, prefixed, Some(PrefixKind::Plain));
 403         check_found_path_(ra_fixture, absolute, Some(PrefixKind::ByCrate));
 404         check_found_path_(ra_fixture, self_prefixed, Some(PrefixKind::BySelf));
 405     }
 406
 407     #[test]
 408     fn same_module() {
 409         let code = r#"
 410             //- /main.rs
 411             struct S;
 412             <|>
 413         "#;
 414         check_found_path(code, "S", "S", "crate::S", "self::S");
 415     }
 416
 417     #[test]
 418     fn enum_variant() {
 419         let code = r#"
 420             //- /main.rs
 421             enum E { A }
 422             <|>
 423         "#;
 424         check_found_path(code, "E::A", "E::A", "E::A", "E::A");
 425     }
 426
 427     #[test]
 428     fn sub_module() {
 429         let code = r#"
 430             //- /main.rs
 431             mod foo {
 432                 pub struct S;
 433             }
 434             <|>
 435         "#;
 436         check_found_path(code, "foo::S", "foo::S", "crate::foo::S", "self::foo::S");
 437     }
 438
 439     #[test]
 440     fn super_module() {
 441         let code = r#"
 442             //- /main.rs
 443             mod foo;
 444             //- /foo.rs
 445             mod bar;
 446             struct S;
 447             //- /foo/bar.rs
 448             <|>
 449         "#;
 450         check_found_path(code, "super::S", "super::S", "crate::foo::S", "super::S");
 451     }
 452
 453     #[test]
 454     fn self_module() {
 455         let code = r#"
 456             //- /main.rs
 457             mod foo;
 458             //- /foo.rs
 459             <|>
 460         "#;
 461         check_found_path(code, "self", "self", "crate::foo", "self");
 462     }
 463
 464     #[test]
 465     fn crate_root() {
 466         let code = r#"
 467             //- /main.rs
 468             mod foo;
 469             //- /foo.rs
 470             <|>
 471         "#;
 472         check_found_path(code, "crate", "crate", "crate", "crate");
 473     }
 474
 475     #[test]
 476     fn same_crate() {
 477         let code = r#"
 478             //- /main.rs
 479             mod foo;
 480             struct S;
 481             //- /foo.rs
 482             <|>
 483         "#;
 484         check_found_path(code, "crate::S", "crate::S", "crate::S", "crate::S");
 485     }
 486
 487     #[test]
 488     fn different_crate() {
 489         let code = r#"
 490             //- /main.rs crate:main deps:std
 491             <|>
 492             //- /std.rs crate:std
 493             pub struct S;
 494         "#;
 495         check_found_path(code, "std::S", "std::S", "std::S", "std::S");
 496     }
 497
 498     #[test]
 499     fn different_crate_renamed() {
 500         let code = r#"
 501             //- /main.rs crate:main deps:std
 502             extern crate std as std_renamed;
 503             <|>
 504             //- /std.rs crate:std
 505             pub struct S;
 506         "#;
 507         check_found_path(
 508             code,
 509             "std_renamed::S",
 510             "std_renamed::S",
 511             "std_renamed::S",
 512             "std_renamed::S",
 513         );
 514     }
 515
 516     #[test]
 517     fn partially_imported() {
 518         // Tests that short paths are used even for external items, when parts of the path are
 519         // already in scope.
 520         let code = r#"
 521             //- /main.rs crate:main deps:syntax
 522
 523             use syntax::ast;
 524             <|>
 525
 526             //- /lib.rs crate:syntax
 527             pub mod ast {
 528                 pub enum ModuleItem {
 529                     A, B, C,
 530                 }
 531             }
 532         "#;
 533         check_found_path(
 534             code,
 535             "ast::ModuleItem",
 536             "syntax::ast::ModuleItem",
 537             "syntax::ast::ModuleItem",
 538             "syntax::ast::ModuleItem",
 539         );
 540
 541         let code = r#"
 542             //- /main.rs crate:main deps:syntax
 543
 544             <|>
 545
 546             //- /lib.rs crate:syntax
 547             pub mod ast {
 548                 pub enum ModuleItem {
 549                     A, B, C,
 550                 }
 551             }
 552         "#;
 553         check_found_path(
 554             code,
 555             "syntax::ast::ModuleItem",
 556             "syntax::ast::ModuleItem",
 557             "syntax::ast::ModuleItem",
 558             "syntax::ast::ModuleItem",
 559         );
 560     }
 561
 562     #[test]
 563     fn same_crate_reexport() {
 564         let code = r#"
 565             //- /main.rs
 566             mod bar {
 567                 mod foo { pub(super) struct S; }
 568                 pub(crate) use foo::*;
 569             }
 570             <|>
 571         "#;
 572         check_found_path(code, "bar::S", "bar::S", "crate::bar::S", "self::bar::S");
 573     }
 574
 575     #[test]
 576     fn same_crate_reexport_rename() {
 577         let code = r#"
 578             //- /main.rs
 579             mod bar {
 580                 mod foo { pub(super) struct S; }
 581                 pub(crate) use foo::S as U;
 582             }
 583             <|>
 584         "#;
 585         check_found_path(code, "bar::U", "bar::U", "crate::bar::U", "self::bar::U");
 586     }
 587
 588     #[test]
 589     fn different_crate_reexport() {
 590         let code = r#"
 591             //- /main.rs crate:main deps:std
 592             <|>
 593             //- /std.rs crate:std deps:core
 594             pub use core::S;
 595             //- /core.rs crate:core
 596             pub struct S;
 597         "#;
 598         check_found_path(code, "std::S", "std::S", "std::S", "std::S");
 599     }
 600
 601     #[test]
 602     fn prelude() {
 603         let code = r#"
 604             //- /main.rs crate:main deps:std
 605             <|>
 606             //- /std.rs crate:std
 607             pub mod prelude { pub struct S; }
 608             #[prelude_import]
 609             pub use prelude::*;
 610         "#;
 611         check_found_path(code, "S", "S", "S", "S");
 612     }
 613
 614     #[test]
 615     fn enum_variant_from_prelude() {
 616         let code = r#"
 617             //- /main.rs crate:main deps:std
 618             <|>
 619             //- /std.rs crate:std
 620             pub mod prelude {
 621                 pub enum Option<T> { Some(T), None }
 622                 pub use Option::*;
 623             }
 624             #[prelude_import]
 625             pub use prelude::*;
 626         "#;
 627         check_found_path(code, "None", "None", "None", "None");
 628         check_found_path(code, "Some", "Some", "Some", "Some");
 629     }
 630
 631     #[test]
 632     fn shortest_path() {
 633         let code = r#"
 634             //- /main.rs
 635             pub mod foo;
 636             pub mod baz;
 637             struct S;
 638             <|>
 639             //- /foo.rs
 640             pub mod bar { pub struct S; }
 641             //- /baz.rs
 642             pub use crate::foo::bar::S;
 643         "#;
 644         check_found_path(code, "baz::S", "baz::S", "crate::baz::S", "self::baz::S");
 645     }
 646
 647     #[test]
 648     fn discount_private_imports() {
 649         let code = r#"
 650             //- /main.rs
 651             mod foo;
 652             pub mod bar { pub struct S; }
 653             use bar::S;
 654             //- /foo.rs
 655             <|>
 656         "#;
 657         // crate::S would be shorter, but using private imports seems wrong
 658         check_found_path(code, "crate::bar::S", "crate::bar::S", "crate::bar::S", "crate::bar::S");
 659     }
 660
 661     #[test]
 662     fn import_cycle() {
 663         let code = r#"
 664             //- /main.rs
 665             pub mod foo;
 666             pub mod bar;
 667             pub mod baz;
 668             //- /bar.rs
 669             <|>
 670             //- /foo.rs
 671             pub use super::baz;
 672             pub struct S;
 673             //- /baz.rs
 674             pub use super::foo;
 675         "#;
 676         check_found_path(code, "crate::foo::S", "crate::foo::S", "crate::foo::S", "crate::foo::S");
 677     }
 678
 679     #[test]
 680     fn prefer_std_paths_over_alloc() {
 681         mark::check!(prefer_std_paths);
 682         let code = r#"
 683         //- /main.rs crate:main deps:alloc,std
 684         <|>
 685
 686         //- /std.rs crate:std deps:alloc
 687         pub mod sync {
 688             pub use alloc::sync::Arc;
 689         }
 690
 691         //- /zzz.rs crate:alloc
 692         pub mod sync {
 693             pub struct Arc;
 694         }
 695         "#;
 696         check_found_path(
 697             code,
 698             "std::sync::Arc",
 699             "std::sync::Arc",
 700             "std::sync::Arc",
 701             "std::sync::Arc",
 702         );
 703     }
 704
 705     #[test]
 706     fn prefer_core_paths_over_std() {
 707         mark::check!(prefer_no_std_paths);
 708         let code = r#"
 709         //- /main.rs crate:main deps:core,std
 710         #![no_std]
 711
 712         <|>
 713
 714         //- /std.rs crate:std deps:core
 715
 716         pub mod fmt {
 717             pub use core::fmt::Error;
 718         }
 719
 720         //- /zzz.rs crate:core
 721
 722         pub mod fmt {
 723             pub struct Error;
 724         }
 725         "#;
 726         check_found_path(
 727             code,
 728             "core::fmt::Error",
 729             "core::fmt::Error",
 730             "core::fmt::Error",
 731             "core::fmt::Error",
 732         );
 733     }
 734
 735     #[test]
 736     fn prefer_alloc_paths_over_std() {
 737         let code = r#"
 738         //- /main.rs crate:main deps:alloc,std
 739         #![no_std]
 740
 741         <|>
 742
 743         //- /std.rs crate:std deps:alloc
 744
 745         pub mod sync {
 746             pub use alloc::sync::Arc;
 747         }
 748
 749         //- /zzz.rs crate:alloc
 750
 751         pub mod sync {
 752             pub struct Arc;
 753         }
 754         "#;
 755         check_found_path(
 756             code,
 757             "alloc::sync::Arc",
 758             "alloc::sync::Arc",
 759             "alloc::sync::Arc",
 760             "alloc::sync::Arc",
 761         );
 762     }
 763
 764     #[test]
 765     fn prefer_shorter_paths_if_not_alloc() {
 766         let code = r#"
 767         //- /main.rs crate:main deps:megaalloc,std
 768         <|>
 769
 770         //- /std.rs crate:std deps:megaalloc
 771         pub mod sync {
 772             pub use megaalloc::sync::Arc;
 773         }
 774
 775         //- /zzz.rs crate:megaalloc
 776         pub struct Arc;
 777         "#;
 778         check_found_path(
 779             code,
 780             "megaalloc::Arc",
 781             "megaalloc::Arc",
 782             "megaalloc::Arc",
 783             "megaalloc::Arc",
 784         );
 785     }
 786
 787     #[test]
 788     fn builtins_are_in_scope() {
 789         let code = r#"
 790         //- /main.rs
 791         <|>
 792
 793         pub mod primitive {
 794             pub use u8;
 795         }
 796         "#;
 797         check_found_path(code, "u8", "u8", "u8", "u8");
 798         check_found_path(code, "u16", "u16", "u16", "u16");
 799     }
 800 }