Changeset - bc8ebcbecd22
Parent rev.
Child rev.
[Not reviewed]
0 2 0
MH - 4 years ago 2021-07-20 18:46:22
contact@maxhenger.nl
rewrite of type loop detection and memory layout, now correctly implemented
2 files changed with 560 insertions and 320 deletions:
src/protocol/ast.rs
111
src/protocol/parser/type_table.rs
449
320
0 comments (0 inline, 0 general)
src/protocol/ast.rs
➞
Show inline comments
 
@@ -526,6 +526,21 @@ impl Default for ConcreteType {
 
}
 

			




	
	
	
		
 
impl ConcreteType {

			




	
	
	
		
 
    /// Returns an iterator over the subtrees that are type arguments (e.g. an

			




	
	
	
		
 
    /// array element's type, or a polymorphic type's arguments) to the

			




	
	
	
		
 
    /// provided parent type (specified by its index in the `parts` array).

			




	
	
	
		
 
    pub(crate) fn embedded_iter<'a>(&'a self, parent_part_idx: usize) -> ConcreteTypeIter<'a> {

			




	
	
	
		
 
        let num_embedded = self.parts[parent_part_idx].num_embedded();

			




	
	
	
		
 
        return ConcreteTypeIter{

			




	
	
	
		
 
            concrete: self,

			




	
	
	
		
 
            idx_embedded: 0,

			




	
	
	
		
 
            num_embedded,

			




	
	
	
		
 
            part_idx: parent_part_idx + 1,

			




	
	
	
		
 
        }

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




	
	
	
		
 
    /// Given the starting position of a type tree, determine the exclusive

			




	
	
	
		
 
    /// ending index.

			




	
	
	
		
 
    pub(crate) fn subtree_end_idx(&self, start_idx: usize) -> usize {

			




	
	
	
		
 
        let mut depth = 1;

			




	
	
	
		
 
        let num_parts = self.parts.len();

			




	
	
		
 
@@ -544,6 +559,102 @@ impl ConcreteType {

			




	
	
	
		
 
        debug_assert!(false, "incorrectly constructed ConcreteType instance");

			




	
	
	
		
 
        return 0;

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




	
	
	
		
 
    /// Construct a human-readable name for the type. Because this performs

			




	
	
	
		
 
    /// a string allocation don't use it for anything else then displaying the

			




	
	
	
		
 
    /// type to the user.

			




	
	
	
		
 
    pub(crate) fn display_name(&self, heap: &Heap) -> String {

			




	
	
	
		
 
        let mut name = String::with_capacity(128);

			




	
	
	
		
 

			




	
	
	
		
 
        fn display_part(parts: &[ConcreteTypePart], heap: &Heap, mut idx: usize, target: &mut String) -> usize {

			




	
	
	
		
 
            use ConcreteTypePart as CTP;

			




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

			




	
	
	
		
 

			




	
	
	
		
 
            let cur_idx = idx;

			




	
	
	
		
 
            idx += 1; // increment by 1, because it always happens

			




	
	
	
		
 

			




	
	
	
		
 
            match parts[cur_idx] {

			




	
	
	
		
 
                CTP::Void => { target.push_str("void"); },

			




	
	
	
		
 
                CTP::Message => { target.push_str(KW_TYPE_MESSAGE_STR); },

			




	
	
	
		
 
                CTP::Bool => { target.push_str(KW_TYPE_BOOL_STR); },

			




	
	
	
		
 
                CTP::UInt8 => { target.push_str(KW_TYPE_UINT8_STR); },

			




	
	
	
		
 
                CTP::UInt16 => { target.push_str(KW_TYPE_UINT16_STR); },

			




	
	
	
		
 
                CTP::UInt32 => { target.push_str(KW_TYPE_UINT32_STR); },

			




	
	
	
		
 
                CTP::UInt64 => { target.push_str(KW_TYPE_UINT64_STR); },

			




	
	
	
		
 
                CTP::SInt8 => { target.push_str(KW_TYPE_SINT8_STR); },

			




	
	
	
		
 
                CTP::SInt16 => { target.push_str(KW_TYPE_SINT16_STR); },

			




	
	
	
		
 
                CTP::SInt32 => { target.push_str(KW_TYPE_SINT32_STR); },

			




	
	
	
		
 
                CTP::SInt64 => { target.push_str(KW_TYPE_SINT64_STR); },

			




	
	
	
		
 
                CTP::Character => { target.push_str(KW_TYPE_CHAR_STR); },

			




	
	
	
		
 
                CTP::String => { target.push_str(KW_TYPE_STRING_STR); },

			




	
	
	
		
 
                CTP::Array | CTP::Slice => {

			




	
	
	
		
 
                    idx = display_part(parts, heap, idx, target);

			




	
	
	
		
 
                    target.push_str("[]");

			




	
	
	
		
 
                },

			




	
	
	
		
 
                CTP::Input => {

			




	
	
	
		
 
                    target.push_str(KW_TYPE_IN_PORT_STR);

			




	
	
	
		
 
                    target.push('<');

			




	
	
	
		
 
                    idx = display_part(parts, heap, idx, target);

			




	
	
	
		
 
                    target.push('>');

			




	
	
	
		
 
                },

			




	
	
	
		
 
                CTP::Output => {

			




	
	
	
		
 
                    target.push_str(KW_TYPE_OUT_PORT_STR);

			




	
	
	
		
 
                    target.push('<');

			




	
	
	
		
 
                    idx = display_part(parts, heap, idx, target);

			




	
	
	
		
 
                    target.push('>');

			




	
	
	
		
 
                },

			




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

			




	
	
	
		
 
                    let definition = &heap[definition_id];

			




	
	
	
		
 
                    target.push_str(definition.identifier().value.as_str());

			




	
	
	
		
 

			




	
	
	
		
 
                    if num_poly_args != 0 {

			




	
	
	
		
 
                        target.push('<');

			




	
	
	
		
 
                        for poly_arg_idx in 0..num_poly_args {

			




	
	
	
		
 
                            if poly_arg_idx != 0 {

			




	
	
	
		
 
                                target.push(',');

			




	
	
	
		
 
                                idx = display_part(parts, heap, idx, target);

			




	
	
	
		
 
                            }

			




	
	
	
		
 
                        }

			




	
	
	
		
 
                        target.push('>');

			




	
	
	
		
 
                    }

			




	
	
	
		
 
                }

			




	
	
	
		
 
            }

			




	
	
	
		
 

			




	
	
	
		
 
            idx

			




	
	
	
		
 
        }

			




	
	
	
		
 

			




	
	
	
		
 
        let _final_idx = display_part(&self.parts, heap, 0, &mut target);

			




	
	
	
		
 
        debug_assert_eq!(_final_idx, self.parts.len());

			




	
	
	
		
 

			




	
	
	
		
 
        return name;

			




	
	
	
		
 
    }

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
#[derive(Debug)]

			




	
	
	
		
 
pub struct ConcreteTypeIter<'a> {

			




	
	
	
		
 
    concrete: &'a ConcreteType,

			




	
	
	
		
 
    idx_embedded: u32,

			




	
	
	
		
 
    num_embedded: u32,

			




	
	
	
		
 
    part_idx: usize,

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
impl<'a> Iterator for ConcreteTypeIter<'a> {

			




	
	
	
		
 
    type Item = &'a [ConcreteTypePart];

			




	
	
	
		
 

			




	
	
	
		
 
    fn next(&'a mut self) -> Option<Self::Item> {

			




	
	
	
		
 
        if self.idx_embedded == self.num_embedded {

			




	
	
	
		
 
            return None;

			




	
	
	
		
 
        }

			




	
	
	
		
 

			




	
	
	
		
 
        // Retrieve the subtree of interest

			




	
	
	
		
 
        let start_idx = self.part_idx;

			




	
	
	
		
 
        let end_idx = self.concrete.subtree_end_idx(start_idx);

			




	
	
	
		
 

			




	
	
	
		
 
        self.idx_embedded += 1;

			




	
	
	
		
 
        self.part_idx = end_idx;

			




	
	
	
		
 

			




	
	
	
		
 
        return Some(&self.concrete.parts[start_idx..end_idx]);

			




	
	
	
		
 
    }

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
#[derive(Debug, Clone, Copy)]

			




        

    


    
    

    

        

                

                    src/protocol/parser/type_table.rs
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -88,6 +88,7 @@ impl DefinedType {

			




	
	
	
		
 
    /// Checks if the monomorph at the specified index has polymorphic arguments

			




	
	
	
		
 
    /// that match the provided polymorphic arguments. Only the polymorphic

			




	
	
	
		
 
    /// variables that are in use by the type are checked.

			




	
	
	
		
 
    #[deprecated]

			




	
	
	
		
 
    pub(crate) fn monomorph_matches_poly_args(&self, monomorph_idx: usize, checking_poly_args: &[ConcreteType]) -> bool {

			




	
	
	
		
 
        use DefinedTypeVariant as DTV;

			




	
	
	
		
 

			




	
	
		
 
@@ -125,6 +126,7 @@ impl DefinedType {

			




	
	
	
		
 
    /// not contribute to the checking (e.g. an `enum` type will always return

			




	
	
	
		
 
    /// `true`, because it cannot embed its polymorphic variables). Returns the

			




	
	
	
		
 
    /// index of the matching monomorph.

			




	
	
	
		
 
    #[deprecated]

			




	
	
	
		
 
    pub(crate) fn has_monomorph(&self, poly_args: &[ConcreteType]) -> Option<usize> {

			




	
	
	
		
 
        use DefinedTypeVariant as DTV;

			




	
	
	
		
 

			




	
	
		
 
@@ -157,6 +159,76 @@ impl DefinedType {

			




	
	
	
		
 
        return None;

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




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

			




	
	
	
		
 
    pub(crate) fn get_monomorph_index(&self, concrete_type: &ConcreteType) -> 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: &ConcreteType, type_b: &ConcreteType| -> bool {

			




	
	
	
		
 
            let mut a_iter = type_a.embedded_iter(0).enumerate();

			




	
	
	
		
 
            let mut b_iter = type_b.embedded_iter(0);

			




	
	
	
		
 

			




	
	
	
		
 
            while let Some((section_idx, a_section)) = a_iter.next() {

			




	
	
	
		
 
                let b_section = b_iter.next();

			




	
	
	
		
 

			




	
	
	
		
 
                if !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) = concrete_type.parts[0] {

			




	
	
	
		
 
                assert_eq!(definition_id, self.ast_definition);

			




	
	
	
		
 
                assert_eq!(num_poly_args, self.poly_vars.len());

			




	
	
	
		
 
            } else {

			




	
	
	
		
 
                assert!(false, "concrete type {:?} is not a user-defined type", concrete_type);

			




	
	
	
		
 
            }

			




	
	
	
		
 
        }

			




	
	
	
		
 

			




	
	
	
		
 
        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, concrete_type) {

			




	
	
	
		
 
                        return Some(monomorph_idx);

			




	
	
	
		
 
                    }

			




	
	
	
		
 
                }

			




	
	
	
		
 
            },

			




	
	
	
		
 
            DTV::Struct(definition) => {

			




	
	
	
		
 
                for (monomorph_idx, monomorph) in definition.monomorphs.iter().enumerate() {

			




	
	
	
		
 
                    if concrete_types_match(&monomorph.concrete_type, concrete_type) {

			




	
	
	
		
 
                        return Some(monomorph_idx);

			




	
	
	
		
 
                    }

			




	
	
	
		
 
                }

			




	
	
	
		
 
            },

			




	
	
	
		
 
            DTV::Function(_) | DTV::Component(_) => {

			




	
	
	
		
 
                unreachable!("called get_monomorph_index on a procedure type");

			




	
	
	
		
 
            }

			




	
	
	
		
 
        }

			




	
	
	
		
 

			




	
	
	
		
 
        // Nothing matched

			




	
	
	
		
 
        return None;

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




	
	
	
		
 
    /// Retrieves size and alignment of the particular type's monomorph

			




	
	
	
		
 
    pub(crate) fn get_monomorph_size_alignment(&self, idx: usize) -> (usize, usize) {

			




	
	
	
		
 
        use DefinedTypeVariant as DTV;

			




	
	
		
 
@@ -270,11 +342,6 @@ pub struct PolymorphicVariable {

			




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

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
/// Data associated with a monomorphized datatype

			




	
	
	
		
 
pub struct DataMonomorph {

			




	
	
	
		
 
    pub poly_args: Vec<ConcreteType>,

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
/// Data associated with a monomorphized procedure type. Has the wrong name,

			




	
	
	
		
 
/// because it will also be used to store expression data for a non-polymorphic

			




	
	
	
		
 
/// procedure. (in that case, there will only ever be one)

			




	
	
		
 
@@ -306,7 +373,7 @@ pub struct EnumVariant {

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
pub struct EnumMonomorph {

			




	
	
	
		
 
    pub poly_args: Vec<ConcreteType>

			




	
	
	
		
 
    pub concrete_type: ConcreteType,

			




	
	
	
		
 
}

			




	
	
	
		
 

			




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

			




	
	
		
 
@@ -333,7 +400,7 @@ pub struct UnionVariant {

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
pub struct UnionMonomorph {

			




	
	
	
		
 
    pub poly_args: Vec<ConcreteType>,

			




	
	
	
		
 
    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,

			




	
	
		
 
@@ -376,7 +443,7 @@ pub struct StructField {

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
pub struct StructMonomorph {

			




	
	
	
		
 
    pub poly_args: Vec<ConcreteType>,

			




	
	
	
		
 
    pub concrete_type: ConcreteType,

			




	
	
	
		
 
    pub fields: Vec<StructMonomorphField>,

			




	
	
	
		
 
    pub size: usize,

			




	
	
	
		
 
    pub alignment: usize,

			




	
	
		
 
@@ -456,12 +523,42 @@ macro_rules! unwrap_lookup_result {

			




	
	
	
		
 
    }

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
struct TypeLoopBreadcrumb {

			




	
	
	
		
 
    definition_id: DefinitionId,

			




	
	
	
		
 
    monomorph_idx: usize,

			




	
	
	
		
 
    next_member: usize,

			




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

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
#[derive(PartialEq, Eq)]

			




	
	
	
		
 
enum BreadcrumbResult {

			




	
	
	
		
 
    TypeExists,

			




	
	
	
		
 
    PushedBreadcrumb,

			




	
	
	
		
 
    TypeLoop(usize), // index into vec of breadcrumbs at which the type matched

			




	
	
	
		
 
}

			




	
	
	
		
 

			




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

			




	
	
	
		
 
struct TypeLoopEntry {

			




	
	
	
		
 
    definition_id: DefinitionId,

			




	
	
	
		
 
    monomorph_idx: usize,

			




	
	
	
		
 
    is_union: bool,

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
struct TypeLoop {

			




	
	
	
		
 
    members: Vec<TypeLoopEntry>

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
pub struct TypeTable {

			




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

			




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

			




	
	
	
		
 
    lookup: HashMap<DefinitionId, DefinedType>,

			




	
	
	
		
 
    /// Breadcrumbs left behind while resolving embedded types

			




	
	
	
		
 
    breadcrumbs: Vec<LayoutBreadcrumb>,

			




	
	
	
		
 
    breadcrumbs_old: Vec<LayoutBreadcrumb>,

			




	
	
	
		
 
    /// Breadcrumbs left behind while trying to find type loops. Also used to

			




	
	
	
		
 
    /// determine sizes of types when all type loops are detected.

			




	
	
	
		
 
    breadcrumbs: Vec<TypeLoopBreadcrumb>,

			




	
	
	
		
 
    type_loops: Vec<TypeLoop>,

			




	
	
	
		
 
    encountered_types: Vec<TypeLoopEntry>,

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
impl TypeTable {

			




	
	
		
 
@@ -469,7 +566,7 @@ impl TypeTable {

			




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

			




	
	
	
		
 
        Self{ 

			




	
	
	
		
 
            lookup: HashMap::new(), 

			




	
	
	
		
 
            breadcrumbs: Vec::with_capacity(32),

			




	
	
	
		
 
            breadcrumbs_old: Vec::with_capacity(32),

			




	
	
	
		
 
        }

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




	
	
		
 
@@ -516,41 +613,8 @@ impl TypeTable {

			




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

			




	
	
	
		
 
        // polymorphic. This might cause us to lay out types that are monomorphs

			




	
	
	
		
 
        // of polymorphic types.

			




	
	
	
		
 
        let mut fake_poly_args = Vec::with_capacity(8);

			




	
	
	
		
 

			




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

			




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

			




	
	
	
		
 
            let base_type = self.lookup.get(&definition_id).unwrap();

			




	
	
	
		
 

			




	
	
	
		
 
            if !base_type.is_polymorph {

			




	
	
	
		
 
                if base_type.poly_vars.len() != 0 {

			




	
	
	
		
 
                    // TODO: @Rewrite, I really don't like this, there should be something living

			




	
	
	
		
 
                    //       underneath this code that is cleaner.

			




	
	
	
		
 
                    fake_poly_args.clear();

			




	
	
	
		
 
                    for _ in 0..base_type.poly_vars.len() {

			




	
	
	
		
 
                        fake_poly_args.push(ConcreteType{ parts: vec![ConcreteTypePart::UInt8] });

			




	
	
	
		
 
                    }

			




	
	
	
		
 
                }

			




	
	
	
		
 

			




	
	
	
		
 
                if !base_type.has_monomorph(&fake_poly_args) {

			




	
	
	
		
 
                    self.push_breadcrumb_for_definition(ctx, definition_id, fake_poly_args.clone());

			




	
	
	
		
 
                }

			




	
	
	
		
 

			




	
	
	
		
 
                while !self.breadcrumbs.is_empty() {

			




	
	
	
		
 
                    match self.layout_for_top_breadcrumb(modules, ctx)? {

			




	
	
	
		
 
                        LayoutResult::PopBreadcrumb => {

			




	
	
	
		
 
                            self.breadcrumbs.pop()

			




	
	
	
		
 
                        },

			




	
	
	
		
 
                        LayoutResult::PushBreadcrumb(definition_id, poly_args) => {

			




	
	
	
		
 
                            self.push_breadcrumb_for_definition(ctx, definition_id, poly_args);

			




	
	
	
		
 
                        },

			




	
	
	
		
 
                        LayoutResult::TypeLoop(breadcrumb_idx) => {

			




	
	
	
		
 

			




	
	
	
		
 
                        }

			




	
	
	
		
 
                    }

			




	
	
	
		
 
                }

			




	
	
	
		
 
            }

			




	
	
	
		
 
        }

			




	
	
	
		
 
        // TODO: Finish this

			




	
	
	
		
 

			




	
	
	
		
 
        Ok(())

			




	
	
	
		
 
    }

			




	
	
		
 
@@ -1063,225 +1127,339 @@ impl TypeTable {

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




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

			




	
	
	
		
 
    // Determining memory layout for types

			




	
	
	
		
 
    // Detecting type loops

			




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

			




	
	
	
		
 

			




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

			




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

			




	
	
	
		
 
        use DefinedTypeVariant as DTV;

			




	
	
	
		
 

			




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

			




	
	
	
		
 
        let top_definition_id = self.breadcrumbs.last().unwrap().definition_id;

			




	
	
	
		
 
        match self.lookup.get(&top_definition_id).unwrap().definition {

			




	
	
	
		
 
            DTV::Enum(_) => self.layout_for_top_enum_breadcrumb(modules, ctx),

			




	
	
	
		
 
            DTV::Union(_) => self.layout_for_top_union_breadcrumb(modules, ctx),

			




	
	
	
		
 
            DTV::Struct(_) => self.layout_for_top_struct_breadcrumb(modules, ctx),

			




	
	
	
		
 
            DTV::Function(_) => self.layout_for_top_function_breadcrumb(modules, ctx),

			




	
	
	
		
 
            DTV::Component(_) => self.layout_for_top_component_breadcrumb(modules, ctx),

			




	
	
	
		
 
        }

			




	
	
	
		
 
    }

			




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

			




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

			




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

			




	
	
	
		
 

			




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

			




	
	
	
		
 
        // Enums are a bit special, because they never use their polymorphic

			




	
	
	
		
 
        // variables. So they only have to be layed out once. But this is

			




	
	
	
		
 
        // already done when laying out the base type.

			




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

			




	
	
	
		
 
        let definition = self.lookup.get_mut(&breadcrumb.definition_id).unwrap().definition.as_enum_mut();

			




	
	
	
		
 
        // Push the initial breadcrumb

			




	
	
	
		
 
        let _initial_result = self.push_breadcrumb_for(get_concrete_type_definition(&concrete_type), &concrete_type);

			




	
	
	
		
 
        debug_assert_eq!(_initial_result, BreadcrumbResult::PushedBreadcrumb);

			




	
	
	
		
 

			




	
	
	
		
 
        debug_assert!(definition.monomorphs.len() == 1 && breadcrumb.monomorph_idx == 0);

			




	
	
	
		
 
        // Enter into the main resolving loop

			




	
	
	
		
 
        while !self.breadcrumbs.is_empty() {

			




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

			




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

			




	
	
	
		
 

			




	
	
	
		
 
        return Ok(LayoutResult::PopBreadcrumb);

			




	
	
	
		
 
    }

			




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

			




	
	
	
		
 

			




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

			




	
	
	
		
 
        // Resolve each variant and embedded type until all sizes can be

			




	
	
	
		
 
        // computed.

			




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

			




	
	
	
		
 
        let definition = self.lookup.get_mut(&breadcrumb.definition_id).unwrap();

			




	
	
	
		
 
        debug_assert!(definition.poly_vars.len() == poly_args.len() || !definition.is_polymorph);

			




	
	
	
		
 
        let type_poly = definition.definition.as_union_mut();

			




	
	
	
		
 
        let type_mono = &mut type_poly.monomorphs[breadcrumb.monomorph_idx];

			




	
	
	
		
 

			




	
	
	
		
 
        let num_variants = type_poly.variants.len();

			




	
	
	
		
 
        while breadcrumb.next_member < num_variants {

			




	
	
	
		
 
            let poly_variant = &type_poly.variants[breadcrumb.next_member];

			




	
	
	
		
 
            let mono_variant = &mut type_mono.variants[breadcrumb.next_member];

			




	
	
	
		
 
            let num_embedded = poly_variant.embedded.len();

			




	
	
	
		
 

			




	
	
	
		
 
            while breadcrumb.next_embedded < num_embedded {

			




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

			




	
	
	
		
 
                let poly_embedded = &poly_variant.embedded[breadcrumb.next_embedded];

			




	
	
	
		
 
                let (concrete_type, size, alignment) = unwrap_lookup_result!(

			




	
	
	
		
 
                    self.lookup_layout_for_member_type(poly_embedded, &type_mono.poly_args)

			




	
	
	
		
 
                );

			




	
	
	
		
 
            // TODO: Misuse of BreadcrumbResult enum?

			




	
	
	
		
 
            let resolve_result = match &poly_type.definition {

			




	
	
	
		
 
                DTV::Enum(_) => {

			




	
	
	
		
 
                    BreadcrumbResult::TypeExists

			




	
	
	
		
 
                },

			




	
	
	
		
 
                DTV::Union(definition) => {

			




	
	
	
		
 
                    let monomorph = &definition.monomorphs[breadcrumb.monomorph_idx];

			




	
	
	
		
 
                    let num_variants = monomorph.variants.len();

			




	
	
	
		
 

			




	
	
	
		
 
                mono_embedded.concrete_type = concrete_type;

			




	
	
	
		
 
                mono_embedded.size = size;

			




	
	
	
		
 
                mono_embedded.alignment = alignment;

			




	
	
	
		
 
                    let mut union_result = BreadcrumbResult::TypeExists;

			




	
	
	
		
 

			




	
	
	
		
 
                breadcrumb.next_embedded += 1;

			




	
	
	
		
 
            }

			




	
	
	
		
 
                    'member_loop: while breadcrumb.next_member < num_variants {

			




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

			




	
	
	
		
 
                        let num_embedded = mono_variant.embedded.len();

			




	
	
	
		
 

			




	
	
	
		
 
            breadcrumb.next_embedded = 0;

			




	
	
	
		
 
            breadcrumb.next_member += 1;

			




	
	
	
		
 
        }

			




	
	
	
		
 
                        while breadcrumb.next_embedded < num_embedded {

			




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

			




	
	
	
		
 
                            union_result = self.push_breadcrumb_for(poly_type.ast_definition, &mono_embedded.concrete_type);

			




	
	
	
		
 

			




	
	
	
		
 
        // If here then each variant, and each therein embedded type, has been

			




	
	
	
		
 
        // found and resolved. But during repeated iteration we might have

			




	
	
	
		
 
        // encountered a type loop. This will have forced some union members to

			




	
	
	
		
 
        // be heap allocated.

			




	
	
	
		
 
                            if union_result != BreadcrumbResult::TypeExists {

			




	
	
	
		
 
                                // In type loop or new breadcrumb pushed, so

			




	
	
	
		
 
                                // break out of the resolving loop

			




	
	
	
		
 
                                break 'member_loop;

			




	
	
	
		
 
                            }

			




	
	
	
		
 

			




	
	
	
		
 
        let mut stack_size = type_poly.tag_size;

			




	
	
	
		
 
        let mut stack_alignment = type_poly.tag_size;

			




	
	
	
		
 
        let mut has_stack_variant = false;

			




	
	
	
		
 
                            breadcrumb.next_embedded += 1;

			




	
	
	
		
 
                        }

			




	
	
	
		
 

			




	
	
	
		
 
        let mut heap_size = 0;

			




	
	
	
		
 
        let mut heap_alignment = 1;

			




	
	
	
		
 
                        breadcrumb.next_embedded = 0;

			




	
	
	
		
 
                        breadcrumb.next_member += 1

			




	
	
	
		
 
                    }

			




	
	
	
		
 

			




	
	
	
		
 
        // Go through all variants and apply their alignment/offsets to compute

			




	
	
	
		
 
        // the stack and heap size.

			




	
	
	
		
 
        for variant in &mut type_mono.variants {

			




	
	
	
		
 
            let mut variant_offset = 0;

			




	
	
	
		
 
            let mut variant_alignment = 1;

			




	
	
	
		
 
                    union_result

			




	
	
	
		
 
                },

			




	
	
	
		
 
                DTV::Struct(definition) => {

			




	
	
	
		
 
                    let monomorph = &definition.monomorphs[breadcrumb.monomorph_idx];

			




	
	
	
		
 
                    let num_fields = monomorph.fields.len();

			




	
	
	
		
 

			




	
	
	
		
 
                    let mut struct_result = BreadcrumbResult::TypeExists;

			




	
	
	
		
 
                    while breadcrumb.next_member < num_fields {

			




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

			




	
	
	
		
 
                        struct_result = self.push_breadcrumb_for(poly_type.ast_definition, &mono_field.concrete_type);

			




	
	
	
		
 

			




	
	
	
		
 
                        if struct_result != BreadcrumbResult::TypeExists {

			




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

			




	
	
	
		
 
                            // the resolving loop

			




	
	
	
		
 
                            break;

			




	
	
	
		
 
                        }

			




	
	
	
		
 

			




	
	
	
		
 
            if !variant.lives_on_heap {

			




	
	
	
		
 
                variant_offset = type_poly.tag_size;

			




	
	
	
		
 
                variant_alignment = type_poly.tag_size;

			




	
	
	
		
 
            }

			




	
	
	
		
 
                        breadcrumb.next_member += 1;

			




	
	
	
		
 
                    }

			




	
	
	
		
 

			




	
	
	
		
 
            for embedded in &mut variant.embedded {

			




	
	
	
		
 
                align_offset_to(&mut variant_offset, embedded.alignment);

			




	
	
	
		
 
                embedded.offset = variant_offset;

			




	
	
	
		
 
                    struct_result,

			




	
	
	
		
 
                },

			




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

			




	
	
	
		
 
            };

			




	
	
	
		
 

			




	
	
	
		
 
                variant_offset += embedded.size;

			




	
	
	
		
 
                variant_alignment = variant_alignment.max(embedded.alignment);

			




	
	
	
		
 
            }

			




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

			




	
	
	
		
 
            match resolve_result {

			




	
	
	
		
 
                BreadcrumbResult::TypeExists => {

			




	
	
	
		
 
                    // We finished parsing the type

			




	
	
	
		
 
                    self.breadcrumbs.pop();

			




	
	
	
		
 
                },

			




	
	
	
		
 
                BreadcrumbResult::PushedBreadcrumb => {

			




	
	
	
		
 
                    // We recurse into the member type, since the breadcrumb is

			




	
	
	
		
 
                    // already pushed we don't take any action here.

			




	
	
	
		
 
                },

			




	
	
	
		
 
                BreadcrumbResult::TypeLoop(first_idx) => {

			




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

			




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

			




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

			




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

			




	
	
	
		
 
                        let mut is_union = false;

			




	
	
	
		
 

			




	
	
	
		
 
                        match self.lookup.get_mut(&breadcrumb.definition_id).unwrap() {

			




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

			




	
	
	
		
 
                                variant.lives_on_heap = true;

			




	
	
	
		
 
                                breadcrumb.next_embedded += 1;

			




	
	
	
		
 
                                is_union = true;

			




	
	
	
		
 
                            },

			




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

			




	
	
	
		
 
                        }

			




	
	
	
		
 

			




	
	
	
		
 
            let variant_size = variant_offset;

			




	
	
	
		
 
                        loop_members.push(TypeLoopEntry{

			




	
	
	
		
 
                            definition_id: breadcrumb.definition_id,

			




	
	
	
		
 
                            monomorph_idx: breadcrumb.monomorph_idx,

			




	
	
	
		
 
                            is_union

			




	
	
	
		
 
                        });

			




	
	
	
		
 
                    }

			




	
	
	
		
 

			




	
	
	
		
 
            if variant.lives_on_heap {

			




	
	
	
		
 
                heap_size = heap_size.max(variant_size);

			




	
	
	
		
 
                heap_alignment = heap_alignment.max(heap_alignment);

			




	
	
	
		
 
            } else {

			




	
	
	
		
 
                stack_size = stack_size.max(variant_size);

			




	
	
	
		
 
                stack_alignment = stack_alignment.max(variant_alignment);

			




	
	
	
		
 
                has_stack_variant = true;

			




	
	
	
		
 
                    self.type_loops.push(TypeLoop{ members: loop_members });

			




	
	
	
		
 
                }

			




	
	
	
		
 
            }

			




	
	
	
		
 
        }

			




	
	
	
		
 

			




	
	
	
		
 
        // Store the computed sizes

			




	
	
	
		
 
        type_mono.stack_size = stack_size;

			




	
	
	
		
 
        type_mono.stack_alignment = stack_alignment;

			




	
	
	
		
 
        type_mono.heap_size = heap_size;

			




	
	
	
		
 
        type_mono.heap_alignment = heap_alignment;

			




	
	
	
		
 

			




	
	
	
		
 
        if type_mono.heap_size != 0 && !has_stack_variant {

			




	
	
	
		
 
            // Union was part of a type loop, because we have variants that live

			




	
	
	
		
 
            // on the heap. But we do not have any stack variants.

			




	
	
	
		
 
            // TODO: Think about this again, we only need one union to be

			




	
	
	
		
 
            //       non-infinite per type loop. But we may encounter multiple

			




	
	
	
		
 
            //       type loops per layed out type. So keep a vec of sets for

			




	
	
	
		
 
            //       each loop? Then at least one in each set should have a

			




	
	
	
		
 
            //       stack variant?

			




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

			




	
	
	
		
 
            return Err(ParseError::new_error_str_at_span(

			




	
	
	
		
 
                source, ctx.heap[definition.ast_definition].identifier().span,

			




	
	
	
		
 
                "This union is part of an infinite type, so should contain a variant that do not cause type loops"

			




	
	
	
		
 
            ));

			




	
	
	
		
 
        }

			




	
	
	
		
 

			




	
	
	
		
 
        return Ok(LayoutResult::PopBreadcrumb);

			




	
	
	
		
 
    }

			




	
	
	
		
 
        // All breadcrumbs have been cleared. So now `type_loops` contains all

			




	
	
	
		
 
        // of the encountered type loops, and `encountered_types` contains a

			




	
	
	
		
 
        // list of all unique monomorphs we encountered.

			




	
	
	
		
 

			




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

			




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

			




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

			




	
	
	
		
 
        // a type loop.

			




	
	
	
		
 
        fn type_loop_source_span_and_message<'a>(

			




	
	
	
		
 
            modules: &'a [Module], ctx: &PassCtx, defined_type: &DefinedType, monomorph_idx: usize, 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.

			




	
	
	
		
 
            use DefinedTypeVariant as DTV;

			




	
	
	
		
 

			




	
	
	
		
 
            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::Enum(_) | DTV::Function(_) | DTV::Component(_) =>

			




	
	
	
		
 
                    unreachable!(), // impossible to have an enum/procedure in a type loop

			




	
	
	
		
 
            };

			




	
	
	
		
 

			




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

			




	
	
	
		
 
        // Resolve each of the struct fields

			




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

			




	
	
	
		
 
        let definition = self.lookup.get_mut(&breadcrumb.definition_id).unwrap();

			




	
	
	
		
 
        debug_assert!(definition.poly_vars.len() == poly_args.len() || !definition.is_polymorph);

			




	
	
	
		
 
        let type_poly = definition.definition.as_struct_mut();

			




	
	
	
		
 
        let type_mono = &mut type_poly.monomorphs[breadcrumb.monomorph_idx];

			




	
	
	
		
 

			




	
	
	
		
 
        let num_members = type_poly.fields.len();

			




	
	
	
		
 
        while breadcrumb.next_member < num_members {

			




	
	
	
		
 
            let poly_member = &type_poly.fields[breadcrumb.next_member];

			




	
	
	
		
 
            let mono_member = &mut type_mono.fields[breadcrumb.next_member];

			




	
	
	
		
 

			




	
	
	
		
 
            let (concrete_type, size, alignment) = unwrap_lookup_result!(

			




	
	
	
		
 
                self.lookup_layout_for_member_type(&poly_member.parser_type, &type_mono.poly_args)

			




	
	
	
		
 
            );

			




	
	
	
		
 
            let type_name = monomorph_type.display_name(&ctx.heap);

			




	
	
	
		
 
            let message = if index_in_loop == 0 {

			




	
	
	
		
 
                format!(

			




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

			




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

			




	
	
	
		
 
                    not part of a type loop",

			




	
	
	
		
 
                    type_name

			




	
	
	
		
 
                )

			




	
	
	
		
 
            } else if index_in_loop == 1 {

			




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

			




	
	
	
		
 
            } else {

			




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

			




	
	
	
		
 
            };

			




	
	
	
		
 

			




	
	
	
		
 
            mono_member.concrete_type = concrete_type;

			




	
	
	
		
 
            mono_member.size = size;

			




	
	
	
		
 
            mono_member.alignment = alignment;

			




	
	
	
		
 
            let ast_definition = &ctx.heap[defined_type.ast_definition];

			




	
	
	
		
 
            let ast_root_id = ast_definition.defined_in();

			




	
	
	
		
 

			




	
	
	
		
 
            breadcrumb.next_member += 1;

			




	
	
	
		
 
            return (

			




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

			




	
	
	
		
 
                ast_definition.identifier().span,

			




	
	
	
		
 
                message

			




	
	
	
		
 
            );

			




	
	
	
		
 
        }

			




	
	
	
		
 

			




	
	
	
		
 
        // All fields are resolved

			




	
	
	
		
 
        let mut offset = 0;

			




	
	
	
		
 
        let mut alignment = 1;

			




	
	
	
		
 
        for type_loop in &self.type_loops {

			




	
	
	
		
 
            let mut can_be_broken = false;

			




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

			




	
	
	
		
 

			




	
	
	
		
 
        for field in &mut type_mono.fields {

			




	
	
	
		
 
            align_offset_to(&mut offset, field.alignment);

			




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

			




	
	
	
		
 

			




	
	
	
		
 
            field.offset = offset;

			




	
	
	
		
 
                    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;

			




	
	
	
		
 
                    }

			




	
	
	
		
 
                }

			




	
	
	
		
 
            }

			




	
	
	
		
 

			




	
	
	
		
 
            offset += field.size;

			




	
	
	
		
 
            alignment = alignment.max(field.alignment);

			




	
	
	
		
 
            if !can_be_broken {

			




	
	
	
		
 
                // Construct a type loop error

			




	
	
	
		
 
                let first_entry = &type_loop.members[0];

			




	
	
	
		
 
                let first_type = self.lookup.get(&first_entry.definition_id).unwrap();

			




	
	
	
		
 
                let (first_module, first_span, first_message) = type_loop_source_span_and_message(

			




	
	
	
		
 
                    modules, ctx, first_type, first_entry.monomorph_idx, 0

			




	
	
	
		
 
                );

			




	
	
	
		
 
                let mut parse_error = ParseError::new_error_at_span(first_module, first_span, first_message);

			




	
	
	
		
 

			




	
	
	
		
 
                for member_idx in 1..type_loop.members.len() {

			




	
	
	
		
 
                    let entry = &type_loop.members[member_idx];

			




	
	
	
		
 
                    let entry_type = self.lookup.get(&first_entry.definition_id).unwrap();

			




	
	
	
		
 
                    let (module, span, message) = type_loop_source_span_and_message(

			




	
	
	
		
 
                        modules, ctx, entry_type, entry.monomorph_idx, member_idx

			




	
	
	
		
 
                    );

			




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

			




	
	
	
		
 
                }

			




	
	
	
		
 

			




	
	
	
		
 
                return Err(parse_error);

			




	
	
	
		
 
            }

			




	
	
	
		
 
        }

			




	
	
	
		
 

			




	
	
	
		
 
        type_mono.size = offset;

			




	
	
	
		
 
        type_mono.alignment = alignment;

			




	
	
	
		
 
        // If here, then all type loops have been resolved and we can lay out

			




	
	
	
		
 
        // all of the members

			




	
	
	
		
 
        // TODO: Continue here

			




	
	
	
		
 

			




	
	
	
		
 
        return Ok(LayoutResult::PopBreadcrumb);

			




	
	
	
		
 
        return Ok(());

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




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

			




	
	
	
		
 
        unreachable!("ended up laying out function, breadcrumbs are: {:?}", self.breadcrumbs);

			




	
	
	
		
 
    }

			




	
	
	
		
 
    // TODO: Pass in definition_type by value?

			




	
	
	
		
 
    fn push_breadcrumb_for(&mut self, definition_id: DefinitionId, definition_type: &ConcreteType) -> BreadcrumbResult {

			




	
	
	
		
 
        use DefinedTypeVariant as DTV;

			




	
	
	
		
 

			




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

			




	
	
	
		
 
        unreachable!("ended up layout out component, breadcrumbs are: {:?}", self.breadcrumbs);

			




	
	
	
		
 
    }

			




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

			




	
	
	
		
 
        if let Some(mono_idx) = base_type.get_monomorph_index(&definition_type) {

			




	
	
	
		
 
            // Monomorph is already known. Check if it is present in the

			




	
	
	
		
 
            // breadcrumbs. If so, then we are in a type loop

			




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

			




	
	
	
		
 
                if breadcrumb.definition_id == definition_id && breadcrumb.monomorph_idx == mono_idx {

			




	
	
	
		
 
                    return BreadcrumbResult::TypeLoop(breadcrumb_idx);

			




	
	
	
		
 
                }

			




	
	
	
		
 
            }

			




	
	
	
		
 

			




	
	
	
		
 
    /// Returns tag concrete type (always a builtin integer type), the size of

			




	
	
	
		
 
    /// that type in bytes (and implicitly, its alignment)

			




	
	
	
		
 
    pub(crate) fn variant_tag_type_from_values(min_val: i64, max_val: i64) -> (ConcreteType, usize) {

			




	
	
	
		
 
        debug_assert!(min_val <= max_val);

			




	
	
	
		
 
            return BreadcrumbResult::TypeExists;

			




	
	
	
		
 
        }

			




	
	
	
		
 

			




	
	
	
		
 
        let (part, size) = if min_val >= 0 {

			




	
	
	
		
 
            // Can be an unsigned integer

			




	
	
	
		
 
            if max_val <= (u8::MAX as i64) {

			




	
	
	
		
 
                (ConcreteTypePart::UInt8, 1)

			




	
	
	
		
 
            } else if max_val <= (u16::MAX as i64) {

			




	
	
	
		
 
                (ConcreteTypePart::UInt16, 2)

			




	
	
	
		
 
            } else if max_val <= (u32::MAX as i64) {

			




	
	
	
		
 
                (ConcreteTypePart::UInt32, 4)

			




	
	
	
		
 
            } else {

			




	
	
	
		
 
                (ConcreteTypePart::UInt64, 8)

			




	
	
	
		
 
            }

			




	
	
	
		
 
        } else {

			




	
	
	
		
 
            // Must be a signed integer

			




	
	
	
		
 
            if min_val >= (i8::MIN as i64) && max_val <= (i8::MAX as i64) {

			




	
	
	
		
 
                (ConcreteTypePart::SInt8, 1)

			




	
	
	
		
 
            } else if min_val >= (i16::MIN as i64) && max_Val <= (i16::MAX as i64) {

			




	
	
	
		
 
                (ConcreteTypePart::SInt16, 2)

			




	
	
	
		
 
            } else if min_val >= (i32::MIN as i64) && max_val <= (i32::MAX as i64) {

			




	
	
	
		
 
                (ConcreteTypePart::SInt32, 4)

			




	
	
	
		
 
            } else {

			




	
	
	
		
 
                (ConcreteTypePart::SInt64, 8)

			




	
	
	
		
 
            }

			




	
	
	
		
 
        // Type is not yet known, so we need to insert it into the lookup and

			




	
	
	
		
 
        // push a new breadcrumb.

			




	
	
	
		
 
        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.clone(),

			




	
	
	
		
 
                });

			




	
	
	
		
 
                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.clone(),

			




	
	
	
		
 
                    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,

			




	
	
	
		
 
                        size: 0,

			




	
	
	
		
 
                        alignment: 0,

			




	
	
	
		
 
                        offset: 0

			




	
	
	
		
 
                    })

			




	
	
	
		
 
                }

			




	
	
	
		
 

			




	
	
	
		
 
                let mono_idx = definition.monomorphs.len();

			




	
	
	
		
 
                definition.monomorphs.push(StructMonomorph{

			




	
	
	
		
 
                    concrete_type: definition_type.clone(),

			




	
	
	
		
 
                    fields: mono_fields,

			




	
	
	
		
 
                    size: 0,

			




	
	
	
		
 
                    alignment: 0

			




	
	
	
		
 
                });

			




	
	
	
		
 

			




	
	
	
		
 
                mono_idx

			




	
	
	
		
 
            },

			




	
	
	
		
 
            DTV::Function(_) | DTV::Component(_) => {

			




	
	
	
		
 
                unreachable!("pushing type resolving breadcrumb for procedure type {:?}", base_type)

			




	
	
	
		
 
            },

			




	
	
	
		
 
        };

			




	
	
	
		
 

			




	
	
	
		
 
        return (ConcreteType{ parts: vec![part] }, size);

			




	
	
	
		
 
        self.breadcrumbs.push(TypeLoopBreadcrumb{

			




	
	
	
		
 
            definition_id,

			




	
	
	
		
 
            monomorph_idx,

			




	
	
	
		
 
            next_member: 0,

			




	
	
	
		
 
            next_embedded: 0

			




	
	
	
		
 
        });

			




	
	
	
		
 

			




	
	
	
		
 
        // With the breadcrumb constructed we know this is a new type, so we

			




	
	
	
		
 
        // also need to add an entry in the list of all encountered types

			




	
	
	
		
 
        self.encountered_types.push(TypeLoopEntry{

			




	
	
	
		
 
            definition_id,

			




	
	
	
		
 
            monomorph_idx,

			




	
	
	
		
 
            is_union,

			




	
	
	
		
 
        });

			




	
	
	
		
 

			




	
	
	
		
 
        return BreadcrumbResult::PushedBreadcrumb;

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




	
	
	
		
 
    pub(crate) fn lookup_layout_for_member_type(

			




	
	
	
		
 
        &self, parser_type: &ParserType, poly_args: &Vec<ConcreteType>, arch: &TargetArch

			




	
	
	
		
 
    ) -> LookupResult {

			




	
	
	
		
 
    /// Constructs a concrete type out of a parser type for a struct field or

			




	
	
	
		
 
    /// union embedded type. It will do this by looking up the polymorphic

			




	
	
	
		
 
    /// variables in the supplied concrete type. The assumption is that the

			




	
	
	
		
 
    /// polymorphic variable's indices correspond to the subtrees in the

			




	
	
	
		
 
    /// concrete type.

			




	
	
	
		
 
    fn construct_concrete_type(member_type: &ParserType, container_type: &ConcreteType) -> ConcreteType {

			




	
	
	
		
 
        use ParserTypeVariant as PTV;

			




	
	
	
		
 
        use ConcreteTypePart as CTP;

			




	
	
	
		
 

			




	
	
	
		
 
        // Helper for direct translation of parser type to concrete type

			




	
	
	
		
 
        // TODO: Combine with code in pass_typing.rs

			




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

			




	
	
	
		
 
            match part {

			




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

			




	
	
		
 
@@ -1305,130 +1483,72 @@ impl TypeTable {

			




	
	
	
		
 
            }

			




	
	
	
		
 
        }

			




	
	
	
		
 

			




	
	
	
		
 
        // Construct the concrete type from the parser type and its polymorphic

			




	
	
	
		
 
        // arguments. Make a rough estimation of the total number of parts:

			




	
	
	
		
 
        // TODO: @Optimize

			




	
	
	
		
 
        debug_assert!(!parser_type.elements.is_empty());

			




	
	
	
		
 
        let mut concrete_parts = Vec::with_capacity(parser_type.elements.len());

			




	
	
	
		
 

			




	
	
	
		
 
        for parser_part in &parser_type.elements {

			




	
	
	
		
 
            if let Some(concrete_part) = parser_to_concrete_part(&parser_part.variant) {

			




	
	
	
		
 
                concrete_parts.push(concrete_part);

			




	
	
	
		
 
            } else if let PTV::PolymorphicArgument(_part_of_id, poly_idx) = parser_part.variant {

			




	
	
	
		
 
                concrete_parts.extend_from_slice(&poly_args[poly_idx as usize].parts);

			




	
	
	
		
 
            } else {

			




	
	
	
		
 
                unreachable!("unexpected parser part {:?} in {:?}", parser_part, parser_type);

			




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

			




	
	
	
		
 
        for member_part in &member_type.elements {

			




	
	
	
		
 
            // Check if we have a regular builtin type

			




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

			




	
	
	
		
 
                parts.push(part);

			




	
	
	
		
 
                continue;

			




	
	
	
		
 
            }

			




	
	
	
		
 
        }

			




	
	
	
		
 

			




	
	
	
		
 
        // Check if the type is an instance of a user-defined type, and if so,

			




	
	
	
		
 
        // whether the particular monomorph is already instantiated.

			




	
	
	
		
 
        let concrete_type = ConcreteType{ parts: concrete_parts };

			




	
	
	
		
 
        if let CTP::Instance(definition_id, num_poly_args) = concrete_type.parts[0] {

			




	
	
	
		
 
            // Retrieve polymorphic arguments from the full type tree

			




	
	
	
		
 
            // TODO: Rather wasteful, this screams for a different implementation

			




	
	
	
		
 
            //       @Optimize

			




	
	
	
		
 
            let mut poly_args = Vec::new();

			




	
	
	
		
 
            if num_poly_args != 0 {

			




	
	
	
		
 
                poly_args.reserve(num_poly_args as usize);

			




	
	
	
		
 

			




	
	
	
		
 
                let mut subtree_idx = 1;

			




	
	
	
		
 
                for _ in 0..num_poly_args {

			




	
	
	
		
 
                    let mut subtree_end = concrete_type.subtree_end_idx(subtree_idx);

			




	
	
	
		
 
                    poly_args.push(ConcreteType{

			




	
	
	
		
 
                        parts: Vec::from(&concrete_type.parts[subtree_idx..subtree_end])

			




	
	
	
		
 
                    });

			




	
	
	
		
 
                }

			




	
	
	
		
 

			




	
	
	
		
 
                debug_assert_eq!(subtree_idx, concrete_p)

			




	
	
	
		
 
            }

			




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

			




	
	
	
		
 
            // about the polymorphic argument at this point.

			




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

			




	
	
	
		
 
                debug_assert_eq!(*_container_definition_id, get_concrete_type_definition(container_type));

			




	
	
	
		
 

			




	
	
	
		
 
            // Always check the breadcrumbs first, because this allows us to

			




	
	
	
		
 
            // detect type loops

			




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

			




	
	
	
		
 
                if breadcrumb.definition_id != definition_id {

			




	
	
	
		
 
                    continue;

			




	
	
	
		
 
                let mut container_iter = container_type.embedded_iter(0);

			




	
	
	
		
 
                for _ in 0..*poly_arg_idx {

			




	
	
	
		
 
                    container_iter.next();

			




	
	
	
		
 
                }

			




	
	
	
		
 

			




	
	
	
		
 
                let other_def = self.lookup.get(&breadcrumb.definition_id).unwrap();

			




	
	
	
		
 
                if other_def.monomorph_matches_poly_args(breadcrumb.monomorph_idx, &poly_args) {

			




	
	
	
		
 
                    // We're in a type loop

			




	
	
	
		
 
                    return LookupResult::TypeLoop(breadcrumb_idx);

			




	
	
	
		
 
                }

			




	
	
	
		
 
            }

			




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

			




	
	
	
		
 
                parts.extend(poly_section);

			




	
	
	
		
 

			




	
	
	
		
 
            // None of the breadcrumbs matched, so we're not in a type loop, but

			




	
	
	
		
 
            // we might have still encountered this particular monomorph before

			




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

			




	
	
	
		
 
            if let Some(monomorph_idx) = definition.has_monomorph(&poly_args) {

			




	
	
	
		
 
                let (size, alignment) = definition.get_monomorph_size_alignment(monomorph_idx);

			




	
	
	
		
 
                return LookupResult::Exists(concrete_type, size, alignment);

			




	
	
	
		
 
                continue;

			




	
	
	
		
 
            }

			




	
	
	
		
 

			




	
	
	
		
 
            // If here, then the type has not been instantiated before

			




	
	
	
		
 
            return LookupResult::Missing(definition_id, poly_args);

			




	
	
	
		
 
        } else {

			




	
	
	
		
 
            // Must be some kind of builtin type. Probably the hot path, so just

			




	
	
	
		
 
            // return the type

			




	
	
	
		
 
            let (size, alignment) = match concrete_type.parts[0] {

			




	
	
	
		
 
                CTP::Void => (0, 1), // alignment is 1 to simplify alignment calculations

			




	
	
	
		
 
                CTP::Message => arch.pointer_size_alignment,

			




	
	
	
		
 
                CTP::Bool => (1, 1),

			




	
	
	
		
 
                CTP::UInt8 | CTP::SInt8 => (1, 1),

			




	
	
	
		
 
                CTP::UInt16 | CTP::SInt16 => (2, 2),

			




	
	
	
		
 
                CTP::UInt32 | CTP::SInt32 => (4, 4),

			




	
	
	
		
 
                CTP::UInt64 | CTP::SInt64 => (8, 8),

			




	
	
	
		
 
                CTP::Array => arch.array_size_alignment,

			




	
	
	
		
 
                CTP::Slice => arch.slice_size_alignment,

			




	
	
	
		
 
                CTP::Input | CTP::Output => arch.port_size_alignment,

			




	
	
	
		
 
                _ => unreachable!("unexpected builtin type in {:?}", concrete_type),

			




	
	
	
		
 
            };

			




	
	
	
		
 

			




	
	
	
		
 
            return LookupResult::Exists(concrete_type, size, alignment);

			




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

			




	
	
	
		
 
        }

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




	
	
	
		
 
    fn handle_breadcrumb_type_loop(&mut self, breadcrumb_idx: usize) -> Result<(), ParseError> {

			




	
	
	
		
 
        // Starting at the breadcrumb index, walk all the way to the back and

			




	
	
	
		
 
        // mark each

			




	
	
	
		
 
        return ConcreteType{ parts };

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




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

			




	
	
	
		
 
    // Breadcrumb management

			




	
	
	
		
 
    // Determining memory layout for types

			




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

			




	
	
	
		
 

			




	
	
	
		
 
    /// Pushes a breadcrumb for a particular definition. The field in the

			




	
	
	
		
 
    /// breadcrumb tracking progress in defining the type will be preallocated

			




	
	
	
		
 
    /// as best as possible.

			




	
	
	
		
 
    fn push_breadcrumb_for_definition(&mut self, ctx: &PassCtx, definition_id: DefinitionId, poly_args: Vec<ConcreteType>) {

			




	
	
	
		
 
        let definition = &ctx.heap[definition_id];

			




	
	
	
		
 
        debug_assert!(!self.lookup.get(&definition_id).unwrap().has_monomorph(&poly_args));

			




	
	
	
		
 

			




	
	
	
		
 
        let monomorph_idx = match definition {

			




	
	
	
		
 
            Definition::Struct(definition) => {

			




	
	
	
		
 

			




	
	
	
		
 
            },

			




	
	
	
		
 
            Definition::Enum(definition) => {

			




	
	
	
		
 

			




	
	
	
		
 
            },

			




	
	
	
		
 
            Definition::Union(definition) => {

			




	
	
	
		
 

			




	
	
	
		
 
            },

			




	
	
	
		
 
            Definition::Component(definition) => {

			




	
	
	
		
 

			




	
	
	
		
 
            },

			




	
	
	
		
 
            Definition::Function(definition) => {

			




	
	
	
		
 
    /// Returns tag concrete type (always a builtin integer type), the size of

			




	
	
	
		
 
    /// that type in bytes (and implicitly, its alignment)

			




	
	
	
		
 
    fn variant_tag_type_from_values(min_val: i64, max_val: i64) -> (ConcreteType, usize) {

			




	
	
	
		
 
        debug_assert!(min_val <= max_val);

			




	
	
	
		
 

			




	
	
	
		
 
        let (part, size) = if min_val >= 0 {

			




	
	
	
		
 
            // Can be an unsigned integer

			




	
	
	
		
 
            if max_val <= (u8::MAX as i64) {

			




	
	
	
		
 
                (ConcreteTypePart::UInt8, 1)

			




	
	
	
		
 
            } else if max_val <= (u16::MAX as i64) {

			




	
	
	
		
 
                (ConcreteTypePart::UInt16, 2)

			




	
	
	
		
 
            } else if max_val <= (u32::MAX as i64) {

			




	
	
	
		
 
                (ConcreteTypePart::UInt32, 4)

			




	
	
	
		
 
            } else {

			




	
	
	
		
 
                (ConcreteTypePart::UInt64, 8)

			




	
	
	
		
 
            }

			




	
	
	
		
 
        } else {

			




	
	
	
		
 
            // Must be a signed integer

			




	
	
	
		
 
            if min_val >= (i8::MIN as i64) && max_val <= (i8::MAX as i64) {

			




	
	
	
		
 
                (ConcreteTypePart::SInt8, 1)

			




	
	
	
		
 
            } else if min_val >= (i16::MIN as i64) && max_Val <= (i16::MAX as i64) {

			




	
	
	
		
 
                (ConcreteTypePart::SInt16, 2)

			




	
	
	
		
 
            } else if min_val >= (i32::MIN as i64) && max_val <= (i32::MAX as i64) {

			




	
	
	
		
 
                (ConcreteTypePart::SInt32, 4)

			




	
	
	
		
 
            } else {

			




	
	
	
		
 
                (ConcreteTypePart::SInt64, 8)

			




	
	
	
		
 
            }

			




	
	
	
		
 
        };

			




	
	
	
		
 

			




	
	
	
		
 
        self.breadcrumbs.push(LayoutBreadcrumb{

			




	
	
	
		
 
            root_id,

			




	
	
	
		
 
            definition_id,

			




	
	
	
		
 
            monomorph_idx: 0,

			




	
	
	
		
 
            next_member: 0,

			




	
	
	
		
 
            next_embedded: 0

			




	
	
	
		
 
        });

			




	
	
	
		
 
        return (ConcreteType{ parts: vec![part] }, size);

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




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

			




	
	
		
 
@@ -1458,4 +1578,13 @@ impl TypeTable {

			




	
	
	
		
 
    let alignment_min_1 = alignment - 1;

			




	
	
	
		
 
    *offset += alignment_min_1;

			




	
	
	
		
 
    *offset &= !(alignment_min_1);

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
#[inline] fn get_concrete_type_definition(concrete: &ConcreteType) -> DefinitionId {

			




	
	
	
		
 
    if let ConcreteTypePart::Instance(definition_id, _) = concrete.parts[0] {

			




	
	
	
		
 
        return definition_id;

			




	
	
	
		
 
    } else {

			




	
	
	
		
 
        debug_assert!(false, "passed {:?} to the type table", concrete);

			




	
	
	
		
 
        return DefinitionId::new_invalid()

			




	
	
	
		
 
    }

			




	
	
	
		
 
}

			




	
	
		
 
\ No newline at end of file

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








    
        Server instance: kalli-3023199
    
    
        This site is powered by
            Kallithea,
        which is
        © 2010–2022 by various authors & licensed under GPLv3.
            – Support