Skip to main content

dive_explore/
storage.rs

1//! Opt-in native safety storage. Exact identities are separate from receiver history.
2
3use 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/// Storage policies for one native safety search. These do not bound total memory.
12#[derive(Clone, Debug, Default)]
13pub struct Storage {
14    /// Resolve state-key collisions using complete mathematical state identities.
15    pub exact: bool,
16    /// Resident predecessor-log capacity before transient spill.
17    pub predecessor_memory_bytes: Option<usize>,
18    /// Parent directory for private predecessor files.
19    pub predecessor_directory: Option<PathBuf>,
20    /// Resident encoded capacity, independently for current and next frontiers.
21    pub frontier_memory_bytes: Option<usize>,
22    /// Existing parent directory for private frontier files.
23    pub frontier_directory: Option<PathBuf>,
24    /// Resident encoded candidate bytes per worker; zero immediately spills.
25    /// Accepted Store values and active evaluator roots are outside this budget.
26    pub candidate_memory_bytes: Option<usize>,
27    /// Parent directory for private transient candidate files.
28    pub candidate_directory: Option<PathBuf>,
29    /// Completed-level trigger for rebuilding the Store from live roots.
30    /// Zero forces every boundary. This is not a hard memory limit.
31    pub store_compact_bytes: Option<usize>,
32    /// The trigger is the caller's default rather than an explicit request.
33    /// Reclamation that cannot run on this search is then skipped and recorded
34    /// instead of refusing the search; cancellation still stops it.
35    pub store_compact_default: bool,
36    /// Opt-in fallible disk membership; runs inline and does not bound values.
37    pub seen_disk: Option<DiskOptions>,
38    /// Test-only: replaces every state key with this value, so every state
39    /// collides and only exact identities can tell states apart.
40    #[cfg(test)]
41    pub collide_keys: Option<u64>,
42}
43
44/// Bounds and owned directory for native disk membership.
45#[derive(Clone, Debug, Default)]
46pub struct DiskOptions {
47    /// Existing disk-key workspace, entry and probe bounds.
48    pub limits: dive_store::seen::Limits,
49    /// Existing parent for private transient files; defaults to system temporary storage.
50    pub directory: Option<PathBuf>,
51}
52
53/// Ordered position at which disk membership first failed.
54#[derive(Clone, Debug)]
55pub struct DiskFailure {
56    /// Membership, insertion, replay or cleanup phase.
57    pub phase: &'static str,
58    /// First library failure, including a later cleanup failure.
59    pub error: dive_store::seen::SeenError,
60    /// Generated count at the original operation.
61    pub generated: u64,
62    /// Concrete source discovery ID, absent for Init.
63    pub predecessor: Option<u64>,
64    /// Emission ordinal within the source's ordered successors.
65    pub successor_ordinal: u64,
66}
67
68/// Actual disk-key storage facts. None of these measure retained state values.
69#[derive(Clone, Debug)]
70pub struct DiskUsage {
71    /// Resolved key and index bounds.
72    pub limits: dive_store::seen::Limits,
73    /// Successfully committed physical keys, including error-replay admissions.
74    pub admitted_keys: u64,
75    /// Facts before explicit cleanup.
76    pub before_cleanup: Option<dive_store::seen::Stats>,
77    /// Facts after cleanup, even when an original cause remains authoritative.
78    pub after_cleanup: Option<dive_store::seen::Stats>,
79    /// First failed operation and its original ordered position.
80    pub first_failure: Option<DiskFailure>,
81    /// Search event reached before a later audit or cleanup failure.
82    pub deciding_event_before_failure: Option<crate::Verdict>,
83    /// A complete retained-record audit finished under the actual run owner.
84    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/// Actual native safety storage facts. These describe components, not RSS.
226#[derive(Clone, Debug, Default)]
227pub struct Usage {
228    /// Completed-level persistent-value reclamation, independently of RSS.
229    pub reclamation: ReclamationUsage,
230    /// Encoded candidate payload and occurrence storage, not total memory.
231    pub candidates: CandidateUsage,
232    /// Opt-in disk membership and its first positioned failure.
233    pub seen: Option<DiskUsage>,
234    /// Exact mathematical identities retained by the collision index.
235    pub exact_states: usize,
236    /// Predecessor storage before explicit cleanup.
237    pub predecessor: dive_store::predecessor::Usage,
238    /// Actual predecessor storage failures.
239    pub predecessor_failures: Vec<String>,
240    /// Search event reached before predecessor storage prevented certification.
241    pub predecessor_deciding_event: Option<String>,
242    /// Explicit predecessor cleanup finished successfully.
243    pub predecessor_cleanup_completed: bool,
244    /// Actual encoded frontier component facts; decoded chunks and Store excluded.
245    pub frontier: FrontierUsage,
246}
247
248/// Persistent-value reclamation facts; live roots and fixed startup remain mandatory.
249#[derive(Clone, Debug, Default)]
250pub struct ReclamationUsage {
251    /// Actual reclamation/key workspace allocation failures.
252    pub failures: Vec<String>,
253    /// Requested measured-Store-byte trigger; zero forces every boundary.
254    pub trigger_bytes: Option<usize>,
255    /// The trigger came from the default policy rather than a request.
256    pub default_trigger: bool,
257    /// Why a default trigger stopped reclaiming; the search continued with the
258    /// resident Store unchanged.
259    pub skipped: Option<String>,
260    /// Completed replacement transactions.
261    pub collections: u64,
262    /// Cumulative values released from replaced Stores.
263    pub reclaimed_nodes: u64,
264    /// Largest measured Store snapshot before a completed transaction.
265    pub peak_before_bytes: u64,
266    /// Largest measured Store snapshot after a completed transaction.
267    pub peak_after_bytes: u64,
268    /// Largest number of nodes retained after a completed transaction.
269    pub peak_after_nodes: u64,
270}
271
272/// Actual candidate queue accounting, including occurrence metadata.
273#[derive(Clone, Debug, Default)]
274pub struct CandidateUsage {
275    /// Requested encoded resident bytes per worker's pending source queue.
276    pub memory_bytes_per_worker: Option<usize>,
277    /// Peak aggregate resident encoded queue capacity across workers.
278    pub peak_retained_bytes: u64,
279    /// Current resident encoded queue capacity after cleanup.
280    pub retained_bytes: u64,
281    /// Peak aggregate retained codec constructor-origin index capacity.
282    pub peak_origin_index_bytes: u64,
283    /// Current retained codec origin-index capacity after cleanup.
284    pub origin_index_bytes: u64,
285    /// Confirmed complete transient data and index bytes written.
286    pub spilled_bytes: u64,
287    /// Actual encoding, filesystem, decoding and cleanup failures.
288    pub failures: Vec<String>,
289    /// Search result reached before a storage failure prevented certification.
290    pub deciding_event_before_failure: Option<String>,
291}
292
293/// Encoded frontier accounting. This is neither RSS nor a total memory budget.
294#[derive(Clone, Debug, Default)]
295pub struct FrontierUsage {
296    /// Requested resident encoded bytes per queue.
297    pub memory_bytes_per_queue: Option<usize>,
298    /// Peak combined current/next resident encoded capacities.
299    pub peak_retained_bytes: u64,
300    /// Resident encoded bytes after explicit cleanup.
301    pub retained_bytes: u64,
302    /// Confirmed complete writes; failed writes can leave additional partial bytes.
303    pub spilled_bytes: u64,
304    /// Actual codec, read, write, validation or cleanup failures.
305    pub failures: Vec<String>,
306    /// Search event reached before storage prevented certification.
307    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
317/// Two ordered encoded queues sharing a fixed live Store/codec owner.
318pub(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    /// Streams the live next queue into a fresh Store-bound codec. Old sources
375    /// are audited and closed before their owner is released; readers remain
376    /// bounded to one paired row independently of the full frontier width.
377    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/// The outcome of inserting a state into the seen set.
609#[derive(Clone, Copy, Debug, PartialEq, Eq)]
610pub(crate) enum Inserted {
611    /// The state was absent and is now present.
612    New,
613    /// The state was already present: its discovery id when the set retains
614    /// ids (in-memory exact identities), otherwise `None`.
615    Seen(Option<u64>),
616}
617
618impl Inserted {
619    pub(crate) const fn is_new(self) -> bool {
620        matches!(self, Self::New)
621    }
622}
623
624/// Retained identities with equal keys, each with its discovery id.
625type Bucket<T> = Vec<(T, u64)>;
626
627/// Retained canonical rows, bucketed by the existing state hash. Hashes select
628/// candidates only; even a complete collision cannot discard a distinct state.
629/// Each retained identity carries the discovery id it was inserted with, so
630/// equal keys of distinct states still resolve to distinct discoveries.
631#[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    /// The discovery id of `row`, when it is present.
651    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    /// Inserts `row` with discovery id `id` unless it is present.
681    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    /// The discovery id of `row`, when it is present.
742    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    /// Inserts `row` with discovery id `id` unless it is present.
754    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                // The first row has already been copied and written when the
867                // next root polls. Mutations therefore exercise partial output.
868                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}