From a9cf12aa4225be895e6acefcca2aede191307f81 2022-02-14 10:25:22 From: mh Date: 2022-02-14 10:25:22 Subject: [PATCH] WIP: Starting type storage refactoring --- diff --git a/src/protocol/parser/type_table.rs b/src/protocol/parser/type_table.rs index f6e909cd3196a83f0206091359c3cdbbeed0d611..5e318dc6461b3d687874b5580aa71b2f8f872c21 100644 --- a/src/protocol/parser/type_table.rs +++ b/src/protocol/parser/type_table.rs @@ -527,6 +527,76 @@ impl MonomorphTable { } } +//------------------------------------------------------------------------------ +// Monomorph Type Storage +//------------------------------------------------------------------------------ + +/// Generic unique type ID. Every monomorphed type and every non-polymorphic +/// type will have one of these associated with it. +pub struct TypeId(i64); + +impl TypeId { + pub(crate) fn new_invalid() -> Self { + return Self(-1); + } +} + +/// A monomorphed type (or non-polymorphic type's) memory layout and information +/// regarding associated types (like a struct's field type). +pub struct MonoType { + concrete_type: ConcreteType, +} + +/// Special structure that acts like the lookup key for `ConcreteType` instances +/// that have already been added to the type table before. +struct MonoSearchKey { + parts: Vec<(bool, ConcreteTypePart)>, +} + +impl Hash for MonoSearchKey { + fn hash(&self, state: &mut H) { + for index in 0..self.parts.len() { + let is_in_use = self.parts[index].0; + if is_in_use { + let type_part = &self.parts[index].1; + type_part.hash(state); + } + } + } +} + +impl PartialEq for MonoSearchKey { + fn eq(&self, other: &Self) -> bool { + let mut self_index = 0; + let mut other_index = 0; + + while self_index < self.parts.len() && other_index < other.parts.len() { + let (self_in_use, self_part) = &self.parts[self_index]; + let (other_in_use, other_part) = &other.parts[self_index]; + + if self_in_use == other_in_use { + if self_in_use { + // Both are in use, so both should be equal + if self_part != other_part { + return false; + } + } // else: both not in use, so we don't care + } else { + // No agreement on importance of parts. This is practically + // impossible + unreachable!(); + } + + self_index += 1; + other_index += 1; + } + + // Everything matched, so if we're at the end of both arrays then we're + // certain that the two keys are equal. + return self_index == self.parts.len() && other_index == other.parts.len(); + } +} + //------------------------------------------------------------------------------ // Type table //------------------------------------------------------------------------------ @@ -539,6 +609,7 @@ struct TypeLoopBreadcrumb { next_embedded: u32, // for unions, the index into the variant's embedded types } +// Programmer note: keep this struct free of dynamically allocated memory #[derive(Clone)] struct MemoryBreadcrumb { monomorph_idx: i32, @@ -570,18 +641,20 @@ struct TypeLoop { } pub struct TypeTable { - /// Lookup from AST DefinitionId to a defined type. Also lookups for - /// concrete type to monomorphs - pub(crate) type_lookup: HashMap, + // Lookup from AST DefinitionId to a defined type. Also lookups for + // concrete type to monomorphs + pub(crate) definition_lookup: HashMap, + pub(crate) mono_type_lookup: HashMap, + pub(crate) mono_types: Vec, 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. + // 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, type_loops: Vec, - /// Stores all encountered types during type loop detection. Used afterwards - /// to iterate over all types in order to compute size/alignment. + // Stores all encountered types during type loop detection. Used afterwards + // to iterate over all types in order to compute size/alignment. encountered_types: Vec, - /// Breadcrumbs and temporary storage during memory layout computation. + // Breadcrumbs and temporary storage during memory layout computation. memory_layout_breadcrumbs: Vec, size_alignment_stack: Vec<(usize, usize)>, } @@ -590,7 +663,9 @@ impl TypeTable { /// Construct a new type table without any resolved types. pub(crate) fn new() -> Self { Self{ - type_lookup: HashMap::with_capacity(128), + definition_lookup: HashMap::with_capacity(128), + mono_type_lookup: HashMap::with_capacity(128), + mono_types: Vec::with_capacity(128), mono_lookup: MonomorphTable::new(), type_loop_breadcrumbs: Vec::with_capacity(32), type_loops: Vec::with_capacity(8), @@ -609,7 +684,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.type_lookup.is_empty()); + debug_assert!(self.definition_lookup.is_empty()); if cfg!(debug_assertions) { for (index, module) in modules.iter().enumerate() { @@ -619,7 +694,7 @@ impl TypeTable { // Use context to guess hashmap size of the base types let reserve_size = ctx.heap.definitions.len(); - self.type_lookup.reserve(reserve_size); + self.definition_lookup.reserve(reserve_size); // Resolve all base types for definition_idx in 0..ctx.heap.definitions.len() { @@ -635,7 +710,7 @@ impl TypeTable { } } - debug_assert_eq!(self.type_lookup.len(), reserve_size, "mismatch in reserved size of type table"); // NOTE: Temp fix for builtin functions + debug_assert_eq!(self.definition_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; } @@ -645,7 +720,7 @@ 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.type_lookup.get(&definition_id).unwrap(); + let poly_type = self.definition_lookup.get(&definition_id).unwrap(); if !poly_type.definition.type_class().is_data_type() || !poly_type.poly_vars.is_empty() { continue; @@ -675,7 +750,7 @@ impl TypeTable { /// an option anyway #[inline] pub(crate) fn get_base_definition(&self, definition_id: &DefinitionId) -> Option<&DefinedType> { - self.type_lookup.get(&definition_id) + self.definition_lookup.get(&definition_id) } /// Returns the index into the monomorph type array if the procedure type @@ -683,7 +758,7 @@ impl TypeTable { /// FIXME: This really shouldn't be called from within the runtime. See UnsafeCell in MonomorphTable #[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(); + let base_type = self.definition_lookup.get(definition_id).unwrap(); return self.mono_lookup.get_monomorph_index(type_parts, &base_type.poly_vars); } @@ -714,7 +789,7 @@ 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 base_type = self.type_lookup.get_mut(definition_id).unwrap(); + let base_type = self.definition_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(), @@ -735,7 +810,7 @@ impl TypeTable { debug_assert_eq!(definition_id, get_concrete_type_definition(&concrete_type)); // Check if the monomorph already exists - let poly_type = self.type_lookup.get_mut(&definition_id).unwrap(); + let poly_type = self.definition_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); } @@ -749,13 +824,15 @@ impl TypeTable { return Ok(mono_idx as i32); } + /// + //-------------------------------------------------------------------------- // Building base types //-------------------------------------------------------------------------- /// Builds the base type for an enum. Will not compute byte sizes fn build_base_enum_definition(&mut self, modules: &[Module], ctx: &mut PassCtx, definition_id: DefinitionId) -> Result<(), ParseError> { - debug_assert!(!self.type_lookup.contains_key(&definition_id), "base enum already built"); + debug_assert!(!self.definition_lookup.contains_key(&definition_id), "base enum already built"); let definition = ctx.heap[definition_id].as_enum(); let root_id = definition.defined_in; @@ -807,7 +884,7 @@ 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.type_lookup.insert(definition_id, DefinedType { + self.definition_lookup.insert(definition_id, DefinedType { ast_root: root_id, ast_definition: definition_id, definition: DefinedTypeVariant::Enum(EnumType{ @@ -827,7 +904,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.type_lookup.contains_key(&definition_id), "base union already built"); + debug_assert!(!self.definition_lookup.contains_key(&definition_id), "base union already built"); let definition = ctx.heap[definition_id].as_union(); let root_id = definition.defined_in; @@ -872,7 +949,7 @@ impl TypeTable { let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use); - self.type_lookup.insert(definition_id, DefinedType{ + self.definition_lookup.insert(definition_id, DefinedType{ ast_root: root_id, ast_definition: definition_id, definition: DefinedTypeVariant::Union(UnionType{ variants, tag_type, tag_size }), @@ -885,7 +962,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.type_lookup.contains_key(&definition_id), "base struct already built"); + debug_assert!(!self.definition_lookup.contains_key(&definition_id), "base struct already built"); let definition = ctx.heap[definition_id].as_struct(); let root_id = definition.defined_in; @@ -917,7 +994,7 @@ impl TypeTable { let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use); - self.type_lookup.insert(definition_id, DefinedType{ + self.definition_lookup.insert(definition_id, DefinedType{ ast_root: root_id, ast_definition: definition_id, definition: DefinedTypeVariant::Struct(StructType{ fields }), @@ -930,7 +1007,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.type_lookup.contains_key(&definition_id), "base function already built"); + debug_assert!(!self.definition_lookup.contains_key(&definition_id), "base function already built"); let definition = ctx.heap[definition_id].as_function(); let root_id = definition.defined_in; @@ -968,7 +1045,7 @@ impl TypeTable { let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use); - self.type_lookup.insert(definition_id, DefinedType{ + self.definition_lookup.insert(definition_id, DefinedType{ ast_root: root_id, ast_definition: definition_id, definition: DefinedTypeVariant::Function(FunctionType{ return_type: definition.return_type.clone(), arguments }), @@ -981,7 +1058,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.type_lookup.contains_key(&definition_id), "base component already built"); + debug_assert!(!self.definition_lookup.contains_key(&definition_id), "base component already built"); let definition = &ctx.heap[definition_id].as_component(); let root_id = definition.defined_in; @@ -1020,7 +1097,7 @@ impl TypeTable { let is_polymorph = poly_vars.iter().any(|arg| arg.is_in_use); - self.type_lookup.insert(definition_id, DefinedType{ + self.definition_lookup.insert(definition_id, DefinedType{ ast_root: root_id, ast_definition: definition_id, definition: DefinedTypeVariant::Component(ComponentType{ variant: definition.variant, arguments }), @@ -1468,7 +1545,7 @@ impl TypeTable { CTP::Instance(definition_id, _) | CTP::Function(definition_id, _) | CTP::Component(definition_id, _) => { - let base_type = self.type_lookup.get(definition_id).unwrap(); + let base_type = self.definition_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) @@ -1524,7 +1601,7 @@ impl TypeTable { }, 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 base_type = self.definition_lookup.get_mut(&definition_id).unwrap(); let monomorph_index = match &mut base_type.definition { DTV::Enum(definition) => { // The enum is a bit exceptional in that when we insert @@ -2024,7 +2101,7 @@ impl TypeTable { CTP::Instance(definition_id, _) => { // Retrieve entry and the specific monomorph index by applying // the full concrete type. - let entry = self.type_lookup.get(&definition_id).unwrap(); + let entry = self.definition_lookup.get(&definition_id).unwrap(); let mono_index = self.mono_lookup.get_monomorph_index(parts, &entry.poly_vars).unwrap(); if let Some((size, alignment)) = self.mono_lookup.get_monomorph_size_alignment(mono_index) {