Skip to main content

kernel/graph/
history.rs

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