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

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