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`], one
7//! rank-bounded spill above that), and run plain loops - no view plan, no
8//! cache, and no per-element allocation on any call path. Higher *original*
9//! ranks are normalized and fused before that choice is made, so they no
10//! longer leave the fused replay.
11
12use crate::cost::KernelClass;
13use crate::{ElementOpApply, Exec, RawStridedMut, RawStridedRef, Result};
14use core::mem::MaybeUninit;
15use core::num::NonZeroUsize;
16use core::ops::{Add, Mul};
17
18/// Rank up to which a fused loop nest is stored inline.
19///
20/// The stateless [`copy_scale_raw`] family and [`crate::CopyPlan`] fuse any rank:
21/// layouts whose *fused* rank is at most this limit replay from that inline
22/// storage, and higher fused ranks spill to storage bounded by their rank.
23///
24/// Replay is allocation-free for an original rank at most this limit. A higher
25/// *original* rank needs one transient scratch buffer even when the fused layout
26/// still fits inline, because fusion happens before the representation is
27/// chosen; the replay itself is still allocation-free in that case.
28pub const RAW_FUSED_RANK_LIMIT: usize = 8;
29
30/// One fused axis, used while sorting and merging axes and when a layout has to
31/// spill beyond [`RAW_FUSED_RANK_LIMIT`].
32#[derive(Clone, Copy, Debug)]
33pub(crate) struct FusedAxis {
34    pub(crate) dim: usize,
35    pub(crate) dst: isize,
36    pub(crate) src: isize,
37}
38
39const EMPTY_AXIS: FusedAxis = FusedAxis {
40    dim: 1,
41    dst: 0,
42    src: 0,
43};
44
45/// Stack-allocated fused stride pair (axes ordered by destination stride,
46/// adjacent contiguous axes merged). Built once and replayed by both the
47/// per-call raw kernels and the prepared [`crate::CopyPlan`].
48///
49/// This is the representation every call site replays through, so it keeps the
50/// exact shape, size and `Copy`-ness it had before high-rank fusion existed.
51#[derive(Clone, Copy, Debug)]
52pub(crate) struct FusedPairLayout {
53    pub(crate) rank: usize,
54    pub(crate) dims: [usize; RAW_FUSED_RANK_LIMIT],
55    dst_strides: [isize; RAW_FUSED_RANK_LIMIT],
56    src_strides: [isize; RAW_FUSED_RANK_LIMIT],
57}
58
59impl FusedPairLayout {
60    /// An empty rank-zero layout (one element at the base offset).
61    ///
62    /// Used as the neutral value when an inline `TinyVec<[CopyPlan; N]>` is
63    /// default-initialized; it is never executed as a real plan.
64    fn empty() -> Self {
65        Self {
66            rank: 0,
67            dims: [1; RAW_FUSED_RANK_LIMIT],
68            dst_strides: [0; RAW_FUSED_RANK_LIMIT],
69            src_strides: [0; RAW_FUSED_RANK_LIMIT],
70        }
71    }
72
73    fn from_axes(axes: &[FusedAxis]) -> Self {
74        debug_assert!(axes.len() <= RAW_FUSED_RANK_LIMIT);
75        let mut layout = Self {
76            rank: axes.len(),
77            dims: [1; RAW_FUSED_RANK_LIMIT],
78            dst_strides: [0; RAW_FUSED_RANK_LIMIT],
79            src_strides: [0; RAW_FUSED_RANK_LIMIT],
80        };
81        for (slot, axis) in layout.dims[..axes.len()].iter_mut().zip(axes) {
82            *slot = axis.dim;
83        }
84        for (slot, axis) in layout.dst_strides[..axes.len()].iter_mut().zip(axes) {
85            *slot = axis.dst;
86        }
87        for (slot, axis) in layout.src_strides[..axes.len()].iter_mut().zip(axes) {
88            *slot = axis.src;
89        }
90        layout
91    }
92}
93
94/// A fused pair traversal of any rank.
95///
96/// Fused ranks at most [`RAW_FUSED_RANK_LIMIT`] use the inline layout; longer
97/// layouts keep their axes in one `Vec`. That storage is sized by the original
98/// rank (the fusion scratch is reused, and `truncate` keeps its capacity), never
99/// by the tensor's element count.
100#[derive(Clone, Debug)]
101pub(crate) enum PairTraversal {
102    Inline(FusedPairLayout),
103    Spilled(Vec<FusedAxis>),
104}
105
106impl Default for FusedPairLayout {
107    fn default() -> Self {
108        Self::empty()
109    }
110}
111
112impl Default for PairTraversal {
113    fn default() -> Self {
114        Self::empty()
115    }
116}
117
118impl PairTraversal {
119    /// The empty inline layout, used as a neutral default.
120    #[inline]
121    fn empty() -> Self {
122        Self::Inline(FusedPairLayout::empty())
123    }
124
125    /// The inline layout, or `None` when the traversal spilled.
126    #[inline]
127    pub(crate) fn inline(&self) -> Option<&FusedPairLayout> {
128        match self {
129            Self::Inline(layout) => Some(layout),
130            Self::Spilled(_) => None,
131        }
132    }
133
134    /// Number of fused axes.
135    #[cfg(test)]
136    pub(crate) fn rank(&self) -> usize {
137        match self {
138            Self::Inline(layout) => layout.rank,
139            Self::Spilled(axes) => axes.len(),
140        }
141    }
142}
143
144/// Sort `dims`/`dst_strides`/`src_strides` by destination stride, drop size-1
145/// axes, and merge axes that are contiguous in both layouts.
146///
147/// Returns the fused rank written to `scratch[..rank]`. A zero extent collapses
148/// to a single zero-length axis, which every replay treats as an empty range.
149fn fuse_axes(
150    scratch: &mut [FusedAxis],
151    dims: &[usize],
152    dst_strides: &[isize],
153    src_strides: &[isize],
154) -> usize {
155    debug_assert!(scratch.len() >= dims.len());
156    let mut rank = 0usize;
157    for axis in 0..dims.len() {
158        if dims[axis] == 1 {
159            continue;
160        }
161        if dims[axis] == 0 {
162            scratch[0] = FusedAxis {
163                dim: 0,
164                dst: 0,
165                src: 0,
166            };
167            return 1;
168        }
169        let entry = FusedAxis {
170            dim: dims[axis],
171            dst: dst_strides[axis],
172            src: src_strides[axis],
173        };
174        let mut position = rank;
175        while position > 0 && scratch[position - 1].dst > entry.dst {
176            scratch[position] = scratch[position - 1];
177            position -= 1;
178        }
179        scratch[position] = entry;
180        rank += 1;
181    }
182    if rank == 0 {
183        scratch[0] = EMPTY_AXIS;
184        return 1;
185    }
186    let mut fused = 0usize;
187    for axis in 1..rank {
188        // A merged extent that overflows (possible for a stride-0 broadcast
189        // whose element count exceeds usize) leaves the axes unfused.
190        let merged = isize::try_from(scratch[fused].dim)
191            .ok()
192            .filter(|&extent| {
193                scratch[fused].dst.checked_mul(extent) == Some(scratch[axis].dst)
194                    && scratch[fused].src.checked_mul(extent) == Some(scratch[axis].src)
195            })
196            .and_then(|_| scratch[fused].dim.checked_mul(scratch[axis].dim));
197        if let Some(merged) = merged {
198            scratch[fused].dim = merged;
199        } else {
200            fused += 1;
201            scratch[fused] = scratch[axis];
202        }
203    }
204    fused + 1
205}
206
207/// Fuse a raw stride pair into a traversal of any rank.
208///
209/// Inline when the fused rank is at most [`RAW_FUSED_RANK_LIMIT`], otherwise one
210/// rank-bounded spill. An original rank above the limit uses a transient scratch
211/// buffer even when the fused layout still fits inline, so that fusion happens
212/// before the representation is chosen.
213pub(crate) fn fuse_pair_traversal(
214    dims: &[usize],
215    dst_strides: &[isize],
216    src_strides: &[isize],
217) -> PairTraversal {
218    if dims.len() <= RAW_FUSED_RANK_LIMIT {
219        let mut scratch = [EMPTY_AXIS; RAW_FUSED_RANK_LIMIT];
220        let rank = fuse_axes(&mut scratch, dims, dst_strides, src_strides);
221        debug_assert!(rank <= RAW_FUSED_RANK_LIMIT);
222        return PairTraversal::Inline(FusedPairLayout::from_axes(&scratch[..rank]));
223    }
224    let mut scratch = vec![EMPTY_AXIS; dims.len()];
225    let rank = fuse_axes(&mut scratch, dims, dst_strides, src_strides);
226    scratch.truncate(rank);
227    if rank <= RAW_FUSED_RANK_LIMIT {
228        PairTraversal::Inline(FusedPairLayout::from_axes(&scratch))
229    } else {
230        PairTraversal::Spilled(scratch)
231    }
232}
233
234impl PairTraversal {
235    /// The given axes as a traversal, in their given order: nothing is
236    /// sorted, merged or dropped. Rank zero becomes the one-element
237    /// `EMPTY_AXIS` layout that [`fuse_axes`] also produces.
238    ///
239    /// The three slices must have equal length, and the extents a checked,
240    /// nonzero product (the replay totals multiply them unchecked).
241    pub(crate) fn given(dims: &[usize], dst_strides: &[isize], src_strides: &[isize]) -> Self {
242        debug_assert!(dims.len() == dst_strides.len() && dims.len() == src_strides.len());
243        let rank = dims.len();
244        if rank > RAW_FUSED_RANK_LIMIT {
245            return Self::Spilled(
246                dims.iter()
247                    .zip(dst_strides)
248                    .zip(src_strides)
249                    .map(|((&dim, &dst), &src)| FusedAxis { dim, dst, src })
250                    .collect(),
251            );
252        }
253        let mut layout = FusedPairLayout::empty();
254        layout.rank = rank.max(1);
255        layout.dims[..rank].copy_from_slice(dims);
256        layout.dst_strides[..rank].copy_from_slice(dst_strides);
257        layout.src_strides[..rank].copy_from_slice(src_strides);
258        Self::Inline(layout)
259    }
260}
261
262/// Fuse a raw stride pair into the inline representation.
263///
264/// Returns `None` when the fused rank exceeds [`RAW_FUSED_RANK_LIMIT`]. Used by
265/// the window plans, whose non-fused replay is compiled alongside the plan.
266pub(crate) fn fuse_pair_layout(
267    dims: &[usize],
268    dst_strides: &[isize],
269    src_strides: &[isize],
270) -> Option<FusedPairLayout> {
271    match fuse_pair_traversal(dims, dst_strides, src_strides) {
272        PairTraversal::Inline(layout) => Some(layout),
273        PairTraversal::Spilled(_) => None,
274    }
275}
276
277/// Number of logical elements covered by a fused layout.
278///
279/// Every constructor of a [`FusedPairLayout`] starts from dims whose product
280/// was checked by [`crate::kernel::total_len`], and fusion only merges axes
281/// with a checked product, so the product cannot overflow.
282#[inline]
283pub(crate) fn fused_total(layout: &FusedPairLayout) -> usize {
284    layout.dims[..layout.rank].iter().product()
285}
286
287/// Number of logical elements covered by a spilled axis list.
288#[inline]
289fn spilled_total(axes: &[FusedAxis]) -> usize {
290    axes.iter().map(|axis| axis.dim).product()
291}
292
293/// Serial replay of a fused pair layout over borrowed raw views.
294///
295/// The destination layout need not be injective: runs are replayed in order,
296/// so accumulating callers such as [`axpy_raw`] keep their sequential
297/// semantics. Parallel replay goes through `copy_plan::replay_fused`, which
298/// the plans and the `replay_*_raw` entries call only with a destination
299/// proven injective or a serial token.
300pub(crate) fn apply_fused_pair<D, S, Apply>(
301    dst: &mut RawStridedMut<'_, D>,
302    src: &RawStridedRef<'_, S>,
303    layout: &FusedPairLayout,
304    apply: Apply,
305) where
306    D: Copy,
307    S: Copy,
308    Apply: Fn(&mut D, S),
309{
310    let total = fused_total(layout);
311    if total == 0 {
312        return;
313    }
314    let src_ptr = src.data().as_ptr();
315    let src_base = src.offset();
316    let dst_base = dst.offset();
317    let dst_ptr = dst.data_mut().as_mut_ptr();
318    // SAFETY: `RawStridedRef`/`RawStridedMut` guarantee (by `new`, or by the
319    // caller of `new_unchecked`) that every offset reachable from their offset
320    // through their dims/strides lies inside their data. Callers pass a layout
321    // fused from exactly those dims/strides, so every logical index in
322    // `0..total` maps to in-bounds source and destination slots. The shared
323    // and exclusive borrows cannot overlap, and this is the only writer.
324    unsafe {
325        apply_fused_range(
326            dst_ptr, dst_base, src_ptr, src_base, layout, 0, total, &apply,
327        );
328    }
329}
330
331/// Serial replay of a spilled fused axis list over borrowed raw views.
332///
333/// Kept out of line and separate from [`apply_fused_pair`] so that the inline
334/// entry points keep the code shape they had before high-rank fusion existed:
335/// fused ranks above [`RAW_FUSED_RANK_LIMIT`] are the rare case, and inlining
336/// this second carry loop into them measurably slowed the inline path (extra
337/// register pressure in a loop that runs once per short run).
338#[inline(never)]
339pub(crate) fn apply_spilled_pair<D, S, Apply>(
340    dst: &mut RawStridedMut<'_, D>,
341    src: &RawStridedRef<'_, S>,
342    axes: &[FusedAxis],
343    apply: Apply,
344) where
345    D: Copy,
346    S: Copy,
347    Apply: Fn(&mut D, S),
348{
349    let total = spilled_total(axes);
350    if total == 0 {
351        return;
352    }
353    let src_ptr = src.data().as_ptr();
354    let src_base = src.offset();
355    let dst_base = dst.offset();
356    let dst_ptr = dst.data_mut().as_mut_ptr();
357    // SAFETY: same contract as `apply_fused_pair`, for the axis list fused from
358    // the same dims/strides.
359    unsafe {
360        apply_spilled_range(dst_ptr, dst_base, src_ptr, src_base, axes, 0, total, &apply);
361    }
362}
363
364/// Replay logical indices `start..start + len` of a fused pair layout, in
365/// column-major order of the fused axes (axis 0 fastest).
366///
367/// The start coordinate is decoded once; runs along axis 0 then advance the
368/// outer coordinates incrementally, so no per-element range checks or
369/// coordinate rebuilds remain in the hot loop.
370///
371/// # Safety
372///
373/// - `start + len` must not exceed [`fused_total`] of `layout`.
374/// - For every logical index `i` in the range, `dst_base` plus the fused
375///   destination offset of `i` must be an in-bounds, writable slot of the
376///   allocation behind `dst_ptr`, and likewise `src_base` plus the source
377///   offset must be an in-bounds, readable slot behind `src_ptr`.
378/// - No other thread may access the destination slots of this range while it
379///   runs, and the source slots must not be written concurrently. Destination
380///   and source slots must not overlap.
381// Range leaf: both bases, the layout, the range and the closure, called once per worker
382// range.
383#[allow(clippy::too_many_arguments)]
384pub(crate) unsafe fn apply_fused_range<D, S, Apply>(
385    dst_ptr: *mut D,
386    dst_base: isize,
387    src_ptr: *const S,
388    src_base: isize,
389    layout: &FusedPairLayout,
390    start: usize,
391    len: usize,
392    apply: &Apply,
393) where
394    D: Copy,
395    S: Copy,
396    Apply: Fn(&mut D, S),
397{
398    if len == 0 {
399        return;
400    }
401    let rank = layout.rank;
402    let inner_len = layout.dims[0];
403    let inner_dst = layout.dst_strides[0];
404    let inner_src = layout.src_strides[0];
405
406    // Decode the start coordinate once per range. `dst_offset`/`src_offset`
407    // track the offset of the current run start (outer coordinates plus the
408    // inner coordinate `inner_start`); every value is a reachable offset.
409    let mut index = [0usize; RAW_FUSED_RANK_LIMIT];
410    let mut rest = start;
411    let mut dst_outer = dst_base;
412    let mut src_outer = src_base;
413    // The axis indexes `index`, `layout.dims` and both stride tables at once.
414    #[allow(clippy::needless_range_loop)]
415    for axis in 0..rank {
416        let dim = layout.dims[axis];
417        index[axis] = rest % dim;
418        rest /= dim;
419        if axis > 0 {
420            dst_outer += index[axis] as isize * layout.dst_strides[axis];
421            src_outer += index[axis] as isize * layout.src_strides[axis];
422        }
423    }
424    let mut inner_start = index[0];
425    let mut remaining = len;
426    loop {
427        let run = (inner_len - inner_start).min(remaining);
428        let dst_run = dst_outer + inner_start as isize * inner_dst;
429        let src_run = src_outer + inner_start as isize * inner_src;
430        // SAFETY: the run covers logical indices inside the caller's range, so
431        // by this function's contract every slot touched below is in-bounds,
432        // exclusively owned by this call (destination) and unaliased.
433        unsafe {
434            apply_run(
435                dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
436            )
437        };
438        remaining -= run;
439        if remaining == 0 {
440            return;
441        }
442        inner_start = 0;
443        // Advance an axis only when another position along it follows, and
444        // rewind it from its last position, so every intermediate base is a
445        // reachable offset of a validated layout (issue #243 follow-up): a
446        // layout ending within one stride of `isize::MAX` must not overflow.
447        // `remaining > 0` guarantees a following run exists, so the loop
448        // always finds an axis to advance before running out of rank.
449        let mut axis = 1;
450        while axis < rank {
451            if index[axis] + 1 < layout.dims[axis] {
452                index[axis] += 1;
453                dst_outer += layout.dst_strides[axis];
454                src_outer += layout.src_strides[axis];
455                break;
456            }
457            let last = (layout.dims[axis] - 1) as isize;
458            dst_outer -= last * layout.dst_strides[axis];
459            src_outer -= last * layout.src_strides[axis];
460            index[axis] = 0;
461            axis += 1;
462        }
463    }
464}
465
466/// Replay logical indices `start..start + len` of a spilled fused axis list, in
467/// column-major order of the axes (axis 0 fastest).
468///
469/// The carry loop is the one [`apply_fused_range`] uses, over interleaved axes
470/// with its carry state in one rank-bounded `Vec`: no allocation scales with
471/// the tensor size and no per-element coordinate decode happens.
472///
473/// # Safety
474///
475/// The [`apply_fused_range`] contract holds for `axes`.
476///
477/// Kept out of line: inlining this second carry loop into the inline replay
478/// measurably slows that one down.
479// Same shape as `apply_fused_range` for the spilled layout, per worker range.
480#[allow(clippy::too_many_arguments)]
481#[inline(never)]
482pub(crate) unsafe fn apply_spilled_range<D, S, Apply>(
483    dst_ptr: *mut D,
484    dst_base: isize,
485    src_ptr: *const S,
486    src_base: isize,
487    axes: &[FusedAxis],
488    start: usize,
489    len: usize,
490    apply: &Apply,
491) where
492    D: Copy,
493    S: Copy,
494    Apply: Fn(&mut D, S),
495{
496    if len == 0 {
497        return;
498    }
499    let rank = axes.len();
500    let inner_len = axes[0].dim;
501    let inner_dst = axes[0].dst;
502    let inner_src = axes[0].src;
503
504    let mut index = vec![0usize; rank];
505    let mut rest = start;
506    let mut dst_outer = dst_base;
507    let mut src_outer = src_base;
508    for axis in 0..rank {
509        let dim = axes[axis].dim;
510        index[axis] = rest % dim;
511        rest /= dim;
512        if axis > 0 {
513            dst_outer += index[axis] as isize * axes[axis].dst;
514            src_outer += index[axis] as isize * axes[axis].src;
515        }
516    }
517    let mut inner_start = index[0];
518    let mut remaining = len;
519    loop {
520        let run = (inner_len - inner_start).min(remaining);
521        let dst_run = dst_outer + inner_start as isize * inner_dst;
522        let src_run = src_outer + inner_start as isize * inner_src;
523        // SAFETY: the run covers logical indices inside the caller's range, so
524        // by the caller's contract every slot touched below is in-bounds,
525        // exclusively owned by this call (destination) and unaliased.
526        unsafe {
527            apply_run(
528                dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
529            )
530        };
531        remaining -= run;
532        if remaining == 0 {
533            return;
534        }
535        inner_start = 0;
536        // Same incremental carry as the inline replay: offsets only ever hold
537        // reachable positions, and `remaining > 0` guarantees an axis advances.
538        let mut axis = 1;
539        while axis < rank {
540            if index[axis] + 1 < axes[axis].dim {
541                index[axis] += 1;
542                dst_outer += axes[axis].dst;
543                src_outer += axes[axis].src;
544                break;
545            }
546            let last = (axes[axis].dim - 1) as isize;
547            dst_outer -= last * axes[axis].dst;
548            src_outer -= last * axes[axis].src;
549            index[axis] = 0;
550            axis += 1;
551        }
552    }
553}
554
555/// One run along the fused inner axis.
556///
557/// # Safety
558///
559/// Every `dst_offset + k * dst_stride` and `src_offset + k * src_stride` for
560/// `k < len` must be an in-bounds slot as described in [`apply_fused_range`],
561/// with exclusive access to the destination slots.
562// Run leaf: both base/offset/stride triples, the length and the closure, per run.
563#[allow(clippy::too_many_arguments)]
564#[inline(always)]
565unsafe fn apply_run<D, S, Apply>(
566    dst_ptr: *mut D,
567    dst_offset: isize,
568    dst_stride: isize,
569    src_ptr: *const S,
570    src_offset: isize,
571    src_stride: isize,
572    len: usize,
573    apply: &Apply,
574) where
575    D: Copy,
576    S: Copy,
577    Apply: Fn(&mut D, S),
578{
579    if dst_stride == 1 {
580        // SAFETY: a unit destination stride makes the run `len` consecutive
581        // in-bounds slots starting at `dst_offset`, exclusively owned here.
582        let dst_run = unsafe { core::slice::from_raw_parts_mut(dst_ptr.offset(dst_offset), len) };
583        if src_stride == 1 {
584            // A `copy_nonoverlapping` per run is not used for plain copies:
585            // it measured slower than this element loop for short runs
586            // (one `memcpy` call each) and for long cache-resident copies.
587            // SAFETY: `len` consecutive in-bounds source slots, which the
588            // exclusive destination run cannot overlap.
589            let src_run = unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset), len) };
590            for (dst, &value) in dst_run.iter_mut().zip(src_run) {
591                apply(dst, value);
592            }
593            return;
594        }
595        if src_stride == -1 {
596            // INVARIANT: the range walks never pass an empty run, and both
597            // strides are nonzero, so the validated reach `len - 1` fits
598            // `isize`; casting `len` itself would wrap for a run of
599            // `isize::MAX + 1` elements. (A `saturating_sub` here measurably
600            // slowed short unit-stride runs by changing the code layout of
601            // the whole inlined walk.)
602            let last = (len - 1) as isize;
603            // SAFETY: the run reads `src_offset - (len - 1) ..= src_offset`,
604            // all in-bounds; the lowest one is the run's last source slot.
605            let src_run =
606                unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset - last), len) };
607            for (dst, &value) in dst_run.iter_mut().zip(src_run.iter().rev()) {
608                apply(dst, value);
609            }
610            return;
611        }
612        // SAFETY: the run start is an in-bounds source slot.
613        let src_start = unsafe { src_ptr.offset(src_offset) };
614        for (position, dst) in dst_run.iter_mut().enumerate() {
615            // SAFETY: `position < len`, so this is a run source slot.
616            let value = unsafe { *src_start.offset(position as isize * src_stride) };
617            apply(dst, value);
618        }
619        return;
620    }
621    // SAFETY: the run start is an in-bounds slot of each allocation.
622    let dst_start = unsafe { dst_ptr.offset(dst_offset) };
623    let src_start = unsafe { src_ptr.offset(src_offset) };
624    // The bound stays `usize`: a checked broadcast run may hold more than
625    // `isize::MAX` elements, and `len as isize` would wrap to an empty loop.
626    for position in 0..len {
627        // INVARIANT: a nonzero stride bounds the run by its validated reach,
628        // so `position` fits `isize` exactly; a longer run is possible only
629        // along a zero stride, where the wrapped cast is multiplied by zero.
630        let position = position as isize;
631        // SAFETY: `position < len`, so both are slots of this run.
632        unsafe {
633            let value = *src_start.offset(position * src_stride);
634            apply(&mut *dst_start.offset(position * dst_stride), value);
635        }
636    }
637}
638
639fn ensure_same_dims(dst: &[usize], src: &[usize]) -> Result<()> {
640    if dst != src {
641        return Err(crate::StridedError::ShapeMismatch(
642            dst.to_vec(),
643            src.to_vec(),
644        ));
645    }
646    // Reject an element count beyond usize (a huge stride-0 broadcast)
647    // instead of replaying it.
648    crate::kernel::total_len(dst)?;
649    Ok(())
650}
651
652/// `dest = scale * src` over borrowed raw strided layouts.
653///
654/// # Errors
655///
656/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
657/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
658/// when the element count does not fit `usize`. Nothing is written on error.
659pub fn copy_scale_raw<T>(
660    dest: &mut RawStridedMut<'_, T>,
661    src: &RawStridedRef<'_, T>,
662    scale: T,
663) -> Result<()>
664where
665    T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
666{
667    ensure_same_dims(dest.dims(), src.dims())?;
668    match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
669        PairTraversal::Inline(layout) => {
670            apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
671                *dst = scale * value
672            })
673        }
674        PairTraversal::Spilled(axes) => {
675            apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
676                *dst = scale * value
677            })
678        }
679    }
680    Ok(())
681}
682
683/// `dest = scale * conj(src)` over borrowed raw strided layouts.
684///
685/// # Errors
686///
687/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
688/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
689/// when the element count does not fit `usize`. Nothing is written on error.
690pub fn copy_scale_conj_raw<T>(
691    dest: &mut RawStridedMut<'_, T>,
692    src: &RawStridedRef<'_, T>,
693    scale: T,
694) -> Result<()>
695where
696    T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
697{
698    ensure_same_dims(dest.dims(), src.dims())?;
699    match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
700        PairTraversal::Inline(layout) => {
701            apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
702                *dst = scale * value.conj()
703            })
704        }
705        PairTraversal::Spilled(axes) => {
706            apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
707                *dst = scale * value.conj()
708            })
709        }
710    }
711    Ok(())
712}
713
714/// `dest = alpha * src + dest` over borrowed raw strided layouts.
715///
716/// # Errors
717///
718/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
719/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
720/// when the element count does not fit `usize`. Nothing is written on error.
721pub fn axpy_raw<T>(
722    dest: &mut RawStridedMut<'_, T>,
723    src: &RawStridedRef<'_, T>,
724    alpha: T,
725) -> Result<()>
726where
727    T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
728{
729    ensure_same_dims(dest.dims(), src.dims())?;
730    match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
731        PairTraversal::Inline(layout) => {
732            apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
733                *dst = *dst + alpha * value
734            })
735        }
736        PairTraversal::Spilled(axes) => {
737            apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
738                *dst = *dst + alpha * value
739            })
740        }
741    }
742    Ok(())
743}
744
745/// `dest = alpha * conj(src) + dest` over borrowed raw strided layouts.
746///
747/// # Errors
748///
749/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
750/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
751/// when the element count does not fit `usize`. Nothing is written on error.
752pub fn axpy_conj_raw<T>(
753    dest: &mut RawStridedMut<'_, T>,
754    src: &RawStridedRef<'_, T>,
755    alpha: T,
756) -> Result<()>
757where
758    T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
759{
760    ensure_same_dims(dest.dims(), src.dims())?;
761    match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
762        PairTraversal::Inline(layout) => {
763            apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
764                *dst = *dst + alpha * value.conj()
765            })
766        }
767        PairTraversal::Spilled(axes) => {
768            apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
769                *dst = *dst + alpha * value.conj()
770            })
771        }
772    }
773    Ok(())
774}
775
776/// Checked replay of the given axes of two views: the shared body of the
777/// `replay_*_raw` entries.
778///
779/// The element count is checked before anything is built. The unfused
780/// traversal keeps every given extent, and the replay totals (`fused_total`,
781/// `replay_spilled_raw`) take an unchecked product, so the zero-first count
782/// of `kernel::total_len` has to keep an empty layout whose nonzero prefix
783/// overflows, such as `[usize::MAX, 2, 0]`, away from them.
784fn replay_given<D, S, Apply>(
785    dest: &mut RawStridedMut<'_, D>,
786    src: &RawStridedRef<'_, S>,
787    apply: Apply,
788    exec: Exec<'_>,
789) -> Result<()>
790where
791    D: Copy + Send + Sync,
792    S: Copy + Send + Sync,
793    Apply: Fn(&mut D, S) + Sync,
794{
795    ensure_same_dims(dest.dims(), src.dims())?;
796    let total = crate::kernel::total_len(dest.dims())?;
797    if total == 0 {
798        return Ok(());
799    }
800    let traversal = PairTraversal::given(dest.dims(), dest.strides(), src.strides());
801    let mut exec = crate::cost::for_len(exec, KernelClass::Copy, total);
802    if !exec.is_serial()
803        && !crate::layout_check::is_injective_layout_without_alloc(dest.dims(), dest.strides())
804    {
805        // A destination not proven injective replays as one sequential walk,
806        // which is also its defined semantics; the budget-one token cannot be
807        // widened again by the replay's own width rule.
808        exec = exec.limit(NonZeroUsize::MIN);
809    }
810    // SAFETY: `traversal` is built from exactly the views' dims and strides
811    // (`ensure_same_dims` proved the dims agree), so the views' bounds proofs
812    // cover every replayed offset; `total_len` checked the nonzero product;
813    // a non-serial `exec` is left only for a destination proven injective;
814    // the exclusive and shared borrows cannot overlap.
815    unsafe { crate::copy_plan::replay_fused(dest, src, &traversal, apply, exec) };
816    Ok(())
817}
818
819/// `dest = src`, replaying the axes of the two views exactly as given.
820///
821/// The views carry already-fused dims: no axis is reordered, dropped or
822/// merged, and no plan is compiled. Axis 0 is the inner run. Bounds were validated when the views were built
823/// ([`RawStridedRef::new`], [`RawStridedMut::new`]). On a successful call the
824/// replay itself (validation, traversal and dispatch) allocates nothing for a
825/// rank at most [`RAW_FUSED_RANK_LIMIT`]; above it, the axis list and the cursor
826/// of each replayed range are stored in rank-sized buffers. An error may
827/// allocate its payload.
828///
829/// The width comes from the repository rule on `exec`. A parallel replay runs
830/// only on a destination proven injective without allocating; any other
831/// destination is replayed serially in column-major order of the given axes.
832///
833/// # Errors
834///
835/// [`StridedError::ShapeMismatch`](crate::StridedError::ShapeMismatch) when the
836/// two views have different dims, and
837/// [`StridedError::OffsetOverflow`](crate::StridedError::OffsetOverflow) when the
838/// element count overflows `usize`; both before any write.
839///
840/// # Examples
841///
842/// Copy the outer band `1..3` of a stored `2 x 3` block into a transposed
843/// destination:
844///
845/// ```rust
846/// use strided_basic::{replay_copy_raw, Exec, RawStridedMut, RawStridedRef};
847///
848/// let stored = [0.0f64, 1.0, 2.0, 3.0, 4.0, 5.0]; // column-major 2 x 3
849/// let band = [2usize, 2];
850/// let src = RawStridedRef::new(&stored, &band, &[1, 2], 2).unwrap();
851/// let mut out = [0.0f64; 4];
852/// let mut dst = RawStridedMut::new(&mut out, &band, &[2, 1], 0).unwrap();
853/// replay_copy_raw(&mut dst, &src, Exec::serial()).unwrap();
854/// assert_eq!(out, [2.0, 4.0, 3.0, 5.0]);
855/// ```
856pub fn replay_copy_raw<T>(
857    dest: &mut RawStridedMut<'_, T>,
858    src: &RawStridedRef<'_, T>,
859    exec: Exec<'_>,
860) -> Result<()>
861where
862    T: Copy + Send + Sync,
863{
864    replay_given(dest, src, |dst: &mut T, value: T| *dst = value, exec)
865}
866
867/// [`replay_copy_raw`] into a potentially uninitialized destination.
868///
869/// On success every reachable destination element is initialized and no
870/// other slot is written. The destination is never read.
871///
872/// # Errors
873///
874/// As [`replay_copy_raw`].
875///
876/// # Examples
877///
878/// ```rust
879/// use core::mem::MaybeUninit;
880/// use strided_basic::{replay_copy_raw_uninit, Exec, RawStridedMut, RawStridedRef};
881///
882/// let src = [1.0f64, 2.0, 3.0];
883/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
884/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
885/// let source = RawStridedRef::new(&src, &[3], &[-1], 2).unwrap();
886/// replay_copy_raw_uninit(&mut dst, &source, Exec::serial()).unwrap();
887/// drop(dst);
888/// // SAFETY: every reachable destination slot was initialized above.
889/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
890/// assert_eq!(values, [3.0, 2.0, 1.0]);
891/// ```
892pub fn replay_copy_raw_uninit<T>(
893    dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
894    src: &RawStridedRef<'_, T>,
895    exec: Exec<'_>,
896) -> Result<()>
897where
898    T: Copy + Send + Sync,
899{
900    replay_given(
901        dest,
902        src,
903        |dst: &mut MaybeUninit<T>, value: T| {
904            dst.write(value);
905        },
906        exec,
907    )
908}
909
910/// `f(&mut dest[i], src[i])` for every element, replaying the axes of the two
911/// views exactly as given.
912///
913/// Traversal, width and errors are those of [`replay_copy_raw`], and so is the
914/// allocation guarantee, which covers the replay only: allocations made by `f`
915/// are its own. `f` runs once per logical element with exactly its arithmetic,
916/// so an accumulate such as `|d, s| *d += s` is exact. The order in which
917/// elements are visited is unspecified, and on a parallel replay `f` runs
918/// concurrently on disjoint slots: the result is defined only for an `f` whose
919/// effect depends on the supplied slot values alone. On a destination that is
920/// not proven injective, the elements are visited serially in column-major
921/// order of the given axes.
922///
923/// # Errors
924///
925/// As [`replay_copy_raw`].
926///
927/// # Examples
928///
929/// ```rust
930/// use strided_basic::{replay_map_raw, Exec, RawStridedMut, RawStridedRef};
931///
932/// let src = [1.0f64, 2.0, 3.0, 4.0];
933/// let mut acc = [10.0f64, 20.0, 30.0, 40.0];
934/// let source = RawStridedRef::new(&src, &[2, 2], &[2, 1], 0).unwrap();
935/// let mut dst = RawStridedMut::new(&mut acc, &[2, 2], &[1, 2], 0).unwrap();
936/// replay_map_raw(&mut dst, &source, |d, s| *d += s, Exec::serial()).unwrap();
937/// assert_eq!(acc, [11.0, 23.0, 32.0, 44.0]);
938/// ```
939pub fn replay_map_raw<D, S, F>(
940    dest: &mut RawStridedMut<'_, D>,
941    src: &RawStridedRef<'_, S>,
942    f: F,
943    exec: Exec<'_>,
944) -> Result<()>
945where
946    D: Copy + Send + Sync,
947    S: Copy + Send + Sync,
948    F: Fn(&mut D, S) + Send + Sync,
949{
950    replay_given(dest, src, f, exec)
951}
952
953/// `dest[i] = f(src[i])` into a potentially uninitialized destination.
954///
955/// `f` cannot read the destination. On success every reachable destination
956/// element is initialized and no other slot is written. The visit-order,
957/// callback and allocation contract is that of [`replay_map_raw`].
958///
959/// # Errors
960///
961/// As [`replay_copy_raw`].
962///
963/// # Examples
964///
965/// ```rust
966/// use core::mem::MaybeUninit;
967/// use strided_basic::{replay_map_raw_uninit, Exec, RawStridedMut, RawStridedRef};
968///
969/// let src = [1i32, 2, 3];
970/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
971/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
972/// let source = RawStridedRef::new(&src, &[3], &[1], 0).unwrap();
973/// replay_map_raw_uninit(&mut dst, &source, |s| f64::from(s) * 0.5, Exec::serial()).unwrap();
974/// drop(dst);
975/// // SAFETY: every reachable destination slot was initialized above.
976/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
977/// assert_eq!(values, [0.5, 1.0, 1.5]);
978/// ```
979pub fn replay_map_raw_uninit<D, S, F>(
980    dest: &mut RawStridedMut<'_, MaybeUninit<D>>,
981    src: &RawStridedRef<'_, S>,
982    f: F,
983    exec: Exec<'_>,
984) -> Result<()>
985where
986    D: Copy + Send + Sync,
987    S: Copy + Send + Sync,
988    F: Fn(S) -> D + Send + Sync,
989{
990    replay_given(
991        dest,
992        src,
993        move |dst: &mut MaybeUninit<D>, value: S| {
994            dst.write(f(value));
995        },
996        exec,
997    )
998}
999
1000#[cfg(test)]
1001#[path = "raw_ops/tests/tests.rs"]
1002mod tests;
1003
1004#[cfg(test)]
1005#[path = "raw_ops/tests/replay_tests.rs"]
1006mod replay_tests;