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::{FxHashMap, FxHashSet, FxHasher};
  11 use smallvec::SmallVec;
  12 use syntax::SmolStr;
  13
  14 use crate::{
  15     db::DefDatabase, item_scope::ItemInNs, visibility::Visibility, AssocItemId, ModuleDefId,
  16     ModuleId, TraitId,
  17 };
  18
  19 type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<FxHasher>>;
  20
  21 /// Item import details stored in the `ImportMap`.
  22 #[derive(Debug, Clone, Eq, PartialEq)]
  23 pub struct ImportInfo {
  24     /// A path that can be used to import the item, relative to the crate's root.
  25     pub path: ImportPath,
  26     /// The module containing this item.
  27     pub container: ModuleId,
  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     /// Maps names of associated items to the item's ID. Only includes items whose defining trait is
  69     /// exported.
  70     assoc_map: FxHashMap<SmolStr, SmallVec<[AssocItemId; 1]>>,
  71 }
  72
  73 impl ImportMap {
  74     pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<Self> {
  75         let _p = profile::span("import_map_query");
  76         let def_map = db.crate_def_map(krate);
  77         let mut import_map = Self::default();
  78
  79         // We look only into modules that are public(ly reexported), starting with the crate root.
  80         let empty = ImportPath { segments: vec![] };
  81         let root = ModuleId { krate, local_id: def_map.root };
  82         let mut worklist = vec![(root, empty)];
  83         while let Some((module, mod_path)) = worklist.pop() {
  84             let ext_def_map;
  85             let mod_data = if module.krate == krate {
  86                 &def_map[module.local_id]
  87             } else {
  88                 // The crate might reexport a module defined in another crate.
  89                 ext_def_map = db.crate_def_map(module.krate);
  90                 &ext_def_map[module.local_id]
  91             };
  92
  93             let visible_items = mod_data.scope.entries().filter_map(|(name, per_ns)| {
  94                 let per_ns = per_ns.filter_visibility(|vis| vis == Visibility::Public);
  95                 if per_ns.is_none() {
  96                     None
  97                 } else {
  98                     Some((name, per_ns))
  99                 }
 100             });
 101
 102             for (name, per_ns) in visible_items {
 103                 let mk_path = || {
 104                     let mut path = mod_path.clone();
 105                     path.segments.push(name.clone());
 106                     path
 107                 };
 108
 109                 for item in per_ns.iter_items() {
 110                     let path = mk_path();
 111                     match import_map.map.entry(item) {
 112                         Entry::Vacant(entry) => {
 113                             entry.insert(ImportInfo { path, container: module });
 114                         }
 115                         Entry::Occupied(mut entry) => {
 116                             // If the new path is shorter, prefer that one.
 117                             if path.len() < entry.get().path.len() {
 118                                 *entry.get_mut() = ImportInfo { path, container: module };
 119                             } else {
 120                                 continue;
 121                             }
 122                         }
 123                     }
 124
 125                     // If we've just added a path to a module, descend into it. We might traverse
 126                     // modules multiple times, but only if the new path to it is shorter than the
 127                     // first (else we `continue` above).
 128                     if let Some(ModuleDefId::ModuleId(mod_id)) = item.as_module_def_id() {
 129                         worklist.push((mod_id, mk_path()));
 130                     }
 131
 132                     // If we've added a path to a trait, add the trait's methods to the method map.
 133                     if let Some(ModuleDefId::TraitId(tr)) = item.as_module_def_id() {
 134                         import_map.collect_trait_methods(db, tr);
 135                     }
 136                 }
 137             }
 138         }
 139
 140         let mut importables = import_map.map.iter().collect::<Vec<_>>();
 141
 142         importables.sort_by(cmp);
 143
 144         // Build the FST, taking care not to insert duplicate values.
 145
 146         let mut builder = fst::MapBuilder::memory();
 147         let mut last_batch_start = 0;
 148
 149         for idx in 0..importables.len() {
 150             if let Some(next_item) = importables.get(idx + 1) {
 151                 if cmp(&importables[last_batch_start], next_item) == Ordering::Equal {
 152                     continue;
 153                 }
 154             }
 155
 156             let start = last_batch_start;
 157             last_batch_start = idx + 1;
 158
 159             let key = fst_string(&importables[start].1.path);
 160             builder.insert(key, start as u64).unwrap();
 161         }
 162
 163         import_map.fst = fst::Map::new(builder.into_inner().unwrap()).unwrap();
 164         import_map.importables = importables.iter().map(|(item, _)| **item).collect();
 165
 166         Arc::new(import_map)
 167     }
 168
 169     /// Returns the `ModPath` needed to import/mention `item`, relative to this crate's root.
 170     pub fn path_of(&self, item: ItemInNs) -> Option<&ImportPath> {
 171         self.import_info_for(item).map(|it| &it.path)
 172     }
 173
 174     pub fn import_info_for(&self, item: ItemInNs) -> Option<&ImportInfo> {
 175         self.map.get(&item)
 176     }
 177
 178     fn collect_trait_methods(&mut self, db: &dyn DefDatabase, tr: TraitId) {
 179         let data = db.trait_data(tr);
 180         for (name, item) in data.items.iter() {
 181             self.assoc_map.entry(name.to_string().into()).or_default().push(*item);
 182         }
 183     }
 184 }
 185
 186 impl PartialEq for ImportMap {
 187     fn eq(&self, other: &Self) -> bool {
 188         // `fst` and `importables` are built from `map`, so we don't need to compare them.
 189         self.map == other.map
 190     }
 191 }
 192
 193 impl Eq for ImportMap {}
 194
 195 impl fmt::Debug for ImportMap {
 196     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 197         let mut importable_paths: Vec<_> = self
 198             .map
 199             .iter()
 200             .map(|(item, info)| {
 201                 let ns = match item {
 202                     ItemInNs::Types(_) => "t",
 203                     ItemInNs::Values(_) => "v",
 204                     ItemInNs::Macros(_) => "m",
 205                 };
 206                 format!("- {} ({})", info.path, ns)
 207             })
 208             .collect();
 209
 210         importable_paths.sort();
 211         f.write_str(&importable_paths.join("\n"))
 212     }
 213 }
 214
 215 fn fst_string<T: ToString>(t: &T) -> String {
 216     let mut s = t.to_string();
 217     s.make_ascii_lowercase();
 218     s
 219 }
 220
 221 fn cmp((_, lhs): &(&ItemInNs, &ImportInfo), (_, rhs): &(&ItemInNs, &ImportInfo)) -> Ordering {
 222     let lhs_str = fst_string(&lhs.path);
 223     let rhs_str = fst_string(&rhs.path);
 224     lhs_str.cmp(&rhs_str)
 225 }
 226
 227 #[derive(Debug, Eq, PartialEq, Hash)]
 228 pub enum ImportKind {
 229     Module,
 230     Function,
 231     Adt,
 232     EnumVariant,
 233     Const,
 234     Static,
 235     Trait,
 236     TypeAlias,
 237     BuiltinType,
 238 }
 239
 240 #[derive(Debug)]
 241 pub struct Query {
 242     query: String,
 243     lowercased: String,
 244     // TODO kb use enums instead?
 245     name_only: bool,
 246     name_end: bool,
 247     strict_include: bool,
 248     case_sensitive: bool,
 249     limit: usize,
 250     exclude_import_kinds: FxHashSet<ImportKind>,
 251 }
 252
 253 impl Query {
 254     pub fn new(query: &str) -> Self {
 255         Self {
 256             lowercased: query.to_lowercase(),
 257             query: query.to_string(),
 258             name_only: false,
 259             name_end: false,
 260             strict_include: false,
 261             case_sensitive: false,
 262             limit: usize::max_value(),
 263             exclude_import_kinds: FxHashSet::default(),
 264         }
 265     }
 266
 267     pub fn name_end(self) -> Self {
 268         Self { name_end: true, ..self }
 269     }
 270
 271     /// todo kb
 272     pub fn name_only(self) -> Self {
 273         Self { name_only: true, ..self }
 274     }
 275
 276     /// todo kb
 277     pub fn strict_include(self) -> Self {
 278         Self { strict_include: true, ..self }
 279     }
 280
 281     /// Limits the returned number of items to `limit`.
 282     pub fn limit(self, limit: usize) -> Self {
 283         Self { limit, ..self }
 284     }
 285
 286     /// Respect casing of the query string when matching.
 287     pub fn case_sensitive(self) -> Self {
 288         Self { case_sensitive: true, ..self }
 289     }
 290
 291     /// Do not include imports of the specified kind in the search results.
 292     pub fn exclude_import_kind(mut self, import_kind: ImportKind) -> Self {
 293         self.exclude_import_kinds.insert(import_kind);
 294         self
 295     }
 296 }
 297
 298 // TODO kb: ugly with a special `return true` case and the `enforce_lowercase` one.
 299 fn contains_query(query: &Query, input_path: &ImportPath, enforce_lowercase: bool) -> bool {
 300     let mut input = if query.name_only {
 301         input_path.segments.last().unwrap().to_string()
 302     } else {
 303         input_path.to_string()
 304     };
 305     if enforce_lowercase || !query.case_sensitive {
 306         input.make_ascii_lowercase();
 307     }
 308
 309     let query_string =
 310         if !enforce_lowercase && query.case_sensitive { &query.query } else { &query.lowercased };
 311
 312     if query.strict_include {
 313         if query.name_end {
 314             &input == query_string
 315         } else {
 316             input.contains(query_string)
 317         }
 318     } else if query.name_end {
 319         input.ends_with(query_string)
 320     } else {
 321         let input_chars = input.chars().collect::<FxHashSet<_>>();
 322         // TODO kb actually check for the order and the quantity
 323         query_string.chars().all(|query_char| input_chars.contains(&query_char))
 324     }
 325 }
 326
 327 /// Searches dependencies of `krate` for an importable path matching `query`.
 328 ///
 329 /// This returns a list of items that could be imported from dependencies of `krate`.
 330 pub fn search_dependencies<'a>(
 331     db: &'a dyn DefDatabase,
 332     krate: CrateId,
 333     query: Query,
 334 ) -> Vec<ItemInNs> {
 335     let _p = profile::span("search_dependencies").detail(|| format!("{:?}", query));
 336
 337     let graph = db.crate_graph();
 338     let import_maps: Vec<_> =
 339         graph[krate].dependencies.iter().map(|dep| db.import_map(dep.crate_id)).collect();
 340
 341     let automaton = fst::automaton::Subsequence::new(&query.lowercased);
 342
 343     let mut op = fst::map::OpBuilder::new();
 344     for map in &import_maps {
 345         op = op.add(map.fst.search(&automaton));
 346     }
 347
 348     let mut stream = op.union();
 349     let mut res = Vec::new();
 350     while let Some((_, indexed_values)) = stream.next() {
 351         for indexed_value in indexed_values {
 352             let import_map = &import_maps[indexed_value.index];
 353             let importables = &import_map.importables[indexed_value.value as usize..];
 354
 355             // Path shared by the importable items in this group.
 356             let common_importables_path = &import_map.map[&importables[0]].path;
 357             if !contains_query(&query, common_importables_path, true) {
 358                 continue;
 359             }
 360
 361             let common_importables_path_fst = fst_string(common_importables_path);
 362             // Add the items from this `ModPath` group. Those are all subsequent items in
 363             // `importables` whose paths match `path`.
 364             let iter = importables
 365                 .iter()
 366                 .copied()
 367                 .take_while(|item| {
 368                     common_importables_path_fst == fst_string(&import_map.map[item].path)
 369                 })
 370                 .filter(|&item| match item_import_kind(item) {
 371                     Some(import_kind) => !query.exclude_import_kinds.contains(&import_kind),
 372                     None => true,
 373                 })
 374                 .filter(|item| contains_query(&query, &import_map.map[item].path, false));
 375             res.extend(iter);
 376
 377             if res.len() >= query.limit {
 378                 res.truncate(query.limit);
 379                 return res;
 380             }
 381         }
 382     }
 383
 384     // Add all exported associated items whose names match the query (exactly).
 385     for map in &import_maps {
 386         if let Some(v) = map.assoc_map.get(&*query.query) {
 387             res.extend(v.iter().map(|&assoc| {
 388                 ItemInNs::Types(match assoc {
 389                     AssocItemId::FunctionId(it) => it.into(),
 390                     AssocItemId::ConstId(it) => it.into(),
 391                     AssocItemId::TypeAliasId(it) => it.into(),
 392                 })
 393             }));
 394         }
 395     }
 396
 397     res
 398 }
 399
 400 fn item_import_kind(item: ItemInNs) -> Option<ImportKind> {
 401     Some(match item.as_module_def_id()? {
 402         ModuleDefId::ModuleId(_) => ImportKind::Module,
 403         ModuleDefId::FunctionId(_) => ImportKind::Function,
 404         ModuleDefId::AdtId(_) => ImportKind::Adt,
 405         ModuleDefId::EnumVariantId(_) => ImportKind::EnumVariant,
 406         ModuleDefId::ConstId(_) => ImportKind::Const,
 407         ModuleDefId::StaticId(_) => ImportKind::Static,
 408         ModuleDefId::TraitId(_) => ImportKind::Trait,
 409         ModuleDefId::TypeAliasId(_) => ImportKind::TypeAlias,
 410         ModuleDefId::BuiltinType(_) => ImportKind::BuiltinType,
 411     })
 412 }
 413
 414 #[cfg(test)]
 415 mod tests {
 416     use base_db::{fixture::WithFixture, SourceDatabase, Upcast};
 417     use expect_test::{expect, Expect};
 418
 419     use crate::{test_db::TestDB, AssocContainerId, Lookup};
 420
 421     use super::*;
 422
 423     fn check_search(ra_fixture: &str, crate_name: &str, query: Query, expect: Expect) {
 424         let db = TestDB::with_files(ra_fixture);
 425         let crate_graph = db.crate_graph();
 426         let krate = crate_graph
 427             .iter()
 428             .find(|krate| {
 429                 crate_graph[*krate].display_name.as_ref().map(|n| n.to_string())
 430                     == Some(crate_name.to_string())
 431             })
 432             .unwrap();
 433
 434         let actual = search_dependencies(db.upcast(), krate, query)
 435             .into_iter()
 436             .filter_map(|item| {
 437                 let mark = match item {
 438                     ItemInNs::Types(_) => "t",
 439                     ItemInNs::Values(_) => "v",
 440                     ItemInNs::Macros(_) => "m",
 441                 };
 442                 let item = assoc_to_trait(&db, item);
 443                 item.krate(db.upcast()).map(|krate| {
 444                     let map = db.import_map(krate);
 445                     let path = map.path_of(item).unwrap();
 446                     format!(
 447                         "{}::{} ({})\n",
 448                         crate_graph[krate].display_name.as_ref().unwrap(),
 449                         path,
 450                         mark
 451                     )
 452                 })
 453             })
 454             .collect::<String>();
 455         expect.assert_eq(&actual)
 456     }
 457
 458     fn assoc_to_trait(db: &dyn DefDatabase, item: ItemInNs) -> ItemInNs {
 459         let assoc: AssocItemId = match item {
 460             ItemInNs::Types(it) | ItemInNs::Values(it) => match it {
 461                 ModuleDefId::TypeAliasId(it) => it.into(),
 462                 ModuleDefId::FunctionId(it) => it.into(),
 463                 ModuleDefId::ConstId(it) => it.into(),
 464                 _ => return item,
 465             },
 466             _ => return item,
 467         };
 468
 469         let container = match assoc {
 470             AssocItemId::FunctionId(it) => it.lookup(db).container,
 471             AssocItemId::ConstId(it) => it.lookup(db).container,
 472             AssocItemId::TypeAliasId(it) => it.lookup(db).container,
 473         };
 474
 475         match container {
 476             AssocContainerId::TraitId(it) => ItemInNs::Types(it.into()),
 477             _ => item,
 478         }
 479     }
 480
 481     fn check(ra_fixture: &str, expect: Expect) {
 482         let db = TestDB::with_files(ra_fixture);
 483         let crate_graph = db.crate_graph();
 484
 485         let actual = crate_graph
 486             .iter()
 487             .filter_map(|krate| {
 488                 let cdata = &crate_graph[krate];
 489                 let name = cdata.display_name.as_ref()?;
 490
 491                 let map = db.import_map(krate);
 492
 493                 Some(format!("{}:\n{:?}\n", name, map))
 494             })
 495             .collect::<String>();
 496
 497         expect.assert_eq(&actual)
 498     }
 499
 500     #[test]
 501     fn smoke() {
 502         check(
 503             r"
 504             //- /main.rs crate:main deps:lib
 505
 506             mod private {
 507                 pub use lib::Pub;
 508                 pub struct InPrivateModule;
 509             }
 510
 511             pub mod publ1 {
 512                 use lib::Pub;
 513             }
 514
 515             pub mod real_pub {
 516                 pub use lib::Pub;
 517             }
 518             pub mod real_pu2 { // same path length as above
 519                 pub use lib::Pub;
 520             }
 521
 522             //- /lib.rs crate:lib
 523             pub struct Pub {}
 524             pub struct Pub2; // t + v
 525             struct Priv;
 526         ",
 527             expect![[r#"
 528                 main:
 529                 - publ1 (t)
 530                 - real_pu2 (t)
 531                 - real_pub (t)
 532                 - real_pub::Pub (t)
 533                 lib:
 534                 - Pub (t)
 535                 - Pub2 (t)
 536                 - Pub2 (v)
 537             "#]],
 538         );
 539     }
 540
 541     #[test]
 542     fn prefers_shortest_path() {
 543         check(
 544             r"
 545             //- /main.rs crate:main
 546
 547             pub mod sub {
 548                 pub mod subsub {
 549                     pub struct Def {}
 550                 }
 551
 552                 pub use super::sub::subsub::Def;
 553             }
 554         ",
 555             expect![[r#"
 556                 main:
 557                 - sub (t)
 558                 - sub::Def (t)
 559                 - sub::subsub (t)
 560             "#]],
 561         );
 562     }
 563
 564     #[test]
 565     fn type_reexport_cross_crate() {
 566         // Reexports need to be visible from a crate, even if the original crate exports the item
 567         // at a shorter path.
 568         check(
 569             r"
 570             //- /main.rs crate:main deps:lib
 571             pub mod m {
 572                 pub use lib::S;
 573             }
 574             //- /lib.rs crate:lib
 575             pub struct S;
 576         ",
 577             expect![[r#"
 578                 main:
 579                 - m (t)
 580                 - m::S (t)
 581                 - m::S (v)
 582                 lib:
 583                 - S (t)
 584                 - S (v)
 585             "#]],
 586         );
 587     }
 588
 589     #[test]
 590     fn macro_reexport() {
 591         check(
 592             r"
 593             //- /main.rs crate:main deps:lib
 594             pub mod m {
 595                 pub use lib::pub_macro;
 596             }
 597             //- /lib.rs crate:lib
 598             #[macro_export]
 599             macro_rules! pub_macro {
 600                 () => {};
 601             }
 602         ",
 603             expect![[r#"
 604                 main:
 605                 - m (t)
 606                 - m::pub_macro (m)
 607                 lib:
 608                 - pub_macro (m)
 609             "#]],
 610         );
 611     }
 612
 613     #[test]
 614     fn module_reexport() {
 615         // Reexporting modules from a dependency adds all contents to the import map.
 616         check(
 617             r"
 618             //- /main.rs crate:main deps:lib
 619             pub use lib::module as reexported_module;
 620             //- /lib.rs crate:lib
 621             pub mod module {
 622                 pub struct S;
 623             }
 624         ",
 625             expect![[r#"
 626                 main:
 627                 - reexported_module (t)
 628                 - reexported_module::S (t)
 629                 - reexported_module::S (v)
 630                 lib:
 631                 - module (t)
 632                 - module::S (t)
 633                 - module::S (v)
 634             "#]],
 635         );
 636     }
 637
 638     #[test]
 639     fn cyclic_module_reexport() {
 640         // A cyclic reexport does not hang.
 641         check(
 642             r"
 643             //- /lib.rs crate:lib
 644             pub mod module {
 645                 pub struct S;
 646                 pub use super::sub::*;
 647             }
 648
 649             pub mod sub {
 650                 pub use super::module;
 651             }
 652         ",
 653             expect![[r#"
 654                 lib:
 655                 - module (t)
 656                 - module::S (t)
 657                 - module::S (v)
 658                 - sub (t)
 659             "#]],
 660         );
 661     }
 662
 663     #[test]
 664     fn private_macro() {
 665         check(
 666             r"
 667             //- /lib.rs crate:lib
 668             macro_rules! private_macro {
 669                 () => {};
 670             }
 671         ",
 672             expect![[r#"
 673                 lib:
 674
 675             "#]],
 676         );
 677     }
 678
 679     #[test]
 680     fn namespacing() {
 681         check(
 682             r"
 683             //- /lib.rs crate:lib
 684             pub struct Thing;     // t + v
 685             #[macro_export]
 686             macro_rules! Thing {  // m
 687                 () => {};
 688             }
 689         ",
 690             expect![[r#"
 691                 lib:
 692                 - Thing (m)
 693                 - Thing (t)
 694                 - Thing (v)
 695             "#]],
 696         );
 697
 698         check(
 699             r"
 700             //- /lib.rs crate:lib
 701             pub mod Thing {}      // t
 702             #[macro_export]
 703             macro_rules! Thing {  // m
 704                 () => {};
 705             }
 706         ",
 707             expect![[r#"
 708                 lib:
 709                 - Thing (m)
 710                 - Thing (t)
 711             "#]],
 712         );
 713     }
 714
 715     #[test]
 716     fn search() {
 717         let ra_fixture = r#"
 718             //- /main.rs crate:main deps:dep
 719             //- /dep.rs crate:dep deps:tdep
 720             use tdep::fmt as fmt_dep;
 721             pub mod fmt {
 722                 pub trait Display {
 723                     fn fmt();
 724                 }
 725             }
 726             #[macro_export]
 727             macro_rules! Fmt {
 728                 () => {};
 729             }
 730             pub struct Fmt;
 731
 732             pub fn format() {}
 733             pub fn no() {}
 734
 735             //- /tdep.rs crate:tdep
 736             pub mod fmt {
 737                 pub struct NotImportableFromMain;
 738             }
 739         "#;
 740
 741         check_search(
 742             ra_fixture,
 743             "main",
 744             Query::new("fmt"),
 745             expect![[r#"
 746                 dep::fmt (t)
 747                 dep::Fmt (t)
 748                 dep::Fmt (v)
 749                 dep::Fmt (m)
 750                 dep::fmt::Display (t)
 751                 dep::format (v)
 752                 dep::fmt::Display (t)
 753             "#]],
 754         );
 755
 756         check_search(
 757             ra_fixture,
 758             "main",
 759             Query::new("fmt").name_only().strict_include(),
 760             expect![[r#"
 761                 dep::fmt (t)
 762                 dep::Fmt (t)
 763                 dep::Fmt (v)
 764                 dep::Fmt (m)
 765                 dep::fmt::Display (t)
 766             "#]],
 767         );
 768     }
 769
 770     #[test]
 771     fn search_casing() {
 772         let ra_fixture = r#"
 773             //- /main.rs crate:main deps:dep
 774             //- /dep.rs crate:dep
 775
 776             pub struct fmt;
 777             pub struct FMT;
 778         "#;
 779
 780         check_search(
 781             ra_fixture,
 782             "main",
 783             Query::new("FMT"),
 784             expect![[r#"
 785                 dep::fmt (t)
 786                 dep::fmt (v)
 787                 dep::FMT (t)
 788                 dep::FMT (v)
 789             "#]],
 790         );
 791
 792         check_search(
 793             ra_fixture,
 794             "main",
 795             Query::new("FMT").case_sensitive(),
 796             expect![[r#"
 797                 dep::FMT (t)
 798                 dep::FMT (v)
 799             "#]],
 800         );
 801     }
 802
 803     #[test]
 804     fn search_limit() {
 805         check_search(
 806             r#"
 807         //- /main.rs crate:main deps:dep
 808         //- /dep.rs crate:dep
 809         pub mod fmt {
 810             pub trait Display {
 811                 fn fmt();
 812             }
 813         }
 814         #[macro_export]
 815         macro_rules! Fmt {
 816             () => {};
 817         }
 818         pub struct Fmt;
 819
 820         pub fn format() {}
 821         pub fn no() {}
 822     "#,
 823             "main",
 824             Query::new("").limit(2),
 825             expect![[r#"
 826                 dep::fmt (t)
 827                 dep::Fmt (t)
 828             "#]],
 829         );
 830     }
 831
 832     #[test]
 833     fn search_exclusions() {
 834         let ra_fixture = r#"
 835             //- /main.rs crate:main deps:dep
 836             //- /dep.rs crate:dep
 837
 838             pub struct fmt;
 839             pub struct FMT;
 840         "#;
 841
 842         check_search(
 843             ra_fixture,
 844             "main",
 845             Query::new("FMT"),
 846             expect![[r#"
 847                 dep::fmt (t)
 848                 dep::fmt (v)
 849                 dep::FMT (t)
 850                 dep::FMT (v)
 851             "#]],
 852         );
 853
 854         check_search(
 855             ra_fixture,
 856             "main",
 857             Query::new("FMT").exclude_import_kind(ImportKind::Adt),
 858             expect![[r#""#]],
 859         );
 860     }
 861 }