use super::*;
use strided_view::auxiliary::index_order;
#[test]
fn test_fuse_dims_contiguous() {
let dims = [3, 4];
let strides1 = [1isize, 3];
let strides2 = [1isize, 3];
let all_strides: Vec<&[isize]> = vec![&strides1, &strides2];
let fused = fuse_dims(&dims, &all_strides);
assert_eq!(fused.as_slice(), vec![12, 1]);
}
#[test]
fn test_fuse_dims_allows_broadcast_operand_across_fused_axes() {
let dims = [16usize, 16, 64, 64];
let out = [1isize, 16, 256, 16_384];
let lhs = [1isize, 16, 0, 256];
let rhs = [0isize, 0, 1, 64];
let all_strides: Vec<&[isize]> = vec![&out, &lhs, &rhs];
let fused = fuse_dims(&dims, &all_strides);
assert_eq!(fused.as_slice(), vec![256, 1, 64, 64]);
}
#[test]
fn test_fuse_dims_non_contiguous() {
let dims = [3, 4];
let strides1 = [1isize, 10]; let all_strides: Vec<&[isize]> = vec![&strides1];
let fused = fuse_dims(&dims, &all_strides);
assert_eq!(fused.as_slice(), vec![3, 4]); }
#[test]
fn test_fuse_dims_partial() {
let dims = [2, 3, 4];
let strides = [1isize, 2, 100]; let all_strides: Vec<&[isize]> = vec![&strides];
let fused = fuse_dims(&dims, &all_strides);
assert_eq!(fused.as_slice(), vec![6, 1, 4]); }
#[test]
fn test_fuse_dims_multiple_arrays() {
let dims = [3, 4];
let strides1 = [1isize, 3]; let strides2 = [1isize, 10]; let all_strides: Vec<&[isize]> = vec![&strides1, &strides2];
let fused = fuse_dims(&dims, &all_strides);
assert_eq!(fused.as_slice(), vec![3, 4]); }
#[test]
fn test_compute_importance_2_arrays() {
let dims = [4usize, 5];
let strides1 = [1isize, 4]; let strides2 = [5isize, 1]; let all_strides: Vec<&[isize]> = vec![&strides1, &strides2];
let order1 = index_order(&strides1);
let order2 = index_order(&strides2);
let index_orders = vec![order1.into_vec(), order2.into_vec()];
let importance = compute_importance(&dims, &all_strides, &index_orders);
assert!(importance[0] > importance[1]);
}
#[test]
fn test_sort_by_importance() {
let importance = vec![100u64, 50, 200, 10];
let perm = sort_by_importance(&importance);
assert_eq!(perm.as_slice(), vec![2, 0, 1, 3]); }
#[test]
fn test_compute_costs() {
let strides1 = [1isize, 4, 0];
let strides2 = [2isize, 1, 0];
let all_strides: Vec<&[isize]> = vec![&strides1, &strides2];
let costs = compute_costs(&all_strides);
assert_eq!(costs.as_slice(), vec![2, 2, 1]);
}
#[test]
fn test_compute_importance_with_zero_stride() {
let dims = [4usize, 5];
let strides1 = [0isize, 1]; let all_strides: Vec<&[isize]> = vec![&strides1];
let order1 = index_order(&strides1);
assert_eq!(order1.as_slice(), &[1, 1]);
let index_orders = vec![order1.into_vec()];
let importance = compute_importance(&dims, &all_strides, &index_orders);
assert_eq!(importance[0], 0);
assert!(importance[1] > 0);
}
#[test]
fn test_compute_importance_size_one_dim() {
let dims = [4usize, 1, 5];
let strides1 = [1isize, 4, 4];
let all_strides: Vec<&[isize]> = vec![&strides1];
let order1 = index_order(&strides1);
let index_orders = vec![order1.into_vec()];
let importance = compute_importance(&dims, &all_strides, &index_orders);
assert_eq!(importance[1], 0);
assert!(importance[0] > 0);
assert!(importance[2] > 0);
}
#[test]
fn test_compute_importance_output_weight() {
let dims = [4usize, 5];
let out_strides = [1isize, 4]; let in_strides = [5isize, 1]; let all_strides: Vec<&[isize]> = vec![&out_strides, &in_strides];
let order_out = index_order(&out_strides); let order_in = index_order(&in_strides); let index_orders = vec![order_out.into_vec(), order_in.into_vec()];
let importance = compute_importance(&dims, &all_strides, &index_orders);
assert!(importance[0] > importance[1]);
}
#[test]
fn test_compute_costs_owned_vecs() {
let strides_list: Vec<Vec<isize>> = vec![vec![1, 0, 3], vec![2, 0, 4]];
let costs = compute_costs(&strides_list);
assert_eq!(costs.as_slice(), vec![2, 1, 6]);
}
#[test]
fn test_compute_costs_with_zero() {
let strides1 = [0isize, 2, -3];
let strides2 = [1isize, 0, 2];
let all_strides: Vec<&[isize]> = vec![&strides1, &strides2];
let costs = compute_costs(&all_strides);
assert_eq!(costs.as_slice(), vec![1, 1, 4]);
}
fn assert_strides(cs: &[crate::inline::InlineVec<isize>], expected: &[&[isize]]) {
assert_eq!(cs.len(), expected.len());
for (actual, expected) in cs.iter().zip(expected) {
assert_eq!(actual.as_slice(), *expected);
}
}
#[test]
fn test_compress_dims_removes_fused() {
let dims = vec![12usize, 1];
let strides = vec![vec![1isize, 3]];
let (cd, cs) = compress_dims(&dims, &strides);
assert_eq!(cd.as_slice(), vec![12]);
assert_strides(&cs, &[&[1]]);
}
#[test]
fn test_compress_dims_removes_multiple() {
let dims = vec![6usize, 1, 4];
let strides = vec![vec![1isize, 2, 100]];
let (cd, cs) = compress_dims(&dims, &strides);
assert_eq!(cd.as_slice(), vec![6, 4]);
assert_strides(&cs, &[&[1, 100]]);
}
#[test]
fn test_compress_dims_no_removal() {
let dims = vec![3usize, 4];
let strides = vec![vec![1isize, 3]];
let (cd, cs) = compress_dims(&dims, &strides);
assert_eq!(cd.as_slice(), vec![3, 4]);
assert_strides(&cs, &[&[1, 3]]);
}
#[test]
fn test_compress_dims_all_ones() {
let dims = vec![1usize, 1, 1];
let strides = vec![vec![1isize, 1, 1]];
let (cd, cs) = compress_dims(&dims, &strides);
assert_eq!(cd.as_slice(), vec![1]);
assert_strides(&cs, &[&[1]]);
}
#[test]
fn test_compress_dims_multi_arrays() {
let dims = vec![6usize, 1, 4];
let strides = vec![vec![1isize, 6, 6], vec![4isize, 24, 1]];
let (cd, cs) = compress_dims(&dims, &strides);
assert_eq!(cd.as_slice(), vec![6, 4]);
assert_strides(&cs, &[&[1, 6], &[4, 1]]);
}
#[test]
fn test_compress_dims_single_dim() {
let dims = vec![5usize];
let strides = vec![vec![1isize]];
let (cd, cs) = compress_dims(&dims, &strides);
assert_eq!(cd.as_slice(), vec![5]);
assert_strides(&cs, &[&[1]]);
}
#[test]
fn test_compress_dims_single_dim_one() {
let dims = vec![1usize];
let strides = vec![vec![1isize]];
let (cd, cs) = compress_dims(&dims, &strides);
assert_eq!(cd.as_slice(), vec![1]);
assert_strides(&cs, &[&[1]]);
}
#[test]
fn test_compress_dims_empty() {
let dims: Vec<usize> = vec![];
let strides: Vec<Vec<isize>> = vec![];
let (cd, cs) = compress_dims(&dims, &strides);
assert!(cd.is_empty());
assert!(cs.is_empty());
}
#[test]
fn test_compute_importance_high_rank_levels_fit_in_u64() {
let mut dims = vec![1usize; 32];
dims[0] = 2048;
let mut strides0 = vec![2048isize; 32];
strides0[0] = 1;
let strides = [strides0.clone(), strides0.clone(), strides0];
let all_strides: Vec<&[isize]> = strides.iter().map(|s| s.as_slice()).collect();
let index_orders: Vec<Vec<usize>> = strides.iter().map(|s| index_order(s).into_vec()).collect();
let importance = compute_importance(&dims, &all_strides, &index_orders);
assert!(importance[0] > 0);
assert!(importance[1..].iter().all(|&w| w == 0));
}
#[test]
fn test_compute_importance_high_rank_keeps_level_order() {
let n = 32;
let dims = vec![2usize; n];
let strides: Vec<isize> = (0..n).map(|i| 1isize << i).collect();
let all_strides: Vec<&[isize]> = (0..3).map(|_| strides.as_slice()).collect();
let index_orders: Vec<Vec<usize>> = (0..3).map(|_| index_order(&strides).into_vec()).collect();
let importance = compute_importance(&dims, &all_strides, &index_orders);
for i in 1..n {
assert!(
importance[i - 1] > importance[i],
"axis {} ({}) is not above axis {} ({})",
i - 1,
importance[i - 1],
i,
importance[i]
);
}
}
#[test]
fn test_compute_importance_keeps_the_original_width_when_it_fits() {
let n = 32;
let mut dims = vec![1usize; n];
dims[0] = 2048;
let out_strides = vec![0isize; n];
let mut in_strides = vec![2048isize; n];
in_strides[0] = 2;
let all_strides: [&[isize]; 2] = [&out_strides, &in_strides];
let index_orders: Vec<Vec<usize>> = [&out_strides[..], &in_strides[..]]
.iter()
.map(|s| index_order(s).into_vec())
.collect();
let importance = compute_importance(&dims, &all_strides, &index_orders);
assert_eq!(importance[0], 1u64 << 62);
assert!(importance[1..].iter().all(|&w| w == 0));
}
#[test]
fn test_compute_importance_rank_64_shares_the_top_weight() {
let n = 64;
let mut dims = vec![1usize; n];
dims[0] = 1024;
dims[1] = 2;
let mut strides = vec![4096isize; n];
strides[0] = 4;
strides[1] = 1;
let all_strides: Vec<&[isize]> = (0..3).map(|_| strides.as_slice()).collect();
let index_orders: Vec<Vec<usize>> = (0..3).map(|_| index_order(&strides).into_vec()).collect();
let importance = compute_importance(&dims, &all_strides, &index_orders);
assert_eq!(importance[0], 6u64 << 61);
assert_eq!(importance[0], importance[1]);
assert!(importance[2..].iter().all(|&w| w == 0));
}
#[test]
fn test_compute_importance_rank_65_broadcast_output_keeps_live_axes_distinct() {
let n = 65;
let mut dims = vec![1usize; n];
dims[0] = 2;
dims[2] = 2;
let out_strides = vec![0isize; n];
let in_strides: Vec<isize> = (0..n).map(|i| i as isize + 1).collect();
let all_strides: [&[isize]; 2] = [&out_strides, &in_strides];
let index_orders: Vec<Vec<usize>> = [&out_strides[..], &in_strides[..]]
.iter()
.map(|s| index_order(s).into_vec())
.collect();
let importance = compute_importance(&dims, &all_strides, &index_orders);
assert_eq!(
importance[0],
1u64 << 63,
"axis 0 (stride 1) takes the top level"
);
assert_eq!(
importance[2],
1u64 << 62,
"axis 2 (stride 3) keeps the level below it"
);
assert!(importance
.iter()
.enumerate()
.all(|(i, &w)| i == 0 || i == 2 || w == 0));
}
#[test]
fn test_compute_importance_rank_65_two_inputs_reject_cap_63() {
let n = 65;
let mut dims = vec![1usize; n];
dims[0] = 2;
let out_strides = vec![0isize; n];
let in_strides: Vec<isize> = (0..n).map(|i| i as isize + 1).collect();
let all_strides: [&[isize]; 3] = [&out_strides, &in_strides, &in_strides];
let index_orders: Vec<Vec<usize>> = [&out_strides[..], &in_strides[..], &in_strides[..]]
.iter()
.map(|s| index_order(s).into_vec())
.collect();
let importance = compute_importance(&dims, &all_strides, &index_orders);
assert_eq!(
importance[0],
1u64 << 63,
"two inputs at cap 62: 2^62 + 2^62"
);
assert!(importance[1..].iter().all(|&w| w == 0));
}
#[test]
fn test_compute_importance_matches_exact_reference() {
fn reference(dims: &[usize], strides: &[&[isize]], orders: &[Vec<usize>]) -> Vec<u128> {
let (n, m) = (dims.len(), strides.len());
if n == 0 || m == 0 {
return Vec::new();
}
let g = 64 - (m as u64 + 1).leading_zeros();
let mut weights = vec![0u128; n];
for i in 0..n {
if strides[0][i] != 0 {
let shift = g * (n - orders[0][i]) as u32;
weights[i] = (1u128 << (g + 1)) * (1u128 << shift);
}
}
for k in 1..m {
for i in 0..n {
if strides[k][i] != 0 {
weights[i] += 1u128 << (g * (n - orders[k][i]) as u32);
}
}
}
for i in 0..n {
if dims[i] <= 1 {
weights[i] = 0;
}
}
weights
}
fn permutations(items: &[isize]) -> Vec<Vec<isize>> {
fn rec(items: &mut [isize], pos: usize, out: &mut Vec<Vec<isize>>) {
if pos == items.len() {
out.push(items.to_vec());
return;
}
for i in pos..items.len() {
items.swap(pos, i);
rec(items, pos + 1, out);
items.swap(pos, i);
}
}
let mut items = items.to_vec();
let mut out = Vec::new();
rec(&mut items, 0, &mut out);
out
}
fn stride_tuples(perms: &[Vec<isize>], m: usize, crossed: &[usize]) -> Vec<Vec<Vec<isize>>> {
let identity = perms[0].clone();
let mut tuples = Vec::new();
let mut pick = vec![0usize; crossed.len()];
loop {
let mut tuple = vec![identity.clone(); m];
for (slot, &operand) in crossed.iter().enumerate() {
tuple[operand] = perms[pick[slot]].clone();
}
tuples.push(tuple);
let mut carry = true;
for p in pick.iter_mut() {
if !carry {
break;
}
*p += 1;
if *p == perms.len() {
*p = 0;
} else {
carry = false;
}
}
if carry {
break;
}
}
tuples
}
fn check(dims: &[usize], strides: &[Vec<isize>]) {
let all_strides: Vec<&[isize]> = strides.iter().map(|s| s.as_slice()).collect();
let orders: Vec<Vec<usize>> = strides.iter().map(|s| index_order(s).into_vec()).collect();
let got: Vec<u128> = compute_importance(dims, &all_strides, &orders)
.as_slice()
.iter()
.map(|&w| w as u128)
.collect();
let want = reference(dims, &all_strides, &orders);
assert_eq!(
got.as_slice(),
want.as_slice(),
"dims {:?} strides {:?}",
dims,
strides
);
}
let mut broadcast_cases = 0usize;
for n in 1..=4usize {
let powers: Vec<isize> = (0..n).map(|i| 1isize << i).collect();
let perms = permutations(&powers);
let mut dim_grids: Vec<Vec<usize>> = vec![vec![2usize; n]];
for i in 0..n {
let mut dims = vec![2usize; n];
dims[i] = 1;
dim_grids.push(dims);
}
for i in 0..n {
for j in (i + 1)..n {
let mut dims = vec![2usize; n];
dims[i] = 1;
dims[j] = 1;
dim_grids.push(dims);
}
}
for m in 1..=4usize {
let independent: Vec<Vec<usize>> = if perms.len().pow(m as u32) <= 2000 {
vec![(0..m).collect()]
} else {
(0..m)
.flat_map(|i| ((i + 1)..m).map(move |j| vec![i, j]))
.collect()
};
let mut tuples: Vec<Vec<Vec<isize>>> = Vec::new();
for crossed in &independent {
tuples.extend(stride_tuples(&perms, m, crossed));
}
for dims in &dim_grids {
for strides in &tuples {
check(dims, strides);
}
}
let broadcast_tuples: Vec<Vec<Vec<isize>>> = if perms.len().pow(m as u32) <= 600 {
tuples.clone()
} else {
let mut t = Vec::new();
for operand in 0..m {
t.extend(stride_tuples(&perms, m, &[operand]));
}
t
};
for strides in &broadcast_tuples {
for zero_mask in 0..(1u32 << n) {
let receivers = if zero_mask == 0 { 1 } else { m + 1 };
for role in 0..receivers {
let mut strides = strides.clone();
for (k, operand) in strides.iter_mut().enumerate() {
if role == m || role == k {
for (i, s) in operand.iter_mut().enumerate() {
if zero_mask & (1 << i) != 0 {
*s = 0;
}
}
}
}
let dims = &dim_grids[broadcast_cases % dim_grids.len()];
broadcast_cases += 1;
check(dims, &strides);
}
}
}
}
}
}