Skip to main content

rusty_agent_runtime/
checkpoint.rs

1//! Checkpointing: thread-scoped, versioned state snapshots.
2//!
3//! Checkpoints happen **at super-step boundaries, never mid-node** — so on
4//! resume the affected node re-runs from its start (node logic must be
5//! idempotent). One primitive, four use cases: durable execution,
6//! human-in-the-loop (interrupt → serialize → approve → resume), time travel
7//! (load any historical checkpoint, fork alternate paths), and
8//! partial-failure recovery.
9//!
10//! - [`InMemoryCheckpointer`] — RAM-only, lost on restart (dev/test).
11//! - [`JsonFileCheckpointer`] — one JSON file per checkpoint under a
12//!   directory, pure `serde_json` + `tokio::fs` (durable across restarts).
13//!
14//! # Delta checkpoints (R0.7 wave 4)
15//!
16//! Durable backends may store a checkpoint as a **channel-level delta**
17//! against the checkpoint before it ([`Checkpoint::base`]) instead of a full
18//! snapshot: only the channels whose values changed are written, which is
19//! what stops a 1000-step run from writing 1000 full copies of a largely
20//! unchanged state. The encoding is **checkpointer-internal**:
21//!
22//! - `put` always receives a full snapshot; the backend decides delta vs
23//!   full ([`encode_delta`]), bounded by a [`DeltaPolicy`] (chain length +
24//!   byte ratio) so resume folds stay O(1)-bounded by construction.
25//! - Every read method returns a fully materialized checkpoint: chains are
26//!   folded onto their base inside the backend ([`fold_delta`]). Callers
27//!   never observe `base`.
28//! - Checkpoints written before W4 have no `base` field and deserialize as
29//!   full snapshots — exactly what they always were.
30//!
31//! [`JsonFileCheckpointer`] and the Postgres backend opt in;
32//! [`InMemoryCheckpointer`] does not — its `put` is a sub-2 µs move, so a
33//! delta would buy nothing.
34
35use std::collections::{HashMap, HashSet};
36use std::path::PathBuf;
37use std::sync::{Arc, Mutex};
38
39use async_trait::async_trait;
40use chrono::{DateTime, Utc};
41use serde::{Deserialize, Serialize};
42
43use crate::error::{Result, RustyError};
44use crate::record::{CheckpointHeader, JournalRef};
45use crate::state::State;
46
47/// A versioned snapshot of one thread's state at a super-step boundary.
48#[derive(Debug, Clone, Serialize, Deserialize)]
49pub struct Checkpoint {
50    /// Unique checkpoint id (UUID v4; also serves as a fork handle for
51    /// time travel).
52    pub id: String,
53
54    /// The thread (session) this checkpoint belongs to. Threads cannot see
55    /// each other's state.
56    pub thread_id: String,
57
58    /// Zero-based super-step index at whose boundary this snapshot was taken.
59    pub step: usize,
60
61    /// The full channel state at the boundary.
62    ///
63    /// In a **delta checkpoint** ([`Checkpoint::base`] set — a storage
64    /// detail only opting-in backends produce and no read method ever
65    /// returns) this holds just the channels whose values changed since the
66    /// base, as full per-channel values. Channels are never deleted from a
67    /// state, so overlaying the delta onto the materialized base restores
68    /// the full state ([`fold_delta`]).
69    pub state: State,
70
71    /// The node set scheduled to run in the *next* super-step. Restored on
72    /// resume so execution continues exactly where it suspended.
73    pub next_nodes: Vec<String>,
74
75    /// Wall-clock creation time (UTC).
76    pub created_at: DateTime<Utc>,
77
78    /// The checkpoint this one diffs against (R0.7 wave 4 delta
79    /// checkpoints). `None` is a full snapshot — every checkpoint written
80    /// before W4, and every checkpoint a read method returns: folding is
81    /// checkpointer-internal, so `base` is only ever observed inside a
82    /// backend's storage (checkpoint files, database rows). Additive:
83    /// absent from the wire when unset, so pre-W4 checkpoints deserialize
84    /// unchanged.
85    #[serde(default, skip_serializing_if = "Option::is_none")]
86    pub base: Option<String>,
87
88    /// Flight Recorder provenance (R0.5): checkpoint format version, graph
89    /// version/content hash, active policy version, and the run's logical
90    /// clock value at creation. See [`CheckpointHeader`] for the semantics.
91    ///
92    /// `#[serde(default)]` keeps checkpoints written before R0.5 (which have
93    /// no header field) deserializable: they load with
94    /// [`CheckpointHeader::default`] — current format version, unversioned
95    /// graph, static policy.
96    #[serde(default)]
97    pub header: CheckpointHeader,
98
99    /// The journal head at this boundary (`None` pre-R0.5), binding this
100    /// state snapshot to the run evidence that produced it.
101    #[serde(default)]
102    pub journal_ref: Option<JournalRef>,
103}
104
105impl Checkpoint {
106    /// A new checkpoint with a fresh UUID v4 id and current timestamp.
107    ///
108    /// Convenience constructor used by tests and pre-R0.5 call paths: the
109    /// header falls back to [`CheckpointHeader::default`] and no journal
110    /// reference is stamped. The executor mints checkpoints field-by-field
111    /// instead, sourcing id/timestamp from the run's determinism seams and
112    /// stamping the real header and journal head.
113    pub fn new(
114        thread_id: impl Into<String>,
115        step: usize,
116        state: State,
117        next_nodes: Vec<String>,
118    ) -> Self {
119        Self {
120            id: uuid::Uuid::new_v4().to_string(),
121            thread_id: thread_id.into(),
122            step,
123            state,
124            next_nodes,
125            created_at: Utc::now(),
126            header: CheckpointHeader::default(),
127            journal_ref: None,
128            base: None,
129        }
130    }
131}
132
133/// Delta-checkpoint chain policy (R0.7 wave 4): when an opting-in backend
134/// rewrites a boundary as a full snapshot instead of another chain link.
135///
136/// Both bounds exist to keep resume reads bounded. An unbounded delta chain
137/// makes every resume an O(chain) fold — the event-sourcing failure mode
138/// checkpoints exist to avoid (checkpoints, not journals, are the resume
139/// authority). The bound is enforced at write time and is a *policy*, never
140/// a correctness condition: readers fold whatever chain they find.
141#[derive(Debug, Clone, Copy, PartialEq)]
142pub struct DeltaPolicy {
143    /// Maximum number of consecutive delta links above a full snapshot. A
144    /// put that would exceed it writes a full snapshot instead, so resume
145    /// folds at most `max_chain_len` channel-sets. Default: 32.
146    pub max_chain_len: usize,
147
148    /// Full-snapshot threshold as a fraction of the full state's serialized
149    /// size: when a delta's serialized size reaches this share of the state
150    /// it would replace, the delta has stopped paying for itself — it costs
151    /// nearly a full write *and* extends the chain — so a full snapshot is
152    /// written instead. Default: 0.8.
153    pub max_byte_ratio: f64,
154}
155
156impl Default for DeltaPolicy {
157    fn default() -> Self {
158        Self {
159            max_chain_len: 32,
160            max_byte_ratio: 0.8,
161        }
162    }
163}
164
165impl DeltaPolicy {
166    /// Full snapshots at every boundary: the pre-W4 write behavior. Used by
167    /// backends that do not opt in, and as the measurement baseline for the
168    /// wave-4 benchmarks.
169    pub fn full_only() -> Self {
170        Self {
171            max_chain_len: 0,
172            max_byte_ratio: 0.0,
173        }
174    }
175
176    /// Whether delta encoding is on at all (`full_only` disables it).
177    fn deltas_enabled(&self) -> bool {
178        self.max_chain_len > 0
179    }
180}
181
182/// The materialized head of a thread's checkpoint chain: what an opting-in
183/// backend diffs the next `put` against.
184#[derive(Debug, Clone)]
185pub struct DeltaHead {
186    /// The head checkpoint, fully materialized (never itself a delta).
187    pub checkpoint: Checkpoint,
188
189    /// Consecutive delta links below the head (0 = the head is itself a
190    /// full snapshot). Backends track this at write time to enforce
191    /// [`DeltaPolicy::max_chain_len`] without re-walking the chain per put.
192    pub chain_len: usize,
193}
194
195/// What [`encode_delta`] decided to persist for one `put`, plus the chain
196/// length the stored checkpoint leaves behind.
197#[derive(Debug, Clone)]
198pub struct DeltaEncoding {
199    /// The checkpoint to store: either the put's checkpoint unchanged
200    /// (`base == None`, a full snapshot), or a channel-level delta whose
201    /// `base` names the chain head's id and whose `state` carries only the
202    /// channels that changed since the head.
203    pub checkpoint: Checkpoint,
204
205    /// Consecutive delta links below this checkpoint once stored (0 for a
206    /// full snapshot).
207    pub chain_len: usize,
208}
209
210impl DeltaEncoding {
211    /// Store the checkpoint as a full snapshot (chain resets).
212    pub(crate) fn full(checkpoint: &Checkpoint) -> Self {
213        Self {
214            checkpoint: Checkpoint {
215                base: None,
216                ..checkpoint.clone()
217            },
218            chain_len: 0,
219        }
220    }
221}
222
223/// The serialized size of a state — the byte measure
224/// [`DeltaPolicy::max_byte_ratio`] speaks in. `serde_json::to_vec` of a
225/// `Value` tree is infallible in practice (the same argument
226/// `record::canonical_json_digest` makes); panicking here would require a
227/// state that cannot serialize, which no checkpoint path can carry anyway.
228fn state_bytes(state: &State) -> usize {
229    serde_json::to_vec(state)
230        .expect("a State always serializes")
231        .len()
232}
233
234/// Decide what an opting-in backend persists for one `put`: a full
235/// snapshot, or a channel-level delta against the thread's head.
236///
237/// This is the write half of the W4 delta-checkpoint contract, shared by
238/// every opting-in backend (the JSON-file checkpointer, the Postgres
239/// checkpointer, and the server store's checkpoint path) so they all make
240/// the *same* decision for the same `(checkpoint, head, policy)` triple.
241///
242/// Rules, in order:
243///
244/// 1. Deltas disabled, no head, or the chain is already at
245///    [`DeltaPolicy::max_chain_len`] → full snapshot (the chain-length
246///    bound: resume folds stay bounded by construction).
247/// 2. The changed-channel delta's serialized size reaches
248///    [`DeltaPolicy::max_byte_ratio`] of the full state's → full snapshot
249///    (the byte-ratio bound: a delta that costs ~full buys nothing).
250/// 3. Otherwise a delta: `base` names the head's id, `state` carries only
251///    channels whose values changed. Unchanged channels are detected by
252///    pointer first (the CoW layer shares them) and by value second, so
253///    equal content is never rewritten even across a deserialize.
254///
255/// `put` always receives full snapshots; a caller-set `base` is never
256/// honored — encoding is checkpointer-internal.
257pub fn encode_delta(
258    checkpoint: &Checkpoint,
259    head: Option<&DeltaHead>,
260    policy: &DeltaPolicy,
261) -> DeltaEncoding {
262    let Some(head) = head.filter(|_| policy.deltas_enabled()) else {
263        return DeltaEncoding::full(checkpoint);
264    };
265    if head.chain_len >= policy.max_chain_len {
266        return DeltaEncoding::full(checkpoint);
267    }
268    let delta = State::from_shared_channels(
269        checkpoint
270            .state
271            .channels_changed_since(&head.checkpoint.state),
272    );
273    let delta_bytes = state_bytes(&delta);
274    let full_bytes = state_bytes(&checkpoint.state);
275    if (delta_bytes as f64) >= policy.max_byte_ratio * (full_bytes as f64) {
276        return DeltaEncoding::full(checkpoint);
277    }
278    DeltaEncoding {
279        checkpoint: Checkpoint {
280            base: Some(head.checkpoint.id.clone()),
281            state: delta,
282            ..checkpoint.clone()
283        },
284        chain_len: head.chain_len + 1,
285    }
286}
287
288/// Fold one delta link onto its materialized base: the base's channels
289/// overlaid with the delta's changed channels. Sharing is preserved — the
290/// materialized state shares unchanged channel values with the base rather
291/// than copying them (the same CoW observation the diff ran on).
292///
293/// The result's `base` is cleared: materialization is checkpointer-internal,
294/// so what a read method returns is always a full, self-contained
295/// checkpoint.
296pub fn fold_delta(base: &Checkpoint, delta: &Checkpoint) -> Checkpoint {
297    let mut state = base.state.clone();
298    for (channel, value) in delta.state.shared_channels() {
299        state.insert_shared(channel.to_owned(), value.clone());
300    }
301    Checkpoint {
302        id: delta.id.clone(),
303        thread_id: delta.thread_id.clone(),
304        step: delta.step,
305        state,
306        next_nodes: delta.next_nodes.clone(),
307        created_at: delta.created_at,
308        header: delta.header.clone(),
309        journal_ref: delta.journal_ref.clone(),
310        base: None,
311    }
312}
313
314/// Materialize a raw stored chain — root-first, each link's `base` naming
315/// the previous link's id — into the full checkpoint at its tip. Errors on
316/// a broken chain (a link whose base is not the previous link, or a root
317/// that is itself a delta): that is corruption, not data.
318///
319/// Public so every opting-in storage path folds chains identically (the
320/// server store's checkpoint path included).
321pub fn fold_chain(chain: &[Checkpoint]) -> Result<Checkpoint> {
322    let Some((root, links)) = chain.split_first() else {
323        return Err(RustyError::Checkpoint(
324            "cannot fold an empty checkpoint chain".into(),
325        ));
326    };
327    if let Some(base) = &root.base {
328        return Err(RustyError::Checkpoint(format!(
329            "checkpoint chain root `{}` is itself a delta against `{base}`; \
330             the chain is broken",
331            root.id
332        )));
333    }
334    let mut tip = root.clone();
335    for link in links {
336        if link.base.as_deref() != Some(tip.id.as_str()) {
337            return Err(RustyError::Checkpoint(format!(
338                "checkpoint `{}` claims base `{:?}` but follows `{}`; the chain is broken",
339                link.id, link.base, tip.id
340            )));
341        }
342        tip = fold_delta(&tip, link);
343    }
344    Ok(tip)
345}
346
347/// Materialize a whole thread's raw checkpoints, in any order: fold each
348/// delta chain onto its base, memoizing materialized links so overlapping
349/// chains fold once. Deltas whose base is absent or cyclic (a corrupt or
350/// partial store) are skipped with a warning, matching the forgiving read
351/// paths the file backend already practices — one corrupt file must not
352/// poison a thread's whole history.
353pub(crate) fn materialize_all(raw: Vec<Checkpoint>) -> Vec<Checkpoint> {
354    let by_id: HashMap<String, Checkpoint> = raw.into_iter().map(|c| (c.id.clone(), c)).collect();
355    let mut memo: HashMap<String, Checkpoint> = HashMap::new();
356    let mut out = Vec::with_capacity(by_id.len());
357
358    'starts: for start_id in by_id.keys() {
359        if let Some(materialized) = memo.get(start_id) {
360            out.push(materialized.clone());
361            continue;
362        }
363        // Walk from this checkpoint up its base chain, collecting links
364        // until a full root or an already-materialized checkpoint.
365        // Iterative, not recursive: a corrupt store could chain deeper than
366        // any stack.
367        let mut links: Vec<&Checkpoint> = Vec::new();
368        let mut visiting: HashSet<&str> = HashSet::new();
369        let mut cursor = by_id.get(start_id);
370        let mut folded: Option<Checkpoint> = None;
371        while let Some(current) = cursor {
372            if !visiting.insert(current.id.as_str()) {
373                tracing::warn!(
374                    checkpoint_id = %start_id,
375                    "checkpoint delta chain has a cycle; skipping"
376                );
377                continue 'starts;
378            }
379            if let Some(materialized) = memo.get(&current.id) {
380                folded = Some(materialized.clone());
381                break;
382            }
383            match &current.base {
384                None => {
385                    folded = Some(current.clone());
386                    break;
387                }
388                Some(base_id) => {
389                    links.push(current);
390                    match by_id.get(base_id) {
391                        Some(base) => cursor = Some(base),
392                        None => {
393                            tracing::warn!(
394                                checkpoint_id = %current.id,
395                                base = %base_id,
396                                "checkpoint delta base is missing; skipping chain"
397                            );
398                            continue 'starts;
399                        }
400                    }
401                }
402            }
403        }
404        // `folded` is always set when the loop exits normally (every path
405        // that cannot resolve has already continued `starts`).
406        let Some(mut tip) = folded else {
407            continue;
408        };
409        // Fold the collected links root-ward → tip: the last link pushed is
410        // the closest to the resolved base.
411        for link in links.iter().rev() {
412            tip = fold_delta(&tip, link);
413            memo.insert(link.id.clone(), tip.clone());
414        }
415        out.push(tip);
416    }
417    out
418}
419
420/// The checkpointer interface (the LangGraph `BaseCheckpointSaver` analog).
421///
422/// Implementations must be safe to share across tasks (`Send + Sync`) and
423/// are typically held as `Arc<dyn Checkpointer>` by the executor.
424#[async_trait]
425pub trait Checkpointer: Send + Sync {
426    /// Persist a checkpoint. Implementations must not overwrite an existing
427    /// checkpoint with the same id (ids are unique by construction).
428    ///
429    /// The checkpoint handed to `put` is always a **full snapshot**;
430    /// backends that opt into delta checkpoints (R0.7 wave 4) decide the
431    /// encoding internally ([`encode_delta`]) — a caller-set
432    /// [`Checkpoint::base`] is never honored.
433    async fn put(&self, checkpoint: Checkpoint) -> Result<()>;
434
435    /// The most recent checkpoint for a thread, or `None` if the thread has
436    /// never been checkpointed. Recency is defined by **insertion (put)
437    /// order — the last successfully stored checkpoint wins** — not by
438    /// super-step number: replay on the same thread legitimately appends
439    /// checkpoints whose `step` is at or below the existing head, and a
440    /// later resume must continue that newest timeline.
441    ///
442    /// Backends without an explicit insertion sequence use `created_at` as
443    /// the insertion proxy. That is exact as long as checkpoints are minted
444    /// fresh ([`Checkpoint::new`]) when stored and forked histories are
445    /// copied oldest-first, which [`Checkpointer::fork_thread`] does.
446    async fn get_latest(&self, thread_id: &str) -> Result<Option<Checkpoint>>;
447
448    /// All checkpoints for a thread, oldest first (time-travel listing).
449    ///
450    /// The order is total and identical across backends — ascending
451    /// `(step, created_at, id)` — so that [`Checkpointer::fork_thread`]'s
452    /// truncation-by-position is deterministic even when replay has appended
453    /// several checkpoints sharing the same `step`.
454    async fn list(&self, thread_id: &str) -> Result<Vec<Checkpoint>>;
455
456    /// Fetch one specific checkpoint of a thread by id (time-travel handle).
457    ///
458    /// The default implementation lists the thread and finds the id, which is
459    /// correct (if not maximally efficient) for every reasonable backend.
460    /// Returns `None` when the thread has no checkpoint with that id.
461    async fn get_by_id(&self, thread_id: &str, checkpoint_id: &str) -> Result<Option<Checkpoint>> {
462        let all = self.list(thread_id).await?;
463        Ok(all.into_iter().find(|c| c.id == checkpoint_id))
464    }
465
466    /// Fork a thread's history into a new thread (time travel).
467    ///
468    /// Copies the source thread's checkpoints — oldest first — into
469    /// `dst_thread`, preserving each checkpoint's `id`, `step`, `state`,
470    /// `next_nodes`, and `created_at`; only the `thread_id` changes. When
471    /// `at_checkpoint_id` is given, only checkpoints up to and including that
472    /// checkpoint are copied (fork from a mid-history point); when `None`,
473    /// the full history is copied. Returns the number of checkpoints copied.
474    ///
475    /// The default implementation re-`put`s each selected checkpoint with the
476    /// destination thread id. This is correct for every implementation whose
477    /// `put` uniqueness scope is per-thread — including both built-in impls
478    /// ([`InMemoryCheckpointer`] keys its map by thread, and
479    /// [`JsonFileCheckpointer`] stores under `{dir}/{thread_id}/`), so reused
480    /// ids cannot collide across threads. An implementation whose `put`
481    /// enforces globally unique ids, or whose storage path ignores
482    /// `checkpoint.thread_id`, **must override this method** (e.g. a SQL
483    /// backend with a global primary key would mint fresh ids or insert with
484    /// an explicit thread column).
485    ///
486    /// Delta-checkpoint backends (R0.7 wave 4) additionally override this to
487    /// write the forked checkpoints as **full snapshots**: a fork is a new
488    /// timeline and the natural compaction point, so time-travel reads on
489    /// the fork never fold a chain — and never another timeline's.
490    ///
491    /// Errors when the source thread has no checkpoints, when
492    /// `at_checkpoint_id` does not exist on the source thread, or when
493    /// `src_thread == dst_thread` (ids would collide within one thread).
494    async fn fork_thread(
495        &self,
496        src_thread: &str,
497        dst_thread: &str,
498        at_checkpoint_id: Option<&str>,
499    ) -> Result<usize> {
500        if src_thread == dst_thread {
501            return Err(RustyError::Checkpoint(format!(
502                "cannot fork thread `{src_thread}` onto itself: checkpoint ids would collide"
503            )));
504        }
505        let all = self.list(src_thread).await?;
506        if all.is_empty() {
507            return Err(RustyError::Checkpoint(format!(
508                "cannot fork thread `{src_thread}`: no checkpoints found"
509            )));
510        }
511        let selected: Vec<Checkpoint> = match at_checkpoint_id {
512            None => all,
513            Some(id) => {
514                let pos = all.iter().position(|c| c.id == id).ok_or_else(|| {
515                    RustyError::Checkpoint(format!(
516                        "cannot fork thread `{src_thread}`: unknown checkpoint id `{id}`"
517                    ))
518                })?;
519                all[..=pos].to_vec()
520            }
521        };
522        let copied = selected.len();
523        for mut checkpoint in selected {
524            checkpoint.thread_id = dst_thread.to_string();
525            self.put(checkpoint).await?;
526        }
527        tracing::info!(
528            src_thread = %src_thread,
529            dst_thread = %dst_thread,
530            copied = copied,
531            "thread history forked"
532        );
533        Ok(copied)
534    }
535}
536
537/// In-memory checkpointer: thread-safe (all operations take a single mutex
538/// over the store), lost on restart. Suitable for development, tests, and
539/// ephemeral runs.
540#[derive(Debug, Default, Clone)]
541pub struct InMemoryCheckpointer {
542    // thread_id -> checkpoints in insertion (super-step) order.
543    inner: Arc<Mutex<HashMap<String, Vec<Checkpoint>>>>,
544}
545
546impl InMemoryCheckpointer {
547    /// An empty store. Clones of the returned checkpointer share the same
548    /// underlying map.
549    pub fn new() -> Self {
550        Self::default()
551    }
552
553    fn lock(&self) -> Result<std::sync::MutexGuard<'_, HashMap<String, Vec<Checkpoint>>>> {
554        self.inner
555            .lock()
556            .map_err(|_| RustyError::Checkpoint("in-memory checkpointer lock poisoned".into()))
557    }
558}
559
560#[async_trait]
561impl Checkpointer for InMemoryCheckpointer {
562    async fn put(&self, checkpoint: Checkpoint) -> Result<()> {
563        let mut guard = self.lock()?;
564        let entry = guard.entry(checkpoint.thread_id.clone()).or_default();
565        if entry.iter().any(|c| c.id == checkpoint.id) {
566            return Err(RustyError::Checkpoint(format!(
567                "checkpoint id `{}` already exists for thread `{}`",
568                checkpoint.id, checkpoint.thread_id
569            )));
570        }
571        tracing::debug!(
572            thread_id = %checkpoint.thread_id,
573            checkpoint_id = %checkpoint.id,
574            step = checkpoint.step,
575            "checkpoint stored (in-memory)"
576        );
577        entry.push(checkpoint);
578        Ok(())
579    }
580
581    async fn get_latest(&self, thread_id: &str) -> Result<Option<Checkpoint>> {
582        let guard = self.lock()?;
583        Ok(guard.get(thread_id).and_then(|v| v.last()).cloned())
584    }
585
586    async fn list(&self, thread_id: &str) -> Result<Vec<Checkpoint>> {
587        let guard = self.lock()?;
588        let mut all = guard.get(thread_id).cloned().unwrap_or_default();
589        // Same total order as every other backend (ascending
590        // `(step, created_at, id)`), not raw insertion order: replay can
591        // append out-of-step-order checkpoints, and fork truncation must be
592        // deterministic across backends.
593        all.sort_by(|a, b| {
594            a.step
595                .cmp(&b.step)
596                .then(a.created_at.cmp(&b.created_at))
597                .then(a.id.cmp(&b.id))
598        });
599        Ok(all)
600    }
601}
602
603/// File-backed checkpointer: one pretty-printed JSON file per checkpoint
604/// (`{dir}/{thread_id}/{checkpoint_id}.json`) plus a `latest` pointer file
605/// (`{dir}/{thread_id}/latest` holding the most recent checkpoint id), using
606/// only `serde_json` and `tokio::fs` — no database dependencies.
607///
608/// Writes are atomic: payload is written to a uniquely named temp file in the
609/// same directory and then renamed over the target path, so a crash mid-write
610/// can never leave a truncated checkpoint file behind. Puts are serialized
611/// per thread (an in-process lock per `thread_id`), so concurrent same-thread
612/// puts cannot interleave the checkpoint file and pointer writes and leave
613/// `latest` pointing at the older checkpoint. The lock is per-process:
614/// multiple writer PROCESSES over the same directory are not serialized —
615/// treat one writer process per thread directory as a precondition.
616///
617/// Read paths are forgiving: a missing thread directory yields `None` / an
618/// empty list, a missing or corrupt `latest` pointer falls back to scanning
619/// the checkpoint files, and individual corrupt checkpoint files are skipped
620/// during scans. Genuine IO failures surface as
621/// [`RustyError::Checkpoint`].
622///
623/// # Delta checkpoints (R0.7 wave 4)
624///
625/// This backend opts into delta encoding: `put` diffs the incoming full
626/// snapshot against the thread's materialized head and stores only the
627/// channels that changed, bounded by a [`DeltaPolicy`]
628/// ([`JsonFileCheckpointer::with_delta_policy`] reconfigures or disables
629/// it). The head is cached in-process (`heads`), so the hot path diffs
630/// against the previous put's shared channel values — pointer-equal for
631/// unchanged channels, no re-read — and a cold process rebuilds the cache
632/// entry by reading the current chain once. Reads fold chains transparently
633/// ([`fold_chain`], `materialize_all`); checkpoint files with no `base`
634/// field (everything written before W4) load exactly as before.
635#[derive(Debug, Clone)]
636pub struct JsonFileCheckpointer {
637    dir: PathBuf,
638    // Per-thread put locks behind a map mutex: the map is locked only long
639    // enough to clone the per-thread `Arc`, never across the put itself.
640    put_locks: Arc<Mutex<HashMap<String, Arc<tokio::sync::Mutex<()>>>>>,
641    // The materialized chain head per thread, for the write-side delta
642    // diff. Coherent in-process because puts are serialized per thread (the
643    // same one-writer-process precondition the whole backend documents);
644    // readers never consult it.
645    heads: Arc<Mutex<HashMap<String, DeltaHead>>>,
646    policy: DeltaPolicy,
647}
648
649impl JsonFileCheckpointer {
650    /// A checkpointer rooted at `dir` (created lazily on first `put`), with
651    /// the default [`DeltaPolicy`] (delta encoding on, chain bounded at 32).
652    pub fn new(dir: impl Into<PathBuf>) -> Self {
653        Self::with_delta_policy(dir, DeltaPolicy::default())
654    }
655
656    /// A checkpointer rooted at `dir` with an explicit delta policy —
657    /// [`DeltaPolicy::full_only`] restores the pre-W4 full-snapshot write
658    /// behavior (the benchmark baseline).
659    pub fn with_delta_policy(dir: impl Into<PathBuf>, policy: DeltaPolicy) -> Self {
660        Self {
661            dir: dir.into(),
662            put_locks: Arc::new(Mutex::new(HashMap::new())),
663            heads: Arc::new(Mutex::new(HashMap::new())),
664            policy,
665        }
666    }
667
668    /// The delta-chain policy this checkpointer writes under.
669    pub fn delta_policy(&self) -> DeltaPolicy {
670        self.policy
671    }
672
673    /// The root directory checkpoints are stored under.
674    pub fn dir(&self) -> &std::path::Path {
675        &self.dir
676    }
677
678    /// The lock serializing `put` for one thread. `Clone`s of this
679    /// checkpointer share the same lock map, so clones still serialize
680    /// against each other.
681    fn put_lock(&self, thread_id: &str) -> Result<Arc<tokio::sync::Mutex<()>>> {
682        let mut map = self
683            .put_locks
684            .lock()
685            .map_err(|_| RustyError::Checkpoint("put-lock map poisoned".into()))?;
686        Ok(map
687            .entry(thread_id.to_owned())
688            .or_insert_with(|| Arc::new(tokio::sync::Mutex::new(())))
689            .clone())
690    }
691
692    /// `{dir}/{thread_id}/` — per-thread subdirectory.
693    fn thread_dir(&self, thread_id: &str) -> PathBuf {
694        self.dir.join(thread_id)
695    }
696
697    /// `{dir}/{thread_id}/{checkpoint_id}.json`.
698    fn checkpoint_path(&self, thread_id: &str, checkpoint_id: &str) -> PathBuf {
699        self.thread_dir(thread_id)
700            .join(format!("{checkpoint_id}.json"))
701    }
702
703    /// `{dir}/{thread_id}/latest` — pointer file holding the most recent
704    /// checkpoint id (plain text).
705    fn latest_path(&self, thread_id: &str) -> PathBuf {
706        self.thread_dir(thread_id).join("latest")
707    }
708
709    /// Atomically write `bytes` to `path` via a unique temp file + rename.
710    /// The temp file lives in the same directory so the rename stays on one
711    /// filesystem. Best-effort temp cleanup on failure.
712    ///
713    /// `pub(crate)`: the W4 artifact store (`journal::FileArtifactStore`)
714    /// writes blobs under the same discipline.
715    pub(crate) async fn atomic_write(path: &PathBuf, bytes: &[u8]) -> Result<()> {
716        let tmp = path.with_file_name(format!(
717            ".{}.tmp-{}",
718            path.file_name()
719                .map(|n| n.to_string_lossy().into_owned())
720                .unwrap_or_else(|| "checkpoint".into()),
721            uuid::Uuid::new_v4()
722        ));
723        if let Err(e) = tokio::fs::write(&tmp, bytes).await {
724            let _ = tokio::fs::remove_file(&tmp).await;
725            return Err(RustyError::Checkpoint(format!(
726                "failed to write temp file `{}`: {e}",
727                tmp.display()
728            )));
729        }
730        if let Err(e) = tokio::fs::rename(&tmp, path).await {
731            let _ = tokio::fs::remove_file(&tmp).await;
732            return Err(RustyError::Checkpoint(format!(
733                "failed to rename `{}` -> `{}`: {e}",
734                tmp.display(),
735                path.display()
736            )));
737        }
738        Ok(())
739    }
740
741    /// Read and deserialize one checkpoint file, mapping IO and JSON errors
742    /// to [`RustyError::Checkpoint`].
743    async fn read_checkpoint(path: &PathBuf) -> Result<Checkpoint> {
744        let bytes = tokio::fs::read(path).await.map_err(|e| {
745            RustyError::Checkpoint(format!(
746                "failed to read checkpoint file `{}`: {e}",
747                path.display()
748            ))
749        })?;
750        serde_json::from_slice(&bytes).map_err(|e| {
751            RustyError::Checkpoint(format!("corrupt checkpoint file `{}`: {e}", path.display()))
752        })
753    }
754
755    /// Load every parseable `*.json` checkpoint in a thread directory,
756    /// **unfolded** (a delta checkpoint stays a delta here — folding happens
757    /// in the read methods above this layer). A missing directory yields an
758    /// empty vec; corrupt files are skipped.
759    async fn scan_thread_raw(&self, thread_id: &str) -> Result<Vec<Checkpoint>> {
760        let dir = self.thread_dir(thread_id);
761        let mut entries = match tokio::fs::read_dir(&dir).await {
762            Ok(entries) => entries,
763            Err(e) if e.kind() == std::io::ErrorKind::NotFound => return Ok(Vec::new()),
764            Err(e) => {
765                return Err(RustyError::Checkpoint(format!(
766                    "failed to read thread directory `{}`: {e}",
767                    dir.display()
768                )))
769            }
770        };
771
772        let mut checkpoints = Vec::new();
773        loop {
774            let entry = match entries.next_entry().await {
775                Ok(Some(entry)) => entry,
776                Ok(None) => break,
777                Err(e) => {
778                    return Err(RustyError::Checkpoint(format!(
779                        "failed to iterate thread directory `{}`: {e}",
780                        dir.display()
781                    )))
782                }
783            };
784            let path = entry.path();
785            let is_json = path.extension().is_some_and(|ext| ext == "json");
786            if !is_json {
787                continue;
788            }
789            match Self::read_checkpoint(&path).await {
790                Ok(cp) => checkpoints.push(cp),
791                // Graceful degradation: one corrupt file must not poison the
792                // whole thread's history.
793                Err(e) => {
794                    tracing::warn!(
795                        thread_id = %thread_id,
796                        path = %path.display(),
797                        error = %e,
798                        "skipping corrupt checkpoint file during scan"
799                    );
800                    continue;
801                }
802            }
803        }
804        Ok(checkpoints)
805    }
806
807    /// The most recently stored raw checkpoint (unfolded — possibly a
808    /// delta): the `latest` pointer fast path, falling back to a directory
809    /// scan when the pointer is missing, corrupt, or dangling.
810    async fn read_latest_raw(&self, thread_id: &str) -> Result<Option<Checkpoint>> {
811        let latest_path = self.latest_path(thread_id);
812        if let Ok(id_bytes) = tokio::fs::read(&latest_path).await {
813            if let Ok(id) = std::str::from_utf8(&id_bytes) {
814                let id = id.trim();
815                if !id.is_empty() {
816                    let path = self.checkpoint_path(thread_id, id);
817                    match Self::read_checkpoint(&path).await {
818                        Ok(cp) => return Ok(Some(cp)),
819                        Err(e) => tracing::warn!(
820                            thread_id = %thread_id,
821                            path = %path.display(),
822                            error = %e,
823                            "latest pointer target unreadable; falling back to directory scan"
824                        ),
825                    }
826                }
827            }
828        }
829        // Fallback: the checkpoint with the greatest `created_at` — the
830        // insertion-order proxy shared with the other backends (see the
831        // trait's `get_latest` contract), not the highest step, so a replay
832        // that appended lower-step checkpoints still resumes the newest
833        // timeline.
834        Ok(self
835            .scan_thread_raw(thread_id)
836            .await?
837            .into_iter()
838            .max_by(|a, b| a.created_at.cmp(&b.created_at).then(a.id.cmp(&b.id))))
839    }
840
841    /// Load the raw delta chain ending at `tip`, root-first. Defensively
842    /// bounded: writes cap chains at the policy bound, so a chain far past
843    /// it means corruption or a foreign writer — and a cycle is always
844    /// corruption. Both error rather than fold forever.
845    async fn load_chain(&self, thread_id: &str, tip: Checkpoint) -> Result<Vec<Checkpoint>> {
846        // The fold bound: generous headroom over the write bound, so any
847        // chain this backend could have written folds, and only corrupt or
848        // foreign chains hit the limit.
849        let fold_bound = self.policy.max_chain_len.saturating_mul(4).max(128);
850        let mut chain = vec![tip];
851        let mut visited = HashSet::new();
852        while let Some(base_id) = chain.last().expect("chain starts non-empty").base.clone() {
853            if !visited.insert(base_id.clone()) {
854                return Err(RustyError::Checkpoint(format!(
855                    "checkpoint delta chain in thread `{thread_id}` has a cycle at `{base_id}`"
856                )));
857            }
858            if chain.len() > fold_bound {
859                return Err(RustyError::Checkpoint(format!(
860                    "checkpoint delta chain in thread `{thread_id}` exceeds {fold_bound} links; \
861                     refusing to fold (write bound is {})",
862                    self.policy.max_chain_len
863                )));
864            }
865            let path = self.checkpoint_path(thread_id, &base_id);
866            chain.push(Self::read_checkpoint(&path).await?);
867        }
868        chain.reverse();
869        Ok(chain)
870    }
871
872    /// The thread's materialized chain head for the write-side delta diff:
873    /// cached, or rebuilt by reading and folding the current chain (a cold
874    /// process pays this once per thread). `None` when the thread has no
875    /// checkpoints.
876    async fn head_of(&self, thread_id: &str) -> Result<Option<DeltaHead>> {
877        if let Some(head) = self.lock_heads()?.get(thread_id) {
878            return Ok(Some(head.clone()));
879        }
880        let Some(raw) = self.read_latest_raw(thread_id).await? else {
881            return Ok(None);
882        };
883        let chain = self.load_chain(thread_id, raw).await?;
884        let head = DeltaHead {
885            chain_len: chain.len() - 1,
886            checkpoint: fold_chain(&chain)?,
887        };
888        self.lock_heads()?
889            .insert(thread_id.to_owned(), head.clone());
890        Ok(Some(head))
891    }
892
893    fn lock_heads(&self) -> Result<std::sync::MutexGuard<'_, HashMap<String, DeltaHead>>> {
894        self.heads
895            .lock()
896            .map_err(|_| RustyError::Checkpoint("delta-head cache poisoned".into()))
897    }
898
899    /// The shared write path. `force_full` stores the checkpoint as a full
900    /// snapshot regardless of policy — the fork compaction semantics
901    /// ([`Checkpointer::fork_thread`]).
902    async fn put_internal(&self, checkpoint: Checkpoint, force_full: bool) -> Result<()> {
903        // Serialize the whole put (checkpoint file THEN pointer file) per
904        // thread: without this, two concurrent same-thread puts can
905        // interleave (file A, file B, pointer B, pointer A) and leave
906        // `latest` pointing at the older checkpoint. Held across `.await`s,
907        // hence a tokio mutex — a std guard would make the future `!Send`.
908        let lock = self.put_lock(&checkpoint.thread_id)?;
909        let _put_guard = lock.lock().await;
910
911        let thread_dir = self.thread_dir(&checkpoint.thread_id);
912        tokio::fs::create_dir_all(&thread_dir).await.map_err(|e| {
913            RustyError::Checkpoint(format!(
914                "failed to create thread directory `{}`: {e}",
915                thread_dir.display()
916            ))
917        })?;
918
919        let path = self.checkpoint_path(&checkpoint.thread_id, &checkpoint.id);
920        // Preserve the no-overwrite contract: checkpoint ids are unique by
921        // construction, so an existing file means a duplicate `put`.
922        if tokio::fs::try_exists(&path).await.map_err(|e| {
923            RustyError::Checkpoint(format!(
924                "failed to stat checkpoint file `{}`: {e}",
925                path.display()
926            ))
927        })? {
928            return Err(RustyError::Checkpoint(format!(
929                "checkpoint id `{}` already exists for thread `{}`",
930                checkpoint.id, checkpoint.thread_id
931            )));
932        }
933
934        // Delta encoding (W4): diff the incoming full snapshot against the
935        // thread's materialized head and store only the channels that
936        // changed, bounded by the chain policy. The encoded file is what
937        // later reads fold back.
938        let encoding = if force_full {
939            DeltaEncoding::full(&checkpoint)
940        } else {
941            let head = self.head_of(&checkpoint.thread_id).await?;
942            encode_delta(&checkpoint, head.as_ref(), &self.policy)
943        };
944
945        let bytes = serde_json::to_vec_pretty(&encoding.checkpoint)?;
946        Self::atomic_write(&path, &bytes).await?;
947
948        // Update the latest pointer (also atomically). Written after the
949        // checkpoint file itself so a crash never leaves a dangling pointer.
950        Self::atomic_write(
951            &self.latest_path(&checkpoint.thread_id),
952            checkpoint.id.as_bytes(),
953        )
954        .await?;
955
956        tracing::debug!(
957            thread_id = %checkpoint.thread_id,
958            checkpoint_id = %checkpoint.id,
959            step = checkpoint.step,
960            delta = encoding.checkpoint.base.is_some(),
961            path = %path.display(),
962            "checkpoint persisted (json file)"
963        );
964
965        // The next put diffs against THIS put's full state, held shared:
966        // channels the next step does not write stay pointer-identical,
967        // which is what makes the diff cheap.
968        self.lock_heads()?.insert(
969            checkpoint.thread_id.clone(),
970            DeltaHead {
971                checkpoint,
972                chain_len: encoding.chain_len,
973            },
974        );
975        Ok(())
976    }
977}
978
979#[async_trait]
980impl Checkpointer for JsonFileCheckpointer {
981    async fn put(&self, checkpoint: Checkpoint) -> Result<()> {
982        self.put_internal(checkpoint, false).await
983    }
984
985    async fn get_latest(&self, thread_id: &str) -> Result<Option<Checkpoint>> {
986        let Some(raw) = self.read_latest_raw(thread_id).await? else {
987            return Ok(None);
988        };
989        if raw.base.is_none() {
990            // A full snapshot — everything written before W4, chain roots,
991            // forked checkpoints — needs no folding.
992            return Ok(Some(raw));
993        }
994        let chain = self.load_chain(thread_id, raw).await?;
995        fold_chain(&chain).map(Some)
996    }
997
998    async fn list(&self, thread_id: &str) -> Result<Vec<Checkpoint>> {
999        // Fold every delta chain, then impose the same total order as every
1000        // other backend (ascending `(step, created_at, id)`), not raw file
1001        // order: replay can append out-of-step-order checkpoints, and fork
1002        // truncation must be deterministic across backends.
1003        let mut all = materialize_all(self.scan_thread_raw(thread_id).await?);
1004        all.sort_by(|a, b| {
1005            a.step
1006                .cmp(&b.step)
1007                .then(a.created_at.cmp(&b.created_at))
1008                .then(a.id.cmp(&b.id))
1009        });
1010        Ok(all)
1011    }
1012
1013    /// Forked histories are written as **full snapshots** (eager
1014    /// compaction): a fork is a new timeline and the natural compaction
1015    /// point, so time-travel reads on the fork never fold a chain — and
1016    /// never another timeline's. The source thread is untouched.
1017    async fn fork_thread(
1018        &self,
1019        src_thread: &str,
1020        dst_thread: &str,
1021        at_checkpoint_id: Option<&str>,
1022    ) -> Result<usize> {
1023        if src_thread == dst_thread {
1024            return Err(RustyError::Checkpoint(format!(
1025                "cannot fork thread `{src_thread}` onto itself: checkpoint ids would collide"
1026            )));
1027        }
1028        let all = self.list(src_thread).await?;
1029        if all.is_empty() {
1030            return Err(RustyError::Checkpoint(format!(
1031                "cannot fork thread `{src_thread}`: no checkpoints found"
1032            )));
1033        }
1034        let selected: Vec<Checkpoint> = match at_checkpoint_id {
1035            None => all,
1036            Some(id) => {
1037                let pos = all.iter().position(|c| c.id == id).ok_or_else(|| {
1038                    RustyError::Checkpoint(format!(
1039                        "cannot fork thread `{src_thread}`: unknown checkpoint id `{id}`"
1040                    ))
1041                })?;
1042                all[..=pos].to_vec()
1043            }
1044        };
1045        let copied = selected.len();
1046        for mut checkpoint in selected {
1047            checkpoint.thread_id = dst_thread.to_string();
1048            checkpoint.base = None;
1049            self.put_internal(checkpoint, true).await?;
1050        }
1051        tracing::info!(
1052            src_thread = %src_thread,
1053            dst_thread = %dst_thread,
1054            copied = copied,
1055            "thread history forked"
1056        );
1057        Ok(copied)
1058    }
1059}
1060
1061#[cfg(test)]
1062mod tests {
1063    use super::*;
1064
1065    fn cp(thread: &str, step: usize) -> Checkpoint {
1066        Checkpoint::new(thread, step, State::new(), vec!["next".into()])
1067    }
1068
1069    #[tokio::test]
1070    async fn in_memory_roundtrip() {
1071        let store = InMemoryCheckpointer::new();
1072        assert!(store.get_latest("t1").await.unwrap().is_none());
1073        assert!(store.list("t1").await.unwrap().is_empty());
1074
1075        store.put(cp("t1", 0)).await.unwrap();
1076        store.put(cp("t1", 1)).await.unwrap();
1077        store.put(cp("t2", 0)).await.unwrap();
1078
1079        let latest = store.get_latest("t1").await.unwrap().unwrap();
1080        assert_eq!(latest.step, 1);
1081        assert_eq!(latest.next_nodes, vec!["next".to_string()]);
1082
1083        let all = store.list("t1").await.unwrap();
1084        assert_eq!(all.len(), 2);
1085        assert_eq!(all[0].step, 0);
1086        assert_eq!(all[1].step, 1);
1087
1088        // Threads are isolated.
1089        assert_eq!(store.list("t2").await.unwrap().len(), 1);
1090    }
1091
1092    #[tokio::test]
1093    async fn in_memory_rejects_duplicate_id() {
1094        let store = InMemoryCheckpointer::new();
1095        let checkpoint = cp("t1", 0);
1096        store.put(checkpoint.clone()).await.unwrap();
1097        let err = store.put(checkpoint).await.unwrap_err();
1098        assert!(matches!(err, RustyError::Checkpoint(_)));
1099    }
1100
1101    #[tokio::test]
1102    async fn checkpoint_serializes() {
1103        let checkpoint = cp("t1", 2);
1104        let json = serde_json::to_string(&checkpoint).unwrap();
1105        let back: Checkpoint = serde_json::from_str(&json).unwrap();
1106        assert_eq!(back.id, checkpoint.id);
1107        assert_eq!(back.step, 2);
1108    }
1109
1110    /// Unique temp root under the OS temp dir, removed on drop.
1111    struct TestDir(PathBuf);
1112
1113    impl TestDir {
1114        fn new() -> Self {
1115            Self(
1116                std::env::temp_dir()
1117                    .join(format!("rusty-checkpoint-test-{}", uuid::Uuid::new_v4())),
1118            )
1119        }
1120    }
1121
1122    impl Drop for TestDir {
1123        fn drop(&mut self) {
1124            let _ = std::fs::remove_dir_all(&self.0);
1125        }
1126    }
1127
1128    #[tokio::test]
1129    async fn json_file_roundtrip() {
1130        let tmp = TestDir::new();
1131        let store = JsonFileCheckpointer::new(tmp.0.clone());
1132
1133        assert!(store.get_latest("t1").await.unwrap().is_none());
1134        assert!(store.list("t1").await.unwrap().is_empty());
1135
1136        let mut state = State::new();
1137        state.insert("answer", serde_json::json!(42));
1138        let cp0 = Checkpoint::new("t1", 0, state.clone(), vec!["node_b".into()]);
1139        let id0 = cp0.id.clone();
1140        store.put(cp0).await.unwrap();
1141
1142        // File layout: <root>/<thread_id>/<checkpoint_id>.json
1143        assert!(tmp.0.join("t1").join(format!("{id0}.json")).exists());
1144
1145        let back = store.get_latest("t1").await.unwrap().unwrap();
1146        assert_eq!(back.id, id0);
1147        assert_eq!(back.thread_id, "t1");
1148        assert_eq!(back.step, 0);
1149        assert_eq!(back.state, state);
1150        assert_eq!(back.next_nodes, vec!["node_b".to_string()]);
1151
1152        // Threads are isolated.
1153        assert!(store.get_latest("t2").await.unwrap().is_none());
1154    }
1155
1156    #[tokio::test]
1157    async fn json_file_latest_pointer_tracks_most_recent_put() {
1158        let tmp = TestDir::new();
1159        let store = JsonFileCheckpointer::new(tmp.0.clone());
1160
1161        store.put(cp("t1", 0)).await.unwrap();
1162        let cp1 = cp("t1", 1);
1163        let id1 = cp1.id.clone();
1164        store.put(cp1).await.unwrap();
1165
1166        // The pointer file holds the most recent checkpoint id as text.
1167        let pointer = std::fs::read_to_string(tmp.0.join("t1").join("latest")).unwrap();
1168        assert_eq!(pointer, id1);
1169
1170        let latest = store.get_latest("t1").await.unwrap().unwrap();
1171        assert_eq!(latest.id, id1);
1172        assert_eq!(latest.step, 1);
1173    }
1174
1175    #[tokio::test]
1176    async fn json_file_list_sorted_by_step_regardless_of_put_order() {
1177        let tmp = TestDir::new();
1178        let store = JsonFileCheckpointer::new(tmp.0.clone());
1179
1180        store.put(cp("t1", 2)).await.unwrap();
1181        store.put(cp("t1", 0)).await.unwrap();
1182        store.put(cp("t1", 1)).await.unwrap();
1183
1184        let all = store.list("t1").await.unwrap();
1185        assert_eq!(all.len(), 3);
1186        assert_eq!(all[0].step, 0);
1187        assert_eq!(all[1].step, 1);
1188        assert_eq!(all[2].step, 2);
1189
1190        // Recency is insertion order, not highest step: the pointer tracks
1191        // the most recent put (step 1), and the scan fallback agrees because
1192        // the freshest `created_at` is also the last put's.
1193        let latest = store.get_latest("t1").await.unwrap().unwrap();
1194        assert_eq!(latest.step, 1);
1195    }
1196
1197    /// The `get_latest`/`list` contract is backend-independent: recency =
1198    /// insertion order, listing = ascending `(step, created_at, id)`. Every
1199    /// `Checkpointer` impl must agree with this test.
1200    #[tokio::test]
1201    async fn recency_and_list_order_agree_across_backends() {
1202        let tmp = TestDir::new();
1203        let memory = InMemoryCheckpointer::new();
1204        let json_file = JsonFileCheckpointer::new(tmp.0.clone());
1205
1206        // Out-of-step-order puts (as replay-on-same-thread produces): each
1207        // checkpoint is minted fresh, so `created_at` increases per put.
1208        let steps = [2usize, 0, 1];
1209        for step in steps {
1210            memory.put(cp("t1", step)).await.unwrap();
1211            json_file.put(cp("t1", step)).await.unwrap();
1212        }
1213
1214        let stores: [&dyn Checkpointer; 2] = [&memory, &json_file];
1215        for store in stores {
1216            // Latest = last put (step 1), not highest step (step 2).
1217            let latest = store.get_latest("t1").await.unwrap().unwrap();
1218            assert_eq!(latest.step, 1, "backend disagrees on recency");
1219            // List = ascending step order regardless of put order.
1220            let listed: Vec<usize> = store
1221                .list("t1")
1222                .await
1223                .unwrap()
1224                .iter()
1225                .map(|c| c.step)
1226                .collect();
1227            assert_eq!(listed, [0, 1, 2], "backend disagrees on list order");
1228        }
1229    }
1230
1231    #[tokio::test]
1232    async fn json_file_missing_thread_returns_none_and_empty() {
1233        let tmp = TestDir::new();
1234        let store = JsonFileCheckpointer::new(tmp.0.clone());
1235
1236        assert!(store.get_latest("never-seen").await.unwrap().is_none());
1237        assert!(store.list("never-seen").await.unwrap().is_empty());
1238    }
1239
1240    #[tokio::test]
1241    async fn json_file_rejects_duplicate_id() {
1242        let tmp = TestDir::new();
1243        let store = JsonFileCheckpointer::new(tmp.0.clone());
1244
1245        let checkpoint = cp("t1", 0);
1246        store.put(checkpoint.clone()).await.unwrap();
1247        let err = store.put(checkpoint).await.unwrap_err();
1248        assert!(matches!(err, RustyError::Checkpoint(_)));
1249    }
1250
1251    #[tokio::test]
1252    async fn json_file_durable_across_instances() {
1253        let tmp = TestDir::new();
1254        let cp0 = cp("t1", 0);
1255        let id0 = cp0.id.clone();
1256
1257        JsonFileCheckpointer::new(tmp.0.clone())
1258            .put(cp0)
1259            .await
1260            .unwrap();
1261
1262        // A fresh instance over the same root sees the checkpoint
1263        // (simulates process restart).
1264        let reopened = JsonFileCheckpointer::new(tmp.0.clone());
1265        let latest = reopened.get_latest("t1").await.unwrap().unwrap();
1266        assert_eq!(latest.id, id0);
1267        assert_eq!(reopened.list("t1").await.unwrap().len(), 1);
1268    }
1269
1270    #[tokio::test]
1271    async fn json_file_corrupt_files_are_handled_gracefully() {
1272        let tmp = TestDir::new();
1273        let store = JsonFileCheckpointer::new(tmp.0.clone());
1274
1275        let good = cp("t1", 0);
1276        let good_id = good.id.clone();
1277        store.put(good).await.unwrap();
1278
1279        // A corrupt checkpoint file next to a valid one must not break
1280        // list/get_latest.
1281        std::fs::write(tmp.0.join("t1").join("garbage.json"), b"{not json!!").unwrap();
1282        let all = store.list("t1").await.unwrap();
1283        assert_eq!(all.len(), 1);
1284        assert_eq!(all[0].id, good_id);
1285
1286        // A corrupt latest pointer falls back to scanning.
1287        std::fs::write(tmp.0.join("t1").join("latest"), b"no-such-checkpoint-id").unwrap();
1288        let latest = store.get_latest("t1").await.unwrap().unwrap();
1289        assert_eq!(latest.id, good_id);
1290
1291        // Garbage bytes in the pointer also fall back to scanning.
1292        std::fs::write(tmp.0.join("t1").join("latest"), [0xff, 0xfe, 0x00]).unwrap();
1293        let latest = store.get_latest("t1").await.unwrap().unwrap();
1294        assert_eq!(latest.id, good_id);
1295    }
1296
1297    #[tokio::test]
1298    async fn get_by_id_hit_and_miss() {
1299        let store = InMemoryCheckpointer::new();
1300        let cp0 = cp("t1", 0);
1301        let id0 = cp0.id.clone();
1302        store.put(cp0).await.unwrap();
1303        store.put(cp("t1", 1)).await.unwrap();
1304        store.put(cp("t2", 0)).await.unwrap();
1305
1306        let hit = store.get_by_id("t1", &id0).await.unwrap().unwrap();
1307        assert_eq!(hit.id, id0);
1308        assert_eq!(hit.step, 0);
1309        assert_eq!(hit.thread_id, "t1");
1310
1311        // Unknown id on an existing thread, and any id on an unknown thread.
1312        assert!(store.get_by_id("t1", "no-such-id").await.unwrap().is_none());
1313        assert!(store.get_by_id("t2", &id0).await.unwrap().is_none());
1314        assert!(store.get_by_id("never-seen", &id0).await.unwrap().is_none());
1315    }
1316
1317    #[tokio::test]
1318    async fn fork_full_history_copies_all_checkpoints() {
1319        let store = InMemoryCheckpointer::new();
1320        let mut src = Vec::new();
1321        for step in 0..3 {
1322            let mut state = State::new();
1323            state.insert("n", serde_json::json!(step));
1324            let checkpoint = Checkpoint::new("src", step, state, vec!["next".into()]);
1325            src.push(checkpoint.clone());
1326            store.put(checkpoint).await.unwrap();
1327        }
1328
1329        let copied = store.fork_thread("src", "dst", None).await.unwrap();
1330        assert_eq!(copied, 3);
1331
1332        let dst = store.list("dst").await.unwrap();
1333        assert_eq!(dst.len(), 3);
1334        for (forked, original) in dst.iter().zip(src.iter()) {
1335            // Everything is preserved except the thread id (ids may be reused
1336            // across threads; uniqueness is per-thread).
1337            assert_eq!(forked.id, original.id);
1338            assert_eq!(forked.step, original.step);
1339            assert_eq!(forked.state, original.state);
1340            assert_eq!(forked.next_nodes, original.next_nodes);
1341            assert_eq!(forked.created_at, original.created_at);
1342            assert_eq!(forked.thread_id, "dst");
1343        }
1344        assert_eq!(store.get_latest("dst").await.unwrap().unwrap().step, 2);
1345
1346        // The source thread is untouched.
1347        assert_eq!(store.list("src").await.unwrap().len(), 3);
1348    }
1349
1350    #[tokio::test]
1351    async fn fork_at_mid_checkpoint_truncates_history() {
1352        let store = InMemoryCheckpointer::new();
1353        let mut ids = Vec::new();
1354        for step in 0..4 {
1355            let checkpoint = cp("src", step);
1356            ids.push(checkpoint.id.clone());
1357            store.put(checkpoint).await.unwrap();
1358        }
1359
1360        // Fork at the step-1 checkpoint: only steps 0 and 1 are copied.
1361        let copied = store
1362            .fork_thread("src", "dst", Some(&ids[1]))
1363            .await
1364            .unwrap();
1365        assert_eq!(copied, 2);
1366
1367        let dst = store.list("dst").await.unwrap();
1368        assert_eq!(dst.len(), 2);
1369        assert_eq!(dst[0].id, ids[0]);
1370        assert_eq!(dst[1].id, ids[1]);
1371        assert_eq!(dst[0].step, 0);
1372        assert_eq!(dst[1].step, 1);
1373        // Latest of the fork is the cut point, not the source's head.
1374        assert_eq!(store.get_latest("dst").await.unwrap().unwrap().id, ids[1]);
1375    }
1376
1377    #[tokio::test]
1378    async fn fork_errors_on_empty_src_unknown_id_and_self_fork() {
1379        let store = InMemoryCheckpointer::new();
1380        let checkpoint = cp("src", 0);
1381        let id0 = checkpoint.id.clone();
1382        store.put(checkpoint).await.unwrap();
1383
1384        let err = store.fork_thread("empty", "dst", None).await.unwrap_err();
1385        assert!(matches!(err, RustyError::Checkpoint(_)));
1386
1387        let err = store
1388            .fork_thread("src", "dst", Some("no-such-id"))
1389            .await
1390            .unwrap_err();
1391        assert!(matches!(err, RustyError::Checkpoint(_)));
1392
1393        let err = store
1394            .fork_thread("src", "src", Some(&id0))
1395            .await
1396            .unwrap_err();
1397        assert!(matches!(err, RustyError::Checkpoint(_)));
1398
1399        // Failed forks leave no partial state behind on the destination.
1400        assert!(store.list("dst").await.unwrap().is_empty());
1401    }
1402
1403    #[tokio::test]
1404    async fn json_file_fork_across_threads_persists_correctly() {
1405        let tmp = TestDir::new();
1406        let store = JsonFileCheckpointer::new(tmp.0.clone());
1407
1408        let mut ids = Vec::new();
1409        for step in 0..3 {
1410            let mut state = State::new();
1411            state.insert("n", serde_json::json!(step));
1412            let checkpoint = Checkpoint::new("src", step, state, vec!["next".into()]);
1413            ids.push(checkpoint.id.clone());
1414            store.put(checkpoint).await.unwrap();
1415        }
1416
1417        let copied = store
1418            .fork_thread("src", "dst", Some(&ids[1]))
1419            .await
1420            .unwrap();
1421        assert_eq!(copied, 2);
1422
1423        // Files land under the destination thread's own directory (reused
1424        // ids live in a different path, so no collision).
1425        assert!(tmp.0.join("dst").join(format!("{}.json", ids[0])).exists());
1426        assert!(tmp.0.join("dst").join(format!("{}.json", ids[1])).exists());
1427        assert!(!tmp.0.join("dst").join(format!("{}.json", ids[2])).exists());
1428
1429        // The forked files carry the destination thread id in their payload.
1430        let latest = store.get_latest("dst").await.unwrap().unwrap();
1431        assert_eq!(latest.id, ids[1]);
1432        assert_eq!(latest.thread_id, "dst");
1433        assert_eq!(latest.step, 1);
1434
1435        // Durable across instances (process restart): the fork survives.
1436        let reopened = JsonFileCheckpointer::new(tmp.0.clone());
1437        let dst = reopened.list("dst").await.unwrap();
1438        assert_eq!(dst.len(), 2);
1439        assert_eq!(dst[0].id, ids[0]);
1440        assert_eq!(dst[1].id, ids[1]);
1441        assert!(dst.iter().all(|c| c.thread_id == "dst"));
1442
1443        // The source thread is untouched.
1444        assert_eq!(reopened.list("src").await.unwrap().len(), 3);
1445        assert_eq!(
1446            reopened.get_latest("src").await.unwrap().unwrap().id,
1447            ids[2]
1448        );
1449    }
1450
1451    // ---- Delta checkpoints (R0.7 wave 4) ----
1452
1453    /// A state whose `blob` channel stays constant while `step` turns over —
1454    /// the shape delta checkpoints exist for.
1455    fn evolving_state(step: usize, blob: &str) -> State {
1456        let mut state = State::new();
1457        state.insert("blob", serde_json::json!(blob));
1458        state.insert("step", serde_json::json!(step));
1459        state
1460    }
1461
1462    /// Read one checkpoint file straight off disk as raw JSON.
1463    fn file_json(tmp: &TestDir, thread: &str, id: &str) -> serde_json::Value {
1464        let text = std::fs::read_to_string(tmp.0.join(thread).join(format!("{id}.json"))).unwrap();
1465        serde_json::from_str(&text).unwrap()
1466    }
1467
1468    #[tokio::test]
1469    async fn delta_chain_roundtrips_through_read_paths() {
1470        let tmp = TestDir::new();
1471        let store = JsonFileCheckpointer::new(tmp.0.clone());
1472        let blob = "x".repeat(1024);
1473
1474        let mut ids = Vec::new();
1475        for step in 0..5 {
1476            let cp = Checkpoint::new("t1", step, evolving_state(step, &blob), vec!["next".into()]);
1477            ids.push(cp.id.clone());
1478            store.put(cp).await.unwrap();
1479        }
1480
1481        // Puts after the first are deltas: `base` names the previous
1482        // checkpoint and `state` carries only the changed `step` channel.
1483        let on_disk = file_json(&tmp, "t1", &ids[2]);
1484        assert_eq!(on_disk["base"], serde_json::json!(ids[1]));
1485        assert_eq!(
1486            on_disk["state"],
1487            serde_json::json!({"step": 2}),
1488            "delta file must carry only changed channels"
1489        );
1490
1491        // Reads materialize: get_latest folds the chain back to full state.
1492        let latest = store.get_latest("t1").await.unwrap().unwrap();
1493        assert_eq!(latest.base, None, "read methods never return a delta");
1494        assert_eq!(latest.state, evolving_state(4, &blob));
1495
1496        // list materializes every link.
1497        let all = store.list("t1").await.unwrap();
1498        assert_eq!(all.len(), 5);
1499        for (step, cp) in all.iter().enumerate() {
1500            assert_eq!(cp.state, evolving_state(step, &blob));
1501            assert_eq!(cp.base, None);
1502        }
1503
1504        // get_by_id (trait default, over list) materializes mid-chain links.
1505        let mid = store.get_by_id("t1", &ids[1]).await.unwrap().unwrap();
1506        assert_eq!(mid.state, evolving_state(1, &blob));
1507    }
1508
1509    #[tokio::test]
1510    async fn delta_chain_is_bounded_by_policy() {
1511        let tmp = TestDir::new();
1512        let policy = DeltaPolicy {
1513            max_chain_len: 3,
1514            ..DeltaPolicy::default()
1515        };
1516        let store = JsonFileCheckpointer::with_delta_policy(tmp.0.clone(), policy);
1517
1518        let mut ids = Vec::new();
1519        for step in 0..7 {
1520            let cp = Checkpoint::new("t1", step, evolving_state(step, "b"), vec![]);
1521            ids.push(cp.id.clone());
1522            store.put(cp).await.unwrap();
1523        }
1524
1525        // Chain: full, delta, delta, delta, FULL (bound hit), delta, delta.
1526        let expect_full = [true, false, false, false, true, false, false];
1527        for (i, id) in ids.iter().enumerate() {
1528            let on_disk = file_json(&tmp, "t1", id);
1529            assert_eq!(
1530                on_disk.get("base").is_some(),
1531                !expect_full[i],
1532                "checkpoint {i} full/delta mismatch: {on_disk}"
1533            );
1534        }
1535        // Reads are unaffected by where the chain compacted.
1536        let all = store.list("t1").await.unwrap();
1537        for (step, cp) in all.iter().enumerate() {
1538            assert_eq!(cp.state, evolving_state(step, "b"));
1539        }
1540    }
1541
1542    #[tokio::test]
1543    async fn delta_byte_ratio_forces_full_when_delta_stops_paying() {
1544        let tmp = TestDir::new();
1545        let policy = DeltaPolicy {
1546            max_chain_len: 32,
1547            max_byte_ratio: 0.5,
1548        };
1549        let store = JsonFileCheckpointer::with_delta_policy(tmp.0.clone(), policy);
1550
1551        let base_state = State::from_value(serde_json::json!({"a": "AAAA", "b": "BBBB"})).unwrap();
1552        let cp0 = Checkpoint::new("t1", 0, base_state, vec![]);
1553        let id0 = cp0.id.clone();
1554        store.put(cp0).await.unwrap();
1555
1556        // Every channel changed: the delta is the whole state — past the
1557        // 0.5 ratio, so a full snapshot is written instead of a chain link.
1558        let changed = State::from_value(serde_json::json!({"a": "CCCC", "b": "DDDD"})).unwrap();
1559        let cp1 = Checkpoint::new("t1", 1, changed, vec![]);
1560        let id1 = cp1.id.clone();
1561        store.put(cp1).await.unwrap();
1562
1563        assert!(file_json(&tmp, "t1", &id0).get("base").is_none());
1564        assert!(
1565            file_json(&tmp, "t1", &id1).get("base").is_none(),
1566            "a delta worth ~full must reset the chain"
1567        );
1568        assert_eq!(
1569            store.get_latest("t1").await.unwrap().unwrap().state,
1570            State::from_value(serde_json::json!({"a": "CCCC", "b": "DDDD"})).unwrap()
1571        );
1572    }
1573
1574    #[tokio::test]
1575    async fn delta_dedupes_equal_content_without_pointer_sharing() {
1576        let tmp = TestDir::new();
1577        let store = JsonFileCheckpointer::new(tmp.0.clone());
1578
1579        store
1580            .put(Checkpoint::new(
1581                "t1",
1582                0,
1583                State::from_value(serde_json::json!({"k": "v"})).unwrap(),
1584                vec![],
1585            ))
1586            .await
1587            .unwrap();
1588        // A fresh, independently built state with identical content: no
1589        // pointer sharing, so only value equality can dedupe it.
1590        let cp1 = Checkpoint::new(
1591            "t1",
1592            1,
1593            State::from_value(serde_json::json!({"k": "v"})).unwrap(),
1594            vec![],
1595        );
1596        let id1 = cp1.id.clone();
1597        store.put(cp1).await.unwrap();
1598
1599        let on_disk = file_json(&tmp, "t1", &id1);
1600        assert!(on_disk.get("base").is_some());
1601        assert_eq!(
1602            on_disk["state"],
1603            serde_json::json!({}),
1604            "identical content must produce an empty delta"
1605        );
1606        assert_eq!(
1607            store.get_latest("t1").await.unwrap().unwrap().state,
1608            State::from_value(serde_json::json!({"k": "v"})).unwrap()
1609        );
1610    }
1611
1612    #[tokio::test]
1613    async fn reopened_store_rebuilds_the_head_and_keeps_differencing() {
1614        let tmp = TestDir::new();
1615        let blob = "y".repeat(512);
1616
1617        let id0;
1618        {
1619            let store = JsonFileCheckpointer::new(tmp.0.clone());
1620            let cp = Checkpoint::new("t1", 0, evolving_state(0, &blob), vec![]);
1621            id0 = cp.id.clone();
1622            store.put(cp).await.unwrap();
1623        }
1624
1625        // A fresh instance over the same root (process restart): the head
1626        // cache is cold and must be rebuilt from the on-disk chain.
1627        let reopened = JsonFileCheckpointer::new(tmp.0.clone());
1628        let cp1 = Checkpoint::new("t1", 1, evolving_state(1, &blob), vec![]);
1629        let id1 = cp1.id.clone();
1630        reopened.put(cp1).await.unwrap();
1631
1632        let on_disk = file_json(&tmp, "t1", &id1);
1633        assert_eq!(on_disk["base"], serde_json::json!(id0));
1634        assert_eq!(on_disk["state"], serde_json::json!({"step": 1}));
1635        assert_eq!(
1636            reopened.get_latest("t1").await.unwrap().unwrap().state,
1637            evolving_state(1, &blob)
1638        );
1639    }
1640
1641    #[tokio::test]
1642    async fn pre_delta_checkpoints_load_unchanged() {
1643        let tmp = TestDir::new();
1644        let store = JsonFileCheckpointer::new(tmp.0.clone());
1645
1646        // Hand-write a checkpoint file in the pre-W4 shape (no `base`
1647        // field), as an older binary would have produced it.
1648        let cp = Checkpoint::new("t1", 0, evolving_state(3, "legacy"), vec!["next".into()]);
1649        let id = cp.id.clone();
1650        let dir = tmp.0.join("t1");
1651        std::fs::create_dir_all(&dir).unwrap();
1652        let mut json: serde_json::Value =
1653            serde_json::from_str(&serde_json::to_string_pretty(&cp).unwrap()).unwrap();
1654        json.as_object_mut().unwrap().remove("base");
1655        let text = serde_json::to_string_pretty(&json).unwrap();
1656        assert!(!text.contains("\"base\""));
1657        std::fs::write(dir.join(format!("{id}.json")), &text).unwrap();
1658        std::fs::write(dir.join("latest"), &id).unwrap();
1659
1660        let latest = store.get_latest("t1").await.unwrap().unwrap();
1661        assert_eq!(latest.id, id);
1662        assert_eq!(latest.state, evolving_state(3, "legacy"));
1663        assert_eq!(latest.next_nodes, vec!["next".to_string()]);
1664        assert_eq!(latest.base, None);
1665
1666        // A delta put on top of a legacy checkpoint diffs against it fine.
1667        let cp1 = Checkpoint::new("t1", 1, evolving_state(4, "legacy"), vec![]);
1668        let id1 = cp1.id.clone();
1669        store.put(cp1).await.unwrap();
1670        assert_eq!(file_json(&tmp, "t1", &id1)["base"], serde_json::json!(id));
1671    }
1672
1673    #[tokio::test]
1674    async fn fork_compacts_to_full_snapshots() {
1675        let tmp = TestDir::new();
1676        let store = JsonFileCheckpointer::new(tmp.0.clone());
1677
1678        let mut ids = Vec::new();
1679        for step in 0..4 {
1680            let cp = Checkpoint::new("src", step, evolving_state(step, "f"), vec![]);
1681            ids.push(cp.id.clone());
1682            store.put(cp).await.unwrap();
1683        }
1684
1685        let copied = store
1686            .fork_thread("src", "dst", Some(&ids[2]))
1687            .await
1688            .unwrap();
1689        assert_eq!(copied, 3);
1690
1691        // Every forked checkpoint is a full snapshot on disk — the fork is
1692        // the compaction point, so its timeline never folds a chain.
1693        for id in &ids[..3] {
1694            let on_disk = file_json(&tmp, "dst", id);
1695            assert!(
1696                on_disk.get("base").is_none(),
1697                "forked checkpoint must be a full snapshot: {on_disk}"
1698            );
1699        }
1700        // And reads agree, on both timelines.
1701        assert_eq!(
1702            store.get_latest("dst").await.unwrap().unwrap().state,
1703            evolving_state(2, "f")
1704        );
1705        assert_eq!(
1706            store.get_latest("src").await.unwrap().unwrap().state,
1707            evolving_state(3, "f")
1708        );
1709    }
1710
1711    #[tokio::test]
1712    async fn full_only_policy_restores_pre_w4_writes() {
1713        let tmp = TestDir::new();
1714        let store =
1715            JsonFileCheckpointer::with_delta_policy(tmp.0.clone(), DeltaPolicy::full_only());
1716
1717        let mut ids = Vec::new();
1718        for step in 0..3 {
1719            let cp = Checkpoint::new("t1", step, evolving_state(step, "z"), vec![]);
1720            ids.push(cp.id.clone());
1721            store.put(cp).await.unwrap();
1722        }
1723        for id in &ids {
1724            assert!(file_json(&tmp, "t1", id).get("base").is_none());
1725        }
1726        assert_eq!(store.list("t1").await.unwrap().len(), 3);
1727    }
1728
1729    #[test]
1730    fn encode_delta_decides_full_delta_and_bounds() {
1731        let head_state = evolving_state(0, "blob");
1732        let head_cp = Checkpoint::new("t", 0, head_state.clone(), vec![]);
1733        let head = DeltaHead {
1734            checkpoint: head_cp.clone(),
1735            chain_len: 0,
1736        };
1737        let policy = DeltaPolicy::default();
1738
1739        // Delta: one small channel changed.
1740        let next = Checkpoint::new("t", 1, evolving_state(1, "blob"), vec![]);
1741        let encoding = encode_delta(&next, Some(&head), &policy);
1742        assert_eq!(encoding.checkpoint.base, Some(head_cp.id.clone()));
1743        assert_eq!(
1744            encoding.checkpoint.state,
1745            State::from_value(serde_json::json!({"step": 1})).unwrap()
1746        );
1747        assert_eq!(encoding.chain_len, 1);
1748
1749        // Chain bound: a head already at the limit forces a full snapshot.
1750        let at_bound = DeltaHead {
1751            chain_len: policy.max_chain_len,
1752            ..head.clone()
1753        };
1754        let encoding = encode_delta(&next, Some(&at_bound), &policy);
1755        assert_eq!(encoding.checkpoint.base, None);
1756        assert_eq!(encoding.chain_len, 0);
1757
1758        // No head or disabled policy: full snapshot.
1759        assert!(encode_delta(&next, None, &policy).checkpoint.base.is_none());
1760        assert!(encode_delta(&next, Some(&head), &DeltaPolicy::full_only())
1761            .checkpoint
1762            .base
1763            .is_none());
1764
1765        // A caller-set base is never honored: put contract is full snapshots.
1766        let mut with_base = next.clone();
1767        with_base.base = Some("caller-lie".into());
1768        let encoding = encode_delta(&with_base, Some(&at_bound), &policy);
1769        assert_eq!(encoding.checkpoint.base, None);
1770    }
1771
1772    #[test]
1773    fn fold_chain_materializes_and_rejects_broken_chains() {
1774        let blob = "q".repeat(64);
1775        let mut chain: Vec<Checkpoint> = Vec::new();
1776        // The materialized tip the backend would diff the next put against.
1777        let mut head: Option<DeltaHead> = None;
1778        for step in 0..4 {
1779            let full = Checkpoint::new("t", step, evolving_state(step, &blob), vec![]);
1780            let encoding = encode_delta(&full, head.as_ref(), &DeltaPolicy::default());
1781            chain.push(encoding.checkpoint);
1782            head = Some(DeltaHead {
1783                checkpoint: full,
1784                chain_len: encoding.chain_len,
1785            });
1786        }
1787
1788        let tip = fold_chain(&chain).unwrap();
1789        assert_eq!(tip.state, evolving_state(3, &blob));
1790        assert_eq!(tip.base, None);
1791
1792        // A root that is itself a delta is a broken chain.
1793        let err = fold_chain(&chain[1..]).unwrap_err();
1794        assert!(matches!(err, RustyError::Checkpoint(_)));
1795
1796        // A link pointing at the wrong base is a broken chain.
1797        let mut broken = chain.clone();
1798        broken[2].base = Some("not-the-parent".into());
1799        assert!(fold_chain(&broken).is_err());
1800    }
1801
1802    #[test]
1803    fn materialize_all_folds_memoized_and_skips_corruption() {
1804        let full = Checkpoint::new("t", 0, evolving_state(0, "m"), vec![]);
1805        let mut link = Checkpoint::new("t", 1, evolving_state(1, "m"), vec![]);
1806        link.base = Some(full.id.clone());
1807        link.state = State::from_value(serde_json::json!({"step": 1})).unwrap();
1808        let mut dangling = Checkpoint::new("t", 2, State::new(), vec![]);
1809        dangling.base = Some("missing-base".into());
1810        let mut cyclic = Checkpoint::new("t", 3, State::new(), vec![]);
1811        cyclic.base = Some(cyclic.id.clone());
1812
1813        let materialized = materialize_all(vec![link.clone(), dangling, cyclic, full.clone()]);
1814        // The dangling and cyclic links are skipped (corruption must not
1815        // poison the thread); the full root and its link fold.
1816        assert_eq!(materialized.len(), 2);
1817        let by_step: HashMap<usize, &Checkpoint> =
1818            materialized.iter().map(|c| (c.step, c)).collect();
1819        assert_eq!(by_step[&0].state, evolving_state(0, "m"));
1820        assert_eq!(by_step[&1].state, evolving_state(1, "m"));
1821        assert!(materialized.iter().all(|c| c.base.is_none()));
1822    }
1823}