use std::{collections::HashSet, fmt::Write, sync::Arc};
use malachite::{Natural, base::num::basic::traits::One};
use crate::{
ast,
dice::Pool,
error::{NonAdditiveSubject, NonAdditiveSumError, RuntimeError, ShapeMismatchError},
};
#[derive(Debug, Clone, Default)]
pub struct SymbolTable {
names: Vec<String>,
declared: HashSet<String>,
}
impl SymbolTable {
pub(crate) fn contains(&self, name: &str) -> bool {
self.declared.contains(name)
}
pub(crate) fn define(&mut self, name: String) -> u32 {
let symbol = u32::try_from(self.names.len()).expect("symbol count fits in u32");
assert!(
self.declared.insert(name.clone()),
"symbol is declared once"
);
self.names.push(name);
symbol
}
pub fn name(&self, symbol: u32) -> &str {
self.names
.get(usize::try_from(symbol).expect("symbol index fits in usize"))
.map(String::as_str)
.unwrap_or("<?>")
}
}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum ElementValue {
AdditiveIdentity,
Int(i32),
Symbol(u32),
Tuple(Arc<[ElementValue]>),
}
impl ElementValue {
pub fn as_int(&self) -> Option<i32> {
match self {
ElementValue::Int(value) => Some(*value),
ElementValue::AdditiveIdentity | ElementValue::Symbol(_) | ElementValue::Tuple(_) => {
None
}
}
}
pub(crate) fn as_int_or_identity(&self) -> Option<i32> {
match self {
ElementValue::AdditiveIdentity => Some(0),
other => other.as_int(),
}
}
pub(crate) fn is_additive(&self) -> bool {
match self {
ElementValue::AdditiveIdentity | ElementValue::Int(_) => true,
ElementValue::Symbol(_) => false,
ElementValue::Tuple(fields) => fields.iter().all(ElementValue::is_additive),
}
}
pub(crate) fn additive_identity(&self) -> Option<ElementValue> {
match self {
ElementValue::AdditiveIdentity => Some(ElementValue::AdditiveIdentity),
ElementValue::Int(_) => Some(ElementValue::Int(0)),
ElementValue::Symbol(_) => None,
ElementValue::Tuple(fields) => fields
.iter()
.map(ElementValue::additive_identity)
.collect::<Option<Vec<_>>>()
.map(|fields| ElementValue::Tuple(fields.into())),
}
}
pub(crate) fn add_scaled(&self, other: &Self, count: u32) -> Result<Self, ElementMismatch> {
match (self, other) {
(ElementValue::AdditiveIdentity, ElementValue::AdditiveIdentity) => {
Ok(ElementValue::AdditiveIdentity)
}
(ElementValue::AdditiveIdentity, other) => other
.additive_identity()
.ok_or_else(|| ElementMismatch::not_numeric(other))?
.add_scaled(other, count),
(other, ElementValue::AdditiveIdentity) => Ok(other.clone()),
(ElementValue::Int(left), ElementValue::Int(right)) => {
let count = i32::try_from(count).expect("pool dimension fits in i32");
Ok(ElementValue::Int(left + right * count))
}
(ElementValue::Tuple(left), ElementValue::Tuple(right))
if left.len() == right.len() =>
{
left.iter()
.zip(right.iter())
.map(|(left, right)| left.add_scaled(right, count))
.collect::<Result<Vec<_>, _>>()
.map(|fields| ElementValue::Tuple(fields.into()))
.map_err(|inner| match inner.kind() {
Mismatch::NotNumeric { .. } if !other.is_additive() => {
ElementMismatch::not_numeric(other)
}
Mismatch::NotNumeric { .. } => ElementMismatch::not_numeric(self),
Mismatch::Shapes { .. } => inner,
})
}
(_, right) if !right.is_additive() => Err(ElementMismatch::not_numeric(right)),
(left, _) if !left.is_additive() => Err(ElementMismatch::not_numeric(left)),
(left, right) => Err(ElementMismatch::shapes(left, right)),
}
}
pub(crate) fn try_map_ints(
&self,
f: &impl Fn(i32) -> Result<i32, String>,
) -> Result<Self, ElementOpError> {
match self {
ElementValue::AdditiveIdentity => Ok(ElementValue::AdditiveIdentity),
ElementValue::Int(value) => Ok(ElementValue::Int(f(*value)?)),
ElementValue::Tuple(fields) => Ok(ElementValue::Tuple(
fields
.iter()
.map(|field| field.try_map_ints(f))
.collect::<Result<Vec<_>, _>>()?
.into(),
)),
ElementValue::Symbol(_) => Err(ElementMismatch::not_numeric(self).into()),
}
}
pub(crate) fn try_zip_ints(
&self,
other: &Self,
f: &impl Fn(i32, i32) -> Result<i32, String>,
) -> Result<Self, ElementOpError> {
match (self, other) {
(ElementValue::AdditiveIdentity, ElementValue::AdditiveIdentity) => {
Ok(ElementValue::AdditiveIdentity)
}
(ElementValue::Int(left), ElementValue::Int(right)) => {
Ok(ElementValue::Int(f(*left, *right)?))
}
(ElementValue::Tuple(left), ElementValue::Tuple(right))
if left.len() == right.len() =>
{
Ok(ElementValue::Tuple(
left.iter()
.zip(right.iter())
.map(|(left, right)| left.try_zip_ints(right, f))
.collect::<Result<Vec<_>, _>>()?
.into(),
))
}
(_, right) if !right.is_additive() => Err(ElementMismatch::not_numeric(right).into()),
(left, _) if !left.is_additive() => Err(ElementMismatch::not_numeric(left).into()),
(left, right) => Err(ElementMismatch::shapes(left, right).into()),
}
}
pub(crate) fn checked_neg(&self) -> Result<Self, ElementOpError> {
self.try_map_ints(&|value| {
value
.checked_neg()
.ok_or_else(|| format!("Negation overflow: -{value}"))
})
}
pub(crate) fn materialize_identity_like(&self, like: &ElementValue) -> ElementValue {
match self {
ElementValue::AdditiveIdentity => like
.additive_identity()
.unwrap_or(ElementValue::AdditiveIdentity),
other => other.clone(),
}
}
pub(crate) fn equals_with_identity(&self, other: &Self) -> bool {
match (self, other) {
(ElementValue::AdditiveIdentity, other) | (other, ElementValue::AdditiveIdentity) => {
other.additive_identity().as_ref() == Some(other)
|| matches!(other, ElementValue::AdditiveIdentity)
}
(left, right) => left == right,
}
}
}
#[derive(Debug, Clone)]
pub(crate) struct ElementMismatch(Box<Mismatch>);
#[derive(Debug, Clone)]
pub(crate) enum Mismatch {
NotNumeric {
witness: ElementValue,
field: Option<usize>,
},
Shapes {
left: ElementValue,
right: ElementValue,
},
}
impl ElementMismatch {
pub(crate) fn not_numeric(witness: &ElementValue) -> Self {
ElementMismatch(Box::new(Mismatch::NotNumeric {
witness: witness.clone(),
field: non_numeric_field(witness),
}))
}
pub(crate) fn shapes(left: &ElementValue, right: &ElementValue) -> Self {
ElementMismatch(Box::new(Mismatch::Shapes {
left: left.clone(),
right: right.clone(),
}))
}
pub(crate) fn kind(&self) -> &Mismatch {
&self.0
}
pub(crate) fn into_error(
self,
range: ast::ByteRange,
action: &'static str,
subject: NonAdditiveSubject,
) -> RuntimeError {
match *self.0 {
Mismatch::NotNumeric { witness, field } => {
RuntimeError::NonAdditiveSum(Box::new(NonAdditiveSumError {
range,
action,
subject,
witness: Some(witness),
field,
}))
}
Mismatch::Shapes { left, right } => {
RuntimeError::ShapeMismatch(Box::new(ShapeMismatchError {
range,
action,
first: left,
second: right,
}))
}
}
}
}
#[derive(Debug, Clone)]
pub(crate) enum ElementOpError {
Math(String),
Mismatch(ElementMismatch),
}
impl From<String> for ElementOpError {
fn from(message: String) -> Self {
ElementOpError::Math(message)
}
}
impl From<ElementMismatch> for ElementOpError {
fn from(mismatch: ElementMismatch) -> Self {
ElementOpError::Mismatch(mismatch)
}
}
pub struct Displayed<'a, T> {
value: &'a T,
symbols: &'a SymbolTable,
}
impl ElementValue {
pub fn display<'a>(&'a self, symbols: &'a SymbolTable) -> Displayed<'a, Self> {
Displayed {
value: self,
symbols,
}
}
}
impl std::fmt::Display for Displayed<'_, ElementValue> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self.value {
ElementValue::AdditiveIdentity => write!(f, "\u{1d452}"),
ElementValue::Int(value) => write!(f, "{value}"),
ElementValue::Symbol(symbol) => write!(f, "{}", self.symbols.name(*symbol)),
ElementValue::Tuple(fields) => write!(
f,
"({})",
fields
.iter()
.map(|field| field.display(self.symbols).to_string())
.collect::<Vec<_>>()
.join(", ")
),
}
}
}
#[derive(Debug, Clone, PartialEq)]
pub enum RuntimeValue {
Element(ElementValue),
List(Arc<Vec<ElementValue>>),
Pool(Arc<Pool<ElementValue>>),
}
impl RuntimeValue {
pub fn display<'a>(&'a self, symbols: &'a SymbolTable) -> Displayed<'a, Self> {
Displayed {
value: self,
symbols,
}
}
}
impl std::fmt::Display for Displayed<'_, RuntimeValue> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self.value {
RuntimeValue::Element(value) => write!(f, "{}", value.display(self.symbols)),
RuntimeValue::List(list) => write!(
f,
"{{{}}}",
list.iter()
.map(|value| value.display(self.symbols).to_string())
.collect::<Vec<_>>()
.join(", ")
),
RuntimeValue::Pool(pool) => {
write!(f, "{}", display_pool(pool, self.symbols))
}
}
}
}
fn display_pool(pool: &Pool<ElementValue>, symbols: &SymbolTable) -> String {
if pool.ordered_outcomes().is_empty() {
return "d{}".to_string();
}
let mut f = String::new();
if pool.dimension() != 1 {
write!(f, "{}", pool.dimension()).expect("write to string");
}
if pool.ordered_outcomes() == [(ElementValue::Int(0), Natural::ONE)] {
write!(f, "d0").expect("write to string");
return f;
}
if pool
.ordered_outcomes()
.iter()
.enumerate()
.all(|(i, (outcome, weight))| {
outcome
.as_int()
.and_then(|outcome| usize::try_from(outcome).ok())
== Some(i + 1)
&& *weight == Natural::ONE
})
{
write!(f, "d{}", pool.ordered_outcomes().len()).expect("write to string");
} else {
write!(
f,
"d{{{}}}",
pool.ordered_outcomes()
.iter()
.map(|(outcome, weight)| if weight == &Natural::ONE {
outcome.display(symbols).to_string()
} else {
format!("{}:{}", outcome.display(symbols), weight)
})
.collect::<Vec<_>>()
.join(", ")
)
.expect("write to string");
}
f
}
impl RuntimeValue {
pub(crate) fn empty_list() -> Self {
RuntimeValue::List(Arc::new(Vec::new()))
}
pub(crate) fn empty_pool() -> Self {
RuntimeValue::Pool(Arc::new(Pool::from_list(1, Vec::new())))
}
pub(crate) fn elements(&self) -> &[ElementValue] {
match self {
RuntimeValue::Element(value) => std::slice::from_ref(value),
RuntimeValue::List(list) => list,
RuntimeValue::Pool(_) => &[],
}
}
pub(crate) fn non_numeric(&self) -> Option<&ElementValue> {
match self {
RuntimeValue::Element(value) => (value.as_int_or_identity().is_none()).then_some(value),
RuntimeValue::List(list) => list
.iter()
.find(|value| value.as_int_or_identity().is_none()),
RuntimeValue::Pool(pool) => pool
.ordered_outcomes()
.iter()
.map(|(outcome, _)| outcome)
.find(|outcome| outcome.as_int_or_identity().is_none()),
}
}
pub(crate) fn to_list(&self, repeat: usize) -> Result<Vec<ElementValue>, ElementMismatch> {
match self {
RuntimeValue::Element(value) => Ok(vec![value.clone(); repeat]),
RuntimeValue::List(list) => {
Ok((0..repeat).flat_map(|_| list.iter().cloned()).collect())
}
RuntimeValue::Pool(pool) if pool.ordered_outcomes().is_empty() => Ok(Vec::new()),
RuntimeValue::Pool(pool) => {
let outcomes = sum_pool(pool)
.map_err(|failure| failure.mismatch)?
.ordered_outcomes()
.iter()
.map(|(outcome, _)| outcome)
.cloned()
.collect::<Vec<_>>();
Ok((0..repeat).flat_map(|_| outcomes.iter().cloned()).collect())
}
}
}
pub(crate) fn map_numeric_outcomes(
&self,
f: impl Fn(i32) -> i32 + Copy,
) -> Result<Self, ElementMismatch> {
let number = |value: &ElementValue| {
value
.as_int_or_identity()
.ok_or_else(|| ElementMismatch::not_numeric(value))
};
match self {
RuntimeValue::Element(value) => Ok(f(number(value)?).into()),
RuntimeValue::List(list) => {
let sum: i32 = list
.iter()
.map(number)
.collect::<Result<Vec<_>, _>>()?
.iter()
.sum();
Ok(f(sum).into())
}
RuntimeValue::Pool(pool) => Ok(RuntimeValue::Pool(Arc::new(
sum_pool(pool)
.map_err(|failure| failure.mismatch)?
.try_map_outcomes(|outcome| {
number(&outcome).map(|value| ElementValue::Int(f(value)))
})?,
))),
}
}
pub(crate) fn to_pool(&self) -> Result<Pool<ElementValue>, ElementMismatch> {
match self {
RuntimeValue::Element(value) => Ok(Pool::from_list(1, vec![value.clone()])),
RuntimeValue::List(list) => Ok(Pool::from_list(1, vec![sum_elements(list)?])),
RuntimeValue::Pool(pool) => Ok((**pool).clone()),
}
}
}
pub(crate) fn materialize_comparable_pair(
left: &RuntimeValue,
right: &RuntimeValue,
) -> (RuntimeValue, RuntimeValue) {
let sample = |value: &RuntimeValue| match value {
RuntimeValue::Pool(pool) => pool
.ordered_outcomes()
.iter()
.map(|(outcome, _)| outcome)
.find(|outcome| !matches!(outcome, ElementValue::AdditiveIdentity))
.cloned(),
value => value
.elements()
.iter()
.find(|value| !matches!(value, ElementValue::AdditiveIdentity))
.cloned(),
};
let Some(zero) = sample(left)
.or_else(|| sample(right))
.and_then(|value| value.additive_identity())
.filter(|zero| !matches!(zero, ElementValue::AdditiveIdentity))
else {
return (left.clone(), right.clone());
};
let materialize = |value: &RuntimeValue| {
let swap = |element: &ElementValue| match element {
ElementValue::AdditiveIdentity => zero.clone(),
other => other.clone(),
};
match value {
RuntimeValue::Element(element) => RuntimeValue::Element(swap(element)),
RuntimeValue::List(list) => {
RuntimeValue::List(Arc::new(list.iter().map(swap).collect()))
}
RuntimeValue::Pool(pool) => RuntimeValue::Pool(Arc::new(
(**pool).clone().map_outcomes(|outcome| swap(&outcome)),
)),
}
};
(materialize(left), materialize(right))
}
pub(crate) fn sum_elements(values: &[ElementValue]) -> Result<ElementValue, ElementMismatch> {
values
.iter()
.try_fold(ElementValue::AdditiveIdentity, |sum, value| {
sum.add_scaled(value, 1)
})
}
#[derive(Debug, Clone)]
pub(crate) struct PoolSumFailure {
dimension: u32,
mismatch: ElementMismatch,
}
impl PoolSumFailure {
pub(crate) fn into_error(self, range: ast::ByteRange, action: &'static str) -> RuntimeError {
self.mismatch
.into_error(range, action, NonAdditiveSubject::Pool(self.dimension))
}
}
pub(crate) fn non_numeric_field(value: &ElementValue) -> Option<usize> {
match value {
ElementValue::Tuple(fields) => fields
.iter()
.position(|field| field.as_int().is_none())
.map(|index| index + 1),
_ => None,
}
}
pub(crate) fn display_requires_summing(pool: &Pool<ElementValue>) -> bool {
!pool.ordered_outcomes().is_empty()
}
pub(crate) fn sum_pool(pool: &Pool<ElementValue>) -> Result<Pool<ElementValue>, PoolSumFailure> {
if pool.dimension() == 1 && !pool.ordered_outcomes().is_empty() {
return Ok(pool.clone());
}
let identity = pool
.ordered_outcomes()
.first()
.and_then(|(outcome, _)| outcome.additive_identity())
.unwrap_or(ElementValue::AdditiveIdentity);
pool.try_sum_by(identity, ElementValue::add_scaled)
.map_err(|mismatch| PoolSumFailure {
dimension: pool.dimension(),
mismatch,
})
}
impl From<i32> for RuntimeValue {
fn from(value: i32) -> Self {
RuntimeValue::Element(ElementValue::Int(value))
}
}
impl From<Arc<Vec<i32>>> for RuntimeValue {
fn from(value: Arc<Vec<i32>>) -> Self {
RuntimeValue::List(Arc::new(
value.iter().copied().map(ElementValue::Int).collect(),
))
}
}
impl From<Vec<i32>> for RuntimeValue {
fn from(value: Vec<i32>) -> Self {
RuntimeValue::List(Arc::new(value.into_iter().map(ElementValue::Int).collect()))
}
}
impl From<Pool> for RuntimeValue {
fn from(value: Pool) -> Self {
RuntimeValue::Pool(Arc::new(value.map_outcomes(ElementValue::Int)))
}
}
#[cfg(test)]
mod tests {
use super::*;
pub(crate) fn attack_result() -> SymbolTable {
let mut symbols = SymbolTable::default();
symbols.define("MISS".to_string());
symbols.define("HIT".to_string());
symbols
}
fn enum_value(index: u32) -> ElementValue {
ElementValue::Symbol(index)
}
fn enum_pool(dimension: u32, members: &[u32]) -> Pool<ElementValue> {
Pool::from_list(
dimension,
members.iter().copied().map(enum_value).collect::<Vec<_>>(),
)
}
#[test]
fn summing_a_multidimensional_non_additive_pool_is_an_error() {
let error =
sum_pool(&enum_pool(2, &[0, 1])).expect_err("two enum dice cannot be added together");
assert_eq!(error.dimension, 2);
}
#[test]
fn rolling_no_dice_sums_to_the_empty_sum() {
let summed = sum_pool(&enum_pool(0, &[0, 1])).expect("no dice, nothing to add");
assert_eq!(
summed.ordered_outcomes(),
[(ElementValue::AdditiveIdentity, Natural::ONE)]
);
}
#[test]
fn a_single_non_additive_die_is_returned_unchanged() {
let one_die = enum_pool(1, &[0, 1]);
assert_eq!(sum_pool(&one_die).unwrap(), one_die);
}
#[test]
fn a_pool_with_no_faces_sums_to_the_empty_sum() {
for dimension in [0, 1, 2] {
assert_eq!(
sum_pool(&enum_pool(dimension, &[]))
.unwrap()
.ordered_outcomes(),
[(ElementValue::AdditiveIdentity, Natural::ONE)],
"dimension {dimension}"
);
}
}
#[test]
fn summing_additive_pools_is_unaffected() {
let ints = Pool::from_list(2, vec![ElementValue::Int(1), ElementValue::Int(2)]);
let summed = sum_pool(&ints).unwrap();
assert_eq!(summed.dimension(), 1);
assert_eq!(
summed
.ordered_outcomes()
.iter()
.map(|(outcome, _)| outcome.clone())
.collect::<Vec<_>>(),
vec![
ElementValue::Int(2),
ElementValue::Int(3),
ElementValue::Int(4)
]
);
let pair =
|a, b| ElementValue::Tuple(vec![ElementValue::Int(a), ElementValue::Int(b)].into());
let tuples = Pool::from_list(2, vec![pair(1, 10), pair(2, 20)]);
let summed = sum_pool(&tuples).unwrap();
assert_eq!(summed.dimension(), 1);
assert_eq!(
summed
.ordered_outcomes()
.iter()
.map(|(outcome, _)| outcome.clone())
.collect::<Vec<_>>(),
vec![pair(2, 20), pair(3, 30), pair(4, 40)]
);
}
#[test]
fn enum_multisets_are_ordered_by_declaration() {
let multisets = enum_pool(2, &[0, 1])
.multiset_iterator()
.collect::<Vec<_>>();
assert_eq!(
multisets,
vec![
(vec![enum_value(0), enum_value(0)], Natural::ONE),
(vec![enum_value(0), enum_value(1)], Natural::from(2u32)),
(vec![enum_value(1), enum_value(1)], Natural::ONE),
]
);
}
#[test]
fn a_non_additive_sum_error_carries_an_offending_outcome() {
let error = sum_pool(&enum_pool(2, &[0, 1]))
.unwrap_err()
.into_error((0, 1).into(), "displaying a pool");
let RuntimeError::NonAdditiveSum(error) = error else {
panic!("expected a non-additive sum error");
};
assert!(matches!(error.subject, NonAdditiveSubject::Pool(2)));
assert_eq!(error.witness, Some(ElementValue::Symbol(0)));
assert_eq!(error.field, None);
}
#[test]
fn a_non_additive_tuple_sum_names_the_offending_field() {
let outcome = ElementValue::Tuple(
vec![
ElementValue::Int(1),
ElementValue::Int(2),
ElementValue::Symbol(0),
]
.into(),
);
let pool = Pool::from_list(2, vec![outcome.clone()]);
let error = sum_pool(&pool)
.unwrap_err()
.into_error((0, 1).into(), "displaying a pool");
let RuntimeError::NonAdditiveSum(error) = error else {
panic!("expected a non-additive sum error");
};
assert_eq!(error.witness, Some(outcome));
assert_eq!(error.field, Some(3));
}
fn pair(a: i32, b: i32) -> ElementValue {
ElementValue::Tuple(vec![ElementValue::Int(a), ElementValue::Int(b)].into())
}
#[test]
fn adding_values_of_different_shapes_reports_both() {
let triple = ElementValue::Tuple(
vec![
ElementValue::Int(1),
ElementValue::Int(2),
ElementValue::Int(3),
]
.into(),
);
for (left, right) in [
(pair(1, 2), triple.clone()),
(pair(1, 2), ElementValue::Int(7)),
(ElementValue::Int(7), pair(1, 2)),
] {
let failure = left
.add_scaled(&right, 1)
.expect_err("shapes that do not line up cannot be added");
let Mismatch::Shapes { .. } = failure.kind() else {
panic!("expected a shape mismatch, got {failure:?}");
};
}
assert_eq!(pair(1, 2).add_scaled(&pair(3, 4), 1).unwrap(), pair(4, 6));
}
#[test]
fn adding_a_non_numeric_value_reports_it() {
let mixed = ElementValue::Tuple(vec![ElementValue::Int(1), ElementValue::Symbol(0)].into());
assert!(!mixed.is_additive());
assert_eq!(mixed.additive_identity(), None);
let failure = pair(1, 2)
.add_scaled(&mixed, 1)
.expect_err("a tuple holding a symbol cannot be added");
let Mismatch::NotNumeric { witness, field } = failure.kind() else {
panic!("expected a non-numeric mismatch, got {failure:?}");
};
assert_eq!(witness, &mixed);
assert_eq!(field, &Some(2));
}
#[test]
fn the_empty_sum_takes_the_shape_it_meets() {
assert_eq!(sum_elements(&[]).unwrap(), ElementValue::AdditiveIdentity);
assert_eq!(sum_elements(&[pair(1, 2), pair(3, 4)]).unwrap(), pair(4, 6));
let identity = ElementValue::AdditiveIdentity;
assert!(identity.equals_with_identity(&ElementValue::Int(0)));
assert!(identity.equals_with_identity(&pair(0, 0)));
assert!(!identity.equals_with_identity(&ElementValue::Int(1)));
assert!(!identity.equals_with_identity(&pair(0, 1)));
assert!(!identity.equals_with_identity(&ElementValue::Symbol(0)));
}
#[test]
fn symbols_are_named_by_the_table() {
let symbols = attack_result();
assert_eq!(enum_value(1).display(&symbols).to_string(), "HIT");
assert_eq!(symbols.name(0), "MISS");
}
}