From 87c3d649056d84946e97148c5e241e4a6141f922 2021-07-14 09:14:23 From: MH Date: 2021-07-14 09:14:23 Subject: [PATCH] more progress on memory layout --- diff --git a/src/protocol/parser/type_table.rs b/src/protocol/parser/type_table.rs index 2ab66833e3a2d72a9dcf7eca051f6adb2e4f8154..7978bd123284fcbdceefa6fa6c1fa73bfc12ee2c 100644 --- a/src/protocol/parser/type_table.rs +++ b/src/protocol/parser/type_table.rs @@ -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 { - 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 { - 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, - pub monomorphs: Vec, + pub monomorphs: Vec, + 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 +} + /// `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, - pub monomorphs: Vec, + pub monomorphs: Vec, pub requires_allocation: bool, pub contains_unallocated_variant: bool, } @@ -225,9 +231,33 @@ pub struct UnionVariant { pub identifier: Identifier, pub embedded: Vec, // zero-length does not have embedded values pub tag_value: i64, - pub exists_in_heap: bool, } +pub struct UnionMonomorph { + pub poly_args: Vec, + pub variants: Vec, + 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, +} + +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, pub monomorphs: Vec, @@ -238,6 +268,19 @@ pub struct StructField { pub parser_type: ParserType, } +pub struct StructMonomorph { + pub poly_args: Vec, + pub fields: Vec, +} + +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, pub arguments: Vec, @@ -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), + TypeLoop(RootId, DefinitionId, Vec), +} + +enum LookupResult { + Exists(ConcreteType), // type was looked up and exists (or is a builtin) + Missing(DefinitionId, Vec), // 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, /// Breadcrumbs left behind while resolving embedded types - breadcrumbs: Vec, + breadcrumbs: Vec, 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, ¶meter.parser_type + modules, ctx, root_id, ¶meter.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 { - // 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 { - 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 { - 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 { - 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, ¶m.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 { - 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, ¶m.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 { - 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 { - 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 &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) -> Result { + // 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) -> Result { + 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 + ) -> 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 { + 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 }); }