vortex_trace/

minimize.rs

//! Trace minimization for failing simulation seeds.
//!
//! When a swarm run finds a failing seed over many ticks, debugging is hard.
//! The minimizer finds the shortest trace that still reproduces the bug.
//!
//! Inspired by Delta Debugging (Zeller, "Simplifying and Isolating
//! Failure-Inducing Input", 2002). Independent implementation.

/// Result of trace minimization.
#[derive(Debug, Clone)]
pub struct MinimizedTrace {
    /// Original tick duration.
    pub original_ticks: u64,
    /// Minimized tick duration that still reproduces the failure.
    pub minimized_ticks: u64,
    /// Original number of fault events.
    pub original_faults: usize,
    /// Minimized number of fault events.
    pub minimized_faults: usize,
    /// The essential fault indices (into the original schedule).
    pub essential_fault_indices: Vec<usize>,
}

/// Minimize the tick duration needed to reproduce a failure.
///
/// Binary searches on the tick count to find the minimum number of ticks
/// that still triggers the invariant violation.
///
/// - `reproduce_fn`: `(ticks) -> bool` — returns true if the failure reproduces
///   at the given tick count.
/// - `max_ticks`: upper bound (must reproduce at this count).
/// - `min_ticks`: lower bound for the search (default: 1).
///
/// ```
/// use vortex_trace::minimize::minimize_ticks;
///
/// // Example: find minimum ticks for a bug that appears after tick 750
/// let result = minimize_ticks(|ticks| ticks >= 750, 2000, 1);
/// assert!(result.minimized_ticks >= 750);
/// assert!(result.minimized_ticks < 800); // Binary search precision
/// ```
pub fn minimize_ticks<F>(reproduce_fn: F, max_ticks: u64, min_ticks: u64) -> MinimizedTrace
where
    F: Fn(u64) -> bool,
{
    // Verify the failure reproduces at max_ticks
    if !reproduce_fn(max_ticks) {
        return MinimizedTrace {
            original_ticks: max_ticks,
            minimized_ticks: max_ticks,
            original_faults: 0,
            minimized_faults: 0,
            essential_fault_indices: Vec::new(),
        };
    }

    let mut lo = min_ticks;
    let mut hi = max_ticks;

    while lo + 1 < hi {
        let mid = lo + (hi - lo) / 2;
        if reproduce_fn(mid) {
            hi = mid;
        } else {
            lo = mid;
        }
    }

    MinimizedTrace {
        original_ticks: max_ticks,
        minimized_ticks: hi,
        original_faults: 0,
        minimized_faults: 0,
        essential_fault_indices: Vec::new(),
    }
}

/// Minimize a fault schedule using delta debugging.
///
/// Tries removing faults one by one (with paired events like crash/restart
/// handled together). Returns the indices of essential faults.
///
/// - `num_faults`: total number of fault events in the original schedule.
/// - `is_paired`: `(idx) -> Option<usize>` returns the paired event index
///   (e.g., restart for a crash, heal for a partition).
/// - `reproduce_with`: `(&[usize]) -> bool` takes a list of *active* fault
///   indices and returns whether the failure reproduces.
///
/// ```
/// use vortex_trace::minimize::minimize_faults;
///
/// // Example: 10 faults, only fault 3 is essential
/// let result = minimize_faults(
///     10,
///     |_| None,  // no paired events
///     |active| active.contains(&3),  // only reproduces if fault 3 is active
/// );
/// assert!(result.essential_fault_indices.contains(&3));
/// assert!(result.minimized_faults <= 2); // fault 3 (+ maybe its pair)
/// ```
pub fn minimize_faults<P, R>(num_faults: usize, is_paired: P, reproduce_with: R) -> MinimizedTrace
where
    P: Fn(usize) -> Option<usize>,
    R: Fn(&[usize]) -> bool,
{
    let mut active: Vec<bool> = vec![true; num_faults];

    // Try removing each fault (and its pair)
    for idx in 0..num_faults {
        if !active[idx] {
            continue;
        }

        let paired = is_paired(idx);

        // Tentatively remove
        active[idx] = false;
        if let Some(pair_idx) = paired {
            active[pair_idx] = false;
        }

        // Check if failure still reproduces without this fault
        let active_indices: Vec<usize> = active
            .iter()
            .enumerate()
            .filter(|(_, a)| **a)
            .map(|(i, _)| i)
            .collect();

        if !reproduce_with(&active_indices) {
            // This fault is essential — put it back
            active[idx] = true;
            if let Some(pair_idx) = paired {
                active[pair_idx] = true;
            }
        }
    }

    let essential: Vec<usize> = active
        .iter()
        .enumerate()
        .filter(|(_, a)| **a)
        .map(|(i, _)| i)
        .collect();

    MinimizedTrace {
        original_ticks: 0,
        minimized_ticks: 0,
        original_faults: num_faults,
        minimized_faults: essential.len(),
        essential_fault_indices: essential,
    }
}

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

    #[test]
    fn test_minimize_ticks_binary_search() {
        // Bug appears at tick >= 500
        let result = minimize_ticks(|ticks| ticks >= 500, 2000, 1);
        assert_eq!(result.minimized_ticks, 500);
        assert_eq!(result.original_ticks, 2000);
    }

    #[test]
    fn test_minimize_ticks_no_reproduction() {
        // Bug never reproduces
        let result = minimize_ticks(|_| false, 1000, 1);
        assert_eq!(result.minimized_ticks, 1000);
    }

    #[test]
    fn test_minimize_ticks_always_reproduces() {
        // Bug reproduces at any tick count — binary search converges to min_ticks + 1
        // because lo starts at min_ticks and loop condition is lo + 1 < hi
        let result = minimize_ticks(|_| true, 1000, 1);
        assert_eq!(result.minimized_ticks, 2);

        // With min_ticks=0, converges to 1
        let result = minimize_ticks(|_| true, 1000, 0);
        assert_eq!(result.minimized_ticks, 1);
    }

    #[test]
    fn test_minimize_faults_single_essential() {
        // 10 faults, only fault 5 is essential
        let result = minimize_faults(10, |_| None, |active| active.contains(&5));
        assert_eq!(result.minimized_faults, 1);
        assert_eq!(result.essential_fault_indices, vec![5]);
    }

    #[test]
    fn test_minimize_faults_multiple_essential() {
        // Faults 2 AND 7 are both needed
        let result = minimize_faults(
            10,
            |_| None,
            |active| active.contains(&2) && active.contains(&7),
        );
        assert_eq!(result.minimized_faults, 2);
        assert!(result.essential_fault_indices.contains(&2));
        assert!(result.essential_fault_indices.contains(&7));
    }

    #[test]
    fn test_minimize_faults_with_pairs() {
        // Fault 0 (crash) is paired with fault 1 (restart), fault 2 is essential
        let result = minimize_faults(
            4,
            |idx| match idx {
                0 => Some(1), // crash -> restart
                1 => Some(0), // restart -> crash
                _ => None,
            },
            |active| active.contains(&2),
        );
        assert!(result.essential_fault_indices.contains(&2));
        // Crash/restart pair (0,1) should have been removed since they're not essential
        assert!(!result.essential_fault_indices.contains(&0));
        assert!(!result.essential_fault_indices.contains(&1));
    }

    #[test]
    fn test_minimize_faults_all_essential() {
        // All faults are needed
        let result = minimize_faults(3, |_| None, |active| active.len() == 3);
        assert_eq!(result.minimized_faults, 3);
    }

    #[test]
    fn test_minimize_faults_none_essential() {
        // Bug reproduces with no faults
        let result = minimize_faults(5, |_| None, |_| true);
        assert_eq!(result.minimized_faults, 0);
        assert!(result.essential_fault_indices.is_empty());
    }
}