MCPcopy Create free account
hub / github.com/atomicdotdev/atomic / canonicalize_session_turns

Function canonicalize_session_turns

atomic-core/src/change/session.rs:459–527  ·  view source on GitHub ↗

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>)

Source from the content-addressed store, hash-verified

457/// `previous_provenance` link keeps a child after its parent when both are
458/// present. Turn numbers are reassigned from zero after ordering.
459pub 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] {

Calls 11

epoch_millisFunction · 0.85
iter_mutMethod · 0.80
getMethod · 0.65
removeMethod · 0.65
lenMethod · 0.45
collectMethod · 0.45
iterMethod · 0.45
as_bytesMethod · 0.45
pushMethod · 0.45
into_iterMethod · 0.45
insertMethod · 0.45