Skip to main content

kernel/graph/
history.rs

1// Copyright 2026 Mark Alan Boykin
2// This Source Code Form is subject to the terms of the Mozilla Public
3// License, v. 2.0. If a copy of the MPL was not distributed with this
4// file, You can obtain one at https://mozilla.org/MPL/2.0/.
5// SPDX-License-Identifier: MPL-2.0
6
7//! Navigation history: the browse trail, in one **shared** visit space for the
8//! whole graph.
9//!
10//! Every node is an `Owner` within a single `chartulary::stemma::Stemma`, keyed by
11//! the node's UUID. A node's own browse history is its owner's path (within-node
12//! back/forward); a node minted by an "open in new node" gesture is **spawned**
13//! with its creator set to the origin node, so its first visit attaches under the
14//! origin's *current* visit: the navigated-from anchor is correct-by-construction
15//! and within-node + cross-node lineage live in one tree (the (b) anchor design,
16//! 2026-06-06; see the node-navigation-lineage plan).
17//!
18//! The trail is not the address. A node's primary address is its own: the url
19//! index finds the node by it, and `SetNodeUrl` changes it with no visit. A visit
20//! (`navigate_node`) records the page here and writes it as the address. A history
21//! step moves the cursor and lands the page it reveals on the address, the one
22//! place history writes the address, so a step re-imposes the trail's page over an
23//! address a `SetNodeUrl` has since moved. The cursor is the position in the trail
24//! (`node_history_projection`); nothing reads it back as the address.
25//!
26//! Stemma holds the trail: the cursor, each visit's transition and its time. It
27//! does not hold recency. When a node was last visited is the `visit.history`
28//! facet's `last_visited_ms`, stamped by navigation, the history steps, creation
29//! and the canvas touch; a read of it costs one facet lookup, where a read of
30//! this memory rebuilds the whole space.
31//!
32//! The store keeps the serializable [`GraphMemorySnapshot`] and rehydrates the
33//! live `GraphMemory` (a non-serializable `SlotMap`) per operation, the same
34//! pattern the per-node predecessor used, now over one shared space. (A live
35//! in-memory copy with custom (de)serialization is the future optimization if the
36//! per-op rehydrate cost matters.)
37//!
38//! Extracted from `graph/mod.rs` per the 2026-05-11 kernel-mod decomposition pass.
39
40use chartulary::stemma::{
41    EntryPrivacy as MemoryEntryPrivacy, Stemma as OwnerScopedMemory,
42    StemmaSnapshot as GraphMemorySnapshot, TransitionKind as MemoryTransitionKind,
43};
44use rkyv::{Archive, Deserialize, Serialize};
45use uuid::Uuid;
46
47/// Owner identity in the shared visit space: one owner per graph node, keyed by
48/// the node's UUID (string form — rkyv/serde-clean without a uuid feature). The
49/// enum (rather than a bare `String`) keeps the identity namespaced and leaves
50/// room for non-node owners later.
51#[derive(
52    Debug,
53    Clone,
54    PartialEq,
55    Eq,
56    Hash,
57    Archive,
58    Serialize,
59    Deserialize,
60    serde::Serialize,
61    serde::Deserialize,
62)]
63#[rkyv(derive(Debug, PartialEq, Eq))]
64pub enum NodeHistoryOwner {
65    Node(String),
66}
67
68impl NodeHistoryOwner {
69    fn of(node: Uuid) -> Self {
70        NodeHistoryOwner::Node(node.to_string())
71    }
72}
73
74#[derive(Debug, Clone, PartialEq, Eq)]
75pub struct NodeHistoryProjection {
76    pub entries: Vec<String>,
77    pub current_index: usize,
78}
79
80#[derive(Debug, Clone, PartialEq, Eq)]
81pub struct NodeHistoryBranchAlternative {
82    pub url: String,
83    pub transition: Option<MemoryTransitionKind>,
84    pub at_ms: u64,
85}
86
87#[derive(Debug, Clone, PartialEq, Eq)]
88pub struct NodeHistoryBranchVisit {
89    pub url: String,
90    pub transition: Option<MemoryTransitionKind>,
91    pub at_ms: u64,
92    pub is_current: bool,
93    pub alternate_children: Vec<NodeHistoryBranchAlternative>,
94}
95
96#[derive(Debug, Clone, PartialEq, Eq, Default)]
97pub struct NodeHistoryBranchProjection {
98    pub visits: Vec<NodeHistoryBranchVisit>,
99    pub current_index: Option<usize>,
100}
101
102#[derive(Debug, Clone, PartialEq, Eq, Default)]
103pub struct NodeHistorySemanticSummary {
104    pub current_url: Option<String>,
105    pub last_visit_at_ms: Option<u64>,
106    pub visit_count: usize,
107}
108
109type Memory = OwnerScopedMemory<String, String, NodeHistoryOwner, ()>;
110type Snapshot = GraphMemorySnapshot<String, String, NodeHistoryOwner, ()>;
111
112/// The graph's whole navigation history: one shared visit space, one owner per
113/// node. Methods key by node [`Uuid`]; an absent owner reads as empty history and
114/// is created lazily on the node's first [`record_visit`](Self::record_visit) (or
115/// eagerly via [`spawn`](Self::spawn) for an anchored branch).
116#[derive(
117    Debug,
118    Clone,
119    PartialEq,
120    Eq,
121    Archive,
122    Serialize,
123    Deserialize,
124    serde::Serialize,
125    serde::Deserialize,
126)]
127pub struct SharedNavigationMemory {
128    snapshot: Snapshot,
129}
130
131impl Default for SharedNavigationMemory {
132    fn default() -> Self {
133        Self::empty()
134    }
135}
136
137impl SharedNavigationMemory {
138    pub fn empty() -> Self {
139        Self {
140            snapshot: GraphMemorySnapshot {
141                entries: Vec::new(),
142                visits: Vec::new(),
143                owners: Vec::new(),
144            },
145        }
146    }
147
148    /// Wrap an existing snapshot (snapshot restore).
149    pub fn from_snapshot(snapshot: Snapshot) -> Self {
150        Self { snapshot }
151    }
152
153    /// The serializable snapshot, for persistence.
154    pub fn snapshot(&self) -> &Snapshot {
155        &self.snapshot
156    }
157
158    pub fn owner_count(&self) -> usize {
159        self.snapshot.owners.len()
160    }
161
162    pub fn entry_count(&self) -> usize {
163        self.snapshot.entries.len()
164    }
165
166    pub fn visit_count(&self) -> usize {
167        self.snapshot.visits.len()
168    }
169
170    fn hydrate(&self) -> Memory {
171        Memory::from_snapshot(self.snapshot.clone())
172    }
173
174    /// Ensure `node` has an owner (no creator — a root history). Lazy: also done
175    /// by [`record_visit`]; explicit calls are harmless (idempotent).
176    pub fn ensure(&mut self, node: Uuid) {
177        let mut memory = self.hydrate();
178        memory.ensure_owner(NodeHistoryOwner::of(node), None);
179        self.snapshot = memory.to_snapshot();
180    }
181
182    /// Spawn `child`'s owner anchored under `parent`'s **current visit** (the
183    /// navigated-from point), via node-lineage's creator machinery. Call **before**
184    /// the child's first [`record_visit`] so that first visit attaches under the
185    /// parent's current visit in the shared tree. A no-op-ish fallback to a root
186    /// owner if `parent` has no owner yet.
187    pub fn spawn(&mut self, child: Uuid, parent: Uuid) {
188        let mut memory = self.hydrate();
189        let creator = memory.owner_id_by_identity(&NodeHistoryOwner::of(parent));
190        memory.ensure_owner(NodeHistoryOwner::of(child), creator);
191        self.snapshot = memory.to_snapshot();
192    }
193
194    /// Record navigating `node` to `url` as a new current visit. Forward-fork:
195    /// navigating after [`back`](Self::back) branches off the current visit and
196    /// preserves the prior forward path. Entries dedup by URL; each navigation is
197    /// a distinct visit. Creates the owner (root) if absent.
198    pub fn record_visit(
199        &mut self,
200        node: Uuid,
201        url: &str,
202        transition: MemoryTransitionKind,
203        at_ms: u64,
204    ) {
205        let mut memory = self.hydrate();
206        let owner = memory.ensure_owner(NodeHistoryOwner::of(node), None);
207        let entry = memory.resolve_or_create_entry(
208            url.to_string(),
209            url.to_string(),
210            at_ms,
211            MemoryEntryPrivacy::LocalOnly,
212        );
213        let _ = memory.visit_entry(owner, entry, (), transition, at_ms);
214        self.snapshot = memory.to_snapshot();
215    }
216
217    /// Move `node`'s cursor back one visit. Returns the revealed URL, or `None` at
218    /// the root (cursor did not move).
219    pub fn back(&mut self, node: Uuid, at_ms: u64) -> Option<String> {
220        self.step(node, true, at_ms)
221    }
222
223    /// Move `node`'s cursor forward one visit. Returns the revealed URL, or `None`
224    /// at the tip.
225    pub fn forward(&mut self, node: Uuid, at_ms: u64) -> Option<String> {
226        self.step(node, false, at_ms)
227    }
228
229    fn step(&mut self, node: Uuid, backward: bool, at_ms: u64) -> Option<String> {
230        let mut memory = self.hydrate();
231        let owner = memory.owner_id_by_identity(&NodeHistoryOwner::of(node))?;
232        let moved = if backward {
233            memory.back(owner, 1, at_ms)
234        } else {
235            memory.forward(owner, 1, at_ms)
236        }
237        .ok()
238        .flatten()?;
239        let url = memory
240            .visit(moved)
241            .and_then(|visit| memory.entry(visit.entry))
242            .map(|entry| entry.payload.clone());
243        self.snapshot = memory.to_snapshot();
244        url
245    }
246
247    /// `node`'s linear-history projection (active path + cursor).
248    pub fn projection(&self, node: Uuid) -> NodeHistoryProjection {
249        let memory = self.hydrate();
250        let Some(owner) = memory.owner_id_by_identity(&NodeHistoryOwner::of(node)) else {
251            return NodeHistoryProjection {
252                entries: Vec::new(),
253                current_index: 0,
254            };
255        };
256        let entries = memory
257            .linear_history_entries_of_owner(owner)
258            .unwrap_or_default()
259            .into_iter()
260            .filter_map(|entry_id| memory.entry(entry_id).map(|entry| entry.payload.clone()))
261            .collect::<Vec<_>>();
262        let current_index = memory
263            .current_index_of_owner(owner)
264            .ok()
265            .flatten()
266            .unwrap_or(0);
267        NodeHistoryProjection {
268            entries,
269            current_index,
270        }
271    }
272
273    /// `node`'s branching-history projection (visit tree with alternates).
274    pub fn branch_projection(&self, node: Uuid) -> NodeHistoryBranchProjection {
275        let memory = self.hydrate();
276        let Some(owner) = memory.owner_id_by_identity(&NodeHistoryOwner::of(node)) else {
277            return NodeHistoryBranchProjection::default();
278        };
279        let Ok(branch) = memory.owner_branch_projection(owner) else {
280            return NodeHistoryBranchProjection::default();
281        };
282        NodeHistoryBranchProjection {
283            visits: branch
284                .visits
285                .into_iter()
286                .map(|visit| NodeHistoryBranchVisit {
287                    url: visit.payload,
288                    transition: visit.transition,
289                    at_ms: visit.at_ms,
290                    is_current: visit.is_current,
291                    alternate_children: visit
292                        .alternate_children
293                        .into_iter()
294                        .map(|child| NodeHistoryBranchAlternative {
295                            url: child.payload,
296                            transition: child.transition,
297                            at_ms: child.at_ms,
298                        })
299                        .collect(),
300                })
301                .collect(),
302            current_index: branch.current_index,
303        }
304    }
305
306    /// A coarse semantic summary of `node`'s history, for intelligence layers.
307    pub fn semantic_summary(&self, node: Uuid) -> NodeHistorySemanticSummary {
308        let memory = self.hydrate();
309        let Some(owner) = memory.owner_id_by_identity(&NodeHistoryOwner::of(node)) else {
310            return NodeHistorySemanticSummary::default();
311        };
312        let current_url = memory
313            .current_entry_of_owner(owner)
314            .and_then(|entry_id| memory.entry(entry_id).map(|entry| entry.payload.clone()));
315        // Last visit timestamp, scoped to this owner's visits.
316        let last_visit_at_ms = memory
317            .linear_history_visits_of_owner(owner)
318            .unwrap_or_default()
319            .into_iter()
320            .filter_map(|visit_id| memory.visit(visit_id).map(|v| v.created_at_ms))
321            .max()
322            .filter(|timestamp| *timestamp > 0);
323        let visit_count = memory
324            .linear_history_visits_of_owner(owner)
325            .map(|v| v.len())
326            .unwrap_or(0);
327        NodeHistorySemanticSummary {
328            current_url,
329            last_visit_at_ms,
330            visit_count,
331        }
332    }
333
334    /// Whether [`back`](Self::back) would move `node`'s cursor.
335    pub fn can_back(&self, node: Uuid) -> bool {
336        self.projection(node).current_index > 0
337    }
338
339    /// Whether [`forward`](Self::forward) would move `node`'s cursor.
340    pub fn can_forward(&self, node: Uuid) -> bool {
341        let projection = self.projection(node);
342        projection.current_index + 1 < projection.entries.len()
343    }
344
345    /// Drop `node`'s owner and its visits (on node removal).
346    pub fn remove(&mut self, node: Uuid) {
347        let mut memory = self.hydrate();
348        if let Some(owner) = memory.owner_id_by_identity(&NodeHistoryOwner::of(node)) {
349            let _ = memory.delete_owner(owner);
350            self.snapshot = memory.to_snapshot();
351        }
352    }
353
354    /// Seed `node`'s linear history from `entries` with `current_index` current
355    /// (a fresh root owner). Used by tests and any linear-history import path.
356    pub fn seed_linear(&mut self, node: Uuid, entries: Vec<String>, current_index: usize) {
357        if entries.is_empty() {
358            return;
359        }
360        let mut memory = self.hydrate();
361        let owner = memory.ensure_owner(NodeHistoryOwner::of(node), None);
362        for (idx, url) in entries.iter().enumerate() {
363            let entry = memory.resolve_or_create_entry(
364                url.clone(),
365                url.clone(),
366                idx as u64,
367                MemoryEntryPrivacy::LocalOnly,
368            );
369            let transition = if idx == 0 {
370                MemoryTransitionKind::UrlTyped
371            } else {
372                MemoryTransitionKind::Unknown
373            };
374            let _ = memory.visit_entry(owner, entry, (), transition, idx as u64);
375        }
376        let clamped = current_index.min(entries.len().saturating_sub(1));
377        let steps_back = entries.len().saturating_sub(1).saturating_sub(clamped);
378        if steps_back > 0 {
379            let _ = memory.back(owner, steps_back, entries.len() as u64);
380        }
381        self.snapshot = memory.to_snapshot();
382    }
383}
384
385#[cfg(test)]
386mod tests {
387    use super::*;
388
389    fn n(x: u128) -> Uuid {
390        Uuid::from_u128(x)
391    }
392
393    /// The page the cursor rests on.
394    fn cursor(m: &SharedNavigationMemory, node: Uuid) -> Option<String> {
395        let trail = m.projection(node);
396        trail.entries.get(trail.current_index).cloned()
397    }
398
399    #[test]
400    fn record_visit_back_forward_and_forward_fork() {
401        let node = n(1);
402        let mut m = SharedNavigationMemory::empty();
403        m.record_visit(node, "a", MemoryTransitionKind::UrlTyped, 1);
404        m.record_visit(node, "b", MemoryTransitionKind::LinkClick, 2);
405        m.record_visit(node, "c", MemoryTransitionKind::LinkClick, 3);
406        assert_eq!(cursor(&m, node).as_deref(), Some("c"));
407        assert!(m.can_back(node));
408        assert!(!m.can_forward(node));
409
410        assert_eq!(m.back(node, 4).as_deref(), Some("b"));
411        assert_eq!(m.back(node, 5).as_deref(), Some("a"));
412        assert_eq!(m.back(node, 6), None, "at the root, back does not move");
413        assert!(!m.can_back(node));
414        assert!(m.can_forward(node));
415        assert_eq!(m.forward(node, 7).as_deref(), Some("b"));
416
417        // Forward-fork: from b, navigate to d. c is preserved as an alternate.
418        m.record_visit(node, "d", MemoryTransitionKind::UrlTyped, 8);
419        assert_eq!(cursor(&m, node).as_deref(), Some("d"));
420        let branch = m.branch_projection(node);
421        let b_visit = branch
422            .visits
423            .iter()
424            .find(|v| v.url == "b")
425            .expect("b on the active path");
426        assert!(
427            b_visit.alternate_children.iter().any(|alt| alt.url == "c"),
428            "c is preserved as an alternate branch off b after the forward-fork",
429        );
430    }
431
432    #[test]
433    fn nodes_have_independent_histories_in_one_space() {
434        let (a, b) = (n(1), n(2));
435        let mut m = SharedNavigationMemory::empty();
436        m.record_visit(a, "a1", MemoryTransitionKind::UrlTyped, 1);
437        m.record_visit(a, "a2", MemoryTransitionKind::LinkClick, 2);
438        m.record_visit(b, "b1", MemoryTransitionKind::UrlTyped, 3);
439        assert_eq!(cursor(&m, a).as_deref(), Some("a2"));
440        assert_eq!(cursor(&m, b).as_deref(), Some("b1"));
441        assert!(
442            m.can_back(a) && !m.can_back(b),
443            "each node walks only its own path"
444        );
445    }
446
447    #[test]
448    fn spawned_child_anchors_under_the_parents_current_visit() {
449        let (parent, child) = (n(1), n(2));
450        let mut m = SharedNavigationMemory::empty();
451        m.record_visit(parent, "p1", MemoryTransitionKind::UrlTyped, 1);
452        m.record_visit(parent, "p2", MemoryTransitionKind::LinkClick, 2); // parent current = p2
453        // Branch: spawn child anchored at the parent, then its first visit.
454        m.spawn(child, parent);
455        m.record_visit(child, "c1", MemoryTransitionKind::UrlTyped, 3);
456        assert_eq!(cursor(&m, child).as_deref(), Some("c1"));
457        // The child is its own history; the parent is unchanged (still at p2).
458        assert_eq!(cursor(&m, parent).as_deref(), Some("p2"));
459        assert!(!m.can_back(child), "the child's first visit is its root");
460    }
461
462    #[test]
463    fn revisiting_a_url_is_a_distinct_visit() {
464        let node = n(1);
465        let mut m = SharedNavigationMemory::empty();
466        m.record_visit(node, "a", MemoryTransitionKind::UrlTyped, 1);
467        m.record_visit(node, "a", MemoryTransitionKind::Reload, 2);
468        assert_eq!(
469            m.projection(node).entries,
470            vec!["a".to_string(), "a".to_string()]
471        );
472    }
473
474    #[test]
475    fn seed_linear_and_remove() {
476        let node = n(1);
477        let mut m = SharedNavigationMemory::empty();
478        m.seed_linear(node, vec!["a".into(), "b".into(), "c".into()], 1);
479        assert_eq!(
480            cursor(&m, node).as_deref(),
481            Some("b"),
482            "cursor at the seeded index"
483        );
484        assert!(m.can_back(node) && m.can_forward(node));
485        m.remove(node);
486        assert_eq!(cursor(&m, node), None, "owner dropped on remove");
487    }
488}