Skip to main content

neco_expr/
product.rs

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}