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