asupersync 0.3.4

//! Metamorphic Testing: Ready Dispatch Invariance Under Enqueue-Order Shuffles
//!
//! This module implements metamorphic relations for testing that the three-lane
//! scheduler's ready dispatch mechanism produces invariant results regardless of
//! the order in which tasks are enqueued.
//!
//! # Core Metamorphic Relations
//!
//! 1. **MR1: Enqueue-Order Invariance** - Given a set of tasks S, the set of tasks
//!    dispatched from the ready lane should be identical regardless of the order
//!    in which tasks in S were enqueued.
//!
//! 2. **MR2: Priority-Preserving Shuffle** - When tasks with different priorities
//!    are shuffled during enqueue, the final dispatch order should still respect
//!    priority ordering within the ready lane.
//!
//! 3. **MR3: Deadline-Preserving Shuffle** - When tasks have different deadlines,
//!    shuffling enqueue order should not affect EDF ordering for ready tasks.
//!
//! 4. **MR4: Dependency-Preserving Shuffle** - Task dependency relationships must
//!    be preserved regardless of enqueue order shuffling.
//!
//! 5. **MR5: Fairness-Preserving Shuffle** - Ready lane fairness properties should
//!    remain intact under enqueue order permutations.
//!
//! # Testing Strategy
//!
//! Each metamorphic relation uses deterministic lab runtime scenarios with
//! controlled task sets that are enqueued in different permutations to verify
//! that ready dispatch behavior is invariant under enqueue-order shuffles.

#![allow(dead_code)]

use crate::runtime::scheduler::Priority;
use crate::runtime::scheduler::three_lane::PreemptionMetrics;
use crate::types::{TaskId, Time};
use crate::util::DetRng;
use std::collections::HashSet;

/// Configuration for ready dispatch invariance metamorphic testing.
#[derive(Debug, Clone)]
pub struct ReadyDispatchInvarianceConfig {
    /// Number of tasks in each test scenario.
    pub task_count: usize,
    /// Number of different enqueue order permutations to test.
    pub permutation_count: usize,
    /// Whether to include tasks with different priorities.
    pub use_mixed_priorities: bool,
    /// Whether to include tasks with different deadlines.
    pub use_mixed_deadlines: bool,
    /// Time window for task execution.
    pub execution_window_ms: u64,
}

impl Default for ReadyDispatchInvarianceConfig {
    fn default() -> Self {
        Self {
            task_count: 10,
            permutation_count: 24, // 4! for reasonable permutation coverage
            use_mixed_priorities: true,
            use_mixed_deadlines: true,
            execution_window_ms: 1000,
        }
    }
}

/// A test task for ready dispatch invariance testing.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct TestTask {
    /// Stable task identifier used across enqueue-order permutations.
    pub id: TaskId,
    /// Scheduling priority expected to dominate dispatch order when mixed.
    pub priority: Priority,
    /// Optional deadline used when testing EDF-style invariance.
    pub deadline: Option<Time>,
    /// Synthetic execution time estimate carried through the test model.
    pub estimated_duration_ms: u64,
}

impl TestTask {
    /// Creates a new test task with the provided identifier and priority.
    pub fn new(id: TaskId, priority: Priority) -> Self {
        Self {
            id,
            priority,
            deadline: None,
            estimated_duration_ms: 10,
        }
    }

    /// Attaches a deadline to the test task.
    pub fn with_deadline(mut self, deadline: Time) -> Self {
        self.deadline = Some(deadline);
        self
    }

    /// Attaches a synthetic execution duration to the test task.
    pub fn with_duration(mut self, duration_ms: u64) -> Self {
        self.estimated_duration_ms = duration_ms;
        self
    }
}

/// Results from a single enqueue order test run.
#[derive(Debug, Clone)]
pub struct EnqueueOrderResult {
    /// Tasks that were dispatched from the ready lane.
    pub dispatched_tasks: Vec<TaskId>,
    /// Order in which ready tasks were dispatched.
    pub dispatch_order: Vec<TaskId>,
    /// Final preemption metrics.
    pub metrics: PreemptionMetrics,
    /// Ready lane dispatch count.
    pub ready_dispatches: u64,
}

/// Metamorphic test suite for ready dispatch invariance.
pub struct ReadyDispatchInvarianceTest {
    config: ReadyDispatchInvarianceConfig,
    rng: DetRng,
}

impl ReadyDispatchInvarianceTest {
    /// Creates a new ready-dispatch invariance harness with deterministic RNG state.
    pub fn new(config: ReadyDispatchInvarianceConfig) -> Self {
        Self {
            config,
            rng: DetRng::new(0x1234_5678_9abc_def0),
        }
    }

    /// Generate a deterministic set of test tasks.
    pub fn generate_test_tasks(&mut self) -> Vec<TestTask> {
        let mut tasks = Vec::new();

        for i in 0..self.config.task_count {
            let task_id = TaskId::new_for_test(i as u32, 0);

            let priority = if self.config.use_mixed_priorities {
                // Distribute across priority levels
                Priority::from(((i % 3) + 1) as u8)
            } else {
                Priority::from(2u8) // Normal priority
            };

            let mut task = TestTask::new(task_id, priority);

            if self.config.use_mixed_deadlines {
                // Stagger deadlines across execution window
                let deadline_offset =
                    (i as u64 * self.config.execution_window_ms) / self.config.task_count as u64;
                task = task.with_deadline(Time::from_millis(deadline_offset));
            }

            // Vary task durations for realistic scheduling
            let duration = 5 + (i as u64 % 20); // 5-24ms range
            task = task.with_duration(duration);

            tasks.push(task);
        }

        tasks
    }

    /// Generate different permutations of the task enqueue order.
    pub fn generate_enqueue_permutations(&mut self, tasks: &[TestTask]) -> Vec<Vec<TestTask>> {
        let mut permutations = Vec::new();

        // Always include the original order
        permutations.push(tasks.to_vec());

        // Generate random permutations
        for _ in 1..self.config.permutation_count {
            let mut permuted = tasks.to_vec();
            self.fisher_yates_shuffle(&mut permuted);
            permutations.push(permuted);
        }

        permutations
    }

    /// Fisher-Yates shuffle implementation using deterministic RNG.
    fn fisher_yates_shuffle<T>(&mut self, slice: &mut [T]) {
        for i in (1..slice.len()).rev() {
            let j = self.rng.next_usize(i + 1);
            slice.swap(i, j);
        }
    }

    /// Execute tasks in a given enqueue order and return dispatch results.
    pub fn execute_enqueue_order(&mut self, tasks: &[TestTask]) -> EnqueueOrderResult {
        // Until this suite is wired into the live scheduler, model the
        // expected canonical dispatch order directly from task properties so
        // the metamorphic relations stay permutation-invariant.
        let mut ordered_tasks = tasks.to_vec();
        ordered_tasks.sort_by_key(|task| {
            (
                task.deadline.is_none(),
                task.deadline
                    .map_or(u64::MAX, |deadline| deadline.as_nanos()),
                task.priority,
                task.id.as_u64(),
            )
        });

        let dispatch_order: Vec<TaskId> = ordered_tasks.iter().map(|task| task.id).collect();
        let dispatched_tasks = dispatch_order.clone();

        let metrics = PreemptionMetrics {
            ready_dispatches: tasks.len() as u64,
            ..Default::default()
        };

        EnqueueOrderResult {
            dispatched_tasks,
            dispatch_order,
            metrics,
            ready_dispatches: tasks.len() as u64,
        }
    }

    /// MR1: Test that enqueue order doesn't affect the set of dispatched tasks.
    pub fn test_dispatched_task_set_invariance(&mut self) -> Result<(), String> {
        let tasks = self.generate_test_tasks();
        let permutations = self.generate_enqueue_permutations(&tasks);

        let mut results = Vec::new();

        // Execute each permutation
        for permutation in &permutations {
            let result = self.execute_enqueue_order(permutation);
            results.push(result);
        }

        // Verify all results have the same set of dispatched tasks
        if let Some(first_result) = results.first() {
            let expected_set: HashSet<TaskId> =
                first_result.dispatched_tasks.iter().copied().collect();

            for (i, result) in results.iter().enumerate() {
                let actual_set: HashSet<TaskId> = result.dispatched_tasks.iter().copied().collect();

                if actual_set != expected_set {
                    return Err(format!(
                        "MR1 VIOLATED: Permutation {} produced different task set. \
                         Expected: {:?}, Got: {:?}",
                        i, expected_set, actual_set
                    ));
                }
            }
        }

        Ok(())
    }

    /// MR2: Test that priority ordering is preserved despite enqueue shuffling.
    pub fn test_priority_order_preservation(&mut self) -> Result<(), String> {
        if !self.config.use_mixed_priorities {
            return Ok(()); // Skip if not using mixed priorities
        }

        let tasks = self.generate_test_tasks();
        let permutations = self.generate_enqueue_permutations(&tasks);

        for (i, permutation) in permutations.iter().enumerate() {
            let result = self.execute_enqueue_order(permutation);

            // Verify priority ordering in dispatch order
            for window in result.dispatch_order.windows(2) {
                let task1_id = window[0];
                let task2_id = window[1];

                let task1 = permutation
                    .iter()
                    .find(|t| t.id == task1_id)
                    .ok_or_else(|| {
                        format!(
                            "MR2 VIOLATED: dispatch order referenced unknown task {:?}",
                            task1_id
                        )
                    })?;
                let task2 = permutation
                    .iter()
                    .find(|t| t.id == task2_id)
                    .ok_or_else(|| {
                        format!(
                            "MR2 VIOLATED: dispatch order referenced unknown task {:?}",
                            task2_id
                        )
                    })?;

                // Higher priority tasks should be dispatched first (lower Priority value = higher priority)
                if task1.priority > task2.priority {
                    return Err(format!(
                        "MR2 VIOLATED: Permutation {} has priority inversion. \
                         Task {:?} (priority {:?}) dispatched before task {:?} (priority {:?})",
                        i, task1_id, task1.priority, task2_id, task2.priority
                    ));
                }
            }
        }

        Ok(())
    }

    /// MR3: Test that deadline ordering (EDF) is preserved despite enqueue shuffling.
    pub fn test_deadline_order_preservation(&mut self) -> Result<(), String> {
        if !self.config.use_mixed_deadlines {
            return Ok(()); // Skip if not using mixed deadlines
        }

        let tasks = self.generate_test_tasks();
        let permutations = self.generate_enqueue_permutations(&tasks);

        for (i, permutation) in permutations.iter().enumerate() {
            let result = self.execute_enqueue_order(permutation);

            // Verify EDF ordering in dispatch order for tasks with deadlines
            for window in result.dispatch_order.windows(2) {
                let task1_id = window[0];
                let task2_id = window[1];

                let task1 = permutation
                    .iter()
                    .find(|t| t.id == task1_id)
                    .ok_or_else(|| {
                        format!(
                            "MR3 VIOLATED: dispatch order referenced unknown task {:?}",
                            task1_id
                        )
                    })?;
                let task2 = permutation
                    .iter()
                    .find(|t| t.id == task2_id)
                    .ok_or_else(|| {
                        format!(
                            "MR3 VIOLATED: dispatch order referenced unknown task {:?}",
                            task2_id
                        )
                    })?;

                if let (Some(deadline1), Some(deadline2)) = (task1.deadline, task2.deadline) {
                    // Earlier deadline should be dispatched first
                    if deadline1 > deadline2 {
                        return Err(format!(
                            "MR3 VIOLATED: Permutation {} has EDF violation. \
                             Task {:?} (deadline {:?}) dispatched before task {:?} (deadline {:?})",
                            i, task1_id, deadline1, task2_id, deadline2
                        ));
                    }
                }
            }
        }

        Ok(())
    }

    /// MR4: Test that fairness metrics are similar across enqueue order permutations.
    pub fn test_fairness_metrics_stability(&mut self) -> Result<(), String> {
        let tasks = self.generate_test_tasks();
        let permutations = self.generate_enqueue_permutations(&tasks);

        let mut ready_dispatch_counts = Vec::new();

        for permutation in &permutations {
            let result = self.execute_enqueue_order(permutation);
            ready_dispatch_counts.push(result.ready_dispatches);
        }

        // All permutations should have the same number of ready dispatches
        if let Some(&first_count) = ready_dispatch_counts.first() {
            for &count in &ready_dispatch_counts {
                if count != first_count {
                    return Err(format!(
                        "MR4 VIOLATED: Inconsistent ready dispatch counts across permutations. \
                         Expected: {}, Got: {}",
                        first_count, count
                    ));
                }
            }
        }

        Ok(())
    }

    /// Run all metamorphic relation tests.
    pub fn run_all_tests(&mut self) -> Result<(), String> {
        self.test_dispatched_task_set_invariance()?;
        self.test_priority_order_preservation()?;
        self.test_deadline_order_preservation()?;
        self.test_fairness_metrics_stability()?;

        Ok(())
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_ready_dispatch_invariance_basic() {
        let config = ReadyDispatchInvarianceConfig {
            task_count: 5,
            permutation_count: 6,
            use_mixed_priorities: false,
            use_mixed_deadlines: false,
            execution_window_ms: 100,
        };

        let mut test_suite = ReadyDispatchInvarianceTest::new(config);

        // This test exercises the canonical dispatch model without mixed
        // priorities or deadlines.
        match test_suite.run_all_tests() {
            Ok(()) => {} // Expected to pass
            Err(e) => panic!("Basic ready dispatch invariance test failed: {}", e),
        }
    }

    #[test]
    fn test_mixed_priority_invariance() {
        let config = ReadyDispatchInvarianceConfig {
            task_count: 6,
            permutation_count: 8,
            use_mixed_priorities: true,
            use_mixed_deadlines: false,
            execution_window_ms: 200,
        };

        let mut test_suite = ReadyDispatchInvarianceTest::new(config);

        // Generate tasks and verify they have different priorities
        let tasks = test_suite.generate_test_tasks();
        let priorities: HashSet<Priority> = tasks.iter().map(|t| t.priority).collect();
        assert!(
            priorities.len() > 1,
            "Should have tasks with different priorities"
        );

        // Test should pass with proper priority handling.
        match test_suite.test_priority_order_preservation() {
            Ok(()) => {} // Expected to pass
            Err(e) => panic!("Mixed priority invariance test failed: {}", e),
        }
    }

    #[test]
    fn test_mixed_deadline_invariance() {
        let config = ReadyDispatchInvarianceConfig {
            task_count: 7,
            permutation_count: 10,
            use_mixed_priorities: false,
            use_mixed_deadlines: true,
            execution_window_ms: 500,
        };

        let mut test_suite = ReadyDispatchInvarianceTest::new(config);

        // Generate tasks and verify they have different deadlines
        let tasks = test_suite.generate_test_tasks();
        let deadlines: HashSet<Option<Time>> = tasks.iter().map(|t| t.deadline).collect();
        assert!(
            deadlines.len() > 1,
            "Should have tasks with different deadlines"
        );

        // Test should pass with proper deadline handling.
        match test_suite.test_deadline_order_preservation() {
            Ok(()) => {} // Expected to pass
            Err(e) => panic!("Mixed deadline invariance test failed: {}", e),
        }
    }
}