Skip to main content

ftui_layout/
pane_persistent.rs

1//! Prototype: persistent / versioned `PaneTree` with structural sharing.
2//!
3//! This module is the spike deliverable for bead `bd-1k7ek.5`. It answers a
4//! single strategic question: does a persistent (structurally shared) pane tree
5//! buy enough asymptotic value — specifically **replay-free `O(1)` undo/redo** —
6//! to justify its complexity and memory footprint versus the checkpointed
7//! [`PaneInteractionTimeline`](crate::pane::PaneInteractionTimeline) replay path?
8//!
9//! # Design
10//!
11//! The canonical [`PaneTree`] stores nodes in a flat
12//! `BTreeMap<PaneId, PaneNodeRecord>` with explicit parent pointers. That shape
13//! is excellent for `O(1)` id lookup but is *not* naturally persistent: cloning
14//! the whole map to snapshot a version is `O(nodes)`, and the timeline therefore
15//! recovers historical states by **replaying** operations forward from the
16//! nearest checkpoint.
17//!
18//! [`VersionedPaneTree`] instead represents the tree as an immutable tree of
19//! `Arc<PersistentNode>`. A structural change produces a **new root** by
20//! *path-copying*: only the nodes on the root→target path are re-allocated;
21//! every off-path subtree is reused by an `Arc` clone (a refcount bump). A
22//! [`PaneVersionStore`] keeps a `Vec` of version roots plus a cursor, so undo
23//! and redo are pure index moves — no clone, no validation, no replay.
24//!
25//! Parent links are intentionally **absent** from [`PersistentNode`]. A node
26//! that knew its parent could not be shared between two versions (or two
27//! positions), so parents are reconstructed during [`VersionedPaneTree::to_pane_tree`].
28//! This is the property that makes structural sharing possible at all.
29//!
30//! # Scope (prototype simplifications)
31//!
32//! - Native path-copying covers [`SetSplitRatio`](crate::pane::PaneOperation::SetSplitRatio),
33//!   [`SplitLeaf`](crate::pane::PaneOperation::SplitLeaf),
34//!   [`CloseNode`](crate::pane::PaneOperation::CloseNode), and
35//!   [`SwapNodes`](crate::pane::PaneOperation::SwapNodes) — i.e. the resize,
36//!   create, destroy, and rearrange shapes. These exercise in-place mutation,
37//!   id-allocating insertion, sibling-promoting removal, and two-path rebuild.
38//! - [`MoveSubtree`](crate::pane::PaneOperation::MoveSubtree) and
39//!   [`NormalizeRatios`](crate::pane::PaneOperation::NormalizeRatios) use a
40//!   *rebuild fallback*: flatten to a canonical [`PaneTree`],
41//!   apply the certified conservative operation, and rebuild the persistent
42//!   tree. This guarantees total semantic parity for the differential oracle at
43//!   the cost of zero sharing for those (rare) operations.
44//! - The path-copy search is `O(nodes)` (no id→path index). A production
45//!   version would maintain a positional index for `O(depth)` location. The
46//!   headline win (`O(1)` version navigation) does not depend on this.
47//!
48//! Every native operation is proven byte-identical to
49//! [`PaneTree::apply_operation_conservative`](crate::pane::PaneTree::apply_operation_conservative)
50//! over lockstep histories in `tests/pane_persistent_equivalence.rs`.
51
52use std::collections::{BTreeMap, HashSet};
53use std::sync::Arc;
54
55use smallvec::smallvec;
56
57use crate::pane::{
58    PANE_TREE_SCHEMA_VERSION, PaneConstraints, PaneId, PaneLeaf, PaneModelError, PaneNodeKind,
59    PaneNodeRecord, PaneOperation, PaneOperationError, PaneOperationFailure, PaneOperationKind,
60    PaneOperationOutcome, PanePlacement, PaneSplit, PaneSplitRatio, PaneTree, PaneTreeSnapshot,
61    SplitAxis,
62};
63
64/// Immutable persistent pane node.
65///
66/// Split children are `Arc`-shared so that unchanged subtrees are reused across
67/// versions. Parent links are deliberately omitted (see the module docs); they
68/// are reconstructed during flattening.
69#[derive(Debug, Clone, PartialEq, Eq)]
70pub enum PersistentNode {
71    /// Terminal content node.
72    Leaf {
73        /// Stable node id (matches the canonical tree's id space).
74        id: PaneId,
75        /// Per-node size bounds.
76        constraints: PaneConstraints,
77        /// Forward-compatible record-level extension bag.
78        node_extensions: BTreeMap<String, String>,
79        /// Leaf payload (surface key + leaf-level extensions).
80        leaf: PaneLeaf,
81    },
82    /// Interior split node with two shared children.
83    Split {
84        /// Stable node id.
85        id: PaneId,
86        /// Per-node size bounds.
87        constraints: PaneConstraints,
88        /// Forward-compatible record-level extension bag.
89        node_extensions: BTreeMap<String, String>,
90        /// Split orientation.
91        axis: SplitAxis,
92        /// First/second weight ratio (always reduced).
93        ratio: PaneSplitRatio,
94        /// First child subtree.
95        first: Arc<PersistentNode>,
96        /// Second child subtree.
97        second: Arc<PersistentNode>,
98    },
99}
100
101impl PersistentNode {
102    /// Node id of this node.
103    #[must_use]
104    pub const fn id(&self) -> PaneId {
105        match self {
106            Self::Leaf { id, .. } | Self::Split { id, .. } => *id,
107        }
108    }
109
110    /// Whether this node is a leaf.
111    #[must_use]
112    pub const fn is_leaf(&self) -> bool {
113        matches!(self, Self::Leaf { .. })
114    }
115
116    /// Total number of nodes in the subtree rooted at `self`.
117    #[must_use]
118    pub fn node_count(&self) -> usize {
119        match self {
120            Self::Leaf { .. } => 1,
121            Self::Split { first, second, .. } => 1 + first.node_count() + second.node_count(),
122        }
123    }
124
125    /// Maximum depth (root counts as depth `1`).
126    #[must_use]
127    pub fn depth(&self) -> usize {
128        match self {
129            Self::Leaf { .. } => 1,
130            Self::Split { first, second, .. } => 1 + first.depth().max(second.depth()),
131        }
132    }
133}
134
135/// One immutable version of a pane tree.
136///
137/// Cloning a version is cheap: it bumps the root `Arc` refcount and clones the
138/// (usually empty) tree-level extension map.
139#[derive(Debug, Clone)]
140pub struct VersionedPaneTree {
141    schema_version: u16,
142    root: Arc<PersistentNode>,
143    next_id: PaneId,
144    extensions: BTreeMap<String, String>,
145}
146
147impl VersionedPaneTree {
148    /// Build a singleton versioned tree holding one root leaf.
149    #[must_use]
150    pub fn singleton(surface_key: impl Into<String>) -> Self {
151        let root = PaneId::MIN;
152        let node = Arc::new(PersistentNode::Leaf {
153            id: root,
154            constraints: PaneConstraints::default(),
155            node_extensions: BTreeMap::new(),
156            leaf: PaneLeaf::new(surface_key),
157        });
158        Self {
159            schema_version: PANE_TREE_SCHEMA_VERSION,
160            root: node,
161            next_id: root.checked_next().unwrap_or(root),
162            extensions: BTreeMap::new(),
163        }
164    }
165
166    /// Build a versioned tree from a canonical [`PaneTree`].
167    #[must_use]
168    pub fn from_pane_tree(tree: &PaneTree) -> Self {
169        Self::from_snapshot(&tree.to_snapshot())
170    }
171
172    /// Build a versioned tree from a canonical snapshot.
173    #[must_use]
174    pub fn from_snapshot(snapshot: &PaneTreeSnapshot) -> Self {
175        let mut records: BTreeMap<PaneId, &PaneNodeRecord> = BTreeMap::new();
176        for record in &snapshot.nodes {
177            let _ = records.insert(record.id, record);
178        }
179        let root = build_persistent(&records, snapshot.root);
180        Self {
181            schema_version: snapshot.schema_version,
182            root,
183            next_id: snapshot.next_id,
184            extensions: snapshot.extensions.clone(),
185        }
186    }
187
188    /// Root node of this version.
189    #[must_use]
190    pub fn root(&self) -> &Arc<PersistentNode> {
191        &self.root
192    }
193
194    /// Root pane id.
195    #[must_use]
196    pub fn root_id(&self) -> PaneId {
197        self.root.id()
198    }
199
200    /// Next deterministic id value.
201    #[must_use]
202    pub const fn next_id(&self) -> PaneId {
203        self.next_id
204    }
205
206    /// Schema version.
207    #[must_use]
208    pub const fn schema_version(&self) -> u16 {
209        self.schema_version
210    }
211
212    /// Number of nodes in this version.
213    #[must_use]
214    pub fn node_count(&self) -> usize {
215        self.root.node_count()
216    }
217
218    /// Maximum tree depth in this version.
219    #[must_use]
220    pub fn depth(&self) -> usize {
221        self.root.depth()
222    }
223
224    /// Flatten to a canonical snapshot (reconstructing parent links).
225    #[must_use]
226    pub fn to_snapshot(&self) -> PaneTreeSnapshot {
227        let mut nodes = Vec::with_capacity(self.node_count());
228        flatten_persistent(&self.root, None, &mut nodes);
229        let mut snapshot = PaneTreeSnapshot {
230            schema_version: self.schema_version,
231            root: self.root.id(),
232            next_id: self.next_id,
233            nodes,
234            extensions: self.extensions.clone(),
235        };
236        snapshot.canonicalize();
237        snapshot
238    }
239
240    /// Flatten and validate into a canonical [`PaneTree`].
241    ///
242    /// This is the bridge back to the production data structure and the basis of
243    /// the differential equivalence oracle.
244    ///
245    /// # Errors
246    ///
247    /// Returns the canonical tree's validation error if the flattened structure
248    /// violates a pane-tree invariant (which should never happen for a tree
249    /// built solely through [`VersionedPaneTree::apply_operation`]).
250    pub fn to_pane_tree(&self) -> Result<PaneTree, PaneModelError> {
251        PaneTree::from_snapshot(self.to_snapshot())
252    }
253
254    /// Deterministic structural hash, identical to the canonical
255    /// [`PaneTree::state_hash`](crate::pane::PaneTree::state_hash).
256    ///
257    /// # Errors
258    ///
259    /// Returns a validation error if the flattened tree is malformed.
260    pub fn state_hash(&self) -> Result<u64, PaneModelError> {
261        Ok(self.to_pane_tree()?.state_hash())
262    }
263
264    /// Apply one structural operation, returning a **new** version.
265    ///
266    /// `self` is never mutated (persistence). Native operations path-copy with
267    /// structural sharing; [`PersistentApplyStrategy::Rebuild`] operations
268    /// delegate to the certified conservative baseline.
269    ///
270    /// # Errors
271    ///
272    /// Returns a [`PersistentApplyError`] mirroring the canonical baseline's
273    /// accept/reject decision for the operation.
274    pub fn apply_operation(&self, operation: &PaneOperation) -> Result<Self, PersistentApplyError> {
275        match operation {
276            PaneOperation::SetSplitRatio { split, ratio } => {
277                self.apply_set_split_ratio(*split, *ratio)
278            }
279            PaneOperation::SplitLeaf {
280                target,
281                axis,
282                ratio,
283                placement,
284                new_leaf,
285            } => self.apply_split_leaf(*target, *axis, *ratio, *placement, new_leaf),
286            PaneOperation::CloseNode { target } => self.apply_close_node(*target),
287            PaneOperation::SwapNodes { first, second } => self.apply_swap_nodes(*first, *second),
288            PaneOperation::MoveSubtree { .. } | PaneOperation::NormalizeRatios => {
289                self.apply_via_rebuild(operation)
290            }
291        }
292    }
293
294    /// Strategy this prototype uses for an operation kind.
295    #[must_use]
296    pub const fn operation_strategy(kind: PaneOperationKind) -> PersistentApplyStrategy {
297        match kind {
298            PaneOperationKind::SetSplitRatio
299            | PaneOperationKind::SplitLeaf
300            | PaneOperationKind::CloseNode
301            | PaneOperationKind::SwapNodes => PersistentApplyStrategy::PathCopy,
302            PaneOperationKind::MoveSubtree | PaneOperationKind::NormalizeRatios => {
303                PersistentApplyStrategy::Rebuild
304            }
305        }
306    }
307
308    fn with_root(&self, root: Arc<PersistentNode>, next_id: PaneId) -> Self {
309        Self {
310            schema_version: self.schema_version,
311            root,
312            next_id,
313            extensions: self.extensions.clone(),
314        }
315    }
316
317    fn apply_set_split_ratio(
318        &self,
319        split: PaneId,
320        ratio: PaneSplitRatio,
321    ) -> Result<Self, PersistentApplyError> {
322        match rebuild_set_ratio(&self.root, split, ratio)
323            .map_err(|node_id| PersistentApplyError::NotSplit { node_id })?
324        {
325            Some(new_root) => Ok(self.with_root(new_root, self.next_id)),
326            None => Err(PersistentApplyError::MissingNode { node_id: split }),
327        }
328    }
329
330    fn apply_split_leaf(
331        &self,
332        target: PaneId,
333        axis: SplitAxis,
334        ratio: PaneSplitRatio,
335        placement: PanePlacement,
336        new_leaf: &PaneLeaf,
337    ) -> Result<Self, PersistentApplyError> {
338        let mut next_id = self.next_id;
339        match rebuild_split_leaf(
340            &self.root,
341            target,
342            axis,
343            ratio,
344            placement,
345            new_leaf,
346            &mut next_id,
347        )? {
348            Some(new_root) => Ok(self.with_root(new_root, next_id)),
349            None => Err(PersistentApplyError::MissingNode { node_id: target }),
350        }
351    }
352
353    fn apply_close_node(&self, target: PaneId) -> Result<Self, PersistentApplyError> {
354        if target == self.root.id() {
355            return Err(PersistentApplyError::CannotCloseRoot { node_id: target });
356        }
357        match rebuild_close_node(&self.root, target) {
358            Some(new_root) => Ok(self.with_root(new_root, self.next_id)),
359            None => Err(PersistentApplyError::MissingNode { node_id: target }),
360        }
361    }
362
363    fn apply_swap_nodes(
364        &self,
365        first: PaneId,
366        second: PaneId,
367    ) -> Result<Self, PersistentApplyError> {
368        if first == second {
369            // Baseline short-circuits to a no-op before existence checks.
370            return Ok(self.clone());
371        }
372        let Some(first_subtree) = find_subtree(&self.root, first) else {
373            return Err(PersistentApplyError::MissingNode { node_id: first });
374        };
375        let Some(second_subtree) = find_subtree(&self.root, second) else {
376            return Err(PersistentApplyError::MissingNode { node_id: second });
377        };
378        if subtree_contains(&first_subtree, second) {
379            return Err(PersistentApplyError::AncestorConflict {
380                ancestor: first,
381                descendant: second,
382            });
383        }
384        if subtree_contains(&second_subtree, first) {
385            return Err(PersistentApplyError::AncestorConflict {
386                ancestor: second,
387                descendant: first,
388            });
389        }
390        let new_root = replace_two(&self.root, first, &second_subtree, second, &first_subtree);
391        Ok(self.with_root(new_root, self.next_id))
392    }
393
394    fn apply_via_rebuild(&self, operation: &PaneOperation) -> Result<Self, PersistentApplyError> {
395        let mut tree = self
396            .to_pane_tree()
397            .map_err(PersistentApplyError::InvalidTree)?;
398        tree.apply_operation_conservative(0, operation.clone())
399            .map_err(|err| PersistentApplyError::Rebuild(format!("{:?}", err.reason)))?;
400        Ok(Self::from_pane_tree(&tree))
401    }
402}
403
404/// Which application strategy the prototype uses for a given operation.
405#[derive(Debug, Clone, Copy, PartialEq, Eq)]
406pub enum PersistentApplyStrategy {
407    /// Native structural-sharing path copy (`O(depth)` new nodes).
408    PathCopy,
409    /// Flatten → conservative baseline → rebuild (no sharing).
410    Rebuild,
411}
412
413/// Failure from [`VersionedPaneTree::apply_operation`].
414///
415/// The variants mirror the canonical baseline's reject conditions closely
416/// enough that the differential oracle only needs accept/reject agreement plus
417/// state-hash equality on the accept path.
418#[derive(Debug, Clone, PartialEq, Eq)]
419pub enum PersistentApplyError {
420    /// Referenced node id is absent from the tree.
421    MissingNode {
422        /// The missing node id.
423        node_id: PaneId,
424    },
425    /// Operation targeted a non-split node where a split was required.
426    NotSplit {
427        /// The offending node id.
428        node_id: PaneId,
429    },
430    /// Operation targeted a non-leaf node where a leaf was required.
431    NotLeaf {
432        /// The offending node id.
433        node_id: PaneId,
434    },
435    /// Attempted to close the root node.
436    CannotCloseRoot {
437        /// The root id.
438        node_id: PaneId,
439    },
440    /// One node is an ancestor of the other (illegal for swap).
441    AncestorConflict {
442        /// The ancestor node.
443        ancestor: PaneId,
444        /// The descendant node.
445        descendant: PaneId,
446    },
447    /// Ran out of the pane id space.
448    IdOverflow {
449        /// The id at which allocation failed.
450        current: PaneId,
451    },
452    /// The flattened tree failed canonical validation (should be unreachable).
453    InvalidTree(PaneModelError),
454    /// The rebuild-fallback baseline rejected the operation.
455    Rebuild(String),
456}
457
458/// A history of pane-tree versions with replay-free undo/redo.
459///
460/// `undo`/`redo`/`current` are `O(1)` — they move or read a cursor over a `Vec`
461/// of immutable version roots. Applying a new operation truncates any redo
462/// branch (matching the canonical timeline) and appends a new version.
463#[derive(Debug, Clone)]
464pub struct PaneVersionStore {
465    versions: Vec<VersionedPaneTree>,
466    cursor: usize,
467    max_versions: usize,
468    pruned: usize,
469}
470
471impl PaneVersionStore {
472    /// Create a store seeded with an initial version (the baseline).
473    #[must_use]
474    pub fn new(initial: VersionedPaneTree) -> Self {
475        Self {
476            versions: vec![initial],
477            cursor: 0,
478            max_versions: 0,
479            pruned: 0,
480        }
481    }
482
483    /// Create a store with a bounded retention window.
484    ///
485    /// When the retained version count exceeds `max_versions`, the oldest
486    /// versions are pruned (which discards the ability to undo into them, the
487    /// same posture as the canonical timeline's entry limit). `0` is unbounded.
488    #[must_use]
489    pub fn with_max_versions(initial: VersionedPaneTree, max_versions: usize) -> Self {
490        let mut store = Self::new(initial);
491        store.max_versions = max_versions;
492        store
493    }
494
495    /// Install a retention bound and immediately enforce it, pruning the oldest
496    /// versions if the store currently exceeds `max_versions`.
497    ///
498    /// Unlike [`with_max_versions`](Self::with_max_versions) this acts on an
499    /// existing store, so a retention policy can re-bound it retroactively.
500    /// Pruning never reaches the cursor: the current version — and therefore
501    /// [`current`](Self::current)'s state hash — plus the redo tail always
502    /// survive, so after a deep undo the store may retain more than
503    /// `max_versions` until the cursor advances again. Returns the number of
504    /// versions pruned by this call (possibly `0` when the cursor pins all
505    /// history). `0` is unbounded.
506    pub fn set_max_versions(&mut self, max_versions: usize) -> usize {
507        let pruned_before = self.pruned;
508        self.max_versions = max_versions;
509        self.enforce_retention();
510        self.pruned.saturating_sub(pruned_before)
511    }
512
513    /// Apply an operation to the current version, appending a new version.
514    ///
515    /// # Errors
516    ///
517    /// Propagates the [`PersistentApplyError`] from the underlying apply.
518    pub fn apply(
519        &mut self,
520        operation: &PaneOperation,
521    ) -> Result<&VersionedPaneTree, PersistentApplyError> {
522        let next = self.current().apply_operation(operation)?;
523        self.commit_prepared(next, false);
524        Ok(self.current())
525    }
526
527    /// Stage one live operation without publishing a version or changing redo.
528    ///
529    /// The caller must first verify that `live` is the current version's valid
530    /// canonical projection. Local ratio edits execute by native path copying;
531    /// structural edits execute once through the canonical operation API. The
532    /// returned canonical tree is ready for rendering and journal publication.
533    pub(crate) fn prepare_live_apply(
534        &self,
535        live: &PaneTree,
536        operation_id: u64,
537        operation: &PaneOperation,
538    ) -> Result<(VersionedPaneTree, PaneTree, PaneOperationOutcome), PaneOperationError> {
539        let PaneOperation::SetSplitRatio { split, ratio } = operation else {
540            let mut projected = live.clone();
541            let outcome = projected.apply_operation(operation_id, operation.clone())?;
542            let next = VersionedPaneTree::from_pane_tree(&projected);
543            return Ok((next, projected, outcome));
544        };
545
546        let before_hash = live.state_hash();
547        let failure = |reason| PaneOperationError {
548            operation_id,
549            kind: PaneOperationKind::SetSplitRatio,
550            touched_nodes: smallvec![*split],
551            before_hash,
552            after_hash: before_hash,
553            reason,
554        };
555        // Deserialization can bypass PaneSplitRatio::new. Match the canonical
556        // accessor-based normalization, including its zero-component fallback.
557        let normalized =
558            PaneSplitRatio::new(ratio.numerator(), ratio.denominator()).map_err(|_| {
559                failure(PaneOperationFailure::InvalidRatio {
560                    node_id: *split,
561                    numerator: ratio.numerator(),
562                    denominator: ratio.denominator(),
563                })
564            })?;
565        let current = self.current();
566        let root = rebuild_set_ratio(&current.root, *split, normalized)
567            .map_err(|node_id| failure(PaneOperationFailure::ParentNotSplit { node_id }))?
568            .ok_or_else(|| failure(PaneOperationFailure::MissingNode { node_id: *split }))?;
569        let next = current.with_root(root, current.next_id);
570        let projected = next
571            .to_pane_tree()
572            .map_err(|source| failure(PaneOperationFailure::Validation(source)))?;
573        let outcome = PaneOperationOutcome {
574            operation_id,
575            kind: PaneOperationKind::SetSplitRatio,
576            touched_nodes: smallvec![*split],
577            before_hash,
578            after_hash: projected.state_hash(),
579        };
580        Ok((next, projected, outcome))
581    }
582
583    /// Publish a prepared version, discarding redo only at this commit boundary.
584    ///
585    /// `coalesce` is permitted only after the caller proves the edit belongs to
586    /// the current gesture. Replacing the current version keeps its predecessor
587    /// intact; at cursor zero, even a coalesced edit appends after the baseline.
588    pub(crate) fn commit_prepared(&mut self, next: VersionedPaneTree, coalesce: bool) {
589        self.versions.truncate(self.cursor + 1);
590        if coalesce && self.cursor > 0 {
591            self.versions[self.cursor] = next;
592        } else {
593            self.versions.push(next);
594            self.cursor = self.versions.len() - 1;
595        }
596        self.enforce_retention();
597    }
598
599    /// Inspect a retained version before flattening and publishing navigation.
600    pub(crate) fn version_at(&self, index: usize) -> Option<&VersionedPaneTree> {
601        self.versions.get(index)
602    }
603
604    /// Select an existing retained version, leaving the cursor unchanged on error.
605    pub(crate) fn seek(&mut self, index: usize) -> bool {
606        if index >= self.versions.len() {
607            return false;
608        }
609        self.cursor = index;
610        true
611    }
612
613    /// Move to the previous version. Returns `false` at the oldest retained version.
614    pub fn undo(&mut self) -> bool {
615        if self.cursor == 0 {
616            return false;
617        }
618        self.cursor -= 1;
619        true
620    }
621
622    /// Move to the next version. Returns `false` at the newest version.
623    pub fn redo(&mut self) -> bool {
624        if self.cursor + 1 >= self.versions.len() {
625            return false;
626        }
627        self.cursor += 1;
628        true
629    }
630
631    /// The current version.
632    #[must_use]
633    pub fn current(&self) -> &VersionedPaneTree {
634        &self.versions[self.cursor]
635    }
636
637    /// Number of retained versions.
638    #[must_use]
639    pub fn version_count(&self) -> usize {
640        self.versions.len()
641    }
642
643    /// Current cursor index.
644    #[must_use]
645    pub const fn cursor(&self) -> usize {
646        self.cursor
647    }
648
649    /// Whether [`undo`](Self::undo) would succeed.
650    #[must_use]
651    pub const fn can_undo(&self) -> bool {
652        self.cursor > 0
653    }
654
655    /// Whether [`redo`](Self::redo) would succeed.
656    #[must_use]
657    pub fn can_redo(&self) -> bool {
658        self.cursor + 1 < self.versions.len()
659    }
660
661    /// Number of versions pruned by the retention bound so far.
662    #[must_use]
663    pub const fn pruned(&self) -> usize {
664        self.pruned
665    }
666
667    /// Compute a structural-sharing and memory-retention report.
668    #[must_use]
669    pub fn report(&self) -> PaneVersioningReport {
670        let mut distinct: HashSet<usize> = HashSet::new();
671        collect_distinct(
672            self.versions.iter().map(VersionedPaneTree::root),
673            &mut distinct,
674        );
675        let total_logical_nodes: usize = self
676            .versions
677            .iter()
678            .map(VersionedPaneTree::node_count)
679            .sum();
680        let distinct_nodes = distinct.len();
681        let shared_nodes = total_logical_nodes.saturating_sub(distinct_nodes);
682        let sharing_ratio = if total_logical_nodes == 0 {
683            0.0
684        } else {
685            shared_nodes as f64 / total_logical_nodes as f64
686        };
687        let current = self.current();
688        PaneVersioningReport {
689            version_count: self.versions.len(),
690            cursor: self.cursor,
691            distinct_nodes,
692            total_logical_nodes,
693            shared_nodes,
694            sharing_ratio,
695            current_node_count: current.node_count(),
696            current_depth: current.depth(),
697            pruned_versions: self.pruned,
698        }
699    }
700
701    /// Compute a deterministic retained-memory byte model over the distinct
702    /// nodes physically held by all retained versions.
703    ///
704    /// The model mirrors the canonical timeline's
705    /// [`retention_diagnostics`](crate::pane::PaneInteractionTimeline::retention_diagnostics)
706    /// methodology — `size_of` struct estimates plus measured string payload
707    /// bytes — so the two strategies are directly comparable. Because shared
708    /// subtrees are counted once (via `Arc` pointer identity), node bytes scale
709    /// with *distinct* nodes, not the logical node total. Tree-level extension
710    /// maps are owned separately by each version and are counted per version.
711    /// This is a payload model, not an allocator measurement: spare capacity
712    /// and allocation bookkeeping are not included.
713    #[must_use]
714    pub fn retention(&self) -> PaneVersionRetention {
715        let bytes = self.retained_byte_counts();
716        let total_logical_node_count: usize = self
717            .versions
718            .iter()
719            .map(VersionedPaneTree::node_count)
720            .sum();
721        let shared_nodes = total_logical_node_count.saturating_sub(bytes.distinct_node_count);
722        let sharing_ratio = if total_logical_node_count == 0 {
723            0.0
724        } else {
725            shared_nodes as f64 / total_logical_node_count as f64
726        };
727
728        PaneVersionRetention {
729            version_count: self.versions.len(),
730            distinct_node_count: bytes.distinct_node_count,
731            total_logical_node_count,
732            sharing_ratio,
733            distinct_struct_bytes: bytes.distinct_struct_bytes,
734            distinct_leaf_payload_bytes: bytes.distinct_leaf_payload_bytes,
735            distinct_extension_payload_bytes: bytes.distinct_extension_payload_bytes,
736            version_metadata_bytes: bytes.version_metadata_bytes,
737            version_extension_payload_bytes: bytes.version_extension_payload_bytes,
738            estimated_total_retained_bytes: bytes.estimated_total_retained_bytes,
739        }
740    }
741
742    /// Return the same byte model as [`retention`](Self::retention) without
743    /// walking each version's logical tree to calculate sharing statistics.
744    #[must_use]
745    pub(crate) fn retained_bytes(&self) -> usize {
746        self.retained_byte_counts().estimated_total_retained_bytes
747    }
748
749    fn retained_byte_counts(&self) -> PaneVersionByteCounts {
750        // Per-distinct-node byte accounting in a single traversal.
751        let mut seen: HashSet<usize> = HashSet::new();
752        let mut distinct_node_count = 0usize;
753        let mut distinct_leaf_payload_bytes = 0usize;
754        let mut distinct_extension_payload_bytes = 0usize;
755        let mut stack: Vec<&Arc<PersistentNode>> =
756            self.versions.iter().map(VersionedPaneTree::root).collect();
757        while let Some(node) = stack.pop() {
758            if !seen.insert(Arc::as_ptr(node).addr()) {
759                continue;
760            }
761            distinct_node_count += 1;
762            match &**node {
763                PersistentNode::Leaf {
764                    node_extensions,
765                    leaf,
766                    ..
767                } => {
768                    distinct_leaf_payload_bytes += leaf.surface_key.len();
769                    distinct_extension_payload_bytes += string_map_payload_bytes(&leaf.extensions)
770                        .saturating_add(string_map_payload_bytes(node_extensions));
771                }
772                PersistentNode::Split {
773                    node_extensions,
774                    first,
775                    second,
776                    ..
777                } => {
778                    distinct_extension_payload_bytes += string_map_payload_bytes(node_extensions);
779                    stack.push(first);
780                    stack.push(second);
781                }
782            }
783        }
784
785        let arc_node_bytes = std::mem::size_of::<PersistentNode>().saturating_add(ARC_HEADER_BYTES);
786        let distinct_struct_bytes = distinct_node_count.saturating_mul(arc_node_bytes);
787        let version_metadata_bytes = self
788            .versions
789            .len()
790            .saturating_mul(std::mem::size_of::<VersionedPaneTree>());
791        let version_extension_payload_bytes =
792            self.versions.iter().fold(0usize, |total, version| {
793                total.saturating_add(string_map_payload_bytes(&version.extensions))
794            });
795        let estimated_total_retained_bytes = std::mem::size_of::<Self>()
796            .saturating_add(distinct_struct_bytes)
797            .saturating_add(distinct_leaf_payload_bytes)
798            .saturating_add(distinct_extension_payload_bytes)
799            .saturating_add(version_metadata_bytes)
800            .saturating_add(version_extension_payload_bytes);
801        PaneVersionByteCounts {
802            distinct_node_count,
803            distinct_struct_bytes,
804            distinct_leaf_payload_bytes,
805            distinct_extension_payload_bytes,
806            version_metadata_bytes,
807            version_extension_payload_bytes,
808            estimated_total_retained_bytes,
809        }
810    }
811
812    fn enforce_retention(&mut self) {
813        if self.max_versions == 0 || self.versions.len() <= self.max_versions {
814            return;
815        }
816        // Never prune at or after the cursor: the version `current()` points
817        // at (and everything the user can still redo into) must survive, even
818        // when the user has undone deep into history. Any excess beyond
819        // `max_versions` is tolerated until the cursor advances again.
820        let drop_count = (self.versions.len() - self.max_versions).min(self.cursor);
821        if drop_count == 0 {
822            return;
823        }
824        let _ = self.versions.drain(0..drop_count);
825        self.pruned += drop_count;
826        self.cursor -= drop_count;
827    }
828}
829
830/// Physical counts shared by byte-only accounting and the full sharing report.
831struct PaneVersionByteCounts {
832    distinct_node_count: usize,
833    distinct_struct_bytes: usize,
834    distinct_leaf_payload_bytes: usize,
835    distinct_extension_payload_bytes: usize,
836    version_metadata_bytes: usize,
837    version_extension_payload_bytes: usize,
838    estimated_total_retained_bytes: usize,
839}
840
841/// Structural-sharing and memory-retention diagnostics for a [`PaneVersionStore`].
842#[derive(Debug, Clone, PartialEq, serde::Serialize)]
843pub struct PaneVersioningReport {
844    /// Number of retained versions.
845    pub version_count: usize,
846    /// Current cursor index.
847    pub cursor: usize,
848    /// Physically distinct `Arc` node allocations across all retained versions.
849    pub distinct_nodes: usize,
850    /// Sum of per-version node counts (what naive snapshot-per-version stores).
851    pub total_logical_nodes: usize,
852    /// `total_logical_nodes - distinct_nodes`: nodes reused via sharing.
853    pub shared_nodes: usize,
854    /// `shared_nodes / total_logical_nodes` in `[0, 1]`.
855    pub sharing_ratio: f64,
856    /// Node count of the current version.
857    pub current_node_count: usize,
858    /// Depth of the current version.
859    pub current_depth: usize,
860    /// Versions pruned by the retention bound.
861    pub pruned_versions: usize,
862}
863
864/// Deterministic retained-memory byte model for a [`PaneVersionStore`].
865///
866/// Mirrors the canonical timeline's
867/// [`PaneInteractionTimelineRetentionDiagnostics`](crate::pane::PaneInteractionTimelineRetentionDiagnostics)
868/// methodology (`size_of` struct estimates plus measured string payload bytes)
869/// so the persistent and checkpointed strategies are directly comparable. The
870/// defining economic property of structural sharing is captured here: node
871/// struct bytes scale with *physically distinct* (`Arc`-shared) nodes, not the
872/// logical node total summed over every retained version.
873#[derive(Debug, Clone, Copy, PartialEq, serde::Serialize)]
874pub struct PaneVersionRetention {
875    /// Number of retained versions held by the store.
876    pub version_count: usize,
877    /// Physically distinct `Arc` node allocations across all retained versions.
878    pub distinct_node_count: usize,
879    /// Sum of per-version node counts (what naive snapshot-per-version stores).
880    pub total_logical_node_count: usize,
881    /// `(total_logical - distinct) / total_logical` in `[0, 1]`.
882    pub sharing_ratio: f64,
883    /// `distinct_node_count × (size_of::<PersistentNode>() + ARC_HEADER_BYTES)`.
884    pub distinct_struct_bytes: usize,
885    /// Measured leaf surface-key payload bytes over distinct nodes.
886    pub distinct_leaf_payload_bytes: usize,
887    /// Measured node + leaf extension-map payload bytes over distinct nodes.
888    pub distinct_extension_payload_bytes: usize,
889    /// `version_count × size_of::<VersionedPaneTree>()` (the per-version handles).
890    pub version_metadata_bytes: usize,
891    /// Tree-level extension-map payload bytes summed over all retained versions.
892    /// These maps are cloned per version, even when every node is shared.
893    pub version_extension_payload_bytes: usize,
894    /// Estimated total retained bytes (container + structs + payload + metadata).
895    pub estimated_total_retained_bytes: usize,
896}
897
898// ---------------------------------------------------------------------------
899// Path-copying primitives (free functions over `Arc<PersistentNode>`).
900//
901// Convention for `rebuild_*`: `Ok(None)` means "target not found in this
902// subtree" (caller keeps searching / surfaces `MissingNode`); `Ok(Some(node))`
903// means "found and rebuilt"; `Err(_)` means "found but the operation is
904// illegal here". Off-path subtrees are returned via `Arc::clone`, preserving
905// structural sharing.
906// ---------------------------------------------------------------------------
907
908fn allocate_id(next_id: &mut PaneId) -> Result<PaneId, PersistentApplyError> {
909    let current = *next_id;
910    *next_id = current
911        .checked_next()
912        .map_err(|_| PersistentApplyError::IdOverflow { current })?;
913    Ok(current)
914}
915
916fn rebuild_split_with(
917    template: &Arc<PersistentNode>,
918    first: Arc<PersistentNode>,
919    second: Arc<PersistentNode>,
920) -> Arc<PersistentNode> {
921    match &**template {
922        PersistentNode::Split {
923            id,
924            constraints,
925            node_extensions,
926            axis,
927            ratio,
928            ..
929        } => Arc::new(PersistentNode::Split {
930            id: *id,
931            constraints: *constraints,
932            node_extensions: node_extensions.clone(),
933            axis: *axis,
934            ratio: *ratio,
935            first,
936            second,
937        }),
938        // Only ever called with a split template.
939        PersistentNode::Leaf { .. } => template.clone(),
940    }
941}
942
943fn rebuild_set_ratio(
944    node: &Arc<PersistentNode>,
945    target: PaneId,
946    ratio: PaneSplitRatio,
947) -> Result<Option<Arc<PersistentNode>>, PaneId> {
948    // The only path-copy error is a matching leaf; return its id so each
949    // caller can preserve its own public error type without replaying an edit.
950    match &**node {
951        PersistentNode::Leaf { id, .. } => {
952            if *id == target {
953                Err(target)
954            } else {
955                Ok(None)
956            }
957        }
958        PersistentNode::Split {
959            id,
960            constraints,
961            node_extensions,
962            axis,
963            first,
964            second,
965            ..
966        } => {
967            if *id == target {
968                return Ok(Some(Arc::new(PersistentNode::Split {
969                    id: *id,
970                    constraints: *constraints,
971                    node_extensions: node_extensions.clone(),
972                    axis: *axis,
973                    ratio,
974                    first: first.clone(),
975                    second: second.clone(),
976                })));
977            }
978            if let Some(new_first) = rebuild_set_ratio(first, target, ratio)? {
979                return Ok(Some(rebuild_split_with(node, new_first, second.clone())));
980            }
981            if let Some(new_second) = rebuild_set_ratio(second, target, ratio)? {
982                return Ok(Some(rebuild_split_with(node, first.clone(), new_second)));
983            }
984            Ok(None)
985        }
986    }
987}
988
989#[allow(clippy::too_many_arguments)]
990fn rebuild_split_leaf(
991    node: &Arc<PersistentNode>,
992    target: PaneId,
993    axis: SplitAxis,
994    ratio: PaneSplitRatio,
995    placement: PanePlacement,
996    new_leaf: &PaneLeaf,
997    next_id: &mut PaneId,
998) -> Result<Option<Arc<PersistentNode>>, PersistentApplyError> {
999    match &**node {
1000        PersistentNode::Leaf { id, .. } => {
1001            if *id != target {
1002                return Ok(None);
1003            }
1004            // Allocation order matches the baseline: split id, then leaf id.
1005            let split_id = allocate_id(next_id)?;
1006            let new_leaf_id = allocate_id(next_id)?;
1007            let existing = node.clone();
1008            let incoming = Arc::new(PersistentNode::Leaf {
1009                id: new_leaf_id,
1010                constraints: PaneConstraints::default(),
1011                node_extensions: BTreeMap::new(),
1012                leaf: new_leaf.clone(),
1013            });
1014            let (first, second) = match placement {
1015                PanePlacement::ExistingFirst => (existing, incoming),
1016                PanePlacement::IncomingFirst => (incoming, existing),
1017            };
1018            Ok(Some(Arc::new(PersistentNode::Split {
1019                id: split_id,
1020                constraints: PaneConstraints::default(),
1021                node_extensions: BTreeMap::new(),
1022                axis,
1023                ratio,
1024                first,
1025                second,
1026            })))
1027        }
1028        PersistentNode::Split {
1029            id, first, second, ..
1030        } => {
1031            if *id == target {
1032                return Err(PersistentApplyError::NotLeaf { node_id: target });
1033            }
1034            if let Some(new_first) =
1035                rebuild_split_leaf(first, target, axis, ratio, placement, new_leaf, next_id)?
1036            {
1037                return Ok(Some(rebuild_split_with(node, new_first, second.clone())));
1038            }
1039            if let Some(new_second) =
1040                rebuild_split_leaf(second, target, axis, ratio, placement, new_leaf, next_id)?
1041            {
1042                return Ok(Some(rebuild_split_with(node, first.clone(), new_second)));
1043            }
1044            Ok(None)
1045        }
1046    }
1047}
1048
1049/// Close `target` by promoting its sibling. Returns the rebuilt parent path, or
1050/// `None` if `target` is not a child anywhere in the subtree.
1051fn rebuild_close_node(node: &Arc<PersistentNode>, target: PaneId) -> Option<Arc<PersistentNode>> {
1052    let PersistentNode::Split { first, second, .. } = &**node else {
1053        return None;
1054    };
1055    if first.id() == target {
1056        return Some(second.clone());
1057    }
1058    if second.id() == target {
1059        return Some(first.clone());
1060    }
1061    if let Some(new_first) = rebuild_close_node(first, target) {
1062        return Some(rebuild_split_with(node, new_first, second.clone()));
1063    }
1064    if let Some(new_second) = rebuild_close_node(second, target) {
1065        return Some(rebuild_split_with(node, first.clone(), new_second));
1066    }
1067    None
1068}
1069
1070/// Find the subtree rooted at `target` (an `Arc` clone), if present.
1071fn find_subtree(node: &Arc<PersistentNode>, target: PaneId) -> Option<Arc<PersistentNode>> {
1072    if node.id() == target {
1073        return Some(node.clone());
1074    }
1075    if let PersistentNode::Split { first, second, .. } = &**node {
1076        if let Some(found) = find_subtree(first, target) {
1077            return Some(found);
1078        }
1079        if let Some(found) = find_subtree(second, target) {
1080            return Some(found);
1081        }
1082    }
1083    None
1084}
1085
1086/// Whether `target` appears anywhere in the subtree (including the root).
1087fn subtree_contains(node: &Arc<PersistentNode>, target: PaneId) -> bool {
1088    if node.id() == target {
1089        return true;
1090    }
1091    match &**node {
1092        PersistentNode::Leaf { .. } => false,
1093        PersistentNode::Split { first, second, .. } => {
1094            subtree_contains(first, target) || subtree_contains(second, target)
1095        }
1096    }
1097}
1098
1099/// Rebuild `node`, replacing the node with id `a` by `arc_a` and id `b` by
1100/// `arc_b`. Subtrees containing neither are returned by `Arc::clone`, so sharing
1101/// is preserved everywhere off the two replacement paths.
1102fn replace_two(
1103    node: &Arc<PersistentNode>,
1104    a: PaneId,
1105    arc_a: &Arc<PersistentNode>,
1106    b: PaneId,
1107    arc_b: &Arc<PersistentNode>,
1108) -> Arc<PersistentNode> {
1109    if node.id() == a {
1110        return arc_a.clone();
1111    }
1112    if node.id() == b {
1113        return arc_b.clone();
1114    }
1115    match &**node {
1116        PersistentNode::Leaf { .. } => node.clone(),
1117        PersistentNode::Split { first, second, .. } => {
1118            let new_first = replace_two(first, a, arc_a, b, arc_b);
1119            let new_second = replace_two(second, a, arc_a, b, arc_b);
1120            if Arc::ptr_eq(&new_first, first) && Arc::ptr_eq(&new_second, second) {
1121                node.clone()
1122            } else {
1123                rebuild_split_with(node, new_first, new_second)
1124            }
1125        }
1126    }
1127}
1128
1129fn build_persistent(
1130    records: &BTreeMap<PaneId, &PaneNodeRecord>,
1131    id: PaneId,
1132) -> Arc<PersistentNode> {
1133    let record = records
1134        .get(&id)
1135        .copied()
1136        .expect("snapshot references only existing ids");
1137    match &record.kind {
1138        PaneNodeKind::Leaf(leaf) => Arc::new(PersistentNode::Leaf {
1139            id: record.id,
1140            constraints: record.constraints,
1141            node_extensions: record.extensions.clone(),
1142            leaf: leaf.clone(),
1143        }),
1144        PaneNodeKind::Split(split) => Arc::new(PersistentNode::Split {
1145            id: record.id,
1146            constraints: record.constraints,
1147            node_extensions: record.extensions.clone(),
1148            axis: split.axis,
1149            ratio: split.ratio,
1150            first: build_persistent(records, split.first),
1151            second: build_persistent(records, split.second),
1152        }),
1153    }
1154}
1155
1156fn flatten_persistent(
1157    node: &Arc<PersistentNode>,
1158    parent: Option<PaneId>,
1159    out: &mut Vec<PaneNodeRecord>,
1160) {
1161    match &**node {
1162        PersistentNode::Leaf {
1163            id,
1164            constraints,
1165            node_extensions,
1166            leaf,
1167        } => out.push(PaneNodeRecord {
1168            id: *id,
1169            parent,
1170            constraints: *constraints,
1171            kind: PaneNodeKind::Leaf(leaf.clone()),
1172            extensions: node_extensions.clone(),
1173        }),
1174        PersistentNode::Split {
1175            id,
1176            constraints,
1177            node_extensions,
1178            axis,
1179            ratio,
1180            first,
1181            second,
1182        } => {
1183            out.push(PaneNodeRecord {
1184                id: *id,
1185                parent,
1186                constraints: *constraints,
1187                kind: PaneNodeKind::Split(PaneSplit {
1188                    axis: *axis,
1189                    ratio: *ratio,
1190                    first: first.id(),
1191                    second: second.id(),
1192                }),
1193                extensions: node_extensions.clone(),
1194            });
1195            flatten_persistent(first, Some(*id), out);
1196            flatten_persistent(second, Some(*id), out);
1197        }
1198    }
1199}
1200
1201/// Bytes an `Arc<T>` allocation prepends ahead of `T`: the strong and weak
1202/// reference counters (`AtomicUsize` each). Added to `size_of::<PersistentNode>()`
1203/// so the persistent retained-memory model accounts for the real heap cost of
1204/// each physically distinct shared node.
1205const ARC_HEADER_BYTES: usize = 2 * std::mem::size_of::<usize>();
1206
1207/// Measured payload bytes (keys + values) of a string→string extension map.
1208///
1209/// Mirrors the canonical timeline's private helper of the same name (in
1210/// [`crate::pane`]) so the persistent and checkpointed retained-memory models
1211/// are byte-comparable.
1212pub(crate) fn string_map_payload_bytes(map: &BTreeMap<String, String>) -> usize {
1213    map.iter()
1214        .map(|(key, value)| key.len().saturating_add(value.len()))
1215        .sum()
1216}
1217
1218/// Collect physically distinct node allocations reachable from `roots`.
1219///
1220/// A node already in `seen` short-circuits: because sharing is structural, a
1221/// previously visited `Arc` shares its entire subtree, so the subtree is already
1222/// counted. This makes distinct-counting proportional to the number of distinct
1223/// nodes rather than the logical node total.
1224fn collect_distinct<'a>(
1225    roots: impl Iterator<Item = &'a Arc<PersistentNode>>,
1226    seen: &mut HashSet<usize>,
1227) {
1228    let mut stack: Vec<&Arc<PersistentNode>> = roots.collect();
1229    while let Some(node) = stack.pop() {
1230        let key = Arc::as_ptr(node).addr();
1231        if !seen.insert(key) {
1232            continue;
1233        }
1234        if let PersistentNode::Split { first, second, .. } = &**node {
1235            stack.push(first);
1236            stack.push(second);
1237        }
1238    }
1239}
1240
1241#[cfg(test)]
1242mod tests {
1243    use super::*;
1244    use crate::pane::PaneTree;
1245
1246    fn ratio(n: u32, d: u32) -> PaneSplitRatio {
1247        PaneSplitRatio::new(n, d).expect("valid ratio")
1248    }
1249
1250    /// Build a small balanced-ish tree by splitting the root then its children.
1251    /// Returns the version plus the ids of the two interior splits.
1252    fn build_demo() -> VersionedPaneTree {
1253        let v0 = VersionedPaneTree::singleton("root");
1254        // Split root leaf (id 1) → split id 2, new leaf id 3.
1255        let op1 = PaneOperation::SplitLeaf {
1256            target: PaneId::MIN,
1257            axis: SplitAxis::Horizontal,
1258            ratio: ratio(1, 1),
1259            placement: PanePlacement::ExistingFirst,
1260            new_leaf: PaneLeaf::new("b"),
1261        };
1262        let v1 = v0.apply_operation(&op1).expect("split root");
1263        // Split leaf id 1 again → split id 4, new leaf id 5.
1264        let op2 = PaneOperation::SplitLeaf {
1265            target: PaneId::MIN,
1266            axis: SplitAxis::Vertical,
1267            ratio: ratio(2, 1),
1268            placement: PanePlacement::ExistingFirst,
1269            new_leaf: PaneLeaf::new("c"),
1270        };
1271        v1.apply_operation(&op2).expect("split leaf 1")
1272    }
1273
1274    fn assert_live_prepare_matches_canonical(
1275        live: &PaneTree,
1276        operation_id: u64,
1277        operation: &PaneOperation,
1278    ) -> Result<PaneTree, PaneOperationError> {
1279        let store = PaneVersionStore::new(VersionedPaneTree::from_pane_tree(live));
1280        let before = live.to_snapshot();
1281        let previous_root = Arc::clone(store.current().root());
1282        let mut canonical = live.clone();
1283        let expected = canonical.apply_operation(operation_id, operation.clone());
1284        let prepared = store.prepare_live_apply(live, operation_id, operation);
1285        assert_eq!(
1286            prepared.as_ref().map(|(_, _, outcome)| outcome),
1287            expected.as_ref(),
1288            "complete canonical outcome/error differs for {operation:?}"
1289        );
1290        assert_eq!(live.to_snapshot(), before, "preparation published a tree");
1291        assert_eq!(store.current().to_snapshot(), before);
1292        assert!(Arc::ptr_eq(&previous_root, store.current().root()));
1293        assert_eq!(store.version_count(), 1);
1294        assert_eq!(store.cursor(), 0);
1295        assert_eq!(store.pruned(), 0);
1296        prepared.map(|(next, projected, _)| {
1297            assert_eq!(projected.to_snapshot(), canonical.to_snapshot());
1298            assert_eq!(next.to_snapshot(), canonical.to_snapshot());
1299            assert_eq!(next.next_id(), canonical.next_id());
1300            projected
1301        })
1302    }
1303
1304    #[test]
1305    fn live_prepare_local_normalizes_deserialized_ratios_and_preserves_sharing() {
1306        let base = build_demo();
1307        let live = base.to_pane_tree().expect("valid base");
1308        let store = PaneVersionStore::new(base.clone());
1309        let split = PaneId::new(4).unwrap();
1310        for (numerator, denominator) in [(6, 4), (0, 4), (6, 0), (0, 0)] {
1311            let deserialized: PaneSplitRatio = serde_json::from_value(serde_json::json!({
1312                "numerator": numerator,
1313                "denominator": denominator,
1314            }))
1315            .expect("raw serialized ratio");
1316            let operation = PaneOperation::SetSplitRatio {
1317                split,
1318                ratio: deserialized,
1319            };
1320            let expected = assert_live_prepare_matches_canonical(&live, 71, &operation)
1321                .expect("canonical accessor normalization accepts the ratio");
1322            let (next, projected, outcome) = store
1323                .prepare_live_apply(&live, 71, &operation)
1324                .expect("prepare native ratio edit");
1325            assert_eq!(projected.to_snapshot(), expected.to_snapshot());
1326            assert_eq!(outcome.touched_nodes.as_slice(), &[split]);
1327            let before_untouched = find_subtree(base.root(), PaneId::new(3).unwrap()).unwrap();
1328            let after_untouched = find_subtree(next.root(), PaneId::new(3).unwrap()).unwrap();
1329            assert!(Arc::ptr_eq(&before_untouched, &after_untouched));
1330            assert!(!Arc::ptr_eq(base.root(), next.root()));
1331            assert_eq!(store.cursor(), 0, "prepare must not publish a version");
1332        }
1333    }
1334
1335    #[test]
1336    fn live_prepare_local_rejections_preserve_exact_typed_errors() {
1337        let live = build_demo().to_pane_tree().expect("valid base");
1338        for (split, reason) in [
1339            (
1340                PaneId::MIN,
1341                PaneOperationFailure::ParentNotSplit {
1342                    node_id: PaneId::MIN,
1343                },
1344            ),
1345            (
1346                PaneId::new(u64::MAX).unwrap(),
1347                PaneOperationFailure::MissingNode {
1348                    node_id: PaneId::new(u64::MAX).unwrap(),
1349                },
1350            ),
1351        ] {
1352            let error = assert_live_prepare_matches_canonical(
1353                &live,
1354                72,
1355                &PaneOperation::SetSplitRatio {
1356                    split,
1357                    ratio: ratio(3, 2),
1358                },
1359            )
1360            .expect_err("invalid split must be rejected");
1361            assert_eq!(error.reason, reason);
1362            assert_eq!(error.before_hash, error.after_hash);
1363        }
1364    }
1365
1366    #[test]
1367    fn live_prepare_accepts_every_structural_family_with_exact_outcomes() {
1368        let mut snapshot = build_demo().to_snapshot();
1369        for node in &mut snapshot.nodes {
1370            if let PaneNodeKind::Split(split) = &mut node.kind {
1371                split.ratio = serde_json::from_str(r#"{"numerator":6,"denominator":4}"#)
1372                    .expect("non-reduced serialized ratio");
1373            }
1374        }
1375        let live = PaneTree::from_snapshot(snapshot).expect("valid non-reduced baseline");
1376        let operations = [
1377            PaneOperation::SplitLeaf {
1378                target: PaneId::new(3).unwrap(),
1379                axis: SplitAxis::Vertical,
1380                ratio: ratio(3, 2),
1381                placement: PanePlacement::IncomingFirst,
1382                new_leaf: PaneLeaf::new("live split"),
1383            },
1384            PaneOperation::CloseNode {
1385                target: PaneId::new(5).unwrap(),
1386            },
1387            PaneOperation::MoveSubtree {
1388                source: PaneId::new(3).unwrap(),
1389                target: PaneId::new(5).unwrap(),
1390                axis: SplitAxis::Horizontal,
1391                ratio: ratio(2, 3),
1392                placement: PanePlacement::IncomingFirst,
1393            },
1394            PaneOperation::SwapNodes {
1395                first: PaneId::MIN,
1396                second: PaneId::new(3).unwrap(),
1397            },
1398            PaneOperation::NormalizeRatios,
1399        ];
1400        for operation in operations {
1401            let projected = assert_live_prepare_matches_canonical(&live, 73, &operation)
1402                .expect("structural operation must be accepted");
1403            assert_ne!(projected.to_snapshot(), live.to_snapshot());
1404        }
1405        // Canonical self-swap is an accepted no-op even when the id is absent.
1406        let missing = PaneId::new(u64::MAX).unwrap();
1407        let projected = assert_live_prepare_matches_canonical(
1408            &live,
1409            74,
1410            &PaneOperation::SwapNodes {
1411                first: missing,
1412                second: missing,
1413            },
1414        )
1415        .expect("canonical self-swap semantics");
1416        assert_eq!(projected.to_snapshot(), live.to_snapshot());
1417    }
1418
1419    #[test]
1420    fn live_prepare_structural_rejections_match_complete_canonical_errors() {
1421        let live = build_demo().to_pane_tree().expect("valid base");
1422        let missing = PaneId::new(u64::MAX).unwrap();
1423        let root = live.root();
1424        let leaf = PaneId::MIN;
1425        let split = PaneId::new(4).unwrap();
1426        let split_leaf = |target| PaneOperation::SplitLeaf {
1427            target,
1428            axis: SplitAxis::Vertical,
1429            ratio: ratio(1, 1),
1430            placement: PanePlacement::ExistingFirst,
1431            new_leaf: PaneLeaf::new("rejected"),
1432        };
1433        let move_subtree = |source, target| PaneOperation::MoveSubtree {
1434            source,
1435            target,
1436            axis: SplitAxis::Vertical,
1437            ratio: ratio(1, 1),
1438            placement: PanePlacement::ExistingFirst,
1439        };
1440        let operations = [
1441            split_leaf(missing),
1442            split_leaf(root),
1443            PaneOperation::CloseNode { target: missing },
1444            PaneOperation::CloseNode { target: root },
1445            move_subtree(missing, leaf),
1446            move_subtree(leaf, missing),
1447            move_subtree(root, leaf),
1448            move_subtree(leaf, leaf),
1449            move_subtree(split, leaf),
1450            move_subtree(leaf, split),
1451            PaneOperation::SwapNodes {
1452                first: missing,
1453                second: leaf,
1454            },
1455            PaneOperation::SwapNodes {
1456                first: leaf,
1457                second: missing,
1458            },
1459            PaneOperation::SwapNodes {
1460                first: split,
1461                second: leaf,
1462            },
1463            PaneOperation::SwapNodes {
1464                first: leaf,
1465                second: split,
1466            },
1467        ];
1468        for operation in operations {
1469            assert_live_prepare_matches_canonical(&live, 75, &operation)
1470                .expect_err("invalid structural edit must be rejected");
1471        }
1472    }
1473
1474    #[test]
1475    fn live_prepare_preserves_partial_failure_hashes_without_publishing() {
1476        let mut snapshot = build_demo().to_snapshot();
1477        snapshot.next_id = PaneId::new(u64::MAX - 1).unwrap();
1478        let live = PaneTree::from_snapshot(snapshot.clone()).expect("one allocatable id");
1479        let split = PaneOperation::SplitLeaf {
1480            target: PaneId::MIN,
1481            axis: SplitAxis::Horizontal,
1482            ratio: ratio(1, 1),
1483            placement: PanePlacement::ExistingFirst,
1484            new_leaf: PaneLeaf::new("overflow"),
1485        };
1486        let error = assert_live_prepare_matches_canonical(&live, 76, &split)
1487            .expect_err("second allocation must fail");
1488        assert_ne!(error.before_hash, error.after_hash);
1489        assert_eq!(
1490            error.reason,
1491            PaneOperationFailure::PaneIdOverflow {
1492                current: PaneId::new(u64::MAX).unwrap(),
1493            }
1494        );
1495
1496        snapshot.next_id = PaneId::new(u64::MAX).unwrap();
1497        let live = PaneTree::from_snapshot(snapshot).expect("exhausted but valid allocator");
1498        let error = assert_live_prepare_matches_canonical(&live, 77, &split)
1499            .expect_err("first allocation must fail");
1500        assert_eq!(error.before_hash, error.after_hash);
1501        let error = assert_live_prepare_matches_canonical(
1502            &live,
1503            78,
1504            &PaneOperation::MoveSubtree {
1505                source: PaneId::new(3).unwrap(),
1506                target: PaneId::new(5).unwrap(),
1507                axis: SplitAxis::Vertical,
1508                ratio: ratio(1, 1),
1509                placement: PanePlacement::ExistingFirst,
1510            },
1511        )
1512        .expect_err("allocation after subtree detach must fail");
1513        assert_ne!(error.before_hash, error.after_hash);
1514        assert!(
1515            error.touched_nodes.len() > 2,
1516            "preserve the grown touched set"
1517        );
1518    }
1519
1520    #[test]
1521    fn live_commit_coalesces_and_branches_without_replacing_the_baseline() {
1522        let mut store = PaneVersionStore::new(build_demo());
1523        let baseline = store.current().to_snapshot();
1524        let mut previous_gesture = baseline.clone();
1525        for (numerator, coalesce, versions) in [(3_u32, true, 2), (4, true, 2), (5, false, 3)] {
1526            let live = store
1527                .current()
1528                .to_pane_tree()
1529                .expect("valid selected version");
1530            let (next, projected, _) = store
1531                .prepare_live_apply(
1532                    &live,
1533                    u64::from(numerator),
1534                    &PaneOperation::SetSplitRatio {
1535                        split: PaneId::new(4).unwrap(),
1536                        ratio: ratio(numerator, 1),
1537                    },
1538                )
1539                .expect("prepare gesture edit");
1540            assert_eq!(store.current().to_snapshot(), live.to_snapshot());
1541            store.commit_prepared(next, coalesce);
1542            assert_eq!(store.version_count(), versions);
1543            assert_eq!(store.current().to_snapshot(), projected.to_snapshot());
1544            assert_eq!(store.version_at(0).unwrap().to_snapshot(), baseline);
1545            if numerator == 4 {
1546                previous_gesture = projected.to_snapshot();
1547            }
1548        }
1549        assert!(store.seek(1));
1550        assert_eq!(store.current().to_snapshot(), previous_gesture);
1551        let old_redo = store.version_at(2).unwrap().to_snapshot();
1552        let live = store
1553            .current()
1554            .to_pane_tree()
1555            .expect("selected earlier version");
1556        let invalid = PaneOperation::CloseNode {
1557            target: live.root(),
1558        };
1559        store
1560            .prepare_live_apply(&live, 79, &invalid)
1561            .expect_err("reject closing root");
1562        assert_eq!(store.cursor(), 1);
1563        assert_eq!(store.version_at(2).unwrap().to_snapshot(), old_redo);
1564
1565        for (numerator, coalesce, versions) in [(6_u32, true, 2), (7, false, 3), (8, false, 3)] {
1566            assert!(store.seek(1));
1567            let live = store.current().to_pane_tree().expect("valid branch base");
1568            let (next, projected, _) = store
1569                .prepare_live_apply(
1570                    &live,
1571                    u64::from(numerator),
1572                    &PaneOperation::SetSplitRatio {
1573                        split: PaneId::new(4).unwrap(),
1574                        ratio: ratio(numerator, 1),
1575                    },
1576                )
1577                .expect("prepare branch");
1578            store.commit_prepared(next, coalesce);
1579            assert_eq!(store.version_count(), versions);
1580            assert!(!store.can_redo());
1581            assert_eq!(store.current().to_snapshot(), projected.to_snapshot());
1582            assert_eq!(store.version_at(0).unwrap().to_snapshot(), baseline);
1583            assert_ne!(store.current().to_snapshot(), old_redo);
1584        }
1585        assert_eq!(store.pruned(), 0);
1586    }
1587
1588    #[test]
1589    fn live_seek_and_version_lookup_preserve_invalid_navigation_state() {
1590        let mut store = PaneVersionStore::new(build_demo());
1591        for numerator in [3, 4] {
1592            store
1593                .apply(&PaneOperation::SetSplitRatio {
1594                    split: PaneId::new(4).unwrap(),
1595                    ratio: ratio(numerator, 1),
1596                })
1597                .expect("prototype apply remains functional");
1598        }
1599        let head = store.current().to_snapshot();
1600        assert!(store.seek(0));
1601        let baseline = store.current().to_snapshot();
1602        for invalid in [store.version_count(), usize::MAX] {
1603            assert!(store.version_at(invalid).is_none());
1604            assert!(!store.seek(invalid));
1605            assert_eq!(store.cursor(), 0);
1606            assert_eq!(store.current().to_snapshot(), baseline);
1607            assert!(store.can_redo());
1608        }
1609        assert!(store.seek(2));
1610        assert_eq!(store.current().to_snapshot(), head);
1611        assert!(store.seek(2), "seeking the selected version is valid");
1612        assert!(!store.redo());
1613        assert!(store.undo());
1614        assert_eq!(store.cursor(), 1);
1615        assert!(store.redo());
1616        assert_eq!(store.current().to_snapshot(), head);
1617    }
1618
1619    #[test]
1620    fn singleton_round_trips_through_canonical_tree() {
1621        let versioned = VersionedPaneTree::singleton("root");
1622        let canonical = PaneTree::singleton("root");
1623        assert_eq!(
1624            versioned.state_hash().expect("hash"),
1625            canonical.state_hash()
1626        );
1627    }
1628
1629    #[test]
1630    fn split_leaf_matches_canonical_baseline() {
1631        let versioned = build_demo();
1632        let mut canonical = PaneTree::singleton("root");
1633        canonical
1634            .apply_operation_conservative(
1635                1,
1636                PaneOperation::SplitLeaf {
1637                    target: PaneId::MIN,
1638                    axis: SplitAxis::Horizontal,
1639                    ratio: ratio(1, 1),
1640                    placement: PanePlacement::ExistingFirst,
1641                    new_leaf: PaneLeaf::new("b"),
1642                },
1643            )
1644            .expect("split root");
1645        canonical
1646            .apply_operation_conservative(
1647                2,
1648                PaneOperation::SplitLeaf {
1649                    target: PaneId::MIN,
1650                    axis: SplitAxis::Vertical,
1651                    ratio: ratio(2, 1),
1652                    placement: PanePlacement::ExistingFirst,
1653                    new_leaf: PaneLeaf::new("c"),
1654                },
1655            )
1656            .expect("split leaf 1");
1657        assert_eq!(
1658            versioned.state_hash().expect("hash"),
1659            canonical.state_hash()
1660        );
1661        assert_eq!(versioned.next_id(), canonical.next_id());
1662    }
1663
1664    #[test]
1665    fn set_split_ratio_preserves_off_path_sharing() {
1666        let base = build_demo();
1667        // The interior split created first is id 2 (root). Its second child is
1668        // leaf id 3, which must be physically shared after we re-ratio split id 4.
1669        let before_second = match &**base.root() {
1670            PersistentNode::Split { second, .. } => second.clone(),
1671            PersistentNode::Leaf { .. } => unreachable!("root is a split"),
1672        };
1673        let next = base
1674            .apply_operation(&PaneOperation::SetSplitRatio {
1675                split: PaneId::new(4).unwrap(),
1676                ratio: ratio(3, 1),
1677            })
1678            .expect("set ratio");
1679        let after_second = match &**next.root() {
1680            PersistentNode::Split { second, .. } => second.clone(),
1681            PersistentNode::Leaf { .. } => unreachable!("root is a split"),
1682        };
1683        assert!(
1684            Arc::ptr_eq(&before_second, &after_second),
1685            "off-path subtree must be shared, not re-allocated"
1686        );
1687        // And the root itself was re-allocated (the path changed).
1688        assert!(!Arc::ptr_eq(base.root(), next.root()));
1689    }
1690
1691    #[test]
1692    fn set_split_ratio_on_leaf_is_rejected() {
1693        let base = build_demo();
1694        let err = base
1695            .apply_operation(&PaneOperation::SetSplitRatio {
1696                split: PaneId::MIN,
1697                ratio: ratio(1, 1),
1698            })
1699            .expect_err("leaf is not a split");
1700        assert_eq!(
1701            err,
1702            PersistentApplyError::NotSplit {
1703                node_id: PaneId::MIN
1704            }
1705        );
1706    }
1707
1708    #[test]
1709    fn close_node_promotes_sibling_like_baseline() {
1710        let base = build_demo();
1711        let op = PaneOperation::CloseNode {
1712            target: PaneId::new(3).unwrap(),
1713        };
1714        let next = base.apply_operation(&op).expect("close leaf 3");
1715
1716        let mut canonical = base.to_pane_tree().expect("flatten");
1717        canonical
1718            .apply_operation_conservative(99, op)
1719            .expect("close leaf 3");
1720        assert_eq!(next.state_hash().expect("hash"), canonical.state_hash());
1721    }
1722
1723    #[test]
1724    fn close_root_is_rejected() {
1725        let base = build_demo();
1726        let err = base
1727            .apply_operation(&PaneOperation::CloseNode {
1728                target: base.root_id(),
1729            })
1730            .expect_err("cannot close root");
1731        assert!(matches!(err, PersistentApplyError::CannotCloseRoot { .. }));
1732    }
1733
1734    #[test]
1735    fn swap_nodes_matches_baseline_and_shares() {
1736        let base = build_demo();
1737        let op = PaneOperation::SwapNodes {
1738            first: PaneId::new(3).unwrap(),
1739            second: PaneId::new(5).unwrap(),
1740        };
1741        let next = base.apply_operation(&op).expect("swap leaves");
1742
1743        let mut canonical = base.to_pane_tree().expect("flatten");
1744        canonical.apply_operation_conservative(7, op).expect("swap");
1745        assert_eq!(next.state_hash().expect("hash"), canonical.state_hash());
1746    }
1747
1748    #[test]
1749    fn swap_with_self_is_noop() {
1750        let base = build_demo();
1751        let next = base
1752            .apply_operation(&PaneOperation::SwapNodes {
1753                first: PaneId::new(3).unwrap(),
1754                second: PaneId::new(3).unwrap(),
1755            })
1756            .expect("self swap is a no-op");
1757        assert_eq!(next.state_hash().expect("a"), base.state_hash().expect("b"));
1758    }
1759
1760    #[test]
1761    fn version_store_undo_redo_is_o1_and_correct() {
1762        let mut store = PaneVersionStore::new(VersionedPaneTree::singleton("root"));
1763        let h0 = store.current().state_hash().expect("h0");
1764        store
1765            .apply(&PaneOperation::SplitLeaf {
1766                target: PaneId::MIN,
1767                axis: SplitAxis::Horizontal,
1768                ratio: ratio(1, 1),
1769                placement: PanePlacement::ExistingFirst,
1770                new_leaf: PaneLeaf::new("b"),
1771            })
1772            .expect("split");
1773        let h1 = store.current().state_hash().expect("h1");
1774        assert_ne!(h0, h1);
1775
1776        assert!(store.undo());
1777        assert_eq!(store.current().state_hash().expect("u"), h0);
1778        assert!(store.redo());
1779        assert_eq!(store.current().state_hash().expect("r"), h1);
1780        assert!(!store.redo());
1781        assert!(store.undo());
1782        assert!(!store.undo());
1783    }
1784
1785    #[test]
1786    fn report_quantifies_sharing() {
1787        let mut store = PaneVersionStore::new(build_demo());
1788        for n in 1..=8u32 {
1789            store
1790                .apply(&PaneOperation::SetSplitRatio {
1791                    split: PaneId::new(4).unwrap(),
1792                    ratio: ratio(n, 1),
1793                })
1794                .expect("set ratio");
1795        }
1796        let report = store.report();
1797        assert_eq!(report.version_count, 9);
1798        assert!(
1799            report.shared_nodes > 0,
1800            "consecutive versions must share nodes"
1801        );
1802        assert!(report.distinct_nodes < report.total_logical_nodes);
1803        assert!(report.sharing_ratio > 0.0 && report.sharing_ratio < 1.0);
1804    }
1805
1806    fn ratio_storm_store() -> PaneVersionStore {
1807        let mut store = PaneVersionStore::new(build_demo());
1808        for n in 1..=8u32 {
1809            store
1810                .apply(&PaneOperation::SetSplitRatio {
1811                    split: PaneId::new(4).unwrap(),
1812                    ratio: ratio(n, 1),
1813                })
1814                .expect("set ratio");
1815        }
1816        store
1817    }
1818
1819    #[test]
1820    fn retained_bytes_matches_full_report_and_shared_resize_byte_model() {
1821        let mut store = PaneVersionStore::new(build_demo());
1822        let node_bytes = std::mem::size_of::<PersistentNode>() + ARC_HEADER_BYTES;
1823        let version_bytes = std::mem::size_of::<VersionedPaneTree>();
1824        for resize_count in 0..=8usize {
1825            let report = store.retention();
1826            // Each resize copies the root and nested split, retaining the
1827            // three original leaves and their surface-key payloads.
1828            let distinct_nodes = 5 + 2 * resize_count;
1829            let versions = resize_count + 1;
1830            let expected_bytes = std::mem::size_of::<PaneVersionStore>()
1831                + distinct_nodes * node_bytes
1832                + "root".len()
1833                + "b".len()
1834                + "c".len()
1835                + versions * version_bytes;
1836            assert_eq!(report.distinct_node_count, distinct_nodes);
1837            assert_eq!(report.total_logical_node_count, 5 * versions);
1838            assert_eq!(report.estimated_total_retained_bytes, expected_bytes);
1839            assert_eq!(store.retained_bytes(), expected_bytes);
1840            if resize_count < 8 {
1841                store
1842                    .apply(&PaneOperation::SetSplitRatio {
1843                        split: PaneId::new(4).unwrap(),
1844                        ratio: ratio(u32::try_from(resize_count + 1).unwrap(), 1),
1845                    })
1846                    .expect("shared resize");
1847            }
1848        }
1849    }
1850
1851    #[test]
1852    fn retained_bytes_matches_full_report_after_live_structural_preparation() {
1853        let mut store = PaneVersionStore::new(build_demo());
1854        let mut live = store.current().to_pane_tree().expect("live baseline");
1855        let operations = [
1856            PaneOperation::SplitLeaf {
1857                target: PaneId::new(3).unwrap(),
1858                axis: SplitAxis::Vertical,
1859                ratio: ratio(3, 2),
1860                new_leaf: PaneLeaf::new("measure 🦀"),
1861                placement: PanePlacement::ExistingFirst,
1862            },
1863            PaneOperation::MoveSubtree {
1864                source: PaneId::MIN,
1865                target: PaneId::new(7).unwrap(),
1866                axis: SplitAxis::Horizontal,
1867                ratio: ratio(2, 3),
1868                placement: PanePlacement::ExistingFirst,
1869            },
1870            PaneOperation::SwapNodes {
1871                first: PaneId::MIN,
1872                second: PaneId::new(5).unwrap(),
1873            },
1874            PaneOperation::CloseNode {
1875                target: PaneId::new(7).unwrap(),
1876            },
1877            PaneOperation::NormalizeRatios,
1878        ];
1879        for (index, operation) in operations.iter().enumerate() {
1880            let (version, projection, _) = store
1881                .prepare_live_apply(&live, u64::try_from(index + 1).unwrap(), operation)
1882                .expect("actual structural preparation");
1883            store.commit_prepared(version, false);
1884            live = projection;
1885            let report = store.retention();
1886            assert_eq!(
1887                store.retained_bytes(),
1888                report.estimated_total_retained_bytes
1889            );
1890            assert_eq!(report.version_count, index + 2);
1891            assert_eq!(report.distinct_node_count, report.total_logical_node_count);
1892            assert_eq!(report.sharing_ratio, 0.0);
1893            assert_eq!(store.current().to_snapshot(), live.to_snapshot());
1894        }
1895    }
1896
1897    #[test]
1898    fn retained_bytes_preserves_extension_costs_through_pruning_and_branching() {
1899        let base = build_demo();
1900        let mut snapshot = base.to_snapshot();
1901        let tree_payload = "workspace".len() + "Layout Lab 🦀".len();
1902        let node_payload = "record".len() + "node".len();
1903        let leaf_payload = "leaf".len() + "café".len();
1904        snapshot
1905            .extensions
1906            .insert("workspace".into(), "Layout Lab 🦀".into());
1907        for node in &mut snapshot.nodes {
1908            node.extensions.insert("record".into(), "node".into());
1909            if let PaneNodeKind::Leaf(leaf) = &mut node.kind {
1910                leaf.extensions.insert("leaf".into(), "café".into());
1911            }
1912        }
1913        let extended = PaneTree::from_snapshot(snapshot).expect("valid extension-rich tree");
1914        let mut plain = PaneVersionStore::new(base);
1915        let mut extended = PaneVersionStore::new(VersionedPaneTree::from_pane_tree(&extended));
1916        let check = |plain: &PaneVersionStore, extended: &PaneVersionStore| {
1917            let before = plain.retention();
1918            let after = extended.retention();
1919            assert_eq!(
1920                plain.retained_bytes(),
1921                before.estimated_total_retained_bytes
1922            );
1923            assert_eq!(
1924                extended.retained_bytes(),
1925                after.estimated_total_retained_bytes
1926            );
1927            assert_eq!(before.distinct_node_count, after.distinct_node_count);
1928            assert_eq!(
1929                extended.retained_bytes() - plain.retained_bytes(),
1930                after.distinct_node_count * node_payload
1931                    + 3 * leaf_payload
1932                    + after.version_count * tree_payload
1933            );
1934        };
1935        check(&plain, &extended);
1936        for numerator in 1..=8 {
1937            let operation = PaneOperation::SetSplitRatio {
1938                split: PaneId::new(4).unwrap(),
1939                ratio: ratio(numerator, 1),
1940            };
1941            plain.apply(&operation).expect("plain resize");
1942            extended.apply(&operation).expect("extended resize");
1943            check(&plain, &extended);
1944        }
1945        let bytes_before_pruning = extended.retained_bytes();
1946        let live_before_pruning = extended.current().to_snapshot();
1947        for _ in 0..2 {
1948            assert!(plain.undo());
1949            assert!(extended.undo());
1950            check(&plain, &extended);
1951        }
1952        let selected = extended.current().to_snapshot();
1953        assert_eq!(plain.set_max_versions(3), 6);
1954        assert_eq!(extended.set_max_versions(3), 6);
1955        assert_eq!(extended.cursor(), 0);
1956        assert!(extended.can_redo());
1957        assert_eq!(extended.current().to_snapshot(), selected);
1958        assert!(extended.retained_bytes() < bytes_before_pruning);
1959        check(&plain, &extended);
1960        assert!(plain.redo());
1961        assert!(extended.redo());
1962        assert!(plain.redo());
1963        assert!(extended.redo());
1964        assert_eq!(extended.current().to_snapshot(), live_before_pruning);
1965        check(&plain, &extended);
1966        assert!(plain.undo());
1967        assert!(extended.undo());
1968        let branch = PaneOperation::SetSplitRatio {
1969            split: PaneId::new(4).unwrap(),
1970            ratio: ratio(11, 2),
1971        };
1972        plain.apply(&branch).expect("plain branch");
1973        extended.apply(&branch).expect("extended branch");
1974        assert!(!extended.can_redo());
1975        assert_ne!(extended.current().to_snapshot(), live_before_pruning);
1976        check(&plain, &extended);
1977    }
1978
1979    #[test]
1980    fn retention_model_is_deterministic() {
1981        // Two independently constructed stores over the identical workload must
1982        // yield byte-identical retention models (acceptance criterion: telemetry
1983        // is deterministic enough to compare strategies meaningfully).
1984        assert_eq!(
1985            ratio_storm_store().retention(),
1986            ratio_storm_store().retention()
1987        );
1988    }
1989
1990    #[test]
1991    fn retention_total_is_faithful_sum_of_classes() {
1992        let store = ratio_storm_store();
1993        let r = store.retention();
1994        let class_sum = std::mem::size_of::<PaneVersionStore>()
1995            + r.distinct_struct_bytes
1996            + r.distinct_leaf_payload_bytes
1997            + r.distinct_extension_payload_bytes
1998            + r.version_metadata_bytes
1999            + r.version_extension_payload_bytes;
2000        assert_eq!(r.estimated_total_retained_bytes, class_sum);
2001        assert_eq!(r.version_count, 9);
2002        assert!(r.distinct_node_count < r.total_logical_node_count);
2003    }
2004
2005    fn tree_extension_stores() -> (PaneVersionStore, PaneVersionStore, usize) {
2006        let plain = build_demo();
2007        let mut snapshot = plain.to_snapshot();
2008        let key = "workspace";
2009        let value = "Layout Lab 🦀";
2010        snapshot.extensions.insert(key.into(), value.into());
2011        let canonical = PaneTree::from_snapshot(snapshot).expect("valid extended tree");
2012        let extended = VersionedPaneTree::from_pane_tree(&canonical);
2013        (
2014            PaneVersionStore::new(plain),
2015            PaneVersionStore::new(extended),
2016            key.len() + value.len(),
2017        )
2018    }
2019
2020    #[test]
2021    fn retention_counts_tree_extensions_even_when_all_nodes_are_shared() {
2022        let (mut plain, mut extended, payload_bytes) = tree_extension_stores();
2023        let noop = PaneOperation::SwapNodes {
2024            first: PaneId::MIN,
2025            second: PaneId::MIN,
2026        };
2027        for version_count in 1..=4 {
2028            let before = plain.retention();
2029            let after = extended.retention();
2030            assert_eq!(after.version_count, version_count);
2031            assert_eq!(after.distinct_node_count, extended.current().node_count());
2032            assert_eq!(after.distinct_struct_bytes, before.distinct_struct_bytes);
2033            assert_eq!(
2034                after.distinct_extension_payload_bytes,
2035                before.distinct_extension_payload_bytes
2036            );
2037            assert_eq!(
2038                after.estimated_total_retained_bytes - before.estimated_total_retained_bytes,
2039                version_count * payload_bytes,
2040                "each version owns its tree extension map even when its root is shared"
2041            );
2042            if version_count < 4 {
2043                plain.apply(&noop).expect("plain no-op");
2044                let previous = Arc::clone(extended.current().root());
2045                extended.apply(&noop).expect("extended no-op");
2046                assert!(Arc::ptr_eq(&previous, extended.current().root()));
2047            }
2048        }
2049    }
2050
2051    #[test]
2052    fn retention_counts_cloned_tree_extensions_and_releases_pruned_versions() {
2053        let (mut plain, mut extended, payload_bytes) = tree_extension_stores();
2054        for n in 2..=4 {
2055            let operation = PaneOperation::SetSplitRatio {
2056                split: PaneId::new(4).unwrap(),
2057                ratio: ratio(n, 1),
2058            };
2059            plain.apply(&operation).expect("plain ratio change");
2060            extended.apply(&operation).expect("extended ratio change");
2061        }
2062        let mut plain_clone = plain.clone();
2063        let mut extended_clone = extended.clone();
2064        assert_eq!(extended_clone.retention(), extended.retention());
2065        assert!(Arc::ptr_eq(
2066            extended_clone.current().root(),
2067            extended.current().root()
2068        ));
2069        assert_eq!(plain_clone.set_max_versions(2), 2);
2070        assert_eq!(extended_clone.set_max_versions(2), 2);
2071        assert_eq!(extended_clone.version_count(), 2);
2072        assert_eq!(
2073            extended_clone.retention().estimated_total_retained_bytes
2074                - plain_clone.retention().estimated_total_retained_bytes,
2075            2 * payload_bytes
2076        );
2077        assert_eq!(extended.version_count(), 4, "cloning isolates retention");
2078        assert_eq!(
2079            extended.retention().estimated_total_retained_bytes
2080                - plain.retention().estimated_total_retained_bytes,
2081            4 * payload_bytes
2082        );
2083        assert_eq!(
2084            extended_clone.current().to_snapshot(),
2085            extended.current().to_snapshot(),
2086            "pruning preserves the selected tree, including its extensions"
2087        );
2088    }
2089
2090    #[test]
2091    fn retention_counts_tree_extensions_in_pinned_redo_until_branch_replacement() {
2092        let (mut plain, mut extended, payload_bytes) = tree_extension_stores();
2093        let noop = PaneOperation::SwapNodes {
2094            first: PaneId::MIN,
2095            second: PaneId::MIN,
2096        };
2097        for _ in 0..3 {
2098            plain.apply(&noop).expect("plain no-op");
2099            extended.apply(&noop).expect("extended no-op");
2100        }
2101        for _ in 0..2 {
2102            assert!(plain.undo());
2103            assert!(extended.undo());
2104        }
2105        assert_eq!(plain.set_max_versions(1), 1);
2106        assert_eq!(extended.set_max_versions(1), 1);
2107        assert_eq!(extended.version_count(), 3);
2108        assert!(extended.can_redo());
2109        assert_eq!(
2110            extended.retention().estimated_total_retained_bytes
2111                - plain.retention().estimated_total_retained_bytes,
2112            3 * payload_bytes,
2113            "current and redo versions still retain their independent maps"
2114        );
2115        let branch = PaneOperation::SetSplitRatio {
2116            split: PaneId::new(4).unwrap(),
2117            ratio: ratio(5, 1),
2118        };
2119        plain.apply(&branch).expect("plain branch replacement");
2120        extended
2121            .apply(&branch)
2122            .expect("extended branch replacement");
2123        assert_eq!(extended.version_count(), 1);
2124        assert!(!extended.can_redo());
2125        assert_eq!(
2126            extended.retention().estimated_total_retained_bytes
2127                - plain.retention().estimated_total_retained_bytes,
2128            payload_bytes
2129        );
2130    }
2131
2132    #[test]
2133    fn retention_node_bytes_scale_with_distinct_not_logical_nodes() {
2134        // The economic claim of structural sharing: node struct bytes are paid
2135        // per physically distinct node, far below the naive snapshot-per-version
2136        // cost of `total_logical_node_count` nodes.
2137        let store = ratio_storm_store();
2138        let r = store.retention();
2139        let per_node = std::mem::size_of::<PersistentNode>() + ARC_HEADER_BYTES;
2140        assert_eq!(r.distinct_struct_bytes, r.distinct_node_count * per_node);
2141        let naive_struct_bytes = r.total_logical_node_count * per_node;
2142        assert!(
2143            r.distinct_struct_bytes < naive_struct_bytes,
2144            "sharing must cost fewer node-struct bytes than naive per-version snapshots"
2145        );
2146        assert!(r.sharing_ratio > 0.0 && r.sharing_ratio < 1.0);
2147    }
2148
2149    #[test]
2150    fn rebuild_fallback_normalize_ratios_matches_baseline() {
2151        let base = build_demo();
2152        let op = PaneOperation::NormalizeRatios;
2153        let next = base.apply_operation(&op).expect("normalize");
2154        let mut canonical = base.to_pane_tree().expect("flatten");
2155        canonical
2156            .apply_operation_conservative(11, op)
2157            .expect("normalize baseline");
2158        assert_eq!(next.state_hash().expect("hash"), canonical.state_hash());
2159        assert_eq!(
2160            VersionedPaneTree::operation_strategy(PaneOperationKind::NormalizeRatios),
2161            PersistentApplyStrategy::Rebuild
2162        );
2163    }
2164}