resolve: Add name resolution for AltPattern

The main changes in this commit can be logically split into two parts:

1) Pushing new pattern binding contexts in alt patterns. At the start
of each AltPattern we push an 'Or' context which represents the relation
between the bindings of different alts.

Before we resolve each alt arm we need to push a 'Product' context to represent
the relation between the bindings of this specific alt arm and each other.
This 'Product' context is removed after the alt arm visit and the its bindings
are pushed into the 'Or' context.

Eventually, the 'Or' context is removed as well after it fulfills its duty.
Its bindings are then pushed into the previous context similarly and so on.

2) Checking for consistent bindings between the alt arms which is handled
by check_bindings_consistency. The info necessary for this check is held
by binding_info_map inside PatternDeclaration class. The binding_info_map
only holds bindings for one alt arm at a time. After every alt arm visit,
these bindings info are pushed into a vec (that contains all alt arms info
and will eventually be passed to check_bindings_consistency) and emptied out
for the next alt arm visit. At the end, all the info from all the alt arms
are pushed again into binding_info in addition to the initial bindings that
were there before the alt arms visits, this way the binding_info will contain
all the binding_info present in the AltPattern (as it should).

In addition to that, some refactors were made (e.g. add_new_binding function)
and some errors emitted, no biggie.

gcc/rust/ChangeLog:

	* resolve/rust-ast-resolve-pattern.cc (PatternDeclaration::go):
	Print out consistency errors.
	(PatternDeclaration::visit): Implement visit for AltPattern.
	(PatternDeclaration::add_new_binding): New helper function for
	adding a binding to identifier.
	* resolve/rust-ast-resolve-pattern.h (struct BindingInfo):
	New struct to facilitate checking for inconsistencies between bindings.

gcc/testsuite/ChangeLog:

	* rust/compile/torture/alt_patterns1.rs: New test.

Signed-off-by: Mahmoud Mohamed <mahadelr19@gmail.com>

3 files changed, 272 insertions, 46 deletions

diff --git a/gcc/rust/resolve/rust-ast-resolve-pattern.cc b/gcc/rust/resolve/rust-ast-resolve-pattern.cc
index 866745e..7eab1f0 100644
--- a/gcc/rust/resolve/rust-ast-resolve-pattern.cc
+++ b/gcc/rust/resolve/rust-ast-resolve-pattern.cc
@@ -28,9 +28,8 @@ PatternDeclaration::go (AST::Pattern *pattern, Rib::ItemType type)
 {
   std::vector<PatternBinding> bindings
     = {PatternBinding (PatternBoundCtx::Product, std::set<Identifier> ())};
-  PatternDeclaration resolver (bindings, type);
-  pattern->accept_vis (resolver);
-};
+  PatternDeclaration::go (pattern, type, bindings);
+}
 
 void
 PatternDeclaration::go (AST::Pattern *pattern, Rib::ItemType type,
@@ -38,49 +37,36 @@ PatternDeclaration::go (AST::Pattern *pattern, Rib::ItemType type,
 {
   PatternDeclaration resolver (bindings, type);
   pattern->accept_vis (resolver);
-}
-
-void
-PatternDeclaration::visit (AST::IdentifierPattern &pattern)
-{
-  bool has_binding_ctx = bindings.size () > 0;
-  rust_assert (has_binding_ctx);
 
-  auto &binding_idents = bindings.back ().idents;
+  for (auto &map_entry : resolver.missing_bindings)
+    {
+      auto ident = map_entry.first; // key
+      auto info = map_entry.second; // value
 
-  bool current_ctx_is_product
-    = bindings.back ().ctx == PatternBoundCtx::Product;
-  bool identifier_is_product_bound
-    = current_ctx_is_product
-      && binding_idents.find (pattern.get_ident ()) != binding_idents.end ();
+      rust_error_at (info.get_locus (), ErrorCode ("E0408"),
+		     "variable '%s' is not bound in all patterns",
+		     ident.c_str ());
+    }
 
-  if (identifier_is_product_bound)
+  for (auto &map_entry : resolver.inconsistent_bindings)
     {
-      if (type == Rib::ItemType::Param)
-	{
-	  rust_error_at (pattern.get_locus (), ErrorCode ("E0415"),
-			 "identifier '%s' is bound more than once in the "
-			 "same parameter list",
-			 pattern.get_ident ().c_str ());
-	}
-      else
-	{
-	  rust_error_at (
-	    pattern.get_locus (), ErrorCode ("E0416"),
-	    "identifier '%s' is bound more than once in the same pattern",
-	    pattern.get_ident ().c_str ());
-	}
+      auto ident = map_entry.first; // key
+      auto info = map_entry.second; // value
 
-      return;
+      rust_error_at (
+	info.get_locus (), ErrorCode ("E0409"),
+	"variable '%s' is bound inconsistently across pattern alternatives",
+	ident.c_str ());
     }
+}
 
-  // if we have a duplicate id this then allows for shadowing correctly
-  // as new refs to this decl will match back here so it is ok to overwrite
-  resolver->get_name_scope ().insert (
-    CanonicalPath::new_seg (pattern.get_node_id (), pattern.get_ident ()),
-    pattern.get_node_id (), pattern.get_locus (), type);
-
-  binding_idents.insert (pattern.get_ident ());
+void
+PatternDeclaration::visit (AST::IdentifierPattern &pattern)
+{
+  Mutability mut = pattern.get_is_mut () ? Mutability::Mut : Mutability::Imm;
+  add_new_binding (pattern.get_ident (), pattern.get_node_id (),
+		   BindingTypeInfo (mut, pattern.get_is_ref (),
+				    pattern.get_locus ()));
 }
 
 void
@@ -154,10 +140,12 @@ PatternDeclaration::visit (AST::StructPattern &pattern)
 	    AST::StructPatternFieldIdent &ident
 	      = static_cast<AST::StructPatternFieldIdent &> (*field.get ());
 
-	    resolver->get_name_scope ().insert (
-	      CanonicalPath::new_seg (ident.get_node_id (),
-				      ident.get_identifier ()),
-	      ident.get_node_id (), ident.get_locus ());
+	    Mutability mut
+	      = ident.is_mut () ? Mutability::Mut : Mutability::Imm;
+
+	    add_new_binding (ident.get_identifier (), ident.get_node_id (),
+			     BindingTypeInfo (mut, ident.is_ref (),
+					      ident.get_locus ()));
 	  }
 	  break;
 	}
@@ -197,6 +185,162 @@ PatternDeclaration::visit (AST::TuplePattern &pattern)
     }
 }
 
+void
+PatternDeclaration::visit (AST::AltPattern &pattern)
+{
+  // push a new set of 'Or' bindings to the stack. Accounts for the
+  // alternatives. e.g. in `p_0 | p_1`, bindings to the same identifier between
+  // p_0 and p_1 shouldn't cause an error.
+  bindings_with_ctx.push_back (
+    PatternBinding (PatternBoundCtx::Or, std::set<Identifier> ()));
+
+  // This is a hack to avoid creating a separate visitor class for the
+  // consistency checks. We empty out the binding_info_map before each iteration
+  // to separate between the alts' binding_maps. And right after the alt
+  // visit...
+  auto tmp_binding_map = binding_info_map;
+  binding_info_map.clear ();
+
+  std::vector<BindingMap> alts_binding_maps;
+
+  for (auto &alt : pattern.get_alts ())
+    {
+      // before this visit, the binding_info_map is guaranteed to be empty
+      rust_assert (binding_info_map.empty ());
+
+      // push a new `Product` context to correctly reject multiple bindings
+      // within this single alt.
+      bindings_with_ctx.push_back (
+	PatternBinding (PatternBoundCtx::Product, std::set<Identifier> ()));
+
+      alt->accept_vis (*this);
+
+      // ...the binding_info_map is (potentially) populated. We copy it to the
+      // vector, and empty it out to be ready for the next iteration. And after
+      // all the iterations are finished...
+      alts_binding_maps.push_back (binding_info_map);
+      binding_info_map.clear ();
+
+      // Remove the last (i.e. `Product`) context and add the bindings from the
+      // visited alt to the one before last (i.e. `Or`). Now (after checking
+      // with the alt internally), the bindings from this alt will reside in the
+      // `Or` context.
+      auto last_bound_idents = bindings_with_ctx.back ().idents;
+      bindings_with_ctx.pop_back ();
+
+      for (auto &ident : last_bound_idents)
+	{
+	  bindings_with_ctx.back ().idents.insert (ident);
+	}
+    }
+
+  // Now we can finally check for consistency.
+  check_bindings_consistency (alts_binding_maps);
+
+  // Now we remove the `Or` context we pushed earlier.
+  // e.g. in `(a, (p_0 | p_1), c)`: after finishing up inside the alt pattern,
+  // we return to the tuple (`Product`) context and push the new bindings.
+  auto idents = bindings_with_ctx.back ().idents;
+  bindings_with_ctx.pop_back ();
+  for (auto &ident : idents)
+    bindings_with_ctx.back ().idents.insert (ident);
+
+  // ...we repopulate the binding_info_map correctly (the initial bindings
+  // stored in the tmp_binding_map + all the bindings from all the alts)
+  binding_info_map = tmp_binding_map;
+  for (auto &alt_map : alts_binding_maps)
+    for (auto &map_entry : alt_map)
+      binding_info_map.insert (map_entry);
+}
+
+void
+PatternDeclaration::add_new_binding (Identifier ident, NodeId node_id,
+				     BindingTypeInfo info)
+{
+  bool has_binding_ctx = bindings_with_ctx.size () > 0;
+  rust_assert (has_binding_ctx);
+
+  bool identifier_or_bound = false, identifier_product_bound = false;
+
+  for (auto binding : bindings_with_ctx)
+    {
+      bool identifier_bound_here
+	= (binding.idents.find (ident) != binding.idents.end ());
+      if (identifier_bound_here)
+	{
+	  identifier_product_bound |= binding.ctx == PatternBoundCtx::Product;
+	  identifier_or_bound |= binding.ctx == PatternBoundCtx::Or;
+	}
+    }
+
+  if (identifier_product_bound)
+    {
+      if (type == Rib::ItemType::Param)
+	{
+	  rust_error_at (info.get_locus (), ErrorCode ("E0415"),
+			 "identifier '%s' is bound more than once in the "
+			 "same parameter list",
+			 ident.c_str ());
+	}
+      else
+	{
+	  rust_error_at (
+	    info.get_locus (), ErrorCode ("E0416"),
+	    "identifier '%s' is bound more than once in the same pattern",
+	    ident.c_str ());
+	}
+
+      return;
+    }
+
+  if (!identifier_or_bound)
+    {
+      bindings_with_ctx.back ().idents.insert (ident);
+      resolver->get_name_scope ().insert (CanonicalPath::new_seg (node_id,
+								  ident),
+					  node_id, info.get_locus (), type);
+    }
+
+  binding_info_map.insert ({ident, info});
+}
+
+// Verifies that all the alts in an AltPattern have the same set of bindings
+// with the same mutability and reference states.
+void
+PatternDeclaration::check_bindings_consistency (
+  std::vector<BindingMap> &binding_maps)
+{
+  for (size_t i = 0; i < binding_maps.size (); i++)
+    {
+      auto &outer_bindings_map = binding_maps[i];
+
+      for (size_t j = 0; j < binding_maps.size (); j++)
+	{
+	  // skip comparing the current outer map with itself.
+	  if (j == i)
+	    continue;
+
+	  auto &inner_bindings_map = binding_maps[j];
+
+	  // iterate over the inner map entries and check if they exist in outer
+	  // map
+	  for (auto map_entry : inner_bindings_map)
+	    {
+	      auto ident = map_entry.first;	  // key
+	      auto inner_info = map_entry.second; // value
+	      bool ident_is_outer_bound = outer_bindings_map.count (ident);
+
+	      if (!ident_is_outer_bound && !missing_bindings.count (ident))
+		missing_bindings.insert ({ident, inner_info});
+
+	      else if (outer_bindings_map[ident] != inner_info
+		       && !inconsistent_bindings.count (ident))
+		inconsistent_bindings.insert ({ident, inner_info});
+	    }
+	}
+    }
+}
+
 static void
 resolve_range_pattern_bound (AST::RangePatternBound *bound)
 {
diff --git a/gcc/rust/resolve/rust-ast-resolve-pattern.h b/gcc/rust/resolve/rust-ast-resolve-pattern.h
index 0ff500a..5723c35 100644
--- a/gcc/rust/resolve/rust-ast-resolve-pattern.h
+++ b/gcc/rust/resolve/rust-ast-resolve-pattern.h
@@ -45,6 +45,51 @@ struct PatternBinding
   {}
 };
 
+// Info that gets stored in the map. Helps us detect if two bindings to the same
+// identifier have different mutability or ref states.
+class BindingTypeInfo
+{
+  Mutability mut;
+  bool is_ref;
+  Location locus;
+
+public:
+  BindingTypeInfo (Mutability mut, bool is_ref, Location locus)
+    : mut (mut), is_ref (is_ref), locus (locus)
+  {}
+
+  BindingTypeInfo (BindingTypeInfo const &other)
+    : mut (other.mut), is_ref (other.is_ref), locus (other.get_locus ())
+  {}
+
+  BindingTypeInfo (){};
+
+  Location get_locus () const { return locus; }
+  Mutability get_mut () const { return mut; }
+  bool get_is_ref () const { return is_ref; }
+
+  BindingTypeInfo operator= (BindingTypeInfo const &other)
+  {
+    mut = other.mut;
+    is_ref = other.is_ref;
+    locus = other.get_locus ();
+
+    return *this;
+  }
+
+  bool operator== (BindingTypeInfo const &other)
+  {
+    return mut == other.mut && is_ref == other.is_ref;
+  }
+
+  bool operator!= (BindingTypeInfo const &other)
+  {
+    return !BindingTypeInfo::operator== (other);
+  }
+};
+
+typedef std::map<Identifier, BindingTypeInfo> BindingMap;
+
 class ResolvePattern : public ResolverBase
 {
   using Rust::Resolver::ResolverBase::visit;
@@ -87,13 +132,35 @@ public:
   void visit (AST::TupleStructPattern &pattern) override;
   void visit (AST::TuplePattern &pattern) override;
   void visit (AST::RangePattern &pattern) override;
+  void visit (AST::AltPattern &pattern) override;
+
+  void add_new_binding (Identifier ident, NodeId node_id, BindingTypeInfo info);
+  void check_bindings_consistency (std::vector<BindingMap> &binding_maps);
 
 private:
-  PatternDeclaration (std::vector<PatternBinding> &bindings, Rib::ItemType type)
-    : ResolverBase (), bindings (bindings), type (type)
+  PatternDeclaration (std::vector<PatternBinding> &bindings_with_ctx,
+		      Rib::ItemType type)
+    : ResolverBase (), bindings_with_ctx (bindings_with_ctx), type (type)
   {}
 
-  std::vector<PatternBinding> &bindings;
+  // To avoid having a separate visitor for consistency checks, we store
+  // bindings in two forms:
+
+  // 1) Bindings as a vector of context-related sets.
+  // Used for checking multiple bindings to the same identifier (i.e. E0415,
+  // E0416).
+  std::vector<PatternBinding> &bindings_with_ctx;
+
+  // 2) Bindings as a map between identifiers and binding info.
+  // Used for checking consistency between alt patterns (i.e. E0408, E0409).
+  BindingMap binding_info_map;
+
+  // we need to insert the missing and inconsistent bindings (found in
+  // check_bindings_consistency) into maps to avoid duplication of error
+  // messages.
+  BindingMap inconsistent_bindings;
+  BindingMap missing_bindings;
+
   Rib::ItemType type;
 };
 
diff --git a/gcc/testsuite/rust/compile/torture/alt_patterns1.rs b/gcc/testsuite/rust/compile/torture/alt_patterns1.rs
new file mode 100644
index 0000000..5647015
--- /dev/null
+++ b/gcc/testsuite/rust/compile/torture/alt_patterns1.rs
@@ -0,0 +1,15 @@
+enum E {
+  A(i32),
+  B(i32, i32),
+}
+
+fn foo((E::A(a) | E::B(mut a, _)): E) {}
+// { dg-error "variable .a. is bound inconsistently across pattern alternatives .E0409." "" { target *-*-* } .-1 }
+
+fn bar((E::A(a) | E::B(mut b, a)): E) {}
+// { dg-error "variable .b. is not bound in all patterns .E0408." "" { target *-*-* } .-1 }
+
+fn baz_correct((a, (E::A(c) | (E::A(c) | E::B(_, c)) | E::B(c, _)), b): (i32, E, u8)) {}
+
+fn baz_wrong((a, (E::A(c) | (E::A(c) | E::B(_, c)) | E::B(c, z)), b): (i32, E, u8)) {}
+// { dg-error "variable .z. is not bound in all patterns .E0408." "" { target *-*-* } .-1 }
\ No newline at end of file