diff --git a/src/protocol/ast.rs b/src/protocol/ast.rs index 5c53156902b10df749a1e2f88698a757bd10e025..8eb367d928941e37bd987f820a3feab632a9da34 100644 --- a/src/protocol/ast.rs +++ b/src/protocol/ast.rs @@ -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 { + 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)] diff --git a/src/protocol/parser/type_table.rs b/src/protocol/parser/type_table.rs index 9de534b863207aa8857807c7d82d0fce3be1f8de..a2d661200c693733b9e05ff4b86c55ea323f33da 100644 --- a/src/protocol/parser/type_table.rs +++ b/src/protocol/parser/type_table.rs @@ -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 { 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 { + 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, -} - /// 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 + 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, + pub concrete_type: ConcreteType, pub variants: Vec, // 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, + pub concrete_type: ConcreteType, pub fields: Vec, 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 +} + pub struct TypeTable { /// Lookup from AST DefinitionId to a defined type. Considering possible /// polymorphs is done inside the `DefinedType` struct. lookup: HashMap, /// Breadcrumbs left behind while resolving embedded types - breadcrumbs: Vec, + breadcrumbs_old: Vec, + /// Breadcrumbs left behind while trying to find type loops. Also used to + /// determine sizes of types when all type loops are detected. + breadcrumbs: Vec, + type_loops: Vec, + encountered_types: Vec, } 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 { + 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 { - // 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 { - // 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 { - // 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 { - 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 { - 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, 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 { 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) { - 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