Skip to main content

raf_source/
resolve.rs

1// SPDX-FileCopyrightText: 2026 Blackcat InformaticsĀ® Inc. <paudley@blackcatinformatics.ca>
2// SPDX-License-Identifier: MIT OR Apache-2.0 OR MulanPSL-2.0
3
4//! Name resolution over the settled scope tables.
5//!
6//! A path is walked segment by segment through the tables built by
7//! [`crate::settle`]. Visibility is not checked on a walk: the index answers
8//! whether a path names an item, and a private item is still an item. Glob
9//! imports are the one place visibility counts, because rustc imports only the
10//! names the importing module can name.
11
12use 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/// The items a walk reached, and the modules a keyword path named.
38#[derive(Debug, Default)]
39pub(crate) struct Walked {
40    pub(crate) modules: BTreeSet<usize>,
41    pub(crate) items: BTreeMap<ItemId, Hit>,
42}
43
44/// How a walk reached an item.
45#[derive(Debug, Clone)]
46pub(crate) struct Hit {
47    pub(crate) via_glob: bool,
48    pub(crate) last: Option<Source>,
49}
50
51impl Hit {
52    /// Of two routes to one item the lesser wins: one that uses no glob beats
53    /// one that does, and ties go to the smaller source.
54    fn rank(&self) -> (bool, &Option<Source>) {
55        (self.via_glob, &self.last)
56    }
57}
58
59/// One segment of a walk: its position in the path, its text, the name space
60/// it is read in and whether it is the last segment of the path.
61#[derive(Debug, Clone, Copy)]
62struct Step<'s> {
63    offset: usize,
64    seg: &'s str,
65    ns: Namespace,
66    last: bool,
67}
68
69/// Add a route to an item, keeping the better route if it is already there.
70fn 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    /// A retained import read was refused before allocating its storage.
102    Storage(LoadError),
103    Missing(Vec<Source>),
104    SuperAboveRoot,
105    /// The path goes through a name that stands for the crate roots of
106    /// several crates, as a crate name of the extern prelude that names
107    /// several libraries does: `roots` are those crate roots, and the path
108    /// would go on in each with its segments from `rest` on. rustc refuses
109    /// such a name whatever follows it.
110    SeveralCrates {
111        roots: Vec<ItemId>,
112        rest: usize,
113    },
114    /// The first segment of a `use` path of edition 2018 or later names both
115    /// what a glob of its module brings in and a different crate of the
116    /// extern prelude, which rustc refuses as ambiguous: `ids` are the items
117    /// the glob brings in and the crate roots of the workspace that the crate
118    /// name stands for.
119    Ambiguous(Vec<ItemId>),
120    /// The lookups of a query after the load passed the limit of its work
121    /// (see [`Index::query_refusal`]). Only a walk of a query fails so: the
122    /// lookups of the load are refused at its checkpoints.
123    Budget(Refused),
124}
125
126impl From<LoadError> for Fail {
127    fn from(error: LoadError) -> Self {
128        Self::Storage(error)
129    }
130}
131
132/// The dependencies, ambiguous items and source reads of one named import.
133#[derive(Default)]
134struct ImportWalks {
135    blockers: Vec<usize>,
136    ambiguous: Vec<ItemId>,
137    reads: Vec<Source>,
138}
139
140/// Why an import-backed place cannot provide a settled binding.
141pub(crate) enum Unsettled {
142    Cycle,
143    LateImport(usize),
144}
145
146/// Why a walk of the load is never refused for its work: only a walk of a
147/// query counts its lookups on a meter it is refused by, and the lookups of
148/// the load are charged at its checkpoints.
149pub(crate) const LOAD_WALK: &str = "a walk of the load is never refused for its work";
150
151/// The refusal of a query whose lookups passed the limit of its work.
152#[derive(Debug, Clone, Copy)]
153pub(crate) struct Refused {
154    /// The limit of the work of one query.
155    limit: usize,
156    /// The module whose lookup passed it.
157    module: usize,
158}
159
160/// The globs of the settled tables whose paths resolve, with the modules
161/// they glob, and those that a lookup reading them fails for (see
162/// [`ResolveError::UnresolvedGlob`]).
163#[derive(Debug, Default)]
164pub(crate) struct GlobFacts {
165    reach: Vec<Vec<usize>>,
166    broken: OrderedTable<usize, ()>,
167}
168
169/// Derived query state, excluded from the equality of the settled index.
170///
171/// Its facts are a pure function of the other index fields. Their admitted
172/// construction finishes before the completed index is published; retaining
173/// derived data does not change what a workspace represents.
174#[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/// What the walks of a canonical path from its crate roots found: the items
196/// they reach, the places they found unbound and the places they read.
197#[derive(Default)]
198struct Walks {
199    found: BTreeMap<ItemId, Hit>,
200    missing: Vec<Source>,
201    reads: Vec<Source>,
202}
203
204/// What the path of a glob import names in the settled tables.
205enum GlobPath {
206    /// The modules it globs.
207    Resolves(BTreeSet<usize>),
208    /// Nothing, as rustc refuses it: a path through a name that stands for
209    /// several crates, an ambiguous first segment, or `super` above the root.
210    Nothing,
211    /// What the index cannot see: a first segment that names nothing in the
212    /// workspace, as a dependency, or a path that goes on in a crate outside
213    /// it.
214    Unknown,
215    /// Nothing past its first segment: the places where it names nothing.
216    Misses(Vec<Source>),
217}
218
219/// What the first segment of a path may name besides the items in scope.
220#[derive(Debug, Clone, Copy, PartialEq, Eq)]
221pub(crate) enum Heads {
222    /// Nothing else: a canonical path, which starts at a crate root.
223    Local,
224    /// A crate of the extern prelude of the module's target, as code written
225    /// in the module names it; `test` for test code, which also names the
226    /// dev-dependencies of a library or a binary.
227    Code {
228        /// True for test code.
229        test: bool,
230    },
231    /// The path of a `use` declaration. In edition 2015 a path whose first
232    /// segment is not `crate`, `self` or `super` starts at the crate root. In
233    /// edition 2018 and later it starts as `Code` does, and a first segment
234    /// that a glob of the module binds and that is also a different crate of
235    /// the extern prelude is ambiguous. `own` is the named import whose path
236    /// it is: an import never resolves through its own binding.
237    Use {
238        /// True for test code.
239        test: bool,
240        /// The position of the named import whose path this is.
241        own: Option<usize>,
242    },
243}
244
245impl Heads {
246    /// The named import whose own binding the walk does not consult.
247    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/// What `resolve` found.
256#[derive(Debug, Clone, PartialEq, Eq)]
257#[non_exhaustive]
258pub struct Resolution {
259    /// The canonical path of the symbol: where it is defined.
260    pub path: String,
261    /// The name space the path was resolved in.
262    pub namespace: Namespace,
263    /// The definitions of the symbol, never empty and sorted by path, file and
264    /// position. More than one means the same symbol is defined more than
265    /// once, as `#[cfg(unix)] fn a()` beside `#[cfg(windows)] fn a()`.
266    pub sites: Vec<ItemId>,
267    /// True when a glob import carried the path to the symbol.
268    pub via_glob: bool,
269    /// The locations the lookup passed through, from the last segment of the
270    /// requested path to the definition.
271    pub chain: Vec<String>,
272    /// Exact type-alias definitions traversed by an associated-member code query.
273    /// These are loaded syntax identities; callers still audit configuration and
274    /// unexpanded declaration attributes before using them as execution proof.
275    pub type_aliases: Vec<ItemId>,
276}
277
278/// Why a path did not resolve.
279#[derive(Debug, Clone, PartialEq, Eq)]
280#[non_exhaustive]
281pub enum ResolveError {
282    /// Nothing the workspace defines has this path. A dependency item, a macro
283    /// expansion and a misspelling all end here.
284    NotFound(String),
285    /// The path names more than one symbol: two globs that bring in different
286    /// items, two imports of one name, two canonical targets, items of two
287    /// targets at one path, a crate path that targets of several packages
288    /// share, or a path through a crate name that stands for several
289    /// libraries (the ids are then the crate roots).
290    Ambiguous(Vec<ItemId>),
291    /// The imports that the path goes through depend on each other.
292    Cyclic(String),
293    /// An import initially found an inaccessible binding, then a later
294    /// glob route made its path accessible. A settled lookup can read that
295    /// path, but the earlier import cannot acquire the late binding.
296    IndeterminateImport {
297        /// The path the caller tried to resolve.
298        path: String,
299        /// The source file of the import that could not be determined.
300        file: RelPath,
301        /// Its one-based source line.
302        line: usize,
303    },
304    /// The text is not a path.
305    Invalid(String),
306    /// Nothing the workspace defines has this path, and the path goes through
307    /// the self type of an inherent impl that the index cannot see (see
308    /// [`SelfType::Unresolved`](crate::SelfType::Unresolved)), which may define
309    /// it.
310    UnresolvedSelf(String),
311    /// The package named to qualify the path is not a package of the
312    /// workspace.
313    UnknownPackage(String),
314    /// Several loaded packages have the requested display name. Select a
315    /// load-local package identity instead.
316    AmbiguousPackageName(String),
317    /// The package identity does not exist in this workspace.
318    UnknownPackageId(PackageId),
319    /// The package has only a structural index, without a declared active context.
320    UnconfiguredPackage(PackageId),
321    /// A resolved site has no admitted active definition context.
322    UnconfiguredDefinition(ItemId),
323    /// The module named to read a `use` path from is not a module of the
324    /// workspace.
325    UnknownModule(String),
326    /// A lookup on the way of the path reads the names a glob import brings
327    /// in, and the glob's path names nothing in the workspace past its first
328    /// segment (`use self::missing::*;`, `use crate::a::gone::*;`). rustc
329    /// refuses such a glob, so what the lookup would find is not known. The
330    /// load does not fail for it: a module that a macro generates is globbed
331    /// this way. A glob whose first segment names nothing in the workspace,
332    /// as a dependency does, is not one: the index cannot look into it.
333    UnresolvedGlob {
334        /// The path that was resolved.
335        path: String,
336        /// The written path of the glob, without its `::*`.
337        glob: String,
338        /// The path of the module that declares the glob.
339        module: String,
340    },
341    /// The query passed its lookup/proof work or transient proof-byte limit.
342    /// Lookup and proof work share the limit of the work of one query,
343    /// [`LoadOptions::max_query_work`](crate::LoadOptions::max_query_work):
344    /// the glob reads its lookups of what the globs of a module bring in
345    /// looked at, and the views that hold a name looked at to find them,
346    /// counted from zero for each query. The answer is not given. This is
347    /// the refusal a load gets from the same budget,
348    /// [`LoadErrorKind::Budget`](crate::LoadErrorKind::Budget): `budget` is
349    /// [`Budget::Work`], [`Budget::ItemBytes`] or [`Budget::GlobBytes`], `limit` the limit that applied, and `file` and
350    /// `line` name the declaration of the module whose lookup passed it.
351    Budget {
352        /// The work, item-byte or glob-byte budget passed.
353        budget: Budget,
354        /// The limit that applied.
355        limit: usize,
356        /// The file of the declaration of the module whose lookup passed it.
357        file: RelPath,
358        /// The line of that declaration, when it has one.
359        line: Option<usize>,
360    },
361    /// A query's native scratch allocation failed for a reason other than
362    /// a configured budget. The original failure is retained for diagnosis.
363    Storage {
364        /// The source file of the binding being checked.
365        file: RelPath,
366        /// Its source line, when known.
367        line: Option<usize>,
368        /// The allocation failure.
369        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
470/// Add the place `name` in `module` in `ns` to the places a walk read, when
471/// they are noted.
472fn 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    /// Refuse a step of a walk that would go on in the crate roots of several
555    /// crates at once, with the segments from `rest` on.
556    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    /// Add to `into` the crate roots of the workspace that the crate name
586    /// `name` stands for in code of `module` (see [`Heads`]): a library of the
587    /// extern prelude of the module's target, or what an `extern crate` item
588    /// at the crate root names, which adds its name to that prelude. Returns
589    /// whether it added any.
590    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    /// Borrow the same prelude and root declarations used by external resolution.
606    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    /// True when a path read under `heads` from `from` starts at the crate
633    /// root: in edition 2015, a `use` path whose first segment is not a
634    /// keyword, and any path written with a leading `::`.
635    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    /// True when `name` is a crate of the extern prelude that a `use` path in
651    /// `module` can start with: `core`, `std` unless the crate has
652    /// `#![no_std]`, a crate of its target's extern prelude for its test code
653    /// (`test`) or other code, or an `extern crate` item at the crate root.
654    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    /// The crate outside the index that the path of the named import at
662    /// `position` starts at, if it starts at one: from edition 2018 on, a
663    /// first segment its module does not bind that is a crate of the extern
664    /// prelude standing for no library of the workspace, or one with a
665    /// leading `::`; in edition 2015, the crate an `extern crate` item at the
666    /// crate root names, or the crate the compiler puts there.
667    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                // An `extern crate` item of a crate outside the index.
691                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    /// The aliases of another crate that the globs of `from` bring in under
742    /// `name`: named imports whose path is a single segment, a crate outside
743    /// the index other than `name` (`pub use std as serde;`), that bind
744    /// `name` in a module the globs reach, directly or through the globs of
745    /// that module, and are visible from `from`. An import of an item of a
746    /// crate outside the index is not one: the index cannot tell its name
747    /// space, and only the type name space collides with a crate (`use
748    /// quote::quote;` brings in a macro).
749    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    /// True when the crate root of `module` binds `name` to an `extern crate`
828    /// item.
829    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    /// The ambiguity of a `use` path whose first segment `name`, written in
839    /// `from`, a glob of the module binds to `bound` in the type name space:
840    /// the items, with the crate roots that the crate name stands for, when
841    /// the name is also a crate of the extern prelude and the glob brings in
842    /// something other than that crate.
843    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    /// Refuse, or hold back, a path whose first segment `first`, which `from`
901    /// does not bind in `ns`, would start at a crate of the extern prelude.
902    /// An explicit import of the name binds it before a crate does, in every
903    /// name space where it keeps the name from the globs (see
904    /// [`Index::blocked`]), whether or not the index can see what it binds:
905    /// there the path never starts at a crate and waits on the name. For a `use`
906    /// path, a glob of the module may still bring the name in, and a name a
907    /// glob brings in that is also a crate is ambiguous, so until the globs
908    /// are settled the path waits on the name. An explicit import's first
909    /// segment that a glob brings in from an import outside the index, which
910    /// the index does not bind, is ambiguous with the crate too (a glob's own
911    /// path is not checked: the check reads the globs of the module).
912    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        // An explicit import shadows a crate in the name spaces where it
931        // keeps the name from the globs, and a glob may still bring the name
932        // in: the path waits on it.
933        if self.blocked(from, first, ns, heads.own()) {
934            return wait();
935        }
936        // A glob of the module that may still bring the name in from a
937        // module where an import keeps it holds back a crate as well, as the
938        // two would be ambiguous. A glob whose path is not settled does not:
939        // until the globs have brought in what they can no crate is read, and
940        // a glob that brings the name in later makes the path ambiguous,
941        // which the settled tables are checked for (see
942        // [`Index::settle_agreed`]).
943        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        // A glob's own path is not checked: the check reads the globs of the
952        // module.
953        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        // An alias of another crate that a glob carries collides with the
961        // crate, though what it binds is never settled in the index.
962        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    /// The state after the first segment of a path, and the index of the
981    /// segment to read next.
982    #[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            // The walk reads the first segment in the crate root's scope,
1002            // which holds its items, its imports and its `extern crate` items.
1003            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                        // As in the segment loop: a name two globs bring in
1049                        // as different items is ambiguous in the module, and
1050                        // a path cannot start with it, also where only one
1051                        // of the items has what the path goes on to name.
1052                        // The `cfg` alternatives of one module are one
1053                        // candidate, and so are definitions and imports of
1054                        // one name, which all count.
1055                        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    /// Walk `segs` from `from`, in the name space `last_ns` for the last
1095    /// segment and the type name space before it.
1096    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    /// [`Index::walk`], adding to `reads` every place whose binding the walk
1109    /// looked up, found or not: what its answer depends on while the tables
1110    /// settle.
1111    ///
1112    /// The lookup steps of the walk are counted where `steps` says. In a
1113    /// query after the load the walk is refused with [`Fail::Budget`] once
1114    /// they pass the limit of the query: after its first segment and after
1115    /// each segment it reads.
1116    #[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        // A `use` path reads each module as rustc resolves an import: only
1131        // what the importing module can access counts.
1132        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    /// One actual metered segment, shared by use/code walks and prefix reachability.
1173    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                // A name two globs bring in as different items is
1218                // ambiguous in the module, and a path cannot go
1219                // through it, as in rustc: also where only one of the
1220                // items has what the path goes on to name. The
1221                // `cfg` alternatives of one module are one
1222                // candidate, and the definitions and imports of a
1223                // name all count.
1224                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    /// The unresolved named imports that can bind `name` in `namespace`.
1276    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    /// Walk a named import in its terminal namespaces without its own binding.
1295    /// Collect unresolved peers, ambiguous first-segment items and read places.
1296    ///
1297    /// # Errors
1298    ///
1299    /// Preserves storage and work refusals from every namespace walk.
1300    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            // The path never reads the imports of the name it binds.
1330            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            // Ordinary imports can bind in all namespaces. A grouped `self`
1340            // can bind only in Type, so one scan suffices for all these reads.
1341            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        // The import's own binding is never a way its path goes.
1349        blockers.remove(&position);
1350        Ok(ImportWalks {
1351            blockers: blockers.into_iter().collect(),
1352            ambiguous: ambiguous.into_iter().collect(),
1353            reads,
1354        })
1355    }
1356
1357    /// True when what is bound at `source` was bound by a named import that
1358    /// never settled: one that bound its name in this name space and is left
1359    /// undecided in another, by a cycle there, or one that a cycle left to
1360    /// the globs there and that never decided (see [`Index::left_to_globs`]).
1361    /// rustc reports such an import as an error, that it cannot determine
1362    /// its resolution, whatever it bound, so a path through it does not
1363    /// resolve.
1364    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    /// Why nothing is bound at `missing`, the places a walk found unbound:
1376    /// `Cyclic` when an import that binds one of them never settled, which
1377    /// the settling of the tables leaves only to the imports of a cycle and
1378    /// those that wait on one, or a glob may still bring the name in from a
1379    /// module where such an import keeps it (see [`Index::unsettled_at`]);
1380    /// else
1381    /// `Ambiguous` naming the items of every ambiguous first segment among
1382    /// the unresolved imports that bind them, or that those wait on; else
1383    /// `UnresolvedGlob` when a lookup of the walk, at `reads`, or of the paths
1384    /// of those imports reads a glob whose path names nothing past its first
1385    /// segment; else `NotFound`.
1386    ///
1387    /// A query whose lookups pass its limit on the way is refused with
1388    /// [`ResolveError::Budget`] instead.
1389    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        // The imports on the way wait on no cycle, so the search ends; it
1426        // keeps a list of its own and visits each import once.
1427        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    /// The error of a path `text` whose lookups read the glob import at
1482    /// `position`, whose path names nothing past its first segment.
1483    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    /// True when a lookup of `name` in `ns` in `module` finds an explicit
1498    /// binding there, or an explicit import keeps the name from the globs
1499    /// (see [`Index::blocked`]): the globs of the module are not read.
1500    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    /// What the path of the glob import at `position` names in the settled
1508    /// tables.
1509    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        // A missing path with no known source cannot be diagnosed as a
1524        // missing local module. This also covers a glob with no segments.
1525        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        // A first segment that names nothing in the workspace, or a path
1543        // that goes on in a crate outside it, is a dependency.
1544        if head.is_err() {
1545            Ok(GlobPath::Unknown)
1546        } else {
1547            Ok(GlobPath::Misses(sources))
1548        }
1549    }
1550
1551    /// The failure that [`Index::resolve`] reports for a path `text` whose
1552    /// last segment reads `name` in `module` in `ns`, where the module binds
1553    /// it to `bound` (what [`Index::lookup_in`] answers there), as far as
1554    /// that last place decides it: `Cyclic` when an import that never
1555    /// settled bound it there, `Ambiguous` when it binds several symbols
1556    /// there, and `UnresolvedGlob` when the lookup reads a glob whose path
1557    /// names nothing past its first segment. The places before the last are
1558    /// the caller's to have checked, each as the last place of its own
1559    /// prefix, so a path is checked once for each of its segments however
1560    /// long the chain of imports behind each one.
1561    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    /// The refusal of a query whose lookups passed the limit of its work,
1598    /// once they have: the walks of the query check it after each segment,
1599    /// and the query before it answers. Never for the load, whose lookups
1600    /// are refused at its checkpoints.
1601    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    /// The answer of a query, or its refusal when its lookups passed the
1614    /// limit of its work on the way: the refusal comes first.
1615    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    /// The [`ResolveError::Budget`] of a refused query.
1627    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    /// The [`LoadError`] of a refused query, as the public surface reports
1638    /// it ([`ExportError::Budget`](crate::ExportError::Budget)).
1639    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    /// The file and line that name `module`: its `mod` item, or for a crate
1645    /// root the root file of its target, with no line.
1646    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    /// True when the path of the glob import at `position` names nothing in
1658    /// the workspace past its first segment, so a lookup that reads it fails
1659    /// with [`ResolveError::UnresolvedGlob`].
1660    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        // The recorded origins lead back to a definition; the guard is for a
1708        // route that was replaced by a better one while the tables settled.
1709        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    /// The package of the target whose crate `module` is in.
1725    fn package_of(&self, module: usize) -> PackageId {
1726        self.targets[self.modules[module].target.index()].package_id
1727    }
1728
1729    /// Walk `rest`, the segments of a canonical path `text` after the crate
1730    /// path of `root`, in `ns`, adding to `walks` what it reaches, the places
1731    /// it found unbound and the places it read.
1732    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            // A canonical path holds no `super` (see [`Index::resolve`]), so
1770            // no walk of one climbs above a crate root; if one did, the path
1771            // is not a path.
1772            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    /// Resolve a canonical path in one name space, among the crates of
1782    /// `package` when one is given.
1783    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        // The prefix grows by one segment a step, so the prefixes of a path
1793        // cost its length, not its length squared.
1794        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            // A crate path that targets of several packages have (two
1810            // libraries with one crate name) names each of their crates; the
1811            // path is told apart only with its package.
1812            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                    // A path that is exactly a crate path names the crate
1828                    // root, a module.
1829                    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    /// What a walk found, as the answer: the unbound error when it found
1868    /// nothing, ambiguity when it found several symbols, and the symbol
1869    /// otherwise. `from_keys` is true when the items come from the foreign
1870    /// keys and not from a walk.
1871    #[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        // One symbol is one path and kind in one crate. Items of two targets
1889        // at one path are two symbols, whatever order they were found in; the
1890        // members of trait impls on types that are not local are keyed by
1891        // the trait, so the impls of every crate share their key.
1892        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        // A lookup on the way that read a glob whose path names nothing past
1906        // its first segment may have missed what the glob would bring in.
1907        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    /// True when `ids` are more than one symbol: a symbol is one path and
1927    /// kind in one crate, so the `cfg` alternatives of one module, which the
1928    /// index keeps as several items, are one.
1929    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    /// The module whose canonical path is `path`, such as `demo::inner`, in
1940    /// the crate of any target: the crate path that starts it is found by
1941    /// prefixes that grow a segment at a time, as in [`Index::resolve_in`],
1942    /// so `demo::test_crate::it::support` is a module of the test target
1943    /// `it` and `demo::bin_crate::tool::cli` one of the binary `tool`.
1944    ///
1945    /// A crate path that targets of several packages share (two libraries
1946    /// with one crate name) names the crates of all of them, and the module is
1947    /// not told apart without its package: it is
1948    /// [`ResolveError::Ambiguous`] between their crate roots, as
1949    /// [`Index::resolve`] answers for a path that starts with that crate path.
1950    /// A path that is a module of two crates, a module `test_crate::it` of the
1951    /// library beside the test target `it`, is ambiguous between the items
1952    /// that stand for the two modules.
1953    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    /// Resolve the path of a `use` declaration written in the module
1993    /// `module`, in `ns` or in each name space in turn.
1994    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    /// [`Index::resolve_from`], its lookup steps counted where `steps` says.
2008    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    /// The shared traversal for a known reading module and explicit head rules.
2131    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    /// Resolve a first-party alias RHS and observe a proven opaque import route.
2144    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    /// Refine a failed route with the native visibility and type-read proofs.
2261    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    /// Follow unique named imports to a crate the index cannot inspect.
2287    /// This proves only where the route leaves the index.
2288    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        // The ordinary failure diagnostic already checks for import cycles.
2296        // A unique route cannot visit more declarations than the index holds.
2297        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    /// The items that a run of path segments, written in code of `from`,
2359    /// names, each run read once segment by segment: every proper prefix in
2360    /// the type name space, the name space a path goes on through, and the
2361    /// whole run in each name space. `test` is true for test code, which also
2362    /// names the dev-dependencies of a library or a binary.
2363    ///
2364    /// A prefix counts as [`Index::resolve_from`] would answer it, read as
2365    /// code reads it ([`Heads::Code`]): it names its items when the walk
2366    /// reaches them, no import on the way is undecided, they are one symbol
2367    /// and no lookup on the way reads a glob whose path names nothing; a
2368    /// prefix that fails names nothing, and every longer prefix fails with it.
2369    /// A prefix of path keywords alone (`crate`, `self`, `super`) names a
2370    /// module and no item.
2371    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    /// A decoded format capture is a value, without type/macro prefix edges.
2391    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    /// Only semantic nonresolution contributes no reachability edge.
2419    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    /// Admit the owned prefix reused by another terminal namespace branch.
2439    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    /// A single segment is read in each namespace under the same allowance.
2455    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    /// Walk each proper type prefix once, then fork only the terminal namespaces.
2505    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    /// Retain only untainted, unambiguous reached identities, before allocating.
2610    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    /// True when a proper prefix of `segs` is the self path of an inherent
2645    /// impl that the index cannot see, of `package` when one is given.
2646    fn through_unresolved(&self, segs: &[String], package: Option<PackageId>) -> bool {
2647        // The prefix grows by one segment a step, as in [`Index::resolve_in`].
2648        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    /// Resolve `path`, trying the type, value and macro name spaces in turn,
2668    /// among the crates of `package` when one is given. The lookup steps are
2669    /// counted on `meter`, the meter of the query: one that passes its limit
2670    /// is refused with [`ResolveError::Budget`], whatever it would answer.
2671    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    /// [`Index::resolve`], its lookup steps counted where `steps` says.
2684    fn resolve_counted(
2685        &self,
2686        path: &str,
2687        ns: Option<Namespace>,
2688        package: Option<PackageId>,
2689        steps: Steps<'_>,
2690    ) -> Result<Resolution, ResolveError> {
2691        // Each segment is read once. A canonical path starts at a crate root
2692        // and names items by their names, so a path keyword is no segment of
2693        // one: `demo::crate::a::x` and `demo::super::x` are not canonical
2694        // paths, and neither is `r#crate`, which is no raw identifier.
2695        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    /// An escape sequence, a bidirectional override and a line break.
2728    const HOSTILE: &str = "a\u{1b}[2J\u{202e}\r\nb";
2729
2730    /// Every variant, built so that a new one cannot be left out: the match
2731    /// names each.
2732    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        // Each segment grows the crate path that is looked up once.
2830        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        // A path is walked in each name space and scanned once for a block it
2853        // cannot see into, so a segment is read a few times and not once for
2854        // each segment before it. The bound is also the ceiling, so a walk
2855        // that starts again from the crate root for each prefix stops at once.
2856        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}