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