aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir_def/src/import_map.rs
diff options
context:
space:
mode:
authorAleksey Kladov <[email protected]>2020-08-13 15:28:27 +0100
committerAleksey Kladov <[email protected]>2020-08-13 15:29:33 +0100
commitb28c54a2c239acd73f2eea80fda9ee3960d2c046 (patch)
tree1bf0ea193bdb3b16ff42c2c01118b13a4276b2bb /crates/ra_hir_def/src/import_map.rs
parentb7aa4898e0841ab8199643f89a0caa967b698ca8 (diff)
Rename ra_hir_def -> hir_def
Diffstat (limited to 'crates/ra_hir_def/src/import_map.rs')
-rw-r--r--crates/ra_hir_def/src/import_map.rs745
1 files changed, 0 insertions, 745 deletions
diff --git a/crates/ra_hir_def/src/import_map.rs b/crates/ra_hir_def/src/import_map.rs
deleted file mode 100644
index d32a0bdaf..000000000
--- a/crates/ra_hir_def/src/import_map.rs
+++ /dev/null
@@ -1,745 +0,0 @@
1//! A map of all publicly exported items in a crate.
2
3use std::{cmp::Ordering, fmt, hash::BuildHasherDefault, sync::Arc};
4
5use base_db::CrateId;
6use fst::{self, Streamer};
7use indexmap::{map::Entry, IndexMap};
8use rustc_hash::{FxHashMap, FxHasher};
9use smallvec::SmallVec;
10use syntax::SmolStr;
11
12use crate::{
13 db::DefDatabase,
14 item_scope::ItemInNs,
15 path::{ModPath, PathKind},
16 visibility::Visibility,
17 AssocItemId, ModuleDefId, ModuleId, TraitId,
18};
19
20type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<FxHasher>>;
21
22/// Item import details stored in the `ImportMap`.
23#[derive(Debug, Clone, Eq, PartialEq)]
24pub struct ImportInfo {
25 /// A path that can be used to import the item, relative to the crate's root.
26 pub path: ModPath,
27 /// The module containing this item.
28 pub container: ModuleId,
29}
30
31/// A map from publicly exported items to the path needed to import/name them from a downstream
32/// crate.
33///
34/// Reexports of items are taken into account, ie. if something is exported under multiple
35/// names, the one with the shortest import path will be used.
36///
37/// Note that all paths are relative to the containing crate's root, so the crate name still needs
38/// to be prepended to the `ModPath` before the path is valid.
39#[derive(Default)]
40pub struct ImportMap {
41 map: FxIndexMap<ItemInNs, ImportInfo>,
42
43 /// List of keys stored in `map`, sorted lexicographically by their `ModPath`. Indexed by the
44 /// values returned by running `fst`.
45 ///
46 /// Since a path can refer to multiple items due to namespacing, we store all items with the
47 /// same path right after each other. This allows us to find all items after the FST gives us
48 /// the index of the first one.
49 importables: Vec<ItemInNs>,
50 fst: fst::Map<Vec<u8>>,
51
52 /// Maps names of associated items to the item's ID. Only includes items whose defining trait is
53 /// exported.
54 assoc_map: FxHashMap<SmolStr, SmallVec<[AssocItemId; 1]>>,
55}
56
57impl ImportMap {
58 pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<Self> {
59 let _p = profile::span("import_map_query");
60 let def_map = db.crate_def_map(krate);
61 let mut import_map = Self::default();
62
63 // We look only into modules that are public(ly reexported), starting with the crate root.
64 let empty = ModPath { kind: PathKind::Plain, segments: vec![] };
65 let root = ModuleId { krate, local_id: def_map.root };
66 let mut worklist = vec![(root, empty)];
67 while let Some((module, mod_path)) = worklist.pop() {
68 let ext_def_map;
69 let mod_data = if module.krate == krate {
70 &def_map[module.local_id]
71 } else {
72 // The crate might reexport a module defined in another crate.
73 ext_def_map = db.crate_def_map(module.krate);
74 &ext_def_map[module.local_id]
75 };
76
77 let visible_items = mod_data.scope.entries().filter_map(|(name, per_ns)| {
78 let per_ns = per_ns.filter_visibility(|vis| vis == Visibility::Public);
79 if per_ns.is_none() {
80 None
81 } else {
82 Some((name, per_ns))
83 }
84 });
85
86 for (name, per_ns) in visible_items {
87 let mk_path = || {
88 let mut path = mod_path.clone();
89 path.segments.push(name.clone());
90 path
91 };
92
93 for item in per_ns.iter_items() {
94 let path = mk_path();
95 match import_map.map.entry(item) {
96 Entry::Vacant(entry) => {
97 entry.insert(ImportInfo { path, container: module });
98 }
99 Entry::Occupied(mut entry) => {
100 // If the new path is shorter, prefer that one.
101 if path.len() < entry.get().path.len() {
102 *entry.get_mut() = ImportInfo { path, container: module };
103 } else {
104 continue;
105 }
106 }
107 }
108
109 // If we've just added a path to a module, descend into it. We might traverse
110 // modules multiple times, but only if the new path to it is shorter than the
111 // first (else we `continue` above).
112 if let Some(ModuleDefId::ModuleId(mod_id)) = item.as_module_def_id() {
113 worklist.push((mod_id, mk_path()));
114 }
115
116 // If we've added a path to a trait, add the trait's methods to the method map.
117 if let Some(ModuleDefId::TraitId(tr)) = item.as_module_def_id() {
118 import_map.collect_trait_methods(db, tr);
119 }
120 }
121 }
122 }
123
124 let mut importables = import_map.map.iter().collect::<Vec<_>>();
125
126 importables.sort_by(cmp);
127
128 // Build the FST, taking care not to insert duplicate values.
129
130 let mut builder = fst::MapBuilder::memory();
131 let mut last_batch_start = 0;
132
133 for idx in 0..importables.len() {
134 if let Some(next_item) = importables.get(idx + 1) {
135 if cmp(&importables[last_batch_start], next_item) == Ordering::Equal {
136 continue;
137 }
138 }
139
140 let start = last_batch_start;
141 last_batch_start = idx + 1;
142
143 let key = fst_path(&importables[start].1.path);
144
145 builder.insert(key, start as u64).unwrap();
146 }
147
148 import_map.fst = fst::Map::new(builder.into_inner().unwrap()).unwrap();
149 import_map.importables = importables.iter().map(|(item, _)| **item).collect();
150
151 Arc::new(import_map)
152 }
153
154 /// Returns the `ModPath` needed to import/mention `item`, relative to this crate's root.
155 pub fn path_of(&self, item: ItemInNs) -> Option<&ModPath> {
156 Some(&self.map.get(&item)?.path)
157 }
158
159 pub fn import_info_for(&self, item: ItemInNs) -> Option<&ImportInfo> {
160 self.map.get(&item)
161 }
162
163 fn collect_trait_methods(&mut self, db: &dyn DefDatabase, tr: TraitId) {
164 let data = db.trait_data(tr);
165 for (name, item) in data.items.iter() {
166 self.assoc_map.entry(name.to_string().into()).or_default().push(*item);
167 }
168 }
169}
170
171impl PartialEq for ImportMap {
172 fn eq(&self, other: &Self) -> bool {
173 // `fst` and `importables` are built from `map`, so we don't need to compare them.
174 self.map == other.map
175 }
176}
177
178impl Eq for ImportMap {}
179
180impl fmt::Debug for ImportMap {
181 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
182 let mut importable_paths: Vec<_> = self
183 .map
184 .iter()
185 .map(|(item, info)| {
186 let ns = match item {
187 ItemInNs::Types(_) => "t",
188 ItemInNs::Values(_) => "v",
189 ItemInNs::Macros(_) => "m",
190 };
191 format!("- {} ({})", info.path, ns)
192 })
193 .collect();
194
195 importable_paths.sort();
196 f.write_str(&importable_paths.join("\n"))
197 }
198}
199
200fn fst_path(path: &ModPath) -> String {
201 let mut s = path.to_string();
202 s.make_ascii_lowercase();
203 s
204}
205
206fn cmp((_, lhs): &(&ItemInNs, &ImportInfo), (_, rhs): &(&ItemInNs, &ImportInfo)) -> Ordering {
207 let lhs_str = fst_path(&lhs.path);
208 let rhs_str = fst_path(&rhs.path);
209 lhs_str.cmp(&rhs_str)
210}
211
212#[derive(Debug)]
213pub struct Query {
214 query: String,
215 lowercased: String,
216 anchor_end: bool,
217 case_sensitive: bool,
218 limit: usize,
219}
220
221impl Query {
222 pub fn new(query: &str) -> Self {
223 Self {
224 lowercased: query.to_lowercase(),
225 query: query.to_string(),
226 anchor_end: false,
227 case_sensitive: false,
228 limit: usize::max_value(),
229 }
230 }
231
232 /// Only returns items whose paths end with the (case-insensitive) query string as their last
233 /// segment.
234 pub fn anchor_end(self) -> Self {
235 Self { anchor_end: true, ..self }
236 }
237
238 /// Limits the returned number of items to `limit`.
239 pub fn limit(self, limit: usize) -> Self {
240 Self { limit, ..self }
241 }
242
243 /// Respect casing of the query string when matching.
244 pub fn case_sensitive(self) -> Self {
245 Self { case_sensitive: true, ..self }
246 }
247}
248
249/// Searches dependencies of `krate` for an importable path matching `query`.
250///
251/// This returns a list of items that could be imported from dependencies of `krate`.
252pub fn search_dependencies<'a>(
253 db: &'a dyn DefDatabase,
254 krate: CrateId,
255 query: Query,
256) -> Vec<ItemInNs> {
257 let _p = profile::span("search_dependencies").detail(|| format!("{:?}", query));
258
259 let graph = db.crate_graph();
260 let import_maps: Vec<_> =
261 graph[krate].dependencies.iter().map(|dep| db.import_map(dep.crate_id)).collect();
262
263 let automaton = fst::automaton::Subsequence::new(&query.lowercased);
264
265 let mut op = fst::map::OpBuilder::new();
266 for map in &import_maps {
267 op = op.add(map.fst.search(&automaton));
268 }
269
270 let mut stream = op.union();
271 let mut res = Vec::new();
272 while let Some((_, indexed_values)) = stream.next() {
273 for indexed_value in indexed_values {
274 let import_map = &import_maps[indexed_value.index];
275 let importables = &import_map.importables[indexed_value.value as usize..];
276
277 // Path shared by the importable items in this group.
278 let path = &import_map.map[&importables[0]].path;
279
280 if query.anchor_end {
281 // Last segment must match query.
282 let last = path.segments.last().unwrap().to_string();
283 if last.to_lowercase() != query.lowercased {
284 continue;
285 }
286 }
287
288 // Add the items from this `ModPath` group. Those are all subsequent items in
289 // `importables` whose paths match `path`.
290 let iter = importables.iter().copied().take_while(|item| {
291 let item_path = &import_map.map[item].path;
292 fst_path(item_path) == fst_path(path)
293 });
294
295 if query.case_sensitive {
296 // FIXME: This does not do a subsequence match.
297 res.extend(iter.filter(|item| {
298 let item_path = &import_map.map[item].path;
299 item_path.to_string().contains(&query.query)
300 }));
301 } else {
302 res.extend(iter);
303 }
304
305 if res.len() >= query.limit {
306 res.truncate(query.limit);
307 return res;
308 }
309 }
310 }
311
312 // Add all exported associated items whose names match the query (exactly).
313 for map in &import_maps {
314 if let Some(v) = map.assoc_map.get(&*query.query) {
315 res.extend(v.iter().map(|&assoc| {
316 ItemInNs::Types(match assoc {
317 AssocItemId::FunctionId(it) => it.into(),
318 AssocItemId::ConstId(it) => it.into(),
319 AssocItemId::TypeAliasId(it) => it.into(),
320 })
321 }));
322 }
323 }
324
325 res
326}
327
328#[cfg(test)]
329mod tests {
330 use base_db::{fixture::WithFixture, SourceDatabase, Upcast};
331 use expect::{expect, Expect};
332
333 use crate::{test_db::TestDB, AssocContainerId, Lookup};
334
335 use super::*;
336
337 fn check_search(ra_fixture: &str, krate_name: &str, query: Query, expect: Expect) {
338 let db = TestDB::with_files(ra_fixture);
339 let crate_graph = db.crate_graph();
340 let krate = crate_graph
341 .iter()
342 .find(|krate| {
343 crate_graph[*krate].display_name.as_ref().map(|n| n.to_string())
344 == Some(krate_name.to_string())
345 })
346 .unwrap();
347
348 let actual = search_dependencies(db.upcast(), krate, query)
349 .into_iter()
350 .filter_map(|item| {
351 let mark = match item {
352 ItemInNs::Types(_) => "t",
353 ItemInNs::Values(_) => "v",
354 ItemInNs::Macros(_) => "m",
355 };
356 let item = assoc_to_trait(&db, item);
357 item.krate(db.upcast()).map(|krate| {
358 let map = db.import_map(krate);
359 let path = map.path_of(item).unwrap();
360 format!(
361 "{}::{} ({})\n",
362 crate_graph[krate].display_name.as_ref().unwrap(),
363 path,
364 mark
365 )
366 })
367 })
368 .collect::<String>();
369 expect.assert_eq(&actual)
370 }
371
372 fn assoc_to_trait(db: &dyn DefDatabase, item: ItemInNs) -> ItemInNs {
373 let assoc: AssocItemId = match item {
374 ItemInNs::Types(it) | ItemInNs::Values(it) => match it {
375 ModuleDefId::TypeAliasId(it) => it.into(),
376 ModuleDefId::FunctionId(it) => it.into(),
377 ModuleDefId::ConstId(it) => it.into(),
378 _ => return item,
379 },
380 _ => return item,
381 };
382
383 let container = match assoc {
384 AssocItemId::FunctionId(it) => it.lookup(db).container,
385 AssocItemId::ConstId(it) => it.lookup(db).container,
386 AssocItemId::TypeAliasId(it) => it.lookup(db).container,
387 };
388
389 match container {
390 AssocContainerId::TraitId(it) => ItemInNs::Types(it.into()),
391 _ => item,
392 }
393 }
394
395 fn check(ra_fixture: &str, expect: Expect) {
396 let db = TestDB::with_files(ra_fixture);
397 let crate_graph = db.crate_graph();
398
399 let actual = crate_graph
400 .iter()
401 .filter_map(|krate| {
402 let cdata = &crate_graph[krate];
403 let name = cdata.display_name.as_ref()?;
404
405 let map = db.import_map(krate);
406
407 Some(format!("{}:\n{:?}\n", name, map))
408 })
409 .collect::<String>();
410
411 expect.assert_eq(&actual)
412 }
413
414 #[test]
415 fn smoke() {
416 check(
417 r"
418 //- /main.rs crate:main deps:lib
419
420 mod private {
421 pub use lib::Pub;
422 pub struct InPrivateModule;
423 }
424
425 pub mod publ1 {
426 use lib::Pub;
427 }
428
429 pub mod real_pub {
430 pub use lib::Pub;
431 }
432 pub mod real_pu2 { // same path length as above
433 pub use lib::Pub;
434 }
435
436 //- /lib.rs crate:lib
437 pub struct Pub {}
438 pub struct Pub2; // t + v
439 struct Priv;
440 ",
441 expect![[r#"
442 main:
443 - publ1 (t)
444 - real_pu2 (t)
445 - real_pub (t)
446 - real_pub::Pub (t)
447 lib:
448 - Pub (t)
449 - Pub2 (t)
450 - Pub2 (v)
451 "#]],
452 );
453 }
454
455 #[test]
456 fn prefers_shortest_path() {
457 check(
458 r"
459 //- /main.rs crate:main
460
461 pub mod sub {
462 pub mod subsub {
463 pub struct Def {}
464 }
465
466 pub use super::sub::subsub::Def;
467 }
468 ",
469 expect![[r#"
470 main:
471 - sub (t)
472 - sub::Def (t)
473 - sub::subsub (t)
474 "#]],
475 );
476 }
477
478 #[test]
479 fn type_reexport_cross_crate() {
480 // Reexports need to be visible from a crate, even if the original crate exports the item
481 // at a shorter path.
482 check(
483 r"
484 //- /main.rs crate:main deps:lib
485 pub mod m {
486 pub use lib::S;
487 }
488 //- /lib.rs crate:lib
489 pub struct S;
490 ",
491 expect![[r#"
492 main:
493 - m (t)
494 - m::S (t)
495 - m::S (v)
496 lib:
497 - S (t)
498 - S (v)
499 "#]],
500 );
501 }
502
503 #[test]
504 fn macro_reexport() {
505 check(
506 r"
507 //- /main.rs crate:main deps:lib
508 pub mod m {
509 pub use lib::pub_macro;
510 }
511 //- /lib.rs crate:lib
512 #[macro_export]
513 macro_rules! pub_macro {
514 () => {};
515 }
516 ",
517 expect![[r#"
518 main:
519 - m (t)
520 - m::pub_macro (m)
521 lib:
522 - pub_macro (m)
523 "#]],
524 );
525 }
526
527 #[test]
528 fn module_reexport() {
529 // Reexporting modules from a dependency adds all contents to the import map.
530 check(
531 r"
532 //- /main.rs crate:main deps:lib
533 pub use lib::module as reexported_module;
534 //- /lib.rs crate:lib
535 pub mod module {
536 pub struct S;
537 }
538 ",
539 expect![[r#"
540 main:
541 - reexported_module (t)
542 - reexported_module::S (t)
543 - reexported_module::S (v)
544 lib:
545 - module (t)
546 - module::S (t)
547 - module::S (v)
548 "#]],
549 );
550 }
551
552 #[test]
553 fn cyclic_module_reexport() {
554 // A cyclic reexport does not hang.
555 check(
556 r"
557 //- /lib.rs crate:lib
558 pub mod module {
559 pub struct S;
560 pub use super::sub::*;
561 }
562
563 pub mod sub {
564 pub use super::module;
565 }
566 ",
567 expect![[r#"
568 lib:
569 - module (t)
570 - module::S (t)
571 - module::S (v)
572 - sub (t)
573 "#]],
574 );
575 }
576
577 #[test]
578 fn private_macro() {
579 check(
580 r"
581 //- /lib.rs crate:lib
582 macro_rules! private_macro {
583 () => {};
584 }
585 ",
586 expect![[r#"
587 lib:
588
589 "#]],
590 );
591 }
592
593 #[test]
594 fn namespacing() {
595 check(
596 r"
597 //- /lib.rs crate:lib
598 pub struct Thing; // t + v
599 #[macro_export]
600 macro_rules! Thing { // m
601 () => {};
602 }
603 ",
604 expect![[r#"
605 lib:
606 - Thing (m)
607 - Thing (t)
608 - Thing (v)
609 "#]],
610 );
611
612 check(
613 r"
614 //- /lib.rs crate:lib
615 pub mod Thing {} // t
616 #[macro_export]
617 macro_rules! Thing { // m
618 () => {};
619 }
620 ",
621 expect![[r#"
622 lib:
623 - Thing (m)
624 - Thing (t)
625 "#]],
626 );
627 }
628
629 #[test]
630 fn search() {
631 let ra_fixture = r#"
632 //- /main.rs crate:main deps:dep
633 //- /dep.rs crate:dep deps:tdep
634 use tdep::fmt as fmt_dep;
635 pub mod fmt {
636 pub trait Display {
637 fn fmt();
638 }
639 }
640 #[macro_export]
641 macro_rules! Fmt {
642 () => {};
643 }
644 pub struct Fmt;
645
646 pub fn format() {}
647 pub fn no() {}
648
649 //- /tdep.rs crate:tdep
650 pub mod fmt {
651 pub struct NotImportableFromMain;
652 }
653 "#;
654
655 check_search(
656 ra_fixture,
657 "main",
658 Query::new("fmt"),
659 expect![[r#"
660 dep::fmt (t)
661 dep::Fmt (t)
662 dep::Fmt (v)
663 dep::Fmt (m)
664 dep::fmt::Display (t)
665 dep::format (v)
666 dep::fmt::Display (t)
667 "#]],
668 );
669
670 check_search(
671 ra_fixture,
672 "main",
673 Query::new("fmt").anchor_end(),
674 expect![[r#"
675 dep::fmt (t)
676 dep::Fmt (t)
677 dep::Fmt (v)
678 dep::Fmt (m)
679 dep::fmt::Display (t)
680 "#]],
681 );
682 }
683
684 #[test]
685 fn search_casing() {
686 let ra_fixture = r#"
687 //- /main.rs crate:main deps:dep
688 //- /dep.rs crate:dep
689
690 pub struct fmt;
691 pub struct FMT;
692 "#;
693
694 check_search(
695 ra_fixture,
696 "main",
697 Query::new("FMT"),
698 expect![[r#"
699 dep::fmt (t)
700 dep::fmt (v)
701 dep::FMT (t)
702 dep::FMT (v)
703 "#]],
704 );
705
706 check_search(
707 ra_fixture,
708 "main",
709 Query::new("FMT").case_sensitive(),
710 expect![[r#"
711 dep::FMT (t)
712 dep::FMT (v)
713 "#]],
714 );
715 }
716
717 #[test]
718 fn search_limit() {
719 check_search(
720 r#"
721 //- /main.rs crate:main deps:dep
722 //- /dep.rs crate:dep
723 pub mod fmt {
724 pub trait Display {
725 fn fmt();
726 }
727 }
728 #[macro_export]
729 macro_rules! Fmt {
730 () => {};
731 }
732 pub struct Fmt;
733
734 pub fn format() {}
735 pub fn no() {}
736 "#,
737 "main",
738 Query::new("").limit(2),
739 expect![[r#"
740 dep::fmt (t)
741 dep::Fmt (t)
742 "#]],
743 );
744 }
745}
generated by cgit v1.2.3 (git 2.25.1) at 2024-10-03 01:07:10 +0100