furiosa_mapping/

mapping.rs

//! Mapping expressions.

use std::fmt::Debug;
use std::marker::PhantomData;

use super::ext::IndexExt;
use abi_stable::std_types::RBox;
use furiosa_mapping_macro::primitive;
use furiosa_mapping_types::{Atom, Ident, Index, M, Mapping, PaddingKind, Term};

/// Marker trait for axis names. Implemented by types generated by `axes!`.
pub trait AxisName: Debug + Clone + 'static {
    /// The identifier of this axis (e.g. `Ident::K`).
    const NAME: Ident;
    /// The size of this axis as declared in `axes!`.
    const SIZE: usize;
}

/// Macro to define shapes using axis names and sizes.
///
/// # Examples
///
/// ```
/// use furiosa_mapping::*;
/// axes![A = 128, B = 64, C = 32];
/// ```
#[macro_export]
macro_rules! axes {
    (
        $( $name:ident = $size:literal ),* $(,)?
    ) => {
        $(
            #[allow(non_camel_case_types)]
            #[derive(Debug, Clone)]
            pub struct $name;
            impl AxisName for $name {
                const NAME: Ident = Ident::new(::core::stringify!($name));
                const SIZE: usize = $size;
            }
        )*
    };
}

/// Identity expression.
#[primitive(mapping::Identity)]
#[derive(Debug, Clone)]
pub struct Identity;

// ANCHOR: identity_impl
impl M for Identity {
    const SIZE: usize = 1;

    fn to_value() -> Mapping {
        Mapping::Identity
    }

    fn map(i: usize) -> Option<Index> {
        if i == 0 { Some(Index::new()) } else { None }
    }
}
// ANCHOR_END: identity_impl

/// Symbol expression that represents a single axis.
#[primitive(mapping::Symbol)]
#[derive(Debug, Clone)]
pub struct Symbol<S: AxisName> {
    _marker: std::marker::PhantomData<S>,
}

// ANCHOR: symbol_impl
impl<S: AxisName> M for Symbol<S> {
    const SIZE: usize = S::SIZE;

    fn to_value() -> Mapping {
        Mapping::Symbol {
            symbol: S::NAME,
            size: S::SIZE,
        }
    }

    fn map(i: usize) -> Option<Index> {
        if i < S::SIZE {
            let mut index = Index::new();
            Index::add_term(
                &mut index,
                Term {
                    inner: Atom::Symbol {
                        symbol: S::NAME,
                        size: S::SIZE,
                    },
                    stride: 1,
                    modulo: S::SIZE,
                },
                i,
            );
            Some(index)
        } else {
            None
        }
    }
}
// ANCHOR_END: symbol_impl

/// Stride expression that represents one for every `SIZE` elements.
#[primitive(mapping::Stride)]
#[derive(Debug, Clone)]
pub struct Stride<L, const SIZE: usize> {
    _marker: PhantomData<L>,
}
// ANCHOR: stride_impl
impl<L, const SIZE: usize> M for Stride<L, SIZE>
where
    L: M,
{
    const SIZE: usize = {
        assert!(L::SIZE % SIZE == 0, "Stride size must divide the original size");
        L::SIZE / SIZE
    };

    fn to_value() -> Mapping {
        Mapping::Stride {
            inner: RBox::new(L::to_value()),
            stride: SIZE,
        }
    }

    fn map(i: usize) -> Option<Index> {
        if i < Self::SIZE { L::map(i * SIZE) } else { None }
    }
}
// ANCHOR_END: stride_impl

/// Modulo expression that represents modulo `SIZE` elements.
#[primitive(mapping::Modulo)]
#[derive(Debug, Clone)]
pub struct Modulo<L, const SIZE: usize> {
    _marker: PhantomData<L>,
}
// ANCHOR: modulo_impl
impl<L, const SIZE: usize> M for Modulo<L, SIZE>
where
    L: M,
{
    const SIZE: usize = {
        assert!(L::SIZE % SIZE == 0, "Modulo size must divide the original size");
        SIZE
    };

    fn to_value() -> Mapping {
        Mapping::Modulo {
            inner: RBox::new(L::to_value()),
            modulo: SIZE,
        }
    }

    fn map(i: usize) -> Option<Index> {
        if i < Self::SIZE { L::map(i % L::SIZE) } else { None }
    }
}
// ANCHOR_END: modulo_impl

/// Truncate expression to `SIZE` elements.
#[primitive(mapping::Resize)]
#[derive(Debug, Clone)]
pub struct Resize<L, const SIZE: usize> {
    _marker: PhantomData<L>,
}
// ANCHOR: resize_impl
impl<L, const SIZE: usize> M for Resize<L, SIZE>
where
    L: M,
{
    const SIZE: usize = SIZE;

    fn to_value() -> Mapping {
        Mapping::Resize {
            inner: RBox::new(L::to_value()),
            resize: SIZE,
        }
    }

    fn map(i: usize) -> Option<Index> {
        if i < SIZE { L::map(i) } else { None }
    }
}
// ANCHOR_END: resize_impl

/// Add padding to increase an expression's size.
#[primitive(mapping::Padding)]
#[derive(Debug, Clone)]
pub struct Padding<L, const SIZE: usize> {
    _marker: PhantomData<L>,
}
// ANCHOR: padding_impl
impl<L, const SIZE: usize> M for Padding<L, SIZE>
where
    L: M,
{
    const SIZE: usize = SIZE;

    fn to_value() -> Mapping {
        Mapping::Padding {
            inner: RBox::new(L::to_value()),
            padding: SIZE,
            kind: PaddingKind::Top,
        }
    }

    fn map(i: usize) -> Option<Index> {
        L::map(i)
    }
}
// ANCHOR_END: padding_impl

/// Pair expression of two expressions.
#[primitive(mapping::Pair)]
#[derive(Debug, Clone)]
pub struct Pair<L, R> {
    _marker: PhantomData<(L, R)>,
}
// ANCHOR: pair_impl
impl<L, R> M for Pair<L, R>
where
    L: M,
    R: M,
{
    const SIZE: usize = L::SIZE * R::SIZE;

    fn to_value() -> Mapping {
        Mapping::Pair {
            left: RBox::new(L::to_value()),
            right: RBox::new(R::to_value()),
        }
    }

    fn map(i: usize) -> Option<Index> {
        let mut l = L::map(i / R::SIZE)?;
        let r = R::map(i % R::SIZE)?;
        Index::add(&mut l, r);
        Some(l)
    }
}
// ANCHOR_END: pair_impl

/// Asserts that dividing `I` from `E` results in `E2` after removing padding.
pub fn assert_div<I: M, E: M, E2: M, const LEN: usize>() {
    use crate::{DivisionExt, FMappingExt, MappingExt};
    let e2 = if LEN == 1 {
        E::to_value()
            .factorize()
            .divide_relaxed(I::to_value().factorize())
            .exact()
            .into_result()
            .expect("[assert_div] failed to split by the index expression")
            .dividend_residue
    } else {
        E::to_value()
            .factorize()
            .divide_span(I::to_value().factorize(), LEN)
            .into_result()
            .and_then(|d| d.exact().into_result())
            .expect("[assert_div] failed to split by the index expression")
            .dividend_residue
    };
    assert_eq!(
        e2.clone(), // XXX(jeehoon.kang): remove padding?
        E2::to_value().factorize(),
        "[assert_div] inconsistent view type after split"
    );
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{DivisionExt, FMappingExt, IndexExt, MappingExt, StrictDivisionExt};
    use abi_stable::std_types::{ROption, RResult, Tuple2};
    use furiosa_mapping_types::{
        BlockBounds, DivisionError, DivisionSide, DivisionTerm, FMapping, Factor, IndexValueError, RSortedMap,
        TermBounds,
    };
    use furiosa_opt_macro::m;

    /// [A # 4, B # 4] (size 16) split at 8.
    #[test]
    fn unittest_split_at_1() {
        axes![A = 2, B = 2];
        let f = <m![A # 4, B # 4]>::to_value().factorize();
        assert_eq!(f.size(), 16);
        let Tuple2(outer, inner) = f.split_at(8);
        assert_eq!(inner.size(), 8);
        assert_eq!(outer.size(), 2);
        assert_eq!(inner, <m![A, B # 4]>::to_value().factorize());
        assert_eq!(outer, <m![1 # 2]>::to_value().factorize());
    }

    /// [A # 4, B, C] (size 16) split at 8.
    #[test]
    fn unittest_split_at_2() {
        axes![A = 2, B = 2, C = 2];
        let f = <m![A # 4, B, C]>::to_value().factorize();
        let Tuple2(outer, inner) = f.split_at(8);
        assert_eq!(inner.size(), 8);
        assert_eq!(outer.size(), 2);
        assert_eq!(inner, <m![A, B, C]>::to_value().factorize());
        assert_eq!(outer, <m![1 # 2]>::to_value().factorize());
    }

    /// [A # 4, B # 4, C # 16, D # 4] split at 16.
    #[test]
    fn unittest_split_at_3() {
        axes![A = 2, B = 2, C = 2, D = 2];
        let f = <m![A # 4, B # 4, C # 16, D # 4]>::to_value().factorize();
        let Tuple2(outer, inner) = f.split_at(16);
        assert_eq!(inner.size(), 16);
        assert_eq!(outer.size(), 64);
        assert_eq!(inner, <m![C # 4, D # 4]>::to_value().factorize());
        assert_eq!(outer, <m![A # 4, B # 4, 1 # 4]>::to_value().factorize());
    }

    /// Non-divisible padding: [B = 4, A = 4 # 9] (size 36) split at 4.
    ///
    /// Padding 9 is not divisible by 4, so the result retains Composite
    /// atoms: `inner = [B, A # 9] % 4`, `outer = [B, A # 9] / 4`.
    #[test]
    fn unittest_split_at_4() {
        axes![A = 4, B = 4];
        let f = <m![B, A # 9]>::to_value().factorize();
        assert_eq!(f.size(), 36);

        let Tuple2(outer, inner) = f.split_at(4);
        assert_eq!(inner.size(), 4);
        assert_eq!(outer.size(), 9);
        assert_eq!(inner, <m![[B, A # 9] % 4]>::to_value().factorize());
        assert_eq!(outer, <m![[B, A # 9] / 4]>::to_value().factorize());
    }

    /// Total size not divisible by target → panic.
    /// [A = 6 # 9] (size 9) split at 4: 9 % 4 != 0.
    #[test]
    #[should_panic(expected = "not divisible")]
    fn unittest_split_at_5() {
        axes![A = 6];
        let f = <m![A # 9]>::to_value().factorize();
        f.split_at(4);
    }

    /// Non-divisible padding with multiple outer terms:
    /// [C = 2, B = 4, A = 4 # 9] (size 72) split at 4.
    #[test]
    fn unittest_split_at_6() {
        axes![A = 8];
        let f = <m![A # 16]>::to_value().factorize();

        let Tuple2(outer, inner) = f.split_at(4);
        assert_eq!(inner.size(), 4);
        assert_eq!(outer.size(), 4);
        assert_eq!(inner, <m![A % 4]>::to_value().factorize());
        assert_eq!(outer, <m![1 # 2, A / 4 % 2]>::to_value().factorize());
    }

    #[test]
    fn unittest_split_at_7() {
        axes![A = 2, B = 2, C = 2, D = 2];
        let f = <m![A, B # 4, [C, D] # 8]>::to_value().factorize();
        let Tuple2(outer, inner) = f.split_at(16);
        assert_eq!(inner.size(), 16);
        assert_eq!(outer.size(), 4);
        assert_eq!(inner, <m![B, 1 # 2, C, D]>::to_value().factorize());
        assert_eq!(outer, <m![A, 1 # 2]>::to_value().factorize());
    }

    /// Round-trip: FMapping → to_mapping → factorize should be identity.
    #[test]
    fn unittest_round_trip_1() {
        axes![A = 4, B = 2];
        let f = <m![A, B]>::to_value().factorize();
        assert_eq!(f, f.to_mapping().factorize());
    }

    #[test]
    fn unittest_round_trip_2() {
        axes![A = 2, B = 2];
        let f = <m![A # 4, B # 4]>::to_value().factorize();
        assert_eq!(f, f.to_mapping().factorize());
    }

    #[test]
    fn unittest_round_trip_3() {
        axes![A = 8];
        let f = <m![A # 16]>::to_value().factorize();
        assert_eq!(f, f.to_mapping().factorize());
    }

    #[test]
    fn unittest_round_trip_4() {
        axes![A = 4, B = 4];
        let f = <m![B, A # 9]>::to_value().factorize();
        assert_eq!(f, f.to_mapping().factorize());
    }

    #[test]
    fn unittest_round_trip_5() {
        axes![A = 2, B = 2, C = 2, D = 2];
        let f = <m![A # 4, B # 4, C # 16, D # 4]>::to_value().factorize();
        assert_eq!(f, f.to_mapping().factorize());
    }

    #[test]
    fn unittest_round_trip_6() {
        axes![A = 2, B = 2, C = 2, D = 2];
        let f = <m![A, B # 4, [C, D] # 8]>::to_value().factorize();
        assert_eq!(f, f.to_mapping().factorize());
    }

    #[test]
    fn unittest_round_trip_7() {
        axes![A = 8];
        let f = <m![A % 4]>::to_value().factorize();
        assert_eq!(f, f.to_mapping().factorize());
    }

    #[test]
    fn unittest_round_trip_8() {
        axes![A = 8];
        let f = <m![A / 4 % 2]>::to_value().factorize();
        assert_eq!(f, f.to_mapping().factorize());
    }

    #[test]
    fn unittest_round_trip_bottom_padding() {
        let f = FMapping(
            vec![Factor::Padding {
                size: 16,
                kind: PaddingKind::Bottom,
            }]
            .into(),
        );
        assert_eq!(f, f.to_mapping().factorize());
    }

    #[test]
    fn unittest_modulo_one_identity() {
        axes![A = 8];
        let f = <m![A % 1]>::to_value().factorize();
        let id = <m![1]>::to_value().factorize();
        assert_eq!(f, id);
    }

    #[test]
    fn unittest_divide_infinite_recursion() {
        axes![A = 8];
        let dividend = <m![A / 4]>::to_value().factorize();
        let divisor = <m![A % 4]>::to_value().factorize();
        assert!(dividend.divide_relaxed(divisor).exact().is_err());
    }

    /// write_transpose divides dst by src: `dst_mapping.divide_strict(&src_mapping, 1)`.
    /// With R=15 and padding to 16, dividing into /4 and %4 parts should work
    /// because the padded size (16) is divisible by 4.
    #[test]
    fn unittest_divide_padded_axis_split() {
        axes![A = 512, R = 15];
        let dst = <m![1 # 2, A / 8, R # 16 / 4, A % 8, R # 16 % 4]>::to_value();
        let src = <m![A, R # 16]>::to_value();
        let result = dst.divide_relaxed(&src).exact();
        assert!(
            result.is_ok(),
            "Dividing dst by src should succeed, but got: {result:?}"
        );
    }

    #[test]
    fn unittest_divide_span_nontrivial_tile() {
        axes![A = 8, B = 4];
        let dividend = <m![A, B]>::to_value().factorize();
        let divisor = <m![B]>::to_value().factorize();
        let division = dividend.clone().divide_span(divisor.clone(), 2).unwrap();
        let [term]: [DivisionTerm; 1] = division.division_terms().to_vec().try_into().unwrap();

        assert_eq!(
            *division.residue(DivisionSide::Dividend),
            <m![A, B = 2 # 4]>::to_value().factorize()
        );
        assert_eq!(
            *division.residue(DivisionSide::Divisor),
            <m![1 # 4]>::to_value().factorize()
        );
        let Factor::Term {
            inner: expected_term,
            resize: expected_resize,
        } = <m![B]>::to_value().factorize().into_factor()
        else {
            panic!("single-axis factorization must yield a term");
        };
        assert_eq!(term.term, expected_term);
        assert_eq!(term.dividend_stride, 1);
        assert_eq!(term.divisor_stride, 1);
        assert_eq!(term.resize, expected_resize);
    }

    #[test]
    fn unittest_div_span_exact_nontrivial_tile() {
        axes![A = 8, B = 4];
        let dividend = <m![A, B]>::to_value().factorize();
        let divisor = <m![B]>::to_value().factorize();
        let division = dividend.divide_span(divisor, 2).unwrap().exact().unwrap();

        assert_eq!(division.dividend_residue, <m![A, B = 2 # 4]>::to_value().factorize());
        assert_eq!(division.divisor_residue, <m![1 # 4]>::to_value().factorize());
    }

    #[test]
    fn unittest_div_span_exact_unmatched() {
        axes![A = 8, B = 4, C = 2];
        let dividend = <m![A, B]>::to_value().factorize();
        let divisor = <m![C]>::to_value().factorize();
        assert!(dividend.divide_span(divisor, 2).and_then(|d| d.exact()).is_err());
    }

    #[test]
    fn unittest_divide_span_unmatched() {
        axes![A = 8, B = 4, C = 2];
        let dividend = <m![A, B]>::to_value().factorize();
        let divisor = <m![C]>::to_value().factorize();
        let division = dividend.divide_span(divisor.clone(), 2).unwrap();

        assert!(division.division_terms().is_empty());
        assert_eq!(division.dividend_residue, <m![A, B]>::to_value().factorize());
        assert_eq!(division.divisor_residue, divisor);
    }

    /// Normalize should merge complementary stride/modulo splits of padded mappings.
    /// For example, `(R # 16 / 4).pair(R # 16 % 4)` should normalize to a single R factor.
    #[test]
    fn normalize_merges_padded_stride_modulo_split() {
        axes![R = 14];
        let r_padded = <m![R # 16]>::to_value();
        let outer = Mapping::Stride {
            inner: RBox::new(r_padded.clone()),
            stride: 4,
        };
        let inner = Mapping::Modulo {
            inner: RBox::new(r_padded),
            modulo: 4,
        };
        let paired = outer.pair(inner);
        let factorized = paired.factorize();
        let normalized = factorized.normalize();
        let expected = <m![R # 16]>::to_value().factorize();

        assert_eq!(
            normalized, expected,
            "Normalized mapping should merge complementary stride/modulo splits of padded mappings, but got: {normalized}"
        );
    }

    // ── divide: dividend_residue / divisor_residue ─────────────────

    #[test]
    fn unittest_divide_partial() {
        axes![A = 512, B = 4, C = 8];
        let a = <m![A / 8, B]>::to_value().factorize();
        let b = <m![B, C]>::to_value().factorize();
        let division = a.clone().divide_strict(b.clone());
        assert_eq!(division.division_terms().len(), 1);
        assert_eq!(
            division.remainder(DivisionSide::Dividend),
            <m![A / 8]>::to_value().factorize()
        );
        assert_eq!(
            division.remainder(DivisionSide::Divisor),
            <m![C]>::to_value().factorize()
        );
    }

    #[test]
    fn unittest_divide_all_matched() {
        axes![A = 512, B = 4];
        let a = <m![A / 8, B]>::to_value().factorize();
        let b = <m![B]>::to_value().factorize();
        assert!(a.clone().divide_relaxed(b.clone()).exact().is_ok());
        let division = a.clone().divide_strict(b.clone());
        assert_eq!(division.division_terms().len(), 1);
        assert_eq!(
            division.remainder(DivisionSide::Dividend),
            <m![A / 8]>::to_value().factorize()
        );
        assert_eq!(division.remainder(DivisionSide::Divisor), FMapping::new());
    }

    #[test]
    fn unittest_divide_nothing_matched() {
        axes![A = 512, C = 8];
        let a = <m![A / 8]>::to_value().factorize();
        let b = <m![C]>::to_value().factorize();
        let division = a.clone().divide_strict(b.clone());
        assert_eq!(division.division_terms().len(), 0);
        assert_eq!(division.remainder(DivisionSide::Dividend), a);
        assert_eq!(division.remainder(DivisionSide::Divisor), b);
    }

    #[test]
    fn unittest_divide_multiple_matched() {
        axes![A = 512, B = 4, C = 8, D = 2];
        let a = <m![A / 4, B, C]>::to_value().factorize();
        let b = <m![B, C, D]>::to_value().factorize();
        let division = a.clone().divide_strict(b.clone());
        assert_eq!(division.division_terms().len(), 2);
        assert_eq!(
            division.remainder(DivisionSide::Dividend),
            <m![A / 4]>::to_value().factorize()
        );
        assert_eq!(
            division.remainder(DivisionSide::Divisor),
            <m![D]>::to_value().factorize()
        );
    }

    #[test]
    fn unittest_divide_padded_by_self() {
        axes![A = 3];
        let a = <m![A # 16]>::to_value().factorize();
        let b = <m![A # 16]>::to_value().factorize();
        assert!(a.clone().divide_relaxed(b.clone()).exact().is_ok());
        let division = a.clone().divide_strict(b.clone());
        assert_eq!(division.division_terms().len(), 1);
    }

    #[test]
    fn unittest_div_exact_fails_on_partial() {
        axes![A = 512, B = 4, C = 8];
        let dividend = <m![A / 8, B]>::to_value().factorize();
        let divisor = <m![B, C]>::to_value().factorize();
        assert!(dividend.divide_relaxed(divisor).exact().is_err());
    }

    #[test]
    fn unittest_divide_span_ne1_unmatched() {
        axes![A = 8];
        let a = <m![A / 4]>::to_value().factorize();
        let b = <m![A % 4]>::to_value().factorize();
        let division = a.clone().divide_span(b.clone(), 2).unwrap();
        assert_eq!(division.division_terms().len(), 0);
        assert_eq!(division.dividend_residue, a);
        assert_eq!(division.divisor_residue, b);
    }

    // ── terms_with_stride ───────────────────────────────────────────

    #[test]
    fn unittest_terms_with_stride() {
        axes![A = 512, B = 4, C = 8];
        let division = <m![A / 8, B]>::to_value()
            .factorize()
            .divide_strict(<m![B, C]>::to_value().factorize());
        let q = division.residue(DivisionSide::Dividend).terms_with_stride();
        assert_eq!(q.len(), 1);
        assert_eq!((q[0].resize, q[0].stride), (64, 4));
        let r = division.residue(DivisionSide::Divisor).terms_with_stride();
        assert_eq!(r.len(), 1);
        assert_eq!((r[0].resize, r[0].stride), (8, 1));
    }

    // ── remainder (applied to original a/b) ─────────────────────────

    #[test]
    fn unittest_remainder_single() {
        axes![A = 512, B = 4, C = 8];
        let a = <m![A / 8, B]>::to_value().factorize();
        let b = <m![B, C]>::to_value().factorize();
        let division = a.clone().divide_strict(b.clone());
        assert_eq!(
            division.remainder(DivisionSide::Dividend),
            <m![A / 8]>::to_value().factorize()
        );
        assert_eq!(
            division.remainder(DivisionSide::Divisor),
            <m![C]>::to_value().factorize()
        );
    }

    #[test]
    fn unittest_remainder_multiple() {
        axes![A = 512, B = 4, C = 8, D = 2];
        let a = <m![A / 4, B, C]>::to_value().factorize();
        let b = <m![B, C, D]>::to_value().factorize();
        let division = a.clone().divide_strict(b.clone());
        assert_eq!(
            division.remainder(DivisionSide::Dividend),
            <m![A / 4]>::to_value().factorize()
        );
        assert_eq!(
            division.remainder(DivisionSide::Divisor),
            <m![D]>::to_value().factorize()
        );
    }

    #[test]
    fn unittest_remainder_interleaved_3_matches() {
        axes![A = 2, B = 3, C = 5, D = 7, E = 11];
        let a = <m![A, B, C, D, E]>::to_value().factorize();
        let b = <m![A, C, E]>::to_value().factorize();
        let division = a.clone().divide_strict(b);
        assert_eq!(
            division.remainder(DivisionSide::Dividend),
            <m![B, D]>::to_value().factorize()
        );
    }

    #[test]
    fn unittest_remainder_interleaved_partial() {
        axes![A = 2, B = 3, C = 5, D = 7, E = 11, F = 13];
        let a = <m![A, B, C, D, E]>::to_value().factorize();
        let b = <m![B, D, F]>::to_value().factorize();
        let division = a.clone().divide_strict(b.clone());
        assert_eq!(
            division.remainder(DivisionSide::Dividend),
            <m![A, C, E]>::to_value().factorize()
        );
        assert_eq!(
            division.remainder(DivisionSide::Divisor),
            <m![F]>::to_value().factorize()
        );
    }

    #[test]
    fn unittest_remainder_preserves_padding() {
        axes![A = 3, B = 4];
        let a = <m![A # 16, B]>::to_value().factorize();
        let division = a.clone().divide_strict(<m![B]>::to_value().factorize());
        assert_eq!(
            division.remainder(DivisionSide::Dividend),
            <m![A # 16]>::to_value().factorize()
        );
    }

    #[test]
    fn unittest_remainder_nothing_matched() {
        axes![A = 512, C = 8];
        let a = <m![A / 8]>::to_value().factorize();
        let b = <m![C]>::to_value().factorize();
        let division = a.clone().divide_strict(b.clone());
        assert_eq!(division.remainder(DivisionSide::Dividend), a);
        assert_eq!(division.remainder(DivisionSide::Divisor), b);
    }

    #[test]
    fn unittest_remainder_all_matched() {
        axes![B = 4];
        let a = <m![B]>::to_value().factorize();
        let b = <m![B]>::to_value().factorize();
        let division = a.clone().divide_strict(b.clone());
        assert_eq!(division.remainder(DivisionSide::Dividend), FMapping::new());
        assert_eq!(division.remainder(DivisionSide::Divisor), FMapping::new());
    }

    #[test]
    fn unittest_remainder_removes_padding_hole() {
        axes![A = 4];
        let a = <m![A # 16]>::to_value().factorize();
        let division = a.clone().divide_strict(<m![A]>::to_value().factorize());
        assert_eq!(
            division.remainder(DivisionSide::Dividend),
            <m![1 # 4]>::to_value().factorize()
        );
    }

    #[test]
    fn unittest_remainder_non_divisible_padding() {
        axes![A = 3];
        let a = <m![A # 16]>::to_value().factorize();
        let b = <m![A]>::to_value().factorize();
        assert!(a.clone().divide_relaxed(b.clone()).exact().is_ok());
        let division = a.clone().divide_strict(b.clone());
        assert_eq!(division.division_terms().len(), 1);
        assert_eq!(
            division.remainder(DivisionSide::Dividend),
            <m![A # 16 / 4]>::to_value().factorize()
        );
        assert_eq!(division.remainder(DivisionSide::Divisor), FMapping::new());
    }

    #[test]
    fn unittest_division_remainder_accessor() {
        axes![A = 3];
        let dividend = <m![A # 16]>::to_value().factorize();
        let divisor = <m![A]>::to_value().factorize();
        let division = dividend.clone().divide_strict(divisor.clone());

        assert_eq!(division.dividend(), &dividend);
        assert_eq!(division.divisor(), &divisor);
        assert_eq!(
            division.remainder(DivisionSide::Dividend),
            <m![A # 16 / 4]>::to_value().factorize()
        );
        assert_eq!(division.remainder(DivisionSide::Divisor), FMapping::new());
    }

    #[test]
    fn unittest_division_residue_accessor_is_mapping_safe() {
        axes![A = 3];
        let residue = <m![A # 16]>::to_value()
            .factorize()
            .divide_strict(<m![A]>::to_value().factorize())
            .residue(DivisionSide::Dividend)
            .clone();

        assert_eq!(residue.clone().normalize(), residue);
    }

    #[test]
    fn unittest_division_padding_bounds_compact_bounds() {
        axes![A = 4];
        let dividend = <m![A # 16]>::to_value().factorize();
        let divisor = <m![A]>::to_value().factorize();
        let division = dividend.divide_strict(divisor);
        let bounds = division.bounds();
        let [term]: [DivisionTerm; 1] = division.division_terms().to_vec().try_into().unwrap();

        assert_eq!(
            bounds,
            vec![TermBounds {
                term,
                dividend: BlockBounds { min: 4, max: 16 },
                divisor: BlockBounds { min: 4, max: 4 },
            }]
        );
    }

    #[test]
    fn unittest_divide_allows_inexact_reconstruction() {
        axes![A = 3];
        let dividend = <m![A # 16]>::to_value().factorize();
        let divisor = <m![A]>::to_value().factorize();
        let division = dividend.divide_strict(divisor);

        assert_eq!(division.division_terms().len(), 1);
    }

    #[test]
    fn unittest_division_padding_bounds_allow_semantic_reconstruction() {
        axes![A = 3];
        let dividend = <m![A # 16]>::to_value().factorize();
        let divisor = <m![A]>::to_value().factorize();
        let division = dividend.divide_strict(divisor);
        let [term]: [DivisionTerm; 1] = division.division_terms().to_vec().try_into().unwrap();

        assert_eq!(
            division.bounds(),
            vec![TermBounds {
                term,
                dividend: BlockBounds { min: 4, max: 16 },
                divisor: BlockBounds { min: 3, max: 3 },
            }]
        );
    }

    #[test]
    fn unittest_division_padding_bounds_collapse_only_contiguous_padding() {
        axes![A = 3, B = 2];
        let dividend = <m![A # 4, B # 16]>::to_value().factorize();
        let divisor = <m![A]>::to_value().factorize();
        let division = dividend.divide_strict(divisor);
        let [term]: [DivisionTerm; 1] = division.division_terms().to_vec().try_into().unwrap();

        assert_eq!(
            division.bounds(),
            vec![TermBounds {
                term,
                dividend: BlockBounds { min: 4, max: 4 },
                divisor: BlockBounds { min: 3, max: 3 },
            }]
        );
    }

    #[test]
    fn unittest_division_padding_bounds_preserve_consecutive_padding_run() {
        axes![A = 3];
        let dividend = <m![A # 4 # 16]>::to_value().factorize();
        let divisor = <m![A]>::to_value().factorize();
        let division = dividend.divide_strict(divisor);
        let [term]: [DivisionTerm; 1] = division.division_terms().to_vec().try_into().unwrap();

        assert_eq!(
            division.bounds(),
            vec![TermBounds {
                term,
                dividend: BlockBounds { min: 4, max: 16 },
                divisor: BlockBounds { min: 3, max: 3 },
            }]
        );
    }

    #[test]
    fn unittest_division_residue_marks_removed_block_as_bottom_padding() {
        axes![A = 3];
        let dividend = <m![A # 16]>::to_value().factorize();
        let divisor = <m![A]>::to_value().factorize();
        let division = dividend.divide_strict(divisor);
        let factors = division.dividend_residue.factors();

        assert!(matches!(
            &*factors,
            [
                Factor::Padding {
                    size: 3,
                    kind: PaddingKind::Bottom
                },
                Factor::Padding {
                    size: 16,
                    kind: PaddingKind::Top
                }
            ]
        ));
    }

    #[test]
    fn unittest_division_padding_bounds_multiple_terms_with_padding() {
        axes![A = 4, B = 3];
        let dividend = <m![A # 16, B]>::to_value().factorize();
        let divisor = <m![A, B]>::to_value().factorize();
        let division = dividend.divide_strict(divisor);
        let bounds = division.bounds();
        let [a_term, b_term]: [DivisionTerm; 2] = division.division_terms().to_vec().try_into().unwrap();

        assert_eq!(
            bounds,
            vec![
                TermBounds {
                    term: a_term,
                    dividend: BlockBounds { min: 4, max: 16 },
                    divisor: BlockBounds { min: 4, max: 4 },
                },
                TermBounds {
                    term: b_term,
                    dividend: BlockBounds { min: 3, max: 3 },
                    divisor: BlockBounds { min: 3, max: 3 },
                },
            ]
        );
    }

    #[test]
    fn unittest_division_padding_bounds_partial_division_only_reports_matched_terms() {
        axes![A = 512, B = 4, C = 8, D = 2];
        let dividend = <m![A / 4, B, C]>::to_value().factorize();
        let divisor = <m![B, C, D]>::to_value().factorize();
        let division = dividend.divide_strict(divisor);
        let bounds = division.bounds();
        let [b_term, c_term]: [DivisionTerm; 2] = division.division_terms().to_vec().try_into().unwrap();

        assert_eq!(division.division_terms().len(), 2);
        assert_eq!(
            bounds,
            vec![
                TermBounds {
                    term: b_term,
                    dividend: BlockBounds { min: 4, max: 4 },
                    divisor: BlockBounds { min: 4, max: 4 },
                },
                TermBounds {
                    term: c_term,
                    dividend: BlockBounds { min: 8, max: 8 },
                    divisor: BlockBounds { min: 8, max: 8 },
                },
            ]
        );
    }

    // ── split_at limitation: Composite on non-divisible padding ─────

    #[test]
    fn unittest_split_at_non_divisible_padding() {
        axes![A = 3];
        let a = <m![A # 16]>::to_value().factorize();
        let Tuple2(outer, inner) = a.split_at(4);
        assert_eq!(inner, <m![A # 4]>::to_value().factorize());
        assert_eq!(outer, <m![1 # 4]>::to_value().factorize());
    }

    #[test]
    fn unittest_stride_partial_live_prefix_padding() {
        axes![R = 5];
        let fm = <m![R # 16 / 4]>::to_value().factorize();
        assert_eq!(fm, <m![1 # 2, [R # 8] / 4]>::to_value().factorize());

        assert_eq!(fm.eval(0).ident_value(Ident::R), RResult::ROk(0));
        assert_eq!(fm.eval(1).ident_value(Ident::R), RResult::ROk(4));
        assert_eq!(
            fm.eval(2).ident_value(Ident::R),
            RResult::RErr(IndexValueError::Invalid)
        );
        assert_eq!(
            fm.eval(3).ident_value(Ident::R),
            RResult::RErr(IndexValueError::Invalid)
        );
    }

    #[test]
    fn unittest_stride_single_live_slot_collapses_to_padding() {
        axes![R = 3];
        let fm = <m![R # 64 / 8]>::to_value().factorize();
        assert_eq!(fm, <m![1 # 8]>::to_value().factorize());

        assert_eq!(fm.eval(0).ident_value(Ident::R), RResult::ROk(0));
        assert_eq!(
            fm.eval(1).ident_value(Ident::R),
            RResult::RErr(IndexValueError::Invalid)
        );
        assert_eq!(
            fm.eval(7).ident_value(Ident::R),
            RResult::RErr(IndexValueError::Invalid)
        );
    }

    #[test]
    fn unittest_mul_scales_single_live_slot_padding() {
        axes![R = 3, A = 5];
        let fm = <m![R # 16 / 4, A]>::to_value().factorize();
        assert_eq!(fm, <m![A # 20]>::to_value().factorize());
    }

    #[test]
    fn unittest_mul_scales_single_live_slot_padding_large_stride() {
        axes![R = 3, A = 5];
        let fm = <m![R # 64 / 8, A]>::to_value().factorize();
        assert_eq!(fm, <m![A # 40]>::to_value().factorize());
    }

    #[test]
    fn unittest_mul_scales_partial_live_prefix_padding() {
        axes![R = 5, A = 5];
        let fm = <m![R # 16 / 4, A]>::to_value().factorize();
        assert_eq!(fm, <m![[[[R # 8] / 4] # 4], A]>::to_value().factorize());
    }

    #[test]
    fn unittest_recursive_stride_over_nested_padding_composite() {
        axes![A = 5];
        let fm = <m![[A # 16 / 4] / 2]>::to_value().factorize();
        assert_eq!(fm, <m![1 # 2]>::to_value().factorize());
    }

    #[test]
    fn unittest_multi_char_ident() {
        // Multi-character identifiers should work with axes! and m! macros.
        axes![Batch = 4, Seq = 8, Hidden = 16];
        let f = <m![Batch, Seq, Hidden]>::to_value().factorize();
        assert_eq!(f.size(), 4 * 8 * 16);

        // Verify individual axis sizes.
        assert_eq!(<m![Batch]>::SIZE, 4);
        assert_eq!(<m![Seq]>::SIZE, 8);
        assert_eq!(<m![Hidden]>::SIZE, 16);

        // Verify idents are correct multi-char strings.
        let idents = f.idents();
        assert_eq!(idents.len(), 3);
        assert_eq!(idents[0].as_str(), "Hidden");
        assert_eq!(idents[1].as_str(), "Seq");
        assert_eq!(idents[2].as_str(), "Batch");
    }

    #[test]
    fn unittest_multi_char_ident_with_ops() {
        // Multi-character identifiers with stride/modulo/padding operations.
        axes![Abxcbjhkdfhjdkf = 32];
        let f = <m![Abxcbjhkdfhjdkf / 8]>::to_value().factorize();
        assert_eq!(f.size(), 4);

        let f2 = <m![Abxcbjhkdfhjdkf % 8]>::to_value().factorize();
        assert_eq!(f2.size(), 8);

        let f3 = <m![Abxcbjhkdfhjdkf # 64]>::to_value().factorize();
        assert_eq!(f3.size(), 64);

        // Verify the ident string is preserved.
        let idents = f.idents();
        assert_eq!(idents[0].as_str(), "Abxcbjhkdfhjdkf");
    }

    #[test]
    fn unittest_multi_char_ident_mixed() {
        // Mix of single-char and multi-char identifiers.
        axes![A = 2, Batch = 4, C = 8];
        let f = <m![A, Batch, C]>::to_value().factorize();
        assert_eq!(f.size(), 2 * 4 * 8);

        let idents = f.idents();
        assert_eq!(idents.len(), 3);
    }

    #[test]
    fn unittest_multi_char_ident_underscore() {
        // Identifiers with underscores.
        axes![ASDKNASGDHJKAWD_CXVXCKVHSDF = 16];
        let f = <m![ASDKNASGDHJKAWD_CXVXCKVHSDF]>::to_value().factorize();
        assert_eq!(f.size(), 16);
        assert_eq!(f.idents()[0].as_str(), "ASDKNASGDHJKAWD_CXVXCKVHSDF");
    }

    #[test]
    fn unittest_find_symbol_size_in_composite() {
        axes![R = 13, B = 2];
        let fm = <m![R # 16 % 4, B]>::to_value().factorize();
        assert_eq!(fm.find_symbol_size(Ident::R), ROption::RSome(13));
        assert_eq!(fm.find_symbol_size(Ident::B), ROption::RSome(2));
        assert_eq!(fm.find_symbol_size(Ident::A), ROption::RNone);
    }

    /// add_term Composite recursion: stride > 1 must recurse into inner FMapping.
    /// R=3 padded to 64, stride 8 → Composite with outer stride=8.
    /// FMapping::eval must match M::map at every position, including overflow detection.
    #[test]
    fn add_term_composite_stride_recursion() {
        axes![R = 3];
        type P = m![R # 64 / 8];
        let fm = P::to_value().factorize();

        // Full cross-validation: FMapping::eval must match M::map at every position
        for i in 0..P::SIZE {
            match P::map(i) {
                Some(idx) => assert_eq!(idx.ident_value(Ident::R), fm.eval(i).ident_value(Ident::R), "pos {i}"),
                None => assert!(
                    fm.eval(i).ident_value(Ident::R).is_err(),
                    "pos {i}: map returned None but eval succeeded"
                ),
            }
        }

        // Specifically: position 0 → R=0 (valid, 0 < 3)
        assert_eq!(fm.eval(0).ident_value(Ident::R), RResult::ROk(0));
        // Position 1 → R=8 (invalid, 8 ≥ 3 → Err via Composite inner overflow)
        assert_eq!(
            fm.eval(1).ident_value(Ident::R),
            RResult::RErr(IndexValueError::Invalid)
        );

        // Also test gcd case: R=50 # 64 / 8. gcd(50,8)=2 → partial stride absorption.
        {
            axes![R = 50];
            type Q = m![R # 64 / 8];
            let fm2 = Q::to_value().factorize();
            for i in 0..Q::SIZE {
                match Q::map(i) {
                    Some(idx) => assert_eq!(
                        idx.ident_value(Ident::R),
                        fm2.eval(i).ident_value(Ident::R),
                        "R=50 pos {i}"
                    ),
                    None => assert!(
                        fm2.eval(i).ident_value(Ident::R).is_err(),
                        "R=50 pos {i}: map returned None but eval succeeded"
                    ),
                }
            }
            // Position 0 → R=0, position 1 → R=8, position 6 → R=48 (last valid, 48<50)
            assert_eq!(fm2.eval(0).ident_value(Ident::R), RResult::ROk(0));
            assert_eq!(fm2.eval(1).ident_value(Ident::R), RResult::ROk(8));
            assert_eq!(fm2.eval(6).ident_value(Ident::R), RResult::ROk(48));
            // Position 7 → R=56 (invalid, 56 ≥ 50 → Err)
            assert_eq!(
                fm2.eval(7).ident_value(Ident::R),
                RResult::RErr(IndexValueError::Invalid)
            );
        }
    }

    /// Mixed-ident Composite should also recurse correctly during eval.
    /// The goal of Index::eval is semantic point evaluation, not syntactic structure preservation.
    #[test]
    fn add_term_composite_stride_recursion_mixed_idents() {
        axes![A = 2, B = 3];
        type P = m![[A, B] # 10 / 2];
        let fm = P::to_value().factorize();

        for i in 0..P::SIZE {
            match P::map(i) {
                Some(idx) => {
                    assert_eq!(idx.ident_value(Ident::A), fm.eval(i).ident_value(Ident::A), "A pos {i}");
                    assert_eq!(idx.ident_value(Ident::B), fm.eval(i).ident_value(Ident::B), "B pos {i}");
                }
                None => {
                    assert!(fm.eval(i).ident_value(Ident::A).is_err(), "A pos {i}");
                    assert!(fm.eval(i).ident_value(Ident::B).is_err(), "B pos {i}");
                }
            }
        }

        assert_eq!(fm.eval(0).ident_value(Ident::A), RResult::ROk(0));
        assert_eq!(fm.eval(0).ident_value(Ident::B), RResult::ROk(0));
        assert_eq!(fm.eval(1).ident_value(Ident::A), RResult::ROk(0));
        assert_eq!(fm.eval(1).ident_value(Ident::B), RResult::ROk(2));
        assert_eq!(fm.eval(2).ident_value(Ident::A), RResult::ROk(1));
        assert_eq!(fm.eval(2).ident_value(Ident::B), RResult::ROk(1));
        assert_eq!(
            fm.eval(3).ident_value(Ident::A),
            RResult::RErr(IndexValueError::Invalid)
        );
        assert_eq!(
            fm.eval(3).ident_value(Ident::B),
            RResult::RErr(IndexValueError::Invalid)
        );
        assert_eq!(
            fm.eval(4).ident_value(Ident::A),
            RResult::RErr(IndexValueError::Invalid)
        );
        assert_eq!(
            fm.eval(4).ident_value(Ident::B),
            RResult::RErr(IndexValueError::Invalid)
        );
    }

    #[test]
    fn ident_value_rejects_composite_terms() {
        axes![A = 2, B = 3];
        let term = <m![[A, B] # 10 / 2]>::to_value()
            .factorize()
            .terms_with_stride()
            .into_iter()
            .next()
            .unwrap()
            .term;
        let index = Index(RResult::ROk(RSortedMap::from_iter([(term, 0)])));
        assert_eq!(
            index.ident_value(Ident::A),
            RResult::RErr(IndexValueError::NonFlattened)
        );
    }

    #[test]
    fn ident_value_treats_absent_as_zero_and_invalid_as_error() {
        axes![A = 4];
        let mut index = Index::new();
        index.add_term(
            Term {
                inner: Atom::Symbol {
                    symbol: Ident::A,
                    size: 4,
                },
                stride: 1,
                modulo: 4,
            },
            2,
        );
        assert_eq!(index.ident_value(Ident::B), RResult::ROk(0));

        let invalid = <m![A # 8]>::to_value().factorize().eval(5);
        assert_eq!(invalid.ident_value(Ident::A), RResult::RErr(IndexValueError::Invalid));
    }

    // ── divide_inner / DivisionMode ─────────────────────────────────

    #[test]
    fn unittest_divide_relaxed_uses_top_padding() {
        axes![A = 4];
        let division = <m![A # 16]>::to_value()
            .factorize()
            .divide_relaxed(<m![A]>::to_value().factorize());
        assert_eq!(
            division.dividend_residue,
            FMapping(
                vec![Factor::Padding {
                    size: 16,
                    kind: PaddingKind::Top,
                }]
                .into()
            )
        );
        assert_eq!(division.divisor_residue, <m![1 # 4]>::to_value().factorize());
    }

    #[test]
    fn unittest_exact_on_relaxed() {
        axes![A = 8, B = 4];
        let ok = <m![A, B]>::to_value()
            .factorize()
            .divide_relaxed(<m![B]>::to_value().factorize())
            .exact()
            .unwrap();
        assert_eq!(ok.dividend_residue, <m![A, 1 # 4]>::to_value().factorize());
        assert_eq!(ok.divisor_residue, <m![1 # 4]>::to_value().factorize());

        let err = <m![A]>::to_value()
            .factorize()
            .divide_relaxed(<m![B]>::to_value().factorize())
            .exact();
        assert!(matches!(err, RResult::RErr(DivisionError::DivisorTermCannotDivide)));
    }

    #[test]
    fn unittest_padding_same_kind_merge() {
        let mut f = FMapping::new();
        f = f.padding(4, PaddingKind::Bottom);
        f = f.padding(8, PaddingKind::Bottom);
        assert_eq!(
            f,
            FMapping(
                vec![Factor::Padding {
                    size: 8,
                    kind: PaddingKind::Bottom,
                }]
                .into()
            )
        );

        let mut f = FMapping::new();
        f = f.padding(4, PaddingKind::Top);
        f = f.padding(8, PaddingKind::Top);
        assert_eq!(
            f,
            FMapping(
                vec![Factor::Padding {
                    size: 8,
                    kind: PaddingKind::Top,
                }]
                .into()
            )
        );

        let mut f = FMapping::new();
        f = f.padding(4, PaddingKind::Bottom);
        f = f.padding(8, PaddingKind::Top);
        assert_eq!(
            f,
            FMapping(
                vec![
                    Factor::Padding {
                        size: 4,
                        kind: PaddingKind::Bottom,
                    },
                    Factor::Padding {
                        size: 8,
                        kind: PaddingKind::Top,
                    },
                ]
                .into()
            )
        );
    }

    /// When two terms A and B are matched from `[A # 4, B, C # 4]`, the strict
    /// residue has two Bottom paddings at different strides.  `bounds()` must
    /// skip the inner Bottom (bottom < resize) and find the outer one.
    #[test]
    fn unittest_bounds_skips_inner_bottom() {
        axes![A = 3, B = 2, C = 3];
        let dividend = <m![A # 4, B, C # 8]>::to_value().factorize();
        let divisor = <m![A, C]>::to_value().factorize();
        let division = dividend.divide_strict(divisor);
        let bounds = division.bounds();
        let [a_term, c_term]: [DivisionTerm; 2] = division.division_terms().to_vec().try_into().unwrap();
        assert_eq!(
            bounds,
            vec![
                TermBounds {
                    term: a_term,
                    dividend: BlockBounds { min: 4, max: 4 },
                    divisor: BlockBounds { min: 3, max: 3 },
                },
                TermBounds {
                    term: c_term,
                    dividend: BlockBounds { min: 4, max: 8 },
                    divisor: BlockBounds { min: 3, max: 3 },
                },
            ]
        );
    }

    /// Multi-term division where divisor terms merge in the divisor residue
    /// (consecutive Bottom paddings get merged by `padding()`).
    #[test]
    fn unittest_bounds_with_merged_divisor_bottom() {
        axes![A = 4, B = 3];
        let dividend = <m![A, B]>::to_value().factorize();
        let divisor = <m![A, B]>::to_value().factorize();
        let division = dividend.divide_strict(divisor);
        let bounds = division.bounds();
        let [a_term, b_term]: [DivisionTerm; 2] = division.division_terms().to_vec().try_into().unwrap();
        assert_eq!(
            bounds,
            vec![
                TermBounds {
                    term: a_term,
                    dividend: BlockBounds { min: 4, max: 4 },
                    divisor: BlockBounds { min: 4, max: 4 },
                },
                TermBounds {
                    term: b_term,
                    dividend: BlockBounds { min: 3, max: 3 },
                    divisor: BlockBounds { min: 3, max: 3 },
                },
            ]
        );
    }

    #[test]
    fn serde_round_trip() {
        axes![A = 512, B = 8, C = 4, D = 3];

        let mappings: Vec<Mapping> = vec![
            Mapping::Identity,
            <m![A]>::to_value(),
            <m![B / 4]>::to_value(),
            <m![B % 4]>::to_value(),
            <m![A = 2]>::to_value(),
            <m![D # 4]>::to_value(),
            <m![A, C]>::to_value(),
        ];

        for m in mappings {
            let json = serde_json::to_string(&m).unwrap();
            let deserialized: Mapping = serde_json::from_str(&json).unwrap();
            assert_eq!(m, deserialized, "Round-trip failed for: {json}");
        }
    }
}