Function canonicalize_session_turns

atomic-core/src/change/session.rs:81–143

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

/// `previous_provenance` link keeps a child after its parent when both are
/// present. Turn numbers are reassigned from zero after ordering.
pub fn canonicalize_session_turns(turns: Vec<SessionTurn>) -> Vec<SessionTurn> {
    type SortKey = (i64, [u8; 32], usize);

    let count = turns.len();
    let positions: std::collections::HashMap<Hash, usize> = turns
        .iter()
        .enumerate()
        .map(|(index, turn)| (turn.provenance_hash, index))
        .collect();
    let sort_keys: Vec<SortKey> = turns
        .iter()
        .enumerate()
        .map(|(index, turn)| (turn.timestamp, *turn.provenance_hash.as_bytes(), index))
        .collect();
    let mut children = vec![Vec::new(); count];
    let mut blocked = vec![false; count];

    for (index, turn) in turns.iter().enumerate() {
        if let Some(parent) = turn
            .previous_provenance
            .and_then(|hash| positions.get(&hash).copied())
        {
            blocked[index] = true;
            children[parent].push(index);
        }
    }

    let mut remaining: std::collections::BTreeSet<SortKey> = sort_keys.iter().copied().collect();
    let mut ready: std::collections::BTreeSet<SortKey> = sort_keys
        .iter()
        .copied()
        .filter(|key| !blocked[key.2])
        .collect();
    let mut slots: Vec<Option<SessionTurn>> = turns.into_iter().map(Some).collect();
    let mut ordered = Vec::with_capacity(count);

    while ordered.len() < count {
        // If malformed provenance contains a cycle, break it at the same
        // timestamp/hash point in every repository.
        let key = ready
            .pop_first()
            .or_else(|| remaining.first().copied())
            .expect("remaining turn while canonicalizing");
        remaining.remove(&key);
        let index = key.2;
        let Some(turn) = slots[index].take() else {
            continue;
        };
        ordered.push(turn);

        for child in &children[index] {
            if blocked[*child] {
                blocked[*child] = false;
                ready.insert(sort_keys[*child]);
            }
        }
    }