Skip to main content

cll/log/
mod.rs

1//! The CLL entry log, checkpoint state and witness state: the storage
2//! interfaces every CLL backend implements, in every language.
3//!
4//! [`docs/backend-contract.md`] is the source of truth for everything here:
5//! the operations and their argument order, the error codes and the order in
6//! which they are checked, the not-found convention, capabilities, limits and
7//! the portable JSONL and SQL formats. The shared conformance vectors turn it
8//! into cases; [`conformance`] runs them against any backend, built-in or
9//! user-supplied.
10//!
11//! | Contract | Trait |
12//! |---|---|
13//! | Entry source (`scanEntries`) | [`EntrySource`] |
14//! | Entry log (+ `append`, `getEntry`) | [`EntryStore`] |
15//! | Checkpoint state (`loadCll`, `commitCll`) | [`CheckpointStateStore`] |
16//! | Witness state (`pendingWitnesses`, `pendingWitnessesFor`, `getWitness`, `commitWitness`) | [`WitnessStateStore`] |
17//! | Checkpoint store (entry source + checkpoint and witness state) | [`CheckpointStore`] |
18//! | Full backend (all of the above + `close`) | [`Backend`] |
19//!
20//! The traits are synchronous, as the contract says for Rust. Every method
21//! takes `&self`: backends use interior mutability, so one handle can be
22//! shared across threads (for example in an `Arc`), like a Go backend.
23//!
24//! Backends:
25//!
26//! - [`memory`]: in-process, no durable state.
27//! - [`jsonl`] (Unix): one log per JSONL v4 journal file.
28//! - `sqlite` (Cargo feature `sqlite`): the shared relational schema on SQLite.
29//! - `mysql` (Cargo feature `mysql`): the shared relational schema on MySQL 8.
30//!
31//! The log stores opaque 32-byte identities and does not know what they name.
32//!
33//! [`docs/backend-contract.md`]: https://github.com/action-state-group/checkpointed-local-log/blob/main/docs/backend-contract.md
34
35use std::fmt;
36
37pub mod conformance;
38mod engine;
39#[cfg(unix)]
40pub mod jsonl;
41pub mod memory;
42#[cfg(feature = "mysql")]
43pub mod mysql;
44#[cfg(any(feature = "sqlite", feature = "mysql"))]
45mod sql;
46#[cfg(feature = "sqlite")]
47pub mod sqlite;
48mod time;
49pub mod wire;
50
51pub use time::Timestamp;
52
53/// `EntryBytes`: the width of every identity, node and peak.
54pub const ENTRY_BYTES: usize = 32;
55/// `MaxWitnesses`: the largest `pendingWitnesses` limit.
56pub const MAX_WITNESSES: usize = 32;
57/// `MaxCheckpointBytes`: the largest checkpoint byte string.
58pub const MAX_CHECKPOINT_BYTES: usize = 65_536;
59/// `MaxJournalEventBytes`: the largest JSONL event line.
60pub const MAX_JOURNAL_EVENT_BYTES: usize = 4_194_304;
61/// `MaxWitnessResponseBytes`: the largest witness receipt.
62pub const MAX_WITNESS_RESPONSE_BYTES: usize = 2_097_152;
63/// `MaxIdentifierBytes`: the longest witness or log identifier, in bytes.
64pub const MAX_IDENTIFIER_BYTES: usize = 191;
65/// `MaxReasonBytes`: the longest `lastError`, in UTF-8 bytes.
66pub const MAX_REASON_BYTES: usize = 4096;
67/// `DefaultScanLimit`: the conventional entry batch size.
68pub const DEFAULT_SCAN_LIMIT: usize = 100;
69/// `MaxScanLimit`: the largest `scanEntries` limit.
70pub const MAX_SCAN_LIMIT: usize = 1000;
71/// `MaxPortableInteger`: JavaScript `Number.MAX_SAFE_INTEGER`, the largest
72/// sequence and receipt position.
73pub const MAX_PORTABLE_INTEGER: u64 = 9_007_199_254_740_991;
74/// `MinPortableUnixMillis`: the earliest ECMAScript `Date`.
75pub const MIN_PORTABLE_UNIX_MILLIS: i64 = -8_640_000_000_000_000;
76/// `MaxPortableUnixMillis`: the latest ECMAScript `Date`.
77pub const MAX_PORTABLE_UNIX_MILLIS: i64 = 8_640_000_000_000_000;
78
79/// The contract's error codes (docs/backend-contract.md, "Error codes").
80#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
81#[non_exhaustive]
82pub enum ErrorCode {
83    /// `not_found`: a direct lookup found nothing.
84    NotFound,
85    /// `invalid`: a caller-supplied value or transition breaks the contract.
86    Invalid,
87    /// `corrupt`: durable bytes, rows or events are malformed or inconsistent.
88    Corrupt,
89    /// `closed`: the backend was closed.
90    Closed,
91    /// `contention`: a compare-and-set failed, or another writer holds the log.
92    Contention,
93    /// `rejected`: a witness or offline verification permanently rejected a
94    /// response. Storage operations never return it.
95    Rejected,
96    /// `unsupported`: the store does not offer this operation.
97    Unsupported,
98    /// Rust only: an I/O or database-driver failure the contract does not
99    /// classify (a lost connection, a permission error). Go and TypeScript
100    /// surface these as their platform's own errors, which carry no CLL
101    /// code; Rust gives every error a code, so they carry this one.
102    Storage,
103}
104
105impl ErrorCode {
106    /// The contract's spelling, for example `not_found`.
107    pub const fn as_str(self) -> &'static str {
108        match self {
109            Self::NotFound => "not_found",
110            Self::Invalid => "invalid",
111            Self::Corrupt => "corrupt",
112            Self::Closed => "closed",
113            Self::Contention => "contention",
114            Self::Rejected => "rejected",
115            Self::Unsupported => "unsupported",
116            Self::Storage => "storage",
117        }
118    }
119}
120
121impl fmt::Display for ErrorCode {
122    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
123        f.write_str(self.as_str())
124    }
125}
126
127/// A CLL storage failure. [`Error::code`] is its contract error code.
128#[derive(Debug)]
129pub struct Error {
130    code: ErrorCode,
131    message: String,
132    source: Option<Box<dyn std::error::Error + Send + Sync + 'static>>,
133}
134
135impl Error {
136    /// An error with `code` and a human-readable message.
137    pub fn new(code: ErrorCode, message: impl Into<String>) -> Self {
138        Self {
139            code,
140            message: message.into(),
141            source: None,
142        }
143    }
144
145    /// An error with `code` caused by `source`.
146    pub fn with_source(
147        code: ErrorCode,
148        message: impl Into<String>,
149        source: impl Into<Box<dyn std::error::Error + Send + Sync + 'static>>,
150    ) -> Self {
151        Self {
152            code,
153            message: message.into(),
154            source: Some(source.into()),
155        }
156    }
157
158    /// The contract error code.
159    pub fn code(&self) -> ErrorCode {
160        self.code
161    }
162
163    /// The message, without the code.
164    pub fn message(&self) -> &str {
165        &self.message
166    }
167
168    pub(crate) fn invalid(message: impl Into<String>) -> Self {
169        Self::new(ErrorCode::Invalid, message)
170    }
171
172    pub(crate) fn corrupt(message: impl Into<String>) -> Self {
173        Self::new(ErrorCode::Corrupt, message)
174    }
175
176    pub(crate) fn contention(message: impl Into<String>) -> Self {
177        Self::new(ErrorCode::Contention, message)
178    }
179
180    pub(crate) fn closed() -> Self {
181        Self::new(ErrorCode::Closed, "the backend is closed")
182    }
183
184    pub(crate) fn not_found(message: impl Into<String>) -> Self {
185        Self::new(ErrorCode::NotFound, message)
186    }
187
188    /// The same failure reported under another code, for example a decoding
189    /// error in durable data, which is `corrupt` rather than `invalid`.
190    pub(crate) fn recode(mut self, code: ErrorCode) -> Self {
191        self.code = code;
192        self
193    }
194}
195
196impl fmt::Display for Error {
197    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
198        write!(f, "{}: {}", self.code, self.message)?;
199        if let Some(source) = &self.source {
200            write!(f, ": {source}")?;
201        }
202        Ok(())
203    }
204}
205
206impl std::error::Error for Error {
207    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
208        self.source
209            .as_deref()
210            .map(|source| source as &(dyn std::error::Error + 'static))
211    }
212}
213
214impl From<std::io::Error> for Error {
215    fn from(error: std::io::Error) -> Self {
216        Self::with_source(ErrorCode::Storage, "I/O failure", error)
217    }
218}
219
220/// The result of every CLL storage operation.
221pub type Result<T, E = Error> = std::result::Result<T, E>;
222
223/// One log entry: a dense 1-based `seq`, a 32-byte identity and its UTC
224/// millisecond observation time.
225#[derive(Clone, Debug, PartialEq, Eq)]
226pub struct Entry {
227    pub seq: u64,
228    pub value: Vec<u8>,
229    pub appended_at: Timestamp,
230}
231
232/// The identity and observation time an application appends. Any byte length
233/// and any time are representable; the backend rejects contract-invalid
234/// values as `invalid`.
235#[derive(Clone, Debug, PartialEq, Eq)]
236pub struct AppendInput {
237    pub value: Vec<u8>,
238    pub appended_at: Timestamp,
239}
240
241/// Whether `append` stored a new entry or found the identity already present.
242#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
243pub enum AppendOutcome {
244    /// `inserted`
245    Inserted,
246    /// `idempotent`: the original entry, with its original `seq` and time.
247    Idempotent,
248}
249
250impl AppendOutcome {
251    /// The contract's spelling.
252    pub const fn as_str(self) -> &'static str {
253        match self {
254            Self::Inserted => "inserted",
255            Self::Idempotent => "idempotent",
256        }
257    }
258}
259
260/// The result of `append`.
261#[derive(Clone, Debug, PartialEq, Eq)]
262pub struct AppendResult {
263    pub entry: Entry,
264    pub outcome: AppendOutcome,
265}
266
267/// The complete checkpoint tuple of a [`State`]: present or absent as a whole.
268#[derive(Clone, Debug, Default, PartialEq, Eq)]
269pub struct CheckpointState {
270    pub bytes: Vec<u8>,
271    pub size: u64,
272    pub indexed_seq: u64,
273    pub peaks: Vec<Vec<u8>>,
274}
275
276/// The restartable MMR, checkpoint and witness state (`State`).
277#[derive(Clone, Debug, Default, PartialEq, Eq)]
278pub struct State {
279    pub size: u64,
280    pub nodes: Vec<Vec<u8>>,
281    pub indexed_seq: u64,
282    pub first_pending_at: Option<Timestamp>,
283    pub checkpoint: Option<CheckpointState>,
284    pub witnesses: Vec<WitnessState>,
285}
286
287/// A verified witness receipt: its bytes and optional metadata.
288#[derive(Clone, Debug, Default, PartialEq, Eq)]
289pub struct WitnessReceiptState {
290    pub bytes: Vec<u8>,
291    /// 64 lowercase hex digits.
292    pub entry_hash: Option<String>,
293    /// `legacy`.
294    pub entry_hash_scheme: Option<String>,
295    pub leaf_index: Option<i64>,
296    pub tree_size: Option<i64>,
297}
298
299/// Delivery state for one witness and checkpoint, keyed by
300/// (`witness_id`, `checkpoint_size`).
301#[derive(Clone, Debug, PartialEq, Eq)]
302pub struct WitnessState {
303    pub witness_id: String,
304    pub checkpoint_size: u64,
305    pub checkpoint: Vec<u8>,
306    pub attempts: u32,
307    pub next_attempt_at: Timestamp,
308    pub receipt: Option<WitnessReceiptState>,
309    pub permanent: bool,
310    pub last_error: Option<String>,
311}
312
313/// What [`CheckpointStateStore::append_cll`] adds to the stored state: the
314/// new nodes and witness rows, and the new scalar fields. The stored size
315/// plus `nodes.len()` is the new `size`.
316#[derive(Clone, Debug, Default, PartialEq, Eq)]
317pub struct StateAppend {
318    pub nodes: Vec<Vec<u8>>,
319    pub indexed_seq: u64,
320    pub first_pending_at: Option<Timestamp>,
321    pub checkpoint: Option<CheckpointState>,
322    /// Rows to add. A key the store already holds is accepted when its
323    /// checkpoint bytes are identical (the stored row is kept) and is
324    /// `contention` otherwise, as in [`CheckpointStateStore::commit_cll`].
325    pub witnesses: Vec<WitnessState>,
326}
327
328/// `EntrySource`: bounded scans after a dense sequence position.
329pub trait EntrySource {
330    /// Entries with `seq > after_seq`, ascending, at most `limit`
331    /// (1..=[`MAX_SCAN_LIMIT`]).
332    fn scan_entries(&self, after_seq: u64, limit: usize) -> Result<Vec<Entry>>;
333}
334
335/// `EntryCounter`: the number of entries in the log. Sequences are dense and
336/// 1-based, so the count is also the last sequence. It is a trait of its own,
337/// beside [`EntrySource`], so that stores written before it still implement
338/// the entry log traits; every built-in backend implements it.
339pub trait EntryCounter {
340    /// The number of entries.
341    fn entry_count(&self) -> Result<u64>;
342}
343
344/// `EntryStore`: the entry log. Appends opaque identities and looks them up.
345pub trait EntryStore: EntrySource {
346    /// Appends `input.value`, or returns its original entry as
347    /// [`AppendOutcome::Idempotent`]. A store without the `digest-append`
348    /// capability returns `unsupported` for an identity it does not hold.
349    fn append(&self, input: &AppendInput) -> Result<AppendResult>;
350
351    /// The entry holding `value`; `not_found` when there is none.
352    fn get_entry(&self, value: &[u8]) -> Result<Entry>;
353}
354
355/// `CheckpointStateStore`: append-only CLL state with compare-and-set.
356pub trait CheckpointStateStore {
357    /// The current state.
358    fn load_cll(&self) -> Result<State>;
359
360    /// Replaces the state with `next` if the current size and checkpoint
361    /// bytes are `expected_size` and `expected_checkpoint` (`None` when there
362    /// is no checkpoint), under the contract's transition rules.
363    fn commit_cll(
364        &self,
365        expected_size: u64,
366        expected_checkpoint: Option<&[u8]>,
367        next: &State,
368    ) -> Result<()>;
369
370    /// [`commit_cll`](Self::commit_cll) for a caller that holds only the
371    /// change: the same compare-and-set and transition rules, as if `next`
372    /// were the stored state extended by `update`. The SQL backends override
373    /// it so the cost of a commit does not grow with the log's history;
374    /// the default loads the state and calls `commit_cll`.
375    fn append_cll(
376        &self,
377        expected_size: u64,
378        expected_checkpoint: Option<&[u8]>,
379        update: &StateAppend,
380    ) -> Result<()> {
381        let mut next = self.load_cll()?;
382        next.size = next
383            .size
384            .checked_add(update.nodes.len() as u64)
385            .ok_or_else(|| Error::invalid("CLL size overflows"))?;
386        next.nodes.extend(update.nodes.iter().cloned());
387        next.indexed_seq = update.indexed_seq;
388        next.first_pending_at = update.first_pending_at;
389        next.checkpoint = update.checkpoint.clone();
390        // Rows for keys the store holds are replaced by the update's, so a
391        // differing checkpoint surfaces as contention; all of the update's
392        // rows are kept, so a repeated key is invalid, as in SQL.
393        next.witnesses.retain(|held| {
394            !update.witnesses.iter().any(|row| {
395                row.witness_id == held.witness_id && row.checkpoint_size == held.checkpoint_size
396            })
397        });
398        next.witnesses.extend(update.witnesses.iter().cloned());
399        self.commit_cll(expected_size, expected_checkpoint, &next)
400    }
401}
402
403/// `WitnessStateStore`: independent witness-delivery state.
404pub trait WitnessStateStore {
405    /// Due rows (no receipt, not permanent, `next_attempt_at <= now`) ordered
406    /// by checkpoint size then witness ID, at most `limit`
407    /// (1..=[`MAX_WITNESSES`]).
408    fn pending_witnesses(&self, now: Timestamp, limit: usize) -> Result<Vec<WitnessState>>;
409
410    /// [`pending_witnesses`](Self::pending_witnesses) restricted to one
411    /// witness and ordered by checkpoint size, so a witness with a long
412    /// backlog cannot fill the page of the others. A malformed identifier, a
413    /// `limit` outside 1..=[`MAX_WITNESSES`] or a non-portable `now` is
414    /// `invalid`.
415    fn pending_witnesses_for(
416        &self,
417        witness_id: &str,
418        now: Timestamp,
419        limit: usize,
420    ) -> Result<Vec<WitnessState>>;
421
422    /// The row for the key, or `Ok(None)` when there is none (the contract's
423    /// not-found convention for Rust). A malformed key is still `invalid`.
424    fn get_witness(&self, witness_id: &str, checkpoint_size: u64) -> Result<Option<WitnessState>>;
425
426    /// Replaces the row for `next`'s key if its stored attempts equal
427    /// `expected_attempts` and its checkpoint bytes are unchanged.
428    fn commit_witness(&self, expected_attempts: u32, next: &WitnessState) -> Result<()>;
429}
430
431/// `CheckpointStore`: the surface a checkpoint runner needs.
432pub trait CheckpointStore: EntrySource + CheckpointStateStore + WitnessStateStore {}
433
434impl<T: EntrySource + CheckpointStateStore + WitnessStateStore + ?Sized> CheckpointStore for T {}
435
436/// `Backend` (TypeScript `CllBackend`): the full backend.
437pub trait Backend: EntryStore + CheckpointStateStore + WitnessStateStore {
438    /// Closes the backend. Repeating it succeeds; every other operation then
439    /// fails with `closed`.
440    fn close(&self) -> Result<()>;
441}
442
443/// Checks the identifier rules: 1..=191 UTF-8 bytes of `[A-Za-z0-9._:/-]`.
444pub fn validate_identifier(value: &str) -> Result<()> {
445    let valid = !value.is_empty()
446        && value.len() <= MAX_IDENTIFIER_BYTES
447        && value
448            .bytes()
449            .all(|b| b.is_ascii_alphanumeric() || matches!(b, b'.' | b'_' | b':' | b'/' | b'-'));
450    if valid {
451        Ok(())
452    } else {
453        Err(Error::invalid(format!(
454            "identifier must be 1..={MAX_IDENTIFIER_BYTES} bytes of [A-Za-z0-9._:/-]"
455        )))
456    }
457}
458
459#[cfg(test)]
460mod tests {
461    use super::*;
462
463    #[test]
464    fn identifiers_follow_the_portable_subset() {
465        for ok in ["primary", "a", "x.y_z:1/2-3", &"a".repeat(191)] {
466            validate_identifier(ok).unwrap();
467        }
468        for bad in ["", "bad id", "ΓΌ", "a\n", &"a".repeat(192)] {
469            assert_eq!(
470                validate_identifier(bad).unwrap_err().code(),
471                ErrorCode::Invalid
472            );
473        }
474    }
475
476    #[test]
477    fn errors_carry_code_message_and_source() {
478        let io = std::io::Error::other("disk");
479        let error = Error::from(io);
480        assert_eq!(error.code(), ErrorCode::Storage);
481        assert_eq!(error.to_string(), "storage: I/O failure: disk");
482        assert!(std::error::Error::source(&error).is_some());
483        assert_eq!(Error::closed().code().as_str(), "closed");
484        assert_eq!(AppendOutcome::Idempotent.as_str(), "idempotent");
485        for code in [
486            ErrorCode::NotFound,
487            ErrorCode::Invalid,
488            ErrorCode::Corrupt,
489            ErrorCode::Closed,
490            ErrorCode::Contention,
491            ErrorCode::Rejected,
492            ErrorCode::Unsupported,
493        ] {
494            assert_eq!(Error::new(code, "m").code().to_string(), code.as_str());
495        }
496    }
497}