}

pub struct PolymorphicVariable {

    identifier: Identifier,

    is_in_use: bool, // a polymorphic argument may be defined, but not used by the type definition

}

/// `EnumType` is the classical C/C++ enum type. It has various variants with

/// an assigned integer value. The integer values may be user-defined,

/// compiler-defined, or a mix of the two. If a user assigns the same enum

/// value multiple times, we assume the user is an expert and we consider both

/// variants to be equal to one another.

pub struct EnumType {

    pub variants: Vec<EnumVariant>,

    pub minimum_tag_value: i64,

    pub maximum_tag_value: i64,

    pub tag_type: ConcreteType,

    pub size: usize,

    pub alignment: usize,

}

// TODO: Also support maximum u64 value

pub struct EnumVariant {

    pub identifier: Identifier,

    pub value: i64,

}

/// `UnionType` is the algebraic datatype (or sum type, or discriminated union).

/// A value is an element of the union, identified by its tag, and may contain

/// a single subtype.

/// For potentially infinite types (i.e. a tree, or a linked list) only unions

/// can break the infinite cycle. So when we lay out these unions in memory we

/// will reserve enough space on the stack for all union variants that do not

/// cause "type loops" (i.e. a union `A` with a variant containing a struct

/// `B`). And we will reserve enough space on the heap (and store a pointer in

/// the union) for all variants which do cause type loops (i.e. a union `A`

/// with a variant to a struct `B` that contains the union `A` again).

pub struct UnionType {

    pub variants: Vec<UnionVariant>,

    pub tag_type: ConcreteType,

    pub tag_size: usize,

}

pub struct UnionVariant {

    pub identifier: Identifier,

    pub embedded: Vec<ParserType>, // zero-length does not have embedded values

    pub tag_value: i64,

}

/// `StructType` is a generic C-like struct type (or record type, or product

/// type) type.

pub struct StructType {

    pub fields: Vec<StructField>,

}

pub struct StructField {

    pub identifier: Identifier,

    pub parser_type: ParserType,

}

/// `FunctionType` is what you expect it to be: a particular function's

/// signature.

pub struct FunctionType {

    pub return_type: ParserType,

    pub arguments: Vec<FunctionArgument>,

}

pub struct ComponentType {

    pub variant: ComponentVariant,

    pub arguments: Vec<FunctionArgument>,

}

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,

    pub(crate) type_id: TypeId,

}

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

// Type monomorph storage

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

pub(crate) enum MonoTypeVariant {

    Enum, // no extra data

    Struct(StructMonomorph),

    Union(UnionMonomorph),

    Procedure(ProcedureMonomorph), // functions, components

    Tuple(TupleMonomorph),

}

impl MonoTypeVariant {

    fn as_struct_mut(&mut self) -> &mut StructMonomorph {

        match self {

            MonoTypeVariant::Struct(v) => v,

            _ => unreachable!(),

        }

    }

    pub(crate) fn as_union(&self) -> &UnionMonomorph {

        match self {

            MonoTypeVariant::Union(v) => v,

            _ => unreachable!(),

        }

    }

    fn as_union_mut(&mut self) -> &mut UnionMonomorph {

        match self {

            MonoTypeVariant::Union(v) => v,

            _ => unreachable!(),

        }

    }

    fn as_tuple_mut(&mut self) -> &mut TupleMonomorph {

        match self {

            MonoTypeVariant::Tuple(v) => v,

            _ => unreachable!(),

        }

    }

    fn as_procedure(&self) -> &ProcedureMonomorph {

        match self {

            MonoTypeVariant::Procedure(v) => v,

            _ => unreachable!(),

        }

    }

    fn as_procedure_mut(&mut self) -> &mut ProcedureMonomorph {

        match self {

            MonoTypeVariant::Procedure(v) => v,

            _ => unreachable!(),

        }

    }

}

/// Struct monomorph

pub struct StructMonomorph {

    pub fields: Vec<StructMonomorphField>,

}

pub struct StructMonomorphField {

    pub type_id: TypeId,

    concrete_type: ConcreteType,

    pub size: usize,

    pub alignment: usize,

    pub offset: usize,

}

/// Union monomorph

pub struct UnionMonomorph {

    pub variants: Vec<UnionMonomorphVariant>,

    pub tag_size: usize, // copied from `UnionType` upon monomorph construction.

    // note that the stack size is in the `TypeMonomorph` struct. This size and

    // alignment will include the size of the union tag.

    //

    // heap_size contains the allocated size of the union in the case it

    // is used to break a type loop. If it is 0, then it doesn't require

    // allocation and lives entirely on the stack.

    pub heap_size: usize,

    pub heap_alignment: usize,

}

pub struct UnionMonomorphVariant {

    pub lives_on_heap: bool,

    pub embedded: Vec<UnionMonomorphEmbedded>,

}

pub struct UnionMonomorphEmbedded {

    pub type_id: TypeId,

    concrete_type: ConcreteType,

    // Note that the meaning of the offset (and alignment) depend on whether or

    // not the variant lives on the stack/heap. If it lives on the stack then

    // they refer to the offset from the start of the union value (so the first

    // embedded type lives at a non-zero offset, because the union tag sits in

    // the front). If it lives on the heap then it refers to the offset from the

    // allocated memory region (so the first embedded type lives at a 0 offset).

    pub size: usize,

    pub alignment: usize,

    pub offset: usize,

}

        debug_assert_eq!(self.definition_lookup.len(), reserve_size, "mismatch in reserved size of type table");

        for module in modules.iter_mut() {

            module.phase = ModuleCompilationPhase::TypesAddedToTable;

        }

        // Go through all types again, lay out all types that are not

        // polymorphic. This might cause us to lay out monomorphized polymorphs

        // if these were member types of non-polymorphic types.

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

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

            let poly_type = self.definition_lookup.get(&definition_id).unwrap();

            if !poly_type.definition.type_class().is_data_type() || !poly_type.poly_vars.is_empty() {

                continue;

            }

            // If here then the type is a data type without polymorphic

            // variables, but we might have instantiated it already, so:

            let concrete_parts = [ConcreteTypePart::Instance(definition_id, 0)];

            self.mono_search_key.set(&concrete_parts, &[]);

            let type_id = self.mono_type_lookup.get(&self.mono_search_key);

            if type_id.is_none() {

                self.detect_and_resolve_type_loops_for(

                    modules, ctx.heap,

                    ConcreteType{

                        parts: vec![ConcreteTypePart::Instance(definition_id, 0)]

                    },

                )?;

                self.lay_out_memory_for_encountered_types(ctx.arch);

            }

        }

        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

    #[inline]

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

        self.definition_lookup.get(&definition_id)

    }

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

    /// already has a (reserved) monomorph.

    #[inline]

    pub(crate) fn get_procedure_monomorph_type_id(&self, definition_id: &DefinitionId, type_parts: &[ConcreteTypePart]) -> Option<TypeId> {

        // Cannot use internal search key due to mutability issues. But this

        // method should end up being deprecated at some point anyway.

        let base_type = self.definition_lookup.get(definition_id).unwrap();

        let mut search_key = MonoSearchKey::with_capacity(type_parts.len());

        search_key.set(type_parts, &base_type.poly_vars);

        return self.mono_type_lookup.get(&search_key).copied();

    }

    #[inline]

    pub(crate) fn get_monomorph(&self, type_id: TypeId) -> &MonoType {

        return &self.mono_types[type_id.0 as usize];

    }

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

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

    #[inline]

    pub(crate) fn get_procedure_monomorph_mut(&mut self, type_id: TypeId) -> &mut ProcedureMonomorph {

        let mono_type = &mut self.mono_types[type_id.0 as usize];

        return mono_type.variant.as_procedure_mut();

    }

    #[inline]

    pub(crate) fn get_procedure_monomorph(&self, type_id: TypeId) -> &ProcedureMonomorph {

        let mono_type = &self.mono_types[type_id.0 as usize];

        return mono_type.variant.as_procedure();

    }

    /// 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_type_id(&mut self, definition_id: &DefinitionId, concrete_type: ConcreteType) -> TypeId {

        let type_id = TypeId(self.mono_types.len() as i64);

        let base_type = self.definition_lookup.get_mut(definition_id).unwrap();

        self.mono_search_key.set(&concrete_type.parts, &base_type.poly_vars);

        debug_assert!(!self.mono_type_lookup.contains_key(&self.mono_search_key));

        self.mono_type_lookup.insert(self.mono_search_key.clone(), type_id);

        self.mono_types.push(MonoType::new_empty(type_id, concrete_type, MonoTypeVariant::Procedure(ProcedureMonomorph{

            arg_types: Vec::new(),

            expr_data: Vec::new(),

        })));

        return type_id;

    }

    /// Adds a monomorphed type to the type table. If it already exists then the

    /// previous entry will be used.

    pub(crate) fn add_monomorphed_type(

        &mut self, modules: &[Module], heap: &Heap, arch: &TargetArch,

        definition_id: DefinitionId, concrete_type: ConcreteType

    ) -> Result<TypeId, ParseError> {

        debug_assert_eq!(definition_id, get_concrete_type_definition(&concrete_type.parts).unwrap());

        // Check if the concrete type was already added

        let definition = self.definition_lookup.get(&definition_id).unwrap();

        let poly_var_in_use = &definition.poly_vars;

        self.mono_search_key.set(&concrete_type.parts, poly_var_in_use.as_slice());

        if let Some(type_id) = self.mono_type_lookup.get(&self.mono_search_key) {

            return Ok(*type_id);

        }

        // Concrete type needs to be added

        self.detect_and_resolve_type_loops_for(modules, heap, concrete_type)?;

        let type_id = self.encountered_types[0].type_id;

        self.lay_out_memory_for_encountered_types(arch);

        return Ok(type_id);

    }

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

    // Building base types

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

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

            }

        }

        let (tag_type, size_and_alignment) = Self::variant_tag_type_from_values(min_enum_value, max_enum_value);

        // 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.definition_lookup.insert(definition_id, DefinedType {

            ast_root: root_id,

            ast_definition: definition_id,

            definition: DefinedTypeVariant::Enum(EnumType{

                variants,

                minimum_tag_value: min_enum_value,

                maximum_tag_value: max_enum_value,

                tag_type,

                size: size_and_alignment,

                alignment: size_and_alignment

            }),

            poly_vars,

            is_polymorph: false,

        });

    }

    /// Go through a list of polymorphic arguments and make sure that the

    /// arguments all have unique names, and the arguments do not conflict with

    /// any symbols defined at the module scope.

    fn check_poly_args_collision(

        modules: &[Module], ctx: &PassCtx, root_id: RootId, poly_args: &[Identifier]

    ) -> Result<(), ParseError> {

        // Make sure polymorphic arguments are unique and none of the

        // identifiers conflict with any imported scopes

        for (arg_idx, poly_arg) in poly_args.iter().enumerate() {

            for other_poly_arg in &poly_args[..arg_idx] {

                if poly_arg == other_poly_arg {

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

                    return Err(ParseError::new_error_str_at_span(

                        module_source, poly_arg.span,

                        "This polymorphic argument is defined more than once"

                    ).with_info_str_at_span(

                        module_source, other_poly_arg.span,

                        "It conflicts with this polymorphic argument"

                    ));

                }

            }

            // Check if identifier conflicts with a symbol defined or imported

            // in the current module

            if let Some(symbol) = ctx.symbols.get_symbol_by_name(SymbolScope::Module(root_id), poly_arg.value.as_bytes()) {

                // We have a conflict

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

                let introduction_span = symbol.variant.span_of_introduction(ctx.heap);

                return Err(ParseError::new_error_str_at_span(

                    module_source, poly_arg.span,

                    "This polymorphic argument conflicts with another symbol"

                ).with_info_str_at_span(

                    module_source, introduction_span,

                    "It conflicts due to this symbol"

                ));

            }

        }

        // All arguments are fine

        Ok(())

    }

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

    // Detecting type loops

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

    /// Internal function that will detect type loops and check if they're

    /// resolvable. If so then the appropriate union variants will be marked as

    /// "living on heap". If not then a `ParseError` will be returned

    fn detect_and_resolve_type_loops_for(&mut self, modules: &[Module], heap: &Heap, concrete_type: ConcreteType) -> Result<(), ParseError> {

        // Programmer notes: what happens here is the we call

        // `check_member_for_type_loops` for a particular type's member, and

        // then take action using the return value:

        // 1. It might already be resolved: in this case it implies we don't

        //  have type loops, or they have been resolved.

        // 2. A new type is encountered. If so then it is added to the type loop

        //  breadcrumbs.

        // 3. A type loop is detected (implying the type is already resolved, or

        //  already exists in the type loop breadcrumbs).

        //

        // Using the breadcrumbs we incrementally check every member type of a

        // particular considered type (e.g. a struct field, tuple member), and

        // do the same as above. Note that when a breadcrumb is added we reserve

        // space in the monomorph storage, initialized to zero-values (i.e.

        // wrong values). The breadcrumbs keep track of how far and along we are

        // with resolving the member types.

        //

        // At the end we may have some type loops. If they're unresolvable then

        // we throw an error). If there are no type loops or they are all

        // resolvable then we end up with a list of `encountered_types`. These

        // are then used by `lay_out_memory_for_encountered_types`.

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

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

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

        // Push the initial breadcrumb

        let initial_breadcrumb = Self::check_member_for_type_loops(

            &self.type_loop_breadcrumbs, &self.definition_lookup, &self.mono_type_lookup,

            &mut self.mono_search_key, &concrete_type

        );

        if let TypeLoopResult::PushBreadcrumb(definition_id, concrete_type) = initial_breadcrumb {

            self.handle_new_breadcrumb_for_type_loops(definition_id, concrete_type);

        } else {

            unreachable!();

        }

        // Enter into the main resolving loop

        while !self.type_loop_breadcrumbs.is_empty() {

            // Because we might be modifying the breadcrumb array we need to

            let breadcrumb_idx = self.type_loop_breadcrumbs.len() - 1;

            let mut breadcrumb = self.type_loop_breadcrumbs[breadcrumb_idx].clone();

            let mono_type = &self.mono_types[breadcrumb.type_id.0 as usize];

            let resolve_result = match &mono_type.variant {

                MonoTypeVariant::Enum => {

                    TypeLoopResult::TypeExists

                },

                MonoTypeVariant::Union(monomorph) => {

                    let num_variants = monomorph.variants.len() as u32;

                    let mut union_result = TypeLoopResult::TypeExists;

                    'member_loop: while breadcrumb.next_member < num_variants {

                        let mono_variant = &monomorph.variants[breadcrumb.next_member as usize];

                        let num_embedded = mono_variant.embedded.len() as u32;

                        while breadcrumb.next_embedded < num_embedded {

                            let mono_embedded = &mono_variant.embedded[breadcrumb.next_embedded as usize];

                            union_result = Self::check_member_for_type_loops(

                                &self.type_loop_breadcrumbs, &self.definition_lookup, &self.mono_type_lookup,

                                &mut self.mono_search_key, &mono_embedded.concrete_type

                            );

                            if union_result != TypeLoopResult::TypeExists {

                                // In type loop or new breadcrumb pushed, so

                                // break out of the resolving loop

                                break 'member_loop;

                            }

                            breadcrumb.next_embedded += 1;

                        }

                        breadcrumb.next_embedded = 0;

                        breadcrumb.next_member += 1

                    }

                    union_result

                },

                MonoTypeVariant::Struct(monomorph) => {

                    let num_fields = monomorph.fields.len() as u32;

                    let mut struct_result = TypeLoopResult::TypeExists;

                    while breadcrumb.next_member < num_fields {

                        let mono_field = &monomorph.fields[breadcrumb.next_member as usize];

                        struct_result = Self::check_member_for_type_loops(

                            &self.type_loop_breadcrumbs, &self.definition_lookup, &self.mono_type_lookup,

                            &mut self.mono_search_key, &mono_field.concrete_type

                        );

                        if struct_result != TypeLoopResult::TypeExists {

                            // Type loop or breadcrumb pushed, so break out of

                            // the resolving loop

                            break;

                        }

                        breadcrumb.next_member += 1;

                    }

                    struct_result

                },

                MonoTypeVariant::Procedure(_) => unreachable!(),

                MonoTypeVariant::Tuple(monomorph) => {

                    let num_members = monomorph.members.len() as u32;

                    let mut tuple_result = TypeLoopResult::TypeExists;

                    while breadcrumb.next_member < num_members {

                        let tuple_member = &monomorph.members[breadcrumb.next_member as usize];

                        tuple_result = Self::check_member_for_type_loops(

                            &self.type_loop_breadcrumbs, &self.definition_lookup, &self.mono_type_lookup,

                            &mut self.mono_search_key, &tuple_member.concrete_type

                        );

                        if tuple_result != TypeLoopResult::TypeExists {

                            break;

                        }

                        breadcrumb.next_member += 1;

                    }

                    tuple_result

                }

            };

            // Handle the result of attempting to resolve the current breadcrumb

            match resolve_result {

                TypeLoopResult::TypeExists => {

                    // We finished parsing the type

                    self.type_loop_breadcrumbs.pop();

                },

                TypeLoopResult::PushBreadcrumb(definition_id, concrete_type) => {

                    // We recurse into the member type.

                    self.type_loop_breadcrumbs[breadcrumb_idx] = breadcrumb;

                    self.handle_new_breadcrumb_for_type_loops(definition_id, concrete_type);

                },

                TypeLoopResult::TypeLoop(first_idx) => {

                    // Because we will be modifying breadcrumbs within the

                    // type-loop handling code, put back the modified breadcrumb

                    self.type_loop_breadcrumbs[breadcrumb_idx] = breadcrumb;

                    // We're in a type loop. Add the type loop

                    let mut loop_members = Vec::with_capacity(self.type_loop_breadcrumbs.len() - first_idx);

        // TODO: Combine with code in pass_typing.rs

        fn parser_to_concrete_part(part: &ParserTypeVariant) -> Option<ConcreteTypePart> {

            match part {

                PTV::Void      => Some(CTP::Void),

                PTV::Message   => Some(CTP::Message),

                PTV::Bool      => Some(CTP::Bool),

                PTV::UInt8     => Some(CTP::UInt8),

                PTV::UInt16    => Some(CTP::UInt16),

                PTV::UInt32    => Some(CTP::UInt32),

                PTV::UInt64    => Some(CTP::UInt64),

                PTV::SInt8     => Some(CTP::SInt8),

                PTV::SInt16    => Some(CTP::SInt16),

                PTV::SInt32    => Some(CTP::SInt32),

                PTV::SInt64    => Some(CTP::SInt64),

                PTV::Character => Some(CTP::Character),

                PTV::String    => Some(CTP::String),

                PTV::Array     => Some(CTP::Array),

                PTV::Input     => Some(CTP::Input),

                PTV::Output    => Some(CTP::Output),

                PTV::Tuple(num) => Some(CTP::Tuple(*num)),

                PTV::Definition(definition_id, num) => Some(CTP::Instance(*definition_id, *num)),

                _              => None

            }

        }

        let mut parts = Vec::with_capacity(member_type.elements.len()); // usually a correct estimation, might not be

        for member_part in &member_type.elements {

            // Check if we have a regular builtin type

            if let Some(part) = parser_to_concrete_part(&member_part.variant) {

                parts.push(part);

                continue;

            }

            // Not builtin, but if all code is working correctly, we only care

            // about the polymorphic argument at this point.

            if let PTV::PolymorphicArgument(_container_definition_id, poly_arg_idx) = member_part.variant {

                debug_assert_eq!(_container_definition_id, get_concrete_type_definition(&container_type.parts).unwrap());

                let mut container_iter = container_type.embedded_iter(0);

                for _ in 0..poly_arg_idx {

                    container_iter.next();

                }

                let poly_section = container_iter.next().unwrap();

                parts.extend(poly_section);

                continue;

            }

            unreachable!("unexpected type part {:?} from {:?}", member_part, member_type);

        }

        return ConcreteType{ parts };

    }

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

    // Determining memory layout for types

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

    /// Should be called after type loops are detected (and resolved

    /// successfully). As a result of this call we expect the

    /// `encountered_types` array to be filled. We'll calculate size/alignment/

    /// offset values for those types in this routine.

    fn lay_out_memory_for_encountered_types(&mut self, arch: &TargetArch) {

        // Programmers note: this works like a little stack machine. We have

        // memory layout breadcrumbs which, like the type loop breadcrumbs, keep

        // track of the currently considered member type. This breadcrumb also

        // stores an index into the `size_alignment_stack`, which will be used

        // to store intermediate size/alignment pairs until all members are

        // resolved. Note that this `size_alignment_stack` is NOT an

        // optimization, we're working around borrowing rules here.

        // Just finished type loop detection, so we're left with the encountered

        // types only

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

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

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

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

        // Push the first entry (the type we originally started with when we

        // were detecting type loops)

        let first_entry = &self.encountered_types[0];

        self.memory_layout_breadcrumbs.push(MemoryBreadcrumb{

            type_id: first_entry.type_id,

            next_member: 0,

            next_embedded: 0,

            first_size_alignment_idx: 0,

        });

        // Enter the main resolving loop

        'breadcrumb_loop: while !self.memory_layout_breadcrumbs.is_empty() {

            let cur_breadcrumb_idx = self.memory_layout_breadcrumbs.len() - 1;

            let mut breadcrumb = self.memory_layout_breadcrumbs[cur_breadcrumb_idx].clone();

            let mono_type = &self.mono_types[breadcrumb.type_id.0 as usize];

            match &mono_type.variant {

                    // Size should already be computed

                    dbg_code!({

                        let mono_type = &self.mono_types[breadcrumb.type_id.0 as usize];

                        debug_assert!(mono_type.size != 0 && mono_type.alignment != 0);

                    });

                },

                MonoTypeVariant::Union(mono_type) => {

                    // Retrieve size/alignment of each embedded type. We do not

                    // compute the offsets or total type sizes yet.

                    let num_variants = mono_type.variants.len() as u32;

                    while breadcrumb.next_member < num_variants {

                        let mono_variant = &mono_type.variants[breadcrumb.next_member as usize];

                        if mono_variant.lives_on_heap {

                            // To prevent type loops we made this a heap-

                            // allocated variant. This implies we cannot

                            // compute sizes of members at this point.

                        } else {

                            let num_embedded = mono_variant.embedded.len() as u32;

                            while breadcrumb.next_embedded < num_embedded {

                                let mono_embedded = &mono_variant.embedded[breadcrumb.next_embedded as usize];

                                let layout_result = Self::get_memory_layout_or_breadcrumb(

                                    &self.definition_lookup, &self.mono_type_lookup, &self.mono_types,

                                    &mut self.mono_search_key, arch, &mono_embedded.concrete_type.parts,

                                    self.size_alignment_stack.len()

                                );

                                match layout_result {

                                    MemoryLayoutResult::TypeExists(size, alignment) => {

                                        self.size_alignment_stack.push((size, alignment));

                                    },

                                    MemoryLayoutResult::PushBreadcrumb(new_breadcrumb) => {

                                        self.memory_layout_breadcrumbs[cur_breadcrumb_idx] = breadcrumb;

                                        self.memory_layout_breadcrumbs.push(new_breadcrumb);

                                        continue 'breadcrumb_loop;

                                    }

                                }

                                breadcrumb.next_embedded += 1;

                            }

                        }

                        breadcrumb.next_member += 1;

                        breadcrumb.next_embedded = 0;

                    }

                    // If here then we can at least compute the stack size of

                    // the type, we'll have to come back at the very end to

                    // fill in the heap size/alignment/offset of each heap-

                    // allocated variant.

                    let mut max_size = mono_type.tag_size;

                    let mut max_alignment = mono_type.tag_size;

                    let mono_type = &mut self.mono_types[breadcrumb.type_id.0 as usize];

                    let union_type = mono_type.variant.as_union_mut();

                    let mut size_alignment_idx = breadcrumb.first_size_alignment_idx as usize;

                    for variant in &mut union_type.variants {

                        // We're doing stack computations, so always start with

                        // the tag size/alignment.

                        let mut variant_offset = union_type.tag_size;

                        let mut variant_alignment = union_type.tag_size;

                        if variant.lives_on_heap {

                            // Variant lives on heap, so just a pointer

                            let (ptr_size, ptr_align) = arch.pointer_size_alignment;

                            align_offset_to(&mut variant_offset, ptr_align);

                            variant_offset += ptr_size;

                            variant_alignment = variant_alignment.max(ptr_align);

                        } else {

                            // Variant lives on stack, so walk all embedded

                            // types.

                            for embedded in &mut variant.embedded {

                                let (size, alignment) = self.size_alignment_stack[size_alignment_idx];

                                embedded.size = size;

                                embedded.alignment = alignment;

                                size_alignment_idx += 1;

                                align_offset_to(&mut variant_offset, alignment);

                                embedded.offset = variant_offset;

                                variant_offset += size;

                                variant_alignment = variant_alignment.max(alignment);

                            }

                        };

                        max_size = max_size.max(variant_offset);

                        max_alignment = max_alignment.max(variant_alignment);

                    }

                    mono_type.size = max_size;

                    mono_type.alignment = max_alignment;

                    self.size_alignment_stack.truncate(breadcrumb.first_size_alignment_idx as usize);

                },

                MonoTypeVariant::Struct(mono_type) => {

                    // Retrieve size and alignment of each struct member. We'll