1use 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#[derive(Debug, Clone, PartialEq, Eq)]
70pub enum PersistentNode {
71 Leaf {
73 id: PaneId,
75 constraints: PaneConstraints,
77 node_extensions: BTreeMap<String, String>,
79 leaf: PaneLeaf,
81 },
82 Split {
84 id: PaneId,
86 constraints: PaneConstraints,
88 node_extensions: BTreeMap<String, String>,
90 axis: SplitAxis,
92 ratio: PaneSplitRatio,
94 first: Arc<PersistentNode>,
96 second: Arc<PersistentNode>,
98 },
99}
100
101impl PersistentNode {
102 #[must_use]
104 pub const fn id(&self) -> PaneId {
105 match self {
106 Self::Leaf { id, .. } | Self::Split { id, .. } => *id,
107 }
108 }
109
110 #[must_use]
112 pub const fn is_leaf(&self) -> bool {
113 matches!(self, Self::Leaf { .. })
114 }
115
116 #[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 #[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#[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 #[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 #[must_use]
168 pub fn from_pane_tree(tree: &PaneTree) -> Self {
169 Self::from_snapshot(&tree.to_snapshot())
170 }
171
172 #[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 #[must_use]
190 pub fn root(&self) -> &Arc<PersistentNode> {
191 &self.root
192 }
193
194 #[must_use]
196 pub fn root_id(&self) -> PaneId {
197 self.root.id()
198 }
199
200 #[must_use]
202 pub const fn next_id(&self) -> PaneId {
203 self.next_id
204 }
205
206 #[must_use]
208 pub const fn schema_version(&self) -> u16 {
209 self.schema_version
210 }
211
212 #[must_use]
214 pub fn node_count(&self) -> usize {
215 self.root.node_count()
216 }
217
218 #[must_use]
220 pub fn depth(&self) -> usize {
221 self.root.depth()
222 }
223
224 #[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 pub fn to_pane_tree(&self) -> Result<PaneTree, PaneModelError> {
251 PaneTree::from_snapshot(self.to_snapshot())
252 }
253
254 pub fn state_hash(&self) -> Result<u64, PaneModelError> {
261 Ok(self.to_pane_tree()?.state_hash())
262 }
263
264 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 #[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 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
406pub enum PersistentApplyStrategy {
407 PathCopy,
409 Rebuild,
411}
412
413#[derive(Debug, Clone, PartialEq, Eq)]
419pub enum PersistentApplyError {
420 MissingNode {
422 node_id: PaneId,
424 },
425 NotSplit {
427 node_id: PaneId,
429 },
430 NotLeaf {
432 node_id: PaneId,
434 },
435 CannotCloseRoot {
437 node_id: PaneId,
439 },
440 AncestorConflict {
442 ancestor: PaneId,
444 descendant: PaneId,
446 },
447 IdOverflow {
449 current: PaneId,
451 },
452 InvalidTree(PaneModelError),
454 Rebuild(String),
456}
457
458#[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 #[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 #[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 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 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 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 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(¤t.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 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 pub(crate) fn version_at(&self, index: usize) -> Option<&VersionedPaneTree> {
601 self.versions.get(index)
602 }
603
604 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 pub fn undo(&mut self) -> bool {
615 if self.cursor == 0 {
616 return false;
617 }
618 self.cursor -= 1;
619 true
620 }
621
622 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 #[must_use]
633 pub fn current(&self) -> &VersionedPaneTree {
634 &self.versions[self.cursor]
635 }
636
637 #[must_use]
639 pub fn version_count(&self) -> usize {
640 self.versions.len()
641 }
642
643 #[must_use]
645 pub const fn cursor(&self) -> usize {
646 self.cursor
647 }
648
649 #[must_use]
651 pub const fn can_undo(&self) -> bool {
652 self.cursor > 0
653 }
654
655 #[must_use]
657 pub fn can_redo(&self) -> bool {
658 self.cursor + 1 < self.versions.len()
659 }
660
661 #[must_use]
663 pub const fn pruned(&self) -> usize {
664 self.pruned
665 }
666
667 #[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 #[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 #[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 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 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
830struct 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#[derive(Debug, Clone, PartialEq, serde::Serialize)]
843pub struct PaneVersioningReport {
844 pub version_count: usize,
846 pub cursor: usize,
848 pub distinct_nodes: usize,
850 pub total_logical_nodes: usize,
852 pub shared_nodes: usize,
854 pub sharing_ratio: f64,
856 pub current_node_count: usize,
858 pub current_depth: usize,
860 pub pruned_versions: usize,
862}
863
864#[derive(Debug, Clone, Copy, PartialEq, serde::Serialize)]
874pub struct PaneVersionRetention {
875 pub version_count: usize,
877 pub distinct_node_count: usize,
879 pub total_logical_node_count: usize,
881 pub sharing_ratio: f64,
883 pub distinct_struct_bytes: usize,
885 pub distinct_leaf_payload_bytes: usize,
887 pub distinct_extension_payload_bytes: usize,
889 pub version_metadata_bytes: usize,
891 pub version_extension_payload_bytes: usize,
894 pub estimated_total_retained_bytes: usize,
896}
897
898fn 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 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 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 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
1049fn 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
1070fn 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
1086fn 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
1099fn 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
1201const ARC_HEADER_BYTES: usize = 2 * std::mem::size_of::<usize>();
1206
1207pub(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
1218fn 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 fn build_demo() -> VersionedPaneTree {
1253 let v0 = VersionedPaneTree::singleton("root");
1254 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 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 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 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 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 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 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 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}