Skip to main content

sheetkit_core/formula/
budget.rs

1//! Finite resource limits shared by formula parsing, mutation, and calculation.
2
3use std::cell::{OnceCell, RefCell};
4use std::rc::Rc;
5
6use crate::error::{Error, Result};
7use crate::resource::{
8    ResourceCategory, ResourceDimension, ResourceLimitError, ResourceOperation, ResourceStage,
9};
10
11/// Finite limits for one formula parse, mutation, or calculation operation.
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub struct FormulaLimits {
14    pub per_formula_input_bytes: u64,
15    pub per_formula_nesting_depth: u64,
16    pub per_formula_binary_chain_depth: u64,
17    pub per_formula_tokens: u64,
18    pub per_formula_ast_nodes: u64,
19    pub operation_input_bytes: u64,
20    pub operation_tokens: u64,
21    pub operation_ast_nodes: u64,
22    pub operation_range_cells: u64,
23    pub operation_dependency_edges: u64,
24    pub operation_ready_queue_ops: u64,
25    pub operation_evaluation_steps: u64,
26    pub operation_match_work: u64,
27    pub operation_output_bytes: u64,
28}
29
30impl FormulaLimits {
31    /// Secure defaults calibrated against the repository's formula corpus.
32    pub const fn secure_default() -> Self {
33        Self {
34            per_formula_input_bytes: 32_768,
35            per_formula_nesting_depth: 64,
36            per_formula_binary_chain_depth: 512,
37            per_formula_tokens: 16_384,
38            per_formula_ast_nodes: 16_384,
39            operation_input_bytes: 4 * 1024 * 1024,
40            operation_tokens: 1_048_576,
41            operation_ast_nodes: 1_048_576,
42            operation_range_cells: 131_072,
43            operation_dependency_edges: 524_288,
44            operation_ready_queue_ops: 524_288,
45            operation_evaluation_steps: 1_048_576,
46            operation_match_work: 1_048_576,
47            operation_output_bytes: 16 * 1024 * 1024,
48        }
49    }
50}
51
52impl Default for FormulaLimits {
53    fn default() -> Self {
54        Self::secure_default()
55    }
56}
57
58#[derive(Debug, Default, Clone, Copy)]
59struct FormulaCounters {
60    input_bytes: u64,
61    tokens: u64,
62    ast_nodes: u64,
63    range_cells: u64,
64    dependency_edges: u64,
65    ready_queue_ops: u64,
66    evaluation_steps: u64,
67    match_work: u64,
68    output_bytes: u64,
69}
70
71/// Operation counters kept inline until the owning budget is first cloned.
72/// The first clone moves the current values behind an `Rc` that the
73/// original and every clone then share, so a budget that is never cloned
74/// needs no heap allocation.
75#[derive(Debug, Default)]
76struct CounterCell {
77    inline: RefCell<FormulaCounters>,
78    shared: OnceCell<Rc<RefCell<FormulaCounters>>>,
79}
80
81impl CounterCell {
82    #[inline]
83    fn get(&self) -> &RefCell<FormulaCounters> {
84        match self.shared.get() {
85            Some(shared) => shared,
86            None => &self.inline,
87        }
88    }
89
90    fn share(&self) -> Rc<RefCell<FormulaCounters>> {
91        Rc::clone(
92            self.shared
93                .get_or_init(|| Rc::new(RefCell::new(*self.inline.borrow()))),
94        )
95    }
96}
97
98impl Clone for CounterCell {
99    fn clone(&self) -> Self {
100        Self {
101            inline: RefCell::default(),
102            shared: OnceCell::from(self.share()),
103        }
104    }
105}
106
107/// A calculation-owned budget. Clones share counters and cannot reset work.
108#[derive(Debug, Clone)]
109pub struct FormulaBudget {
110    operation: ResourceOperation,
111    limits: FormulaLimits,
112    counters: CounterCell,
113}
114
115impl FormulaBudget {
116    const HARD_PER_FORMULA_INPUT_BYTES: u64 = 65_536;
117    const HARD_PER_FORMULA_NESTING_DEPTH: u64 = 128;
118    const HARD_PER_FORMULA_BINARY_CHAIN_DEPTH: u64 = 4_096;
119    const HARD_PER_FORMULA_TOKENS: u64 = 65_536;
120    const HARD_PER_FORMULA_AST_NODES: u64 = 32_768;
121    const HARD_OPERATION_INPUT_BYTES: u64 = 32 * 1024 * 1024;
122    const HARD_OPERATION_TOKENS: u64 = 8_388_608;
123    const HARD_OPERATION_AST_NODES: u64 = 8_388_608;
124    const HARD_OPERATION_RANGE_CELLS: u64 = 1_048_576;
125    const HARD_OPERATION_DEPENDENCY_EDGES: u64 = 4_194_304;
126    const HARD_OPERATION_READY_QUEUE_OPS: u64 = 4_194_304;
127    const HARD_OPERATION_EVALUATION_STEPS: u64 = 8_388_608;
128    const HARD_OPERATION_MATCH_WORK: u64 = 16_777_216;
129    const HARD_OPERATION_OUTPUT_BYTES: u64 = 64 * 1024 * 1024;
130    const HARD_EVALUATION_RECURSION_DEPTH: u64 = 1_024;
131
132    /// Create a parsing budget, rejecting limits above hard ceilings.
133    pub fn for_parse(limits: FormulaLimits) -> Result<Self> {
134        Self::new(ResourceOperation::FormulaParse, limits)
135    }
136
137    /// Create a formula-mutation budget, rejecting limits above hard ceilings.
138    pub fn for_mutation(limits: FormulaLimits) -> Result<Self> {
139        Self::new(ResourceOperation::FormulaMutate, limits)
140    }
141
142    pub(crate) fn secure_mutation() -> Self {
143        Self {
144            operation: ResourceOperation::FormulaMutate,
145            limits: FormulaLimits::secure_default(),
146            counters: CounterCell::default(),
147        }
148    }
149
150    /// Create a calculation budget, rejecting limits above hard ceilings.
151    pub fn for_calculation(limits: FormulaLimits) -> Result<Self> {
152        Self::new(ResourceOperation::FormulaCalculate, limits)
153    }
154
155    pub(crate) fn secure_calculation() -> Self {
156        Self {
157            operation: ResourceOperation::FormulaCalculate,
158            limits: FormulaLimits::secure_default(),
159            counters: CounterCell::default(),
160        }
161    }
162
163    fn new(operation: ResourceOperation, limits: FormulaLimits) -> Result<Self> {
164        for (dimension, limit, ceiling) in [
165            (
166                ResourceDimension::InputBytes,
167                limits.per_formula_input_bytes,
168                Self::HARD_PER_FORMULA_INPUT_BYTES,
169            ),
170            (
171                ResourceDimension::NestingDepth,
172                limits.per_formula_nesting_depth,
173                Self::HARD_PER_FORMULA_NESTING_DEPTH,
174            ),
175            (
176                ResourceDimension::NestingDepth,
177                limits.per_formula_binary_chain_depth,
178                Self::HARD_PER_FORMULA_BINARY_CHAIN_DEPTH,
179            ),
180            (
181                ResourceDimension::TokenCount,
182                limits.per_formula_tokens,
183                Self::HARD_PER_FORMULA_TOKENS,
184            ),
185            (
186                ResourceDimension::NodeCount,
187                limits.per_formula_ast_nodes,
188                Self::HARD_PER_FORMULA_AST_NODES,
189            ),
190            (
191                ResourceDimension::InputBytes,
192                limits.operation_input_bytes,
193                Self::HARD_OPERATION_INPUT_BYTES,
194            ),
195            (
196                ResourceDimension::TokenCount,
197                limits.operation_tokens,
198                Self::HARD_OPERATION_TOKENS,
199            ),
200            (
201                ResourceDimension::NodeCount,
202                limits.operation_ast_nodes,
203                Self::HARD_OPERATION_AST_NODES,
204            ),
205            (
206                ResourceDimension::RangeCellCount,
207                limits.operation_range_cells,
208                Self::HARD_OPERATION_RANGE_CELLS,
209            ),
210            (
211                ResourceDimension::DependencyEdgeCount,
212                limits.operation_dependency_edges,
213                Self::HARD_OPERATION_DEPENDENCY_EDGES,
214            ),
215            (
216                ResourceDimension::OperationCount,
217                limits.operation_ready_queue_ops,
218                Self::HARD_OPERATION_READY_QUEUE_OPS,
219            ),
220            (
221                ResourceDimension::OperationCount,
222                limits.operation_evaluation_steps,
223                Self::HARD_OPERATION_EVALUATION_STEPS,
224            ),
225            (
226                ResourceDimension::MatchWork,
227                limits.operation_match_work,
228                Self::HARD_OPERATION_MATCH_WORK,
229            ),
230            (
231                ResourceDimension::OutputBytes,
232                limits.operation_output_bytes,
233                Self::HARD_OPERATION_OUTPUT_BYTES,
234            ),
235        ] {
236            if limit > ceiling {
237                return Err(resource_error(
238                    operation,
239                    dimension,
240                    ceiling,
241                    limit,
242                    ResourceStage::Validate,
243                ));
244            }
245        }
246        Ok(Self {
247            operation,
248            limits,
249            counters: CounterCell::default(),
250        })
251    }
252
253    /// Charge lexical work for one formula before recursive parsing starts.
254    pub(crate) fn charge_lexical(&self, input_bytes: u64, tokens: u64) -> Result<()> {
255        self.check_input(input_bytes)?;
256        self.check_local(
257            ResourceDimension::InputBytes,
258            self.limits.per_formula_input_bytes,
259            input_bytes,
260            ResourceStage::Parse,
261        )?;
262        self.check_local(
263            ResourceDimension::TokenCount,
264            self.limits.per_formula_tokens,
265            tokens,
266            ResourceStage::Parse,
267        )?;
268        self.charge_counter(
269            ResourceDimension::InputBytes,
270            self.limits.operation_input_bytes,
271            input_bytes,
272            ResourceStage::Parse,
273            |c| &mut c.input_bytes,
274        )?;
275        self.charge_counter(
276            ResourceDimension::TokenCount,
277            self.limits.operation_tokens,
278            tokens,
279            ResourceStage::Parse,
280            |c| &mut c.tokens,
281        )
282    }
283
284    pub(crate) fn check_input(&self, observed: u64) -> Result<()> {
285        self.check_local(
286            ResourceDimension::InputBytes,
287            self.limits.per_formula_input_bytes,
288            observed,
289            ResourceStage::Parse,
290        )
291    }
292
293    /// Check recursive-entry depth before the parser descends.
294    pub(crate) fn check_nesting(&self, observed: u64) -> Result<()> {
295        self.check_local(
296            ResourceDimension::NestingDepth,
297            self.limits.per_formula_nesting_depth,
298            observed,
299            ResourceStage::Parse,
300        )
301    }
302
303    pub(crate) fn check_binary_chain(&self, observed: u64) -> Result<()> {
304        self.check_local(
305            ResourceDimension::NestingDepth,
306            self.limits.per_formula_binary_chain_depth,
307            observed,
308            ResourceStage::Parse,
309        )
310    }
311
312    pub(crate) fn check_evaluation_depth(&self, observed: u64) -> Result<()> {
313        self.check_local(
314            ResourceDimension::NestingDepth,
315            Self::HARD_EVALUATION_RECURSION_DEPTH,
316            observed,
317            ResourceStage::Calculate,
318        )
319    }
320
321    /// Charge the completed AST without resetting operation counters.
322    pub(crate) fn charge_ast(&self, nodes: u64, depth: u64, binary_chain: u64) -> Result<()> {
323        self.check_nesting(depth)?;
324        self.check_local(
325            ResourceDimension::NestingDepth,
326            self.limits.per_formula_binary_chain_depth,
327            binary_chain,
328            ResourceStage::Parse,
329        )?;
330        self.check_local(
331            ResourceDimension::NodeCount,
332            self.limits.per_formula_ast_nodes,
333            nodes,
334            ResourceStage::Parse,
335        )?;
336        self.charge_counter(
337            ResourceDimension::NodeCount,
338            self.limits.operation_ast_nodes,
339            nodes,
340            ResourceStage::Parse,
341            |c| &mut c.ast_nodes,
342        )
343    }
344
345    pub(crate) fn charge_range_cells(&self, amount: u64) -> Result<()> {
346        self.charge_counter(
347            ResourceDimension::RangeCellCount,
348            self.limits.operation_range_cells,
349            amount,
350            ResourceStage::Calculate,
351            |c| &mut c.range_cells,
352        )
353    }
354
355    pub(crate) fn charge_dependency_edges(&self, amount: u64) -> Result<()> {
356        self.charge_counter(
357            ResourceDimension::DependencyEdgeCount,
358            self.limits.operation_dependency_edges,
359            amount,
360            ResourceStage::Calculate,
361            |c| &mut c.dependency_edges,
362        )
363    }
364
365    pub(crate) fn charge_ready_queue_ops(&self, amount: u64) -> Result<()> {
366        self.charge_counter(
367            ResourceDimension::OperationCount,
368            self.limits.operation_ready_queue_ops,
369            amount,
370            ResourceStage::Calculate,
371            |c| &mut c.ready_queue_ops,
372        )
373    }
374
375    pub(crate) fn charge_evaluation_steps(&self, amount: u64) -> Result<()> {
376        self.charge_counter(
377            ResourceDimension::OperationCount,
378            self.limits.operation_evaluation_steps,
379            amount,
380            ResourceStage::Calculate,
381            |c| &mut c.evaluation_steps,
382        )
383    }
384
385    pub(crate) fn charge_match_work(&self, amount: u64) -> Result<()> {
386        self.charge_counter(
387            ResourceDimension::MatchWork,
388            self.limits.operation_match_work,
389            amount,
390            ResourceStage::Calculate,
391            |c| &mut c.match_work,
392        )
393    }
394
395    pub(crate) fn charge_output_bytes(&self, amount: u64) -> Result<()> {
396        self.charge_counter(
397            ResourceDimension::OutputBytes,
398            self.limits.operation_output_bytes,
399            amount,
400            ResourceStage::Calculate,
401            |c| &mut c.output_bytes,
402        )
403    }
404
405    /// Charge one opaque formula copied or shifted by a mutation operation.
406    pub(crate) fn charge_mutation_formula(
407        &self,
408        input_bytes: u64,
409        output_bytes: u64,
410    ) -> Result<()> {
411        self.charge_mutation_input(input_bytes)?;
412        self.charge_mutation_output(output_bytes)
413    }
414
415    /// Charge one opaque formula before mutation code scans or copies it.
416    pub(crate) fn charge_mutation_input(&self, input_bytes: u64) -> Result<()> {
417        self.check_mutation_input(input_bytes)?;
418        self.charge_mutation_input_total(input_bytes)
419    }
420
421    /// Check one opaque formula before any scan proportional to its bytes.
422    pub(crate) fn check_mutation_input(&self, input_bytes: u64) -> Result<()> {
423        self.check_local(
424            ResourceDimension::InputBytes,
425            self.limits.per_formula_input_bytes,
426            input_bytes,
427            ResourceStage::Validate,
428        )
429    }
430
431    /// Charge cumulative mutation scans after checked bulk preflight.
432    pub(crate) fn charge_mutation_input_total(&self, input_bytes: u64) -> Result<()> {
433        self.charge_counter(
434            ResourceDimension::InputBytes,
435            self.limits.operation_input_bytes,
436            input_bytes,
437            ResourceStage::Validate,
438            |c| &mut c.input_bytes,
439        )
440    }
441
442    /// Charge exact staged formula bytes before allocating the output.
443    pub(crate) fn charge_mutation_output(&self, output_bytes: u64) -> Result<()> {
444        self.charge_counter(
445            ResourceDimension::OutputBytes,
446            self.limits.operation_output_bytes,
447            output_bytes,
448            ResourceStage::Serialize,
449            |c| &mut c.output_bytes,
450        )
451    }
452
453    /// Charge the number of cells targeted by one formula mutation.
454    pub(crate) fn charge_mutation_cells(&self, amount: u64) -> Result<()> {
455        self.charge_counter(
456            ResourceDimension::RangeCellCount,
457            self.limits.operation_range_cells,
458            amount,
459            ResourceStage::Validate,
460            |c| &mut c.range_cells,
461        )
462    }
463
464    pub(crate) fn check_output_bytes(&self, amount: u64) -> Result<()> {
465        let observed = self
466            .counters
467            .get()
468            .borrow()
469            .output_bytes
470            .saturating_add(amount);
471        self.check_local(
472            ResourceDimension::OutputBytes,
473            self.limits.operation_output_bytes,
474            observed,
475            ResourceStage::Calculate,
476        )
477    }
478
479    fn check_local(
480        &self,
481        dimension: ResourceDimension,
482        limit: u64,
483        observed: u64,
484        stage: ResourceStage,
485    ) -> Result<()> {
486        if observed > limit {
487            return Err(resource_error(
488                self.operation,
489                dimension,
490                limit,
491                observed,
492                stage,
493            ));
494        }
495        Ok(())
496    }
497
498    fn charge_counter(
499        &self,
500        dimension: ResourceDimension,
501        limit: u64,
502        amount: u64,
503        stage: ResourceStage,
504        select: impl FnOnce(&mut FormulaCounters) -> &mut u64,
505    ) -> Result<()> {
506        let mut counters = self.counters.get().borrow_mut();
507        let counter = select(&mut counters);
508        let observed = counter.checked_add(amount).unwrap_or(u64::MAX);
509        if observed > limit {
510            *counter = observed;
511            return Err(resource_error(
512                self.operation,
513                dimension,
514                limit,
515                observed,
516                stage,
517            ));
518        }
519        *counter = observed;
520        Ok(())
521    }
522}
523
524fn resource_error(
525    operation: ResourceOperation,
526    dimension: ResourceDimension,
527    limit: u64,
528    observed: u64,
529    stage: ResourceStage,
530) -> Error {
531    match ResourceLimitError::exceeded(
532        operation,
533        ResourceCategory::Formula,
534        dimension,
535        limit,
536        observed,
537        Some(stage),
538    ) {
539        Some(error) => Error::ResourceLimitExceeded(error),
540        None => Error::Internal("invalid formula resource-limit state".to_string()),
541    }
542}
543
544#[cfg(test)]
545mod tests {
546    use super::*;
547
548    #[test]
549    fn exact_limit_is_accepted_and_first_unit_over_is_stable() {
550        let limits = FormulaLimits {
551            operation_evaluation_steps: 2,
552            ..FormulaLimits::secure_default()
553        };
554        let budget = FormulaBudget::for_calculation(limits).unwrap();
555        budget.charge_evaluation_steps(1).unwrap();
556        budget.charge_evaluation_steps(1).unwrap();
557        let error = budget.charge_evaluation_steps(1).unwrap_err();
558        let metadata = error.resource_metadata().unwrap();
559        assert_eq!((metadata.limit(), metadata.observed()), (2, 3));
560        assert_eq!(metadata.operation_code(), "formula_calculate");
561        assert_eq!(metadata.dimension_code(), "operation_count");
562    }
563
564    #[test]
565    fn clones_share_counters_charged_before_and_after_cloning() {
566        let limits = FormulaLimits {
567            operation_evaluation_steps: 3,
568            ..FormulaLimits::secure_default()
569        };
570        let budget = FormulaBudget::for_calculation(limits).unwrap();
571        budget.charge_evaluation_steps(1).unwrap();
572        let clone = budget.clone();
573        clone.charge_evaluation_steps(1).unwrap();
574        let second = clone.clone();
575        budget.charge_evaluation_steps(1).unwrap();
576        let error = second.charge_evaluation_steps(1).unwrap_err();
577        let metadata = error.resource_metadata().unwrap();
578        assert_eq!((metadata.limit(), metadata.observed()), (3, 4));
579        let error = budget.charge_evaluation_steps(0).unwrap_err();
580        assert_eq!(error.resource_metadata().unwrap().observed(), 4);
581    }
582
583    #[test]
584    fn checked_counter_overflow_is_an_exceeded_limit() {
585        let limits = FormulaLimits {
586            operation_match_work: FormulaBudget::HARD_OPERATION_MATCH_WORK,
587            ..FormulaLimits::secure_default()
588        };
589        let budget = FormulaBudget::for_calculation(limits).unwrap();
590        let error = budget.charge_match_work(u64::MAX).unwrap_err();
591        assert_eq!(error.resource_metadata().unwrap().observed(), u64::MAX);
592    }
593
594    #[test]
595    fn output_preflight_does_not_consume_the_counter() {
596        let limits = FormulaLimits {
597            operation_output_bytes: 3,
598            ..FormulaLimits::secure_default()
599        };
600        let budget = FormulaBudget::for_calculation(limits).unwrap();
601        budget.check_output_bytes(3).unwrap();
602        budget.check_output_bytes(3).unwrap();
603        budget.charge_output_bytes(3).unwrap();
604        let error = budget.check_output_bytes(1).unwrap_err();
605        let metadata = error.resource_metadata().unwrap();
606        assert_eq!((metadata.limit(), metadata.observed()), (3, 4));
607    }
608
609    #[test]
610    fn trusted_limits_cannot_exceed_hard_ceiling() {
611        let limits = FormulaLimits {
612            operation_range_cells: FormulaBudget::HARD_OPERATION_RANGE_CELLS + 1,
613            ..FormulaLimits::secure_default()
614        };
615        let error = FormulaBudget::for_calculation(limits).unwrap_err();
616        let metadata = error.resource_metadata().unwrap();
617        assert_eq!(metadata.stage_code(), Some("validate"));
618        assert_eq!(metadata.dimension_code(), "range_cell_count");
619    }
620
621    #[test]
622    fn matcher_and_output_counters_are_independent() {
623        let limits = FormulaLimits {
624            operation_match_work: 2,
625            operation_output_bytes: 3,
626            ..FormulaLimits::secure_default()
627        };
628        let budget = FormulaBudget::for_calculation(limits).unwrap();
629        budget.charge_match_work(2).unwrap();
630        budget.charge_output_bytes(3).unwrap();
631        assert_eq!(
632            budget
633                .charge_match_work(1)
634                .unwrap_err()
635                .resource_metadata()
636                .unwrap()
637                .dimension_code(),
638            "match_work"
639        );
640        assert_eq!(
641            budget
642                .charge_output_bytes(1)
643                .unwrap_err()
644                .resource_metadata()
645                .unwrap()
646                .dimension_code(),
647            "output_bytes"
648        );
649    }
650}