CSY/reowolf Changeset - 643b55b4af53 · Centrum Wiskunde & Informatica (CWI)

Changeset - 643b55b4af53

Parent rev.

Child rev.

[Not reviewed]

0 1 0

MH - 4 years ago 2021-12-12 16:51:35
contact@maxhenger.nl

Prepare for rewrite of monomorphs in type table

1 file changed with 97 insertions and 59 deletions:

src/protocol/parser/type_table.rs

0 comments (0 inline, 0 general)

src/protocol/parser/type_table.rs

➞

Show inline comments

@@ @@ -126,531 +126,567 @@ impl DefinedType { @@
             while let Some((section_idx, a_section)) = a_iter.next() {
                 let b_section = b_iter.next().unwrap();
                 if check_if_poly_var_is_used && !self.poly_vars[section_idx].is_in_use {
                     continue;
+                }
                 if a_section != b_section {
                     return false;
+                }
+            }
             return true;
         };
         // Check check if type is polymorphic to some degree at all
         if cfg!(debug_assertions) {
             if let ConcreteTypePart::Instance(definition_id, num_poly_args) = parts[0] {
                 assert_eq!(definition_id, self.ast_definition);
                 assert_eq!(num_poly_args as usize, self.poly_vars.len());
             } else {
                 assert!(false, "concrete type {:?} is not a user-defined type", parts);
+            }
+        }
         match &self.definition {
             DTV::Enum(definition) => {
                 // Special case, enum is never a "true polymorph"
                 debug_assert!(!self.is_polymorph);
                 if definition.monomorphs.is_empty() {
                     return None
                 } else {
                     return Some(0)
+                }
             },
             DTV::Union(definition) => {
                 for (monomorph_idx, monomorph) in definition.monomorphs.iter().enumerate() {
                     if concrete_types_match(&monomorph.concrete_type.parts, parts, true) {
                         return Some(monomorph_idx);
+                    }
+                }
             },
             DTV::Struct(definition) => {
                 for (monomorph_idx, monomorph) in definition.monomorphs.iter().enumerate() {
                     if concrete_types_match(&monomorph.concrete_type.parts, parts, true) {
                         return Some(monomorph_idx);
+                    }
+                }
             },
             DTV::Function(definition) => {
                 for (monomorph_idx, monomorph) in definition.monomorphs.iter().enumerate() {
                     if concrete_types_match(&monomorph.concrete_type.parts, parts, false) {
                         return Some(monomorph_idx)
+                    }
+                }
+            }
             DTV::Component(definition) => {
                 for (monomorph_idx, monomorph) in definition.monomorphs.iter().enumerate() {
                     if concrete_types_match(&monomorph.concrete_type.parts, parts, false) {
                         return Some(monomorph_idx)
+                    }
+                }
+            }
+        }
         // Nothing matched
         return None;
+    }
     /// Retrieves size and alignment of the particular type's monomorph if it
     /// has been layed out in memory.
     pub(crate) fn get_monomorph_size_alignment(&self, idx: usize) -> Option<(usize, usize)> {
         use DefinedTypeVariant as DTV;
         let (size, alignment) = match &self.definition {
             DTV::Enum(def) => {
                 debug_assert!(idx == 0);
                 (def.size, def.alignment)
             },
             DTV::Union(def) => {
                 let monomorph = &def.monomorphs[idx];
                 (monomorph.stack_size, monomorph.stack_alignment)
             },
             DTV::Struct(def) => {
                 let monomorph = &def.monomorphs[idx];
                 (monomorph.size, monomorph.alignment)
             },
             DTV::Function(_) | DTV::Component(_) => {
                 // Type table should never be able to arrive here during layout
                 // of types. Types may only contain function prototypes.
                 unreachable!("retrieving size and alignment of procedure type");
+            }
         };
         if size == 0 && alignment == 0 {
             // The "marker" for when the type has not been layed out yet. Even
             // for zero-size types we will set alignment to `1` to simplify
             // alignment calculations.
             return None;
         } else {
             return Some((size, alignment));
+        }
+    }
+}
 pub enum DefinedTypeVariant {
     Enum(EnumType),
     Union(UnionType),
     Struct(StructType),
     Function(FunctionType),
     Component(ComponentType)
+}
 impl DefinedTypeVariant {
     pub(crate) fn type_class(&self) -> TypeClass {
         match self {
             DefinedTypeVariant::Enum(_) => TypeClass::Enum,
             DefinedTypeVariant::Union(_) => TypeClass::Union,
             DefinedTypeVariant::Struct(_) => TypeClass::Struct,
             DefinedTypeVariant::Function(_) => TypeClass::Function,
             DefinedTypeVariant::Component(_) => TypeClass::Component
+        }
+    }
     pub(crate) fn as_struct(&self) -> &StructType {
         match self {
             DefinedTypeVariant::Struct(v) => v,
             _ => unreachable!("Cannot convert {} to struct variant", self.type_class())
+        }
+    }
     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,
             _ => unreachable!("Cannot convert {} to enum variant", self.type_class())
+        }
+    }
     pub(crate) fn as_enum_mut(&mut self) -> &mut EnumType {
         match self {
             DefinedTypeVariant::Enum(v) => v,
             _ => unreachable!("Cannot convert {} to enum variant", self.type_class())
+        }
+    }
     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 as_union_mut(&mut self) -> &mut UnionType {
         match self {
             DefinedTypeVariant::Union(v) => v,
             _ => unreachable!("Cannot convert {} to union variant", self.type_class())
+        }
+    }
     pub(crate) fn procedure_monomorphs(&self) -> &Vec<ProcedureMonomorph> {
         use DefinedTypeVariant::*;
         match self {
             Function(v) => &v.monomorphs,
             Component(v) => &v.monomorphs,
             _ => unreachable!("cannot get procedure monomorphs from {}", self.type_class()),
+        }
+    }
     pub(crate) fn procedure_monomorphs_mut(&mut self) -> &mut Vec<ProcedureMonomorph> {
         use DefinedTypeVariant::*;
         match self {
             Function(v) => &mut v.monomorphs,
             Component(v) => &mut v.monomorphs,
             _ => unreachable!("cannot get procedure monomorphs from {}", self.type_class()),
+        }
+    }
+}
 pub struct PolymorphicVariable {
     identifier: Identifier,
     is_in_use: bool, // a polymorphic argument may be defined, but not used by the type definition
+}
 /// 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)
 pub struct ProcedureMonomorph {
     // Expression data for one particular monomorph
     pub concrete_type: ConcreteType,
     pub arg_types: Vec<ConcreteType>,
     pub expr_data: Vec<MonomorphExpression>,
+}
 /// `EnumType` is the classical C/C++ enum type. It has various variants with
 /// an assigned integer value. The integer values may be user-defined,
 /// compiler-defined, or a mix of the two. If a user assigns the same enum
 /// value multiple times, we assume the user is an expert and we consider both
 /// variants to be equal to one another.
 pub struct EnumType {
     pub variants: Vec<EnumVariant>,
     pub monomorphs: Vec<EnumMonomorph>,
     pub minimum_tag_value: i64,
     pub maximum_tag_value: i64,
     pub tag_type: ConcreteType,
     pub size: usize,
     pub alignment: usize,
+}
 // TODO: Also support maximum u64 value
 pub struct EnumVariant {
     pub identifier: Identifier,
     pub value: i64,
+}
 pub struct EnumMonomorph {
     pub concrete_type: 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.
 /// For potentially infinite types (i.e. a tree, or a linked list) only unions
 /// can break the infinite cycle. So when we lay out these unions in memory we
 /// will reserve enough space on the stack for all union variants that do not
 /// cause "type loops" (i.e. a union `A` with a variant containing a struct
 /// `B`). And we will reserve enough space on the heap (and store a pointer in
 /// the union) for all variants which do cause type loops (i.e. a union `A`
 /// with a variant to a struct `B` that contains the union `A` again).
 pub struct UnionType {
     pub variants: Vec<UnionVariant>,
     pub monomorphs: Vec<UnionMonomorph>,
     pub tag_type: ConcreteType,
     pub tag_size: usize,
+}
 pub struct UnionVariant {
     pub identifier: Identifier,
     pub embedded: Vec<ParserType>, // zero-length does not have embedded values
     pub tag_value: i64,
+}
 pub struct UnionMonomorph {
     pub concrete_type: ConcreteType,
     pub variants: Vec<UnionMonomorphVariant>,
     // stack_size is the size of the union on the stack, includes the tag
     pub stack_size: usize,
     pub stack_alignment: usize,
     // heap_size contains the allocated size of the union in the case it
     // is used to break a type loop. If it is 0, then it doesn't require
     // allocation and lives entirely on the stack.
     pub heap_size: usize,
     pub heap_alignment: usize,
+}
 pub struct UnionMonomorphVariant {
     pub lives_on_heap: bool,
     pub embedded: Vec<UnionMonomorphEmbedded>,
+}
 pub struct UnionMonomorphEmbedded {
     pub concrete_type: ConcreteType,
     // Note that the meaning of the offset (and alignment) depend on whether or
     // not the variant lives on the stack/heap. If it lives on the stack then
     // they refer to the offset from the start of the union value (so the first
     // embedded type lives at a non-zero offset, because the union tag sits in
     // the front). If it lives on the heap then it refers to the offset from the
     // allocated memory region (so the first embedded type lives at a 0 offset).
     pub size: usize,
     pub alignment: 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<StructMonomorph>,
+}
 pub struct StructField {
     pub identifier: Identifier,
     pub parser_type: ParserType,
+}
 pub struct StructMonomorph {
     pub concrete_type: ConcreteType,
     pub fields: Vec<StructMonomorphField>,
     pub size: usize,
     pub alignment: usize,
+}
 pub struct StructMonomorphField {
     pub concrete_type: ConcreteType,
     pub size: usize,
     pub alignment: 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>,
     pub monomorphs: Vec<ProcedureMonomorph>,
+}
 pub struct ComponentType {
     pub variant: ComponentVariant,
     pub arguments: Vec<FunctionArgument>,
     pub monomorphs: Vec<ProcedureMonomorph>
+}
 pub struct FunctionArgument {
     identifier: Identifier,
     parser_type: ParserType,
+}
 /// Represents the data associated with a single expression after type inference
 /// for a monomorph (or just the normal expression types, if dealing with a
 /// non-polymorphic function/component).
 pub struct MonomorphExpression {
     // The output type of the expression. Note that for a function it is not the
     // function's signature but its return type
     pub(crate) expr_type: ConcreteType,
     // Has multiple meanings: the field index for select expressions, the
     // monomorph index for polymorphic function calls or literals. Negative
     // values are never used, but used to catch programming errors.
     pub(crate) field_or_monomorph_idx: i32,
+}
 //------------------------------------------------------------------------------
 // Type monomorph storage
 //------------------------------------------------------------------------------
 /// Union of all possible type monomorphs. The term "monomorph" is perhaps not
 /// entirely correct: nonpolymorphic types will also get a "monomorph" entry to
 /// store the size/offset/alignment data of all types.
 enum TypeMonomorph {
     Enum(EnumMonomorph),
     Struct(StructMonomorph),
     Union(UnionMonomorph),
     Procedure(ProcedureMonomorph), // functions, components
     Tuple(TupleMonomorph),
+}
 /// Enum monomorph
 pub struct EnumMonomorph {
     pub concrete_type: ConcreteType,
     pub size: usize,
     pub alignment: usize,
+}
 /// Struct monomorph
 pub struct StructMonomorph {
     pub concrete_type: ConcreteType,
     pub fields: Vec<StructMonomorphField>,
     pub size: usize,
     pub alignment: usize,
+}
 pub struct StructMonomorphField {
     pub concrete_type: ConcreteType,
     pub size: usize,
     pub alignment: usize,
     pub offset: usize,
+}
 /// Union monomorph
 pub struct UnionMonomorph {
     pub concrete_type: ConcreteType,
     pub variants: Vec<UnionMonomorphVariant>,
     // stack_size is the size of the union on the stack, includes the tag
     pub stack_size: usize,
     pub stack_alignment: usize,
     // heap_size contains the allocated size of the union in the case it
     // is used to break a type loop. If it is 0, then it doesn't require
     // allocation and lives entirely on the stack.
     pub heap_size: usize,
     pub heap_alignment: usize,
+}
 pub struct UnionMonomorphVariant {
     pub lives_on_heap: bool,
     pub embedded: Vec<UnionMonomorphEmbedded>,
+}
 pub struct UnionMonomorphEmbedded {
     pub concrete_type: ConcreteType,
     // Note that the meaning of the offset (and alignment) depend on whether or
     // not the variant lives on the stack/heap. If it lives on the stack then
     // they refer to the offset from the start of the union value (so the first
     // embedded type lives at a non-zero offset, because the union tag sits in
     // the front). If it lives on the heap then it refers to the offset from the
     // allocated memory region (so the first embedded type lives at a 0 offset).
     pub size: usize,
     pub alignment: usize,
     pub offset: usize,
+}
 /// Procedure (functions and components of all possible types) monomorph. Also
 /// stores the expression type data from the typechecking/inferencing pass.
 pub struct ProcedureMonomorph {
     // Expression data for one particular monomorph
     pub concrete_type: ConcreteType,
     pub arg_types: Vec<ConcreteType>,
     pub expr_data: Vec<MonomorphExpression>,
+}
 /// Tuple monomorph. Again a kind of exception because one cannot define a named
 /// tuple type containing explicit polymorphic variables. But again: we need to
 /// store size/offset/alignment information, so we do it here.
 pub struct TupleMonomorph {
     pub concrete_type: ConcreteType,
     pub size: usize,
     pub alignment: usize,
     pub members: Vec<TupleMonomorphMember>
+}
 pub struct TupleMonomorphMember {
     pub concrete_type: ConcreteType,
     pub size: usize,
     pub alignment: usize,
     pub offset: usize,
+}
 //------------------------------------------------------------------------------
 // Type table
 //------------------------------------------------------------------------------
 // Programmer note: keep this struct free of dynamically allocated memory
 #[derive(Clone)]
 struct TypeLoopBreadcrumb {
     definition_id: DefinitionId,
     monomorph_idx: usize,
     next_member: usize,
     next_embedded: usize, // for unions, the index into the variant's embedded types
+}
 #[derive(Clone)]
 struct MemoryBreadcrumb {
     definition_id: DefinitionId,
     monomorph_idx: usize,
     next_member: usize,
     next_embedded: usize,
     first_size_alignment_idx: usize,
+}
 #[derive(Debug, PartialEq, Eq)]
 enum TypeLoopResult {
     TypeExists,
     PushBreadcrumb(DefinitionId, ConcreteType),
     TypeLoop(usize), // index into vec of breadcrumbs at which the type matched
+}
 enum MemoryLayoutResult {
     TypeExists(usize, usize), // (size, alignment)
     PushBreadcrumb(MemoryBreadcrumb),
+}
 // TODO: @Optimize, initial memory-unoptimized implementation
 struct TypeLoopEntry {
     definition_id: DefinitionId,
     monomorph_idx: usize,
     is_union: bool,
+}
 struct TypeLoop {
     members: Vec<TypeLoopEntry>
+}
 pub struct TypeTable {
     /// Lookup from AST DefinitionId to a defined type. Considering possible
     /// polymorphs is done inside the `DefinedType` struct.
     lookup: HashMap<DefinitionId, DefinedType>,
     /// Breadcrumbs left behind while trying to find type loops. Also used to
     /// determine sizes of types when all type loops are detected.
     type_loop_breadcrumbs: Vec<TypeLoopBreadcrumb>,
     type_loops: Vec<TypeLoop>,
     /// Stores all encountered types during type loop detection. Used afterwards
     /// to iterate over all types in order to compute size/alignment.
     encountered_types: Vec<TypeLoopEntry>,
     /// Breadcrumbs and temporary storage during memory layout computation.
     memory_layout_breadcrumbs: Vec<MemoryBreadcrumb>,
     size_alignment_stack: Vec<(usize, usize)>,
+}
 impl TypeTable {
     /// Construct a new type table without any resolved types.
     pub(crate) fn new() -> Self {
         Self{
             lookup: HashMap::new(),
             type_loop_breadcrumbs: Vec::with_capacity(32),
             type_loops: Vec::with_capacity(8),
             encountered_types: Vec::with_capacity(32),
             memory_layout_breadcrumbs: Vec::with_capacity(32),
             size_alignment_stack: Vec::with_capacity(64),
+        }
+    }
     /// Iterates over all defined types (polymorphic and non-polymorphic) and
     /// add their types in two passes. In the first pass we will just add the
     /// base types (we will not consider monomorphs, and we will not compute
     /// byte sizes). In the second pass we will compute byte sizes of
     /// non-polymorphic types, and potentially the monomorphs that are embedded
     /// in those types.
     pub(crate) fn build_base_types(&mut self, modules: &mut [Module], ctx: &mut PassCtx) -> Result<(), ParseError> {
         // Make sure we're allowed to cast root_id to index into ctx.modules
         debug_assert!(modules.iter().all(|m| m.phase >= ModuleCompilationPhase::DefinitionsParsed));
         debug_assert!(self.lookup.is_empty());
         if cfg!(debug_assertions) {
             for (index, module) in modules.iter().enumerate() {
                 debug_assert_eq!(index, module.root_id.index as usize);
+            }
+        }
         // Use context to guess hashmap size of the base types
         let reserve_size = ctx.heap.definitions.len();
         self.lookup.reserve(reserve_size);
         // Resolve all base types
         for definition_idx in 0..ctx.heap.definitions.len() {
             let definition_id = ctx.heap.definitions.get_id(definition_idx);
             let definition = &ctx.heap[definition_id];
             match definition {
                 Definition::Enum(_) => self.build_base_enum_definition(modules, ctx, definition_id)?,
                 Definition::Union(_) => self.build_base_union_definition(modules, ctx, definition_id)?,
                 Definition::Struct(_) => self.build_base_struct_definition(modules, ctx, definition_id)?,
                 Definition::Function(_) => self.build_base_function_definition(modules, ctx, definition_id)?,
                 Definition::Component(_) => self.build_base_component_definition(modules, ctx, definition_id)?,
+            }
+        }
         debug_assert_eq!(self.lookup.len(), reserve_size, "mismatch in reserved size of type table"); // NOTE: Temp fix for builtin functions
         for module in modules.iter_mut() {
             module.phase = ModuleCompilationPhase::TypesAddedToTable;
+        }
         // 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 poly_type = self.lookup.get(&definition_id).unwrap();
             // Here we explicitly want to instantiate types which have no
             // polymorphic arguments (even if it has phantom polymorphic
             // arguments) because otherwise the user will see very weird
             // error messages.
             if poly_type.definition.type_class().is_data_type() && poly_type.poly_vars.is_empty() && poly_type.num_monomorphs() == 0 {
                 self.detect_and_resolve_type_loops_for(
                     modules, ctx.heap,
                     ConcreteType{
                         parts: vec![ConcreteTypePart::Instance(definition_id, 0)]
                     },
                 )?;
                 self.lay_out_memory_for_encountered_types(ctx.arch);
+            }
+        }
         Ok(())
+    }
     /// Retrieves base definition from type table. We must be able to retrieve
     /// it as we resolve all base types upon type table construction (for now).
     /// However, in the future we might do on-demand type resolving, so return
     /// an option anyway
     pub(crate) fn get_base_definition(&self, definition_id: &DefinitionId) -> Option<&DefinedType> {
         self.lookup.get(&definition_id)
+    }
     /// Returns the index into the monomorph type array if the procedure type
     /// already has a (reserved) monomorph.
     pub(crate) fn get_procedure_monomorph_index(&self, definition_id: &DefinitionId, types: &ConcreteType) -> Option<i32> {
         let def = self.lookup.get(definition_id).unwrap();
         let monos = def.definition.procedure_monomorphs();
         return monos.iter()
             .position(|v| v.concrete_type == *types)
             .map(|v| v as i32);
+    }
     /// Returns a mutable reference to a procedure's monomorph expression data.
     /// Used by typechecker to fill in previously reserved type information
     pub(crate) fn get_procedure_expression_data_mut(&mut self, definition_id: &DefinitionId, monomorph_idx: i32) -> &mut ProcedureMonomorph {
         debug_assert!(monomorph_idx >= 0);
         let def = self.lookup.get_mut(definition_id).unwrap();
         let monomorphs = def.definition.procedure_monomorphs_mut();
         return &mut monomorphs[monomorph_idx as usize];
+    }
     pub(crate) fn get_procedure_expression_data(&self, definition_id: &DefinitionId, monomorph_idx: i32) -> &ProcedureMonomorph {
         debug_assert!(monomorph_idx >= 0);
         let def = self.lookup.get(definition_id).unwrap();
         let monomorphs = def.definition.procedure_monomorphs();
         return &monomorphs[monomorph_idx as usize];
+    }
     /// Reserves space for a monomorph of a polymorphic procedure. The index
     /// will point into a (reserved) slot of the array of expression types. The
     /// monomorph may NOT exist yet (because the reservation implies that we're
     /// going to be performing typechecking on it, and we don't want to
     /// check the same monomorph twice)
     pub(crate) fn reserve_procedure_monomorph_index(&mut self, definition_id: &DefinitionId, concrete_type: ConcreteType) -> i32 {
         let def = self.lookup.get_mut(definition_id).unwrap();
         let mono_types = def.definition.procedure_monomorphs_mut();
         debug_assert!(def.is_polymorph == (concrete_type.parts.len() != 1));
         debug_assert!(!mono_types.iter().any(|v| v.concrete_type == concrete_type));
         let mono_idx = mono_types.len();
         mono_types.push(ProcedureMonomorph{
             concrete_type,
             arg_types: Vec::new(),
             expr_data: Vec::new(),
         });
         return mono_idx as i32;
@@ @@ -1201,384 +1237,386 @@ impl TypeTable { @@
                         let breadcrumb = &mut self.type_loop_breadcrumbs[breadcrumb_idx];
                         let mut is_union = false;
                         let entry = self.lookup.get_mut(&breadcrumb.definition_id).unwrap();
                         match &mut entry.definition {
                             DTV::Union(definition) => {
                                 // Mark the currently processed variant as requiring heap
                                 // allocation, then advance the *embedded* type. The loop above
                                 // will then take care of advancing it to the next *member*.
                                 let monomorph = &mut definition.monomorphs[breadcrumb.monomorph_idx];
                                 let variant = &mut monomorph.variants[breadcrumb.next_member];
                                 variant.lives_on_heap = true;
                                 breadcrumb.next_embedded += 1;
                                 is_union = true;
                                 contains_union = true;
                             },
                             _ => {}, // else: we don't care for now
+                        }
                         loop_members.push(TypeLoopEntry{
                             definition_id: breadcrumb.definition_id,
                             monomorph_idx: breadcrumb.monomorph_idx,
                             is_union
                         });
+                    }
                     let new_type_loop = TypeLoop{ members: loop_members };
                     if !contains_union {
                         // No way to (potentially) break the union. So return a
                         // type loop error. This is because otherwise our
                         // breadcrumb resolver ends up in an infinite loop.
                         return Err(construct_type_loop_error(
                             self, &new_type_loop, modules, heap
                         ));
+                    }
                     self.type_loops.push(new_type_loop);
+                }
+            }
+        }
         // 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], heap: &Heap, 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.
             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
             };
             let type_name = monomorph_type.display_name(&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, or do not have embedded types)",
                     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)
             };
             let ast_definition = &heap[defined_type.ast_definition];
             let ast_root_id = ast_definition.defined_in();
             return (
                 &modules[ast_root_id.index as usize].source,
                 ast_definition.identifier().span,
                 message
             );
+        }
         fn construct_type_loop_error(table: &TypeTable, type_loop: &TypeLoop, modules: &[Module], heap: &Heap) -> ParseError {
             let first_entry = &type_loop.members[0];
             let first_type = table.lookup.get(&first_entry.definition_id).unwrap();
             let (first_module, first_span, first_message) = type_loop_source_span_and_message(
                 modules, heap, 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 = table.lookup.get(&first_entry.definition_id).unwrap();
                 let (module, span, message) = type_loop_source_span_and_message(
                     modules, heap, entry_type, entry.monomorph_idx, member_idx
                 );
                 parse_error = parse_error.with_info_at_span(module, span, message);
+            }
             parse_error
+        }
         for type_loop in &self.type_loops {
             let mut can_be_broken = false;
             debug_assert!(!type_loop.members.is_empty());
             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];
                     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;
+                    }
+                }
+            }
             if !can_be_broken {
                 // Construct a type loop error
                 return Err(construct_type_loop_error(self, type_loop, modules, heap));
+            }
+        }
         // If here, then all type loops have been resolved and we can lay out
         // all of the members
         self.type_loops.clear();
         return Ok(());
+    }
     /// Checks if the specified type needs to be resolved (i.e. we need to push
     /// a breadcrumb), is already resolved (i.e. we can continue with the next
     /// member of the currently considered type) or is in the process of being
     /// resolved (i.e. we're in a type loop). Because of borrowing rules we
     /// don't do any modifications of internal types here. Hence: if we
     /// return `PushBreadcrumb` then call `handle_new_breadcrumb_for_type_loops`
     /// to take care of storing the appropriate types.
     fn check_member_for_type_loops(&self, definition_type: &ConcreteType) -> TypeLoopResult {
         use ConcreteTypePart as CTP;
         // We're only interested in user-defined types, so exit if it is a
         // builtin of some sort.
         debug_assert!(!definition_type.parts.is_empty());
         let definition_id = match &definition_type.parts[0] {
             CTP::Instance(definition_id, _) |
             CTP::Function(definition_id, _) |
             CTP::Component(definition_id, _) => {
                 *definition_id
             },
             _ => {
                 return TypeLoopResult::TypeExists
             },
         };
         let base_type = self.lookup.get(&definition_id).unwrap();
         if let Some(mono_idx) = base_type.get_monomorph_index(&definition_type.parts) {
             // Monomorph is already known. Check if it is present in the
             // breadcrumbs. If so, then we are in a type loop
             for (breadcrumb_idx, breadcrumb) in self.type_loop_breadcrumbs.iter().enumerate() {
                 if breadcrumb.definition_id == definition_id && breadcrumb.monomorph_idx == mono_idx {
                     return TypeLoopResult::TypeLoop(breadcrumb_idx);
+                }
+            }
             return TypeLoopResult::TypeExists;
+        }
         // Type is not yet known, so we need to insert it into the lookup and
         // push a new breadcrumb.
         return TypeLoopResult::PushBreadcrumb(definition_id, definition_type.clone());
+    }
     /// Handles the `PushBreadcrumb` result for a `check_member_for_type_loops`
     /// call.
     fn handle_new_breadcrumb_for_type_loops(&mut self, definition_id: DefinitionId, definition_type: ConcreteType) {
         use DefinedTypeVariant as DTV;
         let base_type = self.lookup.get_mut(&definition_id).unwrap();
         let mut is_union = false;
         let monomorph_idx = match &mut base_type.definition {
             DTV::Enum(definition) => {
                 debug_assert!(definition.monomorphs.is_empty());
                 definition.monomorphs.push(EnumMonomorph{
                     concrete_type: definition_type,
                     size: 0,
                     alignment: 0,
                 });
             },
             DTV::Union(definition) => {
                 // Create all the variants with their concrete types
                 let mut mono_variants = Vec::with_capacity(definition.variants.len());
                 for poly_variant in &definition.variants {
                     let mut mono_embedded = Vec::with_capacity(poly_variant.embedded.len());
                     for poly_embedded in &poly_variant.embedded {
                         let mono_concrete = Self::construct_concrete_type(poly_embedded, &definition_type);
                         mono_embedded.push(UnionMonomorphEmbedded{
                             concrete_type: mono_concrete,
                             size: 0,
                             alignment: 0,
                             offset: 0
                         });
+                    }
                     mono_variants.push(UnionMonomorphVariant{
                         lives_on_heap: false,
                         embedded: mono_embedded,
                     })
+                }
                 let mono_idx = definition.monomorphs.len();
                 definition.monomorphs.push(UnionMonomorph{
                     concrete_type: definition_type,
                     variants: mono_variants,
                     stack_size: 0,
                     stack_alignment: 0,
                     heap_size: 0,
                     heap_alignment: 0
                 });
                 is_union = true;
                 mono_idx
             },
             DTV::Struct(definition) => {
                 let mut mono_fields = Vec::with_capacity(definition.fields.len());
                 for poly_field in &definition.fields {
                     let mono_concrete = Self::construct_concrete_type(&poly_field.parser_type, &definition_type);
                     mono_fields.push(StructMonomorphField{
                         concrete_type: mono_concrete,
                         size: 0,
                         alignment: 0,
                         offset: 0
                     })
+                }
                 let mono_idx = definition.monomorphs.len();
                 definition.monomorphs.push(StructMonomorph{
                     concrete_type: definition_type,
                     fields: mono_fields,
                     size: 0,
                     alignment: 0
                 });
                 mono_idx
             },
             DTV::Function(_) | DTV::Component(_) => {
                 unreachable!("pushing type resolving breadcrumb for procedure type")
             },
         };
         self.encountered_types.push(TypeLoopEntry{
             definition_id,
             monomorph_idx,
             is_union,
         });
         self.type_loop_breadcrumbs.push(TypeLoopBreadcrumb{
             definition_id,
             monomorph_idx,
             next_member: 0,
             next_embedded: 0,
         });
+    }
     /// 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;
         // TODO: Combine with code in pass_typing.rs
         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::Tuple(num) => Some(CTP::Tuple(*num)),
                 PTV::Definition(definition_id, num) => Some(CTP::Instance(*definition_id, *num)),
                 _              => None
+            }
+        }
         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;
+            }
             // 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.variant {
                 debug_assert_eq!(_container_definition_id, get_concrete_type_definition(container_type));
                 let mut container_iter = container_type.embedded_iter(0);
                 for _ in 0..poly_arg_idx {
                     container_iter.next();
+                }
                 let poly_section = container_iter.next().unwrap();
                 parts.extend(poly_section);
                 continue;
+            }
             unreachable!("unexpected type part {:?} from {:?}", member_part, member_type);
+        }
         return ConcreteType{ parts };
+    }
     //--------------------------------------------------------------------------
     // Determining memory layout for types
     //--------------------------------------------------------------------------
     fn lay_out_memory_for_encountered_types(&mut self, arch: &TargetArch) {
         use DefinedTypeVariant as DTV;
         // Just finished type loop detection, so we're left with the encountered
         // types only
         debug_assert!(self.type_loops.is_empty());
         debug_assert!(!self.encountered_types.is_empty());
         debug_assert!(self.memory_layout_breadcrumbs.is_empty());
         debug_assert!(self.size_alignment_stack.is_empty());
         // Push the first entry (the type we originally started with when we
         // were detecting type loops)
         let first_entry = &self.encountered_types[0];
         self.memory_layout_breadcrumbs.push(MemoryBreadcrumb{
             definition_id: first_entry.definition_id,
             monomorph_idx: first_entry.monomorph_idx,
             next_member: 0,
             next_embedded: 0,
             first_size_alignment_idx: 0,
         });
         // Enter the main resolving loop
         'breadcrumb_loop: while !self.memory_layout_breadcrumbs.is_empty() {
             let cur_breadcrumb_idx = self.memory_layout_breadcrumbs.len() - 1;
             let mut breadcrumb = self.memory_layout_breadcrumbs[cur_breadcrumb_idx].clone();
             let poly_type = self.lookup.get(&breadcrumb.definition_id).unwrap();
             match &poly_type.definition {
                 DTV::Enum(definition) => {
                     // Size should already be computed
                     debug_assert!(definition.size != 0 && definition.alignment != 0);
                 },
                 DTV::Union(definition) => {
                     // Retrieve size/alignment of each embedded type. We do not
                     // compute the offsets or total type sizes yet.
                     let mono_type = &definition.monomorphs[breadcrumb.monomorph_idx];
                     let num_variants = mono_type.variants.len();
                     while breadcrumb.next_member < num_variants {
                         let mono_variant = &mono_type.variants[breadcrumb.next_member];
                         if mono_variant.lives_on_heap {
                             // To prevent type loops we made this a heap-
                             // allocated variant. This implies we cannot
                             // compute sizes of members at this point.
                         } else {
                             let num_embedded = mono_variant.embedded.len();

0 comments (0 inline, 0 general)