From 60c8ed1ba8bfb59dd41e446db86bd5220b7b3886 Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Tue, 12 Sep 2023 13:52:18 +0300 Subject: [PATCH] MIR: Refactor: return Result from typecheck --- contrib/mir/src/main.rs | 4 +- contrib/mir/src/stack.rs | 23 ++++- contrib/mir/src/typechecker.rs | 180 +++++++++++++++------------------ 3 files changed, 102 insertions(+), 105 deletions(-) diff --git a/contrib/mir/src/main.rs b/contrib/mir/src/main.rs index 66bc648500a1..ec36333702b4 100644 --- a/contrib/mir/src/main.rs +++ b/contrib/mir/src/main.rs @@ -25,7 +25,7 @@ mod tests { fn typecheck_test_expect_success() { let ast = parser::parse(&FIBONACCI_SRC).unwrap(); let mut stack = VecDeque::from([Type::Nat]); - assert!(typechecker::typecheck(&ast, &mut stack)); + assert!(typechecker::typecheck(&ast, &mut stack).is_ok()); assert!(stack == VecDeque::from([Type::Int])); } @@ -33,7 +33,7 @@ mod tests { fn typecheck_test_expect_fail() { let ast = parser::parse(&FIBONACCI_ILLTYPED_SRC).unwrap(); let mut stack = VecDeque::from([Type::Nat]); - assert!(!typechecker::typecheck(&ast, &mut stack)); + assert!(typechecker::typecheck(&ast, &mut stack).is_err()); } #[test] diff --git a/contrib/mir/src/stack.rs b/contrib/mir/src/stack.rs index ab238aa611e5..0b025d764c6f 100644 --- a/contrib/mir/src/stack.rs +++ b/contrib/mir/src/stack.rs @@ -11,6 +11,25 @@ use crate::ast::*; pub type TypeStack = VecDeque; -pub fn ensure_stack_len(stack: &TypeStack, l: usize) -> bool { - stack.len() >= l +pub struct StackTooShort; + +/// Ensures type stack is at least of the required length, otherwise returns +/// `Err(StackTooShort)`. +pub fn ensure_stack_len(stack: &TypeStack, l: usize) -> Result<(), StackTooShort> { + if stack.len() >= l { + Ok(()) + } else { + Err(StackTooShort) + } +} + +pub struct StacksNotEqual; + +/// Ensures two type stacks compare equal, otherwise returns `Err(StacksNotEqual)`. +pub fn ensure_stacks_eq(stack1: &[Type], stack2: &[Type]) -> Result<(), StacksNotEqual> { + if stack1 == stack2 { + Ok(()) + } else { + Err(StacksNotEqual) + } } diff --git a/contrib/mir/src/typechecker.rs b/contrib/mir/src/typechecker.rs index 64e76bc8f533..e47b9a144d72 100644 --- a/contrib/mir/src/typechecker.rs +++ b/contrib/mir/src/typechecker.rs @@ -9,16 +9,34 @@ use crate::ast::*; use crate::stack::*; use std::collections::VecDeque; -pub fn typecheck(ast: &AST, stack: &mut TypeStack) -> bool { +/// Typechecker error type. +#[derive(Debug, PartialEq, Eq)] +pub enum TcError { + GenericTcError, + StackTooShort, + StacksNotEqual, +} + +impl From for TcError { + fn from(_: StackTooShort) -> Self { + TcError::StackTooShort + } +} + +impl From for TcError { + fn from(_: StacksNotEqual) -> Self { + TcError::StacksNotEqual + } +} + +pub fn typecheck(ast: &AST, stack: &mut TypeStack) -> Result<(), TcError> { for i in ast { - if !typecheck_instruction(&i, stack) { - return false; - } + typecheck_instruction(&i, stack)?; } - return true; + Ok(()) } -fn typecheck_instruction(i: &Instruction, stack: &mut TypeStack) -> bool { +fn typecheck_instruction(i: &Instruction, stack: &mut TypeStack) -> Result<(), TcError> { use Instruction::*; use Type::*; @@ -26,60 +44,42 @@ fn typecheck_instruction(i: &Instruction, stack: &mut TypeStack) -> bool { Add => match stack.make_contiguous() { [Type::Nat, Type::Nat, ..] => { stack.pop_front(); - true } [Type::Int, Type::Int, ..] => { stack.pop_front(); - true } _ => unimplemented!(), }, Dip(opt_height, nested) => { let protected_height: usize = opt_height.unwrap_or(1); - if ensure_stack_len(stack, protected_height) { - // Here we split the stack into protected and live segments, and after typechecking - // nested code with the live segment, we append the protected and the potentially - // modified live segment as the result stack. - let mut live = stack.split_off(protected_height); - if typecheck(nested, &mut live) { - stack.append(&mut live); - true - } else { - false - } - } else { - false - } + ensure_stack_len(stack, protected_height)?; + // Here we split the stack into protected and live segments, and after typechecking + // nested code with the live segment, we append the protected and the potentially + // modified live segment as the result stack. + let mut live = stack.split_off(protected_height); + typecheck(nested, &mut live)?; + stack.append(&mut live); } Drop(opt_height) => { let drop_height: usize = opt_height.unwrap_or(1); - if ensure_stack_len(&stack, drop_height) { - *stack = stack.split_off(drop_height); - true - } else { - false - } + ensure_stack_len(&stack, drop_height)?; + *stack = stack.split_off(drop_height); } Dup(Some(0)) => { // DUP instruction requires an argument that is > 0. - false + return Err(TcError::GenericTcError); } Dup(opt_height) => { let dup_height: usize = opt_height.unwrap_or(1); - if ensure_stack_len(stack, dup_height) { - stack.push_front(stack.get(dup_height - 1).unwrap().to_owned()); - true - } else { - false - } + ensure_stack_len(stack, dup_height)?; + stack.push_front(stack.get(dup_height - 1).unwrap().to_owned()); } Gt => match stack.make_contiguous() { [Type::Int, ..] => { stack[0] = Type::Bool; - true } - _ => false, + _ => return Err(TcError::GenericTcError), }, If(nested_t, nested_f) => match stack.make_contiguous() { // Check if top is bool and bind the tail to `t`. @@ -88,82 +88,61 @@ fn typecheck_instruction(i: &Instruction, stack: &mut TypeStack) -> bool { // the two branches with. let mut t_stack: TypeStack = VecDeque::from(t.to_owned()); let mut f_stack: TypeStack = VecDeque::from(t.to_owned()); - if typecheck(nested_t, &mut t_stack) && typecheck(nested_f, &mut f_stack) { - // If both stacks are same after typecheck, then make result - // stack using one of them and return success. - if t_stack == f_stack { - *stack = t_stack; - true - } else { - false - } - } else { - false - } + typecheck(nested_t, &mut t_stack)?; + typecheck(nested_f, &mut f_stack)?; + // If both stacks are same after typecheck, then make result + // stack using one of them and return success. + ensure_stacks_eq(t_stack.make_contiguous(), f_stack.make_contiguous())?; + *stack = t_stack; } - _ => false, + _ => return Err(TcError::GenericTcError), }, Instruction::Int => match stack.make_contiguous() { [val @ Type::Nat, ..] => { *val = Type::Int; - true } - _ => false, + _ => return Err(TcError::GenericTcError), }, Loop(nested) => match stack.make_contiguous() { // Check if top is bool and bind the tail to `t`. [Bool, t @ ..] => { let mut live: TypeStack = VecDeque::from(t.to_owned()); // Clone the tail and typecheck the nested body using it. - if typecheck(nested, &mut live) { - match live.make_contiguous() { - // ensure the result stack has a bool on top. - [Bool, r @ ..] => { - // If the starting tail and result tail match - // then the typecheck is complete. pop the bool - // off the original stack to form the final result. - if t == r { - stack.pop_front(); - true - } else { - false - } - } - _ => false, + typecheck(nested, &mut live)?; + match live.make_contiguous() { + // ensure the result stack has a bool on top. + [Bool, r @ ..] => { + // If the starting tail and result tail match + // then the typecheck is complete. pop the bool + // off the original stack to form the final result. + ensure_stacks_eq(&t, &r)?; + stack.pop_front(); } - } else { - false + _ => return Err(TcError::GenericTcError), } } - _ => false, + _ => return Err(TcError::GenericTcError), }, Push(t, v) => { - if typecheck_value(&t, &v) { - stack.push_front(t.to_owned()); - true - } else { - false - } + typecheck_value(&t, &v)?; + stack.push_front(t.to_owned()); } Swap => { - if stack.len() > 1 { - stack.swap(0, 1); - true - } else { - false - } + ensure_stack_len(stack, 2)?; + stack.swap(0, 1); } } + Ok(()) } -fn typecheck_value(t: &Type, v: &Value) -> bool { +fn typecheck_value(t: &Type, v: &Value) -> Result<(), TcError> { use Type::*; use Value::*; match (t, v) { - (Nat, NumberValue(n)) => n >= &0, - (Int, NumberValue(_)) => true, - (Bool, BooleanValue(_)) => true, - _ => false, + (Nat, NumberValue(n)) if *n >= 0 => Ok(()), + (Int, NumberValue(_)) => Ok(()), + (Bool, BooleanValue(_)) => Ok(()), + _ => Err(TcError::GenericTcError), } } @@ -179,7 +158,7 @@ mod typecheck_tests { fn test_dup() { let mut stack = VecDeque::from([Type::Nat]); let expected_stack = VecDeque::from([Type::Nat, Type::Nat]); - typecheck_instruction(&Dup(Some(1)), &mut stack); + typecheck_instruction(&Dup(Some(1)), &mut stack).unwrap(); assert!(stack == expected_stack); } @@ -187,7 +166,7 @@ mod typecheck_tests { fn test_dup_n() { let mut stack = VecDeque::from([Type::Nat, Type::Int]); let expected_stack = VecDeque::from([Type::Int, Type::Nat, Type::Int]); - typecheck_instruction(&Dup(Some(2)), &mut stack); + typecheck_instruction(&Dup(Some(2)), &mut stack).unwrap(); assert!(stack == expected_stack); } @@ -195,7 +174,7 @@ mod typecheck_tests { fn test_swap() { let mut stack = VecDeque::from([Type::Nat, Type::Int]); let expected_stack = VecDeque::from([Type::Int, Type::Nat]); - typecheck_instruction(&Swap, &mut stack); + typecheck_instruction(&Swap, &mut stack).unwrap(); assert!(stack == expected_stack); } @@ -203,7 +182,7 @@ mod typecheck_tests { fn test_int() { let mut stack = VecDeque::from([Type::Nat]); let expected_stack = VecDeque::from([Type::Int]); - typecheck_instruction(&Int, &mut stack); + typecheck_instruction(&Int, &mut stack).unwrap(); assert!(stack == expected_stack); } @@ -211,7 +190,7 @@ mod typecheck_tests { fn test_drop() { let mut stack = VecDeque::from([Type::Nat]); let expected_stack = VecDeque::from([]); - typecheck(&parse("{DROP}").unwrap(), &mut stack); + typecheck(&parse("{DROP}").unwrap(), &mut stack).unwrap(); assert!(stack == expected_stack); } @@ -219,7 +198,7 @@ mod typecheck_tests { fn test_drop_n() { let mut stack = VecDeque::from([Type::Nat, Type::Int]); let expected_stack = VecDeque::from([]); - typecheck_instruction(&Drop(Some(2)), &mut stack); + typecheck_instruction(&Drop(Some(2)), &mut stack).unwrap(); assert!(stack == expected_stack); } @@ -227,7 +206,7 @@ mod typecheck_tests { fn test_push() { let mut stack = VecDeque::from([Type::Nat]); let expected_stack = VecDeque::from([Type::Int, Type::Nat]); - typecheck_instruction(&Push(Type::Int, Value::NumberValue(1)), &mut stack); + typecheck_instruction(&Push(Type::Int, Value::NumberValue(1)), &mut stack).unwrap(); assert!(stack == expected_stack); } @@ -235,7 +214,7 @@ mod typecheck_tests { fn test_gt() { let mut stack = VecDeque::from([Type::Int]); let expected_stack = VecDeque::from([Type::Bool]); - typecheck_instruction(&Gt, &mut stack); + typecheck_instruction(&Gt, &mut stack).unwrap(); assert!(stack == expected_stack); } @@ -243,7 +222,7 @@ mod typecheck_tests { fn test_dip() { let mut stack = VecDeque::from([Type::Int, Type::Bool]); let expected_stack = VecDeque::from([Type::Int, Type::Nat, Type::Bool]); - typecheck_instruction(&Dip(Some(1), parse("{PUSH nat 6}").unwrap()), &mut stack); + typecheck_instruction(&Dip(Some(1), parse("{PUSH nat 6}").unwrap()), &mut stack).unwrap(); assert!(stack == expected_stack); } @@ -251,7 +230,7 @@ mod typecheck_tests { fn test_add() { let mut stack = VecDeque::from([Type::Int, Type::Int]); let expected_stack = VecDeque::from([Type::Int]); - typecheck_instruction(&Add, &mut stack); + typecheck_instruction(&Add, &mut stack).unwrap(); assert!(stack == expected_stack); } @@ -259,10 +238,9 @@ mod typecheck_tests { fn test_loop() { let mut stack = VecDeque::from([Type::Bool, Type::Int]); let expected_stack = VecDeque::from([Type::Int]); - assert!(typecheck_instruction( - &Loop(parse("{PUSH bool True}").unwrap()), - &mut stack - )); + assert!( + typecheck_instruction(&Loop(parse("{PUSH bool True}").unwrap()), &mut stack).is_ok() + ); assert!(stack == expected_stack); } } -- GitLab