use alloc::{
format,
string::{
String,
ToString,
},
vec,
vec::Vec,
};
use core::{
fmt::{
Display,
Formatter,
},
panic::Location,
};
use crate::contracts::{
StackEnvironment,
expressions::{
DimExpr,
ExprDisplayAdapter,
MatchResult,
},
shape_view::ShapeView,
};
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum DimMatcher<'a> {
Any {
label_id: Option<usize>,
},
Ellipsis {
label_id: Option<usize>,
},
Expr {
label_id: Option<usize>,
expr: DimExpr<'a>,
},
}
impl<'a> DimMatcher<'a> {
pub const fn any() -> Self {
DimMatcher::Any { label_id: None }
}
pub const fn ellipsis() -> Self {
DimMatcher::Ellipsis { label_id: None }
}
pub const fn expr(expr: DimExpr<'a>) -> Self {
DimMatcher::Expr {
label_id: None,
expr,
}
}
pub const fn label_id(&self) -> Option<usize> {
match self {
DimMatcher::Any { label_id } => *label_id,
DimMatcher::Ellipsis { label_id } => *label_id,
DimMatcher::Expr { label_id, .. } => *label_id,
}
}
pub const fn with_label_id(
self,
label_id: Option<usize>,
) -> Self {
match self {
DimMatcher::Any { .. } => DimMatcher::Any { label_id },
DimMatcher::Ellipsis { .. } => DimMatcher::Ellipsis { label_id },
DimMatcher::Expr { expr, .. } => DimMatcher::Expr { label_id, expr },
}
}
}
pub struct MatcherDisplayAdapter<'a> {
index: &'a [&'a str],
matcher: &'a DimMatcher<'a>,
}
impl<'a> Display for MatcherDisplayAdapter<'a> {
fn fmt(
&self,
f: &mut Formatter<'_>,
) -> core::fmt::Result {
if let Some(label_id) = self.matcher.label_id() {
write!(f, "{}=", self.index[label_id])?;
}
match self.matcher {
DimMatcher::Any { .. } => write!(f, "_"),
DimMatcher::Ellipsis { .. } => write!(f, "..."),
DimMatcher::Expr { expr, .. } => write!(
f,
"{}",
ExprDisplayAdapter {
index: self.index,
expr
}
),
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ShapeContract<'a> {
pub index: &'a [&'a str],
pub terms: &'a [DimMatcher<'a>],
pub ellipsis_pos: Option<usize>,
}
impl Display for ShapeContract<'_> {
fn fmt(
&self,
f: &mut Formatter<'_>,
) -> core::fmt::Result {
write!(f, "[")?;
for (idx, term) in self.terms.iter().enumerate() {
if idx > 0 {
write!(f, ", ")?;
}
write!(
f,
"{}",
MatcherDisplayAdapter {
index: self.index,
matcher: term
}
)?;
}
write!(f, "]")
}
}
impl<'a> ShapeContract<'a> {
pub const fn new(
index: &'a [&'a str],
terms: &'a [DimMatcher<'a>],
) -> Self {
let mut i = 0;
let mut ellipsis_pos: Option<usize> = None;
while i < terms.len() {
if let DimMatcher::Ellipsis { label_id } = &terms[i] {
if label_id.is_some() {
panic!("Labelled ellipsis in pattern");
}
match ellipsis_pos {
Some(_) => panic!("Multiple ellipses in pattern"),
None => ellipsis_pos = Some(i),
}
}
i += 1;
}
ShapeContract {
index,
terms,
ellipsis_pos,
}
}
pub fn maybe_key_to_index(
&self,
key: &str,
) -> Option<usize> {
self.index.iter().position(|&s| s == key)
}
#[track_caller]
pub fn assert_shape<'b, S>(
&'a self,
shape: S,
env: StackEnvironment<'a>,
) where
S: Into<ShapeView<'b>>,
{
let shape = shape.into();
match self._loc_try_assert_shape(&shape, env, Location::caller()) {
Ok(()) => (),
Err(msg) => panic!("{}", msg),
}
}
#[track_caller]
pub fn try_assert_shape<'b, S>(
&'a self,
shape: S,
env: StackEnvironment<'a>,
) -> Result<(), String>
where
S: Into<ShapeView<'b>>,
{
let sv = shape.into();
self._loc_try_assert_shape(&sv, env, Location::caller())
}
fn _key_index(
&'a self,
env: StackEnvironment<'a>,
) -> Result<Vec<Option<isize>>, String> {
let mut key_index: Vec<Option<isize>> = vec![None; self.index.len()];
for (k, v) in env.iter() {
let v = *v as isize;
match self.maybe_key_to_index(k) {
Some(param_id) => key_index[param_id] = Some(v),
None => {
return Err(
format!("The key \"{k}\" is not indexed in the contract:\n{self}")
.to_string(),
);
}
}
}
Ok(key_index)
}
fn _loc_try_assert_shape(
&'a self,
shape: &ShapeView,
env: StackEnvironment<'a>,
loc: &Location<'a>,
) -> Result<(), String> {
let mut key_index = self._key_index(env)?;
self.format_resolve(shape, key_index.as_mut_slice(), loc)
}
#[must_use]
#[track_caller]
pub fn unpack_shape<'b, S, const K: usize>(
&'a self,
shape: S,
keys: &[&'a str; K],
env: StackEnvironment<'a>,
) -> [usize; K]
where
S: Into<ShapeView<'b>>,
{
let sv: ShapeView = shape.into();
self._loc_unpack_shape(&sv, keys, env, Location::caller())
}
fn _loc_unpack_shape<const K: usize>(
&'a self,
shape: &ShapeView,
keys: &[&'a str; K],
env: StackEnvironment<'a>,
loc: &Location<'a>,
) -> [usize; K] {
match self._loc_try_unpack_shape(shape, keys, env, loc) {
Ok(values) => values,
Err(msg) => panic!("{msg}"),
}
}
#[track_caller]
pub fn try_unpack_shape<'b, S, const K: usize>(
&'a self,
shape: S,
keys: &[&'a str; K],
env: StackEnvironment<'a>,
) -> Result<[usize; K], String>
where
S: Into<ShapeView<'b>>,
{
let sv: ShapeView = shape.into();
self._loc_try_unpack_shape(&sv, keys, env, Location::caller())
}
fn _loc_try_unpack_shape<const K: usize>(
&'a self,
shape: &ShapeView,
keys: &[&'a str; K],
env: StackEnvironment<'a>,
loc: &Location<'a>,
) -> Result<[usize; K], String> {
let selection = self.expect_keys_to_selection(keys);
let mut key_index = self._key_index(env)?;
let selected: [isize; K] =
self._loc_try_select(shape, &selection, key_index.as_mut_slice(), loc)?;
let result: [usize; K] = selected
.into_iter()
.map(|v| v as usize)
.collect::<Vec<usize>>()
.try_into()
.unwrap();
Ok(result)
}
pub fn expect_keys_to_selection<const D: usize>(
&'a self,
keys: &[&'a str; D],
) -> [usize; D] {
let mut selection = [0; D];
for (i, key) in keys.iter().enumerate() {
match self.maybe_key_to_index(key) {
Some(param_id) => selection[i] = param_id,
None => panic!("The key \"{key}\" is not indexed in the contract:\n{self}"),
}
}
selection
}
fn _loc_try_select<const K: usize>(
&'a self,
shape: &ShapeView,
selection: &[usize; K],
env: &mut [Option<isize>],
loc: &Location<'a>,
) -> Result<[isize; K], String> {
let num_slots = self.index.len();
assert_eq!(env.len(), num_slots);
self.format_resolve(shape, env, loc)?;
let mut out = [0; K];
for (i, &k) in selection.iter().enumerate() {
out[i] = env[k].unwrap();
}
Ok(out)
}
pub(crate) fn format_resolve(
&'a self,
shape: &ShapeView,
env: &mut [Option<isize>],
location: &Location,
) -> Result<(), String> {
match self._resolve(shape.as_ref(), env) {
Ok(()) => Ok(()),
Err(msg) => Err(format!(
"at {file}:{line}: Shape Error\n {msg}\nActual:\n {shape:?}\nContract:\n {self}\nBindings:\n {{{}}}",
self.index
.iter()
.zip(env.iter())
.filter(|(_, v)| v.is_some())
.map(|(k, v)| format!("\"{}\": {}", *k, v.unwrap()))
.collect::<Vec<_>>()
.join(", "),
file = location.file(),
line = location.line(),
shape = shape.as_ref(),
)),
}
}
#[doc(hidden)]
pub fn _resolve(
&'a self,
shape: &[usize],
env: &mut [Option<isize>],
) -> Result<(), String> {
let rank = shape.len();
let fail_at = |shape_idx: usize, term_idx: usize, msg: &str| -> String {
format!(
"{} !~ {} :: {msg}",
shape[shape_idx],
MatcherDisplayAdapter {
index: self.index,
matcher: &self.terms[term_idx]
}
)
};
let (e_start, e_size) = match self.try_ellipsis_split(rank) {
Ok((e_start, e_size)) => (e_start, e_size),
Err(msg) => return Err(msg),
};
for (shape_idx, &dim_size) in shape.iter().enumerate() {
let dim_size = dim_size as isize;
let term_idx = if shape_idx < e_start {
shape_idx
} else if shape_idx < (e_start + e_size) {
continue;
} else {
shape_idx + 1 - e_size
};
let matcher = &self.terms[term_idx];
if let Some(label_id) = matcher.label_id() {
match env[label_id] {
Some(value) => {
if value != dim_size {
return Err(fail_at(shape_idx, term_idx, "Value MissMatch."));
}
}
None => {
env[label_id] = Some(dim_size);
}
}
}
let expr = match matcher {
DimMatcher::Any { .. } => continue,
DimMatcher::Expr { expr, .. } => expr,
DimMatcher::Ellipsis { .. } => {
unreachable!("Ellipsis should have been handled before")
}
};
match expr.try_match(dim_size, env) {
Ok(MatchResult::Match) => continue,
Ok(MatchResult::Conflict) => {
return Err(fail_at(shape_idx, term_idx, "Value MissMatch."));
}
Ok(MatchResult::ParamConstraint { id, value }) => {
if value < 0 {
return Err(fail_at(shape_idx, term_idx, "Negative solution."));
}
env[id] = Some(value);
}
Err(msg) => return Err(fail_at(shape_idx, term_idx, msg)),
}
}
Ok(())
}
fn try_ellipsis_split(
&self,
rank: usize,
) -> Result<(usize, usize), String> {
let k = self.terms.len();
match self.ellipsis_pos {
None => {
if rank != k {
Err(format!("Shape rank {rank} != pattern dim count {k}",))
} else {
Ok((k, 0))
}
}
Some(pos) => {
let non_ellipsis_terms = k - 1;
if rank < non_ellipsis_terms {
return Err(format!(
"Shape rank {rank} < non-ellipsis pattern term count {non_ellipsis_terms}",
));
}
Ok((pos, rank - non_ellipsis_terms))
}
}
}
}
#[cfg(test)]
mod tests {
use indoc::indoc;
use super::*;
use crate::contracts::{
DimExpr,
assert_shape_contract,
shape_contract,
};
static WINDOWS: ShapeContract = shape_contract![
...,
"height" = "h_wins" * "window",
"width" = "w_wins" * "window",
"color",
];
fn reason(msg: String) -> String {
msg.lines().nth(1).unwrap().trim().to_string()
}
#[test]
fn test_error_message_format() {
let err = WINDOWS
.try_unpack_shape(
&[1usize, 2, 3, 8, 12, 3],
&["h_wins", "w_wins"],
&[("window", 5), ("color", 3)],
)
.unwrap_err();
let (location, body) = err.split_once('\n').unwrap();
assert!(
location.starts_with(&format!("at {}:", file!())),
"{location}"
);
assert!(location.ends_with(": Shape Error"), "{location}");
assert_eq!(
body,
indoc! {r#"
8 !~ height=(h_wins*window) :: No integer solution.
Actual:
[1, 2, 3, 8, 12, 3]
Contract:
[..., height=(h_wins*window), width=(w_wins*window), color]
Bindings:
{"color": 3, "height": 8, "window": 5}"#
},
);
}
#[test]
fn test_error_reasons() {
static PAIRS: ShapeContract = shape_contract!["n" = 2 * "k", "n"];
static BACKWARD: ShapeContract = shape_contract!["a" * "b", "a"];
fn fail(
contract: &ShapeContract,
shape: &[usize],
env: StackEnvironment,
) -> String {
reason(contract.try_assert_shape(shape, env).unwrap_err())
}
assert_eq!(fail(&PAIRS, &[6, 5], &[]), "5 !~ n :: Value MissMatch.");
assert_eq!(
fail(&PAIRS, &[6, 6], &[("n", 4)]),
"6 !~ n=(2*k) :: Value MissMatch."
);
assert_eq!(
fail(&PAIRS, &[7, 7], &[]),
"7 !~ n=(2*k) :: No integer solution."
);
assert_eq!(
fail(&BACKWARD, &[12, 4], &[]),
"12 !~ (a*b) :: Too many unbound params."
);
assert_eq!(
fail(&PAIRS, &[6], &[]),
"Shape rank 1 != pattern dim count 2"
);
assert_eq!(
fail(&WINDOWS, &[8, 12], &[]),
"Shape rank 2 < non-ellipsis pattern term count 3"
);
}
#[test]
fn test_unknown_binding_key() {
let err = WINDOWS
.try_assert_shape(&[8usize, 12, 3], &[("nope", 1)])
.unwrap_err();
assert_eq!(
err,
"The key \"nope\" is not indexed in the contract:\n\
[..., height=(h_wins*window), width=(w_wins*window), color]"
);
}
#[test]
#[should_panic(expected = "The key \"nope\" is not indexed in the contract:")]
fn test_unknown_unpack_key_panics_in_try() {
let _ = WINDOWS.try_unpack_shape(&[8usize, 12, 3], &["nope"], &[]);
}
#[test]
#[should_panic(expected = "Labelled ellipsis in pattern")]
fn test_new_rejects_labelled_ellipsis() {
let terms = [
DimMatcher::ellipsis().with_label_id(Some(0)),
DimMatcher::expr(DimExpr::Param { id: 1 }),
];
let contract = ShapeContract::new(&["rest", "x"], &terms);
let _ = contract.try_unpack_shape(&[2usize, 3, 4], &["rest"], &[]);
}
#[test]
fn test_zero_factor_fails_without_panicking() {
static CONTRACT: ShapeContract = shape_contract!["b", "b" * "t"];
fn fail(shape: &[usize]) -> String {
reason(CONTRACT.try_assert_shape(shape, &[]).unwrap_err())
}
assert_eq!(fail(&[0, 0]), "0 !~ (b*t) :: No unique solution.");
assert_eq!(fail(&[0, 3]), "3 !~ (b*t) :: No integer solution.");
assert_eq!(
CONTRACT.unpack_shape(&[0usize, 0], &["b", "t"], &[("t", 4)]),
[0, 4]
);
}
#[test]
fn test_negative_solution_is_an_error() {
static SUM: ShapeContract = shape_contract!["a", "a" + "b"];
let err = SUM
.try_unpack_shape(&[5usize, 3], &["a", "b"], &[])
.unwrap_err();
assert_eq!(reason(err), "3 !~ (a+b) :: Negative solution.");
assert_eq!(SUM.unpack_shape(&[5usize, 8], &["a", "b"], &[]), [5, 3]);
static NEG_SQUARE: ShapeContract = shape_contract![-"x" ^ 2];
let err = NEG_SQUARE
.try_unpack_shape(&[9usize], &["x"], &[])
.unwrap_err();
assert_eq!(reason(err), "9 !~ ((-x)^2) :: Negative solution.");
}
#[test]
fn test_macro_failure_location_is_the_call() {
use std::panic::catch_unwind;
let line = line!() + 1;
let r = catch_unwind(|| assert_shape_contract!(["a"], &[2usize], &[("a", 3)]));
let payload = r.unwrap_err();
let msg = payload.downcast_ref::<String>().unwrap();
assert!(
msg.starts_with(&format!("at {}:{line}: Shape Error", file!())),
"{msg}"
);
}
#[test]
fn test_unpack_shape() {
static CONTRACT: ShapeContract = ShapeContract::new(
&["b", "h", "w", "p", "z", "c"],
&[
DimMatcher::any(),
DimMatcher::expr(DimExpr::Param { id: 0 }),
DimMatcher::ellipsis(),
DimMatcher::expr(DimExpr::Prod {
children: &[DimExpr::Param { id: 1 }, DimExpr::Param { id: 3 }],
}),
DimMatcher::expr(DimExpr::Prod {
children: &[DimExpr::Param { id: 2 }, DimExpr::Param { id: 3 }],
}),
DimMatcher::expr(DimExpr::Pow {
base: &DimExpr::Param { id: 4 },
exp: 3,
}),
DimMatcher::expr(DimExpr::Param { id: 5 }),
],
);
let b = 2;
let h = 3;
let w = 2;
let p = 4;
let c = 5;
let z = 4;
let shape = [12, b, 1, 2, 3, h * p, w * p, z * z * z, c];
let env = [("p", p), ("c", c)];
CONTRACT.assert_shape(&shape, &env);
let [u_b, u_h, u_w, u_z] = CONTRACT.unpack_shape(&shape, &["b", "h", "w", "z"], &env);
assert_eq!(u_b, b);
assert_eq!(u_h, h);
assert_eq!(u_w, w);
assert_eq!(u_z, z);
}
#[test]
fn test_shape_contract_macro_const() {
use crate::contracts::shape_contract;
static CONTRACT: ShapeContract = shape_contract!["b", 3, 2 * "h" + 1];
let b = 2;
let h = 5;
let shape = [b, 3, 2 * h + 1];
CONTRACT.assert_shape(&shape, &[]);
let [u_b, u_h] = CONTRACT.unpack_shape(&shape, &["b", "h"], &[]);
assert_eq!(u_b, b);
assert_eq!(u_h, h);
}
}