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}