pub struct FunctionArgument {

    identifier: Identifier,

    parser_type: ParserType,

}

/// Represents the data associated with a single expression after type inference

/// for a monomorph (or just the normal expression types, if dealing with a

/// non-polymorphic function/component).

pub struct MonomorphExpression {

    // The output type of the expression. Note that for a function it is not the

    // function's signature but its return type

    pub(crate) expr_type: ConcreteType,

    // Has multiple meanings: the field index for select expressions, the

    // monomorph index for polymorphic function calls or literals. Negative

    // values are never used, but used to catch programming errors.

    pub(crate) field_or_monomorph_idx: i32,

}

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

// Type table

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

struct ResolveBreadcrumb {

    root_id: RootId,

    definition_id: DefinitionId,

    next_member: u32,

    next_embedded: u32, // for unions, the next embedded value inside the member

    progression: DefinedTypeVariant

}

/// Result from attempting to resolve a `ParserType` using the symbol table and

/// the type table.

enum ResolveResult {

    Builtin,

    PolymoprhicArgument,

    /// ParserType points to a user-defined type that is already resolved in the

    /// type table.

    Resolved(RootId, DefinitionId),

    /// ParserType points to a user-defined type that is not yet resolved into

    /// the type table.

    Unresolved(RootId, DefinitionId)

}

/// Result from attempting to progress a breadcrumb

enum ProgressResult {

    PopBreadcrumb,

    PushBreadcrumb(RootId, DefinitionId),

    TypeLoop(RootId, DefinitionId),

}

pub struct TypeTable {

    /// Lookup from AST DefinitionId to a defined type. Considering possible

    /// polymorphs is done inside the `DefinedType` struct.

    lookup: HashMap<DefinitionId, DefinedType>,

    /// Breadcrumbs left behind while resolving embedded types

    breadcrumbs: Vec<ResolveBreadcrumb>,

    infinite_unions: Vec<(RootId, DefinitionId)>,

}

impl TypeTable {

    /// Construct a new type table without any resolved types.

    pub(crate) fn new() -> Self {

        Self{ 

            lookup: HashMap::new(), 

            breadcrumbs: Vec::with_capacity(32),

            infinite_unions: Vec::with_capacity(16),

        }

    }

    /// Iterates over all defined types (polymorphic and non-polymorphic) and

    /// add their types in two passes. In the first pass we will just add the

    /// base types (we will not consider monomorphs, and we will not compute

    /// byte sizes). In the second pass we will compute byte sizes of

    /// non-polymorphic types, and potentially the monomorphs that are embedded

    /// in those types.

    pub(crate) fn build_base_types(&mut self, modules: &mut [Module], ctx: &mut PassCtx) -> Result<(), ParseError> {

        // Make sure we're allowed to cast root_id to index into ctx.modules

        debug_assert!(modules.iter().all(|m| m.phase >= ModuleCompilationPhase::DefinitionsParsed));

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

        if cfg!(debug_assertions) {

            for (index, module) in modules.iter().enumerate() {

                debug_assert_eq!(index, module.root_id.index as usize);

            }

        }

        // Use context to guess hashmap size of the base types

        let reserve_size = ctx.heap.definitions.len();

        self.lookup.reserve(reserve_size);

        // Resolve all base types

        for definition_idx in 0..ctx.heap.definitions.len() {

            let definition_id = ctx.heap.definitions.get_id(definition_idx);

            let definition = &ctx.heap[definition_id];

            match definition {

            }

        }

        debug_assert_eq!(self.lookup.len(), reserve_size, "mismatch in reserved size of type table"); // NOTE: Temp fix for builtin functions

        for module in modules {

            module.phase = ModuleCompilationPhase::TypesAddedToTable;

        }

        Ok(())

    }

    /// Retrieves base definition from type table. We must be able to retrieve

    /// it as we resolve all base types upon type table construction (for now).

    /// However, in the future we might do on-demand type resolving, so return

    /// an option anyway

    pub(crate) fn get_base_definition(&self, definition_id: &DefinitionId) -> Option<&DefinedType> {

        self.lookup.get(&definition_id)

    }

    /// Returns the index into the monomorph type array if the procedure type

    /// already has a (reserved) monomorph.

    pub(crate) fn get_procedure_monomorph_index(&self, definition_id: &DefinitionId, types: &Vec<ConcreteType>) -> Option<i32> {

        let def = self.lookup.get(definition_id).unwrap();

        if def.is_polymorph {

            let monos = def.definition.procedure_monomorphs();

            return monos.iter()

                .position(|v| v.poly_args == *types)

                .map(|v| v as i32);

        } else {

            // We don't actually care about the types

            let monos = def.definition.procedure_monomorphs();

            if monos.is_empty() {

                return None

            } else {

                return Some(0)

            }

        }

    }

    /// Returns a mutable reference to a procedure's monomorph expression data.

    /// Used by typechecker to fill in previously reserved type information

    pub(crate) fn get_procedure_expression_data_mut(&mut self, definition_id: &DefinitionId, monomorph_idx: i32) -> &mut ProcedureMonomorph {

        debug_assert!(monomorph_idx >= 0);

        let def = self.lookup.get_mut(definition_id).unwrap();

        let monomorphs = def.definition.procedure_monomorphs_mut();

        return &mut monomorphs[monomorph_idx as usize];

    }

    pub(crate) fn get_procedure_expression_data(&self, definition_id: &DefinitionId, monomorph_idx: i32) -> &ProcedureMonomorph {

        debug_assert!(monomorph_idx >= 0);

        let def = self.lookup.get(definition_id).unwrap();

        let monomorphs = def.definition.procedure_monomorphs();

        return &monomorphs[monomorph_idx as usize];

    }

    /// Reserves space for a monomorph of a polymorphic procedure. The index

    /// will point into a (reserved) slot of the array of expression types. The

    /// monomorph may NOT exist yet (because the reservation implies that we're

    /// going to be performing typechecking on it, and we don't want to

    /// check the same monomorph twice)

    pub(crate) fn reserve_procedure_monomorph_index(&mut self, definition_id: &DefinitionId, types: Option<Vec<ConcreteType>>) -> i32 {

        let def = self.lookup.get_mut(definition_id).unwrap();

        if let Some(types) = types {

            // Expecting a polymorphic procedure

            let monos = def.definition.procedure_monomorphs_mut();

            debug_assert!(def.is_polymorph);

            debug_assert!(def.poly_vars.len() == types.len());

            debug_assert!(monos.iter().find(|v| v.poly_args == types).is_none());

            let mono_idx = monos.len();

            monos.push(ProcedureMonomorph{ poly_args: types, expr_data: Vec::new() });

            return mono_idx as i32;

        } else {

            // Expecting a non-polymorphic procedure

            let monos = def.definition.procedure_monomorphs_mut();

            debug_assert!(!def.is_polymorph);

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

            debug_assert!(monos.is_empty());

            monos.push(ProcedureMonomorph{ poly_args: Vec::new(), expr_data: Vec::new() });

            return 0;

        }

    }

    /// Adds a datatype polymorph to the type table. Will not add the

    /// monomorph if it is already present, or if the type's polymorphic

    /// variables are all unused.

    pub(crate) fn add_data_monomorph(&mut self, definition_id: &DefinitionId, types: Vec<ConcreteType>) -> i32 {

        let def = self.lookup.get_mut(definition_id).unwrap();

        if !def.is_polymorph {

            // Not a polymorph, or polyvars are not used in type definition

            return 0;

        }

        let monos = def.definition.data_monomorphs_mut();

        if let Some(index) = monos.iter().position(|v| v.poly_args == types) {

            // We already know about this monomorph

            return index as i32;

        }

        let index = monos.len();

        monos.push(DataMonomorph{ poly_args: types });

        self.push_breadcrumb_for_definition(ctx, definition_id);

        while let Some(breadcrumb) = self.breadcrumbs.last() {

            // We have a type to resolve

            let definition = &ctx.heap[breadcrumb.definition_id];

            let can_pop_breadcrumb = match definition {

                // Bit ugly, since we already have the definition, but we need

                // to work around rust borrowing rules...

                Definition::Enum(_) => self.resolve_base_enum_definition(modules, ctx),

                Definition::Union(_) => self.resolve_base_union_definition(modules, ctx),

                Definition::Struct(_) => self.resolve_base_struct_definition(modules, ctx),

                Definition::Component(_) => self.resolve_base_component_definition(modules, ctx),

                Definition::Function(_) => self.resolve_base_function_definition(modules, ctx),

            }?;

            // Otherwise: `ingest_resolve_result` has pushed a new breadcrumb

            // that we must follow before we can resolve the current type

            if can_pop_breadcrumb {

                self.breadcrumbs.pop();

            }

        }

        // We must have resolved the type

        debug_assert!(self.lookup.contains_key(&definition_id), "base type not resolved");

        Ok(())

    }

    /// Builds the base type for an enum. Will not compute byte sizes

    fn build_base_enum_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, definition_id: DefinitionId) -> Result<(), ParseError> {

        debug_assert!(!self.lookup.contains_key(&definition_id), "base enum already built");

        let definition = ctx.heap[definition_id].as_enum();

        let root_id = definition.defined_in;

        // Determine enum variants

        let mut enum_value = -1;

        let mut variants = Vec::with_capacity(definition.variants.len());

        for variant in &definition.variants {

            if enum_value == i64::MAX {

                let source = &modules[definition.defined_in.index as usize].source;

                return Err(ParseError::new_error_str_at_span(

                    source, variant.identifier.span,

                    "this enum variant has an integer value that is too large"

                ));

            }

            enum_value += 1;

            if let EnumVariantValue::Integer(explicit_value) = variant.value {

                enum_value = explicit_value;

            }

            variants.push(EnumVariant{

                identifier: variant.identifier.clone(),

                value: enum_value,

            });

        }

        // Determine tag size

        let mut min_enum_value = 0;

        let mut max_enum_value = 0;

        if !variants.is_empty() {

            min_enum_value = variants[0].value;

            max_enum_value = variants[0].value;

            for variant in variants.iter().skip(1) {

                min_enum_value = min_enum_value.min(variant.value);

                max_enum_value = max_enum_value.max(variant.value);

            }

        }

        // TODO: Tag size determination, here or when laying out?

        // Enum names and polymorphic args do not conflict

        Self::check_identifier_collision(

            modules, root_id, &variants, |variant| &variant.identifier, "enum variant"

        )?;

        // Polymorphic arguments cannot appear as embedded types, because

        // they can only consist of integer variants.

        Self::check_poly_args_collision(modules, ctx, root_id, &definition.poly_vars)?;

        let poly_vars = Self::create_polymorphic_variables(&definition.poly_vars);

        self.lookup.insert(definition_id, DefinedType {

            ast_root: root_id,

            ast_definition: definition_id,

            definition: DefinedTypeVariant::Enum(EnumType{

                variants,

                monomorphs: Vec::new(),

            }),

            poly_vars,

            is_polymorph: false,

        });

        return Ok(());

    }

    fn build_base_struct_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, definition_id: DefinitionId) -> Result<(), ParseError> {

        debug_assert!(!self.lookup.contains_key(&definition_id), "base struct already built");

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

        let root_id = definition.defined_in;

        let mut fields = Vec::with_capacity(definition.fields.len());

        for field in &definition.fields {

        }

    }

    /// Resolve the basic enum definition to an entry in the type table. It will

    /// not instantiate any monomorphized instances of polymorphic enum

    /// definitions. If a subtype has to be resolved first then this function

    /// will return `false` after calling `ingest_resolve_result`.

    fn resolve_base_enum_definition(&mut self, modules: &[Module], ctx: &mut PassCtx) -> Result<bool, ParseError> {

        // Retrieve breadcrumb and perform some basic checking

        let breadcrumb = self.breadcrumbs.last_mut().unwrap();

        let root_id = breadcrumb.root_id;

        let definition_id = breadcrumb.definition_id;

        debug_assert!(ctx.heap[definition_id].is_enum());

        debug_assert!(!self.lookup.contains_key(&definition_id), "base enum already resolved");

        let definition = ctx.heap[definition_id].as_enum();

        // Since we're dealing with an enum's base definition, we're not going

        // to check any embedded types and should finish layout out the enum in

        // one go.

        debug_assert!(breadcrumb.progression.is_none());

        // Determine enum variants

        let mut enum_value = -1;

        let mut min_enum_value = 0;

        let mut max_enum_value = 0;

        let mut variants = Vec::with_capacity(definition.variants.len());

        for variant in &definition.variants {

            enum_value += 1;

            match &variant.value {

                EnumVariantValue::None => {

                    variants.push(EnumVariant{

                        identifier: variant.identifier.clone(),

                        value: enum_value,

                    });

                },

                EnumVariantValue::Integer(override_value) => {

                    enum_value = *override_value;

                    variants.push(EnumVariant{

                        identifier: variant.identifier.clone(),

                        value: enum_value,

                    });

                }

            }

            if enum_value < min_enum_value { min_enum_value = enum_value; }

            else if enum_value > max_enum_value { max_enum_value = enum_value; }

        }

        // Ensure enum names and polymorphic args do not conflict

        Self::check_identifier_collision(

            modules, root_id, &variants, |variant| &variant.identifier, "enum variant"

        )?;

        // Because we're parsing an enum, the programmer cannot put the

        // polymorphic variables inside the variants. But the polymorphic

        // variables might still be present as "marker types"

        Self::check_poly_args_collision(modules, ctx, root_id, &definition.poly_vars)?;

        let poly_vars = Self::create_polymorphic_variables(&definition.poly_vars);

        self.lookup.insert(definition_id, DefinedType {

            ast_root: root_id,

            ast_definition: definition_id,

            definition: DefinedTypeVariant::Enum(EnumType{

                variants,

                monomorphs: Vec::new(),

            }),

            poly_vars,

            is_polymorph: false,

        });

        Ok(true)

    }

    /// Resolves the basic union definiton to an entry in the type table. It

    /// will not instantiate any monomorphized instances of polymorphic union

    /// definitions. If a subtype has to be resolved first then this function

    /// will return `false` after calling `ingest_resolve_result`.

    fn resolve_base_union_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, root_id: RootId, definition_id: DefinitionId) -> Result<bool, ParseError> {

        debug_assert!(ctx.heap[definition_id].is_union());

        debug_assert!(!self.lookup.contains_key(&definition_id), "base union already resolved");

        let definition = ctx.heap[definition_id].as_union();

        // Make sure all embedded types are resolved

        for variant in &definition.variants {

            match &variant.value {

                UnionVariantValue::None => {},

                UnionVariantValue::Embedded(embedded) => {

                    for parser_type in embedded {

                        let resolve_result = self.resolve_base_parser_type(modules, ctx, root_id, parser_type, false)?;

                        if !self.ingest_resolve_result(modules, ctx, resolve_result)? {

                            return Ok(false)

                        }

                    }

                }

            }

        }

        let mut poly_vars = Self::create_polymorphic_variables(&definition.poly_vars);

        for variant in &variants {

            for parser_type in &variant.embedded {

                Self::mark_used_polymorphic_variables(&mut poly_vars, parser_type);

            }

        }

        let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use);

        // Insert base definition in type table

        self.lookup.insert(definition_id, DefinedType {

            ast_root: root_id,

            ast_definition: definition_id,

            definition: DefinedTypeVariant::Union(UnionType{

                variants,

                monomorphs: Vec::new(),

                requires_allocation: false,

                contains_unallocated_variant: true

            }),

            poly_vars,

            is_polymorph,

        });

        Ok(true)

    }

    /// Resolves the basic struct definition to an entry in the type table. It

    /// will not instantiate any monomorphized instances of polymorphic struct

    /// definitions.

    fn resolve_base_struct_definition(&mut self, modules: &[Module], ctx: &mut PassCtx) -> Result<bool, ParseError> {

        debug_assert!(ctx.heap[definition_id].is_struct());

        debug_assert!(!self.lookup.contains_key(&definition_id), "base struct already resolved");

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

        // Make sure all fields point to resolvable types

        for field_definition in &definition.fields {

            let resolve_result = self.resolve_base_parser_type(modules, ctx, root_id, &field_definition.parser_type, false)?;

            if !self.ingest_resolve_result(modules, ctx, resolve_result)? {

                return Ok(false)

            }

        }

        // All fields types are resolved, construct base type

        let mut fields = Vec::with_capacity(definition.fields.len());

        for field_definition in &definition.fields {

            fields.push(StructField{

                identifier: field_definition.field.clone(),

                parser_type: field_definition.parser_type.clone(),

            })

        }

        // And make sure no conflicts exist in field names and/or polymorphic args

        Self::check_identifier_collision(

            modules, root_id, &fields, |field| &field.identifier, "struct field"

        )?;

        Self::check_poly_args_collision(modules, ctx, root_id, &definition.poly_vars)?;

        // Construct representation of polymorphic arguments

        let mut poly_vars = Self::create_polymorphic_variables(&definition.poly_vars);

        for field in &fields {

            Self::mark_used_polymorphic_variables(&mut poly_vars, &field.parser_type);

        }

        let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use);

        self.lookup.insert(definition_id, DefinedType{

            ast_root: root_id,

            ast_definition: definition_id,

            definition: DefinedTypeVariant::Struct(StructType{

                fields,

                monomorphs: Vec::new(),

            }),

            poly_vars,

            is_polymorph,

        });

        Ok(true)

    }

    /// Resolves the basic function definition to an entry in the type table. It

    /// will not instantiate any monomorphized instances of polymorphic function

    /// definitions.

    fn resolve_base_function_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, root_id: RootId, definition_id: DefinitionId) -> Result<bool, ParseError> {

        debug_assert!(ctx.heap[definition_id].is_function());

        debug_assert!(!self.lookup.contains_key(&definition_id), "base function already resolved");

        let definition = ctx.heap[definition_id].as_function();

        // Check the return type

        debug_assert_eq!(definition.return_types.len(), 1, "not one return type"); // TODO: @ReturnValues

        let resolve_result = self.resolve_base_parser_type(modules, ctx, root_id, &definition.return_types[0], definition.builtin)?;

        if !self.ingest_resolve_result(modules, ctx, resolve_result)? {

            return Ok(false)

        }

        // Check the argument types

        for param_id in &definition.parameters {

            let param = &ctx.heap[*param_id];

            let resolve_result = self.resolve_base_parser_type(modules, ctx, root_id, &param.parser_type, definition.builtin)?;

            if !self.ingest_resolve_result(modules, ctx, resolve_result)? {

                return Ok(false)

            }

            arguments.push(FunctionArgument{

                identifier: param.identifier.clone(),

                parser_type: param.parser_type.clone(),

        }

        // Check conflict of argument and polyarg identifiers

        Self::check_identifier_collision(

            modules, root_id, &arguments, |arg| &arg.identifier, "function argument"

        )?;

        Self::check_poly_args_collision(modules, ctx, root_id, &definition.poly_vars)?;

        // Construct polymorphic arguments

        let mut poly_vars = Self::create_polymorphic_variables(&definition.poly_vars);

        Self::mark_used_polymorphic_variables(&mut poly_vars, &definition.return_types[0]);

        for argument in &arguments {

            Self::mark_used_polymorphic_variables(&mut poly_vars, &argument.parser_type);

        }

        let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use);

        // Construct entry in type table

        self.lookup.insert(definition_id, DefinedType{

            ast_root: root_id,

            ast_definition: definition_id,

            definition: DefinedTypeVariant::Function(FunctionType{

                return_types: definition.return_types.clone(),

                arguments,

                monomorphs: Vec::new(),

            }),

            poly_vars,

            is_polymorph,

        });

        Ok(true)

    }

    /// Resolves the basic component definition to an entry in the type table.

    /// It will not instantiate any monomorphized instancees of polymorphic

    /// component definitions.

    fn resolve_base_component_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, root_id: RootId, definition_id: DefinitionId) -> Result<bool, ParseError> {

        debug_assert!(ctx.heap[definition_id].is_component());

        debug_assert!(!self.lookup.contains_key(&definition_id), "base component already resolved");

        let definition = ctx.heap[definition_id].as_component();

        let component_variant = definition.variant;

        // Check argument types

        for param_id in &definition.parameters {

            let param = &ctx.heap[*param_id];

            let resolve_result = self.resolve_base_parser_type(modules, ctx, root_id, &param.parser_type, false)?;

            if !self.ingest_resolve_result(modules, ctx, resolve_result)? {

                return Ok(false)

            }

        }

        // Construct argument types

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

        for param_id in &definition.parameters {

            let param = &ctx.heap[*param_id];

            arguments.push(FunctionArgument{

                identifier: param.identifier.clone(),

                parser_type: param.parser_type.clone()

            })

        }

        // Check conflict of argument and polyarg identifiers

        Self::check_identifier_collision(

            modules, root_id, &arguments, |arg| &arg.identifier, "component argument"

        )?;

        Self::check_poly_args_collision(modules, ctx, root_id, &definition.poly_vars)?;

        // Construct polymorphic arguments

        let mut poly_vars = Self::create_polymorphic_variables(&definition.poly_vars);

        for argument in &arguments {

            Self::mark_used_polymorphic_variables(&mut poly_vars, &argument.parser_type);

        }

        let is_polymorph = poly_vars.iter().any(|v| v.is_in_use);

        // Construct entry in type table

        self.lookup.insert(definition_id, DefinedType{

            ast_root: root_id,

            ast_definition: definition_id,

            definition: DefinedTypeVariant::Component(ComponentType{

                variant: component_variant,

                arguments,

                monomorphs: Vec::new(),

            }),

            poly_vars,

            is_polymorph,

        });

        Ok(true)

    }

    /// Takes a ResolveResult and returns `true` if the caller can happily

    /// continue resolving its current type, or `false` if the caller must break

    /// resolving the current type and exit to the outer resolving loop. In the

    /// latter case the `result` value was `ResolveResult::Unresolved`, implying

    /// that the type must be resolved first.

    fn ingest_resolve_result(&mut self, modules: &[Module], ctx: &PassCtx, result: ResolveResult) -> Result<bool, ParseError> {

        match result {

            ResolveResult::Builtin | ResolveResult::PolymoprhicArgument => Ok(true),

            ResolveResult::Resolved(_, _) => Ok(true),

            ResolveResult::Unresolved(root_id, definition_id) => {

                if self.iter.contains(root_id, definition_id) {

                    // Cyclic dependency encountered

                } else {

                    // Type is not yet resolved, so push IDs on iterator and

                    // continue the resolving loop

                    self.iter.push(root_id, definition_id);

                    Ok(false)

                }

            }

        }

    }

    fn construct_cyclic_type_error(

        &self, modules: &[Module], ctx: &PassCtx, type_root_id: RootId, type_definition_id: DefinitionId

    ) -> ParseError {

        debug_assert!(self.iter.contains(type_root_id, type_definition_id));

        // Construct error message put at the top

        let module_source = &modules[type_root_id.index as usize].source;

        let mut error = ParseError::new_error_str_at_span(

            module_source, ctx.heap[type_definition_id].identifier().span,

            "Evaluating this type definition results in a cyclic type"

        );

        // Show a listing of all dependent types.

        // TODO: Make more correct later

        for (breadcrumb_idx, (root_id, definition_id)) in self.iter.breadcrumbs.iter().enumerate() {

            let msg = if breadcrumb_idx == 0 {

                "The cycle started with this definition"

            } else {

                "Which depends on this definition"

            };

            let module_source = &modules[root_id.index as usize].source;

            error = error.with_info_str_at_span(module_source, ctx.heap[*definition_id].identifier().span, msg);

        }

        return error;

    }

    /// Will check if the member type (field of a struct, embedded type in a