diff --git a/src/common.rs b/src/common.rs index a88c490ca88c28c09e848f86a9d7ede72dd2a5c0..9ac1ddeb679f167a0242856a8f1ee093ba0669a3 100644 --- a/src/common.rs +++ b/src/common.rs @@ -57,7 +57,7 @@ pub struct PortId(Id); /// A safely aliasable heap-allocated payload of message bytes #[derive(Default, Eq, PartialEq, Clone, Ord, PartialOrd)] -pub struct Payload(Arc>); +pub struct Payload(pub Arc>); #[derive(Debug, Eq, PartialEq, Clone, Hash, Copy, Ord, PartialOrd)] /// "Orientation" of a port, determining whether they can send or receive messages with `put` and `get` respectively. diff --git a/src/protocol/ast.rs b/src/protocol/ast.rs index 23d65f22633525765bdb019900c8b6db9f9177a3..56a0149fed527e40c7493e409b86c5dc78feadbc 100644 --- a/src/protocol/ast.rs +++ b/src/protocol/ast.rs @@ -126,6 +126,7 @@ define_new_ast_id!(FunctionDefinitionId, DefinitionId, index(FunctionDefinition, define_aliased_ast_id!(StatementId, Id, index(Statement, statements)); define_new_ast_id!(BlockStatementId, StatementId, index(BlockStatement, Statement::Block, statements), alloc(alloc_block_statement)); +define_new_ast_id!(EndBlockStatementId, StatementId, index(EndBlockStatement, Statement::EndBlock, statements), alloc(alloc_end_block_statement)); define_new_ast_id!(LocalStatementId, StatementId, index(LocalStatement, Statement::Local, statements), alloc(alloc_local_statement)); define_new_ast_id!(MemoryStatementId, LocalStatementId); define_new_ast_id!(ChannelStatementId, LocalStatementId); @@ -975,6 +976,7 @@ impl FunctionDefinition { #[derive(Debug, Clone)] pub enum Statement { Block(BlockStatement), + EndBlock(EndBlockStatement), Local(LocalStatement), Labeled(LabeledStatement), If(IfStatement), @@ -1162,12 +1164,13 @@ impl Statement { Statement::Goto(v) => v.span, Statement::New(v) => v.span, Statement::Expression(v) => v.span, - Statement::EndIf(_) | Statement::EndWhile(_) | Statement::EndSynchronous(_) => unreachable!(), + Statement::EndBlock(_) | Statement::EndIf(_) | Statement::EndWhile(_) | Statement::EndSynchronous(_) => unreachable!(), } } pub fn link_next(&mut self, next: StatementId) { match self { Statement::Block(_) => todo!(), + Statement::EndBlock(stmt) => stmt.next = next, Statement::Local(stmt) => match stmt { LocalStatement::Channel(stmt) => stmt.next = next, LocalStatement::Memory(stmt) => stmt.next = next, @@ -1196,12 +1199,13 @@ pub struct BlockStatement { pub is_implicit: bool, pub span: InputSpan, // of the complete block pub statements: Vec, + pub end_block: EndBlockStatementId, // Phase 2: linker pub parent_scope: Scope, pub first_unique_id_in_scope: i32, // Temporary fix until proper bytecode/asm is generated pub next_unique_id_in_scope: i32, // Temporary fix until proper bytecode/asm is generated pub relative_pos_in_parent: u32, - pub locals: Vec, + pub locals: Vec, pub labels: Vec, } @@ -1228,10 +1232,15 @@ impl BlockStatement { } } } - pub fn first(&self) -> StatementId { - // It is an invariant (guaranteed by the lexer) that block statements have at least one stmt - *self.statements.first().unwrap() - } +} + +#[derive(Debug, Clone)] +pub struct EndBlockStatement { + pub this: EndBlockStatementId, + // Parser + pub start_block: BlockStatementId, + // Validation/Linking + pub next: StatementId, } #[derive(Debug, Clone)] @@ -1313,15 +1322,13 @@ pub struct IfStatement { pub test: ExpressionId, pub true_body: BlockStatementId, pub false_body: Option, - // Phase 2: linker - pub end_if: Option, + pub end_if: EndIfStatementId, } #[derive(Debug, Clone)] pub struct EndIfStatement { pub this: EndIfStatementId, pub start_if: IfStatementId, - // Phase 2: linker pub next: StatementId, } @@ -1332,8 +1339,7 @@ pub struct WhileStatement { pub span: InputSpan, // of the "while" keyword pub test: ExpressionId, pub body: BlockStatementId, - // Phase 2: linker - pub end_while: Option, + pub end_while: EndWhileStatementId, pub in_sync: Option, } @@ -1372,7 +1378,7 @@ pub struct SynchronousStatement { pub span: InputSpan, // of the "sync" keyword pub body: BlockStatementId, // Phase 2: linker - pub end_sync: Option, + pub end_sync: EndSynchronousStatementId, pub parent_scope: Option, } diff --git a/src/protocol/ast_printer.rs b/src/protocol/ast_printer.rs index 1111946971c5c0ba6e8dc61b9b691b103a35910e..c1c80fa9a39a3388c55b0b95158cd39055d18145 100644 --- a/src/protocol/ast_printer.rs +++ b/src/protocol/ast_printer.rs @@ -22,6 +22,7 @@ const PREFIX_COMPONENT_ID: &'static str = "DefC"; const PREFIX_FUNCTION_ID: &'static str = "DefF"; const PREFIX_STMT_ID: &'static str = "Stmt"; const PREFIX_BLOCK_STMT_ID: &'static str = "SBl "; +const PREFIX_ENDBLOCK_STMT_ID: &'static str = "SEBl"; const PREFIX_LOCAL_STMT_ID: &'static str = "SLoc"; const PREFIX_MEM_STMT_ID: &'static str = "SMem"; const PREFIX_CHANNEL_STMT_ID: &'static str = "SCha"; @@ -358,8 +359,8 @@ impl ASTWriter { } self.kv(indent2).with_s_key("Parameters"); - for param_id in &def.parameters { - self.write_parameter(heap, *param_id, indent3); + for variable_id in &def.parameters { + self.write_variable(heap, *variable_id, indent3); } self.kv(indent2).with_s_key("Body"); @@ -378,8 +379,8 @@ impl ASTWriter { } self.kv(indent2).with_s_key("Parameters"); - for param_id in &def.parameters { - self.write_parameter(heap, *param_id, indent3) + for variable_id in &def.parameters { + self.write_variable(heap, *variable_id, indent3) } self.kv(indent2).with_s_key("Body"); @@ -388,16 +389,6 @@ impl ASTWriter { } } - fn write_parameter(&mut self, heap: &Heap, param_id: ParameterId, indent: usize) { - let indent2 = indent + 1; - let param = &heap[param_id]; - - self.kv(indent).with_id(PREFIX_PARAMETER_ID, param_id.0.index) - .with_s_key("Parameter"); - self.kv(indent2).with_s_key("Name").with_identifier_val(¶m.identifier); - self.kv(indent2).with_s_key("ParserType").with_custom_val(|w| write_parser_type(w, heap, ¶m.parser_type)); - } - fn write_stmt(&mut self, heap: &Heap, stmt_id: StatementId, indent: usize) { let stmt = &heap[stmt_id]; let indent2 = indent + 1; @@ -407,6 +398,7 @@ impl ASTWriter { Statement::Block(stmt) => { self.kv(indent).with_id(PREFIX_BLOCK_STMT_ID, stmt.this.0.index) .with_s_key("Block"); + self.kv(indent2).with_s_key("EndBlockID").with_disp_val(&stmt.end_block.0.index); self.kv(indent2).with_s_key("FirstUniqueScopeID").with_disp_val(&stmt.first_unique_id_in_scope); self.kv(indent2).with_s_key("NextUniqueScopeID").with_disp_val(&stmt.next_unique_id_in_scope); self.kv(indent2).with_s_key("RelativePos").with_disp_val(&stmt.relative_pos_in_parent); @@ -416,6 +408,11 @@ impl ASTWriter { self.write_stmt(heap, *stmt_id, indent3); } }, + Statement::EndBlock(stmt) => { + self.kv(indent).with_id(PREFIX_ENDBLOCK_STMT_ID, stmt.this.0.index) + .with_s_key("EndBlock"); + self.kv(indent2).with_s_key("StartBlockID").with_disp_val(&stmt.start_block.0.index); + } Statement::Local(stmt) => { match stmt { LocalStatement::Channel(stmt) => { diff --git a/src/protocol/eval/executor.rs b/src/protocol/eval/executor.rs new file mode 100644 index 0000000000000000000000000000000000000000..f9ce1d8964fcd9e63a44f2442b77683e47c7f3fd --- /dev/null +++ b/src/protocol/eval/executor.rs @@ -0,0 +1,550 @@ + +use std::collections::VecDeque; + +use super::value::*; +use super::store::*; +use crate::protocol::*; +use crate::protocol::ast::*; + +enum ExprInstruction { + EvalExpr(ExpressionId), + PushValToFront, +} + +struct Frame { + definition: DefinitionId, + position: StatementId, + expr_stack: VecDeque, // hack for expression evaluation, evaluated by popping from back + expr_values: VecDeque, // hack for expression results, evaluated by popping from front/back +} + +impl Frame { + /// Creates a new execution frame. Does not modify the stack in any way. + pub fn new(heap: &Heap, definition_id: DefinitionId) -> Self { + let definition = &heap[definition_id]; + let first_statement = match definition { + Definition::Component(definition) => definition.body, + Definition::Function(definition) => definition.body, + _ => unreachable!("initializing frame with {:?} instead of a function/component", definition), + }; + + Frame{ + definition: definition_id, + position: first_statement.upcast(), + expr_stack: VecDeque::with_capacity(128), + expr_values: VecDeque::with_capacity(128), + } + } + + /// Prepares a single expression for execution. This involves walking the + /// expression tree and putting them in the `expr_stack` such that + /// continuously popping from its back will evaluate the expression. The + /// results of each expression will be stored by pushing onto `expr_values`. + pub fn prepare_single_expression(&mut self, heap: &Heap, expr_id: ExpressionId) { + debug_assert!(self.expr_stack.is_empty()); + self.expr_values.clear(); // May not be empty if last expression result(s) were discarded + + self.serialize_expression(heap, expr_id); + } + + /// Prepares multiple expressions for execution (i.e. evaluating all + /// function arguments or all elements of an array/union literal). Per + /// expression this works the same as `prepare_single_expression`. However + /// after each expression is evaluated we insert a `PushValToFront` + /// instruction + pub fn prepare_multiple_expressions(&mut self, heap: &Heap, expr_ids: &[ExpressionId]) { + debug_assert!(self.expr_stack.is_empty()); + self.expr_values.clear(); + + for expr_id in expr_ids { + self.expr_stack.push_back(ExprInstruction::PushValToFront); + self.serialize_expression(heap, *expr_id); + } + } + + /// Performs depth-first serialization of expression tree. Let's not care + /// about performance for a temporary runtime implementation + fn serialize_expression(&mut self, heap: &Heap, id: ExpressionId) { + self.expr_stack.push_back(ExprInstruction::EvalExpr(id)); + + match &heap[id] { + Expression::Assignment(expr) => { + self.serialize_expression(heap, expr.left); + self.serialize_expression(heap, expr.right); + }, + Expression::Binding(expr) => { + todo!("implement binding expression"); + }, + Expression::Conditional(expr) => { + self.serialize_expression(heap, expr.test); + }, + Expression::Binary(expr) => { + self.serialize_expression(heap, expr.left); + self.serialize_expression(heap, expr.right); + }, + Expression::Unary(expr) => { + self.serialize_expression(heap, expr.expression); + }, + Expression::Indexing(expr) => { + self.serialize_expression(heap, expr.index); + self.serialize_expression(heap, expr.subject); + }, + Expression::Slicing(expr) => { + self.serialize_expression(heap, expr.from_index); + self.serialize_expression(heap, expr.to_index); + self.serialize_expression(heap, expr.subject); + }, + Expression::Select(expr) => { + self.serialize_expression(heap, expr.subject); + }, + Expression::Literal(expr) => { + // Here we only care about literals that have subexpressions + match &expr.value { + Literal::Null | Literal::True | Literal::False | + Literal::Character(_) | Literal::String(_) | + Literal::Integer(_) | Literal::Enum(_) => { + // No subexpressions + }, + Literal::Struct(literal) => { + for field in &literal.fields { + self.expr_stack.push_back(ExprInstruction::PushValToFront); + self.serialize_expression(heap, field.value); + } + }, + Literal::Union(literal) => { + for value_expr_id in &literal.values { + self.expr_stack.push_back(ExprInstruction::PushValToFront); + self.serialize_expression(heap, *value_expr_id); + } + }, + Literal::Array(value_expr_ids) => { + for value_expr_id in value_expr_ids { + self.expr_stack.push_back(ExprInstruction::PushValToFront); + self.serialize_expression(heap, *value_expr_id); + } + } + } + }, + Expression::Call(expr) => { + for arg_expr_id in &expr.arguments { + self.expr_stack.push_back(ExprInstruction::PushValToFront); + self.serialize_expression(heap, *arg_expr_id); + } + }, + Expression::Variable(expr) => { + // No subexpressions + } + } + } +} + +type EvalResult = Result<(), EvalContinuation>; +pub enum EvalContinuation { + Stepping, + Inconsistent, + Terminal, + SyncBlockStart, + SyncBlockEnd, + NewComponent(DefinitionId, ValueGroup), + BlockFires(Value), + BlockGet(Value), + Put(Value, Value), +} + +pub struct Prompt { + pub(crate) frames: Vec, + pub(crate) store: Store, +} + +impl Prompt { + pub fn new(heap: &Heap, def: DefinitionId, args: ValueGroup) -> Self { + let mut prompt = Self{ + frames: Vec::new(), + store: Store::new(), + }; + + prompt.frames.push(Frame::new(heap, def)); + args.into_store(&mut prompt.store); + + prompt + } + + pub fn step(&mut self, heap: &Heap, ctx: &mut EvalContext) -> EvalResult { + let cur_frame = self.frames.last_mut().unwrap(); + if cur_frame.position.is_invalid() { + if heap[cur_frame.definition].is_function() { + todo!("End of function without return, return an evaluation error"); + } + return Err(EvalContinuation::Terminal); + } + + while !cur_frame.expr_stack.is_empty() { + let next = cur_frame.expr_stack.pop_back().unwrap(); + match next { + ExprInstruction::PushValToFront => { + cur_frame.expr_values.rotate_right(1); + }, + ExprInstruction::EvalExpr(expr_id) => { + let expr = &heap[expr_id]; + match expr { + Expression::Assignment(expr) => { + let to = cur_frame.expr_values.pop_back().unwrap().as_ref(); + let rhs = cur_frame.expr_values.pop_back().unwrap(); + apply_assignment_operator(&mut self.store, to, expr.operation, rhs); + cur_frame.expr_values.push_back(self.store.read_copy(to)); + self.store.drop_value(&rhs); + }, + Expression::Binding(_expr) => { + todo!("Binding expression"); + }, + Expression::Conditional(expr) => { + // Evaluate testing expression, then extend the + // expression stack with the appropriate expression + let test_result = cur_frame.expr_values.pop_back().unwrap().as_bool(); + if test_result { + cur_frame.serialize_expression(heap, expr.true_expression); + } else { + cur_frame.serialize_expression(heap, expr.false_expression); + } + }, + Expression::Binary(expr) => { + let lhs = cur_frame.expr_values.pop_back().unwrap(); + let rhs = cur_frame.expr_values.pop_back().unwrap(); + let result = apply_binary_operator(&mut self.store, &lhs, expr.operation, &rhs); + cur_frame.expr_values.push_back(result); + self.store.drop_value(&lhs); + self.store.drop_value(&rhs); + }, + Expression::Unary(expr) => { + let val = cur_frame.expr_values.pop_back().unwrap(); + let result = apply_unary_operator(&mut self.store, expr.operation, &val); + cur_frame.expr_values.push_back(result); + self.store.drop_value(&val); + }, + Expression::Indexing(expr) => { + // TODO: Out of bounds checking + // Evaluate index. Never heap allocated so we do + // not have to drop it. + let index = cur_frame.expr_values.pop_back().unwrap(); + let index = match &index { + Value::Ref(value_ref) => self.store.read_ref(*value_ref), + index => index, + }; + debug_assert!(index.is_integer()); + let index = if index.is_signed_integer() { + index.as_signed_integer() as u32 + } else { + index.as_unsigned_integer() as u32 + }; + + let subject = cur_frame.expr_values.pop_back().unwrap(); + let heap_pos = match subject { + Value::Ref(value_ref) => self.store.read_ref(value_ref).as_array(), + val => val.as_array(), + }; + + cur_frame.expr_values.push_back(Value::Ref(ValueId::Heap(heap_pos, index))); + self.store.drop_value(&subject); + }, + Expression::Slicing(expr) => { + // TODO: Out of bounds checking + todo!("implement slicing") + }, + Expression::Select(expr) => { + let subject= cur_frame.expr_values.pop_back().unwrap(); + let heap_pos = match &subject { + Value::Ref(value_ref) => self.store.read_ref(*value_ref).as_struct(), + subject => subject.as_struct(), + }; + + cur_frame.expr_values.push_back(Value::Ref(ValueId::Heap(heap_pos, expr.field.as_symbolic().field_idx as u32))); + self.store.drop_value(&subject); + }, + Expression::Literal(expr) => { + let value = match &expr.value { + Literal::Null => Value::Null, + Literal::True => Value::Bool(true), + Literal::False => Value::Bool(false), + Literal::Character(lit_value) => Value::Char(*lit_value), + Literal::String(lit_value) => { + let heap_pos = self.store.alloc_heap(); + let values = &mut self.store.heap_regions[heap_pos as usize].values; + let value = lit_value.as_str(); + debug_assert!(values.is_empty()); + values.reserve(value.len()); + for character in value.as_bytes() { + debug_assert!(character.is_ascii()); + values.push(Value::Char(*character as char)); + } + Value::String(heap_pos) + } + Literal::Integer(lit_value) => { + use ConcreteTypePart as CTP; + debug_assert_eq!(expr.concrete_type.parts.len(), 1); + match expr.concrete_type.parts[0] { + CTP::UInt8 => Value::UInt8(lit_value.unsigned_value as u8), + CTP::UInt16 => Value::UInt16(lit_value.unsigned_value as u16), + CTP::UInt32 => Value::UInt32(lit_value.unsigned_value as u32), + CTP::UInt64 => Value::UInt64(lit_value.unsigned_value as u64), + CTP::SInt8 => Value::SInt8(lit_value.unsigned_value as i8), + CTP::SInt16 => Value::SInt16(lit_value.unsigned_value as i16), + CTP::SInt32 => Value::SInt32(lit_value.unsigned_value as i32), + CTP::SInt64 => Value::SInt64(lit_value.unsigned_value as i64), + _ => unreachable!(), + } + } + Literal::Struct(lit_value) => { + let heap_pos = self.store.alloc_heap(); + let num_fields = lit_value.fields.len(); + let values = &mut self.store.heap_regions[heap_pos as usize].values; + debug_assert!(values.is_empty()); + values.reserve(num_fields); + for _ in 0..num_fields { + values.push(cur_frame.expr_values.pop_front().unwrap()); + } + Value::Struct(heap_pos) + } + Literal::Enum(lit_value) => { + Value::Enum(lit_value.variant_idx as i64); + } + Literal::Union(lit_value) => { + let heap_pos = self.store.alloc_heap(); + let num_values = lit_value.values.len(); + let values = &mut self.store.heap_regions[heap_pos as usize].values; + debug_assert!(values.is_empty()); + values.reserve(num_values); + for _ in 0..num_values { + values.push(cur_frame.expr_values.pop_front().unwrap()); + } + Value::Union(lit_value.variant_idx as i64, heap_pos) + } + Literal::Array(lit_value) => { + let heap_pos = self.store.alloc_heap(); + let num_values = lit_value.len(); + let values = &mut self.store.heap_regions[heap_pos as usize].values; + debug_assert!(values.is_empty()); + values.reserve(num_values); + for _ in 0..num_values { + values.push(cur_frame.expr_values.pop_front().unwrap()) + } + } + }; + + cur_frame.expr_values.push_back(value); + }, + Expression::Call(expr) => { + // Push a new frame. Note that all expressions have + // been pushed to the front, so they're in the order + // of the definition. + let num_args = expr.arguments.len(); + + // Prepare stack for a new frame + let cur_stack_boundary = self.store.cur_stack_boundary; + self.store.cur_stack_boundary = self.store.stack.len(); + self.store.stack.push(Value::PrevStackBoundary(cur_stack_boundary as isize)); + for _ in 0..num_args { + self.store.stack.push(cur_frame.expr_values.pop_front().unwrap()); + } + + // Push the new frame + self.frames.push(Frame::new(heap, expr.definition)); + + // To simplify the logic a little bit we will now + // return and ask our caller to call us again + return Err(EvalContinuation::Stepping); + }, + Expression::Variable(expr) => { + let variable = &heap[expr.declaration.unwrap()]; + cur_frame.expr_values.push_back(Value::Ref(ValueId::Stack(variable.unique_id_in_scope as StackPos))); + } + } + } + } + } + + // No (more) expressions to evaluate. So evaluate statement (that may + // depend on the result on the last evaluated expression(s)) + let stmt = &heap[cur_frame.position]; + let return_value = match stmt { + Statement::Block(stmt) => { + // Reserve space on stack, but also make sure excess stack space + // is cleared + self.store.clear_stack(stmt.first_unique_id_in_scope as usize); + self.store.reserve_stack(stmt.next_unique_id_in_scope as usize); + cur_frame.position = stmt.statements[0]; + + Ok(()) + }, + Statement::EndBlock(stmt) => { + let block = &heap[stmt.start_block]; + self.store.clear_stack(stmt.first_unique_id_in_scope as usize); + cur_frame.position = stmt.next; + + Ok(()) + }, + Statement::Local(stmt) => { + match stmt { + LocalStatement::Memory(stmt) => { + let variable = &heap[stmt.variable]; + self.store.write(ValueId::Stack(variable.unique_id_in_scope as u32), Value::Unassigned); + + cur_frame.position = stmt.next; + }, + LocalStatement::Channel(stmt) => { + let [from_value, to_value] = ctx.new_channel(); + self.store.write(ValueId::Stack(heap[stmt.from].unique_id_in_scope as u32), from_value); + self.store.write(ValueId::Stack(heap[stmt.to].unique_id_in_scope as u32), to_value); + + cur_frame.position = stmt.next; + } + } + + Ok(()) + }, + Statement::Labeled(stmt) => { + cur_frame.position = stmt.body; + + Ok(()) + }, + Statement::If(stmt) => { + debug_assert_eq!(cur_frame.expr_values.len(), 1, "expected one expr value for if statement"); + let test_value = cur_frame.expr_values.pop_back().unwrap().as_bool(); + if test_value { + cur_frame.position = stmt.true_body.upcast(); + } else if let Some(false_body) = stmt.false_body { + cur_frame.position = false_body.upcast(); + } else { + // Not true, and no false body + cur_frame.position = stmt.end_if.unwrap().upcast(); + } + + Ok(()) + }, + Statement::EndIf(stmt) => { + cur_frame.position = stmt.next; + Ok(()) + }, + Statement::While(stmt) => { + debug_assert_eq!(cur_frame.expr_values.len(), 1, "expected one expr value for while statement"); + let test_value = cur_frame.expr_values.pop_back().unwrap().as_bool(); + if test_value { + cur_frame.position = stmt.body.upcast(); + } else { + cur_frame.position = stmt.end_while.unwrap().upcast(); + } + + Ok(()) + }, + Statement::EndWhile(stmt) => { + cur_frame.position = stmt.next; + + Ok(()) + }, + Statement::Break(stmt) => { + cur_frame.position = stmt.target.unwrap().upcast(); + + Ok(()) + }, + Statement::Continue(stmt) => { + cur_frame.position = stmt.target.unwrap().upcast(); + + Ok(()) + }, + Statement::Synchronous(stmt) => { + cur_frame.position = stmt.body.upcast(); + + Err(EvalContinuation::SyncBlockStart) + }, + Statement::EndSynchronous(stmt) => { + cur_frame.position = stmt.next; + + Err(EvalContinuation::SyncBlockEnd) + }, + Statement::Return(stmt) => { + debug_assert!(heap[cur_frame.definition].is_function()); + debug_assert_eq!(cur_frame.expr_values.len(), 1, "expected one expr value for return statement"); + + // Clear any values in the current stack frame + self.store.clear_stack(0); + + // The preceding frame has executed a call, so is expecting the + // return expression on its expression value stack. + let return_value = cur_frame.expr_values.pop_back().unwrap(); + let prev_stack_idx = self.store.stack[self.store.cur_stack_boundary].as_stack_boundary(); + debug_assert!(prev_stack_idx >= 0); + self.store.cur_stack_boundary = prev_stack_idx as usize; + self.frames.pop(); + let cur_frame = self.frames.last_mut().unwrap(); + cur_frame.expr_values.push_back(return_value); + + // Immediately return, we don't care about the current frame + // anymore and there is nothing left to evaluate + return Ok(()); + }, + Statement::Goto(stmt) => { + cur_frame.position = stmt.target.unwrap().upcast(); + + Ok(()) + }, + Statement::New(stmt) => { + let call_expr = &heap[stmt.expression]; + debug_assert!(heap[call_expr.definition].is_component()); + debug_assert_eq!( + cur_frame.expr_values.len(), heap[call_expr.definition].parameters().len(), + "mismatch in expr stack size and number of arguments for new statement" + ); + + // Note that due to expression value evaluation they exist in + // reverse order on the stack. + // TODO: Revise this code, keep it as is to be compatible with current runtime + let mut args = Vec::new(); + while let Some(value) = cur_frame.expr_values.pop_front() { + args.push(value); + } + + cur_frame.position = stmt.next; + + todo!("Make sure this is handled correctly, transfer 'heap' values to another Prompt"); + Err(EvalContinuation::NewComponent(call_expr.definition, args)) + }, + Statement::Expression(stmt) => { + // The expression has just been completely evaluated. Some + // values might have remained on the expression value stack. + cur_frame.expr_values.clear(); + cur_frame.position = stmt.next; + + Ok(()) + }, + }; + + // If the next statement requires evaluating expressions then we push + // these onto the expression stack. This way we will evaluate this + // stack in the next loop, then evaluate the statement using the result + // from the expression evaluation. + if !cur_frame.position.is_invalid() { + let stmt = &heap[cur_frame.position]; + + match stmt { + Statement::If(stmt) => cur_frame.prepare_single_expression(heap, stmt.test), + Statement::While(stmt) => cur_frame.prepare_single_expression(heap, stmt.test), + Statement::Return(stmt) => { + debug_assert_eq!(stmt.expressions.len(), 1); // TODO: @ReturnValues + cur_frame.prepare_single_expression(heap, stmt.expressions[0]); + }, + Statement::New(stmt) => { + // Note that we will end up not evaluating the call itself. + // Rather we will evaluate its expressions and then + // instantiate the component upon reaching the "new" stmt. + let call_expr = &heap[stmt.expression]; + cur_frame.prepare_multiple_expressions(heap, &call_expr.arguments); + }, + Statement::Expression(stmt) => { + cur_frame.prepare_single_expression(heap, stmt.expression); + } + _ => {}, + } + } + + return_value + } +} \ No newline at end of file diff --git a/src/protocol/eval/mod.rs b/src/protocol/eval/mod.rs index 83d73efd843af124e3a0f27f213407d3e5809ff8..d234f378e8c6e78306a6287808fbe9ffa844756c 100644 --- a/src/protocol/eval/mod.rs +++ b/src/protocol/eval/mod.rs @@ -16,717 +16,14 @@ /// careful with values that reside in the "heap" and make sure that copies are /// properly removed from the heap.. /// -/// Just to reiterate: this is a temporary implementation. A proper +/// Just to reiterate: this is a temporary wasteful implementation. A proper /// implementation would fully fill out the type table with alignment/size/ /// offset information and lay out bytecode. mod value; +mod store; +mod executor; -use std::collections::VecDeque; +pub use value::{Value, ValueGroup}; +pub use executor::{EvalContinuation, Prompt}; -use super::value::*; -use crate::PortId; -use crate::protocol::ast::*; -use crate::protocol::*; - -struct HeapAllocation { - values: Vec, -} - -struct Store { - // The stack where variables/parameters are stored. Note that this is a - // non-shrinking stack. So it may be filled with garbage. - stack: Vec, - // Represents the place in the stack where we find the `PrevStackBoundary` - // value containing the previous stack boundary. This is so we can pop from - // the stack after function calls. - cur_stack_boundary: usize, - // A rather ridiculous simulated heap, but this allows us to "allocate" - // things that occupy more then one stack slot. - heap_regions: Vec, - free_regions: VecDeque, -} - -impl Store { - fn new() -> Self { - let mut store = Self{ - stack: Vec::with_capacity(64), - cur_stack_boundary: 0, - heap_regions: Vec::new(), - free_regions: VecDeque::new(), - }; - - store.stack.push(Value::PrevStackBoundary(-1)); - store - } - - /// Resizes(!) the stack to fit the required number of values. Any - /// unallocated slots are initialized to `Unassigned`. The specified stack - /// index is exclusive. - fn reserve_stack(&mut self, unique_stack_idx: usize) { - let new_size = self.cur_stack_boundary + unique_stack_idx + 1; - if new_size > self.stack.len() { - self.stack.resize(new_size, Value::Unassigned); - } - } - - /// Clears values on the stack and removes their heap allocations when - /// applicable. The specified index itself will also be cleared (so if you - /// specify 0 all values in the frame will be destroyed) - fn clear_stack(&mut self, unique_stack_idx: usize) { - let new_size = self.cur_stack_boundary + unique_stack_idx + 1; - for idx in new_size..self.stack.len() { - self.drop_value(&self.stack[idx]); - self.stack[idx] = Value::Unassigned; - } - } - - /// Reads a value from a specific address. The value is always copied, hence - /// if the value ends up not being written, one should call `drop_value` on - /// it. - fn read_copy(&mut self, address: ValueId) -> Value { - match value { - ValueId::Stack(pos) => { - let cur_pos = self.cur_stack_boundary + 1 + pos as usize; - return self.clone_value(&self.stack[cur_pos]); - }, - ValueId::Heap(heap_pos, region_idx) => { - return self.clone_value(&self.heap_regions[heap_pos as usize].values[region_idx as usize]) - } - } - } - - /// Returns an immutable reference to the value pointed to by an address - fn read_ref(&mut self, address: ValueId) -> &Value { - match value { - ValueId::Stack(pos) => { - let cur_pos = self.cur_stack_boundary + 1 + pos as usize; - return &self.stack[cur_pos]; - }, - ValueId::Heap(heap_pos, region_idx) => { - return &self.heap_regions[heap_pos as usize].values[region_idx as usize]; - } - } - } - - /// Returns a mutable reference to the value pointed to by an address - fn read_mut_ref(&mut self, address: ValueId) -> &mut Value { - match value { - ValueId::Stack(pos) => { - let cur_pos = self.cur_stack_boundary + 1 + pos as usize; - return &mut self.stack[cur_pos]; - }, - ValueId::Heap(heap_pos, region_idx) => { - return &mut self.heap_regions[heap_pos as usize].values[region_idx as usize]; - } - } - } - - /// Writes a value - fn write(&mut self, address: ValueId, value: Value) { - match address { - ValueId::Stack(pos) => { - let cur_pos = self.cur_stack_boundary + 1 + pos as usize; - self.drop_value(&self.stack[cur_pos]); - self.stack[cur_pos] = value; - }, - ValueId::Heap(heap_pos, region_idx) => { - let heap_pos = heap_pos as usize; - let region_idx = region_idx as usize; - self.drop_value(&self.heap_regions[heap_pos].values[region_idx]); - self.heap_regions[heap_pos].values[region_idx] = value - } - } - } - - fn clone_value(&mut self, value: &Value) -> Value { - // Quickly check if the value is not on the heap - let source_heap_pos = value.get_heap_pos(); - if source_heap_pos.is_none() { - // We can do a trivial copy - return value.clone(); - } - - // Value does live on heap, copy it - let source_heap_pos = source_heap_pos.unwrap() as usize; - let target_heap_pos = self.alloc_heap(); - let target_heap_pos_usize = target_heap_pos as usize; - - let num_values = self.heap_regions[source_heap_pos].values.len(); - for value_idx in 0..num_values { - let cloned = self.clone_value(&self.heap_regions[source_heap_pos].values[value_idx]); - self.heap_regions[target_heap_pos_usize].values.push(cloned); - } - - match value { - Value::Message(_) => Value::Message(target_heap_pos), - Value::Array(_) => Value::Array(target_heap_pos), - Value::Union(tag, _) => Value::Union(*tag, target_heap_pos), - Value::Struct(_) => Value::Struct(target_heap_pos), - _ => unreachable!("performed clone_value on heap, but {:?} is not a heap value", value), - } - } - - fn drop_value(&mut self, value: &Value) { - if let Some(heap_pos) = value.get_heap_pos() { - self.drop_heap_pos(heap_pos); - } - } - - fn drop_heap_pos(&mut self, heap_pos: HeapPos) { - let num_values = self.heap_regions[heap_pos as usize].values.len(); - for value_idx in 0..num_values { - if let Some(other_heap_pos) = self.heap_regions[heap_pos as usize].values[value_idx].get_heap_pos() { - self.drop_heap_pos(other_heap_pos); - } - } - - self.heap_regions[heap_pos as usize].values.clear(); - self.free_regions.push_back(heap_pos); - } - - fn alloc_heap(&mut self) -> HeapPos { - if self.free_regions.is_empty() { - let idx = self.heap_regions.len() as HeapPos; - self.heap_regions.push(HeapAllocation{ values: Vec::new() }); - return idx; - } else { - let idx = self.free_regions.pop_back().unwrap(); - return idx; - } - } -} - -enum ExprInstruction { - EvalExpr(ExpressionId), - PushValToFront, -} - -struct Frame { - definition: DefinitionId, - position: StatementId, - expr_stack: VecDeque, // hack for expression evaluation, evaluated by popping from back - expr_values: VecDeque, // hack for expression results, evaluated by popping from front/back -} - -impl Frame { - /// Creates a new execution frame. Does not modify the stack in any way. - pub fn new(heap: &Heap, definition_id: DefinitionId) -> Self { - let definition = &heap[definition_id]; - let first_statement = match definition { - Definition::Component(definition) => definition.body, - Definition::Function(definition) => definition.body, - _ => unreachable!("initializing frame with {:?} instead of a function/component", definition), - }; - - Frame{ - definition: definition_id, - position: first_statement.upcast(), - expr_stack: VecDeque::with_capacity(128), - expr_values: VecDeque::with_capacity(128), - } - } - - /// Prepares a single expression for execution. This involves walking the - /// expression tree and putting them in the `expr_stack` such that - /// continuously popping from its back will evaluate the expression. The - /// results of each expression will be stored by pushing onto `expr_values`. - pub fn prepare_single_expression(&mut self, heap: &Heap, expr_id: ExpressionId) { - debug_assert!(self.expr_stack.is_empty()); - self.expr_values.clear(); // May not be empty if last expression result(s) were discarded - - self.serialize_expression(heap, expr_id); - } - - /// Prepares multiple expressions for execution (i.e. evaluating all - /// function arguments or all elements of an array/union literal). Per - /// expression this works the same as `prepare_single_expression`. However - /// after each expression is evaluated we insert a `PushValToFront` - /// instruction - pub fn prepare_multiple_expressions(&mut self, heap: &Heap, expr_ids: &[ExpressionId]) { - debug_assert!(self.expr_stack.is_empty()); - self.expr_values.clear(); - - for expr_id in expr_ids { - self.expr_stack.push_back(ExprInstruction::PushValToFront); - self.serialize_expression(heap, *expr_id); - } - } - - /// Performs depth-first serialization of expression tree. Let's not care - /// about performance for a temporary runtime implementation - fn serialize_expression(&mut self, heap: &Heap, id: ExpressionId) { - self.expr_stack.push_back(ExprInstruction::EvalExpr(id)); - - match &heap[id] { - Expression::Assignment(expr) => { - self.serialize_expression(heap, expr.left); - self.serialize_expression(heap, expr.right); - }, - Expression::Binding(expr) => { - todo!("implement binding expression"); - }, - Expression::Conditional(expr) => { - self.serialize_expression(heap, expr.test); - }, - Expression::Binary(expr) => { - self.serialize_expression(heap, expr.left); - self.serialize_expression(heap, expr.right); - }, - Expression::Unary(expr) => { - self.serialize_expression(heap, expr.expression); - }, - Expression::Indexing(expr) => { - self.serialize_expression(heap, expr.index); - self.serialize_expression(heap, expr.subject); - }, - Expression::Slicing(expr) => { - self.serialize_expression(heap, expr.from_index); - self.serialize_expression(heap, expr.to_index); - self.serialize_expression(heap, expr.subject); - }, - Expression::Select(expr) => { - self.serialize_expression(heap, expr.subject); - }, - Expression::Literal(expr) => { - // Here we only care about literals that have subexpressions - match &expr.value { - Literal::Null | Literal::True | Literal::False | - Literal::Character(_) | Literal::String(_) | - Literal::Integer(_) | Literal::Enum(_) => { - // No subexpressions - }, - Literal::Struct(literal) => { - for field in &literal.fields { - self.expr_stack.push_back(ExprInstruction::PushValToFront); - self.serialize_expression(heap, field.value); - } - }, - Literal::Union(literal) => { - for value_expr_id in &literal.values { - self.expr_stack.push_back(ExprInstruction::PushValToFront); - self.serialize_expression(heap, *value_expr_id); - } - }, - Literal::Array(value_expr_ids) => { - for value_expr_id in value_expr_ids { - self.expr_stack.push_back(ExprInstruction::PushValToFront); - self.serialize_expression(heap, *value_expr_id); - } - } - } - }, - Expression::Call(expr) => { - for arg_expr_id in &expr.arguments { - self.expr_stack.push_back(ExprInstruction::PushValToFront); - self.serialize_expression(heap, *arg_expr_id); - } - }, - Expression::Variable(expr) => { - // No subexpressions - } - } - } -} - -type EvalResult = Result<(), EvalContinuation>; -pub enum EvalContinuation { - Stepping, - Inconsistent, - Terminal, - SyncBlockStart, - SyncBlockEnd, - NewComponent(DefinitionId, Vec), - BlockFires(Value), - BlockGet(Value), - Put(Value, Value), -} - -pub struct Prompt { - frames: Vec, - store: Store, -} - -impl Prompt { - pub fn new(heap: &Heap, def: DefinitionId) -> Self { - let mut prompt = Self{ - frames: Vec::new(), - store: Store::new(), - }; - - prompt.frames.push(Frame::new(heap, def)); - prompt - } - - pub fn step(&mut self, heap: &Heap, ctx: &mut EvalContext) -> EvalResult { - let cur_frame = self.frames.last_mut().unwrap(); - if cur_frame.position.is_invalid() { - if heap[cur_frame.definition].is_function() { - todo!("End of function without return, return an evaluation error"); - } - return Err(EvalContinuation::Terminal); - } - - while !cur_frame.expr_stack.is_empty() { - let next = cur_frame.expr_stack.pop_back().unwrap(); - match next { - ExprInstruction::PushValToFront => { - cur_frame.expr_values.rotate_right(1); - }, - ExprInstruction::EvalExpr(expr_id) => { - let expr = &heap[expr_id]; - match expr { - Expression::Assignment(expr) => { - let to = cur_frame.expr_values.pop_back().unwrap().as_ref(); - let rhs = cur_frame.expr_values.pop_back().unwrap(); - apply_assignment_operator(&mut self.store, to, expr.operation, rhs); - cur_frame.expr_values.push_back(self.store.read_copy(to)); - self.store.drop_value(&rhs); - }, - Expression::Binding(_expr) => { - todo!("Binding expression"); - }, - Expression::Conditional(expr) => { - // Evaluate testing expression, then extend the - // expression stack with the appropriate expression - let test_result = cur_frame.expr_values.pop_back().unwrap().as_bool(); - if test_result { - cur_frame.serialize_expression(heap, expr.true_expression); - } else { - cur_frame.serialize_expression(heap, expr.false_expression); - } - }, - Expression::Binary(expr) => { - let lhs = cur_frame.expr_values.pop_back().unwrap(); - let rhs = cur_frame.expr_values.pop_back().unwrap(); - let result = apply_binary_operator(&mut self.store, &lhs, expr.operation, &rhs); - cur_frame.expr_values.push_back(result); - self.store.drop_value(&lhs); - self.store.drop_value(&rhs); - }, - Expression::Unary(expr) => { - let val = cur_frame.expr_values.pop_back().unwrap(); - let result = apply_unary_operator(&mut self.store, expr.operation, &val); - cur_frame.expr_values.push_back(result); - self.store.drop_value(&val); - }, - Expression::Indexing(expr) => { - // TODO: Out of bounds checking - // Evaluate index. Never heap allocated so we do - // not have to drop it. - let index = cur_frame.expr_values.pop_back().unwrap(); - let index = match &index { - Value::Ref(value_ref) => self.store.read_ref(*value_ref), - index => index, - }; - debug_assert!(deref.is_integer()); - let index = if index.is_signed_integer() { - index.as_signed_integer() as u32 - } else { - index.as_unsigned_integer() as u32 - }; - - let subject = cur_frame.expr_values.pop_back().unwrap(); - let heap_pos = match val { - Value::Ref(value_ref) => self.store.read_ref(value_ref).as_array(), - val => val.as_array(), - }; - - cur_frame.expr_values.push_back(Value::Ref(ValueId::Heap(heap_pos, index))); - self.store.drop_value(&subject); - }, - Expression::Slicing(expr) => { - // TODO: Out of bounds checking - todo!("implement slicing") - }, - Expression::Select(expr) => { - let subject= cur_frame.expr_values.pop_back().unwrap(); - let heap_pos = match &subject { - Value::Ref(value_ref) => self.store.read_ref(*value_ref).as_struct(), - subject => subject.as_struct(), - }; - - cur_frame.expr_values.push_back(Value::Ref(ValueId::Heap(heap_pos, expr.field.as_symbolic().field_idx as u32))); - self.store.drop_value(&subject); - }, - Expression::Literal(expr) => { - let value = match &expr.value { - Literal::Null => Value::Null, - Literal::True => Value::Bool(true), - Literal::False => Value::Bool(false), - Literal::Character(lit_value) => Value::Char(*lit_value), - Literal::String(lit_value) => { - let heap_pos = self.store.alloc_heap(); - let values = &mut self.store.heap_regions[heap_pos as usize].values; - let value = lit_value.as_str(); - debug_assert!(values.is_empty()); - values.reserve(value.len()); - for character in value.as_bytes() { - debug_assert!(character.is_ascii()); - values.push(Value::Char(*character as char)); - } - Value::String(heap_pos) - } - Literal::Integer(lit_value) => { - use ConcreteTypePart as CTP; - debug_assert_eq!(expr.concrete_type.parts.len(), 1); - match expr.concrete_type.parts[0] { - CTP::UInt8 => Value::UInt8(lit_value.unsigned_value as u8), - CTP::UInt16 => Value::UInt16(lit_value.unsigned_value as u16), - CTP::UInt32 => Value::UInt32(lit_value.unsigned_value as u32), - CTP::UInt64 => Value::UInt64(lit_value.unsigned_value as u64), - CTP::SInt8 => Value::SInt8(lit_value.unsigned_value as i8), - CTP::SInt16 => Value::SInt16(lit_value.unsigned_value as i16), - CTP::SInt32 => Value::SInt32(lit_value.unsigned_value as i32), - CTP::SInt64 => Value::SInt64(lit_value.unsigned_value as i64), - _ => unreachable!(), - } - } - Literal::Struct(lit_value) => { - let heap_pos = self.store.alloc_heap(); - let num_fields = lit_value.fields.len(); - let values = &mut self.store.heap_regions[heap_pos as usize].values; - debug_assert!(values.is_empty()); - values.reserve(num_fields); - for _ in 0..num_fields { - values.push(cur_frame.expr_values.pop_front().unwrap()); - } - Value::Struct(heap_pos) - } - Literal::Enum(lit_value) => { - Value::Enum(lit_value.variant_idx as i64); - } - Literal::Union(lit_value) => { - let heap_pos = self.store.alloc_heap(); - let num_values = lit_value.values.len(); - let values = &mut self.store.heap_regions[heap_pos as usize].values; - debug_assert!(values.is_empty()); - values.reserve(num_values); - for _ in 0..num_values { - values.push(cur_frame.expr_values.pop_front().unwrap()); - } - Value::Union(lit_value.variant_idx as i64, heap_pos) - } - Literal::Array(lit_value) => { - let heap_pos = self.store.alloc_heap(); - let num_values = lit_value.len(); - let values = &mut self.store.heap_regions[heap_pos as usize].values; - debug_assert!(values.is_empty()); - values.reserve(num_values); - for _ in 0..num_values { - values.push(cur_frame.expr_values.pop_front().unwrap()) - } - } - }; - - cur_frame.expr_values.push_back(value); - }, - Expression::Call(expr) => { - // Push a new frame. Note that all expressions have - // been pushed to the front, so they're in the order - // of the definition. - let num_args = expr.arguments.len(); - - // Prepare stack for a new frame - let cur_stack_boundary = self.store.cur_stack_boundary; - self.store.cur_stack_boundary = self.store.stack.len(); - self.store.stack.push(Value::PrevStackBoundary(cur_stack_boundary as isize)); - for _ in 0..num_args { - self.store.stack.push(cur_frame.expr_values.pop_front().unwrap()); - } - - // Push the new frame - self.frames.push(Frame::new(heap, expr.definition)); - - // To simplify the logic a little bit we will now - // return and ask our caller to call us again - return Err(EvalContinuation::Stepping); - }, - Expression::Variable(expr) => { - let variable = &heap[expr.declaration.unwrap()]; - cur_frame.expr_values.push_back(Value::Ref(ValueId::Stack(variable.unique_id_in_scope as StackPos))); - } - } - } - } - } - - // No (more) expressions to evaluate. So evaluate statement (that may - // depend on the result on the last evaluated expression(s)) - let stmt = &heap[cur_frame.position]; - let return_value = match stmt { - Statement::Block(stmt) => { - // Reserve space on stack, but also make sure excess stack space - // is cleared - self.store.clear_stack(stmt.first_unique_id_in_scope as usize); - self.store.reserve_stack(stmt.next_unique_id_in_scope as usize); - cur_frame.position = stmt.statements[0]; - - Ok(()) - }, - Statement::Local(stmt) => { - match stmt { - LocalStatement::Memory(stmt) => { - let variable = &heap[stmt.variable]; - self.store.write(ValueId::Stack(variable.unique_id_in_scope as u32), Value::Unassigned); - - cur_frame.position = stmt.next; - }, - LocalStatement::Channel(stmt) => { - let [from_value, to_value] = ctx.new_channel(); - self.store.write(ValueId::Stack(heap[stmt.from].unique_id_in_scope as u32), from_value); - self.store.write(ValueId::Stack(heap[stmt.to].unique_id_in_scope as u32), to_value); - - cur_frame.position = stmt.next; - } - } - - Ok(()) - }, - Statement::Labeled(stmt) => { - cur_frame.position = stmt.body; - - Ok(()) - }, - Statement::If(stmt) => { - debug_assert_eq!(cur_frame.expr_values.len(), 1, "expected one expr value for if statement"); - let test_value = cur_frame.expr_values.pop_back().unwrap().as_bool(); - if test_value { - cur_frame.position = stmt.true_body.upcast(); - } else if let Some(false_body) = stmt.false_body { - cur_frame.position = false_body.upcast(); - } else { - // Not true, and no false body - cur_frame.position = stmt.end_if.unwrap().upcast(); - } - - Ok(()) - }, - Statement::EndIf(stmt) => { - cur_frame.position = stmt.next; - Ok(()) - }, - Statement::While(stmt) => { - debug_assert_eq!(cur_frame.expr_values.len(), 1, "expected one expr value for while statement"); - let test_value = cur_frame.expr_values.pop_back().unwrap().as_bool(); - if test_value { - cur_frame.position = stmt.body.upcast(); - } else { - cur_frame.position = stmt.end_while.unwrap().upcast(); - } - - Ok(()) - }, - Statement::EndWhile(stmt) => { - cur_frame.position = stmt.next; - - Ok(()) - }, - Statement::Break(stmt) => { - cur_frame.position = stmt.target.unwrap().upcast(); - - Ok(()) - }, - Statement::Continue(stmt) => { - cur_frame.position = stmt.target.unwrap().upcast(); - - Ok(()) - }, - Statement::Synchronous(stmt) => { - cur_frame.position = stmt.body.upcast(); - - Err(EvalContinuation::SyncBlockStart) - }, - Statement::EndSynchronous(stmt) => { - cur_frame.position = stmt.next; - - Err(EvalContinuation::SyncBlockEnd) - }, - Statement::Return(stmt) => { - debug_assert!(heap[cur_frame.definition].is_function()); - debug_assert_eq!(cur_frame.expr_values.len(), 1, "expected one expr value for return statement"); - - // Clear any values in the current stack frame - self.store.clear_stack(0); - - // The preceding frame has executed a call, so is expecting the - // return expression on its expression value stack. - let return_value = cur_frame.expr_values.pop_back().unwrap(); - let prev_stack_idx = self.store.stack[self.store.cur_stack_boundary].as_stack_boundary(); - debug_assert!(prev_stack_idx >= 0); - self.store.cur_stack_boundary = prev_stack_idx as usize; - self.frames.pop(); - let cur_frame = self.frames.last_mut().unwrap(); - cur_frame.expr_values.push_back(return_value); - - // Immediately return, we don't care about the current frame - // anymore and there is nothing left to evaluate - return Ok(()); - }, - Statement::Goto(stmt) => { - cur_frame.position = stmt.target.unwrap().upcast(); - - Ok(()) - }, - Statement::New(stmt) => { - let call_expr = &heap[stmt.expression]; - debug_assert!(heap[call_expr.definition].is_component()); - debug_assert_eq!( - cur_frame.expr_values.len(), heap[call_expr.definition].parameters().len(), - "mismatch in expr stack size and number of arguments for new statement" - ); - - // Note that due to expression value evaluation they exist in - // reverse order on the stack. - // TODO: Revise this code, keep it as is to be compatible with current runtime - let mut args = Vec::new(); - while let Some(value) = cur_frame.expr_values.pop_front() { - args.push(value); - } - - cur_frame.position = stmt.next; - - todo!("Make sure this is handled correctly, transfer 'heap' values to another Prompt"); - Err(EvalContinuation::NewComponent(call_expr.definition, args)) - }, - Statement::Expression(stmt) => { - // The expression has just been completely evaluated. Some - // values might have remained on the expression value stack. - cur_frame.expr_values.clear(); - cur_frame.position = stmt.next; - - Ok(()) - }, - }; - - // If the next statement requires evaluating expressions then we push - // these onto the expression stack. This way we will evaluate this - // stack in the next loop, then evaluate the statement using the result - // from the expression evaluation. - if !cur_frame.position.is_invalid() { - let stmt = &heap[cur_frame.position]; - - match stmt { - Statement::If(stmt) => cur_frame.prepare_single_expression(heap, stmt.test), - Statement::While(stmt) => cur_frame.prepare_single_expression(heap, stmt.test), - Statement::Return(stmt) => { - debug_assert_eq!(stmt.expressions.len(), 1); // TODO: @ReturnValues - cur_frame.prepare_single_expression(heap, stmt.expressions[0]); - }, - Statement::New(stmt) => { - // Note that we will end up not evaluating the call itself. - // Rather we will evaluate its expressions and then - // instantiate the component upon reaching the "new" stmt. - let call_expr = &heap[stmt.expression]; - cur_frame.prepare_multiple_expressions(heap, &call_expr.arguments); - }, - Statement::Expression(stmt) => { - cur_frame.prepare_single_expression(heap, stmt.expression); - } - _ => {}, - } - } - - return_value - } -} \ No newline at end of file diff --git a/src/protocol/eval/store.rs b/src/protocol/eval/store.rs new file mode 100644 index 0000000000000000000000000000000000000000..ac6a01d709149e186b655189a7a31194c1f25b6a --- /dev/null +++ b/src/protocol/eval/store.rs @@ -0,0 +1,172 @@ + +use std::collections::VecDeque; + +use super::value::{Value, ValueId, HeapPos}; + +pub(crate) struct HeapAllocation { + pub values: Vec, +} + +pub(crate) struct Store { + // The stack where variables/parameters are stored. Note that this is a + // non-shrinking stack. So it may be filled with garbage. + pub(crate) stack: Vec, + // Represents the place in the stack where we find the `PrevStackBoundary` + // value containing the previous stack boundary. This is so we can pop from + // the stack after function calls. + pub(crate) cur_stack_boundary: usize, + // A rather ridiculous simulated heap, but this allows us to "allocate" + // things that occupy more then one stack slot. + pub(crate) heap_regions: Vec, + pub(crate) free_regions: VecDeque, +} + +impl Store { + pub(crate) fn new() -> Self { + let mut store = Self{ + stack: Vec::with_capacity(64), + cur_stack_boundary: 0, + heap_regions: Vec::new(), + free_regions: VecDeque::new(), + }; + + store.stack.push(Value::PrevStackBoundary(-1)); + store + } + + /// Resizes(!) the stack to fit the required number of values. Any + /// unallocated slots are initialized to `Unassigned`. The specified stack + /// index is exclusive. + pub(crate) fn reserve_stack(&mut self, unique_stack_idx: usize) { + let new_size = self.cur_stack_boundary + unique_stack_idx + 1; + if new_size > self.stack.len() { + self.stack.resize(new_size, Value::Unassigned); + } + } + + /// Clears values on the stack and removes their heap allocations when + /// applicable. The specified index itself will also be cleared (so if you + /// specify 0 all values in the frame will be destroyed) + pub(crate) fn clear_stack(&mut self, unique_stack_idx: usize) { + let new_size = self.cur_stack_boundary + unique_stack_idx + 1; + for idx in new_size..self.stack.len() { + self.drop_value(&self.stack[idx]); + self.stack[idx] = Value::Unassigned; + } + } + + /// Reads a value from a specific address. The value is always copied, hence + /// if the value ends up not being written, one should call `drop_value` on + /// it. + pub(crate) fn read_copy(&mut self, address: ValueId) -> Value { + match address { + ValueId::Stack(pos) => { + let cur_pos = self.cur_stack_boundary + 1 + pos as usize; + return self.clone_value(&self.stack[cur_pos]); + }, + ValueId::Heap(heap_pos, region_idx) => { + return self.clone_value(&self.heap_regions[heap_pos as usize].values[region_idx as usize]) + } + } + } + + /// Returns an immutable reference to the value pointed to by an address + pub(crate) fn read_ref(&mut self, address: ValueId) -> &Value { + match address { + ValueId::Stack(pos) => { + let cur_pos = self.cur_stack_boundary + 1 + pos as usize; + return &self.stack[cur_pos]; + }, + ValueId::Heap(heap_pos, region_idx) => { + return &self.heap_regions[heap_pos as usize].values[region_idx as usize]; + } + } + } + + /// Returns a mutable reference to the value pointed to by an address + pub(crate) fn read_mut_ref(&mut self, address: ValueId) -> &mut Value { + match address { + ValueId::Stack(pos) => { + let cur_pos = self.cur_stack_boundary + 1 + pos as usize; + return &mut self.stack[cur_pos]; + }, + ValueId::Heap(heap_pos, region_idx) => { + return &mut self.heap_regions[heap_pos as usize].values[region_idx as usize]; + } + } + } + + /// Writes a value + pub(crate) fn write(&mut self, address: ValueId, value: Value) { + match address { + ValueId::Stack(pos) => { + let cur_pos = self.cur_stack_boundary + 1 + pos as usize; + self.drop_value(&self.stack[cur_pos]); + self.stack[cur_pos] = value; + }, + ValueId::Heap(heap_pos, region_idx) => { + let heap_pos = heap_pos as usize; + let region_idx = region_idx as usize; + self.drop_value(&self.heap_regions[heap_pos].values[region_idx]); + self.heap_regions[heap_pos].values[region_idx] = value + } + } + } + + fn clone_value(&mut self, value: &Value) -> Value { + // Quickly check if the value is not on the heap + let source_heap_pos = value.get_heap_pos(); + if source_heap_pos.is_none() { + // We can do a trivial copy + return value.clone(); + } + + // Value does live on heap, copy it + let source_heap_pos = source_heap_pos.unwrap() as usize; + let target_heap_pos = self.alloc_heap(); + let target_heap_pos_usize = target_heap_pos as usize; + + let num_values = self.heap_regions[source_heap_pos].values.len(); + for value_idx in 0..num_values { + let cloned = self.clone_value(&self.heap_regions[source_heap_pos].values[value_idx]); + self.heap_regions[target_heap_pos_usize].values.push(cloned); + } + + match value { + Value::Message(_) => Value::Message(target_heap_pos), + Value::Array(_) => Value::Array(target_heap_pos), + Value::Union(tag, _) => Value::Union(*tag, target_heap_pos), + Value::Struct(_) => Value::Struct(target_heap_pos), + _ => unreachable!("performed clone_value on heap, but {:?} is not a heap value", value), + } + } + + pub(crate) fn drop_value(&mut self, value: &Value) { + if let Some(heap_pos) = value.get_heap_pos() { + self.drop_heap_pos(heap_pos); + } + } + + pub(crate) fn drop_heap_pos(&mut self, heap_pos: HeapPos) { + let num_values = self.heap_regions[heap_pos as usize].values.len(); + for value_idx in 0..num_values { + if let Some(other_heap_pos) = self.heap_regions[heap_pos as usize].values[value_idx].get_heap_pos() { + self.drop_heap_pos(other_heap_pos); + } + } + + self.heap_regions[heap_pos as usize].values.clear(); + self.free_regions.push_back(heap_pos); + } + + pub(crate) fn alloc_heap(&mut self) -> HeapPos { + if self.free_regions.is_empty() { + let idx = self.heap_regions.len() as HeapPos; + self.heap_regions.push(HeapAllocation{ values: Vec::new() }); + return idx; + } else { + let idx = self.free_regions.pop_back().unwrap(); + return idx; + } + } +} \ No newline at end of file diff --git a/src/protocol/eval/value.rs b/src/protocol/eval/value.rs index 8dc006f2f8ced17594cc867729b5e92486996f27..af3c0d9a009887cb98bb27d38caed6747d99b305 100644 --- a/src/protocol/eval/value.rs +++ b/src/protocol/eval/value.rs @@ -1,11 +1,11 @@ +use super::store::*; use crate::PortId; use crate::protocol::ast::{ AssignmentOperator, BinaryOperator, UnaryOperator, }; -use crate::protocol::eval::Store; pub type StackPos = u32; pub type HeapPos = u32; @@ -16,6 +16,10 @@ pub enum ValueId { Heap(HeapPos, u32), // allocated region + values within that region } +/// Represents a value stored on the stack or on the heap. Some values contain +/// a `HeapPos`, implying that they're stored in the store's `Heap`. Clearing +/// a `Value` with a `HeapPos` from a stack must also clear the associated +/// region from the `Heap`. #[derive(Debug, Clone)] pub enum Value { // Special types, never encountered during evaluation if the compiler works correctly @@ -141,9 +145,118 @@ impl Value { } } -/// Applies the assignment operator. If a heap position is returned then that -/// heap position should be cleared -pub(crate) fn apply_assignment_operator(store: &mut Store, lhs: ValueRef, op: AssignmentOperator, rhs: Value) { +/// When providing arguments to a new component, or when transferring values +/// from one component's store to a newly instantiated component, one has to +/// transfer stack and heap values. This `ValueGroup` represents such a +/// temporary group of values with potential heap allocations. +/// +/// Constructing such a ValueGroup manually requires some extra care to make +/// sure all elements of `values` point to valid elements of `regions`. +/// +/// Again: this is a temporary thing, hopefully removed once we move to a +/// bytecode interpreter. +pub struct ValueGroup { + pub(crate) values: Vec, + pub(crate) regions: Vec> +} + +impl ValueGroup { + pub(crate) fn new_stack(values: Vec) -> Self { + debug_assert!(values.iter().all(|v| v.get_heap_pos().is_none())); + Self{ + values, + regions: Vec::new(), + } + } + pub(crate) fn from_store(store: &Store, values: &[Value]) -> Self { + let mut group = ValueGroup{ + values: Vec::with_capacity(values.len()), + regions: Vec::with_capacity(values.len()), // estimation + }; + + for value in values { + let transferred = group.retrieve_value(value, store); + group.values.push(transferred); + } + + group + } + + /// Transfers a provided value from a store into a local value with its + /// heap allocations (if any) stored in the ValueGroup. Calling this + /// function will not store the returned value in the `values` member. + fn retrieve_value(&mut self, value: &Value, from_store: &Store) -> Value { + if let Some(heap_pos) = value.get_heap_pos() { + // Value points to a heap allocation, so transfer the heap values + // internally. + let from_region = &from_store.heap_regions[heap_pos as usize].values; + let mut new_region = Vec::with_capacity(from_region.len()); + for value in from_region { + let transferred = self.transfer_value(value, from_store); + new_region.push(transferred); + } + + // Region is constructed, store internally and return the new value. + let new_region_idx = self.regions.len() as HeapPos; + self.regions.push(new_region); + + return match value { + Value::Message(_) => Value::Message(new_region_idx), + Value::String(_) => Value::String(new_region_idx), + Value::Array(_) => Value::Array(new_region_idx), + Value::Union(tag, _) => Value::Union(*tag, new_region_idx), + Value::Struct(_) => Value::Struct(new_region_idx), + _ => unreachable!(), + }; + } else { + return value.clone(); + } + } + + /// Transfers the heap values and the stack values into the store. Stack + /// values are pushed onto the Store's stack in the order in which they + /// appear in the value group. + pub fn into_store(self, store: &mut Store) { + for value in &self.values { + let transferred = self.provide_value(value, store); + store.stack.push(transferred); + } + } + + fn provide_value(&self, value: &Value, to_store: &mut Store) -> Value { + if let Some(from_heap_pos) = value.get_heap_pos() { + let from_heap_pos = from_heap_pos as usize; + let to_heap_pos = to_store.alloc_heap(); + let to_heap_pos_usize = to_heap_pos as usize; + to_store.heap_regions[to_heap_pos_usize].values.reserve(self.regions[from_heap_pos].len()); + + for value in &self.regions[from_heap_pos as usize] { + let transferred = self.provide_value(value, to_store); + to_store.heap_regions[to_heap_pos_usize].values.push(transferred); + } + + return match value { + Value::Message(_) => Value::Message(to_heap_pos), + Value::String(_) => Value::String(to_heap_pos), + Value::Array(_) => Value::Array(to_heap_pos), + Value::Union(tag, _) => Value::Union(*tag, to_heap_pos), + Value::Struct(_) => Value::Struct(to_heap_pos), + _ => unreachable!(), + }; + } else { + return value.clone(); + } + } +} + +impl Default for ValueGroup { + /// Returns an empty ValueGroup + fn default() -> Self { + Self { values: Vec::new(), regions: Vec::new() } + } +} + +pub(crate) fn apply_assignment_operator(store: &mut Store, lhs: ValueId, op: AssignmentOperator, rhs: Value) { use AssignmentOperator as AO; macro_rules! apply_int_op { @@ -165,7 +278,7 @@ pub(crate) fn apply_assignment_operator(store: &mut Store, lhs: ValueRef, op: As let lhs = store.read_mut_ref(lhs); let mut to_dealloc = None; - match AO { + match op { AO::Set => { match lhs { Value::Unassigned => { *lhs = rhs; }, @@ -290,25 +403,28 @@ pub(crate) fn apply_unary_operator(store: &mut Store, op: UnaryOperator, value: use UnaryOperator as UO; macro_rules! apply_int_expr_and_return { - ($value:ident, $apply:expr, $op:ident) => { + ($value:ident, $apply:tt, $op:ident) => { return match $value { - Value::UInt8(v) => Value::UInt8($apply), - Value::UInt16(v) => Value::UInt16($apply), - Value::UInt32(v) => Value::UInt32($apply), - Value::UInt64(v) => Value::UInt64($apply), - Value::SInt8(v) => Value::SInt8($apply), - Value::SInt16(v) => Value::SInt16($apply), - Value::SInt32(v) => Value::SInt32($apply), - Value::SInt64(v) => Value::SInt64($apply), + Value::UInt8(v) => Value::UInt8($apply *v), + Value::UInt16(v) => Value::UInt16($apply *v), + Value::UInt32(v) => Value::UInt32($apply *v), + Value::UInt64(v) => Value::UInt64($apply *v), + Value::SInt8(v) => Value::SInt8($apply *v), + Value::SInt16(v) => Value::SInt16($apply *v), + Value::SInt32(v) => Value::SInt32($apply *v), + Value::SInt64(v) => Value::SInt64($apply *v), _ => unreachable!("apply_unary_operator {:?} on value {:?}", $op, $value), }; } } match op { - UO::Positive => { apply_int_expr_and_return!(value, *v, op) }, - UO::Negative => { apply_int_expr_and_return!(value, *v, op) }, - UO::BitwiseNot => { apply_int_expr_and_return!(value, *v, op)}, + UO::Positive => { + debug_assert!(value.is_integer()); + return value.clone(); + }, + UO::Negative => { apply_int_expr_and_return!(value, -, op) }, + UO::BitwiseNot => { apply_int_expr_and_return!(value, !, op)}, UO::LogicalNot => { return Value::Bool(!value.as_bool()); }, UO::PreIncrement => { todo!("implement") }, UO::PreDecrement => { todo!("implement") }, diff --git a/src/protocol/mod.rs b/src/protocol/mod.rs index 4342e93024695cb32775328e32f2cb3d4989a399..1ed2c1ced4360b98636228500547e97b607f1d3c 100644 --- a/src/protocol/mod.rs +++ b/src/protocol/mod.rs @@ -20,7 +20,7 @@ pub struct ProtocolDescription { source: InputSource, root: RootId, } -#[derive(Debug, Clone)] +// #[derive(Debug, Clone)] pub(crate) struct ComponentState { prompt: Prompt, } @@ -102,14 +102,14 @@ impl ProtocolDescription { let mut args = Vec::new(); for (&x, y) in ports.iter().zip(self.component_polarities(identifier).unwrap()) { match y { - Polarity::Getter => args.push(Value::Input(InputValue(x))), - Polarity::Putter => args.push(Value::Output(OutputValue(x))), + Polarity::Getter => args.push(Value::Input(x)), + Polarity::Putter => args.push(Value::Output(x)), } } let h = &self.heap; let root = &h[self.root]; let def = root.get_definition_ident(h, identifier).unwrap(); - ComponentState { prompt: Prompt::new(h, def, &args) } + ComponentState { prompt: Prompt::new(h, def, ValueGroup::new_stack(args)) } } } impl ComponentState { @@ -133,9 +133,30 @@ impl ComponentState { EvalContinuation::SyncBlockEnd => unreachable!(), EvalContinuation::NewComponent(definition_id, args) => { // Look up definition (TODO for now, assume it is a definition) + let mut moved_ports = HashSet::new(); + for arg in args.values.iter() { + match arg { + Value::Output(port) => { + moved_ports.insert(*port); + } + Value::Input(port) => { + moved_ports.insert(*port); + } + _ => {} + } + } + for region in args.regions.iter() { + for arg in region { + match arg { + Value::Output(port) => { moved_ports.insert(*port); }, + Value::Input(port) => { moved_ports.insert(*port); }, + _ => {}, + } + } + } let h = &pd.heap; - let init_state = ComponentState { prompt: Prompt::new(h, definition_id, &args) }; - context.new_component(&args, init_state); + let init_state = ComponentState { prompt: Prompt::new(h, definition_id, args) }; + context.new_component(moved_ports, init_state); // Continue stepping continue; } @@ -170,19 +191,19 @@ impl ComponentState { // Not possible to create component in sync block EvalContinuation::NewComponent(_, _) => unreachable!(), EvalContinuation::BlockFires(port) => match port { - Value::Output(OutputValue(port)) => { + Value::Output(port) => { return SyncBlocker::CouldntCheckFiring(port); } - Value::Input(InputValue(port)) => { + Value::Input(port) => { return SyncBlocker::CouldntCheckFiring(port); } _ => unreachable!(), }, EvalContinuation::BlockGet(port) => match port { - Value::Output(OutputValue(port)) => { + Value::Output(port) => { return SyncBlocker::CouldntReadMsg(port); } - Value::Input(InputValue(port)) => { + Value::Input(port) => { return SyncBlocker::CouldntReadMsg(port); } _ => unreachable!(), @@ -190,23 +211,27 @@ impl ComponentState { EvalContinuation::Put(port, message) => { let value; match port { - Value::Output(OutputValue(port_value)) => { + Value::Output(port_value) => { value = port_value; } - Value::Input(InputValue(port_value)) => { + Value::Input(port_value) => { value = port_value; } _ => unreachable!(), } let payload; match message { - Value::Message(MessageValue(None)) => { - // Putting a null message is inconsistent + Value::Null => { return SyncBlocker::Inconsistent; - } - Value::Message(MessageValue(Some(buffer))) => { + }, + Value::Message(heap_pos) => { // Create a copy of the payload - payload = buffer; + let values = &self.prompt.store.heap_regions[heap_pos as usize].values; + let mut bytes = Vec::with_capacity(values.len()); + for value in values { + bytes.push(value.as_uint8()); + } + payload = Payload(Arc::new(bytes)); } _ => unreachable!(), } @@ -225,22 +250,10 @@ impl EvalContext<'_> { // EvalContext::Sync(_) => unreachable!(), // } // } - fn new_component(&mut self, args: &[Value], init_state: ComponentState) -> () { + fn new_component(&mut self, moved_ports: HashSet, init_state: ComponentState) -> () { match self { // EvalContext::None => unreachable!(), EvalContext::Nonsync(context) => { - let mut moved_ports = HashSet::new(); - for arg in args.iter() { - match arg { - Value::Output(OutputValue(port)) => { - moved_ports.insert(*port); - } - Value::Input(InputValue(port)) => { - moved_ports.insert(*port); - } - _ => {} - } - } context.new_component(moved_ports, init_state) } EvalContext::Sync(_) => unreachable!(), @@ -251,8 +264,8 @@ impl EvalContext<'_> { // EvalContext::None => unreachable!(), EvalContext::Nonsync(context) => { let [from, to] = context.new_port_pair(); - let from = Value::Output(OutputValue(from)); - let to = Value::Input(InputValue(to)); + let from = Value::Output(from); + let to = Value::Input(to); return [from, to]; } EvalContext::Sync(_) => unreachable!(), @@ -263,8 +276,8 @@ impl EvalContext<'_> { // EvalContext::None => unreachable!(), EvalContext::Nonsync(_) => unreachable!(), EvalContext::Sync(context) => match port { - Value::Output(OutputValue(port)) => context.is_firing(port).map(Value::from), - Value::Input(InputValue(port)) => context.is_firing(port).map(Value::from), + Value::Output(port) => context.is_firing(port).map(Value::Bool), + Value::Input(port) => context.is_firing(port).map(Value::Bool), _ => unreachable!(), }, } @@ -274,10 +287,11 @@ impl EvalContext<'_> { // EvalContext::None => unreachable!(), EvalContext::Nonsync(_) => unreachable!(), EvalContext::Sync(context) => match port { - Value::Output(OutputValue(port)) => { + Value::Output(port) => { + debug_assert!(false, "Getting from an output port? Am I mad?"); context.read_msg(port).map(Value::receive_message) } - Value::Input(InputValue(port)) => { + Value::Input(port) => { context.read_msg(port).map(Value::receive_message) } _ => unreachable!(), @@ -288,7 +302,7 @@ impl EvalContext<'_> { match self { EvalContext::Nonsync(_) => unreachable!("did_put in nonsync context"), EvalContext::Sync(context) => match port { - Value::Output(OutputValue(port)) => { + Value::Output(port) => { context.did_put_or_get(port) }, Value::Input(_) => unreachable!("did_put on input port"), diff --git a/src/protocol/parser/depth_visitor.rs b/src/protocol/parser/depth_visitor.rs index 49edf55dfe94ff8a2b2c843f8e930c5d6c9b5a80..870aeb48e4df9a32cb5c417e156053b5260d0a24 100644 --- a/src/protocol/parser/depth_visitor.rs +++ b/src/protocol/parser/depth_visitor.rs @@ -43,15 +43,8 @@ pub(crate) trait Visitor: Sized { } fn visit_variable_declaration(&mut self, h: &mut Heap, decl: VariableId) -> VisitorResult { - recursive_variable_declaration(self, h, decl) - } - fn visit_parameter_declaration(&mut self, _h: &mut Heap, _decl: ParameterId) -> VisitorResult { - Ok(()) - } - fn visit_local_declaration(&mut self, _h: &mut Heap, _decl: LocalId) -> VisitorResult { Ok(()) } - fn visit_statement(&mut self, h: &mut Heap, stmt: StatementId) -> VisitorResult { recursive_statement(self, h, stmt) } @@ -71,6 +64,9 @@ pub(crate) trait Visitor: Sized { fn visit_block_statement(&mut self, h: &mut Heap, stmt: BlockStatementId) -> VisitorResult { recursive_block_statement(self, h, stmt) } + fn visit_end_block_statement(&mut self, h: &mut Heap, stmt: EndBlockStatementId) -> VisitorResult { + Ok(()) + } fn visit_labeled_statement(&mut self, h: &mut Heap, stmt: LabeledStatementId) -> VisitorResult { recursive_labeled_statement(self, h, stmt) } @@ -189,23 +185,6 @@ pub(crate) trait Visitor: Sized { } } -// Bubble-up helpers -fn recursive_parameter_as_variable( - this: &mut T, - h: &mut Heap, - param: ParameterId, -) -> VisitorResult { - this.visit_variable_declaration(h, param.upcast()) -} - -fn recursive_local_as_variable( - this: &mut T, - h: &mut Heap, - local: LocalId, -) -> VisitorResult { - this.visit_variable_declaration(h, local.upcast()) -} - fn recursive_call_expression_as_expression( this: &mut T, h: &mut Heap, @@ -266,7 +245,7 @@ fn recursive_composite_definition( def: ComponentDefinitionId, ) -> VisitorResult { for ¶m in h[def].parameters.clone().iter() { - recursive_parameter_as_variable(this, h, param)?; + this.visit_variable_declaration(h, param)?; } this.visit_block_statement(h, h[def].body) } @@ -277,7 +256,7 @@ fn recursive_primitive_definition( def: ComponentDefinitionId, ) -> VisitorResult { for ¶m in h[def].parameters.clone().iter() { - recursive_parameter_as_variable(this, h, param)?; + this.visit_variable_declaration(h, param)?; } this.visit_block_statement(h, h[def].body) } @@ -288,25 +267,15 @@ fn recursive_function_definition( def: FunctionDefinitionId, ) -> VisitorResult { for ¶m in h[def].parameters.clone().iter() { - recursive_parameter_as_variable(this, h, param)?; + this.visit_variable_declaration(h, param)?; } this.visit_block_statement(h, h[def].body) } -fn recursive_variable_declaration( - this: &mut T, - h: &mut Heap, - decl: VariableId, -) -> VisitorResult { - match h[decl].clone() { - Variable::Parameter(decl) => this.visit_parameter_declaration(h, decl.this), - Variable::Local(decl) => this.visit_local_declaration(h, decl.this), - } -} - fn recursive_statement(this: &mut T, h: &mut Heap, stmt: StatementId) -> VisitorResult { match h[stmt].clone() { Statement::Block(stmt) => this.visit_block_statement(h, stmt.this), + Statement::EndBlock(stmt) => this.visit_end_block_statement(h, stmt.this), Statement::Local(stmt) => this.visit_local_statement(h, stmt.this()), Statement::Labeled(stmt) => this.visit_labeled_statement(h, stmt.this), Statement::If(stmt) => this.visit_if_statement(h, stmt.this), @@ -330,7 +299,7 @@ fn recursive_block_statement( block: BlockStatementId, ) -> VisitorResult { for &local in h[block].locals.clone().iter() { - recursive_local_as_variable(this, h, local)?; + this.visit_variable_declaration(h, local)?; } for &stmt in h[block].statements.clone().iter() { this.visit_statement(h, stmt)?; @@ -549,6 +518,18 @@ impl Visitor for LinkStatements { } recursive_statement(self, h, stmt) } + fn visit_block_statement(&mut self, h: &mut Heap, stmt: BlockStatementId) -> VisitorResult { + if let Some(prev) = self.prev.take() { + h[prev.0].link_next(stmt.upcast()); + } + let end_block = h[stmt].end_block; + recursive_block_statement(self, h, stmt)?; + if let Some(prev) = self.prev.take() { + h[prev.0].link_next(end_block.upcast()); + } + self.prev = Some(UniqueStatementId(end_block.upcast())); + Ok(()) + } fn visit_local_statement(&mut self, _h: &mut Heap, stmt: LocalStatementId) -> VisitorResult { self.prev = Some(UniqueStatementId(stmt.upcast())); Ok(()) diff --git a/src/protocol/parser/pass_definitions.rs b/src/protocol/parser/pass_definitions.rs index 46795e3056b332203d54831f5318578969422a35..4fb43dc88f693d922d1c4226ab3c4435a0282b2b 100644 --- a/src/protocol/parser/pass_definitions.rs +++ b/src/protocol/parser/pass_definitions.rs @@ -15,7 +15,7 @@ pub(crate) struct PassDefinitions { struct_fields: ScopedBuffer, enum_variants: ScopedBuffer, union_variants: ScopedBuffer, - parameters: ScopedBuffer, + variables: ScopedBuffer, expressions: ScopedBuffer, statements: ScopedBuffer, parser_types: ScopedBuffer, @@ -29,7 +29,7 @@ impl PassDefinitions { struct_fields: ScopedBuffer::new_reserved(128), enum_variants: ScopedBuffer::new_reserved(128), union_variants: ScopedBuffer::new_reserved(128), - parameters: ScopedBuffer::new_reserved(128), + variables: ScopedBuffer::new_reserved(128), expressions: ScopedBuffer::new_reserved(128), statements: ScopedBuffer::new_reserved(128), parser_types: ScopedBuffer::new_reserved(128), @@ -259,7 +259,7 @@ impl PassDefinitions { consume_polymorphic_vars_spilled(&module.source, iter, ctx)?; // Parse function's argument list - let mut parameter_section = self.parameters.start_section(); + let mut parameter_section = self.variables.start_section(); consume_parameter_list( &module.source, iter, ctx, &mut parameter_section, module_scope, definition_id )?; @@ -314,7 +314,7 @@ impl PassDefinitions { consume_polymorphic_vars_spilled(&module.source, iter, ctx)?; // Parse component's argument list - let mut parameter_section = self.parameters.start_section(); + let mut parameter_section = self.variables.start_section(); consume_parameter_list( &module.source, iter, ctx, &mut parameter_section, module_scope, definition_id )?; @@ -350,18 +350,28 @@ impl PassDefinitions { debug_assert_eq!(statements.len(), 1); let statements = statements.into_vec(); - Ok(ctx.heap.alloc_block_statement(|this| BlockStatement{ + let id = ctx.heap.alloc_block_statement(|this| BlockStatement{ this, is_implicit: true, span: InputSpan::from_positions(wrap_begin_pos, wrap_end_pos), // TODO: @Span statements, + end_block: EndBlockStatementId::new_invalid(), parent_scope: Scope::Definition(DefinitionId::new_invalid()), first_unique_id_in_scope: -1, next_unique_id_in_scope: -1, relative_pos_in_parent: 0, locals: Vec::new(), labels: Vec::new() - })) + }); + + let end_block = ctx.heap.alloc_end_block_statement(|this| EndBlockStatement{ + this, start_block: id, next: StatementId::new_invalid() + }); + + let block_stmt = &mut ctx.heap[id]; + block_stmt.end_block = end_block; + + Ok(id) } } @@ -389,7 +399,7 @@ impl PassDefinitions { section.push(id.upcast()); let if_stmt = &mut ctx.heap[id]; - if_stmt.end_if = Some(end_if); + if_stmt.end_if = end_if; } else if ident == KW_STMT_WHILE { let id = self.consume_while_statement(module, iter, ctx)?; section.push(id.upcast()); @@ -400,7 +410,7 @@ impl PassDefinitions { section.push(id.upcast()); let while_stmt = &mut ctx.heap[id]; - while_stmt.end_while = Some(end_while); + while_stmt.end_while = end_while; } else if ident == KW_STMT_BREAK { let id = self.consume_break_statement(module, iter, ctx)?; section.push(id.upcast()); @@ -416,7 +426,7 @@ impl PassDefinitions { }); let sync_stmt = &mut ctx.heap[id]; - sync_stmt.end_sync = Some(end_sync); + sync_stmt.end_sync = end_sync; } else if ident == KW_STMT_RETURN { let id = self.consume_return_statement(module, iter, ctx)?; section.push(id.upcast()); @@ -474,18 +484,28 @@ impl PassDefinitions { let mut block_span = consume_token(&module.source, iter, TokenKind::CloseCurly)?; block_span.begin = open_curly_pos; - Ok(ctx.heap.alloc_block_statement(|this| BlockStatement{ + let id = ctx.heap.alloc_block_statement(|this| BlockStatement{ this, is_implicit: false, span: block_span, statements, + end_block: EndBlockStatementId::new_invalid(), parent_scope: Scope::Definition(DefinitionId::new_invalid()), first_unique_id_in_scope: -1, next_unique_id_in_scope: -1, relative_pos_in_parent: 0, locals: Vec::new(), labels: Vec::new(), - })) + }); + + let end_block = ctx.heap.alloc_end_block_statement(|this| EndBlockStatement{ + this, start_block: id, next: StatementId::new_invalid() + }); + + let block_stmt = &mut ctx.heap[id]; + block_stmt.end_block = end_block; + + Ok(id) } fn consume_if_statement( @@ -511,7 +531,7 @@ impl PassDefinitions { test, true_body, false_body, - end_if: None, + end_if: EndIfStatementId::new_invalid(), })) } @@ -529,7 +549,7 @@ impl PassDefinitions { span: while_span, test, body, - end_while: None, + end_while: EndWhileStatementId::new_invalid(), in_sync: None, })) } @@ -582,7 +602,7 @@ impl PassDefinitions { this, span: synchronous_span, body, - end_sync: None, + end_sync: EndSynchronousStatementId::new_invalid(), parent_scope: None, })) } @@ -1919,7 +1939,7 @@ fn consume_polymorphic_vars_spilled(source: &InputSource, iter: &mut TokenIter, /// Consumes the parameter list to functions/components fn consume_parameter_list( source: &InputSource, iter: &mut TokenIter, ctx: &mut PassCtx, - target: &mut ScopedSection, scope: SymbolScope, definition_id: DefinitionId + target: &mut ScopedSection, scope: SymbolScope, definition_id: DefinitionId ) -> Result<(), ParseError> { consume_comma_separated( TokenKind::OpenParen, TokenKind::CloseParen, source, iter, ctx, diff --git a/src/protocol/parser/pass_validation_linking.rs b/src/protocol/parser/pass_validation_linking.rs index 4df38c1545ada05e0bc5e8c198792ed2f6dedc9a..0e5cdfbafe161912a1ae689afa86f1f040e34f92 100644 --- a/src/protocol/parser/pass_validation_linking.rs +++ b/src/protocol/parser/pass_validation_linking.rs @@ -12,7 +12,6 @@ use super::visitor::{ VisitorResult }; use crate::protocol::parser::ModuleCompilationPhase; -use crossbeam_utils::thread::scope; #[derive(PartialEq, Eq)] enum DefinitionType {