/*
 * pass_validation_linking.rs
 *
 * The pass that will validate properties of the AST statements (one is not
 * allowed to nest synchronous statements, instantiating components occurs in
 * the right places, etc.) and expressions (assignments may not occur in
 * arbitrary expressions).
 *
 * Furthermore, this pass will also perform "linking", in the sense of: some AST
 * nodes have something to do with one another, so we link them up in this pass
 * (e.g. setting the parents of expressions, linking the control flow statements
 * like `continue` and `break` up to the respective loop statement, etc.).
 *
 * There are several "confusing" parts about this pass:
 *
 * Setting expression parents: this is the simplest one. The pass struct acts
 * like a little state machine. When visiting an expression it will set the
 * "parent expression" field of the pass to itself, then visit its child. The
 * child will look at this "parent expression" field to determine its parent.
 *
 * Setting the `next` statement: the AST is a tree, but during execution we walk
 * a linear path through all statements. So where appropriate a statement may
 * set the "previous statement" field of the pass to itself. When visiting the
 * subsequent statement it will check this "previous statement", and if set, it
 * will link this previous statement up to itself. Not every statement has a
 * previous statement. Hence there are two patterns that occur: assigning the
 * `next` value, then clearing the "previous statement" field. And assigning the
 * `next` value, and then putting the current statement's ID in the "previous
 * statement" field. Because it is so common, this file contain two macros that
 * perform that operation.
 *
 * To make storing types for polymorphic procedures simpler and more efficient,
 * we assign to each expression in the procedure a unique ID. This is what the
 * "next expression index" field achieves. Each expression simply takes the
 * current value, and then increments this counter.
 */

use crate::collections::{ScopedBuffer};
use crate::protocol::ast::*;
use crate::protocol::input_source::*;
use crate::protocol::parser::symbol_table::*;
use crate::protocol::parser::type_table::*;

use super::visitor::{
    BUFFER_INIT_CAP_SMALL,
    BUFFER_INIT_CAP_LARGE,
    Ctx,
    Visitor,
    VisitorResult
};
use crate::protocol::parser::ModuleCompilationPhase;

struct ControlFlowStatement {
    in_sync: SynchronousStatementId,
    in_while: WhileStatementId,
    in_scope: ScopeId,
    statement: StatementId, // of 'break', 'continue' or 'goto'
}

/// This particular visitor will go through the entire AST in a recursive manner
/// and check if all statements and expressions are legal (e.g. no "return"
/// statements in component definitions), and will link certain AST nodes to
/// their appropriate targets (e.g. goto statements, or function calls).
///
/// This visitor will not perform control-flow analysis (e.g. making sure that
/// each function actually returns) and will also not perform type checking. So
/// the linking of function calls and component instantiations will be checked
/// and linked to the appropriate definitions, but the return types and/or
/// arguments will not be checked for validity.
///
/// The main idea is, because we're visiting nodes in a tree, to do as much as
/// we can while we have the memory in cache.
pub(crate) struct PassValidationLinking {
    // Traversal state, all valid IDs if inside a certain AST element. Otherwise
    // `id.is_invalid()` returns true.
    in_sync: SynchronousStatementId,
    in_while: WhileStatementId, // to resolve labeled continue/break
    in_select_guard: SelectStatementId, // for detection/rejection of builtin calls
    in_select_arm: u32,
    in_test_expr: StatementId, // wrapping if/while stmt id
    in_binding_expr: BindingExpressionId, // to resolve variable expressions
    in_binding_expr_lhs: bool,
    // Traversal state, current scope (which can be used to find the parent
    // scope) and the definition variant we are considering.
    cur_scope: ScopeId,
    proc_id: ProcedureDefinitionId,
    proc_kind: ProcedureKind,
    // "Trailing" traversal state, set be child/prev stmt/expr used by next one
    prev_stmt: StatementId,
    expr_parent: ExpressionParent,
    // Set by parent to indicate that child expression must be assignable. The
    // child will throw an error if it is not assignable. The stored span is
    // used for the error's position
    must_be_assignable: Option<InputSpan>,
    // Keeping track of relative positions and unique IDs.
    relative_pos_in_parent: i32, // of statements: to determine when variables are visible
    // Control flow statements that require label resolving
    control_flow_stmts: Vec<ControlFlowStatement>,
    // Various temporary buffers for traversal. Essentially working around
    // Rust's borrowing rules since it cannot understand we're modifying AST
    // members but not the AST container.
    variable_buffer: ScopedBuffer<VariableId>,
    definition_buffer: ScopedBuffer<DefinitionId>,
    statement_buffer: ScopedBuffer<StatementId>,
    expression_buffer: ScopedBuffer<ExpressionId>,
    scope_buffer: ScopedBuffer<ScopeId>,
}

impl PassValidationLinking {
    pub(crate) fn new() -> Self {
        Self{
            in_sync: SynchronousStatementId::new_invalid(),
            in_while: WhileStatementId::new_invalid(),
            in_select_guard: SelectStatementId::new_invalid(),
            in_select_arm: 0,
            in_test_expr: StatementId::new_invalid(),
            in_binding_expr: BindingExpressionId::new_invalid(),
            in_binding_expr_lhs: false,
            cur_scope: ScopeId::new_invalid(),
            prev_stmt: StatementId::new_invalid(),
            expr_parent: ExpressionParent::None,
            proc_id: ProcedureDefinitionId::new_invalid(),
            proc_kind: ProcedureKind::Function,
            must_be_assignable: None,
            relative_pos_in_parent: 0,
            control_flow_stmts: Vec::with_capacity(BUFFER_INIT_CAP_SMALL),
            variable_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL),
            definition_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL),
            statement_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_LARGE),
            expression_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_LARGE),
            scope_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL),
        }
    }

    fn reset_state(&mut self) {
        self.in_sync = SynchronousStatementId::new_invalid();
        self.in_while = WhileStatementId::new_invalid();
        self.in_select_guard = SelectStatementId::new_invalid();
        self.in_test_expr = StatementId::new_invalid();
        self.in_binding_expr = BindingExpressionId::new_invalid();
        self.in_binding_expr_lhs = false;
        self.cur_scope = ScopeId::new_invalid();
        self.proc_id = ProcedureDefinitionId::new_invalid();
        self.proc_kind = ProcedureKind::Function;
        self.prev_stmt = StatementId::new_invalid();
        self.expr_parent = ExpressionParent::None;
        self.must_be_assignable = None;
        self.relative_pos_in_parent = 0;
        self.control_flow_stmts.clear();
    }
}

macro_rules! assign_then_erase_next_stmt {
    ($self:ident, $ctx:ident, $stmt_id:expr) => {
        if !$self.prev_stmt.is_invalid() {
            $ctx.heap[$self.prev_stmt].link_next($stmt_id);
            $self.prev_stmt = StatementId::new_invalid();
        }
    }
}

macro_rules! assign_and_replace_next_stmt {
    ($self:ident, $ctx:ident, $stmt_id:expr) => {
        if !$self.prev_stmt.is_invalid() {
            $ctx.heap[$self.prev_stmt].link_next($stmt_id);
        }
        $self.prev_stmt = $stmt_id;
    }
}

impl Visitor for PassValidationLinking {
    fn visit_module(&mut self, ctx: &mut Ctx) -> VisitorResult {
        debug_assert_eq!(ctx.module().phase, ModuleCompilationPhase::TypesAddedToTable);

        let root = &ctx.heap[ctx.module().root_id];
        let section = self.definition_buffer.start_section_initialized(&root.definitions);
        for definition_id in section.iter_copied() {
            self.visit_definition(ctx, definition_id)?;
        }
        section.forget();

        ctx.module_mut().phase = ModuleCompilationPhase::ValidatedAndLinked;
        Ok(())
    }
    //--------------------------------------------------------------------------
    // Definition visitors
    //--------------------------------------------------------------------------

    fn visit_procedure_definition(&mut self, ctx: &mut Ctx, id: ProcedureDefinitionId) -> VisitorResult {
        self.reset_state();

        let definition = &ctx.heap[id];
        self.proc_id = id;
        self.proc_kind = definition.kind;
        self.expr_parent = ExpressionParent::None;

        // Visit parameters
        let scope_id = definition.scope;
        let old_scope = self.push_scope(ctx, true, scope_id);

        let definition = &ctx.heap[id];
        let body_id = definition.body;
        let definition_is_builtin = definition.source.is_builtin();
        let section = self.variable_buffer.start_section_initialized(&definition.parameters);
        for variable_idx in 0..section.len() {
            let variable_id = section[variable_idx];
            self.checked_at_single_scope_add_local(ctx, self.cur_scope, -1, variable_id)?;
        }
        section.forget();

        // Visit statements in function body, if present at all
        if !definition_is_builtin {
            self.visit_block_stmt(ctx, body_id)?;
        }

        self.pop_scope(old_scope);

        self.resolve_pending_control_flow_targets(ctx)?;

        Ok(())
    }

    //--------------------------------------------------------------------------
    // Statement visitors
    //--------------------------------------------------------------------------

    fn visit_block_stmt(&mut self, ctx: &mut Ctx, id: BlockStatementId) -> VisitorResult {
        // Get end of block
        let block_stmt = &ctx.heap[id];
        let end_block_id = block_stmt.end_block;
        let scope_id = block_stmt.scope;

        // Traverse statements in block
        let statement_section = self.statement_buffer.start_section_initialized(&block_stmt.statements);
        let old_scope = self.push_scope(ctx, false, scope_id);
        assign_and_replace_next_stmt!(self, ctx, id.upcast());

        for stmt_idx in 0..statement_section.len() {
            self.relative_pos_in_parent = stmt_idx as i32;
            self.visit_stmt(ctx, statement_section[stmt_idx])?;
        }

        statement_section.forget();
        assign_and_replace_next_stmt!(self, ctx, end_block_id.upcast());

        self.pop_scope(old_scope);
        Ok(())
    }

    fn visit_local_memory_stmt(&mut self, ctx: &mut Ctx, id: MemoryStatementId) -> VisitorResult {
        let stmt = &ctx.heap[id];
        let expr_id = stmt.initial_expr;
        let variable_id = stmt.variable;

        self.checked_add_local(ctx, self.cur_scope, self.relative_pos_in_parent, variable_id)?;

        assign_and_replace_next_stmt!(self, ctx, id.upcast().upcast());
        debug_assert_eq!(self.expr_parent, ExpressionParent::None);
        self.expr_parent = ExpressionParent::Memory(id);
        self.visit_assignment_expr(ctx, expr_id)?;
        self.expr_parent = ExpressionParent::None;

        Ok(())
    }

    fn visit_local_channel_stmt(&mut self, ctx: &mut Ctx, id: ChannelStatementId) -> VisitorResult {
        let stmt = &ctx.heap[id];
        let from_id = stmt.from;
        let to_id = stmt.to;

        self.checked_add_local(ctx, self.cur_scope, self.relative_pos_in_parent, from_id)?;
        self.checked_add_local(ctx, self.cur_scope, self.relative_pos_in_parent, to_id)?;

        assign_and_replace_next_stmt!(self, ctx, id.upcast().upcast());
        Ok(())
    }

    fn visit_labeled_stmt(&mut self, ctx: &mut Ctx, id: LabeledStatementId) -> VisitorResult {
        let stmt = &ctx.heap[id];
        let body_id = stmt.body;

        self.checked_add_label(ctx, self.relative_pos_in_parent, self.in_sync, id)?;

        self.visit_stmt(ctx, body_id)?;
        Ok(())
    }

    fn visit_if_stmt(&mut self, ctx: &mut Ctx, id: IfStatementId) -> VisitorResult {
        let if_stmt = &ctx.heap[id];
        let end_if_id = if_stmt.end_if;
        let test_expr_id = if_stmt.test;
        let true_case = if_stmt.true_case;
        let false_case = if_stmt.false_case;

        // Visit test expression
        debug_assert_eq!(self.expr_parent, ExpressionParent::None);
        debug_assert!(self.in_test_expr.is_invalid());

        self.in_test_expr = id.upcast();
        self.expr_parent = ExpressionParent::If(id);
        self.visit_expr(ctx, test_expr_id)?;
        self.in_test_expr = StatementId::new_invalid();

        self.expr_parent = ExpressionParent::None;

        // Visit true and false branch. Executor chooses next statement based on
        // test expression, not on if-statement itself. Hence the if statement
        // does not have a static subsequent statement.
        assign_then_erase_next_stmt!(self, ctx, id.upcast());
        let old_scope = self.push_scope(ctx, false, true_case.scope);
        self.visit_stmt(ctx, true_case.body)?;
        self.pop_scope(old_scope);
        assign_then_erase_next_stmt!(self, ctx, end_if_id.upcast());

        if let Some(false_case) = false_case {
            let old_scope = self.push_scope(ctx, false, false_case.scope);
            self.visit_stmt(ctx, false_case.body)?;
            self.pop_scope(old_scope);
            assign_then_erase_next_stmt!(self, ctx, end_if_id.upcast());
        }

        self.prev_stmt = end_if_id.upcast();
        Ok(())
    }

    fn visit_while_stmt(&mut self, ctx: &mut Ctx, id: WhileStatementId) -> VisitorResult {
        let stmt = &ctx.heap[id];
        let end_while_id = stmt.end_while;
        let test_expr_id = stmt.test;
        let body_stmt_id = stmt.body;
        let scope_id = stmt.scope;

        let old_while = self.in_while;
        self.in_while = id;

        // Visit test expression
        debug_assert_eq!(self.expr_parent, ExpressionParent::None);
        debug_assert!(self.in_test_expr.is_invalid());
        self.in_test_expr = id.upcast();
        self.expr_parent = ExpressionParent::While(id);
        self.visit_expr(ctx, test_expr_id)?;
        self.in_test_expr = StatementId::new_invalid();

        // Link up to body statement
        assign_then_erase_next_stmt!(self, ctx, id.upcast());

        self.expr_parent = ExpressionParent::None;
        let old_scope = self.push_scope(ctx, false, scope_id);
        self.visit_stmt(ctx, body_stmt_id)?;
        self.pop_scope(old_scope);
        self.in_while = old_while;

        // Link final entry in while's block statement back to the while. The
        // executor will go to the end-while statement if the test expression
        // is false, so put that in as the new previous stmt
        assign_then_erase_next_stmt!(self, ctx, id.upcast());
        self.prev_stmt = end_while_id.upcast();

        Ok(())
    }

    fn visit_break_stmt(&mut self, ctx: &mut Ctx, id: BreakStatementId) -> VisitorResult {
        self.control_flow_stmts.push(ControlFlowStatement{
            in_sync: self.in_sync,
            in_while: self.in_while,
            in_scope: self.cur_scope,
            statement: id.upcast()
        });
        assign_then_erase_next_stmt!(self, ctx, id.upcast());

        Ok(())
    }

    fn visit_continue_stmt(&mut self, ctx: &mut Ctx, id: ContinueStatementId) -> VisitorResult {
        self.control_flow_stmts.push(ControlFlowStatement{
            in_sync: self.in_sync,
            in_while: self.in_while,
            in_scope: self.cur_scope,
            statement: id.upcast()
        });
        assign_then_erase_next_stmt!(self, ctx, id.upcast());

        Ok(())
    }

    fn visit_synchronous_stmt(&mut self, ctx: &mut Ctx, id: SynchronousStatementId) -> VisitorResult {
        // Check for validity of synchronous statement
        let sync_stmt = &ctx.heap[id];
        let end_sync_id = sync_stmt.end_sync;
        let cur_sync_span = sync_stmt.span;
        let scope_id = sync_stmt.scope;

        if !self.in_sync.is_invalid() {
            // Nested synchronous statement
            let old_sync_span = ctx.heap[self.in_sync].span;
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, cur_sync_span, "Illegal nested synchronous statement"
            ).with_info_str_at_span(
                &ctx.module().source, old_sync_span, "It is nested in this synchronous statement"
            ));
        }

        if self.proc_kind != ProcedureKind::Primitive {
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, cur_sync_span,
                "synchronous statements may only be used in primitive components"
            ));
        }

        // Synchronous statement implicitly moves to its block
        assign_then_erase_next_stmt!(self, ctx, id.upcast());

        // Visit block statement. Note that we explicitly push the scope here
        // (and the `visit_block_stmt` will also push, but without effect) to
        // ensure the scope contains the sync ID.
        let sync_body = ctx.heap[id].body;
        debug_assert!(self.in_sync.is_invalid());
        self.in_sync = id;
        let old_scope = self.push_scope(ctx, false, scope_id);
        self.visit_stmt(ctx, sync_body)?;
        self.pop_scope(old_scope);
        assign_and_replace_next_stmt!(self, ctx, end_sync_id.upcast());

        self.in_sync = SynchronousStatementId::new_invalid();

        Ok(())
    }

    fn visit_fork_stmt(&mut self, ctx: &mut Ctx, id: ForkStatementId) -> VisitorResult {
        let fork_stmt = &ctx.heap[id];
        let end_fork_id = fork_stmt.end_fork;
        let left_body_id = fork_stmt.left_body;
        let right_body_id = fork_stmt.right_body;

        // Fork statements may only occur inside sync blocks
        if self.in_sync.is_invalid() {
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, fork_stmt.span,
                "Forking may only occur inside sync blocks"
            ));
        }

        // Visit the respective bodies. Like the if statement, a fork statement
        // does not have a single static subsequent statement. It forks and then
        // each fork has a different next statement.
        assign_then_erase_next_stmt!(self, ctx, id.upcast());
        self.visit_stmt(ctx, left_body_id)?;
        assign_then_erase_next_stmt!(self, ctx, end_fork_id.upcast());

        if let Some(right_body_id) = right_body_id {
            self.visit_stmt(ctx, right_body_id)?;
            assign_then_erase_next_stmt!(self, ctx, end_fork_id.upcast());
        }

        self.prev_stmt = end_fork_id.upcast();
        Ok(())
    }

    fn visit_select_stmt(&mut self, ctx: &mut Ctx, id: SelectStatementId) -> VisitorResult {
        let select_stmt = &mut ctx.heap[id];
        select_stmt.relative_pos_in_parent = self.relative_pos_in_parent;
        self.relative_pos_in_parent += 1;

        let select_stmt = &ctx.heap[id];
        let end_select_id = select_stmt.end_select;

        // Select statements may only occur inside sync blocks
        if self.in_sync.is_invalid() {
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, select_stmt.span,
                "select statements may only occur inside sync blocks"
            ));
        }

        if self.proc_kind != ProcedureKind::Primitive {
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, select_stmt.span,
                "select statements may only be used in primitive components"
            ));
        }

        // Visit the various arms in the select block
        let mut case_stmt_ids = self.statement_buffer.start_section();
        let mut case_scope_ids = self.scope_buffer.start_section();
        let num_cases = select_stmt.cases.len();
        for case in &select_stmt.cases {
            // We add them in pairs, so the subsequent for-loop retrieves in pairs
            case_stmt_ids.push(case.guard);
            case_stmt_ids.push(case.body);
            case_scope_ids.push(case.scope);
        }

        assign_then_erase_next_stmt!(self, ctx, id.upcast());

        for index in 0..num_cases {
            let base_index = 2 * index;
            let guard_id     = case_stmt_ids[base_index];
            let case_body_id = case_stmt_ids[base_index + 1];
            let case_scope_id = case_scope_ids[index];

            // The guard statement ends up belonging to the block statement
            // following the arm. The reason we parse it separately is to
            // extract all of the "get" calls.
            let old_scope = self.push_scope(ctx, false, case_scope_id);

            // Visit the guard of this arm
            debug_assert!(self.in_select_guard.is_invalid());
            self.in_select_guard = id;
            self.in_select_arm = index as u32;
            self.visit_stmt(ctx, guard_id)?;
            self.in_select_guard = SelectStatementId::new_invalid();

            // Visit the code associated with the guard
            self.relative_pos_in_parent += 1;
            self.visit_stmt(ctx, case_body_id)?;
            self.pop_scope(old_scope);

            // Link up last statement in block to EndSelect
            assign_then_erase_next_stmt!(self, ctx, end_select_id.upcast());
        }

        self.in_select_guard = SelectStatementId::new_invalid();
        self.prev_stmt = end_select_id.upcast();
        Ok(())
    }

    fn visit_return_stmt(&mut self, ctx: &mut Ctx, id: ReturnStatementId) -> VisitorResult {
        // Check if "return" occurs within a function
        let stmt = &ctx.heap[id];
        if self.proc_kind != ProcedureKind::Function {
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, stmt.span,
                "return statements may only appear in function bodies"
            ));
        }

        // If here then we are within a function
        assign_then_erase_next_stmt!(self, ctx, id.upcast());
        debug_assert_eq!(self.expr_parent, ExpressionParent::None);
        debug_assert_eq!(ctx.heap[id].expressions.len(), 1);
        self.expr_parent = ExpressionParent::Return(id);
        self.visit_expr(ctx, ctx.heap[id].expressions[0])?;
        self.expr_parent = ExpressionParent::None;

        Ok(())
    }

    fn visit_goto_stmt(&mut self, ctx: &mut Ctx, id: GotoStatementId) -> VisitorResult {
        self.control_flow_stmts.push(ControlFlowStatement{
            in_sync: self.in_sync,
            in_while: self.in_while,
            in_scope: self.cur_scope,
            statement: id.upcast(),
        });
        assign_then_erase_next_stmt!(self, ctx, id.upcast());

        Ok(())
    }

    fn visit_new_stmt(&mut self, ctx: &mut Ctx, id: NewStatementId) -> VisitorResult {
        // Make sure the new statement occurs inside a composite component
        if self.proc_kind != ProcedureKind::Composite {
            let new_stmt = &ctx.heap[id];
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, new_stmt.span,
                "instantiating components may only be done in composite components"
            ));
        }

        // Recurse into call expression (which will check the expression parent
        // to ensure that the "new" statment instantiates a component)
        let call_expr_id = ctx.heap[id].expression;

        assign_and_replace_next_stmt!(self, ctx, id.upcast());
        debug_assert_eq!(self.expr_parent, ExpressionParent::None);
        self.expr_parent = ExpressionParent::New(id);
        self.visit_call_expr(ctx, call_expr_id)?;
        self.expr_parent = ExpressionParent::None;

        Ok(())
    }

    fn visit_expr_stmt(&mut self, ctx: &mut Ctx, id: ExpressionStatementId) -> VisitorResult {
        let expr_id = ctx.heap[id].expression;

        assign_and_replace_next_stmt!(self, ctx, id.upcast());
        debug_assert_eq!(self.expr_parent, ExpressionParent::None);
        self.expr_parent = ExpressionParent::ExpressionStmt(id);
        self.visit_expr(ctx, expr_id)?;
        self.expr_parent = ExpressionParent::None;

        Ok(())
    }


    //--------------------------------------------------------------------------
    // Expression visitors
    //--------------------------------------------------------------------------

    fn visit_assignment_expr(&mut self, ctx: &mut Ctx, id: AssignmentExpressionId) -> VisitorResult {
        let upcast_id = id.upcast();

        let assignment_expr = &mut ctx.heap[id];

        // Although we call assignment an expression to simplify the compiler's
        // code (mainly typechecking), we disallow nested use in expressions
        match self.expr_parent {
            // Look at us: lying through our teeth while providing error messages.
            ExpressionParent::Memory(_) => {},
            ExpressionParent::ExpressionStmt(_) => {},
            _ => {
                let assignment_span = assignment_expr.full_span;
                return Err(ParseError::new_error_str_at_span(
                    &ctx.module().source, assignment_span,
                    "assignments are statements, and cannot be used in expressions"
                ))
            },
        }

        let left_expr_id = assignment_expr.left;
        let right_expr_id = assignment_expr.right;
        let old_expr_parent = self.expr_parent;
        assignment_expr.parent = old_expr_parent;

        self.expr_parent = ExpressionParent::Expression(upcast_id, 0);
        self.must_be_assignable = Some(assignment_expr.operator_span);
        self.visit_expr(ctx, left_expr_id)?;
        self.expr_parent = ExpressionParent::Expression(upcast_id, 1);
        self.must_be_assignable = None;
        self.visit_expr(ctx, right_expr_id)?;
        self.expr_parent = old_expr_parent;
        Ok(())
    }

    fn visit_binding_expr(&mut self, ctx: &mut Ctx, id: BindingExpressionId) -> VisitorResult {
        let upcast_id = id.upcast();

        // Check for valid context of binding expression
        if let Some(span) = self.must_be_assignable {
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, span, "cannot assign to the result from a binding expression"
            ));
        }

        if self.in_test_expr.is_invalid() {
            let binding_expr = &ctx.heap[id];
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, binding_expr.full_span,
                "binding expressions can only be used inside the testing expression of 'if' and 'while' statements"
            ));
        }

        if !self.in_binding_expr.is_invalid() {
            let binding_expr = &ctx.heap[id];
            let previous_expr = &ctx.heap[self.in_binding_expr];
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, binding_expr.full_span,
                "nested binding expressions are not allowed"
            ).with_info_str_at_span(
                &ctx.module().source, previous_expr.operator_span,
                "the outer binding expression is found here"
            ));
        }

        let mut seeking_parent = self.expr_parent;
        loop {
            // Perform upward search to make sure only LogicalAnd is applied to
            // the binding expression
            let valid = match seeking_parent {
                ExpressionParent::If(_) | ExpressionParent::While(_) => {
                    // Every parent expression (if any) were LogicalAnd.
                    break;
                }
                ExpressionParent::Expression(parent_id, _) => {
                    let parent_expr = &ctx.heap[parent_id];
                    match parent_expr {
                        Expression::Binary(parent_expr) => {
                            // Set new parent to continue the search. Otherwise
                            // halt and provide an error using the current
                            // parent.
                            if parent_expr.operation == BinaryOperator::LogicalAnd {
                                seeking_parent = parent_expr.parent;
                                true
                            } else {
                                false
                            }
                        },
                        _ => false,
                    }
                },
                _ => unreachable!(), // nested under if/while, so always expressions as parents
            };

            if !valid {
                let binding_expr = &ctx.heap[id];
                let parent_expr = &ctx.heap[seeking_parent.as_expression()];
                return Err(ParseError::new_error_str_at_span(
                    &ctx.module().source, binding_expr.full_span,
                    "only the logical-and operator (&&) may be applied to binding expressions"
                ).with_info_str_at_span(
                    &ctx.module().source, parent_expr.operation_span(),
                    "this was the disallowed operation applied to the result from a binding expression"
                ));
            }
        }

        // Perform all of the index/parent assignment magic
        let binding_expr = &mut ctx.heap[id];

        let old_expr_parent = self.expr_parent;
        binding_expr.parent = old_expr_parent;
        self.in_binding_expr = id;

        // Perform preliminary check on children: binding expressions only make
        // sense if the left hand side is just a variable expression, or if it
        // is a literal of some sort. The typechecker will take care of the rest
        let bound_to_id = binding_expr.bound_to;
        let bound_from_id = binding_expr.bound_from;

        match &ctx.heap[bound_to_id] {
            // Variables may not be binding variables, and literals may
            // actually not contain binding variables. But in that case we just
            // perform an equality check.
            Expression::Variable(_) => {}
            Expression::Literal(_) => {},
            _ => {
                let binding_expr = &ctx.heap[id];
                return Err(ParseError::new_error_str_at_span(
                    &ctx.module().source, binding_expr.operator_span,
                    "the left hand side of a binding expression may only be a variable or a literal expression"
                ));
            },
        }

        // Visit the children themselves
        self.in_binding_expr_lhs = true;
        self.expr_parent = ExpressionParent::Expression(upcast_id, 0);
        self.visit_expr(ctx, bound_to_id)?;
        self.in_binding_expr_lhs = false;
        self.expr_parent = ExpressionParent::Expression(upcast_id, 1);
        self.visit_expr(ctx, bound_from_id)?;

        self.expr_parent = old_expr_parent;
        self.in_binding_expr = BindingExpressionId::new_invalid();

        Ok(())
    }

    fn visit_conditional_expr(&mut self, ctx: &mut Ctx, id: ConditionalExpressionId) -> VisitorResult {
        let upcast_id = id.upcast();
        let conditional_expr = &mut ctx.heap[id];

        if let Some(span) = self.must_be_assignable {
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, span, "cannot assign to the result from a conditional expression"
            ))
        }

        let test_expr_id = conditional_expr.test;
        let true_expr_id = conditional_expr.true_expression;
        let false_expr_id = conditional_expr.false_expression;

        let old_expr_parent = self.expr_parent;
        conditional_expr.parent = old_expr_parent;

        self.expr_parent = ExpressionParent::Expression(upcast_id, 0);
        self.visit_expr(ctx, test_expr_id)?;
        self.expr_parent = ExpressionParent::Expression(upcast_id, 1);
        self.visit_expr(ctx, true_expr_id)?;
        self.expr_parent = ExpressionParent::Expression(upcast_id, 2);
        self.visit_expr(ctx, false_expr_id)?;
        self.expr_parent = old_expr_parent;

        Ok(())
    }

    fn visit_binary_expr(&mut self, ctx: &mut Ctx, id: BinaryExpressionId) -> VisitorResult {
        let upcast_id = id.upcast();
        let binary_expr = &mut ctx.heap[id];

        if let Some(span) = self.must_be_assignable {
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, span, "cannot assign to the result from a binary expression"
            ))
        }

        let left_expr_id = binary_expr.left;
        let right_expr_id = binary_expr.right;

        let old_expr_parent = self.expr_parent;
        binary_expr.parent = old_expr_parent;

        self.expr_parent = ExpressionParent::Expression(upcast_id, 0);
        self.visit_expr(ctx, left_expr_id)?;
        self.expr_parent = ExpressionParent::Expression(upcast_id, 1);
        self.visit_expr(ctx, right_expr_id)?;
        self.expr_parent = old_expr_parent;

        Ok(())
    }

    fn visit_unary_expr(&mut self, ctx: &mut Ctx, id: UnaryExpressionId) -> VisitorResult {
        let unary_expr = &mut ctx.heap[id];
        let expr_id = unary_expr.expression;

        if let Some(span) = self.must_be_assignable {
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, span, "cannot assign to the result from a unary expression"
            ))
        }

        let old_expr_parent = self.expr_parent;
        unary_expr.parent = old_expr_parent;

        self.expr_parent = ExpressionParent::Expression(id.upcast(), 0);
        self.visit_expr(ctx, expr_id)?;
        self.expr_parent = old_expr_parent;

        Ok(())
    }

    fn visit_indexing_expr(&mut self, ctx: &mut Ctx, id: IndexingExpressionId) -> VisitorResult {
        let upcast_id = id.upcast();
        let indexing_expr = &mut ctx.heap[id];

        let subject_expr_id = indexing_expr.subject;
        let index_expr_id = indexing_expr.index;

        let old_expr_parent = self.expr_parent;
        indexing_expr.parent = old_expr_parent;

        self.expr_parent = ExpressionParent::Expression(upcast_id, 0);
        self.visit_expr(ctx, subject_expr_id)?;

        let old_assignable = self.must_be_assignable.take();
        self.expr_parent = ExpressionParent::Expression(upcast_id, 1);
        self.visit_expr(ctx, index_expr_id)?;

        self.must_be_assignable = old_assignable;
        self.expr_parent = old_expr_parent;

        Ok(())
    }

    fn visit_slicing_expr(&mut self, ctx: &mut Ctx, id: SlicingExpressionId) -> VisitorResult {
        let upcast_id = id.upcast();
        let slicing_expr = &mut ctx.heap[id];

        if let Some(span) = self.must_be_assignable {
            // TODO: @Slicing
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, span, "assignment to slices should be valid in the final language, but is currently not implemented"
            ));
        }

        let subject_expr_id = slicing_expr.subject;
        let from_expr_id = slicing_expr.from_index;
        let to_expr_id = slicing_expr.to_index;

        let old_expr_parent = self.expr_parent;
        slicing_expr.parent = old_expr_parent;

        self.expr_parent = ExpressionParent::Expression(upcast_id, 0);
        self.visit_expr(ctx, subject_expr_id)?;

        let old_assignable = self.must_be_assignable.take();
        self.expr_parent = ExpressionParent::Expression(upcast_id, 1);
        self.visit_expr(ctx, from_expr_id)?;
        self.expr_parent = ExpressionParent::Expression(upcast_id, 2);
        self.visit_expr(ctx, to_expr_id)?;

        self.must_be_assignable = old_assignable;
        self.expr_parent = old_expr_parent;

        Ok(())
    }

    fn visit_select_expr(&mut self, ctx: &mut Ctx, id: SelectExpressionId) -> VisitorResult {
        let select_expr = &mut ctx.heap[id];
        let expr_id = select_expr.subject;

        let old_expr_parent = self.expr_parent;
        select_expr.parent = old_expr_parent;

        self.expr_parent = ExpressionParent::Expression(id.upcast(), 0);
        self.visit_expr(ctx, expr_id)?;
        self.expr_parent = old_expr_parent;

        Ok(())
    }

    fn visit_literal_expr(&mut self, ctx: &mut Ctx, id: LiteralExpressionId) -> VisitorResult {
        let literal_expr = &mut ctx.heap[id];
        let old_expr_parent = self.expr_parent;
        literal_expr.parent = old_expr_parent;

        if let Some(span) = self.must_be_assignable {
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, span, "cannot assign to a literal expression"
            ))
        }

        match &mut literal_expr.value {
            Literal::Null | Literal::True | Literal::False |
            Literal::Character(_) | Literal::Bytestring(_) | Literal::String(_) |
            Literal::Integer(_) => {
                // Just the parent has to be set, done above
            },
            Literal::Struct(literal) => {
                let upcast_id = id.upcast();
                // Retrieve type definition
                let type_definition = ctx.types.get_base_definition(&literal.definition).unwrap();
                let struct_definition = type_definition.definition.as_struct();

                // Make sure all fields are specified, none are specified twice
                // and all fields exist on the struct definition
                let mut specified = Vec::new(); // TODO: @performance
                specified.resize(struct_definition.fields.len(), false);

                for field in &mut literal.fields {
                    // Find field in the struct definition
                    let field_idx = struct_definition.fields.iter().position(|v| v.identifier == field.identifier);
                    if field_idx.is_none() {
                        let field_span = field.identifier.span;
                        let literal = ctx.heap[id].value.as_struct();
                        let ast_definition = &ctx.heap[literal.definition];
                        return Err(ParseError::new_error_at_span(
                            &ctx.module().source, field_span, format!(
                                "This field does not exist on the struct '{}'",
                                ast_definition.identifier().value.as_str()
                            )
                        ));
                    }
                    field.field_idx = field_idx.unwrap();

                    // Check if specified more than once
                    if specified[field.field_idx] {
                        let field_span = field.identifier.span;
                        return Err(ParseError::new_error_str_at_span(
                            &ctx.module().source, field_span,
                            "This field is specified more than once"
                        ));
                    }

                    specified[field.field_idx] = true;
                }

                if !specified.iter().all(|v| *v) {
                    // Some fields were not specified
                    let mut not_specified = String::new();
                    let mut num_not_specified = 0;
                    for (def_field_idx, is_specified) in specified.iter().enumerate() {
                        if !is_specified {
                            if !not_specified.is_empty() { not_specified.push_str(", ") }
                            let field_ident = &struct_definition.fields[def_field_idx].identifier;
                            not_specified.push_str(field_ident.value.as_str());
                            num_not_specified += 1;
                        }
                    }

                    debug_assert!(num_not_specified > 0);
                    let msg = if num_not_specified == 1 {
                        format!("not all fields are specified, '{}' is missing", not_specified)
                    } else {
                        format!("not all fields are specified, [{}] are missing", not_specified)
                    };

                    let literal_span = literal.parser_type.full_span;
                    return Err(ParseError::new_error_at_span(
                        &ctx.module().source, literal_span, msg
                    ));
                }

                // Need to traverse fields expressions in struct and evaluate
                // the poly args
                let mut expr_section = self.expression_buffer.start_section();
                for field in &literal.fields {
                    expr_section.push(field.value);
                }

                for expr_idx in 0..expr_section.len() {
                    let expr_id = expr_section[expr_idx];
                    self.expr_parent = ExpressionParent::Expression(upcast_id, expr_idx as u32);
                    self.visit_expr(ctx, expr_id)?;
                }

                expr_section.forget();
            },
            Literal::Enum(literal) => {
                // Make sure the variant exists
                let type_definition = ctx.types.get_base_definition(&literal.definition).unwrap();
                let enum_definition = type_definition.definition.as_enum();

                let variant_idx = enum_definition.variants.iter().position(|v| {
                    v.identifier == literal.variant
                });

                if variant_idx.is_none() {
                    let literal = ctx.heap[id].value.as_enum();
                    let ast_definition = ctx.heap[literal.definition].as_enum();
                    return Err(ParseError::new_error_at_span(
                        &ctx.module().source, literal.parser_type.full_span, format!(
                            "the variant '{}' does not exist on the enum '{}'",
                            literal.variant.value.as_str(), ast_definition.identifier.value.as_str()
                        )
                    ));
                }

                literal.variant_idx = variant_idx.unwrap();
            },
            Literal::Union(literal) => {
                // Make sure the variant exists
                let type_definition = ctx.types.get_base_definition(&literal.definition).unwrap();
                let union_definition = type_definition.definition.as_union();

                let variant_idx = union_definition.variants.iter().position(|v| {
                    v.identifier == literal.variant
                });
                if variant_idx.is_none() {
                    let literal = ctx.heap[id].value.as_union();
                    let ast_definition = ctx.heap[literal.definition].as_union();
                    return Err(ParseError::new_error_at_span(
                        &ctx.module().source, literal.parser_type.full_span, format!(
                            "the variant '{}' does not exist on the union '{}'",
                            literal.variant.value.as_str(), ast_definition.identifier.value.as_str()
                        )
                    ));
                }

                literal.variant_idx = variant_idx.unwrap();

                // Make sure the number of specified values matches the expected
                // number of embedded values in the union variant.
                let union_variant = &union_definition.variants[literal.variant_idx];
                if union_variant.embedded.len() != literal.values.len() {
                    let literal = ctx.heap[id].value.as_union();
                    let ast_definition = ctx.heap[literal.definition].as_union();
                    return Err(ParseError::new_error_at_span(
                        &ctx.module().source, literal.parser_type.full_span, format!(
                            "The variant '{}' of union '{}' expects {} embedded values, but {} were specified",
                            literal.variant.value.as_str(), ast_definition.identifier.value.as_str(),
                            union_variant.embedded.len(), literal.values.len()
                        ),
                    ))
                }

                // Traverse embedded values of union (if any) and evaluate the
                // polymorphic arguments
                let upcast_id = id.upcast();
                let mut expr_section = self.expression_buffer.start_section();
                for value in &literal.values {
                    expr_section.push(*value);
                }

                for expr_idx in 0..expr_section.len() {
                    let expr_id = expr_section[expr_idx];
                    self.expr_parent = ExpressionParent::Expression(upcast_id, expr_idx as u32);
                    self.visit_expr(ctx, expr_id)?;
                }

                expr_section.forget();
            },
            Literal::Array(literal) | Literal::Tuple(literal) => {
                // Visit all expressions in the array
                let upcast_id = id.upcast();
                let expr_section = self.expression_buffer.start_section_initialized(literal);
                for expr_idx in 0..expr_section.len() {
                    let expr_id = expr_section[expr_idx];
                    self.expr_parent = ExpressionParent::Expression(upcast_id, expr_idx as u32);
                    self.visit_expr(ctx, expr_id)?;
                }

                expr_section.forget();
            }
        }

        self.expr_parent = old_expr_parent;

        Ok(())
    }

    fn visit_cast_expr(&mut self, ctx: &mut Ctx, id: CastExpressionId) -> VisitorResult {
        let cast_expr = &mut ctx.heap[id];

        if let Some(span) = self.must_be_assignable {
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, span, "cannot assign to the result from a cast expression"
            ))
        }

        let upcast_id = id.upcast();
        let old_expr_parent = self.expr_parent;
        cast_expr.parent = old_expr_parent;

        // Recurse into the thing that we're casting
        self.expr_parent = ExpressionParent::Expression(upcast_id, 0);
        let subject_id = cast_expr.subject;
        self.visit_expr(ctx, subject_id)?;
        self.expr_parent = old_expr_parent;

        Ok(())
    }

    fn visit_call_expr(&mut self, ctx: &mut Ctx, id: CallExpressionId) -> VisitorResult {
        let call_expr = &ctx.heap[id];

        if let Some(span) = self.must_be_assignable {
            return Err(ParseError::new_error_str_at_span(
                &ctx.module().source, span, "cannot assign to the result from a call expression"
            ))
        }

        // Check whether the method is allowed to be called within the code's
        // context (in sync, definition type, etc.)
        let mut expecting_wrapping_new_stmt = false;
        let mut expecting_primitive_def = false;
        let mut expecting_wrapping_sync_stmt = false;
        let mut expecting_no_select_stmt = false;

        match call_expr.method {
            Method::Get => {
                expecting_primitive_def = true;
                expecting_wrapping_sync_stmt = true;
                if !self.in_select_guard.is_invalid() {
                    // In a select guard. Take the argument (i.e. the port we're
                    // retrieving from) and add it to the list of involved ports
                    // of the guard
                    if call_expr.arguments.len() == 1 {
                        // We're checking the number of arguments later, for now
                        // assume it is correct.
                        let argument = call_expr.arguments[0];
                        let select_stmt = &mut ctx.heap[self.in_select_guard];
                        let select_case = &mut select_stmt.cases[self.in_select_arm as usize];
                        select_case.involved_ports.push((id, argument));
                    }
                }
            },
            Method::Put => {
                expecting_primitive_def = true;
                expecting_wrapping_sync_stmt = true;
                expecting_no_select_stmt = true;
            },
            Method::Fires => {
                expecting_primitive_def = true;
                expecting_wrapping_sync_stmt = true;
            },
            Method::Create => {},
            Method::Length => {},
            Method::Assert => {
                expecting_wrapping_sync_stmt = true;
                expecting_no_select_stmt = true;
                if self.proc_kind == ProcedureKind::Function {
                    let call_span = call_expr.func_span;
                    return Err(ParseError::new_error_str_at_span(
                        &ctx.module().source, call_span,
                        "assert statement may only occur in components"
                    ));
                }
            },
            Method::Print => {},
            Method::SelectStart
            | Method::SelectRegisterCasePort
            | Method::SelectWait => unreachable!(), // not usable by programmer directly
            Method::ComponentRandomU32
            | Method::ComponentTcpClient => {
                expecting_wrapping_new_stmt = true;
            },
            Method::UserFunction => {}
            Method::UserComponent => {
                expecting_wrapping_new_stmt = true;
            },
        }

        let call_expr = &mut ctx.heap[id];

        fn get_span_and_name<'a>(ctx: &'a Ctx, id: CallExpressionId) -> (InputSpan, String) {
            let call = &ctx.heap[id];
            let span = call.func_span;
            let name = String::from_utf8_lossy(ctx.module().source.section_at_span(span)).to_string();
            return (span, name);
        }
        if expecting_primitive_def {
            if self.proc_kind != ProcedureKind::Primitive {
                let (call_span, func_name) = get_span_and_name(ctx, id);
                return Err(ParseError::new_error_at_span(
                    &ctx.module().source, call_span,
                    format!("a call to '{}' may only occur in primitive component definitions", func_name)
                ));
            }
        }

        if expecting_wrapping_sync_stmt {
            if self.in_sync.is_invalid() {
                let (call_span, func_name) = get_span_and_name(ctx, id);
                return Err(ParseError::new_error_at_span(
                    &ctx.module().source, call_span,
                    format!("a call to '{}' may only occur inside synchronous blocks", func_name)
                ))
            }
        }

        if expecting_no_select_stmt {
            if !self.in_select_guard.is_invalid() {
                let (call_span, func_name) = get_span_and_name(ctx, id);
                return Err(ParseError::new_error_at_span(
                    &ctx.module().source, call_span,
                    format!("a call to '{}' may not occur in a select statement's guard", func_name)
                ));
            }
        }

        if expecting_wrapping_new_stmt {
            if !self.expr_parent.is_new() {
                let call_span = call_expr.func_span;
                return Err(ParseError::new_error_str_at_span(
                    &ctx.module().source, call_span,
                    "cannot call a component, it can only be instantiated by using 'new'"
                ));
            }
        } else {
            if self.expr_parent.is_new() {
                let call_span = call_expr.func_span;
                return Err(ParseError::new_error_str_at_span(
                    &ctx.module().source, call_span,
                    "only components can be instantiated, this is a function"
                ));
            }
        }

        // Check the number of arguments
        let call_definition = ctx.types.get_base_definition(&call_expr.procedure.upcast()).unwrap();
        let num_expected_args = match &call_definition.definition {
            DefinedTypeVariant::Procedure(definition) => definition.arguments.len(),
            _ => unreachable!(),
        };

        let num_provided_args = call_expr.arguments.len();
        if num_provided_args != num_expected_args {
            let argument_text = if num_expected_args == 1 { "argument" } else { "arguments" };
            let call_span = call_expr.full_span;
            return Err(ParseError::new_error_at_span(
                &ctx.module().source, call_span, format!(
                    "expected {} {}, but {} were provided",
                    num_expected_args, argument_text, num_provided_args
                )
            ));
        }

        // Recurse into all of the arguments and set the expression's parent
        let upcast_id = id.upcast();

        let section = self.expression_buffer.start_section_initialized(&call_expr.arguments);
        let old_expr_parent = self.expr_parent;
        call_expr.parent = old_expr_parent;

        for arg_expr_idx in 0..section.len() {
            let arg_expr_id = section[arg_expr_idx];
            self.expr_parent = ExpressionParent::Expression(upcast_id, arg_expr_idx as u32);
            self.visit_expr(ctx, arg_expr_id)?;
        }

        section.forget();
        self.expr_parent = old_expr_parent;

        Ok(())
    }

    fn visit_variable_expr(&mut self, ctx: &mut Ctx, id: VariableExpressionId) -> VisitorResult {
        let var_expr = &ctx.heap[id];

        // Check if declaration was already resolved (this occurs for the
        // variable expr that is on the LHS of the assignment expr that is
        // associated with a variable declaration)
        let mut variable_id = var_expr.declaration;
        let mut is_binding_target = false;

        // Otherwise try to find it
        if variable_id.is_none() {
            variable_id = self.find_variable(ctx, self.relative_pos_in_parent, &var_expr.identifier);
        }

        // Otherwise try to see if is a variable introduced by a binding expr
        let variable_id = if let Some(variable_id) = variable_id {
            variable_id
        } else {
            if self.in_binding_expr.is_invalid() || !self.in_binding_expr_lhs {
                return Err(ParseError::new_error_str_at_span(
                    &ctx.module().source, var_expr.identifier.span, "unresolved variable"
                ));
            }

            // This is a binding variable, but it may only appear in very
            // specific locations.
            let is_valid_binding = match self.expr_parent {
                ExpressionParent::Expression(expr_id, idx) => {
                    match &ctx.heap[expr_id] {
                        Expression::Binding(_binding_expr) => {
                            // Nested binding is disallowed, and because of
                            // the check above we know we're directly at the
                            // LHS of the binding expression
                            debug_assert_eq!(_binding_expr.this, self.in_binding_expr);
                            debug_assert_eq!(idx, 0);
                            true
                        }
                        Expression::Literal(_lit_expr) => {
                            // Only struct, unions, tuples and arrays can
                            // have subexpressions, so we're always fine
                            dbg_code!({
                                match _lit_expr.value {
                                    Literal::Struct(_) | Literal::Union(_) | Literal::Array(_) | Literal::Tuple(_) => {},
                                    _ => unreachable!(),
                                }
                            });

                            true
                        },
                        _ => false,
                    }
                },
                _ => {
                    false
                }
            };

            if !is_valid_binding {
                let binding_expr = &ctx.heap[self.in_binding_expr];
                return Err(ParseError::new_error_str_at_span(
                    &ctx.module().source, var_expr.identifier.span,
                    "illegal location for binding variable: binding variables may only be nested under a binding expression, or a struct, union or array literal"
                ).with_info_at_span(
                    &ctx.module().source, binding_expr.operator_span, format!(
                        "'{}' was interpreted as a binding variable because the variable is not declared and it is nested under this binding expression",
                        var_expr.identifier.value.as_str()
                    )
                ));
            }

            // By now we know that this is a valid binding expression. Given
            // that a binding expression must be nested under an if/while
            // statement, we now add the variable to the scope associated with
            // that statement.
            let bound_identifier = var_expr.identifier.clone();
            let bound_variable_id = ctx.heap.alloc_variable(|this| Variable {
                this,
                kind: VariableKind::Binding,
                parser_type: ParserType {
                    elements: vec![ParserTypeElement {
                        element_span: bound_identifier.span,
                        variant: ParserTypeVariant::Inferred
                    }],
                    full_span: bound_identifier.span
                },
                identifier: bound_identifier,
                relative_pos_in_parent: 0,
                unique_id_in_scope: -1,
            });

            let scope_id = match &ctx.heap[self.in_test_expr] {
                Statement::If(stmt) => stmt.true_case.scope,
                Statement::While(stmt) => stmt.scope,
                _ => unreachable!(),
            };

            self.checked_at_single_scope_add_local(ctx, scope_id, -1, bound_variable_id)?; // add at -1 such that first statement can find the variable if needed

            is_binding_target = true;
            bound_variable_id
        };

        let var_expr = &mut ctx.heap[id];
        var_expr.declaration = Some(variable_id);
        var_expr.used_as_binding_target = is_binding_target;
        var_expr.parent = self.expr_parent;

        Ok(())
    }
}

impl PassValidationLinking {
    //--------------------------------------------------------------------------
    // Special traversal
    //--------------------------------------------------------------------------

    /// Pushes a new scope associated with a particular statement. If that
    /// statement already has an associated scope (i.e. scope associated with
    /// sync statement or select statement's arm) then we won't do anything.
    /// In all cases the caller must call `pop_statement_scope` with the scope
    /// and relative scope position returned by this function.
    fn push_scope(&mut self, ctx: &mut Ctx, is_top_level_scope: bool, pushed_scope_id: ScopeId) -> (ScopeId, i32) {
        // Set the properties of the pushed scope (it is already created during
        // AST construction, but most values are not yet set to their correct
        // values)
        let old_scope_id = self.cur_scope;

        let scope = &mut ctx.heap[pushed_scope_id];
        if !is_top_level_scope {
            scope.parent = Some(old_scope_id);
        }

        scope.relative_pos_in_parent = self.relative_pos_in_parent;
        let old_relative_pos = self.relative_pos_in_parent;
        self.relative_pos_in_parent = 0;

        // Link up scopes
        if !is_top_level_scope {
            let old_scope = &mut ctx.heap[old_scope_id];
            old_scope.nested.push(pushed_scope_id);
        }

        // Set as current traversal scope, then return old scope
        self.cur_scope = pushed_scope_id;
        return (old_scope_id, old_relative_pos)
    }

    fn pop_scope(&mut self, scope_to_restore: (ScopeId, i32)) {
        self.cur_scope = scope_to_restore.0;
        self.relative_pos_in_parent = scope_to_restore.1;
    }

    fn resolve_pending_control_flow_targets(&mut self, ctx: &mut Ctx) -> Result<(), ParseError> {
        for entry in &self.control_flow_stmts {
            let stmt = &ctx.heap[entry.statement];

            match stmt {
                Statement::Break(stmt) => {
                    let stmt_id = stmt.this;
                    let target_while_id = Self::resolve_break_or_continue_target(ctx, entry, stmt.span, &stmt.label)?;
                    let target_while_stmt = &ctx.heap[target_while_id];
                    let target_end_while_id = target_while_stmt.end_while;
                    debug_assert!(!target_end_while_id.is_invalid());

                    let break_stmt = &mut ctx.heap[stmt_id];
                    break_stmt.target = target_end_while_id;
                },
                Statement::Continue(stmt) => {
                    let stmt_id = stmt.this;
                    let target_while_id = Self::resolve_break_or_continue_target(ctx, entry, stmt.span, &stmt.label)?;

                    let continue_stmt = &mut ctx.heap[stmt_id];
                    continue_stmt.target = target_while_id;
                },
                Statement::Goto(stmt) => {
                    let stmt_id = stmt.this;
                    let target_id = Self::find_label(entry.in_scope, ctx, &stmt.label)?;
                    let target_stmt = &ctx.heap[target_id];
                    if entry.in_sync != target_stmt.in_sync {
                        // Nested sync not allowed. And goto can only go to
                        // outer scopes, so we must be escaping from a sync.
                        debug_assert!(target_stmt.in_sync.is_invalid());    // target not in sync
                        debug_assert!(!entry.in_sync.is_invalid()); // but the goto is in sync
                        let goto_stmt = &ctx.heap[stmt_id];
                        let sync_stmt = &ctx.heap[entry.in_sync];
                        return Err(
                            ParseError::new_error_str_at_span(&ctx.module().source, goto_stmt.span, "goto may not escape the surrounding synchronous block")
                            .with_info_str_at_span(&ctx.module().source, target_stmt.label.span, "this is the target of the goto statement")
                            .with_info_str_at_span(&ctx.module().source, sync_stmt.span, "which will jump past this statement")
                        );
                    }

                    let goto_stmt = &mut ctx.heap[stmt_id];
                    goto_stmt.target = target_id;
                },
                _ => unreachable!("cannot resolve control flow target for {:?}", stmt),
            }
        }

        return Ok(())
    }

    //--------------------------------------------------------------------------
    // Utilities
    //--------------------------------------------------------------------------

    /// Adds a local variable to the current scope. It will also annotate the
    /// `Local` in the AST with its relative position in the block.
    fn checked_add_local(&mut self, ctx: &mut Ctx, target_scope_id: ScopeId, target_relative_pos: i32, new_variable_id: VariableId) -> Result<(), ParseError> {
        let new_variable = &ctx.heap[new_variable_id];

        // We immediately go to the parent scope. We check the target scope
        // in the call at the end. That is also where we check for collisions
        // with symbols.
        let mut scope = &ctx.heap[target_scope_id];
        let mut cur_relative_pos = scope.relative_pos_in_parent;
        while let Some(scope_parent_id) = scope.parent {
            scope = &ctx.heap[scope_parent_id];

            // Check for collisions
            for variable_id in scope.variables.iter().copied() {
                let existing_variable = &ctx.heap[variable_id];
                if existing_variable.identifier == new_variable.identifier &&
                    existing_variable.this != new_variable_id &&
                    cur_relative_pos >= existing_variable.relative_pos_in_parent {
                    return Err(
                        ParseError::new_error_str_at_span(
                            &ctx.module().source, new_variable.identifier.span, "Local variable name conflicts with another variable"
                        ).with_info_str_at_span(
                            &ctx.module().source, existing_variable.identifier.span, "Previous variable is found here"
                        )
                    );
                }
            }

            cur_relative_pos = scope.relative_pos_in_parent;
        }

        // No collisions in any of the parent scope, attempt to add to scope
        self.checked_at_single_scope_add_local(ctx, target_scope_id, target_relative_pos, new_variable_id)
    }

    /// Adds a local variable to the specified scope. Will check the specified
    /// scope for variable conflicts and the symbol table for global conflicts.
    /// Will NOT check parent scopes of the specified scope.
    fn checked_at_single_scope_add_local(
        &mut self, ctx: &mut Ctx, scope_id: ScopeId, relative_pos: i32, new_variable_id: VariableId
    ) -> Result<(), ParseError> {
        // Check the symbol table for conflicts
        {
            let cur_scope = SymbolScope::Definition(self.proc_id.upcast());
            let ident = &ctx.heap[new_variable_id].identifier;
            if let Some(symbol) = ctx.symbols.get_symbol_by_name(cur_scope, &ident.value.as_bytes()) {
                return Err(ParseError::new_error_str_at_span(
                    &ctx.module().source, ident.span,
                    "local variable declaration conflicts with symbol"
                ).with_info_str_at_span(
                    &ctx.module().source, symbol.variant.span_of_introduction(&ctx.heap), "the conflicting symbol is introduced here"
                ));
            }
        }

        // Check the specified scope for conflicts
        let new_variable = &ctx.heap[new_variable_id];
        let scope = &ctx.heap[scope_id];

        for variable_id in scope.variables.iter().copied() {
            let old_variable = &ctx.heap[variable_id];
            if new_variable.this != old_variable.this &&
                // relative_pos >= other_local.relative_pos_in_block &&
                new_variable.identifier == old_variable.identifier {
                // Collision
                return Err(
                    ParseError::new_error_str_at_span(
                        &ctx.module().source, new_variable.identifier.span, "Local variable name conflicts with another variable"
                    ).with_info_str_at_span(
                        &ctx.module().source, old_variable.identifier.span, "Previous variable is found here"
                    )
                );
            }
        }

        // No collisions
        let scope = &mut ctx.heap[scope_id];
        scope.variables.push(new_variable_id);

        let variable = &mut ctx.heap[new_variable_id];
        variable.relative_pos_in_parent = relative_pos;

        Ok(())
    }

    /// Finds a variable in the visitor's scope that must appear before the
    /// specified relative position within that block.
    fn find_variable(&self, ctx: &Ctx, mut relative_pos: i32, identifier: &Identifier) -> Option<VariableId> {
        let mut scope_id = self.cur_scope;

        loop {
            // Check if we can find the variable in the current scope
            let scope = &ctx.heap[scope_id];
            
            for variable_id in scope.variables.iter().copied() {
                let variable = &ctx.heap[variable_id];
                
                if variable.relative_pos_in_parent < relative_pos && identifier == &variable.identifier {
                    return Some(variable_id);
                }
            }

            // Could not find variable, move to parent scope and try again
            if scope.parent.is_none() {
                return None;
            }

            scope_id = scope.parent.unwrap();
            relative_pos = scope.relative_pos_in_parent;
        }
    }

    /// Adds a particular label to the current scope. Will return an error if
    /// there is another label with the same name visible in the current scope.
    fn checked_add_label(&mut self, ctx: &mut Ctx, relative_pos: i32, in_sync: SynchronousStatementId, new_label_id: LabeledStatementId) -> Result<(), ParseError> {
        // Make sure label is not defined within the current scope or any of the
        // parent scope.
        let new_label = &mut ctx.heap[new_label_id];
        new_label.relative_pos_in_parent = relative_pos;
        new_label.in_sync = in_sync;

        let new_label = &ctx.heap[new_label_id];
        let mut scope_id = self.cur_scope;

        loop {
            let scope = &ctx.heap[scope_id];
            for existing_label_id in scope.labels.iter().copied() {
                let existing_label = &ctx.heap[existing_label_id];
                if existing_label.label == new_label.label {
                    // Collision
                    return Err(ParseError::new_error_str_at_span(
                        &ctx.module().source, new_label.label.span, "label name is used more than once"
                    ).with_info_str_at_span(
                        &ctx.module().source, existing_label.label.span, "the other label is found here"
                    ));
                }
            }

            if scope.parent.is_none() {
                break;
            }

            scope_id = scope.parent.unwrap();
        }

        // No collisions
        let scope = &mut ctx.heap[self.cur_scope];
        scope.labels.push(new_label_id);

        Ok(())
    }

    /// Finds a particular labeled statement by its identifier. Once found it
    /// will make sure that the target label does not skip over any variable
    /// declarations within the scope in which the label was found.
    fn find_label(mut scope_id: ScopeId, ctx: &Ctx, identifier: &Identifier) -> Result<LabeledStatementId, ParseError> {
        loop {
            let scope = &ctx.heap[scope_id];
            let relative_scope_pos = scope.relative_pos_in_parent;

            for label_id in scope.labels.iter().copied() {
                let label = &ctx.heap[label_id];
                if label.label == *identifier {
                    // Found the target label, now make sure that the jump to
                    // the label doesn't imply a skipped variable declaration
                    for variable_id in scope.variables.iter().copied() {
                        // TODO: Better to do this in control flow analysis, it
                        //  is legal to skip over a variable declaration if it
                        //  is not actually being used.
                        let variable = &ctx.heap[variable_id];
                        if variable.relative_pos_in_parent > relative_scope_pos && variable.relative_pos_in_parent < label.relative_pos_in_parent {
                            return Err(
                                ParseError::new_error_str_at_span(&ctx.module().source, identifier.span, "this target label skips over a variable declaration")
                                .with_info_str_at_span(&ctx.module().source, label.label.span, "because it jumps to this label")
                                .with_info_str_at_span(&ctx.module().source, variable.identifier.span, "which skips over this variable")
                            );
                        }
                    }
                    return Ok(label_id);
                }
            }

            if scope.parent.is_none() {
                return Err(ParseError::new_error_str_at_span(
                    &ctx.module().source, identifier.span, "could not find this label"
                ));
            }

            scope_id = scope.parent.unwrap();
        }
    }

    /// This function will check if the provided scope has a parent that belongs
    /// to a while statement.
    fn scope_is_nested_in_while_statement(mut scope_id: ScopeId, ctx: &Ctx, expected_while_id: WhileStatementId) -> bool {
        let while_stmt = &ctx.heap[expected_while_id];

        loop {
            let scope = &ctx.heap[scope_id];
            if scope.this == while_stmt.scope {
                return true;
            }

            match scope.parent {
                Some(new_scope_id) => scope_id = new_scope_id,
                None => return false, // walked all the way up, not encountering the while statement
            }
        }
    }

    /// This function should be called while dealing with break/continue
    /// statements. It will try to find the targeted while statement, using the
    /// target label if provided. If a valid target is found then the loop's
    /// ID will be returned, otherwise a parsing error is constructed.
    /// The provided input position should be the position of the break/continue
    /// statement.
    fn resolve_break_or_continue_target(ctx: &Ctx, control_flow: &ControlFlowStatement, span: InputSpan, label: &Option<Identifier>) -> Result<WhileStatementId, ParseError> {
        let target = match label {
            Some(label) => {
                let target_id = Self::find_label(control_flow.in_scope, ctx, label)?;

                // Make sure break target is a while statement
                let target = &ctx.heap[target_id];
                if let Statement::While(target_stmt) = &ctx.heap[target.body] {
                    // Even though we have a target while statement, the control
                    // flow statement might not be present underneath this
                    // particular labeled while statement.
                    if !Self::scope_is_nested_in_while_statement(control_flow.in_scope, ctx, target_stmt.this) {
                        return Err(ParseError::new_error_str_at_span(
                            &ctx.module().source, label.span, "break statement is not nested under the target label's while statement"
                        ).with_info_str_at_span(
                            &ctx.module().source, target.label.span, "the targeted label is found here"
                        ));
                    }

                    target_stmt.this
                } else {
                    return Err(ParseError::new_error_str_at_span(
                        &ctx.module().source, label.span, "incorrect break target label, it must target a while loop"
                    ).with_info_str_at_span(
                        &ctx.module().source, target.label.span, "The targeted label is found here"
                    ));
                }
            },
            None => {
                // Use the enclosing while statement, the break must be
                // nested within that while statement
                if control_flow.in_while.is_invalid() {
                    return Err(ParseError::new_error_str_at_span(
                        &ctx.module().source, span, "Break statement is not nested under a while loop"
                    ));
                }

                control_flow.in_while
            }
        };

        // We have a valid target for the break statement. But we need to
        // make sure we will not break out of a synchronous block
        {
            let target_while = &ctx.heap[target];
            if target_while.in_sync != control_flow.in_sync {
                // Break is nested under while statement, so can only escape a
                // sync block if the sync is nested inside the while statement.
                debug_assert!(!control_flow.in_sync.is_invalid());
                let sync_stmt = &ctx.heap[control_flow.in_sync];
                return Err(
                    ParseError::new_error_str_at_span(&ctx.module().source, span, "break may not escape the surrounding synchronous block")
                        .with_info_str_at_span(&ctx.module().source, target_while.span, "the break escapes out of this loop")
                        .with_info_str_at_span(&ctx.module().source, sync_stmt.span, "And would therefore escape this synchronous block")
                );
            }
        }

        Ok(target)
    }
}