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    #[allow(clippy::too_many_arguments)]
646    unsafe fn write_axis0_columns_raw<T, const UNINIT: bool>(
647        &self,
648        dest_ptr: *mut T,
649        dest_offset: isize,
650        operand_ptr: *const T,
651        operand_offset: isize,
652        fill: T,
653        columns: &ContiguousPadAxis0Columns,
654        exec: Exec<'_>,
655    ) -> Result<()>
656    where
657        T: Copy + Send + Sync,
658    {
659        let column_total = columns.column_total;
660        if column_total == 0 {
661            return Ok(());
662        }
663        let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.dest_total);
664        {
665            if exec.budget().get() > 1 && column_total >= exec.budget().get() {
666                let dest_ptr = crate::threading::SendPtr(dest_ptr);
667                let operand_ptr = crate::threading::SendPtr(operand_ptr as *mut T);
668                return crate::threading::parallel_map_reduce(
669                    0..column_total,
670                    exec,
671                    &|range| {
672                        let mut outer_idx_storage =
673                            CoordScratch::new(columns.dest_outer_dims.len());
674                        let outer_idx = outer_idx_storage.as_mut_slice();
675                        fill_col_major_index(range.start, &columns.dest_outer_dims, outer_idx);
676                        // SAFETY: worker ranges are disjoint; the destination
677                        // is dense column-major, so distinct columns occupy
678                        // disjoint contiguous slots, and the caller's contract
679                        // covers every reachable slot. Padding-only columns
680                        // never read the operand.
681                        unsafe {
682                            self.write_axis0_columns_range::<T, UNINIT>(
683                                dest_ptr.as_ptr(),
684                                dest_offset,
685                                operand_ptr.as_const(),
686                                operand_offset,
687                                fill,
688                                columns,
689                                outer_idx,
690                                range.start,
691                                range.len(),
692                                Exec::serial(),
693                            )
694                        }
695                    },
696                    &|left, right| left.and(right),
697                );
698            }
699        }
700        let mut outer_idx_storage = CoordScratch::new(columns.dest_outer_dims.len());
701        let outer_idx = outer_idx_storage.as_mut_slice();
702        // SAFETY: forwarded from this function's contract.
703        unsafe {
704            self.write_axis0_columns_range::<T, UNINIT>(
705                dest_ptr,
706                dest_offset,
707                operand_ptr,
708                operand_offset,
709                fill,
710                columns,
711                outer_idx,
712                0,
713                column_total,
714                exec,
715            )
716        }
717    }
718
719    /// Write `count` destination columns starting at linear column
720    /// `column_start`, advancing `outer_idx` in place.
721    ///
722    /// # Safety
723    ///
724    /// As for [`Self::write_axis0_columns_raw`], and no other thread may write
725    /// the destination columns visited by this call.
726    #[allow(clippy::too_many_arguments)]
727    unsafe fn write_axis0_columns_range<T, const UNINIT: bool>(
728        &self,
729        dest_ptr: *mut T,
730        dest_offset: isize,
731        operand_ptr: *const T,
732        operand_offset: isize,
733        fill: T,
734        columns: &ContiguousPadAxis0Columns,
735        outer_idx: &mut [usize],
736        column_start: usize,
737        count: usize,
738        mut exec: Exec<'_>,
739    ) -> Result<()>
740    where
741        T: Copy + Send + Sync,
742    {
743        if count == 0 {
744            return Ok(());
745        }
746        let mut dest_column_offset =
747            checked_offset_add(dest_offset, columns.dest_axis0_step, column_start)?;
748        // Carry the operand column offset and in-bounds count through the outer
749        // odometer instead of rescanning every outer axis per column. Only axes
750        // currently in bounds contribute a `stride * q` term, so every product
751        // is one the validated operand layout already produced.
752        let mut operand_column_offset = operand_offset;
753        let mut out_of_bounds = 0usize;
754        for (axis, &coord) in outer_idx.iter().enumerate() {
755            match in_bounds_outer_coord(columns, axis, coord) {
756                Some(q) => {
757                    operand_column_offset = checked_offset_add(
758                        operand_column_offset,
759                        columns.operand_outer_strides[axis],
760                        q,
761                    )?;
762                }
763                None => out_of_bounds += 1,
764            }
765        }
766        for _ in 0..count {
767            if out_of_bounds == 0 {
768                let low_len = columns.low0;
769                let run_len = columns.run_len;
770                let high_len = columns.high0;
771                // SAFETY: the compiled run span and the dense column layout
772                // place the low pad, operand run, and high pad at disjoint
773                // offsets inside this column; the operand run was validated by
774                // the descriptor bounds and `run_len` copies only in-bounds
775                // axis-0 elements. The destination layout is injective and
776                // this call owns the whole column.
777                unsafe {
778                    if UNINIT {
779                        fill_raw_span_uninit(
780                            dest_ptr.offset(dest_column_offset),
781                            low_len,
782                            fill,
783                            exec.reborrow(),
784                        );
785                    } else {
786                        fill_raw_span(
787                            dest_ptr.offset(dest_column_offset),
788                            low_len,
789                            fill,
790                            exec.reborrow(),
791                        );
792                    }
793                    crate::threading::copy_contiguous(
794                        operand_ptr.offset(operand_column_offset),
795                        dest_ptr.offset(dest_column_offset + low_len as isize),
796                        run_len,
797                        exec.reborrow(),
798                    );
799                    if UNINIT {
800                        fill_raw_span_uninit(
801                            dest_ptr
802                                .offset(dest_column_offset + low_len as isize + run_len as isize),
803                            high_len,
804                            fill,
805                            exec.reborrow(),
806                        );
807                    } else {
808                        fill_raw_span(
809                            dest_ptr
810                                .offset(dest_column_offset + low_len as isize + run_len as isize),
811                            high_len,
812                            fill,
813                            exec.reborrow(),
814                        );
815                    }
816                }
817            } else {
818                // SAFETY: as for the in-bounds branch; a padding-only column
819                // never reads the operand.
820                unsafe {
821                    if UNINIT {
822                        fill_raw_span_uninit(
823                            dest_ptr.offset(dest_column_offset),
824                            columns.dest_axis0_len,
825                            fill,
826                            exec.reborrow(),
827                        );
828                    } else {
829                        fill_raw_span(
830                            dest_ptr.offset(dest_column_offset),
831                            columns.dest_axis0_len,
832                            fill,
833                            exec.reborrow(),
834                        );
835                    }
836                }
837            }
838            // Advance the destination column, the outer odometer, and the
839            // incremental operand offset / in-bounds count together.
840            dest_column_offset = dest_column_offset
841                .checked_add(columns.dest_axis0_step)
842                .ok_or(StridedError::OffsetOverflow)?;
843            for (axis, coord) in outer_idx.iter_mut().enumerate() {
844                let was_in_bounds = in_bounds_outer_coord(columns, axis, *coord);
845                if let Some(q) = was_in_bounds {
846                    let q = isize::try_from(q).map_err(|_| StridedError::OffsetOverflow)?;
847                    let scaled = columns.operand_outer_strides[axis]
848                        .checked_mul(q)
849                        .ok_or(StridedError::OffsetOverflow)?;
850                    operand_column_offset = operand_column_offset
851                        .checked_sub(scaled)
852                        .ok_or(StridedError::OffsetOverflow)?;
853                }
854                *coord += 1;
855                let wrapped = *coord >= columns.dest_outer_dims[axis];
856                if wrapped {
857                    *coord = 0;
858                }
859                let is_in_bounds = in_bounds_outer_coord(columns, axis, *coord);
860                if let Some(q) = is_in_bounds {
861                    operand_column_offset = checked_offset_add(
862                        operand_column_offset,
863                        columns.operand_outer_strides[axis],
864                        q,
865                    )?;
866                }
867                match (was_in_bounds.is_some(), is_in_bounds.is_some()) {
868                    (false, true) => out_of_bounds -= 1,
869                    (true, false) => out_of_bounds += 1,
870                    _ => {}
871                }
872                if !wrapped {
873                    break;
874                }
875            }
876        }
877        Ok(())
878    }
879
880    /// Copy every in-bounds axis-0 run of the operand into the destination.
881    ///
882    /// With at least as many runs as workers (above the repository
883    /// threshold) the runs are split across workers; otherwise runs are
884    /// copied in order and each long run is chunked across workers by
885    /// [`crate::threading::copy_contiguous`].
886    ///
887    /// # Safety
888    ///
889    /// `dest_ptr` must be the data pointer of a destination whose layout is
890    /// exactly the compiled destination layout from `dest_offset`, valid for
891    /// writes to every reachable slot, with no concurrent access.
892    unsafe fn copy_axis0_runs_raw<T>(
893        &self,
894        dest_ptr: *mut T,
895        dest_offset: isize,
896        operand: &RawStridedRef<'_, T>,
897        run: ContiguousPadAxis0Run,
898        exec: Exec<'_>,
899    ) -> Result<()>
900    where
901        T: Copy + Send + Sync,
902    {
903        if run.len == 0 {
904            return Ok(());
905        }
906        let outer_dims = &self.operand_dims[1..];
907        let outer_total = checked_total_len(outer_dims)?;
908        let copied = outer_total.saturating_mul(run.len);
909        let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, copied);
910        {
911            if exec.budget().get() > 1 && outer_total >= exec.budget().get() {
912                let dest_ptr = crate::threading::SendPtr(dest_ptr);
913                return crate::threading::parallel_map_reduce(
914                    0..outer_total,
915                    exec,
916                    &|range| {
917                        let mut outer_idx_storage = CoordScratch::new(outer_dims.len());
918                        let outer_idx = outer_idx_storage.as_mut_slice();
919                        fill_col_major_index(range.start, outer_dims, outer_idx);
920                        // SAFETY: the caller's contract covers every run, and
921                        // disjoint outer ranges write disjoint runs because the
922                        // compiled destination layout is injective.
923                        unsafe {
924                            self.copy_axis0_run_range(
925                                dest_ptr.as_ptr(),
926                                dest_offset,
927                                operand,
928                                run,
929                                outer_idx,
930                                range.len(),
931                                Exec::serial(),
932                            )
933                        }
934                    },
935                    &|left, right| left.and(right),
936                );
937            }
938        }
939        let mut outer_idx_storage = CoordScratch::new(outer_dims.len());
940        let outer_idx = outer_idx_storage.as_mut_slice();
941        // SAFETY: forwarded from this function's contract.
942        unsafe {
943            self.copy_axis0_run_range(
944                dest_ptr,
945                dest_offset,
946                operand,
947                run,
948                outer_idx,
949                outer_total,
950                exec,
951            )
952        }
953    }
954
955    /// Copy `count` consecutive axis-0 runs starting at outer coordinate
956    /// `outer_idx` (column-major over axes `1..`), advancing it in place.
957    ///
958    /// # Safety
959    ///
960    /// As for [`Self::copy_axis0_runs_raw`], and no other thread may write the
961    /// destination runs visited by this call.
962    #[allow(clippy::too_many_arguments)]
963    unsafe fn copy_axis0_run_range<T>(
964        &self,
965        dest_ptr: *mut T,
966        dest_offset: isize,
967        operand: &RawStridedRef<'_, T>,
968        run: ContiguousPadAxis0Run,
969        outer_idx: &mut [usize],
970        count: usize,
971        mut exec: Exec<'_>,
972    ) -> Result<()>
973    where
974        T: Copy + Send + Sync,
975    {
976        let outer_dims = &self.operand_dims[1..];
977        let operand_ptr = operand.data().as_ptr();
978        for _ in 0..count {
979            let mut operand_offset =
980                checked_offset_add(operand.offset(), self.operand_strides[0], run.operand_start)?;
981            let mut dest_run_offset =
982                checked_offset_add(dest_offset, self.dest_strides[0], run.dest_start)?;
983            let mut in_bounds = true;
984            for (outer_axis, &coord) in outer_idx.iter().enumerate() {
985                let axis = outer_axis + 1;
986                let out_pos = i128::from(self.edge_padding_low[axis])
987                    + coord as i128 * i128::from(self.interior_step[axis]);
988                if out_pos < 0 || out_pos >= self.dest_dims[axis] as i128 {
989                    in_bounds = false;
990                    break;
991                }
992                operand_offset =
993                    checked_offset_add(operand_offset, self.operand_strides[axis], coord)?;
994                dest_run_offset =
995                    checked_offset_add(dest_run_offset, self.dest_strides[axis], out_pos as usize)?;
996            }
997            if in_bounds {
998                // SAFETY: compile requires unit axis-0 strides, the clipped
999                // run is in bounds of the validated operand and destination,
1000                // and the destination layout is injective. RawStridedMut's
1001                // exclusive borrow cannot overlap the RawStridedRef's shared
1002                // borrow in safe Rust.
1003                unsafe {
1004                    crate::threading::copy_contiguous(
1005                        operand_ptr.offset(operand_offset),
1006                        dest_ptr.offset(dest_run_offset),
1007                        run.len,
1008                        exec.reborrow(),
1009                    );
1010                }
1011            }
1012            advance_col_major_index(outer_idx, outer_dims);
1013        }
1014        Ok(())
1015    }
1016
1017    #[cfg(test)]
1018    fn contiguous_axis0_run(&self) -> Option<(usize, usize, usize)> {
1019        self.contiguous_axis0_run
1020            .map(|run| (run.operand_start, run.dest_start, run.len))
1021    }
1022
1023    #[cfg(test)]
1024    fn has_contiguous_dest_fill(&self) -> bool {
1025        self.contiguous_dest_fill
1026    }
1027
1028    #[cfg(test)]
1029    fn has_contiguous_axis0_columns(&self) -> bool {
1030        self.contiguous_axis0_columns.is_some()
1031    }
1032
1033    fn fill_dest_serial<T>(&self, dest: &mut RawStridedMut<'_, T>, fill: T) -> Result<()>
1034    where
1035        T: Copy,
1036    {
1037        let dest_ptr = dest.data_mut().as_mut_ptr();
1038        let mut cursor = PadFillState::new(dest.offset(), &self.dest_dims, &self.generic_fill);
1039        for _ in 0..self.dest_total {
1040            unsafe {
1041                // INVARIANT: compile-time checked fill spans, validated raw
1042                // descriptors, and exact plan-layout equality prove this is a
1043                // reachable destination offset.
1044                *dest_ptr.offset(cursor.offset) = fill;
1045            }
1046            cursor.advance(&self.dest_dims, &self.generic_fill);
1047        }
1048        Ok(())
1049    }
1050
1051    fn fill_dest_parallel<T>(
1052        &self,
1053        dest: &mut RawStridedMut<'_, T>,
1054        fill: T,
1055        exec: Exec<'_>,
1056    ) -> Result<()>
1057    where
1058        T: Copy + Send + Sync,
1059    {
1060        let dest_offset_base = dest.offset();
1061        let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1062        crate::threading::parallel_map_reduce(
1063            0..self.dest_total,
1064            exec,
1065            &|range| {
1066                let mut cursor = PadFillState::decode(
1067                    range.start,
1068                    dest_offset_base,
1069                    &self.dest_dims,
1070                    &self.generic_fill,
1071                )?;
1072                let dest_ptr = dest_ptr.as_ptr();
1073                for _ in range {
1074                    unsafe {
1075                        // INVARIANT: compile-time checked fill spans, validated
1076                        // raw descriptors, exact layout equality, and disjoint
1077                        // positive logical partition mapping prove this offset
1078                        // is reachable and uniquely owned by this range.
1079                        *dest_ptr.offset(cursor.offset) = fill;
1080                    }
1081                    cursor.advance(&self.dest_dims, &self.generic_fill);
1082                }
1083                Ok(())
1084            },
1085            &|left, right| left.and(right),
1086        )
1087    }
1088
1089    fn copy_operand<T>(
1090        &self,
1091        dest: &mut RawStridedMut<'_, T>,
1092        operand: &RawStridedRef<'_, T>,
1093        exec: Exec<'_>,
1094    ) -> Result<()>
1095    where
1096        T: Copy + Send + Sync,
1097    {
1098        let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.generic_copy.total);
1099        if !exec.is_serial() {
1100            return self.copy_operand_parallel(dest, operand, exec);
1101        }
1102        self.copy_operand_serial(dest, operand)
1103    }
1104
1105    fn copy_operand_uninit<T>(
1106        &self,
1107        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1108        operand: &RawStridedRef<'_, T>,
1109        exec: Exec<'_>,
1110    ) -> Result<()>
1111    where
1112        T: Copy + Send + Sync,
1113    {
1114        let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.generic_copy.total);
1115        if !exec.is_serial() {
1116            return self.copy_operand_uninit_parallel(dest, operand, exec);
1117        }
1118        self.copy_operand_uninit_serial(dest, operand)
1119    }
1120
1121    fn copy_operand_uninit_serial<T>(
1122        &self,
1123        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1124        operand: &RawStridedRef<'_, T>,
1125    ) -> Result<()>
1126    where
1127        T: Copy,
1128    {
1129        if self.generic_copy.total == 0 {
1130            return Ok(());
1131        }
1132        let operand_ptr = operand.data().as_ptr();
1133        let dest_ptr = dest.data_mut().as_mut_ptr();
1134        let source_base = operand
1135            .offset()
1136            .checked_add(self.generic_copy.source_base_delta)
1137            .ok_or(StridedError::OffsetOverflow)?;
1138        let dest_base = dest
1139            .offset()
1140            .checked_add(self.generic_copy.dest_base_delta)
1141            .ok_or(StridedError::OffsetOverflow)?;
1142        let mut cursor = PadCopyState::new(source_base, dest_base, &self.generic_copy);
1143        for _ in 0..self.generic_copy.total {
1144            // SAFETY: `PadPlan::compile` (:337) proved the destination layout
1145            // injective and `dest_dims` equal to the padded extents, and
1146            // `compile_pad_copy_cursor` (:1883) clamped each copied operand interval
1147            // to `[0, operand_dims[axis])` (`checked_pad_valid_interval`, :1955) while
1148            // computing `source_base_delta`/`dest_base_delta` and both step sets with
1149            // checked arithmetic and a checked offset span; `check_call` (:1300)
1150            // re-proved both layouts equal to the compiled ones, and the bases above
1151            // are re-checked against `isize`, so both cursor offsets stay inside the
1152            // buffers `validate_bounds` accepted for `operand`/`dest`.
1153            unsafe {
1154                // INVARIANT: compile-time checked copy spans/base deltas,
1155                // validated raw descriptors, and exact plan-layout equality
1156                // prove both offsets reachable; positive steps make destinations
1157                // injective, so no copy aliases another cursor position.
1158                (*dest_ptr.offset(cursor.dest_offset))
1159                    .write(*operand_ptr.offset(cursor.source_offset));
1160            }
1161            cursor.advance(&self.generic_copy);
1162        }
1163        Ok(())
1164    }
1165
1166    fn copy_operand_uninit_parallel<T>(
1167        &self,
1168        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1169        operand: &RawStridedRef<'_, T>,
1170        exec: Exec<'_>,
1171    ) -> Result<()>
1172    where
1173        T: Copy + Send + Sync,
1174    {
1175        let operand_base = operand
1176            .offset()
1177            .checked_add(self.generic_copy.source_base_delta)
1178            .ok_or(StridedError::OffsetOverflow)?;
1179        let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
1180        let dest_base = dest
1181            .offset()
1182            .checked_add(self.generic_copy.dest_base_delta)
1183            .ok_or(StridedError::OffsetOverflow)?;
1184        let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1185        crate::threading::parallel_map_reduce(
1186            0..self.generic_copy.total,
1187            exec,
1188            &|range| {
1189                let mut cursor =
1190                    PadCopyState::decode(range.start, operand_base, dest_base, &self.generic_copy)?;
1191                let operand_ptr = operand_ptr.as_const();
1192                let dest_ptr = dest_ptr.as_ptr();
1193
1194                for _ in range {
1195                    // SAFETY: `PadPlan::compile` (:337) proved the destination layout
1196                    // injective and `dest_dims` equal to the padded extents, and
1197                    // `compile_pad_copy_cursor` (:1883) clamped each copied operand interval
1198                    // to `[0, operand_dims[axis])` (`checked_pad_valid_interval`, :1955) while
1199                    // computing `source_base_delta`/`dest_base_delta` and both step sets with
1200                    // checked arithmetic and a checked offset span; `check_call` (:1300)
1201                    // re-proved both layouts equal to the compiled ones, and the bases above
1202                    // are re-checked against `isize`, so both cursor offsets stay inside the
1203                    // buffers `validate_bounds` accepted for `operand`/`dest`.
1204                    unsafe {
1205                        // INVARIANT: compile-time checked copy spans/base
1206                        // deltas, validated descriptors, exact layout equality,
1207                        // and positive injective mapping prove disjoint,
1208                        // reachable source/destination offsets per range.
1209                        (*dest_ptr.offset(cursor.dest_offset))
1210                            .write(*operand_ptr.offset(cursor.source_offset));
1211                    }
1212                    cursor.advance(&self.generic_copy);
1213                }
1214                Ok(())
1215            },
1216            &|left, right| left.and(right),
1217        )
1218    }
1219
1220    fn copy_operand_serial<T>(
1221        &self,
1222        dest: &mut RawStridedMut<'_, T>,
1223        operand: &RawStridedRef<'_, T>,
1224    ) -> Result<()>
1225    where
1226        T: Copy,
1227    {
1228        if self.generic_copy.total == 0 {
1229            return Ok(());
1230        }
1231        let operand_ptr = operand.data().as_ptr();
1232        let dest_ptr = dest.data_mut().as_mut_ptr();
1233        let source_base = operand
1234            .offset()
1235            .checked_add(self.generic_copy.source_base_delta)
1236            .ok_or(StridedError::OffsetOverflow)?;
1237        let dest_base = dest
1238            .offset()
1239            .checked_add(self.generic_copy.dest_base_delta)
1240            .ok_or(StridedError::OffsetOverflow)?;
1241        let mut cursor = PadCopyState::new(source_base, dest_base, &self.generic_copy);
1242        for _ in 0..self.generic_copy.total {
1243            unsafe {
1244                // INVARIANT: compile-time checked copy spans/base deltas,
1245                // validated raw descriptors, and exact plan-layout equality
1246                // prove both offsets reachable; positive steps make destinations
1247                // injective, so no copy aliases another cursor position.
1248                *dest_ptr.offset(cursor.dest_offset) = *operand_ptr.offset(cursor.source_offset);
1249            }
1250            cursor.advance(&self.generic_copy);
1251        }
1252        Ok(())
1253    }
1254
1255    fn copy_operand_parallel<T>(
1256        &self,
1257        dest: &mut RawStridedMut<'_, T>,
1258        operand: &RawStridedRef<'_, T>,
1259        exec: Exec<'_>,
1260    ) -> Result<()>
1261    where
1262        T: Copy + Send + Sync,
1263    {
1264        let operand_base = operand
1265            .offset()
1266            .checked_add(self.generic_copy.source_base_delta)
1267            .ok_or(StridedError::OffsetOverflow)?;
1268        let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
1269        let dest_base = dest
1270            .offset()
1271            .checked_add(self.generic_copy.dest_base_delta)
1272            .ok_or(StridedError::OffsetOverflow)?;
1273        let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1274        crate::threading::parallel_map_reduce(
1275            0..self.generic_copy.total,
1276            exec,
1277            &|range| {
1278                let mut cursor =
1279                    PadCopyState::decode(range.start, operand_base, dest_base, &self.generic_copy)?;
1280                let operand_ptr = operand_ptr.as_const();
1281                let dest_ptr = dest_ptr.as_ptr();
1282
1283                for _ in range {
1284                    unsafe {
1285                        // INVARIANT: compile-time checked copy spans/base
1286                        // deltas, validated descriptors, exact layout equality,
1287                        // and positive injective mapping prove disjoint,
1288                        // reachable source/destination offsets per range.
1289                        *dest_ptr.offset(cursor.dest_offset) =
1290                            *operand_ptr.offset(cursor.source_offset);
1291                    }
1292                    cursor.advance(&self.generic_copy);
1293                }
1294                Ok(())
1295            },
1296            &|left, right| left.and(right),
1297        )
1298    }
1299
1300    fn check_call<D, T>(
1301        &self,
1302        dest: &RawStridedMut<'_, D>,
1303        operand: &RawStridedRef<'_, T>,
1304    ) -> Result<()> {
1305        if operand.dims() != &self.operand_dims[..]
1306            || operand.strides() != &self.operand_strides[..]
1307            || dest.dims() != &self.dest_dims[..]
1308            || dest.strides() != &self.dest_strides[..]
1309        {
1310            return Err(StridedError::PlanLayoutMismatch);
1311        }
1312        Ok(())
1313    }
1314}
1315
1316impl ConcatenatePlan {
1317    /// Compile a multi-input concatenate plan for fixed input and destination layouts.
1318    ///
1319    /// # Errors
1320    ///
1321    /// Returns [`StridedError::UnsupportedArity`] when no input is given, and
1322    /// [`StridedError::RankMismatch`] when the dims and strides lists
1323    /// disagree in length or an input's rank differs from the first
1324    /// input's. Returns [`StridedError::StrideLengthMismatch`] when the
1325    /// destination or an input stride list does not match the rank,
1326    /// [`StridedError::InvalidAxis`] when `axis` is out of range, and
1327    /// [`StridedError::ShapeMismatch`] when an input disagrees with the first
1328    /// input off `axis` or the destination dims are not the concatenated
1329    /// extents. Returns [`StridedError::NonInjectiveOutputLayout`] when two
1330    /// destination elements map onto one offset or the layout span is not
1331    /// representable, and
1332    /// [`StridedError::OffsetOverflow`] when a segment total, a segment start
1333    /// or a destination offset overflows.
1334    pub fn compile(
1335        input_dims: &[&[usize]],
1336        input_strides: &[&[isize]],
1337        dest_dims: &[usize],
1338        dest_strides: &[isize],
1339        axis: usize,
1340    ) -> Result<Self> {
1341        if input_dims.is_empty() {
1342            return Err(StridedError::UnsupportedArity {
1343                arity: 0,
1344                max: usize::MAX,
1345            });
1346        }
1347        if input_dims.len() != input_strides.len() {
1348            return Err(StridedError::RankMismatch(
1349                input_strides.len(),
1350                input_dims.len(),
1351            ));
1352        }
1353
1354        let rank = input_dims[0].len();
1355        if dest_dims.len() != rank || dest_strides.len() != rank {
1356            return Err(StridedError::StrideLengthMismatch);
1357        }
1358        if axis >= rank {
1359            return Err(StridedError::InvalidAxis { axis, rank });
1360        }
1361        checked_total_len(dest_dims)?;
1362        if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
1363            return Err(StridedError::NonInjectiveOutputLayout);
1364        }
1365
1366        let mut expected_dest_dims: AxisVec<usize> = input_dims[0].into();
1367        expected_dest_dims[axis] = 0;
1368        let mut stored_input_dims = crate::inline::OperandVec::with_capacity(input_dims.len());
1369        let mut stored_input_strides = crate::inline::OperandVec::with_capacity(input_dims.len());
1370        let mut dest_offset_deltas = crate::inline::OperandVec::with_capacity(input_dims.len());
1371        let mut copy_plans = crate::inline::OperandVec::with_capacity(input_dims.len());
1372        let mut segment_starts = crate::inline::OperandVec::with_capacity(input_dims.len() + 1);
1373        segment_starts.push(0usize);
1374        let mut axis_base = 0usize;
1375
1376        for (dims, strides) in input_dims.iter().zip(input_strides.iter()) {
1377            if dims.len() != rank {
1378                return Err(StridedError::RankMismatch(dims.len(), rank));
1379            }
1380            if strides.len() != rank {
1381                return Err(StridedError::StrideLengthMismatch);
1382            }
1383            let segment_total = checked_total_len(dims)?;
1384            let segment_end = segment_starts[segment_starts.len() - 1]
1385                .checked_add(segment_total)
1386                .ok_or(StridedError::OffsetOverflow)?;
1387            segment_starts.push(segment_end);
1388            for dim in 0..rank {
1389                if dim == axis {
1390                    expected_dest_dims[axis] = expected_dest_dims[axis]
1391                        .checked_add(dims[axis])
1392                        .ok_or(StridedError::OffsetOverflow)?;
1393                } else if dims[dim] != input_dims[0][dim] {
1394                    return Err(StridedError::ShapeMismatch(
1395                        dims.to_vec(),
1396                        input_dims[0].to_vec(),
1397                    ));
1398                }
1399            }
1400            dest_offset_deltas.push(checked_offset_add(0, dest_strides[axis], axis_base)?);
1401            axis_base = axis_base
1402                .checked_add(dims[axis])
1403                .ok_or(StridedError::OffsetOverflow)?;
1404            copy_plans.push(CopyPlan::compile(dims, dest_strides, strides)?);
1405            stored_input_dims.push((*dims).into());
1406            stored_input_strides.push((*strides).into());
1407        }
1408
1409        if dest_dims != &expected_dest_dims[..] {
1410            return Err(StridedError::ShapeMismatch(
1411                dest_dims.to_vec(),
1412                expected_dest_dims.to_vec(),
1413            ));
1414        }
1415
1416        Ok(Self {
1417            input_dims: stored_input_dims,
1418            input_strides: stored_input_strides,
1419            dest_dims: dest_dims.into(),
1420            dest_strides: dest_strides.into(),
1421            dest_offset_deltas,
1422            segment_starts,
1423            copy_plans,
1424        })
1425    }
1426
1427    /// Execute the prepared concatenate traversal.
1428    ///
1429    /// # Errors
1430    ///
1431    /// Returns [`StridedError::PlanLayoutMismatch`] when the destination or
1432    /// an input view does not carry its compiled layout,
1433    /// [`StridedError::RankMismatch`] when the number of inputs differs from
1434    /// the compiled input count, and [`StridedError::OffsetOverflow`] when a
1435    /// segment destination offset overflows.
1436    pub fn execute<T>(
1437        &self,
1438        dest: &mut RawStridedMut<'_, T>,
1439        inputs: &[RawStridedRef<'_, T>],
1440        exec: Exec<'_>,
1441    ) -> Result<()>
1442    where
1443        T: Copy + Send + Sync,
1444    {
1445        let mut exec = exec;
1446        self.check_dest_layout(dest)?;
1447        if inputs.len() != self.input_dims.len() {
1448            return Err(StridedError::RankMismatch(
1449                inputs.len(),
1450                self.input_dims.len(),
1451            ));
1452        }
1453        for (position, input) in inputs.iter().enumerate() {
1454            self.check_input_layout(position, input)?;
1455            self.segment_offset(position, dest.offset())?;
1456        }
1457        if self.try_execute_parallel(
1458            dest,
1459            inputs,
1460            |dst: &mut T, value| *dst = value,
1461            exec.reborrow(),
1462        )? {
1463            return Ok(());
1464        }
1465        for (position, input) in inputs.iter().enumerate() {
1466            self.execute_segment(position, dest, input, exec.reborrow())?;
1467        }
1468        Ok(())
1469    }
1470
1471    /// Execute concatenate into storage whose reachable destination elements are uninitialized.
1472    ///
1473    /// # Errors
1474    ///
1475    /// Returns [`StridedError::PlanLayoutMismatch`] when the destination or
1476    /// an input view does not carry its compiled layout,
1477    /// [`StridedError::RankMismatch`] when the number of inputs differs from
1478    /// the compiled input count, and [`StridedError::OffsetOverflow`] when a
1479    /// segment destination offset overflows.
1480    pub fn execute_uninit<T>(
1481        &self,
1482        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1483        inputs: &[RawStridedRef<'_, T>],
1484        exec: Exec<'_>,
1485    ) -> Result<()>
1486    where
1487        T: Copy + Send + Sync,
1488    {
1489        let mut exec = exec;
1490        self.check_dest_layout(dest)?;
1491        if inputs.len() != self.input_dims.len() {
1492            return Err(StridedError::RankMismatch(
1493                inputs.len(),
1494                self.input_dims.len(),
1495            ));
1496        }
1497        for (position, input) in inputs.iter().enumerate() {
1498            self.check_input_layout(position, input)?;
1499            self.segment_offset(position, dest.offset())?;
1500        }
1501        if self.try_execute_parallel(
1502            dest,
1503            inputs,
1504            |dst: &mut MaybeUninit<T>, value| {
1505                dst.write(value);
1506            },
1507            exec.reborrow(),
1508        )? {
1509            return Ok(());
1510        }
1511        for (position, input) in inputs.iter().enumerate() {
1512            self.execute_segment_uninit(position, dest, input, exec.reborrow())?;
1513        }
1514        Ok(())
1515    }
1516
1517    /// Replay all segments as one logical index space split across workers.
1518    ///
1519    /// Splitting the concatenated space (instead of fanning out per segment)
1520    /// keeps many small segments parallel as a group and splits a large
1521    /// segment across workers, with one fork-join for the whole call. Returns
1522    /// `Ok(false)` without writing when the serial per-segment path must run:
1523    /// the destination is at most the repository threshold, the budget
1524    /// allows one thread, or a segment exceeds the fused-rank limit.
1525    ///
1526    /// The caller must have validated every input layout and segment offset.
1527    fn try_execute_parallel<D, T, Apply>(
1528        &self,
1529        dest: &mut RawStridedMut<'_, D>,
1530        inputs: &[RawStridedRef<'_, T>],
1531        apply: Apply,
1532        exec: Exec<'_>,
1533    ) -> Result<bool>
1534    where
1535        D: Copy + Send + Sync,
1536        T: Copy + Send + Sync,
1537        Apply: Fn(&mut D, T) + Send + Sync,
1538    {
1539        let total = self.segment_starts[self.segment_starts.len() - 1];
1540        let exec = crate::cost::for_len(exec, KernelClass::Copy, total);
1541        if exec.is_serial() {
1542            return Ok(false);
1543        }
1544        // Precompute each segment's destination base offset once into an
1545        // inline operand vector (allocation-free within the operand bound);
1546        // the per-segment descriptors are read straight from `self`/`inputs`
1547        // inside the loop, so the parallel replay allocates nothing.
1548        let mut dest_offsets: crate::inline::OperandVec<isize> =
1549            crate::inline::OperandVec::with_capacity(inputs.len());
1550        for position in 0..inputs.len() {
1551            if self.copy_plans[position].fused_layout().is_none() {
1552                return Ok(false);
1553            }
1554            dest_offsets.push(self.segment_offset(position, dest.offset())?);
1555        }
1556        let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1557        let starts = &self.segment_starts;
1558        let dest_offsets = &dest_offsets;
1559        crate::threading::parallel_for_each(0..total, exec, &|range| {
1560            // First segment whose end lies past the range start.
1561            let mut position = starts[1..].partition_point(|&end| end <= range.start);
1562            while position < inputs.len() && starts[position] < range.end {
1563                let local_start = range.start.max(starts[position]) - starts[position];
1564                let local_end = range.end.min(starts[position + 1]) - starts[position];
1565                // The whole-plan guard above proved every segment has an
1566                // inline fused layout; skip one only if a future caller
1567                // relaxes that check.
1568                let Some(layout) = self.copy_plans[position].fused_layout() else {
1569                    position += 1;
1570                    continue;
1571                };
1572                let input = &inputs[position];
1573                // SAFETY: `check_dest_layout`/`check_input_layout` proved the
1574                // views carry the compiled layouts, so each segment window
1575                // (input dims, destination strides, checked segment offset) is
1576                // a sub-layout of the validated destination and each input
1577                // layout is in-bounds of its data. The destination layout is
1578                // injective and the segments occupy disjoint ranges of the
1579                // concatenation axis, so disjoint logical ranges write
1580                // disjoint slots; inputs are shared borrows that cannot alias
1581                // the exclusive destination borrow.
1582                unsafe {
1583                    crate::raw_ops::apply_fused_range(
1584                        dest_ptr.as_ptr(),
1585                        dest_offsets[position],
1586                        input.data().as_ptr(),
1587                        input.offset(),
1588                        layout,
1589                        local_start,
1590                        local_end - local_start,
1591                        &apply,
1592                    );
1593                }
1594                position += 1;
1595            }
1596        });
1597        Ok(true)
1598    }
1599
1600    pub(crate) fn check_dest_layout<T>(&self, dest: &RawStridedMut<'_, T>) -> Result<()> {
1601        if dest.dims() != &self.dest_dims[..] || dest.strides() != &self.dest_strides[..] {
1602            return Err(StridedError::PlanLayoutMismatch);
1603        }
1604        Ok(())
1605    }
1606
1607    pub(crate) fn check_input_layout<T>(
1608        &self,
1609        position: usize,
1610        input: &RawStridedRef<'_, T>,
1611    ) -> Result<()> {
1612        if position >= self.input_dims.len()
1613            || input.dims() != &self.input_dims[position][..]
1614            || input.strides() != &self.input_strides[position][..]
1615        {
1616            return Err(StridedError::PlanLayoutMismatch);
1617        }
1618        Ok(())
1619    }
1620
1621    pub(crate) fn input_count(&self) -> usize {
1622        self.input_dims.len()
1623    }
1624
1625    /// Whether the whole-plan entry would replay in parallel within the
1626    /// budget of `exec`. Erased callers use it to keep the allocation-free
1627    /// per-segment loop for serial execution.
1628    pub(crate) fn prefers_whole_plan(&self, exec: &Exec<'_>) -> bool {
1629        let total = self.segment_starts[self.segment_starts.len() - 1];
1630        crate::threading::is_parallel(KernelClass::Copy, total, exec)
1631    }
1632
1633    pub(crate) fn segment_offset(&self, position: usize, dest_offset: isize) -> Result<isize> {
1634        dest_offset
1635            .checked_add(self.dest_offset_deltas[position])
1636            .ok_or(StridedError::OffsetOverflow)
1637    }
1638
1639    pub(crate) fn execute_segment<T>(
1640        &self,
1641        position: usize,
1642        dest: &mut RawStridedMut<'_, T>,
1643        input: &RawStridedRef<'_, T>,
1644        exec: Exec<'_>,
1645    ) -> Result<()>
1646    where
1647        T: Copy + Send + Sync,
1648    {
1649        let segment_offset = self.segment_offset(position, dest.offset())?;
1650        let dest_data = dest.data_mut();
1651        let mut segment = unsafe {
1652            RawStridedMut::new_unchecked(
1653                dest_data,
1654                &self.input_dims[position],
1655                &self.dest_strides,
1656                segment_offset,
1657            )
1658        };
1659        self.copy_plans[position].execute(&mut segment, input, exec)
1660    }
1661
1662    pub(crate) fn execute_segment_uninit<T>(
1663        &self,
1664        position: usize,
1665        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1666        input: &RawStridedRef<'_, T>,
1667        exec: Exec<'_>,
1668    ) -> Result<()>
1669    where
1670        T: Copy + Send + Sync,
1671    {
1672        let segment_offset = self.segment_offset(position, dest.offset())?;
1673        let dest_data = dest.data_mut();
1674        let mut segment = unsafe {
1675            RawStridedMut::new_unchecked(
1676                dest_data,
1677                &self.input_dims[position],
1678                &self.dest_strides,
1679                segment_offset,
1680            )
1681        };
1682        self.copy_plans[position].execute_uninit(&mut segment, input, exec)
1683    }
1684}
1685
1686impl ReversePlan {
1687    /// Compile a reverse plan for one operand layout, destination layout, and axis set.
1688    ///
1689    /// # Errors
1690    ///
1691    /// Returns [`StridedError::StrideLengthMismatch`] when the operand or
1692    /// destination stride list does not match the operand rank,
1693    /// [`StridedError::InvalidAxis`] when a listed axis is out of range, and
1694    /// [`StridedError::NonInjectiveOutputLayout`] when two destination
1695    /// elements map onto one offset, or the layout span is not representable.
1696    /// Returns
1697    /// [`StridedError::OffsetOverflow`] when an element count, a negated
1698    /// source stride or the source offset delta overflows.
1699    pub fn compile(
1700        operand_dims: &[usize],
1701        operand_strides: &[isize],
1702        dest_strides: &[isize],
1703        axes: &[usize],
1704    ) -> Result<Self> {
1705        let rank = operand_dims.len();
1706        if operand_strides.len() != rank || dest_strides.len() != rank {
1707            return Err(StridedError::StrideLengthMismatch);
1708        }
1709        checked_total_len(operand_dims)?;
1710
1711        let mut reverse_axis: AxisVec<bool> = (0..rank).map(|_| false).collect();
1712        for &axis in axes {
1713            if axis >= rank {
1714                return Err(StridedError::InvalidAxis { axis, rank });
1715            }
1716            reverse_axis[axis] = true;
1717        }
1718
1719        let mut source_strides: AxisVec<isize> = AxisVec::with_capacity(rank);
1720        let mut source_offset_delta = 0isize;
1721        for axis in 0..rank {
1722            if reverse_axis[axis] {
1723                source_strides.push(
1724                    operand_strides[axis]
1725                        .checked_neg()
1726                        .ok_or(StridedError::OffsetOverflow)?,
1727                );
1728                if operand_dims[axis] > 0 {
1729                    source_offset_delta = checked_offset_add(
1730                        source_offset_delta,
1731                        operand_strides[axis],
1732                        operand_dims[axis] - 1,
1733                    )?;
1734                }
1735            } else {
1736                source_strides.push(operand_strides[axis]);
1737            }
1738        }
1739        let copy_plan = CopyPlan::compile(operand_dims, dest_strides, &source_strides)?;
1740
1741        Ok(Self {
1742            operand_dims: operand_dims.into(),
1743            operand_strides: operand_strides.into(),
1744            dest_strides: dest_strides.into(),
1745            source_strides,
1746            source_offset_delta,
1747            copy_plan,
1748        })
1749    }
1750
1751    /// Execute the prepared reverse traversal.
1752    ///
1753    /// # Errors
1754    ///
1755    /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
1756    /// carry the compiled operand and destination layouts, and
1757    /// [`StridedError::OffsetOverflow`] when the operand offset plus the
1758    /// compiled source offset delta overflows.
1759    pub fn execute<T>(
1760        &self,
1761        dest: &mut RawStridedMut<'_, T>,
1762        operand: &RawStridedRef<'_, T>,
1763        exec: Exec<'_>,
1764    ) -> Result<()>
1765    where
1766        T: Copy + Send + Sync,
1767    {
1768        self.check_call(dest, operand)?;
1769        let source_offset = operand
1770            .offset()
1771            .checked_add(self.source_offset_delta)
1772            .ok_or(StridedError::OffsetOverflow)?;
1773        let source = unsafe {
1774            RawStridedRef::new_unchecked(
1775                operand.data(),
1776                &self.operand_dims,
1777                &self.source_strides,
1778                source_offset,
1779            )
1780        };
1781        self.copy_plan.execute(dest, &source, exec)
1782    }
1783
1784    /// Execute reverse into storage whose reachable destination elements are uninitialized.
1785    ///
1786    /// # Errors
1787    ///
1788    /// Returns [`StridedError::PlanLayoutMismatch`] when the views do not
1789    /// carry the compiled operand and destination layouts, and
1790    /// [`StridedError::OffsetOverflow`] when the operand offset plus the
1791    /// compiled source offset delta overflows.
1792    pub fn execute_uninit<T>(
1793        &self,
1794        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1795        operand: &RawStridedRef<'_, T>,
1796        exec: Exec<'_>,
1797    ) -> Result<()>
1798    where
1799        T: Copy + Send + Sync,
1800    {
1801        self.check_call(dest, operand)?;
1802        let source_offset = operand
1803            .offset()
1804            .checked_add(self.source_offset_delta)
1805            .ok_or(StridedError::OffsetOverflow)?;
1806        let source = unsafe {
1807            RawStridedRef::new_unchecked(
1808                operand.data(),
1809                &self.operand_dims,
1810                &self.source_strides,
1811                source_offset,
1812            )
1813        };
1814        self.copy_plan.execute_uninit(dest, &source, exec)
1815    }
1816
1817    fn check_call<D, T>(
1818        &self,
1819        dest: &RawStridedMut<'_, D>,
1820        operand: &RawStridedRef<'_, T>,
1821    ) -> Result<()> {
1822        if operand.dims() != &self.operand_dims[..]
1823            || operand.strides() != &self.operand_strides[..]
1824            || dest.dims() != &self.operand_dims[..]
1825            || dest.strides() != &self.dest_strides[..]
1826        {
1827            return Err(StridedError::PlanLayoutMismatch);
1828        }
1829        Ok(())
1830    }
1831}
1832
1833fn checked_total_len(dims: &[usize]) -> Result<usize> {
1834    if dims.is_empty() {
1835        return Ok(1);
1836    }
1837    dims.iter()
1838        .try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
1839        .ok_or(StridedError::OffsetOverflow)
1840}
1841
1842fn checked_stride_mul(stride: isize, factor: usize) -> Result<isize> {
1843    let factor = isize::try_from(factor).map_err(|_| StridedError::OffsetOverflow)?;
1844    stride
1845        .checked_mul(factor)
1846        .ok_or(StridedError::OffsetOverflow)
1847}
1848
1849fn checked_pad_output_dim(
1850    input_extent: usize,
1851    edge_low: i64,
1852    edge_high: i64,
1853    interior_step: i64,
1854    axis: usize,
1855    rank: usize,
1856) -> Result<usize> {
1857    let base = if input_extent == 0 {
1858        0i128
1859    } else {
1860        (input_extent as i128 - 1)
1861            .checked_mul(i128::from(interior_step))
1862            .and_then(|value| value.checked_add(1))
1863            .ok_or(StridedError::OffsetOverflow)?
1864    };
1865    let dim = i128::from(edge_low)
1866        .checked_add(i128::from(edge_high))
1867        .and_then(|value| value.checked_add(base))
1868        .ok_or(StridedError::OffsetOverflow)?;
1869    usize::try_from(dim).map_err(|_| StridedError::InvalidAxis { axis, rank })
1870}
1871
1872fn compile_pad_fill_cursor(dims: &[usize], strides: &[isize]) -> Result<PadFillCursor> {
1873    let mut steps = AxisVec::with_capacity(dims.len());
1874    let mut resets = AxisVec::with_capacity(dims.len());
1875    for (&dim, &stride) in dims.iter().zip(strides) {
1876        steps.push(stride);
1877        resets.push(checked_cursor_reset(stride, dim)?);
1878    }
1879    check_offset_span(dims, &steps)?;
1880    Ok(PadFillCursor { steps, resets })
1881}
1882
1883fn compile_pad_copy_cursor(
1884    operand_dims: &[usize],
1885    operand_strides: &[isize],
1886    dest_dims: &[usize],
1887    dest_strides: &[isize],
1888    edge_padding_low: &[i64],
1889    interior_step: &[i64],
1890) -> Result<PadCopyCursor> {
1891    let mut shape = AxisVec::with_capacity(operand_dims.len());
1892    let mut source_steps = AxisVec::with_capacity(operand_dims.len());
1893    let mut source_resets = AxisVec::with_capacity(operand_dims.len());
1894    let mut dest_steps = AxisVec::with_capacity(operand_dims.len());
1895    let mut dest_resets = AxisVec::with_capacity(operand_dims.len());
1896    let mut source_base_delta = 0isize;
1897    let mut dest_base_delta = 0isize;
1898    let mut copy_empty = false;
1899
1900    for axis in 0..operand_dims.len() {
1901        let (start, end) = checked_pad_valid_interval(
1902            operand_dims[axis],
1903            dest_dims[axis],
1904            edge_padding_low[axis],
1905            interior_step[axis],
1906        )?;
1907        let extent = end - start;
1908        shape.push(extent);
1909        if !copy_empty && extent != 0 {
1910            source_base_delta =
1911                checked_offset_add(source_base_delta, operand_strides[axis], start)?;
1912            let output_start = i128::from(edge_padding_low[axis])
1913                .checked_add(
1914                    i128::try_from(start)
1915                        .map_err(|_| StridedError::OffsetOverflow)?
1916                        .checked_mul(i128::from(interior_step[axis]))
1917                        .ok_or(StridedError::OffsetOverflow)?,
1918                )
1919                .ok_or(StridedError::OffsetOverflow)?;
1920            let output_start =
1921                usize::try_from(output_start).map_err(|_| StridedError::OffsetOverflow)?;
1922            dest_base_delta =
1923                checked_offset_add(dest_base_delta, dest_strides[axis], output_start)?;
1924        }
1925        copy_empty |= extent == 0;
1926
1927        let source_step = operand_strides[axis];
1928        let dest_step = checked_stride_mul_i64(dest_strides[axis], interior_step[axis])?;
1929        source_steps.push(source_step);
1930        source_resets.push(checked_cursor_reset(source_step, extent)?);
1931        dest_steps.push(dest_step);
1932        dest_resets.push(checked_cursor_reset(dest_step, extent)?);
1933    }
1934
1935    check_offset_span(&shape, &source_steps)?;
1936    check_offset_span(&shape, &dest_steps)?;
1937    let total = if shape.iter().any(|&extent| extent == 0) {
1938        0
1939    } else {
1940        checked_total_len(&shape)?
1941    };
1942
1943    Ok(PadCopyCursor {
1944        shape,
1945        source_base_delta,
1946        dest_base_delta,
1947        source_steps,
1948        source_resets,
1949        dest_steps,
1950        dest_resets,
1951        total,
1952    })
1953}
1954
1955fn checked_pad_valid_interval(
1956    input_extent: usize,
1957    dest_extent: usize,
1958    edge_low: i64,
1959    step: i64,
1960) -> Result<(usize, usize)> {
1961    if input_extent == 0 || dest_extent == 0 {
1962        return Ok((0, 0));
1963    }
1964    let step = i128::from(step);
1965    let lower = ceil_div_positive(-i128::from(edge_low), step)?;
1966    let dest_last = i128::try_from(dest_extent)
1967        .map_err(|_| StridedError::OffsetOverflow)?
1968        .checked_sub(1)
1969        .ok_or(StridedError::OffsetOverflow)?;
1970    let upper = floor_div_positive(
1971        dest_last
1972            .checked_sub(i128::from(edge_low))
1973            .ok_or(StridedError::OffsetOverflow)?,
1974        step,
1975    )?
1976    .checked_add(1)
1977    .ok_or(StridedError::OffsetOverflow)?;
1978    let input_extent = i128::try_from(input_extent).map_err(|_| StridedError::OffsetOverflow)?;
1979    let lower = lower.clamp(0, input_extent);
1980    let upper = upper.clamp(0, input_extent);
1981    if lower >= upper {
1982        return Ok((0, 0));
1983    }
1984    Ok((
1985        usize::try_from(lower).map_err(|_| StridedError::OffsetOverflow)?,
1986        usize::try_from(upper).map_err(|_| StridedError::OffsetOverflow)?,
1987    ))
1988}
1989
1990fn ceil_div_positive(numerator: i128, denominator: i128) -> Result<i128> {
1991    if denominator <= 0 {
1992        return Err(StridedError::OffsetOverflow);
1993    }
1994    let quotient = numerator.div_euclid(denominator);
1995    let remainder = numerator.rem_euclid(denominator);
1996    quotient
1997        .checked_add(i128::from(remainder != 0))
1998        .ok_or(StridedError::OffsetOverflow)
1999}
2000
2001fn floor_div_positive(numerator: i128, denominator: i128) -> Result<i128> {
2002    if denominator <= 0 {
2003        return Err(StridedError::OffsetOverflow);
2004    }
2005    Ok(numerator.div_euclid(denominator))
2006}
2007
2008fn checked_stride_mul_i64(stride: isize, factor: i64) -> Result<isize> {
2009    let factor = isize::try_from(factor).map_err(|_| StridedError::OffsetOverflow)?;
2010    stride
2011        .checked_mul(factor)
2012        .ok_or(StridedError::OffsetOverflow)
2013}
2014
2015fn checked_cursor_reset(step: isize, extent: usize) -> Result<isize> {
2016    if extent == 0 {
2017        return Ok(0);
2018    }
2019    let last = isize::try_from(extent - 1).map_err(|_| StridedError::OffsetOverflow)?;
2020    step.checked_mul(last)
2021        .and_then(isize::checked_neg)
2022        .ok_or(StridedError::OffsetOverflow)
2023}
2024
2025fn check_offset_span(shape: &[usize], strides: &[isize]) -> Result<()> {
2026    let mut min = 0isize;
2027    let mut max = 0isize;
2028    for (&extent, &stride) in shape.iter().zip(strides) {
2029        if extent <= 1 {
2030            continue;
2031        }
2032        let last = isize::try_from(extent - 1).map_err(|_| StridedError::OffsetOverflow)?;
2033        let delta = stride
2034            .checked_mul(last)
2035            .ok_or(StridedError::OffsetOverflow)?;
2036        if delta < 0 {
2037            min = min.checked_add(delta).ok_or(StridedError::OffsetOverflow)?;
2038        } else {
2039            max = max.checked_add(delta).ok_or(StridedError::OffsetOverflow)?;
2040        }
2041    }
2042    let _ = (min, max);
2043    Ok(())
2044}
2045
2046fn is_dense_col_major(dims: &[usize], strides: &[isize]) -> bool {
2047    let mut expected = 1isize;
2048    for (&dim, &stride) in dims.iter().zip(strides.iter()) {
2049        if stride != expected {
2050            return false;
2051        }
2052        let Ok(dim) = isize::try_from(dim) else {
2053            return false;
2054        };
2055        let Some(next) = expected.checked_mul(dim) else {
2056            return false;
2057        };
2058        expected = next;
2059    }
2060    true
2061}
2062
2063fn compile_contiguous_pad_axis0_run(
2064    operand_dims: &[usize],
2065    operand_strides: &[isize],
2066    dest_dims: &[usize],
2067    dest_strides: &[isize],
2068    edge_padding_low: &[i64],
2069    interior_step: &[i64],
2070) -> Option<ContiguousPadAxis0Run> {
2071    if operand_dims.is_empty()
2072        || operand_strides[0] != 1
2073        || dest_strides[0] != 1
2074        || interior_step[0] != 1
2075    {
2076        return None;
2077    }
2078
2079    let operand_extent = operand_dims[0] as i128;
2080    let dest_extent = dest_dims[0] as i128;
2081    let edge_low = i128::from(edge_padding_low[0]);
2082    let operand_start = (-edge_low).clamp(0, operand_extent);
2083    let dest_start = edge_low.clamp(0, dest_extent);
2084    let len = (operand_extent - operand_start).min(dest_extent - dest_start);
2085    Some(ContiguousPadAxis0Run {
2086        operand_start: usize::try_from(operand_start).ok()?,
2087        dest_start: usize::try_from(dest_start).ok()?,
2088        len: usize::try_from(len).ok()?,
2089    })
2090}
2091
2092/// Compile the disjoint-span column write for the dense, non-cropping,
2093/// no-interior-padding class, or `None` to keep the fill-then-copy fallback.
2094#[allow(clippy::too_many_arguments)]
2095fn compile_contiguous_pad_axis0_columns(
2096    operand_dims: &[usize],
2097    operand_strides: &[isize],
2098    dest_dims: &[usize],
2099    edge_padding_low: &[i64],
2100    edge_padding_high: &[i64],
2101    interior_step: &[i64],
2102    contiguous_dest_fill: bool,
2103    run: ContiguousPadAxis0Run,
2104) -> Option<ContiguousPadAxis0Columns> {
2105    if run.len == 0 || !contiguous_dest_fill || dest_dims.is_empty() {
2106        return None;
2107    }
2108    if edge_padding_low.iter().any(|&low| low < 0)
2109        || edge_padding_high.iter().any(|&high| high < 0)
2110        || interior_step.iter().any(|&step| step != 1)
2111    {
2112        return None;
2113    }
2114
2115    let rank = operand_dims.len();
2116    let dest_axis0_len = dest_dims[0];
2117    let dest_axis0_step = isize::try_from(dest_axis0_len).ok()?;
2118    let column_total = checked_total_len(&dest_dims[1..]).ok()?;
2119    let mut operand_outer_dims = AxisVec::with_capacity(rank - 1);
2120    let mut operand_outer_strides = AxisVec::with_capacity(rank - 1);
2121    let mut dest_outer_dims = AxisVec::with_capacity(rank - 1);
2122    let mut edge_low_outer = AxisVec::with_capacity(rank - 1);
2123    for axis in 1..rank {
2124        operand_outer_dims.push(operand_dims[axis]);
2125        operand_outer_strides.push(operand_strides[axis]);
2126        dest_outer_dims.push(dest_dims[axis]);
2127        edge_low_outer.push(usize::try_from(edge_padding_low[axis]).ok()?);
2128    }
2129
2130    let low0 = run.dest_start;
2131    let high0 = dest_axis0_len.checked_sub(low0)?.checked_sub(run.len)?;
2132    Some(ContiguousPadAxis0Columns {
2133        column_total,
2134        dest_axis0_len,
2135        dest_axis0_step,
2136        low0,
2137        high0,
2138        run_len: run.len,
2139        operand_outer_dims,
2140        operand_outer_strides,
2141        dest_outer_dims,
2142        edge_low_outer,
2143    })
2144}
2145
2146/// Fill a disjoint raw destination span, chunked across the budget of `exec`.
2147///
2148/// # Safety
2149///
2150/// `ptr..ptr + len` must be a writable destination span with no concurrent
2151/// access from another worker.
2152unsafe fn fill_raw_span<T: Copy + Send + Sync>(ptr: *mut T, len: usize, fill: T, exec: Exec<'_>) {
2153    if len == 0 {
2154        return;
2155    }
2156    // SAFETY: the caller guarantees the exact writable span; the slice is not
2157    // retained past `fill_contiguous`.
2158    let span = unsafe { core::slice::from_raw_parts_mut(ptr, len) };
2159    crate::threading::fill_contiguous(span, fill, exec);
2160}
2161
2162/// Fill a disjoint raw destination span that may be uninitialized.
2163///
2164/// # Safety
2165///
2166/// `ptr..ptr + len` must be a writable destination span with no concurrent
2167/// access from another worker.
2168unsafe fn fill_raw_span_uninit<T: Copy + Send + Sync>(
2169    ptr: *mut T,
2170    len: usize,
2171    fill: T,
2172    exec: Exec<'_>,
2173) {
2174    if len == 0 {
2175        return;
2176    }
2177    // SAFETY: the caller guarantees the exact writable span; the
2178    // `MaybeUninit` view never forms a `&mut [T]` over uninitialized memory.
2179    unsafe { crate::threading::fill_contiguous_uninit(ptr, len, fill, exec) };
2180}
2181
2182fn checked_offset_add(base: isize, stride: isize, coord: usize) -> Result<isize> {
2183    let coord = isize::try_from(coord).map_err(|_| StridedError::OffsetOverflow)?;
2184    let scaled = stride
2185        .checked_mul(coord)
2186        .ok_or(StridedError::OffsetOverflow)?;
2187    base.checked_add(scaled).ok_or(StridedError::OffsetOverflow)
2188}
2189
2190/// The operand coordinate contributed by one outer axis, or `None` when the
2191/// axis falls outside the operand's in-bounds interval.
2192fn in_bounds_outer_coord(
2193    columns: &ContiguousPadAxis0Columns,
2194    axis: usize,
2195    coord: usize,
2196) -> Option<usize> {
2197    let q = coord.checked_sub(columns.edge_low_outer[axis])?;
2198    (q < columns.operand_outer_dims[axis]).then_some(q)
2199}
2200
2201fn advance_col_major_index(index: &mut [usize], shape: &[usize]) {
2202    for axis in 0..index.len() {
2203        index[axis] += 1;
2204        if index[axis] < shape[axis] {
2205            return;
2206        }
2207        index[axis] = 0;
2208    }
2209}
2210
2211fn fill_col_major_index(mut linear: usize, shape: &[usize], out: &mut [usize]) {
2212    for (axis, coord) in out.iter_mut().enumerate() {
2213        let dim = shape[axis];
2214        *coord = linear % dim;
2215        linear /= dim;
2216    }
2217}
2218
2219struct PadFillState {
2220    coords: CoordScratch,
2221    offset: isize,
2222}
2223
2224impl PadFillState {
2225    fn new(base: isize, shape: &[usize], _cursor: &PadFillCursor) -> Self {
2226        Self {
2227            coords: CoordScratch::new(shape.len()),
2228            offset: base,
2229        }
2230    }
2231
2232    fn decode(linear: usize, base: isize, shape: &[usize], cursor: &PadFillCursor) -> Result<Self> {
2233        let mut state = Self::new(base, shape, cursor);
2234        fill_col_major_index(linear, shape, state.coords.as_mut_slice());
2235        for (&coord, &step) in state.coords.as_mut_slice().iter().zip(&cursor.steps) {
2236            state.offset = checked_offset_add(state.offset, step, coord)?;
2237        }
2238        Ok(state)
2239    }
2240
2241    #[inline]
2242    fn advance(&mut self, shape: &[usize], cursor: &PadFillCursor) {
2243        // INVARIANT: precomputed checked offset arithmetic, the validated
2244        // descriptor, and exact layout equality prove each incremental offset
2245        // remains reachable.
2246        for axis in 0..shape.len() {
2247            let next = self.coords.as_mut_slice()[axis] + 1;
2248            if next < shape[axis] {
2249                self.coords.as_mut_slice()[axis] = next;
2250                self.offset += cursor.steps[axis];
2251                return;
2252            }
2253            self.coords.as_mut_slice()[axis] = 0;
2254            self.offset += cursor.resets[axis];
2255        }
2256    }
2257}
2258
2259struct PadCopyState {
2260    coords: CoordScratch,
2261    source_offset: isize,
2262    dest_offset: isize,
2263}
2264
2265impl PadCopyState {
2266    fn new(source_base: isize, dest_base: isize, cursor: &PadCopyCursor) -> Self {
2267        Self {
2268            coords: CoordScratch::new(cursor.shape.len()),
2269            source_offset: source_base,
2270            dest_offset: dest_base,
2271        }
2272    }
2273
2274    fn decode(
2275        linear: usize,
2276        source_base: isize,
2277        dest_base: isize,
2278        cursor: &PadCopyCursor,
2279    ) -> Result<Self> {
2280        let mut state = Self::new(source_base, dest_base, cursor);
2281        fill_col_major_index(linear, &cursor.shape, state.coords.as_mut_slice());
2282        for axis in 0..cursor.shape.len() {
2283            let coord = state.coords.as_mut_slice()[axis];
2284            state.source_offset =
2285                checked_offset_add(state.source_offset, cursor.source_steps[axis], coord)?;
2286            state.dest_offset =
2287                checked_offset_add(state.dest_offset, cursor.dest_steps[axis], coord)?;
2288        }
2289        Ok(state)
2290    }
2291
2292    #[inline]
2293    fn advance(&mut self, cursor: &PadCopyCursor) {
2294        // INVARIANT: compile-time checked steps/resets/offset arithmetic,
2295        // validated descriptors, and exact plan-layout equality prove every update below
2296        // stays in the reachable source/destination domains.
2297        for axis in 0..cursor.shape.len() {
2298            let next = self.coords.as_mut_slice()[axis] + 1;
2299            if next < cursor.shape[axis] {
2300                self.coords.as_mut_slice()[axis] = next;
2301                self.source_offset += cursor.source_steps[axis];
2302                self.dest_offset += cursor.dest_steps[axis];
2303                return;
2304            }
2305            self.coords.as_mut_slice()[axis] = 0;
2306            self.source_offset += cursor.source_resets[axis];
2307            self.dest_offset += cursor.dest_resets[axis];
2308        }
2309    }
2310}
2311
2312struct CoordScratch {
2313    inline: [usize; crate::RAW_FUSED_RANK_LIMIT],
2314    heap: Option<Vec<usize>>,
2315    len: usize,
2316}
2317
2318impl CoordScratch {
2319    fn new(len: usize) -> Self {
2320        if len <= crate::RAW_FUSED_RANK_LIMIT {
2321            Self {
2322                inline: [0; crate::RAW_FUSED_RANK_LIMIT],
2323                heap: None,
2324                len,
2325            }
2326        } else {
2327            Self {
2328                inline: [0; crate::RAW_FUSED_RANK_LIMIT],
2329                heap: Some(vec![0; len]),
2330                len,
2331            }
2332        }
2333    }
2334
2335    fn as_mut_slice(&mut self) -> &mut [usize] {
2336        match &mut self.heap {
2337            Some(heap) => heap,
2338            None => &mut self.inline[..self.len],
2339        }
2340    }
2341}
2342
2343#[cfg(test)]
2344#[path = "static_indexing_plan/tests/tests.rs"]
2345mod tests;
2346
2347#[cfg(test)]
2348#[path = "static_indexing_plan/tests/parallel_tests.rs"]
2349mod parallel_tests;