Skip to main content

ftui_layout/
pane_memory.rs

1//! Cross-strategy pane-memory telemetry (`bd-25wj7.1`).
2//!
3//! Pane history can be retained three ways, each buying undo/redo at a different
4//! memory price:
5//!
6//! * **Baseline** — keep only the single live [`PaneTree`]; no undo history at
7//!   all. The irreducible floor.
8//! * **Checkpointed** — the production [`PaneInteractionTimeline`]: a baseline
9//!   snapshot, a periodic checkpoint snapshot, an operation log with per-entry
10//!   before/after state hashes, and replay to reconstruct historical states.
11//! * **Persistent** — the structurally shared [`PaneVersionStore`]: a `Vec` of
12//!   `Arc`-shared version roots where unchanged subtrees are physically reused,
13//!   so navigation is `O(1)` index moves with no replay and no hashes.
14//!
15//! This module turns those three into directly comparable [`PaneMemoryStrategyFootprint`]s
16//! and a single [`PaneMemoryComparison`] artifact. Every footprint is decomposed
17//! into the *same* retained-state classes — node structs, leaf payload,
18//! extension payload, operation log, state hashes, container/metadata — so the
19//! dominant memory driver of each strategy is explicit, not buried in one
20//! aggregate number. The byte models reuse the canonical timeline methodology
21//! (`size_of` struct estimates plus measured string payload bytes), so the
22//! comparison is deterministic and reproducible: identical inputs yield
23//! byte-identical reports, suitable for CI regression artifacts and as concrete
24//! baselines for the bounded-retention (`bd-25wj7.2`) and churn-reduction
25//! (`bd-25wj7.3`) work that depends on this bead.
26//!
27//! The retained-state model lives here in the library so it is pure and
28//! unit-testable; *transient* allocation counts (which need allocator
29//! instrumentation) are captured by the `pane_memory_telemetry` bench, which
30//! embeds this comparison into its emitted JSON manifest.
31
32use crate::pane::{
33    PaneInteractionTimeline, PaneNodeKind, PaneNodeRecord, PaneTree, PaneTreeSnapshot,
34};
35use crate::pane_persistent::{PaneVersionStore, string_map_payload_bytes};
36
37/// Schema version for the emitted memory-telemetry artifact. Bump on any
38/// breaking change to the footprint/comparison field layout.
39pub const PANE_MEMORY_TELEMETRY_SCHEMA_VERSION: u16 = 1;
40
41/// The history-retention strategy a [`PaneMemoryStrategyFootprint`] describes.
42#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize)]
43pub enum PaneMemoryStrategy {
44    /// Keep only the single live tree; no undo history.
45    Baseline,
46    /// Checkpointed operation-log timeline with replay-based navigation.
47    Checkpointed,
48    /// Structurally shared persistent version store with `O(1)` navigation.
49    Persistent,
50}
51
52impl PaneMemoryStrategy {
53    /// Stable lower-case identifier for logs and artifact keys.
54    #[must_use]
55    pub const fn as_str(self) -> &'static str {
56        match self {
57            Self::Baseline => "baseline",
58            Self::Checkpointed => "checkpointed",
59            Self::Persistent => "persistent",
60        }
61    }
62}
63
64/// The single retained-state class that dominates a strategy's footprint.
65#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize)]
66pub enum PaneMemoryDriver {
67    /// Tree node structs (records / `Arc` nodes) retained across versions.
68    NodeStructs,
69    /// Leaf surface-key payload bytes.
70    LeafPayload,
71    /// Node + leaf extension-map payload bytes.
72    ExtensionPayload,
73    /// Operation-log entry structs and operation heap payloads.
74    OperationLog,
75    /// Per-entry before/after state-hash bytes (replay verification cost).
76    StateHashes,
77    /// Container struct plus version/checkpoint metadata handles.
78    ContainerMetadata,
79}
80
81impl PaneMemoryDriver {
82    /// Human-readable phrase for the dominant driver.
83    #[must_use]
84    pub const fn as_str(self) -> &'static str {
85        match self {
86            Self::NodeStructs => "node structs",
87            Self::LeafPayload => "leaf payload",
88            Self::ExtensionPayload => "extension payload",
89            Self::OperationLog => "operation log",
90            Self::StateHashes => "state hashes",
91            Self::ContainerMetadata => "container/metadata",
92        }
93    }
94}
95
96/// Retained-memory footprint of one strategy, decomposed by retained-state class.
97///
98/// `total_retained_bytes` is authoritative; the per-class fields sum to it
99/// exactly (the last class, `container_and_metadata_bytes`, absorbs the
100/// remainder so the decomposition is always faithful).
101#[derive(Debug, Clone, Copy, PartialEq, serde::Serialize)]
102pub struct PaneMemoryStrategyFootprint {
103    /// Which strategy this footprint describes.
104    pub strategy: PaneMemoryStrategy,
105    /// Count of retained heavy units: live tree (`1`) for baseline, retained
106    /// snapshots (baseline + checkpoints) for checkpointed, versions for
107    /// persistent.
108    pub retained_unit_count: usize,
109    /// Total retained tree nodes (logical for checkpointed snapshots; physically
110    /// distinct for the persistent store).
111    pub retained_node_count: usize,
112    /// Tree node struct bytes.
113    pub node_struct_bytes: usize,
114    /// Leaf surface-key payload bytes.
115    pub leaf_payload_bytes: usize,
116    /// Node + leaf extension-map payload bytes.
117    pub extension_payload_bytes: usize,
118    /// Operation-log entry struct + operation heap payload bytes (`0` unless
119    /// checkpointed).
120    pub operation_payload_bytes: usize,
121    /// Per-entry before/after state-hash bytes (`0` unless checkpointed).
122    pub state_hash_overhead_bytes: usize,
123    /// Container struct plus version/checkpoint metadata bytes (remainder).
124    pub container_and_metadata_bytes: usize,
125    /// Authoritative total retained bytes.
126    pub total_retained_bytes: usize,
127    /// The single largest retained-state class.
128    pub dominant_driver: PaneMemoryDriver,
129}
130
131impl PaneMemoryStrategyFootprint {
132    #[allow(clippy::too_many_arguments)]
133    fn assemble(
134        strategy: PaneMemoryStrategy,
135        retained_unit_count: usize,
136        retained_node_count: usize,
137        node_struct_bytes: usize,
138        leaf_payload_bytes: usize,
139        extension_payload_bytes: usize,
140        operation_payload_bytes: usize,
141        state_hash_overhead_bytes: usize,
142        total_retained_bytes: usize,
143    ) -> Self {
144        // The container/metadata class absorbs whatever the authoritative total
145        // does not attribute to a concrete class, so the decomposition always
146        // sums to `total_retained_bytes`.
147        let attributed = node_struct_bytes
148            .saturating_add(leaf_payload_bytes)
149            .saturating_add(extension_payload_bytes)
150            .saturating_add(operation_payload_bytes)
151            .saturating_add(state_hash_overhead_bytes);
152        let container_and_metadata_bytes = total_retained_bytes.saturating_sub(attributed);
153        let dominant_driver = dominant_driver(
154            node_struct_bytes,
155            leaf_payload_bytes,
156            extension_payload_bytes,
157            operation_payload_bytes,
158            state_hash_overhead_bytes,
159            container_and_metadata_bytes,
160        );
161        Self {
162            strategy,
163            retained_unit_count,
164            retained_node_count,
165            node_struct_bytes,
166            leaf_payload_bytes,
167            extension_payload_bytes,
168            operation_payload_bytes,
169            state_hash_overhead_bytes,
170            container_and_metadata_bytes,
171            total_retained_bytes,
172            dominant_driver,
173        }
174    }
175}
176
177/// Side-by-side retained-memory comparison across the three strategies.
178#[derive(Debug, Clone, PartialEq, serde::Serialize)]
179pub struct PaneMemoryComparison {
180    /// Artifact schema version.
181    pub schema_version: u16,
182    /// No-history floor: a single live tree.
183    pub baseline: PaneMemoryStrategyFootprint,
184    /// Production checkpointed timeline.
185    pub checkpointed: PaneMemoryStrategyFootprint,
186    /// Structurally shared persistent store.
187    pub persistent: PaneMemoryStrategyFootprint,
188    /// `persistent.total / checkpointed.total` (`<1` ⇒ persistent is leaner).
189    pub persistent_over_checkpointed: f64,
190    /// `checkpointed.total / baseline.total` (the multiplicative cost of history).
191    pub checkpointed_over_baseline: f64,
192    /// Strategy retaining the fewest total bytes.
193    pub most_compact_strategy: PaneMemoryStrategy,
194    /// One-line human-readable takeaway naming each strategy's dominant driver.
195    pub summary: String,
196}
197
198/// Build a deterministic cross-strategy retained-memory comparison.
199///
200/// `live` is the current tree the caller would keep with no undo history
201/// (the baseline floor). `timeline` and `store` must have been driven through
202/// the *same* operation history as `live` for the comparison to be meaningful;
203/// the function itself is pure and simply reads each strategy's retained-state
204/// model.
205#[must_use]
206pub fn pane_memory_comparison(
207    live: &PaneTree,
208    timeline: &PaneInteractionTimeline,
209    store: &PaneVersionStore,
210) -> PaneMemoryComparison {
211    let baseline = baseline_footprint(live);
212    let checkpointed = checkpointed_footprint(timeline);
213    let persistent = persistent_footprint(store);
214
215    let persistent_over_checkpointed = ratio(
216        persistent.total_retained_bytes,
217        checkpointed.total_retained_bytes,
218    );
219    let checkpointed_over_baseline = ratio(
220        checkpointed.total_retained_bytes,
221        baseline.total_retained_bytes,
222    );
223    let most_compact_strategy = most_compact(&baseline, &checkpointed, &persistent);
224
225    let summary = format!(
226        "baseline: {} tree, {}B (driver {}); checkpointed: {} snapshots / {} entries, {}B (driver {}); \
227         persistent: {} versions, {}B (driver {}). persistent/checkpointed={:.2}x, checkpointed/baseline={:.2}x; \
228         most compact: {}.",
229        baseline.retained_unit_count,
230        baseline.total_retained_bytes,
231        baseline.dominant_driver.as_str(),
232        checkpointed.retained_unit_count,
233        timeline.entries.len(),
234        checkpointed.total_retained_bytes,
235        checkpointed.dominant_driver.as_str(),
236        persistent.retained_unit_count,
237        persistent.total_retained_bytes,
238        persistent.dominant_driver.as_str(),
239        persistent_over_checkpointed,
240        checkpointed_over_baseline,
241        most_compact_strategy.as_str(),
242    );
243
244    PaneMemoryComparison {
245        schema_version: PANE_MEMORY_TELEMETRY_SCHEMA_VERSION,
246        baseline,
247        checkpointed,
248        persistent,
249        persistent_over_checkpointed,
250        checkpointed_over_baseline,
251        most_compact_strategy,
252        summary,
253    }
254}
255
256/// Bytes of one `u64` state hash; the timeline stores a before/after pair per entry.
257const STATE_HASH_BYTES: usize = std::mem::size_of::<u64>();
258
259pub(crate) fn baseline_footprint(live: &PaneTree) -> PaneMemoryStrategyFootprint {
260    let (node_count, leaf_payload_bytes, extension_payload_bytes) = live_payload_bytes(live);
261    let node_struct_bytes = node_count.saturating_mul(std::mem::size_of::<PaneNodeRecord>());
262    let container = std::mem::size_of::<PaneTreeSnapshot>();
263    let total = node_struct_bytes
264        .saturating_add(leaf_payload_bytes)
265        .saturating_add(extension_payload_bytes)
266        .saturating_add(container);
267    PaneMemoryStrategyFootprint::assemble(
268        PaneMemoryStrategy::Baseline,
269        1,
270        node_count,
271        node_struct_bytes,
272        leaf_payload_bytes,
273        extension_payload_bytes,
274        0,
275        0,
276        total,
277    )
278}
279
280fn checkpointed_footprint(timeline: &PaneInteractionTimeline) -> PaneMemoryStrategyFootprint {
281    let diag = timeline.retention_diagnostics();
282    // The entry struct stores the two state hashes inline; surface that cost as
283    // its own class and attribute the rest of the entry struct to the op log.
284    let state_hash_overhead_bytes = diag.entry_count.saturating_mul(2 * STATE_HASH_BYTES);
285    let operation_payload_bytes = diag.retained_operation_payload_bytes.saturating_add(
286        diag.estimated_entry_struct_bytes
287            .saturating_sub(state_hash_overhead_bytes),
288    );
289    PaneMemoryStrategyFootprint::assemble(
290        PaneMemoryStrategy::Checkpointed,
291        diag.retained_snapshot_count,
292        diag.retained_snapshot_node_count,
293        diag.estimated_snapshot_struct_bytes,
294        diag.retained_leaf_payload_bytes,
295        diag.retained_extension_payload_bytes,
296        operation_payload_bytes,
297        state_hash_overhead_bytes,
298        diag.estimated_total_retained_bytes,
299    )
300}
301
302fn persistent_footprint(store: &PaneVersionStore) -> PaneMemoryStrategyFootprint {
303    let r = store.retention();
304    PaneMemoryStrategyFootprint::assemble(
305        PaneMemoryStrategy::Persistent,
306        r.version_count,
307        r.distinct_node_count,
308        r.distinct_struct_bytes,
309        r.distinct_leaf_payload_bytes,
310        r.distinct_extension_payload_bytes
311            .saturating_add(r.version_extension_payload_bytes),
312        0,
313        0,
314        r.estimated_total_retained_bytes,
315    )
316}
317
318/// Count the live projection without allocating a temporary snapshot.
319fn live_payload_bytes(live: &PaneTree) -> (usize, usize, usize) {
320    let mut node_count = 0usize;
321    let mut leaf_payload = 0usize;
322    let mut extension_payload = string_map_payload_bytes(live.extensions());
323    for record in live.nodes() {
324        node_count = node_count.saturating_add(1);
325        extension_payload =
326            extension_payload.saturating_add(string_map_payload_bytes(&record.extensions));
327        if let PaneNodeKind::Leaf(leaf) = &record.kind {
328            leaf_payload = leaf_payload.saturating_add(leaf.surface_key.len());
329            extension_payload =
330                extension_payload.saturating_add(string_map_payload_bytes(&leaf.extensions));
331        }
332    }
333    (node_count, leaf_payload, extension_payload)
334}
335
336/// Pick the dominant retained-state class. Ties resolve to the earlier class in
337/// declaration order (node structs first) for deterministic output.
338fn dominant_driver(
339    node: usize,
340    leaf: usize,
341    ext: usize,
342    op: usize,
343    hash: usize,
344    container: usize,
345) -> PaneMemoryDriver {
346    let classes = [
347        (PaneMemoryDriver::NodeStructs, node),
348        (PaneMemoryDriver::LeafPayload, leaf),
349        (PaneMemoryDriver::ExtensionPayload, ext),
350        (PaneMemoryDriver::OperationLog, op),
351        (PaneMemoryDriver::StateHashes, hash),
352        (PaneMemoryDriver::ContainerMetadata, container),
353    ];
354    let mut best = classes[0];
355    for &candidate in &classes[1..] {
356        if candidate.1 > best.1 {
357            best = candidate;
358        }
359    }
360    best.0
361}
362
363fn ratio(numerator: usize, denominator: usize) -> f64 {
364    if denominator == 0 {
365        0.0
366    } else {
367        numerator as f64 / denominator as f64
368    }
369}
370
371fn most_compact(
372    baseline: &PaneMemoryStrategyFootprint,
373    checkpointed: &PaneMemoryStrategyFootprint,
374    persistent: &PaneMemoryStrategyFootprint,
375) -> PaneMemoryStrategy {
376    let mut best = baseline;
377    if checkpointed.total_retained_bytes < best.total_retained_bytes {
378        best = checkpointed;
379    }
380    if persistent.total_retained_bytes < best.total_retained_bytes {
381        best = persistent;
382    }
383    best.strategy
384}
385
386#[cfg(test)]
387mod tests {
388    use super::*;
389    use crate::pane::{PaneId, PaneLeaf, PaneOperation, PanePlacement, PaneSplitRatio, SplitAxis};
390    use crate::pane_persistent::VersionedPaneTree;
391
392    fn ratio_of(n: u32, d: u32) -> PaneSplitRatio {
393        PaneSplitRatio::new(n, d).expect("valid ratio")
394    }
395
396    /// Drive all three strategies through an identical operation history and
397    /// return `(live_tree, timeline, store)` ready to compare.
398    fn drive_workload() -> (PaneTree, PaneInteractionTimeline, PaneVersionStore) {
399        let mut ops: Vec<PaneOperation> = vec![
400            PaneOperation::SplitLeaf {
401                target: PaneId::MIN,
402                axis: SplitAxis::Horizontal,
403                ratio: ratio_of(1, 1),
404                placement: PanePlacement::ExistingFirst,
405                new_leaf: PaneLeaf::new("b"),
406            },
407            PaneOperation::SplitLeaf {
408                target: PaneId::MIN,
409                axis: SplitAxis::Vertical,
410                ratio: ratio_of(2, 1),
411                placement: PanePlacement::ExistingFirst,
412                new_leaf: PaneLeaf::new("c"),
413            },
414        ];
415        // Resize storm on the split created by the second op (id 4).
416        let split = PaneId::new(4).expect("valid id");
417        for n in 1..=6u32 {
418            ops.push(PaneOperation::SetSplitRatio {
419                split,
420                ratio: ratio_of(n, 1),
421            });
422        }
423
424        let mut tree = PaneTree::singleton("root");
425        let mut timeline = PaneInteractionTimeline::default();
426        let mut store = PaneVersionStore::new(VersionedPaneTree::singleton("root"));
427        for (i, op) in ops.iter().enumerate() {
428            let id = i as u64;
429            timeline
430                .apply_and_record(&mut tree, id, id, op.clone())
431                .expect("timeline apply");
432            store.apply(op).expect("store apply");
433        }
434        (tree, timeline, store)
435    }
436
437    fn assert_footprint_sums(f: &PaneMemoryStrategyFootprint) {
438        let class_sum = f.node_struct_bytes
439            + f.leaf_payload_bytes
440            + f.extension_payload_bytes
441            + f.operation_payload_bytes
442            + f.state_hash_overhead_bytes
443            + f.container_and_metadata_bytes;
444        assert_eq!(
445            class_sum, f.total_retained_bytes,
446            "{:?} class decomposition must sum to the authoritative total",
447            f.strategy
448        );
449    }
450
451    #[test]
452    fn comparison_is_deterministic() {
453        let (t1, tl1, s1) = drive_workload();
454        let (t2, tl2, s2) = drive_workload();
455        assert_eq!(
456            pane_memory_comparison(&t1, &tl1, &s1),
457            pane_memory_comparison(&t2, &tl2, &s2)
458        );
459    }
460
461    #[test]
462    fn every_footprint_decomposition_is_faithful() {
463        let (tree, timeline, store) = drive_workload();
464        let cmp = pane_memory_comparison(&tree, &timeline, &store);
465        assert_footprint_sums(&cmp.baseline);
466        assert_footprint_sums(&cmp.checkpointed);
467        assert_footprint_sums(&cmp.persistent);
468        assert_eq!(cmp.schema_version, PANE_MEMORY_TELEMETRY_SCHEMA_VERSION);
469    }
470
471    #[test]
472    fn comparison_counts_tree_extension_payload_in_every_retained_copy() {
473        let key = "workspace";
474        let value = "編集🦀";
475        let payload = key.len() + value.len();
476        let compare = |include_extensions| {
477            let mut snapshot = PaneTree::singleton("root").to_snapshot();
478            if include_extensions {
479                snapshot.extensions.insert(key.to_owned(), value.to_owned());
480            }
481            let mut tree = PaneTree::from_snapshot(snapshot).expect("valid tree");
482            let mut timeline = PaneInteractionTimeline::with_baseline(&tree);
483            timeline.checkpoint_interval = 1;
484            let mut store = PaneVersionStore::new(VersionedPaneTree::from_pane_tree(&tree));
485            for id in 0..3 {
486                timeline
487                    .apply_and_record(&mut tree, id, id, PaneOperation::NormalizeRatios)
488                    .expect("record operation");
489                store
490                    .apply(&PaneOperation::NormalizeRatios)
491                    .expect("persist operation");
492            }
493            pane_memory_comparison(&tree, &timeline, &store)
494        };
495        let plain = compare(false);
496        let extended = compare(true);
497        for (before, after, copies) in [
498            (&plain.baseline, &extended.baseline, 1),
499            (&plain.checkpointed, &extended.checkpointed, 4),
500            (&plain.persistent, &extended.persistent, 4),
501        ] {
502            assert_eq!(after.extension_payload_bytes, copies * payload);
503            assert_eq!(
504                after.total_retained_bytes - before.total_retained_bytes,
505                copies * payload
506            );
507            assert_eq!(
508                after.container_and_metadata_bytes,
509                before.container_and_metadata_bytes
510            );
511            assert_footprint_sums(after);
512        }
513    }
514
515    #[test]
516    fn baseline_is_the_floor_and_history_costs_more() {
517        let (tree, timeline, store) = drive_workload();
518        let cmp = pane_memory_comparison(&tree, &timeline, &store);
519        // Retaining history (either way) never costs less than one live tree.
520        assert!(cmp.checkpointed.total_retained_bytes > cmp.baseline.total_retained_bytes);
521        assert!(cmp.persistent.total_retained_bytes > cmp.baseline.total_retained_bytes);
522        assert_eq!(cmp.most_compact_strategy, PaneMemoryStrategy::Baseline);
523        assert!(cmp.checkpointed_over_baseline > 1.0);
524    }
525
526    #[test]
527    fn only_checkpointed_pays_state_hash_and_op_log_overhead() {
528        let (tree, timeline, store) = drive_workload();
529        let cmp = pane_memory_comparison(&tree, &timeline, &store);
530        // The persistent store navigates by index: no operation log, no hashes.
531        assert_eq!(cmp.persistent.state_hash_overhead_bytes, 0);
532        assert_eq!(cmp.persistent.operation_payload_bytes, 0);
533        assert_eq!(cmp.baseline.state_hash_overhead_bytes, 0);
534        assert_eq!(cmp.baseline.operation_payload_bytes, 0);
535        // 8 ops × 2 hashes × 8 bytes.
536        assert_eq!(
537            cmp.checkpointed.state_hash_overhead_bytes,
538            timeline.entries.len() * 2 * STATE_HASH_BYTES
539        );
540        assert!(cmp.checkpointed.state_hash_overhead_bytes > 0);
541    }
542
543    #[test]
544    fn checkpointed_defers_nodes_while_persistent_materializes_versions() {
545        let (tree, timeline, store) = drive_workload();
546        let cmp = pane_memory_comparison(&tree, &timeline, &store);
547        // The two history strategies sit on opposite sides of the memory/replay
548        // trade. For a short history (below the checkpoint interval) the
549        // checkpointed path retains almost no snapshot nodes — it leans on its
550        // operation log + state hashes and reconstructs by replay — whereas the
551        // persistent store materializes every version's distinct nodes so it can
552        // navigate in O(1).
553        assert!(cmp.persistent.retained_node_count > cmp.checkpointed.retained_node_count);
554        assert!(cmp.checkpointed.operation_payload_bytes > 0);
555        assert_eq!(cmp.persistent.operation_payload_bytes, 0);
556        // The comparison ratios are populated and finite.
557        assert!(cmp.persistent_over_checkpointed > 0.0);
558        assert!(cmp.persistent_over_checkpointed.is_finite());
559    }
560
561    #[test]
562    fn dominant_driver_prefers_earlier_class_on_ties() {
563        // Equal node and leaf bytes ⇒ node structs win (earlier in order).
564        assert_eq!(
565            dominant_driver(10, 10, 0, 0, 0, 0),
566            PaneMemoryDriver::NodeStructs
567        );
568        // A strictly larger later class wins outright.
569        assert_eq!(
570            dominant_driver(1, 1, 1, 99, 1, 1),
571            PaneMemoryDriver::OperationLog
572        );
573    }
574}