1use crate::value::Value;
6use std::collections::BTreeMap;
7
8fn fnv1a_64(s: &str) -> u64 {
10 let mut h: u64 = 0xcbf29ce484222325;
11 for b in s.as_bytes() {
12 h ^= *b as u64;
13 h = h.wrapping_mul(0x100000001b3);
14 }
15 h
16}
17
18#[derive(Debug, Clone, PartialEq)]
20pub struct TimelineBranch {
21 pub branch_id: String,
23 pub name: String,
25 pub universe_usri: String,
27 pub divergence_epoch: String,
29 pub bifurcation_hash: u64,
31 pub parent_branch: Option<String>,
33}
34
35impl TimelineBranch {
36 pub fn prime(universe_usri: &str) -> Self {
38 Self {
39 branch_id: "prime".into(),
40 name: "Prime Canon Timeline".into(),
41 universe_usri: universe_usri.into(),
42 divergence_epoch: "origin".into(),
43 bifurcation_hash: 0, parent_branch: None,
45 }
46 }
47
48 pub fn divergent(
50 branch_id: &str,
51 name: &str,
52 universe_usri: &str,
53 divergence_epoch: &str,
54 parent_branch: &str,
55 ) -> Self {
56 let bifurcation_input = format!("{}:{}:{}", universe_usri, branch_id, divergence_epoch);
57 Self {
58 branch_id: branch_id.into(),
59 name: name.into(),
60 universe_usri: universe_usri.into(),
61 divergence_epoch: divergence_epoch.into(),
62 bifurcation_hash: fnv1a_64(&bifurcation_input),
63 parent_branch: Some(parent_branch.into()),
64 }
65 }
66
67 pub fn is_prime(&self) -> bool {
69 self.parent_branch.is_none()
70 }
71
72 pub fn context_hash(&self) -> u64 {
75 let input = format!(
76 "{}:{}:{}",
77 self.universe_usri, self.branch_id, self.divergence_epoch
78 );
79 fnv1a_64(&input)
80 }
81
82 pub fn to_value(&self) -> Value {
84 let mut rec = BTreeMap::new();
85 rec.insert("branch_id".into(), Value::String(self.branch_id.clone()));
86 rec.insert("name".into(), Value::String(self.name.clone()));
87 rec.insert(
88 "universe_usri".into(),
89 Value::String(self.universe_usri.clone()),
90 );
91 rec.insert(
92 "divergence_epoch".into(),
93 Value::String(self.divergence_epoch.clone()),
94 );
95 rec.insert("bifurcation_hash".into(), Value::U64(self.bifurcation_hash));
96 if let Some(ref p) = self.parent_branch {
97 rec.insert("parent_branch".into(), Value::String(p.clone()));
98 }
99 Value::Record(rec)
100 }
101}
102
103#[derive(Debug, Clone)]
105pub struct TimelineDag {
106 pub branches: Vec<TimelineBranch>,
108}
109
110impl TimelineDag {
111 pub fn new(prime: TimelineBranch) -> Self {
113 Self {
114 branches: vec![prime],
115 }
116 }
117
118 pub fn add_branch(&mut self, branch: TimelineBranch) -> bool {
121 if let Some(ref parent_id) = branch.parent_branch {
123 if !self.branches.iter().any(|b| &b.branch_id == parent_id) {
124 return false;
125 }
126 }
127 if self
129 .branches
130 .iter()
131 .any(|b| b.branch_id == branch.branch_id)
132 {
133 return false;
134 }
135 if let Some(ref parent_id) = branch.parent_branch {
137 if self.would_create_cycle(&branch.branch_id, parent_id) {
138 return false;
139 }
140 }
141 self.branches.push(branch);
142 true
143 }
144
145 fn would_create_cycle(&self, new_id: &str, parent_id: &str) -> bool {
147 let mut current = parent_id.to_string();
149 while let Some(branch) = self.branches.iter().find(|b| b.branch_id == current) {
150 if branch.branch_id == new_id {
151 return true;
152 }
153 match &branch.parent_branch {
154 Some(p) => current = p.clone(),
155 None => break,
156 }
157 }
158 false
159 }
160
161 pub fn children_of(&self, parent_id: &str) -> Vec<&TimelineBranch> {
163 self.branches
164 .iter()
165 .filter(|b| b.parent_branch.as_deref() == Some(parent_id))
166 .collect()
167 }
168
169 pub fn ancestry(&self, branch_id: &str) -> Vec<&TimelineBranch> {
171 let mut chain = Vec::new();
172 let mut current = branch_id.to_string();
173 while let Some(branch) = self.branches.iter().find(|b| b.branch_id == current) {
174 chain.push(branch);
175 match &branch.parent_branch {
176 Some(p) => current = p.clone(),
177 None => break,
178 }
179 }
180 chain.reverse(); chain
182 }
183
184 pub fn verify_branch_isolation(&self, branch_id: &str) -> bool {
186 let branch = match self.branches.iter().find(|b| b.branch_id == branch_id) {
187 Some(b) => b,
188 None => return false,
189 };
190 if let Some(ref parent_id) = branch.parent_branch {
192 if let Some(parent) = self.branches.iter().find(|b| b.branch_id == *parent_id) {
193 if branch.context_hash() == parent.context_hash() {
194 return false;
195 }
196 }
197 }
198 true
199 }
200
201 pub fn prime(&self) -> Option<&TimelineBranch> {
203 self.branches.iter().find(|b| b.is_prime())
204 }
205}
206
207#[cfg(test)]
208mod tests {
209 use super::*;
210
211 #[test]
212 fn prime_timeline() {
213 let t = TimelineBranch::prime("urn:omni:v1:fiction:star-trek");
214 assert!(t.is_prime());
215 assert_eq!(t.branch_id, "prime");
216 assert!(t.parent_branch.is_none());
217 }
218
219 #[test]
220 fn divergent_branch() {
221 let t = TimelineBranch::divergent(
222 "mirror",
223 "Mirror Terran Timeline",
224 "urn:omni:v1:fiction:star-trek",
225 "antiquity",
226 "prime",
227 );
228 assert!(!t.is_prime());
229 assert_eq!(t.parent_branch, Some("prime".into()));
230 assert!(t.bifurcation_hash != 0);
231 }
232
233 #[test]
234 fn branch_context_hash_differs() {
235 let prime = TimelineBranch::prime("urn:omni:v1:fiction:star-trek");
236 let mirror = TimelineBranch::divergent(
237 "mirror",
238 "Mirror",
239 "urn:omni:v1:fiction:star-trek",
240 "antiquity",
241 "prime",
242 );
243 assert_ne!(prime.context_hash(), mirror.context_hash());
244 }
245
246 #[test]
247 fn dag_add_branch() {
248 let prime = TimelineBranch::prime("urn:omni:v1:fiction:star-trek");
249 let mut dag = TimelineDag::new(prime);
250 let kelvin = TimelineBranch::divergent(
251 "kelvin",
252 "Kelvin Timeline",
253 "urn:omni:v1:fiction:star-trek",
254 "uss-kelvin-destruction",
255 "prime",
256 );
257 assert!(dag.add_branch(kelvin));
258 assert_eq!(dag.branches.len(), 2);
259 }
260
261 #[test]
262 fn dag_rejects_missing_parent() {
263 let prime = TimelineBranch::prime("urn:omni:v1:fiction:star-trek");
264 let mut dag = TimelineDag::new(prime);
265 let orphan = TimelineBranch::divergent(
266 "orphan",
267 "Orphan",
268 "urn:omni:v1:fiction:star-trek",
269 "epoch",
270 "nonexistent",
271 );
272 assert!(!dag.add_branch(orphan));
273 }
274
275 #[test]
276 fn dag_rejects_duplicate() {
277 let prime = TimelineBranch::prime("urn:omni:v1:fiction:star-trek");
278 let mut dag = TimelineDag::new(prime);
279 let dup = TimelineBranch::divergent(
280 "prime",
281 "Duplicate",
282 "urn:omni:v1:fiction:star-trek",
283 "epoch",
284 "prime",
285 );
286 assert!(!dag.add_branch(dup));
287 }
288
289 #[test]
290 fn dag_children_of() {
291 let prime = TimelineBranch::prime("urn:omni:v1:fiction:star-trek");
292 let mut dag = TimelineDag::new(prime);
293 dag.add_branch(TimelineBranch::divergent(
294 "mirror",
295 "Mirror",
296 "urn:omni:v1:fiction:star-trek",
297 "antiquity",
298 "prime",
299 ));
300 dag.add_branch(TimelineBranch::divergent(
301 "kelvin",
302 "Kelvin",
303 "urn:omni:v1:fiction:star-trek",
304 "kelvin-event",
305 "prime",
306 ));
307 let children = dag.children_of("prime");
308 assert_eq!(children.len(), 2);
309 }
310
311 #[test]
312 fn dag_ancestry() {
313 let prime = TimelineBranch::prime("urn:omni:v1:fiction:star-trek");
314 let mut dag = TimelineDag::new(prime);
315 dag.add_branch(TimelineBranch::divergent(
316 "mirror",
317 "Mirror",
318 "urn:omni:v1:fiction:star-trek",
319 "antiquity",
320 "prime",
321 ));
322 dag.add_branch(TimelineBranch::divergent(
323 "mirror-dark",
324 "Dark Mirror",
325 "urn:omni:v1:fiction:star-trek",
326 "later",
327 "mirror",
328 ));
329 let ancestry = dag.ancestry("mirror-dark");
330 assert_eq!(ancestry.len(), 3); assert_eq!(ancestry[0].branch_id, "prime");
332 assert_eq!(ancestry[2].branch_id, "mirror-dark");
333 }
334
335 #[test]
336 fn dag_branch_isolation() {
337 let prime = TimelineBranch::prime("urn:omni:v1:fiction:star-trek");
338 let mut dag = TimelineDag::new(prime);
339 dag.add_branch(TimelineBranch::divergent(
340 "mirror",
341 "Mirror",
342 "urn:omni:v1:fiction:star-trek",
343 "antiquity",
344 "prime",
345 ));
346 assert!(dag.verify_branch_isolation("mirror"));
348 assert!(dag.verify_branch_isolation("prime"));
349 }
350
351 #[test]
352 fn dag_prime_lookup() {
353 let prime = TimelineBranch::prime("urn:omni:v1:fiction:star-trek");
354 let dag = TimelineDag::new(prime);
355 assert!(dag.prime().is_some());
356 assert_eq!(dag.prime().unwrap().branch_id, "prime");
357 }
358
359 #[test]
360 fn branch_to_value() {
361 let t = TimelineBranch::prime("urn:omni:v1:fiction:star-trek");
362 let v = t.to_value();
363 match v {
364 Value::Record(r) => {
365 assert_eq!(r.get("branch_id"), Some(&Value::String("prime".into())));
366 }
367 _ => panic!("expected Record"),
368 }
369 }
370
371 #[test]
372 fn bifurcation_hash_deterministic() {
373 let t1 = TimelineBranch::divergent(
374 "mirror",
375 "Mirror",
376 "urn:omni:v1:fiction:star-trek",
377 "antiquity",
378 "prime",
379 );
380 let t2 = TimelineBranch::divergent(
381 "mirror",
382 "Mirror",
383 "urn:omni:v1:fiction:star-trek",
384 "antiquity",
385 "prime",
386 );
387 assert_eq!(t1.bifurcation_hash, t2.bifurcation_hash);
388 }
389
390 #[test]
391 fn different_branches_different_hash() {
392 let t1 = TimelineBranch::divergent(
393 "mirror",
394 "Mirror",
395 "urn:omni:v1:fiction:star-trek",
396 "antiquity",
397 "prime",
398 );
399 let t2 = TimelineBranch::divergent(
400 "kelvin",
401 "Kelvin",
402 "urn:omni:v1:fiction:star-trek",
403 "kelvin-event",
404 "prime",
405 );
406 assert_ne!(t1.bifurcation_hash, t2.bifurcation_hash);
407 }
408}