diff --git a/src/protocol/parser/pass_rewriting.rs b/src/protocol/parser/pass_rewriting.rs index 80554d91b426312cf0301354c1b037d4f10e5f09..2b8b2229277749989eba786a202138f38a24de83 100644 --- a/src/protocol/parser/pass_rewriting.rs +++ b/src/protocol/parser/pass_rewriting.rs @@ -4,19 +4,21 @@ use crate::protocol::*; use super::visitor::*; pub(crate) struct PassRewriting { - current_scope: BlockStatementId, + current_scope: ScopeId, statement_buffer: ScopedBuffer, call_expr_buffer: ScopedBuffer, expression_buffer: ScopedBuffer, + scope_buffer: ScopedBuffer, } impl PassRewriting { pub(crate) fn new() -> Self { Self{ - current_scope: BlockStatementId::new_invalid(), - statement_buffer: ScopedBuffer::with_capacity(16), - call_expr_buffer: ScopedBuffer::with_capacity(16), - expression_buffer: ScopedBuffer::with_capacity(16), + current_scope: ScopeId::new_invalid(), + statement_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL), + call_expr_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL), + expression_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL), + scope_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL), } } } @@ -27,12 +29,14 @@ impl Visitor for PassRewriting { fn visit_component_definition(&mut self, ctx: &mut Ctx, id: ComponentDefinitionId) -> VisitorResult { let def = &ctx.heap[id]; let body_id = def.body; + self.current_scope = def.scope; return self.visit_block_stmt(ctx, body_id); } fn visit_function_definition(&mut self, ctx: &mut Ctx, id: FunctionDefinitionId) -> VisitorResult { let def = &ctx.heap[id]; let body_id = def.body; + self.current_scope = def.scope; return self.visit_block_stmt(ctx, body_id); } @@ -42,7 +46,7 @@ impl Visitor for PassRewriting { let block_stmt = &ctx.heap[id]; let stmt_section = self.statement_buffer.start_section_initialized(&block_stmt.statements); - self.current_scope = id; + self.current_scope = block_stmt.scope; for stmt_idx in 0..stmt_section.len() { self.visit_stmt(ctx, stmt_section[stmt_idx])?; } @@ -59,12 +63,14 @@ impl Visitor for PassRewriting { fn visit_if_stmt(&mut self, ctx: &mut Ctx, id: IfStatementId) -> VisitorResult { let if_stmt = &ctx.heap[id]; - let true_body_id = if_stmt.true_case; - let false_body_id = if_stmt.false_case; - - self.visit_stmt(ctx, true_body_id.body)?; - if let Some(false_body_id) = false_body_id { - self.visit_stmt(ctx, false_body_id.body)?; + let true_case = if_stmt.true_case; + let false_case = if_stmt.false_case; + + self.current_scope = true_case.scope; + self.visit_stmt(ctx, true_case.body)?; + if let Some(false_case) = false_case { + self.current_scope = false_case.scope; + self.visit_stmt(ctx, false_case.body)?; } return Ok(()) @@ -73,12 +79,14 @@ impl Visitor for PassRewriting { fn visit_while_stmt(&mut self, ctx: &mut Ctx, id: WhileStatementId) -> VisitorResult { let while_stmt = &ctx.heap[id]; let body_id = while_stmt.body; + self.current_scope = while_stmt.scope; return self.visit_stmt(ctx, body_id); } fn visit_synchronous_stmt(&mut self, ctx: &mut Ctx, id: SynchronousStatementId) -> VisitorResult { let sync_stmt = &ctx.heap[id]; let body_id = sync_stmt.body; + self.current_scope = sync_stmt.scope; return self.visit_stmt(ctx, body_id); } @@ -109,9 +117,28 @@ impl Visitor for PassRewriting { return (if_stmt_id, end_if_stmt_id) } - // We're going to transform the select statement by a block statement - // containing builtin runtime-calls. And to do so we create temporary - // variables and move some other statements around. + // Precreate the block that will end up containing all of the + // transformed statements. Also precreate the scope associated with it + let (outer_block_id, outer_end_block_id, outer_scope_id) = + create_ast_block_stmt(ctx, Vec::new()); + + // The "select" and the "end select" statement will act like trampolines + // that jump to the replacement block. So set the child/parent + // relationship already. + // --- for the statements + let select_stmt = &mut ctx.heap[id]; + select_stmt.next = outer_block_id.upcast(); + let end_select_stmt_id = select_stmt.end_select; + let select_stmt_relative_pos = select_stmt.relative_pos_in_parent; + + let outer_end_block_stmt = &mut ctx.heap[outer_end_block_id]; + outer_end_block_stmt.next = end_select_stmt_id.upcast(); + + // --- for the scopes + link_existing_child_to_new_parent_scope(ctx, &mut self.scope_buffer, self.current_scope, outer_scope_id, select_stmt_relative_pos); + + // Create statements that will create temporary variables for all of the + // ports passed to the "get" calls in the select case guards. let select_stmt = &ctx.heap[id]; let total_num_cases = select_stmt.cases.len(); let mut total_num_ports = 0; @@ -141,7 +168,7 @@ impl Visitor for PassRewriting { let port_expr_id = expr_id_section[port_var_idx]; // Move the port expression such that it gets assigned to a temporary variable - let variable_id = create_ast_variable(ctx); + let variable_id = create_ast_variable(ctx, outer_scope_id); let variable_decl_stmt_id = create_ast_variable_declaration_stmt(ctx, variable_id, port_expr_id); // Replace the original port expression in the call with a reference @@ -205,7 +232,7 @@ impl Visitor for PassRewriting { // Create the variable that will hold the result of a completed select // block. Then create the runtime call that will produce this result - let select_variable_id = create_ast_variable(ctx); + let select_variable_id = create_ast_variable(ctx, outer_scope_id); locals.push(select_variable_id); { @@ -217,57 +244,40 @@ impl Visitor for PassRewriting { call_id_section.forget(); expr_id_section.forget(); - // Precreate the block statement that will be the replacement of the - // select statement. Do not set its members yet. - let replacement_stmt_id = ctx.heap.alloc_block_statement(|this| BlockStatement{ - this, - is_implicit: true, - span: InputSpan::new(), - statements: Vec::new(), - end_block: EndBlockStatementId::new_invalid(), - scope: ScopeId::new_invalid(), - next: StatementId::new_invalid(), - }); - let end_block_id = ctx.heap.alloc_end_block_statement(|this| EndBlockStatement{ - this, - start_block: replacement_stmt_id, - next: stmt_id_after_select_stmt, - }); - // Now we transform each of the select block case's guard and code into // a chained if-else statement. if total_num_cases > 0 { let (if_stmt_id, end_if_stmt_id) = transform_select_case_code(ctx, id, 0, select_variable_id); + let first_end_if_stmt = &mut ctx.heap[end_if_stmt_id]; + first_end_if_stmt.next = outer_end_block_id.upcast(); + let mut last_if_stmt_id = if_stmt_id; let mut last_end_if_stmt_id = end_if_stmt_id; transformed_stmts.push(last_if_stmt_id.upcast()); for case_index in 1..total_num_cases { let (if_stmt_id, end_if_stmt_id) = transform_select_case_code(ctx, id, case_index, select_variable_id); - let last_if_stmt = &mut ctx.heap[last_if_stmt_id]; - // last_if_stmt.false_case = Some(if_stmt_id.upcast()); - - // TODO: - // 1. Change scoping such that it is a separate datastructure with separate IDs - // 2. Change statements that contain "implicit scopes" to explicitly point to the appropriate scopes - // 3. Continue here setting the true-body and false-body. - // 4. Figure out how we're going to link everything up again + let false_case_scope_id = ctx.heap.alloc_scope(|this| Scope::new(this, ScopeAssociation::If(last_if_stmt_id, false))); + set_ast_if_statement_false_body(ctx, last_if_stmt_id, last_end_if_stmt_id, IfStatementCase{ body: if_stmt_id.upcast(), scope: false_case_scope_id }); + + let end_if_stmt = &mut ctx.heap[end_if_stmt_id]; + end_if_stmt.next = last_end_if_stmt_id.upcast(); + + last_if_stmt_id = if_stmt_id; + last_end_if_stmt_id = end_if_stmt_id; } } - // let block = ctx.heap.alloc_block_statement(|this| BlockStatement{ - // this, - // is_implicit: true, - // span: stmt.span, - // statements: vec![], - // end_block: EndBlockStatementId(), - // scope_node: ScopeNode {}, - // first_unique_id_in_scope: 0, - // next_unique_id_in_scope: 0, - // locals, - // labels: vec![], - // next: () - // }); + // Final steps: set the statements of the replacement block statement, + // and link all of those statements together + let mut last_stmt_id = transformed_stmts[0]; + for stmt_id in transformed_stmts.iter().skip(1).copied() { + set_ast_statement_next(ctx, last_stmt_id, stmt_id); + last_stmt_id = stmt_id; + } + + let outer_block_stmt = &mut ctx.heap[outer_block_id]; + outer_block_stmt.statements = transformed_stmts; return Ok(()) } @@ -301,60 +311,14 @@ impl PassRewriting { return (call_expr_id, call_stmt_id); } - - fn create_runtime_select_wait_variable_and_statement(&self, ctx: &mut Ctx) -> (VariableId, MemoryStatementId) { - let variable_id = create_ast_variable(ctx); - let variable_expr_id = create_ast_variable_expr(ctx, variable_id); - let runtime_call_expr_id = ctx.heap.alloc_call_expression(|this| CallExpression{ - this, - func_span: InputSpan::new(), - full_span: InputSpan::new(), - parser_type: ParserType{ - elements: Vec::new(), - full_span: InputSpan::new(), - }, - method: Method::SelectWait, - arguments: Vec::new(), - definition: DefinitionId::new_invalid(), - parent: ExpressionParent::None, - unique_id_in_definition: -1 - }); - let initial_expr_id = ctx.heap.alloc_assignment_expression(|this| AssignmentExpression{ - this, - operator_span: InputSpan::new(), - full_span: InputSpan::new(), - left: variable_expr_id.upcast(), - operation: AssignmentOperator::Set, - right: runtime_call_expr_id.upcast(), - parent: ExpressionParent::None, - unique_id_in_definition: -1 - }); - - let variable_statement_id = ctx.heap.alloc_memory_statement(|this| MemoryStatement{ - this, - span: InputSpan::new(), - variable: variable_id, - initial_expr: initial_expr_id, - next: StatementId::new_invalid() - }); - - let variable_expr = &mut ctx.heap[variable_expr_id]; - variable_expr.parent = ExpressionParent::Expression(initial_expr_id.upcast(), 0); - let runtime_call_expr = &mut ctx.heap[runtime_call_expr_id]; - runtime_call_expr.parent = ExpressionParent::Expression(initial_expr_id.upcast(), 1); - let initial_expr = &mut ctx.heap[initial_expr_id]; - initial_expr.parent = ExpressionParent::Memory(variable_statement_id); - - return (variable_id, variable_statement_id); - } } // ----------------------------------------------------------------------------- // Utilities to create compiler-generated AST nodes // ----------------------------------------------------------------------------- -fn create_ast_variable(ctx: &mut Ctx) -> VariableId { - return ctx.heap.alloc_variable(|this| Variable{ +fn create_ast_variable(ctx: &mut Ctx, scope_id: ScopeId) -> VariableId { + let variable_id = ctx.heap.alloc_variable(|this| Variable{ this, kind: VariableKind::Local, parser_type: ParserType{ @@ -365,6 +329,10 @@ fn create_ast_variable(ctx: &mut Ctx) -> VariableId { relative_pos_in_parent: -1, unique_id_in_scope: -1, }); + let scope = &mut ctx.heap[scope_id]; + scope.variables.push(variable_id); + + return variable_id; } fn create_ast_variable_expr(ctx: &mut Ctx, variable_id: VariableId) -> VariableExpressionId { @@ -487,6 +455,29 @@ fn create_ast_variable_declaration_stmt(ctx: &mut Ctx, variable_id: VariableId, return memory_stmt_id; } +fn create_ast_block_stmt(ctx: &mut Ctx, statements: Vec) -> (BlockStatementId, EndBlockStatementId, ScopeId) { + let block_stmt_id = ctx.heap.alloc_block_statement(|this| BlockStatement{ + this, + span: InputSpan::new(), + statements, + end_block: EndBlockStatementId::new_invalid(), + scope: ScopeId::new_invalid(), + next: StatementId::new_invalid(), + }); + let end_block_stmt_id = ctx.heap.alloc_end_block_statement(|this| EndBlockStatement{ + this, + start_block: block_stmt_id, + next: StatementId::new_invalid(), + }); + let scope_id = ctx.heap.alloc_scope(|this| Scope::new(this, ScopeAssociation::Block(block_stmt_id))); + + let block_stmt = &mut ctx.heap[block_stmt_id]; + block_stmt.end_block = end_block_stmt_id; + block_stmt.scope = scope_id; + + return (block_stmt_id, end_block_stmt_id, scope_id); +} + fn create_ast_if_stmt(ctx: &mut Ctx, condition_expression_id: ExpressionId, true_case: IfStatementCase, false_case: Option) -> (IfStatementId, EndIfStatementId) { // Create if statement and the end-if statement let if_stmt_id = ctx.heap.alloc_if_statement(|this| IfStatement{ @@ -511,21 +502,20 @@ fn create_ast_if_stmt(ctx: &mut Ctx, condition_expression_id: ExpressionId, true let condition_expr = &mut ctx.heap[condition_expression_id]; *condition_expr.parent_mut() = ExpressionParent::If(if_stmt_id); + + return (if_stmt_id, end_if_stmt_id); } -fn set_ast_if_statement_false_body(ctx: &mut Ctx, if_statement_id: IfStatementId, end_if_statement_id: EndIfStatementId, false_body_id: StatementId) { +/// Sets the false body for a given +fn set_ast_if_statement_false_body(ctx: &mut Ctx, if_statement_id: IfStatementId, end_if_statement_id: EndIfStatementId, false_case: IfStatementCase) { // Point if-statement to "false body" - todo!("set scopes"); let if_stmt = &mut ctx.heap[if_statement_id]; debug_assert!(if_stmt.false_case.is_none()); // simplifies logic, not necessary - if_stmt.false_case = Some(IfStatementCase{ - body: false_body_id, - scope: ScopeId::new_invalid(), - }); + if_stmt.false_case = Some(false_case); // Point end of false body to the end of the if statement - set_ast_statement_next(ctx, false_body_id, end_if_statement_id.upcast()); + set_ast_statement_next(ctx, false_case.body, end_if_statement_id.upcast()); } /// Sets the specified AST statement's control flow such that it will be @@ -583,4 +573,54 @@ fn set_ast_statement_next(ctx: &mut Ctx, source_stmt_id: StatementId, target_stm Statement::New(stmt) => stmt.next = target_stmt_id, Statement::Expression(stmt) => stmt.next = target_stmt_id, } -} \ No newline at end of file +} + +/// Links a new scope to an existing scope as its child. +fn link_new_child_to_existing_parent_scope(ctx: &mut Ctx, scope_buffer: &mut ScopedBuffer, parent_scope_id: ScopeId, child_scope_id: ScopeId, relative_pos_hint: i32) { + let child_scope = &mut ctx.heap[child_scope_id]; + debug_assert!(child_scope.parent.is_none()); + + child_scope.parent = Some(parent_scope_id); + child_scope.relative_pos_in_parent = relative_pos_hint; + + add_child_scope_to_parent(ctx, scope_buffer, parent_scope_id, child_scope_id, relative_pos_hint); +} + +/// Relinks an existing scope to a new scope as its child. Will also break the +/// link of the child scope's old parent. +fn link_existing_child_to_new_parent_scope(ctx: &mut Ctx, scope_buffer: &mut ScopedBuffer, new_parent_scope_id: ScopeId, child_scope_id: ScopeId, new_relative_pos_in_parent: i32) { + let child_scope = &mut ctx.heap[child_scope_id]; + let old_parent_scope_id = child_scope.parent.unwrap(); + child_scope.parent = Some(new_parent_scope_id); + child_scope.relative_pos_in_parent = new_relative_pos_in_parent; + + // Remove from old parent + let old_parent = &mut ctx.heap[old_parent_scope_id]; + let scope_index = old_parent.nested.iter() + .position(|v| *v == child_scope_id) + .unwrap(); + old_parent.nested.remove(scope_index); + + // Add to new parent + add_child_scope_to_parent(ctx, scope_buffer, new_parent_scope_id, child_scope_id, new_relative_pos_in_parent); +} + +/// Will add a child scope to a parent scope using the relative position hint. +fn add_child_scope_to_parent(ctx: &mut Ctx, scope_buffer: &mut ScopedBuffer, parent_scope_id: ScopeId, child_scope_id: ScopeId, relative_pos_hint: i32) { + let child_scope = &ctx.heap[child_scope_id]; + + let existing_scope_ids = scope_buffer.start_section_initialized(&child_scope.nested); + let mut insert_pos = existing_scope_ids.len(); + for index in 0..existing_scope_ids.len() { + let existing_scope_id = existing_scope_ids[index]; + let existing_scope = &ctx.heap[existing_scope_id]; + if relative_pos_hint <= existing_scope.relative_pos_in_parent { + insert_pos = index; + break; + } + } + existing_scope_ids.forget(); + + let parent_scope = &mut ctx.heap[parent_scope_id]; + parent_scope.nested.insert(insert_pos, child_scope_id); +}