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