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}