1use 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#[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 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#[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#[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 pub fn for_parse(limits: FormulaLimits) -> Result<Self> {
134 Self::new(ResourceOperation::FormulaParse, limits)
135 }
136
137 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 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 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 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 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 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 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 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 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 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 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}