diff --git a/src/protocol/ast.rs b/src/protocol/ast.rs index 63762b6dadd95850af6bb4b2325310725ccb67ea..3510e80f484af804fb41047d1ff0c38d14abd87c 100644 --- a/src/protocol/ast.rs +++ b/src/protocol/ast.rs @@ -495,6 +495,8 @@ pub enum ConcreteTypePart { Slice, Input, Output, + // Tuple: variable number of nested types, will never be 1 + Tuple(u32), // User defined type with any number of nested types Instance(DefinitionId, u32), // instance of data type Function(DefinitionId, u32), // instance of function @@ -513,6 +515,7 @@ impl ConcreteTypePart { 0, Array | Slice | Input | Output => 1, + Tuple(num_embedded) => *num_embedded, Instance(_, num_embedded) => *num_embedded, Function(_, num_embedded) => *num_embedded, Component(_, num_embedded) => *num_embedded, @@ -535,25 +538,28 @@ impl ConcreteType { /// Returns an iterator over the subtrees that are type arguments (e.g. an /// array element's type, or a polymorphic type's arguments) to the /// provided parent type (specified by its index in the `parts` array). - pub(crate) fn embedded_iter<'a>(&'a self, parent_part_idx: usize) -> ConcreteTypeIter<'a> { - let num_embedded = self.parts[parent_part_idx].num_embedded(); - return ConcreteTypeIter{ - concrete: self, - idx_embedded: 0, - num_embedded, - part_idx: parent_part_idx + 1, - } + pub(crate) fn embedded_iter(&self, parent_part_idx: usize) -> ConcreteTypeIter { + return ConcreteTypeIter::new(&self.parts, parent_part_idx); } + /// Construct a human-readable name for the type. Because this performs + /// a string allocation don't use it for anything else then displaying the + /// type to the user. + pub(crate) fn display_name(&self, heap: &Heap) -> String { + return Self::type_parts_display_name(self.parts.as_slice(), heap); + } + + // --- Utilities that operate on slice of parts + /// Given the starting position of a type tree, determine the exclusive /// ending index. - pub(crate) fn subtree_end_idx(&self, start_idx: usize) -> usize { + pub(crate) fn type_parts_subtree_end_idx(parts: &[ConcreteTypePart], start_idx: usize) -> usize { let mut depth = 1; - let num_parts = self.parts.len(); + let num_parts = parts.len(); debug_assert!(start_idx < num_parts); - for part_idx in start_idx..self.parts.len() { - let depth_change = self.parts[part_idx].num_embedded() as i32 - 1; + for part_idx in start_idx..parts.len() { + let depth_change = parts[part_idx].num_embedded() as i32 - 1; depth += depth_change; debug_assert!(depth >= 0); @@ -566,85 +572,108 @@ impl ConcreteType { return 0; } - /// Construct a human-readable name for the type. Because this performs - /// a string allocation don't use it for anything else then displaying the - /// type to the user. - pub(crate) fn display_name(&self, heap: &Heap) -> String { - fn display_part(parts: &[ConcreteTypePart], heap: &Heap, mut idx: usize, target: &mut String) -> usize { - use ConcreteTypePart as CTP; - use crate::protocol::parser::token_parsing::*; - - let cur_idx = idx; - idx += 1; // increment by 1, because it always happens - - match parts[cur_idx] { - CTP::Void => { target.push_str("void"); }, - CTP::Message => { target.push_str(KW_TYPE_MESSAGE_STR); }, - CTP::Bool => { target.push_str(KW_TYPE_BOOL_STR); }, - CTP::UInt8 => { target.push_str(KW_TYPE_UINT8_STR); }, - CTP::UInt16 => { target.push_str(KW_TYPE_UINT16_STR); }, - CTP::UInt32 => { target.push_str(KW_TYPE_UINT32_STR); }, - CTP::UInt64 => { target.push_str(KW_TYPE_UINT64_STR); }, - CTP::SInt8 => { target.push_str(KW_TYPE_SINT8_STR); }, - CTP::SInt16 => { target.push_str(KW_TYPE_SINT16_STR); }, - CTP::SInt32 => { target.push_str(KW_TYPE_SINT32_STR); }, - CTP::SInt64 => { target.push_str(KW_TYPE_SINT64_STR); }, - CTP::Character => { target.push_str(KW_TYPE_CHAR_STR); }, - CTP::String => { target.push_str(KW_TYPE_STRING_STR); }, - CTP::Array | CTP::Slice => { - idx = display_part(parts, heap, idx, target); - target.push_str("[]"); - }, - CTP::Input => { - target.push_str(KW_TYPE_IN_PORT_STR); - target.push('<'); - idx = display_part(parts, heap, idx, target); - target.push('>'); - }, - CTP::Output => { - target.push_str(KW_TYPE_OUT_PORT_STR); + /// Produces a human-readable representation of the concrete type parts + fn type_parts_display_name(parts: &[ConcreteTypePart], heap: &Heap) -> String { + let mut name = String::with_capacity(128); + let _final_idx = Self::render_type_part_at(parts, heap, 0, &mut name); + debug_assert_eq!(_final_idx, parts.len()); + + return name; + } + + /// Produces a human-readable representation of a single type part. Lower + /// level utility for `type_parts_display_name`. + fn render_type_part_at(parts: &[ConcreteTypePart], heap: &Heap, mut idx: usize, target: &mut String) -> usize { + use ConcreteTypePart as CTP; + use crate::protocol::parser::token_parsing::*; + + let cur_idx = idx; + idx += 1; // increment by 1, because it always happens + + match parts[cur_idx] { + CTP::Void => { target.push_str("void"); }, + CTP::Message => { target.push_str(KW_TYPE_MESSAGE_STR); }, + CTP::Bool => { target.push_str(KW_TYPE_BOOL_STR); }, + CTP::UInt8 => { target.push_str(KW_TYPE_UINT8_STR); }, + CTP::UInt16 => { target.push_str(KW_TYPE_UINT16_STR); }, + CTP::UInt32 => { target.push_str(KW_TYPE_UINT32_STR); }, + CTP::UInt64 => { target.push_str(KW_TYPE_UINT64_STR); }, + CTP::SInt8 => { target.push_str(KW_TYPE_SINT8_STR); }, + CTP::SInt16 => { target.push_str(KW_TYPE_SINT16_STR); }, + CTP::SInt32 => { target.push_str(KW_TYPE_SINT32_STR); }, + CTP::SInt64 => { target.push_str(KW_TYPE_SINT64_STR); }, + CTP::Character => { target.push_str(KW_TYPE_CHAR_STR); }, + CTP::String => { target.push_str(KW_TYPE_STRING_STR); }, + CTP::Array | CTP::Slice => { + idx = Self::render_type_part_at(parts, heap, idx, target); + target.push_str("[]"); + }, + CTP::Input => { + target.push_str(KW_TYPE_IN_PORT_STR); + target.push('<'); + idx = Self::render_type_part_at(parts, heap, idx, target); + target.push('>'); + }, + CTP::Output => { + target.push_str(KW_TYPE_OUT_PORT_STR); + target.push('<'); + idx = Self::render_type_part_at(parts, heap, idx, target); + target.push('>'); + }, + CTP::Tuple(num_parts) => { + target.push('('); + if num_parts != 0 { + idx = Self::render_type_part_at(parts, heap, idx, target); + for _ in 1..num_parts { + target.push(','); + idx = Self::render_type_part_at(parts, heap, idx, target); + } + } + target.push(')'); + }, + CTP::Instance(definition_id, num_poly_args) | + CTP::Function(definition_id, num_poly_args) | + CTP::Component(definition_id, num_poly_args) => { + let definition = &heap[definition_id]; + target.push_str(definition.identifier().value.as_str()); + + if num_poly_args != 0 { target.push('<'); - idx = display_part(parts, heap, idx, target); - target.push('>'); - }, - CTP::Instance(definition_id, num_poly_args) | - CTP::Function(definition_id, num_poly_args) | - CTP::Component(definition_id, num_poly_args) => { - let definition = &heap[definition_id]; - target.push_str(definition.identifier().value.as_str()); - - if num_poly_args != 0 { - target.push('<'); - for poly_arg_idx in 0..num_poly_args { - if poly_arg_idx != 0 { - target.push(','); - idx = display_part(parts, heap, idx, target); - } + for poly_arg_idx in 0..num_poly_args { + if poly_arg_idx != 0 { + target.push(','); + idx = Self::render_type_part_at(parts, heap, idx, target); } - target.push('>'); } + target.push('>'); } } - - idx } - let mut name = String::with_capacity(128); - let _final_idx = display_part(&self.parts, heap, 0, &mut name); - debug_assert_eq!(_final_idx, self.parts.len()); - - return name; + idx } } #[derive(Debug)] pub struct ConcreteTypeIter<'a> { - concrete: &'a ConcreteType, + parts: &'a [ConcreteTypePart], idx_embedded: u32, num_embedded: u32, part_idx: usize, } +impl<'a> ConcreteTypeIter<'a> { + pub(crate) fn new(parts: &'a[ConcreteTypePart], parent_idx: usize) -> Self { + let num_embedded = parts[parent_idx].num_embedded(); + return ConcreteTypeIter{ + parts, + idx_embedded: 0, + num_embedded, + part_idx: parent_idx + 1, + } + } +} + impl<'a> Iterator for ConcreteTypeIter<'a> { type Item = &'a [ConcreteTypePart]; @@ -655,12 +684,12 @@ impl<'a> Iterator for ConcreteTypeIter<'a> { // Retrieve the subtree of interest let start_idx = self.part_idx; - let end_idx = self.concrete.subtree_end_idx(start_idx); + let end_idx = ConcreteType::type_parts_subtree_end_idx(&self.parts, start_idx); self.idx_embedded += 1; self.part_idx = end_idx; - return Some(&self.concrete.parts[start_idx..end_idx]); + return Some(&self.parts[start_idx..end_idx]); } } diff --git a/src/protocol/ast_printer.rs b/src/protocol/ast_printer.rs index 39b07471376447c480a689b14a1ab620e03163ca..94a1de00f5443ddc88cad37734069f44eef935bc 100644 --- a/src/protocol/ast_printer.rs +++ b/src/protocol/ast_printer.rs @@ -857,6 +857,17 @@ fn write_parser_type(target: &mut String, heap: &Heap, t: &ParserType) { element_idx = write_element(target, heap, t, element_idx + 1); target.push('>'); }, + PTV::Tuple(num_embedded) => { + target.push('('); + let num_embedded = *num_embedded; + for embedded_idx in 0..num_embedded { + if embedded_idx != 0 { + target.push(','); + } + element_idx = write_element(target, heap, t, element_idx + 1); + } + target.push(')'); + } PTV::PolymorphicArgument(definition_id, arg_idx) => { let definition = &heap[*definition_id]; let poly_var = &definition.poly_vars()[*arg_idx as usize].value; @@ -927,6 +938,16 @@ fn write_concrete_type(target: &mut String, heap: &Heap, def_id: DefinitionId, t idx = write_concrete_part(target, heap, def_id, t, idx + 1); target.push('>') }, + CTP::Tuple(num_embedded) => { + target.push('('); + for idx_embedded in 0..*num_embedded { + if idx_embedded != 0 { + target.push_str(", "); + } + idx = write_concrete_part(target, heap, def_id, t, idx + 1); + } + target.push(')'); + }, CTP::Instance(definition_id, num_embedded) => { let identifier = heap[*definition_id].identifier(); target.push_str(identifier.value.as_str()); diff --git a/src/protocol/mod.rs b/src/protocol/mod.rs index f9d1295140a2ace7cbcc910ac216758e5510aed5..8c3b36972848a66314c30f688e57cd46b27c4434 100644 --- a/src/protocol/mod.rs +++ b/src/protocol/mod.rs @@ -187,6 +187,7 @@ impl ProtocolDescription { }, CTP::Input => if let Value::Input(_) = argument { true } else { false }, CTP::Output => if let Value::Output(_) = argument { true } else { false }, + CTP::Tuple(_) => todo!("implement full type checking on user-supplied arguments"), CTP::Instance(definition_id, _num_embedded) => { let definition = self.types.get_base_definition(definition_id).unwrap(); match &definition.definition { diff --git a/src/protocol/parser/pass_typing.rs b/src/protocol/parser/pass_typing.rs index 268f0d7aed1853aa02b0ef081708c6f585bea0d0..4a75cc5a6249c82f3df41956454ab21e395e7b0f 100644 --- a/src/protocol/parser/pass_typing.rs +++ b/src/protocol/parser/pass_typing.rs @@ -114,6 +114,8 @@ pub(crate) enum InferenceTypePart { Slice, Input, Output, + // Tuple with any number of subtypes (for practical reasons 1 element is impossible) + Tuple(u32), // A user-defined type with any number of subtypes Instance(DefinitionId, u32) } @@ -204,8 +206,8 @@ impl InferenceTypePart { // One subtype, so do not modify depth 0 }, - ITP::Instance(_, num_args) => { - (*num_args as i32) - 1 + ITP::Tuple(num) | ITP::Instance(_, num) => { + (*num as i32) - 1 } } } @@ -609,6 +611,7 @@ impl InferenceType { ITP::Slice => CTP::Slice, ITP::Input => CTP::Input, ITP::Output => CTP::Output, + ITP::Tuple(num) => CTP::Tuple(*num), ITP::Instance(id, num) => CTP::Instance(*id, *num), }; @@ -684,6 +687,17 @@ impl InferenceType { idx = Self::write_display_name(buffer, heap, parts, idx + 1); buffer.push('>'); }, + ITP::Tuple(num_sub) => { + buffer.push('('); + if *num_sub > 0 { + idx = Self::write_display_name(buffer, heap, parts, idx + 1); + for _sub_idx in 1..*num_sub { + buffer.push_str(", "); + idx = Self::write_display_name(buffer, heap, parts, idx + 1); + } + } + buffer.push(')'); + } ITP::Instance(definition_id, num_sub) => { let definition = &heap[*definition_id]; buffer.push_str(definition.identifier().value.as_str()); @@ -3525,6 +3539,7 @@ impl PassTyping { PTV::Array => { infer_type.push(ITP::Array); }, PTV::Input => { infer_type.push(ITP::Input); }, PTV::Output => { infer_type.push(ITP::Output); }, + PTV::Tuple(num_embedded) => { infer_type.push(ITP::Tuple(*num_embedded)); }, PTV::PolymorphicArgument(belongs_to_definition, poly_arg_idx) => { let poly_arg_idx = *poly_arg_idx; if use_definitions_known_poly_args { @@ -3584,6 +3599,7 @@ impl PassTyping { CTP::Slice => parser_type.push(ITP::Slice), CTP::Input => parser_type.push(ITP::Input), CTP::Output => parser_type.push(ITP::Output), + CTP::Tuple(num) => parser_type.push(ITP::Tuple(*num)), CTP::Instance(id, num) => parser_type.push(ITP::Instance(*id, *num)), CTP::Function(_, _) => unreachable!("function type during concrete to inference type conversion"), CTP::Component(_, _) => unreachable!("component type during concrete to inference type conversion"), diff --git a/src/protocol/parser/type_table.rs b/src/protocol/parser/type_table.rs index 4e0279c9ac6f3e228a758a9e12ecc5e6f38395fa..20d1e4a11d9f1469b3f22071e059ad80b62b2b58 100644 --- a/src/protocol/parser/type_table.rs +++ b/src/protocol/parser/type_table.rs @@ -110,18 +110,19 @@ impl DefinedType { 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, concrete_type: &ConcreteType) -> Option { + 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: &ConcreteType, type_b: &ConcreteType, check_if_poly_var_is_used: bool| -> bool { - let mut a_iter = type_a.embedded_iter(0).enumerate(); - let mut b_iter = type_b.embedded_iter(0); + 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(); @@ -140,11 +141,11 @@ impl DefinedType { // Check check if type is polymorphic to some degree at all if cfg!(debug_assertions) { - if let ConcreteTypePart::Instance(definition_id, num_poly_args) = concrete_type.parts[0] { + 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", concrete_type); + assert!(false, "concrete type {:?} is not a user-defined type", parts); } } @@ -160,28 +161,28 @@ impl DefinedType { }, DTV::Union(definition) => { for (monomorph_idx, monomorph) in definition.monomorphs.iter().enumerate() { - if concrete_types_match(&monomorph.concrete_type, concrete_type, true) { + 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, concrete_type, true) { + 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, concrete_type, false) { + 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, concrete_type, false) { + if concrete_types_match(&monomorph.concrete_type.parts, parts, false) { return Some(monomorph_idx) } } @@ -666,7 +667,7 @@ impl TypeTable { // 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) { + if let Some(idx) = poly_type.get_monomorph_index(&concrete_type.parts) { return Ok(idx as i32); } @@ -998,7 +999,7 @@ impl TypeTable { PTV::UInt8 | PTV::UInt16 | PTV::UInt32 | PTV::UInt64 | PTV::SInt8 | PTV::SInt16 | PTV::SInt32 | PTV::SInt64 | PTV::Character | PTV::String | - PTV::Array | PTV::Input | PTV::Output | + PTV::Array | PTV::Input | PTV::Output | PTV::Tuple(_) | // Likewise, polymorphic variables are always valid PTV::PolymorphicArgument(_, _) => {}, // Types that are not constructable, or types that are not @@ -1360,7 +1361,7 @@ impl TypeTable { }; let base_type = self.lookup.get(&definition_id).unwrap(); - if let Some(mono_idx) = base_type.get_monomorph_index(&definition_type) { + if let Some(mono_idx) = base_type.get_monomorph_index(&definition_type.parts) { // Monomorph is already known. Check if it is present in the // breadcrumbs. If so, then we are in a type loop for (breadcrumb_idx, breadcrumb) in self.type_loop_breadcrumbs.iter().enumerate() { @@ -1582,7 +1583,7 @@ impl TypeTable { 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) { + match self.get_memory_layout_or_breadcrumb(arch, &mono_embedded.concrete_type.parts) { MemoryLayoutResult::TypeExists(size, alignment) => { self.size_alignment_stack.push((size, alignment)); }, @@ -1659,7 +1660,7 @@ impl TypeTable { 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) { + match self.get_memory_layout_or_breadcrumb(arch, &mono_field.concrete_type.parts) { MemoryLayoutResult::TypeExists(size, alignment) => { self.size_alignment_stack.push((size, alignment)) }, @@ -1733,7 +1734,7 @@ impl TypeTable { debug_assert!(!variant.embedded.is_empty()); for embedded in &variant.embedded { - match self.get_memory_layout_or_breadcrumb(arch, &embedded.concrete_type) { + match self.get_memory_layout_or_breadcrumb(arch, &embedded.concrete_type.parts) { MemoryLayoutResult::TypeExists(size, alignment) => { self.size_alignment_stack.push((size, alignment)); }, @@ -1787,13 +1788,13 @@ impl TypeTable { self.encountered_types.clear(); } - fn get_memory_layout_or_breadcrumb(&self, arch: &TargetArch, concrete_type: &ConcreteType) -> MemoryLayoutResult { + 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!(!concrete_type.parts.is_empty()); - let (builtin_size, builtin_alignment) = match concrete_type.parts[0] { + debug_assert!(!parts.is_empty()); + let (builtin_size, builtin_alignment) = match parts[0] { CTP::Void => (0, 1), CTP::Message => arch.array_size_alignment, CTP::Bool => (1, 1), @@ -1811,12 +1812,42 @@ 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) + } 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) + } + }, CTP::Instance(definition_id, _) => { - // Special case where we explicitly return to simplify the - // return case for the builtins. + // 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(concrete_type).unwrap(); + let monomorph_idx = entry.get_monomorph_index(parts).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 return MemoryLayoutResult::TypeExists(size, alignment); @@ -1892,14 +1923,16 @@ impl TypeTable { } } -#[inline] fn align_offset_to(offset: &mut usize, alignment: usize) { +#[inline] +fn align_offset_to(offset: &mut usize, alignment: usize) { debug_assert!(alignment > 0); let alignment_min_1 = alignment - 1; *offset += alignment_min_1; *offset &= !(alignment_min_1); } -#[inline] fn get_concrete_type_definition(concrete: &ConcreteType) -> DefinitionId { +#[inline] +fn get_concrete_type_definition(concrete: &ConcreteType) -> DefinitionId { if let ConcreteTypePart::Instance(definition_id, _) = concrete.parts[0] { return definition_id; } else {