From adeea8cdc94840d474f2426903dd12546beaf533 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Mon, 2 Oct 2023 09:46:02 +0300 Subject: [PATCH 1/3] MIR: Add wonky Ord instance for TypedValue --- contrib/mir/src/ast/comparable.rs | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) diff --git a/contrib/mir/src/ast/comparable.rs b/contrib/mir/src/ast/comparable.rs index af80dc9eca4b..b38c31166866 100644 --- a/contrib/mir/src/ast/comparable.rs +++ b/contrib/mir/src/ast/comparable.rs @@ -17,6 +17,13 @@ impl PartialOrd for TypedValue { } } +impl Ord for TypedValue { + fn cmp(&self, other: &Self) -> std::cmp::Ordering { + self.partial_cmp(other) + .expect("Comparing incomparable values in TypedValue") + } +} + #[cfg(test)] mod tests { use super::*; @@ -28,6 +35,7 @@ mod tests { macro_rules! assert_cmp { ($c:expr; $($l:expr),*; $($r:expr),*; $ord:ident) => { assert!($c($($l),*).partial_cmp(&$c($($r),*)) == Some(std::cmp::Ordering::$ord)); + assert!($c($($l),*).cmp(&$c($($r),*)) == std::cmp::Ordering::$ord); }; } @@ -70,4 +78,12 @@ mod tests { // different types don't compare assert!(Bool(true).partial_cmp(&Int(5)) == None); } + + #[test] + #[should_panic(expected = "Comparing incomparable values in TypedValue")] + fn compare_different_comparable() { + // Comparable panics on different types + use TypedValue::*; + let _ = Bool(true).cmp(&Int(5)); //panics + } } -- GitLab From 1191983dac2193b1f56d7a33e7e2cb8627e5d63a Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Mon, 2 Oct 2023 09:47:35 +0300 Subject: [PATCH 2/3] MIR: add map type --- contrib/mir/src/ast.rs | 10 ++++++++-- contrib/mir/src/syntax.lalrpop | 1 + 2 files changed, 9 insertions(+), 2 deletions(-) diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index 04d166e9475f..7a6ff37c4414 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -24,13 +24,14 @@ pub enum Type { Option(Box), List(Box), Operation, + Map(Box, Box), } impl Type { pub fn is_comparable(&self) -> bool { use Type::*; match &self { - List(..) => false, + List(..) | Map(..) => false, Operation => false, Nat | Int | Bool | Mutez | String | Unit => true, Pair(l, r) => l.is_comparable() && r.is_comparable(), @@ -44,7 +45,7 @@ impl Type { Operation => false, Nat | Int | Bool | Mutez | String | Unit => true, Pair(l, r) => l.is_packable() && r.is_packable(), - Option(x) | List(x) => x.is_packable(), + Option(x) | List(x) | Map(_, x) => x.is_packable(), } } @@ -62,6 +63,7 @@ impl Type { Type::Pair(l, r) => 1 + l.size_for_gas() + r.size_for_gas(), Type::Option(x) => 1 + x.size_for_gas(), Type::List(x) => 1 + x.size_for_gas(), + Type::Map(k, v) => 1 + k.size_for_gas() + v.size_for_gas(), } } @@ -76,6 +78,10 @@ impl Type { pub fn new_list(x: Self) -> Self { Self::List(Box::new(x)) } + + pub fn new_map(k: Self, v: Self) -> Self { + Self::Map(Box::new(k), Box::new(v)) + } } #[derive(Debug, Clone, Eq, PartialEq)] diff --git a/contrib/mir/src/syntax.lalrpop b/contrib/mir/src/syntax.lalrpop index 8e621294d378..0232b0e4abfc 100644 --- a/contrib/mir/src/syntax.lalrpop +++ b/contrib/mir/src/syntax.lalrpop @@ -55,6 +55,7 @@ composite_type: Type = { "pair" => Type::new_pair(<>), "option" => Type::new_option(<>), "list" => Type::new_list(<>), + "map" => Type::new_map(<>), } type_expr: Type = { -- GitLab From f3312d55b4b56c1847bca9165725715ea13e70cc Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Mon, 2 Oct 2023 09:51:04 +0300 Subject: [PATCH 3/3] MIR: add map values --- contrib/mir/src/ast.rs | 8 ++ contrib/mir/src/gas.rs | 17 ++++ contrib/mir/src/interpreter.rs | 25 +++++ contrib/mir/src/syntax.lalrpop | 1 + contrib/mir/src/typechecker.rs | 164 +++++++++++++++++++++++++++++++++ 5 files changed, 215 insertions(+) diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index 7a6ff37c4414..d85ada367232 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -9,6 +9,8 @@ pub mod comparable; pub mod parsed; pub mod typechecked; +use std::collections::BTreeMap; + pub use parsed::{ParsedInstruction, ParsedStage}; pub use typechecked::{overloads, TypecheckedInstruction, TypecheckedStage}; @@ -93,6 +95,7 @@ pub enum Value { PairValue(Box, Box), OptionValue(Option>), Seq(Vec), + Elt(Box, Box), } impl Value { @@ -103,6 +106,10 @@ impl Value { pub fn new_option(x: Option) -> Self { Self::OptionValue(x.map(Box::new)) } + + pub fn new_elt(k: Self, v: Self) -> Self { + Self::Elt(Box::new(k), Box::new(v)) + } } #[derive(Debug, Clone, Eq, PartialEq)] @@ -116,6 +123,7 @@ pub enum TypedValue { Pair(Box, Box), Option(Option>), List(Vec), + Map(BTreeMap), } impl TypedValue { diff --git a/contrib/mir/src/gas.rs b/contrib/mir/src/gas.rs index fd83d17bde19..365f311194df 100644 --- a/contrib/mir/src/gas.rs +++ b/contrib/mir/src/gas.rs @@ -94,6 +94,23 @@ pub mod tc_cost { let sz = Checked::from(std::cmp::min(sz1, sz2)); (sz * 60).as_gas_cost() } + + pub fn construct_map(key_size: usize, sz: usize) -> Result { + // Tezos protocol constructs maps element by element, thus the cost ends + // up Σ (80 + key_size*log2(i)) = 80 * n + key_size * Σ log2(i) = 80 * n + // + key_size * log2(Π i) = 80 * n + key_size * log2(n!) + // Using n * log2(n) as an approximation for log2(n!), + // ≈ 80 * n + key_size * n * log2(n) + // which seems like a reasonable first-order approximation. + // to avoid log2(0) it's more practical to compute log2(n + 1) + let n = Checked::from(sz); + let key_size = Checked::from(key_size); + let log2n = (n + 1) + .ok_or(OutOfGas)? + .next_power_of_two() + .trailing_zeros() as usize; + (80 * n + key_size * n * log2n).as_gas_cost() + } } pub mod interpret_cost { diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index 9a49155cc45b..705c80e0ab99 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -227,6 +227,8 @@ fn interpret_one( #[cfg(test)] mod interpreter_tests { + use std::collections::BTreeMap; + use super::*; use crate::gas::Gas; use Instruction::*; @@ -746,4 +748,27 @@ mod interpreter_tests { Gas::default().milligas() - interpret_cost::NIL - interpret_cost::INTERPRET_RET, ) } + + #[test] + fn push_map() { + let mut stack = stk![]; + let mut ctx = Ctx::default(); + let map = BTreeMap::from([ + (TypedValue::Int(1), TypedValue::String("foo".to_owned())), + (TypedValue::Int(2), TypedValue::String("bar".to_owned())), + ]); + assert_eq!( + interpret( + &vec![Push(TypedValue::Map(map.clone()))], + &mut ctx, + &mut stack + ), + Ok(()) + ); + assert_eq!(stack, stk![TypedValue::Map(map)]); + assert_eq!( + ctx.gas.milligas(), + Gas::default().milligas() - interpret_cost::PUSH - interpret_cost::INTERPRET_RET + ); + } } diff --git a/contrib/mir/src/syntax.lalrpop b/contrib/mir/src/syntax.lalrpop index 0232b0e4abfc..ed07f768bbc2 100644 --- a/contrib/mir/src/syntax.lalrpop +++ b/contrib/mir/src/syntax.lalrpop @@ -86,6 +86,7 @@ pair_val_args: Value = { composite_value: Value = { "Pair" => Value::new_pair(<>), "Some" => Value::new_option(Some(<>)), + "Elt" => Value::new_elt(<>), } value_expr: Value = { diff --git a/contrib/mir/src/typechecker.rs b/contrib/mir/src/typechecker.rs index 3d2ddaf81b61..1c8250f76e9b 100644 --- a/contrib/mir/src/typechecker.rs +++ b/contrib/mir/src/typechecker.rs @@ -5,6 +5,7 @@ /* */ /******************************************************************************/ +use std::collections::BTreeMap; use std::num::TryFromIntError; use crate::ast::*; @@ -30,6 +31,14 @@ pub enum TcError { Dup0, #[error("value {0:?} is invalid for type {1:?}")] InvalidValueForType(Value, Type), + #[error("value {0:?} is invalid element for container type {1:?}")] + InvalidEltForMap(Value, Type), + #[error("sequence elements must be in strictly ascending order for type {0:?}")] + ElementsNotSorted(Type), + #[error("type not comparable: {0:?}")] + TypeNotComparable(Type), + #[error("sequence elements must contain no duplicate keys for type {0:?}")] + DuplicateElements(Type), #[error("no matching overload for {instr} on stack {stack:?}{}", .reason.as_ref().map_or("".to_owned(), |x| format!(", reason: {}", x)))] NoMatchingOverload { instr: &'static str, @@ -362,6 +371,45 @@ fn typecheck_value(ctx: &mut Ctx, t: &Type, v: Value) -> Result { + ensure_comparable(tk)?; + let tc_elt = |v: Value| -> Result<(TypedValue, TypedValue), TcError> { + match v { + Value::Elt(k, v) => { + let k = typecheck_value(ctx, tk, *k)?; + let v = typecheck_value(ctx, tv, *v)?; + Ok((k, v)) + } + _ => Err(TcError::InvalidEltForMap(v, t.clone())), + } + }; + let elts: Vec<(TypedValue, TypedValue)> = + vs.into_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())) + } + } + 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(); + TV::Map(map) + } (t, v) => return Err(TcError::InvalidValueForType(v, t.clone())), }) } @@ -388,6 +436,14 @@ fn ensure_packable(ty: Type) -> Result<(), TcError> { } } +fn ensure_comparable(ty: &Type) -> Result<(), TcError> { + if ty.is_comparable() { + Ok(()) + } else { + Err(TcError::TypeNotComparable(ty.clone())) + } +} + /// Ensures two type stacks compare equal, otherwise returns /// `Err(StacksNotEqual)`. If runs out of gas, returns `Err(OutOfGas)` instead. /// @@ -1027,4 +1083,112 @@ mod typecheck_tests { Err(TcError::TypeNotPackable(Type::new_list(Type::Operation))) ); } + + #[test] + fn push_map() { + let mut stack = stk![]; + assert_eq!( + typecheck( + parse(r#"{ PUSH (map int string) { Elt 1 "foo"; Elt 2 "bar" } }"#).unwrap(), + &mut Ctx::default(), + &mut stack + ), + Ok(vec![Push(TypedValue::Map(BTreeMap::from([ + (TypedValue::Int(1), TypedValue::String("foo".to_owned())), + (TypedValue::Int(2), TypedValue::String("bar".to_owned())) + ])))]) + ); + assert_eq!(stack, stk![Type::new_map(Type::Int, Type::String)]); + } + + #[test] + fn push_map_unsorted() { + let mut stack = stk![]; + assert_eq!( + typecheck( + parse(r#"{ PUSH (map int string) { Elt 2 "foo"; Elt 1 "bar" } }"#).unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::ElementsNotSorted(Type::new_map( + Type::Int, + Type::String + ))) + ); + } + + #[test] + fn push_map_incomparable() { + let mut stack = stk![]; + assert_eq!( + typecheck( + parse(r#"{ PUSH (map (list int) string) { Elt { 2 } "foo"; Elt { 1 } "bar" } }"#) + .unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::TypeNotComparable(Type::new_list(Type::Int))) + ); + } + + #[test] + fn push_map_incomparable_empty() { + let mut stack = stk![]; + assert_eq!( + typecheck( + parse(r#"{ PUSH (map (list int) string) { } }"#).unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::TypeNotComparable(Type::new_list(Type::Int))) + ); + } + + #[test] + fn push_map_wrong_key_type() { + let mut stack = stk![]; + assert_eq!( + typecheck( + parse(r#"{ PUSH (map int string) { Elt "1" "foo"; Elt 2 "bar" } }"#).unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::InvalidValueForType( + Value::StringValue("1".to_owned()), + Type::Int + )) + ); + } + + #[test] + fn push_map_wrong_elt() { + let mut stack = stk![]; + assert_eq!( + typecheck( + parse(r#"{ PUSH (map int string) { Elt 1 "foo"; "bar" } }"#).unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::InvalidEltForMap( + Value::StringValue("bar".to_owned()), + Type::new_map(Type::Int, Type::String) + )) + ); + } + + #[test] + fn push_map_duplicate_key() { + let mut stack = stk![]; + assert_eq!( + typecheck( + parse(r#"{ PUSH (map int string) { Elt 1 "foo"; Elt 1 "bar" } }"#).unwrap(), + &mut Ctx::default(), + &mut stack + ), + Err(TcError::DuplicateElements(Type::new_map( + Type::Int, + Type::String + ))) + ); + } } -- GitLab