use alloc::vec::Vec;
use core::fmt;
use core::ops::Deref;
use super::error::{OperationKind, RankExpectation, ShapeError};
pub const INLINE_RANK: usize = 8;
#[derive(Clone)]
pub(crate) struct InlineOrHeap<T: Copy + Default> {
repr: Repr<T>,
}
#[derive(Clone)]
enum Repr<T: Copy + Default> {
Inline { len: usize, items: [T; INLINE_RANK] },
Heap(Vec<T>),
}
impl InlineOrHeap<usize> {
pub const EMPTY: Self = Self {
repr: Repr::Inline {
len: 0,
items: [0; INLINE_RANK],
},
};
}
impl<T: Copy + Default> InlineOrHeap<T> {
#[must_use]
pub fn new() -> Self {
Self {
repr: Repr::Inline {
len: 0,
items: [T::default(); INLINE_RANK],
},
}
}
#[must_use]
pub fn from_slice(items: &[T]) -> Self {
if items.len() <= INLINE_RANK {
let mut inline = [T::default(); INLINE_RANK];
inline[..items.len()].copy_from_slice(items);
Self {
repr: Repr::Inline {
len: items.len(),
items: inline,
},
}
} else {
Self {
repr: Repr::Heap(items.to_vec()),
}
}
}
#[must_use]
pub fn as_slice(&self) -> &[T] {
match &self.repr {
Repr::Inline { len, items } => &items[..*len],
Repr::Heap(v) => v.as_slice(),
}
}
pub fn as_mut_slice(&mut self) -> &mut [T] {
match &mut self.repr {
Repr::Inline { len, items } => &mut items[..*len],
Repr::Heap(v) => v.as_mut_slice(),
}
}
#[must_use]
pub fn len(&self) -> usize {
self.as_slice().len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
#[must_use]
pub fn is_inline(&self) -> bool {
matches!(self.repr, Repr::Inline { .. })
}
pub fn push(&mut self, value: T) {
match &mut self.repr {
Repr::Inline { len, items } if *len < INLINE_RANK => {
items[*len] = value;
*len += 1;
}
Repr::Inline { len, items } => {
let mut heap = Vec::with_capacity(*len + 1);
heap.extend_from_slice(&items[..*len]);
heap.push(value);
self.repr = Repr::Heap(heap);
}
Repr::Heap(v) => v.push(value),
}
}
pub fn pop(&mut self) -> Option<T> {
match &mut self.repr {
Repr::Inline { len, items } => {
if *len == 0 {
None
} else {
*len -= 1;
Some(items[*len])
}
}
Repr::Heap(v) => v.pop(),
}
}
}
impl<T: Copy + Default> Default for InlineOrHeap<T> {
fn default() -> Self {
Self::new()
}
}
impl<T: Copy + Default> Deref for InlineOrHeap<T> {
type Target = [T];
fn deref(&self) -> &[T] {
self.as_slice()
}
}
impl<T: Copy + Default + PartialEq> PartialEq for InlineOrHeap<T> {
fn eq(&self, other: &Self) -> bool {
self.as_slice() == other.as_slice()
}
}
impl<T: Copy + Default + Eq> Eq for InlineOrHeap<T> {}
impl<T: Copy + Default + fmt::Debug> fmt::Debug for InlineOrHeap<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
fmt::Debug::fmt(self.as_slice(), f)
}
}
impl<T: Copy + Default> FromIterator<T> for InlineOrHeap<T> {
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
let mut out = Self::new();
for item in iter {
out.push(item);
}
out
}
}
#[derive(Clone, PartialEq, Eq, Default)]
pub struct ShapeBuf {
dims: InlineOrHeap<usize>,
}
impl ShapeBuf {
pub const SCALAR: Self = Self {
dims: InlineOrHeap::EMPTY,
};
#[must_use]
pub fn scalar() -> Self {
Self {
dims: InlineOrHeap::new(),
}
}
#[must_use]
pub fn from_slice(dims: &[usize]) -> Self {
Self {
dims: InlineOrHeap::from_slice(dims),
}
}
#[must_use]
pub fn dims(&self) -> &[usize] {
self.dims.as_slice()
}
pub fn dims_mut(&mut self) -> &mut [usize] {
self.dims.as_mut_slice()
}
#[must_use]
pub fn rank(&self) -> usize {
self.dims.len()
}
#[must_use]
pub fn is_inline(&self) -> bool {
self.dims.is_inline()
}
pub fn push(&mut self, dim: usize) {
self.dims.push(dim);
}
pub fn pop(&mut self) -> Option<usize> {
self.dims.pop()
}
pub fn numel(&self) -> Option<usize> {
if self.is_empty_tensor() {
return Some(0);
}
self.dims()
.iter()
.try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
}
pub fn checked_numel(&self, operation: OperationKind) -> Result<usize, ShapeError> {
self.numel().ok_or(ShapeError::ArithmeticOverflow {
operation,
expression: "product of dimensions",
})
}
pub fn checked_byte_len(
&self,
element_size: usize,
operation: OperationKind,
) -> Result<usize, ShapeError> {
self.checked_numel(operation)?
.checked_mul(element_size)
.ok_or(ShapeError::ArithmeticOverflow {
operation,
expression: "element count * element size",
})
}
#[must_use]
pub fn is_empty_tensor(&self) -> bool {
self.dims().contains(&0)
}
}
impl serde::Serialize for ShapeBuf {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: serde::Serializer,
{
self.dims().serialize(serializer)
}
}
impl<'de> serde::Deserialize<'de> for ShapeBuf {
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: serde::Deserializer<'de>,
{
let dims = alloc::vec::Vec::<usize>::deserialize(deserializer)?;
Ok(Self::from_slice(&dims))
}
}
impl PartialEq<Vec<usize>> for ShapeBuf {
fn eq(&self, other: &Vec<usize>) -> bool {
self.dims() == other.as_slice()
}
}
impl PartialEq<&[usize]> for ShapeBuf {
fn eq(&self, other: &&[usize]) -> bool {
self.dims() == *other
}
}
impl<const N: usize> PartialEq<[usize; N]> for ShapeBuf {
fn eq(&self, other: &[usize; N]) -> bool {
self.dims() == other.as_slice()
}
}
impl Deref for ShapeBuf {
type Target = [usize];
fn deref(&self) -> &[usize] {
self.dims()
}
}
impl fmt::Debug for ShapeBuf {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
fmt::Debug::fmt(self.dims(), f)
}
}
impl From<&[usize]> for ShapeBuf {
fn from(dims: &[usize]) -> Self {
Self::from_slice(dims)
}
}
impl FromIterator<usize> for ShapeBuf {
fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self {
Self {
dims: iter.into_iter().collect(),
}
}
}
impl AsRef<[usize]> for ShapeBuf {
fn as_ref(&self) -> &[usize] {
self.dims()
}
}
impl AsMut<[usize]> for ShapeBuf {
fn as_mut(&mut self) -> &mut [usize] {
self.dims_mut()
}
}
impl<I: core::slice::SliceIndex<[usize]>> core::ops::Index<I> for ShapeBuf {
type Output = I::Output;
fn index(&self, index: I) -> &Self::Output {
&self.dims()[index]
}
}
impl<I: core::slice::SliceIndex<[usize]>> core::ops::IndexMut<I> for ShapeBuf {
fn index_mut(&mut self, index: I) -> &mut Self::Output {
&mut self.dims_mut()[index]
}
}
impl From<ShapeBuf> for Vec<usize> {
fn from(buf: ShapeBuf) -> Self {
buf.dims().to_vec()
}
}
impl IntoIterator for ShapeBuf {
type Item = usize;
type IntoIter = alloc::vec::IntoIter<usize>;
fn into_iter(self) -> Self::IntoIter {
self.dims().to_vec().into_iter()
}
}
impl<'a> IntoIterator for &'a ShapeBuf {
type Item = &'a usize;
type IntoIter = core::slice::Iter<'a, usize>;
fn into_iter(self) -> Self::IntoIter {
self.dims().iter()
}
}
#[derive(Clone, PartialEq, Eq, Default)]
pub struct StrideBuf {
strides: InlineOrHeap<usize>,
}
impl StrideBuf {
pub const EMPTY: Self = Self {
strides: InlineOrHeap::EMPTY,
};
#[must_use]
pub fn from_slice(strides: &[usize]) -> Self {
Self {
strides: InlineOrHeap::from_slice(strides),
}
}
#[must_use]
pub fn strides(&self) -> &[usize] {
self.strides.as_slice()
}
#[must_use]
pub fn len(&self) -> usize {
self.strides.len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.strides.is_empty()
}
#[must_use]
pub fn is_inline(&self) -> bool {
self.strides.is_inline()
}
pub fn push(&mut self, stride: usize) {
self.strides.push(stride);
}
pub fn pop(&mut self) -> Option<usize> {
self.strides.pop()
}
pub fn contiguous_for(shape: &ShapeBuf, operation: OperationKind) -> Result<Self, ShapeError> {
let dims = shape.dims();
let mut strides = InlineOrHeap::from_slice(&[]);
for _ in dims {
strides.push(1usize);
}
let slice = strides.as_mut_slice();
for axis in (0..dims.len().saturating_sub(1)).rev() {
slice[axis] = slice[axis + 1].checked_mul(dims[axis + 1]).ok_or(
ShapeError::ArithmeticOverflow {
operation,
expression: "stride * trailing dimension",
},
)?;
}
Ok(Self { strides })
}
#[must_use]
pub fn is_contiguous_for(&self, shape: &ShapeBuf) -> bool {
Self::contiguous_for(shape, OperationKind::Storage).is_ok_and(|expected| expected == *self)
}
pub fn checked_span(
&self,
shape: &ShapeBuf,
operation: OperationKind,
) -> Result<usize, ShapeError> {
if self.len() != shape.rank() {
return Err(ShapeError::RankMismatch {
operation,
expected: RankExpectation::SameAs {
operand: "shape",
rank: shape.rank(),
},
actual: self.len(),
});
}
if shape.is_empty_tensor() {
return Ok(0);
}
let mut span = 1usize;
for (&dim, &stride) in shape.dims().iter().zip(self.strides()) {
let extent = (dim - 1).checked_mul(stride).ok_or({
ShapeError::ArithmeticOverflow {
operation,
expression: "(dimension - 1) * stride",
}
})?;
span = span
.checked_add(extent)
.ok_or(ShapeError::ArithmeticOverflow {
operation,
expression: "sum of axis extents",
})?;
}
Ok(span)
}
}
impl PartialEq<Vec<usize>> for StrideBuf {
fn eq(&self, other: &Vec<usize>) -> bool {
self.strides() == other.as_slice()
}
}
impl Deref for StrideBuf {
type Target = [usize];
fn deref(&self) -> &[usize] {
self.strides()
}
}
impl fmt::Debug for StrideBuf {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
fmt::Debug::fmt(self.strides(), f)
}
}
impl From<&[usize]> for StrideBuf {
fn from(strides: &[usize]) -> Self {
Self::from_slice(strides)
}
}
impl FromIterator<usize> for StrideBuf {
fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self {
Self {
strides: iter.into_iter().collect(),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn checked_numel_distinguishes_scalar_zero_and_overflow() {
assert_eq!(
ShapeBuf::scalar()
.checked_numel(OperationKind::Storage)
.unwrap(),
1
);
assert_eq!(
ShapeBuf::from_slice(&[usize::MAX, 0, usize::MAX])
.checked_numel(OperationKind::Storage)
.unwrap(),
0
);
assert!(matches!(
ShapeBuf::from_slice(&[usize::MAX, 2]).checked_numel(OperationKind::Storage),
Err(ShapeError::ArithmeticOverflow { .. })
));
}
#[test]
fn contiguous_strides_reject_unrepresentable_layouts_even_when_empty() {
let overflowing = ShapeBuf::from_slice(&[2, usize::MAX, usize::MAX]);
assert!(matches!(
StrideBuf::contiguous_for(&overflowing, OperationKind::Storage),
Err(ShapeError::ArithmeticOverflow { .. })
));
let empty = ShapeBuf::from_slice(&[0, usize::MAX, usize::MAX]);
assert!(matches!(
StrideBuf::contiguous_for(&empty, OperationKind::Storage),
Err(ShapeError::ArithmeticOverflow { .. })
));
}
#[test]
fn checked_span_rejects_rank_and_arithmetic_overflow() {
let shape = ShapeBuf::from_slice(&[2, 2]);
assert!(matches!(
StrideBuf::from_slice(&[1]).checked_span(&shape, OperationKind::Slice),
Err(ShapeError::RankMismatch { .. })
));
assert!(matches!(
StrideBuf::from_slice(&[usize::MAX, usize::MAX])
.checked_span(&shape, OperationKind::Slice),
Err(ShapeError::ArithmeticOverflow { .. })
));
}
}