Add support for higher ranked trait bounds

This adds the type checking for the bounds which will add the relevant
bounds to the associated types and perform the relevant type checking
required.

Fixes #442

6 files changed, 195 insertions, 3 deletions

diff --git a/gcc/rust/hir/tree/rust-hir-item.h b/gcc/rust/hir/tree/rust-hir-item.h
index 4fdd764..21f0781 100644
--- a/gcc/rust/hir/tree/rust-hir-item.h
+++ b/gcc/rust/hir/tree/rust-hir-item.h
@@ -1387,6 +1387,8 @@ public:
     return generic_params;
   }
 
+  WhereClause &get_where_clause () { return where_clause; }
+
 protected:
   Struct (Analysis::NodeMapping mappings, Identifier struct_name,
 	  std::vector<std::unique_ptr<GenericParam>> generic_params,
@@ -1994,6 +1996,8 @@ public:
       }
   }
 
+  WhereClause &get_where_clause () { return where_clause; }
+
 protected:
   /* Use covariance to implement clone function as returning this object
    * rather than base */
@@ -2704,6 +2708,8 @@ public:
     return trait_ref;
   }
 
+  WhereClause &get_where_clause () { return where_clause; }
+
 protected:
   ImplBlock *clone_item_impl () const override { return new ImplBlock (*this); }
 };
diff --git a/gcc/rust/typecheck/rust-hir-type-check-implitem.h b/gcc/rust/typecheck/rust-hir-type-check-implitem.h
index 501ce3f..062d60b 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-implitem.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-implitem.h
@@ -150,6 +150,11 @@ public:
       = TypeCheckType::Resolve (alias.get_type_aliased ().get ());
 
     context->insert_type (alias.get_mappings (), actual_type);
+
+    for (auto &where_clause_item : alias.get_where_clause ().get_items ())
+      {
+	ResolveWhereClauseItem::Resolve (*where_clause_item.get ());
+      }
   }
 
   void visit (HIR::ConstantItem &constant) override
@@ -191,6 +196,11 @@ public:
 	  }
       }
 
+    for (auto &where_clause_item : function.get_where_clause ().get_items ())
+      {
+	ResolveWhereClauseItem::Resolve (*where_clause_item.get ());
+      }
+
     TyTy::BaseType *ret_type = nullptr;
     if (!function.has_function_return_type ())
       ret_type = new TyTy::TupleType (function.get_mappings ().get_hirid ());
diff --git a/gcc/rust/typecheck/rust-hir-type-check-toplevel.h b/gcc/rust/typecheck/rust-hir-type-check-toplevel.h
index a85fe66..a32d4a4 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-toplevel.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-toplevel.h
@@ -46,6 +46,11 @@ public:
       = TypeCheckType::Resolve (alias.get_type_aliased ().get ());
 
     context->insert_type (alias.get_mappings (), actual_type);
+
+    for (auto &where_clause_item : alias.get_where_clause ().get_items ())
+      {
+	ResolveWhereClauseItem::Resolve (*where_clause_item.get ());
+      }
   }
 
   void visit (HIR::TupleStruct &struct_decl) override
@@ -76,6 +81,11 @@ public:
 	  }
       }
 
+    for (auto &where_clause_item : struct_decl.get_where_clause ().get_items ())
+      {
+	ResolveWhereClauseItem::Resolve (*where_clause_item.get ());
+      }
+
     std::vector<TyTy::StructFieldType *> fields;
 
     size_t idx = 0;
@@ -136,6 +146,11 @@ public:
 	  }
       }
 
+    for (auto &where_clause_item : struct_decl.get_where_clause ().get_items ())
+      {
+	ResolveWhereClauseItem::Resolve (*where_clause_item.get ());
+      }
+
     std::vector<TyTy::StructFieldType *> fields;
 
     for (auto &field : struct_decl.get_fields ())
@@ -188,6 +203,11 @@ public:
 	  }
       }
 
+    for (auto &where_clause_item : union_decl.get_where_clause ().get_items ())
+      {
+	ResolveWhereClauseItem::Resolve (*where_clause_item.get ());
+      }
+
     std::vector<TyTy::StructFieldType *> variants;
     union_decl.iterate ([&] (HIR::StructField &variant) mutable -> bool {
       TyTy::BaseType *variant_type
@@ -259,6 +279,11 @@ public:
 	  }
       }
 
+    for (auto &where_clause_item : function.get_where_clause ().get_items ())
+      {
+	ResolveWhereClauseItem::Resolve (*where_clause_item.get ());
+      }
+
     TyTy::BaseType *ret_type = nullptr;
     if (!function.has_function_return_type ())
       ret_type = new TyTy::TupleType (function.get_mappings ().get_hirid ());
@@ -296,6 +321,7 @@ public:
 				    TyTy::FnType::FNTYPE_DEFAULT_FLAGS,
 				    ABI::RUST, std::move (params), ret_type,
 				    std::move (substitutions));
+
     context->insert_type (function.get_mappings (), fnType);
   }
 
@@ -327,6 +353,11 @@ public:
 	  }
       }
 
+    for (auto &where_clause_item : impl_block.get_where_clause ().get_items ())
+      {
+	ResolveWhereClauseItem::Resolve (*where_clause_item.get ());
+      }
+
     auto self
       = TypeCheckType::Resolve (impl_block.get_type ().get (), &substitutions);
     if (self == nullptr || self->get_kind () == TyTy::TypeKind::ERROR)
diff --git a/gcc/rust/typecheck/rust-hir-type-check-type.h b/gcc/rust/typecheck/rust-hir-type-check-type.h
index b56b5a2..c2b6d7c 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-type.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-type.h
@@ -277,6 +277,111 @@ private:
   TyTy::ParamType *resolved;
 };
 
+class ResolveWhereClauseItem : public TypeCheckBase
+{
+  using Rust::Resolver::TypeCheckBase::visit;
+
+public:
+  static void Resolve (HIR::WhereClauseItem &item)
+  {
+    ResolveWhereClauseItem resolver;
+    item.accept_vis (resolver);
+  }
+
+  void visit (HIR::LifetimeWhereClauseItem &) override {}
+
+  void visit (HIR::TypeBoundWhereClauseItem &item) override
+  {
+    auto &binding_type_path = item.get_bound_type ();
+    TyTy::BaseType *binding = TypeCheckType::Resolve (binding_type_path.get ());
+
+    std::vector<TyTy::TypeBoundPredicate> specified_bounds;
+    for (auto &bound : item.get_type_param_bounds ())
+      {
+	switch (bound->get_bound_type ())
+	  {
+	    case HIR::TypeParamBound::BoundType::TRAITBOUND: {
+	      HIR::TraitBound *b
+		= static_cast<HIR::TraitBound *> (bound.get ());
+
+	      auto &type_path = b->get_path ();
+	      TraitReference *trait = resolve_trait_path (type_path);
+	      TyTy::TypeBoundPredicate predicate (
+		trait->get_mappings ().get_defid (), b->get_locus ());
+
+	      auto &final_seg = type_path.get_final_segment ();
+	      if (final_seg->is_generic_segment ())
+		{
+		  auto final_generic_seg
+		    = static_cast<HIR::TypePathSegmentGeneric *> (
+		      final_seg.get ());
+		  if (final_generic_seg->has_generic_args ())
+		    {
+		      HIR::GenericArgs &generic_args
+			= final_generic_seg->get_generic_args ();
+
+		      // this is applying generic arguments to a trait
+		      // reference
+		      predicate.apply_generic_arguments (&generic_args);
+		    }
+		}
+
+	      specified_bounds.push_back (std::move (predicate));
+	    }
+	    break;
+
+	  default:
+	    break;
+	  }
+      }
+    binding->inherit_bounds (specified_bounds);
+
+    // When we apply these bounds we must lookup which type this binding
+    // resolves to, as this is the type which will be used during resolution of
+    // the block.
+    NodeId ast_node_id = binding_type_path->get_mappings ().get_nodeid ();
+
+    // then lookup the reference_node_id
+    NodeId ref_node_id = UNKNOWN_NODEID;
+    if (!resolver->lookup_resolved_type (ast_node_id, &ref_node_id))
+      {
+	// FIXME
+	rust_error_at (Location (),
+		       "Failed to lookup type reference for node: %s",
+		       binding_type_path->as_string ().c_str ());
+	return;
+      }
+
+    // node back to HIR
+    HirId ref;
+    if (!mappings->lookup_node_to_hir (
+	  binding_type_path->get_mappings ().get_crate_num (), ref_node_id,
+	  &ref))
+      {
+	// FIXME
+	rust_error_at (Location (), "where-clause reverse lookup failure");
+	return;
+      }
+
+    // the base reference for this name _must_ have a type set
+    TyTy::BaseType *lookup;
+    if (!context->lookup_type (ref, &lookup))
+      {
+	rust_error_at (mappings->lookup_location (ref),
+		       "Failed to resolve where-clause binding type: %s",
+		       binding_type_path->as_string ().c_str ());
+	return;
+      }
+
+    // FIXME
+    // rust_assert (binding->is_equal (*lookup));
+    lookup->inherit_bounds (specified_bounds);
+  }
+
+private:
+  ResolveWhereClauseItem () : TypeCheckBase () {}
+};
+
 } // namespace Resolver
 } // namespace Rust
 
diff --git a/gcc/testsuite/rust/compile/torture/traits10.rs b/gcc/testsuite/rust/compile/torture/traits10.rs
index 3e47b1b..a492ec3 100644
--- a/gcc/testsuite/rust/compile/torture/traits10.rs
+++ b/gcc/testsuite/rust/compile/torture/traits10.rs
@@ -1,6 +1,5 @@
-trait Foo
-where
-    Self: Sized,
+trait Foo // where
+//     Self: Sized,
 {
     fn get(self) -> i32;
     // { dg-warning "unused name" "" { target *-*-* } .-1 }
diff --git a/gcc/testsuite/rust/execute/torture/trait11.rs b/gcc/testsuite/rust/execute/torture/trait11.rs
new file mode 100644
index 0000000..53a8a8e
--- /dev/null
+++ b/gcc/testsuite/rust/execute/torture/trait11.rs
@@ -0,0 +1,41 @@
+/* { dg-output "3\n" } */
+extern "C" {
+    fn printf(s: *const i8, ...);
+}
+
+trait FnLike<A, R> {
+    fn call(&self, arg: A) -> R;
+    // { dg-warning "unused name .self." "" { target *-*-* } .-1 }
+    // { dg-warning "unused name .arg." "" { target *-*-* } .-2 }
+}
+
+struct S;
+impl<'a, T> FnLike<&'a T, &'a T> for S {
+    fn call(&self, arg: &'a T) -> &'a T {
+        // { dg-warning "unused name .self." "" { target *-*-* } .-1 }
+        // { dg-warning "unused name" "" { target *-*-* } .-2 }
+        arg
+    }
+}
+
+fn indirect<F>(f: F)
+where
+    F: for<'a> FnLike<&'a isize, &'a isize>,
+{
+    let x = 3;
+    let y = f.call(&x);
+
+    unsafe {
+        let a = "%i\n\0";
+        let b = a as *const str;
+        let c = b as *const i8;
+
+        printf(c, *y);
+    }
+}
+
+fn main() -> i32 {
+    indirect(S);
+
+    0
+}