1use alloc::boxed::Box;
2use alloc::sync::Arc;
3use alloc::vec::Vec;
4
5use neco_algnum::AlgnumError;
6use neco_bigint::{BigintError, Sign};
7
8use crate::error::{
9 map_eval_failure, map_resolve_failure, map_storage_failure, PrecisionFailurePayload,
10 ProvenanceMismatchField, ProvenanceMismatchPayload, ProvenanceRecord,
11};
12use crate::evaluate::{evaluate_reachable, EvaluationRunError};
13use crate::float::{FloatError, PrecisionResolutionError};
14use crate::index::{GrowingIndex, SortedIndex};
15use crate::storage::{reserve_entries, StorageResource};
16use crate::value::{decide_equality, decide_sign, decide_zero};
17use crate::{
18 AbsoluteBits, AtomStore, CertifiedF64, ConsumerId, EvaluationCache, ExactValue, ExprGraph,
19 ExprId, FailureLocation, FailureOperation, IsolationCache, NecoFailure, OwnerId, ResolveError,
20 UnsupportedFailurePayload,
21};
22
23pub const PUBLIC_API_IDENTITY: &str = "neco-expr-exact-computation-v1";
24#[derive(Clone, Debug)]
25pub struct ComputationProductId {
26 token: Arc<()>,
27}
28
29impl ComputationProductId {
30 fn new() -> Self {
31 Self {
32 token: Arc::new(()),
33 }
34 }
35}
36
37impl PartialEq for ComputationProductId {
38 fn eq(&self, other: &Self) -> bool {
39 Arc::ptr_eq(&self.token, &other.token)
40 }
41}
42
43impl Eq for ComputationProductId {}
44
45impl core::hash::Hash for ComputationProductId {
46 fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
47 (Arc::as_ptr(&self.token) as usize).hash(state);
48 }
49}
50
51#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
52pub enum ExactDecisionKind {
53 Zero,
54 Equality,
55 Sign,
56 Degeneracy,
57}
58
59#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
60pub enum ExactDecisionValue {
61 Zero,
62 NonZero,
63 Equal,
64 NotEqual,
65 Negative,
66 Positive,
67 Degenerate,
68 NonDegenerate,
69}
70
71#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
72pub enum ExactDecisionRequest {
73 Zero(ExprId),
74 Equality(ExprId, ExprId),
75 Sign(ExprId),
76 Degeneracy(ExprId),
77}
78
79impl ExactDecisionRequest {
80 pub const fn kind(self) -> ExactDecisionKind {
81 match self {
82 Self::Zero(_) => ExactDecisionKind::Zero,
83 Self::Equality(_, _) => ExactDecisionKind::Equality,
84 Self::Sign(_) => ExactDecisionKind::Sign,
85 Self::Degeneracy(_) => ExactDecisionKind::Degeneracy,
86 }
87 }
88}
89
90#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
91pub enum ExactOperation {
92 NormalizeMonomial,
93 NormalizeFormSum,
94 NormalizeAlgebraic,
95 DecideZero,
96 DecideEquality,
97 DecideSign,
98 DecideDegeneracy,
99 ResolveCertifiedF64,
100}
101
102#[derive(Debug, Eq, PartialEq)]
103pub struct ExactExpressionRequirement {
104 consumer_id: ConsumerId,
105 expressions: Vec<ExprId>,
106 decision: ExactDecisionRequest,
107 precision: AbsoluteBits,
108}
109
110impl ExactExpressionRequirement {
111 pub fn new(
112 consumer_id: ConsumerId,
113 expressions: &[ExprId],
114 decision: ExactDecisionRequest,
115 precision: AbsoluteBits,
116 ) -> Result<Self, NecoFailure> {
117 let location =
118 FailureLocation::operation(FailureOperation::Allocate).with_consumer(consumer_id);
119 if expressions.is_empty() {
120 return Err(NecoFailure::MissingAssignment { location });
121 }
122 let (decision_operands, decision_operand_count) = decision_operands(decision);
123 if !decision_operands[..decision_operand_count]
124 .iter()
125 .all(|operand| expressions.contains(operand))
126 {
127 return Err(NecoFailure::MissingAssignment { location });
128 }
129 let mut owned = Vec::new();
130 reserve_entries(
131 &mut owned,
132 expressions.len(),
133 StorageResource::ProductEntries,
134 )
135 .map_err(|error| map_storage_failure(location, error))?;
136 owned.extend_from_slice(expressions);
137 owned.sort_unstable();
138 if owned.windows(2).any(|pair| pair[0] == pair[1]) {
139 let positions =
140 SortedIndex::build(expressions.iter().copied(), StorageResource::ProductEntries)
141 .map_err(|error| map_storage_failure(location, error))?;
142 let duplicate = positions
143 .second_occurrences()
144 .min()
145 .map_or(expressions[0], |position| expressions[position]);
146 return Err(NecoFailure::StorageFailure {
147 location: location.with_expr(duplicate),
148 payload: Box::new(crate::StorageFailurePayload::DuplicateId {
149 resource: StorageResource::ProductEntries,
150 id: duplicate.get(),
151 }),
152 });
153 }
154 Ok(Self {
155 consumer_id,
156 expressions: owned,
157 decision,
158 precision,
159 })
160 }
161
162 pub const fn consumer_id(&self) -> ConsumerId {
163 self.consumer_id
164 }
165
166 pub fn expressions(&self) -> &[ExprId] {
167 &self.expressions
168 }
169
170 pub const fn decision(&self) -> ExactDecisionRequest {
171 self.decision
172 }
173
174 pub const fn precision(&self) -> AbsoluteBits {
175 self.precision
176 }
177}
178
179#[derive(Debug, Eq, PartialEq)]
180pub struct NecoObservedCapability {
181 source_identity: &'static str,
182 supported_operations: Vec<ExactOperation>,
183}
184
185impl NecoObservedCapability {
186 pub fn current(supported_operations: &[ExactOperation]) -> Result<Self, NecoFailure> {
187 Self::new(env!("CARGO_PKG_VERSION"), supported_operations)
188 }
189
190 pub fn new(
191 source_identity: &'static str,
192 supported_operations: &[ExactOperation],
193 ) -> Result<Self, NecoFailure> {
194 let location = FailureLocation::operation(FailureOperation::Read);
195 let mut supported = Vec::new();
196 reserve_entries(
197 &mut supported,
198 supported_operations.len(),
199 StorageResource::ProductEntries,
200 )
201 .map_err(|error| map_storage_failure(location, error))?;
202 supported.extend_from_slice(supported_operations);
203 supported.sort_unstable();
204 supported.dedup();
205 Ok(Self {
206 source_identity,
207 supported_operations: supported,
208 })
209 }
210
211 pub const fn source_identity(&self) -> &'static str {
212 self.source_identity
213 }
214
215 pub fn supported_operations(&self) -> &[ExactOperation] {
216 &self.supported_operations
217 }
218}
219
220#[derive(Clone, Copy, Debug, Eq, PartialEq)]
221pub struct NecoImplementationSource {
222 revision_identity: &'static str,
223 public_api_identity: &'static str,
224}
225
226impl NecoImplementationSource {
227 pub const fn new(revision_identity: &'static str, public_api_identity: &'static str) -> Self {
228 Self {
229 revision_identity,
230 public_api_identity,
231 }
232 }
233
234 pub const fn current() -> Self {
235 Self::new(env!("CARGO_PKG_VERSION"), PUBLIC_API_IDENTITY)
236 }
237
238 pub const fn revision_identity(&self) -> &'static str {
239 self.revision_identity
240 }
241
242 pub const fn public_api_identity(&self) -> &'static str {
243 self.public_api_identity
244 }
245}
246
247#[derive(Debug, Eq, PartialEq)]
248pub struct OwnerExpressionSet {
249 owner: OwnerId,
250 graph: ExprGraph,
251 atoms: AtomStore,
252 requirements: Vec<ExactExpressionRequirement>,
253}
254
255impl OwnerExpressionSet {
256 pub fn new(
257 owner: OwnerId,
258 graph: ExprGraph,
259 atoms: AtomStore,
260 requirements: Vec<ExactExpressionRequirement>,
261 ) -> Result<Self, NecoFailure> {
262 for requirement in &requirements {
263 for expression in requirement.expressions() {
264 if graph.get(*expression).is_none() {
265 return Err(NecoFailure::UnknownExpression {
266 location: FailureLocation::operation(FailureOperation::Read)
267 .with_consumer(requirement.consumer_id())
268 .with_expr(*expression),
269 });
270 }
271 }
272 }
273 Ok(Self {
274 owner,
275 graph,
276 atoms,
277 requirements,
278 })
279 }
280
281 pub const fn owner(&self) -> OwnerId {
282 self.owner
283 }
284 pub fn graph(&self) -> &ExprGraph {
285 &self.graph
286 }
287 pub fn atoms(&self) -> &AtomStore {
288 &self.atoms
289 }
290 pub fn requirements(&self) -> &[ExactExpressionRequirement] {
291 &self.requirements
292 }
293}
294
295#[derive(Debug, Eq, PartialEq)]
296pub struct ExactAllocationInput {
297 owners: Vec<OwnerExpressionSet>,
298 observed_capability: NecoObservedCapability,
299 implementation_source: NecoImplementationSource,
300}
301
302impl ExactAllocationInput {
303 pub const fn new(
304 owners: Vec<OwnerExpressionSet>,
305 observed_capability: NecoObservedCapability,
306 implementation_source: NecoImplementationSource,
307 ) -> Self {
308 Self {
309 owners,
310 observed_capability,
311 implementation_source,
312 }
313 }
314
315 pub fn owners(&self) -> &[OwnerExpressionSet] {
316 &self.owners
317 }
318 pub fn observed_capability(&self) -> &NecoObservedCapability {
319 &self.observed_capability
320 }
321 pub fn implementation_source(&self) -> &NecoImplementationSource {
322 &self.implementation_source
323 }
324}
325
326#[derive(Debug, Eq, PartialEq)]
327pub struct ExactNumericAllocation {
328 descent_consumers: Vec<(OwnerId, ConsumerId)>,
329}
330
331impl ExactNumericAllocation {
332 pub fn descent_consumers(&self) -> &[(OwnerId, ConsumerId)] {
333 &self.descent_consumers
334 }
335}
336
337#[derive(Debug, Eq, PartialEq)]
338pub struct AllocatedExactNumericContext {
339 input: ExactAllocationInput,
340 allocation: ExactNumericAllocation,
341}
342
343impl AllocatedExactNumericContext {
344 pub fn allocation(&self) -> &ExactNumericAllocation {
345 &self.allocation
346 }
347}
348
349#[derive(Debug, Eq, PartialEq)]
350struct NormalFormEntry {
351 owner: OwnerId,
352 consumer: ConsumerId,
353 expr: ExprId,
354 value_position: usize,
355}
356
357#[derive(Debug, Eq, PartialEq)]
358pub struct NormalizedExactNumericContext {
359 allocated: AllocatedExactNumericContext,
360 normal_values: Vec<Arc<ExactValue>>,
361 normal_forms: Vec<NormalFormEntry>,
362 normal_form_index: SortedIndex<(OwnerId, ConsumerId, ExprId)>,
363 evaluation_count: usize,
364}
365
366impl NormalizedExactNumericContext {
367 pub fn normal_form(
368 &self,
369 owner: OwnerId,
370 consumer: ConsumerId,
371 expr: ExprId,
372 ) -> Option<&ExactValue> {
373 self.normal_form_shared(owner, consumer, expr)
374 .map(|value| &**value)
375 }
376
377 fn normal_form_shared(
378 &self,
379 owner: OwnerId,
380 consumer: ConsumerId,
381 expr: ExprId,
382 ) -> Option<&Arc<ExactValue>> {
383 self.normal_form_index
384 .first(&(owner, consumer, expr))
385 .map(|position| &self.normal_values[self.normal_forms[position].value_position])
386 }
387
388 pub const fn evaluation_count(&self) -> usize {
389 self.evaluation_count
390 }
391}
392
393#[derive(Debug, Eq, PartialEq)]
394pub struct ExactDecisionWitness {
395 kind: ExactDecisionKind,
396 operands: Vec<ExprId>,
397 value: ExactDecisionValue,
398 normal_form_witness: Arc<ExactValue>,
399}
400
401impl ExactDecisionWitness {
402 pub const fn kind(&self) -> ExactDecisionKind {
403 self.kind
404 }
405
406 pub fn operands(&self) -> &[ExprId] {
407 &self.operands
408 }
409
410 pub const fn value(&self) -> ExactDecisionValue {
411 self.value
412 }
413
414 pub fn normal_form_witness(&self) -> &ExactValue {
415 &self.normal_form_witness
416 }
417}
418
419#[derive(Debug, Eq, PartialEq)]
420struct DecisionEntry {
421 owner: OwnerId,
422 consumer: ConsumerId,
423 witness: ExactDecisionWitness,
424}
425
426#[derive(Debug, Eq, PartialEq)]
427pub struct DecidedExactNumericContext {
428 normalized: NormalizedExactNumericContext,
429 decisions: Vec<DecisionEntry>,
430 decision_index: SortedIndex<(OwnerId, ConsumerId)>,
431}
432
433impl DecidedExactNumericContext {
434 pub fn decision(&self, owner: OwnerId, consumer: ConsumerId) -> Option<&ExactDecisionWitness> {
435 self.decision_index
436 .first(&(owner, consumer))
437 .map(|position| &self.decisions[position].witness)
438 }
439}
440
441#[derive(Debug, Eq, PartialEq)]
442pub struct CertifiedF64Expression {
443 owner: OwnerId,
444 consumer_id: ConsumerId,
445 expr: ExprId,
446 precision: AbsoluteBits,
447 source: NecoImplementationSource,
448 certified: Arc<CertifiedF64>,
449}
450
451impl CertifiedF64Expression {
452 pub const fn owner(&self) -> OwnerId {
453 self.owner
454 }
455
456 pub const fn consumer_id(&self) -> ConsumerId {
457 self.consumer_id
458 }
459
460 pub const fn expr(&self) -> ExprId {
461 self.expr
462 }
463
464 pub const fn precision(&self) -> AbsoluteBits {
465 self.precision
466 }
467
468 pub const fn source(&self) -> NecoImplementationSource {
469 self.source
470 }
471
472 pub fn certified(&self) -> &CertifiedF64 {
473 &self.certified
474 }
475 fn try_clone(&self) -> Result<Self, NecoFailure> {
476 Ok(Self {
477 owner: self.owner,
478 consumer_id: self.consumer_id,
479 expr: self.expr,
480 precision: self.precision,
481 source: self.source,
482 certified: Arc::clone(&self.certified),
483 })
484 }
485}
486
487#[derive(Debug, Eq, PartialEq)]
488pub struct CertifiedF64Bundle {
489 owner: OwnerId,
490 consumer_id: ConsumerId,
491 precision: AbsoluteBits,
492 source: NecoImplementationSource,
493 product_identity: ComputationProductId,
494 values: Vec<CertifiedF64Expression>,
495 value_index: SortedIndex<ExprId>,
496}
497
498#[derive(Default)]
499struct ResolutionCache {
500 entries: Vec<Arc<CertifiedF64>>,
501 index: GrowingIndex<(ExprId, AbsoluteBits)>,
502}
503
504fn bundle_value_index(
505 values: &[CertifiedF64Expression],
506 location: FailureLocation,
507) -> Result<SortedIndex<ExprId>, NecoFailure> {
508 SortedIndex::build(
509 values.iter().map(|value| value.expr),
510 StorageResource::ProductResolutionEntries,
511 )
512 .map_err(|error| map_storage_failure(location, error))
513}
514
515impl CertifiedF64Bundle {
516 pub const fn owner(&self) -> OwnerId {
517 self.owner
518 }
519
520 pub const fn consumer_id(&self) -> ConsumerId {
521 self.consumer_id
522 }
523
524 pub const fn precision(&self) -> AbsoluteBits {
525 self.precision
526 }
527
528 pub const fn source(&self) -> NecoImplementationSource {
529 self.source
530 }
531
532 pub fn values(&self) -> &[CertifiedF64Expression] {
533 &self.values
534 }
535 pub fn product_identity(&self) -> &ComputationProductId {
536 &self.product_identity
537 }
538
539 pub fn try_clone(&self) -> Result<Self, NecoFailure> {
540 let location =
541 FailureLocation::operation(FailureOperation::Resolve).with_consumer(self.consumer_id);
542 let mut values = Vec::new();
543 reserve_entries(
544 &mut values,
545 self.values.len(),
546 StorageResource::ProductResolutionEntries,
547 )
548 .map_err(|error| map_storage_failure(location, error))?;
549 for value in &self.values {
550 values.push(value.try_clone()?);
551 }
552 let value_index = bundle_value_index(&values, location)?;
553 Ok(Self {
554 owner: self.owner,
555 consumer_id: self.consumer_id,
556 precision: self.precision,
557 source: self.source,
558 product_identity: self.product_identity.clone(),
559 values,
560 value_index,
561 })
562 }
563}
564
565#[derive(Debug, Eq, PartialEq)]
566pub struct ResolvedExactNumericContext {
567 decided: DecidedExactNumericContext,
568 certified_descents: Vec<CertifiedF64Bundle>,
569 descent_index: SortedIndex<(OwnerId, ConsumerId)>,
570 shared_resolution_count: usize,
571 product_identity: ComputationProductId,
572}
573
574impl ResolvedExactNumericContext {
575 pub fn certified_descent(
576 &self,
577 owner: OwnerId,
578 consumer: ConsumerId,
579 ) -> Option<&CertifiedF64Bundle> {
580 self.descent_index
581 .first(&(owner, consumer))
582 .map(|position| &self.certified_descents[position])
583 }
584
585 pub const fn shared_resolution_count(&self) -> usize {
586 self.shared_resolution_count
587 }
588 pub fn product_identity(&self) -> &ComputationProductId {
589 &self.product_identity
590 }
591}
592
593pub struct DirectInspection<'a> {
594 allocation: &'a ExactNumericAllocation,
595 requirements: Vec<(OwnerId, &'a ExactExpressionRequirement)>,
596 decisions: &'a [DecisionEntry],
597 decision_index: &'a SortedIndex<(OwnerId, ConsumerId)>,
598 certified_descents: &'a [CertifiedF64Bundle],
599 shared_resolution_count: usize,
600}
601
602impl DirectInspection<'_> {
603 pub fn allocation(&self) -> &ExactNumericAllocation {
604 self.allocation
605 }
606
607 pub fn requirements(&self) -> &[(OwnerId, &ExactExpressionRequirement)] {
608 &self.requirements
609 }
610
611 pub fn certified_descents(&self) -> &[CertifiedF64Bundle] {
612 self.certified_descents
613 }
614
615 pub const fn shared_resolution_count(&self) -> usize {
616 self.shared_resolution_count
617 }
618
619 pub fn decision(&self, owner: OwnerId, consumer: ConsumerId) -> Option<&ExactDecisionWitness> {
620 self.decision_index
621 .first(&(owner, consumer))
622 .map(|position| &self.decisions[position].witness)
623 }
624}
625
626#[derive(Debug, Eq, PartialEq)]
627pub struct ExactComputationProduct {
628 resolved: ResolvedExactNumericContext,
629}
630
631impl ExactComputationProduct {
632 pub fn allocation(&self) -> &ExactNumericAllocation {
633 &self.resolved.decided.normalized.allocated.allocation
634 }
635
636 pub fn normal_form(
637 &self,
638 owner: OwnerId,
639 consumer: ConsumerId,
640 expr: ExprId,
641 ) -> Option<&ExactValue> {
642 self.resolved
643 .decided
644 .normalized
645 .normal_form(owner, consumer, expr)
646 }
647
648 pub fn decision(&self, owner: OwnerId, consumer: ConsumerId) -> Option<&ExactDecisionWitness> {
649 self.resolved.decided.decision(owner, consumer)
650 }
651
652 pub fn certified_descent(
653 &self,
654 owner: OwnerId,
655 consumer: ConsumerId,
656 ) -> Option<&CertifiedF64Bundle> {
657 self.resolved.certified_descent(owner, consumer)
658 }
659 pub fn product_identity(&self) -> &ComputationProductId {
660 self.resolved.product_identity()
661 }
662
663 pub fn direct_inspection(&self) -> Result<DirectInspection<'_>, NecoFailure> {
664 let owners = &self.resolved.decided.normalized.allocated.input.owners;
665 let total = requirement_count(owners, FailureOperation::Assemble)?;
666 let mut requirements = Vec::new();
667 reserve_entries(&mut requirements, total, StorageResource::ProductEntries).map_err(
668 |error| {
669 map_storage_failure(
670 FailureLocation::operation(FailureOperation::Assemble),
671 error,
672 )
673 },
674 )?;
675 for core in owners {
676 requirements.extend(
677 core.requirements
678 .iter()
679 .map(|requirement| (core.owner, requirement)),
680 );
681 }
682 Ok(DirectInspection {
683 allocation: self.allocation(),
684 requirements,
685 decisions: &self.resolved.decided.decisions,
686 decision_index: &self.resolved.decided.decision_index,
687 certified_descents: &self.resolved.certified_descents,
688 shared_resolution_count: self.resolved.shared_resolution_count,
689 })
690 }
691
692 pub const fn as_exact_computation(&self) -> &Self {
693 self
694 }
695}
696
697pub fn read_exact_numeric_inputs(
698 input: ExactAllocationInput,
699) -> Result<ExactAllocationInput, NecoFailure> {
700 validate_owners(&input.owners, FailureOperation::Read)?;
701 let expected_source = NecoImplementationSource::current();
702 if input.implementation_source != expected_source {
703 return Err(source_provenance_mismatch(
704 FailureLocation::operation(FailureOperation::Read),
705 expected_source,
706 input.implementation_source,
707 ));
708 }
709 if input.observed_capability.source_identity != env!("CARGO_PKG_VERSION") {
710 return Err(source_provenance_mismatch(
711 FailureLocation::operation(FailureOperation::Read),
712 expected_source,
713 NecoImplementationSource::new(
714 input.observed_capability.source_identity,
715 input.implementation_source.public_api_identity,
716 ),
717 ));
718 }
719 Ok(input)
720}
721
722pub fn allocate_exact_numeric(
723 input: ExactAllocationInput,
724) -> Result<AllocatedExactNumericContext, NecoFailure> {
725 let required_operations = [
726 ExactOperation::NormalizeMonomial,
727 ExactOperation::NormalizeFormSum,
728 ExactOperation::NormalizeAlgebraic,
729 ExactOperation::DecideZero,
730 ExactOperation::DecideEquality,
731 ExactOperation::DecideSign,
732 ExactOperation::DecideDegeneracy,
733 ExactOperation::ResolveCertifiedF64,
734 ];
735 for operation in required_operations {
736 if input
737 .observed_capability
738 .supported_operations
739 .binary_search(&operation)
740 .is_err()
741 {
742 return Err(NecoFailure::UnsupportedRequiredOperation {
743 location: FailureLocation::operation(FailureOperation::Allocate),
744 payload: Box::new(UnsupportedFailurePayload::RequiredOperation(
745 operation_name(operation),
746 )),
747 });
748 }
749 }
750 let mut consumers = Vec::new();
751 let mut seen_consumers = GrowingIndex::default();
752 validate_owners(&input.owners, FailureOperation::Allocate)?;
753 {
754 let mut collect_consumers =
755 |owner: OwnerId, requirements: &[ExactExpressionRequirement]| {
756 for requirement in requirements {
757 let key = (owner, requirement.consumer_id);
758 if seen_consumers.get(&key).is_some() {
759 return Err(NecoFailure::StorageFailure {
760 location: FailureLocation::operation(FailureOperation::Allocate)
761 .with_consumer(requirement.consumer_id),
762 payload: Box::new(crate::StorageFailurePayload::DuplicateId {
763 resource: StorageResource::ProductEntries,
764 id: requirement.consumer_id.get(),
765 }),
766 });
767 }
768 let required = consumers.len().checked_add(1).ok_or_else(|| {
769 map_storage_failure(
770 FailureLocation::operation(FailureOperation::Allocate),
771 crate::StorageError::CapacityOverflow {
772 resource: StorageResource::ProductEntries,
773 },
774 )
775 })?;
776 reserve_entries(&mut consumers, required, StorageResource::ProductEntries)
777 .map_err(|error| {
778 map_storage_failure(
779 FailureLocation::operation(FailureOperation::Allocate),
780 error,
781 )
782 })?;
783 seen_consumers
784 .insert(key, consumers.len(), StorageResource::ProductEntries)
785 .map_err(|error| {
786 map_storage_failure(
787 FailureLocation::operation(FailureOperation::Allocate),
788 error,
789 )
790 })?;
791 consumers.push(key);
792 }
793 Ok::<(), NecoFailure>(())
794 };
795 for core in &input.owners {
796 collect_consumers(core.owner, &core.requirements)?;
797 }
798 }
799 consumers.sort_unstable();
800 let allocation = ExactNumericAllocation {
801 descent_consumers: consumers,
802 };
803 Ok(AllocatedExactNumericContext { input, allocation })
804}
805
806pub fn normalize_exact_expressions(
807 allocated: AllocatedExactNumericContext,
808) -> Result<NormalizedExactNumericContext, NecoFailure> {
809 #[cfg(test)]
810 if let Some(error) = injected_operation_failure(FailureOperation::Normalize) {
811 return Err(error);
812 }
813 let mut normal_values = Vec::new();
814 let mut normal_forms = Vec::new();
815 let mut evaluation_count = 0_usize;
816 for core in &allocated.input.owners {
817 normalize_core(
818 core.owner,
819 core,
820 &mut normal_values,
821 &mut normal_forms,
822 &mut evaluation_count,
823 )?;
824 }
825 let normal_form_index = SortedIndex::build(
826 normal_forms
827 .iter()
828 .map(|entry| (entry.owner, entry.consumer, entry.expr)),
829 StorageResource::ProductEntries,
830 )
831 .map_err(|error| {
832 map_storage_failure(
833 FailureLocation::operation(FailureOperation::Normalize),
834 error,
835 )
836 })?;
837 Ok(NormalizedExactNumericContext {
838 allocated,
839 normal_values,
840 normal_forms,
841 normal_form_index,
842 evaluation_count,
843 })
844}
845
846pub fn decide_exact_properties(
847 normalized: NormalizedExactNumericContext,
848) -> Result<DecidedExactNumericContext, NecoFailure> {
849 #[cfg(test)]
850 if let Some(error) = injected_operation_failure(FailureOperation::Decide) {
851 return Err(error);
852 }
853 let mut decisions = Vec::new();
854 for core in &normalized.allocated.input.owners {
855 decide_core(core.owner, &normalized, &core.requirements, &mut decisions)?;
856 }
857 let decision_index = SortedIndex::build(
858 decisions.iter().map(|entry| (entry.owner, entry.consumer)),
859 StorageResource::ProductEntries,
860 )
861 .map_err(|error| {
862 map_storage_failure(FailureLocation::operation(FailureOperation::Decide), error)
863 })?;
864 Ok(DecidedExactNumericContext {
865 normalized,
866 decisions,
867 decision_index,
868 })
869}
870
871fn decide_core(
872 owner: OwnerId,
873 normalized: &NormalizedExactNumericContext,
874 requirements: &[ExactExpressionRequirement],
875 decisions: &mut Vec<DecisionEntry>,
876) -> Result<(), NecoFailure> {
877 for requirement in requirements {
878 let location = FailureLocation::operation(FailureOperation::Decide)
879 .with_consumer(requirement.consumer_id)
880 .with_decision(requirement.consumer_id.get());
881 let (operands, operand_count) = decision_operands(requirement.decision);
882 let operands = &operands[..operand_count];
883 let first_shared = normalized
884 .normal_form_shared(owner, requirement.consumer_id, operands[0])
885 .ok_or(NecoFailure::UnknownExpression {
886 location: location.with_expr(operands[0]),
887 })?;
888 let first = &**first_shared;
889 let (value, witness) = match requirement.decision {
890 ExactDecisionRequest::Zero(_) => (
891 if decide_zero(first) {
892 ExactDecisionValue::Zero
893 } else {
894 ExactDecisionValue::NonZero
895 },
896 Arc::clone(first_shared),
897 ),
898 ExactDecisionRequest::Equality(_, right) => {
899 let right_value = normalized
900 .normal_form(owner, requirement.consumer_id, right)
901 .ok_or(NecoFailure::UnknownExpression {
902 location: location.with_expr(right),
903 })?;
904 let equal = decide_equality(first, right_value)
905 .map_err(|error| map_eval_failure(location, error))?;
906 let difference = crate::value::sub_exact(first, right_value)
907 .map_err(|error| map_eval_failure(location, error))?;
908 (
909 if equal {
910 ExactDecisionValue::Equal
911 } else {
912 ExactDecisionValue::NotEqual
913 },
914 Arc::new(difference),
915 )
916 }
917 ExactDecisionRequest::Sign(_) => (
918 match decide_sign(first).map_err(|error| map_eval_failure(location, error))? {
919 Sign::Negative => ExactDecisionValue::Negative,
920 Sign::Zero => ExactDecisionValue::Zero,
921 Sign::Positive => ExactDecisionValue::Positive,
922 },
923 Arc::clone(first_shared),
924 ),
925 ExactDecisionRequest::Degeneracy(_) => (
926 if decide_zero(first) {
927 ExactDecisionValue::Degenerate
928 } else {
929 ExactDecisionValue::NonDegenerate
930 },
931 Arc::clone(first_shared),
932 ),
933 };
934 let mut operand_values = Vec::new();
935 reserve_entries(
936 &mut operand_values,
937 operands.len(),
938 StorageResource::ProductEntries,
939 )
940 .map_err(|error| map_storage_failure(location, error))?;
941 operand_values.extend_from_slice(operands);
942 let required = decisions.len().checked_add(1).ok_or_else(|| {
943 map_storage_failure(
944 location,
945 crate::StorageError::CapacityOverflow {
946 resource: StorageResource::ProductEntries,
947 },
948 )
949 })?;
950 reserve_entries(decisions, required, StorageResource::ProductEntries)
951 .map_err(|error| map_storage_failure(location, error))?;
952 decisions.push(DecisionEntry {
953 owner,
954 consumer: requirement.consumer_id,
955 witness: ExactDecisionWitness {
956 kind: requirement.decision.kind(),
957 operands: operand_values,
958 value,
959 normal_form_witness: witness,
960 },
961 });
962 }
963 Ok(())
964}
965
966pub fn resolve_certified_f64(
967 decided: DecidedExactNumericContext,
968) -> Result<ResolvedExactNumericContext, NecoFailure> {
969 #[cfg(test)]
970 if let Some(error) = injected_operation_failure(FailureOperation::Resolve) {
971 return Err(error);
972 }
973 let mut shared_resolution_count = 0_usize;
974 let mut bundles = Vec::new();
975 let product_identity = ComputationProductId::new();
976 for core in &decided.normalized.allocated.input.owners {
977 resolve_core(
978 core.owner,
979 &decided,
980 &core.requirements,
981 &mut shared_resolution_count,
982 &product_identity,
983 &mut bundles,
984 )?;
985 }
986 let descent_index = SortedIndex::build(
987 bundles
988 .iter()
989 .map(|bundle| (bundle.owner, bundle.consumer_id)),
990 StorageResource::ProductEntries,
991 )
992 .map_err(|error| {
993 map_storage_failure(FailureLocation::operation(FailureOperation::Resolve), error)
994 })?;
995 Ok(ResolvedExactNumericContext {
996 decided,
997 certified_descents: bundles,
998 descent_index,
999 shared_resolution_count,
1000 product_identity,
1001 })
1002}
1003
1004fn resolve_core(
1005 owner: OwnerId,
1006 decided: &DecidedExactNumericContext,
1007 requirements: &[ExactExpressionRequirement],
1008 shared_resolution_count: &mut usize,
1009 product_identity: &ComputationProductId,
1010 bundles: &mut Vec<CertifiedF64Bundle>,
1011) -> Result<(), NecoFailure> {
1012 let source = decided.normalized.allocated.input.implementation_source;
1013 let mut cache = ResolutionCache::default();
1014 for requirement in requirements {
1015 let location = FailureLocation::operation(FailureOperation::Resolve)
1016 .with_consumer(requirement.consumer_id);
1017 let mut values = Vec::new();
1018 reserve_entries(
1019 &mut values,
1020 requirement.expressions.len(),
1021 StorageResource::ProductResolutionEntries,
1022 )
1023 .map_err(|error| map_storage_failure(location, error))?;
1024 for expression in &requirement.expressions {
1025 let cache_key = (*expression, requirement.precision);
1026 let certified = match cache
1027 .index
1028 .get(&cache_key)
1029 .map(|position| &cache.entries[position])
1030 {
1031 Some(entry) => Arc::clone(entry),
1032 None => {
1033 let exact = decided
1034 .normalized
1035 .normal_form(owner, requirement.consumer_id, *expression)
1036 .ok_or(NecoFailure::UnknownExpression {
1037 location: location.with_expr(*expression),
1038 })?;
1039 let resolved = Arc::new(
1040 CertifiedF64::resolve_for_requirement(
1041 exact,
1042 *expression,
1043 requirement.precision,
1044 &mut IsolationCache::new(),
1045 )
1046 .map_err(|error| {
1047 map_float_failure(location.with_expr(*expression), error)
1048 })?,
1049 );
1050 let required = cache.entries.len().checked_add(1).ok_or_else(|| {
1051 map_storage_failure(
1052 location,
1053 crate::StorageError::CapacityOverflow {
1054 resource: StorageResource::ProductResolutionEntries,
1055 },
1056 )
1057 })?;
1058 reserve_entries(
1059 &mut cache.entries,
1060 required,
1061 StorageResource::ProductResolutionEntries,
1062 )
1063 .map_err(|error| map_storage_failure(location, error))?;
1064 cache
1065 .index
1066 .insert(
1067 cache_key,
1068 cache.entries.len(),
1069 StorageResource::ProductResolutionEntries,
1070 )
1071 .map_err(|error| map_storage_failure(location, error))?;
1072 cache.entries.push(Arc::clone(&resolved));
1073 resolved
1074 }
1075 };
1076 values.push(CertifiedF64Expression {
1077 owner,
1078 consumer_id: requirement.consumer_id,
1079 expr: *expression,
1080 precision: requirement.precision,
1081 source,
1082 certified,
1083 });
1084 }
1085 let required = bundles.len().checked_add(1).ok_or_else(|| {
1086 map_storage_failure(
1087 location,
1088 crate::StorageError::CapacityOverflow {
1089 resource: StorageResource::ProductEntries,
1090 },
1091 )
1092 })?;
1093 reserve_entries(bundles, required, StorageResource::ProductEntries)
1094 .map_err(|error| map_storage_failure(location, error))?;
1095 let value_index = bundle_value_index(&values, location)?;
1096 bundles.push(CertifiedF64Bundle {
1097 owner,
1098 consumer_id: requirement.consumer_id,
1099 precision: requirement.precision,
1100 source,
1101 values,
1102 value_index,
1103 product_identity: product_identity.clone(),
1104 });
1105 }
1106 *shared_resolution_count += cache.entries.len();
1107 Ok(())
1108}
1109
1110pub fn assemble_exact_computation_product(
1111 resolved: ResolvedExactNumericContext,
1112) -> Result<ExactComputationProduct, NecoFailure> {
1113 let owners = &resolved.decided.normalized.allocated.input.owners;
1114 let expected = requirement_count(owners, FailureOperation::Assemble)?;
1115 if resolved.certified_descents.len() != expected || resolved.decided.decisions.len() != expected
1116 {
1117 return Err(NecoFailure::MissingAssignment {
1118 location: FailureLocation::operation(FailureOperation::Assemble),
1119 });
1120 }
1121 let source = resolved
1122 .decided
1123 .normalized
1124 .allocated
1125 .input
1126 .implementation_source;
1127 for core in owners {
1128 validate_decision_group(
1129 core.owner,
1130 &core.requirements,
1131 &resolved.decided.decision_index,
1132 )?;
1133 validate_result_group(
1134 core.owner,
1135 &core.requirements,
1136 source,
1137 &resolved.certified_descents,
1138 &resolved.descent_index,
1139 )?;
1140 }
1141 Ok(ExactComputationProduct { resolved })
1142}
1143
1144fn validate_decision_group(
1145 owner: OwnerId,
1146 requirements: &[ExactExpressionRequirement],
1147 decision_index: &SortedIndex<(OwnerId, ConsumerId)>,
1148) -> Result<(), NecoFailure> {
1149 for requirement in requirements {
1150 let location = FailureLocation::operation(FailureOperation::Assemble)
1151 .with_consumer(requirement.consumer_id);
1152 if decision_index
1153 .first(&(owner, requirement.consumer_id))
1154 .is_none()
1155 {
1156 return Err(NecoFailure::MissingAssignment { location });
1157 }
1158 }
1159 Ok(())
1160}
1161
1162fn validate_result_group(
1163 owner: OwnerId,
1164 requirements: &[ExactExpressionRequirement],
1165 source: NecoImplementationSource,
1166 bundles: &[CertifiedF64Bundle],
1167 descent_index: &SortedIndex<(OwnerId, ConsumerId)>,
1168) -> Result<(), NecoFailure> {
1169 for requirement in requirements {
1170 let key = (owner, requirement.consumer_id);
1171 let location = FailureLocation::operation(FailureOperation::Assemble)
1172 .with_consumer(requirement.consumer_id);
1173 let Some(position) = descent_index.first(&key) else {
1174 if let Some(actual) = bundles
1175 .iter()
1176 .find(|bundle| bundle.consumer_id == requirement.consumer_id)
1177 .or_else(|| bundles.iter().find(|bundle| bundle.owner == owner))
1178 .or_else(|| bundles.first())
1179 {
1180 return compare_provenance(
1181 location,
1182 provenance_record(owner, requirement, None, source),
1183 bundle_provenance(actual),
1184 );
1185 }
1186 return Err(NecoFailure::MissingAssignment { location });
1187 };
1188 let bundle = &bundles[position];
1189 if descent_index.count(&key) > 1 {
1190 return Err(provenance_mismatch(
1191 location,
1192 provenance_record(owner, requirement, None, source),
1193 bundle_provenance(bundle),
1194 ProvenanceMismatchField::Consumer,
1195 ));
1196 }
1197 validate_bundle(owner, requirement, source, bundle)?;
1198 }
1199 Ok(())
1200}
1201
1202fn validate_bundle(
1203 owner: OwnerId,
1204 requirement: &ExactExpressionRequirement,
1205 source: NecoImplementationSource,
1206 bundle: &CertifiedF64Bundle,
1207) -> Result<(), NecoFailure> {
1208 let bundle_location = FailureLocation::operation(FailureOperation::Assemble)
1209 .with_consumer(requirement.consumer_id);
1210 let expected_bundle = provenance_record(owner, requirement, None, source);
1211 let actual_bundle = bundle_provenance(bundle);
1212 compare_provenance(bundle_location, expected_bundle, actual_bundle)?;
1213 for expression in &requirement.expressions {
1214 let location = bundle_location.with_expr(*expression);
1215 let Some(position) = bundle.value_index.first(expression) else {
1216 if let Some(actual) = bundle.values.iter().find(|value| value.expr != *expression) {
1217 return Err(provenance_mismatch(
1218 location,
1219 provenance_record(owner, requirement, Some(*expression), source),
1220 expression_provenance(actual),
1221 ProvenanceMismatchField::Expression,
1222 ));
1223 }
1224 return Err(NecoFailure::MissingAssignment { location });
1225 };
1226 let value = &bundle.values[position];
1227 if bundle.value_index.count(expression) > 1 {
1228 return Err(provenance_mismatch(
1229 location,
1230 provenance_record(owner, requirement, Some(*expression), source),
1231 expression_provenance(value),
1232 ProvenanceMismatchField::Expression,
1233 ));
1234 }
1235 compare_provenance(
1236 location,
1237 provenance_record(owner, requirement, Some(*expression), source),
1238 expression_provenance(value),
1239 )?;
1240 }
1241 for value in &bundle.values {
1242 if requirement.expressions.binary_search(&value.expr).is_err() {
1243 return Err(provenance_mismatch(
1244 bundle_location.with_expr(value.expr),
1245 provenance_record(owner, requirement, None, source),
1246 expression_provenance(value),
1247 ProvenanceMismatchField::Expression,
1248 ));
1249 }
1250 }
1251 Ok(())
1252}
1253
1254fn compare_provenance(
1255 location: FailureLocation,
1256 expected: ProvenanceRecord,
1257 actual: ProvenanceRecord,
1258) -> Result<(), NecoFailure> {
1259 let field = if expected.consumer_id() != actual.consumer_id() {
1260 ProvenanceMismatchField::Consumer
1261 } else if expected.owner() != actual.owner() {
1262 ProvenanceMismatchField::Owner
1263 } else if expected.expr_id() != actual.expr_id() {
1264 ProvenanceMismatchField::Expression
1265 } else if expected.precision() != actual.precision() {
1266 ProvenanceMismatchField::Precision
1267 } else if expected.revision_identity() != actual.revision_identity()
1268 || expected.public_api_identity() != actual.public_api_identity()
1269 {
1270 ProvenanceMismatchField::Source
1271 } else {
1272 return Ok(());
1273 };
1274 Err(provenance_mismatch(location, expected, actual, field))
1275}
1276
1277fn provenance_mismatch(
1278 location: FailureLocation,
1279 expected: ProvenanceRecord,
1280 actual: ProvenanceRecord,
1281 field: ProvenanceMismatchField,
1282) -> NecoFailure {
1283 NecoFailure::ProvenanceMismatch {
1284 location,
1285 payload: Box::new(ProvenanceMismatchPayload::new(field, expected, actual)),
1286 }
1287}
1288
1289fn provenance_record(
1290 owner: OwnerId,
1291 requirement: &ExactExpressionRequirement,
1292 expr: Option<ExprId>,
1293 source: NecoImplementationSource,
1294) -> ProvenanceRecord {
1295 ProvenanceRecord::new(
1296 Some(owner),
1297 Some(requirement.consumer_id),
1298 expr,
1299 Some(requirement.precision),
1300 Some(source.revision_identity),
1301 Some(source.public_api_identity),
1302 )
1303}
1304
1305fn bundle_provenance(bundle: &CertifiedF64Bundle) -> ProvenanceRecord {
1306 ProvenanceRecord::new(
1307 Some(bundle.owner),
1308 Some(bundle.consumer_id),
1309 None,
1310 Some(bundle.precision),
1311 Some(bundle.source.revision_identity),
1312 Some(bundle.source.public_api_identity),
1313 )
1314}
1315
1316fn expression_provenance(value: &CertifiedF64Expression) -> ProvenanceRecord {
1317 ProvenanceRecord::new(
1318 Some(value.owner),
1319 Some(value.consumer_id),
1320 Some(value.expr),
1321 Some(value.precision),
1322 Some(value.source.revision_identity),
1323 Some(value.source.public_api_identity),
1324 )
1325}
1326
1327fn source_provenance_mismatch(
1328 location: FailureLocation,
1329 expected: NecoImplementationSource,
1330 actual: NecoImplementationSource,
1331) -> NecoFailure {
1332 provenance_mismatch(
1333 location,
1334 ProvenanceRecord::new(
1335 None,
1336 None,
1337 None,
1338 None,
1339 Some(expected.revision_identity),
1340 Some(expected.public_api_identity),
1341 ),
1342 ProvenanceRecord::new(
1343 None,
1344 None,
1345 None,
1346 None,
1347 Some(actual.revision_identity),
1348 Some(actual.public_api_identity),
1349 ),
1350 ProvenanceMismatchField::Source,
1351 )
1352}
1353
1354fn normalize_core(
1355 owner: OwnerId,
1356 core: &OwnerExpressionSet,
1357 values: &mut Vec<Arc<ExactValue>>,
1358 output: &mut Vec<NormalFormEntry>,
1359 evaluation_count: &mut usize,
1360) -> Result<(), NecoFailure> {
1361 let mut cache = EvaluationCache::new();
1362 let mut positions = GrowingIndex::<ExprId>::default();
1363 for requirement in core.requirements() {
1364 for expression in requirement.expressions() {
1365 let location = FailureLocation::operation(FailureOperation::Normalize)
1366 .with_consumer(requirement.consumer_id())
1367 .with_expr(*expression);
1368 let value_position = match positions.get(expression) {
1369 Some(position) => position,
1370 None => {
1371 let before = cache.len();
1372 let value =
1373 evaluate_reachable(*expression, core.graph(), core.atoms(), &mut cache)
1374 .map_err(|error| map_evaluation_run_failure(location, error))?;
1375 *evaluation_count = evaluation_count
1376 .checked_add(cache.len() - before)
1377 .ok_or_else(|| {
1378 map_storage_failure(
1379 location,
1380 crate::StorageError::CapacityOverflow {
1381 resource: StorageResource::ProductEntries,
1382 },
1383 )
1384 })?;
1385 let required = values.len().checked_add(1).ok_or_else(|| {
1386 map_storage_failure(
1387 location,
1388 crate::StorageError::CapacityOverflow {
1389 resource: StorageResource::ProductEntries,
1390 },
1391 )
1392 })?;
1393 reserve_entries(values, required, StorageResource::ProductEntries)
1394 .map_err(|error| map_storage_failure(location, error))?;
1395 positions
1396 .insert(*expression, values.len(), StorageResource::ProductEntries)
1397 .map_err(|error| map_storage_failure(location, error))?;
1398 values.push(Arc::new(value));
1399 values.len() - 1
1400 }
1401 };
1402 let required = output.len().checked_add(1).ok_or_else(|| {
1403 map_storage_failure(
1404 location,
1405 crate::StorageError::CapacityOverflow {
1406 resource: StorageResource::ProductEntries,
1407 },
1408 )
1409 })?;
1410 reserve_entries(output, required, StorageResource::ProductEntries)
1411 .map_err(|error| map_storage_failure(location, error))?;
1412 output.push(NormalFormEntry {
1413 owner,
1414 consumer: requirement.consumer_id(),
1415 expr: *expression,
1416 value_position,
1417 });
1418 }
1419 }
1420 Ok(())
1421}
1422
1423fn validate_owners(
1424 owners: &[OwnerExpressionSet],
1425 operation: FailureOperation,
1426) -> Result<(), NecoFailure> {
1427 for (position, core) in owners.iter().enumerate() {
1428 if owners[..position]
1429 .iter()
1430 .any(|previous| previous.owner == core.owner)
1431 {
1432 return Err(NecoFailure::StorageFailure {
1433 location: FailureLocation::operation(operation),
1434 payload: Box::new(crate::StorageFailurePayload::DuplicateId {
1435 resource: StorageResource::ProductEntries,
1436 id: core.owner.get(),
1437 }),
1438 });
1439 }
1440 }
1441 Ok(())
1442}
1443
1444fn requirement_count(
1445 owners: &[OwnerExpressionSet],
1446 operation: FailureOperation,
1447) -> Result<usize, NecoFailure> {
1448 owners.iter().try_fold(0_usize, |total, core| {
1449 total.checked_add(core.requirements.len()).ok_or_else(|| {
1450 map_storage_failure(
1451 FailureLocation::operation(operation),
1452 crate::StorageError::CapacityOverflow {
1453 resource: StorageResource::ProductEntries,
1454 },
1455 )
1456 })
1457 })
1458}
1459
1460fn map_evaluation_run_failure(location: FailureLocation, error: EvaluationRunError) -> NecoFailure {
1461 match error {
1462 EvaluationRunError::UnknownExpr(expr) => NecoFailure::UnknownExpression {
1463 location: location.with_expr(expr),
1464 },
1465 EvaluationRunError::UnknownAtom { expr, atom } => NecoFailure::UnknownAtom {
1466 location: location.with_expr(expr).with_atom(atom),
1467 },
1468 EvaluationRunError::Evaluation(error) => map_eval_failure(location, error),
1469 EvaluationRunError::Storage(error) => map_storage_failure(location, error),
1470 }
1471}
1472
1473fn map_float_failure(location: FailureLocation, error: PrecisionResolutionError) -> NecoFailure {
1474 match error {
1475 PrecisionResolutionError::Width { requested, width } => NecoFailure::PrecisionExhaustion {
1476 location,
1477 requested,
1478 payload: Box::new(PrecisionFailurePayload::EnclosureWidth {
1479 actual_width: width,
1480 }),
1481 },
1482 PrecisionResolutionError::WidthFailure { requested, error } => {
1483 NecoFailure::PrecisionExhaustion {
1484 location,
1485 requested,
1486 payload: Box::new(PrecisionFailurePayload::Bigint(error)),
1487 }
1488 }
1489 PrecisionResolutionError::Float(error) => match error {
1490 FloatError::OutOfRange => NecoFailure::FloatOutOfRange { location },
1491 FloatError::Bigint(error) => map_resolve_failure(location, ResolveError::Bigint(error)),
1492 FloatError::Algnum(error) => map_resolve_failure(location, ResolveError::Algnum(error)),
1493 FloatError::EnclosureBigint { requested, error } => {
1494 map_precision_bigint_failure(location, requested, error)
1495 }
1496 FloatError::EnclosureAlgnum { requested, error } => {
1497 map_precision_algnum_failure(location, requested, error)
1498 }
1499 FloatError::Storage(error) => map_storage_failure(location, error),
1500 },
1501 }
1502}
1503
1504fn map_precision_bigint_failure(
1505 location: FailureLocation,
1506 requested: AbsoluteBits,
1507 error: BigintError,
1508) -> NecoFailure {
1509 match error {
1510 failure @ BigintError::ExponentOverflow { .. } => NecoFailure::PrecisionExhaustion {
1511 location,
1512 requested,
1513 payload: Box::new(PrecisionFailurePayload::Bigint(failure)),
1514 },
1515 error => map_resolve_failure(location, ResolveError::Bigint(error)),
1516 }
1517}
1518
1519fn map_precision_algnum_failure(
1520 location: FailureLocation,
1521 requested: AbsoluteBits,
1522 error: AlgnumError,
1523) -> NecoFailure {
1524 match error {
1525 failure @ AlgnumError::RepresentationLimit { .. } => NecoFailure::PrecisionExhaustion {
1526 location,
1527 requested,
1528 payload: Box::new(PrecisionFailurePayload::Algnum(failure)),
1529 },
1530 AlgnumError::Bigint(failure @ BigintError::ExponentOverflow { .. }) => {
1531 NecoFailure::PrecisionExhaustion {
1532 location,
1533 requested,
1534 payload: Box::new(PrecisionFailurePayload::Bigint(failure)),
1535 }
1536 }
1537 error => map_resolve_failure(location, ResolveError::Algnum(error)),
1538 }
1539}
1540
1541fn decision_operands(decision: ExactDecisionRequest) -> ([ExprId; 2], usize) {
1542 match decision {
1543 ExactDecisionRequest::Zero(expr)
1544 | ExactDecisionRequest::Sign(expr)
1545 | ExactDecisionRequest::Degeneracy(expr) => ([expr, expr], 1),
1546 ExactDecisionRequest::Equality(left, right) => ([left, right], 2),
1547 }
1548}
1549
1550fn operation_name(operation: ExactOperation) -> &'static str {
1551 match operation {
1552 ExactOperation::NormalizeMonomial => "normalize-monomial",
1553 ExactOperation::NormalizeFormSum => "normalize-form-sum",
1554 ExactOperation::NormalizeAlgebraic => "normalize-algebraic",
1555 ExactOperation::DecideZero => "decide-zero",
1556 ExactOperation::DecideEquality => "decide-equality",
1557 ExactOperation::DecideSign => "decide-sign",
1558 ExactOperation::DecideDegeneracy => "decide-degeneracy",
1559 ExactOperation::ResolveCertifiedF64 => "resolve-certified-f64",
1560 }
1561}
1562
1563#[cfg(test)]
1564#[derive(Clone, Copy)]
1565enum InjectedOperationFailure {
1566 InvalidIsolation,
1567 MultipleTargetRoots,
1568 MissingAssignment(ConsumerId),
1569 FloatOutOfRange(ConsumerId, ExprId),
1570}
1571
1572#[cfg(test)]
1573std::thread_local! {
1574 static INJECTED_OPERATION_FAILURE: core::cell::Cell<Option<InjectedOperationFailure>> = const { core::cell::Cell::new(None) };
1575}
1576
1577#[cfg(test)]
1578fn injected_operation_failure(operation: FailureOperation) -> Option<NecoFailure> {
1579 INJECTED_OPERATION_FAILURE.with(|configured| {
1580 let failure = configured.take()?;
1581 let location = FailureLocation::operation(operation);
1582 Some(match failure {
1583 InjectedOperationFailure::InvalidIsolation => map_eval_failure(
1584 location,
1585 crate::EvalError::Algnum(neco_algnum::AlgnumError::InvalidIsolation),
1586 ),
1587 InjectedOperationFailure::MultipleTargetRoots => map_eval_failure(
1588 location,
1589 crate::EvalError::Algnum(neco_algnum::AlgnumError::MultipleTargetRoots),
1590 ),
1591 InjectedOperationFailure::MissingAssignment(consumer) => {
1592 map_resolve_failure(location, ResolveError::MissingAssignment { consumer })
1593 }
1594 InjectedOperationFailure::FloatOutOfRange(consumer, expr) => {
1595 map_resolve_failure(location, ResolveError::FloatOutOfRange { consumer, expr })
1596 }
1597 })
1598 })
1599}
1600
1601#[cfg(test)]
1602fn with_injected_operation_failure<R>(
1603 failure: InjectedOperationFailure,
1604 operation: impl FnOnce() -> R,
1605) -> R {
1606 INJECTED_OPERATION_FAILURE.with(|configured| configured.set(Some(failure)));
1607 let result = operation();
1608 INJECTED_OPERATION_FAILURE.with(|configured| configured.set(None));
1609 result
1610}
1611
1612#[cfg(test)]
1613mod proof_vectors {
1614 use alloc::vec;
1615
1616 use neco_monomial::Monomial;
1617
1618 use super::*;
1619 use crate::storage::{with_injected_failure, with_injected_failure_after, InjectedFailure};
1620 use crate::{AtomId, ExactValue, ExprNode, StorageError, StorageFailurePayload};
1621
1622 const OPERATIONS: [ExactOperation; 8] = [
1623 ExactOperation::NormalizeMonomial,
1624 ExactOperation::NormalizeFormSum,
1625 ExactOperation::NormalizeAlgebraic,
1626 ExactOperation::DecideZero,
1627 ExactOperation::DecideEquality,
1628 ExactOperation::DecideSign,
1629 ExactOperation::DecideDegeneracy,
1630 ExactOperation::ResolveCertifiedF64,
1631 ];
1632
1633 fn domain(atom: Option<ExactValue>) -> (ExprGraph, AtomStore, ExprId) {
1634 let mut graph = ExprGraph::new();
1635 let expr = graph.push(ExprNode::Atom(AtomId::new(0))).unwrap();
1636 let mut atoms = AtomStore::new();
1637 if let Some(value) = atom {
1638 atoms.insert(AtomId::new(0), value).unwrap();
1639 }
1640 (graph, atoms, expr)
1641 }
1642
1643 fn requirement(consumer: u32, expr: ExprId) -> ExactExpressionRequirement {
1644 ExactExpressionRequirement::new(
1645 ConsumerId::new(consumer),
1646 &[expr],
1647 ExactDecisionRequest::Zero(expr),
1648 AbsoluteBits::new(20),
1649 )
1650 .unwrap()
1651 }
1652
1653 fn input_with_domain(graph: ExprGraph, atoms: AtomStore, expr: ExprId) -> ExactAllocationInput {
1654 let first_owner =
1655 OwnerExpressionSet::new(OwnerId::new(1), graph, atoms, vec![requirement(0, expr)])
1656 .unwrap();
1657 let (second_owner_graph, second_owner_atoms, _) =
1658 domain(Some(ExactValue::Monomial(Monomial::one())));
1659 let second_owner = OwnerExpressionSet::new(
1660 OwnerId::new(2),
1661 second_owner_graph,
1662 second_owner_atoms,
1663 vec![],
1664 )
1665 .unwrap();
1666 ExactAllocationInput::new(
1667 vec![first_owner, second_owner],
1668 NecoObservedCapability::current(&OPERATIONS).unwrap(),
1669 NecoImplementationSource::current(),
1670 )
1671 }
1672
1673 fn allocated_with_value(value: Option<ExactValue>) -> AllocatedExactNumericContext {
1674 let (graph, atoms, expr) = domain(value);
1675 allocate_exact_numeric(
1676 read_exact_numeric_inputs(input_with_domain(graph, atoms, expr)).unwrap(),
1677 )
1678 .unwrap()
1679 }
1680
1681 fn normalized() -> NormalizedExactNumericContext {
1682 normalize_exact_expressions(allocated_with_value(Some(ExactValue::Monomial(
1683 Monomial::one(),
1684 ))))
1685 .unwrap()
1686 }
1687
1688 fn decided() -> DecidedExactNumericContext {
1689 decide_exact_properties(normalized()).unwrap()
1690 }
1691
1692 fn decided_with_two_consumers() -> DecidedExactNumericContext {
1693 let (graph, atoms, expr) = domain(Some(ExactValue::Monomial(Monomial::one())));
1694 let first_owner = OwnerExpressionSet::new(
1695 OwnerId::new(1),
1696 graph,
1697 atoms,
1698 vec![requirement(0, expr), requirement(1, expr)],
1699 )
1700 .unwrap();
1701 let (second_owner_graph, second_owner_atoms, _) =
1702 domain(Some(ExactValue::Monomial(Monomial::one())));
1703 let second_owner = OwnerExpressionSet::new(
1704 OwnerId::new(2),
1705 second_owner_graph,
1706 second_owner_atoms,
1707 vec![],
1708 )
1709 .unwrap();
1710 let input = ExactAllocationInput::new(
1711 vec![first_owner, second_owner],
1712 NecoObservedCapability::current(&OPERATIONS).unwrap(),
1713 NecoImplementationSource::current(),
1714 );
1715 decide_exact_properties(
1716 normalize_exact_expressions(
1717 allocate_exact_numeric(read_exact_numeric_inputs(input).unwrap()).unwrap(),
1718 )
1719 .unwrap(),
1720 )
1721 .unwrap()
1722 }
1723
1724 fn decided_with_two_expressions() -> DecidedExactNumericContext {
1725 let mut graph = ExprGraph::new();
1726 let expr0 = graph.push(ExprNode::Atom(AtomId::new(0))).unwrap();
1727 let expr1 = graph.push(ExprNode::Atom(AtomId::new(1))).unwrap();
1728 let mut atoms = AtomStore::new();
1729 atoms
1730 .insert(AtomId::new(0), ExactValue::Monomial(Monomial::zero()))
1731 .unwrap();
1732 atoms
1733 .insert(AtomId::new(1), ExactValue::Monomial(Monomial::one()))
1734 .unwrap();
1735 let requirement = ExactExpressionRequirement::new(
1736 ConsumerId::new(0),
1737 &[expr0, expr1],
1738 ExactDecisionRequest::Equality(expr0, expr1),
1739 AbsoluteBits::new(20),
1740 )
1741 .unwrap();
1742 let first_owner =
1743 OwnerExpressionSet::new(OwnerId::new(1), graph, atoms, vec![requirement]).unwrap();
1744 let (second_owner_graph, second_owner_atoms, _) =
1745 domain(Some(ExactValue::Monomial(Monomial::one())));
1746 let second_owner = OwnerExpressionSet::new(
1747 OwnerId::new(2),
1748 second_owner_graph,
1749 second_owner_atoms,
1750 vec![],
1751 )
1752 .unwrap();
1753 let input = ExactAllocationInput::new(
1754 vec![first_owner, second_owner],
1755 NecoObservedCapability::current(&OPERATIONS).unwrap(),
1756 NecoImplementationSource::current(),
1757 );
1758 decide_exact_properties(
1759 normalize_exact_expressions(
1760 allocate_exact_numeric(read_exact_numeric_inputs(input).unwrap()).unwrap(),
1761 )
1762 .unwrap(),
1763 )
1764 .unwrap()
1765 }
1766
1767 fn generated_core(
1768 consumers: u32,
1769 offset: u32,
1770 ) -> (ExprGraph, AtomStore, Vec<ExactExpressionRequirement>) {
1771 let mut graph = ExprGraph::new();
1772 let mut atoms = AtomStore::new();
1773 atoms
1774 .insert(AtomId::new(0), ExactValue::Monomial(Monomial::one()))
1775 .unwrap();
1776 let unit = graph.push(ExprNode::Atom(AtomId::new(0))).unwrap();
1777 let mut previous = unit;
1778 for _ in 0..offset {
1779 previous = graph.push(ExprNode::Add(previous, unit)).unwrap();
1780 }
1781 let mut exprs = Vec::new();
1782 for _ in 0..8 {
1783 previous = graph.push(ExprNode::Add(previous, unit)).unwrap();
1784 exprs.push(previous);
1785 }
1786 let mut requirements = Vec::new();
1787 for consumer in 0..consumers {
1788 let first = exprs[(consumer % 8) as usize];
1789 let second = exprs[((consumer * 5 + 3) % 8) as usize];
1790 let operands: &[ExprId] = if first == second {
1791 &[first]
1792 } else {
1793 &[second, first]
1794 };
1795 let decision = if first == second {
1796 ExactDecisionRequest::Zero(first)
1797 } else {
1798 ExactDecisionRequest::Equality(first, second)
1799 };
1800 requirements.push(
1801 ExactExpressionRequirement::new(
1802 ConsumerId::new(consumer),
1803 operands,
1804 decision,
1805 AbsoluteBits::new(10 + consumer % 2),
1806 )
1807 .unwrap(),
1808 );
1809 }
1810 (graph, atoms, requirements)
1811 }
1812
1813 fn generated_input(consumers: u32) -> ExactAllocationInput {
1814 let (graph, atoms, requirements) = generated_core(consumers, 0);
1815 let first_owner =
1816 OwnerExpressionSet::new(OwnerId::new(1), graph, atoms, requirements).unwrap();
1817 let (graph, atoms, requirements) = generated_core(consumers, 20);
1818 let second_owner =
1819 OwnerExpressionSet::new(OwnerId::new(2), graph, atoms, requirements).unwrap();
1820 ExactAllocationInput::new(
1821 vec![first_owner, second_owner],
1822 NecoObservedCapability::current(&OPERATIONS).unwrap(),
1823 NecoImplementationSource::current(),
1824 )
1825 }
1826
1827 fn generated_normalized(consumers: u32) -> NormalizedExactNumericContext {
1828 normalize_exact_expressions(
1829 allocate_exact_numeric(read_exact_numeric_inputs(generated_input(consumers)).unwrap())
1830 .unwrap(),
1831 )
1832 .unwrap()
1833 }
1834
1835 fn generated_resolved(consumers: u32) -> ResolvedExactNumericContext {
1836 resolve_certified_f64(decide_exact_properties(generated_normalized(consumers)).unwrap())
1837 .unwrap()
1838 }
1839
1840 fn shared_core(
1841 consumers: &[(u32, u32, u32)],
1842 ) -> (ExprGraph, AtomStore, Vec<ExactExpressionRequirement>) {
1843 let (graph, atoms, _) = generated_core(0, 0);
1844 let mut requirements = Vec::new();
1845 for (consumer, expr, bits) in consumers {
1846 let expr = ExprId::new(*expr);
1847 requirements.push(
1848 ExactExpressionRequirement::new(
1849 ConsumerId::new(*consumer),
1850 &[expr],
1851 ExactDecisionRequest::Sign(expr),
1852 AbsoluteBits::new(*bits),
1853 )
1854 .unwrap(),
1855 );
1856 }
1857 (graph, atoms, requirements)
1858 }
1859
1860 fn shared_product(
1861 first_owner: &[(u32, u32, u32)],
1862 second_owner: &[(u32, u32, u32)],
1863 ) -> ExactComputationProduct {
1864 let (graph, atoms, requirements) = shared_core(first_owner);
1865 let first_owner =
1866 OwnerExpressionSet::new(OwnerId::new(1), graph, atoms, requirements).unwrap();
1867 let (graph, atoms, requirements) = shared_core(second_owner);
1868 let second_owner =
1869 OwnerExpressionSet::new(OwnerId::new(2), graph, atoms, requirements).unwrap();
1870 let input = ExactAllocationInput::new(
1871 vec![first_owner, second_owner],
1872 NecoObservedCapability::current(&OPERATIONS).unwrap(),
1873 NecoImplementationSource::current(),
1874 );
1875 let resolved = resolve_certified_f64(
1876 decide_exact_properties(
1877 normalize_exact_expressions(
1878 allocate_exact_numeric(read_exact_numeric_inputs(input).unwrap()).unwrap(),
1879 )
1880 .unwrap(),
1881 )
1882 .unwrap(),
1883 )
1884 .unwrap();
1885 assemble_exact_computation_product(resolved).unwrap()
1886 }
1887
1888 #[test]
1889 fn shared_values_match_single_consumer_references_and_share_storage() {
1890 let first_owner: Vec<(u32, u32, u32)> = (0..12_u32)
1891 .map(|consumer| (consumer, 5 + consumer % 3, 20 + 10 * (consumer % 2)))
1892 .collect();
1893 let second_owner: Vec<(u32, u32, u32)> = (0..6_u32)
1894 .map(|consumer| (consumer, 5 + consumer % 2, 20))
1895 .collect();
1896 let product = shared_product(&first_owner, &second_owner);
1897 let normalized = &product.resolved.decided.normalized;
1898 let owners = [
1899 (OwnerId::new(1), &first_owner),
1900 (OwnerId::new(2), &second_owner),
1901 ];
1902 for (owner, consumers) in owners {
1903 for (consumer, expr, bits) in consumers {
1904 let reference = if owner == OwnerId::new(1) {
1905 shared_product(&[(*consumer, *expr, *bits)], &[])
1906 } else {
1907 shared_product(&[], &[(*consumer, *expr, *bits)])
1908 };
1909 let consumer = ConsumerId::new(*consumer);
1910 let expr = ExprId::new(*expr);
1911 let value = normalized.normal_form(owner, consumer, expr).unwrap();
1912 let reference_normalized = &reference.resolved.decided.normalized;
1913 assert_eq!(
1914 Some(value),
1915 reference_normalized.normal_form(owner, consumer, expr)
1916 );
1917 let witness = product.resolved.decided.decision(owner, consumer).unwrap();
1918 let reference_witness = reference
1919 .resolved
1920 .decided
1921 .decision(owner, consumer)
1922 .unwrap();
1923 assert_eq!(witness, reference_witness);
1924 assert!(core::ptr::eq(witness.normal_form_witness(), value));
1925 let certified = &product
1926 .resolved
1927 .certified_descent(owner, consumer)
1928 .unwrap()
1929 .values[0];
1930 let reference_certified = &reference
1931 .resolved
1932 .certified_descent(owner, consumer)
1933 .unwrap()
1934 .values[0];
1935 assert_eq!(certified, reference_certified);
1936 }
1937 }
1938 for (owner, consumers) in owners {
1939 for (a, first) in consumers.iter().enumerate() {
1940 for second in &consumers[a + 1..] {
1941 let first_consumer = ConsumerId::new(first.0);
1942 let second_consumer = ConsumerId::new(second.0);
1943 if first.1 == second.1 {
1944 assert!(core::ptr::eq(
1945 normalized
1946 .normal_form(owner, first_consumer, ExprId::new(first.1))
1947 .unwrap(),
1948 normalized
1949 .normal_form(owner, second_consumer, ExprId::new(second.1))
1950 .unwrap(),
1951 ));
1952 }
1953 let first_value = &product
1954 .resolved
1955 .certified_descent(owner, first_consumer)
1956 .unwrap()
1957 .values[0];
1958 let second_value = &product
1959 .resolved
1960 .certified_descent(owner, second_consumer)
1961 .unwrap()
1962 .values[0];
1963 let same = first.1 == second.1 && first.2 == second.2;
1964 assert_eq!(
1965 core::ptr::eq(first_value.certified(), second_value.certified()),
1966 same
1967 );
1968 }
1969 }
1970 }
1971 let shared_expr = ExprId::new(5);
1972 let first = normalized
1973 .normal_form(OwnerId::new(1), ConsumerId::new(0), shared_expr)
1974 .unwrap();
1975 let other = normalized
1976 .normal_form(OwnerId::new(2), ConsumerId::new(0), shared_expr)
1977 .unwrap();
1978 assert!(!core::ptr::eq(first, other));
1979 let bundle = |owner, consumer| {
1980 product
1981 .resolved
1982 .certified_descent(owner, ConsumerId::new(consumer))
1983 .unwrap()
1984 .values[0]
1985 .certified()
1986 };
1987 assert!(!core::ptr::eq(
1988 bundle(OwnerId::new(1), 0),
1989 bundle(OwnerId::new(2), 0)
1990 ));
1991 assert_eq!(product.resolved.shared_resolution_count(), 6 + 2);
1992 }
1993
1994 #[test]
1995 fn keyed_lookups_match_linear_search_on_generated_input() {
1996 let resolved = generated_resolved(40);
1997 let normalized = &resolved.decided.normalized;
1998 let owners = [OwnerId::new(1), OwnerId::new(2)];
1999 for owner in owners {
2000 for consumer in 0..60_u32 {
2001 let consumer = ConsumerId::new(consumer);
2002 let expected = resolved
2003 .certified_descents
2004 .iter()
2005 .find(|bundle| bundle.owner == owner && bundle.consumer_id == consumer);
2006 assert_eq!(resolved.certified_descent(owner, consumer), expected);
2007 let expected = resolved
2008 .decided
2009 .decisions
2010 .iter()
2011 .find(|entry| entry.owner == owner && entry.consumer == consumer)
2012 .map(|entry| &entry.witness);
2013 assert_eq!(resolved.decided.decision(owner, consumer), expected);
2014 for expr in 0..40_u32 {
2015 let expr = ExprId::new(expr);
2016 let expected = normalized
2017 .normal_forms
2018 .iter()
2019 .find(|entry| {
2020 entry.owner == owner && entry.consumer == consumer && entry.expr == expr
2021 })
2022 .map(|entry| &*normalized.normal_values[entry.value_position]);
2023 assert_eq!(normalized.normal_form(owner, consumer, expr), expected);
2024 }
2025 }
2026 }
2027 let first = ConsumerId::new(3);
2028 let expr = resolved.certified_descents[3].values[0].expr;
2029 assert_ne!(
2030 normalized.normal_form(OwnerId::new(1), first, expr),
2031 normalized.normal_form(OwnerId::new(2), first, expr)
2032 );
2033 let product = assemble_exact_computation_product(resolved).unwrap();
2034 let inspection = product.direct_inspection().unwrap();
2035 for owner in owners {
2036 for consumer in 0..60_u32 {
2037 let consumer = ConsumerId::new(consumer);
2038 let expected = product
2039 .resolved
2040 .decided
2041 .decisions
2042 .iter()
2043 .find(|entry| entry.owner == owner && entry.consumer == consumer)
2044 .map(|entry| &entry.witness);
2045 assert_eq!(inspection.decision(owner, consumer), expected);
2046 }
2047 }
2048 }
2049
2050 fn typed_failures_until_success<T, R: core::fmt::Debug>(
2051 resource: StorageResource,
2052 operation: FailureOperation,
2053 setup: impl Fn() -> T,
2054 run: impl Fn(T) -> Result<R, NecoFailure>,
2055 ) -> usize {
2056 for skipped in 0..64 {
2057 let input = setup();
2058 let result =
2059 with_injected_failure_after(resource, InjectedFailure::Allocation, skipped, || {
2060 run(input)
2061 });
2062 match result {
2063 Ok(_) => return skipped,
2064 Err(NecoFailure::StorageFailure { location, payload }) => {
2065 assert_eq!(location.operation_kind(), operation);
2066 assert!(matches!(
2067 *payload,
2068 StorageFailurePayload::Storage(StorageError::AllocationFailure {
2069 resource: failed,
2070 ..
2071 }) if failed == resource
2072 ));
2073 }
2074 Err(other) => panic!("unexpected failure: {other:?}"),
2075 }
2076 }
2077 panic!("operation kept failing");
2078 }
2079
2080 #[test]
2081 fn index_allocation_failures_are_typed_storage_failures() {
2082 let allocated = || {
2083 allocate_exact_numeric(read_exact_numeric_inputs(generated_input(3)).unwrap()).unwrap()
2084 };
2085 let reserves = typed_failures_until_success(
2086 StorageResource::ProductEntries,
2087 FailureOperation::Normalize,
2088 allocated,
2089 normalize_exact_expressions,
2090 );
2091 assert_eq!(reserves, 39);
2092 let reserves = typed_failures_until_success(
2093 StorageResource::ProductEntries,
2094 FailureOperation::Decide,
2095 || generated_normalized(3),
2096 decide_exact_properties,
2097 );
2098 assert_eq!(reserves, 2 * 6 + 1);
2099 let decided = || decide_exact_properties(generated_normalized(1)).unwrap();
2100 let reserves = typed_failures_until_success(
2101 StorageResource::ProductEntries,
2102 FailureOperation::Resolve,
2103 decided,
2104 resolve_certified_f64,
2105 );
2106 assert_eq!(reserves, 3);
2107 let reserves = typed_failures_until_success(
2108 StorageResource::ProductResolutionEntries,
2109 FailureOperation::Resolve,
2110 decided,
2111 resolve_certified_f64,
2112 );
2113 assert!(reserves > 2);
2114 }
2115
2116 #[test]
2117 fn work_area_allocation_failure_precedes_duplicate_failure() {
2118 let expr = ExprId::new(0);
2119 let duplicate = || {
2120 ExactExpressionRequirement::new(
2121 ConsumerId::new(0),
2122 &[expr, expr],
2123 ExactDecisionRequest::Zero(expr),
2124 AbsoluteBits::new(20),
2125 )
2126 };
2127 let plain = duplicate();
2128 assert!(matches!(
2129 plain,
2130 Err(NecoFailure::StorageFailure { location, payload })
2131 if location.expr() == Some(expr)
2132 && matches!(
2133 *payload,
2134 StorageFailurePayload::DuplicateId { id: 0, .. }
2135 )
2136 ));
2137 for skipped in 0..2 {
2138 let injected = with_injected_failure_after(
2139 StorageResource::ProductEntries,
2140 InjectedFailure::Allocation,
2141 skipped,
2142 duplicate,
2143 );
2144 assert!(matches!(
2145 injected,
2146 Err(NecoFailure::StorageFailure { payload, .. })
2147 if matches!(
2148 *payload,
2149 StorageFailurePayload::Storage(StorageError::AllocationFailure {
2150 resource: StorageResource::ProductEntries,
2151 ..
2152 })
2153 )
2154 ));
2155 }
2156 }
2157
2158 #[test]
2159 fn allocation_storage_failure_preserves_operation_location_and_payload() {
2160 let (graph, atoms, expr) = domain(Some(ExactValue::Monomial(Monomial::one())));
2161 let input = read_exact_numeric_inputs(input_with_domain(graph, atoms, expr)).unwrap();
2162 let result = with_injected_failure(
2163 StorageResource::ProductEntries,
2164 InjectedFailure::Allocation,
2165 || allocate_exact_numeric(input),
2166 );
2167 assert_eq!(
2168 result,
2169 Err(NecoFailure::StorageFailure {
2170 location: FailureLocation::operation(FailureOperation::Allocate),
2171 payload: Box::new(StorageFailurePayload::Storage(
2172 StorageError::AllocationFailure {
2173 resource: StorageResource::ProductEntries,
2174 requested_elements: 1,
2175 }
2176 )),
2177 })
2178 );
2179 }
2180
2181 #[test]
2182 fn normalize_operation_failure_vectors_are_executable() {
2183 let (graph, atoms, expr) = domain(None);
2184 let unknown_atom = normalize_exact_expressions(
2185 allocate_exact_numeric(
2186 read_exact_numeric_inputs(input_with_domain(graph, atoms, expr)).unwrap(),
2187 )
2188 .unwrap(),
2189 );
2190 assert!(matches!(
2191 unknown_atom,
2192 Err(NecoFailure::UnknownAtom { location })
2193 if location.operation_kind() == FailureOperation::Normalize
2194 && location.expr() == Some(expr)
2195 && location.atom() == Some(AtomId::new(0))
2196 ));
2197
2198 let mut malformed = allocated_with_value(Some(ExactValue::Monomial(Monomial::one())));
2199 malformed.input.owners[0].requirements[0].expressions[0] = ExprId::new(99);
2200 assert!(matches!(
2201 normalize_exact_expressions(malformed),
2202 Err(NecoFailure::UnknownExpression { location })
2203 if location.operation_kind() == FailureOperation::Normalize
2204 && location.expr() == Some(ExprId::new(99))
2205 ));
2206
2207 let mut graph = ExprGraph::new();
2208 let zero = graph.push(ExprNode::Atom(AtomId::new(0))).unwrap();
2209 let division = graph.push(ExprNode::Div(zero, zero)).unwrap();
2210 let mut atoms = AtomStore::new();
2211 atoms
2212 .insert(AtomId::new(0), ExactValue::Monomial(Monomial::zero()))
2213 .unwrap();
2214 assert!(matches!(
2215 normalize_exact_expressions(
2216 allocate_exact_numeric(
2217 read_exact_numeric_inputs(input_with_domain(graph, atoms, division)).unwrap(),
2218 )
2219 .unwrap(),
2220 ),
2221 Err(NecoFailure::DivisionByZero { location })
2222 if location.operation_kind() == FailureOperation::Normalize
2223 ));
2224
2225 let mut graph = ExprGraph::new();
2226 let zero = graph.push(ExprNode::Atom(AtomId::new(0))).unwrap();
2227 let power = graph
2228 .push(ExprNode::Pow {
2229 base: zero,
2230 exponent: neco_bigint::ReducedRational::from_bigint(neco_bigint::BigInt::zero())
2231 .unwrap(),
2232 })
2233 .unwrap();
2234 let mut atoms = AtomStore::new();
2235 atoms
2236 .insert(AtomId::new(0), ExactValue::Monomial(Monomial::zero()))
2237 .unwrap();
2238 assert!(matches!(
2239 normalize_exact_expressions(
2240 allocate_exact_numeric(
2241 read_exact_numeric_inputs(input_with_domain(graph, atoms, power)).unwrap(),
2242 )
2243 .unwrap(),
2244 ),
2245 Err(NecoFailure::UndefinedPower { location })
2246 if location.operation_kind() == FailureOperation::Normalize
2247 ));
2248
2249 let invalid_isolation =
2250 with_injected_operation_failure(InjectedOperationFailure::InvalidIsolation, || {
2251 normalize_exact_expressions(allocated_with_value(Some(ExactValue::Monomial(
2252 Monomial::one(),
2253 ))))
2254 });
2255 assert!(matches!(
2256 invalid_isolation,
2257 Err(NecoFailure::InvalidIsolation { location })
2258 if location.operation_kind() == FailureOperation::Normalize
2259 ));
2260
2261 let storage = with_injected_failure(
2262 StorageResource::EvaluationEntries,
2263 InjectedFailure::Allocation,
2264 || {
2265 normalize_exact_expressions(allocated_with_value(Some(ExactValue::Monomial(
2266 Monomial::one(),
2267 ))))
2268 },
2269 );
2270 assert!(matches!(
2271 storage,
2272 Err(NecoFailure::StorageFailure { location, payload })
2273 if location.operation_kind() == FailureOperation::Normalize
2274 && matches!(
2275 *payload,
2276 StorageFailurePayload::Storage(StorageError::AllocationFailure {
2277 resource: StorageResource::EvaluationEntries,
2278 ..
2279 })
2280 )
2281 ));
2282 }
2283
2284 #[test]
2285 fn decide_operation_failure_vectors_are_executable() {
2286 let invalid_input = normalized();
2287 let invalid =
2288 with_injected_operation_failure(InjectedOperationFailure::InvalidIsolation, || {
2289 decide_exact_properties(invalid_input)
2290 });
2291 assert!(matches!(
2292 invalid,
2293 Err(NecoFailure::InvalidIsolation { location })
2294 if location.operation_kind() == FailureOperation::Decide
2295 ));
2296 let multiple_input = normalized();
2297 let multiple =
2298 with_injected_operation_failure(InjectedOperationFailure::MultipleTargetRoots, || {
2299 decide_exact_properties(multiple_input)
2300 });
2301 assert!(matches!(
2302 multiple,
2303 Err(NecoFailure::MultipleTargetRoots { location })
2304 if location.operation_kind() == FailureOperation::Decide
2305 ));
2306 let storage_input = normalized();
2307 let storage = with_injected_failure(
2308 StorageResource::ProductEntries,
2309 InjectedFailure::Allocation,
2310 || decide_exact_properties(storage_input),
2311 );
2312 assert!(matches!(
2313 storage,
2314 Err(NecoFailure::StorageFailure { location, payload })
2315 if location.operation_kind() == FailureOperation::Decide
2316 && matches!(
2317 *payload,
2318 StorageFailurePayload::Storage(StorageError::AllocationFailure {
2319 resource: StorageResource::ProductEntries,
2320 ..
2321 })
2322 )
2323 ));
2324 }
2325
2326 #[test]
2327 fn resolve_operation_failure_vectors_are_executable() {
2328 let consumer = ConsumerId::new(7);
2329 let missing_input = decided();
2330 let missing = with_injected_operation_failure(
2331 InjectedOperationFailure::MissingAssignment(consumer),
2332 || resolve_certified_f64(missing_input),
2333 );
2334 assert!(matches!(
2335 missing,
2336 Err(NecoFailure::MissingAssignment { location })
2337 if location.operation_kind() == FailureOperation::Resolve
2338 && location.consumer() == Some(consumer)
2339 ));
2340 let expr = ExprId::new(3);
2341 let out_of_range_input = decided();
2342 let out_of_range = with_injected_operation_failure(
2343 InjectedOperationFailure::FloatOutOfRange(consumer, expr),
2344 || resolve_certified_f64(out_of_range_input),
2345 );
2346 assert!(matches!(
2347 out_of_range,
2348 Err(NecoFailure::FloatOutOfRange { location })
2349 if location.operation_kind() == FailureOperation::Resolve
2350 && location.consumer() == Some(consumer)
2351 && location.expr() == Some(expr)
2352 ));
2353 let storage = with_injected_failure(
2354 StorageResource::ProductResolutionEntries,
2355 InjectedFailure::Allocation,
2356 || resolve_certified_f64(decided()),
2357 );
2358 assert!(matches!(
2359 storage,
2360 Err(NecoFailure::StorageFailure { location, payload })
2361 if location.operation_kind() == FailureOperation::Resolve
2362 && matches!(
2363 *payload,
2364 StorageFailurePayload::Storage(StorageError::AllocationFailure {
2365 resource: StorageResource::ProductResolutionEntries,
2366 ..
2367 })
2368 )
2369 ));
2370 }
2371
2372 #[test]
2373 fn missing_domain_assembly_returns_failure_without_partial_product() {
2374 let mut resolved = resolve_certified_f64(decided()).unwrap();
2375 resolved.certified_descents.clear();
2376 let result = assemble_exact_computation_product(resolved);
2377 assert!(matches!(
2378 result,
2379 Err(NecoFailure::MissingAssignment { location })
2380 if location.operation_kind() == FailureOperation::Assemble
2381 ));
2382 }
2383
2384 fn reindex(resolved: &mut ResolvedExactNumericContext) {
2385 resolved.descent_index = SortedIndex::build(
2386 resolved
2387 .certified_descents
2388 .iter()
2389 .map(|bundle| (bundle.owner, bundle.consumer_id)),
2390 StorageResource::ProductEntries,
2391 )
2392 .unwrap();
2393 for bundle in &mut resolved.certified_descents {
2394 bundle.value_index = bundle_value_index(
2395 &bundle.values,
2396 FailureLocation::operation(FailureOperation::Assemble),
2397 )
2398 .unwrap();
2399 }
2400 }
2401
2402 fn assembly_mismatch_field(
2403 mut resolved: ResolvedExactNumericContext,
2404 mutate: impl FnOnce(&mut CertifiedF64Bundle),
2405 ) -> ProvenanceMismatchField {
2406 mutate(&mut resolved.certified_descents[0]);
2407 reindex(&mut resolved);
2408 match assemble_exact_computation_product(resolved) {
2409 Err(NecoFailure::ProvenanceMismatch { payload, .. }) => payload.field(),
2410 result => panic!("unexpected assembly result: {result:?}"),
2411 }
2412 }
2413
2414 fn assembly_mismatch_payload(
2415 mut resolved: ResolvedExactNumericContext,
2416 mutate: impl FnOnce(&mut CertifiedF64Bundle),
2417 ) -> ProvenanceMismatchPayload {
2418 mutate(&mut resolved.certified_descents[0]);
2419 reindex(&mut resolved);
2420 match assemble_exact_computation_product(resolved) {
2421 Err(NecoFailure::ProvenanceMismatch { payload, .. }) => *payload,
2422 result => panic!("unexpected assembly result: {result:?}"),
2423 }
2424 }
2425
2426 #[test]
2427 fn assembly_rejects_each_result_lineage_mismatch() {
2428 assert_eq!(
2429 assembly_mismatch_field(
2430 resolve_certified_f64(decided_with_two_consumers()).unwrap(),
2431 |bundle| {
2432 bundle.consumer_id = ConsumerId::new(1);
2433 },
2434 ),
2435 ProvenanceMismatchField::Consumer
2436 );
2437 assert_eq!(
2438 assembly_mismatch_field(
2439 resolve_certified_f64(decided_with_two_expressions()).unwrap(),
2440 |bundle| {
2441 bundle.values[0].expr = ExprId::new(1);
2442 },
2443 ),
2444 ProvenanceMismatchField::Expression
2445 );
2446 assert_eq!(
2447 assembly_mismatch_field(resolve_certified_f64(decided()).unwrap(), |bundle| {
2448 bundle.consumer_id = ConsumerId::new(9);
2449 }),
2450 ProvenanceMismatchField::Consumer
2451 );
2452 assert_eq!(
2453 assembly_mismatch_field(resolve_certified_f64(decided()).unwrap(), |bundle| {
2454 bundle.owner = OwnerId::new(2);
2455 }),
2456 ProvenanceMismatchField::Owner
2457 );
2458 assert_eq!(
2459 assembly_mismatch_field(resolve_certified_f64(decided()).unwrap(), |bundle| {
2460 bundle.precision = AbsoluteBits::new(99);
2461 }),
2462 ProvenanceMismatchField::Precision
2463 );
2464 assert_eq!(
2465 assembly_mismatch_field(resolve_certified_f64(decided()).unwrap(), |bundle| {
2466 bundle.source = NecoImplementationSource::new("wrong", "wrong-api");
2467 }),
2468 ProvenanceMismatchField::Source
2469 );
2470 assert_eq!(
2471 assembly_mismatch_field(resolve_certified_f64(decided()).unwrap(), |bundle| {
2472 bundle.values[0].expr = ExprId::new(99);
2473 }),
2474 ProvenanceMismatchField::Expression
2475 );
2476 }
2477
2478 fn lineage_with_owner(owner: OwnerId) -> ProvenanceRecord {
2479 ProvenanceRecord::new(
2480 Some(owner),
2481 Some(ConsumerId::new(3)),
2482 Some(ExprId::new(4)),
2483 Some(AbsoluteBits::new(20)),
2484 Some("revision"),
2485 Some("api"),
2486 )
2487 }
2488
2489 #[test]
2490 fn lineage_comparison_distinguishes_owners_by_identifier_value_alone() {
2491 let location = FailureLocation::operation(FailureOperation::Assemble);
2492 for owner_value in [0, 1, 7, u32::MAX] {
2493 assert!(compare_provenance(
2494 location,
2495 lineage_with_owner(OwnerId::new(owner_value)),
2496 lineage_with_owner(OwnerId::new(owner_value)),
2497 )
2498 .is_ok());
2499 }
2500 for (expected_value, actual_value) in [(0, 1), (1, 0), (7, 8), (1, u32::MAX)] {
2501 let expected = lineage_with_owner(OwnerId::new(expected_value));
2502 let actual = lineage_with_owner(OwnerId::new(actual_value));
2503 match compare_provenance(location, expected, actual) {
2504 Err(NecoFailure::ProvenanceMismatch { payload, .. }) => {
2505 assert_eq!(payload.field(), ProvenanceMismatchField::Owner);
2506 assert_eq!(
2507 payload.expected().owner(),
2508 Some(OwnerId::new(expected_value))
2509 );
2510 assert_eq!(payload.actual().owner(), Some(OwnerId::new(actual_value)));
2511 }
2512 result => panic!("unexpected comparison result: {result:?}"),
2513 }
2514 }
2515 }
2516
2517 fn expected_expression_provenance() -> ProvenanceRecord {
2518 ProvenanceRecord::new(
2519 Some(OwnerId::new(1)),
2520 Some(ConsumerId::new(0)),
2521 Some(ExprId::new(0)),
2522 Some(AbsoluteBits::new(20)),
2523 Some(env!("CARGO_PKG_VERSION")),
2524 Some(PUBLIC_API_IDENTITY),
2525 )
2526 }
2527
2528 fn assert_nested_lineage_payload(
2529 payload: ProvenanceMismatchPayload,
2530 field: ProvenanceMismatchField,
2531 actual: ProvenanceRecord,
2532 ) {
2533 assert_eq!(payload.field(), field);
2534 assert_eq!(payload.expected(), expected_expression_provenance());
2535 assert_eq!(payload.actual(), actual);
2536 }
2537
2538 #[test]
2539 fn nested_expression_lineage_failure_contains_expected_and_actual_records() {
2540 let payload =
2541 assembly_mismatch_payload(resolve_certified_f64(decided()).unwrap(), |bundle| {
2542 bundle.values[0].owner = OwnerId::new(2);
2543 });
2544 assert_nested_lineage_payload(
2545 payload,
2546 ProvenanceMismatchField::Owner,
2547 ProvenanceRecord::new(
2548 Some(OwnerId::new(2)),
2549 Some(ConsumerId::new(0)),
2550 Some(ExprId::new(0)),
2551 Some(AbsoluteBits::new(20)),
2552 Some(env!("CARGO_PKG_VERSION")),
2553 Some(PUBLIC_API_IDENTITY),
2554 ),
2555 );
2556
2557 let payload =
2558 assembly_mismatch_payload(resolve_certified_f64(decided()).unwrap(), |bundle| {
2559 bundle.values[0].consumer_id = ConsumerId::new(99);
2560 });
2561 assert_nested_lineage_payload(
2562 payload,
2563 ProvenanceMismatchField::Consumer,
2564 ProvenanceRecord::new(
2565 Some(OwnerId::new(1)),
2566 Some(ConsumerId::new(99)),
2567 Some(ExprId::new(0)),
2568 Some(AbsoluteBits::new(20)),
2569 Some(env!("CARGO_PKG_VERSION")),
2570 Some(PUBLIC_API_IDENTITY),
2571 ),
2572 );
2573
2574 let payload =
2575 assembly_mismatch_payload(resolve_certified_f64(decided()).unwrap(), |bundle| {
2576 bundle.values[0].precision = AbsoluteBits::new(99);
2577 });
2578 assert_nested_lineage_payload(
2579 payload,
2580 ProvenanceMismatchField::Precision,
2581 ProvenanceRecord::new(
2582 Some(OwnerId::new(1)),
2583 Some(ConsumerId::new(0)),
2584 Some(ExprId::new(0)),
2585 Some(AbsoluteBits::new(99)),
2586 Some(env!("CARGO_PKG_VERSION")),
2587 Some(PUBLIC_API_IDENTITY),
2588 ),
2589 );
2590
2591 let payload =
2592 assembly_mismatch_payload(resolve_certified_f64(decided()).unwrap(), |bundle| {
2593 bundle.values[0].source = NecoImplementationSource::new("wrong", "wrong-api");
2594 });
2595 assert_nested_lineage_payload(
2596 payload,
2597 ProvenanceMismatchField::Source,
2598 ProvenanceRecord::new(
2599 Some(OwnerId::new(1)),
2600 Some(ConsumerId::new(0)),
2601 Some(ExprId::new(0)),
2602 Some(AbsoluteBits::new(20)),
2603 Some("wrong"),
2604 Some("wrong-api"),
2605 ),
2606 );
2607 }
2608
2609 #[test]
2610 fn representation_limit_maps_to_typed_precision_exhaustion() {
2611 let requested = AbsoluteBits::new(80);
2612 let location = FailureLocation::operation(FailureOperation::Resolve)
2613 .with_consumer(ConsumerId::new(0))
2614 .with_expr(ExprId::new(0));
2615 let result = map_float_failure(
2616 location,
2617 PrecisionResolutionError::Float(FloatError::EnclosureAlgnum {
2618 requested,
2619 error: AlgnumError::RepresentationLimit {
2620 resource: neco_algnum::RepresentationResource::RootDegree,
2621 required: neco_bigint::BigUint::try_from(41_u8).unwrap(),
2622 maximum: neco_bigint::BigUint::try_from(40_u8).unwrap(),
2623 },
2624 }),
2625 );
2626 assert!(matches!(
2627 result,
2628 NecoFailure::PrecisionExhaustion {
2629 location: actual,
2630 requested: actual_requested,
2631 payload,
2632 } if actual == location
2633 && actual_requested == requested
2634 && matches!(
2635 *payload,
2636 PrecisionFailurePayload::Algnum(AlgnumError::RepresentationLimit { .. })
2637 )
2638 ));
2639 }
2640}