diff --git a/src/protocol/ast.rs b/src/protocol/ast.rs index 2e5bdc8d168c3eba253195ba4b8075f3313e7a88..3768723cfe9b4a64bf1f1ab077d2d1e3ba2ad71d 100644 --- a/src/protocol/ast.rs +++ b/src/protocol/ast.rs @@ -480,7 +480,7 @@ impl<'a> Iterator for ParserTypeIter<'a> { /// ConcreteType is the representation of a type after the type inference and /// checker is finished. These are fully typed. -#[derive(Debug, Clone, Copy, Eq, PartialEq)] +#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)] pub enum ConcreteTypePart { // Special types (cannot be explicitly constructed by the programmer) Void, @@ -504,7 +504,7 @@ pub enum ConcreteTypePart { } impl ConcreteTypePart { - fn num_embedded(&self) -> u32 { + pub(crate) fn num_embedded(&self) -> u32 { use ConcreteTypePart::*; match self { diff --git a/src/protocol/eval/executor.rs b/src/protocol/eval/executor.rs index 670993cbc27ba8d66c0c91e19b18288c5e7742cf..8a80bd8dce90a3dc81de4d03d545a90e2b1a5d27 100644 --- a/src/protocol/eval/executor.rs +++ b/src/protocol/eval/executor.rs @@ -226,7 +226,6 @@ impl Prompt { }; // Maybe do typechecking in the future? - debug_assert!((monomorph_idx as usize) < _types.get_base_definition(&def).unwrap().definition.procedure_monomorphs().len()); let new_frame = Frame::new(heap, def, monomorph_idx); let max_stack_size = new_frame.max_stack_size; prompt.frames.push(new_frame); @@ -475,7 +474,7 @@ impl Prompt { }, Expression::Select(expr) => { let subject= cur_frame.expr_values.pop_back().unwrap(); - let mono_data = types.get_procedure_expression_data(&cur_frame.definition, cur_frame.monomorph_idx); + let mono_data = types.get_procedure_monomorph(cur_frame.monomorph_idx); let field_idx = mono_data.expr_data[expr.unique_id_in_definition as usize].field_or_monomorph_idx as u32; // Note: same as above: clone if value lives on expr stack, simply @@ -517,7 +516,7 @@ impl Prompt { } Literal::Integer(lit_value) => { use ConcreteTypePart as CTP; - let def_types = types.get_procedure_expression_data(&cur_frame.definition, cur_frame.monomorph_idx); + let def_types = types.get_procedure_monomorph(cur_frame.monomorph_idx); let concrete_type = &def_types.expr_data[expr.unique_id_in_definition as usize].expr_type; debug_assert_eq!(concrete_type.parts.len(), 1); @@ -559,7 +558,7 @@ impl Prompt { cur_frame.expr_values.push_back(value); }, Expression::Cast(expr) => { - let mono_data = types.get_procedure_expression_data(&cur_frame.definition, cur_frame.monomorph_idx); + let mono_data = types.get_procedure_monomorph(cur_frame.monomorph_idx); let output_type = &mono_data.expr_data[expr.unique_id_in_definition as usize].expr_type; // Typechecking reduced this to two cases: either we @@ -741,7 +740,7 @@ impl Prompt { } // Determine the monomorph index of the function we're calling - let mono_data = types.get_procedure_expression_data(&cur_frame.definition, cur_frame.monomorph_idx); + let mono_data = types.get_procedure_monomorph(cur_frame.monomorph_idx); let call_data = &mono_data.expr_data[expr.unique_id_in_definition as usize]; // Push the new frame and reserve its stack size @@ -974,7 +973,7 @@ impl Prompt { "mismatch in expr stack size and number of arguments for new statement" ); - let mono_data = types.get_procedure_expression_data(&cur_frame.definition, cur_frame.monomorph_idx); + let mono_data = types.get_procedure_monomorph(cur_frame.monomorph_idx); let expr_data = &mono_data.expr_data[call_expr.unique_id_in_definition as usize]; // Note that due to expression value evaluation they exist in diff --git a/src/protocol/mod.rs b/src/protocol/mod.rs index 8c3b36972848a66314c30f688e57cd46b27c4434..80cf2c2384e5bf2f619e58947a66d22db4d73ef3 100644 --- a/src/protocol/mod.rs +++ b/src/protocol/mod.rs @@ -96,27 +96,30 @@ impl ProtocolDescription { } let definition_id = definition_id.unwrap(); - let definition = &self.heap[definition_id]; - if !definition.is_component() { + let ast_definition = &self.heap[definition_id]; + if !ast_definition.is_component() { return Err(ComponentCreationError::DefinitionNotComponent); } // Make sure that the types of the provided value group matches that of // the expected types. - let definition = definition.as_component(); - if !definition.poly_vars.is_empty() { + let ast_definition = ast_definition.as_component(); + if !ast_definition.poly_vars.is_empty() { return Err(ComponentCreationError::DefinitionNotComponent); } - // - check number of arguments - let expr_data = self.types.get_procedure_expression_data(&definition_id, 0); - if expr_data.arg_types.len() != arguments.values.len() { + // - check number of arguments by retrieving the one instantiated + // monomorph + let concrete_type = ConcreteType{ parts: vec![ConcreteTypePart::Component(definition_id, 0)] }; + let mono_index = self.types.get_procedure_monomorph_index(&definition_id, &concrete_type.parts).unwrap(); + let mono_type = self.types.get_procedure_monomorph(mono_index); + if mono_type.arg_types.len() != arguments.values.len() { return Err(ComponentCreationError::InvalidNumArguments); } // - for each argument try to make sure the types match for arg_idx in 0..arguments.values.len() { - let expected_type = &expr_data.arg_types[arg_idx]; + let expected_type = &mono_type.arg_types[arg_idx]; let provided_value = &arguments.values[arg_idx]; if !self.verify_same_type(expected_type, 0, &arguments, provided_value) { return Err(ComponentCreationError::InvalidArgumentType(arg_idx)); diff --git a/src/protocol/parser/pass_typing.rs b/src/protocol/parser/pass_typing.rs index 4a75cc5a6249c82f3df41956454ab21e395e7b0f..83ba7e66895ce36e6bd3ea9a6b90940de032a84a 100644 --- a/src/protocol/parser/pass_typing.rs +++ b/src/protocol/parser/pass_typing.rs @@ -980,10 +980,8 @@ impl PassTyping { let proc_base = ctx.types.get_base_definition(&element.definition_id).unwrap(); if proc_base.is_polymorph { - let proc_monos = proc_base.definition.procedure_monomorphs(); - let proc_mono = &(*proc_monos)[element.reserved_monomorph_idx as usize]; - - for poly_arg in proc_mono.concrete_type.embedded_iter(0) { + let monomorph = ctx.types.get_monomorph(element.reserved_monomorph_idx); + for poly_arg in monomorph.concrete_type.embedded_iter(0) { self.poly_vars.push(ConcreteType{ parts: Vec::from(poly_arg) }); } } @@ -1526,7 +1524,7 @@ impl PassTyping { ctx, extra_data.expr_id, &extra_data.poly_vars, first_concrete_part )?; - match ctx.types.get_procedure_monomorph_index(&definition_id, &concrete_type) { + match ctx.types.get_procedure_monomorph_index(&definition_id, &concrete_type.parts) { Some(reserved_idx) => { // Already typechecked, or already put into the resolve queue infer_expr.field_or_monomorph_idx = reserved_idx; @@ -1575,18 +1573,18 @@ impl PassTyping { // Every expression checked, and new monomorphs are queued. Transfer the // expression information to the type table. - let (definition_id, procedure_arguments) = match &self.definition_type { + let procedure_arguments = match &self.definition_type { DefinitionType::Component(id) => { let definition = &ctx.heap[*id]; - (id.upcast(), &definition.parameters) + &definition.parameters }, DefinitionType::Function(id) => { let definition = &ctx.heap[*id]; - (id.upcast(), &definition.parameters) + &definition.parameters }, }; - let target = ctx.types.get_procedure_expression_data_mut(&definition_id, self.reserved_idx); + let target = ctx.types.get_procedure_monomorph_mut(self.reserved_idx); debug_assert!(target.arg_types.is_empty()); // makes sure we never queue a procedure's type inferencing twice debug_assert!(target.expr_data.is_empty()); diff --git a/src/protocol/parser/type_table.rs b/src/protocol/parser/type_table.rs index aededc074c1301700a3785eb48fefd5a8c241b92..f38043fe0a54cea496248536c5dddd5c14b647b5 100644 --- a/src/protocol/parser/type_table.rs +++ b/src/protocol/parser/type_table.rs @@ -97,137 +97,6 @@ pub struct DefinedType { pub(crate) is_polymorph: bool, } -impl DefinedType { - /// Returns the number of monomorphs that are instantiated. Remember that - /// during the type loop detection, and the memory layout phase we will - /// pre-allocate monomorphs which are not yet fully laid out in memory. - pub(crate) fn num_monomorphs(&self) -> usize { - use DefinedTypeVariant as DTV; - match &self.definition { - DTV::Enum(def) => def.monomorphs.len(), - DTV::Union(def) => def.monomorphs.len(), - DTV::Struct(def) => def.monomorphs.len(), - DTV::Function(_) | DTV::Component(_) => unreachable!(), - } - } - - /// 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). If the type is not polymorphic and its memory has been - /// layed out, then this will always return `Some(0)`. - pub(crate) fn get_monomorph_index(&self, parts: &[ConcreteTypePart]) -> 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: &[ConcreteTypePart], type_b: &[ConcreteTypePart], check_if_poly_var_is_used: bool| -> bool { - let mut a_iter = ConcreteTypeIter::new(type_a, 0).enumerate(); - let mut b_iter = ConcreteTypeIter::new(type_b, 0); - - 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), @@ -288,26 +157,6 @@ impl DefinedTypeVariant { _ => unreachable!("Cannot convert {} to union variant", self.type_class()) } } - - pub(crate) fn procedure_monomorphs(&self) -> &Vec { - 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 { - 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 { @@ -322,7 +171,6 @@ pub struct PolymorphicVariable { /// variants to be equal to one another. pub struct EnumType { pub variants: Vec, - pub monomorphs: Vec, pub minimum_tag_value: i64, pub maximum_tag_value: i64, pub tag_type: ConcreteType, @@ -348,7 +196,6 @@ 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 tag_type: ConcreteType, pub tag_size: usize, } @@ -363,7 +210,6 @@ pub struct UnionVariant { /// type) type. pub struct StructType { pub fields: Vec, - pub monomorphs: Vec, } pub struct StructField { @@ -376,13 +222,11 @@ pub struct StructField { pub struct FunctionType { pub return_types: Vec, pub arguments: Vec, - pub monomorphs: Vec, } pub struct ComponentType { pub variant: ComponentVariant, pub arguments: Vec, - pub monomorphs: Vec } pub struct FunctionArgument { @@ -407,30 +251,84 @@ pub struct MonomorphExpression { // 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), +/// Generic monomorph has a specific concrete type, a size and an alignment. +/// Extra data is in the `MonomorphVariant` per kind of type. +pub(crate) struct TypeMonomorph { + pub concrete_type: ConcreteType, + pub size: usize, + pub alignment: usize, + pub variant: MonomorphVariant, +} + +pub(crate) enum MonomorphVariant { + Enum, // no extra data 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, +impl MonomorphVariant { + fn as_struct(&self) -> &StructMonomorph { + match self { + MonomorphVariant::Struct(v) => v, + _ => unreachable!(), + } + } + + fn as_struct_mut(&mut self) -> &mut StructMonomorph { + match self { + MonomorphVariant::Struct(v) => v, + _ => unreachable!(), + } + } + + pub(crate) fn as_union(&self) -> &UnionMonomorph { + match self { + MonomorphVariant::Union(v) => v, + _ => unreachable!(), + } + } + + fn as_union_mut(&mut self) -> &mut UnionMonomorph { + match self { + MonomorphVariant::Union(v) => v, + _ => unreachable!(), + } + } + + fn as_tuple(&self) -> &TupleMonomorph { + match self { + MonomorphVariant::Tuple(v) => v, + _ => unreachable!(), + } + } + + fn as_tuple_mut(&mut self) -> &mut TupleMonomorph { + match self { + MonomorphVariant::Tuple(v) => v, + _ => unreachable!(), + } + } + + fn as_procedure(&self) -> &ProcedureMonomorph { + match self { + MonomorphVariant::Procedure(v) => v, + _ => unreachable!(), + } + } + + fn as_procedure_mut(&mut self) -> &mut ProcedureMonomorph { + match self { + MonomorphVariant::Procedure(v) => v, + _ => unreachable!(), + } + } } /// Struct monomorph pub struct StructMonomorph { - pub concrete_type: ConcreteType, pub fields: Vec, - pub size: usize, - pub alignment: usize, } pub struct StructMonomorphField { @@ -442,11 +340,10 @@ pub struct StructMonomorphField { /// Union monomorph pub struct UnionMonomorph { - 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, - pub stack_alignment: usize, + // note that the stack size is in the `TypeMonomorph` struct. This size and + // alignment will include the size of the union tag. + // // 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. @@ -476,7 +373,6 @@ pub struct UnionMonomorphEmbedded { /// 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, pub expr_data: Vec, } @@ -485,9 +381,6 @@ pub struct ProcedureMonomorph { /// 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 } @@ -498,6 +391,171 @@ pub struct TupleMonomorphMember { pub offset: usize, } +/// Key used to perform lookups in the monomorph table. It computes a hash of +/// the type while not taking the unused polymorphic variables of the base type +/// into account (e.g. `struct Foo{ A field }`, here `B` is an unused +/// polymorphic variable). +struct MonomorphKey { + parts: Vec, + in_use: Vec, +} + +use std::hash::*; + +impl Hash for MonomorphKey { + fn hash(&self, state: &mut H) { + // if `in_use` is empty, then we may assume the type is not polymorphic + // (or all types are in use) + if self.in_use.is_empty() { + self.parts.hash(state); + } else { + // type is polymorphic + self.parts[0].hash(state); + + // note: hash is computed in a unique way, because practically + // speaking `in_use` is fixed per base type. So we cannot have the + // same base type (hence: a type with the same DefinitionId) with + // different different polymorphic variables in use. + let mut in_use_index = 0; + for section in ConcreteTypeIter::new(self.parts.as_slice(), 0) { + if self.in_use[in_use_index] { + section.hash(state); + } + in_use_index += 1; + } + } + } +} + +impl PartialEq for MonomorphKey { + fn eq(&self, other: &Self) -> bool { + if self.in_use.is_empty() { + return self.parts == other.parts; + } else { + // Outer type does not match + if self.parts[0] != other.parts[0] { + return false; + } + + debug_assert_eq!(self.parts[0].num_embedded() as usize, self.in_use.len()); + let mut iter_self = ConcreteTypeIter::new(self.parts.as_slice(), 0); + let mut iter_other = ConcreteTypeIter::new(other.parts.as_slice(), 0); + let mut index = 0; + while let Some(section_self) = iter_self.next() { + let section_other = iter_other.next().unwrap(); + let in_use = self.in_use[index]; + index += 1; + + if !in_use { + continue; + } + + if section_self != section_other { + return false; + } + } + + return true; + } + } +} + +impl Eq for MonomorphKey {} + +use std::cell::UnsafeCell; + +/// Lookup table for monomorphs. Wrapped in a special struct because we don't +/// want to allocate for each lookup (what we really want is a HashMap that +/// exposes it CompareFn and HashFn, but whatevs). +pub(crate) struct MonomorphTable { + lookup: HashMap, // indexes into `monomorphs` + pub(crate) monomorphs: Vec, + // We use an UnsafeCell because this is only used internally per call to + // `get_monomorph_index` calls. This is safe because `&TypeMonomorph`s + // retrieved for this class remain valid when the key is mutated and the + // type table is not multithreaded. + // + // I added this because we don't want to allocate for each lookup, hence we + // need a reusable `key` internal to this class. This in turn makes + // `get_monomorph_index` a mutable call. Now the code that calls this + // function (even though we're not mutating the table!) needs a lot of extra + // boilerplate. I opted for the `UnsafeCell` instead of the boilerplate. + key: UnsafeCell, +} + +impl MonomorphTable { + fn new() -> Self { + return Self { + lookup: HashMap::with_capacity(256), + monomorphs: Vec::with_capacity(256), + key: UnsafeCell::new(MonomorphKey{ + parts: Vec::with_capacity(32), + in_use: Vec::with_capacity(32), + }) + } + } + + fn insert_with_zero_size_and_alignment(&mut self, concrete_type: ConcreteType, in_use: &[PolymorphicVariable], variant: MonomorphVariant) -> i32 { + let key = MonomorphKey{ + parts: Vec::from(concrete_type.parts.as_slice()), + in_use: in_use.iter().map(|v| v.is_in_use).collect(), + }; + let index = self.monomorphs.len(); + let _result = self.lookup.insert(key, index as i32); + debug_assert!(_result.is_none()); // did not exist yet + self.monomorphs.push(TypeMonomorph{ + concrete_type, + size: 0, + alignment: 0, + variant, + }); + + return index as i32; + } + + fn get_monomorph_index(&self, parts: &[ConcreteTypePart], in_use: &[PolymorphicVariable]) -> Option { + // Note: the entire goal of this internal `MonomorphKey` is to prevent + // allocation. So: + let key = unsafe { + let key = &mut *self.key.get(); + key.parts.clear(); + key.parts.extend_from_slice(parts); + key.in_use.clear(); + key.in_use.extend(in_use.iter().map(|v| v.is_in_use)); + + &*key + }; + + match self.lookup.get(key) { + Some(index) => return Some(*index), + None => return None, + } + } + + #[inline] + fn get(&self, index: i32) -> &TypeMonomorph { + debug_assert!(index >= 0); + return &self.monomorphs[index as usize]; + } + + #[inline] + fn get_mut(&mut self, index: i32) -> &mut TypeMonomorph { + debug_assert!(index >= 0); + return &mut self.monomorphs[index as usize]; + } + + fn get_monomorph_size_alignment(&self, index: i32) -> Option<(usize, usize)> { + let monomorph = self.get(index); + if monomorph.size == 0 && monomorph.alignment == 0 { + // If both are zero, then we wish to mean: we haven't actually + // computed the size and alignment yet. So: + return None; + } else { + return Some((monomorph.size, monomorph.alignment)); + } + } +} + //------------------------------------------------------------------------------ // Type table //------------------------------------------------------------------------------ @@ -505,16 +563,16 @@ pub struct TupleMonomorphMember { // 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 + definition_id: DefinitionId, // TODO: Check if it can be removed? + monomorph_idx: i32, + next_member: u32, + next_embedded: u32, // for unions, the index into the variant's embedded types } #[derive(Clone)] struct MemoryBreadcrumb { definition_id: DefinitionId, - monomorph_idx: usize, + monomorph_idx: i32, next_member: usize, next_embedded: usize, first_size_alignment_idx: usize, @@ -535,7 +593,7 @@ enum MemoryLayoutResult { // TODO: @Optimize, initial memory-unoptimized implementation struct TypeLoopEntry { definition_id: DefinitionId, - monomorph_idx: usize, + monomorph_idx: i32, is_union: bool, } @@ -544,9 +602,10 @@ struct TypeLoop { } pub struct TypeTable { - /// Lookup from AST DefinitionId to a defined type. Considering possible - /// polymorphs is done inside the `DefinedType` struct. - lookup: HashMap, + /// Lookup from AST DefinitionId to a defined type. Also lookups for + /// concrete type to monomorphs + pub(crate) type_lookup: HashMap, + pub(crate) mono_lookup: MonomorphTable, /// 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, @@ -563,7 +622,8 @@ impl TypeTable { /// Construct a new type table without any resolved types. pub(crate) fn new() -> Self { Self{ - lookup: HashMap::new(), + type_lookup: HashMap::with_capacity(128), + mono_lookup: MonomorphTable::new(), type_loop_breadcrumbs: Vec::with_capacity(32), type_loops: Vec::with_capacity(8), encountered_types: Vec::with_capacity(32), @@ -581,7 +641,7 @@ impl TypeTable { 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()); + debug_assert!(self.type_lookup.is_empty()); if cfg!(debug_assertions) { for (index, module) in modules.iter().enumerate() { @@ -591,7 +651,7 @@ impl TypeTable { // Use context to guess hashmap size of the base types let reserve_size = ctx.heap.definitions.len(); - self.lookup.reserve(reserve_size); + self.type_lookup.reserve(reserve_size); // Resolve all base types for definition_idx in 0..ctx.heap.definitions.len() { @@ -607,7 +667,7 @@ impl TypeTable { } } - debug_assert_eq!(self.lookup.len(), reserve_size, "mismatch in reserved size of type table"); // NOTE: Temp fix for builtin functions + debug_assert_eq!(self.type_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; } @@ -617,13 +677,17 @@ impl TypeTable { // 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(); + let poly_type = self.type_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 { + if !poly_type.definition.type_class().is_data_type() || !poly_type.poly_vars.is_empty() { + continue; + } + + // If here then the type is a data type without polymorphic + // variables, but we might have instantiated it already, so: + let concrete_parts = [ConcreteTypePart::Instance(definition_id, 0)]; + let mono_index = self.mono_lookup.get_monomorph_index(&concrete_parts, &[]); + if mono_index.is_none() { self.detect_and_resolve_type_loops_for( modules, ctx.heap, ConcreteType{ @@ -641,34 +705,38 @@ impl TypeTable { /// 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 + #[inline] pub(crate) fn get_base_definition(&self, definition_id: &DefinitionId) -> Option<&DefinedType> { - self.lookup.get(&definition_id) + self.type_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 { - 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); + #[inline] + pub(crate) fn get_procedure_monomorph_index(&self, definition_id: &DefinitionId, type_parts: &[ConcreteTypePart]) -> Option { + let base_type = self.type_lookup.get(definition_id).unwrap(); + return self.mono_lookup.get_monomorph_index(type_parts, &base_type.poly_vars); + } + + #[inline] + pub(crate) fn get_monomorph(&self, monomorph_index: i32) -> &TypeMonomorph { + return self.mono_lookup.get(monomorph_index); } /// 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]; + #[inline] + pub(crate) fn get_procedure_monomorph_mut(&mut self, monomorph_index: i32) -> &mut ProcedureMonomorph { + debug_assert!(monomorph_index >= 0); + let monomorph = self.mono_lookup.get_mut(monomorph_index); + return monomorph.variant.as_procedure_mut(); } - 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]; + #[inline] + pub(crate) fn get_procedure_monomorph(&self, monomorph_index: i32) -> &ProcedureMonomorph { + debug_assert!(monomorph_index >= 0); + let monomorph = self.mono_lookup.get(monomorph_index); + return monomorph.variant.as_procedure(); } /// Reserves space for a monomorph of a polymorphic procedure. The index @@ -677,19 +745,15 @@ impl TypeTable { /// 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; + let base_type = self.type_lookup.get_mut(definition_id).unwrap(); + let mono_index = self.mono_lookup.insert_with_zero_size_and_alignment( + concrete_type, &base_type.poly_vars, MonomorphVariant::Procedure(ProcedureMonomorph{ + arg_types: Vec::new(), + expr_data: Vec::new(), + }) + ); + + return mono_index; } /// Adds a datatype polymorph to the type table. Will not add the @@ -702,9 +766,9 @@ impl TypeTable { debug_assert_eq!(definition_id, get_concrete_type_definition(&concrete_type)); // Check if the monomorph already exists - let poly_type = self.lookup.get_mut(&definition_id).unwrap(); - if let Some(idx) = poly_type.get_monomorph_index(&concrete_type.parts) { - return Ok(idx as i32); + let poly_type = self.type_lookup.get_mut(&definition_id).unwrap(); + if let Some(idx) = self.mono_lookup.get_monomorph_index(&concrete_type.parts, &poly_type.poly_vars) { + return Ok(idx); } // Doesn't exist, so instantiate a monomorph and determine its memory @@ -723,7 +787,7 @@ impl TypeTable { /// 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> { - debug_assert!(!self.lookup.contains_key(&definition_id), "base enum already built"); + debug_assert!(!self.type_lookup.contains_key(&definition_id), "base enum already built"); let definition = ctx.heap[definition_id].as_enum(); let root_id = definition.defined_in; @@ -775,12 +839,11 @@ impl TypeTable { 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 { + self.type_lookup.insert(definition_id, DefinedType { ast_root: root_id, ast_definition: definition_id, definition: DefinedTypeVariant::Enum(EnumType{ variants, - monomorphs: Vec::new(), minimum_tag_value: min_enum_value, maximum_tag_value: max_enum_value, tag_type, @@ -796,7 +859,7 @@ impl TypeTable { /// 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"); + debug_assert!(!self.type_lookup.contains_key(&definition_id), "base union already built"); let definition = ctx.heap[definition_id].as_union(); let root_id = definition.defined_in; @@ -841,15 +904,10 @@ impl TypeTable { let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use); - self.lookup.insert(definition_id, DefinedType{ + self.type_lookup.insert(definition_id, DefinedType{ ast_root: root_id, ast_definition: definition_id, - definition: DefinedTypeVariant::Union(UnionType{ - variants, - monomorphs: Vec::new(), - tag_type, - tag_size, - }), + definition: DefinedTypeVariant::Union(UnionType{ variants, tag_type, tag_size }), poly_vars, is_polymorph }); @@ -859,7 +917,7 @@ impl TypeTable { /// 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"); + debug_assert!(!self.type_lookup.contains_key(&definition_id), "base struct already built"); let definition = ctx.heap[definition_id].as_struct(); let root_id = definition.defined_in; @@ -891,13 +949,10 @@ impl TypeTable { let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use); - self.lookup.insert(definition_id, DefinedType{ + self.type_lookup.insert(definition_id, DefinedType{ ast_root: root_id, ast_definition: definition_id, - definition: DefinedTypeVariant::Struct(StructType{ - fields, - monomorphs: Vec::new(), - }), + definition: DefinedTypeVariant::Struct(StructType{ fields }), poly_vars, is_polymorph }); @@ -907,7 +962,7 @@ impl TypeTable { /// 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"); + debug_assert!(!self.type_lookup.contains_key(&definition_id), "base function already built"); let definition = ctx.heap[definition_id].as_function(); let root_id = definition.defined_in; @@ -949,14 +1004,10 @@ impl TypeTable { let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use); - self.lookup.insert(definition_id, DefinedType{ + self.type_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(), - }), + definition: DefinedTypeVariant::Function(FunctionType{ return_types: definition.return_types.clone(), arguments }), poly_vars, is_polymorph }); @@ -966,7 +1017,7 @@ impl TypeTable { /// 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"); + debug_assert!(!self.type_lookup.contains_key(&definition_id), "base component already built"); let definition = &ctx.heap[definition_id].as_component(); let root_id = definition.defined_in; @@ -999,14 +1050,10 @@ impl TypeTable { let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use); - self.lookup.insert(definition_id, DefinedType{ + self.type_lookup.insert(definition_id, DefinedType{ ast_root: root_id, ast_definition: definition_id, - definition: DefinedTypeVariant::Component(ComponentType{ - variant: definition.variant, - arguments, - monomorphs: Vec::new() - }), + definition: DefinedTypeVariant::Component(ComponentType{ variant: definition.variant, arguments }), poly_vars, is_polymorph }); @@ -1135,6 +1182,27 @@ impl TypeTable { /// resolvable. If so then the appropriate union variants will be marked as /// "living on heap". If not then a `ParseError` will be returned fn detect_and_resolve_type_loops_for(&mut self, modules: &[Module], heap: &Heap, concrete_type: ConcreteType) -> Result<(), ParseError> { + // Programmer notes: what happens here is the we call + // `check_member_for_type_loops` for a particular type's member, and + // then take action using the return value: + // 1. It might already be resolved: in this case it implies we don't + // have type loops, or they have been resolved. + // 2. A new type is encountered. If so then it is added to the type loop + // breadcrumbs. + // 3. A type loop is detected (implying the type is already resolved, or + // already exists in the type loop breadcrumbs). + // + // Using the breadcrumbs we incrementally check every member type of a + // particular considered type (e.g. a struct field, tuple member), and + // do the same as above. Note that when a breadcrumb is added we reserve + // space in the monomorph storage, initialized to zero-values (i.e. + // wrong values). The breadcrumbs keep track of how far and along we are + // with resolving the member types. + // + // At the end we may have some type loops. If they're unresolvable then + // we throw an error). If there are no type loops or they are all + // resolvable then we end up with a list of `encountered_types`. These + // are then used by `lay_out_memory_for_encountered_types`. use DefinedTypeVariant as DTV; debug_assert!(self.type_loop_breadcrumbs.is_empty()); @@ -1155,62 +1223,83 @@ impl TypeTable { let breadcrumb_idx = self.type_loop_breadcrumbs.len() - 1; let mut breadcrumb = self.type_loop_breadcrumbs[breadcrumb_idx].clone(); - let poly_type = self.lookup.get(&breadcrumb.definition_id).unwrap(); + // TODO: Also don't need DefinitionId here. So then only need mono_index, so then just + // do a switch on the monomorph, not on the base type. + let resolve_result = if breadcrumb.definition_id.is_invalid() { + // We're dealing with a tuple + let monomorph = self.mono_lookup.get(breadcrumb.monomorph_idx).variant.as_tuple(); + let num_members = monomorph.members.len() as u32; + let mut tuple_result = TypeLoopResult::TypeExists; - let resolve_result = match &poly_type.definition { - DTV::Enum(_) => { - TypeLoopResult::TypeExists - }, - DTV::Union(definition) => { - let monomorph = &definition.monomorphs[breadcrumb.monomorph_idx]; - let num_variants = monomorph.variants.len(); + while breadcrumb.next_member < num_members { + let tuple_member = &monomorph.members[breadcrumb.next_member as usize]; + tuple_result = self.check_member_for_type_loops(&tuple_member.concrete_type); + + if tuple_result != TypeLoopResult::TypeExists { + break; + } + + breadcrumb.next_member += 1; + } - let mut union_result = TypeLoopResult::TypeExists; + tuple_result + } else { + let poly_type = self.type_lookup.get(&breadcrumb.definition_id).unwrap(); + match &poly_type.definition { + DTV::Enum(_) => { + TypeLoopResult::TypeExists + }, + DTV::Union(definition) => { + let monomorph = self.mono_lookup.get(breadcrumb.monomorph_idx).variant.as_union(); + let num_variants = monomorph.variants.len() as u32; - 'member_loop: while breadcrumb.next_member < num_variants { - let mono_variant = &monomorph.variants[breadcrumb.next_member]; - let num_embedded = mono_variant.embedded.len(); + let mut union_result = TypeLoopResult::TypeExists; - while breadcrumb.next_embedded < num_embedded { - let mono_embedded = &mono_variant.embedded[breadcrumb.next_embedded]; - union_result = self.check_member_for_type_loops(&mono_embedded.concrete_type); + 'member_loop: while breadcrumb.next_member < num_variants { + let mono_variant = &monomorph.variants[breadcrumb.next_member as usize]; + let num_embedded = mono_variant.embedded.len() as u32; + + while breadcrumb.next_embedded < num_embedded { + let mono_embedded = &mono_variant.embedded[breadcrumb.next_embedded as usize]; + union_result = self.check_member_for_type_loops(&mono_embedded.concrete_type); - if union_result != TypeLoopResult::TypeExists { - // In type loop or new breadcrumb pushed, so - // break out of the resolving loop - break 'member_loop; + if union_result != TypeLoopResult::TypeExists { + // In type loop or new breadcrumb pushed, so + // break out of the resolving loop + break 'member_loop; + } + + breadcrumb.next_embedded += 1; } - breadcrumb.next_embedded += 1; + breadcrumb.next_embedded = 0; + breadcrumb.next_member += 1 } - breadcrumb.next_embedded = 0; - breadcrumb.next_member += 1 - } + union_result + }, + DTV::Struct(definition) => { + let monomorph = self.mono_lookup.get(breadcrumb.monomorph_idx).variant.as_struct(); + let num_fields = monomorph.fields.len() as u32; + + let mut struct_result = TypeLoopResult::TypeExists; + while breadcrumb.next_member < num_fields { + let mono_field = &monomorph.fields[breadcrumb.next_member as usize]; + struct_result = self.check_member_for_type_loops(&mono_field.concrete_type); + + if struct_result != TypeLoopResult::TypeExists { + // Type loop or breadcrumb pushed, so break out of + // the resolving loop + break; + } - union_result - }, - DTV::Struct(definition) => { - let monomorph = &definition.monomorphs[breadcrumb.monomorph_idx]; - let num_fields = monomorph.fields.len(); - - let mut struct_result = TypeLoopResult::TypeExists; - while breadcrumb.next_member < num_fields { - let mono_field = &monomorph.fields[breadcrumb.next_member]; - struct_result = self.check_member_for_type_loops(&mono_field.concrete_type); - - if struct_result != TypeLoopResult::TypeExists { - // Type loop or breadcrumb pushed, so break out of - // the resolving loop - break; + breadcrumb.next_member += 1; } - breadcrumb.next_member += 1; - } - - struct_result - }, - DTV::Function(_) | DTV::Component(_) => unreachable!(), + struct_result + }, + DTV::Function(_) | DTV::Component(_) => unreachable!(), + } }; // Handle the result of attempting to resolve the current breadcrumb @@ -1237,14 +1326,15 @@ 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(); + let entry = self.type_lookup.get_mut(&breadcrumb.definition_id).unwrap(); + // TODO: Match on monomorph directly here 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]; + let monomorph = self.mono_lookup.get_mut(breadcrumb.monomorph_idx).variant.as_union_mut(); + let variant = &mut monomorph.variants[breadcrumb.next_member as usize]; variant.lives_on_heap = true; breadcrumb.next_embedded += 1; is_union = true; @@ -1284,16 +1374,18 @@ impl TypeTable { // 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 + modules: &'a [Module], heap: &Heap, mono_lookup: &MonomorphTable, + defined_type: &DefinedType, monomorph_idx: i32, 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. + // TODO: Also remove match on defined_type, replace with mono lookup 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::Union(definition) => &mono_lookup.get(monomorph_idx).concrete_type, + DTV::Struct(definition) => &mono_lookup.get(monomorph_idx).concrete_type, DTV::Enum(_) | DTV::Function(_) | DTV::Component(_) => unreachable!(), // impossible to have an enum/procedure in a type loop }; @@ -1324,19 +1416,26 @@ impl TypeTable { 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_type = table.type_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 + modules, heap, &table.mono_lookup, first_type, first_entry.monomorph_idx, 0 ); let mut parse_error = ParseError::new_error_at_span(first_module, first_span, first_message); + let mut error_counter = 1; 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(); + if entry.definition_id.is_invalid() { + // Don't display the tuples + continue; + } + + let entry_type = table.type_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 + modules, heap, &table.mono_lookup, entry_type, entry.monomorph_idx, error_counter ); parse_error = parse_error.with_info_at_span(module, span, message); + error_counter += 1; } parse_error @@ -1348,13 +1447,12 @@ impl TypeTable { 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]; - + let monomorph = &self.mono_lookup.get(entry.monomorph_idx).variant.as_union(); 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; + break; } } } @@ -1382,26 +1480,32 @@ impl TypeTable { 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. + // Depending on the type, lookup if the type has already been visited + // (i.e. either already has its memory layed out, or is part of a type + // loop because we've already visited the type) debug_assert!(!definition_type.parts.is_empty()); - let definition_id = match &definition_type.parts[0] { + let (definition_id, monomorph_index) = match &definition_type.parts[0] { + CTP::Tuple(_) => { + let monomorph_index = self.mono_lookup.get_monomorph_index(&definition_type.parts, &[]); + + (DefinitionId::new_invalid(), monomorph_index) + }, CTP::Instance(definition_id, _) | CTP::Function(definition_id, _) | CTP::Component(definition_id, _) => { - *definition_id + let base_type = self.type_lookup.get(definition_id).unwrap(); + let monomorph_index = self.mono_lookup.get_monomorph_index(&definition_type.parts, &base_type.poly_vars); + + (*definition_id, monomorph_index) }, _ => { 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 + if let Some(monomorph_index) = monomorph_index { for (breadcrumb_idx, breadcrumb) in self.type_loop_breadcrumbs.iter().enumerate() { - if breadcrumb.definition_id == definition_id && breadcrumb.monomorph_idx == mono_idx { + if breadcrumb.monomorph_idx == monomorph_index { return TypeLoopResult::TypeLoop(breadcrumb_idx); } } @@ -1418,89 +1522,114 @@ impl TypeTable { /// call. fn handle_new_breadcrumb_for_type_loops(&mut self, definition_id: DefinitionId, definition_type: ConcreteType) { use DefinedTypeVariant as DTV; + use ConcreteTypePart as CTP; - 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, - }); - 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, + let monomorph_index = match &definition_type.parts[0] { + CTP::Tuple(num_embedded) => { + debug_assert!(definition_id.is_invalid()); // because tuples do not have an associated `DefinitionId` + let mut members = Vec::with_capacity(*num_embedded as usize); + for section in ConcreteTypeIter::new(&definition_type.parts, 0) { + members.push(TupleMonomorphMember{ + concrete_type: ConcreteType{ parts: Vec::from(section) }, size: 0, alignment: 0, offset: 0 - }) + }); } + let monomorph_index = self.mono_lookup.insert_with_zero_size_and_alignment( + definition_type, &[], + MonomorphVariant::Tuple(TupleMonomorph{ + members, + }) + ); - let mono_idx = definition.monomorphs.len(); - definition.monomorphs.push(StructMonomorph{ - concrete_type: definition_type, - fields: mono_fields, - size: 0, - alignment: 0 - }); - - mono_idx + monomorph_index }, - DTV::Function(_) | DTV::Component(_) => { - unreachable!("pushing type resolving breadcrumb for procedure type") + CTP::Instance(_check_definition_id, _) => { + debug_assert_eq!(definition_id, *_check_definition_id); // because this is how `definition_id` was determined + let base_type = self.type_lookup.get_mut(&definition_id).unwrap(); + let monomorph_index = match &mut base_type.definition { + DTV::Enum(definition) => { + // TODO: Is this correct? + let mono_index = self.mono_lookup.insert_with_zero_size_and_alignment( + definition_type, &base_type.poly_vars, MonomorphVariant::Enum + ); + + mono_index + }, + 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_index = self.mono_lookup.insert_with_zero_size_and_alignment( + definition_type, &base_type.poly_vars, + MonomorphVariant::Union(UnionMonomorph{ + variants: mono_variants, + heap_size: 0, + heap_alignment: 0 + }) + ); + + is_union = true; + mono_index + }, + 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_index = self.mono_lookup.insert_with_zero_size_and_alignment( + definition_type, &base_type.poly_vars, + MonomorphVariant::Struct(StructMonomorph{ fields: mono_fields }) + ); + + mono_index + }, + DTV::Function(_) | DTV::Component(_) => { + unreachable!("pushing type resolving breadcrumb for procedure type") + }, + }; + + monomorph_index }, + _ => unreachable!(), }; self.encountered_types.push(TypeLoopEntry{ definition_id, - monomorph_idx, + monomorph_idx: monomorph_index, is_union, }); self.type_loop_breadcrumbs.push(TypeLoopBreadcrumb{ definition_id, - monomorph_idx, + monomorph_idx: monomorph_index, next_member: 0, next_embedded: 0, }); @@ -1574,7 +1703,18 @@ impl TypeTable { // Determining memory layout for types //-------------------------------------------------------------------------- + /// Should be called after type loops are detected (and resolved + /// successfully). As a result of this call we expect the + /// `encountered_types` array to be filled. We'll calculate size/alignment/ + /// offset values for those types in this routine. fn lay_out_memory_for_encountered_types(&mut self, arch: &TargetArch) { + // Programmers note: this works like a little stack machine. We have + // memory layout breadcrumbs which, like the type loop breadcrumbs, keep + // track of the currently considered member type. This breadcrumb also + // stores an index into the `size_alignment_stack`, which will be used + // to store intermediate size/alignment pairs until all members are + // resolved. Note that this `size_alignment_stack` is NOT an + // optimization, we're working around borrowing rules here. use DefinedTypeVariant as DTV; // Just finished type loop detection, so we're left with the encountered @@ -1600,147 +1740,198 @@ impl TypeTable { 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(); - while breadcrumb.next_embedded < num_embedded { - let mono_embedded = &mono_variant.embedded[breadcrumb.next_embedded]; - match self.get_memory_layout_or_breadcrumb(arch, &mono_embedded.concrete_type.parts) { - MemoryLayoutResult::TypeExists(size, alignment) => { - self.size_alignment_stack.push((size, alignment)); - }, - MemoryLayoutResult::PushBreadcrumb(new_breadcrumb) => { - self.memory_layout_breadcrumbs[cur_breadcrumb_idx] = breadcrumb; - self.memory_layout_breadcrumbs.push(new_breadcrumb); - continue 'breadcrumb_loop; + // TODO: Same as above, replace lookup of base definition, should not + // be needed. + if breadcrumb.definition_id.is_invalid() { + // Handle tuple + let mono_tuple = self.mono_lookup.get(breadcrumb.monomorph_idx).variant.as_tuple(); + let num_members = mono_tuple.members.len(); + while breadcrumb.next_member < num_members { + let mono_member = &mono_tuple.members[breadcrumb.next_member]; + match self.get_memory_layout_or_breadcrumb(arch, &mono_member.concrete_type.parts) { + MemoryLayoutResult::TypeExists(size, alignment) => { + self.size_alignment_stack.push((size, alignment)); + }, + MemoryLayoutResult::PushBreadcrumb(new_breadcrumb) => { + self.memory_layout_breadcrumbs[cur_breadcrumb_idx] = breadcrumb; + self.memory_layout_breadcrumbs.push(new_breadcrumb); + continue 'breadcrumb_loop; + }, + } + + breadcrumb.next_member += 1; + } + + // If here then we can compute the memory layout of the tuple. + let mut cur_offset = 0; + let mut max_alignment = 0; + + let mono_info = self.mono_lookup.get_mut(breadcrumb.monomorph_idx); + let mono_tuple = mono_info.variant.as_tuple_mut(); + let mut size_alignment_index = breadcrumb.first_size_alignment_idx; + for member_index in 0..num_members { + let (member_size, member_alignment) = self.size_alignment_stack[size_alignment_index]; + align_offset_to(&mut cur_offset, member_alignment); + size_alignment_index += 1; + + let member = &mut mono_tuple.members[member_index]; + member.size = member_size; + member.alignment = member_alignment; + member.offset = cur_offset; + + cur_offset += member_size; + max_alignment = max_alignment.max(member_alignment); + } + + mono_info.size = cur_offset; + mono_info.alignment = max_alignment; + self.size_alignment_stack.truncate(breadcrumb.first_size_alignment_idx); + } else { + let poly_type = self.type_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); + let mono_type = self.mono_lookup.get_mut(breadcrumb.monomorph_idx); + mono_type.size = definition.size; + mono_type.alignment = definition.alignment; + }, + DTV::Union(definition) => { + // Retrieve size/alignment of each embedded type. We do not + // compute the offsets or total type sizes yet. + let mono_type = self.mono_lookup.get(breadcrumb.monomorph_idx).variant.as_union(); + 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(); + while breadcrumb.next_embedded < num_embedded { + let mono_embedded = &mono_variant.embedded[breadcrumb.next_embedded]; + match self.get_memory_layout_or_breadcrumb(arch, &mono_embedded.concrete_type.parts) { + MemoryLayoutResult::TypeExists(size, alignment) => { + self.size_alignment_stack.push((size, alignment)); + }, + MemoryLayoutResult::PushBreadcrumb(new_breadcrumb) => { + self.memory_layout_breadcrumbs[cur_breadcrumb_idx] = breadcrumb; + self.memory_layout_breadcrumbs.push(new_breadcrumb); + continue 'breadcrumb_loop; + } } - } - breadcrumb.next_embedded += 1; + breadcrumb.next_embedded += 1; + } } + + breadcrumb.next_member += 1; + breadcrumb.next_embedded = 0; } - breadcrumb.next_member += 1; - breadcrumb.next_embedded = 0; - } + // If here then we can at least compute the stack size of + // the type, we'll have to come back at the very end to + // fill in the heap size/alignment/offset of each heap- + // allocated variant. + let mut max_size = definition.tag_size; + let mut max_alignment = definition.tag_size; + + let poly_type = self.type_lookup.get_mut(&breadcrumb.definition_id).unwrap(); + let definition = poly_type.definition.as_union_mut(); + let mono_info = self.mono_lookup.get_mut(breadcrumb.monomorph_idx); + let mono_type = mono_info.variant.as_union_mut(); + let mut size_alignment_idx = breadcrumb.first_size_alignment_idx; + + for variant in &mut mono_type.variants { + // We're doing stack computations, so always start with + // the tag size/alignment. + let mut variant_offset = definition.tag_size; + let mut variant_alignment = definition.tag_size; + + if variant.lives_on_heap { + // Variant lives on heap, so just a pointer + let (ptr_size, ptr_align) = arch.pointer_size_alignment; + align_offset_to(&mut variant_offset, ptr_align); + + variant_offset += ptr_size; + variant_alignment = variant_alignment.max(ptr_align); + } else { + // Variant lives on stack, so walk all embedded + // types. + for embedded in &mut variant.embedded { + let (size, alignment) = self.size_alignment_stack[size_alignment_idx]; + embedded.size = size; + embedded.alignment = alignment; + size_alignment_idx += 1; + + align_offset_to(&mut variant_offset, alignment); + embedded.offset = variant_offset; + + variant_offset += size; + variant_alignment = variant_alignment.max(alignment); + } + }; - // If here then we can at least compute the stack size of - // the type, we'll have to come back at the very end to - // fill in the heap size/alignment/offset of each heap- - // allocated variant. - let mut max_size = definition.tag_size; - let mut max_alignment = definition.tag_size; - - let poly_type = self.lookup.get_mut(&breadcrumb.definition_id).unwrap(); - let definition = poly_type.definition.as_union_mut(); - let mono_type = &mut definition.monomorphs[breadcrumb.monomorph_idx]; - let mut size_alignment_idx = breadcrumb.first_size_alignment_idx; - - for variant in &mut mono_type.variants { - // We're doing stack computations, so always start with - // the tag size/alignment. - let mut variant_offset = definition.tag_size; - let mut variant_alignment = definition.tag_size; - - if variant.lives_on_heap { - // Variant lives on heap, so just a pointer - let (ptr_size, ptr_align) = arch.pointer_size_alignment; - align_offset_to(&mut variant_offset, ptr_align); - - variant_offset += ptr_size; - variant_alignment = variant_alignment.max(ptr_align); - } else { - // Variant lives on stack, so walk all embedded - // types. - for embedded in &mut variant.embedded { - let (size, alignment) = self.size_alignment_stack[size_alignment_idx]; - embedded.size = size; - embedded.alignment = alignment; - size_alignment_idx += 1; - - align_offset_to(&mut variant_offset, alignment); - embedded.offset = variant_offset; - - variant_offset += size; - variant_alignment = variant_alignment.max(alignment); - } - }; + max_size = max_size.max(variant_offset); + max_alignment = max_alignment.max(variant_alignment); + } - max_size = max_size.max(variant_offset); - max_alignment = max_alignment.max(variant_alignment); - } + mono_info.size = max_size; + mono_info.alignment = max_alignment; + self.size_alignment_stack.truncate(breadcrumb.first_size_alignment_idx); + }, + DTV::Struct(definition) => { + // Retrieve size and alignment of each struct member. We'll + // compute the offsets once all of those are known + let mono_type = self.mono_lookup.get(breadcrumb.monomorph_idx).variant.as_struct(); + let num_fields = mono_type.fields.len(); + while breadcrumb.next_member < num_fields { + let mono_field = &mono_type.fields[breadcrumb.next_member]; + + match self.get_memory_layout_or_breadcrumb(arch, &mono_field.concrete_type.parts) { + MemoryLayoutResult::TypeExists(size, alignment) => { + self.size_alignment_stack.push((size, alignment)) + }, + MemoryLayoutResult::PushBreadcrumb(new_breadcrumb) => { + self.memory_layout_breadcrumbs[cur_breadcrumb_idx] = breadcrumb; + self.memory_layout_breadcrumbs.push(new_breadcrumb); + continue 'breadcrumb_loop; + }, + } - mono_type.stack_size = max_size; - mono_type.stack_alignment = max_alignment; - self.size_alignment_stack.truncate(breadcrumb.first_size_alignment_idx); - }, - DTV::Struct(definition) => { - // Retrieve size and alignment of each struct member. We'll - // compute the offsets once all of those are known - let mono_type = &definition.monomorphs[breadcrumb.monomorph_idx]; - let num_fields = mono_type.fields.len(); - while breadcrumb.next_member < num_fields { - let mono_field = &mono_type.fields[breadcrumb.next_member]; - - match self.get_memory_layout_or_breadcrumb(arch, &mono_field.concrete_type.parts) { - MemoryLayoutResult::TypeExists(size, alignment) => { - self.size_alignment_stack.push((size, alignment)) - }, - MemoryLayoutResult::PushBreadcrumb(new_breadcrumb) => { - self.memory_layout_breadcrumbs[cur_breadcrumb_idx] = breadcrumb; - self.memory_layout_breadcrumbs.push(new_breadcrumb); - continue 'breadcrumb_loop; - }, + breadcrumb.next_member += 1; } - breadcrumb.next_member += 1; - } + // Compute offsets and size of total type + let mut cur_offset = 0; + let mut max_alignment = 1; - // Compute offsets and size of total type - let mut cur_offset = 0; - let mut max_alignment = 1; + let mono_info = self.mono_lookup.get_mut(breadcrumb.monomorph_idx); + let mono_type = mono_info.variant.as_struct_mut(); + let mut size_alignment_idx = breadcrumb.first_size_alignment_idx; - let poly_type = self.lookup.get_mut(&breadcrumb.definition_id).unwrap(); - let definition = poly_type.definition.as_struct_mut(); - let mono_type = &mut definition.monomorphs[breadcrumb.monomorph_idx]; - let mut size_alignment_idx = breadcrumb.first_size_alignment_idx; + for field in &mut mono_type.fields { + let (size, alignment) = self.size_alignment_stack[size_alignment_idx]; + field.size = size; + field.alignment = alignment; + size_alignment_idx += 1; - for field in &mut mono_type.fields { - let (size, alignment) = self.size_alignment_stack[size_alignment_idx]; - field.size = size; - field.alignment = alignment; - size_alignment_idx += 1; + align_offset_to(&mut cur_offset, alignment); + field.offset = cur_offset; - align_offset_to(&mut cur_offset, alignment); - field.offset = cur_offset; + cur_offset += size; + max_alignment = max_alignment.max(alignment); + } - cur_offset += size; - max_alignment = max_alignment.max(alignment); + mono_info.size = cur_offset; + mono_info.alignment = max_alignment; + self.size_alignment_stack.truncate(breadcrumb.first_size_alignment_idx); + }, + DTV::Function(_) | DTV::Component(_) => { + unreachable!(); } - - mono_type.size = cur_offset; - mono_type.alignment = max_alignment; - self.size_alignment_stack.truncate(breadcrumb.first_size_alignment_idx); - }, - DTV::Function(_) | DTV::Component(_) => { - unreachable!(); } } @@ -1761,10 +1952,7 @@ impl TypeTable { // First pass, use buffer to store size/alignment to prevent // borrowing issues. - let poly_type = self.lookup.get(&entry.definition_id).unwrap(); - let definition = poly_type.definition.as_union(); - let mono_type = &definition.monomorphs[entry.monomorph_idx]; - + let mono_type = self.mono_lookup.get(entry.monomorph_idx).variant.as_union(); for variant in &mono_type.variants { if !variant.lives_on_heap { continue; @@ -1783,9 +1971,7 @@ impl TypeTable { } // Second pass, apply the size/alignment values in our buffer - let poly_type = self.lookup.get_mut(&entry.definition_id).unwrap(); - let definition = poly_type.definition.as_union_mut(); - let mono_type = &mut definition.monomorphs[entry.monomorph_idx]; + let mono_type = self.mono_lookup.get_mut(entry.monomorph_idx).variant.as_union_mut(); let mut max_size = 0; let mut max_alignment = 1; @@ -1827,11 +2013,13 @@ impl TypeTable { self.encountered_types.clear(); } + /// Attempts to compute size/alignment for the provided type. Note that this + /// is called *after* type loops have been succesfully resolved. Hence we + /// may assume that all monomorph entries exist, but we may not assume that + /// those entries already have their size/alignment computed. fn get_memory_layout_or_breadcrumb(&self, arch: &TargetArch, parts: &[ConcreteTypePart]) -> MemoryLayoutResult { use ConcreteTypePart as CTP; - // Before we do any fancy shenanigans, we need to check if the concrete - // type actually requires laying out memory. debug_assert!(!parts.is_empty()); let (builtin_size, builtin_alignment) = match parts[0] { CTP::Void => (0, 1), @@ -1851,49 +2039,32 @@ impl TypeTable { CTP::Slice => arch.array_size_alignment, CTP::Input => arch.port_size_alignment, CTP::Output => arch.port_size_alignment, - CTP::Tuple(num_embedded) => { - if num_embedded == 0 { - (0, 1) + CTP::Tuple(_) => { + let mono_index = self.mono_lookup.get_monomorph_index(parts, &[]).unwrap(); + if let Some((size, alignment)) = self.mono_lookup.get_monomorph_size_alignment(mono_index) { + return MemoryLayoutResult::TypeExists(size, alignment); } else { - // TODO: This is a bit hacky: structs and unions are neatly - // layed out element by element using the breadcrumbs, but - // here we do special tuple checking. Tuples should be able - // to get their own breadcrumbs for resolving (and storage - // in the type table!) - debug_assert!(num_embedded > 1); - let mut total_size = 0; - let mut total_alignment = 1; - for embedded in ConcreteTypeIter::new(parts, 0) { - match self.get_memory_layout_or_breadcrumb(arch, embedded) { - MemoryLayoutResult::PushBreadcrumb(new_breadcrumb) => { - return MemoryLayoutResult::PushBreadcrumb(new_breadcrumb); - }, - MemoryLayoutResult::TypeExists(embedded_size, embedded_alignment) => { - align_offset_to(&mut total_size, embedded_alignment); - total_size += embedded_size; - total_alignment = total_alignment.max(embedded_alignment); - } - } - } - - (total_size, total_alignment) + return MemoryLayoutResult::PushBreadcrumb(MemoryBreadcrumb{ + definition_id: DefinitionId::new_invalid(), + monomorph_idx: mono_index, + next_member: 0, + next_embedded: 0, + first_size_alignment_idx: self.size_alignment_stack.len(), + }) } }, CTP::Instance(definition_id, _) => { // Retrieve entry and the specific monomorph index by applying // the full concrete type. - let entry = self.lookup.get(&definition_id).unwrap(); - let monomorph_idx = entry.get_monomorph_index(parts).unwrap(); + let entry = self.type_lookup.get(&definition_id).unwrap(); + let mono_index = self.mono_lookup.get_monomorph_index(parts, &entry.poly_vars).unwrap(); - // Check if this monomorph has its size and alignment layed out, - // and if so: return it. - if let Some((size, alignment)) = entry.get_monomorph_size_alignment(monomorph_idx) { - // Type has been layed out in memory + if let Some((size, alignment)) = self.mono_lookup.get_monomorph_size_alignment(mono_index) { return MemoryLayoutResult::TypeExists(size, alignment); } else { return MemoryLayoutResult::PushBreadcrumb(MemoryBreadcrumb{ definition_id, - monomorph_idx, + monomorph_idx: mono_index, next_member: 0, next_embedded: 0, first_size_alignment_idx: self.size_alignment_stack.len(), diff --git a/src/protocol/tests/parser_monomorphs.rs b/src/protocol/tests/parser_monomorphs.rs index 21124795a872e9895890e26193f70e957ab9b853..2926b727bfa3360ea90779f6de4d5f43ab281694 100644 --- a/src/protocol/tests/parser_monomorphs.rs +++ b/src/protocol/tests/parser_monomorphs.rs @@ -51,7 +51,8 @@ fn test_enum_monomorphs() { " ).for_enum("Answer", |e| { e .assert_num_monomorphs(1) - .assert_has_monomorph("Answer"); + .assert_has_monomorph("Answer") + .assert_size_alignment("Answer", 1, 1); }); // Note for reader: because the enum doesn't actually use the polymorphic diff --git a/src/protocol/tests/utils.rs b/src/protocol/tests/utils.rs index 45faf494e2d692b358c0d91f5692c431d103d1b8..8ffe0c7bbd8e44ccc3b99c90b49944e2fb786530 100644 --- a/src/protocol/tests/utils.rs +++ b/src/protocol/tests/utils.rs @@ -297,8 +297,8 @@ impl<'a> StructTester<'a> { self = self.assert_has_monomorph(monomorph); let (mono_idx, _) = has_monomorph(self.ctx, self.ast_def.this.upcast(), monomorph); let mono_idx = mono_idx.unwrap(); + let mono = self.ctx.types.get_monomorph(mono_idx); - let mono = &self.type_def.monomorphs[mono_idx]; assert!( mono.size == size && mono.alignment == alignment, "[{}] Expected (size,alignment) of ({}, {}), but got ({}, {}) for {}", @@ -403,6 +403,20 @@ impl<'a> EnumTester<'a> { self } + pub(crate) fn assert_size_alignment(mut self, serialized_monomorph: &str, size: usize, alignment: usize) -> Self { + self = self.assert_has_monomorph(serialized_monomorph); + let (has_monomorph, serialized) = has_monomorph(self.ctx, self.def.this.upcast(), serialized_monomorph); + let mono_index = has_monomorph.unwrap(); + let mono = self.ctx.types.get_monomorph(mono_index); + + assert!( + mono.size == size && mono.alignment == alignment, + "[{}] Expected (size,alignment) of ({}, {}), but got ({}, {}) for {}", + self.ctx.test_name, size, alignment, mono.size, mono.alignment, self.assert_postfix() + ); + self + } + pub(crate) fn assert_postfix(&self) -> String { let mut v = String::new(); v.push_str("Enum{ name: "); @@ -462,14 +476,16 @@ impl<'a> UnionTester<'a> { self = self.assert_has_monomorph(serialized_monomorph); let (mono_idx, _) = has_monomorph(self.ctx, self.ast_def.this.upcast(), serialized_monomorph); let mono_idx = mono_idx.unwrap(); - let mono = &self.type_def.monomorphs[mono_idx]; + let mono_base = self.ctx.types.get_monomorph(mono_idx); + let mono_union = mono_base.variant.as_union(); + assert!( - stack_size == mono.stack_size && stack_alignment == mono.stack_alignment && - heap_size == mono.heap_size && heap_alignment == mono.heap_alignment, + stack_size == mono_base.size && stack_alignment == mono_base.alignment && + heap_size == mono_union.heap_size && heap_alignment == mono_union.heap_alignment, "[{}] Expected (stack | heap) (size, alignment) of ({}, {} | {}, {}), but got ({}, {} | {}, {}) for {}", self.ctx.test_name, stack_size, stack_alignment, heap_size, heap_alignment, - mono.stack_size, mono.stack_alignment, mono.heap_size, mono.heap_alignment, + mono_base.size, mono_base.alignment, mono_union.heap_size, mono_union.heap_alignment, self.assert_postfix() ); self @@ -684,7 +700,12 @@ impl<'a> FunctionTester<'a> { fn eval_until_end(&self) -> (Prompt, Result) { use crate::protocol::*; - let mut prompt = Prompt::new(&self.ctx.types, &self.ctx.heap, self.def.this.upcast(), 0, ValueGroup::new_stack(Vec::new())); + // Assuming the function is not polymorphic + let definition_id = self.def.this.upcast(); + let func_type = [ConcreteTypePart::Function(definition_id, 0)]; + let mono_index = self.ctx.types.get_procedure_monomorph_index(&definition_id, &func_type).unwrap(); + + let mut prompt = Prompt::new(&self.ctx.types, &self.ctx.heap, self.def.this.upcast(), mono_index, ValueGroup::new_stack(Vec::new())); let mut call_context = FakeRunContext{}; loop { let result = prompt.step(&self.ctx.types, &self.ctx.heap, &self.ctx.modules, &mut call_context); @@ -728,7 +749,7 @@ impl<'a> VariableTester<'a> { pub(crate) fn assert_concrete_type(self, expected: &str) -> Self { // Lookup concrete type in type table - let mono_data = self.ctx.types.get_procedure_expression_data(&self.definition_id, 0); + let mono_data = get_procedure_monomorph(&self.ctx.heap, &self.ctx.types, self.definition_id); let concrete_type = &mono_data.expr_data[self.var_expr.unique_id_in_definition as usize].expr_type; // Serialize and check @@ -762,7 +783,7 @@ impl<'a> ExpressionTester<'a> { pub(crate) fn assert_concrete_type(self, expected: &str) -> Self { // Lookup concrete type - let mono_data = self.ctx.types.get_procedure_expression_data(&self.definition_id, 0); + let mono_data = get_procedure_monomorph(&self.ctx.heap, &self.ctx.types, self.definition_id); let expr_index = self.expr.get_unique_id_in_definition(); let concrete_type = &mono_data.expr_data[expr_index as usize].expr_type; @@ -785,6 +806,23 @@ impl<'a> ExpressionTester<'a> { } } +fn get_procedure_monomorph<'a>(heap: &Heap, types: &'a TypeTable, definition_id: DefinitionId) -> &'a ProcedureMonomorph { + let ast_definition = &heap[definition_id]; + let func_type = if ast_definition.is_function() { + [ConcreteTypePart::Function(definition_id, 0)] + } else if ast_definition.is_component() { + [ConcreteTypePart::Component(definition_id, 0)] + } else { + assert!(false); + unreachable!() + }; + + let mono_index = types.get_procedure_monomorph_index(&definition_id, &func_type).unwrap(); + let mono_data = types.get_procedure_monomorph(mono_index); + + mono_data +} + //------------------------------------------------------------------------------ // Interface for failed compilation //------------------------------------------------------------------------------ @@ -888,19 +926,27 @@ impl<'a> ErrorTester<'a> { fn has_equal_num_monomorphs(ctx: TestCtx, num: usize, definition_id: DefinitionId) -> (bool, usize) { use DefinedTypeVariant::*; + // Again: inefficient, but its testing code let type_def = ctx.types.get_base_definition(&definition_id).unwrap(); - let num_on_type = match &type_def.definition { - Struct(v) => v.monomorphs.len(), - Enum(v) => v.monomorphs.len(), - Union(v) => v.monomorphs.len(), - Function(v) => v.monomorphs.len(), - Component(v) => v.monomorphs.len(), - }; + let mut num_on_type = 0; + + for mono in &ctx.types.mono_lookup.monomorphs { + match &mono.concrete_type.parts[0] { + ConcreteTypePart::Instance(def_id, _) | + ConcreteTypePart::Function(def_id, _) | + ConcreteTypePart::Component(def_id, _) => { + if *def_id == definition_id { + num_on_type += 1; + } + }, + _ => {}, + }; + } (num_on_type == num, num_on_type) } -fn has_monomorph(ctx: TestCtx, definition_id: DefinitionId, serialized_monomorph: &str) -> (Option, String) { +fn has_monomorph(ctx: TestCtx, definition_id: DefinitionId, serialized_monomorph: &str) -> (Option, String) { use DefinedTypeVariant::*; let type_def = ctx.types.get_base_definition(&definition_id).unwrap(); @@ -919,34 +965,15 @@ fn has_monomorph(ctx: TestCtx, definition_id: DefinitionId, serialized_monomorph let first_idx = full_buffer.len(); full_buffer.push_str(concrete_type.display_name(ctx.heap).as_str()); if &full_buffer[first_idx..] == serialized_monomorph { - has_match = Some(mono_idx); + has_match = Some(mono_idx as i32); } full_buffer.push('"'); }; - match &type_def.definition { - Enum(definition) => { - for (mono_idx, mono) in definition.monomorphs.iter().enumerate() { - append_to_full_buffer(&mono.concrete_type, mono_idx); - } - }, - Union(definition) => { - for (mono_idx, mono) in definition.monomorphs.iter().enumerate() { - append_to_full_buffer(&mono.concrete_type, mono_idx); - } - }, - Struct(definition) => { - for (mono_idx, mono) in definition.monomorphs.iter().enumerate() { - append_to_full_buffer(&mono.concrete_type, mono_idx); - } - }, - Function(_) | Component(_) => { - let monomorphs = type_def.definition.procedure_monomorphs(); - for (mono_idx, mono) in monomorphs.iter().enumerate() { - append_to_full_buffer(&mono.concrete_type, mono_idx); - } - } + // Bit wasteful, but this is (temporary?) testing code: + for (mono_idx, mono) in ctx.types.mono_lookup.monomorphs.iter().enumerate() { + append_to_full_buffer(&mono.concrete_type, mono_idx); } full_buffer.push(']');