diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index 4c0ff0c49286bec1406d933d56dcca853e57ef07..2f871bd61be49a53629605ff1ea4a6fd091068bb 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -432,6 +432,7 @@ pub enum Instruction<'a> { ReadTicket, SplitTicket, JoinTickets, + LoopLeft(Vec), } #[derive(Debug, Clone, PartialEq, Eq)] diff --git a/contrib/mir/src/gas.rs b/contrib/mir/src/gas.rs index f0cc30f597a8f32639bcd9586dac1a1e350e6d84..7933947eab15bf23c0ee0432625e216a6dabed1a 100644 --- a/contrib/mir/src/gas.rs +++ b/contrib/mir/src/gas.rs @@ -256,6 +256,7 @@ pub mod interpret_cost { pub const INTERPRET_RET: u32 = 15; // corresponds to KNil in the Tezos protocol pub const LOOP_ENTER: u32 = 10; // corresponds to KLoop_in in the Tezos protocol + pub const LOOP_LEFT_ENTER: u32 = 10; // corresponds to KLoop_in_left in the Tezos protocol pub const LOOP_EXIT: u32 = 10; pub fn join_tickets(t1: &Ticket, t2: &Ticket) -> Result { diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index 0438da7488f46e9ce754650e476c556d79da5a26..47e62acedf055d46eaa2b6a3c3132a47d64838ec 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -394,6 +394,23 @@ fn interpret_one<'a>( } } } + I::LoopLeft(nested) => { + ctx.gas.consume(interpret_cost::LOOP_LEFT_ENTER)?; + loop { + ctx.gas.consume(interpret_cost::LOOP)?; + match *pop!(V::Or) { + Or::Left(x) => { + stack.push(x); + interpret(nested, ctx, stack)?; + } + Or::Right(x) => { + stack.push(x); + ctx.gas.consume(interpret_cost::LOOP_EXIT)?; + break; + } + } + } + } I::Iter(overload, nested) => { ctx.gas.consume(interpret_cost::ITER)?; match overload { @@ -852,8 +869,8 @@ fn interpret_one<'a>( mod interpreter_tests { use std::collections::{BTreeMap, BTreeSet}; - use super::Lambda; use super::*; + use super::{Lambda, Or}; use crate::ast::michelson_address as addr; use crate::gas::Gas; use Instruction::*; @@ -1360,6 +1377,36 @@ mod interpreter_tests { assert_eq!(stack, expected_stack); } + #[test] + fn loop_left_0() { + let mut stack = stk![V::new_or(Or::Right(V::nat(0)))]; + let mut ctx = Ctx::default(); + assert_eq!( + interpret_one(&LoopLeft(vec![Failwith(Type::Nat)]), &mut ctx, &mut stack), + Ok(()) + ); + assert_eq!(stack, stk![V::nat(0)]) + } + + #[test] + fn loop_left_1() { + let mut stack = stk![V::new_or(Or::Left(V::nat(0)))]; + let mut ctx = Ctx::default(); + assert_eq!( + interpret_one( + &LoopLeft(vec![Drop(None), Push(V::new_or(Or::Right(V::int(1))))]), + &mut ctx, + &mut stack + ), + Ok(()) + ); + assert_eq!(stack, stk![V::int(1)]) + } + + // TODO: the current branch doesn't have LEFT and RIGHT instructions, so + // adding a testcase for LOOP_LEFT with more than one iteration is + // unnecessarily complicated. Left for future work. + #[test] fn test_iter_list_many() { let mut stack = stk![ diff --git a/contrib/mir/src/typechecker.rs b/contrib/mir/src/typechecker.rs index a260dd8acad1cd5a2f88cf8664b2a69300e67217..4398e5fb61a1a671279f01dc4d71124d25dc473c 100644 --- a/contrib/mir/src/typechecker.rs +++ b/contrib/mir/src/typechecker.rs @@ -845,6 +845,25 @@ pub(crate) fn typecheck_instruction<'a>( (App(LOOP, [Seq(_)], _), []) => no_overload!(LOOP, len 1), (App(LOOP, expect_args!(1 seq), _), _) => unexpected_micheline!(), + (App(LOOP_LEFT, [Seq(nested)], _), [.., T::Or(_)]) => { + // copy current stack to unify with later + let opt_copy = FailingTypeStack::Ok(stack.clone()); + let (l_ty, r_ty) = pop!(T::Or).as_ref().clone(); + // loop body consumes left leaf and returns `or` again + stack.push(l_ty); + let nested = typecheck(nested, ctx, self_entrypoints, opt_stack)?; + unify_stacks(ctx, opt_stack, opt_copy)?; + // the loop leaves the right leaf of `or` on the stack at the end + // this FailNotInTail should be impossible to get + opt_stack.access_mut(TcError::FailNotInTail)?[0] = r_ty; + I::LoopLeft(nested) + } + (App(LOOP_LEFT, [Seq(_)], _), [.., ty]) => { + no_overload!(LOOP_LEFT, NMOR::ExpectedOr(ty.clone())) + } + (App(LOOP_LEFT, [Seq(_)], _), []) => no_overload!(LOOP_LEFT, len 1), + (App(LOOP_LEFT, expect_args!(1 seq), _), _) => unexpected_micheline!(), + (App(ITER, [Seq(nested)], ..), [.., T::List(..)]) => { // get the list element type let ty = pop!(T::List); @@ -1659,7 +1678,7 @@ fn ensure_ty_eq(ctx: &mut Ctx, ty1: &Type, ty2: &Type) -> Result<(), TcError> { #[cfg(test)] mod typecheck_tests { - use super::Lambda; + use super::{Lambda, Or}; use crate::ast::micheline::test_helpers::*; use crate::ast::michelson_address as addr; use crate::gas::Gas; @@ -2035,6 +2054,69 @@ mod typecheck_tests { ); } + #[test] + fn test_loop_left() { + let mut stack = tc_stk![Type::Int, Type::new_or(Type::Unit, Type::Nat)]; + let expected_stack = tc_stk![Type::Int, Type::Nat]; + let mut ctx = Ctx::default(); + assert_eq!( + typecheck_instruction( + &parse("LOOP_LEFT {DROP; PUSH (or unit nat) (Right 123)}").unwrap(), + &mut ctx, + &mut stack + ), + Ok(LoopLeft(vec![ + Drop(None), + Push(TypedValue::new_or(Or::Right(TypedValue::nat(123)))) + ])) + ); + assert_eq!(stack, expected_stack); + assert!(ctx.gas.milligas() < Gas::default().milligas()); + } + + #[test] + fn test_loop_left_stacks_not_equal_length() { + let mut stack = tc_stk![Type::Int, Type::new_or(Type::Unit, Type::Nat)]; + let mut ctx = Ctx::default(); + assert_eq!( + typecheck_instruction( + &parse("LOOP_LEFT {PUSH (or unit nat) (Right 123)}").unwrap(), + &mut ctx, + &mut stack + ) + .unwrap_err(), + TcError::StacksNotEqual( + stk![Type::Int, Type::Unit, Type::new_or(Type::Unit, Type::Nat)], + stk![Type::Int, Type::new_or(Type::Unit, Type::Nat)], + StacksNotEqualReason::LengthsDiffer(3, 2) + ) + ); + } + + #[test] + fn test_loop_left_stacks_not_equal_types() { + let mut stack = tc_stk![Type::Int, Type::new_or(Type::Unit, Type::Nat)]; + let mut ctx = Ctx::default(); + assert_eq!( + typecheck_instruction( + &parse("LOOP_LEFT {DROP; PUSH bool True}").unwrap(), + &mut ctx, + &mut stack + ) + .unwrap_err(), + TcError::StacksNotEqual( + stk![Type::Int, Type::Bool], + stk![Type::Int, Type::new_or(Type::Unit, Type::Nat)], + TypesNotEqual(Type::Bool, Type::new_or(Type::Unit, Type::Nat)).into() + ) + ); + } + + #[test] + fn test_loop_left_too_short() { + too_short_test(&app!(LOOP_LEFT[seq! {app!(FAILWITH)}]), Prim::LOOP_LEFT, 1); + } + #[test] fn test_iter_list() { let mut stack = tc_stk![Type::new_list(Type::Int)];