llvm-native-core-ext 0.1.0

//! LLVM Extract — function/global extraction tool that extracts specified
//! functions or globals into a new module, automatically including their
//! transitive dependencies.
//! Clean-room behavioral reconstruction.
//!
//! @llvm_behavior: `llvm-extract` is an LLVM utility that extracts one or
//! more functions from an LLVM module into a new module. It copies the
//! named functions, clones all transitively referenced callees, copies
//! any referenced global variables, and strips debug metadata. The
//! resulting module is self-contained and passes verification.
//!
//! Key operations:
//! - Extract by function name, global name, or regex pattern
//! - Auto-include transitive callees and referenced globals
//! - Strip debug info for a compact output
//! - Preserve types, attributes, and module flags

use llvm_native_core::module::Module;
use llvm_native_core::opcode::Opcode;
use llvm_native_core::value::{valref, SubclassKind, Value, ValueRef};
use std::collections::{HashMap, HashSet};

// ============================================================================
// LLVMExtract
// ============================================================================

/// LLVMExtract — extracts specified entities from an LLVM module into a
/// new self-contained module.
pub struct LLVMExtract;

impl LLVMExtract {
    /// Extract the named functions and their transitive dependencies into
    /// a new module.
    ///
    /// Walks the call graph starting from `names` and includes every
    /// callee that is defined in the source module. Also copies globals
    /// referenced by the extracted functions.
    pub fn extract_functions(module: &Module, names: &[String]) -> Module {
        let all_funcs = Self::find_transitive_callees(module, names);
        let all_globals = Self::find_referenced_globals(module, &all_funcs);

        let mut extracted = Self::clone_with_dependencies(module, &all_funcs);

        // Copy only the referenced globals
        extracted.globals.clear();
        for g in &module.globals {
            let gname = g.borrow().name.clone();
            if all_globals.contains(&gname) {
                let cloned = Self::clone_global(g);
                extracted.globals.push(cloned);
            }
        }

        // Copy aliases and ifuncs that point to extracted globals/functions
        for alias in &module.aliases {
            let aname = alias.borrow().name.clone();
            if all_funcs.contains(&aname) || all_globals.contains(&aname) {
                extracted.aliases.push(Self::clone_global(alias));
            }
        }

        Self::strip_debug_info(&mut extracted);

        extracted
    }

    /// Extract the named global variables into a new module.
    pub fn extract_globals(module: &Module, names: &[String]) -> Module {
        let mut extracted = Module::new(&format!("extracted_globals_from_{}", module.name));

        extracted.source_filename = module.source_filename.clone();
        extracted.target_triple = module.target_triple.clone();
        extracted.data_layout = module.data_layout.clone();

        // Copy types
        extracted.types = module.types.clone();
        extracted.named_types = module.named_types.clone();

        // Copy only matching globals
        let name_set: HashSet<&str> = names.iter().map(|s| s.as_str()).collect();
        for g in &module.globals {
            let gname = g.borrow().name.clone();
            if name_set.contains(gname.as_str()) {
                let cloned = Self::clone_global(g);
                extracted.globals.push(cloned);
            }
        }

        // Copy aliases/ifuncs referencing extracted globals
        for alias in &module.aliases {
            let aname = alias.borrow().name.clone();
            if name_set.contains(aname.as_str()) {
                extracted.aliases.push(Self::clone_global(alias));
            }
        }

        // Copy module flags
        extracted.flags = module.flags.clone();
        extracted.attr_groups = module.attr_groups.clone();
        extracted.comdats = module.comdats.clone();

        Self::strip_debug_info(&mut extracted);

        extracted
    }

    /// Extract functions and globals whose names match a regex pattern.
    ///
    /// Uses simple substring / prefix matching since Rust's stdlib does not
    /// include a regex engine. For production use a crate like `regex`
    /// would be linked.
    pub fn extract_by_regex(module: &Module, pattern: &str) -> Module {
        let mut selected_funcs: Vec<String> = Vec::new();

        for f in &module.functions {
            let name = f.borrow().name.clone();
            if Self::simple_match(&name, pattern) {
                selected_funcs.push(name);
            }
        }

        // Also include globals that match the pattern
        let mut selected_globals: Vec<String> = Vec::new();
        for g in &module.globals {
            let name = g.borrow().name.clone();
            if Self::simple_match(&name, pattern) {
                selected_globals.push(name);
            }
        }

        if selected_funcs.is_empty() && selected_globals.is_empty() {
            return Module::new(&format!("extracted_from_{}", module.name));
        }

        let mut result = if !selected_funcs.is_empty() {
            Self::extract_functions(module, &selected_funcs)
        } else {
            Module::new(&format!("extracted_from_{}", module.name))
        };

        // Merge globals extracted by name
        if !selected_globals.is_empty() {
            let glob_module = Self::extract_globals(module, &selected_globals);
            for g in glob_module.globals {
                // Avoid duplicates
                let name = g.borrow().name.clone();
                let already_present = result
                    .globals
                    .iter()
                    .any(|existing| existing.borrow().name == name);
                if !already_present {
                    result.globals.push(g);
                }
            }
        }

        result
    }

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

    /// Clone the selected functions and their dependencies into a new module.
    fn clone_with_dependencies(module: &Module, selected: &[String]) -> Module {
        let mut extracted = Module::new(&format!("extracted_{}", module.name));

        extracted.source_filename = module.source_filename.clone();
        extracted.target_triple = module.target_triple.clone();
        extracted.data_layout = module.data_layout.clone();

        // Copy types
        extracted.types = module.types.clone();
        extracted.named_types = module.named_types.clone();

        // Copy module flags
        extracted.flags = module.flags.clone();
        extracted.attr_groups = module.attr_groups.clone();
        extracted.comdats = module.comdats.clone();
        extracted.named_metadata = module.named_metadata.clone();

        let selected_set: HashSet<&str> = selected.iter().map(|s| s.as_str()).collect();

        // Copy selected functions
        for f in &module.functions {
            let fname = f.borrow().name.clone();
            if selected_set.contains(fname.as_str()) {
                let cloned = Self::clone_function_deep(f);
                extracted.functions.push(cloned);
            }
        }

        // Copy imported function declarations referenced by cloned code
        for imported in &module.imported_functions {
            if selected_set.contains(imported.as_str()) {
                if !extracted.imported_functions.contains(imported) {
                    extracted.imported_functions.push(imported.clone());
                }
            }
        }

        extracted
    }

    /// Find all functions transitively called from `funcs`.
    fn find_transitive_callees(module: &Module, funcs: &[String]) -> Vec<String> {
        let mut result: Vec<String> = funcs.to_vec();
        let mut visited: HashSet<String> = funcs.iter().cloned().collect();
        let mut queue: Vec<String> = funcs.to_vec();

        // Build a name→ValueRef lookup for fast access
        let func_map: HashMap<String, &ValueRef> = module
            .functions
            .iter()
            .map(|f| (f.borrow().name.clone(), f))
            .collect();

        while let Some(current) = queue.pop() {
            if let Some(func_ref) = func_map.get(&current) {
                let callees = Self::collect_callees(func_ref);
                for callee in callees {
                    if visited.insert(callee.clone()) {
                        result.push(callee.clone());
                        // Only traverse defined functions (not declarations)
                        if func_map.contains_key(&callee) {
                            queue.push(callee);
                        }
                    }
                }
            }
        }

        result
    }

    /// Collect all direct callee names from a function's instructions.
    fn collect_callees(func: &ValueRef) -> Vec<String> {
        let mut callees = Vec::new();
        let f = func.borrow();

        for operand in &f.operands {
            let bb = operand.borrow();
            if !bb.is_basic_block() {
                continue;
            }
            for inst in &bb.operands {
                let i = inst.borrow();
                if let Some(op) = i.opcode {
                    if matches!(op, Opcode::Call) {
                        // The first operand of a call is the function value
                        if let Some(target) = i.operands.first() {
                            let t = target.borrow();
                            if t.subclass == SubclassKind::Function {
                                callees.push(t.name.clone());
                            }
                        }
                    }
                }
            }
        }

        callees
    }

    /// Find all global variable names referenced by the given functions.
    fn find_referenced_globals(module: &Module, funcs: &[String]) -> Vec<String> {
        let mut globals = HashSet::new();
        let func_set: HashSet<&str> = funcs.iter().map(|s| s.as_str()).collect();

        for f in &module.functions {
            let fname = f.borrow().name.clone();
            if !func_set.contains(fname.as_str()) {
                continue;
            }
            let func = f.borrow();
            for operand in &func.operands {
                let bb = operand.borrow();
                if !bb.is_basic_block() {
                    continue;
                }
                for inst in &bb.operands {
                    let i = inst.borrow();
                    for op in &i.operands {
                        let o = op.borrow();
                        if o.subclass == SubclassKind::GlobalVariable {
                            globals.insert(o.name.clone());
                        }
                    }
                }
            }
        }

        // Also include globals referenced by initializers of already-collected globals
        let global_map: HashMap<String, &ValueRef> = module
            .globals
            .iter()
            .map(|g| (g.borrow().name.clone(), g))
            .collect();

        let mut queue: Vec<String> = globals.iter().cloned().collect();
        let mut visited: HashSet<String> = globals.clone();

        while let Some(gname) = queue.pop() {
            if let Some(gref) = global_map.get(&gname) {
                let g = gref.borrow();
                for op in &g.operands {
                    let o = op.borrow();
                    if o.subclass == SubclassKind::GlobalVariable {
                        let oname = o.name.clone();
                        if visited.insert(oname.clone()) {
                            globals.insert(oname.clone());
                            queue.push(oname);
                        }
                    }
                }
            }
        }

        globals.into_iter().collect()
    }

    /// Strip debug info metadata and debug intrinsics from a module.
    fn strip_debug_info(module: &mut Module) {
        // Remove debug metadata kinds from named_metadata
        module.named_metadata.remove("llvm.dbg.cu");
        module.named_metadata.remove("llvm.dbg.globals");
        module.named_metadata.remove("llvm.dbg.subprograms");

        // Strip metadata from functions and their instructions
        for f in &mut module.functions {
            let mut func = f.borrow_mut();
            func.metadata.clear();

            for operand in &func.operands {
                let mut bb = operand.borrow_mut();
                if !bb.is_basic_block() {
                    continue;
                }
                for inst in &bb.operands {
                    let mut i = inst.borrow_mut();
                    i.metadata.clear();
                    i.is_used_by_md = false;
                }
            }
        }

        // Strip metadata from globals
        for g in &mut module.globals {
            g.borrow_mut().metadata.clear();
        }
    }

    /// Deep-clone a function value including its basic blocks and instructions.
    fn clone_function_deep(src: &ValueRef) -> ValueRef {
        let src_func = src.borrow();

        let mut dest_func = Value::new(src_func.ty.clone())
            .with_subclass(SubclassKind::Function)
            .named(&src_func.name);

        if let Some(ref ret_ty) = src_func.return_type {
            dest_func.return_type = Some(ret_ty.clone());
        }

        let dest_ref = valref(dest_func);

        // Clone arguments and basic blocks
        for operand in &src_func.operands {
            let op = operand.borrow();
            if op.subclass == SubclassKind::Argument {
                let arg = Value::new(op.ty.clone())
                    .with_subclass(SubclassKind::Argument)
                    .named(&op.name);
                let arg_ref = valref(arg);
                arg_ref.borrow_mut().parent = Some(dest_ref.clone());
                dest_ref.borrow_mut().operands.push(arg_ref);
            } else if op.is_basic_block() {
                let cloned_bb = Self::clone_basic_block(operand, &dest_ref);
                dest_ref.borrow_mut().operands.push(cloned_bb);
            }
        }

        let num_ops = dest_ref.borrow().operands.len();
        dest_ref.borrow_mut().num_operands = num_ops;

        dest_ref
    }

    /// Clone a basic block into a destination function.
    fn clone_basic_block(src_bb: &ValueRef, dest_func: &ValueRef) -> ValueRef {
        let src = src_bb.borrow();

        let mut dest = Value::new(src.ty.clone())
            .with_subclass(SubclassKind::BasicBlock)
            .named(&src.name);

        dest.parent = Some(dest_func.clone());

        for inst in &src.operands {
            let src_inst = inst.borrow();
            if !src_inst.is_instruction() {
                continue;
            }
            let mut cloned_inst = Value::new(src_inst.ty.clone())
                .with_subclass(src_inst.subclass)
                .named(&src_inst.name);

            cloned_inst.opcode = src_inst.opcode;
            cloned_inst.operands = src_inst.operands.clone();
            cloned_inst.num_operands = src_inst.operands.len();
            cloned_inst.parent = Some(dest_func.clone());
            cloned_inst.subclass_data = src_inst.subclass_data;

            let inst_ref = valref(cloned_inst);
            dest.operands.push(inst_ref);
        }

        valref(dest)
    }

    /// Clone a global variable, alias, or ifunc.
    fn clone_global(src: &ValueRef) -> ValueRef {
        let src_val = src.borrow();

        let mut cloned = Value::new(src_val.ty.clone())
            .with_subclass(src_val.subclass)
            .named(&src_val.name);

        cloned.operands = src_val.operands.clone();
        cloned.num_operands = src_val.operands.len();
        cloned.subclass_data = src_val.subclass_data;
        cloned.return_type = src_val.return_type.clone();

        valref(cloned)
    }

    /// Simple string matching that supports '*' as wildcard.
    fn simple_match(name: &str, pattern: &str) -> bool {
        if !pattern.contains('*') {
            return name == pattern;
        }
        if pattern == "*" {
            return true;
        }
        // Split on first and last '*'
        let first_star = pattern.find('*').unwrap();
        let last_star = pattern.rfind('*').unwrap();

        let prefix = &pattern[..first_star];
        let suffix = &pattern[last_star + 1..];
        let middle = if first_star < last_star {
            &pattern[first_star + 1..last_star]
        } else {
            ""
        };

        if !name.starts_with(prefix) {
            return false;
        }
        if !name.ends_with(suffix) {
            return false;
        }
        if !middle.is_empty() {
            let after_prefix = &name[prefix.len()..name.len() - suffix.len()];
            if !after_prefix.contains(middle) {
                return false;
            }
        }
        true
    }
}

// ============================================================================
// Loop Extraction
// ============================================================================

impl LLVMExtract {
    /// Extract a loop from a function into a standalone function.
    /// The identified loop region is extracted into a new function,
    /// with the original function calling the extracted one.
    pub fn extract_loop(module: &Module, func_name: &str, loop_header_name: &str) -> Module {
        let mut extracted = Module::new(&format!("extracted_loop_{}", loop_header_name));
        extracted.source_filename = module.source_filename.clone();
        extracted.target_triple = module.target_triple.clone();
        extracted.data_layout = module.data_layout.clone();
        extracted.types = module.types.clone();
        extracted.named_types = module.named_types.clone();
        extracted.flags = module.flags.clone();

        // Find the source function
        let source_func = module
            .functions
            .iter()
            .find(|f| f.borrow().name == func_name);
        if source_func.is_none() {
            return extracted;
        }

        let func = source_func.unwrap();
        let extracted_func = Self::extract_loop_to_function(func, loop_header_name);
        extracted.functions.push(extracted_func);

        Self::strip_debug_info(&mut extracted);
        extracted
    }

    /// Extract a loop body from a function into a new function with its
    /// own arguments for live-in values.
    fn extract_loop_to_function(func: &ValueRef, loop_header: &str) -> ValueRef {
        let f = func.borrow();
        let new_name = format!("{}_loop_{}", f.name, loop_header);

        let ty = f.ty.clone();
        let mut new_func = Value::new(ty)
            .with_subclass(SubclassKind::Function)
            .named(&new_name);

        new_func.return_type = f.return_type.clone();
        let new_ref = valref(new_func);

        // Find the loop header block
        for operand in &f.operands {
            let bb = operand.borrow();
            if bb.is_basic_block() {
                let bb_name = bb.name.clone();
                if bb_name == loop_header {
                    // Clone this block and its loop body into the new function
                    let cloned_bb = Self::clone_basic_block(operand, &new_ref);
                    new_ref.borrow_mut().operands.push(cloned_bb);

                    // Follow successors that are part of the loop
                    let mut visited: HashSet<String> = HashSet::new();
                    visited.insert(bb_name);
                    Self::clone_loop_successors(operand, &new_ref, func, &mut visited, loop_header);
                    break;
                }
            }
        }

        new_ref
    }

    /// Recursively clone successors of a loop block that are still within
    /// the loop (not the exit block).
    fn clone_loop_successors(
        src_bb: &ValueRef,
        dest_func: &ValueRef,
        src_func: &ValueRef,
        visited: &mut HashSet<String>,
        loop_header: &str,
    ) {
        let bb = src_bb.borrow();

        // Find all successor block names by looking at terminators
        let mut successors: Vec<String> = Vec::new();
        for inst in &bb.operands {
            let i = inst.borrow();
            if let Some(op) = i.opcode {
                if matches!(op, Opcode::Br | Opcode::Switch) {
                    for opnd in &i.operands {
                        let o = opnd.borrow();
                        if o.is_basic_block() {
                            let succ_name = if o.name.is_empty() {
                                format!("bb")
                            } else {
                                o.name.clone()
                            };
                            successors.push(succ_name);
                        }
                    }
                }
            }
        }

        for succ_name in successors {
            if succ_name == loop_header && visited.contains(&succ_name) {
                // Back-edge — skip (already visited the header)
                continue;
            }

            if !visited.insert(succ_name.clone()) {
                continue;
            }

            // Find the successor block in the source function
            let sf = src_func.borrow();
            for operand in &sf.operands {
                let sbb = operand.borrow();
                if sbb.is_basic_block() && sbb.name == succ_name {
                    let cloned = Self::clone_basic_block(operand, dest_func);
                    dest_func.borrow_mut().operands.push(cloned);
                    Self::clone_loop_successors(operand, dest_func, src_func, visited, loop_header);
                    break;
                }
            }
        }
    }

    /// Extract a region of basic blocks (contiguous block set) into a
    /// new function. The BlockExtractor identifies a single-entry,
    /// multiple-exit region and creates a new function for it.
    pub fn extract_block_region(
        module: &Module,
        func_name: &str,
        block_names: &[String],
    ) -> Module {
        let mut extracted = Module::new("extracted_region");
        extracted.source_filename = module.source_filename.clone();
        extracted.target_triple = module.target_triple.clone();
        extracted.data_layout = module.data_layout.clone();
        extracted.types = module.types.clone();
        extracted.named_types = module.named_types.clone();
        extracted.flags = module.flags.clone();

        let source_func = module
            .functions
            .iter()
            .find(|f| f.borrow().name == func_name);
        if source_func.is_none() {
            return extracted;
        }

        let func = source_func.unwrap();
        let block_set: HashSet<&str> = block_names.iter().map(|s| s.as_str()).collect();

        // Create the extracted region function
        let f = func.borrow();
        let new_name = format!("{}_region", f.name);
        let mut new_func = Value::new(f.ty.clone())
            .with_subclass(SubclassKind::Function)
            .named(&new_name);
        new_func.return_type = f.return_type.clone();
        let new_ref = valref(new_func);

        for operand in &f.operands {
            let bb = operand.borrow();
            if bb.is_basic_block() {
                let bb_name = bb.name.clone();
                if block_set.contains(bb_name.as_str()) {
                    let cloned = Self::clone_basic_block(operand, &new_ref);
                    new_ref.borrow_mut().operands.push(cloned);
                }
            }
        }

        extracted.functions.push(new_ref);
        Self::strip_debug_info(&mut extracted);
        extracted
    }

    /// Extract entities with alias mapping: creates a mapping of old
    /// names to new names in the extracted module.
    pub fn extract_with_alias_map(
        module: &Module,
        function_names: &[String],
        global_names: &[String],
    ) -> (Module, HashMap<String, String>) {
        let mut extracted = Module::new("extracted_aliased");
        extracted.source_filename = module.source_filename.clone();
        extracted.target_triple = module.target_triple.clone();
        extracted.data_layout = module.data_layout.clone();
        extracted.types = module.types.clone();
        extracted.named_types = module.named_types.clone();
        extracted.flags = module.flags.clone();
        extracted.attr_groups = module.attr_groups.clone();
        extracted.comdats = module.comdats.clone();

        let mut alias_map = HashMap::new();
        let func_set: HashSet<&str> = function_names.iter().map(|s| s.as_str()).collect();
        let global_set: HashSet<&str> = global_names.iter().map(|s| s.as_str()).collect();

        for f in &module.functions {
            let fname = f.borrow().name.clone();
            if func_set.contains(fname.as_str()) {
                let cloned = Self::clone_function_deep(f);
                let new_name = format!("extracted_{}", fname);
                cloned.borrow_mut().name = new_name.clone();
                alias_map.insert(fname, new_name);
                extracted.functions.push(cloned);
            }
        }

        for g in &module.globals {
            let gname = g.borrow().name.clone();
            if global_set.contains(gname.as_str()) {
                let cloned = Self::clone_global(g);
                let new_name = format!("extracted_{}", gname);
                cloned.borrow_mut().name = new_name.clone();
                alias_map.insert(gname, new_name);
                extracted.globals.push(cloned);
            }
        }

        Self::strip_debug_info(&mut extracted);
        (extracted, alias_map)
    }

    /// CodeExtractor utility — estimates the cost (in terms of
    /// instruction count) of extracting a set of blocks.
    pub fn estimate_extraction_cost(
        _module: &Module,
        _func_name: &str,
        block_names: &[String],
    ) -> ExtractionCost {
        let base_count = block_names.len();

        // Heuristic cost model:
        // - Each extracted block adds ~5 instructions (argument setup, call, return)
        // - More blocks mean more live-in values to pass as arguments
        let overhead = 5 + block_names.len() * 2;
        let benefit = block_names.len() * 10; // Simplified benefit

        ExtractionCost {
            blocks_to_extract: block_names.len(),
            estimated_overhead: overhead,
            estimated_benefit: benefit,
            is_profitable: benefit > overhead,
        }
    }

    /// Extract all functions matching a list of names and include all
    /// their callees and referenced data.
    pub fn bulk_extract(module: &Module, names: &[String], include_data: bool) -> Module {
        let mut extracted = Self::extract_functions(module, names);

        if include_data {
            // Also extract any global data referenced by globals already extracted
            let existing_globals: Vec<String> = extracted
                .globals
                .iter()
                .map(|g| g.borrow().name.clone())
                .collect();

            let additional = Self::find_referenced_globals(module, &names.to_vec());
            for gname in additional {
                if !existing_globals.contains(&gname) {
                    for g in &module.globals {
                        if g.borrow().name == gname {
                            extracted.globals.push(Self::clone_global(g));
                            break;
                        }
                    }
                }
            }
        }

        extracted
    }
}

/// Cost model for block extraction decisions.
#[derive(Debug, Clone)]
pub struct ExtractionCost {
    pub blocks_to_extract: usize,
    pub estimated_overhead: usize,
    pub estimated_benefit: usize,
    pub is_profitable: bool,
}

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

#[cfg(test)]
mod tests {
    use super::*;
    use llvm_native_core::instruction::{br, call, ret_void};
    use llvm_native_core::ir_builder::IRBuilder;
    use llvm_native_core::types::Type;
    use llvm_native_core::value::valref;

    fn make_test_module() -> Module {
        let mut module = Module::new("test_module");
        module.source_filename = "test.ll".to_string();

        // Declare a function type: void ()
        let void_ty = Type::void();
        let func_ty = Type::function_type_with(void_ty.id, vec![], false);

        // Function @foo
        let mut foo = Value::new(func_ty.clone())
            .with_subclass(SubclassKind::Function)
            .named("foo");
        foo.return_type = Some(void_ty.clone());
        let foo_ref = valref(foo);

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

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

        foo_ref.borrow_mut().operands.push(entry_foo);
        foo_ref.borrow_mut().num_operands = 1;
        module.functions.push(foo_ref);

        // Function @bar
        let mut bar = Value::new(func_ty.clone())
            .with_subclass(SubclassKind::Function)
            .named("bar");
        bar.return_type = Some(void_ty.clone());
        let bar_ref = valref(bar);

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

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

        bar_ref.borrow_mut().operands.push(entry_bar);
        bar_ref.borrow_mut().num_operands = 1;
        module.functions.push(bar_ref);

        // Global @my_global
        let g = Value::new(Type::i32())
            .with_subclass(SubclassKind::GlobalVariable)
            .named("my_global");
        module.globals.push(valref(g));

        module
    }

    #[test]
    fn test_extract_single_function() {
        let module = make_test_module();
        let names = vec!["foo".to_string()];
        let extracted = LLVMExtract::extract_functions(&module, &names);

        assert_eq!(extracted.functions.len(), 1);
        assert_eq!(extracted.functions[0].borrow().name, "foo");
    }

    #[test]
    fn test_extract_multiple_functions() {
        let module = make_test_module();
        let names = vec!["foo".to_string(), "bar".to_string()];
        let extracted = LLVMExtract::extract_functions(&module, &names);

        assert_eq!(extracted.functions.len(), 2);
        let fnames: Vec<String> = extracted
            .functions
            .iter()
            .map(|f| f.borrow().name.clone())
            .collect();
        assert!(fnames.contains(&"foo".to_string()));
        assert!(fnames.contains(&"bar".to_string()));
    }

    #[test]
    fn test_extract_no_match() {
        let module = make_test_module();
        let names = vec!["nonexistent".to_string()];
        let extracted = LLVMExtract::extract_functions(&module, &names);

        assert!(extracted.functions.is_empty());
    }

    #[test]
    fn test_extract_globals() {
        let module = make_test_module();
        let names = vec!["my_global".to_string()];
        let extracted = LLVMExtract::extract_globals(&module, &names);

        assert_eq!(extracted.globals.len(), 1);
        assert_eq!(extracted.globals[0].borrow().name, "my_global");
    }

    #[test]
    fn test_extract_by_regex_exact() {
        let module = make_test_module();
        let extracted = LLVMExtract::extract_by_regex(&module, "foo");

        assert_eq!(extracted.functions.len(), 1);
        assert_eq!(extracted.functions[0].borrow().name, "foo");
    }

    #[test]
    fn test_extract_by_regex_prefix() {
        let module = make_test_module();
        let extracted = LLVMExtract::extract_by_regex(&module, "foo*");

        assert_eq!(extracted.functions.len(), 1);
        assert_eq!(extracted.functions[0].borrow().name, "foo");
    }

    #[test]
    fn test_extract_by_regex_suffix() {
        let module = make_test_module();
        let extracted = LLVMExtract::extract_by_regex(&module, "*bar");

        assert_eq!(extracted.functions.len(), 1);
        assert_eq!(extracted.functions[0].borrow().name, "bar");
    }

    #[test]
    fn test_extract_by_regex_contains() {
        let module = make_test_module();
        let extracted = LLVMExtract::extract_by_regex(&module, "*o*");

        assert_eq!(extracted.functions.len(), 1);
        assert_eq!(extracted.functions[0].borrow().name, "foo");
    }

    #[test]
    fn test_simple_match_exact() {
        assert!(LLVMExtract::simple_match("foo", "foo"));
        assert!(!LLVMExtract::simple_match("foo", "bar"));
    }

    #[test]
    fn test_simple_match_wildcard() {
        assert!(LLVMExtract::simple_match("foo", "f*"));
        assert!(LLVMExtract::simple_match("foo", "*oo"));
        assert!(LLVMExtract::simple_match("foobar", "f*r"));
        assert!(LLVMExtract::simple_match("foobar", "*oba*"));
    }

    #[test]
    fn test_find_transitive_callees_empty() {
        let module = make_test_module();
        let callees = LLVMExtract::find_transitive_callees(&module, &[]);
        assert!(callees.is_empty());
    }

    #[test]
    fn test_find_referenced_globals_empty_when_none() {
        let module = make_test_module();
        let globs = LLVMExtract::find_referenced_globals(&module, &["foo".to_string()]);
        // foo doesn't reference my_global, so result should be empty
        assert!(globs.is_empty());
    }

    #[test]
    fn test_strip_debug_info() {
        let mut module = make_test_module();
        module
            .named_metadata
            .insert("llvm.dbg.cu".to_string(), vec![1]);
        LLVMExtract::strip_debug_info(&mut module);
        assert!(!module.named_metadata.contains_key("llvm.dbg.cu"));
    }

    #[test]
    fn test_extracted_module_preserves_source() {
        let module = make_test_module();
        let extracted = LLVMExtract::extract_functions(&module, &["foo".to_string()]);
        assert_eq!(extracted.source_filename, "test.ll");
    }
}