Skip to main content

raf_source/
facts.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//! Owned facts about one source file.
5//!
6//! The facts are read on the parse thread by [`extract`] and leave it as plain
7//! data, so no syntax tree and no span outlives its thread. They hold what the
8//! module walk needs (module declarations with their `path` attributes) and
9//! what the symbol index needs (items, `use` trees and impl headers with
10//! their positions, attributes, documentation and test role).
11
12use std::cell::{Cell, RefCell};
13use std::collections::HashMap;
14
15use purrdf_hash::fixed::FixedState;
16use std::mem::size_of;
17use std::ops::Range;
18use std::sync::Arc;
19
20use quote::ToTokens as _;
21use syn::parse::Parser as _;
22use syn::spanned::Spanned as _;
23use syn::visit::Visit;
24use syn::{Attribute, Expr, ExprLit, Item, Lit, Meta, Visibility};
25
26use crate::cfg::{CfgExpr, parse_list};
27use crate::meter::FactAllowance;
28use crate::verbatim::{self, Bodiless, Verbatim};
29use crate::work::{self, Work};
30
31/// A region of the file in lines and bytes.
32///
33/// Line ranges are 1-based and half-open, as in `raf_okf::Span`: an item on
34/// line `n` alone has the lines `n..n + 1`.
35///
36/// The struct is `#[non_exhaustive]`: adding a field is not a breaking change,
37/// so a pattern names the fields it reads and ends in `..`.
38///
39/// ```compile_fail,E0638
40/// # fn names(span: &raf_source::SpanFact) {
41/// let raf_source::SpanFact { lines, start_byte, end_byte } = span;
42/// # }
43/// ```
44#[derive(Debug, Clone, PartialEq, Eq)]
45#[non_exhaustive]
46pub struct SpanFact {
47    /// The lines the region covers: from its first line to the line after
48    /// its last.
49    pub lines: Range<usize>,
50    /// The byte offset of the start.
51    pub start_byte: usize,
52    /// The byte offset just past the end.
53    pub end_byte: usize,
54}
55
56/// Whether, and how, an item belongs to test code.
57#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
58#[non_exhaustive]
59pub enum TestRole {
60    /// Not test code by its own attributes or its enclosing modules.
61    None,
62    /// Guarded by a `cfg` that implies `test`, directly or by an enclosing
63    /// module.
64    CfgTest,
65    /// A function marked `#[test]`.
66    TestFn,
67}
68
69/// The declared visibility of an item.
70#[derive(Debug, Clone, PartialEq, Eq)]
71#[non_exhaustive]
72pub enum Vis {
73    /// No visibility keyword.
74    Inherited,
75    /// `pub`.
76    Public,
77    /// `pub(crate)`, `pub(super)`, `pub(self)` or `pub(in path)`, as written
78    /// inside the parentheses.
79    Restricted(String),
80}
81
82/// What a named item is.
83#[derive(Debug, Clone, Copy, PartialEq, Eq)]
84pub(crate) enum ItemKind {
85    /// A function or a method.
86    Fn,
87    /// A struct.
88    Struct,
89    /// An enum.
90    Enum,
91    /// A union.
92    Union,
93    /// A trait.
94    Trait,
95    /// A type alias or an associated type.
96    TypeAlias,
97    /// A constant or an associated constant.
98    Const,
99    /// `const _: T = ..;`, which defines no name. It is recorded so that
100    /// nothing is dropped silently, and is not indexed under a path.
101    UnnamedConst,
102    /// A static.
103    Static,
104    /// A `macro_rules!` definition.
105    MacroRules,
106    /// An `extern crate` item.
107    ExternCrate,
108    /// A function declared in an `extern` block.
109    ForeignFn,
110    /// A static declared in an `extern` block.
111    ForeignStatic,
112    /// A type declared in an `extern` block.
113    ForeignType,
114}
115
116/// A plain path as written: its segments without raw-identifier prefixes and
117/// whether it starts with `::`.
118#[derive(Debug, Clone, PartialEq, Eq)]
119pub(crate) struct PathFact {
120    /// The segments, generic arguments left out.
121    pub(crate) segments: Vec<String>,
122    /// True when the path starts with `::`.
123    pub(crate) leading_colon: bool,
124}
125
126/// How a struct declares its fields. A unit or tuple struct also defines a
127/// name in the value namespace.
128#[derive(Debug, Clone, Copy, PartialEq, Eq)]
129#[non_exhaustive]
130pub enum FieldShape {
131    /// `struct S;`.
132    Unit,
133    /// `struct S(..);`.
134    Tuple,
135    /// `struct S { .. }`.
136    Named,
137}
138
139/// An attribute as written: its path and the tokens after it.
140#[derive(Debug, Clone, PartialEq, Eq)]
141pub(crate) struct AttrFact {
142    /// The attribute path, such as `derive` or `cfg`.
143    pub(crate) path: String,
144    /// The rest of the attribute, such as `(Debug)` or `= "text"`; empty when
145    /// there is none.
146    pub(crate) args: String,
147}
148
149/// What the parameters of a function and the value of a constant add to the
150/// item, shared by every record of the item.
151#[derive(Debug, Clone, PartialEq, Eq, Default)]
152pub(crate) struct ItemDetail {
153    /// The names the parameters bind, in signature order, with `self` first
154    /// for a receiver.
155    pub(crate) bindings: Vec<String>,
156    /// The byte range between the `=` and the `;` of a constant or a static
157    /// that has a value.
158    pub(crate) initializer: Option<Range<usize>>,
159    /// Arity of a nominal declaration with only unconstrained const parameters.
160    pub(crate) nominal_const_arity: Option<usize>,
161    /// Literal const arguments of a zero-parameter, plain-path type alias.
162    pub(crate) alias_const_arity: Option<usize>,
163    /// This method's generic parameters or where clause require applicability evidence.
164    pub(crate) method_requires_inference: bool,
165    /// The written enum members when declaration attributes preserve their upper bound.
166    pub(crate) variants: Option<Box<[VariantFact]>>,
167}
168
169#[derive(Debug, Clone, PartialEq, Eq)]
170pub(crate) struct VariantFact {
171    pub(crate) name: String,
172    pub(crate) shape: FieldShape,
173}
174
175/// A named item.
176#[derive(Debug, Clone, PartialEq, Eq)]
177pub(crate) struct ItemFact {
178    /// The name without a raw-identifier prefix. For `extern crate x as y`
179    /// this is `y`.
180    pub(crate) name: String,
181    /// The original crate name of `extern crate x as y`.
182    pub(crate) renamed_from: Option<String>,
183    /// What the item is.
184    pub(crate) kind: ItemKind,
185    /// The 1-based line of the name.
186    pub(crate) name_line: usize,
187    /// The whole item, attributes included.
188    pub(crate) span: SpanFact,
189    /// The braced body, or the function block, when there is one.
190    pub(crate) body: Option<SpanFact>,
191    /// What a signature or a constant adds; `None` when it adds nothing.
192    pub(crate) detail: Option<Arc<ItemDetail>>,
193    /// The declared visibility.
194    pub(crate) vis: Vis,
195    /// Every attribute, in order.
196    pub(crate) attrs: Vec<AttrFact>,
197    /// True when an unconditional `#[doc]` attribute (or a doc comment) holds
198    /// text, or is `#[doc = include_str!(..)]`. `#[doc(hidden)]` alone does
199    /// not count.
200    pub(crate) documented: bool,
201    /// True when the item has `#[doc(hidden)]`.
202    pub(crate) doc_hidden: bool,
203    /// The test role.
204    pub(crate) test: TestRole,
205    /// True when the item has `#[macro_export]`.
206    pub(crate) macro_export: bool,
207    /// The items of a trait, in order.
208    pub(crate) members: Vec<ItemFact>,
209    /// The field shape of a struct; `None` for every other kind.
210    pub(crate) shape: Option<FieldShape>,
211    /// The aliased path of `type A = path::B;` when the right side is a plain
212    /// path; `None` for every other item.
213    pub(crate) alias: Option<PathFact>,
214}
215
216/// The `path` attributes of a module declaration.
217#[derive(Debug, Clone, PartialEq, Eq, Default)]
218pub(crate) struct PathAttrs {
219    /// Every `#[path = "..."]` that applies unconditionally.
220    pub(crate) unconditional: Vec<String>,
221    /// Every `path` set by `#[cfg_attr(predicate, path = "...")]`.
222    pub(crate) conditional: Vec<ConditionalPath>,
223}
224
225/// A `path` that applies when a predicate holds.
226#[derive(Debug, Clone, PartialEq, Eq)]
227pub(crate) struct ConditionalPath {
228    /// The `cfg_attr` predicate, as written.
229    pub(crate) predicate: String,
230    /// True when the predicate holds only in a test build.
231    pub(crate) implies_test: bool,
232    /// The path value.
233    pub(crate) path: String,
234}
235
236/// A module declaration: `mod name;` or `mod name { .. }`.
237#[derive(Debug, Clone, PartialEq, Eq)]
238pub(crate) struct ModFact {
239    /// The name without a raw-identifier prefix.
240    pub(crate) name: String,
241    /// The 1-based line of the name.
242    pub(crate) name_line: usize,
243    /// The byte at which the name starts: after the attributes and before the
244    /// body, so no configuration and no edit of the body moves it.
245    pub(crate) name_start: usize,
246    /// The whole declaration, attributes included.
247    pub(crate) span: SpanFact,
248    /// The braced body of an inline module.
249    pub(crate) body_span: Option<SpanFact>,
250    /// The declared visibility.
251    pub(crate) vis: Vis,
252    /// Every attribute, in order.
253    pub(crate) attrs: Vec<AttrFact>,
254    /// True when the module is documented.
255    pub(crate) documented: bool,
256    /// True when the module has `#[doc(hidden)]`.
257    pub(crate) doc_hidden: bool,
258    /// The test role of the module itself.
259    pub(crate) test: TestRole,
260    /// The `path` attributes.
261    pub(crate) paths: PathAttrs,
262    /// The contents of an inline module; `None` for `mod name;`.
263    pub(crate) inline: Option<ModBody>,
264}
265
266/// One `use` tree, owned.
267#[derive(Debug, Clone, PartialEq, Eq)]
268pub(crate) enum UseTree {
269    /// `name::rest`.
270    Path {
271        /// The segment.
272        name: String,
273        /// What follows it.
274        rest: Box<UseTree>,
275    },
276    /// `name`.
277    Name(String),
278    /// `name as alias`.
279    Rename {
280        /// The imported name.
281        name: String,
282        /// The local name.
283        alias: String,
284    },
285    /// `*`.
286    Glob,
287    /// `{a, b::c}`.
288    Group(Vec<UseTree>),
289}
290
291/// A `use` declaration.
292#[derive(Debug, Clone, PartialEq, Eq)]
293pub(crate) struct UseFact {
294    /// The 1-based line of the `use` keyword.
295    pub(crate) line: usize,
296    /// The whole declaration.
297    pub(crate) span: SpanFact,
298    /// The declared visibility (a re-export when not inherited).
299    pub(crate) vis: Vis,
300    /// True for `use ::name`.
301    pub(crate) leading_colon: bool,
302    /// The tree.
303    pub(crate) tree: UseTree,
304    /// The test role.
305    pub(crate) test: TestRole,
306    /// True when the declaration has `#[doc(hidden)]`.
307    pub(crate) doc_hidden: bool,
308    /// Configuration can change whether this declaration is present.
309    pub(crate) configuration: ConfigurationDependence,
310}
311
312#[derive(Debug, Clone, Copy, PartialEq, Eq)]
313pub(crate) enum ConfigurationDependence {
314    Unconditional,
315    Conditional,
316}
317
318impl ConfigurationDependence {
319    pub(crate) fn of(attrs: &[AttrFact]) -> Self {
320        if attrs
321            .iter()
322            .any(|attr| matches!(attr.path.as_str(), "cfg" | "cfg_attr"))
323        {
324            Self::Conditional
325        } else {
326            Self::Unconditional
327        }
328    }
329}
330
331/// An `impl` block header and its items.
332#[derive(Debug, Clone, PartialEq, Eq)]
333pub(crate) struct ImplFact {
334    /// The 1-based line of the `impl` keyword.
335    pub(crate) line: usize,
336    /// The whole block.
337    pub(crate) span: SpanFact,
338    /// The braced body.
339    pub(crate) body: SpanFact,
340    /// The trait path as written, for a trait impl.
341    pub(crate) trait_path: Option<String>,
342    /// The segments of the trait path, for a trait impl.
343    pub(crate) trait_segments: Option<PathFact>,
344    /// The self type as written.
345    pub(crate) self_type: String,
346    /// The segments of the path the self type is written with: a plain path,
347    /// or the first trait of a trait object (`dyn Tr + Send` gives `Tr`),
348    /// inside any parentheses. `None` for every other type.
349    pub(crate) self_path: Option<Vec<String>>,
350    /// True when that path starts with `::`, so it names an external crate
351    /// and not a local item.
352    pub(crate) self_leading_colon: bool,
353    /// The names of the generic type and const parameters of the block.
354    pub(crate) generics: Vec<String>,
355    /// A plain inherent self type forwarding unconstrained const parameters only.
356    pub(crate) unconditional_self: Option<usize>,
357    /// The associated items.
358    pub(crate) items: Vec<ItemFact>,
359    /// The test role.
360    pub(crate) test: TestRole,
361}
362
363fn nominal_const_arity(generics: &syn::Generics) -> Option<usize> {
364    (generics.where_clause.is_none()
365        && generics.params.iter().all(|parameter| matches!(parameter, syn::GenericParam::Const(parameter) if parameter.attrs.is_empty())))
366        .then_some(generics.params.len())
367}
368
369fn has_written_variant_roster(attrs: &[AttrFact]) -> bool {
370    attrs.iter().all(|attribute| {
371        matches!(
372            attribute.path.as_str(),
373            "allow"
374                | "cfg"
375                | "deny"
376                | "deprecated"
377                | "derive"
378                | "doc"
379                | "expect"
380                | "forbid"
381                | "must_use"
382                | "non_exhaustive"
383                | "repr"
384                | "warn"
385        )
386    })
387}
388
389fn alias_const_arity(alias: &syn::ItemType) -> Option<usize> {
390    if !alias.generics.params.is_empty() || alias.generics.where_clause.is_some() {
391        return None;
392    }
393    let syn::Type::Path(path) = alias.ty.as_ref() else {
394        return None;
395    };
396    if path.qself.is_some()
397        || path
398            .path
399            .segments
400            .iter()
401            .rev()
402            .skip(1)
403            .any(|segment| !matches!(segment.arguments, syn::PathArguments::None))
404    {
405        return None;
406    }
407    match &path.path.segments.last()?.arguments {
408        syn::PathArguments::None => Some(0),
409        syn::PathArguments::AngleBracketed(arguments) if arguments.args.iter().all(|argument| matches!(argument, syn::GenericArgument::Const(Expr::Lit(value)) if value.attrs.is_empty())) => Some(arguments.args.len()),
410        _ => None,
411    }
412}
413
414fn unconditional_self(block: &syn::ItemImpl) -> bool {
415    if block.trait_.is_some() || block.generics.where_clause.is_some() {
416        return false;
417    }
418    let syn::Type::Path(path) = block.self_ty.as_ref() else {
419        return false;
420    };
421    if path.qself.is_some()
422        || path
423            .path
424            .segments
425            .iter()
426            .rev()
427            .skip(1)
428            .any(|segment| !matches!(segment.arguments, syn::PathArguments::None))
429    {
430        return false;
431    }
432    let Some(last) = path.path.segments.last() else {
433        return false;
434    };
435    let arguments = match &last.arguments {
436        syn::PathArguments::None => return block.generics.params.is_empty(),
437        syn::PathArguments::AngleBracketed(arguments) => &arguments.args,
438        syn::PathArguments::Parenthesized(_) => return false,
439    };
440    if arguments.len() != block.generics.params.len() {
441        return false;
442    }
443    arguments
444        .iter()
445        .zip(&block.generics.params)
446        .all(|(argument, parameter)| {
447            let syn::GenericParam::Const(parameter) = parameter else {
448                return false;
449            };
450            if !parameter.attrs.is_empty() || parameter.default.is_some() {
451                return false;
452            }
453            let path = match argument {
454                syn::GenericArgument::Type(syn::Type::Path(path)) if path.qself.is_none() => {
455                    &path.path
456                }
457                syn::GenericArgument::Const(Expr::Path(path))
458                    if path.qself.is_none() && path.attrs.is_empty() =>
459                {
460                    &path.path
461                }
462                _ => return false,
463            };
464            path.is_ident(&parameter.ident)
465        })
466}
467
468/// One item-producing macro invocation observed on the parse worker.
469#[derive(Debug, Clone, PartialEq, Eq)]
470pub(crate) struct UnexpandedFact {
471    pub(crate) invoked: String,
472    pub(crate) span: SpanFact,
473    pub(crate) test: TestRole,
474    pub(crate) identifiers: Vec<String>,
475}
476
477/// The contents of a module, in source order within each list.
478#[derive(Debug, Clone, PartialEq, Eq, Default)]
479pub(crate) struct ModBody {
480    /// Named items other than modules, `use` declarations and impls.
481    pub(crate) items: Vec<ItemFact>,
482    /// Module declarations.
483    pub(crate) mods: Vec<ModFact>,
484    /// Module declarations inside the function bodies, constant initializers
485    /// and other blocks of the items of this module, in source order. They
486    /// name no item of the module: only the module walk and the index read
487    /// them.
488    pub(crate) blocks: Vec<ModFact>,
489    /// `use` declarations.
490    pub(crate) uses: Vec<UseFact>,
491    /// `impl` blocks.
492    pub(crate) impls: Vec<ImplFact>,
493    /// Item-producing macro invocations, without generated definitions.
494    pub(crate) unexpanded: Vec<UnexpandedFact>,
495    /// Opaque declarations proved disabled for every configuration.
496    pub(crate) disabled: Vec<SpanFact>,
497}
498
499impl ModFact {
500    /// The module path segment of a module declared inside a block. A block
501    /// has no name that a path can write, so the segment holds the module
502    /// name and the byte where the name starts, in braces that no identifier
503    /// has: no path written in source can name the module, and two blocks
504    /// that declare one name stay apart. The name start is used because a
505    /// configured load removes a leading `cfg_attr` that does not apply,
506    /// which moves the start of the declaration, and an edit of the body
507    /// moves its end; neither moves the name, so one declaration has one
508    /// segment in every load.
509    pub(crate) fn block_segment(&self) -> String {
510        format!("{{{}@{}}}", self.name, self.name_start)
511    }
512}
513
514impl ModBody {
515    /// How many module declarations the walk follows in this body: those of
516    /// the item list, then those inside blocks.
517    pub(crate) fn declarations(&self) -> usize {
518        self.mods.len() + self.blocks.len()
519    }
520
521    /// The declaration at `position` of the item list followed by the blocks.
522    pub(crate) fn declaration(&self, position: usize) -> Option<&ModFact> {
523        self.mods.get(position).or_else(|| {
524            position
525                .checked_sub(self.mods.len())
526                .and_then(|local| self.blocks.get(local))
527        })
528    }
529
530    /// True when the declaration at `position` is inside a block.
531    pub(crate) fn is_block_local(&self, position: usize) -> bool {
532        position >= self.mods.len()
533    }
534}
535
536/// The facts of one file.
537#[derive(Debug, Clone, PartialEq, Eq, Default)]
538pub(crate) struct FileFacts {
539    /// The file's own module.
540    pub(crate) body: ModBody,
541    /// True when the file starts with documentation (`//!` or `#![doc = ..]`),
542    /// which documents the module that the file is.
543    pub(crate) documented: bool,
544    /// True when the file has `#![doc(hidden)]`.
545    pub(crate) doc_hidden: bool,
546    /// The inner attributes of the file, in order.
547    pub(crate) attrs: Vec<AttrFact>,
548}
549
550/// Why the facts of a file could not be read.
551#[derive(Debug)]
552pub(crate) enum ExtractError {
553    /// A `cfg` or `cfg_attr` predicate is not readable.
554    Cfg { line: usize, message: String },
555    /// A `path` attribute is not `path = "literal"`: on the module `module`
556    /// when it is on a module, under the `cfg_attr` predicate `predicate`
557    /// when one guards it.
558    PathAttr {
559        line: usize,
560        module: Option<String>,
561        predicate: Option<String>,
562        message: String,
563    },
564    /// An item the index does not model.
565    Unsupported { line: usize, what: String },
566    /// A position outside the text.
567    Position { line: usize },
568    /// The facts passed the fact-bytes budget of the load.
569    Budget { line: usize, limit: usize },
570}
571
572type Found<T> = Result<T, ExtractError>;
573
574/// Characters between two marks of a long line's index.
575const MARK_EVERY: usize = 64;
576
577/// How a long line turns a column into a byte offset.
578enum LineIndex {
579    /// Every character is one byte.
580    Ascii,
581    /// The byte offset, from the line start, of every [`MARK_EVERY`]th
582    /// character.
583    Marks(Vec<usize>),
584}
585
586/// Line starts of the text, for turning positions into byte offsets.
587///
588/// A column counts characters, so a line with a character of more than one
589/// byte is walked. A long line is indexed once, the first time it is asked
590/// about, so the cost of a position does not grow with the length of its line.
591struct Positions<'t> {
592    text: &'t str,
593    starts: Vec<usize>,
594    long: RefCell<HashMap<usize, LineIndex, FixedState>>,
595}
596
597impl<'t> Positions<'t> {
598    fn new(text: &'t str) -> Self {
599        // Native spans count original-source characters, including the BOM.
600        let mut starts = vec![0];
601        starts.extend(text.match_indices('\n').map(|(at, _)| at + 1));
602        Self {
603            text,
604            starts,
605            long: RefCell::new(HashMap::with_hasher(FixedState::new())),
606        }
607    }
608
609    fn byte(&self, line: usize, column: usize) -> Found<usize> {
610        work::add(Work::Positions, 1);
611        let outside = || ExtractError::Position { line };
612        let index = line.checked_sub(1).ok_or_else(outside)?;
613        let start = *self.starts.get(index).ok_or_else(outside)?;
614        let end = self
615            .starts
616            .get(index + 1)
617            .copied()
618            .unwrap_or(self.text.len());
619        let own = self.text.get(start..end).ok_or_else(outside)?;
620        let (base, rest, skip) = if own.len() <= MARK_EVERY {
621            (0, own, column)
622        } else {
623            let mut long = self.long.borrow_mut();
624            let entry = long.entry(index).or_insert_with(|| {
625                if own.is_ascii() {
626                    work::add(Work::ColumnSteps, own.len());
627                    LineIndex::Ascii
628                } else {
629                    LineIndex::Marks(
630                        own.char_indices()
631                            .inspect(|_| work::add(Work::ColumnSteps, 1))
632                            .step_by(MARK_EVERY)
633                            .map(|(at, _)| at)
634                            .collect(),
635                    )
636                }
637            });
638            match entry {
639                LineIndex::Ascii => {
640                    return if column <= own.len() {
641                        Ok(start + column)
642                    } else {
643                        Err(outside())
644                    };
645                }
646                LineIndex::Marks(marks) => {
647                    let mark = (column / MARK_EVERY).min(marks.len().saturating_sub(1));
648                    let base = marks.get(mark).copied().unwrap_or(0);
649                    let rest = own.get(base..).ok_or_else(outside)?;
650                    (base, rest, column - mark * MARK_EVERY)
651                }
652            }
653        };
654        let mut chars = rest
655            .char_indices()
656            .inspect(|_| work::add(Work::ColumnSteps, 1));
657        if let Some((offset, _)) = chars.nth(skip) {
658            return Ok(start + base + offset);
659        }
660        let all = rest.chars().count();
661        work::add(Work::ColumnSteps, all);
662        // Just past the last character of the line.
663        if all == skip {
664            Ok(start + base + rest.len())
665        } else {
666            Err(outside())
667        }
668    }
669
670    fn span(&self, span: proc_macro2::Span) -> Found<SpanFact> {
671        let (start, end) = (span.start(), span.end());
672        Ok(SpanFact {
673            lines: start.line..end.line + 1,
674            start_byte: self.byte(start.line, start.column)?,
675            end_byte: self.byte(end.line, end.column)?,
676        })
677    }
678}
679
680/// Every name a parameter pattern binds, in source order. Types are not
681/// visited, so a path in a type is not a binding.
682struct Bindings<F> {
683    visit: F,
684    expressions: bool,
685}
686
687impl<'ast, F: FnMut(&syn::Ident)> Visit<'ast> for Bindings<F> {
688    fn visit_pat(&mut self, pattern: &'ast syn::Pat) {
689        if !self.expressions {
690            match pattern {
691                syn::Pat::Const(_) => return,
692                syn::Pat::Guard(guard) => {
693                    self.visit_pat(&guard.pat);
694                    return;
695                }
696                _ => {}
697            }
698        }
699        syn::visit::visit_pat(self, pattern);
700    }
701    fn visit_pat_ident(&mut self, pat: &'ast syn::PatIdent) {
702        (self.visit)(&pat.ident);
703        syn::visit::visit_pat_ident(self, pat);
704    }
705
706    fn visit_type(&mut self, _: &'ast syn::Type) {}
707
708    fn visit_expr(&mut self, expression: &'ast Expr) {
709        if self.expressions {
710            syn::visit::visit_expr(self, expression);
711        }
712    }
713}
714
715/// Visit syntactic identifier bindings of a pattern in source order.
716/// Type and expression subtrees are excluded. This observes syntax, not type inference or whether
717/// an otherwise ambiguous identifier denotes a resolved constant.
718pub fn visit_pattern_bindings(pattern: &syn::Pat, visit: impl FnMut(&syn::Ident)) {
719    Bindings {
720        visit,
721        expressions: false,
722    }
723    .visit_pat(pattern);
724}
725
726/// The fact bytes a file takes, charged on its parse thread as each fact is
727/// built: its fixed size and the length of every string and list it owns.
728struct FactMeter {
729    allowance: FactAllowance,
730    spent: Cell<usize>,
731}
732
733impl FactMeter {
734    /// A meter for attributes that are read for their meaning and not kept,
735    /// whose facts are dropped at once.
736    fn scratch() -> Self {
737        Self {
738            allowance: FactAllowance {
739                spent: 0,
740                limit: usize::MAX,
741            },
742            spent: Cell::new(0),
743        }
744    }
745
746    /// Charge `bytes` for a fact built at `line`.
747    fn charge(&self, bytes: usize, line: usize) -> Found<()> {
748        let spent = self.spent.get().saturating_add(bytes);
749        self.spent.set(spent);
750        if self.allowance.spent.saturating_add(spent) > self.allowance.limit {
751            Err(ExtractError::Budget {
752                line,
753                limit: self.allowance.limit,
754            })
755        } else {
756            Ok(())
757        }
758    }
759}
760
761/// The bytes a list of strings owns beyond its own header.
762fn strings_bytes(strings: &[String]) -> usize {
763    strings
764        .iter()
765        .map(|text| size_of::<String>() + text.capacity())
766        .sum()
767}
768
769/// The bytes a visibility owns beyond its own size.
770fn vis_bytes(vis: &Vis) -> usize {
771    match vis {
772        Vis::Restricted(text) => text.capacity(),
773        Vis::Inherited | Vis::Public => 0,
774    }
775}
776
777/// A string that holds no room beyond its text, so what it is charged is
778/// what it holds.
779fn fit(mut text: String) -> String {
780    text.shrink_to_fit();
781    text
782}
783
784/// Trim a list to its length and give the bytes of room it still holds beyond
785/// the elements, which are charged one by one.
786fn slack<T>(list: &mut Vec<T>) -> usize {
787    list.shrink_to_fit();
788    (list.capacity() - list.len()) * size_of::<T>()
789}
790
791fn unraw(ident: &syn::Ident) -> String {
792    let text = ident.to_string();
793    fit(match text.strip_prefix("r#") {
794        Some(plain) => plain.to_owned(),
795        None => text,
796    })
797}
798
799fn vis(visibility: &Visibility) -> Vis {
800    match visibility {
801        Visibility::Public(_) => Vis::Public,
802        Visibility::Restricted(restricted) => {
803            let path = restricted.path.to_token_stream().to_string();
804            Vis::Restricted(fit(if restricted.in_token.is_some() {
805                format!("in {path}")
806            } else {
807                path
808            }))
809        }
810        Visibility::Inherited => Vis::Inherited,
811    }
812}
813
814/// What the attributes of an item say.
815struct AttrSummary {
816    facts: Vec<AttrFact>,
817    documented: bool,
818    doc_hidden: bool,
819    own_test: TestRole,
820    macro_export: bool,
821    paths: PathAttrs,
822}
823
824fn string_value(expr: &Expr) -> Option<String> {
825    match expr {
826        Expr::Lit(ExprLit {
827            lit: Lit::Str(value),
828            ..
829        }) => Some(value.value()),
830        _ => None,
831    }
832}
833
834fn path_text(path: &syn::Path) -> String {
835    path.segments
836        .iter()
837        .map(|segment| segment.ident.to_string())
838        .collect::<Vec<_>>()
839        .join("::")
840}
841
842fn cfg_error(line: usize, message: String) -> ExtractError {
843    ExtractError::Cfg { line, message }
844}
845
846/// A `path` attribute that cannot be read, under `predicate` when a
847/// `cfg_attr` applies it. The module it is on is filled in by the module's
848/// own fact.
849fn path_error(line: usize, predicate: Option<&CfgExpr>, message: String) -> ExtractError {
850    ExtractError::PathAttr {
851        line,
852        module: None,
853        predicate: predicate.map(ToString::to_string),
854        message,
855    }
856}
857
858/// The `path` attribute value, which must be a string literal.
859fn path_value(expr: &Expr, line: usize, predicate: Option<&CfgExpr>) -> Found<String> {
860    string_value(expr).ok_or_else(|| {
861        let written: String = expr
862            .to_token_stream()
863            .to_string()
864            .chars()
865            .take(60)
866            .collect();
867        path_error(
868            line,
869            predicate,
870            format!("the value of `path` is not a string literal: `{written}`"),
871        )
872    })
873}
874
875/// Read the meta item inside `cfg(..)`.
876fn cfg_predicate(tokens: &proc_macro2::TokenStream, line: usize) -> Found<CfgExpr> {
877    let meta = crate::cfg::parse_meta
878        .parse2(tokens.clone())
879        .map_err(|error| cfg_error(line, error.to_string()))?;
880    CfgExpr::from_meta(&meta).map_err(|message| cfg_error(line, message))
881}
882
883/// Read `cfg_attr(predicate, attributes..)`, flattening nested `cfg_attr`
884/// into the combined predicate `all(outer, inner)`.
885fn apply_cfg_attr(
886    tokens: &proc_macro2::TokenStream,
887    outer: Option<&CfgExpr>,
888    summary: &mut AttrSummary,
889    line: usize,
890    meter: &FactMeter,
891) -> Found<()> {
892    let metas = parse_list(tokens).map_err(|message| cfg_error(line, message))?;
893    let Some((first, applied)) = metas.split_first() else {
894        return Err(cfg_error(line, "`cfg_attr` has no predicate".to_owned()));
895    };
896    let own = CfgExpr::from_meta(first).map_err(|message| cfg_error(line, message))?;
897    let combined = match outer {
898        Some(outer) => CfgExpr::All(vec![outer.clone(), own]),
899        None => own,
900    };
901    for meta in applied {
902        match meta {
903            Meta::NameValue(pair) if pair.path.is_ident("path") => {
904                let conditional = ConditionalPath {
905                    predicate: fit(combined.to_string()),
906                    implies_test: combined.implies_test(),
907                    path: fit(path_value(&pair.value, line, Some(&combined))?),
908                };
909                meter.charge(
910                    size_of::<ConditionalPath>()
911                        + conditional.predicate.capacity()
912                        + conditional.path.capacity(),
913                    line,
914                )?;
915                summary.paths.conditional.push(conditional);
916            }
917            Meta::List(list) if list.path.is_ident("cfg_attr") => {
918                apply_cfg_attr(&list.tokens, Some(&combined), summary, line, meter)?;
919            }
920            Meta::List(list) if list.path.is_ident("cfg") => {
921                let inner = cfg_predicate(&list.tokens, line)?;
922                let both = CfgExpr::All(vec![combined.clone(), inner]);
923                if both.implies_test() && summary.own_test != TestRole::TestFn {
924                    summary.own_test = TestRole::CfgTest;
925                }
926            }
927            Meta::Path(path) if path.is_ident("test") => summary.own_test = TestRole::TestFn,
928            // Any other attribute that `cfg_attr` applies is kept in the
929            // arguments of the `cfg_attr` fact and changes nothing the index
930            // records.
931            Meta::Path(_) | Meta::List(_) | Meta::NameValue(_) => {}
932        }
933    }
934    Ok(())
935}
936
937/// True for `include_str!(..)` and its qualified spellings.
938fn is_include_str(expr: &Expr) -> bool {
939    matches!(expr, Expr::Macro(call) if call.mac.path.segments.last().is_some_and(|s| s.ident == "include_str"))
940}
941
942/// Read the attributes of an item, charging each fact to `meter`.
943fn summarize(attrs: &[Attribute], meter: &FactMeter) -> Found<AttrSummary> {
944    let mut summary = AttrSummary {
945        facts: Vec::new(),
946        documented: false,
947        doc_hidden: false,
948        own_test: TestRole::None,
949        macro_export: false,
950        paths: PathAttrs::default(),
951    };
952    for attr in attrs {
953        work::add(Work::Attributes, 1);
954        let line = attr.span().start().line;
955        let path = fit(path_text(attr.path()));
956        let args = fit(match &attr.meta {
957            Meta::Path(_) => String::new(),
958            Meta::List(list) => format!("({})", list.tokens),
959            Meta::NameValue(pair) => format!("= {}", pair.value.to_token_stream()),
960        });
961        meter.charge(
962            size_of::<AttrFact>() + path.capacity() + args.capacity(),
963            line,
964        )?;
965        summary.facts.push(AttrFact {
966            path: path.clone(),
967            args,
968        });
969        match (path.as_str(), &attr.meta) {
970            ("doc", Meta::NameValue(pair)) => {
971                // `include_str!` documentation is non-blank by construction.
972                if is_include_str(&pair.value)
973                    || string_value(&pair.value).is_some_and(|text| !text.trim().is_empty())
974                {
975                    summary.documented = true;
976                }
977            }
978            ("doc", Meta::List(list)) => {
979                if list.tokens.to_string().trim() == "hidden" {
980                    summary.doc_hidden = true;
981                }
982            }
983            ("macro_export", _) => summary.macro_export = true,
984            ("test", Meta::Path(_)) => summary.own_test = TestRole::TestFn,
985            ("test", _) => {
986                return Err(cfg_error(line, "`test` takes no arguments".to_owned()));
987            }
988            ("path", Meta::NameValue(pair)) => {
989                let value = fit(path_value(&pair.value, line, None)?);
990                meter.charge(size_of::<String>() + value.capacity(), line)?;
991                summary.paths.unconditional.push(value);
992            }
993            ("path", _) => {
994                return Err(path_error(
995                    line,
996                    None,
997                    "`path` must be `path = \"..\"`".to_owned(),
998                ));
999            }
1000            ("cfg", Meta::List(list)) => {
1001                let predicate = cfg_predicate(&list.tokens, line)?;
1002                if predicate.implies_test() && summary.own_test != TestRole::TestFn {
1003                    summary.own_test = TestRole::CfgTest;
1004                }
1005            }
1006            ("cfg", _) => {
1007                return Err(cfg_error(line, "`cfg` must be `cfg(predicate)`".to_owned()));
1008            }
1009            ("cfg_attr", Meta::List(list)) => {
1010                apply_cfg_attr(&list.tokens, None, &mut summary, line, meter)?;
1011            }
1012            ("cfg_attr", _) => {
1013                return Err(cfg_error(
1014                    line,
1015                    "`cfg_attr` must be `cfg_attr(predicate, attributes)`".to_owned(),
1016                ));
1017            }
1018            // Every other attribute is kept as written in `facts`; none of
1019            // them changes what the index records.
1020            _ => {}
1021        }
1022    }
1023    let line = attrs.last().map_or(1, |attr| attr.span().start().line);
1024    let room = slack(&mut summary.facts)
1025        + slack(&mut summary.paths.unconditional)
1026        + slack(&mut summary.paths.conditional);
1027    meter.charge(room, line)?;
1028    Ok(summary)
1029}
1030
1031/// Combine an item's own role with the role its enclosing modules give it.
1032fn role(own: TestRole, inherited: TestRole) -> TestRole {
1033    if own == TestRole::TestFn {
1034        TestRole::TestFn
1035    } else if own == TestRole::CfgTest || inherited != TestRole::None {
1036        TestRole::CfgTest
1037    } else {
1038        TestRole::None
1039    }
1040}
1041
1042/// The path a self type is written with: a plain path, or the first trait
1043/// of a trait object (`dyn Tr + Send` is written with `Tr`), inside any
1044/// parentheses. `None` for every other type.
1045fn self_path_of(ty: &syn::Type) -> Option<&syn::Path> {
1046    let mut ty = ty;
1047    // Parentheses nest no deeper than the pre-scan's delimiter budget.
1048    loop {
1049        match ty {
1050            syn::Type::Paren(inner) => ty = &inner.elem,
1051            syn::Type::Group(inner) => ty = &inner.elem,
1052            syn::Type::Path(path) if path.qself.is_none() => return Some(&path.path),
1053            syn::Type::TraitObject(object) => {
1054                return object.bounds.iter().find_map(|bound| match bound {
1055                    syn::TypeParamBound::Trait(found) => Some(&found.path),
1056                    _ => None,
1057                });
1058            }
1059            _ => return None,
1060        }
1061    }
1062}
1063
1064/// The refusal of an item the index does not model, naming its first line
1065/// and the start of its text.
1066fn unsupported(item: &impl quote::ToTokens) -> ExtractError {
1067    ExtractError::Unsupported {
1068        line: item.span().start().line,
1069        what: item
1070            .to_token_stream()
1071            .to_string()
1072            .chars()
1073            .take(60)
1074            .collect(),
1075    }
1076}
1077
1078/// The test role of a `use` declaration with the attributes `attrs`, and
1079/// whether they hold `#[doc(hidden)]`; the attributes are read for their
1080/// meaning and not kept.
1081fn use_role(attrs: &[Attribute], inherited: TestRole) -> Found<UseRole> {
1082    let summary = summarize(attrs, &FactMeter::scratch())?;
1083    Ok(UseRole {
1084        test: role(summary.own_test, inherited),
1085        doc_hidden: summary.doc_hidden,
1086        configuration: ConfigurationDependence::of(&summary.facts),
1087    })
1088}
1089
1090/// What the attributes of a `use` declaration say of it.
1091#[derive(Debug, Clone, Copy)]
1092struct UseRole {
1093    test: TestRole,
1094    doc_hidden: bool,
1095    configuration: ConfigurationDependence,
1096}
1097
1098struct Extractor<'t> {
1099    positions: Positions<'t>,
1100    meter: FactMeter,
1101}
1102
1103impl Extractor<'_> {
1104    #[expect(
1105        clippy::too_many_arguments,
1106        reason = "every field of an item fact comes from the syntax node separately"
1107    )]
1108    fn item(
1109        &self,
1110        name: &syn::Ident,
1111        kind: ItemKind,
1112        vis_of: &Visibility,
1113        attrs: &[Attribute],
1114        whole: proc_macro2::Span,
1115        body: Option<proc_macro2::Span>,
1116        inherited: TestRole,
1117        members: Vec<ItemFact>,
1118    ) -> Found<ItemFact> {
1119        let name_line = name.span().start().line;
1120        let summary = summarize(attrs, &self.meter)?;
1121        let name = unraw(name);
1122        let vis = vis(vis_of);
1123        self.meter.charge(
1124            size_of::<ItemFact>() + name.capacity() + vis_bytes(&vis),
1125            name_line,
1126        )?;
1127        Ok(ItemFact {
1128            name,
1129            renamed_from: None,
1130            kind,
1131            name_line,
1132            span: self.positions.span(whole)?,
1133            body: body.map(|span| self.positions.span(span)).transpose()?,
1134            detail: None,
1135            vis,
1136            attrs: summary.facts,
1137            documented: summary.documented,
1138            doc_hidden: summary.doc_hidden,
1139            test: role(summary.own_test, inherited),
1140            macro_export: summary.macro_export,
1141            members,
1142            shape: None,
1143            alias: None,
1144        })
1145    }
1146
1147    /// `fact` with the parameter bindings of `sig`.
1148    fn with_bindings(
1149        &self,
1150        mut fact: ItemFact,
1151        sig: &syn::Signature,
1152        method: bool,
1153    ) -> Found<ItemFact> {
1154        let mut names = Vec::new();
1155        for input in &sig.inputs {
1156            match input {
1157                syn::FnArg::Receiver(_) => names.push("self".to_owned()),
1158                syn::FnArg::Typed(typed) => {
1159                    // Preserve the parameter observation used by normal form v1.
1160                    // Lexical pattern observers exclude expression-local binders.
1161                    Bindings {
1162                        visit: |ident: &syn::Ident| names.push(ident.to_string()),
1163                        expressions: true,
1164                    }
1165                    .visit_pat(&typed.pat);
1166                }
1167            }
1168        }
1169        let method_requires_inference =
1170            method && (!sig.generics.params.is_empty() || sig.generics.where_clause.is_some());
1171        if !names.is_empty() || method_requires_inference {
1172            self.meter.charge(
1173                size_of::<ItemDetail>() + strings_bytes(&names),
1174                fact.name_line,
1175            )?;
1176            fact.detail = Some(Arc::new(ItemDetail {
1177                bindings: names,
1178                method_requires_inference,
1179                ..ItemDetail::default()
1180            }));
1181        }
1182        Ok(fact)
1183    }
1184
1185    /// `fact` with the range between `eq` and `semi` as its initializer.
1186    fn with_initializer(
1187        &self,
1188        mut fact: ItemFact,
1189        eq: proc_macro2::Span,
1190        semi: proc_macro2::Span,
1191    ) -> Found<ItemFact> {
1192        let start = self.positions.span(eq)?.end_byte;
1193        let end = self.positions.span(semi)?.start_byte;
1194        self.meter.charge(size_of::<ItemDetail>(), fact.name_line)?;
1195        fact.detail = Some(Arc::new(ItemDetail {
1196            initializer: Some(start..end),
1197            ..ItemDetail::default()
1198        }));
1199        Ok(fact)
1200    }
1201
1202    fn module(&self, items: &[Item], inherited: TestRole, line: usize) -> Found<ModBody> {
1203        let mut body = ModBody::default();
1204        for item in items {
1205            self.one(item, inherited, &mut body)?;
1206        }
1207        let room = slack(&mut body.items)
1208            + slack(&mut body.mods)
1209            + slack(&mut body.blocks)
1210            + slack(&mut body.uses)
1211            + slack(&mut body.impls)
1212            + slack(&mut body.unexpanded)
1213            + slack(&mut body.disabled);
1214        self.meter.charge(room, line)?;
1215        Ok(body)
1216    }
1217
1218    fn with_nominal(&self, mut fact: ItemFact, generics: &syn::Generics) -> Found<ItemFact> {
1219        let Some(arity) = nominal_const_arity(generics) else {
1220            return Ok(fact);
1221        };
1222        self.meter.charge(size_of::<ItemDetail>(), fact.name_line)?;
1223        fact.detail = Some(Arc::new(ItemDetail {
1224            nominal_const_arity: Some(arity),
1225            ..ItemDetail::default()
1226        }));
1227        Ok(fact)
1228    }
1229
1230    fn enum_fact(
1231        &self,
1232        declaration: &syn::ItemEnum,
1233        whole: proc_macro2::Span,
1234        inherited: TestRole,
1235    ) -> Found<ItemFact> {
1236        let mut fact = self.item(
1237            &declaration.ident,
1238            ItemKind::Enum,
1239            &declaration.vis,
1240            &declaration.attrs,
1241            whole,
1242            Some(declaration.brace_token.span.join()),
1243            inherited,
1244            Vec::new(),
1245        )?;
1246        if !has_written_variant_roster(&fact.attrs) {
1247            return self.with_nominal(fact, &declaration.generics);
1248        }
1249        self.meter.charge(
1250            size_of::<ItemDetail>() + declaration.variants.len() * size_of::<VariantFact>(),
1251            fact.name_line,
1252        )?;
1253        let mut variants = Vec::with_capacity(declaration.variants.len());
1254        for variant in &declaration.variants {
1255            let name = unraw(&variant.ident);
1256            self.meter.charge(name.capacity(), fact.name_line)?;
1257            let shape = match variant.fields {
1258                syn::Fields::Named(_) => FieldShape::Named,
1259                syn::Fields::Unnamed(_) => FieldShape::Tuple,
1260                syn::Fields::Unit => FieldShape::Unit,
1261            };
1262            variants.push(VariantFact { name, shape });
1263        }
1264        fact.detail = Some(Arc::new(ItemDetail {
1265            nominal_const_arity: nominal_const_arity(&declaration.generics),
1266            variants: Some(variants.into_boxed_slice()),
1267            ..ItemDetail::default()
1268        }));
1269        Ok(fact)
1270    }
1271
1272    fn struct_fact(
1273        &self,
1274        s: &syn::ItemStruct,
1275        whole: proc_macro2::Span,
1276        inherited: TestRole,
1277    ) -> Found<ItemFact> {
1278        let (braces, shape) = match &s.fields {
1279            syn::Fields::Named(named) => (Some(named.brace_token.span.join()), FieldShape::Named),
1280            syn::Fields::Unnamed(_) => (None, FieldShape::Tuple),
1281            syn::Fields::Unit => (None, FieldShape::Unit),
1282        };
1283        let mut fact = self.item(
1284            &s.ident,
1285            ItemKind::Struct,
1286            &s.vis,
1287            &s.attrs,
1288            whole,
1289            braces,
1290            inherited,
1291            Vec::new(),
1292        )?;
1293        fact.shape = Some(shape);
1294        self.with_nominal(fact, &s.generics)
1295    }
1296
1297    fn union_fact(
1298        &self,
1299        u: &syn::ItemUnion,
1300        whole: proc_macro2::Span,
1301        inherited: TestRole,
1302    ) -> Found<ItemFact> {
1303        let mut fact = self.item(
1304            &u.ident,
1305            ItemKind::Union,
1306            &u.vis,
1307            &u.attrs,
1308            whole,
1309            Some(u.fields.brace_token.span.join()),
1310            inherited,
1311            Vec::new(),
1312        )?;
1313        fact.shape = Some(FieldShape::Named);
1314        self.with_nominal(fact, &u.generics)
1315    }
1316
1317    fn trait_fact(
1318        &self,
1319        t: &syn::ItemTrait,
1320        whole: proc_macro2::Span,
1321        inherited: TestRole,
1322        body: &mut ModBody,
1323    ) -> Found<ItemFact> {
1324        let own = summarize(&t.attrs, &FactMeter::scratch())?;
1325        let inside = role(own.own_test, inherited);
1326        let mut members = Vec::new();
1327        for member in &t.items {
1328            match member {
1329                syn::TraitItem::Macro(invocation) => body.unexpanded.push(self.unexpanded(
1330                    &invocation.attrs,
1331                    &invocation.mac,
1332                    member.span(),
1333                    inside,
1334                )?),
1335                syn::TraitItem::Verbatim(tokens) if verbatim::definitely_disabled(tokens) => {
1336                    self.record_disabled(member.span(), body)?;
1337                }
1338                _ => members.push(self.trait_member(member, inside)?),
1339            }
1340        }
1341        self.meter
1342            .charge(slack(&mut members), t.ident.span().start().line)?;
1343        self.item(
1344            &t.ident,
1345            ItemKind::Trait,
1346            &t.vis,
1347            &t.attrs,
1348            whole,
1349            Some(t.brace_token.span.join()),
1350            inherited,
1351            members,
1352        )
1353    }
1354
1355    /// The items that are one named item with no further structure.
1356    fn named(
1357        &self,
1358        item: &Item,
1359        inherited: TestRole,
1360        body: &mut ModBody,
1361    ) -> Found<Option<ItemFact>> {
1362        let whole = item.span();
1363        let fact = match item {
1364            Item::Fn(f) => {
1365                let fact = self.item(
1366                    &f.sig.ident,
1367                    ItemKind::Fn,
1368                    &f.vis,
1369                    &f.attrs,
1370                    whole,
1371                    Some(f.block.brace_token.span.join()),
1372                    inherited,
1373                    Vec::new(),
1374                )?;
1375                self.with_bindings(fact, &f.sig, false)?
1376            }
1377            Item::Struct(s) => self.struct_fact(s, whole, inherited)?,
1378            Item::Enum(e) => self.enum_fact(e, whole, inherited)?,
1379            Item::Union(u) => self.union_fact(u, whole, inherited)?,
1380            Item::Trait(t) => self.trait_fact(t, whole, inherited, body)?,
1381            Item::Type(t) => {
1382                let mut fact = self.item(
1383                    &t.ident,
1384                    ItemKind::TypeAlias,
1385                    &t.vis,
1386                    &t.attrs,
1387                    whole,
1388                    None,
1389                    inherited,
1390                    Vec::new(),
1391                )?;
1392                fact.alias = match &*t.ty {
1393                    syn::Type::Path(path) if path.qself.is_none() => Some(PathFact {
1394                        segments: path.path.segments.iter().map(|s| unraw(&s.ident)).collect(),
1395                        leading_colon: path.path.leading_colon.is_some(),
1396                    }),
1397                    _ => None,
1398                };
1399                if let Some(alias) = &fact.alias {
1400                    self.meter
1401                        .charge(strings_bytes(&alias.segments), fact.name_line)?;
1402                }
1403                if let Some(arity) = alias_const_arity(t) {
1404                    self.meter.charge(size_of::<ItemDetail>(), fact.name_line)?;
1405                    fact.detail = Some(Arc::new(ItemDetail {
1406                        alias_const_arity: Some(arity),
1407                        ..ItemDetail::default()
1408                    }));
1409                }
1410                fact
1411            }
1412            Item::Const(c) => {
1413                let fact = self.item(
1414                    &c.ident,
1415                    if c.ident == "_" {
1416                        ItemKind::UnnamedConst
1417                    } else {
1418                        ItemKind::Const
1419                    },
1420                    &c.vis,
1421                    &c.attrs,
1422                    whole,
1423                    None,
1424                    inherited,
1425                    Vec::new(),
1426                )?;
1427                self.with_initializer(fact, c.eq_token.span(), c.semi_token.span())?
1428            }
1429            Item::Static(s) => {
1430                let fact = self.item(
1431                    &s.ident,
1432                    ItemKind::Static,
1433                    &s.vis,
1434                    &s.attrs,
1435                    whole,
1436                    None,
1437                    inherited,
1438                    Vec::new(),
1439                )?;
1440                self.with_initializer(fact, s.eq_token.span(), s.semi_token.span())?
1441            }
1442            // Modules, impls, `use`, macros and `extern` items are read by the
1443            // caller.
1444            _ => return Ok(None),
1445        };
1446        Ok(Some(fact))
1447    }
1448
1449    fn one(&self, item: &Item, inherited: TestRole, body: &mut ModBody) -> Found<()> {
1450        self.blocks(item, inherited, &mut body.blocks)?;
1451        if let Some(fact) = self.named(item, inherited, body)? {
1452            body.items.push(fact);
1453            return Ok(());
1454        }
1455        let whole = item.span();
1456        match item {
1457            Item::Macro(m) => {
1458                if let Some(ident) = &m.ident {
1459                    body.items.push(self.item(
1460                        ident,
1461                        ItemKind::MacroRules,
1462                        &Visibility::Inherited,
1463                        &m.attrs,
1464                        whole,
1465                        Some(m.mac.delimiter.span().join()),
1466                        inherited,
1467                        Vec::new(),
1468                    )?);
1469                } else {
1470                    body.unexpanded
1471                        .push(self.unexpanded(&m.attrs, &m.mac, whole, inherited)?);
1472                }
1473            }
1474            Item::ExternCrate(e) => {
1475                let mut fact = self.item(
1476                    e.rename.as_ref().map_or(&e.ident, |(_, alias)| alias),
1477                    ItemKind::ExternCrate,
1478                    &e.vis,
1479                    &e.attrs,
1480                    whole,
1481                    None,
1482                    inherited,
1483                    Vec::new(),
1484                )?;
1485                if e.rename.is_some() {
1486                    let original = unraw(&e.ident);
1487                    self.meter.charge(original.capacity(), fact.name_line)?;
1488                    fact.renamed_from = Some(original);
1489                }
1490                body.items.push(fact);
1491            }
1492            Item::ForeignMod(block) => {
1493                let own = summarize(&block.attrs, &FactMeter::scratch())?;
1494                let inside = role(own.own_test, inherited);
1495                for foreign in &block.items {
1496                    self.foreign(foreign, inside, body)?;
1497                }
1498            }
1499            Item::Mod(m) => body.mods.push(self.module_fact(m, inherited)?),
1500            Item::Impl(i) => {
1501                let implementation = self.impl_fact(i, inherited, body)?;
1502                body.impls.push(implementation);
1503            }
1504            Item::Use(u) => {
1505                let role = use_role(&u.attrs, inherited)?;
1506                body.uses.push(self.use_fact(
1507                    role,
1508                    &u.vis,
1509                    u.leading_colon.is_some(),
1510                    &u.tree,
1511                    whole,
1512                )?);
1513            }
1514            Item::Verbatim(tokens) => match verbatim::item(tokens) {
1515                // Each member is a `use` of its own, spanning the whole
1516                // declaration, as the separate declarations would bind.
1517                Some(Verbatim::UseGroup(group)) => {
1518                    // The attributes of the whole declaration are read once,
1519                    // so the work stays linear in the text however many
1520                    // members share them.
1521                    let role = use_role(&group.attrs, inherited)?;
1522                    for member in &group.members {
1523                        body.uses.push(self.use_fact(
1524                            role,
1525                            &group.vis,
1526                            member.leading_colon,
1527                            &member.tree,
1528                            whole,
1529                        )?);
1530                    }
1531                }
1532                Some(Verbatim::Bodiless(read)) => {
1533                    body.items
1534                        .push(self.bodiless(&read, whole, inherited, false)?);
1535                }
1536                None if verbatim::definitely_disabled(tokens) => {
1537                    self.record_disabled(whole, body)?;
1538                }
1539                None => return Err(unsupported(item)),
1540            },
1541            other => return Err(unsupported(other)),
1542        }
1543        Ok(())
1544    }
1545
1546    fn record_disabled(&self, whole: proc_macro2::Span, body: &mut ModBody) -> Found<()> {
1547        let span = self.positions.span(whole)?;
1548        self.meter.charge(size_of::<SpanFact>(), span.lines.start)?;
1549        body.disabled.push(span);
1550        Ok(())
1551    }
1552
1553    /// Observe item syntax without claiming the invocation's generated names.
1554    fn unexpanded(
1555        &self,
1556        attrs: &[Attribute],
1557        invocation: &syn::Macro,
1558        whole: proc_macro2::Span,
1559        inherited: TestRole,
1560    ) -> Found<UnexpandedFact> {
1561        let line = whole.start().line;
1562        let summary = summarize(attrs, &FactMeter::scratch())?;
1563        let mut invoked = if invocation.path.leading_colon.is_some() {
1564            "::".to_owned()
1565        } else {
1566            String::new()
1567        };
1568        invoked.push_str(&path_text(&invocation.path));
1569        let invoked = fit(invoked);
1570        self.meter
1571            .charge(size_of::<UnexpandedFact>() + invoked.capacity(), line)?;
1572        let mut identifiers = Vec::new();
1573        let mut stack =
1574            purrdf_lex::walk::WorkList::<_, 8>::with(invocation.tokens.clone().into_iter());
1575        while let Some(mut tokens) = stack.pop() {
1576            while let Some(token) = tokens.next() {
1577                match token {
1578                    proc_macro2::TokenTree::Ident(ident) => {
1579                        let name = unraw(&ident);
1580                        self.meter
1581                            .charge(size_of::<String>() + name.capacity(), line)?;
1582                        identifiers.push(name);
1583                    }
1584                    proc_macro2::TokenTree::Group(group) => {
1585                        // Conservatively charge spill room before growing the native stack.
1586                        self.meter
1587                            .charge(4 * size_of::<proc_macro2::token_stream::IntoIter>(), line)?;
1588                        stack.push(tokens);
1589                        stack.push(group.stream().into_iter());
1590                        break;
1591                    }
1592                    _ => {}
1593                }
1594            }
1595        }
1596        self.meter.charge(slack(&mut identifiers), line)?;
1597        Ok(UnexpandedFact {
1598            invoked,
1599            span: self.positions.span(whole)?,
1600            test: role(summary.own_test, inherited),
1601            identifiers,
1602        })
1603    }
1604
1605    /// The fact of one `use` declaration spanning `whole`, of the test role
1606    /// and the `doc(hidden)` flag that [`use_role`] read from its attributes.
1607    fn use_fact(
1608        &self,
1609        role: UseRole,
1610        vis_of: &Visibility,
1611        leading_colon: bool,
1612        tree: &syn::UseTree,
1613        whole: proc_macro2::Span,
1614    ) -> Found<UseFact> {
1615        let line = whole.start().line;
1616        let vis = vis(vis_of);
1617        self.meter
1618            .charge(size_of::<UseFact>() + vis_bytes(&vis), line)?;
1619        Ok(UseFact {
1620            line,
1621            span: self.positions.span(whole)?,
1622            vis,
1623            leading_colon,
1624            tree: self.use_tree(tree, line)?,
1625            test: role.test,
1626            doc_hidden: role.doc_hidden,
1627            configuration: role.configuration,
1628        })
1629    }
1630
1631    /// The fact of a function with no body or a type with no definition, read
1632    /// from verbatim tokens: a function or a type alias with no body span.
1633    fn bodiless(
1634        &self,
1635        read: &Bodiless,
1636        whole: proc_macro2::Span,
1637        inherited: TestRole,
1638        method: bool,
1639    ) -> Found<ItemFact> {
1640        match read {
1641            Bodiless::Fn(f) => {
1642                let fact = self.item(
1643                    &f.sig.ident,
1644                    ItemKind::Fn,
1645                    &f.vis,
1646                    &f.attrs,
1647                    whole,
1648                    None,
1649                    inherited,
1650                    Vec::new(),
1651                )?;
1652                self.with_bindings(fact, &f.sig, method)
1653            }
1654            Bodiless::Type(t) => self.item(
1655                &t.ident,
1656                ItemKind::TypeAlias,
1657                &t.vis,
1658                &t.attrs,
1659                whole,
1660                None,
1661                inherited,
1662                Vec::new(),
1663            ),
1664        }
1665    }
1666
1667    fn foreign(
1668        &self,
1669        item: &syn::ForeignItem,
1670        inherited: TestRole,
1671        body: &mut ModBody,
1672    ) -> Found<()> {
1673        let whole = item.span();
1674        match item {
1675            syn::ForeignItem::Fn(f) => body.items.push(self.item(
1676                &f.sig.ident,
1677                ItemKind::ForeignFn,
1678                &f.vis,
1679                &f.attrs,
1680                whole,
1681                None,
1682                inherited,
1683                Vec::new(),
1684            )?),
1685            syn::ForeignItem::Static(s) => body.items.push(self.item(
1686                &s.ident,
1687                ItemKind::ForeignStatic,
1688                &s.vis,
1689                &s.attrs,
1690                whole,
1691                None,
1692                inherited,
1693                Vec::new(),
1694            )?),
1695            syn::ForeignItem::Type(t) => body.items.push(self.item(
1696                &t.ident,
1697                ItemKind::ForeignType,
1698                &t.vis,
1699                &t.attrs,
1700                whole,
1701                None,
1702                inherited,
1703                Vec::new(),
1704            )?),
1705            syn::ForeignItem::Macro(invocation) => body.unexpanded.push(self.unexpanded(
1706                &invocation.attrs,
1707                &invocation.mac,
1708                whole,
1709                inherited,
1710            )?),
1711            other => return Err(unsupported(other)),
1712        }
1713        Ok(())
1714    }
1715
1716    fn trait_member(&self, member: &syn::TraitItem, inherited: TestRole) -> Found<ItemFact> {
1717        let whole = member.span();
1718        match member {
1719            syn::TraitItem::Fn(f) => self
1720                .item(
1721                    &f.sig.ident,
1722                    ItemKind::Fn,
1723                    &Visibility::Inherited,
1724                    &f.attrs,
1725                    whole,
1726                    f.default
1727                        .as_ref()
1728                        .map(|block| block.brace_token.span.join()),
1729                    inherited,
1730                    Vec::new(),
1731                )
1732                .and_then(|fact| self.with_bindings(fact, &f.sig, false)),
1733            syn::TraitItem::Const(c) => self
1734                .item(
1735                    &c.ident,
1736                    ItemKind::Const,
1737                    &Visibility::Inherited,
1738                    &c.attrs,
1739                    whole,
1740                    None,
1741                    inherited,
1742                    Vec::new(),
1743                )
1744                .and_then(|fact| match &c.default {
1745                    Some((eq, _)) => self.with_initializer(fact, eq.span(), c.semi_token.span()),
1746                    None => Ok(fact),
1747                }),
1748            syn::TraitItem::Type(t) => self.item(
1749                &t.ident,
1750                ItemKind::TypeAlias,
1751                &Visibility::Inherited,
1752                &t.attrs,
1753                whole,
1754                None,
1755                inherited,
1756                Vec::new(),
1757            ),
1758            other => Err(unsupported(other)),
1759        }
1760    }
1761
1762    fn impl_member(
1763        &self,
1764        member: &syn::ImplItem,
1765        inherited: TestRole,
1766        body: &mut ModBody,
1767    ) -> Found<Option<ItemFact>> {
1768        let whole = member.span();
1769        let fact = match member {
1770            syn::ImplItem::Fn(f) => {
1771                let fact = self.item(
1772                    &f.sig.ident,
1773                    ItemKind::Fn,
1774                    &f.vis,
1775                    &f.attrs,
1776                    whole,
1777                    Some(f.block.brace_token.span.join()),
1778                    inherited,
1779                    Vec::new(),
1780                )?;
1781                self.with_bindings(fact, &f.sig, true)?
1782            }
1783            syn::ImplItem::Const(c) => {
1784                let fact = self.item(
1785                    &c.ident,
1786                    ItemKind::Const,
1787                    &c.vis,
1788                    &c.attrs,
1789                    whole,
1790                    None,
1791                    inherited,
1792                    Vec::new(),
1793                )?;
1794                self.with_initializer(fact, c.eq_token.span(), c.semi_token.span())?
1795            }
1796            syn::ImplItem::Type(t) => self.item(
1797                &t.ident,
1798                ItemKind::TypeAlias,
1799                &t.vis,
1800                &t.attrs,
1801                whole,
1802                None,
1803                inherited,
1804                Vec::new(),
1805            )?,
1806            syn::ImplItem::Verbatim(tokens) => match verbatim::member(tokens) {
1807                Some(read) => self.bodiless(&read, whole, inherited, true)?,
1808                None if verbatim::definitely_disabled(tokens) => {
1809                    self.record_disabled(whole, body)?;
1810                    return Ok(None);
1811                }
1812                None => return Err(unsupported(member)),
1813            },
1814            other => return Err(unsupported(other)),
1815        };
1816        Ok(Some(fact))
1817    }
1818
1819    fn impl_fact(
1820        &self,
1821        block: &syn::ItemImpl,
1822        inherited: TestRole,
1823        body: &mut ModBody,
1824    ) -> Found<ImplFact> {
1825        let whole = block.span();
1826        let line = block.impl_token.span.start().line;
1827        let summary = summarize(&block.attrs, &FactMeter::scratch())?;
1828        let test = role(summary.own_test, inherited);
1829        let mut items = Vec::new();
1830        for member in &block.items {
1831            if let syn::ImplItem::Macro(invocation) = member {
1832                body.unexpanded.push(self.unexpanded(
1833                    &invocation.attrs,
1834                    &invocation.mac,
1835                    member.span(),
1836                    test,
1837                )?);
1838            } else if let Some(fact) = self.impl_member(member, test, body)? {
1839                items.push(fact);
1840            }
1841        }
1842        let written_path = self_path_of(&block.self_ty);
1843        let self_path: Option<Vec<String>> = written_path.map(|path| {
1844            path.segments
1845                .iter()
1846                .map(|segment| unraw(&segment.ident))
1847                .collect()
1848        });
1849        let self_leading_colon = written_path.is_some_and(|path| path.leading_colon.is_some());
1850        let mut generics = block
1851            .generics
1852            .params
1853            .iter()
1854            .filter_map(|param| match param {
1855                syn::GenericParam::Type(param) => Some(unraw(&param.ident)),
1856                syn::GenericParam::Const(param) => Some(unraw(&param.ident)),
1857                syn::GenericParam::Lifetime(_) => None,
1858            })
1859            .collect::<Vec<_>>();
1860        // A negative impl keeps its `!` in the written trait path.
1861        let trait_path = block.trait_.as_ref().map(|(path, _)| {
1862            let written = path.to_token_stream().to_string();
1863            fit(match block.modifiers.polarity {
1864                Some(_) => format!("!{written}"),
1865                None => written,
1866            })
1867        });
1868        let trait_segments = block.trait_.as_ref().map(|(path, _)| PathFact {
1869            segments: path.segments.iter().map(|s| unraw(&s.ident)).collect(),
1870            leading_colon: path.leading_colon.is_some(),
1871        });
1872        let self_type = fit(block.self_ty.to_token_stream().to_string());
1873        self.meter.charge(
1874            size_of::<ImplFact>()
1875                + trait_path.as_ref().map_or(0, String::capacity)
1876                + trait_segments
1877                    .as_ref()
1878                    .map_or(0, |path| strings_bytes(&path.segments))
1879                + self_type.capacity()
1880                + self_path.as_deref().map_or(0, strings_bytes)
1881                + strings_bytes(&generics)
1882                + slack(&mut generics)
1883                + slack(&mut items),
1884            line,
1885        )?;
1886        Ok(ImplFact {
1887            line,
1888            span: self.positions.span(whole)?,
1889            body: self.positions.span(block.brace_token.span.join())?,
1890            trait_path,
1891            trait_segments,
1892            self_type,
1893            self_path,
1894            self_leading_colon,
1895            generics,
1896            unconditional_self: unconditional_self(block).then_some(block.generics.params.len()),
1897            items,
1898            test,
1899        })
1900    }
1901
1902    fn module_fact(&self, module: &syn::ItemMod, inherited: TestRole) -> Found<ModFact> {
1903        let name_line = module.ident.span().start().line;
1904        let summary = summarize(&module.attrs, &self.meter).map_err(|error| match error {
1905            ExtractError::PathAttr {
1906                line,
1907                module: None,
1908                predicate,
1909                message,
1910            } => ExtractError::PathAttr {
1911                line,
1912                module: Some(unraw(&module.ident)),
1913                predicate,
1914                message,
1915            },
1916            other => other,
1917        })?;
1918        let test = role(summary.own_test, inherited);
1919        let (body_span, inline) = match &module.content {
1920            Some((brace, items)) => (
1921                Some(self.positions.span(brace.span.join())?),
1922                Some(self.module(items, test, name_line)?),
1923            ),
1924            None => (None, None),
1925        };
1926        let name = unraw(&module.ident);
1927        let vis = vis(&module.vis);
1928        self.meter.charge(
1929            size_of::<ModFact>() + name.capacity() + vis_bytes(&vis),
1930            name_line,
1931        )?;
1932        let name_start = self.positions.span(module.ident.span())?.start_byte;
1933        Ok(ModFact {
1934            name,
1935            name_line,
1936            name_start,
1937            span: self.positions.span(module.span())?,
1938            body_span,
1939            vis,
1940            attrs: summary.facts,
1941            documented: summary.documented,
1942            doc_hidden: summary.doc_hidden,
1943            test,
1944            paths: summary.paths,
1945            inline,
1946        })
1947    }
1948}
1949
1950impl Extractor<'_> {
1951    /// The module declarations inside the function bodies and initializers of
1952    /// `item`, appended to `found`. Items that hold no expression (types,
1953    /// `use` declarations, modules) hold none; a module is read whole by
1954    /// [`Self::module_fact`], which reads its own items the same way.
1955    fn blocks(&self, item: &Item, inherited: TestRole, found: &mut Vec<ModFact>) -> Found<()> {
1956        let attrs = match item {
1957            Item::Fn(f) => &f.attrs,
1958            Item::Const(c) => &c.attrs,
1959            Item::Static(s) => &s.attrs,
1960            Item::Impl(i) => &i.attrs,
1961            Item::Trait(t) => &t.attrs,
1962            _ => return Ok(()),
1963        };
1964        let own = summarize(attrs, &FactMeter::scratch())?;
1965        let mut finder = BlockMods {
1966            extractor: self,
1967            test: role(own.own_test, inherited),
1968            found,
1969            failed: None,
1970        };
1971        finder.visit_item(item);
1972        finder.failed.map_or(Ok(()), Err)
1973    }
1974}
1975
1976/// Finds the module declarations nested in the expressions of an item, however
1977/// deep, without entering the module declarations themselves.
1978struct BlockMods<'e, 'f, 'x> {
1979    extractor: &'e Extractor<'x>,
1980    /// The test role of the innermost enclosing item.
1981    test: TestRole,
1982    found: &'f mut Vec<ModFact>,
1983    failed: Option<ExtractError>,
1984}
1985
1986impl BlockMods<'_, '_, '_> {
1987    /// Visit an item with the test role its own attributes give.
1988    fn within(&mut self, attrs: &[Attribute], visit: impl FnOnce(&mut Self)) {
1989        if self.failed.is_some() {
1990            return;
1991        }
1992        match summarize(attrs, &FactMeter::scratch()) {
1993            Ok(own) => {
1994                let outer = self.test;
1995                self.test = role(own.own_test, outer);
1996                visit(self);
1997                self.test = outer;
1998            }
1999            Err(error) => self.failed = Some(error),
2000        }
2001    }
2002}
2003
2004impl<'ast> Visit<'ast> for BlockMods<'_, '_, '_> {
2005    // Types, patterns, generics and the items other than functions, constants,
2006    // statics, impl blocks, traits and modules can hold an expression (an
2007    // array length, an enum discriminant), but this scan skips them: the
2008    // configured selection does not select the attributed positions inside
2009    // them, so a module found there could sit under an attribute that a
2010    // configured load never evaluated.
2011    fn visit_type(&mut self, _: &'ast syn::Type) {}
2012
2013    fn visit_pat(&mut self, _: &'ast syn::Pat) {}
2014
2015    fn visit_generics(&mut self, _: &'ast syn::Generics) {}
2016
2017    fn visit_item(&mut self, item: &'ast Item) {
2018        if matches!(
2019            item,
2020            Item::Fn(_)
2021                | Item::Const(_)
2022                | Item::Static(_)
2023                | Item::Impl(_)
2024                | Item::Trait(_)
2025                | Item::Mod(_)
2026        ) {
2027            syn::visit::visit_item(self, item);
2028        }
2029    }
2030
2031    fn visit_item_mod(&mut self, module: &'ast syn::ItemMod) {
2032        if self.failed.is_some() {
2033            return;
2034        }
2035        match self.extractor.module_fact(module, self.test) {
2036            Ok(fact) => self.found.push(fact),
2037            Err(error) => self.failed = Some(error),
2038        }
2039    }
2040
2041    fn visit_item_fn(&mut self, function: &'ast syn::ItemFn) {
2042        self.within(&function.attrs, |this| {
2043            syn::visit::visit_item_fn(this, function);
2044        });
2045    }
2046
2047    fn visit_item_const(&mut self, item: &'ast syn::ItemConst) {
2048        self.within(&item.attrs, |this| {
2049            syn::visit::visit_item_const(this, item);
2050        });
2051    }
2052
2053    fn visit_item_static(&mut self, item: &'ast syn::ItemStatic) {
2054        self.within(&item.attrs, |this| {
2055            syn::visit::visit_item_static(this, item);
2056        });
2057    }
2058
2059    fn visit_item_impl(&mut self, item: &'ast syn::ItemImpl) {
2060        self.within(&item.attrs, |this| {
2061            syn::visit::visit_item_impl(this, item);
2062        });
2063    }
2064
2065    fn visit_item_trait(&mut self, item: &'ast syn::ItemTrait) {
2066        self.within(&item.attrs, |this| {
2067            syn::visit::visit_item_trait(this, item);
2068        });
2069    }
2070
2071    fn visit_impl_item_const(&mut self, item: &'ast syn::ImplItemConst) {
2072        self.within(&item.attrs, |this| {
2073            syn::visit::visit_impl_item_const(this, item);
2074        });
2075    }
2076
2077    fn visit_trait_item_const(&mut self, item: &'ast syn::TraitItemConst) {
2078        self.within(&item.attrs, |this| {
2079            syn::visit::visit_trait_item_const(this, item);
2080        });
2081    }
2082
2083    fn visit_impl_item_fn(&mut self, function: &'ast syn::ImplItemFn) {
2084        self.within(&function.attrs, |this| {
2085            syn::visit::visit_impl_item_fn(this, function);
2086        });
2087    }
2088
2089    fn visit_trait_item_fn(&mut self, function: &'ast syn::TraitItemFn) {
2090        self.within(&function.attrs, |this| {
2091            syn::visit::visit_trait_item_fn(this, function);
2092        });
2093    }
2094}
2095
2096impl Extractor<'_> {
2097    /// The owned form of a `use` tree, each node charged as it is built: its
2098    /// size and the names it holds.
2099    fn use_tree(&self, tree: &syn::UseTree, line: usize) -> Found<UseTree> {
2100        let node = match tree {
2101            syn::UseTree::Path(path) => {
2102                let name = unraw(&path.ident);
2103                self.meter.charge(name.capacity(), line)?;
2104                UseTree::Path {
2105                    name,
2106                    rest: Box::new(self.use_tree(&path.tree, line)?),
2107                }
2108            }
2109            syn::UseTree::Name(name) => {
2110                let name = unraw(&name.ident);
2111                self.meter.charge(name.capacity(), line)?;
2112                UseTree::Name(name)
2113            }
2114            syn::UseTree::Rename(rename) => {
2115                let (name, alias) = (unraw(&rename.ident), unraw(&rename.rename));
2116                self.meter
2117                    .charge(name.capacity() + alias.capacity(), line)?;
2118                UseTree::Rename { name, alias }
2119            }
2120            syn::UseTree::Glob(_) => UseTree::Glob,
2121            syn::UseTree::Group(group) => {
2122                let mut items = group
2123                    .items
2124                    .iter()
2125                    .map(|item| self.use_tree(item, line))
2126                    .collect::<Found<Vec<_>>>()?;
2127                self.meter.charge(slack(&mut items), line)?;
2128                UseTree::Group(items)
2129            }
2130        };
2131        self.meter.charge(size_of::<UseTree>(), line)?;
2132        Ok(node)
2133    }
2134}
2135
2136/// Read the facts of a parsed file. Runs on the parse thread.
2137///
2138/// Every fact is charged as it is built, against what `allowance` leaves of
2139/// the fact-bytes budget of the load. Returns the facts and the bytes they
2140/// were charged.
2141///
2142/// # Errors
2143///
2144/// Returns an [`ExtractError`] for a `cfg` predicate that cannot be read, an
2145/// item the index does not model, and facts that pass the budget, naming the
2146/// line of the fact that passed it.
2147pub(crate) fn extract(
2148    tree: &syn::File,
2149    text: &str,
2150    allowance: FactAllowance,
2151) -> Result<(FileFacts, usize), ExtractError> {
2152    let extractor = Extractor {
2153        positions: Positions::new(text),
2154        meter: FactMeter {
2155            allowance,
2156            spent: Cell::new(0),
2157        },
2158    };
2159    extractor.meter.charge(size_of::<FileFacts>(), 1)?;
2160    let own = summarize(&tree.attrs, &extractor.meter)?;
2161    let inherited = if own.own_test == TestRole::CfgTest {
2162        TestRole::CfgTest
2163    } else {
2164        TestRole::None
2165    };
2166    let facts = FileFacts {
2167        body: extractor.module(&tree.items, inherited, 1)?,
2168        documented: own.documented,
2169        doc_hidden: own.doc_hidden,
2170        attrs: own.facts,
2171    };
2172    Ok((facts, extractor.meter.spent.get()))
2173}
2174
2175#[cfg(test)]
2176mod tests {
2177    use super::*;
2178    use crate::RelPath;
2179
2180    #[test]
2181    fn a_column_is_turned_into_its_byte_offset_on_short_long_and_wide_lines() {
2182        let wide: String = "é".repeat(200);
2183        let long = "x".repeat(300);
2184        let text = format!("ab\n{long}\n{wide}\ntail");
2185        let positions = Positions::new(&text);
2186        // A short line, its end and its newline.
2187        assert_eq!(positions.byte(1, 1).ok(), Some(1));
2188        assert_eq!(positions.byte(1, 2).ok(), Some(2));
2189        // A long line of one-byte characters.
2190        assert_eq!(positions.byte(2, 0).ok(), Some(3));
2191        assert_eq!(positions.byte(2, 299).ok(), Some(3 + 299));
2192        // A long line of two-byte characters, before, on and after a mark.
2193        let start = 3 + 301;
2194        for column in [0, 1, 63, 64, 65, 130, 199, 200] {
2195            assert_eq!(
2196                positions.byte(3, column).ok(),
2197                Some(start + 2 * column),
2198                "column {column}"
2199            );
2200        }
2201        // The last line ends at the end of the text.
2202        assert_eq!(positions.byte(4, 4).ok(), Some(text.len()));
2203        // A column past its line and a line past the text are refused.
2204        assert!(matches!(
2205            positions.byte(3, 202),
2206            Err(ExtractError::Position { line: 3 })
2207        ));
2208        assert!(matches!(
2209            positions.byte(2, 302),
2210            Err(ExtractError::Position { line: 2 })
2211        ));
2212        assert!(matches!(
2213            positions.byte(9, 0),
2214            Err(ExtractError::Position { line: 9 })
2215        ));
2216    }
2217
2218    const DEMO: &str = "[package]\nname = \"demo\"\nversion = \"0.1.0\"\n";
2219
2220    /// The workspace of the package `demo` with `files` beside its manifest.
2221    fn loaded(files: &[(&str, &str)]) -> crate::Workspace {
2222        let mut all = vec![("Cargo.toml", DEMO)];
2223        all.extend_from_slice(files);
2224        let tree: crate::MemoryTree = all.into_iter().collect();
2225        crate::Workspace::load(&tree, &["."]).unwrap_or_else(|e| panic!("{e}"))
2226    }
2227
2228    #[test]
2229    fn facts_carry_names_lines_documentation_visibility_and_macro_export() {
2230        let ws = loaded(&[(
2231            "src/lib.rs",
2232            "/// Documented.\npub fn documented() {}\n\n#[doc(hidden)]\npub fn hidden() {}\n\n///\nfn blank() {}\n\n#[macro_export]\nmacro_rules! shout { () => {} }\n\npub(crate) struct S { x: u8 }\nextern crate alloc as heap;\n",
2233        )]);
2234        let file = ws
2235            .file(&RelPath::new("src/lib.rs").expect("path"))
2236            .expect("loaded");
2237        let items = &file.facts.body.items;
2238        assert_eq!(items[0].name, "documented");
2239        assert!(items[0].documented && !items[0].doc_hidden);
2240        assert_eq!(items[0].name_line, 2);
2241        assert!(!items[1].documented && items[1].doc_hidden);
2242        assert!(!items[2].documented);
2243        assert!(items[3].macro_export);
2244        assert_eq!(items[4].vis, Vis::Restricted("crate".to_owned()));
2245        assert!(items[4].body.is_some());
2246        assert_eq!(items[5].name, "heap");
2247        assert_eq!(items[5].renamed_from.as_deref(), Some("alloc"));
2248        let span = &items[0].span;
2249        assert_eq!(
2250            &file.text[span.start_byte..span.end_byte],
2251            "/// Documented.\npub fn documented() {}"
2252        );
2253    }
2254
2255    #[test]
2256    fn use_trees_and_impl_headers_are_recorded_as_written() {
2257        let ws = loaded(&[(
2258            "src/lib.rs",
2259            "use ::std::{fmt, io::{self, Read as R}};\nuse crate::a::*;\nstruct Holder<T>(T);\nimpl<T> Holder<T> { fn get(&self) {} }\nimpl Trait for a::b::Thing { fn run(&self) {} }\ntrait Trait {}\n",
2260        )]);
2261        let file = ws
2262            .file(&RelPath::new("src/lib.rs").expect("path"))
2263            .expect("loaded");
2264        assert_eq!(file.facts.body.uses.len(), 2);
2265        assert!(file.facts.body.uses[0].leading_colon);
2266        assert_eq!(file.facts.body.impls.len(), 2);
2267        let inherent = &file.facts.body.impls[0];
2268        assert_eq!(
2269            inherent.self_path.as_deref(),
2270            Some(&["Holder".to_owned()][..])
2271        );
2272        assert!(inherent.trait_path.is_none());
2273        assert_eq!(inherent.items[0].name, "get");
2274        let by_trait = &file.facts.body.impls[1];
2275        assert_eq!(by_trait.trait_path.as_deref(), Some("Trait"));
2276        assert_eq!(
2277            by_trait.self_path.as_deref(),
2278            Some(&["a".to_owned(), "b".to_owned(), "Thing".to_owned()][..])
2279        );
2280    }
2281
2282    #[test]
2283    fn facts_record_struct_shapes_unnamed_consts_leading_colons_and_documentation_forms() {
2284        let ws = loaded(&[
2285            (
2286                "src/lib.rs",
2287                "//! The crate.\n\
2288                 pub struct Unit;\n\
2289                 pub struct Tuple(u8);\n\
2290                 pub struct Named { x: u8 }\n\
2291                 const _: () = ();\n\
2292                 #[doc = include_str!(\"lib.rs\")]\n\
2293                 pub fn guide() {}\n\
2294                 impl Foo for ::other::Thing {}\n\
2295                 impl Foo for local::Thing {}\n\
2296                 mod documented;\n\
2297                 trait Foo {}\n",
2298            ),
2299            ("src/documented.rs", "//! Inner docs.\n"),
2300        ]);
2301        let lib = ws
2302            .file(&RelPath::new("src/lib.rs").expect("path"))
2303            .expect("loaded");
2304        assert!(lib.facts.documented);
2305        let shapes: Vec<_> = lib
2306            .facts
2307            .body
2308            .items
2309            .iter()
2310            .map(|i| (i.name.as_str(), i.shape))
2311            .collect();
2312        assert_eq!(
2313            shapes[..3],
2314            [
2315                ("Unit", Some(FieldShape::Unit)),
2316                ("Tuple", Some(FieldShape::Tuple)),
2317                ("Named", Some(FieldShape::Named)),
2318            ]
2319        );
2320        let unnamed = &lib.facts.body.items[3];
2321        assert_eq!(
2322            (unnamed.name.as_str(), unnamed.kind),
2323            ("_", ItemKind::UnnamedConst)
2324        );
2325        assert!(lib.facts.body.items[4].documented);
2326        assert!(lib.facts.body.impls[0].self_leading_colon);
2327        assert!(!lib.facts.body.impls[1].self_leading_colon);
2328        let inner = ws
2329            .file(&RelPath::new("src/documented.rs").expect("path"))
2330            .expect("loaded");
2331        assert!(inner.facts.documented);
2332        let bare = loaded(&[("src/lib.rs", "pub fn plain() {}")]);
2333        assert!(
2334            !bare
2335                .file(&RelPath::new("src/lib.rs").expect("path"))
2336                .expect("loaded")
2337                .facts
2338                .documented
2339        );
2340    }
2341
2342    #[test]
2343    fn a_verbatim_use_group_is_one_use_fact_per_member_in_its_module_with_the_whole_span() {
2344        let text = "pub mod a { pub fn f() {} }\n\
2345                    pub mod m {\n    #[cfg(test)]\n    pub(crate) use {\n        ::std::fmt::Debug as D,\n        crate::a::f,\n    };\n}\n";
2346        let ws = loaded(&[("src/lib.rs", text)]);
2347        let lib = ws
2348            .file(&RelPath::new("src/lib.rs").expect("path"))
2349            .expect("loaded");
2350        assert_eq!(lib.facts.body.uses, []);
2351        let m = lib.facts.body.mods[1].inline.as_ref().expect("inline");
2352        let start = text.find("#[cfg(test)]").expect("attr");
2353        let end = text.find("};").expect("semi") + 2;
2354        let read: Vec<_> = m
2355            .uses
2356            .iter()
2357            .map(|u| {
2358                (
2359                    u.line,
2360                    u.span.lines.clone(),
2361                    u.span.start_byte,
2362                    u.span.end_byte,
2363                    u.leading_colon,
2364                    u.test,
2365                )
2366            })
2367            .collect();
2368        assert_eq!(
2369            read,
2370            [
2371                (3, 3..8, start, end, true, TestRole::CfgTest),
2372                (3, 3..8, start, end, false, TestRole::CfgTest),
2373            ]
2374        );
2375        assert!(
2376            m.uses
2377                .iter()
2378                .all(|u| u.vis == Vis::Restricted("crate".to_owned()))
2379        );
2380        assert_eq!(
2381            m.uses[0].tree,
2382            UseTree::Path {
2383                name: "std".to_owned(),
2384                rest: Box::new(UseTree::Path {
2385                    name: "fmt".to_owned(),
2386                    rest: Box::new(UseTree::Rename {
2387                        name: "Debug".to_owned(),
2388                        alias: "D".to_owned(),
2389                    }),
2390                }),
2391            }
2392        );
2393    }
2394
2395    #[test]
2396    fn a_large_attribute_on_a_verbatim_use_group_is_read_once_for_all_its_members() {
2397        use std::fmt::Write as _;
2398        // Reading the attribute once per member made this quadratic: 6000
2399        // members under a 6000-name predicate took tens of seconds.
2400        const MEMBERS: usize = 6000;
2401        let names: Vec<String> = (0..MEMBERS).map(|i| format!("a{i}")).collect();
2402        let mut members = String::new();
2403        for i in 0..MEMBERS {
2404            writeln!(members, "    ::std::m{i},").expect("a string takes the text");
2405        }
2406        let text = format!(
2407            "#[cfg(all(test, any({})))]\npub use {{\n{members}}};\n",
2408            names.join(", ")
2409        );
2410        let tree = syn::parse_file(&text).expect("the text parses");
2411        let allowance = FactAllowance {
2412            spent: 0,
2413            limit: usize::MAX,
2414        };
2415        // The attribute is read once for the whole declaration, so its count
2416        // stops at the ceiling of two if it is read for each member instead.
2417        let (extracted, tally) =
2418            work::measure_kind(Work::Attributes, 2, || extract(&tree, &text, allowance));
2419        let (facts, _) = extracted.expect("the facts are read");
2420        assert_eq!(tally.get(Work::Attributes), 1);
2421        let uses = &facts.body.uses;
2422        assert_eq!(uses.len(), MEMBERS);
2423        for (i, u) in uses.iter().enumerate() {
2424            assert_eq!(
2425                (
2426                    u.line,
2427                    u.span.lines.clone(),
2428                    u.span.start_byte,
2429                    u.span.end_byte
2430                ),
2431                (1, 1..MEMBERS + 4, 0, text.len() - 1),
2432                "{i}"
2433            );
2434            assert!(u.leading_colon, "{i}");
2435            assert_eq!((u.test, &u.vis), (TestRole::CfgTest, &Vis::Public), "{i}");
2436            assert_eq!(
2437                u.tree,
2438                UseTree::Path {
2439                    name: "std".to_owned(),
2440                    rest: Box::new(UseTree::Name(format!("m{i}"))),
2441                },
2442                "{i}"
2443            );
2444        }
2445    }
2446
2447    #[test]
2448    fn a_long_line_of_wide_characters_is_indexed_once_for_all_its_positions() {
2449        use std::fmt::Write as _;
2450        // Twenty thousand functions on one line, each name holding a character
2451        // of two bytes, so a column is not a byte offset.
2452        const ITEMS: usize = 20_000;
2453        let mut text = String::new();
2454        let mut starts = Vec::new();
2455        for index in 0..ITEMS {
2456            starts.push(text.len());
2457            write!(text, "pub fn é{index}() {{}} ").expect("a string takes the text");
2458        }
2459        text.push('\n');
2460        let line_chars = text.chars().count();
2461        let tree = syn::parse_file(&text).expect("the text parses");
2462        let allowance = FactAllowance {
2463            spent: 0,
2464            limit: usize::MAX,
2465        };
2466        // A position costs at most one mark interval beside the one pass that
2467        // indexes the line. The ceiling allows eight positions per item; a
2468        // walk from the line start for each position, or an index built for
2469        // each item, passes it within a few thousand items.
2470        let ceiling = line_chars + 8 * ITEMS * (MARK_EVERY + 1);
2471        let (extracted, tally) = work::measure(ceiling, || extract(&tree, &text, allowance));
2472        let (facts, _) = extracted.expect("the facts are read");
2473        let positions = tally.get(Work::Positions);
2474        assert!(positions >= 2 * ITEMS, "{positions}");
2475        assert!(tally.get(Work::ColumnSteps) > 0);
2476        assert!(
2477            tally.get(Work::ColumnSteps) <= line_chars + positions * (MARK_EVERY + 1),
2478            "{} column steps for {positions} positions on a line of {line_chars}",
2479            tally.get(Work::ColumnSteps)
2480        );
2481        assert_eq!(facts.body.items.len(), ITEMS);
2482        for (index, start) in starts.iter().enumerate().step_by(997) {
2483            let item = &facts.body.items[index];
2484            assert_eq!(item.span.start_byte, *start, "é{index}");
2485        }
2486    }
2487}