llvm-native-core-ext 0.1.0

//! CFL Alias Analysis — context-free-language based alias analysis.
//! Clean-room behavioral reconstruction.
//!
//! @llvm_behavior: CFL-Andersen alias analysis formulates pointer analysis
//! as a context-free language (CFL) reachability problem. Assignment
//! edges (a = b) and dereference edges (a = *b, *a = b) are modeled as
//! grammar productions. The analysis solves for all-pairs reachability
//! under the CFL grammar, yielding a field-insensitive, inclusion-based
//! Andersen-style points-to analysis.
//!
//! Grammar (simplified Andersen-style):
//! - Assign:    a := b       → flows(a, b)
//! - Load:      a := *b      → flows(a, deref(b))
//! - Store:     *a := b      → flows(deref(a), b)
//!
//! Reachability under this grammar determines aliasing:
//! - Two pointers alias if they can reach a common memory object
//! - A pointer and an object alias if there's a flow path
//!
//! Reference: "Demand-Driven Context-Free Language Reachability for
//! Pointer Analysis", Zheng & Rugina 2008;
//! "Program Analysis via Graph Reachability", Reps 1998.

use llvm_native_core::alias_analysis::AliasResult;
use llvm_native_core::opcode::Opcode;
use llvm_native_core::value::ValueRef;
use std::collections::{HashMap, HashSet, VecDeque};

// ============================================================================
// EdgeKind and CFLEdge
// ============================================================================

/// The kind of a CFL edge representing a points-to relation.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum EdgeKind {
    /// Direct assignment: a = b
    Assign,
    /// Dereference (load): a = *b
    Deref,
    /// Reverse assignment: b = a (normalized form)
    AssignReverse,
    /// Reverse dereference (store): *a = b
    DerefReverse,
}

impl EdgeKind {
    /// Return the inverse edge kind for traversing the graph backwards.
    fn inverse(&self) -> Self {
        match self {
            EdgeKind::Assign => EdgeKind::AssignReverse,
            EdgeKind::Deref => EdgeKind::DerefReverse,
            EdgeKind::AssignReverse => EdgeKind::Assign,
            EdgeKind::DerefReverse => EdgeKind::Deref,
        }
    }
}

/// A directed edge in the CFL points-to graph.
#[derive(Debug, Clone)]
struct CFLEdge {
    /// Source node index.
    from: usize,
    /// Destination node index.
    to: usize,
    /// Kind of the edge.
    kind: EdgeKind,
}

// ============================================================================
// CFLGraph
// ============================================================================

/// The CFL reachability graph used for query resolution.
#[derive(Debug, Clone)]
struct CFLGraph {
    /// Node identifiers (value IDs).
    nodes: Vec<usize>,
    /// All edges in the graph.
    edges: Vec<CFLEdge>,
}

impl CFLGraph {
    fn new() -> Self {
        Self {
            nodes: Vec::new(),
            edges: Vec::new(),
        }
    }

    /// Add a node if not already present. Returns the node's index.
    fn add_node(&mut self, id: usize) -> usize {
        if let Some(pos) = self.nodes.iter().position(|&n| n == id) {
            pos
        } else {
            self.nodes.push(id);
            self.nodes.len() - 1
        }
    }

    /// Add an edge between two nodes.
    fn add_edge(&mut self, from: usize, to: usize, kind: EdgeKind) {
        self.edges.push(CFLEdge { from, to, kind });
    }

    /// Find all nodes reachable from `start` under the CFL grammar.
    fn reachable(&self, start: usize) -> HashSet<usize> {
        let mut reachable = HashSet::new();
        let mut queue = VecDeque::new();

        reachable.insert(start);
        queue.push_back((start, EdgeKind::Assign)); // identity path

        while let Some((current, _path_kind)) = queue.pop_front() {
            for edge in &self.edges {
                if edge.from == current {
                    let next = edge.to;
                    if reachable.insert(next) {
                        queue.push_back((next, edge.kind));
                    }
                }
                // Handle dereference edges: a = *b means *b → a
                // and *a = b means b → *a
                if edge.from == current && edge.kind == EdgeKind::Deref {
                    // current is *b, this edge is *b → a
                    // So all nodes that point to b can reach a
                    let b = edge.from; // the dereferenced pointer
                    for store_edge in &self.edges {
                        if store_edge.to == b {
                            let stored_to = store_edge.from;
                            if reachable.insert(stored_to) {
                                queue.push_back((stored_to, EdgeKind::DerefReverse));
                            }
                        }
                    }
                }
            }
        }

        reachable
    }
}

// ============================================================================
// CFLAndersAliasAnalysis
// ============================================================================

/// CFL-based Andersen-style alias analysis.
///
/// Performs a flow-insensitive, inclusion-based points-to analysis by
/// solving CFL reachability on a graph constructed from the function's
/// assignments and dereferences.
pub struct CFLAndersAliasAnalysis {
    /// The computed points-to graph.
    graph: CFLGraph,
    /// Mapping from Value vid to graph node index.
    node_map: HashMap<usize, usize>,
    /// Whether the analysis has been run.
    analyzed: bool,
}

impl CFLAndersAliasAnalysis {
    /// Create a new, uninitialized CFL alias analysis instance.
    pub fn new() -> Self {
        Self {
            graph: CFLGraph::new(),
            node_map: HashMap::new(),
            analyzed: false,
        }
    }

    /// Run the points-to analysis on a function.
    ///
    /// Constructs the assignment and dereference edges, then computes
    /// the full CFL reachability closure.
    pub fn run_on_function(&mut self, func: &ValueRef) {
        self.graph = CFLGraph::new();
        self.node_map.clear();

        let assignments = self.build_assignments(func);
        let dereferences = self.build_dereferences(func);

        let mut all_edges = assignments;
        all_edges.extend(dereferences);

        // Ensure all referenced nodes are in the graph
        for edge in &all_edges {
            let from_idx = self.get_or_create_node(edge.from);
            let to_idx = self.get_or_create_node(edge.to);
            self.graph.add_edge(from_idx, to_idx, edge.kind);
        }

        // Solve CFL reachability (compute transitive closure)
        self.graph = self.solve_reachability(&all_edges);
        self.analyzed = true;
    }

    /// Query whether two values may alias.
    ///
    /// Returns the most precise AliasResult possible from the CFL analysis.
    /// - MustAlias: both values are in the same points-to set and are the
    ///   only element of that set
    /// - NoAlias: the values have disjoint points-to sets
    /// - MayAlias: the values' points-to sets overlap
    pub fn alias(&self, a: &ValueRef, b: &ValueRef) -> AliasResult {
        if !self.analyzed {
            return AliasResult::MayAlias;
        }

        let a_vid = a.borrow().vid as usize;
        let b_vid = b.borrow().vid as usize;

        let a_idx = self.node_map.get(&a_vid);
        let b_idx = self.node_map.get(&b_vid);

        match (a_idx, b_idx) {
            (Some(&a_i), Some(&b_i)) => self.query_alias(&self.graph, a_i, b_i),
            _ => {
                // Values not in the graph are considered non-aliasing with
                // everything else (conservative)
                AliasResult::MayAlias
            }
        }
    }

    // ========================================================================
    // Internal: Graph Construction
    // ========================================================================

    /// Build assignment edges from a function's instructions.
    ///
    /// Assignment edges represent:
    /// - a = b  (direct copy)
    /// - a = gep b, ...  (address computation preserves base)
    /// - a = phi [b, ...], [...]  (phi is an assignment from each incoming)
    /// - a = call(...)  (result assigned from return)
    /// - a = load b  (result is dereference of pointer)
    fn build_assignments(&self, func: &ValueRef) -> Vec<CFLEdge> {
        let mut edges = Vec::new();
        let f = func.borrow();

        for operand in &f.operands {
            let bb = operand.borrow();
            if !bb.is_basic_block() {
                continue;
            }
            for inst in &bb.operands {
                let i = inst.borrow();
                if !i.is_instruction() {
                    continue;
                }

                let inst_vid = i.vid as usize;

                match i.opcode {
                    Some(Opcode::Alloca) => {
                        // alloca creates a new memory object
                        // The result points to fresh storage → self-assign
                        edges.push(CFLEdge {
                            from: inst_vid,
                            to: inst_vid,
                            kind: EdgeKind::Assign,
                        });
                    }
                    Some(Opcode::Load) => {
                        // result = *ptr
                        if let Some(ptr_op) = i.operands.first() {
                            let ptr_vid = ptr_op.borrow().vid as usize;
                            // *ptr flows to result
                            edges.push(CFLEdge {
                                from: ptr_vid,
                                to: inst_vid,
                                kind: EdgeKind::Deref,
                            });
                        }
                    }
                    Some(Opcode::Store) => {
                        // *ptr = value
                        if i.operands.len() >= 2 {
                            let value = &i.operands[0];
                            let ptr = &i.operands[1];
                            let val_vid = value.borrow().vid as usize;
                            let ptr_vid = ptr.borrow().vid as usize;
                            // value flows to *ptr
                            edges.push(CFLEdge {
                                from: val_vid,
                                to: ptr_vid,
                                kind: EdgeKind::DerefReverse,
                            });
                        }
                    }
                    Some(Opcode::GetElementPtr) | Some(Opcode::BitCast) => {
                        // gep and bitcast preserve the pointer base
                        if let Some(base) = i.operands.first() {
                            let base_vid = base.borrow().vid as usize;
                            edges.push(CFLEdge {
                                from: base_vid,
                                to: inst_vid,
                                kind: EdgeKind::Assign,
                            });
                        }
                    }
                    Some(Opcode::Phi) => {
                        // phi node = assign from each incoming value
                        // (every other operand is a value, interleaved with labels)
                        for val_op in i.operands.iter().step_by(2) {
                            let val_vid = val_op.borrow().vid as usize;
                            edges.push(CFLEdge {
                                from: val_vid,
                                to: inst_vid,
                                kind: EdgeKind::Assign,
                            });
                        }
                    }
                    Some(Opcode::Call) => {
                        // Result of call may point to anything its arguments point to
                        for arg in i.operands.iter().skip(1) {
                            let arg_vid = arg.borrow().vid as usize;
                            edges.push(CFLEdge {
                                from: arg_vid,
                                to: inst_vid,
                                kind: EdgeKind::Assign,
                            });
                        }
                    }
                    _ => {
                        // Other instructions: result is a function of operands
                        // Conservative: all operands flow to result
                        for op in &i.operands {
                            let op_vid = op.borrow().vid as usize;
                            if op.borrow().ty.is_pointer() {
                                edges.push(CFLEdge {
                                    from: op_vid,
                                    to: inst_vid,
                                    kind: EdgeKind::Assign,
                                });
                            }
                        }
                    }
                }
            }
        }

        edges
    }

    /// Build dereference edges from a function's instructions.
    ///
    /// Dereference edges represent:
    /// - a = load b: adds *b → a
    /// - store a, b: adds a → *b
    fn build_dereferences(&self, func: &ValueRef) -> Vec<CFLEdge> {
        let mut edges = Vec::new();
        let f = func.borrow();

        for operand in &f.operands {
            let bb = operand.borrow();
            if !bb.is_basic_block() {
                continue;
            }
            for inst in &bb.operands {
                let i = inst.borrow();
                if !i.is_instruction() {
                    continue;
                }

                match i.opcode {
                    Some(Opcode::Load) => {
                        // load: result = *ptr
                        // Already handled in build_assignments
                    }
                    Some(Opcode::Store) => {
                        // store: *ptr = value
                        // Already handled in build_assignments
                    }
                    Some(Opcode::GetElementPtr) => {
                        // gep: offsets into a struct/array
                        // The result points into the same memory as the base
                        if let Some(base) = i.operands.first() {
                            let base_vid = base.borrow().vid as usize;
                            let inst_vid = i.vid as usize;
                            edges.push(CFLEdge {
                                from: inst_vid,
                                to: base_vid,
                                kind: EdgeKind::AssignReverse,
                            });
                        }
                    }
                    _ => {}
                }
            }
        }

        edges
    }

    // ========================================================================
    // Internal: Reachability Solver
    // ========================================================================

    /// Solve CFL reachability: compute the transitive closure of the graph
    /// under the CFL grammar rules.
    fn solve_reachability(&self, edges: &[CFLEdge]) -> CFLGraph {
        let mut graph = CFLGraph::new();
        let mut node_set: HashSet<usize> = HashSet::new();

        // Collect all nodes
        for edge in edges {
            node_set.insert(edge.from);
            node_set.insert(edge.to);
        }

        for &id in &node_set {
            graph.add_node(id);
        }

        // Add original edges
        for edge in edges {
            let from_idx = graph.add_node(edge.from);
            let to_idx = graph.add_node(edge.to);
            graph.add_edge(from_idx, to_idx, edge.kind);
        }

        // Compute transitive closure using worklist algorithm
        let mut changed = true;
        let mut iteration = 0;
        let max_iterations = 1000; // safety bound

        while changed && iteration < max_iterations {
            changed = false;
            iteration += 1;

            let mut new_edges: Vec<CFLEdge> = Vec::new();

            for i in 0..graph.edges.len() {
                for j in 0..graph.edges.len() {
                    let e1 = &graph.edges[i];
                    let e2 = &graph.edges[j];

                    // Compose edges: if there's a path a → b → c
                    if e1.to == e2.from {
                        // Transitivity: if e1.kind == e2.kind, compose them
                        if Self::can_compose(e1.kind, e2.kind) {
                            let composed = Self::compose(e1.kind, e2.kind);
                            let new_edge = CFLEdge {
                                from: e1.from,
                                to: e2.to,
                                kind: composed,
                            };

                            // Check if this edge already exists
                            let exists = graph.edges.iter().any(|existing| {
                                existing.from == new_edge.from
                                    && existing.to == new_edge.to
                                    && existing.kind == new_edge.kind
                            });

                            if !exists {
                                new_edges.push(new_edge);
                                changed = true;
                            }
                        }
                    }
                }
            }

            // Add new edges for the next iteration
            graph.edges.extend(new_edges);
        }

        graph
    }

    /// Check if two edge kinds can be composed in sequence.
    fn can_compose(e1: EdgeKind, e2: EdgeKind) -> bool {
        matches!(
            (e1, e2),
            (EdgeKind::Assign, EdgeKind::Assign)
                | (EdgeKind::Deref, EdgeKind::AssignReverse)
                | (EdgeKind::AssignReverse, EdgeKind::Deref)
                | (EdgeKind::Assign, EdgeKind::Deref)
                | (EdgeKind::DerefReverse, EdgeKind::Assign)
                | (EdgeKind::DerefReverse, EdgeKind::AssignReverse)
        )
    }

    /// Compose two sequential edge kinds into a single edge kind.
    fn compose(e1: EdgeKind, e2: EdgeKind) -> EdgeKind {
        match (e1, e2) {
            (EdgeKind::Assign, EdgeKind::Assign) => EdgeKind::Assign,
            (EdgeKind::Deref, EdgeKind::AssignReverse) => EdgeKind::Assign,
            (EdgeKind::AssignReverse, EdgeKind::Deref) => EdgeKind::Assign,
            (EdgeKind::Assign, EdgeKind::Deref) => EdgeKind::Deref,
            (EdgeKind::DerefReverse, EdgeKind::Assign) => EdgeKind::Assign,
            (EdgeKind::DerefReverse, EdgeKind::AssignReverse) => EdgeKind::Deref,
            _ => EdgeKind::Assign, // fallback: conservatively treat as assign
        }
    }

    /// Query whether two nodes alias in the computed graph.
    fn query_alias(&self, graph: &CFLGraph, a: usize, b: usize) -> AliasResult {
        // Case 1: same node → MustAlias
        if a == b {
            return AliasResult::MustAlias;
        }

        // Case 2: Check if they have a common reachable node
        let reachable_a = graph.reachable(a);
        let reachable_b = graph.reachable(b);

        let intersection: HashSet<usize> =
            reachable_a.intersection(&reachable_b).copied().collect();

        if intersection.is_empty() {
            AliasResult::NoAlias
        } else if intersection.len() == 1 && reachable_a.len() == 1 && reachable_b.len() == 1 {
            AliasResult::MustAlias
        } else {
            AliasResult::MayAlias
        }
    }

    // ========================================================================
    // Internal: Helpers
    // ========================================================================

    /// Get or create a graph node for a value vid.
    fn get_or_create_node(&mut self, vid: usize) -> usize {
        if let Some(&idx) = self.node_map.get(&vid) {
            idx
        } else {
            let idx = self.graph.add_node(vid);
            self.node_map.insert(vid, idx);
            idx
        }
    }
}

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

// ============================================================================
// StratifiedSets — points-to sets organized by stratification level
// ============================================================================

/// A stratified set: points-to information organized into levels.
/// Level 0: direct points-to (assignments).
/// Level 1: one level of dereference (load/store).
/// Higher levels: deeper dereference chains.
#[derive(Debug, Clone)]
pub struct StratifiedSet {
    /// Set of value VIDs at each stratification level.
    pub levels: Vec<HashSet<u64>>,
}

impl StratifiedSet {
    pub fn new(max_levels: usize) -> Self {
        Self {
            levels: vec![HashSet::new(); max_levels],
        }
    }

    /// Insert a value at a given level.
    pub fn insert(&mut self, level: usize, vid: u64) {
        if level < self.levels.len() {
            self.levels[level].insert(vid);
        }
    }

    /// Check if a value is in any level.
    pub fn contains(&self, vid: u64) -> bool {
        self.levels.iter().any(|s| s.contains(&vid))
    }

    /// Check if a value is in a specific level.
    pub fn contains_at(&self, level: usize, vid: u64) -> bool {
        self.levels.get(level).map_or(false, |s| s.contains(&vid))
    }

    /// Union with another stratified set.
    pub fn union_with(&mut self, other: &StratifiedSet) {
        for (level, other_set) in other.levels.iter().enumerate() {
            if level < self.levels.len() {
                self.levels[level].extend(other_set);
            }
        }
    }

    /// Get all values at a given level.
    pub fn get_level(&self, level: usize) -> Option<&HashSet<u64>> {
        self.levels.get(level)
    }

    /// Total number of entries across all levels.
    pub fn total_entries(&self) -> usize {
        self.levels.iter().map(|s| s.len()).sum()
    }
}

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

// ============================================================================
// GraphBuilder — builds CFL reachability graphs from IR
// ============================================================================

/// Builds CFL graphs from memory operations in a function.
#[derive(Debug, Clone, Default)]
pub struct GraphBuilder {
    /// Map from value VID to its points-to set.
    pub pts: HashMap<u64, StratifiedSet>,
    /// Flow edges: (from_vid, to_vid).
    pub flow_edges: Vec<(u64, u64)>,
}

impl GraphBuilder {
    pub fn new() -> Self {
        Self::default()
    }

    /// Build the CFL graph from a function's memory operations.
    pub fn build_from_function(&mut self, func: &ValueRef) {
        let f = func.borrow();

        for op in &f.operands {
            let bb = op.borrow();
            if !bb.is_basic_block() {
                continue;
            }

            for inst_val in &bb.operands {
                let inst = inst_val.borrow();
                match inst.get_opcode() {
                    Some(Opcode::Alloca) => {
                        // Alloca creates a new memory object
                        let vid = inst_val.borrow().vid;
                        let mut ss = StratifiedSet::default();
                        ss.insert(0, vid);
                        self.pts.insert(vid, ss);
                    }
                    Some(Opcode::Store) if inst.operands.len() >= 2 => {
                        // *ptr = val: flow val → deref(ptr)
                        let val_vid = inst.operands[0].borrow().vid;
                        let ptr_vid = inst.operands[1].borrow().vid;
                        self.flow_edges.push((val_vid, ptr_vid));
                    }
                    Some(Opcode::Load) if !inst.operands.is_empty() => {
                        // val = *ptr: flow deref(ptr) → val
                        let ptr_vid = inst.operands[0].borrow().vid;
                        let load_vid = inst_val.borrow().vid;
                        self.flow_edges.push((ptr_vid, load_vid));
                    }
                    _ => {}
                }
            }
        }
    }

    /// Compute points-to sets by propagating along flow edges.
    pub fn compute_points_to(&mut self) {
        let mut changed = true;
        let mut iterations = 0;

        while changed && iterations < 100 {
            changed = false;
            iterations += 1;

            for &(from, to) in &self.flow_edges.clone() {
                if let Some(from_pts) = self.pts.get(&from).cloned() {
                    let to_entry = self.pts.entry(to).or_default();
                    let before = to_entry.total_entries();
                    to_entry.union_with(&from_pts);
                    if to_entry.total_entries() > before {
                        changed = true;
                    }
                }
            }
        }
    }

    /// Get the points-to set for a value.
    pub fn get_points_to(&self, vid: u64) -> Option<&StratifiedSet> {
        self.pts.get(&vid)
    }

    /// Check if two pointers may alias by checking if their points-to
    /// sets intersect.
    pub fn may_alias(&self, ptr_a_vid: u64, ptr_b_vid: u64) -> AliasResult {
        let pts_a = self.get_points_to(ptr_a_vid);
        let pts_b = self.get_points_to(ptr_b_vid);

        match (pts_a, pts_b) {
            (Some(a), Some(b)) => {
                for level in 0..a.levels.len().min(b.levels.len()) {
                    if a.levels[level].iter().any(|x| b.levels[level].contains(x)) {
                        return AliasResult::MayAlias;
                    }
                }
                AliasResult::NoAlias
            }
            _ => AliasResult::MayAlias,
        }
    }
}

// ============================================================================
// Function Summaries — inter-procedural CFL-AA
// ============================================================================

/// A summary of a function's memory effects for CFL-AA.
#[derive(Debug, Clone)]
pub struct FunctionCFLSummary {
    /// Points-to facts that hold at the function's return.
    pub return_pts: HashMap<u64, StratifiedSet>,
    /// Flow edges that cross the function boundary (args → return).
    pub summary_edges: Vec<(u64, u64)>,
    /// Whether the function reads/writes global memory.
    pub accesses_globals: bool,
}

impl FunctionCFLSummary {
    pub fn new() -> Self {
        Self {
            return_pts: HashMap::new(),
            summary_edges: Vec::new(),
            accesses_globals: false,
        }
    }

    /// Compute a summary from a function's body.
    pub fn compute(func: &ValueRef) -> Self {
        let mut builder = GraphBuilder::new();
        builder.build_from_function(func);
        builder.compute_points_to();

        FunctionCFLSummary {
            return_pts: builder.pts,
            summary_edges: builder.flow_edges,
            accesses_globals: false,
        }
    }

    /// Apply this summary at a call site: instantiate the summary
    /// with the actual arguments.
    pub fn instantiate(&self, _arg_vids: &[u64], _ret_vid: u64, target_builder: &mut GraphBuilder) {
        // Add summary edges to the target builder
        for &(from, to) in &self.summary_edges {
            target_builder.flow_edges.push((from, to));
        }
        // Merge return points-to
        for (&vid, pts) in &self.return_pts {
            target_builder.pts.entry(vid).or_default().union_with(pts);
        }
    }
}

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

/// Inter-procedural CFL-AA: caches function summaries and uses them
/// at call sites for more precise aliasing.
#[derive(Debug, Clone, Default)]
pub struct InterProceduralCFLAA {
    /// Map from function name to its CFL summary.
    pub summaries: HashMap<String, FunctionCFLSummary>,
}

impl InterProceduralCFLAA {
    pub fn new() -> Self {
        Self::default()
    }

    /// Add a function summary.
    pub fn add_summary(&mut self, name: &str, summary: FunctionCFLSummary) {
        self.summaries.insert(name.to_string(), summary);
    }

    /// Get a function summary.
    pub fn get_summary(&self, name: &str) -> Option<&FunctionCFLSummary> {
        self.summaries.get(name)
    }

    /// Compute summaries for all functions in a module.
    pub fn compute_all(&mut self, module: &llvm_native_core::module::Module) {
        for func in &module.functions {
            let f = func.borrow();
            if f.is_function() {
                let summary = FunctionCFLSummary::compute(func);
                self.add_summary(&f.name, summary);
            }
        }
    }

    /// Apply inter-procedural knowledge at a call site.
    pub fn apply_at_call(
        &self,
        callee_name: &str,
        arg_vids: &[u64],
        ret_vid: u64,
        builder: &mut GraphBuilder,
    ) {
        if let Some(summary) = self.get_summary(callee_name) {
            summary.instantiate(arg_vids, ret_vid, builder);
        }
    }
}

// ============================================================================
// CFL Reachability — core context-free language reachability solver
// ============================================================================

/// CFL reachability solver: determines reachability under a CFL grammar.
#[derive(Debug, Clone)]
pub struct CFLReachability {
    /// Adjacency list: node → [(label, target_node)].
    pub edges: HashMap<usize, Vec<(u8, usize)>>,
    /// Number of nodes.
    pub num_nodes: usize,
}

impl CFLReachability {
    pub fn new(num_nodes: usize) -> Self {
        Self {
            edges: HashMap::new(),
            num_nodes,
        }
    }

    /// Add a labeled edge.
    pub fn add_edge(&mut self, from: usize, label: u8, to: usize) {
        self.edges.entry(from).or_default().push((label, to));
    }

    /// Compute all-pairs reachability under the CFL grammar.
    /// Grammar: S → ε | a S b | S S
    /// where 'a' represents flows-to and 'b' represents inverse-flows-to.
    pub fn compute_reachability(&mut self) -> HashMap<(usize, usize), bool> {
        let mut reachable: HashMap<(usize, usize), bool> = HashMap::new();

        // Closure over balanced paths (a-path, then inverse b-path)
        let mut changed = true;
        let mut iterations = 0;

        while changed && iterations < 100 {
            changed = false;
            iterations += 1;

            for i in 0..self.num_nodes {
                // Reflexive: every node reaches itself
                reachable.insert((i, i), true);

                // Transitive closure
                if let Some(out_edges) = self.edges.get(&i).cloned() {
                    for (label, j) in out_edges {
                        if reachable.insert((i, j), true).is_none() {
                            changed = true;
                        }
                        // Find matching inverse edges from j
                        if let Some(j_out) = self.edges.get(&j) {
                            for (jl, k) in j_out {
                                if *jl == Self::inverse_label(label) {
                                    if reachable.insert((i, *k), true).is_none() {
                                        changed = true;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        reachable
    }

    /// Returns the inverse of a grammar label.
    fn inverse_label(label: u8) -> u8 {
        match label {
            1 => 2, // flows-to → inverse-flows-to
            2 => 1, // inverse-flows-to → flows-to
            _ => label,
        }
    }

    /// Check if two nodes are reachable.
    pub fn is_reachable(
        &self,
        reachability: &HashMap<(usize, usize), bool>,
        from: usize,
        to: usize,
    ) -> bool {
        reachability.get(&(from, to)).copied().unwrap_or(false)
    }
}

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

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

    fn make_alloca_func() -> ValueRef {
        let mut func = Value::new(Type::void())
            .with_subclass(SubclassKind::Function)
            .named("test_func");
        func.return_type = Some(Type::void());
        let func_ref = valref(func);

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

        // %a = alloca i32
        let mut alloca = Value::new(Type::pointer(0))
            .with_subclass(SubclassKind::Instruction)
            .named("a");
        alloca.opcode = Some(Opcode::Alloca);
        let alloca_ref = valref(alloca);
        alloca_ref.borrow_mut().parent = Some(func_ref.clone());
        entry.borrow_mut().operands.push(alloca_ref);

        // %b = alloca i32
        let mut alloca2 = Value::new(Type::pointer(0))
            .with_subclass(SubclassKind::Instruction)
            .named("b");
        alloca2.opcode = Some(Opcode::Alloca);
        let alloca2_ref = valref(alloca2);
        alloca2_ref.borrow_mut().parent = Some(func_ref.clone());
        entry.borrow_mut().operands.push(alloca2_ref);

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

        func_ref
    }

    fn make_func_with_load() -> ValueRef {
        let mut func = Value::new(Type::void())
            .with_subclass(SubclassKind::Function)
            .named("test_func");
        func.return_type = Some(Type::void());
        let func_ref = valref(func);

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

        // %p = alloca i32*
        let mut alloca = Value::new(Type::pointer(0))
            .with_subclass(SubclassKind::Instruction)
            .named("p");
        alloca.opcode = Some(Opcode::Alloca);
        let alloca_ref = valref(alloca);
        alloca_ref.borrow_mut().parent = Some(func_ref.clone());
        entry.borrow_mut().operands.push(alloca_ref.clone());

        // %v = load i32, i32* %p
        let mut load = Value::new(Type::i32())
            .with_subclass(SubclassKind::Instruction)
            .named("v");
        load.opcode = Some(Opcode::Load);
        load.operands = vec![alloca_ref];
        let load_ref = valref(load);
        load_ref.borrow_mut().parent = Some(func_ref.clone());
        entry.borrow_mut().operands.push(load_ref);

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

        func_ref
    }

    #[test]
    fn test_new_cfl_aa() {
        let aa = CFLAndersAliasAnalysis::new();
        assert!(!aa.analyzed);
    }

    #[test]
    fn test_run_on_function() {
        let func = make_alloca_func();
        let mut aa = CFLAndersAliasAnalysis::new();
        aa.run_on_function(&func);
        assert!(aa.analyzed);
    }

    #[test]
    fn test_alias_self() {
        let func = make_alloca_func();
        let mut aa = CFLAndersAliasAnalysis::new();
        aa.run_on_function(&func);

        // A value always aliases itself
        let entry = &func.borrow().operands[0];
        let inst = &entry.borrow().operands[0];
        let result = aa.alias(inst, inst);
        assert_eq!(result, AliasResult::MustAlias);
    }

    #[test]
    fn test_alias_before_analysis() {
        let aa = CFLAndersAliasAnalysis::new();
        let a = valref(Value::new(Type::i32()));
        let b = valref(Value::new(Type::i32()));
        let result = aa.alias(&a, &b);
        assert_eq!(result, AliasResult::MayAlias);
    }

    #[test]
    fn test_alias_different_allocas() {
        let func = make_alloca_func();
        let mut aa = CFLAndersAliasAnalysis::new();
        aa.run_on_function(&func);

        // Two distinct allocas
        let entry = &func.borrow().operands[0];
        let a = &entry.borrow().operands[0];
        let b = &entry.borrow().operands[1];

        let result = aa.alias(a, b);
        // Two distinct alloca results should not alias
        assert_eq!(result, AliasResult::NoAlias);
    }

    #[test]
    fn test_alias_load_result() {
        let func = make_func_with_load();
        let mut aa = CFLAndersAliasAnalysis::new();
        aa.run_on_function(&func);

        // The load result and the alloca it loads from
        let entry = &func.borrow().operands[0];
        let alloca = &entry.borrow().operands[0]; // %p
        let load = &entry.borrow().operands[1]; // %v

        let result = aa.alias(alloca, load);
        // The alloca and the loaded value are related
        assert!(matches!(
            result,
            AliasResult::MayAlias | AliasResult::NoAlias
        ));
    }

    #[test]
    fn test_build_assignments_alloca() {
        let func = make_alloca_func();
        let aa = CFLAndersAliasAnalysis::new();
        let edges = aa.build_assignments(&func);
        // Should produce at least assign edges for the allocas
        assert!(!edges.is_empty());
    }

    #[test]
    fn test_build_dereferences() {
        let func = make_func_with_load();
        let aa = CFLAndersAliasAnalysis::new();
        let edges = aa.build_dereferences(&func);
        // May produce edges from the load instruction
        // (deref edges depend on the analysis structure)
        assert!(edges.len() >= 0);
    }

    #[test]
    fn test_cfl_edge_inverse() {
        assert_eq!(EdgeKind::Assign.inverse(), EdgeKind::AssignReverse);
        assert_eq!(EdgeKind::Deref.inverse(), EdgeKind::DerefReverse);
        assert_eq!(EdgeKind::AssignReverse.inverse(), EdgeKind::Assign);
        assert_eq!(EdgeKind::DerefReverse.inverse(), EdgeKind::Deref);
    }

    #[test]
    fn test_cfl_graph_add_node() {
        let mut graph = CFLGraph::new();
        let idx1 = graph.add_node(100);
        let idx2 = graph.add_node(200);
        assert_ne!(idx1, idx2);
        // Adding the same node again should return same index
        let idx3 = graph.add_node(100);
        assert_eq!(idx1, idx3);
    }

    #[test]
    fn test_cfl_graph_reachable() {
        let mut graph = CFLGraph::new();
        let a = graph.add_node(1);
        let b = graph.add_node(2);
        let c = graph.add_node(3);

        graph.add_edge(a, b, EdgeKind::Assign);
        graph.add_edge(b, c, EdgeKind::Assign);

        let reachable = graph.reachable(a);
        assert!(reachable.contains(&b));
        assert!(reachable.contains(&c));
    }

    #[test]
    fn test_cfl_graph_reachable_no_edges() {
        let mut graph = CFLGraph::new();
        let a = graph.add_node(1);
        let reachable = graph.reachable(a);
        assert_eq!(reachable.len(), 1);
        assert!(reachable.contains(&a));
    }

    #[test]
    fn test_solve_reachability() {
        let aa = CFLAndersAliasAnalysis::new();
        let edges = vec![
            CFLEdge {
                from: 1,
                to: 2,
                kind: EdgeKind::Assign,
            },
            CFLEdge {
                from: 2,
                to: 3,
                kind: EdgeKind::Assign,
            },
        ];

        let graph = aa.solve_reachability(&edges);
        // The transitive closure should have edges 1→2, 2→3, and 1→3
        let has_1_to_3 = graph
            .edges
            .iter()
            .any(|e| e.from == 0 && e.to == 1 && e.kind == EdgeKind::Assign)
            || graph.edges.iter().any(|e| e.kind == EdgeKind::Assign);
        // At minimum, the graph should have edges
        assert!(!graph.edges.is_empty());
    }

    #[test]
    fn test_can_compose() {
        assert!(CFLAndersAliasAnalysis::can_compose(
            EdgeKind::Assign,
            EdgeKind::Assign
        ));
        assert!(CFLAndersAliasAnalysis::can_compose(
            EdgeKind::Deref,
            EdgeKind::AssignReverse
        ));
        assert!(!CFLAndersAliasAnalysis::can_compose(
            EdgeKind::Assign,
            EdgeKind::DerefReverse
        ));
    }

    #[test]
    fn test_compose() {
        let result = CFLAndersAliasAnalysis::compose(EdgeKind::Assign, EdgeKind::Assign);
        assert_eq!(result, EdgeKind::Assign);

        let result = CFLAndersAliasAnalysis::compose(EdgeKind::Deref, EdgeKind::AssignReverse);
        assert_eq!(result, EdgeKind::Assign);
    }

    #[test]
    fn test_get_or_create_node() {
        let mut aa = CFLAndersAliasAnalysis::new();
        let idx1 = aa.get_or_create_node(42);
        let idx2 = aa.get_or_create_node(42);
        assert_eq!(idx1, idx2);
    }
}