pub(crate) mod symbol_table;

pub(crate) mod type_table;

pub(crate) mod tokens;

pub(crate) mod token_parsing;

pub(crate) mod pass_tokenizer;

pub(crate) mod pass_symbols;

pub(crate) mod pass_imports;

pub(crate) mod pass_definitions;

pub(crate) mod pass_definitions_types;

pub(crate) mod pass_validation_linking;

pub(crate) mod pass_rewriting;

pub(crate) mod pass_typing;

pub(crate) mod pass_stack_size;

use tokens::*;

use crate::collections::*;

use visitor::Visitor;

use pass_tokenizer::PassTokenizer;

use pass_symbols::PassSymbols;

use pass_imports::PassImport;

use pass_definitions::PassDefinitions;

use pass_validation_linking::PassValidationLinking;

use pass_typing::{PassTyping, ResolveQueue};

use pass_rewriting::PassRewriting;

use pass_stack_size::PassStackSize;

use symbol_table::*;

use type_table::*;

use crate::protocol::ast::*;

use crate::protocol::input_source::*;

use crate::protocol::ast_printer::ASTWriter;

use crate::protocol::parser::type_table::PolymorphicVariable;

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]

pub enum ModuleCompilationPhase {

    Tokenized,              // source is tokenized

/// resolver takes the `ParserType` structs (the representation of the types

/// written by the programmer), converts them to `InferenceType` structs (the

/// temporary data structure used during type inference) and attempts to arrive

/// at `ConcreteType` structs (the representation of a fully checked and

/// validated type).

///

/// The resolver will visit every statement and expression relevant to the

/// procedure and insert and determine its initial type based on context (e.g. a

/// return statement's expression must match the function's return type, an

/// if statement's test expression must evaluate to a boolean). When all are

/// visited we attempt to make progress in evaluating the types. Whenever a type

/// is progressed we queue the related expressions for further type progression.

/// Once no more expressions are in the queue the algorithm is finished. At this

/// point either all types are inferred (or can be trivially implicitly

/// determined), or we have incomplete types. In the latter case we return an

/// error.

///

/// TODO: Needs a thorough rewrite:

///  0. polymorph_progress is intentionally broken at the moment. Make it work

///     again and use a normal VecSomething.

///  1. The foundation for doing all of the work with predetermined indices

///     instead of with HashMaps is there, but it is not really used because of

///     time constraints. When time is available, rewrite the system such that

///     AST IDs are not needed, and only indices into arrays are used.

macro_rules! debug_log_enabled {

    () => { false };

}

macro_rules! debug_log {

    ($format:literal) => {

        enabled_debug_print!(false, "types", $format);

    };

    ($format:literal, $($args:expr),*) => {

        enabled_debug_print!(false, "types", $format, $($args),*);

    };

}

use std::collections::{HashMap, HashSet};

use crate::collections::{ScopedBuffer, ScopedSection, DequeSet};

use crate::protocol::ast::*;

use crate::protocol::input_source::ParseError;

use crate::protocol::parser::ModuleCompilationPhase;

use crate::protocol::parser::type_table::*;

use crate::protocol::parser::token_parsing::*;

use super::visitor::{

    BUFFER_INIT_CAP_LARGE,

    BUFFER_INIT_CAP_SMALL,

    Ctx,

};

const VOID_TEMPLATE: [InferenceTypePart; 1] = [ InferenceTypePart::Void ];

const MESSAGE_TEMPLATE: [InferenceTypePart; 2] = [ InferenceTypePart::Message, InferenceTypePart::UInt8 ];

const BOOL_TEMPLATE: [InferenceTypePart; 1] = [ InferenceTypePart::Bool ];

const CHARACTER_TEMPLATE: [InferenceTypePart; 1] = [ InferenceTypePart::Character ];

const STRING_TEMPLATE: [InferenceTypePart; 2] = [ InferenceTypePart::String, InferenceTypePart::Character ];

const NUMBERLIKE_TEMPLATE: [InferenceTypePart; 1] = [ InferenceTypePart::NumberLike ];

const INTEGERLIKE_TEMPLATE: [InferenceTypePart; 1] = [ InferenceTypePart::IntegerLike ];

const ARRAY_TEMPLATE: [InferenceTypePart; 2] = [ InferenceTypePart::Array, InferenceTypePart::Unknown ];

const SLICE_TEMPLATE: [InferenceTypePart; 2] = [ InferenceTypePart::Slice, InferenceTypePart::Unknown ];

const ARRAYLIKE_TEMPLATE: [InferenceTypePart; 2] = [ InferenceTypePart::ArrayLike, InferenceTypePart::Unknown ];

/// TODO: @performance Turn into PartialOrd+Ord to simplify checks

#[derive(Debug, Clone, Eq, PartialEq)]

pub(crate) enum InferenceTypePart {

    // When we infer types of AST elements that support polymorphic arguments,

    // then we might have the case that multiple embedded types depend on the

    // polymorphic type (e.g. func bla(T a, T[] b) -> T[][]). If we can infer

    // the type in one place (e.g. argument a), then we may propagate this

    // information to other types (e.g. argument b and the return type). For

    // this reason we place markers in the `InferenceType` instances such that

    // we know which part of the type was originally a polymorphic argument.

    Marker(u32),

    // Completely unknown type, needs to be inferred

    Unknown,

}

impl DualInferenceResult {

    fn modified_lhs(&self) -> bool {

        match self {

            DualInferenceResult::First | DualInferenceResult::Both => true,

            _ => false

        }

    }

    fn modified_rhs(&self) -> bool {

        match self {

            DualInferenceResult::Second | DualInferenceResult::Both => true,

            _ => false

        }

    }

}

#[derive(Debug, PartialEq, Eq)]

enum SingleInferenceResult {

    Unmodified,

    Modified,

    Incompatible

}

enum DefinitionType{

    Component(ComponentDefinitionId),

    Function(FunctionDefinitionId),

}

impl DefinitionType {

    fn definition_id(&self) -> DefinitionId {

        match self {

            DefinitionType::Component(v) => v.upcast(),

            DefinitionType::Function(v) => v.upcast(),

        }

    }

}

pub(crate) struct ResolveQueueElement {

    // Note that using the `definition_id` and the `monomorph_idx` one may

    // query the type table for the full procedure type, thereby retrieving

    // the polymorphic arguments to the procedure.

    pub(crate) root_id: RootId,

    pub(crate) definition_id: DefinitionId,

    pub(crate) reserved_type_id: TypeId,

}

pub(crate) type ResolveQueue = Vec<ResolveQueueElement>;

            let monomorph = ctx.types.get_monomorph(element.reserved_type_id);

            for poly_arg in monomorph.concrete_type.embedded_iter(0) {

                self.poly_vars.push(ConcreteType{ parts: Vec::from(poly_arg) });

            }

        }

        // Visit the definition, setting up the type resolving process, then

        // (attempt to) resolve all types

        self.visit_definition(ctx, element.definition_id)?;

        self.resolve_types(ctx, queue)?;

        Ok(())

    }

    fn reset(&mut self) {

        self.reserved_type_id = TypeId::new_invalid();

        self.definition_type = DefinitionType::Function(FunctionDefinitionId::new_invalid());

        self.poly_vars.clear();

        self.var_types.clear();

        self.expr_types.clear();

        self.extra_data.clear();

        self.expr_queued.clear();

    }

}

    // Definitions

    fn visit_component_definition(&mut self, ctx: &mut Ctx, id: ComponentDefinitionId) -> VisitorResult {

        self.definition_type = DefinitionType::Component(id);

        let comp_def = &ctx.heap[id];

        debug_assert_eq!(comp_def.poly_vars.len(), self.poly_vars.len(), "component polyvars do not match imposed polyvars");

        debug_log!("{}", "-".repeat(50));

        debug_log!("Visiting component '{}': {}", comp_def.identifier.value.as_str(), id.0.index);

        debug_log!("{}", "-".repeat(50));

        // Reserve data for expression types

        debug_assert!(self.expr_types.is_empty());

        self.expr_types.resize(comp_def.num_expressions_in_body as usize, Default::default());

        // Visit parameters

        let section = self.var_buffer.start_section_initialized(comp_def.parameters.as_slice());

        for param_id in section.iter_copied() {

            let param = &ctx.heap[param_id];

            let var_type = self.determine_inference_type_from_parser_type_elements(&param.parser_type.elements, true);

            debug_assert!(var_type.is_done, "expected component arguments to be concrete types");

            self.var_types.insert(param_id, VarData::new_local(var_type));

        }

        section.forget();

        }

        debug_log!("{}", "-".repeat(50));

        // Reserve data for expression types

        debug_assert!(self.expr_types.is_empty());

        self.expr_types.resize(func_def.num_expressions_in_body as usize, Default::default());

        // Visit parameters

        let section = self.var_buffer.start_section_initialized(func_def.parameters.as_slice());

        for param_id in section.iter_copied() {

            let param = &ctx.heap[param_id];

            let var_type = self.determine_inference_type_from_parser_type_elements(&param.parser_type.elements, true);

            debug_assert!(var_type.is_done, "expected function arguments to be concrete types");

            self.var_types.insert(param_id, VarData::new_local(var_type));

        }

        section.forget();

        // Visit all of the expressions within the body

        let body_stmt_id = ctx.heap[id].body;

        self.visit_block_stmt(ctx, body_stmt_id)

    }

    // Statements

    fn visit_block_stmt(&mut self, ctx: &mut Ctx, id: BlockStatementId) -> VisitorResult {

        // Transfer statements for traversal

        let block = &ctx.heap[id];

        let section = self.stmt_buffer.start_section_initialized(block.statements.as_slice());

        for stmt_id in section.iter_copied() {

            self.visit_stmt(ctx, stmt_id)?;

        }

        section.forget();

        Ok(())

    }

    fn visit_local_memory_stmt(&mut self, ctx: &mut Ctx, id: MemoryStatementId) -> VisitorResult {

        let memory_stmt = &ctx.heap[id];

        let initial_expr_id = memory_stmt.initial_expr;

        // Setup memory statement inference

        let local = &ctx.heap[memory_stmt.variable];

        let var_type = self.determine_inference_type_from_parser_type_elements(&local.parser_type.elements, true);

        self.var_types.insert(memory_stmt.variable, VarData::new_local(var_type));

        // Process the initial value

        self.visit_assignment_expr(ctx, initial_expr_id)?;

        Ok(())

    }

    fn visit_local_channel_stmt(&mut self, ctx: &mut Ctx, id: ChannelStatementId) -> VisitorResult {

        let channel_stmt = &ctx.heap[id];

        let from_local = &ctx.heap[channel_stmt.from];

        let from_var_type = self.determine_inference_type_from_parser_type_elements(&from_local.parser_type.elements, true);

        self.var_types.insert(from_local.this, VarData::new_channel(from_var_type, channel_stmt.to));

        let to_local = &ctx.heap[channel_stmt.to];

        let to_var_type = self.determine_inference_type_from_parser_type_elements(&to_local.parser_type.elements, true);

        let false_body_case = if_stmt.false_case;

        let test_expr_id = if_stmt.test;

        self.visit_expr(ctx, test_expr_id)?;

        self.visit_stmt(ctx, true_body_case.body)?;

        if let Some(false_body_case) = false_body_case {

            self.visit_stmt(ctx, false_body_case.body)?;

        }

        Ok(())

    }

    fn visit_while_stmt(&mut self, ctx: &mut Ctx, id: WhileStatementId) -> VisitorResult {

        let while_stmt = &ctx.heap[id];

        let body_id = while_stmt.body;

        let test_expr_id = while_stmt.test;

        self.visit_expr(ctx, test_expr_id)?;

        self.visit_stmt(ctx, body_id)?;

        Ok(())

    }

    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.visit_stmt(ctx, body_id)

    }

    fn visit_fork_stmt(&mut self, ctx: &mut Ctx, id: ForkStatementId) -> VisitorResult {

        let fork_stmt = &ctx.heap[id];

        let left_body_id = fork_stmt.left_body;

        let right_body_id = fork_stmt.right_body;

        self.visit_stmt(ctx, left_body_id)?;

        if let Some(right_body_id) = right_body_id {

            self.visit_stmt(ctx, right_body_id)?;

        }

        Ok(())

    }

    fn visit_select_stmt(&mut self, ctx: &mut Ctx, id: SelectStatementId) -> VisitorResult {

        let select_stmt = &ctx.heap[id];

        let mut section = self.stmt_buffer.start_section();

            section.push(case.body);

        }

        for case_index in 0..num_cases {

            let base_index = 2 * case_index;

            let guard_stmt_id = section[base_index    ];

            let block_stmt_id = section[base_index + 1];

            self.visit_stmt(ctx, guard_stmt_id)?;

            self.visit_stmt(ctx, block_stmt_id)?;

        }

        section.forget();

        Ok(())

    }

    fn visit_return_stmt(&mut self, ctx: &mut Ctx, id: ReturnStatementId) -> VisitorResult {

        let return_stmt = &ctx.heap[id];

        debug_assert_eq!(return_stmt.expressions.len(), 1);

        let expr_id = return_stmt.expressions[0];

        self.visit_expr(ctx, expr_id)

    }

    fn visit_new_stmt(&mut self, ctx: &mut Ctx, id: NewStatementId) -> VisitorResult {

        let new_stmt = &ctx.heap[id];

        let call_expr_id = new_stmt.expression;

        self.visit_call_expr(ctx, call_expr_id)

    }

    fn visit_expr_stmt(&mut self, ctx: &mut Ctx, id: ExpressionStatementId) -> VisitorResult {

        let expr_stmt = &ctx.heap[id];

        let subexpr_id = expr_stmt.expression;

        self.visit_expr(ctx, subexpr_id)

    }

    // Expressions

    fn visit_assignment_expr(&mut self, ctx: &mut Ctx, id: AssignmentExpressionId) -> VisitorResult {

        let upcast_id = id.upcast();

        self.insert_initial_expr_inference_type(ctx, upcast_id)?;

        let assign_expr = &ctx.heap[id];

        let left_expr_id = assign_expr.left;

        let right_expr_id = assign_expr.right;

        self.visit_expr(ctx, left_expr_id)?;

        self.visit_expr(ctx, right_expr_id)?;

        self.progress_assignment_expr(ctx, id)

    }

    fn visit_binding_expr(&mut self, ctx: &mut Ctx, id: BindingExpressionId) -> VisitorResult {

        let upcast_id = id.upcast();

        self.insert_initial_expr_inference_type(ctx, upcast_id)?;

        let binding_expr = &ctx.heap[id];

        let bound_to_id = binding_expr.bound_to;

        let bound_from_id = binding_expr.bound_from;

        self.visit_expr(ctx, bound_to_id)?;

        self.visit_expr(ctx, bound_from_id)?;

        debug_assert!(var_expr.declaration.is_some());

        // Not pretty: if a binding expression, then this is the first time we

        // encounter the variable, so we still need to insert the variable data.

        let declaration = &ctx.heap[var_expr.declaration.unwrap()];

        if !self.var_types.contains_key(&declaration.this)  {

            debug_assert!(declaration.kind == VariableKind::Binding);

            let var_type = self.determine_inference_type_from_parser_type_elements(

                &declaration.parser_type.elements, true

            );

            self.var_types.insert(declaration.this, VarData{

                var_type,

                used_at: vec![upcast_id],

                linked_var: None

            });

        } else {

            let var_data = self.var_types.get_mut(&declaration.this).unwrap();

            var_data.used_at.push(upcast_id);

        }

        self.progress_variable_expr(ctx, id)

    }

}

impl PassTyping {

    #[allow(dead_code)] // used when debug flag at the top of this file is true.

    fn debug_get_display_name(&self, ctx: &Ctx, expr_id: ExpressionId) -> String {

        let expr_idx = ctx.heap[expr_id].get_unique_id_in_definition();

        let expr_type = &self.expr_types[expr_idx as usize].expr_type;

        expr_type.display_name(&ctx.heap)

    }

    fn resolve_types(&mut self, ctx: &mut Ctx, queue: &mut ResolveQueue) -> Result<(), ParseError> {

        // Keep inferring until we can no longer make any progress

        while !self.expr_queued.is_empty() {

            // Make as much progress as possible without forced integer

            // inference.

            while !self.expr_queued.is_empty() {

                let next_expr_idx = self.expr_queued.pop_front().unwrap();

                self.progress_expr(ctx, next_expr_idx)?;

            }

            // Nothing is queued anymore. However we might have integer literals

            // whose type cannot be inferred. For convenience's sake we'll

            // infer these to be s32.

            for (infer_expr_idx, infer_expr) in self.expr_types.iter_mut().enumerate() {

                let expr_type = &mut infer_expr.expr_type;

                if !expr_type.is_done && expr_type.parts.len() == 1 && expr_type.parts[0] == InferenceTypePart::IntegerLike {

/// Globally configured capacity for small-ish buffers in visitor impls

pub(crate) const BUFFER_INIT_CAP_SMALL: usize = 64;

/// General context structure that is used while traversing the AST.

pub(crate) struct Ctx<'p> {

    pub heap: &'p mut Heap,

    pub modules: &'p mut [Module],

    pub module_idx: usize, // currently considered module

    pub symbols: &'p mut SymbolTable,

    pub types: &'p mut TypeTable,

    pub arch: &'p crate::protocol::TargetArch,

}

impl<'p> Ctx<'p> {

    /// Returns module `modules[module_idx]`

    pub(crate) fn module(&self) -> &Module {

        &self.modules[self.module_idx]

    }

    pub(crate) fn module_mut(&mut self) -> &mut Module {

        &mut self.modules[self.module_idx]

    }

}

            Statement::Block(stmt) => {

                let this = stmt.this;

            },

            Statement::Local(stmt) => {

                let this = stmt.this();

            },

            Statement::Labeled(stmt) => {

                let this = stmt.this;

            },

            Statement::If(stmt) => {

                let this = stmt.this;

            },

            Statement::While(stmt) => {

                let this = stmt.this;

            },

            Statement::Break(stmt) => {

                let this = stmt.this;

            },

            Statement::Continue(stmt) => {

                let this = stmt.this;

            },

            Statement::Synchronous(stmt) => {

                let this = stmt.this;

            },

            Statement::Fork(stmt) => {

                let this = stmt.this;

            },

            Statement::Select(stmt) => {

                let this = stmt.this;

            },

            Statement::Return(stmt) => {

                let this = stmt.this;

            },

            Statement::Goto(stmt) => {

                let this = stmt.this;

            },

            Statement::New(stmt) => {

                let this = stmt.this;

            },

            Statement::Expression(stmt) => {

                let this = stmt.this;

            }

        }

    }

            },

            },

        }

    }

            Expression::Assignment(expr) => {

                let this = expr.this;

            },

            Expression::Binding(expr) => {

                let this = expr.this;

            Expression::Conditional(expr) => {

                let this = expr.this;

            Expression::Binary(expr) => {

                let this = expr.this;

            Expression::Unary(expr) => {

                let this = expr.this;

            Expression::Indexing(expr) => {

                let this = expr.this;

            Expression::Slicing(expr) => {

                let this = expr.this;

            Expression::Select(expr) => {

                let this = expr.this;

            Expression::Literal(expr) => {

                let this = expr.this;

            Expression::Cast(expr) => {

                let this = expr.this;

            Expression::Call(expr) => {

                let this = expr.this;

            Expression::Variable(expr) => {

                let this = expr.this;

        }