use crate::black_box::BlackBoxOp;
use acir_field::AcirField;
use serde::{Deserialize, Serialize};
pub type Label = usize;
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub enum MemoryAddress {
Direct(usize),
Relative(usize),
}
impl MemoryAddress {
pub fn direct(address: usize) -> Self {
MemoryAddress::Direct(address)
}
pub fn relative(offset: usize) -> Self {
MemoryAddress::Relative(offset)
}
pub fn unwrap_direct(self) -> usize {
match self {
MemoryAddress::Direct(address) => address,
MemoryAddress::Relative(_) => panic!("Expected direct memory address"),
}
}
pub fn unwrap_relative(self) -> usize {
match self {
MemoryAddress::Direct(_) => panic!("Expected relative memory address"),
MemoryAddress::Relative(offset) => offset,
}
}
pub fn to_usize(self) -> usize {
match self {
MemoryAddress::Direct(address) => address,
MemoryAddress::Relative(offset) => offset,
}
}
pub fn is_relative(&self) -> bool {
match self {
MemoryAddress::Relative(_) => true,
MemoryAddress::Direct(_) => false,
}
}
pub fn offset(&self, amount: usize) -> Self {
match self {
MemoryAddress::Direct(address) => MemoryAddress::Direct(address + amount),
MemoryAddress::Relative(offset) => MemoryAddress::Relative(offset + amount),
}
}
}
impl std::fmt::Display for MemoryAddress {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
MemoryAddress::Direct(address) => write!(f, "@{address}"),
MemoryAddress::Relative(offset) => write!(f, "sp[{offset}]"),
}
}
}
#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize, Hash)]
pub enum HeapValueType {
Simple(BitSize),
Array { value_types: Vec<HeapValueType>, size: usize },
Vector { value_types: Vec<HeapValueType> },
}
impl HeapValueType {
pub fn all_simple(types: &[HeapValueType]) -> bool {
types.iter().all(|typ| matches!(typ, HeapValueType::Simple(_)))
}
pub fn field() -> HeapValueType {
HeapValueType::Simple(BitSize::Field)
}
pub fn flattened_size(&self) -> Option<usize> {
match self {
HeapValueType::Simple(_) => Some(1),
HeapValueType::Array { value_types, size } => {
let element_size =
value_types.iter().map(|t| t.flattened_size()).sum::<Option<usize>>();
element_size.map(|element_size| element_size * size)
}
HeapValueType::Vector { .. } => {
None
}
}
}
}
impl std::fmt::Display for HeapValueType {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let write_types =
|f: &mut std::fmt::Formatter<'_>, value_types: &[HeapValueType]| -> std::fmt::Result {
if value_types.len() == 1 {
write!(f, "{}", value_types[0])?;
} else {
write!(f, "(")?;
for (index, value_type) in value_types.iter().enumerate() {
if index > 0 {
write!(f, ", ")?;
}
write!(f, "{value_type}")?;
}
write!(f, ")")?;
}
Ok(())
};
match self {
HeapValueType::Simple(bit_size) => {
write!(f, "{bit_size}")
}
HeapValueType::Array { value_types, size } => {
write!(f, "[")?;
write_types(f, value_types)?;
write!(f, "; {size}")?;
write!(f, "]")
}
HeapValueType::Vector { value_types } => {
write!(f, "&[")?;
write_types(f, value_types)?;
write!(f, "]")
}
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, Copy, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub struct HeapArray {
pub pointer: MemoryAddress,
pub size: usize,
}
impl Default for HeapArray {
fn default() -> Self {
Self { pointer: MemoryAddress::direct(0), size: 0 }
}
}
impl std::fmt::Display for HeapArray {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "[{}; {}]", self.pointer, self.size)
}
}
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, Copy, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub struct HeapVector {
pub pointer: MemoryAddress,
pub size: MemoryAddress,
}
impl std::fmt::Display for HeapVector {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "&[{}; {}]", self.pointer, self.size)
}
}
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, Copy, PartialOrd, Ord, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub enum IntegerBitSize {
U1,
U8,
U16,
U32,
U64,
U128,
}
impl From<IntegerBitSize> for u32 {
fn from(bit_size: IntegerBitSize) -> u32 {
match bit_size {
IntegerBitSize::U1 => 1,
IntegerBitSize::U8 => 8,
IntegerBitSize::U16 => 16,
IntegerBitSize::U32 => 32,
IntegerBitSize::U64 => 64,
IntegerBitSize::U128 => 128,
}
}
}
impl TryFrom<u32> for IntegerBitSize {
type Error = &'static str;
fn try_from(value: u32) -> Result<Self, Self::Error> {
match value {
1 => Ok(IntegerBitSize::U1),
8 => Ok(IntegerBitSize::U8),
16 => Ok(IntegerBitSize::U16),
32 => Ok(IntegerBitSize::U32),
64 => Ok(IntegerBitSize::U64),
128 => Ok(IntegerBitSize::U128),
_ => Err("Invalid bit size"),
}
}
}
impl std::fmt::Display for IntegerBitSize {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
match self {
IntegerBitSize::U1 => write!(f, "bool"),
IntegerBitSize::U8 => write!(f, "u8"),
IntegerBitSize::U16 => write!(f, "u16"),
IntegerBitSize::U32 => write!(f, "u32"),
IntegerBitSize::U64 => write!(f, "u64"),
IntegerBitSize::U128 => write!(f, "u128"),
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, Copy, PartialOrd, Ord, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub enum BitSize {
Field,
Integer(IntegerBitSize),
}
impl BitSize {
pub fn to_u32<F: AcirField>(self) -> u32 {
match self {
BitSize::Field => F::max_num_bits(),
BitSize::Integer(bit_size) => bit_size.into(),
}
}
pub fn try_from_u32<F: AcirField>(value: u32) -> Result<Self, &'static str> {
if value == F::max_num_bits() {
Ok(BitSize::Field)
} else {
Ok(BitSize::Integer(IntegerBitSize::try_from(value)?))
}
}
}
impl std::fmt::Display for BitSize {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
match self {
BitSize::Field => write!(f, "field"),
BitSize::Integer(bit_size) => write!(f, "{bit_size}"),
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, Copy, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub enum ValueOrArray {
MemoryAddress(MemoryAddress),
HeapArray(HeapArray),
HeapVector(HeapVector),
}
impl std::fmt::Display for ValueOrArray {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
ValueOrArray::MemoryAddress(memory_address) => {
write!(f, "{memory_address}")
}
ValueOrArray::HeapArray(heap_array) => {
write!(f, "{heap_array}")
}
ValueOrArray::HeapVector(heap_vector) => {
write!(f, "{heap_vector}")
}
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub enum BrilligOpcode<F> {
BinaryFieldOp {
destination: MemoryAddress,
op: BinaryFieldOp,
lhs: MemoryAddress,
rhs: MemoryAddress,
},
BinaryIntOp {
destination: MemoryAddress,
op: BinaryIntOp,
bit_size: IntegerBitSize,
lhs: MemoryAddress,
rhs: MemoryAddress,
},
Not {
destination: MemoryAddress,
source: MemoryAddress,
bit_size: IntegerBitSize,
},
Cast {
destination: MemoryAddress,
source: MemoryAddress,
bit_size: BitSize,
},
JumpIf {
condition: MemoryAddress,
location: Label,
},
Jump {
location: Label,
},
CalldataCopy {
destination_address: MemoryAddress,
size_address: MemoryAddress,
offset_address: MemoryAddress,
},
Call {
location: Label,
},
Const {
destination: MemoryAddress,
bit_size: BitSize,
value: F,
},
IndirectConst {
destination_pointer: MemoryAddress,
bit_size: BitSize,
value: F,
},
Return,
ForeignCall {
function: String,
destinations: Vec<ValueOrArray>,
destination_value_types: Vec<HeapValueType>,
inputs: Vec<ValueOrArray>,
input_value_types: Vec<HeapValueType>,
},
Mov {
destination: MemoryAddress,
source: MemoryAddress,
},
ConditionalMov {
destination: MemoryAddress,
source_a: MemoryAddress,
source_b: MemoryAddress,
condition: MemoryAddress,
},
Load {
destination: MemoryAddress,
source_pointer: MemoryAddress,
},
Store {
destination_pointer: MemoryAddress,
source: MemoryAddress,
},
BlackBox(BlackBoxOp),
Trap {
revert_data: HeapVector,
},
Stop {
return_data: HeapVector,
},
}
impl<F: std::fmt::Display> std::fmt::Display for BrilligOpcode<F> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
BrilligOpcode::BinaryFieldOp { destination, op, lhs, rhs } => {
write!(f, "{destination} = field {op} {lhs}, {rhs}")
}
BrilligOpcode::BinaryIntOp { destination, op, bit_size, lhs, rhs } => {
write!(f, "{destination} = {bit_size} {op} {lhs}, {rhs}")
}
BrilligOpcode::Not { destination, source, bit_size } => {
write!(f, "{destination} = {bit_size} not {source}")
}
BrilligOpcode::Cast { destination, source, bit_size } => {
write!(f, "{destination} = cast {source} to {bit_size}")
}
BrilligOpcode::JumpIf { condition, location } => {
write!(f, "jump if {condition} to {location}")
}
BrilligOpcode::Jump { location } => {
write!(f, "jump to {location}")
}
BrilligOpcode::CalldataCopy { destination_address, size_address, offset_address } => {
write!(
f,
"{destination_address} = calldata copy [{offset_address}; {size_address}]"
)
}
BrilligOpcode::Call { location } => {
write!(f, "call {location}")
}
BrilligOpcode::Const { destination, bit_size, value } => {
write!(f, "{destination} = const {bit_size} {value}")
}
BrilligOpcode::IndirectConst { destination_pointer, bit_size, value } => {
write!(f, "{destination_pointer} = indirect const {bit_size} {value}")
}
BrilligOpcode::Return => {
write!(f, "return")
}
BrilligOpcode::ForeignCall {
function,
destinations,
destination_value_types,
inputs,
input_value_types,
} => {
assert_eq!(destinations.len(), destination_value_types.len());
if !destinations.is_empty() {
for (index, (destination, destination_value_type)) in
destinations.iter().zip(destination_value_types.iter()).enumerate()
{
if index > 0 {
write!(f, ", ")?;
}
write!(f, "{destination}: {destination_value_type}")?;
}
write!(f, " = ")?;
}
write!(f, "foreign call {function}(")?;
assert_eq!(inputs.len(), input_value_types.len());
for (index, (input, input_value_type)) in
inputs.iter().zip(input_value_types.iter()).enumerate()
{
if index > 0 {
write!(f, ", ")?;
}
write!(f, "{input}: {input_value_type}")?;
}
write!(f, ")")?;
Ok(())
}
BrilligOpcode::Mov { destination, source } => {
write!(f, "{destination} = {source}")
}
BrilligOpcode::ConditionalMov { destination, source_a, source_b, condition } => {
write!(f, "{destination} = if {condition} then {source_a} else {source_b}")
}
BrilligOpcode::Load { destination, source_pointer } => {
write!(f, "{destination} = load {source_pointer}")
}
BrilligOpcode::Store { destination_pointer, source } => {
write!(f, "store {source} at {destination_pointer}")
}
BrilligOpcode::BlackBox(black_box_op) => {
write!(f, "{black_box_op}")
}
BrilligOpcode::Trap { revert_data } => {
write!(f, "trap {revert_data}")
}
BrilligOpcode::Stop { return_data } => {
write!(f, "stop {return_data}")
}
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub enum BinaryFieldOp {
Add,
Sub,
Mul,
Div,
IntegerDiv,
Equals,
LessThan,
LessThanEquals,
}
impl std::fmt::Display for BinaryFieldOp {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
BinaryFieldOp::Add => write!(f, "add"),
BinaryFieldOp::Sub => write!(f, "sub"),
BinaryFieldOp::Mul => write!(f, "mul"),
BinaryFieldOp::Div => write!(f, "field_div"),
BinaryFieldOp::IntegerDiv => write!(f, "int_div"),
BinaryFieldOp::Equals => write!(f, "eq"),
BinaryFieldOp::LessThan => write!(f, "lt"),
BinaryFieldOp::LessThanEquals => write!(f, "lt_eq"),
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub enum BinaryIntOp {
Add,
Sub,
Mul,
Div,
Equals,
LessThan,
LessThanEquals,
And,
Or,
Xor,
Shl,
Shr,
}
impl std::fmt::Display for BinaryIntOp {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
BinaryIntOp::Add => write!(f, "add"),
BinaryIntOp::Sub => write!(f, "sub"),
BinaryIntOp::Mul => write!(f, "mul"),
BinaryIntOp::Div => write!(f, "div"),
BinaryIntOp::Equals => write!(f, "eq"),
BinaryIntOp::LessThan => write!(f, "lt"),
BinaryIntOp::LessThanEquals => write!(f, "lt_eq"),
BinaryIntOp::And => write!(f, "and"),
BinaryIntOp::Or => write!(f, "or"),
BinaryIntOp::Xor => write!(f, "xor"),
BinaryIntOp::Shl => write!(f, "shl"),
BinaryIntOp::Shr => write!(f, "shr"),
}
}
}
#[cfg(feature = "arb")]
mod tests {
use proptest::arbitrary::Arbitrary;
use proptest::prelude::*;
use super::{BitSize, HeapValueType};
impl Arbitrary for HeapValueType {
type Parameters = ();
type Strategy = BoxedStrategy<Self>;
fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
let leaf = any::<BitSize>().prop_map(HeapValueType::Simple);
leaf.prop_recursive(2, 3, 2, |inner| {
prop_oneof![
(prop::collection::vec(inner.clone(), 1..3), any::<usize>()).prop_map(
|(value_types, size)| { HeapValueType::Array { value_types, size } }
),
(prop::collection::vec(inner.clone(), 1..3))
.prop_map(|value_types| { HeapValueType::Vector { value_types } }),
]
})
.boxed()
}
}
}