pub offset: usize,

}

/// Union monomorph

pub struct UnionMonomorph {

    pub variants: Vec<UnionMonomorphVariant>,

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

/// Key used to perform lookups in the monomorph table. It computes a hash of

/// the type while not taking the unused polymorphic variables of the base type

/// into account (e.g. `struct Foo<A,B>{ A field }`, here `B` is an unused

/// polymorphic variable).

struct MonomorphKey {

    parts: Vec<ConcreteTypePart>,

}

use std::hash::*;

impl Hash for MonomorphKey {

    fn hash<H: Hasher>(&self, state: &mut H) {

// Type table

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

// Programmer note: keep this struct free of dynamically allocated memory

#[derive(Clone)]

struct TypeLoopBreadcrumb {

    monomorph_idx: i32,

    next_member: u32,

    next_embedded: u32, // for unions, the index into the variant's embedded types

}

#[derive(Clone)]

struct MemoryBreadcrumb {

    monomorph_idx: i32,

}

#[derive(Debug, PartialEq, Eq)]

enum TypeLoopResult {

    TypeExists,

    PushBreadcrumb(DefinitionId, ConcreteType),

    TypeExists(usize, usize), // (size, alignment)

    PushBreadcrumb(MemoryBreadcrumb),

}

// TODO: @Optimize, initial memory-unoptimized implementation

struct TypeLoopEntry {

    monomorph_idx: i32,

    is_union: bool,

}

struct TypeLoop {

    members: Vec<TypeLoopEntry>

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

        self.type_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_index(&self, definition_id: &DefinitionId, type_parts: &[ConcreteTypePart]) -> Option<i32> {

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

        return self.mono_lookup.get_monomorph_index(type_parts, &base_type.poly_vars);

    }

            return Ok(idx);

        }

        // Doesn't exist, so instantiate a monomorph and determine its memory

        // layout.

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

        let mono_idx = self.encountered_types[0].monomorph_idx;

        self.lay_out_memory_for_encountered_types(arch);

        return Ok(mono_idx as i32);

    }

        Self::check_identifier_collision(

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

        )?;

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

        // Construct internal representation of component

        //  making sure that each is used in the body. For now, mark them all

        //  as required.

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

        // }

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

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

                    TypeLoopResult::TypeExists

                },

                    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;

                        breadcrumb.next_embedded = 0;

                        breadcrumb.next_member += 1

                    }

                    union_result

                },

                    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(&mono_field.concrete_type);

                        breadcrumb.next_member += 1;

                    }

                    struct_result

                },

                }

            };

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

            match resolve_result {

                TypeLoopResult::TypeExists => {

                    let mut contains_union = false;

                    for breadcrumb_idx in first_idx..self.type_loop_breadcrumbs.len() {

                        let breadcrumb = &mut self.type_loop_breadcrumbs[breadcrumb_idx];

                        let mut is_union = false;

                        // TODO: Match on monomorph directly here

                                // Mark the currently processed variant as requiring heap

                                // allocation, then advance the *embedded* type. The loop above

                                // will then take care of advancing it to the next *member*.

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

                                variant.lives_on_heap = true;

                                breadcrumb.next_embedded += 1;

                                is_union = true;

                                contains_union = true;

                            },

                            _ => {}, // else: we don't care for now

                        }

                        loop_members.push(TypeLoopEntry{

                            monomorph_idx: breadcrumb.monomorph_idx,

                            is_union

                        });

                    }

                    let new_type_loop = TypeLoop{ members: loop_members };

        // The next step is to figure out if all of the type loops can be

        // broken. A type loop can be broken if at least one union exists in the

        // loop and that union ended up having variants that are not part of

        // a type loop.

        fn type_loop_source_span_and_message<'a>(

            modules: &'a [Module], heap: &Heap, mono_lookup: &MonomorphTable,

        ) -> (&'a InputSource, InputSpan, String) {

            // Note: because we will discover the type loop the *first* time we

            // instantiate a monomorph with the provided polymorphic arguments

            // (not all arguments are actually used in the type). We don't have

            // to care about a second instantiation where certain unused

            // polymorphic arguments are different.

            let type_name = monomorph_type.display_name(&heap);

            let message = if index_in_loop == 0 {

                format!(

                    "encountered an infinitely large type for '{}' (which can be fixed by \

                    introducing a union type that has a variant whose embedded types are \

            } else if index_in_loop == 1 {

                format!("because it depends on the type '{}'", type_name)

            } else {

                format!("which depends on the type '{}'", type_name)

            };

            let ast_root_id = ast_definition.defined_in();

            return (

                &modules[ast_root_id.index as usize].source,

                ast_definition.identifier().span,

                message

            );

        }

        fn construct_type_loop_error(table: &TypeTable, type_loop: &TypeLoop, modules: &[Module], heap: &Heap) -> ParseError {

                let (first_module, first_span, first_message) = type_loop_source_span_and_message(

                );

            let mut error_counter = 1;

                let entry = &type_loop.members[member_idx];

                }

                let (module, span, message) = type_loop_source_span_and_message(

                );

                parse_error = parse_error.with_info_at_span(module, span, message);

                error_counter += 1;

            }

            parse_error

        for type_loop in &self.type_loops {

            let mut can_be_broken = false;

            debug_assert!(!type_loop.members.is_empty());

            for entry in &type_loop.members {

                if entry.is_union {

                    debug_assert!(!monomorph.variants.is_empty()); // otherwise it couldn't be part of the type loop

                    let has_stack_variant = monomorph.variants.iter().any(|variant| !variant.lives_on_heap);

                    if has_stack_variant {

                        can_be_broken = true;

                        break;

                    }

                        concrete_type: ConcreteType{ parts: Vec::from(section) },

                        size: 0,

                        alignment: 0,

                        offset: 0

                    });

                }

                    definition_type, &[],

                    MonomorphVariant::Tuple(TupleMonomorph{

                        members,

                    })

                );

            },

            CTP::Instance(_check_definition_id, _) => {

                debug_assert_eq!(definition_id, *_check_definition_id); // because this is how `definition_id` was determined

                let base_type = self.type_lookup.get_mut(&definition_id).unwrap();

                let monomorph_index = match &mut base_type.definition {

                    DTV::Enum(definition) => {

                        let mono_index = self.mono_lookup.insert_with_zero_size_and_alignment(

                            definition_type, &base_type.poly_vars, MonomorphVariant::Enum

                        );

                        mono_index

                    },

                    DTV::Union(definition) => {

                        // Create all the variants with their concrete types

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

                        }

                        let mono_index = self.mono_lookup.insert_with_zero_size_and_alignment(

                            definition_type, &base_type.poly_vars,

                            MonomorphVariant::Union(UnionMonomorph{

                                variants: mono_variants,

                                heap_size: 0,

                                heap_alignment: 0

                            })

                        );

                        is_union = true;

                monomorph_index

            },

            _ => unreachable!(),

        };

        self.encountered_types.push(TypeLoopEntry{

            monomorph_idx: monomorph_index,

            is_union,

        });

        self.type_loop_breadcrumbs.push(TypeLoopBreadcrumb{

            monomorph_idx: monomorph_index,

            next_member: 0,

            next_embedded: 0,

        });

    }

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

            monomorph_idx: first_entry.monomorph_idx,

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

                    // Size should already be computed

                },

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

                    // compute the offsets or total type sizes yet.

                    while breadcrumb.next_member < num_variants {

                        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 {

                            while breadcrumb.next_embedded < num_embedded {

                                match self.get_memory_layout_or_breadcrumb(arch, &mono_embedded.concrete_type.parts) {

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

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

                                    },

                                    MemoryLayoutResult::PushBreadcrumb(new_breadcrumb) => {

                                        self.memory_layout_breadcrumbs[cur_breadcrumb_idx] = breadcrumb;

                    }

                    // 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 mono_info = self.mono_lookup.get_mut(breadcrumb.monomorph_idx);

                    let mono_type = mono_info.variant.as_union_mut();

                    for variant in &mut mono_type.variants {

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

                        // the tag size/alignment.

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

                        max_size = max_size.max(variant_offset);

                        max_alignment = max_alignment.max(variant_alignment);

                    }

                    mono_info.size = max_size;

                    mono_info.alignment = max_alignment;

                },

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

                    // compute the offsets once all of those are known

                    while breadcrumb.next_member < num_fields {

                        match self.get_memory_layout_or_breadcrumb(arch, &mono_field.concrete_type.parts) {

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

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

                            },

                            MemoryLayoutResult::PushBreadcrumb(new_breadcrumb) => {

                    // Compute offsets and size of total type

                    let mut cur_offset = 0;

                    let mut max_alignment = 1;

                    let mono_info = self.mono_lookup.get_mut(breadcrumb.monomorph_idx);

                    let mono_type = mono_info.variant.as_struct_mut();

                    for field in &mut mono_type.fields {

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

                        field.size = size;

                        field.alignment = alignment;

                        size_alignment_idx += 1;

                        cur_offset += size;

                        max_alignment = max_alignment.max(alignment);

                    }

                    mono_info.size = cur_offset;

                    mono_info.alignment = max_alignment;

                },

                    unreachable!();

                    }

                    }

            }

            // If here, then we completely layed out the current type. So move

            // to the next breadcrumb

            self.memory_layout_breadcrumbs.pop();

        }

            CTP::Tuple(_) => {

                let mono_index = self.mono_lookup.get_monomorph_index(parts, &[]).unwrap();

                if let Some((size, alignment)) = self.mono_lookup.get_monomorph_size_alignment(mono_index) {

                    return MemoryLayoutResult::TypeExists(size, alignment);

                } else {

                    return MemoryLayoutResult::PushBreadcrumb(MemoryBreadcrumb{

                        monomorph_idx: mono_index,

                        next_member: 0,

                        next_embedded: 0,

                    })

                }

            },

            CTP::Instance(definition_id, _) => {

                // Retrieve entry and the specific monomorph index by applying

                // the full concrete type.

                let mono_index = self.mono_lookup.get_monomorph_index(parts, &entry.poly_vars).unwrap();

                if let Some((size, alignment)) = self.mono_lookup.get_monomorph_size_alignment(mono_index) {

                    return MemoryLayoutResult::TypeExists(size, alignment);

                } else {

                    return MemoryLayoutResult::PushBreadcrumb(MemoryBreadcrumb{

                        monomorph_idx: mono_index,

                        next_member: 0,

                        next_embedded: 0,

                    });

                }

            },

            CTP::Function(_, _) | CTP::Component(_, _) => {

                todo!("storage for 'function pointers'");

            }

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

// Generic utilities

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

fn has_equal_num_monomorphs(ctx: TestCtx, num: usize, definition_id: DefinitionId) -> (bool, usize) {

    // Again: inefficient, but its testing code

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

    let mut num_on_type = 0;

    for mono in &ctx.types.mono_lookup.monomorphs {

        match &mono.concrete_type.parts[0] {

    }

    (num_on_type == num, num_on_type)

}

fn has_monomorph(ctx: TestCtx, definition_id: DefinitionId, serialized_monomorph: &str) -> (Option<i32>, String) {

    // Note: full_buffer is just for error reporting

    let mut full_buffer = String::new();

    let mut has_match = None;

    full_buffer.push('[');

    let mut append_to_full_buffer = |concrete_type: &ConcreteType, mono_idx: usize| {