oxiproj-engine 0.1.2

//! Pipeline optimization pass: detect and eliminate redundant steps.
//!
//! Called once after pipeline construction in `create.rs`. Applies safe,
//! provably-correct elimination rules without changing observable semantics.
//!
//! # Rules applied (in order)
//!
//! 1. **Complete no-ops**: steps where both `omit_fwd` and `omit_inv` are
//!    true are skipped in every execution path — remove them unconditionally.
//!
//! 2. **Paired axisswap cancellation**: two consecutive `axisswap` steps
//!    cancel only when their composition is the *exact identity*. The axis/sign
//!    state is captured at construction time as a canonical signed permutation
//!    ([`Pj::axisswap_order`], populated by `registry::probe_axisswap_order`),
//!    so this pass compares the real permutation + sign of each step rather
//!    than the (always-zeroed) wrapper fields. Each step's *effective* forward
//!    map is its stored permutation, inverted when the step's `inverted` flag is
//!    set; the pair cancels iff the second step's effective map is the exact
//!    inverse of the first's. This correctly keeps non-cancelling pairs such as
//!    `+order=2,3,1` twice (a 3-cycle squared, net `3,1,2`), `+order=-2,1` twice
//!    (a 90° rotation squared), or `+order=2,1` followed by `+order=1,-2`, while
//!    still cancelling true inverses (`+order=2,1` twice, or a forward/inverse
//!    pair of the same permutation).
//!
//! # Design note: no Helmert / affine folding
//!
//! Only the two passes above are applied. In particular, adjacent `helmert` (or
//! any affine) steps are **never** folded or removed here, for two reasons:
//!
//! * **Wrapper fields carry no Helmert state.** An earlier design attempted to
//!   remove all-zero Helmert steps by inspecting `Pj` wrapper fields (`x0`,
//!   `y0`, `z0`, `k0`, …). This is unsafe: those are the generic PROJ
//!   false-easting/false-northing parameters (`+x_0`, `+y_0`, `+z_0`, `+k_0`),
//!   not the Helmert translation/rotation/scale parameters (`+x`, `+y`, `+z`,
//!   `+rx`, `+ry`, `+rz`, `+s`), which live inside the `Box<dyn Operation>`.
//!   Removing a Helmert on wrapper-field evidence would silently drop a real
//!   shift. The all-zero guard is applied earlier, at the datum-shift pipeline
//!   assembly (before the Helmert is even constructed) — the correct place.
//! * **Composition is not commutative.** Even with full parameter access,
//!   folding two affine/Helmert steps into one is only valid when they truly
//!   compose to the identity (or to a single affine applied in the *same*
//!   order). Rotation matrices and full Helmert transforms do not commute, so a
//!   "cancel if parameters look opposite" heuristic would reorder
//!   non-commuting maps and produce silently wrong coordinates. `axisswap` is
//!   the one family where the state reduces to a signed permutation that we can
//!   compare and invert exactly, which is why it is the only algebraic fold.

use crate::pj::Pj;

/// Run all optimization passes on a pipeline's step list in order.
///
/// Returns the (possibly shorter) optimized step list. The input semantics
/// are preserved: the optimized pipeline is observably identical to the
/// original for all valid inputs.
pub(crate) fn optimize_pipeline(steps: Vec<Pj>) -> Vec<Pj> {
    let steps = remove_complete_noops(steps);
    cancel_axisswap_pairs(steps)
}

/// Remove steps that are skipped in both the forward and inverse directions.
///
/// A step with `omit_fwd = true` AND `omit_inv = true` is never executed
/// regardless of pipeline direction — it is a complete structural no-op.
fn remove_complete_noops(steps: Vec<Pj>) -> Vec<Pj> {
    steps
        .into_iter()
        .filter(|s| !(s.omit_fwd && s.omit_inv))
        .collect()
}

/// Cancel consecutive `axisswap` pairs that compose to the exact identity.
///
/// Two adjacent `axisswap` steps cancel when neither is selectively omitted and
/// the second step's effective forward map is the exact inverse of the first's
/// (see [`axisswap_steps_cancel`]). Pairs whose composition is a non-identity
/// permutation (e.g. two equal 3-cycles) are left in place.
fn cancel_axisswap_pairs(steps: Vec<Pj>) -> Vec<Pj> {
    let mut result: Vec<Pj> = Vec::with_capacity(steps.len());
    let mut iter = steps.into_iter().peekable();
    while let Some(current) = iter.next() {
        let cancels = iter
            .peek()
            .map(|next| {
                current.op_name == "axisswap"
                    && next.op_name == "axisswap"
                    && axisswap_steps_cancel(&current, next)
            })
            .unwrap_or(false);
        if cancels {
            // Consume the next step as well — both steps cancel out.
            let _ = iter.next();
            // Neither step is pushed to result; they are dropped.
        } else {
            result.push(current);
        }
    }
    result
}

/// Invert a signed axis permutation expressed in PROJ `+order=` form.
///
/// The forward map is `out[i] = signum(p[i]) * in[|p[i]| - 1]`; its inverse
/// therefore sends input slot `i` back to source axis `|p[i]| - 1` with the
/// same sign, i.e. `inv[|p[i]| - 1] = signum(p[i]) * (i + 1)`.
fn invert_perm(p: [i8; 4]) -> [i8; 4] {
    let mut inv = [0i8; 4];
    for (i, &val) in p.iter().enumerate() {
        // `val` is always in `±1..=±4` (probe-validated), so `|val| - 1` is a
        // valid 0..=3 index and the subtraction never underflows.
        let axis = (val.unsigned_abs() as usize).saturating_sub(1);
        inv[axis] = val.signum() * (i as i8 + 1);
    }
    inv
}

/// The effective forward signed permutation of an `axisswap` step, accounting
/// for the step's `inverted` flag (an inverted step applies the inverse map).
fn effective_perm(order: [i8; 4], inverted: bool) -> [i8; 4] {
    if inverted {
        invert_perm(order)
    } else {
        order
    }
}

/// Returns `true` when two adjacent `axisswap` steps compose to the exact
/// identity and may therefore both be removed.
///
/// Cancellation requires:
/// 1. Neither step has a selective omit flag (those change which steps run per
///    direction, so the pair is not a structural no-op).
/// 2. Both steps expose a recognised signed permutation (`axisswap_order`).
/// 3. The second step's *effective* forward map (its stored permutation,
///    inverted if `inverted`) is the exact inverse of the first step's — so
///    applying the first then the second yields the identity in both
///    directions.
///
/// This compares the ACTUAL permutation and sign of each step (plus the
/// per-step `inverted` flag), so genuine non-inverses — `+order=2,3,1` twice,
/// `+order=-2,1` twice, or `+order=2,1` then `+order=1,-2` — are correctly kept.
fn axisswap_steps_cancel(a: &Pj, b: &Pj) -> bool {
    // Neither step may have selective omit flags.
    if a.omit_fwd || a.omit_inv || b.omit_fwd || b.omit_inv {
        return false;
    }
    // Both steps must expose a recognised signed permutation; without it we
    // cannot prove cancellation and must conservatively keep both steps.
    let (order_a, order_b) = match (a.axisswap_order, b.axisswap_order) {
        (Some(x), Some(y)) => (x, y),
        _ => return false,
    };
    // Cancel iff B undoes A: B's effective map == inverse of A's effective map.
    let eff_a = effective_perm(order_a, a.inverted);
    let eff_b = effective_perm(order_b, b.inverted);
    eff_b == invert_perm(eff_a)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::pj::Pj;
    use oxiproj_core::{Ellipsoid, IoUnits};

    /// Minimal stand-in operation for unit tests — a pass-through identity.
    #[derive(Debug)]
    struct IdOp;
    impl oxiproj_core::Operation for IdOp {
        fn forward_2d(&self, lp: oxiproj_core::Lp) -> oxiproj_core::ProjResult<oxiproj_core::Xy> {
            Ok(oxiproj_core::Xy::new(lp.lam, lp.phi))
        }
        fn inverse_2d(&self, xy: oxiproj_core::Xy) -> oxiproj_core::ProjResult<oxiproj_core::Lp> {
            Ok(oxiproj_core::Lp::new(xy.x, xy.y))
        }
    }

    fn make_pj(op_name: &str, omit_fwd: bool, omit_inv: bool) -> Pj {
        let ellipsoid = Ellipsoid::named("WGS84").expect("WGS84");
        Pj {
            operation: Box::new(IdOp),
            ellipsoid,
            factors_es: ellipsoid.es,
            lam0: 0.0,
            phi0: 0.0,
            x0: 0.0,
            y0: 0.0,
            z0: 0.0,
            k0: 1.0,
            to_meter: 1.0,
            fr_meter: 1.0,
            vto_meter: 1.0,
            vfr_meter: 1.0,
            from_greenwich: 0.0,
            over: false,
            geoc: false,
            lon_wrap_center: None,
            is_latlong: false,
            left: IoUnits::Whatever,
            right: IoUnits::Whatever,
            inverted: false,
            bypass_prepare_finalize: true,
            omit_fwd,
            omit_inv,
            ad_proj: None,
            op_name: op_name.to_string(),
            axisswap_order: None,
        }
    }

    /// Build an `axisswap` step carrying a canonical signed permutation
    /// (`+order=` form) and an `inverted` flag, mirroring what
    /// `registry::probe_axisswap_order` records at construction time. The inner
    /// operation is irrelevant to the cancellation logic (which reads only
    /// `op_name`, `axisswap_order`, `inverted` and the omit flags), so a
    /// pass-through `IdOp` stands in for it.
    fn make_axisswap(order: [i8; 4], inverted: bool) -> Pj {
        let mut pj = make_pj("axisswap", false, false);
        pj.axisswap_order = Some(order);
        pj.inverted = inverted;
        pj
    }

    #[test]
    fn noop_removal_both_omit() {
        let steps = vec![
            make_pj("noop", false, false),
            make_pj("noop", true, true), // complete no-op
            make_pj("noop", false, false),
        ];
        let result = optimize_pipeline(steps);
        assert_eq!(
            result.len(),
            2,
            "middle step with omit_fwd+omit_inv must be removed"
        );
    }

    #[test]
    fn noop_removal_only_fwd_kept() {
        // omit_fwd only → NOT removed (still runs in inverse)
        let steps = vec![make_pj("noop", true, false)];
        let result = optimize_pipeline(steps);
        assert_eq!(result.len(), 1, "omit_fwd-only step must be kept");
    }

    #[test]
    fn noop_removal_only_inv_kept() {
        // omit_inv only → NOT removed (still runs in forward)
        let steps = vec![make_pj("noop", false, true)];
        let result = optimize_pipeline(steps);
        assert_eq!(result.len(), 1, "omit_inv-only step must be kept");
    }

    #[test]
    fn axisswap_involution_pair_cancelled() {
        // Two identical involutions (`+order=2,1`, a plain X/Y swap) compose to
        // the identity and must cancel.
        let steps = vec![
            make_axisswap([2, 1, 3, 4], false),
            make_axisswap([2, 1, 3, 4], false),
        ];
        let result = optimize_pipeline(steps);
        assert_eq!(result.len(), 0, "two `+order=2,1` steps must cancel");
    }

    #[test]
    fn axisswap_negate_involution_pair_cancelled() {
        // `+order=1,-2` twice: negating Y is its own inverse → identity.
        let steps = vec![
            make_axisswap([1, -2, 3, 4], false),
            make_axisswap([1, -2, 3, 4], false),
        ];
        let result = optimize_pipeline(steps);
        assert_eq!(result.len(), 0, "two `+order=1,-2` steps must cancel");
    }

    #[test]
    fn axisswap_fwd_inv_pair_cancelled() {
        // A permutation followed by its own inverse (same `+order`, opposite
        // `inverted`) always cancels, even for a non-involution 3-cycle.
        let steps = vec![
            make_axisswap([2, 3, 1, 4], false),
            make_axisswap([2, 3, 1, 4], true),
        ];
        let result = optimize_pipeline(steps);
        assert_eq!(result.len(), 0, "a permutation and its inverse must cancel");
    }

    #[test]
    fn axisswap_three_cycle_twice_not_cancelled() {
        // `+order=2,3,1` twice is the 3-cycle squared (net permutation 3,1,2),
        // NOT the identity — both steps must be kept. This is the core bug the
        // old wrapper-field heuristic got wrong.
        let steps = vec![
            make_axisswap([2, 3, 1, 4], false),
            make_axisswap([2, 3, 1, 4], false),
        ];
        let result = optimize_pipeline(steps);
        assert_eq!(
            result.len(),
            2,
            "two equal 3-cycles do NOT cancel (net 3,1,2)"
        );
    }

    #[test]
    fn axisswap_rotation_twice_not_cancelled() {
        // `+order=-2,1` twice is a 90° rotation squared (= 180° rotation),
        // not the identity — both steps must be kept.
        let steps = vec![
            make_axisswap([-2, 1, 3, 4], false),
            make_axisswap([-2, 1, 3, 4], false),
        ];
        let result = optimize_pipeline(steps);
        assert_eq!(result.len(), 2, "two `+order=-2,1` rotations do NOT cancel");
    }

    #[test]
    fn axisswap_swap_then_negate_not_cancelled() {
        // `+order=2,1` then `+order=1,-2` is not the identity — keep both.
        let steps = vec![
            make_axisswap([2, 1, 3, 4], false),
            make_axisswap([1, -2, 3, 4], false),
        ];
        let result = optimize_pipeline(steps);
        assert_eq!(
            result.len(),
            2,
            "distinct non-inverse permutations must NOT cancel"
        );
    }

    #[test]
    fn axisswap_with_omit_not_cancelled() {
        let mut a = make_axisswap([2, 1, 3, 4], false);
        a.omit_fwd = true; // selective omit
        let steps = vec![a, make_axisswap([2, 1, 3, 4], false)];
        let result = optimize_pipeline(steps);
        assert_eq!(
            result.len(),
            2,
            "axisswap with selective omit must not cancel"
        );
    }

    #[test]
    fn axisswap_unknown_order_not_cancelled() {
        // Without a recognised permutation (`axisswap_order == None`) the
        // optimizer cannot prove cancellation and must keep both steps.
        let steps = vec![
            make_pj("axisswap", false, false),
            make_pj("axisswap", false, false),
        ];
        let result = optimize_pipeline(steps);
        assert_eq!(
            result.len(),
            2,
            "axisswap steps without a known permutation must not cancel"
        );
    }

    #[test]
    fn axisswap_singleton_kept() {
        let steps = vec![make_axisswap([2, 1, 3, 4], false)];
        let result = optimize_pipeline(steps);
        assert_eq!(result.len(), 1, "single axisswap must be kept");
    }

    #[test]
    fn invert_perm_round_trips() {
        // invert(invert(p)) == p for every representative permutation shape.
        for p in [
            [1, 2, 3, 4],
            [2, 1, 3, 4],
            [1, -2, 3, 4],
            [2, 3, 1, 4],
            [-2, 1, 3, 4],
            [4, 3, 2, 1],
            [-1, -2, -3, -4],
        ] {
            assert_eq!(
                invert_perm(invert_perm(p)),
                p,
                "invert twice restores {p:?}"
            );
        }
    }

    #[test]
    fn empty_input_stays_empty() {
        let result = optimize_pipeline(vec![]);
        assert!(result.is_empty());
    }
}