1use std::collections::HashMap;
4use std::path::PathBuf;
5use std::sync::Arc;
6
7use dive_core::frontier_codec::FrontierCodec;
8use dive_core::{Error, Handle, Heap};
9use dive_store::spill::{MAX_RECORD_BYTES, OrderedFrontier, SpillError};
10
11#[derive(Clone, Debug, Default)]
13pub struct Storage {
14 pub exact: bool,
16 pub predecessor_memory_bytes: Option<usize>,
18 pub predecessor_directory: Option<PathBuf>,
20 pub frontier_memory_bytes: Option<usize>,
22 pub frontier_directory: Option<PathBuf>,
24 pub candidate_memory_bytes: Option<usize>,
27 pub candidate_directory: Option<PathBuf>,
29 pub store_compact_bytes: Option<usize>,
32 pub store_compact_default: bool,
36 pub seen_disk: Option<DiskOptions>,
38 #[cfg(test)]
41 pub collide_keys: Option<u64>,
42}
43
44#[derive(Clone, Debug, Default)]
46pub struct DiskOptions {
47 pub limits: dive_store::seen::Limits,
49 pub directory: Option<PathBuf>,
51}
52
53#[derive(Clone, Debug)]
55pub struct DiskFailure {
56 pub phase: &'static str,
58 pub error: dive_store::seen::SeenError,
60 pub generated: u64,
62 pub predecessor: Option<u64>,
64 pub successor_ordinal: u64,
66}
67
68#[derive(Clone, Debug)]
70pub struct DiskUsage {
71 pub limits: dive_store::seen::Limits,
73 pub admitted_keys: u64,
75 pub before_cleanup: Option<dive_store::seen::Stats>,
77 pub after_cleanup: Option<dive_store::seen::Stats>,
79 pub first_failure: Option<DiskFailure>,
81 pub deciding_event_before_failure: Option<crate::Verdict>,
83 pub audit_completed: bool,
85}
86
87pub(crate) struct Disk {
88 set: dive_store::seen::DiskSeen,
89 pub(crate) usage: DiskUsage,
90}
91
92impl Disk {
93 pub(crate) fn new(
94 exact: bool,
95 options: &DiskOptions,
96 ) -> Result<Self, dive_store::seen::SeenError> {
97 let mode = if exact {
98 dive_store::StoreMode::Exact
99 } else {
100 dive_store::StoreMode::Fingerprint
101 };
102 let parent = options.directory.clone().unwrap_or_else(std::env::temp_dir);
103 Ok(Self {
104 set: dive_store::seen::DiskSeen::create(mode, &parent, options.limits)?,
105 usage: DiskUsage {
106 limits: options.limits,
107 admitted_keys: 0,
108 before_cleanup: None,
109 after_cleanup: None,
110 first_failure: None,
111 deciding_event_before_failure: None,
112 audit_completed: false,
113 },
114 })
115 }
116
117 #[allow(
118 clippy::too_many_arguments,
119 reason = "one positioned fallible membership operation over an actual canonical row"
120 )]
121 pub(crate) fn operation(
122 &mut self,
123 exact: bool,
124 key: u64,
125 row: &[Handle],
126 heap: &Heap,
127 insert: bool,
128 position: (&'static str, u64, Option<u64>, u64),
129 poll: &(dyn Fn() -> bool + Sync),
130 ) -> Result<bool, Error> {
131 use dive_core::key::KeyError;
132 use dive_store::seen::{InsertOutcome, Key, Operation, SeenError};
133 let bytes = if exact {
134 match dive_core::key::canonical(heap, row, self.usage.limits.key_bytes, &|| !poll()) {
135 Ok(bytes) => bytes,
136 Err(KeyError::Interrupted) => return Err(Error::stop()),
137 Err(KeyError::Unsupported(feature)) => return Err(Error::unsupported(feature)),
138 Err(KeyError::Internal(message)) => return Err(Error::internal(message)),
139 Err(KeyError::Limit(message)) => {
140 let error = SeenError {
141 operation: Operation::Admission,
142 message,
143 cleanup_failure: None,
144 };
145 self.record(position, error.clone());
146 return Err(Error::internal(error.to_string()));
147 }
148 }
149 } else {
150 Vec::new()
151 };
152 let key = if exact {
153 Key::Exact(&bytes)
154 } else {
155 Key::Fingerprint(super::Seen::fix(key))
156 };
157 let result = if insert {
158 self.set
159 .insert(key)
160 .map(|outcome| outcome == InsertOutcome::Inserted)
161 } else {
162 self.set.contains(key)
163 };
164 self.usage.admitted_keys = self.set.stats().physical_entries;
165 result.map_err(|error| {
166 self.record(position, error.clone());
167 Error::internal(error.to_string())
168 })
169 }
170
171 fn record(
172 &mut self,
173 position: (&'static str, u64, Option<u64>, u64),
174 error: dive_store::seen::SeenError,
175 ) {
176 self.usage.first_failure.get_or_insert(DiskFailure {
177 phase: position.0,
178 error,
179 generated: position.1,
180 predecessor: position.2,
181 successor_ordinal: position.3,
182 });
183 }
184
185 pub(crate) fn finish(
186 &mut self,
187 validate: bool,
188 poll: &(dyn Fn() -> bool + Sync),
189 deciding: crate::Verdict,
190 ) -> bool {
191 self.usage.before_cleanup = Some(self.set.stats());
192 let result = self.set.close_controlled(validate, &|| !poll());
193 self.usage.after_cleanup = Some(self.set.stats());
194 match result {
195 Ok((_, complete)) => {
196 self.usage.audit_completed = complete;
197 !validate || complete
198 }
199 Err(error) => {
200 self.usage.deciding_event_before_failure = Some(deciding);
201 if let Some(first) = &mut self.usage.first_failure {
202 if first.error.operation == error.operation
203 && first.error.message == error.message
204 {
205 first.error.cleanup_failure = first
206 .error
207 .cleanup_failure
208 .clone()
209 .or(error.cleanup_failure);
210 } else {
211 first
212 .error
213 .cleanup_failure
214 .get_or_insert_with(|| error.to_string());
215 }
216 } else {
217 self.record(("Cleanup", 0, None, 0), error);
218 }
219 false
220 }
221 }
222 }
223}
224
225#[derive(Clone, Debug, Default)]
227pub struct Usage {
228 pub reclamation: ReclamationUsage,
230 pub candidates: CandidateUsage,
232 pub seen: Option<DiskUsage>,
234 pub exact_states: usize,
236 pub predecessor: dive_store::predecessor::Usage,
238 pub predecessor_failures: Vec<String>,
240 pub predecessor_deciding_event: Option<String>,
242 pub predecessor_cleanup_completed: bool,
244 pub frontier: FrontierUsage,
246}
247
248#[derive(Clone, Debug, Default)]
250pub struct ReclamationUsage {
251 pub failures: Vec<String>,
253 pub trigger_bytes: Option<usize>,
255 pub default_trigger: bool,
257 pub skipped: Option<String>,
260 pub collections: u64,
262 pub reclaimed_nodes: u64,
264 pub peak_before_bytes: u64,
266 pub peak_after_bytes: u64,
268 pub peak_after_nodes: u64,
270}
271
272#[derive(Clone, Debug, Default)]
274pub struct CandidateUsage {
275 pub memory_bytes_per_worker: Option<usize>,
277 pub peak_retained_bytes: u64,
279 pub retained_bytes: u64,
281 pub peak_origin_index_bytes: u64,
283 pub origin_index_bytes: u64,
285 pub spilled_bytes: u64,
287 pub failures: Vec<String>,
289 pub deciding_event_before_failure: Option<String>,
291}
292
293#[derive(Clone, Debug, Default)]
295pub struct FrontierUsage {
296 pub memory_bytes_per_queue: Option<usize>,
298 pub peak_retained_bytes: u64,
300 pub retained_bytes: u64,
302 pub spilled_bytes: u64,
304 pub failures: Vec<String>,
306 pub deciding_event_before_failure: Option<String>,
308}
309
310#[derive(Debug, Default)]
311pub(crate) struct Chunk {
312 pub(crate) identity: Vec<Handle>,
313 pub(crate) original: Vec<Handle>,
314 pub(crate) ids: Vec<u64>,
315}
316
317pub(crate) struct Frontiers {
319 codec: FrontierCodec,
320 variables: usize,
321 memory_bytes: usize,
322 directory: PathBuf,
323 next: OrderedFrontier,
324 current: Option<OrderedFrontier>,
325 next_first: Option<u64>,
326 current_first: Option<u64>,
327 pub(crate) usage: FrontierUsage,
328}
329
330impl Frontiers {
331 pub(crate) fn new(
332 store: &Arc<dive_core::Store>,
333 variables: usize,
334 options: &Storage,
335 ) -> Result<Self, Error> {
336 let memory_bytes = options.frontier_memory_bytes.unwrap_or(0);
337 if variables
338 .checked_mul(16)
339 .and_then(|n| n.checked_add(24))
340 .is_none_or(|n| n > MAX_RECORD_BYTES)
341 {
342 return Err(Error::unsupported(
343 "native frontier row exceeds the encoded record limit",
344 ));
345 }
346 let directory = options
347 .frontier_directory
348 .clone()
349 .unwrap_or_else(std::env::temp_dir);
350 Ok(Self {
351 codec: FrontierCodec::new(Arc::clone(store), variables)?,
352 variables,
353 memory_bytes,
354 next: OrderedFrontier::new(memory_bytes, &directory),
355 directory,
356 current: None,
357 next_first: None,
358 current_first: None,
359 usage: FrontierUsage {
360 memory_bytes_per_queue: Some(memory_bytes),
361 ..FrontierUsage::default()
362 },
363 })
364 }
365
366 pub(crate) fn next_len(&self) -> usize {
367 self.next.len()
368 }
369
370 pub(crate) fn current_len(&self) -> usize {
371 self.current.as_ref().map_or(0, OrderedFrontier::len)
372 }
373
374 pub(crate) fn remap(
378 &mut self,
379 remap: &mut dive_core::store::compact::Remap,
380 poll: &(dyn Fn() -> bool + Sync),
381 ) -> Result<Self, Error> {
382 let mut fresh = Self::new(
383 remap.store(),
384 self.variables,
385 &Storage {
386 frontier_memory_bytes: Some(self.memory_bytes),
387 frontier_directory: Some(self.directory.clone()),
388 ..Storage::default()
389 },
390 )?;
391 let result = (|| {
392 for i in 0..self.next.len() {
393 if i.is_multiple_of(128) && poll() {
394 return Err(Error::stop());
395 }
396 let read = self.next.read(i);
397 let (id, bytes) = self.observe(read)?;
398 if self.next_first.and_then(|n| n.checked_add(i as u64)) != Some(id) {
399 return self.observe(Err(frontier_error("remap discovery position")));
400 }
401 let read = self.codec.decode(&bytes).map_err(frontier_error);
402 let mut rows = self.observe(read)?;
403 for h in rows.identity.iter_mut().chain(&mut rows.original) {
404 *h = remap.copy(*h, &|| !poll())?;
405 }
406 fresh.push(id, &rows.identity, &rows.original)?;
407 }
408 if !self.finish(true, poll) {
409 if self.usage.failures.is_empty() {
410 return Err(Error::stop());
411 }
412 return Err(Error::internal(self.usage.failures.join("; ")));
413 }
414 Ok(())
415 })();
416 if let Err(error) = result {
417 fresh.finish(false, poll);
418 self.usage.spilled_bytes += fresh.usage.spilled_bytes;
419 self.usage.peak_retained_bytes = self
420 .usage
421 .peak_retained_bytes
422 .max(fresh.usage.peak_retained_bytes);
423 self.usage.failures.extend(fresh.usage.failures);
424 return Err(error);
425 }
426 fresh.usage.spilled_bytes += self.usage.spilled_bytes;
427 fresh.usage.peak_retained_bytes = fresh
428 .usage
429 .peak_retained_bytes
430 .max(self.usage.peak_retained_bytes);
431 fresh.usage.failures.append(&mut self.usage.failures);
432 Ok(fresh)
433 }
434
435 fn observe<T>(&mut self, result: Result<T, SpillError>) -> Result<T, Error> {
436 result.map_err(|error| {
437 self.usage.failures.push(error.to_string());
438 Error::internal(error.to_string())
439 })
440 }
441
442 fn refresh(&mut self) {
443 let bytes = self.next.stats().retained_bytes.saturating_add(
444 self.current
445 .as_ref()
446 .map_or(0, |q| q.stats().retained_bytes),
447 );
448 self.usage.retained_bytes = bytes;
449 self.usage.peak_retained_bytes = self.usage.peak_retained_bytes.max(bytes);
450 }
451
452 pub(crate) fn push(
453 &mut self,
454 id: u64,
455 identity: &[Handle],
456 original: &[Handle],
457 ) -> Result<(), Error> {
458 let before = self.next.stats().spilled_bytes;
459 let result = (|| {
460 if self
461 .next_first
462 .is_some_and(|first| first.checked_add(self.next.len() as u64) != Some(id))
463 {
464 return Err(frontier_error("discovery IDs are not consecutive"));
465 }
466 let bytes = self
467 .codec
468 .encode(identity, original)
469 .map_err(frontier_error)?;
470 self.next.push(id, &bytes)
471 })();
472 self.next_first.get_or_insert(id);
473 self.usage.spilled_bytes = self
474 .usage
475 .spilled_bytes
476 .saturating_add(self.next.stats().spilled_bytes.saturating_sub(before));
477 self.refresh();
478 self.observe(result)
479 }
480
481 fn validate(
482 &self,
483 queue: &OrderedFrontier,
484 first: Option<u64>,
485 poll: &(dyn Fn() -> bool + Sync),
486 ) -> Result<bool, SpillError> {
487 for index in 0..queue.len() {
488 if index % 128 == 0 && poll() {
489 return Ok(false);
490 }
491 let (id, bytes) = queue.read(index)?;
492 if first.and_then(|n| n.checked_add(index as u64)) != Some(id) {
493 return Err(frontier_error(
494 "record discovery ID differs from its ordered position",
495 ));
496 }
497 self.codec.decode(&bytes).map_err(frontier_error)?;
498 }
499 Ok(true)
500 }
501
502 fn close_queue(
503 &mut self,
504 queue: &mut OrderedFrontier,
505 first: Option<u64>,
506 validate: bool,
507 poll: &(dyn Fn() -> bool + Sync),
508 ) -> Result<bool, Error> {
509 let checked = if validate {
510 self.validate(queue, first, poll)
511 } else {
512 Ok(true)
513 };
514 let closed = queue.close();
515 let check = self.observe(checked);
516 let close = self.observe(closed);
517 check.and_then(|complete| close.map(|()| complete))
518 }
519
520 pub(crate) fn advance(&mut self, poll: &(dyn Fn() -> bool + Sync)) -> Result<bool, Error> {
521 if let Some(mut old) = self.current.take()
522 && !self.close_queue(&mut old, self.current_first, true, poll)?
523 {
524 self.refresh();
525 return Ok(false);
526 }
527 let fresh = OrderedFrontier::new(self.memory_bytes, &self.directory);
528 self.current = Some(std::mem::replace(&mut self.next, fresh));
529 self.current_first = self.next_first.take();
530 self.refresh();
531 Ok(true)
532 }
533
534 pub(crate) fn chunk(
535 &mut self,
536 start: usize,
537 end: usize,
538 poll: &(dyn Fn() -> bool + Sync),
539 ) -> Result<Option<Chunk>, Error> {
540 let result = (|| {
541 let queue = self
542 .current
543 .as_ref()
544 .ok_or_else(|| frontier_error("missing current queue"))?;
545 let mut chunk = Chunk::default();
546 let handles = end
547 .checked_sub(start)
548 .and_then(|n| n.checked_mul(self.variables))
549 .ok_or_else(|| frontier_error("decoded chunk size overflow"))?;
550 chunk
551 .identity
552 .try_reserve_exact(handles)
553 .map_err(frontier_error)?;
554 chunk
555 .original
556 .try_reserve_exact(handles)
557 .map_err(frontier_error)?;
558 chunk
559 .ids
560 .try_reserve_exact(end - start)
561 .map_err(frontier_error)?;
562 for index in start..end {
563 if (index - start).is_multiple_of(128) && poll() {
564 return Ok(None);
565 }
566 let (id, bytes) = queue.read(index)?;
567 if self.current_first.and_then(|n| n.checked_add(index as u64)) != Some(id) {
568 return Err(frontier_error(
569 "record discovery ID differs from its ordered position",
570 ));
571 }
572 let rows = self.codec.decode(&bytes).map_err(frontier_error)?;
573 chunk.identity.extend(rows.identity);
574 chunk.original.extend(rows.original);
575 chunk.ids.push(id);
576 }
577 Ok(Some(chunk))
578 })();
579 self.observe(result)
580 }
581
582 pub(crate) fn finish(&mut self, validate: bool, poll: &(dyn Fn() -> bool + Sync)) -> bool {
583 let mut complete = true;
584 if let Some(mut current) = self.current.take() {
585 complete &= self
586 .close_queue(&mut current, self.current_first, validate, poll)
587 .unwrap_or(false);
588 }
589 let mut next = std::mem::replace(
590 &mut self.next,
591 OrderedFrontier::new(self.memory_bytes, &self.directory),
592 );
593 complete &= self
594 .close_queue(&mut next, self.next_first, validate && complete, poll)
595 .unwrap_or(false);
596 self.refresh();
597 complete
598 }
599}
600
601fn frontier_error(cause: impl std::fmt::Display) -> SpillError {
602 SpillError {
603 code: "DIVE-S0200",
604 message: format!("native frontier: {cause}"),
605 }
606}
607
608#[derive(Clone, Copy, Debug, PartialEq, Eq)]
610pub(crate) enum Inserted {
611 New,
613 Seen(Option<u64>),
616}
617
618impl Inserted {
619 pub(crate) const fn is_new(self) -> bool {
620 matches!(self, Self::New)
621 }
622}
623
624type Bucket<T> = Vec<(T, u64)>;
626
627#[derive(Debug, Default)]
632pub(crate) struct Exact {
633 rows: HashMap<u64, Bucket<Vec<Handle>>>,
634 encoded: Option<HashMap<u64, Bucket<Vec<u8>>>>,
635 len: usize,
636}
637
638impl Exact {
639 pub(crate) fn detached() -> Self {
640 Self {
641 encoded: Some(HashMap::new()),
642 ..Self::default()
643 }
644 }
645
646 pub(crate) const fn is_detached(&self) -> bool {
647 self.encoded.is_some()
648 }
649
650 pub(crate) fn lookup_controlled(
652 &self,
653 key: u64,
654 row: &[Handle],
655 heap: &Heap,
656 poll: &(dyn Fn() -> bool + Sync),
657 ) -> Result<Option<u64>, Error> {
658 let Some(encoded) = &self.encoded else {
659 return Ok(self.lookup(key, row, heap));
660 };
661 let bytes = detached_key(heap, row, poll)?;
662 Ok(encoded.get(&key).and_then(|bucket| {
663 bucket
664 .iter()
665 .find(|(kept, _)| *kept == bytes)
666 .map(|&(_, id)| id)
667 }))
668 }
669
670 pub(crate) fn contains_controlled(
671 &self,
672 key: u64,
673 row: &[Handle],
674 heap: &Heap,
675 poll: &(dyn Fn() -> bool + Sync),
676 ) -> Result<bool, Error> {
677 Ok(self.lookup_controlled(key, row, heap, poll)?.is_some())
678 }
679
680 pub(crate) fn insert_controlled(
682 &mut self,
683 key: u64,
684 row: &[Handle],
685 heap: &Heap,
686 id: u64,
687 poll: &(dyn Fn() -> bool + Sync),
688 ) -> Result<Inserted, Error> {
689 let Some(encoded) = &mut self.encoded else {
690 return self.insert(key, row, heap, id);
691 };
692 let bytes = detached_key(heap, row, poll)?;
693 if let Some(&(_, seen)) = encoded
694 .get(&key)
695 .and_then(|bucket| bucket.iter().find(|(kept, _)| *kept == bytes))
696 {
697 return Ok(Inserted::Seen(Some(seen)));
698 }
699 encoded
700 .try_reserve(1)
701 .map_err(|_| Error::internal("DIVE-S0203: detached exact state index allocation"))?;
702 let bucket = encoded.entry(key).or_default();
703 bucket.try_reserve(1).map_err(|_| {
704 Error::internal("DIVE-S0203: detached exact collision bucket allocation")
705 })?;
706 bucket.push((bytes, id));
707 self.len += 1;
708 Ok(Inserted::New)
709 }
710
711 pub(crate) fn contains_encoded(
712 &self,
713 key: u64,
714 bytes: &[u8],
715 heap: &Heap,
716 limit: usize,
717 poll: &(dyn Fn() -> bool + Sync),
718 ) -> Result<bool, Error> {
719 let Some(rows) = self.rows.get(&key) else {
720 return Ok(false);
721 };
722 for (row, _) in rows {
723 let encoded =
724 dive_core::key::canonical(heap, row, limit, &|| !poll()).map_err(|error| {
725 if error == dive_core::key::KeyError::Interrupted {
726 Error::stop()
727 } else {
728 Error::internal(format!("DIVE-S0500: distributed exact key: {error:?}"))
729 }
730 })?;
731 if encoded == bytes {
732 return Ok(true);
733 }
734 }
735 Ok(false)
736 }
737 pub(crate) const fn len(&self) -> usize {
738 self.len
739 }
740
741 pub(crate) fn lookup(&self, key: u64, row: &[Handle], heap: &Heap) -> Option<u64> {
743 self.rows.get(&key).and_then(|bucket| {
744 bucket
745 .iter()
746 .find(|(kept, _)| {
747 kept.len() == row.len() && kept.iter().zip(row).all(|(&a, &b)| heap.eq(a, b))
748 })
749 .map(|&(_, id)| id)
750 })
751 }
752
753 pub(crate) fn insert(
755 &mut self,
756 key: u64,
757 row: &[Handle],
758 heap: &Heap,
759 id: u64,
760 ) -> Result<Inserted, Error> {
761 if let Some(seen) = self.lookup(key, row, heap) {
762 return Ok(Inserted::Seen(Some(seen)));
763 }
764 self.rows
765 .try_reserve(1)
766 .map_err(|_| Error::unsupported("exact state index allocation"))?;
767 let mut kept = Vec::new();
768 kept.try_reserve_exact(row.len())
769 .map_err(|_| Error::unsupported("exact state row allocation"))?;
770 kept.extend_from_slice(row);
771 let bucket = self.rows.entry(key).or_default();
772 bucket
773 .try_reserve(1)
774 .map_err(|_| Error::unsupported("exact state collision bucket allocation"))?;
775 bucket.push((kept, id));
776 self.len += 1;
777 Ok(Inserted::New)
778 }
779}
780
781fn detached_key(
782 heap: &Heap,
783 row: &[Handle],
784 poll: &(dyn Fn() -> bool + Sync),
785) -> Result<Vec<u8>, Error> {
786 use dive_core::key::KeyError;
787 dive_core::key::canonical(heap, row, usize::MAX, &|| !poll()).map_err(|error| match error {
788 KeyError::Interrupted => Error::stop(),
789 KeyError::Internal(message) => Error::internal(message),
790 KeyError::Unsupported(message) => Error::unsupported(message),
791 KeyError::Limit(message) => Error::internal(format!("DIVE-S0203: {message}")),
792 })
793}
794
795#[cfg(test)]
796#[allow(clippy::unwrap_used, reason = "exact collision controls")]
797mod tests {
798 use std::fs;
799 use std::io::{Seek, SeekFrom, Write};
800 use std::sync::Arc;
801
802 use dive_core::Store;
803
804 use super::*;
805
806 fn directory() -> PathBuf {
807 static NEXT_DIRECTORY: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
808 let path = std::env::temp_dir().join(format!(
809 "dive-native-frontier-{}-{}",
810 std::process::id(),
811 NEXT_DIRECTORY.fetch_add(1, std::sync::atomic::Ordering::Relaxed)
812 ));
813 fs::create_dir(&path).unwrap();
814 path
815 }
816
817 fn queues(path: &std::path::Path) -> Frontiers {
818 let mut queues = Frontiers::new(
819 &Arc::new(Store::new(true)),
820 1,
821 &Storage {
822 frontier_memory_bytes: Some(0),
823 frontier_directory: Some(path.to_path_buf()),
824 ..Storage::default()
825 },
826 )
827 .unwrap();
828 for id in 0_u32..3 {
829 let value = Handle::int(i64::from(id)).unwrap();
830 queues.push(u64::from(id), &[value], &[value]).unwrap();
831 }
832 queues
833 }
834
835 #[test]
836 fn remapping_cancels_and_reports_corruption_write_and_cleanup_failures() {
837 use std::sync::atomic::{AtomicUsize, Ordering};
838 for fault in ["cancel", "corrupt", "write", "cleanup"] {
839 let path = directory();
840 let store = Arc::new(Store::new(true));
841 let permanent =
842 dive_core::store::compact::Permanent::capture(&store, &|| true).unwrap();
843 let mut remap = permanent.begin(&store, &|| true).unwrap();
844 let mut queues = Frontiers::new(
845 &store,
846 1,
847 &Storage {
848 frontier_memory_bytes: Some(0),
849 frontier_directory: Some(path.clone()),
850 ..Storage::default()
851 },
852 )
853 .unwrap();
854 for id in 0_u32..4 {
855 let h = Handle::int(i64::from(id)).unwrap();
856 queues.push(u64::from(id), &[h], &[h]).unwrap();
857 }
858 let owned = queues.next.disk_directory().unwrap().to_path_buf();
859 if fault == "write" {
860 let blocked = path.join("file");
861 fs::write(&blocked, b"not a directory").unwrap();
862 queues.directory = blocked;
863 }
864 let calls = AtomicUsize::new(0);
865 let poll = || {
866 if calls.fetch_add(1, Ordering::Relaxed) == 3 {
869 match fault {
870 "cancel" => return true,
871 "corrupt" => {
872 let mut file = fs::OpenOptions::new()
873 .write(true)
874 .open(owned.join("states"))
875 .unwrap();
876 file.seek(SeekFrom::End(-1)).unwrap();
877 file.write_all(&[255]).unwrap();
878 }
879 "cleanup" => {
880 fs::rename(&owned, path.join("moved")).unwrap();
881 fs::write(&owned, b"blocks cleanup").unwrap();
882 }
883 _ => {}
884 }
885 }
886 false
887 };
888 let result = queues.remap(&mut remap, &poll);
889 assert!(result.is_err(), "{fault}");
890 if fault == "cancel" {
891 assert_eq!(result.err().unwrap().kind(), dive_core::ErrorKind::Stop);
892 assert_eq!(queues.usage.failures, [] as [String; 0]);
893 } else {
894 assert!(!queues.usage.failures.is_empty(), "{fault}");
895 }
896 queues.finish(false, &|| false);
897 if fault == "cleanup" {
898 assert!(queues.usage.failures.iter().any(|s| s.contains("cleanup")));
899 }
900 assert_eq!(queues.usage.retained_bytes, 0);
901 fs::remove_dir_all(path).unwrap();
902 }
903 }
904
905 #[test]
906 fn detached_exact_keys_survive_replacement_and_resolve_complete_collisions() {
907 let store = Arc::new(Store::new(true));
908 let permanent = dive_core::store::compact::Permanent::capture(&store, &|| true).unwrap();
909 let mut heap = Heap::new(Arc::clone(&store), true, false);
910 let one = Handle::int(1).unwrap();
911 let two = Handle::int(2).unwrap();
912 let a = heap.tuple_literal(&[one, two]);
913 let a = heap.intern(a).unwrap();
914 let b = heap.tuple_literal(&[two, one]);
915 let b = heap.intern(b).unwrap();
916 let mut exact = Exact::detached();
917 assert_eq!(
918 exact
919 .insert_controlled(0, &[a], &heap, 10, &|| false)
920 .unwrap(),
921 Inserted::New
922 );
923 assert_eq!(
924 exact
925 .insert_controlled(0, &[b], &heap, 11, &|| false)
926 .unwrap(),
927 Inserted::New
928 );
929 let mut remap = permanent.begin(&store, &|| true).unwrap();
930 let mapped = remap.copy(b, &|| true).unwrap();
931 let replacement = Heap::new(Arc::clone(remap.store()), true, false);
932 assert!(
933 exact
934 .contains_controlled(0, &[mapped], &replacement, &|| false)
935 .unwrap()
936 );
937 assert_eq!(
938 exact
939 .insert_controlled(0, &[mapped], &replacement, 12, &|| false)
940 .unwrap(),
941 Inserted::Seen(Some(11)),
942 "a detached collision resolves to the discovery id of its own identity"
943 );
944 assert_eq!(
945 exact
946 .lookup_controlled(0, &[mapped], &replacement, &|| false)
947 .unwrap(),
948 Some(11)
949 );
950 assert!(
951 exact.rows.is_empty(),
952 "detached keys must retain no old Store handles"
953 );
954 assert_eq!(exact.len(), 2);
955 }
956
957 #[test]
958 fn missing_current_file_and_unvisited_corruption_invalidate_storage() {
959 for missing in [false, true] {
960 let path = directory();
961 let mut queues = queues(&path);
962 queues.advance(&|| false).unwrap();
963 assert!(queues.chunk(0, 1, &|| false).unwrap().is_some());
964 let owned = queues
965 .current
966 .as_ref()
967 .unwrap()
968 .disk_directory()
969 .unwrap()
970 .to_path_buf();
971 if missing {
972 fs::remove_file(owned.join("states")).unwrap();
973 assert!(queues.chunk(1, 2, &|| false).is_err());
974 } else {
975 let mut file = fs::OpenOptions::new()
976 .write(true)
977 .open(owned.join("states"))
978 .unwrap();
979 file.seek(SeekFrom::End(-1)).unwrap();
980 file.write_all(&[255]).unwrap();
981 }
982 queues.finish(true, &|| false);
983 assert_ne!(queues.usage.failures, [] as [String; 0]);
984 assert!(!owned.exists());
985 assert_eq!(queues.usage.retained_bytes, 0);
986 fs::remove_dir(path).unwrap();
987 }
988 }
989
990 #[test]
991 fn already_stopped_cleanup_does_not_read_or_poll_unprocessed_records() {
992 let path = directory();
993 let mut queues = queues(&path);
994 queues.advance(&|| false).unwrap();
995 let owned = queues
996 .current
997 .as_ref()
998 .unwrap()
999 .disk_directory()
1000 .unwrap()
1001 .to_path_buf();
1002 fs::remove_file(owned.join("states")).unwrap();
1003 queues.finish(false, &|| true);
1004 assert_eq!(queues.usage.failures, [] as [String; 0]);
1005 assert!(!owned.exists());
1006 fs::remove_dir(path).unwrap();
1007 }
1008
1009 #[test]
1010 fn cleanup_failure_is_explicit_even_without_a_certifiable_ending() {
1011 let path = directory();
1012 let mut queues = queues(&path);
1013 let owned = queues.next.disk_directory().unwrap().to_path_buf();
1014 let moved = path.join("moved");
1015 fs::rename(&owned, &moved).unwrap();
1016 fs::write(&owned, b"file blocks directory cleanup").unwrap();
1017 queues.finish(false, &|| false);
1018 assert!(
1019 queues
1020 .usage
1021 .failures
1022 .iter()
1023 .any(|error| error.contains("cleanup"))
1024 );
1025 fs::remove_file(owned).unwrap();
1026 fs::remove_dir_all(path).unwrap();
1027 }
1028
1029 #[test]
1030 fn complete_hash_collision_preserves_distinct_rows_and_zero_key() {
1031 let mut heap = Heap::new(Arc::new(Store::new(true)), true, false);
1032 let mut seen = Exact::default();
1033 let one = Handle::int(1).unwrap();
1034 let two = Handle::int(2).unwrap();
1035 let a = heap.tuple(&[one, two]);
1036 let a = heap.intern(a).unwrap();
1037 let b = heap.tuple(&[two, one]);
1038 let b = heap.intern(b).unwrap();
1039 assert_eq!(seen.insert(0, &[a], &heap, 0).unwrap(), Inserted::New);
1040 assert_eq!(seen.insert(0, &[b], &heap, 1).unwrap(), Inserted::New);
1041 assert_eq!(
1042 seen.insert(0, &[a], &heap, 2).unwrap(),
1043 Inserted::Seen(Some(0))
1044 );
1045 assert_eq!(
1046 seen.insert(0, &[b], &heap, 2).unwrap(),
1047 Inserted::Seen(Some(1))
1048 );
1049 assert_eq!(seen.lookup(0, &[a], &heap), Some(0));
1050 assert_eq!(seen.lookup(0, &[b], &heap), Some(1));
1051 assert_eq!(seen.lookup(1, &[a], &heap), None);
1052 assert_eq!(seen.len, 2);
1053 }
1054
1055 #[test]
1056 fn exact_equality_ignores_literal_class_and_hashconsing_without_erasing_views() {
1057 for hashcons in [false, true] {
1058 let mut heap = Heap::new(Arc::new(Store::new(hashcons)), true, false);
1059 let one = Handle::int(1).unwrap();
1060 let two = Handle::int(2).unwrap();
1061 let tuple = heap.tuple_literal(&[one, two]);
1062 let original = heap.intern_exact(tuple).unwrap();
1063 let canonical_tuple = heap.intern(original).unwrap();
1064 let function = heap.fcn_sorted(&[one, two], &[one, two]);
1065 let canonical_function = heap.intern(function).unwrap();
1066 let mut seen = Exact::default();
1067 assert_eq!(
1068 seen.insert(7, &[canonical_tuple], &heap, 3).unwrap(),
1069 Inserted::New
1070 );
1071 assert_eq!(
1072 seen.insert(7, &[canonical_function], &heap, 4).unwrap(),
1073 Inserted::Seen(Some(3))
1074 );
1075 assert!(heap.view(original).is_tuple_literal());
1076 assert!(!heap.view(canonical_tuple).is_tuple_literal());
1077 assert!(!heap.view(canonical_function).is_tuple_literal());
1078 }
1079 }
1080}