From b6fc9e625da1bee6d7accd8f3412669aeca1e9a3 2022-02-22 16:56:47 From: mh Date: 2022-02-22 16:56:47 Subject: [PATCH] WIP: Remove old expr-based inferencing code --- diff --git a/src/protocol/parser/pass_typing.rs b/src/protocol/parser/pass_typing.rs index aa9bdd04553257001f9173bea47edcf384bc7d10..50118db8a453a2676beacabe0846c6d440c4aef2 100644 --- a/src/protocol/parser/pass_typing.rs +++ b/src/protocol/parser/pass_typing.rs @@ -1025,16 +1025,14 @@ pub(crate) struct PassTyping { bool_buffer: ScopedBuffer, index_buffer: ScopedBuffer, poly_progress_buffer: ScopedBuffer, - temp_type_parts: Vec, // Mapping from parser type to inferred type. We attempt to continue to // specify these types until we're stuck or we've fully determined the type. - var_types: HashMap, // types of variables infer_nodes: Vec, // will be transferred to type table at end poly_data: Vec, // data for polymorph inference var_data: Vec, // Keeping track of which expressions need to be reinferred because the // expressions they're linked to made progression on an associated type - expr_queued: DequeSet, + node_queued: DequeSet, } /// Generic struct that is used to store inferred types associated with @@ -1055,17 +1053,6 @@ struct PolyData { returned: InferenceType, } -impl Default for PolyData { - fn default() -> Self { - Self { - definition_id: DefinitionId::new_invalid(), - poly_vars: Vec::new(), - associated: Vec::new(), - returned: InferenceType::default(), - } - } -} - #[derive(Clone, Copy)] enum PolyDataTypeIndex { Associated(usize), // indexes into `PolyData.associated` @@ -1088,25 +1075,6 @@ impl PolyData { } } -struct VarDataDeprecated { - /// Type of the variable - var_type: InferenceType, - /// VariableExpressions that use the variable - used_at: Vec, - /// For channel statements we link to the other variable such that when one - /// channel's interior type is resolved, we can also resolve the other one. - linked_var: Option, -} - -impl VarDataDeprecated { - fn new_channel(var_type: InferenceType, other_port: VariableId) -> Self { - Self{ var_type, used_at: Vec::new(), linked_var: Some(other_port) } - } - fn new_local(var_type: InferenceType) -> Self { - Self{ var_type, used_at: Vec::new(), linked_var: None } - } -} - struct VarData { var_id: VariableId, var_type: InferenceType, @@ -1125,11 +1093,12 @@ impl PassTyping { expr_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_LARGE), stmt_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_LARGE), bool_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL), + index_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL), poly_progress_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL), - var_types: HashMap::new(), - infer_nodes: Vec::new(), - poly_data: Vec::new(), - expr_queued: DequeSet::new(), + infer_nodes: Vec::with_capacity(BUFFER_INIT_CAP_LARGE), + poly_data: Vec::with_capacity(BUFFER_INIT_CAP_SMALL), + var_data: Vec::with_capacity(BUFFER_INIT_CAP_SMALL), + node_queued: DequeSet::new(), } } @@ -1199,10 +1168,12 @@ impl PassTyping { self.reserved_type_id = TypeId::new_invalid(); self.definition_type = DefinitionType::Function(FunctionDefinitionId::new_invalid()); self.poly_vars.clear(); - self.var_types.clear(); + self.parent_index = None; + self.infer_nodes.clear(); self.poly_data.clear(); - self.expr_queued.clear(); + self.var_data.clear(); + self.node_queued.clear(); } } @@ -1244,7 +1215,12 @@ impl PassTyping { let param = &ctx.heap[param_id]; let var_type = self.determine_inference_type_from_parser_type_elements(¶m.parser_type.elements, true); debug_assert!(var_type.is_done, "expected component arguments to be concrete types"); - self.var_types.insert(param_id, VarDataDeprecated::new_local(var_type)); + self.var_data.push(VarData{ + var_id: param_id, + var_type, + used_at: Vec::new(), + linked_var: None + }); } section.forget(); @@ -1285,7 +1261,12 @@ impl PassTyping { let param = &ctx.heap[param_id]; let var_type = self.determine_inference_type_from_parser_type_elements(¶m.parser_type.elements, true); debug_assert!(var_type.is_done, "expected function arguments to be concrete types"); - self.var_types.insert(param_id, VarDataDeprecated::new_local(var_type)); + self.var_data.push(VarData{ + var_id: param_id, + var_type, + used_at: Vec::new(), + linked_var: None + }) } section.forget(); @@ -1978,30 +1959,28 @@ impl PassTyping { fn resolve_types(&mut self, ctx: &mut Ctx, queue: &mut ResolveQueue) -> Result<(), ParseError> { // Keep inferring until we can no longer make any progress - while !self.expr_queued.is_empty() { + while !self.node_queued.is_empty() { // Make as much progress as possible without forced integer // inference. - while !self.expr_queued.is_empty() { - let next_expr_idx = self.expr_queued.pop_front().unwrap(); + while !self.node_queued.is_empty() { + let next_expr_idx = self.node_queued.pop_front().unwrap(); self.progress_expr(ctx, next_expr_idx)?; } // Nothing is queued anymore. However we might have integer literals // whose type cannot be inferred. For convenience's sake we'll // infer these to be s32. - for (infer_expr_idx, infer_expr) in self.infer_nodes.iter_mut().enumerate() { - let expr_type = &mut infer_expr.expr_type; + for (infer_node_index, infer_node) in self.infer_nodes.iter_mut().enumerate() { + let expr_type = &mut infer_node.expr_type; if !expr_type.is_done && expr_type.parts.len() == 1 && expr_type.parts[0] == InferenceTypePart::IntegerLike { // Force integer type to s32 expr_type.parts[0] = InferenceTypePart::SInt32; expr_type.is_done = true; // Requeue expression (and its parent, if it exists) - self.expr_queued.push_back(infer_expr_idx as i32); - - if let Some(parent_expr) = ctx.heap[infer_expr.expr_id].parent_expr_id() { - let parent_idx = ctx.heap[parent_expr].get_unique_id_in_definition(); - self.expr_queued.push_back(parent_idx); + self.node_queued.push_back(infer_node_index); + if let Some(parent_node_index) = infer_node.parent_index { + self.expr_queued(parent_node_index); } } } @@ -2156,8 +2135,8 @@ impl PassTyping { target.arg_types.reserve(procedure_arguments.len()); for argument_id in procedure_arguments { let mut concrete = ConcreteType::default(); - let argument_type = self.var_types.get(argument_id).unwrap(); - argument_type.var_type.write_concrete_type(&mut concrete); + let var_data = self.var_data.iter().find(|v| v.var_id == *argument_id).unwrap(); + var_data.var_type.write_concrete_type(&mut concrete); target.arg_types.push(concrete); } @@ -2182,7 +2161,7 @@ impl PassTyping { let node = &self.infer_nodes[node_index]; match &node.inference_rule { IR::Noop => - return Ok(()), + unreachable!(), IR::MonoTemplate(_) => self.progress_inference_rule_mono_template(ctx, node_index), IR::BiEqual(_) => @@ -3000,1285 +2979,16 @@ impl PassTyping { } } - fn progress_expr(&mut self, ctx: &mut Ctx, idx: i32) -> Result<(), ParseError> { - let id = self.infer_nodes[idx as usize].expr_id; - match &ctx.heap[id] { - Expression::Assignment(expr) => { - let id = expr.this; - self.progress_assignment_expr(ctx, id) - }, - Expression::Binding(expr) => { - let id = expr.this; - self.progress_binding_expr(ctx, id) - }, - Expression::Conditional(expr) => { - let id = expr.this; - self.progress_conditional_expr(ctx, id) - }, - Expression::Binary(expr) => { - let id = expr.this; - self.progress_binary_expr(ctx, id) - }, - Expression::Unary(expr) => { - let id = expr.this; - self.progress_unary_expr(ctx, id) - }, - Expression::Indexing(expr) => { - let id = expr.this; - self.progress_indexing_expr(ctx, id) - }, - Expression::Slicing(expr) => { - let id = expr.this; - self.progress_slicing_expr(ctx, id) - }, - Expression::Select(expr) => { - let id = expr.this; - self.progress_select_expr(ctx, id) - }, - Expression::Literal(expr) => { - let id = expr.this; - self.progress_literal_expr(ctx, id) - }, - Expression::Cast(expr) => { - let id = expr.this; - self.progress_cast_expr(ctx, id) - }, - Expression::Call(expr) => { - let id = expr.this; - self.progress_call_expr(ctx, id) - }, - Expression::Variable(expr) => { - let id = expr.this; - self.progress_variable_expr(ctx, id) - } - } - } - - fn progress_assignment_expr(&mut self, ctx: &mut Ctx, infer_index: InferNodeIndex) -> Result<(), ParseError> { - use AssignmentOperator as AO; - - - let expr = &ctx.heap[id]; - let arg1_expr_id = expr.left; - let arg2_expr_id = expr.right; - - debug_log!("Assignment expr '{:?}': {}", expr.operation, upcast_id.index); - debug_log!(" * Before:"); - debug_log!(" - Arg1 type: {}", self.debug_get_display_name(ctx, arg1_expr_id)); - debug_log!(" - Arg2 type: {}", self.debug_get_display_name(ctx, arg2_expr_id)); - debug_log!(" - Expr type: {}", self.debug_get_display_name(ctx, upcast_id)); - - // Assignment does not return anything (it operates like a statement) - let progress_expr = self.apply_forced_constraint(ctx, upcast_id, &VOID_TEMPLATE)?; - - // Apply forced constraint to LHS value - let progress_forced = match expr.operation { - AO::Set => - false, - AO::Concatenated => - self.apply_template_constraint(ctx, arg1_expr_id, &ARRAYLIKE_TEMPLATE)?, - AO::Multiplied | AO::Divided | AO::Added | AO::Subtracted => - self.apply_template_constraint(ctx, arg1_expr_id, &NUMBERLIKE_TEMPLATE)?, - AO::Remained | AO::ShiftedLeft | AO::ShiftedRight | - AO::BitwiseAnded | AO::BitwiseXored | AO::BitwiseOred => - self.apply_template_constraint(ctx, arg1_expr_id, &INTEGERLIKE_TEMPLATE)?, - }; - - let (progress_arg1, progress_arg2) = self.apply_equal2_constraint( - ctx, upcast_id, arg1_expr_id, 0, arg2_expr_id, 0 - )?; - - debug_log!(" * After:"); - debug_log!(" - Arg1 type [{}]: {}", progress_forced || progress_arg1, self.debug_get_display_name(ctx, arg1_expr_id)); - debug_log!(" - Arg2 type [{}]: {}", progress_arg2, self.debug_get_display_name(ctx, arg2_expr_id)); - debug_log!(" - Expr type [{}]: {}", progress_expr, self.debug_get_display_name(ctx, upcast_id)); - - - if progress_expr { self.queue_node_parent(ctx, upcast_id); } - if progress_forced || progress_arg1 { self.queue_expr(ctx, arg1_expr_id); } - if progress_arg2 { self.queue_expr(ctx, arg2_expr_id); } - - Ok(()) - } - - fn progress_binding_expr(&mut self, ctx: &mut Ctx, id: BindingExpressionId) -> Result<(), ParseError> { - let upcast_id = id.upcast(); - let binding_expr = &ctx.heap[id]; - let bound_from_id = binding_expr.bound_from; - let bound_to_id = binding_expr.bound_to; - - // Output is always a boolean. The two arguments should be of equal - // type. - let progress_expr = self.apply_forced_constraint(ctx, upcast_id, &BOOL_TEMPLATE)?; - let (progress_from, progress_to) = self.apply_equal2_constraint(ctx, upcast_id, bound_from_id, 0, bound_to_id, 0)?; - - if progress_expr { self.queue_node_parent(ctx, upcast_id); } - if progress_from { self.queue_expr(ctx, bound_from_id); } - if progress_to { self.queue_expr(ctx, bound_to_id); } - - Ok(()) - } - - fn progress_conditional_expr(&mut self, ctx: &mut Ctx, id: ConditionalExpressionId) -> Result<(), ParseError> { - // Note: test expression type is already enforced - let upcast_id = id.upcast(); - let expr = &ctx.heap[id]; - let arg1_expr_id = expr.true_expression; - let arg2_expr_id = expr.false_expression; - - debug_log!("Conditional expr: {}", upcast_id.index); - debug_log!(" * Before:"); - debug_log!(" - Arg1 type: {}", self.debug_get_display_name(ctx, arg1_expr_id)); - debug_log!(" - Arg2 type: {}", self.debug_get_display_name(ctx, arg2_expr_id)); - debug_log!(" - Expr type: {}", self.debug_get_display_name(ctx, upcast_id)); - - // I keep confusing myself: this applies equality of types between the - // condition branches' types, and the result from the conditional - // expression, because the result from the conditional is one of the - // branches. - let (progress_expr, progress_arg1, progress_arg2) = self.apply_equal3_constraint( - ctx, upcast_id, arg1_expr_id, arg2_expr_id, 0 - )?; - - debug_log!(" * After:"); - debug_log!(" - Arg1 type [{}]: {}", progress_arg1, self.debug_get_display_name(ctx, arg1_expr_id)); - debug_log!(" - Arg2 type [{}]: {}", progress_arg2, self.debug_get_display_name(ctx, arg2_expr_id)); - debug_log!(" - Expr type [{}]: {}", progress_expr, self.debug_get_display_name(ctx, upcast_id)); - - if progress_expr { self.queue_node_parent(ctx, upcast_id); } - if progress_arg1 { self.queue_expr(ctx, arg1_expr_id); } - if progress_arg2 { self.queue_expr(ctx, arg2_expr_id); } - - Ok(()) - } - - fn progress_binary_expr(&mut self, ctx: &mut Ctx, id: BinaryExpressionId) -> Result<(), ParseError> { - // Note: our expression type might be fixed by our parent, but we still - // need to make sure it matches the type associated with our operation. - use BinaryOperator as BO; - - let upcast_id = id.upcast(); - let expr = &ctx.heap[id]; - let arg1_id = expr.left; - let arg2_id = expr.right; - - debug_log!("Binary expr '{:?}': {}", expr.operation, upcast_id.index); - debug_log!(" * Before:"); - debug_log!(" - Arg1 type: {}", self.debug_get_display_name(ctx, arg1_id)); - debug_log!(" - Arg2 type: {}", self.debug_get_display_name(ctx, arg2_id)); - debug_log!(" - Expr type: {}", self.debug_get_display_name(ctx, upcast_id)); - - let (progress_expr, progress_arg1, progress_arg2) = match expr.operation { - BO::Concatenate => { - // Two cases: if one of the arguments or the output type is a - // string, then all must be strings. Otherwise the arguments - // must be arraylike and the output will be an array. - let (expr_is_str, expr_is_not_str) = self.type_is_certainly_or_certainly_not_string(ctx, upcast_id); - let (arg1_is_str, arg1_is_not_str) = self.type_is_certainly_or_certainly_not_string(ctx, arg1_id); - let (arg2_is_str, arg2_is_not_str) = self.type_is_certainly_or_certainly_not_string(ctx, arg2_id); - - let someone_is_str = expr_is_str || arg1_is_str || arg2_is_str; - let someone_is_not_str = expr_is_not_str || arg1_is_not_str || arg2_is_not_str; - - // Note: this statement is an expression returning the progression bools - if someone_is_str { - // One of the arguments is a string, then all must be strings - self.apply_equal3_constraint(ctx, upcast_id, arg1_id, arg2_id, 0)? - } else { - let progress_expr = if someone_is_not_str { - // Output must be a normal array - self.apply_template_constraint(ctx, upcast_id, &ARRAY_TEMPLATE)? - } else { - // Output may still be anything - self.apply_template_constraint(ctx, upcast_id, &ARRAYLIKE_TEMPLATE)? - }; - - let progress_arg1 = self.apply_template_constraint(ctx, arg1_id, &ARRAYLIKE_TEMPLATE)?; - let progress_arg2 = self.apply_template_constraint(ctx, arg2_id, &ARRAYLIKE_TEMPLATE)?; - - // If they're all arraylike, then we want the subtype to match - let (subtype_expr, subtype_arg1, subtype_arg2) = - self.apply_equal3_constraint(ctx, upcast_id, arg1_id, arg2_id, 1)?; - - (progress_expr || subtype_expr, progress_arg1 || subtype_arg1, progress_arg2 || subtype_arg2) - } - }, - BO::LogicalAnd | BO::LogicalOr => { - // Forced boolean on all - let progress_expr = self.apply_forced_constraint(ctx, upcast_id, &BOOL_TEMPLATE)?; - let progress_arg1 = self.apply_forced_constraint(ctx, arg1_id, &BOOL_TEMPLATE)?; - let progress_arg2 = self.apply_forced_constraint(ctx, arg2_id, &BOOL_TEMPLATE)?; - - (progress_expr, progress_arg1, progress_arg2) - }, - BO::BitwiseOr | BO::BitwiseXor | BO::BitwiseAnd | BO::Remainder | BO::ShiftLeft | BO::ShiftRight => { - // All equal of integer type - let progress_base = self.apply_template_constraint(ctx, upcast_id, &INTEGERLIKE_TEMPLATE)?; - let (progress_expr, progress_arg1, progress_arg2) = - self.apply_equal3_constraint(ctx, upcast_id, arg1_id, arg2_id, 0)?; - - (progress_base || progress_expr, progress_base || progress_arg1, progress_base || progress_arg2) - }, - BO::Equality | BO::Inequality => { - // Equal2 on args, forced boolean output - let progress_expr = self.apply_forced_constraint(ctx, upcast_id, &BOOL_TEMPLATE)?; - let (progress_arg1, progress_arg2) = - self.apply_equal2_constraint(ctx, upcast_id, arg1_id, 0, arg2_id, 0)?; - - (progress_expr, progress_arg1, progress_arg2) - }, - BO::LessThan | BO::GreaterThan | BO::LessThanEqual | BO::GreaterThanEqual => { - // Equal2 on args with numberlike type, forced boolean output - let progress_expr = self.apply_forced_constraint(ctx, upcast_id, &BOOL_TEMPLATE)?; - let progress_arg_base = self.apply_template_constraint(ctx, arg1_id, &NUMBERLIKE_TEMPLATE)?; - let (progress_arg1, progress_arg2) = - self.apply_equal2_constraint(ctx, upcast_id, arg1_id, 0, arg2_id, 0)?; - - (progress_expr, progress_arg_base || progress_arg1, progress_arg_base || progress_arg2) - }, - BO::Add | BO::Subtract | BO::Multiply | BO::Divide => { - // All equal of number type - let progress_base = self.apply_template_constraint(ctx, upcast_id, &NUMBERLIKE_TEMPLATE)?; - let (progress_expr, progress_arg1, progress_arg2) = - self.apply_equal3_constraint(ctx, upcast_id, arg1_id, arg2_id, 0)?; - - (progress_base || progress_expr, progress_base || progress_arg1, progress_base || progress_arg2) - }, - }; - - debug_log!(" * After:"); - debug_log!(" - Arg1 type [{}]: {}", progress_arg1, self.debug_get_display_name(ctx, arg1_id)); - debug_log!(" - Arg2 type [{}]: {}", progress_arg2, self.debug_get_display_name(ctx, arg2_id)); - debug_log!(" - Expr type [{}]: {}", progress_expr, self.debug_get_display_name(ctx, upcast_id)); - - if progress_expr { self.queue_node_parent(ctx, upcast_id); } - if progress_arg1 { self.queue_expr(ctx, arg1_id); } - if progress_arg2 { self.queue_expr(ctx, arg2_id); } - - Ok(()) - } - - fn progress_unary_expr(&mut self, ctx: &mut Ctx, id: UnaryExpressionId) -> Result<(), ParseError> { - use UnaryOperator as UO; - - let upcast_id = id.upcast(); - let expr = &ctx.heap[id]; - let arg_id = expr.expression; - - debug_log!("Unary expr '{:?}': {}", expr.operation, upcast_id.index); - debug_log!(" * Before:"); - debug_log!(" - Arg type: {}", self.debug_get_display_name(ctx, arg_id)); - debug_log!(" - Expr type: {}", self.debug_get_display_name(ctx, upcast_id)); - - let (progress_expr, progress_arg) = match expr.operation { - UO::Positive | UO::Negative => { - // Equal types of numeric class - let progress_base = self.apply_template_constraint(ctx, upcast_id, &NUMBERLIKE_TEMPLATE)?; - let (progress_expr, progress_arg) = - self.apply_equal2_constraint(ctx, upcast_id, upcast_id, 0, arg_id, 0)?; - - (progress_base || progress_expr, progress_base || progress_arg) - }, - UO::BitwiseNot => { - // Equal types of integer class - let progress_base = self.apply_template_constraint(ctx, upcast_id, &INTEGERLIKE_TEMPLATE)?; - let (progress_expr, progress_arg) = - self.apply_equal2_constraint(ctx, upcast_id, upcast_id, 0, arg_id, 0)?; - - (progress_base || progress_expr, progress_base || progress_arg) - }, - UO::LogicalNot => { - // Both bools - let progress_expr = self.apply_forced_constraint(ctx, upcast_id, &BOOL_TEMPLATE)?; - let progress_arg = self.apply_forced_constraint(ctx, upcast_id, &BOOL_TEMPLATE)?; - (progress_expr, progress_arg) - } - }; - - debug_log!(" * After:"); - debug_log!(" - Arg type [{}]: {}", progress_arg, self.debug_get_display_name(ctx, arg_id)); - debug_log!(" - Expr type [{}]: {}", progress_expr, self.debug_get_display_name(ctx, upcast_id)); - - if progress_expr { self.queue_node_parent(ctx, upcast_id); } - if progress_arg { self.queue_expr(ctx, arg_id); } - - Ok(()) - } - - fn progress_indexing_expr(&mut self, ctx: &mut Ctx, id: IndexingExpressionId) -> Result<(), ParseError> { - let upcast_id = id.upcast(); - let expr = &ctx.heap[id]; - let subject_id = expr.subject; - let index_id = expr.index; - - debug_log!("Indexing expr: {}", upcast_id.index); - debug_log!(" * Before:"); - debug_log!(" - Subject type: {}", self.debug_get_display_name(ctx, subject_id)); - debug_log!(" - Index type: {}", self.debug_get_display_name(ctx, index_id)); - debug_log!(" - Expr type: {}", self.debug_get_display_name(ctx, upcast_id)); - - // Make sure subject is arraylike and index is integerlike - let progress_subject_base = self.apply_template_constraint(ctx, subject_id, &ARRAYLIKE_TEMPLATE)?; - let progress_index = self.apply_template_constraint(ctx, index_id, &INTEGERLIKE_TEMPLATE)?; - - // Make sure if output is of T then subject is Array - let (progress_expr, progress_subject) = - self.apply_equal2_constraint(ctx, upcast_id, upcast_id, 0, subject_id, 1)?; - - debug_log!(" * After:"); - debug_log!(" - Subject type [{}]: {}", progress_subject_base || progress_subject, self.debug_get_display_name(ctx, subject_id)); - debug_log!(" - Index type [{}]: {}", progress_index, self.debug_get_display_name(ctx, index_id)); - debug_log!(" - Expr type [{}]: {}", progress_expr, self.debug_get_display_name(ctx, upcast_id)); - - if progress_expr { self.queue_node_parent(ctx, upcast_id); } - if progress_subject_base || progress_subject { self.queue_expr(ctx, subject_id); } - if progress_index { self.queue_expr(ctx, index_id); } - - Ok(()) - } - - fn progress_slicing_expr(&mut self, ctx: &mut Ctx, id: SlicingExpressionId) -> Result<(), ParseError> { - let upcast_id = id.upcast(); - let expr = &ctx.heap[id]; - let subject_id = expr.subject; - let from_id = expr.from_index; - let to_id = expr.to_index; - - debug_log!("Slicing expr: {}", upcast_id.index); - debug_log!(" * Before:"); - debug_log!(" - Subject type: {}", self.debug_get_display_name(ctx, subject_id)); - debug_log!(" - FromIdx type: {}", self.debug_get_display_name(ctx, from_id)); - debug_log!(" - ToIdx type: {}", self.debug_get_display_name(ctx, to_id)); - debug_log!(" - Expr type: {}", self.debug_get_display_name(ctx, upcast_id)); - - // Make sure subject is arraylike and indices are of equal integerlike - let progress_subject_base = self.apply_template_constraint(ctx, subject_id, &ARRAYLIKE_TEMPLATE)?; - let progress_idx_base = self.apply_template_constraint(ctx, from_id, &INTEGERLIKE_TEMPLATE)?; - let (progress_from, progress_to) = self.apply_equal2_constraint(ctx, upcast_id, from_id, 0, to_id, 0)?; - - let (progress_expr, progress_subject) = match self.type_is_certainly_or_certainly_not_string(ctx, subject_id) { - (true, _) => { - // Certainly a string - (self.apply_forced_constraint(ctx, upcast_id, &STRING_TEMPLATE)?, false) - }, - (_, true) => { - // Certainly not a string - let progress_expr_base = self.apply_template_constraint(ctx, upcast_id, &SLICE_TEMPLATE)?; - let (progress_expr, progress_subject) = - self.apply_equal2_constraint(ctx, upcast_id, upcast_id, 1, subject_id, 1)?; - - (progress_expr_base || progress_expr, progress_subject) - }, - _ => { - // Could be anything, at least attempt to progress subtype - let progress_expr_base = self.apply_template_constraint(ctx, upcast_id, &ARRAYLIKE_TEMPLATE)?; - let (progress_expr, progress_subject) = - self.apply_equal2_constraint(ctx, upcast_id, upcast_id, 1, subject_id, 1)?; - - (progress_expr_base || progress_expr, progress_subject) - } - }; - - debug_log!(" * After:"); - debug_log!(" - Subject type [{}]: {}", progress_subject_base || progress_subject, self.debug_get_display_name(ctx, subject_id)); - debug_log!(" - FromIdx type [{}]: {}", progress_idx_base || progress_from, self.debug_get_display_name(ctx, from_id)); - debug_log!(" - ToIdx type [{}]: {}", progress_idx_base || progress_to, self.debug_get_display_name(ctx, to_id)); - debug_log!(" - Expr type [{}]: {}", progress_expr, self.debug_get_display_name(ctx, upcast_id)); - - if progress_expr { self.queue_node_parent(ctx, upcast_id); } - if progress_subject_base || progress_subject { self.queue_expr(ctx, subject_id); } - if progress_idx_base || progress_from { self.queue_expr(ctx, from_id); } - if progress_idx_base || progress_to { self.queue_expr(ctx, to_id); } - - Ok(()) - } - - fn progress_select_expr(&mut self, ctx: &mut Ctx, id: SelectExpressionId) -> Result<(), ParseError> { - let upcast_id = id.upcast(); - - debug_log!("Select expr: {}", upcast_id.index); - debug_log!(" * Before:"); - debug_log!(" - Subject type: {}", self.debug_get_display_name(ctx, ctx.heap[id].subject)); - debug_log!(" - Expr type: {}", self.debug_get_display_name(ctx, upcast_id)); - - let subject_id = ctx.heap[id].subject; - let subject_expr_idx = ctx.heap[subject_id].get_unique_id_in_definition(); - let select_expr = &ctx.heap[id]; - let expr_idx = select_expr.unique_id_in_definition; - - let infer_expr = &self.infer_nodes[expr_idx as usize]; - let extra_idx = infer_expr.extra_data_idx; - - fn try_get_definition_id_from_inference_type<'a>(types: &'a TypeTable, infer_type: &InferenceType) -> Result, ()> { - for part in &infer_type.parts { - if part.is_marker() || !part.is_concrete() { - continue; - } - - // Part is concrete, check if it is an instance of something - if let InferenceTypePart::Instance(definition_id, _num_sub) = part { - // Lookup type definition and ensure the specified field - // name exists on the struct - let definition = types.get_base_definition(definition_id); - debug_assert!(definition.is_some()); - let definition = definition.unwrap(); - - return Ok(Some(definition)) - } else { - // Expected an instance of something - return Err(()) - } - } - - // Nothing is concrete yet - Ok(None) - } - - fn try_get_tuple_size_from_inference_type(infer_type: &InferenceType) -> Result, ()> { - for part in &infer_type.parts { - if part.is_marker() || !part.is_concrete() { - continue; - } - - if let InferenceTypePart::Tuple(size) = part { - return Ok(Some(*size)); - } else { - // Expected a tuple - return Err(()); - } - } - - // Type is not "defined enough" yet - Ok(None) - } - - let (progress_subject, progress_expr) = match &select_expr.kind { - SelectKind::StructField(field_name) => { - // Handle select of a struct's field - if infer_expr.field_or_monomorph_index < 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.infer_nodes[subject_expr_idx as usize].expr_type; - let type_def = try_get_definition_id_from_inference_type(&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_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 == *field_name { - // Set field definition and index - let infer_expr = &mut self.infer_nodes[expr_idx as usize]; - infer_expr.field_or_monomorph_index = 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, 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, 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 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.poly_data[extra_idx as usize]; - let mut poly_progress = HashSet::new(); // TODO: @Performance - - // Apply to struct's type - let signature_type: *mut _ = &mut poly_data.associated[0]; - let subject_type: *mut _ = &mut self.infer_nodes[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 - )?; - - 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.infer_nodes[expr_idx as usize].expr_type; - - let (_, progress_expr) = Self::apply_equal2_signature_constraint( - ctx, upcast_id, None, poly_data, &mut poly_progress, - signature_type, 0, expr_type, 0 - )?; - - 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); - } - } - - // Reapply progress in polymorphic variables to struct's type - let signature_type: *mut _ = &mut poly_data.associated[0]; - let subject_type: *mut _ = &mut self.infer_nodes[subject_expr_idx as usize].expr_type; - - let progress_subject = Self::apply_equal2_polyvar_constraint( - poly_data, &poly_progress, signature_type, subject_type - ); - - let signature_type: *mut _ = &mut poly_data.returned; - let expr_type: *mut _ = &mut self.infer_nodes[expr_idx as usize].expr_type; - - let progress_expr = Self::apply_equal2_polyvar_constraint( - poly_data, &poly_progress, signature_type, expr_type - ); - - (progress_subject, progress_expr) - }, - SelectKind::TupleMember(member_index) => { - let member_index = *member_index; - - if infer_expr.field_or_monomorph_index < 0 { - // We don't know what kind of tuple we're accessing yet - let subject_type = &self.infer_nodes[subject_expr_idx as usize].expr_type; - let tuple_size = try_get_tuple_size_from_inference_type(subject_type); - - match tuple_size { - Ok(Some(enum_size)) => { - // Make sure we don't access an element outside of - // the tuple's bounds - if member_index >= enum_size as u64 { - return Err(ParseError::new_error_at_span( - &ctx.module().source, select_expr.full_span, format!( - "element index {} is out of bounds, tuple has {} elements", - member_index, enum_size - ) - )); - } - - // Within bounds, so set the index (such that we - // will not perform this lookup again) - let infer_expr = &mut self.infer_nodes[expr_idx as usize]; - infer_expr.field_or_monomorph_index = member_index as i32; - }, - Ok(None) => { - // Nothing is known about the tuple yet - return Ok(()); - }, - Err(()) => { - return Err(ParseError::new_error_at_span( - &ctx.module().source, select_expr.full_span, format!( - "Can only apply tuple element selection to tuples, got a subject of type '{}'", - subject_type.display_name(&ctx.heap) - ) - )); - } - } - } - - // If here then we know which member we're accessing. So seek - // that member in the subject type and apply inference. - let subject_type = &self.infer_nodes[subject_expr_idx as usize].expr_type; - let mut member_start_idx = 1; - for _ in 0..member_index { - member_start_idx = InferenceType::find_subtree_end_idx(&subject_type.parts, member_start_idx); - } - - let (progress_expr, progress_subject) = self.apply_equal2_constraint( - ctx, upcast_id, upcast_id, 0, subject_id, member_start_idx - )?; - - (progress_subject, progress_expr) - }, - }; - - if progress_subject { self.queue_expr(ctx, subject_id); } - if progress_expr { self.queue_node_parent(ctx, upcast_id); } - - debug_log!(" * After:"); - debug_log!(" - Subject type [{}]: {}", progress_subject, self.debug_get_display_name(ctx, subject_id)); - debug_log!(" - Expr type [{}]: {}", progress_expr, self.debug_get_display_name(ctx, upcast_id)); - - Ok(()) - } - - fn progress_literal_expr(&mut self, ctx: &mut Ctx, id: LiteralExpressionId) -> Result<(), ParseError> { - let upcast_id = id.upcast(); - let expr = &ctx.heap[id]; - let expr_idx = expr.unique_id_in_definition; - let extra_idx = self.infer_nodes[expr_idx as usize].extra_data_idx; - - debug_log!("Literal expr: {}", upcast_id.index); - debug_log!(" * Before:"); - debug_log!(" - Expr type: {}", self.debug_get_display_name(ctx, upcast_id)); - - let progress_expr = match &expr.value { - Literal::Null => { - self.apply_template_constraint(ctx, upcast_id, &MESSAGE_TEMPLATE)? - }, - Literal::Integer(_) => { - self.apply_template_constraint(ctx, upcast_id, &INTEGERLIKE_TEMPLATE)? - }, - Literal::True | Literal::False => { - self.apply_forced_constraint(ctx, upcast_id, &BOOL_TEMPLATE)? - }, - Literal::Character(_) => { - self.apply_forced_constraint(ctx, upcast_id, &CHARACTER_TEMPLATE)? - }, - Literal::String(_) => { - self.apply_forced_constraint(ctx, upcast_id, &STRING_TEMPLATE)? - }, - Literal::Struct(data) => { - let extra = &mut self.poly_data[extra_idx as usize]; - for _poly in &extra.poly_vars { - debug_log!(" * Poly: {}", _poly.display_name(&ctx.heap)); - } - let mut poly_progress = HashSet::new(); - debug_assert_eq!(extra.associated.len(), data.fields.len()); - - debug_log!(" * During (inferring types from fields and struct type):"); - - // Mutually infer field signature/expression types - for (field_idx, field) in data.fields.iter().enumerate() { - let field_expr_id = field.value; - let field_expr_idx = ctx.heap[field_expr_id].get_unique_id_in_definition(); - let signature_type: *mut _ = &mut extra.associated[field_idx]; - let field_type: *mut _ = &mut self.infer_nodes[field_expr_idx as usize].expr_type; - let (_, progress_arg) = Self::apply_equal2_signature_constraint( - ctx, upcast_id, Some(field_expr_id), extra, &mut poly_progress, - signature_type, 0, field_type, 0 - )?; - - debug_log!( - " - Field {} type | sig: {}, field: {}", field_idx, - unsafe{&*signature_type}.display_name(&ctx.heap), - unsafe{&*field_type}.display_name(&ctx.heap) - ); - - if progress_arg { - self.expr_queued.push_back(field_expr_idx); - } - } - - debug_log!(" - Field poly progress | {:?}", poly_progress); - - // Same for the type of the struct itself - let signature_type: *mut _ = &mut extra.returned; - let expr_type: *mut _ = &mut self.infer_nodes[expr_idx as usize].expr_type; - let (_, progress_expr) = Self::apply_equal2_signature_constraint( - ctx, upcast_id, None, extra, &mut poly_progress, - signature_type, 0, expr_type, 0 - )?; - - debug_log!( - " - Ret type | sig: {}, expr: {}", - unsafe{&*signature_type}.display_name(&ctx.heap), - unsafe{&*expr_type}.display_name(&ctx.heap) - ); - debug_log!(" - Ret poly progress | {:?}", poly_progress); - - if progress_expr { - // TODO: @cleanup, cannot call utility self.queue_parent thingo - 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); - } - } - - // Check which expressions use the polymorphic arguments. If the - // polymorphic variables have been progressed then we try to - // progress them inside the expression as well. - debug_log!(" * During (reinferring from progressed polyvars):"); - - // For all field expressions - for field_idx in 0..extra.associated.len() { - // Note: fields in extra.embedded are in the same order as - // they are specified in the literal. Whereas - // `data.fields[...].field_idx` points to the field in the - // struct definition. - let signature_type: *mut _ = &mut extra.associated[field_idx]; - let field_expr_id = data.fields[field_idx].value; - let field_expr_idx = ctx.heap[field_expr_id].get_unique_id_in_definition(); - let field_type: *mut _ = &mut self.infer_nodes[field_expr_idx as usize].expr_type; - - let progress_arg = Self::apply_equal2_polyvar_constraint( - extra, &poly_progress, signature_type, field_type - ); - - debug_log!( - " - Field {} type | sig: {}, field: {}", field_idx, - unsafe{&*signature_type}.display_name(&ctx.heap), - unsafe{&*field_type}.display_name(&ctx.heap) - ); - if progress_arg { - self.expr_queued.push_back(field_expr_idx); - } - } - - // For the return type - let signature_type: *mut _ = &mut extra.returned; - let expr_type: *mut _ = &mut self.infer_nodes[expr_idx as usize].expr_type; - - let progress_expr = Self::apply_equal2_polyvar_constraint( - extra, &poly_progress, signature_type, expr_type - ); - - progress_expr - }, - Literal::Enum(_) => { - let extra = &mut self.poly_data[extra_idx as usize]; - for _poly in &extra.poly_vars { - debug_log!(" * Poly: {}", _poly.display_name(&ctx.heap)); - } - let mut poly_progress = HashSet::new(); - - debug_log!(" * During (inferring types from return type)"); - - let signature_type: *mut _ = &mut extra.returned; - let expr_type: *mut _ = &mut self.infer_nodes[expr_idx as usize].expr_type; - let (_, progress_expr) = Self::apply_equal2_signature_constraint( - ctx, upcast_id, None, extra, &mut poly_progress, - signature_type, 0, expr_type, 0 - )?; - - debug_log!( - " - Ret type | sig: {}, expr: {}", - unsafe{&*signature_type}.display_name(&ctx.heap), - unsafe{&*expr_type}.display_name(&ctx.heap) - ); - - if progress_expr { - // TODO: @cleanup - 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); - } - } - - debug_log!(" * During (reinferring from progress polyvars):"); - let progress_expr = Self::apply_equal2_polyvar_constraint( - extra, &poly_progress, signature_type, expr_type - ); - - progress_expr - }, - Literal::Union(data) => { - let extra = &mut self.poly_data[extra_idx as usize]; - for _poly in &extra.poly_vars { - debug_log!(" * Poly: {}", _poly.display_name(&ctx.heap)); - } - let mut poly_progress = HashSet::new(); - debug_assert_eq!(extra.associated.len(), data.values.len()); - - debug_log!(" * During (inferring types from variant values and union type):"); - - // Mutually infer union variant values - for (value_idx, value_expr_id) in data.values.iter().enumerate() { - let value_expr_id = *value_expr_id; - let value_expr_idx = ctx.heap[value_expr_id].get_unique_id_in_definition(); - let signature_type: *mut _ = &mut extra.associated[value_idx]; - let value_type: *mut _ = &mut self.infer_nodes[value_expr_idx as usize].expr_type; - let (_, progress_arg) = Self::apply_equal2_signature_constraint( - ctx, upcast_id, Some(value_expr_id), extra, &mut poly_progress, - signature_type, 0, value_type, 0 - )?; - - debug_log!( - " - Value {} type | sig: {}, field: {}", value_idx, - unsafe{&*signature_type}.display_name(&ctx.heap), - unsafe{&*value_type}.display_name(&ctx.heap) - ); - - if progress_arg { - self.expr_queued.push_back(value_expr_idx); - } - } - - debug_log!(" - Field poly progress | {:?}", poly_progress); - - // Infer type of union itself - let signature_type: *mut _ = &mut extra.returned; - let expr_type: *mut _ = &mut self.infer_nodes[expr_idx as usize].expr_type; - let (_, progress_expr) = Self::apply_equal2_signature_constraint( - ctx, upcast_id, None, extra, &mut poly_progress, - signature_type, 0, expr_type, 0 - )?; - - debug_log!( - " - Ret type | sig: {}, expr: {}", - unsafe{&*signature_type}.display_name(&ctx.heap), - unsafe{&*expr_type}.display_name(&ctx.heap) - ); - debug_log!(" - Ret poly progress | {:?}", poly_progress); - - if progress_expr { - // TODO: @cleanup, borrowing rules - 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); - } - } - - debug_log!(" * During (reinferring from progress polyvars):"); - - // For all embedded values of the union variant - for value_idx in 0..extra.associated.len() { - let signature_type: *mut _ = &mut extra.associated[value_idx]; - let value_expr_id = data.values[value_idx]; - let value_expr_idx = ctx.heap[value_expr_id].get_unique_id_in_definition(); - let value_type: *mut _ = &mut self.infer_nodes[value_expr_idx as usize].expr_type; - - let progress_arg = Self::apply_equal2_polyvar_constraint( - extra, &poly_progress, signature_type, value_type - ); - - debug_log!( - " - Value {} type | sig: {}, value: {}", value_idx, - unsafe{&*signature_type}.display_name(&ctx.heap), - unsafe{&*value_type}.display_name(&ctx.heap) - ); - if progress_arg { - self.expr_queued.push_back(value_expr_idx); - } - } - - // And for the union type itself - let signature_type: *mut _ = &mut extra.returned; - let expr_type: *mut _ = &mut self.infer_nodes[expr_idx as usize].expr_type; - - let progress_expr = Self::apply_equal2_polyvar_constraint( - extra, &poly_progress, signature_type, expr_type - ); - - progress_expr - }, - Literal::Array(data) => { - let expr_elements = self.expr_buffer.start_section_initialized(data.as_slice()); - debug_log!("Array expr ({} elements): {}", expr_elements.len(), upcast_id.index); - debug_log!(" * Before:"); - debug_log!(" - Expr type: {}", self.debug_get_display_name(ctx, upcast_id)); - - // All elements should have an equal type - let mut bool_buffer = self.bool_buffer.start_section(); - self.apply_equal_n_constraint(ctx, upcast_id, &expr_elements, &mut bool_buffer)?; - for (progress_arg, arg_id) in bool_buffer.iter_copied().zip(expr_elements.iter_copied()) { - if progress_arg { - self.queue_expr(ctx, arg_id); - } - } - - // And the output should be an array of the element types - let mut progress_expr = self.apply_template_constraint(ctx, upcast_id, &ARRAY_TEMPLATE)?; - if expr_elements.len() != 0 { - let first_arg_id = expr_elements[0]; - let (inner_expr_progress, arg_progress) = self.apply_equal2_constraint( - ctx, upcast_id, upcast_id, 1, first_arg_id, 0 - )?; - - progress_expr = progress_expr || inner_expr_progress; - - // Note that if the array type progressed the type of the arguments, - // then we should enqueue this progression function again - // TODO: @fix Make apply_equal_n accept a start idx as well - if arg_progress { self.queue_expr(ctx, upcast_id); } - } - - debug_log!(" * After:"); - debug_log!(" - Expr type [{}]: {}", progress_expr, self.debug_get_display_name(ctx, upcast_id)); - - expr_elements.forget(); - progress_expr - }, - Literal::Tuple(data) => { - let expr_elements = self.expr_buffer.start_section_initialized(data.as_slice()); - debug_log!("Tuple expr ({} elements): {}", expr_elements.len(), upcast_id.index); - debug_log!(" * Before:"); - debug_log!(" - Expr type: {}", self.debug_get_display_name(ctx, upcast_id)); - - // Initial tuple constraint - let num_members = expr_elements.len(); - let mut initial_type = Vec::with_capacity(num_members + 1); // TODO: @performance - initial_type.push(InferenceTypePart::Tuple(num_members as u32)); - for _ in 0..num_members { - initial_type.push(InferenceTypePart::Unknown); - } - let mut progress_expr = self.apply_template_constraint(ctx, upcast_id, &initial_type)?; - - // The elements of the tuple can have any type, but they must - // end up as arguments to the output tuple type. - debug_log!(" * During (checking expressions constituting tuple):"); - for (member_expr_index, member_expr_id) in expr_elements.iter_copied().enumerate() { - // For the current expression index, (re)compute the - // position in the tuple type where the types should match. - let mut start_index = 1; // first element is Tuple type, second is the first child - for _ in 0..member_expr_index { - let tuple_expr_index = ctx.heap[id].unique_id_in_definition; - let tuple_type = &self.infer_nodes[tuple_expr_index as usize].expr_type; - start_index = InferenceType::find_subtree_end_idx(&tuple_type.parts, start_index); - debug_assert_ne!(start_index, tuple_type.parts.len()); // would imply less tuple type children than member expressions - } - - // Apply the constraint - let (member_progress_expr, member_progress) = self.apply_equal2_constraint( - ctx, upcast_id, upcast_id, start_index, member_expr_id, 0 - )?; - debug_log!(" - Member {} type | {}", member_expr_index, self.debug_get_display_name(ctx, *member_expr_id)); - progress_expr = progress_expr || member_progress_expr; - - if member_progress { - self.queue_expr(ctx, member_expr_id); - } - } - - expr_elements.forget(); - progress_expr - } - }; - - debug_log!(" * After:"); - debug_log!(" - Expr type [{}]: {}", progress_expr, self.debug_get_display_name(ctx, upcast_id)); - - if progress_expr { self.queue_node_parent(ctx, upcast_id); } - - Ok(()) - } - - fn progress_cast_expr(&mut self, ctx: &mut Ctx, id: CastExpressionId) -> Result<(), ParseError> { - let upcast_id = id.upcast(); - let expr = &ctx.heap[id]; - let expr_idx = expr.unique_id_in_definition; - - debug_log!("Casting expr: {}", upcast_id.index); - debug_log!(" * Before:"); - debug_log!(" - Expr type: {}", self.debug_get_display_name(ctx, upcast_id)); - debug_log!(" - Subject type: {}", self.debug_get_display_name(ctx, expr.subject)); - - // The cast expression might have its output type fixed by the - // programmer, so apply that type to the output. Apart from that casting - // acts like a blocker for two-way inference. So we'll just have to wait - // until we know if the cast is valid. - // TODO: Another thing that has to be updated the moment the type - // inferencer is fully index/job-based - let infer_type = self.determine_inference_type_from_parser_type_elements(&expr.to_type.elements, true); - let expr_progress = self.apply_template_constraint(ctx, upcast_id, &infer_type.parts)?; - - if expr_progress { - self.queue_node_parent(ctx, upcast_id); - } - - // Check if the two types are compatible - debug_log!(" * After:"); - debug_log!(" - Expr type [{}]: {}", expr_progress, self.debug_get_display_name(ctx, upcast_id)); - debug_log!(" - Note that the subject type can never be inferred"); - debug_log!(" * Decision:"); - - let subject_idx = ctx.heap[expr.subject].get_unique_id_in_definition(); - let expr_type = &self.infer_nodes[expr_idx as usize].expr_type; - let subject_type = &self.infer_nodes[subject_idx as usize].expr_type; - if !expr_type.is_done || !subject_type.is_done { - // Not yet done - debug_log!(" - Casting is valid: unknown as the types are not yet complete"); - return Ok(()) - } - - // Valid casts: (bool, integer, character) can always be cast to one - // another. A cast from a type to itself is also valid. - fn is_bool_int_or_char(parts: &[InferenceTypePart]) -> bool { - return parts.len() == 1 && ( - parts[0] == InferenceTypePart::Bool || - parts[0] == InferenceTypePart::Character || - parts[0].is_concrete_integer() - ); - } - - let is_valid = if is_bool_int_or_char(&expr_type.parts) && is_bool_int_or_char(&subject_type.parts) { - true - } else if expr_type.parts == subject_type.parts { - true - } else { - false - }; - - debug_log!(" - Casting is valid: {}", is_valid); - - if !is_valid { - let cast_expr = &ctx.heap[id]; - let subject_expr = &ctx.heap[cast_expr.subject]; - return Err(ParseError::new_error_str_at_span( - &ctx.module().source, cast_expr.full_span, "invalid casting operation" - ).with_info_at_span( - &ctx.module().source, subject_expr.full_span(), format!( - "cannot cast the argument type '{}' to the cast type '{}'", - subject_type.display_name(&ctx.heap), - expr_type.display_name(&ctx.heap) - ) - )); - } - - Ok(()) - } - - // TODO: @cleanup, see how this can be cleaned up once I implement - // polymorphic struct/enum/union literals. These likely follow the same - // pattern as here. - fn progress_call_expr(&mut self, ctx: &mut Ctx, id: CallExpressionId) -> Result<(), ParseError> { - let upcast_id = id.upcast(); - let expr = &ctx.heap[id]; - let expr_idx = expr.unique_id_in_definition; - let extra_idx = self.infer_nodes[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:"); - debug_log!(" - Expr type: {}", self.debug_get_display_name(ctx, upcast_id)); - debug_log!(" * During (inferring types from arguments and return type):"); - - let extra = &mut self.poly_data[extra_idx as usize]; - - // Check if we can make progress using the arguments and/or return types - // while keeping track of the polyvars we've extended - let mut poly_progress = HashSet::new(); - debug_assert_eq!(extra.associated.len(), expr.arguments.len()); - - for (call_arg_idx, arg_id) in expr.arguments.clone().into_iter().enumerate() { - let arg_expr_idx = ctx.heap[arg_id].get_unique_id_in_definition(); - let signature_type: *mut _ = &mut extra.associated[call_arg_idx]; - let argument_type: *mut _ = &mut self.infer_nodes[arg_expr_idx as usize].expr_type; - let (_, progress_arg) = Self::apply_equal2_signature_constraint( - ctx, upcast_id, Some(arg_id), extra, &mut poly_progress, - signature_type, 0, argument_type, 0 - )?; - - debug_log!( - " - Arg {} type | sig: {}, arg: {}", call_arg_idx, - unsafe{&*signature_type}.display_name(&ctx.heap), - unsafe{&*argument_type}.display_name(&ctx.heap)); - - if progress_arg { - // Progressed argument expression - self.expr_queued.push_back(arg_expr_idx); - } - } - - // Do the same for the return type - let signature_type: *mut _ = &mut extra.returned; - let expr_type: *mut _ = &mut self.infer_nodes[expr_idx as usize].expr_type; - let (_, progress_expr) = Self::apply_equal2_signature_constraint( - ctx, upcast_id, None, extra, &mut poly_progress, - signature_type, 0, expr_type, 0 - )?; - - debug_log!( - " - Ret type | sig: {}, expr: {}", - unsafe{&*signature_type}.display_name(&ctx.heap), - unsafe{&*expr_type}.display_name(&ctx.heap) - ); - - if progress_expr { - // TODO: @cleanup, cannot call utility self.queue_parent thingo - 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); - } - } - - // If we did not have an error in the polymorph inference above, then - // reapplying the polymorph type to each argument type and the return - // type should always succeed. - debug_log!(" * During (reinferring from progressed polyvars):"); - for (_poly_idx, _poly_var) in extra.poly_vars.iter().enumerate() { - debug_log!(" - Poly {} | sig: {}", _poly_idx, _poly_var.display_name(&ctx.heap)); - } - // TODO: @performance If the algorithm is changed to be more "on demand - // argument re-evaluation", instead of "all-argument re-evaluation", - // then this is no longer true - for arg_idx in 0..extra.associated.len() { - let signature_type: *mut _ = &mut extra.associated[arg_idx]; - let arg_expr_id = expr.arguments[arg_idx]; - let arg_expr_idx = ctx.heap[arg_expr_id].get_unique_id_in_definition(); - let arg_type: *mut _ = &mut self.infer_nodes[arg_expr_idx as usize].expr_type; - - let progress_arg = Self::apply_equal2_polyvar_constraint( - extra, &poly_progress, - signature_type, arg_type - ); - - debug_log!( - " - Arg {} type | sig: {}, arg: {}", arg_idx, - unsafe{&*signature_type}.display_name(&ctx.heap), - unsafe{&*arg_type}.display_name(&ctx.heap) - ); - if progress_arg { - self.expr_queued.push_back(arg_expr_idx); - } - } - - // Once more for the return type - let signature_type: *mut _ = &mut extra.returned; - let ret_type: *mut _ = &mut self.infer_nodes[expr_idx as usize].expr_type; - - let progress_ret = Self::apply_equal2_polyvar_constraint( - extra, &poly_progress, signature_type, ret_type - ); - debug_log!( - " - Ret type | sig: {}, arg: {}", - unsafe{&*signature_type}.display_name(&ctx.heap), - unsafe{&*ret_type}.display_name(&ctx.heap) - ); - if progress_ret { - self.queue_node_parent(ctx, upcast_id); - } - - debug_log!(" * After:"); - debug_log!(" - Expr type: {}", self.debug_get_display_name(ctx, upcast_id)); - - Ok(()) - } - - fn progress_variable_expr(&mut self, ctx: &mut Ctx, id: VariableExpressionId) -> Result<(), ParseError> { - let upcast_id = id.upcast(); - let var_expr = &ctx.heap[id]; - let var_expr_idx = var_expr.unique_id_in_definition; - let var_id = var_expr.declaration.unwrap(); - - debug_log!("Variable expr '{}': {}", ctx.heap[var_id].identifier.value.as_str(), upcast_id.index); - debug_log!(" * Before:"); - debug_log!(" - Var type: {}", self.var_types.get(&var_id).unwrap().var_type.display_name(&ctx.heap)); - debug_log!(" - Expr type: {}", self.debug_get_display_name(ctx, upcast_id)); - - // Retrieve shared variable type and expression type and apply inference - let var_data = self.var_types.get_mut(&var_id).unwrap(); - let expr_type = &mut self.infer_nodes[var_expr_idx as usize].expr_type; - - let infer_res = unsafe{ InferenceType::infer_subtrees_for_both_types( - &mut var_data.var_type as *mut _, 0, expr_type, 0 - ) }; - if infer_res == DualInferenceResult::Incompatible { - let var_decl = &ctx.heap[var_id]; - return Err(ParseError::new_error_at_span( - &ctx.module().source, var_decl.identifier.span, format!( - "Conflicting types for this variable, previously assigned the type '{}'", - var_data.var_type.display_name(&ctx.heap) - ) - ).with_info_at_span( - &ctx.module().source, var_expr.identifier.span, format!( - "But inferred to have incompatible type '{}' here", - expr_type.display_name(&ctx.heap) - ) - )) - } - - let progress_var = infer_res.modified_lhs(); - let progress_expr = infer_res.modified_rhs(); - - if progress_var { - // Let other variable expressions using this type progress as well - for other_expr in var_data.used_at.iter() { - if *other_expr != upcast_id { - let other_expr_idx = ctx.heap[*other_expr].get_unique_id_in_definition(); - self.expr_queued.push_back(other_expr_idx); - } - } - - // Let a linked port know that our type has updated - if let Some(linked_id) = var_data.linked_var { - // Only perform one-way inference to prevent updating our type, - // this would lead to an inconsistency in the type inference - // algorithm otherwise. - let var_type: *mut _ = &mut var_data.var_type; - let link_data = self.var_types.get_mut(&linked_id).unwrap(); - - debug_assert!( - unsafe{&*var_type}.parts[0] == InferenceTypePart::Input || - unsafe{&*var_type}.parts[0] == InferenceTypePart::Output - ); - debug_assert!( - link_data.var_type.parts[0] == InferenceTypePart::Input || - link_data.var_type.parts[0] == InferenceTypePart::Output - ); - match InferenceType::infer_subtree_for_single_type(&mut link_data.var_type, 1, &unsafe{&*var_type}.parts, 1, false) { - SingleInferenceResult::Modified => { - for other_expr in &link_data.used_at { - let other_expr_idx = ctx.heap[*other_expr].get_unique_id_in_definition(); - self.expr_queued.push_back(other_expr_idx); - } - }, - SingleInferenceResult::Unmodified => {}, - SingleInferenceResult::Incompatible => { - let var_data = self.var_types.get(&var_id).unwrap(); - let link_data = self.var_types.get(&linked_id).unwrap(); - let var_decl = &ctx.heap[var_id]; - let link_decl = &ctx.heap[linked_id]; - - return Err(ParseError::new_error_at_span( - &ctx.module().source, var_decl.identifier.span, format!( - "Conflicting types for this variable, assigned the type '{}'", - var_data.var_type.display_name(&ctx.heap) - ) - ).with_info_at_span( - &ctx.module().source, link_decl.identifier.span, format!( - "Because it is incompatible with this variable, assigned the type '{}'", - link_data.var_type.display_name(&ctx.heap) - ) - )); - } - } - } - } - if progress_expr { self.queue_node_parent(ctx, upcast_id); } - - debug_log!(" * After:"); - debug_log!(" - Var type [{}]: {}", progress_var, self.var_types.get(&var_id).unwrap().var_type.display_name(&ctx.heap)); - debug_log!(" - Expr type [{}]: {}", progress_expr, self.debug_get_display_name(ctx, upcast_id)); - - - Ok(()) - } - fn queue_node_parent(&mut self, node_index: InferNodeIndex) { let node = &self.infer_nodes[node_index]; if let Some(parent_node_index) = node.parent_index { - self.expr_queued.push_back(parent_node_index); + self.node_queued.push_back(parent_node_index); } } #[inline] fn queue_node(&mut self, node_index: InferNodeIndex) { - self.expr_queued.push_back(node_index); + self.node_queued.push_back(node_index); } /// Returns whether the type is certainly a string (true, false), certainly @@ -4314,20 +3024,6 @@ impl PassTyping { } } - fn apply_template_constraint_to_types( - to_infer: *mut InferenceType, to_infer_start_idx: usize, - template: &[InferenceTypePart], template_start_idx: usize - ) -> Result { - match InferenceType::infer_subtree_for_single_type( - unsafe{ &mut *to_infer }, to_infer_start_idx, - template, template_start_idx, false - ) { - SingleInferenceResult::Modified => Ok(true), - SingleInferenceResult::Unmodified => Ok(false), - SingleInferenceResult::Incompatible => Err(()), - } - } - /// Applies a forced constraint: the supplied expression's type MUST be /// inferred from the template, the other way around is considered invalid. fn apply_forced_constraint( @@ -4544,134 +3240,6 @@ impl PassTyping { poly_data.first_rule_application = false; } - /// Applies an equal2 constraint between a signature type (e.g. a function - /// argument or struct field) and an expression whose type should match that - /// expression. If we make progress on the signature, then we try to see if - /// any of the embedded polymorphic types can be progressed. - /// - /// `outer_expr_id` is the main expression we're progressing (e.g. a - /// function call), while `expr_id` is the embedded expression we're - /// matching against the signature. `expression_type` and - /// `expression_start_idx` belong to `expr_id`. - fn apply_equal2_signature_constraint( - ctx: &Ctx, outer_expr_id: ExpressionId, expr_id: Option, - polymorph_data: &mut PolyData, polymorph_progress: &mut HashSet, - signature_type: *mut InferenceType, signature_start_idx: usize, - expression_type: *mut InferenceType, expression_start_idx: usize - ) -> Result<(bool, bool), ParseError> { - // Safety: all pointers distinct - - // Infer the signature and expression type - let infer_res = unsafe { - InferenceType::infer_subtrees_for_both_types( - signature_type, signature_start_idx, - expression_type, expression_start_idx - ) - }; - - if infer_res == DualInferenceResult::Incompatible { - // TODO: Check if I still need to use this - let outer_span = ctx.heap[outer_expr_id].full_span(); - let (span_name, span) = match expr_id { - Some(expr_id) => ("argument's", ctx.heap[expr_id].full_span()), - None => ("type's", outer_span) - }; - let (signature_display_type, expression_display_type) = unsafe { ( - (&*signature_type).display_name(&ctx.heap), - (&*expression_type).display_name(&ctx.heap) - ) }; - - return Err(ParseError::new_error_str_at_span( - &ctx.module().source, outer_span, - "failed to fully resolve the types of this expression" - ).with_info_at_span( - &ctx.module().source, span, format!( - "because the {} signature has been resolved to '{}', but the expression has been resolved to '{}'", - span_name, signature_display_type, expression_display_type - ) - )); - } - - // Try to see if we can progress any of the polymorphic variables - let progress_sig = infer_res.modified_lhs(); - let progress_expr = infer_res.modified_rhs(); - - if progress_sig { - let signature_type = unsafe{&mut *signature_type}; - debug_assert!( - signature_type.has_marker, - "made progress on signature type, but it doesn't have a marker" - ); - for (poly_idx, poly_section) in signature_type.marker_iter() { - let polymorph_type = &mut polymorph_data.poly_vars[poly_idx as usize]; - match Self::apply_template_constraint_to_types( - polymorph_type, 0, poly_section, 0 - ) { - Ok(true) => { polymorph_progress.insert(poly_idx); }, - Ok(false) => {}, - Err(()) => { return Err(Self::construct_poly_arg_error(ctx, polymorph_data, outer_expr_id))} - } - } - } - Ok((progress_sig, progress_expr)) - } - - /// Applies equal2 constraints on the signature type for each of the - /// polymorphic variables. If the signature type is progressed then we - /// progress the expression type as well. - /// - /// This function assumes that the polymorphic variables have already been - /// progressed as far as possible by calling - /// `apply_equal2_signature_constraint`. As such, we expect to not encounter - /// any errors. - /// - /// This function returns true if the expression's type has been progressed - fn apply_equal2_polyvar_constraint( - polymorph_data: &PolyData, _polymorph_progress: &HashSet, - signature_type: *mut InferenceType, expr_type: *mut InferenceType - ) -> bool { - // Safety: all pointers should be distinct - // polymorph_data containers may not be modified - let signature_type = unsafe{&mut *signature_type}; - let expr_type = unsafe{&mut *expr_type}; - - // Iterate through markers in signature type to try and make progress - // on the polymorphic variable - let mut seek_idx = 0; - let mut modified_sig = false; - - while let Some((poly_idx, start_idx)) = signature_type.find_marker(seek_idx) { - let end_idx = InferenceType::find_subtree_end_idx(&signature_type.parts, start_idx); - // if polymorph_progress.contains(&poly_idx) { - // Need to match subtrees - let polymorph_type = &polymorph_data.poly_vars[poly_idx as usize]; - let modified_at_marker = Self::apply_template_constraint_to_types( - signature_type, start_idx, - &polymorph_type.parts, 0 - ).expect("no failure when applying polyvar constraints"); - - modified_sig = modified_sig || modified_at_marker; - // } - - seek_idx = end_idx; - } - - // If we made any progress on the signature's type, then we also need to - // apply it to the expression that is supposed to match the signature. - if modified_sig { - match InferenceType::infer_subtree_for_single_type( - expr_type, 0, &signature_type.parts, 0, true - ) { - SingleInferenceResult::Modified => true, - SingleInferenceResult::Unmodified => false, - SingleInferenceResult::Incompatible => - unreachable!("encountered failure while reapplying modified signature to expression after polyvar inference") - } - } else { - false - } - } - /// Applies a type constraint that expects all three provided types to be /// equal. In case we can make progress in inferring the types then we /// attempt to do so. If the call is successful then the composition of all @@ -4848,9 +3416,10 @@ impl PassTyping { self.infer_nodes.push(InferenceNode { expr_type: inference_type, expr_id, + inference_rule: InferenceRule::Noop, parent_index: self.parent_index, field_or_monomorph_index: -1, - extra_data_idx: -1, + poly_data_index: PolyDataIndex::MAX, type_id: TypeId::new_invalid(), }); @@ -4912,7 +3481,7 @@ impl PassTyping { let extra_data_idx = self.poly_data.len() as PolyDataIndex; self.poly_data.push(PolyData { - expr_id: call_id.upcast(), + first_rule_application: true, definition_id: call.definition, poly_vars: poly_args, associated: parameter_types, @@ -4974,7 +3543,7 @@ impl PassTyping { let extra_data_index = self.poly_data.len() as PolyDataIndex; self.poly_data.push(PolyData { - expr_id: lit_id.upcast(), + first_rule_application: true, definition_id: literal.definition, poly_vars: poly_args, associated: embedded_types, @@ -5021,7 +3590,7 @@ impl PassTyping { let extra_data_index = self.poly_data.len() as PolyDataIndex; self.poly_data.push(PolyData { - expr_id: lit_id.upcast(), + first_rule_application: true, definition_id: literal.definition, poly_vars: poly_args, associated: Vec::new(), @@ -5082,7 +3651,7 @@ impl PassTyping { let extra_data_index = self.poly_data.len(); self.poly_data.push(PolyData { - expr_id: lit_id.upcast(), + first_rule_application: true, definition_id: literal.definition, poly_vars: poly_args, associated: embedded, @@ -5125,6 +3694,7 @@ impl PassTyping { let extra_data_index = self.poly_data.len() as PolyDataIndex; self.poly_data.push(PolyData { + first_rule_application: true, definition_id: struct_def_id, poly_vars, associated: vec![InferenceType::new(num_poly_vars != 0, num_poly_vars == 0, struct_parts)],