1mod scopes;
7use crate::{CellRef, traits::CalcValue};
8use formualizer_common::{
9 ExcelError, ExcelErrorExtra, ExcelErrorKind, LiteralValue, ResourceExhaustionDetail,
10 ResourceExhaustionReason,
11};
12use std::{
13 collections::HashSet,
14 sync::{Arc, Mutex},
15};
16
17#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
18pub enum UnavailableOperation {
19 FunctionPanicked {
21 name: String,
22 },
23 UnknownFunction {
24 name: String,
25 },
26 UnimplementedFunction {
27 name: String,
28 },
29 UnimplementedFunctionMode {
30 name: String,
31 mode: &'static str,
32 },
33 UnverifiedFunctionMode {
36 name: String,
37 mode: &'static str,
38 },
39 UnverifiedProvider {
40 name: String,
41 },
42 PostfixInvocation,
43}
44impl UnavailableOperation {
45 fn owned_text_bytes(&self) -> usize {
46 match self {
47 Self::FunctionPanicked { name }
48 | Self::UnknownFunction { name }
49 | Self::UnimplementedFunction { name }
50 | Self::UnimplementedFunctionMode { name, .. }
51 | Self::UnverifiedFunctionMode { name, .. }
52 | Self::UnverifiedProvider { name } => name.capacity(),
53 Self::PostfixInvocation => 0,
54 }
55 }
56}
57#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
58pub struct OperationRoot {
59 pub cell: Option<CellRef>,
60 pub named_vertex: Option<crate::engine::VertexId>,
62 pub operation: Arc<UnavailableOperation>,
64}
65
66#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
67pub enum OperationDiagnosticScope {
68 #[default]
69 RequestEvents,
70}
71#[derive(Clone, Debug, Default)]
72pub struct OperationDiagnostics {
73 pub scope: OperationDiagnosticScope,
74 pub logical_cell_reason_count: usize,
75 pub logical_root_cell_count: usize,
76 pub logical_named_reason_count: usize,
77 pub physical_unavailable_observations: Option<u64>,
79 pub physical_function_dispatches: Option<u64>,
80 pub roots: Vec<OperationRoot>,
81 pub samples: Vec<OperationRoot>,
82}
83#[derive(Clone, Copy, Debug)]
88pub struct OperationDiagnosticOptions {
89 pub sample_limit: usize,
90 pub physical_telemetry: bool,
91 pub track_unverified_providers: bool,
93 pub max_roots: Option<usize>,
94 pub max_operation_text_bytes: Option<usize>,
97}
98impl Default for OperationDiagnosticOptions {
99 fn default() -> Self {
100 Self {
101 sample_limit: 16,
102 physical_telemetry: false,
103 track_unverified_providers: false,
104 max_roots: None,
105 max_operation_text_bytes: None,
106 }
107 }
108}
109#[derive(Clone)]
112struct OperationIdentity(Arc<UnavailableOperation>);
113impl PartialEq for OperationIdentity {
114 fn eq(&self, other: &Self) -> bool {
115 match (self.0.as_ref(), other.0.as_ref()) {
116 (
117 UnavailableOperation::UnknownFunction { name: left },
118 UnavailableOperation::UnknownFunction { name: right },
119 ) => left.eq_ignore_ascii_case(right),
120 (left, right) => left == right,
121 }
122 }
123}
124impl Eq for OperationIdentity {}
125impl std::hash::Hash for OperationIdentity {
126 fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
127 match self.0.as_ref() {
128 UnavailableOperation::UnknownFunction { name } => {
129 0u8.hash(state);
130 name.len().hash(state);
131 for byte in name.bytes() {
132 byte.to_ascii_uppercase().hash(state);
133 }
134 }
135 operation => {
136 1u8.hash(state);
137 operation.hash(state);
138 }
139 }
140 }
141}
142#[derive(Default)]
143struct State {
144 roots: HashSet<OperationRoot>,
145 operations: HashSet<OperationIdentity>,
146 operation_text_bytes: usize,
147 physical: u64,
148 exhaustion: Option<ResourceExhaustionDetail>,
149 finalized: bool,
150}
151pub struct OperationDiagnosticCollector {
152 options: OperationDiagnosticOptions,
153 state: Mutex<State>,
154 dispatches: std::sync::atomic::AtomicU64,
155}
156#[derive(Clone, Copy, PartialEq, Eq)]
157pub(crate) enum Mode {
158 Inherit,
159 Speculative,
160 Suppressed,
161}
162pub(crate) struct Scope<'a> {
163 _collector: &'a OperationDiagnosticCollector,
164 guard: scopes::Guard,
165}
166impl Scope<'_> {
167 pub(crate) fn encountered(&self) -> bool {
168 self.guard.encountered()
169 }
170 pub(crate) fn tainted(&self) -> bool {
171 self.guard.tainted()
172 }
173}
174fn resource_error(detail: ResourceExhaustionDetail) -> ExcelError {
175 crate::engine::ResourceLedgerError::Exhausted(detail).into_excel_error()
176}
177fn state_error() -> ExcelError {
178 ExcelError::new(ExcelErrorKind::Calc)
179 .with_message("operation evidence has already been finalized")
180}
181fn allocation_detail(observed: usize) -> ResourceExhaustionDetail {
182 ResourceExhaustionDetail {
183 reason: ResourceExhaustionReason::ScratchMemory,
184 limit: u64::MAX,
185 observed: observed as u64,
186 request_id: None,
187 }
188}
189impl OperationDiagnosticCollector {
190 pub fn new(sample_limit: usize) -> Self {
192 Self::with_options(OperationDiagnosticOptions {
193 sample_limit,
194 physical_telemetry: true,
195 ..Default::default()
196 })
197 }
198 pub fn with_options(options: OperationDiagnosticOptions) -> Self {
199 Self {
200 options,
201 state: Mutex::new(State::default()),
202 dispatches: std::sync::atomic::AtomicU64::new(0),
203 }
204 }
205 fn key(&self) -> usize {
206 self as *const Self as usize
207 }
208 pub(crate) fn scope(&self, mode: Mode) -> Scope<'_> {
209 Scope {
210 _collector: self,
211 guard: scopes::enter(self.key(), mode, scopes::Origin::default()),
212 }
213 }
214 pub(crate) fn named_scope(&self, vertex: crate::engine::VertexId) -> Scope<'_> {
215 Scope {
216 _collector: self,
217 guard: scopes::enter(
218 self.key(),
219 Mode::Inherit,
220 scopes::Origin {
221 named_vertex: Some(vertex),
222 reference_cell: None,
223 },
224 ),
225 }
226 }
227 pub(crate) fn reference_scope(&self, cell: Option<CellRef>) -> Scope<'_> {
228 Scope {
229 _collector: self,
230 guard: scopes::enter(
231 self.key(),
232 Mode::Inherit,
233 scopes::Origin {
234 named_vertex: None,
235 reference_cell: cell,
236 },
237 ),
238 }
239 }
240 pub(crate) fn reset(&self) {
241 *self.state.lock().unwrap() = State::default();
242 self.dispatches
243 .store(0, std::sync::atomic::Ordering::Relaxed);
244 }
245 pub(crate) fn tracks_unverified_providers(&self) -> bool {
246 self.options.track_unverified_providers
247 }
248 pub(crate) fn dispatch_started(&self) {
249 if !self.options.physical_telemetry {
250 return;
251 }
252 if scopes::current(self.key()).0 != Mode::Suppressed {
253 self.dispatches
254 .fetch_add(1, std::sync::atomic::Ordering::Relaxed);
255 }
256 }
257 pub fn record(&self, cell: Option<CellRef>, operation: UnavailableOperation) {
260 let Some((mode, origin)) = scopes::event(self.key()) else {
261 return;
262 };
263 let mut state = self.state.lock().unwrap();
264 if self.options.physical_telemetry {
265 state.physical = state.physical.saturating_add(1);
266 }
267 if mode == Mode::Speculative || state.exhaustion.is_some() || state.finalized {
268 return;
269 }
270 let named_vertex = origin.named_vertex;
271 let cell = if named_vertex.is_some() {
272 None
273 } else {
274 cell.or(origin.reference_cell).map(|cell| {
275 CellRef::new_absolute(cell.sheet_id, cell.coord.row(), cell.coord.col())
276 })
277 };
278 let identity = OperationIdentity(Arc::new(operation));
279 let operation = identity.0.as_ref();
280 let existing = state
281 .operations
282 .get(&identity)
283 .map(|key| Arc::clone(&key.0));
284 if let Some(operation) = &existing {
285 let root = OperationRoot {
286 cell,
287 named_vertex,
288 operation: Arc::clone(operation),
289 };
290 if state.roots.contains(&root) {
291 return;
292 }
293 }
294 if let Some(limit) = self.options.max_roots
295 && state.roots.len() >= limit
296 {
297 state.exhaustion = Some(ResourceExhaustionDetail {
298 reason: ResourceExhaustionReason::OperationEvidenceRoots,
299 limit: limit as u64,
300 observed: state.roots.len().saturating_add(1) as u64,
301 request_id: None,
302 });
303 return;
304 }
305 let added_text = if existing.is_some() {
306 0
307 } else {
308 operation.owned_text_bytes()
309 };
310 let Some(next_text) = state.operation_text_bytes.checked_add(added_text) else {
311 state.exhaustion = Some(ResourceExhaustionDetail {
312 reason: ResourceExhaustionReason::ArithmeticOverflow,
313 limit: usize::MAX as u64,
314 observed: u64::MAX,
315 request_id: None,
316 });
317 return;
318 };
319 if let Some(limit) = self.options.max_operation_text_bytes
320 && next_text > limit
321 {
322 state.exhaustion = Some(ResourceExhaustionDetail {
323 reason: ResourceExhaustionReason::OperationEvidenceTextBytes,
324 limit: limit as u64,
325 observed: next_text as u64,
326 request_id: None,
327 });
328 return;
329 }
330 if state.roots.try_reserve(1).is_err()
331 || (existing.is_none() && state.operations.try_reserve(1).is_err())
332 {
333 state.exhaustion = Some(allocation_detail(state.roots.len().saturating_add(1)));
334 return;
335 }
336 let operation = existing.unwrap_or_else(|| {
337 let operation = Arc::clone(&identity.0);
338 state.operations.insert(identity);
339 state.operation_text_bytes = next_text;
340 operation
341 });
342 state.roots.insert(OperationRoot {
343 cell,
344 named_vertex,
345 operation,
346 });
347 }
348 pub(crate) fn input(&self, value: &Result<CalcValue<'_>, ExcelError>) {
349 match value {
350 Ok(value) => self.input_value(value),
351 Err(error) => self.input_error(error),
352 }
353 }
354 pub(crate) fn input_value(&self, value: &CalcValue<'_>) {
355 let tainted = match value {
356 CalcValue::Scalar(value) | CalcValue::AnnotatedScalar(value, _) => {
357 literal_has_nimpl(value)
358 }
359 CalcValue::Range(_) => true,
360 _ => false,
361 };
362 if tainted {
363 self.ambiguous_input();
364 }
365 }
366 pub(crate) fn input_error(&self, error: &ExcelError) {
367 if error.kind == ExcelErrorKind::NImpl {
368 self.ambiguous_input();
369 }
370 }
371 pub(crate) fn ambiguous_input(&self) {
372 scopes::taint(self.key());
373 }
374 fn validate_state(state: &State) -> Result<(), ExcelError> {
375 if let Some(detail) = &state.exhaustion {
376 return Err(resource_error(detail.clone()));
377 }
378 if state.finalized {
379 return Err(state_error());
380 }
381 Ok(())
382 }
383 fn report(
384 &self,
385 roots: impl Iterator<Item = OperationRoot>,
386 count: usize,
387 physical: u64,
388 ) -> Result<OperationDiagnostics, ExcelError> {
389 let mut roots_vec = Vec::new();
390 roots_vec
391 .try_reserve_exact(count)
392 .map_err(|_| resource_error(allocation_detail(count)))?;
393 roots_vec.extend(roots);
394 roots_vec.sort_unstable();
395 let mut previous = None;
396 let mut cells = 0;
397 let mut cell_reasons = 0;
398 let mut named_reasons = 0;
399 for root in &roots_vec {
400 if let Some(cell) = root.cell {
401 cell_reasons += 1;
402 if previous != Some(cell) {
403 cells += 1;
404 previous = Some(cell);
405 }
406 }
407 if root.named_vertex.is_some() {
408 named_reasons += 1;
409 }
410 }
411 let sample_count = self.options.sample_limit.min(roots_vec.len());
412 let mut samples = Vec::new();
413 samples
414 .try_reserve_exact(sample_count)
415 .map_err(|_| resource_error(allocation_detail(sample_count)))?;
416 samples.extend(roots_vec.iter().take(sample_count).cloned());
417 Ok(OperationDiagnostics {
418 scope: OperationDiagnosticScope::RequestEvents,
419 logical_cell_reason_count: cell_reasons,
420 logical_root_cell_count: cells,
421 logical_named_reason_count: named_reasons,
422 physical_unavailable_observations: self.options.physical_telemetry.then_some(physical),
423 physical_function_dispatches: self
424 .options
425 .physical_telemetry
426 .then(|| self.dispatches.load(std::sync::atomic::Ordering::Relaxed)),
427 roots: roots_vec,
428 samples,
429 })
430 }
431 pub fn snapshot(&self) -> Result<OperationDiagnostics, ExcelError> {
432 let mut state = self.state.lock().unwrap();
433 Self::validate_state(&state)?;
434 let report = self.report(
435 state.roots.iter().cloned(),
436 state.roots.len(),
437 state.physical,
438 );
439 if let Err(error) = &report
440 && let ExcelErrorExtra::Resource { detail } = error.extra()
441 {
442 state.exhaustion = Some(detail.as_ref().clone());
443 }
444 report
445 }
446 pub fn take_snapshot(&mut self) -> Result<OperationDiagnostics, ExcelError> {
449 self.take_shared_snapshot()
450 }
451 pub(crate) fn take_shared_snapshot(&self) -> Result<OperationDiagnostics, ExcelError> {
452 let mut state = self.state.lock().unwrap();
453 Self::validate_state(&state)?;
454 let roots = std::mem::take(&mut state.roots);
455 let report = self.report(roots.iter().cloned(), roots.len(), state.physical);
456 if report.is_ok() {
457 state.operations = HashSet::new();
458 state.operation_text_bytes = 0;
459 state.finalized = true;
460 } else {
461 state.roots = roots;
463 if let Err(error) = &report
464 && let ExcelErrorExtra::Resource { detail } = error.extra()
465 {
466 state.exhaustion = Some(detail.as_ref().clone());
467 }
468 }
469 report
470 }
471}
472fn literal_has_nimpl(value: &LiteralValue) -> bool {
473 match value {
474 LiteralValue::Error(error) => error.kind == ExcelErrorKind::NImpl,
475 LiteralValue::Array(_) => true,
476 _ => false,
477 }
478}
479pub(crate) fn is_unimplemented(value: &Result<CalcValue<'_>, ExcelError>) -> bool {
480 let error = match value {
481 Err(error) => Some(error),
482 Ok(
483 CalcValue::Scalar(LiteralValue::Error(error))
484 | CalcValue::AnnotatedScalar(LiteralValue::Error(error), _),
485 ) => Some(error),
486 _ => None,
487 };
488 error.is_some_and(|error| {
489 error.kind == ExcelErrorKind::NImpl && matches!(error.extra(), ExcelErrorExtra::None)
490 })
491}
492
493pub(crate) fn is_unimplemented_reference(
494 result: &Option<Result<formualizer_parse::parser::ReferenceType, ExcelError>>,
495) -> bool {
496 result.as_ref().is_some_and(|result| {
497 result.as_ref().is_err_and(|error| {
498 error.kind == ExcelErrorKind::NImpl && matches!(error.extra(), ExcelErrorExtra::None)
499 })
500 })
501}
502
503pub(crate) fn is_unimplemented_resolution(
504 result: &Result<crate::function::FunctionResolution<'_>, ExcelError>,
505) -> bool {
506 use crate::function::FunctionResolution;
507 let error = match result {
508 Err(error) | Ok(FunctionResolution::ReferenceError(error)) => Some(error),
509 Ok(FunctionResolution::Value(
510 CalcValue::Scalar(LiteralValue::Error(error))
511 | CalcValue::AnnotatedScalar(LiteralValue::Error(error), _),
512 )) => Some(error),
513 _ => None,
514 };
515 error.is_some_and(|error| {
516 error.kind == ExcelErrorKind::NImpl && matches!(error.extra(), ExcelErrorExtra::None)
517 })
518}
519
520#[cfg(test)]
521mod tests {
522 use super::*;
523 use crate::reference::Coord;
524 fn cell(row: u32) -> CellRef {
525 CellRef::new(0, Coord::new(row, 0, true, true))
526 }
527 fn gap(name: &str) -> UnavailableOperation {
528 UnavailableOperation::UnknownFunction { name: name.into() }
529 }
530 fn failure_reason(error: &ExcelError) -> ResourceExhaustionReason {
531 match error.extra() {
532 ExcelErrorExtra::Resource { detail } => detail.reason,
533 _ => panic!("expected typed resource failure: {error:?}"),
534 }
535 }
536
537 #[test]
538 fn collector_cell_anchoring_flags_do_not_duplicate_logical_identity() {
539 let collector = OperationDiagnosticCollector::with_options(OperationDiagnosticOptions {
540 max_roots: Some(1),
541 ..Default::default()
542 });
543 collector.record(Some(cell(0)), gap("GAP"));
544 collector.record(
545 Some(CellRef::new(0, Coord::new(0, 0, false, false))),
546 gap("GAP"),
547 );
548 let report = collector.snapshot().unwrap();
549 assert_eq!(report.logical_root_cell_count, 1);
550 assert_eq!(report.logical_cell_reason_count, 1);
551 assert_eq!(report.roots.len(), 1);
552 assert_eq!(
553 report.roots[0].cell.unwrap().coord,
554 Coord::new(0, 0, true, true)
555 );
556 }
557
558 #[test]
559 fn collector_interns_operation_identity_across_exact_roots_and_samples() {
560 let collector = OperationDiagnosticCollector::with_options(OperationDiagnosticOptions {
561 sample_limit: 1,
562 max_roots: Some(2),
563 max_operation_text_bytes: Some(8),
564 ..Default::default()
565 });
566 collector.record(Some(cell(0)), gap("_xll.Gap"));
567 collector.record(Some(cell(0)), gap("_XLL.GAP"));
568 collector.record(Some(cell(1)), gap("_XLL.gap"));
569 let report = collector.snapshot().unwrap();
570 assert_eq!(report.roots[0].operation.as_ref(), &gap("_xll.Gap"));
571 assert_eq!(report.roots.len(), 2);
572 assert_eq!(report.logical_root_cell_count, 2);
573 assert_eq!(report.samples.len(), 1);
574 assert!(Arc::ptr_eq(
575 &report.roots[0].operation,
576 &report.roots[1].operation
577 ));
578 assert!(Arc::ptr_eq(
579 &report.roots[0].operation,
580 &report.samples[0].operation
581 ));
582 assert_eq!(report.physical_function_dispatches, None);
583 assert_eq!(report.physical_unavailable_observations, None);
584 }
585
586 #[test]
587 fn duplicate_root_at_limit_does_not_exhaust_exact_evidence() {
588 let collector = OperationDiagnosticCollector::with_options(OperationDiagnosticOptions {
589 sample_limit: 0,
590 max_roots: Some(1),
591 ..Default::default()
592 });
593 collector.record(Some(cell(0)), gap("GAP"));
594 collector.record(Some(cell(0)), gap("GAP"));
595 let report = collector.snapshot().unwrap();
596 assert_eq!(report.roots.len(), 1);
597 assert!(report.samples.is_empty());
598 assert_eq!(report.logical_cell_reason_count, 1);
599 }
600
601 #[test]
602 fn root_limit_failure_is_typed_and_sticky_until_next_request() {
603 let mut collector =
604 OperationDiagnosticCollector::with_options(OperationDiagnosticOptions {
605 sample_limit: 0,
606 max_roots: Some(1),
607 ..Default::default()
608 });
609 collector.record(Some(cell(0)), gap("GAP"));
610 collector.record(Some(cell(1)), gap("GAP"));
611 for error in [
612 collector.snapshot().unwrap_err(),
613 collector.take_snapshot().unwrap_err(),
614 ] {
615 assert_eq!(
616 failure_reason(&error),
617 ResourceExhaustionReason::OperationEvidenceRoots
618 );
619 }
620 collector.reset();
621 assert!(collector.snapshot().unwrap().roots.is_empty());
622 }
623
624 #[test]
625 fn operation_text_budget_counts_owned_capacity_only_once() {
626 let mut collector =
627 OperationDiagnosticCollector::with_options(OperationDiagnosticOptions {
628 max_operation_text_bytes: Some(3),
629 ..Default::default()
630 });
631 collector.record(Some(cell(0)), gap("GAP"));
632 collector.record(Some(cell(1)), gap("GAP"));
633 assert_eq!(collector.snapshot().unwrap().roots.len(), 2);
634 collector.record(Some(cell(2)), gap("NEXT"));
635 assert_eq!(
636 failure_reason(&collector.take_snapshot().unwrap_err()),
637 ResourceExhaustionReason::OperationEvidenceTextBytes,
638 );
639 }
640
641 #[test]
642 fn owned_capacity_not_just_string_length_is_bounded() {
643 let collector = OperationDiagnosticCollector::with_options(OperationDiagnosticOptions {
644 max_operation_text_bytes: Some(3),
645 ..Default::default()
646 });
647 let mut name = String::with_capacity(100);
648 name.push_str("GAP");
649 collector.record(None, UnavailableOperation::UnknownFunction { name });
650 assert_eq!(
651 failure_reason(&collector.snapshot().unwrap_err()),
652 ResourceExhaustionReason::OperationEvidenceTextBytes,
653 );
654 }
655
656 #[test]
657 fn speculative_and_suppressed_work_do_not_consume_sparse_root_budget() {
658 let collector = OperationDiagnosticCollector::with_options(OperationDiagnosticOptions {
659 physical_telemetry: true,
660 max_roots: Some(0),
661 max_operation_text_bytes: Some(0),
662 ..Default::default()
663 });
664 {
665 let _speculation = collector.scope(Mode::Speculative);
666 collector.dispatch_started();
667 collector.record(Some(cell(0)), gap("GAP"));
668 }
669 {
670 let _oracle = collector.scope(Mode::Suppressed);
671 let _nested = collector.scope(Mode::Speculative);
672 collector.dispatch_started();
673 collector.record(Some(cell(1)), gap("IGNORED"));
674 }
675 let report = collector.snapshot().unwrap();
676 assert!(report.roots.is_empty());
677 assert_eq!(report.physical_function_dispatches, Some(1));
678 assert_eq!(report.physical_unavailable_observations, Some(1));
679 }
680
681 #[test]
682 fn finalization_consumes_once_and_reset_preserves_configuration() {
683 let mut collector =
684 OperationDiagnosticCollector::with_options(OperationDiagnosticOptions {
685 sample_limit: 0,
686 physical_telemetry: true,
687 ..Default::default()
688 });
689 collector.record(Some(cell(0)), gap("GAP"));
690 let report = collector.take_snapshot().unwrap();
691 assert_eq!(report.roots.len(), 1);
692 assert!(collector.snapshot().is_err());
693 assert!(collector.take_snapshot().is_err());
694 collector.reset();
695 let next = collector.take_snapshot().unwrap();
696 assert!(next.roots.is_empty());
697 assert_eq!(next.physical_function_dispatches, Some(0));
698 assert_eq!(next.physical_unavailable_observations, Some(0));
699 }
700}