src/tools/rust-analyzer/crates/hir-def/src/find_path.rs

   1 //! An algorithm to find a path to refer to a certain item.
   2
   3 use std::{cmp::Ordering, iter};
   4
   5 use hir_expand::name::{known, AsName, Name};
   6 use rustc_hash::FxHashSet;
   7
   8 use crate::{
   9     db::DefDatabase,
  10     item_scope::ItemInNs,
  11     nameres::DefMap,
  12     path::{ModPath, PathKind},
  13     visibility::Visibility,
  14     CrateRootModuleId, ModuleDefId, ModuleId,
  15 };
  16
  17 /// Find a path that can be used to refer to a certain item. This can depend on
  18 /// *from where* you're referring to the item, hence the `from` parameter.
  19 pub fn find_path(
  20     db: &dyn DefDatabase,
  21     item: ItemInNs,
  22     from: ModuleId,
  23     prefer_no_std: bool,
  24 ) -> Option<ModPath> {
  25     let _p = profile::span("find_path");
  26     find_path_inner(db, item, from, None, prefer_no_std)
  27 }
  28
  29 pub fn find_path_prefixed(
  30     db: &dyn DefDatabase,
  31     item: ItemInNs,
  32     from: ModuleId,
  33     prefix_kind: PrefixKind,
  34     prefer_no_std: bool,
  35 ) -> Option<ModPath> {
  36     let _p = profile::span("find_path_prefixed");
  37     find_path_inner(db, item, from, Some(prefix_kind), prefer_no_std)
  38 }
  39
  40 #[derive(Copy, Clone, Debug)]
  41 enum Stability {
  42     Unstable,
  43     Stable,
  44 }
  45 use Stability::*;
  46
  47 fn zip_stability(a: Stability, b: Stability) -> Stability {
  48     match (a, b) {
  49         (Stable, Stable) => Stable,
  50         _ => Unstable,
  51     }
  52 }
  53
  54 const MAX_PATH_LEN: usize = 15;
  55
  56 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
  57 pub enum PrefixKind {
  58     /// Causes paths to always start with either `self`, `super`, `crate` or a crate-name.
  59     /// This is the same as plain, just that paths will start with `self` prepended if the path
  60     /// starts with an identifier that is not a crate.
  61     BySelf,
  62     /// Causes paths to ignore imports in the local module.
  63     Plain,
  64     /// Causes paths to start with `crate` where applicable, effectively forcing paths to be absolute.
  65     ByCrate,
  66 }
  67
  68 impl PrefixKind {
  69     #[inline]
  70     fn prefix(self) -> PathKind {
  71         match self {
  72             PrefixKind::BySelf => PathKind::Super(0),
  73             PrefixKind::Plain => PathKind::Plain,
  74             PrefixKind::ByCrate => PathKind::Crate,
  75         }
  76     }
  77
  78     #[inline]
  79     fn is_absolute(&self) -> bool {
  80         self == &PrefixKind::ByCrate
  81     }
  82 }
  83
  84 /// Attempts to find a path to refer to the given `item` visible from the `from` ModuleId
  85 fn find_path_inner(
  86     db: &dyn DefDatabase,
  87     item: ItemInNs,
  88     from: ModuleId,
  89     prefixed: Option<PrefixKind>,
  90     prefer_no_std: bool,
  91 ) -> Option<ModPath> {
  92     // - if the item is a builtin, it's in scope
  93     if let ItemInNs::Types(ModuleDefId::BuiltinType(builtin)) = item {
  94         return Some(ModPath::from_segments(PathKind::Plain, Some(builtin.as_name())));
  95     }
  96
  97     let def_map = from.def_map(db);
  98     let crate_root = def_map.crate_root();
  99     // - if the item is a module, jump straight to module search
 100     if let ItemInNs::Types(ModuleDefId::ModuleId(module_id)) = item {
 101         let mut visited_modules = FxHashSet::default();
 102         return find_path_for_module(
 103             db,
 104             &def_map,
 105             &mut visited_modules,
 106             crate_root,
 107             from,
 108             module_id,
 109             MAX_PATH_LEN,
 110             prefixed,
 111             prefer_no_std || db.crate_supports_no_std(crate_root.krate),
 112         )
 113         .map(|(item, _)| item);
 114     }
 115
 116     // - if the item is already in scope, return the name under which it is
 117     let scope_name = find_in_scope(db, &def_map, from, item);
 118     if prefixed.is_none() {
 119         if let Some(scope_name) = scope_name {
 120             return Some(ModPath::from_segments(PathKind::Plain, Some(scope_name)));
 121         }
 122     }
 123
 124     // - if the item is in the prelude, return the name from there
 125     if let value @ Some(_) = find_in_prelude(db, &crate_root.def_map(db), &def_map, item, from) {
 126         return value;
 127     }
 128
 129     if let Some(ModuleDefId::EnumVariantId(variant)) = item.as_module_def_id() {
 130         // - if the item is an enum variant, refer to it via the enum
 131         if let Some(mut path) = find_path_inner(
 132             db,
 133             ItemInNs::Types(variant.parent.into()),
 134             from,
 135             prefixed,
 136             prefer_no_std,
 137         ) {
 138             let data = db.enum_data(variant.parent);
 139             path.push_segment(data.variants[variant.local_id].name.clone());
 140             return Some(path);
 141         }
 142         // If this doesn't work, it seems we have no way of referring to the
 143         // enum; that's very weird, but there might still be a reexport of the
 144         // variant somewhere
 145     }
 146
 147     let mut visited_modules = FxHashSet::default();
 148
 149     calculate_best_path(
 150         db,
 151         &def_map,
 152         &mut visited_modules,
 153         crate_root,
 154         MAX_PATH_LEN,
 155         item,
 156         from,
 157         prefixed,
 158         prefer_no_std || db.crate_supports_no_std(crate_root.krate),
 159         scope_name,
 160     )
 161     .map(|(item, _)| item)
 162 }
 163
 164 fn find_path_for_module(
 165     db: &dyn DefDatabase,
 166     def_map: &DefMap,
 167     visited_modules: &mut FxHashSet<ModuleId>,
 168     crate_root: CrateRootModuleId,
 169     from: ModuleId,
 170     module_id: ModuleId,
 171     max_len: usize,
 172     prefixed: Option<PrefixKind>,
 173     prefer_no_std: bool,
 174 ) -> Option<(ModPath, Stability)> {
 175     if max_len == 0 {
 176         return None;
 177     }
 178
 179     // Base cases:
 180     // - if the item is already in scope, return the name under which it is
 181     let scope_name = find_in_scope(db, def_map, from, ItemInNs::Types(module_id.into()));
 182     if prefixed.is_none() {
 183         if let Some(scope_name) = scope_name {
 184             return Some((ModPath::from_segments(PathKind::Plain, Some(scope_name)), Stable));
 185         }
 186     }
 187
 188     // - if the item is the crate root, return `crate`
 189     if module_id == crate_root {
 190         return Some((ModPath::from_segments(PathKind::Crate, None), Stable));
 191     }
 192
 193     // - if relative paths are fine, check if we are searching for a parent
 194     if prefixed.filter(PrefixKind::is_absolute).is_none() {
 195         if let modpath @ Some(_) = find_self_super(def_map, module_id, from) {
 196             return modpath.zip(Some(Stable));
 197         }
 198     }
 199
 200     // - if the item is the crate root of a dependency crate, return the name from the extern prelude
 201     let root_def_map = crate_root.def_map(db);
 202     for (name, (def_id, _extern_crate)) in root_def_map.extern_prelude() {
 203         if module_id == def_id {
 204             let name = scope_name.unwrap_or_else(|| name.clone());
 205
 206             let name_already_occupied_in_type_ns = def_map
 207                 .with_ancestor_maps(db, from.local_id, &mut |def_map, local_id| {
 208                     def_map[local_id]
 209                         .scope
 210                         .type_(&name)
 211                         .filter(|&(id, _)| id != ModuleDefId::ModuleId(def_id.into()))
 212                 })
 213                 .is_some();
 214             let kind = if name_already_occupied_in_type_ns {
 215                 cov_mark::hit!(ambiguous_crate_start);
 216                 PathKind::Abs
 217             } else {
 218                 PathKind::Plain
 219             };
 220             return Some((ModPath::from_segments(kind, Some(name)), Stable));
 221         }
 222     }
 223
 224     if let value @ Some(_) =
 225         find_in_prelude(db, &root_def_map, &def_map, ItemInNs::Types(module_id.into()), from)
 226     {
 227         return value.zip(Some(Stable));
 228     }
 229     calculate_best_path(
 230         db,
 231         def_map,
 232         visited_modules,
 233         crate_root,
 234         max_len,
 235         ItemInNs::Types(module_id.into()),
 236         from,
 237         prefixed,
 238         prefer_no_std,
 239         scope_name,
 240     )
 241 }
 242
 243 // FIXME: Do we still need this now that we record import origins, and hence aliases?
 244 fn find_in_scope(
 245     db: &dyn DefDatabase,
 246     def_map: &DefMap,
 247     from: ModuleId,
 248     item: ItemInNs,
 249 ) -> Option<Name> {
 250     def_map.with_ancestor_maps(db, from.local_id, &mut |def_map, local_id| {
 251         def_map[local_id].scope.name_of(item).map(|(name, _)| name.clone())
 252     })
 253 }
 254
 255 /// Returns single-segment path (i.e. without any prefix) if `item` is found in prelude and its
 256 /// name doesn't clash in current scope.
 257 fn find_in_prelude(
 258     db: &dyn DefDatabase,
 259     root_def_map: &DefMap,
 260     local_def_map: &DefMap,
 261     item: ItemInNs,
 262     from: ModuleId,
 263 ) -> Option<ModPath> {
 264     let (prelude_module, _) = root_def_map.prelude()?;
 265     // Preludes in block DefMaps are ignored, only the crate DefMap is searched
 266     let prelude_def_map = prelude_module.def_map(db);
 267     let prelude_scope = &prelude_def_map[prelude_module.local_id].scope;
 268     let (name, vis) = prelude_scope.name_of(item)?;
 269     if !vis.is_visible_from(db, from) {
 270         return None;
 271     }
 272
 273     // Check if the name is in current scope and it points to the same def.
 274     let found_and_same_def =
 275         local_def_map.with_ancestor_maps(db, from.local_id, &mut |def_map, local_id| {
 276             let per_ns = def_map[local_id].scope.get(name);
 277             let same_def = match item {
 278                 ItemInNs::Types(it) => per_ns.take_types()? == it,
 279                 ItemInNs::Values(it) => per_ns.take_values()? == it,
 280                 ItemInNs::Macros(it) => per_ns.take_macros()? == it,
 281             };
 282             Some(same_def)
 283         });
 284
 285     if found_and_same_def.unwrap_or(true) {
 286         Some(ModPath::from_segments(PathKind::Plain, Some(name.clone())))
 287     } else {
 288         None
 289     }
 290 }
 291
 292 fn find_self_super(def_map: &DefMap, item: ModuleId, from: ModuleId) -> Option<ModPath> {
 293     if item == from {
 294         // - if the item is the module we're in, use `self`
 295         Some(ModPath::from_segments(PathKind::Super(0), None))
 296     } else if let Some(parent_id) = def_map[from.local_id].parent {
 297         // - if the item is the parent module, use `super` (this is not used recursively, since `super::super` is ugly)
 298         let parent_id = def_map.module_id(parent_id);
 299         if item == parent_id {
 300             Some(ModPath::from_segments(PathKind::Super(1), None))
 301         } else {
 302             None
 303         }
 304     } else {
 305         None
 306     }
 307 }
 308
 309 fn calculate_best_path(
 310     db: &dyn DefDatabase,
 311     def_map: &DefMap,
 312     visited_modules: &mut FxHashSet<ModuleId>,
 313     crate_root: CrateRootModuleId,
 314     max_len: usize,
 315     item: ItemInNs,
 316     from: ModuleId,
 317     mut prefixed: Option<PrefixKind>,
 318     prefer_no_std: bool,
 319     scope_name: Option<Name>,
 320 ) -> Option<(ModPath, Stability)> {
 321     if max_len <= 1 {
 322         return None;
 323     }
 324     let mut best_path = None;
 325     let update_best_path =
 326         |best_path: &mut Option<_>, new_path: (ModPath, Stability)| match best_path {
 327             Some((old_path, old_stability)) => {
 328                 *old_path = new_path.0;
 329                 *old_stability = zip_stability(*old_stability, new_path.1);
 330             }
 331             None => *best_path = Some(new_path),
 332         };
 333     // Recursive case:
 334     // - otherwise, look for modules containing (reexporting) it and import it from one of those
 335     if item.krate(db) == Some(from.krate) {
 336         let mut best_path_len = max_len;
 337         // Item was defined in the same crate that wants to import it. It cannot be found in any
 338         // dependency in this case.
 339         for (module_id, name) in find_local_import_locations(db, item, from) {
 340             if !visited_modules.insert(module_id) {
 341                 cov_mark::hit!(recursive_imports);
 342                 continue;
 343             }
 344             if let Some(mut path) = find_path_for_module(
 345                 db,
 346                 def_map,
 347                 visited_modules,
 348                 crate_root,
 349                 from,
 350                 module_id,
 351                 best_path_len - 1,
 352                 prefixed,
 353                 prefer_no_std,
 354             ) {
 355                 path.0.push_segment(name);
 356
 357                 let new_path = match best_path.take() {
 358                     Some(best_path) => select_best_path(best_path, path, prefer_no_std),
 359                     None => path,
 360                 };
 361                 best_path_len = new_path.0.len();
 362                 update_best_path(&mut best_path, new_path);
 363             }
 364         }
 365     } else {
 366         // Item was defined in some upstream crate. This means that it must be exported from one,
 367         // too (unless we can't name it at all). It could *also* be (re)exported by the same crate
 368         // that wants to import it here, but we always prefer to use the external path here.
 369
 370         let crate_graph = db.crate_graph();
 371         let extern_paths = crate_graph[from.krate].dependencies.iter().filter_map(|dep| {
 372             let import_map = db.import_map(dep.crate_id);
 373             import_map.import_info_for(item).and_then(|info| {
 374                 if info.is_doc_hidden {
 375                     // the item or import is `#[doc(hidden)]`, so skip it as it is in an external crate
 376                     return None;
 377                 }
 378
 379                 // Determine best path for containing module and append last segment from `info`.
 380                 // FIXME: we should guide this to look up the path locally, or from the same crate again?
 381                 let (mut path, path_stability) = find_path_for_module(
 382                     db,
 383                     def_map,
 384                     visited_modules,
 385                     crate_root,
 386                     from,
 387                     info.container,
 388                     max_len - 1,
 389                     prefixed,
 390                     prefer_no_std,
 391                 )?;
 392                 cov_mark::hit!(partially_imported);
 393                 path.push_segment(info.name.clone());
 394                 Some((
 395                     path,
 396                     zip_stability(path_stability, if info.is_unstable { Unstable } else { Stable }),
 397                 ))
 398             })
 399         });
 400
 401         for path in extern_paths {
 402             let new_path = match best_path.take() {
 403                 Some(best_path) => select_best_path(best_path, path, prefer_no_std),
 404                 None => path,
 405             };
 406             update_best_path(&mut best_path, new_path);
 407         }
 408     }
 409     if let Some(module) = item.module(db) {
 410         if module.containing_block().is_some() && prefixed.is_some() {
 411             cov_mark::hit!(prefixed_in_block_expression);
 412             prefixed = Some(PrefixKind::Plain);
 413         }
 414     }
 415     match prefixed.map(PrefixKind::prefix) {
 416         Some(prefix) => best_path.or_else(|| {
 417             scope_name.map(|scope_name| (ModPath::from_segments(prefix, Some(scope_name)), Stable))
 418         }),
 419         None => best_path,
 420     }
 421 }
 422
 423 fn select_best_path(
 424     old_path: (ModPath, Stability),
 425     new_path: (ModPath, Stability),
 426     prefer_no_std: bool,
 427 ) -> (ModPath, Stability) {
 428     match (old_path.1, new_path.1) {
 429         (Stable, Unstable) => return old_path,
 430         (Unstable, Stable) => return new_path,
 431         _ => {}
 432     }
 433     const STD_CRATES: [Name; 3] = [known::std, known::core, known::alloc];
 434     match (old_path.0.segments().first(), new_path.0.segments().first()) {
 435         (Some(old), Some(new)) if STD_CRATES.contains(old) && STD_CRATES.contains(new) => {
 436             let rank = match prefer_no_std {
 437                 false => |name: &Name| match name {
 438                     name if name == &known::core => 0,
 439                     name if name == &known::alloc => 0,
 440                     name if name == &known::std => 1,
 441                     _ => unreachable!(),
 442                 },
 443                 true => |name: &Name| match name {
 444                     name if name == &known::core => 2,
 445                     name if name == &known::alloc => 1,
 446                     name if name == &known::std => 0,
 447                     _ => unreachable!(),
 448                 },
 449             };
 450             let nrank = rank(new);
 451             let orank = rank(old);
 452             match nrank.cmp(&orank) {
 453                 Ordering::Less => old_path,
 454                 Ordering::Equal => {
 455                     if new_path.0.len() < old_path.0.len() {
 456                         new_path
 457                     } else {
 458                         old_path
 459                     }
 460                 }
 461                 Ordering::Greater => new_path,
 462             }
 463         }
 464         _ => {
 465             if new_path.0.len() < old_path.0.len() {
 466                 new_path
 467             } else {
 468                 old_path
 469             }
 470         }
 471     }
 472 }
 473
 474 // FIXME: Remove allocations
 475 /// Finds locations in `from.krate` from which `item` can be imported by `from`.
 476 fn find_local_import_locations(
 477     db: &dyn DefDatabase,
 478     item: ItemInNs,
 479     from: ModuleId,
 480 ) -> Vec<(ModuleId, Name)> {
 481     let _p = profile::span("find_local_import_locations");
 482
 483     // `from` can import anything below `from` with visibility of at least `from`, and anything
 484     // above `from` with any visibility. That means we do not need to descend into private siblings
 485     // of `from` (and similar).
 486
 487     let def_map = from.def_map(db);
 488
 489     // Compute the initial worklist. We start with all direct child modules of `from` as well as all
 490     // of its (recursive) parent modules.
 491     let data = &def_map[from.local_id];
 492     let mut worklist =
 493         data.children.values().map(|child| def_map.module_id(*child)).collect::<Vec<_>>();
 494     // FIXME: do we need to traverse out of block expressions here?
 495     for ancestor in iter::successors(from.containing_module(db), |m| m.containing_module(db)) {
 496         worklist.push(ancestor);
 497     }
 498
 499     let def_map = def_map.crate_root().def_map(db);
 500
 501     let mut seen: FxHashSet<_> = FxHashSet::default();
 502
 503     let mut locations = Vec::new();
 504     while let Some(module) = worklist.pop() {
 505         if !seen.insert(module) {
 506             continue; // already processed this module
 507         }
 508
 509         let ext_def_map;
 510         let data = if module.krate == from.krate {
 511             if module.block.is_some() {
 512                 // Re-query the block's DefMap
 513                 ext_def_map = module.def_map(db);
 514                 &ext_def_map[module.local_id]
 515             } else {
 516                 // Reuse the root DefMap
 517                 &def_map[module.local_id]
 518             }
 519         } else {
 520             // The crate might reexport a module defined in another crate.
 521             ext_def_map = module.def_map(db);
 522             &ext_def_map[module.local_id]
 523         };
 524
 525         if let Some((name, vis)) = data.scope.name_of(item) {
 526             if vis.is_visible_from(db, from) {
 527                 let is_private = match vis {
 528                     Visibility::Module(private_to) => private_to.local_id == module.local_id,
 529                     Visibility::Public => false,
 530                 };
 531                 let is_original_def = match item.as_module_def_id() {
 532                     Some(module_def_id) => data.scope.declarations().any(|it| it == module_def_id),
 533                     None => false,
 534                 };
 535
 536                 // Ignore private imports. these could be used if we are
 537                 // in a submodule of this module, but that's usually not
 538                 // what the user wants; and if this module can import
 539                 // the item and we're a submodule of it, so can we.
 540                 // Also this keeps the cached data smaller.
 541                 if !is_private || is_original_def {
 542                     locations.push((module, name.clone()));
 543                 }
 544             }
 545         }
 546
 547         // Descend into all modules visible from `from`.
 548         for (ty, vis) in data.scope.types() {
 549             if let ModuleDefId::ModuleId(module) = ty {
 550                 if vis.is_visible_from(db, from) {
 551                     worklist.push(module);
 552                 }
 553             }
 554         }
 555     }
 556
 557     locations
 558 }
 559
 560 #[cfg(test)]
 561 mod tests {
 562     use base_db::fixture::WithFixture;
 563     use hir_expand::hygiene::Hygiene;
 564     use syntax::ast::AstNode;
 565
 566     use crate::test_db::TestDB;
 567
 568     use super::*;
 569
 570     /// `code` needs to contain a cursor marker; checks that `find_path` for the
 571     /// item the `path` refers to returns that same path when called from the
 572     /// module the cursor is in.
 573     fn check_found_path_(ra_fixture: &str, path: &str, prefix_kind: Option<PrefixKind>) {
 574         let (db, pos) = TestDB::with_position(ra_fixture);
 575         let module = db.module_at_position(pos);
 576         let parsed_path_file = syntax::SourceFile::parse(&format!("use {path};"));
 577         let ast_path =
 578             parsed_path_file.syntax_node().descendants().find_map(syntax::ast::Path::cast).unwrap();
 579         let mod_path = ModPath::from_src(&db, ast_path, &Hygiene::new_unhygienic()).unwrap();
 580
 581         let def_map = module.def_map(&db);
 582         let resolved = def_map
 583             .resolve_path(
 584                 &db,
 585                 module.local_id,
 586                 &mod_path,
 587                 crate::item_scope::BuiltinShadowMode::Module,
 588                 None,
 589             )
 590             .0
 591             .take_types()
 592             .unwrap();
 593
 594         let found_path =
 595             find_path_inner(&db, ItemInNs::Types(resolved), module, prefix_kind, false);
 596         assert_eq!(found_path, Some(mod_path), "{prefix_kind:?}");
 597     }
 598
 599     fn check_found_path(
 600         ra_fixture: &str,
 601         unprefixed: &str,
 602         prefixed: &str,
 603         absolute: &str,
 604         self_prefixed: &str,
 605     ) {
 606         check_found_path_(ra_fixture, unprefixed, None);
 607         check_found_path_(ra_fixture, prefixed, Some(PrefixKind::Plain));
 608         check_found_path_(ra_fixture, absolute, Some(PrefixKind::ByCrate));
 609         check_found_path_(ra_fixture, self_prefixed, Some(PrefixKind::BySelf));
 610     }
 611
 612     #[test]
 613     fn same_module() {
 614         check_found_path(
 615             r#"
 616 struct S;
 617 $0
 618         "#,
 619             "S",
 620             "S",
 621             "crate::S",
 622             "self::S",
 623         );
 624     }
 625
 626     #[test]
 627     fn enum_variant() {
 628         check_found_path(
 629             r#"
 630 enum E { A }
 631 $0
 632         "#,
 633             "E::A",
 634             "E::A",
 635             "crate::E::A",
 636             "self::E::A",
 637         );
 638     }
 639
 640     #[test]
 641     fn sub_module() {
 642         check_found_path(
 643             r#"
 644 mod foo {
 645     pub struct S;
 646 }
 647 $0
 648         "#,
 649             "foo::S",
 650             "foo::S",
 651             "crate::foo::S",
 652             "self::foo::S",
 653         );
 654     }
 655
 656     #[test]
 657     fn super_module() {
 658         check_found_path(
 659             r#"
 660 //- /main.rs
 661 mod foo;
 662 //- /foo.rs
 663 mod bar;
 664 struct S;
 665 //- /foo/bar.rs
 666 $0
 667         "#,
 668             "super::S",
 669             "super::S",
 670             "crate::foo::S",
 671             "super::S",
 672         );
 673     }
 674
 675     #[test]
 676     fn self_module() {
 677         check_found_path(
 678             r#"
 679 //- /main.rs
 680 mod foo;
 681 //- /foo.rs
 682 $0
 683         "#,
 684             "self",
 685             "self",
 686             "crate::foo",
 687             "self",
 688         );
 689     }
 690
 691     #[test]
 692     fn crate_root() {
 693         check_found_path(
 694             r#"
 695 //- /main.rs
 696 mod foo;
 697 //- /foo.rs
 698 $0
 699         "#,
 700             "crate",
 701             "crate",
 702             "crate",
 703             "crate",
 704         );
 705     }
 706
 707     #[test]
 708     fn same_crate() {
 709         check_found_path(
 710             r#"
 711 //- /main.rs
 712 mod foo;
 713 struct S;
 714 //- /foo.rs
 715 $0
 716         "#,
 717             "crate::S",
 718             "crate::S",
 719             "crate::S",
 720             "crate::S",
 721         );
 722     }
 723
 724     #[test]
 725     fn different_crate() {
 726         check_found_path(
 727             r#"
 728 //- /main.rs crate:main deps:std
 729 $0
 730 //- /std.rs crate:std
 731 pub struct S;
 732         "#,
 733             "std::S",
 734             "std::S",
 735             "std::S",
 736             "std::S",
 737         );
 738     }
 739
 740     #[test]
 741     fn different_crate_renamed() {
 742         check_found_path(
 743             r#"
 744 //- /main.rs crate:main deps:std
 745 extern crate std as std_renamed;
 746 $0
 747 //- /std.rs crate:std
 748 pub struct S;
 749         "#,
 750             "std_renamed::S",
 751             "std_renamed::S",
 752             "std_renamed::S",
 753             "std_renamed::S",
 754         );
 755     }
 756
 757     #[test]
 758     fn partially_imported() {
 759         cov_mark::check!(partially_imported);
 760         // Tests that short paths are used even for external items, when parts of the path are
 761         // already in scope.
 762         check_found_path(
 763             r#"
 764 //- /main.rs crate:main deps:syntax
 765
 766 use syntax::ast;
 767 $0
 768
 769 //- /lib.rs crate:syntax
 770 pub mod ast {
 771     pub enum ModuleItem {
 772         A, B, C,
 773     }
 774 }
 775         "#,
 776             "ast::ModuleItem",
 777             "syntax::ast::ModuleItem",
 778             "syntax::ast::ModuleItem",
 779             "syntax::ast::ModuleItem",
 780         );
 781
 782         check_found_path(
 783             r#"
 784 //- /main.rs crate:main deps:syntax
 785 $0
 786
 787 //- /lib.rs crate:syntax
 788 pub mod ast {
 789     pub enum ModuleItem {
 790         A, B, C,
 791     }
 792 }
 793         "#,
 794             "syntax::ast::ModuleItem",
 795             "syntax::ast::ModuleItem",
 796             "syntax::ast::ModuleItem",
 797             "syntax::ast::ModuleItem",
 798         );
 799     }
 800
 801     #[test]
 802     fn same_crate_reexport() {
 803         check_found_path(
 804             r#"
 805 mod bar {
 806     mod foo { pub(super) struct S; }
 807     pub(crate) use foo::*;
 808 }
 809 $0
 810         "#,
 811             "bar::S",
 812             "bar::S",
 813             "crate::bar::S",
 814             "self::bar::S",
 815         );
 816     }
 817
 818     #[test]
 819     fn same_crate_reexport_rename() {
 820         check_found_path(
 821             r#"
 822 mod bar {
 823     mod foo { pub(super) struct S; }
 824     pub(crate) use foo::S as U;
 825 }
 826 $0
 827         "#,
 828             "bar::U",
 829             "bar::U",
 830             "crate::bar::U",
 831             "self::bar::U",
 832         );
 833     }
 834
 835     #[test]
 836     fn different_crate_reexport() {
 837         check_found_path(
 838             r#"
 839 //- /main.rs crate:main deps:std
 840 $0
 841 //- /std.rs crate:std deps:core
 842 pub use core::S;
 843 //- /core.rs crate:core
 844 pub struct S;
 845         "#,
 846             "std::S",
 847             "std::S",
 848             "std::S",
 849             "std::S",
 850         );
 851     }
 852
 853     #[test]
 854     fn prelude() {
 855         check_found_path(
 856             r#"
 857 //- /main.rs edition:2018 crate:main deps:std
 858 $0
 859 //- /std.rs crate:std
 860 pub mod prelude {
 861     pub mod rust_2018 {
 862         pub struct S;
 863     }
 864 }
 865         "#,
 866             "S",
 867             "S",
 868             "S",
 869             "S",
 870         );
 871     }
 872
 873     #[test]
 874     fn shadowed_prelude() {
 875         check_found_path(
 876             r#"
 877 //- /main.rs crate:main deps:std
 878 struct S;
 879 $0
 880 //- /std.rs crate:std
 881 pub mod prelude {
 882     pub mod rust_2018 {
 883         pub struct S;
 884     }
 885 }
 886 "#,
 887             "std::prelude::rust_2018::S",
 888             "std::prelude::rust_2018::S",
 889             "std::prelude::rust_2018::S",
 890             "std::prelude::rust_2018::S",
 891         );
 892     }
 893
 894     #[test]
 895     fn imported_prelude() {
 896         check_found_path(
 897             r#"
 898 //- /main.rs edition:2018 crate:main deps:std
 899 use S;
 900 $0
 901 //- /std.rs crate:std
 902 pub mod prelude {
 903     pub mod rust_2018 {
 904         pub struct S;
 905     }
 906 }
 907 "#,
 908             "S",
 909             "S",
 910             "S",
 911             "S",
 912         );
 913     }
 914
 915     #[test]
 916     fn enum_variant_from_prelude() {
 917         let code = r#"
 918 //- /main.rs edition:2018 crate:main deps:std
 919 $0
 920 //- /std.rs crate:std
 921 pub mod prelude {
 922     pub mod rust_2018 {
 923         pub enum Option<T> { Some(T), None }
 924         pub use Option::*;
 925     }
 926 }
 927         "#;
 928         check_found_path(code, "None", "None", "None", "None");
 929         check_found_path(code, "Some", "Some", "Some", "Some");
 930     }
 931
 932     #[test]
 933     fn shortest_path() {
 934         check_found_path(
 935             r#"
 936 //- /main.rs
 937 pub mod foo;
 938 pub mod baz;
 939 struct S;
 940 $0
 941 //- /foo.rs
 942 pub mod bar { pub struct S; }
 943 //- /baz.rs
 944 pub use crate::foo::bar::S;
 945         "#,
 946             "baz::S",
 947             "baz::S",
 948             "crate::baz::S",
 949             "self::baz::S",
 950         );
 951     }
 952
 953     #[test]
 954     fn discount_private_imports() {
 955         check_found_path(
 956             r#"
 957 //- /main.rs
 958 mod foo;
 959 pub mod bar { pub struct S; }
 960 use bar::S;
 961 //- /foo.rs
 962 $0
 963         "#,
 964             // crate::S would be shorter, but using private imports seems wrong
 965             "crate::bar::S",
 966             "crate::bar::S",
 967             "crate::bar::S",
 968             "crate::bar::S",
 969         );
 970     }
 971
 972     #[test]
 973     fn import_cycle() {
 974         check_found_path(
 975             r#"
 976 //- /main.rs
 977 pub mod foo;
 978 pub mod bar;
 979 pub mod baz;
 980 //- /bar.rs
 981 $0
 982 //- /foo.rs
 983 pub use super::baz;
 984 pub struct S;
 985 //- /baz.rs
 986 pub use super::foo;
 987         "#,
 988             "crate::foo::S",
 989             "crate::foo::S",
 990             "crate::foo::S",
 991             "crate::foo::S",
 992         );
 993     }
 994
 995     #[test]
 996     fn prefer_std_paths_over_alloc() {
 997         check_found_path(
 998             r#"
 999 //- /main.rs crate:main deps:alloc,std
1000 $0
1001
1002 //- /std.rs crate:std deps:alloc
1003 pub mod sync {
1004     pub use alloc::sync::Arc;
1005 }
1006
1007 //- /zzz.rs crate:alloc
1008 pub mod sync {
1009     pub struct Arc;
1010 }
1011         "#,
1012             "std::sync::Arc",
1013             "std::sync::Arc",
1014             "std::sync::Arc",
1015             "std::sync::Arc",
1016         );
1017     }
1018
1019     #[test]
1020     fn prefer_core_paths_over_std() {
1021         check_found_path(
1022             r#"
1023 //- /main.rs crate:main deps:core,std
1024 #![no_std]
1025
1026 $0
1027
1028 //- /std.rs crate:std deps:core
1029
1030 pub mod fmt {
1031     pub use core::fmt::Error;
1032 }
1033
1034 //- /zzz.rs crate:core
1035
1036 pub mod fmt {
1037     pub struct Error;
1038 }
1039         "#,
1040             "core::fmt::Error",
1041             "core::fmt::Error",
1042             "core::fmt::Error",
1043             "core::fmt::Error",
1044         );
1045
1046         // Should also work (on a best-effort basis) if `no_std` is conditional.
1047         check_found_path(
1048             r#"
1049 //- /main.rs crate:main deps:core,std
1050 #![cfg_attr(not(test), no_std)]
1051
1052 $0
1053
1054 //- /std.rs crate:std deps:core
1055
1056 pub mod fmt {
1057     pub use core::fmt::Error;
1058 }
1059
1060 //- /zzz.rs crate:core
1061
1062 pub mod fmt {
1063     pub struct Error;
1064 }
1065         "#,
1066             "core::fmt::Error",
1067             "core::fmt::Error",
1068             "core::fmt::Error",
1069             "core::fmt::Error",
1070         );
1071     }
1072
1073     #[test]
1074     fn prefer_alloc_paths_over_std() {
1075         check_found_path(
1076             r#"
1077 //- /main.rs crate:main deps:alloc,std
1078 #![no_std]
1079
1080 $0
1081
1082 //- /std.rs crate:std deps:alloc
1083
1084 pub mod sync {
1085     pub use alloc::sync::Arc;
1086 }
1087
1088 //- /zzz.rs crate:alloc
1089
1090 pub mod sync {
1091     pub struct Arc;
1092 }
1093             "#,
1094             "alloc::sync::Arc",
1095             "alloc::sync::Arc",
1096             "alloc::sync::Arc",
1097             "alloc::sync::Arc",
1098         );
1099     }
1100
1101     #[test]
1102     fn prefer_shorter_paths_if_not_alloc() {
1103         check_found_path(
1104             r#"
1105 //- /main.rs crate:main deps:megaalloc,std
1106 $0
1107
1108 //- /std.rs crate:std deps:megaalloc
1109 pub mod sync {
1110     pub use megaalloc::sync::Arc;
1111 }
1112
1113 //- /zzz.rs crate:megaalloc
1114 pub struct Arc;
1115             "#,
1116             "megaalloc::Arc",
1117             "megaalloc::Arc",
1118             "megaalloc::Arc",
1119             "megaalloc::Arc",
1120         );
1121     }
1122
1123     #[test]
1124     fn builtins_are_in_scope() {
1125         let code = r#"
1126 $0
1127
1128 pub mod primitive {
1129     pub use u8;
1130 }
1131         "#;
1132         check_found_path(code, "u8", "u8", "u8", "u8");
1133         check_found_path(code, "u16", "u16", "u16", "u16");
1134     }
1135
1136     #[test]
1137     fn inner_items() {
1138         check_found_path(
1139             r#"
1140 fn main() {
1141     struct Inner {}
1142     $0
1143 }
1144         "#,
1145             "Inner",
1146             "Inner",
1147             "Inner",
1148             "Inner",
1149         );
1150     }
1151
1152     #[test]
1153     fn inner_items_from_outer_scope() {
1154         check_found_path(
1155             r#"
1156 fn main() {
1157     struct Struct {}
1158     {
1159         $0
1160     }
1161 }
1162         "#,
1163             "Struct",
1164             "Struct",
1165             "Struct",
1166             "Struct",
1167         );
1168     }
1169
1170     #[test]
1171     fn inner_items_from_inner_module() {
1172         cov_mark::check!(prefixed_in_block_expression);
1173         check_found_path(
1174             r#"
1175 fn main() {
1176     mod module {
1177         struct Struct {}
1178     }
1179     {
1180         $0
1181     }
1182 }
1183         "#,
1184             "module::Struct",
1185             "module::Struct",
1186             "module::Struct",
1187             "module::Struct",
1188         );
1189     }
1190
1191     #[test]
1192     fn outer_items_with_inner_items_present() {
1193         check_found_path(
1194             r#"
1195 mod module {
1196     pub struct CompleteMe;
1197 }
1198
1199 fn main() {
1200     fn inner() {}
1201     $0
1202 }
1203             "#,
1204             // FIXME: these could use fewer/better prefixes
1205             "module::CompleteMe",
1206             "crate::module::CompleteMe",
1207             "crate::module::CompleteMe",
1208             "crate::module::CompleteMe",
1209         )
1210     }
1211
1212     #[test]
1213     fn from_inside_module() {
1214         // This worked correctly, but the test suite logic was broken.
1215         cov_mark::check!(submodule_in_testdb);
1216         check_found_path(
1217             r#"
1218 mod baz {
1219     pub struct Foo {}
1220 }
1221
1222 mod bar {
1223     fn bar() {
1224         $0
1225     }
1226 }
1227             "#,
1228             "crate::baz::Foo",
1229             "crate::baz::Foo",
1230             "crate::baz::Foo",
1231             "crate::baz::Foo",
1232         )
1233     }
1234
1235     #[test]
1236     fn from_inside_module_with_inner_items() {
1237         check_found_path(
1238             r#"
1239 mod baz {
1240     pub struct Foo {}
1241 }
1242
1243 mod bar {
1244     fn bar() {
1245         fn inner() {}
1246         $0
1247     }
1248 }
1249             "#,
1250             "crate::baz::Foo",
1251             "crate::baz::Foo",
1252             "crate::baz::Foo",
1253             "crate::baz::Foo",
1254         )
1255     }
1256
1257     #[test]
1258     fn recursive_pub_mod_reexport() {
1259         cov_mark::check!(recursive_imports);
1260         check_found_path(
1261             r#"
1262 fn main() {
1263     let _ = 22_i32.as_name$0();
1264 }
1265
1266 pub mod name {
1267     pub trait AsName {
1268         fn as_name(&self) -> String;
1269     }
1270     impl AsName for i32 {
1271         fn as_name(&self) -> String {
1272             format!("Name: {}", self)
1273         }
1274     }
1275     pub use crate::name;
1276 }
1277 "#,
1278             "name::AsName",
1279             "name::AsName",
1280             "crate::name::AsName",
1281             "self::name::AsName",
1282         );
1283     }
1284
1285     #[test]
1286     fn extern_crate() {
1287         check_found_path(
1288             r#"
1289 //- /main.rs crate:main deps:dep
1290 $0
1291 //- /dep.rs crate:dep
1292 "#,
1293             "dep",
1294             "dep",
1295             "dep",
1296             "dep",
1297         );
1298
1299         check_found_path(
1300             r#"
1301 //- /main.rs crate:main deps:dep
1302 fn f() {
1303     fn inner() {}
1304     $0
1305 }
1306 //- /dep.rs crate:dep
1307 "#,
1308             "dep",
1309             "dep",
1310             "dep",
1311             "dep",
1312         );
1313     }
1314
1315     #[test]
1316     fn prelude_with_inner_items() {
1317         check_found_path(
1318             r#"
1319 //- /main.rs edition:2018 crate:main deps:std
1320 fn f() {
1321     fn inner() {}
1322     $0
1323 }
1324 //- /std.rs crate:std
1325 pub mod prelude {
1326     pub mod rust_2018 {
1327         pub enum Option { None }
1328         pub use Option::*;
1329     }
1330 }
1331         "#,
1332             "None",
1333             "None",
1334             "None",
1335             "None",
1336         );
1337     }
1338
1339     #[test]
1340     fn different_crate_renamed_through_dep() {
1341         check_found_path(
1342             r#"
1343 //- /main.rs crate:main deps:intermediate
1344 $0
1345 //- /intermediate.rs crate:intermediate deps:std
1346 pub extern crate std as std_renamed;
1347 //- /std.rs crate:std
1348 pub struct S;
1349     "#,
1350             "intermediate::std_renamed::S",
1351             "intermediate::std_renamed::S",
1352             "intermediate::std_renamed::S",
1353             "intermediate::std_renamed::S",
1354         );
1355     }
1356
1357     #[test]
1358     fn different_crate_doc_hidden() {
1359         check_found_path(
1360             r#"
1361 //- /main.rs crate:main deps:intermediate
1362 $0
1363 //- /intermediate.rs crate:intermediate deps:std
1364 #[doc(hidden)]
1365 pub extern crate std;
1366 pub extern crate std as longer;
1367 //- /std.rs crate:std
1368 pub struct S;
1369     "#,
1370             "intermediate::longer::S",
1371             "intermediate::longer::S",
1372             "intermediate::longer::S",
1373             "intermediate::longer::S",
1374         );
1375     }
1376
1377     #[test]
1378     fn respect_doc_hidden() {
1379         check_found_path(
1380             r#"
1381 //- /main.rs crate:main deps:std,lazy_static
1382 $0
1383 //- /lazy_static.rs crate:lazy_static deps:core
1384 #[doc(hidden)]
1385 pub use core::ops::Deref as __Deref;
1386 //- /std.rs crate:std deps:core
1387 pub use core::ops;
1388 //- /core.rs crate:core
1389 pub mod ops {
1390     pub trait Deref {}
1391 }
1392     "#,
1393             "std::ops::Deref",
1394             "std::ops::Deref",
1395             "std::ops::Deref",
1396             "std::ops::Deref",
1397         );
1398     }
1399
1400     #[test]
1401     fn respect_unstable_modules() {
1402         check_found_path(
1403             r#"
1404 //- /main.rs crate:main deps:std,core
1405 #![no_std]
1406 extern crate std;
1407 $0
1408 //- /longer.rs crate:std deps:core
1409 pub mod error {
1410     pub use core::error::Error;
1411 }
1412 //- /core.rs crate:core
1413 pub mod error {
1414     #![unstable(feature = "error_in_core", issue = "103765")]
1415     pub trait Error {}
1416 }
1417 "#,
1418             "std::error::Error",
1419             "std::error::Error",
1420             "std::error::Error",
1421             "std::error::Error",
1422         );
1423     }
1424 }