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.push_front(to_push);

    }

    #[inline]

    pub fn is_empty(&self) -> bool {

        self.inner.is_empty()

    }

}

            SInt8 | SInt16 | SInt32 | SInt64 |

            Character | String | IntegerLiteral |

            Inferred | PolymorphicArgument(_, _) =>

                0,

            ArrayLike | InputOrOutput | Array | Input | Output =>

                1,

        }

    }

}

#[derive(Debug, Clone)]

pub struct ParserTypeElement {

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,

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

    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),

        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();

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

        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 {

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

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

            CTP::Output => ITP::Output,

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

        }

    }

}

struct InferenceType {

    has_marker: bool,

    is_done: bool,

    parts: Vec<InferenceTypePart>,

}

        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;

        }

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

                }

            }

    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

}

    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(),

        }

    }

}

        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)

                            )

                        ))

                    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

            } // 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) => {

    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 =>

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

        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)?;

                (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) =

                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)?;

        debug_log!(" * After:");

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

        Ok(())

    }

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

        let upcast_id = id.upcast();

        let subject_id = expr.subject;

        let from_id = expr.from_index;

        let to_id = expr.to_index;

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

        debug_log!(" * Before:");

        // Make sure subject is arraylike and indices are of equal integerlike

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

        let progress_idx_base = self.apply_forced_constraint(ctx, from_id, &INTEGERLIKE_TEMPLATE)?;

        let (progress_from, progress_to) = self.apply_equal2_constraint(ctx, upcast_id, from_id, 0, to_id, 0)?;

        let progress_expr_base = self.apply_forced_constraint(ctx, upcast_id, &SLICE_TEMPLATE)?;

        let (progress_expr, progress_subject) =

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

        debug_log!(" * After:");

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

        Ok(())

    }

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

        let upcast_id = id.upcast();

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

        debug_log!(" * Before:");

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

        fn determine_inference_type_instance<'a>(types: &'a TypeTable, infer_type: &InferenceType) -> Result<Option<&'a DefinedType>, ()> {

            for part in &infer_type.parts {

                if part.is_marker() || !part.is_concrete() {

                    continue;

                }

            },

            Field::Symbolic(field) => {

                // Retrieve the struct definition id and field index if possible 

                // and not previously determined

                if field.definition.is_none() {

                    // Not yet known, check if we can determine it

                    let type_def = determine_inference_type_instance(&ctx.types, subject_type);

                    match type_def {

                        Ok(Some(type_def)) => {

                            // Subject type is known, check if it is a 

                            // struct and the field exists on the struct

                // If here then field definition and index are known, and the

                // initial type (based on the struct's definition) has been

                // applied.

                // Check to see if we can infer anything about the subject's and

                // the field's polymorphic variables

                let mut poly_progress = HashSet::new();

                // Apply to struct's type

                let signature_type: *mut _ = &mut poly_data.embedded[0];

                let (_, progress_subject) = Self::apply_equal2_signature_constraint(

                    ctx, upcast_id, Some(subject_id), poly_data, &mut poly_progress,

                    signature_type, 0, subject_type, 0

                )?;

                if progress_subject {

                }

                // Apply to field's type

                let signature_type: *mut _ = &mut poly_data.returned;

                let (_, progress_expr) = Self::apply_equal2_signature_constraint(

                    ctx, upcast_id, None, poly_data, &mut poly_progress, 

                    signature_type, 0, expr_type, 0

                )?;

                if progress_expr {

                    if let Some(parent_id) = ctx.heap[upcast_id].parent_expr_id() {

                    }

                }

                // Reapply progress in polymorphic variables to struct's type

                let signature_type: *mut _ = &mut poly_data.embedded[0];

                let progress_subject = Self::apply_equal2_polyvar_constraint(

                    poly_data, &poly_progress, signature_type, subject_type

                );

                let signature_type: *mut _ = &mut poly_data.returned;

                let progress_expr = Self::apply_equal2_polyvar_constraint(

                    poly_data, &poly_progress, signature_type, expr_type

                );

                (progress_subject, progress_expr)

            }

        };

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

        debug_log!(" * After:");

        Ok(())

    }

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

        let upcast_id = id.upcast();

        let expr = &ctx.heap[id];

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

        debug_log!(" * Before:");

        let progress_expr = match &expr.value {

            Literal::Null => {

                self.apply_forced_constraint(ctx, upcast_id, &MESSAGE_TEMPLATE)?

            },

            Literal::Integer(_) => {

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

            },

            Literal::True | Literal::False => {

                self.apply_forced_constraint(ctx, upcast_id, &BOOL_TEMPLATE)?

            },

            Literal::Character(_) => {

            },

            Literal::String(_) => {

            },

            Literal::Struct(data) => {

                for _poly in &extra.poly_vars {

                    debug_log!(" * Poly: {}", _poly.display_name(&ctx.heap));

                }

                let mut poly_progress = HashSet::new();

                debug_assert_eq!(extra.embedded.len(), data.fields.len());

                debug_log!(" * During (inferring types from fields and struct type):");

                // Mutually infer field signature/expression types

                for (field_idx, field) in data.fields.iter().enumerate() {

                    let field_expr_id = field.value;

                    let signature_type: *mut _ = &mut extra.embedded[field_idx];