Support Generic Traits in qualified paths

This extends the ProjectionType which represents an implemented associated
type with its own substitution mappings. The problem is a TypePath to a
trait does not represent a single TyTy primitive type, the type system
handles generics in an interesting way. Take for instance the case of a
generic impl block:

  impl<T> Foo<T> {
    fn Bar<Y>(self, a:T, b:Y) {}
  }

The compiler treats an impl block as the parent so that all items inherit
from this, which is why rustc calls these inherent-impl-blocks. So
in order to handle generic arguments we need to "bind" them, and in rust
only some types actually support generic argument binding, at the moment
for gccrs it is, ADTTypes, FnTypes and Projections. Going back to the
example the TyTy for this function turns into:

  fn Bar<T,Y>(Foo<T>, T, Y)

So when it comes to the generic traits its a similar process but the
difference is that traits contain associated types, these must be able
to bind the generic arguments such that we can substitute any covariant
types fully. But there is a layer of complexity and indirection here
consider the following example:

  trait Foo<T> {
      type A;

      fn test(a: T, b: Self::A) -> (T, Self::A) {
          (a, b)
      }
  }

  struct Bar<T>(T);
  impl<T> Foo<T> for Bar<T> {
      type A = T;
  }

When we deal with a trait with an optional trait function that uses the
associated types what actually happens here is that the type A in this
trait context is considered just a simple PlaceHolder which gets
setup within relation to its relevant impl block, so when we setup the
associated types it turns into:

  Placeholder(A) ->
    Projection<T>(Bar<T> as Foo<T>) ->
      T

So it forms an recursive chain that must be substituted in relation to
what the paticular query is.

19 files changed, 375 insertions, 102 deletions

diff --git a/gcc/rust/backend/rust-compile-context.h b/gcc/rust/backend/rust-compile-context.h
index 66d037d..bffe97c 100644
--- a/gcc/rust/backend/rust-compile-context.h
+++ b/gcc/rust/backend/rust-compile-context.h
@@ -336,7 +336,10 @@ public:
 
   void visit (TyTy::InferType &) override { gcc_unreachable (); }
 
-  void visit (TyTy::ProjectionType &) override { gcc_unreachable (); }
+  void visit (TyTy::ProjectionType &type) override
+  {
+    type.get ()->accept_vis (*this);
+  }
 
   void visit (TyTy::PlaceholderType &type) override
   {
diff --git a/gcc/rust/typecheck/rust-hir-path-probe.h b/gcc/rust/typecheck/rust-hir-path-probe.h
index 60cd98a..dd51f83 100644
--- a/gcc/rust/typecheck/rust-hir-path-probe.h
+++ b/gcc/rust/typecheck/rust-hir-path-probe.h
@@ -276,6 +276,18 @@ protected:
 
 	TyTy::BaseType *trait_item_tyty = trait_item_ref->get_tyty ();
 
+	if (impl != nullptr)
+	  {
+	    HirId impl_block_id = impl->get_mappings ().get_hirid ();
+	    AssociatedImplTrait *lookup_associated = nullptr;
+	    bool found_impl_trait
+	      = context->lookup_associated_trait_impl (impl_block_id,
+						       &lookup_associated);
+	    // see testsuite/rust/compile/torture/traits10.rs this can be false
+	    if (found_impl_trait)
+	      lookup_associated->setup_associated_types ();
+	  }
+
 	// we can substitute the Self with the receiver here
 	if (trait_item_tyty->get_kind () == TyTy::TypeKind::FNDEF)
 	  {
diff --git a/gcc/rust/typecheck/rust-hir-trait-ref.h b/gcc/rust/typecheck/rust-hir-trait-ref.h
index c86892e..f05ff0c 100644
--- a/gcc/rust/typecheck/rust-hir-trait-ref.h
+++ b/gcc/rust/typecheck/rust-hir-trait-ref.h
@@ -47,26 +47,7 @@ public:
 
   TraitItemReference (TraitItemReference const &other);
 
-  TraitItemReference &operator= (TraitItemReference const &other)
-  {
-    identifier = other.identifier;
-    optional_flag = other.optional_flag;
-    type = other.type;
-    hir_trait_item = other.hir_trait_item;
-    self = other.self;
-    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));
-
-    return *this;
-  }
-
-  TraitItemReference (TraitItemReference &&other) = default;
-  TraitItemReference &operator= (TraitItemReference &&other) = default;
+  TraitItemReference &operator= (TraitItemReference const &other);
 
   static TraitItemReference error ()
   {
@@ -368,6 +349,7 @@ public:
 
   TyTy::BaseType *get_projected_type (const TraitItemReference *trait_item_ref,
 				      TyTy::BaseType *reciever, HirId ref,
+				      HIR::GenericArgs &trait_generics,
 				      Location expr_locus);
 
 private:
diff --git a/gcc/rust/typecheck/rust-hir-trait-resolve.cc b/gcc/rust/typecheck/rust-hir-trait-resolve.cc
index aeedf7e..be58840 100644
--- a/gcc/rust/typecheck/rust-hir-trait-resolve.cc
+++ b/gcc/rust/typecheck/rust-hir-trait-resolve.cc
@@ -58,7 +58,7 @@ ResolveTraitItemToRef::visit (HIR::TraitItemFunc &fn)
 
   resolved = TraitItemReference (identifier, is_optional,
 				 TraitItemReference::TraitItemType::FN, &fn,
-				 self, substitutions, locus);
+				 self, std::move (substitutions), locus);
 }
 
 // TraitItemReference items
@@ -196,7 +196,7 @@ TraitItemReference::get_parent_trait_mappings () const
 TyTy::BaseType *
 AssociatedImplTrait::get_projected_type (
   const TraitItemReference *trait_item_ref, TyTy::BaseType *receiver, HirId ref,
-  Location expr_locus)
+  HIR::GenericArgs &trait_generics, Location expr_locus)
 {
   TyTy::BaseType *trait_item_tyty = trait_item_ref->get_tyty ()->clone ();
 
@@ -219,11 +219,17 @@ AssociatedImplTrait::get_projected_type (
       std::vector<TyTy::SubstitutionArg> mappings;
       mappings.push_back (TyTy::SubstitutionArg (param, receiver->clone ()));
 
-      Location locus; // FIXME
-      TyTy::SubstitutionArgumentMappings args (std::move (mappings), locus);
+      TyTy::SubstitutionArgumentMappings args (std::move (mappings),
+					       expr_locus);
       trait_item_tyty = SubstMapperInternal::Resolve (trait_item_tyty, args);
     }
 
+  if (!trait_generics.is_empty ())
+    {
+      trait_item_tyty
+	= SubstMapper::Resolve (trait_item_tyty, expr_locus, &trait_generics);
+    }
+
   return trait_item_tyty;
 }
 
diff --git a/gcc/rust/typecheck/rust-hir-trait-resolve.h b/gcc/rust/typecheck/rust-hir-trait-resolve.h
index 0fe2406..365994f 100644
--- a/gcc/rust/typecheck/rust-hir-trait-resolve.h
+++ b/gcc/rust/typecheck/rust-hir-trait-resolve.h
@@ -37,9 +37,9 @@ public:
   Resolve (HIR::TraitItem &item, TyTy::BaseType *self,
 	   std::vector<TyTy::SubstitutionParamMapping> substitutions)
   {
-    ResolveTraitItemToRef resolver (self, substitutions);
+    ResolveTraitItemToRef resolver (self, std::move (substitutions));
     item.accept_vis (resolver);
-    return resolver.resolved;
+    return std::move (resolver.resolved);
   }
 
   void visit (HIR::TraitItemType &type) override;
@@ -51,9 +51,9 @@ public:
 private:
   ResolveTraitItemToRef (
     TyTy::BaseType *self,
-    std::vector<TyTy::SubstitutionParamMapping> substitutions)
+    std::vector<TyTy::SubstitutionParamMapping> &&substitutions)
     : TypeCheckBase (), resolved (TraitItemReference::error ()), self (self),
-      substitutions (substitutions)
+      substitutions (std::move (substitutions))
   {}
 
   TraitItemReference resolved;
@@ -146,8 +146,14 @@ private:
     std::vector<TraitItemReference> item_refs;
     for (auto &item : trait_reference->get_trait_items ())
       {
+	// make a copy of the substs
+	std::vector<TyTy::SubstitutionParamMapping> item_subst;
+	for (auto &sub : substitutions)
+	  item_subst.push_back (sub.clone ());
+
 	TraitItemReference trait_item_ref
-	  = ResolveTraitItemToRef::Resolve (*item.get (), self, substitutions);
+	  = ResolveTraitItemToRef::Resolve (*item.get (), self,
+					    std::move (item_subst));
 	item_refs.push_back (std::move (trait_item_ref));
       }
 
diff --git a/gcc/rust/typecheck/rust-hir-type-check-implitem.h b/gcc/rust/typecheck/rust-hir-type-check-implitem.h
index 3d83523..59ea4ef 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-implitem.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-implitem.h
@@ -303,11 +303,12 @@ class TypeCheckImplItemWithTrait : public TypeCheckImplItem
   using Rust::Resolver::TypeCheckBase::visit;
 
 public:
-  static const TraitItemReference &Resolve (HIR::ImplItem *item,
-					    TyTy::BaseType *self,
-					    TraitReference &trait_reference)
+  static const TraitItemReference &
+  Resolve (HIR::ImplItem *item, TyTy::BaseType *self,
+	   TraitReference &trait_reference,
+	   std::vector<TyTy::SubstitutionParamMapping> substitutions)
   {
-    TypeCheckImplItemWithTrait resolver (self, trait_reference);
+    TypeCheckImplItemWithTrait resolver (self, trait_reference, substitutions);
     item->accept_vis (resolver);
     return resolver.resolved_trait_item;
   }
@@ -383,7 +384,17 @@ public:
 	  trait_reference.get_name ().c_str ());
       }
 
-    resolved_trait_item.associated_type_set (lookup);
+    rust_debug_loc (type.get_locus (), "type-alias within impl block");
+    lookup->debug ();
+
+    // its actually a projection, since we need a way to actually bind the
+    // generic substitutions to the type itself
+    TyTy::ProjectionType *projection = new TyTy::ProjectionType (
+      type.get_mappings ().get_hirid (), lookup, &trait_reference,
+      resolved_trait_item.get_mappings ().get_defid (), substitutions);
+
+    context->insert_type (type.get_mappings (), projection);
+    resolved_trait_item.associated_type_set (projection);
   }
 
   void visit (HIR::Function &function) override
@@ -452,10 +463,12 @@ public:
   }
 
 private:
-  TypeCheckImplItemWithTrait (TyTy::BaseType *self,
-			      TraitReference &trait_reference)
+  TypeCheckImplItemWithTrait (
+    TyTy::BaseType *self, TraitReference &trait_reference,
+    std::vector<TyTy::SubstitutionParamMapping> substitutions)
     : TypeCheckImplItem (self), trait_reference (trait_reference),
-      resolved_trait_item (TraitItemReference::error_node ())
+      resolved_trait_item (TraitItemReference::error_node ()),
+      substitutions (substitutions)
   {
     rust_assert (is_trait_impl_block ());
   }
@@ -464,6 +477,7 @@ private:
 
   TraitReference &trait_reference;
   TraitItemReference &resolved_trait_item;
+  std::vector<TyTy::SubstitutionParamMapping> substitutions;
 };
 
 } // namespace Resolver
diff --git a/gcc/rust/typecheck/rust-hir-type-check-item.h b/gcc/rust/typecheck/rust-hir-type-check-item.h
index ab32f57..476a961 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-item.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-item.h
@@ -43,6 +43,33 @@ public:
 
   void visit (HIR::ImplBlock &impl_block) override
   {
+    std::vector<TyTy::SubstitutionParamMapping> substitutions;
+    if (impl_block.has_generics ())
+      {
+	for (auto &generic_param : impl_block.get_generic_params ())
+	  {
+	    switch (generic_param.get ()->get_kind ())
+	      {
+	      case HIR::GenericParam::GenericKind::LIFETIME:
+		// Skipping Lifetime completely until better handling.
+		break;
+
+		case HIR::GenericParam::GenericKind::TYPE: {
+		  TyTy::BaseType *l = nullptr;
+		  bool ok = context->lookup_type (
+		    generic_param->get_mappings ().get_hirid (), &l);
+		  if (ok && l->get_kind () == TyTy::TypeKind::PARAM)
+		    {
+		      substitutions.push_back (TyTy::SubstitutionParamMapping (
+			static_cast<HIR::TypeParam &> (*generic_param),
+			static_cast<TyTy::ParamType *> (l)));
+		    }
+		}
+		break;
+	      }
+	  }
+      }
+
     TraitReference *trait_reference = &TraitReference::error_node ();
     if (impl_block.has_trait_ref ())
       {
@@ -72,7 +99,8 @@ public:
 	  {
 	    auto &trait_item_ref
 	      = TypeCheckImplItemWithTrait::Resolve (impl_item.get (), self,
-						     *trait_reference);
+						     *trait_reference,
+						     substitutions);
 	    trait_item_refs.push_back (trait_item_ref);
 	  }
       }
diff --git a/gcc/rust/typecheck/rust-hir-type-check-path.cc b/gcc/rust/typecheck/rust-hir-type-check-path.cc
index 7b0e8ae..8b53e44 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-path.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check-path.cc
@@ -74,7 +74,6 @@ TypeCheckExpr::visit (HIR::QualifiedPathInExpression &expr)
     = context->lookup_associated_trait_impl (impl_block_id, &lookup_associated);
   rust_assert (found_impl_trait);
 
-  DefId resolved_item_id = UNKNOWN_DEFID;
   HIR::PathExprSegment &item_seg = expr.get_segments ().at (0);
 
   const TraitItemReference *trait_item_ref = nullptr;
@@ -85,10 +84,14 @@ TypeCheckExpr::visit (HIR::QualifiedPathInExpression &expr)
       rust_error_at (item_seg.get_locus (), "unknown associated item");
       return;
     }
-  resolved_item_id = trait_item_ref->get_mappings ().get_defid ();
 
+  HIR::GenericArgs trait_generics = qual_path_type.trait_has_generic_args ()
+				      ? qual_path_type.get_trait_generic_args ()
+				      : HIR::GenericArgs::create_empty ();
+
+  lookup_associated->setup_associated_types ();
   infered = lookup_associated->get_projected_type (
-    trait_item_ref, root, item_seg.get_mappings ().get_hirid (),
+    trait_item_ref, root, item_seg.get_mappings ().get_hirid (), trait_generics,
     item_seg.get_locus ());
 
   // turbo-fish segment path::<ty>
@@ -106,12 +109,6 @@ TypeCheckExpr::visit (HIR::QualifiedPathInExpression &expr)
 				      &item_seg.get_generic_args ());
     }
 
-  TyTy::ProjectionType *projection
-    = new TyTy::ProjectionType (qual_path_type.get_mappings ().get_hirid (),
-				TyTy::TyVar (root->get_ref ()), trait_ref,
-				resolved_item_id, lookup_associated);
-  context->insert_type (qual_path_type.get_mappings (), projection);
-
   // continue on as a path-in-expression
   NodeId root_resolved_node_id = trait_item_ref->get_mappings ().get_nodeid ();
   bool fully_resolved = expr.get_segments ().size () <= 1;
@@ -340,6 +337,7 @@ TypeCheckExpr::resolve_segments (NodeId root_resolved_node_id,
 	  candidates
 	    = PathProbeType::Probe (prev_segment, seg.get_segment (), false,
 				    probe_bounds, ignore_mandatory_trait_items);
+
 	  if (candidates.size () == 0)
 	    {
 	      rust_error_at (
diff --git a/gcc/rust/typecheck/rust-hir-type-check-type.cc b/gcc/rust/typecheck/rust-hir-type-check-type.cc
index dd03499..b54a403 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-type.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check-type.cc
@@ -139,7 +139,6 @@ TypeCheckType::visit (HIR::QualifiedPathInType &path)
     = context->lookup_associated_trait_impl (impl_block_id, &lookup_associated);
   rust_assert (found_impl_trait);
 
-  DefId resolved_item_id = UNKNOWN_DEFID;
   std::unique_ptr<HIR::TypePathSegment> &item_seg
     = path.get_associated_segment ();
 
@@ -152,14 +151,17 @@ TypeCheckType::visit (HIR::QualifiedPathInType &path)
       rust_error_at (item_seg->get_locus (), "unknown associated item");
       return;
     }
-  resolved_item_id = trait_item_ref->get_mappings ().get_defid ();
 
   // project
   lookup_associated->setup_associated_types ();
 
+  HIR::GenericArgs trait_generics = qual_path_type.trait_has_generic_args ()
+				      ? qual_path_type.get_trait_generic_args ()
+				      : HIR::GenericArgs::create_empty ();
+
   translated = lookup_associated->get_projected_type (
     trait_item_ref, root, item_seg->get_mappings ().get_hirid (),
-    item_seg->get_locus ());
+    trait_generics, item_seg->get_locus ());
 
   if (translated->get_kind () == TyTy::TypeKind::PLACEHOLDER)
     {
@@ -194,12 +196,6 @@ TypeCheckType::visit (HIR::QualifiedPathInType &path)
 	}
     }
 
-  TyTy::ProjectionType *projection
-    = new TyTy::ProjectionType (qual_path_type.get_mappings ().get_hirid (),
-				TyTy::TyVar (root->get_ref ()), trait_ref,
-				resolved_item_id, lookup_associated);
-  context->insert_type (qual_path_type.get_mappings (), projection);
-
   // continue on as a path-in-expression
   NodeId root_resolved_node_id = trait_item_ref->get_mappings ().get_nodeid ();
   bool fully_resolved = path.get_segments ().empty ();
diff --git a/gcc/rust/typecheck/rust-hir-type-check.cc b/gcc/rust/typecheck/rust-hir-type-check.cc
index 7f0e0ff..453f743 100644
--- a/gcc/rust/typecheck/rust-hir-type-check.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check.cc
@@ -408,8 +408,9 @@ TraitItemReference::TraitItemReference (
   HIR::TraitItem *hir_trait_item, TyTy::BaseType *self,
   std::vector<TyTy::SubstitutionParamMapping> substitutions, Location locus)
   : identifier (identifier), optional_flag (optional), type (type),
-    hir_trait_item (hir_trait_item), inherited_substitutions (substitutions),
-    locus (locus), self (self), context (TypeCheckContext::get ())
+    hir_trait_item (hir_trait_item),
+    inherited_substitutions (std::move (substitutions)), locus (locus),
+    self (self), context (TypeCheckContext::get ())
 {}
 
 TraitItemReference::TraitItemReference (TraitItemReference const &other)
@@ -420,7 +421,28 @@ TraitItemReference::TraitItemReference (TraitItemReference const &other)
   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));
+    inherited_substitutions.push_back (
+      other.inherited_substitutions.at (i).clone ());
+}
+
+TraitItemReference &
+TraitItemReference::operator= (TraitItemReference const &other)
+{
+  identifier = other.identifier;
+  optional_flag = other.optional_flag;
+  type = other.type;
+  hir_trait_item = other.hir_trait_item;
+  self = other.self;
+  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).clone ());
+
+  return *this;
 }
 
 TyTy::BaseType *
@@ -524,10 +546,13 @@ TraitItemReference::get_type_from_fn (/*const*/ HIR::TraitItemFunc &fn) const
       context->insert_type (param.get_mappings (), param_tyty);
     }
 
-  return new TyTy::FnType (fn.get_mappings ().get_hirid (),
-			   fn.get_mappings ().get_defid (),
-			   function.get_function_name (), function.is_method (),
-			   std::move (params), ret_type, substitutions);
+  auto resolved
+    = new TyTy::FnType (fn.get_mappings ().get_hirid (),
+			fn.get_mappings ().get_defid (),
+			function.get_function_name (), function.is_method (),
+			std::move (params), ret_type, substitutions);
+  context->insert_type (fn.get_mappings (), resolved);
+  return resolved;
 }
 
 } // namespace Resolver
diff --git a/gcc/rust/typecheck/rust-hir-type-check.h b/gcc/rust/typecheck/rust-hir-type-check.h
index 27b7f12..491de85 100644
--- a/gcc/rust/typecheck/rust-hir-type-check.h
+++ b/gcc/rust/typecheck/rust-hir-type-check.h
@@ -42,6 +42,8 @@ public:
 		    TyTy::BaseType *type);
   bool lookup_type (HirId id, TyTy::BaseType **type);
 
+  void insert_implicit_type (HirId id, TyTy::BaseType *type);
+
   void insert_type_by_node_id (NodeId ref, HirId id);
   bool lookup_type_by_node_id (NodeId ref, HirId *id);
 
diff --git a/gcc/rust/typecheck/rust-substitution-mapper.h b/gcc/rust/typecheck/rust-substitution-mapper.h
index c7ea029..28cbeb8 100644
--- a/gcc/rust/typecheck/rust-substitution-mapper.h
+++ b/gcc/rust/typecheck/rust-substitution-mapper.h
@@ -90,6 +90,36 @@ public:
       resolved = concrete;
   }
 
+  void visit (TyTy::PlaceholderType &type) override
+  {
+    rust_assert (type.can_resolve ());
+    resolved = SubstMapper::Resolve (type.resolve (), locus, generics);
+  }
+
+  void visit (TyTy::ProjectionType &type) override
+  {
+    TyTy::ProjectionType *concrete = nullptr;
+    if (!have_generic_args ())
+      {
+	TyTy::BaseType *substs = type.infer_substitions (locus);
+	rust_assert (substs->get_kind () == TyTy::TypeKind::ADT);
+	concrete = static_cast<TyTy::ProjectionType *> (substs);
+      }
+    else
+      {
+	TyTy::SubstitutionArgumentMappings mappings
+	  = type.get_mappings_from_generic_args (*generics);
+	if (mappings.is_error ())
+	  return;
+
+	concrete = type.handle_substitions (mappings);
+      }
+
+    if (concrete != nullptr)
+      resolved = concrete;
+  }
+
+  // nothing to do for these
   void visit (TyTy::InferType &) override { gcc_unreachable (); }
   void visit (TyTy::TupleType &) override { gcc_unreachable (); }
   void visit (TyTy::FnPtr &) override { gcc_unreachable (); }
@@ -107,8 +137,6 @@ public:
   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::ProjectionType &) override { gcc_unreachable (); }
 
 private:
   SubstMapper (HirId ref, HIR::GenericArgs *generics, Location locus)
@@ -177,6 +205,17 @@ public:
     resolved = type.handle_substitions (mappings);
   }
 
+  void visit (TyTy::PlaceholderType &type) override
+  {
+    rust_assert (type.can_resolve ());
+    resolved = SubstMapperInternal::Resolve (type.resolve (), mappings);
+  }
+
+  void visit (TyTy::ProjectionType &type) override
+  {
+    resolved = type.handle_substitions (mappings);
+  }
+
   // nothing to do for these
   void visit (TyTy::InferType &) override { gcc_unreachable (); }
   void visit (TyTy::FnPtr &) override { gcc_unreachable (); }
@@ -191,8 +230,6 @@ public:
   void visit (TyTy::CharType &) 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::ProjectionType &) override { gcc_unreachable (); }
 
 private:
   SubstMapperInternal (HirId ref, TyTy::SubstitutionArgumentMappings &mappings)
diff --git a/gcc/rust/typecheck/rust-tyctx.cc b/gcc/rust/typecheck/rust-tyctx.cc
index ff1c627..95a16fa 100644
--- a/gcc/rust/typecheck/rust-tyctx.cc
+++ b/gcc/rust/typecheck/rust-tyctx.cc
@@ -83,6 +83,13 @@ TypeCheckContext::insert_type (const Analysis::NodeMapping &mappings,
   resolved[id] = type;
 }
 
+void
+TypeCheckContext::insert_implicit_type (HirId id, TyTy::BaseType *type)
+{
+  rust_assert (type != nullptr);
+  resolved[id] = type;
+}
+
 bool
 TypeCheckContext::lookup_type (HirId id, TyTy::BaseType **type)
 {
diff --git a/gcc/rust/typecheck/rust-tyty-coercion.h b/gcc/rust/typecheck/rust-tyty-coercion.h
index d30be7f..f12ffb4 100644
--- a/gcc/rust/typecheck/rust-tyty-coercion.h
+++ b/gcc/rust/typecheck/rust-tyty-coercion.h
@@ -46,6 +46,19 @@ public:
 	    other = p->resolve ();
 	  }
       }
+    else if (other->get_kind () == TypeKind::PLACEHOLDER)
+      {
+	PlaceholderType *p = static_cast<PlaceholderType *> (other);
+	if (p->can_resolve ())
+	  {
+	    other = p->resolve ();
+	  }
+      }
+    else if (other->get_kind () == TypeKind::PROJECTION)
+      {
+	ProjectionType *p = static_cast<ProjectionType *> (other);
+	other = p->get ();
+      }
 
     other->accept_vis (*this);
     if (resolved->get_kind () == TyTy::TypeKind::ERROR)
diff --git a/gcc/rust/typecheck/rust-tyty-rules.h b/gcc/rust/typecheck/rust-tyty-rules.h
index 4d0b977..db7d8c0 100644
--- a/gcc/rust/typecheck/rust-tyty-rules.h
+++ b/gcc/rust/typecheck/rust-tyty-rules.h
@@ -76,6 +76,11 @@ public:
 	    other = p->resolve ();
 	  }
       }
+    else if (other->get_kind () == TypeKind::PROJECTION)
+      {
+	ProjectionType *p = static_cast<ProjectionType *> (other);
+	other = p->get ();
+      }
 
     other->accept_vis (*this);
     if (resolved->get_kind () == TyTy::TypeKind::ERROR)
diff --git a/gcc/rust/typecheck/rust-tyty.cc b/gcc/rust/typecheck/rust-tyty.cc
index e449b55..7eb717f 100644
--- a/gcc/rust/typecheck/rust-tyty.cc
+++ b/gcc/rust/typecheck/rust-tyty.cc
@@ -414,8 +414,6 @@ SubstitutionArgumentMappings
 SubstitutionRef::adjust_mappings_for_this (
   SubstitutionArgumentMappings &mappings)
 {
-  Analysis::Mappings *mappings_table = Analysis::Mappings::get ();
-
   std::vector<SubstitutionArg> resolved_mappings;
   for (size_t i = 0; i < substitutions.size (); i++)
     {
@@ -442,20 +440,16 @@ SubstitutionRef::adjust_mappings_for_this (
 	}
 
       bool ok = !arg.is_error ();
-      if (!ok)
+      if (ok)
 	{
-	  rust_error_at (mappings_table->lookup_location (
-			   subst.get_param_ty ()->get_ref ()),
-			 "failed to find parameter type: %s vs mappings [%s]",
-			 subst.get_param_ty ()->as_string ().c_str (),
-			 mappings.as_string ().c_str ());
-	  return SubstitutionArgumentMappings::error ();
+	  SubstitutionArg adjusted (&subst, arg.get_tyty ());
+	  resolved_mappings.push_back (std::move (adjusted));
 	}
-
-      SubstitutionArg adjusted (&subst, arg.get_tyty ());
-      resolved_mappings.push_back (std::move (adjusted));
     }
 
+  if (resolved_mappings.empty ())
+    return SubstitutionArgumentMappings::error ();
+
   return SubstitutionArgumentMappings (resolved_mappings,
 				       mappings.get_locus ());
 }
@@ -907,7 +901,9 @@ FnType::handle_substitions (SubstitutionArgumentMappings subst_mappings)
       bool ok
 	= subst_mappings.get_argument_for_symbol (sub.get_param_ty (), &arg);
       if (ok)
-	sub.fill_param_ty (arg.get_tyty (), subst_mappings.get_locus ());
+	{
+	  sub.fill_param_ty (arg.get_tyty (), subst_mappings.get_locus ());
+	}
     }
 
   auto fty = fn->get_return_type ();
@@ -2139,42 +2135,106 @@ ProjectionType::accept_vis (TyConstVisitor &vis) const
 std::string
 ProjectionType::as_string () const
 {
-  return "<Projection>";
+  return "<Projection=" + subst_as_string () + "::" + base->as_string () + ">";
 }
 
 BaseType *
 ProjectionType::unify (BaseType *other)
 {
-  gcc_unreachable ();
-  return nullptr;
+  return base->unify (other);
 }
 
 BaseType *
 ProjectionType::coerce (BaseType *other)
 {
-  gcc_unreachable ();
-  return nullptr;
+  return base->coerce (other);
 }
 
 BaseType *
 ProjectionType::cast (BaseType *other)
 {
-  gcc_unreachable ();
-  return nullptr;
+  return base->cast (other);
 }
 
 bool
 ProjectionType::can_eq (const BaseType *other, bool emit_errors) const
 {
-  gcc_unreachable ();
-  return false;
+  return base->can_eq (other, emit_errors);
 }
 
 BaseType *
 ProjectionType::clone () const
 {
   return new ProjectionType (get_ref (), get_ty_ref (), base, trait, item,
-			     associated, get_combined_refs ());
+			     clone_substs (), used_arguments,
+			     get_combined_refs ());
+}
+
+ProjectionType *
+ProjectionType::handle_substitions (SubstitutionArgumentMappings subst_mappings)
+{
+  ProjectionType *projection = static_cast<ProjectionType *> (clone ());
+  projection->set_ty_ref (mappings->get_next_hir_id ());
+  projection->used_arguments = subst_mappings;
+
+  auto context = Resolver::TypeCheckContext::get ();
+  context->insert_implicit_type (projection->get_ty_ref (), projection);
+
+  for (auto &sub : projection->get_substs ())
+    {
+      SubstitutionArg arg = SubstitutionArg::error ();
+      bool ok
+	= subst_mappings.get_argument_for_symbol (sub.get_param_ty (), &arg);
+      if (ok)
+	sub.fill_param_ty (arg.get_tyty (), subst_mappings.get_locus ());
+    }
+
+  auto fty = projection->base;
+  bool is_param_ty = fty->get_kind () == TypeKind::PARAM;
+  if (is_param_ty)
+    {
+      ParamType *p = static_cast<ParamType *> (fty);
+
+      SubstitutionArg arg = SubstitutionArg::error ();
+      bool ok = subst_mappings.get_argument_for_symbol (p, &arg);
+      if (ok)
+	{
+	  auto argt = arg.get_tyty ();
+	  bool arg_is_param = argt->get_kind () == TyTy::TypeKind::PARAM;
+	  bool arg_is_concrete = argt->get_kind () != TyTy::TypeKind::INFER;
+
+	  if (arg_is_param || arg_is_concrete)
+	    {
+	      auto new_field = argt->clone ();
+	      new_field->set_ref (fty->get_ref ());
+	      projection->base = new_field;
+	    }
+	  else
+	    {
+	      fty->set_ty_ref (argt->get_ref ());
+	    }
+	}
+    }
+  else if (fty->needs_generic_substitutions ()
+	   || fty->contains_type_parameters ())
+    {
+      BaseType *concrete
+	= Resolver::SubstMapperInternal::Resolve (fty, subst_mappings);
+
+      if (concrete == nullptr || concrete->get_kind () == TyTy::TypeKind::ERROR)
+	{
+	  rust_error_at (subst_mappings.get_locus (),
+			 "Failed to resolve field substitution type: %s",
+			 fty->as_string ().c_str ());
+	  return nullptr;
+	}
+
+      auto new_field = concrete->clone ();
+      new_field->set_ref (fty->get_ref ());
+      projection->base = new_field;
+    }
+
+  return projection;
 }
 
 // rust-tyty-call.h
diff --git a/gcc/rust/typecheck/rust-tyty.h b/gcc/rust/typecheck/rust-tyty.h
index 181be94..0dfae37 100644
--- a/gcc/rust/typecheck/rust-tyty.h
+++ b/gcc/rust/typecheck/rust-tyty.h
@@ -1727,26 +1727,38 @@ public:
 
   bool is_equal (const BaseType &other) const override;
 
+  bool contains_type_parameters () const override
+  {
+    rust_assert (can_resolve ());
+    return resolve ()->contains_type_parameters ();
+  }
+
 private:
   std::string symbol;
 };
 
-class ProjectionType : public BaseType
+class ProjectionType : public BaseType, public SubstitutionRef
 {
 public:
-  ProjectionType (HirId ref, TyVar base, Resolver::TraitReference *trait,
-		  DefId item, Resolver::AssociatedImplTrait *associated,
+  ProjectionType (HirId ref, BaseType *base, Resolver::TraitReference *trait,
+		  DefId item, std::vector<SubstitutionParamMapping> subst_refs,
+		  SubstitutionArgumentMappings generic_arguments
+		  = SubstitutionArgumentMappings::error (),
 		  std::set<HirId> refs = std::set<HirId> ())
-    : BaseType (ref, ref, TypeKind::PROJECTION, refs), base (base),
-      trait (trait), item (item), associated (associated)
+    : BaseType (ref, ref, TypeKind::PROJECTION, refs),
+      SubstitutionRef (std::move (subst_refs), std::move (generic_arguments)),
+      base (base), trait (trait), item (item)
   {}
 
-  ProjectionType (HirId ref, HirId ty_ref, TyVar base,
+  ProjectionType (HirId ref, HirId ty_ref, BaseType *base,
 		  Resolver::TraitReference *trait, DefId item,
-		  Resolver::AssociatedImplTrait *associated,
+		  std::vector<SubstitutionParamMapping> subst_refs,
+		  SubstitutionArgumentMappings generic_arguments
+		  = SubstitutionArgumentMappings::error (),
 		  std::set<HirId> refs = std::set<HirId> ())
-    : BaseType (ref, ty_ref, TypeKind::PROJECTION, refs), base (base),
-      trait (trait), item (item), associated (associated)
+    : BaseType (ref, ty_ref, TypeKind::PROJECTION, refs),
+      SubstitutionRef (std::move (subst_refs), std::move (generic_arguments)),
+      base (base), trait (trait), item (item)
   {}
 
   void accept_vis (TyVisitor &vis) override;
@@ -1765,11 +1777,32 @@ public:
 
   bool is_unit () const override { return false; }
 
+  bool needs_generic_substitutions () const override final
+  {
+    return needs_substitution ();
+  }
+
+  bool supports_substitutions () const override final { return true; }
+
+  bool has_subsititions_defined () const override final
+  {
+    return has_substitutions ();
+  }
+
+  BaseType *get () { return base; }
+
+  bool contains_type_parameters () const override
+  {
+    return base->contains_type_parameters ();
+  }
+
+  ProjectionType *
+  handle_substitions (SubstitutionArgumentMappings mappings) override final;
+
 private:
-  TyVar base;
+  BaseType *base;
   Resolver::TraitReference *trait;
   DefId item;
-  Resolver::AssociatedImplTrait *associated;
 };
 
 } // namespace TyTy
diff --git a/gcc/testsuite/rust/compile/torture/traits14.rs b/gcc/testsuite/rust/compile/torture/traits14.rs
new file mode 100644
index 0000000..8bca0d5
--- /dev/null
+++ b/gcc/testsuite/rust/compile/torture/traits14.rs
@@ -0,0 +1,23 @@
+trait Foo<T> {
+    type A;
+
+    fn test(a: T) -> T {
+        a
+    }
+}
+
+struct Bar<T>(T);
+impl<T> Foo<T> for Bar<T> {
+    type A = T;
+}
+
+pub fn main() {
+    let a;
+    a = Bar(123);
+
+    let b: <Bar<i32> as Foo<i32>>::A;
+    b = 456;
+
+    let c: <Bar<i32> as Foo<i32>>::A;
+    c = <Bar<i32> as Foo<i32>>::test(a.0);
+}
diff --git a/gcc/testsuite/rust/compile/torture/traits15.rs b/gcc/testsuite/rust/compile/torture/traits15.rs
new file mode 100644
index 0000000..c8c40b7
--- /dev/null
+++ b/gcc/testsuite/rust/compile/torture/traits15.rs
@@ -0,0 +1,23 @@
+trait Foo<T> {
+    type A;
+
+    fn test(a: T, b: Self::A) -> (T, Self::A) {
+        (a, b)
+    }
+}
+
+struct Bar<T>(T);
+impl<T> Foo<T> for Bar<T> {
+    type A = T;
+}
+
+pub fn main() {
+    let a;
+    a = Bar(123);
+
+    let b: <Bar<i32> as Foo<i32>>::A;
+    b = 456;
+
+    let c;
+    c = <Bar<i32> as Foo<i32>>::test(a.0, 123);
+}