vj-sim 0.3.0

//! SCHED::ORDER — canonical ordering & intra-region commit infrastructure
//! (scheduler.md §6, ARCHITECTURE §4 item 3; ledger SC-010, SC-012, SC-013,
//! SC-014, DT-005, DT-010).
//!
//! This module is the one place that turns a ready-set of [`PendingActivation`]s
//! into the canonical, thread-count-independent dispatch order (DT-005's
//! precondition for `DeterminismController::partition`), and the one place that
//! resolves same-cell write hazards within a delta cycle by canonical-key order
//! rather than by submission/arrival order (SC-010, SC-012 — the generalized
//! NANDi per-bank write-queue fix: buffer, never apply-on-arrival, commit in
//! canonical order).

use crate::determinism::CanonicalEventKey;
use crate::sched::{PendingActivation, ProcessId, SchedTime};
use crate::state::StateCellId;

/// The 4 fields of [`CanonicalEventKey`] a ready-set activation determines on
/// its own. `local_send_seq` is assigned later, at effect-emission time (per
/// the existing determinism test's own convention), so it is not part of
/// ready-set ordering and is not returned here.
pub fn canonical_key_of(a: &PendingActivation) -> (SchedTime, u32, u32, ProcessId) {
    (
        a.logical_order.0,
        a.logical_order.1 as u32,
        a.reconv_iter,
        a.proc,
    )
}

/// Sorts `ready` in place into the canonical, thread-count-independent
/// dispatch order: `(SimTime, Region, reconv_iter, registration_order)`
/// (DT-005 — this must run before any `DeterminismController::partition`
/// call). `logical_order.2` is the registration-order tiebreak
/// (`PendingActivation::logical_order: (SchedTime, Region, u64)`).
pub fn sort_ready_set(ready: &mut [PendingActivation]) {
    ready.sort_by_key(|a| {
        (
            a.logical_order.0,
            a.logical_order.1 as u32,
            a.reconv_iter,
            a.logical_order.2,
        )
    });
}

/// Buffers writes to state cells and resolves same-cell write hazards within
/// one delta cycle by canonical-key order, never by push/thread/arrival order
/// (SC-010, SC-012). Generic over `T` so Task 7 (NBA commit) reuses this
/// instead of hand-rolling its own last-write-wins resolver.
///
/// **Not** reused by `commit_blocking_write`: a blocking write commits
/// synchronously, one call, one cell, inside one `resume()`; two processes'
/// blocking writes to the same cell in the same Active pass are two separate,
/// sequential `commit_blocking_write` calls already made in canonical
/// dispatch order, so the last call to physically run already *is* the
/// last-write-wins outcome — there is no multi-entry buffer to resolve.
pub struct WriteBuffer<T> {
    entries: Vec<(CanonicalEventKey, StateCellId, T)>,
}

impl<T> Default for WriteBuffer<T> {
    fn default() -> Self {
        Self {
            entries: Vec::new(),
        }
    }
}

impl<T> WriteBuffer<T> {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn push(&mut self, key: CanonicalEventKey, cell: StateCellId, value: T) {
        self.entries.push((key, cell, value));
    }

    /// Groups buffered writes by [`StateCellId`] and keeps, for each cell,
    /// the entry with the maximum [`CanonicalEventKey`] — comparing by
    /// canonical key, never by push/`Vec` insertion order. Output order is
    /// by `StateCellId` (stable, deterministic — not caller-order-dependent).
    pub fn resolve_last_write_wins(self) -> Vec<(StateCellId, T)> {
        let mut by_cell: std::collections::BTreeMap<StateCellId, (CanonicalEventKey, T)> =
            std::collections::BTreeMap::new();
        for (key, cell, value) in self.entries {
            match by_cell.get(&cell) {
                Some((existing_key, _)) if *existing_key >= key => {
                    // A later-or-equal-ranked write is already buffered for
                    // this cell; this entry loses regardless of push order.
                }
                _ => {
                    by_cell.insert(cell, (key, value));
                }
            }
        }
        by_cell
            .into_iter()
            .map(|(cell, (_, value))| (cell, value))
            .collect()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::sched::ResumeArg;
    use vj_abi::Region;

    fn activation(
        id: u64,
        proc: ProcessId,
        ticks: u64,
        region: Region,
        reconv_iter: u32,
        registration_order: u64,
    ) -> PendingActivation {
        PendingActivation {
            id,
            proc,
            arg: ResumeArg::Start,
            reconv_iter,
            logical_order: (SchedTime { ticks }, region, registration_order),
        }
    }

    fn key(
        ticks: u64,
        region: Region,
        reconv_iter: u32,
        proc: ProcessId,
        seq: u64,
    ) -> CanonicalEventKey {
        CanonicalEventKey {
            vtime: SchedTime { ticks },
            region_ordinal: region as u32,
            reconv_iter,
            canonical_process_id: proc,
            local_send_seq: seq,
        }
    }

    #[test]
    fn sort_ready_set_is_insertion_order_independent() {
        let a = activation(1, 10, 5, Region::Active, 0, 0);
        let b = activation(2, 11, 5, Region::Active, 0, 1);
        let c = activation(3, 12, 5, Region::Active, 0, 2);
        let d = activation(4, 13, 5, Region::Active, 0, 3);

        let mut order1 = vec![c, a, d, b];
        let mut order2 = vec![b, d, a, c];

        sort_ready_set(&mut order1);
        sort_ready_set(&mut order2);

        let procs1: Vec<ProcessId> = order1.iter().map(|x| x.proc).collect();
        let procs2: Vec<ProcessId> = order2.iter().map(|x| x.proc).collect();
        assert_eq!(procs1, procs2);
        assert_eq!(procs1, vec![10, 11, 12, 13]);
    }

    #[test]
    fn sort_ready_set_orders_by_time_then_region_then_reconv_iter_then_registration() {
        // Each activation differs from its neighbor in exactly the next
        // tiebreak field, so the expected order below is exercised strictly:
        // time first, then region, then reconv_iter, then registration_order.
        let earliest_time = activation(1, 100, 1, Region::Active, 0, 5); // time=1 wins outright
        let later_time_early_region = activation(2, 101, 2, Region::Active, 0, 9);
        let later_time_later_region = activation(3, 102, 2, Region::Nba, 0, 0);
        let same_tr_early_reconv = activation(4, 103, 2, Region::Nba, 1, 9);
        let same_tr_late_reconv_early_reg = activation(5, 104, 2, Region::Nba, 2, 0);
        let same_tr_late_reconv_late_reg = activation(6, 105, 2, Region::Nba, 2, 1);

        let mut ready = vec![
            same_tr_late_reconv_late_reg,
            same_tr_early_reconv,
            later_time_later_region,
            earliest_time,
            same_tr_late_reconv_early_reg,
            later_time_early_region,
        ];

        sort_ready_set(&mut ready);

        let procs: Vec<ProcessId> = ready.iter().map(|x| x.proc).collect();
        assert_eq!(procs, vec![100, 101, 102, 103, 104, 105]);
    }

    #[test]
    fn write_buffer_last_write_wins_is_key_order_not_push_order() {
        let cell = StateCellId(7);
        let k0 = key(1, Region::Active, 0, 0, 0);
        let k1 = key(2, Region::Active, 0, 0, 0);
        let k2 = key(3, Region::Active, 0, 0, 0);
        assert!(k0 < k1);
        assert!(k1 < k2);

        let mut buf: WriteBuffer<u32> = WriteBuffer::new();
        // Push order deliberately NOT key order: k2, k0, k1.
        buf.push(k2, cell, 200);
        buf.push(k0, cell, 0);
        buf.push(k1, cell, 100);

        let resolved = buf.resolve_last_write_wins();
        assert_eq!(resolved, vec![(cell, 200)]);
    }

    #[test]
    fn write_buffer_out_of_order_submission_still_commits_in_key_order() {
        let cell = StateCellId(3);
        let k_t5 = key(5, Region::Nba, 0, 0, 0);
        let k_t3 = key(3, Region::Nba, 0, 0, 0);

        let mut buf: WriteBuffer<&'static str> = WriteBuffer::new();
        // Submitted out of order: t=5 first (correct answer), then t=3.
        buf.push(k_t5, cell, "t5-value");
        buf.push(k_t3, cell, "t3-value");

        let resolved = buf.resolve_last_write_wins();
        assert_eq!(resolved, vec![(cell, "t5-value")]);
    }

    #[test]
    fn dt010_single_canonical_key_type_used_by_both_ready_set_and_write_buffer() {
        let a = activation(1, 42, 5, Region::Active, 0, 0);
        let (ticks, region_ordinal, reconv_iter, proc) = canonical_key_of(&a);
        let built_key = CanonicalEventKey {
            vtime: ticks,
            region_ordinal,
            reconv_iter,
            canonical_process_id: proc,
            local_send_seq: 0,
        };

        let mut buf: WriteBuffer<u8> = WriteBuffer::new();
        buf.push(built_key, StateCellId(1), 1);
        let resolved = buf.resolve_last_write_wins();
        assert_eq!(resolved, vec![(StateCellId(1), 1)]);
    }
}