use crate::shapes::Dyn;
use crate::shapes::ShapeBuf;
use crate::shapes::dim::Dim;
use crate::shapes::error::{Axis, DimensionConstraint, OperationKind, ShapeError};
use crate::shapes::shape::{DimCons, DynShape, Nil, Shape};
use alloc::vec::Vec;
#[inline]
fn checked_broadcast_dim(
axis: Axis,
lhs: usize,
rhs: usize,
) -> core::result::Result<usize, ShapeError> {
if lhs == rhs || lhs == 1 || rhs == 1 {
Ok(if lhs == 1 { rhs } else { lhs })
} else {
Err(ShapeError::DimensionMismatch {
operation: OperationKind::Broadcast,
axis,
lhs,
rhs,
constraint: DimensionConstraint::Broadcastable,
})
}
}
fn broadcast_dims(lhs: &ShapeBuf, rhs: &ShapeBuf) -> core::result::Result<Vec<usize>, ShapeError> {
let lhs_dims: Vec<usize> = lhs.clone().into();
let rhs_dims: Vec<usize> = rhs.clone().into();
broadcast_dim_slices(&lhs_dims, &rhs_dims)
}
pub fn broadcast_dim_slices(
lhs_dims: &[usize],
rhs_dims: &[usize],
) -> core::result::Result<Vec<usize>, ShapeError> {
let out_rank = lhs_dims.len().max(rhs_dims.len());
let mut out = Vec::with_capacity(out_rank);
for i in 0..out_rank {
let from_end = out_rank - i;
let l = lhs_dims
.len()
.checked_sub(from_end)
.map(|idx| lhs_dims[idx]);
let r = rhs_dims
.len()
.checked_sub(from_end)
.map(|idx| rhs_dims[idx]);
out.push(checked_broadcast_dim(
Axis::Index(i),
l.unwrap_or(1),
r.unwrap_or(1),
)?);
}
Ok(out)
}
#[diagnostic::on_unimplemented(
message = "Cannot broadcast shape `{Self}` to `{Rhs}`",
label = "Shape mismatch during broadcast",
note = "Broadcast requires dimensions to be equal, or one of them to be 1"
)]
pub trait BroadcastShape<Rhs: Shape>: Shape {
type Output: Shape;
fn output_shape(lhs: &ShapeBuf, rhs: &ShapeBuf) -> core::result::Result<ShapeBuf, ShapeError>;
}
#[diagnostic::on_unimplemented(
message = "Cannot broadcast axis `{Self}` against `{Rhs}`",
label = "incompatible axis",
note = "two axes broadcast when their types are the same, or one of them is `U1`"
)]
pub trait BroadcastDim<Rhs: Dim>: Dim {
type Output: Dim;
}
pub trait AnonymousDim: Dim {}
impl AnonymousDim for usize {}
impl<const N: usize> AnonymousDim for crate::shapes::dim::ConstDim<N> {}
impl AnonymousDim for typenum::UTerm {}
impl<U, B> AnonymousDim for typenum::UInt<U, B> where typenum::UInt<U, B>: Dim {}
impl<A: Dim, B: Dim> AnonymousDim for crate::shapes::dim::AddDim<A, B> {}
impl<A: Dim, B: Dim> AnonymousDim for crate::shapes::dim::CheckedSubDim<A, B> {}
impl<A: Dim, B: Dim> AnonymousDim for crate::shapes::dim::ExactDivDim<A, B> {}
impl<A: Dim, B: Dim> AnonymousDim for crate::shapes::dim::MulDim<A, B> {}
impl<A: AnonymousDim, B: AnonymousDim> AnonymousDim for crate::shapes::dim::BroadcastExtent<A, B> {}
type StaticBroadcast<L, R> = crate::shapes::dim::BroadcastStaticNat<L, R>;
type RuntimeStatic<R> =
<<R as typenum::IsEqual<typenum::U1>>::Output as crate::shapes::dim::BroadcastChoice<
usize,
R,
>>::Output;
type StaticRuntime<L> =
<<L as typenum::IsEqual<typenum::U1>>::Output as crate::shapes::dim::BroadcastChoice<
usize,
L,
>>::Output;
trait StaticNatDim: AnonymousDim + typenum::Unsigned + typenum::IsEqual<typenum::U1> {}
impl StaticNatDim for typenum::UTerm {}
impl<U, B> StaticNatDim for typenum::UInt<U, B> where
typenum::UInt<U, B>: AnonymousDim + typenum::Unsigned + typenum::IsEqual<typenum::U1>
{
}
impl<const N: usize> BroadcastDim<crate::shapes::dim::ConstDim<N>>
for crate::shapes::dim::ConstDim<N>
{
type Output = crate::shapes::dim::ConstDim<N>;
}
impl<L, R> BroadcastDim<R> for L
where
L: StaticNatDim,
R: StaticNatDim,
L: typenum::IsEqual<typenum::U1> + typenum::IsEqual<R>,
R: typenum::IsEqual<typenum::U1>,
<L as typenum::IsEqual<typenum::U1>>::Output:
crate::shapes::dim::BroadcastChoice<R, crate::shapes::dim::BroadcastRightNat<L, R>>,
<R as typenum::IsEqual<typenum::U1>>::Output:
crate::shapes::dim::BroadcastChoice<L, crate::shapes::dim::BroadcastSameNat<L, R>>,
<L as typenum::IsEqual<R>>::Output: crate::shapes::dim::BroadcastChoice<L, ()>,
StaticBroadcast<L, R>: Dim,
{
type Output = StaticBroadcast<L, R>;
}
impl BroadcastDim<usize> for usize {
type Output = crate::shapes::dim::BroadcastExtent<Self, usize>;
}
impl<R> BroadcastDim<R> for usize
where
R: StaticNatDim,
<R as typenum::IsEqual<typenum::U1>>::Output: crate::shapes::dim::BroadcastChoice<usize, R>,
RuntimeStatic<R>: Dim,
{
type Output = RuntimeStatic<R>;
}
impl<L> BroadcastDim<usize> for L
where
L: StaticNatDim,
<L as typenum::IsEqual<typenum::U1>>::Output: crate::shapes::dim::BroadcastChoice<usize, L>,
StaticRuntime<L>: Dim,
{
type Output = StaticRuntime<L>;
}
impl<Tag, R> BroadcastDim<R> for crate::shapes::dim::NamedDim<Tag, usize>
where
Tag: crate::shapes::AxisTag,
R: StaticNatDim,
R: typenum::IsEqual<typenum::U1>,
<R as typenum::IsEqual<typenum::U1>>::Output: crate::shapes::dim::BroadcastChoice<usize, R>,
RuntimeStatic<R>: Dim,
{
type Output = crate::shapes::dim::NamedDim<Tag, RuntimeStatic<R>>;
}
impl<Tag> BroadcastDim<usize> for crate::shapes::dim::NamedDim<Tag, usize>
where
Tag: crate::shapes::AxisTag,
{
type Output =
crate::shapes::dim::NamedDim<Tag, crate::shapes::dim::BroadcastExtent<usize, usize>>;
}
impl<Tag, L, R> BroadcastDim<crate::shapes::dim::NamedDim<Tag, R>> for L
where
Tag: crate::shapes::AxisTag,
L: StaticNatDim,
R: StaticNatDim,
L: typenum::IsEqual<typenum::U1> + typenum::IsEqual<R>,
R: typenum::IsEqual<typenum::U1>,
<L as typenum::IsEqual<typenum::U1>>::Output:
crate::shapes::dim::BroadcastChoice<R, crate::shapes::dim::BroadcastRightNat<L, R>>,
<R as typenum::IsEqual<typenum::U1>>::Output:
crate::shapes::dim::BroadcastChoice<L, crate::shapes::dim::BroadcastSameNat<L, R>>,
<L as typenum::IsEqual<R>>::Output: crate::shapes::dim::BroadcastChoice<L, ()>,
StaticBroadcast<L, R>: Dim,
{
type Output = crate::shapes::dim::NamedDim<Tag, StaticBroadcast<L, R>>;
}
impl<Tag, L> BroadcastDim<crate::shapes::dim::NamedDim<Tag, usize>> for L
where
Tag: crate::shapes::AxisTag,
L: StaticNatDim,
L: typenum::IsEqual<typenum::U1>,
<L as typenum::IsEqual<typenum::U1>>::Output: crate::shapes::dim::BroadcastChoice<usize, L>,
StaticRuntime<L>: Dim,
{
type Output = crate::shapes::dim::NamedDim<Tag, StaticRuntime<L>>;
}
impl<Tag, L, R> BroadcastDim<R> for crate::shapes::dim::NamedDim<Tag, L>
where
Tag: crate::shapes::AxisTag,
L: StaticNatDim,
R: StaticNatDim,
L: typenum::IsEqual<typenum::U1> + typenum::IsEqual<R>,
R: typenum::IsEqual<typenum::U1>,
<L as typenum::IsEqual<typenum::U1>>::Output:
crate::shapes::dim::BroadcastChoice<R, crate::shapes::dim::BroadcastRightNat<L, R>>,
<R as typenum::IsEqual<typenum::U1>>::Output:
crate::shapes::dim::BroadcastChoice<L, crate::shapes::dim::BroadcastSameNat<L, R>>,
<L as typenum::IsEqual<R>>::Output: crate::shapes::dim::BroadcastChoice<L, ()>,
StaticBroadcast<L, R>: Dim,
{
type Output = crate::shapes::dim::NamedDim<Tag, StaticBroadcast<L, R>>;
}
impl<Tag, L> BroadcastDim<usize> for crate::shapes::dim::NamedDim<Tag, L>
where
Tag: crate::shapes::AxisTag,
L: StaticNatDim,
L: typenum::IsEqual<typenum::U1>,
<L as typenum::IsEqual<typenum::U1>>::Output: crate::shapes::dim::BroadcastChoice<usize, L>,
StaticRuntime<L>: Dim,
{
type Output = crate::shapes::dim::NamedDim<Tag, StaticRuntime<L>>;
}
impl<Tag, L, R> BroadcastDim<crate::shapes::dim::NamedDim<Tag, R>>
for crate::shapes::dim::NamedDim<Tag, L>
where
Tag: crate::shapes::AxisTag,
L: StaticNatDim,
R: StaticNatDim,
L: typenum::IsEqual<typenum::U1> + typenum::IsEqual<R>,
R: typenum::IsEqual<typenum::U1>,
<L as typenum::IsEqual<typenum::U1>>::Output:
crate::shapes::dim::BroadcastChoice<R, crate::shapes::dim::BroadcastRightNat<L, R>>,
<R as typenum::IsEqual<typenum::U1>>::Output:
crate::shapes::dim::BroadcastChoice<L, crate::shapes::dim::BroadcastSameNat<L, R>>,
<L as typenum::IsEqual<R>>::Output: crate::shapes::dim::BroadcastChoice<L, ()>,
StaticBroadcast<L, R>: Dim,
{
type Output = crate::shapes::dim::NamedDim<Tag, StaticBroadcast<L, R>>;
}
impl<Tag, R> BroadcastDim<crate::shapes::dim::NamedDim<Tag, R>>
for crate::shapes::dim::NamedDim<Tag, usize>
where
Tag: crate::shapes::AxisTag,
R: StaticNatDim,
R: typenum::IsEqual<typenum::U1>,
<R as typenum::IsEqual<typenum::U1>>::Output: crate::shapes::dim::BroadcastChoice<usize, R>,
RuntimeStatic<R>: Dim,
{
type Output = crate::shapes::dim::NamedDim<Tag, RuntimeStatic<R>>;
}
impl<Tag> BroadcastDim<crate::shapes::dim::NamedDim<Tag, usize>>
for crate::shapes::dim::NamedDim<Tag, usize>
where
Tag: crate::shapes::AxisTag,
{
type Output =
crate::shapes::dim::NamedDim<Tag, crate::shapes::dim::BroadcastExtent<usize, usize>>;
}
impl<R: Shape + DynShape> BroadcastShape<R> for Dyn {
type Output = Dyn;
fn output_shape(lhs: &ShapeBuf, rhs: &ShapeBuf) -> core::result::Result<ShapeBuf, ShapeError> {
broadcast_dims(lhs, rhs).map(|dims| crate::shapes::ShapeBuf::from_slice(&dims))
}
}
impl BroadcastShape<Dyn> for Nil {
type Output = Dyn;
fn output_shape(lhs: &ShapeBuf, rhs: &ShapeBuf) -> core::result::Result<ShapeBuf, ShapeError> {
broadcast_dims(lhs, rhs).map(|dims| crate::shapes::ShapeBuf::from_slice(&dims))
}
}
impl<H: Dim, T: Shape + DynShape> BroadcastShape<Dyn> for DimCons<H, T> {
type Output = Dyn;
fn output_shape(lhs: &ShapeBuf, rhs: &ShapeBuf) -> core::result::Result<ShapeBuf, ShapeError> {
broadcast_dims(lhs, rhs).map(|dims| crate::shapes::ShapeBuf::from_slice(&dims))
}
}
pub trait ReverseShape: Shape {
type Output: Shape;
}
impl ReverseShape for Nil {
type Output = Nil;
}
impl<H: Dim, T: Shape + ReverseShape> ReverseShape for DimCons<H, T>
where
<T as ReverseShape>::Output: crate::shapes::AppendDim<H>,
{
type Output = <<T as ReverseShape>::Output as crate::shapes::AppendDim<H>>::Output;
}
trait BroadcastReversed<Rhs: Shape>: Shape {
type Output: Shape;
}
trait StaticShapeNames {
fn names() -> Vec<Option<&'static str>>;
}
impl StaticShapeNames for Nil {
fn names() -> Vec<Option<&'static str>> {
Vec::new()
}
}
impl<H: Dim, T: Shape + StaticShapeNames> StaticShapeNames for DimCons<H, T> {
fn names() -> Vec<Option<&'static str>> {
let mut names = Vec::with_capacity(1 + T::RANK.unwrap_or(0));
names.push(H::NAME);
names.extend(T::names());
names
}
}
fn validate_static_names<L: StaticShapeNames, R: StaticShapeNames>()
-> core::result::Result<(), ShapeError> {
let lhs = L::names();
let rhs = R::names();
let rank = lhs.len().max(rhs.len());
for output_axis in 0..rank {
let lhs_name = output_axis
.checked_add(lhs.len())
.and_then(|index| index.checked_sub(rank))
.and_then(|index| lhs.get(index))
.copied()
.flatten();
let rhs_name = output_axis
.checked_add(rhs.len())
.and_then(|index| index.checked_sub(rank))
.and_then(|index| rhs.get(index))
.copied()
.flatten();
if let (Some(lhs), Some(rhs)) = (lhs_name, rhs_name)
&& lhs != rhs
{
return Err(ShapeError::ConflictingNamedAxes {
axis: output_axis,
lhs,
rhs,
});
}
}
Ok(())
}
impl BroadcastReversed<Nil> for Nil {
type Output = Nil;
}
impl<H: Dim, T: Shape> BroadcastReversed<Nil> for DimCons<H, T> {
type Output = DimCons<H, T>;
}
impl<H: Dim, T: Shape> BroadcastReversed<DimCons<H, T>> for Nil {
type Output = DimCons<H, T>;
}
impl<LH: Dim, LT: Shape, RH: Dim, RT: Shape> BroadcastReversed<DimCons<RH, RT>> for DimCons<LH, LT>
where
LH: BroadcastDim<RH>,
LT: BroadcastReversed<RT>,
{
type Output = DimCons<<LH as BroadcastDim<RH>>::Output, <LT as BroadcastReversed<RT>>::Output>;
}
impl BroadcastShape<Nil> for Nil {
type Output = Nil;
fn output_shape(
_: &crate::shapes::ShapeBuf,
_: &crate::shapes::ShapeBuf,
) -> core::result::Result<crate::shapes::ShapeBuf, ShapeError> {
Ok(crate::shapes::ShapeBuf::scalar())
}
}
impl<H: Dim, T: Shape> BroadcastShape<Nil> for DimCons<H, T> {
type Output = DimCons<H, T>;
fn output_shape(
lhs: &ShapeBuf,
_: &crate::shapes::ShapeBuf,
) -> core::result::Result<ShapeBuf, ShapeError> {
Ok(lhs.clone())
}
}
impl<H: Dim, T: Shape> BroadcastShape<DimCons<H, T>> for Nil {
type Output = DimCons<H, T>;
fn output_shape(
_: &crate::shapes::ShapeBuf,
rhs: &ShapeBuf,
) -> core::result::Result<ShapeBuf, ShapeError> {
Ok(rhs.clone())
}
}
impl<LH: Dim, LT, RH: Dim, RT, LRev, RRev, RevOut> BroadcastShape<DimCons<RH, RT>>
for DimCons<LH, LT>
where
LT: Shape + crate::shapes::DynShape + StaticShapeNames,
RT: Shape + crate::shapes::DynShape + StaticShapeNames,
DimCons<LH, LT>: ReverseShape<Output = LRev>,
DimCons<RH, RT>: ReverseShape<Output = RRev>,
LRev: Shape + BroadcastReversed<RRev>,
RRev: Shape,
<LRev as BroadcastReversed<RRev>>::Output: ReverseShape<Output = RevOut>,
RevOut: Shape,
{
type Output = RevOut;
fn output_shape(lhs: &ShapeBuf, rhs: &ShapeBuf) -> core::result::Result<ShapeBuf, ShapeError> {
validate_static_names::<Self, DimCons<RH, RT>>()?;
<Self::Output as Shape>::STATIC_VALID;
let dims = broadcast_dims(lhs, rhs)?;
crate::shapes::shape::shape_buf_from_dims::<Self::Output>(OperationKind::Broadcast, &dims)
}
}