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

   1 //! A map of all publicly exported items in a crate.
   2
   3 use std::{fmt, hash::BuildHasherDefault};
   4
   5 use base_db::CrateId;
   6 use fst::{self, Streamer};
   7 use hir_expand::name::Name;
   8 use indexmap::{map::Entry, IndexMap};
   9 use itertools::Itertools;
  10 use rustc_hash::{FxHashSet, FxHasher};
  11 use triomphe::Arc;
  12
  13 use crate::{
  14     db::DefDatabase, item_scope::ItemInNs, nameres::DefMap, visibility::Visibility, AssocItemId,
  15     ModuleDefId, ModuleId, TraitId,
  16 };
  17
  18 type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<FxHasher>>;
  19
  20 /// Item import details stored in the `ImportMap`.
  21 #[derive(Debug, Clone, Eq, PartialEq)]
  22 pub struct ImportInfo {
  23     /// A path that can be used to import the item, relative to the crate's root.
  24     pub path: ImportPath,
  25     /// The module containing this item.
  26     pub container: ModuleId,
  27     /// Whether the import is a trait associated item or not.
  28     pub is_trait_assoc_item: bool,
  29 }
  30
  31 #[derive(Debug, Clone, Eq, PartialEq)]
  32 pub struct ImportPath {
  33     pub segments: Vec<Name>,
  34 }
  35
  36 impl ImportPath {
  37     pub fn display<'a>(&'a self, db: &'a dyn DefDatabase) -> impl fmt::Display + 'a {
  38         struct Display<'a> {
  39             db: &'a dyn DefDatabase,
  40             path: &'a ImportPath,
  41         }
  42         impl fmt::Display for Display<'_> {
  43             fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  44                 fmt::Display::fmt(
  45                     &self.path.segments.iter().map(|it| it.display(self.db.upcast())).format("::"),
  46                     f,
  47                 )
  48             }
  49         }
  50         Display { db, path: self }
  51     }
  52
  53     fn len(&self) -> usize {
  54         self.segments.len()
  55     }
  56 }
  57
  58 /// A map from publicly exported items to the path needed to import/name them from a downstream
  59 /// crate.
  60 ///
  61 /// Reexports of items are taken into account, ie. if something is exported under multiple
  62 /// names, the one with the shortest import path will be used.
  63 ///
  64 /// Note that all paths are relative to the containing crate's root, so the crate name still needs
  65 /// to be prepended to the `ModPath` before the path is valid.
  66 #[derive(Default)]
  67 pub struct ImportMap {
  68     map: FxIndexMap<ItemInNs, ImportInfo>,
  69
  70     /// List of keys stored in `map`, sorted lexicographically by their `ModPath`. Indexed by the
  71     /// values returned by running `fst`.
  72     ///
  73     /// Since a path can refer to multiple items due to namespacing, we store all items with the
  74     /// same path right after each other. This allows us to find all items after the FST gives us
  75     /// the index of the first one.
  76     importables: Vec<ItemInNs>,
  77     fst: fst::Map<Vec<u8>>,
  78 }
  79
  80 impl ImportMap {
  81     pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<Self> {
  82         let _p = profile::span("import_map_query");
  83
  84         let mut import_map = collect_import_map(db, krate);
  85
  86         let mut importables = import_map
  87             .map
  88             .iter()
  89             .map(|(item, info)| (item, fst_path(db, &info.path)))
  90             .collect::<Vec<_>>();
  91         importables.sort_by(|(_, fst_path), (_, fst_path2)| fst_path.cmp(fst_path2));
  92
  93         // Build the FST, taking care not to insert duplicate values.
  94
  95         let mut builder = fst::MapBuilder::memory();
  96         let mut last_batch_start = 0;
  97
  98         for idx in 0..importables.len() {
  99             let key = &importables[last_batch_start].1;
 100             if let Some((_, fst_path)) = importables.get(idx + 1) {
 101                 if key == fst_path {
 102                     continue;
 103                 }
 104             }
 105
 106             let _ = builder.insert(key, last_batch_start as u64);
 107
 108             last_batch_start = idx + 1;
 109         }
 110
 111         import_map.fst = builder.into_map();
 112         import_map.importables = importables.iter().map(|&(&item, _)| item).collect();
 113
 114         Arc::new(import_map)
 115     }
 116
 117     /// Returns the `ModPath` needed to import/mention `item`, relative to this crate's root.
 118     pub fn path_of(&self, item: ItemInNs) -> Option<&ImportPath> {
 119         self.import_info_for(item).map(|it| &it.path)
 120     }
 121
 122     pub fn import_info_for(&self, item: ItemInNs) -> Option<&ImportInfo> {
 123         self.map.get(&item)
 124     }
 125
 126     #[cfg(test)]
 127     fn fmt_for_test(&self, db: &dyn DefDatabase) -> String {
 128         let mut importable_paths: Vec<_> = self
 129             .map
 130             .iter()
 131             .map(|(item, info)| {
 132                 let ns = match item {
 133                     ItemInNs::Types(_) => "t",
 134                     ItemInNs::Values(_) => "v",
 135                     ItemInNs::Macros(_) => "m",
 136                 };
 137                 format!("- {} ({ns})", info.path.display(db))
 138             })
 139             .collect();
 140
 141         importable_paths.sort();
 142         importable_paths.join("\n")
 143     }
 144
 145     fn collect_trait_assoc_items(
 146         &mut self,
 147         db: &dyn DefDatabase,
 148         tr: TraitId,
 149         is_type_in_ns: bool,
 150         original_import_info: &ImportInfo,
 151     ) {
 152         let _p = profile::span("collect_trait_assoc_items");
 153         for (assoc_item_name, item) in &db.trait_data(tr).items {
 154             let module_def_id = match item {
 155                 AssocItemId::FunctionId(f) => ModuleDefId::from(*f),
 156                 AssocItemId::ConstId(c) => ModuleDefId::from(*c),
 157                 // cannot use associated type aliases directly: need a `<Struct as Trait>::TypeAlias`
 158                 // qualifier, ergo no need to store it for imports in import_map
 159                 AssocItemId::TypeAliasId(_) => {
 160                     cov_mark::hit!(type_aliases_ignored);
 161                     continue;
 162                 }
 163             };
 164             let assoc_item = if is_type_in_ns {
 165                 ItemInNs::Types(module_def_id)
 166             } else {
 167                 ItemInNs::Values(module_def_id)
 168             };
 169
 170             let mut assoc_item_info = original_import_info.clone();
 171             assoc_item_info.path.segments.push(assoc_item_name.to_owned());
 172             assoc_item_info.is_trait_assoc_item = true;
 173             self.map.insert(assoc_item, assoc_item_info);
 174         }
 175     }
 176 }
 177
 178 fn collect_import_map(db: &dyn DefDatabase, krate: CrateId) -> ImportMap {
 179     let _p = profile::span("collect_import_map");
 180
 181     let def_map = db.crate_def_map(krate);
 182     let mut import_map = ImportMap::default();
 183
 184     // We look only into modules that are public(ly reexported), starting with the crate root.
 185     let empty = ImportPath { segments: vec![] };
 186     let root = def_map.module_id(DefMap::ROOT);
 187     let mut worklist = vec![(root, empty)];
 188     while let Some((module, mod_path)) = worklist.pop() {
 189         let ext_def_map;
 190         let mod_data = if module.krate == krate {
 191             &def_map[module.local_id]
 192         } else {
 193             // The crate might reexport a module defined in another crate.
 194             ext_def_map = module.def_map(db);
 195             &ext_def_map[module.local_id]
 196         };
 197
 198         let visible_items = mod_data.scope.entries().filter_map(|(name, per_ns)| {
 199             let per_ns = per_ns.filter_visibility(|vis| vis == Visibility::Public);
 200             if per_ns.is_none() { None } else { Some((name, per_ns)) }
 201         });
 202
 203         for (name, per_ns) in visible_items {
 204             let mk_path = || {
 205                 let mut path = mod_path.clone();
 206                 path.segments.push(name.clone());
 207                 path
 208             };
 209
 210             for item in per_ns.iter_items() {
 211                 let path = mk_path();
 212                 let path_len = path.len();
 213                 let import_info =
 214                     ImportInfo { path, container: module, is_trait_assoc_item: false };
 215
 216                 if let Some(ModuleDefId::TraitId(tr)) = item.as_module_def_id() {
 217                     import_map.collect_trait_assoc_items(
 218                         db,
 219                         tr,
 220                         matches!(item, ItemInNs::Types(_)),
 221                         &import_info,
 222                     );
 223                 }
 224
 225                 match import_map.map.entry(item) {
 226                     Entry::Vacant(entry) => {
 227                         entry.insert(import_info);
 228                     }
 229                     Entry::Occupied(mut entry) => {
 230                         // If the new path is shorter, prefer that one.
 231                         if path_len < entry.get().path.len() {
 232                             *entry.get_mut() = import_info;
 233                         } else {
 234                             continue;
 235                         }
 236                     }
 237                 }
 238
 239                 // If we've just added a path to a module, descend into it. We might traverse
 240                 // modules multiple times, but only if the new path to it is shorter than the
 241                 // first (else we `continue` above).
 242                 if let Some(ModuleDefId::ModuleId(mod_id)) = item.as_module_def_id() {
 243                     worklist.push((mod_id, mk_path()));
 244                 }
 245             }
 246         }
 247     }
 248
 249     import_map
 250 }
 251
 252 impl PartialEq for ImportMap {
 253     fn eq(&self, other: &Self) -> bool {
 254         // `fst` and `importables` are built from `map`, so we don't need to compare them.
 255         self.map == other.map
 256     }
 257 }
 258
 259 impl Eq for ImportMap {}
 260
 261 impl fmt::Debug for ImportMap {
 262     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 263         let mut importable_paths: Vec<_> = self
 264             .map
 265             .iter()
 266             .map(|(item, _)| match item {
 267                 ItemInNs::Types(it) => format!("- {it:?} (t)",),
 268                 ItemInNs::Values(it) => format!("- {it:?} (v)",),
 269                 ItemInNs::Macros(it) => format!("- {it:?} (m)",),
 270             })
 271             .collect();
 272
 273         importable_paths.sort();
 274         f.write_str(&importable_paths.join("\n"))
 275     }
 276 }
 277
 278 fn fst_path(db: &dyn DefDatabase, path: &ImportPath) -> String {
 279     let _p = profile::span("fst_path");
 280     let mut s = path.display(db).to_string();
 281     s.make_ascii_lowercase();
 282     s
 283 }
 284
 285 #[derive(Debug, Eq, PartialEq, Hash)]
 286 pub enum ImportKind {
 287     Module,
 288     Function,
 289     Adt,
 290     EnumVariant,
 291     Const,
 292     Static,
 293     Trait,
 294     TraitAlias,
 295     TypeAlias,
 296     BuiltinType,
 297     AssociatedItem,
 298     Macro,
 299 }
 300
 301 /// A way to match import map contents against the search query.
 302 #[derive(Debug)]
 303 pub enum SearchMode {
 304     /// Import map entry should strictly match the query string.
 305     Equals,
 306     /// Import map entry should contain the query string.
 307     Contains,
 308     /// Import map entry should contain all letters from the query string,
 309     /// in the same order, but not necessary adjacent.
 310     Fuzzy,
 311 }
 312
 313 #[derive(Debug)]
 314 pub struct Query {
 315     query: String,
 316     lowercased: String,
 317     name_only: bool,
 318     assoc_items_only: bool,
 319     search_mode: SearchMode,
 320     case_sensitive: bool,
 321     limit: usize,
 322     exclude_import_kinds: FxHashSet<ImportKind>,
 323 }
 324
 325 impl Query {
 326     pub fn new(query: String) -> Self {
 327         let lowercased = query.to_lowercase();
 328         Self {
 329             query,
 330             lowercased,
 331             name_only: false,
 332             assoc_items_only: false,
 333             search_mode: SearchMode::Contains,
 334             case_sensitive: false,
 335             limit: usize::max_value(),
 336             exclude_import_kinds: FxHashSet::default(),
 337         }
 338     }
 339
 340     /// Matches entries' names only, ignoring the rest of
 341     /// the qualifier.
 342     /// Example: for `std::marker::PhantomData`, the name is `PhantomData`.
 343     pub fn name_only(self) -> Self {
 344         Self { name_only: true, ..self }
 345     }
 346
 347     /// Matches only the entries that are associated items, ignoring the rest.
 348     pub fn assoc_items_only(self) -> Self {
 349         Self { assoc_items_only: true, ..self }
 350     }
 351
 352     /// Specifies the way to search for the entries using the query.
 353     pub fn search_mode(self, search_mode: SearchMode) -> Self {
 354         Self { search_mode, ..self }
 355     }
 356
 357     /// Limits the returned number of items to `limit`.
 358     pub fn limit(self, limit: usize) -> Self {
 359         Self { limit, ..self }
 360     }
 361
 362     /// Respect casing of the query string when matching.
 363     pub fn case_sensitive(self) -> Self {
 364         Self { case_sensitive: true, ..self }
 365     }
 366
 367     /// Do not include imports of the specified kind in the search results.
 368     pub fn exclude_import_kind(mut self, import_kind: ImportKind) -> Self {
 369         self.exclude_import_kinds.insert(import_kind);
 370         self
 371     }
 372
 373     fn import_matches(
 374         &self,
 375         db: &dyn DefDatabase,
 376         import: &ImportInfo,
 377         enforce_lowercase: bool,
 378     ) -> bool {
 379         let _p = profile::span("import_map::Query::import_matches");
 380         if import.is_trait_assoc_item {
 381             if self.exclude_import_kinds.contains(&ImportKind::AssociatedItem) {
 382                 return false;
 383             }
 384         } else if self.assoc_items_only {
 385             return false;
 386         }
 387
 388         let mut input = if import.is_trait_assoc_item || self.name_only {
 389             import.path.segments.last().unwrap().display(db.upcast()).to_string()
 390         } else {
 391             import.path.display(db).to_string()
 392         };
 393         if enforce_lowercase || !self.case_sensitive {
 394             input.make_ascii_lowercase();
 395         }
 396
 397         let query_string =
 398             if !enforce_lowercase && self.case_sensitive { &self.query } else { &self.lowercased };
 399
 400         match self.search_mode {
 401             SearchMode::Equals => &input == query_string,
 402             SearchMode::Contains => input.contains(query_string),
 403             SearchMode::Fuzzy => {
 404                 let mut unchecked_query_chars = query_string.chars();
 405                 let mut mismatching_query_char = unchecked_query_chars.next();
 406
 407                 for input_char in input.chars() {
 408                     match mismatching_query_char {
 409                         None => return true,
 410                         Some(matching_query_char) if matching_query_char == input_char => {
 411                             mismatching_query_char = unchecked_query_chars.next();
 412                         }
 413                         _ => (),
 414                     }
 415                 }
 416                 mismatching_query_char.is_none()
 417             }
 418         }
 419     }
 420 }
 421
 422 /// Searches dependencies of `krate` for an importable path matching `query`.
 423 ///
 424 /// This returns a list of items that could be imported from dependencies of `krate`.
 425 pub fn search_dependencies(
 426     db: &dyn DefDatabase,
 427     krate: CrateId,
 428     query: Query,
 429 ) -> FxHashSet<ItemInNs> {
 430     let _p = profile::span("search_dependencies").detail(|| format!("{query:?}"));
 431
 432     let graph = db.crate_graph();
 433     let import_maps: Vec<_> =
 434         graph[krate].dependencies.iter().map(|dep| db.import_map(dep.crate_id)).collect();
 435
 436     let automaton = fst::automaton::Subsequence::new(&query.lowercased);
 437
 438     let mut op = fst::map::OpBuilder::new();
 439     for map in &import_maps {
 440         op = op.add(map.fst.search(&automaton));
 441     }
 442
 443     let mut stream = op.union();
 444
 445     let mut all_indexed_values = FxHashSet::default();
 446     while let Some((_, indexed_values)) = stream.next() {
 447         all_indexed_values.extend(indexed_values.iter().copied());
 448     }
 449
 450     let mut res = FxHashSet::default();
 451     for indexed_value in all_indexed_values {
 452         let import_map = &import_maps[indexed_value.index];
 453         let importables = &import_map.importables[indexed_value.value as usize..];
 454
 455         let common_importable_data = &import_map.map[&importables[0]];
 456         if !query.import_matches(db, common_importable_data, true) {
 457             continue;
 458         }
 459
 460         // Path shared by the importable items in this group.
 461         let common_importables_path_fst = fst_path(db, &common_importable_data.path);
 462         // Add the items from this `ModPath` group. Those are all subsequent items in
 463         // `importables` whose paths match `path`.
 464         let iter = importables
 465             .iter()
 466             .copied()
 467             .take_while(|item| {
 468                 common_importables_path_fst == fst_path(db, &import_map.map[item].path)
 469             })
 470             .filter(|&item| match item_import_kind(item) {
 471                 Some(import_kind) => !query.exclude_import_kinds.contains(&import_kind),
 472                 None => true,
 473             })
 474             .filter(|item| {
 475                 !query.case_sensitive // we've already checked the common importables path case-insensitively
 476                         || query.import_matches(db, &import_map.map[item], false)
 477             });
 478         res.extend(iter);
 479
 480         if res.len() >= query.limit {
 481             return res;
 482         }
 483     }
 484
 485     res
 486 }
 487
 488 fn item_import_kind(item: ItemInNs) -> Option<ImportKind> {
 489     Some(match item.as_module_def_id()? {
 490         ModuleDefId::ModuleId(_) => ImportKind::Module,
 491         ModuleDefId::FunctionId(_) => ImportKind::Function,
 492         ModuleDefId::AdtId(_) => ImportKind::Adt,
 493         ModuleDefId::EnumVariantId(_) => ImportKind::EnumVariant,
 494         ModuleDefId::ConstId(_) => ImportKind::Const,
 495         ModuleDefId::StaticId(_) => ImportKind::Static,
 496         ModuleDefId::TraitId(_) => ImportKind::Trait,
 497         ModuleDefId::TraitAliasId(_) => ImportKind::TraitAlias,
 498         ModuleDefId::TypeAliasId(_) => ImportKind::TypeAlias,
 499         ModuleDefId::BuiltinType(_) => ImportKind::BuiltinType,
 500         ModuleDefId::MacroId(_) => ImportKind::Macro,
 501     })
 502 }
 503
 504 #[cfg(test)]
 505 mod tests {
 506     use base_db::{fixture::WithFixture, SourceDatabase, Upcast};
 507     use expect_test::{expect, Expect};
 508
 509     use crate::{db::DefDatabase, test_db::TestDB, ItemContainerId, Lookup};
 510
 511     use super::*;
 512
 513     fn check_search(ra_fixture: &str, crate_name: &str, query: Query, expect: Expect) {
 514         let db = TestDB::with_files(ra_fixture);
 515         let crate_graph = db.crate_graph();
 516         let krate = crate_graph
 517             .iter()
 518             .find(|krate| {
 519                 crate_graph[*krate].display_name.as_ref().map(|n| n.to_string())
 520                     == Some(crate_name.to_string())
 521             })
 522             .unwrap();
 523
 524         let actual = search_dependencies(db.upcast(), krate, query)
 525             .into_iter()
 526             .filter_map(|dependency| {
 527                 let dependency_krate = dependency.krate(db.upcast())?;
 528                 let dependency_imports = db.import_map(dependency_krate);
 529
 530                 let (path, mark) = match assoc_item_path(&db, &dependency_imports, dependency) {
 531                     Some(assoc_item_path) => (assoc_item_path, "a"),
 532                     None => (
 533                         dependency_imports.path_of(dependency)?.display(&db).to_string(),
 534                         match dependency {
 535                             ItemInNs::Types(ModuleDefId::FunctionId(_))
 536                             | ItemInNs::Values(ModuleDefId::FunctionId(_)) => "f",
 537                             ItemInNs::Types(_) => "t",
 538                             ItemInNs::Values(_) => "v",
 539                             ItemInNs::Macros(_) => "m",
 540                         },
 541                     ),
 542                 };
 543
 544                 Some(format!(
 545                     "{}::{} ({})\n",
 546                     crate_graph[dependency_krate].display_name.as_ref()?,
 547                     path,
 548                     mark
 549                 ))
 550             })
 551             // HashSet iteration order isn't defined - it's different on
 552             // x86_64 and i686 at the very least
 553             .sorted()
 554             .collect::<String>();
 555         expect.assert_eq(&actual)
 556     }
 557
 558     fn assoc_item_path(
 559         db: &dyn DefDatabase,
 560         dependency_imports: &ImportMap,
 561         dependency: ItemInNs,
 562     ) -> Option<String> {
 563         let dependency_assoc_item_id = match dependency {
 564             ItemInNs::Types(ModuleDefId::FunctionId(id))
 565             | ItemInNs::Values(ModuleDefId::FunctionId(id)) => AssocItemId::from(id),
 566             ItemInNs::Types(ModuleDefId::ConstId(id))
 567             | ItemInNs::Values(ModuleDefId::ConstId(id)) => AssocItemId::from(id),
 568             ItemInNs::Types(ModuleDefId::TypeAliasId(id))
 569             | ItemInNs::Values(ModuleDefId::TypeAliasId(id)) => AssocItemId::from(id),
 570             _ => return None,
 571         };
 572
 573         let trait_ = assoc_to_trait(db, dependency)?;
 574         if let ModuleDefId::TraitId(tr) = trait_.as_module_def_id()? {
 575             let trait_data = db.trait_data(tr);
 576             let assoc_item_name =
 577                 trait_data.items.iter().find_map(|(assoc_item_name, assoc_item_id)| {
 578                     if &dependency_assoc_item_id == assoc_item_id {
 579                         Some(assoc_item_name)
 580                     } else {
 581                         None
 582                     }
 583                 })?;
 584             return Some(format!(
 585                 "{}::{}",
 586                 dependency_imports.path_of(trait_)?.display(db),
 587                 assoc_item_name.display(db.upcast())
 588             ));
 589         }
 590         None
 591     }
 592
 593     fn assoc_to_trait(db: &dyn DefDatabase, item: ItemInNs) -> Option<ItemInNs> {
 594         let assoc: AssocItemId = match item {
 595             ItemInNs::Types(it) | ItemInNs::Values(it) => match it {
 596                 ModuleDefId::TypeAliasId(it) => it.into(),
 597                 ModuleDefId::FunctionId(it) => it.into(),
 598                 ModuleDefId::ConstId(it) => it.into(),
 599                 _ => return None,
 600             },
 601             _ => return None,
 602         };
 603
 604         let container = match assoc {
 605             AssocItemId::FunctionId(it) => it.lookup(db).container,
 606             AssocItemId::ConstId(it) => it.lookup(db).container,
 607             AssocItemId::TypeAliasId(it) => it.lookup(db).container,
 608         };
 609
 610         match container {
 611             ItemContainerId::TraitId(it) => Some(ItemInNs::Types(it.into())),
 612             _ => None,
 613         }
 614     }
 615
 616     fn check(ra_fixture: &str, expect: Expect) {
 617         let db = TestDB::with_files(ra_fixture);
 618         let crate_graph = db.crate_graph();
 619
 620         let actual = crate_graph
 621             .iter()
 622             .filter_map(|krate| {
 623                 let cdata = &crate_graph[krate];
 624                 let name = cdata.display_name.as_ref()?;
 625
 626                 let map = db.import_map(krate);
 627
 628                 Some(format!("{name}:\n{}\n", map.fmt_for_test(db.upcast())))
 629             })
 630             .sorted()
 631             .collect::<String>();
 632
 633         expect.assert_eq(&actual)
 634     }
 635
 636     #[test]
 637     fn smoke() {
 638         check(
 639             r"
 640             //- /main.rs crate:main deps:lib
 641
 642             mod private {
 643                 pub use lib::Pub;
 644                 pub struct InPrivateModule;
 645             }
 646
 647             pub mod publ1 {
 648                 use lib::Pub;
 649             }
 650
 651             pub mod real_pub {
 652                 pub use lib::Pub;
 653             }
 654             pub mod real_pu2 { // same path length as above
 655                 pub use lib::Pub;
 656             }
 657
 658             //- /lib.rs crate:lib
 659             pub struct Pub {}
 660             pub struct Pub2; // t + v
 661             struct Priv;
 662         ",
 663             expect![[r#"
 664                 lib:
 665                 - Pub (t)
 666                 - Pub2 (t)
 667                 - Pub2 (v)
 668                 main:
 669                 - publ1 (t)
 670                 - real_pu2 (t)
 671                 - real_pub (t)
 672                 - real_pub::Pub (t)
 673             "#]],
 674         );
 675     }
 676
 677     #[test]
 678     fn prefers_shortest_path() {
 679         check(
 680             r"
 681             //- /main.rs crate:main
 682
 683             pub mod sub {
 684                 pub mod subsub {
 685                     pub struct Def {}
 686                 }
 687
 688                 pub use super::sub::subsub::Def;
 689             }
 690         ",
 691             expect![[r#"
 692                 main:
 693                 - sub (t)
 694                 - sub::Def (t)
 695                 - sub::subsub (t)
 696             "#]],
 697         );
 698     }
 699
 700     #[test]
 701     fn type_reexport_cross_crate() {
 702         // Reexports need to be visible from a crate, even if the original crate exports the item
 703         // at a shorter path.
 704         check(
 705             r"
 706             //- /main.rs crate:main deps:lib
 707             pub mod m {
 708                 pub use lib::S;
 709             }
 710             //- /lib.rs crate:lib
 711             pub struct S;
 712         ",
 713             expect![[r#"
 714                 lib:
 715                 - S (t)
 716                 - S (v)
 717                 main:
 718                 - m (t)
 719                 - m::S (t)
 720                 - m::S (v)
 721             "#]],
 722         );
 723     }
 724
 725     #[test]
 726     fn macro_reexport() {
 727         check(
 728             r"
 729             //- /main.rs crate:main deps:lib
 730             pub mod m {
 731                 pub use lib::pub_macro;
 732             }
 733             //- /lib.rs crate:lib
 734             #[macro_export]
 735             macro_rules! pub_macro {
 736                 () => {};
 737             }
 738         ",
 739             expect![[r#"
 740                 lib:
 741                 - pub_macro (m)
 742                 main:
 743                 - m (t)
 744                 - m::pub_macro (m)
 745             "#]],
 746         );
 747     }
 748
 749     #[test]
 750     fn module_reexport() {
 751         // Reexporting modules from a dependency adds all contents to the import map.
 752         check(
 753             r"
 754             //- /main.rs crate:main deps:lib
 755             pub use lib::module as reexported_module;
 756             //- /lib.rs crate:lib
 757             pub mod module {
 758                 pub struct S;
 759             }
 760         ",
 761             expect![[r#"
 762                 lib:
 763                 - module (t)
 764                 - module::S (t)
 765                 - module::S (v)
 766                 main:
 767                 - reexported_module (t)
 768                 - reexported_module::S (t)
 769                 - reexported_module::S (v)
 770             "#]],
 771         );
 772     }
 773
 774     #[test]
 775     fn cyclic_module_reexport() {
 776         // A cyclic reexport does not hang.
 777         check(
 778             r"
 779             //- /lib.rs crate:lib
 780             pub mod module {
 781                 pub struct S;
 782                 pub use super::sub::*;
 783             }
 784
 785             pub mod sub {
 786                 pub use super::module;
 787             }
 788         ",
 789             expect![[r#"
 790                 lib:
 791                 - module (t)
 792                 - module::S (t)
 793                 - module::S (v)
 794                 - sub (t)
 795             "#]],
 796         );
 797     }
 798
 799     #[test]
 800     fn private_macro() {
 801         check(
 802             r"
 803             //- /lib.rs crate:lib
 804             macro_rules! private_macro {
 805                 () => {};
 806             }
 807         ",
 808             expect![[r#"
 809                 lib:
 810
 811             "#]],
 812         );
 813     }
 814
 815     #[test]
 816     fn namespacing() {
 817         check(
 818             r"
 819             //- /lib.rs crate:lib
 820             pub struct Thing;     // t + v
 821             #[macro_export]
 822             macro_rules! Thing {  // m
 823                 () => {};
 824             }
 825         ",
 826             expect![[r#"
 827                 lib:
 828                 - Thing (m)
 829                 - Thing (t)
 830                 - Thing (v)
 831             "#]],
 832         );
 833
 834         check(
 835             r"
 836             //- /lib.rs crate:lib
 837             pub mod Thing {}      // t
 838             #[macro_export]
 839             macro_rules! Thing {  // m
 840                 () => {};
 841             }
 842         ",
 843             expect![[r#"
 844                 lib:
 845                 - Thing (m)
 846                 - Thing (t)
 847             "#]],
 848         );
 849     }
 850
 851     #[test]
 852     fn fuzzy_import_trait_and_assoc_items() {
 853         cov_mark::check!(type_aliases_ignored);
 854         let ra_fixture = r#"
 855         //- /main.rs crate:main deps:dep
 856         //- /dep.rs crate:dep
 857         pub mod fmt {
 858             pub trait Display {
 859                 type FmtTypeAlias;
 860                 const FMT_CONST: bool;
 861
 862                 fn format_function();
 863                 fn format_method(&self);
 864             }
 865         }
 866     "#;
 867
 868         check_search(
 869             ra_fixture,
 870             "main",
 871             Query::new("fmt".to_string()).search_mode(SearchMode::Fuzzy),
 872             expect![[r#"
 873                 dep::fmt (t)
 874                 dep::fmt::Display (t)
 875                 dep::fmt::Display::FMT_CONST (a)
 876                 dep::fmt::Display::format_function (a)
 877                 dep::fmt::Display::format_method (a)
 878             "#]],
 879         );
 880     }
 881
 882     #[test]
 883     fn assoc_items_filtering() {
 884         let ra_fixture = r#"
 885         //- /main.rs crate:main deps:dep
 886         //- /dep.rs crate:dep
 887         pub mod fmt {
 888             pub trait Display {
 889                 type FmtTypeAlias;
 890                 const FMT_CONST: bool;
 891
 892                 fn format_function();
 893                 fn format_method(&self);
 894             }
 895         }
 896     "#;
 897
 898         check_search(
 899             ra_fixture,
 900             "main",
 901             Query::new("fmt".to_string()).search_mode(SearchMode::Fuzzy).assoc_items_only(),
 902             expect![[r#"
 903                 dep::fmt::Display::FMT_CONST (a)
 904                 dep::fmt::Display::format_function (a)
 905                 dep::fmt::Display::format_method (a)
 906             "#]],
 907         );
 908
 909         check_search(
 910             ra_fixture,
 911             "main",
 912             Query::new("fmt".to_string())
 913                 .search_mode(SearchMode::Fuzzy)
 914                 .exclude_import_kind(ImportKind::AssociatedItem),
 915             expect![[r#"
 916             dep::fmt (t)
 917             dep::fmt::Display (t)
 918         "#]],
 919         );
 920
 921         check_search(
 922             ra_fixture,
 923             "main",
 924             Query::new("fmt".to_string())
 925                 .search_mode(SearchMode::Fuzzy)
 926                 .assoc_items_only()
 927                 .exclude_import_kind(ImportKind::AssociatedItem),
 928             expect![[r#""#]],
 929         );
 930     }
 931
 932     #[test]
 933     fn search_mode() {
 934         let ra_fixture = r#"
 935             //- /main.rs crate:main deps:dep
 936             //- /dep.rs crate:dep deps:tdep
 937             use tdep::fmt as fmt_dep;
 938             pub mod fmt {
 939                 pub trait Display {
 940                     fn fmt();
 941                 }
 942             }
 943             #[macro_export]
 944             macro_rules! Fmt {
 945                 () => {};
 946             }
 947             pub struct Fmt;
 948
 949             pub fn format() {}
 950             pub fn no() {}
 951
 952             //- /tdep.rs crate:tdep
 953             pub mod fmt {
 954                 pub struct NotImportableFromMain;
 955             }
 956         "#;
 957
 958         check_search(
 959             ra_fixture,
 960             "main",
 961             Query::new("fmt".to_string()).search_mode(SearchMode::Fuzzy),
 962             expect![[r#"
 963                 dep::Fmt (m)
 964                 dep::Fmt (t)
 965                 dep::Fmt (v)
 966                 dep::fmt (t)
 967                 dep::fmt::Display (t)
 968                 dep::fmt::Display::fmt (a)
 969                 dep::format (f)
 970             "#]],
 971         );
 972
 973         check_search(
 974             ra_fixture,
 975             "main",
 976             Query::new("fmt".to_string()).search_mode(SearchMode::Equals),
 977             expect![[r#"
 978                 dep::Fmt (m)
 979                 dep::Fmt (t)
 980                 dep::Fmt (v)
 981                 dep::fmt (t)
 982                 dep::fmt::Display::fmt (a)
 983             "#]],
 984         );
 985
 986         check_search(
 987             ra_fixture,
 988             "main",
 989             Query::new("fmt".to_string()).search_mode(SearchMode::Contains),
 990             expect![[r#"
 991                 dep::Fmt (m)
 992                 dep::Fmt (t)
 993                 dep::Fmt (v)
 994                 dep::fmt (t)
 995                 dep::fmt::Display (t)
 996                 dep::fmt::Display::fmt (a)
 997             "#]],
 998         );
 999     }
1000
1001     #[test]
1002     fn name_only() {
1003         let ra_fixture = r#"
1004             //- /main.rs crate:main deps:dep
1005             //- /dep.rs crate:dep deps:tdep
1006             use tdep::fmt as fmt_dep;
1007             pub mod fmt {
1008                 pub trait Display {
1009                     fn fmt();
1010                 }
1011             }
1012             #[macro_export]
1013             macro_rules! Fmt {
1014                 () => {};
1015             }
1016             pub struct Fmt;
1017
1018             pub fn format() {}
1019             pub fn no() {}
1020
1021             //- /tdep.rs crate:tdep
1022             pub mod fmt {
1023                 pub struct NotImportableFromMain;
1024             }
1025         "#;
1026
1027         check_search(
1028             ra_fixture,
1029             "main",
1030             Query::new("fmt".to_string()),
1031             expect![[r#"
1032                 dep::Fmt (m)
1033                 dep::Fmt (t)
1034                 dep::Fmt (v)
1035                 dep::fmt (t)
1036                 dep::fmt::Display (t)
1037                 dep::fmt::Display::fmt (a)
1038             "#]],
1039         );
1040
1041         check_search(
1042             ra_fixture,
1043             "main",
1044             Query::new("fmt".to_string()).name_only(),
1045             expect![[r#"
1046                 dep::Fmt (m)
1047                 dep::Fmt (t)
1048                 dep::Fmt (v)
1049                 dep::fmt (t)
1050                 dep::fmt::Display::fmt (a)
1051             "#]],
1052         );
1053     }
1054
1055     #[test]
1056     fn search_casing() {
1057         let ra_fixture = r#"
1058             //- /main.rs crate:main deps:dep
1059             //- /dep.rs crate:dep
1060
1061             pub struct fmt;
1062             pub struct FMT;
1063         "#;
1064
1065         check_search(
1066             ra_fixture,
1067             "main",
1068             Query::new("FMT".to_string()),
1069             expect![[r#"
1070                 dep::FMT (t)
1071                 dep::FMT (v)
1072                 dep::fmt (t)
1073                 dep::fmt (v)
1074             "#]],
1075         );
1076
1077         check_search(
1078             ra_fixture,
1079             "main",
1080             Query::new("FMT".to_string()).case_sensitive(),
1081             expect![[r#"
1082                 dep::FMT (t)
1083                 dep::FMT (v)
1084             "#]],
1085         );
1086     }
1087
1088     #[test]
1089     fn search_limit() {
1090         check_search(
1091             r#"
1092         //- /main.rs crate:main deps:dep
1093         //- /dep.rs crate:dep
1094         pub mod fmt {
1095             pub trait Display {
1096                 fn fmt();
1097             }
1098         }
1099         #[macro_export]
1100         macro_rules! Fmt {
1101             () => {};
1102         }
1103         pub struct Fmt;
1104
1105         pub fn format() {}
1106         pub fn no() {}
1107     "#,
1108             "main",
1109             Query::new("".to_string()).limit(2),
1110             expect![[r#"
1111                 dep::Fmt (m)
1112                 dep::Fmt (t)
1113                 dep::Fmt (v)
1114                 dep::fmt (t)
1115             "#]],
1116         );
1117     }
1118
1119     #[test]
1120     fn search_exclusions() {
1121         let ra_fixture = r#"
1122             //- /main.rs crate:main deps:dep
1123             //- /dep.rs crate:dep
1124
1125             pub struct fmt;
1126             pub struct FMT;
1127         "#;
1128
1129         check_search(
1130             ra_fixture,
1131             "main",
1132             Query::new("FMT".to_string()),
1133             expect![[r#"
1134                 dep::FMT (t)
1135                 dep::FMT (v)
1136                 dep::fmt (t)
1137                 dep::fmt (v)
1138             "#]],
1139         );
1140
1141         check_search(
1142             ra_fixture,
1143             "main",
1144             Query::new("FMT".to_string()).exclude_import_kind(ImportKind::Adt),
1145             expect![[r#""#]],
1146         );
1147     }
1148 }