Merge #1030

1030: Rewrite our unconstrained type-param error checking r=philberty a=philberty

This is a series of patches that were all required to fix this issue. We
now take advantage of our substitutions abstractions and traits
so that our TypeBoundPredicate's which form the basis of our HRTB code
I think this class is almost akin to rustc existential-trait-references. This now
reuses the same code path to give us the same error checking for generics
as we get with ADT's, functions etc.

With this refactoring in place we can then reuse the abstractions to map the
ID's from the used arguments in the type-bound-predicate, the impl block type
substation mappings and the self type itself.

There are quite a few cases to handle and our testsuite picked up all the regressions
so no behaviour of our existing test-cases have changed now. See each commit for
more detailed information.

Fixes #1019 
Addresses #849

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

15 files changed, 483 insertions, 240 deletions

diff --git a/gcc/rust/Make-lang.in b/gcc/rust/Make-lang.in
index 76a45e7..cd40efb 100644
--- a/gcc/rust/Make-lang.in
+++ b/gcc/rust/Make-lang.in
@@ -99,6 +99,7 @@ GRS_OBJS = \
     rust/rust-hir-type-check-pattern.o \
     rust/rust-hir-type-check-expr.o \
     rust/rust-hir-dot-operator.o \
+    rust/rust-hir-type-check-base.o \
     rust/rust-autoderef.o \
     rust/rust-substitution-mapper.o \
     rust/rust-lint-marklive.o \
diff --git a/gcc/rust/hir/tree/rust-hir-path.h b/gcc/rust/hir/tree/rust-hir-path.h
index 9858ba3..99f4f0b 100644
--- a/gcc/rust/hir/tree/rust-hir-path.h
+++ b/gcc/rust/hir/tree/rust-hir-path.h
@@ -133,8 +133,7 @@ public:
 
   GenericArgs (std::vector<Lifetime> lifetime_args,
 	       std::vector<std::unique_ptr<Type> > type_args,
-	       std::vector<GenericArgsBinding> binding_args,
-	       Location locus = Location ())
+	       std::vector<GenericArgsBinding> binding_args, Location locus)
     : lifetime_args (std::move (lifetime_args)),
       type_args (std::move (type_args)),
       binding_args (std::move (binding_args)), locus (locus)
@@ -471,7 +470,7 @@ public:
 		       has_separating_scope_resolution, locus),
       generic_args (GenericArgs (std::move (lifetime_args),
 				 std::move (type_args),
-				 std::move (binding_args)))
+				 std::move (binding_args), locus))
   {}
 
   std::string as_string () const override;
diff --git a/gcc/rust/typecheck/rust-hir-trait-ref.h b/gcc/rust/typecheck/rust-hir-trait-ref.h
index 613ed71..585fb6c 100644
--- a/gcc/rust/typecheck/rust-hir-trait-ref.h
+++ b/gcc/rust/typecheck/rust-hir-trait-ref.h
@@ -181,19 +181,37 @@ class TraitReference
 public:
   TraitReference (const HIR::Trait *hir_trait_ref,
 		  std::vector<TraitItemReference> item_refs,
-		  std::vector<const TraitReference *> super_traits)
+		  std::vector<const TraitReference *> super_traits,
+		  std::vector<TyTy::SubstitutionParamMapping> substs)
     : hir_trait_ref (hir_trait_ref), item_refs (item_refs),
       super_traits (super_traits)
-  {}
+  {
+    trait_substs.clear ();
+    trait_substs.reserve (substs.size ());
+    for (const auto &p : substs)
+      trait_substs.push_back (p.clone ());
+  }
 
   TraitReference (TraitReference const &other)
-    : hir_trait_ref (other.hir_trait_ref), item_refs (other.item_refs)
-  {}
+    : hir_trait_ref (other.hir_trait_ref), item_refs (other.item_refs),
+      super_traits (other.super_traits)
+  {
+    trait_substs.clear ();
+    trait_substs.reserve (other.trait_substs.size ());
+    for (const auto &p : other.trait_substs)
+      trait_substs.push_back (p.clone ());
+  }
 
   TraitReference &operator= (TraitReference const &other)
   {
     hir_trait_ref = other.hir_trait_ref;
     item_refs = other.item_refs;
+    super_traits = other.super_traits;
+
+    trait_substs.clear ();
+    trait_substs.reserve (other.trait_substs.size ());
+    for (const auto &p : other.trait_substs)
+      trait_substs.push_back (p.clone ());
 
     return *this;
   }
@@ -201,7 +219,10 @@ public:
   TraitReference (TraitReference &&other) = default;
   TraitReference &operator= (TraitReference &&other) = default;
 
-  static TraitReference error () { return TraitReference (nullptr, {}, {}); }
+  static TraitReference error ()
+  {
+    return TraitReference (nullptr, {}, {}, {});
+  }
 
   bool is_error () const { return hir_trait_ref == nullptr; }
 
@@ -384,10 +405,18 @@ public:
     return is_safe;
   }
 
+  bool trait_has_generics () const { return !trait_substs.empty (); }
+
+  std::vector<TyTy::SubstitutionParamMapping> get_trait_substs () const
+  {
+    return trait_substs;
+  }
+
 private:
   const HIR::Trait *hir_trait_ref;
   std::vector<TraitItemReference> item_refs;
   std::vector<const TraitReference *> super_traits;
+  std::vector<TyTy::SubstitutionParamMapping> trait_substs;
 };
 
 class AssociatedImplTrait
diff --git a/gcc/rust/typecheck/rust-hir-trait-resolve.h b/gcc/rust/typecheck/rust-hir-trait-resolve.h
index d8df481..806a46f 100644
--- a/gcc/rust/typecheck/rust-hir-trait-resolve.h
+++ b/gcc/rust/typecheck/rust-hir-trait-resolve.h
@@ -150,8 +150,13 @@ private:
 
     // They also inherit themselves as a bound this enables a trait item to
     // reference other Self::trait_items
+    std::vector<TyTy::SubstitutionParamMapping> self_subst_copy;
+    for (auto &sub : substitutions)
+      self_subst_copy.push_back (sub.clone ());
+
     specified_bounds.push_back (
       TyTy::TypeBoundPredicate (trait_reference->get_mappings ().get_defid (),
+				std::move (self_subst_copy),
 				trait_reference->get_locus ()));
 
     std::vector<const TraitReference *> super_traits;
@@ -168,8 +173,8 @@ private:
 		// FIXME this might be recursive we need a check for that
 
 		TraitReference *trait = resolve_trait_path (b->get_path ());
-		TyTy::TypeBoundPredicate predicate (
-		  trait->get_mappings ().get_defid (), bound->get_locus ());
+		TyTy::TypeBoundPredicate predicate (*trait,
+						    bound->get_locus ());
 
 		specified_bounds.push_back (std::move (predicate));
 		super_traits.push_back (predicate.get ());
@@ -193,7 +198,8 @@ private:
       }
 
     TraitReference trait_object (trait_reference, item_refs,
-				 std::move (super_traits));
+				 std::move (super_traits),
+				 std::move (substitutions));
     context->insert_trait_reference (
       trait_reference->get_mappings ().get_defid (), std::move (trait_object));
 
diff --git a/gcc/rust/typecheck/rust-hir-type-check-base.cc b/gcc/rust/typecheck/rust-hir-type-check-base.cc
new file mode 100644
index 0000000..32c5881
--- /dev/null
+++ b/gcc/rust/typecheck/rust-hir-type-check-base.cc
@@ -0,0 +1,84 @@
+// Copyright (C) 2020-2022 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-base.h"
+
+namespace Rust {
+namespace Resolver {
+
+bool
+TypeCheckBase::check_for_unconstrained (
+  const std::vector<TyTy::SubstitutionParamMapping> &params_to_constrain,
+  const TyTy::SubstitutionArgumentMappings &constraint_a,
+  const TyTy::SubstitutionArgumentMappings &constraint_b,
+  const TyTy::BaseType *reference)
+{
+  std::set<HirId> symbols_to_constrain;
+  std::map<HirId, Location> symbol_to_location;
+  for (const auto &p : params_to_constrain)
+    {
+      HirId ref = p.get_param_ty ()->get_ref ();
+      symbols_to_constrain.insert (ref);
+      symbol_to_location.insert ({ref, p.get_param_locus ()});
+    }
+
+  // set up the set of constrained symbols
+  std::set<HirId> constrained_symbols;
+  for (const auto &c : constraint_a.get_mappings ())
+    {
+      const TyTy::BaseType *arg = c.get_tyty ();
+      if (arg != nullptr)
+	{
+	  const TyTy::BaseType *p = arg->get_root ();
+	  constrained_symbols.insert (p->get_ty_ref ());
+	}
+    }
+  for (const auto &c : constraint_b.get_mappings ())
+    {
+      const TyTy::BaseType *arg = c.get_tyty ();
+      if (arg != nullptr)
+	{
+	  const TyTy::BaseType *p = arg->get_root ();
+	  constrained_symbols.insert (p->get_ty_ref ());
+	}
+    }
+
+  const auto root = reference->get_root ();
+  if (root->get_kind () == TyTy::TypeKind::PARAM)
+    {
+      const TyTy::ParamType *p = static_cast<const TyTy::ParamType *> (root);
+      constrained_symbols.insert (p->get_ty_ref ());
+    }
+
+  // check for unconstrained
+  bool unconstrained = false;
+  for (auto &sym : symbols_to_constrain)
+    {
+      bool used = constrained_symbols.find (sym) != constrained_symbols.end ();
+      if (!used)
+	{
+	  Location locus = symbol_to_location.at (sym);
+	  rust_error_at (locus, "unconstrained type parameter");
+	  unconstrained = true;
+	}
+    }
+  return unconstrained;
+}
+
+} // namespace Resolver
+} // namespace Rust
diff --git a/gcc/rust/typecheck/rust-hir-type-check-base.h b/gcc/rust/typecheck/rust-hir-type-check-base.h
index 830b95ca..5a3f553 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-base.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-base.h
@@ -47,6 +47,14 @@ protected:
 
   TraitReference *resolve_trait_path (HIR::TypePath &);
 
+  TyTy::TypeBoundPredicate get_predicate_from_bound (HIR::TypePath &path);
+
+  bool check_for_unconstrained (
+    const std::vector<TyTy::SubstitutionParamMapping> &params_to_constrain,
+    const TyTy::SubstitutionArgumentMappings &constraint_a,
+    const TyTy::SubstitutionArgumentMappings &constraint_b,
+    const TyTy::BaseType *reference);
+
   Analysis::Mappings *mappings;
   Resolver *resolver;
   TypeCheckContext *context;
diff --git a/gcc/rust/typecheck/rust-hir-type-check-item.h b/gcc/rust/typecheck/rust-hir-type-check-item.h
index f86e967..4c6c4a6 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-item.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-item.h
@@ -70,7 +70,7 @@ public:
 	  }
       }
 
-    std::vector<TyTy::TypeBoundPredicate> specified_bounds;
+    auto specified_bound = TyTy::TypeBoundPredicate::error ();
     TraitReference *trait_reference = &TraitReference::error_node ();
     if (impl_block.has_trait_ref ())
       {
@@ -78,26 +78,7 @@ public:
 	trait_reference = TraitResolver::Resolve (*ref.get ());
 	rust_assert (!trait_reference->is_error ());
 
-	// setup the bound
-	TyTy::TypeBoundPredicate predicate (
-	  trait_reference->get_mappings ().get_defid (), ref->get_locus ());
-	auto &final_seg = ref->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));
+	specified_bound = get_predicate_from_bound (*ref.get ());
       }
 
     TyTy::BaseType *self = nullptr;
@@ -108,11 +89,25 @@ public:
 		       "failed to resolve Self for ImplBlock");
 	return;
       }
-    // inherit the bounds
-    self->inherit_bounds (specified_bounds);
 
+    // inherit the bounds
+    if (!specified_bound.is_error ())
+      self->inherit_bounds ({specified_bound});
+
+    // check for any unconstrained type-params
+    const TyTy::SubstitutionArgumentMappings trait_constraints
+      = specified_bound.get_substitution_arguments ();
+    const TyTy::SubstitutionArgumentMappings impl_constraints
+      = GetUsedSubstArgs::From (self);
+
+    bool impl_block_has_unconstrained_typarams
+      = check_for_unconstrained (substitutions, trait_constraints,
+				 impl_constraints, self);
+    if (impl_block_has_unconstrained_typarams)
+      return;
+
+    // validate the impl items
     bool is_trait_impl_block = !trait_reference->is_error ();
-
     std::vector<const TraitItemReference *> trait_item_refs;
     for (auto &impl_item : impl_block.get_impl_items ())
       {
diff --git a/gcc/rust/typecheck/rust-hir-type-check-toplevel.h b/gcc/rust/typecheck/rust-hir-type-check-toplevel.h
index 2271dace..5e12466 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-toplevel.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-toplevel.h
@@ -468,9 +468,8 @@ public:
 	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)
+    auto self = TypeCheckType::Resolve (impl_block.get_type ().get ());
+    if (self->get_kind () == TyTy::TypeKind::ERROR)
       return;
 
     for (auto &impl_item : impl_block.get_impl_items ())
diff --git a/gcc/rust/typecheck/rust-hir-type-check-type.cc b/gcc/rust/typecheck/rust-hir-type-check-type.cc
index 6c6546b..914bebb 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-type.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check-type.cc
@@ -84,11 +84,6 @@ TypeCheckType::visit (HIR::TypePath &path)
 	}
 
       translated = SubstMapper::Resolve (path_type, path.get_locus (), &args);
-      if (translated->get_kind () != TyTy::TypeKind::ERROR
-	  && mappings != nullptr)
-	{
-	  check_for_unconstrained (args.get_type_args ());
-	}
     }
   else if (!args.is_empty ())
     {
@@ -548,27 +543,11 @@ TypeCheckType::visit (HIR::TraitObjectType &type)
       HIR::TypeParamBound &b = *bound.get ();
       HIR::TraitBound &trait_bound = static_cast<HIR::TraitBound &> (b);
 
-      auto &type_path = trait_bound.get_path ();
-      TraitReference *trait = resolve_trait_path (type_path);
-      TyTy::TypeBoundPredicate predicate (trait->get_mappings ().get_defid (),
-					  trait_bound.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);
-	    }
-	}
+      TyTy::TypeBoundPredicate predicate
+	= get_predicate_from_bound (trait_bound.get_path ());
 
-      if (predicate.is_object_safe (true, type.get_locus ()))
+      if (!predicate.is_error ()
+	  && predicate.is_object_safe (true, type.get_locus ()))
 	specified_bounds.push_back (std::move (predicate));
     }
 
diff --git a/gcc/rust/typecheck/rust-hir-type-check-type.h b/gcc/rust/typecheck/rust-hir-type-check-type.h
index e037562..127502f 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-type.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-type.h
@@ -57,12 +57,9 @@ class TypeCheckType : public TypeCheckBase
   using Rust::Resolver::TypeCheckBase::visit;
 
 public:
-  static TyTy::BaseType *
-  Resolve (HIR::Type *type,
-	   std::vector<TyTy::SubstitutionParamMapping> *subst_mappings
-	   = nullptr)
+  static TyTy::BaseType *Resolve (HIR::Type *type)
   {
-    TypeCheckType resolver (type->get_mappings ().get_hirid (), subst_mappings);
+    TypeCheckType resolver (type->get_mappings ().get_hirid ());
     type->accept_vis (resolver);
     rust_assert (resolver.translated != nullptr);
     resolver.context->insert_type (type->get_mappings (), resolver.translated);
@@ -159,43 +156,10 @@ public:
   void visit (HIR::TraitObjectType &type) override;
 
 private:
-  TypeCheckType (HirId id,
-		 std::vector<TyTy::SubstitutionParamMapping> *subst_mappings)
-    : TypeCheckBase (), subst_mappings (subst_mappings),
-      translated (new TyTy::ErrorType (id))
+  TypeCheckType (HirId id)
+    : TypeCheckBase (), translated (new TyTy::ErrorType (id))
   {}
 
-  void
-  check_for_unconstrained (std::vector<std::unique_ptr<HIR::Type>> &type_args)
-  {
-    std::map<std::string, Location> param_location_map;
-    std::set<std::string> param_tys;
-
-    if (subst_mappings != nullptr)
-      {
-	for (auto &mapping : *subst_mappings)
-	  {
-	    std::string sym = mapping.get_param_ty ()->get_symbol ();
-	    param_tys.insert (sym);
-	    param_location_map[sym] = mapping.get_generic_param ().get_locus ();
-	  }
-      }
-
-    std::set<std::string> args;
-    for (auto &arg : type_args)
-      args.insert (arg->as_string ());
-
-    for (auto &exp : param_tys)
-      {
-	bool used = args.find (exp) != args.end ();
-	if (!used)
-	  {
-	    Location locus = param_location_map.at (exp);
-	    rust_error_at (locus, "unconstrained type parameter");
-	  }
-      }
-  }
-
   TyTy::BaseType *resolve_root_path (HIR::TypePath &path, size_t *offset,
 				     NodeId *root_resolved_node_id);
 
@@ -205,7 +169,6 @@ private:
     TyTy::BaseType *tyseg, const Analysis::NodeMapping &expr_mappings,
     Location expr_locus);
 
-  std::vector<TyTy::SubstitutionParamMapping> *subst_mappings;
   TyTy::BaseType *translated;
 };
 
@@ -245,29 +208,10 @@ public:
 		  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));
+		  TyTy::TypeBoundPredicate predicate
+		    = get_predicate_from_bound (b->get_path ());
+		  if (!predicate.is_error ())
+		    specified_bounds.push_back (std::move (predicate));
 		}
 		break;
 
@@ -316,29 +260,10 @@ public:
 	      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));
+	      TyTy::TypeBoundPredicate predicate
+		= get_predicate_from_bound (b->get_path ());
+	      if (!predicate.is_error ())
+		specified_bounds.push_back (std::move (predicate));
 	    }
 	    break;
 
diff --git a/gcc/rust/typecheck/rust-tyty-bounds.cc b/gcc/rust/typecheck/rust-tyty-bounds.cc
index 1d1c481..a7ec42c 100644
--- a/gcc/rust/typecheck/rust-tyty-bounds.cc
+++ b/gcc/rust/typecheck/rust-tyty-bounds.cc
@@ -63,17 +63,101 @@ TypeCheckBase::resolve_trait_path (HIR::TypePath &path)
   return TraitResolver::Resolve (path);
 }
 
+TyTy::TypeBoundPredicate
+TypeCheckBase::get_predicate_from_bound (HIR::TypePath &type_path)
+{
+  TraitReference *trait = resolve_trait_path (type_path);
+  if (trait->is_error ())
+    return TyTy::TypeBoundPredicate::error ();
+
+  TyTy::TypeBoundPredicate predicate (*trait, type_path.get_locus ());
+  HIR::GenericArgs args
+    = HIR::GenericArgs::create_empty (type_path.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 ())
+	{
+	  args = final_generic_seg->get_generic_args ();
+	}
+    }
+
+  if (predicate.requires_generic_args ())
+    {
+      // this is applying generic arguments to a trait reference
+      predicate.apply_generic_arguments (&args);
+    }
+
+  return predicate;
+}
+
 } // namespace Resolver
 
 namespace TyTy {
 
+TypeBoundPredicate::TypeBoundPredicate (
+  const Resolver::TraitReference &trait_reference, Location locus)
+  : SubstitutionRef (trait_reference.get_trait_substs (),
+		     SubstitutionArgumentMappings::error ()),
+    reference (trait_reference.get_mappings ().get_defid ()), locus (locus),
+    args (HIR::GenericArgs::create_empty ()), error_flag (false)
+{}
+
+TypeBoundPredicate::TypeBoundPredicate (
+  DefId reference, std::vector<SubstitutionParamMapping> substitutions,
+  Location locus)
+  : SubstitutionRef (std::move (substitutions),
+		     SubstitutionArgumentMappings::error ()),
+    reference (reference), locus (locus),
+    args (HIR::GenericArgs::create_empty ()), error_flag (false)
+{}
+
+TypeBoundPredicate::TypeBoundPredicate (const TypeBoundPredicate &other)
+  : SubstitutionRef ({}, other.used_arguments), reference (other.reference),
+    locus (other.locus), args (other.args), error_flag (other.error_flag)
+{
+  substitutions.clear ();
+  if (!other.is_error ())
+    {
+      for (const auto &p : other.get_substs ())
+	substitutions.push_back (p.clone ());
+    }
+}
+
+TypeBoundPredicate &
+TypeBoundPredicate::operator= (const TypeBoundPredicate &other)
+{
+  reference = other.reference;
+  locus = other.locus;
+  args = other.args;
+  error_flag = other.error_flag;
+  used_arguments = other.used_arguments;
+
+  substitutions.clear ();
+  if (!other.is_error ())
+    {
+      for (const auto &p : other.get_substs ())
+	substitutions.push_back (p.clone ());
+    }
+
+  return *this;
+}
+
+TypeBoundPredicate
+TypeBoundPredicate::error ()
+{
+  auto p = TypeBoundPredicate (UNKNOWN_DEFID, {}, Location ());
+  p.error_flag = true;
+  return p;
+}
+
 std::string
 TypeBoundPredicate::as_string () const
 {
-  return get ()->as_string ()
-	 + (has_generic_args ()
-	      ? std::string ("<") + args->as_string () + std::string (">")
-	      : "");
+  return get ()->as_string () + subst_as_string ();
 }
 
 const Resolver::TraitReference *
@@ -114,8 +198,19 @@ TypeBoundPredicate::is_object_safe (bool emit_error, Location locus) const
 void
 TypeBoundPredicate::apply_generic_arguments (HIR::GenericArgs *generic_args)
 {
-  args = generic_args;
-  // TODO verify these arguments are valid and not too many were added
+  // we need to get the substitutions argument mappings but also remember that
+  // we have an implicit Self argument which we must be careful to respect
+  rust_assert (used_arguments.is_empty ());
+  rust_assert (!substitutions.empty ());
+
+  // we setup a dummy implict self argument
+  SubstitutionArg placeholder_self (&substitutions.front (), nullptr);
+  used_arguments.get_mappings ().push_back (std::move (placeholder_self));
+
+  // now actually perform a substitution
+  used_arguments = get_mappings_from_generic_args (*generic_args);
+  error_flag |= used_arguments.is_error ();
+  args = *generic_args;
 }
 
 bool
@@ -179,6 +274,34 @@ TypeBoundPredicateItem::get_tyty_for_receiver (
 
   return resolved;
 }
+bool
+TypeBoundPredicate::is_error () const
+{
+  auto context = Resolver::TypeCheckContext::get ();
+
+  Resolver::TraitReference *ref = nullptr;
+  bool ok = context->lookup_trait_reference (reference, &ref);
+
+  return !ok || error_flag;
+}
+
+BaseType *
+TypeBoundPredicate::handle_substitions (SubstitutionArgumentMappings mappings)
+{
+  gcc_unreachable ();
+  return nullptr;
+}
+
+bool
+TypeBoundPredicate::requires_generic_args () const
+{
+  if (is_error ())
+    return false;
+
+  return substitutions.size () > 1 && args.is_empty ();
+}
+
+// trait item reference
 
 const Resolver::TraitItemReference *
 TypeBoundPredicateItem::get_raw_item () const
@@ -192,5 +315,55 @@ TypeBoundPredicateItem::needs_implementation () const
   return !get_raw_item ()->is_optional ();
 }
 
+// TypeBoundsMappings
+
+TypeBoundsMappings::TypeBoundsMappings (
+  std::vector<TypeBoundPredicate> specified_bounds)
+  : specified_bounds (specified_bounds)
+{}
+
+std::vector<TypeBoundPredicate> &
+TypeBoundsMappings::get_specified_bounds ()
+{
+  return specified_bounds;
+}
+
+const std::vector<TypeBoundPredicate> &
+TypeBoundsMappings::get_specified_bounds () const
+{
+  return specified_bounds;
+}
+
+size_t
+TypeBoundsMappings::num_specified_bounds () const
+{
+  return specified_bounds.size ();
+}
+
+std::string
+TypeBoundsMappings::raw_bounds_as_string () const
+{
+  std::string buf;
+  for (size_t i = 0; i < specified_bounds.size (); i++)
+    {
+      const TypeBoundPredicate &b = specified_bounds.at (i);
+      bool has_next = (i + 1) < specified_bounds.size ();
+      buf += b.get_name () + (has_next ? " + " : "");
+    }
+  return buf;
+}
+
+std::string
+TypeBoundsMappings::bounds_as_string () const
+{
+  return "bounds:[" + raw_bounds_as_string () + "]";
+}
+
+void
+TypeBoundsMappings::add_bound (TypeBoundPredicate predicate)
+{
+  specified_bounds.push_back (predicate);
+}
+
 } // namespace TyTy
 } // namespace Rust
diff --git a/gcc/rust/typecheck/rust-tyty.cc b/gcc/rust/typecheck/rust-tyty.cc
index 8d5cc5e..c12095f 100644
--- a/gcc/rust/typecheck/rust-tyty.cc
+++ b/gcc/rust/typecheck/rust-tyty.cc
@@ -201,11 +201,16 @@ BaseType::inherit_bounds (
 const BaseType *
 BaseType::get_root () const
 {
-  const BaseType *root = this;
-  while (root->get_kind () == TyTy::REF)
+  const TyTy::BaseType *root = this;
+  if (get_kind () == TyTy::REF)
     {
       const ReferenceType *r = static_cast<const ReferenceType *> (root);
-      root = r->get_base ();
+      root = r->get_base ()->get_root ();
+    }
+  else if (get_kind () == TyTy::POINTER)
+    {
+      const PointerType *r = static_cast<const PointerType *> (root);
+      root = r->get_base ()->get_root ();
     }
   return root;
 }
@@ -543,11 +548,11 @@ SubstitutionRef::get_mappings_from_generic_args (HIR::GenericArgs &args)
       rust_error_at (
 	r,
 	"generic item takes at least %lu type arguments but %lu were supplied",
-	substitutions.size (), args.get_type_args ().size ());
+	(min_required_substitutions () - offs), args.get_type_args ().size ());
       return SubstitutionArgumentMappings::error ();
     }
 
-  std::vector<SubstitutionArg> mappings;
+  std::vector<SubstitutionArg> mappings = used_arguments.get_mappings ();
   for (auto &arg : args.get_type_args ())
     {
       BaseType *resolved = Resolver::TypeCheckType::Resolve (arg.get ());
@@ -2351,7 +2356,7 @@ ParamType::handle_substitions (SubstitutionArgumentMappings mappings)
 
   SubstitutionArg arg = SubstitutionArg::error ();
   bool ok = mappings.get_argument_for_symbol (this, &arg);
-  if (ok)
+  if (ok && !arg.is_error ())
     p->set_ty_ref (arg.get_tyty ()->get_ref ());
 
   return p;
diff --git a/gcc/rust/typecheck/rust-tyty.h b/gcc/rust/typecheck/rust-tyty.h
index 82262ab..58b5042 100644
--- a/gcc/rust/typecheck/rust-tyty.h
+++ b/gcc/rust/typecheck/rust-tyty.h
@@ -108,92 +108,24 @@ private:
   const Resolver::TraitItemReference *trait_item_ref;
 };
 
-class TypeBoundPredicate
-{
-public:
-  TypeBoundPredicate (DefId reference, Location locus)
-    : reference (reference), locus (locus), args (nullptr)
-  {}
-
-  std::string as_string () const;
-
-  const Resolver::TraitReference *get () const;
-
-  Location get_locus () const { return locus; }
-
-  std::string get_name () const;
-
-  // check that this predicate is object-safe see:
-  // https://doc.rust-lang.org/reference/items/traits.html#object-safety
-  bool is_object_safe (bool emit_error, Location locus) const;
-
-  void apply_generic_arguments (HIR::GenericArgs *generic_args);
-
-  bool contains_item (const std::string &search) const;
-
-  TypeBoundPredicateItem
-  lookup_associated_item (const std::string &search) const;
-
-  HIR::GenericArgs *get_generic_args () { return args; }
-
-  const HIR::GenericArgs *get_generic_args () const { return args; }
-
-  bool has_generic_args () const
-  {
-    if (args == nullptr)
-      return false;
-
-    return args->has_generic_args ();
-  }
-
-private:
-  DefId reference;
-  Location locus;
-  HIR::GenericArgs *args;
-};
-
 class TypeBoundsMappings
 {
 protected:
-  TypeBoundsMappings (std::vector<TypeBoundPredicate> specified_bounds)
-    : specified_bounds (specified_bounds)
-  {}
+  TypeBoundsMappings (std::vector<TypeBoundPredicate> specified_bounds);
 
 public:
-  std::vector<TypeBoundPredicate> &get_specified_bounds ()
-  {
-    return specified_bounds;
-  }
+  std::vector<TypeBoundPredicate> &get_specified_bounds ();
 
-  const std::vector<TypeBoundPredicate> &get_specified_bounds () const
-  {
-    return specified_bounds;
-  }
+  const std::vector<TypeBoundPredicate> &get_specified_bounds () const;
 
-  size_t num_specified_bounds () const { return specified_bounds.size (); }
+  size_t num_specified_bounds () const;
 
-  std::string raw_bounds_as_string () const
-  {
-    std::string buf;
-    for (size_t i = 0; i < specified_bounds.size (); i++)
-      {
-	const TypeBoundPredicate &b = specified_bounds.at (i);
-	bool has_next = (i + 1) < specified_bounds.size ();
-	buf += b.get_name () + (has_next ? " + " : "");
-      }
-    return buf;
-  }
+  std::string raw_bounds_as_string () const;
 
-  std::string bounds_as_string () const
-  {
-    return "bounds:[" + raw_bounds_as_string () + "]";
-  }
+  std::string bounds_as_string () const;
 
 protected:
-  void add_bound (TypeBoundPredicate predicate)
-  {
-    specified_bounds.push_back (predicate);
-  }
+  void add_bound (TypeBoundPredicate predicate);
 
   std::vector<TypeBoundPredicate> specified_bounds;
 };
@@ -619,7 +551,13 @@ public:
     : generic (other.generic), param (other.param)
   {}
 
-  std::string as_string () const { return param->get_name (); }
+  std::string as_string () const
+  {
+    if (param == nullptr)
+      return "nullptr";
+
+    return param->get_name ();
+  }
 
   bool fill_param_ty (BaseType &type, Location locus);
 
@@ -683,7 +621,9 @@ public:
 
   BaseType *get_tyty () { return argument; }
 
-  const SubstitutionParamMapping *get_param_mapping () { return param; }
+  const BaseType *get_tyty () const { return argument; }
+
+  const SubstitutionParamMapping *get_param_mapping () const { return param; }
 
   static SubstitutionArg error () { return SubstitutionArg (nullptr, nullptr); }
 
@@ -702,7 +642,8 @@ public:
 
   std::string as_string () const
   {
-    return param->as_string () + ":" + argument->as_string ();
+    return param->as_string ()
+	   + (argument != nullptr ? ":" + argument->as_string () : "");
   }
 
 private:
@@ -780,8 +721,12 @@ public:
 
   size_t size () const { return mappings.size (); }
 
+  bool is_empty () const { return size () == 0; }
+
   std::vector<SubstitutionArg> &get_mappings () { return mappings; }
 
+  const std::vector<SubstitutionArg> &get_mappings () const { return mappings; }
+
   std::string as_string () const
   {
     std::string buffer;
@@ -1007,6 +952,62 @@ protected:
   SubstitutionArgumentMappings used_arguments;
 };
 
+class TypeBoundPredicate : public SubstitutionRef
+{
+public:
+  TypeBoundPredicate (const Resolver::TraitReference &trait_reference,
+		      Location locus);
+
+  TypeBoundPredicate (DefId reference,
+		      std::vector<SubstitutionParamMapping> substitutions,
+		      Location locus);
+
+  TypeBoundPredicate (const TypeBoundPredicate &other);
+
+  TypeBoundPredicate &operator= (const TypeBoundPredicate &other);
+
+  static TypeBoundPredicate error ();
+
+  std::string as_string () const;
+
+  const Resolver::TraitReference *get () const;
+
+  Location get_locus () const { return locus; }
+
+  std::string get_name () const;
+
+  // check that this predicate is object-safe see:
+  // https://doc.rust-lang.org/reference/items/traits.html#object-safety
+  bool is_object_safe (bool emit_error, Location locus) const;
+
+  void apply_generic_arguments (HIR::GenericArgs *generic_args);
+
+  bool contains_item (const std::string &search) const;
+
+  TypeBoundPredicateItem
+  lookup_associated_item (const std::string &search) const;
+
+  HIR::GenericArgs *get_generic_args () { return &args; }
+
+  const HIR::GenericArgs *get_generic_args () const { return &args; }
+
+  bool has_generic_args () const { return args.has_generic_args (); }
+
+  // WARNING THIS WILL ALWAYS RETURN NULLPTR
+  BaseType *
+  handle_substitions (SubstitutionArgumentMappings mappings) override final;
+
+  bool is_error () const;
+
+  bool requires_generic_args () const;
+
+private:
+  DefId reference;
+  Location locus;
+  HIR::GenericArgs args;
+  bool error_flag;
+};
+
 // https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.VariantDef.html
 class VariantDef
 {
diff --git a/gcc/testsuite/rust/compile/issue-1019.rs b/gcc/testsuite/rust/compile/issue-1019.rs
new file mode 100644
index 0000000..aea86a8
--- /dev/null
+++ b/gcc/testsuite/rust/compile/issue-1019.rs
@@ -0,0 +1,19 @@
+trait A<T> {
+    type Output;
+
+    fn test(self, a: &T) -> &Self::Output;
+}
+
+struct Foo<T> {
+    // { dg-warning "struct is never constructed" "" { target *-*-* } .-1 }
+    start: T,
+    end: T,
+}
+
+impl<X> A<X> for Foo<usize> {
+    type Output = X;
+
+    fn test(self, a: &X) -> &Self::Output {
+        a
+    }
+}
diff --git a/gcc/testsuite/rust/compile/traits12.rs b/gcc/testsuite/rust/compile/traits12.rs
new file mode 100644
index 0000000..25e0eb7
--- /dev/null
+++ b/gcc/testsuite/rust/compile/traits12.rs
@@ -0,0 +1,20 @@
+trait A<T> {
+    type Output;
+
+    fn test(self, a: &T) -> &Self::Output;
+}
+
+struct Foo<T> {
+    start: T,
+    end: T,
+}
+
+impl<T> A for Foo<usize> {
+    // { dg-error "generic item takes at least 1 type arguments but 0 were supplied" "" { target *-*-* } .-1 }
+    // { dg-error "unconstrained type parameter" "" { target *-*-* } .-2 }
+    type Output = T;
+
+    fn test(self, a: &T) -> &Self::Output {
+        a
+    }
+}