Add check for TypeBounds on argument substitutions

TypeParameters contain specified bounds, when we substitute them we need
to ensure that the argument satisfies those bounds otherwise... it fails
the contract.

This change only checks this specific case as a nice isolated PR to
demonstrate the mechanism's we require. Specified bounds are checked but
we must also probe for what bounds are available for the type.

Addreses #440

3 files changed, 102 insertions, 4 deletions

diff --git a/gcc/rust/typecheck/rust-tyty.cc b/gcc/rust/typecheck/rust-tyty.cc
index a2ae4fa..3238631 100644
--- a/gcc/rust/typecheck/rust-tyty.cc
+++ b/gcc/rust/typecheck/rust-tyty.cc
@@ -27,6 +27,8 @@
 #include "rust-tyty-cast.h"
 #include "rust-hir-map.h"
 #include "rust-substitution-mapper.h"
+#include "rust-hir-trait-ref.h"
+#include "rust-hir-type-bounds.h"
 
 extern ::Backend *
 rust_get_backend ();
@@ -34,6 +36,32 @@ rust_get_backend ();
 namespace Rust {
 namespace TyTy {
 
+bool
+BaseType::satisfies_bound (const TypeBoundPredicate &predicate) const
+{
+  const Resolver::TraitReference *query = predicate.get ();
+  for (auto &bound : specified_bounds)
+    {
+      const Resolver::TraitReference *item = bound.get ();
+      bool found = item->get_mappings ().get_defid ()
+		   == query->get_mappings ().get_defid ();
+      if (found)
+	return true;
+    }
+
+  std::vector<std::reference_wrapper<Resolver::TraitReference>> probed
+    = Resolver::TypeBoundsProbe::Probe (this);
+  for (const Resolver::TraitReference &bound : probed)
+    {
+      bool found = bound.get_mappings ().get_defid ()
+		   == query->get_mappings ().get_defid ();
+      if (found)
+	return true;
+    }
+
+  return false;
+}
+
 TyVar::TyVar (HirId ref) : ref (ref)
 {
   // ensure this reference is defined within the context
@@ -556,7 +584,7 @@ ADTType::handle_substitions (SubstitutionArgumentMappings subst_mappings)
       bool ok
 	= subst_mappings.get_argument_for_symbol (sub.get_param_ty (), &arg);
       if (ok)
-	sub.fill_param_ty (arg.get_tyty ());
+	sub.fill_param_ty (arg.get_tyty (), subst_mappings.get_locus ());
     }
 
   adt->iterate_fields ([&] (StructFieldType *field) mutable -> bool {
@@ -811,7 +839,7 @@ FnType::is_equal (const BaseType &other) const
 BaseType *
 FnType::clone () const
 {
-  std::vector<std::pair<HIR::Pattern *, BaseType *> > cloned_params;
+  std::vector<std::pair<HIR::Pattern *, BaseType *>> cloned_params;
   for (auto &p : params)
     cloned_params.push_back (
       std::pair<HIR::Pattern *, BaseType *> (p.first, p.second->clone ()));
@@ -836,7 +864,7 @@ FnType::handle_substitions (SubstitutionArgumentMappings subst_mappings)
       bool ok
 	= subst_mappings.get_argument_for_symbol (sub.get_param_ty (), &arg);
       if (ok)
-	sub.fill_param_ty (arg.get_tyty ());
+	sub.fill_param_ty (arg.get_tyty (), subst_mappings.get_locus ());
     }
 
   auto fty = fn->get_return_type ();
diff --git a/gcc/rust/typecheck/rust-tyty.h b/gcc/rust/typecheck/rust-tyty.h
index 13bab90..6fe67c7 100644
--- a/gcc/rust/typecheck/rust-tyty.h
+++ b/gcc/rust/typecheck/rust-tyty.h
@@ -172,7 +172,21 @@ public:
     return specified_bounds;
   }
 
+  std::string bounds_as_string () const
+  {
+    std::string buf;
+    for (auto &b : specified_bounds)
+      buf += b.as_string () + ", ";
+
+    return "bounds:[" + buf + "]";
+  }
+
 protected:
+  void add_bound (TypeBoundPredicate predicate)
+  {
+    specified_bounds.push_back (predicate);
+  }
+
   std::vector<TypeBoundPredicate> specified_bounds;
 };
 
@@ -237,6 +251,37 @@ public:
     return get_kind () == other.get_kind ();
   }
 
+  bool satisfies_bound (const TypeBoundPredicate &predicate) const;
+
+  bool bounds_compatible (const BaseType &other, Location locus) const
+  {
+    std::vector<std::reference_wrapper<const TypeBoundPredicate>>
+      unsatisfied_bounds;
+    for (auto &bound : get_specified_bounds ())
+      {
+	if (!other.satisfies_bound (bound))
+	  unsatisfied_bounds.push_back (bound);
+      }
+
+    if (unsatisfied_bounds.size () > 0)
+      {
+	RichLocation r (locus);
+	rust_error_at (r, "bounds not satisfied for %s",
+		       other.as_string ().c_str ());
+	return false;
+      }
+
+    return unsatisfied_bounds.size () == 0;
+  }
+
+  void inherit_bounds (const BaseType &other)
+  {
+    for (auto &bound : other.get_specified_bounds ())
+      {
+	add_bound (bound);
+      }
+  }
+
   virtual bool is_unit () const { return false; }
 
   virtual bool is_concrete () const { return true; }
@@ -575,8 +620,18 @@ public:
 
   std::string as_string () const { return param->as_string (); }
 
-  void fill_param_ty (BaseType *type)
+  void fill_param_ty (BaseType *type, Location locus)
   {
+    if (type->get_kind () == TyTy::TypeKind::INFER)
+      {
+	type->inherit_bounds (*param);
+      }
+    else
+      {
+	if (!param->bounds_compatible (*type, locus))
+	  return;
+      }
+
     if (type->get_kind () == TypeKind::PARAM)
       {
 	delete param;
diff --git a/gcc/testsuite/rust/compile/traits6.rs b/gcc/testsuite/rust/compile/traits6.rs
new file mode 100644
index 0000000..3579b5a
--- /dev/null
+++ b/gcc/testsuite/rust/compile/traits6.rs
@@ -0,0 +1,15 @@
+trait Foo {
+    fn default() -> i32;
+}
+
+struct Bar(i32);
+
+fn type_bound_test<T: Foo>() -> i32 {
+    T::default()
+}
+
+fn main() {
+    let a;
+    a = type_bound_test::<Bar>();
+    // { dg-error "bounds not satisfied for Bar" "" { target *-*-* } .-1 }
+}