llvm-native-core-ext 0.1.0

//! LLVM Garbage Collection Support — GC strategies, statepoint lowering,
//! stack map emission, write barriers, and root tracking.
//!
//! Clean-room behavioral reconstruction from the LLVM Garbage Collection
//! documentation, Statepoint and PatchPoint intrinsics reference,
//! Stack Map format specification, and published GC implementation guides.
//! No LLVM C++ source code is consulted.
//!
//! ## Subsystems
//!
//! - **GCStrategy** — Built-in GC strategies: shadow-stack, statepoint-example,
//!   coreclr, erlang, ocaml.
//! - **GCModuleInfo** — Per-module GC configuration and metadata.
//! - **GCFunctionInfo** — Per-function GC live variable tracking.
//! - **GCRoot** — Stack root with frame offset and type metadata.
//! - **Statepoint Lowering** — gc.statepoint → stack map + call,
//!   gc.result → select from spill slot, gc.relocate → load from spill slot.
//! - **Stack Map Format** — `.llvm_stackmaps` section with function/constant/
//!   location records.
//! - **PatchPoint** — Patchable call sites for JIT recompilation.
//! - **OCaml GC** — Custom frame descriptor emission.
//! - **CoreCLR GC** — GCInfo table with fully-interruptible and
//!   partially-interruptible regions.
//! - **ShadowStack** — Runtime shadow stack for precise GC.
//! - **Erlang GC** — Process stack with GC safe points.
//! - **Write Barriers** — Card marking, remembered sets.

use llvm_native_core::codegen::MachineInstr;
use std::collections::{BTreeMap, HashMap, HashSet};

// ============================================================================
// Constants
// ============================================================================

/// Maximum number of GC roots per function.
const MAX_GC_ROOTS: usize = 256;

/// Minimum alignment for GC-managed objects.
const GC_OBJECT_ALIGNMENT: u32 = 8;

/// Default card size for card-marking write barriers (in bytes).
const CARD_SIZE: u32 = 512;

/// Default remembered set log size (in entries).
const REMEMBERED_SET_LOG_SIZE: usize = 12;

/// Stack map version (current: 3).
const STACK_MAP_VERSION: u8 = 3;

/// Stack map section name.
const STACK_MAP_SECTION: &str = ".llvm_stackmaps";

// ============================================================================
// GC Strategies
// ============================================================================

/// Built-in garbage collection strategies available in LLVM.
///
/// Each strategy defines how the compiler inserts GC safepoints,
/// tracks roots, and emits stack maps.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum GCStrategy {
    /// Shadow stack: roots are maintained in a runtime-visible stack
    /// alongside the program stack. Used for precise GC with simple
    /// frontends. The runtime walks the shadow stack to find roots.
    ShadowStack,

    /// Statepoint example: reference implementation using LLVM's
    /// `gc.statepoint`, `gc.result`, and `gc.relocate` intrinsics.
    /// Suitable for generational and copying collectors.
    StatepointExample,

    /// CoreCLR: .NET Core runtime GC. Supports fully-interruptible
    /// and partially-interruptible regions. Uses GCInfo tables for
    /// efficient root enumeration. Supports cooperative suspension.
    CoreCLR,

    /// Erlang: BEAM VM process-heap GC. Each Erlang process has its
    /// own heap and stack. GC safe-points are placed at function
    /// calls and loop back-edges. Supports process-level GC.
    Erlang,

    /// OCaml: Caml runtime GC. Uses custom frame descriptors that
    /// encode root locations compactly. Supports generational
    /// collection with a minor heap.
    OCaml,
}

impl GCStrategy {
    /// Returns the human-readable name of this strategy.
    pub fn name(&self) -> &'static str {
        match self {
            GCStrategy::ShadowStack => "shadow-stack",
            GCStrategy::StatepointExample => "statepoint-example",
            GCStrategy::CoreCLR => "coreclr",
            GCStrategy::Erlang => "erlang",
            GCStrategy::OCaml => "ocaml",
        }
    }

    /// Returns true if this strategy uses statepoints.
    pub fn uses_statepoints(&self) -> bool {
        match self {
            GCStrategy::StatepointExample | GCStrategy::CoreCLR => true,
            GCStrategy::ShadowStack | GCStrategy::Erlang | GCStrategy::OCaml => false,
        }
    }

    /// Returns true if this strategy uses a shadow stack.
    pub fn uses_shadow_stack(&self) -> bool {
        match self {
            GCStrategy::ShadowStack => true,
            GCStrategy::StatepointExample
            | GCStrategy::CoreCLR
            | GCStrategy::Erlang
            | GCStrategy::OCaml => false,
        }
    }

    /// Returns true if this strategy supports generational collection.
    pub fn supports_generational(&self) -> bool {
        match self {
            GCStrategy::StatepointExample
            | GCStrategy::CoreCLR
            | GCStrategy::OCaml => true,
            GCStrategy::ShadowStack | GCStrategy::Erlang => false,
        }
    }

    /// Returns true if this strategy requires write barriers.
    pub fn requires_write_barriers(&self) -> bool {
        self.supports_generational()
    }

    /// Returns true if this strategy supports concurrent marking.
    pub fn supports_concurrent_marking(&self) -> bool {
        match self {
            GCStrategy::CoreCLR | GCStrategy::StatepointExample => true,
            GCStrategy::ShadowStack | GCStrategy::Erlang | GCStrategy::OCaml => false,
        }
    }

    /// Returns true if cooperative suspension is used.
    pub fn uses_cooperative_suspension(&self) -> bool {
        match self {
            GCStrategy::CoreCLR => true,
            GCStrategy::ShadowStack
            | GCStrategy::StatepointExample
            | GCStrategy::Erlang
            | GCStrategy::OCaml => false,
        }
    }

    /// Returns the recommended GC safepoint frequency.
    /// Lower means more frequent safepoints.
    pub fn safepoint_frequency(&self) -> u32 {
        match self {
            GCStrategy::ShadowStack => 0,
            GCStrategy::StatepointExample => 0,
            GCStrategy::CoreCLR => 1,
            GCStrategy::Erlang => 2,
            GCStrategy::OCaml => 1,
        }
    }
}

impl Default for GCStrategy {
    fn default() -> Self {
        GCStrategy::StatepointExample
    }
}

impl std::fmt::Display for GCStrategy {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.name())
    }
}

// ============================================================================
// GC Root
// ============================================================================

/// A GC root describes a pointer on the stack that must be tracked
/// during garbage collection.
#[derive(Debug, Clone)]
pub struct GCRoot {
    /// Unique identifier for this root.
    pub id: u32,

    /// Offset from the frame pointer (canonical frame address, CFA)
    /// where the root is stored.
    pub frame_offset: i32,

    /// The LLVM type of the pointer (e.g., `i8*`, `%Foo*`).
    pub pointer_type: String,

    /// Optional metadata describing the pointee type for precise
    /// scanning (e.g., "java.lang.Object", "Foo").
    pub type_metadata: Option<String>,

    /// Whether this root is derived (interior pointer).
    pub is_derived: bool,

    /// Whether this root is a base pointer (points to object start).
    pub is_base: bool,

    /// The offset from the base object if this is an interior pointer.
    pub interior_offset: i32,

    /// Whether this root is constant (never modified after init).
    pub is_constant: bool,

    /// Whether this root must be updated during GC (relocated).
    pub needs_relocation: bool,

    /// The source language that produced this root.
    pub source_language: Option<String>,
}

impl GCRoot {
    /// Creates a new base pointer GC root.
    pub fn new_base(id: u32, frame_offset: i32, pointer_type: &str) -> Self {
        GCRoot {
            id,
            frame_offset,
            pointer_type: pointer_type.to_string(),
            type_metadata: None,
            is_derived: false,
            is_base: true,
            interior_offset: 0,
            is_constant: false,
            needs_relocation: true,
            source_language: None,
        }
    }

    /// Creates a new derived (interior) pointer GC root.
    pub fn new_derived(
        id: u32,
        frame_offset: i32,
        pointer_type: &str,
        interior_offset: i32,
    ) -> Self {
        GCRoot {
            id,
            frame_offset,
            pointer_type: pointer_type.to_string(),
            type_metadata: None,
            is_derived: true,
            is_base: false,
            interior_offset,
            is_constant: false,
            needs_relocation: true,
            source_language: None,
        }
    }

    /// Creates a new constant GC root (never modified).
    pub fn new_constant(id: u32, frame_offset: i32, pointer_type: &str) -> Self {
        GCRoot {
            id,
            frame_offset,
            pointer_type: pointer_type.to_string(),
            type_metadata: None,
            is_derived: false,
            is_base: true,
            interior_offset: 0,
            is_constant: true,
            needs_relocation: false,
            source_language: None,
        }
    }

    /// Sets the type metadata for this root.
    pub fn with_type_metadata(mut self, metadata: &str) -> Self {
        self.type_metadata = Some(metadata.to_string());
        self
    }

    /// Sets the source language.
    pub fn with_language(mut self, lang: &str) -> Self {
        self.source_language = Some(lang.to_string());
        self
    }

    /// Returns the total size in bytes of this root slot.
    pub fn slot_size(&self) -> u32 {
        if self.is_derived {
            16 // base + derived pair
        } else {
            8 // single pointer
        }
    }

    /// Returns true if this root is live at the given instruction index.
    pub fn is_live_at(&self, _index: usize) -> bool {
        // Placeholder: real implementation checks live ranges.
        true
    }

    /// Returns the base root id if this is a derived pointer;
    /// returns self.id if this is a base pointer.
    pub fn base_root_id(&self) -> u32 {
        if self.is_derived {
            // Derived pointers pair with the preceding base root.
            self.id.saturating_sub(1)
        } else {
            self.id
        }
    }
}

// ============================================================================
// GCFunctionInfo
// ============================================================================

/// Per-function GC information tracking live variables, roots,
/// and safepoint locations.
#[derive(Debug, Clone)]
pub struct GCFunctionInfo {
    /// The name of the function.
    pub function_name: String,

    /// GC strategy used for this function.
    pub strategy: GCStrategy,

    /// All GC roots in this function (stack slots).
    pub roots: Vec<GCRoot>,

    /// Map from safepoint ID to the set of live root IDs.
    pub safepoint_live_roots: HashMap<u32, HashSet<u32>>,

    /// All safepoint locations (instruction offsets).
    pub safepoint_locations: Vec<SafepointLocation>,

    /// Frame size in bytes.
    pub frame_size: i32,

    /// Number of spill slots used for GC.
    pub spill_slot_count: u32,

    /// Whether this function has a frame pointer.
    pub has_frame_pointer: bool,

    /// Whether this function is fully interruptible.
    pub is_fully_interruptible: bool,

    /// Safe-point count per basic block.
    pub block_safepoints: HashMap<String, usize>,

    /// Total number of call sites in this function.
    pub call_site_count: usize,

    /// Whether the function has been analyzed.
    pub analyzed: bool,
}

impl GCFunctionInfo {
    /// Creates a new empty GCFunctionInfo.
    pub fn new(function_name: &str, strategy: GCStrategy) -> Self {
        GCFunctionInfo {
            function_name: function_name.to_string(),
            strategy,
            roots: Vec::new(),
            safepoint_live_roots: HashMap::new(),
            safepoint_locations: Vec::new(),
            frame_size: 0,
            spill_slot_count: 0,
            has_frame_pointer: true,
            is_fully_interruptible: false,
            block_safepoints: HashMap::new(),
            call_site_count: 0,
            analyzed: false,
        }
    }

    /// Adds a GC root to this function.
    pub fn add_root(&mut self, root: GCRoot) -> u32 {
        let id = root.id;
        self.roots.push(root);
        if self.roots.len() > MAX_GC_ROOTS {
            eprintln!(
                "Warning: function {} exceeds max GC roots ({} > {})",
                self.function_name,
                self.roots.len(),
                MAX_GC_ROOTS
            );
        }
        id
    }

    /// Records a safepoint location.
    pub fn add_safepoint(&mut self, location: SafepointLocation) {
        let sp_id = location.id;
        self.safepoint_live_roots
            .insert(sp_id, location.live_roots.clone());
        self.safepoint_locations.push(location);
    }

    /// Finds all roots live at the given safepoint.
    pub fn live_roots_at(&self, safepoint_id: u32) -> Vec<&GCRoot> {
        match self.safepoint_live_roots.get(&safepoint_id) {
            Some(live_set) => self.roots.iter().filter(|r| live_set.contains(&r.id)).collect(),
            None => Vec::new(),
        }
    }

    /// Returns the total number of roots in this function.
    pub fn root_count(&self) -> usize {
        self.roots.len()
    }

    /// Returns the number of derived roots.
    pub fn derived_root_count(&self) -> usize {
        self.roots.iter().filter(|r| r.is_derived).count()
    }

    /// Returns the number of base roots.
    pub fn base_root_count(&self) -> usize {
        self.roots.iter().filter(|r| r.is_base).count()
    }

    /// Returns the total safepoint count.
    pub fn safepoint_count(&self) -> usize {
        self.safepoint_locations.len()
    }

    /// Sets the frame size.
    pub fn set_frame_size(&mut self, size: i32) {
        self.frame_size = size;
    }

    /// Marks the analysis as complete.
    pub fn mark_analyzed(&mut self) {
        self.analyzed = true;
    }
}

// ============================================================================
// Safepoint Location
// ============================================================================

/// Describes a single GC safepoint within a function.
#[derive(Debug, Clone)]
pub struct SafepointLocation {
    /// Unique safepoint ID within the function.
    pub id: u32,

    /// Instruction offset from function start (in bytes).
    pub instruction_offset: u32,

    /// The basic block name containing this safepoint.
    pub block_name: String,

    /// Set of live GC root IDs at this safepoint.
    pub live_roots: HashSet<u32>,

    /// Whether this is a call safepoint (vs. loop back-edge).
    pub is_call: bool,

    /// The call target name (if a call safepoint).
    pub call_target: Option<String>,

    /// Whether this safepoint is a polling site.
    pub is_polling: bool,

    /// Reference to the statepoint ID in the stack map.
    pub statepoint_id: Option<u64>,

    /// Whether the runtime may need to patch this safepoint.
    pub is_patchable: bool,

    /// Deoptimization state associated with this safepoint.
    pub deopt_state: Option<DeoptState>,
}

impl SafepointLocation {
    /// Creates a new call safepoint.
    pub fn new_call(
        id: u32,
        offset: u32,
        block: &str,
        call_target: &str,
        live_roots: HashSet<u32>,
    ) -> Self {
        SafepointLocation {
            id,
            instruction_offset: offset,
            block_name: block.to_string(),
            live_roots,
            is_call: true,
            call_target: Some(call_target.to_string()),
            is_polling: false,
            statepoint_id: None,
            is_patchable: false,
            deopt_state: None,
        }
    }

    /// Creates a new loop-back-edge safepoint (polling site).
    pub fn new_poll(id: u32, offset: u32, block: &str, live_roots: HashSet<u32>) -> Self {
        SafepointLocation {
            id,
            instruction_offset: offset,
            block_name: block.to_string(),
            live_roots,
            is_call: false,
            call_target: None,
            is_polling: true,
            statepoint_id: None,
            is_patchable: false,
            deopt_state: None,
        }
    }

    /// Sets the statepoint ID.
    pub fn with_statepoint_id(mut self, sp_id: u64) -> Self {
        self.statepoint_id = Some(sp_id);
        self
    }

    /// Marks as patchable.
    pub fn with_patchable(mut self) -> Self {
        self.is_patchable = true;
        self
    }
}

// ============================================================================
// Deopt State
// ============================================================================

/// Deoptimization state associated with a safepoint.
/// Allows the runtime to reconstruct the interpreter state from
/// compiled code at a safepoint.
#[derive(Debug, Clone)]
pub struct DeoptState {
    /// The bytecode offset (or equivalent) for this point.
    pub bytecode_offset: u32,

    /// Map from virtual register number to stack location.
    pub vreg_to_stack: BTreeMap<u32, i32>,

    /// Live local variables at this point.
    pub live_locals: Vec<DeoptLocal>,

    /// Inlining chain depth (0 = top-level).
    pub inline_depth: u32,

    /// Reason for potential deoptimization.
    pub reason: DeoptReason,
}

impl DeoptState {
    /// Creates a new deoptimization state.
    pub fn new(bytecode_offset: u32, reason: DeoptReason) -> Self {
        DeoptState {
            bytecode_offset,
            vreg_to_stack: BTreeMap::new(),
            live_locals: Vec::new(),
            inline_depth: 0,
            reason,
        }
    }

    /// Adds a virtual register location mapping.
    pub fn add_vreg(&mut self, vreg: u32, stack_offset: i32) {
        self.vreg_to_stack.insert(vreg, stack_offset);
    }

    /// Adds a live local variable.
    pub fn add_local(&mut self, local: DeoptLocal) {
        self.live_locals.push(local);
    }

    /// Sets the inlining depth.
    pub fn with_inline_depth(mut self, depth: u32) -> Self {
        self.inline_depth = depth;
        self
    }
}

/// A live local variable at a deoptimization point.
#[derive(Debug, Clone)]
pub struct DeoptLocal {
    /// Local variable name.
    pub name: String,

    /// Type descriptor.
    pub type_name: String,

    /// Stack offset where the value is stored.
    pub stack_offset: i32,

    /// Whether this local is a GC reference.
    pub is_reference: bool,
}

/// Reason for potential deoptimization at a safepoint.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DeoptReason {
    /// No specific reason.
    None,
    /// Speculative optimization may be invalid.
    SpeculativeGuard,
    /// Type check may fail.
    TypeCheck,
    /// Bounds check may fail.
    BoundsCheck,
    /// Null check may fail.
    NullCheck,
    /// Division by zero may occur.
    DivZero,
    /// Class hierarchy may be incomplete.
    ClassCheck,
    /// Virtual call target may have changed.
    VirtualCall,
}

impl DeoptReason {
    pub fn as_str(&self) -> &'static str {
        match self {
            DeoptReason::None => "none",
            DeoptReason::SpeculativeGuard => "speculative_guard",
            DeoptReason::TypeCheck => "type_check",
            DeoptReason::BoundsCheck => "bounds_check",
            DeoptReason::NullCheck => "null_check",
            DeoptReason::DivZero => "div_zero",
            DeoptReason::ClassCheck => "class_check",
            DeoptReason::VirtualCall => "virtual_call",
        }
    }
}

// ============================================================================
// GCModuleInfo
// ============================================================================

/// Per-module GC configuration and metadata.
#[derive(Debug, Clone)]
pub struct GCModuleInfo {
    /// The GC strategy for this module.
    pub strategy: GCStrategy,

    /// Per-function GC information.
    pub functions: HashMap<String, GCFunctionInfo>,

    /// Module-level GC configuration options.
    pub config: GCConfig,

    /// Stack map records for this module.
    pub stack_maps: Vec<StackMapRecord>,

    /// Whether the module has been compiled with GC support.
    pub gc_enabled: bool,

    /// Target architecture triple.
    pub target_triple: String,
}

impl GCModuleInfo {
    /// Creates a new GCModuleInfo with the given strategy.
    pub fn new(strategy: GCStrategy, target_triple: &str) -> Self {
        GCModuleInfo {
            strategy,
            functions: HashMap::new(),
            config: GCConfig::default(),
            stack_maps: Vec::new(),
            gc_enabled: true,
            target_triple: target_triple.to_string(),
        }
    }

    /// Adds function-level GC info.
    pub fn add_function(&mut self, info: GCFunctionInfo) {
        self.functions.insert(info.function_name.clone(), info);
    }

    /// Returns the GC info for a function, if present.
    pub fn get_function(&self, name: &str) -> Option<&GCFunctionInfo> {
        self.functions.get(name)
    }

    /// Adds a stack map record.
    pub fn add_stack_map(&mut self, record: StackMapRecord) {
        self.stack_maps.push(record);
    }

    /// Returns the total number of safepoints across all functions.
    pub fn total_safepoints(&self) -> usize {
        self.functions.values().map(|f| f.safepoint_count()).sum()
    }

    /// Returns the total number of GC roots across all functions.
    pub fn total_roots(&self) -> usize {
        self.functions.values().map(|f| f.root_count()).sum()
    }

    /// Disables GC for this module.
    pub fn disable_gc(&mut self) {
        self.gc_enabled = false;
    }

    /// Enables GC for this module.
    pub fn enable_gc(&mut self) {
        self.gc_enabled = true;
    }
}

// ============================================================================
// GCConfig
// ============================================================================

/// Module-level GC configuration options.
#[derive(Debug, Clone)]
pub struct GCConfig {
    /// Whether to emit stack maps.
    pub emit_stack_maps: bool,

    /// Whether to insert safepoint polls on loop back-edges.
    pub insert_loop_polls: bool,

    /// Whether to rewrite statepoints for this GC.
    pub rewrite_statepoints: bool,

    /// Number of bytes for the card table.
    pub card_table_size: usize,

    /// Whether to emit write barriers for reference stores.
    pub emit_write_barriers: bool,

    /// Whether to emit read barriers for reference loads.
    pub emit_read_barriers: bool,

    /// Whether GC is exact (precise) vs. conservative.
    pub is_exact: bool,

    /// Safepoint poll frequency: 0 = every call, N = every Nth back-edge.
    pub poll_frequency: u32,

    /// Whether to use a separate GC thread.
    pub concurrent_gc: bool,

    /// GC initial heap size hint (in MB).
    pub initial_heap_size: u32,

    /// GC maximum heap size (in MB).
    pub max_heap_size: u32,
}

impl Default for GCConfig {
    fn default() -> Self {
        GCConfig {
            emit_stack_maps: true,
            insert_loop_polls: false,
            rewrite_statepoints: true,
            card_table_size: 0,
            emit_write_barriers: false,
            emit_read_barriers: false,
            is_exact: true,
            poll_frequency: 0,
            concurrent_gc: false,
            initial_heap_size: 16,
            max_heap_size: 1024,
        }
    }
}

impl GCConfig {
    /// Creates a config for a generational collector.
    pub fn for_generational() -> Self {
        GCConfig {
            emit_stack_maps: true,
            insert_loop_polls: true,
            rewrite_statepoints: true,
            card_table_size: 64 * 1024 * 1024 / CARD_SIZE as usize,
            emit_write_barriers: true,
            emit_read_barriers: false,
            is_exact: true,
            poll_frequency: 1,
            concurrent_gc: true,
            initial_heap_size: 16,
            max_heap_size: 4096,
        }
    }

    /// Creates a config for CoreCLR-style GC.
    pub fn for_coreclr() -> Self {
        GCConfig {
            emit_stack_maps: true,
            insert_loop_polls: true,
            rewrite_statepoints: true,
            card_table_size: 128 * 1024,
            emit_write_barriers: true,
            emit_read_barriers: false,
            is_exact: true,
            poll_frequency: 0,
            concurrent_gc: true,
            initial_heap_size: 16,
            max_heap_size: 0, // unlimited
        }
    }

    /// Creates a config for OCaml-style GC.
    pub fn for_ocaml() -> Self {
        GCConfig {
            emit_stack_maps: true,
            insert_loop_polls: true,
            rewrite_statepoints: false,
            card_table_size: 0,
            emit_write_barriers: true,
            emit_read_barriers: false,
            is_exact: true,
            poll_frequency: 2,
            concurrent_gc: false,
            initial_heap_size: 4,
            max_heap_size: 256,
        }
    }
}

// ============================================================================
// Stack Map Format
// ============================================================================

/// Header for the `.llvm_stackmaps` section.
#[derive(Debug, Clone)]
pub struct StackMapHeader {
    /// Version number (currently 3).
    pub version: u8,
    /// Reserved bytes (must be 0).
    pub reserved: [u8; 3],
}

impl Default for StackMapHeader {
    fn default() -> Self {
        StackMapHeader {
            version: STACK_MAP_VERSION,
            reserved: [0, 0, 0],
        }
    }
}

/// A record in the stack map section.
#[derive(Debug, Clone)]
pub enum StackMapRecord {
    /// A function record: maps function address to stack size.
    Function(FunctionRecord),

    /// A constant record: large constants shared across records.
    Constant(ConstantRecord),

    /// A location record: describes a single live value at a safepoint.
    Location(LocationRecord),
}

/// Function record in the stack map.
#[derive(Debug, Clone)]
pub struct FunctionRecord {
    /// The function address (relative to module base).
    pub function_address: u64,

    /// The stack size in bytes.
    pub stack_size: u64,

    /// Number of call-site records that follow.
    pub call_site_count: u64,
}

/// Constant record in the stack map.
#[derive(Debug, Clone)]
pub struct ConstantRecord {
    /// The constant value (up to 64 bits).
    pub value: u64,
}

/// Location record describing a live value.
#[derive(Debug, Clone)]
pub struct LocationRecord {
    /// Location kind: register, direct, indirect, constant.
    pub kind: LocationKind,
    /// Register number or offset.
    pub dwarf_reg_num_or_offset: u16,
    /// Reserved field.
    pub reserved: u16,
    /// Location size in bytes.
    pub size: u32,
    /// Offset within the value (for large values).
    pub offset: u16,
}

/// Kinds of stack map locations.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum LocationKind {
    /// Value is in a register.
    Register = 1,
    /// Value is at [base + offset].
    Direct = 2,
    /// Value is at [[base + offset]] (indirection).
    Indirect = 3,
    /// Value is a constant.
    Constant = 4,
    /// Value is a constant index into the constant pool.
    ConstantIndex = 5,
}

impl LocationKind {
    /// Parses a location kind from its encoded value.
    pub fn from_u8(v: u8) -> Option<LocationKind> {
        match v {
            1 => Some(LocationKind::Register),
            2 => Some(LocationKind::Direct),
            3 => Some(LocationKind::Indirect),
            4 => Some(LocationKind::Constant),
            5 => Some(LocationKind::ConstantIndex),
            _ => None,
        }
    }

    /// Returns the encoded value.
    pub fn to_u8(self) -> u8 {
        self as u8
    }
}

/// A full call-site record in the stack map.
#[derive(Debug, Clone)]
pub struct CallSiteRecord {
    /// The ID of this stack map / patchpoint.
    pub id: u64,

    /// Instruction offset from the start of the function.
    pub instruction_offset: u32,

    /// Reserved field (flags).
    pub flags: u16,

    /// Number of location records that follow.
    pub num_locations: u16,
}

/// Complete stack map for emission to the `.llvm_stackmaps` section.
#[derive(Debug, Clone)]
pub struct StackMap {
    /// Section header.
    pub header: StackMapHeader,

    /// Number of functions.
    pub num_functions: u32,

    /// Number of constants.
    pub num_constants: u32,

    /// Number of call sites.
    pub num_call_sites: u32,

    /// Function records.
    pub functions: Vec<FunctionRecord>,

    /// Constant records.
    pub constants: Vec<ConstantRecord>,

    /// Call-site records.
    pub call_sites: Vec<CallSiteRecord>,

    /// Location records (per-call-site).
    pub locations: Vec<Vec<LocationRecord>>,
}

impl StackMap {
    /// Creates an empty stack map.
    pub fn new() -> Self {
        StackMap {
            header: StackMapHeader::default(),
            num_functions: 0,
            num_constants: 0,
            num_call_sites: 0,
            functions: Vec::new(),
            constants: Vec::new(),
            call_sites: Vec::new(),
            locations: Vec::new(),
        }
    }

    /// Adds a function record.
    pub fn add_function(&mut self, func: FunctionRecord) {
        self.functions.push(func);
        self.num_functions = self.functions.len() as u32;
    }

    /// Adds a constant record.
    pub fn add_constant(&mut self, constant: ConstantRecord) {
        self.constants.push(constant);
        self.num_constants = self.constants.len() as u32;
    }

    /// Adds a call-site record with its location records.
    pub fn add_call_site(&mut self, call_site: CallSiteRecord, locs: Vec<LocationRecord>) {
        self.call_sites.push(call_site);
        self.locations.push(locs);
        self.num_call_sites = self.call_sites.len() as u32;
    }

    /// Returns the total size of the stack map in bytes (approximate).
    pub fn total_size(&self) -> usize {
        let header_size = 4; // 1 + 3 reserved
        let counts_size = 12; // 3 * u32
        let func_size = self.functions.len() * 24; // u64 + u64 + u64
        let const_size = self.constants.len() * 8;
        let cs_size = self.call_sites.len() * 20; // u64 + u32 + u16 + u16
        let loc_size: usize = self
            .locations
            .iter()
            .map(|locs| locs.len() * 12) // kind + reg + reserved + size + offset
            .sum();
        header_size + counts_size + func_size + const_size + cs_size + loc_size
    }

    /// Generates the binary representation of the stack map section.
    pub fn emit_bytes(&self) -> Vec<u8> {
        let mut bytes = Vec::new();
        // Header
        bytes.push(self.header.version);
        bytes.extend_from_slice(&self.header.reserved);
        // Padding to 8-byte alignment
        bytes.extend_from_slice(&[0u8; 4]);

        // Record counts
        bytes.extend_from_slice(&self.num_functions.to_le_bytes());
        bytes.extend_from_slice(&self.num_constants.to_le_bytes());
        bytes.extend_from_slice(&self.num_call_sites.to_le_bytes());

        // Function records
        for func in &self.functions {
            bytes.extend_from_slice(&func.function_address.to_le_bytes());
            bytes.extend_from_slice(&func.stack_size.to_le_bytes());
            bytes.extend_from_slice(&func.call_site_count.to_le_bytes());
        }

        // Constant records
        for c in &self.constants {
            bytes.extend_from_slice(&c.value.to_le_bytes());
        }

        // Call site records + locations
        for (cs, locs) in self.call_sites.iter().zip(self.locations.iter()) {
            bytes.extend_from_slice(&cs.id.to_le_bytes());
            bytes.extend_from_slice(&cs.instruction_offset.to_le_bytes());
            bytes.extend_from_slice(&cs.flags.to_le_bytes());
            bytes.extend_from_slice(&cs.num_locations.to_le_bytes());

            for loc in locs {
                bytes.push(loc.kind.to_u8());
                bytes.push(0); // padding
                bytes.extend_from_slice(&loc.dwarf_reg_num_or_offset.to_le_bytes());
                bytes.extend_from_slice(&loc.reserved.to_le_bytes());
                bytes.extend_from_slice(&loc.size.to_le_bytes());
                bytes.extend_from_slice(&loc.offset.to_le_bytes());
            }
        }

        bytes
    }

    /// Emits the stack map section as a string suitable for assembly output.
    pub fn emit_assembly(&self) -> String {
        let mut asm = String::new();
        asm.push_str(&format!(".section {}\n", STACK_MAP_SECTION));
        asm.push_str(&format!(".byte {}\n", self.header.version));
        asm.push_str(".byte 0, 0, 0\n"); // reserved
        asm.push_str(".align 8\n");
        asm.push_str(&format!(".long {}\n", self.num_functions));
        asm.push_str(&format!(".long {}\n", self.num_constants));
        asm.push_str(&format!(".long {}\n", self.num_call_sites));

        for func in &self.functions {
            asm.push_str(&format!(".quad {}\n", func.function_address));
            asm.push_str(&format!(".quad {}\n", func.stack_size));
            asm.push_str(&format!(".quad {}\n", func.call_site_count));
        }

        for c in &self.constants {
            asm.push_str(&format!(".quad {}\n", c.value));
        }

        for (cs, locs) in self.call_sites.iter().zip(self.locations.iter()) {
            asm.push_str(&format!(".quad {}\n", cs.id));
            asm.push_str(&format!(".long {}\n", cs.instruction_offset));
            asm.push_str(&format!(".short {}\n", cs.flags));
            asm.push_str(&format!(".short {}\n", cs.num_locations));

            for loc in locs {
                asm.push_str(&format!(".byte {}\n", loc.kind.to_u8()));
                asm.push_str(".byte 0\n");
                asm.push_str(&format!(".short {}\n", loc.dwarf_reg_num_or_offset));
                asm.push_str(&format!(".short {}\n", loc.reserved));
                asm.push_str(&format!(".long {}\n", loc.size));
                asm.push_str(&format!(".short {}\n", loc.offset));
            }
        }

        asm
    }
}

impl Default for StackMap {
    fn default() -> Self {
        StackMap::new()
    }
}

// ============================================================================
// Statepoint Lowering
// ============================================================================

/// Represents a `gc.statepoint` intrinsic that marks a call site
/// where GC may occur.
#[derive(Debug, Clone)]
pub struct Statepoint {
    /// Unique ID for this statepoint.
    pub id: u64,

    /// The call target that is wrapped.
    pub call_target: String,

    /// Number of call arguments.
    pub num_call_args: u32,

    /// Flags (e.g., deopt)
    pub flags: u32,

    /// The actual call instruction being wrapped.
    pub wrapped_call: String,

    /// The basic block containing this statepoint.
    pub block: String,

    /// The transition args (GC pointer base, derived pointers).
    pub gc_transition_args: Vec<u32>,

    /// Deoptimization state bundle args.
    pub deopt_args: Vec<i64>,

    /// GC live pointer args.
    pub gc_args: Vec<String>,
}

impl Statepoint {
    /// Creates a new statepoint for a call.
    pub fn new(
        id: u64,
        call_target: &str,
        num_call_args: u32,
        wrapped_call: &str,
    ) -> Self {
        Statepoint {
            id,
            call_target: call_target.to_string(),
            num_call_args,
            flags: 0,
            wrapped_call: wrapped_call.to_string(),
            block: String::new(),
            gc_transition_args: Vec::new(),
            deopt_args: Vec::new(),
            gc_args: Vec::new(),
        }
    }

    /// Adds a GC base pointer.
    pub fn add_base_ptr(&mut self, vreg: u32) {
        self.gc_transition_args.push(vreg);
    }

    /// Adds a GC derived pointer.
    pub fn add_derived_ptr(&mut self, vreg: u32) {
        self.gc_transition_args.push(vreg);
    }

    /// Adds a deoptimization argument.
    pub fn add_deopt_arg(&mut self, value: i64) {
        self.deopt_args.push(value);
    }

    /// Adds a GC live pointer.
    pub fn add_gc_arg(&mut self, reg: &str) {
        self.gc_args.push(reg.to_string());
    }

    /// Returns the total number of GC transition args.
    pub fn num_gc_transition_args(&self) -> usize {
        self.gc_transition_args.len()
    }

    /// Returns the total number of deopt args.
    pub fn num_deopt_args(&self) -> usize {
        self.deopt_args.len()
    }

    /// Returns true if this statepoint has deoptimization info.
    pub fn has_deopt(&self) -> bool {
        !self.deopt_args.is_empty()
    }

    /// Generates the LLVM IR text for this statepoint.
    pub fn to_ir(&self) -> String {
        let mut ir = String::new();
        ir.push_str(&format!(
            "  %sp{} = call token (i64, i32, {}, i32, ...) @llvm.experimental.gc.statepoint.p0(i64 {}, i32 {}, ",
            self.id,
            self.wrapped_call,
            self.id,
            self.num_call_args,
        ));
        ir.push_str(&format!("{}()", self.call_target));
        if !self.deopt_args.is_empty() {
            ir.push_str(", i32 0, ");
            for (i, arg) in self.deopt_args.iter().enumerate() {
                if i > 0 {
                    ir.push_str(", ");
                }
                ir.push_str(&format!("i32 {}", arg));
            }
        }
        for arg in &self.gc_args {
            ir.push_str(&format!(", {}* {}", self.call_target, arg));
        }
        ir.push(')');
        ir
    }
}

/// Represents a `gc.result` intrinsic that extracts the result
/// from a statepoint call.
#[derive(Debug, Clone)]
pub struct GCResult {
    /// The statepoint ID this result comes from.
    pub statepoint_id: u64,

    /// The result type.
    pub result_type: String,

    /// The virtual register holding the result.
    pub result_vreg: String,
}

impl GCResult {
    /// Creates a new GC result intrinsic.
    pub fn new(statepoint_id: u64, result_type: &str, result_vreg: &str) -> Self {
        GCResult {
            statepoint_id,
            result_type: result_type.to_string(),
            result_vreg: result_vreg.to_string(),
        }
    }

    /// Generates the LLVM IR for `gc.result`.
    pub fn to_ir(&self) -> String {
        format!(
            "  {} = call {} @llvm.experimental.gc.result(token %sp{})",
            self.result_vreg, self.result_type, self.statepoint_id
        )
    }
}

/// Represents a `gc.relocate` intrinsic that reloads a GC pointer
/// after a statepoint (since GC may have moved the object).
#[derive(Debug, Clone)]
pub struct GCRelocate {
    /// The statepoint ID.
    pub statepoint_id: u64,

    /// The base pointer index in the transition args.
    pub base_index: u32,

    /// The derived pointer index in the transition args.
    pub derived_index: u32,

    /// The type of the relocated pointer.
    pub pointer_type: String,

    /// The virtual register holding the relocated pointer.
    pub result_vreg: String,
}

impl GCRelocate {
    /// Creates a new GC relocate intrinsic.
    pub fn new(
        statepoint_id: u64,
        base_index: u32,
        derived_index: u32,
        pointer_type: &str,
        result_vreg: &str,
    ) -> Self {
        GCRelocate {
            statepoint_id,
            base_index,
            derived_index,
            pointer_type: pointer_type.to_string(),
            result_vreg: result_vreg.to_string(),
        }
    }

    /// Generates the LLVM IR for `gc.relocate`.
    pub fn to_ir(&self) -> String {
        format!(
            "  {} = call {} @llvm.experimental.gc.relocate(token %sp{}, i32 {}, i32 {})",
            self.result_vreg,
            self.pointer_type,
            self.statepoint_id,
            self.base_index,
            self.derived_index
        )
    }
}

// ============================================================================
// Statepoint Lowering Pass
// ============================================================================

/// Lowers abstract statepoints to machine-level stack maps and
/// spill/reload sequences.
#[derive(Debug, Clone)]
pub struct StatepointLowering {
    /// The GC strategy being lowered.
    pub strategy: GCStrategy,

    /// The stack map being built.
    pub stack_map: StackMap,

    /// Map from statepoint ID to spill slot offset.
    pub spill_slots: HashMap<u64, i32>,

    /// The next available spill slot offset.
    pub next_spill_offset: i32,

    /// Map from statepoint ID to its location records.
    pub statepoint_locations: HashMap<u64, Vec<LocationRecord>>,

    /// Number of statepoints lowered.
    pub lowered_count: usize,
}

impl StatepointLowering {
    /// Creates a new statepoint lowering instance.
    pub fn new(strategy: GCStrategy) -> Self {
        StatepointLowering {
            strategy,
            stack_map: StackMap::new(),
            spill_slots: HashMap::new(),
            next_spill_offset: 0,
            statepoint_locations: HashMap::new(),
            lowered_count: 0,
        }
    }

    /// Allocates a spill slot for a statepoint.
    pub fn allocate_spill_slot(&mut self, statepoint_id: u64) -> i32 {
        let slot = self.next_spill_offset;
        self.spill_slots.insert(statepoint_id, slot);
        self.next_spill_offset += 8;
        slot
    }

    /// Lowers a single statepoint to a call + stack map entry.
    pub fn lower_statepoint(&mut self, sp: &Statepoint, function_addr: u64) {
        // Allocate spill slots for GC args
        for gc_arg in &sp.gc_args {
            let slot = self.allocate_spill_slot(sp.id);
            // Emit spill: store gc_arg to stack slot
            // In practice, this would produce a MachineInstr::Store.
            let _ = slot;
        }

        // Create location records for each live GC pointer
        let mut locs = Vec::new();
        for (i, _gc_arg) in sp.gc_args.iter().enumerate() {
            let offset = self.spill_slots.get(&sp.id).copied().unwrap_or(0) + (i as i32 * 8);
            locs.push(LocationRecord {
                kind: LocationKind::Direct,
                dwarf_reg_num_or_offset: 6, // RBP on x86-64
                reserved: 0,
                size: 8,
                offset: offset.try_into().unwrap_or(0),
            });
        }

        self.statepoint_locations.insert(sp.id, locs.clone());

        // Add to stack map
        let cs = CallSiteRecord {
            id: sp.id,
            instruction_offset: 0, // will be patched
            flags: 0,
            num_locations: locs.len() as u16,
        };

        self.stack_map.add_call_site(cs, locs);
        self.lowered_count += 1;
    }

    /// Lowers a `gc.result` intrinsic: selects the result from the spill
    /// slot where the call return value was stored.
    pub fn lower_result(&self, result: &GCResult) -> String {
        let sp_id = result.statepoint_id;
        let spill_slot = self.spill_slots.get(&sp_id).copied().unwrap_or(0);
        format!(
            "  {} = load {}, i64* [rbp + {}]",
            result.result_vreg, result.result_type, spill_slot
        )
    }

    /// Lowers a `gc.relocate` intrinsic: loads the relocated pointer
    /// from the spill slot where it was saved.
    pub fn lower_relocate(&self, relocate: &GCRelocate) -> String {
        let sp_id = relocate.statepoint_id;
        let spill_slot = self
            .spill_slots
            .get(&sp_id)
            .copied()
            .unwrap_or(0);
        let slot = spill_slot + (relocate.base_index as i32 * 8);
        format!(
            "  {} = load {}*, i64* [rbp + {}]",
            relocate.result_vreg, relocate.pointer_type, slot
        )
    }

    /// Finalizes the stack map with function records.
    pub fn finalize(&mut self, function_addr: u64, stack_size: u64) {
        let func = FunctionRecord {
            function_address: function_addr,
            stack_size,
            call_site_count: self.lowered_count as u64,
        };
        self.stack_map.add_function(func);
    }

    /// Returns the assembled stack map bytes.
    pub fn emit_stack_map(&self) -> Vec<u8> {
        self.stack_map.emit_bytes()
    }

    /// Returns the stack map section assembly.
    pub fn emit_stack_map_assembly(&self) -> String {
        self.stack_map.emit_assembly()
    }
}

impl Default for StatepointLowering {
    fn default() -> Self {
        StatepointLowering::new(GCStrategy::StatepointExample)
    }
}

// ============================================================================
// PatchPoint
// ============================================================================

/// A PatchPoint represents a call site that can be patched at runtime
/// (e.g., for JIT recompilation, deoptimization, or inline cache).
#[derive(Debug, Clone)]
pub struct PatchPoint {
    /// Unique ID for this patch point.
    pub id: u64,

    /// The original call target.
    pub original_target: String,

    /// The number of bytes reserved for patching (nop sled).
    pub patch_size: u32,

    /// Instruction offset from function start.
    pub instruction_offset: u32,

    /// Whether this patch point is currently patched.
    pub is_patched: bool,

    /// The current patched target (if patched).
    pub patched_target: Option<String>,

    /// The basic block containing this patch point.
    pub block: String,

    /// Stack map ID for this patch point.
    pub stack_map_id: u64,

    /// Live GC values at this patch point.
    pub live_values: Vec<String>,

    /// Whether deoptimization is supported here.
    pub supports_deopt: bool,

    /// Whether this is a call patch point (vs. branch patch point).
    pub is_call: bool,
}

impl PatchPoint {
    /// Creates a new call patch point.
    pub fn new_call(id: u64, original_target: &str, patch_size: u32) -> Self {
        PatchPoint {
            id,
            original_target: original_target.to_string(),
            patch_size,
            instruction_offset: 0,
            is_patched: false,
            patched_target: None,
            block: String::new(),
            stack_map_id: id,
            live_values: Vec::new(),
            supports_deopt: false,
            is_call: true,
        }
    }

    /// Creates a new branch patch point.
    pub fn new_branch(id: u64, original_target: &str, patch_size: u32) -> Self {
        PatchPoint {
            id,
            original_target: original_target.to_string(),
            patch_size,
            instruction_offset: 0,
            is_patched: false,
            patched_target: None,
            block: String::new(),
            stack_map_id: id,
            live_values: Vec::new(),
            supports_deopt: false,
            is_call: false,
        }
    }

    /// Patches this patch point to a new target.
    pub fn patch(&mut self, new_target: &str) {
        self.patched_target = Some(new_target.to_string());
        self.is_patched = true;
    }

    /// Unpatches, restoring the original target.
    pub fn unpatch(&mut self) {
        self.patched_target = None;
        self.is_patched = false;
    }

    /// Returns the effective target.
    pub fn effective_target(&self) -> &str {
        self.patched_target
            .as_deref()
            .unwrap_or(&self.original_target)
    }

    /// Sets the instruction offset.
    pub fn with_offset(mut self, offset: u32) -> Self {
        self.instruction_offset = offset;
        self
    }

    /// Enables deoptimization support.
    pub fn with_deopt(mut self) -> Self {
        self.supports_deopt = true;
        self
    }

    /// Adds a live value reference.
    pub fn add_live_value(mut self, value: &str) -> Self {
        self.live_values.push(value.to_string());
        self
    }

    /// Generates the LLVM IR for this patch point.
    pub fn to_ir(&self) -> String {
        let mut ir = String::new();
        ir.push_str(&format!(
            "  %pp{} = call i64 @llvm.experimental.patchpoint.i64(i64 {}, i32 {}, ",
            self.id, self.id, self.patch_size
        ));
        ir.push_str(&format!(
            "i8* bitcast ({} @{} to i8*)",
            if self.is_call { "void ()*" } else { "i8*" },
            self.original_target
        ));
        for v in &self.live_values {
            ir.push_str(&format!(", i64 {}", v));
        }
        ir.push(')');
        ir
    }
}

// ============================================================================
// ShadowStack
// ============================================================================

/// A ShadowStack maintains a runtime-visible stack of GC roots.
/// Each frame pushes its roots on entry and pops them on exit.
#[derive(Debug, Clone)]
pub struct ShadowStack {
    /// The current shadow stack entries.
    pub entries: Vec<ShadowStackEntry>,

    /// Base pointer for current frame.
    pub frame_base: usize,

    /// Total number of roots tracked.
    pub total_roots_tracked: usize,

    /// Whether the shadow stack is initialized.
    pub initialized: bool,

    /// The strategy using this shadow stack.
    pub strategy: GCStrategy,
}

impl ShadowStack {
    /// Creates a new empty shadow stack.
    pub fn new(strategy: GCStrategy) -> Self {
        ShadowStack {
            entries: Vec::new(),
            frame_base: 0,
            total_roots_tracked: 0,
            initialized: false,
            strategy,
        }
    }

    /// Initializes the shadow stack for a function frame.
    pub fn init_frame(&mut self, frame_number: usize) {
        self.frame_base = self.entries.len();
        self.initialized = true;
        // Emit shadow-stack frame header
        self.entries.push(ShadowStackEntry {
            root: GCRoot::new_base(0, 0, "frame_header"),
            kind: ShadowStackEntryKind::FrameHeader,
            frame_number,
            is_live: true,
        });
    }

    /// Pushes a root onto the shadow stack.
    pub fn push_root(&mut self, root: GCRoot, frame_number: usize) {
        self.entries.push(ShadowStackEntry {
            root: root.clone(),
            kind: ShadowStackEntryKind::Root,
            frame_number,
            is_live: true,
        });
        self.total_roots_tracked += 1;
    }

    /// Pops all roots for the current frame.
    pub fn pop_frame(&mut self) -> Vec<GCRoot> {
        let mut popped = Vec::new();
        while let Some(entry) = self.entries.last() {
            if entry.kind == ShadowStackEntryKind::FrameHeader {
                self.entries.pop();
                break;
            }
            let entry = self.entries.pop().unwrap();
            popped.push(entry.root);
        }
        self.initialized = false;
        popped
    }

    /// Returns all currently live roots.
    pub fn live_roots(&self) -> Vec<&GCRoot> {
        self.entries
            .iter()
            .filter(|e| e.kind == ShadowStackEntryKind::Root && e.is_live)
            .map(|e| &e.root)
            .collect()
    }

    /// Walks the shadow stack and returns root pointers.
    pub fn walk(&self) -> Vec<&GCRoot> {
        self.live_roots()
    }
}

/// An entry in the shadow stack.
#[derive(Debug, Clone)]
pub struct ShadowStackEntry {
    /// The GC root stored at this entry.
    pub root: GCRoot,

    /// The kind of entry.
    pub kind: ShadowStackEntryKind,

    /// The frame number this entry belongs to.
    pub frame_number: usize,

    /// Whether this entry is currently live.
    pub is_live: bool,
}

/// Kinds of shadow stack entries.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ShadowStackEntryKind {
    /// Marks the beginning of a frame.
    FrameHeader,
    /// A regular GC root.
    Root,
    /// A callee-saved register root.
    CalleeSavedReg,
    /// End of frame marker.
    FrameFooter,
}

// ============================================================================
// OCaml GC
// ============================================================================

/// OCaml GC support: custom frame descriptors.
///
/// OCaml uses a generational GC with a minor heap (nursery) and a
/// major heap. Each stack frame has a frame descriptor that encodes
/// which stack slots contain GC roots using a compact bitmask.
#[derive(Debug, Clone)]
pub struct OCamlFrameDescriptor {
    /// The return address for this frame.
    pub return_address: u64,

    /// Frame size in words.
    pub frame_size: u16,

    /// Number of live roots in this frame.
    pub num_live_roots: u16,

    /// Bitmask of root offsets within the frame.
    pub root_bitmask: Vec<u64>,

    /// Whether this frame descriptor is valid.
    pub is_valid: bool,
}

impl OCamlFrameDescriptor {
    /// Creates a new OCaml frame descriptor.
    pub fn new(return_address: u64, frame_size: u16) -> Self {
        OCamlFrameDescriptor {
            return_address,
            frame_size,
            num_live_roots: 0,
            root_bitmask: Vec::new(),
            is_valid: false,
        }
    }

    /// Adds a root at the given word offset.
    pub fn add_root(&mut self, word_offset: u16) {
        let word_idx = word_offset as usize / 64;
        let bit_idx = word_offset as usize % 64;

        while self.root_bitmask.len() <= word_idx {
            self.root_bitmask.push(0);
        }

        self.root_bitmask[word_idx] |= 1u64 << bit_idx;
        self.num_live_roots += 1;
        self.is_valid = true;
    }

    /// Returns true if the given word offset is a root.
    pub fn is_root(&self, word_offset: u16) -> bool {
        if !self.is_valid {
            return false;
        }
        let word_idx = word_offset as usize / 64;
        let bit_idx = word_offset as usize % 64;
        if word_idx < self.root_bitmask.len() {
            (self.root_bitmask[word_idx] & (1u64 << bit_idx)) != 0
        } else {
            false
        }
    }

    /// Returns all root offsets in this frame.
    pub fn root_offsets(&self) -> Vec<u16> {
        let mut offsets = Vec::new();
        for (word_idx, &mask) in self.root_bitmask.iter().enumerate() {
            for bit_idx in 0..64 {
                if (mask & (1u64 << bit_idx)) != 0 {
                    offsets.push((word_idx * 64 + bit_idx) as u16);
                }
            }
        }
        offsets
    }

    /// Generates the C-compatible frame descriptor table entry.
    pub fn to_c_table_entry(&self) -> String {
        let bitmask_str: Vec<String> = self
            .root_bitmask
            .iter()
            .map(|m| format!("0x{:016x}", m))
            .collect();
        format!(
            "  {{ {}, {}, {}, {{{}}}, {} }}",
            self.return_address,
            self.frame_size,
            self.num_live_roots,
            bitmask_str.join(", "),
            self.is_valid
        )
    }
}

/// OCaml GC table: a collection of frame descriptors.
#[derive(Debug, Clone)]
pub struct OCamlGCTable {
    /// All frame descriptors, indexed by return address.
    pub descriptors: Vec<OCamlFrameDescriptor>,

    /// Lookup map from return address to descriptor index.
    pub addr_to_index: HashMap<u64, usize>,
}

impl OCamlGCTable {
    /// Creates a new empty OCaml GC table.
    pub fn new() -> Self {
        OCamlGCTable {
            descriptors: Vec::new(),
            addr_to_index: HashMap::new(),
        }
    }

    /// Adds a frame descriptor.
    pub fn add_descriptor(&mut self, desc: OCamlFrameDescriptor) -> usize {
        let index = self.descriptors.len();
        self.addr_to_index.insert(desc.return_address, index);
        self.descriptors.push(desc);
        index
    }

    /// Looks up a frame descriptor by return address.
    pub fn lookup(&self, return_address: u64) -> Option<&OCamlFrameDescriptor> {
        self.addr_to_index
            .get(&return_address)
            .and_then(|&idx| self.descriptors.get(idx))
    }

    /// Returns the total number of descriptors.
    pub fn len(&self) -> usize {
        self.descriptors.len()
    }

    /// Returns true if the table is empty.
    pub fn is_empty(&self) -> bool {
        self.descriptors.is_empty()
    }
}

impl Default for OCamlGCTable {
    fn default() -> Self {
        OCamlGCTable::new()
    }
}

// ============================================================================
// CoreCLR GC
// ============================================================================

/// CoreCLR GC support: GCInfo table with fully-interruptible and
/// partially-interruptible regions.
#[derive(Debug, Clone)]
pub struct CoreCLRGCInfo {
    /// Version of the GC info format.
    pub version: u32,

    /// The return address for the method.
    pub return_address: u64,

    /// Total method size in bytes.
    pub method_size: u32,

    /// Whether the method is fully interruptible.
    pub is_fully_interruptible: bool,

    /// Partially-interruptible regions (if not fully interruptible).
    pub interruptible_regions: Vec<CoreCLRInterruptibleRegion>,

    /// Map from instruction offset to set of live GC roots.
    pub live_slots: BTreeMap<u32, Vec<CoreCLRLiveSlot>>,

    /// Transitions for the GC info.
    pub transitions: Vec<CoreCLRTransition>,

    /// Whether this method has a security object.
    pub has_security_object: bool,

    /// Whether this method has a generational GC cookie.
    pub has_gen_cookie: bool,

    /// EPILOG information.
    pub epilog_count: u32,
}

impl CoreCLRGCInfo {
    /// Creates a new CoreCLR GC info entry.
    pub fn new(return_address: u64, method_size: u32) -> Self {
        CoreCLRGCInfo {
            version: 2,
            return_address,
            method_size,
            is_fully_interruptible: false,
            interruptible_regions: Vec::new(),
            live_slots: BTreeMap::new(),
            transitions: Vec::new(),
            has_security_object: false,
            has_gen_cookie: false,
            epilog_count: 0,
        }
    }

    /// Marks this method as fully interruptible.
    pub fn mark_fully_interruptible(&mut self) {
        self.is_fully_interruptible = true;
    }

    /// Adds an interruptible region.
    pub fn add_interruptible_region(&mut self, region: CoreCLRInterruptibleRegion) {
        self.interruptible_regions.push(region);
    }

    /// Adds a live slot mapping at a given offset.
    pub fn add_live_slot(&mut self, offset: u32, slot: CoreCLRLiveSlot) {
        self.live_slots.entry(offset).or_default().push(slot);
    }

    /// Adds a transition (safe-point transition in the GC info).
    pub fn add_transition(&mut self, transition: CoreCLRTransition) {
        self.transitions.push(transition);
    }

    /// Returns the live slots at a given instruction offset.
    pub fn live_slots_at(&self, offset: u32) -> Option<&Vec<CoreCLRLiveSlot>> {
        self.live_slots.get(&offset)
    }

    /// Encodes the GC info into a compact binary format.
    pub fn encode(&self) -> Vec<u8> {
        let mut data = Vec::new();
        data.extend_from_slice(&self.version.to_le_bytes());
        data.extend_from_slice(&self.return_address.to_le_bytes());
        data.extend_from_slice(&self.method_size.to_le_bytes());
        data.push(self.is_fully_interruptible as u8);
        data.push(self.has_security_object as u8);
        data.push(self.has_gen_cookie as u8);
        data.extend_from_slice(&self.epilog_count.to_le_bytes());

        // Encode interruptible regions
        data.extend_from_slice(&(self.interruptible_regions.len() as u32).to_le_bytes());
        for region in &self.interruptible_regions {
            data.extend_from_slice(&region.start_offset.to_le_bytes());
            data.extend_from_slice(&region.end_offset.to_le_bytes());
        }

        // Encode live slots
        data.extend_from_slice(&(self.live_slots.len() as u32).to_le_bytes());
        for (&offset, slots) in &self.live_slots {
            data.extend_from_slice(&offset.to_le_bytes());
            data.extend_from_slice(&(slots.len() as u32).to_le_bytes());
            for slot in slots {
                data.extend_from_slice(&slot.stack_offset.to_le_bytes());
                data.push(slot.is_byref as u8);
                data.push(slot.is_pinned as u8);
            }
        }

        // Encode transitions
        data.extend_from_slice(&(self.transitions.len() as u32).to_le_bytes());
        for t in &self.transitions {
            data.extend_from_slice(&t.instruction_offset.to_le_bytes());
            data.extend_from_slice(&t.code_offset.to_le_bytes());
            data.push(t.is_call_site as u8);
        }

        data
    }
}

/// A partially-interruptible region in CoreCLR GC info.
#[derive(Debug, Clone, Copy)]
pub struct CoreCLRInterruptibleRegion {
    /// Start instruction offset (inclusive).
    pub start_offset: u32,

    /// End instruction offset (exclusive).
    pub end_offset: u32,
}

/// A live GC slot in CoreCLR GC info.
#[derive(Debug, Clone, Copy)]
pub struct CoreCLRLiveSlot {
    /// Offset from the frame pointer.
    pub stack_offset: i32,

    /// Whether this slot holds a byref (interior pointer).
    pub is_byref: bool,

    /// Whether this slot is pinned (the object cannot be moved).
    pub is_pinned: bool,
}

/// A transition point in CoreCLR GC info.
#[derive(Debug, Clone, Copy)]
pub struct CoreCLRTransition {
    /// Instruction offset.
    pub instruction_offset: u32,

    /// Code offset in the GC info encoding.
    pub code_offset: u32,

    /// Whether this is a call site.
    pub is_call_site: bool,
}

// ============================================================================
// CoreCLR GC Table
// ============================================================================

/// A table of CoreCLR GC info records for a module.
#[derive(Debug, Clone)]
pub struct CoreCLRGCTable {
    /// All GC info entries.
    pub entries: Vec<CoreCLRGCInfo>,

    /// Lookup map from return address to info index.
    pub addr_to_index: HashMap<u64, usize>,
}

impl CoreCLRGCTable {
    /// Creates a new empty CoreCLR GC table.
    pub fn new() -> Self {
        CoreCLRGCTable {
            entries: Vec::new(),
            addr_to_index: HashMap::new(),
        }
    }

    /// Adds a GC info entry.
    pub fn add_entry(&mut self, info: CoreCLRGCInfo) -> usize {
        let index = self.entries.len();
        self.addr_to_index.insert(info.return_address, index);
        self.entries.push(info);
        index
    }

    /// Looks up GC info by return address.
    pub fn lookup(&self, return_address: u64) -> Option<&CoreCLRGCInfo> {
        self.addr_to_index
            .get(&return_address)
            .and_then(|&idx| self.entries.get(idx))
    }

    /// Returns the total number of entries.
    pub fn len(&self) -> usize {
        self.entries.len()
    }

    /// Returns true if the table is empty.
    pub fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }
}

impl Default for CoreCLRGCTable {
    fn default() -> Self {
        CoreCLRGCTable::new()
    }
}

// ============================================================================
// Erlang GC
// ============================================================================

/// Erlang (BEAM VM) GC: process stack with GC safe points.
///
/// Each Erlang process has its own heap and stack. GC works at the
/// process level: when a process needs more heap space, it performs
/// a GC that traces from the process's stack and registers.
#[derive(Debug, Clone)]
pub struct ErlangGCInfo {
    /// Process identifier.
    pub process_id: u64,

    /// Heap pointer for this process.
    pub heap_ptr: u64,

    /// Heap limit (high water mark).
    pub heap_limit: u64,

    /// Stack pointer for this process.
    pub stack_ptr: u64,

    /// Current number of reductions (used for scheduling).
    pub reductions: u64,

    /// GC safe point locations.
    pub safe_points: Vec<ErlangSafePoint>,

    /// Whether this process is currently in GC.
    pub in_gc: bool,

    /// Generation of the process heap.
    pub generation: u32,
}

impl ErlangGCInfo {
    /// Creates a new Erlang GC info for a process.
    pub fn new(process_id: u64) -> Self {
        ErlangGCInfo {
            process_id,
            heap_ptr: 0,
            heap_limit: 0,
            stack_ptr: 0,
            reductions: 0,
            safe_points: Vec::new(),
            in_gc: false,
            generation: 0,
        }
    }

    /// Adds a GC safe point.
    pub fn add_safe_point(&mut self, safe_point: ErlangSafePoint) {
        self.safe_points.push(safe_point);
    }

    /// Returns safe points within the given bytecode range.
    pub fn safe_points_in_range(
        &self,
        start: u32,
        end: u32,
    ) -> Vec<&ErlangSafePoint> {
        self.safe_points
            .iter()
            .filter(|sp| sp.bytecode_offset >= start && sp.bytecode_offset < end)
            .collect()
    }

    /// Checks if this process needs GC (heap above limit).
    pub fn needs_gc(&self) -> bool {
        self.heap_ptr >= self.heap_limit
    }

    /// Initiates GC for this process.
    pub fn start_gc(&mut self) {
        self.in_gc = true;
    }

    /// Finishes GC for this process.
    pub fn finish_gc(&mut self) {
        self.in_gc = false;
        self.generation += 1;
    }
}

/// A GC safe point in Erlang code.
#[derive(Debug, Clone)]
pub struct ErlangSafePoint {
    /// Bytecode offset of this safe point.
    pub bytecode_offset: u32,

    /// Whether this is a call safe point.
    pub is_call: bool,

    /// Whether this is a loop back-edge safe point.
    pub is_loop_backedge: bool,

    /// Whether this is a BIF (built-in function) safe point.
    pub is_bif: bool,

    /// The number of live X registers at this point.
    pub live_x_regs: u8,

    /// The number of live Y registers (stack slots) at this point.
    pub live_y_regs: u8,

    /// The stack words needed at this point.
    pub stack_need: u16,
}

impl ErlangSafePoint {
    /// Creates a new call safe point.
    pub fn new_call(bytecode_offset: u32, live_x: u8, live_y: u8) -> Self {
        ErlangSafePoint {
            bytecode_offset,
            is_call: true,
            is_loop_backedge: false,
            is_bif: false,
            live_x_regs: live_x,
            live_y_regs: live_y,
            stack_need: 0,
        }
    }

    /// Creates a new loop back-edge safe point.
    pub fn new_loop(bytecode_offset: u32, live_x: u8, live_y: u8) -> Self {
        ErlangSafePoint {
            bytecode_offset,
            is_call: false,
            is_loop_backedge: true,
            is_bif: false,
            live_x_regs: live_x,
            live_y_regs: live_y,
            stack_need: 0,
        }
    }

    /// Creates a new BIF safe point.
    pub fn new_bif(bytecode_offset: u32, live_x: u8, live_y: u8) -> Self {
        ErlangSafePoint {
            bytecode_offset,
            is_call: false,
            is_loop_backedge: false,
            is_bif: true,
            live_x_regs: live_x,
            live_y_regs: live_y,
            stack_need: 0,
        }
    }
}

// ============================================================================
// Write Barriers
// ============================================================================

/// Write barrier kinds for generational GC.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum WriteBarrierKind {
    /// No write barrier.
    None,
    /// Card marking: mark a card in the card table as dirty.
    CardMarking,
    /// Remembered set: add the written-to location to a remembered set.
    RememberedSet,
    /// Snapshot-at-the-beginning (SATB): log the old value before write.
    SATB,
    /// Yuasa-style barrier.
    Yuasa,
    /// Steele barrier.
    Steele,
}

impl WriteBarrierKind {
    pub fn as_str(&self) -> &'static str {
        match self {
            WriteBarrierKind::None => "none",
            WriteBarrierKind::CardMarking => "card_marking",
            WriteBarrierKind::RememberedSet => "remembered_set",
            WriteBarrierKind::SATB => "satb",
            WriteBarrierKind::Yuasa => "yuasa",
            WriteBarrierKind::Steele => "steele",
        }
    }
}

/// A write barrier inserted at a reference store site.
#[derive(Debug, Clone)]
pub struct WriteBarrier {
    /// The kind of write barrier.
    pub kind: WriteBarrierKind,

    /// The base object address being stored into.
    pub base_address: String,

    /// The field offset within the object.
    pub field_offset: i32,

    /// The new value being stored.
    pub new_value: String,

    /// The old value (for SATB barriers).
    pub old_value: Option<String>,

    /// The basic block containing this barrier.
    pub block: String,

    /// Whether this barrier is for an array element write.
    pub is_array_element: bool,
}

impl WriteBarrier {
    /// Creates a new card-marking write barrier.
    pub fn new_card_marking(
        base_address: &str,
        field_offset: i32,
        new_value: &str,
    ) -> Self {
        WriteBarrier {
            kind: WriteBarrierKind::CardMarking,
            base_address: base_address.to_string(),
            field_offset,
            new_value: new_value.to_string(),
            old_value: None,
            block: String::new(),
            is_array_element: false,
        }
    }

    /// Creates a new SATB write barrier.
    pub fn new_satb(
        base_address: &str,
        field_offset: i32,
        new_value: &str,
        old_value: &str,
    ) -> Self {
        WriteBarrier {
            kind: WriteBarrierKind::SATB,
            base_address: base_address.to_string(),
            field_offset,
            new_value: new_value.to_string(),
            old_value: Some(old_value.to_string()),
            block: String::new(),
            is_array_element: false,
        }
    }

    /// Generates the LLVM IR for this write barrier.
    pub fn to_ir(&self) -> String {
        match self.kind {
            WriteBarrierKind::CardMarking => self.emit_card_marking_ir(),
            WriteBarrierKind::SATB => self.emit_satb_ir(),
            WriteBarrierKind::RememberedSet => {
                format!(
                    "  call void @llvm_gc_write_barrier(i8* {}, i8* {})",
                    self.base_address, self.new_value
                )
            }
            WriteBarrierKind::None => String::new(),
            _ => format!(
                "  ; write barrier ({}): {}[{}] <- {}",
                self.kind.as_str(),
                self.base_address,
                self.field_offset,
                self.new_value
            ),
        }
    }

    fn emit_card_marking_ir(&self) -> String {
        let card_addr = format!(
            "  %card_addr = getelementptr i8, i8* @card_table, i64 (({} - @heap_base) / {})",
            self.base_address, CARD_SIZE
        );
        format!(
            "{}\n  store i8 1, i8* %card_addr",
            card_addr
        )
    }

    fn emit_satb_ir(&self) -> String {
        let old = self.old_value.as_deref().unwrap_or("null");
        format!(
            "  %old_{} = load i8*, i8** {}\n  call void @satb_enqueue(i8* %old_{})\n  store i8* {}, i8** {}",
            self.base_address.replace('%', ""),
            self.base_address,
            self.base_address.replace('%', ""),
            self.new_value,
            self.base_address
        )
    }
}

// ============================================================================
// Card Table
// ============================================================================

/// Manages a card table for generational GC write barriers.
#[derive(Debug, Clone)]
pub struct CardTable {
    /// The card table bytes (one byte per card).
    pub cards: Vec<u8>,

    /// The address of the heap start.
    pub heap_start: u64,

    /// The address of the heap end.
    pub heap_end: u64,

    /// Card size in bytes.
    pub card_size: u32,

    /// Number of cards.
    pub num_cards: u32,

    /// Whether byte-level marking is used.
    pub use_byte_map: bool,
}

impl CardTable {
    /// Creates a new card table covering the given heap range.
    pub fn new(heap_start: u64, heap_size: u64, card_size: u32) -> Self {
        let num_cards = ((heap_size + card_size as u64 - 1) / card_size as u64) as u32;
        let cards = vec![0u8; num_cards as usize];
        CardTable {
            cards,
            heap_start,
            heap_end: heap_start + heap_size,
            card_size,
            num_cards,
            use_byte_map: true,
        }
    }

    /// Returns the card index for a given heap address.
    pub fn card_index(&self, address: u64) -> Option<u32> {
        if address < self.heap_start || address >= self.heap_end {
            return None;
        }
        let offset = address - self.heap_start;
        let idx = (offset / self.card_size as u64) as u32;
        if idx < self.num_cards {
            Some(idx)
        } else {
            None
        }
    }

    /// Marks a card as dirty.
    pub fn mark_card(&mut self, address: u64) -> bool {
        if let Some(idx) = self.card_index(address) {
            self.cards[idx as usize] = 1;
            true
        } else {
            false
        }
    }

    /// Clears a card.
    pub fn clear_card(&mut self, address: u64) -> bool {
        if let Some(idx) = self.card_index(address) {
            self.cards[idx as usize] = 0;
            true
        } else {
            false
        }
    }

    /// Returns true if a card is dirty.
    pub fn is_dirty(&self, address: u64) -> bool {
        if let Some(idx) = self.card_index(address) {
            self.cards[idx as usize] != 0
        } else {
            false
        }
    }

    /// Scans all dirty cards and returns their addresses.
    pub fn dirty_cards(&self) -> Vec<u64> {
        self.cards
            .iter()
            .enumerate()
            .filter(|&(_, &dirty)| dirty != 0)
            .map(|(i, _)| self.heap_start + (i as u64 * self.card_size as u64))
            .collect()
    }

    /// Clears all cards (e.g., after a minor GC).
    pub fn clear_all(&mut self) {
        for c in &mut self.cards {
            *c = 0;
        }
    }

    /// Returns the number of dirty cards.
    pub fn dirty_count(&self) -> usize {
        self.cards.iter().filter(|&&c| c != 0).count()
    }

    /// Returns the total number of cards.
    pub fn total_cards(&self) -> u32 {
        self.num_cards
    }
}

// ============================================================================
// Remembered Set
// ============================================================================

/// A remembered set tracks old-to-young references for generational GC.
#[derive(Debug, Clone)]
pub struct RememberedSet {
    /// The entries in the remembered set (old-gen addresses).
    pub entries: Vec<u64>,

    /// Hash set for fast membership testing.
    pub hash_set: HashSet<u64>,

    /// Maximum size before overflow.
    pub max_size: usize,

    /// Whether the remembered set has overflowed.
    pub overflowed: bool,
}

impl RememberedSet {
    /// Creates a new empty remembered set.
    pub fn new(max_size: usize) -> Self {
        RememberedSet {
            entries: Vec::with_capacity(max_size),
            hash_set: HashSet::with_capacity(max_size),
            max_size,
            overflowed: false,
        }
    }

    /// Adds an address to the remembered set.
    pub fn add(&mut self, address: u64) -> bool {
        if self.overflowed {
            return false;
        }
        if self.hash_set.insert(address) {
            if self.entries.len() >= self.max_size {
                self.overflowed = true;
                return false;
            }
            self.entries.push(address);
            true
        } else {
            false
        }
    }

    /// Removes an address from the remembered set.
    pub fn remove(&mut self, address: u64) -> bool {
        if self.hash_set.remove(&address) {
            self.entries.retain(|&e| e != address);
            self.overflowed = false;
            true
        } else {
            false
        }
    }

    /// Returns true if the given address is in the set.
    pub fn contains(&self, address: u64) -> bool {
        self.hash_set.contains(&address)
    }

    /// Clears the remembered set.
    pub fn clear(&mut self) {
        self.entries.clear();
        self.hash_set.clear();
        self.overflowed = false;
    }

    /// Returns the number of entries.
    pub fn len(&self) -> usize {
        self.entries.len()
    }

    /// Returns true if the set is empty.
    pub fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }
}

// ============================================================================
// GCStrategy Selection
// ============================================================================

/// Selects and configures a GC strategy for a module.
#[derive(Debug, Clone)]
pub struct GCStrategySelector {
    /// All available strategies.
    pub available_strategies: Vec<GCStrategy>,

    /// The currently selected strategy.
    pub selected: GCStrategy,

    /// Whether custom strategy parameters are set.
    pub has_custom_params: bool,

    /// Per-strategy configuration.
    pub strategy_configs: HashMap<GCStrategy, GCConfig>,
}

impl GCStrategySelector {
    /// Creates a new selector with all strategies.
    pub fn new() -> Self {
        let mut configs = HashMap::new();
        configs.insert(GCStrategy::CoreCLR, GCConfig::for_coreclr());
        configs.insert(GCStrategy::OCaml, GCConfig::for_ocaml());

        GCStrategySelector {
            available_strategies: vec![
                GCStrategy::ShadowStack,
                GCStrategy::StatepointExample,
                GCStrategy::CoreCLR,
                GCStrategy::Erlang,
                GCStrategy::OCaml,
            ],
            selected: GCStrategy::default(),
            has_custom_params: false,
            strategy_configs: configs,
        }
    }

    /// Selects a strategy by name.
    pub fn select(&mut self, name: &str) -> Result<GCStrategy, String> {
        for s in &self.available_strategies {
            if s.name() == name {
                self.selected = *s;
                return Ok(*s);
            }
        }
        Err(format!("Unknown GC strategy: {}", name))
    }

    /// Returns the config for the selected strategy.
    pub fn current_config(&self) -> GCConfig {
        self.strategy_configs
            .get(&self.selected)
            .cloned()
            .unwrap_or_default()
    }

    /// Sets a custom config for the current strategy.
    pub fn set_custom_config(&mut self, config: GCConfig) {
        self.strategy_configs.insert(self.selected, config);
        self.has_custom_params = true;
    }

    /// Lists all available strategy names.
    pub fn list_strategies(&self) -> Vec<&'static str> {
        self.available_strategies
            .iter()
            .map(|s| s.name())
            .collect()
    }

    /// Returns true if the selected strategy uses statepoints.
    pub fn uses_statepoints(&self) -> bool {
        self.selected.uses_statepoints()
    }
}

impl Default for GCStrategySelector {
    fn default() -> Self {
        GCStrategySelector::new()
    }
}

// ============================================================================
// GC Safepoint Poll Insertion
// ============================================================================

/// Inserts GC safepoint polling code at function boundaries,
/// loop back-edges, and call sites.
#[derive(Debug, Clone)]
pub struct GCSafepointPoller {
    /// The GC strategy.
    pub strategy: GCStrategy,

    /// Poll frequency (0 = every back-edge, N = every Nth).
    pub poll_frequency: u32,

    /// Poll counter.
    pub poll_counter: u32,

    /// Whether polls have been inserted.
    pub inserted: bool,
}

impl GCSafepointPoller {
    /// Creates a new poller.
    pub fn new(strategy: GCStrategy, frequency: u32) -> Self {
        GCSafepointPoller {
            strategy,
            poll_frequency: frequency,
            poll_counter: 0,
            inserted: false,
        }
    }

    /// Decides whether to insert a poll at the current point.
    pub fn should_poll(&mut self, is_backedge: bool, is_call: bool) -> bool {
        if is_call && self.strategy.uses_cooperative_suspension() {
            return true;
        }
        if is_backedge && self.poll_frequency == 0 {
            return true;
        }
        if is_backedge {
            self.poll_counter += 1;
            if self.poll_counter >= self.poll_frequency {
                self.poll_counter = 0;
                return true;
            }
        }
        false
    }

    /// Generates the poll IR.
    pub fn emit_poll_ir(&self) -> String {
        match self.strategy {
            GCStrategy::CoreCLR => {
                "  %poll_addr = load i8*, i8** @g_polling_page\n  %poll_val = load volatile i8, i8* %poll_addr\n  ; CoreCLR GC poll".to_string()
            }
            GCStrategy::Erlang => {
                "  %need_gc = call i1 @erts_gc_needed()\n  br i1 %need_gc, label %gc_label, label %continue_label".to_string()
            }
            _ => {
                "  call void @llvm.experimental.gc.safepoint_poll()".to_string()
            }
        }
    }

    /// Marks the insertion as done.
    pub fn mark_inserted(&mut self) {
        self.inserted = true;
    }
}

// ============================================================================
// Stack Map Parser
// ============================================================================

/// Parses the `.llvm_stackmaps` section from an object file.
#[derive(Debug, Clone)]
pub struct StackMapParser {
    /// The raw bytes of the stack map section.
    pub raw_data: Vec<u8>,

    /// Parsed stack map.
    pub stack_map: Option<StackMap>,

    /// Whether parsing was successful.
    pub is_valid: bool,

    /// Parse error message, if any.
    pub error: Option<String>,
}

impl StackMapParser {
    /// Creates a new parser from raw bytes.
    pub fn new(data: Vec<u8>) -> Self {
        StackMapParser {
            raw_data: data,
            stack_map: None,
            is_valid: false,
            error: None,
        }
    }

    /// Parses the stack map section.
    pub fn parse(&mut self) -> Result<&StackMap, String> {
        if self.raw_data.len() < 16 {
            return Err("Stack map data too short".to_string());
        }

        let version = self.raw_data[0];
        if version != STACK_MAP_VERSION {
            return Err(format!(
                "Unsupported stack map version: {} (expected {})",
                version, STACK_MAP_VERSION
            ));
        }

        let mut offset = 8; // skip header + padding
        let num_functions = u32::from_le_bytes([
            self.raw_data[offset],
            self.raw_data[offset + 1],
            self.raw_data[offset + 2],
            self.raw_data[offset + 3],
        ]);
        offset += 4;
        let num_constants = u32::from_le_bytes([
            self.raw_data[offset],
            self.raw_data[offset + 1],
            self.raw_data[offset + 2],
            self.raw_data[offset + 3],
        ]);
        offset += 4;
        let num_call_sites = u32::from_le_bytes([
            self.raw_data[offset],
            self.raw_data[offset + 1],
            self.raw_data[offset + 2],
            self.raw_data[offset + 3],
        ]);
        offset += 4;

        let mut stack_map = StackMap::new();
        stack_map.num_functions = num_functions;
        stack_map.num_constants = num_constants;
        stack_map.num_call_sites = num_call_sites;

        // Parse function records
        for _ in 0..num_functions {
            if offset + 24 > self.raw_data.len() {
                return Err("Unexpected end of data in function records".to_string());
            }
            let mut fa = [0u8; 8];
            fa.copy_from_slice(&self.raw_data[offset..offset + 8]);
            offset += 8;
            let mut ss = [0u8; 8];
            ss.copy_from_slice(&self.raw_data[offset..offset + 8]);
            offset += 8;
            let mut csc = [0u8; 8];
            csc.copy_from_slice(&self.raw_data[offset..offset + 8]);
            offset += 8;

            stack_map.add_function(FunctionRecord {
                function_address: u64::from_le_bytes(fa),
                stack_size: u64::from_le_bytes(ss),
                call_site_count: u64::from_le_bytes(csc),
            });
        }

        // Parse constant records
        for _ in 0..num_constants {
            if offset + 8 > self.raw_data.len() {
                return Err("Unexpected end of data in constant records".to_string());
            }
            let mut cv = [0u8; 8];
            cv.copy_from_slice(&self.raw_data[offset..offset + 8]);
            offset += 8;
            stack_map.add_constant(ConstantRecord {
                value: u64::from_le_bytes(cv),
            });
        }

        // Parse call site records + locations
        for _ in 0..num_call_sites {
            if offset + 16 > self.raw_data.len() {
                return Err("Unexpected end of data in call site records".to_string());
            }
            let mut id = [0u8; 8];
            id.copy_from_slice(&self.raw_data[offset..offset + 8]);
            offset += 8;
            let mut io = [0u8; 4];
            io.copy_from_slice(&self.raw_data[offset..offset + 4]);
            offset += 4;
            let mut fl = [0u8; 2];
            fl.copy_from_slice(&self.raw_data[offset..offset + 2]);
            offset += 2;
            let mut nl = [0u8; 2];
            nl.copy_from_slice(&self.raw_data[offset..offset + 2]);
            offset += 2;

            let num_locs = u16::from_le_bytes(nl) as usize;
            let mut locs = Vec::with_capacity(num_locs);

            for _ in 0..num_locs {
                if offset + 12 > self.raw_data.len() {
                    return Err("Unexpected end of data in location records".to_string());
                }
                let kind_byte = self.raw_data[offset];
                offset += 1;
                let _padding = self.raw_data[offset]; // skip
                offset += 1;
                let mut drn = [0u8; 2];
                drn.copy_from_slice(&self.raw_data[offset..offset + 2]);
                offset += 2;
                let mut res = [0u8; 2];
                res.copy_from_slice(&self.raw_data[offset..offset + 2]);
                offset += 2;
                let mut sz = [0u8; 4];
                sz.copy_from_slice(&self.raw_data[offset..offset + 4]);
                offset += 4;
                let mut off = [0u8; 2];
                off.copy_from_slice(&self.raw_data[offset..offset + 2]);
                offset += 2;

                locs.push(LocationRecord {
                    kind: LocationKind::from_u8(kind_byte)
                        .unwrap_or(LocationKind::Register),
                    dwarf_reg_num_or_offset: u16::from_le_bytes(drn),
                    reserved: u16::from_le_bytes(res),
                    size: u32::from_le_bytes(sz),
                    offset: u16::from_le_bytes(off),
                });
            }

            stack_map.add_call_site(
                CallSiteRecord {
                    id: u64::from_le_bytes(id),
                    instruction_offset: u32::from_le_bytes(io),
                    flags: u16::from_le_bytes(fl),
                    num_locations: u16::from_le_bytes(nl),
                },
                locs,
            );
        }

        self.stack_map = Some(stack_map);
        self.is_valid = true;
        Ok(self.stack_map.as_ref().unwrap())
    }

    /// Looks up a stack map record by ID.
    pub fn lookup_call_site(&self, id: u64) -> Option<&CallSiteRecord> {
        self.stack_map
            .as_ref()?
            .call_sites
            .iter()
            .find(|cs| cs.id == id)
    }

    /// Returns the location records for a call site.
    pub fn location_records(&self, id: u64) -> Option<&Vec<LocationRecord>> {
        let stack_map = self.stack_map.as_ref()?;
        let index = stack_map
            .call_sites
            .iter()
            .position(|cs| cs.id == id)?;
        stack_map.locations.get(index)
    }
}

// ============================================================================
// GC Live Variable Analysis
// ============================================================================

/// Analyzes which variables are live at each safepoint.
#[derive(Debug, Clone)]
pub struct GCLiveAnalysis {
    /// Per-block live-in sets.
    pub live_in: HashMap<String, HashSet<u32>>,

    /// Per-block live-out sets.
    pub live_out: HashMap<String, HashSet<u32>>,

    /// Instruction-level liveness.
    pub live_at_inst: BTreeMap<usize, HashSet<u32>>,

    /// The function being analyzed.
    pub function_name: String,
}

impl GCLiveAnalysis {
    /// Creates a new analysis.
    pub fn new(function_name: &str) -> Self {
        GCLiveAnalysis {
            live_in: HashMap::new(),
            live_out: HashMap::new(),
            live_at_inst: BTreeMap::new(),
            function_name: function_name.to_string(),
        }
    }

    /// Adds a live-in set for a block.
    pub fn set_live_in(&mut self, block: &str, live: HashSet<u32>) {
        self.live_in.insert(block.to_string(), live);
    }

    /// Adds a live-out set for a block.
    pub fn set_live_out(&mut self, block: &str, live: HashSet<u32>) {
        self.live_out.insert(block.to_string(), live);
    }

    /// Records liveness at a specific instruction.
    pub fn set_live_at(&mut self, inst_idx: usize, live: HashSet<u32>) {
        self.live_at_inst.insert(inst_idx, live);
    }

    /// Returns the live variables at a given instruction.
    pub fn live_at(&self, inst_idx: usize) -> Option<&HashSet<u32>> {
        self.live_at_inst.get(&inst_idx)
    }

    /// Computes the union of all live variables.
    pub fn all_live(&self) -> HashSet<u32> {
        let mut all = HashSet::new();
        for live in self.live_at_inst.values() {
            all.extend(live);
        }
        all
    }
}

// ============================================================================
// GC Code Generation
// ============================================================================

/// Generates GC-related code (barriers, root tracking, safepoints).
#[derive(Debug, Clone)]
pub struct GCCodeGenerator {
    /// The module-level GC info.
    pub module_info: GCModuleInfo,

    /// Current function info (for code generation).
    pub current_function: Option<GCFunctionInfo>,

    /// The statepoint lowering pass.
    pub statepoint_lowering: StatepointLowering,

    /// The stack map being built.
    pub stack_map: StackMap,

    /// Inserted write barriers.
    pub write_barriers: Vec<WriteBarrier>,

    /// Inserted safepoints.
    pub safepoints: Vec<Statepoint>,
}

impl GCCodeGenerator {
    /// Creates a new GC code generator.
    pub fn new(strategy: GCStrategy, target_triple: &str) -> Self {
        GCCodeGenerator {
            module_info: GCModuleInfo::new(strategy, target_triple),
            current_function: None,
            statepoint_lowering: StatepointLowering::new(strategy),
            stack_map: StackMap::new(),
            write_barriers: Vec::new(),
            safepoints: Vec::new(),
        }
    }

    /// Begins a new function context.
    pub fn begin_function(&mut self, name: &str) {
        let func_info = GCFunctionInfo::new(name, self.module_info.strategy);
        self.current_function = Some(func_info);
    }

    /// Ends the current function context.
    pub fn end_function(&mut self) {
        if let Some(func) = self.current_function.take() {
            self.module_info.add_function(func);
        }
    }

    /// Adds a GC root to the current function.
    pub fn add_root(&mut self, root: GCRoot) {
        if let Some(ref mut func) = self.current_function {
            func.add_root(root);
        }
    }

    /// Inserts a statepoint at a call site.
    pub fn insert_statepoint(&mut self, sp: Statepoint) {
        self.safepoints.push(sp.clone());
        self.statepoint_lowering.lower_statepoint(&sp, 0);
    }

    /// Inserts a write barrier.
    pub fn insert_write_barrier(&mut self, barrier: WriteBarrier) {
        self.write_barriers.push(barrier);
    }

    /// Finalizes GC code generation for the module.
    pub fn finalize(&mut self) {
        // Finalize statepoint lowering
        for (name, func) in &self.module_info.functions {
            let _ = name;
            let _ = func;
        }
        self.stack_map = self.statepoint_lowering.stack_map.clone();
    }

    /// Returns the generated stack map bytes.
    pub fn emit_stack_map(&self) -> Vec<u8> {
        self.stack_map.emit_bytes()
    }

    /// Returns the generated stack map assembly text.
    pub fn emit_stack_map_assembly(&self) -> String {
        self.stack_map.emit_assembly()
    }
}

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

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

    #[test]
    fn test_gc_strategy_names() {
        assert_eq!(GCStrategy::ShadowStack.name(), "shadow-stack");
        assert_eq!(GCStrategy::StatepointExample.name(), "statepoint-example");
        assert_eq!(GCStrategy::CoreCLR.name(), "coreclr");
        assert_eq!(GCStrategy::Erlang.name(), "erlang");
        assert_eq!(GCStrategy::OCaml.name(), "ocaml");
    }

    #[test]
    fn test_gc_strategy_uses_statepoints() {
        assert!(!GCStrategy::ShadowStack.uses_statepoints());
        assert!(GCStrategy::StatepointExample.uses_statepoints());
        assert!(GCStrategy::CoreCLR.uses_statepoints());
        assert!(!GCStrategy::Erlang.uses_statepoints());
        assert!(!GCStrategy::OCaml.uses_statepoints());
    }

    #[test]
    fn test_gc_strategy_supports_generational() {
        assert!(GCStrategy::StatepointExample.supports_generational());
        assert!(GCStrategy::CoreCLR.supports_generational());
        assert!(GCStrategy::OCaml.supports_generational());
        assert!(!GCStrategy::ShadowStack.supports_generational());
        assert!(!GCStrategy::Erlang.supports_generational());
    }

    #[test]
    fn test_gc_root_new_base() {
        let root = GCRoot::new_base(1, 16, "i8*");
        assert_eq!(root.id, 1);
        assert_eq!(root.frame_offset, 16);
        assert!(root.is_base);
        assert!(!root.is_derived);
    }

    #[test]
    fn test_gc_root_new_derived() {
        let root = GCRoot::new_derived(2, 24, "i8*", 8);
        assert_eq!(root.id, 2);
        assert!(root.is_derived);
        assert!(!root.is_base);
        assert_eq!(root.interior_offset, 8);
    }

    #[test]
    fn test_gc_root_metadata() {
        let root = GCRoot::new_base(1, 16, "i8*")
            .with_type_metadata("java.lang.String")
            .with_language("java");
        assert_eq!(root.type_metadata, Some("java.lang.String".to_string()));
        assert_eq!(root.source_language, Some("java".to_string()));
    }

    #[test]
    fn test_gc_function_info_basic() {
        let mut info = GCFunctionInfo::new("test_func", GCStrategy::StatepointExample);
        assert_eq!(info.function_name, "test_func");
        assert_eq!(info.root_count(), 0);
        assert!(!info.analyzed);

        info.add_root(GCRoot::new_base(1, 0, "i8*"));
        assert_eq!(info.root_count(), 1);

        info.mark_analyzed();
        assert!(info.analyzed);
    }

    #[test]
    fn test_gc_function_info_safepoints() {
        let mut info = GCFunctionInfo::new("test_sp", GCStrategy::StatepointExample);
        let live_roots: HashSet<u32> = vec![1, 2, 3].into_iter().collect();
        let sp = SafepointLocation::new_call(0, 4, "entry", "malloc", live_roots.clone());
        info.add_safepoint(sp);

        assert_eq!(info.safepoint_count(), 1);
        assert_eq!(info.live_roots_at(0).len(), 3);
    }

    #[test]
    fn test_safepoint_location_call() {
        let live: HashSet<u32> = vec![1].into_iter().collect();
        let sp = SafepointLocation::new_call(5, 10, "bb1", "foo", live.clone());
        assert!(sp.is_call);
        assert_eq!(sp.call_target, Some("foo".to_string()));
        assert_eq!(sp.instruction_offset, 10);
    }

    #[test]
    fn test_safepoint_location_poll() {
        let live: HashSet<u32> = HashSet::new();
        let sp = SafepointLocation::new_poll(3, 8, "loop_header", live);
        assert!(!sp.is_call);
        assert!(sp.is_polling);
    }

    #[test]
    fn test_deopt_state_basic() {
        let mut ds = DeoptState::new(42, DeoptReason::BoundsCheck);
        ds.add_vreg(1, -8);
        ds.add_local(DeoptLocal {
            name: "i".to_string(),
            type_name: "int".to_string(),
            stack_offset: -8,
            is_reference: false,
        });
        assert_eq!(ds.bytecode_offset, 42);
        assert_eq!(ds.vreg_to_stack.len(), 1);
        assert_eq!(ds.live_locals.len(), 1);
    }

    #[test]
    fn test_deopt_reason_str() {
        assert_eq!(DeoptReason::None.as_str(), "none");
        assert_eq!(DeoptReason::SpeculativeGuard.as_str(), "speculative_guard");
        assert_eq!(DeoptReason::TypeCheck.as_str(), "type_check");
        assert_eq!(DeoptReason::BoundsCheck.as_str(), "bounds_check");
        assert_eq!(DeoptReason::NullCheck.as_str(), "null_check");
        assert_eq!(DeoptReason::DivZero.as_str(), "div_zero");
        assert_eq!(DeoptReason::ClassCheck.as_str(), "class_check");
        assert_eq!(DeoptReason::VirtualCall.as_str(), "virtual_call");
    }

    #[test]
    fn test_gc_module_info_basic() {
        let mut mod_info = GCModuleInfo::new(GCStrategy::CoreCLR, "x86_64-linux-gnu");
        assert!(mod_info.gc_enabled);
        assert_eq!(mod_info.strategy, GCStrategy::CoreCLR);

        let func_info = GCFunctionInfo::new("main", GCStrategy::CoreCLR);
        mod_info.add_function(func_info);
        assert!(mod_info.get_function("main").is_some());
        assert_eq!(mod_info.total_safepoints(), 0);
    }

    #[test]
    fn test_gc_config_default() {
        let config = GCConfig::default();
        assert!(config.emit_stack_maps);
        assert!(!config.insert_loop_polls);
        assert!(config.is_exact);
    }

    #[test]
    fn test_gc_config_generational() {
        let config = GCConfig::for_generational();
        assert!(config.emit_write_barriers);
        assert!(config.concurrent_gc);
        assert!(config.insert_loop_polls);
    }

    #[test]
    fn test_gc_config_coreclr() {
        let config = GCConfig::for_coreclr();
        assert!(config.emit_write_barriers);
        assert_eq!(config.max_heap_size, 0); // unlimited
    }

    #[test]
    fn test_gc_config_ocaml() {
        let config = GCConfig::for_ocaml();
        assert!(!config.rewrite_statepoints);
        assert!(config.emit_write_barriers);
        assert!(!config.concurrent_gc);
    }

    #[test]
    fn test_stack_map_empty() {
        let sm = StackMap::new();
        assert_eq!(sm.num_functions, 0);
        assert_eq!(sm.num_constants, 0);
        assert_eq!(sm.num_call_sites, 0);
        assert!(sm.emit_bytes().len() >= 16);
    }

    #[test]
    fn test_stack_map_add_function() {
        let mut sm = StackMap::new();
        sm.add_function(FunctionRecord {
            function_address: 0x1000,
            stack_size: 64,
            call_site_count: 2,
        });
        assert_eq!(sm.num_functions, 1);
    }

    #[test]
    fn test_stack_map_add_call_site() {
        let mut sm = StackMap::new();
        let locs = vec![LocationRecord {
            kind: LocationKind::Direct,
            dwarf_reg_num_or_offset: 6,
            reserved: 0,
            size: 8,
            offset: 16,
        }];
        sm.add_call_site(
            CallSiteRecord {
                id: 1,
                instruction_offset: 4,
                flags: 0,
                num_locations: 1,
            },
            locs,
        );
        assert_eq!(sm.num_call_sites, 1);
    }

    #[test]
    fn test_stack_map_assembly() {
        let mut sm = StackMap::new();
        sm.add_function(FunctionRecord {
            function_address: 0x4000,
            stack_size: 32,
            call_site_count: 1,
        });
        let asm = sm.emit_assembly();
        assert!(asm.contains(".llvm_stackmaps"));
        assert!(asm.contains(".quad 16384")); // 0x4000
    }

    #[test]
    fn test_statepoint_new() {
        let sp = Statepoint::new(1, "malloc", 1, "call_malloc");
        assert_eq!(sp.id, 1);
        assert_eq!(sp.call_target, "malloc");
        assert_eq!(sp.num_call_args, 1);
    }

    #[test]
    fn test_statepoint_with_gc_args() {
        let mut sp = Statepoint::new(2, "allocate", 2, "call_alloc");
        sp.add_base_ptr(1);
        sp.add_derived_ptr(2);
        sp.add_deopt_arg(42);
        sp.add_gc_arg("%obj");
        assert_eq!(sp.num_gc_transition_args(), 2);
        assert_eq!(sp.num_deopt_args(), 1);
    }

    #[test]
    fn test_gc_result_ir() {
        let result = GCResult::new(1, "i8*", "%r");
        let ir = result.to_ir();
        assert!(ir.contains("gc.result"));
        assert!(ir.contains("%sp1"));
    }

    #[test]
    fn test_gc_relocate_ir() {
        let reloc = GCRelocate::new(1, 0, 1, "i8*", "%r");
        let ir = reloc.to_ir();
        assert!(ir.contains("gc.relocate"));
        assert!(ir.contains("%sp1"));
    }

    #[test]
    fn test_statepoint_lowering_basic() {
        let mut lowering = StatepointLowering::new(GCStrategy::StatepointExample);
        let sp = Statepoint::new(1, "bar", 0, "call_bar");
        lowering.lower_statepoint(&sp, 0x1000);
        assert_eq!(lowering.lowered_count, 1);
    }

    #[test]
    fn test_statepoint_lowering_finalize() {
        let mut lowering = StatepointLowering::new(GCStrategy::StatepointExample);
        let sp = Statepoint::new(1, "foo", 0, "call_foo");
        lowering.lower_statepoint(&sp, 0x2000);
        lowering.finalize(0x2000, 48);
        assert_eq!(lowering.stack_map.num_functions, 1);
    }

    #[test]
    fn test_statepoint_lowering_spill_slot() {
        let mut lowering = StatepointLowering::new(GCStrategy::StatepointExample);
        let slot1 = lowering.allocate_spill_slot(1);
        let slot2 = lowering.allocate_spill_slot(1);
        assert_eq!(slot1, 0);
        assert_eq!(slot2, 8);
    }

    #[test]
    fn test_patch_point_call() {
        let pp = PatchPoint::new_call(1, "target_fn", 12);
        assert!(pp.is_call);
        assert_eq!(pp.original_target, "target_fn");
        assert_eq!(pp.patch_size, 12);
        assert!(!pp.is_patched);
    }

    #[test]
    fn test_patch_point_patch_unpatch() {
        let mut pp = PatchPoint::new_call(2, "original", 8);
        pp.patch("new_target");
        assert!(pp.is_patched);
        assert_eq!(pp.effective_target(), "new_target");

        pp.unpatch();
        assert!(!pp.is_patched);
        assert_eq!(pp.effective_target(), "original");
    }

    #[test]
    fn test_patch_point_with_deopt() {
        let pp = PatchPoint::new_branch(3, "fallback", 16)
            .with_deopt()
            .with_offset(32)
            .add_live_value("%x");
        assert!(pp.supports_deopt);
        assert_eq!(pp.instruction_offset, 32);
        assert_eq!(pp.live_values.len(), 1);
    }

    #[test]
    fn test_shadow_stack_init_frame() {
        let mut ss = ShadowStack::new(GCStrategy::ShadowStack);
        ss.init_frame(0);
        assert!(ss.initialized);
        assert_eq!(ss.entries.len(), 1);
    }

    #[test]
    fn test_shadow_stack_push_pop() {
        let mut ss = ShadowStack::new(GCStrategy::ShadowStack);
        ss.init_frame(1);
        let root = GCRoot::new_base(1, -8, "i8*");
        ss.push_root(root.clone(), 1);

        assert_eq!(ss.entries.len(), 2);
        let popped = ss.pop_frame();
        assert_eq!(popped.len(), 1);
        assert!(!ss.initialized);
    }

    #[test]
    fn test_shadow_stack_live_roots() {
        let mut ss = ShadowStack::new(GCStrategy::ShadowStack);
        ss.init_frame(0);
        ss.push_root(GCRoot::new_base(1, -8, "i8*"), 0);
        ss.push_root(GCRoot::new_base(2, -16, "i8*"), 0);
        assert_eq!(ss.live_roots().len(), 2);
    }

    #[test]
    fn test_ocaml_frame_descriptor_basic() {
        let mut desc = OCamlFrameDescriptor::new(0x4000, 16);
        assert!(!desc.is_valid);
        desc.add_root(0);
        desc.add_root(7);
        assert!(desc.is_valid);
        assert_eq!(desc.num_live_roots, 2);
        assert!(desc.is_root(0));
        assert!(desc.is_root(7));
        assert!(!desc.is_root(1));
    }

    #[test]
    fn test_ocaml_root_offsets() {
        let mut desc = OCamlFrameDescriptor::new(0x5000, 32);
        desc.add_root(0);
        desc.add_root(5);
        desc.add_root(10);
        let offsets = desc.root_offsets();
        assert_eq!(offsets.len(), 3);
        assert!(offsets.contains(&0));
        assert!(offsets.contains(&5));
        assert!(offsets.contains(&10));
    }

    #[test]
    fn test_ocaml_gc_table_add_lookup() {
        let mut table = OCamlGCTable::new();
        let desc = OCamlFrameDescriptor {
            return_address: 0x1000,
            frame_size: 8,
            num_live_roots: 1,
            root_bitmask: vec![1],
            is_valid: true,
        };
        table.add_descriptor(desc);
        assert_eq!(table.len(), 1);
        assert!(table.lookup(0x1000).is_some());
        assert!(table.lookup(0x2000).is_none());
    }

    #[test]
    fn test_coreclr_gc_info_basic() {
        let mut info = CoreCLRGCInfo::new(0x4000, 128);
        assert!(!info.is_fully_interruptible);
        info.mark_fully_interruptible();
        assert!(info.is_fully_interruptible);
    }

    #[test]
    fn test_coreclr_interruptible_region() {
        let mut info = CoreCLRGCInfo::new(0x5000, 256);
        info.add_interruptible_region(CoreCLRInterruptibleRegion {
            start_offset: 32,
            end_offset: 64,
        });
        assert_eq!(info.interruptible_regions.len(), 1);
    }

    #[test]
    fn test_coreclr_live_slots() {
        let mut info = CoreCLRGCInfo::new(0x6000, 100);
        info.add_live_slot(
            10,
            CoreCLRLiveSlot {
                stack_offset: -8,
                is_byref: false,
                is_pinned: false,
            },
        );
        let slots = info.live_slots_at(10).unwrap();
        assert_eq!(slots.len(), 1);
        assert_eq!(slots[0].stack_offset, -8);
    }

    #[test]
    fn test_coreclr_gc_info_encode() {
        let info = CoreCLRGCInfo::new(0x7000, 64);
        let encoded = info.encode();
        assert!(encoded.len() >= 20);
    }

    #[test]
    fn test_coreclr_gc_table() {
        let mut table = CoreCLRGCTable::new();
        let info = CoreCLRGCInfo::new(0x8000, 32);
        table.add_entry(info);
        assert_eq!(table.len(), 1);
        assert!(table.lookup(0x8000).is_some());
    }

    #[test]
    fn test_erlang_gc_info_basic() {
        let mut info = ErlangGCInfo::new(1);
        assert_eq!(info.process_id, 1);
        assert!(!info.in_gc);
    }

    #[test]
    fn test_erlang_safe_points() {
        let mut info = ErlangGCInfo::new(2);
        info.add_safe_point(ErlangSafePoint::new_call(10, 3, 2));
        info.add_safe_point(ErlangSafePoint::new_loop(20, 1, 0));
        info.add_safe_point(ErlangSafePoint::new_bif(30, 2, 1));

        assert_eq!(info.safe_points.len(), 3);
        assert_eq!(info.safe_points_in_range(10, 21).len(), 1);
    }

    #[test]
    fn test_erlang_needs_gc() {
        let mut info = ErlangGCInfo::new(3);
        info.heap_limit = 1024;
        info.heap_ptr = 512;
        assert!(!info.needs_gc());
        info.heap_ptr = 2048;
        assert!(info.needs_gc());
    }

    #[test]
    fn test_erlang_start_finish_gc() {
        let mut info = ErlangGCInfo::new(4);
        info.start_gc();
        assert!(info.in_gc);
        info.finish_gc();
        assert!(!info.in_gc);
        assert_eq!(info.generation, 1);
    }

    #[test]
    fn test_write_barrier_card_marking() {
        let wb = WriteBarrier::new_card_marking("%obj", 16, "%val");
        assert_eq!(wb.kind, WriteBarrierKind::CardMarking);
        let ir = wb.to_ir();
        assert!(ir.contains("card_table"));
    }

    #[test]
    fn test_write_barrier_satb() {
        let wb = WriteBarrier::new_satb("%obj", 16, "%new", "%old");
        assert_eq!(wb.kind, WriteBarrierKind::SATB);
        let ir = wb.to_ir();
        assert!(ir.contains("satb_enqueue"));
    }

    #[test]
    fn test_card_table_basic() {
        let mut ct = CardTable::new(0x10000, 65536, 512);
        assert_eq!(ct.total_cards(), 128);
        assert!(ct.mark_card(0x10000 + 0));
        assert!(ct.is_dirty(0x10000));
        assert!(!ct.is_dirty(0x10000 + 1024));
    }

    #[test]
    fn test_card_table_dirty_count() {
        let mut ct = CardTable::new(0x0, 4096, 256);
        ct.mark_card(0x0);
        ct.mark_card(0x200);
        ct.mark_card(0x400);
        assert_eq!(ct.dirty_count(), 3);
        ct.clear_all();
        assert_eq!(ct.dirty_count(), 0);
    }

    #[test]
    fn test_card_table_dirty_cards() {
        let mut ct = CardTable::new(0x0, 1024, 256);
        ct.mark_card(0x0);
        ct.mark_card(0x500);
        let dirty = ct.dirty_cards();
        assert_eq!(dirty.len(), 2);
    }

    #[test]
    fn test_remembered_set_add_contains() {
        let mut rs = RememberedSet::new(64);
        assert!(rs.add(0x1000));
        assert!(rs.contains(0x1000));
        assert!(!rs.contains(0x2000));
        assert_eq!(rs.len(), 1);
    }

    #[test]
    fn test_remembered_set_overflow() {
        let mut rs = RememberedSet::new(2);
        assert!(rs.add(1));
        assert!(rs.add(2));
        assert!(!rs.add(3)); // overflow
        assert!(rs.overflowed);
    }

    #[test]
    fn test_remembered_set_remove() {
        let mut rs = RememberedSet::new(8);
        rs.add(0x1000);
        rs.add(0x2000);
        assert!(rs.remove(0x1000));
        assert_eq!(rs.len(), 1);
        assert!(!rs.contains(0x1000));
    }

    #[test]
    fn test_gc_strategy_selector_select() {
        let mut selector = GCStrategySelector::new();
        assert!(selector.select("shadow-stack").is_ok());
        assert_eq!(selector.selected, GCStrategy::ShadowStack);

        assert!(selector.select("erlang").is_ok());
        assert_eq!(selector.selected, GCStrategy::Erlang);

        assert!(selector.select("unknown").is_err());
    }

    #[test]
    fn test_gc_strategy_selector_list() {
        let selector = GCStrategySelector::new();
        let list = selector.list_strategies();
        assert!(list.contains(&"shadow-stack"));
        assert!(list.contains(&"coreclr"));
        assert!(list.contains(&"ocaml"));
    }

    #[test]
    fn test_gc_safepoint_poller() {
        let mut poller = GCSafepointPoller::new(GCStrategy::StatepointExample, 0);
        assert!(poller.should_poll(true, false)); // back-edge, freq 0 → always
        assert!(!poller.should_poll(false, false)); // not back-edge, not call
    }

    #[test]
    fn test_gc_safepoint_poller_call() {
        let mut poller = GCSafepointPoller::new(GCStrategy::CoreCLR, 1);
        assert!(poller.should_poll(false, true)); // call always polls for CoreCLR
    }

    #[test]
    fn test_gc_safepoint_poller_erlang() {
        let poller = GCSafepointPoller::new(GCStrategy::Erlang, 0);
        let ir = poller.emit_poll_ir();
        assert!(ir.contains("erts_gc_needed"));
    }

    #[test]
    fn test_stack_map_parser_basic() {
        // Create valid stack map bytes
        let mut sm = StackMap::new();
        sm.add_function(FunctionRecord {
            function_address: 0x1000,
            stack_size: 32,
            call_site_count: 1,
        });
        sm.add_constant(ConstantRecord { value: 42 });
        let locs = vec![LocationRecord {
            kind: LocationKind::Register,
            dwarf_reg_num_or_offset: 5,
            reserved: 0,
            size: 8,
            offset: 0,
        }];
        sm.add_call_site(
            CallSiteRecord {
                id: 1,
                instruction_offset: 0,
                flags: 0,
                num_locations: 1,
            },
            locs,
        );

        let bytes = sm.emit_bytes();
        let mut parser = StackMapParser::new(bytes);
        let parsed = parser.parse();
        assert!(parsed.is_ok());
        assert!(parser.is_valid);
    }

    #[test]
    fn test_gc_live_analysis() {
        let mut analysis = GCLiveAnalysis::new("test_func");
        let live: HashSet<u32> = vec![1, 2].into_iter().collect();
        analysis.set_live_at(0, live.clone());
        analysis.set_live_at(1, live);

        assert!(analysis.live_at(0).is_some());
        assert_eq!(analysis.live_at(0).unwrap().len(), 2);
        assert!(analysis.live_at(99).is_none());
    }

    #[test]
    fn test_gc_live_analysis_all_live() {
        let mut analysis = GCLiveAnalysis::new("test2");
        let live1: HashSet<u32> = vec![1, 3].into_iter().collect();
        let live2: HashSet<u32> = vec![2, 3, 4].into_iter().collect();
        analysis.set_live_at(0, live1);
        analysis.set_live_at(1, live2);
        assert_eq!(analysis.all_live().len(), 4); // 1,2,3,4
    }

    #[test]
    fn test_gc_code_generator_basic() {
        let mut r#gen = GCCodeGenerator::new(GCStrategy::StatepointExample, "x86_64-unknown-linux-gnu");
        r#gen.begin_function("main");
        r#gen.add_root(GCRoot::new_base(1, -8, "i8*"));
        r#gen.end_function();

        assert!(r#gen.module_info.get_function("main").is_some());
    }

    #[test]
    fn test_gc_code_generator_safepoints() {
        let mut r#gen = GCCodeGenerator::new(GCStrategy::StatepointExample, "x86_64-unknown-linux-gnu");
        r#gen.begin_function("test_sp_func");
        let sp = Statepoint::new(1, "bar", 1, "call_bar");
        r#gen.insert_statepoint(sp);
        r#gen.end_function();

        assert_eq!(r#gen.safepoints.len(), 1);
    }

    #[test]
    fn test_gc_code_generator_write_barriers() {
        let mut r#gen = GCCodeGenerator::new(GCStrategy::CoreCLR, "x86_64-unknown-linux-gnu");
        let wb = WriteBarrier::new_card_marking("%ptr", 0, "%new_val");
        r#gen.insert_write_barrier(wb);
        assert_eq!(r#gen.write_barriers.len(), 1);
    }

    #[test]
    fn test_location_kind_conversion() {
        assert_eq!(LocationKind::from_u8(1), Some(LocationKind::Register));
        assert_eq!(LocationKind::from_u8(2), Some(LocationKind::Direct));
        assert_eq!(LocationKind::from_u8(3), Some(LocationKind::Indirect));
        assert_eq!(LocationKind::from_u8(4), Some(LocationKind::Constant));
        assert_eq!(LocationKind::from_u8(5), Some(LocationKind::ConstantIndex));
        assert_eq!(LocationKind::from_u8(99), None);
        assert_eq!(LocationKind::Register.to_u8(), 1);
        assert_eq!(LocationKind::Direct.to_u8(), 2);
    }

    #[test]
    fn test_stack_map_total_size() {
        let mut sm = StackMap::new();
        sm.add_function(FunctionRecord {
            function_address: 0x1000,
            stack_size: 64,
            call_site_count: 1,
        });
        let locs = vec![LocationRecord {
            kind: LocationKind::Direct,
            dwarf_reg_num_or_offset: 6,
            reserved: 0,
            size: 8,
            offset: 0,
        }];
        sm.add_call_site(
            CallSiteRecord {
                id: 1,
                instruction_offset: 0,
                flags: 0,
                num_locations: 1,
            },
            locs,
        );
        // 4(header) + 4(pad) + 12(counts) + 24(func) + 0(const) + 20(cs) + 12(loc)
        assert_eq!(sm.total_size(), 4 + 4 + 12 + 24 + 0 + 20 + 12);
    }

    #[test]
    fn test_patch_point_ir_generation() {
        let pp = PatchPoint::new_call(1, "my_func", 14)
            .add_live_value("%x")
            .add_live_value("%y");
        let ir = pp.to_ir();
        assert!(ir.contains("patchpoint"));
        assert!(ir.contains("my_func"));
        assert!(ir.contains("%x"));
        assert!(ir.contains("%y"));
    }

    #[test]
    fn test_statepoint_ir_generation() {
        let mut sp = Statepoint::new(1, "malloc", 1, "call_malloc");
        sp.add_gc_arg("%obj");
        sp.add_deopt_arg(0);
        let ir = sp.to_ir();
        assert!(ir.contains("gc.statepoint"));
        assert!(ir.contains("malloc"));
    }

    #[test]
    fn test_ocaml_frame_descriptor_to_c() {
        let mut desc = OCamlFrameDescriptor::new(0x4000, 8);
        desc.add_root(0);
        let entry = desc.to_c_table_entry();
        assert!(entry.contains("0x4000"));
        assert!(entry.contains("0x0000000000000001"));
    }
}