crates/ra_hir_def/src/find_path.rs

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