diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index 044698b73a6842fdfcb9496838b09eaf18463546..71dee0aeb0a25281a19c2262dfb6c54a5034e5c9 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -12,10 +12,22 @@ pub enum Type { Bool, } +impl Type { + /// Returns abstract size of the type representation. Used for gas cost + /// estimation. + pub fn size_for_gas(&self) -> usize { + match self { + Type::Nat => 1, + Type::Int => 1, + Type::Bool => 1, + } + } +} + #[derive(Debug, Eq, PartialEq)] pub enum Value { NumberValue(i32), - BooleanValue(bool) + BooleanValue(bool), } pub type InstructionBlock = Vec; diff --git a/contrib/mir/src/gas.rs b/contrib/mir/src/gas.rs new file mode 100644 index 0000000000000000000000000000000000000000..12ba4057575b6f4b043c48c5ced10eb61bb039e3 --- /dev/null +++ b/contrib/mir/src/gas.rs @@ -0,0 +1,99 @@ +/******************************************************************************/ +/* */ +/* SPDX-License-Identifier: MIT */ +/* Copyright (c) [2023] Serokell */ +/* */ +/******************************************************************************/ + +#[derive(Debug)] +pub struct Gas { + milligas_amount: Option, +} + +#[derive(Debug, PartialEq, Eq)] +pub struct OutOfGas; + +// Default gas limit per transaction, according to +// https://opentezos.com/tezos-basics/economics-and-rewards/#transaction-cost +const DEFAULT_GAS_AMOUNT: u32 = 1_040_000; + +impl Default for Gas { + fn default() -> Self { + Gas::new(DEFAULT_GAS_AMOUNT * 1000) + } +} + +impl Gas { + pub fn new(milligas_amount: u32) -> Gas { + Gas { + milligas_amount: Some(milligas_amount), + } + } + + pub fn consume(&mut self, cost: u32) -> Result<(), OutOfGas> { + self.milligas_amount = self.milligas().checked_sub(cost); + if self.milligas_amount.is_none() { + Err(OutOfGas) + } else { + Ok(()) + } + } + + pub fn milligas(&self) -> u32 { + self.milligas_amount + .expect("Access to gas after exhaustion") + } +} + +pub mod tc_cost { + // Due to the quirk of Octez implementation, step gas is charged twice as + // often as in MIR. + pub const INSTR_STEP: u32 = 220 * 2; + + pub const VALUE_STEP: u32 = 100; + + fn variadic(depth: usize) -> u32 { + (depth * 50).try_into().unwrap() + } + + pub fn drop_n(depth: &Option) -> u32 { + depth.map(variadic).unwrap_or(0) + } + + pub fn dip_n(depth: &Option) -> u32 { + depth.map(variadic).unwrap_or(0) + } + + pub fn ty_eq(sz1: usize, sz2: usize) -> u32 { + // complexity of comparing types T and U is O(min(|T|, |U|)), as + // comparison short-circuits at the first mismatch + (std::cmp::min(sz1, sz2) * 60).try_into().unwrap() // according to Nairobi + } +} + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn gas_consumption() { + let mut gas = Gas::new(100); + gas.consume(30).unwrap(); + assert_eq!(gas.milligas(), 70) + } + + #[test] + fn gas_exhaustion_error() { + let mut gas = Gas::new(100); + assert_eq!(gas.consume(1000), Err(OutOfGas)); + } + + #[test] + #[should_panic(expected = "Access to gas after exhaustion")] + fn gas_exhaustion_panic() { + let mut gas = Gas::new(100); + assert_eq!(gas.consume(1000), Err(OutOfGas)); + + let _ = gas.consume(1000); // panics + } +} diff --git a/contrib/mir/src/main.rs b/contrib/mir/src/main.rs index ec36333702b43e7510e3020468be8abd9aa92f42..cd74185d034f7af8808331334667e5accf64f15a 100644 --- a/contrib/mir/src/main.rs +++ b/contrib/mir/src/main.rs @@ -6,6 +6,7 @@ /******************************************************************************/ mod ast; +mod gas; mod parser; mod stack; mod syntax; @@ -18,6 +19,7 @@ mod tests { use std::collections::VecDeque; use crate::ast::*; + use crate::gas::Gas; use crate::parser; use crate::typechecker; @@ -25,15 +27,38 @@ mod tests { fn typecheck_test_expect_success() { let ast = parser::parse(&FIBONACCI_SRC).unwrap(); let mut stack = VecDeque::from([Type::Nat]); - assert!(typechecker::typecheck(&ast, &mut stack).is_ok()); - assert!(stack == VecDeque::from([Type::Int])); + assert!(typechecker::typecheck(&ast, &mut Gas::default(), &mut stack).is_ok()); + assert_eq!(stack, VecDeque::from([Type::Int])); + } + + #[test] + fn typecheck_gas() { + let ast = parser::parse(&FIBONACCI_SRC).unwrap(); + let mut stack = VecDeque::from([Type::Nat]); + let mut gas = Gas::new(11460); + assert!(typechecker::typecheck(&ast, &mut gas, &mut stack).is_ok()); + assert_eq!(gas.milligas(), 0); + } + + #[test] + fn typecheck_out_of_gas() { + let ast = parser::parse(&FIBONACCI_SRC).unwrap(); + let mut stack = VecDeque::from([Type::Nat]); + let mut gas = Gas::new(1000); + assert_eq!( + typechecker::typecheck(&ast, &mut gas, &mut stack), + Err(typechecker::TcError::OutOfGas) + ); } #[test] fn typecheck_test_expect_fail() { let ast = parser::parse(&FIBONACCI_ILLTYPED_SRC).unwrap(); let mut stack = VecDeque::from([Type::Nat]); - assert!(typechecker::typecheck(&ast, &mut stack).is_err()); + assert_eq!( + typechecker::typecheck(&ast, &mut Gas::default(), &mut stack), + Err(typechecker::TcError::StackTooShort) + ); } #[test] @@ -45,7 +70,12 @@ mod tests { #[test] fn parser_test_expect_fail() { - assert_eq!(&parser::parse(&FIBONACCI_MALFORMED_SRC).unwrap_err().to_string(), "Unrecognized token `GT` found at 133:135\nExpected one of \";\" or \"}\""); + assert_eq!( + &parser::parse(&FIBONACCI_MALFORMED_SRC) + .unwrap_err() + .to_string(), + "Unrecognized token `GT` found at 133:135\nExpected one of \";\" or \"}\"" + ); } const FIBONACCI_SRC: &str = "{ INT ; PUSH int 0 ; DUP 2 ; GT ; diff --git a/contrib/mir/src/stack.rs b/contrib/mir/src/stack.rs index 0b025d764c6fc407e48f18adb09908b2d1766768..ebf0e9148985cb12e2ea67a88784b6e49fc0d65b 100644 --- a/contrib/mir/src/stack.rs +++ b/contrib/mir/src/stack.rs @@ -8,28 +8,39 @@ use std::collections::VecDeque; use crate::ast::*; +use crate::gas; +use crate::gas::Gas; +use crate::typechecker::TcError; pub type TypeStack = VecDeque; -pub struct StackTooShort; - /// Ensures type stack is at least of the required length, otherwise returns /// `Err(StackTooShort)`. -pub fn ensure_stack_len(stack: &TypeStack, l: usize) -> Result<(), StackTooShort> { +pub fn ensure_stack_len(stack: &TypeStack, l: usize) -> Result<(), TcError> { if stack.len() >= l { Ok(()) } else { - Err(StackTooShort) + Err(TcError::StackTooShort) } } -pub struct StacksNotEqual; +/// Ensures two type stacks compare equal, otherwise returns +/// `Err(StacksNotEqual)`. If runs out of gas, returns `Err(OutOfGas)` instead. +pub fn ensure_stacks_eq(gas: &mut Gas, stack1: &[Type], stack2: &[Type]) -> Result<(), TcError> { + if stack1.len() != stack2.len() { + return Err(TcError::StacksNotEqual); + } + for (ty1, ty2) in stack1.iter().zip(stack2.iter()) { + ensure_ty_eq(gas, ty1, ty2)?; + } + Ok(()) +} -/// Ensures two type stacks compare equal, otherwise returns `Err(StacksNotEqual)`. -pub fn ensure_stacks_eq(stack1: &[Type], stack2: &[Type]) -> Result<(), StacksNotEqual> { - if stack1 == stack2 { - Ok(()) +fn ensure_ty_eq(gas: &mut Gas, ty1: &Type, ty2: &Type) -> Result<(), TcError> { + gas.consume(gas::tc_cost::ty_eq(ty1.size_for_gas(), ty2.size_for_gas()))?; + if ty1 != ty2 { + Err(TcError::StacksNotEqual) } else { - Err(StacksNotEqual) + Ok(()) } } diff --git a/contrib/mir/src/typechecker.rs b/contrib/mir/src/typechecker.rs index e47b9a144d724dedfa1f286869fc318f2b91ded2..20a2322aab5885e6a5516f6483a0f1084781ddb3 100644 --- a/contrib/mir/src/typechecker.rs +++ b/contrib/mir/src/typechecker.rs @@ -6,6 +6,8 @@ /******************************************************************************/ use crate::ast::*; +use crate::gas; +use crate::gas::{Gas, OutOfGas}; use crate::stack::*; use std::collections::VecDeque; @@ -15,31 +17,32 @@ pub enum TcError { GenericTcError, StackTooShort, StacksNotEqual, + OutOfGas, } -impl From for TcError { - fn from(_: StackTooShort) -> Self { - TcError::StackTooShort +impl From for TcError { + fn from(_: OutOfGas) -> Self { + TcError::OutOfGas } } -impl From for TcError { - fn from(_: StacksNotEqual) -> Self { - TcError::StacksNotEqual - } -} - -pub fn typecheck(ast: &AST, stack: &mut TypeStack) -> Result<(), TcError> { +pub fn typecheck(ast: &AST, gas: &mut Gas, stack: &mut TypeStack) -> Result<(), TcError> { for i in ast { - typecheck_instruction(&i, stack)?; + typecheck_instruction(&i, gas, stack)?; } Ok(()) } -fn typecheck_instruction(i: &Instruction, stack: &mut TypeStack) -> Result<(), TcError> { +fn typecheck_instruction( + i: &Instruction, + gas: &mut Gas, + stack: &mut TypeStack, +) -> Result<(), TcError> { use Instruction::*; use Type::*; + gas.consume(gas::tc_cost::INSTR_STEP)?; + match i { Add => match stack.make_contiguous() { [Type::Nat, Type::Nat, ..] => { @@ -53,16 +56,19 @@ fn typecheck_instruction(i: &Instruction, stack: &mut TypeStack) -> Result<(), T Dip(opt_height, nested) => { let protected_height: usize = opt_height.unwrap_or(1); + gas.consume(gas::tc_cost::dip_n(opt_height))?; + ensure_stack_len(stack, protected_height)?; // Here we split the stack into protected and live segments, and after typechecking // nested code with the live segment, we append the protected and the potentially // modified live segment as the result stack. let mut live = stack.split_off(protected_height); - typecheck(nested, &mut live)?; + typecheck(nested, gas, &mut live)?; stack.append(&mut live); } Drop(opt_height) => { let drop_height: usize = opt_height.unwrap_or(1); + gas.consume(gas::tc_cost::drop_n(opt_height))?; ensure_stack_len(&stack, drop_height)?; *stack = stack.split_off(drop_height); } @@ -88,11 +94,11 @@ fn typecheck_instruction(i: &Instruction, stack: &mut TypeStack) -> Result<(), T // the two branches with. let mut t_stack: TypeStack = VecDeque::from(t.to_owned()); let mut f_stack: TypeStack = VecDeque::from(t.to_owned()); - typecheck(nested_t, &mut t_stack)?; - typecheck(nested_f, &mut f_stack)?; + typecheck(nested_t, gas, &mut t_stack)?; + typecheck(nested_f, gas, &mut f_stack)?; // If both stacks are same after typecheck, then make result // stack using one of them and return success. - ensure_stacks_eq(t_stack.make_contiguous(), f_stack.make_contiguous())?; + ensure_stacks_eq(gas, t_stack.make_contiguous(), f_stack.make_contiguous())?; *stack = t_stack; } _ => return Err(TcError::GenericTcError), @@ -108,23 +114,17 @@ fn typecheck_instruction(i: &Instruction, stack: &mut TypeStack) -> Result<(), T [Bool, t @ ..] => { let mut live: TypeStack = VecDeque::from(t.to_owned()); // Clone the tail and typecheck the nested body using it. - typecheck(nested, &mut live)?; - match live.make_contiguous() { - // ensure the result stack has a bool on top. - [Bool, r @ ..] => { - // If the starting tail and result tail match - // then the typecheck is complete. pop the bool - // off the original stack to form the final result. - ensure_stacks_eq(&t, &r)?; - stack.pop_front(); - } - _ => return Err(TcError::GenericTcError), - } + typecheck(nested, gas, &mut live)?; + // If the starting stack and result stack match + // then the typecheck is complete. pop the bool + // off the original stack to form the final result. + ensure_stacks_eq(gas, live.make_contiguous(), stack.make_contiguous())?; + stack.pop_front(); } _ => return Err(TcError::GenericTcError), }, Push(t, v) => { - typecheck_value(&t, &v)?; + typecheck_value(gas, &t, &v)?; stack.push_front(t.to_owned()); } Swap => { @@ -135,9 +135,10 @@ fn typecheck_instruction(i: &Instruction, stack: &mut TypeStack) -> Result<(), T Ok(()) } -fn typecheck_value(t: &Type, v: &Value) -> Result<(), TcError> { +fn typecheck_value(gas: &mut Gas, t: &Type, v: &Value) -> Result<(), TcError> { use Type::*; use Value::*; + gas.consume(gas::tc_cost::VALUE_STEP)?; match (t, v) { (Nat, NumberValue(n)) if *n >= 0 => Ok(()), (Int, NumberValue(_)) => Ok(()), @@ -158,89 +159,150 @@ mod typecheck_tests { fn test_dup() { let mut stack = VecDeque::from([Type::Nat]); let expected_stack = VecDeque::from([Type::Nat, Type::Nat]); - typecheck_instruction(&Dup(Some(1)), &mut stack).unwrap(); + let mut gas = Gas::new(10000); + typecheck_instruction(&Dup(Some(1)), &mut gas, &mut stack).unwrap(); assert!(stack == expected_stack); + assert!(gas.milligas() == 10000 - 440); } #[test] fn test_dup_n() { let mut stack = VecDeque::from([Type::Nat, Type::Int]); let expected_stack = VecDeque::from([Type::Int, Type::Nat, Type::Int]); - typecheck_instruction(&Dup(Some(2)), &mut stack).unwrap(); + let mut gas = Gas::new(10000); + typecheck_instruction(&Dup(Some(2)), &mut gas, &mut stack).unwrap(); assert!(stack == expected_stack); + assert!(gas.milligas() == 10000 - 440); } #[test] fn test_swap() { let mut stack = VecDeque::from([Type::Nat, Type::Int]); let expected_stack = VecDeque::from([Type::Int, Type::Nat]); - typecheck_instruction(&Swap, &mut stack).unwrap(); + let mut gas = Gas::new(10000); + typecheck_instruction(&Swap, &mut gas, &mut stack).unwrap(); assert!(stack == expected_stack); + assert!(gas.milligas() == 10000 - 440); } #[test] fn test_int() { let mut stack = VecDeque::from([Type::Nat]); let expected_stack = VecDeque::from([Type::Int]); - typecheck_instruction(&Int, &mut stack).unwrap(); + let mut gas = Gas::new(10000); + typecheck_instruction(&Int, &mut gas, &mut stack).unwrap(); assert!(stack == expected_stack); + assert!(gas.milligas() == 10000 - 440); } #[test] fn test_drop() { let mut stack = VecDeque::from([Type::Nat]); let expected_stack = VecDeque::from([]); - typecheck(&parse("{DROP}").unwrap(), &mut stack).unwrap(); + let mut gas = Gas::new(10000); + typecheck(&parse("{DROP}").unwrap(), &mut gas, &mut stack).unwrap(); assert!(stack == expected_stack); + assert!(gas.milligas() == 10000 - 440); } #[test] fn test_drop_n() { let mut stack = VecDeque::from([Type::Nat, Type::Int]); let expected_stack = VecDeque::from([]); - typecheck_instruction(&Drop(Some(2)), &mut stack).unwrap(); + let mut gas = Gas::new(10000); + typecheck_instruction(&Drop(Some(2)), &mut gas, &mut stack).unwrap(); assert!(stack == expected_stack); + assert!(gas.milligas() == 10000 - 440 - 2 * 50); } #[test] fn test_push() { let mut stack = VecDeque::from([Type::Nat]); let expected_stack = VecDeque::from([Type::Int, Type::Nat]); - typecheck_instruction(&Push(Type::Int, Value::NumberValue(1)), &mut stack).unwrap(); + let mut gas = Gas::new(10000); + typecheck_instruction( + &Push(Type::Int, Value::NumberValue(1)), + &mut gas, + &mut stack, + ) + .unwrap(); assert!(stack == expected_stack); + assert!(gas.milligas() == 10000 - 440 - 100); } #[test] fn test_gt() { let mut stack = VecDeque::from([Type::Int]); let expected_stack = VecDeque::from([Type::Bool]); - typecheck_instruction(&Gt, &mut stack).unwrap(); + let mut gas = Gas::new(10000); + typecheck_instruction(&Gt, &mut gas, &mut stack).unwrap(); assert!(stack == expected_stack); + assert!(gas.milligas() == 10000 - 440); } #[test] fn test_dip() { let mut stack = VecDeque::from([Type::Int, Type::Bool]); let expected_stack = VecDeque::from([Type::Int, Type::Nat, Type::Bool]); - typecheck_instruction(&Dip(Some(1), parse("{PUSH nat 6}").unwrap()), &mut stack).unwrap(); + let mut gas = Gas::new(10000); + typecheck_instruction( + &Dip(Some(1), parse("{PUSH nat 6}").unwrap()), + &mut gas, + &mut stack, + ) + .unwrap(); assert!(stack == expected_stack); + assert!(gas.milligas() == 10000 - 440 - 440 - 100 - 50); } #[test] fn test_add() { let mut stack = VecDeque::from([Type::Int, Type::Int]); let expected_stack = VecDeque::from([Type::Int]); - typecheck_instruction(&Add, &mut stack).unwrap(); + let mut gas = Gas::new(10000); + typecheck_instruction(&Add, &mut gas, &mut stack).unwrap(); assert!(stack == expected_stack); + assert!(gas.milligas() == 10000 - 440); } #[test] fn test_loop() { let mut stack = VecDeque::from([Type::Bool, Type::Int]); let expected_stack = VecDeque::from([Type::Int]); + let mut gas = Gas::new(10000); + assert!(typecheck_instruction( + &Loop(parse("{PUSH bool True}").unwrap()), + &mut gas, + &mut stack + ) + .is_ok()); + assert!(stack == expected_stack); + assert!(gas.milligas() == 10000 - 440 - 440 - 100 - 60 * 2); + } + + #[test] + fn test_loop_stacks_not_equal_length() { + let mut stack = VecDeque::from([Type::Bool, Type::Int]); + let mut gas = Gas::new(10000); assert!( - typecheck_instruction(&Loop(parse("{PUSH bool True}").unwrap()), &mut stack).is_ok() + typecheck_instruction( + &Loop(parse("{PUSH int 1; PUSH bool True}").unwrap()), + &mut gas, + &mut stack + ) == Err(TcError::StacksNotEqual) + ); + } + + #[test] + fn test_loop_stacks_not_equal_types() { + let mut stack = VecDeque::from([Type::Bool, Type::Int]); + let mut gas = Gas::new(10000); + assert!( + typecheck_instruction( + &Loop(parse("{DROP; PUSH bool False; PUSH bool True}").unwrap()), + &mut gas, + &mut stack + ) == Err(TcError::StacksNotEqual) ); - assert!(stack == expected_stack); } }