Skip to main content

strided_basic/
copy_plan.rs

1//! Prepared (compile-once, execute-many) copy plans over raw strided layouts.
2//!
3//! [`copy_scale_raw`](crate::copy_scale_raw) and friends rebuild the fused
4//! loop nest on every call; for prepared-replay consumers that issue many
5//! small copies with a fixed layout, that per-call planning dominates
6//! (see issue #139). [`CopyPlan`] splits the work: [`CopyPlan::compile`]
7//! validates the layout pair and builds the fused traversal once,
8//! [`CopyPlan::execute`]/[`CopyPlan::execute_scale`]/[`CopyPlan::execute_conj`]
9//! replay it with no heap allocation for fused ranks at most
10//! [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT). The only per-execute
11//! planning is the cache-block selection for the element type, which runs the
12//! shared block model on layouts of at least two non-unit axes. A layout is
13//! walked tile by tile when the tiles change the visit order and can reuse a
14//! cache line across the runs they regroup.
15
16use core::{
17    marker::PhantomData,
18    mem::{size_of, MaybeUninit},
19    ops::{Add, Mul},
20};
21
22use num_traits::{One, Zero};
23
24use crate::cost::KernelClass;
25use crate::raw_ops::{
26    apply_fused_range, apply_spilled_range, apply_spilled_tiled_box, apply_tiled_box,
27    fuse_pair_traversal, fused_total, pair_tiles, replay_route_serial, FusedAxis, FusedPairLayout,
28    PairTiles, PairTraversal, Route, SpilledTiles,
29};
30use crate::{ElementOpApply, Exec, RawStridedMut, RawStridedRef, Result, StridedError};
31use strided_perm::HostClass;
32
33// Same pattern as map_view.rs / outer_product.rs: inline storage in both
34// feature configurations. Only `compile` touches these; `execute*` never
35// allocates for them. (A spilled fused layout replays from stack arrays bounded
36// by its moving-axis count: see `raw_ops::MAX_MOVING_AXES`.)
37type AxisVec<T> = crate::inline::InlineVec<T>;
38
39pub(crate) trait OverwriteWriter<T> {
40    fn dims(&self) -> &[usize];
41    fn strides(&self) -> &[isize];
42    fn offset(&self) -> isize;
43    /// # Safety
44    /// The caller must use the pointer only for the validated allocation and
45    /// logical layout represented by this writer.
46    unsafe fn data_ptr(&mut self) -> *mut T;
47    /// # Safety
48    /// The offset must be an in-bounds logical destination proven by layout.
49    unsafe fn write_at(&mut self, offset: isize, value: T);
50}
51
52pub(crate) trait ReadModifyWrite<T>: OverwriteWriter<T> {
53    /// # Safety
54    /// The offset must be an in-bounds initialized slot covered by the
55    /// traversal's copy and disjointness proof.
56    unsafe fn add_at<F>(&mut self, offset: isize, value: T, combine: F)
57    where
58        F: FnOnce(T, T) -> T;
59}
60
61impl<'a, T> OverwriteWriter<T> for RawStridedMut<'a, T> {
62    fn dims(&self) -> &[usize] {
63        self.dims()
64    }
65    fn strides(&self) -> &[isize] {
66        self.strides()
67    }
68    fn offset(&self) -> isize {
69        self.offset()
70    }
71    unsafe fn data_ptr(&mut self) -> *mut T {
72        self.data_mut().as_mut_ptr()
73    }
74    unsafe fn write_at(&mut self, offset: isize, value: T) {
75        // SAFETY: the prepared layout validates every logical destination.
76        unsafe { self.data_mut().as_mut_ptr().offset(offset).write(value) }
77    }
78}
79
80impl<'a, T> ReadModifyWrite<T> for RawStridedMut<'a, T>
81where
82    T: Add<Output = T>,
83{
84    #[inline(always)]
85    unsafe fn add_at<F>(&mut self, offset: isize, value: T, combine: F)
86    where
87        F: FnOnce(T, T) -> T,
88    {
89        // SAFETY: the copy or initialized caller proves this logical slot.
90        unsafe {
91            let ptr = self.data_mut().as_mut_ptr().offset(offset);
92            ptr.write(combine(ptr.read(), value));
93        }
94    }
95}
96
97impl<'a, T> OverwriteWriter<T> for RawStridedMut<'a, MaybeUninit<T>> {
98    fn dims(&self) -> &[usize] {
99        self.dims()
100    }
101    fn strides(&self) -> &[isize] {
102        self.strides()
103    }
104    fn offset(&self) -> isize {
105        self.offset()
106    }
107    unsafe fn data_ptr(&mut self) -> *mut T {
108        self.data_mut().as_mut_ptr().cast()
109    }
110    unsafe fn write_at(&mut self, offset: isize, value: T) {
111        // SAFETY: the prepared layout validates every logical destination.
112        unsafe {
113            self.data_mut()
114                .as_mut_ptr()
115                .offset(offset)
116                .write(MaybeUninit::new(value))
117        }
118    }
119}
120
121pub(crate) struct InitializedRawDest<'a, T> {
122    ptr: *mut T,
123    extent: usize,
124    dims: &'a [usize],
125    strides: &'a [isize],
126    offset: isize,
127    _marker: PhantomData<&'a mut [MaybeUninit<T>]>,
128}
129
130impl<'a, T> OverwriteWriter<T> for InitializedRawDest<'a, T> {
131    fn dims(&self) -> &[usize] {
132        self.dims
133    }
134    fn strides(&self) -> &[isize] {
135        self.strides
136    }
137    fn offset(&self) -> isize {
138        self.offset
139    }
140    unsafe fn data_ptr(&mut self) -> *mut T {
141        self.ptr
142    }
143    unsafe fn write_at(&mut self, offset: isize, value: T) {
144        debug_assert!(offset >= 0 && (offset as usize) < self.extent);
145        // SAFETY: the copy proof and extent check cover this logical slot.
146        unsafe { self.ptr.offset(offset).write(value) }
147    }
148}
149
150impl<'a, T> ReadModifyWrite<T> for InitializedRawDest<'a, T>
151where
152    T: Add<Output = T>,
153{
154    #[inline(always)]
155    unsafe fn add_at<F>(&mut self, offset: isize, value: T, combine: F)
156    where
157        F: FnOnce(T, T) -> T,
158    {
159        debug_assert!(offset >= 0 && (offset as usize) < self.extent);
160        // SAFETY: the copy proof and extent check cover this logical slot.
161        unsafe {
162            let ptr = self.ptr.offset(offset);
163            ptr.write(combine(ptr.read(), value));
164        }
165    }
166}
167
168/// A compiled copy traversal for one `(dims, dst_strides, src_strides)`
169/// layout pair.
170///
171/// `compile` proves the layout facts once (rank agreement, extent overflow,
172/// destination injectivity) and fuses/orders the loop nest; each `execute*`
173/// call then only re-checks the per-call facts (that the supplied views carry
174/// exactly the compiled layout) and selects the cache blocks for its element
175/// type before replaying the prepared loops. The order in which elements are
176/// visited is unspecified.
177///
178/// Overlapping `src`/`dest` memory is not supported, matching the rest of the
179/// crate.
180///
181/// Ranks above [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT) are supported by the same fused
182/// traversal, which then stores its axes in one rank-bounded allocation.
183///
184/// # Example
185///
186/// ```rust
187/// use strided_basic::{CopyPlan, Exec, RawStridedMut, RawStridedRef};
188///
189/// let dims = [2usize, 3];
190/// let src_strides = [3isize, 1];
191/// let dst_strides = [1isize, 2]; // transposed destination
192/// let plan = CopyPlan::compile(&dims, &dst_strides, &src_strides).unwrap();
193///
194/// let src = [0.0f64, 1.0, 2.0, 10.0, 11.0, 12.0];
195/// let mut dst = [0.0f64; 6];
196/// let src_ref = RawStridedRef::new(&src, &dims, &src_strides, 0).unwrap();
197/// let mut dst_mut = RawStridedMut::new(&mut dst, &dims, &dst_strides, 0).unwrap();
198/// plan.execute(&mut dst_mut, &src_ref, Exec::serial()).unwrap();
199/// assert_eq!(dst, [0.0, 10.0, 1.0, 11.0, 2.0, 12.0]);
200/// ```
201#[derive(Clone, Debug, Default)]
202pub struct CopyPlan {
203    dims: AxisVec<usize>,
204    dst_strides: AxisVec<isize>,
205    src_strides: AxisVec<isize>,
206    fused: PairTraversal,
207    /// Elements each side spans ([`span_elements`]), so that the working set in
208    /// bytes is `dst_span * size_of::<D>() + src_span * size_of::<S>()` at replay,
209    /// where the element types are known.
210    dst_span: usize,
211    src_span: usize,
212}
213
214impl CopyPlan {
215    /// `None` when the fused traversal is stored in the rank-bounded spill.
216    #[inline]
217    pub(crate) fn fused_layout(&self) -> Option<&FusedPairLayout> {
218        self.fused.inline()
219    }
220
221    /// The cache tiles [`Self::execute`] replays this plan's inline layout with
222    /// for destination element `D` and source element `S`, or `None` when it
223    /// keeps the column-major walk or the layout spilled: the one decision a
224    /// caller replaying the plan's inline traversal itself must reuse.
225    #[inline]
226    pub(crate) fn inline_tiles<D, S>(&self) -> Option<PairTiles> {
227        self.fused.inline().and_then(pair_tiles::<D, S>)
228    }
229
230    /// Whether [`Self::tiles`] can return tiles for any element types; known
231    /// at compile time ([`PairTraversal::may_tile`]).
232    #[inline]
233    pub(crate) fn may_tile(&self) -> bool {
234        self.fused.may_tile()
235    }
236
237    /// Copy into uninitialized storage, then lend the initialized destination to `f`.
238    ///
239    /// [`Self::execute_uninit`] initializes every reachable logical destination
240    /// element before `f` runs, so the [`InitializedRawDest`] receipt handed to `f`
241    /// may read and overwrite exactly those offsets. Slots outside the plan's
242    /// reachable set are not written by that copy and it makes no claim about
243    /// them: a caller that handed in a `MaybeUninit` array still owns those slots,
244    /// so they keep whatever initialization the caller left. With
245    /// `CopyPlan::compile(&[2], &[2], &[1])` the offset-1 hole keeps the caller's
246    /// value (measured `[7.0, 99.0, 8.0]` for `src = [7, 8]`) rather than
247    /// becoming uninitialized. That is why the receipt exposes
248    /// `write_at`/`add_at` (copy_plan.rs:138, :150) instead of a typed slice: their
249    /// contracts require an offset proven by this plan's layout. The receipt borrows
250    /// the destination for `f`'s lifetime, so a read-modify-write consumer (the
251    /// gather and scatter update replay in gather_plan.rs) sees the copied operand
252    /// once and cannot alias the source.
253    ///
254    /// # Errors
255    ///
256    /// Returns the [`Self::execute_uninit`] errors (`PlanLayoutMismatch`, before any
257    /// write); `f` runs only on success.
258    pub(crate) fn execute_uninit_then<'a, T, R>(
259        &self,
260        dest: &'a mut RawStridedMut<'a, MaybeUninit<T>>,
261        src: &RawStridedRef<'_, T>,
262        mut exec: Exec<'_>,
263        f: impl for<'b, 'e> FnOnce(InitializedRawDest<'b, T>, Exec<'e>) -> R,
264    ) -> Result<R>
265    where
266        T: Copy + Send + Sync,
267    {
268        self.execute_uninit(dest, src, exec.reborrow())?;
269        let data = dest.data_mut();
270        let receipt = InitializedRawDest {
271            ptr: data.as_mut_ptr().cast(),
272            extent: data.len(),
273            dims: dest.dims(),
274            strides: dest.strides(),
275            offset: dest.offset(),
276            _marker: PhantomData,
277        };
278        Ok(f(receipt, exec))
279    }
280
281    /// Compile a copy plan for the given layout pair.
282    ///
283    /// Performs the layout validation and traversal construction
284    /// (fuse + order) once.
285    ///
286    /// # Errors
287    ///
288    /// Returns [`StridedError::StrideLengthMismatch`] when `dims`,
289    /// `dst_strides`, and `src_strides` do not all have the same length,
290    /// [`StridedError::OffsetOverflow`] when the total element count does not
291    /// fit `usize`, and [`StridedError::NonInjectiveOutputLayout`] when the
292    /// destination layout cannot be proven injective (aliasing elements, or a
293    /// span the check cannot represent).
294    pub fn compile(dims: &[usize], dst_strides: &[isize], src_strides: &[isize]) -> Result<Self> {
295        if dims.len() != dst_strides.len() || dims.len() != src_strides.len() {
296            return Err(StridedError::StrideLengthMismatch);
297        }
298        // A zero-sized layout has zero elements even when its other extents
299        // overflow; only a nonempty overflowing count is rejected.
300        crate::kernel::total_len(dims)?;
301        if !crate::layout_check::is_injective_layout(dims, dst_strides) {
302            return Err(StridedError::NonInjectiveOutputLayout);
303        }
304        let fused = fuse_pair_traversal(dims, dst_strides, src_strides);
305        Ok(Self {
306            dims: dims.into(),
307            dst_strides: dst_strides.into(),
308            src_strides: src_strides.into(),
309            fused,
310            dst_span: span_elements(dims, dst_strides),
311            src_span: span_elements(dims, src_strides),
312        })
313    }
314
315    /// Serial rate this plan prices itself at on host class `host`: the `Copy`
316    /// row while the plan is one contiguous run, the row plus one cache line per
317    /// run of its walk otherwise, the class's beyond-L2 line past its L2 cache
318    /// (strided-rs#364). [`Self::replay`] asks it for [`HostClass::detect`]; the
319    /// class is a parameter so that the tests can pin it.
320    ///
321    /// The element size is the one fact `compile` cannot know, so the footprint
322    /// in bytes is formed here from the compiled span; nothing is probed.
323    fn ns_per_element_on<D, S>(&self, host: HostClass) -> f64 {
324        plan_ns_per_element::<D, S>(host, &self.fused, self.dst_span, self.src_span)
325    }
326
327    /// Check the per-call facts: the supplied views must carry exactly the
328    /// compiled layout. Buffer bounds against that layout were already proven
329    /// by [`RawStridedRef::new`]/[`RawStridedMut::new`] (or asserted by the
330    /// caller of the `new_unchecked` constructors), so layout equality is the
331    /// complete precondition for the pointer-based fused replay below.
332    fn check_call<D, S>(
333        &self,
334        dest: &RawStridedMut<'_, D>,
335        src: &RawStridedRef<'_, S>,
336    ) -> Result<()> {
337        check_layout_pair(&self.dims, &self.dst_strides, &self.src_strides, dest, src)
338    }
339
340    /// Check the per-call facts, then replay the compiled traversal, priced for
341    /// this host's class.
342    fn replay<D, S, Apply>(
343        &self,
344        dest: &mut RawStridedMut<'_, D>,
345        src: &RawStridedRef<'_, S>,
346        apply: Apply,
347        exec: Exec<'_>,
348    ) -> Result<()>
349    where
350        D: Copy + Send + Sync,
351        S: Copy + Send + Sync,
352        Apply: Fn(&mut D, S) + Sync,
353    {
354        self.replay_on(HostClass::detect(), dest, src, apply, exec)
355    }
356
357    /// [`Self::replay`] priced for host class `host`: every scheduling decision
358    /// of the replay asks at [`Self::ns_per_element_on`] of that class. Split out
359    /// so that a test can pin the class and observe the rate reach the replay on
360    /// every host (strided-rs#364).
361    fn replay_on<D, S, Apply>(
362        &self,
363        host: HostClass,
364        dest: &mut RawStridedMut<'_, D>,
365        src: &RawStridedRef<'_, S>,
366        apply: Apply,
367        exec: Exec<'_>,
368    ) -> Result<()>
369    where
370        D: Copy + Send + Sync,
371        S: Copy + Send + Sync,
372        Apply: Fn(&mut D, S) + Sync,
373    {
374        self.check_call(dest, src)?;
375        let ns_per_element = self.ns_per_element_on::<D, S>(host);
376        self.fused.with_route::<D, S, _>(|route| {
377            // SAFETY: `check_call` proved both views carry exactly the compiled
378            // layout, and `fused` is the fusion of that layout (only `compile`
379            // and `Default`, the rank-zero layout, build it). `compile` checked
380            // the element count and proved the destination injective, so the
381            // tiles of `fused` may be replayed.
382            unsafe { replay_fused(dest, src, route, apply, ns_per_element, exec) }
383        });
384        Ok(())
385    }
386
387    /// `dest = src` into a potentially uninitialized destination.
388    ///
389    /// On success every reachable logical destination element is initialized.
390    /// Non-reachable holes in the backing allocation are not written.
391    ///
392    /// # Errors
393    ///
394    /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
395    /// carry the compiled layout, before any write.
396    pub fn execute_uninit<T>(
397        &self,
398        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
399        src: &RawStridedRef<'_, T>,
400        exec: Exec<'_>,
401    ) -> Result<()>
402    where
403        T: Copy + Send + Sync,
404    {
405        self.replay(
406            dest,
407            src,
408            |dst: &mut MaybeUninit<T>, value: T| {
409                dst.write(value);
410            },
411            exec,
412        )
413    }
414
415    /// `dest = src`. Allocation-free for fused ranks at most
416    /// [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT).
417    ///
418    /// # Errors
419    ///
420    /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
421    /// carry the compiled layout, before any write.
422    pub fn execute<T>(
423        &self,
424        dest: &mut RawStridedMut<'_, T>,
425        src: &RawStridedRef<'_, T>,
426        exec: Exec<'_>,
427    ) -> Result<()>
428    where
429        T: Copy + Send + Sync,
430    {
431        self.replay(dest, src, |dst: &mut T, value: T| *dst = value, exec)
432    }
433
434    /// `dest = scale * src`. Allocation-free for fused ranks at most
435    /// [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT).
436    ///
437    /// # Errors
438    ///
439    /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
440    /// carry the compiled layout, before any write.
441    pub fn execute_scale<T>(
442        &self,
443        dest: &mut RawStridedMut<'_, T>,
444        src: &RawStridedRef<'_, T>,
445        scale: T,
446        exec: Exec<'_>,
447    ) -> Result<()>
448    where
449        T: Copy + Mul<T, Output = T> + Send + Sync,
450    {
451        self.replay(
452            dest,
453            src,
454            |dst: &mut T, value: T| *dst = scale * value,
455            exec,
456        )
457    }
458
459    /// `dest = conj(src)`. Allocation-free for fused ranks at most
460    /// [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT).
461    ///
462    /// # Errors
463    ///
464    /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
465    /// carry the compiled layout, before any write.
466    pub fn execute_conj<T>(
467        &self,
468        dest: &mut RawStridedMut<'_, T>,
469        src: &RawStridedRef<'_, T>,
470        exec: Exec<'_>,
471    ) -> Result<()>
472    where
473        T: Copy + ElementOpApply + Send + Sync,
474    {
475        self.replay(dest, src, |dst: &mut T, value: T| *dst = value.conj(), exec)
476    }
477}
478
479/// Whether the replay walks `fused` as one unit-stride run on each side, the
480/// layout the `Copy` row is calibrated on, and the length of the unit-stride run
481/// its walk starts with.
482///
483/// A *run* is a stretch of the walk that advances by one element on both sides;
484/// a streamed contiguous copy is one run and keeps the row at every footprint, a
485/// reversed one (`-1` on a side) streams the same way, and a transposing walk
486/// takes one run of one element per visit. The run length is the
487/// `elements / segments` ratio of strided-rs#364's
488/// `segments * per_segment + elements * per_element_inside_segment`, read off the
489/// frozen fused layout, so it is a compile-time plan property and nothing is
490/// probed.
491///
492/// The question is about the walk the replay takes, not about a walk the layout
493/// would allow: both replays walk the fused axes in their stored order with axis 0
494/// fastest (`apply_fused_range`, `apply_spilled_range`), and the tiled replay only
495/// exists for two or more moving axes. So the strides, read in that order, must be
496/// the running products of the extents with one sign per operand. Fusion already
497/// merges every such pair, so in practice a one-run walk is a fused rank of one at
498/// unit stride; a dense *reversed* buffer of rank two or more is not one run here,
499/// because fusion sorts the axes by signed destination stride and walks
500/// `[-1, -512]` over `[512, 512]` with `-512` fastest (strided-rs#364 review).
501/// That walk's runs are one element long, and it is priced as the strided walk it
502/// is.
503fn walk_runs(fused: &PairTraversal) -> (usize, bool) {
504    /// `(leading run length, that run is the whole walk)`.
505    fn runs(axes: impl Iterator<Item = (usize, isize, isize)>) -> (usize, bool) {
506        let mut len = 1usize;
507        let mut signs = None;
508        for (dim, dst, src) in axes {
509            if dim == 1 {
510                continue;
511            }
512            // A direction flip ends the run too: the walk reverses there, so the
513            // next element is a new cache line even at a unit stride.
514            let axis_signs = (dst < 0, src < 0);
515            if dst.unsigned_abs() != len
516                || src.unsigned_abs() != len
517                || *signs.get_or_insert(axis_signs) != axis_signs
518            {
519                return (len, false);
520            }
521            len = len.saturating_mul(dim);
522        }
523        (len, true)
524    }
525    match fused {
526        PairTraversal::Inline(layout) => runs(inline_axes(layout)),
527        PairTraversal::Spilled(axes) => runs(spilled_axes(axes)),
528    }
529}
530
531// shortcut: the run length is the fused axes' untiled walk. The tiled replay of
532// strided-rs#422 cuts a box, so its runs can be shorter than the leading axis run
533// (an inner extent of 8 tiled to 6 and 2 halves the run length and so doubles the
534// per-run line charge). Upgrade when a tiled plan's in-L2 pricing is measured
535// against the model: derive the charge from `PairTraversal::with_route` then.
536
537/// The axes of a fused walk in replay order (axis 0 fastest) as
538/// `(extent, destination stride, source stride)`.
539fn inline_axes(layout: &FusedPairLayout) -> impl Iterator<Item = (usize, isize, isize)> + '_ {
540    (0..layout.rank).map(move |axis| {
541        (
542            layout.dims[axis],
543            layout.dst_strides[axis],
544            layout.src_strides[axis],
545        )
546    })
547}
548
549/// [`inline_axes`] for the spilled traversal.
550fn spilled_axes(axes: &[FusedAxis]) -> impl Iterator<Item = (usize, isize, isize)> + '_ {
551    axes.iter().map(|axis| (axis.dim, axis.dst, axis.src))
552}
553
554/// Serial rate a copy-shaped plan prices itself at on `host`, from the three
555/// facts `compile` froze in its fused layout and spans: whether the whole walk is
556/// one contiguous run, the length of its runs, and the working set in bytes.
557///
558/// [`CopyPlan`] and [`UpdatePlan`] both replay [`replay_fused`], so both ask their
559/// rate here (strided-rs#364).
560fn plan_ns_per_element<D, S>(
561    host: HostClass,
562    fused: &PairTraversal,
563    dst_span: usize,
564    src_span: usize,
565) -> f64 {
566    let (run_len, one_run) = walk_runs(fused);
567    if one_run {
568        return KernelClass::Copy.ns_per_element_of(host);
569    }
570    let bytes = dst_span
571        .saturating_mul(size_of::<D>())
572        .saturating_add(src_span.saturating_mul(size_of::<S>()));
573    crate::cost::copy_ns_per_element_for_plan(host, bytes, run_len)
574}
575
576/// Elements one side of a compiled layout spans: `1 + sum((dim - 1) * |stride|)`,
577/// the reach of the side from its base offset. Summed over the two sides it is
578/// the plan's working set in elements, saturating rather than wrapping because a
579/// stride is only bounded by `isize`.
580fn span_elements(dims: &[usize], strides: &[isize]) -> usize {
581    dims.iter()
582        .zip(strides)
583        .fold(1usize, |span, (&dim, &stride)| {
584            span.saturating_add(dim.saturating_sub(1).saturating_mul(stride.unsigned_abs()))
585        })
586}
587
588/// Verify that a pair of raw views carries exactly a compiled layout.
589///
590/// Shared by [`CopyPlan`] and [`UpdatePlan`], whose `compile` methods prove the
591/// layout facts once. Buffer bounds against that layout were already proven by
592/// [`RawStridedRef::new`]/[`RawStridedMut::new`] (or asserted by the caller of
593/// the `new_unchecked` constructors), so layout equality is the complete
594/// per-call precondition for the pointer-based fused replay.
595fn check_layout_pair<D, S>(
596    dims: &[usize],
597    dst_strides: &[isize],
598    src_strides: &[isize],
599    dest: &RawStridedMut<'_, D>,
600    src: &RawStridedRef<'_, S>,
601) -> Result<()> {
602    if dest.dims() != dims
603        || src.dims() != dims
604        || dest.strides() != dst_strides
605        || src.strides() != src_strides
606    {
607        return Err(StridedError::PlanLayoutMismatch);
608    }
609    Ok(())
610}
611
612/// A compiled read-modify-write traversal for one `(dims, dst_strides,
613/// src_strides)` layout pair.
614///
615/// [`execute`](Self::execute) computes `dest = alpha * f(src) + beta * dest` by
616/// replaying the same fused pair traversal as [`CopyPlan`]: `compile` proves
617/// the layout facts once (rank agreement, extent overflow, destination
618/// injectivity) and each call only re-checks that the supplied views carry the
619/// compiled layout before running monomorphized loops. Execute is
620/// allocation-free for fused ranks at most
621/// [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT), and the injective
622/// destination makes a large replay parallel-safe exactly as in [`CopyPlan`].
623///
624/// Overlapping `src`/`dest` memory is not supported, matching the rest of the
625/// crate.
626///
627/// # Example
628///
629/// ```rust
630/// use strided_basic::{Exec, RawStridedMut, RawStridedRef, UpdatePlan};
631///
632/// let dims = [2usize, 2];
633/// let dst_strides = [1isize, 2];
634/// let src_strides = [1isize, 2];
635/// let plan = UpdatePlan::compile(&dims, &dst_strides, &src_strides).unwrap();
636///
637/// let src = [1.0f64, 2.0, 3.0, 4.0];
638/// let mut dst = [10.0f64, 20.0, 30.0, 40.0];
639/// let src_ref = RawStridedRef::new(&src, &dims, &src_strides, 0).unwrap();
640/// let mut dst_mut = RawStridedMut::new(&mut dst, &dims, &dst_strides, 0).unwrap();
641/// // dst = 2 * src + 3 * dst
642/// plan.execute(&mut dst_mut, &src_ref, 2.0, 3.0, |x| x, Exec::serial()).unwrap();
643/// assert_eq!(dst, [32.0, 64.0, 96.0, 128.0]);
644/// ```
645#[derive(Clone, Debug)]
646pub struct UpdatePlan {
647    dims: AxisVec<usize>,
648    dst_strides: AxisVec<isize>,
649    src_strides: AxisVec<isize>,
650    fused: PairTraversal,
651    /// Working-set spans, as on [`CopyPlan`]: the footprint in bytes is formed at
652    /// replay, where the element types are known.
653    dst_span: usize,
654    src_span: usize,
655}
656
657impl UpdatePlan {
658    /// Compile an update plan for the given layout pair.
659    ///
660    /// Performs the same layout validation as [`CopyPlan::compile`].
661    ///
662    /// # Errors
663    ///
664    /// Returns [`StridedError::StrideLengthMismatch`] when `dims`,
665    /// `dst_strides`, and `src_strides` do not all have the same length,
666    /// [`StridedError::OffsetOverflow`] when the total element count does not
667    /// fit `usize`, and [`StridedError::NonInjectiveOutputLayout`] when the
668    /// destination layout cannot be proven injective: two logical indices name
669    /// one slot (so a parallel replay would write that slot once per index), or
670    /// the offset span cannot be represented, leaving injectivity undecided.
671    pub fn compile(dims: &[usize], dst_strides: &[isize], src_strides: &[isize]) -> Result<Self> {
672        if dims.len() != dst_strides.len() || dims.len() != src_strides.len() {
673            return Err(StridedError::StrideLengthMismatch);
674        }
675        crate::kernel::total_len(dims)?;
676        if !crate::layout_check::is_injective_layout(dims, dst_strides) {
677            return Err(StridedError::NonInjectiveOutputLayout);
678        }
679        let fused = fuse_pair_traversal(dims, dst_strides, src_strides);
680        Ok(Self {
681            dims: dims.into(),
682            dst_strides: dst_strides.into(),
683            src_strides: src_strides.into(),
684            fused,
685            dst_span: span_elements(dims, dst_strides),
686            src_span: span_elements(dims, src_strides),
687        })
688    }
689
690    /// Serial rate this plan prices itself at on host class `host`: the same
691    /// [`plan_ns_per_element`] as [`CopyPlan`], because both replay
692    /// [`replay_fused`] and a caller that paid the line per run on one would pay
693    /// it on the other (strided-rs#364).
694    fn ns_per_element_on<D, S>(&self, host: HostClass) -> f64 {
695        plan_ns_per_element::<D, S>(host, &self.fused, self.dst_span, self.src_span)
696    }
697
698    /// Check the per-call facts, then replay the compiled traversal, priced for
699    /// this host's class.
700    fn replay<D, S, Apply>(
701        &self,
702        dest: &mut RawStridedMut<'_, D>,
703        src: &RawStridedRef<'_, S>,
704        apply: Apply,
705        exec: Exec<'_>,
706    ) -> Result<()>
707    where
708        D: Copy + Send + Sync,
709        S: Copy + Send + Sync,
710        Apply: Fn(&mut D, S) + Sync,
711    {
712        self.replay_on(HostClass::detect(), dest, src, apply, exec)
713    }
714
715    /// [`Self::replay`] priced for host class `host`: split out for the same
716    /// reason as [`CopyPlan::replay_on`], so that a test can pin the class and see
717    /// the plan's rate reach the replay on every host (strided-rs#364).
718    fn replay_on<D, S, Apply>(
719        &self,
720        host: HostClass,
721        dest: &mut RawStridedMut<'_, D>,
722        src: &RawStridedRef<'_, S>,
723        apply: Apply,
724        exec: Exec<'_>,
725    ) -> Result<()>
726    where
727        D: Copy + Send + Sync,
728        S: Copy + Send + Sync,
729        Apply: Fn(&mut D, S) + Sync,
730    {
731        check_layout_pair(&self.dims, &self.dst_strides, &self.src_strides, dest, src)?;
732        let ns_per_element = self.ns_per_element_on::<D, S>(host);
733        self.fused.with_route::<D, S, _>(|route| {
734            // SAFETY: as in `CopyPlan::replay`: the views carry the compiled
735            // layout, `fused` is its fusion (built only by `compile`), and
736            // `compile` checked the count and destination injectivity.
737            unsafe { replay_fused(dest, src, route, apply, ns_per_element, exec) }
738        });
739        Ok(())
740    }
741
742    /// `dest = alpha * f(src) + beta * dest`.
743    ///
744    /// `f` is applied to the source element before scaling. When `beta` is
745    /// zero (`-0.0` included; `NaN` is not zero) the replay is write-only: the
746    /// old destination element is never read, so a NaN-filled or uninitialized
747    /// destination cannot contaminate the result, matching BLAS `beta = 0`
748    /// semantics. Otherwise the old destination element is read through the
749    /// destination layout. Allocation-free for fused ranks at most
750    /// [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT).
751    ///
752    /// `f` runs once per logical element. The order in which elements are
753    /// visited is unspecified, and on a parallel replay `f` runs concurrently
754    /// on disjoint slots: the result is defined only for an `f` whose effect
755    /// depends on the supplied value alone.
756    ///
757    /// # Errors
758    ///
759    /// [`StridedError::PlanLayoutMismatch`] when the supplied views do not
760    /// carry the compiled layout, before any write.
761    pub fn execute<T, F>(
762        &self,
763        dest: &mut RawStridedMut<'_, T>,
764        src: &RawStridedRef<'_, T>,
765        alpha: T,
766        beta: T,
767        f: F,
768        exec: Exec<'_>,
769    ) -> Result<()>
770    where
771        T: Copy + Send + Sync + Add<Output = T> + Mul<Output = T> + Zero + One + PartialEq,
772        F: Fn(T) -> T + Send + Sync,
773    {
774        if beta.is_zero() {
775            // Write-only: never form a read of the old destination.
776            if alpha.is_one() {
777                self.replay(dest, src, |dst: &mut T, value: T| *dst = f(value), exec)
778            } else {
779                self.replay(
780                    dest,
781                    src,
782                    |dst: &mut T, value: T| *dst = alpha * f(value),
783                    exec,
784                )
785            }
786        } else {
787            self.replay(
788                dest,
789                src,
790                |dst: &mut T, value: T| *dst = alpha * f(value) + beta * *dst,
791                exec,
792            )
793        }
794    }
795
796    /// `dest = alpha * f(src)` into a potentially uninitialized destination.
797    ///
798    /// This is [`execute`](Self::execute) with `beta = 0`: the destination is
799    /// never read. On success every reachable logical destination element is
800    /// initialized; non-reachable holes in the backing allocation are not
801    /// written. Allocation-free for fused ranks at most
802    /// [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT). The visit-order
803    /// and callback contract is that of [`execute`](Self::execute).
804    ///
805    /// # Errors
806    ///
807    /// [`StridedError::PlanLayoutMismatch`] when the supplied views do not
808    /// carry the compiled layout, before any write.
809    ///
810    /// # Examples
811    ///
812    /// ```rust
813    /// use core::mem::MaybeUninit;
814    /// use strided_basic::{Exec, RawStridedMut, RawStridedRef, UpdatePlan};
815    ///
816    /// let dims = [2usize, 2];
817    /// let strides = [1isize, 2];
818    /// let plan = UpdatePlan::compile(&dims, &strides, &strides).unwrap();
819    /// let src = [1.0f64, 2.0, 3.0, 4.0];
820    /// let mut storage = [MaybeUninit::<f64>::uninit(); 4];
821    /// let mut dst = RawStridedMut::new(&mut storage, &dims, &strides, 0).unwrap();
822    /// let source = RawStridedRef::new(&src, &dims, &strides, 0).unwrap();
823    /// // dst = 2 * src
824    /// plan.execute_uninit(&mut dst, &source, 2.0, |x| x, Exec::serial()).unwrap();
825    /// drop(dst);
826    /// // SAFETY: every reachable destination slot was initialized above.
827    /// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
828    /// assert_eq!(values, [2.0, 4.0, 6.0, 8.0]);
829    /// ```
830    pub fn execute_uninit<T, F>(
831        &self,
832        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
833        src: &RawStridedRef<'_, T>,
834        alpha: T,
835        f: F,
836        exec: Exec<'_>,
837    ) -> Result<()>
838    where
839        T: Copy + Send + Sync + Mul<Output = T> + One + PartialEq,
840        F: Fn(T) -> T + Send + Sync,
841    {
842        if alpha.is_one() {
843            self.replay(
844                dest,
845                src,
846                |dst: &mut MaybeUninit<T>, value: T| {
847                    dst.write(f(value));
848                },
849                exec,
850            )
851        } else {
852            self.replay(
853                dest,
854                src,
855                |dst: &mut MaybeUninit<T>, value: T| {
856                    dst.write(alpha * f(value));
857                },
858                exec,
859            )
860        }
861    }
862}
863
864/// Replay `route` over a pair of raw views, splitting it across the budget
865/// of `exec` when the repository threshold allows it.
866///
867/// A tiled route walks its cache tiles and splits the box with the dimension
868/// splitter (see [`replay_fused_raw`] and [`replay_spilled_tiled`]). An
869/// untiled one splits the logical index space `0..total`
870/// (column-major over the traversal axes) is split into contiguous worker
871/// ranges, which divides the outer axes and, when there are fewer outer
872/// positions than workers, also chunks long inner runs (for example a rank-1
873/// contiguous copy). A serial token walks the route through
874/// [`replay_route_serial`], the walk [`crate::replay_map_raw_serial`]
875/// shares.
876///
877/// # Safety
878///
879/// - `route` must replay exactly the logical index space of the two views:
880///   either their dims and strides fused by `fuse_pair_traversal`
881///   ([`PairTraversal::with_route`]), or given by them
882///   ([`crate::raw_ops::with_given_route`]). The views' own bounds proofs
883///   ([`RawStridedRef::new`], [`RawStridedMut::new`], or the caller of their
884///   `new_unchecked`) then make every replayed offset in-bounds.
885/// - The product of the route's extents must not overflow `usize` (a checked
886///   count, zero included).
887/// - The route's tiles, when present, must be the decision of the route
888///   builder for its own axes.
889/// - When the route is tiled or `exec` is not serial, the destination strides
890///   must be injective over the route.
891/// - The destination and source must not overlap.
892///
893/// `ns_per_element` is the serial rate the replay prices itself at; both plan
894/// types pass their own ([`CopyPlan::ns_per_element_on`],
895/// `UpdatePlan::ns_per_element_on`), because the pricing follows the traversal and
896/// not the entry. The plan-free `replay_*_raw` entries pass the rate of
897/// `KernelClass::Copy` ([`crate::cost::KernelClass::ns_per_element`]).
898pub(crate) unsafe fn replay_fused<D, S, Apply>(
899    dest: &mut RawStridedMut<'_, D>,
900    src: &RawStridedRef<'_, S>,
901    route: Route<'_>,
902    mut apply: Apply,
903    ns_per_element: f64,
904    exec: Exec<'_>,
905) where
906    D: Copy + Send + Sync,
907    S: Copy + Send + Sync,
908    Apply: Fn(&mut D, S) + Sync,
909{
910    let src_ptr = src.data().as_ptr();
911    let src_base = src.offset();
912    let dst_base = dest.offset();
913    let dst_ptr = dest.data_mut().as_mut_ptr();
914    if exec.is_serial() {
915        // SAFETY: forwarded caller contract, on a serial token.
916        unsafe {
917            replay_route_serial(dst_ptr, dst_base, src_ptr, src_base, route, &mut apply);
918        }
919        return;
920    }
921    // SAFETY: forwarded caller contract: every logical index of `route` maps
922    // to in-bounds slots of both views, injectivity holds whenever the replay
923    // is tiled or the token can fan out, and the borrows do not overlap. Inline
924    // tiles address exactly the slots of their layout, in the same column-major
925    // order.
926    unsafe {
927        match route {
928            Route::Inline { layout, tiles } => replay_fused_raw(
929                dst_ptr,
930                dst_base,
931                src_ptr,
932                src_base,
933                layout,
934                tiles,
935                apply,
936                ns_per_element,
937                exec,
938            ),
939            Route::Spilled {
940                tiles: Some(tiles), ..
941            } => replay_spilled_tiled(
942                dst_ptr,
943                dst_base,
944                src_ptr,
945                src_base,
946                tiles,
947                apply,
948                exec,
949                ns_per_element,
950            ),
951            Route::Spilled { axes, tiles: None } => replay_spilled_raw(
952                dst_ptr,
953                dst_base,
954                src_ptr,
955                src_base,
956                axes,
957                apply,
958                ns_per_element,
959                exec,
960            ),
961        }
962    }
963}
964
965/// Pointer-level fused replay shared by [`CopyPlan`], [`UpdatePlan`], the
966/// plan-free `replay_*_raw` entries and the dynamic slice plans, which replay
967/// a fused window layout at a runtime base offset.
968///
969/// Without `tiles`, splits `0..total` across the budget of `exec` when the
970/// repository threshold allows more than one slot, otherwise runs the serial
971/// kernel directly. With `tiles`, the box is walked tile by tile; a token on
972/// which one fork pays splits it with the dimension splitter, and every leaf
973/// walks its sub-box with the same tiles anchored at its origin.
974///
975/// # Safety
976///
977/// Every logical index of `layout`, mapped through its destination strides
978/// from `dst_base` and its source strides from `src_base`, must be an
979/// in-bounds slot of the destination and source allocations, and the product
980/// of its extents must not overflow `usize`. `tiles`, when `Some`, must be
981/// `pair_tiles::<D, S>(layout)`. When `tiles` is `Some` or `exec` is not
982/// serial, the destination strides must be injective over `layout`; an
983/// untiled serial replay updates a repeated slot once per logical index, in
984/// order. The destination must not overlap the source, and nothing else may
985/// access the destination slots during the call.
986#[allow(clippy::too_many_arguments)]
987pub(crate) unsafe fn replay_fused_raw<D, S, Apply>(
988    dst_ptr: *mut D,
989    dst_base: isize,
990    src_ptr: *const S,
991    src_base: isize,
992    layout: &FusedPairLayout,
993    tiles: Option<&PairTiles>,
994    mut apply: Apply,
995    ns_per_element: f64,
996    exec: Exec<'_>,
997) where
998    D: Copy + Send + Sync,
999    S: Copy + Send + Sync,
1000    Apply: Fn(&mut D, S) + Sync,
1001{
1002    let total = fused_total(layout);
1003    if total == 0 {
1004        return;
1005    }
1006    if let Some(tiles) = tiles {
1007        // SAFETY: forwarded caller contract; `tiles` addresses exactly the
1008        // slots of `layout` and the destination is injective over them.
1009        unsafe {
1010            replay_tiled(
1011                dst_ptr,
1012                dst_base,
1013                src_ptr,
1014                src_base,
1015                tiles,
1016                &apply,
1017                ns_per_element,
1018                exec,
1019            )
1020        };
1021        return;
1022    }
1023    let exec = crate::cost::for_len_at_rate(exec, total, ns_per_element);
1024    if !exec.is_serial() {
1025        let dst_ptr = crate::threading::SendPtr(dst_ptr);
1026        let src_ptr = crate::threading::SendPtr(src_ptr as *mut S);
1027        crate::threading::parallel_for_each(0..total, exec, &|range| {
1028            // SAFETY: the caller contract makes every index in bounds; the
1029            // token is not serial, so the destination strides are injective
1030            // and the disjoint worker ranges write disjoint slots; the source
1031            // is only read.
1032            unsafe {
1033                apply_fused_range(
1034                    dst_ptr.as_ptr(),
1035                    dst_base,
1036                    src_ptr.as_const(),
1037                    src_base,
1038                    layout,
1039                    range.start,
1040                    range.len(),
1041                    &mut &apply,
1042                );
1043            }
1044        });
1045        return;
1046    }
1047    // SAFETY: forwarded caller contract over the full range `0..total`; one
1048    // sequential walk needs no injectivity.
1049    unsafe {
1050        apply_fused_range(
1051            dst_ptr, dst_base, src_ptr, src_base, layout, 0, total, &mut apply,
1052        );
1053    }
1054}
1055
1056/// Tiled replay of [`replay_fused_raw`]: serially one [`apply_tiled_box`] over
1057/// the whole box, or, when one fork pays, the dimension splitter of the view
1058/// path with one [`apply_tiled_box`] per leaf box.
1059///
1060/// The leaves walk the model's own blocks clipped to the leaf, as Strided.jl's
1061/// leaves rerun `_mapreduce_kernel!` with the same `blocks`; the halved blocks
1062/// the splitter normalizes internally only steer where it may cut.
1063///
1064/// # Safety
1065///
1066/// The [`replay_fused_raw`] contract for `tiles.layout`, with an injective
1067/// destination.
1068#[inline(never)]
1069#[allow(clippy::too_many_arguments)]
1070unsafe fn replay_tiled<D, S, Apply>(
1071    dst_ptr: *mut D,
1072    dst_base: isize,
1073    src_ptr: *const S,
1074    src_base: isize,
1075    tiles: &PairTiles,
1076    apply: &Apply,
1077    ns_per_element: f64,
1078    exec: Exec<'_>,
1079) where
1080    D: Copy + Send + Sync,
1081    S: Copy + Send + Sync,
1082    Apply: Fn(&mut D, S) + Sync,
1083{
1084    let layout = &tiles.layout;
1085    let rank = layout.rank;
1086    let total = fused_total(layout);
1087    // The plan's rate, not the row: a footprint past the class's L2 pays here too
1088    // (strided-rs#364).
1089    if !crate::cost::is_parallel_at_rate(total, ns_per_element, &exec) {
1090        // SAFETY: forwarded caller contract over the whole box.
1091        unsafe {
1092            apply_tiled_box(
1093                dst_ptr,
1094                dst_base,
1095                src_ptr,
1096                src_base,
1097                layout,
1098                &tiles.blocks,
1099                &mut &*apply,
1100            )
1101        };
1102        return;
1103    }
1104    let strides = [&layout.dst_strides[..rank], &layout.src_strides[..rank]];
1105    let costs = crate::fuse::compute_costs(&strides);
1106    let dst_ptr = crate::threading::SendPtr(dst_ptr);
1107    let src_ptr = crate::threading::SendPtr(src_ptr as *mut S);
1108    #[cfg(test)]
1109    let leaves = std::sync::Mutex::new(Vec::new());
1110    let result = crate::threading::mapreduce_threaded_at_rate(
1111        &layout.dims[..rank],
1112        &tiles.blocks[..rank],
1113        &strides,
1114        &[dst_base, src_base],
1115        &costs,
1116        ns_per_element,
1117        exec,
1118        &|box_dims, _, _, offsets| {
1119            #[cfg(test)]
1120            if let Ok(mut leaves) = leaves.lock() {
1121                leaves.push((offsets[0], offsets[1], box_dims.to_vec()));
1122            }
1123            let mut leaf = *layout;
1124            leaf.dims[..rank].copy_from_slice(box_dims);
1125            // SAFETY: the splitter hands disjoint sub-boxes of `layout` with
1126            // the offsets of their origins, so every logical index of a leaf
1127            // is one of `layout`; the injective destination makes the leaves
1128            // write disjoint slots, and the source is only read.
1129            unsafe {
1130                apply_tiled_box(
1131                    dst_ptr.as_ptr(),
1132                    offsets[0],
1133                    src_ptr.as_const(),
1134                    offsets[1],
1135                    &leaf,
1136                    &tiles.blocks,
1137                    &mut &*apply,
1138                )
1139            };
1140            Ok(())
1141        },
1142    );
1143    // INVARIANT: the splitter fails only on an extent product beyond `usize`,
1144    // which the caller contract excludes, and the leaves never fail.
1145    debug_assert!(result.is_ok());
1146    #[cfg(test)]
1147    crate::threading::record_tiled_leaves(leaves.into_inner().unwrap_or_default());
1148}
1149
1150/// Tiled replay of a spilled axis list: serially one
1151/// [`apply_spilled_tiled_box`] over the whole box, or, when one fork pays, the
1152/// dimension splitter of the view path with one box walk per leaf box.
1153///
1154/// The spilled counterpart of [`replay_tiled`], on the slice-backed
1155/// [`SpilledTiles`]: same splitter, same per-leaf clipping of the model's own
1156/// blocks.
1157///
1158/// # Safety
1159///
1160/// The [`replay_spilled_raw`] contract for `tiles.dims`, with an injective
1161/// destination.
1162#[allow(clippy::too_many_arguments)]
1163#[inline(never)]
1164unsafe fn replay_spilled_tiled<D, S, Apply>(
1165    dst_ptr: *mut D,
1166    dst_base: isize,
1167    src_ptr: *const S,
1168    src_base: isize,
1169    tiles: &SpilledTiles,
1170    mut apply: Apply,
1171    exec: Exec<'_>,
1172    ns_per_element: f64,
1173) where
1174    D: Copy + Send + Sync,
1175    S: Copy + Send + Sync,
1176    Apply: Fn(&mut D, S) + Sync,
1177{
1178    let total = tiles.dims().iter().product::<usize>();
1179    if !crate::cost::is_parallel_at_rate(total, ns_per_element, &exec) {
1180        // SAFETY: forwarded caller contract over the whole box.
1181        unsafe {
1182            apply_spilled_tiled_box(
1183                dst_ptr,
1184                dst_base,
1185                src_ptr,
1186                src_base,
1187                tiles,
1188                tiles.dims(),
1189                &mut apply,
1190            )
1191        };
1192        return;
1193    }
1194    let strides = [tiles.dst(), tiles.src()];
1195    let costs = crate::fuse::compute_costs(&strides);
1196    let dst_ptr = crate::threading::SendPtr(dst_ptr);
1197    let src_ptr = crate::threading::SendPtr(src_ptr as *mut S);
1198    #[cfg(test)]
1199    let leaves = std::sync::Mutex::new(Vec::new());
1200    let result = crate::threading::mapreduce_threaded_at_rate(
1201        tiles.dims(),
1202        tiles.blocks(),
1203        &strides,
1204        &[dst_base, src_base],
1205        &costs,
1206        ns_per_element,
1207        exec,
1208        &|box_dims, _, _, offsets| {
1209            #[cfg(test)]
1210            if let Ok(mut leaves) = leaves.lock() {
1211                leaves.push((offsets[0], offsets[1], box_dims.to_vec()));
1212            }
1213            // SAFETY: the splitter hands disjoint sub-boxes of `tiles.dims`
1214            // with the offsets of their origins, so every logical index of a
1215            // leaf is one of the tiles' slots; the injective destination makes
1216            // the leaves write disjoint slots, and the source is only read.
1217            unsafe {
1218                apply_spilled_tiled_box(
1219                    dst_ptr.as_ptr(),
1220                    offsets[0],
1221                    src_ptr.as_const(),
1222                    offsets[1],
1223                    tiles,
1224                    box_dims,
1225                    &mut &apply,
1226                )
1227            };
1228            Ok(())
1229        },
1230    );
1231    // INVARIANT: the splitter fails only on an extent product beyond `usize`,
1232    // which the caller contract excludes, and the leaves never fail.
1233    debug_assert!(result.is_ok());
1234    #[cfg(test)]
1235    crate::threading::record_tiled_leaves(leaves.into_inner().unwrap_or_default());
1236}
1237
1238/// Pointer-level replay of a spilled axis list.
1239///
1240/// Mirrors [`replay_fused_raw`] including its worker split; kept separate so
1241/// that the inline replay keeps its fixed-rank shape.
1242///
1243/// # Safety
1244///
1245/// The [`replay_fused_raw`] contract, for `axes`.
1246#[allow(clippy::too_many_arguments)]
1247pub(crate) unsafe fn replay_spilled_raw<D, S, Apply>(
1248    dst_ptr: *mut D,
1249    dst_base: isize,
1250    src_ptr: *const S,
1251    src_base: isize,
1252    axes: &[FusedAxis],
1253    mut apply: Apply,
1254    ns_per_element: f64,
1255    exec: Exec<'_>,
1256) where
1257    D: Copy + Send + Sync,
1258    S: Copy + Send + Sync,
1259    Apply: Fn(&mut D, S) + Sync,
1260{
1261    let total = axes.iter().map(|axis| axis.dim).product::<usize>();
1262    if total == 0 {
1263        return;
1264    }
1265    let exec = crate::cost::for_len_at_rate(exec, total, ns_per_element);
1266    if !exec.is_serial() {
1267        let dst_ptr = crate::threading::SendPtr(dst_ptr);
1268        let src_ptr = crate::threading::SendPtr(src_ptr as *mut S);
1269        crate::threading::parallel_for_each(0..total, exec, &|range| {
1270            // SAFETY: as in `replay_fused_raw`: in-bounds indices, injective
1271            // destination for a non-serial token, disjoint worker ranges.
1272            unsafe {
1273                apply_spilled_range(
1274                    dst_ptr.as_ptr(),
1275                    dst_base,
1276                    src_ptr.as_const(),
1277                    src_base,
1278                    axes,
1279                    range.start,
1280                    range.len(),
1281                    &mut &apply,
1282                );
1283            }
1284        });
1285        return;
1286    }
1287    // SAFETY: forwarded caller contract over the full range `0..total`; one
1288    // sequential walk needs no injectivity.
1289    unsafe {
1290        apply_spilled_range(
1291            dst_ptr, dst_base, src_ptr, src_base, axes, 0, total, &mut apply,
1292        );
1293    }
1294}
1295
1296#[cfg(test)]
1297#[path = "copy_plan/tests/tests.rs"]
1298mod tests;
1299
1300#[cfg(test)]
1301#[path = "copy_plan/tests/parallel_tests.rs"]
1302mod parallel_tests;