Skip to main content

strided_basic/
static_indexing_plan.rs

1//! Prepared static-indexing plans over raw strided value layouts.
2//!
3//! This module owns reusable static indexing traversal for downstream tensor
4//! runtimes. It keeps allocation, dtype policy, and tensor-level validation out
5//! of `strided-kernel`; callers provide already-owned output buffers and fixed
6//! raw descriptors.
7
8use core::mem::MaybeUninit;
9
10use crate::cost::KernelClass;
11use crate::raw_ops::PairTiles;
12use crate::{CopyPlan, Exec, RawStridedMut, RawStridedRef, Result, StridedError};
13
14type AxisVec<T> = crate::inline::InlineVec<T>;
15
16/// A compiled static-slice traversal.
17///
18/// `compile` validates the fixed `starts`/`limits`/`slice_strides` contract and
19/// lowers replay to a strided copy from the corresponding source view.
20#[derive(Clone, Debug)]
21pub struct SlicePlan {
22    operand_dims: AxisVec<usize>,
23    operand_strides: AxisVec<isize>,
24    dest_dims: AxisVec<usize>,
25    dest_strides: AxisVec<isize>,
26    source_strides: AxisVec<isize>,
27    source_offset_delta: isize,
28    copy_plan: CopyPlan,
29}
30
31/// A compiled reverse traversal over selected axes.
32///
33/// Replay is a strided copy from a negative-stride source view.
34#[derive(Clone, Debug)]
35pub struct ReversePlan {
36    operand_dims: AxisVec<usize>,
37    operand_strides: AxisVec<isize>,
38    dest_strides: AxisVec<isize>,
39    source_strides: AxisVec<isize>,
40    source_offset_delta: isize,
41    copy_plan: CopyPlan,
42}
43
44/// A compiled pad traversal.
45///
46/// Replay fills every destination element with the caller-provided fill
47/// scalar, then copies reachable input positions into the padded output.
48/// A dense column-major destination with a unit-stride axis-0 operand and
49/// non-negative edges without interior spacing instead writes disjoint spans
50/// (low pad, operand run, high pad) per column so each element is written once.
51#[derive(Clone, Debug)]
52pub struct PadPlan {
53    operand_dims: AxisVec<usize>,
54    operand_strides: AxisVec<isize>,
55    dest_dims: AxisVec<usize>,
56    dest_strides: AxisVec<isize>,
57    edge_padding_low: AxisVec<i64>,
58    interior_step: AxisVec<i64>,
59    operand_total: usize,
60    dest_total: usize,
61    contiguous_dest_fill: bool,
62    contiguous_axis0_run: Option<ContiguousPadAxis0Run>,
63    contiguous_axis0_columns: Option<ContiguousPadAxis0Columns>,
64    generic_fill: PadFillCursor,
65    generic_copy: PadCopyCursor,
66}
67
68#[derive(Clone, Debug)]
69struct PadFillCursor {
70    steps: AxisVec<isize>,
71    resets: AxisVec<isize>,
72}
73
74#[derive(Clone, Debug)]
75struct PadCopyCursor {
76    shape: AxisVec<usize>,
77    source_base_delta: isize,
78    dest_base_delta: isize,
79    source_steps: AxisVec<isize>,
80    source_resets: AxisVec<isize>,
81    dest_steps: AxisVec<isize>,
82    dest_resets: AxisVec<isize>,
83    total: usize,
84}
85
86#[derive(Clone, Copy, Debug, Eq, PartialEq)]
87struct ContiguousPadAxis0Run {
88    operand_start: usize,
89    dest_start: usize,
90    len: usize,
91}
92
93/// Prepared single-pass write for a dense column-major destination whose
94/// axis-0 operand stride is one and whose edges are non-negative with no
95/// interior spacing on any axis.
96///
97/// Replay walks destination columns. Each column writes its low pad, copies
98/// the operand axis-0 run, and writes its high pad; columns with no reachable
99/// operand coordinate write the whole column as padding. Every reachable
100/// destination slot is therefore written exactly once, and the write spans of
101/// distinct columns are disjoint because the destination layout is injective.
102#[derive(Clone, Debug)]
103struct ContiguousPadAxis0Columns {
104    /// Number of destination columns, `dest_dims[0]` elements each.
105    column_total: usize,
106    dest_axis0_len: usize,
107    dest_axis0_step: isize,
108    low0: usize,
109    high0: usize,
110    run_len: usize,
111    operand_outer_dims: AxisVec<usize>,
112    operand_outer_strides: AxisVec<isize>,
113    dest_outer_dims: AxisVec<usize>,
114    edge_low_outer: AxisVec<usize>,
115}
116
117/// A compiled multi-input concatenate traversal.
118///
119/// Each input segment is lowered to a prepared strided copy into the
120/// corresponding destination window. The per-input collections are inline up
121/// to [`OPERAND_CAP`](crate::inline::OPERAND_CAP) slots (destination plus four
122/// inputs), so a bounded concatenate compiles and executes without touching the
123/// heap; above that bound they spill gracefully. `segment_starts` carries one
124/// more entry than there are inputs (the `input_count + 1` prefix-sum sentinel
125/// whose last entry is the destination total), which is why its bound is the
126/// same operand cap.
127#[derive(Clone, Debug)]
128pub struct ConcatenatePlan {
129    input_dims: crate::inline::OperandVec<AxisVec<usize>>,
130    input_strides: crate::inline::OperandVec<AxisVec<isize>>,
131    dest_dims: AxisVec<usize>,
132    dest_strides: AxisVec<isize>,
133    dest_offset_deltas: crate::inline::OperandVec<isize>,
134    /// Logical start of each segment in the concatenated index space
135    /// (segment totals prefix sums); the last entry is the destination total.
136    segment_starts: crate::inline::OperandVec<usize>,
137    copy_plans: crate::inline::OperandVec<CopyPlan>,
138    /// Whether any segment can tile for some element types
139    /// ([`CopyPlan::may_tile`]). Without one, the whole-plan replay is the flat
140    /// split of the concatenated index space and asks no tiling question.
141    may_tile: bool,
142}
143
144impl SlicePlan {
145    /// Compile a static slice plan for one operand layout and destination layout.
146    ///
147    /// # Errors
148    ///
149    /// Returns [`StridedError::StrideLengthMismatch`] when the operand or
150    /// destination layout lengths differ from the operand rank, and
151    /// [`StridedError::RankMismatch`] when `starts`, `limits` or
152    /// `slice_strides` differ from it. Returns
153    /// [`StridedError::InvalidAxis`] for a window with `start > limit`, a
154    /// `limit` beyond the extent, or a zero slice stride, and
155    /// [`StridedError::ShapeMismatch`] when the destination dims are not the
156    /// sliced extents. Returns [`StridedError::NonInjectiveOutputLayout`]
157    /// when two destination elements map onto one offset or the layout span is
158    /// not representable, and
159    /// [`StridedError::OffsetOverflow`] when an element count, a scaled
160    /// source stride, or the source offset delta overflows.
161    // The plan compile takes the operand and destination layouts plus the three
162    // slice vectors; splitting it would only move the argument list.
163    #[allow(clippy::too_many_arguments)]
164    pub fn compile(
165        operand_dims: &[usize],
166        operand_strides: &[isize],
167        dest_dims: &[usize],
168        dest_strides: &[isize],
169        starts: &[usize],
170        limits: &[usize],
171        slice_strides: &[usize],
172    ) -> Result<Self> {
173        let rank = operand_dims.len();
174        if operand_strides.len() != rank || dest_dims.len() != rank || dest_strides.len() != rank {
175            return Err(StridedError::StrideLengthMismatch);
176        }
177        if starts.len() != rank {
178            return Err(StridedError::RankMismatch(starts.len(), rank));
179        }
180        if limits.len() != rank {
181            return Err(StridedError::RankMismatch(limits.len(), rank));
182        }
183        if slice_strides.len() != rank {
184            return Err(StridedError::RankMismatch(slice_strides.len(), rank));
185        }
186        checked_total_len(operand_dims)?;
187        checked_total_len(dest_dims)?;
188
189        let mut expected_dest_dims: AxisVec<usize> = AxisVec::with_capacity(rank);
190        let mut source_strides: AxisVec<isize> = AxisVec::with_capacity(rank);
191        let mut source_offset_delta = 0isize;
192        for axis in 0..rank {
193            let start = starts[axis];
194            let limit = limits[axis];
195            let stride = slice_strides[axis];
196            if start > limit || limit > operand_dims[axis] || stride == 0 {
197                return Err(StridedError::InvalidAxis { axis, rank });
198            }
199            let span = limit - start;
200            expected_dest_dims.push(span.div_ceil(stride));
201            source_strides.push(checked_stride_mul(operand_strides[axis], stride)?);
202            source_offset_delta =
203                checked_offset_add(source_offset_delta, operand_strides[axis], start)?;
204        }
205        if dest_dims != &expected_dest_dims[..] {
206            return Err(StridedError::ShapeMismatch(
207                dest_dims.to_vec(),
208                expected_dest_dims.to_vec(),
209            ));
210        }
211        let copy_plan = CopyPlan::compile(dest_dims, dest_strides, &source_strides)?;
212
213        Ok(Self {
214            operand_dims: operand_dims.into(),
215            operand_strides: operand_strides.into(),
216            dest_dims: dest_dims.into(),
217            dest_strides: dest_strides.into(),
218            source_strides,
219            source_offset_delta,
220            copy_plan,
221        })
222    }
223
224    /// Execute the prepared static slice traversal.
225    ///
226    /// # Errors
227    ///
228    /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
229    /// carry the compiled operand and destination layouts, and
230    /// [`StridedError::OffsetOverflow`] when the operand offset plus the
231    /// compiled source offset delta overflows.
232    pub fn execute<T>(
233        &self,
234        dest: &mut RawStridedMut<'_, T>,
235        operand: &RawStridedRef<'_, T>,
236        exec: Exec<'_>,
237    ) -> Result<()>
238    where
239        T: Copy + Send + Sync,
240    {
241        self.check_call(dest, operand)?;
242        let source_offset = operand
243            .offset()
244            .checked_add(self.source_offset_delta)
245            .ok_or(StridedError::OffsetOverflow)?;
246        // SAFETY: `SlicePlan::compile` (:159) rejected every window outside the
247        // operand (`start > limit || limit > operand_dims[axis]`, :191), built
248        // `source_strides`/`source_offset_delta` with checked arithmetic and required
249        // `dest_dims == span.div_ceil(stride)`, so each index this view can reach is
250        // an index the operand already reaches; `check_call` (:301) re-proved the
251        // operand carries the compiled layout, its offsets were validated by
252        // `validate_bounds` (strided-view/src/view.rs:187) in `RawStridedRef::new`
253        // (strided-view/src/raw.rs:917), and the delta sum above is checked.
254        let source = unsafe {
255            RawStridedRef::new_unchecked(
256                operand.data(),
257                &self.dest_dims,
258                &self.source_strides,
259                source_offset,
260            )
261        };
262        self.copy_plan.execute(dest, &source, exec)
263    }
264
265    /// Execute into storage whose reachable destination elements are uninitialized.
266    ///
267    /// # Errors
268    ///
269    /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
270    /// carry the compiled operand and destination layouts, and
271    /// [`StridedError::OffsetOverflow`] when the operand offset plus the
272    /// compiled source offset delta overflows.
273    pub fn execute_uninit<T>(
274        &self,
275        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
276        operand: &RawStridedRef<'_, T>,
277        exec: Exec<'_>,
278    ) -> Result<()>
279    where
280        T: Copy + Send + Sync,
281    {
282        self.check_call(dest, operand)?;
283        let source_offset = operand
284            .offset()
285            .checked_add(self.source_offset_delta)
286            .ok_or(StridedError::OffsetOverflow)?;
287        // SAFETY: `SlicePlan::compile` (:159) rejected every window outside the
288        // operand (`start > limit || limit > operand_dims[axis]`, :191), built
289        // `source_strides`/`source_offset_delta` with checked arithmetic and required
290        // `dest_dims == span.div_ceil(stride)`, so each index this view can reach is
291        // an index the operand already reaches; `check_call` (:301) re-proved the
292        // operand carries the compiled layout, its offsets were validated by
293        // `validate_bounds` (strided-view/src/view.rs:187) in `RawStridedRef::new`
294        // (strided-view/src/raw.rs:917), and the delta sum above is checked.
295        let source = unsafe {
296            RawStridedRef::new_unchecked(
297                operand.data(),
298                &self.dest_dims,
299                &self.source_strides,
300                source_offset,
301            )
302        };
303        self.copy_plan.execute_uninit(dest, &source, exec)
304    }
305
306    fn check_call<D, T>(
307        &self,
308        dest: &RawStridedMut<'_, D>,
309        operand: &RawStridedRef<'_, T>,
310    ) -> Result<()> {
311        if operand.dims() != &self.operand_dims[..]
312            || operand.strides() != &self.operand_strides[..]
313            || dest.dims() != &self.dest_dims[..]
314            || dest.strides() != &self.dest_strides[..]
315        {
316            return Err(StridedError::PlanLayoutMismatch);
317        }
318        Ok(())
319    }
320}
321
322impl PadPlan {
323    /// Compile a pad plan for one operand layout and destination layout.
324    ///
325    /// # Errors
326    ///
327    /// Returns [`StridedError::StrideLengthMismatch`] when the operand or
328    /// destination layout lengths differ from the operand rank, and
329    /// [`StridedError::RankMismatch`] when the edge or interior padding
330    /// lengths differ from it. Returns [`StridedError::InvalidAxis`] for a
331    /// negative interior padding or a padded extent that does not fit
332    /// `usize`, [`StridedError::ShapeMismatch`] when the destination dims are
333    /// not the padded extents, and
334    /// [`StridedError::NonInjectiveOutputLayout`] when two destination
335    /// elements map onto one offset, or the layout span is not representable.
336    /// Returns
337    /// [`StridedError::OffsetOverflow`] when an element count, a padded
338    /// extent or a cursor stride computation overflows.
339    // Same shape as `SlicePlan::compile`: two layouts plus the three padding
340    // vectors; a wrapper type would hide the layout contract at the call site.
341    #[allow(clippy::too_many_arguments)]
342    pub fn compile(
343        operand_dims: &[usize],
344        operand_strides: &[isize],
345        dest_dims: &[usize],
346        dest_strides: &[isize],
347        edge_padding_low: &[i64],
348        edge_padding_high: &[i64],
349        interior_padding: &[i64],
350    ) -> Result<Self> {
351        let rank = operand_dims.len();
352        if operand_strides.len() != rank || dest_dims.len() != rank || dest_strides.len() != rank {
353            return Err(StridedError::StrideLengthMismatch);
354        }
355        if edge_padding_low.len() != rank {
356            return Err(StridedError::RankMismatch(edge_padding_low.len(), rank));
357        }
358        if edge_padding_high.len() != rank {
359            return Err(StridedError::RankMismatch(edge_padding_high.len(), rank));
360        }
361        if interior_padding.len() != rank {
362            return Err(StridedError::RankMismatch(interior_padding.len(), rank));
363        }
364
365        let operand_total = checked_total_len(operand_dims)?;
366        let dest_total = checked_total_len(dest_dims)?;
367        if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
368            return Err(StridedError::NonInjectiveOutputLayout);
369        }
370
371        let mut expected_dest_dims: AxisVec<usize> = AxisVec::with_capacity(rank);
372        let mut interior_step: AxisVec<i64> = AxisVec::with_capacity(rank);
373        for axis in 0..rank {
374            if interior_padding[axis] < 0 {
375                return Err(StridedError::InvalidAxis { axis, rank });
376            }
377            let step = interior_padding[axis]
378                .checked_add(1)
379                .ok_or(StridedError::OffsetOverflow)?;
380            interior_step.push(step);
381            expected_dest_dims.push(checked_pad_output_dim(
382                operand_dims[axis],
383                edge_padding_low[axis],
384                edge_padding_high[axis],
385                step,
386                axis,
387                rank,
388            )?);
389        }
390        if dest_dims != &expected_dest_dims[..] {
391            return Err(StridedError::ShapeMismatch(
392                dest_dims.to_vec(),
393                expected_dest_dims.to_vec(),
394            ));
395        }
396        let contiguous_dest_fill = is_dense_col_major(dest_dims, dest_strides);
397        let contiguous_axis0_run = compile_contiguous_pad_axis0_run(
398            operand_dims,
399            operand_strides,
400            dest_dims,
401            dest_strides,
402            edge_padding_low,
403            &interior_step,
404        );
405        let contiguous_axis0_columns = contiguous_axis0_run.and_then(|run| {
406            compile_contiguous_pad_axis0_columns(
407                operand_dims,
408                operand_strides,
409                dest_dims,
410                edge_padding_low,
411                edge_padding_high,
412                &interior_step,
413                contiguous_dest_fill,
414                run,
415            )
416        });
417        let generic_fill = compile_pad_fill_cursor(dest_dims, dest_strides)?;
418        let generic_copy = compile_pad_copy_cursor(
419            operand_dims,
420            operand_strides,
421            dest_dims,
422            dest_strides,
423            edge_padding_low,
424            &interior_step,
425        )?;
426
427        Ok(Self {
428            operand_dims: operand_dims.into(),
429            operand_strides: operand_strides.into(),
430            dest_dims: dest_dims.into(),
431            dest_strides: dest_strides.into(),
432            edge_padding_low: edge_padding_low.into(),
433            interior_step,
434            operand_total,
435            dest_total,
436            contiguous_dest_fill,
437            contiguous_axis0_run,
438            contiguous_axis0_columns,
439            generic_fill,
440            generic_copy,
441        })
442    }
443
444    /// Execute the prepared pad traversal.
445    ///
446    /// # Errors
447    ///
448    /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
449    /// carry the compiled operand and destination layouts, and
450    /// [`StridedError::OffsetOverflow`] when the destination base offset or
451    /// its contiguous fill span cannot be expressed in `usize`.
452    pub fn execute<T>(
453        &self,
454        dest: &mut RawStridedMut<'_, T>,
455        operand: &RawStridedRef<'_, T>,
456        fill: T,
457        exec: Exec<'_>,
458    ) -> Result<()>
459    where
460        T: Copy + Send + Sync,
461    {
462        let mut exec = exec;
463        self.check_call(dest, operand)?;
464        if self.operand_total == 0 {
465            return self.fill_dest(dest, fill, exec);
466        }
467        if let Some(columns) = &self.contiguous_axis0_columns {
468            return self.execute_axis0_columns(dest, operand, fill, columns, exec);
469        }
470        self.fill_dest(dest, fill, exec.reborrow())?;
471        if let Some(run) = self.contiguous_axis0_run {
472            return self.copy_operand_axis0_runs(dest, operand, run, exec);
473        }
474        self.copy_operand(dest, operand, exec)
475    }
476
477    /// Execute pad into storage whose reachable destination elements are uninitialized.
478    ///
479    /// # Errors
480    ///
481    /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
482    /// carry the compiled operand and destination layouts, and
483    /// [`StridedError::OffsetOverflow`] when the destination base offset or
484    /// its contiguous fill span cannot be expressed in `usize`.
485    pub fn execute_uninit<T>(
486        &self,
487        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
488        operand: &RawStridedRef<'_, T>,
489        fill: T,
490        exec: Exec<'_>,
491    ) -> Result<()>
492    where
493        T: Copy + Send + Sync,
494    {
495        let mut exec = exec;
496        self.check_call(dest, operand)?;
497        if self.operand_total == 0 {
498            return self.fill_dest(dest, MaybeUninit::new(fill), exec);
499        }
500        if let Some(columns) = &self.contiguous_axis0_columns {
501            return self.execute_axis0_columns_uninit(dest, operand, fill, columns, exec);
502        }
503        self.fill_dest(dest, MaybeUninit::new(fill), exec.reborrow())?;
504        if let Some(run) = self.contiguous_axis0_run {
505            return self.copy_operand_axis0_runs_uninit(dest, operand, run, exec);
506        }
507        self.copy_operand_uninit(dest, operand, exec)
508    }
509
510    fn fill_dest<T>(&self, dest: &mut RawStridedMut<'_, T>, fill: T, exec: Exec<'_>) -> Result<()>
511    where
512        T: Copy + Send + Sync,
513    {
514        if self.dest_total == 0 {
515            return Ok(());
516        }
517        if self.contiguous_dest_fill {
518            let dest_offset =
519                usize::try_from(dest.offset()).map_err(|_| StridedError::OffsetOverflow)?;
520            let dest_end = dest_offset
521                .checked_add(self.dest_total)
522                .ok_or(StridedError::OffsetOverflow)?;
523            let dest_data = dest.data_mut();
524            let dest_slice = dest_data
525                .get_mut(dest_offset..dest_end)
526                .ok_or(StridedError::OffsetOverflow)?;
527            crate::threading::fill_contiguous(dest_slice, fill, exec);
528            return Ok(());
529        }
530        let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.dest_total);
531        if !exec.is_serial() {
532            return self.fill_dest_parallel(dest, fill, exec);
533        }
534        self.fill_dest_serial(dest, fill)
535    }
536
537    fn copy_operand_axis0_runs<T>(
538        &self,
539        dest: &mut RawStridedMut<'_, T>,
540        operand: &RawStridedRef<'_, T>,
541        run: ContiguousPadAxis0Run,
542        exec: Exec<'_>,
543    ) -> Result<()>
544    where
545        T: Copy + Send + Sync,
546    {
547        let dest_offset = dest.offset();
548        let dest_ptr = dest.data_mut().as_mut_ptr();
549        // SAFETY: `check_call` proved `dest` carries the compiled destination
550        // layout, so its validated data covers every reachable destination
551        // slot, and the exclusive borrow is the only access during the call.
552        unsafe { self.copy_axis0_runs_raw(dest_ptr, dest_offset, operand, run, exec) }
553    }
554
555    fn copy_operand_axis0_runs_uninit<T>(
556        &self,
557        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
558        operand: &RawStridedRef<'_, T>,
559        run: ContiguousPadAxis0Run,
560        exec: Exec<'_>,
561    ) -> Result<()>
562    where
563        T: Copy + Send + Sync,
564    {
565        let dest_offset = dest.offset();
566        let dest_ptr = dest.data_mut().as_mut_ptr().cast::<T>();
567        // SAFETY: as in `copy_operand_axis0_runs`; `MaybeUninit<T>` has the
568        // layout of `T`, and only writes go through the cast pointer.
569        unsafe { self.copy_axis0_runs_raw(dest_ptr, dest_offset, operand, run, exec) }
570    }
571
572    fn execute_axis0_columns<T>(
573        &self,
574        dest: &mut RawStridedMut<'_, T>,
575        operand: &RawStridedRef<'_, T>,
576        fill: T,
577        columns: &ContiguousPadAxis0Columns,
578        exec: Exec<'_>,
579    ) -> Result<()>
580    where
581        T: Copy + Send + Sync,
582    {
583        let dest_offset = dest.offset();
584        let dest_ptr = dest.data_mut().as_mut_ptr();
585        let operand_offset = operand.offset();
586        let operand_ptr = operand.data().as_ptr();
587        // SAFETY: `check_call` proved `dest` carries the compiled destination
588        // layout, so its validated data covers every reachable destination
589        // slot, and the exclusive borrow is the only access during the call.
590        unsafe {
591            self.write_axis0_columns_raw::<T, false>(
592                dest_ptr,
593                dest_offset,
594                operand_ptr,
595                operand_offset,
596                fill,
597                columns,
598                exec,
599            )
600        }
601    }
602
603    fn execute_axis0_columns_uninit<T>(
604        &self,
605        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
606        operand: &RawStridedRef<'_, T>,
607        fill: T,
608        columns: &ContiguousPadAxis0Columns,
609        exec: Exec<'_>,
610    ) -> Result<()>
611    where
612        T: Copy + Send + Sync,
613    {
614        let dest_offset = dest.offset();
615        let dest_ptr = dest.data_mut().as_mut_ptr().cast::<T>();
616        let operand_offset = operand.offset();
617        let operand_ptr = operand.data().as_ptr();
618        // SAFETY: as in `execute_axis0_columns`; `MaybeUninit<T>` has the
619        // layout of `T`, and only writes go through the cast pointer.
620        unsafe {
621            self.write_axis0_columns_raw::<T, true>(
622                dest_ptr,
623                dest_offset,
624                operand_ptr,
625                operand_offset,
626                fill,
627                columns,
628                exec,
629            )
630        }
631    }
632
633    /// Write every destination column as disjoint low-pad, operand-run, and
634    /// high-pad spans.
635    ///
636    /// With at least as many columns as workers (above the repository
637    /// threshold) the columns are split across workers; otherwise columns run
638    /// in order and each long span is chunked across workers by
639    /// [`crate::threading::copy_contiguous`] and
640    /// [`crate::threading::fill_contiguous`].
641    ///
642    /// # Safety
643    ///
644    /// `dest_ptr` and `operand_ptr` must be the data pointers of descriptors
645    /// whose layouts are exactly the compiled layouts from `dest_offset` and
646    /// `operand_offset`. The destination must be writable at every reachable
647    /// slot and no other access may overlap the call; the operand may only be
648    /// read at coordinates that are copied, but no read is performed for a
649    /// padding-only column.
650    // Whole-plan entry for the column write: both base pointers with their offsets,
651    // the fill value and the compiled column plan, handed to
652    // `write_axis0_columns_range` per worker range. The argument list is that plan
653    // forwarded, not a per-column invocation.
654    #[allow(clippy::too_many_arguments)]
655    unsafe fn write_axis0_columns_raw<T, const UNINIT: bool>(
656        &self,
657        dest_ptr: *mut T,
658        dest_offset: isize,
659        operand_ptr: *const T,
660        operand_offset: isize,
661        fill: T,
662        columns: &ContiguousPadAxis0Columns,
663        exec: Exec<'_>,
664    ) -> Result<()>
665    where
666        T: Copy + Send + Sync,
667    {
668        let column_total = columns.column_total;
669        if column_total == 0 {
670            return Ok(());
671        }
672        let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.dest_total);
673        {
674            if exec.budget().get() > 1 && column_total >= exec.budget().get() {
675                let dest_ptr = crate::threading::SendPtr(dest_ptr);
676                let operand_ptr = crate::threading::SendPtr(operand_ptr as *mut T);
677                return crate::threading::parallel_map_reduce(
678                    0..column_total,
679                    exec,
680                    &|range| {
681                        let mut outer_idx_storage =
682                            CoordScratch::new(columns.dest_outer_dims.len());
683                        let outer_idx = outer_idx_storage.as_mut_slice();
684                        fill_col_major_index(range.start, &columns.dest_outer_dims, outer_idx);
685                        // SAFETY: worker ranges are disjoint; the destination
686                        // is dense column-major, so distinct columns occupy
687                        // disjoint contiguous slots, and the caller's contract
688                        // covers every reachable slot. Padding-only columns
689                        // never read the operand.
690                        unsafe {
691                            self.write_axis0_columns_range::<T, UNINIT>(
692                                dest_ptr.as_ptr(),
693                                dest_offset,
694                                operand_ptr.as_const(),
695                                operand_offset,
696                                fill,
697                                columns,
698                                outer_idx,
699                                range.start,
700                                range.len(),
701                                Exec::serial(),
702                            )
703                        }
704                    },
705                    &|left, right| left.and(right),
706                );
707            }
708        }
709        let mut outer_idx_storage = CoordScratch::new(columns.dest_outer_dims.len());
710        let outer_idx = outer_idx_storage.as_mut_slice();
711        // SAFETY: forwarded from this function's contract.
712        unsafe {
713            self.write_axis0_columns_range::<T, UNINIT>(
714                dest_ptr,
715                dest_offset,
716                operand_ptr,
717                operand_offset,
718                fill,
719                columns,
720                outer_idx,
721                0,
722                column_total,
723                exec,
724            )
725        }
726    }
727
728    /// Write `count` destination columns starting at linear column
729    /// `column_start`, advancing `outer_idx` in place.
730    ///
731    /// # Safety
732    ///
733    /// As for [`Self::write_axis0_columns_raw`], and no other thread may write
734    /// the destination columns visited by this call.
735    // Per-range sibling of `write_axis0_columns_raw`, same arguments plus the range.
736    #[allow(clippy::too_many_arguments)]
737    unsafe fn write_axis0_columns_range<T, const UNINIT: bool>(
738        &self,
739        dest_ptr: *mut T,
740        dest_offset: isize,
741        operand_ptr: *const T,
742        operand_offset: isize,
743        fill: T,
744        columns: &ContiguousPadAxis0Columns,
745        outer_idx: &mut [usize],
746        column_start: usize,
747        count: usize,
748        mut exec: Exec<'_>,
749    ) -> Result<()>
750    where
751        T: Copy + Send + Sync,
752    {
753        if count == 0 {
754            return Ok(());
755        }
756        let mut dest_column_offset =
757            checked_offset_add(dest_offset, columns.dest_axis0_step, column_start)?;
758        // Carry the operand column offset and in-bounds count through the outer
759        // odometer instead of rescanning every outer axis per column. Only axes
760        // currently in bounds contribute a `stride * q` term, so every product
761        // is one the validated operand layout already produced.
762        let mut operand_column_offset = operand_offset;
763        let mut out_of_bounds = 0usize;
764        for (axis, &coord) in outer_idx.iter().enumerate() {
765            match in_bounds_outer_coord(columns, axis, coord) {
766                Some(q) => {
767                    operand_column_offset = checked_offset_add(
768                        operand_column_offset,
769                        columns.operand_outer_strides[axis],
770                        q,
771                    )?;
772                }
773                None => out_of_bounds += 1,
774            }
775        }
776        for _ in 0..count {
777            if out_of_bounds == 0 {
778                let low_len = columns.low0;
779                let run_len = columns.run_len;
780                let high_len = columns.high0;
781                // SAFETY: the compiled run span and the dense column layout
782                // place the low pad, operand run, and high pad at disjoint
783                // offsets inside this column; the operand run was validated by
784                // the descriptor bounds and `run_len` copies only in-bounds
785                // axis-0 elements. The destination layout is injective and
786                // this call owns the whole column.
787                unsafe {
788                    if UNINIT {
789                        fill_raw_span_uninit(
790                            dest_ptr.offset(dest_column_offset),
791                            low_len,
792                            fill,
793                            exec.reborrow(),
794                        );
795                    } else {
796                        fill_raw_span(
797                            dest_ptr.offset(dest_column_offset),
798                            low_len,
799                            fill,
800                            exec.reborrow(),
801                        );
802                    }
803                    crate::threading::copy_contiguous(
804                        operand_ptr.offset(operand_column_offset),
805                        dest_ptr.offset(dest_column_offset + low_len as isize),
806                        run_len,
807                        exec.reborrow(),
808                    );
809                    if UNINIT {
810                        fill_raw_span_uninit(
811                            dest_ptr
812                                .offset(dest_column_offset + low_len as isize + run_len as isize),
813                            high_len,
814                            fill,
815                            exec.reborrow(),
816                        );
817                    } else {
818                        fill_raw_span(
819                            dest_ptr
820                                .offset(dest_column_offset + low_len as isize + run_len as isize),
821                            high_len,
822                            fill,
823                            exec.reborrow(),
824                        );
825                    }
826                }
827            } else {
828                // SAFETY: as for the in-bounds branch; a padding-only column
829                // never reads the operand.
830                unsafe {
831                    if UNINIT {
832                        fill_raw_span_uninit(
833                            dest_ptr.offset(dest_column_offset),
834                            columns.dest_axis0_len,
835                            fill,
836                            exec.reborrow(),
837                        );
838                    } else {
839                        fill_raw_span(
840                            dest_ptr.offset(dest_column_offset),
841                            columns.dest_axis0_len,
842                            fill,
843                            exec.reborrow(),
844                        );
845                    }
846                }
847            }
848            // Advance the destination column, the outer odometer, and the
849            // incremental operand offset / in-bounds count together.
850            dest_column_offset = dest_column_offset
851                .checked_add(columns.dest_axis0_step)
852                .ok_or(StridedError::OffsetOverflow)?;
853            for (axis, coord) in outer_idx.iter_mut().enumerate() {
854                let was_in_bounds = in_bounds_outer_coord(columns, axis, *coord);
855                if let Some(q) = was_in_bounds {
856                    let q = isize::try_from(q).map_err(|_| StridedError::OffsetOverflow)?;
857                    let scaled = columns.operand_outer_strides[axis]
858                        .checked_mul(q)
859                        .ok_or(StridedError::OffsetOverflow)?;
860                    operand_column_offset = operand_column_offset
861                        .checked_sub(scaled)
862                        .ok_or(StridedError::OffsetOverflow)?;
863                }
864                *coord += 1;
865                let wrapped = *coord >= columns.dest_outer_dims[axis];
866                if wrapped {
867                    *coord = 0;
868                }
869                let is_in_bounds = in_bounds_outer_coord(columns, axis, *coord);
870                if let Some(q) = is_in_bounds {
871                    operand_column_offset = checked_offset_add(
872                        operand_column_offset,
873                        columns.operand_outer_strides[axis],
874                        q,
875                    )?;
876                }
877                match (was_in_bounds.is_some(), is_in_bounds.is_some()) {
878                    (false, true) => out_of_bounds -= 1,
879                    (true, false) => out_of_bounds += 1,
880                    _ => {}
881                }
882                if !wrapped {
883                    break;
884                }
885            }
886        }
887        Ok(())
888    }
889
890    /// Copy every in-bounds axis-0 run of the operand into the destination.
891    ///
892    /// With at least as many runs as workers (above the repository
893    /// threshold) the runs are split across workers; otherwise runs are
894    /// copied in order and each long run is chunked across workers by
895    /// [`crate::threading::copy_contiguous`].
896    ///
897    /// # Safety
898    ///
899    /// `dest_ptr` must be the data pointer of a destination whose layout is
900    /// exactly the compiled destination layout from `dest_offset`, valid for
901    /// writes to every reachable slot, with no concurrent access.
902    unsafe fn copy_axis0_runs_raw<T>(
903        &self,
904        dest_ptr: *mut T,
905        dest_offset: isize,
906        operand: &RawStridedRef<'_, T>,
907        run: ContiguousPadAxis0Run,
908        exec: Exec<'_>,
909    ) -> Result<()>
910    where
911        T: Copy + Send + Sync,
912    {
913        if run.len == 0 {
914            return Ok(());
915        }
916        let outer_dims = &self.operand_dims[1..];
917        let outer_total = checked_total_len(outer_dims)?;
918        let copied = outer_total.saturating_mul(run.len);
919        let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, copied);
920        {
921            if exec.budget().get() > 1 && outer_total >= exec.budget().get() {
922                let dest_ptr = crate::threading::SendPtr(dest_ptr);
923                return crate::threading::parallel_map_reduce(
924                    0..outer_total,
925                    exec,
926                    &|range| {
927                        let mut outer_idx_storage = CoordScratch::new(outer_dims.len());
928                        let outer_idx = outer_idx_storage.as_mut_slice();
929                        fill_col_major_index(range.start, outer_dims, outer_idx);
930                        // SAFETY: the caller's contract covers every run, and
931                        // disjoint outer ranges write disjoint runs because the
932                        // compiled destination layout is injective.
933                        unsafe {
934                            self.copy_axis0_run_range(
935                                dest_ptr.as_ptr(),
936                                dest_offset,
937                                operand,
938                                run,
939                                outer_idx,
940                                range.len(),
941                                Exec::serial(),
942                            )
943                        }
944                    },
945                    &|left, right| left.and(right),
946                );
947            }
948        }
949        let mut outer_idx_storage = CoordScratch::new(outer_dims.len());
950        let outer_idx = outer_idx_storage.as_mut_slice();
951        // SAFETY: forwarded from this function's contract.
952        unsafe {
953            self.copy_axis0_run_range(
954                dest_ptr,
955                dest_offset,
956                operand,
957                run,
958                outer_idx,
959                outer_total,
960                exec,
961            )
962        }
963    }
964
965    /// Copy `count` consecutive axis-0 runs starting at outer coordinate
966    /// `outer_idx` (column-major over axes `1..`), advancing it in place.
967    ///
968    /// # Safety
969    ///
970    /// As for [`Self::copy_axis0_runs_raw`], and no other thread may write the
971    /// destination runs visited by this call.
972    // Run-copy leaf: both bases, the compiled run, the outer index, the count and the
973    // token.
974    #[allow(clippy::too_many_arguments)]
975    unsafe fn copy_axis0_run_range<T>(
976        &self,
977        dest_ptr: *mut T,
978        dest_offset: isize,
979        operand: &RawStridedRef<'_, T>,
980        run: ContiguousPadAxis0Run,
981        outer_idx: &mut [usize],
982        count: usize,
983        mut exec: Exec<'_>,
984    ) -> Result<()>
985    where
986        T: Copy + Send + Sync,
987    {
988        let outer_dims = &self.operand_dims[1..];
989        let operand_ptr = operand.data().as_ptr();
990        for _ in 0..count {
991            let mut operand_offset =
992                checked_offset_add(operand.offset(), self.operand_strides[0], run.operand_start)?;
993            let mut dest_run_offset =
994                checked_offset_add(dest_offset, self.dest_strides[0], run.dest_start)?;
995            let mut in_bounds = true;
996            for (outer_axis, &coord) in outer_idx.iter().enumerate() {
997                let axis = outer_axis + 1;
998                let out_pos = i128::from(self.edge_padding_low[axis])
999                    + coord as i128 * i128::from(self.interior_step[axis]);
1000                if out_pos < 0 || out_pos >= self.dest_dims[axis] as i128 {
1001                    in_bounds = false;
1002                    break;
1003                }
1004                operand_offset =
1005                    checked_offset_add(operand_offset, self.operand_strides[axis], coord)?;
1006                dest_run_offset =
1007                    checked_offset_add(dest_run_offset, self.dest_strides[axis], out_pos as usize)?;
1008            }
1009            if in_bounds {
1010                // SAFETY: compile requires unit axis-0 strides, the clipped
1011                // run is in bounds of the validated operand and destination,
1012                // and the destination layout is injective. RawStridedMut's
1013                // exclusive borrow cannot overlap the RawStridedRef's shared
1014                // borrow in safe Rust.
1015                unsafe {
1016                    crate::threading::copy_contiguous(
1017                        operand_ptr.offset(operand_offset),
1018                        dest_ptr.offset(dest_run_offset),
1019                        run.len,
1020                        exec.reborrow(),
1021                    );
1022                }
1023            }
1024            advance_col_major_index(outer_idx, outer_dims);
1025        }
1026        Ok(())
1027    }
1028
1029    #[cfg(test)]
1030    fn contiguous_axis0_run(&self) -> Option<(usize, usize, usize)> {
1031        self.contiguous_axis0_run
1032            .map(|run| (run.operand_start, run.dest_start, run.len))
1033    }
1034
1035    #[cfg(test)]
1036    fn has_contiguous_dest_fill(&self) -> bool {
1037        self.contiguous_dest_fill
1038    }
1039
1040    #[cfg(test)]
1041    fn has_contiguous_axis0_columns(&self) -> bool {
1042        self.contiguous_axis0_columns.is_some()
1043    }
1044
1045    fn fill_dest_serial<T>(&self, dest: &mut RawStridedMut<'_, T>, fill: T) -> Result<()>
1046    where
1047        T: Copy,
1048    {
1049        let dest_ptr = dest.data_mut().as_mut_ptr();
1050        let mut cursor = PadFillState::new(dest.offset(), &self.dest_dims, &self.generic_fill);
1051        for _ in 0..self.dest_total {
1052            unsafe {
1053                // INVARIANT: compile-time checked fill spans, validated raw
1054                // descriptors, and exact plan-layout equality prove this is a
1055                // reachable destination offset.
1056                *dest_ptr.offset(cursor.offset) = fill;
1057            }
1058            cursor.advance(&self.dest_dims, &self.generic_fill);
1059        }
1060        Ok(())
1061    }
1062
1063    fn fill_dest_parallel<T>(
1064        &self,
1065        dest: &mut RawStridedMut<'_, T>,
1066        fill: T,
1067        exec: Exec<'_>,
1068    ) -> Result<()>
1069    where
1070        T: Copy + Send + Sync,
1071    {
1072        let dest_offset_base = dest.offset();
1073        let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1074        crate::threading::parallel_map_reduce(
1075            0..self.dest_total,
1076            exec,
1077            &|range| {
1078                let mut cursor = PadFillState::decode(
1079                    range.start,
1080                    dest_offset_base,
1081                    &self.dest_dims,
1082                    &self.generic_fill,
1083                )?;
1084                let dest_ptr = dest_ptr.as_ptr();
1085                for _ in range {
1086                    unsafe {
1087                        // INVARIANT: compile-time checked fill spans, validated
1088                        // raw descriptors, exact layout equality, and disjoint
1089                        // positive logical partition mapping prove this offset
1090                        // is reachable and uniquely owned by this range.
1091                        *dest_ptr.offset(cursor.offset) = fill;
1092                    }
1093                    cursor.advance(&self.dest_dims, &self.generic_fill);
1094                }
1095                Ok(())
1096            },
1097            &|left, right| left.and(right),
1098        )
1099    }
1100
1101    fn copy_operand<T>(
1102        &self,
1103        dest: &mut RawStridedMut<'_, T>,
1104        operand: &RawStridedRef<'_, T>,
1105        exec: Exec<'_>,
1106    ) -> Result<()>
1107    where
1108        T: Copy + Send + Sync,
1109    {
1110        let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.generic_copy.total);
1111        if !exec.is_serial() {
1112            return self.copy_operand_parallel(dest, operand, exec);
1113        }
1114        self.copy_operand_serial(dest, operand)
1115    }
1116
1117    fn copy_operand_uninit<T>(
1118        &self,
1119        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1120        operand: &RawStridedRef<'_, T>,
1121        exec: Exec<'_>,
1122    ) -> Result<()>
1123    where
1124        T: Copy + Send + Sync,
1125    {
1126        let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.generic_copy.total);
1127        if !exec.is_serial() {
1128            return self.copy_operand_uninit_parallel(dest, operand, exec);
1129        }
1130        self.copy_operand_uninit_serial(dest, operand)
1131    }
1132
1133    fn copy_operand_uninit_serial<T>(
1134        &self,
1135        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1136        operand: &RawStridedRef<'_, T>,
1137    ) -> Result<()>
1138    where
1139        T: Copy,
1140    {
1141        if self.generic_copy.total == 0 {
1142            return Ok(());
1143        }
1144        let operand_ptr = operand.data().as_ptr();
1145        let dest_ptr = dest.data_mut().as_mut_ptr();
1146        let source_base = operand
1147            .offset()
1148            .checked_add(self.generic_copy.source_base_delta)
1149            .ok_or(StridedError::OffsetOverflow)?;
1150        let dest_base = dest
1151            .offset()
1152            .checked_add(self.generic_copy.dest_base_delta)
1153            .ok_or(StridedError::OffsetOverflow)?;
1154        let mut cursor = PadCopyState::new(source_base, dest_base, &self.generic_copy);
1155        for _ in 0..self.generic_copy.total {
1156            // SAFETY: `PadPlan::compile` (:337) proved the destination layout
1157            // injective and `dest_dims` equal to the padded extents, and
1158            // `compile_pad_copy_cursor` (:1883) clamped each copied operand interval
1159            // to `[0, operand_dims[axis])` (`checked_pad_valid_interval`, :1955) while
1160            // computing `source_base_delta`/`dest_base_delta` and both step sets with
1161            // checked arithmetic and a checked offset span; `check_call` (:1300)
1162            // re-proved both layouts equal to the compiled ones, and the bases above
1163            // are re-checked against `isize`, so both cursor offsets stay inside the
1164            // buffers `validate_bounds` accepted for `operand`/`dest`.
1165            unsafe {
1166                // INVARIANT: compile-time checked copy spans/base deltas,
1167                // validated raw descriptors, and exact plan-layout equality
1168                // prove both offsets reachable; positive steps make destinations
1169                // injective, so no copy aliases another cursor position.
1170                (*dest_ptr.offset(cursor.dest_offset))
1171                    .write(*operand_ptr.offset(cursor.source_offset));
1172            }
1173            cursor.advance(&self.generic_copy);
1174        }
1175        Ok(())
1176    }
1177
1178    fn copy_operand_uninit_parallel<T>(
1179        &self,
1180        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1181        operand: &RawStridedRef<'_, T>,
1182        exec: Exec<'_>,
1183    ) -> Result<()>
1184    where
1185        T: Copy + Send + Sync,
1186    {
1187        let operand_base = operand
1188            .offset()
1189            .checked_add(self.generic_copy.source_base_delta)
1190            .ok_or(StridedError::OffsetOverflow)?;
1191        let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
1192        let dest_base = dest
1193            .offset()
1194            .checked_add(self.generic_copy.dest_base_delta)
1195            .ok_or(StridedError::OffsetOverflow)?;
1196        let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1197        crate::threading::parallel_map_reduce(
1198            0..self.generic_copy.total,
1199            exec,
1200            &|range| {
1201                let mut cursor =
1202                    PadCopyState::decode(range.start, operand_base, dest_base, &self.generic_copy)?;
1203                let operand_ptr = operand_ptr.as_const();
1204                let dest_ptr = dest_ptr.as_ptr();
1205
1206                for _ in range {
1207                    // SAFETY: `PadPlan::compile` (:337) proved the destination layout
1208                    // injective and `dest_dims` equal to the padded extents, and
1209                    // `compile_pad_copy_cursor` (:1883) clamped each copied operand interval
1210                    // to `[0, operand_dims[axis])` (`checked_pad_valid_interval`, :1955) while
1211                    // computing `source_base_delta`/`dest_base_delta` and both step sets with
1212                    // checked arithmetic and a checked offset span; `check_call` (:1300)
1213                    // re-proved both layouts equal to the compiled ones, and the bases above
1214                    // are re-checked against `isize`, so both cursor offsets stay inside the
1215                    // buffers `validate_bounds` accepted for `operand`/`dest`.
1216                    unsafe {
1217                        // INVARIANT: compile-time checked copy spans/base
1218                        // deltas, validated descriptors, exact layout equality,
1219                        // and positive injective mapping prove disjoint,
1220                        // reachable source/destination offsets per range.
1221                        (*dest_ptr.offset(cursor.dest_offset))
1222                            .write(*operand_ptr.offset(cursor.source_offset));
1223                    }
1224                    cursor.advance(&self.generic_copy);
1225                }
1226                Ok(())
1227            },
1228            &|left, right| left.and(right),
1229        )
1230    }
1231
1232    fn copy_operand_serial<T>(
1233        &self,
1234        dest: &mut RawStridedMut<'_, T>,
1235        operand: &RawStridedRef<'_, T>,
1236    ) -> Result<()>
1237    where
1238        T: Copy,
1239    {
1240        if self.generic_copy.total == 0 {
1241            return Ok(());
1242        }
1243        let operand_ptr = operand.data().as_ptr();
1244        let dest_ptr = dest.data_mut().as_mut_ptr();
1245        let source_base = operand
1246            .offset()
1247            .checked_add(self.generic_copy.source_base_delta)
1248            .ok_or(StridedError::OffsetOverflow)?;
1249        let dest_base = dest
1250            .offset()
1251            .checked_add(self.generic_copy.dest_base_delta)
1252            .ok_or(StridedError::OffsetOverflow)?;
1253        let mut cursor = PadCopyState::new(source_base, dest_base, &self.generic_copy);
1254        for _ in 0..self.generic_copy.total {
1255            unsafe {
1256                // INVARIANT: compile-time checked copy spans/base deltas,
1257                // validated raw descriptors, and exact plan-layout equality
1258                // prove both offsets reachable; positive steps make destinations
1259                // injective, so no copy aliases another cursor position.
1260                *dest_ptr.offset(cursor.dest_offset) = *operand_ptr.offset(cursor.source_offset);
1261            }
1262            cursor.advance(&self.generic_copy);
1263        }
1264        Ok(())
1265    }
1266
1267    fn copy_operand_parallel<T>(
1268        &self,
1269        dest: &mut RawStridedMut<'_, T>,
1270        operand: &RawStridedRef<'_, T>,
1271        exec: Exec<'_>,
1272    ) -> Result<()>
1273    where
1274        T: Copy + Send + Sync,
1275    {
1276        let operand_base = operand
1277            .offset()
1278            .checked_add(self.generic_copy.source_base_delta)
1279            .ok_or(StridedError::OffsetOverflow)?;
1280        let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
1281        let dest_base = dest
1282            .offset()
1283            .checked_add(self.generic_copy.dest_base_delta)
1284            .ok_or(StridedError::OffsetOverflow)?;
1285        let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1286        crate::threading::parallel_map_reduce(
1287            0..self.generic_copy.total,
1288            exec,
1289            &|range| {
1290                let mut cursor =
1291                    PadCopyState::decode(range.start, operand_base, dest_base, &self.generic_copy)?;
1292                let operand_ptr = operand_ptr.as_const();
1293                let dest_ptr = dest_ptr.as_ptr();
1294
1295                for _ in range {
1296                    unsafe {
1297                        // INVARIANT: compile-time checked copy spans/base
1298                        // deltas, validated descriptors, exact layout equality,
1299                        // and positive injective mapping prove disjoint,
1300                        // reachable source/destination offsets per range.
1301                        *dest_ptr.offset(cursor.dest_offset) =
1302                            *operand_ptr.offset(cursor.source_offset);
1303                    }
1304                    cursor.advance(&self.generic_copy);
1305                }
1306                Ok(())
1307            },
1308            &|left, right| left.and(right),
1309        )
1310    }
1311
1312    fn check_call<D, T>(
1313        &self,
1314        dest: &RawStridedMut<'_, D>,
1315        operand: &RawStridedRef<'_, T>,
1316    ) -> Result<()> {
1317        if operand.dims() != &self.operand_dims[..]
1318            || operand.strides() != &self.operand_strides[..]
1319            || dest.dims() != &self.dest_dims[..]
1320            || dest.strides() != &self.dest_strides[..]
1321        {
1322            return Err(StridedError::PlanLayoutMismatch);
1323        }
1324        Ok(())
1325    }
1326}
1327
1328impl ConcatenatePlan {
1329    /// Compile a multi-input concatenate plan for fixed input and destination layouts.
1330    ///
1331    /// # Errors
1332    ///
1333    /// Returns [`StridedError::UnsupportedArity`] when no input is given, and
1334    /// [`StridedError::RankMismatch`] when the dims and strides lists
1335    /// disagree in length or an input's rank differs from the first
1336    /// input's. Returns [`StridedError::StrideLengthMismatch`] when the
1337    /// destination or an input stride list does not match the rank,
1338    /// [`StridedError::InvalidAxis`] when `axis` is out of range, and
1339    /// [`StridedError::ShapeMismatch`] when an input disagrees with the first
1340    /// input off `axis` or the destination dims are not the concatenated
1341    /// extents. Returns [`StridedError::NonInjectiveOutputLayout`] when two
1342    /// destination elements map onto one offset or the layout span is not
1343    /// representable, and
1344    /// [`StridedError::OffsetOverflow`] when a segment total, a segment start
1345    /// or a destination offset overflows.
1346    pub fn compile(
1347        input_dims: &[&[usize]],
1348        input_strides: &[&[isize]],
1349        dest_dims: &[usize],
1350        dest_strides: &[isize],
1351        axis: usize,
1352    ) -> Result<Self> {
1353        if input_dims.is_empty() {
1354            return Err(StridedError::UnsupportedArity {
1355                arity: 0,
1356                max: usize::MAX,
1357            });
1358        }
1359        if input_dims.len() != input_strides.len() {
1360            return Err(StridedError::RankMismatch(
1361                input_strides.len(),
1362                input_dims.len(),
1363            ));
1364        }
1365
1366        let rank = input_dims[0].len();
1367        if dest_dims.len() != rank || dest_strides.len() != rank {
1368            return Err(StridedError::StrideLengthMismatch);
1369        }
1370        if axis >= rank {
1371            return Err(StridedError::InvalidAxis { axis, rank });
1372        }
1373        checked_total_len(dest_dims)?;
1374        if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
1375            return Err(StridedError::NonInjectiveOutputLayout);
1376        }
1377
1378        let mut expected_dest_dims: AxisVec<usize> = input_dims[0].into();
1379        expected_dest_dims[axis] = 0;
1380        let mut stored_input_dims = crate::inline::OperandVec::with_capacity(input_dims.len());
1381        let mut stored_input_strides = crate::inline::OperandVec::with_capacity(input_dims.len());
1382        let mut dest_offset_deltas = crate::inline::OperandVec::with_capacity(input_dims.len());
1383        let mut copy_plans = crate::inline::OperandVec::with_capacity(input_dims.len());
1384        let mut segment_starts = crate::inline::OperandVec::with_capacity(input_dims.len() + 1);
1385        segment_starts.push(0usize);
1386        let mut axis_base = 0usize;
1387
1388        for (dims, strides) in input_dims.iter().zip(input_strides.iter()) {
1389            if dims.len() != rank {
1390                return Err(StridedError::RankMismatch(dims.len(), rank));
1391            }
1392            if strides.len() != rank {
1393                return Err(StridedError::StrideLengthMismatch);
1394            }
1395            let segment_total = checked_total_len(dims)?;
1396            let segment_end = segment_starts[segment_starts.len() - 1]
1397                .checked_add(segment_total)
1398                .ok_or(StridedError::OffsetOverflow)?;
1399            segment_starts.push(segment_end);
1400            for dim in 0..rank {
1401                if dim == axis {
1402                    expected_dest_dims[axis] = expected_dest_dims[axis]
1403                        .checked_add(dims[axis])
1404                        .ok_or(StridedError::OffsetOverflow)?;
1405                } else if dims[dim] != input_dims[0][dim] {
1406                    return Err(StridedError::ShapeMismatch(
1407                        dims.to_vec(),
1408                        input_dims[0].to_vec(),
1409                    ));
1410                }
1411            }
1412            dest_offset_deltas.push(checked_offset_add(0, dest_strides[axis], axis_base)?);
1413            axis_base = axis_base
1414                .checked_add(dims[axis])
1415                .ok_or(StridedError::OffsetOverflow)?;
1416            copy_plans.push(CopyPlan::compile(dims, dest_strides, strides)?);
1417            stored_input_dims.push((*dims).into());
1418            stored_input_strides.push((*strides).into());
1419        }
1420
1421        if dest_dims != &expected_dest_dims[..] {
1422            return Err(StridedError::ShapeMismatch(
1423                dest_dims.to_vec(),
1424                expected_dest_dims.to_vec(),
1425            ));
1426        }
1427
1428        Ok(Self {
1429            input_dims: stored_input_dims,
1430            input_strides: stored_input_strides,
1431            dest_dims: dest_dims.into(),
1432            dest_strides: dest_strides.into(),
1433            dest_offset_deltas,
1434            segment_starts,
1435            may_tile: copy_plans.iter().any(CopyPlan::may_tile),
1436            copy_plans,
1437        })
1438    }
1439
1440    /// Execute the prepared concatenate traversal.
1441    ///
1442    /// # Errors
1443    ///
1444    /// Returns [`StridedError::PlanLayoutMismatch`] when the destination or
1445    /// an input view does not carry its compiled layout,
1446    /// [`StridedError::RankMismatch`] when the number of inputs differs from
1447    /// the compiled input count, and [`StridedError::OffsetOverflow`] when a
1448    /// segment destination offset overflows.
1449    pub fn execute<T>(
1450        &self,
1451        dest: &mut RawStridedMut<'_, T>,
1452        inputs: &[RawStridedRef<'_, T>],
1453        exec: Exec<'_>,
1454    ) -> Result<()>
1455    where
1456        T: Copy + Send + Sync,
1457    {
1458        let mut exec = exec;
1459        self.check_dest_layout(dest)?;
1460        if inputs.len() != self.input_dims.len() {
1461            return Err(StridedError::RankMismatch(
1462                inputs.len(),
1463                self.input_dims.len(),
1464            ));
1465        }
1466        for (position, input) in inputs.iter().enumerate() {
1467            self.check_input_layout(position, input)?;
1468            self.segment_offset(position, dest.offset())?;
1469        }
1470        if self.try_execute_parallel(
1471            dest,
1472            inputs,
1473            |dst: &mut T, value| *dst = value,
1474            exec.reborrow(),
1475        )? {
1476            return Ok(());
1477        }
1478        for (position, input) in inputs.iter().enumerate() {
1479            self.execute_segment(position, dest, input, exec.reborrow())?;
1480        }
1481        Ok(())
1482    }
1483
1484    /// Execute concatenate into storage whose reachable destination elements are uninitialized.
1485    ///
1486    /// # Errors
1487    ///
1488    /// Returns [`StridedError::PlanLayoutMismatch`] when the destination or
1489    /// an input view does not carry its compiled layout,
1490    /// [`StridedError::RankMismatch`] when the number of inputs differs from
1491    /// the compiled input count, and [`StridedError::OffsetOverflow`] when a
1492    /// segment destination offset overflows.
1493    pub fn execute_uninit<T>(
1494        &self,
1495        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1496        inputs: &[RawStridedRef<'_, T>],
1497        exec: Exec<'_>,
1498    ) -> Result<()>
1499    where
1500        T: Copy + Send + Sync,
1501    {
1502        let mut exec = exec;
1503        self.check_dest_layout(dest)?;
1504        if inputs.len() != self.input_dims.len() {
1505            return Err(StridedError::RankMismatch(
1506                inputs.len(),
1507                self.input_dims.len(),
1508            ));
1509        }
1510        for (position, input) in inputs.iter().enumerate() {
1511            self.check_input_layout(position, input)?;
1512            self.segment_offset(position, dest.offset())?;
1513        }
1514        if self.try_execute_parallel(
1515            dest,
1516            inputs,
1517            |dst: &mut MaybeUninit<T>, value| {
1518                dst.write(value);
1519            },
1520            exec.reborrow(),
1521        )? {
1522            return Ok(());
1523        }
1524        for (position, input) in inputs.iter().enumerate() {
1525            self.execute_segment_uninit(position, dest, input, exec.reborrow())?;
1526        }
1527        Ok(())
1528    }
1529
1530    /// Replay all segments as one logical index space split across workers.
1531    ///
1532    /// Splitting the concatenated space (instead of fanning out per segment)
1533    /// keeps many small segments parallel as a group and splits a large
1534    /// segment across workers, with one fork-join for the whole call. Returns
1535    /// `Ok(false)` without writing when the serial per-segment path must run:
1536    /// the destination is at most the repository threshold, the budget
1537    /// allows one thread, or a segment exceeds the fused-rank limit.
1538    ///
1539    /// A segment whose layout tiles ([`CopyPlan::tiles`], the decision its
1540    /// serial replay [`CopyPlan::execute`] takes) is walked tile by tile: a
1541    /// worker range over the segment's elements owns the tiles whose share of
1542    /// the segment starts in it, so the tiles are split across the token whole
1543    /// and every tile is the one the serial replay walks ([#427]). A segment
1544    /// that declines keeps the flat walk of its element range. A plan none of
1545    /// whose segments can tile for any element types (`may_tile`, decided at
1546    /// compile time) skips the per-call tiling question and takes the flat
1547    /// split below unchanged. When any segment tiles, every segment is divided across the whole budget, as
1548    /// its serial replay divides it, instead of cutting the concatenated
1549    /// space; without tiles the concatenated space is cut as before. Each
1550    /// worker replays its part serially, so nothing is split twice.
1551    ///
1552    /// The caller must have validated every input layout and segment offset.
1553    ///
1554    /// [#427]: https://github.com/tensor4all/strided-rs/issues/427
1555    fn try_execute_parallel<D, T, Apply>(
1556        &self,
1557        dest: &mut RawStridedMut<'_, D>,
1558        inputs: &[RawStridedRef<'_, T>],
1559        apply: Apply,
1560        exec: Exec<'_>,
1561    ) -> Result<bool>
1562    where
1563        D: Copy + Send + Sync,
1564        T: Copy + Send + Sync,
1565        Apply: Fn(&mut D, T) + Send + Sync,
1566    {
1567        let total = self.segment_starts[self.segment_starts.len() - 1];
1568        let exec = crate::cost::for_len(exec, KernelClass::Copy, total);
1569        if exec.is_serial() {
1570            return Ok(false);
1571        }
1572        // Precompute each segment's destination base offset once into an
1573        // inline operand vector (allocation-free within the operand bound);
1574        // the per-segment descriptors are read straight from `self`/`inputs`
1575        // inside the loop, so the parallel replay allocates nothing.
1576        let mut dest_offsets: crate::inline::OperandVec<isize> =
1577            crate::inline::OperandVec::with_capacity(inputs.len());
1578        for position in 0..inputs.len() {
1579            if self.copy_plans[position].fused_layout().is_none() {
1580                return Ok(false);
1581            }
1582            dest_offsets.push(self.segment_offset(position, dest.offset())?);
1583        }
1584        if !self.may_tile {
1585            // No segment can tile, whatever the element types: the flat split
1586            // of the concatenated index space, with no tiling question asked.
1587            self.replay_flat_parallel(dest, inputs, &dest_offsets, apply, exec);
1588            return Ok(true);
1589        }
1590        // The cache tiles of each segment, in an inline operand vector too.
1591        let mut segment_tiles: crate::inline::OperandVec<Option<PairTiles>> =
1592            crate::inline::OperandVec::with_capacity(inputs.len());
1593        for plan in &self.copy_plans {
1594            // An inline traversal only ever tiles inline.
1595            segment_tiles.push(plan.inline_tiles::<D, T>());
1596        }
1597        let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1598        let starts = &self.segment_starts;
1599        let dest_offsets = &dest_offsets;
1600        let segment_tiles = &segment_tiles;
1601        #[cfg(test)]
1602        let walked_tiles = core::sync::atomic::AtomicUsize::new(0);
1603        // Per segment, the dispatched ranges that walked at least one of its
1604        // tiles.
1605        #[cfg(test)]
1606        let tiled_ranges: Vec<core::sync::atomic::AtomicUsize> = (0..inputs.len())
1607            .map(|_| core::sync::atomic::AtomicUsize::new(0))
1608            .collect();
1609        // Replay the elements `local_start..local_end` of one segment: the
1610        // tiles whose share starts in them, or the flat range.
1611        let replay_segment = |position: usize, local_start: usize, local_end: usize| {
1612            // The tile walk records each tile it visits on the thread that
1613            // walks it. Move this range's tiles of this segment from that
1614            // thread's count to `walked_tiles`, count the range for the segment
1615            // when it walked any, and keep what the thread had counted before;
1616            // both reach the caller's counters after the dispatch.
1617            #[cfg(test)]
1618            let _count = MoveTileCount {
1619                counted_before: crate::threading::take_tile_boxes(),
1620                walked: &walked_tiles,
1621                tiled_ranges: &tiled_ranges[position],
1622            };
1623            // The whole-plan guard above proved every segment has an inline
1624            // fused layout; skip one only if a future caller relaxes that
1625            // check.
1626            let Some(layout) = self.copy_plans[position].fused_layout() else {
1627                return;
1628            };
1629            let input = &inputs[position];
1630            // SAFETY: `check_dest_layout`/`check_input_layout` proved the
1631            // views carry the compiled layouts, so each segment window (input
1632            // dims, destination strides, checked segment offset) is a
1633            // sub-layout of the validated destination and each input layout is
1634            // in-bounds of its data. The destination layout is injective and
1635            // the segments occupy disjoint ranges of the concatenation axis,
1636            // so disjoint element ranges write disjoint slots; inputs are
1637            // shared borrows that cannot alias the exclusive destination
1638            // borrow. The tiles of a segment are `pair_tiles` of its layout,
1639            // which address exactly its slots, and disjoint element ranges own
1640            // disjoint tile ranges within the grid (`tile_share` is monotone
1641            // and maps the segment end to the tile count).
1642            unsafe {
1643                if let Some(tiles) = &segment_tiles[position] {
1644                    let segment_len = starts[position + 1] - starts[position];
1645                    let count = crate::raw_ops::tile_count(&tiles.layout, &tiles.blocks);
1646                    let first = tile_share(local_start, count, segment_len);
1647                    let end = tile_share(local_end, count, segment_len);
1648                    crate::raw_ops::apply_tile_range(
1649                        dest_ptr.as_ptr(),
1650                        dest_offsets[position],
1651                        input.data().as_ptr(),
1652                        input.offset(),
1653                        &tiles.layout,
1654                        &tiles.blocks,
1655                        first,
1656                        end - first,
1657                        &mut &apply,
1658                    );
1659                } else {
1660                    crate::raw_ops::apply_fused_range(
1661                        dest_ptr.as_ptr(),
1662                        dest_offsets[position],
1663                        input.data().as_ptr(),
1664                        input.offset(),
1665                        layout,
1666                        local_start,
1667                        local_end - local_start,
1668                        &mut &apply,
1669                    );
1670                }
1671            }
1672        };
1673        if segment_tiles.iter().any(Option::is_some) {
1674            // Every segment is divided across the whole budget, as its serial
1675            // replay divides it: slot `w` of `width` owns the share
1676            // `w/width..(w+1)/width` of each segment. A tiled segment's elements
1677            // cost several times a contiguous one's, so cutting the
1678            // concatenated space by element count would leave the slots that
1679            // drew contiguous segments idle (#427).
1680            let width = exec.budget().get();
1681            crate::threading::parallel_for_each(0..width, exec, &|slots| {
1682                for position in 0..inputs.len() {
1683                    let segment_len = starts[position + 1] - starts[position];
1684                    if segment_len == 0 {
1685                        continue;
1686                    }
1687                    replay_segment(
1688                        position,
1689                        slot_share(slots.start, segment_len, width),
1690                        slot_share(slots.end, segment_len, width),
1691                    );
1692                }
1693            });
1694        } else {
1695            crate::threading::parallel_for_each(0..total, exec, &|range| {
1696                // First segment whose end lies past the range start.
1697                let mut position = starts[1..].partition_point(|&end| end <= range.start);
1698                while position < inputs.len() && starts[position] < range.end {
1699                    let local_start = range.start.max(starts[position]) - starts[position];
1700                    let local_end = range.end.min(starts[position + 1]) - starts[position];
1701                    replay_segment(position, local_start, local_end);
1702                    position += 1;
1703                }
1704            });
1705        }
1706        #[cfg(test)]
1707        {
1708            crate::threading::record_tile_boxes(walked_tiles.into_inner());
1709            crate::threading::record_tiled_ranges(
1710                tiled_ranges
1711                    .into_iter()
1712                    .map(core::sync::atomic::AtomicUsize::into_inner)
1713                    .collect(),
1714            );
1715        }
1716        Ok(true)
1717    }
1718
1719    /// The whole-plan replay of a plan none of whose segments can tile: the
1720    /// concatenated index space `0..total` split into contiguous worker
1721    /// ranges, each segment window walked flat.
1722    ///
1723    /// The caller must have validated every input layout and segment offset,
1724    /// passed the segments' destination base offsets, proved every segment
1725    /// has an inline fused layout, and narrowed `exec` for `total`.
1726    fn replay_flat_parallel<D, T, Apply>(
1727        &self,
1728        dest: &mut RawStridedMut<'_, D>,
1729        inputs: &[RawStridedRef<'_, T>],
1730        dest_offsets: &crate::inline::OperandVec<isize>,
1731        apply: Apply,
1732        exec: Exec<'_>,
1733    ) where
1734        D: Copy + Send + Sync,
1735        T: Copy + Send + Sync,
1736        Apply: Fn(&mut D, T) + Send + Sync,
1737    {
1738        let total = self.segment_starts[self.segment_starts.len() - 1];
1739        let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1740        let starts = &self.segment_starts;
1741        crate::threading::parallel_for_each(0..total, exec, &|range| {
1742            // First segment whose end lies past the range start.
1743            let mut position = starts[1..].partition_point(|&end| end <= range.start);
1744            while position < inputs.len() && starts[position] < range.end {
1745                let local_start = range.start.max(starts[position]) - starts[position];
1746                let local_end = range.end.min(starts[position + 1]) - starts[position];
1747                // The caller proved every segment has an inline fused layout;
1748                // skip one only if a future caller relaxes that check.
1749                let Some(layout) = self.copy_plans[position].fused_layout() else {
1750                    position += 1;
1751                    continue;
1752                };
1753                let input = &inputs[position];
1754                // SAFETY: `check_dest_layout`/`check_input_layout` proved the
1755                // views carry the compiled layouts, so each segment window
1756                // (input dims, destination strides, checked segment offset) is
1757                // a sub-layout of the validated destination and each input
1758                // layout is in-bounds of its data. The destination layout is
1759                // injective and the segments occupy disjoint ranges of the
1760                // concatenation axis, so disjoint logical ranges write
1761                // disjoint slots; inputs are shared borrows that cannot alias
1762                // the exclusive destination borrow.
1763                unsafe {
1764                    crate::raw_ops::apply_fused_range(
1765                        dest_ptr.as_ptr(),
1766                        dest_offsets[position],
1767                        input.data().as_ptr(),
1768                        input.offset(),
1769                        layout,
1770                        local_start,
1771                        local_end - local_start,
1772                        &mut &apply,
1773                    );
1774                }
1775                position += 1;
1776            }
1777        });
1778    }
1779
1780    pub(crate) fn check_dest_layout<T>(&self, dest: &RawStridedMut<'_, T>) -> Result<()> {
1781        if dest.dims() != &self.dest_dims[..] || dest.strides() != &self.dest_strides[..] {
1782            return Err(StridedError::PlanLayoutMismatch);
1783        }
1784        Ok(())
1785    }
1786
1787    pub(crate) fn check_input_layout<T>(
1788        &self,
1789        position: usize,
1790        input: &RawStridedRef<'_, T>,
1791    ) -> Result<()> {
1792        if position >= self.input_dims.len()
1793            || input.dims() != &self.input_dims[position][..]
1794            || input.strides() != &self.input_strides[position][..]
1795        {
1796            return Err(StridedError::PlanLayoutMismatch);
1797        }
1798        Ok(())
1799    }
1800
1801    pub(crate) fn input_count(&self) -> usize {
1802        self.input_dims.len()
1803    }
1804
1805    /// Whether the whole-plan entry would replay in parallel within the
1806    /// budget of `exec`. Erased callers use it to keep the allocation-free
1807    /// per-segment loop for serial execution.
1808    pub(crate) fn prefers_whole_plan(&self, exec: &Exec<'_>) -> bool {
1809        let total = self.segment_starts[self.segment_starts.len() - 1];
1810        crate::threading::is_parallel(KernelClass::Copy, total, exec)
1811    }
1812
1813    pub(crate) fn segment_offset(&self, position: usize, dest_offset: isize) -> Result<isize> {
1814        dest_offset
1815            .checked_add(self.dest_offset_deltas[position])
1816            .ok_or(StridedError::OffsetOverflow)
1817    }
1818
1819    pub(crate) fn execute_segment<T>(
1820        &self,
1821        position: usize,
1822        dest: &mut RawStridedMut<'_, T>,
1823        input: &RawStridedRef<'_, T>,
1824        exec: Exec<'_>,
1825    ) -> Result<()>
1826    where
1827        T: Copy + Send + Sync,
1828    {
1829        let segment_offset = self.segment_offset(position, dest.offset())?;
1830        let dest_data = dest.data_mut();
1831        let mut segment = unsafe {
1832            RawStridedMut::new_unchecked(
1833                dest_data,
1834                &self.input_dims[position],
1835                &self.dest_strides,
1836                segment_offset,
1837            )
1838        };
1839        self.copy_plans[position].execute(&mut segment, input, exec)
1840    }
1841
1842    pub(crate) fn execute_segment_uninit<T>(
1843        &self,
1844        position: usize,
1845        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1846        input: &RawStridedRef<'_, T>,
1847        exec: Exec<'_>,
1848    ) -> Result<()>
1849    where
1850        T: Copy + Send + Sync,
1851    {
1852        let segment_offset = self.segment_offset(position, dest.offset())?;
1853        let dest_data = dest.data_mut();
1854        let mut segment = unsafe {
1855            RawStridedMut::new_unchecked(
1856                dest_data,
1857                &self.input_dims[position],
1858                &self.dest_strides,
1859                segment_offset,
1860            )
1861        };
1862        self.copy_plans[position].execute_uninit(&mut segment, input, exec)
1863    }
1864}
1865
1866/// Moves the tile boxes the current thread recorded since it was built into
1867/// `walked`, counts one range in `tiled_ranges` (the counter of the segment
1868/// being replayed) when there were any, and restores the count the thread had
1869/// before, when dropped.
1870#[cfg(test)]
1871struct MoveTileCount<'a> {
1872    counted_before: usize,
1873    walked: &'a core::sync::atomic::AtomicUsize,
1874    tiled_ranges: &'a core::sync::atomic::AtomicUsize,
1875}
1876
1877#[cfg(test)]
1878impl Drop for MoveTileCount<'_> {
1879    fn drop(&mut self) {
1880        let walked = crate::threading::take_tile_boxes();
1881        self.walked
1882            .fetch_add(walked, core::sync::atomic::Ordering::Relaxed);
1883        if walked > 0 {
1884            self.tiled_ranges
1885                .fetch_add(1, core::sync::atomic::Ordering::Relaxed);
1886        }
1887        crate::threading::record_tile_boxes(self.counted_before);
1888    }
1889}
1890
1891/// The first tile owned by the worker range of a segment that starts at
1892/// element `local` of `len`: `ceil(local * count / len)`, so element 0 owns
1893/// tile 0, the segment end owns `count`, and the map is monotone. A tile thus
1894/// goes to the range holding its proportional start, which keeps the split
1895/// balanced by elements while handing out whole tiles.
1896fn tile_share(local: usize, count: usize, len: usize) -> usize {
1897    debug_assert!(local <= len && len > 0);
1898    // `count <= len`, so the quotient fits `usize`; the product needs u128.
1899    ((local as u128 * count as u128).div_ceil(len as u128)) as usize
1900}
1901
1902/// The first element of a segment of `len` elements owned by slot `slot` of
1903/// `width`: `slot * len / width`, so slot 0 starts at 0, slot `width` at `len`,
1904/// and the map is monotone.
1905fn slot_share(slot: usize, len: usize, width: usize) -> usize {
1906    debug_assert!(slot <= width && width > 0);
1907    // The quotient is at most `len`; the product needs u128.
1908    (slot as u128 * len as u128 / width as u128) as usize
1909}
1910
1911impl ReversePlan {
1912    /// Compile a reverse plan for one operand layout, destination layout, and axis set.
1913    ///
1914    /// # Errors
1915    ///
1916    /// Returns [`StridedError::StrideLengthMismatch`] when the operand or
1917    /// destination stride list does not match the operand rank,
1918    /// [`StridedError::InvalidAxis`] when a listed axis is out of range, and
1919    /// [`StridedError::NonInjectiveOutputLayout`] when two destination
1920    /// elements map onto one offset, or the layout span is not representable.
1921    /// Returns
1922    /// [`StridedError::OffsetOverflow`] when an element count, a negated
1923    /// source stride or the source offset delta overflows.
1924    pub fn compile(
1925        operand_dims: &[usize],
1926        operand_strides: &[isize],
1927        dest_strides: &[isize],
1928        axes: &[usize],
1929    ) -> Result<Self> {
1930        let rank = operand_dims.len();
1931        if operand_strides.len() != rank || dest_strides.len() != rank {
1932            return Err(StridedError::StrideLengthMismatch);
1933        }
1934        checked_total_len(operand_dims)?;
1935
1936        let mut reverse_axis: AxisVec<bool> = (0..rank).map(|_| false).collect();
1937        for &axis in axes {
1938            if axis >= rank {
1939                return Err(StridedError::InvalidAxis { axis, rank });
1940            }
1941            reverse_axis[axis] = true;
1942        }
1943
1944        let mut source_strides: AxisVec<isize> = AxisVec::with_capacity(rank);
1945        let mut source_offset_delta = 0isize;
1946        for axis in 0..rank {
1947            if reverse_axis[axis] {
1948                source_strides.push(
1949                    operand_strides[axis]
1950                        .checked_neg()
1951                        .ok_or(StridedError::OffsetOverflow)?,
1952                );
1953                if operand_dims[axis] > 0 {
1954                    source_offset_delta = checked_offset_add(
1955                        source_offset_delta,
1956                        operand_strides[axis],
1957                        operand_dims[axis] - 1,
1958                    )?;
1959                }
1960            } else {
1961                source_strides.push(operand_strides[axis]);
1962            }
1963        }
1964        let copy_plan = CopyPlan::compile(operand_dims, dest_strides, &source_strides)?;
1965
1966        Ok(Self {
1967            operand_dims: operand_dims.into(),
1968            operand_strides: operand_strides.into(),
1969            dest_strides: dest_strides.into(),
1970            source_strides,
1971            source_offset_delta,
1972            copy_plan,
1973        })
1974    }
1975
1976    /// Execute the prepared reverse traversal.
1977    ///
1978    /// # Errors
1979    ///
1980    /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
1981    /// carry the compiled operand and destination layouts, and
1982    /// [`StridedError::OffsetOverflow`] when the operand offset plus the
1983    /// compiled source offset delta overflows.
1984    pub fn execute<T>(
1985        &self,
1986        dest: &mut RawStridedMut<'_, T>,
1987        operand: &RawStridedRef<'_, T>,
1988        exec: Exec<'_>,
1989    ) -> Result<()>
1990    where
1991        T: Copy + Send + Sync,
1992    {
1993        self.check_call(dest, operand)?;
1994        let source_offset = operand
1995            .offset()
1996            .checked_add(self.source_offset_delta)
1997            .ok_or(StridedError::OffsetOverflow)?;
1998        let source = unsafe {
1999            RawStridedRef::new_unchecked(
2000                operand.data(),
2001                &self.operand_dims,
2002                &self.source_strides,
2003                source_offset,
2004            )
2005        };
2006        self.copy_plan.execute(dest, &source, exec)
2007    }
2008
2009    /// Execute reverse into storage whose reachable destination elements are uninitialized.
2010    ///
2011    /// # Errors
2012    ///
2013    /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
2014    /// carry the compiled operand and destination layouts, and
2015    /// [`StridedError::OffsetOverflow`] when the operand offset plus the
2016    /// compiled source offset delta overflows.
2017    pub fn execute_uninit<T>(
2018        &self,
2019        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
2020        operand: &RawStridedRef<'_, T>,
2021        exec: Exec<'_>,
2022    ) -> Result<()>
2023    where
2024        T: Copy + Send + Sync,
2025    {
2026        self.check_call(dest, operand)?;
2027        let source_offset = operand
2028            .offset()
2029            .checked_add(self.source_offset_delta)
2030            .ok_or(StridedError::OffsetOverflow)?;
2031        let source = unsafe {
2032            RawStridedRef::new_unchecked(
2033                operand.data(),
2034                &self.operand_dims,
2035                &self.source_strides,
2036                source_offset,
2037            )
2038        };
2039        self.copy_plan.execute_uninit(dest, &source, exec)
2040    }
2041
2042    fn check_call<D, T>(
2043        &self,
2044        dest: &RawStridedMut<'_, D>,
2045        operand: &RawStridedRef<'_, T>,
2046    ) -> Result<()> {
2047        if operand.dims() != &self.operand_dims[..]
2048            || operand.strides() != &self.operand_strides[..]
2049            || dest.dims() != &self.operand_dims[..]
2050            || dest.strides() != &self.dest_strides[..]
2051        {
2052            return Err(StridedError::PlanLayoutMismatch);
2053        }
2054        Ok(())
2055    }
2056}
2057
2058fn checked_total_len(dims: &[usize]) -> Result<usize> {
2059    if dims.is_empty() {
2060        return Ok(1);
2061    }
2062    dims.iter()
2063        .try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
2064        .ok_or(StridedError::OffsetOverflow)
2065}
2066
2067fn checked_stride_mul(stride: isize, factor: usize) -> Result<isize> {
2068    let factor = isize::try_from(factor).map_err(|_| StridedError::OffsetOverflow)?;
2069    stride
2070        .checked_mul(factor)
2071        .ok_or(StridedError::OffsetOverflow)
2072}
2073
2074fn checked_pad_output_dim(
2075    input_extent: usize,
2076    edge_low: i64,
2077    edge_high: i64,
2078    interior_step: i64,
2079    axis: usize,
2080    rank: usize,
2081) -> Result<usize> {
2082    let base = if input_extent == 0 {
2083        0i128
2084    } else {
2085        (input_extent as i128 - 1)
2086            .checked_mul(i128::from(interior_step))
2087            .and_then(|value| value.checked_add(1))
2088            .ok_or(StridedError::OffsetOverflow)?
2089    };
2090    let dim = i128::from(edge_low)
2091        .checked_add(i128::from(edge_high))
2092        .and_then(|value| value.checked_add(base))
2093        .ok_or(StridedError::OffsetOverflow)?;
2094    usize::try_from(dim).map_err(|_| StridedError::InvalidAxis { axis, rank })
2095}
2096
2097fn compile_pad_fill_cursor(dims: &[usize], strides: &[isize]) -> Result<PadFillCursor> {
2098    let mut steps = AxisVec::with_capacity(dims.len());
2099    let mut resets = AxisVec::with_capacity(dims.len());
2100    for (&dim, &stride) in dims.iter().zip(strides) {
2101        steps.push(stride);
2102        resets.push(checked_cursor_reset(stride, dim)?);
2103    }
2104    check_offset_span(dims, &steps)?;
2105    Ok(PadFillCursor { steps, resets })
2106}
2107
2108fn compile_pad_copy_cursor(
2109    operand_dims: &[usize],
2110    operand_strides: &[isize],
2111    dest_dims: &[usize],
2112    dest_strides: &[isize],
2113    edge_padding_low: &[i64],
2114    interior_step: &[i64],
2115) -> Result<PadCopyCursor> {
2116    let mut shape = AxisVec::with_capacity(operand_dims.len());
2117    let mut source_steps = AxisVec::with_capacity(operand_dims.len());
2118    let mut source_resets = AxisVec::with_capacity(operand_dims.len());
2119    let mut dest_steps = AxisVec::with_capacity(operand_dims.len());
2120    let mut dest_resets = AxisVec::with_capacity(operand_dims.len());
2121    let mut source_base_delta = 0isize;
2122    let mut dest_base_delta = 0isize;
2123    let mut copy_empty = false;
2124
2125    for axis in 0..operand_dims.len() {
2126        let (start, end) = checked_pad_valid_interval(
2127            operand_dims[axis],
2128            dest_dims[axis],
2129            edge_padding_low[axis],
2130            interior_step[axis],
2131        )?;
2132        let extent = end - start;
2133        shape.push(extent);
2134        if !copy_empty && extent != 0 {
2135            source_base_delta =
2136                checked_offset_add(source_base_delta, operand_strides[axis], start)?;
2137            let output_start = i128::from(edge_padding_low[axis])
2138                .checked_add(
2139                    i128::try_from(start)
2140                        .map_err(|_| StridedError::OffsetOverflow)?
2141                        .checked_mul(i128::from(interior_step[axis]))
2142                        .ok_or(StridedError::OffsetOverflow)?,
2143                )
2144                .ok_or(StridedError::OffsetOverflow)?;
2145            let output_start =
2146                usize::try_from(output_start).map_err(|_| StridedError::OffsetOverflow)?;
2147            dest_base_delta =
2148                checked_offset_add(dest_base_delta, dest_strides[axis], output_start)?;
2149        }
2150        copy_empty |= extent == 0;
2151
2152        let source_step = operand_strides[axis];
2153        let dest_step = checked_stride_mul_i64(dest_strides[axis], interior_step[axis])?;
2154        source_steps.push(source_step);
2155        source_resets.push(checked_cursor_reset(source_step, extent)?);
2156        dest_steps.push(dest_step);
2157        dest_resets.push(checked_cursor_reset(dest_step, extent)?);
2158    }
2159
2160    check_offset_span(&shape, &source_steps)?;
2161    check_offset_span(&shape, &dest_steps)?;
2162    let total = if shape.contains(&0) {
2163        0
2164    } else {
2165        checked_total_len(&shape)?
2166    };
2167
2168    Ok(PadCopyCursor {
2169        shape,
2170        source_base_delta,
2171        dest_base_delta,
2172        source_steps,
2173        source_resets,
2174        dest_steps,
2175        dest_resets,
2176        total,
2177    })
2178}
2179
2180fn checked_pad_valid_interval(
2181    input_extent: usize,
2182    dest_extent: usize,
2183    edge_low: i64,
2184    step: i64,
2185) -> Result<(usize, usize)> {
2186    if input_extent == 0 || dest_extent == 0 {
2187        return Ok((0, 0));
2188    }
2189    let step = i128::from(step);
2190    let lower = ceil_div_positive(-i128::from(edge_low), step)?;
2191    let dest_last = i128::try_from(dest_extent)
2192        .map_err(|_| StridedError::OffsetOverflow)?
2193        .checked_sub(1)
2194        .ok_or(StridedError::OffsetOverflow)?;
2195    let upper = floor_div_positive(
2196        dest_last
2197            .checked_sub(i128::from(edge_low))
2198            .ok_or(StridedError::OffsetOverflow)?,
2199        step,
2200    )?
2201    .checked_add(1)
2202    .ok_or(StridedError::OffsetOverflow)?;
2203    let input_extent = i128::try_from(input_extent).map_err(|_| StridedError::OffsetOverflow)?;
2204    let lower = lower.clamp(0, input_extent);
2205    let upper = upper.clamp(0, input_extent);
2206    if lower >= upper {
2207        return Ok((0, 0));
2208    }
2209    Ok((
2210        usize::try_from(lower).map_err(|_| StridedError::OffsetOverflow)?,
2211        usize::try_from(upper).map_err(|_| StridedError::OffsetOverflow)?,
2212    ))
2213}
2214
2215fn ceil_div_positive(numerator: i128, denominator: i128) -> Result<i128> {
2216    if denominator <= 0 {
2217        return Err(StridedError::OffsetOverflow);
2218    }
2219    let quotient = numerator.div_euclid(denominator);
2220    let remainder = numerator.rem_euclid(denominator);
2221    quotient
2222        .checked_add(i128::from(remainder != 0))
2223        .ok_or(StridedError::OffsetOverflow)
2224}
2225
2226fn floor_div_positive(numerator: i128, denominator: i128) -> Result<i128> {
2227    if denominator <= 0 {
2228        return Err(StridedError::OffsetOverflow);
2229    }
2230    Ok(numerator.div_euclid(denominator))
2231}
2232
2233fn checked_stride_mul_i64(stride: isize, factor: i64) -> Result<isize> {
2234    let factor = isize::try_from(factor).map_err(|_| StridedError::OffsetOverflow)?;
2235    stride
2236        .checked_mul(factor)
2237        .ok_or(StridedError::OffsetOverflow)
2238}
2239
2240fn checked_cursor_reset(step: isize, extent: usize) -> Result<isize> {
2241    if extent == 0 {
2242        return Ok(0);
2243    }
2244    let last = isize::try_from(extent - 1).map_err(|_| StridedError::OffsetOverflow)?;
2245    step.checked_mul(last)
2246        .and_then(isize::checked_neg)
2247        .ok_or(StridedError::OffsetOverflow)
2248}
2249
2250fn check_offset_span(shape: &[usize], strides: &[isize]) -> Result<()> {
2251    let mut min = 0isize;
2252    let mut max = 0isize;
2253    for (&extent, &stride) in shape.iter().zip(strides) {
2254        if extent <= 1 {
2255            continue;
2256        }
2257        let last = isize::try_from(extent - 1).map_err(|_| StridedError::OffsetOverflow)?;
2258        let delta = stride
2259            .checked_mul(last)
2260            .ok_or(StridedError::OffsetOverflow)?;
2261        if delta < 0 {
2262            min = min.checked_add(delta).ok_or(StridedError::OffsetOverflow)?;
2263        } else {
2264            max = max.checked_add(delta).ok_or(StridedError::OffsetOverflow)?;
2265        }
2266    }
2267    let _ = (min, max);
2268    Ok(())
2269}
2270
2271fn is_dense_col_major(dims: &[usize], strides: &[isize]) -> bool {
2272    let mut expected = 1isize;
2273    for (&dim, &stride) in dims.iter().zip(strides.iter()) {
2274        if stride != expected {
2275            return false;
2276        }
2277        let Ok(dim) = isize::try_from(dim) else {
2278            return false;
2279        };
2280        let Some(next) = expected.checked_mul(dim) else {
2281            return false;
2282        };
2283        expected = next;
2284    }
2285    true
2286}
2287
2288fn compile_contiguous_pad_axis0_run(
2289    operand_dims: &[usize],
2290    operand_strides: &[isize],
2291    dest_dims: &[usize],
2292    dest_strides: &[isize],
2293    edge_padding_low: &[i64],
2294    interior_step: &[i64],
2295) -> Option<ContiguousPadAxis0Run> {
2296    if operand_dims.is_empty()
2297        || operand_strides[0] != 1
2298        || dest_strides[0] != 1
2299        || interior_step[0] != 1
2300    {
2301        return None;
2302    }
2303
2304    let operand_extent = operand_dims[0] as i128;
2305    let dest_extent = dest_dims[0] as i128;
2306    let edge_low = i128::from(edge_padding_low[0]);
2307    let operand_start = (-edge_low).clamp(0, operand_extent);
2308    let dest_start = edge_low.clamp(0, dest_extent);
2309    let len = (operand_extent - operand_start).min(dest_extent - dest_start);
2310    Some(ContiguousPadAxis0Run {
2311        operand_start: usize::try_from(operand_start).ok()?,
2312        dest_start: usize::try_from(dest_start).ok()?,
2313        len: usize::try_from(len).ok()?,
2314    })
2315}
2316
2317/// Compile the disjoint-span column write for the dense, non-cropping,
2318/// no-interior-padding class, or `None` to keep the fill-then-copy fallback.
2319// Compile key: the operand layout, the destination dims, the three padding
2320// vectors, the destination-fill flag and the run.
2321#[allow(clippy::too_many_arguments)]
2322fn compile_contiguous_pad_axis0_columns(
2323    operand_dims: &[usize],
2324    operand_strides: &[isize],
2325    dest_dims: &[usize],
2326    edge_padding_low: &[i64],
2327    edge_padding_high: &[i64],
2328    interior_step: &[i64],
2329    contiguous_dest_fill: bool,
2330    run: ContiguousPadAxis0Run,
2331) -> Option<ContiguousPadAxis0Columns> {
2332    if run.len == 0 || !contiguous_dest_fill || dest_dims.is_empty() {
2333        return None;
2334    }
2335    if edge_padding_low.iter().any(|&low| low < 0)
2336        || edge_padding_high.iter().any(|&high| high < 0)
2337        || interior_step.iter().any(|&step| step != 1)
2338    {
2339        return None;
2340    }
2341
2342    let rank = operand_dims.len();
2343    let dest_axis0_len = dest_dims[0];
2344    let dest_axis0_step = isize::try_from(dest_axis0_len).ok()?;
2345    let column_total = checked_total_len(&dest_dims[1..]).ok()?;
2346    let mut operand_outer_dims = AxisVec::with_capacity(rank - 1);
2347    let mut operand_outer_strides = AxisVec::with_capacity(rank - 1);
2348    let mut dest_outer_dims = AxisVec::with_capacity(rank - 1);
2349    let mut edge_low_outer = AxisVec::with_capacity(rank - 1);
2350    for axis in 1..rank {
2351        operand_outer_dims.push(operand_dims[axis]);
2352        operand_outer_strides.push(operand_strides[axis]);
2353        dest_outer_dims.push(dest_dims[axis]);
2354        edge_low_outer.push(usize::try_from(edge_padding_low[axis]).ok()?);
2355    }
2356
2357    let low0 = run.dest_start;
2358    let high0 = dest_axis0_len.checked_sub(low0)?.checked_sub(run.len)?;
2359    Some(ContiguousPadAxis0Columns {
2360        column_total,
2361        dest_axis0_len,
2362        dest_axis0_step,
2363        low0,
2364        high0,
2365        run_len: run.len,
2366        operand_outer_dims,
2367        operand_outer_strides,
2368        dest_outer_dims,
2369        edge_low_outer,
2370    })
2371}
2372
2373/// Fill a disjoint raw destination span, chunked across the budget of `exec`.
2374///
2375/// # Safety
2376///
2377/// `ptr..ptr + len` must be a writable destination span with no concurrent
2378/// access from another worker.
2379unsafe fn fill_raw_span<T: Copy + Send + Sync>(ptr: *mut T, len: usize, fill: T, exec: Exec<'_>) {
2380    if len == 0 {
2381        return;
2382    }
2383    // SAFETY: the caller guarantees the exact writable span; the slice is not
2384    // retained past `fill_contiguous`.
2385    let span = unsafe { core::slice::from_raw_parts_mut(ptr, len) };
2386    crate::threading::fill_contiguous(span, fill, exec);
2387}
2388
2389/// Fill a disjoint raw destination span that may be uninitialized.
2390///
2391/// # Safety
2392///
2393/// `ptr..ptr + len` must be a writable destination span with no concurrent
2394/// access from another worker.
2395unsafe fn fill_raw_span_uninit<T: Copy + Send + Sync>(
2396    ptr: *mut T,
2397    len: usize,
2398    fill: T,
2399    exec: Exec<'_>,
2400) {
2401    if len == 0 {
2402        return;
2403    }
2404    // SAFETY: the caller guarantees the exact writable span; the
2405    // `MaybeUninit` view never forms a `&mut [T]` over uninitialized memory.
2406    unsafe { crate::threading::fill_contiguous_uninit(ptr, len, fill, exec) };
2407}
2408
2409fn checked_offset_add(base: isize, stride: isize, coord: usize) -> Result<isize> {
2410    let coord = isize::try_from(coord).map_err(|_| StridedError::OffsetOverflow)?;
2411    let scaled = stride
2412        .checked_mul(coord)
2413        .ok_or(StridedError::OffsetOverflow)?;
2414    base.checked_add(scaled).ok_or(StridedError::OffsetOverflow)
2415}
2416
2417/// The operand coordinate contributed by one outer axis, or `None` when the
2418/// axis falls outside the operand's in-bounds interval.
2419fn in_bounds_outer_coord(
2420    columns: &ContiguousPadAxis0Columns,
2421    axis: usize,
2422    coord: usize,
2423) -> Option<usize> {
2424    let q = coord.checked_sub(columns.edge_low_outer[axis])?;
2425    (q < columns.operand_outer_dims[axis]).then_some(q)
2426}
2427
2428fn advance_col_major_index(index: &mut [usize], shape: &[usize]) {
2429    for axis in 0..index.len() {
2430        index[axis] += 1;
2431        if index[axis] < shape[axis] {
2432            return;
2433        }
2434        index[axis] = 0;
2435    }
2436}
2437
2438fn fill_col_major_index(mut linear: usize, shape: &[usize], out: &mut [usize]) {
2439    for (axis, coord) in out.iter_mut().enumerate() {
2440        let dim = shape[axis];
2441        *coord = linear % dim;
2442        linear /= dim;
2443    }
2444}
2445
2446struct PadFillState {
2447    coords: CoordScratch,
2448    offset: isize,
2449}
2450
2451impl PadFillState {
2452    fn new(base: isize, shape: &[usize], _cursor: &PadFillCursor) -> Self {
2453        Self {
2454            coords: CoordScratch::new(shape.len()),
2455            offset: base,
2456        }
2457    }
2458
2459    fn decode(linear: usize, base: isize, shape: &[usize], cursor: &PadFillCursor) -> Result<Self> {
2460        let mut state = Self::new(base, shape, cursor);
2461        fill_col_major_index(linear, shape, state.coords.as_mut_slice());
2462        for (&coord, &step) in state.coords.as_mut_slice().iter().zip(&cursor.steps) {
2463            state.offset = checked_offset_add(state.offset, step, coord)?;
2464        }
2465        Ok(state)
2466    }
2467
2468    #[inline]
2469    fn advance(&mut self, shape: &[usize], cursor: &PadFillCursor) {
2470        // INVARIANT: precomputed checked offset arithmetic, the validated
2471        // descriptor, and exact layout equality prove each incremental offset
2472        // remains reachable.
2473        // The axis indexes the coordinates, the shape, the steps and the resets.
2474        #[allow(clippy::needless_range_loop)]
2475        for axis in 0..shape.len() {
2476            let next = self.coords.as_mut_slice()[axis] + 1;
2477            if next < shape[axis] {
2478                self.coords.as_mut_slice()[axis] = next;
2479                self.offset += cursor.steps[axis];
2480                return;
2481            }
2482            self.coords.as_mut_slice()[axis] = 0;
2483            self.offset += cursor.resets[axis];
2484        }
2485    }
2486}
2487
2488struct PadCopyState {
2489    coords: CoordScratch,
2490    source_offset: isize,
2491    dest_offset: isize,
2492}
2493
2494impl PadCopyState {
2495    fn new(source_base: isize, dest_base: isize, cursor: &PadCopyCursor) -> Self {
2496        Self {
2497            coords: CoordScratch::new(cursor.shape.len()),
2498            source_offset: source_base,
2499            dest_offset: dest_base,
2500        }
2501    }
2502
2503    fn decode(
2504        linear: usize,
2505        source_base: isize,
2506        dest_base: isize,
2507        cursor: &PadCopyCursor,
2508    ) -> Result<Self> {
2509        let mut state = Self::new(source_base, dest_base, cursor);
2510        fill_col_major_index(linear, &cursor.shape, state.coords.as_mut_slice());
2511        for axis in 0..cursor.shape.len() {
2512            let coord = state.coords.as_mut_slice()[axis];
2513            state.source_offset =
2514                checked_offset_add(state.source_offset, cursor.source_steps[axis], coord)?;
2515            state.dest_offset =
2516                checked_offset_add(state.dest_offset, cursor.dest_steps[axis], coord)?;
2517        }
2518        Ok(state)
2519    }
2520
2521    #[inline]
2522    fn advance(&mut self, cursor: &PadCopyCursor) {
2523        // INVARIANT: compile-time checked steps/resets/offset arithmetic,
2524        // validated descriptors, and exact plan-layout equality prove every update below
2525        // stays in the reachable source/destination domains.
2526        for axis in 0..cursor.shape.len() {
2527            let next = self.coords.as_mut_slice()[axis] + 1;
2528            if next < cursor.shape[axis] {
2529                self.coords.as_mut_slice()[axis] = next;
2530                self.source_offset += cursor.source_steps[axis];
2531                self.dest_offset += cursor.dest_steps[axis];
2532                return;
2533            }
2534            self.coords.as_mut_slice()[axis] = 0;
2535            self.source_offset += cursor.source_resets[axis];
2536            self.dest_offset += cursor.dest_resets[axis];
2537        }
2538    }
2539}
2540
2541struct CoordScratch {
2542    inline: [usize; crate::RAW_FUSED_RANK_LIMIT],
2543    heap: Option<Vec<usize>>,
2544    len: usize,
2545}
2546
2547impl CoordScratch {
2548    fn new(len: usize) -> Self {
2549        if len <= crate::RAW_FUSED_RANK_LIMIT {
2550            Self {
2551                inline: [0; crate::RAW_FUSED_RANK_LIMIT],
2552                heap: None,
2553                len,
2554            }
2555        } else {
2556            Self {
2557                inline: [0; crate::RAW_FUSED_RANK_LIMIT],
2558                heap: Some(vec![0; len]),
2559                len,
2560            }
2561        }
2562    }
2563
2564    fn as_mut_slice(&mut self) -> &mut [usize] {
2565        match &mut self.heap {
2566            Some(heap) => heap,
2567            None => &mut self.inline[..self.len],
2568        }
2569    }
2570}
2571
2572#[cfg(test)]
2573#[path = "static_indexing_plan/tests/tests.rs"]
2574mod tests;
2575
2576#[cfg(test)]
2577#[path = "static_indexing_plan/tests/parallel_tests.rs"]
2578mod parallel_tests;