heap: &mut self.heap,

                modules: &mut self.modules,

                module_idx,

                symbols: &mut self.symbol_table,

                types: &mut self.type_table,

                arch: &self.arch,

            };

            self.pass_validation.visit_module(&mut ctx)?;

        }

        // Perform typechecking on all modules

        let mut queue = ResolveQueue::new();

        for module_idx in 0..self.modules.len() {

            let mut ctx = visitor::Ctx{

                heap: &mut self.heap,

                modules: &mut self.modules,

                module_idx,

                symbols: &mut self.symbol_table,

                types: &mut self.type_table,

                arch: &self.arch,

            };

            self.pass_typing.queue_module_definitions(&mut ctx, &mut queue);

        };

        while !queue.is_empty() {

            let mut ctx = visitor::Ctx{

                heap: &mut self.heap,

                modules: &mut self.modules,

                module_idx: top.root_id.index as usize,

                symbols: &mut self.symbol_table,

                types: &mut self.type_table,

                arch: &self.arch,

            };

            self.pass_typing.handle_module_definition(&mut ctx, &mut queue, top)?;

        }

        // Rewrite nodes in tree, then prepare for execution of code

        for module_idx in 0..self.modules.len() {

            self.modules[module_idx].phase = ModuleCompilationPhase::Typed;

            let mut ctx = visitor::Ctx{

                heap: &mut self.heap,

                modules: &mut self.modules,

                module_idx,

                symbols: &mut self.symbol_table,

                types: &mut self.type_table,

                arch: &self.arch,

            };

            self.pass_rewriting.visit_module(&mut ctx)?;

            self.pass_stack_size.visit_module(&mut ctx)?;

            unique_id_in_scope: 0

        });

        parameters.push(param_id);

    }

    let func = &mut p.heap[procedure_id];

    func.parameters = parameters;

    func.return_type = Some(return_type);

    // Insert into symbol table

    p.symbol_table.insert_symbol(SymbolScope::Global, Symbol{

        name: func_ident_ref,

        variant: SymbolVariant::Definition(SymbolDefinition{

            defined_in_module: RootId::new_invalid(),

            defined_in_scope: SymbolScope::Global,

            definition_span: InputSpan::new(),

            identifier_span: InputSpan::new(),

            imported_at: None,

            class: DefinitionClass::Function,

            definition_id: procedure_id.upcast(),

        })

    }).unwrap();

    // Insert into type table

}

///

/// TODO: Needs a thorough rewrite:

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

///     again and use a normal VecSomething.

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

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

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

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

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

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

macro_rules! debug_log_enabled {

    () => { false };

}

macro_rules! debug_log {

    ($format:literal) => {

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

    };

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

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

    };

}

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

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

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

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

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

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

use super::visitor::{

    BUFFER_INIT_CAP_LARGE,

    BUFFER_INIT_CAP_SMALL,

    Ctx,

};

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

// Inference type

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

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

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

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

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

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

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

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

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

enum SingleInferenceResult {

    Unmodified,

    Modified,

    Incompatible

}

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

// PassTyping - Public Interface

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

type InferNodeIndex = usize;

type PolyDataIndex = isize;

type VarDataIndex = usize;

pub(crate) struct ResolveQueueElement {

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

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

    // the polymorphic arguments to the procedure.

    pub(crate) root_id: RootId,

    pub(crate) definition_id: DefinitionId,

    pub(crate) reserved_type_id: TypeId,

    pub(crate) reserved_monomorph_index: u32,

}

struct InferenceNode {

    // filled in during type inference

    expr_type: InferenceType,               // result type from expression

    expr_id: ExpressionId,                  // expression that is evaluated

    inference_rule: InferenceRule,          // rule used to infer node type

    parent_index: Option<InferNodeIndex>,   // parent of inference node

    field_index: i32,                       // index of struct field or tuple member

    poly_data_index: PolyDataIndex,         // index to inference data for polymorphic types

    // filled in once type inference is done

    info_type_id: TypeId,

    info_variant: ExpressionInfoVariant,

}

impl InferenceNode {

    #[inline]

    fn as_expression_info(&self) -> ExpressionInfo {

        return ExpressionInfo {

            type_id: self.info_type_id,

            variant: self.info_variant

        }

    }

}

            let definition = &ctx.heap[definition_id];

            let first_concrete_part_and_procedure_id = match definition {

                Definition::Procedure(definition) => {

                    if definition.poly_vars.is_empty() {

                        if definition.kind == ProcedureKind::Function {

                            Some((ConcreteTypePart::Function(definition.this, 0), definition.this))

                        } else {

                            Some((ConcreteTypePart::Component(definition.this, 0), definition.this))

                        }

                    } else {

                        None

                    }

                }

                Definition::Enum(_) | Definition::Struct(_) | Definition::Union(_) => None,

            };

            if let Some((first_concrete_part, procedure_id)) = first_concrete_part_and_procedure_id {

                let procedure = &mut ctx.heap[procedure_id];

                let monomorph_index = procedure.monomorphs.len() as u32;

                procedure.monomorphs.push(ProcedureDefinitionMonomorph::new_invalid());

                let concrete_type = ConcreteType{ parts: vec![first_concrete_part] };

                let type_id = ctx.types.reserve_procedure_monomorph_type_id(&definition_id, concrete_type, monomorph_index);

                    root_id,

                    definition_id,

                    reserved_type_id: type_id,

                    reserved_monomorph_index: monomorph_index,

                })

            }

        }

        definitions_section.forget();

    }

    pub(crate) fn handle_module_definition(

        &mut self, ctx: &mut Ctx, queue: &mut ResolveQueue, element: ResolveQueueElement

    ) -> VisitorResult {

        self.reset();

        debug_assert_eq!(ctx.module().root_id, element.root_id);

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

        // Prepare for visiting the definition

        self.reserved_type_id = element.reserved_type_id;

        self.reserved_monomorph_index = element.reserved_monomorph_index;

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

        if proc_base.is_polymorph {

                let num_poly_vars = poly_data.poly_vars.len() as u32;

                let first_part = match expr.method {

                    Method::UserFunction => ConcreteTypePart::Function(procedure_id, num_poly_vars),

                    Method::UserComponent => ConcreteTypePart::Component(procedure_id, num_poly_vars),

                    _ => ConcreteTypePart::Function(procedure_id, num_poly_vars),

                };

                let definition_id = procedure_id.upcast();

                let signature_type = poly_data_type_to_concrete_type(

                    ctx, infer_node.expr_id, &poly_data.poly_vars, first_part

                )?;

                let (type_id, monomorph_index) = if let Some(type_id) = ctx.types.get_procedure_monomorph_type_id(&definition_id, &signature_type.parts) {

                    // Procedure is already typechecked

                    let monomorph_index = ctx.types.get_monomorph(type_id).variant.as_procedure().monomorph_index;

                    (type_id, monomorph_index)

                } else {

                    // Procedure is not yet typechecked, reserve a TypeID and a monomorph index

                    let procedure_to_check = &mut ctx.heap[procedure_id];

                    let monomorph_index = procedure_to_check.monomorphs.len() as u32;

                    procedure_to_check.monomorphs.push(ProcedureDefinitionMonomorph::new_invalid());

                    let type_id = ctx.types.reserve_procedure_monomorph_type_id(&definition_id, signature_type, monomorph_index);

                    (type_id, monomorph_index)

                };

                ExpressionInfoVariant::Procedure(type_id, monomorph_index)

            } else if let Expression::Select(_expr) = expr {

                ExpressionInfoVariant::Select(infer_node.field_index)

            } else {

                ExpressionInfoVariant::Generic

            };

            infer_node.info_type_id = info_type_id;

            infer_node.info_variant = info_variant;

        }

        // Write the types of the arguments

        let procedure = &ctx.heap[self.procedure_id];

        for parameter_id in procedure.parameters.iter().copied() {

            let mut concrete = ConcreteType::default();

            let var_data = self.var_data.iter().find(|v| v.var_id == parameter_id).unwrap();

            var_data.var_type.write_concrete_type(&mut concrete);

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

            monomorph.argument_types.push(type_id)

        }

        // Determine if we have already assigned type indices to the expressions

        // before (the indices that, for a monomorph, can retrieve the type of

        // the expression).

        let has_type_indices = self.reserved_monomorph_index > 0;

        if has_type_indices {

            // already have indices, so resize and then index into it

            debug_assert!(monomorph.expr_info.is_empty());

            monomorph.expr_info.resize(num_infer_nodes, ExpressionInfo::new_invalid());

            for infer_node in self.infer_nodes.iter() {

                let type_index = ctx.heap[infer_node.expr_id].type_index();

                monomorph.expr_info[type_index as usize] = infer_node.as_expression_info();

            }

        } else {

            // no indices yet, need to be assigned in AST

            for infer_node in self.infer_nodes.iter() {

                let type_index = monomorph.expr_info.len();

                monomorph.expr_info.push(infer_node.as_expression_info());

                *ctx.heap[infer_node.expr_id].type_index_mut() = type_index as i32;

            }

        }

        // Push the information into the AST

        let procedure = &mut ctx.heap[self.procedure_id];

        procedure.monomorphs[self.reserved_monomorph_index as usize] = monomorph;

            let (flags, part) = self.parts[index];

            if flags & Self::KEY_IN_USE != 0 {

                part.hash(state);

            }

        }

    }

}

impl PartialEq for MonoSearchKey {

    fn eq(&self, other: &Self) -> bool {

        let mut self_index = 0;

        let mut other_index = 0;

        while self_index < self.parts.len() && other_index < other.parts.len() {

            // Retrieve part and flags

            let (self_bits, _) = self.parts[self_index];

            let (other_bits, _) = other.parts[other_index];

            let self_in_use = (self_bits & Self::KEY_IN_USE) != 0;

            let other_in_use = (other_bits & Self::KEY_IN_USE) != 0;

            // Determine ending indices

            let self_end_index = self.find_end_index(self_index);

            let other_end_index = other.find_end_index(other_index);

            if self_in_use == other_in_use {

                if self_in_use {

                    // Both are in use, so both parts should be equal

                    let delta_self = self_end_index - self_index;

                    let delta_other = other_end_index - other_index;

                    if delta_self != delta_other {

                        // Both in use, but not of equal length, so the types

                        // cannot match

                        return false;

                    }

                    for _ in 0..delta_self {

                        let (_, self_part) = self.parts[self_index];

                        let (_, other_part) = other.parts[other_index];

                        if self_part != other_part {

                            return false;

                        }

                        self_index += 1;

                        other_index += 1;

                    }

                } else {

                    // Both not in use, so skip associated parts