Skip to main content

raf_source/
meter.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//! What one load spends against its work and memory budgets.
5
6use std::cell::{Cell, RefCell};
7use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
8
9use purrdf_lex::allocation::{Admission, StorageError};
10use purrdf_lex::walk::WorkList;
11
12use crate::budget::Budget;
13use crate::error::{LoadError, LoadErrorKind};
14use crate::modtree::TargetId;
15use crate::options::LoadOptions;
16use crate::path::RelPath;
17use crate::prescan::Scan;
18
19/// What a load spent against its budgets, as [`Workspace::usage`] reports it.
20///
21/// [`Workspace::usage`]: crate::Workspace::usage
22#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
23#[non_exhaustive]
24pub struct Usage {
25    /// Bytes read: every source file and manifest ([`Budget::TotalBytes`]).
26    pub total_bytes: usize,
27    /// Bytes charged to the index, shared immutable derived glob facts and
28    /// native load traversal scratch
29    /// ([`Budget::ItemBytes`]).
30    pub item_bytes: usize,
31    /// Bytes charged to the facts of the files ([`Budget::FactBytes`]).
32    pub fact_bytes: usize,
33    /// The most bytes charged to import settling at once
34    /// ([`Budget::GlobBytes`]): scope tables, retained named and glob reads,
35    /// queues, subscriptions, graph scratch, impl self-type and trait-path
36    /// traversal scratch, derived glob-fact construction scratch and waiting
37    /// changes at their peak. Immutable cached glob facts use `item_bytes`.
38    pub glob_bytes: usize,
39    /// The most tokens of one file ([`Budget::FileTokens`]).
40    pub max_file_tokens: usize,
41    /// The highest value the recursion counter of the pre-scan reached in one
42    /// file ([`Budget::Recursion`]).
43    pub max_recursion: usize,
44    /// The deepest directory that discovery or a `workspace.members` pattern
45    /// entered, in levels below its root ([`Budget::DirectoryDepth`]).
46    pub max_directory_depth: usize,
47    /// The import-settling steps the load made ([`Budget::Work`]), including
48    /// table reconstruction, retained reads, queues, subscriptions and graph
49    /// traversal, plus impl self-type and trait-path traversal and its retained
50    /// path segments and bytes. Named imports consume this budget even without glob imports.
51    pub work: usize,
52}
53
54/// The running totals of one load, or of one query after it, checked
55/// against their limits.
56pub(crate) struct Meter {
57    options: LoadOptions,
58    total_bytes: Cell<usize>,
59    item_bytes: Cell<usize>,
60    fact_bytes: Cell<usize>,
61    glob_bytes: Cell<usize>,
62    glob_peak: Cell<usize>,
63    max_file_tokens: Cell<usize>,
64    max_recursion: Cell<usize>,
65    max_directory_depth: Cell<usize>,
66    work: Cell<usize>,
67    /// The most steps of work: `max_work` for a load, `max_query_work` for
68    /// a query after it.
69    work_limit: usize,
70    /// For a query, the module whose lookup first made the work pass the
71    /// limit: the query is refused at its next checkpoint, naming it.
72    query_passed: Cell<Option<usize>>,
73}
74
75/// Fallible reservations for temporary resolver storage held at once.
76/// Each reservation precedes allocation; dropping the owner releases it.
77pub(crate) struct Transient<'m> {
78    meter: &'m Meter,
79    bytes: Cell<usize>,
80}
81
82/// Optional failed-route observations owned by one original query grant.
83pub(crate) struct QueryObservation<'m> {
84    memory: Transient<'m>,
85    targets: RefCell<Vec<TargetId>>,
86}
87
88impl<'m> QueryObservation<'m> {
89    pub(crate) const fn new(meter: &'m Meter) -> Self {
90        Self {
91            memory: Transient::new(meter),
92            targets: RefCell::new(Vec::new()),
93        }
94    }
95
96    pub(crate) fn record(
97        &self,
98        target: TargetId,
99        file: &RelPath,
100        line: Option<usize>,
101    ) -> Result<(), LoadError> {
102        let mut targets = self.targets.borrow_mut();
103        self.memory
104            .work(targets.len().saturating_add(1), file, line)?;
105        if targets.contains(&target) {
106            return Ok(());
107        }
108        let bytes = targets.capacity() * size_of::<TargetId>();
109        let steps = Steps::QueryAt {
110            memory: &self.memory,
111            file,
112            line,
113        };
114        let mut admission = NativeAdmission::resume(steps, bytes);
115        purrdf_lex::allocation::Memory::resume(&mut admission, bytes)
116            .push(&mut targets, target)
117            .map_err(|error| admission.graph_error(error.into()))
118    }
119
120    pub(crate) fn finish(self) -> Vec<TargetId> {
121        self.targets.into_inner()
122    }
123}
124
125impl<'m> Transient<'m> {
126    pub(crate) const fn new(meter: &'m Meter) -> Self {
127        Self {
128            meter,
129            bytes: Cell::new(0),
130        }
131    }
132
133    pub(crate) const fn child(&self) -> Self {
134        Self::new(self.meter)
135    }
136
137    pub(crate) fn charge(
138        &self,
139        bytes: usize,
140        file: &RelPath,
141        line: Option<usize>,
142    ) -> Result<(), LoadError> {
143        let limit = self.meter.options.max_glob_bytes;
144        let next = self
145            .bytes
146            .get()
147            .checked_add(bytes)
148            .filter(|_| {
149                self.meter
150                    .glob_bytes
151                    .get()
152                    .checked_add(bytes)
153                    .is_some_and(|held| held <= limit)
154            })
155            .ok_or_else(|| over_budget(Budget::GlobBytes, limit, file, line))?;
156        self.meter.globs(bytes, file, line)?;
157        self.bytes.set(next);
158        Ok(())
159    }
160
161    pub(crate) fn work(
162        &self,
163        units: usize,
164        file: &RelPath,
165        line: Option<usize>,
166    ) -> Result<(), LoadError> {
167        self.meter.work(units, file, line)
168    }
169
170    /// Move an already admitted surviving payload to its enclosing owner.
171    /// The global live total stays unchanged; this owner releases only scratch.
172    pub(crate) fn transfer_to(
173        &self,
174        owner: &Self,
175        bytes: usize,
176        file: &RelPath,
177        line: Option<usize>,
178    ) -> Result<(), LoadError> {
179        let retained = owner.bytes.get().checked_add(bytes);
180        if !std::ptr::eq(self.meter, owner.meter)
181            || std::ptr::eq(self, owner)
182            || bytes > self.bytes.get()
183            || retained.is_none()
184        {
185            return Err(LoadError::new(
186                file,
187                line,
188                LoadErrorKind::Internal {
189                    what: "retained import storage exceeds its original allocation grant"
190                        .to_owned(),
191                },
192            ));
193        }
194        owner
195            .bytes
196            .set(retained.expect("checked destination grant"));
197        self.bytes.set(self.bytes.get() - bytes);
198        Ok(())
199    }
200}
201
202impl Drop for Transient<'_> {
203    fn drop(&mut self) {
204        self.meter.release_globs(self.bytes.get());
205    }
206}
207
208/// Lend native physical storage the resolver's original live-byte grant.
209/// The parent lease retains successful result storage after this callback dies.
210pub(crate) struct NativeAdmission<'m> {
211    steps: Steps<'m>,
212    items: Option<(&'m Meter, &'m RelPath, Option<usize>)>,
213    live: usize,
214    failure: Option<LoadError>,
215}
216
217impl<'m> NativeAdmission<'m> {
218    pub(crate) const fn new(steps: Steps<'m>) -> Self {
219        Self {
220            steps,
221            items: None,
222            live: 0,
223            failure: None,
224        }
225    }
226
227    /// Resume a buffer originally constructed under this same parent lease.
228    pub(crate) const fn resume(steps: Steps<'m>, live: usize) -> Self {
229        Self {
230            steps,
231            items: None,
232            live,
233            failure: None,
234        }
235    }
236
237    /// Admit index-emission scratch to the original cumulative item budget.
238    pub(crate) const fn items(
239        meter: &'m Meter,
240        file: &'m RelPath,
241        line: Option<usize>,
242        bytes: usize,
243    ) -> Self {
244        Self {
245            steps: Steps::Load,
246            items: Some((meter, file, line)),
247            live: bytes,
248            failure: None,
249        }
250    }
251
252    pub(crate) fn graph_error(&mut self, error: purrdf_core::graph::GraphError) -> LoadError {
253        self.failure.take().unwrap_or_else(|| {
254            let (file, line) = if let Some((_, file, line)) = self.items {
255                (file.clone(), line)
256            } else {
257                match self.steps {
258                    Steps::LoadAt { file, line, .. } => (file.clone(), Some(line)),
259                    Steps::QueryAt { file, line, .. } | Steps::QueryItems { file, line, .. } => {
260                        (file.clone(), line)
261                    }
262                    Steps::Load | Steps::Query(_) | Steps::Observed(_) => (RelPath::root(), None),
263                }
264            };
265            LoadError::new(&file, line, LoadErrorKind::Graph(error))
266        })
267    }
268}
269
270impl Admission for NativeAdmission<'_> {
271    fn resize(&mut self, live: usize) -> Result<(), StorageError> {
272        if live > self.live {
273            let result = if let Some((meter, file, line)) = self.items {
274                meter.items(live - self.live, file, line)
275            } else {
276                self.steps.reserve(live - self.live)
277            };
278            if let Err(error) = result {
279                if self.failure.is_none() {
280                    self.failure = Some(error);
281                }
282                return Err(StorageError::AdmissionFailed);
283            }
284        } else if let Steps::LoadAt { memory, .. } | Steps::QueryAt { memory, .. } = self.steps {
285            let released = self.live - live;
286            // Memory invokes shrink only after the native allocation dies.
287            memory.bytes.set(memory.bytes.get() - released);
288            memory.meter.release_globs(released);
289        }
290        self.live = live;
291        Ok(())
292    }
293}
294
295/// Lend a native traversal spill the original cumulative item account.
296pub(crate) fn push_item_work<T, const N: usize>(
297    into: &mut WorkList<T, N>,
298    value: T,
299    meter: &Meter,
300    file: &RelPath,
301    line: Option<usize>,
302) -> Result<(), LoadError> {
303    let bytes = into.heap_capacity() * size_of::<T>();
304    let mut admission = NativeAdmission::items(meter, file, line, bytes);
305    into.try_push_admitted(
306        value,
307        &mut purrdf_lex::allocation::Memory::resume(&mut admission, bytes),
308    )
309    .map_err(|error| admission.graph_error(error.into()))
310}
311
312/// The lookup steps a load makes while it builds its index: each glob read
313/// that a lookup of what the globs of a module bring in under a name looks
314/// at, and each view that holds the name looked at to find those reads.
315/// They are made by code that answers and cannot refuse, so they are
316/// counted here as they are made and drained into the work of the load at
317/// its next checkpoint, which can (see `Index::settle_lookups`). An atomic,
318/// so that the index stays `Sync`; it clones and compares by its count, so
319/// the index keeps its derives. The count is zero once the index is built:
320/// a query after the load counts on its own meter (see [`Steps`]), and a
321/// debug build checks that none counts here.
322#[derive(Debug, Default)]
323pub(crate) struct LookupCount {
324    /// The steps counted since the last take.
325    count: AtomicUsize,
326    /// True once the index is built, until its tables are settled again:
327    /// a lookup counted here then is a query's, counted in the wrong place.
328    built: AtomicBool,
329}
330
331impl LookupCount {
332    /// Count `steps` more. Only the thread that builds the index counts, so
333    /// the count is read and written apart.
334    pub(crate) fn add(&self, steps: usize) {
335        debug_assert!(
336            !self.built.load(Ordering::Relaxed),
337            "a lookup after the load counted on the count of the load"
338        );
339        self.count
340            .store(self.get().saturating_add(steps), Ordering::Relaxed);
341    }
342
343    /// The steps counted since the last take, and none left.
344    pub(crate) fn take(&self) -> usize {
345        self.count.swap(0, Ordering::Relaxed)
346    }
347
348    /// The steps counted since the last take.
349    pub(crate) fn get(&self) -> usize {
350        self.count.load(Ordering::Relaxed)
351    }
352
353    /// Mark the index built, or settled again when `built` is false.
354    pub(crate) fn built(&self, built: bool) {
355        self.built.store(built, Ordering::Relaxed);
356    }
357}
358
359impl Clone for LookupCount {
360    fn clone(&self) -> Self {
361        Self {
362            count: AtomicUsize::new(self.get()),
363            built: AtomicBool::new(self.built.load(Ordering::Relaxed)),
364        }
365    }
366}
367
368impl PartialEq for LookupCount {
369    fn eq(&self, other: &Self) -> bool {
370        self.get() == other.get()
371    }
372}
373
374impl Eq for LookupCount {}
375
376/// Where a lookup of what the globs of a module bring in counts its steps.
377#[derive(Clone, Copy)]
378pub(crate) enum Steps<'m> {
379    /// The load: on the index's [`LookupCount`], drained into the work of
380    /// the load at its next checkpoint.
381    Load,
382    /// A retained import read: reserve its storage before construction.
383    LoadAt {
384        memory: &'m Transient<'m>,
385        file: &'m RelPath,
386        line: usize,
387    },
388    /// A query after the load: on the query's own meter, against the limit
389    /// of the work of one query.
390    Query(&'m Meter),
391    /// The same query, with opt-in observations of native failed routes.
392    Observed(&'m QueryObservation<'m>),
393    /// Post-load traversal storage charged cumulatively to `ItemBytes`.
394    QueryItems {
395        meter: &'m Meter,
396        file: &'m RelPath,
397        line: Option<usize>,
398    },
399    /// A query proof with explicit live scratch admission and work charges.
400    QueryAt {
401        memory: &'m Transient<'m>,
402        file: &'m RelPath,
403        line: Option<usize>,
404    },
405}
406
407impl<'m> Steps<'m> {
408    pub(crate) fn reserve(self, bytes: usize) -> Result<(), LoadError> {
409        match self {
410            Self::LoadAt { memory, file, line } => memory.charge(bytes, file, Some(line)),
411            Self::QueryAt { memory, file, line } => memory.charge(bytes, file, line),
412            Self::QueryItems { meter, file, line } => meter.items(bytes, file, line),
413            Self::Load | Self::Query(_) | Self::Observed(_) => Ok(()),
414        }
415    }
416
417    pub(crate) fn storage_work(self, units: usize) -> Result<(), LoadError> {
418        match self {
419            Self::LoadAt { memory, file, line } => {
420                memory.work(units, file, Some(line))?;
421                crate::work::add(crate::work::Work::SettleSteps, units);
422                Ok(())
423            }
424            Self::QueryAt { memory, file, line } => {
425                memory.work(units, file, line)?;
426                crate::work::add(crate::work::Work::LookupCharges, units);
427                Ok(())
428            }
429            Self::QueryItems { meter, file, line } => {
430                meter.work(units, file, line)?;
431                crate::work::add(crate::work::Work::LookupCharges, units);
432                Ok(())
433            }
434            Self::Load | Self::Query(_) | Self::Observed(_) => Ok(()),
435        }
436    }
437
438    pub(crate) fn temporary(self) -> Option<Transient<'m>> {
439        match self {
440            Self::LoadAt { memory, .. } | Self::QueryAt { memory, .. } => Some(memory.child()),
441            Self::Load | Self::Query(_) | Self::Observed(_) | Self::QueryItems { .. } => None,
442        }
443    }
444
445    pub(crate) fn at(self, memory: &'m Transient<'m>) -> Self {
446        match self {
447            Self::LoadAt { file, line, .. } => Self::LoadAt { memory, file, line },
448            Self::QueryAt { file, line, .. } => Self::QueryAt { memory, file, line },
449            Self::Load | Self::Query(_) | Self::Observed(_) | Self::QueryItems { .. } => self,
450        }
451    }
452
453    pub(crate) fn query_meter(self) -> Option<&'m Meter> {
454        match self {
455            Self::Query(meter) | Self::QueryItems { meter, .. } => Some(meter),
456            Self::Observed(observation) => Some(observation.memory.meter),
457            Self::QueryAt { memory, .. } => Some(memory.meter),
458            Self::Load | Self::LoadAt { .. } => None,
459        }
460    }
461
462    /// Attach physical query-stack storage without changing load admission.
463    pub(crate) fn with_query_storage(
464        self,
465        memory: Option<&'m Transient<'m>>,
466        site: (&'m RelPath, Option<usize>),
467    ) -> Self {
468        if matches!(self, Self::QueryItems { .. }) {
469            return self;
470        }
471        memory.map_or(self, |memory| Self::QueryAt {
472            memory,
473            file: site.0,
474            line: site.1,
475        })
476    }
477}
478
479/// Admit native physical storage to the original cumulative item-byte grant.
480pub(crate) struct ItemAdmission<'m> {
481    meter: &'m Meter,
482    file: &'m RelPath,
483    live: usize,
484    failure: Option<LoadError>,
485}
486
487impl<'m> ItemAdmission<'m> {
488    pub(crate) const fn new(meter: &'m Meter, file: &'m RelPath) -> Self {
489        Self::resume(meter, file, 0)
490    }
491
492    /// Continue an account whose native payloads are still retained.
493    pub(crate) const fn resume(meter: &'m Meter, file: &'m RelPath, live: usize) -> Self {
494        Self {
495            meter,
496            file,
497            live,
498            failure: None,
499        }
500    }
501
502    pub(crate) fn error(&mut self, error: StorageError) -> LoadError {
503        self.failure
504            .take()
505            .unwrap_or_else(|| LoadError::new(self.file, None, LoadErrorKind::Storage(error)))
506    }
507
508    /// Restore this account's refusal, otherwise preserve an already typed error.
509    pub(crate) fn recover(&mut self, error: LoadError) -> LoadError {
510        self.failure.take().unwrap_or(error)
511    }
512}
513
514impl Admission for ItemAdmission<'_> {
515    fn resize(&mut self, live: usize) -> Result<(), StorageError> {
516        if self.failure.is_some() {
517            return Err(StorageError::AdmissionFailed);
518        }
519        if live > self.live
520            && let Err(error) = self.meter.items(live - self.live, self.file, None)
521        {
522            self.failure = Some(error);
523            return Err(StorageError::AdmissionFailed);
524        }
525        // ItemBytes is cumulative: freeing storage never refunds this grant.
526        self.live = live;
527        Ok(())
528    }
529}
530
531/// A refusal by one budget, naming the file and the line.
532pub(crate) fn over_budget(
533    budget: Budget,
534    limit: usize,
535    file: &RelPath,
536    line: Option<usize>,
537) -> LoadError {
538    LoadError::new(file, line, LoadErrorKind::Budget { budget, limit })
539}
540
541/// Add `amount` to `total`, refusing a sum above `limit`.
542fn add(total: &Cell<usize>, amount: usize, limit: usize) -> Result<(), ()> {
543    let sum = total.get().saturating_add(amount);
544    total.set(sum);
545    if sum > limit { Err(()) } else { Ok(()) }
546}
547
548impl Meter {
549    /// A scoped parser callback spends the same original grant on its own thread.
550    pub(crate) fn resume(options: &LoadOptions, usage: Usage) -> Self {
551        let meter = Self::new(options);
552        meter.total_bytes.set(usage.total_bytes);
553        meter.item_bytes.set(usage.item_bytes);
554        meter.fact_bytes.set(usage.fact_bytes);
555        meter.glob_peak.set(usage.glob_bytes);
556        meter.max_file_tokens.set(usage.max_file_tokens);
557        meter.max_recursion.set(usage.max_recursion);
558        meter.max_directory_depth.set(usage.max_directory_depth);
559        meter.work.set(usage.work);
560        meter
561    }
562
563    /// Snapshot the two counters a configuration callback can spend.
564    pub(crate) fn configuration_usage(&self) -> ConfigurationUsage {
565        ConfigurationUsage {
566            item_bytes: self.item_bytes.get(),
567            work: self.work.get(),
568        }
569    }
570
571    /// Commit only actual configuration scratch/work spent by a completed callback.
572    pub(crate) fn configuration_spent(
573        &self,
574        before: Usage,
575        after: ConfigurationUsage,
576        file: &RelPath,
577    ) -> Result<(), LoadError> {
578        let backwards = || {
579            LoadError::new(
580                file,
581                None,
582                LoadErrorKind::Internal {
583                    what: "configuration callback usage moved backwards".to_owned(),
584                },
585            )
586        };
587        self.items(
588            after
589                .item_bytes
590                .checked_sub(before.item_bytes)
591                .ok_or_else(backwards)?,
592            file,
593            None,
594        )?;
595        self.work(
596            after.work.checked_sub(before.work).ok_or_else(backwards)?,
597            file,
598            None,
599        )
600    }
601    pub(crate) fn new(options: &LoadOptions) -> Self {
602        Self {
603            options: options.clone(),
604            total_bytes: Cell::new(0),
605            item_bytes: Cell::new(0),
606            fact_bytes: Cell::new(0),
607            glob_bytes: Cell::new(0),
608            glob_peak: Cell::new(0),
609            max_file_tokens: Cell::new(0),
610            max_recursion: Cell::new(0),
611            max_directory_depth: Cell::new(0),
612            work: Cell::new(0),
613            work_limit: options.max_work,
614            query_passed: Cell::new(None),
615        }
616    }
617
618    /// The meter of one query after a load made with `options`: its work is
619    /// the lookup steps of the query, from zero, against `max_query_work`.
620    pub(crate) fn query(options: &LoadOptions) -> Self {
621        Self {
622            work_limit: options.max_query_work,
623            ..Self::new(options)
624        }
625    }
626
627    /// Continue the same query's work and storage allowance across stages.
628    pub(crate) fn resume_query(options: &LoadOptions, usage: Usage) -> Self {
629        Self {
630            work_limit: options.max_query_work,
631            ..Self::resume(options, usage)
632        }
633    }
634
635    /// Count `units` lookup steps of a query, made in `module`. The count is
636    /// not refused here, where the lookup answers; the first count that
637    /// passes the limit records its module, and the query is refused at its
638    /// next checkpoint (see [`Meter::query_passed`]).
639    pub(crate) fn count_query(&self, units: usize, module: usize) {
640        let sum = self.work.get().saturating_add(units);
641        self.work.set(sum);
642        if sum > self.work_limit && self.query_passed.get().is_none() {
643            self.query_passed.set(Some(module));
644        }
645    }
646
647    /// The module whose lookup made the work of the query pass its limit,
648    /// if one did.
649    pub(crate) fn query_passed(&self) -> Option<usize> {
650        self.query_passed.get()
651    }
652
653    /// The most steps of work this meter allows.
654    pub(crate) fn work_limit(&self) -> usize {
655        self.work_limit
656    }
657
658    pub(crate) fn options(&self) -> &LoadOptions {
659        &self.options
660    }
661
662    /// Charge the text of `file`, just read, to the bytes of the load.
663    pub(crate) fn read(&self, file: &RelPath, text: &str) -> Result<(), LoadError> {
664        self.read_bytes(file, text.len())
665    }
666
667    /// Charge binary input before a bounded decoder or hash processes it.
668    pub(crate) fn read_bytes(&self, file: &RelPath, bytes: usize) -> Result<(), LoadError> {
669        let limit = self.options.max_total_bytes;
670        add(&self.total_bytes, bytes, limit)
671            .map_err(|()| over_budget(Budget::TotalBytes, limit, file, None))
672    }
673
674    /// Charge `bytes` of index records built for `file` at `line`.
675    ///
676    /// Every charge is an upper bound of the allocations it covers, derived
677    /// from the layout of the containers that hold them (see `crate::cost`),
678    /// never an estimate measured on typical input, so the budget bounds what
679    /// the index and the walk allocate whatever the shape of the input.
680    pub(crate) fn items(
681        &self,
682        bytes: usize,
683        file: &RelPath,
684        line: Option<usize>,
685    ) -> Result<(), LoadError> {
686        let limit = self.options.max_item_bytes;
687        add(&self.item_bytes, bytes, limit)
688            .map_err(|()| over_budget(Budget::ItemBytes, limit, file, line))
689    }
690
691    /// Charge `bytes` of glob scope tables built for the glob import at
692    /// `line` of `file`.
693    ///
694    /// Like [`Meter::items`], every charge is an upper bound of the
695    /// allocations it covers, derived from the layout of the containers that
696    /// hold them (see `crate::cost`). Unlike the other byte budgets, this one
697    /// bounds what is held at once: what is freed is released
698    /// ([`Meter::release_globs`]), and the budget refuses the charge that
699    /// would make what is held pass the limit.
700    pub(crate) fn globs(
701        &self,
702        bytes: usize,
703        file: &RelPath,
704        line: Option<usize>,
705    ) -> Result<(), LoadError> {
706        let limit = self.options.max_glob_bytes;
707        let held = add(&self.glob_bytes, bytes, limit);
708        self.glob_peak
709            .set(self.glob_peak.get().max(self.glob_bytes.get()));
710        held.map_err(|()| over_budget(Budget::GlobBytes, limit, file, line))
711    }
712
713    /// Charge `units` steps of glob table work made for the glob import at
714    /// `line` of `file`, before they are made.
715    ///
716    /// Unlike the glob bytes, the work is never released: the budget bounds
717    /// every step one load makes, and refuses the charge that makes the count
718    /// pass the limit.
719    pub(crate) fn work(
720        &self,
721        units: usize,
722        file: &RelPath,
723        line: Option<usize>,
724    ) -> Result<(), LoadError> {
725        let limit = self.work_limit;
726        #[cfg(test)]
727        charges::record(units);
728        add(&self.work, units, limit).map_err(|()| over_budget(Budget::Work, limit, file, line))
729    }
730
731    /// Release `bytes` of glob scope tables charged before and now freed.
732    pub(crate) fn release_globs(&self, bytes: usize) {
733        let held = self
734            .glob_bytes
735            .get()
736            .checked_sub(bytes)
737            .expect("only what was charged is released");
738        self.glob_bytes.set(held);
739    }
740
741    /// What the facts of the next file may still take: the bytes charged so
742    /// far and the limit.
743    pub(crate) fn fact_allowance(&self) -> FactAllowance {
744        FactAllowance {
745            spent: self.fact_bytes.get(),
746            limit: self.options.max_fact_bytes,
747        }
748    }
749
750    /// Record the facts of a file, charged on its parse thread.
751    pub(crate) fn facts(&self, bytes: usize, file: &RelPath) -> Result<(), LoadError> {
752        let total = self
753            .fact_bytes
754            .get()
755            .checked_add(bytes)
756            .filter(|total| *total <= self.options.max_fact_bytes)
757            .ok_or_else(|| {
758                LoadError::new(
759                    file,
760                    None,
761                    LoadErrorKind::Internal {
762                        what: "parser fact accounting exceeded its original allowance".to_owned(),
763                    },
764                )
765            })?;
766        self.fact_bytes.set(total);
767        Ok(())
768    }
769
770    /// Record what the pre-scan of a parsed file counted.
771    pub(crate) fn scanned(&self, scan: Scan) {
772        self.max_file_tokens
773            .set(self.max_file_tokens.get().max(scan.tokens));
774        self.max_recursion
775            .set(self.max_recursion.get().max(scan.recursion));
776    }
777
778    /// Check a directory `depth` levels below its root and record it.
779    pub(crate) fn directory(&self, depth: usize, dir: &RelPath) -> Result<(), LoadError> {
780        if depth > Budget::DirectoryDepth.limit() {
781            return Err(over_budget(
782                Budget::DirectoryDepth,
783                Budget::DirectoryDepth.limit(),
784                dir,
785                None,
786            ));
787        }
788        self.max_directory_depth
789            .set(self.max_directory_depth.get().max(depth));
790        Ok(())
791    }
792
793    pub(crate) fn usage(&self) -> Usage {
794        Usage {
795            total_bytes: self.total_bytes.get(),
796            item_bytes: self.item_bytes.get(),
797            fact_bytes: self.fact_bytes.get(),
798            glob_bytes: self.glob_peak.get(),
799            max_file_tokens: self.max_file_tokens.get(),
800            max_recursion: self.max_recursion.get(),
801            max_directory_depth: self.max_directory_depth.get(),
802            work: self.work.get(),
803        }
804    }
805}
806
807/// The charges of glob table work made on this thread, for the tests that
808/// check where a load is refused.
809#[cfg(test)]
810pub(crate) mod charges {
811    use std::cell::RefCell;
812
813    thread_local! {
814        /// Each charge of glob table work since the last [`take`].
815        static CHARGES: RefCell<Vec<usize>> = const { RefCell::new(Vec::new()) };
816    }
817
818    /// Record one charge.
819    pub(super) fn record(units: usize) {
820        CHARGES.with_borrow_mut(|charges| charges.push(units));
821    }
822
823    /// The charges recorded since the last call, in the order they were made.
824    pub(crate) fn take() -> Vec<usize> {
825        CHARGES.take()
826    }
827}
828
829/// The fact bytes one file may take, handed to its parse thread.
830#[derive(Debug, Clone, Copy)]
831pub(crate) struct FactAllowance {
832    /// Bytes the earlier files of the load took.
833    pub(crate) spent: usize,
834    /// The limit of the load.
835    pub(crate) limit: usize,
836}
837
838#[derive(Clone, Copy)]
839pub(crate) struct ConfigurationUsage {
840    item_bytes: usize,
841    work: usize,
842}
843
844#[cfg(test)]
845mod tests {
846    use std::error::Error;
847
848    use purrdf_lex::allocation::{Admission, Memory, StorageError};
849
850    use super::{ItemAdmission, Meter, NativeAdmission, Steps, Transient, charges};
851    use crate::budget::Budget;
852    use crate::error::{LoadError, LoadErrorKind, Origin};
853    use crate::options::LoadOptions;
854    use crate::path::RelPath;
855
856    fn meter(max_work: usize) -> Meter {
857        Meter::new(&LoadOptions {
858            max_work,
859            ..LoadOptions::default()
860        })
861    }
862
863    #[test]
864    fn native_recovery_preserves_nested_provenance_and_restores_its_own_refusal() {
865        let account = RelPath::new("account/Cargo.toml").unwrap();
866        let nested = RelPath::new("nested/src/lib.rs").unwrap();
867        let meter = Meter::new(&LoadOptions {
868            max_item_bytes: 0,
869            ..LoadOptions::default()
870        });
871        let mut admission = ItemAdmission::new(&meter, &account);
872        let original = || {
873            LoadError::new(
874                &nested,
875                Some(17),
876                LoadErrorKind::Storage(StorageError::AdmissionFailed),
877            )
878            .reached_by(&Origin::Discovery)
879        };
880        let preserved = admission.recover(original());
881        assert_eq!(preserved.file, nested);
882        assert_eq!(preserved.line, Some(17));
883        assert!(matches!(
884            preserved.origin.as_deref(),
885            Some(Origin::Discovery)
886        ));
887        assert!(matches!(
888            preserved.kind,
889            LoadErrorKind::Storage(StorageError::AdmissionFailed)
890        ));
891        assert_eq!(admission.resize(1), Err(StorageError::AdmissionFailed));
892        let restored = admission.recover(original());
893        assert_eq!(restored.file, account);
894        assert_eq!(restored.line, None);
895        assert!(matches!(
896            restored.kind,
897            LoadErrorKind::Budget {
898                budget: Budget::ItemBytes,
899                limit: 0
900            }
901        ));
902    }
903
904    #[test]
905    fn native_storage_preserves_the_item_limit_and_cumulative_charges() {
906        let file = RelPath::new("Cargo.toml").expect("path");
907        let meter = Meter::new(&LoadOptions {
908            max_item_bytes: 16,
909            ..LoadOptions::default()
910        });
911        let mut admission = ItemAdmission::new(&meter, &file);
912        admission.resize(16).expect("exact limit");
913        admission.resize(8).expect("released storage");
914        assert_eq!(meter.usage().item_bytes, 16);
915        let native = admission.resize(9).expect_err("growth remains cumulative");
916        assert_eq!(native, StorageError::AdmissionFailed);
917        assert_eq!(admission.resize(8), Err(StorageError::AdmissionFailed));
918        let error = admission.error(native);
919        assert!(matches!(
920            error.kind,
921            LoadErrorKind::Budget {
922                budget: Budget::ItemBytes,
923                limit: 16,
924            }
925        ));
926        assert_eq!(error.file, file);
927        assert_eq!(meter.usage().item_bytes, 17);
928    }
929
930    #[test]
931    fn native_storage_capacity_failure_has_its_original_error_source() {
932        let file = RelPath::new("Cargo.toml").expect("path");
933        let meter = Meter::new(&LoadOptions::default());
934        let mut admission = ItemAdmission::new(&meter, &file);
935        let mut values = Vec::<u64>::new();
936        let native = {
937            let mut memory = Memory::new(&mut admission);
938            memory
939                .reserve(&mut values, 1)
940                .expect("small native allocation");
941            let native = memory
942                .reserve(&mut values, usize::MAX)
943                .expect_err("impossible native capacity");
944            memory
945                .reserve(&mut values, 2)
946                .expect("capacity failure did not poison admission");
947            native
948        };
949        let error = admission.error(native);
950        assert!(matches!(error.kind, LoadErrorKind::Storage(found) if found == native));
951        assert_eq!(error.file, file);
952        assert_eq!(
953            error.source().expect("native source").to_string(),
954            native.to_string()
955        );
956        assert_eq!(values.len(), 0);
957    }
958
959    #[test]
960    fn work_up_to_the_limit_is_accepted_and_the_charge_that_passes_it_is_refused() {
961        let file = RelPath::new("src/lib.rs").expect("path");
962        let meter = meter(10);
963        meter.work(4, &file, Some(3)).expect("below the limit");
964        meter.work(6, &file, Some(3)).expect("at the limit");
965        assert_eq!(meter.usage().work, 10);
966        let error = meter.work(5, &file, Some(7)).expect_err("over the limit");
967        assert!(
968            matches!(
969                error.kind,
970                LoadErrorKind::Budget {
971                    budget: Budget::Work,
972                    limit: 10
973                }
974            ),
975            "{error}"
976        );
977        assert_eq!((error.file.as_str(), error.line), ("src/lib.rs", Some(7)));
978        // The count at the refusal is the limit and the charge that passed it.
979        assert_eq!(meter.usage().work, 15);
980        assert_eq!(charges::take(), vec![4, 6, 5]);
981    }
982
983    #[test]
984    fn work_is_never_released_and_each_meter_counts_from_zero() {
985        let file = RelPath::new("src/lib.rs").expect("path");
986        let first = meter(100);
987        first.globs(64, &file, None).expect("glob bytes");
988        first.work(40, &file, None).expect("work");
989        first.release_globs(64);
990        first.work(40, &file, None).expect("work");
991        assert_eq!(first.usage().work, 80);
992        assert_eq!(first.usage().glob_bytes, 64);
993        let second = meter(100);
994        assert_eq!(second.usage().work, 0);
995        second.work(1, &file, None).expect("work");
996        assert_eq!(second.usage().work, 1);
997        assert_eq!(first.usage().work, 80);
998    }
999
1000    #[test]
1001    fn transient_reservations_refuse_atomically_and_release_on_every_exit() {
1002        let file = RelPath::new("src/imports.rs").expect("path");
1003        for limit in [63, 64] {
1004            let meter = Meter::new(&LoadOptions {
1005                max_glob_bytes: limit,
1006                ..LoadOptions::default()
1007            });
1008            meter.globs(16, &file, Some(2)).expect("retained tables");
1009            {
1010                let first = Transient::new(&meter);
1011                first
1012                    .charge(24, &file, Some(3))
1013                    .expect("previous generation");
1014                {
1015                    let next = first.child();
1016                    let result = next.charge(24, &file, Some(7));
1017                    if limit == 64 {
1018                        result.expect("exact simultaneous limit");
1019                        assert_eq!(meter.glob_bytes.get(), 64);
1020                    } else {
1021                        let error = result.expect_err("one below simultaneous limit");
1022                        assert_eq!(
1023                            (error.file.as_str(), error.line),
1024                            ("src/imports.rs", Some(7))
1025                        );
1026                        assert!(matches!(
1027                            error.kind,
1028                            LoadErrorKind::Budget {
1029                                budget: Budget::GlobBytes,
1030                                limit: 63
1031                            }
1032                        ));
1033                        assert_eq!(next.bytes.get(), 0);
1034                        assert_eq!(meter.glob_bytes.get(), 40);
1035                    }
1036                    assert!(next.charge(usize::MAX, &file, Some(9)).is_err());
1037                    assert_eq!(meter.glob_bytes.get(), if limit == 64 { 64 } else { 40 });
1038                }
1039                assert_eq!(meter.glob_bytes.get(), 40);
1040                assert!(first.charge(limit, &file, Some(11)).is_err());
1041                assert_eq!(first.bytes.get(), 24);
1042                first
1043                    .work(1, &file, Some(3))
1044                    .expect("work is nonrefundable");
1045            }
1046            assert_eq!(meter.glob_bytes.get(), 16);
1047            assert_eq!(meter.usage().work, 1);
1048            let neighbor = Transient::new(&meter);
1049            neighbor
1050                .charge(limit - 16, &file, Some(12))
1051                .expect("failed owners left no phantom reservation");
1052        }
1053    }
1054
1055    #[test]
1056    fn retained_payload_moves_its_original_grant_without_readmission() {
1057        let file = RelPath::new("src/imports.rs").expect("path");
1058        let options = LoadOptions {
1059            max_glob_bytes: 64,
1060            ..LoadOptions::default()
1061        };
1062        let meter = Meter::new(&options);
1063        let owner = Transient::new(&meter);
1064        owner.charge(16, &file, Some(1)).expect("batch storage");
1065        {
1066            let scratch = owner.child();
1067            scratch.charge(48, &file, Some(2)).expect("exact peak");
1068            scratch
1069                .transfer_to(&owner, 24, &file, Some(2))
1070                .expect("retained result");
1071            assert_eq!(meter.glob_bytes.get(), 64);
1072            assert_eq!(meter.usage().glob_bytes, 64);
1073            assert!(scratch.transfer_to(&owner, 25, &file, Some(3)).is_err());
1074            assert_eq!((scratch.bytes.get(), owner.bytes.get()), (24, 40));
1075            let other_meter = Meter::new(&options);
1076            let unrelated = Transient::new(&other_meter);
1077            assert!(scratch.transfer_to(&unrelated, 1, &file, Some(4)).is_err());
1078            assert_eq!(other_meter.glob_bytes.get(), 0);
1079        }
1080        assert_eq!(meter.glob_bytes.get(), 40);
1081        owner
1082            .charge(24, &file, Some(5))
1083            .expect("released scratch is reusable");
1084        assert!(owner.charge(1, &file, Some(6)).is_err());
1085        drop(owner);
1086        assert_eq!(meter.glob_bytes.get(), 0);
1087    }
1088
1089    #[test]
1090    fn native_emission_spill_preserves_cumulative_item_admission() {
1091        let file = RelPath::new("src/lib.rs").expect("path");
1092        let run = |count, limit| {
1093            let meter = Meter::new(&LoadOptions {
1094                max_item_bytes: limit,
1095                max_glob_bytes: 0,
1096                ..LoadOptions::default()
1097            });
1098            let mut pending = purrdf_lex::walk::WorkList::<usize, 1>::new();
1099            let mut result = Ok(());
1100            for value in 0..count {
1101                let live = pending.heap_capacity() * size_of::<usize>();
1102                let mut admission = NativeAdmission::items(&meter, &file, Some(7), live);
1103                result = pending
1104                    .try_push_admitted(value, &mut Memory::resume(&mut admission, live))
1105                    .map_err(|error| admission.graph_error(error.into()));
1106                if result.is_err() {
1107                    break;
1108                }
1109            }
1110            let spent = meter.usage().item_bytes;
1111            drop(pending);
1112            assert_eq!(meter.usage().item_bytes, spent, "items are cumulative");
1113            assert_eq!(meter.usage().glob_bytes, 0);
1114            (result, spent)
1115        };
1116        assert!(
1117            run(1, 0).0.is_ok(),
1118            "inline neighbor needs no item allocation"
1119        );
1120        let (result, spent) = run(33, usize::MAX);
1121        result.expect("several native growths");
1122        assert!(spent > 0);
1123        assert!(run(33, spent).0.is_ok());
1124        let (result, _) = run(33, spent - 1);
1125        let error = result.expect_err("one item byte less");
1126        assert_eq!((error.file.as_str(), error.line), ("src/lib.rs", Some(7)));
1127        assert!(matches!(error.kind, LoadErrorKind::Budget {
1128            budget: Budget::ItemBytes, limit,
1129        } if limit == spent - 1));
1130    }
1131
1132    #[test]
1133    fn native_graph_storage_preserves_overlapping_grants_and_typed_refusals() {
1134        let file = RelPath::new("src/imports.rs").expect("path");
1135        let graph = [vec![1], vec![0, 2], vec![]];
1136        let run = |limit| {
1137            let meter = Meter::new(&LoadOptions {
1138                max_glob_bytes: limit,
1139                ..LoadOptions::default()
1140            });
1141            let outer = Transient::new(&meter);
1142            outer
1143                .charge(17, &file, Some(2))
1144                .expect("unrelated live payload");
1145            {
1146                let lease = outer.child();
1147                let mut admission = NativeAdmission::new(Steps::LoadAt {
1148                    memory: &lease,
1149                    file: &file,
1150                    line: 7,
1151                });
1152                let result = purrdf_core::graph::tarjan_scc_with_memory(
1153                    &graph,
1154                    &mut Memory::new(&mut admission),
1155                )
1156                .map_err(|error| admission.graph_error(error));
1157                match result {
1158                    Ok(components) => {
1159                        assert_eq!(components.len(), 2);
1160                        // Construction scratch has died; the surviving result
1161                        // remains covered even after the native callback dies.
1162                        assert!(lease.bytes.get() > 0);
1163                        assert_eq!(meter.glob_bytes.get(), 17 + lease.bytes.get());
1164                        drop(components);
1165                    }
1166                    Err(error) => {
1167                        assert_eq!(
1168                            (error.file.as_str(), error.line),
1169                            ("src/imports.rs", Some(7))
1170                        );
1171                        assert!(matches!(error.kind, LoadErrorKind::Budget {
1172                            budget: Budget::GlobBytes, limit: found,
1173                        } if found == limit));
1174                        assert_eq!(lease.bytes.get(), 0);
1175                    }
1176                }
1177            }
1178            assert_eq!(meter.glob_bytes.get(), 17);
1179            meter.usage().glob_bytes
1180        };
1181        let peak = run(usize::MAX);
1182        assert!(peak > 17);
1183        assert_eq!(run(peak), peak);
1184        assert!(run(peak - 1) < peak);
1185    }
1186}