Skip to main content

strided_basic/
kernel.rs

1//! Kernel iteration engine ported from Julia's Strided.jl/src/mapreduce.jl
2//!
3//! This module implements the core iteration engine that follows Julia's
4//! `_mapreduce_kernel!` pattern for cache-optimized strided array operations.
5
6use crate::fuse::{compress_dims, fuse_dims};
7use crate::inline::{InlineVec, OperandVec};
8use crate::{block, order, Exec, Result, StridedError};
9
10/// Maximum total elements for the small tensor fast path.
11/// Tensors at or below this size skip `compute_order` and `compute_block_sizes`
12/// since they fit in L1 cache and blocking provides no benefit.
13pub const SMALL_TENSOR_THRESHOLD: usize = 1024;
14
15/// Blocking metadata produced by the execution planners; not a layout-validity proof.
16#[derive(Debug)]
17pub struct KernelPlan {
18    #[cfg_attr(not(test), allow(dead_code))]
19    pub(crate) order: InlineVec<usize>, // inner -> outer
20    pub block: InlineVec<usize>,
21}
22
23/// Build an execution plan for strided iteration (used only in tests).
24///
25/// This follows Julia's `_mapreduce_order!` -> `_mapreduce_block!` pipeline
26/// without fusion:
27/// 1. Compute optimal iteration order
28/// 2. Reorder dims and strides into that order
29/// 3. Compute block sizes for cache efficiency
30#[cfg(test)]
31pub(crate) fn build_plan(
32    dims: &[usize],
33    strides_list: &[&[isize]],
34    dest_index: Option<usize>,
35    elem_size: usize,
36) -> KernelPlan {
37    let order = order::compute_order(dims, strides_list, dest_index);
38    let ordered_dims: InlineVec<usize> = order.iter().map(|&d| dims[d]).collect();
39    let ordered_strides: OperandVec<InlineVec<isize>> = strides_list
40        .iter()
41        .map(|strides| order.iter().map(|&d| strides[d]).collect())
42        .collect();
43    let ordered_strides_refs: OperandVec<&[isize]> =
44        ordered_strides.iter().map(|s| s.as_slice()).collect();
45    let block = block::compute_block_sizes(&ordered_dims, &ordered_strides_refs, elem_size);
46    KernelPlan { order, block }
47}
48
49/// Build an execution plan with dimension fusion.
50///
51/// Pipeline: order -> reorder -> fuse -> block.
52///
53/// Ordering first ensures that dimensions are sorted by stride importance
54/// (smallest stride innermost). Fusing *after* ordering catches contiguous
55/// dimensions regardless of the original memory layout (column-major,
56/// row-major, or any permutation).
57///
58/// Returns `(fused_dims, ordered_strides, KernelPlan)` where dimensions
59/// and strides are already in iteration order (plan.order is identity).
60pub(crate) fn build_plan_fused(
61    dims: &[usize],
62    strides_list: &[&[isize]],
63    dest_index: Option<usize>,
64    elem_size: usize,
65) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
66    // 1. Compute optimal iteration order on original dims
67    let order = order::compute_order(dims, strides_list, dest_index);
68
69    // 2. Reorder dims and strides
70    let ordered_dims: InlineVec<usize> = order.iter().map(|&d| dims[d]).collect();
71    let ordered_strides: OperandVec<InlineVec<isize>> = strides_list
72        .iter()
73        .map(|strides| order.iter().map(|&d| strides[d]).collect())
74        .collect();
75    let ordered_strides_refs: OperandVec<&[isize]> =
76        ordered_strides.iter().map(|s| s.as_slice()).collect();
77
78    // 3. Fuse contiguous dimensions in ordered space
79    let fused_dims = fuse_dims(&ordered_dims, &ordered_strides_refs);
80
81    // 4. Compress: remove size-1 dimensions to reduce loop depth
82    let (compressed_dims, compressed_strides) = compress_dims(&fused_dims, &ordered_strides_refs);
83    let compressed_strides_refs: OperandVec<&[isize]> =
84        compressed_strides.iter().map(|s| s.as_slice()).collect();
85
86    // 5. Compute blocks on the already ordered axes
87    let identity: InlineVec<usize> = (0..compressed_dims.len()).collect();
88    let block = block::compute_block_sizes(&compressed_dims, &compressed_strides_refs, elem_size);
89
90    (
91        compressed_dims,
92        compressed_strides,
93        KernelPlan {
94            order: identity,
95            block,
96        },
97    )
98}
99
100/// Simplified plan for small tensors that fit in L1 cache.
101///
102/// Skips `compute_order` and `compute_block_sizes` since blocking is
103/// unnecessary for small data. Only fuses and compresses dimensions
104/// to reduce loop depth.
105///
106/// Returns `(fused_dims, fused_strides, KernelPlan)` where the plan's
107/// order is identity and block sizes equal the full dimension sizes.
108pub(crate) fn build_plan_fused_small(
109    dims: &[usize],
110    strides_list: &[&[isize]],
111) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
112    // Single fuse + compress pass (no ordering needed)
113    let fused = fuse_dims(dims, strides_list);
114    let (fused_dims, fused_strides) = compress_dims(&fused, strides_list);
115
116    // Block = full dimension (no tiling)
117    let block = fused_dims.clone();
118    let identity: InlineVec<usize> = (0..fused_dims.len()).collect();
119
120    (
121        fused_dims,
122        fused_strides,
123        KernelPlan {
124            order: identity,
125            block,
126        },
127    )
128}
129
130// ============================================================================
131// Block-based iteration with inner stride callback
132// ============================================================================
133
134/// Iterate over blocks, calling f with (offsets, block_len, inner_strides).
135///
136/// The callback receives the current byte offsets for each array, the number
137/// of elements in the innermost block, and the innermost strides for each array.
138/// This allows the caller to implement vectorized inner loops.
139#[cfg(test)]
140#[inline]
141pub(crate) fn for_each_inner_block<F>(
142    dims: &[usize],
143    plan: &KernelPlan,
144    strides_list: &[&[isize]],
145    mut f: F,
146) -> Result<()>
147where
148    F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
149{
150    let rank = dims.len();
151    if rank == 0 {
152        let offsets: OperandVec<isize> = strides_list.iter().map(|_| 0isize).collect();
153        return f(&offsets, 1, &[]);
154    }
155
156    // Reorder dimensions and strides according to plan
157    let ordered_dims: InlineVec<usize> = plan.order.iter().map(|&d| dims[d]).collect();
158    let ordered_blocks: InlineVec<usize> = plan.block.clone();
159
160    // Build stride vectors for each array, ordered by plan
161    let mut ordered_strides: OperandVec<InlineVec<isize>> = OperandVec::new();
162    for strides in strides_list {
163        ordered_strides.push(plan.order.iter().map(|&d| strides[d]).collect());
164    }
165    let ordered_strides_refs: OperandVec<&[isize]> =
166        ordered_strides.iter().map(|s| s.as_slice()).collect();
167
168    // Initial offsets (all zero)
169    let mut offsets: OperandVec<isize> = strides_list.iter().map(|_| 0isize).collect();
170
171    // Call the specialized kernel based on rank
172    match rank {
173        1 => kernel_1d_inner(
174            &ordered_dims,
175            &ordered_blocks,
176            &ordered_strides_refs,
177            &mut offsets,
178            &mut f,
179        ),
180        2 => kernel_2d_inner(
181            &ordered_dims,
182            &ordered_blocks,
183            &ordered_strides_refs,
184            &mut offsets,
185            &mut f,
186        ),
187        3 => kernel_3d_inner(
188            &ordered_dims,
189            &ordered_blocks,
190            &ordered_strides_refs,
191            &mut offsets,
192            &mut f,
193        ),
194        4 => kernel_4d_inner(
195            &ordered_dims,
196            &ordered_blocks,
197            &ordered_strides_refs,
198            &mut offsets,
199            &mut f,
200        ),
201        5 => kernel_5d_inner(
202            &ordered_dims,
203            &ordered_blocks,
204            &ordered_strides_refs,
205            &mut offsets,
206            &mut f,
207        ),
208        6 => kernel_6d_inner(
209            &ordered_dims,
210            &ordered_blocks,
211            &ordered_strides_refs,
212            &mut offsets,
213            &mut f,
214        ),
215        7 => kernel_7d_inner(
216            &ordered_dims,
217            &ordered_blocks,
218            &ordered_strides_refs,
219            &mut offsets,
220            &mut f,
221        ),
222        8 => kernel_8d_inner(
223            &ordered_dims,
224            &ordered_blocks,
225            &ordered_strides_refs,
226            &mut offsets,
227            &mut f,
228        ),
229        _ => kernel_nd_inner_iterative(
230            &ordered_dims,
231            &ordered_blocks,
232            &ordered_strides_refs,
233            &mut offsets,
234            &mut f,
235        ),
236    }
237}
238
239// ============================================================================
240// Macro-generated rank-specialized kernels (inner-block callback)
241// ============================================================================
242
243// Every loop below advances an offset only when another position along its
244// level follows, and each loop rewinds its own level on completion. Offsets
245// therefore only ever hold reachable positions of the validated layouts (plus
246// the caller's initial offsets), so no intermediate value can overflow even
247// when a layout ends within one stride of `isize::MAX` (issue #243
248// follow-up). The rewind distance is the difference of two reachable offsets,
249// so it is representable as well.
250
251/// Element-level nested loops for ranks >= 2.
252///
253/// Iterates over the element block, calling `f` at each innermost position.
254/// Levels are listed from outermost to innermost (excluding level 0 which is
255/// the callback level). For a rank-N kernel, element levels are N-1, N-2, ..., 1.
256/// Each level leaves the offsets where it found them.
257macro_rules! elem_loops {
258    // Base case: single level (innermost element level).
259    // Iterates blens[$lv] times, calling f and advancing by stride[$lv]
260    // between calls.
261    ($offsets:ident, $strides:ident, $f:ident, $blens:ident, $is:ident; $lv:literal) => {
262        for _i in 0..$blens[$lv] {
263            $f($offsets, $blens[0], &$is)?;
264            if _i + 1 < $blens[$lv] {
265                for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
266                    *o += s[$lv];
267                }
268            }
269        }
270        let _back = $blens[$lv].saturating_sub(1) as isize;
271        for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
272            *o -= _back * s[$lv];
273        }
274    };
275    // Recursive case: outermost level wraps inner levels, which rewind
276    // themselves; this level advances between inner passes.
277    ($offsets:ident, $strides:ident, $f:ident, $blens:ident, $is:ident;
278     $lv:literal, $next:literal $(, $rest:literal)*) => {
279        for _i in 0..$blens[$lv] {
280            elem_loops!($offsets, $strides, $f, $blens, $is; $next $(, $rest)*);
281            if _i + 1 < $blens[$lv] {
282                for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
283                    *o += s[$lv];
284                }
285            }
286        }
287        let _back = $blens[$lv].saturating_sub(1) as isize;
288        for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
289            *o -= _back * s[$lv];
290        }
291    };
292}
293
294/// Block-level nested while loops for ranks >= 2.
295///
296/// Each block level iterates over tiles of the corresponding dimension.
297/// At level 0 (innermost), element loops are executed. Each block level
298/// advances to the next tile only when one follows and rewinds itself on
299/// completion; inner levels rewind themselves.
300macro_rules! block_loop {
301    // Base case: single block level (the innermost).
302    ($dims:ident, $blocks:ident, $strides:ident, $offsets:ident, $f:ident,
303     $blens:ident, $is:ident; elem=[$($el:literal),+]; $lv0:literal; top=$top:literal) => {{
304        let mut _j = 0usize;
305        let mut _advanced = 0usize;
306        while _j < $dims[$lv0] {
307            $blens[$lv0] = $blocks[$lv0].max(1).min($dims[$lv0]).min($dims[$lv0] - _j);
308            elem_loops!($offsets, $strides, $f, $blens, $is; $($el),+);
309            _j += $blens[$lv0];
310            if _j < $dims[$lv0] {
311                for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
312                    *o += ($blens[$lv0] as isize) * s[$lv0];
313                }
314                _advanced = _j;
315            }
316        }
317        for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
318            *o -= (_advanced as isize) * s[$lv0];
319        }
320    }};
321    // Recursive case: outer block level wraps inner block levels.
322    ($dims:ident, $blocks:ident, $strides:ident, $offsets:ident, $f:ident,
323     $blens:ident, $is:ident; elem=[$($el:literal),+];
324     $lv:literal, $next:literal $(, $rest:literal)*; top=$top:literal) => {{
325        let mut _j = 0usize;
326        let mut _advanced = 0usize;
327        while _j < $dims[$lv] {
328            $blens[$lv] = $blocks[$lv].max(1).min($dims[$lv]).min($dims[$lv] - _j);
329            block_loop!($dims, $blocks, $strides, $offsets, $f, $blens, $is;
330                elem=[$($el),+]; $next $(, $rest)*; top=$top);
331            _j += $blens[$lv];
332            if _j < $dims[$lv] {
333                for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
334                    *o += ($blens[$lv] as isize) * s[$lv];
335                }
336                _advanced = _j;
337            }
338        }
339        for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
340            *o -= (_advanced as isize) * s[$lv];
341        }
342    }};
343}
344
345/// Generate a rank-specialized kernel function.
346///
347/// For rank 1 there are no element loops; only a single block loop on dim 0.
348/// For rank >= 2, block loops nest from outermost to innermost (dim 0), and
349/// element loops nest from dim N-1 down to dim 1 inside the innermost block.
350/// The offsets are back at their starting values on return.
351macro_rules! make_kernel {
352    // Rank 1: single block loop, no element nesting.
353    ($name:ident, rank=1) => {
354        #[inline]
355        fn $name<F>(
356            dims: &[usize],
357            blocks: &[usize],
358            strides: &[&[isize]],
359            offsets: &mut [isize],
360            f: &mut F,
361        ) -> Result<()>
362        where
363            F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
364        {
365            let d0 = dims[0];
366            let b0 = blocks[0].max(1).min(d0);
367            let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
368
369            let mut j0 = 0usize;
370            let mut advanced = 0usize;
371            while j0 < d0 {
372                let blen0 = b0.min(d0 - j0);
373                f(offsets, blen0, &inner_strides)?;
374                j0 += blen0;
375                if j0 < d0 {
376                    for (o, s) in offsets.iter_mut().zip(strides.iter()) {
377                        *o += (blen0 as isize) * s[0];
378                    }
379                    advanced = j0;
380                }
381            }
382            for (o, s) in offsets.iter_mut().zip(strides.iter()) {
383                *o -= (advanced as isize) * s[0];
384            }
385            Ok(())
386        }
387    };
388    // Rank >= 2: nested block loops + element loops.
389    //   block=[outermost, ..., 0]  - block loop levels from outermost to innermost
390    //   elem=[N-1, ..., 1]         - element loop levels from outermost to innermost
391    //   top=N-1                    - topmost element level (= rank - 1)
392    ($name:ident, rank=$rank:literal,
393     block=[$($blk:literal),+], elem=[$($el:literal),+], top=$top:literal) => {
394        #[inline]
395        fn $name<F>(
396            dims: &[usize],
397            blocks: &[usize],
398            strides: &[&[isize]],
399            offsets: &mut [isize],
400            f: &mut F,
401        ) -> Result<()>
402        where
403            F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
404        {
405            let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
406            let mut blens = [0usize; $rank];
407            block_loop!(dims, blocks, strides, offsets, f, blens, inner_strides;
408                elem=[$($el),+]; $($blk),+; top=$top);
409            Ok(())
410        }
411    };
412}
413
414make_kernel!(kernel_1d_inner, rank = 1);
415make_kernel!(
416    kernel_2d_inner,
417    rank = 2,
418    block = [1, 0],
419    elem = [1],
420    top = 1
421);
422make_kernel!(
423    kernel_3d_inner,
424    rank = 3,
425    block = [2, 1, 0],
426    elem = [2, 1],
427    top = 2
428);
429make_kernel!(
430    kernel_4d_inner,
431    rank = 4,
432    block = [3, 2, 1, 0],
433    elem = [3, 2, 1],
434    top = 3
435);
436make_kernel!(
437    kernel_5d_inner,
438    rank = 5,
439    block = [4, 3, 2, 1, 0],
440    elem = [4, 3, 2, 1],
441    top = 4
442);
443make_kernel!(
444    kernel_6d_inner,
445    rank = 6,
446    block = [5, 4, 3, 2, 1, 0],
447    elem = [5, 4, 3, 2, 1],
448    top = 5
449);
450make_kernel!(
451    kernel_7d_inner,
452    rank = 7,
453    block = [6, 5, 4, 3, 2, 1, 0],
454    elem = [6, 5, 4, 3, 2, 1],
455    top = 6
456);
457make_kernel!(
458    kernel_8d_inner,
459    rank = 8,
460    block = [7, 6, 5, 4, 3, 2, 1, 0],
461    elem = [7, 6, 5, 4, 3, 2, 1],
462    top = 7
463);
464
465/// N-dimensional kernel with inner block callback (iterative form).
466///
467/// Fallback for rank >= 9. Uses a carry-style increment over outer levels
468/// instead of compile-time unrolled nested loops.
469#[inline]
470fn kernel_nd_inner_iterative<F>(
471    dims: &[usize],
472    blocks: &[usize],
473    strides: &[&[isize]],
474    offsets: &mut [isize],
475    f: &mut F,
476) -> Result<()>
477where
478    F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
479{
480    let rank = dims.len();
481    debug_assert!(rank >= 9);
482
483    let d0 = dims[0];
484    let b0 = blocks[0].max(1).min(d0);
485    let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
486
487    // Current position for each outer level (1..rank-1). Level 0 uses block loop.
488    let mut idx: Vec<usize> = vec![0usize; rank];
489
490    // As in the rank-specialized kernels, offsets advance only when another
491    // position follows and each level rewinds from its last position, so they
492    // never leave the reachable span.
493    if dims.contains(&0) {
494        return Ok(());
495    }
496    loop {
497        // Level 0: callback over contiguous block fragments.
498        let mut j0 = 0usize;
499        let mut advanced = 0usize;
500        while j0 < d0 {
501            let blen0 = b0.min(d0 - j0);
502            f(offsets, blen0, &inner_strides)?;
503            j0 += blen0;
504            if j0 < d0 {
505                for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
506                    *offset += (blen0 as isize) * s[0];
507                }
508                advanced = j0;
509            }
510        }
511        for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
512            *offset -= (advanced as isize) * s[0];
513        }
514
515        // Carry-style increment for outer levels.
516        let mut level = 1usize;
517        loop {
518            if idx[level] + 1 < dims[level] {
519                idx[level] += 1;
520                for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
521                    *offset += s[level];
522                }
523                break;
524            }
525
526            let last = (dims[level] - 1) as isize;
527            idx[level] = 0;
528            for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
529                *offset -= last * s[level];
530            }
531            level += 1;
532            if level == rank {
533                return Ok(());
534            }
535        }
536    }
537}
538
539// ============================================================================
540// Pre-ordered iteration (for threaded leaf functions)
541// ============================================================================
542
543/// Iterate over blocks with pre-ordered dimensions and initial offsets.
544///
545/// Unlike `for_each_inner_block`, this function assumes that `dims`, `blocks`,
546/// and `strides` are **already in iteration order** (i.e., identity ordering).
547/// It also accepts `initial_offsets` which are added to the starting offsets
548/// before iteration begins.
549///
550/// This avoids the redundant re-ordering and per-callback `Vec` allocation
551/// that `for_each_inner_block_with_offsets` previously incurred.
552///
553/// The block-walking machinery is compiled once (`preordered_dyn`): a generic
554/// caller only instantiates its own callback, reached through one indirect call
555/// per inner block (a run of elements, never per element). Keeping the walk
556/// generic would duplicate it for every operation, dtype and element-op
557/// combination of every downstream crate.
558#[inline]
559pub(crate) fn for_each_inner_block_preordered<S: AsRef<[isize]>, F>(
560    dims: &[usize],
561    blocks: &[usize],
562    strides: &[S],
563    initial_offsets: &[isize],
564    mut f: F,
565) -> Result<()>
566where
567    F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
568{
569    let refs: OperandVec<&[isize]> = strides.iter().map(|s| s.as_ref()).collect();
570    preordered_dyn(dims, blocks, &refs, initial_offsets, &mut f)
571}
572
573type BlockFn<'a> = &'a mut dyn FnMut(&[isize], usize, &[isize]) -> Result<()>;
574
575#[inline(never)]
576fn preordered_dyn(
577    dims: &[usize],
578    blocks: &[usize],
579    strides: &[&[isize]],
580    initial_offsets: &[isize],
581    mut f: BlockFn<'_>,
582) -> Result<()> {
583    let rank = dims.len();
584    if rank == 0 {
585        return f(initial_offsets, 1, &[]);
586    }
587
588    // Start from initial_offsets (kernel functions reset to starting values at end)
589    let mut offsets: OperandVec<isize> = initial_offsets.iter().copied().collect();
590
591    match rank {
592        1 => kernel_1d_inner(dims, blocks, strides, &mut offsets, &mut f),
593        2 => kernel_2d_inner(dims, blocks, strides, &mut offsets, &mut f),
594        3 => kernel_3d_inner(dims, blocks, strides, &mut offsets, &mut f),
595        4 => kernel_4d_inner(dims, blocks, strides, &mut offsets, &mut f),
596        5 => kernel_5d_inner(dims, blocks, strides, &mut offsets, &mut f),
597        6 => kernel_6d_inner(dims, blocks, strides, &mut offsets, &mut f),
598        7 => kernel_7d_inner(dims, blocks, strides, &mut offsets, &mut f),
599        8 => kernel_8d_inner(dims, blocks, strides, &mut offsets, &mut f),
600        _ => kernel_nd_inner_iterative(dims, blocks, strides, &mut offsets, &mut f),
601    }
602}
603
604// ============================================================================
605// Utility functions
606// ============================================================================
607
608/// Check exact shape agreement before prevalidated replay.
609///
610/// # Examples
611///
612/// ```
613/// use strided_basic::execution::ensure_same_shape;
614/// ensure_same_shape(&[2, 3], &[2, 3]).unwrap();
615/// assert!(ensure_same_shape(&[2, 3], &[3, 2]).is_err());
616/// ```
617///
618/// # Errors
619///
620/// Returns [`StridedError::RankMismatch`] when the two shapes have different
621/// ranks, and [`StridedError::ShapeMismatch`] when their extents differ.
622pub fn ensure_same_shape(a: &[usize], b: &[usize]) -> Result<()> {
623    if a.len() != b.len() {
624        return Err(crate::StridedError::RankMismatch(a.len(), b.len()));
625    }
626    if a != b {
627        return Err(crate::StridedError::ShapeMismatch(a.to_vec(), b.to_vec()));
628    }
629    Ok(())
630}
631
632#[derive(Copy, Clone, Debug, Eq, PartialEq)]
633pub(crate) enum ContiguousLayout {
634    /// C-like layout: last axis varies fastest.
635    RowMajor,
636    /// Julia/Fortran-like layout: first axis varies fastest.
637    ColMajor,
638}
639
640/// Returns the contiguous memory layout kind for the given (dims, strides).
641///
642/// Notes:
643/// - Ignores axes with `dim <= 1` since they do not affect addressability.
644/// - Does not treat negative-stride views as contiguous for fast-path purposes.
645pub(crate) fn contiguous_layout(dims: &[usize], strides: &[isize]) -> Option<ContiguousLayout> {
646    if dims.len() != strides.len() {
647        return None;
648    }
649    if dims.is_empty() {
650        return Some(ContiguousLayout::RowMajor);
651    }
652
653    // Row-major: check from last to first.
654    let mut expected = 1isize;
655    let mut row_ok = true;
656    for (&dim, &stride) in dims.iter().rev().zip(strides.iter().rev()) {
657        if dim <= 1 {
658            continue;
659        }
660        if stride != expected {
661            row_ok = false;
662            break;
663        }
664        expected = expected.saturating_mul(dim as isize);
665    }
666    if row_ok {
667        return Some(ContiguousLayout::RowMajor);
668    }
669
670    // Col-major: check from first to last.
671    let mut expected = 1isize;
672    for (&dim, &stride) in dims.iter().zip(strides.iter()) {
673        if dim <= 1 {
674            continue;
675        }
676        if stride != expected {
677            return None;
678        }
679        expected = expected.saturating_mul(dim as isize);
680    }
681    Some(ContiguousLayout::ColMajor)
682}
683
684/// Checked element count of `dims`.
685///
686/// A shape containing a zero extent has zero elements even when the product
687/// of its other extents would overflow; such views pass
688/// `strided_view::validate_bounds`, so this must not form that product. A
689/// nonempty shape whose element count exceeds `usize::MAX` (for example a
690/// huge stride-0 broadcast) returns [`StridedError::OffsetOverflow`].
691pub(crate) fn total_len(dims: &[usize]) -> Result<usize> {
692    if dims.contains(&0) {
693        return Ok(0);
694    }
695    dims.iter()
696        .try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
697        .ok_or(StridedError::OffsetOverflow)
698}
699
700/// Whether the sequential contiguous fast path should be used.
701///
702/// When a fork over `total` elements of `class` pays and `exec` has a second slot,
703/// the contiguous fast path must not be taken so that the parallel kernel path
704/// can be reached. A serial token has no threaded path to reach and the
705/// sequential slice loop is the right kernel.
706#[inline]
707pub(crate) fn use_sequential_fast_path(
708    class: crate::cost::KernelClass,
709    total: usize,
710    exec: &Exec<'_>,
711) -> bool {
712    !crate::threading::is_parallel(class, total, exec)
713}
714
715/// Returns the common contiguous layout if **all** provided stride arrays
716/// share the same contiguous layout for the given `dims`.
717///
718/// Returns `None` if `strides_list` is empty, any array is not contiguous,
719/// or any two arrays have different contiguous layouts.
720#[inline]
721pub(crate) fn same_contiguous_layout(
722    dims: &[usize],
723    strides_list: &[&[isize]],
724) -> Option<ContiguousLayout> {
725    let first = contiguous_layout(dims, strides_list.first()?)?;
726    for strides in &strides_list[1..] {
727        if contiguous_layout(dims, strides)? != first {
728            return None;
729        }
730    }
731    Some(first)
732}
733
734/// Returns the common contiguous layout only when the sequential fast path
735/// should be used (a fork over the elements does not pay for `class`, or a serial token).
736///
737/// `class` is the cost class of the kernel the caller would otherwise fork:
738/// a copy asks as `Copy`, a reduction as `Reduce`, an element map as `Map`.
739///
740/// Returns [`StridedError::OffsetOverflow`] when the element count of `dims`
741/// does not fit in `usize`.
742#[inline]
743pub(crate) fn sequential_contiguous_layout(
744    class: crate::cost::KernelClass,
745    dims: &[usize],
746    strides_list: &[&[isize]],
747    exec: &Exec<'_>,
748) -> Result<Option<ContiguousLayout>> {
749    if !use_sequential_fast_path(class, total_len(dims)?, exec) {
750        return Ok(None);
751    }
752    Ok(same_contiguous_layout(dims, strides_list))
753}
754
755#[cfg(test)]
756#[path = "kernel/tests/tests.rs"]
757mod tests;