use crate::shapes::{DimCons, NamedDim, Nil, Shape};
use alloc::vec::Vec;
pub struct InferDim;
pub struct Ellipsis;
pub struct Slice<Start, End, Diff> {
_marker: core::marker::PhantomData<(Start, End, Diff)>,
}
pub trait DimIdx {
type Resolved: Dim;
fn size() -> Option<usize>;
}
use super::dim::Dim;
use typenum::consts::*;
use typenum::{Bit, UInt, UTerm, Unsigned};
impl DimIdx for UTerm {
type Resolved = UTerm;
fn size() -> Option<usize> {
Some(0)
}
}
impl<U, B> DimIdx for UInt<U, B>
where
U: Unsigned + Dim,
B: Bit + Default + Copy + Clone + core::fmt::Debug + Send + Sync + Eq + PartialEq + 'static,
UInt<U, B>: Unsigned
+ Default
+ Copy
+ Clone
+ core::fmt::Debug
+ Send
+ Sync
+ Eq
+ PartialEq
+ 'static,
{
type Resolved = UInt<U, B>;
fn size() -> Option<usize> {
Some(Self::USIZE)
}
}
impl DimIdx for InferDim {
type Resolved = usize;
fn size() -> Option<usize> {
None
}
}
impl<Tag: crate::shapes::AxisTag> DimIdx for NamedDim<Tag, usize> {
type Resolved = NamedDim<Tag, usize>;
fn size() -> Option<usize> {
None
}
}
#[diagnostic::on_unimplemented(
message = "Cannot reshape dimension into `{Self}`",
label = "Invalid dimension for reshape",
note = "The element count must remain constant during reshape"
)]
pub trait ReshapeTarget<In: Shape> {
type Output: Shape;
fn calculate_shape(
in_shape_vec: &[usize],
) -> core::result::Result<Vec<usize>, crate::shapes::error::ShapeError>;
}
#[doc(hidden)]
pub trait ReshapeTargetSpec {
type Output: Shape;
fn collect(
sizes: &mut Vec<usize>,
inferred: &mut Option<usize>,
) -> core::result::Result<(), crate::shapes::error::ShapeError>;
}
impl ReshapeTargetSpec for Nil {
type Output = Nil;
fn collect(
_sizes: &mut Vec<usize>,
_inferred: &mut Option<usize>,
) -> core::result::Result<(), crate::shapes::error::ShapeError> {
Ok(())
}
}
impl<D: DimIdx, T: ReshapeTargetSpec> ReshapeTargetSpec for DimCons<D, T>
where
D::Resolved: Dim,
{
type Output = DimCons<D::Resolved, T::Output>;
fn collect(
sizes: &mut Vec<usize>,
inferred: &mut Option<usize>,
) -> core::result::Result<(), crate::shapes::error::ShapeError> {
let index = sizes.len();
if let Some(size) = D::size() {
sizes.push(size);
} else {
if inferred.is_some() {
return Err(crate::shapes::error::ShapeError::InvalidParameter {
operation: crate::shapes::error::OperationKind::Reshape,
parameter: "inferred dimensions",
value: 2,
});
}
*inferred = Some(index);
sizes.push(0);
}
T::collect(sizes, inferred)
}
}
impl<In: Shape, Target: ReshapeTargetSpec> ReshapeTarget<In> for Target {
type Output = Target::Output;
fn calculate_shape(
in_shape_vec: &[usize],
) -> core::result::Result<Vec<usize>, crate::shapes::error::ShapeError> {
let total_elements = crate::shapes::ShapeBuf::from_slice(in_shape_vec)
.checked_numel(crate::shapes::error::OperationKind::Reshape)?;
let mut sizes = Vec::new();
let mut inferred = None;
Target::collect(&mut sizes, &mut inferred)?;
if let Some(index) = inferred {
let known_product = sizes
.iter()
.enumerate()
.filter(|(i, _)| *i != index)
.try_fold(1usize, |product, (_, &size)| product.checked_mul(size))
.ok_or(crate::shapes::error::ShapeError::ArithmeticOverflow {
operation: crate::shapes::error::OperationKind::Reshape,
expression: "product of specified reshape dimensions",
})?;
if known_product == 0 {
sizes[index] = 0;
} else if !total_elements.is_multiple_of(known_product) {
return Err(crate::shapes::error::ShapeError::DimensionMismatch {
operation: crate::shapes::error::OperationKind::Reshape,
axis: crate::shapes::error::Axis::Index(index),
lhs: total_elements,
rhs: known_product,
constraint: crate::shapes::error::DimensionConstraint::DivisibleBy,
});
} else {
sizes[index] = total_elements / known_product;
}
}
Ok(sizes)
}
}
pub trait SliceIdx {
type Resolved: Dim;
fn bounds(size: usize) -> (usize, usize);
}
impl<Start: Unsigned, End: Unsigned, Diff: Dim> SliceIdx for Slice<Start, End, Diff> {
type Resolved = Diff;
fn bounds(_size: usize) -> (usize, usize) {
(Start::USIZE, End::USIZE)
}
}
impl SliceIdx for UTerm {
type Resolved = U1;
fn bounds(_size: usize) -> (usize, usize) {
(0, 1)
}
}
impl<U, B> SliceIdx for UInt<U, B>
where
U: Unsigned + Dim,
B: Bit + Default + Copy + Clone + core::fmt::Debug + Send + Sync + Eq + PartialEq + 'static,
UInt<U, B>: Unsigned
+ Default
+ Copy
+ Clone
+ core::fmt::Debug
+ Send
+ Sync
+ Eq
+ PartialEq
+ 'static,
{
type Resolved = U1;
fn bounds(_size: usize) -> (usize, usize) {
(Self::USIZE, Self::USIZE + 1)
}
}
impl SliceIdx for Ellipsis {
type Resolved = usize;
fn bounds(size: usize) -> (usize, usize) {
(0, size)
}
}
#[diagnostic::on_unimplemented(
message = "Cannot slice dimension with `{Self}`",
label = "Invalid slice target",
note = "The slice range must be within the bounds of the original dimension"
)]
pub trait SliceTarget<In: Shape> {
type Output: Shape;
fn calculate_bounds(in_shape_vec: &[usize]) -> Vec<(usize, usize)>;
}
#[doc(hidden)]
pub trait SliceSpec {
type Output: Shape;
fn collect(input: &[usize], axis: &mut usize, output: &mut Vec<(usize, usize)>);
}
impl SliceSpec for Nil {
type Output = Nil;
fn collect(_input: &[usize], _axis: &mut usize, _output: &mut Vec<(usize, usize)>) {}
}
impl<D: SliceIdx, T: SliceSpec> SliceSpec for DimCons<D, T>
where
D::Resolved: Dim,
{
type Output = DimCons<D::Resolved, T::Output>;
fn collect(input: &[usize], axis: &mut usize, output: &mut Vec<(usize, usize)>) {
let size = input.get(*axis).copied().unwrap_or(0);
output.push(D::bounds(size));
*axis += 1;
T::collect(input, axis, output);
}
}
impl<In: Shape, Target: SliceSpec> SliceTarget<In> for Target {
type Output = Target::Output;
fn calculate_bounds(in_shape_vec: &[usize]) -> Vec<(usize, usize)> {
let mut bounds = Vec::new();
let mut axis = 0;
Target::collect(in_shape_vec, &mut axis, &mut bounds);
bounds
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Hash)]
pub struct Here;
impl Here {
pub fn normalize(&self, rank: usize) -> crate::err::Result<Vec<usize>> {
AxisSelector::new(&[0]).normalize(rank)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Hash)]
pub struct Next<I>(pub core::marker::PhantomData<I>);
impl<I> Next<I> {
pub const DEFAULT: Self = Next(core::marker::PhantomData);
pub fn normalize(&self, rank: usize) -> crate::err::Result<Vec<usize>>
where
Self: StaticCursor,
{
AxisSelector::new(&[<Next<I> as StaticCursor>::INDEX]).normalize(rank)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Hash)]
pub struct FromEnd<I>(pub core::marker::PhantomData<I>);
impl<I> FromEnd<I> {
pub const DEFAULT: Self = FromEnd(core::marker::PhantomData);
}
impl<I: StaticCursor> FromEnd<I> {
pub const INDEX: isize = -(1 + I::INDEX);
pub fn normalize(&self, rank: usize) -> crate::err::Result<Vec<usize>> {
AxisSelector::new(&[Self::INDEX]).normalize(rank)
}
}
pub trait StaticCursor:
'static + Copy + Clone + core::fmt::Debug + Send + Sync + Eq + PartialEq
{
const INDEX: isize;
}
pub trait AxisCursor:
'static + Copy + Clone + core::fmt::Debug + Send + Sync + Eq + PartialEq
{
const INDEX: isize;
}
impl<I: StaticCursor> AxisCursor for I {
const INDEX: isize = I::INDEX;
}
impl<I: StaticCursor> AxisCursor for FromEnd<I> {
const INDEX: isize = FromEnd::<I>::INDEX;
}
impl StaticCursor for Here {
const INDEX: isize = 0;
}
impl<I: StaticCursor> StaticCursor for Next<I> {
const INDEX: isize = 1 + I::INDEX;
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
pub struct StaticAxis<I: StaticCursor>(core::marker::PhantomData<I>);
impl<I: StaticCursor> StaticAxis<I> {
pub const DEFAULT: Self = Self(core::marker::PhantomData);
pub fn normalize(&self, rank: usize) -> crate::err::Result<Vec<usize>> {
AxisSelector::new(&[I::INDEX]).normalize(rank)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Hash)]
pub struct ForwardAxis<I: crate::shapes::shape::ForwardCursor>(core::marker::PhantomData<I>);
impl<I: crate::shapes::shape::ForwardCursor> ForwardAxis<I> {
pub const DEFAULT: Self = ForwardAxis(core::marker::PhantomData);
pub fn normalize(&self, rank: usize) -> crate::err::Result<Vec<usize>> {
AxisSelector::new(&[I::INDEX]).normalize(rank)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Hash)]
pub struct ReverseAxis<I: StaticCursor>(core::marker::PhantomData<I>);
impl<I: StaticCursor> ReverseAxis<I> {
pub const DEFAULT: Self = ReverseAxis(core::marker::PhantomData);
pub fn normalize(&self, rank: usize) -> crate::err::Result<Vec<usize>> {
AxisSelector::new(&[FromEnd::<I>::INDEX]).normalize(rank)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct NamedAxisSelector<Tag: crate::shapes::AxisTag>(core::marker::PhantomData<Tag>);
impl<Tag: crate::shapes::AxisTag> Default for NamedAxisSelector<Tag> {
fn default() -> Self {
Self(core::marker::PhantomData)
}
}
impl<Tag: crate::shapes::AxisTag> NamedAxisSelector<Tag> {
pub fn resolve<S>(&self) -> crate::err::Result<usize>
where
S: NamedAxisLookup<Tag>,
{
S::lookup_named().map_err(crate::err::Error::Shape)
}
}
pub trait NamedAxisLookup<Tag: crate::shapes::AxisTag>: Shape {
fn lookup_named() -> core::result::Result<usize, crate::shapes::ShapeError>;
}
trait NamedAxisMetadata {
fn collect_named<Tag: crate::shapes::AxisTag>(offset: usize, matches: &mut Vec<usize>);
}
impl NamedAxisMetadata for Nil {
fn collect_named<Tag: crate::shapes::AxisTag>(_: usize, _: &mut Vec<usize>) {}
}
impl<H: Dim, T: Shape + NamedAxisMetadata> NamedAxisMetadata for DimCons<H, T> {
fn collect_named<Tag: crate::shapes::AxisTag>(offset: usize, matches: &mut Vec<usize>) {
if H::matches_tag::<Tag>() {
matches.push(offset);
}
T::collect_named::<Tag>(offset + 1, matches);
}
}
impl<Tag: crate::shapes::AxisTag, S: Shape + NamedAxisMetadata> NamedAxisLookup<Tag> for S {
fn lookup_named() -> core::result::Result<usize, crate::shapes::ShapeError> {
let mut matches = Vec::new();
S::collect_named::<Tag>(0, &mut matches);
match matches.as_slice() {
[] => Err(crate::shapes::ShapeError::MissingNamedAxis { name: Tag::NAME }),
[index] => Ok(*index),
_ => Err(crate::shapes::ShapeError::AmbiguousNamedAxis { name: Tag::NAME }),
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct AxisSelector {
pub raw_axes: Vec<isize>,
}
impl AxisSelector {
pub fn new(axes: &[isize]) -> Self {
Self {
raw_axes: axes.to_vec(),
}
}
pub fn normalize(&self, rank: usize) -> crate::err::Result<Vec<usize>> {
let mut normalized = Vec::with_capacity(self.raw_axes.len());
for &raw in &self.raw_axes {
let norm = if raw >= 0 {
let u = raw as usize;
if u >= rank {
return Err(crate::err::Error::Shape(
crate::shapes::error::ShapeError::InvalidAxis { axis: u, rank },
));
}
u
} else {
let neg = raw.unsigned_abs();
if neg > rank {
return Err(crate::err::Error::Shape(
crate::shapes::error::ShapeError::InvalidAxis { axis: rank, rank },
));
}
rank - neg
};
if normalized.contains(&norm) {
return Err(crate::err::Error::Shape(
crate::shapes::error::ShapeError::DuplicateAxis { axis: norm },
));
}
normalized.push(norm);
}
Ok(normalized)
}
pub fn normalize_unsigned(axis: usize, rank: usize) -> crate::err::Result<usize> {
if axis >= rank {
return Err(crate::err::Error::Shape(
crate::shapes::error::ShapeError::InvalidAxis { axis, rank },
));
}
Ok(axis)
}
}
pub trait ToAxisIndex {
fn to_axis_index(&self) -> isize;
}
impl ToAxisIndex for isize {
fn to_axis_index(&self) -> isize {
*self
}
}
impl ToAxisIndex for i32 {
fn to_axis_index(&self) -> isize {
*self as isize
}
}
impl ToAxisIndex for Here {
fn to_axis_index(&self) -> isize {
<Here as StaticCursor>::INDEX
}
}
impl<I: StaticCursor> ToAxisIndex for Next<I> {
fn to_axis_index(&self) -> isize {
<Next<I> as StaticCursor>::INDEX
}
}
impl<I: StaticCursor> ToAxisIndex for FromEnd<I> {
fn to_axis_index(&self) -> isize {
FromEnd::<I>::INDEX
}
}
impl<I: StaticCursor> ToAxisIndex for StaticAxis<I> {
fn to_axis_index(&self) -> isize {
I::INDEX
}
}
impl<I: crate::shapes::shape::ForwardCursor> ToAxisIndex for ForwardAxis<I> {
fn to_axis_index(&self) -> isize {
I::INDEX
}
}
impl<I: StaticCursor> ToAxisIndex for ReverseAxis<I> {
fn to_axis_index(&self) -> isize {
FromEnd::<I>::INDEX
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::shapes::{DimCons, Nil, Shape};
use typenum::{U0, U1, U2, U3, U4};
trait Same<T> {}
impl<T> Same<T> for T {}
fn assert_shape_eq<S1: Shape, S2: Shape>()
where
S1: Same<S2>,
{
}
#[test]
fn slice_range_output_shape() {
type Input = DimCons<U4, DimCons<U4, DimCons<U3, Nil>>>;
type IdxT = DimCons<Slice<U1, U3, U2>, DimCons<Ellipsis, DimCons<Slice<U0, U2, U2>, Nil>>>;
type Expected = DimCons<U2, DimCons<usize, DimCons<U2, Nil>>>;
assert_shape_eq::<<IdxT as SliceTarget<Input>>::Output, Expected>();
}
#[test]
fn slice_full_passthrough() {
type Input = DimCons<U4, DimCons<U4, DimCons<U3, Nil>>>;
type IdxT = DimCons<Ellipsis, DimCons<Ellipsis, DimCons<Ellipsis, Nil>>>;
type Expected = DimCons<usize, DimCons<usize, DimCons<usize, Nil>>>;
assert_shape_eq::<<IdxT as SliceTarget<Input>>::Output, Expected>();
}
}