Changeset - 87c3d649056d
[Not reviewed]
0 1 0
MH - 4 years ago 2021-07-14 09:14:23
contact@maxhenger.nl
more progress on memory layout
1 file changed with 234 insertions and 539 deletions:
0 comments (0 inline, 0 general)
src/protocol/parser/type_table.rs
Show inline comments
 
@@ -14,15 +14,20 @@
 
 * The basic algorithm for type resolving and computing byte sizes is to
 
 * recursively try to lay out each member type of a particular type. This is
 
 * done in a stack-like fashion, where each embedded type pushes a breadcrumb
 
 * unto the stack. We may discover a cycle in embedded types (called a "type
 
 * loop"). After which the type table attempts to break the type loop by making
 
 * specific types heap-allocated. Upon doing so we know their size because their
 
 * stack-size is now based on pointers.
 
 * unto the stack. We may discover a cycle in embedded types (we call this a
 
 * "type loop"). After which the type table attempts to break the type loop by
 
 * making specific types heap-allocated. Upon doing so we know their size
 
 * because their stack-size is now based on pointers. Hence breaking the type
 
 * loop required for computing the byte size of types.
 
 *
 
 * The reason for these type shenanigans is because PDL is a value-based
 
 * language, but we would still like to be able to express recursively defined
 
 * types like trees or linked lists. Hence we need to insert pointers somewhere
 
 * to break these cycles.
 
 *
 
 * As a final bit of global documentation: non-polymorphic types will always
 
 * have one "monomorph" entry. This contains the non-polymorphic type's memory
 
 * layout.
 
 */
 

	
 
use std::fmt::{Formatter, Result as FmtResult};
 
@@ -105,6 +110,13 @@ impl DefinedTypeVariant {
 
        }
 
    }
 

	
 
    pub(crate) fn as_struct_mut(&mut self) -> &mut StructType {
 
        match self {
 
            DefinedTypeVariant::Struct(v) => v,
 
            _ => unreachable!("Cannot convert {} to struct variant", self.type_class())
 
        }
 
    }
 

	
 
    pub(crate) fn as_enum(&self) -> &EnumType {
 
        match self {
 
            DefinedTypeVariant::Enum(v) => v,
 
@@ -112,39 +124,24 @@ impl DefinedTypeVariant {
 
        }
 
    }
 

	
 
    pub(crate) fn as_union(&self) -> &UnionType {
 
    pub(crate) fn as_enum_mut(&mut self) -> &mut EnumType {
 
        match self {
 
            DefinedTypeVariant::Union(v) => v,
 
            _ => unreachable!("Cannot convert {} to union variant", self.type_class())
 
            DefinedTypeVariant::Enum(v) => v,
 
            _ => unreachable!("Cannot convert {} to enum variant", self.type_class())
 
        }
 
    }
 

	
 
    pub(crate) fn as_union_mut(&mut self) -> &mut UnionType {
 
    pub(crate) fn as_union(&self) -> &UnionType {
 
        match self {
 
            DefinedTypeVariant::Union(v) => v,
 
            _ => unreachable!("Cannot convert {} to union variant", self.type_class())
 
        }
 
    }
 

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

	
 
        match self {
 
            Enum(v) => &v.monomorphs,
 
            Union(v) => &v.monomorphs,
 
            Struct(v) => &v.monomorphs,
 
            _ => unreachable!("cannot get data monomorphs from {}", self.type_class()),
 
        }
 
    }
 

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

	
 
    pub(crate) fn as_union_mut(&mut self) -> &mut UnionType {
 
        match self {
 
            Enum(v) => &mut v.monomorphs,
 
            Union(v) => &mut v.monomorphs,
 
            Struct(v) => &mut v.monomorphs,
 
            _ => unreachable!("cannot get data monomorphs from {}", self.type_class()),
 
            DefinedTypeVariant::Union(v) => v,
 
            _ => unreachable!("Cannot convert {} to union variant", self.type_class())
 
        }
 
    }
 

	
 
@@ -195,7 +192,12 @@ pub struct ProcedureMonomorph {
 
/// variants to be equal to one another.
 
pub struct EnumType {
 
    pub variants: Vec<EnumVariant>,
 
    pub monomorphs: Vec<DataMonomorph>,
 
    pub monomorphs: Vec<EnumMonomorph>,
 
    pub minimum_tag_value: i64,
 
    pub maximum_tag_value: i64,
 
    pub tag_type: ConcreteType,
 
    pub size: usize,
 
    pub alignment: usize,
 
}
 

	
 
// TODO: Also support maximum u64 value
 
@@ -204,6 +206,10 @@ pub struct EnumVariant {
 
    pub value: i64,
 
}
 

	
 
pub struct EnumMonomorph {
 
    pub poly_args: Vec<ConcreteType>
 
}
 

	
 
/// `UnionType` is the algebraic datatype (or sum type, or discriminated union).
 
/// A value is an element of the union, identified by its tag, and may contain
 
/// a single subtype.
 
@@ -216,7 +222,7 @@ 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<DataMonomorph>,
 
    pub monomorphs: Vec<UnionMonomorph>,
 
    pub requires_allocation: bool,
 
    pub contains_unallocated_variant: bool,
 
}
 
@@ -225,9 +231,33 @@ pub struct UnionVariant {
 
    pub identifier: Identifier,
 
    pub embedded: Vec<ParserType>, // zero-length does not have embedded values
 
    pub tag_value: i64,
 
    pub exists_in_heap: bool,
 
}
 

	
 
pub struct UnionMonomorph {
 
    pub poly_args: Vec<ConcreteType>,
 
    pub variants: Vec<UnionMonomorphVariant>,
 
    pub alignment: usize,
 
    // stack_byte_size is the size of the union on the stack, includes the tag
 
    pub stack_byte_size: usize,
 
    // heap_byte_size contains the allocated size of the union in the case it
 
    // is used to break a type loop. If it is 0, then it doesn't require
 
    // allocation and lives entirely on the stack.
 
    pub heap_byte_size: usize,
 
}
 

	
 
pub struct UnionMonomorphVariant {
 
    pub lives_on_heap: bool,
 
    pub embedded: Vec<UnionMonomorphEmbedded>,
 
}
 

	
 
pub struct UnionMonomorphEmbedded {
 
    pub concrete_type: ConcreteType,
 
    pub size: usize,
 
    pub offset: usize,
 
}
 

	
 
/// `StructType` is a generic C-like struct type (or record type, or product
 
/// type) type.
 
pub struct StructType {
 
    pub fields: Vec<StructField>,
 
    pub monomorphs: Vec<DataMonomorph>,
 
@@ -238,6 +268,19 @@ pub struct StructField {
 
    pub parser_type: ParserType,
 
}
 

	
 
pub struct StructMonomorph {
 
    pub poly_args: Vec<ConcreteType>,
 
    pub fields: Vec<StructMonomorphField>,
 
}
 

	
 
pub struct StructMonomorphField {
 
    pub concrete_type: ConcreteType,
 
    pub size: usize,
 
    pub offset: usize,
 
}
 

	
 
/// `FunctionType` is what you expect it to be: a particular function's
 
/// signature.
 
pub struct FunctionType {
 
    pub return_types: Vec<ParserType>,
 
    pub arguments: Vec<FunctionArgument>,
 
@@ -272,32 +315,24 @@ pub struct MonomorphExpression {
 
// Type table
 
//------------------------------------------------------------------------------
 

	
 
struct ResolveBreadcrumb {
 
struct LayoutBreadcrumb {
 
    root_id: RootId,
 
    definition_id: DefinitionId,
 
    next_member: u32,
 
    next_embedded: u32, // for unions, the next embedded value inside the member
 
    progression: DefinedTypeVariant
 
}
 

	
 
/// Result from attempting to resolve a `ParserType` using the symbol table and
 
/// the type table.
 
enum ResolveResult {
 
    Builtin,
 
    PolymoprhicArgument,
 
    /// ParserType points to a user-defined type that is already resolved in the
 
    /// type table.
 
    Resolved(RootId, DefinitionId),
 
    /// ParserType points to a user-defined type that is not yet resolved into
 
    /// the type table.
 
    Unresolved(RootId, DefinitionId)
 
    monomorph_idx: usize,
 
    next_member: usize,
 
    next_embedded: usize, // for unions, the next embedded value inside the member
 
}
 

	
 
/// Result from attempting to progress a breadcrumb
 
enum ProgressResult {
 
enum LayoutResult {
 
    PopBreadcrumb,
 
    PushBreadcrumb(RootId, DefinitionId),
 
    TypeLoop(RootId, DefinitionId),
 
    PushBreadcrumb(RootId, DefinitionId, Vec<ConcreteType>),
 
    TypeLoop(RootId, DefinitionId, Vec<ConcreteType>),
 
}
 

	
 
enum LookupResult {
 
    Exists(ConcreteType), // type was looked up and exists (or is a builtin)
 
    Missing(DefinitionId, Vec<ConcreteType>), // type was looked up and doesn't exist, vec contains poly args
 
}
 

	
 
pub struct TypeTable {
 
@@ -305,7 +340,7 @@ pub struct TypeTable {
 
    /// polymorphs is done inside the `DefinedType` struct.
 
    lookup: HashMap<DefinitionId, DefinedType>,
 
    /// Breadcrumbs left behind while resolving embedded types
 
    breadcrumbs: Vec<ResolveBreadcrumb>,
 
    breadcrumbs: Vec<LayoutBreadcrumb>,
 
    infinite_unions: Vec<(RootId, DefinitionId)>,
 
}
 

	
 
@@ -359,7 +394,16 @@ impl TypeTable {
 
            module.phase = ModuleCompilationPhase::TypesAddedToTable;
 
        }
 

	
 
        // Go through all types again, now try to m
 
        // 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.
 
        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 {
 

	
 
            }
 
        }
 

	
 
        Ok(())
 
    }
 
@@ -460,40 +504,9 @@ impl TypeTable {
 
        return index as i32;
 
    }
 

	
 
    /// This function will resolve just the basic definition of the type, it
 
    /// will not handle any of the monomorphized instances of the type.
 
    fn resolve_base_definition<'a>(&'a mut self, modules: &[Module], ctx: &mut PassCtx, definition_id: DefinitionId) -> Result<(), ParseError> {
 
        // Check if we have already resolved the base definition
 
        if self.lookup.contains_key(&definition_id) { return Ok(()); }
 

	
 
        // We haven't, push the first breadcrumb and start resolving
 
        self.push_breadcrumb_for_definition(ctx, definition_id);
 

	
 
        while let Some(breadcrumb) = self.breadcrumbs.last() {
 
            // We have a type to resolve
 
            let definition = &ctx.heap[breadcrumb.definition_id];
 

	
 
            let can_pop_breadcrumb = match definition {
 
                // Bit ugly, since we already have the definition, but we need
 
                // to work around rust borrowing rules...
 
                Definition::Enum(_) => self.resolve_base_enum_definition(modules, ctx),
 
                Definition::Union(_) => self.resolve_base_union_definition(modules, ctx),
 
                Definition::Struct(_) => self.resolve_base_struct_definition(modules, ctx),
 
                Definition::Component(_) => self.resolve_base_component_definition(modules, ctx),
 
                Definition::Function(_) => self.resolve_base_function_definition(modules, ctx),
 
            }?;
 

	
 
            // Otherwise: `ingest_resolve_result` has pushed a new breadcrumb
 
            // that we must follow before we can resolve the current type
 
            if can_pop_breadcrumb {
 
                self.breadcrumbs.pop();
 
            }
 
        }
 

	
 
        // We must have resolved the type
 
        debug_assert!(self.lookup.contains_key(&definition_id), "base type not resolved");
 
        Ok(())
 
    }
 
    //--------------------------------------------------------------------------
 
    // Building base types
 
    //--------------------------------------------------------------------------
 

	
 
    /// Builds the base type for an enum. Will not compute byte sizes
 
    fn build_base_enum_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, definition_id: DefinitionId) -> Result<(), ParseError> {
 
@@ -537,7 +550,7 @@ impl TypeTable {
 
            }
 
        }
 

	
 
        // TODO: Tag size determination, here or when laying out?
 
        let (tag_type, size_and_alignment) = Self::variant_tag_type_from_values(min_enum_value, max_enum_value);
 

	
 
        // Enum names and polymorphic args do not conflict
 
        Self::check_identifier_collision(
 
@@ -555,6 +568,11 @@ impl TypeTable {
 
            definition: DefinedTypeVariant::Enum(EnumType{
 
                variants,
 
                monomorphs: Vec::new(),
 
                minimum_tag_value: min_enum_value,
 
                maximum_tag_value: max_enum_value,
 
                tag_type,
 
                size: size_and_alignment,
 
                alignment: size_and_alignment
 
            }),
 
            poly_vars,
 
            is_polymorph: false,
 
@@ -563,6 +581,7 @@ impl TypeTable {
 
        return Ok(());
 
    }
 

	
 
    /// 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");
 
        let definition = ctx.heap[definition_id].as_union();
 
@@ -583,7 +602,6 @@ impl TypeTable {
 
                identifier: variant.identifier.clone(),
 
                embedded: variant.value.clone(),
 
                tag_value: tag_counter,
 
                exists_in_heap: false
 
            });
 
        }
 

	
 
@@ -619,6 +637,7 @@ impl TypeTable {
 
        return Ok(());
 
    }
 

	
 
    /// 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");
 
        let definition = ctx.heap[definition_id].as_struct();
 
@@ -666,6 +685,7 @@ impl TypeTable {
 
        return Ok(())
 
    }
 

	
 
    /// 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");
 
        let definition = ctx.heap[definition_id].as_function();
 
@@ -724,6 +744,7 @@ impl TypeTable {
 
        return Ok(());
 
    }
 

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

	
 
@@ -735,7 +756,7 @@ impl TypeTable {
 
        for parameter_id in &definition.parameters {
 
            let parameter = &ctx.heap[*parameter_id];
 
            Self::check_member_parser_type(
 
                modules, ctx, root_id, &parameter.parser_type
 
                modules, ctx, root_id, &parameter.parser_type, false
 
            )?;
 

	
 
            arguments.push(FunctionArgument{
 
@@ -746,7 +767,7 @@ impl TypeTable {
 

	
 
        // Check conflict of identifiers
 
        Self::check_identifier_collision(
 
            modules, root_id, &arguments, |arg| &arg.identifier
 
            modules, root_id, &arguments, |arg| &arg.identifier, "connector argument"
 
        )?;
 
        Self::check_poly_args_collision(modules, ctx, root_id, &definition.poly_vars)?;
 

	
 
@@ -773,384 +794,6 @@ impl TypeTable {
 
        Ok(())
 
    }
 

	
 

	
 
    /// Resolve the basic enum definition to an entry in the type table. It will
 
    /// not instantiate any monomorphized instances of polymorphic enum
 
    /// definitions. If a subtype has to be resolved first then this function
 
    /// will return `false` after calling `ingest_resolve_result`.
 
    fn resolve_base_enum_definition(&mut self, modules: &[Module], ctx: &mut PassCtx) -> Result<bool, ParseError> {
 
        // Retrieve breadcrumb and perform some basic checking
 
        let breadcrumb = self.breadcrumbs.last_mut().unwrap();
 
        let root_id = breadcrumb.root_id;
 
        let definition_id = breadcrumb.definition_id;
 

	
 
        debug_assert!(ctx.heap[definition_id].is_enum());
 
        debug_assert!(!self.lookup.contains_key(&definition_id), "base enum already resolved");
 
        
 
        let definition = ctx.heap[definition_id].as_enum();
 

	
 
        // Since we're dealing with an enum's base definition, we're not going
 
        // to check any embedded types and should finish layout out the enum in
 
        // one go.
 
        debug_assert!(breadcrumb.progression.is_none());
 

	
 
        // Determine enum variants
 
        let mut enum_value = -1;
 
        let mut min_enum_value = 0;
 
        let mut max_enum_value = 0;
 
        let mut variants = Vec::with_capacity(definition.variants.len());
 
        for variant in &definition.variants {
 
            enum_value += 1;
 
            match &variant.value {
 
                EnumVariantValue::None => {
 
                    variants.push(EnumVariant{
 
                        identifier: variant.identifier.clone(),
 
                        value: enum_value,
 
                    });
 
                },
 
                EnumVariantValue::Integer(override_value) => {
 
                    enum_value = *override_value;
 
                    variants.push(EnumVariant{
 
                        identifier: variant.identifier.clone(),
 
                        value: enum_value,
 
                    });
 
                }
 
            }
 
            if enum_value < min_enum_value { min_enum_value = enum_value; }
 
            else if enum_value > max_enum_value { max_enum_value = enum_value; }
 
        }
 

	
 
        // Ensure enum names and polymorphic args do not conflict
 
        Self::check_identifier_collision(
 
            modules, root_id, &variants, |variant| &variant.identifier, "enum variant"
 
        )?;
 

	
 
        // Because we're parsing an enum, the programmer cannot put the
 
        // polymorphic variables inside the variants. But the polymorphic
 
        // variables might still be present as "marker types"
 
        Self::check_poly_args_collision(modules, ctx, root_id, &definition.poly_vars)?;
 
        let poly_vars = Self::create_polymorphic_variables(&definition.poly_vars);
 

	
 
        self.lookup.insert(definition_id, DefinedType {
 
            ast_root: root_id,
 
            ast_definition: definition_id,
 
            definition: DefinedTypeVariant::Enum(EnumType{
 
                variants,
 
                monomorphs: Vec::new(),
 
            }),
 
            poly_vars,
 
            is_polymorph: false,
 
        });
 

	
 
        Ok(true)
 
    }
 

	
 
    /// Resolves the basic union definiton to an entry in the type table. It
 
    /// will not instantiate any monomorphized instances of polymorphic union
 
    /// definitions. If a subtype has to be resolved first then this function
 
    /// will return `false` after calling `ingest_resolve_result`.
 
    fn resolve_base_union_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, root_id: RootId, definition_id: DefinitionId) -> Result<bool, ParseError> {
 
        debug_assert!(ctx.heap[definition_id].is_union());
 
        debug_assert!(!self.lookup.contains_key(&definition_id), "base union already resolved");
 

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

	
 
        // Make sure all embedded types are resolved
 
        for variant in &definition.variants {
 
            match &variant.value {
 
                UnionVariantValue::None => {},
 
                UnionVariantValue::Embedded(embedded) => {
 
                    for parser_type in embedded {
 
                        let resolve_result = self.resolve_base_parser_type(modules, ctx, root_id, parser_type, false)?;
 
                        if !self.ingest_resolve_result(modules, ctx, resolve_result)? {
 
                            return Ok(false)
 
                        }
 
                    }
 
                }
 
            }
 
        }
 

	
 
        // If here then all embedded types are resolved
 

	
 
        // Determine the union variants
 
        let mut tag_value = -1;
 
        let mut variants = Vec::with_capacity(definition.variants.len());
 
        for variant in &definition.variants {
 
            tag_value += 1;
 
            let embedded = match &variant.value {
 
                UnionVariantValue::None => { Vec::new() },
 
                UnionVariantValue::Embedded(embedded) => {
 
                    // Type should be resolvable, we checked this above
 
                    embedded.clone()
 
                },
 
            };
 

	
 
            variants.push(UnionVariant{
 
                identifier: variant.identifier.clone(),
 
                embedded,
 
                tag_value,
 
                exists_in_heap: false
 
            })
 
        }
 

	
 
        // Ensure union names and polymorphic args do not conflict
 
        Self::check_identifier_collision(
 
            modules, root_id, &variants, |variant| &variant.identifier, "union variant"
 
        )?;
 
        Self::check_poly_args_collision(modules, ctx, root_id, &definition.poly_vars)?;
 

	
 
        // Construct polymorphic variables and mark the ones that are in use
 
        let mut poly_vars = Self::create_polymorphic_variables(&definition.poly_vars);
 
        for variant in &variants {
 
            for parser_type in &variant.embedded {
 
                Self::mark_used_polymorphic_variables(&mut poly_vars, parser_type);
 
            }
 
        }
 
        let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use);
 

	
 
        // Insert base definition in type table
 
        self.lookup.insert(definition_id, DefinedType {
 
            ast_root: root_id,
 
            ast_definition: definition_id,
 
            definition: DefinedTypeVariant::Union(UnionType{
 
                variants,
 
                monomorphs: Vec::new(),
 
                requires_allocation: false,
 
                contains_unallocated_variant: true
 
            }),
 
            poly_vars,
 
            is_polymorph,
 
        });
 

	
 
        Ok(true)
 
    }
 

	
 
    /// Resolves the basic struct definition to an entry in the type table. It
 
    /// will not instantiate any monomorphized instances of polymorphic struct
 
    /// definitions.
 
    fn resolve_base_struct_definition(&mut self, modules: &[Module], ctx: &mut PassCtx) -> Result<bool, ParseError> {
 
        debug_assert!(ctx.heap[definition_id].is_struct());
 
        debug_assert!(!self.lookup.contains_key(&definition_id), "base struct already resolved");
 

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

	
 
        // Make sure all fields point to resolvable types
 
        for field_definition in &definition.fields {
 
            let resolve_result = self.resolve_base_parser_type(modules, ctx, root_id, &field_definition.parser_type, false)?;
 
            if !self.ingest_resolve_result(modules, ctx, resolve_result)? {
 
                return Ok(false)
 
            }
 
        }
 

	
 
        // All fields types are resolved, construct base type
 
        let mut fields = Vec::with_capacity(definition.fields.len());
 
        for field_definition in &definition.fields {
 
            fields.push(StructField{
 
                identifier: field_definition.field.clone(),
 
                parser_type: field_definition.parser_type.clone(),
 
            })
 
        }
 

	
 
        // And make sure no conflicts exist in field names and/or polymorphic args
 
        Self::check_identifier_collision(
 
            modules, root_id, &fields, |field| &field.identifier, "struct field"
 
        )?;
 
        Self::check_poly_args_collision(modules, ctx, root_id, &definition.poly_vars)?;
 

	
 
        // Construct representation of polymorphic arguments
 
        let mut poly_vars = Self::create_polymorphic_variables(&definition.poly_vars);
 
        for field in &fields {
 
            Self::mark_used_polymorphic_variables(&mut poly_vars, &field.parser_type);
 
        }
 

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

	
 
        self.lookup.insert(definition_id, DefinedType{
 
            ast_root: root_id,
 
            ast_definition: definition_id,
 
            definition: DefinedTypeVariant::Struct(StructType{
 
                fields,
 
                monomorphs: Vec::new(),
 
            }),
 
            poly_vars,
 
            is_polymorph,
 
        });
 

	
 
        Ok(true)
 
    }
 

	
 
    /// Resolves the basic function definition to an entry in the type table. It
 
    /// will not instantiate any monomorphized instances of polymorphic function
 
    /// definitions.
 
    fn resolve_base_function_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, root_id: RootId, definition_id: DefinitionId) -> Result<bool, ParseError> {
 
        debug_assert!(ctx.heap[definition_id].is_function());
 
        debug_assert!(!self.lookup.contains_key(&definition_id), "base function already resolved");
 

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

	
 
        // Check the return type
 
        debug_assert_eq!(definition.return_types.len(), 1, "not one return type"); // TODO: @ReturnValues
 
        let resolve_result = self.resolve_base_parser_type(modules, ctx, root_id, &definition.return_types[0], definition.builtin)?;
 
        if !self.ingest_resolve_result(modules, ctx, resolve_result)? {
 
            return Ok(false)
 
        }
 

	
 
        // Check the argument types
 
        let mut arguments = Vec::with_capacity(definition.parameters.len());
 

	
 
        for param_id in &definition.parameters {
 
            let param = &ctx.heap[*param_id];
 
            let resolve_result = self.resolve_base_parser_type(modules, ctx, root_id, &param.parser_type, definition.builtin)?;
 
            if !self.ingest_resolve_result(modules, ctx, resolve_result)? {
 
                return Ok(false)
 
            }
 

	
 
            arguments.push(FunctionArgument{
 
                identifier: param.identifier.clone(),
 
                parser_type: param.parser_type.clone(),
 
            });
 
        }
 

	
 
        // Check conflict of argument and polyarg identifiers
 
        Self::check_identifier_collision(
 
            modules, root_id, &arguments, |arg| &arg.identifier, "function argument"
 
        )?;
 
        Self::check_poly_args_collision(modules, ctx, root_id, &definition.poly_vars)?;
 

	
 
        // Construct polymorphic arguments
 
        let mut poly_vars = Self::create_polymorphic_variables(&definition.poly_vars);
 
        Self::mark_used_polymorphic_variables(&mut poly_vars, &definition.return_types[0]);
 
        for argument in &arguments {
 
            Self::mark_used_polymorphic_variables(&mut poly_vars, &argument.parser_type);
 
        }
 
        let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use);
 

	
 
        // Construct entry in type table
 
        self.lookup.insert(definition_id, DefinedType{
 
            ast_root: root_id,
 
            ast_definition: definition_id,
 
            definition: DefinedTypeVariant::Function(FunctionType{
 
                return_types: definition.return_types.clone(),
 
                arguments,
 
                monomorphs: Vec::new(),
 
            }),
 
            poly_vars,
 
            is_polymorph,
 
        });
 

	
 
        Ok(true)
 
    }
 

	
 
    /// Resolves the basic component definition to an entry in the type table.
 
    /// It will not instantiate any monomorphized instancees of polymorphic
 
    /// component definitions.
 
    fn resolve_base_component_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, root_id: RootId, definition_id: DefinitionId) -> Result<bool, ParseError> {
 
        debug_assert!(ctx.heap[definition_id].is_component());
 
        debug_assert!(!self.lookup.contains_key(&definition_id), "base component already resolved");
 

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

	
 
        // Check argument types
 
        for param_id in &definition.parameters {
 
            let param = &ctx.heap[*param_id];
 
            let resolve_result = self.resolve_base_parser_type(modules, ctx, root_id, &param.parser_type, false)?;
 
            if !self.ingest_resolve_result(modules, ctx, resolve_result)? {
 
                return Ok(false)
 
            }
 
        }
 

	
 
        // Construct argument types
 
        let mut arguments = Vec::with_capacity(definition.parameters.len());
 
        for param_id in &definition.parameters {
 
            let param = &ctx.heap[*param_id];
 
            arguments.push(FunctionArgument{
 
                identifier: param.identifier.clone(),
 
                parser_type: param.parser_type.clone()
 
            })
 
        }
 

	
 
        // Check conflict of argument and polyarg identifiers
 
        Self::check_identifier_collision(
 
            modules, root_id, &arguments, |arg| &arg.identifier, "component argument"
 
        )?;
 
        Self::check_poly_args_collision(modules, ctx, root_id, &definition.poly_vars)?;
 

	
 
        // Construct polymorphic arguments
 
        let mut poly_vars = Self::create_polymorphic_variables(&definition.poly_vars);
 
        for argument in &arguments {
 
            Self::mark_used_polymorphic_variables(&mut poly_vars, &argument.parser_type);
 
        }
 

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

	
 
        // Construct entry in type table
 
        self.lookup.insert(definition_id, DefinedType{
 
            ast_root: root_id,
 
            ast_definition: definition_id,
 
            definition: DefinedTypeVariant::Component(ComponentType{
 
                variant: component_variant,
 
                arguments,
 
                monomorphs: Vec::new(),
 
            }),
 
            poly_vars,
 
            is_polymorph,
 
        });
 

	
 
        Ok(true)
 
    }
 

	
 
    /// Takes a ResolveResult and returns `true` if the caller can happily
 
    /// continue resolving its current type, or `false` if the caller must break
 
    /// resolving the current type and exit to the outer resolving loop. In the
 
    /// latter case the `result` value was `ResolveResult::Unresolved`, implying
 
    /// that the type must be resolved first.
 
    fn ingest_resolve_result(&mut self, modules: &[Module], ctx: &PassCtx, result: ResolveResult) -> Result<bool, ParseError> {
 
        match result {
 
            ResolveResult::Builtin | ResolveResult::PolymoprhicArgument => Ok(true),
 
            ResolveResult::Resolved(_, _) => Ok(true),
 
            ResolveResult::Unresolved(root_id, definition_id) => {
 
                if self.iter.contains(root_id, definition_id) {
 
                    // Cyclic dependency encountered
 

	
 
                } else {
 
                    // Type is not yet resolved, so push IDs on iterator and
 
                    // continue the resolving loop
 
                    self.iter.push(root_id, definition_id);
 
                    Ok(false)
 
                }
 
            }
 
        }
 
    }
 

	
 
    fn construct_cyclic_type_error(
 
        &self, modules: &[Module], ctx: &PassCtx, type_root_id: RootId, type_definition_id: DefinitionId
 
    ) -> ParseError {
 
        debug_assert!(self.iter.contains(type_root_id, type_definition_id));
 

	
 
        // Construct error message put at the top
 
        let module_source = &modules[type_root_id.index as usize].source;
 
        let mut error = ParseError::new_error_str_at_span(
 
            module_source, ctx.heap[type_definition_id].identifier().span,
 
            "Evaluating this type definition results in a cyclic type"
 
        );
 

	
 
        // Show a listing of all dependent types.
 
        // TODO: Make more correct later
 
        for (breadcrumb_idx, (root_id, definition_id)) in self.iter.breadcrumbs.iter().enumerate() {
 
            let msg = if breadcrumb_idx == 0 {
 
                "The cycle started with this definition"
 
            } else {
 
                "Which depends on this definition"
 
            };
 

	
 
            let module_source = &modules[root_id.index as usize].source;
 
            error = error.with_info_str_at_span(module_source, ctx.heap[*definition_id].identifier().span, msg);
 
        }
 

	
 
        return error;
 
    }
 

	
 
    /// Will check if the member type (field of a struct, embedded type in a
 
    /// union variant) is valid.
 
    fn check_member_parser_type(
 
@@ -1199,77 +842,6 @@ impl TypeTable {
 
        return Ok(());
 
    }
 

	
 
    /// Each type may consist of embedded types. If this type does not have a
 
    /// fixed implementation (e.g. an input port may have an embedded type
 
    /// indicating the type of messages, but it always exists in the runtime as
 
    /// a port identifier, so it has a fixed implementation) then this function
 
    /// will traverse the embedded types to ensure all of them are resolved.
 
    ///
 
    /// Hence if one checks a particular parser type for being resolved, one may
 
    /// get back a result value indicating an embedded type (with a different
 
    /// DefinitionId) is unresolved.
 
    fn resolve_base_parser_type(
 
        &mut self, modules: &[Module], ctx: &PassCtx, root_id: RootId,
 
        parser_type: &ParserType, allow_special_compiler_types: bool
 
    ) -> Result<ResolveResult, ParseError> {
 
        use ParserTypeVariant as PTV;
 

	
 
        // Result for the very first time we resolve a type (i.e the outer type
 
        // that we're actually looking up)
 
        let mut resolve_result = None;
 
        let mut set_resolve_result = |v: ResolveResult| {
 
            if resolve_result.is_none() { resolve_result = Some(v); }
 
        };
 

	
 
        for element in parser_type.elements.iter() {
 
            match element.variant {
 
                PTV::Void | PTV::InputOrOutput | PTV::ArrayLike | PTV::IntegerLike => {
 
                    if allow_special_compiler_types {
 
                        set_resolve_result(ResolveResult::Builtin);
 
                    } else {
 
                        unreachable!("compiler-only ParserTypeVariant within type definition");
 
                    }
 
                },
 
                PTV::Message | PTV::Bool |
 
                PTV::UInt8 | PTV::UInt16 | PTV::UInt32 | PTV::UInt64 |
 
                PTV::SInt8 | PTV::SInt16 | PTV::SInt32 | PTV::SInt64 |
 
                PTV::Character | PTV::String |
 
                PTV::Array | PTV::Input | PTV::Output => {
 
                    // Nothing to do: these are builtin types or types with a
 
                    // fixed implementation
 
                    set_resolve_result(ResolveResult::Builtin);
 
                },
 
                PTV::IntegerLiteral | PTV::Inferred => {
 
                    // As we're parsing the type definitions where these kinds
 
                    // of types are impossible/disallowed to express:
 
                    unreachable!("illegal ParserTypeVariant within type definition");
 
                },
 
                PTV::PolymorphicArgument(_, _) => {
 
                    set_resolve_result(ResolveResult::PolymoprhicArgument);
 
                },
 
                PTV::Definition(embedded_id, _) => {
 
                    let definition = &ctx.heap[embedded_id];
 
                    if !(definition.is_struct() || definition.is_enum() || definition.is_union()) {
 
                        let module_source = &modules[root_id.index as usize].source;
 
                        return Err(ParseError::new_error_str_at_span(
 
                            module_source, element.element_span, "expected a datatype (struct, enum or union)"
 
                        ))
 
                    }
 

	
 
                    if self.lookup.contains_key(&embedded_id) {
 
                        set_resolve_result(ResolveResult::Resolved(definition.defined_in(), embedded_id))
 
                    } else {
 
                        return Ok(ResolveResult::Unresolved(definition.defined_in(), embedded_id))
 
                    }
 
                }
 
            }
 
        }
 

	
 
        // If here then all types in the embedded type's tree were resolved.
 
        debug_assert!(resolve_result.is_some(), "faulty logic in ParserType resolver");
 
        return Ok(resolve_result.unwrap())
 
    }
 

	
 
    /// Go through a list of identifiers and ensure that all identifiers have
 
    /// unique names
 
    fn check_identifier_collision<T: Sized, F: Fn(&T) -> &Identifier>(
 
@@ -1335,6 +907,130 @@ impl TypeTable {
 
        Ok(())
 
    }
 

	
 
    //--------------------------------------------------------------------------
 
    // Determining memory layout for types
 
    //--------------------------------------------------------------------------
 

	
 
    pub(crate) fn layout_for_top_enum_breadcrumb(&mut self, modules: &[Module], ctx: &mut PassCtx, poly_args: Vec<ConcreteType>) -> Result<LayoutResult, ParseError> {
 
        // Enums are a bit special, because they never use their polymorphic
 
        // variables. So they only have to be layed out once. And this was
 
        // 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();
 
        if definition.monomorphs.iter().any(|v| v.poly_args == poly_args) {
 
            return Ok(LayoutResult::PopBreadcrumb);
 
        }
 

	
 
        definition.monomorphs.push(EnumMonomorph{ poly_args });
 
        return Ok(LayoutResult::PopBreadcrumb);
 
    }
 

	
 
    pub(crate) fn layout_for_top_union_breadcrumb(&mut self, modules: &[Module], ctx: &mut PassCtx, poly_args: Vec<ConcreteType>) -> Result<LayoutResult, ParseError> {
 
        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 num_embedded = poly_variant.embedded.len();
 

	
 
            while breadcrumb.next_embedded < num_embedded {
 
                let poly_embedded = &poly_variant.embedded[breadcrumb.next_embedded];
 

	
 

	
 
                breadcrumb.next_embedded += 1;
 
            }
 

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

	
 
        return Ok(LayoutResult::PopBreadcrumb);
 
    }
 

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

	
 
        let (part, size) = if min_val >= 0 {
 
            // Can be an unsigned integer
 
            if max_val <= (u32::MAX as i64) {
 
                (ConcreteTypePart::UInt32, 4)
 
            } else {
 
                (ConcreteTypePart::UInt64, 8)
 
            }
 
        } else {
 
            // Must be a signed integer
 
            if min_val >= (i32::MIN as i64) && max_val <= (i32::MAX as i64) {
 
                (ConcreteTypePart::SInt32, 4)
 
            } else {
 
                (ConcreteTypePart::SInt64, 8)
 
            }
 
        };
 

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

	
 
    pub(crate) fn prepare_layout_for_member_type(
 
        &self, definition_id: DefinitionId, parser_type: &ParserType, poly_args: &Vec<ConcreteType>
 
    ) -> LookupResult {
 
        use ParserTypeVariant as PTV;
 
        use ConcreteTypePart as CTP;
 

	
 
        // Helper for direct translation of parser type to concrete type
 
        fn parser_to_concrete_part(part: &ParserTypeVariant) -> Option<ConcreteTypePart> {
 
            match part {
 
                PTV::Void      => Some(CTP::Void),
 
                PTV::Message   => Some(CTP::Message),
 
                PTV::Bool      => Some(CTP::Bool),
 
                PTV::UInt8     => Some(CTP::UInt8),
 
                PTV::UInt16    => Some(CTP::UInt16),
 
                PTV::UInt32    => Some(CTP::UInt32),
 
                PTV::UInt64    => Some(CTP::UInt64),
 
                PTV::SInt8     => Some(CTP::SInt8),
 
                PTV::SInt16    => Some(CTP::SInt16),
 
                PTV::SInt32    => Some(CTP::SInt32),
 
                PTV::SInt64    => Some(CTP::SInt64),
 
                PTV::Character => Some(CTP::Character),
 
                PTV::String    => Some(CTP::String),
 
                PTV::Array     => Some(CTP::Array),
 
                PTV::Input     => Some(CTP::Input),
 
                PTV::Output    => Some(CTP::Output),
 
                PTV::Definition(definition_id, num) => Some(CTP::Instance(*definition_id, *num)),
 
                _              => None
 
            }
 
        }
 

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

	
 
        // Check if the type is an instance of a user-defined type, and if so,
 
        // whether the particular monomorph is already instantiated.
 
        if let CTP::Instance(definition_id, _) = concrete_parts[0] {
 
            let target_type = self.lookup.get(&definition_id).unwrap();
 
            // TODO: Continue here
 
        } else {
 

	
 
        }
 
    }
 

	
 
    //--------------------------------------------------------------------------
 
    // Breadcrumb management
 
    //--------------------------------------------------------------------------
 
@@ -1402,7 +1098,6 @@ impl TypeTable {
 
            definition_id,
 
            next_member: 0,
 
            next_embedded: 0,
 
            progression
 
        });
 
    }
 

	
0 comments (0 inline, 0 general)