Skip to main content

strided_basic/
raw_ops.rs

1//! Allocation-free copy/axpy over borrowed raw strided layouts.
2//!
3//! The map/zip kernels build a traversal plan per call; for small replay
4//! copies that fixed cost dominates. These entry points take
5//! [`RawStridedRef`]/[`RawStridedMut`], fuse the stride pair into a loop nest
6//! (inline storage for fused ranks at most [`RAW_FUSED_RANK_LIMIT`], a stack
7//! layout bounded by the moving-axis count above that), and run plain loops -
8//! no view plan, no cache, and no per-element allocation on any call path; the
9//! `replay_*_raw` entries allocate nothing at any rank on a serial token.
10//! Higher *original* ranks are normalized and fused before that choice is
11//! made, so they no longer leave the fused replay.
12
13use crate::cost::KernelClass;
14use crate::{ElementOpApply, Exec, RawStridedMut, RawStridedRef, Result};
15use core::mem::MaybeUninit;
16use core::num::NonZeroUsize;
17use core::ops::{Add, Mul};
18
19/// Rank up to which a fused loop nest is stored inline.
20///
21/// It selects the traversal: a layout of at most this many axes replays through
22/// the inline loop nest, a longer one through the out-of-line wide loop. It
23/// does not decide allocation for the `replay_*_raw` entries, which allocate
24/// nothing at any rank on a serial token (see [`replay_copy_raw`]).
25///
26/// The stateless [`copy_scale_raw`] family and the compilation of
27/// [`crate::CopyPlan`] fuse any rank. An *original* rank above this limit needs
28/// one transient fusion scratch buffer there even when the fused layout still
29/// fits inline, because fusion happens before the representation is chosen.
30pub const RAW_FUSED_RANK_LIMIT: usize = 8;
31
32/// Capacity of the stack storage of the wide replay route.
33///
34/// A replay reaches its loops only with a checked, nonzero element count, and
35/// every axis of extent above 1 at least doubles that count, so
36/// `2^m <= total <= usize::MAX` bounds the `m` moving axes by
37/// `usize::BITS - 1`. Extent-1 axes are dropped before the bound is used: their
38/// coordinate is 0 throughout the walk, so dropping them changes neither the
39/// slots nor their column-major order.
40pub(crate) const MAX_MOVING_AXES: usize = usize::BITS as usize;
41
42/// One fused axis, used while sorting and merging axes and when a layout has to
43/// spill beyond [`RAW_FUSED_RANK_LIMIT`].
44#[derive(Clone, Copy, Debug)]
45pub(crate) struct FusedAxis {
46    pub(crate) dim: usize,
47    pub(crate) dst: isize,
48    pub(crate) src: isize,
49}
50
51const EMPTY_AXIS: FusedAxis = FusedAxis {
52    dim: 1,
53    dst: 0,
54    src: 0,
55};
56
57/// Stack-allocated fused stride pair (axes ordered by destination stride,
58/// adjacent contiguous axes merged). Built once and replayed by both the
59/// per-call raw kernels and the prepared [`crate::CopyPlan`].
60///
61/// This is the representation every call site replays through, so it keeps the
62/// exact shape, size and `Copy`-ness it had before high-rank fusion existed.
63#[derive(Clone, Copy, Debug)]
64pub(crate) struct FusedPairLayout {
65    pub(crate) rank: usize,
66    pub(crate) dims: [usize; RAW_FUSED_RANK_LIMIT],
67    pub(crate) dst_strides: [isize; RAW_FUSED_RANK_LIMIT],
68    pub(crate) src_strides: [isize; RAW_FUSED_RANK_LIMIT],
69}
70
71impl FusedPairLayout {
72    /// An empty rank-zero layout (one element at the base offset).
73    ///
74    /// Used as the neutral value when an inline `TinyVec<[CopyPlan; N]>` is
75    /// default-initialized; it is never executed as a real plan.
76    fn empty() -> Self {
77        Self {
78            rank: 0,
79            dims: [1; RAW_FUSED_RANK_LIMIT],
80            dst_strides: [0; RAW_FUSED_RANK_LIMIT],
81            src_strides: [0; RAW_FUSED_RANK_LIMIT],
82        }
83    }
84
85    fn from_axes(axes: &[FusedAxis]) -> Self {
86        debug_assert!(axes.len() <= RAW_FUSED_RANK_LIMIT);
87        let mut layout = Self {
88            rank: axes.len(),
89            dims: [1; RAW_FUSED_RANK_LIMIT],
90            dst_strides: [0; RAW_FUSED_RANK_LIMIT],
91            src_strides: [0; RAW_FUSED_RANK_LIMIT],
92        };
93        for (slot, axis) in layout.dims[..axes.len()].iter_mut().zip(axes) {
94            *slot = axis.dim;
95        }
96        for (slot, axis) in layout.dst_strides[..axes.len()].iter_mut().zip(axes) {
97            *slot = axis.dst;
98        }
99        for (slot, axis) in layout.src_strides[..axes.len()].iter_mut().zip(axes) {
100            *slot = axis.src;
101        }
102        layout
103    }
104}
105
106/// A fused pair traversal of any rank.
107///
108/// Fused ranks at most [`RAW_FUSED_RANK_LIMIT`] use the inline layout; longer
109/// layouts keep their axes in one `Vec`. That storage is sized by the original
110/// rank (the fusion scratch is reused, and `truncate` keeps its capacity), never
111/// by the tensor's element count.
112#[derive(Clone, Debug)]
113pub(crate) enum PairTraversal {
114    Inline(FusedPairLayout),
115    Spilled(Vec<FusedAxis>),
116}
117
118impl Default for FusedPairLayout {
119    fn default() -> Self {
120        Self::empty()
121    }
122}
123
124impl Default for PairTraversal {
125    fn default() -> Self {
126        Self::empty()
127    }
128}
129
130impl PairTraversal {
131    /// The empty inline layout, used as a neutral default.
132    #[inline]
133    fn empty() -> Self {
134        Self::Inline(FusedPairLayout::empty())
135    }
136
137    /// Run `f` on the replay route of this traversal: its axes with the cache
138    /// tiles of destination element `D` and source element `S`, or no tiles
139    /// when the column-major walk is kept.
140    ///
141    /// The one decision entry point for both storage shapes, so a plan and a
142    /// replay entry ask the same question whatever the fused rank. A spilled
143    /// traversal decides in [`with_spilled_route`], whose stack frame holds the
144    /// wide tiles while `f` runs.
145    pub(crate) fn with_route<D, S, R>(&self, f: impl FnOnce(Route<'_>) -> R) -> R {
146        match self {
147            Self::Inline(layout) => {
148                let tiles = pair_tiles::<D, S>(layout);
149                f(Route::Inline {
150                    layout,
151                    tiles: tiles.as_ref(),
152                })
153            }
154            Self::Spilled(axes) => with_spilled_route::<D, S, R>(axes, f),
155        }
156    }
157
158    /// The cache tiles of this traversal, copied out of its route.
159    #[cfg(test)]
160    pub(crate) fn tiles<D, S>(&self) -> Option<Tiles> {
161        self.with_route::<D, S, _>(|route| route.snapshot())
162    }
163
164    /// Whether [`Self::with_route`] can tile for any element types: `false`
165    /// when the traversal covers at most one element or has fewer than two
166    /// axes of extent above 1, the exits [`pair_tiles`] and
167    /// [`with_spilled_route`] take before they look at an element size. Such
168    /// a traversal is one run, whose order no block vector can change.
169    pub(crate) fn may_tile(&self) -> bool {
170        let (total, moving) = match self {
171            Self::Inline(layout) => (
172                fused_total(layout),
173                layout.dims[..layout.rank]
174                    .iter()
175                    .filter(|&&dim| dim != 1)
176                    .count(),
177            ),
178            Self::Spilled(axes) => (
179                spilled_total(axes),
180                axes.iter().filter(|axis| axis.dim != 1).count(),
181            ),
182        };
183        total > 1 && moving >= 2
184    }
185
186    /// The inline layout, or `None` when the traversal spilled.
187    #[inline]
188    pub(crate) fn inline(&self) -> Option<&FusedPairLayout> {
189        match self {
190            Self::Inline(layout) => Some(layout),
191            Self::Spilled(_) => None,
192        }
193    }
194
195    /// Number of fused axes.
196    #[cfg(test)]
197    pub(crate) fn rank(&self) -> usize {
198        match self {
199            Self::Inline(layout) => layout.rank,
200            Self::Spilled(axes) => axes.len(),
201        }
202    }
203}
204
205/// Sort `dims`/`dst_strides`/`src_strides` by destination stride, drop size-1
206/// axes, and merge axes that are contiguous in both layouts.
207///
208/// Returns the fused rank written to `scratch[..rank]`. A zero extent collapses
209/// to a single zero-length axis, which every replay treats as an empty range.
210fn fuse_axes(
211    scratch: &mut [FusedAxis],
212    dims: &[usize],
213    dst_strides: &[isize],
214    src_strides: &[isize],
215) -> usize {
216    debug_assert!(scratch.len() >= dims.len());
217    let mut rank = 0usize;
218    for axis in 0..dims.len() {
219        if dims[axis] == 1 {
220            continue;
221        }
222        if dims[axis] == 0 {
223            scratch[0] = FusedAxis {
224                dim: 0,
225                dst: 0,
226                src: 0,
227            };
228            return 1;
229        }
230        let entry = FusedAxis {
231            dim: dims[axis],
232            dst: dst_strides[axis],
233            src: src_strides[axis],
234        };
235        let mut position = rank;
236        while position > 0 && scratch[position - 1].dst > entry.dst {
237            scratch[position] = scratch[position - 1];
238            position -= 1;
239        }
240        scratch[position] = entry;
241        rank += 1;
242    }
243    if rank == 0 {
244        scratch[0] = EMPTY_AXIS;
245        return 1;
246    }
247    let mut fused = 0usize;
248    for axis in 1..rank {
249        // A merged extent that overflows (possible for a stride-0 broadcast
250        // whose element count exceeds usize) leaves the axes unfused.
251        let merged = isize::try_from(scratch[fused].dim)
252            .ok()
253            .filter(|&extent| {
254                scratch[fused].dst.checked_mul(extent) == Some(scratch[axis].dst)
255                    && scratch[fused].src.checked_mul(extent) == Some(scratch[axis].src)
256            })
257            .and_then(|_| scratch[fused].dim.checked_mul(scratch[axis].dim));
258        if let Some(merged) = merged {
259            scratch[fused].dim = merged;
260        } else {
261            fused += 1;
262            scratch[fused] = scratch[axis];
263        }
264    }
265    fused + 1
266}
267
268/// Fuse a raw stride pair into a traversal of any rank.
269///
270/// Inline when the fused rank is at most [`RAW_FUSED_RANK_LIMIT`], otherwise one
271/// rank-bounded spill. An original rank above the limit uses a transient scratch
272/// buffer even when the fused layout still fits inline, so that fusion happens
273/// before the representation is chosen.
274pub(crate) fn fuse_pair_traversal(
275    dims: &[usize],
276    dst_strides: &[isize],
277    src_strides: &[isize],
278) -> PairTraversal {
279    if dims.len() <= RAW_FUSED_RANK_LIMIT {
280        let mut scratch = [EMPTY_AXIS; RAW_FUSED_RANK_LIMIT];
281        let rank = fuse_axes(&mut scratch, dims, dst_strides, src_strides);
282        debug_assert!(rank <= RAW_FUSED_RANK_LIMIT);
283        return PairTraversal::Inline(FusedPairLayout::from_axes(&scratch[..rank]));
284    }
285    let mut scratch = vec![EMPTY_AXIS; dims.len()];
286    let rank = fuse_axes(&mut scratch, dims, dst_strides, src_strides);
287    scratch.truncate(rank);
288    if rank <= RAW_FUSED_RANK_LIMIT {
289        PairTraversal::Inline(FusedPairLayout::from_axes(&scratch))
290    } else {
291        PairTraversal::Spilled(scratch)
292    }
293}
294
295impl PairTraversal {
296    /// The traversal [`with_given_route`] replays for the given axes, as an
297    /// owned value for the tests.
298    #[cfg(test)]
299    pub(crate) fn given(dims: &[usize], dst_strides: &[isize], src_strides: &[isize]) -> Self {
300        with_given_route::<(), (), _>(dims, dst_strides, src_strides, |route| match route {
301            Route::Inline { layout, .. } => Self::Inline(*layout),
302            Route::Spilled { axes, .. } => Self::Spilled(axes.to_vec()),
303        })
304    }
305}
306
307/// A replay route borrowed from the frame that decided it: the axes to walk
308/// and, when the walk is tiled, their cache tiles.
309///
310/// The wide storage lives in the out-of-line frames of [`with_spilled_route`]
311/// and [`with_given_route`], so the inline route's frame never holds it.
312#[derive(Clone, Copy, Debug)]
313pub(crate) enum Route<'a> {
314    Inline {
315        layout: &'a FusedPairLayout,
316        tiles: Option<&'a PairTiles>,
317    },
318    Spilled {
319        axes: &'a [FusedAxis],
320        tiles: Option<&'a SpilledTiles>,
321    },
322}
323
324impl<'a> Route<'a> {
325    /// Whether the route walks cache tiles.
326    pub(crate) fn is_tiled(&self) -> bool {
327        match self {
328            Self::Inline { tiles, .. } => tiles.is_some(),
329            Self::Spilled { tiles, .. } => tiles.is_some(),
330        }
331    }
332
333    /// The same axes walked column-major.
334    pub(crate) fn untiled(self) -> Self {
335        match self {
336            Self::Inline { layout, .. } => Self::Inline {
337                layout,
338                tiles: None,
339            },
340            Self::Spilled { axes, .. } => Self::Spilled { axes, tiles: None },
341        }
342    }
343
344    /// The block vector of the tiles over their compressed axes, or `None` for
345    /// the column-major walk.
346    #[cfg(feature = "bench-hooks")]
347    pub(crate) fn blocks(&self) -> Option<&'a [usize]> {
348        match *self {
349            Self::Inline { tiles, .. } => tiles.map(|tiles| &tiles.blocks[..tiles.layout.rank]),
350            Self::Spilled { tiles, .. } => tiles.map(SpilledTiles::blocks),
351        }
352    }
353
354    /// The tiles of the route, copied out.
355    #[cfg(test)]
356    pub(crate) fn snapshot(self) -> Option<Tiles> {
357        match self {
358            Self::Inline { tiles, .. } => tiles.copied().map(Tiles::Inline),
359            Self::Spilled { tiles, .. } => tiles.copied().map(Tiles::Spilled),
360        }
361    }
362}
363
364/// Run `f` on the replay route of the given axes, in their given order:
365/// nothing is sorted or merged. Rank zero becomes the one-element
366/// `EMPTY_AXIS` layout that [`fuse_axes`] also produces.
367///
368/// The three slices must have equal length, and the extents a checked,
369/// nonzero product (the replay totals multiply them unchecked). A rank above
370/// [`RAW_FUSED_RANK_LIMIT`] is compacted to its moving axes first, out of line
371/// ([`with_wide_given_route`]).
372pub(crate) fn with_given_route<D, S, R>(
373    dims: &[usize],
374    dst_strides: &[isize],
375    src_strides: &[isize],
376    f: impl FnOnce(Route<'_>) -> R,
377) -> R {
378    debug_assert!(dims.len() == dst_strides.len() && dims.len() == src_strides.len());
379    let rank = dims.len();
380    if rank > RAW_FUSED_RANK_LIMIT {
381        return with_wide_given_route::<D, S, R>(dims, dst_strides, src_strides, f);
382    }
383    let mut layout = FusedPairLayout::empty();
384    layout.rank = rank.max(1);
385    layout.dims[..rank].copy_from_slice(dims);
386    layout.dst_strides[..rank].copy_from_slice(dst_strides);
387    layout.src_strides[..rank].copy_from_slice(src_strides);
388    let tiles = pair_tiles::<D, S>(&layout);
389    f(Route::Inline {
390        layout: &layout,
391        tiles: tiles.as_ref(),
392    })
393}
394
395/// [`with_given_route`] above [`RAW_FUSED_RANK_LIMIT`] given axes: the moving
396/// axes, in their given order, in a stack array. At most
397/// [`RAW_FUSED_RANK_LIMIT`] of them replay through the inline layout, more
398/// through [`with_spilled_route`].
399///
400/// The tile decision is the one the given axes would get: the model already
401/// drops extent-1 axes before it decides.
402#[inline(never)]
403fn with_wide_given_route<D, S, R>(
404    dims: &[usize],
405    dst_strides: &[isize],
406    src_strides: &[isize],
407    f: impl FnOnce(Route<'_>) -> R,
408) -> R {
409    let mut axes = [EMPTY_AXIS; MAX_MOVING_AXES];
410    let mut moving = 0;
411    for ((&dim, &dst), &src) in dims.iter().zip(dst_strides).zip(src_strides) {
412        if dim == 1 {
413            continue;
414        }
415        // INVARIANT: the caller's checked nonzero count gives
416        // `2^moving <= total <= usize::MAX`, so `moving < MAX_MOVING_AXES`.
417        axes[moving] = FusedAxis { dim, dst, src };
418        moving += 1;
419    }
420    if moving <= RAW_FUSED_RANK_LIMIT {
421        let layout = FusedPairLayout::from_axes(if moving == 0 {
422            &[EMPTY_AXIS]
423        } else {
424            &axes[..moving]
425        });
426        let tiles = pair_tiles::<D, S>(&layout);
427        return f(Route::Inline {
428            layout: &layout,
429            tiles: tiles.as_ref(),
430        });
431    }
432    with_spilled_route::<D, S, R>(&axes[..moving], f)
433}
434
435/// Run `f` on the replay route of a spilled axis list: more than
436/// [`RAW_FUSED_RANK_LIMIT`] axes, every extent at least 2, and a checked
437/// product (fused or compacted axes).
438///
439/// The exits the model decides before its metadata are answered from the axes
440/// first ([#425]), so a layout they answer never sets up the tiles' storage.
441///
442/// [#425]: https://github.com/tensor4all/strided-rs/issues/425
443#[inline(never)]
444fn with_spilled_route<D, S, R>(axes: &[FusedAxis], f: impl FnOnce(Route<'_>) -> R) -> R {
445    debug_assert!(axes.len() > RAW_FUSED_RANK_LIMIT && axes.iter().all(|axis| axis.dim >= 2));
446    if crate::block::exits_before_metadata(
447        axes.iter().map(|axis| (axis.dim, axis.dst, axis.src)),
448        core::mem::size_of::<D>(),
449        core::mem::size_of::<S>(),
450    ) {
451        return f(Route::Spilled { axes, tiles: None });
452    }
453    with_modelled_spilled_route::<D, S, R>(axes, f)
454}
455
456/// [`with_spilled_route`] past the model's early exits: the tiles live in this
457/// frame while `f` runs, so neither the inline route nor an early exit carries
458/// their storage.
459#[inline(never)]
460fn with_modelled_spilled_route<D, S, R>(axes: &[FusedAxis], f: impl FnOnce(Route<'_>) -> R) -> R {
461    let mut tiles = SpilledTiles::EMPTY;
462    let tiled = spilled_tiles::<D, S>(axes, &mut tiles);
463    f(Route::Spilled {
464        axes,
465        tiles: tiled.then_some(&tiles),
466    })
467}
468
469/// Fuse a raw stride pair into the inline representation.
470///
471/// Returns `None` when the fused rank exceeds [`RAW_FUSED_RANK_LIMIT`]. Used by
472/// the window plans, whose non-fused replay is compiled alongside the plan.
473pub(crate) fn fuse_pair_layout(
474    dims: &[usize],
475    dst_strides: &[isize],
476    src_strides: &[isize],
477) -> Option<FusedPairLayout> {
478    match fuse_pair_traversal(dims, dst_strides, src_strides) {
479        PairTraversal::Inline(layout) => Some(layout),
480        PairTraversal::Spilled(_) => None,
481    }
482}
483
484/// Number of logical elements covered by a fused layout.
485///
486/// Every constructor of a [`FusedPairLayout`] starts from dims whose product
487/// was checked by [`crate::kernel::total_len`], and fusion only merges axes
488/// with a checked product, so the product cannot overflow.
489#[inline]
490pub(crate) fn fused_total(layout: &FusedPairLayout) -> usize {
491    layout.dims[..layout.rank].iter().product()
492}
493
494/// Number of logical elements covered by a spilled axis list.
495#[inline]
496fn spilled_total(axes: &[FusedAxis]) -> usize {
497    axes.iter().map(|axis| axis.dim).product()
498}
499
500/// The tiles of a route, copied out for the tests.
501#[cfg(test)]
502#[derive(Clone, Debug)]
503#[allow(clippy::large_enum_variant)] // a test snapshot; production borrows `Route`
504pub(crate) enum Tiles {
505    Inline(PairTiles),
506    Spilled(SpilledTiles),
507}
508
509#[cfg(test)]
510impl Tiles {
511    /// The tiles of the inline walk, or `None` for a spilled one.
512    pub(crate) fn inline(&self) -> Option<&PairTiles> {
513        match self {
514            Self::Inline(tiles) => Some(tiles),
515            Self::Spilled(_) => None,
516        }
517    }
518}
519
520/// The cache tiles of a spilled axis list whose rank exceeds
521/// [`RAW_FUSED_RANK_LIMIT`].
522///
523/// `dims`/`dst`/`src` are the axes of the list, every extent at least 2, and
524/// address exactly its slots in the same column-major order. They are stored
525/// in arrays of [`MAX_MOVING_AXES`] and read as `rank`-long slices, because the
526/// tile walk and the dimension splitter both take slices.
527#[derive(Clone, Copy, Debug)]
528pub(crate) struct SpilledTiles {
529    rank: usize,
530    dims: [usize; MAX_MOVING_AXES],
531    dst: [isize; MAX_MOVING_AXES],
532    src: [isize; MAX_MOVING_AXES],
533    blocks: [usize; MAX_MOVING_AXES],
534}
535
536impl SpilledTiles {
537    const EMPTY: Self = Self {
538        rank: 0,
539        dims: [1; MAX_MOVING_AXES],
540        dst: [0; MAX_MOVING_AXES],
541        src: [0; MAX_MOVING_AXES],
542        blocks: [1; MAX_MOVING_AXES],
543    };
544
545    pub(crate) fn dims(&self) -> &[usize] {
546        &self.dims[..self.rank]
547    }
548
549    pub(crate) fn dst(&self) -> &[isize] {
550        &self.dst[..self.rank]
551    }
552
553    pub(crate) fn src(&self) -> &[isize] {
554        &self.src[..self.rank]
555    }
556
557    pub(crate) fn blocks(&self) -> &[usize] {
558        &self.blocks[..self.rank]
559    }
560}
561
562/// The cache tiles of a fused pair layout whose tiled walk visits the slots in
563/// a different order from the column-major walk.
564///
565/// Built by [`pair_tiles`]; `layout` addresses exactly the slots of the layout
566/// it was built from, in the same column-major order, without its extent-1
567/// axes.
568#[derive(Clone, Copy, Debug)]
569pub(crate) struct PairTiles {
570    pub(crate) layout: FusedPairLayout,
571    pub(crate) blocks: [usize; RAW_FUSED_RANK_LIMIT],
572}
573
574/// Cache tiles for replaying `layout` with destination element `D` and source
575/// element `S`, or `None` when the column-major walk is kept.
576///
577/// The extent-1 axes are dropped first: they address offset 0 whatever their
578/// stride, so the compressed layout addresses the same slots in the same
579/// order, and an unvalidated stride on such an axis never reaches the block
580/// arithmetic. Fewer than two remaining axes form one run, whose order no
581/// block vector can change. The blocks come from the shared model
582/// (`block::compute_block_sizes`), which sizes each operand by its own element
583/// size exactly as the view path does. Tiles are returned only when they
584/// change the visit order (the first axis whose block is smaller than its
585/// extent is followed by an axis with a block above 1) and when that change can
586/// reuse a cache line (see [`crate::block::declines_tiles`]).
587///
588/// The extents of `layout` must have a product that fits `usize` (every
589/// constructor of a [`FusedPairLayout`] checks it).
590pub(crate) fn pair_tiles<D, S>(layout: &FusedPairLayout) -> Option<PairTiles> {
591    if fused_total(layout) <= 1 {
592        return None;
593    }
594    let moving = layout.dims[..layout.rank]
595        .iter()
596        .filter(|&&dim| dim != 1)
597        .count();
598    if moving < 2 {
599        return None;
600    }
601    let compressed;
602    let layout = if moving == layout.rank {
603        layout
604    } else {
605        compressed = without_unit_axes(layout);
606        &compressed
607    };
608    let rank = layout.rank;
609    let mut blocks = [1; RAW_FUSED_RANK_LIMIT];
610    tile_blocks::<D, S, { 2 * RAW_FUSED_RANK_LIMIT }, RAW_FUSED_RANK_LIMIT>(
611        &layout.dims[..rank],
612        &layout.dst_strides[..rank],
613        &layout.src_strides[..rank],
614        &mut blocks[..rank],
615    )
616    .then_some(PairTiles {
617        layout: *layout,
618        blocks,
619    })
620}
621
622/// The block vector of the shared cache-block model for already-compressed
623/// axes (`dims`/`dst`/`src` of one length, every extent at least 2), written
624/// to `blocks`; `false` when the column-major walk is kept.
625///
626/// The model's scratch holds `ORDERS` stride-order slots (two per axis) and
627/// `AXES` cost slots, at least what `dims` needs. It is set up only past the
628/// model's exits, so a layout they answer does not pay for it.
629///
630/// The single source of the tiling decision for both storage shapes: the
631/// inline [`FusedPairLayout`] and the spilled [`SpilledTiles`].
632fn tile_blocks<D, S, const ORDERS: usize, const AXES: usize>(
633    dims: &[usize],
634    dst: &[isize],
635    src: &[isize],
636    blocks: &mut [usize],
637) -> bool {
638    let strides = [dst, src];
639    let elem_sizes = [core::mem::size_of::<D>(), core::mem::size_of::<S>()];
640    // `false`: one of the model's exits keeps the full dimensions, which
641    // cannot change the visit order.
642    if crate::block::model_exits(dims, &strides, &elem_sizes) {
643        return false;
644    }
645    let rank = dims.len();
646    // INVARIANT: both callers pass capacities of at least their rank.
647    let mut orders = [0usize; ORDERS];
648    let mut costs = [0isize; AXES];
649    crate::block::reduced_block_sizes_into(
650        dims,
651        &strides,
652        &elem_sizes,
653        blocks,
654        &mut orders[..2 * rank],
655        &mut costs[..rank],
656    );
657    let Some(first_cut) = (0..dims.len()).find(|&axis| blocks[axis] < dims[axis]) else {
658        return false;
659    };
660    if blocks[first_cut + 1..].iter().all(|&block| block == 1) {
661        return false;
662    }
663    // The axes before `first_cut` are walked whole inside every tile, so each
664    // operand is judged with its own element size, as the model now does.
665    if crate::block::declines_tiles(dims, &strides, &elem_sizes, blocks) {
666        return false;
667    }
668    // Operand 0 is the destination, as on the view path (#287).
669    crate::block::fit_l1_sets(dims, &strides, &elem_sizes, 0, blocks);
670    true
671}
672
673/// Cache tiles for replaying a spilled axis list (more than
674/// [`RAW_FUSED_RANK_LIMIT`] axes, every extent at least 2, a checked product)
675/// that [`crate::block::exits_before_metadata`] does not answer, written to
676/// `tiles`; `false` when the column-major walk is kept.
677///
678/// The invariant: an axis list is tiled exactly when the same layout given
679/// inline would be.
680fn spilled_tiles<D, S>(axes: &[FusedAxis], tiles: &mut SpilledTiles) -> bool {
681    let rank = axes.len();
682    // INVARIANT: every axis has an extent of at least 2 and the product is a
683    // checked nonzero count, so `2^rank <= usize::MAX` and
684    // `rank < MAX_MOVING_AXES`.
685    tiles.rank = rank;
686    for (axis, entry) in axes.iter().enumerate() {
687        tiles.dims[axis] = entry.dim;
688        tiles.dst[axis] = entry.dst;
689        tiles.src[axis] = entry.src;
690    }
691    tile_blocks::<D, S, { 2 * MAX_MOVING_AXES }, MAX_MOVING_AXES>(
692        &tiles.dims[..rank],
693        &tiles.dst[..rank],
694        &tiles.src[..rank],
695        &mut tiles.blocks[..rank],
696    )
697}
698
699/// `layout` without its extent-1 axes, in the given order.
700fn without_unit_axes(layout: &FusedPairLayout) -> FusedPairLayout {
701    let mut compressed = FusedPairLayout::empty();
702    let mut rank = 0;
703    for axis in 0..layout.rank {
704        if layout.dims[axis] == 1 {
705            continue;
706        }
707        compressed.dims[rank] = layout.dims[axis];
708        compressed.dst_strides[rank] = layout.dst_strides[axis];
709        compressed.src_strides[rank] = layout.src_strides[axis];
710        rank += 1;
711    }
712    compressed.rank = rank;
713    compressed
714}
715
716/// Replay every logical index of `tile_box` tile by tile: the tiles of extents
717/// `blocks`, anchored at the box origin and clipped to the box, are visited in
718/// column-major order of the tile grid, and each tile is walked in
719/// column-major order by [`apply_fused_range`].
720///
721/// Kept out of line so that the untiled replay keeps its code shape.
722///
723/// # Safety
724///
725/// The [`apply_fused_range`] contract for the whole of `tile_box`, and every
726/// `blocks[axis]` for `axis < tile_box.rank` is at least 1.
727#[inline(never)]
728pub(crate) unsafe fn apply_tiled_box<D, S, Apply>(
729    dst_ptr: *mut D,
730    dst_base: isize,
731    src_ptr: *const S,
732    src_base: isize,
733    tile_box: &FusedPairLayout,
734    blocks: &[usize; RAW_FUSED_RANK_LIMIT],
735    apply: &mut Apply,
736) where
737    D: Copy,
738    S: Copy,
739    Apply: FnMut(&mut D, S),
740{
741    let tiles = tile_count(tile_box, blocks);
742    // SAFETY: forwarded caller contract; `0..tiles` is the whole tile grid.
743    unsafe {
744        apply_tile_range(
745            dst_ptr, dst_base, src_ptr, src_base, tile_box, blocks, 0, tiles, apply,
746        );
747    }
748}
749
750/// Number of tiles of extents `blocks` that cover `tile_box`; at most its
751/// element count, so it cannot overflow.
752pub(crate) fn tile_count(
753    tile_box: &FusedPairLayout,
754    blocks: &[usize; RAW_FUSED_RANK_LIMIT],
755) -> usize {
756    tile_box.dims[..tile_box.rank]
757        .iter()
758        .zip(blocks)
759        .map(|(&dim, &block)| dim.div_ceil(block))
760        .product()
761}
762
763/// Replay the tiles `first..first + count` of `tile_box`, numbered in
764/// column-major order of the tile grid [`apply_tiled_box`] walks, each in
765/// column-major order by [`apply_fused_range`].
766///
767/// Disjoint tile ranges address disjoint logical indices, and the ranges
768/// `0..k`, `k..tile_count` together walk exactly what [`apply_tiled_box`]
769/// walks, in the same order.
770///
771/// # Safety
772///
773/// The [`apply_fused_range`] contract for the whole of `tile_box`, every
774/// `blocks[axis]` for `axis < tile_box.rank` at least 1, and
775/// `first + count` at most [`tile_count`] of `tile_box` and `blocks`.
776#[allow(clippy::too_many_arguments)]
777#[inline(never)]
778pub(crate) unsafe fn apply_tile_range<D, S, Apply>(
779    dst_ptr: *mut D,
780    dst_base: isize,
781    src_ptr: *const S,
782    src_base: isize,
783    tile_box: &FusedPairLayout,
784    blocks: &[usize; RAW_FUSED_RANK_LIMIT],
785    first: usize,
786    count: usize,
787    apply: &mut Apply,
788) where
789    D: Copy,
790    S: Copy,
791    Apply: FnMut(&mut D, S),
792{
793    if count == 0 {
794        return;
795    }
796    let rank = tile_box.rank;
797    let mut tile = *tile_box;
798    // `origin[axis]` is the first box coordinate of the current tile along
799    // `axis`; `dst_tile`/`src_tile` are the offsets of the tile origin.
800    let mut origin = [0usize; RAW_FUSED_RANK_LIMIT];
801    let mut dst_tile = dst_base;
802    let mut src_tile = src_base;
803    // Decode `first` into its tile-grid coordinates, axis 0 fastest.
804    let mut rest = first;
805    for axis in 0..rank {
806        let along = tile_box.dims[axis].div_ceil(blocks[axis]);
807        origin[axis] = (rest % along) * blocks[axis];
808        rest /= along;
809        dst_tile += origin[axis] as isize * tile_box.dst_strides[axis];
810        src_tile += origin[axis] as isize * tile_box.src_strides[axis];
811        tile.dims[axis] = blocks[axis].min(tile_box.dims[axis] - origin[axis]);
812    }
813    let mut left = count;
814    loop {
815        // Counted here, where the tile is walked, so that a test sees the
816        // walk itself and not the range a caller asked for.
817        #[cfg(test)]
818        crate::threading::record_tile_box();
819        // SAFETY: the tile is a sub-box of `tile_box` at a reachable origin, so
820        // the caller's contract covers every logical index of the tile.
821        unsafe {
822            apply_fused_range(
823                dst_ptr,
824                dst_tile,
825                src_ptr,
826                src_tile,
827                &tile,
828                0,
829                fused_total(&tile),
830                apply,
831            );
832        }
833        left -= 1;
834        if left == 0 {
835            return;
836        }
837        // Column-major odometer over the tile grid. An axis advances only
838        // when another tile follows along it, so `blocks[axis]` is at most
839        // its last box coordinate, and it rewinds by its current origin:
840        // every intermediate offset is a reachable offset of the box. The
841        // caller's bound on `first + count` keeps the walk inside the grid.
842        let mut axis = 0;
843        loop {
844            debug_assert!(axis < rank, "tile range past the end of the grid");
845            let next = origin[axis] + blocks[axis];
846            if next < tile_box.dims[axis] {
847                origin[axis] = next;
848                dst_tile += blocks[axis] as isize * tile_box.dst_strides[axis];
849                src_tile += blocks[axis] as isize * tile_box.src_strides[axis];
850                tile.dims[axis] = blocks[axis].min(tile_box.dims[axis] - next);
851                break;
852            }
853            dst_tile -= origin[axis] as isize * tile_box.dst_strides[axis];
854            src_tile -= origin[axis] as isize * tile_box.src_strides[axis];
855            origin[axis] = 0;
856            tile.dims[axis] = blocks[axis].min(tile_box.dims[axis]);
857            axis += 1;
858        }
859    }
860}
861
862/// Replay every logical index of `box_dims`, a sub-box of `tiles`, tile by
863/// tile: the tiles of extents `tiles.blocks`, anchored at the box origin and
864/// clipped to it, are visited in column-major order of the tile grid, and each
865/// tile is walked in column-major order by [`apply_spilled_range`].
866///
867/// The spilled counterpart of [`apply_tiled_box`]: same tile odometer, same
868/// per-element walk as the untiled replay, only the axis storage differs. Kept
869/// out of line so that the untiled spilled replay keeps its code shape. The
870/// tile, its cursor and its origin are stack arrays of [`MAX_MOVING_AXES`].
871///
872/// # Safety
873///
874/// The [`apply_spilled_range`] contract for the whole of `box_dims`, which
875/// must be `tiles.dims` or a sub-box of it anchored at `dst_base`/`src_base`,
876/// and every `tiles.blocks[axis]` at least 1.
877#[allow(clippy::too_many_arguments)]
878#[inline(never)]
879pub(crate) unsafe fn apply_spilled_tiled_box<D, S, Apply>(
880    dst_ptr: *mut D,
881    dst_base: isize,
882    src_ptr: *const S,
883    src_base: isize,
884    tiles: &SpilledTiles,
885    box_dims: &[usize],
886    apply: &mut Apply,
887) where
888    D: Copy,
889    S: Copy,
890    Apply: FnMut(&mut D, S),
891{
892    let rank = box_dims.len();
893    // One axis list for the current tile and one cursor for the whole walk,
894    // however many tiles it visits.
895    // INVARIANT: `box_dims` is `tiles.dims` or a sub-box of it, so
896    // `rank == tiles.rank < MAX_MOVING_AXES`.
897    let mut tile_axes = [EMPTY_AXIS; MAX_MOVING_AXES];
898    let tile = &mut tile_axes[..rank];
899    for (axis, slot) in tile.iter_mut().enumerate() {
900        slot.dst = tiles.dst[axis];
901        slot.src = tiles.src[axis];
902    }
903    let mut cursor = [0usize; MAX_MOVING_AXES];
904    let index = &mut cursor[..rank];
905    let mut origins = [0usize; MAX_MOVING_AXES];
906    let origin = &mut origins[..rank];
907    let mut dst_tile = dst_base;
908    let mut src_tile = src_base;
909    loop {
910        #[cfg(test)]
911        crate::threading::record_tile_box();
912        let mut count = 1usize;
913        for axis in 0..rank {
914            let dim = tiles.blocks[axis].min(box_dims[axis] - origin[axis]);
915            tile[axis].dim = dim;
916            count *= dim;
917        }
918        // SAFETY: the tile is a sub-box of `box_dims` at a reachable origin, so
919        // the caller's contract covers every logical index of the tile.
920        unsafe {
921            apply_spilled_range_with(
922                dst_ptr, dst_tile, src_ptr, src_tile, tile, 0, count, index, apply,
923            );
924        }
925        // The column-major odometer of [`apply_tiled_box`], over slices.
926        let mut axis = 0;
927        loop {
928            if axis == rank {
929                return;
930            }
931            let next = origin[axis] + tiles.blocks[axis];
932            if next < box_dims[axis] {
933                origin[axis] = next;
934                dst_tile += tiles.blocks[axis] as isize * tiles.dst[axis];
935                src_tile += tiles.blocks[axis] as isize * tiles.src[axis];
936                break;
937            }
938            dst_tile -= origin[axis] as isize * tiles.dst[axis];
939            src_tile -= origin[axis] as isize * tiles.src[axis];
940            origin[axis] = 0;
941            axis += 1;
942        }
943    }
944}
945
946/// Serial replay of a fused pair layout over borrowed raw views.
947///
948/// The destination layout need not be injective: runs are replayed in order,
949/// so accumulating callers such as [`axpy_raw`] keep their sequential
950/// semantics. Parallel replay goes through `copy_plan::replay_fused`, which
951/// the plans and the `replay_*_raw` entries call only with a destination
952/// proven injective or a serial token.
953pub(crate) fn apply_fused_pair<D, S, Apply>(
954    dst: &mut RawStridedMut<'_, D>,
955    src: &RawStridedRef<'_, S>,
956    layout: &FusedPairLayout,
957    mut apply: Apply,
958) where
959    D: Copy,
960    S: Copy,
961    Apply: FnMut(&mut D, S),
962{
963    let total = fused_total(layout);
964    if total == 0 {
965        return;
966    }
967    let src_ptr = src.data().as_ptr();
968    let src_base = src.offset();
969    let dst_base = dst.offset();
970    let dst_ptr = dst.data_mut().as_mut_ptr();
971    // SAFETY: `RawStridedRef`/`RawStridedMut` guarantee (by `new`, or by the
972    // caller of `new_unchecked`) that every offset reachable from their offset
973    // through their dims/strides lies inside their data. Callers pass a layout
974    // fused from exactly those dims/strides, so every logical index in
975    // `0..total` maps to in-bounds source and destination slots. The shared
976    // and exclusive borrows cannot overlap, and this is the only writer.
977    unsafe {
978        apply_fused_range(
979            dst_ptr, dst_base, src_ptr, src_base, layout, 0, total, &mut apply,
980        );
981    }
982}
983
984/// Serial replay of a spilled fused axis list over borrowed raw views.
985///
986/// Kept out of line and separate from [`apply_fused_pair`] so that the inline
987/// entry points keep the code shape they had before high-rank fusion existed:
988/// fused ranks above [`RAW_FUSED_RANK_LIMIT`] are the rare case, and inlining
989/// this second carry loop into them measurably slowed the inline path (extra
990/// register pressure in a loop that runs once per short run).
991#[inline(never)]
992pub(crate) fn apply_spilled_pair<D, S, Apply>(
993    dst: &mut RawStridedMut<'_, D>,
994    src: &RawStridedRef<'_, S>,
995    axes: &[FusedAxis],
996    mut apply: Apply,
997) where
998    D: Copy,
999    S: Copy,
1000    Apply: FnMut(&mut D, S),
1001{
1002    let total = spilled_total(axes);
1003    if total == 0 {
1004        return;
1005    }
1006    let src_ptr = src.data().as_ptr();
1007    let src_base = src.offset();
1008    let dst_base = dst.offset();
1009    let dst_ptr = dst.data_mut().as_mut_ptr();
1010    // SAFETY: same contract as `apply_fused_pair`, for the axis list fused from
1011    // the same dims/strides.
1012    unsafe {
1013        apply_spilled_range(
1014            dst_ptr, dst_base, src_ptr, src_base, axes, 0, total, &mut apply,
1015        );
1016    }
1017}
1018
1019/// Serial replay of a route on the calling thread: the four whole-box walks of
1020/// the parallel replay's serial branches, one sequential pass through `apply`.
1021///
1022/// [`crate::copy_plan::replay_fused`] sends a serial token here, and so does
1023/// [`replay_map_raw_serial`] with its `FnMut`, so both walk the same leaves in
1024/// the same order. No arm needs `Send` or `Sync`: nothing crosses a thread.
1025///
1026/// # Safety
1027///
1028/// The [`crate::copy_plan::replay_fused`] contract for `route` at these bases,
1029/// with a serial token: every logical index maps to in-bounds slots of both
1030/// allocations, the product of the extents does not overflow, the tiles (when
1031/// present) are the route builder's own and the destination is injective over
1032/// a tiled route, and the destination does not overlap the source.
1033pub(crate) unsafe fn replay_route_serial<D, S, Apply>(
1034    dst_ptr: *mut D,
1035    dst_base: isize,
1036    src_ptr: *const S,
1037    src_base: isize,
1038    route: Route<'_>,
1039    apply: &mut Apply,
1040) where
1041    D: Copy,
1042    S: Copy,
1043    Apply: FnMut(&mut D, S),
1044{
1045    // SAFETY: forwarded caller contract. Inline tiles address exactly the
1046    // slots of their layout; spilled tiles hold their own axes. One
1047    // sequential walk updates a repeated slot once per logical index, in
1048    // order, so an untiled route needs no injectivity.
1049    unsafe {
1050        match route {
1051            Route::Inline {
1052                layout,
1053                tiles: None,
1054            } => apply_fused_range(
1055                dst_ptr,
1056                dst_base,
1057                src_ptr,
1058                src_base,
1059                layout,
1060                0,
1061                fused_total(layout),
1062                apply,
1063            ),
1064            Route::Inline {
1065                tiles: Some(tiles), ..
1066            } => apply_tiled_box(
1067                dst_ptr,
1068                dst_base,
1069                src_ptr,
1070                src_base,
1071                &tiles.layout,
1072                &tiles.blocks,
1073                apply,
1074            ),
1075            Route::Spilled { axes, tiles: None } => apply_spilled_range(
1076                dst_ptr,
1077                dst_base,
1078                src_ptr,
1079                src_base,
1080                axes,
1081                0,
1082                spilled_total(axes),
1083                apply,
1084            ),
1085            Route::Spilled {
1086                tiles: Some(tiles), ..
1087            } => apply_spilled_tiled_box(
1088                dst_ptr,
1089                dst_base,
1090                src_ptr,
1091                src_base,
1092                tiles,
1093                tiles.dims(),
1094                apply,
1095            ),
1096        }
1097    }
1098}
1099
1100/// Replay logical indices `start..start + len` of a fused pair layout, in
1101/// column-major order of the fused axes (axis 0 fastest).
1102///
1103/// The start coordinate is decoded once; runs along axis 0 then advance the
1104/// outer coordinates incrementally, so no per-element range checks or
1105/// coordinate rebuilds remain in the hot loop.
1106///
1107/// # Safety
1108///
1109/// - `start + len` must not exceed [`fused_total`] of `layout`.
1110/// - For every logical index `i` in the range, `dst_base` plus the fused
1111///   destination offset of `i` must be an in-bounds, writable slot of the
1112///   allocation behind `dst_ptr`, and likewise `src_base` plus the source
1113///   offset must be an in-bounds, readable slot behind `src_ptr`.
1114/// - No other thread may access the destination slots of this range while it
1115///   runs, and the source slots must not be written concurrently. Destination
1116///   and source slots must not overlap.
1117// Range leaf: both bases, the layout, the range and the closure, called once per worker
1118// range.
1119#[allow(clippy::too_many_arguments)]
1120pub(crate) unsafe fn apply_fused_range<D, S, Apply>(
1121    dst_ptr: *mut D,
1122    dst_base: isize,
1123    src_ptr: *const S,
1124    src_base: isize,
1125    layout: &FusedPairLayout,
1126    start: usize,
1127    len: usize,
1128    apply: &mut Apply,
1129) where
1130    D: Copy,
1131    S: Copy,
1132    Apply: FnMut(&mut D, S),
1133{
1134    if len == 0 {
1135        return;
1136    }
1137    let rank = layout.rank;
1138    let inner_len = layout.dims[0];
1139    let inner_dst = layout.dst_strides[0];
1140    let inner_src = layout.src_strides[0];
1141
1142    // Decode the start coordinate once per range. `dst_offset`/`src_offset`
1143    // track the offset of the current run start (outer coordinates plus the
1144    // inner coordinate `inner_start`); every value is a reachable offset.
1145    let mut index = [0usize; RAW_FUSED_RANK_LIMIT];
1146    let mut rest = start;
1147    let mut dst_outer = dst_base;
1148    let mut src_outer = src_base;
1149    // The axis indexes `index`, `layout.dims` and both stride tables at once.
1150    #[allow(clippy::needless_range_loop)]
1151    for axis in 0..rank {
1152        let dim = layout.dims[axis];
1153        index[axis] = rest % dim;
1154        rest /= dim;
1155        if axis > 0 {
1156            dst_outer += index[axis] as isize * layout.dst_strides[axis];
1157            src_outer += index[axis] as isize * layout.src_strides[axis];
1158        }
1159    }
1160    let mut inner_start = index[0];
1161    let mut remaining = len;
1162    loop {
1163        let run = (inner_len - inner_start).min(remaining);
1164        let dst_run = dst_outer + inner_start as isize * inner_dst;
1165        let src_run = src_outer + inner_start as isize * inner_src;
1166        // SAFETY: the run covers logical indices inside the caller's range, so
1167        // by this function's contract every slot touched below is in-bounds,
1168        // exclusively owned by this call (destination) and unaliased.
1169        unsafe {
1170            apply_run(
1171                dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
1172            )
1173        };
1174        remaining -= run;
1175        if remaining == 0 {
1176            return;
1177        }
1178        inner_start = 0;
1179        // Advance an axis only when another position along it follows, and
1180        // rewind it from its last position, so every intermediate base is a
1181        // reachable offset of a validated layout (issue #243 follow-up): a
1182        // layout ending within one stride of `isize::MAX` must not overflow.
1183        // `remaining > 0` guarantees a following run exists, so the loop
1184        // always finds an axis to advance before running out of rank.
1185        let mut axis = 1;
1186        while axis < rank {
1187            if index[axis] + 1 < layout.dims[axis] {
1188                index[axis] += 1;
1189                dst_outer += layout.dst_strides[axis];
1190                src_outer += layout.src_strides[axis];
1191                break;
1192            }
1193            let last = (layout.dims[axis] - 1) as isize;
1194            dst_outer -= last * layout.dst_strides[axis];
1195            src_outer -= last * layout.src_strides[axis];
1196            index[axis] = 0;
1197            axis += 1;
1198        }
1199    }
1200}
1201
1202/// Replay logical indices `start..start + len` of a spilled fused axis list, in
1203/// column-major order of the axes (axis 0 fastest).
1204///
1205/// The carry loop is the one [`apply_fused_range`] uses, over interleaved axes
1206/// with its carry state in a stack array of [`MAX_MOVING_AXES`]: nothing is
1207/// allocated and no per-element coordinate decode happens.
1208///
1209/// # Safety
1210///
1211/// The [`apply_fused_range`] contract holds for `axes`, which hold at most
1212/// [`MAX_MOVING_AXES`] entries (every caller passes fused or compacted axes of
1213/// a checked count; a longer list panics before any access).
1214///
1215/// Kept out of line: inlining this second carry loop into the inline replay
1216/// measurably slows that one down.
1217// Same shape as `apply_fused_range` for the spilled layout, per worker range.
1218#[allow(clippy::too_many_arguments)]
1219#[inline(never)]
1220pub(crate) unsafe fn apply_spilled_range<D, S, Apply>(
1221    dst_ptr: *mut D,
1222    dst_base: isize,
1223    src_ptr: *const S,
1224    src_base: isize,
1225    axes: &[FusedAxis],
1226    start: usize,
1227    len: usize,
1228    apply: &mut Apply,
1229) where
1230    D: Copy,
1231    S: Copy,
1232    Apply: FnMut(&mut D, S),
1233{
1234    if len == 0 {
1235        return;
1236    }
1237    let mut cursor = [0usize; MAX_MOVING_AXES];
1238    // INVARIANT: fused and compacted axes have extents of at least 2 and a
1239    // checked product, so `axes.len() < MAX_MOVING_AXES`.
1240    let index = &mut cursor[..axes.len()];
1241    // SAFETY: forwarded caller contract; `index` is the rank-sized cursor.
1242    unsafe {
1243        apply_spilled_range_with(
1244            dst_ptr, dst_base, src_ptr, src_base, axes, start, len, index, apply,
1245        )
1246    }
1247}
1248
1249/// [`apply_spilled_range`] with the caller's rank-sized coordinate buffer, so
1250/// that the tile walk keeps one cursor for all its tiles.
1251///
1252/// # Safety
1253///
1254/// The [`apply_spilled_range`] contract, and `index.len()` at least
1255/// `axes.len()`.
1256#[allow(clippy::too_many_arguments)]
1257unsafe fn apply_spilled_range_with<D, S, Apply>(
1258    dst_ptr: *mut D,
1259    dst_base: isize,
1260    src_ptr: *const S,
1261    src_base: isize,
1262    axes: &[FusedAxis],
1263    start: usize,
1264    len: usize,
1265    index: &mut [usize],
1266    apply: &mut Apply,
1267) where
1268    D: Copy,
1269    S: Copy,
1270    Apply: FnMut(&mut D, S),
1271{
1272    if len == 0 {
1273        return;
1274    }
1275    let rank = axes.len();
1276    debug_assert!(index.len() >= rank);
1277    let inner_len = axes[0].dim;
1278    let inner_dst = axes[0].dst;
1279    let inner_src = axes[0].src;
1280
1281    let mut rest = start;
1282    let mut dst_outer = dst_base;
1283    let mut src_outer = src_base;
1284    for axis in 0..rank {
1285        let dim = axes[axis].dim;
1286        index[axis] = rest % dim;
1287        rest /= dim;
1288        if axis > 0 {
1289            dst_outer += index[axis] as isize * axes[axis].dst;
1290            src_outer += index[axis] as isize * axes[axis].src;
1291        }
1292    }
1293    let mut inner_start = index[0];
1294    let mut remaining = len;
1295    loop {
1296        let run = (inner_len - inner_start).min(remaining);
1297        let dst_run = dst_outer + inner_start as isize * inner_dst;
1298        let src_run = src_outer + inner_start as isize * inner_src;
1299        // SAFETY: the run covers logical indices inside the caller's range, so
1300        // by the caller's contract every slot touched below is in-bounds,
1301        // exclusively owned by this call (destination) and unaliased.
1302        unsafe {
1303            apply_run(
1304                dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
1305            )
1306        };
1307        remaining -= run;
1308        if remaining == 0 {
1309            return;
1310        }
1311        inner_start = 0;
1312        // Same incremental carry as the inline replay: offsets only ever hold
1313        // reachable positions, and `remaining > 0` guarantees an axis advances.
1314        let mut axis = 1;
1315        while axis < rank {
1316            if index[axis] + 1 < axes[axis].dim {
1317                index[axis] += 1;
1318                dst_outer += axes[axis].dst;
1319                src_outer += axes[axis].src;
1320                break;
1321            }
1322            let last = (axes[axis].dim - 1) as isize;
1323            dst_outer -= last * axes[axis].dst;
1324            src_outer -= last * axes[axis].src;
1325            index[axis] = 0;
1326            axis += 1;
1327        }
1328    }
1329}
1330
1331/// One run along the fused inner axis.
1332///
1333/// # Safety
1334///
1335/// Every `dst_offset + k * dst_stride` and `src_offset + k * src_stride` for
1336/// `k < len` must be an in-bounds slot as described in [`apply_fused_range`],
1337/// with exclusive access to the destination slots.
1338// Run leaf: both base/offset/stride triples, the length and the closure, per run.
1339#[allow(clippy::too_many_arguments)]
1340#[inline(always)]
1341unsafe fn apply_run<D, S, Apply>(
1342    dst_ptr: *mut D,
1343    dst_offset: isize,
1344    dst_stride: isize,
1345    src_ptr: *const S,
1346    src_offset: isize,
1347    src_stride: isize,
1348    len: usize,
1349    apply: &mut Apply,
1350) where
1351    D: Copy,
1352    S: Copy,
1353    Apply: FnMut(&mut D, S),
1354{
1355    if dst_stride == 1 {
1356        // SAFETY: a unit destination stride makes the run `len` consecutive
1357        // in-bounds slots starting at `dst_offset`, exclusively owned here.
1358        let dst_run = unsafe { core::slice::from_raw_parts_mut(dst_ptr.offset(dst_offset), len) };
1359        if src_stride == 1 {
1360            // A `copy_nonoverlapping` per run is not used for plain copies:
1361            // it measured slower than this element loop for short runs
1362            // (one `memcpy` call each) and for long cache-resident copies.
1363            // SAFETY: `len` consecutive in-bounds source slots, which the
1364            // exclusive destination run cannot overlap.
1365            let src_run = unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset), len) };
1366            for (dst, &value) in dst_run.iter_mut().zip(src_run) {
1367                apply(dst, value);
1368            }
1369            return;
1370        }
1371        if src_stride == -1 {
1372            // INVARIANT: the range walks never pass an empty run, and both
1373            // strides are nonzero, so the validated reach `len - 1` fits
1374            // `isize`; casting `len` itself would wrap for a run of
1375            // `isize::MAX + 1` elements. (A `saturating_sub` here measurably
1376            // slowed short unit-stride runs by changing the code layout of
1377            // the whole inlined walk.)
1378            let last = (len - 1) as isize;
1379            // SAFETY: the run reads `src_offset - (len - 1) ..= src_offset`,
1380            // all in-bounds; the lowest one is the run's last source slot.
1381            let src_run =
1382                unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset - last), len) };
1383            for (dst, &value) in dst_run.iter_mut().zip(src_run.iter().rev()) {
1384                apply(dst, value);
1385            }
1386            return;
1387        }
1388        // SAFETY: the run start is an in-bounds source slot.
1389        let src_start = unsafe { src_ptr.offset(src_offset) };
1390        for (position, dst) in dst_run.iter_mut().enumerate() {
1391            // SAFETY: `position < len`, so this is a run source slot.
1392            let value = unsafe { *src_start.offset(position as isize * src_stride) };
1393            apply(dst, value);
1394        }
1395        return;
1396    }
1397    // SAFETY: the run start is an in-bounds slot of each allocation.
1398    let dst_start = unsafe { dst_ptr.offset(dst_offset) };
1399    let src_start = unsafe { src_ptr.offset(src_offset) };
1400    // The bound stays `usize`: a checked broadcast run may hold more than
1401    // `isize::MAX` elements, and `len as isize` would wrap to an empty loop.
1402    for position in 0..len {
1403        // INVARIANT: a nonzero stride bounds the run by its validated reach,
1404        // so `position` fits `isize` exactly; a longer run is possible only
1405        // along a zero stride, where the wrapped cast is multiplied by zero.
1406        let position = position as isize;
1407        // SAFETY: `position < len`, so both are slots of this run.
1408        unsafe {
1409            let value = *src_start.offset(position * src_stride);
1410            apply(&mut *dst_start.offset(position * dst_stride), value);
1411        }
1412    }
1413}
1414
1415fn ensure_same_dims(dst: &[usize], src: &[usize]) -> Result<()> {
1416    if dst != src {
1417        return Err(crate::StridedError::ShapeMismatch(
1418            dst.to_vec(),
1419            src.to_vec(),
1420        ));
1421    }
1422    // Reject an element count beyond usize (a huge stride-0 broadcast)
1423    // instead of replaying it.
1424    crate::kernel::total_len(dst)?;
1425    Ok(())
1426}
1427
1428/// `dest = scale * src` over borrowed raw strided layouts.
1429///
1430/// # Errors
1431///
1432/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
1433/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
1434/// when the element count does not fit `usize`. Nothing is written on error.
1435pub fn copy_scale_raw<T>(
1436    dest: &mut RawStridedMut<'_, T>,
1437    src: &RawStridedRef<'_, T>,
1438    scale: T,
1439) -> Result<()>
1440where
1441    T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
1442{
1443    ensure_same_dims(dest.dims(), src.dims())?;
1444    match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
1445        PairTraversal::Inline(layout) => {
1446            apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
1447                *dst = scale * value
1448            })
1449        }
1450        PairTraversal::Spilled(axes) => {
1451            apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
1452                *dst = scale * value
1453            })
1454        }
1455    }
1456    Ok(())
1457}
1458
1459/// `dest = scale * conj(src)` over borrowed raw strided layouts.
1460///
1461/// # Errors
1462///
1463/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
1464/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
1465/// when the element count does not fit `usize`. Nothing is written on error.
1466pub fn copy_scale_conj_raw<T>(
1467    dest: &mut RawStridedMut<'_, T>,
1468    src: &RawStridedRef<'_, T>,
1469    scale: T,
1470) -> Result<()>
1471where
1472    T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
1473{
1474    ensure_same_dims(dest.dims(), src.dims())?;
1475    match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
1476        PairTraversal::Inline(layout) => {
1477            apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
1478                *dst = scale * value.conj()
1479            })
1480        }
1481        PairTraversal::Spilled(axes) => {
1482            apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
1483                *dst = scale * value.conj()
1484            })
1485        }
1486    }
1487    Ok(())
1488}
1489
1490/// `dest = alpha * src + dest` over borrowed raw strided layouts.
1491///
1492/// # Errors
1493///
1494/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
1495/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
1496/// when the element count does not fit `usize`. Nothing is written on error.
1497pub fn axpy_raw<T>(
1498    dest: &mut RawStridedMut<'_, T>,
1499    src: &RawStridedRef<'_, T>,
1500    alpha: T,
1501) -> Result<()>
1502where
1503    T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
1504{
1505    ensure_same_dims(dest.dims(), src.dims())?;
1506    match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
1507        PairTraversal::Inline(layout) => {
1508            apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
1509                *dst = *dst + alpha * value
1510            })
1511        }
1512        PairTraversal::Spilled(axes) => {
1513            apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
1514                *dst = *dst + alpha * value
1515            })
1516        }
1517    }
1518    Ok(())
1519}
1520
1521/// `dest = alpha * conj(src) + dest` over borrowed raw strided layouts.
1522///
1523/// # Errors
1524///
1525/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
1526/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
1527/// when the element count does not fit `usize`. Nothing is written on error.
1528pub fn axpy_conj_raw<T>(
1529    dest: &mut RawStridedMut<'_, T>,
1530    src: &RawStridedRef<'_, T>,
1531    alpha: T,
1532) -> Result<()>
1533where
1534    T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
1535{
1536    ensure_same_dims(dest.dims(), src.dims())?;
1537    match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
1538        PairTraversal::Inline(layout) => {
1539            apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
1540                *dst = *dst + alpha * value.conj()
1541            })
1542        }
1543        PairTraversal::Spilled(axes) => {
1544            apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
1545                *dst = *dst + alpha * value.conj()
1546            })
1547        }
1548    }
1549    Ok(())
1550}
1551
1552/// The checked route of the given axes of two views: the shared front of
1553/// every `replay_*_raw` entry, parallel and serial.
1554///
1555/// The element count is checked before anything is built. The unfused
1556/// traversal keeps every given extent, and the replay totals (`fused_total`,
1557/// `replay_spilled_raw`) take an unchecked product, so the zero-first count
1558/// of `kernel::total_len` has to keep an empty layout whose nonzero prefix
1559/// overflows, such as `[usize::MAX, 2, 0]`, away from them. An empty layout
1560/// returns before `f` runs.
1561///
1562/// `f` receives the route, the element count and, when the route came out
1563/// tiled, whether the destination was proven injective; the tiles are dropped
1564/// unless it was.
1565///
1566/// The slices are the views' own metadata, borrowed apart from the views so
1567/// that `f` can take the destination mutably.
1568fn with_checked_route<D, S>(
1569    dims: &[usize],
1570    dst_strides: &[isize],
1571    src_dims: &[usize],
1572    src_strides: &[isize],
1573    f: impl FnOnce(Route<'_>, usize, Option<bool>),
1574) -> Result<()> {
1575    ensure_same_dims(dims, src_dims)?;
1576    let total = crate::kernel::total_len(dims)?;
1577    if total == 0 {
1578        return Ok(());
1579    }
1580    with_given_route::<D, S, _>(dims, dst_strides, src_strides, |route| {
1581        let mut route = route;
1582        let mut proven = None;
1583        if route.is_tiled() {
1584            let holds = crate::layout_check::is_injective_layout_without_alloc(dims, dst_strides);
1585            proven = Some(holds);
1586            if !holds {
1587                route = route.untiled();
1588            }
1589        }
1590        f(route, total, proven)
1591    });
1592    Ok(())
1593}
1594
1595/// Checked replay of the given axes of two views: the shared body of the
1596/// parallel `replay_*_raw` entries.
1597fn replay_given<D, S, Apply>(
1598    dest: &mut RawStridedMut<'_, D>,
1599    src: &RawStridedRef<'_, S>,
1600    apply: Apply,
1601    exec: Exec<'_>,
1602) -> Result<()>
1603where
1604    D: Copy + Send + Sync,
1605    S: Copy + Send + Sync,
1606    Apply: Fn(&mut D, S) + Sync,
1607{
1608    let (dims, dst_strides) = (dest.dims(), dest.strides());
1609    let injective = || crate::layout_check::is_injective_layout_without_alloc(dims, dst_strides);
1610    with_checked_route::<D, S>(
1611        dims,
1612        dst_strides,
1613        src.dims(),
1614        src.strides(),
1615        |route, total, proven| {
1616            let exec = if route.is_tiled() {
1617                // The tiled tree gates every node on the caller's token itself; the
1618                // flat width rule would cap it at the width of one flat dispatch.
1619                exec
1620            } else {
1621                let exec = crate::cost::for_len(exec, KernelClass::Copy, total);
1622                if !exec.is_serial() && !proven.unwrap_or_else(injective) {
1623                    // A destination not proven injective replays as one sequential
1624                    // column-major walk, which is also its defined semantics; the
1625                    // budget-one token cannot be widened again by the replay's own
1626                    // width rule.
1627                    exec.limit(NonZeroUsize::MIN)
1628                } else {
1629                    exec
1630                }
1631            };
1632            // SAFETY: the route is built from exactly the views' dims and strides
1633            // (`ensure_same_dims` proved the dims agree); compaction drops only
1634            // extent-1 axes, whose coordinate is always 0, so the reachable
1635            // offsets equal the views' validated set, and the original metadata
1636            // still drives bounds, shape and injectivity. The views' bounds proofs
1637            // therefore cover every replayed offset; `total_len` checked the
1638            // nonzero product; the route's tiles are the decision for its own
1639            // axes, and tiles or a non-serial `exec` are left only for a
1640            // destination proven injective; the exclusive and shared borrows
1641            // cannot overlap.
1642            unsafe {
1643                crate::copy_plan::replay_fused(
1644                    dest,
1645                    src,
1646                    route,
1647                    apply,
1648                    KernelClass::Copy.ns_per_element(),
1649                    exec,
1650                )
1651            };
1652        },
1653    )
1654}
1655
1656/// `dest = src`, replaying the axes of the two views exactly as given.
1657///
1658/// The views carry already-fused dims: no axis is reordered, dropped or
1659/// merged, and no plan is compiled. Axis 0 is the inner run of the
1660/// column-major walk; when the shared cache-block model finds tiles that change
1661/// the visit order and can reuse a cache line, the walk goes tile by tile
1662/// instead, each tile column-major over the given axes. Bounds were validated when the views were built
1663/// ([`RawStridedRef::new`], [`RawStridedMut::new`]).
1664///
1665/// On a successful call the replay itself (validation, traversal and
1666/// dispatch) allocates nothing at any rank on a serial token, or on a pooled
1667/// token whose replay is not tiled. A pooled tiled replay with more than
1668/// [`RAW_FUSED_RANK_LIMIT`] moving axes may allocate the splitter's metadata.
1669/// The wide route uses a rank-bounded amount of stack. An error may allocate
1670/// its payload.
1671///
1672/// The width comes from the repository rule on `exec`. A parallel or tiled
1673/// replay runs only on a destination proven injective without allocating; any
1674/// other destination is replayed serially in column-major order of the given
1675/// axes.
1676///
1677/// # Errors
1678///
1679/// [`StridedError::ShapeMismatch`](crate::StridedError::ShapeMismatch) when the
1680/// two views have different dims, and
1681/// [`StridedError::OffsetOverflow`](crate::StridedError::OffsetOverflow) when the
1682/// element count overflows `usize`; both before any write.
1683///
1684/// # Examples
1685///
1686/// Copy the outer band `1..3` of a stored `2 x 3` block into a transposed
1687/// destination:
1688///
1689/// ```rust
1690/// use strided_basic::{replay_copy_raw, Exec, RawStridedMut, RawStridedRef};
1691///
1692/// let stored = [0.0f64, 1.0, 2.0, 3.0, 4.0, 5.0]; // column-major 2 x 3
1693/// let band = [2usize, 2];
1694/// let src = RawStridedRef::new(&stored, &band, &[1, 2], 2).unwrap();
1695/// let mut out = [0.0f64; 4];
1696/// let mut dst = RawStridedMut::new(&mut out, &band, &[2, 1], 0).unwrap();
1697/// replay_copy_raw(&mut dst, &src, Exec::serial()).unwrap();
1698/// assert_eq!(out, [2.0, 4.0, 3.0, 5.0]);
1699/// ```
1700pub fn replay_copy_raw<T>(
1701    dest: &mut RawStridedMut<'_, T>,
1702    src: &RawStridedRef<'_, T>,
1703    exec: Exec<'_>,
1704) -> Result<()>
1705where
1706    T: Copy + Send + Sync,
1707{
1708    replay_given(dest, src, |dst: &mut T, value: T| *dst = value, exec)
1709}
1710
1711/// [`replay_copy_raw`] into a potentially uninitialized destination.
1712///
1713/// On success every reachable destination element is initialized and no
1714/// other slot is written. The destination is never read.
1715///
1716/// # Errors
1717///
1718/// As [`replay_copy_raw`].
1719///
1720/// # Examples
1721///
1722/// ```rust
1723/// use core::mem::MaybeUninit;
1724/// use strided_basic::{replay_copy_raw_uninit, Exec, RawStridedMut, RawStridedRef};
1725///
1726/// let src = [1.0f64, 2.0, 3.0];
1727/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
1728/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
1729/// let source = RawStridedRef::new(&src, &[3], &[-1], 2).unwrap();
1730/// replay_copy_raw_uninit(&mut dst, &source, Exec::serial()).unwrap();
1731/// drop(dst);
1732/// // SAFETY: every reachable destination slot was initialized above.
1733/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
1734/// assert_eq!(values, [3.0, 2.0, 1.0]);
1735/// ```
1736pub fn replay_copy_raw_uninit<T>(
1737    dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1738    src: &RawStridedRef<'_, T>,
1739    exec: Exec<'_>,
1740) -> Result<()>
1741where
1742    T: Copy + Send + Sync,
1743{
1744    replay_given(
1745        dest,
1746        src,
1747        |dst: &mut MaybeUninit<T>, value: T| {
1748            dst.write(value);
1749        },
1750        exec,
1751    )
1752}
1753
1754/// `f(&mut dest[i], src[i])` for every element, replaying the axes of the two
1755/// views exactly as given.
1756///
1757/// Traversal, width and errors are those of [`replay_copy_raw`], and so is the
1758/// allocation guarantee, which covers the replay only: allocations made by `f`
1759/// are its own. `f` runs once per logical element with exactly its arithmetic,
1760/// so an accumulate such as `|d, s| *d += s` is exact. The order in which
1761/// elements are visited is unspecified, and on a parallel replay `f` runs
1762/// concurrently on disjoint slots: the result is defined only for an `f` whose
1763/// effect depends on the supplied slot values alone. On a destination that is
1764/// not proven injective, the elements are visited serially in column-major
1765/// order of the given axes.
1766/// For an `FnMut`, or for element types that are not `Send + Sync`, use
1767/// [`replay_map_raw_serial`].
1768///
1769/// # Errors
1770///
1771/// As [`replay_copy_raw`].
1772///
1773/// # Examples
1774///
1775/// ```rust
1776/// use strided_basic::{replay_map_raw, Exec, RawStridedMut, RawStridedRef};
1777///
1778/// let src = [1.0f64, 2.0, 3.0, 4.0];
1779/// let mut acc = [10.0f64, 20.0, 30.0, 40.0];
1780/// let source = RawStridedRef::new(&src, &[2, 2], &[2, 1], 0).unwrap();
1781/// let mut dst = RawStridedMut::new(&mut acc, &[2, 2], &[1, 2], 0).unwrap();
1782/// replay_map_raw(&mut dst, &source, |d, s| *d += s, Exec::serial()).unwrap();
1783/// assert_eq!(acc, [11.0, 23.0, 32.0, 44.0]);
1784/// ```
1785pub fn replay_map_raw<D, S, F>(
1786    dest: &mut RawStridedMut<'_, D>,
1787    src: &RawStridedRef<'_, S>,
1788    f: F,
1789    exec: Exec<'_>,
1790) -> Result<()>
1791where
1792    D: Copy + Send + Sync,
1793    S: Copy + Send + Sync,
1794    F: Fn(&mut D, S) + Send + Sync,
1795{
1796    replay_given(dest, src, f, exec)
1797}
1798
1799/// [`replay_map_raw`] on the calling thread, for callbacks and elements that
1800/// are not `Send + Sync`: `f(&mut dest[i], src[i])` for every element, with
1801/// `f` an `FnMut`.
1802///
1803/// The traversal, the errors and the visit order are those of
1804/// [`replay_map_raw`] under [`Exec::serial()`]: both walk the same route
1805/// through the same leaves. `f` is called exactly once per logical element,
1806/// sequentially on the calling thread, column-major over the given axes with
1807/// axis 0 fastest. The one exception is a destination proven injective whose
1808/// layout the shared cache-block model tiles: the walk then goes tile by tile,
1809/// the tile grid and each tile column-major. A destination that is not proven
1810/// injective is always walked column-major, so an accumulating `f` sees a
1811/// repeated slot once per logical index, in that order.
1812///
1813/// A successful call allocates nothing at any rank; allocations made by `f`
1814/// are its own. The wide route uses a rank-bounded amount of the caller's
1815/// stack. An error may allocate its payload.
1816///
1817/// With `D = MaybeUninit<T>` the destination is initialized only if `f`
1818/// writes its slot on every call: a successful return guarantees that `f` ran
1819/// exactly once for every reachable destination element, not that it wrote.
1820///
1821/// # Errors
1822///
1823/// As [`replay_copy_raw`], before `f` first runs.
1824///
1825/// # Examples
1826///
1827/// A generic copy whose element type need not be `Send` or `Sync`, counting
1828/// its calls through a captured `Rc`:
1829///
1830/// ```rust
1831/// use std::cell::Cell;
1832/// use std::rc::Rc;
1833/// use strided_basic::{replay_map_raw_serial, RawStridedMut, RawStridedRef, Result};
1834///
1835/// fn copy_generic<T: Copy>(dst: &mut RawStridedMut<'_, T>, src: &RawStridedRef<'_, T>) -> Result<()> {
1836///     replay_map_raw_serial(dst, src, |d, s| *d = s)
1837/// }
1838///
1839/// let stored = [0.0f64, 1.0, 2.0, 3.0, 4.0, 5.0]; // column-major 2 x 3
1840/// let src = RawStridedRef::new(&stored, &[2, 3], &[1, 2], 0).unwrap();
1841/// let mut out = [0.0f64; 6];
1842/// let mut dst = RawStridedMut::new(&mut out, &[2, 3], &[3, 1], 0).unwrap();
1843/// copy_generic(&mut dst, &src).unwrap();
1844///
1845/// let calls = Rc::new(Cell::new(0));
1846/// let counter = Rc::clone(&calls);
1847/// replay_map_raw_serial(&mut dst, &src, |d, s| {
1848///     counter.set(counter.get() + 1);
1849///     *d += s;
1850/// })
1851/// .unwrap();
1852/// drop(dst);
1853/// assert_eq!(calls.get(), 6);
1854/// assert_eq!(out, [0.0, 4.0, 8.0, 2.0, 6.0, 10.0]);
1855/// ```
1856///
1857/// An uninitialized destination, filled by a closure that writes every slot:
1858///
1859/// ```rust
1860/// use core::mem::MaybeUninit;
1861/// use strided_basic::{replay_map_raw_serial, RawStridedMut, RawStridedRef};
1862///
1863/// let src = [1.0f64, 2.0, 3.0];
1864/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
1865/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
1866/// let source = RawStridedRef::new(&src, &[3], &[-1], 2).unwrap();
1867/// replay_map_raw_serial(&mut dst, &source, |d: &mut MaybeUninit<f64>, s| {
1868///     d.write(s);
1869/// })
1870/// .unwrap();
1871/// drop(dst);
1872/// // SAFETY: the closure writes its slot on every call, and the successful
1873/// // replay called it once for every reachable destination slot, which are
1874/// // all three slots of `storage`.
1875/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
1876/// assert_eq!(values, [3.0, 2.0, 1.0]);
1877/// ```
1878pub fn replay_map_raw_serial<D, S, F>(
1879    dest: &mut RawStridedMut<'_, D>,
1880    src: &RawStridedRef<'_, S>,
1881    mut f: F,
1882) -> Result<()>
1883where
1884    D: Copy,
1885    S: Copy,
1886    F: FnMut(&mut D, S),
1887{
1888    let (dims, dst_strides) = (dest.dims(), dest.strides());
1889    with_checked_route::<D, S>(
1890        dims,
1891        dst_strides,
1892        src.dims(),
1893        src.strides(),
1894        |route, _, _| {
1895            let src_ptr = src.data().as_ptr();
1896            let src_base = src.offset();
1897            let dst_base = dest.offset();
1898            let dst_ptr = dest.data_mut().as_mut_ptr();
1899            // SAFETY: the route is the one `replay_given` builds from exactly the
1900            // views' dims and strides, so the views' bounds proofs cover every
1901            // replayed offset and `total_len` checked the nonzero product (see
1902            // there). `with_checked_route` kept tiles only for a destination
1903            // proven injective, and an untiled walk is one sequential pass; the
1904            // exclusive and shared borrows cannot overlap.
1905            unsafe { replay_route_serial(dst_ptr, dst_base, src_ptr, src_base, route, &mut f) };
1906        },
1907    )
1908}
1909
1910/// `dest[i] = f(src[i])` into a potentially uninitialized destination.
1911///
1912/// `f` cannot read the destination. On success every reachable destination
1913/// element is initialized and no other slot is written. The visit-order,
1914/// callback and allocation contract is that of [`replay_map_raw`].
1915///
1916/// # Errors
1917///
1918/// As [`replay_copy_raw`].
1919///
1920/// # Examples
1921///
1922/// ```rust
1923/// use core::mem::MaybeUninit;
1924/// use strided_basic::{replay_map_raw_uninit, Exec, RawStridedMut, RawStridedRef};
1925///
1926/// let src = [1i32, 2, 3];
1927/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
1928/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
1929/// let source = RawStridedRef::new(&src, &[3], &[1], 0).unwrap();
1930/// replay_map_raw_uninit(&mut dst, &source, |s| f64::from(s) * 0.5, Exec::serial()).unwrap();
1931/// drop(dst);
1932/// // SAFETY: every reachable destination slot was initialized above.
1933/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
1934/// assert_eq!(values, [0.5, 1.0, 1.5]);
1935/// ```
1936pub fn replay_map_raw_uninit<D, S, F>(
1937    dest: &mut RawStridedMut<'_, MaybeUninit<D>>,
1938    src: &RawStridedRef<'_, S>,
1939    f: F,
1940    exec: Exec<'_>,
1941) -> Result<()>
1942where
1943    D: Copy + Send + Sync,
1944    S: Copy + Send + Sync,
1945    F: Fn(S) -> D + Send + Sync,
1946{
1947    replay_given(
1948        dest,
1949        src,
1950        move |dst: &mut MaybeUninit<D>, value: S| {
1951            dst.write(f(value));
1952        },
1953        exec,
1954    )
1955}
1956
1957/// `f(&mut dest[i], src[i])` after fusing the two layouts inside the call.
1958///
1959/// [`replay_map_raw`] replays the axes exactly as given, so a caller that holds
1960/// an unfused layout has to fuse it first and pays that pass per call. This
1961/// entry performs the same fusion [`copy_scale_raw`] does before choosing the
1962/// route, then replays with the caller's token; the small-block fusion cost is
1963/// therefore inside the crate, once, instead of at every call site.
1964///
1965/// The traversal, width, callback and allocation contracts are those of
1966/// [`replay_map_raw`]: the visit order is unspecified, and a successful call
1967/// allocates nothing at any rank on a serial token, or on a pooled token whose
1968/// replay is not tiled above [`RAW_FUSED_RANK_LIMIT`] moving axes. The fusion
1969/// itself holds its scratch on the stack, so it does not allocate either.
1970///
1971/// # Errors
1972///
1973/// As [`replay_map_raw`].
1974///
1975/// # Examples
1976///
1977/// ```rust
1978/// use strided_basic::{replay_map_raw_fused, Exec, RawStridedMut, RawStridedRef};
1979///
1980/// let src = [1.0f64, 2.0, 3.0, 4.0];
1981/// let mut acc = [10.0f64, 20.0, 30.0, 40.0];
1982/// let source = RawStridedRef::new(&src, &[2, 2], &[2, 1], 0).unwrap();
1983/// // The destination is transposed relative to the source; the fused entry
1984/// // fuses the two layouts before it walks them.
1985/// let mut dst = RawStridedMut::new(&mut acc, &[2, 2], &[1, 2], 0).unwrap();
1986/// replay_map_raw_fused(&mut dst, &source, |d, s| *d += s, Exec::serial()).unwrap();
1987/// assert_eq!(acc, [11.0, 23.0, 32.0, 44.0]);
1988/// ```
1989pub fn replay_map_raw_fused<D, S, F>(
1990    dest: &mut RawStridedMut<'_, D>,
1991    src: &RawStridedRef<'_, S>,
1992    f: F,
1993    exec: Exec<'_>,
1994) -> Result<()>
1995where
1996    D: Copy + Send + Sync,
1997    S: Copy + Send + Sync,
1998    F: Fn(&mut D, S) + Send + Sync,
1999{
2000    replay_fused_given(dest, src, f, exec)
2001}
2002
2003/// [`replay_map_raw_fused`] into a potentially uninitialized destination.
2004///
2005/// `f` cannot read the destination. On success every reachable destination
2006/// element is initialized and no other slot is written. The fused traversal,
2007/// callback and allocation contract is that of [`replay_map_raw_fused`].
2008///
2009/// # Errors
2010///
2011/// As [`replay_map_raw`].
2012///
2013/// # Examples
2014///
2015/// ```rust
2016/// use core::mem::MaybeUninit;
2017/// use strided_basic::{replay_map_raw_uninit_fused, Exec, RawStridedMut, RawStridedRef};
2018///
2019/// let src = [1i32, 2, 3];
2020/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
2021/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
2022/// let source = RawStridedRef::new(&src, &[3], &[1], 0).unwrap();
2023/// replay_map_raw_uninit_fused(&mut dst, &source, |s| f64::from(s) * 0.5, Exec::serial())
2024///     .unwrap();
2025/// drop(dst);
2026/// // SAFETY: every reachable destination slot was initialized above.
2027/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
2028/// assert_eq!(values, [0.5, 1.0, 1.5]);
2029/// ```
2030pub fn replay_map_raw_uninit_fused<D, S, F>(
2031    dest: &mut RawStridedMut<'_, MaybeUninit<D>>,
2032    src: &RawStridedRef<'_, S>,
2033    f: F,
2034    exec: Exec<'_>,
2035) -> Result<()>
2036where
2037    D: Copy + Send + Sync,
2038    S: Copy + Send + Sync,
2039    F: Fn(S) -> D + Send + Sync,
2040{
2041    replay_fused_given(
2042        dest,
2043        src,
2044        move |dst: &mut MaybeUninit<D>, value: S| {
2045            dst.write(f(value));
2046        },
2047        exec,
2048    )
2049}
2050
2051/// Fuse the compacted moving axes of the pair on the stack, then replay them.
2052///
2053/// [`fuse_pair_traversal`] keeps a `Vec` for an original rank above
2054/// [`RAW_FUSED_RANK_LIMIT`]; this path compacts extent-1 axes first and holds
2055/// both the compacted and the fused axes in fixed arrays, so the fusion adds no
2056/// allocation at any rank. The element count is checked before the arrays are
2057/// indexed, which also bounds the moving-axis count by
2058/// [`MAX_MOVING_AXES`].
2059fn replay_fused_given<D, S, Apply>(
2060    dest: &mut RawStridedMut<'_, D>,
2061    src: &RawStridedRef<'_, S>,
2062    apply: Apply,
2063    exec: Exec<'_>,
2064) -> Result<()>
2065where
2066    D: Copy + Send + Sync,
2067    S: Copy + Send + Sync,
2068    Apply: Fn(&mut D, S) + Send + Sync,
2069{
2070    ensure_same_dims(dest.dims(), src.dims())?;
2071    if crate::kernel::total_len(dest.dims())? == 0 {
2072        return Ok(());
2073    }
2074
2075    let mut dims = [1usize; MAX_MOVING_AXES];
2076    let mut dst_strides = [0isize; MAX_MOVING_AXES];
2077    let mut src_strides = [0isize; MAX_MOVING_AXES];
2078    let mut moving = 0;
2079    for ((&dim, &dst), &src_stride) in dest.dims().iter().zip(dest.strides()).zip(src.strides()) {
2080        if dim == 1 {
2081            continue;
2082        }
2083        // INVARIANT: the checked nonzero count gives `2^moving <= total`, so
2084        // `moving < MAX_MOVING_AXES`.
2085        dims[moving] = dim;
2086        dst_strides[moving] = dst;
2087        src_strides[moving] = src_stride;
2088        moving += 1;
2089    }
2090
2091    let mut fused = [EMPTY_AXIS; MAX_MOVING_AXES];
2092    let rank = fuse_axes(
2093        &mut fused[..moving.max(1)],
2094        &dims[..moving],
2095        &dst_strides[..moving],
2096        &src_strides[..moving],
2097    );
2098    let mut fused_dims = [1usize; MAX_MOVING_AXES];
2099    let mut fused_dst = [0isize; MAX_MOVING_AXES];
2100    let mut fused_src = [0isize; MAX_MOVING_AXES];
2101    for (slot, axis) in fused[..rank].iter().enumerate() {
2102        fused_dims[slot] = axis.dim;
2103        fused_dst[slot] = axis.dst;
2104        fused_src[slot] = axis.src;
2105    }
2106
2107    let dst_offset = dest.offset();
2108    let src_offset = src.offset();
2109    // SAFETY: fusion only reorders and merges the compacted moving axes, so the
2110    // set of reachable offsets is unchanged and the views' constructors already
2111    // proved that set inside their data.
2112    let mut dest = unsafe {
2113        RawStridedMut::new_unchecked(
2114            dest.data_mut(),
2115            &fused_dims[..rank],
2116            &fused_dst[..rank],
2117            dst_offset,
2118        )
2119    };
2120    let src = unsafe {
2121        RawStridedRef::new_unchecked(
2122            src.data(),
2123            &fused_dims[..rank],
2124            &fused_src[..rank],
2125            src_offset,
2126        )
2127    };
2128    replay_given(&mut dest, &src, apply, exec)
2129}
2130
2131#[cfg(test)]
2132#[path = "raw_ops/tests/tests.rs"]
2133mod tests;
2134
2135#[cfg(test)]
2136#[path = "raw_ops/tests/replay_tests.rs"]
2137mod replay_tests;
2138
2139#[cfg(test)]
2140#[path = "raw_ops/tests/tiled_tests.rs"]
2141mod tiled_tests;