diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index 0c89e9c647f772065dc202266f910f98b3db7511..48de061d687b2420f9b9b557a2031253f8737cbb 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -18,7 +18,7 @@ pub mod or; pub mod overloads; pub use micheline::Micheline; -use std::collections::BTreeMap; +use std::collections::{BTreeMap, BTreeSet}; pub use tezos_crypto_rs::hash::ChainId; use typed_arena::Arena; @@ -67,6 +67,7 @@ pub enum Type { Option(Box), List(Box), Operation, + Set(Box), Map(Box<(Type, Type)>), Or(Box<(Type, Type)>), Contract(Box), @@ -87,7 +88,7 @@ impl Type { 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(), - Option(x) | List(x) | Contract(x) => 1 + x.size_for_gas(), + Option(x) | List(x) | Set(x) | Contract(x) => 1 + x.size_for_gas(), } } @@ -103,6 +104,10 @@ impl Type { Self::List(Box::new(x)) } + pub fn new_set(v: Self) -> Self { + Self::Set(Box::new(v)) + } + pub fn new_map(k: Self, v: Self) -> Self { Self::Map(Box::new((k, v))) } @@ -127,6 +132,7 @@ pub enum TypedValue { Pair(Box<(TypedValue, TypedValue)>), Option(Option>), List(MichelsonList), + Set(BTreeSet), Map(BTreeMap), Or(Box>), Address(Address), @@ -164,6 +170,7 @@ pub fn typed_value_to_value_optimized_legacy<'a>( // and uses an untyped representation that is the shortest. TV::Pair(b) => V::prim2(arena, Prim::Pair, go(b.0), go(b.1)), TV::List(l) => V::Seq(arena.alloc_extend(l.into_iter().map(go))), + TV::Set(s) => V::Seq(arena.alloc_extend(s.into_iter().map(go))), TV::Map(m) => V::Seq( arena.alloc_extend( m.into_iter() @@ -253,6 +260,7 @@ pub enum Instruction { Compare, Amount, Nil, + EmptySet, Get(overloads::Get), Update(overloads::Update), Seq(Vec), diff --git a/contrib/mir/src/ast/comparable.rs b/contrib/mir/src/ast/comparable.rs index eb7a84216842439036fb9df1b61f4be40a6c00ae..ab56bc0af778394c82560d77005f887da42a2dad 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(..) | Map(..) | Contract(..) | Operation(_), _) => None, + (List(..) | Set(..) | Map(..) | Contract(..) | Operation(_), _) => None, } } } diff --git a/contrib/mir/src/ast/overloads.rs b/contrib/mir/src/ast/overloads.rs index baa5379c21762e67900419be0111109aa87ecd18..a0783b9f2ad92745f17ee208f116780bb9cef8e6 100644 --- a/contrib/mir/src/ast/overloads.rs +++ b/contrib/mir/src/ast/overloads.rs @@ -21,12 +21,14 @@ pub enum Get { #[derive(Debug, PartialEq, Eq, Clone, Copy)] pub enum Update { + Set, Map, } #[derive(Debug, PartialEq, Eq, Clone, Copy)] pub enum Iter { List, + Set, Map, } diff --git a/contrib/mir/src/gas.rs b/contrib/mir/src/gas.rs index 1cb0d8cb7438d74a8086c10ab2d17e6282ff6b13..f8c9930a33c7c129a6d851af0a719e0e5a955ffc 100644 --- a/contrib/mir/src/gas.rs +++ b/contrib/mir/src/gas.rs @@ -156,6 +156,14 @@ pub mod tc_cost { let log2n = super::log2i((n + 1).ok_or(OutOfGas)?) as usize; (80 * n + key_size * n * log2n).as_gas_cost() } + + pub fn construct_set(val_size: usize, sz: usize) -> Result { + // Similar to `construct_map`, only the coefficient differs + let n = Checked::from(sz); + let key_size = Checked::from(val_size); + let log2n = super::log2i((n + 1).ok_or(OutOfGas)?) as usize; + (130 * n + key_size * n * log2n).as_gas_cost() + } } pub mod interpret_cost { @@ -190,6 +198,7 @@ pub mod interpret_cost { pub const AMOUNT: u32 = 10; pub const NIL: u32 = 10; pub const CONS: u32 = 15; + pub const EMPTY_SET: u32 = 300; pub const CHAIN_ID: u32 = 15; pub const PACK: u32 = 0; pub const SELF: u32 = 10; @@ -338,7 +347,9 @@ pub mod interpret_cost { .as_gas_cost()?, (V::Or(..), _) => incomparable(), - (V::List(..) | V::Map(..) | V::Contract(_) | V::Operation(_), _) => incomparable(), + (V::List(..) | V::Set(..) | V::Map(..) | V::Contract(_) | V::Operation(_), _) => { + incomparable() + } }) } @@ -370,6 +381,16 @@ pub mod interpret_cost { (80 + 2 * lookup_cost).as_gas_cost() } + pub fn set_update(k: &TypedValue, map_size: usize) -> Result { + // NB: same considerations as for map_update + let compare_cost = compare(k, k)?; + let size_log = super::log2i(map_size + 1); + let lookup_cost = Checked::from(compare_cost) * size_log; + // coefficient larger than in case of Map looks suspicious, something + // to benchmark later + (130 + 2 * lookup_cost).as_gas_cost() + } + /// Measures size of Michelson using several metrics. pub struct MichelineSize { /// Total number of nodes (including leaves). diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index 1ef1dde52af9004b43560baf8f1d783d14f6c507..cc64872f6899eff915f208adf9cb605e75ae4727 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -272,6 +272,14 @@ fn interpret_one(i: &Instruction, ctx: &mut Ctx, stack: &mut IStack) -> Result<( interpret(nested, ctx, stack)?; } } + overloads::Iter::Set => { + let set = pop!(V::Set); + for v in set { + ctx.gas.consume(interpret_cost::PUSH)?; + stack.push(v); + interpret(nested, ctx, stack)?; + } + } overloads::Iter::Map => { let map = pop!(V::Map); for (k, v) in map { @@ -354,6 +362,11 @@ fn interpret_one(i: &Instruction, ctx: &mut Ctx, stack: &mut IStack) -> Result<( lst.cons(elt); stack.push(V::List(lst)); } + I::EmptySet => { + use std::collections::BTreeSet; + ctx.gas.consume(interpret_cost::EMPTY_SET)?; + stack.push(V::Set(BTreeSet::new())) + } I::Get(overload) => match overload { overloads::Get::Map => { let key = pop!(); @@ -364,17 +377,28 @@ fn interpret_one(i: &Instruction, ctx: &mut Ctx, stack: &mut IStack) -> Result<( } }, I::Update(overload) => match overload { + overloads::Update::Set => { + let key = pop!(); + let new_present = pop!(V::Bool); + let set = irrefutable_match!(&mut stack[0]; V::Set); + ctx.gas + .consume(interpret_cost::set_update(&key, set.len())?)?; + if new_present { + set.insert(key) + } else { + set.remove(&key) + }; + } overloads::Update::Map => { let key = pop!(); let opt_new_val = pop!(V::Option); - let mut map = pop!(V::Map); + let map = irrefutable_match!(&mut stack[0]; V::Map); ctx.gas .consume(interpret_cost::map_update(&key, map.len())?)?; match opt_new_val { None => map.remove(&key), Some(val) => map.insert(key, *val), }; - stack.push(V::Map(map)); } }, I::ChainId => { @@ -499,7 +523,7 @@ fn interpret_one(i: &Instruction, ctx: &mut Ctx, stack: &mut IStack) -> Result<( #[cfg(test)] mod interpreter_tests { - use std::collections::BTreeMap; + use std::collections::{BTreeMap, BTreeSet}; use super::*; use crate::ast::michelson_address as addr; @@ -799,6 +823,45 @@ mod interpreter_tests { assert_eq!(stack, stk![V::Unit]); } + #[test] + fn test_iter_set_many() { + let mut stack = stk![ + V::List(vec![].into()), + V::Set( + vec![(V::Int(1)), (V::Int(2)), (V::Int(3)),] + .into_iter() + .collect() + ) + ]; + assert!(interpret_one( + &Iter(overloads::Iter::Set, vec![Cons]), + &mut Ctx::default(), + &mut stack, + ) + .is_ok()); + assert_eq!( + stack, + stk![V::List( + // NB: traversing the set start-to-end, we're CONSing to a + // list, thus the first element of the map is the last element + // of the list. + vec![V::Int(3), V::Int(2), V::Int(1),].into() + )] + ); + } + + #[test] + fn test_iter_set_zero() { + let mut stack = stk![V::Int(0), V::Set(BTreeSet::new())]; + assert!(interpret_one( + &Iter(overloads::Iter::Set, vec![Add(overloads::Add::IntInt)]), + &mut Ctx::default(), + &mut stack, + ) + .is_ok()); + assert_eq!(stack, stk![V::Int(0)]); + } + #[test] fn test_iter_map_many() { let mut stack = stk![ @@ -1312,6 +1375,108 @@ mod interpreter_tests { ); } + #[test] + fn empty_set() { + let mut ctx = Ctx::default(); + let mut stack = stk![]; + assert_eq!(interpret(&vec![EmptySet], &mut ctx, &mut stack), Ok(())); + assert_eq!(stack, stk![TypedValue::Set(BTreeSet::new())]); + assert_eq!( + ctx.gas.milligas(), + Gas::default().milligas() - interpret_cost::EMPTY_SET - interpret_cost::INTERPRET_RET + ); + } + + #[test] + fn update_set_insert() { + let mut ctx = Ctx::default(); + let set = BTreeSet::new(); + let mut stack = stk![ + TypedValue::Set(set), + TypedValue::Bool(true), + TypedValue::Int(1) + ]; + assert_eq!( + interpret(&vec![Update(overloads::Update::Set)], &mut ctx, &mut stack), + Ok(()) + ); + assert_eq!( + stack, + stk![TypedValue::Set(BTreeSet::from([TypedValue::Int(1)])),] + ); + assert_eq!( + ctx.gas.milligas(), + Gas::default().milligas() + - interpret_cost::set_update(&TypedValue::Int(1), 0).unwrap() + - interpret_cost::INTERPRET_RET + ); + } + + #[test] + fn update_set_remove() { + let mut ctx = Ctx::default(); + let set = BTreeSet::from([TypedValue::Int(1)]); + let mut stack = stk![ + TypedValue::Set(set), + TypedValue::Bool(false), + TypedValue::Int(1) + ]; + assert_eq!( + interpret(&vec![Update(overloads::Update::Set)], &mut ctx, &mut stack), + Ok(()) + ); + assert_eq!(stack, stk![TypedValue::Set(BTreeSet::new())]); + assert_eq!( + ctx.gas.milligas(), + Gas::default().milligas() + - interpret_cost::set_update(&TypedValue::Int(1), 1).unwrap() + - interpret_cost::INTERPRET_RET + ); + } + + #[test] + fn update_set_insert_when_exists() { + let mut ctx = Ctx::default(); + let set = BTreeSet::from([TypedValue::Int(1)]); + let mut stack = stk![ + TypedValue::Set(set.clone()), + TypedValue::Bool(true), + TypedValue::Int(1) + ]; + assert_eq!( + interpret(&vec![Update(overloads::Update::Set)], &mut ctx, &mut stack), + Ok(()) + ); + assert_eq!(stack, stk![TypedValue::Set(set)]); + assert_eq!( + ctx.gas.milligas(), + Gas::default().milligas() + - interpret_cost::set_update(&TypedValue::Int(1), 1).unwrap() + - interpret_cost::INTERPRET_RET + ); + } + + #[test] + fn update_set_remove_when_absent() { + let mut ctx = Ctx::default(); + let mut stack = stk![ + TypedValue::Set(BTreeSet::new()), + TypedValue::Bool(false), + TypedValue::Int(1) + ]; + assert_eq!( + interpret(&vec![Update(overloads::Update::Set)], &mut ctx, &mut stack), + Ok(()) + ); + assert_eq!(stack, stk![TypedValue::Set(BTreeSet::new())]); + assert_eq!( + ctx.gas.milligas(), + Gas::default().milligas() + - interpret_cost::set_update(&TypedValue::Int(1), 0).unwrap() + - interpret_cost::INTERPRET_RET + ); + } + #[test] fn update_map_insert() { let mut ctx = Ctx::default(); diff --git a/contrib/mir/src/typechecker.rs b/contrib/mir/src/typechecker.rs index 8bc5c6728efca95d9693375e9b0de72977130853..6c0e3961e585ea470caadf23859bd3dfcea43a88 100644 --- a/contrib/mir/src/typechecker.rs +++ b/contrib/mir/src/typechecker.rs @@ -6,7 +6,7 @@ /******************************************************************************/ use std::collections::hash_map::Entry; -use std::collections::{BTreeMap, HashMap}; +use std::collections::{BTreeMap, BTreeSet, HashMap}; use std::num::TryFromIntError; use tezos_crypto_rs::{base58::FromBase58CheckError, hash::FromBytesError}; @@ -344,6 +344,13 @@ fn parse_ty_with_entrypoints( } App(contract, ..) => unexpected()?, + App(set, [k], _) => { + let k = parse_ty(ctx, k)?; + k.ensure_prop(&mut ctx.gas, TypeProperty::Comparable)?; + Type::new_set(k) + } + App(set, ..) => unexpected()?, + App(map, [k, v], _) => { let k = parse_ty(ctx, k)?; k.ensure_prop(&mut ctx.gas, TypeProperty::Comparable)?; @@ -774,6 +781,19 @@ pub(crate) fn typecheck_instruction( unify_stacks(ctx, opt_stack, opt_inner_stack)?; I::Iter(overloads::Iter::List, nested) } + (App(ITER, [Seq(nested)], _), [.., T::Set(..)]) => { + // get the set element type + let ty = pop!(T::Set); + // clone the rest of the stack + let mut inner_stack = stack.clone(); + // push the element type to the top of the inner stack and typecheck + inner_stack.push(*ty); + let mut opt_inner_stack = FailingTypeStack::Ok(inner_stack); + let nested = typecheck(nested, ctx, self_entrypoints, &mut opt_inner_stack)?; + // If the starting stack (sans set) and result stack unify, all is good. + unify_stacks(ctx, opt_stack, opt_inner_stack)?; + I::Iter(overloads::Iter::Set, nested) + } (App(ITER, [Seq(nested)], _), [.., T::Map(..)]) => { // get the map element type let kty_vty_box = pop!(T::Map); @@ -928,6 +948,14 @@ pub(crate) fn typecheck_instruction( (App(CONS, [], _), [] | [_]) => no_overload!(CONS, len 2), (App(CONS, expect_args!(0), _), _) => unexpected_micheline!(), + (App(EMPTY_SET, [ty], _), _) => { + let ty = parse_ty(ctx, ty)?; + ty.ensure_prop(&mut ctx.gas, TypeProperty::Comparable)?; + stack.push(T::new_set(ty)); + I::EmptySet + } + (App(EMPTY_SET, expect_args!(1), _), _) => unexpected_micheline!(), + (App(GET, [], _), [.., T::Map(..), _]) => { let kty_ = pop!(); let (kty, vty) = *pop!(T::Map); @@ -939,12 +967,16 @@ pub(crate) fn typecheck_instruction( (App(GET, [], _), [] | [_]) => no_overload!(GET, len 2), (App(GET, expect_args!(0), _), _) => unexpected_micheline!(), + (App(UPDATE, [], _), [.., T::Set(ty), T::Bool, ty_]) => { + ensure_ty_eq(ctx, ty, ty_)?; + stack.drop_top(2); + I::Update(overloads::Update::Set) + } (App(UPDATE, [], _), [.., T::Map(m), T::Option(vty_new), kty_]) => { let (kty, vty) = m.as_ref(); ensure_ty_eq(ctx, kty, kty_)?; ensure_ty_eq(ctx, vty, vty_new)?; - pop!(); - pop!(); + stack.drop_top(2); I::Update(overloads::Update::Map) } (App(UPDATE, [], _), [.., _, _, _]) => no_overload!(UPDATE), @@ -1052,9 +1084,9 @@ pub(crate) fn typecheck_instruction( } (App(RIGHT, [_ty_left], _), []) => no_overload!(RIGHT, len 1), (App(RIGHT, expect_args!(1), _), _) => unexpected_micheline!(), - + (App(other, ..), _) => todo!("Unhandled instruction {other}"), - + (Seq(nested), _) => I::Seq(typecheck(nested, ctx, self_entrypoints, opt_stack)?), }) } @@ -1106,43 +1138,53 @@ pub(crate) fn typecheck_value( .map(|v| typecheck_value(v, ctx, ty)) .collect::>()?, ), - (T::Map(m), V::Seq(vs)) => { + (set_ty @ T::Set(ty), V::Seq(vs)) => { + ctx.gas + .consume(gas::tc_cost::construct_set(ty.size_for_gas(), vs.len())?)?; + let ctx_cell = std::cell::RefCell::new(ctx); + // See the same concern about constructing from ordered sequence as in Map + let set: BTreeSet = OrderValidatingIterator { + it: vs + .iter() + .map(|v| typecheck_value(v, *ctx_cell.borrow_mut(), ty)) + .peekable(), + container_ty: set_ty, + to_key: |x| x, + ctx: &ctx_cell, + } + .collect::>()?; + TV::Set(set) + } + (map_ty @ T::Map(m), V::Seq(vs)) => { let (tk, tv) = m.as_ref(); - let tc_elt = |v: &Micheline| -> Result<(TypedValue, TypedValue), TcError> { - match v { - Micheline::App(Prim::Elt, [k, v], _) => { - let k = typecheck_value(k, ctx, tk)?; - let v = typecheck_value(v, ctx, tv)?; - Ok((k, v)) - } - _ => Err(TcError::InvalidEltForMap(format!("{v:?}"), t.clone())), - } - }; - let elts: Vec<(TypedValue, TypedValue)> = - vs.iter().map(tc_elt).collect::>()?; - if elts.len() > 1 { - let mut prev = &elts[0].0; - for i in &elts[1..] { - ctx.gas.consume(gas::interpret_cost::compare(prev, &i.0)?)?; - match prev.cmp(&i.0) { - std::cmp::Ordering::Less => (), - std::cmp::Ordering::Equal => { - return Err(TcError::DuplicateElements(t.clone())) - } - std::cmp::Ordering::Greater => { - return Err(TcError::ElementsNotSorted(t.clone())) + ctx.gas + .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> { + match v { + Micheline::App(Prim::Elt, [k, v], _) => { + let k = typecheck_value(k, ctx, tk)?; + let v = typecheck_value(v, ctx, tv)?; + Ok((k, v)) } + _ => Err(TcError::InvalidEltForMap(format!("{v:?}"), t.clone())), } - prev = &i.0; - } - } - ctx.gas - .consume(gas::tc_cost::construct_map(tk.size_for_gas(), elts.len())?)?; + }; // Unfortunately, `BTreeMap` doesn't expose methods to build from an already-sorted // slice/vec/iterator. FWIW, Rust docs claim that its sorting algorithm is "designed to // be very fast in cases where the slice is nearly sorted", so hopefully it doesn't add // too much overhead. - let map: BTreeMap = elts.into_iter().collect(); + let map: BTreeMap = OrderValidatingIterator { + it: vs + .iter() + .map(|v| tc_elt(v, *ctx_cell.borrow_mut())) + .peekable(), + container_ty: map_ty, + to_key: |(k, _)| k, + ctx: &ctx_cell, + } + .collect::>()?; TV::Map(map) } (T::Address, V::String(str)) => { @@ -1234,6 +1276,50 @@ fn validate_u10(n: i128) -> Result { Ok(res) } +/// An iterator that ensures the keys to be in strictly ascending order. +/// (where you specify a getter to obtain the key from an element). +/// +/// Also charges gas for this check. +struct OrderValidatingIterator<'a, T: Iterator>, I> { + it: std::iter::Peekable, + to_key: fn(&I) -> &TypedValue, + container_ty: &'a Type, + ctx: &'a std::cell::RefCell<&'a mut Ctx>, +} + +impl Iterator for OrderValidatingIterator<'_, T, I> +where + T: Iterator>, +{ + type Item = Result; + fn next(&mut self) -> Option { + self.it.next().map(|cur| { + let cur = cur?; + if let Some(Ok(next)) = self.it.peek() { + let mut ctx = self.ctx.borrow_mut(); + let cur_key = (self.to_key)(&cur); + let next_key = (self.to_key)(next); + ctx.gas + .consume(gas::interpret_cost::compare(cur_key, next_key)?)?; + match cur_key.cmp(next_key) { + std::cmp::Ordering::Less => (), + std::cmp::Ordering::Equal => { + Err(TcError::DuplicateElements(self.container_ty.clone()))? + } + std::cmp::Ordering::Greater => { + Err(TcError::ElementsNotSorted(self.container_ty.clone()))? + } + } + } + Ok(cur) + }) + } + + fn size_hint(&self) -> (usize, Option) { + self.it.size_hint() + } +} + /// Ensures type stack is at least of the required length, otherwise returns /// `Err(StackTooShort)`. fn ensure_stack_len(instr: Prim, stack: &TypeStack, l: usize) -> Result<(), TcError> { @@ -1557,6 +1643,31 @@ mod typecheck_tests { ); } + #[test] + fn test_iter_set() { + let mut stack = tc_stk![Type::new_set(Type::Int)]; + let mut ctx = Ctx::default(); + assert_eq!( + typecheck_instruction(&parse("ITER { DROP }").unwrap(), &mut ctx, &mut stack), + Ok(Iter(overloads::Iter::Set, vec![Drop(None)])) + ); + assert_eq!(stack, tc_stk![]); + } + + #[test] + fn test_iter_set_inner_mismatch() { + let mut stack = tc_stk![Type::new_set(Type::Int)]; + let mut ctx = Ctx::default(); + assert_eq!( + typecheck_instruction(&parse("ITER { }").unwrap(), &mut ctx, &mut stack), + Err(TcError::StacksNotEqual( + stk![], + stk![Type::Int], + StacksNotEqualReason::LengthsDiffer(0, 1) + )) + ); + } + #[test] fn test_iter_map() { let mut stack = tc_stk![Type::new_map(Type::Int, Type::Nat)]; @@ -2222,6 +2333,81 @@ mod typecheck_tests { ); } + #[test] + fn push_set() { + let mut stack = tc_stk![]; + assert_eq!( + typecheck_instruction( + &parse(r#"PUSH (set int) { 1; 2 }"#).unwrap(), + &mut Ctx::default(), + &mut stack + ), + Ok(Push(TypedValue::Set(BTreeSet::from([ + TypedValue::Int(1), + TypedValue::Int(2) + ])))) + ); + assert_eq!(stack, tc_stk![Type::new_set(Type::Int)]); + } + + #[test] + fn push_set_unsorted() { + let mut stack = tc_stk![]; + assert_eq!( + typecheck_instruction( + &parse(r#"PUSH (set int) { 2; 1 }"#).unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::ElementsNotSorted(Type::new_set(Type::Int))) + ); + } + + #[test] + fn push_set_incomparable() { + let mut stack = tc_stk![]; + assert_eq!( + typecheck_instruction( + &parse(r#"PUSH (set (list int)) { }"#).unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::InvalidTypeProperty( + TypeProperty::Comparable, + Type::new_list(Type::Int) + )) + ); + } + + #[test] + fn push_set_wrong_key_type() { + let mut stack = tc_stk![]; + assert_eq!( + typecheck_instruction( + &parse(r#"PUSH (set int) { "1"; 2 }"#).unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::InvalidValueForType( + "String(\"1\")".into(), + Type::Int + )) + ); + } + + #[test] + fn push_set_duplicate_key() { + let mut stack = tc_stk![]; + assert_eq!( + typecheck_instruction( + &parse(r#"PUSH (set int) { 1; 1 }"#).unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::DuplicateElements(Type::new_set(Type::Int))) + ); + } + #[test] fn push_map() { let mut stack = tc_stk![]; @@ -2336,6 +2522,36 @@ mod typecheck_tests { ); } + #[test] + fn empty_set() { + let mut stack = tc_stk![]; + assert_eq!( + typecheck_instruction( + &parse("EMPTY_SET int").unwrap(), + &mut Ctx::default(), + &mut stack + ), + Ok(EmptySet) + ); + assert_eq!(stack, tc_stk![Type::new_set(Type::Int)]); + } + + #[test] + fn empty_set_incomparable() { + let mut stack = tc_stk![]; + assert_eq!( + typecheck_instruction( + &parse("EMPTY_SET operation").unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::InvalidTypeProperty( + TypeProperty::Comparable, + Type::Operation + )) + ); + } + #[test] fn get_map() { let mut stack = tc_stk![Type::new_map(Type::Int, Type::String), Type::Int]; @@ -2373,6 +2589,44 @@ mod typecheck_tests { ); } + #[test] + fn update_set() { + let mut stack = tc_stk![Type::new_set(Type::Int), Type::Bool, Type::Int]; + assert_eq!( + typecheck_instruction(&parse("UPDATE").unwrap(), &mut Ctx::default(), &mut stack), + Ok(Update(overloads::Update::Set)) + ); + assert_eq!(stack, tc_stk![Type::new_set(Type::Int)]); + } + + #[test] + fn update_set_wrong_ty() { + let mut stack = tc_stk![Type::new_set(Type::Int), Type::Bool, Type::Nat]; + assert_eq!( + typecheck_instruction(&parse("UPDATE").unwrap(), &mut Ctx::default(), &mut stack), + Err(TypesNotEqual(Type::Int, Type::Nat).into()) + ); + } + + #[test] + fn update_set_incomparable() { + assert_eq!( + parse("UPDATE").unwrap().typecheck_instruction( + &mut Ctx::default(), + None, + &[ + app!(set[app!(list[app!(int)])]), + app!(bool), + app!(list[app!(int)]) + ] + ), + Err(TcError::InvalidTypeProperty( + TypeProperty::Comparable, + Type::new_list(Type::Int) + )) + ); + } + #[test] fn update_map() { let mut stack = tc_stk![ diff --git a/contrib/mir/src/typechecker/type_props.rs b/contrib/mir/src/typechecker/type_props.rs index 912ce8fbb383ad4fbaf07d2e34460fe133f580d0..9248f55503ee26007218182426064105e34eb11f 100644 --- a/contrib/mir/src/typechecker/type_props.rs +++ b/contrib/mir/src/typechecker/type_props.rs @@ -66,6 +66,15 @@ impl Type { | TypeProperty::BigMapValue | TypeProperty::Duplicable => x.ensure_prop(gas, prop)?, }, + Set(x) => match prop { + TypeProperty::Comparable => return invalid_type_prop(), + TypeProperty::Passable + | TypeProperty::Storable + | TypeProperty::Pushable + | TypeProperty::Packable + | TypeProperty::BigMapValue + | TypeProperty::Duplicable => x.ensure_prop(gas, prop)?, + }, Map(p) => match prop { TypeProperty::Comparable => return invalid_type_prop(), TypeProperty::Passable