use std::collections::VecDeque;

/// Simple double ended queue that ensures that all elements are unique. Queue

pub struct DequeSet<T: Eq> {

    inner: VecDeque<T>,

}

impl<T: Eq> DequeSet<T> {

    pub fn new() -> Self {

        Self{ inner: VecDeque::new() }

    }

    #[inline]

    pub fn pop_front(&mut self) -> Option<T> {

        self.inner.pop_front()

    #[inline]

    pub fn push_front(&mut self, to_push: T) {

        for element in self.inner.iter() {

            if *element == to_push {

                return;

            }

        }

        self.inner.push_front(to_push);

    }

    #[inline]

    pub fn is_empty(&self) -> bool {

        self.inner.is_empty()

    }

}

        use ParserTypeVariant::*;

        match self {

            Void | IntegerLike |

            Message | Bool |

            UInt8 | UInt16 | UInt32 | UInt64 |

            SInt8 | SInt16 | SInt32 | SInt64 |

            Character | String | IntegerLiteral |

            Inferred | PolymorphicArgument(_, _) =>

                0,

            ArrayLike | InputOrOutput | Array | Input | Output =>

                1,

        }

    }

}

#[derive(Debug, Clone)]

pub struct ParserTypeElement {

    // TODO: @cleanup, do we ever need the span of a user-defined type after

    //  constructing it?

    pub full_span: InputSpan, // full span of type, including any polymorphic arguments

    pub variant: ParserTypeVariant,

}

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

pub struct ConcreteType {

    pub(crate) parts: Vec<ConcreteTypePart>

}

impl Default for ConcreteType {

    fn default() -> Self {

        Self{ parts: Vec::new() }

    }

}

// TODO: Remove at some point

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

pub enum PrimitiveType {

    Unassigned,

    Input,

    Output,

    Message,

    Boolean,

    Byte,

    Short,

    Int,

    Long,

                target.push('<');

                element_idx = write_element(target, heap, t, element_idx + 1);

                target.push('>');

            },

            PTV::Output => {

                target.push_str(KW_TYPE_OUT_PORT_STR);

                target.push('<');

                element_idx = write_element(target, heap, t, element_idx + 1);

                target.push('>');

            },

            PTV::PolymorphicArgument(definition_id, arg_idx) => {

                let definition = &heap[*definition_id];

                target.push_str(poly_var.as_str());

            },

            PTV::Definition(definition_id, num_embedded) => {

                let definition = &heap[*definition_id];

                let definition_ident = definition.identifier().value.as_str();

                target.push_str(definition_ident);

                let num_embedded = *num_embedded;

                if num_embedded != 0 {

                    target.push('<');

                    for embedded_idx in 0..num_embedded {

                        if embedded_idx != 0 {

}

// TODO: @Cleanup, this is littered at three places in the codebase

fn write_concrete_type(target: &mut String, heap: &Heap, def_id: DefinitionId, t: &ConcreteType) {

    use ConcreteTypePart as CTP;

    fn write_concrete_part(target: &mut String, heap: &Heap, def_id: DefinitionId, t: &ConcreteType, mut idx: usize) -> usize {

        if idx >= t.parts.len() {

            return idx;

        }

        match &t.parts[idx] {

            CTP::Void => target.push_str("void"),

            CTP::Message => target.push_str("msg"),

            CTP::Bool => target.push_str("bool"),

            CTP::UInt8 => target.push_str(KW_TYPE_UINT8_STR),

            CTP::UInt16 => target.push_str(KW_TYPE_UINT16_STR),

            CTP::UInt32 => target.push_str(KW_TYPE_UINT32_STR),

            CTP::UInt64 => target.push_str(KW_TYPE_UINT64_STR),

            CTP::SInt8 => target.push_str(KW_TYPE_SINT8_STR),

            CTP::SInt16 => target.push_str(KW_TYPE_SINT16_STR),

            CTP::SInt32 => target.push_str(KW_TYPE_SINT32_STR),

            CTP::SInt64 => target.push_str(KW_TYPE_SINT64_STR),

            CTP::Character => target.push_str(KW_TYPE_CHAR_STR),

    }

    // We need to handle concatenate in a special way because it needs the store

    // mutably.

    if op == BO::Concatenate {

        let target_heap_pos = store.alloc_heap();

        let lhs_heap_pos;

        let rhs_heap_pos;

        let lhs = store.maybe_read_ref(lhs);

        let rhs = store.maybe_read_ref(rhs);

        let value_kind;

        match lhs {

            Value::Message(lhs_pos) => {

                lhs_heap_pos = *lhs_pos;

                rhs_heap_pos = rhs.as_message();

                value_kind = ValueKind::Message;

            },

            Value::String(lhs_pos) => {

                lhs_heap_pos = *lhs_pos;

                rhs_heap_pos = rhs.as_string();

                value_kind = ValueKind::String;

use pass_symbols::PassSymbols;

use pass_imports::PassImport;

use pass_definitions::PassDefinitions;

use pass_validation_linking::PassValidationLinking;

use pass_typing::{PassTyping, ResolveQueue};

use symbol_table::*;

use type_table::TypeTable;

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

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

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

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

pub enum ModuleCompilationPhase {

    Source,                 // only source is set

    Tokenized,              // source is tokenized

    SymbolsScanned,         // all definitions are linked to their type class

    ImportsResolved,        // all imports are added to the symbol table

    DefinitionsParsed,      // produced the AST for the entire module

    TypesAddedToTable,      // added all definitions to the type table

    ValidatedAndLinked,     // AST is traversed and has linked the required AST nodes

    Typed,                  // Type inference and checking has been performed

}

    let func_ident_ref = p.string_pool.intern(func_name.as_bytes());

    let func_id = p.heap.alloc_function_definition(|this| FunctionDefinition{

        this,

        defined_in: RootId::new_invalid(),

        builtin: true,

        span: InputSpan::new(),

        identifier: Identifier{ span: InputSpan::new(), value: func_ident_ref.clone() },

        poly_vars,

        return_types: Vec::new(),

        parameters: Vec::new(),

        body: BlockStatementId::new_invalid(),

    });

    let (args, ret) = arg_and_return_fn(func_id);

    let mut parameters = Vec::with_capacity(args.len());

    for (arg_name, arg_type) in args {

        let identifier = Identifier{ span: InputSpan::new(), value: p.string_pool.intern(arg_name.as_bytes()) };

        let param_id = p.heap.alloc_variable(|this| Variable{

            this,

            kind: VariableKind::Parameter,

            parser_type: arg_type.clone(),

            identifier,

///     to a fires() call must be port-like), only then to start progressing the

///     types.

///     Furthermore, queueing of expressions can be more intelligent, currently

///     every child/parent of an expression is inferred again when queued. Hence

///     we need to queue only specific children/parents of expressions.

///  3. Remove the `msg` type?

///  4. Disallow certain types in certain operations (e.g. `Void`).

///  5. Implement implicit and explicit casting.

///  6. Investigate different ways of performing the type-on-type inference,

///     maybe there is a better way then flattened trees + markers?

macro_rules! debug_log_enabled {

}

macro_rules! debug_log {

    ($format:literal) => {

    };

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

    };

}

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

use crate::collections::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::{

    STMT_BUFFER_INIT_CAPACITY,

    EXPR_BUFFER_INIT_CAPACITY,

    Ctx,

    Visitor2,

    VisitorResult

};

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; 1] = [ InferenceTypePart::String ];

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

            CTP::SInt64 => ITP::SInt64,

            CTP::Character => ITP::Character,

            CTP::String => ITP::String,

            CTP::Array => ITP::Array,

            CTP::Slice => ITP::Slice,

            CTP::Input => ITP::Input,

            CTP::Output => ITP::Output,

            CTP::Instance(id, num) => ITP::Instance(id, num),

        }

    }

}

struct InferenceType {

    has_marker: bool,

    is_done: bool,

    parts: Vec<InferenceTypePart>,

}

impl InferenceType {

    /// Generates a new InferenceType. The two boolean flags will be checked in

    /// debug mode.

    fn new(has_marker: bool, is_done: bool, parts: Vec<InferenceTypePart>) -> Self {

        if cfg!(debug_assertions) {

            debug_assert!(!parts.is_empty());

        self.parts.splice(start_idx..end_idx, with.iter().cloned());

        self.recompute_is_done();

    }

    // TODO: @performance, might all be done inline in the type inference methods

    fn recompute_is_done(&mut self) {

        self.is_done = self.parts.iter().all(|v| v.is_concrete());

    }

    /// Seeks a body marker starting at the specified position. If a marker is

    /// found then its value and the index of the type subtree that follows it

    /// is returned.

        while start_idx < self.parts.len() {

                return Some((*marker, start_idx + 1))

            }

            start_idx += 1;

        }

        None

    }

    /// Returns an iterator over all body markers and the partial type tree that

    /// follows those markers. If it is a problem that `InferenceType` is 

    /// borrowed by the iterator, then use `find_body_marker`.

            to_infer.parts[*to_infer_idx] = template_part.clone();

            *to_infer_idx += 1;

            *template_idx += 1;

            return Some(depth_change);

        }

        // Inference of a completely unknown type

        if *to_infer_part == ITP::Unknown {

            // template part is different, so cannot be unknown, hence copy the

            // entire subtree. Make sure not to copy markers.

            let template_end_idx = Self::find_subtree_end_idx(template_parts, *template_idx);

                let template_part = &template_parts[template_idx];

                if !template_part.is_marker() {

                    to_infer.parts.insert(*to_infer_idx, template_part.clone());

                    *to_infer_idx += 1;

                }

            }

            *template_idx = template_end_idx;

            // Note: by definition the LHS was Unknown and the RHS traversed a 

            // full subtree.

            return Some(-1);

        }

    }

}

#[derive(PartialEq, Eq)]

pub(crate) struct ResolveQueueElement {

    pub(crate) root_id: RootId,

    pub(crate) definition_id: DefinitionId,

    pub(crate) monomorph_types: Vec<ConcreteType>,

}

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

struct InferenceExpression {

    expr_type: InferenceType,       // result type from expression

    expr_id: ExpressionId,          // expression that is evaluated

    field_or_monomorph_idx: i32,    // index of field, of index of monomorph array in type table

    var_or_extra_data_idx: i32,     // index of extra data needed for inference

}

impl Default for InferenceExpression {

    fn default() -> Self {

        Self{

            expr_type: InferenceType::default(),

            expr_id: ExpressionId::new_invalid(),

    // specify these types until we're stuck or we've fully determined the type.

    var_types: HashMap<VariableId, VarData>,            // types of variables

    expr_types: Vec<InferenceExpression>,                     // will be transferred to type table at end

    extra_data: Vec<ExtraData>,       // data for polymorph inference

    // Keeping track of which expressions need to be reinferred because the

    // expressions they're linked to made progression on an associated type

    expr_queued: DequeSet<i32>,

}

// TODO: @Rename, this is used for a lot of type inferencing. It seems like

//  there is a different underlying architecture waiting to surface.

struct ExtraData {

    /// Progression of polymorphic variables (if any)

    poly_vars: Vec<InferenceType>,

    /// Progression of types of call arguments or struct members

    embedded: Vec<InferenceType>,

    returned: InferenceType,

}

impl Default for ExtraData {

    fn default() -> Self {

        Self{

            poly_vars: Vec::new(),

            embedded: Vec::new(),

            returned: InferenceType::default(),

        }

    }

}

struct VarData {

    /// Type of the variable

    var_type: InferenceType,

    /// VariableExpressions that use the variable

    used_at: Vec<ExpressionId>,

        let upcast_id = id.upcast();

        self.insert_initial_expr_inference_type(ctx, upcast_id)?;

        let var_expr = &ctx.heap[id];

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

        let var_data = self.var_types.get_mut(var_expr.declaration.as_ref().unwrap()).unwrap();

        var_data.used_at.push(upcast_id);

        self.progress_variable_expr(ctx, id)

    }

}

impl PassTyping {

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

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

        }

        // We check if we have all the types we need. If we're typechecking a 

        // polymorphic procedure more than once, then we have already annotated

        // the AST and have now performed typechecking for a different 

        // monomorph. In that case we just need to perform typechecking, no need

        // to annotate the AST again.

        let definition_id = match &self.definition_type {

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

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

        };

        let already_checked = ctx.types.get_base_definition(&definition_id).unwrap().has_any_monomorph();

            if !expr_type.is_done {

                // Auto-infer numberlike/integerlike types to a regular int

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

                    expr_type.parts[0] = InferenceTypePart::SInt32;

                } else {

                    return Err(ParseError::new_error_at_span(

                        &ctx.module.source, expr.span(), format!(

                            "could not fully infer the type of this expression (got '{}')",

                            expr_type.display_name(&ctx.heap)

                        )

                    ));

                }

            }

            if !already_checked {

                expr_type.write_concrete_type(concrete_type);

            } else {

                if cfg!(debug_assertions) {

                    let mut concrete_type = ConcreteType::default();

                    expr_type.write_concrete_type(&mut concrete_type);

                }

            }

        }

        // All types are fine

        ctx.types.add_monomorph(&definition_id, self.poly_vars.clone());

        // Check all things we need to monomorphize

        // TODO: Struct/enum/union monomorphization

            if extra_data.poly_vars.is_empty() { continue; }

            // Retrieve polymorph variable specification. Those of struct 

            // literals and those of procedure calls need to be fully inferred.

            // The remaining ones (e.g. select expressions) allow partial 

            // inference of types, as long as the accessed field's type is

            // fully inferred.

                Expression::Call(_) => true,

                Expression::Literal(_) => true,

                _ => false

            };

            if needs_full_inference {

                let mut monomorph_types = Vec::with_capacity(extra_data.poly_vars.len());

                for (poly_idx, poly_type) in extra_data.poly_vars.iter().enumerate() {

                    if !poly_type.is_done {

                        // TODO: Single clean function for function signatures and polyvars.

                        // TODO: Better error message

                        return Err(ParseError::new_error_at_span(

                            &ctx.module.source, expr.span(), format!(

                                "could not fully infer the type of polymorphic variable {} of this expression (got '{}')",

                                poly_idx, poly_type.display_name(&ctx.heap)

                            )

                        ))

                    }

                    let mut concrete_type = ConcreteType::default();

                    poly_type.write_concrete_type(&mut concrete_type);

                    monomorph_types.insert(poly_idx, concrete_type);

                }

                // Resolve to the appropriate expression and instantiate 

                // monomorphs.

                    Expression::Call(call_expr) => {

                        // Add to type table if not yet typechecked

                        if call_expr.method == Method::UserFunction {

                            let definition_id = call_expr.definition;

                            if !ctx.types.has_monomorph(&definition_id, &monomorph_types) {

                                let root_id = ctx.types

                                    .get_base_definition(&definition_id)

                                    .unwrap()

                                    .ast_root;

                                // Pre-emptively add the monomorph to the type table, but

                                // we still need to perform typechecking on it

                        if !ctx.types.has_monomorph(definition_id, &monomorph_types) {

                            ctx.types.add_monomorph(definition_id, monomorph_types);

                        }

                    },

                    _ => unreachable!("needs fully inference, but not a struct literal or call expression")

                }

            } // else: was just a helper structure...

        }

        Ok(())

    }

        match &ctx.heap[id] {

            Expression::Assignment(expr) => {

                let id = expr.this;

                self.progress_assignment_expr(ctx, id)

            },

            Expression::Binding(_expr) => {

                unimplemented!("progress binding expression");

            },

            Expression::Conditional(expr) => {

                let id = expr.this;

                self.progress_conditional_expr(ctx, id)

            },

            Expression::Variable(expr) => {

                let id = expr.this;

                self.progress_variable_expr(ctx, id)

            }

        }

    }

    fn progress_assignment_expr(&mut self, ctx: &mut Ctx, id: AssignmentExpressionId) -> Result<(), ParseError> {

        use AssignmentOperator as AO;

        let upcast_id = id.upcast();

        let expr = &ctx.heap[id];

        let arg1_expr_id = expr.left;

        let arg2_expr_id = expr.right;

        debug_log!("Assignment expr '{:?}': {}", expr.operation, upcast_id.index);

        debug_log!(" * Before:");

        // Apply forced constraint to LHS value

        let progress_forced = match expr.operation {

            AO::Set =>

                false,

            AO::Multiplied | AO::Divided | AO::Added | AO::Subtracted =>

                self.apply_forced_constraint(ctx, arg1_expr_id, &NUMBERLIKE_TEMPLATE)?,

            AO::Remained | AO::ShiftedLeft | AO::ShiftedRight |

            AO::BitwiseAnded | AO::BitwiseXored | AO::BitwiseOred =>

                self.apply_forced_constraint(ctx, arg1_expr_id, &INTEGERLIKE_TEMPLATE)?,

        };

        let (progress_arg1, progress_arg2) = self.apply_equal2_constraint(

            ctx, upcast_id, arg1_expr_id, 0, arg2_expr_id, 0

        )?;

        debug_assert!(if progress_forced { progress_arg2 } else { true });

        debug_log!(" * After:");

        if progress_expr { self.queue_expr_parent(ctx, upcast_id); }

        Ok(())

    }

    fn progress_conditional_expr(&mut self, ctx: &mut Ctx, id: ConditionalExpressionId) -> Result<(), ParseError> {

        // Note: test expression type is already enforced

        let upcast_id = id.upcast();

        let expr = &ctx.heap[id];

        let arg1_expr_id = expr.true_expression;

        let arg2_expr_id = expr.false_expression;

        debug_log!("Conditional expr: {}", upcast_id.index);

        debug_log!(" * Before:");

        let (progress_expr, progress_arg1, progress_arg2) = self.apply_equal3_constraint(

            ctx, upcast_id, arg1_expr_id, arg2_expr_id, 0

        )?;

        debug_log!(" * After:");

        if progress_expr { self.queue_expr_parent(ctx, upcast_id); }

        Ok(())

    }

    fn progress_binary_expr(&mut self, ctx: &mut Ctx, id: BinaryExpressionId) -> Result<(), ParseError> {

        // Note: our expression type might be fixed by our parent, but we still

        // need to make sure it matches the type associated with our operation.

        use BinaryOperator as BO;

        let upcast_id = id.upcast();

        let expr = &ctx.heap[id];

        let arg1_id = expr.left;

        let arg2_id = expr.right;

        debug_log!("Binary expr '{:?}': {}", expr.operation, upcast_id.index);

        debug_log!(" * Before:");

        let (progress_expr, progress_arg1, progress_arg2) = match expr.operation {

            BO::Concatenate => {

                // Arguments may be arrays/slices, output is always an array

                let progress_expr = self.apply_forced_constraint(ctx, upcast_id, &ARRAY_TEMPLATE)?;

                let progress_arg1 = self.apply_forced_constraint(ctx, arg1_id, &ARRAYLIKE_TEMPLATE)?;

                let progress_arg2 = self.apply_forced_constraint(ctx, arg2_id, &ARRAYLIKE_TEMPLATE)?;

                // If they're all arraylike, then we want the subtype to match

                let (subtype_expr, subtype_arg1, subtype_arg2) =

                    self.apply_equal3_constraint(ctx, upcast_id, arg1_id, arg2_id, 1)?;

            },

            BO::Add | BO::Subtract | BO::Multiply | BO::Divide => {

                // All equal of number type

                let progress_base = self.apply_forced_constraint(ctx, upcast_id, &NUMBERLIKE_TEMPLATE)?;

                let (progress_expr, progress_arg1, progress_arg2) =

                    self.apply_equal3_constraint(ctx, upcast_id, arg1_id, arg2_id, 0)?;

                (progress_base || progress_expr, progress_base || progress_arg1, progress_base || progress_arg2)

            },

        };

        debug_log!(" * After:");

        if progress_expr { self.queue_expr_parent(ctx, upcast_id); }

        Ok(())

    }

    fn progress_unary_expr(&mut self, ctx: &mut Ctx, id: UnaryExpressionId) -> Result<(), ParseError> {

        use UnaryOperator as UO;

        let upcast_id = id.upcast();

        let expr = &ctx.heap[id];

        let arg_id = expr.expression;

        debug_log!("Unary expr '{:?}': {}", expr.operation, upcast_id.index);

        debug_log!(" * Before:");

        let (progress_expr, progress_arg) = match expr.operation {

            UO::Positive | UO::Negative => {

                // Equal types of numeric class

                let progress_base = self.apply_forced_constraint(ctx, upcast_id, &NUMBERLIKE_TEMPLATE)?;

                let (progress_expr, progress_arg) =

                    self.apply_equal2_constraint(ctx, upcast_id, upcast_id, 0, arg_id, 0)?;

                (progress_base || progress_expr, progress_base || progress_arg)

            },

            UO::BitwiseNot | UO::PreIncrement | UO::PreDecrement | UO::PostIncrement | UO::PostDecrement => {

                // Equal types of integer class

                (progress_base || progress_expr, progress_base || progress_arg)

            },

            UO::LogicalNot => {

                // Both booleans

                let progress_expr = self.apply_forced_constraint(ctx, upcast_id, &BOOL_TEMPLATE)?;

                let progress_arg = self.apply_forced_constraint(ctx, upcast_id, &BOOL_TEMPLATE)?;

                (progress_expr, progress_arg)

            }

        };

        debug_log!(" * After:");

        if progress_expr { self.queue_expr_parent(ctx, upcast_id); }

        Ok(())

    }

    fn progress_indexing_expr(&mut self, ctx: &mut Ctx, id: IndexingExpressionId) -> Result<(), ParseError> {

        let upcast_id = id.upcast();

        let expr = &ctx.heap[id];

        let subject_id = expr.subject;

        let index_id = expr.index;

        debug_log!("Indexing expr: {}", upcast_id.index);

        debug_log!(" * Before:");

        // Make sure subject is arraylike and index is integerlike

        let progress_subject_base = self.apply_forced_constraint(ctx, subject_id, &ARRAYLIKE_TEMPLATE)?;

        let progress_index = self.apply_forced_constraint(ctx, index_id, &INTEGERLIKE_TEMPLATE)?;

        // Make sure if output is of T then subject is Array<T>

        let (progress_expr, progress_subject) =

            self.apply_equal2_constraint(ctx, upcast_id, upcast_id, 0, subject_id, 1)?;