Skip to main content

raf_source/
modtree.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//! Following `mod` declarations from a target root, as rustc does.
5//!
6//! The rules, per module declaration:
7//!
8//! * `mod name;` without a `path` attribute is `name.rs` or `name/mod.rs` in
9//!   the module directory; both existing is an error. The module directory of
10//!   a root file or a `mod.rs` file is its own directory, and the module
11//!   directory of any other file `a.rs` is `a/` beside it.
12//! * `#[path = "p"]` on `mod name;` names a file relative to the directory of
13//!   the file that holds the declaration, or, inside an inline module, relative
14//!   to the module directory including the inline components. A file named
15//!   this way is treated like a `mod.rs` for its own children.
16//! * An inline module `mod m { .. }` adds `m` to the module directory; a
17//!   `path` attribute on it replaces that component.
18//! * `#[cfg_attr(predicate, path = "p")]` is another site. Every site is
19//!   followed, carrying its predicate, in structural loads. Configured loads
20//!   select active declarations and path attributes before this walk.
21//!
22//! The walk runs on the caller's thread with an explicit stack, so its own
23//! depth costs no stack of the caller, and detects a cycle on the stack of
24//! files being followed. Files are told apart by their identity in the
25//! [`Tree`], not by their spelling: a file reached by several module paths,
26//! or under several spellings (through a symlink to a directory), is read and
27//! parsed once, recorded under each path, and keeps the spelling that sorts
28//! first.
29
30use std::collections::{BTreeMap, HashMap};
31
32use purrdf_hash::fixed::FixedState;
33use purrdf_lex::allocation::{Admission, Memory, OwnedAdmission, StorageError, growth_capacity};
34use std::alloc::Layout;
35use std::mem::size_of;
36use std::rc::Rc;
37
38use crate::budget::Budget;
39use crate::cost::{btree_entry, hash_entry, shared_text, vec_first, vec_slot};
40use crate::error::{LoadError, LoadErrorKind, Origin, TreeError};
41use crate::facts::{ExtractError, FileFacts, ModBody, ModFact, TestRole};
42use crate::intern::Interner;
43use crate::item::{ItemId, SharedStr};
44use crate::meter::{Meter, over_budget};
45use crate::parse::{
46    Candidate, Extracted, ExtractionError, Parser, extract_head, parse_counted_mut, storage,
47};
48#[cfg(target_os = "linux")]
49use crate::parse::{ConfigurationKey, ExtractionGrant};
50use crate::path::RelPath;
51use crate::tree::{EntryKind, FileId, Opened, Tree};
52use crate::workspace::SourceFile;
53use crate::{ActiveConfiguration, PackageId};
54
55/// Index of a target in [`Workspace::targets`](crate::Workspace::targets).
56#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
57pub struct TargetId(pub(crate) usize);
58
59impl TargetId {
60    /// The position of the target.
61    #[must_use]
62    pub const fn index(self) -> usize {
63        self.0
64    }
65}
66
67/// One way a file was reached.
68///
69/// The struct is `#[non_exhaustive]`: adding a field is not a breaking change,
70/// so a pattern names the fields it reads and ends in `..`.
71///
72/// ```compile_fail,E0638
73/// # fn names(reach: &raf_source::Reach) {
74/// let raf_source::Reach { target, module_path, test, predicate } = reach;
75/// # }
76/// ```
77#[derive(Debug, Clone, PartialEq, Eq)]
78#[non_exhaustive]
79pub struct Reach {
80    /// The target whose module tree holds the file.
81    pub target: TargetId,
82    /// The module path of the file's own module, such as `demo::inner`.
83    pub module_path: SharedStr,
84    /// True when the file was reached through an item guarded by a `test`
85    /// predicate, or through a `path` that a `test` predicate sets.
86    pub test: bool,
87    /// The `cfg_attr` predicate of the `path` that led here, if any.
88    pub predicate: Option<String>,
89    /// The `path` attribute that led the walk to this file, if one did.
90    pub path_attribute: Option<PathSite>,
91}
92
93/// The `path` attribute through which the walk reached a file.
94///
95/// A `path` on `mod name;`, plain or inside `cfg_attr`, names the file
96/// itself. A `path` on an inline module names a directory, and a file module
97/// declared inside it, at any inline depth, is reached through that
98/// attribute. A file's own children are reached through the file, not
99/// through the attribute that led to it.
100///
101/// ```compile_fail,E0638
102/// # fn names(site: &raf_source::PathSite) {
103/// let raf_source::PathSite { file, line, resolved } = site;
104/// # }
105/// ```
106#[derive(Debug, Clone, PartialEq, Eq)]
107#[non_exhaustive]
108pub struct PathSite {
109    /// The file that holds the module declaration carrying the attribute.
110    pub file: RelPath,
111    /// The line of that module's name.
112    pub line: usize,
113    /// The spelling the walk followed to the reached file: relative to the
114    /// tree root, with `dir/..` collapsed through real directories.
115    pub resolved: RelPath,
116}
117
118/// A parsed file.
119#[derive(Debug, Clone)]
120pub(crate) struct Parsed {
121    pub(crate) text: String,
122    pub(crate) facts: FileFacts,
123}
124
125/// Where the children of a module live.
126struct DirCtx<'a> {
127    /// The directory of the file, extended by inline modules.
128    dir: RelPath,
129    /// The stem of a non-`mod.rs` file, whose children live in `dir/stem`;
130    /// folded into `dir` as soon as an inline module is entered.
131    relative: Option<String>,
132    /// The declaring file and line of the inline module `path` attribute
133    /// that set `dir`, if one did.
134    via: Option<(RelPath, usize)>,
135    // The original subgrant is refunded only after the owned string dies.
136    _admission: Option<OwnedAdmission<FrameAdmission<'a>>>,
137}
138
139/// How the walk arrives at a file.
140#[derive(Default)]
141struct Arrival<'p> {
142    /// The `cfg_attr` predicate of the `path` that leads to the file.
143    predicate: Option<&'p str>,
144    /// The `path` attribute that leads to the file.
145    path_attribute: Option<PathSite>,
146}
147
148impl<'a> DirCtx<'a> {
149    fn new(
150        dir: RelPath,
151        relative: Option<&str>,
152        via: Option<(RelPath, usize)>,
153        parser: Option<&'a dyn Parser>,
154    ) -> Result<Self, LoadError> {
155        let mut admission =
156            parser.map(|parser| OwnedAdmission::new(FrameAdmission { parser, bytes: 0 }));
157        let relative = match (relative, admission.as_mut()) {
158            (Some(text), Some(admission)) => Some(
159                Memory::new(admission)
160                    .string(text)
161                    .map_err(frontier_storage)?,
162            ),
163            (Some(text), None) => Some(text.to_owned()),
164            (None, _) => None,
165        };
166        Ok(Self {
167            dir,
168            relative,
169            via,
170            _admission: admission,
171        })
172    }
173
174    fn copy(&self, parser: Option<&'a dyn Parser>) -> Result<Self, LoadError> {
175        Self::new(
176            self.dir.clone(),
177            self.relative.as_deref(),
178            self.via.clone(),
179            parser,
180        )
181    }
182
183    /// The directory under which a module declared here is found by name:
184    /// the module directory, or the directory itself for a declaration inside
185    /// a block, which owns no module directory. A module inside an inline
186    /// module of a block has no stem to fold either, since entering the
187    /// inline module drops it.
188    fn declared_dir(
189        &self,
190        unowned: bool,
191        origin: &Origin,
192        file: &RelPath,
193        line: usize,
194    ) -> Result<RelPath, LoadError> {
195        if unowned {
196            Ok(self.dir.clone())
197        } else {
198            self.module_dir(origin, file, line)
199        }
200    }
201
202    fn module_dir(
203        &self,
204        origin: &Origin,
205        file: &RelPath,
206        line: usize,
207    ) -> Result<RelPath, LoadError> {
208        match &self.relative {
209            Some(stem) => join(&self.dir, stem, file, line, origin),
210            None => Ok(self.dir.clone()),
211        }
212    }
213}
214
215fn join(
216    base: &RelPath,
217    relative: &str,
218    file: &RelPath,
219    line: usize,
220    origin: &Origin,
221) -> Result<RelPath, LoadError> {
222    base.join(relative)
223        .map_err(|error| LoadError::tree(file, Some(line), origin, error.into()))
224}
225
226/// Where a module declaration sits.
227#[derive(Clone, Copy)]
228struct Site<'a> {
229    file: &'a RelPath,
230    line: usize,
231    module: &'a str,
232}
233
234/// State carried down the walk.
235#[derive(Debug, Clone)]
236struct Scope {
237    target: TargetId,
238    module_path: SharedStr,
239    test: bool,
240    depth: usize,
241}
242
243/// A parsed file with every way it was reached.
244pub(crate) struct Visited {
245    pub(crate) parsed: Rc<Parsed>,
246    pub(crate) reached: Vec<Reach>,
247}
248
249/// What a walk found.
250pub(crate) struct Walked {
251    /// The parsed files, by the spelling each keeps.
252    pub(crate) files: BTreeMap<RelPath, Visited>,
253    /// Every arrival, in the order of the walk.
254    pub(crate) visits: Vec<Visit>,
255    /// One copy of each module path the walk recorded.
256    pub(crate) paths: Interner,
257}
258
259/// One arrival of the walk at a file: the file and the position of the
260/// [`Reach`] it recorded in the file's list.
261///
262/// The walk records a file's arrival before it follows the file's own module
263/// declarations, so in the order of arrivals the file that declares a module
264/// always comes before the module's own file.
265#[derive(Debug, Clone, PartialEq, Eq)]
266pub(crate) struct Visit {
267    pub(crate) file: RelPath,
268    pub(crate) reach: usize,
269}
270
271/// A module body of a parsed file: the file's own body, or an inline module
272/// inside it, found by the positions of the inline modules on the way.
273struct BodyAt<'a> {
274    parsed: Rc<Parsed>,
275    inline: Vec<usize>,
276    // This owner follows the vector even while a popped body remains active.
277    _admission: Option<OwnedAdmission<FrameAdmission<'a>>>,
278}
279
280impl<'a> BodyAt<'a> {
281    fn body(&self, file: &RelPath) -> Result<&ModBody, LoadError> {
282        let mut body = &self.parsed.facts.body;
283        for &position in &self.inline {
284            body = body
285                .declaration(position)
286                .and_then(|module| module.inline.as_ref())
287                .ok_or_else(|| {
288                    LoadError::new(
289                        file,
290                        None,
291                        LoadErrorKind::Internal {
292                            what: "an inline module of the walk is not in its file".to_owned(),
293                        },
294                    )
295                })?;
296        }
297        Ok(body)
298    }
299
300    fn copy(
301        &self,
302        position: Option<usize>,
303        parser: Option<&'a dyn Parser>,
304    ) -> Result<Self, LoadError> {
305        let mut admission =
306            parser.map(|parser| OwnedAdmission::new(FrameAdmission { parser, bytes: 0 }));
307        let mut inline = if let Some(admission) = admission.as_mut() {
308            let mut inline = Vec::new();
309            let required = self
310                .inline
311                .len()
312                .checked_add(usize::from(position.is_some()))
313                .ok_or_else(|| frontier_storage(StorageError::SizeOverflow))?;
314            Memory::new(admission)
315                .reserve(&mut inline, required)
316                .map_err(frontier_storage)?;
317            inline.extend_from_slice(&self.inline);
318            inline
319        } else {
320            self.inline.clone()
321        };
322        if let Some(position) = position {
323            inline.push(position);
324        }
325        Ok(Self {
326            parsed: Rc::clone(&self.parsed),
327            inline,
328            _admission: admission,
329        })
330    }
331}
332
333/// The module declaration at `position` of a body, with the place the walk
334/// reached it from.
335struct Declared<'a> {
336    at: BodyAt<'a>,
337    position: usize,
338    file: RelPath,
339    ctx: DirCtx<'a>,
340}
341
342impl Declared<'_> {
343    /// True when the declaration is inside a block.
344    fn in_block(&self) -> Result<bool, LoadError> {
345        Ok(self.at.body(&self.file)?.is_block_local(self.position))
346    }
347
348    fn module(&self) -> Result<&ModFact, LoadError> {
349        self.at
350            .body(&self.file)?
351            .declaration(self.position)
352            .ok_or_else(|| {
353                LoadError::new(
354                    &self.file,
355                    None,
356                    LoadErrorKind::Internal {
357                        what: "a module declaration of the walk is not in its file".to_owned(),
358                    },
359                )
360            })
361    }
362}
363
364/// What is left to do, on the walk's own stack.
365enum Frame<'a> {
366    /// Follow the module declarations of a body, from position `next` on.
367    Decls {
368        at: BodyAt<'a>,
369        file: RelPath,
370        ctx: DirCtx<'a>,
371        scope: Scope,
372        next: usize,
373        frontier: (usize, usize),
374    },
375    /// Follow the `cfg_attr` path alternatives of a declaration, from
376    /// alternative `next` on. `scope` is the scope inside the module.
377    Alternatives {
378        declared: Declared<'a>,
379        scope: Scope,
380        next: usize,
381        frontier: usize,
382    },
383    /// The declarations of a file are done; it leaves the stack of files
384    /// being followed.
385    Leave,
386}
387
388/// A native subview that forwards every resize to the original scheduler grant.
389struct FrameAdmission<'a> {
390    parser: &'a dyn Parser,
391    bytes: usize,
392}
393
394fn frontier_storage(cause: StorageError) -> LoadError {
395    storage(&RelPath::root(), cause)
396}
397
398impl Admission for FrameAdmission<'_> {
399    fn resize(&mut self, bytes: usize) -> Result<(), StorageError> {
400        self.parser.resize_frontier(self.bytes, bytes)?;
401        self.bytes = bytes;
402        Ok(())
403    }
404}
405
406struct Frames<'a> {
407    values: Vec<Frame<'a>>,
408    parser: Option<&'a dyn Parser>,
409}
410
411impl<'a> Frames<'a> {
412    fn reserve(&mut self) -> Result<(), LoadError> {
413        let Some(parser) = self.parser else {
414            return Ok(());
415        };
416        let operation = (|| {
417            let bytes = Layout::array::<Frame<'a>>(self.values.capacity())
418                .map_err(|_| StorageError::SizeOverflow)?
419                .size();
420            let required = self
421                .values
422                .len()
423                .checked_add(1)
424                .ok_or(StorageError::SizeOverflow)?;
425            let capacity = growth_capacity::<Frame<'a>>(self.values.capacity(), required)?;
426            let mut admission = FrameAdmission { parser, bytes };
427            Memory::resume(&mut admission, bytes).reserve(&mut self.values, capacity)
428        })();
429        operation.map_err(frontier_storage)
430    }
431
432    fn push(&mut self, frame: Frame<'a>) -> Result<(), LoadError> {
433        self.reserve()?;
434        self.values.push(frame);
435        Ok(())
436    }
437
438    fn insert(&mut self, index: usize, frame: Frame<'a>) -> Result<(), LoadError> {
439        self.reserve()?;
440        self.values.insert(index, frame);
441        Ok(())
442    }
443
444    fn pop(&mut self) -> Option<Frame<'a>> {
445        self.values.pop()
446    }
447
448    fn len(&self) -> usize {
449        self.values.len()
450    }
451}
452
453impl Drop for Frames<'_> {
454    fn drop(&mut self) {
455        if let Some(parser) = self.parser {
456            let values = std::mem::take(&mut self.values);
457            let bytes = Layout::array::<Frame<'_>>(values.capacity())
458                .expect("retained frontier capacity has a representable layout")
459                .size();
460            let mut admission = FrameAdmission { parser, bytes };
461            Memory::resume(&mut admission, bytes)
462                .release_vec(values)
463                .expect("destroyed frontier retains its original scheduler grant");
464        }
465    }
466}
467
468/// One file the walk read, with every way it was reached.
469struct Known<'a> {
470    configuration: Option<(PackageId, &'a ActiveConfiguration)>,
471    path: RelPath,
472    parsed: Rc<Parsed>,
473    reached: Vec<Reach>,
474}
475
476/// What remembering the identity of one spelling allocates at most: its entry
477/// in the table of spellings, the spelling's text and what the identity holds.
478fn spelling_bytes(path: &RelPath, id: &FileId) -> usize {
479    hash_entry::<(RelPath, FileId)>() + shared_text(path.as_str().len()) + id.heap_bytes()
480}
481
482/// What a file the walk reads allocates at most beyond its text and facts: its
483/// place among the files read and in the table of identities, its entry in the
484/// workspace's files, its shared parse, the first room of its list of reaches,
485/// and its entry and first room among the items of each file in the index.
486fn file_bytes(id: &FileId) -> usize {
487    vec_slot::<Known>()
488        + hash_entry::<(FileId, usize)>()
489        + id.heap_bytes()
490        + btree_entry::<RelPath, SourceFile>()
491        + size_of::<Parsed>()
492        + 2 * size_of::<usize>()
493        + vec_first::<Reach>()
494        + btree_entry::<RelPath, Vec<ItemId>>()
495        + vec_first::<ItemId>()
496}
497
498/// What an arrival allocates at most: its reach, predicate and the spellings
499/// of its path attribute in its file's list, its place in both orders of
500/// arrivals, the entry that marks its file, target and module path as
501/// indexed, and its entry and first room among the files of each module path
502/// while the index is built.
503fn reach_bytes(reach: &Reach) -> usize {
504    vec_slot::<Reach>()
505        + reach.predicate.as_ref().map_or(0, String::capacity)
506        + reach.path_attribute.as_ref().map_or(0, |site| {
507            shared_text(site.file.as_str().len()) + shared_text(site.resolved.as_str().len())
508        })
509        + vec_slot::<(usize, usize)>()
510        + vec_slot::<Visit>()
511        + btree_entry::<(RelPath, TargetId, SharedStr), ()>()
512        + btree_entry::<(TargetId, &str), Vec<&SourceFile>>()
513        + vec_first::<&SourceFile>()
514}
515
516#[derive(Clone, Copy)]
517pub(crate) struct WalkConfiguration<'a> {
518    pub(crate) package: PackageId,
519    pub(crate) active: &'a ActiveConfiguration,
520    #[cfg(target_os = "linux")]
521    pub(crate) key: ConfigurationKey,
522}
523
524pub(crate) struct Walker<'a> {
525    configuration: Option<WalkConfiguration<'a>>,
526    tree: &'a dyn Tree,
527    meter: &'a Meter,
528    /// Every file read, in the order it was first reached.
529    files: Vec<Known<'a>>,
530    /// The position in `files` of each file identity.
531    by_id: HashMap<FileId, usize, FixedState>,
532    /// The identity of each spelling the walk asked about.
533    spellings: HashMap<RelPath, FileId, FixedState>,
534    /// Every arrival, in the order of the walk: a position in `files` and in
535    /// that file's reaches.
536    visits: Vec<(usize, usize)>,
537    /// The files being followed, outermost first.
538    active: Vec<FileId>,
539    /// Module paths recorded so far, over all targets.
540    arrivals: usize,
541    /// One copy of each module path.
542    paths: Interner,
543    stack: Frames<'a>,
544    parser: Option<&'a dyn Parser>,
545}
546
547impl<'a> Walker<'a> {
548    pub(crate) fn new(tree: &'a dyn Tree, meter: &'a Meter) -> Self {
549        Self {
550            configuration: None,
551            tree,
552            meter,
553            files: Vec::new(),
554            by_id: HashMap::with_hasher(FixedState::new()),
555            spellings: HashMap::with_hasher(FixedState::new()),
556            visits: Vec::new(),
557            active: Vec::new(),
558            arrivals: 0,
559            paths: Interner::default(),
560            stack: Frames {
561                values: Vec::new(),
562                parser: None,
563            },
564            parser: None,
565        }
566    }
567    pub(crate) fn with_parser(
568        tree: &'a dyn Tree,
569        meter: &'a Meter,
570        parser: Option<&'a dyn Parser>,
571    ) -> Self {
572        let mut walker = Self::new(tree, meter);
573        walker.parser = parser;
574        walker.stack.parser = parser;
575        walker
576    }
577    pub(crate) fn configure(&mut self, configuration: Option<WalkConfiguration<'a>>) {
578        self.configuration = configuration;
579    }
580
581    /// Advance a target frontier once; committed physical files are not reread.
582    pub(crate) fn speculate(&self, path: &RelPath) -> bool {
583        self.speculate_candidate(Candidate::Existing(path))
584    }
585
586    fn speculate_candidate(&self, candidate: Candidate<'_>) -> bool {
587        self.parser.is_none_or(|parser| {
588            parser.speculate(self.tree, candidate, self.meter.options(), &|id| {
589                self.by_id.contains_key(id)
590            })
591        })
592    }
593
594    fn speculative_capacity(&self) -> bool {
595        self.parser.is_some_and(Parser::has_capacity)
596    }
597
598    /// Each frame keeps its own monotonically advancing candidate cursor.
599    fn prefetch_body(
600        &self,
601        at: &BodyAt<'a>,
602        file: &RelPath,
603        ctx: &DirCtx<'a>,
604        next: usize,
605        mut frontier: (usize, usize),
606    ) -> Result<(usize, usize), LoadError> {
607        if frontier.0 <= next {
608            frontier = (next + 1, 0);
609        }
610        let body = at.body(file)?;
611        while self.speculative_capacity() && frontier.0 < body.declarations() {
612            #[cfg(all(test, target_os = "linux"))]
613            let _preparation = crate::parse::parallel::tests::preparing();
614            let Some(module) = body.declaration(frontier.0) else {
615                break;
616            };
617            let unowned = body.is_block_local(frontier.0);
618            if module.inline.is_some() {
619                frontier = (frontier.0 + 1, 0);
620                continue;
621            }
622            let defaults = if module.paths.unconditional.is_empty() {
623                2
624            } else {
625                1
626            };
627            let candidate = if frontier.1 < defaults {
628                if let Some(path) = module.paths.unconditional.first() {
629                    Some(Candidate::Joined {
630                        base: &ctx.dir,
631                        stem: None,
632                        input: path,
633                        suffix: "",
634                    })
635                } else {
636                    Some(Candidate::Joined {
637                        base: &ctx.dir,
638                        stem: if unowned {
639                            None
640                        } else {
641                            ctx.relative.as_deref()
642                        },
643                        input: &module.name,
644                        suffix: if frontier.1 == 0 { ".rs" } else { "/mod.rs" },
645                    })
646                }
647            } else {
648                module
649                    .paths
650                    .conditional
651                    .get(frontier.1 - defaults)
652                    .map(|alternative| Candidate::Joined {
653                        base: &ctx.dir,
654                        stem: None,
655                        input: &alternative.path,
656                        suffix: "",
657                    })
658            };
659            if let Some(candidate) = candidate
660                && !self.speculate_candidate(candidate)
661            {
662                break;
663            }
664            frontier.1 += 1;
665            if frontier.1 >= defaults + module.paths.conditional.len() {
666                frontier = (frontier.0 + 1, 0);
667            }
668        }
669        Ok(frontier)
670    }
671
672    fn prefetch_alternatives(
673        &self,
674        declared: &Declared<'a>,
675        mut frontier: usize,
676    ) -> Result<usize, LoadError> {
677        let module = declared.module()?;
678        // Inline alternatives name directories. Their own Decls frames provide
679        // file candidates once the corresponding directory context is reached.
680        if module.inline.is_some() {
681            return Ok(module.paths.conditional.len());
682        }
683        while self.speculative_capacity() && frontier < module.paths.conditional.len() {
684            #[cfg(all(test, target_os = "linux"))]
685            let _preparation = crate::parse::parallel::tests::preparing();
686            if !self.speculate_candidate(Candidate::Joined {
687                base: &declared.ctx.dir,
688                stem: None,
689                input: &module.paths.conditional[frontier].path,
690                suffix: "",
691            }) {
692                break;
693            }
694            frontier += 1;
695        }
696        Ok(frontier)
697    }
698
699    /// The parsed files, keyed by the spelling each keeps (the one that sorts
700    /// first of those it was reached by), and every arrival
701    /// in the order of the walk, with the table of module paths.
702    pub(crate) fn finish(self) -> Result<Walked, LoadError> {
703        let visits = self
704            .visits
705            .iter()
706            .map(|&(file, reach)| Visit {
707                file: self.files[file].path.clone(),
708                reach,
709            })
710            .collect();
711        let mut files = BTreeMap::new();
712        for known in self.files {
713            let path = known.path;
714            let visited = Visited {
715                parsed: known.parsed,
716                reached: known.reached,
717            };
718            if files.insert(path.clone(), visited).is_some() {
719                return Err(LoadError::new(
720                    &path,
721                    None,
722                    LoadErrorKind::Internal {
723                        what: "two files of the walk keep one spelling".to_owned(),
724                    },
725                ));
726            }
727        }
728        Ok(Walked {
729            files,
730            visits,
731            paths: self.paths,
732        })
733    }
734
735    /// Follow a target from its root file.
736    pub(crate) fn root(
737        &mut self,
738        target: TargetId,
739        root: &RelPath,
740        module_path: &str,
741        origin: &Origin,
742    ) -> Result<(), LoadError> {
743        let ctx = DirCtx::new(parent_dir(root)?, None, None, self.parser)?;
744        let (module_path, cost) = self.paths.intern(module_path);
745        self.meter.items(cost, root, None)?;
746        let scope = Scope {
747            target,
748            module_path,
749            test: match self.configuration {
750                Some(configuration) => crate::configuration::evaluate(
751                    &crate::cfg::CfgExpr::Test,
752                    configuration.active,
753                    false,
754                    self.meter,
755                    root,
756                )?,
757                None => false,
758            },
759            depth: 0,
760        };
761        self.enter(root, None, origin, scope, Arrival::default(), ctx)?;
762        self.run()
763    }
764
765    /// Work the stack until it is empty.
766    fn run(&mut self) -> Result<(), LoadError> {
767        while let Some(frame) = self.stack.pop() {
768            match frame {
769                Frame::Leave => {
770                    self.active.pop();
771                }
772                Frame::Decls {
773                    at,
774                    file,
775                    ctx,
776                    scope,
777                    next,
778                    frontier,
779                } => {
780                    if next < at.body(&file)?.declarations() {
781                        let frontier = self.prefetch_body(&at, &file, &ctx, next, frontier)?;
782                        self.stack.push(Frame::Decls {
783                            at: at.copy(None, self.parser)?,
784                            file: file.clone(),
785                            ctx: ctx.copy(self.parser)?,
786                            scope: scope.clone(),
787                            next: next + 1,
788                            frontier,
789                        })?;
790                        let declared = Declared {
791                            at,
792                            position: next,
793                            file,
794                            ctx,
795                        };
796                        self.module(declared, &scope)?;
797                    }
798                }
799                Frame::Alternatives {
800                    declared,
801                    scope,
802                    next,
803                    frontier,
804                } => self.alternative(declared, scope, next, frontier)?,
805            }
806        }
807        Ok(())
808    }
809
810    /// The identity of the file at `path`, asked once per spelling, and its
811    /// text when the walk has not read the file yet: one open gives both.
812    fn identify(
813        &mut self,
814        path: &RelPath,
815        site: Option<Site<'_>>,
816        origin: &Origin,
817    ) -> Result<(FileId, Option<String>), LoadError> {
818        if let Some(known) = self.spellings.get(path) {
819            return Ok((known.clone(), None));
820        }
821        let by_id = &self.by_id;
822        let max_bytes = self.meter.options().max_file_bytes;
823        // Speculation observed another seen predicate. Only this canonical
824        // observation can decide whether an alias still needs to be read.
825        let opened = self
826            .tree
827            .read_unseen(path, max_bytes, &|id| by_id.contains_key(id));
828        let (id, text) = match opened {
829            Ok(Opened::Seen(id)) => (id, None),
830            Ok(Opened::Read { id, text }) => (id, Some(text)),
831            Err(TreeError::NotFound { .. }) if site.is_some() => {
832                return Err(unresolved(site, path, origin));
833            }
834            Err(error) => {
835                let (file, line) = site.map_or((path, None), |s| (s.file, Some(s.line)));
836                return Err(LoadError::tree(file, line, origin, error));
837            }
838        };
839        let (charged, line) = site.map_or((path, None), |s| (s.file, Some(s.line)));
840        self.meter
841            .items(spelling_bytes(path, &id), charged, line)
842            .map_err(|error| error.reached_by(origin))?;
843        self.spellings.insert(path.clone(), id.clone());
844        Ok((id, text))
845    }
846
847    /// The file `id` at `path` with `reach` recorded: parsed from `text` when
848    /// it is new, which the open that gave `id` read.
849    fn load(
850        &mut self,
851        path: &RelPath,
852        (id, text): (FileId, Option<String>),
853        origin: &Origin,
854        reach: Reach,
855    ) -> Result<Rc<Parsed>, LoadError> {
856        let configuration = self
857            .configuration
858            .map(|context| (context.package, context.active));
859        let Some(text) = text else {
860            let position = *self.by_id.get(&id).ok_or_else(|| {
861                LoadError::new(
862                    path,
863                    None,
864                    LoadErrorKind::Internal {
865                        what: "a file seen by the walk was never read".to_owned(),
866                    },
867                )
868            })?;
869            let known = &mut self.files[position];
870            if !match (known.configuration, configuration) {
871                (None, None) => true,
872                (Some((left, a)), Some((right, b))) => {
873                    left == right && a.same_syntax_under(b, self.meter, path)?
874                }
875                _ => false,
876            } {
877                return Err(crate::configuration::failure(
878                    path,
879                    "one physical source file is shared by different configured package contexts; load those contexts separately",
880                ));
881            }
882            self.visits.push((position, known.reached.len()));
883            known.reached.push(reach);
884            if *path < known.path {
885                known.path = path.clone();
886            }
887            return Ok(Rc::clone(&known.parsed));
888        };
889        self.meter
890            .read(path, &text)
891            .map_err(|error| error.reached_by(origin))?;
892        let before = self.meter.usage();
893        let Extracted { text, head, scan } = self
894            .extract(
895                path,
896                #[cfg(target_os = "linux")]
897                &id,
898                text,
899                before,
900            )
901            .map_err(|error| error.reached_by(origin))?;
902        if let Some(after) = head.configuration_usage {
903            self.meter.configuration_spent(before, after, path)?;
904        }
905        let (facts, fact_bytes) = head.facts.map_err(|problem| match problem {
906            ExtractionError::Configuration(error) => error,
907            ExtractionError::Facts(error) => extract_error(path, origin, error),
908        })?;
909        self.meter.facts(fact_bytes, path)?;
910        self.meter.scanned(scan);
911        self.meter
912            .items(file_bytes(&id), path, None)
913            .map_err(|error| error.reached_by(origin))?;
914        let parsed = Rc::new(Parsed { text, facts });
915        let position = self.files.len();
916        self.visits.push((position, 0));
917        self.files.push(Known {
918            configuration,
919            path: path.clone(),
920            parsed: Rc::clone(&parsed),
921            reached: vec![reach],
922        });
923        self.by_id.insert(id, position);
924        Ok(parsed)
925    }
926
927    fn extract(
928        &self,
929        path: &RelPath,
930        #[cfg(target_os = "linux")] id: &FileId,
931        text: String,
932        before: crate::Usage,
933    ) -> Result<Extracted, LoadError> {
934        let options = self.meter.options();
935        let allowance = self.meter.fact_allowance();
936        #[cfg(target_os = "linux")]
937        if let Some(parser) = self.parser {
938            return parser.parse(
939                path,
940                id,
941                text,
942                options,
943                ExtractionGrant {
944                    allowance,
945                    usage: before,
946                    configuration: self.configuration.map(|configuration| configuration.key),
947                },
948            );
949        }
950        let configuration = self
951            .configuration
952            .map(|configuration| (configuration.active, options, before));
953        let (head, scan) = parse_counted_mut(path, &text, options.max_file_tokens, |tree| {
954            extract_head(tree, path, &text, allowance, configuration)
955        })?;
956        Ok(Extracted { text, head, scan })
957    }
958
959    /// Count one module walk (a file arrival or an inline body) against the
960    /// module-path budget. `site` is the declaring file and line, if any.
961    fn count(
962        &mut self,
963        site: Option<(&RelPath, usize)>,
964        path: &RelPath,
965        origin: &Origin,
966    ) -> Result<(), LoadError> {
967        self.arrivals += 1;
968        if self.arrivals > Budget::ModulePaths.limit() {
969            let (file, line) = site.map_or((path, None), |(file, line)| (file, Some(line)));
970            return Err(
971                over_budget(Budget::ModulePaths, Budget::ModulePaths.limit(), file, line)
972                    .reached_by(origin),
973            );
974        }
975        Ok(())
976    }
977
978    /// Record an arrival at `path` and put its module declarations on the
979    /// stack.
980    fn enter(
981        &mut self,
982        path: &RelPath,
983        site: Option<Site<'_>>,
984        origin: &Origin,
985        scope: Scope,
986        arrival: Arrival<'_>,
987        ctx: DirCtx<'a>,
988    ) -> Result<(), LoadError> {
989        let opened = self.identify(path, site, origin)?;
990        let id = opened.0.clone();
991        if self.active.contains(&id) {
992            let (file, line, module) = site.map_or((path, None, String::new()), |s| {
993                (s.file, Some(s.line), s.module.to_owned())
994            });
995            return Err(LoadError::new(
996                file,
997                line,
998                LoadErrorKind::ModuleCycle {
999                    module,
1000                    again: Box::new(path.clone()),
1001                },
1002            )
1003            .reached_by(origin));
1004        }
1005        self.count(site.map(|s| (s.file, s.line)), path, origin)?;
1006        let reach = Reach {
1007            target: scope.target,
1008            module_path: scope.module_path.clone(),
1009            test: scope.test,
1010            predicate: arrival.predicate.map(str::to_owned),
1011            path_attribute: arrival.path_attribute,
1012        };
1013        let (charged, line) = site.map_or((path, None), |s| (s.file, Some(s.line)));
1014        self.meter
1015            .items(reach_bytes(&reach), charged, line)
1016            .map_err(|error| error.reached_by(origin))?;
1017        let parsed = self.load(path, opened, origin, reach)?;
1018        self.active.push(id);
1019        self.stack.push(Frame::Leave)?;
1020        self.stack.push(Frame::Decls {
1021            at: BodyAt {
1022                parsed,
1023                inline: Vec::new(),
1024                _admission: None,
1025            },
1026            file: path.clone(),
1027            ctx,
1028            scope,
1029            next: 0,
1030            frontier: (0, 0),
1031        })?;
1032        Ok(())
1033    }
1034
1035    fn deeper(module: &ModFact, file: &RelPath, scope: &Scope) -> Result<(), LoadError> {
1036        if scope.depth + 1 > Budget::ModuleDepth.limit() {
1037            return Err(over_budget(
1038                Budget::ModuleDepth,
1039                Budget::ModuleDepth.limit(),
1040                file,
1041                Some(module.name_line),
1042            )
1043            .reached_by(&Origin::ModDecl {
1044                module: module.name.clone(),
1045            }));
1046        }
1047        Ok(())
1048    }
1049
1050    /// Follow one module declaration: its default part now, its alternatives
1051    /// once that is done.
1052    fn module(&mut self, declared: Declared<'a>, scope: &Scope) -> Result<(), LoadError> {
1053        let module = declared.module()?;
1054        let file = &declared.file;
1055        Self::deeper(module, file, scope)?;
1056        if module.paths.unconditional.len() > 1 {
1057            return Err(LoadError::new(
1058                file,
1059                Some(module.name_line),
1060                LoadErrorKind::DuplicatePathAttr {
1061                    module: module.name.clone(),
1062                },
1063            )
1064            .reached_by(&Origin::PathAttr {
1065                module: module.name.clone(),
1066                predicate: None,
1067            }));
1068        }
1069        let unowned = declared.in_block()?;
1070        let segment = if declared.at.body(file)?.is_block_local(declared.position) {
1071            module.block_segment()
1072        } else {
1073            module.name.clone()
1074        };
1075        let (module_path, cost) = self
1076            .paths
1077            .intern(&format!("{}::{segment}", scope.module_path));
1078        self.meter
1079            .items(cost, file, Some(module.name_line))
1080            .map_err(|error| {
1081                error.reached_by(&Origin::ModDecl {
1082                    module: module.name.clone(),
1083                })
1084            })?;
1085        let inner = Scope {
1086            target: scope.target,
1087            module_path,
1088            test: scope.test || module.test != TestRole::None,
1089            depth: scope.depth + 1,
1090        };
1091        let site = Site {
1092            file,
1093            line: module.name_line,
1094            module: &module.name,
1095        };
1096        let has_alternatives = !module.paths.conditional.is_empty();
1097        let frontier = if has_alternatives {
1098            self.prefetch_alternatives(&declared, 0)?
1099        } else {
1100            0
1101        };
1102        let before = self.stack.len();
1103        if module.inline.is_some() {
1104            self.inline_default(module, site, &declared, &inner, unowned)?;
1105        } else {
1106            self.declared_default(
1107                module,
1108                site,
1109                &declared.ctx,
1110                &inner,
1111                has_alternatives,
1112                unowned,
1113            )?;
1114        }
1115        if has_alternatives {
1116            // Below the frames of the default part, so it runs once they are
1117            // done.
1118            self.stack.insert(
1119                before,
1120                Frame::Alternatives {
1121                    declared,
1122                    scope: inner,
1123                    next: 0,
1124                    frontier,
1125                },
1126            )?;
1127        }
1128        Ok(())
1129    }
1130
1131    /// The default part of an inline module: its body, under its `path` or its
1132    /// name.
1133    fn inline_default(
1134        &mut self,
1135        module: &ModFact,
1136        site: Site<'_>,
1137        declared: &Declared<'a>,
1138        scope: &Scope,
1139        unowned: bool,
1140    ) -> Result<(), LoadError> {
1141        let ctx = &declared.ctx;
1142        let (dir, via) = if let Some(path) = module.paths.unconditional.first() {
1143            let origin = Origin::PathAttr {
1144                module: module.name.clone(),
1145                predicate: None,
1146            };
1147            (
1148                join(&ctx.dir, path, site.file, site.line, &origin)?,
1149                Some((site.file.clone(), site.line)),
1150            )
1151        } else {
1152            let by_name = Origin::ModDecl {
1153                module: module.name.clone(),
1154            };
1155            let base = ctx.declared_dir(unowned, &by_name, site.file, site.line)?;
1156            (
1157                join(&base, &module.name, site.file, site.line, &by_name)?,
1158                ctx.via.clone(),
1159            )
1160        };
1161        self.stack.push(Frame::Decls {
1162            at: declared.at.copy(Some(declared.position), self.parser)?,
1163            file: site.file.clone(),
1164            ctx: DirCtx::new(dir, None, via, self.parser)?,
1165            scope: scope.clone(),
1166            next: 0,
1167            frontier: (0, 0),
1168        })?;
1169        Ok(())
1170    }
1171
1172    /// The default part of `mod name;`: its unconditional `path`, or
1173    /// `name.rs` or `name/mod.rs`.
1174    fn declared_default(
1175        &mut self,
1176        module: &ModFact,
1177        site: Site<'_>,
1178        ctx: &DirCtx<'a>,
1179        scope: &Scope,
1180        has_alternatives: bool,
1181        unowned: bool,
1182    ) -> Result<(), LoadError> {
1183        if let Some(path) = module.paths.unconditional.first() {
1184            let origin = Origin::PathAttr {
1185                module: module.name.clone(),
1186                predicate: None,
1187            };
1188            let file = join(&ctx.dir, path, site.file, site.line, &origin)?;
1189            let file = self.tidy(&file, site, &origin)?;
1190            self.follow_path_file(&file, site, &origin, scope.clone(), None)?;
1191        } else {
1192            self.follow_default(module, site, ctx, scope, has_alternatives, unowned)?;
1193        }
1194        Ok(())
1195    }
1196
1197    /// Follow alternative `next` of a declaration, and leave the rest on the
1198    /// stack.
1199    fn alternative(
1200        &mut self,
1201        declared: Declared<'a>,
1202        scope: Scope,
1203        next: usize,
1204        frontier: usize,
1205    ) -> Result<(), LoadError> {
1206        let frontier = self.prefetch_alternatives(&declared, frontier.max(next + 1))?;
1207        let module = declared.module()?;
1208        let Some(alternative) = module.paths.conditional.get(next) else {
1209            return Ok(());
1210        };
1211        let name = module.name.clone();
1212        let line = module.name_line;
1213        let inline = module.inline.is_some();
1214        let alternative = alternative.clone();
1215        let origin = Origin::PathAttr {
1216            module: name.clone(),
1217            predicate: Some(alternative.predicate.clone()),
1218        };
1219        let alternative_scope = Scope {
1220            test: scope.test || alternative.implies_test,
1221            ..scope.clone()
1222        };
1223        let file = declared.file.clone();
1224        let site = Site {
1225            file: &file,
1226            line,
1227            module: &name,
1228        };
1229        let dir = join(&declared.ctx.dir, &alternative.path, &file, line, &origin)?;
1230        if inline {
1231            self.count(Some((&file, line)), &file, &origin)?;
1232            let at = declared.at.copy(Some(declared.position), self.parser)?;
1233            self.stack.push(Frame::Alternatives {
1234                declared,
1235                scope,
1236                next: next + 1,
1237                frontier,
1238            })?;
1239            self.stack.push(Frame::Decls {
1240                at,
1241                file: file.clone(),
1242                ctx: DirCtx::new(dir, None, Some((file.clone(), line)), self.parser)?,
1243                scope: alternative_scope,
1244                next: 0,
1245                frontier: (0, 0),
1246            })?;
1247        } else {
1248            let target = self.tidy(&dir, site, &origin)?;
1249            let after = self.stack.len();
1250            self.follow_path_file(
1251                &target,
1252                site,
1253                &origin,
1254                alternative_scope,
1255                Some(&alternative.predicate),
1256            )?;
1257            self.stack.insert(
1258                after,
1259                Frame::Alternatives {
1260                    declared,
1261                    scope,
1262                    next: next + 1,
1263                    frontier,
1264                },
1265            )?;
1266        }
1267        Ok(())
1268    }
1269
1270    fn tidy(&self, path: &RelPath, site: Site<'_>, origin: &Origin) -> Result<RelPath, LoadError> {
1271        tidy(self.tree, path)
1272            .map_err(|error| LoadError::tree(site.file, Some(site.line), origin, error))
1273    }
1274
1275    /// True when a file, or a symlink that may lead to one, is at `path`.
1276    fn exists(&self, path: &RelPath, site: Site<'_>, origin: &Origin) -> Result<bool, LoadError> {
1277        match self
1278            .tree
1279            .entry(path)
1280            .map_err(|error| LoadError::tree(site.file, Some(site.line), origin, error))?
1281        {
1282            // A special file counts as present so that reading it is refused,
1283            // not mistaken for a missing module.
1284            Some(EntryKind::File | EntryKind::Symlink | EntryKind::Other) => Ok(true),
1285            Some(EntryKind::Dir) | None => Ok(false),
1286        }
1287    }
1288
1289    /// A file named by a `path` attribute: a `mod.rs` for its own children.
1290    fn follow_path_file(
1291        &mut self,
1292        file: &RelPath,
1293        site: Site<'_>,
1294        origin: &Origin,
1295        scope: Scope,
1296        predicate: Option<&str>,
1297    ) -> Result<(), LoadError> {
1298        let ctx = DirCtx::new(parent_dir(file)?, None, None, self.parser)?;
1299        let arrival = Arrival {
1300            predicate,
1301            path_attribute: Some(PathSite {
1302                file: site.file.clone(),
1303                line: site.line,
1304                resolved: file.clone(),
1305            }),
1306        };
1307        self.enter(file, Some(site), origin, scope, arrival, ctx)
1308    }
1309
1310    /// `mod name;` without a `path`: `name.rs` or `name/mod.rs`.
1311    fn follow_default(
1312        &mut self,
1313        module: &ModFact,
1314        site: Site<'_>,
1315        ctx: &DirCtx<'a>,
1316        scope: &Scope,
1317        has_alternatives: bool,
1318        unowned: bool,
1319    ) -> Result<(), LoadError> {
1320        let origin = Origin::ModDecl {
1321            module: module.name.clone(),
1322        };
1323        let base = ctx.declared_dir(unowned, &origin, site.file, site.line)?;
1324        let flat = join(
1325            &base,
1326            &format!("{}.rs", module.name),
1327            site.file,
1328            site.line,
1329            &origin,
1330        )?;
1331        let nested = join(
1332            &base,
1333            &format!("{}/mod.rs", module.name),
1334            site.file,
1335            site.line,
1336            &origin,
1337        )?;
1338        // A file found by name in a directory that an inline module's `path`
1339        // set is reached through that attribute.
1340        let arrival = |found: &RelPath| -> Result<Arrival<'_>, LoadError> {
1341            let path_attribute = match &ctx.via {
1342                Some((file, line)) => Some(PathSite {
1343                    file: file.clone(),
1344                    line: *line,
1345                    resolved: self.tidy(found, site, &origin)?,
1346                }),
1347                None => None,
1348            };
1349            Ok(Arrival {
1350                predicate: None,
1351                path_attribute,
1352            })
1353        };
1354        match (
1355            self.exists(&flat, site, &origin)?,
1356            self.exists(&nested, site, &origin)?,
1357        ) {
1358            (true, true) => Err(LoadError::new(
1359                site.file,
1360                Some(site.line),
1361                LoadErrorKind::BothModFiles {
1362                    module: module.name.clone(),
1363                    first: Box::new(flat),
1364                    second: Box::new(nested),
1365                },
1366            )
1367            .reached_by(&origin)),
1368            (true, false) => {
1369                let children = DirCtx::new(base, Some(&module.name), None, self.parser)?;
1370                let arrival = arrival(&flat)?;
1371                self.enter(&flat, Some(site), &origin, scope.clone(), arrival, children)
1372            }
1373            (false, true) => {
1374                let children = DirCtx::new(parent_dir(&nested)?, None, None, self.parser)?;
1375                let arrival = arrival(&nested)?;
1376                self.enter(
1377                    &nested,
1378                    Some(site),
1379                    &origin,
1380                    scope.clone(),
1381                    arrival,
1382                    children,
1383                )
1384            }
1385            // Every `cfg_attr` alternative names a file; none of them need the
1386            // default one.
1387            (false, false) if has_alternatives => Ok(()),
1388            (false, false) => Err(unresolved(Some(site), &flat, &origin)),
1389        }
1390    }
1391}
1392
1393/// Collapse `dir/..` pairs where `dir` is a real directory, so one file has
1394/// one spelling. A `..` after a symlink, a file or a missing entry stays, and
1395/// the disk decides where it leads.
1396pub(crate) fn tidy(tree: &dyn Tree, path: &RelPath) -> Result<RelPath, TreeError> {
1397    let mut kept: Vec<&str> = Vec::new();
1398    for segment in path.segments() {
1399        if segment == ".." && kept.last().is_some_and(|last| *last != "..") {
1400            let prefix = path.source_root().join(&kept.join("/"))?;
1401            if tree.entry(&prefix)? == Some(EntryKind::Dir) {
1402                kept.pop();
1403                continue;
1404            }
1405        }
1406        kept.push(segment);
1407    }
1408    Ok(path.source_root().join(&kept.join("/"))?)
1409}
1410
1411fn unresolved(site: Option<Site<'_>>, path: &RelPath, origin: &Origin) -> LoadError {
1412    let (file, line, module) = site.map_or((path, None, String::new()), |s| {
1413        (s.file, Some(s.line), s.module.to_owned())
1414    });
1415    LoadError::new(file, line, LoadErrorKind::UnresolvedMod { module }).reached_by(origin)
1416}
1417
1418/// The directory that holds a file.
1419fn parent_dir(file: &RelPath) -> Result<RelPath, LoadError> {
1420    file.parent().ok_or_else(|| {
1421        LoadError::tree(
1422            file,
1423            None,
1424            &Origin::Discovery,
1425            TreeError::NotRegular {
1426                path: file.to_string(),
1427            },
1428        )
1429    })
1430}
1431
1432fn extract_error(file: &RelPath, origin: &Origin, problem: ExtractError) -> LoadError {
1433    // A `path` attribute on a module is what the error comes from, not what
1434    // reached the file that holds it.
1435    if let ExtractError::PathAttr {
1436        line,
1437        module: Some(module),
1438        predicate,
1439        message,
1440    } = problem
1441    {
1442        return LoadError::new(file, Some(line), LoadErrorKind::CfgParse { message })
1443            .reached_by(&Origin::PathAttr { module, predicate });
1444    }
1445    let (line, kind) = match problem {
1446        ExtractError::Budget { line, limit } => (
1447            line,
1448            LoadErrorKind::Budget {
1449                budget: Budget::FactBytes,
1450                limit,
1451            },
1452        ),
1453        ExtractError::Cfg { line, message } | ExtractError::PathAttr { line, message, .. } => {
1454            (line, LoadErrorKind::CfgParse { message })
1455        }
1456        ExtractError::Unsupported { line, what } => (line, LoadErrorKind::UnsupportedItem { what }),
1457        ExtractError::Position { line } => (
1458            line,
1459            LoadErrorKind::UnsupportedItem {
1460                what: "a position outside the text".to_owned(),
1461            },
1462        ),
1463    };
1464    LoadError::new(file, Some(line), kind).reached_by(origin)
1465}