dive-store 0.1.0

State fingerprints and disk-backed state storage for TLA+ model checking
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
//! Fallible, private-file seen-state storage.
//!
//! Every operation is fallible: an I/O error is returned, never read as absence.
//! The checker admits this storage through an explicit fallible inline route.
//! Entries are physical library commits,
//! not a model checker's ordered discovery-prefix count.
//!
//! Keys and offsets remain on disk. At most two key-sized workspaces, scalar index
//! probes and sequential rehash workspaces are bounded by [`Limits`]. OS page
//! cache, handles, paths and caller-owned keys are outside these bounds.

mod files;

use std::fs;
use std::path::{Path, PathBuf};
use std::sync::atomic::{AtomicU64, Ordering};

use crate::StoreMode;

static NEXT: AtomicU64 = AtomicU64::new(0);

/// Maximum encoded key admitted by the default library policy: 64 MiB.
pub const MAX_KEY_BYTES: usize = 64 * 1024 * 1024;

/// Deterministic resource bounds, checked before record allocation or index growth.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Limits {
    /// Maximum one-record key buffer. Fingerprint keys always use eight bytes.
    pub key_bytes: usize,
    /// Maximum number of physically committed keys.
    pub entries: u64,
    /// Maximum slots examined by one index lookup, including rehash insertion.
    pub probe_steps: u64,
    /// Maximum pair comparisons for the bounded, quadratic collision summary.
    /// Exceeding this refuses the summary; it never silently omits metadata.
    pub summary_pairs: u64,
}

impl Default for Limits {
    fn default() -> Self {
        Self {
            key_bytes: MAX_KEY_BYTES,
            entries: 16 * 1024 * 1024,
            probe_steps: 32 * 1024 * 1024,
            summary_pairs: 1_000_000,
        }
    }
}

impl Limits {
    /// Checks policy bounds without allocating, opening files or invoking callbacks.
    ///
    /// # Errors
    /// An invalid key, entry or probe bound. A zero summary budget is valid and
    /// explicitly refuses a summary requiring pair comparisons.
    pub fn validate(self) -> Result<(), SeenError> {
        if self.key_bytes > MAX_KEY_BYTES
            || self.key_bytes < 8
            || self.entries == 0
            || self.entries > u64::from(u32::MAX)
            || self.probe_steps == 0
        {
            return Err(error(
                Operation::Admission,
                "invalid disk seen-state limits",
            ));
        }
        Ok(())
    }
}

/// Borrowed storage identity; exact keys are existing canonical bytes, unchanged.
#[derive(Clone, Copy, Debug)]
pub enum Key<'a> {
    /// Complete 64-bit fingerprint, including the high bit and zero.
    Fingerprint(u64),
    /// Full canonical state encoding. No normalization or provider is invoked.
    Exact(&'a [u8]),
}

/// A successful, fully committed insertion.
/// This is an in-process write commit, not crash durability or recovery.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum InsertOutcome {
    /// The complete key already exists.
    Present,
    /// Record and index entry were both committed.
    Inserted,
}

/// Typed operation at which the first failure occurred.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Operation {
    /// Invalid key mode, resource bound or checked arithmetic.
    Admission,
    /// Creating private owned files.
    Create,
    /// Reading file bytes or metadata.
    Read,
    /// Seeking to a bounded offset.
    Seek,
    /// Writing or flushing a record/index entry.
    Write,
    /// Allocating the bounded record workspace.
    Allocate,
    /// Constructing and committing a larger on-disk index.
    Rehash,
    /// Invalid header, offset, length, identity or checksum.
    Corruption,
    /// Computing the fingerprint-gap summary.
    Summary,
    /// Removing only owned files and their private directory.
    Cleanup,
}

/// A storage failure retained by the poisoned store. Checksums detect accidental
/// corruption; neither these files nor this error are an authenticity certificate.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SeenError {
    /// First failing operation; subsequent operations return this same cause.
    pub operation: Operation,
    /// Bounded diagnostic context, without a copy of the key.
    pub message: String,
    /// Additional cleanup failure, without replacing the original cause.
    pub cleanup_failure: Option<String>,
}

impl SeenError {
    /// Stable code for disk seen-state failures.
    #[must_use]
    pub const fn code(&self) -> &'static str {
        "DIVE-S0700"
    }
}

impl std::fmt::Display for SeenError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}: {:?}: {}", self.code(), self.operation, self.message)?;
        if let Some(cleanup) = &self.cleanup_failure {
            write!(f, "; cleanup also failed: {cleanup}")?;
        }
        Ok(())
    }
}
impl std::error::Error for SeenError {}

fn error(operation: Operation, cause: impl std::fmt::Display) -> SeenError {
    SeenError {
        operation,
        message: cause.to_string(),
        cleanup_failure: None,
    }
}

/// Library storage facts, independent of semantic search-prefix statistics.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Stats {
    /// Record/index insertions whose full in-process writes completed. Inserts
    /// do not fsync data and this library has no restart/import guarantee.
    pub physical_entries: u64,
    /// Current expected data/index lengths, not cumulative rehash traffic.
    pub disk_bytes: u64,
    /// Zero: there is no resident key/offset collection.
    pub resident_key_bytes: u64,
    /// Whether an operation failed and accounting may exclude partial writes.
    pub poisoned: bool,
    /// Whether explicit removal of all owned files and directory completed.
    pub cleanup_completed: bool,
}

/// Owned transient disk set. Calls are coordinated through exclusive borrowing;
/// this first library slice does not claim parallel engine integration.
///
/// ```
/// use dive_store::{StoreMode, seen::{DiskSeen, InsertOutcome, Key, Limits}};
/// let mut set = DiskSeen::create(StoreMode::Exact, &std::env::temp_dir(), Limits::default())?;
/// assert_eq!(set.insert(Key::Exact(b"canonical-state"))?, InsertOutcome::Inserted);
/// assert_eq!(set.insert(Key::Exact(b"canonical-state"))?, InsertOutcome::Present);
/// assert!(set.contains(Key::Exact(b"canonical-state"))?);
/// assert!(set.close()?.cleanup_completed);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[derive(Debug)]
pub struct DiskSeen {
    directory: PathBuf,
    mode: StoreMode,
    limits: Limits,
    capacity: u64,
    count: u64,
    data_end: u64,
    first: Option<SeenError>,
    closed: bool,
    audited: bool,
    #[cfg(test)]
    fault: Option<(Operation, u64)>,
    #[cfg(test)]
    forced_hash: Option<u64>,
}

impl DiskSeen {
    /// Creates a unique child directory and versioned files, without clobbering
    /// or adopting caller files. The parent must already exist.
    ///
    /// # Errors
    /// Invalid bounds or filesystem creation/write/cleanup failures.
    pub fn create(mode: StoreMode, parent: &Path, limits: Limits) -> Result<Self, SeenError> {
        limits.validate()?;
        let directory = parent.join(format!(
            "dive-seen-{}-{}",
            std::process::id(),
            NEXT.fetch_add(1, Ordering::Relaxed)
        ));
        fs::create_dir(&directory).map_err(|e| error(Operation::Create, e))?;
        let mut set = Self {
            directory,
            mode,
            limits,
            capacity: 8,
            count: 0,
            data_end: files::HEADER,
            first: None,
            closed: false,
            audited: false,
            #[cfg(test)]
            fault: None,
            #[cfg(test)]
            forced_hash: None,
        };
        if let Err(mut failure) = set.initialize() {
            if let Err(cleanup) = set.remove_owned() {
                failure.cleanup_failure = Some(cleanup.message);
            }
            return Err(failure);
        }
        Ok(set)
    }

    /// Current physical facts, also available after a failure.
    #[must_use]
    pub fn stats(&self) -> Stats {
        Stats {
            physical_entries: self.count,
            disk_bytes: if self.closed {
                0
            } else {
                self.data_end + files::HEADER + self.capacity * files::SLOT
            },
            resident_key_bytes: 0,
            poisoned: self.first.is_some(),
            cleanup_completed: self.closed,
        }
    }

    /// Tests full identity, never treating an error as absence.
    ///
    /// # Errors
    /// Mode/bounds, file integrity or I/O failure; the first failure poisons future calls.
    pub fn contains(&mut self, key: Key<'_>) -> Result<bool, SeenError> {
        self.available()?;
        let result = self.find_key(key).map(|(_, found)| found);
        self.retain(result)
    }

    /// Commits one complete record and index slot. A failed partial write poisons
    /// the store, never yielding `Inserted` or `Present`.
    /// These are transient in-process writes, without per-insert data fsync or
    /// a crash-recovery contract.
    ///
    /// # Errors
    /// Membership, resource, allocation, write or rehash failure.
    pub fn insert(&mut self, key: Key<'_>) -> Result<InsertOutcome, SeenError> {
        self.available()?;
        let result = self.insert_inner(key);
        self.retain(result)
    }

    /// Fallible bounded-workspace TLC minimum-gap counterpart. This first slice
    /// scans pairs quadratically and refuses beyond `summary_pairs`; it does not
    /// allocate a fingerprint vector or silently remove collision metadata.
    ///
    /// # Errors
    /// Exact mode, policy work limit, corruption or I/O failure.
    pub fn tlc_min_gap(&mut self, fp_bits: u32) -> Result<u64, SeenError> {
        self.available()?;
        let result = self.gap_inner(fp_bits);
        self.retain(result)
    }

    /// Explicitly removes owned files before a caller reports completion.
    /// Unknown caller-added files are never deleted. A prior failure remains
    /// authoritative even when cleanup succeeds, with any cleanup failure attached.
    /// Cleanup may remove some owned files before failing; the poisoned store
    /// cannot be reused, even if later cleanup succeeds.
    ///
    /// # Errors
    /// The first retained failure, or explicit cleanup failure.
    pub fn close(&mut self) -> Result<Stats, SeenError> {
        let (stats, audited) = self.close_controlled(true, &|| true)?;
        if audited {
            Ok(stats)
        } else {
            Err(error(
                Operation::Admission,
                "store was discarded without a complete audit",
            ))
        }
    }

    /// Audits retained records under an actual owner, then removes owned files.
    ///
    /// `validate = false` discards an already stopped run without scanning its
    /// remaining records. The Boolean result is true only after a complete
    /// audit; cancellation still cleans up but can never certify the contents.
    /// Later calls cannot upgrade discarded files into audited contents.
    ///
    /// ```
    /// use dive_store::{StoreMode, seen::{DiskSeen, Key, Limits, SeenError}};
    /// let mut seen = DiskSeen::create(StoreMode::Fingerprint, &std::env::temp_dir(), Limits::default())?;
    /// seen.insert(Key::Fingerprint(7))?;
    /// let (stats, audited) = seen.close_controlled(true, &|| false)?;
    /// assert!(stats.cleanup_completed);
    /// assert!(!audited);
    /// assert!(seen.close().is_err());
    /// # Ok::<(), SeenError>(())
    /// ```
    ///
    /// # Errors
    /// The original storage cause, with cleanup errors retained separately.
    pub fn close_controlled(
        &mut self,
        validate: bool,
        proceed: &dyn Fn() -> bool,
    ) -> Result<(Stats, bool), SeenError> {
        if !self.closed {
            if validate && self.first.is_none() {
                match self.audit_inner(proceed) {
                    Ok(audited) => self.audited = audited,
                    Err(failure) => self.first = Some(failure),
                }
            }
            if let Err(cleanup) = self.remove_owned() {
                if let Some(first) = &mut self.first {
                    first.cleanup_failure.get_or_insert(cleanup.message);
                } else {
                    self.first = Some(cleanup);
                }
            } else {
                self.closed = true;
            }
        }
        self.first
            .clone()
            .map_or_else(|| Ok((self.stats(), self.audited)), Err)
    }

    fn remove_owned(&mut self) -> Result<(), SeenError> {
        self.check_fault(Operation::Cleanup)?;
        for name in ["data", "index", "index-next"] {
            match fs::remove_file(self.directory.join(name)) {
                Ok(()) => {}
                Err(e) if e.kind() == std::io::ErrorKind::NotFound => {}
                Err(e) => return Err(error(Operation::Cleanup, e)),
            }
        }
        fs::remove_dir(&self.directory).map_err(|e| error(Operation::Cleanup, e))
    }

    fn available(&self) -> Result<(), SeenError> {
        if let Some(first) = &self.first {
            return Err(first.clone());
        }
        if self.closed {
            return Err(error(Operation::Admission, "store is closed"));
        }
        Ok(())
    }

    fn retain<T>(&mut self, result: Result<T, SeenError>) -> Result<T, SeenError> {
        if let Err(failure) = &result {
            self.first = Some(failure.clone());
        }
        result
    }

    #[allow(
        clippy::unused_self,
        clippy::unnecessary_wraps,
        reason = "test-only fault injection uses the production I/O boundaries"
    )]
    fn check_fault(&mut self, operation: Operation) -> Result<(), SeenError> {
        #[cfg(test)]
        if let Some((wanted, remaining)) = &mut self.fault
            && *wanted == operation
        {
            if *remaining == 0 {
                self.fault = None;
                return Err(error(
                    operation,
                    if operation == Operation::Write {
                        std::io::Error::new(
                            std::io::ErrorKind::StorageFull,
                            "injected storage exhaustion",
                        )
                        .to_string()
                    } else {
                        "injected storage failure".to_owned()
                    },
                ));
            }
            *remaining -= 1;
        }
        let _ = operation;
        Ok(())
    }
}

#[cfg(test)]
mod tests;

impl Drop for DiskSeen {
    fn drop(&mut self) {
        if !self.closed {
            let _ = self.remove_owned();
        }
    }
}