Merge #609

609: Initial TypeBounds support r=philberty a=philberty

This allows us to specify bounds on type parameters that influence
path resolution to allow us to resolve to trait items. More error
checking is required to actually enforce the trait constraint but
this patch is getting rather large and does not cause regressions.

Fixes #583 

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

31 files changed, 1200 insertions, 264 deletions

diff --git a/gcc/rust/Make-lang.in b/gcc/rust/Make-lang.in
index 794c7a3..f4bc9ea 100644
--- a/gcc/rust/Make-lang.in
+++ b/gcc/rust/Make-lang.in
@@ -79,6 +79,7 @@ GRS_OBJS = \
     rust/rust-hir-type-check.o \
     rust/rust-tyty.o \
     rust/rust-tyctx.o \
+    rust/rust-tyty-bounds.o \
     rust/rust-hir-const-fold.o \
     rust/rust-lint-marklive.o \
     $(END)
diff --git a/gcc/rust/ast/rust-ast.h b/gcc/rust/ast/rust-ast.h
index 067e2f5b..e376488 100644
--- a/gcc/rust/ast/rust-ast.h
+++ b/gcc/rust/ast/rust-ast.h
@@ -1126,9 +1126,17 @@ public:
 
   virtual void accept_vis (ASTVisitor &vis) = 0;
 
+  NodeId get_node_id () const { return node_id; }
+
+  virtual Location get_locus_slow () const = 0;
+
 protected:
   // Clone function implementation as pure virtual method
   virtual TypeParamBound *clone_type_param_bound_impl () const = 0;
+
+  TypeParamBound (NodeId node_id) : node_id (node_id) {}
+
+  NodeId node_id;
 };
 
 // Represents a lifetime (and is also a kind of type param bound)
@@ -1144,22 +1152,22 @@ public:
 
 private:
   LifetimeType lifetime_type;
-
-  // TODO: LIFETIME_OR_LABEL (aka lifetime token) is only field
-  // find way of enclosing token or something
   std::string lifetime_name;
-  // only applies for NAMED lifetime_type
-
   Location locus;
-
   NodeId node_id;
 
 public:
   // Constructor
   Lifetime (LifetimeType type, std::string name = std::string (),
 	    Location locus = Location ())
-    : lifetime_type (type), lifetime_name (std::move (name)), locus (locus),
-      node_id (Analysis::Mappings::get ()->get_next_node_id ())
+    : TypeParamBound (Analysis::Mappings::get ()->get_next_node_id ()),
+      lifetime_type (type), lifetime_name (std::move (name)), locus (locus)
+  {}
+
+  Lifetime (NodeId id, LifetimeType type, std::string name = std::string (),
+	    Location locus = Location ())
+    : TypeParamBound (id), lifetime_type (type),
+      lifetime_name (std::move (name)), locus (locus)
   {}
 
   // Creates an "error" lifetime.
@@ -1177,18 +1185,18 @@ public:
 
   LifetimeType get_lifetime_type () { return lifetime_type; }
 
-  Location get_locus () { return locus; }
+  Location get_locus () const { return locus; }
 
-  std::string get_lifetime_name () const { return lifetime_name; }
+  Location get_locus_slow () const override final { return get_locus (); }
 
-  NodeId get_node_id () const { return node_id; }
+  std::string get_lifetime_name () const { return lifetime_name; }
 
 protected:
   /* Use covariance to implement clone function as returning this object rather
    * than base */
   Lifetime *clone_type_param_bound_impl () const override
   {
-    return new Lifetime (*this);
+    return new Lifetime (node_id, lifetime_type, lifetime_name, locus);
   }
 };
 
diff --git a/gcc/rust/ast/rust-type.h b/gcc/rust/ast/rust-type.h
index a9c1966..b658a53 100644
--- a/gcc/rust/ast/rust-type.h
+++ b/gcc/rust/ast/rust-type.h
@@ -50,7 +50,18 @@ public:
 	      bool opening_question_mark = false,
 	      std::vector<LifetimeParam> for_lifetimes
 	      = std::vector<LifetimeParam> ())
-    : in_parens (in_parens), opening_question_mark (opening_question_mark),
+    : TypeParamBound (Analysis::Mappings::get ()->get_next_node_id ()),
+      in_parens (in_parens), opening_question_mark (opening_question_mark),
+      for_lifetimes (std::move (for_lifetimes)),
+      type_path (std::move (type_path)), locus (locus)
+  {}
+
+  TraitBound (NodeId id, TypePath type_path, Location locus,
+	      bool in_parens = false, bool opening_question_mark = false,
+	      std::vector<LifetimeParam> for_lifetimes
+	      = std::vector<LifetimeParam> ())
+    : TypeParamBound (id), in_parens (in_parens),
+      opening_question_mark (opening_question_mark),
       for_lifetimes (std::move (for_lifetimes)),
       type_path (std::move (type_path)), locus (locus)
   {}
@@ -59,18 +70,24 @@ public:
 
   Location get_locus () const { return locus; }
 
+  Location get_locus_slow () const override final { return get_locus (); }
+
   void accept_vis (ASTVisitor &vis) override;
 
   // TODO: this mutable getter seems kinda dodgy
   TypePath &get_type_path () { return type_path; }
   const TypePath &get_type_path () const { return type_path; }
 
+  bool is_in_parens () const { return in_parens; }
+  bool has_opening_question_mark () const { return opening_question_mark; }
+
 protected:
   /* Use covariance to implement clone function as returning this object rather
    * than base */
   TraitBound *clone_type_param_bound_impl () const override
   {
-    return new TraitBound (*this);
+    return new TraitBound (node_id, type_path, locus, in_parens,
+			   opening_question_mark, for_lifetimes);
   }
 };
 
diff --git a/gcc/rust/backend/rust-compile-resolve-path.cc b/gcc/rust/backend/rust-compile-resolve-path.cc
index af8d609..c87b477 100644
--- a/gcc/rust/backend/rust-compile-resolve-path.cc
+++ b/gcc/rust/backend/rust-compile-resolve-path.cc
@@ -20,6 +20,8 @@
 #include "rust-backend.h"
 #include "rust-compile-resolve-path.h"
 #include "rust-compile-item.h"
+#include "rust-hir-trait-resolve.h"
+#include "rust-hir-path-probe.h"
 
 namespace Rust {
 namespace Compile {
@@ -94,7 +96,76 @@ ResolvePathRef::visit (HIR::PathInExpression &expr)
 	  HIR::ImplItem *resolved_item
 	    = ctx->get_mappings ()->lookup_hir_implitem (
 	      expr.get_mappings ().get_crate_num (), ref, &parent_impl_id);
-	  if (resolved_item != nullptr)
+
+	  if (resolved_item == nullptr)
+	    {
+	      // it might be resolved to a trait item
+	      HIR::TraitItem *trait_item
+		= ctx->get_mappings ()->lookup_hir_trait_item (
+		  expr.get_mappings ().get_crate_num (), ref);
+	      HIR::Trait *trait
+		= ctx->get_mappings ()->lookup_trait_item_mapping (
+		  trait_item->get_mappings ().get_hirid ());
+
+	      Resolver::TraitReference &trait_ref
+		= Resolver::TraitResolver::error_node ();
+	      bool ok = ctx->get_tyctx ()->lookup_trait_reference (
+		trait->get_mappings ().get_defid (), trait_ref);
+	      rust_assert (ok);
+
+	      TyTy::BaseType *receiver = nullptr;
+	      ok = ctx->get_tyctx ()->lookup_receiver (
+		expr.get_mappings ().get_hirid (), &receiver);
+	      rust_assert (ok);
+
+	      if (receiver->get_kind () == TyTy::TypeKind::PARAM)
+		{
+		  TyTy::ParamType *p
+		    = static_cast<TyTy::ParamType *> (receiver);
+		  receiver = p->resolve ();
+		}
+
+	      // the type resolver can only resolve type bounds to their trait
+	      // item so its up to us to figure out if this path should resolve
+	      // to an trait-impl-block-item or if it can be defaulted to the
+	      // trait-impl-item's definition
+	      std::vector<Resolver::PathProbeCandidate> candidates
+		= Resolver::PathProbeType::Probe (
+		  receiver, expr.get_final_segment ().get_segment (), true,
+		  false, true);
+
+	      if (candidates.size () == 0)
+		{
+		  // this means we are defaulting back to the trait_item if
+		  // possible
+		  // TODO
+		  gcc_unreachable ();
+		}
+	      else
+		{
+		  Resolver::PathProbeCandidate &candidate = candidates.at (0);
+		  rust_assert (candidate.is_impl_candidate ());
+
+		  HIR::ImplBlock *impl = candidate.item.impl.parent;
+		  HIR::ImplItem *impl_item = candidate.item.impl.impl_item;
+
+		  TyTy::BaseType *self = nullptr;
+		  bool ok = ctx->get_tyctx ()->lookup_type (
+		    impl->get_type ()->get_mappings ().get_hirid (), &self);
+		  rust_assert (ok);
+
+		  if (!lookup->has_subsititions_defined ())
+		    CompileInherentImplItem::Compile (self, impl_item, ctx,
+						      true);
+		  else
+		    CompileInherentImplItem::Compile (self, impl_item, ctx,
+						      true, lookup);
+
+		  lookup->set_ty_ref (
+		    impl_item->get_impl_mappings ().get_hirid ());
+		}
+	    }
+	  else
 	    {
 	      rust_assert (parent_impl_id != UNKNOWN_HIRID);
 	      HIR::Item *impl_ref = ctx->get_mappings ()->lookup_hir_item (
@@ -114,18 +185,13 @@ ResolvePathRef::visit (HIR::PathInExpression &expr)
 		CompileInherentImplItem::Compile (self, resolved_item, ctx,
 						  true, lookup);
 	    }
-	  else
-	    {
-	      rust_error_at (expr.get_locus (),
-			     "failed to lookup definition declaration");
-	      return;
-	    }
 	}
 
       if (!ctx->lookup_function_decl (lookup->get_ty_ref (), &fn))
 	{
-	  rust_fatal_error (expr.get_locus (),
-			    "forward declaration was not compiled");
+	  resolved = ctx->get_backend ()->error_expression ();
+	  rust_error_at (expr.get_locus (),
+			 "forward declaration was not compiled");
 	  return;
 	}
     }
diff --git a/gcc/rust/backend/rust-compile.cc b/gcc/rust/backend/rust-compile.cc
index aa9aa2d..f422572 100644
--- a/gcc/rust/backend/rust-compile.cc
+++ b/gcc/rust/backend/rust-compile.cc
@@ -20,6 +20,8 @@
 #include "rust-compile-item.h"
 #include "rust-compile-expr.h"
 #include "rust-compile-struct-field-expr.h"
+#include "rust-hir-trait-resolve.h"
+#include "rust-hir-path-probe.h"
 #include "fnv-hash.h"
 
 namespace Rust {
@@ -141,31 +143,105 @@ CompileExpr::visit (HIR::MethodCallExpr &expr)
 	expr.get_mappings ().get_crate_num (), ref, nullptr);
       if (resolved_item == nullptr)
 	{
-	  rust_error_at (expr.get_locus (),
-			 "failed to lookup forward declaration");
-	  return;
-	}
+	  // it might be resolved to a trait item
+	  HIR::TraitItem *trait_item
+	    = ctx->get_mappings ()->lookup_hir_trait_item (
+	      expr.get_mappings ().get_crate_num (), ref);
+	  HIR::Trait *trait = ctx->get_mappings ()->lookup_trait_item_mapping (
+	    trait_item->get_mappings ().get_hirid ());
+
+	  Resolver::TraitReference &trait_ref
+	    = Resolver::TraitResolver::error_node ();
+	  bool ok = ctx->get_tyctx ()->lookup_trait_reference (
+	    trait->get_mappings ().get_defid (), trait_ref);
+	  rust_assert (ok);
+
+	  TyTy::BaseType *receiver = nullptr;
+	  ok = ctx->get_tyctx ()->lookup_receiver (
+	    expr.get_mappings ().get_hirid (), &receiver);
+	  rust_assert (ok);
+
+	  if (receiver->get_kind () == TyTy::TypeKind::PARAM)
+	    {
+	      TyTy::ParamType *p = static_cast<TyTy::ParamType *> (receiver);
+	      receiver = p->resolve ();
+	    }
 
-      TyTy::BaseType *self_type = nullptr;
-      if (!ctx->get_tyctx ()->lookup_type (
-	    expr.get_receiver ()->get_mappings ().get_hirid (), &self_type))
-	{
-	  rust_error_at (expr.get_locus (),
-			 "failed to resolve type for self param");
-	  return;
-	}
+	  // the type resolver can only resolve type bounds to their trait
+	  // item so its up to us to figure out if this path should resolve
+	  // to an trait-impl-block-item or if it can be defaulted to the
+	  // trait-impl-item's definition
+	  std::vector<Resolver::PathProbeCandidate> candidates
+	    = Resolver::PathProbeType::Probe (
+	      receiver, expr.get_method_name ().get_segment (), true, false,
+	      true);
 
-      if (!fntype->has_subsititions_defined ())
-	CompileInherentImplItem::Compile (self_type, resolved_item, ctx, true);
+	  if (candidates.size () == 0)
+	    {
+	      // this means we are defaulting back to the trait_item if
+	      // possible
+	      // TODO
+	      gcc_unreachable ();
+	    }
+	  else
+	    {
+	      Resolver::PathProbeCandidate &candidate = candidates.at (0);
+	      rust_assert (candidate.is_impl_candidate ());
+
+	      HIR::ImplItem *impl_item = candidate.item.impl.impl_item;
+
+	      TyTy::BaseType *self_type = nullptr;
+	      if (!ctx->get_tyctx ()->lookup_type (
+		    expr.get_receiver ()->get_mappings ().get_hirid (),
+		    &self_type))
+		{
+		  rust_error_at (expr.get_locus (),
+				 "failed to resolve type for self param");
+		  return;
+		}
+
+	      if (!fntype->has_subsititions_defined ())
+		CompileInherentImplItem::Compile (self_type, impl_item, ctx,
+						  true);
+	      else
+		CompileInherentImplItem::Compile (self_type, impl_item, ctx,
+						  true, fntype);
+
+	      if (!ctx->lookup_function_decl (
+		    impl_item->get_impl_mappings ().get_hirid (), &fn))
+		{
+		  translated = ctx->get_backend ()->error_expression ();
+		  rust_error_at (expr.get_locus (),
+				 "forward declaration was not compiled");
+		  return;
+		}
+	    }
+	}
       else
-	CompileInherentImplItem::Compile (self_type, resolved_item, ctx, true,
-					  fntype);
-
-      if (!ctx->lookup_function_decl (fntype->get_ty_ref (), &fn))
 	{
-	  rust_error_at (expr.get_locus (),
-			 "forward declaration was not compiled");
-	  return;
+	  TyTy::BaseType *self_type = nullptr;
+	  if (!ctx->get_tyctx ()->lookup_type (
+		expr.get_receiver ()->get_mappings ().get_hirid (), &self_type))
+	    {
+	      rust_error_at (expr.get_locus (),
+			     "failed to resolve type for self param");
+	      return;
+	    }
+
+	  if (!fntype->has_subsititions_defined ())
+	    CompileInherentImplItem::Compile (self_type, resolved_item, ctx,
+					      true);
+	  else
+	    CompileInherentImplItem::Compile (self_type, resolved_item, ctx,
+					      true, fntype);
+
+	  if (!ctx->lookup_function_decl (fntype->get_ty_ref (), &fn))
+	    {
+	      translated = ctx->get_backend ()->error_expression ();
+	      rust_error_at (expr.get_locus (),
+			     "forward declaration was not compiled");
+	      return;
+	    }
 	}
     }
 
diff --git a/gcc/rust/hir/rust-ast-lower-base.h b/gcc/rust/hir/rust-ast-lower-base.h
index 7ef5938..b1d0df3 100644
--- a/gcc/rust/hir/rust-ast-lower-base.h
+++ b/gcc/rust/hir/rust-ast-lower-base.h
@@ -245,20 +245,6 @@ protected:
 
   HIR::Lifetime lower_lifetime (AST::Lifetime &lifetime)
   {
-    HIR::Lifetime::LifetimeType type = HIR::Lifetime::LifetimeType::NAMED;
-    switch (lifetime.get_lifetime_type ())
-      {
-      case AST::Lifetime::LifetimeType::NAMED:
-	type = HIR::Lifetime::LifetimeType::NAMED;
-	break;
-      case AST::Lifetime::LifetimeType::STATIC:
-	type = HIR::Lifetime::LifetimeType::STATIC;
-	break;
-      case AST::Lifetime::LifetimeType::WILDCARD:
-	type = HIR::Lifetime::LifetimeType::WILDCARD;
-	break;
-      }
-
     auto crate_num = mappings->get_current_crate ();
     Analysis::NodeMapping mapping (crate_num, lifetime.get_node_id (),
 				   mappings->get_next_hir_id (crate_num),
@@ -266,8 +252,8 @@ protected:
     mappings->insert_node_to_hir (mapping.get_crate_num (),
 				  mapping.get_nodeid (), mapping.get_hirid ());
 
-    return HIR::Lifetime (mapping, type, lifetime.get_lifetime_name (),
-			  lifetime.get_locus ());
+    return HIR::Lifetime (mapping, lifetime.get_lifetime_type (),
+			  lifetime.get_lifetime_name (), lifetime.get_locus ());
   }
 
   HIR::LoopLabel lower_loop_label (AST::LoopLabel &loop_label)
@@ -296,6 +282,8 @@ protected:
   HIR::SelfParam lower_self (AST::SelfParam &self);
 
   HIR::Type *lower_type_no_bounds (AST::TypeNoBounds *type);
+
+  HIR::TypeParamBound *lower_bound (AST::TypeParamBound *bound);
 };
 
 } // namespace HIR
diff --git a/gcc/rust/hir/rust-ast-lower-item.h b/gcc/rust/hir/rust-ast-lower-item.h
index d49d2b2..3083554 100644
--- a/gcc/rust/hir/rust-ast-lower-item.h
+++ b/gcc/rust/hir/rust-ast-lower-item.h
@@ -496,10 +496,12 @@ public:
     std::vector<std::unique_ptr<HIR::TypeParamBound> > type_param_bounds;
 
     std::vector<std::unique_ptr<HIR::TraitItem> > trait_items;
+    std::vector<HirId> trait_item_ids;
     for (auto &item : trait.get_trait_items ())
       {
 	HIR::TraitItem *lowered = ASTLowerTraitItem::translate (item.get ());
 	trait_items.push_back (std::unique_ptr<HIR::TraitItem> (lowered));
+	trait_item_ids.push_back (lowered->get_mappings ().get_hirid ());
       }
 
     auto crate_num = mappings->get_current_crate ();
@@ -507,17 +509,24 @@ public:
 				   mappings->get_next_hir_id (crate_num),
 				   mappings->get_next_localdef_id (crate_num));
 
-    translated = new HIR::Trait (mapping, trait.get_identifier (),
-				 trait.is_unsafe (), std::move (generic_params),
-				 std::move (type_param_bounds), where_clause,
-				 std::move (trait_items), vis,
-				 trait.get_outer_attrs (), trait.get_locus ());
+    HIR::Trait *hir_trait
+      = new HIR::Trait (mapping, trait.get_identifier (), trait.is_unsafe (),
+			std::move (generic_params),
+			std::move (type_param_bounds), where_clause,
+			std::move (trait_items), vis, trait.get_outer_attrs (),
+			trait.get_locus ());
+    translated = hir_trait;
 
     mappings->insert_defid_mapping (mapping.get_defid (), translated);
     mappings->insert_hir_item (mapping.get_crate_num (), mapping.get_hirid (),
 			       translated);
     mappings->insert_location (crate_num, mapping.get_hirid (),
 			       trait.get_locus ());
+
+    for (auto trait_item_id : trait_item_ids)
+      {
+	mappings->insert_trait_item_mapping (trait_item_id, hir_trait);
+      }
   }
 
   void visit (AST::TraitImpl &impl_block) override
diff --git a/gcc/rust/hir/rust-ast-lower-type.h b/gcc/rust/hir/rust-ast-lower-type.h
index efaf9db..9b5ec0a 100644
--- a/gcc/rust/hir/rust-ast-lower-type.h
+++ b/gcc/rust/hir/rust-ast-lower-type.h
@@ -284,6 +284,9 @@ public:
       resolver.translated->get_mappings ().get_crate_num (),
       resolver.translated->get_mappings ().get_hirid (),
       param->get_locus_slow ());
+    resolver.mappings->insert_hir_generic_param (
+      resolver.translated->get_mappings ().get_crate_num (),
+      resolver.translated->get_mappings ().get_hirid (), resolver.translated);
 
     return resolver.translated;
   }
@@ -294,24 +297,9 @@ public:
     Analysis::NodeMapping mapping (crate_num, param.get_node_id (),
 				   mappings->get_next_hir_id (crate_num),
 				   mappings->get_next_localdef_id (crate_num));
-    HIR::Lifetime::LifetimeType ltt;
 
-    switch (param.get_lifetime ().get_lifetime_type ())
-      {
-      case AST::Lifetime::LifetimeType::NAMED:
-	ltt = HIR::Lifetime::LifetimeType::NAMED;
-	break;
-      case AST::Lifetime::LifetimeType::STATIC:
-	ltt = HIR::Lifetime::LifetimeType::STATIC;
-	break;
-      case AST::Lifetime::LifetimeType::WILDCARD:
-	ltt = HIR::Lifetime::LifetimeType::WILDCARD;
-	break;
-      default:
-	gcc_unreachable ();
-      }
-
-    HIR::Lifetime lt (mapping, ltt, param.get_lifetime ().get_lifetime_name (),
+    HIR::Lifetime lt (mapping, param.get_lifetime ().get_lifetime_type (),
+		      param.get_lifetime ().get_lifetime_name (),
 		      param.get_lifetime ().get_locus ());
 
     translated = new HIR::LifetimeParam (mapping, lt, param.get_locus (),
@@ -322,6 +310,16 @@ public:
   {
     AST::Attribute outer_attr = AST::Attribute::create_empty ();
     std::vector<std::unique_ptr<HIR::TypeParamBound> > type_param_bounds;
+    if (param.has_type_param_bounds ())
+      {
+	for (auto &bound : param.get_type_param_bounds ())
+	  {
+	    HIR::TypeParamBound *lowered_bound = lower_bound (bound.get ());
+	    type_param_bounds.push_back (
+	      std::unique_ptr<HIR::TypeParamBound> (lowered_bound));
+	  }
+      }
+
     HIR::Type *type = param.has_type ()
 			? ASTLoweringType::translate (param.get_type ().get ())
 			: nullptr;
@@ -344,6 +342,55 @@ private:
   HIR::GenericParam *translated;
 };
 
+class ASTLoweringTypeBounds : public ASTLoweringBase
+{
+  using Rust::HIR::ASTLoweringBase::visit;
+
+public:
+  static HIR::TypeParamBound *translate (AST::TypeParamBound *type)
+  {
+    ASTLoweringTypeBounds resolver;
+    type->accept_vis (resolver);
+
+    rust_assert (resolver.translated != nullptr);
+    resolver.mappings->insert_location (
+      resolver.translated->get_mappings ().get_crate_num (),
+      resolver.translated->get_mappings ().get_hirid (),
+      resolver.translated->get_locus_slow ());
+
+    return resolver.translated;
+  }
+
+  void visit (AST::TraitBound &bound) override
+  {
+    // FIXME
+    std::vector<HIR::LifetimeParam> lifetimes;
+
+    AST::TypePath &ast_trait_path = bound.get_type_path ();
+    HIR::TypePath *trait_path = ASTLowerTypePath::translate (ast_trait_path);
+
+    auto crate_num = mappings->get_current_crate ();
+    Analysis::NodeMapping mapping (crate_num, bound.get_node_id (),
+				   mappings->get_next_hir_id (crate_num),
+				   UNKNOWN_LOCAL_DEFID);
+
+    translated = new HIR::TraitBound (mapping, *trait_path, bound.get_locus (),
+				      bound.is_in_parens (),
+				      bound.has_opening_question_mark ());
+  }
+
+  void visit (AST::Lifetime &bound) override
+  {
+    HIR::Lifetime lifetime = lower_lifetime (bound);
+    translated = new HIR::Lifetime (lifetime);
+  }
+
+private:
+  ASTLoweringTypeBounds () : ASTLoweringBase (), translated (nullptr) {}
+
+  HIR::TypeParamBound *translated;
+};
+
 } // namespace HIR
 } // namespace Rust
 
diff --git a/gcc/rust/hir/rust-ast-lower.cc b/gcc/rust/hir/rust-ast-lower.cc
index 04587ed..ed59777 100644
--- a/gcc/rust/hir/rust-ast-lower.cc
+++ b/gcc/rust/hir/rust-ast-lower.cc
@@ -263,6 +263,12 @@ ASTLowerPathInExpression::visit (AST::PathInExpression &expr)
   std::vector<HIR::PathExprSegment> path_segments;
   expr.iterate_path_segments ([&] (AST::PathExprSegment &s) mutable -> bool {
     path_segments.push_back (lower_path_expr_seg (s));
+
+    // insert the mappings for the segment
+    HIR::PathExprSegment *lowered_seg = &path_segments.back ();
+    mappings->insert_hir_path_expr_seg (
+      lowered_seg->get_mappings ().get_crate_num (),
+      lowered_seg->get_mappings ().get_hirid (), lowered_seg);
     return true;
   });
 
@@ -403,5 +409,11 @@ ASTLoweringBase::lower_type_no_bounds (AST::TypeNoBounds *type)
   return ASTLoweringType::translate (type);
 }
 
+HIR::TypeParamBound *
+ASTLoweringBase::lower_bound (AST::TypeParamBound *bound)
+{
+  return ASTLoweringTypeBounds::translate (bound);
+}
+
 } // namespace HIR
 } // namespace Rust
diff --git a/gcc/rust/hir/tree/rust-hir-full-test.cc b/gcc/rust/hir/tree/rust-hir-full-test.cc
index d61d060..dee2827 100644
--- a/gcc/rust/hir/tree/rust-hir-full-test.cc
+++ b/gcc/rust/hir/tree/rust-hir-full-test.cc
@@ -2113,11 +2113,11 @@ Lifetime::as_string () const
 
   switch (lifetime_type)
     {
-    case NAMED:
+    case AST::Lifetime::LifetimeType::NAMED:
       return "'" + lifetime_name;
-    case STATIC:
+    case AST::Lifetime::LifetimeType::STATIC:
       return "'static";
-    case WILDCARD:
+    case AST::Lifetime::LifetimeType::WILDCARD:
       return "'_";
     default:
       return "ERROR-MARK-STRING: lifetime type failure";
@@ -2747,7 +2747,8 @@ TypePath::to_trait_bound (bool in_parens) const
   // create clone FIXME is this required? or is copy constructor automatically
   // called?
   TypePath copy (*this);
-  return new TraitBound (std::move (copy), copy.get_locus (), in_parens);
+  return new TraitBound (mappings, std::move (copy), copy.get_locus (),
+			 in_parens);
 }
 
 std::string
diff --git a/gcc/rust/hir/tree/rust-hir-item.h b/gcc/rust/hir/tree/rust-hir-item.h
index 182fe87..ba04339 100644
--- a/gcc/rust/hir/tree/rust-hir-item.h
+++ b/gcc/rust/hir/tree/rust-hir-item.h
@@ -124,6 +124,11 @@ public:
     return type->get_mappings ();
   }
 
+  std::vector<std::unique_ptr<TypeParamBound> > &get_type_param_bounds ()
+  {
+    return type_param_bounds;
+  }
+
 protected:
   // Clone function implementation as (not pure) virtual method
   TypeParam *clone_generic_param_impl () const override
@@ -333,7 +338,8 @@ public:
   SelfParam (Analysis::NodeMapping mappings, std::unique_ptr<Type> type,
 	     bool is_mut, Location locus)
     : self_kind (is_mut ? ImplicitSelfKind::MUT : ImplicitSelfKind::IMM),
-      lifetime (Lifetime (mappings, Lifetime::LifetimeType::NAMED, "", locus)),
+      lifetime (
+	Lifetime (mappings, AST::Lifetime::LifetimeType::NAMED, "", locus)),
       type (std::move (type)), locus (locus), mappings (mappings)
   {}
 
diff --git a/gcc/rust/hir/tree/rust-hir-type.h b/gcc/rust/hir/tree/rust-hir-type.h
index 3cb4be1..8d75d02 100644
--- a/gcc/rust/hir/tree/rust-hir-type.h
+++ b/gcc/rust/hir/tree/rust-hir-type.h
@@ -33,26 +33,23 @@ class TraitBound : public TypeParamBound
 {
   bool in_parens;
   bool opening_question_mark;
-
-  // bool has_for_lifetimes;
-  // LifetimeParams for_lifetimes;
-  std::vector<LifetimeParam> for_lifetimes; // inlined LifetimeParams
-
+  std::vector<LifetimeParam> for_lifetimes;
   TypePath type_path;
-
   Location locus;
 
+  Analysis::NodeMapping mappings;
+
 public:
   // Returns whether trait bound has "for" lifetimes
   bool has_for_lifetimes () const { return !for_lifetimes.empty (); }
 
-  TraitBound (TypePath type_path, Location locus, bool in_parens = false,
-	      bool opening_question_mark = false,
+  TraitBound (Analysis::NodeMapping mapping, TypePath type_path, Location locus,
+	      bool in_parens = false, bool opening_question_mark = false,
 	      std::vector<LifetimeParam> for_lifetimes
 	      = std::vector<LifetimeParam> ())
     : in_parens (in_parens), opening_question_mark (opening_question_mark),
       for_lifetimes (std::move (for_lifetimes)),
-      type_path (std::move (type_path)), locus (locus)
+      type_path (std::move (type_path)), locus (locus), mappings (mapping)
   {}
 
   std::string as_string () const override;
@@ -61,6 +58,19 @@ public:
 
   void accept_vis (HIRVisitor &vis) override;
 
+  Analysis::NodeMapping get_mappings () const override final
+  {
+    return mappings;
+  }
+
+  Location get_locus_slow () const override final { return get_locus (); }
+
+  BoundType get_bound_type () const final override { return TRAITBOUND; }
+
+  TypePath &get_path () { return type_path; }
+
+  const TypePath &get_path () const { return type_path; }
+
 protected:
   /* Use covariance to implement clone function as returning this object rather
    * than base */
diff --git a/gcc/rust/hir/tree/rust-hir.h b/gcc/rust/hir/tree/rust-hir.h
index 7d53feb..20408bb 100644
--- a/gcc/rust/hir/tree/rust-hir.h
+++ b/gcc/rust/hir/tree/rust-hir.h
@@ -406,6 +406,12 @@ protected:
 class TypeParamBound
 {
 public:
+  enum BoundType
+  {
+    LIFETIME,
+    TRAITBOUND
+  };
+
   virtual ~TypeParamBound () {}
 
   // Unique pointer custom clone function
@@ -418,6 +424,12 @@ public:
 
   virtual void accept_vis (HIRVisitor &vis) = 0;
 
+  virtual Analysis::NodeMapping get_mappings () const = 0;
+
+  virtual Location get_locus_slow () const = 0;
+
+  virtual BoundType get_bound_type () const = 0;
+
 protected:
   // Clone function implementation as pure virtual method
   virtual TypeParamBound *clone_type_param_bound_impl () const = 0;
@@ -426,30 +438,16 @@ protected:
 // Represents a lifetime (and is also a kind of type param bound)
 class Lifetime : public TypeParamBound
 {
-public:
-  enum LifetimeType
-  {
-    NAMED,   // corresponds to LIFETIME_OR_LABEL
-    STATIC,  // corresponds to 'static
-    WILDCARD // corresponds to '_
-  };
-
 private:
-  LifetimeType lifetime_type;
-
-  // TODO: LIFETIME_OR_LABEL (aka lifetime token) is only field
-  // find way of enclosing token or something
+  AST::Lifetime::LifetimeType lifetime_type;
   std::string lifetime_name;
-  // only applies for NAMED lifetime_type
-
   Location locus;
-
   Analysis::NodeMapping mappings;
 
 public:
   // Constructor
-  Lifetime (Analysis::NodeMapping mapping, LifetimeType type, std::string name,
-	    Location locus)
+  Lifetime (Analysis::NodeMapping mapping, AST::Lifetime::LifetimeType type,
+	    std::string name, Location locus)
     : lifetime_type (type), lifetime_name (std::move (name)), locus (locus),
       mappings (mapping)
   {}
@@ -457,13 +455,14 @@ public:
   // Returns true if the lifetime is in an error state.
   bool is_error () const
   {
-    return lifetime_type == NAMED && lifetime_name.empty ();
+    return lifetime_type == AST::Lifetime::LifetimeType::NAMED
+	   && lifetime_name.empty ();
   }
 
   static Lifetime error ()
   {
-    return Lifetime (Analysis::NodeMapping::get_error (), LifetimeType::NAMED,
-		     "", Location ());
+    return Lifetime (Analysis::NodeMapping::get_error (),
+		     AST::Lifetime::LifetimeType::NAMED, "", Location ());
   }
 
   std::string as_string () const override;
@@ -472,11 +471,21 @@ public:
 
   std::string get_name () const { return lifetime_name; }
 
-  LifetimeType get_lifetime_type () const { return lifetime_type; }
+  AST::Lifetime::LifetimeType get_lifetime_type () const
+  {
+    return lifetime_type;
+  }
 
   Location get_locus () const { return locus; }
 
-  Analysis::NodeMapping get_mappings () const { return mappings; }
+  Analysis::NodeMapping get_mappings () const override final
+  {
+    return mappings;
+  }
+
+  Location get_locus_slow () const override final { return get_locus (); }
+
+  BoundType get_bound_type () const final override { return LIFETIME; }
 
 protected:
   /* Use covariance to implement clone function as returning this object rather
diff --git a/gcc/rust/resolve/rust-ast-resolve-type.h b/gcc/rust/resolve/rust-ast-resolve-type.h
index d826d68..46ebdc4 100644
--- a/gcc/rust/resolve/rust-ast-resolve-type.h
+++ b/gcc/rust/resolve/rust-ast-resolve-type.h
@@ -297,6 +297,42 @@ private:
   bool ok;
 };
 
+class ResolveTypeBound : public ResolverBase
+{
+  using Rust::Resolver::ResolverBase::visit;
+
+public:
+  static NodeId go (AST::TypeParamBound *type, NodeId parent,
+		    bool canonicalize_type_with_generics = false)
+  {
+    ResolveTypeBound resolver (parent, canonicalize_type_with_generics);
+    type->accept_vis (resolver);
+    if (!resolver.ok)
+      rust_error_at (type->get_locus_slow (), "unresolved type bound");
+
+    return resolver.resolved_node;
+  };
+
+  void visit (AST::TraitBound &bound) override
+  {
+    resolved_node = ResolveType::go (&bound.get_type_path (), parent,
+				     canonicalize_type_with_generics);
+    ok = resolved_node != UNKNOWN_NODEID;
+  }
+
+  void visit (AST::Lifetime &bound) override { ok = true; }
+
+private:
+  ResolveTypeBound (NodeId parent, bool canonicalize_type_with_generics)
+    : ResolverBase (parent),
+      canonicalize_type_with_generics (canonicalize_type_with_generics),
+      ok (false)
+  {}
+
+  bool canonicalize_type_with_generics;
+  bool ok;
+};
+
 class ResolveGenericParam : public ResolverBase
 {
   using Rust::Resolver::ResolverBase::visit;
@@ -326,6 +362,14 @@ public:
     if (param.has_type ())
       ResolveType::go (param.get_type ().get (), param.get_node_id ());
 
+    if (param.has_type_param_bounds ())
+      {
+	for (auto &bound : param.get_type_param_bounds ())
+	  {
+	    ResolveTypeBound::go (bound.get (), param.get_node_id ());
+	  }
+      }
+
     // for now lets focus on handling the basics: like struct<T> { a:T, ....}
     resolver->get_type_scope ().insert (
       CanonicalPath::new_seg (param.get_node_id (),
diff --git a/gcc/rust/typecheck/rust-hir-path-probe.h b/gcc/rust/typecheck/rust-hir-path-probe.h
index 1b7aa4d..8e3ca31 100644
--- a/gcc/rust/typecheck/rust-hir-path-probe.h
+++ b/gcc/rust/typecheck/rust-hir-path-probe.h
@@ -23,6 +23,7 @@
 #include "rust-hir-full.h"
 #include "rust-tyty.h"
 #include "rust-substitution-mapper.h"
+#include "rust-hir-type-bounds.h"
 
 namespace Rust {
 namespace Resolver {
@@ -34,12 +35,80 @@ struct PathProbeCandidate
     IMPL_CONST,
     IMPL_TYPE_ALIAS,
     IMPL_FUNC,
+
+    TRAIT_ITEM_CONST,
+    TRAIT_TYPE_ALIAS,
+    TRAIT_FUNC,
+  };
+
+  struct ImplItemCandidate
+  {
+    HIR::ImplItem *impl_item;
+    HIR::ImplBlock *parent;
+  };
+
+  struct TraitItemCandidate
+  {
+    const TraitReference &trait_ref;
+    const TraitItemReference &item_ref;
   };
 
   CandidateType type;
-  HIR::ImplItem *impl_item;
   TyTy::BaseType *ty;
-  HIR::ImplBlock *parent;
+  Location locus;
+  union Candidate
+  {
+    ImplItemCandidate impl;
+    TraitItemCandidate trait;
+
+    Candidate (ImplItemCandidate impl) : impl (impl) {}
+    Candidate (TraitItemCandidate trait) : trait (trait) {}
+  } item;
+
+  PathProbeCandidate (CandidateType type, TyTy::BaseType *ty, Location locus,
+		      ImplItemCandidate impl)
+    : type (type), ty (ty), item (impl)
+  {}
+
+  PathProbeCandidate (CandidateType type, TyTy::BaseType *ty, Location locus,
+		      TraitItemCandidate trait)
+    : type (type), ty (ty), item (trait)
+  {}
+
+  std::string as_string () const
+  {
+    return "PathProbe candidate TODO - as_string";
+  }
+
+  bool is_impl_candidate () const
+  {
+    switch (type)
+      {
+      case IMPL_CONST:
+      case IMPL_TYPE_ALIAS:
+      case IMPL_FUNC:
+	return true;
+
+      default:
+	return false;
+      }
+    gcc_unreachable ();
+  }
+
+  bool is_trait_candidate () const
+  {
+    switch (type)
+      {
+      case TRAIT_ITEM_CONST:
+      case TRAIT_TYPE_ALIAS:
+      case TRAIT_FUNC:
+	return true;
+
+      default:
+	return false;
+      }
+    gcc_unreachable ();
+  }
 };
 
 class PathProbeType : public TypeCheckBase
@@ -48,32 +117,33 @@ class PathProbeType : public TypeCheckBase
 
 public:
   static std::vector<PathProbeCandidate>
-  Probe (TyTy::BaseType *receiver, const HIR::PathIdentSegment &segment_name)
+  Probe (const TyTy::BaseType *receiver,
+	 const HIR::PathIdentSegment &segment_name, bool probe_impls,
+	 bool probe_bounds, bool ignore_mandatory_trait_items)
   {
     PathProbeType probe (receiver, segment_name);
-    probe.mappings->iterate_impl_items (
-      [&] (HirId id, HIR::ImplItem *item,
-	   HIR::ImplBlock *impl) mutable -> bool {
-	probe.process_candidate (id, item, impl);
-	return true;
-      });
+    if (probe_impls)
+      probe.process_impl_items_for_candidates ();
 
-    return probe.candidates;
-  }
+    if (!probe_bounds)
+      return probe.candidates;
 
-  void process_candidate (HirId id, HIR::ImplItem *item, HIR::ImplBlock *impl)
-  {
-    current_impl = impl;
-    HirId impl_ty_id = impl->get_type ()->get_mappings ().get_hirid ();
-    TyTy::BaseType *impl_block_ty = nullptr;
-    bool ok = context->lookup_type (impl_ty_id, &impl_block_ty);
-    rust_assert (ok);
+    std::vector<std::reference_wrapper<TraitReference>> probed_bounds
+      = TypeBoundsProbe::Probe (receiver);
 
-    if (!receiver->can_eq (impl_block_ty, false))
-      return;
+    std::vector<std::reference_wrapper<const TraitReference>> specified_bounds;
+    for (const TyTy::TypeBoundPredicate &predicate :
+	 receiver->get_specified_bounds ())
+      {
+	const TraitReference *trait_item = predicate.get ();
+	specified_bounds.push_back (*trait_item);
+      }
 
-    // lets visit the impl_item
-    item->accept_vis (*this);
+    std::vector<std::reference_wrapper<const TraitReference>> union_type_bounds
+      = probe.union_bounds (probed_bounds, specified_bounds);
+    probe.process_traits_for_candidates (union_type_bounds,
+					 ignore_mandatory_trait_items);
+    return probe.candidates;
   }
 
   void visit (HIR::TypeAlias &alias) override
@@ -86,9 +156,11 @@ public:
 	bool ok = context->lookup_type (tyid, &ty);
 	rust_assert (ok);
 
+	PathProbeCandidate::ImplItemCandidate impl_item_candidate{&alias,
+								  current_impl};
 	PathProbeCandidate candidate{
-	  PathProbeCandidate::CandidateType::IMPL_TYPE_ALIAS, &alias, ty,
-	  current_impl};
+	  PathProbeCandidate::CandidateType::IMPL_TYPE_ALIAS, ty,
+	  alias.get_locus (), impl_item_candidate};
 	candidates.push_back (std::move (candidate));
       }
   }
@@ -103,9 +175,11 @@ public:
 	bool ok = context->lookup_type (tyid, &ty);
 	rust_assert (ok);
 
+	PathProbeCandidate::ImplItemCandidate impl_item_candidate{&constant,
+								  current_impl};
 	PathProbeCandidate candidate{
-	  PathProbeCandidate::CandidateType::IMPL_CONST, &constant, ty,
-	  current_impl};
+	  PathProbeCandidate::CandidateType::IMPL_CONST, ty,
+	  constant.get_locus (), impl_item_candidate};
 	candidates.push_back (std::move (candidate));
       }
   }
@@ -120,20 +194,146 @@ public:
 	bool ok = context->lookup_type (tyid, &ty);
 	rust_assert (ok);
 
+	PathProbeCandidate::ImplItemCandidate impl_item_candidate{&function,
+								  current_impl};
 	PathProbeCandidate candidate{
-	  PathProbeCandidate::CandidateType::IMPL_FUNC, &function, ty,
-	  current_impl};
+	  PathProbeCandidate::CandidateType::IMPL_FUNC, ty,
+	  function.get_locus (), impl_item_candidate};
 	candidates.push_back (std::move (candidate));
       }
   }
 
 private:
-  PathProbeType (TyTy::BaseType *receiver, const HIR::PathIdentSegment &query)
+  void process_impl_items_for_candidates ()
+  {
+    mappings->iterate_impl_items ([&] (HirId id, HIR::ImplItem *item,
+				       HIR::ImplBlock *impl) mutable -> bool {
+      process_impl_item_candidate (id, item, impl);
+      return true;
+    });
+  }
+
+  void process_impl_item_candidate (HirId id, HIR::ImplItem *item,
+				    HIR::ImplBlock *impl)
+  {
+    current_impl = impl;
+    HirId impl_ty_id = impl->get_type ()->get_mappings ().get_hirid ();
+    TyTy::BaseType *impl_block_ty = nullptr;
+    bool ok = context->lookup_type (impl_ty_id, &impl_block_ty);
+    rust_assert (ok);
+
+    if (!receiver->can_eq (impl_block_ty, false))
+      return;
+
+    // lets visit the impl_item
+    item->accept_vis (*this);
+  }
+
+  void process_traits_for_candidates (
+    const std::vector<std::reference_wrapper<const TraitReference>> traits,
+    bool ignore_mandatory_trait_items)
+  {
+    for (const TraitReference &trait_ref : traits)
+      {
+	const TraitItemReference &trait_item_ref
+	  = trait_ref.lookup_trait_item (search.as_string ());
+	if (trait_item_ref.is_error ())
+	  continue;
+
+	bool trait_item_needs_implementation = !trait_item_ref.is_optional ();
+	if (ignore_mandatory_trait_items && trait_item_needs_implementation)
+	  continue;
+
+	PathProbeCandidate::CandidateType candidate_type;
+	switch (trait_item_ref.get_trait_item_type ())
+	  {
+	  case TraitItemReference::TraitItemType::FN:
+	    candidate_type = PathProbeCandidate::CandidateType::TRAIT_FUNC;
+	    break;
+	  case TraitItemReference::TraitItemType::CONST:
+	    candidate_type
+	      = PathProbeCandidate::CandidateType::TRAIT_ITEM_CONST;
+	    break;
+	  case TraitItemReference::TraitItemType::TYPE:
+	    candidate_type
+	      = PathProbeCandidate::CandidateType::TRAIT_TYPE_ALIAS;
+	    break;
+
+	  case TraitItemReference::TraitItemType::ERROR:
+	    gcc_unreachable ();
+	    break;
+	  }
+
+	TyTy::BaseType *trait_item_tyty = trait_item_ref.get_tyty ();
+
+	// we can substitute the Self with the receiver here
+	if (trait_item_tyty->get_kind () == TyTy::TypeKind::FNDEF)
+	  {
+	    TyTy::FnType *fn = static_cast<TyTy::FnType *> (trait_item_tyty);
+	    TyTy::SubstitutionParamMapping *param = nullptr;
+	    for (auto &param_mapping : fn->get_substs ())
+	      {
+		const HIR::TypeParam &type_param
+		  = param_mapping.get_generic_param ();
+		if (type_param.get_type_representation ().compare ("Self") == 0)
+		  {
+		    param = &param_mapping;
+		    break;
+		  }
+	      }
+	    rust_assert (param != nullptr);
+
+	    std::vector<TyTy::SubstitutionArg> mappings;
+	    mappings.push_back (
+	      TyTy::SubstitutionArg (param, receiver->clone ()));
+
+	    Location locus; // FIXME
+	    TyTy::SubstitutionArgumentMappings args (std::move (mappings),
+						     locus);
+	    trait_item_tyty
+	      = SubstMapperInternal::Resolve (trait_item_tyty, args);
+	  }
+
+	PathProbeCandidate::TraitItemCandidate trait_item_candidate{
+	  trait_ref, trait_item_ref};
+	PathProbeCandidate candidate{candidate_type,
+				     trait_item_tyty,
+				     trait_ref.get_locus (),
+				     {trait_item_candidate}};
+	candidates.push_back (std::move (candidate));
+      }
+  }
+
+private:
+  PathProbeType (const TyTy::BaseType *receiver,
+		 const HIR::PathIdentSegment &query)
     : TypeCheckBase (), receiver (receiver), search (query),
       current_impl (nullptr)
   {}
 
-  TyTy::BaseType *receiver;
+  std::vector<std::reference_wrapper<const TraitReference>> union_bounds (
+    const std::vector<std::reference_wrapper</*const*/ TraitReference>> a,
+    const std::vector<std::reference_wrapper<const TraitReference>> b) const
+  {
+    std::map<DefId, std::reference_wrapper<const TraitReference>> mapper;
+    for (const TraitReference &ref : a)
+      {
+	mapper.insert ({ref.get_mappings ().get_defid (), ref});
+      }
+    for (const TraitReference &ref : b)
+      {
+	mapper.insert ({ref.get_mappings ().get_defid (), ref});
+      }
+
+    std::vector<std::reference_wrapper<const TraitReference>> union_set;
+    for (auto it = mapper.begin (); it != mapper.end (); it++)
+      {
+	union_set.push_back (it->second);
+      }
+    return union_set;
+  }
+
+  const TyTy::BaseType *receiver;
   const HIR::PathIdentSegment &search;
   std::vector<PathProbeCandidate> candidates;
   HIR::ImplBlock *current_impl;
@@ -150,7 +350,22 @@ public:
     RichLocation r (query_locus);
     ReportMultipleCandidateError visitor (r);
     for (auto &c : candidates)
-      c.impl_item->accept_vis (visitor);
+      {
+	switch (c.type)
+	  {
+	  case PathProbeCandidate::CandidateType::IMPL_CONST:
+	  case PathProbeCandidate::CandidateType::IMPL_TYPE_ALIAS:
+	  case PathProbeCandidate::CandidateType::IMPL_FUNC:
+	    c.item.impl.impl_item->accept_vis (visitor);
+	    break;
+
+	  case PathProbeCandidate::CandidateType::TRAIT_ITEM_CONST:
+	  case PathProbeCandidate::CandidateType::TRAIT_TYPE_ALIAS:
+	  case PathProbeCandidate::CandidateType::TRAIT_FUNC:
+	    r.add_range (c.item.trait.item_ref.get_locus ());
+	    break;
+	  }
+      }
 
     rust_error_at (r, "multiple applicable items in scope for: %s",
 		   query.as_string ().c_str ());
diff --git a/gcc/rust/typecheck/rust-hir-trait-ref.h b/gcc/rust/typecheck/rust-hir-trait-ref.h
index 35c0fef..b19c38a 100644
--- a/gcc/rust/typecheck/rust-hir-trait-ref.h
+++ b/gcc/rust/typecheck/rust-hir-trait-ref.h
@@ -56,6 +56,7 @@ public:
     locus = other.locus;
     context = other.context;
 
+    inherited_substitutions.clear ();
     inherited_substitutions.reserve (other.inherited_substitutions.size ());
     for (size_t i = 0; i < other.inherited_substitutions.size (); i++)
       inherited_substitutions.push_back (other.inherited_substitutions.at (i));
@@ -221,6 +222,21 @@ public:
 	   + "]";
   }
 
+  const Analysis::NodeMapping &get_mappings () const
+  {
+    return hir_trait_ref->get_mappings ();
+  }
+
+  const TraitItemReference &lookup_trait_item (const std::string &ident) const
+  {
+    for (auto &item : item_refs)
+      {
+	if (ident.compare (item.get_identifier ()) == 0)
+	  return item;
+      }
+    return TraitItemReference::error_node ();
+  }
+
   const TraitItemReference &
   lookup_trait_item (const std::string &ident,
 		     TraitItemReference::TraitItemType type) const
diff --git a/gcc/rust/typecheck/rust-hir-trait-resolve.h b/gcc/rust/typecheck/rust-hir-trait-resolve.h
index 3de68c8..6d7c864 100644
--- a/gcc/rust/typecheck/rust-hir-trait-resolve.h
+++ b/gcc/rust/typecheck/rust-hir-trait-resolve.h
@@ -121,8 +121,7 @@ private:
     if (!resolver->lookup_resolved_type (path.get_mappings ().get_nodeid (),
 					 &ref))
       {
-	rust_fatal_error (path.get_locus (),
-			  "Failed to resolve path to node-id");
+	rust_error_at (path.get_locus (), "Failed to resolve path to node-id");
 	return error_node ();
       }
 
@@ -130,8 +129,7 @@ private:
     if (!mappings->lookup_node_to_hir (mappings->get_current_crate (), ref,
 				       &hir_node))
       {
-	rust_fatal_error (path.get_locus (),
-			  "Failed to resolve path to hir-id");
+	rust_error_at (path.get_locus (), "Failed to resolve path to hir-id");
 	return error_node ();
       }
 
diff --git a/gcc/rust/typecheck/rust-hir-type-bounds.h b/gcc/rust/typecheck/rust-hir-type-bounds.h
new file mode 100644
index 0000000..d97c0f5
--- /dev/null
+++ b/gcc/rust/typecheck/rust-hir-type-bounds.h
@@ -0,0 +1,57 @@
+// Copyright (C) 2021 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_HIR_TYPE_BOUNDS_H
+#define RUST_HIR_TYPE_BOUNDS_H
+
+#include "rust-hir-type-check-base.h"
+#include "rust-hir-full.h"
+#include "rust-tyty.h"
+
+namespace Rust {
+namespace Resolver {
+
+class TypeBoundsProbe : public TypeCheckBase
+{
+  using Rust::Resolver::TypeCheckBase::visit;
+
+public:
+  static std::vector<std::reference_wrapper<TraitReference>>
+  Probe (const TyTy::BaseType *receiver)
+  {
+    TypeBoundsProbe probe (receiver);
+    probe.scan ();
+    return probe.trait_references;
+  }
+
+private:
+  void scan ();
+
+private:
+  TypeBoundsProbe (const TyTy::BaseType *receiver)
+    : TypeCheckBase (), receiver (receiver)
+  {}
+
+  const TyTy::BaseType *receiver;
+  std::vector<std::reference_wrapper<TraitReference>> trait_references;
+};
+
+} // namespace Resolver
+} // namespace Rust
+
+#endif // RUST_HIR_TYPE_BOUNDS_H
diff --git a/gcc/rust/typecheck/rust-hir-type-check-base.h b/gcc/rust/typecheck/rust-hir-type-check-base.h
index ae71611..f05ab86 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-base.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-base.h
@@ -28,6 +28,8 @@
 namespace Rust {
 namespace Resolver {
 
+class TraitReference;
+
 // base class to allow derivatives to overload as needed
 class TypeCheckBase : public HIR::HIRVisitor
 {
@@ -200,6 +202,8 @@ protected:
       context (TypeCheckContext::get ())
   {}
 
+  TraitReference &resolve_trait_path (HIR::TypePath &);
+
   Analysis::Mappings *mappings;
   Resolver *resolver;
   TypeCheckContext *context;
diff --git a/gcc/rust/typecheck/rust-hir-type-check-expr.h b/gcc/rust/typecheck/rust-hir-type-check-expr.h
index bd42b4c..7f1a83d 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-expr.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-expr.h
@@ -205,15 +205,25 @@ public:
 	return;
       }
 
+    context->insert_receiver (expr.get_mappings ().get_hirid (), receiver_tyty);
+
     // https://doc.rust-lang.org/reference/expressions/method-call-expr.html
     // method resolution is complex in rust once we start handling generics and
     // traits. For now we only support looking up the valid name in impl blocks
     // which is simple. There will need to be adjustments to ensure we can turn
     // the receiver into borrowed references etc
 
+    bool reciever_is_generic
+      = receiver_tyty->get_kind () == TyTy::TypeKind::PARAM;
+    bool probe_bounds = true;
+    bool probe_impls = !reciever_is_generic;
+    bool ignore_mandatory_trait_items = !reciever_is_generic;
+
     auto candidates
       = PathProbeType::Probe (receiver_tyty,
-			      expr.get_method_name ().get_segment ());
+			      expr.get_method_name ().get_segment (),
+			      probe_impls, probe_bounds,
+			      ignore_mandatory_trait_items);
     if (candidates.size () == 0)
       {
 	rust_error_at (expr.get_locus (),
@@ -229,13 +239,18 @@ public:
       }
 
     auto resolved_candidate = candidates.at (0);
-    HIR::ImplItem *resolved_method = resolved_candidate.impl_item;
     TyTy::BaseType *lookup_tyty = resolved_candidate.ty;
+    NodeId resolved_node_id
+      = resolved_candidate.is_impl_candidate ()
+	  ? resolved_candidate.item.impl.impl_item->get_impl_mappings ()
+	      .get_nodeid ()
+	  : resolved_candidate.item.trait.item_ref.get_mappings ()
+	      .get_nodeid ();
 
     if (lookup_tyty->get_kind () != TyTy::TypeKind::FNDEF)
       {
 	RichLocation r (expr.get_method_name ().get_locus ());
-	r.add_range (resolved_method->get_impl_locus ());
+	r.add_range (resolved_candidate.locus);
 	rust_error_at (r, "associated impl item is not a method");
 	return;
       }
@@ -245,7 +260,7 @@ public:
     if (!fn->is_method ())
       {
 	RichLocation r (expr.get_method_name ().get_locus ());
-	r.add_range (resolved_method->get_impl_locus ());
+	r.add_range (resolved_candidate.locus);
 	rust_error_at (r, "associated function is not a method");
 	return;
       }
@@ -303,20 +318,25 @@ public:
 	  }
       }
 
-    // apply any remaining generic arguments
-    if (expr.get_method_name ().has_generic_args ())
-      {
-	HIR::GenericArgs &args = expr.get_method_name ().get_generic_args ();
-	lookup
-	  = SubstMapper::Resolve (lookup, expr.get_method_name ().get_locus (),
-				  &args);
-	if (lookup->get_kind () == TyTy::TypeKind::ERROR)
-	  return;
-      }
-    else if (lookup->needs_generic_substitutions ())
+    if (!reciever_is_generic)
       {
-	lookup = SubstMapper::InferSubst (lookup,
-					  expr.get_method_name ().get_locus ());
+	// apply any remaining generic arguments
+	if (expr.get_method_name ().has_generic_args ())
+	  {
+	    HIR::GenericArgs &args
+	      = expr.get_method_name ().get_generic_args ();
+	    lookup = SubstMapper::Resolve (lookup,
+					   expr.get_method_name ().get_locus (),
+					   &args);
+	    if (lookup->get_kind () == TyTy::TypeKind::ERROR)
+	      return;
+	  }
+	else if (lookup->needs_generic_substitutions ())
+	  {
+	    lookup
+	      = SubstMapper::InferSubst (lookup,
+					 expr.get_method_name ().get_locus ());
+	  }
       }
 
     TyTy::BaseType *function_ret_tyty
@@ -333,9 +353,8 @@ public:
     context->insert_type (expr.get_method_name ().get_mappings (), lookup);
 
     // set up the resolved name on the path
-    resolver->insert_resolved_name (
-      expr.get_mappings ().get_nodeid (),
-      resolved_method->get_impl_mappings ().get_nodeid ());
+    resolver->insert_resolved_name (expr.get_mappings ().get_nodeid (),
+				    resolved_node_id);
 
     // return the result of the function back
     infered = function_ret_tyty;
@@ -429,7 +448,7 @@ public:
     if (!mappings->lookup_node_to_hir (expr.get_mappings ().get_crate_num (),
 				       ref_node_id, &ref))
       {
-	rust_error_at (expr.get_locus (), "reverse lookup failure");
+	rust_error_at (expr.get_locus (), "123 reverse lookup failure");
 	return;
       }
 
@@ -937,8 +956,16 @@ public:
       {
 	HIR::PathExprSegment &seg = expr.get_segments ().at (i);
 
+	bool reciever_is_generic
+	  = prev_segment->get_kind () == TyTy::TypeKind::PARAM;
+	bool probe_bounds = true;
+	bool probe_impls = !reciever_is_generic;
+	bool ignore_mandatory_trait_items = !reciever_is_generic;
+
 	// probe the path
-	auto candidates = PathProbeType::Probe (tyseg, seg.get_segment ());
+	auto candidates
+	  = PathProbeType::Probe (tyseg, seg.get_segment (), probe_impls,
+				  probe_bounds, ignore_mandatory_trait_items);
 	if (candidates.size () == 0)
 	  {
 	    rust_error_at (
@@ -954,11 +981,21 @@ public:
 	    return;
 	  }
 
-	auto candidate = candidates.at (0);
+	auto &candidate = candidates.at (0);
 	prev_segment = tyseg;
 	tyseg = candidate.ty;
-	resolved_node_id
-	  = candidate.impl_item->get_impl_mappings ().get_nodeid ();
+
+	if (candidate.is_impl_candidate ())
+	  {
+	    resolved_node_id
+	      = candidate.item.impl.impl_item->get_impl_mappings ()
+		  .get_nodeid ();
+	  }
+	else
+	  {
+	    resolved_node_id
+	      = candidate.item.trait.item_ref.get_mappings ().get_nodeid ();
+	  }
 
 	if (seg.has_generic_args ())
 	  {
@@ -977,6 +1014,7 @@ public:
 	  }
       }
 
+    context->insert_receiver (expr.get_mappings ().get_hirid (), prev_segment);
     if (tyseg->needs_generic_substitutions ())
       {
 	Location locus = expr.get_segments ().back ().get_locus ();
@@ -984,8 +1022,9 @@ public:
 	  {
 	    auto used_args_in_prev_segment
 	      = GetUsedSubstArgs::From (prev_segment);
-	    tyseg
-	      = SubstMapperInternal::Resolve (tyseg, used_args_in_prev_segment);
+	    if (!used_args_in_prev_segment.is_error ())
+	      tyseg = SubstMapperInternal::Resolve (tyseg,
+						    used_args_in_prev_segment);
 	  }
 	else
 	  {
@@ -1214,7 +1253,13 @@ private:
 	  {
 	    if (is_root)
 	      {
-		rust_error_at (seg.get_locus (), "reverse lookup failure");
+		rust_error_at (seg.get_locus (), "456 reverse lookup failure");
+		rust_debug_loc (
+		  seg.get_locus (),
+		  "failure with [%s] mappings [%s] ref_node_id [%u]",
+		  seg.as_string ().c_str (),
+		  seg.get_mappings ().as_string ().c_str (), ref_node_id);
+
 		return new TyTy::ErrorType (expr.get_mappings ().get_hirid ());
 	      }
 	    return root_tyty;
diff --git a/gcc/rust/typecheck/rust-hir-type-check-type.h b/gcc/rust/typecheck/rust-hir-type-check-type.h
index 0f75c54..91d9c53 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-type.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-type.h
@@ -215,7 +215,7 @@ private:
   {}
 
   void
-  check_for_unconstrained (std::vector<std::unique_ptr<HIR::Type> > &type_args)
+  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;
@@ -270,8 +270,31 @@ public:
     if (param.has_type ())
       TypeCheckType::Resolve (param.get_type ().get ());
 
+    std::vector<TyTy::TypeBoundPredicate> specified_bounds;
+    if (param.has_type_param_bounds ())
+      {
+	for (auto &bound : param.get_type_param_bounds ())
+	  {
+	    switch (bound->get_bound_type ())
+	      {
+		case HIR::TypeParamBound::BoundType::TRAITBOUND: {
+		  HIR::TraitBound *b
+		    = static_cast<HIR::TraitBound *> (bound.get ());
+		  TyTy::TypeBoundPredicate predicate (
+		    &resolve_trait_path (b->get_path ()));
+		  specified_bounds.push_back (std::move (predicate));
+		}
+		break;
+
+	      default:
+		break;
+	      }
+	  }
+      }
+
     resolved = new TyTy::ParamType (param.get_type_representation (),
-				    param.get_mappings ().get_hirid (), param);
+				    param.get_mappings ().get_hirid (), param,
+				    specified_bounds);
   }
 
 private:
diff --git a/gcc/rust/typecheck/rust-hir-type-check.cc b/gcc/rust/typecheck/rust-hir-type-check.cc
index 66adfcb..4b66fdb 100644
--- a/gcc/rust/typecheck/rust-hir-type-check.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check.cc
@@ -418,6 +418,7 @@ TraitItemReference::TraitItemReference (TraitItemReference const &other)
     type (other.type), hir_trait_item (other.hir_trait_item),
     locus (other.locus), self (other.self), context (TypeCheckContext::get ())
 {
+  inherited_substitutions.clear ();
   inherited_substitutions.reserve (other.inherited_substitutions.size ());
   for (size_t i = 0; i < other.inherited_substitutions.size (); i++)
     inherited_substitutions.push_back (other.inherited_substitutions.at (i));
diff --git a/gcc/rust/typecheck/rust-hir-type-check.h b/gcc/rust/typecheck/rust-hir-type-check.h
index 0298068..b171123 100644
--- a/gcc/rust/typecheck/rust-hir-type-check.h
+++ b/gcc/rust/typecheck/rust-hir-type-check.h
@@ -102,6 +102,21 @@ public:
     return true;
   }
 
+  void insert_receiver (HirId id, TyTy::BaseType *t)
+  {
+    receiver_context[id] = t;
+  }
+
+  bool lookup_receiver (HirId id, TyTy::BaseType **ref)
+  {
+    auto it = receiver_context.find (id);
+    if (it == receiver_context.end ())
+      return false;
+
+    *ref = it->second;
+    return true;
+  }
+
 private:
   TypeCheckContext ();
 
@@ -111,6 +126,7 @@ private:
   std::vector<TyTy::BaseType *> return_type_stack;
   std::vector<TyTy::BaseType *> loop_type_stack;
   std::map<DefId, TraitReference> trait_context;
+  std::map<HirId, TyTy::BaseType *> receiver_context;
 };
 
 class TypeResolution
diff --git a/gcc/rust/typecheck/rust-substitution-mapper.h b/gcc/rust/typecheck/rust-substitution-mapper.h
index 3730faa..a3c00da 100644
--- a/gcc/rust/typecheck/rust-substitution-mapper.h
+++ b/gcc/rust/typecheck/rust-substitution-mapper.h
@@ -280,24 +280,24 @@ public:
     args = type.get_substitution_arguments ();
   }
 
-  void visit (TyTy::InferType &) override { gcc_unreachable (); }
-  void visit (TyTy::TupleType &) override { gcc_unreachable (); }
-  void visit (TyTy::FnPtr &) override { gcc_unreachable (); }
-  void visit (TyTy::ArrayType &) override { gcc_unreachable (); }
-  void visit (TyTy::BoolType &) override { gcc_unreachable (); }
-  void visit (TyTy::IntType &) override { gcc_unreachable (); }
-  void visit (TyTy::UintType &) override { gcc_unreachable (); }
-  void visit (TyTy::FloatType &) override { gcc_unreachable (); }
-  void visit (TyTy::USizeType &) override { gcc_unreachable (); }
-  void visit (TyTy::ISizeType &) override { gcc_unreachable (); }
-  void visit (TyTy::ErrorType &) override { gcc_unreachable (); }
-  void visit (TyTy::CharType &) override { gcc_unreachable (); }
-  void visit (TyTy::ReferenceType &) override { gcc_unreachable (); }
-  void visit (TyTy::PointerType &) override { gcc_unreachable (); }
-  void visit (TyTy::ParamType &) override { gcc_unreachable (); }
-  void visit (TyTy::StrType &) override { gcc_unreachable (); }
-  void visit (TyTy::NeverType &) override { gcc_unreachable (); }
-  void visit (TyTy::PlaceholderType &) override { gcc_unreachable (); }
+  void visit (TyTy::InferType &) override {}
+  void visit (TyTy::TupleType &) override {}
+  void visit (TyTy::FnPtr &) override {}
+  void visit (TyTy::ArrayType &) override {}
+  void visit (TyTy::BoolType &) override {}
+  void visit (TyTy::IntType &) override {}
+  void visit (TyTy::UintType &) override {}
+  void visit (TyTy::FloatType &) override {}
+  void visit (TyTy::USizeType &) override {}
+  void visit (TyTy::ISizeType &) override {}
+  void visit (TyTy::ErrorType &) override {}
+  void visit (TyTy::CharType &) override {}
+  void visit (TyTy::ReferenceType &) override {}
+  void visit (TyTy::PointerType &) override {}
+  void visit (TyTy::ParamType &) override {}
+  void visit (TyTy::StrType &) override {}
+  void visit (TyTy::NeverType &) override {}
+  void visit (TyTy::PlaceholderType &) override {}
 
 private:
   GetUsedSubstArgs () : args (TyTy::SubstitutionArgumentMappings::error ()) {}
diff --git a/gcc/rust/typecheck/rust-tyty-bounds.cc b/gcc/rust/typecheck/rust-tyty-bounds.cc
new file mode 100644
index 0000000..a480155
--- /dev/null
+++ b/gcc/rust/typecheck/rust-tyty-bounds.cc
@@ -0,0 +1,75 @@
+// Copyright (C) 2021 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-bounds.h"
+#include "rust-hir-trait-resolve.h"
+
+namespace Rust {
+namespace Resolver {
+
+void
+TypeBoundsProbe::scan ()
+{
+  std::vector<HIR::TypePath *> possible_trait_paths;
+  mappings->iterate_impl_blocks (
+    [&] (HirId id, HIR::ImplBlock *impl) mutable -> bool {
+      // we are filtering for trait-impl-blocks
+      if (!impl->has_trait_ref ())
+	return true;
+
+      TyTy::BaseType *impl_type = nullptr;
+      bool ok
+	= context->lookup_type (impl->get_type ()->get_mappings ().get_hirid (),
+				&impl_type);
+      if (!ok)
+	return true;
+
+      if (!receiver->can_eq (impl_type, false))
+	return true;
+
+      possible_trait_paths.push_back (impl->get_trait_ref ().get ());
+      return true;
+    });
+
+  for (auto &trait_path : possible_trait_paths)
+    {
+      TraitReference &trait_ref = TraitResolver::Resolve (*trait_path);
+
+      if (!trait_ref.is_error ())
+	trait_references.push_back (trait_ref);
+    }
+}
+
+TraitReference &
+TypeCheckBase::resolve_trait_path (HIR::TypePath &path)
+{
+  return TraitResolver::Resolve (path);
+}
+
+} // namespace Resolver
+
+namespace TyTy {
+
+std::string
+TypeBoundPredicate::as_string () const
+{
+  return reference->as_string ();
+}
+
+} // namespace TyTy
+} // namespace Rust
diff --git a/gcc/rust/typecheck/rust-tyty.cc b/gcc/rust/typecheck/rust-tyty.cc
index 6bac764..a2ae4fa 100644
--- a/gcc/rust/typecheck/rust-tyty.cc
+++ b/gcc/rust/typecheck/rust-tyty.cc
@@ -127,7 +127,7 @@ InferType::cast (BaseType *other)
 }
 
 BaseType *
-InferType::clone ()
+InferType::clone () const
 {
   return new InferType (get_ref (), get_ty_ref (), get_infer_kind (),
 			get_combined_refs ());
@@ -201,7 +201,7 @@ ErrorType::cast (BaseType *other)
 }
 
 BaseType *
-ErrorType::clone ()
+ErrorType::clone () const
 {
   return new ErrorType (get_ref (), get_ty_ref (), get_combined_refs ());
 }
@@ -243,6 +243,7 @@ SubstitutionParamMapping::override_context ()
 
   auto mappings = Analysis::Mappings::get ();
   auto context = Resolver::TypeCheckContext::get ();
+
   context->insert_type (Analysis::NodeMapping (mappings->get_current_crate (),
 					       UNKNOWN_NODEID,
 					       param->get_ref (),
@@ -531,7 +532,7 @@ ADTType::is_equal (const BaseType &other) const
 }
 
 BaseType *
-ADTType::clone ()
+ADTType::clone () const
 {
   std::vector<StructFieldType *> cloned_fields;
   for (auto &f : fields)
@@ -687,7 +688,7 @@ TupleType::is_equal (const BaseType &other) const
 }
 
 BaseType *
-TupleType::clone ()
+TupleType::clone () const
 {
   return new TupleType (get_ref (), get_ty_ref (), fields,
 			get_combined_refs ());
@@ -808,7 +809,7 @@ FnType::is_equal (const BaseType &other) const
 }
 
 BaseType *
-FnType::clone ()
+FnType::clone () const
 {
   std::vector<std::pair<HIR::Pattern *, BaseType *> > cloned_params;
   for (auto &p : params)
@@ -1011,7 +1012,7 @@ FnPtr::is_equal (const BaseType &other) const
 }
 
 BaseType *
-FnPtr::clone ()
+FnPtr::clone () const
 {
   std::vector<TyVar> cloned_params;
   for (auto &p : params)
@@ -1097,7 +1098,7 @@ ArrayType::get_element_type () const
 }
 
 BaseType *
-ArrayType::clone ()
+ArrayType::clone () const
 {
   return new ArrayType (get_ref (), get_ty_ref (), get_capacity (),
 			element_type, get_combined_refs ());
@@ -1150,7 +1151,7 @@ BoolType::can_eq (const BaseType *other, bool emit_errors) const
 }
 
 BaseType *
-BoolType::clone ()
+BoolType::clone () const
 {
   return new BoolType (get_ref (), get_ty_ref (), get_combined_refs ());
 }
@@ -1216,7 +1217,7 @@ IntType::can_eq (const BaseType *other, bool emit_errors) const
 }
 
 BaseType *
-IntType::clone ()
+IntType::clone () const
 {
   return new IntType (get_ref (), get_ty_ref (), get_int_kind (),
 		      get_combined_refs ());
@@ -1293,7 +1294,7 @@ UintType::can_eq (const BaseType *other, bool emit_errors) const
 }
 
 BaseType *
-UintType::clone ()
+UintType::clone () const
 {
   return new UintType (get_ref (), get_ty_ref (), get_uint_kind (),
 		       get_combined_refs ());
@@ -1364,7 +1365,7 @@ FloatType::can_eq (const BaseType *other, bool emit_errors) const
 }
 
 BaseType *
-FloatType::clone ()
+FloatType::clone () const
 {
   return new FloatType (get_ref (), get_ty_ref (), get_float_kind (),
 			get_combined_refs ());
@@ -1427,7 +1428,7 @@ USizeType::can_eq (const BaseType *other, bool emit_errors) const
 }
 
 BaseType *
-USizeType::clone ()
+USizeType::clone () const
 {
   return new USizeType (get_ref (), get_ty_ref (), get_combined_refs ());
 }
@@ -1479,7 +1480,7 @@ ISizeType::can_eq (const BaseType *other, bool emit_errors) const
 }
 
 BaseType *
-ISizeType::clone ()
+ISizeType::clone () const
 {
   return new ISizeType (get_ref (), get_ty_ref (), get_combined_refs ());
 }
@@ -1531,7 +1532,7 @@ CharType::can_eq (const BaseType *other, bool emit_errors) const
 }
 
 BaseType *
-CharType::clone ()
+CharType::clone () const
 {
   return new CharType (get_ref (), get_ty_ref (), get_combined_refs ());
 }
@@ -1600,7 +1601,7 @@ ReferenceType::get_base () const
 }
 
 BaseType *
-ReferenceType::clone ()
+ReferenceType::clone () const
 {
   return new ReferenceType (get_ref (), get_ty_ref (), base, is_mutable (),
 			    get_combined_refs ());
@@ -1686,7 +1687,7 @@ PointerType::get_base () const
 }
 
 BaseType *
-PointerType::clone ()
+PointerType::clone () const
 {
   return new PointerType (get_ref (), get_ty_ref (), base, is_mutable (),
 			  get_combined_refs ());
@@ -1765,10 +1766,10 @@ ParamType::can_eq (const BaseType *other, bool emit_errors) const
 }
 
 BaseType *
-ParamType::clone ()
+ParamType::clone () const
 {
-  return new ParamType (get_symbol (), get_ref (), get_ty_ref (),
-			get_generic_param (), get_combined_refs ());
+  return new ParamType (get_symbol (), get_ref (), get_ty_ref (), param,
+			get_specified_bounds (), get_combined_refs ());
 }
 
 std::string
@@ -1780,8 +1781,6 @@ ParamType::get_symbol () const
 BaseType *
 ParamType::resolve () const
 {
-  rust_assert (can_resolve ());
-
   TyVar var (get_ty_ref ());
   BaseType *r = var.get_tyty ();
 
@@ -1795,7 +1794,10 @@ ParamType::resolve () const
       r = v.get_tyty ();
     }
 
-  return TyVar (r->get_ty_ref ()).get_tyty ();
+  if (r->get_kind () == TypeKind::PARAM && (r->get_ref () == r->get_ty_ref ()))
+    return TyVar (r->get_ty_ref ()).get_tyty ();
+
+  return r;
 }
 
 bool
@@ -1833,7 +1835,7 @@ ParamType::handle_substitions (SubstitutionArgumentMappings mappings)
 }
 
 BaseType *
-StrType::clone ()
+StrType::clone () const
 {
   return new StrType (get_ref (), get_ty_ref (), get_combined_refs ());
 }
@@ -1937,7 +1939,7 @@ NeverType::can_eq (const BaseType *other, bool emit_errors) const
 }
 
 BaseType *
-NeverType::clone ()
+NeverType::clone () const
 {
   return new NeverType (get_ref (), get_ty_ref (), get_combined_refs ());
 }
@@ -1989,7 +1991,7 @@ PlaceholderType::can_eq (const BaseType *other, bool emit_errors) const
 }
 
 BaseType *
-PlaceholderType::clone ()
+PlaceholderType::clone () const
 {
   return new PlaceholderType (get_ref (), get_ty_ref (), get_combined_refs ());
 }
diff --git a/gcc/rust/typecheck/rust-tyty.h b/gcc/rust/typecheck/rust-tyty.h
index 46110e4..13bab90 100644
--- a/gcc/rust/typecheck/rust-tyty.h
+++ b/gcc/rust/typecheck/rust-tyty.h
@@ -25,6 +25,10 @@
 #include "rust-diagnostics.h"
 
 namespace Rust {
+namespace Resolver {
+class TraitReference;
+}
+
 namespace TyTy {
 
 // https://rustc-dev-guide.rust-lang.org/type-inference.html#inference-variables
@@ -125,9 +129,56 @@ public:
   }
 };
 
+class TypeBoundPredicate
+{
+public:
+  TypeBoundPredicate (Resolver::TraitReference *reference)
+    : reference (reference)
+  {}
+
+  TypeBoundPredicate (const TypeBoundPredicate &other)
+    : reference (other.reference)
+  {}
+
+  TypeBoundPredicate &operator= (const TypeBoundPredicate &other)
+  {
+    reference = other.reference;
+    return *this;
+  }
+
+  std::string as_string () const;
+
+  const Resolver::TraitReference *get () const { return reference; }
+
+private:
+  Resolver::TraitReference *reference;
+};
+
+class TypeBoundsMappings
+{
+protected:
+  TypeBoundsMappings (std::vector<TypeBoundPredicate> specified_bounds)
+    : specified_bounds (specified_bounds)
+  {}
+
+public:
+  std::vector<TypeBoundPredicate> &get_specified_bounds ()
+  {
+    return specified_bounds;
+  }
+
+  const std::vector<TypeBoundPredicate> &get_specified_bounds () const
+  {
+    return specified_bounds;
+  }
+
+protected:
+  std::vector<TypeBoundPredicate> specified_bounds;
+};
+
 class TyVisitor;
 class TyConstVisitor;
-class BaseType
+class BaseType : public TypeBoundsMappings
 {
 public:
   virtual ~BaseType () {}
@@ -194,10 +245,10 @@ public:
 
   /* Returns a pointer to a clone of this. The caller is responsible for
    * releasing the memory of the returned ty. */
-  virtual BaseType *clone () = 0;
+  virtual BaseType *clone () const = 0;
 
   // get_combined_refs returns the chain of node refs involved in unification
-  std::set<HirId> get_combined_refs () { return combined; }
+  std::set<HirId> get_combined_refs () const { return combined; }
 
   void append_reference (HirId id) { combined.insert (id); }
 
@@ -240,8 +291,15 @@ public:
 protected:
   BaseType (HirId ref, HirId ty_ref, TypeKind kind,
 	    std::set<HirId> refs = std::set<HirId> ())
-    : kind (kind), ref (ref), ty_ref (ty_ref), combined (refs),
-      mappings (Analysis::Mappings::get ())
+    : TypeBoundsMappings ({}), kind (kind), ref (ref), ty_ref (ty_ref),
+      combined (refs), mappings (Analysis::Mappings::get ())
+  {}
+
+  BaseType (HirId ref, HirId ty_ref, TypeKind kind,
+	    std::vector<TypeBoundPredicate> specified_bounds,
+	    std::set<HirId> refs = std::set<HirId> ())
+    : TypeBoundsMappings (specified_bounds), kind (kind), ref (ref),
+      ty_ref (ty_ref), combined (refs), mappings (Analysis::Mappings::get ())
   {}
 
   TypeKind kind;
@@ -300,7 +358,7 @@ public:
   BaseType *coerce (BaseType *other) override;
   BaseType *cast (BaseType *other) override;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   InferTypeKind get_infer_kind () const { return infer_kind; }
 
@@ -337,7 +395,7 @@ public:
   BaseType *coerce (BaseType *other) override;
   BaseType *cast (BaseType *other) override;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   std::string get_name () const override final { return as_string (); }
 };
@@ -347,15 +405,18 @@ class ParamType : public BaseType
 {
 public:
   ParamType (std::string symbol, HirId ref, HIR::GenericParam &param,
+	     std::vector<TypeBoundPredicate> specified_bounds,
 	     std::set<HirId> refs = std::set<HirId> ())
-    : BaseType (ref, ref, TypeKind::PARAM, refs), symbol (symbol), param (param)
+    : BaseType (ref, ref, TypeKind::PARAM, specified_bounds, refs),
+      symbol (symbol), param (param)
   {}
 
   ParamType (std::string symbol, HirId ref, HirId ty_ref,
 	     HIR::GenericParam &param,
+	     std::vector<TypeBoundPredicate> specified_bounds,
 	     std::set<HirId> refs = std::set<HirId> ())
-    : BaseType (ref, ty_ref, TypeKind::PARAM, refs), symbol (symbol),
-      param (param)
+    : BaseType (ref, ty_ref, TypeKind::PARAM, specified_bounds, refs),
+      symbol (symbol), param (param)
   {}
 
   void accept_vis (TyVisitor &vis) override;
@@ -368,7 +429,7 @@ public:
   BaseType *coerce (BaseType *other) override;
   BaseType *cast (BaseType *other) override;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   std::string get_symbol () const;
 
@@ -462,7 +523,7 @@ public:
 
   BaseType *get_field (size_t index) const;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   bool is_concrete () const override final
   {
@@ -527,7 +588,7 @@ public:
       }
   }
 
-  SubstitutionParamMapping clone ()
+  SubstitutionParamMapping clone () const
   {
     return SubstitutionParamMapping (generic, static_cast<ParamType *> (
 						param->clone ()));
@@ -728,7 +789,7 @@ public:
     return substitutions;
   }
 
-  std::vector<SubstitutionParamMapping> clone_substs ()
+  std::vector<SubstitutionParamMapping> clone_substs () const
   {
     std::vector<SubstitutionParamMapping> clone;
 
@@ -885,9 +946,9 @@ public:
       identifier (identifier), fields (fields), adt_kind (adt_kind)
   {}
 
-  ADTKind get_adt_kind () { return adt_kind; }
-  bool is_tuple_struct () { return adt_kind == TUPLE_STRUCT; }
-  bool is_union () { return adt_kind == UNION; }
+  ADTKind get_adt_kind () const { return adt_kind; }
+  bool is_tuple_struct () const { return adt_kind == TUPLE_STRUCT; }
+  bool is_union () const { return adt_kind == UNION; }
 
   bool is_unit () const override { return this->fields.empty (); }
 
@@ -942,7 +1003,7 @@ public:
     return nullptr;
   }
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   std::vector<StructFieldType *> &get_fields () { return fields; }
   const std::vector<StructFieldType *> &get_fields () const { return fields; }
@@ -986,7 +1047,7 @@ public:
 #define FNTYPE_IS_VARADIC_FLAG 0X04
 
   FnType (HirId ref, DefId id, std::string identifier, uint8_t flags,
-	  std::vector<std::pair<HIR::Pattern *, BaseType *> > params,
+	  std::vector<std::pair<HIR::Pattern *, BaseType *>> params,
 	  BaseType *type, std::vector<SubstitutionParamMapping> subst_refs,
 	  std::set<HirId> refs = std::set<HirId> ())
     : BaseType (ref, ref, TypeKind::FNDEF, refs),
@@ -1001,7 +1062,7 @@ public:
 
   FnType (HirId ref, HirId ty_ref, DefId id, std::string identifier,
 	  uint8_t flags,
-	  std::vector<std::pair<HIR::Pattern *, BaseType *> > params,
+	  std::vector<std::pair<HIR::Pattern *, BaseType *>> params,
 	  BaseType *type, std::vector<SubstitutionParamMapping> subst_refs,
 	  std::set<HirId> refs = std::set<HirId> ())
     : BaseType (ref, ty_ref, TypeKind::FNDEF, refs),
@@ -1054,12 +1115,12 @@ public:
     return get_params ().at (0).second;
   }
 
-  std::vector<std::pair<HIR::Pattern *, BaseType *> > &get_params ()
+  std::vector<std::pair<HIR::Pattern *, BaseType *>> &get_params ()
   {
     return params;
   }
 
-  const std::vector<std::pair<HIR::Pattern *, BaseType *> > &get_params () const
+  const std::vector<std::pair<HIR::Pattern *, BaseType *>> &get_params () const
   {
     return params;
   }
@@ -1076,7 +1137,7 @@ public:
 
   BaseType *get_return_type () const { return type; }
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   bool needs_generic_substitutions () const override final
   {
@@ -1094,7 +1155,7 @@ public:
   handle_substitions (SubstitutionArgumentMappings mappings) override final;
 
 private:
-  std::vector<std::pair<HIR::Pattern *, BaseType *> > params;
+  std::vector<std::pair<HIR::Pattern *, BaseType *>> params;
   BaseType *type;
   uint8_t flags;
   std::string identifier;
@@ -1136,7 +1197,7 @@ public:
 
   bool is_equal (const BaseType &other) const override;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   void iterate_params (std::function<bool (BaseType *)> cb) const
   {
@@ -1186,7 +1247,7 @@ public:
 
   BaseType *get_element_type () const;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   bool is_concrete () const final override
   {
@@ -1221,7 +1282,7 @@ public:
   BaseType *coerce (BaseType *other) override;
   BaseType *cast (BaseType *other) override;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 };
 
 class IntType : public BaseType
@@ -1259,7 +1320,7 @@ public:
 
   IntKind get_int_kind () const { return int_kind; }
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   bool is_equal (const BaseType &other) const override;
 
@@ -1302,7 +1363,7 @@ public:
 
   UintKind get_uint_kind () const { return uint_kind; }
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   bool is_equal (const BaseType &other) const override;
 
@@ -1343,7 +1404,7 @@ public:
 
   FloatKind get_float_kind () const { return float_kind; }
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   bool is_equal (const BaseType &other) const override;
 
@@ -1374,7 +1435,7 @@ public:
   BaseType *coerce (BaseType *other) override;
   BaseType *cast (BaseType *other) override;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 };
 
 class ISizeType : public BaseType
@@ -1400,7 +1461,7 @@ public:
   BaseType *coerce (BaseType *other) override;
   BaseType *cast (BaseType *other) override;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 };
 
 class CharType : public BaseType
@@ -1426,7 +1487,7 @@ public:
   BaseType *coerce (BaseType *other) override;
   BaseType *cast (BaseType *other) override;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 };
 
 class ReferenceType : public BaseType
@@ -1458,7 +1519,7 @@ public:
 
   bool is_equal (const BaseType &other) const override;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   bool contains_type_parameters () const override final
   {
@@ -1504,7 +1565,7 @@ public:
 
   bool is_equal (const BaseType &other) const override;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   bool contains_type_parameters () const override final
   {
@@ -1547,7 +1608,7 @@ public:
 
   bool is_equal (const BaseType &other) const override;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 };
 
 // https://doc.rust-lang.org/std/primitive.never.html
@@ -1581,7 +1642,7 @@ public:
   BaseType *coerce (BaseType *other) override;
   BaseType *cast (BaseType *other) override;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   std::string get_name () const override final { return as_string (); }
 
@@ -1612,7 +1673,7 @@ public:
   BaseType *coerce (BaseType *other) override;
   BaseType *cast (BaseType *other) override;
 
-  BaseType *clone () final override;
+  BaseType *clone () const final override;
 
   std::string get_name () const override final { return as_string (); }
 
diff --git a/gcc/rust/util/rust-hir-map.cc b/gcc/rust/util/rust-hir-map.cc
index 69fbe25..4ffbff0 100644
--- a/gcc/rust/util/rust-hir-map.cc
+++ b/gcc/rust/util/rust-hir-map.cc
@@ -383,6 +383,56 @@ Mappings::lookup_hir_expr (CrateNum crateNum, HirId id)
 }
 
 void
+Mappings::insert_hir_path_expr_seg (CrateNum crateNum, HirId id,
+				    HIR::PathExprSegment *expr)
+{
+  rust_assert (lookup_hir_path_expr_seg (crateNum, id) == nullptr);
+
+  hirPathSegMappings[crateNum][id] = expr;
+  nodeIdToHirMappings[crateNum][expr->get_mappings ().get_nodeid ()] = id;
+  insert_location (crateNum, id, expr->get_locus ());
+}
+
+HIR::PathExprSegment *
+Mappings::lookup_hir_path_expr_seg (CrateNum crateNum, HirId id)
+{
+  auto it = hirPathSegMappings.find (crateNum);
+  if (it == hirPathSegMappings.end ())
+    return nullptr;
+
+  auto iy = it->second.find (id);
+  if (iy == it->second.end ())
+    return nullptr;
+
+  return iy->second;
+}
+
+void
+Mappings::insert_hir_generic_param (CrateNum crateNum, HirId id,
+				    HIR::GenericParam *param)
+{
+  rust_assert (lookup_hir_generic_param (crateNum, id) == nullptr);
+
+  hirGenericParamMappings[crateNum][id] = param;
+  nodeIdToHirMappings[crateNum][param->get_mappings ().get_nodeid ()] = id;
+  insert_location (crateNum, id, param->get_locus_slow ());
+}
+
+HIR::GenericParam *
+Mappings::lookup_hir_generic_param (CrateNum crateNum, HirId id)
+{
+  auto it = hirGenericParamMappings.find (crateNum);
+  if (it == hirGenericParamMappings.end ())
+    return nullptr;
+
+  auto iy = it->second.find (id);
+  if (iy == it->second.end ())
+    return nullptr;
+
+  return iy->second;
+}
+
+void
 Mappings::insert_hir_type (CrateNum crateNum, HirId id, HIR::Type *type)
 {
   rust_assert (lookup_hir_type (crateNum, id) == nullptr);
diff --git a/gcc/rust/util/rust-hir-map.h b/gcc/rust/util/rust-hir-map.h
index 7e5449c..ccc873b 100644
--- a/gcc/rust/util/rust-hir-map.h
+++ b/gcc/rust/util/rust-hir-map.h
@@ -148,6 +148,14 @@ public:
   void insert_hir_expr (CrateNum crateNum, HirId id, HIR::Expr *expr);
   HIR::Expr *lookup_hir_expr (CrateNum crateNum, HirId id);
 
+  void insert_hir_path_expr_seg (CrateNum crateNum, HirId id,
+				 HIR::PathExprSegment *expr);
+  HIR::PathExprSegment *lookup_hir_path_expr_seg (CrateNum crateNum, HirId id);
+
+  void insert_hir_generic_param (CrateNum crateNum, HirId id,
+				 HIR::GenericParam *expr);
+  HIR::GenericParam *lookup_hir_generic_param (CrateNum crateNum, HirId id);
+
   void insert_hir_type (CrateNum crateNum, HirId id, HIR::Type *type);
   HIR::Type *lookup_hir_type (CrateNum crateNum, HirId id);
 
@@ -215,6 +223,20 @@ public:
 	   != nullptr;
   }
 
+  void insert_trait_item_mapping (HirId trait_item_id, HIR::Trait *trait)
+  {
+    rust_assert (hirTraitItemsToTraitMappings.find (trait_item_id)
+		 == hirTraitItemsToTraitMappings.end ());
+    hirTraitItemsToTraitMappings[trait_item_id] = trait;
+  }
+
+  HIR::Trait *lookup_trait_item_mapping (HirId trait_item_id)
+  {
+    auto lookup = hirTraitItemsToTraitMappings.find (trait_item_id);
+    rust_assert (lookup != hirTraitItemsToTraitMappings.end ());
+    return lookup->second;
+  }
+
 private:
   Mappings ();
 
@@ -245,6 +267,11 @@ private:
   std::map<CrateNum, std::map<HirId, HIR::TraitItem *> > hirTraitItemMappings;
   std::map<CrateNum, std::map<HirId, HIR::ExternalItem *> >
     hirExternItemMappings;
+  std::map<CrateNum, std::map<HirId, HIR::PathExprSegment *> >
+    hirPathSegMappings;
+  std::map<CrateNum, std::map<HirId, HIR::GenericParam *> >
+    hirGenericParamMappings;
+  std::map<HirId, HIR::Trait *> hirTraitItemsToTraitMappings;
 
   // location info
   std::map<CrateNum, std::map<NodeId, Location> > locations;
diff --git a/gcc/testsuite/rust/compile/torture/traits8.rs b/gcc/testsuite/rust/compile/torture/traits8.rs
new file mode 100644
index 0000000..0e83a7d
--- /dev/null
+++ b/gcc/testsuite/rust/compile/torture/traits8.rs
@@ -0,0 +1,22 @@
+trait Foo {
+    fn default() -> i32;
+}
+
+struct Bar(i32);
+// { dg-warning "struct is never constructed" "" { target *-*-* } .-1 }
+
+impl Foo for Bar {
+    fn default() -> i32 {
+        // { dg-warning "unused name" "" { target *-*-* } .-1 }
+        123
+    }
+}
+
+fn type_bound_test<T: Foo>() -> i32 {
+    T::default()
+}
+
+fn main() {
+    let a;
+    a = type_bound_test::<Bar>();
+}
diff --git a/gcc/testsuite/rust/compile/torture/traits9.rs b/gcc/testsuite/rust/compile/torture/traits9.rs
new file mode 100644
index 0000000..075a219
--- /dev/null
+++ b/gcc/testsuite/rust/compile/torture/traits9.rs
@@ -0,0 +1,30 @@
+trait Foo {
+    fn default() -> i32;
+    fn get(self) -> i32;
+    // { dg-warning "unused name" "" { target *-*-* } .-1 }
+}
+
+struct Bar(i32);
+impl Foo for Bar {
+    fn default() -> i32 {
+        // { dg-warning "unused name" "" { target *-*-* } .-1 }
+        123
+    }
+
+    fn get(self) -> i32 {
+        // { dg-warning "unused name" "" { target *-*-* } .-1 }
+        self.0
+    }
+}
+
+fn type_bound_test<T: Foo>(a: T) -> i32 {
+    T::default() + a.get()
+}
+
+fn main() {
+    let a;
+    a = Bar(456);
+
+    let b;
+    b = type_bound_test(a);
+}