}

    #[inline]

    pub(crate) fn contains(&self, value: &T) -> bool {

        self.check_length();

        let vec = unsafe{&*self.inner};

                return true;

            }

        }

        return false;

    }

    };

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

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

    };

}

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

// -----------------------------------------------------------------------------

// PassTyping - Public Interface

// -----------------------------------------------------------------------------

type InferNodeIndex = usize;

type VarDataIndex = usize;

enum DefinitionType{

    Component(ComponentDefinitionId),

    Function(FunctionDefinitionId),

}

    pub(crate) definition_id: DefinitionId,

    pub(crate) reserved_type_id: TypeId,

}

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

struct InferenceNode {

    expr_type: InferenceType,       // result type from expression

    expr_id: ExpressionId,          // expression that is evaluated

    inference_rule: InferenceRule,

    parent_index: Option<InferNodeIndex>,

    field_or_monomorph_index: i32,    // index of field

    union_cast_method_impl!(as_literal_tuple, InferenceRuleLiteralTuple, InferenceRule::LiteralTuple);

    union_cast_method_impl!(as_cast_expr, InferenceRuleCastExpr, InferenceRule::CastExpr);

    union_cast_method_impl!(as_call_expr, InferenceRuleCallExpr, InferenceRule::CallExpr);

    union_cast_method_impl!(as_variable_expr, InferenceRuleVariableExpr, InferenceRule::VariableExpr);

}

struct InferenceRuleTemplate {

    template: &'static [InferenceTypePart],

    application: InferenceRuleTemplateApplication,

}

impl InferenceRuleTemplate {

struct PolyData {

    first_rule_application: bool,

    definition_id: DefinitionId, // the definition, only used for user feedback

    /// Inferred types of the polymorphic variables as they are written down

    /// at the type's definition.

    poly_vars: Vec<InferenceType>,

    /// Inferred types of associated types (e.g. struct fields, tuple members,

    /// function arguments). These types may depend on the polymorphic variables

    /// defined above.

    associated: Vec<InferenceType>,

    /// Inferred "returned" type (e.g. if a struct field is selected, then this

    /// contains the type of the selected field, for a function call it contains

#[derive(Clone, Copy)]

enum PolyDataTypeIndex {

    Associated(usize), // indexes into `PolyData.associated`

    Returned,

}

    fn get_type(&self, index: PolyDataTypeIndex) -> &InferenceType {

        match index {

            PolyDataTypeIndex::Associated(index) => return &self.associated[index],

            PolyDataTypeIndex::Returned => return &self.returned,

        }

    }

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

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

                let _infer_type = InferenceType::new(false, true, infer_type_parts);

                debug_log!(" - [{:03}] {:?}", _idx, _infer_type.display_name(&ctx.heap));

            }

        }

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

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

                    expr_indices.push(expr_index);

                }

                expr_ids.forget();

                let element_indices = expr_indices.into_vec();

                // Assign rule and extra data index to inference node

                let node = &mut self.infer_nodes[self_index];

                node.inference_rule = InferenceRule::LiteralStruct(InferenceRuleLiteralStruct{

                    element_indices,

                });

            },

            Literal::Enum(_) => {

                // Enumerations do not carry any subexpressions, but may still

                // have a user-defined polymorphic marker variable. For this 

                // reason we may still have to apply inference to this 

                // polymorphic variable

                let node = &mut self.infer_nodes[self_index];

                node.inference_rule = InferenceRule::LiteralEnum;

            },

            Literal::Union(literal) => {

                // May carry subexpressions and polymorphic arguments

                let expr_ids = self.expr_buffer.start_section_initialized(literal.values.as_slice());

                let mut expr_indices = self.index_buffer.start_section();

                for expr_id in expr_ids.iter_copied() {

                    let expr_index = self.visit_expr(ctx, expr_id)?;

                    expr_indices.push(expr_index);

                }

                expr_ids.forget();

                let element_indices = expr_indices.into_vec();

                let node = &mut self.infer_nodes[self_index];

                node.inference_rule = InferenceRule::LiteralUnion(InferenceRuleLiteralUnion{

                    element_indices,

                });

            },

                let expr_ids = self.expr_buffer.start_section_initialized(expressions.as_slice());

                for expr_id in expr_ids.iter_copied() {

                    let expr_index = self.visit_expr(ctx, expr_id)?;

                    expr_indices.push(expr_index);

                }

                expr_ids.forget();

                let element_indices = expr_indices.into_vec();

                let node = &mut self.infer_nodes[self_index];

                node.inference_rule = InferenceRule::LiteralArray(InferenceRuleLiteralArray{

                    element_indices,

                })

            }

        }

        self.parent_index = old_parent;

        self.progress_inference_rule(ctx, self_index)?;

        // The cast expression is a bit special at this point: the progression

        // function simply makes sure input/output types are compatible. But if

        // the programmer explicitly specified the output type, then we can

        // already perform that inference rule here.

        {

            let specified_type = self.determine_inference_type_from_parser_type_elements(&cast_expr.to_type.elements, true);

            let _progress = self.apply_template_constraint(ctx, self_index, &specified_type.parts)?;

        }

        self.progress_inference_rule_cast_expr(ctx, self_index)?;

        return Ok(self_index);

        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.node_queued.is_empty() {

            while !self.node_queued.is_empty() {

            }

            // 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_node_index, infer_node) in self.infer_nodes.iter_mut().enumerate() {

                    // Force integer type to s32

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

                    expr_type.is_done = true;

                    // Requeue expression (and its parent, if it exists)

                    self.node_queued.push_back(infer_node_index);

                    }

                }

            }

        }

        // Helper for transferring polymorphic variables to concrete types and

                        infer_expr.expr_type.display_name(&ctx.heap)

                    )

                ));

            }

            // Expression is fine, check if any extra data is attached

            // Extra data is attached, perform typechecking and transfer

            // resolved information to the expression

            // Note that only call and literal expressions need full inference.

            // Select expressions also use `extra_data`, but only for temporary

            // storage of the struct type whose field it is selecting.

                Expression::Call(expr) => {

                    // Check if it is not a builtin function. If not, then

                    // construct the first part of the concrete type.

                    let first_concrete_part = if expr.method == Method::UserFunction {

                    } else if expr.method == Method::UserComponent {

                    } else {

                        // Builtin function

                        continue;

                    };

                    let definition_id = expr.definition;

                    let concrete_type = inference_type_to_concrete_type(

                    )?;

                    match ctx.types.get_procedure_monomorph_type_id(&definition_id, &concrete_type.parts) {

                        Some(type_id) => {

                            // Already typechecked, or already put into the resolve queue

                            infer_expr.type_id = type_id;

                    let definition_id = match &expr.value {

                        Literal::Enum(lit) => lit.definition,

                        Literal::Union(lit) => lit.definition,

                        Literal::Struct(lit) => lit.definition,

                        _ => unreachable!(),

                    };

                    let concrete_type = inference_type_to_concrete_type(

                    )?;

                    let type_id = ctx.types.add_monomorphed_type(ctx.modules, ctx.heap, ctx.arch, definition_id, concrete_type)?;

                    infer_expr.type_id = type_id;

                },

                Expression::Select(_) => {

                    debug_assert!(infer_expr.field_or_monomorph_index >= 0);

                },

                _ => {

                }

            }

        }

        // Every expression checked, and new monomorphs are queued. Transfer the

        // expression information to the type table.

                self.progress_inference_rule_variable_expr(ctx, node_index),

        }

    }

    fn progress_inference_rule_mono_template(&mut self, ctx: &Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> {

        let node = &self.infer_nodes[node_index];

        let progress = self.progress_template(ctx, node_index, rule.application, rule.template)?;

        if progress { self.queue_node_parent(node_index); }

        return Ok(());

    }

    fn progress_inference_rule_bi_equal(&mut self, ctx: &Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> {

        let node = &self.infer_nodes[node_index];

        let rule = node.inference_rule.as_bi_equal();

        let arg_index = rule.argument_index;

        let (node_progress, arg_progress) = self.apply_equal2_constraint(ctx, node_index, node_index, 0, arg_index, 0)?;

        if base_progress || node_progress { self.queue_node_parent(node_index); }

        if arg_progress { self.queue_node(arg_index); }

        return Ok(())

    }

    fn progress_inference_rule_tri_equal_args(&mut self, ctx: &Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> {

        let node = &self.infer_nodes[node_index];

        let rule = node.inference_rule.as_tri_equal_args();

        let arg1_index = rule.argument1_index;

        let arg2_index = rule.argument2_index;

        let (arg1_progress, arg2_progress) = self.apply_equal2_constraint(ctx, node_index, arg1_index, 0, arg2_index, 0)?;

        if self_template_progress { self.queue_node_parent(node_index); }

        if arg1_template_progress || arg1_progress { self.queue_node(arg1_index); }

        return Ok(());

    }

    fn progress_inference_rule_tri_equal_all(&mut self, ctx: &Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> {

        let node = &self.infer_nodes[node_index];

        let rule = node.inference_rule.as_tri_equal_all();

        let arg1_index = rule.argument1_index;

        let arg2_index = rule.argument2_index;

        let (node_progress, arg1_progress, arg2_progress) =

            self.apply_equal3_constraint(ctx, node_index, arg1_index, arg2_index, 0)?;

        if template_progress || node_progress { self.queue_node_parent(node_index); }

        if arg1_progress { self.queue_node(arg1_index); }

        if arg2_progress { self.queue_node(arg2_index); }

        let (expr_is_str, expr_is_not_str) = self.type_is_certainly_or_certainly_not_string(node_index);

        let (arg1_is_str, arg1_is_not_str) = self.type_is_certainly_or_certainly_not_string(arg1_index);

        let (arg2_is_str, arg2_is_not_str) = self.type_is_certainly_or_certainly_not_string(arg2_index);

        let someone_is_str = expr_is_str || arg1_is_str || arg2_is_str;

        let someone_is_not_str = expr_is_not_str || arg1_is_not_str || arg2_is_not_str;

        // Note: this statement is an expression returning the progression bools

        let (node_progress, arg1_progress, arg2_progress) = if someone_is_str {

            // One of the arguments is a string, then all must be strings

            self.apply_equal3_constraint(ctx, node_index, arg1_index, arg2_index, 0)?

        } else {

            let progress_expr = if someone_is_not_str {

        let (from_index_progress, to_index_progress) =

            self.apply_equal2_constraint(ctx, node_index, from_index_index, 0, to_index_index, 0)?;

        // Same as array indexing: result depends on whether subject is string

        // or array

        let (is_string, is_not_string) = self.type_is_certainly_or_certainly_not_string(node_index);

        let (node_progress, subject_progress) = if is_string {

            // Certainly a string

            (

                self.apply_forced_constraint(ctx, node_index, &STRING_TEMPLATE)?,

                false

            )

    fn progress_inference_rule_select_struct_field(&mut self, ctx: &Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> {

        let node = &self.infer_nodes[node_index];

        let rule = node.inference_rule.as_select_struct_field();

        let subject_index = rule.subject_index;

        fn get_definition_id_from_inference_type(inference_type: &InferenceType) -> Result<Option<DefinitionId>, ()> {

            for part in inference_type.parts.iter() {

                if part.is_marker() { continue; }

                if !part.is_concrete() { break; }

                    // Determined definition of subject for the first time.

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

                    let struct_definition = if let DefinedTypeVariant::Struct(struct_definition) = &base_definition.definition {

                        struct_definition

                    } else {

                        return Err(ParseError::new_error_at_span(

                                "Can only apply field access to structs, got a subject of type '{}'",

                            )

                        ));

                    };

                    // Seek the field that is referenced by the select

                    // expression

                    let mut field_found = false;

                    for (field_index, field) in struct_definition.fields.iter().enumerate() {

                            // Found the field of interest

                            field_found = true;

                            let node = &mut self.infer_nodes[node_index];

                            node.field_or_monomorph_index = field_index as i32;

                            break;

                        }

                    }

                    if !field_found {

                        let struct_definition = ctx.heap[definition_id].as_struct();

                        return Err(ParseError::new_error_at_span(

                                "this field does not exist on the struct '{}'",

                            )

                        ));

                    }

                    // Insert the initial data needed to infer polymorphic

                    // fields

                    return Ok(())

                },

                Err(()) => {

                    return Err(ParseError::new_error_at_span(

                        &ctx.module().source, rule.selected_field.span, format!(

                            "Can only apply field access to structs, got a subject of type '{}'",

                        )

                    ));

                },

            }

        }

        let mut selected_member_start_index = 1; // start just after the InferenceTypeElement::Tuple

        for _ in 0..tuple_member_index {

            selected_member_start_index = InferenceType::find_subtree_end_idx(&subject_type.parts, selected_member_start_index);

        }

        let (progress_member, progress_subject) = self.apply_equal2_constraint(

        )?;

        if progress_member { self.queue_node_parent(node_index); }

        if progress_subject { self.queue_node(subject_index); }

        return Ok(());

    }

    fn progress_inference_rule_literal_struct(&mut self, ctx: &Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> {

        let node = &self.infer_nodes[node_index];

        let rule = node.inference_rule.as_literal_struct();

        // For each of the fields in the literal struct, apply the type equality

        // constraint. If the literal is polymorphic, then we try to progress

        // their types during this process

        let mut poly_progress_section = self.poly_progress_buffer.start_section();

            let field_expr_id = self.infer_nodes[field_node_index].expr_id;

            let (_, progress_field) = self.apply_polydata_equal2_constraint(

                ctx, node_index, field_expr_id, "struct field's",

                PolyDataTypeIndex::Associated(field_index), 0,

                field_node_index, 0, &mut poly_progress_section

            )?;

            if progress_field { self.queue_node(field_node_index); }

        }

        // Now we do the same thing for the struct literal expression (the type

        // of the struct itself).

        let (_, progress_literal_1) = self.apply_polydata_equal2_constraint(

            PolyDataTypeIndex::Returned, 0, node_index, 0, &mut poly_progress_section

        )?;

        // And the other way around: if any of our polymorphic variables are

        // more specific then they were before, then we forward that information

        // back to our struct/fields.

            let progress_field = self.apply_polydata_polyvar_constraint(

                ctx, node_index, PolyDataTypeIndex::Associated(field_index),

                field_node_index, &poly_progress_section

            );

            if progress_field { self.queue_node(field_node_index); }

            node_index, &poly_progress_section

        );

        if progress_literal_1 || progress_literal_2 { self.queue_node_parent(node_index); }

        poly_progress_section.forget();

        self.finish_polydata_constraint(node_index);

        return Ok(())

    }

    fn progress_inference_rule_literal_enum(&mut self, ctx: &Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> {

        let node = &self.infer_nodes[node_index];

        let mut poly_progress_section = self.poly_progress_buffer.start_section();

        // An enum literal type is simply, well, the enum's type. However, it

        // might still have polymorphic variables, hence the use of `PolyData`.

        let (_, progress_literal_1) = self.apply_polydata_equal2_constraint(

            PolyDataTypeIndex::Returned, 0, node_index, 0, &mut poly_progress_section

        )?;

        let progress_literal_2 = self.apply_polydata_polyvar_constraint(

            ctx, node_index, PolyDataTypeIndex::Returned, node_index, &poly_progress_section

        );

        self.finish_polydata_constraint(node_index);

        return Ok(());

    }

    fn progress_inference_rule_literal_union(&mut self, ctx: &Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> {

        let node = &self.infer_nodes[node_index];

        let rule = node.inference_rule.as_literal_union();

        // Infer type of any embedded values in the union variant. At the same

        // time progress the polymorphic variables associated with the union.

        let mut poly_progress_section = self.poly_progress_buffer.start_section();

            let embedded_node_expr_id = self.infer_nodes[embedded_node_index].expr_id;

            let (_, progress_embedded) = self.apply_polydata_equal2_constraint(

                ctx, node_index, embedded_node_expr_id, "embedded value's",

                PolyDataTypeIndex::Associated(embedded_index), 0,

                embedded_node_index, 0, &mut poly_progress_section

            )?;

            if progress_embedded { self.queue_node(embedded_node_index); }

        }

        let (_, progress_literal_1) = self.apply_polydata_equal2_constraint(

            PolyDataTypeIndex::Returned, 0, node_index, 0, &mut poly_progress_section

        )?;

        // Propagate progress in the polymorphic variables to the expressions

        // that constitute the union literal.

            let progress_embedded = self.apply_polydata_polyvar_constraint(

                ctx, node_index, PolyDataTypeIndex::Associated(embedded_index),

                embedded_node_index, &poly_progress_section

            );

            if progress_embedded { self.queue_node(embedded_node_index); }

            progress_literal = progress_literal || progress_literal_inner;

            // It is possible that the `Array<T>` has a more progress `T` then

            // the arguments. So in the case we progress our argument type we

            // simply queue this rule again

        }

        argument_node_indices.forget();

        argument_progress_section.forget();

        if progress_literal { self.queue_node_parent(node_index); }

            progress_literal = progress_literal || progress_literal_element;

            if progress_element {

                self.queue_node(element_node_index);

            }

            // Prepare for next element

            let subtree_end_index = InferenceType::find_subtree_end_idx(&node.expr_type.parts, element_subtree_start_index);

            element_subtree_start_index = subtree_end_index;

        }

        if progress_literal { self.queue_node_parent(node_index); }

        element_indices.forget();

        return Ok(());

    }

                if !part.is_marker() { break; }

                index += 1;

            }

            debug_assert!(index != parts.len());

            let part = &parts[index];

                debug_assert!(index + 1 == parts.len()); // type is done, first part does not have children -> must be at end

                return true;

            } else {

                return false;

            }

        }

        if !is_valid {

            let cast_expr = &ctx.heap[node.expr_id];

            let subject_expr = &ctx.heap[subject.expr_id];

            return Err(ParseError::new_error_str_at_span(

                &ctx.module().source, cast_expr.full_span(), "invalid casting operation"

            ).with_info_at_span(

                    "cannot cast the argument type '{}' to the type '{}'",

                    subject.expr_type.display_name(&ctx.heap),

                    node.expr_type.display_name(&ctx.heap)

                )

            ));

        }

        return Ok(())

    }

    fn progress_inference_rule_call_expr(&mut self, ctx: &Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> {

        let node = &self.infer_nodes[node_index];

        let rule = node.inference_rule.as_call_expr();

        let mut poly_progress_section = self.poly_progress_buffer.start_section();

        let argument_node_indices = self.index_buffer.start_section_initialized(&rule.argument_indices);

        // Perform inference on arguments to function, while trying to figure

            )?;

            if progress_argument { self.queue_node(argument_node_index); }

        }

        // Same for the return type.

        let (_, progress_call_1) = self.apply_polydata_equal2_constraint(

            PolyDataTypeIndex::Returned, 0,

            node_index, 0, &mut poly_progress_section

        )?;

        // We will now apply any progression in the polymorphic variable type

        // back to the arguments.

    }

    fn progress_inference_rule_variable_expr(&mut self, ctx: &Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> {

        let node = &mut self.infer_nodes[node_index];

        let rule = node.inference_rule.as_variable_expr();

        let var_data_index = rule.var_data_index;

        // Apply inference to the shared variable type and the expression type

        let shared_type: *mut _ = &mut var_data.var_type;

        let expr_type: *mut _ = &mut node.expr_type;

        let inference_result = unsafe {

            // safety: vectors exist in different storage vectors, so cannot alias

        if progress_var_data {

            // We progressed the type of the shared variable, so propagate this

            // to all associated variable expressions (and relatived variables).

            for other_node_index in var_data.used_at.iter().copied() {

                if other_node_index != node_index {

                }

            }

            if let Some(linked_var_data_index) = var_data.linked_var {

                // Only perform one-way inference, progressing the linked

                // variable.

                    &mut linked_var_data.var_type, 1,

                    unsafe{ &(*this_var_type).parts }, 1, false

                );

                match inference_result {

                    SingleInferenceResult::Modified => {

                        for used_at in linked_var_data.used_at.iter().copied() {

                        }

                    },

                    SingleInferenceResult::Unmodified => {},

                    SingleInferenceResult::Incompatible => {

                        let var_data_this = &self.var_data[var_data_index];

                        let var_decl_this = &ctx.heap[var_data_this.var_id];

    }

    /// Returns whether the type is certainly a string (true, false), certainly

    /// not a string (false, true), or still unknown (false, false).

    fn type_is_certainly_or_certainly_not_string(&self, node_index: InferNodeIndex) -> (bool, bool) {

        let expr_type = &self.infer_nodes[node_index].expr_type;

                return (true, false);

            } else {

                return (false, true);

            }

        }

        (false, false)

    }

    /// Applies a template type constraint: the type associated with the

    /// supplied expression will be molded into the provided `template`. But

    /// will be considered valid if the template could've been molded into the

        outer_node_index: InferNodeIndex, error_location_expr_id: ExpressionId, error_type_name: &str,

        poly_data_type_index: PolyDataTypeIndex, poly_data_start_index: usize,

        associated_node_index: InferNodeIndex, associated_node_start_index: usize,

        poly_progress_section: &mut ScopedSection<u32>,

    ) -> Result<(bool, bool), ParseError> {

        let poly_data_index = self.infer_nodes[outer_node_index].poly_data_index;

        let associated_type: *mut _ = &mut self.infer_nodes[associated_node_index].expr_type;

        let inference_result = unsafe{

            // Safety: pointers originate from different vectors, so cannot

            // alias.

            let poly_data_type: *mut _ = poly_data_type;

            debug_assert!(poly_data_type.has_marker);

            // Go through markers for polymorphic variables and use the

            // (hopefully) more specific types to update their representation

            // in the PolyData struct

            for (poly_var_index, poly_var_section) in poly_data_type.marker_iter() {