Skip to main content

strided_basic/
outer_product.rs

1//! Semantic outer-product API on dynamic-rank strided views.
2
3use core::mem::MaybeUninit;
4use std::ops::Mul;
5
6use crate::view::{StridedView, StridedViewMut};
7use crate::{broadcast_mul_into, broadcast_mul_into_uninit, Exec};
8use crate::{ElementOp, Result, StridedError};
9
10type AxisVec<T> = crate::inline::InlineVec<T>;
11
12/// Compute `dest[lhs_free..., rhs_free..., batch...] =
13/// lhs[lhs_free..., batch...] * rhs[rhs_free..., batch...]`.
14///
15/// This is a semantic convenience wrapper over [`broadcast_mul_into`]. The
16/// broadcast/mul planner owns kernel selection, so explicit outer-product calls
17/// and equivalent broadcasted multiplication use the same implementation path.
18///
19/// # Errors
20///
21/// Returns [`StridedError::RankMismatch`] when the free/batch split does not
22/// describe the operand and destination ranks, [`StridedError::ShapeMismatch`]
23/// when the batch or free extents disagree, or
24/// [`StridedError::NonInjectiveOutputLayout`] when the destination layout
25/// cannot be proven representable and injective. Validation completes before
26/// the first write.
27pub fn batched_outer_product_into<D, A, B, OpA, OpB>(
28    dest: &mut StridedViewMut<D>,
29    lhs: &StridedView<A, OpA>,
30    rhs: &StridedView<B, OpB>,
31    lhs_free_ndim: usize,
32    rhs_free_ndim: usize,
33    exec: Exec<'_>,
34) -> Result<()>
35where
36    D: Copy + Send + Sync + 'static,
37    A: Copy + Send + Sync + Mul<B, Output = D> + 'static,
38    B: Copy + Send + Sync + 'static,
39    OpA: ElementOp<A>,
40    OpB: ElementOp<B>,
41{
42    validate_batched_outer_shape(dest, lhs, rhs, lhs_free_ndim, rhs_free_ndim)?;
43
44    let batch_ndim = lhs.ndim() - lhs_free_ndim;
45    let mut lhs_axes = AxisVec::<usize>::with_capacity(lhs.ndim());
46    let mut rhs_axes = AxisVec::<usize>::with_capacity(rhs.ndim());
47
48    lhs_axes.extend(0..lhs_free_ndim);
49    rhs_axes.extend(lhs_free_ndim..lhs_free_ndim + rhs_free_ndim);
50
51    let batch_axis_start = lhs_free_ndim + rhs_free_ndim;
52    lhs_axes.extend(batch_axis_start..batch_axis_start + batch_ndim);
53    rhs_axes.extend(batch_axis_start..batch_axis_start + batch_ndim);
54
55    broadcast_mul_into(dest, lhs, &lhs_axes, rhs, &rhs_axes, exec)
56}
57
58/// Compute a batched outer product into a fully overwritten uninitialized output.
59///
60/// Rank, shape, destination-injectivity, and reachable-byte overlap validation
61/// completes before the first write. Safe Rust borrows already prevent
62/// input/output aliasing; the explicit overlap check in the shared broadcast
63/// kernel preserves the contract for views produced through unsafe constructors.
64///
65/// `Ok(())` means every logical destination element is initialized. An error
66/// occurs before writes. A panic during replay may leave a partially initialized
67/// destination, which remains safe to drop as `MaybeUninit<D>`.
68///
69/// # Errors
70///
71/// Returns [`StridedError::RankMismatch`] when the free/batch split does not
72/// describe the operand and destination ranks, or
73/// [`StridedError::ShapeMismatch`] when the batch or free extents disagree,
74/// [`StridedError::NonInjectiveOutputLayout`] for an overlapping output layout,
75/// [`StridedError::OverlappingInputOutput`] for aliased storage, or
76/// [`StridedError::OffsetOverflow`] when a reachable byte range is not
77/// representable.
78pub fn batched_outer_product_into_uninit<D, A, B, OpA, OpB>(
79    dest: &mut StridedViewMut<MaybeUninit<D>>,
80    lhs: &StridedView<A, OpA>,
81    rhs: &StridedView<B, OpB>,
82    lhs_free_ndim: usize,
83    rhs_free_ndim: usize,
84    exec: Exec<'_>,
85) -> Result<()>
86where
87    D: Copy + Send + Sync + 'static,
88    A: Copy + Send + Sync + Mul<B, Output = D> + 'static,
89    B: Copy + Send + Sync + 'static,
90    OpA: ElementOp<A>,
91    OpB: ElementOp<B>,
92{
93    validate_batched_outer_shape(dest, lhs, rhs, lhs_free_ndim, rhs_free_ndim)?;
94    let batch_ndim = lhs.ndim() - lhs_free_ndim;
95    let mut lhs_axes = AxisVec::<usize>::with_capacity(lhs.ndim());
96    let mut rhs_axes = AxisVec::<usize>::with_capacity(rhs.ndim());
97    lhs_axes.extend(0..lhs_free_ndim);
98    rhs_axes.extend(lhs_free_ndim..lhs_free_ndim + rhs_free_ndim);
99    let batch_axis_start = lhs_free_ndim + rhs_free_ndim;
100    lhs_axes.extend(batch_axis_start..batch_axis_start + batch_ndim);
101    rhs_axes.extend(batch_axis_start..batch_axis_start + batch_ndim);
102    broadcast_mul_into_uninit(dest, lhs, &lhs_axes, rhs, &rhs_axes, exec)
103}
104
105fn validate_batched_outer_shape<D, A, OpA, B, OpB>(
106    dest: &StridedViewMut<D>,
107    lhs: &StridedView<A, OpA>,
108    rhs: &StridedView<B, OpB>,
109    lhs_free_ndim: usize,
110    rhs_free_ndim: usize,
111) -> Result<()> {
112    if lhs_free_ndim > lhs.ndim() {
113        return Err(StridedError::RankMismatch(lhs_free_ndim, lhs.ndim()));
114    }
115    if rhs_free_ndim > rhs.ndim() {
116        return Err(StridedError::RankMismatch(rhs_free_ndim, rhs.ndim()));
117    }
118
119    let lhs_batch_ndim = lhs.ndim() - lhs_free_ndim;
120    let rhs_batch_ndim = rhs.ndim() - rhs_free_ndim;
121    if lhs_batch_ndim != rhs_batch_ndim {
122        return Err(StridedError::RankMismatch(lhs_batch_ndim, rhs_batch_ndim));
123    }
124
125    let expected_dest_rank = lhs_free_ndim + rhs_free_ndim + lhs_batch_ndim;
126    if dest.ndim() != expected_dest_rank {
127        return Err(StridedError::RankMismatch(dest.ndim(), expected_dest_rank));
128    }
129
130    ensure_dims(&dest.dims()[..lhs_free_ndim], &lhs.dims()[..lhs_free_ndim])?;
131    ensure_dims(
132        &dest.dims()[lhs_free_ndim..lhs_free_ndim + rhs_free_ndim],
133        &rhs.dims()[..rhs_free_ndim],
134    )?;
135    ensure_dims(
136        &dest.dims()[lhs_free_ndim + rhs_free_ndim..],
137        &lhs.dims()[lhs_free_ndim..],
138    )?;
139    ensure_dims(
140        &dest.dims()[lhs_free_ndim + rhs_free_ndim..],
141        &rhs.dims()[rhs_free_ndim..],
142    )?;
143
144    Ok(())
145}
146
147fn ensure_dims(actual: &[usize], expected: &[usize]) -> Result<()> {
148    if actual == expected {
149        Ok(())
150    } else {
151        Err(StridedError::ShapeMismatch(
152            actual.to_vec(),
153            expected.to_vec(),
154        ))
155    }
156}
157
158/// Storage layout for a lazily ordered outer product.
159///
160/// Returned by [`plan_lazy_outer_product`]. The caller allocates a dense
161/// column-major base of [`base_dims`](Self::base_dims), fills it through a
162/// destination descriptor over that base with the logical output dims and
163/// [`output_strides`](Self::output_strides) at offset zero (for example with
164/// [`broadcast_mul_into_uninit`] and the original axis maps), and then exposes
165/// the result as a strided view with those same dims and strides.
166#[derive(Clone, Debug, PartialEq, Eq)]
167pub struct LazyOuterProductLayout {
168    /// Column-major extents of the dense base allocation.
169    pub base_dims: Vec<usize>,
170    /// Strides, in base elements, of the logical output axes over the base.
171    pub output_strides: Vec<isize>,
172}
173
174/// Plan an outer-product output whose memory order follows the inputs'
175/// physical stride order instead of the logical output order.
176///
177/// `lhs_axes[k]` (respectively `rhs_axes[k]`) names the output axis that
178/// operand axis `k` maps to, with the operand extent equal to the output
179/// extent. Output axes mapped only by `lhs` are its free axes, axes mapped
180/// only by `rhs` are its free axes, and axes mapped by both are batch axes.
181///
182/// A layout is returned only when the product splits into free and batch
183/// groups, both free groups have more than one element, the logical output
184/// order is `[lhs_free, rhs_free, batch]` or `[rhs_free, lhs_free, batch]`,
185/// all strides are non-negative, and sorting either operand's free axes by
186/// `(stride, axis)` changes their order. The base then holds the leading
187/// group's free axes in the leading operand's physical order, then the
188/// trailing group's free axes in the trailing operand's physical order, then
189/// the batch axes in output order. Traversing inputs in their physical order
190/// while writing the base contiguously is what makes the layout useful.
191///
192/// # Examples
193///
194/// ```
195/// use strided_basic::plan_lazy_outer_product;
196///
197/// // lhs is a transposed 2 x 3 matrix (row-major strides), rhs is a vector.
198/// let layout = plan_lazy_outer_product(&[2, 3, 4], &[2, 3], &[3, 1], &[0, 1], &[4], &[1], &[2])
199///     .unwrap()
200///     .unwrap();
201/// assert_eq!(layout.base_dims, [3, 2, 4]);
202/// assert_eq!(layout.output_strides, [3, 1, 6]);
203/// ```
204///
205/// # Errors
206///
207/// Returns [`StridedError::RankMismatch`] when an operand's dims, strides,
208/// and axis map lengths disagree, and [`StridedError::OffsetOverflow`] when a
209/// base extent product or stride is not representable. Inputs that are valid
210/// but ineligible return `Ok(None)`.
211pub fn plan_lazy_outer_product(
212    output_dims: &[usize],
213    lhs_dims: &[usize],
214    lhs_strides: &[isize],
215    lhs_axes: &[usize],
216    rhs_dims: &[usize],
217    rhs_strides: &[isize],
218    rhs_axes: &[usize],
219) -> Result<Option<LazyOuterProductLayout>> {
220    for (dims, strides, axes) in [
221        (lhs_dims, lhs_strides, lhs_axes),
222        (rhs_dims, rhs_strides, rhs_axes),
223    ] {
224        if dims.len() != strides.len() {
225            return Err(StridedError::RankMismatch(dims.len(), strides.len()));
226        }
227        if dims.len() != axes.len() {
228            return Err(StridedError::RankMismatch(dims.len(), axes.len()));
229        }
230    }
231    if !extents_match_output(output_dims, lhs_dims, lhs_axes)
232        || !extents_match_output(output_dims, rhs_dims, rhs_axes)
233        || lhs_strides
234            .iter()
235            .chain(rhs_strides)
236            .any(|&stride| stride < 0)
237    {
238        return Ok(None);
239    }
240    let Some(partition) = classify_outer_axes(output_dims.len(), lhs_axes, rhs_axes) else {
241        return Ok(None);
242    };
243    if checked_axes_product(lhs_dims, &partition.lhs_free)? <= 1
244        || checked_axes_product(rhs_dims, &partition.rhs_free)? <= 1
245    {
246        return Ok(None);
247    }
248
249    let output_rank = output_dims.len();
250    let lhs_prefix = partition
251        .lhs_free_out
252        .iter()
253        .chain(&partition.rhs_free_out)
254        .chain(&partition.batch_out)
255        .copied()
256        .eq(0..output_rank);
257    let rhs_prefix = !lhs_prefix
258        && partition
259            .rhs_free_out
260            .iter()
261            .chain(&partition.lhs_free_out)
262            .chain(&partition.batch_out)
263            .copied()
264            .eq(0..output_rank);
265    if !lhs_prefix && !rhs_prefix {
266        return Ok(None);
267    }
268
269    let lhs_physical = axes_by_physical_stride(lhs_strides, &partition.lhs_free);
270    let rhs_physical = axes_by_physical_stride(rhs_strides, &partition.rhs_free);
271    if lhs_physical == partition.lhs_free && rhs_physical == partition.rhs_free {
272        return Ok(None);
273    }
274
275    // Base axis order: leading free, trailing free, then batch in output order.
276    let mut base_out_axes = Vec::with_capacity(output_rank);
277    let (leading, leading_axes, trailing, trailing_axes) = if lhs_prefix {
278        (&lhs_physical, lhs_axes, &rhs_physical, rhs_axes)
279    } else {
280        (&rhs_physical, rhs_axes, &lhs_physical, lhs_axes)
281    };
282    base_out_axes.extend(leading.iter().map(|&axis| leading_axes[axis]));
283    base_out_axes.extend(trailing.iter().map(|&axis| trailing_axes[axis]));
284    base_out_axes.extend(partition.batch_out.iter().copied());
285
286    let base_dims: Vec<usize> = base_out_axes
287        .iter()
288        .map(|&axis| output_dims[axis])
289        .collect();
290    let mut output_strides = vec![0isize; output_rank];
291    let mut stride = 1isize;
292    for (&out_axis, &extent) in base_out_axes.iter().zip(&base_dims) {
293        // INVARIANT: `classify_outer_axes` proved every output axis appears
294        // exactly once in the free/batch groups, so each slot is written once.
295        output_strides[out_axis] = stride;
296        let extent = isize::try_from(extent).map_err(|_| StridedError::OffsetOverflow)?;
297        stride = stride
298            .checked_mul(extent)
299            .ok_or(StridedError::OffsetOverflow)?;
300    }
301    Ok(Some(LazyOuterProductLayout {
302        base_dims,
303        output_strides,
304    }))
305}
306
307struct OuterAxisPartition {
308    lhs_free_out: Vec<usize>,
309    rhs_free_out: Vec<usize>,
310    batch_out: Vec<usize>,
311    lhs_free: Vec<usize>,
312    rhs_free: Vec<usize>,
313}
314
315fn extents_match_output(output_dims: &[usize], dims: &[usize], axes: &[usize]) -> bool {
316    dims.iter()
317        .zip(axes)
318        .all(|(&dim, &axis)| output_dims.get(axis) == Some(&dim))
319}
320
321fn operand_axes_by_output(axes: &[usize], output_rank: usize) -> Option<Vec<Option<usize>>> {
322    let mut by_output = vec![None; output_rank];
323    for (operand_axis, &output_axis) in axes.iter().enumerate() {
324        if by_output
325            .get_mut(output_axis)?
326            .replace(operand_axis)
327            .is_some()
328        {
329            return None;
330        }
331    }
332    Some(by_output)
333}
334
335fn classify_outer_axes(
336    output_rank: usize,
337    lhs_axes: &[usize],
338    rhs_axes: &[usize],
339) -> Option<OuterAxisPartition> {
340    let lhs_by_output = operand_axes_by_output(lhs_axes, output_rank)?;
341    let rhs_by_output = operand_axes_by_output(rhs_axes, output_rank)?;
342    let mut partition = OuterAxisPartition {
343        lhs_free_out: Vec::new(),
344        rhs_free_out: Vec::new(),
345        batch_out: Vec::new(),
346        lhs_free: Vec::new(),
347        rhs_free: Vec::new(),
348    };
349    for output_axis in 0..output_rank {
350        match (lhs_by_output[output_axis], rhs_by_output[output_axis]) {
351            (Some(_), Some(_)) => partition.batch_out.push(output_axis),
352            (Some(lhs_axis), None) => {
353                partition.lhs_free_out.push(output_axis);
354                partition.lhs_free.push(lhs_axis);
355            }
356            (None, Some(rhs_axis)) => {
357                partition.rhs_free_out.push(output_axis);
358                partition.rhs_free.push(rhs_axis);
359            }
360            (None, None) => return None,
361        }
362    }
363    Some(partition)
364}
365
366fn checked_axes_product(dims: &[usize], axes: &[usize]) -> Result<usize> {
367    // A zero extent makes the group empty even when the other extents
368    // overflow.
369    if axes.iter().any(|&axis| dims[axis] == 0) {
370        return Ok(0);
371    }
372    axes.iter().try_fold(1usize, |acc, &axis| {
373        acc.checked_mul(dims[axis])
374            .ok_or(StridedError::OffsetOverflow)
375    })
376}
377
378fn axes_by_physical_stride(strides: &[isize], axes: &[usize]) -> Vec<usize> {
379    let mut sorted = axes.to_vec();
380    sorted.sort_by(|&lhs, &rhs| strides[lhs].cmp(&strides[rhs]).then(lhs.cmp(&rhs)));
381    sorted
382}