1use purrdf_lex::allocation::{Memory, OrderedTable, Shared};
13use purrdf_lex::walk::WorkList;
14use std::collections::{BTreeMap, BTreeSet};
15use std::error::Error;
16use std::fmt;
17
18use crate::budget::Budget;
19use crate::cost::{btree_entry, btree_map, vec_first, vec_slot};
20use crate::error::{Esc, LoadError};
21use crate::glob_scope::push_work;
22use crate::index::{Index, UseKind};
23use crate::item::{ItemId, Namespace, SharedStr, SymbolKind};
24use crate::meter::{Meter, NativeAdmission, Steps, Transient, over_budget};
25use crate::modtree::TargetId;
26use crate::path::RelPath;
27use crate::settle::{Source, slot, storage_failure};
28use crate::target::PackageId;
29use crate::work::{self, Work};
30
31mod determinacy;
32mod glob_facts;
33mod observation;
34mod variant_import;
35pub use observation::ResolutionAttempt;
36
37#[derive(Debug, Default)]
39pub(crate) struct Walked {
40 pub(crate) modules: BTreeSet<usize>,
41 pub(crate) items: BTreeMap<ItemId, Hit>,
42}
43
44#[derive(Debug, Clone)]
46pub(crate) struct Hit {
47 pub(crate) via_glob: bool,
48 pub(crate) last: Option<Source>,
49}
50
51impl Hit {
52 fn rank(&self) -> (bool, &Option<Source>) {
55 (self.via_glob, &self.last)
56 }
57}
58
59#[derive(Debug, Clone, Copy)]
62struct Step<'s> {
63 offset: usize,
64 seg: &'s str,
65 ns: Namespace,
66 last: bool,
67}
68
69fn merge(
71 found: &mut BTreeMap<ItemId, Hit>,
72 id: ItemId,
73 hit: Hit,
74 steps: Steps<'_>,
75) -> Result<(), LoadError> {
76 if !found.contains_key(&id) {
77 steps.reserve(
78 btree_entry::<ItemId, Hit>()
79 + if found.is_empty() {
80 btree_map::<ItemId, Hit>()
81 } else {
82 0
83 },
84 )?;
85 }
86 match found.entry(id) {
87 std::collections::btree_map::Entry::Vacant(vacant) => {
88 vacant.insert(hit);
89 }
90 std::collections::btree_map::Entry::Occupied(mut occupied) => {
91 if hit.rank() < occupied.get().rank() {
92 occupied.insert(hit);
93 }
94 }
95 }
96 Ok(())
97}
98
99#[derive(Debug)]
100pub(crate) enum Fail {
101 Storage(LoadError),
103 Missing(Vec<Source>),
104 SuperAboveRoot,
105 SeveralCrates {
111 roots: Vec<ItemId>,
112 rest: usize,
113 },
114 Ambiguous(Vec<ItemId>),
120 Budget(Refused),
124}
125
126impl From<LoadError> for Fail {
127 fn from(error: LoadError) -> Self {
128 Self::Storage(error)
129 }
130}
131
132#[derive(Default)]
134struct ImportWalks {
135 blockers: Vec<usize>,
136 ambiguous: Vec<ItemId>,
137 reads: Vec<Source>,
138}
139
140pub(crate) enum Unsettled {
142 Cycle,
143 LateImport(usize),
144}
145
146pub(crate) const LOAD_WALK: &str = "a walk of the load is never refused for its work";
150
151#[derive(Debug, Clone, Copy)]
153pub(crate) struct Refused {
154 limit: usize,
156 module: usize,
158}
159
160#[derive(Debug, Default)]
164pub(crate) struct GlobFacts {
165 reach: Vec<Vec<usize>>,
166 broken: OrderedTable<usize, ()>,
167}
168
169#[derive(Debug, Clone, Default)]
175pub(crate) struct GlobFactsCache(Option<Shared<GlobFacts>>);
176
177impl GlobFactsCache {
178 pub(crate) fn get(&self) -> Option<&GlobFacts> {
179 self.0.as_deref()
180 }
181
182 pub(crate) fn replace(&mut self, facts: Shared<GlobFacts>) {
183 self.0 = Some(facts);
184 }
185}
186
187impl PartialEq for GlobFactsCache {
188 fn eq(&self, _other: &Self) -> bool {
189 true
190 }
191}
192
193impl Eq for GlobFactsCache {}
194
195#[derive(Default)]
198struct Walks {
199 found: BTreeMap<ItemId, Hit>,
200 missing: Vec<Source>,
201 reads: Vec<Source>,
202}
203
204enum GlobPath {
206 Resolves(BTreeSet<usize>),
208 Nothing,
211 Unknown,
215 Misses(Vec<Source>),
217}
218
219#[derive(Debug, Clone, Copy, PartialEq, Eq)]
221pub(crate) enum Heads {
222 Local,
224 Code {
228 test: bool,
230 },
231 Use {
238 test: bool,
240 own: Option<usize>,
242 },
243}
244
245impl Heads {
246 pub(crate) fn own(self) -> Option<usize> {
248 match self {
249 Self::Use { own, .. } => own,
250 Self::Local | Self::Code { .. } => None,
251 }
252 }
253}
254
255#[derive(Debug, Clone, PartialEq, Eq)]
257#[non_exhaustive]
258pub struct Resolution {
259 pub path: String,
261 pub namespace: Namespace,
263 pub sites: Vec<ItemId>,
267 pub via_glob: bool,
269 pub chain: Vec<String>,
272 pub type_aliases: Vec<ItemId>,
276}
277
278#[derive(Debug, Clone, PartialEq, Eq)]
280#[non_exhaustive]
281pub enum ResolveError {
282 NotFound(String),
285 Ambiguous(Vec<ItemId>),
291 Cyclic(String),
293 IndeterminateImport {
297 path: String,
299 file: RelPath,
301 line: usize,
303 },
304 Invalid(String),
306 UnresolvedSelf(String),
311 UnknownPackage(String),
314 AmbiguousPackageName(String),
317 UnknownPackageId(PackageId),
319 UnconfiguredPackage(PackageId),
321 UnconfiguredDefinition(ItemId),
323 UnknownModule(String),
326 UnresolvedGlob {
334 path: String,
336 glob: String,
338 module: String,
340 },
341 Budget {
352 budget: Budget,
354 limit: usize,
356 file: RelPath,
358 line: Option<usize>,
360 },
361 Storage {
364 file: RelPath,
366 line: Option<usize>,
368 what: String,
370 },
371}
372
373impl fmt::Display for ResolveError {
374 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
375 match self {
376 Self::UnconfiguredPackage(id) => write!(
377 f,
378 "package {} has no declared configuration; use a configured locked load",
379 id.index()
380 ),
381 Self::UnconfiguredDefinition(id) => write!(
382 f,
383 "definition {} has no admitted active context",
384 id.index()
385 ),
386 Self::NotFound(path) => write!(f, "`{}` names nothing in the workspace", Esc(path)),
387 Self::Ambiguous(ids) => write!(f, "the path names {} different symbols", ids.len()),
388 Self::Cyclic(path) => {
389 write!(f, "`{}` goes through imports that form a cycle", Esc(path))
390 }
391 Self::IndeterminateImport { path, file, line } => write!(
392 f,
393 "`{}` goes through an import at {}:{line} whose binding became accessible after it was determined absent",
394 Esc(path),
395 Esc(file.as_str())
396 ),
397 Self::Invalid(text) => write!(f, "`{}` is not a path", Esc(text)),
398 Self::UnresolvedSelf(path) => write!(
399 f,
400 "`{}` goes through the self type of an inherent impl that the index cannot see",
401 Esc(path)
402 ),
403 Self::UnknownPackage(package) => {
404 write!(f, "`{}` is not a package of the workspace", Esc(package))
405 }
406 Self::AmbiguousPackageName(package) => write!(
407 f,
408 "several packages are named `{}`; select a PackageId from this workspace",
409 Esc(package)
410 ),
411 Self::UnknownPackageId(id) => {
412 write!(
413 f,
414 "package identity {} is not in this workspace",
415 id.index()
416 )
417 }
418 Self::UnknownModule(module) => {
419 write!(f, "`{}` is not a module of the workspace", Esc(module))
420 }
421 Self::UnresolvedGlob { path, glob, module } => write!(
422 f,
423 "`{}` reads the glob `{}::*` of module `{}`, whose path names nothing in the \
424 workspace",
425 Esc(path),
426 Esc(glob),
427 Esc(module)
428 ),
429 Self::Budget {
430 budget,
431 limit,
432 file,
433 line,
434 } => write!(
435 f,
436 "the query is over budget: {}",
437 over_budget(*budget, *limit, file, *line)
438 ),
439 Self::Storage { file, line, what } => write!(
440 f,
441 "query storage failed at {}{}: {}",
442 Esc(file.as_str()),
443 line.map_or_else(String::new, |line| format!(":{line}")),
444 Esc(what)
445 ),
446 }
447 }
448}
449
450impl Error for ResolveError {}
451
452impl ResolveError {
453 fn storage(error: LoadError) -> Self {
454 let crate::error::LoadErrorKind::Budget { budget, limit } = error.kind else {
455 return Self::Storage {
456 what: error.kind.to_string(),
457 file: error.file,
458 line: error.line,
459 };
460 };
461 Self::Budget {
462 budget,
463 limit,
464 file: error.file,
465 line: error.line,
466 }
467 }
468}
469
470fn note(
473 reads: &mut Option<&mut Vec<Source>>,
474 module: usize,
475 ns: Namespace,
476 name: &str,
477 steps: Steps<'_>,
478) -> Result<(), Fail> {
479 if let Some(list) = reads.as_deref_mut() {
480 push_source(list, module, ns, name, steps)?;
481 }
482 Ok(())
483}
484
485fn push_source(
486 list: &mut Vec<Source>,
487 module: usize,
488 ns: Namespace,
489 name: &str,
490 steps: Steps<'_>,
491) -> Result<(), Fail> {
492 steps
493 .reserve(
494 vec_slot::<Source>()
495 + name.len()
496 + if list.is_empty() {
497 vec_first::<Source>()
498 } else {
499 0
500 },
501 )
502 .map_err(Fail::Storage)?;
503 list.push(Source {
504 module,
505 ns,
506 name: name.to_owned(),
507 });
508 Ok(())
509}
510
511fn strip_raw(segment: &str) -> &str {
512 segment.strip_prefix("r#").map_or(segment, |plain| plain)
513}
514
515fn valid_code_segment(segment: &str) -> bool {
516 let name = strip_raw(segment);
517 let mut characters = name.chars();
518 !(matches!(name, "Self" | "_") || name != segment && matches!(name, "crate" | "self" | "super"))
519 && characters
520 .next()
521 .is_some_and(|first| first == '_' || unicode_ident::is_xid_start(first))
522 && characters.all(unicode_ident::is_xid_continue)
523}
524
525pub(crate) fn insert_module(
526 modules: &mut BTreeSet<usize>,
527 module: usize,
528 steps: Steps<'_>,
529) -> Result<(), LoadError> {
530 if !modules.contains(&module) {
531 steps.reserve(
532 btree_entry::<usize, ()>()
533 + if modules.is_empty() {
534 btree_map::<usize, ()>()
535 } else {
536 0
537 },
538 )?;
539 modules.insert(module);
540 }
541 Ok(())
542}
543
544fn reserve_ids(count: usize, steps: Steps<'_>) -> Result<(), Fail> {
545 steps
546 .reserve(vec_first::<ItemId>() + 2 * count * vec_slot::<ItemId>())
547 .map_err(Fail::Storage)?;
548 steps
549 .storage_work(count.saturating_mul(count.max(1).ilog2() as usize + 1))
550 .map_err(Fail::Storage)
551}
552
553impl Index {
554 pub(crate) fn one_crate(
557 &self,
558 modules: &BTreeSet<usize>,
559 rest: usize,
560 steps: Steps<'_>,
561 ) -> Result<(), Fail> {
562 steps
563 .reserve(vec_first::<usize>() + modules.len() * vec_slot::<usize>())
564 .map_err(Fail::Storage)?;
565 steps.storage_work(modules.len()).map_err(Fail::Storage)?;
566 let roots: Vec<usize> = modules
567 .iter()
568 .copied()
569 .filter(|module| self.modules[*module].parent.is_none())
570 .collect();
571 if roots.len() > 1 {
572 reserve_ids(roots.len(), steps)?;
573 return Err(Fail::SeveralCrates {
574 roots: self.sorted(
575 roots
576 .iter()
577 .filter_map(|root| self.root_items.get(root).copied()),
578 ),
579 rest,
580 });
581 }
582 Ok(())
583 }
584
585 pub(crate) fn extern_roots(
591 &self,
592 module: usize,
593 name: &str,
594 heads: Heads,
595 into: &mut BTreeSet<usize>,
596 steps: Steps<'_>,
597 ) -> Result<bool, Fail> {
598 let before = into.len();
599 for root in self.extern_root_candidates(module, name, heads) {
600 insert_module(into, root, steps)?;
601 }
602 Ok(into.len() > before)
603 }
604
605 pub(crate) fn extern_root_candidates<'a>(
607 &'a self,
608 module: usize,
609 name: &'a str,
610 heads: Heads,
611 ) -> impl Iterator<Item = usize> + 'a {
612 let test = match heads {
613 Heads::Code { test } | Heads::Use { test, .. } => Some(test),
614 Heads::Local => None,
615 };
616 let root = self.modules[module].root;
617 test.into_iter().flat_map(move |test| {
618 let prelude = self
619 .extern_name(module, name, test)
620 .into_iter()
621 .flat_map(move |entry| entry.roots(test));
622 let explicit = self.scopes[root]
623 .get(name)
624 .into_iter()
625 .flat_map(|entry| entry.defs[slot(Namespace::Type)].keys())
626 .filter(|id| self.items[id.0].kind == SymbolKind::ExternCrate)
627 .flat_map(|id| self.modules_for(*id));
628 prelude.chain(explicit)
629 })
630 }
631
632 pub(crate) fn crate_relative(
636 &self,
637 from: usize,
638 first: &str,
639 leading_colon: bool,
640 heads: Heads,
641 ) -> bool {
642 let keyword = matches!(first, "crate" | "self" | "super");
643 match heads {
644 Heads::Local => false,
645 Heads::Code { .. } => leading_colon && self.edition(from) == 2015,
646 Heads::Use { .. } => self.edition(from) == 2015 && (leading_colon || !keyword),
647 }
648 }
649
650 pub(crate) fn in_use_prelude(&self, module: usize, name: &str, test: bool) -> bool {
655 name == "core"
656 || (name == "std" && !self.no_std(module))
657 || self.extern_name(module, name, test).is_some()
658 || self.root_extern_crate(module, name)
659 }
660
661 pub(crate) fn read_outside_crate(
668 &self,
669 position: usize,
670 steps: Steps<'_>,
671 ) -> Result<Option<String>, Fail> {
672 let decl = &self.uses[position];
673 let UseKind::Named { segs, .. } = &decl.kind else {
674 return Ok(None);
675 };
676 let Some(head) = segs.first() else {
677 return Ok(None);
678 };
679 if matches!(head.as_str(), "crate" | "self" | "super") {
680 return Ok(None);
681 }
682 let heads = Heads::Use {
683 test: decl.test,
684 own: Some(position),
685 };
686 if self.crate_relative(decl.module, head, decl.leading_colon, heads) {
687 let root = self.modules[decl.module].root;
688 let lookup = self.read_lookup(root, Namespace::Type, head, None, None, steps)?;
689 return Ok(match lookup.as_ref() {
690 Some((bound, _)) => {
692 if bound.len() == 1 {
693 let id = bound.keys().next().expect("one bound item");
694 if self.modules_for(*id).next().is_none() {
695 if let Some(name) = self.extern_names.get(id) {
696 steps.reserve(name.len()).map_err(Fail::Storage)?;
697 Some(name.to_string())
698 } else {
699 None
700 }
701 } else {
702 None
703 }
704 } else {
705 None
706 }
707 }
708 None => {
709 if head == self.injected_crate(decl.module) {
710 steps.reserve(head.len()).map_err(Fail::Storage)?;
711 Some(head.clone())
712 } else {
713 None
714 }
715 }
716 });
717 }
718 let unbound = decl.leading_colon
719 || (self
720 .read_lookup(
721 decl.module,
722 Namespace::Type,
723 head,
724 Some(position),
725 None,
726 steps,
727 )?
728 .as_ref()
729 .is_none()
730 && !self.blocked(decl.module, head, Namespace::Type, Some(position)));
731 let mut roots = BTreeSet::new();
732 let outside = unbound
733 && self.in_use_prelude(decl.module, head, decl.test)
734 && !self.extern_roots(decl.module, head, heads, &mut roots, steps)?;
735 if outside {
736 steps.reserve(head.len()).map_err(Fail::Storage)?;
737 }
738 Ok(outside.then(|| head.clone()))
739 }
740
741 pub(crate) fn globbed_outside(
750 &self,
751 from: usize,
752 name: &str,
753 steps: Steps<'_>,
754 ) -> Result<Vec<usize>, LoadError> {
755 self.read_globbed_outside(from, name, steps)
756 .map_err(storage_failure)
757 }
758
759 fn read_globbed_outside(
760 &self,
761 from: usize,
762 name: &str,
763 steps: Steps<'_>,
764 ) -> Result<Vec<usize>, Fail> {
765 let mut seen = BTreeSet::new();
766 insert_module(&mut seen, from, steps)?;
767 let stack_memory = steps.query_meter().map(Transient::new);
768 let (stack_file, stack_line) = self.module_site(from);
769 let stack_steps =
770 steps.with_query_storage(stack_memory.as_ref(), (&stack_file, stack_line));
771 let mut work = WorkList::<_, 8>::new();
772 push_work(&mut work, from, stack_steps).map_err(Fail::Storage)?;
773 let mut found = Vec::new();
774 while let Some(module) = work.pop() {
775 for glob in self.globs_of(module) {
776 steps.storage_work(1).map_err(Fail::Storage)?;
777 let targets = match self.glob_targets(*glob, steps) {
778 Ok(targets) => targets,
779 Err(Fail::Storage(error)) => return Err(Fail::Storage(error)),
780 Err(_) => continue,
781 };
782 for target in targets {
783 if seen.contains(&target) {
784 continue;
785 }
786 insert_module(&mut seen, target, steps)?;
787 push_work(&mut work, target, stack_steps).map_err(Fail::Storage)?;
788 for position in self.imports_of(target, name) {
789 steps.storage_work(1).map_err(Fail::Storage)?;
790 let import = &self.uses[*position];
791 let crate_alias =
792 matches!(&import.kind, UseKind::Named { segs, .. } if segs.len() == 1);
793 if crate_alias
794 && !self.use_resolved[*position]
795 && self.read_visibility(&import.vis, target, from, steps)?
796 && self
797 .read_outside_crate(*position, steps)?
798 .is_some_and(|krate| krate != name)
799 {
800 steps
801 .reserve(
802 vec_slot::<usize>()
803 + if found.is_empty() {
804 vec_first::<usize>()
805 } else {
806 0
807 },
808 )
809 .map_err(Fail::Storage)?;
810 found.push(*position);
811 }
812 }
813 }
814 }
815 }
816 steps
817 .storage_work(
818 found
819 .len()
820 .saturating_mul(found.len().max(1).ilog2() as usize + 1),
821 )
822 .map_err(Fail::Storage)?;
823 found.sort_unstable();
824 Ok(found)
825 }
826
827 fn root_extern_crate(&self, module: usize, name: &str) -> bool {
830 let root = self.modules[module].root;
831 self.scopes[root].get(name).is_some_and(|entry| {
832 entry.defs[slot(Namespace::Type)]
833 .keys()
834 .any(|id| self.items[id.0].kind == SymbolKind::ExternCrate)
835 })
836 }
837
838 pub(crate) fn glob_against_prelude(
844 &self,
845 from: usize,
846 name: &str,
847 test: bool,
848 bound: &crate::settle::Bound,
849 ) -> Option<Vec<ItemId>> {
850 self.read_glob_against_prelude(from, name, test, bound, Steps::Load)
851 .expect("a nonretained prelude check reserves no import storage")
852 }
853
854 fn read_glob_against_prelude(
855 &self,
856 from: usize,
857 name: &str,
858 test: bool,
859 bound: &crate::settle::Bound,
860 steps: Steps<'_>,
861 ) -> Result<Option<Vec<ItemId>>, Fail> {
862 if self.edition(from) == 2015 || !self.in_use_prelude(from, name, test) {
863 return Ok(None);
864 }
865 let mut roots = BTreeSet::new();
866 self.extern_roots(from, name, Heads::Code { test }, &mut roots, steps)?;
867 let names_the_crate = bound.keys().all(|id| {
868 let item = &self.items[id.0];
869 match item.kind {
870 SymbolKind::ExternCrate => {
871 let count = self.modules_for(*id).count();
872 if count == 0 {
873 self.extern_names
874 .get(id)
875 .is_some_and(|real| real.as_ref() == name)
876 } else {
877 count == roots.len()
878 && self.modules_for(*id).all(|module| roots.contains(&module))
879 }
880 }
881 SymbolKind::Mod => self
882 .module_of
883 .get(id)
884 .is_some_and(|module| roots.contains(module)),
885 _ => false,
886 }
887 });
888 if names_the_crate {
889 return Ok(None);
890 }
891 let ids = bound.keys().copied().chain(
892 roots
893 .iter()
894 .filter_map(|root| self.root_items.get(root).copied()),
895 );
896 reserve_ids(bound.len() + roots.len(), steps)?;
897 Ok(Some(self.sorted(ids)))
898 }
899
900 fn unbound_use_head(
913 &self,
914 from: usize,
915 ns: Namespace,
916 first: &str,
917 heads: Heads,
918 steps: Steps<'_>,
919 ) -> Result<(), Fail> {
920 let wait = || {
921 steps
922 .reserve(vec_first::<Source>() + vec_slot::<Source>() + first.len())
923 .map_err(Fail::Storage)?;
924 Err(Fail::Missing(vec![Source {
925 module: from,
926 ns,
927 name: first.to_owned(),
928 }]))
929 };
930 if self.blocked(from, first, ns, heads.own()) {
934 return wait();
935 }
936 let pending = self.read_pending_at(from, first, slot(ns), None, heads.own(), steps)?;
944 let rest = || if pending { wait() } else { Ok(()) };
945 let Heads::Use { test, own } = heads else {
946 return rest();
947 };
948 if !self.crates_open && !self.globs_of(from).is_empty() {
949 return wait();
950 }
951 if !own.is_some_and(|position| matches!(self.uses[position].kind, UseKind::Named { .. }))
954 || ns != Namespace::Type
955 || self.edition(from) == 2015
956 || !self.in_use_prelude(from, first, test)
957 {
958 return rest();
959 }
960 let carried = self.read_globbed_outside(from, first, steps)?;
963 if carried.is_empty() {
964 return rest();
965 }
966 let mut roots = BTreeSet::new();
967 self.extern_roots(from, first, heads, &mut roots, steps)?;
968 let ids = carried
969 .iter()
970 .flat_map(|position| self.module_items(self.uses[*position].module))
971 .chain(
972 roots
973 .iter()
974 .filter_map(|root| self.root_items.get(root).copied()),
975 );
976 reserve_ids(carried.len() + roots.len(), steps)?;
977 Err(Fail::Ambiguous(self.sorted(ids)))
978 }
979
980 #[expect(
983 clippy::too_many_arguments,
984 reason = "the first segment is read as the walk reads it, noting what it read and counting its lookups"
985 )]
986 fn start(
987 &self,
988 from: usize,
989 segs: &[String],
990 leading_colon: bool,
991 last_ns: Namespace,
992 heads: Heads,
993 reads: &mut Option<&mut Vec<Source>>,
994 steps: Steps<'_>,
995 ) -> Result<(Walked, usize), Fail> {
996 let mut state = Walked::default();
997 let Some(first) = segs.first() else {
998 return Err(Fail::Missing(Vec::new()));
999 };
1000 if self.crate_relative(from, first, leading_colon, heads) {
1001 insert_module(&mut state.modules, self.modules[from].root, steps)?;
1004 return Ok((state, 0));
1005 }
1006 let mut next_index = 1;
1007 if leading_colon {
1008 if !self.extern_roots(from, first, heads, &mut state.modules, steps)? {
1009 return Err(Fail::Missing(Vec::new()));
1010 }
1011 } else {
1012 match first.as_str() {
1013 "crate" => {
1014 insert_module(&mut state.modules, self.modules[from].root, steps)?;
1015 }
1016 "self" => {
1017 insert_module(&mut state.modules, from, steps)?;
1018 }
1019 "super" => {
1020 let mut module = from;
1021 let mut at = 0;
1022 while segs.get(at).is_some_and(|s| s == "super") {
1023 module = self.modules[module].parent.ok_or(Fail::SuperAboveRoot)?;
1024 at += 1;
1025 }
1026 insert_module(&mut state.modules, module, steps)?;
1027 next_index = at;
1028 }
1029 _ => {
1030 let ns = if segs.len() == 1 {
1031 last_ns
1032 } else {
1033 Namespace::Type
1034 };
1035 note(reads, from, ns, first, steps)?;
1036 let lookup = self.read_lookup(from, ns, first, heads.own(), None, steps)?;
1037 if lookup.as_ref().is_none() {
1038 self.unbound_use_head(from, ns, first, heads, steps)?;
1039 }
1040 if let Some((bound, from_glob)) = lookup.as_ref() {
1041 if let (true, Namespace::Type, Heads::Use { test, .. }) =
1042 (from_glob, ns, heads)
1043 && let Some(ids) =
1044 self.read_glob_against_prelude(from, first, test, bound, steps)?
1045 {
1046 return Err(Fail::Ambiguous(ids));
1047 }
1048 if from_glob
1056 && segs.len() > 1
1057 && self.several_symbols(bound.keys().copied())
1058 {
1059 reserve_ids(bound.len(), steps)?;
1060 return Err(Fail::Ambiguous(self.sorted(bound.keys().copied())));
1061 }
1062 for (id, origin) in bound.iter() {
1063 steps.reserve(first.len()).map_err(Fail::Storage)?;
1064 merge(
1065 &mut state.items,
1066 *id,
1067 Hit {
1068 via_glob: from_glob || origin.via_glob,
1069 last: Some(Source {
1070 module: from,
1071 ns,
1072 name: first.clone(),
1073 }),
1074 },
1075 steps,
1076 )?;
1077 }
1078 } else if !self.extern_roots(from, first, heads, &mut state.modules, steps)? {
1079 steps
1080 .reserve(vec_first::<Source>() + vec_slot::<Source>() + first.len())
1081 .map_err(Fail::Storage)?;
1082 return Err(Fail::Missing(vec![Source {
1083 module: from,
1084 ns,
1085 name: first.clone(),
1086 }]));
1087 }
1088 }
1089 }
1090 }
1091 Ok((state, next_index))
1092 }
1093
1094 pub(crate) fn walk(
1097 &self,
1098 from: usize,
1099 segs: &[String],
1100 leading_colon: bool,
1101 last_ns: Namespace,
1102 heads: Heads,
1103 steps: Steps<'_>,
1104 ) -> Result<Walked, Fail> {
1105 self.walk_noting(from, segs, leading_colon, last_ns, heads, None, steps)
1106 }
1107
1108 #[expect(
1117 clippy::too_many_arguments,
1118 reason = "a walk reads one path from one module under one reading, noting what it read and counting its lookups"
1119 )]
1120 pub(crate) fn walk_noting(
1121 &self,
1122 from: usize,
1123 segs: &[String],
1124 leading_colon: bool,
1125 last_ns: Namespace,
1126 heads: Heads,
1127 reads: Option<&mut Vec<Source>>,
1128 steps: Steps<'_>,
1129 ) -> Result<Walked, Fail> {
1130 let viewer = matches!(heads, Heads::Use { .. }).then_some(from);
1133 self.walk_with_visibility(
1134 from,
1135 (segs, leading_colon, last_ns),
1136 (heads, viewer, reads),
1137 steps,
1138 )
1139 }
1140
1141 fn walk_with_visibility(
1142 &self,
1143 from: usize,
1144 (segs, leading_colon, last_ns): (&[String], bool, Namespace),
1145 (heads, viewer, mut reads): (Heads, Option<usize>, Option<&mut Vec<Source>>),
1146 steps: Steps<'_>,
1147 ) -> Result<Walked, Fail> {
1148 let (mut state, next_index) =
1149 self.start(from, segs, leading_colon, last_ns, heads, &mut reads, steps)?;
1150 Self::query_refusal(steps).map_err(Fail::Budget)?;
1151 self.one_crate(&state.modules, next_index, steps)?;
1152 for (offset, seg) in segs.iter().enumerate().skip(next_index) {
1153 let last = offset + 1 == segs.len();
1154 let ns = if last { last_ns } else { Namespace::Type };
1155 state = self.step(
1156 state,
1157 Step {
1158 offset,
1159 seg,
1160 ns,
1161 last,
1162 },
1163 heads,
1164 viewer,
1165 &mut reads,
1166 steps,
1167 )?;
1168 }
1169 Ok(state)
1170 }
1171
1172 fn step(
1174 &self,
1175 mut state: Walked,
1176 on: Step<'_>,
1177 heads: Heads,
1178 viewer: Option<usize>,
1179 reads: &mut Option<&mut Vec<Source>>,
1180 steps: Steps<'_>,
1181 ) -> Result<Walked, Fail> {
1182 let Step {
1183 offset,
1184 seg,
1185 ns,
1186 last,
1187 } = on;
1188 work::add(Work::SegmentReads, 1);
1189 if seg == "super" && state.items.is_empty() {
1190 let mut parents = BTreeSet::new();
1191 for module in &state.modules {
1192 insert_module(
1193 &mut parents,
1194 self.modules[*module].parent.ok_or(Fail::SuperAboveRoot)?,
1195 steps,
1196 )?;
1197 }
1198 return Ok(Walked {
1199 modules: parents,
1200 items: BTreeMap::new(),
1201 });
1202 }
1203 let mut containers = std::mem::take(&mut state.modules);
1204 let carried = state.items.values().any(|hit| hit.via_glob);
1205 for id in state.items.keys() {
1206 for module in self.modules_for(*id) {
1207 insert_module(&mut containers, module, steps)?;
1208 }
1209 }
1210 self.one_crate(&containers, offset, steps)?;
1211 let mut found: BTreeMap<ItemId, Hit> = BTreeMap::new();
1212 let mut missing = Vec::new();
1213 for module in containers {
1214 note(reads, module, ns, seg, steps)?;
1215 let lookup = self.read_lookup(module, ns, seg, heads.own(), viewer, steps)?;
1216 if let Some((bound, from_glob)) = lookup.as_ref() {
1217 if from_glob && !last && self.several_symbols(bound.keys().copied()) {
1225 reserve_ids(bound.len(), steps)?;
1226 return Err(Fail::Ambiguous(self.sorted(bound.keys().copied())));
1227 }
1228 for (id, origin) in bound.iter() {
1229 steps.reserve(seg.len()).map_err(Fail::Storage)?;
1230 merge(
1231 &mut found,
1232 *id,
1233 Hit {
1234 via_glob: carried || from_glob || origin.via_glob,
1235 last: Some(Source {
1236 module,
1237 ns,
1238 name: seg.to_owned(),
1239 }),
1240 },
1241 steps,
1242 )?;
1243 }
1244 } else {
1245 push_source(&mut missing, module, ns, seg, steps)?;
1246 }
1247 }
1248 for (id, hit) in &state.items {
1249 if let Some(members) = self.assoc.get(id).and_then(|m| m.get(seg)) {
1250 for member in members {
1251 if self.items[member.0].in_namespace(ns) {
1252 merge(
1253 &mut found,
1254 *member,
1255 Hit {
1256 via_glob: hit.via_glob,
1257 last: None,
1258 },
1259 steps,
1260 )?;
1261 }
1262 }
1263 }
1264 }
1265 Self::query_refusal(steps).map_err(Fail::Budget)?;
1266 if found.is_empty() {
1267 return Err(Fail::Missing(missing));
1268 }
1269 Ok(Walked {
1270 modules: BTreeSet::new(),
1271 items: found,
1272 })
1273 }
1274
1275 fn unresolved_uses<'a>(
1277 &'a self,
1278 module: usize,
1279 name: &str,
1280 namespace: Namespace,
1281 ) -> impl Iterator<Item = usize> + use<'a> {
1282 self.imports_of(module, name)
1283 .iter()
1284 .copied()
1285 .filter(move |&position| {
1286 !self.use_resolved[position]
1287 && self.uses[position]
1288 .kind
1289 .terminal_namespaces()
1290 .contains(&namespace)
1291 })
1292 }
1293
1294 fn import_walks(&self, position: usize, steps: Steps<'_>) -> Result<ImportWalks, ResolveError> {
1301 let decl = &self.uses[position];
1302 let UseKind::Named { segs, .. } = &decl.kind else {
1303 return Ok(ImportWalks::default());
1304 };
1305 let mut reads = Vec::new();
1306 let mut ambiguous = BTreeSet::new();
1307 for &ns in decl.kind.terminal_namespaces() {
1308 match self.walk_noting(
1309 decl.module,
1310 segs,
1311 decl.leading_colon,
1312 ns,
1313 Heads::Use {
1314 test: decl.test,
1315 own: Some(position),
1316 },
1317 Some(&mut reads),
1318 steps,
1319 ) {
1320 Err(Fail::Ambiguous(ids)) => ambiguous.extend(ids),
1321 Err(Fail::Storage(error)) => return Err(ResolveError::storage(error)),
1322 Err(Fail::Budget(refused)) => return Err(self.refused(refused)),
1323 Ok(_)
1324 | Err(Fail::Missing(_) | Fail::SuperAboveRoot | Fail::SeveralCrates { .. }) => {}
1325 }
1326 }
1327 let mut places = BTreeMap::new();
1328 for source in &reads {
1329 if !self.binds_name(position, source.module, source.ns, &source.name) {
1331 let sees_type = places
1332 .entry((source.module, source.name.as_str()))
1333 .or_insert(false);
1334 *sees_type |= source.ns == Namespace::Type;
1335 }
1336 }
1337 let mut blockers = BTreeSet::new();
1338 for ((module, name), sees_type) in places {
1339 let namespace = if sees_type {
1342 Namespace::Type
1343 } else {
1344 Namespace::Value
1345 };
1346 blockers.extend(self.unresolved_uses(module, name, namespace));
1347 }
1348 blockers.remove(&position);
1350 Ok(ImportWalks {
1351 blockers: blockers.into_iter().collect(),
1352 ambiguous: ambiguous.into_iter().collect(),
1353 reads,
1354 })
1355 }
1356
1357 pub(crate) fn bound_by_undecided(&self, module: usize, ns: Namespace, name: &str) -> bool {
1365 let at = slot(ns);
1366 let bound = self.scopes[module]
1367 .get(name)
1368 .is_some_and(|entry| !entry.defs[at].is_empty());
1369 self.imports_of(module, name).iter().any(|position| {
1370 !self.use_settled[*position]
1371 && (bound && self.use_bound[*position][at] || self.left_to_globs(*position, at))
1372 })
1373 }
1374
1375 fn unbound(
1390 &self,
1391 missing: &[Source],
1392 reads: &[Source],
1393 text: &str,
1394 steps: Steps<'_>,
1395 ) -> ResolveError {
1396 if let Err(error) = self.record_failed_routes(reads.iter().chain(missing), steps) {
1397 return ResolveError::storage(error);
1398 }
1399 let mut unsettled = None;
1400 for source in missing {
1401 match self.unsettled_at(source, steps) {
1402 Ok(Some(reason)) => {
1403 unsettled = Some(reason);
1404 break;
1405 }
1406 Ok(None) => (),
1407 Err(error) => return ResolveError::storage(error),
1408 }
1409 }
1410 if let Err(refused) = Self::query_refusal(steps) {
1411 return self.refused(refused);
1412 }
1413 match unsettled {
1414 Some(Unsettled::Cycle) => return ResolveError::Cyclic(text.to_owned()),
1415 Some(Unsettled::LateImport(position)) => {
1416 let decl = &self.uses[position];
1417 return ResolveError::IndeterminateImport {
1418 path: text.to_owned(),
1419 file: decl.file.clone(),
1420 line: decl.line,
1421 };
1422 }
1423 None => {}
1424 }
1425 let stack_memory = steps.query_meter().map(Transient::new);
1428 let Some(source) = missing.first().or_else(|| reads.first()) else {
1429 return ResolveError::NotFound(text.to_owned());
1430 };
1431 let (stack_file, stack_line) = self.module_site(source.module);
1432 let stack_steps =
1433 steps.with_query_storage(stack_memory.as_ref(), (&stack_file, stack_line));
1434 let mut seen: BTreeSet<usize> = BTreeSet::new();
1435 let mut work = WorkList::<_, 8>::new();
1436 for source in missing {
1437 for position in self.unresolved_uses(source.module, &source.name, source.ns) {
1438 if let Err(error) = push_work(&mut work, position, stack_steps) {
1439 return ResolveError::storage(error);
1440 }
1441 }
1442 }
1443 let mut ambiguous: BTreeSet<ItemId> = BTreeSet::new();
1444 let mut through: Vec<Source> = reads.to_vec();
1445 while let Some(position) = work.pop() {
1446 if !seen.insert(position) {
1447 continue;
1448 }
1449 let ImportWalks {
1450 blockers: following,
1451 ambiguous: items,
1452 reads,
1453 } = match self.import_walks(position, steps) {
1454 Ok(walks) => walks,
1455 Err(error) => return error,
1456 };
1457 if let Err(refused) = Self::query_refusal(steps) {
1458 return self.refused(refused);
1459 }
1460 ambiguous.extend(items);
1461 if let Err(error) = self.record_failed_routes(reads.iter(), steps) {
1462 return ResolveError::storage(error);
1463 }
1464 for position in following {
1465 if let Err(error) = push_work(&mut work, position, stack_steps) {
1466 return ResolveError::storage(error);
1467 }
1468 }
1469 through.extend(reads);
1470 }
1471 if !ambiguous.is_empty() {
1472 return ResolveError::Ambiguous(self.sorted(ambiguous));
1473 }
1474 match self.unresolved_glob_read(&through, steps) {
1475 Ok(Some(glob)) => self.glob_error(glob, text),
1476 Ok(None) => ResolveError::NotFound(text.to_owned()),
1477 Err(error) => ResolveError::storage(error),
1478 }
1479 }
1480
1481 pub(crate) fn glob_error(&self, position: usize, text: &str) -> ResolveError {
1484 let decl = &self.uses[position];
1485 let (UseKind::Glob { segs } | UseKind::Named { segs, .. }) = &decl.kind;
1486 ResolveError::UnresolvedGlob {
1487 path: text.to_owned(),
1488 glob: format!(
1489 "{}{}",
1490 if decl.leading_colon { "::" } else { "" },
1491 segs.join("::")
1492 ),
1493 module: self.modules[decl.module].path.to_string(),
1494 }
1495 }
1496
1497 fn binds_explicitly(&self, module: usize, ns: Namespace, name: &str) -> bool {
1501 self.scopes[module]
1502 .get(name)
1503 .is_some_and(|entry| !entry.defs[slot(ns)].is_empty())
1504 || self.blocked(module, name, ns, None)
1505 }
1506
1507 fn glob_path(&self, position: usize, steps: Steps<'_>) -> Result<GlobPath, LoadError> {
1510 let decl = &self.uses[position];
1511 let UseKind::Glob { segs } = &decl.kind else {
1512 return Ok(GlobPath::Nothing);
1513 };
1514 let sources = match self.glob_targets(position, steps) {
1515 Ok(targets) => return Ok(GlobPath::Resolves(targets)),
1516 Err(Fail::Missing(sources)) => sources,
1517 Err(Fail::SuperAboveRoot | Fail::SeveralCrates { .. } | Fail::Ambiguous(_)) => {
1518 return Ok(GlobPath::Nothing);
1519 }
1520 Err(Fail::Budget(_)) => unreachable!("{LOAD_WALK}"),
1521 Err(Fail::Storage(error)) => return Err(error),
1522 };
1523 if sources.is_empty() {
1526 return Ok(GlobPath::Unknown);
1527 }
1528 let head = self.walk(
1529 decl.module,
1530 &segs[..1],
1531 decl.leading_colon,
1532 Namespace::Type,
1533 Heads::Use {
1534 test: decl.test,
1535 own: Some(position),
1536 },
1537 steps,
1538 );
1539 if let Err(Fail::Storage(error)) = head {
1540 return Err(error);
1541 }
1542 if head.is_err() {
1545 Ok(GlobPath::Unknown)
1546 } else {
1547 Ok(GlobPath::Misses(sources))
1548 }
1549 }
1550
1551 pub(crate) fn binding_failure(
1562 &self,
1563 module: usize,
1564 ns: Namespace,
1565 name: &str,
1566 bound: &[ItemId],
1567 text: &str,
1568 steps: Steps<'_>,
1569 ) -> Option<ResolveError> {
1570 if let Err(error) = self.binding_determinacy(module, ns, name, bound, text, steps) {
1571 return Some(error);
1572 }
1573 if self.bound_by_undecided(module, ns, name) {
1574 return Some(ResolveError::Cyclic(text.to_owned()));
1575 }
1576 let groups: BTreeSet<(TargetId, &str, SymbolKind)> = bound
1577 .iter()
1578 .map(|id| {
1579 let item = &self.items[id.0];
1580 (item.target, item.path.as_str(), item.kind)
1581 })
1582 .collect();
1583 if groups.len() > 1 {
1584 return Some(ResolveError::Ambiguous(self.sorted(bound.iter().copied())));
1585 }
1586 let source = Source {
1587 module,
1588 ns,
1589 name: name.to_owned(),
1590 };
1591 match self.unresolved_glob_read(std::slice::from_ref(&source), steps) {
1592 Ok(glob) => glob.map(|glob| self.glob_error(glob, text)),
1593 Err(error) => Some(ResolveError::storage(error)),
1594 }
1595 }
1596
1597 pub(crate) fn query_refusal(steps: Steps<'_>) -> Result<(), Refused> {
1602 if let Some(meter) = steps.query_meter()
1603 && let Some(module) = meter.query_passed()
1604 {
1605 return Err(Refused {
1606 limit: meter.work_limit(),
1607 module,
1608 });
1609 }
1610 Ok(())
1611 }
1612
1613 fn query_checked(
1616 &self,
1617 steps: Steps<'_>,
1618 answer: Result<Resolution, ResolveError>,
1619 ) -> Result<Resolution, ResolveError> {
1620 match Self::query_refusal(steps) {
1621 Err(refused) => Err(self.refused(refused)),
1622 Ok(()) => answer,
1623 }
1624 }
1625
1626 pub(crate) fn refused(&self, refused: Refused) -> ResolveError {
1628 let (file, line) = self.module_site(refused.module);
1629 ResolveError::Budget {
1630 budget: Budget::Work,
1631 limit: refused.limit,
1632 file,
1633 line,
1634 }
1635 }
1636
1637 pub(crate) fn refused_load(&self, refused: Refused) -> LoadError {
1640 let (file, line) = self.module_site(refused.module);
1641 over_budget(Budget::Work, refused.limit, &file, line)
1642 }
1643
1644 pub(crate) fn module_site(&self, module: usize) -> (RelPath, Option<usize>) {
1647 if self.modules[module].parent.is_some()
1648 && let Some(id) = self.module_items(module).first()
1649 {
1650 let item = &self.items[id.0];
1651 return (item.file.clone(), Some(item.name_line));
1652 }
1653 let target = &self.targets[self.modules[module].target.index()];
1654 (target.root.clone(), None)
1655 }
1656
1657 pub(crate) fn glob_broken(&self, position: usize, meter: &Meter) -> Result<bool, LoadError> {
1661 let Some(facts) = self.glob_facts() else {
1662 return Ok(false);
1663 };
1664 let decl = &self.uses[position];
1665 meter.work(
1666 glob_facts::table_units(facts.broken.len()),
1667 &decl.file,
1668 Some(decl.line),
1669 )?;
1670 Ok(facts.broken.get(&position).is_some())
1671 }
1672
1673 fn glob_facts(&self) -> Option<&GlobFacts> {
1674 let facts = self.glob_facts.get();
1675 assert!(
1676 facts.is_some() || self.glob_imports.is_empty(),
1677 "glob facts are built before a completed index is queried"
1678 );
1679 facts
1680 }
1681
1682 pub(crate) fn origin_of(
1683 &self,
1684 source: &Source,
1685 id: ItemId,
1686 steps: Steps<'_>,
1687 ) -> Option<crate::settle::Origin> {
1688 let ns = slot(source.ns);
1689 let defs = self.scopes[source.module]
1690 .get(&source.name)
1691 .and_then(|entry| entry.defs[ns].get(id));
1692 match defs {
1693 Some(origin) => Some(origin.clone()),
1694 None => self
1695 .globbed(source.module, &source.name, ns, steps)
1696 .get(id)
1697 .cloned(),
1698 }
1699 }
1700
1701 fn chain_for(&self, requested: &str, hit: &Hit, id: ItemId, steps: Steps<'_>) -> Vec<String> {
1702 let mut chain = Vec::new();
1703 let Some(mut at) = hit.last.clone() else {
1704 chain.push(requested.to_owned());
1705 return chain;
1706 };
1707 let mut visited: BTreeSet<Source> = BTreeSet::new();
1710 while visited.insert(at.clone()) {
1711 chain.push(format!("{}::{}", self.modules[at.module].path, at.name));
1712 let next = self
1713 .origin_of(&at, id, steps)
1714 .and_then(|origin| origin.link)
1715 .and_then(|link| link.source);
1716 match next {
1717 Some(source) => at = source,
1718 None => break,
1719 }
1720 }
1721 chain
1722 }
1723
1724 fn package_of(&self, module: usize) -> PackageId {
1726 self.targets[self.modules[module].target.index()].package_id
1727 }
1728
1729 fn walk_from_root(
1733 &self,
1734 root: usize,
1735 rest: &[String],
1736 ns: Namespace,
1737 text: &str,
1738 walks: &mut Walks,
1739 steps: Steps<'_>,
1740 ) -> Result<(), ResolveError> {
1741 let start = walks.reads.len();
1742 let walk = self.walk_noting(
1743 root,
1744 rest,
1745 false,
1746 ns,
1747 Heads::Local,
1748 Some(&mut walks.reads),
1749 steps,
1750 );
1751 if walk.is_ok()
1752 && walks.reads[start..]
1753 .iter()
1754 .any(|source| self.bound_by_undecided(source.module, source.ns, &source.name))
1755 {
1756 return Err(ResolveError::Cyclic(text.to_owned()));
1757 }
1758 match walk {
1759 Ok(walked) => {
1760 self.path_determinacy(root, rest, false, ns, Heads::Local, text, steps)?;
1761 for (id, hit) in walked.items {
1762 merge(&mut walks.found, id, hit, steps).map_err(ResolveError::storage)?;
1763 }
1764 }
1765 Err(Fail::Missing(sources)) => walks.missing.extend(sources),
1766 Err(Fail::SeveralCrates { roots: ids, .. } | Fail::Ambiguous(ids)) => {
1767 return Err(ResolveError::Ambiguous(ids));
1768 }
1769 Err(Fail::SuperAboveRoot) => {
1773 return Err(ResolveError::Invalid(text.to_owned()));
1774 }
1775 Err(Fail::Budget(refused)) => return Err(self.refused(refused)),
1776 Err(Fail::Storage(error)) => return Err(ResolveError::storage(error)),
1777 }
1778 Ok(())
1779 }
1780
1781 fn resolve_in(
1784 &self,
1785 segs: &[String],
1786 ns: Namespace,
1787 text: &str,
1788 package: Option<PackageId>,
1789 steps: Steps<'_>,
1790 ) -> Result<Resolution, ResolveError> {
1791 let mut walks = Walks::default();
1792 let mut prefix = String::with_capacity(text.len());
1795 for (taken, seg) in (1..=segs.len()).zip(segs) {
1796 work::add(Work::SegmentReads, 1);
1797 if taken > 1 {
1798 prefix.push_str("::");
1799 }
1800 prefix.push_str(seg);
1801 let Some(roots) = self.crate_roots.get(&prefix) else {
1802 continue;
1803 };
1804 let roots: Vec<usize> = roots
1805 .iter()
1806 .copied()
1807 .filter(|root| package.is_none_or(|id| self.package_of(*root) == id))
1808 .collect();
1809 if roots.len() > 1 {
1813 return Err(ResolveError::Ambiguous(
1814 self.sorted(
1815 roots
1816 .iter()
1817 .filter_map(|root| self.root_items.get(root).copied()),
1818 ),
1819 ));
1820 }
1821 for root in roots {
1822 if taken < segs.len() {
1823 self.walk_from_root(root, &segs[taken..], ns, text, &mut walks, steps)?;
1824 } else if ns == Namespace::Type
1825 && let Some(item) = self.root_items.get(&root)
1826 {
1827 merge(
1830 &mut walks.found,
1831 *item,
1832 Hit {
1833 via_glob: false,
1834 last: None,
1835 },
1836 steps,
1837 )
1838 .map_err(ResolveError::storage)?;
1839 }
1840 }
1841 }
1842 let Walks {
1843 mut found,
1844 missing,
1845 reads,
1846 } = walks;
1847 let from_keys = found.is_empty();
1848 if let (true, Some(ids)) = (from_keys, self.foreign.get(text)) {
1849 for id in ids {
1850 let item = &self.items[id.0];
1851 if item.in_namespace(ns)
1852 && package.is_none_or(|id| self.targets[item.target.index()].package_id == id)
1853 {
1854 found.insert(
1855 *id,
1856 Hit {
1857 via_glob: false,
1858 last: None,
1859 },
1860 );
1861 }
1862 }
1863 }
1864 self.conclude(&found, &missing, &reads, text, ns, from_keys, steps)
1865 }
1866
1867 #[expect(
1872 clippy::too_many_arguments,
1873 reason = "the answer is concluded from what one walk found, read and missed, counting its lookups"
1874 )]
1875 fn conclude(
1876 &self,
1877 found: &BTreeMap<ItemId, Hit>,
1878 missing: &[Source],
1879 reads: &[Source],
1880 text: &str,
1881 ns: Namespace,
1882 from_keys: bool,
1883 steps: Steps<'_>,
1884 ) -> Result<Resolution, ResolveError> {
1885 if found.is_empty() {
1886 return Err(self.unbound(missing, reads, text, steps));
1887 }
1888 let mut groups: BTreeSet<(Option<TargetId>, &str, SymbolKind)> = BTreeSet::new();
1893 for id in found.keys() {
1894 let item = &self.items[id.0];
1895 let target = if from_keys {
1896 item.trait_definition_target
1897 } else {
1898 Some(item.target)
1899 };
1900 groups.insert((target, item.path.as_str(), item.kind));
1901 }
1902 if groups.len() > 1 {
1903 return Err(ResolveError::Ambiguous(self.sorted(found.keys().copied())));
1904 }
1905 if let Some(glob) = self
1908 .unresolved_glob_read(reads, steps)
1909 .map_err(ResolveError::storage)?
1910 {
1911 return Err(self.glob_error(glob, text));
1912 }
1913 let sites = self.sorted(found.keys().copied());
1914 let first = sites[0];
1915 let hit = &found[&first];
1916 Ok(Resolution {
1917 path: self.items[first.0].path.to_string(),
1918 namespace: ns,
1919 via_glob: hit.via_glob,
1920 chain: self.chain_for(text, hit, first, steps),
1921 type_aliases: Vec::new(),
1922 sites,
1923 })
1924 }
1925
1926 fn several_symbols(&self, ids: impl Iterator<Item = ItemId>) -> bool {
1930 let groups: BTreeSet<(TargetId, &str, SymbolKind)> = ids
1931 .map(|id| {
1932 let item = &self.items[id.0];
1933 (item.target, item.path.as_str(), item.kind)
1934 })
1935 .collect();
1936 groups.len() > 1
1937 }
1938
1939 fn module_named(
1954 &self,
1955 path: &str,
1956 package: Option<PackageId>,
1957 ) -> Result<Option<usize>, ResolveError> {
1958 let key = SharedStr::from(path);
1959 let mut found = Vec::new();
1960 let mut prefix = String::with_capacity(path.len());
1961 for (taken, segment) in path.split("::").enumerate() {
1962 work::add(Work::SegmentReads, 1);
1963 if taken > 0 {
1964 prefix.push_str("::");
1965 }
1966 prefix.push_str(segment);
1967 let Some(roots) = self.crate_roots.get(&prefix) else {
1968 continue;
1969 };
1970 let roots = roots
1971 .iter()
1972 .copied()
1973 .filter(|root| package.is_none_or(|id| self.package_of(*root) == id));
1974 if roots.clone().count() > 1 {
1975 return Err(ResolveError::Ambiguous(self.sorted(
1976 roots.filter_map(|root| self.root_items.get(&root).copied()),
1977 )));
1978 }
1979 found.extend(
1980 roots.filter_map(|root| self.module_by_path.get(&(root, key.clone())).copied()),
1981 );
1982 }
1983 match found.as_slice() {
1984 [] => Ok(None),
1985 [one] => Ok(Some(*one)),
1986 several => Err(ResolveError::Ambiguous(
1987 self.sorted(several.iter().flat_map(|module| self.module_items(*module))),
1988 )),
1989 }
1990 }
1991
1992 pub(crate) fn resolve_from(
1995 &self,
1996 module: &str,
1997 path: &str,
1998 ns: Option<Namespace>,
1999 package: Option<PackageId>,
2000 meter: &Meter,
2001 ) -> Result<Resolution, ResolveError> {
2002 let steps = Steps::Query(meter);
2003 let answer = self.resolve_from_counted(module, path, ns, package, steps);
2004 self.query_checked(steps, answer)
2005 }
2006
2007 fn resolve_from_counted(
2009 &self,
2010 module: &str,
2011 path: &str,
2012 ns: Option<Namespace>,
2013 package: Option<PackageId>,
2014 steps: Steps<'_>,
2015 ) -> Result<Resolution, ResolveError> {
2016 let from = self
2017 .module_named(module, package)?
2018 .ok_or_else(|| ResolveError::UnknownModule(module.to_owned()))?;
2019 self.resolve_at(
2020 from,
2021 path,
2022 ns,
2023 Heads::Use {
2024 test: false,
2025 own: None,
2026 },
2027 steps,
2028 )
2029 }
2030
2031 pub(crate) fn unconditional_method(
2032 &self,
2033 id: ItemId,
2034 steps: Steps<'_>,
2035 ) -> Result<bool, ResolveError> {
2036 let item = &self.items[id.index()];
2037 if item
2038 .detail
2039 .as_ref()
2040 .is_some_and(|detail| detail.method_requires_inference)
2041 {
2042 return Ok(false);
2043 }
2044 let Some(block) = self
2045 .impl_blocks
2046 .iter()
2047 .find(|block| block.members.contains(&id))
2048 else {
2049 return Ok(false);
2050 };
2051 let Some(arity) = block.unconditional_self else {
2052 return Ok(false);
2053 };
2054 let base = block
2055 .self_type
2056 .split('<')
2057 .next()
2058 .unwrap_or(&block.self_type);
2059 let resolution = match self.resolve_at(
2060 block.module_index,
2061 base,
2062 Some(Namespace::Type),
2063 Heads::Code {
2064 test: item.test != crate::TestRole::None,
2065 },
2066 steps,
2067 ) {
2068 Ok(resolution) => resolution,
2069 Err(error @ (ResolveError::Budget { .. } | ResolveError::Storage { .. })) => {
2070 return Err(error);
2071 }
2072 Err(_) => return Ok(false),
2073 };
2074 Ok(!resolution.sites.is_empty()
2075 && resolution.sites.iter().all(|site| {
2076 block.self_items.contains(site)
2077 && self.items[site.index()]
2078 .detail
2079 .as_ref()
2080 .and_then(|detail| detail.nominal_const_arity)
2081 == Some(arity)
2082 && matches!(
2083 self.items[site.index()].kind,
2084 SymbolKind::Struct | SymbolKind::Enum | SymbolKind::Union
2085 )
2086 }))
2087 }
2088
2089 fn prefer_inherent(
2090 &self,
2091 found: &mut BTreeMap<ItemId, Hit>,
2092 steps: Steps<'_>,
2093 ) -> Result<(), ResolveError> {
2094 let Some(&first) = found.keys().next() else {
2095 return Ok(());
2096 };
2097 let item = &self.items[first.index()];
2098 let storage = steps.query_meter().map(Transient::new);
2099 let steps = steps.with_query_storage(storage.as_ref(), (&item.file, Some(item.name_line)));
2100 let mut inherent = OrderedTable::default();
2101 let mut live = 0;
2102 for id in found.keys() {
2103 steps.storage_work(1).map_err(ResolveError::storage)?;
2104 let item = &self.items[id.index()];
2105 if item.kind != SymbolKind::InherentMethod || !self.unconditional_method(*id, steps)? {
2106 continue;
2107 }
2108 let mut admission = NativeAdmission::resume(steps, live);
2109 let result = {
2110 let mut memory = Memory::resume(&mut admission, live);
2111 let result = inherent.insert((item.target, item.path.as_str()), (), &mut memory);
2112 live = memory.admitted_bytes();
2113 result
2114 };
2115 result.map_err(|error| ResolveError::storage(admission.graph_error(error.into())))?;
2116 }
2117 if !inherent.is_empty() {
2118 steps
2119 .storage_work(found.len())
2120 .map_err(ResolveError::storage)?;
2121 found.retain(|id, _| {
2122 let item = &self.items[id.index()];
2123 item.kind != SymbolKind::TraitImplMethod
2124 || inherent.get(&(item.target, item.path.as_str())).is_none()
2125 });
2126 }
2127 Ok(())
2128 }
2129
2130 pub(crate) fn resolve_at(
2132 &self,
2133 from: usize,
2134 path: &str,
2135 ns: Option<Namespace>,
2136 heads: Heads,
2137 steps: Steps<'_>,
2138 ) -> Result<Resolution, ResolveError> {
2139 let answer = self.resolve_at_counted(from, path, ns, heads, steps, None);
2140 self.query_checked(steps, answer)
2141 }
2142
2143 pub(crate) fn resolve_alias_at(
2145 &self,
2146 from: usize,
2147 path: &str,
2148 heads: Heads,
2149 steps: Steps<'_>,
2150 ) -> Result<Option<Resolution>, ResolveError> {
2151 let mut outside = false;
2152 let answer = self.resolve_at_counted(
2153 from,
2154 path,
2155 Some(Namespace::Type),
2156 heads,
2157 steps,
2158 Some(&mut outside),
2159 );
2160 match self.query_checked(steps, answer) {
2161 Err(ResolveError::NotFound(_)) if outside => Ok(None),
2162 answer => answer.map(Some),
2163 }
2164 }
2165
2166 fn resolve_at_counted(
2167 &self,
2168 from: usize,
2169 path: &str,
2170 ns: Option<Namespace>,
2171 heads: Heads,
2172 steps: Steps<'_>,
2173 mut outside: Option<&mut bool>,
2174 ) -> Result<Resolution, ResolveError> {
2175 let (leading_colon, written) = path.strip_prefix("::").map_or((false, path), |p| (true, p));
2176 let segs: Vec<String> = written
2177 .split("::")
2178 .map(|s| strip_raw(s).to_owned())
2179 .collect();
2180 if !written.split("::").all(valid_code_segment) {
2181 return Err(ResolveError::Invalid(path.to_owned()));
2182 }
2183 let text = segs.join("::");
2184 let spaces: Vec<Namespace> = ns.map_or_else(|| Namespace::ALL.to_vec(), |one| vec![one]);
2185 for space in spaces {
2186 let mut reads = Vec::new();
2187 let walk = self.walk_noting(
2188 from,
2189 &segs,
2190 leading_colon,
2191 space,
2192 heads,
2193 Some(&mut reads),
2194 steps,
2195 );
2196 if walk.is_ok()
2197 && reads
2198 .iter()
2199 .any(|source| self.bound_by_undecided(source.module, source.ns, &source.name))
2200 {
2201 return Err(ResolveError::Cyclic(text));
2202 }
2203 let outcome = match walk {
2204 Ok(mut walked) => {
2205 self.path_determinacy(from, &segs, leading_colon, space, heads, &text, steps)?;
2206 if space == Namespace::Value {
2207 self.prefer_inherent(&mut walked.items, steps)?;
2208 }
2209 if space == Namespace::Type && walked.items.is_empty() {
2210 for module in &walked.modules {
2211 for definition in self.module_items(*module) {
2212 merge(
2213 &mut walked.items,
2214 definition,
2215 Hit {
2216 via_glob: false,
2217 last: None,
2218 },
2219 steps,
2220 )
2221 .map_err(ResolveError::storage)?;
2222 }
2223 }
2224 }
2225 self.conclude(&walked.items, &[], &reads, &text, space, false, steps)
2226 }
2227 Err(Fail::Missing(missing)) => {
2228 let error = self.unbound(&missing, &reads, &text, steps);
2229 if matches!(error, ResolveError::NotFound(_))
2230 && let Some(outside) = outside.as_deref_mut()
2231 && let [source] = missing.as_slice()
2232 && !self.imports_of(source.module, &source.name).is_empty()
2233 && let Some(visible) = self.unconditional_missing_source(
2234 from,
2235 (&segs, leading_colon, space),
2236 heads,
2237 steps,
2238 )?
2239 && visible == *source
2240 {
2241 *outside = self.missing_external_import(visible, from, heads, steps)?;
2242 }
2243 Err(error)
2244 }
2245 Err(Fail::SeveralCrates { roots: ids, .. } | Fail::Ambiguous(ids)) => {
2246 Err(ResolveError::Ambiguous(ids))
2247 }
2248 Err(Fail::SuperAboveRoot) => Err(ResolveError::Invalid(path.to_owned())),
2249 Err(Fail::Budget(refused)) => Err(self.refused(refused)),
2250 Err(Fail::Storage(error)) => Err(ResolveError::storage(error)),
2251 };
2252 match outcome {
2253 Err(ResolveError::NotFound(_)) => {}
2254 other => return other,
2255 }
2256 }
2257 Err(ResolveError::NotFound(text))
2258 }
2259
2260 fn unconditional_missing_source(
2262 &self,
2263 from: usize,
2264 path: (&[String], bool, Namespace),
2265 heads: Heads,
2266 steps: Steps<'_>,
2267 ) -> Result<Option<Source>, ResolveError> {
2268 let mut reads = Vec::new();
2269 match self.walk_with_visibility(from, path, (heads, Some(from), Some(&mut reads)), steps) {
2270 Err(Fail::Missing(missing)) => {
2271 let Ok([source]) = <[Source; 1]>::try_from(missing) else {
2272 return Ok(None);
2273 };
2274 Ok(self
2275 .unconditional_type_reads(from, &reads, heads, steps)?
2276 .then_some(source))
2277 }
2278 Err(Fail::Storage(error)) => Err(ResolveError::storage(error)),
2279 Err(Fail::Budget(refused)) => Err(self.refused(refused)),
2280 Ok(_) | Err(Fail::SuperAboveRoot | Fail::SeveralCrates { .. } | Fail::Ambiguous(_)) => {
2281 Ok(None)
2282 }
2283 }
2284 }
2285
2286 fn missing_external_import(
2289 &self,
2290 mut source: Source,
2291 mut from: usize,
2292 mut heads: Heads,
2293 steps: Steps<'_>,
2294 ) -> Result<bool, ResolveError> {
2295 for _ in 0..self.uses.len() {
2298 let Some(position) = self.unique_missing_import(&source, from, heads, steps)? else {
2299 return Ok(false);
2300 };
2301 if self
2302 .read_outside_crate(position, steps)
2303 .map_err(|error| ResolveError::storage(storage_failure(error)))?
2304 .is_some()
2305 {
2306 return Ok(true);
2307 }
2308 let decl = &self.uses[position];
2309 let UseKind::Named { segs, .. } = &decl.kind else {
2310 return Ok(false);
2311 };
2312 from = decl.module;
2313 heads = decl.heads(position);
2314 let Some(next) = self.unconditional_missing_source(
2315 from,
2316 (segs, decl.leading_colon, source.ns),
2317 heads,
2318 steps,
2319 )?
2320 else {
2321 return Ok(false);
2322 };
2323 source = next;
2324 }
2325 Ok(false)
2326 }
2327
2328 fn unique_missing_import(
2329 &self,
2330 source: &Source,
2331 from: usize,
2332 heads: Heads,
2333 steps: Steps<'_>,
2334 ) -> Result<Option<usize>, ResolveError> {
2335 let mut selected = None;
2336 let test = matches!(
2337 heads,
2338 Heads::Code { test: true } | Heads::Use { test: true, .. }
2339 );
2340 steps
2341 .storage_work(self.imports_of(source.module, &source.name).len() + 1)
2342 .map_err(ResolveError::storage)?;
2343 for position in self.unresolved_uses(source.module, &source.name, source.ns) {
2344 let decl = &self.uses[position];
2345 if heads.own() != Some(position)
2346 && (test || !decl.test)
2347 && self
2348 .read_visibility(&decl.vis, source.module, from, steps)
2349 .map_err(|error| ResolveError::storage(storage_failure(error)))?
2350 && selected.replace(position).is_some()
2351 {
2352 return Ok(None);
2353 }
2354 }
2355 Ok(selected)
2356 }
2357
2358 pub(crate) fn reach_run(
2372 &self,
2373 from: usize,
2374 segs: &[String],
2375 leading_colon: bool,
2376 test: bool,
2377 steps: Steps<'_>,
2378 ) -> Result<BTreeSet<ItemId>, LoadError> {
2379 let heads = Heads::Code { test };
2380 let mut out = BTreeSet::new();
2381 match segs.len() {
2382 0 => {}
2383 1 => self.reach_single(from, segs, leading_colon, heads, &mut out, steps)?,
2384 _ => self.reach_chain(from, segs, leading_colon, heads, &mut out, steps)?,
2385 }
2386 Self::query_refusal(steps).map_err(|refused| self.refused_load(refused))?;
2387 Ok(out)
2388 }
2389
2390 pub(crate) fn reach_value(
2392 &self,
2393 from: usize,
2394 name: &str,
2395 test: bool,
2396 steps: Steps<'_>,
2397 ) -> Result<BTreeSet<ItemId>, LoadError> {
2398 steps.reserve(name.len())?;
2399 let segs = [name.to_owned()];
2400 let mut reads = Vec::new();
2401 let mut out = BTreeSet::new();
2402 let outcome = self.walk_noting(
2403 from,
2404 &segs,
2405 false,
2406 Namespace::Value,
2407 Heads::Code { test },
2408 Some(&mut reads),
2409 steps,
2410 );
2411 if let Some(walked) = self.reach_outcome(outcome, steps)? {
2412 self.take(&walked, false, &reads, &mut out, steps)?;
2413 }
2414 Self::query_refusal(steps).map_err(|refused| self.refused_load(refused))?;
2415 Ok(out)
2416 }
2417
2418 pub(crate) fn reach_outcome<T>(
2420 &self,
2421 outcome: Result<T, Fail>,
2422 steps: Steps<'_>,
2423 ) -> Result<Option<T>, LoadError> {
2424 Self::query_refusal(steps).map_err(|refused| self.refused_load(refused))?;
2425 match outcome {
2426 Ok(value) => Ok(Some(value)),
2427 Err(Fail::Storage(error)) => Err(error),
2428 Err(Fail::Budget(refused)) => Err(self.refused_load(refused)),
2429 Err(
2430 Fail::Missing(_)
2431 | Fail::SuperAboveRoot
2432 | Fail::SeveralCrates { .. }
2433 | Fail::Ambiguous(_),
2434 ) => Ok(None),
2435 }
2436 }
2437
2438 fn fork_walk(state: &Walked, steps: Steps<'_>) -> Result<Walked, LoadError> {
2440 steps.storage_work(state.modules.len().saturating_add(state.items.len()))?;
2441 let mut branch = Walked::default();
2442 for module in &state.modules {
2443 insert_module(&mut branch.modules, *module, steps)?;
2444 }
2445 for (id, hit) in &state.items {
2446 if let Some(source) = &hit.last {
2447 steps.reserve(source.name.len())?;
2448 }
2449 merge(&mut branch.items, *id, hit.clone(), steps)?;
2450 }
2451 Ok(branch)
2452 }
2453
2454 fn reach_single(
2456 &self,
2457 from: usize,
2458 segs: &[String],
2459 leading_colon: bool,
2460 heads: Heads,
2461 out: &mut BTreeSet<ItemId>,
2462 steps: Steps<'_>,
2463 ) -> Result<(), LoadError> {
2464 for ns in Namespace::ALL {
2465 let mut own = Vec::new();
2466 let started = self.start(
2467 from,
2468 segs,
2469 leading_colon,
2470 ns,
2471 heads,
2472 &mut Some(&mut own),
2473 steps,
2474 );
2475 let Some((first, next)) = self.reach_outcome(started, steps)? else {
2476 continue;
2477 };
2478 let walked = self.one_crate(&first.modules, next, steps).and_then(|()| {
2479 if next == 0 {
2480 self.step(
2481 first,
2482 Step {
2483 offset: 0,
2484 seg: &segs[0],
2485 ns,
2486 last: true,
2487 },
2488 heads,
2489 None,
2490 &mut Some(&mut own),
2491 steps,
2492 )
2493 } else {
2494 Ok(first)
2495 }
2496 });
2497 if let Some(walked) = self.reach_outcome(walked, steps)? {
2498 self.take(&walked, false, &own, out, steps)?;
2499 }
2500 }
2501 Ok(())
2502 }
2503
2504 fn reach_chain(
2506 &self,
2507 from: usize,
2508 segs: &[String],
2509 leading_colon: bool,
2510 heads: Heads,
2511 out: &mut BTreeSet<ItemId>,
2512 steps: Steps<'_>,
2513 ) -> Result<(), LoadError> {
2514 let mut reads = Vec::new();
2515 let started = self.start(
2516 from,
2517 segs,
2518 leading_colon,
2519 Namespace::Type,
2520 heads,
2521 &mut Some(&mut reads),
2522 steps,
2523 );
2524 let Some((mut state, next)) = self.reach_outcome(started, steps)? else {
2525 return Ok(());
2526 };
2527 if self
2528 .reach_outcome(self.one_crate(&state.modules, next, steps), steps)?
2529 .is_none()
2530 {
2531 return Ok(());
2532 }
2533 let mut tainted = self.taints(&reads, steps)?;
2534 if next == 1 {
2535 tainted |= self.take(&state, tainted, &reads, out, steps)?;
2536 }
2537 let last_offset = segs.len() - 1;
2538 for (offset, seg) in segs.iter().enumerate().skip(next) {
2539 if offset == last_offset {
2540 let mut retained = Some(state);
2541 for (branch, ns) in Namespace::ALL.into_iter().enumerate() {
2542 let state = if branch + 1 == Namespace::ALL.len() {
2543 retained
2544 .take()
2545 .expect("the final namespace owns the retained prefix")
2546 } else {
2547 Self::fork_walk(
2548 retained
2549 .as_ref()
2550 .expect("earlier namespaces borrow the prefix"),
2551 steps,
2552 )?
2553 };
2554 let mut own = Vec::new();
2555 let walked = self.step(
2556 state,
2557 Step {
2558 offset,
2559 seg,
2560 ns,
2561 last: true,
2562 },
2563 heads,
2564 None,
2565 &mut Some(&mut own),
2566 steps,
2567 );
2568 if let Some(walked) = self.reach_outcome(walked, steps)? {
2569 self.take(&walked, tainted, &own, out, steps)?;
2570 }
2571 }
2572 return Ok(());
2573 }
2574 let mut own = Vec::new();
2575 let walked = self.step(
2576 state,
2577 Step {
2578 offset,
2579 seg,
2580 ns: Namespace::Type,
2581 last: false,
2582 },
2583 heads,
2584 None,
2585 &mut Some(&mut own),
2586 steps,
2587 );
2588 let Some(walked) = self.reach_outcome(walked, steps)? else {
2589 return Ok(());
2590 };
2591 state = walked;
2592 tainted |= self.take(&state, tainted, &own, out, steps)?;
2593 }
2594 Ok(())
2595 }
2596
2597 fn taints(&self, reads: &[Source], steps: Steps<'_>) -> Result<bool, LoadError> {
2598 if reads
2599 .iter()
2600 .any(|source| self.bound_by_undecided(source.module, source.ns, &source.name))
2601 {
2602 return Ok(true);
2603 }
2604 let broken = self.unresolved_glob_read(reads, steps)?;
2605 Self::query_refusal(steps).map_err(|refused| self.refused_load(refused))?;
2606 Ok(broken.is_some())
2607 }
2608
2609 fn take(
2611 &self,
2612 walked: &Walked,
2613 tainted: bool,
2614 own: &[Source],
2615 out: &mut BTreeSet<ItemId>,
2616 steps: Steps<'_>,
2617 ) -> Result<bool, LoadError> {
2618 if tainted || self.taints(own, steps)? {
2619 return Ok(true);
2620 }
2621 if walked.items.is_empty() || self.several_symbols(walked.items.keys().copied()) {
2622 return Ok(false);
2623 }
2624 if !self.reach_binding_determinacy(walked, own, steps)? {
2625 return Ok(true);
2626 }
2627 steps.storage_work(walked.items.len())?;
2628 for id in walked.items.keys() {
2629 if !out.contains(id) {
2630 steps.reserve(
2631 btree_entry::<ItemId, ()>()
2632 + if out.is_empty() {
2633 btree_map::<ItemId, ()>()
2634 } else {
2635 0
2636 },
2637 )?;
2638 out.insert(*id);
2639 }
2640 }
2641 Ok(false)
2642 }
2643
2644 fn through_unresolved(&self, segs: &[String], package: Option<PackageId>) -> bool {
2647 let mut prefix = String::new();
2649 segs.iter().take(segs.len().saturating_sub(1)).any(|seg| {
2650 work::add(Work::SegmentReads, 1);
2651 if !prefix.is_empty() {
2652 prefix.push_str("::");
2653 }
2654 prefix.push_str(seg);
2655 let start = self
2656 .unresolved
2657 .partition_point(|block| block.path.as_str() < prefix.as_str());
2658 self.unresolved[start..]
2659 .iter()
2660 .take_while(|block| block.path == prefix)
2661 .any(|block| {
2662 package.is_none_or(|id| self.targets[block.target.index()].package_id == id)
2663 })
2664 })
2665 }
2666
2667 pub(crate) fn resolve(
2672 &self,
2673 path: &str,
2674 ns: Option<Namespace>,
2675 package: Option<PackageId>,
2676 meter: &Meter,
2677 ) -> Result<Resolution, ResolveError> {
2678 let steps = Steps::Query(meter);
2679 let answer = self.resolve_counted(path, ns, package, steps);
2680 self.query_checked(steps, answer)
2681 }
2682
2683 fn resolve_counted(
2685 &self,
2686 path: &str,
2687 ns: Option<Namespace>,
2688 package: Option<PackageId>,
2689 steps: Steps<'_>,
2690 ) -> Result<Resolution, ResolveError> {
2691 let segs: Vec<String> = path.split("::").map(|s| strip_raw(s).to_owned()).collect();
2696 let valid = |s: &String| {
2697 !s.is_empty()
2698 && !matches!(s.as_str(), "crate" | "self" | "super" | "Self")
2699 && s.chars().all(|c| c.is_alphanumeric() || c == '_')
2700 };
2701 if !segs.iter().all(valid) {
2702 return Err(ResolveError::Invalid(path.to_owned()));
2703 }
2704 let text = segs.join("::");
2705 let spaces: Vec<Namespace> = ns.map_or_else(|| Namespace::ALL.to_vec(), |one| vec![one]);
2706 for space in spaces {
2707 match self.resolve_in(&segs, space, &text, package, steps) {
2708 Ok(resolution) => return Ok(resolution),
2709 Err(ResolveError::NotFound(_)) => {}
2710 Err(other) => return Err(other),
2711 }
2712 }
2713 if self.through_unresolved(&segs, package) {
2714 return Err(ResolveError::UnresolvedSelf(text));
2715 }
2716 Err(ResolveError::NotFound(text))
2717 }
2718}
2719
2720#[cfg(test)]
2721mod tests {
2722 use super::ResolveError;
2723 use crate::item::ItemId;
2724 use crate::work::{self, Work};
2725 use crate::{MemoryTree, Workspace};
2726
2727 const HOSTILE: &str = "a\u{1b}[2J\u{202e}\r\nb";
2729
2730 fn every_variant() -> Vec<ResolveError> {
2733 let hostile = || HOSTILE.to_owned();
2734 let all = vec![
2735 ResolveError::NotFound(hostile()),
2736 ResolveError::Ambiguous(vec![ItemId(0), ItemId(1)]),
2737 ResolveError::Cyclic(hostile()),
2738 ResolveError::Invalid(hostile()),
2739 ResolveError::UnresolvedSelf(hostile()),
2740 ResolveError::UnknownPackage(hostile()),
2741 ResolveError::AmbiguousPackageName(hostile()),
2742 ResolveError::UnknownPackageId(crate::PackageId(7)),
2743 ResolveError::UnconfiguredPackage(crate::PackageId(7)),
2744 ResolveError::UnconfiguredDefinition(ItemId(7)),
2745 ResolveError::UnknownModule(hostile()),
2746 ResolveError::IndeterminateImport {
2747 path: hostile(),
2748 file: crate::RelPath::new(&format!("src/{}.rs", hostile()))
2749 .expect("a relative path"),
2750 line: 3,
2751 },
2752 ResolveError::UnresolvedGlob {
2753 path: hostile(),
2754 glob: hostile(),
2755 module: hostile(),
2756 },
2757 ResolveError::Budget {
2758 budget: crate::Budget::Work,
2759 limit: 7,
2760 file: crate::RelPath::new(&format!("src/{}.rs", hostile()))
2761 .expect("a relative path"),
2762 line: Some(3),
2763 },
2764 ResolveError::Storage {
2765 file: crate::RelPath::new(&format!("src/{}.rs", hostile()))
2766 .expect("a relative path"),
2767 line: Some(3),
2768 what: hostile(),
2769 },
2770 ];
2771 for error in &all {
2772 match error {
2773 ResolveError::NotFound(_)
2774 | ResolveError::Ambiguous(_)
2775 | ResolveError::Cyclic(_)
2776 | ResolveError::IndeterminateImport { .. }
2777 | ResolveError::Invalid(_)
2778 | ResolveError::UnresolvedSelf(_)
2779 | ResolveError::UnknownPackage(_)
2780 | ResolveError::AmbiguousPackageName(_)
2781 | ResolveError::UnknownPackageId(_)
2782 | ResolveError::UnconfiguredPackage(_)
2783 | ResolveError::UnconfiguredDefinition(_)
2784 | ResolveError::UnknownModule(_)
2785 | ResolveError::UnresolvedGlob { .. }
2786 | ResolveError::Budget { .. }
2787 | ResolveError::Storage { .. } => {}
2788 }
2789 }
2790 all
2791 }
2792
2793 #[test]
2794 fn every_user_derived_field_of_every_resolve_error_is_escaped() {
2795 for error in every_variant() {
2796 let text = error.to_string();
2797 assert!(
2798 !text.chars().any(|c| c.is_control() || c == '\u{202e}'),
2799 "a control character got through: {text:?}"
2800 );
2801 let fields = match &error {
2802 ResolveError::Ambiguous(_)
2803 | ResolveError::UnknownPackageId(_)
2804 | ResolveError::UnconfiguredPackage(_)
2805 | ResolveError::UnconfiguredDefinition(_) => 0,
2806 ResolveError::UnresolvedGlob { .. } => 3,
2807 ResolveError::IndeterminateImport { .. } | ResolveError::Storage { .. } => 2,
2808 _ => 1,
2809 };
2810 assert_eq!(
2811 text.matches(r"a\u{1b}[2J\u{202e}\r\nb").count(),
2812 fields,
2813 "{text}"
2814 );
2815 }
2816 }
2817
2818 #[test]
2819 fn a_module_path_of_fifty_thousand_segments_is_read_once_to_find_its_crate() {
2820 const SEGMENTS: usize = 50_000;
2821 let manifest = "[package]\nname = \"demo\"\nversion = \"0.1.0\"\n";
2822 let tree: MemoryTree = [("Cargo.toml", manifest), ("src/lib.rs", "pub fn x() {}\n")]
2823 .into_iter()
2824 .collect();
2825 let ws = Workspace::load(&tree, &["."]).unwrap_or_else(|e| panic!("{e}"));
2826 let module = format!("demo{}", "::a".repeat(SEGMENTS));
2827 let (answer, tally) = work::measure(SEGMENTS + 1, || ws.resolve_from(&module, "x"));
2828 assert_eq!(answer, Err(ResolveError::UnknownModule(module.clone())));
2829 assert_eq!(tally.get(Work::SegmentReads), SEGMENTS + 1);
2831 let (answer, tally) = work::measure(SEGMENTS + 1, || ws.resolve_from("demo", "x"));
2832 assert_eq!(answer.map(|found| found.path), Ok("demo::x".to_owned()));
2833 assert!(tally.get(Work::SegmentReads) >= 1);
2834 }
2835
2836 #[test]
2837 fn a_path_of_fifty_thousand_segments_reads_each_segment_a_bounded_number_of_times() {
2838 const SEGMENTS: usize = 50_000;
2839 let manifest = "[package]\nname = \"demo\"\nversion = \"0.1.0\"\n";
2840 let tree: MemoryTree = [
2841 ("Cargo.toml", manifest),
2842 (
2843 "src/lib.rs",
2844 "pub mod m { pub use crate::m; pub fn end() {} }\n",
2845 ),
2846 ]
2847 .into_iter()
2848 .collect();
2849 let ws = Workspace::load(&tree, &["."]).unwrap_or_else(|e| panic!("{e}"));
2850 let missing = format!("demo{}", "::a".repeat(SEGMENTS));
2851 let deep = format!("demo{}::end", "::m".repeat(SEGMENTS));
2852 let segments = SEGMENTS + 2;
2857 let reads = 4 * segments;
2858 let lookups = 2 * segments;
2859 let (answer, tally) = work::measure(reads, || ws.resolve(&missing));
2860 assert_eq!(answer, Err(ResolveError::NotFound(missing.clone())));
2861 assert!(tally.get(Work::SegmentReads) > 0);
2862 assert!(tally.get(Work::SegmentReads) <= reads);
2863 assert!(tally.get(Work::Lookups) > 0);
2864 assert!(tally.get(Work::Lookups) <= lookups);
2865 let (answer, tally) = work::measure(reads, || ws.resolve(&deep));
2866 assert_eq!(answer.expect("the deep path resolves").path, "demo::m::end");
2867 assert!(tally.get(Work::SegmentReads) > 0);
2868 assert!(tally.get(Work::SegmentReads) <= reads);
2869 assert!(tally.get(Work::Lookups) > 0);
2870 assert!(tally.get(Work::Lookups) <= lookups);
2871 }
2872}