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