Merge #839

839: Add typechecking for match-expr r=philberty a=philberty

This adds in the type checking pass for the match expression including static
analysis for errors such as:

 - error[E0532]: expected tuple struct or tuple variant, found struct variant `Foo::D`
 - error[E0027]: pattern does not mention fields `x`, `y`
 - error[E0026]: variant `Foo::D` does not have a field named `b`
 - error[E0532]: expected tuple struct or tuple variant, found struct variant `Foo::D`

Addresses #190 

Co-authored-by: Philip Herron <philip.herron@embecosm.com>

13 files changed, 474 insertions, 12 deletions

diff --git a/gcc/rust/Make-lang.in b/gcc/rust/Make-lang.in
index 1274578..391151f 100644
--- a/gcc/rust/Make-lang.in
+++ b/gcc/rust/Make-lang.in
@@ -89,6 +89,7 @@ GRS_OBJS = \
     rust/rust-hir-type-check-type.o \
     rust/rust-hir-type-check-struct.o \
     rust/rust-hir-address-taken.o \
+    rust/rust-hir-type-check-pattern.o \
     rust/rust-substitution-mapper.o \
     rust/rust-lint-marklive.o \
     rust/rust-hir-type-check-path.o \
diff --git a/gcc/rust/hir/tree/rust-hir-expr.h b/gcc/rust/hir/tree/rust-hir-expr.h
index 0e5d97b..e50e210 100644
--- a/gcc/rust/hir/tree/rust-hir-expr.h
+++ b/gcc/rust/hir/tree/rust-hir-expr.h
@@ -3614,15 +3614,9 @@ struct MatchArm
 {
 private:
   AST::AttrVec outer_attrs;
-  // MatchArmPatterns patterns;
-  std::vector<std::unique_ptr<Pattern> > match_arm_patterns; // inlined
-
-  // bool has_match_arm_guard;
-  // inlined from MatchArmGuard
+  std::vector<std::unique_ptr<Pattern> > match_arm_patterns;
   std::unique_ptr<Expr> guard_expr;
 
-  // TODO: should this store location data?
-
 public:
   // Returns whether the MatchArm has a match arm guard expression
   bool has_match_arm_guard () const { return guard_expr != nullptr; }
@@ -3679,6 +3673,11 @@ public:
   }
 
   std::string as_string () const;
+
+  std::vector<std::unique_ptr<Pattern> > &get_patterns ()
+  {
+    return match_arm_patterns;
+  }
 };
 
 /* A "match case" - a correlated match arm and resulting expression. Not
@@ -3718,6 +3717,9 @@ public:
   std::string as_string () const;
 
   Analysis::NodeMapping get_mappings () const { return mappings; }
+
+  MatchArm &get_arm () { return arm; }
+  std::unique_ptr<Expr> &get_expr () { return expr; }
 };
 
 #if 0
@@ -3868,6 +3870,15 @@ public:
 
   void accept_vis (HIRVisitor &vis) override;
 
+  std::unique_ptr<Expr> &get_scrutinee_expr ()
+  {
+    rust_assert (branch_value != nullptr);
+    return branch_value;
+  }
+
+  const std::vector<MatchCase> &get_match_cases () const { return match_arms; }
+  std::vector<MatchCase> &get_match_cases () { return match_arms; }
+
 protected:
   /* Use covariance to implement clone function as returning this object rather
    * than base */
diff --git a/gcc/rust/resolve/rust-ast-resolve-pattern.cc b/gcc/rust/resolve/rust-ast-resolve-pattern.cc
index c97a83f..f355541 100644
--- a/gcc/rust/resolve/rust-ast-resolve-pattern.cc
+++ b/gcc/rust/resolve/rust-ast-resolve-pattern.cc
@@ -49,7 +49,7 @@ PatternDeclaration::visit (AST::TupleStructPattern &pattern)
 	for (auto &inner_pattern : items_no_range.get_patterns ())
 	  {
 	    PatternDeclaration::go (inner_pattern.get (),
-				    pattern.get_node_id ());
+				    inner_pattern->get_pattern_node_id ());
 	  }
       }
       break;
@@ -85,10 +85,10 @@ PatternDeclaration::visit (AST::StructPattern &pattern)
 	    resolver->get_name_scope ().insert (
 	      CanonicalPath::new_seg (ident.get_node_id (),
 				      ident.get_identifier ()),
-	      ident.get_node_id (), pattern.get_locus ());
-	    resolver->insert_new_definition (
-	      ident.get_node_id (),
-	      Definition{ident.get_node_id (), pattern.get_node_id ()});
+	      ident.get_node_id (), ident.get_locus ());
+	    resolver->insert_new_definition (ident.get_node_id (),
+					     Definition{ident.get_node_id (),
+							ident.get_node_id ()});
 	    resolver->mark_decl_mutability (ident.get_node_id (),
 					    ident.is_mut ());
 	  }
diff --git a/gcc/rust/typecheck/rust-hir-type-check-expr.h b/gcc/rust/typecheck/rust-hir-type-check-expr.h
index 1015cc2..8de736d 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-expr.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-expr.h
@@ -32,6 +32,7 @@
 #include "rust-hir-type-bounds.h"
 #include "rust-hir-dot-operator.h"
 #include "rust-hir-address-taken.h"
+#include "rust-hir-type-check-pattern.h"
 
 namespace Rust {
 namespace Resolver {
@@ -51,6 +52,9 @@ public:
 
     if (resolver.infered == nullptr)
       {
+	// FIXME
+	// this is an internal error message for debugging and should be removed
+	// at some point
 	rust_error_at (expr->get_locus (), "failed to type resolve expression");
 	return new TyTy::ErrorType (expr->get_mappings ().get_hirid ());
       }
@@ -540,6 +544,8 @@ public:
 	Definition def;
 	if (!resolver->lookup_definition (ref_node_id, &def))
 	  {
+	    // FIXME
+	    // this is an internal error
 	    rust_error_at (expr.get_locus (),
 			   "unknown reference for resolved name");
 	    return;
@@ -548,6 +554,8 @@ public:
       }
     else if (!resolver->lookup_resolved_type (ast_node_id, &ref_node_id))
       {
+	// FIXME
+	// this is an internal error
 	rust_error_at (expr.get_locus (),
 		       "Failed to lookup type reference for node: %s",
 		       expr.as_string ().c_str ());
@@ -556,6 +564,8 @@ public:
 
     if (ref_node_id == UNKNOWN_NODEID)
       {
+	// FIXME
+	// this is an internal error
 	rust_error_at (expr.get_locus (), "unresolved node: %s",
 		       expr.as_string ().c_str ());
 	return;
@@ -566,6 +576,8 @@ public:
     if (!mappings->lookup_node_to_hir (expr.get_mappings ().get_crate_num (),
 				       ref_node_id, &ref))
       {
+	// FIXME
+	// this is an internal error
 	rust_error_at (expr.get_locus (), "123 reverse lookup failure");
 	return;
       }
@@ -574,6 +586,8 @@ public:
     TyTy::BaseType *lookup;
     if (!context->lookup_type (ref, &lookup))
       {
+	// FIXME
+	// this is an internal error
 	rust_error_at (mappings->lookup_location (ref),
 		       "Failed to resolve IdentifierExpr type: %s",
 		       expr.as_string ().c_str ());
@@ -1265,6 +1279,50 @@ public:
     infered = expr_to_convert->cast (tyty_to_convert_to);
   }
 
+  void visit (HIR::MatchExpr &expr) override
+  {
+    // this needs to perform a least upper bound coercion on the blocks and then
+    // unify the scruintee and arms
+    TyTy::BaseType *scrutinee_tyty
+      = TypeCheckExpr::Resolve (expr.get_scrutinee_expr ().get (), false);
+
+    std::vector<TyTy::BaseType *> kase_block_tys;
+    for (auto &kase : expr.get_match_cases ())
+      {
+	// lets check the arms
+	HIR::MatchArm &kase_arm = kase.get_arm ();
+	for (auto &pattern : kase_arm.get_patterns ())
+	  {
+	    TyTy::BaseType *kase_arm_ty
+	      = TypeCheckPattern::Resolve (pattern.get ());
+
+	    TyTy::BaseType *checked_kase = scrutinee_tyty->unify (kase_arm_ty);
+	    if (checked_kase->get_kind () == TyTy::TypeKind::ERROR)
+	      return;
+	  }
+
+	// check the kase type
+	TyTy::BaseType *kase_block_ty
+	  = TypeCheckExpr::Resolve (kase.get_expr ().get (), false);
+	kase_block_tys.push_back (kase_block_ty);
+      }
+
+    if (kase_block_tys.size () == 0)
+      {
+	infered = new TyTy::TupleType (expr.get_mappings ().get_hirid ());
+	return;
+      }
+
+    infered = kase_block_tys.at (0);
+    for (size_t i = 1; i < kase_block_tys.size (); i++)
+      {
+	TyTy::BaseType *kase_ty = kase_block_tys.at (i);
+	infered = infered->unify (kase_ty);
+	if (infered->get_kind () == TyTy::TypeKind::ERROR)
+	  return;
+      }
+  }
+
 protected:
   bool
   resolve_operator_overload (Analysis::RustLangItem::ItemType lang_item_type,
diff --git a/gcc/rust/typecheck/rust-hir-type-check-pattern.cc b/gcc/rust/typecheck/rust-hir-type-check-pattern.cc
new file mode 100644
index 0000000..2b93958
--- /dev/null
+++ b/gcc/rust/typecheck/rust-hir-type-check-pattern.cc
@@ -0,0 +1,223 @@
+// Copyright (C) 2020-2021 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC is free software; you can redistribute it and/or modify it under
+// the terms of the GNU General Public License as published by the Free
+// Software Foundation; either version 3, or (at your option) any later
+// version.
+
+// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY; without even the implied warranty of MERCHANTABILITY or
+// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+// for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include "rust-hir-type-check-pattern.h"
+#include "rust-hir-type-check-expr.h"
+
+namespace Rust {
+namespace Resolver {
+
+void
+TypeCheckPattern::visit (HIR::PathInExpression &pattern)
+{
+  infered = TypeCheckExpr::Resolve (&pattern, false);
+}
+
+void
+TypeCheckPattern::visit (HIR::TupleStructPattern &pattern)
+{
+  infered = TypeCheckExpr::Resolve (&pattern.get_path (), false);
+  if (infered->get_kind () == TyTy::TypeKind::ERROR)
+    return;
+
+  rust_assert (infered->get_kind () == TyTy::TypeKind::ADT);
+  TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (infered);
+  rust_assert (adt->is_enum ());
+
+  // what variant is this?
+  HirId variant_id;
+  bool ok = context->lookup_variant_definition (
+    pattern.get_path ().get_mappings ().get_hirid (), &variant_id);
+  rust_assert (ok);
+
+  TyTy::VariantDef *variant = nullptr;
+  ok = adt->lookup_variant_by_id (variant_id, &variant);
+  rust_assert (ok);
+
+  // error[E0532]: expected tuple struct or tuple variant, found struct variant
+  // `Foo::D`
+  if (variant->get_variant_type () != TyTy::VariantDef::VariantType::TUPLE)
+    {
+      std::string variant_type
+	= TyTy::VariantDef::variant_type_string (variant->get_variant_type ());
+
+      rust_error_at (
+	pattern.get_locus (),
+	"expected tuple struct or tuple variant, found %s variant %s::%s",
+	variant_type.c_str (), adt->get_name ().c_str (),
+	variant->get_identifier ().c_str ());
+      return;
+    }
+
+  // check the elements
+  // error[E0023]: this pattern has 2 fields, but the corresponding tuple
+  // variant has 1 field
+  // error[E0023]: this pattern has 0 fields, but the corresponding tuple
+  // variant has 1 field
+
+  std::unique_ptr<HIR::TupleStructItems> &items = pattern.get_items ();
+  switch (items->get_item_type ())
+    {
+      case HIR::TupleStructItems::RANGE: {
+	// TODO
+	gcc_unreachable ();
+      }
+      break;
+
+      case HIR::TupleStructItems::NO_RANGE: {
+	HIR::TupleStructItemsNoRange &items_no_range
+	  = static_cast<HIR::TupleStructItemsNoRange &> (*items.get ());
+
+	if (items_no_range.get_patterns ().size () != variant->num_fields ())
+	  {
+	    rust_error_at (pattern.get_locus (),
+			   "this pattern has %lu fields but the corresponding "
+			   "tuple variant has %lu field",
+			   items_no_range.get_patterns ().size (),
+			   variant->num_fields ());
+	    // we continue on to try and setup the types as best we can for
+	    // type checking
+	  }
+
+	// iterate the fields and set them up, I wish we had ZIP
+	size_t i = 0;
+	for (auto &pattern : items_no_range.get_patterns ())
+	  {
+	    if (i >= variant->num_fields ())
+	      break;
+
+	    TyTy::StructFieldType *field = variant->get_field_at_index (i++);
+	    TyTy::BaseType *fty = field->get_field_type ();
+
+	    // setup the type on this pattern type
+	    context->insert_type (pattern->get_pattern_mappings (), fty);
+	  }
+      }
+      break;
+    }
+}
+
+void
+TypeCheckPattern::visit (HIR::StructPattern &pattern)
+{
+  infered = TypeCheckExpr::Resolve (&pattern.get_path (), false);
+  if (infered->get_kind () == TyTy::TypeKind::ERROR)
+    return;
+
+  rust_assert (infered->get_kind () == TyTy::TypeKind::ADT);
+  TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (infered);
+  rust_assert (adt->is_enum ());
+
+  // what variant is this?
+  HirId variant_id;
+  bool ok = context->lookup_variant_definition (
+    pattern.get_path ().get_mappings ().get_hirid (), &variant_id);
+  rust_assert (ok);
+
+  TyTy::VariantDef *variant = nullptr;
+  ok = adt->lookup_variant_by_id (variant_id, &variant);
+  rust_assert (ok);
+
+  // error[E0532]: expected tuple struct or tuple variant, found struct variant
+  // `Foo::D`
+  if (variant->get_variant_type () != TyTy::VariantDef::VariantType::STRUCT)
+    {
+      std::string variant_type
+	= TyTy::VariantDef::variant_type_string (variant->get_variant_type ());
+      rust_error_at (pattern.get_locus (),
+		     "expected struct variant, found %s variant %s",
+		     variant_type.c_str (),
+		     variant->get_identifier ().c_str ());
+      return;
+    }
+
+  // check the elements
+  // error[E0027]: pattern does not mention fields `x`, `y`
+  // error[E0026]: variant `Foo::D` does not have a field named `b`
+
+  std::vector<std::string> named_fields;
+  auto &struct_pattern_elems = pattern.get_struct_pattern_elems ();
+  for (auto &field : struct_pattern_elems.get_struct_pattern_fields ())
+    {
+      switch (field->get_item_type ())
+	{
+	  case HIR::StructPatternField::ItemType::TUPLE_PAT: {
+	    // TODO
+	    gcc_unreachable ();
+	  }
+	  break;
+
+	  case HIR::StructPatternField::ItemType::IDENT_PAT: {
+	    // TODO
+	    gcc_unreachable ();
+	  }
+	  break;
+
+	  case HIR::StructPatternField::ItemType::IDENT: {
+	    HIR::StructPatternFieldIdent &ident
+	      = static_cast<HIR::StructPatternFieldIdent &> (*field.get ());
+
+	    TyTy::StructFieldType *field = nullptr;
+	    if (!variant->lookup_field (ident.get_identifier (), &field,
+					nullptr))
+	      {
+		rust_error_at (ident.get_locus (),
+			       "variant %s does not have a field named %s",
+			       variant->get_identifier ().c_str (),
+			       ident.get_identifier ().c_str ());
+		break;
+	      }
+	    named_fields.push_back (ident.get_identifier ());
+
+	    // setup the type on this pattern
+	    TyTy::BaseType *fty = field->get_field_type ();
+	    context->insert_type (ident.get_mappings (), fty);
+	  }
+	  break;
+	}
+    }
+
+  if (named_fields.size () != variant->num_fields ())
+    {
+      std::map<std::string, bool> missing_names;
+
+      // populate with all fields
+      for (auto &field : variant->get_fields ())
+	missing_names[field->get_name ()] = true;
+
+      // then eliminate with named_fields
+      for (auto &named : named_fields)
+	missing_names.erase (named);
+
+      // then get the list of missing names
+      size_t i = 0;
+      std::string missing_fields_str;
+      for (auto it = missing_names.begin (); it != missing_names.end (); it++)
+	{
+	  bool has_next = (i + 1) < missing_names.size ();
+	  missing_fields_str += it->first + (has_next ? ", " : "");
+	  i++;
+	}
+
+      rust_error_at (pattern.get_locus (), "pattern does not mention fields %s",
+		     missing_fields_str.c_str ());
+    }
+}
+
+} // namespace Resolver
+} // namespace Rust
diff --git a/gcc/rust/typecheck/rust-hir-type-check-pattern.h b/gcc/rust/typecheck/rust-hir-type-check-pattern.h
new file mode 100644
index 0000000..ac348fb
--- /dev/null
+++ b/gcc/rust/typecheck/rust-hir-type-check-pattern.h
@@ -0,0 +1,60 @@
+// Copyright (C) 2020-2021 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC is free software; you can redistribute it and/or modify it under
+// the terms of the GNU General Public License as published by the Free
+// Software Foundation; either version 3, or (at your option) any later
+// version.
+
+// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY; without even the implied warranty of MERCHANTABILITY or
+// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+// for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef RUST_HIR_TYPE_CHECK_PATTERN
+#define RUST_HIR_TYPE_CHECK_PATTERN
+
+#include "rust-hir-type-check-base.h"
+#include "rust-hir-full.h"
+
+namespace Rust {
+namespace Resolver {
+
+class TypeCheckPattern : public TypeCheckBase
+{
+  using Rust::Resolver::TypeCheckBase::visit;
+
+public:
+  static TyTy::BaseType *Resolve (HIR::Pattern *pattern)
+  {
+    TypeCheckPattern resolver;
+    pattern->accept_vis (resolver);
+
+    // FIXME need to check how we do mappings here
+    if (resolver.infered == nullptr)
+      return new TyTy::ErrorType (1);
+
+    return resolver.infered;
+  }
+
+  void visit (HIR::PathInExpression &pattern) override;
+
+  void visit (HIR::StructPattern &pattern) override;
+
+  void visit (HIR::TupleStructPattern &pattern) override;
+
+private:
+  TypeCheckPattern () : TypeCheckBase (), infered (nullptr) {}
+
+  TyTy::BaseType *infered;
+};
+
+} // namespace Resolver
+} // namespace Rust
+
+#endif // RUST_HIR_TYPE_CHECK_PATTERN
diff --git a/gcc/rust/typecheck/rust-tyty.h b/gcc/rust/typecheck/rust-tyty.h
index 3cedba8..012e846 100644
--- a/gcc/rust/typecheck/rust-tyty.h
+++ b/gcc/rust/typecheck/rust-tyty.h
@@ -1018,6 +1018,21 @@ public:
     STRUCT
   };
 
+  static std::string variant_type_string (VariantType type)
+  {
+    switch (type)
+      {
+      case NUM:
+	return "enumeral";
+      case TUPLE:
+	return "tuple";
+      case STRUCT:
+	return "struct";
+      }
+    gcc_unreachable ();
+    return "";
+  }
+
   VariantDef (HirId id, std::string identifier, int discriminant)
     : id (id), identifier (identifier), discriminant (discriminant)
   {
diff --git a/gcc/testsuite/rust/compile/match1.rs b/gcc/testsuite/rust/compile/match1.rs
new file mode 100644
index 0000000..f649f3a
--- /dev/null
+++ b/gcc/testsuite/rust/compile/match1.rs
@@ -0,0 +1,16 @@
+enum Foo {
+    A,
+    B,
+    C(char),
+    D { x: i64, y: i64 },
+}
+
+fn inspect(f: Foo) {
+    match f {
+        Foo::A => {}
+        Foo::B => {}
+        Foo::C(a, b) => {}
+        // { dg-error "this pattern has 2 fields but the corresponding tuple variant has 1 field" "" { target *-*-* } .-1 }
+        Foo::D { x, y } => {}
+    }
+}
diff --git a/gcc/testsuite/rust/compile/match2.rs b/gcc/testsuite/rust/compile/match2.rs
new file mode 100644
index 0000000..359936a
--- /dev/null
+++ b/gcc/testsuite/rust/compile/match2.rs
@@ -0,0 +1,15 @@
+enum Foo {
+    A,
+    B,
+    C(char),
+    D { x: i64, y: i64 },
+}
+
+fn inspect(f: Foo) {
+    match f {
+        Foo::A => {}
+        Foo::B => {}
+        Foo::C(x) => {}
+        Foo::D { y } => {} // { dg-error "pattern does not mention fields x" }
+    }
+}
diff --git a/gcc/testsuite/rust/compile/match3.rs b/gcc/testsuite/rust/compile/match3.rs
new file mode 100644
index 0000000..98181e8
--- /dev/null
+++ b/gcc/testsuite/rust/compile/match3.rs
@@ -0,0 +1,16 @@
+enum Foo {
+    A,
+    B,
+    C(char),
+    D { x: i64, y: i64 },
+}
+
+fn inspect(f: Foo) {
+    match f {
+        Foo::A => {}
+        Foo::B => {}
+        Foo::C(x) => {}
+        Foo::D { z } => {} // { dg-error "variant D does not have a field named z" }
+                           // { dg-error "pattern does not mention fields x, y" "" { target *-*-* } .-1 }
+    }
+}
diff --git a/gcc/testsuite/rust/compile/match4.rs b/gcc/testsuite/rust/compile/match4.rs
new file mode 100644
index 0000000..35b90a6
--- /dev/null
+++ b/gcc/testsuite/rust/compile/match4.rs
@@ -0,0 +1,16 @@
+enum Foo {
+    A,
+    B,
+    C(char),
+    D { x: i64, y: i64 },
+}
+
+fn inspect(f: Foo) {
+    match f {
+        Foo::A => {}
+        Foo::B => {}
+        Foo::C { a } => {}
+        // { dg-error "expected struct variant, found tuple variant C" "" { target *-*-* } .-1 }
+        Foo::D { x, y } => {}
+    }
+}
diff --git a/gcc/testsuite/rust/compile/match5.rs b/gcc/testsuite/rust/compile/match5.rs
new file mode 100644
index 0000000..6f3d6e4
--- /dev/null
+++ b/gcc/testsuite/rust/compile/match5.rs
@@ -0,0 +1,15 @@
+enum Foo {
+    A,
+    B,
+    C(char),
+    D { x: i64, y: i64 },
+}
+
+fn inspect(f: Foo) {
+    match f {
+        Foo::A => {}
+        Foo::B => {}
+        Foo::C(a) => {}
+        Foo::D(x, y) => {} // { dg-error "expected tuple struct or tuple variant, found struct variant Foo::D" }
+    }
+}
diff --git a/gcc/testsuite/rust/compile/torture/match1.rs b/gcc/testsuite/rust/compile/torture/match1.rs
new file mode 100644
index 0000000..916b11a
--- /dev/null
+++ b/gcc/testsuite/rust/compile/torture/match1.rs
@@ -0,0 +1,16 @@
+// { dg-additional-options "-w" }
+enum Foo {
+    A,
+    B,
+    C(char),
+    D { x: i64, y: i64 },
+}
+
+fn inspect(f: Foo) {
+    match f {
+        Foo::A => {}
+        Foo::B => {}
+        Foo::C(x) => {}
+        Foo::D { x, y } => {}
+    }
+}