weir/

cross_language.rs

//! `cross_language`  -  forward reachability that requires the flow to cross
//! at least one cross-language FFI edge anywhere on the source-to-sink path.
//!
//! The merged polyglot `ProgramGraph` (built upstream by
//! `surge_frontend::pipeline::merge_polyglot`) carries language-specific
//! `CALL_ARG` edges plus a small set of "FFI" edges that span
//! languages  -  Python `ctypes` → C symbol, JNI Java→C, N-API JS→C,
//! Rust `bindgen` Rust→C. The vanilla `flows_to` primitive treats
//! all edges identically and therefore fires on intra-language flows
//! that never cross a language boundary; this primitive constrains
//! the path to traverse at least one FFI edge so cross-language
//! detection is precise.
//!
//! Lowering shape (composes existing Tier-2.5 primitives):
//!
//! 1. **Source-side reach.** Run `bitset_fixpoint`-driven BFS from the source
//!    over the full graph. This models intra-language setup before a boundary
//!    crossing.
//! 2. **Mandatory FFI bridge.** Run `csr_forward_traverse` from the source-side
//!    reach set restricted to the `EDGE_KIND_FFI` mask. The output
//!    (`post_cross`) is exactly the callee-side nodes reached through at least
//!    one cross-language edge.
//! 3. **Free-form continuation.** Run `bitset_fixpoint`-driven BFS from
//!    `post_cross` over the full edge mask. The fixpoint output is the set of
//!    nodes the source can reach after crossing the language boundary.
//! 4. **Sink intersection.** AND the reach with the sink bitset; the
//!    output is non-empty iff some source reaches some sink across a
//!    language boundary.
//!
//! Soundness: [`MayOver`](super::soundness::Soundness::MayOver). The
//! BFS over-approximates calls (we model every FFI edge as
//! reachable, even when feature flags / arch gates would prune the
//! call site). Rules that need precision must compose with a
//! sanitizer-dominator filter.

#![allow(clippy::too_many_arguments)]
use vyre::ir::Program;
use vyre_foundation::execution_plan::fusion::fuse_programs;
use vyre_primitives::bitset::and::bitset_and;
use vyre_primitives::bitset::copy::bitset_copy;
use vyre_primitives::fixpoint::bitset_fixpoint::bitset_fixpoint_warm_start;
use vyre_primitives::graph::csr_forward_traverse::{bitset_words, csr_forward_traverse};
use vyre_primitives::graph::program_graph::ProgramGraphShape;

pub(crate) const OP_ID: &str = "weir::cross_language";

/// Edge-kind mask reserved for FFI / cross-language CALL_ARG edges.
/// Aligns with the `vyre_primitives::predicate::edge_kind` namespace
///  -  `0x10000` is the bit `surge_frontend::pipeline::merge_polyglot`
///     stamps onto every edge produced by the FFI binding tables.
pub const EDGE_KIND_FFI: u32 = 0x0001_0000;

/// Edge-kind mask covering "everything" (post-crossing flow uses any
/// edge). The exact value mirrors `csr_forward_traverse`'s "all"
/// dispatch convention.
pub const EDGE_KIND_ALL: u32 = 0xFFFF_FFFF;

/// Build the cross-language reach Program.
///
/// Buffer contract:
/// - `source`: per-node source bitset (input).
/// - `sink`: per-node sink bitset (input).
/// - `post_cross`: scratch bitset for stage-1 output.
/// - `current` / `next` / `changed` / `seed`: fixpoint scratch
///   buffers for stage-2 (provided by caller so the same buffers
///   can be reused across rules in one fused dispatch).
/// - `out`: per-node bitset, set iff a source reaches a sink across
///   at least one FFI edge.
///
/// # Errors
///
/// Returns an actionable fusion error if the composed CSR, fixpoint,
/// and bitset stages cannot be legally fused into one `vyre::Program`.
pub fn cross_language(
    node_count: u32,
    source: &str,
    sink: &str,
    post_cross: &str,
    current: &str,
    next: &str,
    changed: &str,
    seed: &str,
    out: &str,
) -> Result<Program, String> {
    let words = bitset_words(node_count);
    let edge_capacity = node_count
        .checked_mul(8)
        .map(|capacity| capacity.max(1))
        .ok_or_else(|| {
            format!(
                "Fix: cross-language reachability shape for node_count={node_count} exceeds u32 edge-capacity metadata. Partition the interprocedural graph before constructing the GPU program."
            )
        })?;
    let shape = ProgramGraphShape::new(node_count, edge_capacity);

    // Stage 1: reach every source-side setup node before the cross-language
    // boundary. Reusing the caller-owned fixpoint buffers keeps the ABI stable.
    let stage_source_seed = bitset_copy(seed, source, words);
    let stage_source_reach = bitset_fixpoint_warm_start(current, next, changed, seed, words);

    // Stage 2: take one mandatory cross-language bridge from any source-reached
    // node. This permits realistic paths such as source -> parser -> FFI call
    // -> C callee -> sink, while still rejecting all-single-language flows.
    let stage_bridge = csr_forward_traverse(shape, current, post_cross, EDGE_KIND_FFI);

    // Stage 3: copy the mandatory FFI-hop result into the caller-owned
    // fixpoint seed, then run free-form BFS-to-fixpoint from that seed.
    let stage_seed = bitset_copy(seed, post_cross, words);
    let stage_post_cross_reach = bitset_fixpoint_warm_start(current, next, changed, seed, words);

    // Stage 4: intersect `current` (the converged reach) with the
    // sink bitset to produce the final answer.
    let stage_sink = bitset_and(current, sink, out, words);

    let fused = fuse_programs(&[
        stage_source_seed,
        stage_source_reach,
        stage_bridge,
        stage_seed,
        stage_post_cross_reach,
        stage_sink,
    ])
    .map_err(|error| {
        format!(
            "Fix: cross-language reachability fusion failed for node_count={node_count}, words={words}: {error:?}"
        )
    })?;
    Ok(vyre_harness::region::tag_program(OP_ID, fused))
}

/// reference oracle: forward reach that requires at least one FFI edge in
/// the path. Inputs use the same conventions as
/// `csr_forward_traverse::cpu_ref` plus a parallel `edge_is_ffi`
/// bitset (per-edge: 1 if the edge is a cross-language FFI edge).
#[must_use]
#[cfg(any(test, feature = "cpu-parity"))]
#[deprecated(
    note = "reference oracle only; production code must dispatch the Weir Program on a concrete GPU backend or use weir::oracle for parity evidence"
)]
pub(crate) fn cpu_ref(
    node_count: u32,
    edge_offsets: &[u32],
    edge_targets: &[u32],
    edge_kind_mask: &[u32],
    edge_is_ffi: &[u32],
    source: &[u32],
    sink: &[u32],
) -> Vec<u32> {
    let nodes =
        usize::try_from(node_count).expect("cross_language_cpu_ref node_count must fit host usize");
    let words = nodes.checked_add(31).unwrap_or_else(|| {
        panic!(
            "cross_language_cpu_ref node_count={node_count} overflows host bitset word calculation. Fix: shard the oracle graph."
        )
    }) / 32;
    crate::dispatch_decode::require_csr_shape(
        "cross_language_cpu_ref",
        node_count,
        edge_offsets,
        edge_targets,
        edge_kind_mask,
    )
    .expect("cross_language cpu_ref oracle received malformed CSR graph");
    if edge_is_ffi.len() != edge_targets.len() {
        panic!(
            "cross_language cpu_ref oracle received malformed FFI edge mask: expected {} words, got {}",
            edge_targets.len(),
            edge_is_ffi.len()
        );
    }
    crate::dispatch_decode::require_bitset_words("cross_language_cpu_ref source", source, words)
        .expect("cross_language cpu_ref oracle received malformed source bitset");
    crate::dispatch_decode::require_bitset_words("cross_language_cpu_ref sink", sink, words)
        .expect("cross_language cpu_ref oracle received malformed sink bitset");
    let test = |bs: &[u32], n: u32| -> bool {
        let n = usize::try_from(n).expect("cross_language_cpu_ref bit index must fit usize");
        let w = n / 32;
        let b = n % 32;
        bs[w] & (1u32 << b) != 0
    };
    let mark = |bs: &mut [u32], n: u32| -> bool {
        let n = usize::try_from(n).expect("cross_language_cpu_ref bit index must fit usize");
        let w = n / 32;
        let b = n % 32;
        let mask = 1u32 << b;
        let was_set = bs[w] & mask != 0;
        if was_set {
            return false;
        }
        bs[w] |= 1u32 << b;
        true
    };

    // Stage 1: reach source-side setup nodes over all edges.
    let mut source_side_reach = vec![0u32; words];
    let mut queue = Vec::new();
    for n in 0..node_count {
        if test(source, n) && mark(&mut source_side_reach, n) {
            queue.push(n);
        }
    }
    let mut cursor = 0usize;
    while cursor < queue.len() {
        let n = queue[cursor];
        cursor += 1;
        let node = usize::try_from(n).expect("cross_language_cpu_ref node index must fit usize");
        let start = usize::try_from(edge_offsets[node])
            .expect("cross_language_cpu_ref CSR row start must fit usize");
        let end = usize::try_from(edge_offsets[node + 1])
            .expect("cross_language_cpu_ref CSR row end must fit usize");
        for i in start..end {
            let t = edge_targets[i];
            if t < node_count && mark(&mut source_side_reach, t) {
                queue.push(t);
            }
        }
    }

    // Stage 2: bridge from any source-reached node across one FFI edge.
    let mut post_cross = vec![0u32; words];
    queue.clear();
    for n in 0..node_count {
        if !test(&source_side_reach, n) {
            continue;
        }
        let node = usize::try_from(n).expect("cross_language_cpu_ref node index must fit usize");
        let start = usize::try_from(edge_offsets[node])
            .expect("cross_language_cpu_ref CSR row start must fit usize");
        let end = usize::try_from(edge_offsets[node + 1])
            .expect("cross_language_cpu_ref CSR row end must fit usize");
        for i in start..end {
            let kind = edge_kind_mask[i];
            let is_ffi = edge_is_ffi[i];
            if (kind & EDGE_KIND_FFI) != 0 || is_ffi != 0 {
                let t = edge_targets[i];
                if t < node_count && mark(&mut post_cross, t) {
                    queue.push(t);
                }
            }
        }
    }

    // Stage 3: BFS to fixpoint from post_cross via any edge. This is
    // queue-driven rather than graph-wide rescanning, so sparse
    // cross-language paths scale with reached edges instead of
    // `node_count * edge_count * diameter`.
    let mut reach = post_cross;
    let mut cursor = 0usize;
    while cursor < queue.len() {
        let n = queue[cursor];
        cursor += 1;
        let node = usize::try_from(n).expect("cross_language_cpu_ref node index must fit usize");
        let start = usize::try_from(edge_offsets[node])
            .expect("cross_language_cpu_ref CSR row start must fit usize");
        let end = usize::try_from(edge_offsets[node + 1])
            .expect("cross_language_cpu_ref CSR row end must fit usize");
        for i in start..end {
            let t = edge_targets[i];
            if t < node_count && mark(&mut reach, t) {
                queue.push(t);
            }
        }
    }

    // Stage 4: reach ∩ sink.
    let mut out = vec![0u32; words];
    for w in 0..words {
        out[w] = reach[w] & sink[w];
    }
    out
}

/// Soundness marker for [`cross_language`].
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct CrossLanguage;
impl super::soundness::SoundnessTagged for CrossLanguage {
    fn soundness(&self) -> super::soundness::Soundness {
        super::soundness::Soundness::MayOver
    }
}

fn release_witness_program() -> Program {
    match cross_language(
        4,
        "source",
        "sink",
        "post_cross",
        "current",
        "next",
        "changed",
        "seed",
        "out",
    ) {
        Ok(program) => program,
        Err(error) => {
            unreachable!("weir::cross_language fixed release witness must fuse; error={error}")
        }
    }
}

fn release_witness_inputs() -> Vec<Vec<Vec<u8>>> {
    let u32s = crate::dispatch_decode::pack_u32;
    vec![vec![
        u32s(&[0]),                           // seed
        u32s(&[0b0001]),                      // source
        u32s(&[0]),                           // current
        u32s(&[0]),                           // next
        u32s(&[0]),                           // changed
        u32s(&[0, 0, 0, 0]),                  // pg_nodes
        u32s(&[0, 1, 1, 1, 1]),               // pg_edge_offsets
        u32s(&[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), // pg_edge_targets
        u32s(&[EDGE_KIND_FFI, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), // pg_edge_kind_mask
        u32s(&[0, 0, 0, 0]),                  // pg_node_tags
        u32s(&[0]),                           // post_cross scratch
        u32s(&[0b0010]),                      // sink
        u32s(&[0]),                           // out
    ]]
}

fn release_witness_expected() -> Vec<Vec<Vec<u8>>> {
    let u32s = crate::dispatch_decode::pack_u32;
    vec![vec![
        u32s(&[0b0010]), // seed
        u32s(&[0b0011]), // current
        u32s(&[1]),      // changed
        u32s(&[0b0010]), // post_cross
        u32s(&[0b0010]), // out
    ]]
}

inventory::submit! {
    vyre_harness::OpEntry::new(
        OP_ID,
        release_witness_program,
        Some(release_witness_inputs),
        Some(release_witness_expected),
    )
}

#[cfg(test)]
#[allow(deprecated)]
mod tests {
    use super::*;

    fn one(n: u32) -> Vec<u32> {
        let w = n as usize / 32;
        let b = n as usize % 32;
        let mut v = vec![0u32; w + 1];
        v[w] = 1u32 << b;
        v
    }

    #[test]
    fn flow_through_ffi_edge_reaches_sink() {
        // Graph: 0 → (FFI) → 1 → (CALL_ARG) → 2.
        // Source = {0}, Sink = {2}. Expected: out has bit 2 set.
        let edge_offsets = vec![0, 1, 2, 2];
        let edge_targets = vec![1u32, 2];
        let edge_kind_mask = vec![EDGE_KIND_FFI, 0x1];
        let edge_is_ffi = vec![1u32, 0];
        let source = one(0);
        let sink = one(2);
        let out = cpu_ref(
            3,
            &edge_offsets,
            &edge_targets,
            &edge_kind_mask,
            &edge_is_ffi,
            &source,
            &sink,
        );
        assert!(out[0] & (1 << 2) != 0, "sink should be reached: {out:?}");
    }

    #[test]
    fn intra_language_flow_does_not_reach_sink() {
        // Graph: 0 → (CALL_ARG, NOT FFI) → 1 → (CALL_ARG) → 2.
        // No FFI hop anywhere  -  must not fire.
        let edge_offsets = vec![0, 1, 2, 2];
        let edge_targets = vec![1u32, 2];
        let edge_kind_mask = vec![0x1, 0x1];
        let edge_is_ffi = vec![0u32, 0];
        let source = one(0);
        let sink = one(2);
        let out = cpu_ref(
            3,
            &edge_offsets,
            &edge_targets,
            &edge_kind_mask,
            &edge_is_ffi,
            &source,
            &sink,
        );
        assert_eq!(out, vec![0u32], "no FFI hop → no cross-lang reach: {out:?}");
    }

    #[test]
    fn ffi_edge_after_intra_language_setup_reaches_sink() {
        // Graph: 0 → (CALL_ARG) → 1 → (FFI) → 2 → (CALL_ARG) → 3.
        // First hop is intra-language; FFI is at hop 2. Cross-language
        // reachability requires an FFI bridge anywhere on the path.
        let edge_offsets = vec![0, 1, 2, 3, 3];
        let edge_targets = vec![1u32, 2, 3];
        let edge_kind_mask = vec![0x1, EDGE_KIND_FFI, 0x1];
        let edge_is_ffi = vec![0u32, 1, 0];
        let source = one(0);
        let sink = one(3);
        let out = cpu_ref(
            4,
            &edge_offsets,
            &edge_targets,
            &edge_kind_mask,
            &edge_is_ffi,
            &source,
            &sink,
        );
        assert!(
            out[0] & (1 << 3) != 0,
            "FFI bridge after intra-language setup should reach sink: {out:?}"
        );
    }

    #[test]
    fn empty_source_yields_empty_output() {
        let edge_offsets = vec![0, 1, 1];
        let edge_targets = vec![1u32];
        let edge_kind_mask = vec![EDGE_KIND_FFI];
        let edge_is_ffi = vec![1u32];
        let source = vec![0u32];
        let sink = one(1);
        let out = cpu_ref(
            2,
            &edge_offsets,
            &edge_targets,
            &edge_kind_mask,
            &edge_is_ffi,
            &source,
            &sink,
        );
        assert_eq!(out, vec![0u32]);
    }

    #[test]
    fn multi_step_post_cross_continuation_reaches_distant_sink() {
        // Graph: 0 → (FFI) → 1 → (CALL_ARG) → 2 → (CALL_ARG) → 3.
        // FFI happens at hop 1; further hops are free-form.
        let edge_offsets = vec![0, 1, 2, 3, 3];
        let edge_targets = vec![1u32, 2, 3];
        let edge_kind_mask = vec![EDGE_KIND_FFI, 0x1, 0x1];
        let edge_is_ffi = vec![1u32, 0, 0];
        let source = one(0);
        let sink = one(3);
        let out = cpu_ref(
            4,
            &edge_offsets,
            &edge_targets,
            &edge_kind_mask,
            &edge_is_ffi,
            &source,
            &sink,
        );
        assert!(out[0] & (1 << 3) != 0, "distant sink reachable: {out:?}");
    }

    #[test]
    fn op_id_is_canonical() {
        assert_eq!(OP_ID, "weir::cross_language");
    }

    #[test]
    fn release_witness_matches_fused_program_buffer_contract() {
        let program = release_witness_program();
        let buffer_names = program
            .buffers()
            .iter()
            .map(|buffer| buffer.name())
            .collect::<Vec<_>>();
        assert_eq!(
            buffer_names,
            vec![
                "seed",
                "source",
                "current",
                "next",
                "changed",
                "pg_nodes",
                "pg_edge_offsets",
                "pg_edge_targets",
                "pg_edge_kind_mask",
                "pg_node_tags",
                "post_cross",
                "sink",
                "out",
            ],
            "release witness inputs must follow fused Program::buffers order"
        );

        let inputs = release_witness_inputs();
        let case = &inputs[0];
        assert_eq!(case.len(), program.buffers().len());
        for (buffer, bytes) in program.buffers().iter().zip(case.iter()) {
            let expected = buffer
                .static_byte_len()
                .expect("release witness buffers must have valid static lengths")
                .expect("release witness buffers must be statically sized");
            assert_eq!(
                bytes.len(),
                expected,
                "release witness buffer `{}` has wrong byte length",
                buffer.name()
            );
        }

        let writable_names = program
            .buffers()
            .iter()
            .filter(|buffer| {
                matches!(
                    buffer.access(),
                    vyre::ir::BufferAccess::ReadWrite | vyre::ir::BufferAccess::WriteOnly
                )
            })
            .map(|buffer| buffer.name())
            .collect::<Vec<_>>();
        assert_eq!(
            writable_names,
            vec!["seed", "current", "changed", "post_cross", "out"]
        );
        assert_eq!(
            release_witness_expected()[0].len(),
            writable_names.len(),
            "expected outputs must match writable output order"
        );
    }

    #[test]
    fn cpu_ref_rejects_malformed_csr() {
        let panic = std::panic::catch_unwind(|| {
            let _ = cpu_ref(2, &[1, 1, 1], &[0], &[0], &[0], &[0b1], &[0b1]);
        })
        .expect_err("malformed CSR must panic");
        let msg = panic_message(&panic);
        assert!(msg.contains("malformed CSR graph"), "got {msg}");
    }

    #[test]
    fn cpu_ref_rejects_mismatched_ffi_mask() {
        let panic = std::panic::catch_unwind(|| {
            let _ = cpu_ref(2, &[0, 1, 1], &[1], &[0], &[0, 0], &[0b1], &[0b1]);
        })
        .expect_err("mismatched FFI mask must panic");
        let msg = panic_message(&panic);
        assert!(msg.contains("malformed FFI edge mask"), "got {msg}");
    }

    #[test]
    fn cpu_ref_rejects_malformed_source_bitset() {
        let panic = std::panic::catch_unwind(|| {
            let _ = cpu_ref(2, &[0, 1, 1], &[1], &[0], &[0], &[0b1, 0b0], &[0b1]);
        })
        .expect_err("malformed source must panic");
        let msg = panic_message(&panic);
        assert!(msg.contains("malformed source bitset"), "got {msg}");
    }

    #[test]
    fn cpu_ref_rejects_malformed_sink_bitset() {
        let panic = std::panic::catch_unwind(|| {
            let _ = cpu_ref(2, &[0, 1, 1], &[1], &[0], &[0], &[0b1], &[0b1, 0b0]);
        })
        .expect_err("malformed sink must panic");
        let msg = panic_message(&panic);
        assert!(msg.contains("malformed sink bitset"), "got {msg}");
    }

    fn panic_message(panic: &Box<dyn std::any::Any + Send>) -> String {
        if let Some(s) = (**panic).downcast_ref::<String>() {
            s.clone()
        } else if let Some(s) = (**panic).downcast_ref::<&'static str>() {
            (*s).to_string()
        } else {
            "<non-string>".to_string()
        }
    }
}