1use 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#[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#[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#[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 pub fn from_snapshot(snapshot: Snapshot) -> Self {
141 Self { snapshot }
142 }
143
144 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 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 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 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 pub fn back(&mut self, node: Uuid, at_ms: u64) -> Option<String> {
211 self.step(node, true, at_ms)
212 }
213
214 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 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 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 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 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 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 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 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 pub fn can_back(&self, node: Uuid) -> bool {
369 self.projection(node).current_index > 0
370 }
371
372 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 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 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 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); 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 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); 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 let top = m.recent_visited(1);
535 assert_eq!(top.len(), 1);
536 assert_eq!(top[0].node, a);
537
538 assert!(SharedNavigationMemory::empty().recent_visited(5).is_empty());
540 }
541}