1use 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#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
57pub struct TargetId(pub(crate) usize);
58
59impl TargetId {
60 #[must_use]
62 pub const fn index(self) -> usize {
63 self.0
64 }
65}
66
67#[derive(Debug, Clone, PartialEq, Eq)]
78#[non_exhaustive]
79pub struct Reach {
80 pub target: TargetId,
82 pub module_path: SharedStr,
84 pub test: bool,
87 pub predicate: Option<String>,
89 pub path_attribute: Option<PathSite>,
91}
92
93#[derive(Debug, Clone, PartialEq, Eq)]
107#[non_exhaustive]
108pub struct PathSite {
109 pub file: RelPath,
111 pub line: usize,
113 pub resolved: RelPath,
116}
117
118#[derive(Debug, Clone)]
120pub(crate) struct Parsed {
121 pub(crate) text: String,
122 pub(crate) facts: FileFacts,
123}
124
125struct DirCtx<'a> {
127 dir: RelPath,
129 relative: Option<String>,
132 via: Option<(RelPath, usize)>,
135 _admission: Option<OwnedAdmission<FrameAdmission<'a>>>,
137}
138
139#[derive(Default)]
141struct Arrival<'p> {
142 predicate: Option<&'p str>,
144 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 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#[derive(Clone, Copy)]
228struct Site<'a> {
229 file: &'a RelPath,
230 line: usize,
231 module: &'a str,
232}
233
234#[derive(Debug, Clone)]
236struct Scope {
237 target: TargetId,
238 module_path: SharedStr,
239 test: bool,
240 depth: usize,
241}
242
243pub(crate) struct Visited {
245 pub(crate) parsed: Rc<Parsed>,
246 pub(crate) reached: Vec<Reach>,
247}
248
249pub(crate) struct Walked {
251 pub(crate) files: BTreeMap<RelPath, Visited>,
253 pub(crate) visits: Vec<Visit>,
255 pub(crate) paths: Interner,
257}
258
259#[derive(Debug, Clone, PartialEq, Eq)]
266pub(crate) struct Visit {
267 pub(crate) file: RelPath,
268 pub(crate) reach: usize,
269}
270
271struct BodyAt<'a> {
274 parsed: Rc<Parsed>,
275 inline: Vec<usize>,
276 _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
333struct Declared<'a> {
336 at: BodyAt<'a>,
337 position: usize,
338 file: RelPath,
339 ctx: DirCtx<'a>,
340}
341
342impl Declared<'_> {
343 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
364enum Frame<'a> {
366 Decls {
368 at: BodyAt<'a>,
369 file: RelPath,
370 ctx: DirCtx<'a>,
371 scope: Scope,
372 next: usize,
373 frontier: (usize, usize),
374 },
375 Alternatives {
378 declared: Declared<'a>,
379 scope: Scope,
380 next: usize,
381 frontier: usize,
382 },
383 Leave,
386}
387
388struct 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
468struct Known<'a> {
470 configuration: Option<(PackageId, &'a ActiveConfiguration)>,
471 path: RelPath,
472 parsed: Rc<Parsed>,
473 reached: Vec<Reach>,
474}
475
476fn spelling_bytes(path: &RelPath, id: &FileId) -> usize {
479 hash_entry::<(RelPath, FileId)>() + shared_text(path.as_str().len()) + id.heap_bytes()
480}
481
482fn 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
498fn 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 files: Vec<Known<'a>>,
530 by_id: HashMap<FileId, usize, FixedState>,
532 spellings: HashMap<RelPath, FileId, FixedState>,
534 visits: Vec<(usize, usize)>,
537 active: Vec<FileId>,
539 arrivals: usize,
541 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 Some(EntryKind::File | EntryKind::Symlink | EntryKind::Other) => Ok(true),
1285 Some(EntryKind::Dir) | None => Ok(false),
1286 }
1287 }
1288
1289 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 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 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 (false, false) if has_alternatives => Ok(()),
1388 (false, false) => Err(unresolved(Some(site), &flat, &origin)),
1389 }
1390 }
1391}
1392
1393pub(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
1418fn 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 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}