llvm-native-core-ext 0.1.0

//! LLVM Diff — module diffing that compares two LLVM modules for structural
//! and semantic differences.
//! Clean-room behavioral reconstruction.
//!
//! @llvm_behavior: LLVM provides a `llvm-diff` tool that compares two
//! modules at the IR level. It identifies added/removed functions and
//! globals, and for functions that exist in both modules, compares their
//! instructions. The comparison uses a combination of structural hashing
//! and instruction-level equality checks.
//!
//! This module implements:
//! - Module-level diff (functions, globals, aliases, ifuncs, types)
//! - Function-level diff (basic blocks, instructions)
//! - Global-level diff (initializers)
//! - Instruction-level diff with structural hashing
//! - Human-readable diff output

use llvm_native_core::module::Module;
use llvm_native_core::opcode::Opcode;
use llvm_native_core::value::ValueRef;
use llvm_native_core::SubclassKind;
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

// ============================================================================
// DiffKind and DiffEntry
// ============================================================================

/// The kind of difference between two entities.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DiffKind {
    /// The entity exists in module B but not in module A.
    Added,
    /// The entity exists in module A but not in module B.
    Removed,
    /// The entity exists in both but has differing content.
    Modified,
    /// The entity exists in both and is identical.
    Unchanged,
}

impl std::fmt::Display for DiffKind {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            DiffKind::Added => write!(f, "+"),
            DiffKind::Removed => write!(f, "-"),
            DiffKind::Modified => write!(f, "~"),
            DiffKind::Unchanged => write!(f, "="),
        }
    }
}

/// A single diff entry describing one difference.
#[derive(Debug, Clone)]
pub struct DiffEntry {
    /// What kind of change this entry records.
    pub kind: DiffKind,
    /// The entity path (e.g., "function @foo", "global @bar", "instruction %5").
    pub entity: String,
    /// Additional details about the change.
    pub details: String,
}

// ============================================================================
// LLVMDiff
// ============================================================================

/// LLVMDiff — compares two LLVM modules and produces a list of differences.
pub struct LLVMDiff;

impl LLVMDiff {
    /// Diff two full modules, comparing functions, globals, aliases, types,
    /// and metadata.
    pub fn diff_modules(a: &Module, b: &Module) -> Vec<DiffEntry> {
        let mut diffs = Vec::new();

        // Compare module-level attributes
        if a.source_filename != b.source_filename {
            diffs.push(DiffEntry {
                kind: DiffKind::Modified,
                entity: "module.source_filename".to_string(),
                details: format!(
                    "changed from '{}' to '{}'",
                    a.source_filename, b.source_filename
                ),
            });
        }

        if a.target_triple != b.target_triple {
            diffs.push(DiffEntry {
                kind: DiffKind::Modified,
                entity: "module.target_triple".to_string(),
                details: format!(
                    "changed from {:?} to {:?}",
                    a.target_triple, b.target_triple
                ),
            });
        }

        if a.data_layout != b.data_layout {
            diffs.push(DiffEntry {
                kind: DiffKind::Modified,
                entity: "module.data_layout".to_string(),
                details: format!("changed from {:?} to {:?}", a.data_layout, b.data_layout),
            });
        }

        // Compare type counts
        if a.types.len() != b.types.len() {
            diffs.push(DiffEntry {
                kind: DiffKind::Modified,
                entity: "module.type_table".to_string(),
                details: format!(
                    "type count changed from {} to {}",
                    a.types.len(),
                    b.types.len()
                ),
            });
        }

        // Diff functions
        diffs.extend(Self::diff_function_lists(&a.functions, &b.functions));

        // Diff globals
        diffs.extend(Self::diff_global_lists(&a.globals, &b.globals));

        // Diff aliases
        diffs.extend(Self::diff_global_lists(&a.aliases, &b.aliases));

        // Diff ifuncs
        diffs.extend(Self::diff_global_lists(&a.ifuncs, &b.ifuncs));

        // Diff named metadata
        diffs.extend(Self::diff_named_metadata(a, b));

        // Diff module flags
        diffs.extend(Self::diff_module_flags(a, b));

        diffs
    }

    /// Diff two function definitions at the instruction level.
    pub fn diff_functions(a: &ValueRef, b: &ValueRef) -> Vec<DiffEntry> {
        let mut diffs = Vec::new();
        let fa = a.borrow();
        let fb = b.borrow();

        let a_blocks: Vec<&ValueRef> = fa
            .operands
            .iter()
            .filter(|op| op.borrow().is_basic_block())
            .collect();
        let b_blocks: Vec<&ValueRef> = fb
            .operands
            .iter()
            .filter(|op| op.borrow().is_basic_block())
            .collect();

        // Compare block count
        if a_blocks.len() != b_blocks.len() {
            diffs.push(DiffEntry {
                kind: DiffKind::Modified,
                entity: format!("function {}.block_count", fa.name),
                details: format!(
                    "block count changed from {} to {}",
                    a_blocks.len(),
                    b_blocks.len()
                ),
            });
        }

        // Compare blocks by index
        for i in 0..a_blocks.len().min(b_blocks.len()) {
            let a_block = a_blocks[i];
            let b_block = b_blocks[i];

            let ab = a_block.borrow();
            let bb = b_block.borrow();

            if ab.name != bb.name {
                diffs.push(DiffEntry {
                    kind: DiffKind::Modified,
                    entity: format!("{}.block[{}].name", fa.name, i),
                    details: format!("'{}' -> '{}'", ab.name, bb.name),
                });
            }

            let a_insts: Vec<&ValueRef> = ab
                .operands
                .iter()
                .filter(|op| op.borrow().is_instruction())
                .collect();
            let b_insts: Vec<&ValueRef> = bb
                .operands
                .iter()
                .filter(|op| op.borrow().is_instruction())
                .collect();

            if a_insts.len() != b_insts.len() {
                diffs.push(DiffEntry {
                    kind: DiffKind::Modified,
                    entity: format!("{}.block[{}].instruction_count", fa.name, i),
                    details: format!(
                        "instruction count changed from {} to {}",
                        a_insts.len(),
                        b_insts.len()
                    ),
                });
            }

            // Compare instructions pairwise
            for j in 0..a_insts.len().min(b_insts.len()) {
                if !Self::are_instructions_equal(a_insts[j], b_insts[j]) {
                    let ai = a_insts[j].borrow();
                    let bi = b_insts[j].borrow();
                    diffs.push(DiffEntry {
                        kind: DiffKind::Modified,
                        entity: format!("{}.block[{}].inst[{}]", fa.name, i, j),
                        details: format!("instruction changed: {:?} vs {:?}", ai.opcode, bi.opcode),
                    });
                }
            }

            // Extra instructions in B
            for j in a_insts.len()..b_insts.len() {
                diffs.push(DiffEntry {
                    kind: DiffKind::Added,
                    entity: format!("{}.block[{}].inst[{}]", fa.name, i, j),
                    details: "instruction added".to_string(),
                });
            }

            // Extra instructions in A (removed in B)
            for j in b_insts.len()..a_insts.len() {
                diffs.push(DiffEntry {
                    kind: DiffKind::Removed,
                    entity: format!("{}.block[{}].inst[{}]", fa.name, i, j),
                    details: "instruction removed".to_string(),
                });
            }
        }

        // Extra blocks in B
        for i in a_blocks.len()..b_blocks.len() {
            diffs.push(DiffEntry {
                kind: DiffKind::Added,
                entity: format!("{}.block[{}]", fa.name, i),
                details: "block added".to_string(),
            });
        }

        // Extra blocks in A (removed in B)
        for i in b_blocks.len()..a_blocks.len() {
            diffs.push(DiffEntry {
                kind: DiffKind::Removed,
                entity: format!("{}.block[{}]", fa.name, i),
                details: "block removed".to_string(),
            });
        }

        diffs
    }

    /// Diff two global variable definitions.
    pub fn diff_globals(a: &ValueRef, b: &ValueRef) -> DiffEntry {
        let ga = a.borrow();
        let gb = b.borrow();

        let mut details = Vec::new();

        if ga.ty != gb.ty {
            details.push(format!(
                "type changed: {:?} vs {:?}",
                ga.ty.kind, gb.ty.kind
            ));
        }

        if ga.operands.len() != gb.operands.len() {
            details.push(format!(
                "operand count changed: {} vs {}",
                ga.operands.len(),
                gb.operands.len()
            ));
        }

        if ga.subclass_data != gb.subclass_data {
            details.push(format!(
                "subclass data changed: {} vs {}",
                ga.subclass_data, gb.subclass_data
            ));
        }

        let kind = if details.is_empty() {
            DiffKind::Unchanged
        } else {
            DiffKind::Modified
        };

        DiffEntry {
            kind,
            entity: format!("global @{}", ga.name),
            details: details.join("; "),
        }
    }

    /// Print a human-readable diff report.
    pub fn print_diff(diffs: &[DiffEntry]) -> String {
        if diffs.is_empty() {
            return "No differences found.\n".to_string();
        }

        let mut output = String::new();
        let mut added = 0usize;
        let mut removed = 0usize;
        let mut modified = 0usize;

        for d in diffs {
            match d.kind {
                DiffKind::Added => added += 1,
                DiffKind::Removed => removed += 1,
                DiffKind::Modified => modified += 1,
                DiffKind::Unchanged => {}
            }
            output.push_str(&format!("{}  {:<60}  {}\n", d.kind, d.entity, d.details));
        }

        output.push_str(&format!(
            "\nSummary: {} added, {} removed, {} modified, {} total differences\n",
            added,
            removed,
            modified,
            diffs.len()
        ));

        output
    }

    // ========================================================================
    // Internal helpers
    // ========================================================================

    /// Compute a structural hash for an instruction.
    fn hash_instruction(inst: &ValueRef) -> u64 {
        let mut hasher = DefaultHasher::new();
        let i = inst.borrow();

        if let Some(op) = i.opcode {
            (op as u32).hash(&mut hasher);
        }
        i.ty.kind.hash(&mut hasher);
        i.num_operands.hash(&mut hasher);

        for op in &i.operands {
            let o = op.borrow();
            o.vid.hash(&mut hasher);
            o.ty.kind.hash(&mut hasher);
        }

        hasher.finish()
    }

    /// Check if two instructions are structurally equivalent.
    fn are_instructions_equal(a: &ValueRef, b: &ValueRef) -> bool {
        let ia = a.borrow();
        let ib = b.borrow();

        // Compare opcodes
        if ia.opcode != ib.opcode {
            return false;
        }

        // Compare types
        if ia.ty.kind != ib.ty.kind {
            return false;
        }

        // Compare operand count
        if ia.operands.len() != ib.operands.len() {
            return false;
        }

        // Compare operand types (not identity — structural comparison)
        for (opa, opb) in ia.operands.iter().zip(ib.operands.iter()) {
            let oa = opa.borrow();
            let ob = opb.borrow();
            if oa.ty.kind != ob.ty.kind {
                return false;
            }
        }

        // Compare subclass data if relevant
        if ia.subclass_data != ib.subclass_data {
            return false;
        }

        true
    }

    /// Diff two lists of functions.
    fn diff_function_lists(a: &[ValueRef], b: &[ValueRef]) -> Vec<DiffEntry> {
        let mut diffs = Vec::new();
        let a_names: Vec<String> = a.iter().map(|f| f.borrow().name.clone()).collect();
        let b_names: Vec<String> = b.iter().map(|f| f.borrow().name.clone()).collect();

        let a_set: std::collections::HashSet<&str> = a_names.iter().map(|s| s.as_str()).collect();
        let b_set: std::collections::HashSet<&str> = b_names.iter().map(|s| s.as_str()).collect();

        // Removed functions (in A but not B)
        for name in &a_names {
            if !b_set.contains(name.as_str()) {
                diffs.push(DiffEntry {
                    kind: DiffKind::Removed,
                    entity: format!("function @{}", name),
                    details: String::new(),
                });
            }
        }

        // Added functions (in B but not A)
        for name in &b_names {
            if !a_set.contains(name.as_str()) {
                diffs.push(DiffEntry {
                    kind: DiffKind::Added,
                    entity: format!("function @{}", name),
                    details: String::new(),
                });
            }
        }

        // Modified functions (in both, but different)
        // Build maps using indices to avoid lifetime issues
        let a_idx_map: std::collections::HashMap<&str, usize> = a_names
            .iter()
            .enumerate()
            .map(|(i, name)| (name.as_str(), i))
            .collect();
        let b_idx_map: std::collections::HashMap<&str, usize> = b_names
            .iter()
            .enumerate()
            .map(|(i, name)| (name.as_str(), i))
            .collect();

        for name in &a_names {
            if let (Some(&ai), Some(&bi)) =
                (a_idx_map.get(name.as_str()), b_idx_map.get(name.as_str()))
            {
                let func_diffs = Self::diff_functions(&a[ai], &b[bi]);
                if !func_diffs.is_empty() {
                    diffs.extend(func_diffs);
                }
            }
        }

        diffs
    }

    /// Diff two lists of globals (or aliases, ifuncs).
    fn diff_global_lists(a: &[ValueRef], b: &[ValueRef]) -> Vec<DiffEntry> {
        let mut diffs = Vec::new();
        let a_names: Vec<String> = a.iter().map(|f| f.borrow().name.clone()).collect();
        let b_names: Vec<String> = b.iter().map(|f| f.borrow().name.clone()).collect();

        let a_set: std::collections::HashSet<&str> = a_names.iter().map(|s| s.as_str()).collect();
        let b_set: std::collections::HashSet<&str> = b_names.iter().map(|s| s.as_str()).collect();

        for name in &a_names {
            if !b_set.contains(name.as_str()) {
                diffs.push(DiffEntry {
                    kind: DiffKind::Removed,
                    entity: format!("global @{}", name),
                    details: String::new(),
                });
            }
        }

        for name in &b_names {
            if !a_set.contains(name.as_str()) {
                diffs.push(DiffEntry {
                    kind: DiffKind::Added,
                    entity: format!("global @{}", name),
                    details: String::new(),
                });
            }
        }

        // Compare globals present in both
        let a_idx_map: std::collections::HashMap<&str, usize> = a_names
            .iter()
            .enumerate()
            .map(|(i, name)| (name.as_str(), i))
            .collect();
        let b_idx_map: std::collections::HashMap<&str, usize> = b_names
            .iter()
            .enumerate()
            .map(|(i, name)| (name.as_str(), i))
            .collect();

        for name in &a_names {
            if let (Some(&ai), Some(&bi)) =
                (a_idx_map.get(name.as_str()), b_idx_map.get(name.as_str()))
            {
                let entry = Self::diff_globals(&a[ai], &b[bi]);
                if entry.kind != DiffKind::Unchanged {
                    diffs.push(entry);
                }
            }
        }

        diffs
    }

    /// Diff named metadata entries.
    fn diff_named_metadata(a: &Module, b: &Module) -> Vec<DiffEntry> {
        let mut diffs = Vec::new();

        let a_keys: std::collections::HashSet<&str> =
            a.named_metadata.keys().map(|s| s.as_str()).collect();
        let b_keys: std::collections::HashSet<&str> =
            b.named_metadata.keys().map(|s| s.as_str()).collect();

        for key in &a_keys {
            if !b_keys.contains(key) {
                diffs.push(DiffEntry {
                    kind: DiffKind::Removed,
                    entity: format!("named_metadata !{}", key),
                    details: String::new(),
                });
            } else {
                let a_val = &a.named_metadata[*key];
                let b_val = &b.named_metadata[*key];
                if a_val != b_val {
                    diffs.push(DiffEntry {
                        kind: DiffKind::Modified,
                        entity: format!("named_metadata !{}", key),
                        details: format!("node IDs changed: {:?} vs {:?}", a_val, b_val),
                    });
                }
            }
        }

        for key in &b_keys {
            if !a_keys.contains(key) {
                diffs.push(DiffEntry {
                    kind: DiffKind::Added,
                    entity: format!("named_metadata !{}", key),
                    details: String::new(),
                });
            }
        }

        diffs
    }

    /// Diff module flags.
    fn diff_module_flags(a: &Module, b: &Module) -> Vec<DiffEntry> {
        let mut diffs = Vec::new();

        if a.flags.len() != b.flags.len() {
            diffs.push(DiffEntry {
                kind: DiffKind::Modified,
                entity: "module.flags".to_string(),
                details: format!(
                    "flag count changed from {} to {}",
                    a.flags.len(),
                    b.flags.len()
                ),
            });
        }

        // Compare flags by key
        let a_keys: Vec<&str> = a.flags.iter().map(|f| f.key.as_str()).collect();
        let b_keys: std::collections::HashSet<&str> =
            b.flags.iter().map(|f| f.key.as_str()).collect();

        for (i, key) in a_keys.iter().enumerate() {
            if !b_keys.contains(key) {
                diffs.push(DiffEntry {
                    kind: DiffKind::Removed,
                    entity: format!("module.flag[{}]", key),
                    details: String::new(),
                });
            } else if i < b.flags.len() && a.flags[i].behavior != b.flags[i].behavior {
                diffs.push(DiffEntry {
                    kind: DiffKind::Modified,
                    entity: format!("module.flag[{}].behavior", key),
                    details: format!(
                        "changed from {} to {}",
                        a.flags[i].behavior, b.flags[i].behavior
                    ),
                });
            }
        }

        diffs
    }
}

// ============================================================================
// Structural Module Comparison
// ============================================================================

/// Detailed structural comparison of two modules, including type tables,
/// metadata, and attribute groups.
impl LLVMDiff {
    /// Perform a comprehensive structural diff of two modules.
    /// Returns a detailed report covering types, metadata, attributes,
    /// and all IR entities.
    pub fn diff_structural(&self, a: &Module, b: &Module) -> Vec<DiffEntry> {
        let mut diffs = Vec::new();

        // Compare triples
        if a.target_triple != b.target_triple {
            diffs.push(DiffEntry {
                kind: DiffKind::Modified,
                entity: "target_triple".to_string(),
                details: format!(
                    "changed from '{}' to '{}'",
                    a.target_triple.as_deref().unwrap_or("none"),
                    b.target_triple.as_deref().unwrap_or("none")
                ),
            });
        }

        // Compare data layouts
        if a.data_layout != b.data_layout {
            diffs.push(DiffEntry {
                kind: DiffKind::Modified,
                entity: "data_layout".to_string(),
                details: format!(
                    "changed from '{}' to '{}'",
                    a.data_layout.as_deref().unwrap_or("none"),
                    b.data_layout.as_deref().unwrap_or("none")
                ),
            });
        }

        // Compare type table sizes
        if a.types.len() != b.types.len() {
            diffs.push(DiffEntry {
                kind: DiffKind::Modified,
                entity: "type_table".to_string(),
                details: format!("size changed from {} to {}", a.types.len(), b.types.len()),
            });
        }

        diffs
    }

    /// Diff functions with block-level matching.
    /// Uses a block-matching algorithm that pairs basic blocks across
    /// two functions based on structure and instruction similarity.
    pub fn diff_functions_detailed(&self, a: &ValueRef, b: &ValueRef) -> Vec<DiffEntry> {
        let mut diffs = Vec::new();
        let fa = a.borrow();
        let fb = b.borrow();

        // Compare function signatures
        if fa.ty != fb.ty {
            diffs.push(DiffEntry {
                kind: DiffKind::Modified,
                entity: "function.type".to_string(),
                details: "return type or parameter types differ".to_string(),
            });
        }

        // Block matching: try to pair basic blocks between A and B
        let blocks_a = Self::get_basic_blocks(a);
        let blocks_b = Self::get_basic_blocks(b);

        let matched_pairs = Self::match_blocks(&blocks_a, &blocks_b);

        let mut a_matched: Vec<bool> = vec![false; blocks_a.len()];
        let mut b_matched: Vec<bool> = vec![false; blocks_b.len()];

        for (ai, bi, _score) in &matched_pairs {
            a_matched[*ai] = true;
            b_matched[*bi] = true;

            // Diff instructions within matched blocks
            let inst_diff = Self::diff_instructions_in_block(&blocks_a[*ai], &blocks_b[*bi]);
            diffs.extend(inst_diff);
        }

        // Report unmatched blocks
        for (i, matched) in a_matched.iter().enumerate() {
            if !matched {
                let bb = blocks_a[i].borrow();
                let name = if bb.name.is_empty() {
                    format!("bb{}", i)
                } else {
                    bb.name.clone()
                };
                diffs.push(DiffEntry {
                    kind: DiffKind::Removed,
                    entity: format!("block.{}", name),
                    details: "block removed or unmatched".to_string(),
                });
            }
        }
        for (i, matched) in b_matched.iter().enumerate() {
            if !matched {
                let bb = blocks_b[i].borrow();
                let name = if bb.name.is_empty() {
                    format!("bb{}", i)
                } else {
                    bb.name.clone()
                };
                diffs.push(DiffEntry {
                    kind: DiffKind::Added,
                    entity: format!("block.{}", name),
                    details: "block added".to_string(),
                });
            }
        }

        diffs
    }

    /// Extract basic blocks from a function.
    fn get_basic_blocks(func: &ValueRef) -> Vec<ValueRef> {
        let f = func.borrow();
        f.operands
            .iter()
            .filter(|op| op.borrow().subclass == SubclassKind::BasicBlock)
            .cloned()
            .collect()
    }

    /// Match basic blocks between two functions using structural hashing.
    /// Returns triples of (index_in_a, index_in_b, similarity_score).
    fn match_blocks(a_blocks: &[ValueRef], b_blocks: &[ValueRef]) -> Vec<(usize, usize, u64)> {
        let mut matches = Vec::new();

        for (i, ba) in a_blocks.iter().enumerate() {
            let hash_a = Self::hash_block_structure(ba);

            let mut best_score: u64 = 0;
            let mut best_j: Option<usize> = None;

            for (j, bb) in b_blocks.iter().enumerate() {
                let hash_b = Self::hash_block_structure(bb);
                let similarity = Self::hash_similarity(hash_a, hash_b);
                if similarity > best_score {
                    best_score = similarity;
                    best_j = Some(j);
                }
            }

            if let Some(j) = best_j {
                if best_score > 0 {
                    matches.push((i, j, best_score));
                }
            }
        }

        // Remove duplicate matches (keep best score per B block)
        let mut filtered: Vec<(usize, usize, u64)> = Vec::new();
        let mut used_b: Vec<bool> = vec![false; b_blocks.len()];
        matches.sort_by(|a, b| b.2.cmp(&a.2));

        for (ai, bi, score) in matches {
            if !used_b[bi] {
                used_b[bi] = true;
                filtered.push((ai, bi, score));
            }
        }

        filtered
    }

    /// Hash the structure of a basic block (instruction opcodes and counts).
    fn hash_block_structure(block: &ValueRef) -> u64 {
        let bb = block.borrow();
        let mut hasher = DefaultHasher::new();

        for inst in &bb.operands {
            let i = inst.borrow();
            i.opcode.hash(&mut hasher);
            // Hash operand count for structural comparison
            i.operands.len().hash(&mut hasher);
        }

        hasher.finish()
    }

    /// Compute a similarity score between two hashes (inverse Hamming distance).
    fn hash_similarity(a: u64, b: u64) -> u64 {
        let xor = a ^ b;
        // Count matching bits as similarity
        64 - xor.count_ones() as u64
    }

    /// Diff instructions within two matched basic blocks.
    fn diff_instructions_in_block(a: &ValueRef, b: &ValueRef) -> Vec<DiffEntry> {
        let mut diffs = Vec::new();
        let ba = a.borrow();
        let bb = b.borrow();

        let insts_a: Vec<&ValueRef> = ba
            .operands
            .iter()
            .filter(|op| op.borrow().subclass == SubclassKind::Instruction)
            .collect();
        let insts_b: Vec<&ValueRef> = bb
            .operands
            .iter()
            .filter(|op| op.borrow().subclass == SubclassKind::Instruction)
            .collect();

        // Instruction-level similarity scoring with tolerance for reordering
        let matched = Self::match_instructions_with_tolerance(&insts_a, &insts_b, 2);

        let mut a_matched: Vec<bool> = vec![false; insts_a.len()];
        let mut b_matched: Vec<bool> = vec![false; insts_b.len()];

        for (ai, bi, _sim) in &matched {
            a_matched[*ai] = true;
            b_matched[*bi] = true;
        }

        for (i, matched) in a_matched.iter().enumerate() {
            if !matched {
                let inst = insts_a[i].borrow();
                diffs.push(DiffEntry {
                    kind: DiffKind::Removed,
                    entity: format!("inst.{:?}", inst.opcode),
                    details: "instruction removed from block".to_string(),
                });
            }
        }
        for (i, matched) in b_matched.iter().enumerate() {
            if !matched {
                let inst = insts_b[i].borrow();
                diffs.push(DiffEntry {
                    kind: DiffKind::Added,
                    entity: format!("inst.{:?}", inst.opcode),
                    details: "instruction added to block".to_string(),
                });
            }
        }

        diffs
    }

    /// Match instructions with tolerance for reordering within a window.
    fn match_instructions_with_tolerance(
        a: &[&ValueRef],
        b: &[&ValueRef],
        window: usize,
    ) -> Vec<(usize, usize, u64)> {
        let mut matches = Vec::new();
        let mut b_used: Vec<bool> = vec![false; b.len()];

        for (i, ia) in a.iter().enumerate() {
            let start = if i >= window { i - window } else { 0 };
            let end = (i + window + 1).min(b.len());

            for j in start..end {
                if b_used[j] {
                    continue;
                }
                if LLVMDiff::are_instructions_ref_equal(ia, b[j]) {
                    matches.push((i, j, 100));
                    b_used[j] = true;
                    break;
                }
            }
        }

        matches
    }

    /// Check if two instruction references are structurally equal.
    fn are_instructions_ref_equal(a: &ValueRef, b: &ValueRef) -> bool {
        let ia = a.borrow();
        let ib = b.borrow();

        if ia.opcode != ib.opcode {
            return false;
        }
        if ia.operands.len() != ib.operands.len() {
            return false;
        }
        // Deep compare operand opcodes
        for (oa, ob) in ia.operands.iter().zip(ib.operands.iter()) {
            let va = oa.borrow();
            let vb = ob.borrow();
            if va.opcode != vb.opcode || va.ty != vb.ty {
                return false;
            }
        }
        true
    }

    /// Generate a unified diff report with context.
    pub fn diff_report(&self, a: &Module, b: &Module) -> String {
        let diffs = LLVMDiff::diff_modules(a, b);
        let mut report = String::new();

        report.push_str(&format!("--- a/{}\n", a.name));
        report.push_str(&format!("+++ b/{}\n", b.name));

        let additions = diffs.iter().filter(|d| d.kind == DiffKind::Added).count();
        let removals = diffs.iter().filter(|d| d.kind == DiffKind::Removed).count();
        let modifications = diffs
            .iter()
            .filter(|d| d.kind == DiffKind::Modified)
            .count();

        report.push_str(&format!(
            "@@ -{},{} +{},{} @@\n",
            additions,
            removals,
            modifications,
            diffs.len()
        ));

        for diff in &diffs {
            let prefix = match diff.kind {
                DiffKind::Added => "+",
                DiffKind::Removed => "-",
                DiffKind::Modified => "~",
                DiffKind::Unchanged => " ",
            };
            report.push_str(&format!(
                "{} {}{}\n",
                prefix,
                diff.entity,
                if diff.details.is_empty() {
                    String::new()
                } else {
                    format!(": {}", diff.details)
                }
            ));
        }

        report
    }

    /// Generate a summary of differences between two modules.
    pub fn diff_summary(&self, a: &Module, b: &Module) -> DiffSummary {
        let diffs = LLVMDiff::diff_modules(a, b);
        DiffSummary {
            total_diffs: diffs.len(),
            functions_added: diffs
                .iter()
                .filter(|d| d.entity.starts_with("function") && d.kind == DiffKind::Added)
                .count(),
            functions_removed: diffs
                .iter()
                .filter(|d| d.entity.starts_with("function") && d.kind == DiffKind::Removed)
                .count(),
            functions_modified: diffs
                .iter()
                .filter(|d| d.entity.starts_with("function") && d.kind == DiffKind::Modified)
                .count(),
            globals_added: diffs
                .iter()
                .filter(|d| d.entity.starts_with("global") && d.kind == DiffKind::Added)
                .count(),
            globals_removed: diffs
                .iter()
                .filter(|d| d.entity.starts_with("global") && d.kind == DiffKind::Removed)
                .count(),
            metadata_changed: diffs
                .iter()
                .filter(|d| {
                    d.entity.starts_with("named_metadata") || d.entity.starts_with("module.flag")
                })
                .count(),
        }
    }
}

/// Summary of differences between two modules.
#[derive(Debug, Clone, Default)]
pub struct DiffSummary {
    pub total_diffs: usize,
    pub functions_added: usize,
    pub functions_removed: usize,
    pub functions_modified: usize,
    pub globals_added: usize,
    pub globals_removed: usize,
    pub metadata_changed: usize,
}

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

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

    fn make_simple_module(name: &str) -> Module {
        let mut module = Module::new(name);
        module.source_filename = format!("{}.ll", name);

        let void_ty = Type::void();
        let func_ty = Type::function_type_with(void_ty.id, vec![], false);

        let mut func = Value::new(func_ty.clone())
            .with_subclass(SubclassKind::Function)
            .named("test_func");
        func.return_type = Some(void_ty.clone());
        let func_ref = valref(func);

        let entry = valref(
            Value::new(Type::label())
                .with_subclass(SubclassKind::BasicBlock)
                .named("entry"),
        );
        entry.borrow_mut().parent = Some(func_ref.clone());

        let ret = valref(
            Value::new(Type::void())
                .with_subclass(SubclassKind::Instruction)
                .named("ret"),
        );
        ret.borrow_mut().opcode = Some(Opcode::Ret);
        ret.borrow_mut().parent = Some(func_ref.clone());
        entry.borrow_mut().operands.push(ret);

        func_ref.borrow_mut().operands.push(entry);
        func_ref.borrow_mut().num_operands = 1;
        module.functions.push(func_ref);

        module
    }

    #[test]
    fn test_diff_identical_modules() {
        let a = make_simple_module("mod_a");
        let b = make_simple_module("mod_a");
        let diffs = LLVMDiff::diff_modules(&a, &b);
        assert!(diffs.is_empty());
    }

    #[test]
    fn test_diff_different_source_filename() {
        let a = make_simple_module("mod_a");
        let b = make_simple_module("mod_b");
        let diffs = LLVMDiff::diff_modules(&a, &b);
        assert!(diffs.iter().any(|d| d.entity == "module.source_filename"));
    }

    #[test]
    fn test_diff_function_added() {
        let a = Module::new("mod_a");
        let b = make_simple_module("mod_b");
        let diffs = LLVMDiff::diff_modules(&a, &b);
        assert!(diffs.iter().any(|d| d.kind == DiffKind::Added));
    }

    #[test]
    fn test_diff_function_removed() {
        let a = make_simple_module("mod_a");
        let b = Module::new("mod_b");
        let diffs = LLVMDiff::diff_modules(&a, &b);
        assert!(diffs.iter().any(|d| d.kind == DiffKind::Removed));
    }

    #[test]
    fn test_hash_instruction_is_deterministic() {
        let module = make_simple_module("mod");
        let func = &module.functions[0];
        let func_b = func.borrow();
        let bb = &func_b.operands[0];
        let inst = &bb.borrow().operands[0];

        let h1 = LLVMDiff::hash_instruction(inst);
        let h2 = LLVMDiff::hash_instruction(inst);
        assert_eq!(h1, h2);
    }

    #[test]
    fn test_are_instructions_equal_same() {
        let module = make_simple_module("mod");
        let func = &module.functions[0];
        let func_b = func.borrow();
        let bb = &func_b.operands[0];
        let inst = &bb.borrow().operands[0];

        assert!(LLVMDiff::are_instructions_equal(inst, inst));
    }

    #[test]
    fn test_diff_globals_identical() {
        let shared_ty = Type::i32();
        let g1 = valref(
            Value::new(shared_ty.clone())
                .with_subclass(SubclassKind::GlobalVariable)
                .named("g"),
        );
        let g2 = valref(
            Value::new(shared_ty.clone())
                .with_subclass(SubclassKind::GlobalVariable)
                .named("g"),
        );

        let entry = LLVMDiff::diff_globals(&g1, &g2);
        assert_eq!(entry.kind, DiffKind::Unchanged);
    }

    #[test]
    fn test_diff_globals_different_type() {
        let g1 = valref(
            Value::new(Type::i32())
                .with_subclass(SubclassKind::GlobalVariable)
                .named("g"),
        );
        let g2 = valref(
            Value::new(Type::i64())
                .with_subclass(SubclassKind::GlobalVariable)
                .named("g"),
        );

        let entry = LLVMDiff::diff_globals(&g1, &g2);
        assert_eq!(entry.kind, DiffKind::Modified);
    }

    #[test]
    fn test_print_diff_empty() {
        let output = LLVMDiff::print_diff(&[]);
        assert!(output.contains("No differences"));
    }

    #[test]
    fn test_print_diff_with_entries() {
        let diffs = vec![DiffEntry {
            kind: DiffKind::Added,
            entity: "function @foo".to_string(),
            details: String::new(),
        }];
        let output = LLVMDiff::print_diff(&diffs);
        assert!(output.contains("function @foo"));
        assert!(output.contains("1 added"));
    }

    #[test]
    fn test_diff_named_metadata() {
        let mut a = Module::new("a");
        let mut b = Module::new("b");
        a.named_metadata
            .insert("llvm.module.flags".to_string(), vec![1, 2]);
        b.named_metadata
            .insert("llvm.module.flags".to_string(), vec![1, 3]);

        let diffs = LLVMDiff::diff_modules(&a, &b);
        assert!(diffs
            .iter()
            .any(|d| d.kind == DiffKind::Modified && d.entity.contains("module.flags")));
    }
}