[committed 38/88] gccrs: Refactor SubstitutionRef base class into its own CC file

[arthur.cohen@embecosm.com]

From: Philip Herron <herron.philip@googlemail.com>

Signed-off-by: Philip Herron <herron.philip@googlemail.com>

gcc/rust/ChangeLog:

	* Make-lang.in: update the makefile
	* typecheck/rust-tyty.cc (SubstitutionParamMapping::need_substitution): likewise
	(SubstitutionParamMapping::override_context): likewise
	(SubstitutionRef::get_mappings_from_generic_args): likewise
	(SubstitutionRef::infer_substitions): likewise
	(SubstitutionRef::are_mappings_bound): likewise
	(SubstitutionRef::solve_missing_mappings_from_this): likewise
	(SubstitutionRef::monomorphize): likewise
	* typecheck/rust-tyty.h (class SubstitutionParamMapping): likewise
	(class SubstitutionArg): likewise
	(std::function<void): likewise
	(class SubstitutionArgumentMappings): likewise
	(class SubstitutionRef): likewise
	* typecheck/rust-tyty-subst.cc: New file.
	* typecheck/rust-tyty-subst.h: New file.
---
 gcc/rust/Make-lang.in                 |   1 +
 gcc/rust/typecheck/rust-tyty-subst.cc | 927 ++++++++++++++++++++++++++
 gcc/rust/typecheck/rust-tyty-subst.h  | 316 +++++++++
 gcc/rust/typecheck/rust-tyty.cc       | 466 -------------
 gcc/rust/typecheck/rust-tyty.h        | 464 +------------
 5 files changed, 1245 insertions(+), 929 deletions(-)
 create mode 100644 gcc/rust/typecheck/rust-tyty-subst.cc
 create mode 100644 gcc/rust/typecheck/rust-tyty-subst.h

diff --git a/gcc/rust/Make-lang.in b/gcc/rust/Make-lang.in
index 2aa61bcfb19..5e173f1d2dc 100644
--- a/gcc/rust/Make-lang.in
+++ b/gcc/rust/Make-lang.in
@@ -117,6 +117,7 @@ GRS_OBJS = \
     rust/rust-tyty.o \
     rust/rust-tyty-util.o \
     rust/rust-tyty-call.o \
+    rust/rust-tyty-subst.o \
     rust/rust-tyctx.o \
     rust/rust-tyty-bounds.o \
     rust/rust-hir-type-check-util.o \
diff --git a/gcc/rust/typecheck/rust-tyty-subst.cc b/gcc/rust/typecheck/rust-tyty-subst.cc
new file mode 100644
index 00000000000..64001459b4d
--- /dev/null
+++ b/gcc/rust/typecheck/rust-tyty-subst.cc
@@ -0,0 +1,927 @@
+// Copyright (C) 2020-2022 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC is free software; you can redistribute it and/or modify it under
+// the terms of the GNU General Public License as published by the Free
+// Software Foundation; either version 3, or (at your option) any later
+// version.
+
+// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY; without even the implied warranty of MERCHANTABILITY or
+// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+// for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include "rust-tyty-subst.h"
+#include "rust-hir-full.h"
+#include "rust-tyty.h"
+#include "rust-hir-type-check.h"
+#include "rust-substitution-mapper.h"
+#include "rust-hir-type-check-type.h"
+
+namespace Rust {
+namespace TyTy {
+
+SubstitutionParamMapping::SubstitutionParamMapping (
+  const HIR::TypeParam &generic, ParamType *param)
+  : generic (generic), param (param)
+{}
+
+SubstitutionParamMapping::SubstitutionParamMapping (
+  const SubstitutionParamMapping &other)
+  : generic (other.generic), param (other.param)
+{}
+
+std::string
+SubstitutionParamMapping::as_string () const
+{
+  if (param == nullptr)
+    return "nullptr";
+
+  return param->get_name ();
+}
+
+SubstitutionParamMapping
+SubstitutionParamMapping::clone () const
+{
+  return SubstitutionParamMapping (generic,
+				   static_cast<ParamType *> (param->clone ()));
+}
+
+ParamType *
+SubstitutionParamMapping::get_param_ty ()
+{
+  return param;
+}
+
+const ParamType *
+SubstitutionParamMapping::get_param_ty () const
+{
+  return param;
+}
+
+const HIR::TypeParam &
+SubstitutionParamMapping::get_generic_param ()
+{
+  return generic;
+};
+
+bool
+SubstitutionParamMapping::needs_substitution () const
+{
+  return !(get_param_ty ()->is_concrete ());
+}
+
+Location
+SubstitutionParamMapping::get_param_locus () const
+{
+  return generic.get_locus ();
+}
+
+bool
+SubstitutionParamMapping::param_has_default_ty () const
+{
+  return generic.has_type ();
+}
+
+BaseType *
+SubstitutionParamMapping::get_default_ty () const
+{
+  TyVar var (generic.get_type_mappings ().get_hirid ());
+  return var.get_tyty ();
+}
+
+bool
+SubstitutionParamMapping::need_substitution () const
+{
+  if (!param->can_resolve ())
+    return true;
+
+  auto resolved = param->resolve ();
+  return !resolved->is_concrete ();
+}
+
+bool
+SubstitutionParamMapping::fill_param_ty (
+  SubstitutionArgumentMappings &subst_mappings, Location locus)
+{
+  SubstitutionArg arg = SubstitutionArg::error ();
+  bool ok = subst_mappings.get_argument_for_symbol (get_param_ty (), &arg);
+  if (!ok)
+    return true;
+
+  TyTy::BaseType &type = *arg.get_tyty ();
+  if (type.get_kind () == TyTy::TypeKind::INFER)
+    {
+      type.inherit_bounds (*param);
+    }
+  else
+    {
+      if (!param->bounds_compatible (type, locus, true))
+	return false;
+    }
+
+  if (type.get_kind () == TypeKind::PARAM)
+    {
+      // delete param;
+      param = static_cast<ParamType *> (type.clone ());
+    }
+  else
+    {
+      // check the substitution is compatible with bounds
+      if (!param->bounds_compatible (type, locus, true))
+	return false;
+
+      // recursively pass this down to all HRTB's
+      for (auto &bound : param->get_specified_bounds ())
+	bound.handle_substitions (subst_mappings);
+
+      param->set_ty_ref (type.get_ref ());
+    }
+
+  return true;
+}
+
+void
+SubstitutionParamMapping::override_context ()
+{
+  if (!param->can_resolve ())
+    return;
+
+  auto mappings = Analysis::Mappings::get ();
+  auto context = Resolver::TypeCheckContext::get ();
+
+  context->insert_type (Analysis::NodeMapping (mappings->get_current_crate (),
+					       UNKNOWN_NODEID,
+					       param->get_ref (),
+					       UNKNOWN_LOCAL_DEFID),
+			param->resolve ());
+}
+
+SubstitutionArg::SubstitutionArg (const SubstitutionParamMapping *param,
+				  BaseType *argument)
+  : param (param), argument (argument)
+{}
+
+SubstitutionArg::SubstitutionArg (const SubstitutionArg &other)
+  : param (other.param), argument (other.argument)
+{}
+
+SubstitutionArg &
+SubstitutionArg::operator= (const SubstitutionArg &other)
+{
+  param = other.param;
+  argument = other.argument;
+  return *this;
+}
+
+BaseType *
+SubstitutionArg::get_tyty ()
+{
+  return argument;
+}
+
+const BaseType *
+SubstitutionArg::get_tyty () const
+{
+  return argument;
+}
+
+const SubstitutionParamMapping *
+SubstitutionArg::get_param_mapping () const
+{
+  return param;
+}
+
+SubstitutionArg
+SubstitutionArg::error ()
+{
+  return SubstitutionArg (nullptr, nullptr);
+}
+
+bool
+SubstitutionArg::is_error () const
+{
+  return param == nullptr || argument == nullptr;
+}
+
+bool
+SubstitutionArg::is_conrete () const
+{
+  if (argument != nullptr)
+    return true;
+
+  if (argument->get_kind () == TyTy::TypeKind::PARAM)
+    return false;
+
+  return argument->is_concrete ();
+}
+
+std::string
+SubstitutionArg::as_string () const
+{
+  return param->as_string ()
+	 + (argument != nullptr ? ":" + argument->as_string () : "");
+}
+
+// SubstitutionArgumentMappings
+
+SubstitutionArgumentMappings::SubstitutionArgumentMappings (
+  std::vector<SubstitutionArg> mappings,
+  std::map<std::string, BaseType *> binding_args, Location locus,
+  ParamSubstCb param_subst_cb, bool trait_item_flag)
+  : mappings (mappings), binding_args (binding_args), locus (locus),
+    param_subst_cb (param_subst_cb), trait_item_flag (trait_item_flag)
+{}
+
+SubstitutionArgumentMappings::SubstitutionArgumentMappings (
+  const SubstitutionArgumentMappings &other)
+  : mappings (other.mappings), binding_args (other.binding_args),
+    locus (other.locus), param_subst_cb (other.param_subst_cb),
+    trait_item_flag (other.trait_item_flag)
+{}
+
+SubstitutionArgumentMappings &
+SubstitutionArgumentMappings::operator= (
+  const SubstitutionArgumentMappings &other)
+{
+  mappings = other.mappings;
+  binding_args = other.binding_args;
+  locus = other.locus;
+  param_subst_cb = other.param_subst_cb;
+  trait_item_flag = other.trait_item_flag;
+
+  return *this;
+}
+
+SubstitutionArgumentMappings
+SubstitutionArgumentMappings::error ()
+{
+  return SubstitutionArgumentMappings ({}, {}, Location (), nullptr, false);
+}
+
+bool
+SubstitutionArgumentMappings::is_error () const
+{
+  return mappings.size () == 0;
+}
+
+bool
+SubstitutionArgumentMappings::get_argument_for_symbol (
+  const ParamType *param_to_find, SubstitutionArg *argument)
+{
+  for (auto &mapping : mappings)
+    {
+      const SubstitutionParamMapping *param = mapping.get_param_mapping ();
+      const ParamType *p = param->get_param_ty ();
+
+      if (p->get_symbol ().compare (param_to_find->get_symbol ()) == 0)
+	{
+	  *argument = mapping;
+	  return true;
+	}
+    }
+  return false;
+}
+
+bool
+SubstitutionArgumentMappings::get_argument_at (size_t index,
+					       SubstitutionArg *argument)
+{
+  if (index > mappings.size ())
+    return false;
+
+  *argument = mappings.at (index);
+  return true;
+}
+
+bool
+SubstitutionArgumentMappings::is_concrete () const
+{
+  for (auto &mapping : mappings)
+    {
+      if (!mapping.is_conrete ())
+	return false;
+    }
+  return true;
+}
+
+Location
+SubstitutionArgumentMappings::get_locus () const
+{
+  return locus;
+}
+
+size_t
+SubstitutionArgumentMappings::size () const
+{
+  return mappings.size ();
+}
+
+bool
+SubstitutionArgumentMappings::is_empty () const
+{
+  return size () == 0;
+}
+
+std::vector<SubstitutionArg> &
+SubstitutionArgumentMappings::get_mappings ()
+{
+  return mappings;
+}
+
+const std::vector<SubstitutionArg> &
+SubstitutionArgumentMappings::get_mappings () const
+{
+  return mappings;
+}
+
+std::map<std::string, BaseType *> &
+SubstitutionArgumentMappings::get_binding_args ()
+{
+  return binding_args;
+}
+
+const std::map<std::string, BaseType *> &
+SubstitutionArgumentMappings::get_binding_args () const
+{
+  return binding_args;
+}
+
+std::string
+SubstitutionArgumentMappings::as_string () const
+{
+  std::string buffer;
+  for (auto &mapping : mappings)
+    {
+      buffer += mapping.as_string () + ", ";
+    }
+  return "<" + buffer + ">";
+}
+
+void
+SubstitutionArgumentMappings::on_param_subst (const ParamType &p,
+					      const SubstitutionArg &a) const
+{
+  if (param_subst_cb == nullptr)
+    return;
+
+  param_subst_cb (p, a);
+}
+
+ParamSubstCb
+SubstitutionArgumentMappings::get_subst_cb () const
+{
+  return param_subst_cb;
+}
+
+bool
+SubstitutionArgumentMappings::trait_item_mode () const
+{
+  return trait_item_flag;
+}
+
+// SubstitutionRef
+
+SubstitutionRef::SubstitutionRef (
+  std::vector<SubstitutionParamMapping> substitutions,
+  SubstitutionArgumentMappings arguments)
+  : substitutions (substitutions), used_arguments (arguments)
+{}
+
+bool
+SubstitutionRef::has_substitutions () const
+{
+  return substitutions.size () > 0;
+}
+
+std::string
+SubstitutionRef::subst_as_string () const
+{
+  std::string buffer;
+  for (size_t i = 0; i < substitutions.size (); i++)
+    {
+      const SubstitutionParamMapping &sub = substitutions.at (i);
+      buffer += sub.as_string ();
+
+      if ((i + 1) < substitutions.size ())
+	buffer += ", ";
+    }
+
+  return buffer.empty () ? "" : "<" + buffer + ">";
+}
+
+bool
+SubstitutionRef::supports_associated_bindings () const
+{
+  return get_num_associated_bindings () > 0;
+}
+
+size_t
+SubstitutionRef::get_num_associated_bindings () const
+{
+  return 0;
+}
+
+TypeBoundPredicateItem
+SubstitutionRef::lookup_associated_type (const std::string &search)
+{
+  return TypeBoundPredicateItem::error ();
+}
+
+size_t
+SubstitutionRef::get_num_substitutions () const
+{
+  return substitutions.size ();
+}
+
+std::vector<SubstitutionParamMapping> &
+SubstitutionRef::get_substs ()
+{
+  return substitutions;
+}
+
+const std::vector<SubstitutionParamMapping> &
+SubstitutionRef::get_substs () const
+{
+  return substitutions;
+}
+
+std::vector<SubstitutionParamMapping>
+SubstitutionRef::clone_substs () const
+{
+  std::vector<SubstitutionParamMapping> clone;
+
+  for (auto &sub : substitutions)
+    clone.push_back (sub.clone ());
+
+  return clone;
+}
+
+void
+SubstitutionRef::override_context ()
+{
+  for (auto &sub : substitutions)
+    {
+      sub.override_context ();
+    }
+}
+
+bool
+SubstitutionRef::needs_substitution () const
+{
+  for (auto &sub : substitutions)
+    {
+      if (sub.need_substitution ())
+	return true;
+    }
+  return false;
+}
+
+bool
+SubstitutionRef::was_substituted () const
+{
+  return !needs_substitution ();
+}
+
+SubstitutionArgumentMappings
+SubstitutionRef::get_substitution_arguments () const
+{
+  return used_arguments;
+}
+
+size_t
+SubstitutionRef::num_required_substitutions () const
+{
+  size_t n = 0;
+  for (auto &p : substitutions)
+    {
+      if (p.needs_substitution ())
+	n++;
+    }
+  return n;
+}
+
+size_t
+SubstitutionRef::min_required_substitutions () const
+{
+  size_t n = 0;
+  for (auto &p : substitutions)
+    {
+      if (p.needs_substitution () && !p.param_has_default_ty ())
+	n++;
+    }
+  return n;
+}
+
+SubstitutionArgumentMappings
+SubstitutionRef::get_used_arguments () const
+{
+  return used_arguments;
+}
+
+SubstitutionArgumentMappings
+SubstitutionRef::get_mappings_from_generic_args (HIR::GenericArgs &args)
+{
+  std::map<std::string, BaseType *> binding_arguments;
+  if (args.get_binding_args ().size () > 0)
+    {
+      if (supports_associated_bindings ())
+	{
+	  if (args.get_binding_args ().size () > get_num_associated_bindings ())
+	    {
+	      RichLocation r (args.get_locus ());
+
+	      rust_error_at (r,
+			     "generic item takes at most %lu type binding "
+			     "arguments but %lu were supplied",
+			     (unsigned long) get_num_associated_bindings (),
+			     (unsigned long) args.get_binding_args ().size ());
+	      return SubstitutionArgumentMappings::error ();
+	    }
+
+	  for (auto &binding : args.get_binding_args ())
+	    {
+	      BaseType *resolved
+		= Resolver::TypeCheckType::Resolve (binding.get_type ().get ());
+	      if (resolved == nullptr
+		  || resolved->get_kind () == TyTy::TypeKind::ERROR)
+		{
+		  rust_error_at (binding.get_locus (),
+				 "failed to resolve type arguments");
+		  return SubstitutionArgumentMappings::error ();
+		}
+
+	      // resolve to relevant binding
+	      auto binding_item
+		= lookup_associated_type (binding.get_identifier ());
+	      if (binding_item.is_error ())
+		{
+		  rust_error_at (binding.get_locus (),
+				 "unknown associated type binding: %s",
+				 binding.get_identifier ().c_str ());
+		  return SubstitutionArgumentMappings::error ();
+		}
+
+	      binding_arguments[binding.get_identifier ()] = resolved;
+	    }
+	}
+      else
+	{
+	  RichLocation r (args.get_locus ());
+	  for (auto &binding : args.get_binding_args ())
+	    r.add_range (binding.get_locus ());
+
+	  rust_error_at (r, "associated type bindings are not allowed here");
+	  return SubstitutionArgumentMappings::error ();
+	}
+    }
+
+  // for inherited arguments
+  size_t offs = used_arguments.size ();
+  if (args.get_type_args ().size () + offs > substitutions.size ())
+    {
+      RichLocation r (args.get_locus ());
+      r.add_range (substitutions.front ().get_param_locus ());
+
+      rust_error_at (
+	r,
+	"generic item takes at most %lu type arguments but %lu were supplied",
+	(unsigned long) substitutions.size (),
+	(unsigned long) args.get_type_args ().size ());
+      return SubstitutionArgumentMappings::error ();
+    }
+
+  if (args.get_type_args ().size () + offs < min_required_substitutions ())
+    {
+      RichLocation r (args.get_locus ());
+      r.add_range (substitutions.front ().get_param_locus ());
+
+      rust_error_at (
+	r,
+	"generic item takes at least %lu type arguments but %lu were supplied",
+	(unsigned long) (min_required_substitutions () - offs),
+	(unsigned long) args.get_type_args ().size ());
+      return SubstitutionArgumentMappings::error ();
+    }
+
+  std::vector<SubstitutionArg> mappings = used_arguments.get_mappings ();
+  for (auto &arg : args.get_type_args ())
+    {
+      BaseType *resolved = Resolver::TypeCheckType::Resolve (arg.get ());
+      if (resolved == nullptr || resolved->get_kind () == TyTy::TypeKind::ERROR)
+	{
+	  rust_error_at (args.get_locus (), "failed to resolve type arguments");
+	  return SubstitutionArgumentMappings::error ();
+	}
+
+      SubstitutionArg subst_arg (&substitutions.at (offs), resolved);
+      offs++;
+      mappings.push_back (std::move (subst_arg));
+    }
+
+  // we must need to fill out defaults
+  size_t left_over
+    = num_required_substitutions () - min_required_substitutions ();
+  if (left_over > 0)
+    {
+      for (size_t offs = mappings.size (); offs < substitutions.size (); offs++)
+	{
+	  SubstitutionParamMapping &param = substitutions.at (offs);
+	  rust_assert (param.param_has_default_ty ());
+
+	  BaseType *resolved = param.get_default_ty ();
+	  if (resolved->get_kind () == TypeKind::ERROR)
+	    return SubstitutionArgumentMappings::error ();
+
+	  // this resolved default might already contain default parameters
+	  if (resolved->contains_type_parameters ())
+	    {
+	      SubstitutionArgumentMappings intermediate (mappings,
+							 binding_arguments,
+							 args.get_locus ());
+	      resolved = Resolver::SubstMapperInternal::Resolve (resolved,
+								 intermediate);
+
+	      if (resolved->get_kind () == TypeKind::ERROR)
+		return SubstitutionArgumentMappings::error ();
+	    }
+
+	  SubstitutionArg subst_arg (&param, resolved);
+	  mappings.push_back (std::move (subst_arg));
+	}
+    }
+
+  return SubstitutionArgumentMappings (mappings, binding_arguments,
+				       args.get_locus ());
+}
+
+BaseType *
+SubstitutionRef::infer_substitions (Location locus)
+{
+  std::vector<SubstitutionArg> args;
+  std::map<std::string, BaseType *> argument_mappings;
+  for (auto &p : get_substs ())
+    {
+      if (p.needs_substitution ())
+	{
+	  const std::string &symbol = p.get_param_ty ()->get_symbol ();
+	  auto it = argument_mappings.find (symbol);
+	  bool have_mapping = it != argument_mappings.end ();
+
+	  if (have_mapping)
+	    {
+	      args.push_back (SubstitutionArg (&p, it->second));
+	    }
+	  else
+	    {
+	      TyVar infer_var = TyVar::get_implicit_infer_var (locus);
+	      args.push_back (SubstitutionArg (&p, infer_var.get_tyty ()));
+	      argument_mappings[symbol] = infer_var.get_tyty ();
+	    }
+	}
+      else
+	{
+	  args.push_back (SubstitutionArg (&p, p.get_param_ty ()->resolve ()));
+	}
+    }
+
+  // FIXME do we need to add inference variables to all the possible bindings?
+  // it might just lead to inference variable hell not 100% sure if rustc does
+  // this i think the language might needs this to be explicitly set
+
+  SubstitutionArgumentMappings infer_arguments (std::move (args),
+						{} /* binding_arguments */,
+						locus);
+  return handle_substitions (std::move (infer_arguments));
+}
+
+SubstitutionArgumentMappings
+SubstitutionRef::adjust_mappings_for_this (
+  SubstitutionArgumentMappings &mappings)
+{
+  std::vector<SubstitutionArg> resolved_mappings;
+  for (size_t i = 0; i < substitutions.size (); i++)
+    {
+      auto &subst = substitutions.at (i);
+
+      SubstitutionArg arg = SubstitutionArg::error ();
+      if (mappings.size () == substitutions.size ())
+	{
+	  mappings.get_argument_at (i, &arg);
+	}
+      else
+	{
+	  if (subst.needs_substitution ())
+	    {
+	      // get from passed in mappings
+	      mappings.get_argument_for_symbol (subst.get_param_ty (), &arg);
+	    }
+	  else
+	    {
+	      // we should already have this somewhere
+	      used_arguments.get_argument_for_symbol (subst.get_param_ty (),
+						      &arg);
+	    }
+	}
+
+      bool ok = !arg.is_error ();
+      if (ok)
+	{
+	  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_binding_args (),
+				       mappings.get_locus (),
+				       mappings.get_subst_cb (),
+				       mappings.trait_item_mode ());
+}
+
+bool
+SubstitutionRef::are_mappings_bound (SubstitutionArgumentMappings &mappings)
+{
+  std::vector<SubstitutionArg> resolved_mappings;
+  for (size_t i = 0; i < substitutions.size (); i++)
+    {
+      auto &subst = substitutions.at (i);
+
+      SubstitutionArg arg = SubstitutionArg::error ();
+      if (mappings.size () == substitutions.size ())
+	{
+	  mappings.get_argument_at (i, &arg);
+	}
+      else
+	{
+	  if (subst.needs_substitution ())
+	    {
+	      // get from passed in mappings
+	      mappings.get_argument_for_symbol (subst.get_param_ty (), &arg);
+	    }
+	  else
+	    {
+	      // we should already have this somewhere
+	      used_arguments.get_argument_for_symbol (subst.get_param_ty (),
+						      &arg);
+	    }
+	}
+
+      bool ok = !arg.is_error ();
+      if (ok)
+	{
+	  SubstitutionArg adjusted (&subst, arg.get_tyty ());
+	  resolved_mappings.push_back (std::move (adjusted));
+	}
+    }
+
+  return !resolved_mappings.empty ();
+}
+
+// this function assumes that the mappings being passed are for the same type as
+// this new substitution reference so ordering matters here
+SubstitutionArgumentMappings
+SubstitutionRef::solve_mappings_from_receiver_for_self (
+  SubstitutionArgumentMappings &mappings) const
+{
+  std::vector<SubstitutionArg> resolved_mappings;
+
+  rust_assert (mappings.size () == get_num_substitutions ());
+  for (size_t i = 0; i < get_num_substitutions (); i++)
+    {
+      const SubstitutionParamMapping &param_mapping = substitutions.at (i);
+      SubstitutionArg &arg = mappings.get_mappings ().at (i);
+
+      if (param_mapping.needs_substitution ())
+	{
+	  SubstitutionArg adjusted (&param_mapping, arg.get_tyty ());
+	  resolved_mappings.push_back (std::move (adjusted));
+	}
+    }
+
+  return SubstitutionArgumentMappings (resolved_mappings,
+				       mappings.get_binding_args (),
+				       mappings.get_locus ());
+}
+
+SubstitutionArgumentMappings
+SubstitutionRef::solve_missing_mappings_from_this (SubstitutionRef &ref,
+						   SubstitutionRef &to)
+{
+  rust_assert (!ref.needs_substitution ());
+  rust_assert (needs_substitution ());
+  rust_assert (get_num_substitutions () == ref.get_num_substitutions ());
+
+  Location locus = used_arguments.get_locus ();
+  std::vector<SubstitutionArg> resolved_mappings;
+
+  std::map<HirId, std::pair<ParamType *, BaseType *>> substs;
+  for (size_t i = 0; i < get_num_substitutions (); i++)
+    {
+      SubstitutionParamMapping &a = substitutions.at (i);
+      SubstitutionParamMapping &b = ref.substitutions.at (i);
+
+      if (a.need_substitution ())
+	{
+	  const BaseType *root = a.get_param_ty ()->resolve ()->get_root ();
+	  rust_assert (root->get_kind () == TyTy::TypeKind::PARAM);
+	  const ParamType *p = static_cast<const TyTy::ParamType *> (root);
+
+	  substs[p->get_ty_ref ()] = {static_cast<ParamType *> (p->clone ()),
+				      b.get_param_ty ()->resolve ()};
+	}
+    }
+
+  for (auto it = substs.begin (); it != substs.end (); it++)
+    {
+      HirId param_id = it->first;
+      BaseType *arg = it->second.second;
+
+      const SubstitutionParamMapping *associate_param = nullptr;
+      for (SubstitutionParamMapping &p : to.substitutions)
+	{
+	  if (p.get_param_ty ()->get_ty_ref () == param_id)
+	    {
+	      associate_param = &p;
+	      break;
+	    }
+	}
+
+      rust_assert (associate_param != nullptr);
+      SubstitutionArg argument (associate_param, arg);
+      resolved_mappings.push_back (std::move (argument));
+    }
+
+  return SubstitutionArgumentMappings (resolved_mappings, {}, locus);
+}
+
+bool
+SubstitutionRef::monomorphize ()
+{
+  auto context = Resolver::TypeCheckContext::get ();
+  for (const auto &subst : get_substs ())
+    {
+      const TyTy::ParamType *pty = subst.get_param_ty ();
+
+      if (!pty->can_resolve ())
+	continue;
+
+      const TyTy::BaseType *binding = pty->resolve ();
+      if (binding->get_kind () == TyTy::TypeKind::PARAM)
+	continue;
+
+      for (const auto &bound : pty->get_specified_bounds ())
+	{
+	  const Resolver::TraitReference *specified_bound_ref = bound.get ();
+
+	  // setup any associated type mappings for the specified bonds and this
+	  // type
+	  auto candidates = Resolver::TypeBoundsProbe::Probe (binding);
+
+	  Resolver::AssociatedImplTrait *associated_impl_trait = nullptr;
+	  for (auto &probed_bound : candidates)
+	    {
+	      const Resolver::TraitReference *bound_trait_ref
+		= probed_bound.first;
+	      const HIR::ImplBlock *associated_impl = probed_bound.second;
+
+	      HirId impl_block_id
+		= associated_impl->get_mappings ().get_hirid ();
+	      Resolver::AssociatedImplTrait *associated = nullptr;
+	      bool found_impl_trait
+		= context->lookup_associated_trait_impl (impl_block_id,
+							 &associated);
+	      if (found_impl_trait)
+		{
+		  bool found_trait
+		    = specified_bound_ref->is_equal (*bound_trait_ref);
+		  bool found_self
+		    = associated->get_self ()->can_eq (binding, false);
+		  if (found_trait && found_self)
+		    {
+		      associated_impl_trait = associated;
+		      break;
+		    }
+		}
+	    }
+
+	  if (associated_impl_trait != nullptr)
+	    {
+	      associated_impl_trait->setup_associated_types (binding, bound);
+	    }
+	}
+    }
+
+  return true;
+}
+
+} // namespace TyTy
+} // namespace Rust
diff --git a/gcc/rust/typecheck/rust-tyty-subst.h b/gcc/rust/typecheck/rust-tyty-subst.h
new file mode 100644
index 00000000000..4d09a3013e7
--- /dev/null
+++ b/gcc/rust/typecheck/rust-tyty-subst.h
@@ -0,0 +1,316 @@
+// Copyright (C) 2020-2022 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC is free software; you can redistribute it and/or modify it under
+// the terms of the GNU General Public License as published by the Free
+// Software Foundation; either version 3, or (at your option) any later
+// version.
+
+// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY; without even the implied warranty of MERCHANTABILITY or
+// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+// for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef RUST_TYTY_SUBST_H
+#define RUST_TYTY_SUBST_H
+
+#include "rust-system.h"
+#include "rust-location.h"
+#include "rust-hir-full-decls.h"
+#include "rust-tyty-bounds.h"
+
+namespace Rust {
+namespace TyTy {
+
+class BaseType;
+class ParamType;
+class SubstitutionArgumentMappings;
+class SubstitutionParamMapping
+{
+public:
+  SubstitutionParamMapping (const HIR::TypeParam &generic, ParamType *param);
+
+  SubstitutionParamMapping (const SubstitutionParamMapping &other);
+
+  std::string as_string () const;
+
+  bool fill_param_ty (SubstitutionArgumentMappings &subst_mappings,
+		      Location locus);
+
+  SubstitutionParamMapping clone () const;
+
+  ParamType *get_param_ty ();
+
+  const ParamType *get_param_ty () const;
+
+  const HIR::TypeParam &get_generic_param ();
+
+  // this is used for the backend to override the HirId ref of the param to
+  // what the concrete type is for the rest of the context
+  void override_context ();
+
+  bool needs_substitution () const;
+
+  Location get_param_locus () const;
+
+  bool param_has_default_ty () const;
+
+  BaseType *get_default_ty () const;
+
+  bool need_substitution () const;
+
+private:
+  const HIR::TypeParam &generic;
+  ParamType *param;
+};
+
+class SubstitutionArg
+{
+public:
+  SubstitutionArg (const SubstitutionParamMapping *param, BaseType *argument);
+
+  // FIXME
+  // the copy constructors need removed - they are unsafe see
+  // TypeBoundPredicate
+  SubstitutionArg (const SubstitutionArg &other);
+
+  SubstitutionArg &operator= (const SubstitutionArg &other);
+
+  BaseType *get_tyty ();
+
+  const BaseType *get_tyty () const;
+
+  const SubstitutionParamMapping *get_param_mapping () const;
+
+  static SubstitutionArg error ();
+
+  bool is_error () const;
+
+  bool is_conrete () const;
+
+  std::string as_string () const;
+
+private:
+  const SubstitutionParamMapping *param;
+  BaseType *argument;
+};
+
+typedef std::function<void (const ParamType &, const SubstitutionArg &)>
+  ParamSubstCb;
+class SubstitutionArgumentMappings
+{
+public:
+  SubstitutionArgumentMappings (std::vector<SubstitutionArg> mappings,
+				std::map<std::string, BaseType *> binding_args,
+				Location locus,
+				ParamSubstCb param_subst_cb = nullptr,
+				bool trait_item_flag = false);
+
+  SubstitutionArgumentMappings (const SubstitutionArgumentMappings &other);
+  SubstitutionArgumentMappings &
+  operator= (const SubstitutionArgumentMappings &other);
+
+  SubstitutionArgumentMappings (SubstitutionArgumentMappings &&other) = default;
+  SubstitutionArgumentMappings &operator= (SubstitutionArgumentMappings &&other)
+    = default;
+
+  static SubstitutionArgumentMappings error ();
+
+  bool is_error () const;
+
+  bool get_argument_for_symbol (const ParamType *param_to_find,
+				SubstitutionArg *argument);
+
+  bool get_argument_at (size_t index, SubstitutionArg *argument);
+
+  // is_concrete means if the used args is non error, ie: non empty this will
+  // verify if actual real types have been put in place of are they still
+  // ParamTy
+  bool is_concrete () const;
+
+  Location get_locus () const;
+
+  size_t size () const;
+
+  bool is_empty () const;
+
+  std::vector<SubstitutionArg> &get_mappings ();
+
+  const std::vector<SubstitutionArg> &get_mappings () const;
+
+  std::map<std::string, BaseType *> &get_binding_args ();
+
+  const std::map<std::string, BaseType *> &get_binding_args () const;
+
+  std::string as_string () const;
+
+  void on_param_subst (const ParamType &p, const SubstitutionArg &a) const;
+
+  ParamSubstCb get_subst_cb () const;
+
+  bool trait_item_mode () const;
+
+private:
+  std::vector<SubstitutionArg> mappings;
+  std::map<std::string, BaseType *> binding_args;
+  Location locus;
+  ParamSubstCb param_subst_cb;
+  bool trait_item_flag;
+};
+
+class SubstitutionRef
+{
+public:
+  SubstitutionRef (std::vector<SubstitutionParamMapping> substitutions,
+		   SubstitutionArgumentMappings arguments);
+
+  bool has_substitutions () const;
+
+  std::string subst_as_string () const;
+
+  bool supports_associated_bindings () const;
+
+  // this is overridden in TypeBoundPredicate
+  // which support bindings we don't add them directly to the SubstitutionRef
+  // base class because this class represents the fn<X: Foo, Y: Bar>. The only
+  // construct which supports associated types
+  virtual size_t get_num_associated_bindings () const;
+
+  // this is overridden in TypeBoundPredicate
+  virtual TypeBoundPredicateItem
+  lookup_associated_type (const std::string &search);
+
+  size_t get_num_substitutions () const;
+
+  std::vector<SubstitutionParamMapping> &get_substs ();
+
+  const std::vector<SubstitutionParamMapping> &get_substs () const;
+
+  std::vector<SubstitutionParamMapping> clone_substs () const;
+
+  void override_context ();
+
+  bool needs_substitution () const;
+
+  bool was_substituted () const;
+
+  SubstitutionArgumentMappings get_substitution_arguments () const;
+
+  // this is the count of type params that are not substituted fuly
+  size_t num_required_substitutions () const;
+
+  // this is the count of type params that need substituted taking into account
+  // possible defaults
+  size_t min_required_substitutions () const;
+
+  // We are trying to subst <i32, f32> into Struct Foo<X,Y> {}
+  // in the case of Foo<i32,f32>{...}
+  //
+  // the substitions we have here define X,Y but the arguments have no bindings
+  // so its a matter of ordering
+  SubstitutionArgumentMappings
+  get_mappings_from_generic_args (HIR::GenericArgs &args);
+
+  // Recursive substitutions
+  // Foo <A,B> { a:A, b: B}; Bar <X,Y,Z>{a:X, b: Foo<Y,Z>}
+  //
+  // we have bindings for X Y Z and need to propagate the binding Y,Z into Foo
+  // Which binds to A,B
+  SubstitutionArgumentMappings
+  adjust_mappings_for_this (SubstitutionArgumentMappings &mappings);
+
+  // Are the mappings here actually bound to this type. For example imagine the
+  // case:
+  //
+  // struct Foo<T>(T);
+  // impl<T> Foo<T> {
+  //   fn test(self) { ... }
+  // }
+  //
+  // In this case we have a generic ADT of Foo and an impl block of a generic T
+  // on Foo for the Self type. When we it comes to path resolution we can have:
+  //
+  // Foo::<i32>::test()
+  //
+  // This means the first segment of Foo::<i32> returns the ADT Foo<i32> not the
+  // Self ADT bound to the T from the impl block. This means when it comes to
+  // the next segment of test which resolves to the function we need to check
+  // wether the arguments in the struct definition of foo can be bound here
+  // before substituting the previous segments type here. This functions acts as
+  // a guard for the solve_mappings_from_receiver_for_self to handle the case
+  // where arguments are not bound. This is important for this next case:
+  //
+  // struct Baz<A, B>(A, B);
+  // impl Baz<i32, f32> {
+  //   fn test<X>(a: X) -> X {
+  //       a
+  //   }
+  // }
+  //
+  // In this case Baz has been already substituted for the impl's Self to become
+  // ADT<i32, f32> so that the function test only has 1 generic argument of X.
+  // The path for this will be:
+  //
+  // Baz::test::<_>(123)
+  //
+  // So the first segment here will be Baz<_, _> to try and infer the arguments
+  // which will be taken from the impl's Self type in this case since it is
+  // already substituted and like the previous case the check to see if we need
+  // to inherit the previous segments generic arguments takes place but the
+  // generic arguments are not bound to this type as they have already been
+  // substituted.
+  //
+  // Its important to remember from the first example the FnType actually looks
+  // like:
+  //
+  // fn <T>test(self :Foo<T>(T))
+  //
+  // As the generic parameters are "bound" to each of the items in the impl
+  // block. So this check is about wether the arguments we have here can
+  // actually be bound to this type.
+  bool are_mappings_bound (SubstitutionArgumentMappings &mappings);
+
+  // struct Foo<A, B>(A, B);
+  //
+  // impl<T> Foo<T, f32>;
+  //     -> fn test<X>(self, a: X) -> X
+  //
+  // We might invoke this via:
+  //
+  // a = Foo(123, 456f32);
+  // b = a.test::<bool>(false);
+  //
+  // we need to figure out relevant generic arguemts for self to apply to the
+  // fntype
+  SubstitutionArgumentMappings solve_mappings_from_receiver_for_self (
+    SubstitutionArgumentMappings &mappings) const;
+
+  // TODO comment
+  SubstitutionArgumentMappings
+  solve_missing_mappings_from_this (SubstitutionRef &ref, SubstitutionRef &to);
+
+  // TODO comment
+  BaseType *infer_substitions (Location locus);
+
+  // TODO comment
+  bool monomorphize ();
+
+  // TODO comment
+  virtual BaseType *handle_substitions (SubstitutionArgumentMappings mappings)
+    = 0;
+
+  SubstitutionArgumentMappings get_used_arguments () const;
+
+protected:
+  std::vector<SubstitutionParamMapping> substitutions;
+  SubstitutionArgumentMappings used_arguments;
+};
+
+} // namespace TyTy
+} // namespace Rust
+#endif // RUST_TYTY_SUBST_H
diff --git a/gcc/rust/typecheck/rust-tyty.cc b/gcc/rust/typecheck/rust-tyty.cc
index 55a8123ce87..b45bd99b1bd 100644
--- a/gcc/rust/typecheck/rust-tyty.cc
+++ b/gcc/rust/typecheck/rust-tyty.cc
@@ -514,472 +514,6 @@ StructFieldType::monomorphized_clone () const
 			      get_field_type ()->monomorphized_clone (), locus);
 }
 
-bool
-SubstitutionParamMapping::need_substitution () const
-{
-  if (!param->can_resolve ())
-    return true;
-
-  auto resolved = param->resolve ();
-  return !resolved->is_concrete ();
-}
-
-bool
-SubstitutionParamMapping::fill_param_ty (
-  SubstitutionArgumentMappings &subst_mappings, Location locus)
-{
-  SubstitutionArg arg = SubstitutionArg::error ();
-  bool ok = subst_mappings.get_argument_for_symbol (get_param_ty (), &arg);
-  if (!ok)
-    return true;
-
-  TyTy::BaseType &type = *arg.get_tyty ();
-  if (type.get_kind () == TyTy::TypeKind::INFER)
-    {
-      type.inherit_bounds (*param);
-    }
-  else
-    {
-      if (!param->bounds_compatible (type, locus, true))
-	return false;
-    }
-
-  if (type.get_kind () == TypeKind::PARAM)
-    {
-      // delete param;
-      param = static_cast<ParamType *> (type.clone ());
-    }
-  else
-    {
-      // check the substitution is compatible with bounds
-      if (!param->bounds_compatible (type, locus, true))
-	return false;
-
-      // recursively pass this down to all HRTB's
-      for (auto &bound : param->get_specified_bounds ())
-	bound.handle_substitions (subst_mappings);
-
-      param->set_ty_ref (type.get_ref ());
-    }
-
-  return true;
-}
-
-void
-SubstitutionParamMapping::override_context ()
-{
-  if (!param->can_resolve ())
-    return;
-
-  auto mappings = Analysis::Mappings::get ();
-  auto context = Resolver::TypeCheckContext::get ();
-
-  context->insert_type (Analysis::NodeMapping (mappings->get_current_crate (),
-					       UNKNOWN_NODEID,
-					       param->get_ref (),
-					       UNKNOWN_LOCAL_DEFID),
-			param->resolve ());
-}
-
-SubstitutionArgumentMappings
-SubstitutionRef::get_mappings_from_generic_args (HIR::GenericArgs &args)
-{
-  std::map<std::string, BaseType *> binding_arguments;
-  if (args.get_binding_args ().size () > 0)
-    {
-      if (supports_associated_bindings ())
-	{
-	  if (args.get_binding_args ().size () > get_num_associated_bindings ())
-	    {
-	      RichLocation r (args.get_locus ());
-
-	      rust_error_at (r,
-			     "generic item takes at most %lu type binding "
-			     "arguments but %lu were supplied",
-			     (unsigned long) get_num_associated_bindings (),
-			     (unsigned long) args.get_binding_args ().size ());
-	      return SubstitutionArgumentMappings::error ();
-	    }
-
-	  for (auto &binding : args.get_binding_args ())
-	    {
-	      BaseType *resolved
-		= Resolver::TypeCheckType::Resolve (binding.get_type ().get ());
-	      if (resolved == nullptr
-		  || resolved->get_kind () == TyTy::TypeKind::ERROR)
-		{
-		  rust_error_at (binding.get_locus (),
-				 "failed to resolve type arguments");
-		  return SubstitutionArgumentMappings::error ();
-		}
-
-	      // resolve to relevant binding
-	      auto binding_item
-		= lookup_associated_type (binding.get_identifier ());
-	      if (binding_item.is_error ())
-		{
-		  rust_error_at (binding.get_locus (),
-				 "unknown associated type binding: %s",
-				 binding.get_identifier ().c_str ());
-		  return SubstitutionArgumentMappings::error ();
-		}
-
-	      binding_arguments[binding.get_identifier ()] = resolved;
-	    }
-	}
-      else
-	{
-	  RichLocation r (args.get_locus ());
-	  for (auto &binding : args.get_binding_args ())
-	    r.add_range (binding.get_locus ());
-
-	  rust_error_at (r, "associated type bindings are not allowed here");
-	  return SubstitutionArgumentMappings::error ();
-	}
-    }
-
-  // for inherited arguments
-  size_t offs = used_arguments.size ();
-  if (args.get_type_args ().size () + offs > substitutions.size ())
-    {
-      RichLocation r (args.get_locus ());
-      r.add_range (substitutions.front ().get_param_locus ());
-
-      rust_error_at (
-	r,
-	"generic item takes at most %lu type arguments but %lu were supplied",
-	(unsigned long) substitutions.size (),
-	(unsigned long) args.get_type_args ().size ());
-      return SubstitutionArgumentMappings::error ();
-    }
-
-  if (args.get_type_args ().size () + offs < min_required_substitutions ())
-    {
-      RichLocation r (args.get_locus ());
-      r.add_range (substitutions.front ().get_param_locus ());
-
-      rust_error_at (
-	r,
-	"generic item takes at least %lu type arguments but %lu were supplied",
-	(unsigned long) (min_required_substitutions () - offs),
-	(unsigned long) args.get_type_args ().size ());
-      return SubstitutionArgumentMappings::error ();
-    }
-
-  std::vector<SubstitutionArg> mappings = used_arguments.get_mappings ();
-  for (auto &arg : args.get_type_args ())
-    {
-      BaseType *resolved = Resolver::TypeCheckType::Resolve (arg.get ());
-      if (resolved == nullptr || resolved->get_kind () == TyTy::TypeKind::ERROR)
-	{
-	  rust_error_at (args.get_locus (), "failed to resolve type arguments");
-	  return SubstitutionArgumentMappings::error ();
-	}
-
-      SubstitutionArg subst_arg (&substitutions.at (offs), resolved);
-      offs++;
-      mappings.push_back (std::move (subst_arg));
-    }
-
-  // we must need to fill out defaults
-  size_t left_over
-    = num_required_substitutions () - min_required_substitutions ();
-  if (left_over > 0)
-    {
-      for (size_t offs = mappings.size (); offs < substitutions.size (); offs++)
-	{
-	  SubstitutionParamMapping &param = substitutions.at (offs);
-	  rust_assert (param.param_has_default_ty ());
-
-	  BaseType *resolved = param.get_default_ty ();
-	  if (resolved->get_kind () == TypeKind::ERROR)
-	    return SubstitutionArgumentMappings::error ();
-
-	  // this resolved default might already contain default parameters
-	  if (resolved->contains_type_parameters ())
-	    {
-	      SubstitutionArgumentMappings intermediate (mappings,
-							 binding_arguments,
-							 args.get_locus ());
-	      resolved = Resolver::SubstMapperInternal::Resolve (resolved,
-								 intermediate);
-
-	      if (resolved->get_kind () == TypeKind::ERROR)
-		return SubstitutionArgumentMappings::error ();
-	    }
-
-	  SubstitutionArg subst_arg (&param, resolved);
-	  mappings.push_back (std::move (subst_arg));
-	}
-    }
-
-  return SubstitutionArgumentMappings (mappings, binding_arguments,
-				       args.get_locus ());
-}
-
-BaseType *
-SubstitutionRef::infer_substitions (Location locus)
-{
-  std::vector<SubstitutionArg> args;
-  std::map<std::string, BaseType *> argument_mappings;
-  for (auto &p : get_substs ())
-    {
-      if (p.needs_substitution ())
-	{
-	  const std::string &symbol = p.get_param_ty ()->get_symbol ();
-	  auto it = argument_mappings.find (symbol);
-	  bool have_mapping = it != argument_mappings.end ();
-
-	  if (have_mapping)
-	    {
-	      args.push_back (SubstitutionArg (&p, it->second));
-	    }
-	  else
-	    {
-	      TyVar infer_var = TyVar::get_implicit_infer_var (locus);
-	      args.push_back (SubstitutionArg (&p, infer_var.get_tyty ()));
-	      argument_mappings[symbol] = infer_var.get_tyty ();
-	    }
-	}
-      else
-	{
-	  args.push_back (SubstitutionArg (&p, p.get_param_ty ()->resolve ()));
-	}
-    }
-
-  // FIXME do we need to add inference variables to all the possible bindings?
-  // it might just lead to inference variable hell not 100% sure if rustc does
-  // this i think the language might needs this to be explicitly set
-
-  SubstitutionArgumentMappings infer_arguments (std::move (args),
-						{} /* binding_arguments */,
-						locus);
-  return handle_substitions (std::move (infer_arguments));
-}
-
-SubstitutionArgumentMappings
-SubstitutionRef::adjust_mappings_for_this (
-  SubstitutionArgumentMappings &mappings)
-{
-  std::vector<SubstitutionArg> resolved_mappings;
-  for (size_t i = 0; i < substitutions.size (); i++)
-    {
-      auto &subst = substitutions.at (i);
-
-      SubstitutionArg arg = SubstitutionArg::error ();
-      if (mappings.size () == substitutions.size ())
-	{
-	  mappings.get_argument_at (i, &arg);
-	}
-      else
-	{
-	  if (subst.needs_substitution ())
-	    {
-	      // get from passed in mappings
-	      mappings.get_argument_for_symbol (subst.get_param_ty (), &arg);
-	    }
-	  else
-	    {
-	      // we should already have this somewhere
-	      used_arguments.get_argument_for_symbol (subst.get_param_ty (),
-						      &arg);
-	    }
-	}
-
-      bool ok = !arg.is_error ();
-      if (ok)
-	{
-	  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_binding_args (),
-				       mappings.get_locus (),
-				       mappings.get_subst_cb (),
-				       mappings.trait_item_mode ());
-}
-
-bool
-SubstitutionRef::are_mappings_bound (SubstitutionArgumentMappings &mappings)
-{
-  std::vector<SubstitutionArg> resolved_mappings;
-  for (size_t i = 0; i < substitutions.size (); i++)
-    {
-      auto &subst = substitutions.at (i);
-
-      SubstitutionArg arg = SubstitutionArg::error ();
-      if (mappings.size () == substitutions.size ())
-	{
-	  mappings.get_argument_at (i, &arg);
-	}
-      else
-	{
-	  if (subst.needs_substitution ())
-	    {
-	      // get from passed in mappings
-	      mappings.get_argument_for_symbol (subst.get_param_ty (), &arg);
-	    }
-	  else
-	    {
-	      // we should already have this somewhere
-	      used_arguments.get_argument_for_symbol (subst.get_param_ty (),
-						      &arg);
-	    }
-	}
-
-      bool ok = !arg.is_error ();
-      if (ok)
-	{
-	  SubstitutionArg adjusted (&subst, arg.get_tyty ());
-	  resolved_mappings.push_back (std::move (adjusted));
-	}
-    }
-
-  return !resolved_mappings.empty ();
-}
-
-// this function assumes that the mappings being passed are for the same type as
-// this new substitution reference so ordering matters here
-SubstitutionArgumentMappings
-SubstitutionRef::solve_mappings_from_receiver_for_self (
-  SubstitutionArgumentMappings &mappings) const
-{
-  std::vector<SubstitutionArg> resolved_mappings;
-
-  rust_assert (mappings.size () == get_num_substitutions ());
-  for (size_t i = 0; i < get_num_substitutions (); i++)
-    {
-      const SubstitutionParamMapping &param_mapping = substitutions.at (i);
-      SubstitutionArg &arg = mappings.get_mappings ().at (i);
-
-      if (param_mapping.needs_substitution ())
-	{
-	  SubstitutionArg adjusted (&param_mapping, arg.get_tyty ());
-	  resolved_mappings.push_back (std::move (adjusted));
-	}
-    }
-
-  return SubstitutionArgumentMappings (resolved_mappings,
-				       mappings.get_binding_args (),
-				       mappings.get_locus ());
-}
-
-SubstitutionArgumentMappings
-SubstitutionRef::solve_missing_mappings_from_this (SubstitutionRef &ref,
-						   SubstitutionRef &to)
-{
-  rust_assert (!ref.needs_substitution ());
-  rust_assert (needs_substitution ());
-  rust_assert (get_num_substitutions () == ref.get_num_substitutions ());
-
-  Location locus = used_arguments.get_locus ();
-  std::vector<SubstitutionArg> resolved_mappings;
-
-  std::map<HirId, std::pair<ParamType *, BaseType *>> substs;
-  for (size_t i = 0; i < get_num_substitutions (); i++)
-    {
-      SubstitutionParamMapping &a = substitutions.at (i);
-      SubstitutionParamMapping &b = ref.substitutions.at (i);
-
-      if (a.need_substitution ())
-	{
-	  const BaseType *root = a.get_param_ty ()->resolve ()->get_root ();
-	  rust_assert (root->get_kind () == TyTy::TypeKind::PARAM);
-	  const ParamType *p = static_cast<const TyTy::ParamType *> (root);
-
-	  substs[p->get_ty_ref ()] = {static_cast<ParamType *> (p->clone ()),
-				      b.get_param_ty ()->resolve ()};
-	}
-    }
-
-  for (auto it = substs.begin (); it != substs.end (); it++)
-    {
-      HirId param_id = it->first;
-      BaseType *arg = it->second.second;
-
-      const SubstitutionParamMapping *associate_param = nullptr;
-      for (SubstitutionParamMapping &p : to.substitutions)
-	{
-	  if (p.get_param_ty ()->get_ty_ref () == param_id)
-	    {
-	      associate_param = &p;
-	      break;
-	    }
-	}
-
-      rust_assert (associate_param != nullptr);
-      SubstitutionArg argument (associate_param, arg);
-      resolved_mappings.push_back (std::move (argument));
-    }
-
-  return SubstitutionArgumentMappings (resolved_mappings, {}, locus);
-}
-
-bool
-SubstitutionRef::monomorphize ()
-{
-  auto context = Resolver::TypeCheckContext::get ();
-  for (const auto &subst : get_substs ())
-    {
-      const TyTy::ParamType *pty = subst.get_param_ty ();
-
-      if (!pty->can_resolve ())
-	continue;
-
-      const TyTy::BaseType *binding = pty->resolve ();
-      if (binding->get_kind () == TyTy::TypeKind::PARAM)
-	continue;
-
-      for (const auto &bound : pty->get_specified_bounds ())
-	{
-	  const Resolver::TraitReference *specified_bound_ref = bound.get ();
-
-	  // setup any associated type mappings for the specified bonds and this
-	  // type
-	  auto candidates = Resolver::TypeBoundsProbe::Probe (binding);
-
-	  Resolver::AssociatedImplTrait *associated_impl_trait = nullptr;
-	  for (auto &probed_bound : candidates)
-	    {
-	      const Resolver::TraitReference *bound_trait_ref
-		= probed_bound.first;
-	      const HIR::ImplBlock *associated_impl = probed_bound.second;
-
-	      HirId impl_block_id
-		= associated_impl->get_mappings ().get_hirid ();
-	      Resolver::AssociatedImplTrait *associated = nullptr;
-	      bool found_impl_trait
-		= context->lookup_associated_trait_impl (impl_block_id,
-							 &associated);
-	      if (found_impl_trait)
-		{
-		  bool found_trait
-		    = specified_bound_ref->is_equal (*bound_trait_ref);
-		  bool found_self
-		    = associated->get_self ()->can_eq (binding, false);
-		  if (found_trait && found_self)
-		    {
-		      associated_impl_trait = associated;
-		      break;
-		    }
-		}
-	    }
-
-	  if (associated_impl_trait != nullptr)
-	    {
-	      associated_impl_trait->setup_associated_types (binding, bound);
-	    }
-	}
-    }
-
-  return true;
-}
-
 void
 ADTType::accept_vis (TyVisitor &vis)
 {
diff --git a/gcc/rust/typecheck/rust-tyty.h b/gcc/rust/typecheck/rust-tyty.h
index a8bdf6f3a15..cb30a60ae96 100644
--- a/gcc/rust/typecheck/rust-tyty.h
+++ b/gcc/rust/typecheck/rust-tyty.h
@@ -27,6 +27,7 @@
 #include "rust-identifier.h"
 #include "rust-tyty-bounds.h"
 #include "rust-tyty-util.h"
+#include "rust-tyty-subst.h"
 
 namespace Rust {
 
@@ -462,469 +463,6 @@ private:
   std::vector<TyVar> fields;
 };
 
-class SubstitutionParamMapping
-{
-public:
-  SubstitutionParamMapping (const HIR::TypeParam &generic, ParamType *param)
-    : generic (generic), param (param)
-  {}
-
-  SubstitutionParamMapping (const SubstitutionParamMapping &other)
-    : generic (other.generic), param (other.param)
-  {}
-
-  std::string as_string () const
-  {
-    if (param == nullptr)
-      return "nullptr";
-
-    return param->get_name ();
-  }
-
-  bool fill_param_ty (SubstitutionArgumentMappings &subst_mappings,
-		      Location locus);
-
-  SubstitutionParamMapping clone () const
-  {
-    return SubstitutionParamMapping (generic, static_cast<ParamType *> (
-						param->clone ()));
-  }
-
-  ParamType *get_param_ty () { return param; }
-
-  const ParamType *get_param_ty () const { return param; }
-
-  const HIR::TypeParam &get_generic_param () { return generic; };
-
-  // this is used for the backend to override the HirId ref of the param to
-  // what the concrete type is for the rest of the context
-  void override_context ();
-
-  bool needs_substitution () const
-  {
-    return !(get_param_ty ()->is_concrete ());
-  }
-
-  Location get_param_locus () const { return generic.get_locus (); }
-
-  bool param_has_default_ty () const { return generic.has_type (); }
-
-  BaseType *get_default_ty () const
-  {
-    TyVar var (generic.get_type_mappings ().get_hirid ());
-    return var.get_tyty ();
-  }
-
-  bool need_substitution () const;
-
-private:
-  const HIR::TypeParam &generic;
-  ParamType *param;
-};
-
-class SubstitutionArg
-{
-public:
-  SubstitutionArg (const SubstitutionParamMapping *param, BaseType *argument)
-    : param (param), argument (argument)
-  {}
-
-  // FIXME
-  // the copy constructors need removed - they are unsafe see
-  // TypeBoundPredicate
-  SubstitutionArg (const SubstitutionArg &other)
-    : param (other.param), argument (other.argument)
-  {}
-
-  SubstitutionArg &operator= (const SubstitutionArg &other)
-  {
-    param = other.param;
-    argument = other.argument;
-    return *this;
-  }
-
-  BaseType *get_tyty () { return argument; }
-
-  const BaseType *get_tyty () const { return argument; }
-
-  const SubstitutionParamMapping *get_param_mapping () const { return param; }
-
-  static SubstitutionArg error () { return SubstitutionArg (nullptr, nullptr); }
-
-  bool is_error () const { return param == nullptr || argument == nullptr; }
-
-  bool is_conrete () const
-  {
-    if (argument != nullptr)
-      return true;
-
-    if (argument->get_kind () == TyTy::TypeKind::PARAM)
-      return false;
-
-    return argument->is_concrete ();
-  }
-
-  std::string as_string () const
-  {
-    return param->as_string ()
-	   + (argument != nullptr ? ":" + argument->as_string () : "");
-  }
-
-private:
-  const SubstitutionParamMapping *param;
-  BaseType *argument;
-};
-
-typedef std::function<void (const ParamType &, const SubstitutionArg &)>
-  ParamSubstCb;
-class SubstitutionArgumentMappings
-{
-public:
-  SubstitutionArgumentMappings (std::vector<SubstitutionArg> mappings,
-				std::map<std::string, BaseType *> binding_args,
-				Location locus,
-				ParamSubstCb param_subst_cb = nullptr,
-				bool trait_item_flag = false)
-    : mappings (mappings), binding_args (binding_args), locus (locus),
-      param_subst_cb (param_subst_cb), trait_item_flag (trait_item_flag)
-  {}
-
-  SubstitutionArgumentMappings (const SubstitutionArgumentMappings &other)
-    : mappings (other.mappings), binding_args (other.binding_args),
-      locus (other.locus), param_subst_cb (other.param_subst_cb),
-      trait_item_flag (other.trait_item_flag)
-  {}
-
-  SubstitutionArgumentMappings &
-  operator= (const SubstitutionArgumentMappings &other)
-  {
-    mappings = other.mappings;
-    binding_args = other.binding_args;
-    locus = other.locus;
-    param_subst_cb = other.param_subst_cb;
-    trait_item_flag = other.trait_item_flag;
-
-    return *this;
-  }
-
-  SubstitutionArgumentMappings (SubstitutionArgumentMappings &&other) = default;
-  SubstitutionArgumentMappings &operator= (SubstitutionArgumentMappings &&other)
-    = default;
-
-  static SubstitutionArgumentMappings error ()
-  {
-    return SubstitutionArgumentMappings ({}, {}, Location (), nullptr, false);
-  }
-
-  bool is_error () const { return mappings.size () == 0; }
-
-  bool get_argument_for_symbol (const ParamType *param_to_find,
-				SubstitutionArg *argument)
-  {
-    for (auto &mapping : mappings)
-      {
-	const SubstitutionParamMapping *param = mapping.get_param_mapping ();
-	const ParamType *p = param->get_param_ty ();
-
-	if (p->get_symbol ().compare (param_to_find->get_symbol ()) == 0)
-	  {
-	    *argument = mapping;
-	    return true;
-	  }
-      }
-    return false;
-  }
-
-  bool get_argument_at (size_t index, SubstitutionArg *argument)
-  {
-    if (index > mappings.size ())
-      return false;
-
-    *argument = mappings.at (index);
-    return true;
-  }
-
-  // is_concrete means if the used args is non error, ie: non empty this will
-  // verify if actual real types have been put in place of are they still
-  // ParamTy
-  bool is_concrete () const
-  {
-    for (auto &mapping : mappings)
-      {
-	if (!mapping.is_conrete ())
-	  return false;
-      }
-    return true;
-  }
-
-  Location get_locus () const { return locus; }
-
-  size_t size () const { return mappings.size (); }
-
-  bool is_empty () const { return size () == 0; }
-
-  std::vector<SubstitutionArg> &get_mappings () { return mappings; }
-
-  const std::vector<SubstitutionArg> &get_mappings () const { return mappings; }
-
-  std::map<std::string, BaseType *> &get_binding_args ()
-  {
-    return binding_args;
-  }
-
-  const std::map<std::string, BaseType *> &get_binding_args () const
-  {
-    return binding_args;
-  }
-
-  std::string as_string () const
-  {
-    std::string buffer;
-    for (auto &mapping : mappings)
-      {
-	buffer += mapping.as_string () + ", ";
-      }
-    return "<" + buffer + ">";
-  }
-
-  void on_param_subst (const ParamType &p, const SubstitutionArg &a) const
-  {
-    if (param_subst_cb == nullptr)
-      return;
-
-    param_subst_cb (p, a);
-  }
-
-  ParamSubstCb get_subst_cb () const { return param_subst_cb; }
-
-  bool trait_item_mode () const { return trait_item_flag; }
-
-private:
-  std::vector<SubstitutionArg> mappings;
-  std::map<std::string, BaseType *> binding_args;
-  Location locus;
-  ParamSubstCb param_subst_cb;
-  bool trait_item_flag;
-};
-
-class SubstitutionRef
-{
-public:
-  SubstitutionRef (std::vector<SubstitutionParamMapping> substitutions,
-		   SubstitutionArgumentMappings arguments)
-    : substitutions (substitutions), used_arguments (arguments)
-  {}
-
-  bool has_substitutions () const { return substitutions.size () > 0; }
-
-  std::string subst_as_string () const
-  {
-    std::string buffer;
-    for (size_t i = 0; i < substitutions.size (); i++)
-      {
-	const SubstitutionParamMapping &sub = substitutions.at (i);
-	buffer += sub.as_string ();
-
-	if ((i + 1) < substitutions.size ())
-	  buffer += ", ";
-      }
-
-    return buffer.empty () ? "" : "<" + buffer + ">";
-  }
-
-  bool supports_associated_bindings () const
-  {
-    return get_num_associated_bindings () > 0;
-  }
-
-  // this is overridden in TypeBoundPredicate
-  // which support bindings we don't add them directly to the SubstitutionRef
-  // base class because this class represents the fn<X: Foo, Y: Bar>. The only
-  // construct which supports associated types
-  virtual size_t get_num_associated_bindings () const { return 0; }
-
-  // this is overridden in TypeBoundPredicate
-  virtual TypeBoundPredicateItem
-  lookup_associated_type (const std::string &search)
-  {
-    return TypeBoundPredicateItem::error ();
-  }
-
-  size_t get_num_substitutions () const { return substitutions.size (); }
-
-  std::vector<SubstitutionParamMapping> &get_substs () { return substitutions; }
-
-  const std::vector<SubstitutionParamMapping> &get_substs () const
-  {
-    return substitutions;
-  }
-
-  std::vector<SubstitutionParamMapping> clone_substs () const
-  {
-    std::vector<SubstitutionParamMapping> clone;
-
-    for (auto &sub : substitutions)
-      clone.push_back (sub.clone ());
-
-    return clone;
-  }
-
-  void override_context ()
-  {
-    for (auto &sub : substitutions)
-      {
-	sub.override_context ();
-      }
-  }
-
-  bool needs_substitution () const
-  {
-    for (auto &sub : substitutions)
-      {
-	if (sub.need_substitution ())
-	  return true;
-      }
-    return false;
-  }
-
-  bool was_substituted () const { return !needs_substitution (); }
-
-  SubstitutionArgumentMappings get_substitution_arguments () const
-  {
-    return used_arguments;
-  }
-
-  // this is the count of type params that are not substituted fuly
-  size_t num_required_substitutions () const
-  {
-    size_t n = 0;
-    for (auto &p : substitutions)
-      {
-	if (p.needs_substitution ())
-	  n++;
-      }
-    return n;
-  }
-
-  // this is the count of type params that need substituted taking into account
-  // possible defaults
-  size_t min_required_substitutions () const
-  {
-    size_t n = 0;
-    for (auto &p : substitutions)
-      {
-	if (p.needs_substitution () && !p.param_has_default_ty ())
-	  n++;
-      }
-    return n;
-  }
-
-  // We are trying to subst <i32, f32> into Struct Foo<X,Y> {}
-  // in the case of Foo<i32,f32>{...}
-  //
-  // the substitions we have here define X,Y but the arguments have no bindings
-  // so its a matter of ordering
-  SubstitutionArgumentMappings
-  get_mappings_from_generic_args (HIR::GenericArgs &args);
-
-  // Recursive substitutions
-  // Foo <A,B> { a:A, b: B}; Bar <X,Y,Z>{a:X, b: Foo<Y,Z>}
-  //
-  // we have bindings for X Y Z and need to propagate the binding Y,Z into Foo
-  // Which binds to A,B
-  SubstitutionArgumentMappings
-  adjust_mappings_for_this (SubstitutionArgumentMappings &mappings);
-
-  // Are the mappings here actually bound to this type. For example imagine the
-  // case:
-  //
-  // struct Foo<T>(T);
-  // impl<T> Foo<T> {
-  //   fn test(self) { ... }
-  // }
-  //
-  // In this case we have a generic ADT of Foo and an impl block of a generic T
-  // on Foo for the Self type. When we it comes to path resolution we can have:
-  //
-  // Foo::<i32>::test()
-  //
-  // This means the first segment of Foo::<i32> returns the ADT Foo<i32> not the
-  // Self ADT bound to the T from the impl block. This means when it comes to
-  // the next segment of test which resolves to the function we need to check
-  // wether the arguments in the struct definition of foo can be bound here
-  // before substituting the previous segments type here. This functions acts as
-  // a guard for the solve_mappings_from_receiver_for_self to handle the case
-  // where arguments are not bound. This is important for this next case:
-  //
-  // struct Baz<A, B>(A, B);
-  // impl Baz<i32, f32> {
-  //   fn test<X>(a: X) -> X {
-  //       a
-  //   }
-  // }
-  //
-  // In this case Baz has been already substituted for the impl's Self to become
-  // ADT<i32, f32> so that the function test only has 1 generic argument of X.
-  // The path for this will be:
-  //
-  // Baz::test::<_>(123)
-  //
-  // So the first segment here will be Baz<_, _> to try and infer the arguments
-  // which will be taken from the impl's Self type in this case since it is
-  // already substituted and like the previous case the check to see if we need
-  // to inherit the previous segments generic arguments takes place but the
-  // generic arguments are not bound to this type as they have already been
-  // substituted.
-  //
-  // Its important to remember from the first example the FnType actually looks
-  // like:
-  //
-  // fn <T>test(self :Foo<T>(T))
-  //
-  // As the generic parameters are "bound" to each of the items in the impl
-  // block. So this check is about wether the arguments we have here can
-  // actually be bound to this type.
-  bool are_mappings_bound (SubstitutionArgumentMappings &mappings);
-
-  // struct Foo<A, B>(A, B);
-  //
-  // impl<T> Foo<T, f32>;
-  //     -> fn test<X>(self, a: X) -> X
-  //
-  // We might invoke this via:
-  //
-  // a = Foo(123, 456f32);
-  // b = a.test::<bool>(false);
-  //
-  // we need to figure out relevant generic arguemts for self to apply to the
-  // fntype
-  SubstitutionArgumentMappings solve_mappings_from_receiver_for_self (
-    SubstitutionArgumentMappings &mappings) const;
-
-  // TODO comment
-  SubstitutionArgumentMappings
-  solve_missing_mappings_from_this (SubstitutionRef &ref, SubstitutionRef &to);
-
-  // TODO comment
-  BaseType *infer_substitions (Location locus);
-
-  // TODO comment
-  bool monomorphize ();
-
-  // TODO comment
-  virtual BaseType *handle_substitions (SubstitutionArgumentMappings mappings)
-    = 0;
-
-  SubstitutionArgumentMappings get_used_arguments () const
-  {
-    return used_arguments;
-  }
-
-protected:
-  std::vector<SubstitutionParamMapping> substitutions;
-  SubstitutionArgumentMappings used_arguments;
-};
-
 class TypeBoundPredicate : public SubstitutionRef
 {
 public:
-- 
2.40.0