From ef37386d0c6ff72a979fa75736f2a6623036bb56 2021-05-21 14:47:09 From: MH Date: 2021-05-21 14:47:09 Subject: [PATCH] Put expression types of procedures in type table Before we annotated the AST. But that is silly in hindsight: certain operations have a completely different meaning when applied in a polymorphic context (i.e. the field index determined by a select expression). --- diff --git a/src/collections/mod.rs b/src/collections/mod.rs index 243c723d50aa4a11c695146cb31f1874e164c268..f46f2b472b55f67be2680ae64498f01088e18d9e 100644 --- a/src/collections/mod.rs +++ b/src/collections/mod.rs @@ -5,4 +5,4 @@ mod sets; pub(crate) use string_pool::{StringPool, StringRef}; pub(crate) use scoped_buffer::{ScopedBuffer, ScopedSection}; -pub(crate) use sets::DequeSet; \ No newline at end of file +pub(crate) use sets::{DequeSet, VecSet}; \ No newline at end of file diff --git a/src/collections/sets.rs b/src/collections/sets.rs index 669a5b65f1f60091ca9a0c97b767e559b49bb584..96f7df9fbdfeb228cc51882a6cc6d2dcf58604ce 100644 --- a/src/collections/sets.rs +++ b/src/collections/sets.rs @@ -1,8 +1,7 @@ use std::collections::VecDeque; /// Simple double ended queue that ensures that all elements are unique. Queue -/// elements are not ordered (use case is that the queue should be rather -/// small). +/// elements are not ordered (we expect the queue to be rather small). pub struct DequeSet { inner: VecDeque, } @@ -49,6 +48,44 @@ impl DequeSet { self.inner.clear(); } + #[inline] + pub fn is_empty(&self) -> bool { + self.inner.is_empty() + } +} + +/// Simple vector set that ensures that all elements are unique. Elements are +/// not ordered (we expect the vector to be small). +pub struct VecSet { + inner: Vec, +} + +impl VecSet { + pub fn new() -> Self { + Self{ inner: Vec::new() } + } + + #[inline] + pub fn pop(&mut self) -> Option { + self.inner.pop() + } + + #[inline] + pub fn push(&mut self, to_push: T) { + for element in self.inner.iter() { + if *element == to_push { + return; + } + } + + self.inner.push(to_push); + } + + #[inline] + pub fn clear(&mut self) { + self.inner.clear(); + } + #[inline] pub fn is_empty(&self) -> bool { self.inner.is_empty() diff --git a/src/protocol/ast.rs b/src/protocol/ast.rs index e25a4c6096979e401e406744b0c72680eb815cb4..674196216068f1b7af7f34f77e500b996290b6cc 100644 --- a/src/protocol/ast.rs +++ b/src/protocol/ast.rs @@ -597,38 +597,6 @@ impl Display for Type { } } -#[derive(Debug, Clone)] -pub enum Field { - Length, - Symbolic(FieldSymbolic), -} -impl Field { - pub fn is_length(&self) -> bool { - match self { - Field::Length => true, - _ => false, - } - } - - pub fn as_symbolic(&self) -> &FieldSymbolic { - match self { - Field::Symbolic(v) => v, - _ => unreachable!("attempted to get Field::Symbolic from {:?}", self) - } - } -} - -#[derive(Debug, Clone)] -pub struct FieldSymbolic { - // Phase 1: Parser - pub(crate) identifier: Identifier, - // Phase 3: Typing - // TODO: @Monomorph These fields cannot be trusted because the last time it - // was typed it may refer to a different monomorph. - pub(crate) definition: Option, - pub(crate) field_idx: usize, -} - #[derive(Debug, Clone, Copy)] pub enum Scope { Definition(DefinitionId), @@ -1562,38 +1530,6 @@ impl Expression { Expression::Variable(expr) => expr.parent = parent, } } - pub fn get_type(&self) -> &ConcreteType { - match self { - Expression::Assignment(expr) => &expr.concrete_type, - Expression::Binding(expr) => &expr.concrete_type, - Expression::Conditional(expr) => &expr.concrete_type, - Expression::Binary(expr) => &expr.concrete_type, - Expression::Unary(expr) => &expr.concrete_type, - Expression::Indexing(expr) => &expr.concrete_type, - Expression::Slicing(expr) => &expr.concrete_type, - Expression::Select(expr) => &expr.concrete_type, - Expression::Literal(expr) => &expr.concrete_type, - Expression::Call(expr) => &expr.concrete_type, - Expression::Variable(expr) => &expr.concrete_type, - } - } - - // TODO: @cleanup - pub fn get_type_mut(&mut self) -> &mut ConcreteType { - match self { - Expression::Assignment(expr) => &mut expr.concrete_type, - Expression::Binding(expr) => &mut expr.concrete_type, - Expression::Conditional(expr) => &mut expr.concrete_type, - Expression::Binary(expr) => &mut expr.concrete_type, - Expression::Unary(expr) => &mut expr.concrete_type, - Expression::Indexing(expr) => &mut expr.concrete_type, - Expression::Slicing(expr) => &mut expr.concrete_type, - Expression::Select(expr) => &mut expr.concrete_type, - Expression::Literal(expr) => &mut expr.concrete_type, - Expression::Call(expr) => &mut expr.concrete_type, - Expression::Variable(expr) => &mut expr.concrete_type, - } - } pub fn get_unique_id_in_definition(&self) -> i32 { match self { @@ -1638,8 +1574,6 @@ pub struct AssignmentExpression { // Validator/Linker pub parent: ExpressionParent, pub unique_id_in_definition: i32, - // Typing - pub concrete_type: ConcreteType, } #[derive(Debug, Clone)] @@ -1652,8 +1586,6 @@ pub struct BindingExpression { // Validator/Linker pub parent: ExpressionParent, pub unique_id_in_definition: i32, - // Typing - pub concrete_type: ConcreteType, } #[derive(Debug, Clone)] @@ -1667,8 +1599,6 @@ pub struct ConditionalExpression { // Validator/Linking pub parent: ExpressionParent, pub unique_id_in_definition: i32, - // Typing - pub concrete_type: ConcreteType, } #[derive(Debug, Clone, Copy, PartialEq, Eq)] @@ -1705,8 +1635,6 @@ pub struct BinaryExpression { // Validator/Linker pub parent: ExpressionParent, pub unique_id_in_definition: i32, - // Typing - pub concrete_type: ConcreteType, } #[derive(Debug, Clone, Copy, PartialEq, Eq)] @@ -1731,8 +1659,6 @@ pub struct UnaryExpression { // Validator/Linker pub parent: ExpressionParent, pub unique_id_in_definition: i32, - // Typing - pub concrete_type: ConcreteType, } #[derive(Debug, Clone)] @@ -1745,8 +1671,6 @@ pub struct IndexingExpression { // Validator/Linker pub parent: ExpressionParent, pub unique_id_in_definition: i32, - // Typing - pub concrete_type: ConcreteType, } #[derive(Debug, Clone)] @@ -1760,8 +1684,6 @@ pub struct SlicingExpression { // Validator/Linker pub parent: ExpressionParent, pub unique_id_in_definition: i32, - // Typing - pub concrete_type: ConcreteType, } #[derive(Debug, Clone)] @@ -1770,12 +1692,10 @@ pub struct SelectExpression { // Parsing pub span: InputSpan, // of the '.' pub subject: ExpressionId, - pub field: Field, + pub field_name: Identifier, // Validator/Linker pub parent: ExpressionParent, pub unique_id_in_definition: i32, - // Typing - pub concrete_type: ConcreteType, } #[derive(Debug, Clone)] @@ -1790,8 +1710,6 @@ pub struct CallExpression { // Validator/Linker pub parent: ExpressionParent, pub unique_id_in_definition: i32, - // Typing - pub concrete_type: ConcreteType, // of the return type } #[derive(Debug, Clone, PartialEq, Eq)] @@ -1822,8 +1740,6 @@ pub struct LiteralExpression { // Validator/Linker pub parent: ExpressionParent, pub unique_id_in_definition: i32, - // Typing - pub concrete_type: ConcreteType, } #[derive(Debug, Clone)] @@ -1927,6 +1843,4 @@ pub struct VariableExpression { pub declaration: Option, pub parent: ExpressionParent, pub unique_id_in_definition: i32, - // Typing - pub concrete_type: ConcreteType, } \ No newline at end of file diff --git a/src/protocol/ast_printer.rs b/src/protocol/ast_printer.rs index f15d0c2544260783ca0207689c7a6fafea3a4d70..a788c9be9fb03ca95f022fc9e4c0b424814e366a 100644 --- a/src/protocol/ast_printer.rs +++ b/src/protocol/ast_printer.rs @@ -561,8 +561,6 @@ impl ASTWriter { self.write_expr(heap, expr.right, indent3); self.kv(indent2).with_s_key("Parent") .with_custom_val(|v| write_expression_parent(v, &expr.parent)); - self.kv(indent2).with_s_key("ConcreteType") - .with_custom_val(|v| write_concrete_type(v, heap, def_id, &expr.concrete_type)); }, Expression::Binding(expr) => { self.kv(indent).with_id(PREFIX_BINARY_EXPR_ID, expr.this.0.index) @@ -573,8 +571,6 @@ impl ASTWriter { self.write_expr(heap, expr.right, indent3); self.kv(indent2).with_s_key("Parent") .with_custom_val(|v| write_expression_parent(v, &expr.parent)); - self.kv(indent2).with_s_key("ConcreteType") - .with_custom_val(|v| write_concrete_type(v, heap, def_id, &expr.concrete_type)); }, Expression::Conditional(expr) => { self.kv(indent).with_id(PREFIX_CONDITIONAL_EXPR_ID, expr.this.0.index) @@ -587,8 +583,6 @@ impl ASTWriter { self.write_expr(heap, expr.false_expression, indent3); self.kv(indent2).with_s_key("Parent") .with_custom_val(|v| write_expression_parent(v, &expr.parent)); - self.kv(indent2).with_s_key("ConcreteType") - .with_custom_val(|v| write_concrete_type(v, heap, def_id, &expr.concrete_type)); }, Expression::Binary(expr) => { self.kv(indent).with_id(PREFIX_BINARY_EXPR_ID, expr.this.0.index) @@ -600,8 +594,6 @@ impl ASTWriter { self.write_expr(heap, expr.right, indent3); self.kv(indent2).with_s_key("Parent") .with_custom_val(|v| write_expression_parent(v, &expr.parent)); - self.kv(indent2).with_s_key("ConcreteType") - .with_custom_val(|v| write_concrete_type(v, heap, def_id, &expr.concrete_type)); }, Expression::Unary(expr) => { self.kv(indent).with_id(PREFIX_UNARY_EXPR_ID, expr.this.0.index) @@ -611,8 +603,6 @@ impl ASTWriter { self.write_expr(heap, expr.expression, indent3); self.kv(indent2).with_s_key("Parent") .with_custom_val(|v| write_expression_parent(v, &expr.parent)); - self.kv(indent2).with_s_key("ConcreteType") - .with_custom_val(|v| write_concrete_type(v, heap, def_id, &expr.concrete_type)); }, Expression::Indexing(expr) => { self.kv(indent).with_id(PREFIX_INDEXING_EXPR_ID, expr.this.0.index) @@ -623,8 +613,6 @@ impl ASTWriter { self.write_expr(heap, expr.index, indent3); self.kv(indent2).with_s_key("Parent") .with_custom_val(|v| write_expression_parent(v, &expr.parent)); - self.kv(indent2).with_s_key("ConcreteType") - .with_custom_val(|v| write_concrete_type(v, heap, def_id, &expr.concrete_type)); }, Expression::Slicing(expr) => { self.kv(indent).with_id(PREFIX_SLICING_EXPR_ID, expr.this.0.index) @@ -637,8 +625,6 @@ impl ASTWriter { self.write_expr(heap, expr.to_index, indent3); self.kv(indent2).with_s_key("Parent") .with_custom_val(|v| write_expression_parent(v, &expr.parent)); - self.kv(indent2).with_s_key("ConcreteType") - .with_custom_val(|v| write_concrete_type(v, heap, def_id, &expr.concrete_type)); }, Expression::Select(expr) => { self.kv(indent).with_id(PREFIX_SELECT_EXPR_ID, expr.this.0.index) @@ -646,20 +632,9 @@ impl ASTWriter { self.kv(indent2).with_s_key("Subject"); self.write_expr(heap, expr.subject, indent3); - match &expr.field { - Field::Length => { - self.kv(indent2).with_s_key("Field").with_s_val("length"); - }, - Field::Symbolic(field) => { - self.kv(indent2).with_s_key("Field").with_identifier_val(&field.identifier); - self.kv(indent3).with_s_key("Definition").with_opt_disp_val(field.definition.as_ref().map(|v| &v.index)); - self.kv(indent3).with_s_key("Index").with_disp_val(&field.field_idx); - } - } + self.kv(indent2).with_s_key("Field").with_identifier_val(&expr.field_name); self.kv(indent2).with_s_key("Parent") .with_custom_val(|v| write_expression_parent(v, &expr.parent)); - self.kv(indent2).with_s_key("ConcreteType") - .with_custom_val(|v| write_concrete_type(v, heap, def_id, &expr.concrete_type)); }, Expression::Literal(expr) => { self.kv(indent).with_id(PREFIX_LITERAL_EXPR_ID, expr.this.0.index) @@ -728,8 +703,6 @@ impl ASTWriter { self.kv(indent2).with_s_key("Parent") .with_custom_val(|v| write_expression_parent(v, &expr.parent)); - self.kv(indent2).with_s_key("ConcreteType") - .with_custom_val(|v| write_concrete_type(v, heap, def_id, &expr.concrete_type)); }, Expression::Call(expr) => { self.kv(indent).with_id(PREFIX_CALL_EXPR_ID, expr.this.0.index) @@ -760,8 +733,6 @@ impl ASTWriter { // Parent self.kv(indent2).with_s_key("Parent") .with_custom_val(|v| write_expression_parent(v, &expr.parent)); - self.kv(indent2).with_s_key("ConcreteType") - .with_custom_val(|v| write_concrete_type(v, heap, def_id, &expr.concrete_type)); }, Expression::Variable(expr) => { self.kv(indent).with_id(PREFIX_VARIABLE_EXPR_ID, expr.this.0.index) @@ -771,8 +742,6 @@ impl ASTWriter { .with_opt_disp_val(expr.declaration.as_ref().map(|v| &v.index)); self.kv(indent2).with_s_key("Parent") .with_custom_val(|v| write_expression_parent(v, &expr.parent)); - self.kv(indent2).with_s_key("ConcreteType") - .with_custom_val(|v| write_concrete_type(v, heap, def_id, &expr.concrete_type)); } } } diff --git a/src/protocol/eval/executor.rs b/src/protocol/eval/executor.rs index aaa8ff51668fbea70e82fe55e9c6a9cf2e7686c4..d2178fc7c6b01753c66f524f0e57f0f9174e8c46 100644 --- a/src/protocol/eval/executor.rs +++ b/src/protocol/eval/executor.rs @@ -6,6 +6,7 @@ use super::store::*; use super::error::*; use crate::protocol::*; use crate::protocol::ast::*; +use crate::protocol::type_table::*; macro_rules! debug_enabled { () => { true }; } macro_rules! debug_log { @@ -26,6 +27,7 @@ pub(crate) enum ExprInstruction { #[derive(Debug, Clone)] pub(crate) struct Frame { pub(crate) definition: DefinitionId, + pub(crate) monomorph_idx: i32, pub(crate) position: StatementId, pub(crate) expr_stack: VecDeque, // hack for expression evaluation, evaluated by popping from back pub(crate) expr_values: VecDeque, // hack for expression results, evaluated by popping from front/back @@ -33,7 +35,7 @@ pub(crate) struct Frame { impl Frame { /// Creates a new execution frame. Does not modify the stack in any way. - pub fn new(heap: &Heap, definition_id: DefinitionId) -> Self { + pub fn new(heap: &Heap, definition_id: DefinitionId, monomorph_idx: i32) -> Self { let definition = &heap[definition_id]; let first_statement = match definition { Definition::Component(definition) => definition.body, @@ -43,6 +45,7 @@ impl Frame { Frame{ definition: definition_id, + monomorph_idx, position: first_statement.upcast(), expr_stack: VecDeque::with_capacity(128), expr_values: VecDeque::with_capacity(128), @@ -159,7 +162,7 @@ pub enum EvalContinuation { Terminal, SyncBlockStart, SyncBlockEnd, - NewComponent(DefinitionId, ValueGroup), + NewComponent(DefinitionId, i32, ValueGroup), BlockFires(Value), BlockGet(Value), Put(Value, Value), @@ -174,19 +177,21 @@ pub struct Prompt { } impl Prompt { - pub fn new(heap: &Heap, def: DefinitionId, args: ValueGroup) -> Self { + pub fn new(_types: &TypeTable, heap: &Heap, def: DefinitionId, monomorph_idx: i32, args: ValueGroup) -> Self { let mut prompt = Self{ frames: Vec::new(), store: Store::new(), }; - prompt.frames.push(Frame::new(heap, def)); + // Maybe do typechecking in the future? + debug_assert!((monomorph_idx as usize) < _types.get_base_definition(&def).unwrap().definition.procedure_monomorphs().len()); + prompt.frames.push(Frame::new(heap, def, monomorph_idx)); args.into_store(&mut prompt.store); prompt } - pub(crate) fn step(&mut self, heap: &Heap, modules: &[Module], ctx: &mut EvalContext) -> EvalResult { + pub(crate) fn step(&mut self, types: &TypeTable, heap: &Heap, modules: &[Module], ctx: &mut EvalContext) -> EvalResult { // Helper function to transfer multiple values from the expression value // array into a heap region (e.g. constructing arrays or structs). fn transfer_expression_values_front_into_heap(cur_frame: &mut Frame, store: &mut Store, num_values: usize) -> HeapPos { @@ -389,7 +394,9 @@ impl Prompt { }, Expression::Select(expr) => { let subject= cur_frame.expr_values.pop_back().unwrap(); - let field_idx = expr.field.as_symbolic().field_idx as u32; + let mono_data = types.get_procedure_expression_data(&cur_frame.definition, 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 // refer to it if it already lives on the stack/heap. let (deallocate_heap_pos, value_to_push) = match subject { @@ -429,8 +436,11 @@ impl Prompt { } Literal::Integer(lit_value) => { use ConcreteTypePart as CTP; - debug_assert_eq!(expr.concrete_type.parts.len(), 1); - match expr.concrete_type.parts[0] { + let def_types = types.get_procedure_expression_data(&cur_frame.definition, 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); + match concrete_type.parts[0] { CTP::UInt8 => Value::UInt8(lit_value.unsigned_value as u8), CTP::UInt16 => Value::UInt16(lit_value.unsigned_value as u16), CTP::UInt32 => Value::UInt32(lit_value.unsigned_value as u32), @@ -439,7 +449,7 @@ impl Prompt { CTP::SInt16 => Value::SInt16(lit_value.unsigned_value as i16), CTP::SInt32 => Value::SInt32(lit_value.unsigned_value as i32), CTP::SInt64 => Value::SInt64(lit_value.unsigned_value as i64), - _ => unreachable!("got concrete type {:?} for integer literal at expr {:?}", &expr.concrete_type, expr_id), + _ => unreachable!("got concrete type {:?} for integer literal at expr {:?}", concrete_type, expr_id), } } Literal::Struct(lit_value) => { @@ -484,8 +494,12 @@ impl Prompt { self.store.stack.push(argument); } + // 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 call_data = &mono_data.expr_data[expr.unique_id_in_definition as usize]; + // Push the new frame - self.frames.push(Frame::new(heap, expr.definition)); + self.frames.push(Frame::new(heap, expr.definition, call_data.field_or_monomorph_idx)); self.store.cur_stack_boundary = new_stack_boundary; // To simplify the logic a little bit we will now @@ -665,6 +679,9 @@ 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 expr_data = &mono_data.expr_data[call_expr.unique_id_in_definition as usize]; + // Note that due to expression value evaluation they exist in // reverse order on the stack. // TODO: Revise this code, keep it as is to be compatible with current runtime @@ -684,7 +701,7 @@ impl Prompt { cur_frame.position = stmt.next; todo!("Make sure this is handled correctly, transfer 'heap' values to another Prompt"); - Ok(EvalContinuation::NewComponent(call_expr.definition, argument_group)) + Ok(EvalContinuation::NewComponent(call_expr.definition, expr_data.field_or_monomorph_idx, argument_group)) }, Statement::Expression(stmt) => { // The expression has just been completely evaluated. Some diff --git a/src/protocol/mod.rs b/src/protocol/mod.rs index 12f5acc3386ab4f83bafd844bfbdbd471661953e..c52236eeb8caad4696d3a66ec68d878d32918c8a 100644 --- a/src/protocol/mod.rs +++ b/src/protocol/mod.rs @@ -15,6 +15,7 @@ use crate::protocol::ast::*; use crate::protocol::eval::*; use crate::protocol::input_source::*; use crate::protocol::parser::*; +use crate::protocol::type_table::*; /// A protocol description module pub struct Module { @@ -27,6 +28,7 @@ pub struct Module { pub struct ProtocolDescription { modules: Vec, heap: Heap, + types: TypeTable, pool: Mutex, } #[derive(Debug, Clone)] @@ -71,6 +73,7 @@ impl ProtocolDescription { return Ok(ProtocolDescription { modules, heap: parser.heap, + types: parser.type_table, pool: Mutex::new(parser.string_pool), }); } @@ -138,7 +141,7 @@ impl ProtocolDescription { let module_root = self.lookup_module_root(module_name).unwrap(); let root = &self.heap[module_root]; let def = root.get_definition_ident(&self.heap, identifier).unwrap(); - ComponentState { prompt: Prompt::new(&self.heap, def, ValueGroup::new_stack(args)) } + ComponentState { prompt: Prompt::new(&self.types, &self.heap, def, 0, ValueGroup::new_stack(args)) } } fn lookup_module_root(&self, module_name: &[u8]) -> Option { @@ -164,7 +167,7 @@ impl ComponentState { ) -> NonsyncBlocker { let mut context = EvalContext::Nonsync(context); loop { - let result = self.prompt.step(&pd.heap, &pd.modules, &mut context); + let result = self.prompt.step(&pd.types, &pd.heap, &pd.modules, &mut context); match result { Err(err) => { println!("Evaluation error:\n{}", err); @@ -177,7 +180,7 @@ impl ComponentState { EvalContinuation::SyncBlockStart => return NonsyncBlocker::SyncBlockStart, // Not possible to end sync block if never entered one EvalContinuation::SyncBlockEnd => unreachable!(), - EvalContinuation::NewComponent(definition_id, args) => { + EvalContinuation::NewComponent(definition_id, monomorph_idx, args) => { // Look up definition (TODO for now, assume it is a definition) let mut moved_ports = HashSet::new(); for arg in args.values.iter() { @@ -200,8 +203,7 @@ impl ComponentState { } } } - let h = &pd.heap; - let init_state = ComponentState { prompt: Prompt::new(h, definition_id, args) }; + let init_state = ComponentState { prompt: Prompt::new(&pd.types, &pd.heap, definition_id, monomorph_idx, args) }; context.new_component(moved_ports, init_state); // Continue stepping continue; @@ -222,7 +224,7 @@ impl ComponentState { ) -> SyncBlocker { let mut context = EvalContext::Sync(context); loop { - let result = self.prompt.step(&pd.heap, &pd.modules, &mut context); + let result = self.prompt.step(&pd.types, &pd.heap, &pd.modules, &mut context); match result { Err(err) => { println!("Evaluation error:\n{}", err); @@ -237,7 +239,7 @@ impl ComponentState { EvalContinuation::SyncBlockStart => unreachable!(), EvalContinuation::SyncBlockEnd => return SyncBlocker::SyncBlockEnd, // Not possible to create component in sync block - EvalContinuation::NewComponent(_, _) => unreachable!(), + EvalContinuation::NewComponent(_, _, _) => unreachable!(), EvalContinuation::BlockFires(port) => match port { Value::Output(port) => { return SyncBlocker::CouldntCheckFiring(port); diff --git a/src/protocol/parser/depth_visitor.rs b/src/protocol/parser/depth_visitor.rs index acc0fb04531d6f6aeab674504c6b229660785df1..90505722b27003ecc0317a6beff8d72c8b6cff13 100644 --- a/src/protocol/parser/depth_visitor.rs +++ b/src/protocol/parser/depth_visitor.rs @@ -644,333 +644,4 @@ impl Visitor for LinkStatements { fn visit_expression(&mut self, _h: &mut Heap, _expr: ExpressionId) -> VisitorResult { Ok(()) } -} - -pub(crate) struct AssignableExpressions { - assignable: bool, -} - -impl AssignableExpressions { - pub(crate) fn new() -> Self { - AssignableExpressions { assignable: false } - } - fn error(&self, position: InputPosition) -> VisitorResult { - Err((position, "Unassignable expression".to_string())) - } -} - -impl Visitor for AssignableExpressions { - fn visit_assignment_expression( - &mut self, - h: &mut Heap, - expr: AssignmentExpressionId, - ) -> VisitorResult { - if self.assignable { - self.error(h[expr].span.begin) - } else { - self.assignable = true; - self.visit_expression(h, h[expr].left)?; - self.assignable = false; - self.visit_expression(h, h[expr].right) - } - } - fn visit_conditional_expression( - &mut self, - h: &mut Heap, - expr: ConditionalExpressionId, - ) -> VisitorResult { - if self.assignable { - self.error(h[expr].span.begin) - } else { - recursive_conditional_expression(self, h, expr) - } - } - fn visit_binary_expression(&mut self, h: &mut Heap, expr: BinaryExpressionId) -> VisitorResult { - if self.assignable { - self.error(h[expr].span.begin) - } else { - recursive_binary_expression(self, h, expr) - } - } - fn visit_unary_expression(&mut self, h: &mut Heap, expr: UnaryExpressionId) -> VisitorResult { - if self.assignable { - self.error(h[expr].span.begin) - } else { - match h[expr].operation { - UnaryOperator::PostDecrement - | UnaryOperator::PreDecrement - | UnaryOperator::PostIncrement - | UnaryOperator::PreIncrement => { - self.assignable = true; - recursive_unary_expression(self, h, expr)?; - self.assignable = false; - Ok(()) - } - _ => recursive_unary_expression(self, h, expr), - } - } - } - fn visit_indexing_expression( - &mut self, - h: &mut Heap, - expr: IndexingExpressionId, - ) -> VisitorResult { - let old = self.assignable; - self.assignable = false; - recursive_indexing_expression(self, h, expr)?; - self.assignable = old; - Ok(()) - } - fn visit_slicing_expression( - &mut self, - h: &mut Heap, - expr: SlicingExpressionId, - ) -> VisitorResult { - let old = self.assignable; - self.assignable = false; - recursive_slicing_expression(self, h, expr)?; - self.assignable = old; - Ok(()) - } - fn visit_select_expression(&mut self, h: &mut Heap, expr: SelectExpressionId) -> VisitorResult { - if h[expr].field.is_length() && self.assignable { - return self.error(h[expr].span.begin); - } - let old = self.assignable; - self.assignable = false; - recursive_select_expression(self, h, expr)?; - self.assignable = old; - Ok(()) - } - fn visit_call_expression(&mut self, h: &mut Heap, expr: CallExpressionId) -> VisitorResult { - if self.assignable { - self.error(h[expr].span.begin) - } else { - recursive_call_expression(self, h, expr) - } - } - fn visit_constant_expression( - &mut self, - h: &mut Heap, - expr: LiteralExpressionId, - ) -> VisitorResult { - if self.assignable { - self.error(h[expr].span.begin) - } else { - Ok(()) - } - } - fn visit_variable_expression( - &mut self, - _h: &mut Heap, - _expr: VariableExpressionId, - ) -> VisitorResult { - Ok(()) - } -} - -pub(crate) struct IndexableExpressions { - indexable: bool, -} - -impl IndexableExpressions { - pub(crate) fn new() -> Self { - IndexableExpressions { indexable: false } - } - fn error(&self, position: InputPosition) -> VisitorResult { - Err((position, "Unindexable expression".to_string())) - } -} - -impl Visitor for IndexableExpressions { - fn visit_assignment_expression( - &mut self, - h: &mut Heap, - expr: AssignmentExpressionId, - ) -> VisitorResult { - if self.indexable { - self.error(h[expr].span.begin) - } else { - recursive_assignment_expression(self, h, expr) - } - } - fn visit_conditional_expression( - &mut self, - h: &mut Heap, - expr: ConditionalExpressionId, - ) -> VisitorResult { - let old = self.indexable; - self.indexable = false; - self.visit_expression(h, h[expr].test)?; - self.indexable = old; - self.visit_expression(h, h[expr].true_expression)?; - self.visit_expression(h, h[expr].false_expression) - } - fn visit_binary_expression(&mut self, h: &mut Heap, expr: BinaryExpressionId) -> VisitorResult { - if self.indexable && h[expr].operation != BinaryOperator::Concatenate { - self.error(h[expr].span.begin) - } else { - recursive_binary_expression(self, h, expr) - } - } - fn visit_unary_expression(&mut self, h: &mut Heap, expr: UnaryExpressionId) -> VisitorResult { - if self.indexable { - self.error(h[expr].span.begin) - } else { - recursive_unary_expression(self, h, expr) - } - } - fn visit_indexing_expression( - &mut self, - h: &mut Heap, - expr: IndexingExpressionId, - ) -> VisitorResult { - let old = self.indexable; - self.indexable = true; - self.visit_expression(h, h[expr].subject)?; - self.indexable = false; - self.visit_expression(h, h[expr].index)?; - self.indexable = old; - Ok(()) - } - fn visit_slicing_expression( - &mut self, - h: &mut Heap, - expr: SlicingExpressionId, - ) -> VisitorResult { - let old = self.indexable; - self.indexable = true; - self.visit_expression(h, h[expr].subject)?; - self.indexable = false; - self.visit_expression(h, h[expr].from_index)?; - self.visit_expression(h, h[expr].to_index)?; - self.indexable = old; - Ok(()) - } - fn visit_select_expression(&mut self, h: &mut Heap, expr: SelectExpressionId) -> VisitorResult { - let old = self.indexable; - self.indexable = false; - recursive_select_expression(self, h, expr)?; - self.indexable = old; - Ok(()) - } - fn visit_call_expression(&mut self, h: &mut Heap, expr: CallExpressionId) -> VisitorResult { - let old = self.indexable; - self.indexable = false; - recursive_call_expression(self, h, expr)?; - self.indexable = old; - Ok(()) - } - fn visit_constant_expression( - &mut self, - h: &mut Heap, - expr: LiteralExpressionId, - ) -> VisitorResult { - if self.indexable { - self.error(h[expr].span.begin) - } else { - Ok(()) - } - } -} - -pub(crate) struct SelectableExpressions { - selectable: bool, -} - -impl SelectableExpressions { - pub(crate) fn new() -> Self { - SelectableExpressions { selectable: false } - } - fn error(&self, position: InputPosition) -> VisitorResult { - Err((position, "Unselectable expression".to_string())) - } -} - -impl Visitor for SelectableExpressions { - fn visit_assignment_expression( - &mut self, - h: &mut Heap, - expr: AssignmentExpressionId, - ) -> VisitorResult { - // left-hand side of assignment can be skipped - let old = self.selectable; - self.selectable = false; - self.visit_expression(h, h[expr].right)?; - self.selectable = old; - Ok(()) - } - fn visit_conditional_expression( - &mut self, - h: &mut Heap, - expr: ConditionalExpressionId, - ) -> VisitorResult { - let old = self.selectable; - self.selectable = false; - self.visit_expression(h, h[expr].test)?; - self.selectable = old; - self.visit_expression(h, h[expr].true_expression)?; - self.visit_expression(h, h[expr].false_expression) - } - fn visit_binary_expression(&mut self, h: &mut Heap, expr: BinaryExpressionId) -> VisitorResult { - if self.selectable && h[expr].operation != BinaryOperator::Concatenate { - self.error(h[expr].span.begin) - } else { - recursive_binary_expression(self, h, expr) - } - } - fn visit_unary_expression(&mut self, h: &mut Heap, expr: UnaryExpressionId) -> VisitorResult { - if self.selectable { - self.error(h[expr].span.begin) - } else { - recursive_unary_expression(self, h, expr) - } - } - fn visit_indexing_expression( - &mut self, - h: &mut Heap, - expr: IndexingExpressionId, - ) -> VisitorResult { - let old = self.selectable; - self.selectable = false; - recursive_indexing_expression(self, h, expr)?; - self.selectable = old; - Ok(()) - } - fn visit_slicing_expression( - &mut self, - h: &mut Heap, - expr: SlicingExpressionId, - ) -> VisitorResult { - let old = self.selectable; - self.selectable = false; - recursive_slicing_expression(self, h, expr)?; - self.selectable = old; - Ok(()) - } - fn visit_select_expression(&mut self, h: &mut Heap, expr: SelectExpressionId) -> VisitorResult { - let old = self.selectable; - self.selectable = false; - recursive_select_expression(self, h, expr)?; - self.selectable = old; - Ok(()) - } - fn visit_call_expression(&mut self, h: &mut Heap, expr: CallExpressionId) -> VisitorResult { - let old = self.selectable; - self.selectable = false; - recursive_call_expression(self, h, expr)?; - self.selectable = old; - Ok(()) - } - fn visit_constant_expression( - &mut self, - h: &mut Heap, - expr: LiteralExpressionId, - ) -> VisitorResult { - if self.selectable { - self.error(h[expr].span.begin) - } else { - Ok(()) - } - } -} +} \ No newline at end of file diff --git a/src/protocol/parser/mod.rs b/src/protocol/parser/mod.rs index c7a2fead50166aa78e1fbdb3af8182aabd2a5298..102a9c2964506143a252ecff933439558a77573b 100644 --- a/src/protocol/parser/mod.rs +++ b/src/protocol/parser/mod.rs @@ -199,13 +199,13 @@ impl Parser { // Perform typechecking on all modules let mut queue = ResolveQueue::new(); for module in &mut self.modules { - let ctx = visitor::Ctx{ + let mut ctx = visitor::Ctx{ heap: &mut self.heap, module, symbols: &mut self.symbol_table, types: &mut self.type_table, }; - PassTyping::queue_module_definitions(&ctx, &mut queue); + PassTyping::queue_module_definitions(&mut ctx, &mut queue); }; while !queue.is_empty() { let top = queue.pop().unwrap(); @@ -248,9 +248,9 @@ impl Parser { LinkStatements::new().visit_protocol_description(h, pd)?; // BuildLabels::new().visit_protocol_description(h, pd)?; // ResolveLabels::new().visit_protocol_description(h, pd)?; - AssignableExpressions::new().visit_protocol_description(h, pd)?; - IndexableExpressions::new().visit_protocol_description(h, pd)?; - SelectableExpressions::new().visit_protocol_description(h, pd)?; + // AssignableExpressions::new().visit_protocol_description(h, pd)?; + // IndexableExpressions::new().visit_protocol_description(h, pd)?; + // SelectableExpressions::new().visit_protocol_description(h, pd)?; Ok(()) } diff --git a/src/protocol/parser/pass_definitions.rs b/src/protocol/parser/pass_definitions.rs index a3d214d775f672d7193b17863fb9c009718d3e85..f9f4826427962b1e0e90dbe34b7a94ea5c089dc0 100644 --- a/src/protocol/parser/pass_definitions.rs +++ b/src/protocol/parser/pass_definitions.rs @@ -838,7 +838,6 @@ impl PassDefinitions { declaration: None, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: Default::default() }); let assignment_expr_id = ctx.heap.alloc_assignment_expression(|this| AssignmentExpression{ this, @@ -848,7 +847,6 @@ impl PassDefinitions { right: initial_expr_id, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: Default::default(), }); let assignment_stmt_id = ctx.heap.alloc_expression_statement(|this| ExpressionStatement{ this, @@ -935,7 +933,6 @@ impl PassDefinitions { this, span, left, operation, right, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default(), }).upcast()) } else { Ok(expr) @@ -958,7 +955,6 @@ impl PassDefinitions { this, span, test, true_expression, false_expression, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default(), }).upcast()) } else { Ok(result) @@ -1142,7 +1138,6 @@ impl PassDefinitions { this, span, operation, expression, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default() }).upcast()) } else { self.consume_postfix_expression(module, iter, ctx) @@ -1176,7 +1171,6 @@ impl PassDefinitions { expression: result, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default() }).upcast(); } else if token == TokenKind::MinusMinus { result = ctx.heap.alloc_unary_expression(|this| UnaryExpression{ @@ -1185,7 +1179,6 @@ impl PassDefinitions { expression: result, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default() }).upcast(); } else if token == TokenKind::OpenSquare { let subject = result; @@ -1204,7 +1197,6 @@ impl PassDefinitions { this, span, subject, from_index, to_index, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default() }).upcast(); } else if Some(TokenKind::CloseSquare) == next { let end_span = consume_token(&module.source, iter, TokenKind::CloseSquare)?; @@ -1215,7 +1207,6 @@ impl PassDefinitions { index: from_index, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default() }).upcast(); } else { return Err(ParseError::new_error_str_at_pos( @@ -1225,20 +1216,12 @@ impl PassDefinitions { } else { debug_assert_eq!(token, TokenKind::Dot); let subject = result; - let (field_text, field_span) = consume_ident(&module.source, iter)?; - let field = if field_text == b"length" { - Field::Length - } else { - let value = ctx.pool.intern(field_text); - let identifier = Identifier{ value, span: field_span }; - Field::Symbolic(FieldSymbolic{ identifier, definition: None, field_idx: 0 }) - }; + let field_name = consume_ident_interned(&module.source, iter, ctx)?; result = ctx.heap.alloc_select_expression(|this| SelectExpression{ - this, span, subject, field, + this, span, subject, field_name, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default() }).upcast(); } @@ -1276,7 +1259,6 @@ impl PassDefinitions { value: Literal::Array(scoped_section.into_vec()), parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default(), }).upcast() } else if next == Some(TokenKind::Integer) { let (literal, span) = consume_integer_literal(&module.source, iter, &mut self.buffer)?; @@ -1286,7 +1268,6 @@ impl PassDefinitions { value: Literal::Integer(LiteralInteger{ unsigned_value: literal, negated: false }), parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default(), }).upcast() } else if next == Some(TokenKind::String) { let span = consume_string_literal(&module.source, iter, &mut self.buffer)?; @@ -1297,7 +1278,6 @@ impl PassDefinitions { value: Literal::String(interned), parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default(), }).upcast() } else if next == Some(TokenKind::Character) { let (character, span) = consume_character_literal(&module.source, iter)?; @@ -1307,7 +1287,6 @@ impl PassDefinitions { value: Literal::Character(character), parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default(), }).upcast() } else if next == Some(TokenKind::Ident) { // May be a variable, a type instantiation or a function call. If we @@ -1359,7 +1338,6 @@ impl PassDefinitions { }), parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default(), }).upcast() }, Definition::Enum(_) => { @@ -1378,7 +1356,6 @@ impl PassDefinitions { }), parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default() }).upcast() }, Definition::Union(_) => { @@ -1404,7 +1381,6 @@ impl PassDefinitions { }), parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default() }).upcast() }, Definition::Component(_) => { @@ -1420,7 +1396,6 @@ impl PassDefinitions { definition: target_definition_id, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default(), }).upcast() }, Definition::Function(function_definition) => { @@ -1451,7 +1426,6 @@ impl PassDefinitions { definition: target_definition_id, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default(), }).upcast() } } @@ -1483,7 +1457,6 @@ impl PassDefinitions { value, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default(), }).upcast() } else { // Not a builtin literal, but also not a known type. So we @@ -1518,7 +1491,6 @@ impl PassDefinitions { declaration: None, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default() }).upcast() } } @@ -1554,7 +1526,6 @@ impl PassDefinitions { this, span, left, operation, right, parent: ExpressionParent::None, unique_id_in_definition: -1, - concrete_type: ConcreteType::default() }).upcast(); } diff --git a/src/protocol/parser/pass_typing.rs b/src/protocol/parser/pass_typing.rs index 44fbded30803aaa72d198376daab03eca8ae31d0..2bfe03822957446486b6547415f5fedccf1c9d0c 100644 --- a/src/protocol/parser/pass_typing.rs +++ b/src/protocol/parser/pass_typing.rs @@ -823,13 +823,23 @@ impl DefinitionType { } } -#[derive(PartialEq, Eq)] pub(crate) struct ResolveQueueElement { pub(crate) root_id: RootId, pub(crate) definition_id: DefinitionId, pub(crate) monomorph_types: Vec, + pub(crate) reserved_monomorph_idx: i32, } +impl PartialEq for ResolveQueueElement { + fn eq(&self, other: &Self) -> bool { + return + self.root_id == other.root_id && + self.definition_id == other.definition_id && + self.monomorph_types == other.monomorph_types; + } +} +impl Eq for ResolveQueueElement {} + pub(crate) type ResolveQueue = Vec; #[derive(Clone)] @@ -837,7 +847,7 @@ struct InferenceExpression { expr_type: InferenceType, // result type from expression expr_id: ExpressionId, // expression that is evaluated field_or_monomorph_idx: i32, // index of field, of index of monomorph array in type table - var_or_extra_data_idx: i32, // index of extra data needed for inference + extra_data_idx: i32, // index of extra data needed for inference } impl Default for InferenceExpression { @@ -846,7 +856,7 @@ impl Default for InferenceExpression { expr_type: InferenceType::default(), expr_id: ExpressionId::new_invalid(), field_or_monomorph_idx: -1, - var_or_extra_data_idx: -1, + extra_data_idx: -1, } } } @@ -855,6 +865,7 @@ impl Default for InferenceExpression { /// that all expressions have the appropriate types. pub(crate) struct PassTyping { // Current definition we're typechecking. + reserved_idx: i32, definition_type: DefinitionType, poly_vars: Vec, @@ -876,6 +887,7 @@ pub(crate) struct PassTyping { // there is a different underlying architecture waiting to surface. struct ExtraData { expr_id: ExpressionId, // the expression with which this data is associated + definition_id: DefinitionId, // the definition, only used for user feedback /// Progression of polymorphic variables (if any) poly_vars: Vec, /// Progression of types of call arguments or struct members @@ -887,6 +899,7 @@ impl Default for ExtraData { fn default() -> Self { Self{ expr_id: ExpressionId::new_invalid(), + definition_id: DefinitionId::new_invalid(), poly_vars: Vec::new(), embedded: Vec::new(), returned: InferenceType::default(), @@ -916,6 +929,7 @@ impl VarData { impl PassTyping { pub(crate) fn new() -> Self { PassTyping { + reserved_idx: -1, definition_type: DefinitionType::Function(FunctionDefinitionId::new_invalid()), poly_vars: Vec::new(), stmt_buffer: Vec::with_capacity(STMT_BUFFER_INIT_CAPACITY), @@ -929,32 +943,27 @@ impl PassTyping { // TODO: @cleanup Unsure about this, maybe a pattern will arise after // a while. - pub(crate) fn queue_module_definitions(ctx: &Ctx, queue: &mut ResolveQueue) { + pub(crate) fn queue_module_definitions(ctx: &mut Ctx, queue: &mut ResolveQueue) { debug_assert_eq!(ctx.module.phase, ModuleCompilationPhase::ValidatedAndLinked); let root_id = ctx.module.root_id; let root = &ctx.heap.protocol_descriptions[root_id]; for definition_id in &root.definitions { let definition = &ctx.heap[*definition_id]; - match definition { - Definition::Function(definition) => { - if definition.poly_vars.is_empty() { - queue.push(ResolveQueueElement{ - root_id, - definition_id: *definition_id, - monomorph_types: Vec::new(), - }) - } - }, - Definition::Component(definition) => { - if definition.poly_vars.is_empty() { - queue.push(ResolveQueueElement{ - root_id, - definition_id: *definition_id, - monomorph_types: Vec::new(), - }) - } - }, - Definition::Enum(_) | Definition::Struct(_) | Definition::Union(_) => {}, + + let should_add_to_queue = match definition { + Definition::Function(definition) => definition.poly_vars.is_empty(), + Definition::Component(definition) => definition.poly_vars.is_empty(), + Definition::Enum(_) | Definition::Struct(_) | Definition::Union(_) => false, + }; + + if should_add_to_queue { + let reserved_idx = ctx.types.reserve_procedure_monomorph_index(definition_id, None); + queue.push(ResolveQueueElement{ + root_id, + definition_id: *definition_id, + monomorph_types: Vec::new(), + reserved_monomorph_idx: reserved_idx, + }) } } } @@ -965,8 +974,9 @@ impl PassTyping { // Visit the definition debug_assert_eq!(ctx.module.root_id, element.root_id); self.reset(); - self.poly_vars.clear(); - self.poly_vars.extend(element.monomorph_types.iter().cloned()); + debug_assert!(self.poly_vars.is_empty()); + self.reserved_idx = element.reserved_monomorph_idx; + self.poly_vars = element.monomorph_types; self.visit_definition(ctx, element.definition_id)?; // Keep resolving types @@ -975,6 +985,7 @@ impl PassTyping { } fn reset(&mut self) { + self.reserved_idx = -1; self.definition_type = DefinitionType::Function(FunctionDefinitionId::new_invalid()); self.poly_vars.clear(); self.stmt_buffer.clear(); @@ -1243,13 +1254,6 @@ impl Visitor2 for PassTyping { } fn visit_select_expr(&mut self, ctx: &mut Ctx, id: SelectExpressionId) -> VisitorResult { - // TODO: @Monomorph, this is a temporary hack, see other comments - let expr = &mut ctx.heap[id]; - if let Field::Symbolic(field) = &mut expr.field { - field.definition = None; - field.field_idx = 0; - } - let upcast_id = id.upcast(); self.insert_initial_expr_inference_type(ctx, upcast_id)?; @@ -1318,8 +1322,13 @@ impl Visitor2 for PassTyping { self.insert_initial_expr_inference_type(ctx, upcast_id)?; self.insert_initial_call_polymorph_data(ctx, id); - // TODO: @performance + // By default we set the polymorph idx for calls to 0. If the call ends + // up not being a polymorphic one, then we will select the default + // expression types in the type table let call_expr = &ctx.heap[id]; + self.expr_types[call_expr.unique_id_in_definition as usize].field_or_monomorph_idx = 0; + + // Visit all arguments for arg_expr_id in call_expr.arguments.clone() { self.visit_expr(ctx, arg_expr_id)?; } @@ -1354,18 +1363,44 @@ impl PassTyping { self.progress_expr(ctx, next_expr_idx)?; } - // We check if we have all the types we need. If we're typechecking a - // polymorphic procedure more than once, then we have already annotated - // the AST and have now performed typechecking for a different - // monomorph. In that case we just need to perform typechecking, no need - // to annotate the AST again. - let definition_id = match &self.definition_type { - DefinitionType::Component(id) => id.upcast(), - DefinitionType::Function(id) => id.upcast(), - }; + // Helper for transferring polymorphic variables to concrete types and + // checking if they're completely specified + fn poly_inference_to_concrete_type( + ctx: &Ctx, expr_id: ExpressionId, inference: &Vec + ) -> Result, ParseError> { + let mut concrete = Vec::with_capacity(inference.len()); + for (poly_idx, poly_type) in inference.iter().enumerate() { + if !poly_type.is_done { + let expr = &ctx.heap[expr_id]; + let definition = match expr { + Expression::Call(expr) => expr.definition, + Expression::Literal(expr) => match &expr.value { + Literal::Enum(lit) => lit.definition, + Literal::Union(lit) => lit.definition, + Literal::Struct(lit) => lit.definition, + _ => unreachable!() + }, + _ => unreachable!(), + }; + let poly_vars = ctx.heap[definition].poly_vars(); + return Err(ParseError::new_error_at_span( + &ctx.module.source, expr.span(), format!( + "could not fully infer the type of polymorphic variable '{}' of this expression (got '{}')", + poly_vars[poly_idx].value.as_str(), poly_type.display_name(&ctx.heap) + ) + )); + } - // TODO: Modify this to be correct and use a new array with types - let already_checked = ctx.types.get_base_definition(&definition_id).unwrap().has_any_monomorph(); + let mut concrete_type = ConcreteType::default(); + poly_type.write_concrete_type(&mut concrete_type); + concrete.push(concrete_type); + } + + Ok(concrete) + } + + // Inference is now done. But we may still have uninferred types. So we + // check for these. for infer_expr in self.expr_types.iter_mut() { let expr_type = &mut infer_expr.expr_type; if !expr_type.is_done { @@ -1383,98 +1418,85 @@ impl PassTyping { } } - if !already_checked { - let concrete_type = ctx.heap[infer_expr.expr_id].get_type_mut(); - expr_type.write_concrete_type(concrete_type); - } else { - if cfg!(debug_assertions) { - let mut concrete_type = ConcreteType::default(); - expr_type.write_concrete_type(&mut concrete_type); - debug_assert_eq!(*ctx.heap[infer_expr.expr_id].get_type(), concrete_type); - } - } - } - - // All types are fine - ctx.types.add_monomorph(&definition_id, self.poly_vars.clone()); + // Expression is fine, check if any extra data is attached + if infer_expr.extra_data_idx < 0 { continue; } - // Check all things we need to monomorphize - // TODO: Struct/enum/union monomorphization - for extra_data in self.extra_data.iter() { + // Extra data is attached, perform typechecking and transfer + // resolved information to the expression + let extra_data = &self.extra_data[infer_expr.extra_data_idx as usize]; if extra_data.poly_vars.is_empty() { continue; } - // Retrieve polymorph variable specification. Those of struct - // literals and those of procedure calls need to be fully inferred. - // The remaining ones (e.g. select expressions) allow partial - // inference of types, as long as the accessed field's type is - // fully inferred. - let needs_full_inference = match &ctx.heap[extra_data.expr_id] { - Expression::Call(_) => true, - Expression::Literal(_) => true, - _ => false - }; - - if needs_full_inference { - let mut monomorph_types = Vec::with_capacity(extra_data.poly_vars.len()); - for (poly_idx, poly_type) in extra_data.poly_vars.iter().enumerate() { - if !poly_type.is_done { - // TODO: Single clean function for function signatures and polyvars. - // TODO: Better error message - let expr = &ctx.heap[extra_data.expr_id]; - return Err(ParseError::new_error_at_span( - &ctx.module.source, expr.span(), format!( - "could not fully infer the type of polymorphic variable {} of this expression (got '{}')", - poly_idx, poly_type.display_name(&ctx.heap) - ) - )) + // Note that only call and literal expressions need full inference. + // Select expressions also use `extra_data`, but only for temporary + // storage of the struct type whose field it is selecting. + match &ctx.heap[extra_data.expr_id] { + Expression::Call(expr) => { + if expr.method != Method::UserFunction && expr.method != Method::UserComponent { + // Builtin function + continue; } - let mut concrete_type = ConcreteType::default(); - poly_type.write_concrete_type(&mut concrete_type); - monomorph_types.insert(poly_idx, concrete_type); - } + let definition_id = expr.definition; + let poly_types = poly_inference_to_concrete_type(ctx, extra_data.expr_id, &extra_data.poly_vars)?; - // Resolve to the appropriate expression and instantiate - // monomorphs. - match &ctx.heap[extra_data.expr_id] { - Expression::Call(call_expr) => { - // Add to type table if not yet typechecked - if call_expr.method == Method::UserFunction { - let definition_id = call_expr.definition; - if !ctx.types.has_monomorph(&definition_id, &monomorph_types) { - let root_id = ctx.types - .get_base_definition(&definition_id) - .unwrap() - .ast_root; - - // Pre-emptively add the monomorph to the type table, but - // we still need to perform typechecking on it - // TODO: Unsure about this, performance wise - let queue_element = ResolveQueueElement{ - root_id, - definition_id, - monomorph_types, - }; - if !queue.contains(&queue_element) { - queue.push(queue_element); - } - } - } - }, - Expression::Literal(lit_expr) => { - let definition_id = match &lit_expr.value { - Literal::Struct(literal) => &literal.definition, - Literal::Enum(literal) => &literal.definition, - Literal::Union(literal) => &literal.definition, - _ => unreachable!("post-inference monomorph for non-struct, non-enum, non-union literal") - }; - if !ctx.types.has_monomorph(definition_id, &monomorph_types) { - ctx.types.add_monomorph(definition_id, monomorph_types); + match ctx.types.get_procedure_monomorph_index(&definition_id, &poly_types) { + Some(reserved_idx) => { + // Already typechecked, or already put into the resolve queue + infer_expr.field_or_monomorph_idx = reserved_idx; + }, + None => { + // Not typechecked yet, so add an entry in the queue + let reserved_idx = ctx.types.reserve_procedure_monomorph_index(&definition_id, Some(poly_types.clone())); + infer_expr.field_or_monomorph_idx = reserved_idx; + queue.push(ResolveQueueElement{ + root_id: ctx.heap[definition_id].defined_in(), + definition_id, + monomorph_types: poly_types, + reserved_monomorph_idx: reserved_idx, + }); } - }, - _ => unreachable!("needs fully inference, but not a struct literal or call expression") + } + }, + Expression::Literal(expr) => { + let definition_id = match &expr.value { + Literal::Enum(lit) => lit.definition, + Literal::Union(lit) => lit.definition, + Literal::Struct(lit) => lit.definition, + _ => unreachable!(), + }; + + let poly_types = poly_inference_to_concrete_type(ctx, extra_data.expr_id, &extra_data.poly_vars)?; + let mono_index = ctx.types.add_data_monomorph(&definition_id, poly_types); + infer_expr.field_or_monomorph_idx = mono_index; + }, + Expression::Select(_) => { + debug_assert!(infer_expr.field_or_monomorph_idx >= 0); + }, + _ => { + unreachable!("handling extra data for expression {:?}", &ctx.heap[extra_data.expr_id]); } - } // else: was just a helper structure... + } + } + + // Every expression checked, and new monomorphs are queued. Transfer the + // expression information to the type table. + let definition_id = match &self.definition_type { + DefinitionType::Component(id) => id.upcast(), + DefinitionType::Function(id) => id.upcast(), + }; + + let target = ctx.types.get_procedure_expression_data_mut(&definition_id, self.reserved_idx); + debug_assert!(target.poly_args == self.poly_vars); + debug_assert!(target.expr_data.is_empty()); + + target.expr_data.reserve(self.expr_types.len()); + for infer_expr in self.expr_types.iter() { + let mut concrete = ConcreteType::default(); + infer_expr.expr_type.write_concrete_type(&mut concrete); + target.expr_data.push(MonomorphExpression{ + expr_type: concrete, + field_or_monomorph_idx: infer_expr.field_or_monomorph_idx + }); } Ok(()) @@ -1817,9 +1839,11 @@ impl PassTyping { let subject_id = ctx.heap[id].subject; let subject_expr_idx = ctx.heap[subject_id].get_unique_id_in_definition(); - let expr = &mut ctx.heap[id]; - let expr_idx = expr.unique_id_in_definition; - let extra_idx = self.expr_types[expr_idx as usize].var_or_extra_data_idx; + let select_expr = &ctx.heap[id]; + let expr_idx = select_expr.unique_id_in_definition; + + let infer_expr = &self.expr_types[expr_idx as usize]; + let extra_idx = infer_expr.extra_data_idx; fn determine_inference_type_instance<'a>(types: &'a TypeTable, infer_type: &InferenceType) -> Result, ()> { for part in &infer_type.parts { @@ -1846,132 +1870,118 @@ impl PassTyping { Ok(None) } - let (progress_subject, progress_expr) = match &mut expr.field { - Field::Length => { - let progress_subject = self.apply_forced_constraint(ctx, subject_id, &ARRAYLIKE_TEMPLATE)?; - let progress_expr = self.apply_forced_constraint(ctx, upcast_id, &INTEGERLIKE_TEMPLATE)?; + if infer_expr.field_or_monomorph_idx < 0 { + // We don't know the field or the definition it is pointing to yet + // Not yet known, check if we can determine it + let subject_type = &self.expr_types[subject_expr_idx as usize].expr_type; + let type_def = determine_inference_type_instance(&ctx.types, subject_type); - (progress_subject, progress_expr) - }, - Field::Symbolic(field) => { - // Retrieve the struct definition id and field index if possible - // and not previously determined - if field.definition.is_none() { - // Not yet known, check if we can determine it - let subject_type = &self.expr_types[subject_expr_idx as usize].expr_type; - let type_def = determine_inference_type_instance(&ctx.types, subject_type); - - match type_def { - Ok(Some(type_def)) => { - // Subject type is known, check if it is a - // struct and the field exists on the struct - let struct_def = if let DefinedTypeVariant::Struct(struct_def) = &type_def.definition { - struct_def - } else { - return Err(ParseError::new_error_at_span( - &ctx.module.source, field.identifier.span, format!( - "Can only apply field access to structs, got a subject of type '{}'", - subject_type.display_name(&ctx.heap) - ) - )); - }; - - for (field_def_idx, field_def) in struct_def.fields.iter().enumerate() { - if field_def.identifier == field.identifier { - // Set field definition and index - field.definition = Some(type_def.ast_definition); - field.field_idx = field_def_idx; - break; - } - } - - if field.definition.is_none() { - let field_span = field.identifier.span; - let ast_struct_def = ctx.heap[type_def.ast_definition].as_struct(); - return Err(ParseError::new_error_at_span( - &ctx.module.source, field_span, format!( - "this field does not exist on the struct '{}'", - ast_struct_def.identifier.value.as_str() - ) - )) - } - - // Encountered definition and field index for the - // first time - self.insert_initial_select_polymorph_data(ctx, id); - }, - Ok(None) => { - // Type of subject is not yet known, so we - // cannot make any progress yet - return Ok(()) - }, - Err(()) => { - return Err(ParseError::new_error_at_span( - &ctx.module.source, field.identifier.span, format!( - "Can only apply field access to structs, got a subject of type '{}'", - subject_type.display_name(&ctx.heap) - ) - )); + match type_def { + Ok(Some(type_def)) => { + // Subject type is known, check if it is a + // struct and the field exists on the struct + let struct_def = if let DefinedTypeVariant::Struct(struct_def) = &type_def.definition { + struct_def + } else { + return Err(ParseError::new_error_at_span( + &ctx.module.source, select_expr.field_name.span, format!( + "Can only apply field access to structs, got a subject of type '{}'", + subject_type.display_name(&ctx.heap) + ) + )); + }; + + let mut struct_def_id = None; + + for (field_def_idx, field_def) in struct_def.fields.iter().enumerate() { + if field_def.identifier == select_expr.field_name { + // Set field definition and index + let infer_expr = &mut self.expr_types[expr_idx as usize]; + infer_expr.field_or_monomorph_idx = field_def_idx as i32; + struct_def_id = Some(type_def.ast_definition); + break; } } + + if struct_def_id.is_none() { + let ast_struct_def = ctx.heap[type_def.ast_definition].as_struct(); + return Err(ParseError::new_error_at_span( + &ctx.module.source, select_expr.field_name.span, format!( + "this field does not exist on the struct '{}'", + ast_struct_def.identifier.value.as_str() + ) + )) + } + + // Encountered definition and field index for the + // first time + self.insert_initial_select_polymorph_data(ctx, id, struct_def_id.unwrap()); + }, + Ok(None) => { + // Type of subject is not yet known, so we + // cannot make any progress yet + return Ok(()) + }, + Err(()) => { + return Err(ParseError::new_error_at_span( + &ctx.module.source, select_expr.field_name.span, format!( + "Can only apply field access to structs, got a subject of type '{}'", + subject_type.display_name(&ctx.heap) + ) + )); } + } + } - // If here then field definition and index are known, and the - // initial type (based on the struct's definition) has been - // applied. - // Check to see if we can infer anything about the subject's and - // the field's polymorphic variables + // If here then field index is known, and the referenced struct type + // information is inserted into `extra_data`. Check to see if we can + // do some mutual inference. + let poly_data = &mut self.extra_data[extra_idx as usize]; + let mut poly_progress = HashSet::new(); - let poly_data = &mut self.extra_data[extra_idx as usize]; - let mut poly_progress = HashSet::new(); - - // Apply to struct's type - let signature_type: *mut _ = &mut poly_data.embedded[0]; - let subject_type: *mut _ = &mut self.expr_types[subject_expr_idx as usize].expr_type; + // Apply to struct's type + let signature_type: *mut _ = &mut poly_data.embedded[0]; + let subject_type: *mut _ = &mut self.expr_types[subject_expr_idx as usize].expr_type; - let (_, progress_subject) = Self::apply_equal2_signature_constraint( - ctx, upcast_id, Some(subject_id), poly_data, &mut poly_progress, - signature_type, 0, subject_type, 0 - )?; + let (_, progress_subject) = Self::apply_equal2_signature_constraint( + ctx, upcast_id, Some(subject_id), poly_data, &mut poly_progress, + signature_type, 0, subject_type, 0 + )?; - if progress_subject { - self.expr_queued.push_back(subject_expr_idx); - } - - // Apply to field's type - let signature_type: *mut _ = &mut poly_data.returned; - let expr_type: *mut _ = &mut self.expr_types[expr_idx as usize].expr_type; + if progress_subject { + self.expr_queued.push_back(subject_expr_idx); + } - let (_, progress_expr) = Self::apply_equal2_signature_constraint( - ctx, upcast_id, None, poly_data, &mut poly_progress, - signature_type, 0, expr_type, 0 - )?; + // Apply to field's type + let signature_type: *mut _ = &mut poly_data.returned; + let expr_type: *mut _ = &mut self.expr_types[expr_idx as usize].expr_type; - if progress_expr { - if let Some(parent_id) = ctx.heap[upcast_id].parent_expr_id() { - let parent_idx = ctx.heap[parent_id].get_unique_id_in_definition(); - self.expr_queued.push_back(parent_idx); - } - } + let (_, progress_expr) = Self::apply_equal2_signature_constraint( + ctx, upcast_id, None, poly_data, &mut poly_progress, + signature_type, 0, expr_type, 0 + )?; - // Reapply progress in polymorphic variables to struct's type - let signature_type: *mut _ = &mut poly_data.embedded[0]; - let subject_type: *mut _ = &mut self.expr_types[subject_expr_idx as usize].expr_type; - - let progress_subject = Self::apply_equal2_polyvar_constraint( - poly_data, &poly_progress, signature_type, subject_type - ); + if progress_expr { + if let Some(parent_id) = ctx.heap[upcast_id].parent_expr_id() { + let parent_idx = ctx.heap[parent_id].get_unique_id_in_definition(); + self.expr_queued.push_back(parent_idx); + } + } - let signature_type: *mut _ = &mut poly_data.returned; - let expr_type: *mut _ = &mut self.expr_types[expr_idx as usize].expr_type; + // Reapply progress in polymorphic variables to struct's type + let signature_type: *mut _ = &mut poly_data.embedded[0]; + let subject_type: *mut _ = &mut self.expr_types[subject_expr_idx as usize].expr_type; - let progress_expr = Self::apply_equal2_polyvar_constraint( - poly_data, &poly_progress, signature_type, expr_type - ); + let progress_subject = Self::apply_equal2_polyvar_constraint( + poly_data, &poly_progress, signature_type, subject_type + ); - (progress_subject, progress_expr) - } - }; + let signature_type: *mut _ = &mut poly_data.returned; + let expr_type: *mut _ = &mut self.expr_types[expr_idx as usize].expr_type; + + let progress_expr = Self::apply_equal2_polyvar_constraint( + poly_data, &poly_progress, signature_type, expr_type + ); if progress_subject { self.queue_expr(ctx, subject_id); } if progress_expr { self.queue_expr_parent(ctx, upcast_id); } @@ -1987,7 +1997,7 @@ impl PassTyping { let upcast_id = id.upcast(); let expr = &ctx.heap[id]; let expr_idx = expr.unique_id_in_definition; - let extra_idx = self.expr_types[expr_idx as usize].var_or_extra_data_idx; + let extra_idx = self.expr_types[expr_idx as usize].extra_data_idx; debug_log!("Literal expr: {}", upcast_id.index); debug_log!(" * Before:"); @@ -2283,7 +2293,7 @@ impl PassTyping { let upcast_id = id.upcast(); let expr = &ctx.heap[id]; let expr_idx = expr.unique_id_in_definition; - let extra_idx = self.expr_types[expr_idx as usize].var_or_extra_data_idx; + let extra_idx = self.expr_types[expr_idx as usize].extra_data_idx; debug_log!("Call expr '{}': {}", ctx.heap[expr.definition].identifier().value.as_str(), upcast_id.index); debug_log!(" * Before:"); @@ -2875,7 +2885,7 @@ impl PassTyping { if needs_extra_data { let extra_idx = self.extra_data.len() as i32; self.extra_data.push(ExtraData::default()); - infer_expr.var_or_extra_data_idx = extra_idx; + infer_expr.extra_data_idx = extra_idx; } } else { // We already have an entry @@ -2886,7 +2896,7 @@ impl PassTyping { return Err(self.construct_expr_type_error(ctx, expr_id, expr_id)); } - debug_assert!((infer_expr.var_or_extra_data_idx != -1) == needs_extra_data); + debug_assert!((infer_expr.extra_data_idx != -1) == needs_extra_data); } Ok(()) @@ -2905,7 +2915,7 @@ impl PassTyping { // map them back and forth to the polymorphic arguments of the function // we are calling. let call = &ctx.heap[call_id]; - let extra_data_idx = self.expr_types[call.unique_id_in_definition as usize].var_or_extra_data_idx; // TODO: @Temp + let extra_data_idx = self.expr_types[call.unique_id_in_definition as usize].extra_data_idx; // TODO: @Temp debug_assert!(extra_data_idx != -1, "insert initial call polymorph data, no preallocated ExtraData"); // Handle the polymorphic arguments (if there are any) @@ -2951,6 +2961,7 @@ impl PassTyping { self.extra_data[extra_data_idx as usize] = ExtraData{ expr_id: call_id.upcast(), + definition_id: call.definition, poly_vars: poly_args, embedded: parameter_types, returned: return_type @@ -2962,7 +2973,7 @@ impl PassTyping { ) { use InferenceTypePart as ITP; let literal = &ctx.heap[lit_id]; - let extra_data_idx = self.expr_types[literal.unique_id_in_definition as usize].var_or_extra_data_idx; // TODO: @Temp + let extra_data_idx = self.expr_types[literal.unique_id_in_definition as usize].extra_data_idx; // TODO: @Temp debug_assert!(extra_data_idx != -1, "initial struct polymorph data, but no preallocated ExtraData"); let literal = ctx.heap[lit_id].value.as_struct(); @@ -3013,6 +3024,7 @@ impl PassTyping { self.extra_data[extra_data_idx as usize] = ExtraData{ expr_id: lit_id.upcast(), + definition_id: literal.definition, poly_vars: poly_args, embedded: embedded_types, returned: return_type, @@ -3027,7 +3039,7 @@ impl PassTyping { ) { use InferenceTypePart as ITP; let literal = &ctx.heap[lit_id]; - let extra_data_idx = self.expr_types[literal.unique_id_in_definition as usize].var_or_extra_data_idx; // TODO: @Temp + let extra_data_idx = self.expr_types[literal.unique_id_in_definition as usize].extra_data_idx; // TODO: @Temp debug_assert!(extra_data_idx != -1, "initial enum polymorph data, but no preallocated ExtraData"); let literal = ctx.heap[lit_id].value.as_enum(); @@ -3059,6 +3071,7 @@ impl PassTyping { self.extra_data[extra_data_idx as usize] = ExtraData{ expr_id: lit_id.upcast(), + definition_id: literal.definition, poly_vars: poly_args, embedded: Vec::new(), returned: enum_type, @@ -3072,7 +3085,7 @@ impl PassTyping { ) { use InferenceTypePart as ITP; let literal = &ctx.heap[lit_id]; - let extra_data_idx = self.expr_types[literal.unique_id_in_definition as usize].var_or_extra_data_idx; // TODO: @Temp + let extra_data_idx = self.expr_types[literal.unique_id_in_definition as usize].extra_data_idx; // TODO: @Temp debug_assert!(extra_data_idx != -1, "initial union polymorph data, but no preallocated ExtraData"); let literal = ctx.heap[lit_id].value.as_union(); @@ -3119,6 +3132,7 @@ impl PassTyping { self.extra_data[extra_data_idx as usize] = ExtraData{ expr_id: lit_id.upcast(), + definition_id: literal.definition, poly_vars: poly_args, embedded, returned: union_type @@ -3128,19 +3142,18 @@ impl PassTyping { /// Inserts the extra polymorphic data struct. Assumes that the select /// expression's referenced (definition_id, field_idx) has been resolved. fn insert_initial_select_polymorph_data( - &mut self, ctx: &Ctx, select_id: SelectExpressionId + &mut self, ctx: &Ctx, select_id: SelectExpressionId, struct_def_id: DefinitionId ) { use InferenceTypePart as ITP; // Retrieve relevant data let expr = &ctx.heap[select_id]; - let extra_data_idx = self.expr_types[expr.unique_id_in_definition as usize].var_or_extra_data_idx; // TODO: @Temp + let expr_type = &self.expr_types[expr.unique_id_in_definition as usize]; + let field_idx = expr_type.field_or_monomorph_idx as usize; + let extra_data_idx = expr_type.extra_data_idx; // TODO: @Temp debug_assert!(extra_data_idx != -1, "initial select polymorph data, but no preallocated ExtraData"); - let field = expr.field.as_symbolic(); - let definition_id = field.definition.unwrap(); - let definition = ctx.heap[definition_id].as_struct(); - let field_idx = field.field_idx; + let definition = ctx.heap[struct_def_id].as_struct(); // Generate initial polyvar types and struct type // TODO: @Performance: we can immediately set the polyvars of the subject's struct type @@ -3148,7 +3161,7 @@ impl PassTyping { let mut poly_vars = Vec::with_capacity(num_poly_vars); let struct_parts_reserved = 1 + 2 * num_poly_vars; let mut struct_parts = Vec::with_capacity(struct_parts_reserved); - struct_parts.push(ITP::Instance(definition_id, num_poly_vars as u32)); + struct_parts.push(ITP::Instance(struct_def_id, num_poly_vars as u32)); for poly_idx in 0..num_poly_vars { poly_vars.push(InferenceType::new(true, false, vec![ @@ -3163,6 +3176,7 @@ impl PassTyping { let field_type = self.determine_inference_type_from_parser_type_elements(&definition.fields[field_idx].parser_type.elements, false); self.extra_data[extra_data_idx as usize] = ExtraData{ expr_id: select_id.upcast(), + definition_id: struct_def_id, poly_vars, embedded: vec![InferenceType::new(num_poly_vars != 0, num_poly_vars == 0, struct_parts)], returned: field_type @@ -3375,10 +3389,10 @@ impl PassTyping { } // Helper function to construct initial error - fn construct_main_error(ctx: &Ctx, poly_var_idx: u32, expr: &Expression) -> ParseError { + fn construct_main_error(ctx: &Ctx, poly_data: &ExtraData, poly_var_idx: u32, expr: &Expression) -> ParseError { match expr { Expression::Call(expr) => { - let (poly_var, func_name) = get_poly_var_and_definition_name(ctx, poly_var_idx, expr.definition); + let (poly_var, func_name) = get_poly_var_and_definition_name(ctx, poly_var_idx, poly_data.definition_id); return ParseError::new_error_at_span( &ctx.module.source, expr.span, format!( "Conflicting type for polymorphic variable '{}' of '{}'", @@ -3387,14 +3401,7 @@ impl PassTyping { ) }, Expression::Literal(expr) => { - let definition_id = match &expr.value { - Literal::Struct(v) => v.definition, - Literal::Enum(v) => v.definition, - Literal::Union(v) => v.definition, - _ => unreachable!(), - }; - - let (poly_var, type_name) = get_poly_var_and_definition_name(ctx, poly_var_idx, definition_id); + let (poly_var, type_name) = get_poly_var_and_definition_name(ctx, poly_var_idx, poly_data.definition_id); return ParseError::new_error_at_span( &ctx.module.source, expr.span, format!( "Conflicting type for polymorphic variable '{}' of instantiation of '{}'", @@ -3403,12 +3410,11 @@ impl PassTyping { ); }, Expression::Select(expr) => { - let field = expr.field.as_symbolic(); - let (poly_var, struct_name) = get_poly_var_and_definition_name(ctx, poly_var_idx, field.definition.unwrap()); + let (poly_var, struct_name) = get_poly_var_and_definition_name(ctx, poly_var_idx, poly_data.definition_id); return ParseError::new_error_at_span( &ctx.module.source, expr.span, format!( "Conflicting type for polymorphic variable '{}' while accessing field '{}' of '{}'", - poly_var, field.identifier.value.as_str(), struct_name + poly_var, expr.field_name.value.as_str(), struct_name ) ) } @@ -3450,7 +3456,7 @@ impl PassTyping { if let Some((poly_idx, section_a, section_b)) = has_poly_mismatch( &poly_data.returned, &poly_data.returned ) { - return construct_main_error(ctx, poly_idx, expr) + return construct_main_error(ctx, poly_data, poly_idx, expr) .with_info_at_span( &ctx.module.source, expr.span(), format!( "The {} inferred the conflicting types '{}' and '{}'", @@ -3469,7 +3475,7 @@ impl PassTyping { } if let Some((poly_idx, section_a, section_b)) = has_poly_mismatch(&arg_a, &arg_b) { - let error = construct_main_error(ctx, poly_idx, expr); + let error = construct_main_error(ctx, poly_data, poly_idx, expr); if arg_a_idx == arg_b_idx { // Same argument let arg = &ctx.heap[expr_args[arg_a_idx]]; @@ -3501,7 +3507,7 @@ impl PassTyping { // Check with return type if let Some((poly_idx, section_arg, section_ret)) = has_poly_mismatch(arg_a, &poly_data.returned) { let arg = &ctx.heap[expr_args[arg_a_idx]]; - return construct_main_error(ctx, poly_idx, expr) + return construct_main_error(ctx, poly_data, poly_idx, expr) .with_info_at_span( &ctx.module.source, arg.span(), format!( "This argument inferred it to '{}'", diff --git a/src/protocol/parser/type_table.rs b/src/protocol/parser/type_table.rs index 649c769175ef752c8fe538f991d152a8cf3cb655..597c4a116528ffda0d8e07b781d2897824e89f4c 100644 --- a/src/protocol/parser/type_table.rs +++ b/src/protocol/parser/type_table.rs @@ -50,28 +50,6 @@ pub struct DefinedType { pub(crate) definition: DefinedTypeVariant, pub(crate) poly_vars: Vec, pub(crate) is_polymorph: bool, - // TODO: @optimize - pub(crate) monomorphs: Vec>, -} - -impl DefinedType { - fn add_monomorph(&mut self, types: Vec) { - debug_assert!(!self.has_monomorph(&types), "monomorph already exists"); - self.monomorphs.push(types); - } - - pub(crate) fn has_any_monomorph(&self) -> bool { - !self.monomorphs.is_empty() - } - - pub(crate) fn has_monomorph(&self, types: &Vec) -> bool { - debug_assert_eq!(self.poly_vars.len(), types.len(), "mismatch in number of polymorphic types"); - for monomorph in &self.monomorphs { - if monomorph == types { return true; } - } - - return false; - } } pub enum DefinedTypeVariant { @@ -113,6 +91,48 @@ impl DefinedTypeVariant { _ => unreachable!("Cannot convert {} to union variant", self.type_class()) } } + + pub(crate) fn data_monomorphs(&self) -> &Vec { + use DefinedTypeVariant::*; + + match self { + Enum(v) => &v.monomorphs, + Union(v) => &v.monomorphs, + Struct(v) => &v.monomorphs, + _ => unreachable!("cannot get data monomorphs from {}", self.type_class()), + } + } + + pub(crate) fn data_monomorphs_mut(&mut self) -> &mut Vec { + use DefinedTypeVariant::*; + + match self { + Enum(v) => &mut v.monomorphs, + Union(v) => &mut v.monomorphs, + Struct(v) => &mut v.monomorphs, + _ => unreachable!("cannot get data monomorphs from {}", 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 { @@ -120,43 +140,60 @@ pub struct PolymorphicVariable { is_in_use: bool, // a polymorphic argument may be defined, but not used by the type definition } +/// Data associated with a monomorphized datatype +pub struct DataMonomorph { + pub poly_args: Vec, +} + +/// Data associated with a monomorphized procedure type. Has the wrong name, +/// because it will also be used to store expression data for a non-polymorphic +/// procedure. (in that case, there will only ever be one) +pub struct ProcedureMonomorph { + // Expression data for one particular monomorph + pub poly_args: Vec, + pub expr_data: Vec, +} + /// `EnumType` is the classical C/C++ enum type. It has various variants with /// an assigned integer value. The integer values may be user-defined, /// compiler-defined, or a mix of the two. If a user assigns the same enum /// value multiple times, we assume the user is an expert and we consider both /// variants to be equal to one another. pub struct EnumType { - pub(crate) variants: Vec, - pub(crate) representation: PrimitiveType, + pub variants: Vec, + pub representation: PrimitiveType, + pub monomorphs: Vec, } // TODO: Also support maximum u64 value pub struct EnumVariant { - pub(crate) identifier: Identifier, - pub(crate) value: i64, + pub identifier: Identifier, + pub value: i64, } /// `UnionType` is the algebraic datatype (or sum type, or discriminated union). /// A value is an element of the union, identified by its tag, and may contain /// a single subtype. pub struct UnionType { - pub(crate) variants: Vec, - pub(crate) tag_representation: PrimitiveType + pub variants: Vec, + pub tag_representation: PrimitiveType, + pub monomorphs: Vec, } pub struct UnionVariant { - pub(crate) identifier: Identifier, - pub(crate) embedded: Vec, // zero-length does not have embedded values - pub(crate) tag_value: i64, + pub identifier: Identifier, + pub embedded: Vec, // zero-length does not have embedded values + pub tag_value: i64, } pub struct StructType { - pub(crate) fields: Vec, + pub fields: Vec, + pub monomorphs: Vec, } pub struct StructField { - pub(crate) identifier: Identifier, - pub(crate) parser_type: ParserType, + pub identifier: Identifier, + pub parser_type: ParserType, } pub struct FunctionType { @@ -168,7 +205,7 @@ pub struct FunctionType { pub struct ComponentType { pub variant: ComponentVariant, pub arguments: Vec, - pub monomorphs: Vec, + pub monomorphs: Vec } pub struct FunctionArgument { @@ -176,11 +213,6 @@ pub struct FunctionArgument { parser_type: ParserType, } -pub struct ProcedureMonomorph { - // Expression data for one particular monomorph - expr_data: Vec, -} - /// Represents the data associated with a single expression after type inference /// for a monomorph (or just the normal expression types, if dealing with a /// non-polymorphic function/component). @@ -194,12 +226,6 @@ pub struct MonomorphExpression { pub(crate) field_or_monomorph_idx: i32, } -impl Default for MonomorphExpression { - fn default() -> Self { - Self{ expr_type: ConcreteType::default(), field_or_monomorph_idx: -1 } - } -} - //------------------------------------------------------------------------------ // Type table //------------------------------------------------------------------------------ @@ -254,7 +280,7 @@ enum ResolveResult { Unresolved(RootId, DefinitionId) } -pub(crate) struct TypeTable { +pub struct TypeTable { /// Lookup from AST DefinitionId to a defined type. Considering possible /// polymorphs is done inside the `DefinedType` struct. lookup: HashMap, @@ -317,26 +343,92 @@ impl TypeTable { self.lookup.get(&definition_id) } - /// Instantiates a monomorph for a given base definition. - pub(crate) fn add_monomorph(&mut self, definition_id: &DefinitionId, types: Vec) { - debug_assert!( - self.lookup.contains_key(definition_id), - "attempting to instantiate monomorph of definition unknown to type table" - ); + /// 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: &Vec) -> Option { + let def = self.lookup.get(definition_id).unwrap(); + if def.is_polymorph { + let monos = def.definition.procedure_monomorphs(); + return monos.iter() + .position(|v| v.poly_args == *types) + .map(|v| v as i32); + } else { + // We don't actually care about the types + let monos = def.definition.procedure_monomorphs(); + if monos.is_empty() { + return None + } else { + return Some(0) + } + } + } - let definition = self.lookup.get_mut(definition_id).unwrap(); - definition.add_monomorph(types); + /// 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]; } - /// Checks if a given definition already has a specific monomorph - pub(crate) fn has_monomorph(&mut self, definition_id: &DefinitionId, types: &Vec) -> bool { - debug_assert!( - self.lookup.contains_key(definition_id), - "attempting to check monomorph existence of definition unknown to type table" - ); + 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]; + } - let definition = self.lookup.get(definition_id).unwrap(); - definition.has_monomorph(types) + /// Reserves space for a monomorph of a polymorphic procedure. The index + /// will point into a (reserved) slot of the array of expression types. The + /// monomorph may NOT exist yet (because the reservation implies that we're + /// going to be performing typechecking on it, and we don't want to + /// check the same monomorph twice) + pub(crate) fn reserve_procedure_monomorph_index(&mut self, definition_id: &DefinitionId, types: Option>) -> i32 { + let def = self.lookup.get_mut(definition_id).unwrap(); + if let Some(types) = types { + // Expecting a polymorphic procedure + let monos = def.definition.procedure_monomorphs_mut(); + debug_assert!(def.is_polymorph); + debug_assert!(def.poly_vars.len() == types.len()); + debug_assert!(monos.iter().find(|v| v.poly_args == types).is_none()); + + let mono_idx = monos.len(); + monos.push(ProcedureMonomorph{ poly_args: types, expr_data: Vec::new() }); + + return mono_idx as i32; + } else { + // Expecting a non-polymorphic procedure + let monos = def.definition.procedure_monomorphs_mut(); + debug_assert!(!def.is_polymorph); + debug_assert!(def.poly_vars.is_empty()); + debug_assert!(monos.is_empty()); + + monos.push(ProcedureMonomorph{ poly_args: Vec::new(), expr_data: Vec::new() }); + + return 0; + } + } + + /// Adds a datatype polymorph to the type table. Will not add the + /// monomorph if it is already present, or if the type's polymorphic + /// variables are all unused. + pub(crate) fn add_data_monomorph(&mut self, definition_id: &DefinitionId, types: Vec) -> i32 { + let def = self.lookup.get_mut(definition_id).unwrap(); + if !def.is_polymorph { + // Not a polymorph, or polyvars are not used in type definition + return 0; + } + + let monos = def.definition.data_monomorphs_mut(); + if let Some(index) = monos.iter().position(|v| v.poly_args == types) { + // We already know about this monomorph + return index as i32; + } + + let index = monos.len(); + monos.push(DataMonomorph{ poly_args: types }); + return index as i32; } /// This function will resolve just the basic definition of the type, it @@ -425,11 +517,11 @@ impl TypeTable { ast_definition: definition_id, definition: DefinedTypeVariant::Enum(EnumType{ variants, - representation: Self::enum_tag_type(min_enum_value, max_enum_value) + representation: Self::enum_tag_type(min_enum_value, max_enum_value), + monomorphs: Vec::new(), }), poly_vars, is_polymorph: false, - monomorphs: Vec::new() }); Ok(true) @@ -504,10 +596,10 @@ impl TypeTable { definition: DefinedTypeVariant::Union(UnionType{ variants, tag_representation: Self::enum_tag_type(-1, tag_value), + monomorphs: Vec::new(), }), poly_vars, is_polymorph, - monomorphs: Vec::new() }); Ok(true) @@ -558,10 +650,10 @@ impl TypeTable { ast_definition: definition_id, definition: DefinedTypeVariant::Struct(StructType{ fields, + monomorphs: Vec::new(), }), poly_vars, is_polymorph, - monomorphs: Vec::new(), }); Ok(true) @@ -627,7 +719,6 @@ impl TypeTable { }), poly_vars, is_polymorph, - monomorphs: Vec::new(), }); Ok(true) @@ -687,7 +778,6 @@ impl TypeTable { }), poly_vars, is_polymorph, - monomorphs: Vec::new(), }); Ok(true) diff --git a/src/protocol/tests/eval_silly.rs b/src/protocol/tests/eval_silly.rs index 93695ad6b73d5de2d9cd567ea455a6b20bfd9ef4..3e3e4ddcba74959c366c307c1f648aa0b0261ae0 100644 --- a/src/protocol/tests/eval_silly.rs +++ b/src/protocol/tests/eval_silly.rs @@ -65,14 +65,13 @@ fn test_concatenate_operator() { #[test] fn test_slicing_magic() { - // TODO: Reimplement polymorphism, then retest with polymorphic types Tester::new_single_source_expect_ok("slicing", " - struct Holder { - u32[] left, - u32[] right, + struct Holder { + T[] left, + T[] right, } - func create_array(u32 first_index, u32 last_index) -> u32[] { + func create_array(T first_index, T last_index) -> T[] { auto result = {}; while (first_index < last_index) { // Absolutely rediculous, but we don't have builtin array functions yet... @@ -82,7 +81,7 @@ fn test_slicing_magic() { return result; } - func create_holder(u32 left_first, u32 left_last, u32 right_first, u32 right_last) -> Holder { + func create_holder(T left_first, T left_last, T right_first, T right_last) -> Holder { return Holder{ left: create_array(left_first, left_last), right: create_array(right_first, right_last) @@ -91,7 +90,7 @@ fn test_slicing_magic() { // Another silly thing, we first slice the full thing. Then subslice a single // element, then concatenate. We always return an array of two things. - func slicing_magic(Holder holder, u32 left_base, u32 left_amount, u32 right_base, u32 right_amount) -> u32[] { + func slicing_magic(Holder holder, u32 left_base, u32 left_amount, u32 right_base, u32 right_amount) -> T[] { auto left = holder.left[left_base..left_base + left_amount]; auto right = holder.right[right_base..right_base + right_amount]; return left[0..1] @ right[0..1]; diff --git a/src/protocol/tests/parser_monomorphs.rs b/src/protocol/tests/parser_monomorphs.rs index d4d0ee270ead1db7ba6feefbb0c88b91478a2b40..c38ada857574258cfd6076e26734c3af70b5cec6 100644 --- a/src/protocol/tests/parser_monomorphs.rs +++ b/src/protocol/tests/parser_monomorphs.rs @@ -52,6 +52,9 @@ fn test_enum_monomorphs() { .assert_num_monomorphs(0); }); + // Note for reader: because the enum doesn't actually use the polymorphic + // variable, we expect to have 0 polymorphs: the type only has to be laid + // out once. Tester::new_single_source_expect_ok( "single polymorph", " @@ -65,10 +68,7 @@ fn test_enum_monomorphs() { } " ).for_enum("Answer", |e| { e - .assert_num_monomorphs(3) - .assert_has_monomorph("s8") - .assert_has_monomorph("s32") - .assert_has_monomorph("Answer>"); + .assert_num_monomorphs(0); }); } diff --git a/src/protocol/tests/utils.rs b/src/protocol/tests/utils.rs index 122cd003914927bf1ad7474b0ae13a8080a6a792..5dc895e2375c035bc85e36c53d9a2968a2f44ae8 100644 --- a/src/protocol/tests/utils.rs +++ b/src/protocol/tests/utils.rs @@ -5,7 +5,7 @@ use crate::protocol::{ input_source::*, parser::{ Parser, - type_table::TypeTable, + type_table::{TypeTable, DefinedTypeVariant}, symbol_table::SymbolTable, token_parsing::*, }, @@ -644,10 +644,10 @@ impl<'a> FunctionTester<'a> { use crate::protocol::*; use crate::runtime::*; - let mut prompt = Prompt::new(&self.ctx.heap, self.def.this.upcast(), ValueGroup::new_stack(Vec::new())); + let mut prompt = Prompt::new(&self.ctx.types, &self.ctx.heap, self.def.this.upcast(), 0, ValueGroup::new_stack(Vec::new())); let mut call_context = EvalContext::None; loop { - let result = prompt.step(&self.ctx.heap, &self.ctx.modules, &mut call_context); + let result = prompt.step(&self.ctx.types, &self.ctx.heap, &self.ctx.modules, &mut call_context); match result { Ok(EvalContinuation::Stepping) => {}, _ => return (prompt, result), @@ -687,12 +687,14 @@ impl<'a> VariableTester<'a> { } pub(crate) fn assert_concrete_type(self, expected: &str) -> Self { - let mut serialized = String::new(); + // Lookup concrete type in type table + let mono_data = self.ctx.types.get_procedure_expression_data(&self.definition_id, 0); let lhs = self.ctx.heap[self.assignment.left].as_variable(); - serialize_concrete_type( - &mut serialized, self.ctx.heap, self.definition_id, - &lhs.concrete_type - ); + let concrete_type = &mono_data.expr_data[lhs.unique_id_in_definition as usize].expr_type; + + // Serialize and check + let mut serialized = String::new(); + serialize_concrete_type(&mut serialized, self.ctx.heap, self.definition_id, concrete_type); assert_eq!( expected, &serialized, @@ -721,11 +723,14 @@ 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 expr_index = self.expr.get_unique_id_in_definition(); + let concrete_type = &mono_data.expr_data[expr_index as usize].expr_type; + + // Serialize and check type let mut serialized = String::new(); - serialize_concrete_type( - &mut serialized, self.ctx.heap, self.definition_id, - self.expr.get_type() - ); + serialize_concrete_type(&mut serialized, self.ctx.heap, self.definition_id, concrete_type); assert_eq!( expected, &serialized, @@ -863,38 +868,75 @@ impl<'a> ErrorTester<'a> { // Generic utilities //------------------------------------------------------------------------------ -fn has_equal_num_monomorphs<'a>(ctx: TestCtx<'a>, num: usize, definition_id: DefinitionId) -> (bool, usize) { +fn has_equal_num_monomorphs(ctx: TestCtx, num: usize, definition_id: DefinitionId) -> (bool, usize) { + use DefinedTypeVariant::*; + let type_def = ctx.types.get_base_definition(&definition_id).unwrap(); - let num_on_type = type_def.monomorphs.len(); - + 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(), + }; + (num_on_type == num, num_on_type) } -fn has_monomorph<'a>(ctx: TestCtx<'a>, definition_id: DefinitionId, serialized_monomorph: &str) -> (bool, String) { +fn has_monomorph(ctx: TestCtx, definition_id: DefinitionId, serialized_monomorph: &str) -> (bool, String) { + use DefinedTypeVariant::*; + let type_def = ctx.types.get_base_definition(&definition_id).unwrap(); + // Note: full_buffer is just for error reporting let mut full_buffer = String::new(); let mut has_match = false; - full_buffer.push('['); - for (monomorph_idx, monomorph) in type_def.monomorphs.iter().enumerate() { + + let serialize_monomorph = |monomorph: &Vec| -> String { let mut buffer = String::new(); - for (element_idx, monomorph_element) in monomorph.iter().enumerate() { - if element_idx != 0 { buffer.push(';'); } - serialize_concrete_type(&mut buffer, ctx.heap, definition_id, monomorph_element); + for (element_idx, element) in monomorph.iter().enumerate() { + if element_idx != 0 { + buffer.push(';'); + } + serialize_concrete_type(&mut buffer, ctx.heap, definition_id, element); } - if buffer == serialized_monomorph { - // Found an exact match - has_match = true; - } + buffer + }; - if monomorph_idx != 0 { + full_buffer.push('['); + let mut append_to_full_buffer = |buffer: String| { + if buffer.len() == 1 { full_buffer.push_str(", "); } full_buffer.push('"'); full_buffer.push_str(&buffer); full_buffer.push('"'); + }; + + match &type_def.definition { + Enum(_) | Union(_) | Struct(_) => { + let monomorphs = type_def.definition.data_monomorphs(); + for monomorph in monomorphs.iter() { + let buffer = serialize_monomorph(&monomorph.poly_args); + if buffer == serialized_monomorph { + has_match = true; + } + append_to_full_buffer(buffer); + } + }, + Function(_) | Component(_) => { + let monomorphs = type_def.definition.procedure_monomorphs(); + for monomorph in monomorphs.iter() { + let buffer = serialize_monomorph(&monomorph.poly_args); + if buffer == serialized_monomorph { + has_match = true; + } + append_to_full_buffer(buffer); + } + } } + full_buffer.push(']'); (has_match, full_buffer)