Add type unification as part of typecheck.

Rust must examine each usage of a name and unify their types. For example:

let mut x;
x = 1

This means the declaration is determined to be an inference variable then
the assignment can be resolved to an Integer TyTy which can be combined
as part of the rules to now make the let x decl be an i32.

11 files changed, 216 insertions, 10 deletions

diff --git a/gcc/rust/backend/rust-compile-context.h b/gcc/rust/backend/rust-compile-context.h
index f890678..1924b52 100644
--- a/gcc/rust/backend/rust-compile-context.h
+++ b/gcc/rust/backend/rust-compile-context.h
@@ -205,9 +205,13 @@ public:
 
   virtual ~TyTyResolveCompile () {}
 
-  void visit (TyTy::FnType &type) { gcc_unreachable (); }
+  void visit (TyTy::UnitType &type) override { gcc_unreachable (); }
 
-  void visit (TyTy::BoolType &type)
+  void visit (TyTy::InferType &type) override { gcc_unreachable (); }
+
+  void visit (TyTy::FnType &type) override { gcc_unreachable (); }
+
+  void visit (TyTy::BoolType &type) override
   {
     ::Btype *compiled_type = nullptr;
     bool ok = ctx->lookup_compiled_types (type.get_ref (), &compiled_type);
@@ -215,7 +219,7 @@ public:
     translated = compiled_type;
   }
 
-  void visit (TyTy::IntType &type)
+  void visit (TyTy::IntType &type) override
   {
     printf ("type [%s] has ref: %u\n", type.as_string ().c_str (),
 	    type.get_ref ());
@@ -226,7 +230,7 @@ public:
     translated = compiled_type;
   }
 
-  void visit (TyTy::UintType &type)
+  void visit (TyTy::UintType &type) override
   {
     ::Btype *compiled_type = nullptr;
     bool ok = ctx->lookup_compiled_types (type.get_ref (), &compiled_type);
diff --git a/gcc/rust/hir/tree/rust-hir-stmt.h b/gcc/rust/hir/tree/rust-hir-stmt.h
index c799b5e..9a0e0f2 100644
--- a/gcc/rust/hir/tree/rust-hir-stmt.h
+++ b/gcc/rust/hir/tree/rust-hir-stmt.h
@@ -109,6 +109,8 @@ public:
   LetStmt (LetStmt &&other) = default;
   LetStmt &operator= (LetStmt &&other) = default;
 
+  Location get_locus_slow () const override { return get_locus (); }
+
   Location get_locus () const { return locus; }
 
   void accept_vis (HIRVisitor &vis) override;
diff --git a/gcc/rust/resolve/rust-ast-resolve.cc b/gcc/rust/resolve/rust-ast-resolve.cc
index 57bd0f3..ba4ee21 100644
--- a/gcc/rust/resolve/rust-ast-resolve.cc
+++ b/gcc/rust/resolve/rust-ast-resolve.cc
@@ -168,6 +168,7 @@ Resolver::insert_resolved_name (NodeId refId, NodeId defId)
   rust_assert (it == resolved_names.end ());
 
   resolved_names[refId] = defId;
+  get_name_scope ().peek ()->append_reference_for_def (defId, refId);
 }
 
 bool
@@ -188,6 +189,7 @@ Resolver::insert_resolved_type (NodeId refId, NodeId defId)
   rust_assert (it == resolved_types.end ());
 
   resolved_types[refId] = defId;
+  get_type_scope ().peek ()->append_reference_for_def (defId, refId);
 }
 
 bool
diff --git a/gcc/rust/resolve/rust-name-resolver.h b/gcc/rust/resolve/rust-name-resolver.h
index 2aa592c..38206f6 100644
--- a/gcc/rust/resolve/rust-name-resolver.h
+++ b/gcc/rust/resolve/rust-name-resolver.h
@@ -41,6 +41,7 @@ public:
   {
     mappings[ident] = id;
     decls_within_rib.insert (id);
+    references[id] = {};
   }
 
   bool lookup_name (std::string ident, NodeId *id)
@@ -65,11 +66,30 @@ public:
       }
   }
 
+  void iterate_references_for_def (NodeId def, std::function<bool (NodeId)> cb)
+  {
+    auto it = references.find (def);
+    if (it == references.end ())
+      return;
+
+    for (auto ref : it->second)
+      {
+	if (!cb (ref))
+	  return;
+      }
+  }
+
+  void append_reference_for_def (NodeId def, NodeId ref)
+  {
+    references[def].insert (ref);
+  }
+
 private:
   CrateNum crate_num;
   NodeId node_id;
   std::map<std::string, NodeId> mappings;
   std::set<NodeId> decls_within_rib;
+  std::map<NodeId, std::set<NodeId> > references;
 };
 
 class Scope
@@ -135,8 +155,8 @@ private:
 //
 // if parent is UNKNOWN_NODEID then this is a root declaration
 // say the var_decl hasa node_id=4;
-// the parent could be a BLOCK_Expr node_id but lets make it UNKNOWN_NODE_ID so
-// we know when it terminates
+// the parent could be a BLOCK_Expr node_id but lets make it UNKNOWN_NODE_ID
+// so we know when it terminates
 struct Definition
 {
   NodeId node;
@@ -211,9 +231,6 @@ private:
   // we need two namespaces one for names and ones for types
   std::map<NodeId, NodeId> resolved_names;
   std::map<NodeId, NodeId> resolved_types;
-
-  std::map<NodeId, std::set<NodeId> > nameDefNodeIdToRibs;
-  std::map<NodeId, std::set<NodeId> > typeDefNodeIdToRibs;
 };
 
 } // namespace Resolver
diff --git a/gcc/rust/typecheck/rust-hir-type-check-expr.h b/gcc/rust/typecheck/rust-hir-type-check-expr.h
index 32a5d8b..c9a0fde 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-expr.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-expr.h
@@ -94,6 +94,9 @@ public:
     auto rhs = TypeCheckExpr::Resolve (expr.get_rhs ());
 
     infered = lhs->combine (rhs);
+    // need to overrite the lhs type with this combination
+    context->insert_type (expr.get_lhs ()->get_mappings ().get_hirid (),
+			  infered);
   }
 
   void visit (HIR::IdentifierExpr &expr)
diff --git a/gcc/rust/typecheck/rust-hir-type-check-item.h b/gcc/rust/typecheck/rust-hir-type-check-item.h
index ab964a9..c90af13 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-item.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-item.h
@@ -24,6 +24,7 @@
 #include "rust-hir-type-check-type.h"
 #include "rust-hir-type-check-stmt.h"
 #include "rust-tyty-visitor.h"
+#include "rust-tyty-resolver.h"
 
 namespace Rust {
 namespace Resolver {
@@ -78,6 +79,19 @@ public:
       return true;
     });
 
+    // now that the stmts have been resolved we must resolve the block of locals
+    // and make sure the variables have been resolved
+    auto body_mappings = function.function_body->get_mappings ();
+    Rib *rib = nullptr;
+    if (!resolver->find_name_rib (body_mappings.get_nodeid (), &rib))
+      {
+	rust_fatal_error (function.get_locus (),
+			  "failed to lookup locals per block");
+	return;
+      }
+
+    TyTyResolver::Resolve (rib, mappings, resolver, context);
+
     context->pop_return_type ();
   }
 
diff --git a/gcc/rust/typecheck/rust-tyctx.cc b/gcc/rust/typecheck/rust-tyctx.cc
index 8869e34..6eb46ff 100644
--- a/gcc/rust/typecheck/rust-tyctx.cc
+++ b/gcc/rust/typecheck/rust-tyctx.cc
@@ -60,7 +60,6 @@ TypeCheckContext::insert_builtin (HirId id, NodeId ref, TyTy::TyBase *type)
 void
 TypeCheckContext::insert_type (HirId id, TyTy::TyBase *type)
 {
-  rust_assert (resolved.find (id) == resolved.end ());
   rust_assert (type != nullptr);
   resolved[id] = type;
 }
diff --git a/gcc/rust/typecheck/rust-tyty-resolver.h b/gcc/rust/typecheck/rust-tyty-resolver.h
new file mode 100644
index 0000000..1ee533e
--- /dev/null
+++ b/gcc/rust/typecheck/rust-tyty-resolver.h
@@ -0,0 +1,121 @@
+// Copyright (C) 2020 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_TYTY_RESOLVER
+#define RUST_TYTY_RESOLVER
+
+#include "rust-system.h"
+#include "rust-diagnostics.h"
+#include "rust-hir-map.h"
+#include "rust-name-resolver.h"
+#include "rust-hir-type-check.h"
+#include "rust-hir-full.h"
+
+namespace Rust {
+namespace Resolver {
+
+class TyTyResolver
+{
+public:
+  static void Resolve (Rib *rib, Analysis::Mappings *mappings,
+		       Resolver *resolver, TypeCheckContext *context)
+  {
+    TyTyResolver r (mappings, resolver, context);
+    r.go (rib);
+  }
+
+  virtual ~TyTyResolver () {}
+
+  void go (Rib *rib)
+  {
+    rib->iterate_decls ([&] (NodeId decl_node_id) mutable -> bool {
+      // type inference in rust means we need to gather and examine all
+      // references of this decl and combine each to make sure the type is
+      // correctly inferred. Consider the example:
+      // let mut x; x = 1;
+      // we can only say x is an infer variable then at the assignment
+      // we think x must be an integer
+
+      std::vector<TyTy::TyBase *> gathered_types;
+      rib->iterate_references_for_def (
+	decl_node_id, [&] (NodeId ref_node) mutable -> bool {
+	  HirId hir_node_ref;
+	  bool ok
+	    = mappings->lookup_node_to_hir (mappings->get_current_crate (),
+					    ref_node, &hir_node_ref);
+	  rust_assert (ok);
+
+	  TyTy::TyBase *resolved = nullptr;
+	  if (!context->lookup_type (hir_node_ref, &resolved))
+	    {
+	      rust_fatal_error (mappings->lookup_location (hir_node_ref),
+				"failed to lookup type for reference");
+	      return false;
+	    }
+
+	  gathered_types.push_back (resolved);
+	  return true;
+	});
+
+      Definition d;
+      bool ok = resolver->lookup_definition (decl_node_id, &d);
+      rust_assert (ok);
+
+      HIR::Stmt *decl = nullptr;
+      ok = mappings->resolve_nodeid_to_stmt (d.parent, &decl);
+      rust_assert (ok);
+
+      TyTy::TyBase *resolved_type = nullptr;
+      ok = context->lookup_type (decl->get_mappings ().get_hirid (),
+				 &resolved_type);
+      rust_assert (ok);
+
+      auto resolved_tyty = resolved_type;
+      for (auto it : gathered_types)
+	resolved_tyty = resolved_tyty->combine (it);
+
+      // something is not inferred we need to look at all references now
+      if (resolved_tyty == nullptr || resolved_tyty->is_unit ())
+	{
+	  rust_error_at (decl->get_locus_slow (), "failed to resolve type");
+	  return false;
+	}
+
+      // insert the new resolved definition
+      context->insert_type (decl->get_mappings ().get_hirid (), resolved_tyty);
+      return true;
+    });
+  }
+
+protected:
+private:
+  TyTyResolver (Analysis::Mappings *mappings, Resolver *resolver,
+		TypeCheckContext *context)
+    : mappings (mappings), resolver (resolver), context (context)
+  {}
+
+  Analysis::Mappings *mappings;
+  Resolver *resolver;
+  TypeCheckContext *context;
+};
+
+} // namespace Resolver
+
+} // namespace Rust
+
+#endif // RUST_TYTY_RESOLVER
diff --git a/gcc/rust/typecheck/rust-tyty-rules.h b/gcc/rust/typecheck/rust-tyty-rules.h
index 372229b..205ef44 100644
--- a/gcc/rust/typecheck/rust-tyty-rules.h
+++ b/gcc/rust/typecheck/rust-tyty-rules.h
@@ -105,6 +105,23 @@ public:
     return resolved;
   }
 
+  // we are an inference variable so this means we can take the other as the
+  // type
+  virtual void visit (BoolType &type) override
+  {
+    resolved = new BoolType (type.get_ref ());
+  }
+
+  virtual void visit (IntType &type) override
+  {
+    resolved = new IntType (type.get_ref (), type.get_kind ());
+  }
+
+  virtual void visit (UintType &type) override
+  {
+    resolved = new UintType (type.get_ref (), type.get_kind ());
+  }
+
 private:
   InferType *base;
   TyBase *resolved;
diff --git a/gcc/testsuite/rust.test/compilable/type_infer3.rs b/gcc/testsuite/rust.test/compilable/type_infer3.rs
new file mode 100644
index 0000000..b20b565
--- /dev/null
+++ b/gcc/testsuite/rust.test/compilable/type_infer3.rs
@@ -0,0 +1,13 @@
+fn test(x: i32) -> i32 {
+    return x + 1;
+}
+
+fn main() {
+    let mut an_integer = 5;
+    an_integer = test(1) + 3;
+
+    let mut x;
+    x = 1;
+
+    let call_test = test(1);
+}
diff --git a/gcc/testsuite/rust.test/fail_compilation/bad_type2.rs b/gcc/testsuite/rust.test/fail_compilation/bad_type2.rs
new file mode 100644
index 0000000..f1e17ed
--- /dev/null
+++ b/gcc/testsuite/rust.test/fail_compilation/bad_type2.rs
@@ -0,0 +1,14 @@
+fn test(x: i32) -> i32 {
+    return x + 1;
+}
+
+fn main() {
+    let mut an_integer = 5;
+    an_integer = test(1) + 3;
+
+    let mut x;
+    x = 1;
+    x = true;
+
+    let call_test = test(1);
+}