aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir/src/nameres.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_hir/src/nameres.rs')
-rw-r--r--crates/ra_hir/src/nameres.rs539
1 files changed, 4 insertions, 535 deletions
diff --git a/crates/ra_hir/src/nameres.rs b/crates/ra_hir/src/nameres.rs
index 59297425e..2248842de 100644
--- a/crates/ra_hir/src/nameres.rs
+++ b/crates/ra_hir/src/nameres.rs
@@ -17,43 +17,15 @@
17pub(crate) mod lower; 17pub(crate) mod lower;
18pub(crate) mod crate_def_map; 18pub(crate) mod crate_def_map;
19 19
20use std::{time, sync::Arc}; 20use rustc_hash::FxHashMap;
21
22use rustc_hash::{FxHashMap, FxHashSet};
23
24use ra_arena::map::ArenaMap;
25use ra_db::Edition; 21use ra_db::Edition;
26use test_utils::tested_by;
27 22
28use crate::{ 23use crate::{
29 Module, ModuleDef, 24 ModuleDef, Name,
30 Path, PathKind, PersistentHirDatabase, 25 nameres::lower::ImportId,
31 Crate, Name,
32 nameres::{
33 crate_def_map::{CrateDefMap, ModuleId},
34 lower::{ImportId, LoweredModule, ImportData}
35 },
36}; 26};
37 27
38/// `ItemMap` is the result of module name resolution. It contains, for each 28pub(crate) use self::crate_def_map::{CrateDefMap, ModuleId};
39/// module, the set of visible items.
40#[derive(Debug, PartialEq, Eq)]
41pub struct ItemMap {
42 edition: Edition,
43 /// The prelude module for this crate. This either comes from an import
44 /// marked with the `prelude_import` attribute, or (in the normal case) from
45 /// a dependency (`std` or `core`).
46 pub(crate) prelude: Option<Module>,
47 pub(crate) extern_prelude: FxHashMap<Name, ModuleDef>,
48 per_module: ArenaMap<ModuleId, ModuleScope>,
49}
50
51impl std::ops::Index<ModuleId> for ItemMap {
52 type Output = ModuleScope;
53 fn index(&self, id: ModuleId) -> &ModuleScope {
54 &self.per_module[id]
55 }
56}
57 29
58#[derive(Debug, Default, PartialEq, Eq, Clone)] 30#[derive(Debug, Default, PartialEq, Eq, Clone)]
59pub struct ModuleScope { 31pub struct ModuleScope {
@@ -158,292 +130,6 @@ impl<T> PerNs<T> {
158 } 130 }
159} 131}
160 132
161struct Resolver<'a, DB> {
162 db: &'a DB,
163 input: &'a FxHashMap<ModuleId, Arc<LoweredModule>>,
164 krate: Crate,
165 def_map: Arc<CrateDefMap>,
166 processed_imports: FxHashSet<(ModuleId, ImportId)>,
167 /// If module `a` has `use b::*`, then this contains the mapping b -> a (and the import)
168 glob_imports: FxHashMap<ModuleId, Vec<(ModuleId, ImportId)>>,
169 result: ItemMap,
170}
171
172impl<'a, DB> Resolver<'a, DB>
173where
174 DB: PersistentHirDatabase,
175{
176 fn new(
177 db: &'a DB,
178 input: &'a FxHashMap<ModuleId, Arc<LoweredModule>>,
179 krate: Crate,
180 ) -> Resolver<'a, DB> {
181 Resolver {
182 db,
183 input,
184 krate,
185 def_map: db.crate_def_map(krate),
186 processed_imports: FxHashSet::default(),
187 glob_imports: FxHashMap::default(),
188 result: ItemMap {
189 edition: krate.edition(db),
190 prelude: None,
191 extern_prelude: FxHashMap::default(),
192 per_module: ArenaMap::default(),
193 },
194 }
195 }
196
197 pub(crate) fn resolve(mut self) -> ItemMap {
198 self.populate_extern_prelude();
199 for (&module_id, items) in self.input.iter() {
200 self.populate_module(module_id, Arc::clone(items));
201 }
202
203 let mut iter = 0;
204 loop {
205 iter += 1;
206 if iter > 1000 {
207 panic!("failed to reach fixedpoint after 1000 iters")
208 }
209 let processed_imports_count = self.processed_imports.len();
210 for &module_id in self.input.keys() {
211 self.db.check_canceled();
212 self.resolve_imports(module_id);
213 }
214 if processed_imports_count == self.processed_imports.len() {
215 // no new imports resolved
216 break;
217 }
218 }
219 self.result
220 }
221
222 fn populate_extern_prelude(&mut self) {
223 for dep in self.krate.dependencies(self.db) {
224 log::debug!("crate dep {:?} -> {:?}", dep.name, dep.krate);
225 if let Some(module) = dep.krate.root_module(self.db) {
226 self.result.extern_prelude.insert(dep.name.clone(), module.into());
227 }
228 // look for the prelude
229 if self.result.prelude.is_none() {
230 let item_map = self.db.item_map(dep.krate);
231 if item_map.prelude.is_some() {
232 self.result.prelude = item_map.prelude;
233 }
234 }
235 }
236 }
237
238 fn populate_module(&mut self, module_id: ModuleId, input: Arc<LoweredModule>) {
239 let mut module_items = ModuleScope::default();
240 for (import_id, import_data) in input.imports.iter() {
241 if let Some(last_segment) = import_data.path.segments.iter().last() {
242 if !import_data.is_glob {
243 let name =
244 import_data.alias.clone().unwrap_or_else(|| last_segment.name.clone());
245 module_items
246 .items
247 .insert(name, Resolution { def: PerNs::none(), import: Some(import_id) });
248 }
249 }
250 }
251 // Populate explicitly declared items, except modules
252 for (name, &def) in input.declarations.iter() {
253 let resolution = Resolution { def, import: None };
254 module_items.items.insert(name.clone(), resolution);
255 }
256
257 // Populate modules
258 for (name, module_id) in self.def_map[module_id].children.iter() {
259 let module = Module { module_id: *module_id, krate: self.krate };
260 self.add_module_item(&mut module_items, name.clone(), PerNs::types(module.into()));
261 }
262
263 self.result.per_module.insert(module_id, module_items);
264 }
265
266 fn add_module_item(&self, module_items: &mut ModuleScope, name: Name, def: PerNs<ModuleDef>) {
267 let resolution = Resolution { def, import: None };
268 module_items.items.insert(name, resolution);
269 }
270
271 fn resolve_imports(&mut self, module_id: ModuleId) {
272 for (import_id, import_data) in self.input[&module_id].imports.iter() {
273 if self.processed_imports.contains(&(module_id, import_id)) {
274 // already done
275 continue;
276 }
277 if self.resolve_import(module_id, import_id, import_data) == ReachedFixedPoint::Yes {
278 log::debug!("import {:?} resolved (or definite error)", import_id);
279 self.processed_imports.insert((module_id, import_id));
280 }
281 }
282 }
283
284 fn resolve_import(
285 &mut self,
286 module_id: ModuleId,
287 import_id: ImportId,
288 import: &ImportData,
289 ) -> ReachedFixedPoint {
290 log::debug!("resolving import: {:?} ({:?})", import, self.result.edition);
291 let original_module = Module { krate: self.krate, module_id };
292
293 let (def, reached_fixedpoint) = if import.is_extern_crate {
294 let res = self.result.resolve_name_in_extern_prelude(
295 &import
296 .path
297 .as_ident()
298 .expect("extern crate should have been desugared to one-element path"),
299 );
300 (res, if res.is_none() { ReachedFixedPoint::No } else { ReachedFixedPoint::Yes })
301 } else {
302 let res = self.result.resolve_path_fp(
303 self.db,
304 ResolveMode::Import,
305 original_module,
306 &import.path,
307 );
308
309 (res.resolved_def, res.reached_fixedpoint)
310 };
311
312 if reached_fixedpoint != ReachedFixedPoint::Yes {
313 return reached_fixedpoint;
314 }
315
316 if import.is_glob {
317 log::debug!("glob import: {:?}", import);
318 match def.take_types() {
319 Some(ModuleDef::Module(m)) => {
320 if import.is_prelude {
321 tested_by!(std_prelude);
322 self.result.prelude = Some(m);
323 } else if m.krate != self.krate {
324 tested_by!(glob_across_crates);
325 // glob import from other crate => we can just import everything once
326 let item_map = self.db.item_map(m.krate);
327 let scope = &item_map[m.module_id];
328 let items = scope
329 .items
330 .iter()
331 .map(|(name, res)| (name.clone(), res.clone()))
332 .collect::<Vec<_>>();
333 self.update(module_id, Some(import_id), &items);
334 } else {
335 // glob import from same crate => we do an initial
336 // import, and then need to propagate any further
337 // additions
338 let scope = &self.result[m.module_id];
339 let items = scope
340 .items
341 .iter()
342 .map(|(name, res)| (name.clone(), res.clone()))
343 .collect::<Vec<_>>();
344 self.update(module_id, Some(import_id), &items);
345 // record the glob import in case we add further items
346 self.glob_imports
347 .entry(m.module_id)
348 .or_default()
349 .push((module_id, import_id));
350 }
351 }
352 Some(ModuleDef::Enum(e)) => {
353 tested_by!(glob_enum);
354 // glob import from enum => just import all the variants
355 let variants = e.variants(self.db);
356 let resolutions = variants
357 .into_iter()
358 .filter_map(|variant| {
359 let res = Resolution {
360 def: PerNs::both(variant.into(), variant.into()),
361 import: Some(import_id),
362 };
363 let name = variant.name(self.db)?;
364 Some((name, res))
365 })
366 .collect::<Vec<_>>();
367 self.update(module_id, Some(import_id), &resolutions);
368 }
369 Some(d) => {
370 log::debug!("glob import {:?} from non-module/enum {:?}", import, d);
371 }
372 None => {
373 log::debug!("glob import {:?} didn't resolve as type", import);
374 }
375 }
376 } else {
377 let last_segment = import.path.segments.last().unwrap();
378 let name = import.alias.clone().unwrap_or_else(|| last_segment.name.clone());
379 log::debug!("resolved import {:?} ({:?}) to {:?}", name, import, def);
380
381 // extern crates in the crate root are special-cased to insert entries into the extern prelude: rust-lang/rust#54658
382 if let Some(root_module) = self.krate.root_module(self.db) {
383 if import.is_extern_crate && module_id == root_module.module_id {
384 if let Some(def) = def.take_types() {
385 self.result.extern_prelude.insert(name.clone(), def);
386 }
387 }
388 }
389 let resolution = Resolution { def, import: Some(import_id) };
390 self.update(module_id, None, &[(name, resolution)]);
391 }
392 reached_fixedpoint
393 }
394
395 fn update(
396 &mut self,
397 module_id: ModuleId,
398 import: Option<ImportId>,
399 resolutions: &[(Name, Resolution)],
400 ) {
401 self.update_recursive(module_id, import, resolutions, 0)
402 }
403
404 fn update_recursive(
405 &mut self,
406 module_id: ModuleId,
407 import: Option<ImportId>,
408 resolutions: &[(Name, Resolution)],
409 depth: usize,
410 ) {
411 if depth > 100 {
412 // prevent stack overflows (but this shouldn't be possible)
413 panic!("infinite recursion in glob imports!");
414 }
415 let module_items = self.result.per_module.get_mut(module_id).unwrap();
416 let mut changed = false;
417 for (name, res) in resolutions {
418 let existing = module_items.items.entry(name.clone()).or_default();
419 if existing.def.types.is_none() && res.def.types.is_some() {
420 existing.def.types = res.def.types;
421 existing.import = import.or(res.import);
422 changed = true;
423 }
424 if existing.def.values.is_none() && res.def.values.is_some() {
425 existing.def.values = res.def.values;
426 existing.import = import.or(res.import);
427 changed = true;
428 }
429 }
430 if !changed {
431 return;
432 }
433 let glob_imports = self
434 .glob_imports
435 .get(&module_id)
436 .into_iter()
437 .flat_map(|v| v.iter())
438 .cloned()
439 .collect::<Vec<_>>();
440 for (glob_importing_module, glob_import) in glob_imports {
441 // We pass the glob import so that the tracked import in those modules is that glob import
442 self.update_recursive(glob_importing_module, Some(glob_import), resolutions, depth + 1);
443 }
444 }
445}
446
447#[derive(Debug, Clone)] 133#[derive(Debug, Clone)]
448struct ResolvePathResult { 134struct ResolvePathResult {
449 resolved_def: PerNs<ModuleDef>, 135 resolved_def: PerNs<ModuleDef>,
@@ -476,220 +162,3 @@ enum ReachedFixedPoint {
476 Yes, 162 Yes,
477 No, 163 No,
478} 164}
479
480impl ItemMap {
481 pub(crate) fn item_map_query(db: &impl PersistentHirDatabase, krate: Crate) -> Arc<ItemMap> {
482 let start = time::Instant::now();
483 let def_map = db.crate_def_map(krate);
484 let input = def_map
485 .modules()
486 .map(|module_id| (module_id, db.lower_module(Module { krate, module_id })))
487 .collect::<FxHashMap<_, _>>();
488
489 let resolver = Resolver::new(db, &input, krate);
490 let res = resolver.resolve();
491 let elapsed = start.elapsed();
492 log::info!("item_map: {:?}", elapsed);
493 Arc::new(res)
494 }
495
496 pub(crate) fn resolve_path(
497 &self,
498 db: &impl PersistentHirDatabase,
499 original_module: Module,
500 path: &Path,
501 ) -> (PerNs<ModuleDef>, Option<usize>) {
502 let res = self.resolve_path_fp(db, ResolveMode::Other, original_module, path);
503 (res.resolved_def, res.segment_index)
504 }
505
506 fn resolve_in_prelude(
507 &self,
508 db: &impl PersistentHirDatabase,
509 original_module: Module,
510 name: &Name,
511 ) -> PerNs<ModuleDef> {
512 if let Some(prelude) = self.prelude {
513 let resolution = if prelude.krate == original_module.krate {
514 self[prelude.module_id].items.get(name).cloned()
515 } else {
516 db.item_map(prelude.krate)[prelude.module_id].items.get(name).cloned()
517 };
518 resolution.map(|r| r.def).unwrap_or_else(PerNs::none)
519 } else {
520 PerNs::none()
521 }
522 }
523
524 pub(crate) fn resolve_name_in_module(
525 &self,
526 db: &impl PersistentHirDatabase,
527 module: Module,
528 name: &Name,
529 ) -> PerNs<ModuleDef> {
530 // Resolve in:
531 // - current module / scope
532 // - extern prelude
533 // - std prelude
534 let from_scope = self[module.module_id].items.get(name).map_or(PerNs::none(), |it| it.def);
535 let from_extern_prelude =
536 self.extern_prelude.get(name).map_or(PerNs::none(), |&it| PerNs::types(it));
537 let from_prelude = self.resolve_in_prelude(db, module, name);
538
539 from_scope.or(from_extern_prelude).or(from_prelude)
540 }
541
542 fn resolve_name_in_extern_prelude(&self, name: &Name) -> PerNs<ModuleDef> {
543 self.extern_prelude.get(name).map_or(PerNs::none(), |&it| PerNs::types(it))
544 }
545
546 fn resolve_name_in_crate_root_or_extern_prelude(
547 &self,
548 db: &impl PersistentHirDatabase,
549 module: Module,
550 name: &Name,
551 ) -> PerNs<ModuleDef> {
552 let crate_root = module.crate_root(db);
553 let from_crate_root =
554 self[crate_root.module_id].items.get(name).map_or(PerNs::none(), |it| it.def);
555 let from_extern_prelude = self.resolve_name_in_extern_prelude(name);
556
557 from_crate_root.or(from_extern_prelude)
558 }
559
560 // Returns Yes if we are sure that additions to `ItemMap` wouldn't change
561 // the result.
562 fn resolve_path_fp(
563 &self,
564 db: &impl PersistentHirDatabase,
565 mode: ResolveMode,
566 original_module: Module,
567 path: &Path,
568 ) -> ResolvePathResult {
569 let mut segments = path.segments.iter().enumerate();
570 let mut curr_per_ns: PerNs<ModuleDef> = match path.kind {
571 PathKind::Crate => PerNs::types(original_module.crate_root(db).into()),
572 PathKind::Self_ => PerNs::types(original_module.into()),
573 // plain import or absolute path in 2015: crate-relative with
574 // fallback to extern prelude (with the simplification in
575 // rust-lang/rust#57745)
576 // TODO there must be a nicer way to write this condition
577 PathKind::Plain | PathKind::Abs
578 if self.edition == Edition::Edition2015
579 && (path.kind == PathKind::Abs || mode == ResolveMode::Import) =>
580 {
581 let segment = match segments.next() {
582 Some((_, segment)) => segment,
583 None => return ResolvePathResult::empty(ReachedFixedPoint::Yes),
584 };
585 log::debug!("resolving {:?} in crate root (+ extern prelude)", segment);
586 self.resolve_name_in_crate_root_or_extern_prelude(
587 db,
588 original_module,
589 &segment.name,
590 )
591 }
592 PathKind::Plain => {
593 let segment = match segments.next() {
594 Some((_, segment)) => segment,
595 None => return ResolvePathResult::empty(ReachedFixedPoint::Yes),
596 };
597 log::debug!("resolving {:?} in module", segment);
598 self.resolve_name_in_module(db, original_module, &segment.name)
599 }
600 PathKind::Super => {
601 if let Some(p) = original_module.parent(db) {
602 PerNs::types(p.into())
603 } else {
604 log::debug!("super path in root module");
605 return ResolvePathResult::empty(ReachedFixedPoint::Yes);
606 }
607 }
608 PathKind::Abs => {
609 // 2018-style absolute path -- only extern prelude
610 let segment = match segments.next() {
611 Some((_, segment)) => segment,
612 None => return ResolvePathResult::empty(ReachedFixedPoint::Yes),
613 };
614 if let Some(def) = self.extern_prelude.get(&segment.name) {
615 log::debug!("absolute path {:?} resolved to crate {:?}", path, def);
616 PerNs::types(*def)
617 } else {
618 return ResolvePathResult::empty(ReachedFixedPoint::No); // extern crate declarations can add to the extern prelude
619 }
620 }
621 };
622
623 for (i, segment) in segments {
624 let curr = match curr_per_ns.as_ref().take_types() {
625 Some(r) => r,
626 None => {
627 // we still have path segments left, but the path so far
628 // didn't resolve in the types namespace => no resolution
629 // (don't break here because `curr_per_ns` might contain
630 // something in the value namespace, and it would be wrong
631 // to return that)
632 return ResolvePathResult::empty(ReachedFixedPoint::No);
633 }
634 };
635 // resolve segment in curr
636
637 curr_per_ns = match curr {
638 ModuleDef::Module(module) => {
639 if module.krate != original_module.krate {
640 let path = Path {
641 segments: path.segments[i..].iter().cloned().collect(),
642 kind: PathKind::Self_,
643 };
644 log::debug!("resolving {:?} in other crate", path);
645 let item_map = db.item_map(module.krate);
646 let (def, s) = item_map.resolve_path(db, *module, &path);
647 return ResolvePathResult::with(
648 def,
649 ReachedFixedPoint::Yes,
650 s.map(|s| s + i),
651 );
652 }
653
654 match self[module.module_id].items.get(&segment.name) {
655 Some(res) if !res.def.is_none() => res.def,
656 _ => {
657 log::debug!("path segment {:?} not found", segment.name);
658 return ResolvePathResult::empty(ReachedFixedPoint::No);
659 }
660 }
661 }
662 ModuleDef::Enum(e) => {
663 // enum variant
664 tested_by!(can_import_enum_variant);
665 match e.variant(db, &segment.name) {
666 Some(variant) => PerNs::both(variant.into(), variant.into()),
667 None => {
668 return ResolvePathResult::with(
669 PerNs::types((*e).into()),
670 ReachedFixedPoint::Yes,
671 Some(i),
672 );
673 }
674 }
675 }
676 s => {
677 // could be an inherent method call in UFCS form
678 // (`Struct::method`), or some other kind of associated item
679 log::debug!(
680 "path segment {:?} resolved to non-module {:?}, but is not last",
681 segment.name,
682 curr,
683 );
684
685 return ResolvePathResult::with(
686 PerNs::types((*s).into()),
687 ReachedFixedPoint::Yes,
688 Some(i),
689 );
690 }
691 };
692 }
693 ResolvePathResult::with(curr_per_ns, ReachedFixedPoint::Yes, None)
694 }
695}