Changeset - d23aebafc979
[Not reviewed]
0 7 0
MH - 4 years ago 2021-12-14 17:08:09
contact@maxhenger.nl
Initial TypeTable rewrite to support Tuple size/alignment computations
7 files changed with 820 insertions and 621 deletions:
0 comments (0 inline, 0 general)
src/protocol/ast.rs
Show inline comments
 
@@ -480,7 +480,7 @@ impl<'a> Iterator for ParserTypeIter<'a> {
 

	
 
/// ConcreteType is the representation of a type after the type inference and
 
/// checker is finished. These are fully typed.
 
#[derive(Debug, Clone, Copy, Eq, PartialEq)]
 
#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)]
 
pub enum ConcreteTypePart {
 
    // Special types (cannot be explicitly constructed by the programmer)
 
    Void,
 
@@ -504,7 +504,7 @@ pub enum ConcreteTypePart {
 
}
 

	
 
impl ConcreteTypePart {
 
    fn num_embedded(&self) -> u32 {
 
    pub(crate) fn num_embedded(&self) -> u32 {
 
        use ConcreteTypePart::*;
 

	
 
        match self {
src/protocol/eval/executor.rs
Show inline comments
 
@@ -226,7 +226,6 @@ impl Prompt {
 
        };
 

	
 
        // Maybe do typechecking in the future?
 
        debug_assert!((monomorph_idx as usize) < _types.get_base_definition(&def).unwrap().definition.procedure_monomorphs().len());
 
        let new_frame = Frame::new(heap, def, monomorph_idx);
 
        let max_stack_size = new_frame.max_stack_size;
 
        prompt.frames.push(new_frame);
 
@@ -475,7 +474,7 @@ impl Prompt {
 
                        },
 
                        Expression::Select(expr) => {
 
                            let subject= cur_frame.expr_values.pop_back().unwrap();
 
                            let mono_data = types.get_procedure_expression_data(&cur_frame.definition, cur_frame.monomorph_idx);
 
                            let mono_data = types.get_procedure_monomorph(cur_frame.monomorph_idx);
 
                            let field_idx = mono_data.expr_data[expr.unique_id_in_definition as usize].field_or_monomorph_idx as u32;
 

	
 
                            // Note: same as above: clone if value lives on expr stack, simply
 
@@ -517,7 +516,7 @@ impl Prompt {
 
                                }
 
                                Literal::Integer(lit_value) => {
 
                                    use ConcreteTypePart as CTP;
 
                                    let def_types = types.get_procedure_expression_data(&cur_frame.definition, cur_frame.monomorph_idx);
 
                                    let def_types = types.get_procedure_monomorph(cur_frame.monomorph_idx);
 
                                    let concrete_type = &def_types.expr_data[expr.unique_id_in_definition as usize].expr_type;
 

	
 
                                    debug_assert_eq!(concrete_type.parts.len(), 1);
 
@@ -559,7 +558,7 @@ impl Prompt {
 
                            cur_frame.expr_values.push_back(value);
 
                        },
 
                        Expression::Cast(expr) => {
 
                            let mono_data = types.get_procedure_expression_data(&cur_frame.definition, cur_frame.monomorph_idx);
 
                            let mono_data = types.get_procedure_monomorph(cur_frame.monomorph_idx);
 
                            let output_type = &mono_data.expr_data[expr.unique_id_in_definition as usize].expr_type;
 

	
 
                            // Typechecking reduced this to two cases: either we
 
@@ -741,7 +740,7 @@ impl Prompt {
 
                                    }
 

	
 
                                    // Determine the monomorph index of the function we're calling
 
                                    let mono_data = types.get_procedure_expression_data(&cur_frame.definition, cur_frame.monomorph_idx);
 
                                    let mono_data = types.get_procedure_monomorph(cur_frame.monomorph_idx);
 
                                    let call_data = &mono_data.expr_data[expr.unique_id_in_definition as usize];
 

	
 
                                    // Push the new frame and reserve its stack size
 
@@ -974,7 +973,7 @@ impl Prompt {
 
                    "mismatch in expr stack size and number of arguments for new statement"
 
                );
 

	
 
                let mono_data = types.get_procedure_expression_data(&cur_frame.definition, cur_frame.monomorph_idx);
 
                let mono_data = types.get_procedure_monomorph(cur_frame.monomorph_idx);
 
                let expr_data = &mono_data.expr_data[call_expr.unique_id_in_definition as usize];
 

	
 
                // Note that due to expression value evaluation they exist in
src/protocol/mod.rs
Show inline comments
 
@@ -96,27 +96,30 @@ impl ProtocolDescription {
 
        }
 
        let definition_id = definition_id.unwrap();
 

	
 
        let definition = &self.heap[definition_id];
 
        if !definition.is_component() {
 
        let ast_definition = &self.heap[definition_id];
 
        if !ast_definition.is_component() {
 
            return Err(ComponentCreationError::DefinitionNotComponent);
 
        }
 

	
 
        // Make sure that the types of the provided value group matches that of
 
        // the expected types.
 
        let definition = definition.as_component();
 
        if !definition.poly_vars.is_empty() {
 
        let ast_definition = ast_definition.as_component();
 
        if !ast_definition.poly_vars.is_empty() {
 
            return Err(ComponentCreationError::DefinitionNotComponent);
 
        }
 

	
 
        // - check number of arguments
 
        let expr_data = self.types.get_procedure_expression_data(&definition_id, 0);
 
        if expr_data.arg_types.len() != arguments.values.len() {
 
        // - check number of arguments by retrieving the one instantiated
 
        //   monomorph
 
        let concrete_type = ConcreteType{ parts: vec![ConcreteTypePart::Component(definition_id, 0)] };
 
        let mono_index = self.types.get_procedure_monomorph_index(&definition_id, &concrete_type.parts).unwrap();
 
        let mono_type = self.types.get_procedure_monomorph(mono_index);
 
        if mono_type.arg_types.len() != arguments.values.len() {
 
            return Err(ComponentCreationError::InvalidNumArguments);
 
        }
 

	
 
        // - for each argument try to make sure the types match
 
        for arg_idx in 0..arguments.values.len() {
 
            let expected_type = &expr_data.arg_types[arg_idx];
 
            let expected_type = &mono_type.arg_types[arg_idx];
 
            let provided_value = &arguments.values[arg_idx];
 
            if !self.verify_same_type(expected_type, 0, &arguments, provided_value) {
 
                return Err(ComponentCreationError::InvalidArgumentType(arg_idx));
src/protocol/parser/pass_typing.rs
Show inline comments
 
@@ -980,10 +980,8 @@ impl PassTyping {
 

	
 
        let proc_base = ctx.types.get_base_definition(&element.definition_id).unwrap();
 
        if proc_base.is_polymorph {
 
            let proc_monos = proc_base.definition.procedure_monomorphs();
 
            let proc_mono = &(*proc_monos)[element.reserved_monomorph_idx as usize];
 

	
 
            for poly_arg in proc_mono.concrete_type.embedded_iter(0) {
 
            let monomorph = ctx.types.get_monomorph(element.reserved_monomorph_idx);
 
            for poly_arg in monomorph.concrete_type.embedded_iter(0) {
 
                self.poly_vars.push(ConcreteType{ parts: Vec::from(poly_arg) });
 
            }
 
        }
 
@@ -1526,7 +1524,7 @@ impl PassTyping {
 
                        ctx, extra_data.expr_id, &extra_data.poly_vars, first_concrete_part
 
                    )?;
 

	
 
                    match ctx.types.get_procedure_monomorph_index(&definition_id, &concrete_type) {
 
                    match ctx.types.get_procedure_monomorph_index(&definition_id, &concrete_type.parts) {
 
                        Some(reserved_idx) => {
 
                            // Already typechecked, or already put into the resolve queue
 
                            infer_expr.field_or_monomorph_idx = reserved_idx;
 
@@ -1575,18 +1573,18 @@ impl PassTyping {
 

	
 
        // Every expression checked, and new monomorphs are queued. Transfer the
 
        // expression information to the type table.
 
        let (definition_id, procedure_arguments) = match &self.definition_type {
 
        let procedure_arguments = match &self.definition_type {
 
            DefinitionType::Component(id) => {
 
                let definition = &ctx.heap[*id];
 
                (id.upcast(), &definition.parameters)
 
                &definition.parameters
 
            },
 
            DefinitionType::Function(id) => {
 
                let definition = &ctx.heap[*id];
 
                (id.upcast(), &definition.parameters)
 
                &definition.parameters
 
            },
 
        };
 

	
 
        let target = ctx.types.get_procedure_expression_data_mut(&definition_id, self.reserved_idx);
 
        let target = ctx.types.get_procedure_monomorph_mut(self.reserved_idx);
 
        debug_assert!(target.arg_types.is_empty()); // makes sure we never queue a procedure's type inferencing twice
 
        debug_assert!(target.expr_data.is_empty());
 

	
src/protocol/parser/type_table.rs
Show inline comments
 
@@ -97,137 +97,6 @@ pub struct DefinedType {
 
    pub(crate) is_polymorph: bool,
 
}
 

	
 
impl DefinedType {
 
    /// Returns the number of monomorphs that are instantiated. Remember that
 
    /// during the type loop detection, and the memory layout phase we will
 
    /// pre-allocate monomorphs which are not yet fully laid out in memory.
 
    pub(crate) fn num_monomorphs(&self) -> usize {
 
        use DefinedTypeVariant as DTV;
 
        match &self.definition {
 
            DTV::Enum(def) => def.monomorphs.len(),
 
            DTV::Union(def) => def.monomorphs.len(),
 
            DTV::Struct(def) => def.monomorphs.len(),
 
            DTV::Function(_) | DTV::Component(_) => unreachable!(),
 
        }
 
    }
 

	
 
    /// Returns the index at which a monomorph occurs. Will only check the
 
    /// polymorphic arguments that are in use (none of the, in rust lingo,
 
    /// phantom types). If the type is not polymorphic and its memory has been
 
    /// layed out, then this will always return `Some(0)`.
 
    pub(crate) fn get_monomorph_index(&self, parts: &[ConcreteTypePart]) -> Option<usize> {
 
        use DefinedTypeVariant as DTV;
 

	
 
        // Helper to compare two types, while disregarding the polymorphic
 
        // variables that are not in use.
 
        let concrete_types_match = |type_a: &[ConcreteTypePart], type_b: &[ConcreteTypePart], check_if_poly_var_is_used: bool| -> bool {
 
            let mut a_iter = ConcreteTypeIter::new(type_a, 0).enumerate();
 
            let mut b_iter = ConcreteTypeIter::new(type_b, 0);
 

	
 
            while let Some((section_idx, a_section)) = a_iter.next() {
 
                let b_section = b_iter.next().unwrap();
 

	
 
                if check_if_poly_var_is_used && !self.poly_vars[section_idx].is_in_use {
 
                    continue;
 
                }
 

	
 
                if a_section != b_section {
 
                    return false;
 
                }
 
            }
 

	
 
            return true;
 
        };
 

	
 
        // Check check if type is polymorphic to some degree at all
 
        if cfg!(debug_assertions) {
 
            if let ConcreteTypePart::Instance(definition_id, num_poly_args) = parts[0] {
 
                assert_eq!(definition_id, self.ast_definition);
 
                assert_eq!(num_poly_args as usize, self.poly_vars.len());
 
            } else {
 
                assert!(false, "concrete type {:?} is not a user-defined type", parts);
 
            }
 
        }
 

	
 
        match &self.definition {
 
            DTV::Enum(definition) => {
 
                // Special case, enum is never a "true polymorph"
 
                debug_assert!(!self.is_polymorph);
 
                if definition.monomorphs.is_empty() {
 
                    return None
 
                } else {
 
                    return Some(0)
 
                }
 
            },
 
            DTV::Union(definition) => {
 
                for (monomorph_idx, monomorph) in definition.monomorphs.iter().enumerate() {
 
                    if concrete_types_match(&monomorph.concrete_type.parts, parts, true) {
 
                        return Some(monomorph_idx);
 
                    }
 
                }
 
            },
 
            DTV::Struct(definition) => {
 
                for (monomorph_idx, monomorph) in definition.monomorphs.iter().enumerate() {
 
                    if concrete_types_match(&monomorph.concrete_type.parts, parts, true) {
 
                        return Some(monomorph_idx);
 
                    }
 
                }
 
            },
 
            DTV::Function(definition) => {
 
                for (monomorph_idx, monomorph) in definition.monomorphs.iter().enumerate() {
 
                    if concrete_types_match(&monomorph.concrete_type.parts, parts, false) {
 
                        return Some(monomorph_idx)
 
                    }
 
                }
 
            }
 
            DTV::Component(definition) => {
 
                for (monomorph_idx, monomorph) in definition.monomorphs.iter().enumerate() {
 
                    if concrete_types_match(&monomorph.concrete_type.parts, parts, false) {
 
                        return Some(monomorph_idx)
 
                    }
 
                }
 
            }
 
        }
 

	
 
        // Nothing matched
 
        return None;
 
    }
 

	
 
    /// Retrieves size and alignment of the particular type's monomorph if it
 
    /// has been layed out in memory.
 
    pub(crate) fn get_monomorph_size_alignment(&self, idx: usize) -> Option<(usize, usize)> {
 
        use DefinedTypeVariant as DTV;
 
        let (size, alignment) = match &self.definition {
 
            DTV::Enum(def) => {
 
                debug_assert!(idx == 0);
 
                (def.size, def.alignment)
 
            },
 
            DTV::Union(def) => {
 
                let monomorph = &def.monomorphs[idx];
 
                (monomorph.stack_size, monomorph.stack_alignment)
 
            },
 
            DTV::Struct(def) => {
 
                let monomorph = &def.monomorphs[idx];
 
                (monomorph.size, monomorph.alignment)
 
            },
 
            DTV::Function(_) | DTV::Component(_) => {
 
                // Type table should never be able to arrive here during layout
 
                // of types. Types may only contain function prototypes.
 
                unreachable!("retrieving size and alignment of procedure type");
 
            }
 
        };
 

	
 
        if size == 0 && alignment == 0 {
 
            // The "marker" for when the type has not been layed out yet. Even
 
            // for zero-size types we will set alignment to `1` to simplify
 
            // alignment calculations.
 
            return None;
 
        } else {
 
            return Some((size, alignment));
 
        }
 
    }
 
}
 

	
 
pub enum DefinedTypeVariant {
 
    Enum(EnumType),
 
    Union(UnionType),
 
@@ -288,26 +157,6 @@ impl DefinedTypeVariant {
 
            _ => unreachable!("Cannot convert {} to union variant", self.type_class())
 
        }
 
    }
 

	
 
    pub(crate) fn procedure_monomorphs(&self) -> &Vec<ProcedureMonomorph> {
 
        use DefinedTypeVariant::*;
 

	
 
        match self {
 
            Function(v) => &v.monomorphs,
 
            Component(v) => &v.monomorphs,
 
            _ => unreachable!("cannot get procedure monomorphs from {}", self.type_class()),
 
        }
 
    }
 

	
 
    pub(crate) fn procedure_monomorphs_mut(&mut self) -> &mut Vec<ProcedureMonomorph> {
 
        use DefinedTypeVariant::*;
 

	
 
        match self {
 
            Function(v) => &mut v.monomorphs,
 
            Component(v) => &mut v.monomorphs,
 
            _ => unreachable!("cannot get procedure monomorphs from {}", self.type_class()),
 
        }
 
    }
 
}
 

	
 
pub struct PolymorphicVariable {
 
@@ -322,7 +171,6 @@ pub struct PolymorphicVariable {
 
/// variants to be equal to one another.
 
pub struct EnumType {
 
    pub variants: Vec<EnumVariant>,
 
    pub monomorphs: Vec<EnumMonomorph>,
 
    pub minimum_tag_value: i64,
 
    pub maximum_tag_value: i64,
 
    pub tag_type: ConcreteType,
 
@@ -348,7 +196,6 @@ pub struct EnumVariant {
 
/// with a variant to a struct `B` that contains the union `A` again).
 
pub struct UnionType {
 
    pub variants: Vec<UnionVariant>,
 
    pub monomorphs: Vec<UnionMonomorph>,
 
    pub tag_type: ConcreteType,
 
    pub tag_size: usize,
 
}
 
@@ -363,7 +210,6 @@ pub struct UnionVariant {
 
/// type) type.
 
pub struct StructType {
 
    pub fields: Vec<StructField>,
 
    pub monomorphs: Vec<StructMonomorph>,
 
}
 

	
 
pub struct StructField {
 
@@ -376,13 +222,11 @@ pub struct StructField {
 
pub struct FunctionType {
 
    pub return_types: Vec<ParserType>,
 
    pub arguments: Vec<FunctionArgument>,
 
    pub monomorphs: Vec<ProcedureMonomorph>,
 
}
 

	
 
pub struct ComponentType {
 
    pub variant: ComponentVariant,
 
    pub arguments: Vec<FunctionArgument>,
 
    pub monomorphs: Vec<ProcedureMonomorph>
 
}
 

	
 
pub struct FunctionArgument {
 
@@ -407,30 +251,84 @@ pub struct MonomorphExpression {
 
// Type monomorph storage
 
//------------------------------------------------------------------------------
 

	
 
/// Union of all possible type monomorphs. The term "monomorph" is perhaps not
 
/// entirely correct: nonpolymorphic types will also get a "monomorph" entry to
 
/// store the size/offset/alignment data of all types.
 
enum TypeMonomorph {
 
    Enum(EnumMonomorph),
 
/// Generic monomorph has a specific concrete type, a size and an alignment.
 
/// Extra data is in the `MonomorphVariant` per kind of type.
 
pub(crate) struct TypeMonomorph {
 
    pub concrete_type: ConcreteType,
 
    pub size: usize,
 
    pub alignment: usize,
 
    pub variant: MonomorphVariant,
 
}
 

	
 
pub(crate) enum MonomorphVariant {
 
    Enum, // no extra data
 
    Struct(StructMonomorph),
 
    Union(UnionMonomorph),
 
    Procedure(ProcedureMonomorph), // functions, components
 
    Tuple(TupleMonomorph),
 
}
 

	
 
/// Enum monomorph
 
pub struct EnumMonomorph {
 
    pub concrete_type: ConcreteType,
 
    pub size: usize,
 
    pub alignment: usize,
 
impl MonomorphVariant {
 
    fn as_struct(&self) -> &StructMonomorph {
 
        match self {
 
            MonomorphVariant::Struct(v) => v,
 
            _ => unreachable!(),
 
        }
 
    }
 

	
 
    fn as_struct_mut(&mut self) -> &mut StructMonomorph {
 
        match self {
 
            MonomorphVariant::Struct(v) => v,
 
            _ => unreachable!(),
 
        }
 
    }
 

	
 
    pub(crate) fn as_union(&self) -> &UnionMonomorph {
 
        match self {
 
            MonomorphVariant::Union(v) => v,
 
            _ => unreachable!(),
 
        }
 
    }
 

	
 
    fn as_union_mut(&mut self) -> &mut UnionMonomorph {
 
        match self {
 
            MonomorphVariant::Union(v) => v,
 
            _ => unreachable!(),
 
        }
 
    }
 

	
 
    fn as_tuple(&self) -> &TupleMonomorph {
 
        match self {
 
            MonomorphVariant::Tuple(v) => v,
 
            _ => unreachable!(),
 
        }
 
    }
 

	
 
    fn as_tuple_mut(&mut self) -> &mut TupleMonomorph {
 
        match self {
 
            MonomorphVariant::Tuple(v) => v,
 
            _ => unreachable!(),
 
        }
 
    }
 

	
 
    fn as_procedure(&self) -> &ProcedureMonomorph {
 
        match self {
 
            MonomorphVariant::Procedure(v) => v,
 
            _ => unreachable!(),
 
        }
 
    }
 

	
 
    fn as_procedure_mut(&mut self) -> &mut ProcedureMonomorph {
 
        match self {
 
            MonomorphVariant::Procedure(v) => v,
 
            _ => unreachable!(),
 
        }
 
    }
 
}
 

	
 
/// Struct monomorph
 
pub struct StructMonomorph {
 
    pub concrete_type: ConcreteType,
 
    pub fields: Vec<StructMonomorphField>,
 
    pub size: usize,
 
    pub alignment: usize,
 
}
 

	
 
pub struct StructMonomorphField {
 
@@ -442,11 +340,10 @@ pub struct StructMonomorphField {
 

	
 
/// Union monomorph
 
pub struct UnionMonomorph {
 
    pub concrete_type: ConcreteType,
 
    pub variants: Vec<UnionMonomorphVariant>,
 
    // stack_size is the size of the union on the stack, includes the tag
 
    pub stack_size: usize,
 
    pub stack_alignment: usize,
 
    // 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.
 
@@ -476,7 +373,6 @@ pub struct UnionMonomorphEmbedded {
 
/// stores the expression type data from the typechecking/inferencing pass.
 
pub struct ProcedureMonomorph {
 
    // Expression data for one particular monomorph
 
    pub concrete_type: ConcreteType,
 
    pub arg_types: Vec<ConcreteType>,
 
    pub expr_data: Vec<MonomorphExpression>,
 
}
 
@@ -485,9 +381,6 @@ pub struct ProcedureMonomorph {
 
/// tuple type containing explicit polymorphic variables. But again: we need to
 
/// store size/offset/alignment information, so we do it here.
 
pub struct TupleMonomorph {
 
    pub concrete_type: ConcreteType,
 
    pub size: usize,
 
    pub alignment: usize,
 
    pub members: Vec<TupleMonomorphMember>
 
}
 

	
 
@@ -498,6 +391,171 @@ pub struct TupleMonomorphMember {
 
    pub offset: usize,
 
}
 

	
 
/// 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>,
 
    in_use: Vec<bool>,
 
}
 

	
 
use std::hash::*;
 

	
 
impl Hash for MonomorphKey {
 
    fn hash<H: Hasher>(&self, state: &mut H) {
 
        // if `in_use` is empty, then we may assume the type is not polymorphic
 
        // (or all types are in use)
 
        if self.in_use.is_empty() {
 
            self.parts.hash(state);
 
        } else {
 
            // type is polymorphic
 
            self.parts[0].hash(state);
 

	
 
            // note: hash is computed in a unique way, because practically
 
            // speaking `in_use` is fixed per base type. So we cannot have the
 
            // same base type (hence: a type with the same DefinitionId) with
 
            // different different polymorphic variables in use.
 
            let mut in_use_index = 0;
 
            for section in ConcreteTypeIter::new(self.parts.as_slice(), 0) {
 
                if self.in_use[in_use_index] {
 
                    section.hash(state);
 
                }
 
                in_use_index += 1;
 
            }
 
        }
 
    }
 
}
 

	
 
impl PartialEq for MonomorphKey {
 
    fn eq(&self, other: &Self) -> bool {
 
        if self.in_use.is_empty() {
 
            return self.parts == other.parts;
 
        } else {
 
            // Outer type does not match
 
            if self.parts[0] != other.parts[0] {
 
                return false;
 
            }
 

	
 
            debug_assert_eq!(self.parts[0].num_embedded() as usize, self.in_use.len());
 
            let mut iter_self = ConcreteTypeIter::new(self.parts.as_slice(), 0);
 
            let mut iter_other = ConcreteTypeIter::new(other.parts.as_slice(), 0);
 
            let mut index = 0;
 
            while let Some(section_self) = iter_self.next() {
 
                let section_other = iter_other.next().unwrap();
 
                let in_use = self.in_use[index];
 
                index += 1;
 

	
 
                if !in_use {
 
                    continue;
 
                }
 

	
 
                if section_self != section_other {
 
                    return false;
 
                }
 
            }
 

	
 
            return true;
 
        }
 
    }
 
}
 

	
 
impl Eq for MonomorphKey {}
 

	
 
use std::cell::UnsafeCell;
 

	
 
/// Lookup table for monomorphs. Wrapped in a special struct because we don't
 
/// want to allocate for each lookup (what we really want is a HashMap that
 
/// exposes it CompareFn and HashFn, but whatevs).
 
pub(crate) struct MonomorphTable {
 
    lookup: HashMap<MonomorphKey, i32>, // indexes into `monomorphs`
 
    pub(crate) monomorphs: Vec<TypeMonomorph>,
 
    // We use an UnsafeCell because this is only used internally per call to
 
    // `get_monomorph_index` calls. This is safe because `&TypeMonomorph`s
 
    // retrieved for this class remain valid when the key is mutated and the
 
    // type table is not multithreaded.
 
    //
 
    // I added this because we don't want to allocate for each lookup, hence we
 
    // need a reusable `key` internal to this class. This in turn makes
 
    // `get_monomorph_index` a mutable call. Now the code that calls this
 
    // function (even though we're not mutating the table!) needs a lot of extra
 
    // boilerplate. I opted for the `UnsafeCell` instead of the boilerplate.
 
    key: UnsafeCell<MonomorphKey>,
 
}
 

	
 
impl MonomorphTable {
 
    fn new() -> Self {
 
        return Self {
 
            lookup: HashMap::with_capacity(256),
 
            monomorphs: Vec::with_capacity(256),
 
            key: UnsafeCell::new(MonomorphKey{
 
                parts: Vec::with_capacity(32),
 
                in_use: Vec::with_capacity(32),
 
            })
 
        }
 
    }
 

	
 
    fn insert_with_zero_size_and_alignment(&mut self, concrete_type: ConcreteType, in_use: &[PolymorphicVariable], variant: MonomorphVariant) -> i32 {
 
        let key = MonomorphKey{
 
            parts: Vec::from(concrete_type.parts.as_slice()),
 
            in_use: in_use.iter().map(|v| v.is_in_use).collect(),
 
        };
 
        let index = self.monomorphs.len();
 
        let _result = self.lookup.insert(key, index as i32);
 
        debug_assert!(_result.is_none()); // did not exist yet
 
        self.monomorphs.push(TypeMonomorph{
 
            concrete_type,
 
            size: 0,
 
            alignment: 0,
 
            variant,
 
        });
 

	
 
        return index as i32;
 
    }
 

	
 
    fn get_monomorph_index(&self, parts: &[ConcreteTypePart], in_use: &[PolymorphicVariable]) -> Option<i32> {
 
        // Note: the entire goal of this internal `MonomorphKey` is to prevent
 
        // allocation. So:
 
        let key = unsafe {
 
            let key = &mut *self.key.get();
 
            key.parts.clear();
 
            key.parts.extend_from_slice(parts);
 
            key.in_use.clear();
 
            key.in_use.extend(in_use.iter().map(|v| v.is_in_use));
 

	
 
            &*key
 
        };
 

	
 
        match self.lookup.get(key) {
 
            Some(index) => return Some(*index),
 
            None => return None,
 
        }
 
    }
 

	
 
    #[inline]
 
    fn get(&self, index: i32) -> &TypeMonomorph {
 
        debug_assert!(index >= 0);
 
        return &self.monomorphs[index as usize];
 
    }
 

	
 
    #[inline]
 
    fn get_mut(&mut self, index: i32) -> &mut TypeMonomorph {
 
        debug_assert!(index >= 0);
 
        return &mut self.monomorphs[index as usize];
 
    }
 

	
 
    fn get_monomorph_size_alignment(&self, index: i32) -> Option<(usize, usize)> {
 
        let monomorph = self.get(index);
 
        if monomorph.size == 0 && monomorph.alignment == 0 {
 
            // If both are zero, then we wish to mean: we haven't actually
 
            // computed the size and alignment yet. So:
 
            return None;
 
        } else {
 
            return Some((monomorph.size, monomorph.alignment));
 
        }
 
    }
 
}
 

	
 
//------------------------------------------------------------------------------
 
// Type table
 
//------------------------------------------------------------------------------
 
@@ -505,16 +563,16 @@ pub struct TupleMonomorphMember {
 
// Programmer note: keep this struct free of dynamically allocated memory
 
#[derive(Clone)]
 
struct TypeLoopBreadcrumb {
 
    definition_id: DefinitionId,
 
    monomorph_idx: usize,
 
    next_member: usize,
 
    next_embedded: usize, // for unions, the index into the variant's embedded types
 
    definition_id: DefinitionId, // TODO: Check if it can be removed?
 
    monomorph_idx: i32,
 
    next_member: u32,
 
    next_embedded: u32, // for unions, the index into the variant's embedded types
 
}
 

	
 
#[derive(Clone)]
 
struct MemoryBreadcrumb {
 
    definition_id: DefinitionId,
 
    monomorph_idx: usize,
 
    monomorph_idx: i32,
 
    next_member: usize,
 
    next_embedded: usize,
 
    first_size_alignment_idx: usize,
 
@@ -535,7 +593,7 @@ enum MemoryLayoutResult {
 
// TODO: @Optimize, initial memory-unoptimized implementation
 
struct TypeLoopEntry {
 
    definition_id: DefinitionId,
 
    monomorph_idx: usize,
 
    monomorph_idx: i32,
 
    is_union: bool,
 
}
 

	
 
@@ -544,9 +602,10 @@ struct TypeLoop {
 
}
 

	
 
pub struct TypeTable {
 
    /// Lookup from AST DefinitionId to a defined type. Considering possible
 
    /// polymorphs is done inside the `DefinedType` struct.
 
    lookup: HashMap<DefinitionId, DefinedType>,
 
    /// Lookup from AST DefinitionId to a defined type. Also lookups for
 
    /// concrete type to monomorphs
 
    pub(crate) type_lookup: HashMap<DefinitionId, DefinedType>,
 
    pub(crate) mono_lookup: MonomorphTable,
 
    /// Breadcrumbs left behind while trying to find type loops. Also used to
 
    /// determine sizes of types when all type loops are detected.
 
    type_loop_breadcrumbs: Vec<TypeLoopBreadcrumb>,
 
@@ -563,7 +622,8 @@ impl TypeTable {
 
    /// Construct a new type table without any resolved types.
 
    pub(crate) fn new() -> Self {
 
        Self{ 
 
            lookup: HashMap::new(), 
 
            type_lookup: HashMap::with_capacity(128),
 
            mono_lookup: MonomorphTable::new(),
 
            type_loop_breadcrumbs: Vec::with_capacity(32),
 
            type_loops: Vec::with_capacity(8),
 
            encountered_types: Vec::with_capacity(32),
 
@@ -581,7 +641,7 @@ impl TypeTable {
 
    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());
 
        debug_assert!(self.type_lookup.is_empty());
 

	
 
        if cfg!(debug_assertions) {
 
            for (index, module) in modules.iter().enumerate() {
 
@@ -591,7 +651,7 @@ impl TypeTable {
 

	
 
        // Use context to guess hashmap size of the base types
 
        let reserve_size = ctx.heap.definitions.len();
 
        self.lookup.reserve(reserve_size);
 
        self.type_lookup.reserve(reserve_size);
 

	
 
        // Resolve all base types
 
        for definition_idx in 0..ctx.heap.definitions.len() {
 
@@ -607,7 +667,7 @@ impl TypeTable {
 
            }
 
        }
 

	
 
        debug_assert_eq!(self.lookup.len(), reserve_size, "mismatch in reserved size of type table"); // NOTE: Temp fix for builtin functions
 
        debug_assert_eq!(self.type_lookup.len(), reserve_size, "mismatch in reserved size of type table"); // NOTE: Temp fix for builtin functions
 
        for module in modules.iter_mut() {
 
            module.phase = ModuleCompilationPhase::TypesAddedToTable;
 
        }
 
@@ -617,13 +677,17 @@ impl TypeTable {
 
        // of 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.lookup.get(&definition_id).unwrap();
 
            let poly_type = self.type_lookup.get(&definition_id).unwrap();
 

	
 
            // Here we explicitly want to instantiate types which have no
 
            // polymorphic arguments (even if it has phantom polymorphic
 
            // arguments) because otherwise the user will see very weird
 
            // error messages.
 
            if poly_type.definition.type_class().is_data_type() && poly_type.poly_vars.is_empty() && poly_type.num_monomorphs() == 0 {
 
            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)];
 
            let mono_index = self.mono_lookup.get_monomorph_index(&concrete_parts, &[]);
 
            if mono_index.is_none() {
 
                self.detect_and_resolve_type_loops_for(
 
                    modules, ctx.heap,
 
                    ConcreteType{
 
@@ -641,34 +705,38 @@ impl TypeTable {
 
    /// 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.lookup.get(&definition_id)
 
        self.type_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: &ConcreteType) -> Option<i32> {
 
        let def = self.lookup.get(definition_id).unwrap();
 
        let monos = def.definition.procedure_monomorphs();
 
        return monos.iter()
 
            .position(|v| v.concrete_type == *types)
 
            .map(|v| v as i32);
 
    #[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);
 
    }
 

	
 
    #[inline]
 
    pub(crate) fn get_monomorph(&self, monomorph_index: i32) -> &TypeMonomorph {
 
        return self.mono_lookup.get(monomorph_index);
 
    }
 

	
 
    /// 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];
 
    #[inline]
 
    pub(crate) fn get_procedure_monomorph_mut(&mut self, monomorph_index: i32) -> &mut ProcedureMonomorph {
 
        debug_assert!(monomorph_index >= 0);
 
        let monomorph = self.mono_lookup.get_mut(monomorph_index);
 
        return monomorph.variant.as_procedure_mut();
 
    }
 

	
 
    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];
 
    #[inline]
 
    pub(crate) fn get_procedure_monomorph(&self, monomorph_index: i32) -> &ProcedureMonomorph {
 
        debug_assert!(monomorph_index >= 0);
 
        let monomorph = self.mono_lookup.get(monomorph_index);
 
        return monomorph.variant.as_procedure();
 
    }
 

	
 
    /// Reserves space for a monomorph of a polymorphic procedure. The index
 
@@ -677,19 +745,15 @@ impl TypeTable {
 
    /// 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, concrete_type: ConcreteType) -> i32 {
 
        let def = self.lookup.get_mut(definition_id).unwrap();
 
        let mono_types = def.definition.procedure_monomorphs_mut();
 
        debug_assert!(def.is_polymorph == (concrete_type.parts.len() != 1));
 
        debug_assert!(!mono_types.iter().any(|v| v.concrete_type == concrete_type));
 

	
 
        let mono_idx = mono_types.len();
 
        mono_types.push(ProcedureMonomorph{
 
            concrete_type,
 
            arg_types: Vec::new(),
 
            expr_data: Vec::new(),
 
        });
 

	
 
        return mono_idx as i32;
 
        let base_type = self.type_lookup.get_mut(definition_id).unwrap();
 
        let mono_index = self.mono_lookup.insert_with_zero_size_and_alignment(
 
            concrete_type, &base_type.poly_vars, MonomorphVariant::Procedure(ProcedureMonomorph{
 
                arg_types: Vec::new(),
 
                expr_data: Vec::new(),
 
            })
 
        );
 

	
 
        return mono_index;
 
    }
 

	
 
    /// Adds a datatype polymorph to the type table. Will not add the
 
@@ -702,9 +766,9 @@ impl TypeTable {
 
        debug_assert_eq!(definition_id, get_concrete_type_definition(&concrete_type));
 

	
 
        // Check if the monomorph already exists
 
        let poly_type = self.lookup.get_mut(&definition_id).unwrap();
 
        if let Some(idx) = poly_type.get_monomorph_index(&concrete_type.parts) {
 
            return Ok(idx as i32);
 
        let poly_type = self.type_lookup.get_mut(&definition_id).unwrap();
 
        if let Some(idx) = self.mono_lookup.get_monomorph_index(&concrete_type.parts, &poly_type.poly_vars) {
 
            return Ok(idx);
 
        }
 

	
 
        // Doesn't exist, so instantiate a monomorph and determine its memory
 
@@ -723,7 +787,7 @@ impl TypeTable {
 

	
 
    /// 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");
 
        debug_assert!(!self.type_lookup.contains_key(&definition_id), "base enum already built");
 
        let definition = ctx.heap[definition_id].as_enum();
 
        let root_id = definition.defined_in;
 

	
 
@@ -775,12 +839,11 @@ impl TypeTable {
 
        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 {
 
        self.type_lookup.insert(definition_id, DefinedType {
 
            ast_root: root_id,
 
            ast_definition: definition_id,
 
            definition: DefinedTypeVariant::Enum(EnumType{
 
                variants,
 
                monomorphs: Vec::new(),
 
                minimum_tag_value: min_enum_value,
 
                maximum_tag_value: max_enum_value,
 
                tag_type,
 
@@ -796,7 +859,7 @@ impl TypeTable {
 

	
 
    /// Builds the base type for a union. Will compute byte sizes.
 
    fn build_base_union_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, definition_id: DefinitionId) -> Result<(), ParseError> {
 
        debug_assert!(!self.lookup.contains_key(&definition_id), "base union already built");
 
        debug_assert!(!self.type_lookup.contains_key(&definition_id), "base union already built");
 
        let definition = ctx.heap[definition_id].as_union();
 
        let root_id = definition.defined_in;
 

	
 
@@ -841,15 +904,10 @@ impl TypeTable {
 

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

	
 
        self.lookup.insert(definition_id, DefinedType{
 
        self.type_lookup.insert(definition_id, DefinedType{
 
            ast_root: root_id,
 
            ast_definition: definition_id,
 
            definition: DefinedTypeVariant::Union(UnionType{
 
                variants,
 
                monomorphs: Vec::new(),
 
                tag_type,
 
                tag_size,
 
            }),
 
            definition: DefinedTypeVariant::Union(UnionType{ variants, tag_type, tag_size }),
 
            poly_vars,
 
            is_polymorph
 
        });
 
@@ -859,7 +917,7 @@ impl TypeTable {
 

	
 
    /// Builds base struct type. Will not compute byte sizes.
 
    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");
 
        debug_assert!(!self.type_lookup.contains_key(&definition_id), "base struct already built");
 
        let definition = ctx.heap[definition_id].as_struct();
 
        let root_id = definition.defined_in;
 

	
 
@@ -891,13 +949,10 @@ impl TypeTable {
 

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

	
 
        self.lookup.insert(definition_id, DefinedType{
 
        self.type_lookup.insert(definition_id, DefinedType{
 
            ast_root: root_id,
 
            ast_definition: definition_id,
 
            definition: DefinedTypeVariant::Struct(StructType{
 
                fields,
 
                monomorphs: Vec::new(),
 
            }),
 
            definition: DefinedTypeVariant::Struct(StructType{ fields }),
 
            poly_vars,
 
            is_polymorph
 
        });
 
@@ -907,7 +962,7 @@ impl TypeTable {
 

	
 
    /// Builds base function type.
 
    fn build_base_function_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, definition_id: DefinitionId) -> Result<(), ParseError> {
 
        debug_assert!(!self.lookup.contains_key(&definition_id), "base function already built");
 
        debug_assert!(!self.type_lookup.contains_key(&definition_id), "base function already built");
 
        let definition = ctx.heap[definition_id].as_function();
 
        let root_id = definition.defined_in;
 

	
 
@@ -949,14 +1004,10 @@ impl TypeTable {
 

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

	
 
        self.lookup.insert(definition_id, DefinedType{
 
        self.type_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(),
 
            }),
 
            definition: DefinedTypeVariant::Function(FunctionType{ return_types: definition.return_types.clone(), arguments }),
 
            poly_vars,
 
            is_polymorph
 
        });
 
@@ -966,7 +1017,7 @@ impl TypeTable {
 

	
 
    /// Builds base component type.
 
    fn build_base_component_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, definition_id: DefinitionId) -> Result<(), ParseError> {
 
        debug_assert!(!self.lookup.contains_key(&definition_id), "base component already built");
 
        debug_assert!(!self.type_lookup.contains_key(&definition_id), "base component already built");
 

	
 
        let definition = &ctx.heap[definition_id].as_component();
 
        let root_id = definition.defined_in;
 
@@ -999,14 +1050,10 @@ impl TypeTable {
 

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

	
 
        self.lookup.insert(definition_id, DefinedType{
 
        self.type_lookup.insert(definition_id, DefinedType{
 
            ast_root: root_id,
 
            ast_definition: definition_id,
 
            definition: DefinedTypeVariant::Component(ComponentType{
 
                variant: definition.variant,
 
                arguments,
 
                monomorphs: Vec::new()
 
            }),
 
            definition: DefinedTypeVariant::Component(ComponentType{ variant: definition.variant, arguments }),
 
            poly_vars,
 
            is_polymorph
 
        });
 
@@ -1135,6 +1182,27 @@ impl TypeTable {
 
    /// 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`.
 
        use DefinedTypeVariant as DTV;
 

	
 
        debug_assert!(self.type_loop_breadcrumbs.is_empty());
 
@@ -1155,62 +1223,83 @@ impl TypeTable {
 
            let breadcrumb_idx = self.type_loop_breadcrumbs.len() - 1;
 
            let mut breadcrumb = self.type_loop_breadcrumbs[breadcrumb_idx].clone();
 

	
 
            let poly_type = self.lookup.get(&breadcrumb.definition_id).unwrap();
 
            // TODO: Also don't need DefinitionId here. So then only need mono_index, so then just
 
            //  do a switch on the monomorph, not on the base type.
 
            let resolve_result = if breadcrumb.definition_id.is_invalid() {
 
                // We're dealing with a tuple
 
                let monomorph = self.mono_lookup.get(breadcrumb.monomorph_idx).variant.as_tuple();
 
                let num_members = monomorph.members.len() as u32;
 
                let mut tuple_result = TypeLoopResult::TypeExists;
 

	
 
            let resolve_result = match &poly_type.definition {
 
                DTV::Enum(_) => {
 
                    TypeLoopResult::TypeExists
 
                },
 
                DTV::Union(definition) => {
 
                    let monomorph = &definition.monomorphs[breadcrumb.monomorph_idx];
 
                    let num_variants = monomorph.variants.len();
 
                while breadcrumb.next_member < num_members {
 
                    let tuple_member = &monomorph.members[breadcrumb.next_member as usize];
 
                    tuple_result = self.check_member_for_type_loops(&tuple_member.concrete_type);
 

	
 
                    if tuple_result != TypeLoopResult::TypeExists {
 
                        break;
 
                    }
 

	
 
                    breadcrumb.next_member += 1;
 
                }
 

	
 
                    let mut union_result = TypeLoopResult::TypeExists;
 
                tuple_result
 
            } else {
 
                let poly_type = self.type_lookup.get(&breadcrumb.definition_id).unwrap();
 
                match &poly_type.definition {
 
                    DTV::Enum(_) => {
 
                        TypeLoopResult::TypeExists
 
                    },
 
                    DTV::Union(definition) => {
 
                        let monomorph = self.mono_lookup.get(breadcrumb.monomorph_idx).variant.as_union();
 
                        let num_variants = monomorph.variants.len() as u32;
 

	
 
                    'member_loop: while breadcrumb.next_member < num_variants {
 
                        let mono_variant = &monomorph.variants[breadcrumb.next_member];
 
                        let num_embedded = mono_variant.embedded.len();
 
                        let mut union_result = TypeLoopResult::TypeExists;
 

	
 
                        while breadcrumb.next_embedded < num_embedded {
 
                            let mono_embedded = &mono_variant.embedded[breadcrumb.next_embedded];
 
                            union_result = self.check_member_for_type_loops(&mono_embedded.concrete_type);
 
                        '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(&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;
 
                                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 += 1;
 
                            breadcrumb.next_embedded = 0;
 
                            breadcrumb.next_member += 1
 
                        }
 

	
 
                        breadcrumb.next_embedded = 0;
 
                        breadcrumb.next_member += 1
 
                    }
 
                        union_result
 
                    },
 
                    DTV::Struct(definition) => {
 
                        let monomorph = self.mono_lookup.get(breadcrumb.monomorph_idx).variant.as_struct();
 
                        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);
 

	
 
                            if struct_result != TypeLoopResult::TypeExists {
 
                                // Type loop or breadcrumb pushed, so break out of
 
                                // the resolving loop
 
                                break;
 
                            }
 

	
 
                    union_result
 
                },
 
                DTV::Struct(definition) => {
 
                    let monomorph = &definition.monomorphs[breadcrumb.monomorph_idx];
 
                    let num_fields = monomorph.fields.len();
 

	
 
                    let mut struct_result = TypeLoopResult::TypeExists;
 
                    while breadcrumb.next_member < num_fields {
 
                        let mono_field = &monomorph.fields[breadcrumb.next_member];
 
                        struct_result = self.check_member_for_type_loops(&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;
 
                        }
 

	
 
                        breadcrumb.next_member += 1;
 
                    }
 

	
 
                    struct_result
 
                },
 
                DTV::Function(_) | DTV::Component(_) => unreachable!(),
 
                        struct_result
 
                    },
 
                    DTV::Function(_) | DTV::Component(_) => unreachable!(),
 
                }
 
            };
 

	
 
            // Handle the result of attempting to resolve the current breadcrumb
 
@@ -1237,14 +1326,15 @@ impl TypeTable {
 
                        let breadcrumb = &mut self.type_loop_breadcrumbs[breadcrumb_idx];
 
                        let mut is_union = false;
 

	
 
                        let entry = self.lookup.get_mut(&breadcrumb.definition_id).unwrap();
 
                        let entry = self.type_lookup.get_mut(&breadcrumb.definition_id).unwrap();
 
                        // TODO: Match on monomorph directly here
 
                        match &mut entry.definition {
 
                            DTV::Union(definition) => {
 
                                // 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 monomorph = &mut definition.monomorphs[breadcrumb.monomorph_idx];
 
                                let variant = &mut monomorph.variants[breadcrumb.next_member];
 
                                let monomorph = self.mono_lookup.get_mut(breadcrumb.monomorph_idx).variant.as_union_mut();
 
                                let variant = &mut monomorph.variants[breadcrumb.next_member as usize];
 
                                variant.lives_on_heap = true;
 
                                breadcrumb.next_embedded += 1;
 
                                is_union = true;
 
@@ -1284,16 +1374,18 @@ impl TypeTable {
 
        // 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, defined_type: &DefinedType, monomorph_idx: usize, index_in_loop: usize
 
            modules: &'a [Module], heap: &Heap, mono_lookup: &MonomorphTable,
 
            defined_type: &DefinedType, monomorph_idx: i32, index_in_loop: usize
 
        ) -> (&'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.
 
            // TODO: Also remove match on defined_type, replace with mono lookup
 
            let monomorph_type = match &defined_type.definition {
 
                DTV::Union(definition) => &definition.monomorphs[monomorph_idx].concrete_type,
 
                DTV::Struct(definition) => &definition.monomorphs[monomorph_idx].concrete_type,
 
                DTV::Union(definition) => &mono_lookup.get(monomorph_idx).concrete_type,
 
                DTV::Struct(definition) => &mono_lookup.get(monomorph_idx).concrete_type,
 
                DTV::Enum(_) | DTV::Function(_) | DTV::Component(_) =>
 
                    unreachable!(), // impossible to have an enum/procedure in a type loop
 
            };
 
@@ -1324,19 +1416,26 @@ impl TypeTable {
 

	
 
        fn construct_type_loop_error(table: &TypeTable, type_loop: &TypeLoop, modules: &[Module], heap: &Heap) -> ParseError {
 
            let first_entry = &type_loop.members[0];
 
            let first_type = table.lookup.get(&first_entry.definition_id).unwrap();
 
            let first_type = table.type_lookup.get(&first_entry.definition_id).unwrap();
 
            let (first_module, first_span, first_message) = type_loop_source_span_and_message(
 
                modules, heap, first_type, first_entry.monomorph_idx, 0
 
                modules, heap, &table.mono_lookup, first_type, first_entry.monomorph_idx, 0
 
            );
 
            let mut parse_error = ParseError::new_error_at_span(first_module, first_span, first_message);
 

	
 
            let mut error_counter = 1;
 
            for member_idx in 1..type_loop.members.len() {
 
                let entry = &type_loop.members[member_idx];
 
                let entry_type = table.lookup.get(&first_entry.definition_id).unwrap();
 
                if entry.definition_id.is_invalid() {
 
                    // Don't display the tuples
 
                    continue;
 
                }
 

	
 
                let entry_type = table.type_lookup.get(&first_entry.definition_id).unwrap();
 
                let (module, span, message) = type_loop_source_span_and_message(
 
                    modules, heap, entry_type, entry.monomorph_idx, member_idx
 
                    modules, heap, &table.mono_lookup, entry_type, entry.monomorph_idx, error_counter
 
                );
 
                parse_error = parse_error.with_info_at_span(module, span, message);
 
                error_counter += 1;
 
            }
 

	
 
            parse_error
 
@@ -1348,13 +1447,12 @@ impl TypeTable {
 

	
 
            for entry in &type_loop.members {
 
                if entry.is_union {
 
                    let base_type = self.lookup.get(&entry.definition_id).unwrap();
 
                    let monomorph = &base_type.definition.as_union().monomorphs[entry.monomorph_idx];
 

	
 
                    let monomorph = &self.mono_lookup.get(entry.monomorph_idx).variant.as_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;
 
                    }
 
                }
 
            }
 
@@ -1382,26 +1480,32 @@ impl TypeTable {
 
    fn check_member_for_type_loops(&self, definition_type: &ConcreteType) -> TypeLoopResult {
 
        use ConcreteTypePart as CTP;
 

	
 
        // We're only interested in user-defined types, so exit if it is a
 
        // builtin of some sort.
 
        // Depending on the type, lookup if the type has already been visited
 
        // (i.e. either already has its memory layed out, or is part of a type
 
        // loop because we've already visited the type)
 
        debug_assert!(!definition_type.parts.is_empty());
 
        let definition_id = match &definition_type.parts[0] {
 
        let (definition_id, monomorph_index) = match &definition_type.parts[0] {
 
            CTP::Tuple(_) => {
 
                let monomorph_index = self.mono_lookup.get_monomorph_index(&definition_type.parts, &[]);
 

	
 
                (DefinitionId::new_invalid(), monomorph_index)
 
            },
 
            CTP::Instance(definition_id, _) |
 
            CTP::Function(definition_id, _) |
 
            CTP::Component(definition_id, _) => {
 
                *definition_id
 
                let base_type = self.type_lookup.get(definition_id).unwrap();
 
                let monomorph_index = self.mono_lookup.get_monomorph_index(&definition_type.parts, &base_type.poly_vars);
 

	
 
                (*definition_id, monomorph_index)
 
            },
 
            _ => {
 
                return TypeLoopResult::TypeExists
 
            },
 
        };
 

	
 
        let base_type = self.lookup.get(&definition_id).unwrap();
 
        if let Some(mono_idx) = base_type.get_monomorph_index(&definition_type.parts) {
 
            // Monomorph is already known. Check if it is present in the
 
            // breadcrumbs. If so, then we are in a type loop
 
        if let Some(monomorph_index) = monomorph_index {
 
            for (breadcrumb_idx, breadcrumb) in self.type_loop_breadcrumbs.iter().enumerate() {
 
                if breadcrumb.definition_id == definition_id && breadcrumb.monomorph_idx == mono_idx {
 
                if breadcrumb.monomorph_idx == monomorph_index {
 
                    return TypeLoopResult::TypeLoop(breadcrumb_idx);
 
                }
 
            }
 
@@ -1418,89 +1522,114 @@ impl TypeTable {
 
    /// call.
 
    fn handle_new_breadcrumb_for_type_loops(&mut self, definition_id: DefinitionId, definition_type: ConcreteType) {
 
        use DefinedTypeVariant as DTV;
 
        use ConcreteTypePart as CTP;
 

	
 
        let base_type = self.lookup.get_mut(&definition_id).unwrap();
 
        let mut is_union = false;
 
        let monomorph_idx = match &mut base_type.definition {
 
            DTV::Enum(definition) => {
 
                debug_assert!(definition.monomorphs.is_empty());
 
                definition.monomorphs.push(EnumMonomorph{
 
                    concrete_type: definition_type,
 
                    size: 0,
 
                    alignment: 0,
 
                });
 
                0
 
            },
 
            DTV::Union(definition) => {
 
                // Create all the variants with their concrete types
 
                let mut mono_variants = Vec::with_capacity(definition.variants.len());
 
                for poly_variant in &definition.variants {
 
                    let mut mono_embedded = Vec::with_capacity(poly_variant.embedded.len());
 
                    for poly_embedded in &poly_variant.embedded {
 
                        let mono_concrete = Self::construct_concrete_type(poly_embedded, &definition_type);
 
                        mono_embedded.push(UnionMonomorphEmbedded{
 
                            concrete_type: mono_concrete,
 
                            size: 0,
 
                            alignment: 0,
 
                            offset: 0
 
                        });
 
                    }
 

	
 
                    mono_variants.push(UnionMonomorphVariant{
 
                        lives_on_heap: false,
 
                        embedded: mono_embedded,
 
                    })
 
                }
 

	
 
                let mono_idx = definition.monomorphs.len();
 
                definition.monomorphs.push(UnionMonomorph{
 
                    concrete_type: definition_type,
 
                    variants: mono_variants,
 
                    stack_size: 0,
 
                    stack_alignment: 0,
 
                    heap_size: 0,
 
                    heap_alignment: 0
 
                });
 

	
 
                is_union = true;
 
                mono_idx
 
            },
 
            DTV::Struct(definition) => {
 
                let mut mono_fields = Vec::with_capacity(definition.fields.len());
 
                for poly_field in &definition.fields {
 
                    let mono_concrete = Self::construct_concrete_type(&poly_field.parser_type, &definition_type);
 
                    mono_fields.push(StructMonomorphField{
 
                        concrete_type: mono_concrete,
 
        let monomorph_index = match &definition_type.parts[0] {
 
            CTP::Tuple(num_embedded) => {
 
                debug_assert!(definition_id.is_invalid()); // because tuples do not have an associated `DefinitionId`
 
                let mut members = Vec::with_capacity(*num_embedded as usize);
 
                for section in ConcreteTypeIter::new(&definition_type.parts, 0) {
 
                    members.push(TupleMonomorphMember{
 
                        concrete_type: ConcreteType{ parts: Vec::from(section) },
 
                        size: 0,
 
                        alignment: 0,
 
                        offset: 0
 
                    })
 
                    });
 
                }
 
                let monomorph_index = self.mono_lookup.insert_with_zero_size_and_alignment(
 
                    definition_type, &[],
 
                    MonomorphVariant::Tuple(TupleMonomorph{
 
                        members,
 
                    })
 
                );
 

	
 
                let mono_idx = definition.monomorphs.len();
 
                definition.monomorphs.push(StructMonomorph{
 
                    concrete_type: definition_type,
 
                    fields: mono_fields,
 
                    size: 0,
 
                    alignment: 0
 
                });
 

	
 
                mono_idx
 
                monomorph_index
 
            },
 
            DTV::Function(_) | DTV::Component(_) => {
 
                unreachable!("pushing type resolving breadcrumb for procedure type")
 
            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) => {
 
                        // TODO: Is this correct?
 
                        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());
 
                        for poly_variant in &definition.variants {
 
                            let mut mono_embedded = Vec::with_capacity(poly_variant.embedded.len());
 
                            for poly_embedded in &poly_variant.embedded {
 
                                let mono_concrete = Self::construct_concrete_type(poly_embedded, &definition_type);
 
                                mono_embedded.push(UnionMonomorphEmbedded{
 
                                    concrete_type: mono_concrete,
 
                                    size: 0,
 
                                    alignment: 0,
 
                                    offset: 0
 
                                });
 
                            }
 

	
 
                            mono_variants.push(UnionMonomorphVariant{
 
                                lives_on_heap: false,
 
                                embedded: mono_embedded,
 
                            })
 
                        }
 

	
 
                        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;
 
                        mono_index
 
                    },
 
                    DTV::Struct(definition) => {
 
                        let mut mono_fields = Vec::with_capacity(definition.fields.len());
 
                        for poly_field in &definition.fields {
 
                            let mono_concrete = Self::construct_concrete_type(&poly_field.parser_type, &definition_type);
 
                            mono_fields.push(StructMonomorphField{
 
                                concrete_type: mono_concrete,
 
                                size: 0,
 
                                alignment: 0,
 
                                offset: 0
 
                            })
 
                        }
 

	
 
                        let mono_index = self.mono_lookup.insert_with_zero_size_and_alignment(
 
                            definition_type, &base_type.poly_vars,
 
                            MonomorphVariant::Struct(StructMonomorph{ fields: mono_fields })
 
                        );
 

	
 
                        mono_index
 
                    },
 
                    DTV::Function(_) | DTV::Component(_) => {
 
                        unreachable!("pushing type resolving breadcrumb for procedure type")
 
                    },
 
                };
 

	
 
                monomorph_index
 
            },
 
            _ => unreachable!(),
 
        };
 

	
 
        self.encountered_types.push(TypeLoopEntry{
 
            definition_id,
 
            monomorph_idx,
 
            monomorph_idx: monomorph_index,
 
            is_union,
 
        });
 

	
 
        self.type_loop_breadcrumbs.push(TypeLoopBreadcrumb{
 
            definition_id,
 
            monomorph_idx,
 
            monomorph_idx: monomorph_index,
 
            next_member: 0,
 
            next_embedded: 0,
 
        });
 
@@ -1574,7 +1703,18 @@ impl TypeTable {
 
    // 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.
 
        use DefinedTypeVariant as DTV;
 

	
 
        // Just finished type loop detection, so we're left with the encountered
 
@@ -1600,147 +1740,198 @@ impl TypeTable {
 
            let cur_breadcrumb_idx = self.memory_layout_breadcrumbs.len() - 1;
 
            let mut breadcrumb = self.memory_layout_breadcrumbs[cur_breadcrumb_idx].clone();
 

	
 
            let poly_type = self.lookup.get(&breadcrumb.definition_id).unwrap();
 
            match &poly_type.definition {
 
                DTV::Enum(definition) => {
 
                    // Size should already be computed
 
                    debug_assert!(definition.size != 0 && definition.alignment != 0);
 
                },
 
                DTV::Union(definition) => {
 
                    // Retrieve size/alignment of each embedded type. We do not
 
                    // compute the offsets or total type sizes yet.
 
                    let mono_type = &definition.monomorphs[breadcrumb.monomorph_idx];
 
                    let num_variants = mono_type.variants.len();
 
                    while breadcrumb.next_member < num_variants {
 
                        let mono_variant = &mono_type.variants[breadcrumb.next_member];
 

	
 
                        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();
 
                            while breadcrumb.next_embedded < num_embedded {
 
                                let mono_embedded = &mono_variant.embedded[breadcrumb.next_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;
 
                                        self.memory_layout_breadcrumbs.push(new_breadcrumb);
 
                                        continue 'breadcrumb_loop;
 
            // TODO: Same as above, replace lookup of base definition, should not
 
            //  be needed.
 
            if breadcrumb.definition_id.is_invalid() {
 
                // Handle tuple
 
                let mono_tuple = self.mono_lookup.get(breadcrumb.monomorph_idx).variant.as_tuple();
 
                let num_members = mono_tuple.members.len();
 
                while breadcrumb.next_member < num_members {
 
                    let mono_member = &mono_tuple.members[breadcrumb.next_member];
 
                    match self.get_memory_layout_or_breadcrumb(arch, &mono_member.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;
 
                            self.memory_layout_breadcrumbs.push(new_breadcrumb);
 
                            continue 'breadcrumb_loop;
 
                        },
 
                    }
 

	
 
                    breadcrumb.next_member += 1;
 
                }
 

	
 
                // If here then we can compute the memory layout of the tuple.
 
                let mut cur_offset = 0;
 
                let mut max_alignment = 0;
 

	
 
                let mono_info = self.mono_lookup.get_mut(breadcrumb.monomorph_idx);
 
                let mono_tuple = mono_info.variant.as_tuple_mut();
 
                let mut size_alignment_index = breadcrumb.first_size_alignment_idx;
 
                for member_index in 0..num_members {
 
                    let (member_size, member_alignment) = self.size_alignment_stack[size_alignment_index];
 
                    align_offset_to(&mut cur_offset, member_alignment);
 
                    size_alignment_index += 1;
 

	
 
                    let member = &mut mono_tuple.members[member_index];
 
                    member.size = member_size;
 
                    member.alignment = member_alignment;
 
                    member.offset = cur_offset;
 

	
 
                    cur_offset += member_size;
 
                    max_alignment = max_alignment.max(member_alignment);
 
                }
 

	
 
                mono_info.size = cur_offset;
 
                mono_info.alignment = max_alignment;
 
                self.size_alignment_stack.truncate(breadcrumb.first_size_alignment_idx);
 
            } else {
 
                let poly_type = self.type_lookup.get(&breadcrumb.definition_id).unwrap();
 
                match &poly_type.definition {
 
                    DTV::Enum(definition) => {
 
                        // Size should already be computed
 
                        debug_assert!(definition.size != 0 && definition.alignment != 0);
 
                        let mono_type = self.mono_lookup.get_mut(breadcrumb.monomorph_idx);
 
                        mono_type.size = definition.size;
 
                        mono_type.alignment = definition.alignment;
 
                    },
 
                    DTV::Union(definition) => {
 
                        // Retrieve size/alignment of each embedded type. We do not
 
                        // compute the offsets or total type sizes yet.
 
                        let mono_type = self.mono_lookup.get(breadcrumb.monomorph_idx).variant.as_union();
 
                        let num_variants = mono_type.variants.len();
 
                        while breadcrumb.next_member < num_variants {
 
                            let mono_variant = &mono_type.variants[breadcrumb.next_member];
 

	
 
                            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();
 
                                while breadcrumb.next_embedded < num_embedded {
 
                                    let mono_embedded = &mono_variant.embedded[breadcrumb.next_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;
 
                                            self.memory_layout_breadcrumbs.push(new_breadcrumb);
 
                                            continue 'breadcrumb_loop;
 
                                        }
 
                                    }
 
                                }
 

	
 
                                breadcrumb.next_embedded += 1;
 
                                    breadcrumb.next_embedded += 1;
 
                                }
 
                            }
 

	
 
                            breadcrumb.next_member += 1;
 
                            breadcrumb.next_embedded = 0;
 
                        }
 

	
 
                        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 = definition.tag_size;
 
                        let mut max_alignment = definition.tag_size;
 

	
 
                        let poly_type = self.type_lookup.get_mut(&breadcrumb.definition_id).unwrap();
 
                        let definition = poly_type.definition.as_union_mut();
 
                        let mono_info = self.mono_lookup.get_mut(breadcrumb.monomorph_idx);
 
                        let mono_type = mono_info.variant.as_union_mut();
 
                        let mut size_alignment_idx = breadcrumb.first_size_alignment_idx;
 

	
 
                        for variant in &mut mono_type.variants {
 
                            // We're doing stack computations, so always start with
 
                            // the tag size/alignment.
 
                            let mut variant_offset = definition.tag_size;
 
                            let mut variant_alignment = definition.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);
 
                                }
 
                            };
 

	
 
                    // 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 = definition.tag_size;
 
                    let mut max_alignment = definition.tag_size;
 

	
 
                    let poly_type = self.lookup.get_mut(&breadcrumb.definition_id).unwrap();
 
                    let definition = poly_type.definition.as_union_mut();
 
                    let mono_type = &mut definition.monomorphs[breadcrumb.monomorph_idx];
 
                    let mut size_alignment_idx = breadcrumb.first_size_alignment_idx;
 

	
 
                    for variant in &mut mono_type.variants {
 
                        // We're doing stack computations, so always start with
 
                        // the tag size/alignment.
 
                        let mut variant_offset = definition.tag_size;
 
                        let mut variant_alignment = definition.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);
 
                        }
 

	
 
                        max_size = max_size.max(variant_offset);
 
                        max_alignment = max_alignment.max(variant_alignment);
 
                    }
 
                        mono_info.size = max_size;
 
                        mono_info.alignment = max_alignment;
 
                        self.size_alignment_stack.truncate(breadcrumb.first_size_alignment_idx);
 
                    },
 
                    DTV::Struct(definition) => {
 
                        // Retrieve size and alignment of each struct member. We'll
 
                        // compute the offsets once all of those are known
 
                        let mono_type = self.mono_lookup.get(breadcrumb.monomorph_idx).variant.as_struct();
 
                        let num_fields = mono_type.fields.len();
 
                        while breadcrumb.next_member < num_fields {
 
                            let mono_field = &mono_type.fields[breadcrumb.next_member];
 

	
 
                            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) => {
 
                                    self.memory_layout_breadcrumbs[cur_breadcrumb_idx] = breadcrumb;
 
                                    self.memory_layout_breadcrumbs.push(new_breadcrumb);
 
                                    continue 'breadcrumb_loop;
 
                                },
 
                            }
 

	
 
                    mono_type.stack_size = max_size;
 
                    mono_type.stack_alignment = max_alignment;
 
                    self.size_alignment_stack.truncate(breadcrumb.first_size_alignment_idx);
 
                },
 
                DTV::Struct(definition) => {
 
                    // Retrieve size and alignment of each struct member. We'll
 
                    // compute the offsets once all of those are known
 
                    let mono_type = &definition.monomorphs[breadcrumb.monomorph_idx];
 
                    let num_fields = mono_type.fields.len();
 
                    while breadcrumb.next_member < num_fields {
 
                        let mono_field = &mono_type.fields[breadcrumb.next_member];
 

	
 
                        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) => {
 
                                self.memory_layout_breadcrumbs[cur_breadcrumb_idx] = breadcrumb;
 
                                self.memory_layout_breadcrumbs.push(new_breadcrumb);
 
                                continue 'breadcrumb_loop;
 
                            },
 
                            breadcrumb.next_member += 1;
 
                        }
 

	
 
                        breadcrumb.next_member += 1;
 
                    }
 
                        // Compute offsets and size of total type
 
                        let mut cur_offset = 0;
 
                        let mut max_alignment = 1;
 

	
 
                    // 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();
 
                        let mut size_alignment_idx = breadcrumb.first_size_alignment_idx;
 

	
 
                    let poly_type = self.lookup.get_mut(&breadcrumb.definition_id).unwrap();
 
                    let definition = poly_type.definition.as_struct_mut();
 
                    let mono_type = &mut definition.monomorphs[breadcrumb.monomorph_idx];
 
                    let mut size_alignment_idx = breadcrumb.first_size_alignment_idx;
 
                        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;
 

	
 
                    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;
 
                            align_offset_to(&mut cur_offset, alignment);
 
                            field.offset = cur_offset;
 

	
 
                        align_offset_to(&mut cur_offset, alignment);
 
                        field.offset = cur_offset;
 
                            cur_offset += size;
 
                            max_alignment = max_alignment.max(alignment);
 
                        }
 

	
 
                        cur_offset += size;
 
                        max_alignment = max_alignment.max(alignment);
 
                        mono_info.size = cur_offset;
 
                        mono_info.alignment = max_alignment;
 
                        self.size_alignment_stack.truncate(breadcrumb.first_size_alignment_idx);
 
                    },
 
                    DTV::Function(_) | DTV::Component(_) => {
 
                        unreachable!();
 
                    }
 

	
 
                    mono_type.size = cur_offset;
 
                    mono_type.alignment = max_alignment;
 
                    self.size_alignment_stack.truncate(breadcrumb.first_size_alignment_idx);
 
                },
 
                DTV::Function(_) | DTV::Component(_) => {
 
                    unreachable!();
 
                }
 
            }
 

	
 
@@ -1761,10 +1952,7 @@ impl TypeTable {
 

	
 
            // First pass, use buffer to store size/alignment to prevent
 
            // borrowing issues.
 
            let poly_type = self.lookup.get(&entry.definition_id).unwrap();
 
            let definition = poly_type.definition.as_union();
 
            let mono_type = &definition.monomorphs[entry.monomorph_idx];
 

	
 
            let mono_type = self.mono_lookup.get(entry.monomorph_idx).variant.as_union();
 
            for variant in &mono_type.variants {
 
                if !variant.lives_on_heap {
 
                    continue;
 
@@ -1783,9 +1971,7 @@ impl TypeTable {
 
            }
 

	
 
            // Second pass, apply the size/alignment values in our buffer
 
            let poly_type = self.lookup.get_mut(&entry.definition_id).unwrap();
 
            let definition = poly_type.definition.as_union_mut();
 
            let mono_type = &mut definition.monomorphs[entry.monomorph_idx];
 
            let mono_type = self.mono_lookup.get_mut(entry.monomorph_idx).variant.as_union_mut();
 

	
 
            let mut max_size = 0;
 
            let mut max_alignment = 1;
 
@@ -1827,11 +2013,13 @@ impl TypeTable {
 
        self.encountered_types.clear();
 
    }
 

	
 
    /// Attempts to compute size/alignment for the provided type. Note that this
 
    /// is called *after* type loops have been succesfully resolved. Hence we
 
    /// may assume that all monomorph entries exist, but we may not assume that
 
    /// those entries already have their size/alignment computed.
 
    fn get_memory_layout_or_breadcrumb(&self, arch: &TargetArch, parts: &[ConcreteTypePart]) -> MemoryLayoutResult {
 
        use ConcreteTypePart as CTP;
 

	
 
        // Before we do any fancy shenanigans, we need to check if the concrete
 
        // type actually requires laying out memory.
 
        debug_assert!(!parts.is_empty());
 
        let (builtin_size, builtin_alignment) = match parts[0] {
 
            CTP::Void   => (0, 1),
 
@@ -1851,49 +2039,32 @@ impl TypeTable {
 
            CTP::Slice => arch.array_size_alignment,
 
            CTP::Input => arch.port_size_alignment,
 
            CTP::Output => arch.port_size_alignment,
 
            CTP::Tuple(num_embedded) => {
 
                if num_embedded == 0 {
 
                    (0, 1)
 
            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 {
 
                    // TODO: This is a bit hacky: structs and unions are neatly
 
                    //  layed out element by element using the breadcrumbs, but
 
                    //  here we do special tuple checking. Tuples should be able
 
                    //  to get their own breadcrumbs for resolving (and storage
 
                    //  in the type table!)
 
                    debug_assert!(num_embedded > 1);
 
                    let mut total_size = 0;
 
                    let mut total_alignment = 1;
 
                    for embedded in ConcreteTypeIter::new(parts, 0) {
 
                        match self.get_memory_layout_or_breadcrumb(arch, embedded) {
 
                            MemoryLayoutResult::PushBreadcrumb(new_breadcrumb) => {
 
                                return MemoryLayoutResult::PushBreadcrumb(new_breadcrumb);
 
                            },
 
                            MemoryLayoutResult::TypeExists(embedded_size, embedded_alignment) => {
 
                                align_offset_to(&mut total_size, embedded_alignment);
 
                                total_size += embedded_size;
 
                                total_alignment = total_alignment.max(embedded_alignment);
 
                            }
 
                        }
 
                    }
 

	
 
                    (total_size, total_alignment)
 
                    return MemoryLayoutResult::PushBreadcrumb(MemoryBreadcrumb{
 
                        definition_id: DefinitionId::new_invalid(),
 
                        monomorph_idx: mono_index,
 
                        next_member: 0,
 
                        next_embedded: 0,
 
                        first_size_alignment_idx: self.size_alignment_stack.len(),
 
                    })
 
                }
 
            },
 
            CTP::Instance(definition_id, _) => {
 
                // Retrieve entry and the specific monomorph index by applying
 
                // the full concrete type.
 
                let entry = self.lookup.get(&definition_id).unwrap();
 
                let monomorph_idx = entry.get_monomorph_index(parts).unwrap();
 
                let entry = self.type_lookup.get(&definition_id).unwrap();
 
                let mono_index = self.mono_lookup.get_monomorph_index(parts, &entry.poly_vars).unwrap();
 

	
 
                // Check if this monomorph has its size and alignment layed out,
 
                // and if so: return it.
 
                if let Some((size, alignment)) = entry.get_monomorph_size_alignment(monomorph_idx) {
 
                    // Type has been layed out in memory
 
                if let Some((size, alignment)) = self.mono_lookup.get_monomorph_size_alignment(mono_index) {
 
                    return MemoryLayoutResult::TypeExists(size, alignment);
 
                } else {
 
                    return MemoryLayoutResult::PushBreadcrumb(MemoryBreadcrumb{
 
                        definition_id,
 
                        monomorph_idx,
 
                        monomorph_idx: mono_index,
 
                        next_member: 0,
 
                        next_embedded: 0,
 
                        first_size_alignment_idx: self.size_alignment_stack.len(),
src/protocol/tests/parser_monomorphs.rs
Show inline comments
 
@@ -51,7 +51,8 @@ fn test_enum_monomorphs() {
 
        "
 
    ).for_enum("Answer", |e| { e
 
        .assert_num_monomorphs(1)
 
        .assert_has_monomorph("Answer");
 
        .assert_has_monomorph("Answer")
 
        .assert_size_alignment("Answer", 1, 1);
 
    });
 

	
 
    // Note for reader: because the enum doesn't actually use the polymorphic
src/protocol/tests/utils.rs
Show inline comments
 
@@ -297,8 +297,8 @@ impl<'a> StructTester<'a> {
 
        self = self.assert_has_monomorph(monomorph);
 
        let (mono_idx, _) = has_monomorph(self.ctx, self.ast_def.this.upcast(), monomorph);
 
        let mono_idx = mono_idx.unwrap();
 
        let mono = self.ctx.types.get_monomorph(mono_idx);
 

	
 
        let mono = &self.type_def.monomorphs[mono_idx];
 
        assert!(
 
            mono.size == size && mono.alignment == alignment,
 
            "[{}] Expected (size,alignment) of ({}, {}), but got ({}, {}) for {}",
 
@@ -403,6 +403,20 @@ impl<'a> EnumTester<'a> {
 
        self
 
    }
 

	
 
    pub(crate) fn assert_size_alignment(mut self, serialized_monomorph: &str, size: usize, alignment: usize) -> Self {
 
        self = self.assert_has_monomorph(serialized_monomorph);
 
        let (has_monomorph, serialized) = has_monomorph(self.ctx, self.def.this.upcast(), serialized_monomorph);
 
        let mono_index = has_monomorph.unwrap();
 
        let mono = self.ctx.types.get_monomorph(mono_index);
 

	
 
        assert!(
 
            mono.size == size && mono.alignment == alignment,
 
            "[{}] Expected (size,alignment) of ({}, {}), but got ({}, {}) for {}",
 
            self.ctx.test_name, size, alignment, mono.size, mono.alignment, self.assert_postfix()
 
        );
 
        self
 
    }
 

	
 
    pub(crate) fn assert_postfix(&self) -> String {
 
        let mut v = String::new();
 
        v.push_str("Enum{ name: ");
 
@@ -462,14 +476,16 @@ impl<'a> UnionTester<'a> {
 
        self = self.assert_has_monomorph(serialized_monomorph);
 
        let (mono_idx, _) = has_monomorph(self.ctx, self.ast_def.this.upcast(), serialized_monomorph);
 
        let mono_idx = mono_idx.unwrap();
 
        let mono = &self.type_def.monomorphs[mono_idx];
 
        let mono_base = self.ctx.types.get_monomorph(mono_idx);
 
        let mono_union = mono_base.variant.as_union();
 

	
 
        assert!(
 
            stack_size == mono.stack_size && stack_alignment == mono.stack_alignment &&
 
                heap_size == mono.heap_size && heap_alignment == mono.heap_alignment,
 
            stack_size == mono_base.size && stack_alignment == mono_base.alignment &&
 
                heap_size == mono_union.heap_size && heap_alignment == mono_union.heap_alignment,
 
            "[{}] Expected (stack | heap) (size, alignment) of ({}, {} | {}, {}), but got ({}, {} | {}, {}) for {}",
 
            self.ctx.test_name,
 
            stack_size, stack_alignment, heap_size, heap_alignment,
 
            mono.stack_size, mono.stack_alignment, mono.heap_size, mono.heap_alignment,
 
            mono_base.size, mono_base.alignment, mono_union.heap_size, mono_union.heap_alignment,
 
            self.assert_postfix()
 
        );
 
        self
 
@@ -684,7 +700,12 @@ impl<'a> FunctionTester<'a> {
 
    fn eval_until_end(&self) -> (Prompt, Result<EvalContinuation, EvalError>) {
 
        use crate::protocol::*;
 

	
 
        let mut prompt = Prompt::new(&self.ctx.types, &self.ctx.heap, self.def.this.upcast(), 0, ValueGroup::new_stack(Vec::new()));
 
        // Assuming the function is not polymorphic
 
        let definition_id = self.def.this.upcast();
 
        let func_type = [ConcreteTypePart::Function(definition_id, 0)];
 
        let mono_index = self.ctx.types.get_procedure_monomorph_index(&definition_id, &func_type).unwrap();
 

	
 
        let mut prompt = Prompt::new(&self.ctx.types, &self.ctx.heap, self.def.this.upcast(), mono_index, ValueGroup::new_stack(Vec::new()));
 
        let mut call_context = FakeRunContext{};
 
        loop {
 
            let result = prompt.step(&self.ctx.types, &self.ctx.heap, &self.ctx.modules, &mut call_context);
 
@@ -728,7 +749,7 @@ impl<'a> VariableTester<'a> {
 

	
 
    pub(crate) fn assert_concrete_type(self, expected: &str) -> Self {
 
        // Lookup concrete type in type table
 
        let mono_data = self.ctx.types.get_procedure_expression_data(&self.definition_id, 0);
 
        let mono_data = get_procedure_monomorph(&self.ctx.heap, &self.ctx.types, self.definition_id);
 
        let concrete_type = &mono_data.expr_data[self.var_expr.unique_id_in_definition as usize].expr_type;
 

	
 
        // Serialize and check
 
@@ -762,7 +783,7 @@ impl<'a> ExpressionTester<'a> {
 

	
 
    pub(crate) fn assert_concrete_type(self, expected: &str) -> Self {
 
        // Lookup concrete type
 
        let mono_data = self.ctx.types.get_procedure_expression_data(&self.definition_id, 0);
 
        let mono_data = get_procedure_monomorph(&self.ctx.heap, &self.ctx.types, self.definition_id);
 
        let expr_index = self.expr.get_unique_id_in_definition();
 
        let concrete_type = &mono_data.expr_data[expr_index as usize].expr_type;
 

	
 
@@ -785,6 +806,23 @@ impl<'a> ExpressionTester<'a> {
 
    }
 
}
 

	
 
fn get_procedure_monomorph<'a>(heap: &Heap, types: &'a TypeTable, definition_id: DefinitionId) -> &'a ProcedureMonomorph {
 
    let ast_definition = &heap[definition_id];
 
    let func_type = if ast_definition.is_function() {
 
        [ConcreteTypePart::Function(definition_id, 0)]
 
    } else if ast_definition.is_component() {
 
        [ConcreteTypePart::Component(definition_id, 0)]
 
    } else {
 
        assert!(false);
 
        unreachable!()
 
    };
 

	
 
    let mono_index = types.get_procedure_monomorph_index(&definition_id, &func_type).unwrap();
 
    let mono_data = types.get_procedure_monomorph(mono_index);
 

	
 
    mono_data
 
}
 

	
 
//------------------------------------------------------------------------------
 
// Interface for failed compilation
 
//------------------------------------------------------------------------------
 
@@ -888,19 +926,27 @@ impl<'a> ErrorTester<'a> {
 
fn has_equal_num_monomorphs(ctx: TestCtx, num: usize, definition_id: DefinitionId) -> (bool, usize) {
 
    use DefinedTypeVariant::*;
 

	
 
    // Again: inefficient, but its testing code
 
    let type_def = ctx.types.get_base_definition(&definition_id).unwrap();
 
    let num_on_type = match &type_def.definition {
 
        Struct(v) => v.monomorphs.len(),
 
        Enum(v) => v.monomorphs.len(),
 
        Union(v) => v.monomorphs.len(),
 
        Function(v) => v.monomorphs.len(),
 
        Component(v) => v.monomorphs.len(),
 
    };
 
    let mut num_on_type = 0;
 

	
 
    for mono in &ctx.types.mono_lookup.monomorphs {
 
        match &mono.concrete_type.parts[0] {
 
            ConcreteTypePart::Instance(def_id, _) |
 
            ConcreteTypePart::Function(def_id, _) |
 
            ConcreteTypePart::Component(def_id, _) => {
 
                if *def_id == definition_id {
 
                    num_on_type += 1;
 
                }
 
            },
 
            _ => {},
 
        };
 
    }
 

	
 
    (num_on_type == num, num_on_type)
 
}
 

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

	
 
    let type_def = ctx.types.get_base_definition(&definition_id).unwrap();
 
@@ -919,34 +965,15 @@ fn has_monomorph(ctx: TestCtx, definition_id: DefinitionId, serialized_monomorph
 
        let first_idx = full_buffer.len();
 
        full_buffer.push_str(concrete_type.display_name(ctx.heap).as_str());
 
        if &full_buffer[first_idx..] == serialized_monomorph {
 
            has_match = Some(mono_idx);
 
            has_match = Some(mono_idx as i32);
 
        }
 

	
 
        full_buffer.push('"');
 
    };
 

	
 
    match &type_def.definition {
 
        Enum(definition) => {
 
            for (mono_idx, mono) in definition.monomorphs.iter().enumerate() {
 
                append_to_full_buffer(&mono.concrete_type, mono_idx);
 
            }
 
        },
 
        Union(definition) => {
 
            for (mono_idx, mono) in definition.monomorphs.iter().enumerate() {
 
                append_to_full_buffer(&mono.concrete_type, mono_idx);
 
            }
 
        },
 
        Struct(definition) => {
 
            for (mono_idx, mono) in definition.monomorphs.iter().enumerate() {
 
                append_to_full_buffer(&mono.concrete_type, mono_idx);
 
            }
 
        },
 
        Function(_) | Component(_) => {
 
            let monomorphs = type_def.definition.procedure_monomorphs();
 
            for (mono_idx, mono) in monomorphs.iter().enumerate() {
 
                append_to_full_buffer(&mono.concrete_type, mono_idx);
 
            }
 
        }
 
    // Bit wasteful, but this is (temporary?) testing code:
 
    for (mono_idx, mono) in ctx.types.mono_lookup.monomorphs.iter().enumerate() {
 
        append_to_full_buffer(&mono.concrete_type, mono_idx);
 
    }
 

	
 
    full_buffer.push(']');
0 comments (0 inline, 0 general)