diff --git a/.github/workflows/history.yml b/.github/workflows/history.yml new file mode 100644 --- /dev/null +++ b/.github/workflows/history.yml @@ -0,0 +1,50 @@ +name: Shared History + +on: + push: + branches: [main] + paths: ["crates/history/**", "Cargo.toml", "Cargo.lock", ".github/workflows/history.yml"] + pull_request: + paths: ["crates/history/**", "Cargo.toml", "Cargo.lock", ".github/workflows/history.yml"] + workflow_dispatch: + +permissions: + contents: read + +concurrency: + group: shared-history-${{ github.ref }} + cancel-in-progress: true + +jobs: + native: + name: History (${{ matrix.os }}) + timeout-minutes: 15 + strategy: + fail-fast: false + matrix: + os: [ubuntu-latest, windows-latest, macos-latest] + runs-on: ${{ matrix.os }} + steps: + - uses: actions/checkout@v4 + - uses: dtolnay/rust-toolchain@stable + with: + components: rustfmt, clippy + - uses: Swatinem/rust-cache@v2 + with: + key: craft-history + - run: cargo fmt --all -- --check + - run: cargo clippy -p craft-history --all-targets --locked -- -D warnings + - run: cargo test -p craft-history --locked + wasm: + name: History WASM + timeout-minutes: 15 + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v4 + - uses: dtolnay/rust-toolchain@stable + with: + targets: wasm32-unknown-unknown + - uses: Swatinem/rust-cache@v2 + with: + key: craft-history-wasm + - run: cargo check -p craft-history --locked --target wasm32-unknown-unknown diff --git a/Cargo.lock b/Cargo.lock --- a/Cargo.lock +++ b/Cargo.lock @@ -529,6 +529,13 @@ dependencies = [ "rayon", ] +[[package]] +name = "craft-history" +version = "0.1.0" +dependencies = [ + "serde", +] + [[package]] name = "craft-print" version = "0.1.0" diff --git a/Cargo.toml b/Cargo.toml --- a/Cargo.toml +++ b/Cargo.toml @@ -11,6 +11,7 @@ repository = "https://github.com/storytold/craft-libs" [workspace.dependencies] # internal: add each crate here as `craft- = { path = "crates/" }` +craft-history = { path = "crates/history" } craft-atomic = { path = "crates/atomic" } craft-cms = { path = "crates/cms" } craft-print = { path = "crates/print" } diff --git a/NOTICE b/NOTICE --- a/NOTICE +++ b/NOTICE @@ -79,3 +79,9 @@ The colour management module in crates/cms is extracted from: Copyright (c) 2026 ArtCraft Team and the PhotoCraft contributors. Licensed MIT OR Apache-2.0. Its generated ICC profile is dedicated to the public domain (CC0-1.0); see ATTRIBUTION.md. + +The branching history engine in crates/history is extracted and generalized from: +- PhotoCraft, crates/ops/src/lib.rs, revision 0e3f37be652cf50883487d59bba3a3aa6ecc6c14. + https://github.com/TheSeanLavery/photocraft + Copyright (c) 2026 ArtCraft Team and the PhotoCraft contributors. + Licensed MIT OR Apache-2.0. diff --git a/README.md b/README.md --- a/README.md +++ b/README.md @@ -23,6 +23,8 @@ craft- = { git = "https://github.com/storytold/craft-libs", rev = "` stores immutable `Arc` snapshots. + +```rust +use craft_history::{History, Policy}; +use std::{collections::HashSet, sync::Arc}; + +#[derive(Clone, Debug)] +struct TextApp; +impl Policy for TextApp { + type Document = String; + type Target = (usize, usize); + type Id = (); + fn has_selection(_: &String) -> bool { false } + fn remap_id(_: &mut Arc, _: ()) {} + fn document_bytes(text: &String, seen: &mut HashSet) -> usize { + if seen.insert(text.as_ptr() as usize) { text.capacity() } else { 0 } + } +} +let mut history = History::::default(); +history.record("Typing", Arc::new("Before".to_owned()), (0, 5)); +let restored = history.try_undo(Arc::new("After".to_owned()))?; +# Ok::<(), String>(()) +``` + +An `ArchivedDocument` provides fallible restoration and optional resident +backing for compact replay. The app chooses codecs, scratch directories, worker +scheduling, RAM spill policy, durable publication, file locks, and recovery cleanup. +The library does not promise crash durability itself. + +`checkpoint`, `timeline`, and selection metadata queries never load archives. +Undo/redo load the destination before modifying navigation; a failed load leaves +the cursor and stacks intact. Direct jumps accept an already-loaded destination, +so the app can perform I/O off the UI thread without loading intervening states. +The app must revalidate its worker result against its document/history revision +before committing it. Allocation identity guards stale asynchronous spill results. + +`max_states = 0` and `max_bytes = 0` mean unlimited. An app with unlimited history +must arrange backing storage and reject edits on storage failure rather than use +the destructive bounded-history eviction helpers. Byte accounting is an estimate +of app-managed payloads, not total process RAM; metadata is reported separately. + +Checkpoint IDs permit missing parents after eviction, but reject duplicate IDs, +invalid forward/self parent references, invalid branches, exhausted identity ranges, +and excessive labels. Applications must impose serialized input-size/state-count +limits before decoding a checkpoint, and validate document/target semantics. + +PhotoCraft keeps pixel serialization, exact raster move replay, its recovery format, +thumbnail production, selection restoration, commands, and egui history panel. +These are adapters, not dependencies of this crate. diff --git a/crates/history/src/lib.rs b/crates/history/src/lib.rs new file mode 100644 --- /dev/null +++ b/crates/history/src/lib.rs @@ -0,0 +1,812 @@ +//! Snapshot-based branching history shared by Craft applications. +//! +//! No document format, renderer, filesystem, or app dependency is required. A +//! [`Policy`] supplies document-specific metadata and shared-allocation accounting; +//! [`ArchivedDocument`] supplies fallible lazy storage or compact replay. +#![doc = include_str!("../README.md")] +#![forbid(unsafe_code)] +#![deny(clippy::unwrap_used, clippy::expect_used, clippy::panic, clippy::unimplemented, clippy::todo, clippy::unreachable)] + +use serde::{Deserialize, Serialize}; +use std::collections::{HashSet, VecDeque}; +use std::sync::Arc; + +/// Application adapter. Hooks must be deterministic and must not hydrate storage. +/// Keep every allocation visited by `document_bytes` alive during a deduplication pass. +/// Targets can be target, cells, slides, tracks, or an empty value. +pub trait Policy: Clone + std::fmt::Debug + Send + Sync + 'static { + type Document: Clone + std::fmt::Debug + Send + Sync + 'static; + type Target: Clone + Default + std::fmt::Debug + Send + Sync + 'static; + type Id: Copy + std::fmt::Debug + Send + Sync; + fn has_selection(document: &Self::Document) -> bool; + fn remap_id(document: &mut Arc, id: Self::Id); + fn document_bytes(document: &Self::Document, seen: &mut HashSet) -> usize; + fn target_bytes(_target: &Self::Target) -> usize { + 0 + } +} + +#[derive(Clone, Debug)] +pub struct HistoryState { + pub label: String, + /// The target targeted when this state was created. + pub target: P::Target, + pub identity: StateIdentity, + document: StoredDocument

, + has_selection: bool, +} + +/// Stable navigation identity; branch colors follow `branch`, not row positions. +#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Serialize, Deserialize)] +pub struct StateIdentity { + pub id: u64, + pub parent: Option, + pub branch: u64, + #[serde(default)] + pub revision: u64, +} + +#[derive(Clone, Debug)] +pub struct HistoryEntry { + pub identity: StateIdentity, + pub label: String, + pub current: bool, +} + +impl HistoryState

{ + /// Build a resident recovery state without copying pixel data. + pub fn from_document(label: impl Into, document: Arc) -> Self { + Self { + label: label.into(), + target: P::Target::default(), + identity: StateIdentity::default(), + has_selection: P::has_selection(&document), + document: StoredDocument::

::Resident(document), + } + } + + /// Build a lazily restored recovery state. `has_selection` is metadata for + /// selection menus, which must not read storage merely to draw themselves. + pub fn from_archive(label: impl Into, has_selection: bool, archive: Arc>) -> Self { + Self { + label: label.into(), + target: P::Target::default(), + identity: StateIdentity::default(), + has_selection, + document: StoredDocument::

::Archived(archive), + } + } + + /// May read storage for a cold state; recovery writers call this on a worker. + pub fn load_document(&self) -> Result, String> { + self.document.load() + } + + pub fn has_selection(&self) -> bool { + self.has_selection + } + + pub fn with_target(mut self, target: P::Target) -> Self { + self.target = target; + self + } +} + +/// Immutable handles and navigation metadata captured alongside the current +/// document. Undo is oldest first; redo's last entry is the next redo state. +/// Capturing this value never hydrates archived documents. +#[derive(Clone, Debug)] +pub struct HistoryCheckpoint { + pub undo: Vec>, + pub redo: Vec>, + pub branches: Vec>, + pub current_identity: StateIdentity, + pub current_label: String, + pub current_target: P::Target, + pub max_states: usize, + pub max_bytes: usize, +} + +/// Engine-owned immutable scratch archive. Loading must preserve the complete document. +pub trait ArchivedDocument: std::fmt::Debug + Send + Sync { + fn load(&self) -> Result, String>; + fn metadata_bytes(&self) -> usize { + 0 + } + /// Resident backing for compact replay states; counted once, never mistaken for disk. + fn resident(&self) -> Option<&Arc> { + None + } +} + +#[derive(Debug)] +struct RemappedDocument { + source: Arc>, + id: P::Id, +} +impl ArchivedDocument

for RemappedDocument

{ + fn load(&self) -> Result, String> { + let mut doc = self.source.load()?; + P::remap_id(&mut doc, self.id); + Ok(doc) + } + fn metadata_bytes(&self) -> usize { + std::mem::size_of::().saturating_add(self.source.metadata_bytes()) + } + fn resident(&self) -> Option<&Arc> { + self.source.resident() + } +} + +#[derive(Clone, Debug)] +enum StoredDocument { + Resident(Arc), + Archived(Arc>), +} + +impl StoredDocument

{ + fn load(&self) -> Result, String> { + match self { + Self::Resident(doc) => Ok(doc.clone()), + Self::Archived(archive) => archive.load(), + } + } + fn resident(&self) -> Option<&Arc> { + match self { + Self::Resident(doc) => Some(doc), + Self::Archived(archive) => archive.resident(), + } + } +} + +#[derive(Clone, Debug)] +pub struct History { + /// Past states; the last one is the state *before* the current document. + undo: VecDeque>, + redo: Vec>, + branches: Vec>, + current_identity: StateIdentity, + next_id: u64, + pub max_states: usize, + /// Pixel memory budget in bytes for the current document plus the tiles only history holds + /// (0 = unlimited). [`History::

::trim`] drops the oldest states beyond it. + pub max_bytes: usize, + /// Label of the step that produced the current document. + current_label: String, + /// The target targeted when the current document was created (opened or edited). + current_target: P::Target, + current_archive: Option>>, + current_archive_document: Option>, +} + +impl Default for History

{ + fn default() -> Self { + Self::new(0) + } +} + +impl History

{ + pub fn checkpoint(&self) -> HistoryCheckpoint

{ + HistoryCheckpoint { + undo: self.undo.iter().cloned().collect(), + redo: self.redo.clone(), + branches: self.branches.clone(), + current_identity: self.current_identity, + current_label: self.current_label.clone(), + current_target: self.current_target.clone(), + max_states: self.max_states, + max_bytes: self.max_bytes, + } + } + + /// Restore the exact navigation cursor without reading document storage. + /// Recovery metadata has independent admission limits; preference limits + /// may subsequently be applied explicitly through `enforce_state_limit`. + pub fn from_checkpoint(mut checkpoint: HistoryCheckpoint

) -> Result { + const MAX_LABEL_BYTES: usize = 4096; + if checkpoint.current_label.len() > MAX_LABEL_BYTES + || checkpoint.undo.iter().chain(checkpoint.redo.iter()).chain(checkpoint.branches.iter()).any(|state| state.label.len() > MAX_LABEL_BYTES) + { + return Err("Recovery history label exceeds 4096 bytes".into()); + } + // Legacy checkpoints have no identities. Assign their linear path once. + if checkpoint.current_identity == StateIdentity::default() + && checkpoint.undo.iter().chain(checkpoint.redo.iter()).all(|state| state.identity == StateIdentity::default()) + && checkpoint.branches.is_empty() + { + let mut id = 0u64; + for state in &mut checkpoint.undo { + state.identity = StateIdentity { id, parent: id.checked_sub(1), branch: 0, revision: 0 }; + id = id.saturating_add(1); + } + checkpoint.current_identity = StateIdentity { id, parent: id.checked_sub(1), branch: 0, revision: 0 }; + for state in checkpoint.redo.iter_mut().rev() { + id = id.saturating_add(1); + state.identity = StateIdentity { id, parent: id.checked_sub(1), branch: 0, revision: 0 }; + } + } + if checkpoint.current_identity.id > u64::MAX / 2 + || checkpoint.current_identity.revision > u64::MAX / 2 + || checkpoint.current_identity.branch > checkpoint.current_identity.id + || checkpoint.current_identity.parent.is_some_and(|parent| parent >= checkpoint.current_identity.id) + { + return Err("Invalid current history identity".into()); + } + let mut ids = HashSet::from([checkpoint.current_identity.id]); + let mut next_id = checkpoint.current_identity.id.checked_add(1).ok_or("History identity exhausted")?; + for state in checkpoint.undo.iter().chain(checkpoint.redo.iter()).chain(checkpoint.branches.iter()) { + if !ids.insert(state.identity.id) + || state.identity.id > u64::MAX / 2 + || state.identity.revision > u64::MAX / 2 + || state.identity.branch > state.identity.id + || state.identity.parent.is_some_and(|parent| parent >= state.identity.id) + { + return Err("Invalid recovery history identity".into()); + } + next_id = next_id.max(state.identity.id.checked_add(1).ok_or("History identity exhausted")?); + } + Ok(Self { + undo: checkpoint.undo.into(), + redo: checkpoint.redo, + branches: checkpoint.branches, + current_identity: checkpoint.current_identity, + next_id, + current_label: checkpoint.current_label, + current_target: checkpoint.current_target, + current_archive: None, + current_archive_document: None, + max_states: checkpoint.max_states, + max_bytes: checkpoint.max_bytes, + }) + } + + pub fn new(max_states: usize) -> Self { + Self { + undo: VecDeque::new(), + redo: Vec::new(), + branches: Vec::new(), + current_identity: StateIdentity::default(), + next_id: 1, + max_states, + max_bytes: 0, + current_label: "Open".into(), + current_target: P::Target::default(), + current_archive: None, + current_archive_document: None, + } + } + + /// Metadata-only stamp for logical history changes (including Purge). + pub fn checkpoint_signature(&self) -> (usize, usize, &str) { + (self.undo.len(), self.redo.len(), &self.current_label) + } + + /// A duplicate recovered tab can be admitted under a fresh identity. + /// Cold states are remapped only when restored, without reading disk here. + pub fn remap_document_id(&mut self, id: P::Id) { + if let Some(source) = self.current_archive.take() { + self.current_archive = Some(Arc::new(RemappedDocument { source, id })); + } + for state in self.undo.iter_mut().chain(self.redo.iter_mut()).chain(self.branches.iter_mut()) { + match &mut state.document { + StoredDocument::

::Resident(doc) => { + P::remap_id(doc, id); + } + StoredDocument::

::Archived(source) => { + *source = Arc::new(RemappedDocument { source: source.clone(), id }); + } + } + } + } + + /// Record that `before` was replaced by a new current document via step `label`, which left + /// `target` targeted. + pub fn record(&mut self, label: impl Into, before: Arc, target: P::Target) { + self.clear_current_archive(); + let prev_label = std::mem::replace(&mut self.current_label, label.into()); + let prev_layers = std::mem::replace(&mut self.current_target, target); + self.undo.push_back(HistoryState { + label: prev_label, + target: prev_layers, + identity: self.current_identity, + has_selection: P::has_selection(&before), + document: StoredDocument::

::Resident(before), + }); + let branch = if self.redo.is_empty() { self.current_identity.branch } else { self.next_id }; + self.current_identity = StateIdentity { id: self.next_id, parent: Some(self.current_identity.id), branch, revision: 0 }; + self.next_id = self.next_id.saturating_add(1); + self.branches.append(&mut self.redo); + self.enforce_state_limit(); + } + + pub fn can_undo(&self) -> bool { + !self.undo.is_empty() + } + pub fn can_redo(&self) -> bool { + !self.redo.is_empty() + } + pub fn undo_label(&self) -> Option<&str> { + self.can_undo().then_some(self.current_label.as_str()) + } + pub fn redo_label(&self) -> Option<&str> { + self.redo.last().map(|s| s.label.as_str()) + } + /// Labels of the redo states, the next redo first (the History panel's greyed rows). + pub fn redo_labels(&self) -> impl Iterator { + self.redo.iter().rev().map(|s| s.label.as_str()) + } + + /// Set the target the current document targets from its creation on: when it is first + /// opened, or when its step coalesces or changes the selection after recording. + pub fn set_current_target(&mut self, target: P::Target) { + self.current_target = target; + self.current_identity.revision = self.current_identity.revision.saturating_add(1); + } + + pub fn current_target(&self) -> &P::Target { + &self.current_target + } + + /// Restore first: a failed archive read never moves either history stack. + pub fn try_undo(&mut self, current: Arc) -> Result>, String> { + let Some(prev) = self.undo.back() else { return Ok(None) }; + let restored = prev.document.load()?; + let Some(prev) = self.undo.pop_back() else { return Ok(None) }; + let label = std::mem::replace(&mut self.current_label, prev.label); + let target = std::mem::replace(&mut self.current_target, prev.target.clone()); + let has_selection = P::has_selection(¤t); + let document = self.take_current_document(current); + self.redo.push(HistoryState { label, has_selection, document, target, identity: self.current_identity }); + self.current_identity = prev.identity; + self.current_archive = match prev.document { + StoredDocument::

::Archived(archive) => Some(archive), + _ => None, + }; + self.current_archive_document = self.current_archive.as_ref().map(|_| Arc::downgrade(&restored)); + Ok(Some(restored)) + } + + pub fn try_redo(&mut self, current: Arc) -> Result>, String> { + let Some(next) = self.redo.last() else { return Ok(None) }; + let restored = next.document.load()?; + let Some(next) = self.redo.pop() else { return Ok(None) }; + let label = std::mem::replace(&mut self.current_label, next.label); + let target = std::mem::replace(&mut self.current_target, next.target.clone()); + let has_selection = P::has_selection(¤t); + let document = self.take_current_document(current); + self.undo.push_back(HistoryState { label, has_selection, document, target, identity: self.current_identity }); + self.current_identity = next.identity; + self.current_archive = match next.document { + StoredDocument::

::Archived(archive) => Some(archive), + _ => None, + }; + self.current_archive_document = self.current_archive.as_ref().map(|_| Arc::downgrade(&restored)); + Ok(Some(restored)) + } + + /// Compatibility wrapper. Interactive callers should use [`Self::try_undo`] to report errors. + pub fn undo(&mut self, current: Arc) -> Option<(Arc, P::Target)> { + self.try_undo(current).ok().flatten().map(|doc| (doc, self.current_target.clone())) + } + /// Compatibility wrapper. Interactive callers should use [`Self::try_redo`] to report errors. + pub fn redo(&mut self, current: Arc) -> Option<(Arc, P::Target)> { + self.try_redo(current).ok().flatten().map(|doc| (doc, self.current_target.clone())) + } + + /// Entries for a History panel: past labels oldest→newest, then the current label. + pub fn entries(&self) -> Vec { + self.undo.iter().map(|s| s.label.clone()).chain(std::iter::once(self.current_label.clone())).collect() + } + + /// Metadata only: drawing history must never decode a document from disk. + pub fn timeline(&self) -> Vec { + let mut entries: Vec<_> = self + .undo + .iter() + .chain(self.redo.iter()) + .chain(self.branches.iter()) + .map(|state| HistoryEntry { identity: state.identity, label: state.label.clone(), current: false }) + .collect(); + entries.push(HistoryEntry { identity: self.current_identity, label: self.current_label.clone(), current: true }); + entries.sort_by_key(|entry| entry.identity.id); + entries + } + + /// Delete one branch state and all of its descendants, preserving independent branches. + /// The caller first moves the current document to the deleted state's predecessor. + pub fn prune_descendants(&mut self, id: u64) { + let timeline = self.timeline(); + let mut removed = HashSet::from([id]); + loop { + let before = removed.len(); + for entry in &timeline { + if entry.identity.parent.is_some_and(|parent| removed.contains(&parent)) { + removed.insert(entry.identity.id); + } + } + if removed.len() == before { + break; + } + } + self.undo.retain(|state| !removed.contains(&state.identity.id)); + self.redo.retain(|state| !removed.contains(&state.identity.id)); + self.branches.retain(|state| !removed.contains(&state.identity.id)); + } + + pub fn current_id(&self) -> u64 { + self.current_identity.id + } + + pub fn timeline_stamp(&self) -> (u64, u64, u64, usize, usize, usize) { + (self.current_identity.id, self.current_identity.revision, self.next_id, self.undo.len(), self.redo.len(), self.branches.len()) + } + + pub fn adjacent_id(&self, redo: bool) -> Option { + (if redo { self.redo.last() } else { self.undo.back() }).map(|state| state.identity.id) + } + + /// Immutable destination handle, safe to restore on a worker. + pub fn state_by_id(&self, current: Arc, id: u64) -> Option> { + if id == self.current_identity.id { + let mut state = HistoryState::

::from_document(self.current_label.clone(), current).with_target(self.current_target.clone()); + state.identity = self.current_identity; + return Some(state); + } + self.undo.iter().chain(self.redo.iter()).chain(self.branches.iter()).find(|state| state.identity.id == id).cloned() + } + + /// Commit one already-loaded destination. Intervening snapshots stay cold. + /// Build/validate the path before mutating navigation, so any error is atomic. + pub fn jump_loaded(&mut self, current: Arc, id: u64, restored: Arc) -> Result<(), String> { + self.jump_loaded_on_path(current, id, restored, None) + } + + pub fn navigation_branch(&self) -> u64 { + self.redo.first().map_or(self.current_identity.branch, |state| state.identity.branch) + } + + pub fn jump_loaded_on_path( + &mut self, + current: Arc, + id: u64, + restored: Arc, + preferred_branch: Option, + ) -> Result<(), String> { + if id == self.current_identity.id { + return Ok(()); + } + let mut nodes: std::collections::BTreeMap<_, _> = + self.undo.iter().chain(self.redo.iter()).chain(self.branches.iter()).map(|state| (state.identity.id, state.clone())).collect(); + let target = nodes.remove(&id).ok_or("History state is no longer available")?; + let mut current_state = + HistoryState::

::from_document(self.current_label.clone(), current.clone()).with_target(self.current_target.clone()); + current_state.identity = self.current_identity; + nodes.insert(self.current_identity.id, current_state); + let mut ancestors = Vec::new(); + let mut parent = target.identity.parent; + let mut seen = HashSet::from([id]); + while let Some(key) = parent { + if !seen.insert(key) { + return Err("Cyclic history path".into()); + } + let Some(state) = nodes.remove(&key) else { break }; + parent = state.identity.parent; + ancestors.push(state); + } + ancestors.reverse(); + let branch = + preferred_branch.unwrap_or_else(|| if target.identity.parent.is_none() { self.navigation_branch() } else { target.identity.branch }); + let mut descendants = Vec::new(); + let mut children: std::collections::BTreeMap> = std::collections::BTreeMap::new(); + for state in nodes.values() { + if let Some(parent) = state.identity.parent { + children.entry(parent).or_default().push(state.identity.id); + } + } + let mut cursor = id; + loop { + let next = children + .get(&cursor) + .into_iter() + .flatten() + .filter_map(|key| nodes.get(key)) + .max_by_key(|state| (state.identity.branch == branch, state.identity.id)) + .map(|state| state.identity.id); + let Some(next) = next else { break }; + if !seen.insert(next) { + return Err("Cyclic history path".into()); + } + let Some(state) = nodes.remove(&next) else { break }; + cursor = next; + descendants.push(state); + } + // Preserve an archived handle for the previous current document when available. + let stored_current = self.take_current_document(current); + for state in ancestors.iter_mut().chain(descendants.iter_mut()).chain(nodes.values_mut()) { + if state.identity.id == self.current_identity.id { + state.document = stored_current.clone(); + } + } + descendants.reverse(); + self.undo = ancestors.into(); + self.redo = descendants; + self.branches = nodes.into_values().collect(); + self.current_identity = target.identity; + self.current_label = target.label; + self.current_target = target.target; + self.current_archive = match target.document { + StoredDocument::

::Archived(archive) => Some(archive), + _ => None, + }; + self.current_archive_document = self.current_archive.as_ref().map(|_| Arc::downgrade(&restored)); + Ok(()) + } + + /// Document of past entry `i`, indexed like [`History::

::entries`] (0 = oldest). The last entry is + /// the current document, which the history does not hold, so it (and any index past it) is `None`. + pub fn state(&self, i: usize) -> Option> { + self.try_state(i).ok().flatten() + } + + /// Metadata-only query for menus; never hydrates a cold snapshot. + pub fn has_past_selection(&self) -> bool { + self.undo.iter().any(|state| state.has_selection) + } + + /// Most recent selection-bearing state, found without reading scratch storage. + pub fn latest_selection_state(&self) -> Option { + self.undo.iter().enumerate().rev().find_map(|(index, state)| state.has_selection.then_some(index)) + } + + pub fn resident_state(&self, i: usize) -> Option> { + self.undo.get(i).and_then(|state| match &state.document { + StoredDocument::

::Resident(doc) => Some(doc.clone()), + _ => None, + }) + } + + pub fn try_state(&self, i: usize) -> Result>, String> { + self.undo.get(i).map(|state| state.document.load()).transpose() + } + + /// Resident snapshots only; this never reads scratch storage. + pub fn resident_states(&self) -> Vec> { + let mut seen = HashSet::new(); + self.undo + .iter() + .chain(self.redo.iter()) + .chain(self.branches.iter()) + .filter_map(|state| state.document.resident().cloned()) + .chain(self.current_archive.iter().filter_map(|archive| archive.resident().cloned())) + .filter(|doc| seen.insert(Arc::as_ptr(doc) as usize)) + .collect() + } + + /// Concrete snapshots eligible for scratch serialization. Compact replay backing stays resident. + pub fn spillable_states(&self) -> Vec> { + self.undo + .iter() + .chain(self.redo.iter()) + .chain(self.branches.iter()) + .filter_map(|state| match &state.document { + StoredDocument::

::Resident(doc) => Some(doc.clone()), + _ => None, + }) + .collect() + } + + /// State descriptors and compact replay records, separate from pixel payload accounting. + pub fn metadata_bytes(&self) -> usize { + let mut total = self.current_label.capacity().saturating_add(P::target_bytes(&self.current_target)); + for state in self.undo.iter().chain(self.redo.iter()).chain(self.branches.iter()) { + total = total + .saturating_add(std::mem::size_of::>()) + .saturating_add(state.label.capacity()) + .saturating_add(P::target_bytes(&state.target)); + if let StoredDocument::

::Archived(archive) = &state.document { + total = total.saturating_add(archive.metadata_bytes()); + } + } + if let Some(archive) = &self.current_archive { + total = total.saturating_add(archive.metadata_bytes()); + } + total + } + + pub fn archived_states(&self) -> usize { + self.undo + .iter() + .chain(self.redo.iter()) + .chain(self.branches.iter()) + .filter(|state| matches!(&state.document, StoredDocument::

::Archived(archive) if archive.resident().is_none())) + .count() + } + + /// Adjacent resident snapshots pinned for immediate undo/redo. + pub fn hot_states(&self) -> Vec> { + self.undo + .back() + .into_iter() + .chain(self.redo.last()) + .filter_map(|state| state.document.resident().cloned()) + .chain(self.current_archive.iter().filter_map(|archive| archive.resident().cloned())) + .collect() + } + + /// Whether this allocation is the immediate undo or redo state. + /// Used to revalidate asynchronous spill results after intervening navigation. + pub fn is_hot(&self, doc: &Arc) -> bool { + self.undo.back().and_then(|state| state.document.resident()).is_some_and(|hot| Arc::ptr_eq(doc, hot)) + || self.redo.last().and_then(|state| state.document.resident()).is_some_and(|hot| Arc::ptr_eq(doc, hot)) + } + + /// Oldest eligible snapshot, keeping the immediate undo and redo states hot. + pub fn spill_candidate(&self) -> Option> { + self.undo + .iter() + .take(self.undo.len().saturating_sub(1)) + .chain(self.redo.iter().take(self.redo.len().saturating_sub(1))) + .filter_map(|state| state.document.resident()) + .find(|doc| { + !self.undo.back().and_then(|state| state.document.resident()).is_some_and(|hot| Arc::ptr_eq(doc, hot)) + && !self.redo.last().and_then(|state| state.document.resident()).is_some_and(|hot| Arc::ptr_eq(doc, hot)) + }) + .cloned() + } + + /// Replace only the allocation actually archived; stale worker results are harmless. + pub fn replace_resident(&mut self, doc: &Arc, archive: Arc>) -> bool { + let mut replaced = false; + for state in self.undo.iter_mut().chain(self.redo.iter_mut()).chain(self.branches.iter_mut()) { + if matches!(&state.document, StoredDocument::

::Resident(resident) if Arc::ptr_eq(resident, doc)) { + state.document = StoredDocument::

::Archived(archive.clone()); + replaced = true; + } + } + replaced + } + + /// Budget fallback, preserving the immediate undo and redo steps. + pub fn drop_oldest(&mut self) -> bool { + if !self.branches.is_empty() { + self.branches.remove(0); + return true; + } + if self.undo.len() > 1 { + self.undo.pop_front(); + true + } else if self.redo.len() > 1 { + self.redo.remove(0); + true + } else { + false + } + } + + /// Explicit preference reduction may retire even the final undo/redo state. + /// The current document is never owned by these stacks. + pub fn discard_oldest(&mut self) -> bool { + if !self.branches.is_empty() { + self.branches.remove(0); + return true; + } + if self.undo.pop_front().is_some() { + true + } else if !self.redo.is_empty() { + self.redo.remove(0); + true + } else { + false + } + } + + /// Enforce a lowered history-count preference without reading scratch storage. + pub fn enforce_state_limit(&mut self) -> usize { + if self.max_states == 0 { + return 0; + } + let limit = self.max_states.max(1); + let mut removed = 0; + while self.undo.len().saturating_add(self.redo.len()).saturating_add(self.branches.len()) > limit { + if !self.discard_oldest() { + break; + } + removed += 1; + } + removed + } + + /// Number of past states (entries before the current one). + pub fn past_len(&self) -> usize { + self.undo.len() + } + + /// Rename the current step (e.g. after folding several steps into one with [`Self::purge_last`]). + pub fn set_current_label(&mut self, label: impl Into) { + self.current_label = label.into(); + } + + /// Forget the most recent undo state and every redo state (Edit › Purge › Undo): the + /// last step can no longer be undone and its pixels are released. + pub fn purge_last(&mut self) -> bool { + self.redo.clear(); + self.undo.pop_back().is_some() + } + + /// Forget the redo states, e.g. after undoing half of a compound step that failed. + pub fn clear_redo(&mut self) { + self.redo.clear(); + } + + /// Invalidate replay provenance after a successful edit that changes the current document. + pub fn clear_current_archive(&mut self) { + self.current_archive = None; + self.current_archive_document = None; + } + + pub fn set_current_archive(&mut self, current: &Arc, archive: Arc>) { + self.current_archive_document = Some(Arc::downgrade(current)); + self.current_archive = Some(archive); + } + + fn take_current_document(&mut self, current: Arc) -> StoredDocument

{ + let matches = self.current_archive_document.take().and_then(|bound| bound.upgrade()).is_some_and(|bound| Arc::ptr_eq(&bound, ¤t)); + match self.current_archive.take() { + Some(archive) if matches => StoredDocument::

::Archived(archive), + _ => StoredDocument::

::Resident(current), + } + } + + pub fn clear(&mut self) { + self.clear_current_archive(); + self.undo.clear(); + self.redo.clear(); + self.branches.clear(); + self.current_identity.parent = None; + } + + /// Approximate unique tile and shared binary-payload bytes held by history. + pub fn unique_bytes(&self, current: &P::Document) -> usize { + let mut seen = HashSet::new(); + P::document_bytes(current, &mut seen); + self.resident_states().iter().fold(0usize, |n, doc| n.saturating_add(P::document_bytes(doc, &mut seen))) + } + + /// Managed bytes of `current` plus the allocations only history holds (what [`History::

::trim`] + /// bounds by [`History::

::max_bytes`]). + pub fn pixel_bytes(&self, current: &P::Document) -> usize { + let mut seen = HashSet::new(); + let own = P::document_bytes(current, &mut seen); + self.resident_states().iter().fold(own, |n, doc| n.saturating_add(P::document_bytes(doc, &mut seen))) + } + + /// Keep pixel memory within [`History::

::max_bytes`]: the current document's tiles plus the + /// tiles only history holds (newest states first). The oldest undo states that don't fit are + /// dropped; the most recent one is always kept so the last step can be undone. Returns how + /// many states were dropped. + pub fn trim(&mut self, current: &P::Document) -> usize { + if self.max_bytes == 0 || self.undo.len() <= 1 { + return 0; + } + let mut seen = HashSet::new(); + let mut total = P::document_bytes(current, &mut seen); + for s in self.redo.iter().rev() { + if let Some(doc) = s.document.resident() { + total = total.saturating_add(P::document_bytes(doc, &mut seen)); + } + } + let mut keep = 0; + for s in self.undo.iter().rev() { + if let Some(doc) = s.document.resident() { + total = total.saturating_add(P::document_bytes(doc, &mut seen)); + } + if total > self.max_bytes && keep >= 1 { + break; + } + keep += 1; + } + let drop = self.undo.len() - keep; + self.undo.drain(..drop); + drop + } +} diff --git a/crates/history/tests/history.rs b/crates/history/tests/history.rs new file mode 100644 --- /dev/null +++ b/crates/history/tests/history.rs @@ -0,0 +1,298 @@ +use craft_history::{ArchivedDocument, History, HistoryState, Policy, StateIdentity}; +use std::collections::HashSet; +use std::sync::{ + Arc, + atomic::{AtomicUsize, Ordering}, +}; + +#[derive(Clone, Debug)] +struct Sheet { + id: u64, + cells: Arc>, + selection: bool, +} +#[derive(Clone, Debug)] +struct Sheets; +impl Policy for Sheets { + type Document = Sheet; + type Target = Vec; + type Id = u64; + fn has_selection(doc: &Sheet) -> bool { + doc.selection + } + fn remap_id(doc: &mut Arc, id: u64) { + if doc.id != id { + Arc::make_mut(doc).id = id; + } + } + fn document_bytes(doc: &Sheet, seen: &mut HashSet) -> usize { + if seen.insert(Arc::as_ptr(&doc.cells) as usize) { doc.cells.capacity() } else { 0 } + } + fn target_bytes(target: &Vec) -> usize { + target.capacity() * size_of::() + } +} +fn sheet(value: u8) -> Arc { + Arc::new(Sheet { id: 1, cells: Arc::new(vec![value; 32]), selection: value.is_multiple_of(2) }) +} +fn edit(history: &mut History, current: &mut Arc, value: u8) { + history.record(format!("Cell {value}"), current.clone(), vec![usize::from(value)]); + *current = sheet(value); +} +#[derive(Debug)] +struct Archive { + document: Arc, + reads: Arc, + fail: bool, +} +impl ArchivedDocument for Archive { + fn load(&self) -> Result, String> { + self.reads.fetch_add(1, Ordering::Relaxed); + if self.fail { Err("Storage unavailable".into()) } else { Ok(self.document.clone()) } + } +} +#[test] +fn branches_survive_navigation_and_checkpoint_restore() { + let mut history = History::::default(); + let mut current = sheet(0); + edit(&mut history, &mut current, 1); + edit(&mut history, &mut current, 2); + let alternate = history.current_id(); + current = history.try_undo(current).unwrap().unwrap(); + edit(&mut history, &mut current, 3); + assert_eq!(history.timeline().len(), 4); + let checkpoint = history.checkpoint(); + let mut restored = History::::from_checkpoint(checkpoint).unwrap(); + let target = restored.state_by_id(current.clone(), alternate).unwrap().load_document().unwrap(); + assert_eq!(target.cells[0], 2); + restored.jump_loaded(current, alternate, target).unwrap(); + assert_eq!(restored.current_id(), alternate); + assert_eq!(restored.current_target(), &vec![2]); + assert_eq!(restored.timeline().len(), 4); +} +#[test] +fn cold_navigation_reads_only_destination_and_menus_read_nothing() { + let mut history = History::::default(); + let mut current = sheet(0); + for value in 1..80 { + edit(&mut history, &mut current, value); + } + let reads = Arc::new(AtomicUsize::new(0)); + for state in history.checkpoint().undo { + let document = state.load_document().unwrap(); + history.replace_resident(&document, Arc::new(Archive { document: document.clone(), reads: reads.clone(), fail: false })); + } + let _ = history.timeline(); + let _ = history.checkpoint(); + assert!(history.has_past_selection()); + assert!(history.latest_selection_state().is_some()); + assert_eq!(reads.load(Ordering::Relaxed), 0); + let target = history.state_by_id(current.clone(), 0).unwrap().load_document().unwrap(); + history.jump_loaded(current, 0, target).unwrap(); + assert_eq!(reads.load(Ordering::Relaxed), 1); + assert_eq!(history.archived_states(), 78); +} +#[test] +fn failed_undo_and_redo_leave_navigation_unchanged() { + for redo in [false, true] { + let mut history = History::::default(); + let mut current = sheet(0); + edit(&mut history, &mut current, 1); + if redo { + current = history.try_undo(current).unwrap().unwrap(); + } + let target = history.state_by_id(current.clone(), history.adjacent_id(redo).unwrap()).unwrap().load_document().unwrap(); + history.replace_resident(&target, Arc::new(Archive { document: target.clone(), reads: Arc::new(AtomicUsize::new(0)), fail: true })); + let before = history.timeline_stamp(); + let checkpoint = history.checkpoint(); + let result = if redo { history.try_redo(current) } else { history.try_undo(current) }; + assert!(result.is_err()); + assert_eq!(history.timeline_stamp(), before); + assert_eq!(history.checkpoint().current_label, checkpoint.current_label); + } +} +#[test] +fn shared_allocations_are_counted_once_and_targets_count_as_metadata() { + let current = sheet(0); + let mut history = History::::default(); + history.record("First", current.clone(), vec![3, 4]); + history.record("Second", Arc::new((*current).clone()), vec![5]); + assert_eq!(history.pixel_bytes(¤t), 32); + assert_eq!(history.unique_bytes(¤t), 0); + assert!(history.metadata_bytes() > 0); + assert_eq!(history.spillable_states().len(), 2); +} +#[test] +fn cold_identity_remap_is_lazy_and_preserves_original() { + let mut history = History::::default(); + let mut current = sheet(0); + edit(&mut history, &mut current, 1); + let original = history.try_state(0).unwrap().unwrap(); + let reads = Arc::new(AtomicUsize::new(0)); + history.replace_resident(&original, Arc::new(Archive { document: original.clone(), reads: reads.clone(), fail: false })); + history.remap_document_id(99); + assert_eq!(reads.load(Ordering::Relaxed), 0); + assert_eq!(history.try_state(0).unwrap().unwrap().id, 99); + assert_eq!(original.id, 1); +} +#[test] +fn unlimited_default_and_explicit_limits_preserve_current() { + let mut history = History::::default(); + let mut current = sheet(0); + for value in 1..120 { + edit(&mut history, &mut current, value); + } + assert_eq!(history.past_len(), 119); + let id = history.current_id(); + history.max_states = 2; + assert_eq!(history.enforce_state_limit(), 117); + assert_eq!(history.past_len(), 2); + assert_eq!(history.current_id(), id); + history.max_bytes = 1; + assert_eq!(history.trim(¤t), 1); + assert!(history.can_undo()); +} +#[test] +fn recovery_rejects_duplicate_and_invalid_identity_and_oversized_labels() { + let mut history = History::::default(); + let mut current = sheet(0); + edit(&mut history, &mut current, 1); + let good = history.checkpoint(); + let mut bad = good.clone(); + bad.undo[0].identity = bad.current_identity; + assert!(History::::from_checkpoint(bad).is_err()); + let mut bad = good.clone(); + bad.current_identity.parent = Some(bad.current_identity.id); + assert!(History::::from_checkpoint(bad).is_err()); + let mut bad = good.clone(); + bad.current_identity.id = u64::MAX; + assert!(History::::from_checkpoint(bad).is_err()); + let mut bad = good; + bad.current_label = "X".repeat(4097); + assert!(History::::from_checkpoint(bad).is_err()); +} +#[test] +fn legacy_checkpoint_gets_a_valid_linear_identity_path() { + let mut history = History::::default(); + let mut current = sheet(0); + edit(&mut history, &mut current, 1); + edit(&mut history, &mut current, 2); + let mut checkpoint = history.checkpoint(); + checkpoint.current_identity = StateIdentity::default(); + for state in &mut checkpoint.undo { + state.identity = StateIdentity::default(); + } + let recovered = History::::from_checkpoint(checkpoint).unwrap(); + assert_eq!(recovered.timeline().iter().map(|entry| entry.identity.id).collect::>(), vec![0, 1, 2]); +} +#[test] +fn stale_spill_result_does_not_replace_different_snapshot() { + let mut history = History::::default(); + let mut current = sheet(0); + edit(&mut history, &mut current, 1); + let other = sheet(0); + assert!(!history.replace_resident(&other, Arc::new(Archive { document: other.clone(), reads: Arc::new(AtomicUsize::new(0)), fail: true }))); + assert!(history.try_undo(current).unwrap().is_some()); +} +#[derive(Clone, Debug)] +struct Slides; +impl Policy for Slides { + type Document = String; + type Target = (usize, usize); + type Id = (); + fn has_selection(_document: &String) -> bool { + false + } + fn remap_id(_document: &mut Arc, _id: ()) {} + fn document_bytes(document: &String, seen: &mut HashSet) -> usize { + if seen.insert(document.as_ptr() as usize) { document.capacity() } else { 0 } + } +} +#[test] +fn independent_text_document_and_slide_target_use_same_engine() { + let mut history = History::::default(); + history.set_current_target((0, 0)); + history.record("Slide title", Arc::new("Original".to_owned()), (2, 3)); + let current = Arc::new("Updated".to_owned()); + let restored = history.try_undo(current).unwrap().unwrap(); + assert_eq!(&*restored, "Original"); + assert_eq!(history.current_target(), &(0, 0)); + let updated = history.try_redo(restored).unwrap().unwrap(); + assert_eq!(&*updated, "Updated"); + assert_eq!(history.current_target(), &(2, 3)); + assert!(!history.has_past_selection()); + let state = HistoryState::::from_document("Preview", updated); + assert!(!state.has_selection()); +} + +#[test] +fn mixed_edits_branches_jumps_and_recovery_preserve_every_revision() { + let mut history = History::::default(); + let mut current = Arc::new("Root".to_owned()); + let mut expected = std::collections::BTreeMap::from([(0, current.clone())]); + let mut random = 7u64; + for step in 0..256 { + random = random.wrapping_mul(6364136223846793005).wrapping_add(1); + match random % 4 { + 0 => { + let before = current.clone(); + current = Arc::new(format!("Revision {step}")); + history.record(format!("Edit {step}"), before, (step, 0)); + expected.insert(history.current_id(), current.clone()); + } + 1 | 2 => { + let redo = random % 4 == 2; + let destination = history.adjacent_id(redo); + let restored = if redo { history.try_redo(current.clone()) } else { history.try_undo(current.clone()) }.unwrap(); + if let Some(restored) = restored { + current = restored; + assert_eq!(history.current_id(), destination.unwrap()); + } else { + assert!(destination.is_none()); + } + } + _ => { + let index = (random as usize) % expected.len(); + let id = *expected.keys().nth(index).unwrap(); + let restored = history.state_by_id(current.clone(), id).unwrap().load_document().unwrap(); + history.jump_loaded(current, id, restored.clone()).unwrap(); + current = restored; + } + } + assert_eq!(¤t, expected.get(&history.current_id()).unwrap()); + assert_eq!(history.timeline().len(), expected.len()); + if step % 7 == 0 { + history = History::::from_checkpoint(history.checkpoint()).unwrap(); + } + for (&id, original) in &expected { + let restored = history.state_by_id(current.clone(), id).unwrap().load_document().unwrap(); + assert_eq!(&restored, original); + } + } +} + +#[test] +fn pruning_one_alternate_path_preserves_other_branch_and_root() { + let mut history = History::::default(); + let root = Arc::new("Root".to_owned()); + history.record("A", root.clone(), (0, 0)); + let a = Arc::new("A".to_owned()); + history.record("B", a.clone(), (0, 0)); + let b = Arc::new("B".to_owned()); + history.record("C", b, (0, 0)); + let c = Arc::new("C".to_owned()); + history.jump_loaded(c, 1, a.clone()).unwrap(); + history.record("D", a, (0, 0)); + history.prune_descendants(2); + assert_eq!(history.timeline().iter().map(|entry| entry.identity.id).collect::>(), vec![0, 1, 4]); + assert_eq!(history.current_id(), 4); +} + +#[test] +fn text_adapter_deduplicates_current_payload_shared_with_history() { + let current = Arc::new("Title".to_owned()); + let mut history = History::::default(); + history.record("Shared payload", current.clone(), (0, 0)); + assert_eq!(history.pixel_bytes(¤t), current.capacity()); + assert_eq!(history.unique_bytes(¤t), 0); +}