Only store item name instead of full path

2 files changed, 149 insertions, 214 deletions

diff --git a/crates/hir-def/src/find_path.rs b/crates/hir-def/src/find_path.rs
index 8c49ae1c4af..df2af4c89b0 100644
--- a/crates/hir-def/src/find_path.rs
+++ b/crates/hir-def/src/find_path.rs
@@ -360,7 +360,7 @@ fn calculate_best_path(
                     prefer_no_std,
                 )?;
                 cov_mark::hit!(partially_imported);
-                path.push_segment(info.path.segments.last()?.clone());
+                path.push_segment(info.name.clone());
                 Some(path)
             })
         });
diff --git a/crates/hir-def/src/import_map.rs b/crates/hir-def/src/import_map.rs
index fb7870c72f3..63caaa8f831 100644
--- a/crates/hir-def/src/import_map.rs
+++ b/crates/hir-def/src/import_map.rs
@@ -1,13 +1,14 @@
 //! A map of all publicly exported items in a crate.
 
+use std::collections::hash_map::Entry;
 use std::{fmt, hash::BuildHasherDefault};
 
 use base_db::CrateId;
 use fst::{self, Streamer};
 use hir_expand::name::Name;
-use indexmap::{map::Entry, IndexMap};
+use indexmap::IndexMap;
 use itertools::Itertools;
-use rustc_hash::{FxHashSet, FxHasher};
+use rustc_hash::{FxHashMap, FxHashSet, FxHasher};
 use triomphe::Arc;
 
 use crate::{
@@ -17,52 +18,23 @@ use crate::{
 
 type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<FxHasher>>;
 
+// FIXME: Support aliases: an item may be exported under multiple names, so `ImportInfo` should
+// have `Vec<(Name, ModuleId)>` instead of `(Name, ModuleId)`.
 /// 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: ImportPath,
+    /// A name that can be used to import the item, relative to the crate's root.
+    pub name: Name,
     /// The module containing this item.
     pub container: ModuleId,
     /// Whether the import is a trait associated item or not.
     pub is_trait_assoc_item: bool,
 }
 
-#[derive(Debug, Clone, Eq, PartialEq)]
-pub struct ImportPath {
-    pub segments: Vec<Name>,
-}
-
-impl ImportPath {
-    pub fn display<'a>(&'a self, db: &'a dyn DefDatabase) -> impl fmt::Display + 'a {
-        struct Display<'a> {
-            db: &'a dyn DefDatabase,
-            path: &'a ImportPath,
-        }
-        impl fmt::Display for Display<'_> {
-            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-                fmt::Display::fmt(
-                    &self.path.segments.iter().map(|it| it.display(self.db.upcast())).format("::"),
-                    f,
-                )
-            }
-        }
-        Display { db, path: self }
-    }
-
-    fn len(&self) -> usize {
-        self.segments.len()
-    }
-}
-
-/// A map from publicly exported items to the path needed to import/name them from a downstream
-/// crate.
+/// A map from publicly exported items to its name.
 ///
 /// 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.
 #[derive(Default)]
 pub struct ImportMap {
     map: FxIndexMap<ItemInNs, ImportInfo>,
@@ -70,84 +42,50 @@ pub struct ImportMap {
     /// 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
+    /// Since a name can refer to multiple items due to namespacing, we store all items with the
+    /// same name 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> {
+    pub(crate) fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<Self> {
         let _p = profile::span("import_map_query");
 
         let mut import_map = collect_import_map(db, krate);
 
-        let mut importables = import_map
+        let mut importables: Vec<_> = import_map
             .map
             .iter()
-            .map(|(item, info)| (item, fst_path(db, &info.path)))
-            .collect::<Vec<_>>();
-        importables.sort_by(|(_, fst_path), (_, fst_path2)| fst_path.cmp(fst_path2));
+            // We've only collected items, whose name cannot be tuple field.
+            .map(|(item, info)| (item, info.name.as_str().unwrap().to_ascii_lowercase()))
+            .collect();
+        importables.sort_by(|(_, lhs_name), (_, rhs_name)| lhs_name.cmp(rhs_name));
 
         // 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() {
-            let key = &importables[last_batch_start].1;
-            if let Some((_, fst_path)) = importables.get(idx + 1) {
-                if key == fst_path {
-                    continue;
-                }
-            }
-
-            let _ = builder.insert(key, last_batch_start as u64);
-
-            last_batch_start = idx + 1;
+        let iter = importables.iter().enumerate().dedup_by(|lhs, rhs| lhs.1 .1 == rhs.1 .1);
+        for (start_idx, (_, name)) in iter {
+            let _ = builder.insert(name, start_idx as u64);
         }
 
         import_map.fst = builder.into_map();
-        import_map.importables = importables.iter().map(|&(&item, _)| item).collect();
+        import_map.importables = importables.into_iter().map(|(&item, _)| item).collect();
 
         Arc::new(import_map)
     }
 
-    /// Returns the `ModPath` needed to import/mention `item`, relative to this crate's root.
-    pub fn path_of(&self, item: ItemInNs) -> Option<&ImportPath> {
-        self.import_info_for(item).map(|it| &it.path)
-    }
-
     pub fn import_info_for(&self, item: ItemInNs) -> Option<&ImportInfo> {
         self.map.get(&item)
     }
 
-    #[cfg(test)]
-    fn fmt_for_test(&self, db: &dyn DefDatabase) -> String {
-        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!("- {} ({ns})", info.path.display(db))
-            })
-            .collect();
-
-        importable_paths.sort();
-        importable_paths.join("\n")
-    }
-
     fn collect_trait_assoc_items(
         &mut self,
         db: &dyn DefDatabase,
         tr: TraitId,
         is_type_in_ns: bool,
-        original_import_info: &ImportInfo,
+        trait_import_info: &ImportInfo,
     ) {
         let _p = profile::span("collect_trait_assoc_items");
         for (assoc_item_name, item) in &db.trait_data(tr).items {
@@ -167,9 +105,11 @@ impl ImportMap {
                 ItemInNs::Values(module_def_id)
             };
 
-            let mut assoc_item_info = original_import_info.clone();
-            assoc_item_info.path.segments.push(assoc_item_name.to_owned());
-            assoc_item_info.is_trait_assoc_item = true;
+            let assoc_item_info = ImportInfo {
+                container: trait_import_info.container,
+                name: assoc_item_name.clone(),
+                is_trait_assoc_item: true,
+            };
             self.map.insert(assoc_item, assoc_item_info);
         }
     }
@@ -182,10 +122,10 @@ fn collect_import_map(db: &dyn DefDatabase, krate: CrateId) -> ImportMap {
     let mut import_map = ImportMap::default();
 
     // We look only into modules that are public(ly reexported), starting with the crate root.
-    let empty = ImportPath { segments: vec![] };
     let root = def_map.module_id(DefMap::ROOT);
-    let mut worklist = vec![(root, empty)];
-    while let Some((module, mod_path)) = worklist.pop() {
+    let mut worklist = vec![(root, 0)];
+    let mut depth_map = FxHashMap::default();
+    while let Some((module, depth)) = worklist.pop() {
         let ext_def_map;
         let mod_data = if module.krate == krate {
             &def_map[module.local_id]
@@ -205,17 +145,25 @@ fn collect_import_map(db: &dyn DefDatabase, krate: CrateId) -> ImportMap {
         });
 
         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();
-                let path_len = path.len();
-                let import_info =
-                    ImportInfo { path, container: module, is_trait_assoc_item: false };
+                let import_info = ImportInfo {
+                    name: name.clone(),
+                    container: module,
+                    is_trait_assoc_item: false,
+                };
+
+                match depth_map.entry(item) {
+                    Entry::Vacant(entry) => {
+                        entry.insert(depth);
+                    }
+                    Entry::Occupied(mut entry) => {
+                        if depth < *entry.get() {
+                            entry.insert(depth);
+                        } else {
+                            continue;
+                        }
+                    }
+                }
 
                 if let Some(ModuleDefId::TraitId(tr)) = item.as_module_def_id() {
                     import_map.collect_trait_assoc_items(
@@ -226,25 +174,13 @@ fn collect_import_map(db: &dyn DefDatabase, krate: CrateId) -> ImportMap {
                     );
                 }
 
-                match import_map.map.entry(item) {
-                    Entry::Vacant(entry) => {
-                        entry.insert(import_info);
-                    }
-                    Entry::Occupied(mut entry) => {
-                        // If the new path is shorter, prefer that one.
-                        if path_len < entry.get().path.len() {
-                            *entry.get_mut() = import_info;
-                        } else {
-                            continue;
-                        }
-                    }
-                }
+                import_map.map.insert(item, import_info);
 
-                // 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 we've just added a module, descend into it. We might traverse modules
+                // multiple times, but only if the module depth is smaller (else we `continue`
+                // above).
                 if let Some(ModuleDefId::ModuleId(mod_id)) = item.as_module_def_id() {
-                    worklist.push((mod_id, mk_path()));
+                    worklist.push((mod_id, depth + 1));
                 }
             }
         }
@@ -264,7 +200,7 @@ impl Eq for ImportMap {}
 
 impl fmt::Debug for ImportMap {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        let mut importable_paths: Vec<_> = self
+        let mut importable_names: Vec<_> = self
             .map
             .iter()
             .map(|(item, _)| match item {
@@ -274,18 +210,11 @@ impl fmt::Debug for ImportMap {
             })
             .collect();
 
-        importable_paths.sort();
-        f.write_str(&importable_paths.join("\n"))
+        importable_names.sort();
+        f.write_str(&importable_names.join("\n"))
     }
 }
 
-fn fst_path(db: &dyn DefDatabase, path: &ImportPath) -> String {
-    let _p = profile::span("fst_path");
-    let mut s = path.display(db).to_string();
-    s.make_ascii_lowercase();
-    s
-}
-
 /// A way to match import map contents against the search query.
 #[derive(Debug)]
 enum SearchMode {
@@ -363,7 +292,7 @@ impl Query {
             _ => {}
         }
 
-        let mut input = import.path.segments.last().unwrap().display(db.upcast()).to_string();
+        let mut input = import.name.display(db.upcast()).to_string();
         let case_insensitive = enforce_lowercase || !self.case_sensitive;
         if case_insensitive {
             input.make_ascii_lowercase();
@@ -386,7 +315,7 @@ impl Query {
     }
 }
 
-/// Searches dependencies of `krate` for an importable path matching `query`.
+/// Searches dependencies of `krate` for an importable name matching `query`.
 ///
 /// This returns a list of items that could be imported from dependencies of `krate`.
 pub fn search_dependencies(
@@ -409,39 +338,38 @@ pub fn search_dependencies(
 
     let mut stream = op.union();
 
-    let mut all_indexed_values = FxHashSet::default();
-    while let Some((_, indexed_values)) = stream.next() {
-        all_indexed_values.extend(indexed_values.iter().copied());
-    }
-
     let mut res = FxHashSet::default();
-    for indexed_value in all_indexed_values {
-        let import_map = &import_maps[indexed_value.index];
-        let importables = &import_map.importables[indexed_value.value as usize..];
+    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..];
 
-        let common_importable_data = &import_map.map[&importables[0]];
-        if !query.import_matches(db, common_importable_data, true) {
-            continue;
-        }
+            let common_importable_data = &import_map.map[&importables[0]];
+            if !query.import_matches(db, common_importable_data, true) {
+                continue;
+            }
 
-        // Path shared by the importable items in this group.
-        let common_importables_path_fst = fst_path(db, &common_importable_data.path);
-        // 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| {
-                common_importables_path_fst == fst_path(db, &import_map.map[item].path)
-            })
-            .filter(|item| {
-                !query.case_sensitive // we've already checked the common importables path case-insensitively
+            // Name shared by the importable items in this group.
+            let common_importable_name =
+                common_importable_data.name.to_smol_str().to_ascii_lowercase();
+            // Add the items from this name group. Those are all subsequent items in
+            // `importables` whose name match `common_importable_name`.
+            let iter = importables
+                .iter()
+                .copied()
+                .take_while(|item| {
+                    common_importable_name
+                        == import_map.map[item].name.to_smol_str().to_ascii_lowercase()
+                })
+                .filter(|item| {
+                    !query.case_sensitive // we've already checked the common importables name case-insensitively
                         || query.import_matches(db, &import_map.map[item], false)
-            });
-        res.extend(iter);
+                });
+            res.extend(iter);
 
-        if res.len() >= query.limit {
-            return res;
+            if res.len() >= query.limit {
+                return res;
+            }
         }
     }
 
@@ -457,16 +385,39 @@ mod tests {
 
     use super::*;
 
+    impl ImportMap {
+        fn fmt_for_test(&self, db: &dyn DefDatabase) -> String {
+            let mut importable_paths: Vec<_> = self
+                .map
+                .iter()
+                .map(|(item, info)| {
+                    let path = render_path(db, info);
+                    let ns = match item {
+                        ItemInNs::Types(_) => "t",
+                        ItemInNs::Values(_) => "v",
+                        ItemInNs::Macros(_) => "m",
+                    };
+                    format!("- {path} ({ns})")
+                })
+                .collect();
+
+            importable_paths.sort();
+            importable_paths.join("\n")
+        }
+    }
+
     fn check_search(ra_fixture: &str, crate_name: &str, query: Query, expect: Expect) {
         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(crate_name.to_string())
+            .find(|&krate| {
+                crate_graph[krate]
+                    .display_name
+                    .as_ref()
+                    .is_some_and(|it| &**it.crate_name() == crate_name)
             })
-            .unwrap();
+            .expect("could not find crate");
 
         let actual = search_dependencies(db.upcast(), krate, query)
             .into_iter()
@@ -477,7 +428,7 @@ mod tests {
                 let (path, mark) = match assoc_item_path(&db, &dependency_imports, dependency) {
                     Some(assoc_item_path) => (assoc_item_path, "a"),
                     None => (
-                        dependency_imports.path_of(dependency)?.display(&db).to_string(),
+                        render_path(&db, dependency_imports.import_info_for(dependency)?),
                         match dependency {
                             ItemInNs::Types(ModuleDefId::FunctionId(_))
                             | ItemInNs::Values(ModuleDefId::FunctionId(_)) => "f",
@@ -507,57 +458,25 @@ mod tests {
         dependency_imports: &ImportMap,
         dependency: ItemInNs,
     ) -> Option<String> {
-        let dependency_assoc_item_id = match dependency {
-            ItemInNs::Types(ModuleDefId::FunctionId(id))
-            | ItemInNs::Values(ModuleDefId::FunctionId(id)) => AssocItemId::from(id),
-            ItemInNs::Types(ModuleDefId::ConstId(id))
-            | ItemInNs::Values(ModuleDefId::ConstId(id)) => AssocItemId::from(id),
-            ItemInNs::Types(ModuleDefId::TypeAliasId(id))
-            | ItemInNs::Values(ModuleDefId::TypeAliasId(id)) => AssocItemId::from(id),
+        let (dependency_assoc_item_id, container) = match dependency.as_module_def_id()? {
+            ModuleDefId::FunctionId(id) => (AssocItemId::from(id), id.lookup(db).container),
+            ModuleDefId::ConstId(id) => (AssocItemId::from(id), id.lookup(db).container),
+            ModuleDefId::TypeAliasId(id) => (AssocItemId::from(id), id.lookup(db).container),
             _ => return None,
         };
 
-        let trait_ = assoc_to_trait(db, dependency)?;
-        if let ModuleDefId::TraitId(tr) = trait_.as_module_def_id()? {
-            let trait_data = db.trait_data(tr);
-            let assoc_item_name =
-                trait_data.items.iter().find_map(|(assoc_item_name, assoc_item_id)| {
-                    if &dependency_assoc_item_id == assoc_item_id {
-                        Some(assoc_item_name)
-                    } else {
-                        None
-                    }
-                })?;
-            return Some(format!(
-                "{}::{}",
-                dependency_imports.path_of(trait_)?.display(db),
-                assoc_item_name.display(db.upcast())
-            ));
-        }
-        None
-    }
-
-    fn assoc_to_trait(db: &dyn DefDatabase, item: ItemInNs) -> Option<ItemInNs> {
-        let assoc: AssocItemId = match item {
-            ItemInNs::Types(it) | ItemInNs::Values(it) => match it {
-                ModuleDefId::TypeAliasId(it) => it.into(),
-                ModuleDefId::FunctionId(it) => it.into(),
-                ModuleDefId::ConstId(it) => it.into(),
-                _ => return None,
-            },
-            _ => return None,
+        let ItemContainerId::TraitId(trait_id) = container else {
+            return None;
         };
 
-        let container = match assoc {
-            AssocItemId::FunctionId(it) => it.lookup(db).container,
-            AssocItemId::ConstId(it) => it.lookup(db).container,
-            AssocItemId::TypeAliasId(it) => it.lookup(db).container,
-        };
+        let trait_info = dependency_imports.import_info_for(ItemInNs::Types(trait_id.into()))?;
 
-        match container {
-            ItemContainerId::TraitId(it) => Some(ItemInNs::Types(it.into())),
-            _ => None,
-        }
+        let trait_data = db.trait_data(trait_id);
+        let (assoc_item_name, _) = trait_data
+            .items
+            .iter()
+            .find(|(_, assoc_item_id)| &dependency_assoc_item_id == assoc_item_id)?;
+        Some(format!("{}::{}", render_path(db, trait_info), assoc_item_name.display(db.upcast())))
     }
 
     fn check(ra_fixture: &str, expect: Expect) {
@@ -580,6 +499,24 @@ mod tests {
         expect.assert_eq(&actual)
     }
 
+    fn render_path(db: &dyn DefDatabase, info: &ImportInfo) -> String {
+        let mut module = info.container;
+        let mut segments = vec![&info.name];
+
+        let def_map = module.def_map(db);
+        assert!(def_map.block_id().is_none(), "block local items should not be in `ImportMap`");
+
+        while let Some(parent) = module.containing_module(db) {
+            let parent_data = &def_map[parent.local_id];
+            let (name, _) =
+                parent_data.children.iter().find(|(_, id)| **id == module.local_id).unwrap();
+            segments.push(name);
+            module = parent;
+        }
+
+        segments.iter().rev().map(|it| it.display(db.upcast())).join("::")
+    }
+
     #[test]
     fn smoke() {
         check(
@@ -696,6 +633,7 @@ mod tests {
     #[test]
     fn module_reexport() {
         // Reexporting modules from a dependency adds all contents to the import map.
+        // XXX: The rendered paths are relative to the defining crate.
         check(
             r"
             //- /main.rs crate:main deps:lib
@@ -711,9 +649,9 @@ mod tests {
                 - module::S (t)
                 - module::S (v)
                 main:
+                - module::S (t)
+                - module::S (v)
                 - reexported_module (t)
-                - reexported_module::S (t)
-                - reexported_module::S (v)
             "#]],
         );
     }
@@ -1025,12 +963,9 @@ mod tests {
         pub fn no() {}
     "#,
             "main",
-            Query::new("".to_string()).fuzzy().limit(2),
+            Query::new("".to_string()).fuzzy().limit(1),
             expect![[r#"
-                dep::Fmt (m)
-                dep::Fmt (t)
-                dep::Fmt (v)
-                dep::fmt (t)
+                dep::fmt::Display (t)
             "#]],
         );
     }