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