1 files changed, 679 insertions, 0 deletions

diff --git a/crates/ra_hir_def/src/import_map.rs b/crates/ra_hir_def/src/import_map.rs
new file mode 100644
index 000000000..68e20d06b
--- /dev/null
+++ b/crates/ra_hir_def/src/import_map.rs
@@ -0,0 +1,679 @@
+//! A map of all publicly exported items in a crate.
+
+use std::{cmp::Ordering, fmt, hash::BuildHasherDefault, sync::Arc};
+
+use fst::{self, Streamer};
+use indexmap::{map::Entry, IndexMap};
+use ra_db::CrateId;
+use rustc_hash::FxHasher;
+
+use crate::{
+    db::DefDatabase,
+    item_scope::ItemInNs,
+    path::{ModPath, PathKind},
+    visibility::Visibility,
+    ModuleDefId, ModuleId,
+};
+
+type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<FxHasher>>;
+
+/// Item import details stored in the `ImportMap`.
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub struct ImportInfo {
+    /// A path that can be used to import the item, relative to the crate's root.
+    pub path: ModPath,
+    /// The module containing this item.
+    pub container: ModuleId,
+}
+
+/// A map from publicly exported items to the path needed to import/name them from a downstream
+/// crate.
+///
+/// Reexports of items are taken into account, ie. if something is exported under multiple
+/// names, the one with the shortest import path will be used.
+///
+/// Note that all paths are relative to the containing crate's root, so the crate name still needs
+/// to be prepended to the `ModPath` before the path is valid.
+pub struct ImportMap {
+    map: FxIndexMap<ItemInNs, ImportInfo>,
+
+    /// List of keys stored in `map`, sorted lexicographically by their `ModPath`. Indexed by the
+    /// values returned by running `fst`.
+    ///
+    /// Since a path can refer to multiple items due to namespacing, we store all items with the
+    /// same path right after each other. This allows us to find all items after the FST gives us
+    /// the index of the first one.
+    importables: Vec<ItemInNs>,
+    fst: fst::Map<Vec<u8>>,
+}
+
+impl ImportMap {
+    pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<Self> {
+        let _p = ra_prof::profile("import_map_query");
+        let def_map = db.crate_def_map(krate);
+        let mut import_map = FxIndexMap::with_capacity_and_hasher(64, Default::default());
+
+        // We look only into modules that are public(ly reexported), starting with the crate root.
+        let empty = ModPath { kind: PathKind::Plain, segments: vec![] };
+        let root = ModuleId { krate, local_id: def_map.root };
+        let mut worklist = vec![(root, empty)];
+        while let Some((module, mod_path)) = worklist.pop() {
+            let ext_def_map;
+            let mod_data = if module.krate == krate {
+                &def_map[module.local_id]
+            } else {
+                // The crate might reexport a module defined in another crate.
+                ext_def_map = db.crate_def_map(module.krate);
+                &ext_def_map[module.local_id]
+            };
+
+            let visible_items = mod_data.scope.entries().filter_map(|(name, per_ns)| {
+                let per_ns = per_ns.filter_visibility(|vis| vis == Visibility::Public);
+                if per_ns.is_none() {
+                    None
+                } else {
+                    Some((name, per_ns))
+                }
+            });
+
+            for (name, per_ns) in visible_items {
+                let mk_path = || {
+                    let mut path = mod_path.clone();
+                    path.segments.push(name.clone());
+                    path
+                };
+
+                for item in per_ns.iter_items() {
+                    let path = mk_path();
+                    match import_map.entry(item) {
+                        Entry::Vacant(entry) => {
+                            entry.insert(ImportInfo { path, container: module });
+                        }
+                        Entry::Occupied(mut entry) => {
+                            // If the new path is shorter, prefer that one.
+                            if path.len() < entry.get().path.len() {
+                                *entry.get_mut() = ImportInfo { path, container: module };
+                            } else {
+                                continue;
+                            }
+                        }
+                    }
+
+                    // If we've just added a path to a module, descend into it. We might traverse
+                    // modules multiple times, but only if the new path to it is shorter than the
+                    // first (else we `continue` above).
+                    if let Some(ModuleDefId::ModuleId(mod_id)) = item.as_module_def_id() {
+                        worklist.push((mod_id, mk_path()));
+                    }
+                }
+            }
+        }
+
+        let mut importables = import_map.iter().collect::<Vec<_>>();
+
+        importables.sort_by(cmp);
+
+        // Build the FST, taking care not to insert duplicate values.
+
+        let mut builder = fst::MapBuilder::memory();
+        let mut last_batch_start = 0;
+
+        for idx in 0..importables.len() {
+            if let Some(next_item) = importables.get(idx + 1) {
+                if cmp(&importables[last_batch_start], next_item) == Ordering::Equal {
+                    continue;
+                }
+            }
+
+            let start = last_batch_start;
+            last_batch_start = idx + 1;
+
+            let key = fst_path(&importables[start].1.path);
+
+            builder.insert(key, start as u64).unwrap();
+        }
+
+        let fst = fst::Map::new(builder.into_inner().unwrap()).unwrap();
+        let importables = importables.iter().map(|(item, _)| **item).collect();
+
+        Arc::new(Self { map: import_map, fst, importables })
+    }
+
+    /// Returns the `ModPath` needed to import/mention `item`, relative to this crate's root.
+    pub fn path_of(&self, item: ItemInNs) -> Option<&ModPath> {
+        Some(&self.map.get(&item)?.path)
+    }
+
+    pub fn import_info_for(&self, item: ItemInNs) -> Option<&ImportInfo> {
+        self.map.get(&item)
+    }
+}
+
+impl PartialEq for ImportMap {
+    fn eq(&self, other: &Self) -> bool {
+        // `fst` and `importables` are built from `map`, so we don't need to compare them.
+        self.map == other.map
+    }
+}
+
+impl Eq for ImportMap {}
+
+impl fmt::Debug for ImportMap {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let mut importable_paths: Vec<_> = self
+            .map
+            .iter()
+            .map(|(item, info)| {
+                let ns = match item {
+                    ItemInNs::Types(_) => "t",
+                    ItemInNs::Values(_) => "v",
+                    ItemInNs::Macros(_) => "m",
+                };
+                format!("- {} ({})", info.path, ns)
+            })
+            .collect();
+
+        importable_paths.sort();
+        f.write_str(&importable_paths.join("\n"))
+    }
+}
+
+fn fst_path(path: &ModPath) -> String {
+    let mut s = path.to_string();
+    s.make_ascii_lowercase();
+    s
+}
+
+fn cmp((_, lhs): &(&ItemInNs, &ImportInfo), (_, rhs): &(&ItemInNs, &ImportInfo)) -> Ordering {
+    let lhs_str = fst_path(&lhs.path);
+    let rhs_str = fst_path(&rhs.path);
+    lhs_str.cmp(&rhs_str)
+}
+
+#[derive(Debug)]
+pub struct Query {
+    query: String,
+    lowercased: String,
+    anchor_end: bool,
+    case_sensitive: bool,
+    limit: usize,
+}
+
+impl Query {
+    pub fn new(query: &str) -> Self {
+        Self {
+            lowercased: query.to_lowercase(),
+            query: query.to_string(),
+            anchor_end: false,
+            case_sensitive: false,
+            limit: usize::max_value(),
+        }
+    }
+
+    /// Only returns items whose paths end with the (case-insensitive) query string as their last
+    /// segment.
+    pub fn anchor_end(self) -> Self {
+        Self { anchor_end: true, ..self }
+    }
+
+    /// Limits the returned number of items to `limit`.
+    pub fn limit(self, limit: usize) -> Self {
+        Self { limit, ..self }
+    }
+
+    /// Respect casing of the query string when matching.
+    pub fn case_sensitive(self) -> Self {
+        Self { case_sensitive: true, ..self }
+    }
+}
+
+/// Searches dependencies of `krate` for an importable path matching `query`.
+///
+/// This returns a list of items that could be imported from dependencies of `krate`.
+pub fn search_dependencies<'a>(
+    db: &'a dyn DefDatabase,
+    krate: CrateId,
+    query: Query,
+) -> Vec<ItemInNs> {
+    let _p = ra_prof::profile("search_dependencies").detail(|| format!("{:?}", query));
+
+    let graph = db.crate_graph();
+    let import_maps: Vec<_> =
+        graph[krate].dependencies.iter().map(|dep| db.import_map(dep.crate_id)).collect();
+
+    let automaton = fst::automaton::Subsequence::new(&query.lowercased);
+
+    let mut op = fst::map::OpBuilder::new();
+    for map in &import_maps {
+        op = op.add(map.fst.search(&automaton));
+    }
+
+    let mut stream = op.union();
+    let mut res = Vec::new();
+    while let Some((_, indexed_values)) = stream.next() {
+        for indexed_value in indexed_values {
+            let import_map = &import_maps[indexed_value.index];
+            let importables = &import_map.importables[indexed_value.value as usize..];
+
+            // Path shared by the importable items in this group.
+            let path = &import_map.map[&importables[0]].path;
+
+            if query.anchor_end {
+                // Last segment must match query.
+                let last = path.segments.last().unwrap().to_string();
+                if last.to_lowercase() != query.lowercased {
+                    continue;
+                }
+            }
+
+            // Add the items from this `ModPath` group. Those are all subsequent items in
+            // `importables` whose paths match `path`.
+            let iter = importables.iter().copied().take_while(|item| {
+                let item_path = &import_map.map[item].path;
+                fst_path(item_path) == fst_path(path)
+            });
+
+            if query.case_sensitive {
+                // FIXME: This does not do a subsequence match.
+                res.extend(iter.filter(|item| {
+                    let item_path = &import_map.map[item].path;
+                    item_path.to_string().contains(&query.query)
+                }));
+            } else {
+                res.extend(iter);
+            }
+
+            if res.len() >= query.limit {
+                res.truncate(query.limit);
+                return res;
+            }
+        }
+    }
+
+    res
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::test_db::TestDB;
+    use insta::assert_snapshot;
+    use itertools::Itertools;
+    use ra_db::fixture::WithFixture;
+    use ra_db::{SourceDatabase, Upcast};
+
+    fn import_map(ra_fixture: &str) -> String {
+        let db = TestDB::with_files(ra_fixture);
+        let crate_graph = db.crate_graph();
+
+        let s = crate_graph
+            .iter()
+            .filter_map(|krate| {
+                let cdata = &crate_graph[krate];
+                let name = cdata.display_name.as_ref()?;
+
+                let map = db.import_map(krate);
+
+                Some(format!("{}:\n{:?}", name, map))
+            })
+            .join("\n");
+        s
+    }
+
+    fn search_dependencies_of(ra_fixture: &str, krate_name: &str, query: Query) -> String {
+        let db = TestDB::with_files(ra_fixture);
+        let crate_graph = db.crate_graph();
+        let krate = crate_graph
+            .iter()
+            .find(|krate| {
+                crate_graph[*krate].display_name.as_ref().map(|n| n.to_string())
+                    == Some(krate_name.to_string())
+            })
+            .unwrap();
+
+        search_dependencies(db.upcast(), krate, query)
+            .into_iter()
+            .filter_map(|item| {
+                let mark = match item {
+                    ItemInNs::Types(_) => "t",
+                    ItemInNs::Values(_) => "v",
+                    ItemInNs::Macros(_) => "m",
+                };
+                item.krate(db.upcast()).map(|krate| {
+                    let map = db.import_map(krate);
+                    let path = map.path_of(item).unwrap();
+                    format!(
+                        "{}::{} ({})",
+                        crate_graph[krate].display_name.as_ref().unwrap(),
+                        path,
+                        mark
+                    )
+                })
+            })
+            .join("\n")
+    }
+
+    #[test]
+    fn smoke() {
+        let map = import_map(
+            r"
+            //- /main.rs crate:main deps:lib
+
+            mod private {
+                pub use lib::Pub;
+                pub struct InPrivateModule;
+            }
+
+            pub mod publ1 {
+                use lib::Pub;
+            }
+
+            pub mod real_pub {
+                pub use lib::Pub;
+            }
+            pub mod real_pu2 { // same path length as above
+                pub use lib::Pub;
+            }
+
+            //- /lib.rs crate:lib
+            pub struct Pub {}
+            pub struct Pub2; // t + v
+            struct Priv;
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - publ1 (t)
+        - real_pu2 (t)
+        - real_pub (t)
+        - real_pub::Pub (t)
+        lib:
+        - Pub (t)
+        - Pub2 (t)
+        - Pub2 (v)
+        "###);
+    }
+
+    #[test]
+    fn prefers_shortest_path() {
+        let map = import_map(
+            r"
+            //- /main.rs crate:main
+
+            pub mod sub {
+                pub mod subsub {
+                    pub struct Def {}
+                }
+
+                pub use super::sub::subsub::Def;
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - sub (t)
+        - sub::Def (t)
+        - sub::subsub (t)
+        "###);
+    }
+
+    #[test]
+    fn type_reexport_cross_crate() {
+        // Reexports need to be visible from a crate, even if the original crate exports the item
+        // at a shorter path.
+        let map = import_map(
+            r"
+            //- /main.rs crate:main deps:lib
+            pub mod m {
+                pub use lib::S;
+            }
+            //- /lib.rs crate:lib
+            pub struct S;
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - m (t)
+        - m::S (t)
+        - m::S (v)
+        lib:
+        - S (t)
+        - S (v)
+        "###);
+    }
+
+    #[test]
+    fn macro_reexport() {
+        let map = import_map(
+            r"
+            //- /main.rs crate:main deps:lib
+            pub mod m {
+                pub use lib::pub_macro;
+            }
+            //- /lib.rs crate:lib
+            #[macro_export]
+            macro_rules! pub_macro {
+                () => {};
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - m (t)
+        - m::pub_macro (m)
+        lib:
+        - pub_macro (m)
+        "###);
+    }
+
+    #[test]
+    fn module_reexport() {
+        // Reexporting modules from a dependency adds all contents to the import map.
+        let map = import_map(
+            r"
+            //- /main.rs crate:main deps:lib
+            pub use lib::module as reexported_module;
+            //- /lib.rs crate:lib
+            pub mod module {
+                pub struct S;
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - reexported_module (t)
+        - reexported_module::S (t)
+        - reexported_module::S (v)
+        lib:
+        - module (t)
+        - module::S (t)
+        - module::S (v)
+        "###);
+    }
+
+    #[test]
+    fn cyclic_module_reexport() {
+        // A cyclic reexport does not hang.
+        let map = import_map(
+            r"
+            //- /lib.rs crate:lib
+            pub mod module {
+                pub struct S;
+                pub use super::sub::*;
+            }
+
+            pub mod sub {
+                pub use super::module;
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        lib:
+        - module (t)
+        - module::S (t)
+        - module::S (v)
+        - sub (t)
+        "###);
+    }
+
+    #[test]
+    fn private_macro() {
+        let map = import_map(
+            r"
+            //- /lib.rs crate:lib
+            macro_rules! private_macro {
+                () => {};
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        lib:
+        "###);
+    }
+
+    #[test]
+    fn namespacing() {
+        let map = import_map(
+            r"
+            //- /lib.rs crate:lib
+            pub struct Thing;     // t + v
+            #[macro_export]
+            macro_rules! Thing {  // m
+                () => {};
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        lib:
+        - Thing (m)
+        - Thing (t)
+        - Thing (v)
+        "###);
+
+        let map = import_map(
+            r"
+            //- /lib.rs crate:lib
+            pub mod Thing {}      // t
+            #[macro_export]
+            macro_rules! Thing {  // m
+                () => {};
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        lib:
+        - Thing (m)
+        - Thing (t)
+        "###);
+    }
+
+    #[test]
+    fn search() {
+        let ra_fixture = r#"
+            //- /main.rs crate:main deps:dep
+            //- /dep.rs crate:dep deps:tdep
+            use tdep::fmt as fmt_dep;
+            pub mod fmt {
+                pub trait Display {
+                    fn fmt();
+                }
+            }
+            #[macro_export]
+            macro_rules! Fmt {
+                () => {};
+            }
+            pub struct Fmt;
+
+            pub fn format() {}
+            pub fn no() {}
+
+            //- /tdep.rs crate:tdep
+            pub mod fmt {
+                pub struct NotImportableFromMain;
+            }
+        "#;
+
+        let res = search_dependencies_of(ra_fixture, "main", Query::new("fmt"));
+        assert_snapshot!(res, @r###"
+        dep::fmt (t)
+        dep::Fmt (t)
+        dep::Fmt (v)
+        dep::Fmt (m)
+        dep::fmt::Display (t)
+        dep::format (v)
+        "###);
+
+        let res = search_dependencies_of(ra_fixture, "main", Query::new("fmt").anchor_end());
+        assert_snapshot!(res, @r###"
+        dep::fmt (t)
+        dep::Fmt (t)
+        dep::Fmt (v)
+        dep::Fmt (m)
+        "###);
+    }
+
+    #[test]
+    fn search_casing() {
+        let ra_fixture = r#"
+            //- /main.rs crate:main deps:dep
+            //- /dep.rs crate:dep
+
+            pub struct fmt;
+            pub struct FMT;
+        "#;
+
+        let res = search_dependencies_of(ra_fixture, "main", Query::new("FMT"));
+
+        assert_snapshot!(res, @r###"
+        dep::fmt (t)
+        dep::fmt (v)
+        dep::FMT (t)
+        dep::FMT (v)
+        "###);
+
+        let res = search_dependencies_of(ra_fixture, "main", Query::new("FMT").case_sensitive());
+
+        assert_snapshot!(res, @r###"
+        dep::FMT (t)
+        dep::FMT (v)
+        "###);
+    }
+
+    #[test]
+    fn search_limit() {
+        let res = search_dependencies_of(
+            r#"
+        //- /main.rs crate:main deps:dep
+        //- /dep.rs crate:dep
+        pub mod fmt {
+            pub trait Display {
+                fn fmt();
+            }
+        }
+        #[macro_export]
+        macro_rules! Fmt {
+            () => {};
+        }
+        pub struct Fmt;
+
+        pub fn format() {}
+        pub fn no() {}
+    "#,
+            "main",
+            Query::new("").limit(2),
+        );
+        assert_snapshot!(res, @r###"
+        dep::fmt (t)
+        dep::Fmt (t)
+        "###);
+    }
+}