diff options
author | Mikhail Rakhmanov <[email protected]> | 2020-06-13 07:42:15 +0100 |
---|---|---|
committer | Mikhail Rakhmanov <[email protected]> | 2020-06-13 07:42:15 +0100 |
commit | 16bbf4ab7f132e6e5e5318dccdef9a5d71afdd7f (patch) | |
tree | 4b79fa8c046be56b02427ba843e70cdf3ac05767 /crates/ra_hir_def/src/find_path.rs | |
parent | eeb8b9e236796da8734ba81a49164864497f7226 (diff) | |
parent | b56ad148db0c69eb279c225f45d324b4e80e7367 (diff) |
Merge branch 'master' into keyword_completion
# Conflicts:
# docs/user/generated_features.adoc
Diffstat (limited to 'crates/ra_hir_def/src/find_path.rs')
-rw-r--r-- | crates/ra_hir_def/src/find_path.rs | 247 |
1 files changed, 163 insertions, 84 deletions
diff --git a/crates/ra_hir_def/src/find_path.rs b/crates/ra_hir_def/src/find_path.rs index 4db798473..06701a830 100644 --- a/crates/ra_hir_def/src/find_path.rs +++ b/crates/ra_hir_def/src/find_path.rs | |||
@@ -1,9 +1,8 @@ | |||
1 | //! An algorithm to find a path to refer to a certain item. | 1 | //! An algorithm to find a path to refer to a certain item. |
2 | 2 | ||
3 | use std::sync::Arc; | ||
4 | |||
5 | use hir_expand::name::{known, AsName, Name}; | 3 | use hir_expand::name::{known, AsName, Name}; |
6 | use ra_prof::profile; | 4 | use ra_prof::profile; |
5 | use rustc_hash::FxHashSet; | ||
7 | use test_utils::mark; | 6 | use test_utils::mark; |
8 | 7 | ||
9 | use crate::{ | 8 | use crate::{ |
@@ -11,7 +10,7 @@ use crate::{ | |||
11 | item_scope::ItemInNs, | 10 | item_scope::ItemInNs, |
12 | path::{ModPath, PathKind}, | 11 | path::{ModPath, PathKind}, |
13 | visibility::Visibility, | 12 | visibility::Visibility, |
14 | CrateId, ModuleDefId, ModuleId, | 13 | ModuleDefId, ModuleId, |
15 | }; | 14 | }; |
16 | 15 | ||
17 | // FIXME: handle local items | 16 | // FIXME: handle local items |
@@ -20,7 +19,7 @@ use crate::{ | |||
20 | /// *from where* you're referring to the item, hence the `from` parameter. | 19 | /// *from where* you're referring to the item, hence the `from` parameter. |
21 | pub fn find_path(db: &dyn DefDatabase, item: ItemInNs, from: ModuleId) -> Option<ModPath> { | 20 | pub fn find_path(db: &dyn DefDatabase, item: ItemInNs, from: ModuleId) -> Option<ModPath> { |
22 | let _p = profile("find_path"); | 21 | let _p = profile("find_path"); |
23 | db.find_path_inner(item, from, MAX_PATH_LEN) | 22 | find_path_inner(db, item, from, MAX_PATH_LEN) |
24 | } | 23 | } |
25 | 24 | ||
26 | const MAX_PATH_LEN: usize = 15; | 25 | const MAX_PATH_LEN: usize = 15; |
@@ -36,20 +35,9 @@ impl ModPath { | |||
36 | let first_segment = self.segments.first(); | 35 | let first_segment = self.segments.first(); |
37 | first_segment == Some(&known::alloc) || first_segment == Some(&known::core) | 36 | first_segment == Some(&known::alloc) || first_segment == Some(&known::core) |
38 | } | 37 | } |
39 | |||
40 | fn len(&self) -> usize { | ||
41 | self.segments.len() | ||
42 | + match self.kind { | ||
43 | PathKind::Plain => 0, | ||
44 | PathKind::Super(i) => i as usize, | ||
45 | PathKind::Crate => 1, | ||
46 | PathKind::Abs => 0, | ||
47 | PathKind::DollarCrate(_) => 1, | ||
48 | } | ||
49 | } | ||
50 | } | 38 | } |
51 | 39 | ||
52 | pub(crate) fn find_path_inner_query( | 40 | fn find_path_inner( |
53 | db: &dyn DefDatabase, | 41 | db: &dyn DefDatabase, |
54 | item: ItemInNs, | 42 | item: ItemInNs, |
55 | from: ModuleId, | 43 | from: ModuleId, |
@@ -133,31 +121,67 @@ pub(crate) fn find_path_inner_query( | |||
133 | } | 121 | } |
134 | 122 | ||
135 | // - otherwise, look for modules containing (reexporting) it and import it from one of those | 123 | // - otherwise, look for modules containing (reexporting) it and import it from one of those |
124 | |||
136 | let crate_root = ModuleId { local_id: def_map.root, krate: from.krate }; | 125 | let crate_root = ModuleId { local_id: def_map.root, krate: from.krate }; |
137 | let crate_attrs = db.attrs(crate_root.into()); | 126 | let crate_attrs = db.attrs(crate_root.into()); |
138 | let prefer_no_std = crate_attrs.by_key("no_std").exists(); | 127 | let prefer_no_std = crate_attrs.by_key("no_std").exists(); |
139 | let importable_locations = find_importable_locations(db, item, from); | ||
140 | let mut best_path = None; | 128 | let mut best_path = None; |
141 | let mut best_path_len = max_len; | 129 | let mut best_path_len = max_len; |
142 | for (module_id, name) in importable_locations { | ||
143 | let mut path = match db.find_path_inner( | ||
144 | ItemInNs::Types(ModuleDefId::ModuleId(module_id)), | ||
145 | from, | ||
146 | best_path_len - 1, | ||
147 | ) { | ||
148 | None => continue, | ||
149 | Some(path) => path, | ||
150 | }; | ||
151 | path.segments.push(name); | ||
152 | 130 | ||
153 | let new_path = if let Some(best_path) = best_path { | 131 | if item.krate(db) == Some(from.krate) { |
154 | select_best_path(best_path, path, prefer_no_std) | 132 | // Item was defined in the same crate that wants to import it. It cannot be found in any |
155 | } else { | 133 | // dependency in this case. |
156 | path | 134 | |
157 | }; | 135 | let local_imports = find_local_import_locations(db, item, from); |
158 | best_path_len = new_path.len(); | 136 | for (module_id, name) in local_imports { |
159 | best_path = Some(new_path); | 137 | if let Some(mut path) = find_path_inner( |
138 | db, | ||
139 | ItemInNs::Types(ModuleDefId::ModuleId(module_id)), | ||
140 | from, | ||
141 | best_path_len - 1, | ||
142 | ) { | ||
143 | path.segments.push(name); | ||
144 | |||
145 | let new_path = if let Some(best_path) = best_path { | ||
146 | select_best_path(best_path, path, prefer_no_std) | ||
147 | } else { | ||
148 | path | ||
149 | }; | ||
150 | best_path_len = new_path.len(); | ||
151 | best_path = Some(new_path); | ||
152 | } | ||
153 | } | ||
154 | } else { | ||
155 | // Item was defined in some upstream crate. This means that it must be exported from one, | ||
156 | // too (unless we can't name it at all). It could *also* be (re)exported by the same crate | ||
157 | // that wants to import it here, but we always prefer to use the external path here. | ||
158 | |||
159 | let crate_graph = db.crate_graph(); | ||
160 | let extern_paths = crate_graph[from.krate].dependencies.iter().filter_map(|dep| { | ||
161 | let import_map = db.import_map(dep.crate_id); | ||
162 | import_map.import_info_for(item).and_then(|info| { | ||
163 | // Determine best path for containing module and append last segment from `info`. | ||
164 | let mut path = find_path_inner( | ||
165 | db, | ||
166 | ItemInNs::Types(ModuleDefId::ModuleId(info.container)), | ||
167 | from, | ||
168 | best_path_len - 1, | ||
169 | )?; | ||
170 | path.segments.push(info.path.segments.last().unwrap().clone()); | ||
171 | Some(path) | ||
172 | }) | ||
173 | }); | ||
174 | |||
175 | for path in extern_paths { | ||
176 | let new_path = if let Some(best_path) = best_path { | ||
177 | select_best_path(best_path, path, prefer_no_std) | ||
178 | } else { | ||
179 | path | ||
180 | }; | ||
181 | best_path = Some(new_path); | ||
182 | } | ||
160 | } | 183 | } |
184 | |||
161 | best_path | 185 | best_path |
162 | } | 186 | } |
163 | 187 | ||
@@ -185,69 +209,86 @@ fn select_best_path(old_path: ModPath, new_path: ModPath, prefer_no_std: bool) - | |||
185 | } | 209 | } |
186 | } | 210 | } |
187 | 211 | ||
188 | fn find_importable_locations( | 212 | /// Finds locations in `from.krate` from which `item` can be imported by `from`. |
213 | fn find_local_import_locations( | ||
189 | db: &dyn DefDatabase, | 214 | db: &dyn DefDatabase, |
190 | item: ItemInNs, | 215 | item: ItemInNs, |
191 | from: ModuleId, | 216 | from: ModuleId, |
192 | ) -> Vec<(ModuleId, Name)> { | 217 | ) -> Vec<(ModuleId, Name)> { |
193 | let crate_graph = db.crate_graph(); | 218 | let _p = profile("find_local_import_locations"); |
194 | let mut result = Vec::new(); | 219 | |
195 | // We only look in the crate from which we are importing, and the direct | 220 | // `from` can import anything below `from` with visibility of at least `from`, and anything |
196 | // dependencies. We cannot refer to names from transitive dependencies | 221 | // above `from` with any visibility. That means we do not need to descend into private siblings |
197 | // directly (only through reexports in direct dependencies). | 222 | // of `from` (and similar). |
198 | for krate in Some(from.krate) | 223 | |
199 | .into_iter() | 224 | let def_map = db.crate_def_map(from.krate); |
200 | .chain(crate_graph[from.krate].dependencies.iter().map(|dep| dep.crate_id)) | 225 | |
201 | { | 226 | // Compute the initial worklist. We start with all direct child modules of `from` as well as all |
202 | result.extend( | 227 | // of its (recursive) parent modules. |
203 | db.importable_locations_of(item, krate) | 228 | let data = &def_map.modules[from.local_id]; |
204 | .iter() | 229 | let mut worklist = data |
205 | .filter(|(_, _, vis)| vis.is_visible_from(db, from)) | 230 | .children |
206 | .map(|(m, n, _)| (*m, n.clone())), | 231 | .values() |
207 | ); | 232 | .map(|child| ModuleId { krate: from.krate, local_id: *child }) |
208 | } | 233 | .collect::<Vec<_>>(); |
209 | result | 234 | let mut parent = data.parent; |
210 | } | 235 | while let Some(p) = parent { |
236 | worklist.push(ModuleId { krate: from.krate, local_id: p }); | ||
237 | parent = def_map.modules[p].parent; | ||
238 | } | ||
239 | |||
240 | let mut seen: FxHashSet<_> = FxHashSet::default(); | ||
241 | |||
242 | let mut locations = Vec::new(); | ||
243 | while let Some(module) = worklist.pop() { | ||
244 | if !seen.insert(module) { | ||
245 | continue; // already processed this module | ||
246 | } | ||
247 | |||
248 | let ext_def_map; | ||
249 | let data = if module.krate == from.krate { | ||
250 | &def_map[module.local_id] | ||
251 | } else { | ||
252 | // The crate might reexport a module defined in another crate. | ||
253 | ext_def_map = db.crate_def_map(module.krate); | ||
254 | &ext_def_map[module.local_id] | ||
255 | }; | ||
211 | 256 | ||
212 | /// Collects all locations from which we might import the item in a particular | ||
213 | /// crate. These include the original definition of the item, and any | ||
214 | /// non-private `use`s. | ||
215 | /// | ||
216 | /// Note that the crate doesn't need to be the one in which the item is defined; | ||
217 | /// it might be re-exported in other crates. | ||
218 | pub(crate) fn importable_locations_of_query( | ||
219 | db: &dyn DefDatabase, | ||
220 | item: ItemInNs, | ||
221 | krate: CrateId, | ||
222 | ) -> Arc<[(ModuleId, Name, Visibility)]> { | ||
223 | let _p = profile("importable_locations_of_query"); | ||
224 | let def_map = db.crate_def_map(krate); | ||
225 | let mut result = Vec::new(); | ||
226 | for (local_id, data) in def_map.modules.iter() { | ||
227 | if let Some((name, vis)) = data.scope.name_of(item) { | 257 | if let Some((name, vis)) = data.scope.name_of(item) { |
228 | let is_private = if let Visibility::Module(private_to) = vis { | 258 | if vis.is_visible_from(db, from) { |
229 | private_to.local_id == local_id | 259 | let is_private = if let Visibility::Module(private_to) = vis { |
230 | } else { | 260 | private_to.local_id == module.local_id |
231 | false | 261 | } else { |
232 | }; | 262 | false |
233 | let is_original_def = if let Some(module_def_id) = item.as_module_def_id() { | 263 | }; |
234 | data.scope.declarations().any(|it| it == module_def_id) | 264 | let is_original_def = if let Some(module_def_id) = item.as_module_def_id() { |
235 | } else { | 265 | data.scope.declarations().any(|it| it == module_def_id) |
236 | false | 266 | } else { |
237 | }; | 267 | false |
238 | if is_private && !is_original_def { | 268 | }; |
269 | |||
239 | // Ignore private imports. these could be used if we are | 270 | // Ignore private imports. these could be used if we are |
240 | // in a submodule of this module, but that's usually not | 271 | // in a submodule of this module, but that's usually not |
241 | // what the user wants; and if this module can import | 272 | // what the user wants; and if this module can import |
242 | // the item and we're a submodule of it, so can we. | 273 | // the item and we're a submodule of it, so can we. |
243 | // Also this keeps the cached data smaller. | 274 | // Also this keeps the cached data smaller. |
244 | continue; | 275 | if !is_private || is_original_def { |
276 | locations.push((module, name.clone())); | ||
277 | } | ||
278 | } | ||
279 | } | ||
280 | |||
281 | // Descend into all modules visible from `from`. | ||
282 | for (_, per_ns) in data.scope.entries() { | ||
283 | if let Some((ModuleDefId::ModuleId(module), vis)) = per_ns.take_types_vis() { | ||
284 | if vis.is_visible_from(db, from) { | ||
285 | worklist.push(module); | ||
286 | } | ||
245 | } | 287 | } |
246 | result.push((ModuleId { krate, local_id }, name.clone(), vis)); | ||
247 | } | 288 | } |
248 | } | 289 | } |
249 | 290 | ||
250 | Arc::from(result) | 291 | locations |
251 | } | 292 | } |
252 | 293 | ||
253 | #[cfg(test)] | 294 | #[cfg(test)] |
@@ -264,8 +305,8 @@ mod tests { | |||
264 | /// `code` needs to contain a cursor marker; checks that `find_path` for the | 305 | /// `code` needs to contain a cursor marker; checks that `find_path` for the |
265 | /// item the `path` refers to returns that same path when called from the | 306 | /// item the `path` refers to returns that same path when called from the |
266 | /// module the cursor is in. | 307 | /// module the cursor is in. |
267 | fn check_found_path(code: &str, path: &str) { | 308 | fn check_found_path(ra_fixture: &str, path: &str) { |
268 | let (db, pos) = TestDB::with_position(code); | 309 | let (db, pos) = TestDB::with_position(ra_fixture); |
269 | let module = db.module_for_file(pos.file_id); | 310 | let module = db.module_for_file(pos.file_id); |
270 | let parsed_path_file = ra_syntax::SourceFile::parse(&format!("use {};", path)); | 311 | let parsed_path_file = ra_syntax::SourceFile::parse(&format!("use {};", path)); |
271 | let ast_path = parsed_path_file | 312 | let ast_path = parsed_path_file |
@@ -396,6 +437,44 @@ mod tests { | |||
396 | } | 437 | } |
397 | 438 | ||
398 | #[test] | 439 | #[test] |
440 | fn partially_imported() { | ||
441 | // Tests that short paths are used even for external items, when parts of the path are | ||
442 | // already in scope. | ||
443 | check_found_path( | ||
444 | r#" | ||
445 | //- /main.rs crate:main deps:ra_syntax | ||
446 | |||
447 | use ra_syntax::ast; | ||
448 | <|> | ||
449 | |||
450 | //- /lib.rs crate:ra_syntax | ||
451 | pub mod ast { | ||
452 | pub enum ModuleItem { | ||
453 | A, B, C, | ||
454 | } | ||
455 | } | ||
456 | "#, | ||
457 | "ast::ModuleItem", | ||
458 | ); | ||
459 | |||
460 | check_found_path( | ||
461 | r#" | ||
462 | //- /main.rs crate:main deps:ra_syntax | ||
463 | |||
464 | <|> | ||
465 | |||
466 | //- /lib.rs crate:ra_syntax | ||
467 | pub mod ast { | ||
468 | pub enum ModuleItem { | ||
469 | A, B, C, | ||
470 | } | ||
471 | } | ||
472 | "#, | ||
473 | "ra_syntax::ast::ModuleItem", | ||
474 | ); | ||
475 | } | ||
476 | |||
477 | #[test] | ||
399 | fn same_crate_reexport() { | 478 | fn same_crate_reexport() { |
400 | let code = r#" | 479 | let code = r#" |
401 | //- /main.rs | 480 | //- /main.rs |