bendns' repos / rust-analyzer
Unnamed repository; edit this file 'description' to name the repository.
Diffstat (limited to 'crates/hir-def/src/find_path.rs')
-rw-r--r--crates/hir-def/src/find_path.rs313
1 files changed, 138 insertions, 175 deletions
diff --git a/crates/hir-def/src/find_path.rs b/crates/hir-def/src/find_path.rs
index d9495d36c0..58a1872ef2 100644
--- a/crates/hir-def/src/find_path.rs
+++ b/crates/hir-def/src/find_path.rs
@@ -1,6 +1,6 @@
//! An algorithm to find a path to refer to a certain item.
-use std::{cmp::Ordering, iter};
+use std::{cell::Cell, cmp::Ordering, iter};
use hir_expand::{
name::{known, AsName, Name},
@@ -23,15 +23,40 @@ pub fn find_path(
db: &dyn DefDatabase,
item: ItemInNs,
from: ModuleId,
- prefix_kind: PrefixKind,
+ mut prefix_kind: PrefixKind,
ignore_local_imports: bool,
- cfg: ImportPathConfig,
+ mut cfg: ImportPathConfig,
) -> Option<ModPath> {
- let _p = tracing::span!(tracing::Level::INFO, "find_path").entered();
- find_path_inner(FindPathCtx { db, prefix: prefix_kind, cfg, ignore_local_imports }, item, from)
+ let _p = tracing::info_span!("find_path").entered();
+
+ // - if the item is a builtin, it's in scope
+ if let ItemInNs::Types(ModuleDefId::BuiltinType(builtin)) = item {
+ return Some(ModPath::from_segments(PathKind::Plain, iter::once(builtin.as_name())));
+ }
+
+ // within block modules, forcing a `self` or `crate` prefix will not allow using inner items, so
+ // default to plain paths.
+ if item.module(db).is_some_and(ModuleId::is_within_block) {
+ prefix_kind = PrefixKind::Plain;
+ }
+ cfg.prefer_no_std = cfg.prefer_no_std || db.crate_supports_no_std(from.krate());
+
+ find_path_inner(
+ &FindPathCtx {
+ db,
+ prefix: prefix_kind,
+ cfg,
+ ignore_local_imports,
+ from,
+ from_def_map: &from.def_map(db),
+ fuel: Cell::new(FIND_PATH_FUEL),
+ },
+ item,
+ MAX_PATH_LEN,
+ )
}
-#[derive(Copy, Clone, Debug)]
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
enum Stability {
Unstable,
Stable,
@@ -46,6 +71,7 @@ fn zip_stability(a: Stability, b: Stability) -> Stability {
}
const MAX_PATH_LEN: usize = 15;
+const FIND_PATH_FUEL: usize = 10000;
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum PrefixKind {
@@ -63,79 +89,54 @@ impl PrefixKind {
#[inline]
fn path_kind(self) -> PathKind {
match self {
- PrefixKind::BySelf => PathKind::Super(0),
+ PrefixKind::BySelf => PathKind::SELF,
PrefixKind::Plain => PathKind::Plain,
PrefixKind::ByCrate => PathKind::Crate,
}
}
}
-#[derive(Copy, Clone)]
struct FindPathCtx<'db> {
db: &'db dyn DefDatabase,
prefix: PrefixKind,
cfg: ImportPathConfig,
ignore_local_imports: bool,
+ from: ModuleId,
+ from_def_map: &'db DefMap,
+ fuel: Cell<usize>,
}
/// Attempts to find a path to refer to the given `item` visible from the `from` ModuleId
-fn find_path_inner(ctx: FindPathCtx<'_>, item: ItemInNs, from: ModuleId) -> Option<ModPath> {
- // - if the item is a builtin, it's in scope
- if let ItemInNs::Types(ModuleDefId::BuiltinType(builtin)) = item {
- return Some(ModPath::from_segments(PathKind::Plain, iter::once(builtin.as_name())));
- }
-
- let def_map = from.def_map(ctx.db);
- let crate_root = from.derive_crate_root();
+fn find_path_inner(ctx: &FindPathCtx<'_>, item: ItemInNs, max_len: usize) -> Option<ModPath> {
// - if the item is a module, jump straight to module search
if let ItemInNs::Types(ModuleDefId::ModuleId(module_id)) = item {
let mut visited_modules = FxHashSet::default();
- return find_path_for_module(
- FindPathCtx {
- cfg: ImportPathConfig {
- prefer_no_std: ctx.cfg.prefer_no_std
- || ctx.db.crate_supports_no_std(crate_root.krate),
- ..ctx.cfg
- },
- ..ctx
- },
- &def_map,
- &mut visited_modules,
- from,
- module_id,
- MAX_PATH_LEN,
- )
- .map(|(item, _)| item);
+ return find_path_for_module(ctx, &mut visited_modules, module_id, max_len)
+ .map(|(item, _)| item);
}
- let prefix = if item.module(ctx.db).is_some_and(|it| it.is_within_block()) {
- PrefixKind::Plain
- } else {
- ctx.prefix
- };
- let may_be_in_scope = match prefix {
+ let may_be_in_scope = match ctx.prefix {
PrefixKind::Plain | PrefixKind::BySelf => true,
- PrefixKind::ByCrate => from.is_crate_root(),
+ PrefixKind::ByCrate => ctx.from.is_crate_root(),
};
if may_be_in_scope {
// - if the item is already in scope, return the name under which it is
- let scope_name = find_in_scope(ctx.db, &def_map, from, item, ctx.ignore_local_imports);
+ let scope_name =
+ find_in_scope(ctx.db, ctx.from_def_map, ctx.from, item, ctx.ignore_local_imports);
if let Some(scope_name) = scope_name {
- return Some(ModPath::from_segments(prefix.path_kind(), iter::once(scope_name)));
+ return Some(ModPath::from_segments(ctx.prefix.path_kind(), iter::once(scope_name)));
}
}
// - if the item is in the prelude, return the name from there
- if let value @ Some(_) =
- find_in_prelude(ctx.db, &crate_root.def_map(ctx.db), &def_map, item, from)
- {
- return value;
+ if let Some(value) = find_in_prelude(ctx.db, ctx.from_def_map, item, ctx.from) {
+ return Some(value);
}
if let Some(ModuleDefId::EnumVariantId(variant)) = item.as_module_def_id() {
// - if the item is an enum variant, refer to it via the enum
if let Some(mut path) =
- find_path_inner(ctx, ItemInNs::Types(variant.lookup(ctx.db).parent.into()), from)
+ find_path_inner(ctx, ItemInNs::Types(variant.lookup(ctx.db).parent.into()), max_len)
{
path.push_segment(ctx.db.enum_variant_data(variant).name.clone());
return Some(path);
@@ -147,53 +148,32 @@ fn find_path_inner(ctx: FindPathCtx<'_>, item: ItemInNs, from: ModuleId) -> Opti
let mut visited_modules = FxHashSet::default();
- calculate_best_path(
- FindPathCtx {
- cfg: ImportPathConfig {
- prefer_no_std: ctx.cfg.prefer_no_std
- || ctx.db.crate_supports_no_std(crate_root.krate),
- ..ctx.cfg
- },
- ..ctx
- },
- &def_map,
- &mut visited_modules,
- MAX_PATH_LEN,
- item,
- from,
- )
- .map(|(item, _)| item)
+ calculate_best_path(ctx, &mut visited_modules, item, max_len).map(|(item, _)| item)
}
#[tracing::instrument(skip_all)]
fn find_path_for_module(
- ctx: FindPathCtx<'_>,
- def_map: &DefMap,
+ ctx: &FindPathCtx<'_>,
visited_modules: &mut FxHashSet<ModuleId>,
- from: ModuleId,
module_id: ModuleId,
max_len: usize,
) -> Option<(ModPath, Stability)> {
- if max_len == 0 {
- return None;
- }
-
- let is_crate_root = module_id.as_crate_root();
- // - if the item is the crate root, return `crate`
- if is_crate_root.is_some_and(|it| it == from.derive_crate_root()) {
- return Some((ModPath::from_segments(PathKind::Crate, None), Stable));
- }
+ if let Some(crate_root) = module_id.as_crate_root() {
+ if crate_root == ctx.from.derive_crate_root() {
+ // - if the item is the crate root, return `crate`
+ return Some((ModPath::from_segments(PathKind::Crate, None), Stable));
+ }
+ // - otherwise if the item is the crate root of a dependency crate, return the name from the extern prelude
- let root_def_map = from.derive_crate_root().def_map(ctx.db);
- // - if the item is the crate root of a dependency crate, return the name from the extern prelude
- if let Some(crate_root) = is_crate_root {
+ let root_def_map = ctx.from.derive_crate_root().def_map(ctx.db);
// rev here so we prefer looking at renamed extern decls first
for (name, (def_id, _extern_crate)) in root_def_map.extern_prelude().rev() {
if crate_root != def_id {
continue;
}
- let name_already_occupied_in_type_ns = def_map
- .with_ancestor_maps(ctx.db, from.local_id, &mut |def_map, local_id| {
+ let name_already_occupied_in_type_ns = ctx
+ .from_def_map
+ .with_ancestor_maps(ctx.db, ctx.from.local_id, &mut |def_map, local_id| {
def_map[local_id]
.scope
.type_(name)
@@ -209,30 +189,30 @@ fn find_path_for_module(
return Some((ModPath::from_segments(kind, iter::once(name.clone())), Stable));
}
}
- let prefix = if module_id.is_within_block() { PrefixKind::Plain } else { ctx.prefix };
- let may_be_in_scope = match prefix {
+
+ let may_be_in_scope = match ctx.prefix {
PrefixKind::Plain | PrefixKind::BySelf => true,
- PrefixKind::ByCrate => from.is_crate_root(),
+ PrefixKind::ByCrate => ctx.from.is_crate_root(),
};
if may_be_in_scope {
let scope_name = find_in_scope(
ctx.db,
- def_map,
- from,
+ ctx.from_def_map,
+ ctx.from,
ItemInNs::Types(module_id.into()),
ctx.ignore_local_imports,
);
if let Some(scope_name) = scope_name {
// - if the item is already in scope, return the name under which it is
return Some((
- ModPath::from_segments(prefix.path_kind(), iter::once(scope_name)),
+ ModPath::from_segments(ctx.prefix.path_kind(), iter::once(scope_name)),
Stable,
));
}
}
// - if the module can be referenced as self, super or crate, do that
- if let Some(mod_path) = is_kw_kind_relative_to_from(def_map, module_id, from) {
+ if let Some(mod_path) = is_kw_kind_relative_to_from(ctx.from_def_map, module_id, ctx.from) {
if ctx.prefix != PrefixKind::ByCrate || mod_path.kind == PathKind::Crate {
return Some((mod_path, Stable));
}
@@ -240,21 +220,13 @@ fn find_path_for_module(
// - if the module is in the prelude, return it by that path
if let Some(mod_path) =
- find_in_prelude(ctx.db, &root_def_map, def_map, ItemInNs::Types(module_id.into()), from)
+ find_in_prelude(ctx.db, ctx.from_def_map, ItemInNs::Types(module_id.into()), ctx.from)
{
return Some((mod_path, Stable));
}
- calculate_best_path(
- ctx,
- def_map,
- visited_modules,
- max_len,
- ItemInNs::Types(module_id.into()),
- from,
- )
+ calculate_best_path(ctx, visited_modules, ItemInNs::Types(module_id.into()), max_len)
}
-// FIXME: Do we still need this now that we record import origins, and hence aliases?
fn find_in_scope(
db: &dyn DefDatabase,
def_map: &DefMap,
@@ -274,13 +246,11 @@ fn find_in_scope(
/// name doesn't clash in current scope.
fn find_in_prelude(
db: &dyn DefDatabase,
- root_def_map: &DefMap,
local_def_map: &DefMap,
item: ItemInNs,
from: ModuleId,
) -> Option<ModPath> {
- let (prelude_module, _) = root_def_map.prelude()?;
- // Preludes in block DefMaps are ignored, only the crate DefMap is searched
+ let (prelude_module, _) = local_def_map.prelude()?;
let prelude_def_map = prelude_module.def_map(db);
let prelude_scope = &prelude_def_map[prelude_module.local_id].scope;
let (name, vis, _declared) = prelude_scope.name_of(item)?;
@@ -319,7 +289,7 @@ fn is_kw_kind_relative_to_from(
let from = from.local_id;
if item == from {
// - if the item is the module we're in, use `self`
- Some(ModPath::from_segments(PathKind::Super(0), None))
+ Some(ModPath::from_segments(PathKind::SELF, None))
} else if let Some(parent_id) = def_map[from].parent {
if item == parent_id {
// - if the item is the parent module, use `super` (this is not used recursively, since `super::super` is ugly)
@@ -337,60 +307,71 @@ fn is_kw_kind_relative_to_from(
#[tracing::instrument(skip_all)]
fn calculate_best_path(
- ctx: FindPathCtx<'_>,
- def_map: &DefMap,
+ ctx: &FindPathCtx<'_>,
visited_modules: &mut FxHashSet<ModuleId>,
- max_len: usize,
item: ItemInNs,
- from: ModuleId,
+ max_len: usize,
) -> Option<(ModPath, Stability)> {
if max_len <= 1 {
+ // recursive base case, we can't find a path prefix of length 0, one segment is occupied by
+ // the item's name itself.
+ return None;
+ }
+ let fuel = ctx.fuel.get();
+ if fuel == 0 {
+ // we ran out of fuel, so we stop searching here
+ tracing::warn!(
+ "ran out of fuel while searching for a path for item {item:?} of krate {:?} from krate {:?}",
+ item.krate(ctx.db),
+ ctx.from.krate()
+ );
return None;
}
+ ctx.fuel.set(fuel - 1);
+
let mut best_path = None;
- let update_best_path =
- |best_path: &mut Option<_>, new_path: (ModPath, Stability)| match best_path {
+ let mut best_path_len = max_len;
+ let mut process = |mut path: (ModPath, Stability), name, best_path_len: &mut _| {
+ path.0.push_segment(name);
+ let new_path = match best_path.take() {
+ Some(best_path) => select_best_path(best_path, path, ctx.cfg),
+ None => path,
+ };
+ if new_path.1 == Stable {
+ *best_path_len = new_path.0.len();
+ }
+ match &mut best_path {
Some((old_path, old_stability)) => {
*old_path = new_path.0;
*old_stability = zip_stability(*old_stability, new_path.1);
}
- None => *best_path = Some(new_path),
- };
- // Recursive case:
- // - otherwise, look for modules containing (reexporting) it and import it from one of those
- if item.krate(ctx.db) == Some(from.krate) {
- let mut best_path_len = max_len;
+ None => best_path = Some(new_path),
+ }
+ };
+ let db = ctx.db;
+ if item.krate(db) == Some(ctx.from.krate) {
// Item was defined in the same crate that wants to import it. It cannot be found in any
// dependency in this case.
- for (module_id, name) in find_local_import_locations(ctx.db, item, from) {
+ // FIXME: cache the `find_local_import_locations` output?
+ find_local_import_locations(db, item, ctx.from, ctx.from_def_map, |name, module_id| {
if !visited_modules.insert(module_id) {
- continue;
+ return;
}
- if let Some(mut path) = find_path_for_module(
- ctx,
- def_map,
- visited_modules,
- from,
- module_id,
- best_path_len - 1,
- ) {
- path.0.push_segment(name);
-
- let new_path = match best_path.take() {
- Some(best_path) => select_best_path(best_path, path, ctx.cfg),
- None => path,
- };
- best_path_len = new_path.0.len();
- update_best_path(&mut best_path, new_path);
+ // we are looking for paths of length up to best_path_len, any longer will make it be
+ // less optimal. The -1 is due to us pushing name onto it afterwards.
+ if let Some(path) =
+ find_path_for_module(ctx, visited_modules, module_id, best_path_len - 1)
+ {
+ process(path, name.clone(), &mut best_path_len);
}
- }
+ })
} else {
// Item was defined in some upstream crate. This means that it must be exported from one,
// too (unless we can't name it at all). It could *also* be (re)exported by the same crate
// that wants to import it here, but we always prefer to use the external path here.
- for dep in &ctx.db.crate_graph()[from.krate].dependencies {
- let import_map = ctx.db.import_map(dep.crate_id);
+ for dep in &db.crate_graph()[ctx.from.krate].dependencies {
+ let import_map = db.import_map(dep.crate_id);
let Some(import_info_for) = import_map.import_info_for(item) else { continue };
for info in import_info_for {
if info.is_doc_hidden {
@@ -400,29 +381,18 @@ fn calculate_best_path(
// Determine best path for containing module and append last segment from `info`.
// FIXME: we should guide this to look up the path locally, or from the same crate again?
- let Some((mut path, path_stability)) = find_path_for_module(
- ctx,
- def_map,
- visited_modules,
- from,
- info.container,
- max_len - 1,
- ) else {
+ let path =
+ find_path_for_module(ctx, visited_modules, info.container, best_path_len - 1);
+ let Some((path, path_stability)) = path else {
continue;
};
cov_mark::hit!(partially_imported);
- path.push_segment(info.name.clone());
-
- let path_with_stab = (
+ let path = (
path,
zip_stability(path_stability, if info.is_unstable { Unstable } else { Stable }),
);
- let new_path_with_stab = match best_path.take() {
- Some(best_path) => select_best_path(best_path, path_with_stab, ctx.cfg),
- None => path_with_stab,
- };
- update_best_path(&mut best_path, new_path_with_stab);
+ process(path, info.name.clone(), &mut best_path_len);
}
}
}
@@ -430,7 +400,7 @@ fn calculate_best_path(
}
/// Select the best (most relevant) path between two paths.
-/// This accounts for stability, path length whether std should be chosen over alloc/core paths as
+/// This accounts for stability, path length whether, std should be chosen over alloc/core paths as
/// well as ignoring prelude like paths or not.
fn select_best_path(
old_path @ (_, old_stability): (ModPath, Stability),
@@ -496,36 +466,33 @@ fn select_best_path(
}
}
-// FIXME: Remove allocations
/// Finds locations in `from.krate` from which `item` can be imported by `from`.
fn find_local_import_locations(
db: &dyn DefDatabase,
item: ItemInNs,
from: ModuleId,
-) -> Vec<(ModuleId, Name)> {
- let _p = tracing::span!(tracing::Level::INFO, "find_local_import_locations").entered();
+ def_map: &DefMap,
+ mut cb: impl FnMut(&Name, ModuleId),
+) {
+ let _p = tracing::info_span!("find_local_import_locations").entered();
// `from` can import anything below `from` with visibility of at least `from`, and anything
// above `from` with any visibility. That means we do not need to descend into private siblings
// of `from` (and similar).
- let def_map = from.def_map(db);
-
// Compute the initial worklist. We start with all direct child modules of `from` as well as all
// of its (recursive) parent modules.
- let data = &def_map[from.local_id];
- let mut worklist =
- data.children.values().map(|child| def_map.module_id(*child)).collect::<Vec<_>>();
- // FIXME: do we need to traverse out of block expressions here?
- for ancestor in iter::successors(from.containing_module(db), |m| m.containing_module(db)) {
- worklist.push(ancestor);
- }
+ let mut worklist = def_map[from.local_id]
+ .children
+ .values()
+ .map(|child| def_map.module_id(*child))
+ // FIXME: do we need to traverse out of block expressions here?
+ .chain(iter::successors(from.containing_module(db), |m| m.containing_module(db)))
+ .collect::<Vec<_>>();
+ let mut seen: FxHashSet<_> = FxHashSet::default();
let def_map = def_map.crate_root().def_map(db);
- let mut seen: FxHashSet<_> = FxHashSet::default();
-
- let mut locations = Vec::new();
while let Some(module) = worklist.pop() {
if !seen.insert(module) {
continue; // already processed this module
@@ -566,7 +533,7 @@ fn find_local_import_locations(
// the item and we're a submodule of it, so can we.
// Also this keeps the cached data smaller.
if declared || is_pub_or_explicit {
- locations.push((module, name.clone()));
+ cb(name, module);
}
}
}
@@ -578,8 +545,6 @@ fn find_local_import_locations(
}
}
}
-
- locations
}
#[cfg(test)]
@@ -633,15 +598,13 @@ mod tests {
.into_iter()
.cartesian_product([false, true])
{
- let found_path = find_path_inner(
- FindPathCtx {
- db: &db,
- prefix,
- cfg: ImportPathConfig { prefer_no_std: false, prefer_prelude },
- ignore_local_imports,
- },
+ let found_path = find_path(
+ &db,
resolved,
module,
+ prefix,
+ ignore_local_imports,
+ ImportPathConfig { prefer_no_std: false, prefer_prelude },
);
format_to!(
res,