Changeset - a9cf12aa4225
Parent rev.
Child rev.
[Not reviewed]
0 1 0
mh - 3 years ago 2022-02-14 10:25:22
contact@maxhenger.nl
WIP: Starting type storage refactoring
1 file changed with 107 insertions and 30 deletions:
src/protocol/parser/type_table.rs
107
30
0 comments (0 inline, 0 general)
src/protocol/parser/type_table.rs
➞
Show inline comments
 
@@ -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<H: Hasher>(&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<DefinitionId, DefinedType>,

			




	
	
	
		
 
    // Lookup from AST DefinitionId to a defined type. Also lookups for

			




	
	
	
		
 
    // concrete type to monomorphs

			




	
	
	
		
 
    pub(crate) definition_lookup: HashMap<DefinitionId, DefinedType>,

			




	
	
	
		
 
    pub(crate) mono_type_lookup: HashMap<MonoSearchKey, TypeId>,

			




	
	
	
		
 
    pub(crate) mono_types: Vec<MonoType>,

			




	
	
	
		
 
    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<TypeLoopBreadcrumb>,

			




	
	
	
		
 
    type_loops: Vec<TypeLoop>,

			




	
	
	
		
 
    /// Stores all encountered types during type loop detection. Used afterwards

			




	
	
	
		
 
    /// to iterate over all types in order to compute size/alignment.

			




	
	
	
		
 
    // Stores all encountered types during type loop detection. Used afterwards

			




	
	
	
		
 
    // to iterate over all types in order to compute size/alignment.

			




	
	
	
		
 
    encountered_types: Vec<TypeLoopEntry>,

			




	
	
	
		
 
    /// Breadcrumbs and temporary storage during memory layout computation.

			




	
	
	
		
 
    // Breadcrumbs and temporary storage during memory layout computation.

			




	
	
	
		
 
    memory_layout_breadcrumbs: Vec<MemoryBreadcrumb>,

			




	
	
	
		
 
    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<i32> {

			




	
	
	
		
 
        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) {

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








    
        Server instance: kalli-1039567
    
    
        This site is powered by
            Kallithea,
        which is
        © 2010–2022 by various authors & licensed under GPLv3.
            – Support