1use alloc::vec::Vec;
2use core::mem::size_of;
3
4use crate::{
5 AbsoluteBits, AtomId, CertifiedF64, ConsumerId, EvalError, ExactValue, ExprId, InsertError,
6 ResolveError, StorageError,
7};
8use neco_algnum::IsolatingInterval;
9
10#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
11pub enum StorageResource {
12 GraphNodes,
13 AtomEntries,
14 PrecisionEntries,
15 AssignmentEntries,
16 EvaluationEntries,
17 IsolationEntries,
18 ResolvedEntries,
19}
20
21#[derive(Debug, Eq, PartialEq)]
22pub struct AtomStore {
23 entries: Vec<(AtomId, ExactValue)>,
24}
25
26#[derive(Debug, Eq, PartialEq)]
27pub struct PrecisionRequirements {
28 entries: Vec<(ConsumerId, AbsoluteBits)>,
29}
30
31#[derive(Debug, Eq, PartialEq)]
32pub struct Assignments {
33 entries: Vec<(ConsumerId, ExprId)>,
34}
35
36#[derive(Debug, Eq, PartialEq)]
37pub struct EvaluationCache {
38 entries: Vec<(ExprId, Result<ExactValue, EvalError>)>,
39}
40
41#[derive(Debug, Eq, PartialEq)]
42pub struct IsolationCache {
43 entries: Vec<((ExprId, AbsoluteBits), IsolatingInterval)>,
44}
45
46#[derive(Debug, Eq, PartialEq)]
47pub struct ResolvedValues {
48 entries: Vec<(ConsumerId, Result<CertifiedF64, ResolveError>)>,
49}
50
51#[allow(clippy::len_without_is_empty, clippy::new_without_default)]
52impl AtomStore {
53 pub fn new() -> Self {
54 Self {
55 entries: Vec::new(),
56 }
57 }
58
59 pub fn len(&self) -> usize {
60 self.entries.len()
61 }
62
63 pub fn get(&self, id: AtomId) -> Option<&ExactValue> {
64 get_entry(&self.entries, id)
65 }
66
67 pub fn insert(&mut self, id: AtomId, value: ExactValue) -> Result<(), InsertError> {
68 insert_entry(
69 &mut self.entries,
70 id,
71 value,
72 StorageResource::AtomEntries,
73 id.get(),
74 )
75 }
76
77 pub fn set(&mut self, id: AtomId, value: ExactValue) -> Result<(), InsertError> {
78 set_entry(
79 &mut self.entries,
80 id,
81 value,
82 StorageResource::AtomEntries,
83 id.get(),
84 )
85 }
86
87 pub fn try_clone(&self) -> Result<Self, InsertError> {
88 let mut entries = Vec::new();
89 reserve_entries(
90 &mut entries,
91 self.entries.len(),
92 StorageResource::AtomEntries,
93 )?;
94 for (id, value) in &self.entries {
95 entries.push((*id, value.try_clone().map_err(atom_value_error)?));
96 }
97 Ok(Self { entries })
98 }
99}
100
101fn atom_value_error(error: EvalError) -> InsertError {
102 InsertError::Value(atom_value_payload(error))
103}
104
105fn atom_value_payload(error: EvalError) -> EvalError {
106 error
107}
108
109#[allow(clippy::len_without_is_empty, clippy::new_without_default)]
110impl PrecisionRequirements {
111 pub fn new() -> Self {
112 Self {
113 entries: Vec::new(),
114 }
115 }
116
117 pub fn len(&self) -> usize {
118 self.entries.len()
119 }
120
121 pub fn get(&self, id: ConsumerId) -> Option<AbsoluteBits> {
122 get_entry(&self.entries, id).copied()
123 }
124
125 pub fn insert(&mut self, id: ConsumerId, bits: AbsoluteBits) -> Result<(), InsertError> {
126 insert_entry(
127 &mut self.entries,
128 id,
129 bits,
130 StorageResource::PrecisionEntries,
131 id.get(),
132 )
133 }
134
135 pub fn set(&mut self, id: ConsumerId, bits: AbsoluteBits) -> Result<(), InsertError> {
136 set_entry(
137 &mut self.entries,
138 id,
139 bits,
140 StorageResource::PrecisionEntries,
141 id.get(),
142 )
143 }
144
145 pub fn try_clone(&self) -> Result<Self, InsertError> {
146 Ok(Self {
147 entries: try_clone_copy_entries(&self.entries, StorageResource::PrecisionEntries)?,
148 })
149 }
150
151 pub(crate) fn entries(&self) -> &[(ConsumerId, AbsoluteBits)] {
152 &self.entries
153 }
154}
155
156#[allow(clippy::len_without_is_empty, clippy::new_without_default)]
157impl Assignments {
158 pub fn new() -> Self {
159 Self {
160 entries: Vec::new(),
161 }
162 }
163
164 pub fn len(&self) -> usize {
165 self.entries.len()
166 }
167
168 pub fn get(&self, id: ConsumerId) -> Option<ExprId> {
169 get_entry(self.entries(), id).copied()
170 }
171
172 pub fn insert(&mut self, id: ConsumerId, expr: ExprId) -> Result<(), InsertError> {
173 insert_entry(
174 &mut self.entries,
175 id,
176 expr,
177 StorageResource::AssignmentEntries,
178 id.get(),
179 )
180 }
181
182 pub fn set(&mut self, id: ConsumerId, expr: ExprId) -> Result<(), InsertError> {
183 set_entry(
184 &mut self.entries,
185 id,
186 expr,
187 StorageResource::AssignmentEntries,
188 id.get(),
189 )
190 }
191
192 pub fn try_clone(&self) -> Result<Self, InsertError> {
193 Ok(Self {
194 entries: try_clone_copy_entries(&self.entries, StorageResource::AssignmentEntries)?,
195 })
196 }
197
198 pub(crate) fn entries(&self) -> &[(ConsumerId, ExprId)] {
199 &self.entries
200 }
201}
202
203#[allow(clippy::len_without_is_empty, clippy::new_without_default)]
204impl EvaluationCache {
205 pub(crate) fn new() -> Self {
206 Self {
207 entries: Vec::new(),
208 }
209 }
210
211 pub fn len(&self) -> usize {
212 self.entries.len()
213 }
214
215 pub fn get(&self, id: ExprId) -> Option<&Result<ExactValue, EvalError>> {
216 get_entry(&self.entries, id)
217 }
218
219 pub(crate) fn get_mut(&mut self, id: ExprId) -> Option<&mut Result<ExactValue, EvalError>> {
220 self.entries
221 .binary_search_by(|(candidate, _)| candidate.cmp(&id))
222 .ok()
223 .map(|index| &mut self.entries[index].1)
224 }
225
226 pub(crate) fn insert(
227 &mut self,
228 id: ExprId,
229 value: Result<ExactValue, EvalError>,
230 ) -> Result<(), StorageError> {
231 let index = match find_key(&self.entries, &id) {
232 Ok(_) => return Ok(()),
233 Err(index) => index,
234 };
235 let required = required_elements(self.entries.len(), StorageResource::EvaluationEntries)?;
236 reserve_entries(
237 &mut self.entries,
238 required,
239 StorageResource::EvaluationEntries,
240 )?;
241 self.entries.insert(index, (id, value));
242 Ok(())
243 }
244}
245
246#[allow(clippy::len_without_is_empty)]
247impl IsolationCache {
248 pub(crate) fn new() -> Self {
249 Self {
250 entries: Vec::new(),
251 }
252 }
253
254 pub fn len(&self) -> usize {
255 self.entries.len()
256 }
257
258 pub fn get(&self, id: ExprId, bits: AbsoluteBits) -> Option<&IsolatingInterval> {
259 get_entry(&self.entries, (id, bits))
260 }
261
262 pub(crate) fn insert(
263 &mut self,
264 id: ExprId,
265 bits: AbsoluteBits,
266 interval: IsolatingInterval,
267 ) -> Result<(), StorageError> {
268 insert_cache_entry(
269 &mut self.entries,
270 (id, bits),
271 interval,
272 StorageResource::IsolationEntries,
273 )
274 }
275}
276
277#[allow(clippy::len_without_is_empty)]
278impl ResolvedValues {
279 pub(crate) fn new() -> Self {
280 Self {
281 entries: Vec::new(),
282 }
283 }
284
285 pub fn len(&self) -> usize {
286 self.entries.len()
287 }
288
289 pub fn get(&self, id: ConsumerId) -> Option<&Result<CertifiedF64, ResolveError>> {
290 get_entry(&self.entries, id)
291 }
292
293 pub(crate) fn insert(
294 &mut self,
295 id: ConsumerId,
296 value: Result<CertifiedF64, ResolveError>,
297 ) -> Result<(), StorageError> {
298 insert_cache_entry(
299 &mut self.entries,
300 id,
301 value,
302 StorageResource::ResolvedEntries,
303 )
304 }
305}
306
307fn insert_cache_entry<K: Ord, V>(
308 entries: &mut Vec<(K, V)>,
309 key: K,
310 value: V,
311 resource: StorageResource,
312) -> Result<(), StorageError> {
313 let index = match find_key(entries, &key) {
314 Ok(_) => return Ok(()),
315 Err(index) => index,
316 };
317 let required = required_elements(entries.len(), resource)?;
318 reserve_entries(entries, required, resource)?;
319 entries.insert(index, (key, value));
320 Ok(())
321}
322
323fn find_key<K: Ord, V>(entries: &[(K, V)], key: &K) -> Result<usize, usize> {
324 entries.binary_search_by(|(candidate, _)| candidate.cmp(key))
325}
326
327fn get_entry<K: Ord, V>(entries: &[(K, V)], key: K) -> Option<&V> {
328 find_key(entries, &key).ok().map(|index| &entries[index].1)
329}
330
331fn insert_entry<K: Ord, V>(
332 entries: &mut Vec<(K, V)>,
333 key: K,
334 value: V,
335 resource: StorageResource,
336 id: u32,
337) -> Result<(), InsertError> {
338 let index = match find_key(entries, &key) {
339 Ok(_) => return Err(InsertError::DuplicateId { resource, id }),
340 Err(index) => index,
341 };
342 let required = required_elements(entries.len(), resource)?;
343 reserve_entries(entries, required, resource)?;
344 entries.insert(index, (key, value));
345 Ok(())
346}
347
348fn set_entry<K: Ord, V>(
349 entries: &mut Vec<(K, V)>,
350 key: K,
351 value: V,
352 resource: StorageResource,
353 id: u32,
354) -> Result<(), InsertError> {
355 match find_key(entries, &key) {
356 Ok(index) => {
357 entries[index].1 = value;
358 Ok(())
359 }
360 Err(_) => insert_entry(entries, key, value, resource, id),
361 }
362}
363
364fn try_clone_copy_entries<K: Copy, V: Copy>(
365 source: &[(K, V)],
366 resource: StorageResource,
367) -> Result<Vec<(K, V)>, InsertError> {
368 let mut entries = Vec::new();
369 reserve_entries(&mut entries, source.len(), resource)?;
370 entries.extend_from_slice(source);
371 Ok(entries)
372}
373
374pub(crate) fn required_elements(
375 current: usize,
376 resource: StorageResource,
377) -> Result<usize, StorageError> {
378 current
379 .checked_add(1)
380 .ok_or(StorageError::CapacityOverflow { resource })
381}
382
383pub(crate) fn reserve_entries<T>(
384 entries: &mut Vec<T>,
385 total_required: usize,
386 resource: StorageResource,
387) -> Result<(), StorageError> {
388 #[cfg(test)]
389 if let Some(error) = injected_failure(resource, total_required) {
390 return Err(error);
391 }
392
393 let maximum = if size_of::<T>() == 0 {
394 usize::MAX
395 } else {
396 (isize::MAX as usize) / size_of::<T>()
397 };
398 if total_required > maximum {
399 return Err(StorageError::CapacityOverflow { resource });
400 }
401 let additional = total_required
402 .checked_sub(entries.len())
403 .ok_or(StorageError::CapacityOverflow { resource })?;
404 entries
405 .try_reserve(additional)
406 .map_err(|_| StorageError::AllocationFailure {
407 resource,
408 requested_elements: total_required,
409 })
410}
411
412#[cfg(test)]
413#[derive(Clone, Copy)]
414pub(crate) enum InjectedFailure {
415 Capacity,
416 Allocation,
417}
418
419#[cfg(test)]
420std::thread_local! {
421 static INJECTED_FAILURE: core::cell::Cell<Option<(StorageResource, InjectedFailure)>> = const { core::cell::Cell::new(None) };
422}
423
424#[cfg(test)]
425fn injected_failure(resource: StorageResource, requested_elements: usize) -> Option<StorageError> {
426 INJECTED_FAILURE.with(|configured| {
427 let error = match configured.get() {
428 Some((expected, InjectedFailure::Capacity)) if expected == resource => {
429 Some(StorageError::CapacityOverflow { resource })
430 }
431 Some((expected, InjectedFailure::Allocation)) if expected == resource => {
432 Some(StorageError::AllocationFailure {
433 resource,
434 requested_elements,
435 })
436 }
437 _ => None,
438 };
439 if error.is_some() {
440 configured.set(None);
441 }
442 error
443 })
444}
445
446#[cfg(test)]
447pub(crate) fn with_injected_failure<R>(
448 resource: StorageResource,
449 failure: InjectedFailure,
450 operation: impl FnOnce() -> R,
451) -> R {
452 INJECTED_FAILURE.with(|configured| configured.set(Some((resource, failure))));
453 let result = operation();
454 INJECTED_FAILURE.with(|configured| configured.set(None));
455 result
456}
457
458#[cfg(test)]
459mod tests {
460 use alloc::vec;
461 use alloc::vec::Vec;
462
463 use neco_algnum::RealAlgebraic;
464 use neco_formsum::FormSum;
465 use neco_monomial::{Monomial, MonomialErrorKind};
466
467 use super::{
468 required_elements, reserve_entries, with_injected_failure, InjectedFailure, StorageResource,
469 };
470 use crate::value::{with_clone_failure, CloneContact};
471 use crate::{
472 AbsoluteBits, Assignments, AtomId, AtomStore, ConsumerId, EvalError, ExactValue, ExprGraph,
473 ExprNode, GraphError, InsertError, PrecisionRequirements, ResolveError, Resolver,
474 StorageError,
475 };
476
477 const RESOURCES: [StorageResource; 7] = [
478 StorageResource::GraphNodes,
479 StorageResource::AtomEntries,
480 StorageResource::PrecisionEntries,
481 StorageResource::AssignmentEntries,
482 StorageResource::EvaluationEntries,
483 StorageResource::IsolationEntries,
484 StorageResource::ResolvedEntries,
485 ];
486
487 #[test]
488 fn required_total_rejects_capacity_overflow() {
489 for resource in RESOURCES {
490 assert_eq!(
491 required_elements(usize::MAX, resource),
492 Err(StorageError::CapacityOverflow { resource })
493 );
494 }
495 }
496
497 #[test]
498 fn allocation_failure_reports_total_and_preserves_entries() {
499 let mut entries = vec![10_u32];
500 let result = with_injected_failure(
501 StorageResource::PrecisionEntries,
502 InjectedFailure::Allocation,
503 || reserve_entries(&mut entries, 2, StorageResource::PrecisionEntries),
504 );
505 assert_eq!(
506 result,
507 Err(StorageError::AllocationFailure {
508 resource: StorageResource::PrecisionEntries,
509 requested_elements: 2,
510 })
511 );
512 assert_eq!(entries, [10]);
513 }
514
515 #[test]
516 fn capacity_injection_uses_production_reservation_path() {
517 let mut requirements = PrecisionRequirements::new();
518 let result = with_injected_failure(
519 StorageResource::PrecisionEntries,
520 InjectedFailure::Capacity,
521 || requirements.insert(ConsumerId::new(1), AbsoluteBits::new(20)),
522 );
523 assert_eq!(
524 result,
525 Err(InsertError::Storage(StorageError::CapacityOverflow {
526 resource: StorageResource::PrecisionEntries,
527 }))
528 );
529 assert_eq!(requirements.len(), 0);
530 }
531
532 #[test]
533 fn allocation_injection_identifies_every_resource() {
534 for resource in RESOURCES {
535 let mut entries = Vec::<u32>::new();
536 let result = with_injected_failure(resource, InjectedFailure::Allocation, || {
537 reserve_entries(&mut entries, 1, resource)
538 });
539 assert_eq!(
540 result,
541 Err(StorageError::AllocationFailure {
542 resource,
543 requested_elements: 1,
544 })
545 );
546 assert!(entries.is_empty());
547 }
548 }
549
550 #[test]
551 fn map_order_duplicate_and_set_are_deterministic() {
552 let mut left = PrecisionRequirements::new();
553 left.insert(ConsumerId::new(2), AbsoluteBits::new(20))
554 .unwrap();
555 left.insert(ConsumerId::new(1), AbsoluteBits::new(10))
556 .unwrap();
557
558 let mut right = PrecisionRequirements::new();
559 right
560 .insert(ConsumerId::new(1), AbsoluteBits::new(10))
561 .unwrap();
562 right
563 .insert(ConsumerId::new(2), AbsoluteBits::new(20))
564 .unwrap();
565 assert_eq!(left, right);
566
567 assert_eq!(
568 left.insert(ConsumerId::new(1), AbsoluteBits::new(99)),
569 Err(InsertError::DuplicateId {
570 resource: StorageResource::PrecisionEntries,
571 id: 1,
572 })
573 );
574 assert_eq!(left.get(ConsumerId::new(1)), Some(AbsoluteBits::new(10)));
575
576 left.set(ConsumerId::new(1), AbsoluteBits::new(30)).unwrap();
577 assert_eq!(left.get(ConsumerId::new(1)), Some(AbsoluteBits::new(30)));
578 assert_eq!(left.len(), 2);
579 }
580
581 #[test]
582 fn graph_storage_failure_is_wrapped_and_preserves_graph() {
583 let mut graph = ExprGraph::new();
584 let result = with_injected_failure(
585 StorageResource::GraphNodes,
586 InjectedFailure::Allocation,
587 || graph.push(ExprNode::Atom(AtomId::new(0))),
588 );
589 assert_eq!(
590 result,
591 Err(GraphError::Storage(StorageError::AllocationFailure {
592 resource: StorageResource::GraphNodes,
593 requested_elements: 1,
594 }))
595 );
596 assert!(graph.is_empty());
597 }
598
599 #[test]
600 fn every_input_map_wraps_allocation_failure_and_preserves_its_value() {
601 let mut atoms = AtomStore::new();
602 let atom_result = with_injected_failure(
603 StorageResource::AtomEntries,
604 InjectedFailure::Allocation,
605 || atoms.insert(AtomId::new(4), ExactValue::Monomial(Monomial::one())),
606 );
607 assert_eq!(
608 atom_result,
609 Err(InsertError::Storage(StorageError::AllocationFailure {
610 resource: StorageResource::AtomEntries,
611 requested_elements: 1,
612 }))
613 );
614 assert_eq!(atoms.len(), 0);
615
616 let mut requirements = PrecisionRequirements::new();
617 let precision_result = with_injected_failure(
618 StorageResource::PrecisionEntries,
619 InjectedFailure::Allocation,
620 || requirements.insert(ConsumerId::new(4), AbsoluteBits::new(20)),
621 );
622 assert_eq!(
623 precision_result,
624 Err(InsertError::Storage(StorageError::AllocationFailure {
625 resource: StorageResource::PrecisionEntries,
626 requested_elements: 1,
627 }))
628 );
629 assert_eq!(requirements.len(), 0);
630
631 let mut assignments = Assignments::new();
632 let assignment_result = with_injected_failure(
633 StorageResource::AssignmentEntries,
634 InjectedFailure::Allocation,
635 || assignments.insert(ConsumerId::new(4), crate::ExprId::new(0)),
636 );
637 assert_eq!(
638 assignment_result,
639 Err(InsertError::Storage(StorageError::AllocationFailure {
640 resource: StorageResource::AssignmentEntries,
641 requested_elements: 1,
642 }))
643 );
644 assert_eq!(assignments.len(), 0);
645 }
646
647 #[test]
648 fn atom_clone_failure_is_value_error_with_the_original_payload() {
649 let mut atoms = AtomStore::new();
650 atoms
651 .insert(AtomId::new(0), ExactValue::Monomial(Monomial::one()))
652 .unwrap();
653 assert_eq!(
654 with_clone_failure(CloneContact::Monomial, || atoms.try_clone()),
655 Err(InsertError::Value(EvalError::Monomial(
656 MonomialErrorKind::AllocationFailure {
657 requested_elements: 19,
658 }
659 )))
660 );
661 assert_eq!(atoms.len(), 1);
662 }
663
664 #[test]
665 fn evaluation_clone_failure_is_local_and_preserves_the_cache_entry() {
666 let mut graph = ExprGraph::new();
667 let failed = graph.push(ExprNode::Atom(AtomId::new(0))).unwrap();
668 let succeeded = graph.push(ExprNode::Atom(AtomId::new(1))).unwrap();
669 let mut atoms = AtomStore::new();
670 atoms
671 .insert(AtomId::new(0), ExactValue::Monomial(Monomial::one()))
672 .unwrap();
673 atoms
674 .insert(AtomId::new(1), ExactValue::FormSum(FormSum::one().unwrap()))
675 .unwrap();
676 let mut requirements = PrecisionRequirements::new();
677 let mut assignments = Assignments::new();
678 for (consumer, expression) in [
679 (ConsumerId::new(0), failed),
680 (ConsumerId::new(1), succeeded),
681 ] {
682 requirements.insert(consumer, AbsoluteBits::new(0)).unwrap();
683 assignments.insert(consumer, expression).unwrap();
684 }
685 let (evaluation, _, resolved) = with_clone_failure(CloneContact::Monomial, || {
686 Resolver::new().resolve_all(&graph, &atoms, &requirements, &assignments)
687 })
688 .unwrap();
689 let expected = EvalError::Monomial(MonomialErrorKind::AllocationFailure {
690 requested_elements: 19,
691 });
692 assert_eq!(evaluation.get(failed), Some(&Err(expected)));
693 assert_eq!(
694 resolved.get(ConsumerId::new(0)),
695 Some(&Err(ResolveError::Evaluation(EvalError::Monomial(
696 MonomialErrorKind::AllocationFailure {
697 requested_elements: 19,
698 }
699 ))))
700 );
701 assert!(resolved.get(ConsumerId::new(1)).unwrap().as_ref().is_ok());
702 }
703
704 #[test]
705 fn resolver_reports_evaluation_and_result_storage_failures_globally() {
706 let mut graph = ExprGraph::new();
707 let expr = graph.push(ExprNode::Atom(AtomId::new(0))).unwrap();
708 let mut atoms = AtomStore::new();
709 atoms
710 .insert(AtomId::new(0), ExactValue::Monomial(Monomial::one()))
711 .unwrap();
712 let mut requirements = PrecisionRequirements::new();
713 requirements
714 .insert(ConsumerId::new(0), AbsoluteBits::new(0))
715 .unwrap();
716 let mut assignments = Assignments::new();
717 assignments.insert(ConsumerId::new(0), expr).unwrap();
718
719 for resource in [
720 StorageResource::EvaluationEntries,
721 StorageResource::ResolvedEntries,
722 ] {
723 let result = with_injected_failure(resource, InjectedFailure::Allocation, || {
724 Resolver::new().resolve_all(&graph, &atoms, &requirements, &assignments)
725 });
726 assert_eq!(
727 result,
728 Err(ResolveError::Storage(StorageError::AllocationFailure {
729 resource,
730 requested_elements: 1,
731 }))
732 );
733 }
734 }
735
736 #[test]
737 fn resolver_reports_isolation_storage_failure_globally() {
738 let form = FormSum::one().unwrap();
739 let mut graph = ExprGraph::new();
740 let expr = graph.push(ExprNode::Atom(AtomId::new(0))).unwrap();
741 let mut atoms = AtomStore::new();
742 atoms
743 .insert(
744 AtomId::new(0),
745 ExactValue::Algebraic(RealAlgebraic::from_form_sum(&form).unwrap()),
746 )
747 .unwrap();
748 let mut requirements = PrecisionRequirements::new();
749 requirements
750 .insert(ConsumerId::new(0), AbsoluteBits::new(0))
751 .unwrap();
752 let mut assignments = Assignments::new();
753 assignments.insert(ConsumerId::new(0), expr).unwrap();
754
755 let result = with_injected_failure(
756 StorageResource::IsolationEntries,
757 InjectedFailure::Allocation,
758 || Resolver::new().resolve_all(&graph, &atoms, &requirements, &assignments),
759 );
760 assert_eq!(
761 result,
762 Err(ResolveError::Storage(StorageError::AllocationFailure {
763 resource: StorageResource::IsolationEntries,
764 requested_elements: 1,
765 }))
766 );
767 }
768}