use hir_expand::name::{known, AsName, Name};
use rustc_hash::FxHashSet;
use test_utils::mark;
use crate::{
db::DefDatabase,
item_scope::ItemInNs,
path::{ModPath, PathKind},
visibility::Visibility,
ModuleDefId, ModuleId,
};
pub fn find_path(db: &dyn DefDatabase, item: ItemInNs, from: ModuleId) -> Option<ModPath> {
let _p = profile::span("find_path");
find_path_inner(db, item, from, MAX_PATH_LEN)
}
const MAX_PATH_LEN: usize = 15;
impl ModPath {
fn starts_with_std(&self) -> bool {
self.segments.first() == Some(&known::std)
}
fn can_start_with_std(&self) -> bool {
let first_segment = self.segments.first();
first_segment == Some(&known::alloc) || first_segment == Some(&known::core)
}
}
fn find_path_inner(
db: &dyn DefDatabase,
item: ItemInNs,
from: ModuleId,
max_len: usize,
) -> Option<ModPath> {
if max_len == 0 {
return None;
}
let def_map = db.crate_def_map(from.krate);
let from_scope: &crate::item_scope::ItemScope = &def_map.modules[from.local_id].scope;
if let Some((name, _)) = from_scope.name_of(item) {
return Some(ModPath::from_segments(PathKind::Plain, vec![name.clone()]));
}
if item
== ItemInNs::Types(ModuleDefId::ModuleId(ModuleId {
krate: from.krate,
local_id: def_map.root,
}))
{
return Some(ModPath::from_segments(PathKind::Crate, Vec::new()));
}
if item == ItemInNs::Types(from.into()) {
return Some(ModPath::from_segments(PathKind::Super(0), Vec::new()));
}
if let Some(parent_id) = def_map.modules[from.local_id].parent {
if item
== ItemInNs::Types(ModuleDefId::ModuleId(ModuleId {
krate: from.krate,
local_id: parent_id,
}))
{
return Some(ModPath::from_segments(PathKind::Super(1), Vec::new()));
}
}
for (name, def_id) in &def_map.extern_prelude {
if item == ItemInNs::Types(*def_id) {
return Some(ModPath::from_segments(PathKind::Plain, vec![name.clone()]));
}
}
if let Some(prelude_module) = def_map.prelude {
let prelude_def_map = db.crate_def_map(prelude_module.krate);
let prelude_scope: &crate::item_scope::ItemScope =
&prelude_def_map.modules[prelude_module.local_id].scope;
if let Some((name, vis)) = prelude_scope.name_of(item) {
if vis.is_visible_from(db, from) {
return Some(ModPath::from_segments(PathKind::Plain, vec![name.clone()]));
}
}
}
if let ItemInNs::Types(ModuleDefId::BuiltinType(builtin)) = item {
return Some(ModPath::from_segments(PathKind::Plain, vec![builtin.as_name()]));
}
if let Some(ModuleDefId::EnumVariantId(variant)) = item.as_module_def_id() {
if let Some(mut path) = find_path(db, ItemInNs::Types(variant.parent.into()), from) {
let data = db.enum_data(variant.parent);
path.segments.push(data.variants[variant.local_id].name.clone());
return Some(path);
}
}
let crate_root = ModuleId { local_id: def_map.root, krate: from.krate };
let crate_attrs = db.attrs(crate_root.into());
let prefer_no_std = crate_attrs.by_key("no_std").exists();
let mut best_path = None;
let mut best_path_len = max_len;
if item.krate(db) == Some(from.krate) {
let local_imports = find_local_import_locations(db, item, from);
for (module_id, name) in local_imports {
if let Some(mut path) = find_path_inner(
db,
ItemInNs::Types(ModuleDefId::ModuleId(module_id)),
from,
best_path_len - 1,
) {
path.segments.push(name);
let new_path = if let Some(best_path) = best_path {
select_best_path(best_path, path, prefer_no_std)
} else {
path
};
best_path_len = new_path.len();
best_path = Some(new_path);
}
}
} else {
let crate_graph = db.crate_graph();
let extern_paths = crate_graph[from.krate].dependencies.iter().filter_map(|dep| {
let import_map = db.import_map(dep.crate_id);
import_map.import_info_for(item).and_then(|info| {
let mut path = find_path_inner(
db,
ItemInNs::Types(ModuleDefId::ModuleId(info.container)),
from,
best_path_len - 1,
)?;
path.segments.push(info.path.segments.last().unwrap().clone());
Some(path)
})
});
for path in extern_paths {
let new_path = if let Some(best_path) = best_path {
select_best_path(best_path, path, prefer_no_std)
} else {
path
};
best_path = Some(new_path);
}
}
best_path
}
fn select_best_path(old_path: ModPath, new_path: ModPath, prefer_no_std: bool) -> ModPath {
if old_path.starts_with_std() && new_path.can_start_with_std() {
if prefer_no_std {
mark::hit!(prefer_no_std_paths);
new_path
} else {
mark::hit!(prefer_std_paths);
old_path
}
} else if new_path.starts_with_std() && old_path.can_start_with_std() {
if prefer_no_std {
mark::hit!(prefer_no_std_paths);
old_path
} else {
mark::hit!(prefer_std_paths);
new_path
}
} else if new_path.len() < old_path.len() {
new_path
} else {
old_path
}
}
fn find_local_import_locations(
db: &dyn DefDatabase,
item: ItemInNs,
from: ModuleId,
) -> Vec<(ModuleId, Name)> {
let _p = profile::span("find_local_import_locations");
let def_map = db.crate_def_map(from.krate);
let data = &def_map.modules[from.local_id];
let mut worklist = data
.children
.values()
.map(|child| ModuleId { krate: from.krate, local_id: *child })
.collect::<Vec<_>>();
let mut parent = data.parent;
while let Some(p) = parent {
worklist.push(ModuleId { krate: from.krate, local_id: p });
parent = def_map.modules[p].parent;
}
let mut seen: FxHashSet<_> = FxHashSet::default();
let mut locations = Vec::new();
while let Some(module) = worklist.pop() {
if !seen.insert(module) {
continue;
}
let ext_def_map;
let data = if module.krate == from.krate {
&def_map[module.local_id]
} else {
ext_def_map = db.crate_def_map(module.krate);
&ext_def_map[module.local_id]
};
if let Some((name, vis)) = data.scope.name_of(item) {
if vis.is_visible_from(db, from) {
let is_private = if let Visibility::Module(private_to) = vis {
private_to.local_id == module.local_id
} else {
false
};
let is_original_def = if let Some(module_def_id) = item.as_module_def_id() {
data.scope.declarations().any(|it| it == module_def_id)
} else {
false
};
if !is_private || is_original_def {
locations.push((module, name.clone()));
}
}
}
for (_, per_ns) in data.scope.entries() {
if let Some((ModuleDefId::ModuleId(module), vis)) = per_ns.take_types_vis() {
if vis.is_visible_from(db, from) {
worklist.push(module);
}
}
}
}
locations
}
#[cfg(test)]
mod tests {
use base_db::fixture::WithFixture;
use hir_expand::hygiene::Hygiene;
use syntax::ast::AstNode;
use test_utils::mark;
use crate::test_db::TestDB;
use super::*;
fn check_found_path(ra_fixture: &str, path: &str) {
let (db, pos) = TestDB::with_position(ra_fixture);
let module = db.module_for_file(pos.file_id);
let parsed_path_file = syntax::SourceFile::parse(&format!("use {};", path));
let ast_path =
parsed_path_file.syntax_node().descendants().find_map(syntax::ast::Path::cast).unwrap();
let mod_path = ModPath::from_src(ast_path, &Hygiene::new_unhygienic()).unwrap();
let crate_def_map = db.crate_def_map(module.krate);
let resolved = crate_def_map
.resolve_path(
&db,
module.local_id,
&mod_path,
crate::item_scope::BuiltinShadowMode::Module,
)
.0
.take_types()
.unwrap();
let found_path = find_path(&db, ItemInNs::Types(resolved), module);
assert_eq!(found_path, Some(mod_path));
}
#[test]
fn same_module() {
let code = r#"
//- /main.rs
struct S;
<|>
"#;
check_found_path(code, "S");
}
#[test]
fn enum_variant() {
let code = r#"
//- /main.rs
enum E { A }
<|>
"#;
check_found_path(code, "E::A");
}
#[test]
fn sub_module() {
let code = r#"
//- /main.rs
mod foo {
pub struct S;
}
<|>
"#;
check_found_path(code, "foo::S");
}
#[test]
fn super_module() {
let code = r#"
//- /main.rs
mod foo;
//- /foo.rs
mod bar;
struct S;
//- /foo/bar.rs
<|>
"#;
check_found_path(code, "super::S");
}
#[test]
fn self_module() {
let code = r#"
//- /main.rs
mod foo;
//- /foo.rs
<|>
"#;
check_found_path(code, "self");
}
#[test]
fn crate_root() {
let code = r#"
//- /main.rs
mod foo;
//- /foo.rs
<|>
"#;
check_found_path(code, "crate");
}
#[test]
fn same_crate() {
let code = r#"
//- /main.rs
mod foo;
struct S;
//- /foo.rs
<|>
"#;
check_found_path(code, "crate::S");
}
#[test]
fn different_crate() {
let code = r#"
//- /main.rs crate:main deps:std
<|>
//- /std.rs crate:std
pub struct S;
"#;
check_found_path(code, "std::S");
}
#[test]
fn different_crate_renamed() {
let code = r#"
//- /main.rs crate:main deps:std
extern crate std as std_renamed;
<|>
//- /std.rs crate:std
pub struct S;
"#;
check_found_path(code, "std_renamed::S");
}
#[test]
fn partially_imported() {
check_found_path(
r#"
//- /main.rs crate:main deps:syntax
use syntax::ast;
<|>
//- /lib.rs crate:syntax
pub mod ast {
pub enum ModuleItem {
A, B, C,
}
}
"#,
"ast::ModuleItem",
);
check_found_path(
r#"
//- /main.rs crate:main deps:syntax
<|>
//- /lib.rs crate:syntax
pub mod ast {
pub enum ModuleItem {
A, B, C,
}
}
"#,
"syntax::ast::ModuleItem",
);
}
#[test]
fn same_crate_reexport() {
let code = r#"
//- /main.rs
mod bar {
mod foo { pub(super) struct S; }
pub(crate) use foo::*;
}
<|>
"#;
check_found_path(code, "bar::S");
}
#[test]
fn same_crate_reexport_rename() {
let code = r#"
//- /main.rs
mod bar {
mod foo { pub(super) struct S; }
pub(crate) use foo::S as U;
}
<|>
"#;
check_found_path(code, "bar::U");
}
#[test]
fn different_crate_reexport() {
let code = r#"
//- /main.rs crate:main deps:std
<|>
//- /std.rs crate:std deps:core
pub use core::S;
//- /core.rs crate:core
pub struct S;
"#;
check_found_path(code, "std::S");
}
#[test]
fn prelude() {
let code = r#"
//- /main.rs crate:main deps:std
<|>
//- /std.rs crate:std
pub mod prelude { pub struct S; }
#[prelude_import]
pub use prelude::*;
"#;
check_found_path(code, "S");
}
#[test]
fn enum_variant_from_prelude() {
let code = r#"
//- /main.rs crate:main deps:std
<|>
//- /std.rs crate:std
pub mod prelude {
pub enum Option<T> { Some(T), None }
pub use Option::*;
}
#[prelude_import]
pub use prelude::*;
"#;
check_found_path(code, "None");
check_found_path(code, "Some");
}
#[test]
fn shortest_path() {
let code = r#"
//- /main.rs
pub mod foo;
pub mod baz;
struct S;
<|>
//- /foo.rs
pub mod bar { pub struct S; }
//- /baz.rs
pub use crate::foo::bar::S;
"#;
check_found_path(code, "baz::S");
}
#[test]
fn discount_private_imports() {
let code = r#"
//- /main.rs
mod foo;
pub mod bar { pub struct S; }
use bar::S;
//- /foo.rs
<|>
"#;
check_found_path(code, "crate::bar::S");
}
#[test]
fn import_cycle() {
let code = r#"
//- /main.rs
pub mod foo;
pub mod bar;
pub mod baz;
//- /bar.rs
<|>
//- /foo.rs
pub use super::baz;
pub struct S;
//- /baz.rs
pub use super::foo;
"#;
check_found_path(code, "crate::foo::S");
}
#[test]
fn prefer_std_paths_over_alloc() {
mark::check!(prefer_std_paths);
let code = r#"
//- /main.rs crate:main deps:alloc,std
<|>
//- /std.rs crate:std deps:alloc
pub mod sync {
pub use alloc::sync::Arc;
}
//- /zzz.rs crate:alloc
pub mod sync {
pub struct Arc;
}
"#;
check_found_path(code, "std::sync::Arc");
}
#[test]
fn prefer_core_paths_over_std() {
mark::check!(prefer_no_std_paths);
let code = r#"
//- /main.rs crate:main deps:core,std
#![no_std]
<|>
//- /std.rs crate:std deps:core
pub mod fmt {
pub use core::fmt::Error;
}
//- /zzz.rs crate:core
pub mod fmt {
pub struct Error;
}
"#;
check_found_path(code, "core::fmt::Error");
}
#[test]
fn prefer_alloc_paths_over_std() {
let code = r#"
//- /main.rs crate:main deps:alloc,std
#![no_std]
<|>
//- /std.rs crate:std deps:alloc
pub mod sync {
pub use alloc::sync::Arc;
}
//- /zzz.rs crate:alloc
pub mod sync {
pub struct Arc;
}
"#;
check_found_path(code, "alloc::sync::Arc");
}
#[test]
fn prefer_shorter_paths_if_not_alloc() {
let code = r#"
//- /main.rs crate:main deps:megaalloc,std
<|>
//- /std.rs crate:std deps:megaalloc
pub mod sync {
pub use megaalloc::sync::Arc;
}
//- /zzz.rs crate:megaalloc
pub struct Arc;
"#;
check_found_path(code, "megaalloc::Arc");
}
#[test]
fn builtins_are_in_scope() {
let code = r#"
//- /main.rs
<|>
pub mod primitive {
pub use u8;
}
"#;
check_found_path(code, "u8");
check_found_path(code, "u16");
}
}