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

        self.check_length();

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

                return true;

            }

        }

    };

}

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

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

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

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

type InferNodeIndex = usize;

type VarDataIndex = usize;

enum DefinitionType{

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

struct InferenceNode {

    expr_type: InferenceType,       // result type from expression

    expr_id: ExpressionId,          // expression that is evaluated

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

}

struct InferenceRuleTemplate {

    template: &'static [InferenceTypePart],

    application: InferenceRuleTemplateApplication,

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

    Returned,

}

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

        match index {

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

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

        }

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

                });

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

                let element_indices = expr_indices.into_vec();

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

                node.inference_rule = InferenceRule::LiteralArray(InferenceRuleLiteralArray{

                    element_indices,

                })

            }

        }

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

        }

    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

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

                    self.node_queued.push_back(infer_node_index);

                    }

                }

            }

            }

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

                        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;

                    debug_assert!(infer_expr.field_or_monomorph_index >= 0);

                },

                _ => {

                }

            }

        }

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

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

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

        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

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

            (

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

                        struct_definition

                    } else {

                        return Err(ParseError::new_error_at_span(

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

                            )

                        ));

                    };

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

                    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 '{}'",

                            )

                        ));

                    }

                    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 (progress_member, progress_subject) = self.apply_equal2_constraint(

        )?;

        if progress_member { self.queue_node_parent(node_index); }

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

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

        )?;

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

        }

        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

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

            }

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

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

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

        }

        // Same for the return type.

        let (_, progress_call_1) = self.apply_polydata_equal2_constraint(

            PolyDataTypeIndex::Returned, 0,

            node_index, 0, &mut poly_progress_section

        )?;

        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;

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

                }

            }

                match inference_result {

                    SingleInferenceResult::Modified => {

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

                        }

                    },

                    SingleInferenceResult::Unmodified => {},

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

    }

        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{

            // (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() {

                match InferenceType::infer_subtree_for_single_type(poly_var_type, 0, poly_var_section, 0, false) {

                    SingleInferenceResult::Modified => {

                        poly_progress_section.push_unique(poly_var_index);

                    },

                    SingleInferenceResult::Incompatible => {

                        return Err(Self::construct_poly_arg_error(

                            self.infer_nodes[outer_node_index].expr_id

                        ));

                    }

        associated_node_index: InferNodeIndex, poly_progress_section: &ScopedSection<u32>

    ) -> bool {

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

        // Early exit, most common case (literals or functions calls which are

        // actually not polymorphic)

        }

        // safety: we're borrowing from two distinct fields, so should be fine

        let mut last_start_index = 0;

        let mut modified_poly_type = false;

    /// constraints.

    fn finish_polydata_constraint(&mut self, outer_node_index: InferNodeIndex) {

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

        poly_data.first_rule_application = false;

    }

            inference_rule: InferenceRule::Noop,

            parent_index: self.parent_index,

            field_or_monomorph_index: -1,

            type_id: TypeId::new_invalid(),

        });

            first_rule_application: true,

            definition_id: call.definition,

            poly_vars: poly_args,

        });

        return extra_data_idx

    }

            first_rule_application: true,

            definition_id: literal.definition,

            poly_vars: poly_args,

        });

        return extra_data_index

            first_rule_application: true,

            definition_id: literal.definition,

            poly_vars: poly_args,

        });

        return extra_data_index;

        debug_assert_eq!(parts_reserved, parts.len());

        let union_type = InferenceType::new(!poly_args.is_empty(), union_type_done, parts);

        self.poly_data.push(PolyData {

            first_rule_application: true,

            definition_id: literal.definition,

            poly_vars: poly_args,

        });

        return extra_data_index;

            first_rule_application: true,

            definition_id: struct_def_id,

            poly_vars,

        });

        return extra_data_index;

        // - check return type with itself

        if let Some((poly_idx, section_a, section_b)) = has_poly_mismatch(

        ) {

            return construct_main_error(ctx, poly_data, poly_idx, expr)

                .with_info_at_span(

        }

        // - check arguments with each other argument and with return type

                if arg_b_idx > arg_a_idx {

                    break;

                }

            }

            // Check with return type

                let arg = &ctx.heap[expr_args[arg_a_idx]];

                return construct_main_error(ctx, poly_data, poly_idx, expr)

                    .with_info_at_span(

        // Now check against the explicitly specified polymorphic variables (if

        // any).

            if let Some((poly_idx, poly_section, arg_section)) = has_explicit_poly_mismatch(&poly_data.poly_vars, arg) {

                let arg = &ctx.heap[expr_args[arg_idx]];

                return construct_main_error(ctx, poly_data, poly_idx, expr)

            }

        }

            return construct_main_error(ctx, poly_data, poly_idx, expr)

                .with_info_at_span(

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

        "

    ).error(|e| { e

        .assert_occurs_at(0, "Foo::A")

        .assert_occurs_at(1, "false")

        .assert_msg_has(1, "has been resolved to 's32'")

        .assert_msg_has(1, "has been resolved to 'bool'");