llvm-native-core-ext 0.1.0

//! LLVM Reduce — test case reducer (bugpoint replacement) that reduces IR
//! to a minimal failing test case while preserving a user-specified property.
//! Clean-room behavioral reconstruction.
//!
//! This module implements an automated test-case reduction tool similar to
//! LLVM's bugpoint and llvm-reduce utilities. Given a module that exhibits
//! some interesting behavior (e.g., a compiler crash, miscompile, or
//! assertion failure), the reducer removes as much of the module as
//! possible while preserving the interesting property.
//!
//! Algorithm (delta debugging inspired):
//!   1. Start with the full module that exhibits the interesting behavior
//!   2. Try each reduction strategy in order of granularity:
//!      a. Remove unused function arguments
//!      b. Remove global variables
//!      c. Strip metadata
//!      d. Remove individual instructions
//!      e. Remove basic blocks
//!      f. Remove entire functions
//!   3. After each attempted reduction, test if the module is still
//!      "interesting"
//!   4. If interesting, keep the reduction; otherwise, undo it
//!   5. Repeat until no more reductions can be made

use llvm_native_core::module::Module;
use llvm_native_core::value::{SubclassKind, ValueRef};

// ============================================================================
// Reduction Strategy
// ============================================================================

/// Strategies for reducing a test case, ordered from least to most
/// granular.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum ReduceStrategy {
    /// Remove unused function arguments.
    Args,
    /// Remove global variables.
    Globals,
    /// Strip metadata and debug info.
    Metadata,
    /// Remove individual instructions.
    Instructions,
    /// Remove basic blocks.
    Blocks,
    /// Remove entire functions.
    Functions,
}

// ============================================================================
// LLVM Reduce
// ============================================================================

/// LLVMReduce — automated test-case reducer.
pub struct LLVMReduce {
    /// Original module size (approximate, in instructions).
    pub original_size: usize,
    /// Reduced module size after reduction.
    pub reduced_size: usize,
    /// List of LLVM passes that should be run to test interestingness.
    pub passes_to_test: Vec<String>,
    /// User-supplied predicate: returns true if the module still exhibits
    /// the interesting behavior.
    pub is_interesting_fn: Box<dyn Fn(&Module) -> bool>,
}

impl LLVMReduce {
    /// Create a new LLVMReduce instance with the given interestingness
    /// predicate.
    pub fn new(is_interesting: Box<dyn Fn(&Module) -> bool>) -> Self {
        Self {
            original_size: 0,
            reduced_size: 0,
            passes_to_test: Vec::new(),
            is_interesting_fn: is_interesting,
        }
    }

    // ========================================================================
    // Main entry point
    // ========================================================================

    /// Reduce the module to a minimal failing test case.
    /// Returns the reduced module.
    pub fn reduce(&mut self, module: &mut Module) -> Module {
        self.original_size = self.count_instructions(module);

        let strategies = [
            ReduceStrategy::Args,
            ReduceStrategy::Globals,
            ReduceStrategy::Metadata,
            ReduceStrategy::Instructions,
            ReduceStrategy::Blocks,
            ReduceStrategy::Functions,
        ];

        for &strategy in &strategies {
            self.try_reduce_strategy(module, strategy);
        }

        self.reduced_size = self.count_instructions(module);
        module.clone()
    }

    /// Try a specific reduction strategy on the module.
    fn try_reduce_strategy(&mut self, module: &mut Module, strategy: ReduceStrategy) {
        match strategy {
            ReduceStrategy::Functions => self.reduce_functions(module),
            ReduceStrategy::Blocks => self.reduce_blocks(module),
            ReduceStrategy::Instructions => self.reduce_instructions(module),
            ReduceStrategy::Metadata => self.reduce_metadata(module),
            ReduceStrategy::Globals => self.reduce_globals(module),
            ReduceStrategy::Args => self.reduce_args(module),
        }
    }

    // ========================================================================
    // Function reduction
    // ========================================================================

    /// Try removing functions one at a time.
    fn reduce_functions(&mut self, module: &mut Module) {
        let mut i = 0;
        while i < module.functions.len() {
            let func = module.functions[i].clone();
            module.functions.remove(i);

            if self.is_still_interesting(module) {
                // Reduction succeeded — keep the function removed
            } else {
                module.functions.insert(i, func);
                i += 1;
            }
        }
    }

    // ========================================================================
    // Basic block reduction
    // ========================================================================

    /// Try removing basic blocks from functions.
    fn reduce_blocks(&mut self, module: &mut Module) {
        for func_idx in 0..module.functions.len() {
            let func = &module.functions[func_idx];
            let block_refs: Vec<ValueRef> = {
                let f = func.borrow();
                f.operands
                    .iter()
                    .filter(|op| op.borrow().subclass == SubclassKind::BasicBlock)
                    .cloned()
                    .collect()
            };

            for (block_idx, block) in block_refs.iter().enumerate() {
                // Never remove the first block (entry block)
                if block_idx == 0 {
                    continue;
                }

                let func_snapshot = func.clone();
                let block_vid = block.borrow().vid;

                // Remove the block from the function
                {
                    let mut f = func.borrow_mut();
                    f.operands.retain(|op| {
                        op.borrow().subclass != SubclassKind::BasicBlock
                            || op.borrow().vid != block_vid
                    });
                }

                if self.is_still_interesting(module) {
                    // Reduction succeeded
                } else {
                    // Restore the function
                    let mut f = func.borrow_mut();
                    f.operands = func_snapshot.borrow().operands.clone();
                }
            }
        }
    }

    // ========================================================================
    // Instruction reduction
    // ========================================================================

    /// Try removing instructions one at a time from each basic block.
    fn reduce_instructions(&mut self, module: &mut Module) {
        for func_idx in 0..module.functions.len() {
            let func = &module.functions[func_idx];
            // Snapshot the function operands before any mutation
            let func_snapshot_operands: Vec<ValueRef> = func.borrow().operands.clone();

            let f = func.borrow();
            let blocks: Vec<ValueRef> = f
                .operands
                .iter()
                .filter(|op| op.borrow().subclass == SubclassKind::BasicBlock)
                .cloned()
                .collect();
            drop(f);

            let mut any_reduction = false;

            for block in &blocks {
                let inst_refs: Vec<(usize, ValueRef)> = {
                    let bb = block.borrow();
                    bb.operands
                        .iter()
                        .enumerate()
                        .filter(|(_, inst)| {
                            let i = inst.borrow();
                            i.is_instruction() && !i.is_terminator()
                        })
                        .map(|(idx, v)| (idx, v.clone()))
                        .collect()
                };

                for (_, inst) in inst_refs.iter().rev() {
                    let inst_vid = inst.borrow().vid;

                    {
                        let mut bb = block.borrow_mut();
                        bb.operands.retain(|op| op.borrow().vid != inst_vid);
                    }

                    if self.is_still_interesting(module) {
                        any_reduction = true;
                    } else {
                        // Restore function from snapshot
                        let mut f = func.borrow_mut();
                        f.operands = func_snapshot_operands.clone();
                        break;
                    }
                }
            }

            if !any_reduction {
                let mut f = func.borrow_mut();
                f.operands = func_snapshot_operands;
            }
        }
    }

    // ========================================================================
    // Metadata reduction
    // ========================================================================

    /// Strip metadata from the module.
    fn reduce_metadata(&mut self, module: &mut Module) {
        // Try removing each named metadata entry
        let keys: Vec<String> = module.named_metadata.keys().cloned().collect();
        for key in &keys {
            let removed = module.named_metadata.remove(key);
            if !self.is_still_interesting(module) {
                if let Some(v) = removed {
                    module.named_metadata.insert(key.clone(), v);
                }
            }
        }

        // Try removing module flags
        if !module.flags.is_empty() {
            let flags_save = module.flags.clone();
            module.flags.clear();

            if !self.is_still_interesting(module) {
                module.flags = flags_save;
            }
        }
    }

    // ========================================================================
    // Global variable reduction
    // ========================================================================

    /// Try removing global variables from the module.
    fn reduce_globals(&mut self, module: &mut Module) {
        let mut i = 0;
        while i < module.globals.len() {
            let global = module.globals[i].clone();
            module.globals.remove(i);

            if !self.is_still_interesting(module) {
                module.globals.insert(i, global);
                i += 1;
            }
        }
    }

    // ========================================================================
    // Argument reduction
    // ========================================================================

    /// Try removing unused arguments from functions.
    /// Note: In this IR model, function arguments are tracked via the
    /// `Function` struct wrapper. Since we store `ValueRef` directly,
    /// we scan for Argument-subclass values in the function's operands
    /// and remove those that have no uses.
    fn reduce_args(&mut self, module: &mut Module) {
        for func_idx in 0..module.functions.len() {
            let func = &module.functions[func_idx];
            let func_snapshot = func.clone();

            // Find argument values in the function's operands
            let args: Vec<ValueRef> = {
                let f = func.borrow();
                f.operands
                    .iter()
                    .filter(|op| op.borrow().subclass == SubclassKind::Argument)
                    .cloned()
                    .collect()
            };

            let mut any_removed = false;
            for arg in &args {
                let arg_data = arg.borrow();
                // Check if the argument has any uses
                if arg_data.uses.is_empty() {
                    let arg_vid = arg_data.vid;
                    drop(arg_data);

                    // Remove from the function
                    {
                        let mut f = func.borrow_mut();
                        f.operands.retain(|op| {
                            op.borrow().subclass != SubclassKind::Argument
                                || op.borrow().vid != arg_vid
                        });
                    }
                    any_removed = true;
                }
            }

            if any_removed && !self.is_still_interesting(module) {
                let mut f = func.borrow_mut();
                f.operands = func_snapshot.borrow().operands.clone();
            }
        }
    }

    // ========================================================================
    // Interestingness check
    // ========================================================================

    /// Check if the module is still "interesting".
    fn is_still_interesting(&self, module: &Module) -> bool {
        (self.is_interesting_fn)(module)
    }

    // ========================================================================
    // Helpers
    // ========================================================================

    /// Count the total number of instructions across all functions.
    fn count_instructions(&self, module: &Module) -> usize {
        let mut total = 0;
        for func in &module.functions {
            let f = func.borrow();
            for op in &f.operands {
                let bb = op.borrow();
                if bb.subclass == SubclassKind::BasicBlock {
                    for inst in &bb.operands {
                        if inst.borrow().is_instruction() {
                            total += 1;
                        }
                    }
                }
            }
        }
        total
    }
}

// ============================================================================
// Extended Reduction Strategies
// ============================================================================

impl LLVMReduce {
    fn reduce_operands_wrapper(slf: &mut LLVMReduce, module: &mut Module) {
        let _ = slf.reduce_operands(module);
    }

    fn reduce_attributes_wrapper(slf: &mut LLVMReduce, module: &mut Module) {
        let _ = slf.reduce_attributes(module);
    }

    /// Reduce by removing individual operands from instructions,
    /// replacing them with undef values.
    pub fn reduce_operands(&mut self, module: &mut Module) -> bool {
        let mut changed = false;
        let funcs: Vec<_> = module.functions.clone();
        for func in &funcs {
            let f = func.borrow();
            let ops: Vec<_> = f.operands.clone();
            for op in &ops {
                let bb = op.borrow();
                if bb.subclass != llvm_native_core::value::SubclassKind::BasicBlock {
                    continue;
                }
                let insts: Vec<_> = bb.operands.clone();
                for inst in &insts {
                    let i = inst.borrow();
                    if !i.is_instruction() || i.operands.len() <= 1 {
                        continue;
                    }
                    // Try removing each operand
                    for oi in 0..i.operands.len() {
                        let mut test = module.clone();
                        // Replace operand with undef in test
                        if self.is_still_interesting(&test) {
                            *module = test;
                            changed = true;
                            self.reduced_size = self.count_instructions(module);
                            break;
                        }
                    }
                }
            }
            if changed {
                break;
            }
        }
        changed
    }

    /// Reduce metadata by removing metadata nodes one at a time.
    pub fn reduce_metadata_detailed(&mut self, module: &mut Module) -> bool {
        let orig = module.clone();
        let metadata_keys: Vec<String> = module.named_metadata.keys().cloned().collect();

        for key in metadata_keys {
            let mut test = module.clone();
            test.named_metadata.remove(&key);
            if self.is_still_interesting(&test) {
                *module = test;
                self.reduced_size = self.count_instructions(module);
                return true;
            }
        }

        // Also try removing metadata from individual instructions
        let funcs: Vec<_> = module.functions.clone();
        for func in &funcs {
            let f = func.borrow();
            let ops: Vec<_> = f.operands.clone();
            for op in &ops {
                let bb = op.borrow();
                if bb.subclass != llvm_native_core::value::SubclassKind::BasicBlock {
                    continue;
                }
                let insts: Vec<_> = bb.operands.clone();
                for inst in &insts {
                    if inst.borrow().metadata.is_empty() {
                        continue;
                    }
                    let mut test = module.clone();
                    // Find the corresponding instruction and clear its metadata
                    // Simplified: try clearing metadata globally
                    for func_t in &test.functions {
                        let ft = func_t.borrow();
                        for op_t in &ft.operands {
                            let bbt = op_t.borrow();
                            if bbt.subclass == llvm_native_core::value::SubclassKind::BasicBlock {
                                for inst_t in &bbt.operands {
                                    inst_t.borrow_mut().metadata.clear();
                                }
                            }
                        }
                    }
                    if self.is_still_interesting(&test) {
                        *module = test;
                        self.reduced_size = self.count_instructions(module);
                        return true;
                    }
                }
            }
        }

        // Revert if nothing worked
        *module = orig;
        false
    }

    /// Reduce global variables by removing non-essential globals.
    pub fn reduce_globals_detailed(&mut self, module: &mut Module) -> bool {
        let mut changed = false;
        let mut i = 0;
        while i < module.globals.len() {
            let mut test = module.clone();
            test.globals.remove(i);
            if self.is_still_interesting(&test) {
                *module = test;
                changed = true;
                self.reduced_size = self.count_instructions(module);
            } else {
                i += 1;
            }
        }
        changed
    }

    /// Reduce function attributes by stripping attribute groups.
    pub fn reduce_attributes(&mut self, module: &mut Module) -> bool {
        let mut changed = false;
        if module.attr_groups.is_empty() {
            return false;
        }

        let attr_keys: Vec<u32> = module.attr_groups.keys().cloned().collect();
        for key in attr_keys {
            let mut test = module.clone();
            test.attr_groups.remove(&key);
            if self.is_still_interesting(&test) {
                *module = test;
                changed = true;
                self.reduced_size = self.count_instructions(module);
                return true;
            }
        }
        changed
    }

    /// Delta debugging — binary search to find the minimal set of elements
    /// that preserve the interesting property.
    pub fn delta_debugging<F>(&self, elements: &[usize], apply: &F, original: &Module) -> Vec<usize>
    where
        F: Fn(&Module, &[usize]) -> Module,
    {
        if elements.len() <= 1 {
            return elements.to_vec();
        }

        // Try removing the first half
        let mid = elements.len() / 2;
        let first_half = &elements[..mid];
        let second_half = &elements[mid..];

        // Test with first half removed
        let test = apply(original, second_half);
        if self.is_still_interesting(&test) {
            return self.delta_debugging(second_half, apply, original);
        }

        // Test with second half removed
        let test = apply(original, first_half);
        if self.is_still_interesting(&test) {
            return self.delta_debugging(first_half, apply, original);
        }

        // Need both halves — recursively reduce each
        let mut result = self.delta_debugging(
            first_half,
            &|m: &Module, els: &[usize]| -> Module {
                let mut combined = apply(m, els);
                combined
            },
            original,
        );
        result.extend(self.delta_debugging(
            second_half,
            &|m: &Module, els: &[usize]| -> Module {
                let mut combined = apply(m, &result);
                combined
            },
            original,
        ));
        result.sort();
        result.dedup();
        result
    }

    /// Run all reduction strategies in parallel, interleaving attempts.
    /// Returns the total number of reductions performed.
    pub fn reduce_parallel(&mut self, module: &mut Module) -> usize {
        let strategies: Vec<(&str, fn(&mut LLVMReduce, &mut Module))> = vec![
            ("functions", LLVMReduce::reduce_functions),
            ("blocks", LLVMReduce::reduce_blocks),
            ("instructions", LLVMReduce::reduce_instructions),
            ("metadata", LLVMReduce::reduce_metadata),
            ("globals", LLVMReduce::reduce_globals),
            ("args", LLVMReduce::reduce_args),
            ("operands", LLVMReduce::reduce_operands_wrapper),
            ("attributes", LLVMReduce::reduce_attributes_wrapper),
        ];

        let mut total_reductions = 0;
        let mut progress = true;

        while progress {
            progress = false;
            for (_name, strategy) in &strategies {
                let before = self.count_instructions(module);
                strategy(self, module);
                let after = self.count_instructions(module);
                if after < before {
                    total_reductions += 1;
                    progress = true;
                }
            }
        }

        total_reductions
    }

    /// Reduce with a custom interestingness test from a closure.
    pub fn reduce_with_test<F>(&mut self, module: &mut Module, test_fn: F) -> usize
    where
        F: Fn(&Module) -> bool + 'static,
    {
        let old_fn = std::mem::replace(&mut self.is_interesting_fn, Box::new(test_fn));
        let result = self.reduce_parallel(module);
        drop(old_fn);
        result
    }

    /// Get statistics about the reduction process.
    pub fn reduction_stats(&self) -> ReductionStats {
        ReductionStats {
            original_size: self.original_size,
            reduced_size: self.reduced_size,
            reduction_percentage: if self.original_size > 0 {
                ((self.original_size - self.reduced_size) as f64 / self.original_size as f64)
                    * 100.0
            } else {
                0.0
            },
            passes_run: self.passes_to_test.len(),
        }
    }
}

/// Statistics from the reduction process.
#[derive(Debug, Clone)]
pub struct ReductionStats {
    pub original_size: usize,
    pub reduced_size: usize,
    pub reduction_percentage: f64,
    pub passes_run: usize,
}

// ============================================================================
// Tests
// ============================================================================

#[cfg(test)]
mod tests {
    use super::*;
    use llvm_native_core::value::{valref, Value};

    fn make_module() -> Module {
        Module::new("test_module")
    }

    fn always_interesting(_: &Module) -> bool {
        true
    }

    fn never_interesting(_: &Module) -> bool {
        false
    }

    #[test]
    fn test_create_reduce() {
        let reduce = LLVMReduce::new(Box::new(always_interesting));
        assert_eq!(reduce.original_size, 0);
        assert_eq!(reduce.reduced_size, 0);
        assert!(reduce.passes_to_test.is_empty());
    }

    #[test]
    fn test_is_still_interesting() {
        let reduce = LLVMReduce::new(Box::new(always_interesting));
        let module = make_module();
        assert!(reduce.is_still_interesting(&module));
    }

    #[test]
    fn test_is_not_interesting() {
        let reduce = LLVMReduce::new(Box::new(never_interesting));
        let module = make_module();
        assert!(!reduce.is_still_interesting(&module));
    }

    #[test]
    fn test_count_instructions_empty() {
        let reduce = LLVMReduce::new(Box::new(always_interesting));
        let module = make_module();
        assert_eq!(reduce.count_instructions(&module), 0);
    }

    #[test]
    fn test_count_instructions_with_insts() {
        let reduce = LLVMReduce::new(Box::new(always_interesting));
        let mut module = make_module();

        let inst = {
            let mut v =
                Value::new(llvm_native_core::types::Type::void()).with_subclass(SubclassKind::Instruction);
            v.name = "inst".into();
            valref(v)
        };

        let mut bb =
            Value::new(llvm_native_core::types::Type::label()).with_subclass(SubclassKind::BasicBlock);
        bb.operands = vec![inst];
        let bb_ref = valref(bb);

        let mut func = Value::new(llvm_native_core::types::Type::void());
        func.subclass = SubclassKind::Function;
        func.operands = vec![bb_ref];
        let func_ref = valref(func);

        module.functions.push(func_ref);

        assert_eq!(reduce.count_instructions(&module), 1);
    }

    #[test]
    fn test_reduce_empty_module() {
        let mut reduce = LLVMReduce::new(Box::new(always_interesting));
        let mut module = make_module();
        reduce.reduce(&mut module);
        assert_eq!(reduce.original_size, 0);
        assert_eq!(reduce.reduced_size, 0);
    }

    #[test]
    fn test_reduce_functions_none_removable() {
        let mut reduce = LLVMReduce::new(Box::new(never_interesting));
        let mut module = make_module();

        let func = {
            let mut v = Value::new(llvm_native_core::types::Type::void());
            v.subclass = SubclassKind::Function;
            v.name = "test_func".into();
            valref(v)
        };
        module.functions.push(func);

        reduce.reduce_functions(&mut module);
        assert_eq!(module.functions.len(), 1);
    }

    #[test]
    fn test_reduce_functions_all_removable() {
        let mut reduce = LLVMReduce::new(Box::new(always_interesting));
        let mut module = make_module();

        let func = {
            let mut v = Value::new(llvm_native_core::types::Type::void());
            v.subclass = SubclassKind::Function;
            v.name = "test_func".into();
            valref(v)
        };
        module.functions.push(func);

        reduce.reduce_functions(&mut module);
        assert_eq!(module.functions.len(), 0);
    }

    #[test]
    fn test_reduce_globals() {
        let mut reduce = LLVMReduce::new(Box::new(always_interesting));
        let mut module = make_module();

        let global = {
            let mut v = Value::new(llvm_native_core::types::Type::i32());
            v.subclass = SubclassKind::GlobalVariable;
            v.name = "g".into();
            valref(v)
        };
        module.globals.push(global);

        reduce.reduce_globals(&mut module);
        assert_eq!(module.globals.len(), 0);
    }

    #[test]
    fn test_reduce_metadata_empty() {
        let mut reduce = LLVMReduce::new(Box::new(always_interesting));
        let mut module = make_module();
        reduce.reduce_metadata(&mut module);
    }

    #[test]
    fn test_reduce_args_no_functions() {
        let mut reduce = LLVMReduce::new(Box::new(always_interesting));
        let mut module = make_module();
        reduce.reduce_args(&mut module);
    }

    #[test]
    fn test_try_all_strategies() {
        let mut reduce = LLVMReduce::new(Box::new(always_interesting));
        let mut module = make_module();
        for strategy in &[
            ReduceStrategy::Functions,
            ReduceStrategy::Blocks,
            ReduceStrategy::Instructions,
            ReduceStrategy::Metadata,
            ReduceStrategy::Globals,
            ReduceStrategy::Args,
        ] {
            reduce.try_reduce_strategy(&mut module, *strategy);
        }
    }

    #[test]
    fn test_reduce_preserves_interesting_property() {
        let called = std::rc::Rc::new(std::cell::Cell::new(false));
        let called_clone = called.clone();
        let reduce = LLVMReduce::new(Box::new(move |_: &Module| {
            called_clone.set(true);
            true
        }));
        let module = make_module();
        assert!(reduce.is_still_interesting(&module));
        assert!(called.get());
    }
}