simplicity/

value.rs

// SPDX-License-Identifier: CC0-1.0

//! # Simplicity values
//!
//! Simplicity processes data in terms of [`Value`]s,
//! i.e., inputs, intermediate results and outputs.

use crate::dag::{Dag, DagLike, NoSharing};
use crate::types::Final;

use crate::{types, EarlyEndOfStreamError};
use std::collections::VecDeque;
use std::fmt;
use std::hash::Hash;
use std::sync::Arc;

/// A Simplicity value.
#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct Value {
    inner: ValueInner,
    ty: Arc<Final>,
}

/// The inner structure of a Simplicity value.
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
enum ValueInner {
    /// The unit value.
    ///
    /// The unit value is the only value of the unit type `1`.
    /// It must be wrapped in left and right values to encode information.
    Unit,
    /// A left value.
    ///
    /// A left value wraps a value of type `A` and its type is the sum `A + B` for some `B`.
    /// A `false` bit encodes that a left value is wrapped.
    Left(Arc<Value>),
    /// A right value.
    ///
    /// A right value wraps a value of type `B` and its type is the sum `A + B` for some `A`.
    /// A `true` bit encodes that a right value is wrapped.
    Right(Arc<Value>),
    /// A product value.
    ///
    /// A product value wraps a left value of type `A` and a right value of type `B`,
    /// and its type is the product `A × B`.
    /// A product value combines the information of its inner values.
    Product(Arc<Value>, Arc<Value>),
}

impl<'a> DagLike for &'a Value {
    type Node = Value;

    fn data(&self) -> &Value {
        self
    }

    fn as_dag_node(&self) -> Dag<Self> {
        match &self.inner {
            ValueInner::Unit => Dag::Nullary,
            ValueInner::Left(child) | ValueInner::Right(child) => Dag::Unary(child),
            ValueInner::Product(left, right) => Dag::Binary(left, right),
        }
    }
}

impl Value {
    /// Make a cheap copy of the value.
    pub fn shallow_clone(&self) -> Self {
        Self {
            inner: self.inner.clone(),
            ty: Arc::clone(&self.ty),
        }
    }

    /// Access the type of the value.
    pub fn ty(&self) -> &Final {
        &self.ty
    }

    /// Create the unit value.
    pub fn unit() -> Self {
        Self {
            inner: ValueInner::Unit,
            ty: Final::unit(),
        }
    }

    /// Create a left value that wraps the given `inner` value.
    pub fn left(inner: Self, right: Arc<Final>) -> Self {
        Self {
            ty: Final::sum(Arc::clone(&inner.ty), right),
            inner: ValueInner::Left(Arc::new(inner)),
        }
    }

    /// Create a right value that wraps the given `inner` value.
    pub fn right(left: Arc<Final>, inner: Self) -> Self {
        Self {
            ty: Final::sum(left, Arc::clone(&inner.ty)),
            inner: ValueInner::Right(Arc::new(inner)),
        }
    }

    /// Create a product value that wraps the given `left` and `right` values.
    pub fn product(left: Self, right: Self) -> Self {
        Self {
            ty: Final::product(Arc::clone(&left.ty), Arc::clone(&right.ty)),
            inner: ValueInner::Product(Arc::new(left), Arc::new(right)),
        }
    }

    /// Create a none value.
    pub fn none(right: Arc<Final>) -> Self {
        Self {
            ty: Final::sum(Final::unit(), right),
            inner: ValueInner::Left(Arc::new(Value::unit())),
        }
    }

    /// Create a some value.
    pub fn some(inner: Self) -> Self {
        Self {
            ty: Final::sum(Final::unit(), Arc::clone(&inner.ty)),
            inner: ValueInner::Right(Arc::new(inner)),
        }
    }

    /// Return the bit length of the value in compact encoding.
    pub fn compact_len(&self) -> usize {
        self.iter_compact().count()
    }

    /// Return the bit length of the value in padded encoding.
    pub fn padded_len(&self) -> usize {
        self.iter_padded().count()
    }

    /// Check if the value is a nested product of units.
    /// In this case, the value contains no information.
    pub fn is_empty(&self) -> bool {
        self.pre_order_iter::<NoSharing>()
            .all(|value| matches!(&value.inner, ValueInner::Unit | ValueInner::Product(..)))
    }

    /// Check if the value is a unit.
    pub fn is_unit(&self) -> bool {
        matches!(&self.inner, ValueInner::Unit)
    }

    /// Access the inner value of a left sum value.
    pub fn as_left(&self) -> Option<&Self> {
        match &self.inner {
            ValueInner::Left(inner) => Some(inner.as_ref()),
            _ => None,
        }
    }

    /// Access the inner value of a right sum value.
    pub fn as_right(&self) -> Option<&Self> {
        match &self.inner {
            ValueInner::Right(inner) => Some(inner.as_ref()),
            _ => None,
        }
    }

    /// Access the inner values of a product value.
    pub fn as_product(&self) -> Option<(&Self, &Self)> {
        match &self.inner {
            ValueInner::Product(left, right) => Some((left.as_ref(), right.as_ref())),
            _ => None,
        }
    }

    /// Create a 1-bit integer.
    ///
    /// ## Panics
    ///
    /// The value is out of range.
    pub fn u1(value: u8) -> Self {
        match value {
            0 => Self::left(Self::unit(), Final::unit()),
            1 => Self::right(Final::unit(), Self::unit()),
            x => panic!("{} out of range for Value::u1", x),
        }
    }

    /// Create a 2-bit integer.
    ///
    /// ## Panics
    ///
    /// The value is out of range.
    pub fn u2(value: u8) -> Self {
        let b0 = (value & 2) / 2;
        let b1 = value & 1;
        assert!(value <= 3, "{} out of range for Value::u2", value);
        Self::product(Self::u1(b0), Self::u1(b1))
    }

    /// Create a 4-bit integer.
    ///
    /// ## Panics
    ///
    /// The value is ouf of range.
    pub fn u4(value: u8) -> Self {
        let w0 = (value & 12) / 4;
        let w1 = value & 3;
        assert!(value <= 15, "{} out of range for Value::u2", value);
        Self::product(Self::u2(w0), Self::u2(w1))
    }

    /// Create an 8-bit integer.
    pub fn u8(value: u8) -> Self {
        let w0 = value >> 4;
        let w1 = value & 0xf;
        Self::product(Self::u4(w0), Self::u4(w1))
    }

    /// Create a 16-bit integer.
    pub fn u16(bytes: u16) -> Self {
        Self::from_byte_array(bytes.to_be_bytes())
    }

    /// Create a 32-bit integer.
    pub fn u32(bytes: u32) -> Self {
        Self::from_byte_array(bytes.to_be_bytes())
    }

    /// Create a 64-bit integer.
    pub fn u64(bytes: u64) -> Self {
        Self::from_byte_array(bytes.to_be_bytes())
    }

    /// Create a 128-bit integer.
    pub fn u128(bytes: u128) -> Self {
        Self::from_byte_array(bytes.to_be_bytes())
    }

    /// Create a 256-bit integer.
    pub fn u256(bytes: [u8; 32]) -> Self {
        Self::from_byte_array(bytes)
    }

    /// Create a 512-bit integer.
    pub fn u512(bytes: [u8; 64]) -> Self {
        Self::from_byte_array(bytes)
    }

    /// Create a value from a byte array.
    ///
    /// ## Panics
    ///
    /// The array length is not a power of two.
    pub fn from_byte_array<const N: usize>(bytes: [u8; N]) -> Self {
        assert!(N.is_power_of_two(), "Array length must be a power of two");
        let mut values: VecDeque<_> = bytes.into_iter().map(Value::u8).collect();

        while values.len() > 1 {
            let mut alt_values = VecDeque::with_capacity(values.len() / 2);

            while let (Some(left), Some(right)) = (values.pop_front(), values.pop_front()) {
                alt_values.push_back(Value::product(left, right));
            }

            values = alt_values;
        }

        values.into_iter().next().unwrap()
    }

    /// Return an iterator over the compact bit encoding of the value.
    ///
    /// This encoding is used for writing witness data and for computing IMRs.
    pub fn iter_compact(&self) -> impl Iterator<Item = bool> + '_ {
        self.pre_order_iter::<NoSharing>()
            .filter_map(|value| match &value.inner {
                ValueInner::Left(..) => Some(false),
                ValueInner::Right(..) => Some(true),
                _ => None,
            })
    }

    /// Return an iterator over the padded bit encoding of the value.
    ///
    /// This encoding is used to represent the value in the Bit Machine.
    pub fn iter_padded(&self) -> impl Iterator<Item = bool> + '_ {
        PaddedBitsIter::new(self)
    }

    /// Check if the value is of the given type.
    pub fn is_of_type(&self, ty: &Final) -> bool {
        self.ty.as_ref() == ty
    }
}

impl fmt::Debug for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        fmt::Display::fmt(self, f)
    }
}

impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for data in self.verbose_pre_order_iter::<NoSharing>(None) {
            match &data.node.inner {
                ValueInner::Unit => {
                    if data.n_children_yielded == 0
                        && !matches!(
                            data.parent.map(|value| &value.inner),
                            Some(ValueInner::Left(_)) | Some(ValueInner::Right(_))
                        )
                    {
                        f.write_str("ε")?;
                    }
                }
                ValueInner::Left(..) => {
                    if data.n_children_yielded == 0 {
                        f.write_str("0")?;
                    }
                }
                ValueInner::Right(..) => {
                    if data.n_children_yielded == 0 {
                        f.write_str("1")?;
                    }
                }
                ValueInner::Product(..) => match data.n_children_yielded {
                    0 => f.write_str("(")?,
                    1 => f.write_str(",")?,
                    2 => f.write_str(")")?,
                    _ => unreachable!(),
                },
            }
        }
        Ok(())
    }
}

/// An iterator over the bits of the padded encoding of a [`Value`].
#[derive(Debug, Clone, Eq, PartialEq, Hash)]
struct PaddedBitsIter<'a> {
    stack: Vec<&'a Value>,
    next_padding: Option<usize>,
}

impl<'a> PaddedBitsIter<'a> {
    /// Create an iterator over the bits of the padded encoding of the `value`.
    pub fn new(value: &'a Value) -> Self {
        Self {
            stack: vec![value],
            next_padding: None,
        }
    }
}

impl<'a> Iterator for PaddedBitsIter<'a> {
    type Item = bool;

    fn next(&mut self) -> Option<Self::Item> {
        match self.next_padding {
            Some(0) => {
                self.next_padding = None;
            }
            Some(n) => {
                self.next_padding = Some(n - 1);
                return Some(false);
            }
            None => {}
        }

        while let Some(value) = self.stack.pop() {
            if value.is_unit() {
                // NOP
            } else if let Some(l_value) = value.as_left() {
                let (l_ty, r_ty) = value.ty.as_sum().unwrap();
                self.stack.push(l_value);
                self.next_padding = Some(l_ty.pad_left(r_ty));
                return Some(false);
            } else if let Some(r_value) = value.as_right() {
                let (l_ty, r_ty) = value.ty.as_sum().unwrap();
                self.stack.push(r_value);
                self.next_padding = Some(l_ty.pad_right(r_ty));
                return Some(true);
            } else if let Some((l_value, r_value)) = value.as_product() {
                self.stack.push(r_value);
                self.stack.push(l_value);
            }
        }

        None
    }
}

trait Padding {
    fn read_left_padding<I: Iterator<Item = bool>>(
        bits: &mut I,
        ty_l: &Final,
        ty_r: &Final,
    ) -> Result<(), EarlyEndOfStreamError>;

    fn read_right_padding<I: Iterator<Item = bool>>(
        bits: &mut I,
        ty_l: &Final,
        ty_r: &Final,
    ) -> Result<(), EarlyEndOfStreamError>;
}

enum CompactEncoding {}
enum PaddedEncoding {}

impl Padding for CompactEncoding {
    fn read_left_padding<I: Iterator<Item = bool>>(
        _: &mut I,
        _: &Final,
        _: &Final,
    ) -> Result<(), EarlyEndOfStreamError> {
        // no padding
        Ok(())
    }

    fn read_right_padding<I: Iterator<Item = bool>>(
        _: &mut I,
        _: &Final,
        _: &Final,
    ) -> Result<(), EarlyEndOfStreamError> {
        // no padding
        Ok(())
    }
}

impl Padding for PaddedEncoding {
    fn read_left_padding<I: Iterator<Item = bool>>(
        bits: &mut I,
        ty_l: &Final,
        ty_r: &Final,
    ) -> Result<(), EarlyEndOfStreamError> {
        for _ in 0..ty_l.pad_left(ty_r) {
            let _padding = bits.next().ok_or(EarlyEndOfStreamError)?;
        }
        Ok(())
    }

    fn read_right_padding<I: Iterator<Item = bool>>(
        bits: &mut I,
        ty_l: &Final,
        ty_r: &Final,
    ) -> Result<(), EarlyEndOfStreamError> {
        for _ in 0..ty_l.pad_right(ty_r) {
            let _padding = bits.next().ok_or(EarlyEndOfStreamError)?;
        }
        Ok(())
    }
}

impl Value {
    fn from_bits<I: Iterator<Item = bool>, P: Padding>(
        bits: &mut I,
        ty: &Final,
    ) -> Result<Self, EarlyEndOfStreamError> {
        enum State<'a> {
            ProcessType(&'a Final),
            DoSumL(Arc<Final>),
            DoSumR(Arc<Final>),
            DoProduct,
        }

        let mut stack = vec![State::ProcessType(ty)];
        let mut result_stack = vec![];
        while let Some(state) = stack.pop() {
            match state {
                State::ProcessType(ty) => match ty.bound() {
                    types::CompleteBound::Unit => result_stack.push(Value::unit()),
                    types::CompleteBound::Sum(ref l, ref r) => {
                        if !bits.next().ok_or(EarlyEndOfStreamError)? {
                            P::read_left_padding(bits, l, r)?;
                            stack.push(State::DoSumL(Arc::clone(r)));
                            stack.push(State::ProcessType(l));
                        } else {
                            P::read_right_padding(bits, l, r)?;
                            stack.push(State::DoSumR(Arc::clone(l)));
                            stack.push(State::ProcessType(r));
                        }
                    }
                    types::CompleteBound::Product(ref l, ref r) => {
                        stack.push(State::DoProduct);
                        stack.push(State::ProcessType(r));
                        stack.push(State::ProcessType(l));
                    }
                },
                State::DoSumL(r) => {
                    let val = result_stack.pop().unwrap();
                    result_stack.push(Value::left(val, r));
                }
                State::DoSumR(l) => {
                    let val = result_stack.pop().unwrap();
                    result_stack.push(Value::right(l, val));
                }
                State::DoProduct => {
                    let val_r = result_stack.pop().unwrap();
                    let val_l = result_stack.pop().unwrap();
                    result_stack.push(Value::product(val_l, val_r));
                }
            }
        }
        debug_assert_eq!(result_stack.len(), 1);
        Ok(result_stack.pop().unwrap())
    }

    /// Decode a value of the given type from its compact bit encoding.
    pub fn from_compact_bits<I: Iterator<Item = bool>>(
        bits: &mut I,
        ty: &Final,
    ) -> Result<Self, EarlyEndOfStreamError> {
        Self::from_bits::<_, CompactEncoding>(bits, ty)
    }

    /// Decode a value of the given type from its padded bit encoding.
    pub fn from_padded_bits<I: Iterator<Item = bool>>(
        bits: &mut I,
        ty: &Final,
    ) -> Result<Self, EarlyEndOfStreamError> {
        Self::from_bits::<_, PaddedEncoding>(bits, ty)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::jet::type_name::TypeName;

    #[test]
    fn value_display() {
        // Only test a couple values becasue we probably want to change this
        // at some point and will have to redo this test.
        assert_eq!(Value::u1(0).to_string(), "0",);
        assert_eq!(Value::u1(1).to_string(), "1",);
        assert_eq!(Value::u4(6).to_string(), "((0,1),(1,0))",);
    }

    #[test]
    fn is_of_type() {
        let value_typename = [
            (Value::unit(), TypeName(b"1")),
            (Value::left(Value::unit(), Final::unit()), TypeName(b"+11")),
            (Value::right(Final::unit(), Value::unit()), TypeName(b"+11")),
            (
                Value::left(Value::unit(), Final::two_two_n(8)),
                TypeName(b"+1h"),
            ),
            (
                Value::right(Final::two_two_n(8), Value::unit()),
                TypeName(b"+h1"),
            ),
            (
                Value::product(Value::unit(), Value::unit()),
                TypeName(b"*11"),
            ),
            (Value::u8(u8::MAX), TypeName(b"c")),
            (Value::u64(u64::MAX), TypeName(b"l")),
        ];

        for (value, typename) in value_typename {
            let ty = typename.to_final();
            assert!(value.is_of_type(ty.as_ref()));
        }
    }
}