Skip to main content

strided_basic/
gather_plan.rs

1//! Prepared indexed plans over raw strided value and index layouts.
2//!
3//! This module owns the generic gather, dynamic-slice/update, and scatter
4//! traversals used by the erased replay layer. It models the XLA/tenferro
5//! indexed shape vocabulary, but keeps tensor allocation, dtype promotion, and
6//! frontend error policy outside `strided-kernel`.
7
8use core::{mem::MaybeUninit, ops::Add};
9
10use crate::copy_plan::{replay_fused_raw, CopyPlan, OverwriteWriter, ReadModifyWrite};
11use crate::cost::KernelClass;
12use crate::inline::InlineVec;
13use crate::raw_ops::pair_tiles;
14use crate::raw_ops::{fuse_pair_layout, FusedPairLayout};
15use crate::{Exec, RawStridedMut, RawStridedRef, Result, StridedError, RAW_FUSED_RANK_LIMIT};
16
17type AxisVec<T> = InlineVec<T>;
18
19/// Gather configuration shared by generic and erased replay.
20///
21/// The fields follow the usual gather vocabulary:
22///
23/// - `start_index_map[component]` names the operand axis controlled by a
24///   component in the index vector;
25/// - `collapsed_slice_dims` names operand axes whose slice size is one and
26///   which do not appear as output window axes;
27/// - `offset_dims` names output axes that represent window offsets;
28/// - output axes not in `offset_dims` are batch axes from `start_indices`;
29/// - `index_vector_dim == start_indices_rank` represents scalar index vectors.
30#[derive(Clone, Debug, Eq, PartialEq)]
31pub struct GatherSpec {
32    pub offset_dims: Vec<usize>,
33    pub collapsed_slice_dims: Vec<usize>,
34    pub start_index_map: Vec<usize>,
35    pub index_vector_dim: usize,
36    pub slice_sizes: Vec<usize>,
37}
38
39/// Index scalar types accepted by [`GatherPlan`].
40pub trait GatherIndex: Copy + Send + Sync {
41    fn to_i64(self) -> i64;
42}
43
44impl GatherIndex for i32 {
45    #[inline]
46    fn to_i64(self) -> i64 {
47        i64::from(self)
48    }
49}
50
51impl GatherIndex for i64 {
52    #[inline]
53    fn to_i64(self) -> i64 {
54        self
55    }
56}
57
58/// A compiled gather traversal for one value layout, index layout, and output layout.
59#[derive(Clone, Debug)]
60pub struct GatherPlan {
61    operand_dims: AxisVec<usize>,
62    operand_strides: AxisVec<isize>,
63    index_dims: AxisVec<usize>,
64    index_strides: AxisVec<isize>,
65    dest_dims: AxisVec<usize>,
66    dest_strides: AxisVec<isize>,
67    spec: GatherSpec,
68    replay: GatherReplay,
69    total: usize,
70}
71
72#[derive(Clone, Copy, Debug, Default)]
73struct GatherReplayAxis {
74    dest_step: isize,
75    dest_reset: isize,
76    window_step: isize,
77    window_reset: isize,
78    index_batch_step: isize,
79    index_batch_reset: isize,
80}
81
82#[derive(Clone, Debug)]
83struct GatherReplay {
84    axes: AxisVec<GatherReplayAxis>,
85    index_component_offsets: AxisVec<isize>,
86    index_operand_strides: AxisVec<isize>,
87}
88
89struct GatherReplayState {
90    coords: AxisVec<usize>,
91    dest_offset: isize,
92    window_offset: isize,
93    index_batch_offset: isize,
94}
95
96#[derive(Clone, Copy, Debug, Default)]
97struct WindowReplayAxis {
98    source_step: isize,
99    source_reset: isize,
100    dest_step: isize,
101    dest_reset: isize,
102}
103
104/// The offsets a strided window reaches, relative to its base offset.
105#[derive(Clone, Copy, Debug, Default)]
106struct OffsetSpan {
107    min: isize,
108    max: isize,
109}
110
111impl OffsetSpan {
112    /// Every offset the window reaches from `base` fits `isize`.
113    fn covers(&self, base: isize) -> Result<()> {
114        base.checked_add(self.min)
115            .ok_or(StridedError::OffsetOverflow)?;
116        base.checked_add(self.max)
117            .ok_or(StridedError::OffsetOverflow)?;
118        Ok(())
119    }
120}
121
122#[derive(Clone, Debug)]
123struct WindowReplay {
124    shape: AxisVec<usize>,
125    axes: AxisVec<WindowReplayAxis>,
126    /// Offsets the window reaches in the update and destination layouts,
127    /// relative to the runtime base. Fusing keeps the reachable offset set, so
128    /// these spans also bound every fused replay step.
129    source_span: OffsetSpan,
130    dest_span: OffsetSpan,
131}
132
133struct WindowReplayState {
134    coords: CoordScratch,
135    source_offset: isize,
136    dest_offset: isize,
137}
138
139#[derive(Clone, Debug)]
140struct ScatterReplay {
141    batch: WindowReplay,
142    window: WindowReplay,
143    index_component_offsets: AxisVec<isize>,
144}
145
146impl ScatterReplay {
147    // Scatter compile: batch and window shapes, the index layout with its vector
148    // stride and component count, and the collapsed-slice set.
149    #[allow(clippy::too_many_arguments)]
150    fn compile(
151        batch_shape: &[usize],
152        index_dims: &[usize],
153        index_strides: &[isize],
154        index_vector_dim: usize,
155        index_component_count: usize,
156        update_dims: &[usize],
157        update_strides: &[isize],
158        update_window_dims: &[usize],
159        is_update_window_dim: &[bool],
160        window_shape_updates: &[usize],
161        window_dims: &[usize],
162        dest_strides: &[isize],
163    ) -> Result<Self> {
164        let (
165            batch_source_strides,
166            batch_dest_strides,
167            window_source_strides,
168            window_dest_strides,
169            vector_stride,
170        ) = scatter_replay_strides(
171            index_dims,
172            index_strides,
173            index_vector_dim,
174            update_dims,
175            update_strides,
176            update_window_dims,
177            is_update_window_dim,
178            window_dims,
179            dest_strides,
180        );
181        let batch = WindowReplay::compile(batch_shape, &batch_source_strides, &batch_dest_strides)?;
182        let window = WindowReplay::compile(
183            window_shape_updates,
184            &window_source_strides,
185            &window_dest_strides,
186        )?;
187        let mut index_component_offsets = AxisVec::with_capacity(index_component_count);
188        for component in 0..index_component_count {
189            index_component_offsets.push(checked_offset_add(0, vector_stride, component)?);
190        }
191        Ok(Self {
192            batch,
193            window,
194            index_component_offsets,
195        })
196    }
197}
198
199// Replay strides: both shapes, the index strides and vector axis, the update
200// window set and the operand shape.
201#[allow(clippy::too_many_arguments)]
202fn scatter_replay_strides(
203    index_dims: &[usize],
204    index_strides: &[isize],
205    index_vector_dim: usize,
206    update_dims: &[usize],
207    update_strides: &[isize],
208    update_window_dims: &[usize],
209    is_update_window_dim: &[bool],
210    window_dims: &[usize],
211    dest_strides: &[isize],
212) -> (
213    AxisVec<isize>,
214    AxisVec<isize>,
215    AxisVec<isize>,
216    AxisVec<isize>,
217    isize,
218) {
219    let batch_source_strides = index_dims
220        .iter()
221        .zip(index_strides.iter())
222        .enumerate()
223        .filter_map(|(axis, (_, &stride))| (axis != index_vector_dim).then_some(stride))
224        .collect();
225    let batch_dest_strides = update_dims
226        .iter()
227        .zip(update_strides.iter())
228        .enumerate()
229        .filter_map(|(axis, (_, &stride))| (!is_update_window_dim[axis]).then_some(stride))
230        .collect();
231    let window_source_strides = update_window_dims
232        .iter()
233        .map(|&axis| update_strides[axis])
234        .collect();
235    let window_dest_strides = window_dims.iter().map(|&axis| dest_strides[axis]).collect();
236    let vector_stride = if index_vector_dim < index_dims.len() {
237        index_strides[index_vector_dim]
238    } else {
239        0
240    };
241    (
242        batch_source_strides,
243        batch_dest_strides,
244        window_source_strides,
245        window_dest_strides,
246        vector_stride,
247    )
248}
249
250impl WindowReplay {
251    fn compile(shape: &[usize], source_strides: &[isize], dest_strides: &[isize]) -> Result<Self> {
252        let source_span = validate_layout_span(shape, source_strides)?;
253        let dest_span = validate_layout_span(shape, dest_strides)?;
254        let mut fused_shape: AxisVec<usize> = AxisVec::with_capacity(shape.len());
255        let mut axes: AxisVec<WindowReplayAxis> = AxisVec::with_capacity(shape.len());
256        for (axis, &dim) in shape.iter().enumerate() {
257            let source_step = source_strides[axis];
258            let dest_step = dest_strides[axis];
259            if let Some(previous_axis) = fused_shape.len().checked_sub(1) {
260                let previous_extent = fused_shape[previous_axis];
261                let previous_extent =
262                    isize::try_from(previous_extent).map_err(|_| StridedError::OffsetOverflow)?;
263                let expected_source = axes[previous_axis]
264                    .source_step
265                    .checked_mul(previous_extent)
266                    .ok_or(StridedError::OffsetOverflow)?;
267                let expected_dest = axes[previous_axis]
268                    .dest_step
269                    .checked_mul(previous_extent)
270                    .ok_or(StridedError::OffsetOverflow)?;
271                if source_step == expected_source && dest_step == expected_dest {
272                    let fused_extent = fused_shape[previous_axis]
273                        .checked_mul(dim)
274                        .ok_or(StridedError::OffsetOverflow)?;
275                    fused_shape[previous_axis] = fused_extent;
276                    axes[previous_axis].source_reset =
277                        checked_replay_reset(fused_extent, axes[previous_axis].source_step)?;
278                    axes[previous_axis].dest_reset =
279                        checked_replay_reset(fused_extent, axes[previous_axis].dest_step)?;
280                    continue;
281                }
282            }
283            fused_shape.push(dim);
284            axes.push(WindowReplayAxis {
285                source_step,
286                source_reset: checked_replay_reset(dim, source_step)?,
287                dest_step,
288                dest_reset: checked_replay_reset(dim, dest_step)?,
289            });
290        }
291        Ok(Self {
292            shape: fused_shape,
293            axes,
294            source_span,
295            dest_span,
296        })
297    }
298
299    /// The replay state at linear index zero. Every coordinate is zero, so
300    /// this needs no offset arithmetic and cannot fail after the destination
301    /// copy.
302    fn start(&self, source_base: isize, dest_base: isize) -> WindowReplayState {
303        WindowReplayState {
304            coords: CoordScratch::new(self.shape.len()),
305            source_offset: source_base,
306            dest_offset: dest_base,
307        }
308    }
309
310    fn decode(
311        &self,
312        mut linear: usize,
313        source_base: isize,
314        dest_base: isize,
315    ) -> Result<WindowReplayState> {
316        let mut coords = CoordScratch::new(self.shape.len());
317        let mut source_offset = source_base;
318        let mut dest_offset = dest_base;
319        for (axis, (&dim, coord)) in self
320            .shape
321            .iter()
322            .zip(coords.as_mut_slice().iter_mut())
323            .enumerate()
324        {
325            *coord = linear % dim;
326            linear /= dim;
327            let replay_axis = self.axes[axis];
328            source_offset = checked_offset_add(source_offset, replay_axis.source_step, *coord)?;
329            dest_offset = checked_offset_add(dest_offset, replay_axis.dest_step, *coord)?;
330        }
331        Ok(WindowReplayState {
332            coords,
333            source_offset,
334            dest_offset,
335        })
336    }
337
338    #[inline]
339    fn advance(&self, state: &mut WindowReplayState) {
340        for ((coord, &dim), replay_axis) in state
341            .coords
342            .as_mut_slice()
343            .iter_mut()
344            .zip(self.shape.iter())
345            .zip(self.axes.iter())
346        {
347            let next = *coord + 1;
348            if next < dim {
349                *coord = next;
350                state.source_offset += replay_axis.source_step;
351                state.dest_offset += replay_axis.dest_step;
352                return;
353            }
354            *coord = 0;
355            state.source_offset += replay_axis.source_reset;
356            state.dest_offset += replay_axis.dest_reset;
357        }
358    }
359}
360
361/// Scatter configuration shared by generic and erased replay.
362///
363/// `ScatterPlan` implements tenferro's current additive scatter semantics:
364/// every update value is added to the selected output slot, so overlapping
365/// windows accumulate in deterministic column-major replay order.
366#[derive(Clone, Debug, Eq, PartialEq)]
367pub struct ScatterSpec {
368    pub update_window_dims: Vec<usize>,
369    pub inserted_window_dims: Vec<usize>,
370    pub scatter_dims_to_operand_dims: Vec<usize>,
371    pub index_vector_dim: usize,
372}
373
374/// A compiled fixed-window dynamic-slice traversal.
375#[derive(Clone, Debug)]
376pub struct DynamicSlicePlan {
377    operand_dims: AxisVec<usize>,
378    operand_strides: AxisVec<isize>,
379    start_dims: AxisVec<usize>,
380    start_strides: AxisVec<isize>,
381    dest_dims: AxisVec<usize>,
382    dest_strides: AxisVec<isize>,
383    slice_sizes: AxisVec<usize>,
384    total: usize,
385    /// Fused window traversal (dest strides, operand strides) replayed at the
386    /// runtime source base; `None` when its fused rank exceeds
387    /// [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT), in which case
388    /// `replay`/`execute_parallel` walk the window instead.
389    window: Option<FusedPairLayout>,
390    replay: WindowReplay,
391}
392
393/// A compiled dynamic-update-slice traversal.
394///
395/// Execution first copies `operand` into `dest`, then overwrites the clamped
396/// update window. The plan performs no allocation for ranks at most
397/// [`RAW_FUSED_RANK_LIMIT`].
398#[derive(Clone, Debug)]
399pub struct DynamicUpdateSlicePlan {
400    operand_dims: AxisVec<usize>,
401    operand_strides: AxisVec<isize>,
402    start_dims: AxisVec<usize>,
403    start_strides: AxisVec<isize>,
404    update_dims: AxisVec<usize>,
405    update_strides: AxisVec<isize>,
406    dest_dims: AxisVec<usize>,
407    dest_strides: AxisVec<isize>,
408    total: usize,
409    copy_plan: CopyPlan,
410    /// Fused update window traversal (dest strides, update strides) replayed
411    /// at the runtime destination base; `None` when its fused rank exceeds
412    /// [`RAW_FUSED_RANK_LIMIT`](crate::RAW_FUSED_RANK_LIMIT), in which case
413    /// `replay`/`execute_update_parallel` walk the window instead.
414    window: Option<FusedPairLayout>,
415    replay: WindowReplay,
416}
417
418/// Update-window metadata resolved before the operand copy.
419///
420/// Reading the clamped start vector, mapping it onto the destination layout,
421/// bounding the window against both runtime bases, and (on the rank-one
422/// contiguous path) converting the run bounds are the only fallible steps of
423/// the update phase. Preparing them up front keeps a rejected call from
424/// leaving `dest` copied but un-updated.
425enum UpdateWindow<'a, T> {
426    /// The window is empty: the copy alone is the result.
427    Empty,
428    /// Rank-one contiguous run, as the checked update run and destination
429    /// index.
430    RankOne { update: &'a [T], dest_start: usize },
431    /// Replay base in the destination layout, shared by the fused and generic
432    /// paths.
433    Replay { dest_base: isize },
434}
435
436/// A compiled additive scatter traversal.
437///
438/// Execution first copies `operand` into `dest`, then applies additive updates
439/// in deterministic column-major order. Boolean values are intentionally not
440/// supported because additive scatter has no bool semantics.
441#[derive(Clone, Debug)]
442pub struct ScatterPlan {
443    operand_dims: AxisVec<usize>,
444    operand_strides: AxisVec<isize>,
445    index_dims: AxisVec<usize>,
446    index_strides: AxisVec<isize>,
447    update_dims: AxisVec<usize>,
448    update_strides: AxisVec<isize>,
449    dest_dims: AxisVec<usize>,
450    dest_strides: AxisVec<isize>,
451    spec: ScatterSpec,
452    window_shape: AxisVec<usize>,
453    batch_elems: usize,
454    window_elems: usize,
455    copy_plan: CopyPlan,
456    replay: ScatterReplay,
457}
458
459impl GatherPlan {
460    /// Compile a gather plan for fixed operand, index, and destination layouts.
461    ///
462    /// # Errors
463    ///
464    /// Returns [`StridedError::StrideLengthMismatch`] when a stride list does
465    /// not match its dimension list, [`StridedError::OffsetOverflow`] when an
466    /// element count or a layout span does not fit `usize`/`isize`,
467    /// [`StridedError::NonInjectiveOutputLayout`] when the destination layout
468    /// maps two logical indices onto one offset.
469    /// [`StridedError::RankMismatch`] reports `spec.slice_sizes` or
470    /// `spec.offset_dims` of the wrong length, or an index vector that does not
471    /// match `spec.start_index_map`;
472    /// [`StridedError::InvalidAxis`] reports `collapsed_slice_dims`,
473    /// `start_index_map`, or `offset_dims` that repeat or exceed their rank,
474    /// `index_vector_dim` beyond the index rank, a slice size beyond its
475    /// operand extent, or a collapsed axis whose slice size is not one; and
476    /// [`StridedError::ShapeMismatch`] reports a `dest_dims` that is not the
477    /// gathered window/batch shape.
478    pub fn compile(
479        operand_dims: &[usize],
480        operand_strides: &[isize],
481        index_dims: &[usize],
482        index_strides: &[isize],
483        dest_dims: &[usize],
484        dest_strides: &[isize],
485        spec: GatherSpec,
486    ) -> Result<Self> {
487        if operand_dims.len() != operand_strides.len()
488            || index_dims.len() != index_strides.len()
489            || dest_dims.len() != dest_strides.len()
490        {
491            return Err(StridedError::StrideLengthMismatch);
492        }
493        checked_total_len(operand_dims)?;
494        checked_total_len(index_dims)?;
495        let total = checked_total_len(dest_dims)?;
496        validate_layout_span(operand_dims, operand_strides)?;
497        validate_layout_span(index_dims, index_strides)?;
498        validate_layout_span(dest_dims, dest_strides)?;
499        if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
500            return Err(StridedError::NonInjectiveOutputLayout);
501        }
502
503        let operand_rank = operand_dims.len();
504        if spec.slice_sizes.len() != operand_rank {
505            return Err(StridedError::RankMismatch(
506                spec.slice_sizes.len(),
507                operand_rank,
508            ));
509        }
510        validate_unique_axes(&spec.collapsed_slice_dims, operand_rank)?;
511        validate_unique_axes(&spec.start_index_map, operand_rank)?;
512        if spec.index_vector_dim > index_dims.len() {
513            return Err(StridedError::InvalidAxis {
514                axis: spec.index_vector_dim,
515                rank: index_dims.len() + 1,
516            });
517        }
518
519        for (axis, (&window, &dim)) in spec.slice_sizes.iter().zip(operand_dims.iter()).enumerate()
520        {
521            if window > dim {
522                return Err(StridedError::InvalidAxis {
523                    axis,
524                    rank: operand_rank,
525                });
526            }
527        }
528        for &axis in &spec.collapsed_slice_dims {
529            if spec.slice_sizes[axis] != 1 {
530                return Err(StridedError::InvalidAxis {
531                    axis,
532                    rank: operand_rank,
533                });
534            }
535        }
536
537        let index_vector_size = if spec.index_vector_dim == index_dims.len() {
538            1
539        } else {
540            index_dims[spec.index_vector_dim]
541        };
542        if index_vector_size != spec.start_index_map.len() {
543            return Err(StridedError::RankMismatch(
544                index_vector_size,
545                spec.start_index_map.len(),
546            ));
547        }
548
549        let window_dims = operand_window_dims(operand_rank, &spec.collapsed_slice_dims);
550        if spec.offset_dims.len() != window_dims.len() {
551            return Err(StridedError::RankMismatch(
552                spec.offset_dims.len(),
553                window_dims.len(),
554            ));
555        }
556
557        let batch_shape = index_batch_shape(index_dims, spec.index_vector_dim);
558        let out_rank = batch_shape.len() + spec.offset_dims.len();
559        validate_unique_axes(&spec.offset_dims, out_rank)?;
560
561        let mut out_axis_to_operand_dim: AxisVec<Option<usize>> =
562            (0..out_rank).map(|_| None).collect();
563        for (offset_axis, &out_axis) in spec.offset_dims.iter().enumerate() {
564            out_axis_to_operand_dim[out_axis] = Some(window_dims[offset_axis]);
565        }
566
567        let mut expected_dest_dims: AxisVec<usize> = AxisVec::with_capacity(out_rank);
568        let mut batch_axis = 0usize;
569        for &operand_dim in &out_axis_to_operand_dim {
570            match operand_dim {
571                Some(axis) => expected_dest_dims.push(spec.slice_sizes[axis]),
572                None => {
573                    expected_dest_dims.push(batch_shape[batch_axis]);
574                    batch_axis += 1;
575                }
576            }
577        }
578        if dest_dims != &expected_dest_dims[..] {
579            return Err(StridedError::ShapeMismatch(
580                dest_dims.to_vec(),
581                expected_dest_dims.to_vec(),
582            ));
583        }
584
585        let batch_index_strides: AxisVec<isize> = index_dims
586            .iter()
587            .zip(index_strides.iter())
588            .enumerate()
589            .filter_map(|(axis, (_, &stride))| (axis != spec.index_vector_dim).then_some(stride))
590            .collect();
591        let mut batch_axis = 0usize;
592        let mut replay_axes = AxisVec::with_capacity(out_rank);
593        for (out_axis, &operand_dim) in out_axis_to_operand_dim.iter().enumerate() {
594            let (window_step, index_batch_step) = match operand_dim {
595                Some(axis) => (operand_strides[axis], 0),
596                None => {
597                    let step = batch_index_strides[batch_axis];
598                    batch_axis += 1;
599                    (0, step)
600                }
601            };
602            replay_axes.push(GatherReplayAxis {
603                dest_step: dest_strides[out_axis],
604                dest_reset: checked_replay_reset(dest_dims[out_axis], dest_strides[out_axis])?,
605                window_step,
606                window_reset: checked_replay_reset(dest_dims[out_axis], window_step)?,
607                index_batch_step,
608                index_batch_reset: checked_replay_reset(dest_dims[out_axis], index_batch_step)?,
609            });
610        }
611
612        let vector_stride = if spec.index_vector_dim < index_dims.len() {
613            index_strides[spec.index_vector_dim]
614        } else {
615            0
616        };
617        let mut index_component_offsets = AxisVec::with_capacity(spec.start_index_map.len());
618        for component in 0..spec.start_index_map.len() {
619            index_component_offsets.push(checked_offset_add(0, vector_stride, component)?);
620        }
621
622        let index_operand_strides: AxisVec<isize> = spec
623            .start_index_map
624            .iter()
625            .map(|&axis| operand_strides[axis])
626            .collect();
627
628        Ok(Self {
629            operand_dims: operand_dims.into(),
630            operand_strides: operand_strides.into(),
631            index_dims: index_dims.into(),
632            index_strides: index_strides.into(),
633            dest_dims: dest_dims.into(),
634            dest_strides: dest_strides.into(),
635            spec,
636            replay: GatherReplay {
637                axes: replay_axes,
638                index_component_offsets,
639                index_operand_strides,
640            },
641            total,
642        })
643    }
644
645    #[inline]
646    pub fn spec(&self) -> &GatherSpec {
647        &self.spec
648    }
649
650    #[inline]
651    pub fn dest_dims(&self) -> &[usize] {
652        &self.dest_dims
653    }
654
655    /// Execute the prepared gather traversal.
656    ///
657    /// # Errors
658    ///
659    /// Returns [`StridedError::PlanLayoutMismatch`] when the operand, index,
660    /// or destination view does not carry its compiled extents and strides,
661    /// before any destination write, and
662    /// [`StridedError::OffsetOverflow`] when a replayed chunk's offset
663    /// arithmetic cannot be represented. Start indices are clamped into the
664    /// operand window, so an out-of-range index is not an error. The offset
665    /// arithmetic runs per worker above the threading threshold, so a
666    /// destination split across workers may be partially written when that
667    /// error surfaces.
668    pub fn execute<T, I>(
669        &self,
670        dest: &mut RawStridedMut<'_, T>,
671        operand: &RawStridedRef<'_, T>,
672        start_indices: &RawStridedRef<'_, I>,
673        exec: Exec<'_>,
674    ) -> Result<()>
675    where
676        T: Copy + Send + Sync,
677        I: GatherIndex,
678    {
679        self.execute_with_writer(dest, operand, start_indices, exec)
680    }
681
682    /// Execute the prepared gather into a destination whose reachable slots
683    /// may be uninitialized. Every logical destination slot is written.
684    pub(crate) fn execute_uninit<T, I>(
685        &self,
686        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
687        operand: &RawStridedRef<'_, T>,
688        start_indices: &RawStridedRef<'_, I>,
689        exec: Exec<'_>,
690    ) -> Result<()>
691    where
692        T: Copy + Send + Sync,
693        I: GatherIndex,
694    {
695        self.execute_with_writer(dest, operand, start_indices, exec)
696    }
697
698    fn execute_with_writer<T, I, W>(
699        &self,
700        dest: &mut W,
701        operand: &RawStridedRef<'_, T>,
702        start_indices: &RawStridedRef<'_, I>,
703        exec: Exec<'_>,
704    ) -> Result<()>
705    where
706        T: Copy + Send + Sync,
707        I: GatherIndex,
708        W: OverwriteWriter<T>,
709    {
710        self.check_call(dest, operand, start_indices)?;
711        if self.total == 0 {
712            return Ok(());
713        }
714        if self.uses_rank_one_scalar_take_path() {
715            let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.total);
716            if !exec.is_serial() {
717                return self.execute_rank_one_scalar_take_parallel(
718                    dest,
719                    operand,
720                    start_indices,
721                    exec,
722                );
723            }
724            return self.execute_rank_one_scalar_take(dest, operand, start_indices);
725        }
726        let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.total);
727        if !exec.is_serial() {
728            return self.execute_parallel(dest, operand, start_indices, exec);
729        }
730
731        let mut state =
732            self.decode_replay_state(0, dest.offset(), operand.offset(), start_indices.offset())?;
733        let operand_data = operand.data();
734        let index_data = start_indices.data();
735
736        // INVARIANT: the checked decode starts at a valid logical output. Each
737        // replay axis has checked step/reset deltas, so this state remains the
738        // corresponding destination, window, and batch-index offsets.
739        for _ in 0..self.total {
740            // INVARIANT: window_offset plus every clamped mapped contribution
741            // is an operand offset for coordinates inside operand_dims; the
742            // validated operand span and RawStridedRef reachability therefore
743            // keep the fresh source offset inside the allocation.
744            let mut source_offset = state.window_offset;
745            for ((&index_component_offset, &operand_stride), &operand_dim) in self
746                .replay
747                .index_component_offsets
748                .iter()
749                .zip(self.replay.index_operand_strides.iter())
750                .zip(self.spec.start_index_map.iter())
751            {
752                let index_offset = state.index_batch_offset + index_component_offset;
753                // SAFETY: checked index layout replay and RawStridedRef
754                // reachability prove this component read is in bounds.
755                let start = unsafe { *index_data.as_ptr().offset(index_offset) }.to_i64();
756                let clamped = self.clamp_window_start(start, operand_dim);
757                source_offset += operand_stride * clamped as isize;
758            }
759
760            // SAFETY: checked replay metadata and the validated writer prove
761            // both the source and the distinct destination offset are valid.
762            let value = unsafe { *operand_data.as_ptr().offset(source_offset) };
763            unsafe { dest.write_at(state.dest_offset, value) };
764            self.advance_replay_state(&mut state);
765        }
766        Ok(())
767    }
768
769    fn uses_rank_one_scalar_take_path(&self) -> bool {
770        self.operand_dims.len() == 1
771            && self.index_dims.len() == 1
772            && self.dest_dims.len() == 1
773            && self.operand_strides[0] == 1
774            && self.index_strides[0] == 1
775            && self.dest_strides[0] == 1
776            && self.spec.offset_dims.is_empty()
777            && self.spec.collapsed_slice_dims.as_slice() == [0]
778            && self.spec.start_index_map.as_slice() == [0]
779            && self.spec.index_vector_dim == 1
780            && self.spec.slice_sizes.as_slice() == [1]
781    }
782
783    fn execute_rank_one_scalar_take<T, I, W>(
784        &self,
785        dest: &mut W,
786        operand: &RawStridedRef<'_, T>,
787        start_indices: &RawStridedRef<'_, I>,
788    ) -> Result<()>
789    where
790        T: Copy,
791        I: GatherIndex,
792        W: OverwriteWriter<T>,
793    {
794        let mut dest_offset = dest.offset();
795        let mut index_offset = start_indices.offset();
796        let operand_offset = operand.offset();
797        let operand_data = operand.data();
798        let index_data = start_indices.data();
799
800        // INVARIANT: compile and check_call validated compact rank-one layouts,
801        // so incrementing these offsets once per logical element stays within
802        // the validated allocations and cannot overflow isize.
803        // `index_offset` is the pointer walk of this gather line, not a counter.
804        #[allow(clippy::explicit_counter_loop)]
805        for _ in 0..self.total {
806            // SAFETY: the invariant above proves all three offsets are in bounds.
807            unsafe {
808                let start = (*index_data.as_ptr().offset(index_offset)).to_i64();
809                let source_offset = operand_offset + self.clamp_window_start(start, 0) as isize;
810                dest.write_at(dest_offset, *operand_data.as_ptr().offset(source_offset));
811            }
812            dest_offset += 1;
813            index_offset += 1;
814        }
815        Ok(())
816    }
817
818    fn execute_rank_one_scalar_take_parallel<T, I, W>(
819        &self,
820        dest: &mut W,
821        operand: &RawStridedRef<'_, T>,
822        start_indices: &RawStridedRef<'_, I>,
823        exec: Exec<'_>,
824    ) -> Result<()>
825    where
826        T: Copy + Send + Sync,
827        I: GatherIndex,
828        W: OverwriteWriter<T>,
829    {
830        let dest_offset = dest.offset();
831        let operand_offset = operand.offset();
832        let index_offset = start_indices.offset();
833        // SAFETY: check_call validated the writer's complete destination layout.
834        let dest_ptr = crate::threading::SendPtr(unsafe { dest.data_ptr() });
835        let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
836        let index_ptr = crate::threading::SendPtr(start_indices.data().as_ptr() as *mut I);
837
838        crate::threading::parallel_map_reduce(
839            0..self.total,
840            exec,
841            &|range| {
842                let dest_ptr = dest_ptr.as_ptr();
843                let operand_ptr = operand_ptr.as_const();
844                let index_ptr = index_ptr.as_const();
845                // INVARIANT: the validated compact rank-one layouts map each
846                // output position to one distinct destination offset.
847                for position in range {
848                    let position = position as isize;
849                    // SAFETY: the invariant above proves the source and distinct
850                    // destination offsets are in their validated allocations.
851                    unsafe {
852                        let start = (*index_ptr.offset(index_offset + position)).to_i64();
853                        let source_offset =
854                            operand_offset + self.clamp_window_start(start, 0) as isize;
855                        dest_ptr
856                            .offset(dest_offset + position)
857                            .write(operand_ptr.offset(source_offset).read());
858                    }
859                }
860                Ok(())
861            },
862            &|left, right| left.and(right),
863        )
864    }
865
866    fn execute_parallel<T, I, W>(
867        &self,
868        dest: &mut W,
869        operand: &RawStridedRef<'_, T>,
870        start_indices: &RawStridedRef<'_, I>,
871        exec: Exec<'_>,
872    ) -> Result<()>
873    where
874        T: Copy + Send + Sync,
875        I: GatherIndex,
876        W: OverwriteWriter<T>,
877    {
878        let dest_offset_base = dest.offset();
879        let operand_offset_base = operand.offset();
880        let index_offset_base = start_indices.offset();
881        // SAFETY: the validated writer owns the destination allocation.
882        let dest_ptr = crate::threading::SendPtr(unsafe { dest.data_ptr() });
883        let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
884        let index_ptr = crate::threading::SendPtr(start_indices.data().as_ptr() as *mut I);
885
886        crate::threading::parallel_map_reduce(
887            0..self.total,
888            exec,
889            &|range| {
890                let mut state = self.decode_replay_state(
891                    range.start,
892                    dest_offset_base,
893                    operand_offset_base,
894                    index_offset_base,
895                )?;
896                let dest_ptr = dest_ptr.as_ptr();
897                let operand_ptr = operand_ptr.as_const();
898                let index_ptr = index_ptr.as_const();
899
900                // INVARIANT: this worker owns a disjoint logical range. Checked
901                // range-start decode plus checked replay deltas keeps every
902                // state at its corresponding output, and injectivity makes all
903                // writes across workers distinct.
904                for _ in range {
905                    // INVARIANT: source_offset is freshly based on the current
906                    // window offset; clamped mapped coordinates remain inside
907                    // the validated operand span and are never accumulated.
908                    let mut source_offset = state.window_offset;
909                    for ((&index_component_offset, &operand_stride), &operand_dim) in self
910                        .replay
911                        .index_component_offsets
912                        .iter()
913                        .zip(self.replay.index_operand_strides.iter())
914                        .zip(self.spec.start_index_map.iter())
915                    {
916                        let index_offset = state.index_batch_offset + index_component_offset;
917                        // SAFETY: the checked index span and this worker's
918                        // validated range-start state prove this read is valid.
919                        let start = unsafe { (*index_ptr.offset(index_offset)).to_i64() };
920                        let clamped = self.clamp_window_start(start, operand_dim);
921                        source_offset += operand_stride * clamped as isize;
922                    }
923
924                    // SAFETY: the source proof above and distinct destination
925                    // invariant justify these raw accesses.
926                    unsafe {
927                        dest_ptr
928                            .offset(state.dest_offset)
929                            .write(operand_ptr.offset(source_offset).read());
930                    }
931                    self.advance_replay_state(&mut state);
932                }
933                Ok(())
934            },
935            &|left, right| left.and(right),
936        )
937    }
938
939    fn check_call<T, I, W>(
940        &self,
941        dest: &W,
942        operand: &RawStridedRef<'_, T>,
943        start_indices: &RawStridedRef<'_, I>,
944    ) -> Result<()>
945    where
946        W: OverwriteWriter<T>,
947    {
948        if dest.dims() != &self.dest_dims[..]
949            || dest.strides() != &self.dest_strides[..]
950            || operand.dims() != &self.operand_dims[..]
951            || operand.strides() != &self.operand_strides[..]
952            || start_indices.dims() != &self.index_dims[..]
953            || start_indices.strides() != &self.index_strides[..]
954        {
955            return Err(StridedError::PlanLayoutMismatch);
956        }
957        Ok(())
958    }
959
960    fn decode_replay_state(
961        &self,
962        mut linear: usize,
963        dest_offset_base: isize,
964        operand_offset_base: isize,
965        index_offset_base: isize,
966    ) -> Result<GatherReplayState> {
967        let mut coords = AxisVec::with_capacity(self.dest_dims.len());
968        let mut dest_offset = dest_offset_base;
969        let mut window_offset = operand_offset_base;
970        let mut index_batch_offset = index_offset_base;
971        for (axis, &dim) in self.dest_dims.iter().enumerate() {
972            let coord = linear % dim;
973            linear /= dim;
974            let replay_axis = self.replay.axes[axis];
975            coords.push(coord);
976            dest_offset = checked_offset_add(dest_offset, replay_axis.dest_step, coord)?;
977            window_offset = checked_offset_add(window_offset, replay_axis.window_step, coord)?;
978            index_batch_offset =
979                checked_offset_add(index_batch_offset, replay_axis.index_batch_step, coord)?;
980        }
981        Ok(GatherReplayState {
982            coords,
983            dest_offset,
984            window_offset,
985            index_batch_offset,
986        })
987    }
988
989    #[inline]
990    fn advance_replay_state(&self, state: &mut GatherReplayState) {
991        for (axis, replay_axis) in self.replay.axes.iter().enumerate() {
992            let coord = state.coords[axis];
993            if coord + 1 < self.dest_dims[axis] {
994                state.coords[axis] = coord + 1;
995                state.dest_offset += replay_axis.dest_step;
996                state.window_offset += replay_axis.window_step;
997                state.index_batch_offset += replay_axis.index_batch_step;
998                return;
999            }
1000            state.coords[axis] = 0;
1001            state.dest_offset += replay_axis.dest_reset;
1002            state.window_offset += replay_axis.window_reset;
1003            state.index_batch_offset += replay_axis.index_batch_reset;
1004        }
1005    }
1006
1007    #[inline]
1008    fn clamp_window_start(&self, start: i64, operand_dim: usize) -> usize {
1009        let dim_size = self.operand_dims[operand_dim];
1010        let window_size = self.spec.slice_sizes[operand_dim];
1011        let max_start = dim_size.saturating_sub(window_size) as i64;
1012        start.clamp(0, max_start) as usize
1013    }
1014}
1015
1016impl DynamicSlicePlan {
1017    /// Compile a fixed-window dynamic-slice traversal.
1018    ///
1019    /// `start_*` describes a rank-1 index vector whose length equals the
1020    /// operand rank. `dest_dims` must equal `slice_sizes`.
1021    ///
1022    /// # Errors
1023    ///
1024    /// Returns [`StridedError::StrideLengthMismatch`] when a stride list does
1025    /// not match its dimension list, [`StridedError::RankMismatch`] when
1026    /// `slice_sizes` differs from the operand rank or the start layout is not a
1027    /// rank-1 vector of that same length,
1028    /// [`StridedError::OffsetOverflow`] when an element count or layout span
1029    /// does not fit `usize`/`isize`, [`StridedError::ShapeMismatch`] when
1030    /// `dest_dims` differs from `slice_sizes` in extent or rank,
1031    /// [`StridedError::NonInjectiveOutputLayout`] when the destination layout
1032    /// maps two logical indices onto one offset, and
1033    /// [`StridedError::InvalidAxis`] when a slice size exceeds its operand
1034    /// extent.
1035    pub fn compile(
1036        operand_dims: &[usize],
1037        operand_strides: &[isize],
1038        start_dims: &[usize],
1039        start_strides: &[isize],
1040        dest_dims: &[usize],
1041        dest_strides: &[isize],
1042        slice_sizes: &[usize],
1043    ) -> Result<Self> {
1044        if operand_dims.len() != operand_strides.len()
1045            || start_dims.len() != start_strides.len()
1046            || dest_dims.len() != dest_strides.len()
1047        {
1048            return Err(StridedError::StrideLengthMismatch);
1049        }
1050        if slice_sizes.len() != operand_dims.len() {
1051            return Err(StridedError::RankMismatch(
1052                slice_sizes.len(),
1053                operand_dims.len(),
1054            ));
1055        }
1056        validate_start_vector(start_dims, operand_dims.len())?;
1057        checked_total_len(operand_dims)?;
1058        checked_total_len(start_dims)?;
1059        let total = checked_total_len(dest_dims)?;
1060        validate_layout_span(operand_dims, operand_strides)?;
1061        validate_layout_span(start_dims, start_strides)?;
1062        validate_layout_span(dest_dims, dest_strides)?;
1063        if dest_dims != slice_sizes {
1064            return Err(StridedError::ShapeMismatch(
1065                dest_dims.to_vec(),
1066                slice_sizes.to_vec(),
1067            ));
1068        }
1069        if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
1070            return Err(StridedError::NonInjectiveOutputLayout);
1071        }
1072        validate_window_sizes(operand_dims, slice_sizes)?;
1073        let replay = WindowReplay::compile(slice_sizes, operand_strides, dest_strides)?;
1074
1075        Ok(Self {
1076            operand_dims: operand_dims.into(),
1077            operand_strides: operand_strides.into(),
1078            start_dims: start_dims.into(),
1079            start_strides: start_strides.into(),
1080            dest_dims: dest_dims.into(),
1081            dest_strides: dest_strides.into(),
1082            slice_sizes: slice_sizes.into(),
1083            total,
1084            window: fuse_pair_layout(slice_sizes, dest_strides, operand_strides),
1085            replay,
1086        })
1087    }
1088
1089    /// Execute the prepared dynamic-slice traversal.
1090    ///
1091    /// # Errors
1092    ///
1093    /// Returns [`StridedError::PlanLayoutMismatch`] when the operand, start,
1094    /// or destination view does not carry its compiled extents and strides,
1095    /// before any destination write. Start values are clamped to
1096    /// `operand_dims - slice_sizes`, so an out-of-range start is not an
1097    /// error.
1098    pub fn execute<T, I>(
1099        &self,
1100        dest: &mut RawStridedMut<'_, T>,
1101        operand: &RawStridedRef<'_, T>,
1102        starts: &RawStridedRef<'_, I>,
1103        exec: Exec<'_>,
1104    ) -> Result<()>
1105    where
1106        T: Copy + Send + Sync,
1107        I: GatherIndex,
1108    {
1109        self.execute_with_writer(dest, operand, starts, exec)
1110    }
1111
1112    pub(crate) fn execute_uninit<T, I>(
1113        &self,
1114        dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1115        operand: &RawStridedRef<'_, T>,
1116        starts: &RawStridedRef<'_, I>,
1117        exec: Exec<'_>,
1118    ) -> Result<()>
1119    where
1120        T: Copy + Send + Sync,
1121        I: GatherIndex,
1122    {
1123        self.execute_with_writer(dest, operand, starts, exec)
1124    }
1125
1126    fn execute_with_writer<T, I, W>(
1127        &self,
1128        dest: &mut W,
1129        operand: &RawStridedRef<'_, T>,
1130        starts: &RawStridedRef<'_, I>,
1131        exec: Exec<'_>,
1132    ) -> Result<()>
1133    where
1134        T: Copy + Send + Sync,
1135        I: GatherIndex,
1136        W: OverwriteWriter<T>,
1137    {
1138        self.check_call(dest, operand, starts)?;
1139        if self.total == 0 {
1140            return Ok(());
1141        }
1142        if self.uses_rank_one_contiguous_path() {
1143            return self.execute_rank_one_contiguous(dest, operand, starts, exec);
1144        }
1145        if let Some(window) = &self.window {
1146            return self.execute_fused_window(dest, operand, starts, window, exec);
1147        }
1148        let replay = &self.replay;
1149        let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.total);
1150        if !exec.is_serial() {
1151            return self.execute_parallel(dest, operand, starts, exec, replay);
1152        }
1153
1154        let mut starts_storage = CoordScratch::new(self.operand_dims.len());
1155        let clamped_starts = starts_storage.as_mut_slice();
1156        read_clamped_starts(
1157            starts,
1158            &self.operand_dims,
1159            &self.slice_sizes,
1160            clamped_starts,
1161        )?;
1162        let source_base =
1163            checked_strided_offset(operand.offset(), &self.operand_strides, clamped_starts)?;
1164        let mut state = replay.decode(0, source_base, dest.offset())?;
1165        let operand_data = operand.data();
1166
1167        // INVARIANT: compile validated the full operand/destination spans and the
1168        // replay window spans; checked bases plus checked reset deltas therefore
1169        // keep every current offset reachable without per-element offset scans.
1170        for _ in 0..self.total {
1171            // SAFETY: the invariant above proves both current offsets are valid.
1172            let value = unsafe { *operand_data.as_ptr().offset(state.source_offset) };
1173            // SAFETY: the invariant above proves this logical destination offset
1174            // is in-bounds, and the output layout is injective.
1175            unsafe { dest.write_at(state.dest_offset, value) };
1176            replay.advance(&mut state);
1177        }
1178        Ok(())
1179    }
1180
1181    /// Replay the compiled fused window from the clamped runtime source base.
1182    ///
1183    /// The window is a CopyPlan-style fused layout, so full inner runs are
1184    /// replayed with a pointer loop (slice copies for unit strides) and the
1185    /// work is split across workers above the repository threshold.
1186    fn execute_fused_window<T, I, W>(
1187        &self,
1188        dest: &mut W,
1189        operand: &RawStridedRef<'_, T>,
1190        starts: &RawStridedRef<'_, I>,
1191        window: &FusedPairLayout,
1192        exec: Exec<'_>,
1193    ) -> Result<()>
1194    where
1195        T: Copy + Send + Sync,
1196        I: GatherIndex,
1197        W: OverwriteWriter<T>,
1198    {
1199        let mut starts_storage = CoordScratch::new(self.operand_dims.len());
1200        let clamped_starts = starts_storage.as_mut_slice();
1201        read_clamped_starts(
1202            starts,
1203            &self.operand_dims,
1204            &self.slice_sizes,
1205            clamped_starts,
1206        )?;
1207        let source_base =
1208            checked_strided_offset(operand.offset(), &self.operand_strides, clamped_starts)?;
1209        let dest_base = dest.offset();
1210        // SAFETY: the validated writer owns the destination allocation.
1211        let dest_ptr = unsafe { dest.data_ptr() }.cast::<MaybeUninit<T>>();
1212        let tiles = pair_tiles::<MaybeUninit<T>, T>(window);
1213        // SAFETY: `window` fuses `slice_sizes` with the checked destination
1214        // and operand strides. The clamped window `start + slice_sizes` lies
1215        // inside `operand_dims`, so every source offset from `source_base` is
1216        // an offset the validated operand view can reach; the destination has
1217        // exactly `slice_sizes` dims and its validated layout reaches every
1218        // destination offset. Compile proved the destination injective, and
1219        // the exclusive writer borrow does not overlap the shared operand.
1220        // Writing `MaybeUninit::new` is valid for both initialized and
1221        // uninitialized destination slots. The injective destination lets the
1222        // window replay its tiles.
1223        unsafe {
1224            replay_fused_raw(
1225                dest_ptr,
1226                dest_base,
1227                operand.data().as_ptr(),
1228                source_base,
1229                window,
1230                tiles.as_ref(),
1231                |slot: &mut MaybeUninit<T>, value: T| *slot = MaybeUninit::new(value),
1232                KernelClass::Copy.ns_per_element(),
1233                exec,
1234            );
1235        }
1236        Ok(())
1237    }
1238
1239    #[inline]
1240    fn uses_rank_one_contiguous_path(&self) -> bool {
1241        self.operand_dims.len() == 1 && self.operand_strides[0] == 1 && self.dest_strides[0] == 1
1242    }
1243
1244    fn execute_rank_one_contiguous<T, I, W>(
1245        &self,
1246        dest: &mut W,
1247        operand: &RawStridedRef<'_, T>,
1248        starts: &RawStridedRef<'_, I>,
1249        exec: Exec<'_>,
1250    ) -> Result<()>
1251    where
1252        T: Copy + Send + Sync,
1253        I: GatherIndex,
1254        W: OverwriteWriter<T>,
1255    {
1256        let mut clamped_starts = [0usize; 1];
1257        read_clamped_starts(
1258            starts,
1259            &self.operand_dims,
1260            &self.slice_sizes,
1261            &mut clamped_starts,
1262        )?;
1263        let source_start = checked_offset_add(operand.offset(), 1, clamped_starts[0])?;
1264        let source_start =
1265            usize::try_from(source_start).map_err(|_| StridedError::OffsetOverflow)?;
1266        let dest_start =
1267            usize::try_from(dest.offset()).map_err(|_| StridedError::OffsetOverflow)?;
1268        let source_end = source_start
1269            .checked_add(self.total)
1270            .ok_or(StridedError::OffsetOverflow)?;
1271        let source = operand
1272            .data()
1273            .get(source_start..source_end)
1274            .ok_or(StridedError::OffsetOverflow)?;
1275        // SAFETY: the validated writer owns the destination allocation.
1276        let dest_ptr = unsafe { dest.data_ptr() };
1277        // SAFETY: the source run was resolved above (`operand.data().get`,
1278        // :1260) and the destination run is the plan's own layout: compile set
1279        // `total = checked_total_len(dest_dims)` with `dest_dims == slice_sizes`
1280        // (:1050-:1054), required `dest_strides[0] == 1` on this rank-one path
1281        // (:1228), and `check_call` (:1341) proved the writer carries exactly the
1282        // compiled destination layout, whose reachable offsets `RawStridedMut::new`
1283        // validated (strided-view/src/raw.rs:1036, `validate_bounds` at :1042;
1284        // strided-view/src/view.rs:187). `data_ptr()` (copy_plan.rs:41) is the
1285        // allocation base, so `dest.offset() .. dest.offset() + total` is inside the
1286        // writer's allocation and the chunked workers write disjoint slices of it.
1287        unsafe {
1288            // Chunked across workers above the repository threshold; each
1289            // worker writes a disjoint chunk of the checked destination run.
1290            crate::threading::copy_contiguous(
1291                source.as_ptr(),
1292                dest_ptr.add(dest_start),
1293                self.total,
1294                exec,
1295            );
1296        }
1297        Ok(())
1298    }
1299
1300    fn execute_parallel<T, I, W>(
1301        &self,
1302        dest: &mut W,
1303        operand: &RawStridedRef<'_, T>,
1304        starts: &RawStridedRef<'_, I>,
1305        exec: Exec<'_>,
1306        replay: &WindowReplay,
1307    ) -> Result<()>
1308    where
1309        T: Copy + Send + Sync,
1310        I: GatherIndex,
1311        W: OverwriteWriter<T>,
1312    {
1313        let mut clamped_starts: AxisVec<usize> = (0..self.operand_dims.len()).map(|_| 0).collect();
1314        read_clamped_starts(
1315            starts,
1316            &self.operand_dims,
1317            &self.slice_sizes,
1318            &mut clamped_starts,
1319        )?;
1320        let source_base =
1321            checked_strided_offset(operand.offset(), &self.operand_strides, &clamped_starts)?;
1322        let dest_base = dest.offset();
1323        let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
1324        // SAFETY: the validated writer owns the destination allocation.
1325        let dest_ptr = crate::threading::SendPtr(unsafe { dest.data_ptr() });
1326
1327        crate::threading::parallel_map_reduce(
1328            0..self.total,
1329            exec,
1330            &|range| {
1331                let mut state = replay.decode(range.start, source_base, dest_base)?;
1332                let operand_ptr = operand_ptr.as_const();
1333                let dest_ptr = dest_ptr.as_ptr();
1334
1335                // INVARIANT: each worker decodes one checked range start. Its
1336                // replay range is disjoint, and the injective output layout makes
1337                // all writes distinct across workers.
1338                for _ in range {
1339                    // SAFETY: checked replay bases/resets keep both offsets in
1340                    // their validated allocations.
1341                    unsafe {
1342                        dest_ptr
1343                            .offset(state.dest_offset)
1344                            .write(operand_ptr.offset(state.source_offset).read());
1345                    }
1346                    replay.advance(&mut state);
1347                }
1348                Ok(())
1349            },
1350            &|left, right| left.and(right),
1351        )
1352    }
1353
1354    fn check_call<T, I, W>(
1355        &self,
1356        dest: &W,
1357        operand: &RawStridedRef<'_, T>,
1358        starts: &RawStridedRef<'_, I>,
1359    ) -> Result<()>
1360    where
1361        W: OverwriteWriter<T>,
1362    {
1363        if dest.dims() != &self.dest_dims[..]
1364            || dest.strides() != &self.dest_strides[..]
1365            || operand.dims() != &self.operand_dims[..]
1366            || operand.strides() != &self.operand_strides[..]
1367            || starts.dims() != &self.start_dims[..]
1368            || starts.strides() != &self.start_strides[..]
1369        {
1370            return Err(StridedError::PlanLayoutMismatch);
1371        }
1372        Ok(())
1373    }
1374}
1375
1376impl DynamicUpdateSlicePlan {
1377    /// Compile a dynamic-update-slice traversal.
1378    ///
1379    /// `dest_dims` must match `operand_dims`; execution materializes
1380    /// `dest = operand` and then overwrites the clamped update window.
1381    ///
1382    /// # Errors
1383    ///
1384    /// Returns [`StridedError::StrideLengthMismatch`] when a stride list does
1385    /// not match its dimension list, [`StridedError::RankMismatch`] when
1386    /// `update_dims` differs from the operand rank or the start layout is not a
1387    /// rank-1 vector of that same length,
1388    /// [`StridedError::OffsetOverflow`] when an element count or layout span
1389    /// does not fit `usize`/`isize`, [`StridedError::ShapeMismatch`] when
1390    /// `dest_dims` differs from `operand_dims` in extent or rank,
1391    /// [`StridedError::NonInjectiveOutputLayout`] when the destination layout
1392    /// maps two logical indices onto one offset, and
1393    /// [`StridedError::InvalidAxis`] when an update extent exceeds its
1394    /// operand extent.
1395    // Compile key: the operand, start, update and destination layouts, as four
1396    // dim/stride pairs; a wrapper type would only move the same slices.
1397    #[allow(clippy::too_many_arguments)]
1398    pub fn compile(
1399        operand_dims: &[usize],
1400        operand_strides: &[isize],
1401        start_dims: &[usize],
1402        start_strides: &[isize],
1403        update_dims: &[usize],
1404        update_strides: &[isize],
1405        dest_dims: &[usize],
1406        dest_strides: &[isize],
1407    ) -> Result<Self> {
1408        if operand_dims.len() != operand_strides.len()
1409            || start_dims.len() != start_strides.len()
1410            || update_dims.len() != update_strides.len()
1411            || dest_dims.len() != dest_strides.len()
1412        {
1413            return Err(StridedError::StrideLengthMismatch);
1414        }
1415        if update_dims.len() != operand_dims.len() {
1416            return Err(StridedError::RankMismatch(
1417                update_dims.len(),
1418                operand_dims.len(),
1419            ));
1420        }
1421        validate_start_vector(start_dims, operand_dims.len())?;
1422        checked_total_len(operand_dims)?;
1423        checked_total_len(start_dims)?;
1424        let total = checked_total_len(update_dims)?;
1425        validate_layout_span(operand_dims, operand_strides)?;
1426        validate_layout_span(start_dims, start_strides)?;
1427        validate_layout_span(update_dims, update_strides)?;
1428        validate_layout_span(dest_dims, dest_strides)?;
1429        if dest_dims != operand_dims {
1430            return Err(StridedError::ShapeMismatch(
1431                dest_dims.to_vec(),
1432                operand_dims.to_vec(),
1433            ));
1434        }
1435        if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
1436            return Err(StridedError::NonInjectiveOutputLayout);
1437        }
1438        validate_window_sizes(operand_dims, update_dims)?;
1439        let copy_plan = CopyPlan::compile(operand_dims, dest_strides, operand_strides)?;
1440        let replay = WindowReplay::compile(update_dims, update_strides, dest_strides)?;
1441
1442        Ok(Self {
1443            operand_dims: operand_dims.into(),
1444            operand_strides: operand_strides.into(),
1445            start_dims: start_dims.into(),
1446            start_strides: start_strides.into(),
1447            update_dims: update_dims.into(),
1448            update_strides: update_strides.into(),
1449            dest_dims: dest_dims.into(),
1450            dest_strides: dest_strides.into(),
1451            total,
1452            copy_plan,
1453            window: fuse_pair_layout(update_dims, dest_strides, update_strides),
1454            replay,
1455        })
1456    }
1457
1458    /// Execute the prepared dynamic-update-slice traversal.
1459    ///
1460    /// # Errors
1461    ///
1462    /// Returns [`StridedError::PlanLayoutMismatch`] when the operand, update,
1463    /// start, or destination view does not carry its compiled extents and
1464    /// strides, and [`StridedError::OffsetOverflow`] when the checked update
1465    /// window does not fit `isize`. Both are decided before the operand copy
1466    /// runs, so a failed call leaves `dest` unmodified. Start values are
1467    /// clamped to `operand_dims - update_dims`, so an out-of-range start is
1468    /// not an error.
1469    pub fn execute<T, I>(
1470        &self,
1471        dest: &mut RawStridedMut<'_, T>,
1472        operand: &RawStridedRef<'_, T>,
1473        update: &RawStridedRef<'_, T>,
1474        starts: &RawStridedRef<'_, I>,
1475        exec: Exec<'_>,
1476    ) -> Result<()>
1477    where
1478        T: Copy + Send + Sync,
1479        I: GatherIndex,
1480    {
1481        let mut exec = exec;
1482        self.check_call(dest, operand, update, starts)?;
1483        let window = self.preflight_update_window(dest, update, starts)?;
1484        self.copy_plan.execute(dest, operand, exec.reborrow())?;
1485        self.execute_update_with_writer(dest, update, &window, exec)
1486    }
1487
1488    /// Execute dynamic update into a destination whose reachable slots may be
1489    /// uninitialized. The copy completes before any read-modify-write access,
1490    /// and a rejected update window is reported before the copy.
1491    pub(crate) fn execute_uninit<'a, T, I>(
1492        &self,
1493        dest: &'a mut RawStridedMut<'a, MaybeUninit<T>>,
1494        operand: &RawStridedRef<'_, T>,
1495        update: &RawStridedRef<'_, T>,
1496        starts: &RawStridedRef<'_, I>,
1497        exec: Exec<'_>,
1498    ) -> Result<()>
1499    where
1500        T: Copy + Send + Sync,
1501        I: GatherIndex,
1502    {
1503        self.check_call(dest, operand, update, starts)?;
1504        let window = self.preflight_update_window(dest, update, starts)?;
1505        self.copy_plan
1506            .execute_uninit_then(dest, operand, exec, |mut receipt, exec| {
1507                self.execute_update_with_writer(&mut receipt, update, &window, exec)
1508            })?
1509    }
1510
1511    /// Resolve every fallible step of the update phase before the operand copy.
1512    fn preflight_update_window<'a, T, I, W>(
1513        &self,
1514        dest: &W,
1515        update: &'a RawStridedRef<'_, T>,
1516        starts: &RawStridedRef<'_, I>,
1517    ) -> Result<UpdateWindow<'a, T>>
1518    where
1519        T: Copy,
1520        I: GatherIndex,
1521        W: OverwriteWriter<T>,
1522    {
1523        if self.total == 0 {
1524            return Ok(UpdateWindow::Empty);
1525        }
1526        let mut starts_storage = CoordScratch::new(self.operand_dims.len());
1527        let clamped_starts = starts_storage.as_mut_slice();
1528        read_clamped_starts(
1529            starts,
1530            &self.operand_dims,
1531            &self.update_dims,
1532            clamped_starts,
1533        )?;
1534        let dest_base = checked_strided_offset(dest.offset(), &self.dest_strides, clamped_starts)?;
1535        // The replay adds per-axis steps to these bases, on every worker, so
1536        // the whole window and not only its base has to fit `isize` first.
1537        self.replay.source_span.covers(update.offset())?;
1538        self.replay.dest_span.covers(dest_base)?;
1539        if self.uses_rank_one_contiguous_path() {
1540            let update_start =
1541                usize::try_from(update.offset()).map_err(|_| StridedError::OffsetOverflow)?;
1542            let dest_start =
1543                usize::try_from(dest_base).map_err(|_| StridedError::OffsetOverflow)?;
1544            let update_end = update_start
1545                .checked_add(self.total)
1546                .ok_or(StridedError::OffsetOverflow)?;
1547            let run = update
1548                .data()
1549                .get(update_start..update_end)
1550                .ok_or(StridedError::OffsetOverflow)?;
1551            return Ok(UpdateWindow::RankOne {
1552                update: run,
1553                dest_start,
1554            });
1555        }
1556        Ok(UpdateWindow::Replay { dest_base })
1557    }
1558
1559    fn execute_update_with_writer<T, W>(
1560        &self,
1561        dest: &mut W,
1562        update: &RawStridedRef<'_, T>,
1563        window: &UpdateWindow<'_, T>,
1564        exec: Exec<'_>,
1565    ) -> Result<()>
1566    where
1567        T: Copy + Send + Sync,
1568        W: OverwriteWriter<T>,
1569    {
1570        let dest_base = match *window {
1571            UpdateWindow::Empty => return Ok(()),
1572            UpdateWindow::RankOne { update, dest_start } => {
1573                return self.execute_rank_one_contiguous(dest, update, dest_start, exec)
1574            }
1575            UpdateWindow::Replay { dest_base } => dest_base,
1576        };
1577        if let Some(fused) = &self.window {
1578            return self.execute_fused_window(dest, update, dest_base, fused, exec);
1579        }
1580        let replay = &self.replay;
1581        let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.total);
1582        if !exec.is_serial() {
1583            return self.execute_update_parallel(dest, update, dest_base, exec);
1584        }
1585
1586        let mut state = replay.start(update.offset(), dest_base);
1587        let update_data = update.data();
1588
1589        // INVARIANT: the initial CopyPlan has completed before this replay;
1590        // compile validated both window spans and the preflight proved every
1591        // replay offset fits from the checked bases.
1592        for _ in 0..self.total {
1593            // SAFETY: checked replay metadata proves the current update read.
1594            let value = unsafe { *update_data.as_ptr().offset(state.source_offset) };
1595            // SAFETY: the copied, injective destination layout proves this write
1596            // is initialized and in-bounds.
1597            unsafe { dest.write_at(state.dest_offset, value) };
1598            replay.advance(&mut state);
1599        }
1600        Ok(())
1601    }
1602
1603    /// Replay the compiled fused update window at the preflighted runtime
1604    /// destination base (see [`DynamicSlicePlan`]'s fused window replay).
1605    fn execute_fused_window<T, W>(
1606        &self,
1607        dest: &mut W,
1608        update: &RawStridedRef<'_, T>,
1609        dest_base: isize,
1610        window: &FusedPairLayout,
1611        exec: Exec<'_>,
1612    ) -> Result<()>
1613    where
1614        T: Copy + Send + Sync,
1615        W: OverwriteWriter<T>,
1616    {
1617        // SAFETY: the validated writer owns the destination allocation.
1618        let dest_ptr = unsafe { dest.data_ptr() }.cast::<MaybeUninit<T>>();
1619        let tiles = pair_tiles::<MaybeUninit<T>, T>(window);
1620        // SAFETY: `window` fuses `update_dims` with the checked destination
1621        // and update strides. The update view has exactly `update_dims` and
1622        // its validated layout reaches every source offset; the clamped window
1623        // lies inside `dest_dims`, so every destination offset from
1624        // `dest_base` is reachable through the validated destination layout.
1625        // Compile proved the destination injective, and the exclusive writer
1626        // borrow does not overlap the shared update. The injective destination
1627        // lets the window replay its tiles.
1628        unsafe {
1629            replay_fused_raw(
1630                dest_ptr,
1631                dest_base,
1632                update.data().as_ptr(),
1633                update.offset(),
1634                window,
1635                tiles.as_ref(),
1636                |slot: &mut MaybeUninit<T>, value: T| *slot = MaybeUninit::new(value),
1637                KernelClass::Copy.ns_per_element(),
1638                exec,
1639            );
1640        }
1641        Ok(())
1642    }
1643
1644    #[inline]
1645    fn uses_rank_one_contiguous_path(&self) -> bool {
1646        self.operand_dims.len() == 1
1647            && self.operand_strides[0] == 1
1648            && self.update_strides[0] == 1
1649            && self.dest_strides[0] == 1
1650    }
1651
1652    fn execute_rank_one_contiguous<T, W>(
1653        &self,
1654        dest: &mut W,
1655        update: &[T],
1656        dest_start: usize,
1657        exec: Exec<'_>,
1658    ) -> Result<()>
1659    where
1660        T: Copy + Send + Sync,
1661        W: OverwriteWriter<T>,
1662    {
1663        // SAFETY: the validated writer owns the destination allocation.
1664        let dest_ptr = unsafe { dest.data_ptr() };
1665        // SAFETY: the preflight resolved the update run (`update.data().get`,
1666        // :1534) and proved the window span fits `isize` (`dest_span.covers`,
1667        // :1523); the destination run is the plan's own layout: compile set
1668        // `total = checked_total_len(update_dims)` (:1409) with
1669        // `dest_dims == operand_dims` (:1414) and `validate_window_sizes`
1670        // (:1423), this rank-one path requires `dest_strides[0] == 1` (:1630),
1671        // and `check_call` (:1718) proved the writer carries exactly that
1672        // layout. The last offset this run writes is `dest_start + total - 1`
1673        // (`total >= 1` here: an empty window returns as `UpdateWindow::Empty`
1674        // at :1508 and leaves at :1556), and that offset cannot pass the
1675        // highest one `RawStridedMut::new` validated
1676        // (strided-view/src/raw.rs:1036, `validate_bounds` at :1042). The
1677        // exclusive end `dest_start + total` is one past the run's last
1678        // element and may equal `max + 1`.
1679        unsafe {
1680            // Chunked across workers above the repository threshold; each
1681            // worker writes a disjoint chunk of the checked destination run.
1682            crate::threading::copy_contiguous(
1683                update.as_ptr(),
1684                dest_ptr.add(dest_start),
1685                self.total,
1686                exec,
1687            );
1688        }
1689        Ok(())
1690    }
1691
1692    fn execute_update_parallel<T, W>(
1693        &self,
1694        dest: &mut W,
1695        update: &RawStridedRef<'_, T>,
1696        dest_base: isize,
1697        exec: Exec<'_>,
1698    ) -> Result<()>
1699    where
1700        T: Copy + Send + Sync,
1701        W: OverwriteWriter<T>,
1702    {
1703        let replay = &self.replay;
1704        let source_base = update.offset();
1705        let update_ptr = crate::threading::SendPtr(update.data().as_ptr() as *mut T);
1706        // SAFETY: the validated writer owns the destination allocation.
1707        let dest_ptr = crate::threading::SendPtr(unsafe { dest.data_ptr() });
1708
1709        crate::threading::parallel_map_reduce(
1710            0..self.total,
1711            exec,
1712            &|range| {
1713                let mut state = replay.decode(range.start, source_base, dest_base)?;
1714                let update_ptr = update_ptr.as_const();
1715                let dest_ptr = dest_ptr.as_ptr();
1716
1717                // INVARIANT: the initial operand copy completed before this
1718                // replay; workers own disjoint ranges and injective output
1719                // layouts make their writes distinct. Preflight bounded both
1720                // window spans, so a worker decode cannot overflow.
1721                for _ in range {
1722                    // SAFETY: checked replay bases/resets prove both offsets are
1723                    // within the initialized update and destination allocations.
1724                    unsafe {
1725                        dest_ptr
1726                            .offset(state.dest_offset)
1727                            .write(update_ptr.offset(state.source_offset).read());
1728                    }
1729                    replay.advance(&mut state);
1730                }
1731                Ok(())
1732            },
1733            &|left, right| left.and(right),
1734        )
1735    }
1736
1737    fn check_call<T, I, W>(
1738        &self,
1739        dest: &W,
1740        operand: &RawStridedRef<'_, T>,
1741        update: &RawStridedRef<'_, T>,
1742        starts: &RawStridedRef<'_, I>,
1743    ) -> Result<()>
1744    where
1745        W: OverwriteWriter<T>,
1746    {
1747        if dest.dims() != &self.dest_dims[..]
1748            || dest.strides() != &self.dest_strides[..]
1749            || operand.dims() != &self.operand_dims[..]
1750            || operand.strides() != &self.operand_strides[..]
1751            || update.dims() != &self.update_dims[..]
1752            || update.strides() != &self.update_strides[..]
1753            || starts.dims() != &self.start_dims[..]
1754            || starts.strides() != &self.start_strides[..]
1755        {
1756            return Err(StridedError::PlanLayoutMismatch);
1757        }
1758        Ok(())
1759    }
1760}
1761
1762impl ScatterPlan {
1763    /// Compile an additive scatter traversal.
1764    ///
1765    /// # Errors
1766    ///
1767    /// Returns [`StridedError::StrideLengthMismatch`] when a stride list does
1768    /// not match its dimension list, [`StridedError::OffsetOverflow`] when an
1769    /// element count or layout span does not fit `usize`/`isize`,
1770    /// [`StridedError::ShapeMismatch`] when `dest_dims` differs from
1771    /// `operand_dims` or an update batch extent differs from the index batch
1772    /// shape, and [`StridedError::NonInjectiveOutputLayout`] when the
1773    /// destination layout cannot be proven injective (aliasing elements, or a
1774    /// span the check cannot represent).
1775    /// [`StridedError::InvalidAxis`] reports `inserted_window_dims`,
1776    /// `scatter_dims_to_operand_dims`, or `update_window_dims` that repeat or
1777    /// exceed their rank, `index_vector_dim` beyond the index rank, or an
1778    /// update window extent beyond its operand extent; and
1779    /// [`StridedError::RankMismatch`] reports an index vector that does not
1780    /// match `scatter_dims_to_operand_dims`, a wrong-length
1781    /// `update_window_dims`, or an update batch rank that disagrees with the
1782    /// index batch shape.
1783    // Compile key: the operand, index, update and destination layouts, as four
1784    // dim/stride pairs, plus the scatter spec.
1785    #[allow(clippy::too_many_arguments)]
1786    pub fn compile(
1787        operand_dims: &[usize],
1788        operand_strides: &[isize],
1789        index_dims: &[usize],
1790        index_strides: &[isize],
1791        update_dims: &[usize],
1792        update_strides: &[isize],
1793        dest_dims: &[usize],
1794        dest_strides: &[isize],
1795        spec: ScatterSpec,
1796    ) -> Result<Self> {
1797        if operand_dims.len() != operand_strides.len()
1798            || index_dims.len() != index_strides.len()
1799            || update_dims.len() != update_strides.len()
1800            || dest_dims.len() != dest_strides.len()
1801        {
1802            return Err(StridedError::StrideLengthMismatch);
1803        }
1804        checked_total_len(operand_dims)?;
1805        checked_total_len(index_dims)?;
1806        checked_total_len(update_dims)?;
1807        if dest_dims != operand_dims {
1808            return Err(StridedError::ShapeMismatch(
1809                dest_dims.to_vec(),
1810                operand_dims.to_vec(),
1811            ));
1812        }
1813        if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
1814            return Err(StridedError::NonInjectiveOutputLayout);
1815        }
1816
1817        let operand_rank = operand_dims.len();
1818        validate_unique_axes(&spec.inserted_window_dims, operand_rank)?;
1819        validate_unique_axes(&spec.scatter_dims_to_operand_dims, operand_rank)?;
1820        if spec.index_vector_dim > index_dims.len() {
1821            return Err(StridedError::InvalidAxis {
1822                axis: spec.index_vector_dim,
1823                rank: index_dims.len() + 1,
1824            });
1825        }
1826        let index_vector_size = if spec.index_vector_dim == index_dims.len() {
1827            1
1828        } else {
1829            index_dims[spec.index_vector_dim]
1830        };
1831        if index_vector_size != spec.scatter_dims_to_operand_dims.len() {
1832            return Err(StridedError::RankMismatch(
1833                index_vector_size,
1834                spec.scatter_dims_to_operand_dims.len(),
1835            ));
1836        }
1837
1838        let batch_shape = index_batch_shape(index_dims, spec.index_vector_dim);
1839        let window_dims = operand_window_dims(operand_rank, &spec.inserted_window_dims);
1840        if spec.update_window_dims.len() != window_dims.len() {
1841            return Err(StridedError::RankMismatch(
1842                spec.update_window_dims.len(),
1843                window_dims.len(),
1844            ));
1845        }
1846
1847        let update_rank = update_dims.len();
1848        let expected_batch_rank = update_rank
1849            .checked_sub(spec.update_window_dims.len())
1850            .ok_or(StridedError::RankMismatch(
1851                spec.update_window_dims.len(),
1852                update_rank,
1853            ))?;
1854        if expected_batch_rank != batch_shape.len() {
1855            return Err(StridedError::RankMismatch(
1856                expected_batch_rank,
1857                batch_shape.len(),
1858            ));
1859        }
1860        validate_unique_axes(&spec.update_window_dims, update_rank)?;
1861
1862        let mut is_update_window_dim: AxisVec<bool> = (0..update_rank).map(|_| false).collect();
1863        for &axis in &spec.update_window_dims {
1864            is_update_window_dim[axis] = true;
1865        }
1866
1867        let mut batch_axis = 0usize;
1868        for axis in 0..update_rank {
1869            if !is_update_window_dim[axis] {
1870                if update_dims[axis] != batch_shape[batch_axis] {
1871                    return Err(StridedError::ShapeMismatch(
1872                        update_dims.to_vec(),
1873                        expected_scatter_update_shape(&batch_shape, &spec, update_dims).to_vec(),
1874                    ));
1875                }
1876                batch_axis += 1;
1877            }
1878        }
1879
1880        let mut window_shape: AxisVec<usize> = (0..operand_rank).map(|_| 1).collect();
1881        let mut window_shape_updates: AxisVec<usize> =
1882            AxisVec::with_capacity(spec.update_window_dims.len());
1883        for (pos, &update_axis) in spec.update_window_dims.iter().enumerate() {
1884            let dim = update_dims[update_axis];
1885            window_shape_updates.push(dim);
1886            window_shape[window_dims[pos]] = dim;
1887        }
1888        validate_window_sizes(operand_dims, &window_shape)?;
1889
1890        let batch_elems = checked_total_len(&batch_shape)?;
1891        let window_elems = checked_total_len(&window_shape_updates)?;
1892        let copy_plan = CopyPlan::compile(operand_dims, dest_strides, operand_strides)?;
1893        let replay = ScatterReplay::compile(
1894            &batch_shape,
1895            index_dims,
1896            index_strides,
1897            spec.index_vector_dim,
1898            spec.scatter_dims_to_operand_dims.len(),
1899            update_dims,
1900            update_strides,
1901            &spec.update_window_dims,
1902            &is_update_window_dim,
1903            &window_shape_updates,
1904            &window_dims,
1905            dest_strides,
1906        )?;
1907
1908        Ok(Self {
1909            operand_dims: operand_dims.into(),
1910            operand_strides: operand_strides.into(),
1911            index_dims: index_dims.into(),
1912            index_strides: index_strides.into(),
1913            update_dims: update_dims.into(),
1914            update_strides: update_strides.into(),
1915            dest_dims: dest_dims.into(),
1916            dest_strides: dest_strides.into(),
1917            spec,
1918            window_shape,
1919            batch_elems,
1920            window_elems,
1921            copy_plan,
1922            replay,
1923        })
1924    }
1925
1926    /// Execute the prepared additive scatter traversal.
1927    ///
1928    /// # Errors
1929    ///
1930    /// Returns [`StridedError::PlanLayoutMismatch`] when the operand, index,
1931    /// update, or destination view does not carry its compiled extents and
1932    /// strides, before the operand copy runs. Start values are clamped into
1933    /// the operand window, so an out-of-range scatter index is not an error.
1934    #[inline(always)]
1935    pub fn execute<T, I>(
1936        &self,
1937        dest: &mut RawStridedMut<'_, T>,
1938        operand: &RawStridedRef<'_, T>,
1939        scatter_indices: &RawStridedRef<'_, I>,
1940        updates: &RawStridedRef<'_, T>,
1941        exec: Exec<'_>,
1942    ) -> Result<()>
1943    where
1944        T: Copy + Add<Output = T> + Send + Sync,
1945        I: GatherIndex,
1946    {
1947        self.check_call(dest, operand, scatter_indices, updates)?;
1948        self.copy_plan.execute(dest, operand, exec)?;
1949        self.execute_updates(dest, scatter_indices, updates, |a, b| a + b)
1950    }
1951
1952    /// Execute additive scatter into a destination whose reachable slots may
1953    /// be uninitialized. The operand copy completes before any RMW access.
1954    pub(crate) fn execute_uninit<'a, T, I>(
1955        &self,
1956        dest: &'a mut RawStridedMut<'a, MaybeUninit<T>>,
1957        operand: &RawStridedRef<'_, T>,
1958        scatter_indices: &RawStridedRef<'_, I>,
1959        updates: &RawStridedRef<'_, T>,
1960        combine: fn(T, T) -> T,
1961        exec: Exec<'_>,
1962    ) -> Result<()>
1963    where
1964        T: Copy + Add<Output = T> + Send + Sync,
1965        I: GatherIndex,
1966    {
1967        self.check_call(dest, operand, scatter_indices, updates)?;
1968        self.copy_plan
1969            .execute_uninit_then(dest, operand, exec, |mut receipt, _| {
1970                self.execute_updates(&mut receipt, scatter_indices, updates, combine)
1971            })?
1972    }
1973
1974    #[inline(always)]
1975    fn execute_updates<T, I, W, F>(
1976        &self,
1977        dest: &mut W,
1978        scatter_indices: &RawStridedRef<'_, I>,
1979        updates: &RawStridedRef<'_, T>,
1980        combine: F,
1981    ) -> Result<()>
1982    where
1983        T: Copy + Send + Sync,
1984        I: GatherIndex,
1985        W: ReadModifyWrite<T>,
1986        F: Fn(T, T) -> T + Copy,
1987    {
1988        if self.batch_elems == 0 || self.window_elems == 0 {
1989            return Ok(());
1990        }
1991        if self.uses_rank_one_scalar_update_path() {
1992            return self.execute_rank_one_scalar_updates(dest, scatter_indices, updates, combine);
1993        }
1994        self.execute_generic_updates(dest, scatter_indices, updates, combine)
1995    }
1996
1997    #[inline(never)]
1998    fn execute_generic_updates<T, I, W, F>(
1999        &self,
2000        dest: &mut W,
2001        scatter_indices: &RawStridedRef<'_, I>,
2002        updates: &RawStridedRef<'_, T>,
2003        combine: F,
2004    ) -> Result<()>
2005    where
2006        T: Copy + Send + Sync,
2007        I: GatherIndex,
2008        W: ReadModifyWrite<T>,
2009        F: Fn(T, T) -> T + Copy,
2010    {
2011        // Overlapping additive updates are order-sensitive, so this remains a
2012        // deterministic serial replay until a combine-aware parallel plan exists.
2013        let replay = &self.replay;
2014
2015        let mut operand_base_storage = CoordScratch::new(self.operand_dims.len());
2016        let operand_base = operand_base_storage.as_mut_slice();
2017        let mut batch_state = replay
2018            .batch
2019            .decode(0, scatter_indices.offset(), updates.offset())?;
2020        let index_data = scatter_indices.data();
2021        let update_data = updates.data();
2022
2023        // INVARIANT: batch and window replay metadata was checked at compile;
2024        // the indirect component loop below is the only data-dependent lookup.
2025        for _ in 0..self.batch_elems {
2026            operand_base.fill(0);
2027            for (&component_offset, &operand_axis) in replay
2028                .index_component_offsets
2029                .iter()
2030                .zip(self.spec.scatter_dims_to_operand_dims.iter())
2031            {
2032                let index_offset = batch_state
2033                    .source_offset
2034                    .checked_add(component_offset)
2035                    .ok_or(StridedError::OffsetOverflow)?;
2036                // SAFETY: checked batch replay and component offsets keep this
2037                // indirect index read inside the validated index allocation.
2038                let start = unsafe { *index_data.as_ptr().offset(index_offset) }.to_i64();
2039                operand_base[operand_axis] = clamp_window_start(
2040                    start,
2041                    self.operand_dims[operand_axis],
2042                    self.window_shape[operand_axis],
2043                );
2044            }
2045
2046            let dest_base = checked_strided_offset(dest.offset(), dest.strides(), operand_base)?;
2047            let mut window_state = replay
2048                .window
2049                .decode(0, batch_state.dest_offset, dest_base)?;
2050            for _ in 0..self.window_elems {
2051                // SAFETY: copy completion and checked replay state prove both
2052                // the update read and initialized destination RMW are valid.
2053                let value = unsafe { *update_data.as_ptr().offset(window_state.source_offset) };
2054                unsafe { dest.add_at(window_state.dest_offset, value, combine) };
2055                replay.window.advance(&mut window_state);
2056            }
2057            replay.batch.advance(&mut batch_state);
2058        }
2059        Ok(())
2060    }
2061
2062    fn uses_rank_one_scalar_update_path(&self) -> bool {
2063        self.operand_dims.len() == 1
2064            && self.index_dims.len() == 2
2065            && self.update_dims.len() == 1
2066            && self.dest_dims.len() == 1
2067            && self.operand_strides[0] == 1
2068            && self.index_strides[0] == 1
2069            && self.update_strides[0] == 1
2070            && self.dest_strides[0] == 1
2071            && self.index_dims[1] == 1
2072            && self.spec.update_window_dims.is_empty()
2073            && self.spec.inserted_window_dims.as_slice() == [0]
2074            && self.spec.scatter_dims_to_operand_dims.as_slice() == [0]
2075            && self.spec.index_vector_dim == 1
2076            && self.window_elems == 1
2077    }
2078
2079    #[inline(always)]
2080    fn execute_rank_one_scalar_updates<T, I, W, F>(
2081        &self,
2082        dest: &mut W,
2083        scatter_indices: &RawStridedRef<'_, I>,
2084        updates: &RawStridedRef<'_, T>,
2085        combine: F,
2086    ) -> Result<()>
2087    where
2088        T: Copy,
2089        I: GatherIndex,
2090        W: ReadModifyWrite<T>,
2091        F: Fn(T, T) -> T + Copy,
2092    {
2093        let mut index_offset = scatter_indices.offset();
2094        let mut update_offset = updates.offset();
2095        let dest_offset = dest.offset();
2096        let index_data = scatter_indices.data();
2097        let update_data = updates.data();
2098        // SAFETY: the validated writer owns the destination allocation.
2099        let dest_ptr = unsafe { dest.data_ptr() };
2100
2101        // INVARIANT: compile and check_call validated compact rank-one index
2102        // and update layouts. Ordered replay preserves repeated-index semantics.
2103        // `index_offset`/`update_offset` are the pointer walk, not counters.
2104        #[allow(clippy::explicit_counter_loop)]
2105        for _ in 0..self.batch_elems {
2106            // SAFETY: the invariant above proves index/update reads and the
2107            // clamped destination offset are in their validated allocations.
2108            unsafe {
2109                let start = (*index_data.as_ptr().offset(index_offset)).to_i64();
2110                let output_offset =
2111                    dest_offset + clamp_window_start(start, self.operand_dims[0], 1) as isize;
2112                let output = dest_ptr.offset(output_offset);
2113                output.write(combine(
2114                    output.read(),
2115                    *update_data.as_ptr().offset(update_offset),
2116                ));
2117            }
2118            index_offset += 1;
2119            update_offset += 1;
2120        }
2121        Ok(())
2122    }
2123
2124    fn check_call<T, I, W>(
2125        &self,
2126        dest: &W,
2127        operand: &RawStridedRef<'_, T>,
2128        scatter_indices: &RawStridedRef<'_, I>,
2129        updates: &RawStridedRef<'_, T>,
2130    ) -> Result<()>
2131    where
2132        W: OverwriteWriter<T>,
2133    {
2134        if dest.dims() != &self.dest_dims[..]
2135            || dest.strides() != &self.dest_strides[..]
2136            || operand.dims() != &self.operand_dims[..]
2137            || operand.strides() != &self.operand_strides[..]
2138            || scatter_indices.dims() != &self.index_dims[..]
2139            || scatter_indices.strides() != &self.index_strides[..]
2140            || updates.dims() != &self.update_dims[..]
2141            || updates.strides() != &self.update_strides[..]
2142        {
2143            return Err(StridedError::PlanLayoutMismatch);
2144        }
2145        Ok(())
2146    }
2147}
2148
2149fn validate_unique_axes(axes: &[usize], rank: usize) -> Result<()> {
2150    // Inline boolean metadata: rank <= INLINE_RANK validation allocates
2151    // nothing, and it spills above the inline bound.
2152    let mut seen: InlineVec<bool> = InlineVec::new();
2153    seen.resize(rank, false);
2154    for &axis in axes {
2155        if axis >= rank {
2156            return Err(StridedError::InvalidAxis { axis, rank });
2157        }
2158        if seen[axis] {
2159            return Err(StridedError::InvalidAxis { axis, rank });
2160        }
2161        seen[axis] = true;
2162    }
2163    Ok(())
2164}
2165
2166fn validate_start_vector(start_dims: &[usize], operand_rank: usize) -> Result<()> {
2167    if start_dims.len() != 1 {
2168        return Err(StridedError::RankMismatch(start_dims.len(), 1));
2169    }
2170    if start_dims[0] != operand_rank {
2171        return Err(StridedError::RankMismatch(start_dims[0], operand_rank));
2172    }
2173    Ok(())
2174}
2175
2176fn validate_window_sizes(operand_dims: &[usize], window_sizes: &[usize]) -> Result<()> {
2177    if operand_dims.len() != window_sizes.len() {
2178        return Err(StridedError::RankMismatch(
2179            window_sizes.len(),
2180            operand_dims.len(),
2181        ));
2182    }
2183    for (axis, (&window, &dim)) in window_sizes.iter().zip(operand_dims.iter()).enumerate() {
2184        if window > dim {
2185            return Err(StridedError::InvalidAxis {
2186                axis,
2187                rank: operand_dims.len(),
2188            });
2189        }
2190    }
2191    Ok(())
2192}
2193
2194fn read_clamped_starts<I>(
2195    starts: &RawStridedRef<'_, I>,
2196    operand_dims: &[usize],
2197    window_sizes: &[usize],
2198    out: &mut [usize],
2199) -> Result<()>
2200where
2201    I: GatherIndex,
2202{
2203    debug_assert_eq!(operand_dims.len(), window_sizes.len());
2204    debug_assert_eq!(operand_dims.len(), out.len());
2205    for axis in 0..operand_dims.len() {
2206        let offset = checked_offset_add(starts.offset(), starts.strides()[0], axis)?;
2207        let start = unsafe { *starts.data().as_ptr().offset(offset) }.to_i64();
2208        out[axis] = clamp_window_start(start, operand_dims[axis], window_sizes[axis]);
2209    }
2210    Ok(())
2211}
2212
2213#[inline]
2214fn clamp_window_start(start: i64, dim_size: usize, window_size: usize) -> usize {
2215    let max_start = dim_size.saturating_sub(window_size) as i64;
2216    start.clamp(0, max_start) as usize
2217}
2218
2219fn expected_scatter_update_shape(
2220    batch_shape: &[usize],
2221    spec: &ScatterSpec,
2222    update_dims: &[usize],
2223) -> AxisVec<usize> {
2224    let mut expected: AxisVec<usize> = AxisVec::with_capacity(update_dims.len());
2225    let mut batch_axis = 0usize;
2226    for (axis, &dim) in update_dims.iter().enumerate() {
2227        if spec.update_window_dims.contains(&axis) {
2228            expected.push(dim);
2229        } else {
2230            expected.push(batch_shape[batch_axis]);
2231            batch_axis += 1;
2232        }
2233    }
2234    expected
2235}
2236
2237fn operand_window_dims(rank: usize, collapsed_slice_dims: &[usize]) -> AxisVec<usize> {
2238    (0..rank)
2239        .filter(|axis| !collapsed_slice_dims.contains(axis))
2240        .collect()
2241}
2242
2243fn index_batch_shape(index_dims: &[usize], index_vector_dim: usize) -> AxisVec<usize> {
2244    if index_vector_dim == index_dims.len() {
2245        return index_dims.into();
2246    }
2247    index_dims
2248        .iter()
2249        .enumerate()
2250        .filter_map(|(axis, &dim)| (axis != index_vector_dim).then_some(dim))
2251        .collect()
2252}
2253
2254/// Validate a layout's reachable offsets and return them relative to its base.
2255fn validate_layout_span(dims: &[usize], strides: &[isize]) -> Result<OffsetSpan> {
2256    if dims.len() != strides.len() {
2257        return Err(StridedError::StrideLengthMismatch);
2258    }
2259    let mut span = OffsetSpan::default();
2260    for (&dim, &stride) in dims.iter().zip(strides.iter()) {
2261        let last =
2262            isize::try_from(dim.saturating_sub(1)).map_err(|_| StridedError::OffsetOverflow)?;
2263        let extent = stride
2264            .checked_mul(last)
2265            .ok_or(StridedError::OffsetOverflow)?;
2266        if extent < 0 {
2267            span.min = span
2268                .min
2269                .checked_add(extent)
2270                .ok_or(StridedError::OffsetOverflow)?;
2271        } else {
2272            span.max = span
2273                .max
2274                .checked_add(extent)
2275                .ok_or(StridedError::OffsetOverflow)?;
2276        }
2277    }
2278    Ok(span)
2279}
2280
2281fn checked_replay_reset(dim: usize, step: isize) -> Result<isize> {
2282    if dim == 0 {
2283        return Ok(0);
2284    }
2285    let last = isize::try_from(dim - 1).map_err(|_| StridedError::OffsetOverflow)?;
2286    step.checked_mul(last)
2287        .and_then(isize::checked_neg)
2288        .ok_or(StridedError::OffsetOverflow)
2289}
2290
2291fn checked_total_len(dims: &[usize]) -> Result<usize> {
2292    if dims.is_empty() {
2293        return Ok(1);
2294    }
2295    dims.iter()
2296        .try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
2297        .ok_or(StridedError::OffsetOverflow)
2298}
2299
2300fn checked_strided_offset(base: isize, strides: &[isize], index: &[usize]) -> Result<isize> {
2301    let mut offset = base;
2302    for (&stride, &coord) in strides.iter().zip(index.iter()) {
2303        offset = checked_offset_add(offset, stride, coord)?;
2304    }
2305    Ok(offset)
2306}
2307
2308fn checked_offset_add(base: isize, stride: isize, coord: usize) -> Result<isize> {
2309    let coord = isize::try_from(coord).map_err(|_| StridedError::OffsetOverflow)?;
2310    let scaled = stride
2311        .checked_mul(coord)
2312        .ok_or(StridedError::OffsetOverflow)?;
2313    base.checked_add(scaled).ok_or(StridedError::OffsetOverflow)
2314}
2315
2316struct CoordScratch {
2317    inline: [usize; RAW_FUSED_RANK_LIMIT],
2318    heap: Option<Vec<usize>>,
2319    len: usize,
2320}
2321
2322impl CoordScratch {
2323    fn new(len: usize) -> Self {
2324        if len <= RAW_FUSED_RANK_LIMIT {
2325            Self {
2326                inline: [0; RAW_FUSED_RANK_LIMIT],
2327                heap: None,
2328                len,
2329            }
2330        } else {
2331            Self {
2332                inline: [0; RAW_FUSED_RANK_LIMIT],
2333                heap: Some(vec![0; len]),
2334                len,
2335            }
2336        }
2337    }
2338
2339    fn as_mut_slice(&mut self) -> &mut [usize] {
2340        match &mut self.heap {
2341            Some(heap) => heap,
2342            None => &mut self.inline[..self.len],
2343        }
2344    }
2345}
2346
2347#[cfg(test)]
2348#[path = "gather_plan/tests/tests.rs"]
2349mod tests;
2350
2351#[cfg(test)]
2352#[path = "gather_plan/tests/parallel_tests.rs"]
2353mod parallel_tests;