crates/hir_def/src/import_map.rs

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