From ea3ab02d251a7015d0b332de0b719726ed683754 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Tue, 21 Nov 2023 13:36:16 +0300 Subject: [PATCH 1/5] MIR: add lambda type --- contrib/mir/src/ast.rs | 7 ++++++- contrib/mir/src/typechecker.rs | 16 ++++++++++++++++ contrib/mir/src/typechecker/type_props.rs | 9 +++++++++ 3 files changed, 31 insertions(+), 1 deletion(-) diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index 18e8dd4875b1..6bcb3b17fd4f 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -78,6 +78,7 @@ pub enum Type { Key, Signature, KeyHash, + Lambda(Box<(Type, Type)>), } impl Type { @@ -88,7 +89,7 @@ impl Type { match self { Nat | Int | Bool | Mutez | String | Unit | Never | Operation | Address | ChainId | Bytes | Key | Signature | KeyHash => 1, - Pair(p) | Or(p) | Map(p) => 1 + p.0.size_for_gas() + p.1.size_for_gas(), + Pair(p) | Or(p) | Map(p) | Lambda(p) => 1 + p.0.size_for_gas() + p.1.size_for_gas(), Option(x) | List(x) | Set(x) | Contract(x) => 1 + x.size_for_gas(), } } @@ -120,6 +121,10 @@ impl Type { pub fn new_contract(ty: Self) -> Self { Self::Contract(Box::new(ty)) } + + pub fn new_lambda(ty1: Self, ty2: Self) -> Self { + Self::Lambda(Box::new((ty1, ty2))) + } } #[derive(Debug, Clone, Eq, PartialEq)] diff --git a/contrib/mir/src/typechecker.rs b/contrib/mir/src/typechecker.rs index 93dea6ad6b3f..e6e0e98263f1 100644 --- a/contrib/mir/src/typechecker.rs +++ b/contrib/mir/src/typechecker.rs @@ -334,6 +334,9 @@ fn parse_ty_with_entrypoints( App(list, [t], _) => Type::new_list(parse_ty(ctx, t)?), App(list, ..) => unexpected()?, + App(lambda, [ty1, ty2], _) => Type::new_lambda(parse_ty(ctx, ty1)?, parse_ty(ctx, ty2)?), + App(lambda, ..) => unexpected()?, + App(contract, [t], _) => { let t = parse_ty(ctx, t)?; // NB: despite `contract` type being duplicable and packable, its @@ -4100,4 +4103,17 @@ mod typecheck_tests { }) ); } + + #[test] + fn push_lambda_wrong_type() { + assert_eq!( + parse("PUSH (lambda unit unit) Unit") + .unwrap() + .typecheck_instruction(&mut Ctx::default(), None, &[]), + Err(TcError::InvalidValueForType( + "App(Unit, [], [])".to_owned(), + Type::new_lambda(Type::Unit, Type::Unit) + )) + ); + } } diff --git a/contrib/mir/src/typechecker/type_props.rs b/contrib/mir/src/typechecker/type_props.rs index 9248f55503ee..46234b5e2da0 100644 --- a/contrib/mir/src/typechecker/type_props.rs +++ b/contrib/mir/src/typechecker/type_props.rs @@ -91,6 +91,15 @@ impl Type { | TypeProperty::Pushable | TypeProperty::BigMapValue => return invalid_type_prop(), }, + Lambda(_) => match prop { + TypeProperty::Comparable => return invalid_type_prop(), + TypeProperty::Passable + | TypeProperty::Storable + | TypeProperty::Pushable + | TypeProperty::Packable + | TypeProperty::BigMapValue + | TypeProperty::Duplicable => (), + }, } Ok(()) } -- GitLab From 12d79fdc8cdba0c033237d885a28186b308928c6 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Tue, 21 Nov 2023 16:21:23 +0300 Subject: [PATCH 2/5] MIR: add Micheline seq smart constructor --- contrib/mir/src/ast/micheline.rs | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/contrib/mir/src/ast/micheline.rs b/contrib/mir/src/ast/micheline.rs index d35e9311315c..da2dd8d06758 100644 --- a/contrib/mir/src/ast/micheline.rs +++ b/contrib/mir/src/ast/micheline.rs @@ -40,6 +40,13 @@ impl<'a> Micheline<'a> { ) -> Self { Micheline::App(prim, arena.alloc_extend([arg1, arg2]), NO_ANNS) } + + pub fn seq( + arena: &'a Arena>, + args: impl IntoIterator>, + ) -> Self { + Micheline::Seq(arena.alloc_extend(args)) + } } impl<'a> From for Micheline<'a> { -- GitLab From 9e276e1e012d1e91824fb2f35a5ad34bb6daf585 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Tue, 21 Nov 2023 16:21:38 +0300 Subject: [PATCH 3/5] MIR: add lambda values (no untyping yet) --- contrib/mir/src/ast.rs | 4 ++++ contrib/mir/src/ast/comparable.rs | 2 +- contrib/mir/src/ast/michelson_lambda.rs | 14 ++++++++++++++ contrib/mir/src/gas.rs | 12 +++++++++--- 4 files changed, 28 insertions(+), 4 deletions(-) create mode 100644 contrib/mir/src/ast/michelson_lambda.rs diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index 6bcb3b17fd4f..ee20f143775f 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -12,6 +12,7 @@ pub mod micheline; pub mod michelson_address; pub mod michelson_key; pub mod michelson_key_hash; +pub mod michelson_lambda; pub mod michelson_list; pub mod michelson_signature; pub mod or; @@ -29,6 +30,7 @@ pub use byte_repr_trait::{ByteReprError, ByteReprTrait}; pub use michelson_address::*; pub use michelson_key::Key; pub use michelson_key_hash::KeyHash; +pub use michelson_lambda::Lambda; pub use michelson_list::MichelsonList; pub use michelson_signature::Signature; pub use or::Or; @@ -147,6 +149,7 @@ pub enum TypedValue { Bytes(Vec), Key(Key), Signature(Signature), + Lambda(Lambda), KeyHash(KeyHash), Operation(Box), } @@ -194,6 +197,7 @@ pub fn typed_value_to_value_optimized_legacy<'a>( TV::Bytes(x) => V::Bytes(x), TV::Key(k) => V::Bytes(k.to_bytes_vec()), TV::Signature(s) => V::Bytes(s.to_bytes_vec()), + TV::Lambda(_) => todo!(), TV::KeyHash(s) => V::Bytes(s.to_bytes_vec()), TV::Contract(x) => go(TV::Address(x)), TV::Operation(operation_info) => match operation_info.operation { diff --git a/contrib/mir/src/ast/comparable.rs b/contrib/mir/src/ast/comparable.rs index 99a10a2acfc6..50579d7cd9d7 100644 --- a/contrib/mir/src/ast/comparable.rs +++ b/contrib/mir/src/ast/comparable.rs @@ -50,7 +50,7 @@ impl PartialOrd for TypedValue { (KeyHash(..), _) => None, // non-comparable types - (List(..) | Set(..) | Map(..) | Contract(..) | Operation(_), _) => None, + (List(..) | Set(..) | Map(..) | Contract(..) | Operation(_) | Lambda(..), _) => None, } } } diff --git a/contrib/mir/src/ast/michelson_lambda.rs b/contrib/mir/src/ast/michelson_lambda.rs new file mode 100644 index 000000000000..7d37e4d19c41 --- /dev/null +++ b/contrib/mir/src/ast/michelson_lambda.rs @@ -0,0 +1,14 @@ +/******************************************************************************/ +/* */ +/* SPDX-License-Identifier: MIT */ +/* Copyright (c) [2023] Serokell */ +/* */ +/******************************************************************************/ + +use super::Instruction; + +#[derive(Debug, Clone, Eq, PartialEq)] +pub enum Lambda { + Lambda { code: Vec }, + LambdaRec { code: Vec }, +} diff --git a/contrib/mir/src/gas.rs b/contrib/mir/src/gas.rs index a73afdaed70c..51c776d4b0b1 100644 --- a/contrib/mir/src/gas.rs +++ b/contrib/mir/src/gas.rs @@ -371,9 +371,15 @@ pub mod interpret_cost { .as_gas_cost()?, (V::Or(..), _) => incomparable(), - (V::List(..) | V::Set(..) | V::Map(..) | V::Contract(_) | V::Operation(_), _) => { - incomparable() - } + ( + V::List(..) + | V::Set(..) + | V::Map(..) + | V::Contract(_) + | V::Operation(_) + | V::Lambda(_), + _, + ) => incomparable(), }) } -- GitLab From eeea62e6ef994fbc6b9a88bbcc18a8a843b03a19 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Tue, 21 Nov 2023 16:23:00 +0300 Subject: [PATCH 4/5] MIR: untype lambdas --- contrib/mir/src/ast.rs | 51 ++++++----- contrib/mir/src/ast/comparable.rs | 4 +- contrib/mir/src/ast/michelson_lambda.rs | 14 ++- contrib/mir/src/interpreter.rs | 54 ++++++----- contrib/mir/src/lib.rs | 115 +++++++++++++++++------- contrib/mir/src/stack.rs | 2 +- contrib/mir/src/typechecker.rs | 34 +++---- contrib/mir/src/tzt.rs | 39 +++++--- contrib/mir/src/tzt/expectation.rs | 4 +- 9 files changed, 199 insertions(+), 118 deletions(-) diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index ee20f143775f..6850f911d382 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -36,8 +36,8 @@ pub use michelson_signature::Signature; pub use or::Or; #[derive(Debug, Clone, Eq, PartialEq)] -pub struct TransferTokens { - pub param: TypedValue, +pub struct TransferTokens<'a> { + pub param: TypedValue<'a>, pub destination_address: Address, pub amount: i64, } @@ -46,14 +46,14 @@ pub struct TransferTokens { pub struct SetDelegate(pub Option); #[derive(Debug, Clone, Eq, PartialEq)] -pub enum Operation { - TransferTokens(TransferTokens), +pub enum Operation<'a> { + TransferTokens(TransferTokens<'a>), SetDelegate(SetDelegate), } #[derive(Debug, Clone, Eq, PartialEq)] -pub struct OperationInfo { - pub operation: Operation, +pub struct OperationInfo<'a> { + pub operation: Operation<'a>, pub counter: u128, } @@ -130,28 +130,28 @@ impl Type { } #[derive(Debug, Clone, Eq, PartialEq)] -pub enum TypedValue { +pub enum TypedValue<'a> { Int(BigInt), Nat(BigUint), Mutez(i64), Bool(bool), String(String), Unit, - Pair(Box<(TypedValue, TypedValue)>), - Option(Option>), - List(MichelsonList), - Set(BTreeSet), - Map(BTreeMap), - Or(Box>), + Pair(Box<(Self, Self)>), + Option(Option>), + List(MichelsonList), + Set(BTreeSet), + Map(BTreeMap), + Or(Box>), Address(Address), ChainId(ChainId), Contract(Address), Bytes(Vec), Key(Key), Signature(Signature), - Lambda(Lambda), + Lambda(Lambda<'a>), KeyHash(KeyHash), - Operation(Box), + Operation(Box>), } /// Untypes a value using optimized representation in legacy mode. @@ -161,7 +161,7 @@ pub enum TypedValue { /// instance, what `PACK` uses. pub fn typed_value_to_value_optimized_legacy<'a>( arena: &'a Arena>, - tv: TypedValue, + tv: TypedValue<'a>, ) -> Micheline<'a> { use Micheline as V; use TypedValue as TV; @@ -197,7 +197,12 @@ pub fn typed_value_to_value_optimized_legacy<'a>( TV::Bytes(x) => V::Bytes(x), TV::Key(k) => V::Bytes(k.to_bytes_vec()), TV::Signature(s) => V::Bytes(s.to_bytes_vec()), - TV::Lambda(_) => todo!(), + TV::Lambda(lam) => match lam { + Lambda::Lambda { micheline_code, .. } => micheline_code, + Lambda::LambdaRec { micheline_code, .. } => { + V::prim1(arena, Prim::Lambda_rec, micheline_code) + } + }, TV::KeyHash(s) => V::Bytes(s.to_bytes_vec()), TV::Contract(x) => go(TV::Address(x)), TV::Operation(operation_info) => match operation_info.operation { @@ -222,7 +227,7 @@ pub fn typed_value_to_value_optimized_legacy<'a>( } } -impl TypedValue { +impl<'a> TypedValue<'a> { pub fn new_pair(l: Self, r: Self) -> Self { Self::Pair(Box::new((l, r))) } @@ -235,7 +240,7 @@ impl TypedValue { Self::Or(Box::new(x)) } - pub fn new_operation(o: Operation, c: u128) -> Self { + pub fn new_operation(o: Operation<'a>, c: u128) -> Self { Self::Operation(Box::new(OperationInfo { operation: o, counter: c, @@ -256,7 +261,7 @@ impl TypedValue { } #[derive(Debug, Eq, PartialEq, Clone)] -pub enum Instruction { +pub enum Instruction<'a> { Add(overloads::Add), Dip(Option, Vec), Drop(Option), @@ -268,7 +273,7 @@ pub enum Instruction { IfNone(Vec, Vec), Int, Loop(Vec), - Push(TypedValue), + Push(TypedValue<'a>), Swap, Failwith(Type), Never, @@ -306,8 +311,8 @@ pub enum Instruction { } #[derive(Debug, Clone, PartialEq, Eq)] -pub struct ContractScript { +pub struct ContractScript<'a> { pub parameter: Type, pub storage: Type, - pub code: Instruction, + pub code: Instruction<'a>, } diff --git a/contrib/mir/src/ast/comparable.rs b/contrib/mir/src/ast/comparable.rs index 50579d7cd9d7..7fe5736792b8 100644 --- a/contrib/mir/src/ast/comparable.rs +++ b/contrib/mir/src/ast/comparable.rs @@ -1,6 +1,6 @@ use super::TypedValue; -impl PartialOrd for TypedValue { +impl PartialOrd for TypedValue<'_> { fn partial_cmp(&self, other: &Self) -> Option { use TypedValue::*; match (self, other) { @@ -55,7 +55,7 @@ impl PartialOrd for TypedValue { } } -impl Ord for TypedValue { +impl Ord for TypedValue<'_> { fn cmp(&self, other: &Self) -> std::cmp::Ordering { self.partial_cmp(other) .expect("Comparing incomparable values in TypedValue") diff --git a/contrib/mir/src/ast/michelson_lambda.rs b/contrib/mir/src/ast/michelson_lambda.rs index 7d37e4d19c41..b335fbcf8794 100644 --- a/contrib/mir/src/ast/michelson_lambda.rs +++ b/contrib/mir/src/ast/michelson_lambda.rs @@ -5,10 +5,16 @@ /* */ /******************************************************************************/ -use super::Instruction; +use super::{Instruction, Micheline}; #[derive(Debug, Clone, Eq, PartialEq)] -pub enum Lambda { - Lambda { code: Vec }, - LambdaRec { code: Vec }, +pub enum Lambda<'a> { + Lambda { + micheline_code: Micheline<'a>, + code: Vec>, + }, + LambdaRec { + micheline_code: Micheline<'a>, + code: Vec>, + }, } diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index f180da66d08a..e65bfa8c16eb 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -9,47 +9,51 @@ use num_bigint::{BigInt, BigUint}; use num_traits::{Signed, Zero}; use typed_arena::Arena; -use crate::ast::annotations::NO_ANNS; use crate::ast::*; use crate::context::Ctx; use crate::gas::{interpret_cost, OutOfGas}; use crate::irrefutable_match::irrefutable_match; -use crate::lexer::Prim; use crate::stack::*; use crate::typechecker::typecheck_value; #[derive(Debug, PartialEq, Eq, Clone, thiserror::Error)] -pub enum InterpretError { +pub enum InterpretError<'a> { #[error(transparent)] OutOfGas(#[from] OutOfGas), #[error("mutez overflow")] MutezOverflow, #[error("failed with: {1:?} of type {0:?}")] - FailedWith(Type, TypedValue), + FailedWith(Type, TypedValue<'a>), } #[derive(Debug, PartialEq, Eq, thiserror::Error)] -pub enum ContractInterpretError { +pub enum ContractInterpretError<'a> { #[error("failed typechecking input: {0}")] TcError(#[from] crate::typechecker::TcError), #[error("runtime failure while running the contract: {0}")] - InterpretError(#[from] crate::interpreter::InterpretError), + InterpretError(InterpretError<'a>), } -impl ContractScript { +impl<'a> From> for ContractInterpretError<'a> { + fn from(x: InterpretError<'a>) -> Self { + Self::InterpretError(x) + } +} + +impl<'a> ContractScript<'a> { /// Interpret a typechecked contract script using the provided parameter and /// storage. Parameter and storage are given as `Micheline`, as this /// allows ensuring they satisfy the types expected by the script. pub fn interpret( &self, ctx: &mut crate::context::Ctx, - parameter: Micheline, - storage: Micheline, - ) -> Result<(impl Iterator, TypedValue), ContractInterpretError> { - let in_ty = Type::new_pair(self.parameter.clone(), self.storage.clone()); - let in_val = &[parameter, storage]; - let in_val = Micheline::App(Prim::Pair, in_val, NO_ANNS); - let tc_val = typecheck_value(&in_val, ctx, &in_ty)?; + parameter: Micheline<'a>, + storage: Micheline<'a>, + ) -> Result<(impl Iterator>, TypedValue<'a>), ContractInterpretError<'a>> + { + let parameter = typecheck_value(¶meter, ctx, &self.parameter)?; + let storage = typecheck_value(&storage, ctx, &self.storage)?; + let tc_val = TypedValue::new_pair(parameter, storage); let mut stack = stk![tc_val]; self.code.interpret(ctx, &mut stack)?; use TypedValue as V; @@ -67,7 +71,7 @@ impl ContractScript { } } -impl Instruction { +impl<'a> Instruction<'a> { /// Interpret the instruction with the given `Ctx` and input stack. Note the /// interpreter assumes the instruction can execute on the provided stack, /// otherwise this function will panic. @@ -75,16 +79,20 @@ impl Instruction { /// # Panics /// /// When the instruction can't be executed on the provided stack. - pub fn interpret(&self, ctx: &mut Ctx, stack: &mut IStack) -> Result<(), InterpretError> { + pub fn interpret( + &self, + ctx: &mut Ctx, + stack: &mut IStack<'a>, + ) -> Result<(), InterpretError<'a>> { interpret_one(self, ctx, stack) } } -fn interpret( - ast: &Vec, +fn interpret<'a>( + ast: &Vec>, ctx: &mut Ctx, - stack: &mut IStack, -) -> Result<(), InterpretError> { + stack: &mut IStack<'a>, +) -> Result<(), InterpretError<'a>> { for i in ast { i.interpret(ctx, stack)?; } @@ -99,7 +107,11 @@ fn unreachable_state() -> ! { panic!("Unreachable state reached during interpreting, possibly broken typechecking!") } -fn interpret_one(i: &Instruction, ctx: &mut Ctx, stack: &mut IStack) -> Result<(), InterpretError> { +fn interpret_one<'a>( + i: &Instruction<'a>, + ctx: &mut Ctx, + stack: &mut IStack<'a>, +) -> Result<(), InterpretError<'a>> { use Instruction as I; use TypedValue as V; diff --git a/contrib/mir/src/lib.rs b/contrib/mir/src/lib.rs index d4eb6cd2da5c..9c786a7e2327 100644 --- a/contrib/mir/src/lib.rs +++ b/contrib/mir/src/lib.rs @@ -215,9 +215,11 @@ mod tests { #[test] fn vote_contract() { - use crate::ast::micheline::test_helpers::*; let ctx = &mut Ctx::default(); ctx.amount = 5_000_000; + let arena = typed_arena::Arena::new(); + use crate::lexer::Prim; + use Micheline as M; let interp_res = parse_contract_script(VOTE_SRC) .unwrap() .typecheck_script(ctx) @@ -225,7 +227,14 @@ mod tests { .interpret( ctx, "foo".into(), - seq! {app!(Elt["bar", 0]); app!(Elt["baz", 0]); app!(Elt["foo", 0])}, + M::seq( + &arena, + [ + M::prim2(&arena, Prim::Elt, "bar".into(), 0.into()), + M::prim2(&arena, Prim::Elt, "baz".into(), 0.into()), + M::prim2(&arena, Prim::Elt, "foo".into(), 0.into()), + ], + ), ); use TypedValue as TV; match interp_res.unwrap() { @@ -233,7 +242,7 @@ mod tests { assert_eq!(m.get(&TV::String("foo".to_owned())).unwrap(), &TV::int(1)) } _ => panic!("unexpected contract output"), - } + }; } const FIBONACCI_SRC: &str = "{ INT ; PUSH int 0 ; DUP 2 ; GT ; @@ -286,10 +295,10 @@ mod tests { #[cfg(test)] mod multisig_tests { - use crate::ast::micheline::test_helpers::*; use crate::ast::*; use crate::context::Ctx; use crate::interpreter::{ContractInterpretError, InterpretError}; + use crate::lexer::Prim; use crate::parser::test_helpers::parse_contract_script; use num_bigint::BigUint; use Type as T; @@ -327,6 +336,35 @@ mod multisig_tests { BigUint::from(111u32) } + fn arena() -> &'static typed_arena::Arena> { + // this is generally terrible and will leak memory in some + // (multi-threaded) workloads, but it's fine for these tests + thread_local! { + static BX: &'static typed_arena::Arena> = + Box::leak(Box::new(typed_arena::Arena::new())); + } + BX.with(|a| *a) + } + + fn pair( + x: impl Into>, + y: impl Into>, + ) -> Micheline<'static> { + Micheline::prim2(arena(), Prim::Pair, x.into(), y.into()) + } + fn right(x: impl Into>) -> Micheline<'static> { + Micheline::prim1(arena(), Prim::Right, x.into()) + } + fn left(x: impl Into>) -> Micheline<'static> { + Micheline::prim1(arena(), Prim::Left, x.into()) + } + fn some(x: impl Into>) -> Micheline<'static> { + Micheline::prim1(arena(), Prim::Some, x.into()) + } + fn seq(xs: impl IntoIterator>>) -> Micheline<'static> { + Micheline::seq(arena(), xs.into_iter().map(Into::into)) + } + #[test] fn multisig_transfer() { let mut ctx = make_ctx(); @@ -355,20 +393,23 @@ mod multisig_tests { .unwrap() .interpret( &mut ctx, - app!(Pair[ + pair( // :payload - app!(Pair[ + pair( anti_replay_counter(), - app!(Left[ + left( // :transfer - app!(Pair[transfer_amount as i128,transfer_destination]) - ]) - ]), + pair(transfer_amount as i128, transfer_destination), + ), + ), // %sigs - seq!{ app!(Some[signature]) } - ]), + seq([some(signature)]), + ), // make_initial_storage(), - app!(Pair[anti_replay_counter(), threshold.clone(), seq!{ PUBLIC_KEY }]), + pair( + anti_replay_counter(), + pair(threshold.clone(), seq([PUBLIC_KEY])), + ), ); assert_eq!( @@ -422,19 +463,22 @@ mod multisig_tests { .unwrap() .interpret( &mut ctx, - app!(Pair[ + pair( // :payload - app!(Pair[ + pair( anti_replay_counter(), - app!(Right[ app!(Left[ + right(left( // %delegate - app!(Some[new_delegate]) - ])]) - ]), + some(new_delegate), + )), + ), // %sigs - seq!{ app!(Some[signature]) } - ]), - app!(Pair[anti_replay_counter(), threshold.clone(), seq!{ PUBLIC_KEY }]), + seq([some(signature)]), + ), + pair( + anti_replay_counter(), + pair(threshold.clone(), seq([PUBLIC_KEY])), + ), ); assert_eq!( @@ -472,19 +516,19 @@ mod multisig_tests { .unwrap() .interpret( &mut ctx, - app!(Pair[ + pair( // :payload - app!(Pair[ + pair( anti_replay_counter(), - app!(Right[ app!(Left[ + right(left( // %delegate - app!(Some[new_delegate]) - ])]) - ]), + some(new_delegate), + )), + ), // %sigs - seq!{ app!(Some[invalid_signature]) } - ]), - app!(Pair[anti_replay_counter(), threshold, seq!{ PUBLIC_KEY }]), + seq([some(invalid_signature)]), + ), + pair(anti_replay_counter(), pair(threshold, seq([PUBLIC_KEY]))), ); assert_eq!( @@ -498,9 +542,12 @@ mod multisig_tests { // The interpretation result contains an iterator of operations, // which does not implement `Eq` and therefore cannot be used with `assert_eq!`. // This function collects the iterator into a vector so we can use `assert_eq!`. - fn collect_ops( - result: Result<(impl Iterator, TypedValue), ContractInterpretError>, - ) -> Result<(Vec, TypedValue), ContractInterpretError> { + fn collect_ops<'a>( + result: Result< + (impl Iterator>, TypedValue<'a>), + ContractInterpretError<'a>, + >, + ) -> Result<(Vec>, TypedValue<'a>), ContractInterpretError<'a>> { result.map(|(ops, val)| (ops.collect(), val)) } diff --git a/contrib/mir/src/stack.rs b/contrib/mir/src/stack.rs index 91bef040dc40..eeaa435d4229 100644 --- a/contrib/mir/src/stack.rs +++ b/contrib/mir/src/stack.rs @@ -11,7 +11,7 @@ use std::slice::SliceIndex; use crate::ast::*; pub type TypeStack = Stack; -pub type IStack = Stack; +pub type IStack<'a> = Stack>; /// Possibly failed type stack. Stacks are considered failed after /// always-failing instructions. A failed stack can be unified (in terms of diff --git a/contrib/mir/src/typechecker.rs b/contrib/mir/src/typechecker.rs index e6e0e98263f1..26bf55059f4c 100644 --- a/contrib/mir/src/typechecker.rs +++ b/contrib/mir/src/typechecker.rs @@ -137,14 +137,14 @@ pub struct TypesNotEqual(Type, Type); pub type Entrypoints = HashMap; -impl Micheline<'_> { +impl<'a> Micheline<'a> { /// Typechecks `Micheline` as a value, given its type (also as `Micheline`). /// Validates the type. pub fn typecheck_value( &self, ctx: &mut Ctx, value_type: &Micheline, - ) -> Result { + ) -> Result, TcError> { let ty = parse_ty(ctx, value_type)?; typecheck_value(self, ctx, &ty) } @@ -161,7 +161,7 @@ impl Micheline<'_> { ctx: &mut Ctx, self_type: Option<&Micheline>, stack: &[Micheline], - ) -> Result { + ) -> Result, TcError> { let entrypoints = self_type .map(|ty| { let (entrypoints, ty) = parse_parameter_ty_with_entrypoints(ctx, ty)?; @@ -191,7 +191,7 @@ impl Micheline<'_> { /// Typecheck the contract script. Validates the script's types, then /// typechecks the code and checks the result stack is as expected. Returns /// typechecked script. - pub fn typecheck_script(&self, ctx: &mut Ctx) -> Result { + pub fn typecheck_script(&self, ctx: &mut Ctx) -> Result, TcError> { let seq = match self { // top-level allows one level of nesting Micheline::Seq([Micheline::Seq(seq)]) => seq, @@ -424,12 +424,12 @@ fn parse_parameter_ty_with_entrypoints( /// /// Entrypoint map is carried as an argument, not as part of context, because it /// has to be locally overridden during typechecking. -fn typecheck( - ast: &[Micheline], +fn typecheck<'a>( + ast: &[Micheline<'a>], ctx: &mut Ctx, self_entrypoints: Option<&Entrypoints>, opt_stack: &mut FailingTypeStack, -) -> Result, TcError> { +) -> Result>, TcError> { ast.iter() .map(|i| typecheck_instruction(i, ctx, self_entrypoints, opt_stack)) .collect() @@ -452,12 +452,12 @@ macro_rules! nothing_to_none { /// /// Entrypoint map is carried as an argument, not as part of context, because it /// has to be locally overridden during typechecking. -pub(crate) fn typecheck_instruction( - i: &Micheline, +pub(crate) fn typecheck_instruction<'a>( + i: &Micheline<'a>, ctx: &mut Ctx, self_entrypoints: Option<&Entrypoints>, opt_stack: &mut FailingTypeStack, -) -> Result { +) -> Result, TcError> { use Instruction as I; use NoMatchingOverloadReason as NMOR; use Type as T; @@ -1115,11 +1115,11 @@ pub(crate) fn typecheck_instruction( /// 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( - v: &Micheline, +pub(crate) fn typecheck_value<'a>( + v: &Micheline<'a>, ctx: &mut Ctx, t: &Type, -) -> Result { +) -> Result, TcError> { use Micheline as V; use Type as T; use TypedValue as TV; @@ -1183,7 +1183,7 @@ pub(crate) fn typecheck_value( .consume(gas::tc_cost::construct_map(tk.size_for_gas(), vs.len())?)?; let ctx_cell = std::cell::RefCell::new(ctx); let tc_elt = - |v: &Micheline, ctx: &mut Ctx| -> Result<(TypedValue, TypedValue), TcError> { + |v: &Micheline<'a>, ctx: &mut Ctx| -> Result<(TypedValue, TypedValue), TcError> { match v { Micheline::App(Prim::Elt, [k, v], _) => { let k = typecheck_value(k, ctx, tk)?; @@ -1416,11 +1416,11 @@ mod typecheck_tests { use Option::None; /// hack to simplify syntax in tests - fn typecheck_instruction( - i: &Micheline, + fn typecheck_instruction<'a>( + i: &Micheline<'a>, ctx: &mut Ctx, opt_stack: &mut FailingTypeStack, - ) -> Result { + ) -> Result, TcError> { super::typecheck_instruction(i, ctx, None, opt_stack) } diff --git a/contrib/mir/src/tzt.rs b/contrib/mir/src/tzt.rs index 529581eec369..d366063f95e4 100644 --- a/contrib/mir/src/tzt.rs +++ b/contrib/mir/src/tzt.rs @@ -23,14 +23,17 @@ use crate::syntax::tztTestEntitiesParser; use crate::typechecker::*; use crate::tzt::expectation::*; -pub type TestStack = Vec<(Type, TypedValue)>; +pub type TestStack<'a> = Vec<(Type, TypedValue<'a>)>; #[derive(PartialEq, Eq, Clone, Debug)] pub enum TztTestError<'a> { - StackMismatch((FailingTypeStack, IStack), (FailingTypeStack, IStack)), - UnexpectedError(TestError), - UnexpectedSuccess(ErrorExpectation<'a>, IStack), - ExpectedDifferentError(ErrorExpectation<'a>, TestError), + StackMismatch( + (FailingTypeStack, IStack<'a>), + (FailingTypeStack, IStack<'a>), + ), + UnexpectedError(TestError<'a>), + UnexpectedSuccess(ErrorExpectation<'a>, IStack<'a>), + ExpectedDifferentError(ErrorExpectation<'a>, TestError<'a>), } impl fmt::Display for TztTestError<'_> { @@ -65,7 +68,7 @@ impl fmt::Display for TztTestError<'_> { #[derive(Debug, PartialEq, Eq, Clone)] pub struct TztTest<'a> { pub code: Micheline<'a>, - pub input: TestStack, + pub input: TestStack<'a>, pub output: TestExpectation<'a>, pub amount: Option, pub chain_id: Option, @@ -73,7 +76,9 @@ pub struct TztTest<'a> { pub self_addr: Option, } -fn typecheck_stack(stk: Vec<(Micheline, Micheline)>) -> Result, TcError> { +fn typecheck_stack<'a>( + stk: Vec<(Micheline<'a>, Micheline<'a>)>, +) -> Result)>, TcError> { stk.into_iter() .map(|(t, v)| { let t = parse_ty(&mut Ctx::default(), &t)?; @@ -169,18 +174,24 @@ impl<'a> TryFrom>> for TztTest<'a> { /// This represents possibilities in which the execution of /// the code in a test can fail. #[derive(Debug, PartialEq, Eq, Clone, thiserror::Error)] -pub enum TestError { +pub enum TestError<'a> { #[error(transparent)] TypecheckerError(#[from] TcError), #[error(transparent)] - InterpreterError(#[from] InterpretError), + InterpreterError(InterpretError<'a>), +} + +impl<'a> From> for TestError<'a> { + fn from(x: InterpretError<'a>) -> Self { + Self::InterpreterError(x) + } } /// This represents the outcome that we expect from interpreting /// the code in a test. #[derive(Debug, PartialEq, Eq, Clone)] pub enum TestExpectation<'a> { - ExpectSuccess(Vec<(Type, TypedValue)>), + ExpectSuccess(Vec<(Type, TypedValue<'a>)>), ExpectError(ErrorExpectation<'a>), } @@ -237,12 +248,12 @@ pub enum TztOutput<'a> { TztError(ErrorExpectation<'a>), } -fn execute_tzt_test_code( - code: Micheline, +fn execute_tzt_test_code<'a>( + code: Micheline<'a>, ctx: &mut Ctx, parameter: Option<&Micheline>, - input: Vec<(Type, TypedValue)>, -) -> Result<(FailingTypeStack, IStack), TestError> { + input: Vec<(Type, TypedValue<'a>)>, +) -> Result<(FailingTypeStack, IStack<'a>), TestError<'a>> { // Build initial stacks (type and value) for running the test from the test input // stack. let (typs, vals): (Vec, Vec) = input.into_iter().unzip(); diff --git a/contrib/mir/src/tzt/expectation.rs b/contrib/mir/src/tzt/expectation.rs index 310bbd06c81f..67a8367030f0 100644 --- a/contrib/mir/src/tzt/expectation.rs +++ b/contrib/mir/src/tzt/expectation.rs @@ -10,7 +10,7 @@ use super::*; fn check_error_expectation<'a>( ctx: &mut Ctx, err_exp: ErrorExpectation<'a>, - err: TestError, + err: TestError<'a>, ) -> Result<(), TztTestError<'a>> { use ErrorExpectation as Ex; use TestError as Er; @@ -71,7 +71,7 @@ fn unify_interpreter_error( pub fn check_expectation<'a>( ctx: &mut Ctx, expected: TestExpectation<'a>, - real: Result<(FailingTypeStack, IStack), TestError>, + real: Result<(FailingTypeStack, IStack<'a>), TestError<'a>>, ) -> Result<(), TztTestError<'a>> { use TestExpectation::*; use TztTestError::*; -- GitLab From 7bb6a8855c75da2d2b0a2618b7ee01852ea3cac7 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Tue, 21 Nov 2023 17:22:12 +0300 Subject: [PATCH 5/5] MIR: typecheck lambda values --- contrib/mir/src/typechecker.rs | 144 +++++++++++++++++++++++++++++++++ 1 file changed, 144 insertions(+) diff --git a/contrib/mir/src/typechecker.rs b/contrib/mir/src/typechecker.rs index 26bf55059f4c..c30f68544b7e 100644 --- a/contrib/mir/src/typechecker.rs +++ b/contrib/mir/src/typechecker.rs @@ -1286,10 +1286,52 @@ pub(crate) fn typecheck_value<'a>( ctx.gas.consume(gas::tc_cost::KEY_HASH_OPTIMIZED)?; TV::KeyHash(KeyHash::from_bytes(bs).map_err(|e| TcError::ByteReprError(T::KeyHash, e))?) } + ( + T::Lambda(tys), + raw @ (V::Seq(instrs) | V::App(Prim::Lambda_rec, [V::Seq(instrs)], _)), + ) => { + let (in_ty, out_ty) = tys.as_ref(); + TV::Lambda(typecheck_lambda( + instrs, + ctx, + in_ty.clone(), + out_ty.clone(), + matches!(raw, V::App(Prim::Lambda_rec, ..)), + )?) + } (t, v) => return Err(TcError::InvalidValueForType(format!("{v:?}"), t.clone())), }) } +fn typecheck_lambda<'a>( + instrs: &'a [Micheline<'a>], + ctx: &mut Ctx, + in_ty: Type, + out_ty: Type, + recursive: bool, +) -> Result, TcError> { + let stk = &mut if recursive { + let self_ty = Type::new_lambda(in_ty.clone(), out_ty.clone()); + tc_stk![self_ty, in_ty] + } else { + tc_stk![in_ty] + }; + let code = typecheck(instrs, ctx, None, stk)?; + unify_stacks(ctx, stk, tc_stk![out_ty])?; + let micheline_code = Micheline::Seq(instrs); + Ok(if recursive { + Lambda::LambdaRec { + micheline_code, + code, + } + } else { + Lambda::Lambda { + micheline_code, + code, + } + }) +} + fn validate_u10(n: &BigInt) -> Result { let res = u16::try_from(n).map_err(|_| TcError::ExpectedU10(n.clone()))?; if res >= 1024 { @@ -4116,4 +4158,106 @@ mod typecheck_tests { )) ); } + + #[test] + fn push_lambda() { + assert_eq!( + parse("PUSH (lambda unit unit) { DROP ; UNIT }") + .unwrap() + .typecheck_instruction(&mut Ctx::default(), None, &[]), + Ok(Push(TypedValue::Lambda(Lambda::Lambda { + micheline_code: seq! { app!(DROP); app!(UNIT) }, + code: vec![Drop(None), Unit] + }))) + ); + } + + #[test] + fn push_lambda_bad_result() { + assert_eq!( + parse("PUSH (lambda unit int) { DROP ; UNIT }") + .unwrap() + .typecheck_instruction(&mut Ctx::default(), None, &[]), + Err(TcError::StacksNotEqual( + stk![Type::Unit], + stk![Type::Int], + TypesNotEqual(Type::Unit, Type::Int).into() + )) + ); + } + + #[test] + fn push_lambda_bad_input() { + assert_eq!( + parse("PUSH (lambda int unit) { IF { UNIT } { UNIT } }") + .unwrap() + .typecheck_instruction(&mut Ctx::default(), None, &[]), + Err(TcError::NoMatchingOverload { + instr: Prim::IF, + stack: stk![Type::Int], + reason: Some(TypesNotEqual(Type::Bool, Type::Int).into()) + }) + ); + } + + #[test] + fn push_lambda_with_self() { + assert_eq!( + parse("PUSH (lambda unit unit) { SELF }") + .unwrap() + .typecheck_instruction(&mut Ctx::default(), Some(&app!(unit)), &[]), + Err(TcError::SelfForbidden) + ); + } + + #[test] + fn push_lambda_rec_with_self() { + assert_eq!( + parse("PUSH (lambda unit unit) (Lambda_rec { SELF })") + .unwrap() + .typecheck_instruction(&mut Ctx::default(), Some(&app!(unit)), &[]), + Err(TcError::SelfForbidden) + ); + } + + #[test] + fn push_lambda_rec() { + assert_eq!( + parse("PUSH (lambda unit unit) (Lambda_rec { DIP { DROP } })") + .unwrap() + .typecheck_instruction(&mut Ctx::default(), None, &[]), + Ok(Push(TypedValue::Lambda(Lambda::LambdaRec { + micheline_code: seq! { app!(DIP[seq! { app!(DROP) } ]) }, + code: vec![Dip(None, vec![Drop(None)])] + }))) + ); + } + + #[test] + fn push_lambda_rec_bad_result() { + assert_eq!( + parse("PUSH (lambda unit unit) (Lambda_rec { DROP })") + .unwrap() + .typecheck_instruction(&mut Ctx::default(), None, &[]), + Err(TcError::StacksNotEqual( + stk![Type::new_lambda(Type::Unit, Type::Unit)], + stk![Type::Unit], + TypesNotEqual(Type::new_lambda(Type::Unit, Type::Unit), Type::Unit).into() + )) + ); + } + + #[test] + fn push_lambda_rec_bad_input() { + assert_eq!( + parse("PUSH (lambda int unit) (Lambda_rec { IF { UNIT } { UNIT }; DIP { DROP } })") + .unwrap() + .typecheck_instruction(&mut Ctx::default(), None, &[]), + Err(TcError::NoMatchingOverload { + instr: Prim::IF, + stack: stk![Type::new_lambda(Type::Int, Type::Unit), Type::Int], + reason: Some(TypesNotEqual(Type::Bool, Type::Int).into()) + }) + ); + } } -- GitLab