From 4fcb5d4646a6e3c920caee69111415528f80f656 2022-02-21 13:36:02 From: MH Date: 2022-02-21 13:36:02 Subject: [PATCH] WIP: Refactoring to use TypeIDs and InferIndices --- diff --git a/src/collections/scoped_buffer.rs b/src/collections/scoped_buffer.rs index 7f5194cf31bc6ef317490d82f6dc413fb07e2272..518c889433f8045e9c80d5ce3862414e60c38369 100644 --- a/src/collections/scoped_buffer.rs +++ b/src/collections/scoped_buffer.rs @@ -73,54 +73,80 @@ pub(crate) struct ScopedSection { } impl ScopedSection { + /// Pushes value into section #[inline] pub(crate) fn push(&mut self, value: T) { + self.check_length(); let vec = unsafe{&mut *self.inner}; - hide!(debug_assert_eq!( - vec.len(), self.cur_size as usize, - "trying to push onto section, but size is larger than expected" - )); vec.push(value); hide!(self.cur_size += 1); } #[inline] pub(crate) fn len(&self) -> usize { + self.check_length(); let vec = unsafe{&mut *self.inner}; - hide!(debug_assert_eq!( - vec.len(), self.cur_size as usize, - "trying to get section length, but size is larger than expected" - )); return vec.len() - self.start_size as usize; } #[inline] #[allow(unused_mut)] // used in debug mode pub(crate) fn forget(mut self) { + self.check_length(); let vec = unsafe{&mut *self.inner}; - hide!({ - debug_assert_eq!( - vec.len(), self.cur_size as usize, - "trying to forget section, but size is larger than expected" - ); - self.cur_size = self.start_size; - }); + hide!(self.cur_size = self.start_size); vec.truncate(self.start_size as usize); } #[inline] #[allow(unused_mut)] // used in debug mode pub(crate) fn into_vec(mut self) -> Vec { + self.check_length(); let vec = unsafe{&mut *self.inner}; + hide!(self.cur_size = self.start_size); + let section = Vec::from_iter(vec.drain(self.start_size as usize..)); + section + } + + #[inline] + pub(crate) fn check_length(&self) { hide!({ + let vec = unsafe{&*self.inner}; debug_assert_eq!( vec.len(), self.cur_size as usize, - "trying to turn section into vec, but size is larger than expected" - ); - self.cur_size = self.start_size; - }); - let section = Vec::from_iter(vec.drain(self.start_size as usize..)); - section + "incorrect use of ScopedSection: underlying storage vector has changed size" + ) + }) + } +} + +impl ScopedSection { + #[inline] + pub(crate) fn push_unique(&mut self, value: T) { + self.check_length(); + let vec = unsafe{&mut *self.inner}; + for item in &vec[self.start_size as usize..] { + if *item == value { + // item already exists + return; + } + } + + vec.push(value); + hide!(self.cur_size += 1); + } + + #[inline] + pub(crate) fn contains(&self, value: &T) -> bool { + self.check_length(); + let vec = unsafe{&*self.inner}; + for index in self.start_size..vec.len() { + if vec[index] == value { + return true; + } + } + + return false; } } diff --git a/src/protocol/parser/pass_typing.rs b/src/protocol/parser/pass_typing.rs index 2373bfe14c4e0f4fe9614d12aa949eb1eef46a39..78a48d4fd57c4119c169cdbc1927f0766d2ca50a 100644 --- a/src/protocol/parser/pass_typing.rs +++ b/src/protocol/parser/pass_typing.rs @@ -880,7 +880,7 @@ impl InferenceRule { union_cast_method_impl!(as_indexing_expr, InferenceRuleIndexingExpr, InferenceRule::IndexingExpr); union_cast_method_impl!(as_slicing_expr, InferenceRuleSlicingExpr, InferenceRule::SlicingExpr); union_cast_method_impl!(as_select_struct_field, InferenceRuleSelectStructField, InferenceRule::SelectStructField); - union_cast_method_impl!(as_select_union_member, InferenceRuleSelectTupleMember, InferenceRule::SelectTupleMember); + union_cast_method_impl!(as_select_tuple_member, InferenceRuleSelectTupleMember, InferenceRule::SelectTupleMember); } struct InferenceRuleTemplate { @@ -1026,6 +1026,7 @@ pub(crate) struct PassTyping { stmt_buffer: ScopedBuffer, bool_buffer: ScopedBuffer, index_buffer: ScopedBuffer, + poly_progress_buffer: ScopedBuffer, // 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 @@ -1064,6 +1065,7 @@ impl Default for PolyData { } } +#[derive(Clone, Copy)] enum PolyDataTypeIndex { Associated(usize), // indexes into `PolyData.associated` Returned, @@ -1115,6 +1117,7 @@ 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), + poly_progress_buffer: ScopedBuffer::with_capacity(BUFFER_INIT_CAP_SMALL), var_types: HashMap::new(), infer_nodes: Vec::new(), poly_data: Vec::new(), @@ -2355,61 +2358,80 @@ impl PassTyping { // If here then the field index is known, hence we can start inferring // the type of the selected field - let node = &self.infer_nodes[node_index]; - let poly_data = &mut self.poly_data[node.poly_data_index 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 field_expr_id = self.infer_nodes[node_index].expr_id; + let subject_expr_id = self.infer_nodes[subject_index].expr_id; + let mut poly_progress_section = self.poly_progress_buffer.start_section(); - 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_1) = self.apply_polydata_equal2_constraint( + ctx, node_index, subject_expr_id, "selected struct's", + PolyDataTypeIndex::Associated(0), 0, subject_index, 0, &mut poly_progress_section + )?; + let (_, progress_field_1) = self.apply_polydata_equal2_constraint( + ctx, node_index, field_expr_id, "selected field's", + PolyDataTypeIndex::Returned, 0, node_index, 0, &mut poly_progress_section )?; - 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; + // Maybe make progress on types due to inferred polymorphic variables + let progress_subject_2 = self.apply_polydata_polyvar_constraint( + ctx, node_index, PolyDataTypeIndex::Associated(0), subject_index, &poly_progress_section + ); + let progress_field_2 = self.apply_polydata_polyvar_constraint( + ctx, node_index, PolyDataTypeIndex::Returned, node_index, &poly_progress_section + ); - 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_subject_1 || progress_subject_2 { self.queue_node(subject_index); } + if progress_field_1 || progress_field_2 { self.queue_node_parent(node_index); } - 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); - } - } + return Ok(()) + } - // 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; + fn progress_inference_rule_select_tuple_member(&mut self, ctx: &mut Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> { + let node = &self.infer_nodes[node_index]; + let rule = node.inference_rule.as_select_tuple_member(); + let subject_index = rule.subject_index; + let tuple_member_index = rule.selected_index; - let progress_subject = Self::apply_equal2_polyvar_constraint( - poly_data, &poly_progress, signature_type, subject_type - ); + fn get_tuple_size_from_inference_type(inference_type: &InferenceType) -> Result, ()> { + for part in &inference_type.parts { + if part.is_marker() { continue; } + if !part.is_concrete() { break; } - let signature_type: *mut _ = &mut poly_data.returned; - let expr_type: *mut _ = &mut self.infer_nodes[expr_idx as usize].expr_type; + if let InferenceTypePart::Tuple(size) = part { + return Ok(Some(*size)); + } else { + return Err(()); // not a tuple! + } + } - let progress_expr = Self::apply_equal2_polyvar_constraint( - poly_data, &poly_progress, signature_type, expr_type - ); + return Ok(None); + } - (progress_subject, progress_expr) + if node.field_or_monomorph_index < 0 { + let subject_type = &self.infer_nodes[subject_index].expr_type; + let tuple_size = get_tuple_size_from_inference_type(subject_type); + let tuple_size = match tuple_size { + Ok(Some(tuple_size)) => { + tuple_size + }, + Ok(None) => { + // We can't infer anything yet + return Ok(()) + }, + Err(()) => { + let select_expr_span = ctx.heap[node.expr_id].full_span(); + return Err(ParseError::new_error_at_span( + &ctx.module().source, select_expr_span, format!( + "tuple element select cannot be applied to a subject of type '{}'", + subject_type.display_name(&ctx.heap) + ) + )); + } + }; - return Ok(()) - } - fn progress_inference_rule_select_tuple_member(&mut self, ctx: &mut Ctx, node_index: InferNodeIndex) -> Result<(), ParseError> { + } + return Ok(()) } fn progress_template(&mut self, ctx: &Ctx, node_index: InferNodeIndex, application: InferenceRuleTemplateApplication, template: &[InferenceTypePart]) -> Result { @@ -3803,20 +3825,26 @@ impl PassTyping { /// the expression that constructs the value of a struct field). Hence the /// "associated" variables. /// - /// Again a special case: the `associated_expr_id` is only used + /// Finally, when an error occurs we'll first show the outer node's + /// location. As info, the `error_location_expr_id` span is shown, + /// indicating that the "`error_type_name` type has been resolved to + /// `outer_node_type`, but this expression has been resolved to + /// `associated_node_type`". fn apply_polydata_equal2_constraint( &mut self, ctx: &Ctx, - outer_node_index: InferNodeIndex, error_location_expr_id: ExpressionId, error_location_name: &str - poly_data_type: PolyDataTypeIndex, poly_data_start_index: usize, - associated_node_index: InferNodeIndex, associated_node_start_index: usize + outer_node_index: InferNodeIndex, error_location_expr_id: ExpressionId, error_type_name: &str, + poly_data_type_index: PolyDataTypeIndex, poly_data_start_index: usize, + associated_node_index: InferNodeIndex, associated_node_start_index: usize, + poly_progress_section: &mut ScopedSection, ) -> Result<(bool, bool), ParseError> { - let poly_index = self.infer_nodes[outer_node_index].poly_data_index; - let poly_data_type: *mut _ = self.poly_data[poly_index].get_type_mut(poly_data_type); + let poly_data_index = self.infer_nodes[outer_node_index].poly_data_index; + let poly_data_type = self.poly_data[poly_data_index].get_type_mut(poly_data_type_index); let associated_type: *mut _ = &mut self.infer_nodes[associated_node_index].expr_type; let inference_result = unsafe{ // Safety: pointers originate from different vectors, so cannot // alias. + let poly_data_type: *mut _ = poly_data_type; InferenceType::infer_subtrees_for_both_types( poly_data_type, poly_data_start_index, associated_type, associated_node_start_index @@ -3828,12 +3856,121 @@ impl PassTyping { if inference_result == DualInferenceResult::Incompatible { let outer_node_expr_id = self.infer_nodes[outer_node_index].expr_id; let outer_node_span = ctx.heap[outer_node_expr_id].full_span(); - let detailed_span = ctx.heap[error_location_expr_id]. + let detailed_span = ctx.heap[error_location_expr_id].full_span(); + + let outer_node_type = poly_data_type.display_name(&ctx.heap); + let associated_type = self.infer_nodes[associated_node_index].expr_type.display_name(&ctx.heap); + + let source = &ctx.module().source; + return Err(ParseError::new_error_str_at_span( + source, outer_node_span, "failed to resolve the types of this expression" + ).with_info_str_at_span( + source, detailed_span, &format!( + "because the {} type has been resolved to '{}', but this expression has been resolved to '{}'", + error_type_name, outer_node_type, associated_type + ) + )); } + + if modified_poly_data { + debug_assert!(poly_data_type.has_marker); + + // Go through markers for polymorphic variables and use the + // (hopefully) more specific types to update their representation + // in the PolyData struct + for (poly_var_index, poly_var_section) in poly_data_type.marker_iter() { + let poly_var_type = &mut self.poly_data[poly_data_index].poly_vars[poly_var_index as usize]; + match InferenceType::infer_subtree_for_single_type(poly_var_type, 0, poly_var_section, 0, false) { + SingleInferenceResult::Modified => { + poly_progress_section.push_unique(poly_var_index); + }, + SingleInferenceResult::Unmodified => { + // nothing to do + }, + SingleInferenceResult::Incompatible => { + return Err(Self::construct_poly_arg_error( + ctx, &self.poly_data[poly_data_index], + self.infer_nodes[outer_node_index].expr_id + )); + } + } + } + } + + return Ok((modified_poly_data, modified_associated)); } - fn apply_polydata_polyvar_constraint() -> bool { + /// After calling `apply_polydata_equal2_constraint` on several expressions + /// that are associated with some kind of polymorphic expression, several of + /// the polymorphic variables might have been inferred to more specific + /// types than before. + /// + /// At this point one should call this function to apply the progress in + /// these polymorphic variables back onto the types that are functions of + /// these polymorphic variables. + /// + /// An example: a struct literal with a polymorphic variable `T` may have + /// two fields `foo` and `bar` each with different types that are a function + /// of the polymorhic variable `T`. If the expressions constructing the + /// value for the field `foo` causes the type `T` to progress, then we can + /// also progress the type of the expression that constructs `bar`. + /// + /// And so we have `outer_node_index` + `poly_data_type_index` pointing to + /// the appropriate type in the `PolyData` struct. Which will be updated + /// first using the polymorphic variables. If we happen to have updated that + /// type, then we should also progress the associated expression, hence the + /// `associated_node_index`. + fn apply_polydata_polyvar_constraint( + &mut self, ctx: &Ctx, + outer_node_index: InferNodeIndex, poly_data_type_index: PolyDataTypeIndex, + associated_node_index: InferNodeIndex, poly_progress_section: &ScopedSection + ) -> bool { + let poly_data_index = self.infer_nodes[outer_node_index].poly_data_index; + let poly_data = &mut self.poly_data[poly_data_index]; + + // safety: we're borrowing from two distinct fields, so should be fine + let poly_data_type = poly_data.get_type_mut(poly_data_type_index); + let mut last_start_index = 0; + let mut modified_poly_type = false; + + while let Some((poly_var_index, poly_var_start_index)) = poly_data_type.find_marker(last_start_index) { + let poly_var_end_index = InferenceType::find_subtree_end_idx(&poly_data_type.parts, poly_var_start_index); + if poly_progress_section.contains(&poly_var_index) { + // We have updated this polymorphic variable, so try updating it + // in the PolyData type + let modified_in_poly_data = match InferenceType::infer_subtree_for_single_type( + poly_data_type, poly_var_start_index, &poly_data.poly_vars[poly_var_index as usize].parts, 0, false + ) { + SingleInferenceResult::Modified => true, + SingleInferenceResult::Unmodified => false, + SingleInferenceResult::Incompatible => { + // practically impossible: before calling this function we gather all the + // data on the polymorphic variables from the associated expressions. So if + // the polymorphic variables in those expressions were not mutually + // compatible, we must have encountered that error already. + unreachable!() + }, + }; + modified_poly_type = modified_poly_type || modified_in_poly_data; + } + + last_start_index = poly_var_end_index; + } + + if modified_poly_type { + let associated_type = &mut self.infer_nodes[associated_node_index].expr_type; + match InferenceType::infer_subtree_for_single_type( + associated_type, 0, &poly_data_type.parts, 0, true + ) { + SingleInferenceResult::Modified => return true, + SingleInferenceResult::Unmodified => return false, + SingleInferenceResult::Incompatible => unreachable!(), // same as above + } + } else { + // Did not update associated type + return false; + } } /// Applies an equal2 constraint between a signature type (e.g. a function