1use 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#[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#[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 pub fn from_snapshot(snapshot: Snapshot) -> Self {
150 Self { snapshot }
151 }
152
153 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 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 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 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 pub fn back(&mut self, node: Uuid, at_ms: u64) -> Option<String> {
220 self.step(node, true, at_ms)
221 }
222
223 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 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 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 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 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 pub fn can_back(&self, node: Uuid) -> bool {
336 self.projection(node).current_index > 0
337 }
338
339 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 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 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 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 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); m.spawn(child, parent);
455 m.record_visit(child, "c1", MemoryTransitionKind::UrlTyped, 3);
456 assert_eq!(cursor(&m, child).as_deref(), Some("c1"));
457 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}