Skip to main content

strided_basic/
erased.rs

1use crate::cost::KernelClass;
2use crate::erased_common::*;
3use crate::*;
4use core::mem::MaybeUninit;
5use num_complex::{Complex32, Complex64};
6use num_traits::{One, Zero};
7mod arg_reduce;
8mod line;
9mod norm;
10mod reduce_kernel;
11mod scan;
12
13pub use arg_reduce::{ArgReduceOp, ErasedArgReducePlan};
14pub use norm::{ErasedNormPlan, NormKind, NormSpec};
15pub use scan::{ErasedScanPlan, ScanOp, ScanOptions};
16
17use reduce_kernel::{
18    reduce_axes_range, reduce_full_range, AxesRange, FullTraversal, MaxKernel, MinKernel,
19    ReassociatedProductKernel, ReduceKernel, StableProductKernel, StableProductScalar, SumKernel,
20    SumSquaresKernel,
21};
22
23trait ReduceWriter<T> {
24    fn offset(&self) -> isize;
25    /// # Safety
26    /// The pointer may only be used within the validated destination extent.
27    unsafe fn ptr(&mut self) -> *mut T;
28    fn extent(&self) -> usize;
29    /// # Safety
30    /// The offset must be an in-bounds logical reduction destination offset.
31    unsafe fn write_at(&mut self, offset: isize, value: T) {
32        debug_assert!(offset >= 0 && (offset as usize) < self.extent());
33        // SAFETY: reduction layout validation proves the logical offset.
34        unsafe { self.ptr().offset(offset).write(value) }
35    }
36}
37
38struct RawReduceWriter<'a, T> {
39    ptr: *mut T,
40    extent: usize,
41    offset: isize,
42    _marker: core::marker::PhantomData<&'a mut [MaybeUninit<T>]>,
43}
44
45impl<'a, T> ReduceWriter<T> for RawReduceWriter<'a, T> {
46    fn offset(&self) -> isize {
47        self.offset
48    }
49    unsafe fn ptr(&mut self) -> *mut T {
50        self.ptr
51    }
52    fn extent(&self) -> usize {
53        self.extent
54    }
55}
56
57/// Dtype-erased wrapper around [`CopyPlan`].
58#[derive(Clone, Debug)]
59pub struct ErasedCopyPlan {
60    dtype: KernelDType,
61    plan: CopyPlan,
62}
63
64/// Dtype-erased concatenate wrapper.
65#[derive(Clone, Debug)]
66pub struct ErasedConcatenatePlan {
67    dtype: KernelDType,
68    plan: ConcatenatePlan,
69}
70
71impl ErasedCopyPlan {
72    /// Compile a copy plan for one dtype and layout pair.
73    ///
74    /// # Errors
75    ///
76    /// Returns [`StridedError::StrideLengthMismatch`] when `dims`,
77    /// `dst_strides`, and `src_strides` do not all have the same length,
78    /// [`StridedError::OffsetOverflow`] when the element count does not fit
79    /// `usize`, and [`StridedError::NonInjectiveOutputLayout`] when the
80    /// destination layout cannot be proven injective (aliasing elements, or a
81    /// span the check cannot represent). The dtype
82    /// is only stored here; [`execute`](Self::execute) checks it.
83    pub fn compile(
84        dtype: KernelDType,
85        dims: &[usize],
86        dst_strides: &[isize],
87        src_strides: &[isize],
88    ) -> Result<Self> {
89        Ok(Self {
90            dtype,
91            plan: CopyPlan::compile(dims, dst_strides, src_strides)?,
92        })
93    }
94
95    #[inline]
96    pub fn dtype(&self) -> KernelDType {
97        self.dtype
98    }
99
100    /// `dest = src` through a non-generic dtype-erased replay boundary.
101    ///
102    /// # Errors
103    ///
104    /// Returns [`StridedError::DTypeMismatch`] when `dest` or `src` carries a
105    /// different dtype than the plan, and
106    /// [`StridedError::PlanLayoutMismatch`] when a view does not carry the
107    /// compiled extents and strides. Nothing is written unless every check
108    /// succeeds.
109    pub fn execute(
110        &self,
111        dest: &mut ErasedRawStridedMut<'_>,
112        src: &ErasedRawStridedRef<'_>,
113        exec: Exec<'_>,
114    ) -> Result<()> {
115        self.check_dtype(dest.dtype())?;
116        self.check_dtype(src.dtype())?;
117
118        match self.dtype {
119            KernelDType::F32 => execute_copy::<f32>(&self.plan, dest, src, exec),
120            KernelDType::F64 => execute_copy::<f64>(&self.plan, dest, src, exec),
121            KernelDType::I32 => execute_copy::<i32>(&self.plan, dest, src, exec),
122            KernelDType::I64 => execute_copy::<i64>(&self.plan, dest, src, exec),
123            KernelDType::Bool => execute_copy::<bool>(&self.plan, dest, src, exec),
124            KernelDType::C32 => execute_copy::<Complex32>(&self.plan, dest, src, exec),
125            KernelDType::C64 => execute_copy::<Complex64>(&self.plan, dest, src, exec),
126            _ => Err(StridedError::UnsupportedDType {
127                dtype: self.dtype.label(),
128            }),
129        }
130    }
131
132    fn check_dtype(&self, actual: KernelDType) -> Result<()> {
133        if actual != self.dtype {
134            return Err(StridedError::DTypeMismatch {
135                expected: self.dtype.label(),
136                actual: actual.label(),
137            });
138        }
139        Ok(())
140    }
141}
142
143impl ErasedConcatenatePlan {
144    /// Validate and store a concatenate plan for one dtype and fixed layout set.
145    ///
146    /// # Errors
147    ///
148    /// Returns [`StridedError::UnsupportedArity`] when no input is given,
149    /// [`StridedError::RankMismatch`] when
150    /// `input_dims` and `input_strides` list different numbers of layouts or
151    /// an input rank differs from the first input's rank,
152    /// [`StridedError::StrideLengthMismatch`] when a stride list does not
153    /// match its dimension list, [`StridedError::InvalidAxis`] when `axis` is
154    /// outside the rank, [`StridedError::ShapeMismatch`] when a
155    /// non-concatenated extent differs or the destination is not the
156    /// concatenation of the inputs,
157    /// [`StridedError::NonInjectiveOutputLayout`] when the destination layout
158    /// maps two logical indices onto one offset, and
159    /// [`StridedError::OffsetOverflow`] when a segment length or base offset
160    /// cannot be represented.
161    pub fn compile(
162        dtype: KernelDType,
163        input_dims: &[&[usize]],
164        input_strides: &[&[isize]],
165        dest_dims: &[usize],
166        dest_strides: &[isize],
167        axis: usize,
168    ) -> Result<Self> {
169        check_static_indexing_dtype(dtype)?;
170        Ok(Self {
171            dtype,
172            plan: ConcatenatePlan::compile(
173                input_dims,
174                input_strides,
175                dest_dims,
176                dest_strides,
177                axis,
178            )?,
179        })
180    }
181
182    #[inline]
183    pub fn dtype(&self) -> KernelDType {
184        self.dtype
185    }
186
187    #[inline]
188    pub fn plan(&self) -> &ConcatenatePlan {
189        &self.plan
190    }
191
192    /// Execute concatenate into an erased output descriptor.
193    ///
194    /// # Errors
195    ///
196    /// Returns [`StridedError::DTypeMismatch`] when the destination or any
197    /// input carries a different dtype than the plan,
198    /// [`StridedError::RankMismatch`] when the number of inputs differs from
199    /// the compiled one, [`StridedError::PlanLayoutMismatch`] when the
200    /// destination or an input does not carry its compiled extents and
201    /// strides, and [`StridedError::OffsetOverflow`] when a segment's
202    /// destination offset cannot be expressed in `isize`. Every check runs
203    /// before the first segment is written.
204    pub fn execute(
205        &self,
206        dest: &mut ErasedRawStridedMut<'_>,
207        inputs: &[ErasedRawStridedRef<'_>],
208        exec: Exec<'_>,
209    ) -> Result<()> {
210        check_dtype(self.dtype, dest.dtype())?;
211        for input in inputs {
212            check_dtype(self.dtype, input.dtype())?;
213        }
214
215        match self.dtype {
216            KernelDType::F32 => execute_concatenate::<f32>(&self.plan, dest, inputs, exec),
217            KernelDType::F64 => execute_concatenate::<f64>(&self.plan, dest, inputs, exec),
218            KernelDType::I32 => execute_concatenate::<i32>(&self.plan, dest, inputs, exec),
219            KernelDType::I64 => execute_concatenate::<i64>(&self.plan, dest, inputs, exec),
220            KernelDType::Bool => execute_concatenate::<bool>(&self.plan, dest, inputs, exec),
221            KernelDType::C32 => execute_concatenate::<Complex32>(&self.plan, dest, inputs, exec),
222            KernelDType::C64 => execute_concatenate::<Complex64>(&self.plan, dest, inputs, exec),
223            _ => Err(StridedError::UnsupportedDType {
224                dtype: self.dtype.label(),
225            }),
226        }
227    }
228
229    /// Execute concatenate as a full overwrite of uninitialized output storage.
230    /// On success, every reachable destination slot is fully overwritten;
231    /// unreachable holes are neither read nor initialized. Validation errors
232    /// are returned before any destination write. A panic during execution
233    /// may leave a partially initialized `MaybeUninit` destination, which is
234    /// still safely droppable; no readable value is promised for unwritten
235    /// reachable slots.
236    ///
237    /// # Errors
238    ///
239    /// Returns [`StridedError::DTypeMismatch`] when the destination or any
240    /// input carries a different dtype than the plan,
241    /// [`StridedError::RankMismatch`] when the number of inputs differs from
242    /// the compiled one, [`StridedError::OverlappingInputOutput`] when an
243    /// input allocation overlaps the destination,
244    /// [`StridedError::InvalidBoolByte`] when `bool` input bytes are not 0 or
245    /// 1, [`StridedError::PlanLayoutMismatch`] when the destination or an
246    /// input does not carry its compiled extents and strides, and
247    /// [`StridedError::OffsetOverflow`] when a segment's destination offset
248    /// cannot be expressed in `isize`. Everything above is returned before any
249    /// destination write.
250    pub fn execute_uninit(
251        &self,
252        dest: &mut ErasedRawStridedUninitMut<'_>,
253        inputs: &[ErasedRawStridedPtr<'_>],
254        exec: Exec<'_>,
255    ) -> Result<()> {
256        check_dtype(self.dtype, dest.dtype())?;
257        if inputs.len() != self.plan.input_count() {
258            return Err(StridedError::RankMismatch(
259                inputs.len(),
260                self.plan.input_count(),
261            ));
262        }
263        for input in inputs {
264            check_dtype(self.dtype, input.dtype())?;
265        }
266        for (position, input) in inputs.iter().enumerate() {
267            validate_uninit_no_overlap(dest, input, position)?;
268        }
269        for input in inputs {
270            // SAFETY: input/output overlap was rejected before forming references.
271            unsafe { input.try_as_ref_after_no_overlap() }?;
272        }
273
274        match self.dtype {
275            KernelDType::F32 => execute_concatenate_uninit::<f32>(&self.plan, dest, inputs, exec),
276            KernelDType::F64 => execute_concatenate_uninit::<f64>(&self.plan, dest, inputs, exec),
277            KernelDType::I32 => execute_concatenate_uninit::<i32>(&self.plan, dest, inputs, exec),
278            KernelDType::I64 => execute_concatenate_uninit::<i64>(&self.plan, dest, inputs, exec),
279            KernelDType::Bool => execute_concatenate_uninit::<bool>(&self.plan, dest, inputs, exec),
280            KernelDType::C32 => {
281                execute_concatenate_uninit::<Complex32>(&self.plan, dest, inputs, exec)
282            }
283            KernelDType::C64 => {
284                execute_concatenate_uninit::<Complex64>(&self.plan, dest, inputs, exec)
285            }
286            _ => Err(StridedError::UnsupportedDType {
287                dtype: self.dtype.label(),
288            }),
289        }
290    }
291}
292
293/// Runtime reduction operation for dtype-erased full reductions.
294#[non_exhaustive]
295#[derive(Clone, Copy, Debug, Eq, PartialEq)]
296pub enum ReduceOp {
297    Sum,
298    Product,
299    /// Reassociated, overflow/underflow-safe product.
300    ///
301    /// Tracks a signed mantissa and an exact integer exponent per lane, so
302    /// factors outside the dtype range do not overflow or underflow a partial.
303    /// The reduction is reassociated and threaded like [`Self::Sum`].
304    ///
305    /// A zero, subnormal, infinite or NaN input cannot be represented by the
306    /// exponent-tracked accumulator; the affected output is then recomputed in
307    /// source order, keeping IEEE propagation (`0 * inf = NaN`, a zero or an
308    /// infinity result) identical to the sequential fold. For integers this is
309    /// the reassociated wrapping product and for complex dtypes the
310    /// source-order product.
311    StableProduct,
312    /// Sum of same-dtype rounded squares.
313    ///
314    /// Each input is first multiplied by itself without FMA contraction, then
315    /// accumulated under the same association policy as [`Self::Sum`].
316    SumSquares,
317    /// NaN-propagating maximum for `f32`/`f64`, ordered maximum for
318    /// `i32`/`i64`.
319    ///
320    /// Any NaN operand makes the result the canonical NaN of the dtype. The
321    /// identity written for an empty reduction is `-inf` for floats and the
322    /// dtype minimum for integers. Complex and `bool` dtypes are rejected.
323    /// When the reduced values contain both `-0.0` and `+0.0`, which zero is
324    /// returned is unspecified.
325    Max,
326    /// NaN-propagating minimum for `f32`/`f64`, ordered minimum for
327    /// `i32`/`i64`.
328    ///
329    /// Any NaN operand makes the result the canonical NaN of the dtype. The
330    /// identity written for an empty reduction is `+inf` for floats and the
331    /// dtype maximum for integers. Complex and `bool` dtypes are rejected.
332    /// When the reduced values contain both `-0.0` and `+0.0`, which zero is
333    /// returned is unspecified.
334    Min,
335}
336
337/// Dtype-erased reduction wrapper.
338///
339/// This is the erased replay boundary for full-tensor scalar reductions and
340/// axis reductions with a fixed output layout. It supports only operations with
341/// an unambiguous identity value in the selected dtype.
342///
343/// # Evaluation order
344///
345/// The op is matched once per execution; every loop runs a kernel
346/// specialized for one `(dtype, op)` pair. Integer results are exact
347/// (wrapping) and [`ReduceOp::Max`] / [`ReduceOp::Min`] do not depend on
348/// order, so the rules below only affect the rounding of floating point and
349/// complex [`ReduceOp::Sum`], [`ReduceOp::Product`], [`ReduceOp::StableProduct`]
350/// and [`ReduceOp::SumSquares`]. Two details of float max and min follow the
351/// visit order: a NaN input makes the result NaN, but which NaN (payload and
352/// sign) is returned is unspecified, and when the extremum is a zero its sign
353/// is unspecified if both `+0.0` and `-0.0` occur.
354///
355/// [`ReduceOp::Product`] is the reassociated product, matching PyTorch: it
356/// splits each run into lanes, uses the SIMD product where available, threads a
357/// full reduction, and combines the partials in a fixed tree. It is fast and
358/// never recomputes an output, but reassociating can overflow a lane to `inf`
359/// and underflow another to `0`, whose `inf * 0` combine is `NaN`; an
360/// alternating `2.0`/`0.5` input at `2^600`/`2^-600` scale can therefore give
361/// `NaN` where the source-order product is representable (tenferro-rs#2150).
362///
363/// [`ReduceOp::StableProduct`] avoids that. For `f32`/`f64` it tracks a signed
364/// mantissa and an exact integer exponent per lane and across runs and workers,
365/// so a partial cannot overflow or underflow; the final value is scaled with a
366/// correctly rounded `ldexp`. An input that is zero, subnormal, infinite or NaN
367/// cannot be represented this way, so an output that saw one is recomputed in
368/// source order, preserving IEEE propagation. It is reassociated and threaded
369/// like [`ReduceOp::Product`] otherwise. For integers it is the reassociated
370/// wrapping product and for complex dtypes the source-order product.
371///
372/// * Full reductions (from [`Self::compile`], or [`Self::compile_axes`]
373///   with every axis reduced) visit the source in a layout derived order:
374///   extent one axes are dropped, the rest are ordered by increasing
375///   absolute stride and contiguous axes are fused into runs. Each run is
376///   reduced by the SIMD kernel (unit stride, `simd` feature), a sixteen
377///   lane kernel (other unit stride runs) or an eight lane kernel (strided
378///   runs), and runs are combined left to right. A dense column major
379///   source therefore reduces exactly like one contiguous slice.
380/// * With a budget above one and a region whose serial time (the `Reduce`
381///   class of `execution::KernelClass`) repays the sections of a tree split, a
382///   full reduction splits the traversal into one deterministic range per
383///   task. Each range runs the same run kernel as the serial path and
384///   the partials are combined in a fixed tree. The result is bitwise
385///   repeatable for a fixed layout and budget, but may differ between
386///   budgets and from the serial result.
387/// * Axis reductions with kept axes compute every output independently, so
388///   the result never depends on the token or its budget. Each output
389///   folds its reduced elements sequentially in caller reduced axis order,
390///   except that a unit stride leading reduced run (after fusing adjacent
391///   reduced axes) of length at least 16 is reduced by the contiguous run
392///   kernel, with runs folded in order. When instead the leading kept axis
393///   has unit stride, adjacent outputs are accumulated as a block from one
394///   contiguous source run per reduced element; each output still folds in
395///   caller reduced axis order.
396#[derive(Clone, Debug)]
397pub struct ErasedReducePlan {
398    dtype: KernelDType,
399    op: ReduceOp,
400    layout: ReduceLayout,
401}
402
403#[derive(Clone, Debug)]
404enum ReduceLayout {
405    Full {
406        dims: crate::inline::InlineVec<usize>,
407        src_strides: crate::inline::InlineVec<isize>,
408        traversal: FullTraversal,
409    },
410    Axes {
411        src_dims: crate::inline::InlineVec<usize>,
412        src_strides: crate::inline::InlineVec<isize>,
413        dest_dims: crate::inline::InlineVec<usize>,
414        dest_strides: crate::inline::InlineVec<isize>,
415        outer_axes: crate::inline::InlineVec<ReduceOuterAxis>,
416        inner_axes: crate::inline::InlineVec<ReduceInnerAxis>,
417        dest_total: usize,
418        reduce_total: usize,
419        /// Set when every source axis is reduced; the plan then runs the
420        /// full-reduction traversal.
421        full: Option<FullTraversal>,
422    },
423}
424
425#[derive(Clone, Copy, Debug, Default)]
426struct ReduceOuterAxis {
427    extent: usize,
428    source_step: isize,
429    source_reset: isize,
430    dest_step: isize,
431    dest_reset: isize,
432}
433#[derive(Clone, Copy, Debug, Default)]
434struct ReduceInnerAxis {
435    extent: usize,
436    source_step: isize,
437    source_reset: isize,
438}
439impl ReduceLayout {
440    fn src_dims(&self) -> &[usize] {
441        match self {
442            Self::Full { dims, .. } => dims,
443            Self::Axes { src_dims, .. } => src_dims,
444        }
445    }
446
447    fn src_strides(&self) -> &[isize] {
448        match self {
449            Self::Full { src_strides, .. } | Self::Axes { src_strides, .. } => src_strides,
450        }
451    }
452
453    fn check_src_layout(&self, src: &ErasedRawStridedRef<'_>) -> Result<()> {
454        if src.dims() != self.src_dims() || src.strides() != self.src_strides() {
455            return Err(StridedError::PlanLayoutMismatch);
456        }
457        Ok(())
458    }
459}
460
461#[derive(Clone, Copy, Debug)]
462struct AxesLayout<'a> {
463    outer_axes: &'a [ReduceOuterAxis],
464    inner_axes: &'a [ReduceInnerAxis],
465    dest_total: usize,
466    reduce_total: usize,
467}
468
469impl ErasedReducePlan {
470    /// Validate and store a full-reduction plan for one dtype and source layout.
471    ///
472    /// # Errors
473    ///
474    /// Returns [`StridedError::UnsupportedDType`] when `op` has no identity
475    /// in `dtype`: [`ReduceOp::SumSquares`] outside `f32`/`f64`,
476    /// [`ReduceOp::Max`] or [`ReduceOp::Min`] for a complex or `bool` dtype,
477    /// and every op for `bool`. Returns
478    /// [`StridedError::StrideLengthMismatch`] when `dims` and `src_strides`
479    /// have different lengths, and [`StridedError::OffsetOverflow`] when the
480    /// element count overflows `usize` or the fused traversal arithmetic
481    /// (extents, steps, and negated resets) does not fit `isize`.
482    pub fn compile(
483        dtype: KernelDType,
484        op: ReduceOp,
485        dims: &[usize],
486        src_strides: &[isize],
487    ) -> Result<Self> {
488        check_reduce_op_dtype(dtype, op)?;
489        if dims.len() != src_strides.len() {
490            return Err(StridedError::StrideLengthMismatch);
491        }
492        checked_total_len(dims)?;
493        let traversal = FullTraversal::compile(dims, src_strides)?;
494        Ok(Self {
495            dtype,
496            op,
497            layout: ReduceLayout::Full {
498                dims: dims.into(),
499                src_strides: src_strides.into(),
500                traversal,
501            },
502        })
503    }
504
505    /// Validate and store an axis-reduction plan for one dtype and fixed source/output layouts.
506    ///
507    /// `axes` names the source axes reduced away. Output dimensions must be the
508    /// remaining source dimensions in source-axis order. When all axes are
509    /// reduced, any output layout with exactly one reachable element is accepted.
510    ///
511    /// # Errors
512    ///
513    /// Returns [`StridedError::UnsupportedDType`] when `op` has no identity
514    /// in `dtype` (see [`Self::compile`]),
515    /// [`StridedError::StrideLengthMismatch`] when a stride list does not
516    /// match its dimension list, [`StridedError::OffsetOverflow`] when an
517    /// element count, a layout span, a reset or a fused extent does not fit
518    /// `usize`/`isize`, [`StridedError::NonInjectiveOutputLayout`] when the
519    /// destination layout cannot be proven injective (aliasing elements, or a
520    /// span the check cannot represent),
521    /// [`StridedError::InvalidAxis`] when `axes` repeats an axis or names one
522    /// outside the source rank, and [`StridedError::ShapeMismatch`] when
523    /// `dest_dims` is not the kept source extents in source-axis order (or,
524    /// when every axis is reduced, does not hold exactly one element).
525    #[allow(clippy::too_many_arguments)]
526    pub fn compile_axes(
527        dtype: KernelDType,
528        op: ReduceOp,
529        src_dims: &[usize],
530        src_strides: &[isize],
531        dest_dims: &[usize],
532        dest_strides: &[isize],
533        axes: &[usize],
534    ) -> Result<Self> {
535        check_reduce_op_dtype(dtype, op)?;
536        if src_dims.len() != src_strides.len() || dest_dims.len() != dest_strides.len() {
537            return Err(StridedError::StrideLengthMismatch);
538        }
539        checked_total_len(src_dims)?;
540        check_reduce_layout_offset_arithmetic(src_dims, src_strides)?;
541        let dest_total = checked_total_len(dest_dims)?;
542        check_reduce_layout_offset_arithmetic(dest_dims, dest_strides)?;
543        if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
544            return Err(StridedError::NonInjectiveOutputLayout);
545        }
546        validate_unique_axes(axes, src_dims.len())?;
547
548        let kept_axes: crate::inline::InlineVec<usize> = (0..src_dims.len())
549            .filter(|axis| !axes.contains(axis))
550            .collect();
551        let expected_dest_dims: crate::inline::InlineVec<usize> =
552            kept_axes.iter().map(|&axis| src_dims[axis]).collect();
553        if expected_dest_dims.is_empty() {
554            if dest_total != 1 {
555                return Err(StridedError::ShapeMismatch(
556                    dest_dims.to_vec(),
557                    expected_dest_dims.to_vec(),
558                ));
559            }
560        } else if dest_dims != expected_dest_dims.as_slice() {
561            return Err(StridedError::ShapeMismatch(
562                dest_dims.to_vec(),
563                expected_dest_dims.to_vec(),
564            ));
565        }
566
567        let reduce_total = axes
568            .iter()
569            .try_fold(1usize, |total, &axis| total.checked_mul(src_dims[axis]))
570            .ok_or(StridedError::OffsetOverflow)?;
571        let outer_axes = compress_reduce_outer_axes(
572            kept_axes
573                .iter()
574                .enumerate()
575                .map(|(dest_axis, &src_axis)| {
576                    let extent = src_dims[src_axis];
577                    Ok(ReduceOuterAxis {
578                        extent,
579                        source_step: src_strides[src_axis],
580                        source_reset: checked_reduce_reset(extent, src_strides[src_axis])?,
581                        dest_step: dest_strides[dest_axis],
582                        dest_reset: checked_reduce_reset(extent, dest_strides[dest_axis])?,
583                    })
584                })
585                .collect::<Result<crate::inline::InlineVec<_>>>()?,
586        )?;
587        let inner_axes = compress_reduce_inner_axes(
588            axes.iter()
589                .map(|&src_axis| {
590                    let extent = src_dims[src_axis];
591                    Ok(ReduceInnerAxis {
592                        extent,
593                        source_step: src_strides[src_axis],
594                        source_reset: checked_reduce_reset(extent, src_strides[src_axis])?,
595                    })
596                })
597                .collect::<Result<crate::inline::InlineVec<_>>>()?,
598        )?;
599        let full = if kept_axes.is_empty() {
600            Some(FullTraversal::compile(src_dims, src_strides)?)
601        } else {
602            None
603        };
604        Ok(Self {
605            dtype,
606            op,
607            layout: ReduceLayout::Axes {
608                src_dims: src_dims.into(),
609                src_strides: src_strides.into(),
610                dest_dims: dest_dims.into(),
611                dest_strides: dest_strides.into(),
612                outer_axes,
613                inner_axes,
614                dest_total,
615                reduce_total,
616                full,
617            },
618        })
619    }
620
621    #[inline]
622    pub fn dtype(&self) -> KernelDType {
623        self.dtype
624    }
625
626    #[inline]
627    pub fn op(&self) -> ReduceOp {
628        self.op
629    }
630
631    /// Execute the reduction into an erased output descriptor.
632    ///
633    /// # Errors
634    ///
635    /// Returns [`StridedError::DTypeMismatch`] when `dest` or `src` carries a
636    /// different dtype than the plan,
637    /// [`StridedError::PlanLayoutMismatch`] when the source layout or the
638    /// axis-reduction destination layout does not match the compiled one,
639    /// [`StridedError::RankMismatch`] when a full reduction gets a
640    /// destination that does not hold exactly one element,
641    /// [`StridedError::OffsetOverflow`] when that destination's extents
642    /// multiply beyond `usize`. All are returned before the first destination
643    /// write.
644    pub fn execute(
645        &self,
646        dest: &mut ErasedRawStridedMut<'_>,
647        src: &ErasedRawStridedRef<'_>,
648        exec: Exec<'_>,
649    ) -> Result<()> {
650        check_dtype(self.dtype, dest.dtype())?;
651        check_dtype(self.dtype, src.dtype())?;
652        self.layout.check_src_layout(src)?;
653        match &self.layout {
654            ReduceLayout::Full { .. } => {
655                let dest_len = checked_total_len(dest.dims())?;
656                if dest_len != 1 {
657                    return Err(StridedError::RankMismatch(dest_len, 1));
658                }
659            }
660            ReduceLayout::Axes {
661                dest_dims,
662                dest_strides,
663                ..
664            } => {
665                if dest.dims() != dest_dims.as_slice() || dest.strides() != dest_strides.as_slice()
666                {
667                    return Err(StridedError::PlanLayoutMismatch);
668                }
669            }
670        }
671
672        let result = match self.dtype {
673            KernelDType::F32 => {
674                let mut writer = reduce_writer::<f32>(dest)?;
675                dispatch_reduce::<f32, _>(self.op, &self.layout, &mut writer, src, exec)
676            }
677            KernelDType::F64 => {
678                let mut writer = reduce_writer::<f64>(dest)?;
679                dispatch_reduce::<f64, _>(self.op, &self.layout, &mut writer, src, exec)
680            }
681            KernelDType::I32 => {
682                let mut writer = reduce_writer::<i32>(dest)?;
683                dispatch_reduce::<i32, _>(self.op, &self.layout, &mut writer, src, exec)
684            }
685            KernelDType::I64 => {
686                let mut writer = reduce_writer::<i64>(dest)?;
687                dispatch_reduce::<i64, _>(self.op, &self.layout, &mut writer, src, exec)
688            }
689            KernelDType::C32 => {
690                let mut writer = reduce_writer::<Complex32>(dest)?;
691                dispatch_reduce::<Complex32, _>(self.op, &self.layout, &mut writer, src, exec)
692            }
693            KernelDType::C64 => {
694                let mut writer = reduce_writer::<Complex64>(dest)?;
695                dispatch_reduce::<Complex64, _>(self.op, &self.layout, &mut writer, src, exec)
696            }
697            _ => Err(StridedError::UnsupportedDType {
698                dtype: self.dtype.label(),
699            }),
700        };
701        result
702    }
703
704    /// On success, every reachable destination slot is fully overwritten;
705    /// unreachable holes are neither read nor initialized. Validation errors
706    /// are returned before any destination write. A panic during execution
707    /// may leave a partially initialized `MaybeUninit` destination, which is
708    /// still safely droppable; no readable value is promised for unwritten
709    /// reachable slots.
710    ///
711    /// # Errors
712    ///
713    /// Returns [`StridedError::DTypeMismatch`] when `dest` or `src` carries a
714    /// different dtype than the plan,
715    /// [`StridedError::OverlappingInputOutput`] when the source allocation
716    /// overlaps the destination, [`StridedError::PlanLayoutMismatch`],
717    /// [`StridedError::RankMismatch`], and [`StridedError::OffsetOverflow`]
718    /// exactly as [`Self::execute`] does. All are returned before the first
719    /// destination write.
720    pub fn execute_uninit(
721        &self,
722        dest: &mut ErasedRawStridedUninitMut<'_>,
723        src: &ErasedRawStridedPtr<'_>,
724        exec: Exec<'_>,
725    ) -> Result<()> {
726        check_dtype(self.dtype, dest.dtype())?;
727        check_dtype(self.dtype, src.dtype())?;
728        validate_uninit_no_overlap(dest, src, 0)?;
729        // SAFETY: the owning erased entry rejected all input/output overlap before conversion.
730        let src = unsafe { src.try_as_ref_after_no_overlap() }?;
731        self.layout.check_src_layout(&src)?;
732        match &self.layout {
733            ReduceLayout::Full { .. } => {
734                let total = checked_total_len(dest.dims())?;
735                if total != 1 {
736                    return Err(StridedError::RankMismatch(total, 1));
737                }
738            }
739            ReduceLayout::Axes {
740                dest_dims,
741                dest_strides,
742                ..
743            } => {
744                if dest.dims() != dest_dims.as_slice() || dest.strides() != dest_strides.as_slice()
745                {
746                    return Err(StridedError::PlanLayoutMismatch);
747                }
748            }
749        }
750        macro_rules! run {
751            ($ty:ty) => {{
752                let mut writer = reduce_uninit_writer::<$ty>(dest)?;
753                dispatch_reduce::<$ty, _>(self.op, &self.layout, &mut writer, &src, exec)
754            }};
755        }
756        match self.dtype {
757            KernelDType::F32 => run!(f32),
758            KernelDType::F64 => run!(f64),
759            KernelDType::I32 => run!(i32),
760            KernelDType::I64 => run!(i64),
761            KernelDType::C32 => run!(Complex32),
762            KernelDType::C64 => run!(Complex64),
763            _ => Err(StridedError::UnsupportedDType {
764                dtype: self.dtype.label(),
765            }),
766        }
767    }
768}
769
770fn reduce_writer<'a, T>(dest: &'a mut ErasedRawStridedMut<'_>) -> Result<RawReduceWriter<'a, T>>
771where
772    T: KernelStorageElement,
773{
774    let offset = dest.offset();
775    let data = dest.data_as_mut::<T>()?;
776    let ptr = data.as_mut_ptr();
777    let extent = data.len();
778    Ok(RawReduceWriter {
779        ptr,
780        extent,
781        offset,
782        _marker: core::marker::PhantomData,
783    })
784}
785
786fn reduce_uninit_writer<'a, T>(
787    dest: &'a mut ErasedRawStridedUninitMut<'_>,
788) -> Result<RawReduceWriter<'a, T>>
789where
790    T: KernelStorageElement,
791{
792    let offset = dest.offset();
793    let data = dest.data_as_uninit_mut::<T>()?;
794    let ptr = data.as_mut_ptr().cast::<T>();
795    let extent = data.len();
796    Ok(RawReduceWriter {
797        ptr,
798        extent,
799        offset,
800        _marker: core::marker::PhantomData,
801    })
802}
803
804fn check_reduce_dtype(dtype: KernelDType) -> Result<()> {
805    match dtype {
806        KernelDType::F32
807        | KernelDType::F64
808        | KernelDType::I32
809        | KernelDType::I64
810        | KernelDType::C32
811        | KernelDType::C64 => Ok(()),
812        _ => Err(StridedError::UnsupportedDType {
813            dtype: dtype.label(),
814        }),
815    }
816}
817
818fn check_reduce_op_dtype(dtype: KernelDType, op: ReduceOp) -> Result<()> {
819    if op == ReduceOp::SumSquares && !matches!(dtype, KernelDType::F32 | KernelDType::F64) {
820        return Err(StridedError::UnsupportedDType {
821            dtype: dtype.label(),
822        });
823    }
824    if matches!(op, ReduceOp::Max | ReduceOp::Min)
825        && !matches!(
826            dtype,
827            KernelDType::F32 | KernelDType::F64 | KernelDType::I32 | KernelDType::I64
828        )
829    {
830        return Err(StridedError::UnsupportedDType {
831            dtype: dtype.label(),
832        });
833    }
834    check_reduce_dtype(dtype)
835}
836
837fn checked_total_len(dims: &[usize]) -> Result<usize> {
838    if dims.is_empty() {
839        return Ok(1);
840    }
841    dims.iter()
842        .try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
843        .ok_or(StridedError::OffsetOverflow)
844}
845
846fn execute_copy<T>(
847    plan: &CopyPlan,
848    dest: &mut ErasedRawStridedMut<'_>,
849    src: &ErasedRawStridedRef<'_>,
850    exec: Exec<'_>,
851) -> Result<()>
852where
853    T: Copy + Send + Sync + KernelStorageElement,
854{
855    let source_data = src.data_as::<T>()?;
856    let dest_dims = dest.dims();
857    let dest_strides = dest.strides();
858    let dest_offset = dest.offset();
859    let dest_data = dest.data_as_mut::<T>()?;
860    // SAFETY: the source (`src`/`input`) is an erased descriptor built only by checked
861    // constructors (`ErasedRawStridedRef::from_slice`/`from_raw_parts`,
862    // strided-view/src/raw.rs:396/:449), which ran `validate_bounds`
863    // (strided-view/src/view.rs:186) on exactly these dims/strides/offset;
864    // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count, so
865    // every reachable offset is inside the buffer it hands to `new_unchecked`.
866    let source = unsafe {
867        RawStridedRef::new_unchecked(source_data, src.dims(), src.strides(), src.offset())
868    };
869    // SAFETY: `dest` is an erased descriptor built only by checked
870    // constructors (`ErasedRawStridedMut::from_slice_mut`/`from_raw_parts`,
871    // strided-view/src/raw.rs:555/:610), which ran `validate_bounds`
872    // (strided-view/src/view.rs:186) on exactly these dims/strides/offset;
873    // `data_as_mut::<T>` (raw.rs:663) re-checks the dtype at that element count,
874    // and the `&mut` borrow keeps the storage unaliased for this call.
875    let mut dest =
876        unsafe { RawStridedMut::new_unchecked(dest_data, dest_dims, dest_strides, dest_offset) };
877    plan.execute(&mut dest, &source, exec)
878}
879
880fn execute_concatenate<T>(
881    plan: &ConcatenatePlan,
882    dest: &mut ErasedRawStridedMut<'_>,
883    inputs: &[ErasedRawStridedRef<'_>],
884    mut exec: Exec<'_>,
885) -> Result<()>
886where
887    T: Copy + Send + Sync + KernelStorageElement,
888{
889    if inputs.len() != plan.input_count() {
890        return Err(StridedError::RankMismatch(inputs.len(), plan.input_count()));
891    }
892    let dest_dims = dest.dims();
893    let dest_strides = dest.strides();
894    let dest_offset = dest.offset();
895    let dest_data = dest.data_as_mut::<T>()?;
896    // SAFETY: `dest` is an erased descriptor built only by checked
897    // constructors (`ErasedRawStridedMut::from_slice_mut`/`from_raw_parts`,
898    // strided-view/src/raw.rs:555/:610), which ran `validate_bounds`
899    // (strided-view/src/view.rs:186) on exactly these dims/strides/offset;
900    // `data_as_mut::<T>` (raw.rs:663) re-checks the dtype at that element count,
901    // and the `&mut` borrow keeps the storage unaliased for this call.
902    let mut dest_ref =
903        unsafe { RawStridedMut::new_unchecked(dest_data, dest_dims, dest_strides, dest_offset) };
904    plan.check_dest_layout(&dest_ref)?;
905
906    for (position, input) in inputs.iter().enumerate() {
907        let input_data = input.data_as::<T>()?;
908        // SAFETY: the source (`src`/`input`) is an erased descriptor built only by checked
909        // constructors (`ErasedRawStridedRef::from_slice`/`from_raw_parts`,
910        // strided-view/src/raw.rs:396/:449), which ran `validate_bounds`
911        // (strided-view/src/view.rs:186) on exactly these dims/strides/offset;
912        // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count, so
913        // every reachable offset is inside the buffer it hands to `new_unchecked`.
914        let input_ref = unsafe {
915            RawStridedRef::new_unchecked(input_data, input.dims(), input.strides(), input.offset())
916        };
917        plan.check_input_layout(position, &input_ref)?;
918        plan.segment_offset(position, dest_offset)?;
919    }
920    if plan.prefers_whole_plan(&exec)
921        && !inputs.is_empty()
922        && inputs.len() <= crate::inline::OPERAND_CAP
923    {
924        // Build the typed descriptors on the stack: `RawStridedRef` is `Copy`,
925        // so this stays allocation-free within the operand bound. The
926        // whole-plan entry then splits the concatenated space and the typed
927        // `try_execute_parallel` reads each segment straight from the plan.
928        let first_data = inputs[0].data_as::<T>()?;
929        // SAFETY: the source (`src`/`input`) is an erased descriptor built only by checked
930        // constructors (`ErasedRawStridedRef::from_slice`/`from_raw_parts`,
931        // strided-view/src/raw.rs:396/:449), which ran `validate_bounds`
932        // (strided-view/src/view.rs:186) on exactly these dims/strides/offset;
933        // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count, so
934        // every reachable offset is inside the buffer it hands to `new_unchecked`.
935        let first = unsafe {
936            RawStridedRef::new_unchecked(
937                first_data,
938                inputs[0].dims(),
939                inputs[0].strides(),
940                inputs[0].offset(),
941            )
942        };
943        let mut input_refs = [first; crate::inline::OPERAND_CAP];
944        for (slot, input) in input_refs.iter_mut().zip(inputs) {
945            let input_data = input.data_as::<T>()?;
946            // SAFETY: the source (`src`/`input`) is an erased descriptor built only by checked
947            // constructors (`ErasedRawStridedRef::from_slice`/`from_raw_parts`,
948            // strided-view/src/raw.rs:396/:449), which ran `validate_bounds`
949            // (strided-view/src/view.rs:186) on exactly these dims/strides/offset;
950            // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count, so
951            // every reachable offset is inside the buffer it hands to `new_unchecked`.
952            *slot = unsafe {
953                RawStridedRef::new_unchecked(
954                    input_data,
955                    input.dims(),
956                    input.strides(),
957                    input.offset(),
958                )
959            };
960        }
961        return plan.execute(&mut dest_ref, &input_refs[..inputs.len()], exec);
962    }
963    for (position, input) in inputs.iter().enumerate() {
964        let input_data = input.data_as::<T>()?;
965        // SAFETY: the source (`src`/`input`) is an erased descriptor built only by checked
966        // constructors (`ErasedRawStridedRef::from_slice`/`from_raw_parts`,
967        // strided-view/src/raw.rs:396/:449), which ran `validate_bounds`
968        // (strided-view/src/view.rs:186) on exactly these dims/strides/offset;
969        // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count, so
970        // every reachable offset is inside the buffer it hands to `new_unchecked`.
971        let input_ref = unsafe {
972            RawStridedRef::new_unchecked(input_data, input.dims(), input.strides(), input.offset())
973        };
974        plan.execute_segment(position, &mut dest_ref, &input_ref, exec.reborrow())?;
975    }
976    Ok(())
977}
978
979fn execute_concatenate_uninit<T>(
980    plan: &ConcatenatePlan,
981    dest: &mut ErasedRawStridedUninitMut<'_>,
982    inputs: &[ErasedRawStridedPtr<'_>],
983    mut exec: Exec<'_>,
984) -> Result<()>
985where
986    T: Copy + Send + Sync + KernelStorageElement,
987{
988    let dest_dims = dest.dims();
989    let dest_strides = dest.strides();
990    let dest_offset = dest.offset();
991    let dest_data = dest.data_as_uninit_mut::<T>()?;
992    // SAFETY: `dest` is an erased descriptor built only by checked
993    // constructors (`ErasedRawStridedUninitMut::from_uninit_slice`/
994    // `from_raw_parts`, strided-view/src/raw.rs:745/:801), which ran
995    // `validate_bounds` (strided-view/src/view.rs:186) on exactly these
996    // dims/strides/offset; `data_as_uninit_mut::<T>` (raw.rs:828) re-checks the
997    // dtype at that element count, writes go through `MaybeUninit`, and the
998    // `&mut` borrow keeps the storage unaliased.
999    let mut dest_ref =
1000        unsafe { RawStridedMut::new_unchecked(dest_data, dest_dims, dest_strides, dest_offset) };
1001    plan.check_dest_layout(&dest_ref)?;
1002
1003    for (position, input) in inputs.iter().enumerate() {
1004        // SAFETY: input/output overlap was rejected before forming references.
1005        let input = unsafe { input.try_as_ref_after_no_overlap() }?;
1006        let input_data = input.data_as::<T>()?;
1007        // SAFETY: this input reached `RawStridedRef` through
1008        // `ErasedRawStridedPtr::try_as_ref_after_no_overlap` (raw.rs:288), which
1009        // re-ran the erased reference's raw constructor (`from_raw_parts`,
1010        // strided-view/src/raw.rs:449) → `validate_bounds`
1011        // (strided-view/src/view.rs:186) on exactly these dims/strides/offset, and
1012        // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count.
1013        let input_ref = unsafe {
1014            RawStridedRef::new_unchecked(input_data, input.dims(), input.strides(), input.offset())
1015        };
1016        plan.check_input_layout(position, &input_ref)?;
1017        plan.segment_offset(position, dest_offset)?;
1018    }
1019    if plan.prefers_whole_plan(&exec)
1020        && !inputs.is_empty()
1021        && inputs.len() <= crate::inline::OPERAND_CAP
1022    {
1023        // SAFETY: input/output overlap was rejected before forming references.
1024        let first_erased = unsafe { inputs[0].try_as_ref_after_no_overlap() }?;
1025        let mut erased_refs = [first_erased; crate::inline::OPERAND_CAP];
1026        for (slot, input) in erased_refs.iter_mut().zip(inputs) {
1027            // SAFETY: input/output overlap was rejected before forming references.
1028            *slot = unsafe { input.try_as_ref_after_no_overlap() }?;
1029        }
1030        let first_data = erased_refs[0].data_as::<T>()?;
1031        // SAFETY: this input reached `RawStridedRef` through
1032        // `ErasedRawStridedPtr::try_as_ref_after_no_overlap` (raw.rs:288), which
1033        // re-ran the erased reference's raw constructor (`from_raw_parts`,
1034        // strided-view/src/raw.rs:449) → `validate_bounds`
1035        // (strided-view/src/view.rs:186) on exactly these dims/strides/offset, and
1036        // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count.
1037        let first = unsafe {
1038            RawStridedRef::new_unchecked(
1039                first_data,
1040                erased_refs[0].dims(),
1041                erased_refs[0].strides(),
1042                erased_refs[0].offset(),
1043            )
1044        };
1045        let mut input_refs = [first; crate::inline::OPERAND_CAP];
1046        for (slot, erased) in input_refs.iter_mut().zip(&erased_refs) {
1047            let input_data = erased.data_as::<T>()?;
1048            // SAFETY: this input reached `RawStridedRef` through
1049            // `ErasedRawStridedPtr::try_as_ref_after_no_overlap` (raw.rs:288), which
1050            // re-ran the erased reference's raw constructor (`from_raw_parts`,
1051            // strided-view/src/raw.rs:449) → `validate_bounds`
1052            // (strided-view/src/view.rs:186) on exactly these dims/strides/offset, and
1053            // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count.
1054            *slot = unsafe {
1055                RawStridedRef::new_unchecked(
1056                    input_data,
1057                    erased.dims(),
1058                    erased.strides(),
1059                    erased.offset(),
1060                )
1061            };
1062        }
1063        return plan.execute_uninit(&mut dest_ref, &input_refs[..inputs.len()], exec);
1064    }
1065    for (position, input) in inputs.iter().enumerate() {
1066        // SAFETY: input/output overlap was rejected before forming references.
1067        let input = unsafe { input.try_as_ref_after_no_overlap() }?;
1068        let input_data = input.data_as::<T>()?;
1069        // SAFETY: this input reached `RawStridedRef` through
1070        // `ErasedRawStridedPtr::try_as_ref_after_no_overlap` (raw.rs:288), which
1071        // re-ran the erased reference's raw constructor (`from_raw_parts`,
1072        // strided-view/src/raw.rs:449) → `validate_bounds`
1073        // (strided-view/src/view.rs:186) on exactly these dims/strides/offset, and
1074        // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count.
1075        let input_ref = unsafe {
1076            RawStridedRef::new_unchecked(input_data, input.dims(), input.strides(), input.offset())
1077        };
1078        plan.execute_segment_uninit(position, &mut dest_ref, &input_ref, exec.reborrow())?;
1079    }
1080    Ok(())
1081}
1082
1083/// Runtime unary operation applied to the source of an [`ErasedUpdatePlan`].
1084///
1085/// The real dtypes have only [`Self::Identity`]; the complex dtypes also have
1086/// [`Self::Conj`], matching the `ElementOp` choices a beta accumulator uses.
1087#[non_exhaustive]
1088#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1089pub enum UpdateOp {
1090    /// `op(x) = x`.
1091    Identity,
1092    /// `op(x) = conj(x)`.
1093    Conj,
1094}
1095
1096/// Dtype-erased wrapper around [`UpdatePlan`].
1097///
1098/// The layout traversal is compiled once and stored without a scalar type;
1099/// each [`execute`](Self::execute) names the concrete scalar type, resolves the
1100/// runtime element op once per call, and then replays monomorphized loops.
1101#[derive(Clone, Debug)]
1102pub struct ErasedUpdatePlan {
1103    dtype: KernelDType,
1104    plan: UpdatePlan,
1105}
1106
1107impl ErasedUpdatePlan {
1108    /// Compile an update plan for one dtype and layout pair.
1109    ///
1110    /// # Errors
1111    ///
1112    /// Returns [`StridedError::StrideLengthMismatch`] when `dims`,
1113    /// `dst_strides`, and `src_strides` do not all have the same length,
1114    /// [`StridedError::OffsetOverflow`] when the element count does not fit
1115    /// `usize`, and [`StridedError::NonInjectiveOutputLayout`] when the
1116    /// destination layout cannot be proven injective (aliasing elements, or a
1117    /// span the check cannot represent).
1118    pub fn compile(
1119        dtype: KernelDType,
1120        dims: &[usize],
1121        dst_strides: &[isize],
1122        src_strides: &[isize],
1123    ) -> Result<Self> {
1124        check_static_indexing_dtype(dtype)?;
1125        Ok(Self {
1126            dtype,
1127            plan: UpdatePlan::compile(dims, dst_strides, src_strides)?,
1128        })
1129    }
1130
1131    #[inline]
1132    pub fn dtype(&self) -> KernelDType {
1133        self.dtype
1134    }
1135
1136    /// The compiled typed traversal.
1137    #[inline]
1138    pub fn plan(&self) -> &UpdatePlan {
1139        &self.plan
1140    }
1141
1142    /// `dest = alpha * op(src) + beta * dest` into an erased destination.
1143    ///
1144    /// `alpha`, `beta`, and `op` are resolved once per call; the layout check
1145    /// and replay are the same allocation-free [`UpdatePlan`] path.
1146    ///
1147    /// # Errors
1148    ///
1149    /// Returns [`StridedError::DTypeMismatch`] when `dest`, `src`, or the
1150    /// scalar type `T` carries a different dtype than the plan, and
1151    /// [`StridedError::PlanLayoutMismatch`] when a view does not carry the
1152    /// compiled extents and strides. Both are returned before any destination
1153    /// write.
1154    ///
1155    /// # Examples
1156    ///
1157    /// ```
1158    /// use strided_basic::{
1159    ///     ErasedRawStridedMut, ErasedRawStridedRef, ErasedUpdatePlan, Exec, KernelDType,
1160    ///     UpdateOp,
1161    /// };
1162    ///
1163    /// let plan = ErasedUpdatePlan::compile(KernelDType::F64, &[2], &[1], &[1]).unwrap();
1164    /// let src_data = [1.0_f64, 2.0];
1165    /// let mut dst_data = [10.0_f64, 20.0];
1166    /// let src = ErasedRawStridedRef::from_slice(&src_data, &[2], &[1], 0).unwrap();
1167    /// let mut dst = ErasedRawStridedMut::from_slice_mut(&mut dst_data, &[2], &[1], 0).unwrap();
1168    /// // dst = 2 * src + 3 * dst
1169    /// plan.execute(&mut dst, &src, 2.0, 3.0, UpdateOp::Identity, Exec::serial())
1170    ///     .unwrap();
1171    /// drop(dst);
1172    /// assert_eq!(dst_data, [32.0, 64.0]);
1173    /// ```
1174    pub fn execute<T>(
1175        &self,
1176        dest: &mut ErasedRawStridedMut<'_>,
1177        src: &ErasedRawStridedRef<'_>,
1178        alpha: T,
1179        beta: T,
1180        op: UpdateOp,
1181        exec: Exec<'_>,
1182    ) -> Result<()>
1183    where
1184        T: Copy
1185            + Send
1186            + Sync
1187            + KernelStorageElement
1188            + core::ops::Add<Output = T>
1189            + core::ops::Mul<Output = T>
1190            + Zero
1191            + One
1192            + PartialEq
1193            + ElementOpApply,
1194    {
1195        check_dtype(self.dtype, dest.dtype())?;
1196        check_dtype(self.dtype, src.dtype())?;
1197        let source_data = src.data_as::<T>()?;
1198        let dest_dims = dest.dims();
1199        let dest_strides = dest.strides();
1200        let dest_offset = dest.offset();
1201        let dest_data = dest.data_as_mut::<T>()?;
1202        // SAFETY: the source (`src`/`input`) is an erased descriptor built only by checked
1203        // constructors (`ErasedRawStridedRef::from_slice`/`from_raw_parts`,
1204        // strided-view/src/raw.rs:396/:449), which ran `validate_bounds`
1205        // (strided-view/src/view.rs:186) on exactly these dims/strides/offset;
1206        // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count, so
1207        // every reachable offset is inside the buffer it hands to `new_unchecked`.
1208        let source = unsafe {
1209            RawStridedRef::new_unchecked(source_data, src.dims(), src.strides(), src.offset())
1210        };
1211        // SAFETY: `dest` is an erased descriptor built only by checked
1212        // constructors (`ErasedRawStridedMut::from_slice_mut`/`from_raw_parts`,
1213        // strided-view/src/raw.rs:555/:610), which ran `validate_bounds`
1214        // (strided-view/src/view.rs:186) on exactly these dims/strides/offset;
1215        // `data_as_mut::<T>` (raw.rs:663) re-checks the dtype at that element count,
1216        // and the `&mut` borrow keeps the storage unaliased for this call.
1217        let mut dest_ref = unsafe {
1218            RawStridedMut::new_unchecked(dest_data, dest_dims, dest_strides, dest_offset)
1219        };
1220        match op {
1221            UpdateOp::Identity => {
1222                self.plan
1223                    .execute(&mut dest_ref, &source, alpha, beta, |x| x, exec)
1224            }
1225            UpdateOp::Conj => {
1226                self.plan
1227                    .execute(&mut dest_ref, &source, alpha, beta, |x| x.conj(), exec)
1228            }
1229        }
1230    }
1231
1232    /// `dest = alpha * op(src)` into an uninitialized erased destination.
1233    ///
1234    /// This is [`execute`](Self::execute) with `beta = 0`: the destination is
1235    /// never read, so a NaN-filled or uninitialized output cannot contaminate
1236    /// the result. On success every reachable destination element is written;
1237    /// validation errors are returned before any write. A panic during
1238    /// execution may leave a partially initialized `MaybeUninit` destination,
1239    /// which is still safely droppable; no readable value is promised for
1240    /// unwritten reachable slots.
1241    ///
1242    /// # Examples
1243    ///
1244    /// ```
1245    /// use core::mem::MaybeUninit;
1246    /// use strided_basic::{
1247    ///     ErasedRawStridedPtr, ErasedRawStridedRef, ErasedRawStridedUninitMut, ErasedUpdatePlan,
1248    ///     Exec, KernelDType, UpdateOp,
1249    /// };
1250    ///
1251    /// let plan = ErasedUpdatePlan::compile(KernelDType::F64, &[2], &[1], &[1]).unwrap();
1252    /// let src_data = [1.0_f64, 2.0];
1253    /// let mut dst_data = [MaybeUninit::<f64>::uninit(); 2];
1254    /// let src = ErasedRawStridedRef::from_slice(&src_data, &[2], &[1], 0).unwrap();
1255    /// let src_ptr = ErasedRawStridedPtr::from_ref(&src);
1256    /// let mut dst =
1257    ///     ErasedRawStridedUninitMut::from_uninit_slice(&mut dst_data, &[2], &[1], 0).unwrap();
1258    /// // dst = 2 * src
1259    /// plan.execute_uninit(&mut dst, &src_ptr, 2.0, UpdateOp::Identity, Exec::serial())
1260    ///     .unwrap();
1261    /// let values: Vec<f64> = dst_data.iter().map(|v| unsafe { v.assume_init() }).collect();
1262    /// assert_eq!(values, [2.0, 4.0]);
1263    /// ```
1264    ///
1265    /// # Errors
1266    ///
1267    /// Returns `DTypeMismatch` or `PlanLayoutMismatch` when a descriptor does
1268    /// not match the plan, and `OverlappingInputOutput` when the source
1269    /// overlaps the destination allocation, all before any destination write.
1270    pub fn execute_uninit<T>(
1271        &self,
1272        dest: &mut ErasedRawStridedUninitMut<'_>,
1273        src: &ErasedRawStridedPtr<'_>,
1274        alpha: T,
1275        op: UpdateOp,
1276        exec: Exec<'_>,
1277    ) -> Result<()>
1278    where
1279        T: Copy
1280            + Send
1281            + Sync
1282            + KernelStorageElement
1283            + core::ops::Mul<Output = T>
1284            + One
1285            + PartialEq
1286            + ElementOpApply,
1287    {
1288        check_dtype(self.dtype, dest.dtype())?;
1289        check_dtype(self.dtype, src.dtype())?;
1290        validate_uninit_no_overlap(dest, src, 0)?;
1291        // SAFETY: the owning erased entry rejected all input/output overlap before conversion.
1292        let src = unsafe { src.try_as_ref_after_no_overlap() }?;
1293        let source_data = src.data_as::<T>()?;
1294        let dest_dims = dest.dims();
1295        let dest_strides = dest.strides();
1296        let dest_offset = dest.offset();
1297        let dest_data = dest.data_as_uninit_mut::<T>()?;
1298        // SAFETY: this input reached `RawStridedRef` through
1299        // `ErasedRawStridedPtr::try_as_ref_after_no_overlap` (raw.rs:288), which
1300        // re-ran the erased reference's raw constructor (`from_raw_parts`,
1301        // strided-view/src/raw.rs:449) → `validate_bounds`
1302        // (strided-view/src/view.rs:186) on exactly these dims/strides/offset, and
1303        // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count.
1304        let source = unsafe {
1305            RawStridedRef::new_unchecked(source_data, src.dims(), src.strides(), src.offset())
1306        };
1307        // SAFETY: `dest` is an erased descriptor built only by checked
1308        // constructors (`ErasedRawStridedUninitMut::from_uninit_slice`/
1309        // `from_raw_parts`, strided-view/src/raw.rs:745/:801), which ran
1310        // `validate_bounds` (strided-view/src/view.rs:186) on exactly these
1311        // dims/strides/offset; `data_as_uninit_mut::<T>` (raw.rs:828) re-checks the
1312        // dtype at that element count, writes go through `MaybeUninit`, and the
1313        // `&mut` borrow keeps the storage unaliased.
1314        let mut dest_ref = unsafe {
1315            RawStridedMut::new_unchecked(dest_data, dest_dims, dest_strides, dest_offset)
1316        };
1317        match op {
1318            UpdateOp::Identity => {
1319                self.plan
1320                    .execute_uninit(&mut dest_ref, &source, alpha, |x| x, exec)
1321            }
1322            UpdateOp::Conj => {
1323                self.plan
1324                    .execute_uninit(&mut dest_ref, &source, alpha, |x| x.conj(), exec)
1325            }
1326        }
1327    }
1328}
1329
1330fn execute_reduce_full<T, W, K>(
1331    dest: &mut W,
1332    src: &ErasedRawStridedRef<'_>,
1333    traversal: &FullTraversal,
1334    exec: Exec<'_>,
1335) -> Result<bool>
1336where
1337    T: ErasedReduceScalar,
1338    W: ReduceWriter<T>,
1339    K: ReduceKernel<T>,
1340{
1341    let source = src.data_as::<T>()?;
1342    let total = traversal.total();
1343    if total == 0 {
1344        // SAFETY: validated rank-zero destination layout proves the offset.
1345        unsafe { dest.write_at(dest.offset(), K::finish(K::identity())) };
1346        return Ok(false);
1347    }
1348    let acc = reduce_full_split::<T, K>(source, src.offset(), traversal, exec)?;
1349
1350    if K::needs_ordered_fallback(&acc) {
1351        // The caller re-runs this layout with `K::Fallback`; the destination is
1352        // left untouched so nothing observable is written twice.
1353        return Ok(true);
1354    }
1355    // SAFETY: validated rank-zero destination layout proves the offset.
1356    unsafe { dest.write_at(dest.offset(), K::finish(acc)) };
1357    Ok(false)
1358}
1359
1360/// Full reduction of `source` over the traversal, split across the budget of
1361/// `exec` above the repository threshold.
1362///
1363/// Splitting reassociates one output element's factors across ranges, so only
1364/// a kernel that may be reassociated takes it (tenferro-rs#2150). A stable
1365/// accumulator that detects an unrepresentable factor sets the fallback flag,
1366/// and the caller then recomputes the whole output in source order.
1367fn reduce_full_split<T, K>(
1368    source: &[T],
1369    source_base: isize,
1370    traversal: &FullTraversal,
1371    exec: Exec<'_>,
1372) -> Result<K::Acc>
1373where
1374    T: ErasedReduceScalar,
1375    K: ReduceKernel<T>,
1376{
1377    let total = traversal.total();
1378    // INVARIANT: (1) FullTraversal::compile checked every step/reset of the
1379    // source layout; (2) the raw source descriptor validated every reachable
1380    // offset; (3) execute checked exact plan-layout equality.
1381    if !K::reassociable() {
1382        // SAFETY: the three-link invariant proves every traversal offset is
1383        // readable.
1384        return unsafe {
1385            reduce_full_range::<T, K>(source.as_ptr(), source_base, traversal, 0..total)
1386        };
1387    }
1388    let source_ptr = crate::threading::SendPtr(source.as_ptr() as *mut T);
1389    crate::threading::parallel_map_reduce(
1390        0..total,
1391        crate::cost::for_len_tree(exec, KernelClass::Reduce, total),
1392        &|range| {
1393            // SAFETY: same three-link invariant as above; each range is
1394            // non-empty.
1395            unsafe {
1396                reduce_full_range::<T, K>(source_ptr.as_const(), source_base, traversal, range)
1397            }
1398        },
1399        &|left, right| Ok(K::combine(left?, right?)),
1400    )
1401}
1402
1403fn dispatch_reduce<T, W>(
1404    op: ReduceOp,
1405    layout: &ReduceLayout,
1406    dest: &mut W,
1407    src: &ErasedRawStridedRef<'_>,
1408    exec: Exec<'_>,
1409) -> Result<()>
1410where
1411    T: ErasedReduceScalar,
1412    W: ReduceWriter<T>,
1413{
1414    // The op is matched once per execution; every loop below is generic over
1415    // the selected kernel type.
1416    match op {
1417        ReduceOp::Sum => dispatch_reduce_kernel::<T, W, SumKernel>(layout, dest, src, exec),
1418        ReduceOp::Product => {
1419            dispatch_reduce_kernel::<T, W, ReassociatedProductKernel>(layout, dest, src, exec)
1420        }
1421        ReduceOp::StableProduct => {
1422            dispatch_reduce_kernel::<T, W, StableProductKernel>(layout, dest, src, exec)
1423        }
1424        ReduceOp::SumSquares => {
1425            dispatch_reduce_kernel::<T, W, SumSquaresKernel>(layout, dest, src, exec)
1426        }
1427        ReduceOp::Max => dispatch_reduce_kernel::<T, W, MaxKernel>(layout, dest, src, exec),
1428        ReduceOp::Min => dispatch_reduce_kernel::<T, W, MinKernel>(layout, dest, src, exec),
1429    }
1430}
1431
1432fn dispatch_reduce_kernel<T, W, K>(
1433    layout: &ReduceLayout,
1434    dest: &mut W,
1435    src: &ErasedRawStridedRef<'_>,
1436    mut exec: Exec<'_>,
1437) -> Result<()>
1438where
1439    T: ErasedReduceScalar,
1440    W: ReduceWriter<T>,
1441    K: ReduceKernel<T>,
1442{
1443    let fallback = match layout {
1444        ReduceLayout::Full { traversal, .. } => {
1445            execute_reduce_full::<T, W, K>(dest, src, traversal, exec.reborrow())?
1446        }
1447        ReduceLayout::Axes {
1448            outer_axes,
1449            inner_axes,
1450            dest_total,
1451            reduce_total,
1452            full,
1453            ..
1454        } => {
1455            let axes = AxesLayout {
1456                outer_axes,
1457                inner_axes,
1458                dest_total: *dest_total,
1459                reduce_total: *reduce_total,
1460            };
1461            match full {
1462                Some(traversal) => {
1463                    execute_reduce_full::<T, W, K>(dest, src, traversal, exec.reborrow())?
1464                }
1465                None => {
1466                    // An axis reduction falls back per output inside
1467                    // `reduce_axes_range`; it never asks for a layout-wide
1468                    // recompute.
1469                    execute_reduce_axes::<T, W, K>(dest, src, axes, exec.reborrow())?;
1470                    false
1471                }
1472            }
1473        }
1474    };
1475    if fallback {
1476        // Only a full reduction (one output) requests the layout-wide
1477        // recompute; `K::Fallback` must not itself request a fallback, so this
1478        // recurses at most once. Scalar kernels use `Fallback = Self` and never
1479        // set the flag, so the branch is unreachable for them.
1480        return dispatch_reduce_kernel::<T, W, K::Fallback>(layout, dest, src, exec);
1481    }
1482    Ok(())
1483}
1484
1485fn execute_reduce_axes<T, W, K>(
1486    dest: &mut W,
1487    src: &ErasedRawStridedRef<'_>,
1488    layout: AxesLayout<'_>,
1489    exec: Exec<'_>,
1490) -> Result<()>
1491where
1492    T: ErasedReduceScalar,
1493    W: ReduceWriter<T>,
1494    K: ReduceKernel<T>,
1495{
1496    if layout.dest_total == 0 {
1497        return Ok(());
1498    }
1499
1500    if layout.reduce_total == 0 {
1501        execute_reduce_axes_identity::<T, W, K>(dest, layout, exec)
1502    } else {
1503        execute_reduce_axes_split::<T, W, K>(dest, src, layout, exec)
1504    }
1505}
1506
1507fn execute_reduce_axes_split<T, W, K>(
1508    dest: &mut W,
1509    src: &ErasedRawStridedRef<'_>,
1510    layout: AxesLayout<'_>,
1511    exec: Exec<'_>,
1512) -> Result<()>
1513where
1514    T: ErasedReduceScalar,
1515    W: ReduceWriter<T>,
1516    K: ReduceKernel<T>,
1517{
1518    let source_data = src.data_as::<T>()?;
1519    let source_base = src.offset();
1520    let dest_base = dest.offset();
1521    // SAFETY: the validated reduction writer owns the destination allocation.
1522    let dest_ptr = unsafe { dest.ptr() };
1523    // The threshold counts source elements read (outputs times reduced
1524    // elements), as documented in docs/design/erased-execution-policy.md,
1525    // so a few thousand outputs with long reductions still split. Ranges
1526    // partition the independent outputs; with the output block kernel this
1527    // splits along the contiguous kept axis.
1528    let work = layout.dest_total.saturating_mul(layout.reduce_total);
1529    let exec = crate::cost::for_len_tree(exec, KernelClass::Reduce, work).limit(
1530        core::num::NonZeroUsize::new(layout.dest_total).unwrap_or(core::num::NonZeroUsize::MIN),
1531    );
1532    if !exec.is_serial() {
1533        let dest_ptr = crate::threading::SendPtr(dest_ptr);
1534        let source_ptr = crate::threading::SendPtr(source_data.as_ptr() as *mut T);
1535        return crate::threading::parallel_map_reduce(
1536            0..layout.dest_total,
1537            exec,
1538            &|range| {
1539                let parts = AxesRange {
1540                    source: source_ptr.as_const(),
1541                    source_base,
1542                    dest: dest_ptr.as_ptr(),
1543                    dest_base,
1544                    outer_axes: layout.outer_axes,
1545                    inner_axes: layout.inner_axes,
1546                    reduce_total: layout.reduce_total,
1547                };
1548                // SAFETY: see `execute_reduce_axes_split` serial call.
1549                unsafe { reduce_axes_range::<T, K>(parts, range) }
1550            },
1551            &|left, right| left.and(right),
1552        );
1553    }
1554
1555    let parts = AxesRange {
1556        source: source_data.as_ptr(),
1557        source_base,
1558        dest: dest_ptr,
1559        dest_base,
1560        outer_axes: layout.outer_axes,
1561        inner_axes: layout.inner_axes,
1562        reduce_total: layout.reduce_total,
1563    };
1564    // INVARIANT: (1) compile_axes checked signed source/destination spans and
1565    // every cursor step/reset; (2) raw input and output descriptors validated
1566    // every reachable offset; (3) execute checked exact plan-layout equality
1567    // before dispatch. Output ranges are disjoint, and the initialized entry
1568    // holds distinct borrows while the uninit entry rejected overlap.
1569    // SAFETY: the three-link invariant above; `reduce_total` is nonzero.
1570    unsafe { reduce_axes_range::<T, K>(parts, 0..layout.dest_total) }
1571}
1572
1573fn execute_reduce_axes_identity_serial<T, W, K>(dest: &mut W, layout: AxesLayout<'_>) -> Result<()>
1574where
1575    T: ErasedReduceScalar,
1576    W: ReduceWriter<T>,
1577    K: ReduceKernel<T>,
1578{
1579    let mut outer = ReduceOuterCursor::decode(0, 0, dest.offset(), layout.outer_axes)?;
1580    for output in 0..layout.dest_total {
1581        // INVARIANT: (1) compile_axes checked the destination span and every
1582        // destination step/reset, including -(extent-1)*stride; (2) the raw
1583        // destination descriptor validated every reachable offset; (3) execute
1584        // checked exact plan-layout equality before dispatch.
1585        // SAFETY: the three-link layout invariant proves this destination
1586        // cursor offset is in bounds; the source pointer is intentionally never
1587        // formed for an empty reduction domain.
1588        unsafe { dest.write_at(outer.dest_offset, K::finish(K::identity())) };
1589        if output + 1 < layout.dest_total {
1590            outer.advance();
1591        }
1592    }
1593    Ok(())
1594}
1595fn execute_reduce_axes_identity<T, W, K>(
1596    dest: &mut W,
1597    layout: AxesLayout<'_>,
1598    exec: Exec<'_>,
1599) -> Result<()>
1600where
1601    T: ErasedReduceScalar,
1602    W: ReduceWriter<T>,
1603    K: ReduceKernel<T>,
1604{
1605    let exec = crate::cost::for_len_tree(exec, KernelClass::Reduce, layout.dest_total);
1606    if !exec.is_serial() {
1607        return execute_reduce_axes_identity_parallel::<T, W, K>(dest, layout, exec);
1608    }
1609    execute_reduce_axes_identity_serial::<T, W, K>(dest, layout)
1610}
1611
1612fn execute_reduce_axes_identity_parallel<T, W, K>(
1613    dest: &mut W,
1614    layout: AxesLayout<'_>,
1615    exec: Exec<'_>,
1616) -> Result<()>
1617where
1618    T: ErasedReduceScalar,
1619    W: ReduceWriter<T>,
1620    K: ReduceKernel<T>,
1621{
1622    // SAFETY: the validated reduction writer owns the destination allocation.
1623    let dest_ptr = crate::threading::SendPtr(unsafe { dest.ptr() });
1624    let dest_offset_base = dest.offset();
1625    crate::threading::parallel_map_reduce(
1626        0..layout.dest_total,
1627        exec,
1628        &|range| {
1629            let range_end = range.end;
1630            let mut outer =
1631                ReduceOuterCursor::decode(range.start, 0, dest_offset_base, layout.outer_axes)?;
1632            let dest_ptr = dest_ptr.as_ptr();
1633            for output in range {
1634                // INVARIANT: (1) compile_axes checked the destination span and
1635                // every destination step/reset, including
1636                // -(extent-1)*stride; (2) the raw destination descriptor
1637                // validated every reachable pointer offset; (3) execute checked
1638                // exact plan-layout equality before dispatch.
1639                // SAFETY: the three-link layout invariant proves this
1640                // destination offset is in bounds; no source pointer is formed.
1641                unsafe {
1642                    dest_ptr
1643                        .offset(outer.dest_offset)
1644                        .write(K::finish(K::identity()))
1645                };
1646                if output + 1 < range_end {
1647                    outer.advance();
1648                }
1649            }
1650            Ok(())
1651        },
1652        &|left, right| left.and(right),
1653    )
1654}
1655
1656trait ErasedReduceScalar:
1657    KernelStorageElement
1658    + Copy
1659    + One
1660    + Zero
1661    + Send
1662    + Sync
1663    + crate::simd::MaybeSimdOps
1664    + crate::simd::MaybeSimdProduct
1665    + crate::simd::MaybeSimdSumSquares
1666    + crate::simd::MaybeSimdBlockFold
1667    + StableProductScalar
1668{
1669    fn reduce_sum(lhs: Self, rhs: Self) -> Self;
1670    fn reduce_product(lhs: Self, rhs: Self) -> Self;
1671    /// Identity of [`ReduceOp::Max`]; unreachable for dtypes the plan rejects.
1672    fn max_identity() -> Self;
1673    /// Identity of [`ReduceOp::Min`]; unreachable for dtypes the plan rejects.
1674    fn min_identity() -> Self;
1675    fn reduce_max(lhs: Self, rhs: Self) -> Self;
1676    fn reduce_min(lhs: Self, rhs: Self) -> Self;
1677}
1678
1679macro_rules! impl_float_erased_reduce_scalar {
1680    ($($ty:ty),* $(,)?) => {
1681        $(
1682            impl ErasedReduceScalar for $ty {
1683                #[inline(always)]
1684                fn reduce_sum(lhs: Self, rhs: Self) -> Self {
1685                    lhs + rhs
1686                }
1687
1688                #[inline(always)]
1689                fn reduce_product(lhs: Self, rhs: Self) -> Self {
1690                    lhs * rhs
1691                }
1692
1693                #[inline(always)]
1694                fn max_identity() -> Self {
1695                    <$ty>::NEG_INFINITY
1696                }
1697
1698                #[inline(always)]
1699                fn min_identity() -> Self {
1700                    <$ty>::INFINITY
1701                }
1702
1703                #[inline(always)]
1704                fn reduce_max(lhs: Self, rhs: Self) -> Self {
1705                    // Select form: both sides are evaluated and the NaN test
1706                    // picks the result, so lane loops lower to compare and
1707                    // blend instead of a data dependent branch.
1708                    // A NaN `lhs` is kept by the second test and a NaN
1709                    // `rhs` fails the comparison, so NaN propagates from
1710                    // either side. Equal values (including +0.0 and -0.0)
1711                    // return `rhs`.
1712                    if (lhs > rhs) | lhs.is_nan() {
1713                        lhs
1714                    } else {
1715                        rhs
1716                    }
1717                }
1718
1719                #[inline(always)]
1720                fn reduce_min(lhs: Self, rhs: Self) -> Self {
1721                    // Select form: both sides are evaluated and the NaN test
1722                    // picks the result, so lane loops lower to compare and
1723                    // blend instead of a data dependent branch.
1724                    // A NaN `lhs` is kept by the second test and a NaN
1725                    // `rhs` fails the comparison, so NaN propagates from
1726                    // either side. Equal values (including +0.0 and -0.0)
1727                    // return `rhs`.
1728                    if (lhs < rhs) | lhs.is_nan() {
1729                        lhs
1730                    } else {
1731                        rhs
1732                    }
1733                }
1734            }
1735        )*
1736    };
1737}
1738
1739macro_rules! impl_complex_erased_reduce_scalar {
1740    ($($ty:ty),* $(,)?) => {
1741        $(
1742            impl ErasedReduceScalar for $ty {
1743                #[inline(always)]
1744                fn reduce_sum(lhs: Self, rhs: Self) -> Self {
1745                    lhs + rhs
1746                }
1747
1748                #[inline(always)]
1749                fn reduce_product(lhs: Self, rhs: Self) -> Self {
1750                    lhs * rhs
1751                }
1752
1753                fn max_identity() -> Self {
1754                    // INVARIANT: check_reduce_op_dtype rejects complex Max at compile time.
1755                    unreachable!("complex max reduction is rejected at plan compile")
1756                }
1757
1758                fn min_identity() -> Self {
1759                    // INVARIANT: check_reduce_op_dtype rejects complex Min at compile time.
1760                    unreachable!("complex min reduction is rejected at plan compile")
1761                }
1762
1763                fn reduce_max(_lhs: Self, _rhs: Self) -> Self {
1764                    // INVARIANT: check_reduce_op_dtype rejects complex Max at compile time.
1765                    unreachable!("complex max reduction is rejected at plan compile")
1766                }
1767
1768                fn reduce_min(_lhs: Self, _rhs: Self) -> Self {
1769                    // INVARIANT: check_reduce_op_dtype rejects complex Min at compile time.
1770                    unreachable!("complex min reduction is rejected at plan compile")
1771                }
1772            }
1773        )*
1774    };
1775}
1776
1777macro_rules! impl_wrapping_erased_reduce_scalar {
1778    ($($ty:ty),* $(,)?) => {
1779        $(
1780            impl ErasedReduceScalar for $ty {
1781                #[inline(always)]
1782                fn reduce_sum(lhs: Self, rhs: Self) -> Self {
1783                    lhs.wrapping_add(rhs)
1784                }
1785
1786                #[inline(always)]
1787                fn reduce_product(lhs: Self, rhs: Self) -> Self {
1788                    lhs.wrapping_mul(rhs)
1789                }
1790
1791                #[inline(always)]
1792                fn max_identity() -> Self {
1793                    <$ty>::MIN
1794                }
1795
1796                #[inline(always)]
1797                fn min_identity() -> Self {
1798                    <$ty>::MAX
1799                }
1800
1801                #[inline(always)]
1802                fn reduce_max(lhs: Self, rhs: Self) -> Self {
1803                    lhs.max(rhs)
1804                }
1805
1806                #[inline(always)]
1807                fn reduce_min(lhs: Self, rhs: Self) -> Self {
1808                    lhs.min(rhs)
1809                }
1810            }
1811        )*
1812    };
1813}
1814
1815impl_float_erased_reduce_scalar!(f32, f64);
1816
1817impl_complex_erased_reduce_scalar!(Complex32, Complex64);
1818
1819impl_wrapping_erased_reduce_scalar!(i32, i64);
1820
1821fn validate_unique_axes(axes: &[usize], rank: usize) -> Result<()> {
1822    // Inline for the rank bound (P4); above it the spill may allocate.
1823    let mut inline = [false; strided_view::INLINE_RANK];
1824    let mut spill: Vec<bool> = Vec::new();
1825    let seen: &mut [bool] = if rank <= strided_view::INLINE_RANK {
1826        &mut inline[..rank]
1827    } else {
1828        spill.resize(rank, false);
1829        &mut spill
1830    };
1831    for &axis in axes {
1832        if axis >= rank {
1833            return Err(StridedError::InvalidAxis { axis, rank });
1834        }
1835        if seen[axis] {
1836            return Err(StridedError::InvalidAxis { axis, rank });
1837        }
1838        seen[axis] = true;
1839    }
1840    Ok(())
1841}
1842
1843struct ReduceOuterCursor<'a> {
1844    axes: &'a [ReduceOuterAxis],
1845    coords: CoordScratch,
1846    source_offset: isize,
1847    dest_offset: isize,
1848}
1849impl<'a> ReduceOuterCursor<'a> {
1850    fn decode(
1851        mut linear: usize,
1852        source_base: isize,
1853        dest_base: isize,
1854        axes: &'a [ReduceOuterAxis],
1855    ) -> Result<Self> {
1856        let mut coords = CoordScratch::new(axes.len());
1857        let mut source_offset = source_base;
1858        let mut dest_offset = dest_base;
1859        for (coord, axis) in coords.as_mut_slice().iter_mut().zip(axes) {
1860            // INVARIANT: a non-empty destination domain implies every outer
1861            // extent is nonzero before decode; compile-time span checks make
1862            // these one-time checked additions represent valid layout offsets.
1863            debug_assert!(axis.extent != 0);
1864            *coord = linear % axis.extent;
1865            linear /= axis.extent;
1866            source_offset = checked_offset_add(source_offset, axis.source_step, *coord)?;
1867            dest_offset = checked_offset_add(dest_offset, axis.dest_step, *coord)?;
1868        }
1869        Ok(Self {
1870            axes,
1871            coords,
1872            source_offset,
1873            dest_offset,
1874        })
1875    }
1876
1877    /// Coordinate along the first (fastest) compressed outer axis.
1878    #[inline]
1879    fn leading_coord(&self) -> usize {
1880        self.coords.first()
1881    }
1882
1883    #[inline]
1884    fn advance(&mut self) {
1885        // INVARIANT: compile_axes checked every signed step and reset delta;
1886        // descriptor validation plus exact layout equality proves each cursor
1887        // state is a reachable source/destination offset.
1888        for (coord, axis) in self.coords.as_mut_slice().iter_mut().zip(self.axes) {
1889            let next = *coord + 1;
1890            if next < axis.extent {
1891                *coord = next;
1892                self.source_offset += axis.source_step;
1893                self.dest_offset += axis.dest_step;
1894                return;
1895            }
1896            *coord = 0;
1897            self.source_offset += axis.source_reset;
1898            self.dest_offset += axis.dest_reset;
1899        }
1900    }
1901}
1902struct ReduceInnerCursor<'a> {
1903    axes: &'a [ReduceInnerAxis],
1904    coords: CoordScratch,
1905    source_offset: isize,
1906}
1907impl<'a> ReduceInnerCursor<'a> {
1908    fn new(source_base: isize, axes: &'a [ReduceInnerAxis]) -> Self {
1909        Self {
1910            axes,
1911            coords: CoordScratch::new(axes.len()),
1912            source_offset: source_base,
1913        }
1914    }
1915
1916    #[inline]
1917    fn reset(&mut self, source_base: isize) {
1918        self.coords.as_mut_slice().fill(0);
1919        self.source_offset = source_base;
1920    }
1921
1922    #[inline]
1923    fn advance(&mut self) {
1924        // INVARIANT: compile_axes checked every signed source step and reset
1925        // delta, and the validated descriptor/layout chain proves each value
1926        // offset is reachable from the current outer source base.
1927        for (coord, axis) in self.coords.as_mut_slice().iter_mut().zip(self.axes) {
1928            let next = *coord + 1;
1929            if next < axis.extent {
1930                *coord = next;
1931                self.source_offset += axis.source_step;
1932                return;
1933            }
1934            *coord = 0;
1935            self.source_offset += axis.source_reset;
1936        }
1937    }
1938}
1939fn check_reduce_layout_offset_arithmetic(dims: &[usize], strides: &[isize]) -> Result<()> {
1940    if dims.len() != strides.len() {
1941        return Err(StridedError::StrideLengthMismatch);
1942    }
1943    let mut min_offset = 0isize;
1944    let mut max_offset = 0isize;
1945    for (&dim, &stride) in dims.iter().zip(strides) {
1946        let last =
1947            isize::try_from(dim.saturating_sub(1)).map_err(|_| StridedError::OffsetOverflow)?;
1948        let extent = stride
1949            .checked_mul(last)
1950            .ok_or(StridedError::OffsetOverflow)?;
1951        if extent < 0 {
1952            min_offset = min_offset
1953                .checked_add(extent)
1954                .ok_or(StridedError::OffsetOverflow)?;
1955        } else {
1956            max_offset = max_offset
1957                .checked_add(extent)
1958                .ok_or(StridedError::OffsetOverflow)?;
1959        }
1960    }
1961    let _ = (min_offset, max_offset);
1962    Ok(())
1963}
1964fn compress_reduce_outer_axes(
1965    axes: crate::inline::InlineVec<ReduceOuterAxis>,
1966) -> Result<crate::inline::InlineVec<ReduceOuterAxis>> {
1967    let mut compressed: crate::inline::InlineVec<ReduceOuterAxis> =
1968        crate::inline::InlineVec::with_capacity(axes.len());
1969    for axis in axes {
1970        if let Some(previous) = compressed.last_mut() {
1971            let previous_extent =
1972                isize::try_from(previous.extent).map_err(|_| StridedError::OffsetOverflow)?;
1973            let expected_source = previous
1974                .source_step
1975                .checked_mul(previous_extent)
1976                .ok_or(StridedError::OffsetOverflow)?;
1977            let expected_dest = previous
1978                .dest_step
1979                .checked_mul(previous_extent)
1980                .ok_or(StridedError::OffsetOverflow)?;
1981            if axis.source_step == expected_source && axis.dest_step == expected_dest {
1982                let fused_extent = previous
1983                    .extent
1984                    .checked_mul(axis.extent)
1985                    .ok_or(StridedError::OffsetOverflow)?;
1986                previous.extent = fused_extent;
1987                previous.source_reset = checked_reduce_reset(fused_extent, previous.source_step)?;
1988                previous.dest_reset = checked_reduce_reset(fused_extent, previous.dest_step)?;
1989                continue;
1990            }
1991        }
1992        compressed.push(axis);
1993    }
1994    Ok(compressed)
1995}
1996fn compress_reduce_inner_axes(
1997    axes: crate::inline::InlineVec<ReduceInnerAxis>,
1998) -> Result<crate::inline::InlineVec<ReduceInnerAxis>> {
1999    let mut compressed: crate::inline::InlineVec<ReduceInnerAxis> =
2000        crate::inline::InlineVec::with_capacity(axes.len());
2001    for axis in axes {
2002        if let Some(previous) = compressed.last_mut() {
2003            let previous_extent =
2004                isize::try_from(previous.extent).map_err(|_| StridedError::OffsetOverflow)?;
2005            let expected_source = previous
2006                .source_step
2007                .checked_mul(previous_extent)
2008                .ok_or(StridedError::OffsetOverflow)?;
2009            if axis.source_step == expected_source {
2010                let fused_extent = previous
2011                    .extent
2012                    .checked_mul(axis.extent)
2013                    .ok_or(StridedError::OffsetOverflow)?;
2014                previous.extent = fused_extent;
2015                previous.source_reset = checked_reduce_reset(fused_extent, previous.source_step)?;
2016                continue;
2017            }
2018        }
2019        compressed.push(axis);
2020    }
2021    Ok(compressed)
2022}
2023fn checked_reduce_reset(extent: usize, stride: isize) -> Result<isize> {
2024    if extent == 0 {
2025        return Ok(0);
2026    }
2027    let last = isize::try_from(extent - 1).map_err(|_| StridedError::OffsetOverflow)?;
2028    stride
2029        .checked_mul(last)
2030        .and_then(isize::checked_neg)
2031        .ok_or(StridedError::OffsetOverflow)
2032}
2033fn checked_offset_add(base: isize, stride: isize, coord: usize) -> Result<isize> {
2034    let coord = isize::try_from(coord).map_err(|_| StridedError::OffsetOverflow)?;
2035    let scaled = stride
2036        .checked_mul(coord)
2037        .ok_or(StridedError::OffsetOverflow)?;
2038    base.checked_add(scaled).ok_or(StridedError::OffsetOverflow)
2039}
2040
2041struct CoordScratch {
2042    inline: [usize; RAW_FUSED_RANK_LIMIT],
2043    heap: Option<Vec<usize>>,
2044    len: usize,
2045}
2046
2047impl CoordScratch {
2048    fn new(len: usize) -> Self {
2049        if len <= RAW_FUSED_RANK_LIMIT {
2050            Self {
2051                inline: [0; RAW_FUSED_RANK_LIMIT],
2052                heap: None,
2053                len,
2054            }
2055        } else {
2056            Self {
2057                inline: [0; RAW_FUSED_RANK_LIMIT],
2058                heap: Some(vec![0; len]),
2059                len,
2060            }
2061        }
2062    }
2063
2064    #[inline]
2065    fn first(&self) -> usize {
2066        match &self.heap {
2067            Some(heap) => heap.first().copied().unwrap_or(0),
2068            None => self.inline[0],
2069        }
2070    }
2071
2072    fn as_mut_slice(&mut self) -> &mut [usize] {
2073        match &mut self.heap {
2074            Some(heap) => heap,
2075            None => &mut self.inline[..self.len],
2076        }
2077    }
2078}