gccrs: Add Rust type information

Contains abstractions over Rust's types, used when performing the
HIR's type-resolution.

	gcc/rust/
	* typecheck/rust-tyty.cc: New.
	* typecheck/rust-tyty.h: New.

2 files changed, 5418 insertions, 0 deletions

diff --git a/gcc/rust/typecheck/rust-tyty.cc b/gcc/rust/typecheck/rust-tyty.cc
new file mode 100644
index 00000000000..3c2c6786940
--- /dev/null
+++ b/gcc/rust/typecheck/rust-tyty.cc
@@ -0,0 +1,2885 @@
+// 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.h"
+#include "rust-tyty-visitor.h"
+#include "rust-tyty-call.h"
+#include "rust-hir-type-check-expr.h"
+#include "rust-hir-type-check-type.h"
+#include "rust-tyty-rules.h"
+#include "rust-tyty-cmp.h"
+#include "rust-hir-map.h"
+#include "rust-substitution-mapper.h"
+#include "rust-hir-trait-ref.h"
+#include "rust-hir-type-bounds.h"
+
+namespace Rust {
+namespace TyTy {
+
+std::string
+TypeKindFormat::to_string (TypeKind kind)
+{
+  switch (kind)
+    {
+    case TypeKind::INFER:
+      return "Infer";
+
+    case TypeKind::ADT:
+      return "ADT";
+
+    case TypeKind::STR:
+      return "STR";
+
+    case TypeKind::REF:
+      return "REF";
+
+    case TypeKind::POINTER:
+      return "POINTER";
+
+    case TypeKind::PARAM:
+      return "PARAM";
+
+    case TypeKind::ARRAY:
+      return "ARRAY";
+
+    case TypeKind::SLICE:
+      return "SLICE";
+
+    case TypeKind::FNDEF:
+      return "FnDef";
+
+    case TypeKind::FNPTR:
+      return "FnPtr";
+
+    case TypeKind::TUPLE:
+      return "Tuple";
+
+    case TypeKind::BOOL:
+      return "Bool";
+
+    case TypeKind::CHAR:
+      return "Char";
+
+    case TypeKind::INT:
+      return "Int";
+
+    case TypeKind::UINT:
+      return "Uint";
+
+    case TypeKind::FLOAT:
+      return "Float";
+
+    case TypeKind::USIZE:
+      return "Usize";
+
+    case TypeKind::ISIZE:
+      return "Isize";
+
+    case TypeKind::NEVER:
+      return "Never";
+
+    case TypeKind::PLACEHOLDER:
+      return "Placeholder";
+
+    case TypeKind::PROJECTION:
+      return "Projection";
+
+    case TypeKind::DYNAMIC:
+      return "Dynamic";
+
+    case TypeKind::CLOSURE:
+      return "Closure";
+
+    case TypeKind::ERROR:
+      return "ERROR";
+    }
+  gcc_unreachable ();
+}
+
+bool
+is_primitive_type_kind (TypeKind kind)
+{
+  switch (kind)
+    {
+    case TypeKind::BOOL:
+    case TypeKind::CHAR:
+    case TypeKind::INT:
+    case TypeKind::UINT:
+    case TypeKind::ISIZE:
+    case TypeKind::USIZE:
+    case TypeKind::FLOAT:
+    case TypeKind::NEVER:
+    case TypeKind::STR:
+      return true;
+    default:
+      return false;
+    }
+}
+
+bool
+BaseType::satisfies_bound (const TypeBoundPredicate &predicate) const
+{
+  const Resolver::TraitReference *query = predicate.get ();
+  for (auto &bound : specified_bounds)
+    {
+      const Resolver::TraitReference *item = bound.get ();
+      bool found = item->get_mappings ().get_defid ()
+		   == query->get_mappings ().get_defid ();
+      if (found)
+	return true;
+    }
+
+  auto probed = Resolver::TypeBoundsProbe::Probe (this);
+  for (auto &b : probed)
+    {
+      const Resolver::TraitReference *bound = b.first;
+      bool found = bound->get_mappings ().get_defid ()
+		   == query->get_mappings ().get_defid ();
+      if (found)
+	return true;
+    }
+
+  return false;
+}
+
+bool
+BaseType::bounds_compatible (const BaseType &other, Location locus,
+			     bool emit_error) const
+{
+  std::vector<std::reference_wrapper<const TypeBoundPredicate>>
+    unsatisfied_bounds;
+  for (auto &bound : get_specified_bounds ())
+    {
+      if (!other.satisfies_bound (bound))
+	unsatisfied_bounds.push_back (bound);
+    }
+
+  // lets emit a single error for this
+  if (unsatisfied_bounds.size () > 0)
+    {
+      RichLocation r (locus);
+      std::string missing_preds;
+      for (size_t i = 0; i < unsatisfied_bounds.size (); i++)
+	{
+	  const TypeBoundPredicate &pred = unsatisfied_bounds.at (i);
+	  r.add_range (pred.get_locus ());
+	  missing_preds += pred.get_name ();
+
+	  bool have_next = (i + 1) < unsatisfied_bounds.size ();
+	  if (have_next)
+	    missing_preds += ", ";
+	}
+
+      if (emit_error)
+	{
+	  rust_error_at (r,
+			 "bounds not satisfied for %s %<%s%> is not satisfied",
+			 other.get_name ().c_str (), missing_preds.c_str ());
+	  // rust_assert (!emit_error);
+	}
+    }
+
+  return unsatisfied_bounds.size () == 0;
+}
+
+void
+BaseType::inherit_bounds (const BaseType &other)
+{
+  inherit_bounds (other.get_specified_bounds ());
+}
+
+void
+BaseType::inherit_bounds (
+  const std::vector<TyTy::TypeBoundPredicate> &specified_bounds)
+{
+  // FIXME
+  // 1. This needs to union the bounds
+  // 2. Do some checking for trait polarity to ensure compatibility
+  for (auto &bound : specified_bounds)
+    {
+      add_bound (bound);
+    }
+}
+
+const BaseType *
+BaseType::get_root () const
+{
+  // FIXME this needs to be it its own visitor class with a vector adjustments
+  const TyTy::BaseType *root = this;
+  if (get_kind () == TyTy::REF)
+    {
+      const ReferenceType *r = static_cast<const ReferenceType *> (root);
+      root = r->get_base ()->get_root ();
+    }
+  else if (get_kind () == TyTy::POINTER)
+    {
+      const PointerType *r = static_cast<const PointerType *> (root);
+      root = r->get_base ()->get_root ();
+    }
+
+  // these are an unsize
+  else if (get_kind () == TyTy::SLICE)
+    {
+      const SliceType *r = static_cast<const SliceType *> (root);
+      root = r->get_element_type ()->get_root ();
+    }
+  // else if (get_kind () == TyTy::ARRAY)
+  //   {
+  //     const ArrayType *r = static_cast<const ArrayType *> (root);
+  //     root = r->get_element_type ()->get_root ();
+  //   }
+
+  return root;
+}
+
+const BaseType *
+BaseType::destructure () const
+{
+  int recurisve_ops = 0;
+  const BaseType *x = this;
+  while (true)
+    {
+      if (recurisve_ops++ >= rust_max_recursion_depth)
+	{
+	  rust_error_at (
+	    Location (),
+	    "%<recursion depth%> count exceeds limit of %i (use "
+	    "%<frust-max-recursion-depth=%> to increase the limit)",
+	    rust_max_recursion_depth);
+	  return new ErrorType (get_ref ());
+	}
+
+      switch (x->get_kind ())
+	{
+	  case TyTy::TypeKind::PARAM: {
+	    const TyTy::ParamType *p = static_cast<const TyTy::ParamType *> (x);
+	    x = p->resolve ();
+	  }
+	  break;
+
+	  case TyTy::TypeKind::PLACEHOLDER: {
+	    const TyTy::PlaceholderType *p
+	      = static_cast<const TyTy::PlaceholderType *> (x);
+	    rust_assert (p->can_resolve ());
+	    x = p->resolve ();
+	  }
+	  break;
+
+	  case TyTy::TypeKind::PROJECTION: {
+	    const TyTy::ProjectionType *p
+	      = static_cast<const TyTy::ProjectionType *> (x);
+	    x = p->get ();
+	  }
+	  break;
+
+	default:
+	  return x;
+	}
+    }
+
+  return x;
+}
+
+TyVar::TyVar (HirId ref) : ref (ref)
+{
+  // ensure this reference is defined within the context
+  auto context = Resolver::TypeCheckContext::get ();
+  BaseType *lookup = nullptr;
+  bool ok = context->lookup_type (ref, &lookup);
+  rust_assert (ok);
+}
+
+BaseType *
+TyVar::get_tyty () const
+{
+  auto context = Resolver::TypeCheckContext::get ();
+  BaseType *lookup = nullptr;
+  bool ok = context->lookup_type (ref, &lookup);
+  rust_assert (ok);
+  return lookup;
+}
+
+TyVar
+TyVar::get_implicit_infer_var (Location locus)
+{
+  auto mappings = Analysis::Mappings::get ();
+  auto context = Resolver::TypeCheckContext::get ();
+
+  InferType *infer = new InferType (mappings->get_next_hir_id (),
+				    InferType::InferTypeKind::GENERAL, locus);
+  context->insert_type (Analysis::NodeMapping (mappings->get_current_crate (),
+					       UNKNOWN_NODEID,
+					       infer->get_ref (),
+					       UNKNOWN_LOCAL_DEFID),
+			infer);
+  mappings->insert_location (infer->get_ref (), locus);
+
+  return TyVar (infer->get_ref ());
+}
+
+TyVar
+TyVar::subst_covariant_var (TyTy::BaseType *orig, TyTy::BaseType *subst)
+{
+  if (orig->get_kind () != TyTy::TypeKind::PARAM)
+    return TyVar (subst->get_ty_ref ());
+  else if (subst->get_kind () == TyTy::TypeKind::PARAM)
+    {
+      TyTy::ParamType *p = static_cast<TyTy::ParamType *> (subst);
+      if (p->resolve ()->get_kind () == TyTy::TypeKind::PARAM)
+	{
+	  return TyVar (subst->get_ty_ref ());
+	}
+    }
+
+  return TyVar (subst->get_ref ());
+}
+
+TyVar
+TyVar::clone () const
+{
+  TyTy::BaseType *c = get_tyty ()->clone ();
+  return TyVar (c->get_ref ());
+}
+
+TyVar
+TyVar::monomorphized_clone () const
+{
+  auto mappings = Analysis::Mappings::get ();
+  auto context = Resolver::TypeCheckContext::get ();
+
+  // this needs a new hirid
+  TyTy::BaseType *c = get_tyty ()->monomorphized_clone ();
+  c->set_ref (mappings->get_next_hir_id ());
+
+  // insert it
+  context->insert_type (Analysis::NodeMapping (mappings->get_current_crate (),
+					       UNKNOWN_NODEID, c->get_ref (),
+					       UNKNOWN_LOCAL_DEFID),
+			c);
+
+  return TyVar (c->get_ref ());
+}
+
+TyWithLocation::TyWithLocation (BaseType *ty, Location locus)
+  : ty (ty), locus (locus)
+{}
+
+TyWithLocation::TyWithLocation (BaseType *ty) : ty (ty)
+{
+  auto mappings = Analysis::Mappings::get ();
+  locus = mappings->lookup_location (ty->get_ref ());
+}
+
+void
+InferType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+InferType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+InferType::as_string () const
+{
+  switch (infer_kind)
+    {
+    case GENERAL:
+      return "T?";
+    case INTEGRAL:
+      return "<integer>";
+    case FLOAT:
+      return "<float>";
+    }
+  return "<infer::error>";
+}
+
+BaseType *
+InferType::unify (BaseType *other)
+{
+  InferRules r (this);
+  return r.unify (other);
+}
+
+bool
+InferType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  InferCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+BaseType *
+InferType::clone () const
+{
+  // clones for inference variables are special in that they _must_ exist within
+  // the type check context and we must ensure we don't loose the chain
+  // otherwise we will end up in the missing type annotations case
+  //
+  // This means we cannot simply take over the same reference we must generate a
+  // new ref just like the get_implicit_infer_var code then we can setup the
+  // chain of references accordingly to ensure we don't loose the ability to
+  // update the inference variables when we solve the type
+
+  auto mappings = Analysis::Mappings::get ();
+  auto context = Resolver::TypeCheckContext::get ();
+
+  InferType *clone
+    = new InferType (mappings->get_next_hir_id (), get_infer_kind (),
+		     get_ident ().locus, get_combined_refs ());
+
+  context->insert_type (Analysis::NodeMapping (mappings->get_current_crate (),
+					       UNKNOWN_NODEID,
+					       clone->get_ref (),
+					       UNKNOWN_LOCAL_DEFID),
+			clone);
+  mappings->insert_location (clone->get_ref (),
+			     mappings->lookup_location (get_ref ()));
+
+  // setup the chain to reference this
+  clone->append_reference (get_ref ());
+
+  return clone;
+}
+
+BaseType *
+InferType::monomorphized_clone () const
+{
+  return clone ();
+}
+
+bool
+InferType::default_type (BaseType **type) const
+{
+  auto context = Resolver::TypeCheckContext::get ();
+  bool ok = false;
+  switch (infer_kind)
+    {
+    case GENERAL:
+      return false;
+
+      case INTEGRAL: {
+	ok = context->lookup_builtin ("i32", type);
+	rust_assert (ok);
+	return ok;
+      }
+
+      case FLOAT: {
+	ok = context->lookup_builtin ("f64", type);
+	rust_assert (ok);
+	return ok;
+      }
+    }
+  return false;
+}
+
+void
+ErrorType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+ErrorType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+ErrorType::as_string () const
+{
+  return "<tyty::error>";
+}
+
+BaseType *
+ErrorType::unify (BaseType *other)
+{
+  return this;
+}
+
+bool
+ErrorType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  return get_kind () == other->get_kind ();
+}
+
+BaseType *
+ErrorType::clone () const
+{
+  return new ErrorType (get_ref (), get_ty_ref (), get_combined_refs ());
+}
+
+BaseType *
+ErrorType::monomorphized_clone () const
+{
+  return clone ();
+}
+
+std::string
+StructFieldType::as_string () const
+{
+  return name + ":" + get_field_type ()->debug_str ();
+}
+
+bool
+StructFieldType::is_equal (const StructFieldType &other) const
+{
+  bool names_eq = get_name ().compare (other.get_name ()) == 0;
+
+  TyTy::BaseType *o = other.get_field_type ();
+  if (o->get_kind () == TypeKind::PARAM)
+    {
+      ParamType *op = static_cast<ParamType *> (o);
+      o = op->resolve ();
+    }
+
+  bool types_eq = get_field_type ()->is_equal (*o);
+
+  return names_eq && types_eq;
+}
+
+StructFieldType *
+StructFieldType::clone () const
+{
+  return new StructFieldType (get_ref (), get_name (),
+			      get_field_type ()->clone ());
+}
+
+StructFieldType *
+StructFieldType::monomorphized_clone () const
+{
+  return new StructFieldType (get_ref (), get_name (),
+			      get_field_type ()->monomorphized_clone ());
+}
+
+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)
+{
+  if (args.get_binding_args ().size () > 0)
+    {
+      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,
+							 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, args.get_locus ());
+}
+
+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_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_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)
+{
+  vis.visit (*this);
+}
+
+void
+ADTType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+ADTType::as_string () const
+{
+  std::string variants_buffer;
+  for (size_t i = 0; i < number_of_variants (); ++i)
+    {
+      TyTy::VariantDef *variant = variants.at (i);
+      variants_buffer += variant->as_string ();
+      if ((i + 1) < number_of_variants ())
+	variants_buffer += ", ";
+    }
+
+  return identifier + subst_as_string () + "{" + variants_buffer + "}";
+}
+
+BaseType *
+ADTType::unify (BaseType *other)
+{
+  ADTRules r (this);
+  return r.unify (other);
+}
+
+bool
+ADTType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  ADTCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+bool
+ADTType::is_equal (const BaseType &other) const
+{
+  if (get_kind () != other.get_kind ())
+    return false;
+
+  auto other2 = static_cast<const ADTType &> (other);
+  if (get_adt_kind () != other2.get_adt_kind ())
+    return false;
+
+  if (number_of_variants () != other2.number_of_variants ())
+    return false;
+
+  if (has_subsititions_defined () != other2.has_subsititions_defined ())
+    return false;
+
+  if (has_subsititions_defined ())
+    {
+      if (get_num_substitutions () != other2.get_num_substitutions ())
+	return false;
+
+      for (size_t i = 0; i < get_num_substitutions (); i++)
+	{
+	  const SubstitutionParamMapping &a = substitutions.at (i);
+	  const SubstitutionParamMapping &b = other2.substitutions.at (i);
+
+	  const ParamType *aa = a.get_param_ty ();
+	  const ParamType *bb = b.get_param_ty ();
+	  BaseType *aaa = aa->resolve ();
+	  BaseType *bbb = bb->resolve ();
+	  if (!aaa->is_equal (*bbb))
+	    return false;
+	}
+    }
+
+  for (size_t i = 0; i < number_of_variants (); i++)
+    {
+      const TyTy::VariantDef *a = get_variants ().at (i);
+      const TyTy::VariantDef *b = other2.get_variants ().at (i);
+
+      if (!a->is_equal (*b))
+	return false;
+    }
+
+  return true;
+}
+
+BaseType *
+ADTType::clone () const
+{
+  std::vector<VariantDef *> cloned_variants;
+  for (auto &variant : variants)
+    cloned_variants.push_back (variant->clone ());
+
+  return new ADTType (get_ref (), get_ty_ref (), identifier, ident,
+		      get_adt_kind (), cloned_variants, clone_substs (),
+		      get_repr_options (), used_arguments,
+		      get_combined_refs ());
+}
+
+BaseType *
+ADTType::monomorphized_clone () const
+{
+  std::vector<VariantDef *> cloned_variants;
+  for (auto &variant : variants)
+    cloned_variants.push_back (variant->monomorphized_clone ());
+
+  return new ADTType (get_ref (), get_ty_ref (), identifier, ident,
+		      get_adt_kind (), cloned_variants, clone_substs (),
+		      get_repr_options (), used_arguments,
+		      get_combined_refs ());
+}
+
+static bool
+handle_substitions (SubstitutionArgumentMappings &subst_mappings,
+		    StructFieldType *field)
+{
+  auto fty = field->get_field_type ();
+  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 ());
+	      field->set_field_type (new_field);
+	    }
+	  else
+	    {
+	      field->get_field_type ()->set_ty_ref (argt->get_ref ());
+	    }
+	}
+    }
+  else if (fty->has_subsititions_defined () || fty->contains_type_parameters ())
+    {
+      BaseType *concrete
+	= Resolver::SubstMapperInternal::Resolve (fty, subst_mappings);
+
+      if (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 false;
+	}
+
+      auto new_field = concrete->clone ();
+      new_field->set_ref (fty->get_ref ());
+      field->set_field_type (new_field);
+    }
+
+  return true;
+}
+
+ADTType *
+ADTType::handle_substitions (SubstitutionArgumentMappings subst_mappings)
+{
+  ADTType *adt = static_cast<ADTType *> (clone ());
+  adt->set_ty_ref (mappings->get_next_hir_id ());
+  adt->used_arguments = subst_mappings;
+
+  for (auto &sub : adt->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 (subst_mappings, subst_mappings.get_locus ());
+    }
+
+  for (auto &variant : adt->get_variants ())
+    {
+      if (variant->is_dataless_variant ())
+	continue;
+
+      for (auto &field : variant->get_fields ())
+	{
+	  bool ok = ::Rust::TyTy::handle_substitions (subst_mappings, field);
+	  if (!ok)
+	    return adt;
+	}
+    }
+
+  return adt;
+}
+
+void
+TupleType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+TupleType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+TupleType::as_string () const
+{
+  std::string fields_buffer;
+  for (const TyVar &field : get_fields ())
+    {
+      fields_buffer += field.get_tyty ()->as_string ();
+      fields_buffer += ", ";
+    }
+  return "(" + fields_buffer + ")";
+}
+
+BaseType *
+TupleType::get_field (size_t index) const
+{
+  return fields.at (index).get_tyty ();
+}
+
+BaseType *
+TupleType::unify (BaseType *other)
+{
+  TupleRules r (this);
+  return r.unify (other);
+}
+
+bool
+TupleType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  TupleCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+bool
+TupleType::is_equal (const BaseType &other) const
+{
+  if (get_kind () != other.get_kind ())
+    return false;
+
+  auto other2 = static_cast<const TupleType &> (other);
+  if (num_fields () != other2.num_fields ())
+    return false;
+
+  for (size_t i = 0; i < num_fields (); i++)
+    {
+      if (!get_field (i)->is_equal (*other2.get_field (i)))
+	return false;
+    }
+  return true;
+}
+
+BaseType *
+TupleType::clone () const
+{
+  std::vector<TyVar> cloned_fields;
+  for (const auto &f : fields)
+    cloned_fields.push_back (f.clone ());
+
+  return new TupleType (get_ref (), get_ty_ref (), get_ident ().locus,
+			cloned_fields, get_combined_refs ());
+}
+
+BaseType *
+TupleType::monomorphized_clone () const
+{
+  std::vector<TyVar> cloned_fields;
+  for (const auto &f : fields)
+    cloned_fields.push_back (f.monomorphized_clone ());
+
+  return new TupleType (get_ref (), get_ty_ref (), get_ident ().locus,
+			cloned_fields, get_combined_refs ());
+}
+
+TupleType *
+TupleType::handle_substitions (SubstitutionArgumentMappings mappings)
+{
+  auto mappings_table = Analysis::Mappings::get ();
+
+  TupleType *tuple = static_cast<TupleType *> (clone ());
+  tuple->set_ref (mappings_table->get_next_hir_id ());
+  tuple->set_ty_ref (mappings_table->get_next_hir_id ());
+
+  for (size_t i = 0; i < tuple->fields.size (); i++)
+    {
+      TyVar &field = fields.at (i);
+      if (field.get_tyty ()->contains_type_parameters ())
+	{
+	  BaseType *concrete
+	    = Resolver::SubstMapperInternal::Resolve (field.get_tyty (),
+						      mappings);
+	  tuple->fields[i]
+	    = TyVar::subst_covariant_var (field.get_tyty (), concrete);
+	}
+    }
+
+  return tuple;
+}
+
+void
+FnType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+FnType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+FnType::as_string () const
+{
+  std::string params_str = "";
+  for (auto &param : params)
+    {
+      auto pattern = param.first;
+      auto ty = param.second;
+      params_str += pattern->as_string () + " " + ty->as_string ();
+      params_str += ",";
+    }
+
+  std::string ret_str = type->as_string ();
+  return "fn" + subst_as_string () + " (" + params_str + ") -> " + ret_str;
+}
+
+BaseType *
+FnType::unify (BaseType *other)
+{
+  FnRules r (this);
+  return r.unify (other);
+}
+
+bool
+FnType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  FnCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+bool
+FnType::is_equal (const BaseType &other) const
+{
+  if (get_kind () != other.get_kind ())
+    return false;
+
+  auto other2 = static_cast<const FnType &> (other);
+  if (get_identifier ().compare (other2.get_identifier ()) != 0)
+    return false;
+
+  if (!get_return_type ()->is_equal (*other2.get_return_type ()))
+    return false;
+
+  if (has_subsititions_defined () != other2.has_subsititions_defined ())
+    return false;
+
+  if (has_subsititions_defined ())
+    {
+      if (get_num_substitutions () != other2.get_num_substitutions ())
+	return false;
+
+      const FnType &ofn = static_cast<const FnType &> (other);
+      for (size_t i = 0; i < get_num_substitutions (); i++)
+	{
+	  const SubstitutionParamMapping &a = get_substs ().at (i);
+	  const SubstitutionParamMapping &b = ofn.get_substs ().at (i);
+
+	  const ParamType *pa = a.get_param_ty ();
+	  const ParamType *pb = b.get_param_ty ();
+
+	  if (!pa->is_equal (*pb))
+	    return false;
+	}
+    }
+
+  if (num_params () != other2.num_params ())
+    return false;
+
+  for (size_t i = 0; i < num_params (); i++)
+    {
+      auto lhs = param_at (i).second;
+      auto rhs = other2.param_at (i).second;
+      if (!lhs->is_equal (*rhs))
+	return false;
+    }
+  return true;
+}
+
+BaseType *
+FnType::clone () const
+{
+  std::vector<std::pair<HIR::Pattern *, BaseType *>> cloned_params;
+  for (auto &p : params)
+    cloned_params.push_back ({p.first, p.second->clone ()});
+
+  return new FnType (get_ref (), get_ty_ref (), get_id (), get_identifier (),
+		     ident, flags, abi, std::move (cloned_params),
+		     get_return_type ()->clone (), clone_substs (),
+		     get_combined_refs ());
+}
+
+BaseType *
+FnType::monomorphized_clone () const
+{
+  std::vector<std::pair<HIR::Pattern *, BaseType *>> cloned_params;
+  for (auto &p : params)
+    cloned_params.push_back ({p.first, p.second->monomorphized_clone ()});
+
+  return new FnType (get_ref (), get_ty_ref (), get_id (), get_identifier (),
+		     ident, flags, abi, std::move (cloned_params),
+		     get_return_type ()->clone (), clone_substs (),
+		     get_combined_refs ());
+}
+
+FnType *
+FnType::handle_substitions (SubstitutionArgumentMappings subst_mappings)
+{
+  FnType *fn = static_cast<FnType *> (clone ());
+  fn->set_ty_ref (mappings->get_next_hir_id ());
+  fn->used_arguments = subst_mappings;
+
+  for (auto &sub : fn->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 (subst_mappings, subst_mappings.get_locus ());
+	}
+    }
+
+  auto fty = fn->get_return_type ();
+  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 ());
+	      fn->type = 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 ());
+      fn->type = new_field;
+    }
+
+  for (auto &param : fn->get_params ())
+    {
+      auto fty = param.second;
+
+      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 ());
+		  param.second = new_field;
+		}
+	      else
+		{
+		  fty->set_ty_ref (argt->get_ref ());
+		}
+	    }
+	}
+      else if (fty->has_subsititions_defined ()
+	       || 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 ());
+	  param.second = new_field;
+	}
+    }
+
+  return fn;
+}
+
+void
+FnPtr::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+FnPtr::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+FnPtr::as_string () const
+{
+  std::string params_str;
+
+  auto &params = get_params ();
+  for (auto &p : params)
+    {
+      params_str += p.get_tyty ()->as_string () + " ,";
+    }
+
+  return "fnptr (" + params_str + ") -> " + get_return_type ()->as_string ();
+}
+
+BaseType *
+FnPtr::unify (BaseType *other)
+{
+  FnptrRules r (this);
+  return r.unify (other);
+}
+
+bool
+FnPtr::can_eq (const BaseType *other, bool emit_errors) const
+{
+  FnptrCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+bool
+FnPtr::is_equal (const BaseType &other) const
+{
+  if (get_kind () != other.get_kind ())
+    return false;
+
+  auto other2 = static_cast<const FnPtr &> (other);
+  auto this_ret_type = get_return_type ();
+  auto other_ret_type = other2.get_return_type ();
+  if (this_ret_type->is_equal (*other_ret_type))
+    return false;
+
+  if (num_params () != other2.num_params ())
+    return false;
+
+  for (size_t i = 0; i < num_params (); i++)
+    {
+      if (!param_at (i)->is_equal (*other2.param_at (i)))
+	return false;
+    }
+  return true;
+}
+
+BaseType *
+FnPtr::clone () const
+{
+  std::vector<TyVar> cloned_params;
+  for (auto &p : params)
+    cloned_params.push_back (TyVar (p.get_ref ()));
+
+  return new FnPtr (get_ref (), get_ty_ref (), ident.locus,
+		    std::move (cloned_params), result_type,
+		    get_combined_refs ());
+}
+
+BaseType *
+FnPtr::monomorphized_clone () const
+{
+  std::vector<TyVar> cloned_params;
+  for (auto &p : params)
+    cloned_params.push_back (p.monomorphized_clone ());
+
+  return new FnPtr (get_ref (), get_ty_ref (), ident.locus,
+		    std::move (cloned_params), result_type,
+		    get_combined_refs ());
+}
+
+void
+ClosureType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+ClosureType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+ClosureType::as_string () const
+{
+  return "TODO";
+}
+
+BaseType *
+ClosureType::unify (BaseType *other)
+{
+  ClosureRules r (this);
+  return r.unify (other);
+}
+
+bool
+ClosureType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  ClosureCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+bool
+ClosureType::is_equal (const BaseType &other) const
+{
+  gcc_unreachable ();
+  return false;
+}
+
+BaseType *
+ClosureType::clone () const
+{
+  return new ClosureType (get_ref (), get_ty_ref (), ident, id, parameter_types,
+			  result_type, clone_substs (), get_combined_refs ());
+}
+
+BaseType *
+ClosureType::monomorphized_clone () const
+{
+  return clone ();
+}
+
+ClosureType *
+ClosureType::handle_substitions (SubstitutionArgumentMappings mappings)
+{
+  gcc_unreachable ();
+  return nullptr;
+}
+
+void
+ArrayType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+ArrayType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+ArrayType::as_string () const
+{
+  return "[" + get_element_type ()->as_string () + ":" + "CAPACITY" + "]";
+}
+
+BaseType *
+ArrayType::unify (BaseType *other)
+{
+  ArrayRules r (this);
+  return r.unify (other);
+}
+
+bool
+ArrayType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  ArrayCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+bool
+ArrayType::is_equal (const BaseType &other) const
+{
+  if (get_kind () != other.get_kind ())
+    return false;
+
+  auto other2 = static_cast<const ArrayType &> (other);
+
+  auto this_element_type = get_element_type ();
+  auto other_element_type = other2.get_element_type ();
+
+  return this_element_type->is_equal (*other_element_type);
+}
+
+BaseType *
+ArrayType::get_element_type () const
+{
+  return element_type.get_tyty ();
+}
+
+BaseType *
+ArrayType::clone () const
+{
+  return new ArrayType (get_ref (), get_ty_ref (), ident.locus, capacity_expr,
+			element_type, get_combined_refs ());
+}
+
+BaseType *
+ArrayType::monomorphized_clone () const
+{
+  return new ArrayType (get_ref (), get_ty_ref (), ident.locus, capacity_expr,
+			element_type.monomorphized_clone (),
+			get_combined_refs ());
+}
+
+ArrayType *
+ArrayType::handle_substitions (SubstitutionArgumentMappings mappings)
+{
+  auto mappings_table = Analysis::Mappings::get ();
+
+  ArrayType *ref = static_cast<ArrayType *> (clone ());
+  ref->set_ty_ref (mappings_table->get_next_hir_id ());
+
+  // might be &T or &ADT so this needs to be recursive
+  auto base = ref->get_element_type ();
+  BaseType *concrete = Resolver::SubstMapperInternal::Resolve (base, mappings);
+  ref->element_type = TyVar::subst_covariant_var (base, concrete);
+
+  return ref;
+}
+
+void
+SliceType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+SliceType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+SliceType::as_string () const
+{
+  return "[" + get_element_type ()->as_string () + "]";
+}
+
+BaseType *
+SliceType::unify (BaseType *other)
+{
+  SliceRules r (this);
+  return r.unify (other);
+}
+
+bool
+SliceType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  SliceCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+bool
+SliceType::is_equal (const BaseType &other) const
+{
+  if (get_kind () != other.get_kind ())
+    return false;
+
+  auto other2 = static_cast<const SliceType &> (other);
+
+  auto this_element_type = get_element_type ();
+  auto other_element_type = other2.get_element_type ();
+
+  return this_element_type->is_equal (*other_element_type);
+}
+
+BaseType *
+SliceType::get_element_type () const
+{
+  return element_type.get_tyty ();
+}
+
+BaseType *
+SliceType::clone () const
+{
+  return new SliceType (get_ref (), get_ty_ref (), ident.locus,
+			element_type.clone (), get_combined_refs ());
+}
+
+BaseType *
+SliceType::monomorphized_clone () const
+{
+  return new SliceType (get_ref (), get_ty_ref (), ident.locus,
+			element_type.monomorphized_clone (),
+			get_combined_refs ());
+}
+
+SliceType *
+SliceType::handle_substitions (SubstitutionArgumentMappings mappings)
+{
+  auto mappings_table = Analysis::Mappings::get ();
+
+  SliceType *ref = static_cast<SliceType *> (clone ());
+  ref->set_ty_ref (mappings_table->get_next_hir_id ());
+
+  // might be &T or &ADT so this needs to be recursive
+  auto base = ref->get_element_type ();
+  BaseType *concrete = Resolver::SubstMapperInternal::Resolve (base, mappings);
+  ref->element_type = TyVar::subst_covariant_var (base, concrete);
+
+  return ref;
+}
+
+void
+BoolType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+BoolType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+BoolType::as_string () const
+{
+  return "bool";
+}
+
+BaseType *
+BoolType::unify (BaseType *other)
+{
+  BoolRules r (this);
+  return r.unify (other);
+}
+
+bool
+BoolType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  BoolCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+BaseType *
+BoolType::clone () const
+{
+  return new BoolType (get_ref (), get_ty_ref (), get_combined_refs ());
+}
+
+BaseType *
+BoolType::monomorphized_clone () const
+{
+  return clone ();
+}
+
+void
+IntType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+IntType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+IntType::as_string () const
+{
+  switch (int_kind)
+    {
+    case I8:
+      return "i8";
+    case I16:
+      return "i16";
+    case I32:
+      return "i32";
+    case I64:
+      return "i64";
+    case I128:
+      return "i128";
+    }
+  gcc_unreachable ();
+  return "__unknown_int_type";
+}
+
+BaseType *
+IntType::unify (BaseType *other)
+{
+  IntRules r (this);
+  return r.unify (other);
+}
+
+bool
+IntType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  IntCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+BaseType *
+IntType::clone () const
+{
+  return new IntType (get_ref (), get_ty_ref (), get_int_kind (),
+		      get_combined_refs ());
+}
+
+BaseType *
+IntType::monomorphized_clone () const
+{
+  return clone ();
+}
+
+bool
+IntType::is_equal (const BaseType &other) const
+{
+  if (!BaseType::is_equal (other))
+    return false;
+
+  const IntType &o = static_cast<const IntType &> (other);
+  return get_int_kind () == o.get_int_kind ();
+}
+
+void
+UintType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+UintType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+UintType::as_string () const
+{
+  switch (uint_kind)
+    {
+    case U8:
+      return "u8";
+    case U16:
+      return "u16";
+    case U32:
+      return "u32";
+    case U64:
+      return "u64";
+    case U128:
+      return "u128";
+    }
+  gcc_unreachable ();
+  return "__unknown_uint_type";
+}
+
+BaseType *
+UintType::unify (BaseType *other)
+{
+  UintRules r (this);
+  return r.unify (other);
+}
+
+bool
+UintType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  UintCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+BaseType *
+UintType::clone () const
+{
+  return new UintType (get_ref (), get_ty_ref (), get_uint_kind (),
+		       get_combined_refs ());
+}
+
+BaseType *
+UintType::monomorphized_clone () const
+{
+  return clone ();
+}
+
+bool
+UintType::is_equal (const BaseType &other) const
+{
+  if (!BaseType::is_equal (other))
+    return false;
+
+  const UintType &o = static_cast<const UintType &> (other);
+  return get_uint_kind () == o.get_uint_kind ();
+}
+
+void
+FloatType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+FloatType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+FloatType::as_string () const
+{
+  switch (float_kind)
+    {
+    case F32:
+      return "f32";
+    case F64:
+      return "f64";
+    }
+  gcc_unreachable ();
+  return "__unknown_float_type";
+}
+
+BaseType *
+FloatType::unify (BaseType *other)
+{
+  FloatRules r (this);
+  return r.unify (other);
+}
+
+bool
+FloatType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  FloatCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+BaseType *
+FloatType::clone () const
+{
+  return new FloatType (get_ref (), get_ty_ref (), get_float_kind (),
+			get_combined_refs ());
+}
+
+BaseType *
+FloatType::monomorphized_clone () const
+{
+  return clone ();
+}
+
+bool
+FloatType::is_equal (const BaseType &other) const
+{
+  if (!BaseType::is_equal (other))
+    return false;
+
+  const FloatType &o = static_cast<const FloatType &> (other);
+  return get_float_kind () == o.get_float_kind ();
+}
+
+void
+USizeType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+USizeType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+USizeType::as_string () const
+{
+  return "usize";
+}
+
+BaseType *
+USizeType::unify (BaseType *other)
+{
+  USizeRules r (this);
+  return r.unify (other);
+}
+
+bool
+USizeType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  USizeCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+BaseType *
+USizeType::clone () const
+{
+  return new USizeType (get_ref (), get_ty_ref (), get_combined_refs ());
+}
+
+BaseType *
+USizeType::monomorphized_clone () const
+{
+  return clone ();
+}
+
+void
+ISizeType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+ISizeType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+ISizeType::as_string () const
+{
+  return "isize";
+}
+
+BaseType *
+ISizeType::unify (BaseType *other)
+{
+  ISizeRules r (this);
+  return r.unify (other);
+}
+
+bool
+ISizeType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  ISizeCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+BaseType *
+ISizeType::clone () const
+{
+  return new ISizeType (get_ref (), get_ty_ref (), get_combined_refs ());
+}
+
+BaseType *
+ISizeType::monomorphized_clone () const
+{
+  return clone ();
+}
+
+void
+CharType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+CharType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+CharType::as_string () const
+{
+  return "char";
+}
+
+BaseType *
+CharType::unify (BaseType *other)
+{
+  CharRules r (this);
+  return r.unify (other);
+}
+
+bool
+CharType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  CharCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+BaseType *
+CharType::clone () const
+{
+  return new CharType (get_ref (), get_ty_ref (), get_combined_refs ());
+}
+
+BaseType *
+CharType::monomorphized_clone () const
+{
+  return clone ();
+}
+
+void
+ReferenceType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+ReferenceType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+ReferenceType::as_string () const
+{
+  return std::string ("&") + (is_mutable () ? "mut" : "") + " "
+	 + get_base ()->as_string ();
+}
+
+BaseType *
+ReferenceType::unify (BaseType *other)
+{
+  ReferenceRules r (this);
+  return r.unify (other);
+}
+
+bool
+ReferenceType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  ReferenceCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+bool
+ReferenceType::is_equal (const BaseType &other) const
+{
+  if (get_kind () != other.get_kind ())
+    return false;
+
+  auto other2 = static_cast<const ReferenceType &> (other);
+  if (mutability () != other2.mutability ())
+    return false;
+
+  return get_base ()->is_equal (*other2.get_base ());
+}
+
+BaseType *
+ReferenceType::get_base () const
+{
+  return base.get_tyty ();
+}
+
+BaseType *
+ReferenceType::clone () const
+{
+  return new ReferenceType (get_ref (), get_ty_ref (), base, mutability (),
+			    get_combined_refs ());
+}
+
+BaseType *
+ReferenceType::monomorphized_clone () const
+{
+  return new ReferenceType (get_ref (), get_ty_ref (),
+			    base.monomorphized_clone (), mutability (),
+			    get_combined_refs ());
+}
+
+ReferenceType *
+ReferenceType::handle_substitions (SubstitutionArgumentMappings mappings)
+{
+  auto mappings_table = Analysis::Mappings::get ();
+
+  ReferenceType *ref = static_cast<ReferenceType *> (clone ());
+  ref->set_ty_ref (mappings_table->get_next_hir_id ());
+
+  // might be &T or &ADT so this needs to be recursive
+  auto base = ref->get_base ();
+  BaseType *concrete = Resolver::SubstMapperInternal::Resolve (base, mappings);
+  ref->base = TyVar::subst_covariant_var (base, concrete);
+
+  return ref;
+}
+
+void
+PointerType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+PointerType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+PointerType::as_string () const
+{
+  return std::string ("* ") + (is_mutable () ? "mut" : "const") + " "
+	 + get_base ()->as_string ();
+}
+
+BaseType *
+PointerType::unify (BaseType *other)
+{
+  PointerRules r (this);
+  return r.unify (other);
+}
+
+bool
+PointerType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  PointerCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+bool
+PointerType::is_equal (const BaseType &other) const
+{
+  if (get_kind () != other.get_kind ())
+    return false;
+
+  auto other2 = static_cast<const PointerType &> (other);
+  if (mutability () != other2.mutability ())
+    return false;
+
+  return get_base ()->is_equal (*other2.get_base ());
+}
+
+BaseType *
+PointerType::get_base () const
+{
+  return base.get_tyty ();
+}
+
+BaseType *
+PointerType::clone () const
+{
+  return new PointerType (get_ref (), get_ty_ref (), base, mutability (),
+			  get_combined_refs ());
+}
+
+BaseType *
+PointerType::monomorphized_clone () const
+{
+  return new PointerType (get_ref (), get_ty_ref (),
+			  base.monomorphized_clone (), mutability (),
+			  get_combined_refs ());
+}
+
+PointerType *
+PointerType::handle_substitions (SubstitutionArgumentMappings mappings)
+{
+  auto mappings_table = Analysis::Mappings::get ();
+
+  PointerType *ref = static_cast<PointerType *> (clone ());
+  ref->set_ty_ref (mappings_table->get_next_hir_id ());
+
+  // might be &T or &ADT so this needs to be recursive
+  auto base = ref->get_base ();
+  BaseType *concrete = Resolver::SubstMapperInternal::Resolve (base, mappings);
+  ref->base = TyVar::subst_covariant_var (base, concrete);
+
+  return ref;
+}
+
+void
+ParamType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+ParamType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+ParamType::as_string () const
+{
+  if (!can_resolve ())
+    {
+      return get_symbol () + " REF: " + std::to_string (get_ref ());
+    }
+
+  BaseType *lookup = resolve ();
+  return get_symbol () + "=" + lookup->as_string ();
+}
+
+std::string
+ParamType::get_name () const
+{
+  if (!can_resolve ())
+    return get_symbol ();
+
+  return resolve ()->get_name ();
+}
+
+BaseType *
+ParamType::unify (BaseType *other)
+{
+  ParamRules r (this);
+  return r.unify (other);
+}
+
+bool
+ParamType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  ParamCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+BaseType *
+ParamType::clone () const
+{
+  return new ParamType (get_symbol (), ident.locus, get_ref (), get_ty_ref (),
+			param, get_specified_bounds (), get_combined_refs ());
+}
+
+BaseType *
+ParamType::monomorphized_clone () const
+{
+  return resolve ()->clone ();
+}
+
+std::string
+ParamType::get_symbol () const
+{
+  return symbol;
+}
+
+BaseType *
+ParamType::resolve () const
+{
+  TyVar var (get_ty_ref ());
+  BaseType *r = var.get_tyty ();
+
+  while (r->get_kind () == TypeKind::PARAM)
+    {
+      ParamType *rr = static_cast<ParamType *> (r);
+      if (!rr->can_resolve ())
+	break;
+
+      TyVar v (rr->get_ty_ref ());
+      r = v.get_tyty ();
+    }
+
+  if (r->get_kind () == TypeKind::PARAM && (r->get_ref () == r->get_ty_ref ()))
+    return TyVar (r->get_ty_ref ()).get_tyty ();
+
+  return r;
+}
+
+bool
+ParamType::is_equal (const BaseType &other) const
+{
+  if (get_kind () != other.get_kind ())
+    {
+      if (!can_resolve ())
+	return false;
+
+      return resolve ()->is_equal (other);
+    }
+
+  auto other2 = static_cast<const ParamType &> (other);
+  if (can_resolve () != other2.can_resolve ())
+    return false;
+
+  if (can_resolve ())
+    return resolve ()->can_eq (other2.resolve (), false);
+
+  return get_symbol ().compare (other2.get_symbol ()) == 0;
+}
+
+ParamType *
+ParamType::handle_substitions (SubstitutionArgumentMappings subst_mappings)
+{
+  SubstitutionArg arg = SubstitutionArg::error ();
+  bool ok = subst_mappings.get_argument_for_symbol (this, &arg);
+  if (!ok || arg.is_error ())
+    return this;
+
+  ParamType *p = static_cast<ParamType *> (clone ());
+  subst_mappings.on_param_subst (*p, arg);
+
+  // there are two cases one where we substitute directly to a new PARAM and
+  // otherwise
+  if (arg.get_tyty ()->get_kind () == TyTy::TypeKind::PARAM)
+    {
+      p->set_ty_ref (arg.get_tyty ()->get_ref ());
+      return p;
+    }
+
+  // this is the new subst that this needs to pass
+  p->set_ref (mappings->get_next_hir_id ());
+  p->set_ty_ref (arg.get_tyty ()->get_ref ());
+
+  return p;
+}
+
+BaseType *
+StrType::clone () const
+{
+  return new StrType (get_ref (), get_ty_ref (), get_combined_refs ());
+}
+
+BaseType *
+StrType::monomorphized_clone () const
+{
+  return clone ();
+}
+
+void
+StrType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+StrType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+StrType::as_string () const
+{
+  return "str";
+}
+
+BaseType *
+StrType::unify (BaseType *other)
+{
+  StrRules r (this);
+  return r.unify (other);
+}
+
+bool
+StrType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  StrCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+bool
+StrType::is_equal (const BaseType &other) const
+{
+  return get_kind () == other.get_kind ();
+}
+
+void
+NeverType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+NeverType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+NeverType::as_string () const
+{
+  return "!";
+}
+
+BaseType *
+NeverType::unify (BaseType *other)
+{
+  NeverRules r (this);
+  return r.unify (other);
+}
+
+bool
+NeverType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  NeverCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+BaseType *
+NeverType::clone () const
+{
+  return new NeverType (get_ref (), get_ty_ref (), get_combined_refs ());
+}
+
+BaseType *
+NeverType::monomorphized_clone () const
+{
+  return clone ();
+}
+
+// placeholder type
+
+void
+PlaceholderType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+PlaceholderType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+PlaceholderType::as_string () const
+{
+  return "<placeholder:" + (can_resolve () ? resolve ()->as_string () : "")
+	 + ">";
+}
+
+BaseType *
+PlaceholderType::unify (BaseType *other)
+{
+  PlaceholderRules r (this);
+  return r.unify (other);
+}
+
+bool
+PlaceholderType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  PlaceholderCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+BaseType *
+PlaceholderType::clone () const
+{
+  return new PlaceholderType (get_symbol (), get_ref (), get_ty_ref (),
+			      get_combined_refs ());
+}
+
+BaseType *
+PlaceholderType::monomorphized_clone () const
+{
+  if (can_resolve ())
+    return resolve ()->monomorphized_clone ();
+
+  return clone ();
+}
+
+void
+PlaceholderType::set_associated_type (HirId ref)
+{
+  auto context = Resolver::TypeCheckContext::get ();
+  context->insert_associated_type_mapping (get_ty_ref (), ref);
+}
+
+void
+PlaceholderType::clear_associated_type ()
+{
+  auto context = Resolver::TypeCheckContext::get ();
+  context->clear_associated_type_mapping (get_ty_ref ());
+}
+
+bool
+PlaceholderType::can_resolve () const
+{
+  auto context = Resolver::TypeCheckContext::get ();
+  return context->lookup_associated_type_mapping (get_ty_ref (), nullptr);
+}
+
+BaseType *
+PlaceholderType::resolve () const
+{
+  auto context = Resolver::TypeCheckContext::get ();
+
+  HirId mapping;
+  bool ok = context->lookup_associated_type_mapping (get_ty_ref (), &mapping);
+  rust_assert (ok);
+
+  return TyVar (mapping).get_tyty ();
+}
+
+bool
+PlaceholderType::is_equal (const BaseType &other) const
+{
+  if (get_kind () != other.get_kind ())
+    {
+      if (!can_resolve ())
+	return false;
+
+      return resolve ()->is_equal (other);
+    }
+
+  auto other2 = static_cast<const PlaceholderType &> (other);
+  return get_symbol ().compare (other2.get_symbol ()) == 0;
+}
+
+// Projection type
+
+void
+ProjectionType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+ProjectionType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+ProjectionType::as_string () const
+{
+  return "<Projection=" + subst_as_string () + "::" + base->as_string () + ">";
+}
+
+BaseType *
+ProjectionType::unify (BaseType *other)
+{
+  return base->unify (other);
+}
+
+bool
+ProjectionType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  return base->can_eq (other, emit_errors);
+}
+
+BaseType *
+ProjectionType::clone () const
+{
+  return new ProjectionType (get_ref (), get_ty_ref (), base->clone (), trait,
+			     item, clone_substs (), used_arguments,
+			     get_combined_refs ());
+}
+
+BaseType *
+ProjectionType::monomorphized_clone () const
+{
+  return get ()->monomorphized_clone ();
+}
+
+ProjectionType *
+ProjectionType::handle_substitions (SubstitutionArgumentMappings subst_mappings)
+{
+  // // do we really need to substitute this?
+  // if (base->needs_generic_substitutions () || base->contains_type_parameters
+  // ())
+  //   {
+  //     return this;
+  //   }
+
+  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 (subst_mappings, 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;
+	}
+
+      projection->base = concrete;
+    }
+
+  return projection;
+}
+
+void
+DynamicObjectType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+void
+DynamicObjectType::accept_vis (TyConstVisitor &vis) const
+{
+  vis.visit (*this);
+}
+
+std::string
+DynamicObjectType::as_string () const
+{
+  return "dyn [" + raw_bounds_as_string () + "]";
+}
+
+BaseType *
+DynamicObjectType::unify (BaseType *other)
+{
+  DynamicRules r (this);
+  return r.unify (other);
+}
+
+bool
+DynamicObjectType::can_eq (const BaseType *other, bool emit_errors) const
+{
+  DynamicCmp r (this, emit_errors);
+  return r.can_eq (other);
+}
+
+BaseType *
+DynamicObjectType::clone () const
+{
+  return new DynamicObjectType (get_ref (), get_ty_ref (), ident,
+				specified_bounds, get_combined_refs ());
+}
+
+BaseType *
+DynamicObjectType::monomorphized_clone () const
+{
+  return clone ();
+}
+
+std::string
+DynamicObjectType::get_name () const
+{
+  return "dyn [" + raw_bounds_as_name () + "]";
+}
+
+bool
+DynamicObjectType::is_equal (const BaseType &other) const
+{
+  if (get_kind () != other.get_kind ())
+    return false;
+
+  if (num_specified_bounds () != other.num_specified_bounds ())
+    return false;
+
+  return bounds_compatible (other, Location (), false);
+}
+
+const std::vector<
+  std::pair<const Resolver::TraitItemReference *, const TypeBoundPredicate *>>
+DynamicObjectType::get_object_items () const
+{
+  std::vector<
+    std::pair<const Resolver::TraitItemReference *, const TypeBoundPredicate *>>
+    items;
+  for (auto &bound : get_specified_bounds ())
+    {
+      const Resolver::TraitReference *trait = bound.get ();
+      for (auto &item : trait->get_trait_items ())
+	{
+	  if (item.get_trait_item_type ()
+		== Resolver::TraitItemReference::TraitItemType::FN
+	      && item.is_object_safe ())
+	    items.push_back ({&item, &bound});
+	}
+
+      for (auto &super_trait : trait->get_super_traits ())
+	{
+	  for (auto &item : super_trait->get_trait_items ())
+	    {
+	      if (item.get_trait_item_type ()
+		    == Resolver::TraitItemReference::TraitItemType::FN
+		  && item.is_object_safe ())
+		items.push_back ({&item, &bound});
+	    }
+	}
+    }
+  return items;
+}
+
+} // namespace TyTy
+} // namespace Rust
diff --git a/gcc/rust/typecheck/rust-tyty.h b/gcc/rust/typecheck/rust-tyty.h
new file mode 100644
index 00000000000..c47921d44d7
--- /dev/null
+++ b/gcc/rust/typecheck/rust-tyty.h
@@ -0,0 +1,2533 @@
+// 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
+#define RUST_TYTY
+
+#include "rust-hir-map.h"
+#include "rust-hir-full.h"
+#include "rust-diagnostics.h"
+#include "rust-abi.h"
+#include "rust-common.h"
+#include "rust-identifier.h"
+
+namespace Rust {
+
+namespace Resolver {
+class TraitReference;
+class TraitItemReference;
+class AssociatedImplTrait;
+} // namespace Resolver
+
+namespace TyTy {
+
+// https://rustc-dev-guide.rust-lang.org/type-inference.html#inference-variables
+// https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/enum.TyKind.html#variants
+enum TypeKind
+{
+  INFER,
+  ADT,
+  STR,
+  REF,
+  POINTER,
+  PARAM,
+  ARRAY,
+  SLICE,
+  FNDEF,
+  FNPTR,
+  TUPLE,
+  BOOL,
+  CHAR,
+  INT,
+  UINT,
+  FLOAT,
+  USIZE,
+  ISIZE,
+  NEVER,
+  PLACEHOLDER,
+  PROJECTION,
+  DYNAMIC,
+  CLOSURE,
+  // there are more to add...
+  ERROR
+};
+
+extern bool
+is_primitive_type_kind (TypeKind kind);
+
+class TypeKindFormat
+{
+public:
+  static std::string to_string (TypeKind kind);
+};
+
+class BaseType;
+class TypeBoundPredicate;
+class TypeBoundPredicateItem
+{
+public:
+  TypeBoundPredicateItem (const TypeBoundPredicate *parent,
+			  const Resolver::TraitItemReference *trait_item_ref)
+    : parent (parent), trait_item_ref (trait_item_ref)
+  {}
+
+  static TypeBoundPredicateItem error ()
+  {
+    return TypeBoundPredicateItem (nullptr, nullptr);
+  }
+
+  bool is_error () const
+  {
+    return parent == nullptr || trait_item_ref == nullptr;
+  }
+
+  BaseType *get_tyty_for_receiver (const TyTy::BaseType *receiver);
+
+  const Resolver::TraitItemReference *get_raw_item () const;
+
+  bool needs_implementation () const;
+
+  const TypeBoundPredicate *get_parent () const { return parent; }
+
+  Location get_locus () const;
+
+private:
+  const TypeBoundPredicate *parent;
+  const Resolver::TraitItemReference *trait_item_ref;
+};
+
+class TypeBoundsMappings
+{
+protected:
+  TypeBoundsMappings (std::vector<TypeBoundPredicate> specified_bounds);
+
+public:
+  std::vector<TypeBoundPredicate> &get_specified_bounds ();
+
+  const std::vector<TypeBoundPredicate> &get_specified_bounds () const;
+
+  size_t num_specified_bounds () const;
+
+  std::string raw_bounds_as_string () const;
+
+  std::string bounds_as_string () const;
+
+  std::string raw_bounds_as_name () const;
+
+protected:
+  void add_bound (TypeBoundPredicate predicate);
+
+  std::vector<TypeBoundPredicate> specified_bounds;
+};
+
+class TyVisitor;
+class TyConstVisitor;
+class BaseType : public TypeBoundsMappings
+{
+public:
+  virtual ~BaseType () {}
+
+  HirId get_ref () const { return ref; }
+
+  void set_ref (HirId id)
+  {
+    if (id != ref)
+      append_reference (ref);
+    ref = id;
+  }
+
+  HirId get_ty_ref () const { return ty_ref; }
+
+  void set_ty_ref (HirId id) { ty_ref = id; }
+
+  virtual void accept_vis (TyVisitor &vis) = 0;
+
+  virtual void accept_vis (TyConstVisitor &vis) const = 0;
+
+  virtual std::string as_string () const = 0;
+
+  virtual std::string get_name () const = 0;
+
+  // Unify two types. Returns a pointer to the newly-created unified ty, or
+  // nullptr if the two ty cannot be unified. The caller is responsible for
+  // releasing the memory of the returned ty.
+  virtual BaseType *unify (BaseType *other) = 0;
+
+  // similar to unify but does not actually perform type unification but
+  // determines whether they are compatible. Consider the following
+  //
+  // fn foo<T>() -> T { ... }
+  // fn foo() -> i32 { ... }
+  //
+  // when the function has been substituted they can be considered equal.
+  //
+  // It can also be used to optional emit errors for trait item compatibility
+  // checks
+  virtual bool can_eq (const BaseType *other, bool emit_errors) const = 0;
+
+  // Check value equality between two ty. Type inference rules are ignored. Two
+  //   ty are considered equal if they're of the same kind, and
+  //     1. (For ADTs, arrays, tuples, refs) have the same underlying ty
+  //     2. (For functions) have the same signature
+  virtual bool is_equal (const BaseType &other) const
+  {
+    return get_kind () == other.get_kind ();
+  }
+
+  bool satisfies_bound (const TypeBoundPredicate &predicate) const;
+
+  bool bounds_compatible (const BaseType &other, Location locus,
+			  bool emit_error) const;
+
+  void inherit_bounds (const BaseType &other);
+
+  void inherit_bounds (
+    const std::vector<TyTy::TypeBoundPredicate> &specified_bounds);
+
+  virtual bool is_unit () const { return false; }
+
+  virtual bool is_concrete () const = 0;
+
+  TypeKind get_kind () const { return kind; }
+
+  /* Returns a pointer to a clone of this. The caller is responsible for
+   * releasing the memory of the returned ty. */
+  virtual BaseType *clone () const = 0;
+
+  // TODO
+  virtual BaseType *monomorphized_clone () const = 0;
+
+  // get_combined_refs returns the chain of node refs involved in unification
+  std::set<HirId> get_combined_refs () const { return combined; }
+
+  void append_reference (HirId id) { combined.insert (id); }
+
+  virtual bool supports_substitutions () const { return false; }
+
+  virtual bool has_subsititions_defined () const { return false; }
+
+  virtual bool can_substitute () const
+  {
+    return supports_substitutions () && has_subsititions_defined ();
+  }
+
+  virtual bool needs_generic_substitutions () const { return false; }
+
+  bool contains_type_parameters () const { return !is_concrete (); }
+
+  std::string mappings_str () const
+  {
+    std::string buffer = "Ref: " + std::to_string (get_ref ())
+			 + " TyRef: " + std::to_string (get_ty_ref ());
+    buffer += "[";
+    for (auto &ref : combined)
+      buffer += std::to_string (ref) + ",";
+    buffer += "]";
+    return "(" + buffer + ")";
+  }
+
+  std::string debug_str () const
+  {
+    return TypeKindFormat::to_string (get_kind ()) + ":" + as_string () + ":"
+	   + mappings_str () + ":" + bounds_as_string ();
+  }
+
+  void debug () const
+  {
+    rust_debug ("[%p] %s", static_cast<const void *> (this),
+		debug_str ().c_str ());
+  }
+
+  // FIXME this will eventually go away
+  const BaseType *get_root () const;
+
+  // This will get the monomorphized type from Params, Placeholders or
+  // Projections if available or error
+  const BaseType *destructure () const;
+
+  const RustIdent &get_ident () const { return ident; }
+
+  Location get_locus () const { return ident.locus; }
+
+protected:
+  BaseType (HirId ref, HirId ty_ref, TypeKind kind, RustIdent ident,
+	    std::set<HirId> refs = std::set<HirId> ())
+    : TypeBoundsMappings ({}), kind (kind), ref (ref), ty_ref (ty_ref),
+      combined (refs), ident (ident), mappings (Analysis::Mappings::get ())
+  {}
+
+  BaseType (HirId ref, HirId ty_ref, TypeKind kind, RustIdent ident,
+	    std::vector<TypeBoundPredicate> specified_bounds,
+	    std::set<HirId> refs = std::set<HirId> ())
+    : TypeBoundsMappings (specified_bounds), kind (kind), ref (ref),
+      ty_ref (ty_ref), combined (refs), ident (ident),
+      mappings (Analysis::Mappings::get ())
+  {}
+
+  TypeKind kind;
+  HirId ref;
+  HirId ty_ref;
+  std::set<HirId> combined;
+  RustIdent ident;
+
+  Analysis::Mappings *mappings;
+};
+
+// this is a placeholder for types that can change like inference variables
+class TyVar
+{
+public:
+  explicit TyVar (HirId ref);
+
+  HirId get_ref () const { return ref; }
+
+  BaseType *get_tyty () const;
+
+  TyVar clone () const;
+
+  TyVar monomorphized_clone () const;
+
+  static TyVar get_implicit_infer_var (Location locus);
+
+  static TyVar subst_covariant_var (TyTy::BaseType *orig,
+				    TyTy::BaseType *subst);
+
+private:
+  HirId ref;
+};
+
+class TyWithLocation
+{
+public:
+  TyWithLocation (BaseType *ty, Location locus);
+  TyWithLocation (BaseType *ty);
+
+  BaseType *get_ty () const { return ty; }
+  Location get_locus () const { return locus; }
+
+private:
+  BaseType *ty;
+  Location locus;
+};
+
+class InferType : public BaseType
+{
+public:
+  enum InferTypeKind
+  {
+    GENERAL,
+    INTEGRAL,
+    FLOAT
+  };
+
+  InferType (HirId ref, InferTypeKind infer_kind, Location locus,
+	     std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::INFER,
+		{Resolver::CanonicalPath::create_empty (), locus}, refs),
+      infer_kind (infer_kind)
+  {}
+
+  InferType (HirId ref, HirId ty_ref, InferTypeKind infer_kind, Location locus,
+	     std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::INFER,
+		{Resolver::CanonicalPath::create_empty (), locus}, refs),
+      infer_kind (infer_kind)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  BaseType *unify (BaseType *other) override;
+
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  InferTypeKind get_infer_kind () const { return infer_kind; }
+
+  std::string get_name () const override final { return as_string (); }
+
+  bool default_type (BaseType **type) const;
+
+  bool is_concrete () const final override { return true; }
+
+private:
+  InferTypeKind infer_kind;
+};
+
+class ErrorType : public BaseType
+{
+public:
+  ErrorType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::ERROR,
+		{Resolver::CanonicalPath::create_empty (), Location ()}, refs)
+  {}
+
+  ErrorType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::ERROR,
+		{Resolver::CanonicalPath::create_empty (), Location ()}, refs)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  bool is_unit () const override { return true; }
+
+  std::string as_string () const override;
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  bool is_concrete () const final override { return false; }
+};
+
+class SubstitutionArgumentMappings;
+class ParamType : public BaseType
+{
+public:
+  ParamType (std::string symbol, Location locus, HirId ref,
+	     HIR::GenericParam &param,
+	     std::vector<TypeBoundPredicate> specified_bounds,
+	     std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::PARAM,
+		{Resolver::CanonicalPath::new_seg (UNKNOWN_NODEID, symbol),
+		 locus},
+		specified_bounds, refs),
+      symbol (symbol), param (param)
+  {}
+
+  ParamType (std::string symbol, Location locus, HirId ref, HirId ty_ref,
+	     HIR::GenericParam &param,
+	     std::vector<TypeBoundPredicate> specified_bounds,
+	     std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::PARAM,
+		{Resolver::CanonicalPath::new_seg (UNKNOWN_NODEID, symbol),
+		 locus},
+		specified_bounds, refs),
+      symbol (symbol), param (param)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  std::string get_symbol () const;
+
+  HIR::GenericParam &get_generic_param () { return param; }
+
+  bool can_resolve () const { return get_ref () != get_ty_ref (); }
+
+  BaseType *resolve () const;
+
+  std::string get_name () const override final;
+
+  bool is_equal (const BaseType &other) const override;
+
+  bool is_concrete () const override final
+  {
+    auto r = resolve ();
+    if (r == this)
+      return false;
+
+    return r->is_concrete ();
+  }
+
+  ParamType *handle_substitions (SubstitutionArgumentMappings mappings);
+
+private:
+  std::string symbol;
+  HIR::GenericParam &param;
+};
+
+class StructFieldType
+{
+public:
+  StructFieldType (HirId ref, std::string name, BaseType *ty)
+    : ref (ref), name (name), ty (ty)
+  {}
+
+  HirId get_ref () const { return ref; }
+
+  std::string as_string () const;
+
+  bool is_equal (const StructFieldType &other) const;
+
+  std::string get_name () const { return name; }
+
+  BaseType *get_field_type () const { return ty; }
+
+  void set_field_type (BaseType *fty) { ty = fty; }
+
+  StructFieldType *clone () const;
+
+  StructFieldType *monomorphized_clone () const;
+
+  bool is_concrete () const { return ty->is_concrete (); }
+
+  void debug () const { rust_debug ("%s", as_string ().c_str ()); }
+
+private:
+  HirId ref;
+  std::string name;
+  BaseType *ty;
+};
+
+class TupleType : public BaseType
+{
+public:
+  TupleType (HirId ref, Location locus,
+	     std::vector<TyVar> fields = std::vector<TyVar> (),
+	     std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::TUPLE,
+		{Resolver::CanonicalPath::create_empty (), locus}, refs),
+      fields (fields)
+  {}
+
+  TupleType (HirId ref, HirId ty_ref, Location locus,
+	     std::vector<TyVar> fields = std::vector<TyVar> (),
+	     std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::TUPLE,
+		{Resolver::CanonicalPath::create_empty (), locus}, refs),
+      fields (fields)
+  {}
+
+  static TupleType *get_unit_type (HirId ref)
+  {
+    return new TupleType (ref, Linemap::predeclared_location ());
+  }
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  bool is_unit () const override { return this->fields.empty (); }
+
+  std::string as_string () const override;
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  bool is_equal (const BaseType &other) const override;
+
+  size_t num_fields () const { return fields.size (); }
+
+  BaseType *get_field (size_t index) const;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  bool is_concrete () const override final
+  {
+    for (size_t i = 0; i < num_fields (); i++)
+      {
+	if (!get_field (i)->is_concrete ())
+	  return false;
+      }
+    return true;
+  }
+
+  const std::vector<TyVar> &get_fields () const { return fields; }
+
+  std::string get_name () const override final { return as_string (); }
+
+  TupleType *handle_substitions (SubstitutionArgumentMappings mappings);
+
+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,
+				Location locus,
+				ParamSubstCb param_subst_cb = nullptr,
+				bool trait_item_flag = false)
+    : mappings (mappings), locus (locus), param_subst_cb (param_subst_cb),
+      trait_item_flag (trait_item_flag)
+  {}
+
+  SubstitutionArgumentMappings (const SubstitutionArgumentMappings &other)
+    : mappings (other.mappings), 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;
+    locus = other.locus;
+    param_subst_cb = other.param_subst_cb;
+    trait_item_flag = other.trait_item_flag;
+
+    return *this;
+  }
+
+  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::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;
+  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 + ">";
+  }
+
+  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)
+  {
+    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);
+	    if (it == argument_mappings.end ())
+	      {
+		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, it->second));
+	      }
+	  }
+	else
+	  {
+	    args.push_back (
+	      SubstitutionArg (&p, p.get_param_ty ()->resolve ()));
+	  }
+      }
+
+    SubstitutionArgumentMappings infer_arguments (std::move (args), locus);
+    return handle_substitions (std::move (infer_arguments));
+  }
+
+  // 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:
+  TypeBoundPredicate (const Resolver::TraitReference &trait_reference,
+		      Location locus);
+
+  TypeBoundPredicate (DefId reference,
+		      std::vector<SubstitutionParamMapping> substitutions,
+		      Location locus);
+
+  TypeBoundPredicate (const TypeBoundPredicate &other);
+
+  TypeBoundPredicate &operator= (const TypeBoundPredicate &other);
+
+  static TypeBoundPredicate error ();
+
+  std::string as_string () const;
+
+  std::string as_name () const;
+
+  const Resolver::TraitReference *get () const;
+
+  Location get_locus () const { return locus; }
+
+  std::string get_name () const;
+
+  // check that this predicate is object-safe see:
+  // https://doc.rust-lang.org/reference/items/traits.html#object-safety
+  bool is_object_safe (bool emit_error, Location locus) const;
+
+  void apply_generic_arguments (HIR::GenericArgs *generic_args);
+
+  bool contains_item (const std::string &search) const;
+
+  TypeBoundPredicateItem
+  lookup_associated_item (const std::string &search) const;
+
+  TypeBoundPredicateItem
+  lookup_associated_item (const Resolver::TraitItemReference *ref) const;
+
+  // WARNING THIS WILL ALWAYS RETURN NULLPTR
+  BaseType *
+  handle_substitions (SubstitutionArgumentMappings mappings) override final;
+
+  bool is_error () const;
+
+  bool requires_generic_args () const;
+
+private:
+  DefId reference;
+  Location locus;
+  bool error_flag;
+};
+
+// https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.VariantDef.html
+class VariantDef
+{
+public:
+  enum VariantType
+  {
+    NUM,
+    TUPLE,
+    STRUCT
+  };
+
+  static std::string variant_type_string (VariantType type)
+  {
+    switch (type)
+      {
+      case NUM:
+	return "enumeral";
+      case TUPLE:
+	return "tuple";
+      case STRUCT:
+	return "struct";
+      }
+    gcc_unreachable ();
+    return "";
+  }
+
+  VariantDef (HirId id, std::string identifier, RustIdent ident,
+	      HIR::Expr *discriminant)
+    : id (id), identifier (identifier), ident (ident),
+      discriminant (discriminant)
+
+  {
+    type = VariantType::NUM;
+    fields = {};
+  }
+
+  VariantDef (HirId id, std::string identifier, RustIdent ident,
+	      VariantType type, HIR::Expr *discriminant,
+	      std::vector<StructFieldType *> fields)
+    : id (id), identifier (identifier), ident (ident), type (type),
+      discriminant (discriminant), fields (fields)
+  {
+    rust_assert (
+      (type == VariantType::NUM && fields.empty ())
+      || (type == VariantType::TUPLE || type == VariantType::STRUCT));
+  }
+
+  VariantDef (const VariantDef &other)
+    : id (other.id), identifier (other.identifier), ident (other.ident),
+      type (other.type), discriminant (other.discriminant),
+      fields (other.fields)
+  {}
+
+  VariantDef &operator= (const VariantDef &other)
+  {
+    id = other.id;
+    identifier = other.identifier;
+    type = other.type;
+    discriminant = other.discriminant;
+    fields = other.fields;
+    ident = other.ident;
+
+    return *this;
+  }
+
+  static VariantDef &get_error_node ()
+  {
+    static VariantDef node
+      = VariantDef (UNKNOWN_HIRID, "",
+		    {Resolver::CanonicalPath::create_empty (),
+		     Linemap::unknown_location ()},
+		    nullptr);
+
+    return node;
+  }
+
+  bool is_error () const { return get_id () == UNKNOWN_HIRID; }
+
+  HirId get_id () const { return id; }
+
+  VariantType get_variant_type () const { return type; }
+  bool is_data_variant () const { return type != VariantType::NUM; }
+  bool is_dataless_variant () const { return type == VariantType::NUM; }
+
+  std::string get_identifier () const { return identifier; }
+
+  size_t num_fields () const { return fields.size (); }
+  StructFieldType *get_field_at_index (size_t index)
+  {
+    rust_assert (index < fields.size ());
+    return fields.at (index);
+  }
+
+  std::vector<StructFieldType *> &get_fields ()
+  {
+    rust_assert (type != NUM);
+    return fields;
+  }
+
+  bool lookup_field (const std::string &lookup, StructFieldType **field_lookup,
+		     size_t *index) const
+  {
+    size_t i = 0;
+    for (auto &field : fields)
+      {
+	if (field->get_name ().compare (lookup) == 0)
+	  {
+	    if (index != nullptr)
+	      *index = i;
+
+	    if (field_lookup != nullptr)
+	      *field_lookup = field;
+
+	    return true;
+	  }
+	i++;
+      }
+    return false;
+  }
+
+  HIR::Expr *get_discriminant () const
+  {
+    rust_assert (discriminant != nullptr);
+    return discriminant;
+  }
+
+  std::string as_string () const
+  {
+    if (type == VariantType::NUM)
+      return identifier + " = " + discriminant->as_string ();
+
+    std::string buffer;
+    for (size_t i = 0; i < fields.size (); ++i)
+      {
+	buffer += fields.at (i)->as_string ();
+	if ((i + 1) < fields.size ())
+	  buffer += ", ";
+      }
+
+    if (type == VariantType::TUPLE)
+      return identifier + " (" + buffer + ")";
+    else
+      return identifier + " {" + buffer + "}";
+  }
+
+  bool is_equal (const VariantDef &other) const
+  {
+    if (type != other.type)
+      return false;
+
+    if (identifier.compare (other.identifier) != 0)
+      return false;
+
+    if (discriminant != other.discriminant)
+      return false;
+
+    if (fields.size () != other.fields.size ())
+      return false;
+
+    for (size_t i = 0; i < fields.size (); i++)
+      {
+	if (!fields.at (i)->is_equal (*other.fields.at (i)))
+	  return false;
+      }
+
+    return true;
+  }
+
+  VariantDef *clone () const
+  {
+    std::vector<StructFieldType *> cloned_fields;
+    for (auto &f : fields)
+      cloned_fields.push_back ((StructFieldType *) f->clone ());
+
+    return new VariantDef (id, identifier, ident, type, discriminant,
+			   cloned_fields);
+  }
+
+  VariantDef *monomorphized_clone () const
+  {
+    std::vector<StructFieldType *> cloned_fields;
+    for (auto &f : fields)
+      cloned_fields.push_back ((StructFieldType *) f->monomorphized_clone ());
+
+    return new VariantDef (id, identifier, ident, type, discriminant,
+			   cloned_fields);
+  }
+
+  const RustIdent &get_ident () const { return ident; }
+
+private:
+  HirId id;
+  std::string identifier;
+  RustIdent ident;
+  VariantType type;
+  // can either be a structure or a discriminant value
+  HIR::Expr *discriminant;
+  std::vector<StructFieldType *> fields;
+};
+
+class ADTType : public BaseType, public SubstitutionRef
+{
+public:
+  enum ADTKind
+  {
+    STRUCT_STRUCT,
+    TUPLE_STRUCT,
+    UNION,
+    ENUM
+  };
+
+  // Representation options, specified via attributes e.g. #[repr(packed)]
+  struct ReprOptions
+  {
+    // bool is_c;
+    // bool is_transparent;
+    //...
+
+    // For align and pack: 0 = unspecified. Nonzero = byte alignment.
+    // It is an error for both to be nonzero, this should be caught when
+    // parsing the #[repr] attribute.
+    unsigned char align = 0;
+    unsigned char pack = 0;
+  };
+
+  ADTType (HirId ref, std::string identifier, RustIdent ident, ADTKind adt_kind,
+	   std::vector<VariantDef *> variants,
+	   std::vector<SubstitutionParamMapping> subst_refs,
+	   SubstitutionArgumentMappings generic_arguments
+	   = SubstitutionArgumentMappings::error (),
+	   std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::ADT, ident, refs),
+      SubstitutionRef (std::move (subst_refs), std::move (generic_arguments)),
+      identifier (identifier), variants (variants), adt_kind (adt_kind)
+  {}
+
+  ADTType (HirId ref, HirId ty_ref, std::string identifier, RustIdent ident,
+	   ADTKind adt_kind, std::vector<VariantDef *> variants,
+	   std::vector<SubstitutionParamMapping> subst_refs,
+	   SubstitutionArgumentMappings generic_arguments
+	   = SubstitutionArgumentMappings::error (),
+	   std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::ADT, ident, refs),
+      SubstitutionRef (std::move (subst_refs), std::move (generic_arguments)),
+      identifier (identifier), variants (variants), adt_kind (adt_kind)
+  {}
+
+  ADTType (HirId ref, HirId ty_ref, std::string identifier, RustIdent ident,
+	   ADTKind adt_kind, std::vector<VariantDef *> variants,
+	   std::vector<SubstitutionParamMapping> subst_refs, ReprOptions repr,
+	   SubstitutionArgumentMappings generic_arguments
+	   = SubstitutionArgumentMappings::error (),
+	   std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::ADT, ident, refs),
+      SubstitutionRef (std::move (subst_refs), std::move (generic_arguments)),
+      identifier (identifier), variants (variants), adt_kind (adt_kind),
+      repr (repr)
+  {}
+
+  ADTKind get_adt_kind () const { return adt_kind; }
+  ReprOptions get_repr_options () const { return repr; }
+
+  bool is_struct_struct () const { return adt_kind == STRUCT_STRUCT; }
+  bool is_tuple_struct () const { return adt_kind == TUPLE_STRUCT; }
+  bool is_union () const { return adt_kind == UNION; }
+  bool is_enum () const { return adt_kind == ENUM; }
+
+  bool is_unit () const override
+  {
+    if (number_of_variants () == 0)
+      return true;
+
+    if (number_of_variants () == 1)
+      return variants.at (0)->num_fields () == 0;
+
+    return false;
+  }
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  bool is_equal (const BaseType &other) const override;
+
+  std::string get_identifier () const { return identifier; }
+
+  std::string get_name () const override final
+  {
+    return identifier + subst_as_string ();
+  }
+
+  bool is_concrete () const override final
+  {
+    for (auto &variant : variants)
+      {
+	for (auto &field : variant->get_fields ())
+	  {
+	    if (!field->is_concrete ())
+	      return false;
+	  }
+      }
+    return true;
+  }
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  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 ();
+  }
+
+  size_t number_of_variants () const { return variants.size (); }
+
+  std::vector<VariantDef *> &get_variants () { return variants; }
+  const std::vector<VariantDef *> &get_variants () const { return variants; }
+
+  bool lookup_variant (const std::string &lookup,
+		       VariantDef **found_variant) const
+  {
+    for (auto &variant : variants)
+      {
+	if (variant->get_identifier ().compare (lookup) == 0)
+	  {
+	    *found_variant = variant;
+	    return true;
+	  }
+      }
+    return false;
+  }
+
+  bool lookup_variant_by_id (HirId id, VariantDef **found_variant,
+			     int *index = nullptr) const
+  {
+    int i = 0;
+    for (auto &variant : variants)
+      {
+	if (variant->get_id () == id)
+	  {
+	    if (index != nullptr)
+	      *index = i;
+
+	    *found_variant = variant;
+	    return true;
+	  }
+	i++;
+      }
+    return false;
+  }
+
+  ADTType *
+  handle_substitions (SubstitutionArgumentMappings mappings) override final;
+
+private:
+  std::string identifier;
+  std::vector<VariantDef *> variants;
+  ADTType::ADTKind adt_kind;
+  ReprOptions repr;
+};
+
+class FnType : public BaseType, public SubstitutionRef
+{
+public:
+  static const uint8_t FNTYPE_DEFAULT_FLAGS = 0x00;
+  static const uint8_t FNTYPE_IS_METHOD_FLAG = 0x01;
+  static const uint8_t FNTYPE_IS_EXTERN_FLAG = 0x02;
+  static const uint8_t FNTYPE_IS_VARADIC_FLAG = 0X04;
+
+  FnType (HirId ref, DefId id, std::string identifier, RustIdent ident,
+	  uint8_t flags, ABI abi,
+	  std::vector<std::pair<HIR::Pattern *, BaseType *>> params,
+	  BaseType *type, std::vector<SubstitutionParamMapping> subst_refs,
+	  std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::FNDEF, ident, refs),
+      SubstitutionRef (std::move (subst_refs),
+		       SubstitutionArgumentMappings::error ()),
+      params (std::move (params)), type (type), flags (flags),
+      identifier (identifier), id (id), abi (abi)
+  {
+    LocalDefId local_def_id = id.localDefId;
+    rust_assert (local_def_id != UNKNOWN_LOCAL_DEFID);
+  }
+
+  FnType (HirId ref, HirId ty_ref, DefId id, std::string identifier,
+	  RustIdent ident, uint8_t flags, ABI abi,
+	  std::vector<std::pair<HIR::Pattern *, BaseType *>> params,
+	  BaseType *type, std::vector<SubstitutionParamMapping> subst_refs,
+	  std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::FNDEF, ident, refs),
+      SubstitutionRef (std::move (subst_refs),
+		       SubstitutionArgumentMappings::error ()),
+      params (params), type (type), flags (flags), identifier (identifier),
+      id (id), abi (abi)
+  {
+    LocalDefId local_def_id = id.localDefId;
+    rust_assert (local_def_id != UNKNOWN_LOCAL_DEFID);
+  }
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  std::string get_identifier () const { return identifier; }
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  bool is_equal (const BaseType &other) const override;
+
+  size_t num_params () const { return params.size (); }
+
+  bool is_method () const
+  {
+    if (num_params () == 0)
+      return false;
+
+    return (flags & FNTYPE_IS_METHOD_FLAG) != 0;
+  }
+
+  bool is_extern () const { return (flags & FNTYPE_IS_EXTERN_FLAG) != 0; }
+
+  bool is_varadic () const { return (flags & FNTYPE_IS_VARADIC_FLAG) != 0; }
+
+  DefId get_id () const { return id; }
+
+  // get the Self type for the method
+  BaseType *get_self_type () const
+  {
+    rust_assert (is_method ());
+    return param_at (0).second;
+  }
+
+  bool is_concrete () const override final
+  {
+    for (const auto &param : params)
+      {
+	const BaseType *p = param.second;
+	if (!p->is_concrete ())
+	  return false;
+      }
+    return get_return_type ()->is_concrete ();
+  }
+
+  std::vector<std::pair<HIR::Pattern *, BaseType *>> &get_params ()
+  {
+    return params;
+  }
+
+  const std::vector<std::pair<HIR::Pattern *, BaseType *>> &get_params () const
+  {
+    return params;
+  }
+
+  std::pair<HIR::Pattern *, BaseType *> &param_at (size_t idx)
+  {
+    return params.at (idx);
+  }
+
+  const std::pair<HIR::Pattern *, BaseType *> &param_at (size_t idx) const
+  {
+    return params.at (idx);
+  }
+
+  BaseType *get_return_type () const { return type; }
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  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 ();
+  }
+
+  FnType *
+  handle_substitions (SubstitutionArgumentMappings mappings) override final;
+
+  ABI get_abi () const { return abi; }
+
+private:
+  std::vector<std::pair<HIR::Pattern *, BaseType *>> params;
+  BaseType *type;
+  uint8_t flags;
+  std::string identifier;
+  DefId id;
+  ABI abi;
+};
+
+class FnPtr : public BaseType
+{
+public:
+  FnPtr (HirId ref, Location locus, std::vector<TyVar> params,
+	 TyVar result_type, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::FNPTR,
+		{Resolver::CanonicalPath::create_empty (), locus}, refs),
+      params (std::move (params)), result_type (result_type)
+  {}
+
+  FnPtr (HirId ref, HirId ty_ref, Location locus, std::vector<TyVar> params,
+	 TyVar result_type, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::FNPTR,
+		{Resolver::CanonicalPath::create_empty (), locus}, refs),
+      params (params), result_type (result_type)
+  {}
+
+  std::string get_name () const override final { return as_string (); }
+
+  BaseType *get_return_type () const { return result_type.get_tyty (); }
+
+  size_t num_params () const { return params.size (); }
+
+  BaseType *param_at (size_t idx) const { return params.at (idx).get_tyty (); }
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  bool is_equal (const BaseType &other) const override;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  void iterate_params (std::function<bool (BaseType *)> cb) const
+  {
+    for (auto &p : params)
+      {
+	if (!cb (p.get_tyty ()))
+	  return;
+      }
+  }
+
+  std::vector<TyVar> &get_params () { return params; }
+  const std::vector<TyVar> &get_params () const { return params; }
+
+  bool is_concrete () const override final
+  {
+    for (auto &p : params)
+      {
+	if (!p.get_tyty ()->is_concrete ())
+	  return false;
+      }
+    return result_type.get_tyty ()->is_concrete ();
+  }
+
+private:
+  std::vector<TyVar> params;
+  TyVar result_type;
+};
+
+class ClosureType : public BaseType, public SubstitutionRef
+{
+public:
+  ClosureType (HirId ref, DefId id, RustIdent ident,
+	       std::vector<TyVar> parameter_types, TyVar result_type,
+	       std::vector<SubstitutionParamMapping> subst_refs,
+	       std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::CLOSURE, ident, refs),
+      SubstitutionRef (std::move (subst_refs),
+		       SubstitutionArgumentMappings::error ()),
+      parameter_types (std::move (parameter_types)),
+      result_type (std::move (result_type)), id (id)
+  {
+    LocalDefId local_def_id = id.localDefId;
+    rust_assert (local_def_id != UNKNOWN_LOCAL_DEFID);
+  }
+
+  ClosureType (HirId ref, HirId ty_ref, RustIdent ident, DefId id,
+	       std::vector<TyVar> parameter_types, TyVar result_type,
+	       std::vector<SubstitutionParamMapping> subst_refs,
+	       std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::CLOSURE, ident, refs),
+      SubstitutionRef (std::move (subst_refs),
+		       SubstitutionArgumentMappings::error ()),
+      parameter_types (std::move (parameter_types)),
+      result_type (std::move (result_type)), id (id)
+  {
+    LocalDefId local_def_id = id.localDefId;
+    rust_assert (local_def_id != UNKNOWN_LOCAL_DEFID);
+  }
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+  std::string get_name () const override final { return as_string (); }
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  bool is_equal (const BaseType &other) const override;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  bool is_concrete () const override final
+  {
+    for (auto &param : parameter_types)
+      {
+	auto p = param.get_tyty ();
+	if (!p->is_concrete ())
+	  return false;
+      }
+    return result_type.get_tyty ()->is_concrete ();
+  }
+
+  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 ();
+  }
+
+  ClosureType *
+  handle_substitions (SubstitutionArgumentMappings mappings) override final;
+
+private:
+  std::vector<TyVar> parameter_types;
+  TyVar result_type;
+  DefId id;
+};
+
+class ArrayType : public BaseType
+{
+public:
+  ArrayType (HirId ref, Location locus, HIR::Expr &capacity_expr, TyVar base,
+	     std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::ARRAY,
+		{Resolver::CanonicalPath::create_empty (), locus}, refs),
+      element_type (base), capacity_expr (capacity_expr)
+  {}
+
+  ArrayType (HirId ref, HirId ty_ref, Location locus, HIR::Expr &capacity_expr,
+	     TyVar base, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::ARRAY,
+		{Resolver::CanonicalPath::create_empty (), locus}, refs),
+      element_type (base), capacity_expr (capacity_expr)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  bool is_equal (const BaseType &other) const override;
+
+  BaseType *get_element_type () const;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  bool is_concrete () const final override
+  {
+    return get_element_type ()->is_concrete ();
+  }
+
+  HIR::Expr &get_capacity_expr () const { return capacity_expr; }
+
+  ArrayType *handle_substitions (SubstitutionArgumentMappings mappings);
+
+private:
+  TyVar element_type;
+  HIR::Expr &capacity_expr;
+};
+
+class SliceType : public BaseType
+{
+public:
+  SliceType (HirId ref, Location locus, TyVar base,
+	     std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::SLICE,
+		{Resolver::CanonicalPath::create_empty (), locus}, refs),
+      element_type (base)
+  {}
+
+  SliceType (HirId ref, HirId ty_ref, Location locus, TyVar base,
+	     std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::SLICE,
+		{Resolver::CanonicalPath::create_empty (), locus}, refs),
+      element_type (base)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  bool is_equal (const BaseType &other) const override;
+
+  BaseType *get_element_type () const;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  bool is_concrete () const final override
+  {
+    return get_element_type ()->is_concrete ();
+  }
+
+  SliceType *handle_substitions (SubstitutionArgumentMappings mappings);
+
+private:
+  TyVar element_type;
+};
+
+class BoolType : public BaseType
+{
+public:
+  BoolType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::BOOL,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs)
+  {}
+
+  BoolType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::BOOL,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+  bool is_concrete () const override final { return true; }
+};
+
+class IntType : public BaseType
+{
+public:
+  enum IntKind
+  {
+    I8,
+    I16,
+    I32,
+    I64,
+    I128
+  };
+
+  IntType (HirId ref, IntKind kind, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::INT,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs),
+      int_kind (kind)
+  {}
+
+  IntType (HirId ref, HirId ty_ref, IntKind kind,
+	   std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::INT,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs),
+      int_kind (kind)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  IntKind get_int_kind () const { return int_kind; }
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  bool is_equal (const BaseType &other) const override;
+  bool is_concrete () const override final { return true; }
+
+private:
+  IntKind int_kind;
+};
+
+class UintType : public BaseType
+{
+public:
+  enum UintKind
+  {
+    U8,
+    U16,
+    U32,
+    U64,
+    U128
+  };
+
+  UintType (HirId ref, UintKind kind, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::UINT,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs),
+      uint_kind (kind)
+  {}
+
+  UintType (HirId ref, HirId ty_ref, UintKind kind,
+	    std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::UINT,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs),
+      uint_kind (kind)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  UintKind get_uint_kind () const { return uint_kind; }
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  bool is_equal (const BaseType &other) const override;
+  bool is_concrete () const override final { return true; }
+
+private:
+  UintKind uint_kind;
+};
+
+class FloatType : public BaseType
+{
+public:
+  enum FloatKind
+  {
+    F32,
+    F64
+  };
+
+  FloatType (HirId ref, FloatKind kind,
+	     std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::FLOAT,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs),
+      float_kind (kind)
+  {}
+
+  FloatType (HirId ref, HirId ty_ref, FloatKind kind,
+	     std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::FLOAT,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs),
+      float_kind (kind)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  FloatKind get_float_kind () const { return float_kind; }
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  bool is_equal (const BaseType &other) const override;
+  bool is_concrete () const override final { return true; }
+
+private:
+  FloatKind float_kind;
+};
+
+class USizeType : public BaseType
+{
+public:
+  USizeType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::USIZE,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs)
+  {}
+
+  USizeType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::USIZE,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+  bool is_concrete () const override final { return true; }
+};
+
+class ISizeType : public BaseType
+{
+public:
+  ISizeType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::ISIZE,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs)
+  {}
+
+  ISizeType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::ISIZE,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+  bool is_concrete () const override final { return true; }
+};
+
+class CharType : public BaseType
+{
+public:
+  CharType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::CHAR,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs)
+  {}
+
+  CharType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::CHAR,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+  bool is_concrete () const override final { return true; }
+};
+
+class StrType : public BaseType
+{
+public:
+  StrType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::STR,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs)
+  {}
+
+  StrType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::STR,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs)
+  {}
+
+  std::string get_name () const override final { return as_string (); }
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  bool is_equal (const BaseType &other) const override;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+  bool is_concrete () const override final { return true; }
+};
+
+class ReferenceType : public BaseType
+{
+public:
+  ReferenceType (HirId ref, TyVar base, Mutability mut,
+		 std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::REF,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs),
+      base (base), mut (mut)
+  {}
+
+  ReferenceType (HirId ref, HirId ty_ref, TyVar base, Mutability mut,
+		 std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::REF,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs),
+      base (base), mut (mut)
+  {}
+
+  BaseType *get_base () const;
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  std::string get_name () const override final
+  {
+    return "&" + get_base ()->get_name ();
+  }
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  bool is_equal (const BaseType &other) const override;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  bool is_concrete () const override final
+  {
+    return get_base ()->is_concrete ();
+  }
+
+  ReferenceType *handle_substitions (SubstitutionArgumentMappings mappings);
+
+  Mutability mutability () const { return mut; }
+
+  bool is_mutable () const { return mut == Mutability::Mut; }
+
+  bool is_dyn_object () const
+  {
+    return is_dyn_slice_type () || is_dyn_str_type ();
+  }
+
+  bool is_dyn_slice_type (const TyTy::SliceType **slice = nullptr) const
+  {
+    const TyTy::BaseType *element = get_base ()->destructure ();
+    if (element->get_kind () != TyTy::TypeKind::SLICE)
+      return false;
+    if (slice == nullptr)
+      return true;
+
+    *slice = static_cast<const TyTy::SliceType *> (element);
+    return true;
+  }
+
+  bool is_dyn_str_type (const TyTy::StrType **str = nullptr) const
+  {
+    const TyTy::BaseType *element = get_base ()->destructure ();
+    if (element->get_kind () != TyTy::TypeKind::STR)
+      return false;
+    if (str == nullptr)
+      return true;
+
+    *str = static_cast<const TyTy::StrType *> (element);
+    return true;
+  }
+
+private:
+  TyVar base;
+  Mutability mut;
+};
+
+class PointerType : public BaseType
+{
+public:
+  PointerType (HirId ref, TyVar base, Mutability mut,
+	       std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::POINTER,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs),
+      base (base), mut (mut)
+  {}
+
+  PointerType (HirId ref, HirId ty_ref, TyVar base, Mutability mut,
+	       std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::POINTER,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs),
+      base (base), mut (mut)
+  {}
+
+  BaseType *get_base () const;
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  std::string get_name () const override final
+  {
+    return "*" + get_base ()->get_name ();
+  }
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  bool is_equal (const BaseType &other) const override;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  bool is_concrete () const override final
+  {
+    return get_base ()->is_concrete ();
+  }
+
+  PointerType *handle_substitions (SubstitutionArgumentMappings mappings);
+
+  Mutability mutability () const { return mut; }
+
+  bool is_mutable () const { return mut == Mutability::Mut; }
+
+  bool is_const () const { return mut == Mutability::Imm; }
+
+  bool is_dyn_object () const
+  {
+    return is_dyn_slice_type () || is_dyn_str_type ();
+  }
+
+  bool is_dyn_slice_type (const TyTy::SliceType **slice = nullptr) const
+  {
+    const TyTy::BaseType *element = get_base ()->destructure ();
+    if (element->get_kind () != TyTy::TypeKind::SLICE)
+      return false;
+    if (slice == nullptr)
+      return true;
+
+    *slice = static_cast<const TyTy::SliceType *> (element);
+    return true;
+  }
+
+  bool is_dyn_str_type (const TyTy::StrType **str = nullptr) const
+  {
+    const TyTy::BaseType *element = get_base ()->destructure ();
+    if (element->get_kind () != TyTy::TypeKind::STR)
+      return false;
+    if (str == nullptr)
+      return true;
+
+    *str = static_cast<const TyTy::StrType *> (element);
+    return true;
+  }
+
+private:
+  TyVar base;
+  Mutability mut;
+};
+
+// https://doc.rust-lang.org/std/primitive.never.html
+//
+// Since the `!` type is really complicated and it is even still unstable
+// in rustc, only fairly limited support for this type is introduced here.
+// Unification between `!` and ANY other type (including `<T?>`) is simply
+// not allowed. If it is needed, it should be handled manually. For example,
+// unifying `!` with other types is very necessary when resolving types of
+// `if/else` expressions.
+//
+// See related discussion at https://github.com/Rust-GCC/gccrs/pull/364
+class NeverType : public BaseType
+{
+public:
+  NeverType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::NEVER,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs)
+  {}
+
+  NeverType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::NEVER,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  bool is_unit () const override { return true; }
+  bool is_concrete () const override final { return true; }
+};
+
+// used at the type in associated types in traits
+// see: https://doc.rust-lang.org/book/ch19-03-advanced-traits.html
+class PlaceholderType : public BaseType
+{
+public:
+  PlaceholderType (std::string symbol, HirId ref,
+		   std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::PLACEHOLDER,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs),
+      symbol (symbol)
+  {}
+
+  PlaceholderType (std::string symbol, HirId ref, HirId ty_ref,
+		   std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::PLACEHOLDER,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs),
+      symbol (symbol)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  bool is_unit () const override
+  {
+    rust_assert (can_resolve ());
+    return resolve ()->is_unit ();
+  }
+
+  std::string get_symbol () const { return symbol; }
+
+  void set_associated_type (HirId ref);
+
+  void clear_associated_type ();
+
+  bool can_resolve () const;
+
+  BaseType *resolve () const;
+
+  bool is_equal (const BaseType &other) const override;
+
+  bool is_concrete () const override final
+  {
+    if (!can_resolve ())
+      return true;
+
+    return resolve ()->is_concrete ();
+  }
+
+private:
+  std::string symbol;
+};
+
+class ProjectionType : public BaseType, public SubstitutionRef
+{
+public:
+  ProjectionType (HirId ref, BaseType *base,
+		  const 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,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs),
+      SubstitutionRef (std::move (subst_refs), std::move (generic_arguments)),
+      base (base), trait (trait), item (item)
+  {}
+
+  ProjectionType (HirId ref, HirId ty_ref, BaseType *base,
+		  const Resolver::TraitReference *trait, DefId item,
+		  std::vector<SubstitutionParamMapping> subst_refs,
+		  SubstitutionArgumentMappings generic_arguments
+		  = SubstitutionArgumentMappings::error (),
+		  std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::PROJECTION,
+		{Resolver::CanonicalPath::create_empty (),
+		 Linemap::predeclared_location ()},
+		refs),
+      SubstitutionRef (std::move (subst_refs), std::move (generic_arguments)),
+      base (base), trait (trait), item (item)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  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 ();
+  }
+
+  const BaseType *get () const { return base; }
+  BaseType *get () { return base; }
+
+  bool is_concrete () const override final { return base->is_concrete (); }
+
+  ProjectionType *
+  handle_substitions (SubstitutionArgumentMappings mappings) override final;
+
+private:
+  BaseType *base;
+  const Resolver::TraitReference *trait;
+  DefId item;
+};
+
+class DynamicObjectType : public BaseType
+{
+public:
+  DynamicObjectType (HirId ref, RustIdent ident,
+		     std::vector<TypeBoundPredicate> specified_bounds,
+		     std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::DYNAMIC, ident, specified_bounds, refs)
+  {}
+
+  DynamicObjectType (HirId ref, HirId ty_ref, RustIdent ident,
+		     std::vector<TypeBoundPredicate> specified_bounds,
+		     std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::DYNAMIC, ident, specified_bounds, refs)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+  void accept_vis (TyConstVisitor &vis) const override;
+
+  std::string as_string () const override;
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (const BaseType *other, bool emit_errors) const override final;
+
+  bool is_equal (const BaseType &other) const override;
+
+  BaseType *clone () const final override;
+  BaseType *monomorphized_clone () const final override;
+
+  std::string get_name () const override final;
+
+  bool is_concrete () const override final { return true; }
+
+  // this returns a flat list of items including super trait bounds
+  const std::vector<
+    std::pair<const Resolver::TraitItemReference *, const TypeBoundPredicate *>>
+  get_object_items () const;
+};
+
+} // namespace TyTy
+} // namespace Rust
+
+#endif // RUST_TYTY