From 8dbdf7022aaf77ed364827c7954f05b7d73dfe12 2021-04-06 18:05:53 From: MH Date: 2021-04-06 18:05:53 Subject: [PATCH] Initial union implementation Still untested, but: make union declaration implicit (so no longer inferred from 'enum' use), and initial implementation of type inference. --- diff --git a/src/protocol/parser/type_resolver.rs b/src/protocol/parser/type_resolver.rs index 0bc1ba54cc3f44f4c478753244ab72bddfe0d484..9248f11b8c1a23825225b47e27e4f7d6fe85a59f 100644 --- a/src/protocol/parser/type_resolver.rs +++ b/src/protocol/parser/type_resolver.rs @@ -244,14 +244,12 @@ impl InferenceType { fn new(has_body_marker: bool, is_done: bool, parts: Vec) -> Self { if cfg!(debug_assertions) { debug_assert!(!parts.is_empty()); - if !has_body_marker { - debug_assert!(!parts.iter().any(|v| { - if let InferenceTypePart::MarkerBody(_) = v { true } else { false } - })); - } - if is_done { - debug_assert!(parts.iter().all(|v| v.is_concrete())); - } + let parts_body_marker = parts.iter().any(|v| { + if let InferenceTypePart::MarkerBody(_) = v { true } else { false } + }); + debug_assert_eq!(has_body_marker, parts_body_marker); + let parts_done = parts.iter().all(|v| v.is_concrete()); + debug_assert_eq!(is_done, parts_done, "{:?}", parts); } Self{ has_body_marker: has_body_marker, is_done, parts } } @@ -1231,6 +1229,16 @@ impl Visitor2 for TypeResolvingVisitor { // reason we may still have to apply inference to this // polymorphic variable self.insert_initial_enum_polymorph_data(ctx, id); + }, + Literal::Union(literal) => { + // May carry subexpressions and polymorphic arguments + // TODO: @performance + let expr_ids = literal.values.clone(); + self.insert_initial_union_polymorph_data(ctx, id); + + for expr_id in expr_ids { + self.visit_expr(ctx, expr_id)?; + } } } @@ -2112,6 +2120,93 @@ impl TypeResolvingVisitor { &ctx.heap, extra, &poly_progress, signature_type, expr_type ); + progress_expr + }, + Literal::Union(data) => { + let extra = self.extra_data.get_mut(&upcast_id).unwrap(); + for poly in &extra.poly_vars { + debug_log!(" * Poly: {}", poly.display_name(&ctx.heap)); + } + let mut poly_progress = HashSet::new(); + debug_assert_eq!(extra.embedded.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 signature_type: *mut _ = &mut extra.embedded[value_idx]; + let value_type: *mut _ = self.expr_types.get_mut(&value_expr_id).unwrap(); + 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.insert(value_expr_id); + } + } + + debug_log!(" - Field poly progress | {:?}", poly_progress); + + // Infer type of union itself + let signature_type: *mut _ = &mut extra.returned; + let expr_type: *mut _ = self.expr_types.get_mut(&upcast_id).unwrap(); + 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() { + self.expr_queued.insert(parent_id); + } + } + + debug_log!(" * During (reinferring from progress polyvars):"); + + // For all embedded values of the union variant + for value_idx in 0..extra.embedded.len() { + let signature_type: *mut _ = &mut extra.embedded[value_idx]; + let value_expr_id = data.values[value_idx]; + let value_type: *mut _ = self.expr_types.get_mut(&value_expr_id).unwrap(); + + let progress_arg = Self::apply_equal2_polyvar_constraint( + &ctx.heap, 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.insert(value_expr_id); + } + } + + // And for the union type itself + let signature_type: *mut _ = &mut extra.returned; + let expr_type: *mut _ = self.expr_types.get_mut(&upcast_id).unwrap(); + + let progress_expr = Self::apply_equal2_polyvar_constraint( + &ctx.heap, extra, &poly_progress, signature_type, expr_type + ); + progress_expr } }; @@ -2862,7 +2957,7 @@ impl TypeResolvingVisitor { } debug_assert_eq!(parts.len(), parts_reserved); - let return_type = InferenceType::new(true, return_type_done, parts); + let return_type = InferenceType::new(!poly_vars.is_empty(), return_type_done, parts); self.extra_data.insert(lit_id.upcast(), ExtraData{ poly_vars, @@ -2872,6 +2967,8 @@ impl TypeResolvingVisitor { } /// Inserts the extra polymorphic data struct for enum expressions. These + /// can never be determined from the enum itself, but may be inferred from + /// the use of the enum. fn insert_initial_enum_polymorph_data( &mut self, ctx: &Ctx, lit_id: LiteralExpressionId ) { @@ -2902,7 +2999,7 @@ impl TypeResolvingVisitor { } debug_assert_eq!(parts.len(), parts_reserved); - let enum_type = InferenceType::new(true, enum_type_done, parts); + let enum_type = InferenceType::new(!poly_vars.is_empty(), enum_type_done, parts); self.extra_data.insert(lit_id.upcast(), ExtraData{ poly_vars, @@ -2911,6 +3008,64 @@ impl TypeResolvingVisitor { }); } + /// Inserts the extra polymorphic data struct for unions. The polymorphic + /// arguments may be partially determined from embedded values in the union. + fn insert_initial_union_polymorph_data( + &mut self, ctx: &Ctx, lit_id: LiteralExpressionId + ) { + use InferenceTypePart as ITP; + let literal = ctx.heap[lit_id].value.as_union(); + + // Construct the polymorphic variables + let mut poly_vars = Vec::with_capacity(literal.poly_args2.len()); + let mut total_num_poly_parts = 0; + for poly_arg_type_id in literal.poly_args2.clone() { // TODO: @performance + let inference_type = self.determine_inference_type_from_parser_type( + ctx, poly_arg_type_id, true + ); + total_num_poly_parts += inference_type.parts.len(); + poly_vars.push(inference_type); + } + + // Handle any of the embedded values in the variant, if specified + let definition_id = literal.definition.unwrap(); + let union_definition = ctx.types.get_base_definition(&definition_id) + .unwrap() + .definition.as_union(); + let variant_definition = &union_definition.variants[literal.variant_idx]; + debug_assert_eq!(variant_definition.embedded.len(), literal.values.len()); + + let mut embedded = Vec::with_capacity(variant_definition.embedded.len()); + for embedded_id in &variant_definition.embedded { + let inference_type = self.determine_inference_type_from_parser_type( + ctx, *embedded_id, true + ); + embedded.push(inference_type); + } + + // Handle the type of the union itself + let parts_reserved = 1 + poly_vars.len() + total_num_poly_parts; + let mut parts = Vec::with_capacity(parts_reserved); + parts.push(ITP::Instance(definition_id, poly_vars.len())); + let mut union_type_done = true; + for (poly_var_idx, poly_var) in poly_vars.iter().enumerate() { + if !poly_var.is_done { union_type_done = false; } + + parts.push(ITP::MarkerBody(poly_var_idx)); + + parts.extend(poly_var.parts.iter().cloned()); + } + + debug_assert_eq!(parts_reserved, parts.len()); + let union_type = InferenceType::new(!poly_vars.is_empty(), union_type_done, parts); + + self.extra_data.insert(lit_id.upcast(), ExtraData{ + poly_vars, + embedded, + returned: union_type + }); + } + /// 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( @@ -2949,7 +3104,7 @@ impl TypeResolvingVisitor { self.extra_data.insert(select_id.upcast(), ExtraData{ poly_vars, - embedded: vec![InferenceType::new(true, false, struct_parts)], + embedded: vec![InferenceType::new(num_poly_vars != 0, num_poly_vars == 0, struct_parts)], returned: field_type }); } @@ -3185,7 +3340,7 @@ impl TypeResolvingVisitor { Method::Symbolic(symbolic) => { let definition = &ctx.heap[symbolic.definition.unwrap()]; let poly_var = match definition { - Definition::Struct(_) | Definition::Enum(_) => unreachable!(), + Definition::Struct(_) | Definition::Enum(_) | Definition::Union(_) => unreachable!(), Definition::Function(definition) => { String::from_utf8_lossy(&definition.poly_vars[poly_var_idx].value).to_string() }, @@ -3201,14 +3356,27 @@ impl TypeResolvingVisitor { fn get_poly_var_and_type_name(ctx: &Ctx, poly_var_idx: usize, definition_id: DefinitionId) -> (String, String) { let definition = &ctx.heap[definition_id]; - match definition { - Definition::Enum(_) | Definition::Function(_) | Definition::Component(_) => - unreachable!("get_poly_var_and_type_name called on non-struct value"), + let (poly_var_name, type_name) = match definition { + Definition::Function(_) | Definition::Component(_) => + unreachable!("get_poly_var_and_type_name called on unsupported type"), + Definition::Enum(definition) => ( + &definition.poly_vars[poly_var_idx].value, + &definition.identifier.value + ), Definition::Struct(definition) => ( - String::from_utf8_lossy(&definition.poly_vars[poly_var_idx].value).to_string(), - String::from_utf8_lossy(&definition.identifier.value).to_string() + &definition.poly_vars[poly_var_idx].value, + &definition.identifier.value ), - } + Definition::Union(definition) => ( + &definition.poly_vars[poly_var_idx].value, + &definition.identifier.value + ), + }; + + ( + String::from_utf8_lossy(poly_var_name).to_string(), + String::from_utf8_lossy(type_name).to_string() + ) } // Helper function to construct initial error @@ -3225,8 +3393,14 @@ impl TypeResolvingVisitor { ) }, Expression::Literal(expr) => { - let lit_struct = expr.value.as_struct(); - let (poly_var, struct_name) = get_poly_var_and_type_name(ctx, poly_var_idx, lit_struct.definition.unwrap()); + let definition_id = match &expr.value { + Literal::Struct(v) => v.definition.unwrap(), + Literal::Enum(v) => v.definition.unwrap(), + Literal::Union(v) => v.definition.unwrap(), + _ => unreachable!(), + }; + + let (poly_var, struct_name) = get_poly_var_and_type_name(ctx, poly_var_idx, definition_id); return ParseError::new_error( &ctx.module.source, expr.position(), &format!( @@ -3258,14 +3432,18 @@ impl TypeResolvingVisitor { expr.arguments.clone(), "return type" ), - Expression::Literal(expr) => - ( - expr.value.as_struct().fields - .iter() + Expression::Literal(expr) => { + let expressions = match &expr.value { + Literal::Struct(v) => v.fields.iter() .map(|f| f.value) .collect(), - "literal" - ), + Literal::Enum(_) => Vec::new(), + Literal::Union(v) => v.values.clone(), + _ => unreachable!() + }; + + ( expressions, "literal" ) + }, Expression::Select(expr) => // Select expression uses the polymorphic variables of the // struct it is accessing, so get the subject expression. @@ -3410,7 +3588,7 @@ mod tests { for (lhs, rhs) in pairs.iter() { let mut lhs_type = IT::new(false, false, lhs.clone()); - let mut rhs_type = IT::new(false, false, rhs.clone()); + let mut rhs_type = IT::new(false, true, rhs.clone()); let result = unsafe{ IT::infer_subtrees_for_both_types( &mut lhs_type, 0, &mut rhs_type, 0 ) }; @@ -3418,7 +3596,7 @@ mod tests { assert_eq!(lhs_type.parts, rhs_type.parts); let mut lhs_type = IT::new(false, false, lhs.clone()); - let rhs_type = IT::new(false, false, rhs.clone()); + let rhs_type = IT::new(false, true, rhs.clone()); let result = IT::infer_subtree_for_single_type( &mut lhs_type, 0, &rhs_type.parts, 0 ); diff --git a/src/protocol/parser/type_table.rs b/src/protocol/parser/type_table.rs index 60d2c3886e4cc8327aaaf16ef7692c78468c322b..e1735e1e230dd82a76e1e9f2d2f660457c4e71ae 100644 --- a/src/protocol/parser/type_table.rs +++ b/src/protocol/parser/type_table.rs @@ -1145,7 +1145,7 @@ impl TypeTable { fn enum_tag_type(min_tag_value: i64, max_tag_value: i64) -> PrimitiveType { // TODO: @consistency tag values should be handled correctly - debug_assert!(min_tag_value < max_tag_value); + debug_assert!(min_tag_value <= max_tag_value); let abs_max_value = min_tag_value.abs().max(max_tag_value.abs()); if abs_max_value <= u8::max_value() as i64 { PrimitiveType::Byte diff --git a/src/protocol/tests/parser_inference.rs b/src/protocol/tests/parser_inference.rs index a3eecc0b65a4ddd0e140b9942a34c4967c498e20..6855fa19d14c0253ac287c308363f9cb46b5c279 100644 --- a/src/protocol/tests/parser_inference.rs +++ b/src/protocol/tests/parser_inference.rs @@ -351,6 +351,25 @@ fn test_failed_polymorph_inference() { .assert_msg_has(2, "inferred it to 'byte'"); }); + // Cannot really test literal inference error, but this comes close + Tester::new_single_source_expect_err( + "enum literal inference mismatch", + " + enum Uninteresting{ Variant } + int fix_t(Uninteresting arg) { return 0; } + int call() { + auto a = Uninteresting::Variant; + fix_t(a); + fix_t(a); + return 4; + } + " + ).error(|e| { e + .assert_num(2) + .assert_msg_has(0, "the type 'Uninteresting'") + .assert_msg_has(1, "type 'Uninteresting'"); + }); + Tester::new_single_source_expect_err( "field access inference mismatch", " @@ -372,7 +391,7 @@ fn test_failed_polymorph_inference() { // TODO: Needs better error messages anyway, but this failed before Tester::new_single_source_expect_err( - "by nested field access", + "nested field access inference mismatch", " struct Node{ T1 l, T2 r } Node construct(T1 l, T2 r) { return Node{ l: l, r: r }; } diff --git a/src/protocol/tests/parser_validation.rs b/src/protocol/tests/parser_validation.rs index 112e6264b41ec11ead733918afbb01359437cad0..6b058569a03f21230018723fbe973c4f2fc982d1 100644 --- a/src/protocol/tests/parser_validation.rs +++ b/src/protocol/tests/parser_validation.rs @@ -85,4 +85,4 @@ fn test_correct_struct_instance() { } " ); -} \ No newline at end of file +}