/*

 * 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;

        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 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::Component {

            return Err(ParseError::new_error_str_at_span(

                &ctx.module().source, cur_sync_span,

                "synchronous statements may only be used in 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(())

    }