From d94b65f34732139733913880c6650171036f4b44 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Wed, 13 Dec 2023 13:51:05 +0300 Subject: [PATCH 1/5] MIR: PAIR n instruction --- contrib/mir/src/ast.rs | 1 + contrib/mir/src/gas.rs | 11 ++++ contrib/mir/src/interpreter.rs | 39 ++++++++++++ contrib/mir/src/stack.rs | 37 ++++++++++++ contrib/mir/src/typechecker.rs | 107 ++++++++++++++++++++++++++++++++- 5 files changed, 194 insertions(+), 1 deletion(-) diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index a7c8a93975ad..d953b91cd6d5 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -542,6 +542,7 @@ pub enum Instruction<'a> { Car, Cdr, Pair, + PairN(u16), /// `ISome` because `Some` is already taken ISome, None, diff --git a/contrib/mir/src/gas.rs b/contrib/mir/src/gas.rs index 720c92c26802..cadfd157f305 100644 --- a/contrib/mir/src/gas.rs +++ b/contrib/mir/src/gas.rs @@ -210,6 +210,11 @@ pub mod tc_cost { let log2n = (n + 1).ok_or(OutOfGas)?.log2i() as usize; (130 * n + key_size * n * log2n).as_gas_cost() } + + pub fn pair_n(size: usize) -> Result { + // corresponds to Cost_of.Typechecking.proof_argument in the protocol + (Checked::from(size) * 50).as_gas_cost() + } } pub trait BigIntByteSize { @@ -814,6 +819,12 @@ pub mod interpret_cost { let size = Checked::from(bytes.len()); (260 + (size >> 1)).as_gas_cost() } + + pub fn pair_n(size: usize) -> Result { + let size = Checked::from(size); + let v0 = size - 2; + (40 + ((v0 >> 2) + (v0 * 3))).as_gas_cost() + } } #[cfg(test)] diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index 444ceff87aa7..9d94b78b1fac 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -702,6 +702,15 @@ fn interpret_one<'a>( let r = pop!(); stack.push(V::new_pair(l, r)); } + I::PairN(n) => { + ctx.gas.consume(interpret_cost::pair_n(*n as usize)?)?; + let res = stack + .drain_top(*n as usize) + .rev() + .reduce(|acc, e| V::new_pair(e, acc)) + .unwrap(); + stack.push(res); + } I::Unpair => { ctx.gas.consume(interpret_cost::UNPAIR)?; let (l, r) = *pop!(V::Pair); @@ -2348,6 +2357,36 @@ mod interpreter_tests { assert_eq!(stack, stk![V::new_pair(V::Bool(false), V::nat(42))]); } + #[test] + fn pair_n_3() { + let mut stack = stk![V::String("foo".into()), V::Unit, V::nat(42), V::Bool(false)]; // NB: bool is top + let ctx = &mut Ctx::default(); + assert_eq!(interpret_one(&PairN(3), ctx, &mut stack), Ok(())); + assert_eq!( + stack, + stk![ + V::String("foo".into()), + V::new_pair(V::Bool(false), V::new_pair(V::nat(42), V::Unit)) + ] + ); + assert!(ctx.gas.milligas() < Ctx::default().gas.milligas()) + } + + #[test] + fn pair_n_4() { + let mut stack = stk![V::String("foo".into()), V::Unit, V::nat(42), V::Bool(false)]; // NB: bool is top + let ctx = &mut Ctx::default(); + assert_eq!(interpret_one(&PairN(4), ctx, &mut stack), Ok(())); + assert_eq!( + stack, + stk![V::new_pair( + V::Bool(false), + V::new_pair(V::nat(42), V::new_pair(V::Unit, V::String("foo".into()))) + )] + ); + assert!(ctx.gas.milligas() < Ctx::default().gas.milligas()) + } + #[test] fn unpair() { let mut stack = stk![V::new_pair(V::Bool(false), V::nat(42))]; diff --git a/contrib/mir/src/stack.rs b/contrib/mir/src/stack.rs index 4033ee81692e..845a61bca57e 100644 --- a/contrib/mir/src/stack.rs +++ b/contrib/mir/src/stack.rs @@ -121,6 +121,20 @@ impl Stack { .truncate(len.checked_sub(size).expect("size too large in drop_top")); } + /// Removes the specified number of elements from the top of the stack and + /// returns them as an iterator over the removed items, starting with the stack's top. + /// + /// Panics if the `size` is larger than length of the stack. + /// + /// If you do not need the items, use `drop_top` instead. + #[must_use] + pub fn drain_top(&mut self, size: usize) -> impl DoubleEndedIterator + '_ { + let len = self.len(); + self.0 + .drain(len.checked_sub(size).expect("size too large in drain_top")..) + .rev() + } + /// Borrow the stack content as an immutable slice. Note that stack top is /// the _rightmost_ element. pub fn as_slice(&self) -> &[T] { @@ -386,6 +400,22 @@ mod tests { assert_eq!(stk, stk![1]); } + #[test] + fn drain_top() { + let mut stk = stk![1, 2, 3, 4]; + let drained = stk.drain_top(3); + assert_eq!(drained.collect::>(), vec![4, 3, 2]); + assert_eq!(stk, stk![1]); + } + + #[test] + fn drain_top_0() { + let mut stk = stk![1, 2, 3, 4]; + let drained = stk.drain_top(0); + assert_eq!(drained.collect::>(), vec![]); + assert_eq!(stk, stk![1, 2, 3, 4]); + } + #[test] #[should_panic(expected = "size too large in drop_top")] fn drop_top_out_of_bounds() { @@ -393,6 +423,13 @@ mod tests { stk.drop_top(42); } + #[test] + #[should_panic(expected = "size too large in drain_top")] + fn drain_top_out_of_bounds() { + let mut stk = stk![1, 2, 3, 4]; + let _ = stk.drain_top(42); + } + #[test] fn as_slice() { let stk = stk![1, 2, 3, 4]; diff --git a/contrib/mir/src/typechecker.rs b/contrib/mir/src/typechecker.rs index e60fa16e0025..909988820662 100644 --- a/contrib/mir/src/typechecker.rs +++ b/contrib/mir/src/typechecker.rs @@ -27,7 +27,7 @@ use crate::ast::micheline::{ use crate::ast::michelson_address::AddressHash; use crate::context::Ctx; use crate::gas::OutOfGas; -use crate::gas::{self, Gas}; +use crate::gas::{self, tc_cost, Gas}; use crate::irrefutable_match::irrefutable_match; use crate::lexer::Prim; use crate::stack::*; @@ -50,6 +50,8 @@ pub enum TcError { TypesNotEqual(#[from] TypesNotEqual), #[error("DUP 0 is forbidden")] Dup0, + #[error("PAIR {0} is forbidden")] + PairN01(u16), #[error("value {0} is invalid for type {1:?}")] InvalidValueForType(String, Type), #[error("value {0:?} is invalid element for container type {1:?}")] @@ -1205,6 +1207,24 @@ pub(crate) fn typecheck_instruction<'a>( I::Pair } (App(PAIR, [], _), [] | [_]) => no_overload!(PAIR, len 2), + (App(PAIR, [Micheline::Int(n)], _), _) => { + let n = validate_u10(n)?; + if n < 2 { + return Err(TcError::PairN01(n)); + } + if stack.len() < n as usize { + no_overload!(PAIR, len n as usize); + } + ctx.gas.consume(tc_cost::pair_n(n as usize)?)?; + // unwrap is fine, n is non-zero. + let res = stack + .drain_top(n as usize) + .rev() + .reduce(|acc, e| Type::new_pair(e, acc)) + .unwrap(); + stack.push(res); + I::PairN(n) + } (App(PAIR, expect_args!(0), _), _) => unexpected_micheline!(), (App(UNPAIR, [], _), [.., T::Pair(..)]) => { @@ -3496,6 +3516,91 @@ mod typecheck_tests { assert_eq!(stack, tc_stk![Type::new_pair(Type::Nat, Type::Int)]); } + #[test] + fn pair_n_3() { + let mut stack = tc_stk![Type::String, Type::Unit, Type::Int, Type::Nat]; // NB: nat is top + assert_eq!( + typecheck_instruction(&parse("PAIR 3").unwrap(), &mut Ctx::default(), &mut stack), + Ok(PairN(3)) + ); + assert_eq!( + stack, + tc_stk![ + Type::String, + Type::new_pair(Type::Nat, Type::new_pair(Type::Int, Type::Unit)) + ] + ); + } + + #[test] + fn pair_n_4() { + let mut stack = tc_stk![Type::String, Type::Unit, Type::Int, Type::Nat]; // NB: nat is top + assert_eq!( + typecheck_instruction(&parse("PAIR 4").unwrap(), &mut Ctx::default(), &mut stack), + Ok(PairN(4)) + ); + assert_eq!( + stack, + tc_stk![Type::new_pair( + Type::Nat, + Type::new_pair(Type::Int, Type::new_pair(Type::Unit, Type::String)) + )] + ); + } + + #[test] + fn pair_n_neg() { + let mut stack = tc_stk![Type::String, Type::Unit, Type::Int, Type::Nat]; // NB: nat is top + assert_eq!( + typecheck_instruction(&parse("PAIR -1").unwrap(), &mut Ctx::default(), &mut stack), + Err(TcError::ExpectedU10((-1).into())) + ); + } + + #[test] + fn pair_n_0() { + let mut stack = tc_stk![Type::String, Type::Unit, Type::Int, Type::Nat]; // NB: nat is top + assert_eq!( + typecheck_instruction(&parse("PAIR 0").unwrap(), &mut Ctx::default(), &mut stack), + Err(TcError::PairN01(0)) + ); + } + + #[test] + fn pair_n_1() { + let mut stack = tc_stk![Type::String, Type::Unit, Type::Int, Type::Nat]; // NB: nat is top + assert_eq!( + typecheck_instruction(&parse("PAIR 1").unwrap(), &mut Ctx::default(), &mut stack), + Err(TcError::PairN01(1)) + ); + } + + #[test] + fn pair_n_too_large() { + let mut stack = tc_stk![Type::String, Type::Unit, Type::Int, Type::Nat]; // NB: nat is top + assert_eq!( + typecheck_instruction( + &parse("PAIR 1024").unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::ExpectedU10(1024.into())) + ); + } + + #[test] + fn pair_n_too_short() { + let mut stack = tc_stk![Type::Int, Type::Nat]; // NB: nat is top + assert_eq!( + typecheck_instruction(&parse("PAIR 10").unwrap(), &mut Ctx::default(), &mut stack), + Err(TcError::NoMatchingOverload { + instr: Prim::PAIR, + stack: stk![Type::Int, Type::Nat], + reason: Some(NoMatchingOverloadReason::StackTooShort { expected: 10 }) + }) + ); + } + #[test] fn unpair() { let mut stack = tc_stk![Type::new_pair(Type::Nat, Type::Int)]; -- GitLab From 282a2eaa439dc50ee7b6c74cc9610bc17a662479 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Wed, 13 Dec 2023 14:28:06 +0300 Subject: [PATCH 2/5] MIR: UNPAIR n instruction --- contrib/mir/src/ast.rs | 1 + contrib/mir/src/gas.rs | 11 +++ contrib/mir/src/interpreter.rs | 50 ++++++++++++ contrib/mir/src/stack.rs | 4 + contrib/mir/src/typechecker.rs | 142 +++++++++++++++++++++++++++++++-- 5 files changed, 203 insertions(+), 5 deletions(-) diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index d953b91cd6d5..86d630f795a1 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -559,6 +559,7 @@ pub enum Instruction<'a> { Size(overloads::Size), Seq(Vec), Unpair, + UnpairN(u16), Cons, And(overloads::And), Or(overloads::Or), diff --git a/contrib/mir/src/gas.rs b/contrib/mir/src/gas.rs index cadfd157f305..68489d1f1ec8 100644 --- a/contrib/mir/src/gas.rs +++ b/contrib/mir/src/gas.rs @@ -215,6 +215,11 @@ pub mod tc_cost { // corresponds to Cost_of.Typechecking.proof_argument in the protocol (Checked::from(size) * 50).as_gas_cost() } + + pub fn unpair_n(size: usize) -> Result { + // corresponds to Cost_of.Typechecking.proof_argument in the protocol + (Checked::from(size) * 50).as_gas_cost() + } } pub trait BigIntByteSize { @@ -825,6 +830,12 @@ pub mod interpret_cost { let v0 = size - 2; (40 + ((v0 >> 2) + (v0 * 3))).as_gas_cost() } + + pub fn unpair_n(size: usize) -> Result { + let size = Checked::from(size); + let v0 = size - 2; + (30 + (v0 * 4)).as_gas_cost() + } } #[cfg(test)] diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index 9d94b78b1fac..ad96893647d9 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -717,6 +717,22 @@ fn interpret_one<'a>( stack.push(r); stack.push(l); } + I::UnpairN(n) => { + ctx.gas.consume(interpret_cost::unpair_n(*n as usize)?)?; + fn fill<'a>(n: u16, stack: &mut IStack<'a>, p: TypedValue<'a>) { + if n == 0 { + stack.push(p); + } else if let V::Pair(p) = p { + fill(n - 1, stack, p.1); + stack.push(p.0); + } else { + unreachable_state(); + } + } + let p = pop!(); + stack.reserve(*n as usize); + fill(n - 1, stack, p); + } I::ISome => { ctx.gas.consume(interpret_cost::SOME)?; let v = pop!(); @@ -2394,6 +2410,40 @@ mod interpreter_tests { assert_eq!(stack, stk![V::nat(42), V::Bool(false)]); } + #[test] + fn unpair_n_3() { + let mut stack = stk![V::new_pair( + V::Bool(false), + V::new_pair(V::nat(42), V::new_pair(V::Unit, V::String("foo".into()))) + )]; + let ctx = &mut Ctx::default(); + assert_eq!(interpret_one(&UnpairN(3), ctx, &mut stack), Ok(())); + assert_eq!( + stack, + stk![ + V::new_pair(V::Unit, V::String("foo".into())), + V::nat(42), + V::Bool(false) + ], + ); + assert!(ctx.gas.milligas() < Ctx::default().gas.milligas()) + } + + #[test] + fn unpair_n_4() { + let mut stack = stk![V::new_pair( + V::Bool(false), + V::new_pair(V::nat(42), V::new_pair(V::Unit, V::String("foo".into()))) + )]; + let ctx = &mut Ctx::default(); + assert_eq!(interpret_one(&UnpairN(4), ctx, &mut stack), Ok(())); + assert_eq!( + stack, + stk![V::String("foo".into()), V::Unit, V::nat(42), V::Bool(false)], + ); + assert!(ctx.gas.milligas() < Ctx::default().gas.milligas()) + } + #[test] fn pair_car() { let mut stack = stk![V::nat(42), V::Bool(false)]; // NB: bool is top diff --git a/contrib/mir/src/stack.rs b/contrib/mir/src/stack.rs index 845a61bca57e..2c025e534876 100644 --- a/contrib/mir/src/stack.rs +++ b/contrib/mir/src/stack.rs @@ -135,6 +135,10 @@ impl Stack { .rev() } + pub fn reserve(&mut self, additional: usize) { + self.0.reserve(additional) + } + /// Borrow the stack content as an immutable slice. Note that stack top is /// the _rightmost_ element. pub fn as_slice(&self) -> &[T] { diff --git a/contrib/mir/src/typechecker.rs b/contrib/mir/src/typechecker.rs index 909988820662..c01d997af83d 100644 --- a/contrib/mir/src/typechecker.rs +++ b/contrib/mir/src/typechecker.rs @@ -50,8 +50,8 @@ pub enum TcError { TypesNotEqual(#[from] TypesNotEqual), #[error("DUP 0 is forbidden")] Dup0, - #[error("PAIR {0} is forbidden")] - PairN01(u16), + #[error("{0} {1} is forbidden")] + PairN01(Prim, u16), #[error("value {0} is invalid for type {1:?}")] InvalidValueForType(String, Type), #[error("value {0:?} is invalid element for container type {1:?}")] @@ -1210,7 +1210,7 @@ pub(crate) fn typecheck_instruction<'a>( (App(PAIR, [Micheline::Int(n)], _), _) => { let n = validate_u10(n)?; if n < 2 { - return Err(TcError::PairN01(n)); + return Err(TcError::PairN01(PAIR, n)); } if stack.len() < n as usize { no_overload!(PAIR, len n as usize); @@ -1235,6 +1235,33 @@ pub(crate) fn typecheck_instruction<'a>( } (App(UNPAIR, [], _), [.., ty]) => no_overload!(UNPAIR, NMOR::ExpectedPair(ty.clone())), (App(UNPAIR, [], _), []) => no_overload!(UNPAIR, len 1), + (App(UNPAIR, [Micheline::Int(n)], _), [.., _]) => { + let n = validate_u10(n)?; + if n < 2 { + return Err(TcError::PairN01(UNPAIR, n)); + } + ctx.gas.consume(tc_cost::unpair_n(n as usize)?)?; + fn fill(n: u16, stack: &mut Stack, p: &Type) -> Result<(), TcError> { + if n == 0 { + stack.push(p.clone()); + } else if let Type::Pair(p) = p { + fill(n - 1, stack, &p.1)?; + stack.push(p.0.clone()); + } else { + return Err(TcError::NoMatchingOverload { + instr: UNPAIR, + stack: stack.clone(), + reason: Option::Some(NMOR::ExpectedPair(p.clone())), + }); + } + Ok(()) + } + stack.reserve(n as usize); + let p = pop!(); + fill(n - 1, stack, &p)?; + I::UnpairN(n) + } + (App(UNPAIR, [Micheline::Int(_)], _), []) => no_overload!(UNPAIR, len 1), (App(UNPAIR, expect_args!(0), _), _) => unexpected_micheline!(), (App(SOME, [], _), [.., _]) => { @@ -3562,7 +3589,7 @@ mod typecheck_tests { let mut stack = tc_stk![Type::String, Type::Unit, Type::Int, Type::Nat]; // NB: nat is top assert_eq!( typecheck_instruction(&parse("PAIR 0").unwrap(), &mut Ctx::default(), &mut stack), - Err(TcError::PairN01(0)) + Err(TcError::PairN01(Prim::PAIR, 0)) ); } @@ -3571,7 +3598,7 @@ mod typecheck_tests { let mut stack = tc_stk![Type::String, Type::Unit, Type::Int, Type::Nat]; // NB: nat is top assert_eq!( typecheck_instruction(&parse("PAIR 1").unwrap(), &mut Ctx::default(), &mut stack), - Err(TcError::PairN01(1)) + Err(TcError::PairN01(Prim::PAIR, 1)) ); } @@ -3611,6 +3638,111 @@ mod typecheck_tests { assert_eq!(stack, tc_stk![Type::Int, Type::Nat]); } + #[test] + fn unpair_n_3() { + let mut stack = tc_stk![Type::new_pair( + Type::Nat, + Type::new_pair(Type::Int, Type::new_pair(Type::Unit, Type::String)) + )]; + assert_eq!( + typecheck_instruction(&parse("UNPAIR 3").unwrap(), &mut Ctx::default(), &mut stack), + Ok(UnpairN(3)) + ); + assert_eq!( + stack, + tc_stk![ + Type::new_pair(Type::Unit, Type::String), + Type::Int, + Type::Nat + ] + ) + } + + #[test] + fn unpair_n_4() { + let mut stack = tc_stk![Type::new_pair( + Type::Nat, + Type::new_pair(Type::Int, Type::new_pair(Type::Unit, Type::String)) + )]; + assert_eq!( + typecheck_instruction(&parse("UNPAIR 4").unwrap(), &mut Ctx::default(), &mut stack), + Ok(UnpairN(4)) + ); + assert_eq!( + stack, + tc_stk![Type::String, Type::Unit, Type::Int, Type::Nat], + ); + } + + #[test] + fn unpair_n_neg() { + let mut stack = tc_stk![Type::new_pair( + Type::Nat, + Type::new_pair(Type::Int, Type::new_pair(Type::Unit, Type::String)) + )]; + assert_eq!( + typecheck_instruction( + &parse("UNPAIR -1").unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::ExpectedU10((-1).into())) + ); + } + + #[test] + fn unpair_n_0() { + let mut stack = tc_stk![Type::new_pair( + Type::Nat, + Type::new_pair(Type::Int, Type::new_pair(Type::Unit, Type::String)) + )]; + assert_eq!( + typecheck_instruction(&parse("UNPAIR 0").unwrap(), &mut Ctx::default(), &mut stack), + Err(TcError::PairN01(Prim::UNPAIR, 0)) + ); + } + + #[test] + fn unpair_n_1() { + let mut stack = tc_stk![Type::new_pair( + Type::Nat, + Type::new_pair(Type::Int, Type::new_pair(Type::Unit, Type::String)) + )]; + assert_eq!( + typecheck_instruction(&parse("UNPAIR 1").unwrap(), &mut Ctx::default(), &mut stack), + Err(TcError::PairN01(Prim::UNPAIR, 1)) + ); + } + + #[test] + fn unpair_n_too_large() { + let mut stack = tc_stk![Type::new_pair( + Type::Nat, + Type::new_pair(Type::Int, Type::new_pair(Type::Unit, Type::String)) + )]; + assert_eq!( + typecheck_instruction( + &parse("UNPAIR 1024").unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::ExpectedU10(1024.into())) + ); + } + + #[test] + fn unpair_n_too_short() { + let mut stack = tc_stk![]; // NB: nat is top + assert_eq!( + typecheck_instruction(&parse("UNPAIR 2").unwrap(), &mut Ctx::default(), &mut stack), + Err(TcError::NoMatchingOverload { + instr: Prim::UNPAIR, + stack: stk![], + reason: Some(NoMatchingOverloadReason::StackTooShort { expected: 1 }) + }) + ); + } + #[test] fn pair_car() { let mut stack = tc_stk![Type::Int, Type::Nat]; // NB: nat is top -- GitLab From 28466662284b2956a3dc5b8b20f0fe3202d1dfe1 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Wed, 13 Dec 2023 15:44:07 +0300 Subject: [PATCH 3/5] MIR: GET n instruction --- contrib/mir/src/ast.rs | 1 + contrib/mir/src/gas.rs | 10 +++ contrib/mir/src/interpreter.rs | 69 +++++++++++++++ contrib/mir/src/typechecker.rs | 154 +++++++++++++++++++++++++++++++++ 4 files changed, 234 insertions(+) diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index 86d630f795a1..7ff7582f6b51 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -553,6 +553,7 @@ pub enum Instruction<'a> { EmptyBigMap(Type, Type), Mem(overloads::Mem), Get(overloads::Get), + GetN(u16), Update(overloads::Update), GetAndUpdate(overloads::GetAndUpdate), Concat(overloads::Concat), diff --git a/contrib/mir/src/gas.rs b/contrib/mir/src/gas.rs index 68489d1f1ec8..0ebf6aac14fa 100644 --- a/contrib/mir/src/gas.rs +++ b/contrib/mir/src/gas.rs @@ -220,6 +220,11 @@ pub mod tc_cost { // corresponds to Cost_of.Typechecking.proof_argument in the protocol (Checked::from(size) * 50).as_gas_cost() } + + pub fn get_n(size: usize) -> Result { + // corresponds to Cost_of.Typechecking.proof_argument in the protocol + (Checked::from(size) * 50).as_gas_cost() + } } pub trait BigIntByteSize { @@ -836,6 +841,11 @@ pub mod interpret_cost { let v0 = size - 2; (30 + (v0 * 4)).as_gas_cost() } + + pub fn get_n(size: usize) -> Result { + let size = Checked::from(size); + (20 + ((size >> 1) + (size >> 4))).as_gas_cost() + } } #[cfg(test)] diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index ad96893647d9..d5c28097e06e 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -882,6 +882,12 @@ fn interpret_one<'a>( stack.push(V::new_option(result)); } }, + I::GetN(n) => { + ctx.gas.consume(interpret_cost::get_n(*n as usize)?)?; + let res = get_nth_field_ref(*n, &mut stack[0]); + // this is a bit hacky, but borrow rules leave few other options + stack[0] = std::mem::replace(res, V::Unit); + } I::Update(overload) => match overload { overloads::Update::Set => { let key = pop!(); @@ -1360,6 +1366,25 @@ fn compute_contract_address(operation_group_hash: &[u8; 32], o_index: u32) -> Ad } } +fn get_nth_field_ref<'a, 'b>( + mut m: u16, + mut val: &'a mut TypedValue<'b>, +) -> &'a mut TypedValue<'b> { + use TypedValue as V; + loop { + match (m, val) { + (0, val_) => break val_, + (1, V::Pair(p)) => break &mut p.0, + + (_, V::Pair(p)) => { + val = &mut p.1; + m -= 2; + } + _ => unreachable_state(), + } + } +} + #[cfg(test)] mod interpreter_tests { use std::collections::{BTreeMap, BTreeSet, HashMap}; @@ -2773,6 +2798,50 @@ mod interpreter_tests { ); } + mod get_n { + use super::*; + + #[track_caller] + fn check(n: u16, val: TypedValue, field_val: TypedValue) { + let mut stack = stk![val]; + assert_eq!( + interpret_one(&GetN(n), &mut Ctx::default(), &mut stack), + Ok(()) + ); + assert_eq!(stack, stk![field_val]) + } + + #[test] + fn ok_0() { + let val = V::new_pair(V::int(1), V::new_pair(V::int(3), V::int(4))); + check(0, val.clone(), val); + } + + #[test] + fn ok_1() { + let val = V::new_pair(V::int(1), V::new_pair(V::int(3), V::int(4))); + check(1, val, V::int(1)); + } + + #[test] + fn ok_2() { + let val = V::new_pair(V::int(1), V::new_pair(V::int(3), V::int(4))); + check(2, val, V::new_pair(V::int(3), V::int(4))); + } + + #[test] + fn ok_3() { + let val = V::new_pair(V::int(1), V::new_pair(V::int(3), V::int(4))); + check(3, val, V::int(3)); + } + + #[test] + fn ok_4() { + let val = V::new_pair(V::int(1), V::new_pair(V::int(3), V::int(4))); + check(4, val, V::int(4)); + } + } + #[test] fn mem_map() { let mut ctx = Ctx::default(); diff --git a/contrib/mir/src/typechecker.rs b/contrib/mir/src/typechecker.rs index c01d997af83d..6585014988cc 100644 --- a/contrib/mir/src/typechecker.rs +++ b/contrib/mir/src/typechecker.rs @@ -1399,6 +1399,23 @@ pub(crate) fn typecheck_instruction<'a>( } (App(GET, [], _), [.., _, _]) => no_overload!(GET), (App(GET, [], _), [] | [_]) => no_overload!(GET, len 2), + + (App(GET, [Micheline::Int(n)], _), [.., _]) => { + // NB: it's important to NOT pop from the stack here, otherwise + // no_overload! below won't report the type on the top of the stack. + let ty = &mut stack[0]; + let n = validate_u10(n)?; + ctx.gas.consume(tc_cost::get_n(n as usize)?)?; + let res = match get_nth_field_ref(n, ty) { + Ok(res) => res, + Err(ty) => no_overload!(GET, NMOR::ExpectedPair(ty)), + }; + // this is a bit hacky, but borrow rules leave few other options + stack[0] = std::mem::replace(res, T::Unit); + I::GetN(n) + } + (App(GET, [Micheline::Int(_)], _), []) => no_overload!(GET, len 1), + (App(GET, expect_args!(0), _), _) => unexpected_micheline!(), (App(UPDATE, [], _), [.., T::Set(ty), T::Bool, ty_]) => { @@ -1922,6 +1939,23 @@ pub(crate) fn typecheck_contract_address( } } +fn get_nth_field_ref(mut m: u16, mut ty: &mut Type) -> Result<&mut Type, Type> { + Ok(loop { + match (m, ty) { + (0, ty_) => break ty_, + (1, Type::Pair(p)) => break &mut Rc::make_mut(p).0, + (_, Type::Pair(p)) => { + ty = &mut Rc::make_mut(p).1; + m -= 2; + } + (_, ty) => { + let ty = ty.clone(); + return Err(ty); + } + } + }) +} + /// Typecheck a value. Assumes passed the type is valid, i.e. doesn't contain /// illegal types like `set operation` or `contract operation`. pub(crate) fn typecheck_value<'a>( @@ -4392,6 +4426,126 @@ mod typecheck_tests { ); } + mod get_n { + use super::*; + + #[track_caller] + fn check(n: u16, ty: Type, field_ty: Type) { + let mut stack = tc_stk![ty]; + assert_eq!( + typecheck_instruction( + &parse(&format!("GET {n}")).unwrap(), + &mut Ctx::default(), + &mut stack + ), + Ok(GetN(n)) + ); + assert_eq!(stack, tc_stk![field_ty]) + } + + #[test] + fn ok_0() { + let ty = Type::new_pair( + Type::Unit, + Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)), + ); + check(0, ty.clone(), ty); + } + + #[test] + fn ok_1() { + let ty = Type::new_pair( + Type::Unit, + Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)), + ); + check(1, ty, Type::Unit); + } + + #[test] + fn ok_2() { + let ty = Type::new_pair( + Type::Unit, + Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)), + ); + check( + 2, + ty, + Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)), + ); + } + + #[test] + fn ok_3() { + let ty = Type::new_pair( + Type::Unit, + Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)), + ); + check(3, ty, Type::Nat); + } + + #[test] + fn ok_4() { + let ty = Type::new_pair( + Type::Unit, + Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)), + ); + check(4, ty, Type::new_pair(Type::String, Type::Int)); + } + + #[test] + fn ok_5() { + let ty = Type::new_pair( + Type::Unit, + Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)), + ); + check(5, ty, Type::String); + } + + #[test] + fn ok_6() { + let ty = Type::new_pair( + Type::Unit, + Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)), + ); + check(6, ty, Type::Int); + } + + #[test] + fn fail_7() { + let ty = Type::new_pair( + Type::Unit, + Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)), + ); + let mut stack = tc_stk![ty.clone()]; + assert_eq!( + typecheck_instruction(&parse("GET 7").unwrap(), &mut Ctx::default(), &mut stack), + Err(TcError::NoMatchingOverload { + instr: Prim::GET, + stack: stk![ty], + reason: Some(NoMatchingOverloadReason::ExpectedPair(Type::Int)) + }) + ); + } + + #[test] + fn too_short() { + too_short_test(&app!(GET[0]), Prim::GET, 1); + } + + #[test] + fn too_large() { + let ty = Type::new_pair( + Type::Unit, + Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)), + ); + let mut stack = tc_stk![ty]; + assert_eq!( + typecheck_instruction(&parse("GET 1024").unwrap(), &mut Ctx::default(), &mut stack), + Err(TcError::ExpectedU10(1024.into())) + ); + } + } + #[test] fn mem_map() { let mut stack = tc_stk![Type::new_map(Type::Int, Type::String), Type::Int]; -- GitLab From c3f2792ba78a53dcd3f4d5ac4ec911a5933a0949 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Wed, 13 Dec 2023 16:40:09 +0300 Subject: [PATCH 4/5] MIR: UPDATE n instruction --- contrib/mir/src/ast.rs | 1 + contrib/mir/src/gas.rs | 10 +++ contrib/mir/src/interpreter.rs | 62 ++++++++++++++++++ contrib/mir/src/typechecker.rs | 112 +++++++++++++++++++++++++++++++++ 4 files changed, 185 insertions(+) diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index 7ff7582f6b51..2dcc71aa0d8a 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -558,6 +558,7 @@ pub enum Instruction<'a> { GetAndUpdate(overloads::GetAndUpdate), Concat(overloads::Concat), Size(overloads::Size), + UpdateN(u16), Seq(Vec), Unpair, UnpairN(u16), diff --git a/contrib/mir/src/gas.rs b/contrib/mir/src/gas.rs index 0ebf6aac14fa..f024c091d5e8 100644 --- a/contrib/mir/src/gas.rs +++ b/contrib/mir/src/gas.rs @@ -225,6 +225,11 @@ pub mod tc_cost { // corresponds to Cost_of.Typechecking.proof_argument in the protocol (Checked::from(size) * 50).as_gas_cost() } + + pub fn update_n(size: usize) -> Result { + // corresponds to Cost_of.Typechecking.proof_argument in the protocol + (Checked::from(size) * 50).as_gas_cost() + } } pub trait BigIntByteSize { @@ -846,6 +851,11 @@ pub mod interpret_cost { let size = Checked::from(size); (20 + ((size >> 1) + (size >> 4))).as_gas_cost() } + + pub fn update_n(size: usize) -> Result { + let size = Checked::from(size); + (30 + ((size >> 5) + ((size >> 2) + size))).as_gas_cost() + } } #[cfg(test)] diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index d5c28097e06e..56e020e490e7 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -964,6 +964,12 @@ fn interpret_one<'a>( overloads::Size::Map => run_size!(Map, SIZE_MAP), } } + I::UpdateN(n) => { + ctx.gas.consume(interpret_cost::update_n(*n as usize)?)?; + let new_val = pop!(); + let field = get_nth_field_ref(*n, &mut stack[0]); + *field = new_val; + } I::ChainId => { ctx.gas.consume(interpret_cost::CHAIN_ID)?; stack.push(V::ChainId(ctx.chain_id.clone())); @@ -2842,6 +2848,62 @@ mod interpreter_tests { } } + mod update_n { + use super::*; + + #[track_caller] + fn check(n: u16, val: TypedValue, new_val: TypedValue) { + let mut stack = stk![val, TypedValue::nat(100500)]; + assert_eq!( + interpret_one(&UpdateN(n), &mut Ctx::default(), &mut stack), + Ok(()) + ); + assert_eq!(stack, stk![new_val]) + } + + #[test] + fn ok_0() { + let val = V::new_pair(V::int(1), V::new_pair(V::int(3), V::int(4))); + check(0, val, V::nat(100500)); + } + + #[test] + fn ok_1() { + let val = V::new_pair(V::int(1), V::new_pair(V::int(3), V::int(4))); + check( + 1, + val, + V::new_pair(V::nat(100500), V::new_pair(V::int(3), V::int(4))), + ); + } + + #[test] + fn ok_2() { + let val = V::new_pair(V::int(1), V::new_pair(V::int(3), V::int(4))); + check(2, val, V::new_pair(V::int(1), V::nat(100500))); + } + + #[test] + fn ok_3() { + let val = V::new_pair(V::int(1), V::new_pair(V::int(3), V::int(4))); + check( + 3, + val, + V::new_pair(V::int(1), V::new_pair(V::nat(100500), V::int(4))), + ); + } + + #[test] + fn ok_4() { + let val = V::new_pair(V::int(1), V::new_pair(V::int(3), V::int(4))); + check( + 4, + val, + V::new_pair(V::int(1), V::new_pair(V::int(3), V::nat(100500))), + ); + } + } + #[test] fn mem_map() { let mut ctx = Ctx::default(); diff --git a/contrib/mir/src/typechecker.rs b/contrib/mir/src/typechecker.rs index 6585014988cc..4d131bea6960 100644 --- a/contrib/mir/src/typechecker.rs +++ b/contrib/mir/src/typechecker.rs @@ -1439,6 +1439,23 @@ pub(crate) fn typecheck_instruction<'a>( } (App(UPDATE, [], _), [.., _, _, _]) => no_overload!(UPDATE), (App(UPDATE, [], _), [] | [_] | [_, _]) => no_overload!(UPDATE, len 3), + + (App(UPDATE, [Micheline::Int(n)], _), [.., _, _]) => { + let n = validate_u10(n)?; + let new_val = pop!(); + let old_val = match get_nth_field_ref(n, &mut stack[0]) { + Ok(res) => res, + Err(ty) => { + // restores the initial stack + stack.push(new_val); + no_overload!(UPDATE, NMOR::ExpectedPair(ty)); + } + }; + *old_val = new_val; + I::UpdateN(n) + } + (App(UPDATE, [Micheline::Int(_)], _), [] | [_]) => no_overload!(UPDATE, len 2), + (App(UPDATE, expect_args!(0), _), _) => unexpected_micheline!(), (App(GET_AND_UPDATE, [], _), [.., T::Map(m), T::Option(vty_new), kty_]) => { @@ -4546,6 +4563,101 @@ mod typecheck_tests { } } + mod update_n { + use super::*; + + #[track_caller] + fn check(n: u16, ty: Type, new_ty: Type) { + let mut stack = tc_stk![ty, Type::Unit]; + assert_eq!( + typecheck_instruction( + &parse(&format!("UPDATE {n}")).unwrap(), + &mut Ctx::default(), + &mut stack + ), + Ok(UpdateN(n)) + ); + assert_eq!(stack, tc_stk![new_ty]) + } + + #[test] + fn ok_0() { + let ty = Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)); + check(0, ty, Type::Unit); + } + + #[test] + fn ok_1() { + let ty = Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)); + check( + 1, + ty, + Type::new_pair(Type::Unit, Type::new_pair(Type::String, Type::Int)), + ); + } + + #[test] + fn ok_2() { + let ty = Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)); + check(2, ty, Type::new_pair(Type::Nat, Type::Unit)); + } + + #[test] + fn ok_3() { + let ty = Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)); + check( + 3, + ty, + Type::new_pair(Type::Nat, Type::new_pair(Type::Unit, Type::Int)), + ); + } + + #[test] + fn ok_4() { + let ty = Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)); + check( + 4, + ty, + Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Unit)), + ); + } + + #[test] + fn fail_5() { + let ty = Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)); + + let mut stack = tc_stk![ty.clone(), Type::Unit]; + assert_eq!( + typecheck_instruction(&parse("UPDATE 5").unwrap(), &mut Ctx::default(), &mut stack), + Err(TcError::NoMatchingOverload { + instr: Prim::UPDATE, + stack: stk![ty, Type::Unit], + reason: Some(NoMatchingOverloadReason::ExpectedPair(Type::Int)) + }) + ); + } + + #[test] + fn too_short() { + too_short_test(&app!(UPDATE[0]), Prim::UPDATE, 2); + } + + #[test] + fn too_large() { + let ty = Type::new_pair(Type::Nat, Type::new_pair(Type::String, Type::Int)); + + let mut stack = tc_stk![ty, Type::Unit]; + assert_eq!( + typecheck_instruction( + &parse("UPDATE 1024").unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::ExpectedU10(1024.into())) + ); + } + } + #[test] fn mem_map() { let mut stack = tc_stk![Type::new_map(Type::Int, Type::String), Type::Int]; -- GitLab From b101a7319f48c54dc292bfb0b5481d5ca5df3ad3 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Wed, 13 Dec 2023 17:07:52 +0300 Subject: [PATCH 5/5] MIR: more tests for GET_AND_UPDATE (map variant) --- contrib/mir/src/interpreter.rs | 86 ++++++++++++++++++++++++++++++++++ 1 file changed, 86 insertions(+) diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index 56e020e490e7..b5d9d0217fab 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -3278,6 +3278,92 @@ mod interpreter_tests { assert_eq!(stack, stk![TypedValue::nat(2)]); } + #[test] + fn get_and_update_map_insert() { + let mut ctx = Ctx::default(); + let map = BTreeMap::new(); + let mut stack = stk![ + V::Map(map), + V::new_option(Some(V::String("foo".to_owned()))), + V::int(1) + ]; + assert_eq!( + interpret_one( + &GetAndUpdate(overloads::GetAndUpdate::Map), + &mut ctx, + &mut stack + ), + Ok(()) + ); + assert_eq!( + stack, + stk![ + V::Map(BTreeMap::from([(V::int(1), V::String("foo".to_owned()))])), + V::new_option(None), + ] + ); + assert_eq!( + ctx.gas.milligas(), + Gas::default().milligas() - interpret_cost::map_get_and_update(&V::int(1), 0).unwrap() + ); + } + + #[test] + fn get_and_update_map_update() { + let mut ctx = Ctx::default(); + let map = BTreeMap::from([(V::int(1), V::String("bar".to_owned()))]); + let mut stack = stk![ + V::Map(map), + V::new_option(Some(V::String("foo".to_owned()))), + V::int(1) + ]; + assert_eq!( + interpret_one( + &GetAndUpdate(overloads::GetAndUpdate::Map), + &mut ctx, + &mut stack + ), + Ok(()) + ); + assert_eq!( + stack, + stk![ + V::Map(BTreeMap::from([(V::int(1), V::String("foo".to_owned()))])), + V::new_option(Some(V::String("bar".into()))) + ] + ); + assert_eq!( + ctx.gas.milligas(), + Gas::default().milligas() - interpret_cost::map_get_and_update(&V::int(1), 1).unwrap() + ); + } + + #[test] + fn get_and_update_map_remove() { + let mut ctx = Ctx::default(); + let map = BTreeMap::from([(V::int(1), V::String("bar".to_owned()))]); + let mut stack = stk![V::Map(map), V::new_option(None), V::int(1)]; + assert_eq!( + interpret_one( + &GetAndUpdate(overloads::GetAndUpdate::Map), + &mut ctx, + &mut stack + ), + Ok(()) + ); + assert_eq!( + stack, + stk![ + V::Map(BTreeMap::new()), + V::new_option(Some(V::String("bar".into()))), + ] + ); + assert_eq!( + ctx.gas.milligas(), + Gas::default().milligas() - interpret_cost::map_get_and_update(&V::int(1), 1).unwrap() + ); + } + #[test] fn update_big_map() { fn check<'a>( -- GitLab