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 = ModuleId { krate, local_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 = db.crate_def_map(module.krate);
  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) => f.into(),
 191                 AssocItemId::ConstId(c) => c.into(),
 192                 AssocItemId::TypeAliasId(t) => t.into(),
 193             };
 194             let assoc_item = if is_type_in_ns {
 195                 ItemInNs::Types(module_def_id)
 196             } else {
 197                 ItemInNs::Values(module_def_id)
 198             };
 199
 200             let mut assoc_item_info = original_import_info.to_owned();
 201             assoc_item_info.path.segments.push(assoc_item_name.to_owned());
 202             assoc_item_info.is_trait_assoc_item = true;
 203             self.map.insert(assoc_item, assoc_item_info);
 204         }
 205     }
 206 }
 207
 208 impl PartialEq for ImportMap {
 209     fn eq(&self, other: &Self) -> bool {
 210         // `fst` and `importables` are built from `map`, so we don't need to compare them.
 211         self.map == other.map
 212     }
 213 }
 214
 215 impl Eq for ImportMap {}
 216
 217 impl fmt::Debug for ImportMap {
 218     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 219         let mut importable_paths: Vec<_> = self
 220             .map
 221             .iter()
 222             .map(|(item, info)| {
 223                 let ns = match item {
 224                     ItemInNs::Types(_) => "t",
 225                     ItemInNs::Values(_) => "v",
 226                     ItemInNs::Macros(_) => "m",
 227                 };
 228                 format!("- {} ({})", info.path, ns)
 229             })
 230             .collect();
 231
 232         importable_paths.sort();
 233         f.write_str(&importable_paths.join("\n"))
 234     }
 235 }
 236
 237 fn fst_path(path: &ImportPath) -> String {
 238     let mut s = path.to_string();
 239     s.make_ascii_lowercase();
 240     s
 241 }
 242
 243 fn cmp((_, lhs): &(&ItemInNs, &ImportInfo), (_, rhs): &(&ItemInNs, &ImportInfo)) -> Ordering {
 244     let lhs_str = fst_path(&lhs.path);
 245     let rhs_str = fst_path(&rhs.path);
 246     lhs_str.cmp(&rhs_str)
 247 }
 248
 249 #[derive(Debug, Eq, PartialEq, Hash)]
 250 pub enum ImportKind {
 251     Module,
 252     Function,
 253     Adt,
 254     EnumVariant,
 255     Const,
 256     Static,
 257     Trait,
 258     TypeAlias,
 259     BuiltinType,
 260 }
 261
 262 /// A way to match import map contents against the search query.
 263 #[derive(Debug)]
 264 pub enum SearchMode {
 265     /// Import map entry should strictly match the query string.
 266     Equals,
 267     /// Import map entry should contain the query string.
 268     Contains,
 269     /// Import map entry should contain all letters from the query string,
 270     /// in the same order, but not necessary adjacent.
 271     Fuzzy,
 272 }
 273
 274 #[derive(Debug)]
 275 pub struct Query {
 276     query: String,
 277     lowercased: String,
 278     name_only: bool,
 279     search_mode: SearchMode,
 280     case_sensitive: bool,
 281     limit: usize,
 282     exclude_import_kinds: FxHashSet<ImportKind>,
 283 }
 284
 285 impl Query {
 286     pub fn new(query: String) -> Self {
 287         let lowercased = query.to_lowercase();
 288         Self {
 289             query,
 290             lowercased,
 291             name_only: false,
 292             search_mode: SearchMode::Contains,
 293             case_sensitive: false,
 294             limit: usize::max_value(),
 295             exclude_import_kinds: FxHashSet::default(),
 296         }
 297     }
 298
 299     /// Matches entries' names only, ignoring the rest of
 300     /// the qualifier.
 301     /// Example: for `std::marker::PhantomData`, the name is `PhantomData`.
 302     pub fn name_only(self) -> Self {
 303         Self { name_only: true, ..self }
 304     }
 305
 306     /// Specifies the way to search for the entries using the query.
 307     pub fn search_mode(self, search_mode: SearchMode) -> Self {
 308         Self { search_mode, ..self }
 309     }
 310
 311     /// Limits the returned number of items to `limit`.
 312     pub fn limit(self, limit: usize) -> Self {
 313         Self { limit, ..self }
 314     }
 315
 316     /// Respect casing of the query string when matching.
 317     pub fn case_sensitive(self) -> Self {
 318         Self { case_sensitive: true, ..self }
 319     }
 320
 321     /// Do not include imports of the specified kind in the search results.
 322     pub fn exclude_import_kind(mut self, import_kind: ImportKind) -> Self {
 323         self.exclude_import_kinds.insert(import_kind);
 324         self
 325     }
 326 }
 327
 328 fn import_matches_query(import: &ImportInfo, query: &Query, enforce_lowercase: bool) -> bool {
 329     let mut input = if import.is_trait_assoc_item || query.name_only {
 330         import.path.segments.last().unwrap().to_string()
 331     } else {
 332         import.path.to_string()
 333     };
 334     if enforce_lowercase || !query.case_sensitive {
 335         input.make_ascii_lowercase();
 336     }
 337
 338     let query_string =
 339         if !enforce_lowercase && query.case_sensitive { &query.query } else { &query.lowercased };
 340
 341     match query.search_mode {
 342         SearchMode::Equals => &input == query_string,
 343         SearchMode::Contains => input.contains(query_string),
 344         SearchMode::Fuzzy => {
 345             let mut unchecked_query_chars = query_string.chars();
 346             let mut mismatching_query_char = unchecked_query_chars.next();
 347
 348             for input_char in input.chars() {
 349                 match mismatching_query_char {
 350                     None => return true,
 351                     Some(matching_query_char) if matching_query_char == input_char => {
 352                         mismatching_query_char = unchecked_query_chars.next();
 353                     }
 354                     _ => (),
 355                 }
 356             }
 357             mismatching_query_char.is_none()
 358         }
 359     }
 360 }
 361
 362 /// Searches dependencies of `krate` for an importable path matching `query`.
 363 ///
 364 /// This returns a list of items that could be imported from dependencies of `krate`.
 365 pub fn search_dependencies<'a>(
 366     db: &'a dyn DefDatabase,
 367     krate: CrateId,
 368     query: Query,
 369 ) -> Vec<ItemInNs> {
 370     let _p = profile::span("search_dependencies").detail(|| format!("{:?}", query));
 371
 372     let graph = db.crate_graph();
 373     let import_maps: Vec<_> =
 374         graph[krate].dependencies.iter().map(|dep| db.import_map(dep.crate_id)).collect();
 375
 376     let automaton = fst::automaton::Subsequence::new(&query.lowercased);
 377
 378     let mut op = fst::map::OpBuilder::new();
 379     for map in &import_maps {
 380         op = op.add(map.fst.search(&automaton));
 381     }
 382
 383     let mut stream = op.union();
 384     let mut res = Vec::new();
 385     while let Some((_, indexed_values)) = stream.next() {
 386         for indexed_value in indexed_values {
 387             let import_map = &import_maps[indexed_value.index];
 388             let importables = &import_map.importables[indexed_value.value as usize..];
 389
 390             let common_importable_data = &import_map.map[&importables[0]];
 391             if !import_matches_query(common_importable_data, &query, true) {
 392                 continue;
 393             }
 394
 395             // Path shared by the importable items in this group.
 396             let common_importables_path_fst = fst_path(&common_importable_data.path);
 397             // Add the items from this `ModPath` group. Those are all subsequent items in
 398             // `importables` whose paths match `path`.
 399             let iter = importables
 400                 .iter()
 401                 .copied()
 402                 .take_while(|item| {
 403                     common_importables_path_fst == fst_path(&import_map.map[item].path)
 404                 })
 405                 .filter(|&item| match item_import_kind(item) {
 406                     Some(import_kind) => !query.exclude_import_kinds.contains(&import_kind),
 407                     None => true,
 408                 })
 409                 .filter(|item| {
 410                     !query.case_sensitive // we've already checked the common importables path case-insensitively
 411                         || import_matches_query(&import_map.map[item], &query, false)
 412                 });
 413             res.extend(iter);
 414
 415             if res.len() >= query.limit {
 416                 res.truncate(query.limit);
 417                 return res;
 418             }
 419         }
 420     }
 421
 422     res
 423 }
 424
 425 fn item_import_kind(item: ItemInNs) -> Option<ImportKind> {
 426     Some(match item.as_module_def_id()? {
 427         ModuleDefId::ModuleId(_) => ImportKind::Module,
 428         ModuleDefId::FunctionId(_) => ImportKind::Function,
 429         ModuleDefId::AdtId(_) => ImportKind::Adt,
 430         ModuleDefId::EnumVariantId(_) => ImportKind::EnumVariant,
 431         ModuleDefId::ConstId(_) => ImportKind::Const,
 432         ModuleDefId::StaticId(_) => ImportKind::Static,
 433         ModuleDefId::TraitId(_) => ImportKind::Trait,
 434         ModuleDefId::TypeAliasId(_) => ImportKind::TypeAlias,
 435         ModuleDefId::BuiltinType(_) => ImportKind::BuiltinType,
 436     })
 437 }
 438
 439 #[cfg(test)]
 440 mod tests {
 441     use base_db::{fixture::WithFixture, SourceDatabase, Upcast};
 442     use expect_test::{expect, Expect};
 443
 444     use crate::{test_db::TestDB, AssocContainerId, Lookup};
 445
 446     use super::*;
 447
 448     fn check_search(ra_fixture: &str, crate_name: &str, query: Query, expect: Expect) {
 449         let db = TestDB::with_files(ra_fixture);
 450         let crate_graph = db.crate_graph();
 451         let krate = crate_graph
 452             .iter()
 453             .find(|krate| {
 454                 crate_graph[*krate].display_name.as_ref().map(|n| n.to_string())
 455                     == Some(crate_name.to_string())
 456             })
 457             .unwrap();
 458
 459         let actual = search_dependencies(db.upcast(), krate, query)
 460             .into_iter()
 461             .filter_map(|dependency| {
 462                 let dependency_krate = dependency.krate(db.upcast())?;
 463                 let dependency_imports = db.import_map(dependency_krate);
 464
 465                 let (path, mark) = match assoc_item_path(&db, &dependency_imports, dependency) {
 466                     Some(assoc_item_path) => (assoc_item_path, "a"),
 467                     None => (
 468                         dependency_imports.path_of(dependency)?.to_string(),
 469                         match dependency {
 470                             ItemInNs::Types(ModuleDefId::FunctionId(_))
 471                             | ItemInNs::Values(ModuleDefId::FunctionId(_)) => "f",
 472                             ItemInNs::Types(_) => "t",
 473                             ItemInNs::Values(_) => "v",
 474                             ItemInNs::Macros(_) => "m",
 475                         },
 476                     ),
 477                 };
 478
 479                 Some(format!(
 480                     "{}::{} ({})\n",
 481                     crate_graph[dependency_krate].display_name.as_ref()?,
 482                     path,
 483                     mark
 484                 ))
 485             })
 486             .collect::<String>();
 487         expect.assert_eq(&actual)
 488     }
 489
 490     fn assoc_item_path(
 491         db: &dyn DefDatabase,
 492         dependency_imports: &ImportMap,
 493         dependency: ItemInNs,
 494     ) -> Option<String> {
 495         let dependency_assoc_item_id = match dependency {
 496             ItemInNs::Types(ModuleDefId::FunctionId(id))
 497             | ItemInNs::Values(ModuleDefId::FunctionId(id)) => AssocItemId::from(id),
 498             ItemInNs::Types(ModuleDefId::ConstId(id))
 499             | ItemInNs::Values(ModuleDefId::ConstId(id)) => AssocItemId::from(id),
 500             ItemInNs::Types(ModuleDefId::TypeAliasId(id))
 501             | ItemInNs::Values(ModuleDefId::TypeAliasId(id)) => AssocItemId::from(id),
 502             _ => return None,
 503         };
 504
 505         let trait_ = assoc_to_trait(db, dependency)?;
 506         if let ModuleDefId::TraitId(tr) = trait_.as_module_def_id()? {
 507             let trait_data = db.trait_data(tr);
 508             let assoc_item_name =
 509                 trait_data.items.iter().find_map(|(assoc_item_name, assoc_item_id)| {
 510                     if &dependency_assoc_item_id == assoc_item_id {
 511                         Some(assoc_item_name)
 512                     } else {
 513                         None
 514                     }
 515                 })?;
 516             return Some(format!("{}::{}", dependency_imports.path_of(trait_)?, assoc_item_name));
 517         }
 518         None
 519     }
 520
 521     fn assoc_to_trait(db: &dyn DefDatabase, item: ItemInNs) -> Option<ItemInNs> {
 522         let assoc: AssocItemId = match item {
 523             ItemInNs::Types(it) | ItemInNs::Values(it) => match it {
 524                 ModuleDefId::TypeAliasId(it) => it.into(),
 525                 ModuleDefId::FunctionId(it) => it.into(),
 526                 ModuleDefId::ConstId(it) => it.into(),
 527                 _ => return None,
 528             },
 529             _ => return None,
 530         };
 531
 532         let container = match assoc {
 533             AssocItemId::FunctionId(it) => it.lookup(db).container,
 534             AssocItemId::ConstId(it) => it.lookup(db).container,
 535             AssocItemId::TypeAliasId(it) => it.lookup(db).container,
 536         };
 537
 538         match container {
 539             AssocContainerId::TraitId(it) => Some(ItemInNs::Types(it.into())),
 540             _ => None,
 541         }
 542     }
 543
 544     fn check(ra_fixture: &str, expect: Expect) {
 545         let db = TestDB::with_files(ra_fixture);
 546         let crate_graph = db.crate_graph();
 547
 548         let actual = crate_graph
 549             .iter()
 550             .filter_map(|krate| {
 551                 let cdata = &crate_graph[krate];
 552                 let name = cdata.display_name.as_ref()?;
 553
 554                 let map = db.import_map(krate);
 555
 556                 Some(format!("{}:\n{:?}\n", name, map))
 557             })
 558             .collect::<String>();
 559
 560         expect.assert_eq(&actual)
 561     }
 562
 563     #[test]
 564     fn smoke() {
 565         check(
 566             r"
 567             //- /main.rs crate:main deps:lib
 568
 569             mod private {
 570                 pub use lib::Pub;
 571                 pub struct InPrivateModule;
 572             }
 573
 574             pub mod publ1 {
 575                 use lib::Pub;
 576             }
 577
 578             pub mod real_pub {
 579                 pub use lib::Pub;
 580             }
 581             pub mod real_pu2 { // same path length as above
 582                 pub use lib::Pub;
 583             }
 584
 585             //- /lib.rs crate:lib
 586             pub struct Pub {}
 587             pub struct Pub2; // t + v
 588             struct Priv;
 589         ",
 590             expect![[r#"
 591                 main:
 592                 - publ1 (t)
 593                 - real_pu2 (t)
 594                 - real_pub (t)
 595                 - real_pub::Pub (t)
 596                 lib:
 597                 - Pub (t)
 598                 - Pub2 (t)
 599                 - Pub2 (v)
 600             "#]],
 601         );
 602     }
 603
 604     #[test]
 605     fn prefers_shortest_path() {
 606         check(
 607             r"
 608             //- /main.rs crate:main
 609
 610             pub mod sub {
 611                 pub mod subsub {
 612                     pub struct Def {}
 613                 }
 614
 615                 pub use super::sub::subsub::Def;
 616             }
 617         ",
 618             expect![[r#"
 619                 main:
 620                 - sub (t)
 621                 - sub::Def (t)
 622                 - sub::subsub (t)
 623             "#]],
 624         );
 625     }
 626
 627     #[test]
 628     fn type_reexport_cross_crate() {
 629         // Reexports need to be visible from a crate, even if the original crate exports the item
 630         // at a shorter path.
 631         check(
 632             r"
 633             //- /main.rs crate:main deps:lib
 634             pub mod m {
 635                 pub use lib::S;
 636             }
 637             //- /lib.rs crate:lib
 638             pub struct S;
 639         ",
 640             expect![[r#"
 641                 main:
 642                 - m (t)
 643                 - m::S (t)
 644                 - m::S (v)
 645                 lib:
 646                 - S (t)
 647                 - S (v)
 648             "#]],
 649         );
 650     }
 651
 652     #[test]
 653     fn macro_reexport() {
 654         check(
 655             r"
 656             //- /main.rs crate:main deps:lib
 657             pub mod m {
 658                 pub use lib::pub_macro;
 659             }
 660             //- /lib.rs crate:lib
 661             #[macro_export]
 662             macro_rules! pub_macro {
 663                 () => {};
 664             }
 665         ",
 666             expect![[r#"
 667                 main:
 668                 - m (t)
 669                 - m::pub_macro (m)
 670                 lib:
 671                 - pub_macro (m)
 672             "#]],
 673         );
 674     }
 675
 676     #[test]
 677     fn module_reexport() {
 678         // Reexporting modules from a dependency adds all contents to the import map.
 679         check(
 680             r"
 681             //- /main.rs crate:main deps:lib
 682             pub use lib::module as reexported_module;
 683             //- /lib.rs crate:lib
 684             pub mod module {
 685                 pub struct S;
 686             }
 687         ",
 688             expect![[r#"
 689                 main:
 690                 - reexported_module (t)
 691                 - reexported_module::S (t)
 692                 - reexported_module::S (v)
 693                 lib:
 694                 - module (t)
 695                 - module::S (t)
 696                 - module::S (v)
 697             "#]],
 698         );
 699     }
 700
 701     #[test]
 702     fn cyclic_module_reexport() {
 703         // A cyclic reexport does not hang.
 704         check(
 705             r"
 706             //- /lib.rs crate:lib
 707             pub mod module {
 708                 pub struct S;
 709                 pub use super::sub::*;
 710             }
 711
 712             pub mod sub {
 713                 pub use super::module;
 714             }
 715         ",
 716             expect![[r#"
 717                 lib:
 718                 - module (t)
 719                 - module::S (t)
 720                 - module::S (v)
 721                 - sub (t)
 722             "#]],
 723         );
 724     }
 725
 726     #[test]
 727     fn private_macro() {
 728         check(
 729             r"
 730             //- /lib.rs crate:lib
 731             macro_rules! private_macro {
 732                 () => {};
 733             }
 734         ",
 735             expect![[r#"
 736                 lib:
 737
 738             "#]],
 739         );
 740     }
 741
 742     #[test]
 743     fn namespacing() {
 744         check(
 745             r"
 746             //- /lib.rs crate:lib
 747             pub struct Thing;     // t + v
 748             #[macro_export]
 749             macro_rules! Thing {  // m
 750                 () => {};
 751             }
 752         ",
 753             expect![[r#"
 754                 lib:
 755                 - Thing (m)
 756                 - Thing (t)
 757                 - Thing (v)
 758             "#]],
 759         );
 760
 761         check(
 762             r"
 763             //- /lib.rs crate:lib
 764             pub mod Thing {}      // t
 765             #[macro_export]
 766             macro_rules! Thing {  // m
 767                 () => {};
 768             }
 769         ",
 770             expect![[r#"
 771                 lib:
 772                 - Thing (m)
 773                 - Thing (t)
 774             "#]],
 775         );
 776     }
 777
 778     #[test]
 779     fn fuzzy_import_trait_and_assoc_items() {
 780         let ra_fixture = r#"
 781         //- /main.rs crate:main deps:dep
 782         //- /dep.rs crate:dep
 783         pub mod fmt {
 784             pub trait Display {
 785                 type FmtTypeAlias;
 786                 const FMT_CONST: bool;
 787
 788                 fn format_function();
 789                 fn format_method(&self);
 790             }
 791         }
 792     "#;
 793
 794         check_search(
 795             ra_fixture,
 796             "main",
 797             Query::new("fmt".to_string()).search_mode(SearchMode::Fuzzy),
 798             expect![[r#"
 799                 dep::fmt (t)
 800                 dep::fmt::Display (t)
 801                 dep::fmt::Display::FMT_CONST (a)
 802                 dep::fmt::Display::FmtTypeAlias (a)
 803                 dep::fmt::Display::format_function (a)
 804                 dep::fmt::Display::format_method (a)
 805             "#]],
 806         );
 807     }
 808
 809     #[test]
 810     fn search_mode() {
 811         let ra_fixture = r#"
 812             //- /main.rs crate:main deps:dep
 813             //- /dep.rs crate:dep deps:tdep
 814             use tdep::fmt as fmt_dep;
 815             pub mod fmt {
 816                 pub trait Display {
 817                     fn fmt();
 818                 }
 819             }
 820             #[macro_export]
 821             macro_rules! Fmt {
 822                 () => {};
 823             }
 824             pub struct Fmt;
 825
 826             pub fn format() {}
 827             pub fn no() {}
 828
 829             //- /tdep.rs crate:tdep
 830             pub mod fmt {
 831                 pub struct NotImportableFromMain;
 832             }
 833         "#;
 834
 835         check_search(
 836             ra_fixture,
 837             "main",
 838             Query::new("fmt".to_string()).search_mode(SearchMode::Fuzzy),
 839             expect![[r#"
 840                 dep::fmt (t)
 841                 dep::Fmt (t)
 842                 dep::Fmt (v)
 843                 dep::Fmt (m)
 844                 dep::fmt::Display (t)
 845                 dep::fmt::Display::fmt (a)
 846                 dep::format (f)
 847             "#]],
 848         );
 849
 850         check_search(
 851             ra_fixture,
 852             "main",
 853             Query::new("fmt".to_string()).search_mode(SearchMode::Equals),
 854             expect![[r#"
 855                 dep::fmt (t)
 856                 dep::Fmt (t)
 857                 dep::Fmt (v)
 858                 dep::Fmt (m)
 859                 dep::fmt::Display::fmt (a)
 860             "#]],
 861         );
 862
 863         check_search(
 864             ra_fixture,
 865             "main",
 866             Query::new("fmt".to_string()).search_mode(SearchMode::Contains),
 867             expect![[r#"
 868                 dep::fmt (t)
 869                 dep::Fmt (t)
 870                 dep::Fmt (v)
 871                 dep::Fmt (m)
 872                 dep::fmt::Display (t)
 873                 dep::fmt::Display::fmt (a)
 874             "#]],
 875         );
 876     }
 877
 878     #[test]
 879     fn name_only() {
 880         let ra_fixture = r#"
 881             //- /main.rs crate:main deps:dep
 882             //- /dep.rs crate:dep deps:tdep
 883             use tdep::fmt as fmt_dep;
 884             pub mod fmt {
 885                 pub trait Display {
 886                     fn fmt();
 887                 }
 888             }
 889             #[macro_export]
 890             macro_rules! Fmt {
 891                 () => {};
 892             }
 893             pub struct Fmt;
 894
 895             pub fn format() {}
 896             pub fn no() {}
 897
 898             //- /tdep.rs crate:tdep
 899             pub mod fmt {
 900                 pub struct NotImportableFromMain;
 901             }
 902         "#;
 903
 904         check_search(
 905             ra_fixture,
 906             "main",
 907             Query::new("fmt".to_string()),
 908             expect![[r#"
 909                 dep::fmt (t)
 910                 dep::Fmt (t)
 911                 dep::Fmt (v)
 912                 dep::Fmt (m)
 913                 dep::fmt::Display (t)
 914                 dep::fmt::Display::fmt (a)
 915             "#]],
 916         );
 917
 918         check_search(
 919             ra_fixture,
 920             "main",
 921             Query::new("fmt".to_string()).name_only(),
 922             expect![[r#"
 923                 dep::fmt (t)
 924                 dep::Fmt (t)
 925                 dep::Fmt (v)
 926                 dep::Fmt (m)
 927                 dep::fmt::Display::fmt (a)
 928             "#]],
 929         );
 930     }
 931
 932     #[test]
 933     fn search_casing() {
 934         let ra_fixture = r#"
 935             //- /main.rs crate:main deps:dep
 936             //- /dep.rs crate:dep
 937
 938             pub struct fmt;
 939             pub struct FMT;
 940         "#;
 941
 942         check_search(
 943             ra_fixture,
 944             "main",
 945             Query::new("FMT".to_string()),
 946             expect![[r#"
 947                 dep::fmt (t)
 948                 dep::fmt (v)
 949                 dep::FMT (t)
 950                 dep::FMT (v)
 951             "#]],
 952         );
 953
 954         check_search(
 955             ra_fixture,
 956             "main",
 957             Query::new("FMT".to_string()).case_sensitive(),
 958             expect![[r#"
 959                 dep::FMT (t)
 960                 dep::FMT (v)
 961             "#]],
 962         );
 963     }
 964
 965     #[test]
 966     fn search_limit() {
 967         check_search(
 968             r#"
 969         //- /main.rs crate:main deps:dep
 970         //- /dep.rs crate:dep
 971         pub mod fmt {
 972             pub trait Display {
 973                 fn fmt();
 974             }
 975         }
 976         #[macro_export]
 977         macro_rules! Fmt {
 978             () => {};
 979         }
 980         pub struct Fmt;
 981
 982         pub fn format() {}
 983         pub fn no() {}
 984     "#,
 985             "main",
 986             Query::new("".to_string()).limit(2),
 987             expect![[r#"
 988                 dep::fmt (t)
 989                 dep::Fmt (t)
 990             "#]],
 991         );
 992     }
 993
 994     #[test]
 995     fn search_exclusions() {
 996         let ra_fixture = r#"
 997             //- /main.rs crate:main deps:dep
 998             //- /dep.rs crate:dep
 999
1000             pub struct fmt;
1001             pub struct FMT;
1002         "#;
1003
1004         check_search(
1005             ra_fixture,
1006             "main",
1007             Query::new("FMT".to_string()),
1008             expect![[r#"
1009                 dep::fmt (t)
1010                 dep::fmt (v)
1011                 dep::FMT (t)
1012                 dep::FMT (v)
1013             "#]],
1014         );
1015
1016         check_search(
1017             ra_fixture,
1018             "main",
1019             Query::new("FMT".to_string()).exclude_import_kind(ImportKind::Adt),
1020             expect![[r#""#]],
1021         );
1022     }
1023 }