Return a deterministic, causality-aware ordering for a session's turns. Stored provenance can arrive in any order (for example during pull). A timestamp plus full provenance hash provides a stable tie-break, while the `previous_provenance` link keeps a child after its parent when both are present. Turn numbers are reassigned from zero after ordering.
(turns: Vec<SessionTurn>)
| 457 | /// `previous_provenance` link keeps a child after its parent when both are |
| 458 | /// present. Turn numbers are reassigned from zero after ordering. |
| 459 | pub fn canonicalize_session_turns(turns: Vec<SessionTurn>) -> Vec<SessionTurn> { |
| 460 | type SortKey = (i64, [u8; 32], usize); |
| 461 | |
| 462 | let count = turns.len(); |
| 463 | let positions: std::collections::HashMap<Hash, usize> = turns |
| 464 | .iter() |
| 465 | .enumerate() |
| 466 | .map(|(index, turn)| (turn.provenance_hash, index)) |
| 467 | .collect(); |
| 468 | let sort_keys: Vec<SortKey> = turns |
| 469 | .iter() |
| 470 | .enumerate() |
| 471 | .map(|(index, turn)| { |
| 472 | ( |
| 473 | crate::types::timestamp::epoch_millis(turn.timestamp), |
| 474 | *turn.provenance_hash.as_bytes(), |
| 475 | index, |
| 476 | ) |
| 477 | }) |
| 478 | .collect(); |
| 479 | let mut children = vec![Vec::new(); count]; |
| 480 | let mut blocked = vec![false; count]; |
| 481 | |
| 482 | for (index, turn) in turns.iter().enumerate() { |
| 483 | if let Some(parent) = turn |
| 484 | .previous_provenance |
| 485 | .and_then(|hash| positions.get(&hash).copied()) |
| 486 | { |
| 487 | blocked[index] = true; |
| 488 | children[parent].push(index); |
| 489 | } |
| 490 | } |
| 491 | |
| 492 | let mut remaining: std::collections::BTreeSet<SortKey> = sort_keys.iter().copied().collect(); |
| 493 | let mut ready: std::collections::BTreeSet<SortKey> = sort_keys |
| 494 | .iter() |
| 495 | .copied() |
| 496 | .filter(|key| !blocked[key.2]) |
| 497 | .collect(); |
| 498 | let mut slots: Vec<Option<SessionTurn>> = turns.into_iter().map(Some).collect(); |
| 499 | let mut ordered = Vec::with_capacity(count); |
| 500 | |
| 501 | while ordered.len() < count { |
| 502 | // If malformed provenance contains a cycle, break it at the same |
| 503 | // timestamp/hash point in every repository. |
| 504 | let key = ready |
| 505 | .pop_first() |
| 506 | .or_else(|| remaining.first().copied()) |
| 507 | .expect("remaining turn while canonicalizing"); |
| 508 | remaining.remove(&key); |
| 509 | let index = key.2; |
| 510 | let Some(turn) = slots[index].take() else { |
| 511 | continue; |
| 512 | }; |
| 513 | ordered.push(turn); |
| 514 | |
| 515 | for child in &children[index] { |
| 516 | if blocked[*child] { |