vyre-self-substrate 0.4.1

//! IR transform passes as categorical functors (#52 self-consumer).
//!
//! Closes the recursion thesis for #52 — categorical-database
//! migration ships to user dialects (ETL pipelines, schema evolution)
//! AND treats vyre's IR transform passes as functors in a
//! Cat-of-IR-views category.
//!
//! # The legendary self-use
//!
//! Vyre's optimizer applies passes that rewrite the Region tree.
//! Today each pass is an ad-hoc match-on-Node procedure with no
//! algebraic relationship to other passes. Treating passes as
//! functors `F: IR_view_in → IR_view_out` unlocks:
//!
//! - **Compositionality**: F ∘ G is automatically a valid pass if F
//!   and G are. The composition's correctness is implied by the
//!   functor laws (preserves identity, preserves composition).
//! - **Equational reasoning**: pass A; pass B = pass B; pass A iff
//!   the functors commute. Today this is checked by hand on a
//!   case-by-case basis.
//! - **Free reuse of categorical machinery**: Yoneda lemma,
//!   adjoint pairs (where there's a least pass that achieves an
//!   effect = the left adjoint), Kan extensions (deriving missing
//!   passes from a partial pass list).
//!
//! The vyre transform pass framework can move from a hand-managed
//! dependency DAG to a typed functor-category where pass ordering,
//! correctness, and re-usability are derived from algebra.
//!
//! # The substrate primitive that powers this
//!
//! `functor_apply` performs one column-mapping functor application:
//! given a source row in the input category and a functor encoded
//! as a column-mapping lookup table, produce the target row in the
//! output category. Whole-schema migration composes per-row
//! functor_apply with `level_wave_program` for tree topology.
//!
//! This module owns the per-row functorial pass-application step.
//! Whole-pass migrations compose this primitive with the tree topology
//! helpers instead of changing this row-level contract.

/// Apply a functor to a row of IR-view data. `view_in[i]` is the
/// i-th column's value in the input view; `column_mapping[i]` is
/// the target-view column index for input column i. Returns the
/// transformed row in the output view of size `target_n_cols`.
///
/// # Panics
///
/// Panics if `view_in.len() != column_mapping.len()`.
#[must_use]
pub fn apply_pass_functor(view_in: &[u32], column_mapping: &[u32], target_n_cols: u32) -> Vec<u32> {
    let mut out = Vec::new();
    apply_pass_functor_into(view_in, column_mapping, target_n_cols, &mut out);
    out
}

/// Apply a functor into caller-owned output storage.
pub fn apply_pass_functor_into(
    view_in: &[u32],
    column_mapping: &[u32],
    target_n_cols: u32,
    out: &mut Vec<u32>,
) {
    use crate::observability::{bump, functorial_pass_composition_calls};
    bump(&functorial_pass_composition_calls);
    assert_eq!(view_in.len(), column_mapping.len());
    out.clear();
    out.resize(target_n_cols as usize, 0);
    for (i, &dst) in column_mapping.iter().enumerate() {
        if (dst as usize) < out.len() {
            out[dst as usize] = view_in[i];
        }
    }
}

/// Compose two functors: F ∘ G applied to a single row. Returns
/// `(F ∘ G)(row) = F(G(row))`.
///
/// `mapping_g` maps view_in (size n_in) → middle view (size n_mid).
/// `mapping_f` maps middle view (size n_mid) → view_out (size n_out).
///
/// # Panics
///
/// Panics on size mismatches.
#[must_use]
pub fn compose_passes(
    view_in: &[u32],
    mapping_g: &[u32],
    n_mid: u32,
    mapping_f: &[u32],
    n_out: u32,
) -> Vec<u32> {
    let mut out = Vec::new();
    let mut combined = Vec::new();
    compose_passes_into(
        view_in,
        mapping_g,
        n_mid,
        mapping_f,
        n_out,
        &mut combined,
        &mut out,
    );
    out
}

/// Compose two functors into caller-owned scratch and output buffers.
pub fn compose_passes_into(
    view_in: &[u32],
    mapping_g: &[u32],
    n_mid: u32,
    mapping_f: &[u32],
    n_out: u32,
    combined: &mut Vec<u32>,
    out: &mut Vec<u32>,
) {
    assert_eq!(view_in.len(), mapping_g.len());
    assert_eq!(mapping_f.len(), n_mid as usize);
    // Collapse G then F into one column map so scatter/gather matches a single
    // `apply_pass_functor` (two-step apply can disagree when mid columns alias).
    combined.clear();
    combined.reserve(mapping_g.len());
    combined.extend(mapping_g.iter().map(|&mid_dst| mapping_f[mid_dst as usize]));
    apply_pass_functor_into(view_in, combined, n_out, out);
}

/// Categorical identity functor: maps each column to itself.
/// Used as the "no-op pass" — composes with anything as identity.
#[must_use]
pub fn identity_functor(n_cols: u32) -> Vec<u32> {
    let mut out = Vec::new();
    identity_functor_into(n_cols, &mut out);
    out
}

/// Write the identity functor into caller-owned storage.
pub fn identity_functor_into(n_cols: u32, out: &mut Vec<u32>) {
    out.clear();
    out.reserve(n_cols as usize);
    out.extend(0..n_cols);
}

/// Test whether two functors commute on a given input row.
/// `f_then_g(x) == g_then_f(x)` for x = `view_in`.
#[must_use]
#[allow(clippy::too_many_arguments)]
pub fn passes_commute_on(
    view_in: &[u32],
    mapping_a: &[u32],
    n_mid_a: u32,
    mapping_b_after_a: &[u32],
    mapping_b: &[u32],
    n_mid_b: u32,
    mapping_a_after_b: &[u32],
    n_out: u32,
) -> bool {
    let ab = compose_passes(view_in, mapping_a, n_mid_a, mapping_b_after_a, n_out);
    let ba = compose_passes(view_in, mapping_b, n_mid_b, mapping_a_after_b, n_out);
    ab == ba
}

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

    #[test]
    fn identity_preserves_input() {
        let view_in = vec![10u32, 20, 30, 40];
        let id = identity_functor(4);
        let out = apply_pass_functor(&view_in, &id, 4);
        assert_eq!(out, view_in);
    }

    #[test]
    fn pass_remaps_columns() {
        // Input row [10, 20, 30]; mapping says col 0 → out 2, col 1 → out 0,
        // col 2 → out 1. Expected output: [20, 30, 10].
        let view_in = vec![10u32, 20, 30];
        let mapping = vec![2u32, 0, 1];
        let out = apply_pass_functor(&view_in, &mapping, 3);
        assert_eq!(out, vec![20, 30, 10]);
    }

    #[test]
    fn apply_pass_functor_into_reuses_output() {
        let view_in = vec![10u32, 20, 30];
        let mapping = vec![2u32, 0, 1];
        let mut out = Vec::with_capacity(8);
        let ptr = out.as_ptr();
        apply_pass_functor_into(&view_in, &mapping, 3, &mut out);
        assert_eq!(out, vec![20, 30, 10]);
        assert_eq!(out.as_ptr(), ptr);
    }

    #[test]
    fn composition_is_associative() {
        // (F ∘ G)(x) for two simple permutations.
        let view_in = vec![1u32, 2, 3, 4];
        let g = vec![1u32, 0, 3, 2]; // swap pairs
        let f = vec![3u32, 2, 1, 0]; // reverse
        let composed = compose_passes(&view_in, &g, 4, &f, 4);
        // G applied: [2, 1, 4, 3]. F applied: reverse → [3, 4, 1, 2].
        assert_eq!(composed, vec![3, 4, 1, 2]);
    }

    #[test]
    fn compose_passes_into_reuses_combined_and_output() {
        let view_in = vec![1u32, 2, 3, 4];
        let g = vec![1u32, 0, 3, 2];
        let f = vec![3u32, 2, 1, 0];
        let mut combined = Vec::with_capacity(8);
        let mut out = Vec::with_capacity(8);
        let combined_ptr = combined.as_ptr();
        let out_ptr = out.as_ptr();
        compose_passes_into(&view_in, &g, 4, &f, 4, &mut combined, &mut out);
        assert_eq!(out, vec![3, 4, 1, 2]);
        assert_eq!(combined.as_ptr(), combined_ptr);
        assert_eq!(out.as_ptr(), out_ptr);
    }

    #[test]
    fn identity_composes_as_no_op() {
        let view_in = vec![5u32, 10, 15];
        let any_pass = vec![2u32, 0, 1];
        let id = identity_functor(3);
        let id_then_pass = compose_passes(&view_in, &id, 3, &any_pass, 3);
        let pass_then_id = compose_passes(&view_in, &any_pass, 3, &id, 3);
        let pass_alone = apply_pass_functor(&view_in, &any_pass, 3);
        assert_eq!(id_then_pass, pass_alone);
        assert_eq!(pass_then_id, pass_alone);
    }

    #[test]
    fn commutative_passes_detected() {
        // Two identity-equivalent reshuffles that compose to the same
        // identity in either order.
        let view_in = vec![100u32, 200];
        let a = vec![0u32, 1]; // identity
        let b = vec![0u32, 1]; // identity
        let commute = passes_commute_on(&view_in, &a, 2, &b, &b, 2, &a, 2);
        assert!(commute, "two identities must commute");
    }

    #[test]
    fn non_commutative_passes_detected() {
        // Two non-identity passes that don't commute.
        let view_in = vec![1u32, 2, 3];
        let a = vec![1u32, 2, 0]; // shift left
        let b_after_a = vec![2u32, 0, 1]; // some target permutation
        let b = vec![2u32, 0, 1]; // same shape, different arrangement
        let a_after_b = vec![1u32, 2, 0];
        let _commute = passes_commute_on(&view_in, &a, 3, &b_after_a, &b, 3, &a_after_b, 3);
        // Specific result depends on the permutations; test exercises
        // the API path without asserting a specific bool.
    }
}