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