Skip to main content

raf_source/
reach.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//! Reachability: the items and impl blocks of every target that a set of root
5//! items reach over three edges.
6//!
7//! * **contains**: a struct, enum or union to its methods and associated
8//!   items, a trait to its members, and a module reached from a root by
9//!   contains alone to its items and the impl blocks it holds. A crate root
10//!   contains nothing, and a module reached any other way reaches nothing
11//!   below it.
12//! * **impl-of**: a struct, enum or union to the impl blocks whose self type
13//!   it is, and a block to its members.
14//! * **references**: an item or a block to each item that a path in its own
15//!   tokens names. The paths are the `Ident (:: Ident)*` runs that no `.`
16//!   precedes, read as code of its module reads it: each proper prefix in the
17//!   type name space and the whole run in each name space. A run that `Self`
18//!   starts, and a method called on `self`, are read in the impl block or the
19//!   trait that holds the unit: they name its members of that name.
20//!   Positively identified standard `format!` calls also name their decoded
21//!   implicit value and count captures. Named argument binding identifiers are
22//!   not value paths; their expressions retain the ordinary reference rules.
23//!
24//! The tokens of an item are those of its span outside the spans of the items
25//! and blocks below it: a type's members and a block's members are their own
26//! units. A module's own tokens are its declaration before its body; what a
27//! module body holds outside its items and blocks (its `use` declarations and
28//! the macro invocations at module level) is no item's, and a crate root has
29//! none. Each file is lexed once per package edition, the first time an item
30//! of it is reached in that edition, and
31//! each run is resolved, and what it names given to the walk, at most once
32//! for each place it is read in: a module with a test flag, or an impl block
33//! or a trait. What the walk holds is charged to the item-bytes budget of the
34//! load.
35
36use std::collections::btree_map::Entry;
37use std::collections::{BTreeMap, BTreeSet, VecDeque};
38use std::error::Error;
39use std::fmt;
40use std::mem::size_of;
41use std::panic;
42use std::str::FromStr;
43use std::thread;
44
45use proc_macro2::{Delimiter, Spacing, TokenStream, TokenTree};
46
47use crate::cost::{btree_entry, btree_map, vec_first, vec_slot};
48use crate::error::{LoadError, LoadErrorKind};
49use crate::facts::TestRole;
50use crate::index::Index;
51use crate::item::{ImplId, ItemId, SharedStr, SymbolKind};
52use crate::meter::{Meter, Steps};
53use crate::options::LoadOptions;
54use crate::parse::PARSE_STACK_BYTES;
55use crate::path::RelPath;
56use crate::work::{self, Work};
57use crate::workspace::SourceFile;
58
59mod format;
60
61/// A node of the reachability graph: an item or an impl block.
62#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
63pub enum Node {
64    /// An item of the index.
65    Item(ItemId),
66    /// An impl block of [`Workspace::impls`](crate::Workspace::impls).
67    Impl(ImplId),
68}
69
70impl From<ItemId> for Node {
71    fn from(id: ItemId) -> Self {
72        Self::Item(id)
73    }
74}
75
76impl From<ImplId> for Node {
77    fn from(id: ImplId) -> Self {
78        Self::Impl(id)
79    }
80}
81
82/// The edge a node was first reached by.
83#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
84#[non_exhaustive]
85pub enum Edge {
86    /// The node is one of the roots.
87    Root,
88    /// The node is below the node it was reached from: a member of a type or
89    /// a trait, or an item or impl block of a module.
90    Contains,
91    /// The node is an impl block of the type it was reached from, or a
92    /// member of the impl block it was reached from.
93    ImplOf,
94    /// A path in the tokens of the node it was reached from names it.
95    References,
96}
97
98/// One reached node, with the edge it was first reached by and the node that
99/// edge comes from (`None` for a root).
100#[derive(Debug, Clone, Copy, PartialEq, Eq)]
101#[non_exhaustive]
102pub struct Reached {
103    /// The node.
104    pub node: Node,
105    /// The edge it was first reached by.
106    pub edge: Edge,
107    /// The node that edge comes from; `None` for a root.
108    pub from: Option<Node>,
109}
110
111/// What [`Workspace::reachable`](crate::Workspace::reachable) found: every
112/// reached node once, in the order the walk reached them, breadth first from
113/// the roots in the order of their nodes.
114#[derive(Debug, Clone, PartialEq, Eq)]
115#[non_exhaustive]
116pub struct Reachability {
117    /// The reached nodes, roots first.
118    pub reached: Vec<Reached>,
119    /// The place of each node in `reached`.
120    at: BTreeMap<Node, usize>,
121}
122
123impl Reachability {
124    /// How `node` was reached, or `None` when it was not.
125    #[must_use]
126    pub fn get(&self, node: Node) -> Option<&Reached> {
127        self.at.get(&node).map(|at| &self.reached[*at])
128    }
129
130    /// True when `node` was reached.
131    #[must_use]
132    pub fn contains(&self, node: Node) -> bool {
133        self.at.contains_key(&node)
134    }
135
136    /// The reached items, in the order of `reached`.
137    pub fn items(&self) -> impl Iterator<Item = ItemId> + '_ {
138        self.reached
139            .iter()
140            .filter_map(|reached| match reached.node {
141                Node::Item(id) => Some(id),
142                Node::Impl(_) => None,
143            })
144    }
145
146    /// The reached impl blocks, in the order of `reached`.
147    pub fn impls(&self) -> impl Iterator<Item = ImplId> + '_ {
148        self.reached
149            .iter()
150            .filter_map(|reached| match reached.node {
151                Node::Impl(id) => Some(id),
152                Node::Item(_) => None,
153            })
154    }
155}
156
157/// Why the reachability of a set of roots could not be given.
158#[derive(Debug)]
159#[non_exhaustive]
160pub enum ReachError {
161    /// A root is past the items of this workspace. An [`ItemId`] is the
162    /// place of an item in the workspace that gave it, so an id of another
163    /// workspace that is not past the items of this one is read as the item
164    /// of this one at that place.
165    UnknownItem(ItemId),
166    /// A root is past the impl blocks of this workspace; as for
167    /// [`ReachError::UnknownItem`], an [`ImplId`] is a place.
168    UnknownImpl(ImplId),
169    /// The text of a file of a reached item could not be read for its paths:
170    /// the thread that lexes it could not start
171    /// ([`LoadErrorKind::Spawn`]), or the text does not lex
172    /// ([`LoadErrorKind::Syntax`]), which a file the load parsed does not do;
173    /// or native format-context storage could not be allocated
174    /// ([`LoadErrorKind::Storage`]).
175    Source(LoadError),
176    /// The walk passed its query-work limit or the item-bytes budget of the load
177    /// ([`Budget::ItemBytes`](crate::Budget::ItemBytes)), counted on from
178    /// what the load holds: a `Budget` load error naming the budget, its
179    /// limit and the file of the runs or the node being held.
180    Budget(LoadError),
181}
182
183impl From<LoadError> for ReachError {
184    fn from(error: LoadError) -> Self {
185        if matches!(error.kind, LoadErrorKind::Budget { .. }) {
186            Self::Budget(error)
187        } else {
188            Self::Source(error)
189        }
190    }
191}
192
193impl fmt::Display for ReachError {
194    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
195        match self {
196            Self::UnknownItem(id) => {
197                write!(f, "item {} is past the items of the workspace", id.index())
198            }
199            Self::UnknownImpl(id) => {
200                write!(
201                    f,
202                    "impl block {} is past the impl blocks of the workspace",
203                    id.index()
204                )
205            }
206            Self::Source(error) => write!(f, "{error}"),
207            Self::Budget(error) => write!(f, "the walk is over budget: {error}"),
208        }
209    }
210}
211
212impl Error for ReachError {
213    fn source(&self) -> Option<&(dyn Error + 'static)> {
214        match self {
215            Self::Source(error) | Self::Budget(error) => Some(error),
216            Self::UnknownItem(_) | Self::UnknownImpl(_) => None,
217        }
218    }
219}
220
221/// How a run is read.
222#[derive(Debug, Clone, Copy, PartialEq, Eq)]
223enum RunKind {
224    /// A path, read as code of the unit's module reads it.
225    Path,
226    /// A path that `Self` starts, read in the impl block or trait that holds
227    /// the unit.
228    SelfPath,
229    /// The name of a method called on `self` (`self.name(` or
230    /// `self.name::<`), read as `Self::name` is.
231    Method,
232}
233
234/// A run of a file: the byte offset of its first identifier, whether a `::`
235/// opens it, how it is read, and its segments: `len` byte ranges of the
236/// file's text from `first` in [`Lexed::segs`], each without a
237/// raw-identifier prefix.
238#[derive(Debug, Clone, Copy, PartialEq, Eq)]
239struct Run {
240    start: usize,
241    first: usize,
242    len: usize,
243    leading_colon: bool,
244    kind: RunKind,
245}
246
247/// What lexing one file gave: its runs in text order, their segments and the
248/// tokens read.
249#[derive(Debug, Default)]
250struct Lexed {
251    runs: Vec<Run>,
252    segs: Vec<(usize, usize)>,
253    tokens: usize,
254    formats: Option<Box<format::Formats>>,
255    format_tokens: usize,
256    format_bytes: usize,
257}
258
259impl Lexed {
260    /// Start a run of one segment and return its place.
261    fn start(
262        &mut self,
263        start: usize,
264        leading_colon: bool,
265        kind: RunKind,
266        seg: (usize, usize),
267    ) -> usize {
268        self.runs.push(Run {
269            start,
270            first: self.segs.len(),
271            len: 1,
272            leading_colon,
273            kind,
274        });
275        self.segs.push(seg);
276        self.runs.len() - 1
277    }
278
279    /// Add a segment to the run at `at`, the last one.
280    fn extend(&mut self, at: usize, seg: (usize, usize)) {
281        self.runs[at].len += 1;
282        self.segs.push(seg);
283    }
284
285    /// Drop the last run and its segments.
286    fn drop_last(&mut self) {
287        if let Some(run) = self.runs.pop() {
288            self.segs.truncate(run.first);
289        }
290    }
291}
292
293/// A lexing failure as plain data, read on the thread that lexed.
294struct LexFailure {
295    message: String,
296    line: usize,
297    column: usize,
298}
299
300/// The words that are no segment of a path in every edition, beside `crate`,
301/// `self` and `super`, which start one, and `Self`, which starts one read in
302/// its impl block or trait: the strict and reserved keywords of edition 2015.
303const KEYWORDS: [&str; 43] = [
304    "abstract", "as", "become", "box", "break", "const", "continue", "do", "else", "enum",
305    "extern", "false", "final", "fn", "for", "if", "impl", "in", "let", "loop", "macro", "match",
306    "mod", "move", "mut", "override", "priv", "pub", "ref", "return", "static", "struct", "trait",
307    "true", "type", "typeof", "unsafe", "unsized", "use", "virtual", "where", "while", "yield",
308];
309
310/// The keywords that edition 2018 adds.
311const KEYWORDS_2018: [&str; 4] = ["async", "await", "dyn", "try"];
312
313/// The keyword that edition 2024 adds.
314const KEYWORD_2024: &str = "gen";
315
316/// True when `word` cannot be a segment of a path at all in `edition`, or
317/// goes on no run (`Self`).
318fn blocked(word: &str, edition: u16) -> bool {
319    word == "Self"
320        || KEYWORDS.contains(&word)
321        || (edition >= 2018 && KEYWORDS_2018.contains(&word))
322        || (edition >= 2024 && word == KEYWORD_2024)
323}
324
325/// The words after which an identifier is the name an item declares, not a
326/// path: `fn helper` declares `helper`. `const` is not one of them: the name
327/// of a constant is a run of one segment before a single `:`, and after
328/// `*const` and `&raw const` comes a path.
329const DECLARES: [&str; 8] = [
330    "fn", "struct", "enum", "union", "trait", "type", "mod", "static",
331];
332
333/// What an identifier is to the scanner.
334#[derive(Debug, Clone, Copy, PartialEq, Eq)]
335enum Word {
336    /// Any other identifier.
337    Plain,
338    /// A keyword after which an identifier is a declared name.
339    Declares,
340    /// `macro_rules`, after whose `!` an identifier is a declared name.
341    MacroRules,
342    /// `self`, after whose `.` a called name is a method of `Self`.
343    SelfValue,
344}
345
346/// A token as the run scanner remembers it.
347#[derive(Debug, Clone, Copy, PartialEq, Eq)]
348enum Tok {
349    /// An identifier, whether it is the last segment of the open run, and
350    /// what it is to the scanner.
351    Ident { in_run: bool, word: Word },
352    /// A punctuation character and whether the next character joins it.
353    Punct { ch: char, joint: bool },
354    /// A literal or a delimited group.
355    Other,
356}
357
358/// The run scanner of one delimiter level: the last three tokens, and
359/// whether a `where` clause is open, from its keyword to the `;` or the
360/// braced group that ends it.
361#[derive(Debug, Default)]
362struct Level {
363    last: [Option<Tok>; 3],
364    in_where: bool,
365}
366
367impl Level {
368    fn push(&mut self, tok: Tok) {
369        self.last = [self.last[1], self.last[2], Some(tok)];
370    }
371
372    /// True when the last two tokens are `::`.
373    fn colons(&self) -> bool {
374        matches!(
375            (self.last[1], self.last[2]),
376            (
377                Some(Tok::Punct {
378                    ch: ':',
379                    joint: true
380                }),
381                Some(Tok::Punct { ch: ':', .. })
382            )
383        )
384    }
385
386    /// True when the last token is a `.` that is not part of `..`.
387    fn single_dot(&self) -> bool {
388        matches!(
389            self.last[2],
390            Some(Tok::Punct {
391                ch: '.',
392                joint: false
393            })
394        ) && !matches!(
395            self.last[1],
396            Some(Tok::Punct {
397                ch: '.',
398                joint: true
399            })
400        )
401    }
402
403    /// True when the next identifier is a name an item declares: it follows
404    /// a declaring keyword, or `macro_rules!`.
405    fn declaring(&self) -> bool {
406        matches!(
407            (self.last[1], self.last[2]),
408            (
409                _,
410                Some(Tok::Ident {
411                    word: Word::Declares,
412                    ..
413                })
414            ) | (
415                Some(Tok::Ident {
416                    word: Word::MacroRules,
417                    ..
418                }),
419                Some(Tok::Punct { ch: '!', .. })
420            )
421        )
422    }
423
424    /// True when the next identifier is a name called after `self.`, if a
425    /// `(` or a `::` follows it.
426    fn after_self_dot(&self) -> bool {
427        self.single_dot()
428            && matches!(
429                self.last[1],
430                Some(Tok::Ident {
431                    word: Word::SelfValue,
432                    ..
433                })
434            )
435    }
436
437    /// What `word`, the next identifier, is to the scanner: a keyword after
438    /// a `'` is a lifetime, as `'static`.
439    fn word(&self, word: &str) -> Word {
440        if matches!(self.last[2], Some(Tok::Punct { ch: '\'', .. })) {
441            Word::Plain
442        } else if DECLARES.contains(&word) {
443            Word::Declares
444        } else if word == "macro_rules" {
445            Word::MacroRules
446        } else if word == "self" {
447            Word::SelfValue
448        } else {
449            Word::Plain
450        }
451    }
452}
453
454/// Where a scanned identifier goes.
455enum Place {
456    /// It goes on the open run.
457    Extend,
458    /// It starts a run, with whether a `::` opens it and how it is read.
459    Start(bool, RunKind),
460    /// It is no segment of a run.
461    Skip,
462}
463
464/// The open run: its place, and whether each of its segments is `self` or
465/// `super`.
466#[derive(Debug, Clone, Copy)]
467struct Open {
468    at: usize,
469    supers: bool,
470}
471
472/// Decide where the identifier `word` goes after the tokens of `level` in
473/// `edition`, `supers` telling whether the open run, when there is one, is
474/// made of `self` and `super` alone. A raw identifier (`raw`) is never a
475/// keyword.
476fn place(level: &Level, word: &str, raw: bool, supers: bool, edition: u16) -> Place {
477    let blocked = |word: &str| !raw && blocked(word, edition);
478    let path_word = !raw && matches!(word, "crate" | "self" | "super");
479    if level.colons() {
480        return match level.last[0] {
481            Some(Tok::Ident { in_run: true, .. }) => {
482                if blocked(word) || (path_word && !(word == "super" && supers)) {
483                    Place::Skip
484                } else {
485                    Place::Extend
486                }
487            }
488            Some(Tok::Ident { in_run: false, .. } | Tok::Punct { ch: '>', .. }) => Place::Skip,
489            _ if blocked(word) || path_word => Place::Skip,
490            _ => Place::Start(true, RunKind::Path),
491        };
492    }
493    let self_type = !raw && word == "Self";
494    if (blocked(word) && !self_type) || level.single_dot() || level.declaring() {
495        return Place::Skip;
496    }
497    match level.last[2] {
498        Some(Tok::Punct { ch: '\'', .. }) => Place::Skip,
499        Some(Tok::Punct { ch: '$', .. }) if word != "crate" => Place::Skip,
500        _ if self_type => Place::Start(false, RunKind::SelfPath),
501        _ => Place::Start(false, RunKind::Path),
502    }
503}
504
505/// The runs of `stream`, lexed from `text` past its first `base` bytes, so
506/// that its byte offsets plus `base` are those of `text`, in text order, and
507/// the tokens read, with the keywords of `edition`. The levels of delimiters
508/// are walked on an explicit stack.
509///
510/// A run of one segment directly followed by a single `:` is a name being
511/// bound or a field, not a path (`helper: u8`, `S { helper: 1 }`), and is
512/// dropped, except in a `where` clause, where it is the type a bound is put
513/// on (`where Helper: Clone`); a `::` after it goes on with it. A name after
514/// `self.` that a `(` or a `::` follows is a method called on `self`.
515///
516/// An identifier is a segment only where `text` spells it. The lexer reads a
517/// doc comment as the attribute `#[doc = "..."]` and gives its `doc` the span
518/// of the whole comment, so that `doc` is written nowhere: it starts no run,
519/// and no byte of the comment is read as a segment.
520fn scan(stream: TokenStream, text: &str, base: usize, edition: u16) -> Lexed {
521    let mut lexed = Lexed::default();
522    let mut stack: Vec<(proc_macro2::token_stream::IntoIter, Level)> =
523        vec![(stream.into_iter(), Level::default())];
524    let mut open: Option<Open> = None;
525    // The run of one segment that the `:` just read follows, if any, and
526    // whether that `:` joins the next character.
527    let mut colon: Option<(usize, bool)> = None;
528    // The name after `self.` just read, where it starts and its segment,
529    // until the next token tells whether it is called.
530    let mut method: Option<(usize, (usize, usize))> = None;
531    while let Some((tokens, level)) = stack.last_mut() {
532        let tree = tokens.next();
533        if let Some((start, seg)) = method.take() {
534            let called = match &tree {
535                Some(TokenTree::Group(group)) => group.delimiter() == Delimiter::Parenthesis,
536                Some(TokenTree::Punct(punct)) => {
537                    punct.as_char() == ':' && punct.spacing() == Spacing::Joint
538                }
539                _ => false,
540            };
541            if called {
542                lexed.start(start, false, RunKind::Method, seg);
543            }
544        }
545        let next_colon = matches!(&tree, Some(TokenTree::Punct(punct)) if punct.as_char() == ':');
546        if let Some((at, joint)) = colon.take()
547            && !(joint && next_colon)
548            && lexed.runs.len() == at + 1
549        {
550            lexed.drop_last();
551            open = None;
552        }
553        let Some(tree) = tree else {
554            stack.pop();
555            open = None;
556            if let Some((_, outer)) = stack.last_mut() {
557                outer.push(Tok::Other);
558            }
559            continue;
560        };
561        lexed.tokens += 1;
562        match tree {
563            TokenTree::Group(group) => {
564                open = None;
565                if group.delimiter() == Delimiter::Brace {
566                    level.in_where = false;
567                }
568                stack.push((group.stream().into_iter(), Level::default()));
569            }
570            TokenTree::Ident(ident) => {
571                let range = ident.span().byte_range();
572                let span = (base + range.start, base + range.end);
573                // A span's ends are character boundaries of the lexed text:
574                // the lexer counts characters and gives their byte offsets.
575                if ident == text[span.0..span.1] {
576                    open = scan_ident(&mut lexed, level, open, &ident, span, edition, &mut method);
577                } else {
578                    open = None;
579                    level.push(Tok::Ident {
580                        in_run: false,
581                        word: Word::Plain,
582                    });
583                }
584            }
585            TokenTree::Punct(punct) => {
586                let ch = punct.as_char();
587                let joint = punct.spacing() == Spacing::Joint;
588                if ch == ':' {
589                    // The first `:` of a pair, or a single one: a run of one
590                    // segment before it is dropped unless a second follows,
591                    // or a `where` clause is open.
592                    let first = !matches!(
593                        level.last[2],
594                        Some(Tok::Punct {
595                            ch: ':',
596                            joint: true
597                        })
598                    );
599                    if first
600                        && !level.in_where
601                        && let (Some(run), Some(Tok::Ident { in_run: true, .. })) =
602                            (open, level.last[2])
603                        && lexed.runs[run.at].len == 1
604                    {
605                        colon = Some((run.at, joint));
606                    }
607                } else {
608                    // A run stays open only across the `::` that may go on
609                    // with it.
610                    open = None;
611                    if ch == ';' {
612                        level.in_where = false;
613                    }
614                }
615                level.push(Tok::Punct { ch, joint });
616            }
617            TokenTree::Literal(_) => {
618                open = None;
619                level.push(Tok::Other);
620            }
621        }
622    }
623    lexed
624}
625
626/// Scan the identifier `ident`, written in the text at the byte range
627/// `span`, after the tokens of `level`, with the open run `open`, and return
628/// the open run after it. A name after `self.` is kept in `method` until the
629/// next token.
630fn scan_ident(
631    lexed: &mut Lexed,
632    level: &mut Level,
633    open: Option<Open>,
634    ident: &proc_macro2::Ident,
635    span: (usize, usize),
636    edition: u16,
637    method: &mut Option<(usize, (usize, usize))>,
638) -> Option<Open> {
639    let text = ident.to_string();
640    // A raw identifier is never a keyword.
641    let (word, raw) = match text.strip_prefix("r#") {
642        Some(word) => (word, true),
643        None => (text.as_str(), false),
644    };
645    let kind = if raw { Word::Plain } else { level.word(word) };
646    let (start, end) = span;
647    let seg = (end - word.len(), end);
648    if !raw && word == "where" {
649        level.in_where = true;
650    }
651    if level.after_self_dot() {
652        *method = Some((start, seg));
653    }
654    let path_word = !raw && matches!(word, "self" | "super");
655    let supers = open.is_some_and(|run| run.supers);
656    let (in_run, open) = match place(level, word, raw, supers, edition) {
657        Place::Extend => {
658            let open = open.map(|run| {
659                lexed.extend(run.at, seg);
660                Open {
661                    at: run.at,
662                    supers: run.supers && path_word,
663                }
664            });
665            (true, open)
666        }
667        Place::Start(leading_colon, kind) => {
668            let at = lexed.start(start, leading_colon, kind, seg);
669            (
670                true,
671                Some(Open {
672                    at,
673                    supers: path_word,
674                }),
675            )
676        }
677        Place::Skip => (false, None),
678    };
679    level.push(Tok::Ident { in_run, word: kind });
680    open
681}
682
683/// Lex `text` with the keywords of `edition` and scan its runs. A byte-order
684/// mark and a first line that is a shebang, as `syn` reads them, are left
685/// out, and offsets stay those of `text`.
686fn lex_text(text: &str, edition: u16) -> Result<Lexed, LexFailure> {
687    let mut base = 0;
688    let mut body = text;
689    if let Some(rest) = body.strip_prefix('\u{feff}') {
690        base += '\u{feff}'.len_utf8();
691        body = rest;
692    }
693    if let Some(after) = body.strip_prefix("#!")
694        && !after.trim_start().starts_with('[')
695    {
696        let cut = body.find('\n').unwrap_or(body.len());
697        base += cut;
698        body = &body[cut..];
699    }
700    let stream = TokenStream::from_str(body).map_err(|error| {
701        let start = error.span().start();
702        LexFailure {
703            message: error.to_string(),
704            line: start.line + text[..base].matches('\n').count(),
705            column: start.column + 1,
706        }
707    })?;
708    let mut lexed = scan(stream.clone(), text, base, edition);
709    (lexed.formats, lexed.format_tokens, lexed.format_bytes) = format::scan(stream, text, base);
710    lexed.runs.shrink_to_fit();
711    lexed.segs.shrink_to_fit();
712    Ok(lexed)
713}
714
715/// Lex the text of `file` on a thread of its own, whose span data is dropped
716/// with it, with the stack of the parse thread.
717fn lex(file: &RelPath, text: &str, edition: u16) -> Result<Lexed, ReachError> {
718    thread::scope(|scope| {
719        let worker = thread::Builder::new()
720            .name(file.to_string())
721            .stack_size(PARSE_STACK_BYTES)
722            .spawn_scoped(scope, move || lex_text(text, edition))
723            .map_err(|source| {
724                ReachError::Source(LoadError::new(file, None, LoadErrorKind::Spawn(source)))
725            })?;
726        match worker.join() {
727            Ok(Ok(lexed)) => Ok(lexed),
728            Ok(Err(failure)) => Err(ReachError::Source(LoadError::new(
729                file,
730                Some(failure.line),
731                LoadErrorKind::Syntax {
732                    message: failure.message,
733                    column: failure.column,
734                },
735            ))),
736            Err(payload) => panic::resume_unwind(payload),
737        }
738    })
739}
740
741/// The runs of one file and their segments, each run given to the innermost
742/// unit whose span holds its start: an item or an impl block, by its span.
743#[derive(Debug, Default)]
744struct FileRuns {
745    runs: Vec<Run>,
746    segs: Vec<(usize, usize)>,
747    by_unit: BTreeMap<(usize, usize), Vec<usize>>,
748    formats: Option<Box<format::Formats>>,
749    calls_by_unit: BTreeMap<(usize, usize), Vec<usize>>,
750}
751
752/// Give each run, in text order, to the innermost of `units` (spans as
753/// `(start, end)`, nested or apart) that holds its start.
754fn place_runs(runs: &[Run], units: Vec<(usize, usize)>) -> BTreeMap<(usize, usize), Vec<usize>> {
755    place_starts(
756        runs.iter().enumerate().map(|(at, run)| (at, run.start)),
757        units,
758        Work::ReachUnits,
759    )
760}
761
762fn place_starts(
763    starts: impl Iterator<Item = (usize, usize)>,
764    mut units: Vec<(usize, usize)>,
765    kind: Work,
766) -> BTreeMap<(usize, usize), Vec<usize>> {
767    // Outer units first where two start at one byte.
768    units.sort_by(|a, b| a.0.cmp(&b.0).then(b.1.cmp(&a.1)));
769    units.dedup();
770    let mut by_unit: BTreeMap<(usize, usize), Vec<usize>> = BTreeMap::new();
771    let mut open: Vec<(usize, usize)> = Vec::new();
772    let mut next = 0;
773    for (position, start) in starts {
774        while let Some(&unit) = units.get(next).filter(|unit| unit.0 <= start) {
775            work::add(kind, 1);
776            while open.last().is_some_and(|top| top.1 <= unit.0) {
777                work::add(kind, 1);
778                open.pop();
779            }
780            open.push(unit);
781            next += 1;
782        }
783        while open.last().is_some_and(|top| top.1 <= start) {
784            work::add(kind, 1);
785            open.pop();
786        }
787        if let Some(unit) = open.last() {
788            work::add(kind, 1);
789            by_unit.entry(*unit).or_default().push(position);
790        }
791    }
792    for positions in by_unit.values_mut() {
793        positions.shrink_to_fit();
794    }
795    by_unit
796}
797
798/// What `Self` stands for in a unit: the impl block or the trait that holds
799/// it.
800#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
801enum Owner {
802    /// A member of the impl block, or the block's own tokens.
803    Block(ImplId),
804    /// A member of the trait, or the trait's own tokens.
805    Trait(ItemId),
806}
807
808/// Where the runs of a unit are read: as code of a module, test code when
809/// the flag is set, or in the impl block or trait that `Self` stands for.
810#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
811enum Ctx {
812    Module(usize, bool),
813    Value(usize, bool),
814    Owner(Owner),
815}
816
817/// Where the runs of an item are read: the module of its paths (its own
818/// module, the module of its impl block for a member of one, the module of
819/// its trait for a member of a trait), and what `Self` stands for in it.
820#[derive(Debug, Clone, Copy, Default)]
821pub(crate) struct Home {
822    module: Option<usize>,
823    owner: Option<Owner>,
824}
825
826impl Home {
827    pub(crate) const fn module(self) -> Option<usize> {
828        self.module
829    }
830}
831
832/// Populate the shared source-owned reading context of every indexed item.
833pub(crate) fn fill_homes(index: &Index, homes: &mut [Home], lexical: bool) {
834    for (module, entry) in index.modules.iter().enumerate() {
835        for id in &entry.defs {
836            work::add(Work::ReachSteps, 1);
837            homes[id.0].module = Some(module);
838        }
839    }
840    for (module, id) in &index.root_items {
841        work::add(Work::ReachSteps, 1);
842        homes[id.0].module = Some(*module);
843    }
844    if lexical {
845        for (id, module) in &index.macro_modules {
846            work::add(Work::ReachSteps, 1);
847            homes[id.0].module = Some(*module);
848        }
849    }
850    for block in &index.impl_blocks {
851        work::add(Work::ReachSteps, 1);
852        for member in &block.members {
853            work::add(Work::ReachSteps, 1);
854            homes[member.0] = Home {
855                module: Some(block.module_index),
856                owner: Some(Owner::Block(block.id)),
857            };
858        }
859    }
860    for (owner, members) in &index.assoc {
861        if index.items[owner.0].kind != SymbolKind::Trait {
862            continue;
863        }
864        homes[owner.0].owner = Some(Owner::Trait(*owner));
865        for id in members.values().flatten() {
866            work::add(Work::ReachSteps, 1);
867            homes[id.0] = Home {
868                module: homes[owner.0].module,
869                owner: Some(Owner::Trait(*owner)),
870            };
871        }
872    }
873}
874
875/// What the walk reads of an impl block for the paths that `Self` starts:
876/// its members by name when no type keys it, and the traits of the walk
877/// that its trait path names from its module.
878#[derive(Debug, Default)]
879struct BlockNames<'a> {
880    members: BTreeMap<&'a str, Vec<ItemId>>,
881    traits: Vec<ItemId>,
882}
883
884/// A unit whose own runs are read: the file and the line it is charged at,
885/// its span, where its own tokens end, its module and test flag and its
886/// owner.
887struct Unit<'u> {
888    file: &'u RelPath,
889    line: usize,
890    span: (usize, usize),
891    before: usize,
892    module: usize,
893    test: bool,
894    owner: Option<Owner>,
895}
896
897/// An entry of the queue of the walk: a node, the edge it is reached by and
898/// the node that edge comes from.
899type Queued = (Node, Edge, Option<Node>);
900
901/// What a map of lists of impl blocks holds at most.
902fn lists_bytes<K>(map: &BTreeMap<K, Vec<ImplId>>) -> usize {
903    btree_map::<K, Vec<ImplId>>()
904        + map
905            .values()
906            .map(|list| btree_entry::<K, Vec<ImplId>>() + list.capacity() * size_of::<ImplId>())
907            .sum::<usize>()
908}
909
910/// The members called `name` of the type or trait `owner`.
911fn members_named<'a>(index: &'a Index, owner: ItemId, name: &str) -> &'a [ItemId] {
912    work::add(Work::ReachSteps, 1);
913    index
914        .assoc
915        .get(&owner)
916        .and_then(|members| members.get(name))
917        .map_or(&[], Vec::as_slice)
918}
919
920/// The segments of a trait path as an impl block writes it without spaces,
921/// and whether `::` opens it: its generic arguments left out; `None` for a
922/// negative impl (`!Sync`) or a path that is not one of identifiers.
923fn trait_segments(written: &str) -> Option<(bool, Vec<String>)> {
924    if written.starts_with('!') {
925        return None;
926    }
927    let path = &written[..written.find(['<', '(']).unwrap_or(written.len())];
928    let (leading_colon, path) = match path.strip_prefix("::") {
929        Some(rest) => (true, rest),
930        None => (false, path),
931    };
932    let segs: Vec<String> = path
933        .split("::")
934        .map(|seg| seg.strip_prefix("r#").unwrap_or(seg).to_owned())
935        .collect();
936    segs.iter()
937        .all(|seg| !seg.is_empty() && seg.chars().all(|c| c == '_' || c.is_alphanumeric()))
938        .then_some((leading_colon, segs))
939}
940
941/// The walk: the index, the files, the tables built for it and what it has
942/// found.
943struct Walk<'a> {
944    index: &'a Index,
945    files: &'a BTreeMap<RelPath, SourceFile>,
946    meter: &'a Meter,
947    /// Where the runs of each item are read.
948    homes: Vec<Home>,
949    /// The impl blocks of each struct, enum and union.
950    blocks_of_type: BTreeMap<ItemId, Vec<ImplId>>,
951    /// The impl blocks each module holds.
952    blocks_of_module: BTreeMap<usize, Vec<ImplId>>,
953    /// The block modules each item holds a declaration of, by the item whose
954    /// span is the innermost to hold it.
955    block_modules_of: BTreeMap<ItemId, Vec<usize>>,
956    /// The crate root items.
957    roots: BTreeSet<ItemId>,
958    /// The runs of each file lexed so far, with the edition whose keywords
959    /// were used. One physical file can be shared by packages of different editions.
960    files_runs: BTreeMap<(RelPath, u16), FileRuns>,
961    /// The texts of the runs resolved so far, by the place they were read
962    /// in. What a run named was given to the walk when it was resolved, so a
963    /// run of the same text read in the same place again gives nothing.
964    seen: BTreeMap<Ctx, BTreeSet<Box<str>>>,
965    /// What the walk read of each impl block for the paths `Self` starts.
966    blocks: BTreeMap<ImplId, BlockNames<'a>>,
967    format_identity: Option<format::Resolver>,
968}
969
970impl<'a> Walk<'a> {
971    /// The tables of the walk, charged to `meter` at `file` and `line`.
972    fn new(
973        index: &'a Index,
974        files: &'a BTreeMap<RelPath, SourceFile>,
975        meter: &'a Meter,
976        (file, line): (&RelPath, usize),
977    ) -> Result<Self, ReachError> {
978        let mut homes = vec![Home::default(); index.items.len()];
979        // Reachability retains its documented export-placement approximation;
980        // lexical source observations retain actual macro declaration modules.
981        fill_homes(index, &mut homes, false);
982        let mut blocks_of_type: BTreeMap<ItemId, Vec<ImplId>> = BTreeMap::new();
983        let mut blocks_of_module: BTreeMap<usize, Vec<ImplId>> = BTreeMap::new();
984        for block in &index.impl_blocks {
985            blocks_of_module
986                .entry(block.module_index)
987                .or_default()
988                .push(block.id);
989            for ty in &block.self_items {
990                work::add(Work::ReachSteps, 1);
991                blocks_of_type.entry(*ty).or_default().push(block.id);
992            }
993        }
994        let mut block_modules_of: BTreeMap<ItemId, Vec<usize>> = BTreeMap::new();
995        if !index.block_modules.is_empty() {
996            let mut in_module: BTreeMap<usize, Vec<ItemId>> = BTreeMap::new();
997            for item in &index.items {
998                if let Some(module) = homes[item.id.0].module {
999                    in_module.entry(module).or_default().push(item.id);
1000                }
1001            }
1002            for site in &index.block_modules {
1003                work::add(
1004                    Work::ReachSteps,
1005                    1 + in_module.get(&site.parent).map_or(0, Vec::len),
1006                );
1007                let owner = in_module
1008                    .get(&site.parent)
1009                    .into_iter()
1010                    .flatten()
1011                    .map(|id| &index.items[id.0])
1012                    .filter(|item| {
1013                        item.file == site.file
1014                            && item.span.start_byte <= site.span.0
1015                            && site.span.1 <= item.span.end_byte
1016                    })
1017                    .min_by_key(|item| item.span.end_byte - item.span.start_byte);
1018                if let Some(owner) = owner {
1019                    block_modules_of
1020                        .entry(owner.id)
1021                        .or_default()
1022                        .push(site.module);
1023                }
1024            }
1025        }
1026        let roots: BTreeSet<ItemId> = index.root_items.values().copied().collect();
1027        let held = homes.capacity() * size_of::<Home>()
1028            + lists_bytes(&blocks_of_type)
1029            + lists_bytes(&blocks_of_module)
1030            + btree_map::<ItemId, Vec<usize>>()
1031            + block_modules_of
1032                .values()
1033                .map(|list| {
1034                    btree_entry::<ItemId, Vec<usize>>() + list.capacity() * size_of::<usize>()
1035                })
1036                .sum::<usize>()
1037            + btree_map::<ItemId, ()>()
1038            + roots.len() * btree_entry::<ItemId, ()>()
1039            + btree_map::<(RelPath, u16), FileRuns>()
1040            + btree_map::<Ctx, BTreeSet<Box<str>>>()
1041            + btree_map::<ImplId, BlockNames<'_>>();
1042        meter
1043            .items(held, file, Some(line))
1044            .map_err(ReachError::Budget)?;
1045        Ok(Self {
1046            index,
1047            files,
1048            meter,
1049            homes,
1050            blocks_of_type,
1051            blocks_of_module,
1052            block_modules_of,
1053            roots,
1054            files_runs: BTreeMap::new(),
1055            seen: BTreeMap::new(),
1056            blocks: BTreeMap::new(),
1057            format_identity: None,
1058        })
1059    }
1060
1061    /// Lex and place the runs of `file` the first time they are asked, with
1062    /// the keywords of the edition of the package of `module`, and charge
1063    /// what they hold.
1064    fn load(&mut self, file: &RelPath, module: usize) -> Result<(RelPath, u16), ReachError> {
1065        let key = (file.clone(), self.index.edition(module));
1066        if self.files_runs.contains_key(&key) {
1067            return Ok(key);
1068        }
1069        let text = self
1070            .files
1071            .get(file)
1072            .map_or("", |source| source.text.as_str());
1073        let lexed = lex(file, text, key.1)?;
1074        work::add(Work::ReachTokens, lexed.tokens);
1075        work::add(Work::ReachFormatTokens, lexed.format_tokens);
1076        work::add(Work::ReachFormatBytes, lexed.format_bytes);
1077        let mut units: Vec<(usize, usize)> = self
1078            .index
1079            .by_file
1080            .get(file)
1081            .into_iter()
1082            .flatten()
1083            .filter(|id| !self.roots.contains(id))
1084            .map(|id| {
1085                let span = &self.index.items[id.0].span;
1086                (span.start_byte, span.end_byte)
1087            })
1088            .collect();
1089        let first = self
1090            .index
1091            .impl_blocks
1092            .partition_point(|block| block.file < *file);
1093        units.extend(
1094            self.index.impl_blocks[first..]
1095                .iter()
1096                .take_while(|block| block.file == *file)
1097                .map(|block| (block.span.start_byte, block.span.end_byte)),
1098        );
1099        let calls_by_unit = lexed
1100            .formats
1101            .as_ref()
1102            .map_or_else(BTreeMap::new, |formats| {
1103                place_starts(
1104                    formats
1105                        .calls
1106                        .iter()
1107                        .enumerate()
1108                        .map(|(at, call)| (at, call.start)),
1109                    units.clone(),
1110                    Work::ReachFormatTokens,
1111                )
1112            });
1113        let by_unit = place_runs(&lexed.runs, units);
1114        let mut held = btree_entry::<(RelPath, u16), FileRuns>()
1115            + lexed.runs.capacity() * size_of::<Run>()
1116            + lexed.segs.capacity() * size_of::<(usize, usize)>();
1117        if !by_unit.is_empty() {
1118            held += btree_map::<(usize, usize), Vec<usize>>();
1119        }
1120        for positions in by_unit.values() {
1121            held += btree_entry::<(usize, usize), Vec<usize>>()
1122                + positions.capacity() * size_of::<usize>();
1123        }
1124        if let Some(formats) = &lexed.formats {
1125            held += formats.retained_bytes();
1126        }
1127        if !calls_by_unit.is_empty() {
1128            held += btree_map::<(usize, usize), Vec<usize>>();
1129            for positions in calls_by_unit.values() {
1130                held += btree_entry::<(usize, usize), Vec<usize>>()
1131                    + positions.capacity() * size_of::<usize>();
1132            }
1133        }
1134        if lexed.formats.is_some() && self.format_identity.is_none() {
1135            let identity = format::Resolver::new(self.index, self.files, self.meter, file)?;
1136            self.format_identity = Some(identity);
1137        }
1138        self.meter
1139            .items(held, file, None)
1140            .map_err(ReachError::Budget)?;
1141        self.files_runs.insert(
1142            key.clone(),
1143            FileRuns {
1144                runs: lexed.runs,
1145                segs: lexed.segs,
1146                by_unit,
1147                formats: lexed.formats,
1148                calls_by_unit,
1149            },
1150        );
1151        Ok(key)
1152    }
1153
1154    /// The items the own tokens of `unit` name: the runs of its file given
1155    /// to its span that start before where its own tokens end, each read in
1156    /// its place the first time its text is read there.
1157    fn references(&mut self, unit: &Unit<'_>) -> Result<Vec<ItemId>, ReachError> {
1158        let key = self.load(unit.file, unit.module)?;
1159        let index = self.index;
1160        let text = self
1161            .files
1162            .get(unit.file)
1163            .map_or("", |source| source.text.as_str());
1164        let runs = &self.files_runs[&key];
1165        let mut out = Vec::new();
1166        let suppressed = format_references(
1167            index,
1168            self.meter,
1169            self.format_identity.as_ref(),
1170            &mut self.seen,
1171            unit,
1172            runs,
1173            &mut out,
1174        )?;
1175        for position in runs.by_unit.get(&unit.span).into_iter().flatten() {
1176            let run = runs.runs[*position];
1177            if run.start >= unit.before {
1178                break;
1179            }
1180            if suppressed.binary_search(&run.start).is_ok() {
1181                continue;
1182            }
1183            work::add(Work::ReachSteps, 1);
1184            let segs = &runs.segs[run.first..run.first + run.len];
1185            let word = |at: usize| &text[segs[at].0..segs[at].1];
1186            let (ctx, key) = match (run.kind, unit.owner) {
1187                (RunKind::Path, _) => {
1188                    let mut key = String::from(if run.leading_colon { "::" } else { "" });
1189                    for at in 0..segs.len() {
1190                        if at > 0 {
1191                            key.push_str("::");
1192                        }
1193                        key.push_str(word(at));
1194                    }
1195                    (Ctx::Module(unit.module, unit.test), key)
1196                }
1197                // Only the name after `Self` is read.
1198                (RunKind::SelfPath, Some(owner)) if run.len > 1 => {
1199                    (Ctx::Owner(owner), format!("Self::{}", word(1)))
1200                }
1201                (RunKind::Method, Some(owner)) => (Ctx::Owner(owner), format!(".{}", word(0))),
1202                (RunKind::SelfPath | RunKind::Method, _) => continue,
1203            };
1204            let mut held = btree_entry::<Box<str>, ()>() + key.len();
1205            if !self.seen.contains_key(&ctx) {
1206                held += btree_entry::<Ctx, BTreeSet<Box<str>>>() + btree_map::<Box<str>, ()>();
1207            }
1208            let seen = self.seen.entry(ctx).or_default();
1209            if seen.contains(key.as_str()) {
1210                continue;
1211            }
1212            self.meter
1213                .items(held, unit.file, Some(unit.line))
1214                .map_err(ReachError::Budget)?;
1215            seen.insert(key.into_boxed_str());
1216            work::add(Work::ReachPaths, 1);
1217            match (run.kind, ctx) {
1218                (RunKind::Path, _) => {
1219                    let words: Vec<String> =
1220                        (0..segs.len()).map(|at| word(at).to_owned()).collect();
1221                    out.extend(index.reach_run(
1222                        unit.module,
1223                        &words,
1224                        run.leading_colon,
1225                        unit.test,
1226                        Steps::QueryItems {
1227                            meter: self.meter,
1228                            file: unit.file,
1229                            line: Some(unit.line),
1230                        },
1231                    )?);
1232                }
1233                (kind, Ctx::Owner(owner)) => {
1234                    let (name, variant) = match kind {
1235                        RunKind::SelfPath => (word(1), true),
1236                        _ => (word(0), false),
1237                    };
1238                    let names = owner_names(
1239                        index,
1240                        self.meter,
1241                        &mut self.blocks,
1242                        owner,
1243                        (name, variant),
1244                        unit,
1245                    )?;
1246                    out.extend(names);
1247                }
1248                (_, Ctx::Module(..) | Ctx::Value(..)) => {}
1249            }
1250        }
1251        Ok(out)
1252    }
1253
1254    /// The nodes `node`, reached by `edge`, leads to, with their edges, and
1255    /// whether it opens its module (a module reached from a root by contains
1256    /// alone). `first` is true the first time the node is reached; a module
1257    /// reached again by contains is opened then.
1258    fn next(
1259        &mut self,
1260        node: Node,
1261        edge: Edge,
1262        first: bool,
1263        opened: &mut BTreeSet<ItemId>,
1264    ) -> Result<Vec<(Node, Edge)>, ReachError> {
1265        let index = self.index;
1266        let mut out = Vec::new();
1267        match node {
1268            Node::Item(id) => {
1269                let item = &index.items[id.0];
1270                if self.roots.contains(&id) {
1271                    return Ok(out);
1272                }
1273                match item.kind {
1274                    SymbolKind::Mod => {
1275                        if matches!(edge, Edge::Root | Edge::Contains)
1276                            && opened.insert(id)
1277                            && let Some(module) = index.module_of.get(&id)
1278                        {
1279                            for child in &index.modules[*module].defs {
1280                                work::add(Work::ReachSteps, 1);
1281                                out.push((Node::Item(*child), Edge::Contains));
1282                            }
1283                            for block in self.blocks_of_module.get(module).into_iter().flatten() {
1284                                work::add(Work::ReachSteps, 1);
1285                                out.push((Node::Impl(*block), Edge::Contains));
1286                            }
1287                        }
1288                    }
1289                    SymbolKind::Struct
1290                    | SymbolKind::Enum
1291                    | SymbolKind::Union
1292                    | SymbolKind::Trait
1293                        if first =>
1294                    {
1295                        for member in index.assoc.get(&id).into_iter().flat_map(|m| m.values()) {
1296                            for child in member {
1297                                work::add(Work::ReachSteps, 1);
1298                                out.push((Node::Item(*child), Edge::Contains));
1299                            }
1300                        }
1301                        for block in self.blocks_of_type.get(&id).into_iter().flatten() {
1302                            work::add(Work::ReachSteps, 1);
1303                            out.push((Node::Impl(*block), Edge::ImplOf));
1304                        }
1305                    }
1306                    _ => {}
1307                }
1308                if first {
1309                    // A module declared inside the item's body is reached
1310                    // with the item, as a module in an item list is with the
1311                    // module that holds it.
1312                    for &module in self.block_modules_of.get(&id).into_iter().flatten() {
1313                        for child in &index.modules[module].defs {
1314                            work::add(Work::ReachSteps, 1);
1315                            out.push((Node::Item(*child), Edge::Contains));
1316                        }
1317                        for block in self.blocks_of_module.get(&module).into_iter().flatten() {
1318                            work::add(Work::ReachSteps, 1);
1319                            out.push((Node::Impl(*block), Edge::Contains));
1320                        }
1321                    }
1322                }
1323                let home = self.homes[id.0];
1324                if first && let Some(module) = home.module {
1325                    // A module's own tokens end where its body starts.
1326                    let before = match (item.kind, &item.body) {
1327                        (SymbolKind::Mod, Some(body)) => body.start_byte,
1328                        _ => usize::MAX,
1329                    };
1330                    let unit = Unit {
1331                        file: &item.file,
1332                        line: item.name_line,
1333                        span: (item.span.start_byte, item.span.end_byte),
1334                        before,
1335                        module,
1336                        test: item.test != TestRole::None,
1337                        owner: home.owner,
1338                    };
1339                    for found in self.references(&unit)? {
1340                        work::add(Work::ReachSteps, 1);
1341                        out.push((Node::Item(found), Edge::References));
1342                    }
1343                }
1344            }
1345            Node::Impl(id) => {
1346                if first {
1347                    let block = &index.impl_blocks[id.0];
1348                    for member in &block.members {
1349                        work::add(Work::ReachSteps, 1);
1350                        out.push((Node::Item(*member), Edge::ImplOf));
1351                    }
1352                    let unit = Unit {
1353                        file: &block.file,
1354                        line: block.line,
1355                        span: (block.span.start_byte, block.span.end_byte),
1356                        before: usize::MAX,
1357                        module: block.module_index,
1358                        test: block.test != TestRole::None,
1359                        owner: Some(Owner::Block(id)),
1360                    };
1361                    for found in self.references(&unit)? {
1362                        work::add(Work::ReachSteps, 1);
1363                        out.push((Node::Item(found), Edge::References));
1364                    }
1365                }
1366            }
1367        }
1368        Ok(out)
1369    }
1370}
1371
1372fn format_references(
1373    index: &Index,
1374    meter: &Meter,
1375    identity: Option<&format::Resolver>,
1376    seen_paths: &mut BTreeMap<Ctx, BTreeSet<Box<str>>>,
1377    unit: &Unit<'_>,
1378    runs: &FileRuns,
1379    out: &mut Vec<ItemId>,
1380) -> Result<Vec<usize>, ReachError> {
1381    let mut suppressed = Vec::new();
1382    if let (Some(formats), Some(identity)) = (&runs.formats, identity) {
1383        for &position in runs.calls_by_unit.get(&unit.span).into_iter().flatten() {
1384            let call = &formats.calls[position];
1385            if call.start >= unit.before {
1386                break;
1387            }
1388            if !identity.standard(
1389                formats,
1390                call,
1391                index,
1392                unit,
1393                Steps::QueryItems {
1394                    meter,
1395                    file: unit.file,
1396                    line: Some(unit.line),
1397                },
1398            )? {
1399                continue;
1400            }
1401            let Some(arguments) = &call.arguments else {
1402                continue;
1403            };
1404            let arguments = arguments
1405                .as_ref()
1406                .map_err(|refusal| ReachError::Source(refusal.error(unit.file)))?;
1407            suppressed.extend_from_slice(&arguments.bindings);
1408            for name in &arguments.captures {
1409                let ctx = Ctx::Value(unit.module, unit.test);
1410                let mut held = btree_entry::<Box<str>, ()>() + name.len();
1411                if !seen_paths.contains_key(&ctx) {
1412                    held += btree_entry::<Ctx, BTreeSet<Box<str>>>() + btree_map::<Box<str>, ()>();
1413                }
1414                let seen = seen_paths.entry(ctx).or_default();
1415                if seen.contains(name.as_ref()) {
1416                    continue;
1417                }
1418                meter
1419                    .items(held, unit.file, Some(unit.line))
1420                    .map_err(ReachError::Budget)?;
1421                seen.insert(name.clone());
1422                work::add(Work::ReachPaths, 1);
1423                out.extend(index.reach_value(
1424                    unit.module,
1425                    name,
1426                    unit.test,
1427                    Steps::QueryItems {
1428                        meter,
1429                        file: unit.file,
1430                        line: Some(unit.line),
1431                    },
1432                )?);
1433            }
1434        }
1435    }
1436    suppressed.sort_unstable();
1437    Ok(suppressed)
1438}
1439
1440/// The items that `Self::name` (`variant`) or `self.name(` names in
1441/// `owner`: in a trait, its members called `name`; in an impl block, the
1442/// members called `name` of the types its self type keys (every block of
1443/// them, the block itself among them) or, when no type keys it, of the block
1444/// itself, and the members called `name` of the trait it implements. A
1445/// `Self::name` that names none of them in a block on an enum names the enum:
1446/// `name` is a variant, as `E::V` names `E`.
1447fn owner_names<'a>(
1448    index: &'a Index,
1449    meter: &Meter,
1450    blocks: &mut BTreeMap<ImplId, BlockNames<'a>>,
1451    owner: Owner,
1452    (name, variant): (&str, bool),
1453    unit: &Unit<'_>,
1454) -> Result<Vec<ItemId>, ReachError> {
1455    let mut out: Vec<ItemId> = Vec::new();
1456    match owner {
1457        Owner::Trait(id) => out.extend_from_slice(members_named(index, id, name)),
1458        Owner::Block(id) => {
1459            let block = &index.impl_blocks[id.0];
1460            let names = block_names(index, meter, blocks, id, unit)?;
1461            for ty in &block.self_items {
1462                out.extend_from_slice(members_named(index, *ty, name));
1463            }
1464            if let Some(members) = names.members.get(name) {
1465                out.extend_from_slice(members);
1466            }
1467            for found in &names.traits {
1468                out.extend_from_slice(members_named(index, *found, name));
1469            }
1470            if variant && out.is_empty() {
1471                out.extend(
1472                    block
1473                        .self_items
1474                        .iter()
1475                        .filter(|ty| index.items[ty.0].kind == SymbolKind::Enum),
1476                );
1477            }
1478        }
1479    }
1480    Ok(out)
1481}
1482
1483/// What the walk reads of the impl block `id` for `Self` paths, built and
1484/// charged the first time it is asked: its members by name when no type
1485/// keys it, and the traits its trait path names from its module.
1486fn block_names<'a, 'b>(
1487    index: &'a Index,
1488    meter: &Meter,
1489    blocks: &'b mut BTreeMap<ImplId, BlockNames<'a>>,
1490    id: ImplId,
1491    unit: &Unit<'_>,
1492) -> Result<&'b BlockNames<'a>, ReachError> {
1493    let slot = match blocks.entry(id) {
1494        Entry::Occupied(found) => return Ok(found.into_mut()),
1495        Entry::Vacant(slot) => slot,
1496    };
1497    let block = &index.impl_blocks[id.0];
1498    let mut names = BlockNames::default();
1499    if block.self_items.is_empty() {
1500        for member in &block.members {
1501            work::add(Work::ReachSteps, 1);
1502            names
1503                .members
1504                .entry(index.items[member.0].name.as_str())
1505                .or_default()
1506                .push(*member);
1507        }
1508    }
1509    if let Some((leading_colon, segs)) = block
1510        .trait_path
1511        .as_ref()
1512        .map(SharedStr::as_str)
1513        .and_then(trait_segments)
1514    {
1515        work::add(Work::ReachPaths, 1);
1516        names.traits = index
1517            .reach_run(
1518                block.module_index,
1519                &segs,
1520                leading_colon,
1521                block.test != TestRole::None,
1522                Steps::QueryItems {
1523                    meter,
1524                    file: unit.file,
1525                    line: Some(unit.line),
1526                },
1527            )?
1528            .into_iter()
1529            .filter(|found| index.items[found.0].kind == SymbolKind::Trait)
1530            .collect();
1531    }
1532    let mut held =
1533        btree_entry::<ImplId, BlockNames<'_>>() + names.traits.capacity() * size_of::<ItemId>();
1534    if !names.members.is_empty() {
1535        held += btree_map::<&str, Vec<ItemId>>();
1536    }
1537    for members in names.members.values() {
1538        held += btree_entry::<&str, Vec<ItemId>>() + members.capacity() * size_of::<ItemId>();
1539    }
1540    meter
1541        .items(held, unit.file, Some(unit.line))
1542        .map_err(ReachError::Budget)?;
1543    Ok(slot.insert(names))
1544}
1545
1546/// The file and the line of `node`, which a charge for it names.
1547fn place_of(index: &Index, node: Node) -> (&RelPath, usize) {
1548    match node {
1549        Node::Item(id) => {
1550            let item = &index.items[id.0];
1551            (&item.file, item.name_line)
1552        }
1553        Node::Impl(id) => {
1554            let block = &index.impl_blocks[id.0];
1555            (&block.file, block.line)
1556        }
1557    }
1558}
1559
1560/// The nodes that `roots` reach in `index`, whose files are `files`, what
1561/// the walk holds charged to the item-bytes budget of `options` on from the
1562/// `held` bytes of the load.
1563pub(crate) fn reachable(
1564    index: &Index,
1565    files: &BTreeMap<RelPath, SourceFile>,
1566    (options, held): (&LoadOptions, usize),
1567    roots: &[Node],
1568) -> Result<Reachability, ReachError> {
1569    let mut sorted: Vec<Node> = Vec::with_capacity(roots.len());
1570    for root in roots {
1571        work::add(Work::ReachSteps, 1);
1572        match *root {
1573            Node::Item(id) if id.0 >= index.items.len() => return Err(ReachError::UnknownItem(id)),
1574            Node::Impl(id) if id.0 >= index.impl_blocks.len() => {
1575                return Err(ReachError::UnknownImpl(id));
1576            }
1577            node => sorted.push(node),
1578        }
1579    }
1580    sorted.sort_unstable();
1581    sorted.dedup();
1582    let Some(first) = sorted.first() else {
1583        return Ok(Reachability {
1584            reached: Vec::new(),
1585            at: BTreeMap::new(),
1586        });
1587    };
1588    let (file, line) = place_of(index, *first);
1589    let meter = Meter::query(options);
1590    meter
1591        .items(
1592            held + vec_first::<Reached>()
1593                + btree_map::<Node, usize>()
1594                + btree_map::<ItemId, ()>()
1595                + vec_first::<Queued>(),
1596            file,
1597            Some(line),
1598        )
1599        .map_err(ReachError::Budget)?;
1600    let mut walk = Walk::new(index, files, &meter, (file, line))?;
1601    let mut queue: VecDeque<Queued> = sorted
1602        .into_iter()
1603        .map(|node| (node, Edge::Root, None))
1604        .collect();
1605    let mut peak = queue.len();
1606    meter
1607        .items(peak * vec_slot::<Queued>(), file, Some(line))
1608        .map_err(ReachError::Budget)?;
1609    let mut reached: Vec<Reached> = Vec::new();
1610    let mut at: BTreeMap<Node, usize> = BTreeMap::new();
1611    let mut opened: BTreeSet<ItemId> = BTreeSet::new();
1612    while let Some((node, edge, from)) = queue.pop_front() {
1613        work::add(Work::ReachSteps, 1);
1614        let first = !at.contains_key(&node);
1615        let (file, line) = place_of(index, node);
1616        if first {
1617            meter
1618                .items(
1619                    vec_slot::<Reached>() + btree_entry::<Node, usize>(),
1620                    file,
1621                    Some(line),
1622                )
1623                .map_err(ReachError::Budget)?;
1624            at.insert(node, reached.len());
1625            reached.push(Reached { node, edge, from });
1626        }
1627        let was_opened = opened.len();
1628        for (next, by) in walk.next(node, edge, first, &mut opened)? {
1629            let opens = matches!(next, Node::Item(id) if index.items[id.0].kind == SymbolKind::Mod && by == Edge::Contains && !opened.contains(&id));
1630            if opens || !at.contains_key(&next) {
1631                queue.push_back((next, by, Some(node)));
1632            }
1633        }
1634        // What the queue holds at its most, and each module opened.
1635        let grown = queue.len().saturating_sub(peak) * vec_slot::<Queued>()
1636            + (opened.len() - was_opened) * btree_entry::<ItemId, ()>();
1637        peak = peak.max(queue.len());
1638        if grown > 0 {
1639            meter
1640                .items(grown, file, Some(line))
1641                .map_err(ReachError::Budget)?;
1642        }
1643    }
1644    Ok(Reachability { reached, at })
1645}
1646
1647#[cfg(test)]
1648mod tests {
1649    use std::fmt::Write as _;
1650    use std::mem::size_of;
1651
1652    use super::{DECLARES, Run, RunKind, Walk, lex_text, place_runs};
1653    use crate::budget::Budget;
1654    use crate::error::LoadErrorKind;
1655    use crate::item::Namespace;
1656    use crate::meter::{Meter, Steps};
1657    use crate::reach::{Node, ReachError};
1658    use crate::work::{self, Work};
1659    use crate::{LoadOptions, MemoryTree, Workspace};
1660
1661    /// The runs of `text` in `edition` as their text and the byte where each
1662    /// starts: a path as written without spaces, a run that `Self` starts as
1663    /// `Self::...`, and a method called on `self` as `.name`.
1664    fn runs_in(edition: u16, text: &str) -> Vec<(String, usize)> {
1665        let lexed = lex_text(text, edition).unwrap_or_else(|failure| panic!("{}", failure.message));
1666        lexed
1667            .runs
1668            .iter()
1669            .map(|run| {
1670                let words: Vec<&str> = lexed.segs[run.first..run.first + run.len]
1671                    .iter()
1672                    .map(|(start, end)| &text[*start..*end])
1673                    .collect();
1674                let shown = match run.kind {
1675                    RunKind::Method => format!(".{}", words.join("::")),
1676                    RunKind::Path | RunKind::SelfPath => format!(
1677                        "{}{}",
1678                        if run.leading_colon { "::" } else { "" },
1679                        words.join("::")
1680                    ),
1681                };
1682                (shown, run.start)
1683            })
1684            .collect()
1685    }
1686
1687    fn runs(text: &str) -> Vec<(String, usize)> {
1688        runs_in(2021, text)
1689    }
1690
1691    /// The texts of the runs of `text` in `edition`.
1692    fn texts_in(edition: u16, text: &str) -> Vec<String> {
1693        runs_in(edition, text)
1694            .into_iter()
1695            .map(|(text, _)| text)
1696            .collect()
1697    }
1698
1699    /// The texts of the runs of `text` in edition 2021.
1700    fn texts(text: &str) -> Vec<String> {
1701        texts_in(2021, text)
1702    }
1703
1704    #[test]
1705    fn a_run_is_an_identifier_path_that_no_dot_precedes_with_its_first_byte() {
1706        assert_eq!(runs("a::b::c"), [("a::b::c".to_owned(), 0)]);
1707        assert_eq!(texts("x.helper(); x.0.y"), ["x", "x"]);
1708        assert_eq!(texts("0..LIMIT; ..=END"), ["LIMIT", "END"]);
1709        assert_eq!(texts("::std::fmt::Debug"), ["::std::fmt::Debug"]);
1710        assert_eq!(texts("Vec::<u8>::new()"), ["Vec", "u8"]);
1711        assert_eq!(texts("<T as Tr>::f"), ["T", "Tr"]);
1712        assert_eq!(texts("r#match::x"), ["match::x"]);
1713        assert_eq!(texts("a :: b"), ["a::b"]);
1714        assert_eq!(texts("f(a::b, c)"), ["f", "a::b", "c"]);
1715        // A raw segment is read without its prefix, where it starts.
1716        assert_eq!(runs("r#gen::x"), [("gen::x".to_owned(), 0)]);
1717    }
1718
1719    #[test]
1720    fn path_keywords_start_a_run_and_other_keywords_are_no_segment() {
1721        assert_eq!(
1722            texts("crate::a; self::b; super::super::c; self::super::d"),
1723            ["crate::a", "self::b", "super::super::c", "self::super::d"]
1724        );
1725        // A keyword ends the run, and what goes on after it is no run.
1726        assert_eq!(texts("a::crate; a::self::b"), ["a", "a"]);
1727        assert_eq!(texts("r#fn::r#match"), ["fn::match"]);
1728        assert_eq!(texts("pub use a as b;"), ["a", "b"]);
1729        // `Self` starts a run of its own and is no later segment.
1730        assert_eq!(
1731            texts("Self::new(); impl Tr for S; a::Self::b; ::Self::c"),
1732            ["Self::new", "Tr", "S", "a"]
1733        );
1734        assert_eq!(texts("Self { a: 1 }; Self(2)"), ["Self", "Self"]);
1735    }
1736
1737    #[test]
1738    fn the_keywords_are_those_of_the_edition() {
1739        let text = "async(); await(); dyn(); try(); gen(); r#gen(); r#try()";
1740        assert_eq!(
1741            texts_in(2015, text),
1742            ["async", "await", "dyn", "try", "gen", "gen", "try"]
1743        );
1744        for edition in [2018, 2021] {
1745            assert_eq!(texts_in(edition, text), ["gen", "gen", "try"], "{edition}");
1746        }
1747        assert_eq!(texts_in(2024, text), ["gen", "try"]);
1748        // Every edition's keywords end a run.
1749        assert_eq!(texts_in(2015, "a::fn::b; a::dyn::b"), ["a", "a::dyn::b"]);
1750        assert_eq!(texts_in(2024, "a::gen::b; a::r#gen::b"), ["a", "a::gen::b"]);
1751    }
1752
1753    #[test]
1754    fn a_lifetime_a_metavariable_a_declared_name_and_a_bound_name_are_no_run() {
1755        assert_eq!(texts("&'a T; 'label: loop {}"), ["T"]);
1756        assert_eq!(texts("&'static Foo"), ["Foo"]);
1757        assert_eq!(texts("$x; $crate::helper()"), ["crate::helper"]);
1758        assert_eq!(texts("fn helper(x: u8) -> Foo {}"), ["u8", "Foo"]);
1759        assert_eq!(
1760            texts(
1761                "struct S { helper: u8 } enum E {} trait T {} type A = B; mod m {} const C: u8 = 1; static D: X = Y;"
1762            ),
1763            ["u8", "B", "u8", "X", "Y"]
1764        );
1765        assert_eq!(
1766            texts("macro_rules! m { () => { g() } }"),
1767            ["macro_rules", "g"]
1768        );
1769        assert_eq!(texts("S { helper: 1, other }"), ["S", "other"]);
1770        assert_eq!(texts("where T::Assoc: Bound"), ["T::Assoc", "Bound"]);
1771        assert_eq!(texts("x: ::std::Y"), ["::std::Y"]);
1772        assert_eq!(texts("x:&Y"), ["Y"]);
1773    }
1774
1775    #[test]
1776    fn const_declares_nothing_so_a_pointer_and_a_raw_borrow_name_their_path() {
1777        assert!(!DECLARES.contains(&"const"));
1778        assert_eq!(
1779            texts("fn f(p: *const Helper, q: *mut Other) {}"),
1780            ["Helper", "Other"]
1781        );
1782        assert_eq!(
1783            texts("&raw const VALUE; &raw mut OTHER"),
1784            ["raw", "VALUE", "raw", "OTHER"]
1785        );
1786        // Where `const` declares, what it declares is still no run: a
1787        // constant, a const fn, a const block and a const parameter.
1788        assert_eq!(
1789            texts("const C: u8 = 1; pub const D: E = F;"),
1790            ["u8", "E", "F"]
1791        );
1792        assert_eq!(
1793            texts("const fn helper() {} const unsafe fn other() {}"),
1794            Vec::<String>::new()
1795        );
1796        assert_eq!(texts("const { g() }"), ["g"]);
1797        assert_eq!(texts("fn f<const N: usize>() {}"), ["usize"]);
1798        assert_eq!(texts("impl<const N: usize> S<N> {}"), ["usize", "S", "N"]);
1799    }
1800
1801    #[test]
1802    fn a_where_clause_keeps_the_type_its_bound_is_put_on() {
1803        assert_eq!(
1804            texts("fn f<T>() where Helper: Clone, T: Into<Other> {}"),
1805            ["T", "Helper", "Clone", "T", "Into", "Other"]
1806        );
1807        // The clause ends at the body or at `;`, and a bound name after it is
1808        // no run again.
1809        assert_eq!(
1810            texts("fn f(helper: u8) where T: X { S { field: 1 } }"),
1811            ["u8", "T", "X", "S"]
1812        );
1813        assert_eq!(
1814            texts("fn g() where Self: Sized; fn h(x: u8) {}"),
1815            ["Self", "Sized", "u8"]
1816        );
1817        assert_eq!(
1818            texts(
1819                "struct S<T> where T: X { field: u8 } struct P(u8) where Q: Y; static Z: u8 = 0;"
1820            ),
1821            ["T", "T", "X", "u8", "u8", "Q", "Y", "u8"]
1822        );
1823        // A generic parameter's own bound is a name being bound.
1824        assert_eq!(texts("fn f<T: Clone>() {}"), ["Clone"]);
1825    }
1826
1827    #[test]
1828    fn a_name_called_on_self_is_a_method_run_and_a_field_of_self_is_not() {
1829        assert_eq!(
1830            texts("self.helper(); self.field; self.turbo::<u8>(); other.method(); self.0.x()"),
1831            [
1832                "self", ".helper", "self", "self", ".turbo", "u8", "other", "self"
1833            ]
1834        );
1835        let text = "fn f(&self) { self.r#match() }";
1836        assert_eq!(
1837            runs(text),
1838            [
1839                ("self".to_owned(), text.find("self)").expect("the receiver")),
1840                ("self".to_owned(), text.find("self.").expect("self")),
1841                (
1842                    ".match".to_owned(),
1843                    text.find("r#match").expect("the method")
1844                ),
1845            ]
1846        );
1847        // `self` as a path, and a name after a `.` of anything else, are not.
1848        assert_eq!(
1849            texts("self::helper(); s.helper(); Self.x()"),
1850            ["self::helper", "s", "Self"]
1851        );
1852    }
1853
1854    #[test]
1855    fn a_byte_order_mark_and_a_shebang_are_left_out_and_offsets_are_those_of_the_text() {
1856        let text = "\u{feff}fn f() { g() }";
1857        assert_eq!(runs(text), [("g".to_owned(), text.find('g').expect("g"))]);
1858        let text = "#!/usr/bin/env run\nfn f() { g() }";
1859        assert_eq!(runs(text), [("g".to_owned(), text.find("g(").expect("g"))]);
1860        // An inner attribute is no shebang.
1861        assert_eq!(texts("#![allow(unused)]\nfn f() {}"), ["allow", "unused"]);
1862        // A text that does not lex says where.
1863        let failure = lex_text("fn f() {\n\"", 2021).expect_err("an open string");
1864        assert_eq!(failure.line, 2);
1865    }
1866
1867    /// A doc comment lexes as a `doc` attribute whose `doc` is written
1868    /// nowhere in the text, so it starts no run and no byte of its text is
1869    /// read as a segment, whatever character ends it; a written `#[doc]`
1870    /// is a run as any attribute is.
1871    #[test]
1872    fn a_doc_comment_is_no_run_whatever_character_ends_it() {
1873        let text = "//! Crate §\n/// Calls abc\n/// See §1,\n/** Block ß */\n\
1874                    #[doc = \"x\"]\npub fn f() { a::b() }\nfn abc() {}\n";
1875        let ws = load(text);
1876        let site = |path: &str| {
1877            Node::Item(
1878                ws.resolve_in(path, Namespace::Value)
1879                    .unwrap_or_else(|e| panic!("{path}: {e}"))
1880                    .sites[0],
1881            )
1882        };
1883        let reached = ws
1884            .reachable(&[site("demo::f")])
1885            .unwrap_or_else(|e| panic!("{e}"));
1886        assert!(!reached.contains(site("demo::abc")));
1887        assert_eq!(
1888            runs(text),
1889            [
1890                ("doc".to_owned(), text.find("doc").expect("the attribute")),
1891                ("a::b".to_owned(), text.find("a::b").expect("the call")),
1892            ]
1893        );
1894    }
1895
1896    fn run_at(start: usize) -> Run {
1897        Run {
1898            start,
1899            first: 0,
1900            len: 1,
1901            leading_colon: false,
1902            kind: RunKind::Path,
1903        }
1904    }
1905
1906    #[test]
1907    fn each_run_goes_to_the_innermost_unit_that_holds_its_start() {
1908        // An impl block (0..100) holding two members, beside an item after
1909        // it, and a run outside every unit.
1910        let units = vec![(120, 150), (10, 20), (0, 100), (30, 40), (0, 100)];
1911        let runs: Vec<Run> = [5, 10, 25, 35, 99, 100, 130, 160]
1912            .into_iter()
1913            .map(run_at)
1914            .collect();
1915        let placed = place_runs(&runs, units);
1916        let by: Vec<((usize, usize), Vec<usize>)> = placed.into_iter().collect();
1917        assert_eq!(
1918            by,
1919            [
1920                ((0, 100), vec![0, 2, 4]),
1921                ((10, 20), vec![1]),
1922                ((30, 40), vec![3]),
1923                ((120, 150), vec![6]),
1924            ]
1925        );
1926    }
1927
1928    const MANIFEST: &str = "[package]\nname = \"demo\"\nversion = \"0.1.0\"\nedition = \"2021\"\n";
1929
1930    fn load_with(text: &str, options: &LoadOptions) -> Workspace {
1931        let tree = MemoryTree::from([("Cargo.toml", MANIFEST), ("src/lib.rs", text)]);
1932        Workspace::load_with(&tree, &["."], options).unwrap_or_else(|e| panic!("{e}"))
1933    }
1934
1935    fn load(text: &str) -> Workspace {
1936        load_with(text, &LoadOptions::default())
1937    }
1938
1939    /// A library of `items` public functions, each calling its own private
1940    /// helper `references` times.
1941    fn fan(items: usize, references: usize) -> Workspace {
1942        let mut text = String::new();
1943        for i in 0..items {
1944            let calls = format!("h{i}(); ").repeat(references);
1945            writeln!(text, "pub fn f{i}() {{ {calls}}}\nfn h{i}() {{}}").expect("write");
1946        }
1947        load(&text)
1948    }
1949
1950    /// The kinds of work the walk counts.
1951    const KINDS: [Work; 6] = [
1952        Work::ReachTokens,
1953        Work::ReachUnits,
1954        Work::ReachPaths,
1955        Work::ReachSteps,
1956        Work::SegmentReads,
1957        Work::Lookups,
1958    ];
1959
1960    /// The work of reaching `roots` in `ws`, by kind, and how many nodes
1961    /// were reached.
1962    fn work_of(ws: &Workspace, roots: &[Node]) -> ([usize; 6], usize) {
1963        let (reached, tally) = work::measure(usize::MAX, || ws.reachable(roots));
1964        let reached = reached.unwrap_or_else(|e| panic!("{e}")).reached.len();
1965        (KINDS.map(|kind| tally.get(kind)), reached)
1966    }
1967
1968    /// The work of reaching every public function of `fan(items,
1969    /// references)`.
1970    fn fan_work(items: usize, references: usize) -> ([usize; 6], usize) {
1971        let ws = fan(items, references);
1972        let roots: Vec<Node> = (0..items)
1973            .map(|i| {
1974                let path = format!("demo::f{i}");
1975                Node::Item(ws.resolve_in(&path, Namespace::Value).expect("f").sites[0])
1976            })
1977            .collect();
1978        work_of(&ws, &roots)
1979    }
1980
1981    #[test]
1982    fn the_work_of_a_walk_is_counted_exactly() {
1983        for (n, r) in [(1, 1), (3, 2), (5, 4)] {
1984            let ([tokens, units, paths, steps, ..], reached) = fan_work(n, r);
1985            assert_eq!(reached, 2 * n, "{n} {r}");
1986            // Each function is `pub fn f() { h(); ... }`, five tokens and
1987            // three for each call, and each helper `fn h() {}`, four.
1988            assert_eq!(tokens, n * (9 + 3 * r), "{n} {r}");
1989            // One push of the first unit, then for each further function
1990            // the helper before it and the function opened and closed, and
1991            // each run placed once.
1992            assert_eq!(units, n * r + 4 * n - 3, "{n} {r}");
1993            // Each helper's name is resolved once in its module, however
1994            // often it is called; a declared name is no path.
1995            assert_eq!(paths, n, "{n} {r}");
1996            // The tables (each item of the module and the crate root), the
1997            // roots, each node taken from the queue (a root and its helper),
1998            // each run of a function, and the one site its first run names:
1999            // a run read again in its module gives nothing.
2000            assert_eq!(steps, 6 * n + 1 + n * r, "{n} {r}");
2001        }
2002    }
2003
2004    #[test]
2005    fn the_work_grows_with_the_items_and_the_references_and_not_their_product() {
2006        // Three sizes in items at a fixed number of references, then in
2007        // references at a fixed number of items: each step adds the same
2008        // work, so no kind grows with a product of the two.
2009        let by_items: Vec<[usize; 6]> = [10, 20, 30].map(|n| fan_work(n, 3).0).to_vec();
2010        let by_references: Vec<[usize; 6]> = [2, 4, 6].map(|r| fan_work(10, r).0).to_vec();
2011        for sizes in [&by_items, &by_references] {
2012            for (kind, name) in KINDS.iter().enumerate() {
2013                let first = sizes[1][kind] - sizes[0][kind];
2014                let second = sizes[2][kind] - sizes[1][kind];
2015                assert_eq!(first, second, "{name:?}: {sizes:?}");
2016            }
2017        }
2018        // The references add no resolution: a run is resolved once in its
2019        // module.
2020        assert_eq!(by_references[0][2], by_references[2][2]);
2021    }
2022
2023    /// A library of a trait of `members` methods and `types` modules below
2024    /// one module `top`, each holding a struct with an inherent block of
2025    /// `members` methods and a block of the trait, an enum with a block,
2026    /// a type alias, a constant, a static and a function. Each method calls
2027    /// its next sibling through `Self::`, through `self.` and names the
2028    /// constant and the static; each trait method calls its inherent
2029    /// namesake on `self`.
2030    fn kinds(types: usize, members: usize) -> String {
2031        let mut text = String::from("pub trait Tr {\n");
2032        for j in 0..members {
2033            writeln!(text, "    fn t{j}(&self) -> u8;").expect("write");
2034        }
2035        text.push_str("}\npub mod top {\n");
2036        for i in 0..types {
2037            writeln!(
2038                text,
2039                "pub mod m{i} {{\n\
2040                 pub struct T{i} {{ f: u8 }}\n\
2041                 pub enum E{i} {{ A, B }}\n\
2042                 pub type A{i} = T{i};\n\
2043                 const K{i}: u8 = 1;\n\
2044                 static S{i}: u8 = 2;\n\
2045                 pub fn helper{i}() -> E{i} {{ E{i}::A }}\n\
2046                 impl E{i} {{ pub fn is_a(&self) -> bool {{ matches!(self, Self::A) }} }}"
2047            )
2048            .expect("write");
2049            writeln!(text, "impl T{i} {{").expect("write");
2050            for j in 0..members {
2051                let next = (j + 1) % members;
2052                writeln!(
2053                    text,
2054                    "    pub fn a{j}(&self) -> u8 {{ Self::a{next}(self) + self.a{next}() + K{i} + S{i} }}"
2055                )
2056                .expect("write");
2057            }
2058            writeln!(text, "}}\nimpl crate::Tr for T{i} {{").expect("write");
2059            for j in 0..members {
2060                writeln!(text, "    fn t{j}(&self) -> u8 {{ self.a{j}() }}").expect("write");
2061            }
2062            text.push_str("}\n}\n");
2063        }
2064        text.push_str("}\n");
2065        text
2066    }
2067
2068    /// The work of reaching the module `top` of `kinds(types, members)`.
2069    fn kinds_work(types: usize, members: usize) -> ([usize; 6], usize) {
2070        let ws = load(&kinds(types, members));
2071        let top = ws
2072            .resolve_in("demo::top", Namespace::Type)
2073            .expect("top")
2074            .sites[0];
2075        work_of(&ws, &[Node::Item(top)])
2076    }
2077
2078    #[test]
2079    fn the_work_over_types_impl_blocks_traits_and_members_grows_with_each_and_not_their_product() {
2080        // Every item and block below `top` is reached: the module, and for
2081        // each type its module, the struct, the enum, the alias, the
2082        // constant, the static, the function, the method of the enum, the
2083        // three blocks and the 2k methods.
2084        for (n, k) in [(1, 1), (2, 3), (4, 2)] {
2085            let (_, reached) = kinds_work(n, k);
2086            assert_eq!(reached, 2 + k + n * (11 + 2 * k), "{n} {k}");
2087        }
2088        // Equal steps in the types at a fixed number of members, and in the
2089        // members at a fixed number of types, in every counted kind: no work
2090        // grows with the types times the blocks, nor with the members times
2091        // the paths.
2092        let by_types: Vec<[usize; 6]> = [4, 8, 12].map(|n| kinds_work(n, 3).0).to_vec();
2093        let by_members: Vec<[usize; 6]> = [2, 4, 6].map(|k| kinds_work(4, k).0).to_vec();
2094        for sizes in [&by_types, &by_members] {
2095            for (kind, name) in KINDS.iter().enumerate() {
2096                let first = sizes[1][kind] - sizes[0][kind];
2097                let second = sizes[2][kind] - sizes[1][kind];
2098                assert_eq!(first, second, "{name:?}: {sizes:?}");
2099            }
2100        }
2101        // The exact counts, by kind, for n types of k members: the tokens
2102        // of the trait (four, and nine for each method) and of `top` (four),
2103        // and of each module; the steps of placing their runs; the runs
2104        // resolved (two at the top, and in each module fourteen and three
2105        // for each method: `Self::a` and `.a` in the inherent block, and `.a`
2106        // in the block of the trait);
2107        // the steps of the walk; and the segment reads and lookups of the
2108        // paths resolved, which the members do not change: a path that
2109        // `Self` starts and a method called on `self` are read in their
2110        // block, not walked as paths.
2111        for (n, k) in [(1, 1), (2, 3), (4, 2), (3, 5)] {
2112            let ([tokens, units, paths, steps, segments, lookups], _) = kinds_work(n, k);
2113            assert_eq!(tokens, 8 + 9 * k + n * (83 + 38 * k), "{n} {k}");
2114            assert_eq!(units, 4 * k + n * (39 + 16 * k), "{n} {k}");
2115            assert_eq!(paths, 2 + n * (14 + 3 * k), "{n} {k}");
2116            assert_eq!(steps, 5 + 5 * k + n * (68 + 31 * k), "{n} {k}");
2117            assert_eq!(segments, 9 * n, "{n} {k}");
2118            assert_eq!(lookups, 3 + 34 * n, "{n} {k}");
2119        }
2120    }
2121
2122    #[test]
2123    fn a_path_of_fifty_thousand_segments_is_walked_once_and_not_once_for_each_prefix() {
2124        const SEGMENTS: usize = 50_000;
2125        let text = format!(
2126            "pub mod m {{ pub use crate::m; pub struct End; }}\npub type T = {}End;\n",
2127            "m::".repeat(SEGMENTS)
2128        );
2129        let ws = load(&text);
2130        let alias = ws.resolve("demo::T").expect("the alias").sites[0];
2131        let end = ws.resolve("demo::m::End").expect("the struct").sites[0];
2132        // Each proper prefix is one step of one walk and the last segment is
2133        // read in each name space, so a segment is read a few times; a walk
2134        // from the start for each prefix would read it once for each prefix
2135        // after it, and passes the ceiling at once.
2136        let segments = SEGMENTS + 1;
2137        let (reached, tally) = work::measure_kind(Work::SegmentReads, 4 * segments, || {
2138            ws.reachable(&[Node::Item(alias)])
2139        });
2140        let reached = reached.unwrap_or_else(|e| panic!("{e}"));
2141        assert!(reached.contains(Node::Item(end)));
2142        assert!(tally.get(Work::SegmentReads) >= segments);
2143        assert!(tally.get(Work::Lookups) <= 4 * segments);
2144        assert_eq!(tally.get(Work::ReachPaths), 1);
2145    }
2146
2147    /// A library whose public function calls `a` `runs` times.
2148    fn dense(runs: usize) -> String {
2149        format!("pub fn f() {{ {}}}\nfn a() {{}}\n", "a; ".repeat(runs))
2150    }
2151
2152    /// The least item-bytes limit under which the walk from `demo::f` of
2153    /// `text` is given, less what the load holds: what the walk charges.
2154    fn walk_charge(text: &str) -> usize {
2155        let ws = load(text);
2156        let held = ws.usage().item_bytes;
2157        let walk = |limit: usize| {
2158            let ws = load_with(
2159                text,
2160                &LoadOptions {
2161                    max_item_bytes: limit,
2162                    ..LoadOptions::default()
2163                },
2164            );
2165            let f = ws.resolve_in("demo::f", Namespace::Value).expect("f").sites[0];
2166            ws.reachable(&[Node::Item(f)])
2167        };
2168        let (mut low, mut high) = (held, held + (1 << 24));
2169        assert!(walk(high).is_ok());
2170        while high - low > 1 {
2171            let mid = low + (high - low) / 2;
2172            if walk(mid).is_ok() {
2173                high = mid;
2174            } else {
2175                low = mid;
2176            }
2177        }
2178        let error = walk(low).expect_err("one byte less is refused");
2179        match error {
2180            ReachError::Budget(error) => {
2181                assert!(
2182                    matches!(
2183                        error.kind,
2184                        LoadErrorKind::Budget {
2185                            budget: Budget::ItemBytes,
2186                            limit
2187                        } if limit == low
2188                    ),
2189                    "{error}"
2190                );
2191                assert_eq!(error.file.as_str(), "src/lib.rs");
2192            }
2193            other => panic!("{other}"),
2194        }
2195        high - held
2196    }
2197
2198    #[test]
2199    fn what_the_walk_holds_is_charged_to_the_item_bytes_budget_on_from_the_load() {
2200        // Each run holds its record, its segment and its place in its unit,
2201        // and nothing else: the text it resolves to is held once.
2202        let per_run = size_of::<Run>() + size_of::<(usize, usize)>() + size_of::<usize>();
2203        let charges = [1000, 2000, 3000].map(|runs| walk_charge(&dense(runs)));
2204        assert_eq!(charges[1] - charges[0], 1000 * per_run);
2205        assert_eq!(charges[2] - charges[1], 1000 * per_run);
2206        // `a; ` is three bytes of text for each run.
2207        #[cfg(target_pointer_width = "64")]
2208        assert_eq!(per_run, 56);
2209        assert!(per_run < 20 * 3, "{per_run}");
2210    }
2211
2212    #[test]
2213    fn format_candidates_charge_owned_bytes_and_return_worker_work_to_the_caller() {
2214        let source = |calls| {
2215            format!(
2216                "const VALUE:u32=7; pub fn f(){{ {} }}",
2217                "let _=format!(\"{VALUE}\");".repeat(calls)
2218            )
2219        };
2220        let samples = [32, 64, 96].map(|calls| {
2221            let text = source(calls);
2222            let ws = load(&text);
2223            let root = ws.resolve_in("demo::f", Namespace::Value).expect("f").sites[0];
2224            let capture = ws
2225                .resolve_in("demo::VALUE", Namespace::Value)
2226                .expect("VALUE")
2227                .sites[0];
2228            let (reached, tally) = work::measure(100_000, || ws.reachable(&[Node::Item(root)]));
2229            assert!(reached.expect("reachability").contains(Node::Item(capture)));
2230            let tokens = tally.get(Work::ReachFormatTokens);
2231            let bytes = tally.get(Work::ReachFormatBytes);
2232            assert!(tokens > calls, "worker token work was lost");
2233            assert!(
2234                bytes >= calls * "{VALUE}".len(),
2235                "worker decode work was lost"
2236            );
2237            (tokens, bytes, walk_charge(&text))
2238        });
2239        for at in 0..2 {
2240            let get = |n: usize| if at == 0 { samples[n].0 } else { samples[n].1 };
2241            assert_eq!(get(2) - get(1), get(1) - get(0));
2242        }
2243        assert!(samples[1].2 > samples[0].2);
2244        assert_eq!(samples[2].2 - samples[1].2, samples[1].2 - samples[0].2);
2245    }
2246
2247    #[test]
2248    fn code_prefix_reads_share_one_query_account_and_refuse_one_less() {
2249        let tree = MemoryTree::from([
2250            (
2251                "Cargo.toml",
2252                "[package]\nname='demo'\nversion='0.1.0'\nedition='2021'\n",
2253            ),
2254            (
2255                "src/lib.rs",
2256                "mod a { pub struct X {} } mod b { pub use crate::a::*; } pub use b::*;",
2257            ),
2258        ]);
2259        let ws = Workspace::load(&tree, &["."]).expect("glob source");
2260        let index = ws.index();
2261        let root = index.target_roots[0];
2262        let (file, line) = index.module_site(root);
2263        let words = ["X".to_owned()];
2264        let run = |limit| {
2265            let options = LoadOptions {
2266                max_query_work: limit,
2267                ..LoadOptions::default()
2268            };
2269            let meter = Meter::query(&options);
2270            let answer = index.reach_run(
2271                root,
2272                &words,
2273                false,
2274                false,
2275                Steps::QueryItems {
2276                    meter: &meter,
2277                    file: &file,
2278                    line,
2279                },
2280            );
2281            (answer, meter.usage())
2282        };
2283        let (answer, usage) = run(usize::MAX);
2284        let expected = answer.expect("native admitted resolver");
2285        assert!(!expected.is_empty());
2286        assert!(usage.work > 0);
2287        assert!(usage.item_bytes > 0);
2288        assert_eq!(usage.glob_bytes, 0);
2289        assert_eq!(run(usage.work).0.expect("exact work"), expected);
2290        let error = run(usage.work - 1).0.expect_err("one work unit short");
2291        assert!(
2292            matches!(error.kind, LoadErrorKind::Budget { budget: Budget::Work, limit }
2293            if limit == usage.work - 1)
2294        );
2295        assert_eq!(error.file.as_str(), "src/lib.rs");
2296    }
2297
2298    #[test]
2299    fn a_shared_files_edition_caches_are_each_counted_and_charged_once() {
2300        let tree = MemoryTree::from([
2301            ("Cargo.toml", "[workspace]\nmembers = [\"old\", \"new\"]\n"),
2302            (
2303                "old/Cargo.toml",
2304                "[package]\nname = \"old\"\nversion = \"0.1.0\"\nedition = \"2021\"\n",
2305            ),
2306            (
2307                "new/Cargo.toml",
2308                "[package]\nname = \"new\"\nversion = \"0.1.0\"\nedition = \"2024\"\n",
2309            ),
2310            (
2311                "old/src/lib.rs",
2312                "#[path = \"../../shared.rs\"] mod shared;\n",
2313            ),
2314            (
2315                "new/src/lib.rs",
2316                "#[path = \"../../shared.rs\"] mod shared;\n",
2317            ),
2318            ("shared.rs", "pub fn f() { r#gen() }\nfn r#gen() {}\n"),
2319        ]);
2320        let ws = Workspace::load(&tree, &["."]).expect("shared source");
2321        let options = LoadOptions::default();
2322        let meter = Meter::new(&options);
2323        let files = ws
2324            .files()
2325            .map(|source| {
2326                (
2327                    source.path.clone(),
2328                    crate::SourceFile {
2329                        path: source.path.clone(),
2330                        package: source.package.clone(),
2331                        shipping: source.shipping,
2332                        test: source.test,
2333                        text: source.text.clone(),
2334                        facts: source.facts.clone(),
2335                        reached: source.reached.clone(),
2336                    },
2337                )
2338            })
2339            .collect();
2340        let item = |name| {
2341            ws.resolve_in(name, Namespace::Value)
2342                .expect("function")
2343                .sites[0]
2344        };
2345        let old = item("old::shared::f");
2346        let new = item("new::shared::f");
2347        let file = &ws.item(old).expect("old function").file;
2348        assert_eq!(file, &ws.item(new).expect("new function").file);
2349        let mut walk = Walk::new(ws.index(), &files, &meter, (file, 1)).expect("walk tables");
2350        let old_module = walk.homes[old.0].module.expect("old module");
2351        let new_module = walk.homes[new.0].module.expect("new module");
2352        let (_, first) = work::measure(usize::MAX, || {
2353            walk.load(file, old_module).expect("old cache")
2354        });
2355        let first_bytes = meter.usage().item_bytes;
2356        let (_, repeated) = work::measure(usize::MAX, || {
2357            walk.load(file, old_module).expect("old cache again")
2358        });
2359        assert!(first.get(Work::ReachTokens) > 0);
2360        assert_eq!(repeated.get(Work::ReachTokens), 0);
2361        assert_eq!(meter.usage().item_bytes, first_bytes);
2362        let (_, second) = work::measure(usize::MAX, || {
2363            walk.load(file, new_module).expect("new cache")
2364        });
2365        let both_bytes = meter.usage().item_bytes;
2366        assert_eq!(second.get(Work::ReachTokens), first.get(Work::ReachTokens));
2367        assert!(both_bytes > first_bytes);
2368        assert_eq!(walk.files_runs.len(), 2);
2369        let (_, repeated) = work::measure(usize::MAX, || {
2370            walk.load(file, new_module).expect("new cache again")
2371        });
2372        assert_eq!(repeated.get(Work::ReachTokens), 0);
2373        assert_eq!(meter.usage().item_bytes, both_bytes);
2374
2375        let under = |limit| -> Result<usize, ReachError> {
2376            let options = LoadOptions {
2377                max_item_bytes: limit,
2378                ..LoadOptions::default()
2379            };
2380            let meter = Meter::new(&options);
2381            let mut walk = Walk::new(ws.index(), &files, &meter, (file, 1))?;
2382            walk.load(file, old_module)?;
2383            walk.load(file, new_module)?;
2384            Ok(meter.usage().item_bytes)
2385        };
2386        assert_eq!(
2387            under(both_bytes).expect("exact retained-byte limit"),
2388            both_bytes
2389        );
2390        let error = under(both_bytes - 1).expect_err("one byte short refuses second cache");
2391        assert!(
2392            matches!(error, ReachError::Budget(ref load) if matches!(load.kind,
2393            LoadErrorKind::Budget { budget: Budget::ItemBytes, limit } if limit == both_bytes - 1))
2394        );
2395    }
2396}