gccrs: Typecheck: add regions (lifetimes) to TyTy

gcc/rust/ChangeLog:

	* typecheck/rust-hir-trait-resolve.cc: add regions
	* typecheck/rust-hir-type-check-base.cc (TypeCheckBase::resolve_literal):
	add regions, resolve generic lifetimes
	* typecheck/rust-hir-type-check-expr.cc (TypeCheckExpr::visit): add regions
	* typecheck/rust-hir-type-check-implitem.cc (TypeCheckTopLevelExternItem::visit):
	add regions, resolve lifetimes
	(TypeCheckImplItem::visit): add regions, resove lifetimes
	* typecheck/rust-hir-type-check-implitem.h: add default value for result
	* typecheck/rust-hir-type-check-item.cc (TypeCheckItem::visit): add regions,
	resove lifetimes
	(TypeCheckItem::resolve_impl_block_substitutions): add regions, resove lifetimes
	* typecheck/rust-hir-type-check-path.cc (TypeCheckExpr::visit): add regions,
	resove lifetimes
	(TypeCheckExpr::resolve_root_path): add regions, resove lifetimes
	(TypeCheckExpr::resolve_segments): add regions, resove lifetimes
	* typecheck/rust-hir-type-check-type.cc (TypeCheckType::visit): add regions,
	resove lifetimes
	(TypeCheckType::resolve_root_path): add regions, resove lifetimes
	(ResolveWhereClauseItem::Resolve): add regions, resove lifetimes
	(ResolveWhereClauseItem::visit): add regions, resove lifetimes
	* typecheck/rust-hir-type-check.cc (TypeCheckContext::LifetimeResolver::resolve):
	add regions, resolve lifetimes
	(TraitItemReference::get_type_from_fn): add regions, resove lifetimes
	* typecheck/rust-hir-type-check.h: add regions, resove lifetimes
	* typecheck/rust-substitution-mapper.cc (SubstMapper::SubstMapper): add regions,
	resove lifetimes
	(SubstMapper::Resolve): add regions, resove lifetimes
	(SubstMapper::InferSubst): add regions, resove lifetimes
	(SubstMapper::visit): add regions, resove lifetimes
	* typecheck/rust-substitution-mapper.h: add regions, resove lifetimes
	* typecheck/rust-typecheck-context.cc (TypeCheckContext::TypeCheckContext):
	lifetime resolution
	(TypeCheckContext::regions_from_generic_args): lifetime resolution helper
	* typecheck/rust-tyty-bounds.cc (TypeBoundPredicate::TypeBoundPredicate):
	add regions, resove lifetimes
	(TypeBoundPredicate::operator=): add regions, resove lifetimes
	(TypeBoundPredicate::apply_generic_arguments): add regions, resove lifetimes
	(TypeBoundPredicateItem::get_tyty_for_receiver): add regions, resove lifetimes
	* typecheck/rust-tyty-subst.cc (SubstitutionArgumentMappings::get_regions):
	add regions, resove lifetimes
	(SubstitutionArgumentMappings::get_mut_regions): getter
	(SubstitutionArgumentMappings::error): split error and empty
	(SubstitutionArgumentMappings::empty): split error and empty
	(SubstitutionArgumentMappings::find_symbol): helper
	(SubstitutionRef::get_num_lifetime_params): getter
	(SubstitutionRef::get_num_type_params): getter
	(SubstitutionRef::needs_substitution): extend to regions
	(SubstitutionRef::get_mappings_from_generic_args): helper
	(SubstitutionRef::infer_substitions): add regions
	* typecheck/rust-tyty-subst.h (class RegionParamList): region param handler
	* typecheck/rust-tyty.cc (BaseType::monomorphized_clone): add regions, resove lifetimes
	(InferType::default_type): add regions, resove lifetimes
	(FnType::clone): add regions, resove lifetimes
	(ReferenceType::ReferenceType): add regions
	(ReferenceType::get_region): getter
	(ReferenceType::clone): add regions
	* typecheck/rust-tyty.h: add regions, resove

Signed-off-by: Jakub Dupak <dev@jakubdupak.com>

18 files changed, 585 insertions, 177 deletions

diff --git a/gcc/rust/typecheck/rust-hir-trait-resolve.cc b/gcc/rust/typecheck/rust-hir-trait-resolve.cc
index 1d6a9fb..a300cec 100644
--- a/gcc/rust/typecheck/rust-hir-trait-resolve.cc
+++ b/gcc/rust/typecheck/rust-hir-trait-resolve.cc
@@ -520,9 +520,10 @@ AssociatedImplTrait::setup_associated_types (
 	}
     }
 
-  TyTy::SubstitutionArgumentMappings infer_arguments (std::move (subst_args),
-						      {}, locus,
-						      param_subst_cb);
+  TyTy::SubstitutionArgumentMappings infer_arguments (
+    std::move (subst_args), {},
+    TyTy::SubstitutionArgumentMappings::regions_from_nullable_args (args),
+    locus, param_subst_cb);
   TyTy::BaseType *impl_self_infer
     = (!associated_self->is_concrete ())
 	? SubstMapperInternal::Resolve (associated_self, infer_arguments)
@@ -613,7 +614,9 @@ AssociatedImplTrait::setup_associated_types (
     }
 
   TyTy::SubstitutionArgumentMappings associated_type_args (
-    std::move (associated_arguments), {}, locus);
+    std::move (associated_arguments), {},
+    TyTy::SubstitutionArgumentMappings::regions_from_nullable_args (args),
+    locus);
 
   auto &impl_items = impl->get_impl_items ();
   for (auto &impl_item : impl_items)
diff --git a/gcc/rust/typecheck/rust-hir-type-check-base.cc b/gcc/rust/typecheck/rust-hir-type-check-base.cc
index 871b892..b9b4f91 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-base.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check-base.cc
@@ -225,7 +225,8 @@ TypeCheckBase::resolve_literal (const Analysis::NodeMapping &expr_mappings,
 
 	infered = new TyTy::ReferenceType (expr_mappings.get_hirid (),
 					   TyTy::TyVar (base->get_ref ()),
-					   Mutability::Imm);
+					   Mutability::Imm,
+					   TyTy::Region::make_static ());
       }
       break;
 
@@ -271,7 +272,8 @@ TypeCheckBase::resolve_literal (const Analysis::NodeMapping &expr_mappings,
 
 	infered = new TyTy::ReferenceType (expr_mappings.get_hirid (),
 					   TyTy::TyVar (array->get_ref ()),
-					   Mutability::Imm);
+					   Mutability::Imm,
+					   TyTy::Region::make_static ());
       }
       break;
 
@@ -352,16 +354,23 @@ TypeCheckBase::parse_repr_options (const AST::AttrVec &attrs, location_t locus)
 
 void
 TypeCheckBase::resolve_generic_params (
-  const std::vector<std::unique_ptr<HIR::GenericParam> > &generic_params,
+  const std::vector<std::unique_ptr<HIR::GenericParam>> &generic_params,
   std::vector<TyTy::SubstitutionParamMapping> &substitutions)
 {
   for (auto &generic_param : generic_params)
     {
-      switch (generic_param.get ()->get_kind ())
+      switch (generic_param->get_kind ())
 	{
-	case HIR::GenericParam::GenericKind::LIFETIME:
-	  // FIXME: Skipping Lifetime completely until better
-	  // handling.
+	  case HIR::GenericParam::GenericKind::LIFETIME: {
+	    auto lifetime_param
+	      = static_cast<HIR::LifetimeParam &> (*generic_param);
+	    auto lifetime = lifetime_param.get_lifetime ();
+	    rust_assert (lifetime.get_lifetime_type ()
+			 == AST::Lifetime::LifetimeType::NAMED);
+	    context->get_lifetime_resolver ().insert_mapping (
+	      context->intern_lifetime (lifetime));
+	  }
+
 	  break;
 
 	  case HIR::GenericParam::GenericKind::CONST: {
diff --git a/gcc/rust/typecheck/rust-hir-type-check-expr.cc b/gcc/rust/typecheck/rust-hir-type-check-expr.cc
index 43d183f..9f5042a 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-expr.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check-expr.cc
@@ -674,8 +674,9 @@ TypeCheckExpr::visit (HIR::RangeFromToExpr &expr)
   const TyTy::SubstitutionParamMapping *param_ref = &adt->get_substs ().at (0);
   subst_mappings.push_back (TyTy::SubstitutionArg (param_ref, unified));
 
-  TyTy::SubstitutionArgumentMappings subst (subst_mappings, {},
-					    expr.get_locus ());
+  TyTy::SubstitutionArgumentMappings subst (
+    subst_mappings, {}, adt->get_substitution_arguments ().get_regions (),
+    expr.get_locus ());
   infered = SubstMapperInternal::Resolve (adt, subst);
 }
 
@@ -721,8 +722,9 @@ TypeCheckExpr::visit (HIR::RangeFromExpr &expr)
   const TyTy::SubstitutionParamMapping *param_ref = &adt->get_substs ().at (0);
   subst_mappings.push_back (TyTy::SubstitutionArg (param_ref, from_ty));
 
-  TyTy::SubstitutionArgumentMappings subst (subst_mappings, {},
-					    expr.get_locus ());
+  TyTy::SubstitutionArgumentMappings subst (
+    subst_mappings, {}, adt->get_substitution_arguments ().get_regions (),
+    expr.get_locus ());
   infered = SubstMapperInternal::Resolve (adt, subst);
 }
 
@@ -767,8 +769,9 @@ TypeCheckExpr::visit (HIR::RangeToExpr &expr)
   const TyTy::SubstitutionParamMapping *param_ref = &adt->get_substs ().at (0);
   subst_mappings.push_back (TyTy::SubstitutionArg (param_ref, from_ty));
 
-  TyTy::SubstitutionArgumentMappings subst (subst_mappings, {},
-					    expr.get_locus ());
+  TyTy::SubstitutionArgumentMappings subst (
+    subst_mappings, {}, adt->get_substitution_arguments ().get_regions (),
+    expr.get_locus ());
   infered = SubstMapperInternal::Resolve (adt, subst);
 }
 
@@ -851,8 +854,9 @@ TypeCheckExpr::visit (HIR::RangeFromToInclExpr &expr)
   const TyTy::SubstitutionParamMapping *param_ref = &adt->get_substs ().at (0);
   subst_mappings.push_back (TyTy::SubstitutionArg (param_ref, unified));
 
-  TyTy::SubstitutionArgumentMappings subst (subst_mappings, {},
-					    expr.get_locus ());
+  TyTy::SubstitutionArgumentMappings subst (
+    subst_mappings, {}, adt->get_substitution_arguments ().get_regions (),
+    expr.get_locus ());
   infered = SubstMapperInternal::Resolve (adt, subst);
 }
 
@@ -1193,7 +1197,9 @@ TypeCheckExpr::visit (HIR::MethodCallExpr &expr)
 
   if (resolved_candidate.is_impl_candidate ())
     {
-      auto infer_arguments = TyTy::SubstitutionArgumentMappings::error ();
+      auto infer_arguments = TyTy::SubstitutionArgumentMappings::empty ();
+      infer_arguments.get_mut_regions ()
+	= fn->get_used_arguments ().get_regions ();
       HIR::ImplBlock &impl = *resolved_candidate.item.impl.parent;
       TyTy::BaseType *impl_self_infer
 	= TypeCheckItem::ResolveImplBlockSelfWithInference (impl,
diff --git a/gcc/rust/typecheck/rust-hir-type-check-implitem.cc b/gcc/rust/typecheck/rust-hir-type-check-implitem.cc
index 5fb6fa3..0ca59de 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-implitem.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check-implitem.cc
@@ -62,6 +62,8 @@ TypeCheckTopLevelExternItem::visit (HIR::ExternalStaticItem &item)
 void
 TypeCheckTopLevelExternItem::visit (HIR::ExternalFunctionItem &function)
 {
+  auto binder_pin = context->push_clean_lifetime_resolver ();
+
   std::vector<TyTy::SubstitutionParamMapping> substitutions;
   if (function.has_generics ())
     {
@@ -70,6 +72,11 @@ TypeCheckTopLevelExternItem::visit (HIR::ExternalFunctionItem &function)
 	  switch (generic_param.get ()->get_kind ())
 	    {
 	    case HIR::GenericParam::GenericKind::LIFETIME:
+	      context->intern_and_insert_lifetime (
+		static_cast<HIR::LifetimeParam &> (*generic_param)
+		  .get_lifetime ());
+	      // TODO: handle bounds
+	      break;
 	    case HIR::GenericParam::GenericKind::CONST:
 	      // FIXME: Skipping Lifetime and Const completely until better
 	      // handling.
@@ -153,11 +160,13 @@ TypeCheckTopLevelExternItem::visit (HIR::ExternalFunctionItem &function)
 			    function.get_item_name ().as_string ()),
     function.get_locus ()};
 
-  auto fnType = new TyTy::FnType (function.get_mappings ().get_hirid (),
-				  function.get_mappings ().get_defid (),
-				  function.get_item_name ().as_string (), ident,
-				  flags, parent.get_abi (), std::move (params),
-				  ret_type, std::move (substitutions));
+  auto fnType = new TyTy::FnType (
+    function.get_mappings ().get_hirid (),
+    function.get_mappings ().get_defid (),
+    function.get_item_name ().as_string (), ident, flags, parent.get_abi (),
+    std::move (params), ret_type, std::move (substitutions),
+    TyTy::SubstitutionArgumentMappings::empty (
+      context->get_lifetime_resolver ().get_num_bound_regions ()));
 
   context->insert_type (function.get_mappings (), fnType);
   resolved = fnType;
@@ -192,6 +201,8 @@ TypeCheckImplItem::Resolve (
 void
 TypeCheckImplItem::visit (HIR::Function &function)
 {
+  auto binder_pin = context->push_lifetime_binder ();
+
   if (function.has_generics ())
     resolve_generic_params (function.get_generic_params (), substitutions);
 
@@ -254,16 +265,36 @@ TypeCheckImplItem::visit (HIR::Function &function)
 	      self_type = self->clone ();
 	      break;
 
-	    case HIR::SelfParam::IMM_REF:
-	      self_type = new TyTy::ReferenceType (
-		self_param.get_mappings ().get_hirid (),
-		TyTy::TyVar (self->get_ref ()), Mutability::Imm);
+	      case HIR::SelfParam::IMM_REF: {
+		auto region = context->lookup_and_resolve_lifetime (
+		  self_param.get_lifetime ());
+		if (!region.has_value ())
+		  {
+		    rust_inform (self_param.get_locus (),
+				 "failed to resolve lifetime");
+		    region = TyTy::Region::make_anonymous (); // FIXME
+		  }
+		self_type = new TyTy::ReferenceType (
+		  self_param.get_mappings ().get_hirid (),
+		  TyTy::TyVar (self->get_ref ()), Mutability::Imm,
+		  region.value ());
+	      }
 	      break;
 
-	    case HIR::SelfParam::MUT_REF:
-	      self_type = new TyTy::ReferenceType (
-		self_param.get_mappings ().get_hirid (),
-		TyTy::TyVar (self->get_ref ()), Mutability::Mut);
+	      case HIR::SelfParam::MUT_REF: {
+		auto region = context->lookup_and_resolve_lifetime (
+		  self_param.get_lifetime ());
+		if (!region.has_value ())
+		  {
+		    rust_error_at (self_param.get_locus (),
+				   "failed to resolve lifetime");
+		    return;
+		  }
+		self_type = new TyTy::ReferenceType (
+		  self_param.get_mappings ().get_hirid (),
+		  TyTy::TyVar (self->get_ref ()), Mutability::Mut,
+		  region.value ());
+	      }
 	      break;
 
 	    default:
@@ -295,15 +326,15 @@ TypeCheckImplItem::visit (HIR::Function &function)
   rust_assert (ok);
 
   RustIdent ident{*canonical_path, function.get_locus ()};
-  auto fnType
-    = new TyTy::FnType (function.get_mappings ().get_hirid (),
-			function.get_mappings ().get_defid (),
-			function.get_function_name ().as_string (), ident,
-			function.is_method ()
-			  ? TyTy::FnType::FNTYPE_IS_METHOD_FLAG
+  auto fnType = new TyTy::FnType (
+    function.get_mappings ().get_hirid (),
+    function.get_mappings ().get_defid (),
+    function.get_function_name ().as_string (), ident,
+    function.is_method () ? TyTy::FnType::FNTYPE_IS_METHOD_FLAG
 			  : TyTy::FnType::FNTYPE_DEFAULT_FLAGS,
-			ABI::RUST, std::move (params), ret_type,
-			std::move (substitutions));
+    ABI::RUST, std::move (params), ret_type, std::move (substitutions),
+    TyTy::SubstitutionArgumentMappings::empty (
+      context->get_lifetime_resolver ().get_num_bound_regions ()));
 
   context->insert_type (function.get_mappings (), fnType);
   result = fnType;
@@ -348,6 +379,11 @@ TypeCheckImplItem::visit (HIR::ConstantItem &constant)
 void
 TypeCheckImplItem::visit (HIR::TypeAlias &alias)
 {
+  auto binder_pin = context->push_lifetime_binder ();
+
+  if (alias.has_generics ())
+    resolve_generic_params (alias.get_generic_params (), substitutions);
+
   TyTy::BaseType *actual_type
     = TypeCheckType::Resolve (alias.get_type_aliased ().get ());
 
diff --git a/gcc/rust/typecheck/rust-hir-type-check-implitem.h b/gcc/rust/typecheck/rust-hir-type-check-implitem.h
index 7db06c0..067465e 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-implitem.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-implitem.h
@@ -61,7 +61,7 @@ protected:
   TyTy::BaseType *self;
   std::vector<TyTy::SubstitutionParamMapping> substitutions;
 
-  TyTy::BaseType *result;
+  TyTy::BaseType *result = nullptr;
 };
 
 class TypeCheckImplItemWithTrait : public TypeCheckBase,
diff --git a/gcc/rust/typecheck/rust-hir-type-check-item.cc b/gcc/rust/typecheck/rust-hir-type-check-item.cc
index 0bf4d70..eb2698e 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-item.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check-item.cc
@@ -113,8 +113,11 @@ TypeCheckItem::ResolveImplBlockSelfWithInference (
     }
 
   // create argument mappings
-  *infer_arguments
-    = TyTy::SubstitutionArgumentMappings (std::move (args), {}, locus);
+  *infer_arguments = TyTy::SubstitutionArgumentMappings (
+    std::move (args), {},
+    TyTy::SubstitutionArgumentMappings::regions_from_nullable_args (
+      infer_arguments),
+    locus);
 
   TyTy::BaseType *infer = SubstMapperInternal::Resolve (self, *infer_arguments);
 
@@ -139,7 +142,7 @@ TypeCheckItem::visit (HIR::TypeAlias &alias)
 
   for (auto &where_clause_item : alias.get_where_clause ().get_items ())
     {
-      ResolveWhereClauseItem::Resolve (*where_clause_item.get ());
+      ResolveWhereClauseItem::Resolve (*where_clause_item);
     }
   infered = actual_type;
 }
@@ -147,13 +150,15 @@ TypeCheckItem::visit (HIR::TypeAlias &alias)
 void
 TypeCheckItem::visit (HIR::TupleStruct &struct_decl)
 {
+  auto lifetime_pin = context->push_clean_lifetime_resolver ();
+
   std::vector<TyTy::SubstitutionParamMapping> substitutions;
   if (struct_decl.has_generics ())
     resolve_generic_params (struct_decl.get_generic_params (), substitutions);
 
   for (auto &where_clause_item : struct_decl.get_where_clause ().get_items ())
     {
-      ResolveWhereClauseItem::Resolve (*where_clause_item.get ());
+      ResolveWhereClauseItem::Resolve (*where_clause_item);
     }
 
   std::vector<TyTy::StructFieldType *> fields;
@@ -162,7 +167,7 @@ TypeCheckItem::visit (HIR::TupleStruct &struct_decl)
     {
       TyTy::BaseType *field_type
 	= TypeCheckType::Resolve (field.get_field_type ().get ());
-      TyTy::StructFieldType *ty_field
+      auto *ty_field
 	= new TyTy::StructFieldType (field.get_mappings ().get_hirid (),
 				     std::to_string (idx), field_type,
 				     field.get_locus ());
@@ -192,12 +197,13 @@ TypeCheckItem::visit (HIR::TupleStruct &struct_decl)
   TyTy::ADTType::ReprOptions repr
     = parse_repr_options (attrs, struct_decl.get_locus ());
 
-  TyTy::BaseType *type
-    = new TyTy::ADTType (struct_decl.get_mappings ().get_hirid (),
-			 mappings->get_next_hir_id (),
-			 struct_decl.get_identifier ().as_string (), ident,
-			 TyTy::ADTType::ADTKind::TUPLE_STRUCT,
-			 std::move (variants), std::move (substitutions), repr);
+  TyTy::BaseType *type = new TyTy::ADTType (
+    struct_decl.get_mappings ().get_hirid (), mappings->get_next_hir_id (),
+    struct_decl.get_identifier ().as_string (), ident,
+    TyTy::ADTType::ADTKind::TUPLE_STRUCT, std::move (variants),
+    std::move (substitutions), repr,
+    TyTy::SubstitutionArgumentMappings::empty (
+      context->get_lifetime_resolver ().get_num_bound_regions ()));
 
   context->insert_type (struct_decl.get_mappings (), type);
   infered = type;
@@ -206,13 +212,15 @@ TypeCheckItem::visit (HIR::TupleStruct &struct_decl)
 void
 TypeCheckItem::visit (HIR::StructStruct &struct_decl)
 {
+  auto lifetime_pin = context->push_clean_lifetime_resolver ();
+
   std::vector<TyTy::SubstitutionParamMapping> substitutions;
   if (struct_decl.has_generics ())
     resolve_generic_params (struct_decl.get_generic_params (), substitutions);
 
   for (auto &where_clause_item : struct_decl.get_where_clause ().get_items ())
     {
-      ResolveWhereClauseItem::Resolve (*where_clause_item.get ());
+      ResolveWhereClauseItem::Resolve (*where_clause_item);
     }
 
   std::vector<TyTy::StructFieldType *> fields;
@@ -220,7 +228,7 @@ TypeCheckItem::visit (HIR::StructStruct &struct_decl)
     {
       TyTy::BaseType *field_type
 	= TypeCheckType::Resolve (field.get_field_type ().get ());
-      TyTy::StructFieldType *ty_field
+      auto *ty_field
 	= new TyTy::StructFieldType (field.get_mappings ().get_hirid (),
 				     field.get_field_name ().as_string (),
 				     field_type, field.get_locus ());
@@ -249,12 +257,13 @@ TypeCheckItem::visit (HIR::StructStruct &struct_decl)
   TyTy::ADTType::ReprOptions repr
     = parse_repr_options (attrs, struct_decl.get_locus ());
 
-  TyTy::BaseType *type
-    = new TyTy::ADTType (struct_decl.get_mappings ().get_hirid (),
-			 mappings->get_next_hir_id (),
-			 struct_decl.get_identifier ().as_string (), ident,
-			 TyTy::ADTType::ADTKind::STRUCT_STRUCT,
-			 std::move (variants), std::move (substitutions), repr);
+  TyTy::BaseType *type = new TyTy::ADTType (
+    struct_decl.get_mappings ().get_hirid (), mappings->get_next_hir_id (),
+    struct_decl.get_identifier ().as_string (), ident,
+    TyTy::ADTType::ADTKind::STRUCT_STRUCT, std::move (variants),
+    std::move (substitutions), repr,
+    TyTy::SubstitutionArgumentMappings::empty (
+      context->get_lifetime_resolver ().get_num_bound_regions ()));
 
   context->insert_type (struct_decl.get_mappings (), type);
   infered = type;
@@ -263,6 +272,7 @@ TypeCheckItem::visit (HIR::StructStruct &struct_decl)
 void
 TypeCheckItem::visit (HIR::Enum &enum_decl)
 {
+  auto lifetime_pin = context->push_clean_lifetime_resolver ();
   std::vector<TyTy::SubstitutionParamMapping> substitutions;
   if (enum_decl.has_generics ())
     resolve_generic_params (enum_decl.get_generic_params (), substitutions);
@@ -301,13 +311,14 @@ TypeCheckItem::visit (HIR::Enum &enum_decl)
 void
 TypeCheckItem::visit (HIR::Union &union_decl)
 {
+  auto lifetime_pin = context->push_clean_lifetime_resolver ();
   std::vector<TyTy::SubstitutionParamMapping> substitutions;
   if (union_decl.has_generics ())
     resolve_generic_params (union_decl.get_generic_params (), substitutions);
 
   for (auto &where_clause_item : union_decl.get_where_clause ().get_items ())
     {
-      ResolveWhereClauseItem::Resolve (*where_clause_item.get ());
+      ResolveWhereClauseItem::Resolve (*where_clause_item);
     }
 
   std::vector<TyTy::StructFieldType *> fields;
@@ -315,7 +326,7 @@ TypeCheckItem::visit (HIR::Union &union_decl)
     {
       TyTy::BaseType *variant_type
 	= TypeCheckType::Resolve (variant.get_field_type ().get ());
-      TyTy::StructFieldType *ty_variant
+      auto *ty_variant
 	= new TyTy::StructFieldType (variant.get_mappings ().get_hirid (),
 				     variant.get_field_name ().as_string (),
 				     variant_type, variant.get_locus ());
@@ -387,6 +398,8 @@ TypeCheckItem::visit (HIR::ConstantItem &constant)
 void
 TypeCheckItem::visit (HIR::ImplBlock &impl_block)
 {
+  auto binder_pin = context->push_clean_lifetime_resolver (true);
+
   bool failed_flag = false;
   std::vector<TyTy::SubstitutionParamMapping> substitutions
     = resolve_impl_block_substitutions (impl_block, failed_flag);
@@ -429,13 +442,14 @@ TypeCheckItem::resolve_impl_item (HIR::ImplBlock &impl_block,
 void
 TypeCheckItem::visit (HIR::Function &function)
 {
+  auto lifetime_pin = context->push_clean_lifetime_resolver ();
   std::vector<TyTy::SubstitutionParamMapping> substitutions;
   if (function.has_generics ())
     resolve_generic_params (function.get_generic_params (), substitutions);
 
   for (auto &where_clause_item : function.get_where_clause ().get_items ())
     {
-      ResolveWhereClauseItem::Resolve (*where_clause_item.get ());
+      ResolveWhereClauseItem::Resolve (*where_clause_item);
     }
 
   TyTy::BaseType *ret_type = nullptr;
@@ -463,8 +477,7 @@ TypeCheckItem::visit (HIR::Function &function)
     {
       // get the name as well required for later on
       auto param_tyty = TypeCheckType::Resolve (param.get_type ().get ());
-      params.push_back (std::pair<HIR::Pattern *, TyTy::BaseType *> (
-	param.get_param_name ().get (), param_tyty));
+      params.emplace_back (param.get_param_name ().get (), param_tyty);
 
       context->insert_type (param.get_mappings (), param_tyty);
       TypeCheckPattern::Resolve (param.get_param_name ().get (), param_tyty);
@@ -477,21 +490,25 @@ TypeCheckItem::visit (HIR::Function &function)
   rust_assert (ok);
 
   RustIdent ident{*canonical_path, function.get_locus ()};
-  auto fnType = new TyTy::FnType (function.get_mappings ().get_hirid (),
-				  function.get_mappings ().get_defid (),
-				  function.get_function_name ().as_string (),
-				  ident, TyTy::FnType::FNTYPE_DEFAULT_FLAGS,
-				  ABI::RUST, std::move (params), ret_type,
-				  std::move (substitutions));
 
-  context->insert_type (function.get_mappings (), fnType);
+  auto fn_type = new TyTy::FnType (
+    function.get_mappings ().get_hirid (),
+    function.get_mappings ().get_defid (),
+    function.get_function_name ().as_string (), ident,
+    TyTy::FnType::FNTYPE_DEFAULT_FLAGS, ABI::RUST, std::move (params), ret_type,
+    std::move (substitutions),
+    TyTy::SubstitutionArgumentMappings::empty (
+      context->get_lifetime_resolver ().get_num_bound_regions ()));
+
+  context->insert_type (function.get_mappings (), fn_type);
 
   // need to get the return type from this
-  TyTy::FnType *resolved_fn_type = fnType;
+  TyTy::FnType *resolved_fn_type = fn_type;
   auto expected_ret_tyty = resolved_fn_type->get_return_type ();
   context->push_return_type (TypeCheckContextItem (&function),
 			     expected_ret_tyty);
 
+  context->switch_to_fn_body ();
   auto block_expr_ty
     = TypeCheckExpr::Resolve (function.get_definition ().get ());
 
@@ -505,14 +522,14 @@ TypeCheckItem::visit (HIR::Function &function)
 
   context->pop_return_type ();
 
-  infered = fnType;
+  infered = fn_type;
 }
 
 void
 TypeCheckItem::visit (HIR::Module &module)
 {
   for (auto &item : module.get_items ())
-    TypeCheckItem::Resolve (*item.get ());
+    TypeCheckItem::Resolve (*item);
 }
 
 void
@@ -551,7 +568,7 @@ TypeCheckItem::resolve_impl_block_substitutions (HIR::ImplBlock &impl_block,
 
   for (auto &where_clause_item : impl_block.get_where_clause ().get_items ())
     {
-      ResolveWhereClauseItem::Resolve (*where_clause_item.get ());
+      ResolveWhereClauseItem::Resolve (*where_clause_item);
     }
 
   auto specified_bound = TyTy::TypeBoundPredicate::error ();
@@ -559,13 +576,13 @@ TypeCheckItem::resolve_impl_block_substitutions (HIR::ImplBlock &impl_block,
   if (impl_block.has_trait_ref ())
     {
       std::unique_ptr<HIR::TypePath> &ref = impl_block.get_trait_ref ();
-      trait_reference = TraitResolver::Resolve (*ref.get ());
+      trait_reference = TraitResolver::Resolve (*ref);
       rust_assert (!trait_reference->is_error ());
 
       // we don't error out here see: gcc/testsuite/rust/compile/traits2.rs
       // for example
       specified_bound
-	= get_predicate_from_bound (*ref.get (), impl_block.get_type ().get ());
+	= get_predicate_from_bound (*ref, impl_block.get_type ().get ());
     }
 
   TyTy::BaseType *self = TypeCheckType::Resolve (impl_block.get_type ().get ());
@@ -596,13 +613,13 @@ TypeCheckItem::validate_trait_impl_block (
   if (impl_block.has_trait_ref ())
     {
       std::unique_ptr<HIR::TypePath> &ref = impl_block.get_trait_ref ();
-      trait_reference = TraitResolver::Resolve (*ref.get ());
+      trait_reference = TraitResolver::Resolve (*ref);
       rust_assert (!trait_reference->is_error ());
 
       // we don't error out here see: gcc/testsuite/rust/compile/traits2.rs
       // for example
       specified_bound
-	= get_predicate_from_bound (*ref.get (), impl_block.get_type ().get ());
+	= get_predicate_from_bound (*ref, impl_block.get_type ().get ());
     }
 
   bool is_trait_impl_block = !trait_reference->is_error ();
@@ -637,17 +654,17 @@ TypeCheckItem::validate_trait_impl_block (
 	      std::string trait_item_name = trait_item_ref.get_identifier ();
 	      std::string impl_item_name
 		= implemented_trait_item->get_identifier ();
-	      found = trait_item_name.compare (impl_item_name) == 0;
+	      found = trait_item_name == impl_item_name;
 	      if (found)
 		break;
 	    }
 
 	  bool is_required_trait_item = !trait_item_ref.is_optional ();
 	  if (!found && is_required_trait_item)
-	    missing_trait_items.push_back (trait_item_ref);
+	    missing_trait_items.emplace_back (trait_item_ref);
 	}
 
-      if (missing_trait_items.size () > 0)
+      if (!missing_trait_items.empty ())
 	{
 	  std::string missing_items_buf;
 	  rich_location r (line_table, impl_block.get_locus ());
diff --git a/gcc/rust/typecheck/rust-hir-type-check-path.cc b/gcc/rust/typecheck/rust-hir-type-check-path.cc
index 7dfa936..ea7d842 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-path.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check-path.cc
@@ -141,8 +141,12 @@ TypeCheckExpr::visit (HIR::QualifiedPathInExpression &expr)
 	  infered = new TyTy::ErrorType (expr.get_mappings ().get_hirid ());
 	  return;
 	}
+      std::vector<TyTy::Region> regions;
+
       infered = SubstMapper::Resolve (infered, expr.get_locus (),
-				      &item_seg.get_generic_args ());
+				      &item_seg.get_generic_args (),
+				      context->regions_from_generic_args (
+					item_seg.get_generic_args ()));
     }
 
   // continue on as a path-in-expression
@@ -298,7 +302,9 @@ TypeCheckExpr::resolve_root_path (HIR::PathInExpression &expr, size_t *offset,
       if (seg.has_generic_args ())
 	{
 	  lookup = SubstMapper::Resolve (lookup, expr.get_locus (),
-					 &seg.get_generic_args ());
+					 &seg.get_generic_args (),
+					 context->regions_from_generic_args (
+					   seg.get_generic_args ()));
 	  if (lookup->get_kind () == TyTy::TypeKind::ERROR)
 	    return new TyTy::ErrorType (expr.get_mappings ().get_hirid ());
 	}
@@ -471,8 +477,10 @@ TypeCheckExpr::resolve_segments (NodeId root_resolved_node_id,
 
       if (seg.has_generic_args ())
 	{
-	  tyseg = SubstMapper::Resolve (tyseg, expr_locus,
-					&seg.get_generic_args ());
+	  tyseg
+	    = SubstMapper::Resolve (tyseg, expr_locus, &seg.get_generic_args (),
+				    context->regions_from_generic_args (
+				      seg.get_generic_args ()));
 	  if (tyseg->get_kind () == TyTy::TypeKind::ERROR)
 	    return;
 	}
diff --git a/gcc/rust/typecheck/rust-hir-type-check-type.cc b/gcc/rust/typecheck/rust-hir-type-check-type.cc
index 9519201..e7a86b9 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-type.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check-type.cc
@@ -70,6 +70,12 @@ TypeCheckType::Resolve (HIR::Type *type)
 void
 TypeCheckType::visit (HIR::BareFunctionType &fntype)
 {
+  auto binder_pin = context->push_lifetime_binder ();
+  for (auto &lifetime_param : fntype.get_for_lifetimes ())
+    {
+      context->intern_and_insert_lifetime (lifetime_param.get_lifetime ());
+    }
+
   TyTy::BaseType *return_type;
   if (fntype.has_return_type ())
     {
@@ -292,8 +298,11 @@ TypeCheckType::visit (HIR::QualifiedPathInType &path)
 		= new TyTy::ErrorType (path.get_mappings ().get_hirid ());
 	      return;
 	    }
-	  translated = SubstMapper::Resolve (translated, path.get_locus (),
-					     &generic_seg.get_generic_args ());
+	  translated
+	    = SubstMapper::Resolve (translated, path.get_locus (),
+				    &generic_seg.get_generic_args (),
+				    context->regions_from_generic_args (
+				      generic_seg.get_generic_args ()));
 	}
     }
 
@@ -425,8 +434,11 @@ TypeCheckType::resolve_root_path (HIR::TypePath &path, size_t *offset,
 	  HIR::TypePathSegmentGeneric *generic_segment
 	    = static_cast<HIR::TypePathSegmentGeneric *> (seg.get ());
 
+	  auto regions = context->regions_from_generic_args (
+	    generic_segment->get_generic_args ());
 	  lookup = SubstMapper::Resolve (lookup, path.get_locus (),
-					 &generic_segment->get_generic_args ());
+					 &generic_segment->get_generic_args (),
+					 regions);
 	  if (lookup->get_kind () == TyTy::TypeKind::ERROR)
 	    return new TyTy::ErrorType (seg->get_mappings ().get_hirid ());
 	}
@@ -434,7 +446,9 @@ TypeCheckType::resolve_root_path (HIR::TypePath &path, size_t *offset,
 	{
 	  HIR::GenericArgs empty
 	    = HIR::GenericArgs::create_empty (path.get_locus ());
-	  lookup = SubstMapper::Resolve (lookup, path.get_locus (), &empty);
+	  lookup
+	    = SubstMapper::Resolve (lookup, path.get_locus (), &empty,
+				    context->regions_from_generic_args (empty));
 	}
 
       *root_resolved_node_id = ref_node_id;
@@ -532,11 +546,26 @@ TypeCheckType::resolve_segments (
 
       if (seg->is_generic_segment ())
 	{
-	  HIR::TypePathSegmentGeneric *generic_segment
+	  auto *generic_segment
 	    = static_cast<HIR::TypePathSegmentGeneric *> (seg.get ());
 
+	  std::vector<TyTy::Region> regions;
+	  for (auto &lifetime :
+	       generic_segment->get_generic_args ().get_lifetime_args ())
+	    {
+	      auto region = context->lookup_and_resolve_lifetime (lifetime);
+	      if (!region.has_value ())
+		{
+		  rust_error_at (lifetime.get_locus (),
+				 "failed to resolve lifetime");
+		  return new TyTy::ErrorType (expr_id);
+		}
+	      regions.push_back (region.value ());
+	    }
+
 	  tyseg = SubstMapper::Resolve (tyseg, expr_locus,
-					&generic_segment->get_generic_args ());
+					&generic_segment->get_generic_args (),
+					regions);
 	  if (tyseg->get_kind () == TyTy::TypeKind::ERROR)
 	    return new TyTy::ErrorType (expr_id);
 	}
@@ -607,6 +636,12 @@ TypeCheckType::visit (HIR::TraitObjectType &type)
       HIR::TypeParamBound &b = *bound.get ();
       HIR::TraitBound &trait_bound = static_cast<HIR::TraitBound &> (b);
 
+      auto binder_pin = context->push_lifetime_binder ();
+      for (auto &lifetime_param : trait_bound.get_for_lifetimes ())
+	{
+	  context->intern_and_insert_lifetime (lifetime_param.get_lifetime ());
+	}
+
       TyTy::TypeBoundPredicate predicate = get_predicate_from_bound (
 	trait_bound.get_path (),
 	nullptr /*this will setup a PLACEHOLDER for self*/);
@@ -660,10 +695,18 @@ void
 TypeCheckType::visit (HIR::ReferenceType &type)
 {
   TyTy::BaseType *base = TypeCheckType::Resolve (type.get_base_type ().get ());
-  translated
-    = new TyTy::ReferenceType (type.get_mappings ().get_hirid (),
-			       TyTy::TyVar (base->get_ref ()), type.get_mut ());
-}
+  rust_assert (type.has_lifetime ());
+  auto region = context->lookup_and_resolve_lifetime (type.get_lifetime ());
+  if (!region.has_value ())
+    {
+      rust_error_at (type.get_locus (), "failed to resolve lifetime");
+      translated = new TyTy::ErrorType (type.get_mappings ().get_hirid ());
+      return;
+    }
+  translated = new TyTy::ReferenceType (type.get_mappings ().get_hirid (),
+					TyTy::TyVar (base->get_ref ()),
+					type.get_mut (), region.value ());
+} // namespace Resolver
 
 void
 TypeCheckType::visit (HIR::RawPointerType &type)
@@ -849,6 +892,9 @@ void
 ResolveWhereClauseItem::Resolve (HIR::WhereClauseItem &item)
 {
   ResolveWhereClauseItem resolver;
+
+  auto binder_pin = resolver.context->push_lifetime_binder ();
+
   switch (item.get_item_type ())
     {
     case HIR::WhereClauseItem::LIFETIME:
@@ -863,11 +909,34 @@ ResolveWhereClauseItem::Resolve (HIR::WhereClauseItem &item)
 
 void
 ResolveWhereClauseItem::visit (HIR::LifetimeWhereClauseItem &item)
-{}
+{
+  auto lhs = context->lookup_and_resolve_lifetime (item.get_lifetime ());
+  if (!lhs.has_value ())
+    {
+      rust_error_at (UNKNOWN_LOCATION, "failed to resolve lifetime");
+    }
+  for (auto &lifetime : item.get_lifetime_bounds ())
+    {
+      auto rhs_i = context->lookup_and_resolve_lifetime (lifetime);
+      if (!rhs_i.has_value ())
+	{
+	  rust_error_at (UNKNOWN_LOCATION, "failed to resolve lifetime");
+	}
+    }
+}
 
 void
 ResolveWhereClauseItem::visit (HIR::TypeBoundWhereClauseItem &item)
 {
+  auto binder_pin = context->push_lifetime_binder ();
+  if (item.has_for_lifetimes ())
+    {
+      for (auto &lifetime_param : item.get_for_lifetimes ())
+	{
+	  context->intern_and_insert_lifetime (lifetime_param.get_lifetime ());
+	}
+    }
+
   auto &binding_type_path = item.get_bound_type ();
   TyTy::BaseType *binding = TypeCheckType::Resolve (binding_type_path.get ());
 
@@ -879,7 +948,7 @@ ResolveWhereClauseItem::visit (HIR::TypeBoundWhereClauseItem &item)
       switch (bound->get_bound_type ())
 	{
 	  case HIR::TypeParamBound::BoundType::TRAITBOUND: {
-	    HIR::TraitBound *b = static_cast<HIR::TraitBound *> (bound.get ());
+	    auto *b = static_cast<HIR::TraitBound *> (bound.get ());
 
 	    TyTy::TypeBoundPredicate predicate
 	      = get_predicate_from_bound (b->get_path (),
@@ -888,6 +957,19 @@ ResolveWhereClauseItem::visit (HIR::TypeBoundWhereClauseItem &item)
 	      specified_bounds.push_back (std::move (predicate));
 	  }
 	  break;
+	  case HIR::TypeParamBound::BoundType::LIFETIME: {
+	    if (binding->is<TyTy::ParamType> ())
+	      {
+		auto *b = static_cast<HIR::Lifetime *> (bound.get ());
+		auto region = context->lookup_and_resolve_lifetime (*b);
+		if (!region.has_value ())
+		  {
+		    rust_error_at (UNKNOWN_LOCATION,
+				   "failed to resolve lifetime");
+		  }
+	      }
+	  }
+	  break;
 
 	default:
 	  break;
diff --git a/gcc/rust/typecheck/rust-hir-type-check.cc b/gcc/rust/typecheck/rust-hir-type-check.cc
index c8e223d..68d9681 100644
--- a/gcc/rust/typecheck/rust-hir-type-check.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check.cc
@@ -30,6 +30,39 @@ saw_errors (void);
 namespace Rust {
 namespace Resolver {
 
+tl::optional<TyTy::Region>
+TypeCheckContext::LifetimeResolver::resolve (const Lifetime &placeholder) const
+{
+  if (placeholder.is_static ())
+    return TyTy::Region::make_static ();
+
+  if (placeholder == Lifetime::anonymous_lifetime ())
+    return TyTy::Region::make_anonymous ();
+
+  for (auto it = lifetime_lookup.rbegin (); it != lifetime_lookup.rend (); ++it)
+    {
+      if (it->first == placeholder)
+	{
+	  if (it->second.scope <= ITEM_SCOPE)
+	    {
+	      // It is useful to have the static lifetime and named
+	      // lifetimed disjoint so we add the +1 here.
+	      return (is_body)
+		       ? TyTy::Region::make_named (it->second.index + 1)
+		       : TyTy::Region::make_early_bound (it->second.index);
+	    }
+	  else
+	    {
+	      return TyTy::Region::make_late_bound (get_current_scope ()
+						      - it->second.scope,
+						    it->second.index);
+	    }
+	}
+    }
+
+  return tl::nullopt;
+}
+
 void
 TypeResolution::Resolve (HIR::Crate &crate)
 {
@@ -151,6 +184,8 @@ TraitItemReference::get_type_from_constant (
 TyTy::BaseType *
 TraitItemReference::get_type_from_fn (/*const*/ HIR::TraitItemFunc &fn) const
 {
+  auto binder_pin = context->push_clean_lifetime_resolver ();
+
   std::vector<TyTy::SubstitutionParamMapping> substitutions
     = inherited_substitutions;
 
@@ -161,7 +196,15 @@ TraitItemReference::get_type_from_fn (/*const*/ HIR::TraitItemFunc &fn) const
 	{
 	  switch (generic_param.get ()->get_kind ())
 	    {
-	    case HIR::GenericParam::GenericKind::LIFETIME:
+	      case HIR::GenericParam::GenericKind::LIFETIME: {
+		auto lifetime_param
+		  = static_cast<HIR::LifetimeParam &> (*generic_param);
+
+		context->intern_and_insert_lifetime (
+		  lifetime_param.get_lifetime ());
+		// TODO: Handle lifetime bounds
+	      }
+	      break;
 	    case HIR::GenericParam::GenericKind::CONST:
 	      // FIXME: Skipping Lifetime and Const completely until better
 	      // handling.
@@ -234,15 +277,27 @@ TraitItemReference::get_type_from_fn (/*const*/ HIR::TraitItemFunc &fn) const
 	      break;
 
 	    case HIR::SelfParam::IMM_REF:
-	      self_type = new TyTy::ReferenceType (
-		self_param.get_mappings ().get_hirid (),
-		TyTy::TyVar (self->get_ref ()), Mutability::Imm);
-	      break;
-
-	    case HIR::SelfParam::MUT_REF:
-	      self_type = new TyTy::ReferenceType (
-		self_param.get_mappings ().get_hirid (),
-		TyTy::TyVar (self->get_ref ()), Mutability::Mut);
+	      case HIR::SelfParam::MUT_REF: {
+		auto mutability
+		  = self_param.get_self_kind () == HIR::SelfParam::IMM_REF
+		      ? Mutability::Imm
+		      : Mutability::Mut;
+		rust_assert (self_param.has_lifetime ());
+
+		auto maybe_region = context->lookup_and_resolve_lifetime (
+		  self_param.get_lifetime ());
+
+		if (!maybe_region.has_value ())
+		  {
+		    rust_error_at (self_param.get_locus (),
+				   "failed to resolve lifetime");
+		    return get_error ();
+		  }
+		self_type = new TyTy::ReferenceType (
+		  self_param.get_mappings ().get_hirid (),
+		  TyTy::TyVar (self->get_ref ()), mutability,
+		  maybe_region.value ());
+	      }
 	      break;
 
 	    default:
@@ -274,15 +329,14 @@ TraitItemReference::get_type_from_fn (/*const*/ HIR::TraitItemFunc &fn) const
   rust_assert (ok);
 
   RustIdent ident{*canonical_path, fn.get_locus ()};
-  auto resolved
-    = new TyTy::FnType (fn.get_mappings ().get_hirid (),
-			fn.get_mappings ().get_defid (),
-			function.get_function_name ().as_string (), ident,
-			function.is_method ()
-			  ? TyTy::FnType::FNTYPE_IS_METHOD_FLAG
+  auto resolved = new TyTy::FnType (
+    fn.get_mappings ().get_hirid (), fn.get_mappings ().get_defid (),
+    function.get_function_name ().as_string (), ident,
+    function.is_method () ? TyTy::FnType::FNTYPE_IS_METHOD_FLAG
 			  : TyTy::FnType::FNTYPE_DEFAULT_FLAGS,
-			ABI::RUST, std::move (params), ret_type, substitutions);
-
+    ABI::RUST, std::move (params), ret_type, substitutions,
+    TyTy::SubstitutionArgumentMappings::empty (
+      context->get_lifetime_resolver ().get_num_bound_regions ()));
   context->insert_type (fn.get_mappings (), resolved);
   return resolved;
 }
diff --git a/gcc/rust/typecheck/rust-hir-type-check.h b/gcc/rust/typecheck/rust-hir-type-check.h
index 0d74ae1..3d66e29 100644
--- a/gcc/rust/typecheck/rust-hir-type-check.h
+++ b/gcc/rust/typecheck/rust-hir-type-check.h
@@ -23,6 +23,7 @@
 #include "rust-tyty.h"
 #include "rust-hir-trait-reference.h"
 #include "rust-autoderef.h"
+#include "rust-tyty-region.h"
 
 #include <stack>
 
@@ -222,8 +223,14 @@ public:
   WARN_UNUSED_RESULT tl::optional<Lifetime>
   lookup_lifetime (const HIR::Lifetime &lifetime) const;
 
+  WARN_UNUSED_RESULT tl::optional<TyTy::Region>
+  lookup_and_resolve_lifetime (const HIR::Lifetime &lifetime) const;
+
   void intern_and_insert_lifetime (const HIR::Lifetime &lifetime);
 
+  WARN_UNUSED_RESULT std::vector<TyTy::Region>
+  regions_from_generic_args (const HIR::GenericArgs &args) const;
+
 private:
   TypeCheckContext ();
 
@@ -327,6 +334,9 @@ private:
 	{placeholder, {get_current_scope (), binder_size_stack.top ()++}});
     }
 
+    WARN_UNUSED_RESULT tl::optional<TyTy::Region>
+    resolve (const Lifetime &placeholder) const;
+
     /** Only to be used by the guard. */
     void push_binder () { binder_size_stack.push (0); }
     /** Only to be used by the guard. */
diff --git a/gcc/rust/typecheck/rust-substitution-mapper.cc b/gcc/rust/typecheck/rust-substitution-mapper.cc
index b2d58c4..394dfe4 100644
--- a/gcc/rust/typecheck/rust-substitution-mapper.cc
+++ b/gcc/rust/typecheck/rust-substitution-mapper.cc
@@ -23,15 +23,18 @@ namespace Rust {
 namespace Resolver {
 
 SubstMapper::SubstMapper (HirId ref, HIR::GenericArgs *generics,
+			  const std::vector<TyTy::Region> &regions,
 			  location_t locus)
-  : resolved (new TyTy::ErrorType (ref)), generics (generics), locus (locus)
+  : resolved (new TyTy::ErrorType (ref)), generics (generics),
+    regions (regions), locus (locus)
 {}
 
 TyTy::BaseType *
 SubstMapper::Resolve (TyTy::BaseType *base, location_t locus,
-		      HIR::GenericArgs *generics)
+		      HIR::GenericArgs *generics,
+		      const std::vector<TyTy::Region> &regions)
 {
-  SubstMapper mapper (base->get_ref (), generics, locus);
+  SubstMapper mapper (base->get_ref (), generics, regions, locus);
   base->accept_vis (mapper);
   rust_assert (mapper.resolved != nullptr);
   return mapper.resolved;
@@ -40,7 +43,7 @@ SubstMapper::Resolve (TyTy::BaseType *base, location_t locus,
 TyTy::BaseType *
 SubstMapper::InferSubst (TyTy::BaseType *base, location_t locus)
 {
-  return SubstMapper::Resolve (base, locus, nullptr);
+  return SubstMapper::Resolve (base, locus, nullptr, {});
 }
 
 bool
@@ -62,7 +65,7 @@ SubstMapper::visit (TyTy::FnType &type)
   else
     {
       TyTy::SubstitutionArgumentMappings mappings
-	= type.get_mappings_from_generic_args (*generics);
+	= type.get_mappings_from_generic_args (*generics, regions);
       if (mappings.is_error ())
 	return;
 
@@ -86,7 +89,7 @@ SubstMapper::visit (TyTy::ADTType &type)
   else
     {
       TyTy::SubstitutionArgumentMappings mappings
-	= type.get_mappings_from_generic_args (*generics);
+	= type.get_mappings_from_generic_args (*generics, regions);
       if (mappings.is_error ())
 	return;
 
@@ -101,7 +104,7 @@ void
 SubstMapper::visit (TyTy::PlaceholderType &type)
 {
   rust_assert (type.can_resolve ());
-  resolved = SubstMapper::Resolve (type.resolve (), locus, generics);
+  resolved = SubstMapper::Resolve (type.resolve (), locus, generics, regions);
 }
 
 void
@@ -117,7 +120,7 @@ SubstMapper::visit (TyTy::ProjectionType &type)
   else
     {
       TyTy::SubstitutionArgumentMappings mappings
-	= type.get_mappings_from_generic_args (*generics);
+	= type.get_mappings_from_generic_args (*generics, regions);
       if (mappings.is_error ())
 	return;
 
diff --git a/gcc/rust/typecheck/rust-substitution-mapper.h b/gcc/rust/typecheck/rust-substitution-mapper.h
index 0a816c7..13487cf 100644
--- a/gcc/rust/typecheck/rust-substitution-mapper.h
+++ b/gcc/rust/typecheck/rust-substitution-mapper.h
@@ -29,7 +29,9 @@ class SubstMapper : public TyTy::TyVisitor
 {
 public:
   static TyTy::BaseType *Resolve (TyTy::BaseType *base, location_t locus,
-				  HIR::GenericArgs *generics = nullptr);
+				  HIR::GenericArgs *generics = nullptr,
+				  const std::vector<TyTy::Region> &regions
+				  = {});
 
   static TyTy::BaseType *InferSubst (TyTy::BaseType *base, location_t locus);
 
@@ -63,10 +65,12 @@ public:
   void visit (TyTy::ClosureType &) override { rust_unreachable (); }
 
 private:
-  SubstMapper (HirId ref, HIR::GenericArgs *generics, location_t locus);
+  SubstMapper (HirId ref, HIR::GenericArgs *generics,
+	       const std::vector<TyTy::Region> &regions, location_t locus);
 
   TyTy::BaseType *resolved;
   HIR::GenericArgs *generics;
+  const std::vector<TyTy::Region> &regions;
   location_t locus;
 };
 
diff --git a/gcc/rust/typecheck/rust-typecheck-context.cc b/gcc/rust/typecheck/rust-typecheck-context.cc
index c6840c8..1f4a5a3 100644
--- a/gcc/rust/typecheck/rust-typecheck-context.cc
+++ b/gcc/rust/typecheck/rust-typecheck-context.cc
@@ -543,12 +543,39 @@ TypeCheckContext::lookup_lifetime (const HIR::Lifetime &lifetime) const
   rust_unreachable ();
 }
 
+WARN_UNUSED_RESULT tl::optional<TyTy::Region>
+TypeCheckContext::lookup_and_resolve_lifetime (
+  const HIR::Lifetime &lifetime) const
+{
+  auto maybe_interned = lookup_lifetime (lifetime);
+  if (!maybe_interned)
+    return tl::nullopt;
+
+  return get_lifetime_resolver ().resolve (maybe_interned.value ());
+}
 void
 TypeCheckContext::intern_and_insert_lifetime (const HIR::Lifetime &lifetime)
 {
   get_lifetime_resolver ().insert_mapping (intern_lifetime (lifetime));
 }
 
+WARN_UNUSED_RESULT std::vector<TyTy::Region>
+TypeCheckContext::regions_from_generic_args (const HIR::GenericArgs &args) const
+{
+  std::vector<TyTy::Region> regions;
+  for (const auto &lifetime : args.get_lifetime_args ())
+    {
+      auto resolved = lookup_and_resolve_lifetime (lifetime);
+      if (!resolved)
+	{
+	  rust_error_at (lifetime.get_locus (), "unresolved lifetime");
+	  return {};
+	}
+      regions.push_back (*resolved);
+    }
+  return regions;
+}
+
 // TypeCheckContextItem
 
 TypeCheckContextItem::Item::Item (HIR::Function *item) : item (item) {}
diff --git a/gcc/rust/typecheck/rust-tyty-bounds.cc b/gcc/rust/typecheck/rust-tyty-bounds.cc
index 6a87c05..066fe47 100644
--- a/gcc/rust/typecheck/rust-tyty-bounds.cc
+++ b/gcc/rust/typecheck/rust-tyty-bounds.cc
@@ -375,6 +375,7 @@ TypeBoundPredicate::TypeBoundPredicate (const TypeBoundPredicate &other)
 
   used_arguments
     = SubstitutionArgumentMappings (copied_arg_mappings, {},
+				    other.used_arguments.get_regions (),
 				    other.used_arguments.get_locus ());
 }
 
@@ -415,6 +416,7 @@ TypeBoundPredicate::operator= (const TypeBoundPredicate &other)
 
   used_arguments
     = SubstitutionArgumentMappings (copied_arg_mappings, {},
+				    other.used_arguments.get_regions (),
 				    other.used_arguments.get_locus ());
 
   return *this;
@@ -482,7 +484,10 @@ TypeBoundPredicate::apply_generic_arguments (HIR::GenericArgs *generic_args,
     }
 
   // now actually perform a substitution
-  used_arguments = get_mappings_from_generic_args (*generic_args);
+  used_arguments = get_mappings_from_generic_args (
+    *generic_args,
+    Resolver::TypeCheckContext::get ()->regions_from_generic_args (
+      *generic_args));
 
   error_flag |= used_arguments.is_error ();
   auto &subst_mappings = used_arguments;
@@ -590,6 +595,7 @@ TypeBoundPredicateItem::get_tyty_for_receiver (const TyTy::BaseType *receiver)
     }
 
   SubstitutionArgumentMappings adjusted (adjusted_mappings, {},
+					 gargs.get_regions (),
 					 gargs.get_locus (),
 					 gargs.get_subst_cb (),
 					 true /* trait-mode-flag */);
diff --git a/gcc/rust/typecheck/rust-tyty-subst.cc b/gcc/rust/typecheck/rust-tyty-subst.cc
index b71c918..fcb09d50 100644
--- a/gcc/rust/typecheck/rust-tyty-subst.cc
+++ b/gcc/rust/typecheck/rust-tyty-subst.cc
@@ -17,6 +17,8 @@
 // <http://www.gnu.org/licenses/>.
 
 #include "rust-tyty-subst.h"
+
+#include <utility>
 #include "rust-tyty.h"
 #include "rust-hir-type-check.h"
 #include "rust-substitution-mapper.h"
@@ -243,21 +245,34 @@ SubstitutionArg::as_string () const
 	 + (argument != nullptr ? ":" + argument->as_string () : "");
 }
 
+const RegionParamList &
+SubstitutionArgumentMappings::get_regions () const
+{
+  return regions;
+}
+
+RegionParamList &
+SubstitutionArgumentMappings::get_mut_regions ()
+{
+  return regions;
+}
+
 // SubstitutionArgumentMappings
 
 SubstitutionArgumentMappings::SubstitutionArgumentMappings (
   std::vector<SubstitutionArg> mappings,
-  std::map<std::string, BaseType *> binding_args, location_t locus,
-  ParamSubstCb param_subst_cb, bool trait_item_flag, bool error_flag)
-  : mappings (mappings), binding_args (binding_args), locus (locus),
-    param_subst_cb (param_subst_cb), trait_item_flag (trait_item_flag),
-    error_flag (error_flag)
+  std::map<std::string, BaseType *> binding_args, RegionParamList regions,
+  location_t locus, ParamSubstCb param_subst_cb, bool trait_item_flag,
+  bool error_flag)
+  : mappings (std::move (mappings)), binding_args (binding_args),
+    regions (regions), locus (locus), param_subst_cb (param_subst_cb),
+    trait_item_flag (trait_item_flag), error_flag (error_flag)
 {}
 
 SubstitutionArgumentMappings::SubstitutionArgumentMappings (
   const SubstitutionArgumentMappings &other)
   : mappings (other.mappings), binding_args (other.binding_args),
-    locus (other.locus), param_subst_cb (nullptr),
+    regions (other.regions), locus (other.locus), param_subst_cb (nullptr),
     trait_item_flag (other.trait_item_flag), error_flag (other.error_flag)
 {}
 
@@ -267,6 +282,7 @@ SubstitutionArgumentMappings::operator= (
 {
   mappings = other.mappings;
   binding_args = other.binding_args;
+  regions = other.regions;
   locus = other.locus;
   param_subst_cb = nullptr;
   trait_item_flag = other.trait_item_flag;
@@ -278,15 +294,15 @@ SubstitutionArgumentMappings::operator= (
 SubstitutionArgumentMappings
 SubstitutionArgumentMappings::error ()
 {
-  return SubstitutionArgumentMappings ({}, {}, UNDEF_LOCATION, nullptr, false,
-				       true);
+  return SubstitutionArgumentMappings ({}, {}, 0, UNDEF_LOCATION, nullptr,
+				       false, true);
 }
 
 SubstitutionArgumentMappings
-SubstitutionArgumentMappings::empty ()
+SubstitutionArgumentMappings::empty (size_t num_regions)
 {
-  return SubstitutionArgumentMappings ({}, {}, UNDEF_LOCATION, nullptr, false,
-				       false);
+  return SubstitutionArgumentMappings ({}, {}, num_regions, UNDEF_LOCATION,
+				       nullptr, false, false);
 }
 
 bool
@@ -297,12 +313,12 @@ SubstitutionArgumentMappings::is_error () const
 
 bool
 SubstitutionArgumentMappings::get_argument_for_symbol (
-  const ParamType *param_to_find, SubstitutionArg *argument)
+  const ParamType *param_to_find, SubstitutionArg *argument) const
 {
-  for (auto &mapping : mappings)
+  for (const auto &mapping : mappings)
     {
       const ParamType *p = mapping.get_param_ty ();
-      if (p->get_symbol ().compare (param_to_find->get_symbol ()) == 0)
+      if (p->get_symbol () == param_to_find->get_symbol ())
 	{
 	  *argument = mapping;
 	  return true;
@@ -310,6 +326,18 @@ SubstitutionArgumentMappings::get_argument_for_symbol (
     }
   return false;
 }
+tl::optional<size_t>
+SubstitutionArgumentMappings::find_symbol (const ParamType &param_to_find) const
+{
+  auto it = std::find_if (mappings.begin (), mappings.end (),
+			  [param_to_find] (const SubstitutionArg &arg) {
+			    return arg.get_param_ty ()->get_symbol ()
+				   == param_to_find.get_symbol ();
+			  });
+  if (it == mappings.end ())
+    return tl::nullopt;
+  return std::distance (mappings.begin (), it);
+}
 
 bool
 SubstitutionArgumentMappings::get_argument_at (size_t index,
@@ -461,6 +489,16 @@ SubstitutionRef::get_num_substitutions () const
 {
   return substitutions.size ();
 }
+size_t
+SubstitutionRef::get_num_lifetime_params () const
+{
+  return used_arguments.get_regions ().size ();
+}
+size_t
+SubstitutionRef::get_num_type_params () const
+{
+  return get_num_substitutions ();
+}
 
 std::vector<SubstitutionParamMapping> &
 SubstitutionRef::get_substs ()
@@ -497,12 +535,9 @@ SubstitutionRef::override_context ()
 bool
 SubstitutionRef::needs_substitution () const
 {
-  for (auto &sub : substitutions)
-    {
-      if (sub.need_substitution ())
-	return true;
-    }
-  return false;
+  return std::any_of (substitutions.begin (), substitutions.end (),
+		      std::mem_fn (
+			&SubstitutionParamMapping::needs_substitution));
 }
 
 bool
@@ -547,14 +582,15 @@ SubstitutionRef::min_required_substitutions () const
   return n;
 }
 
-SubstitutionArgumentMappings
+const SubstitutionArgumentMappings &
 SubstitutionRef::get_used_arguments () const
 {
   return used_arguments;
 }
 
 SubstitutionArgumentMappings
-SubstitutionRef::get_mappings_from_generic_args (HIR::GenericArgs &args)
+SubstitutionRef::get_mappings_from_generic_args (
+  HIR::GenericArgs &args, const std::vector<Region> &regions)
 {
   std::map<std::string, BaseType *> binding_arguments;
   if (args.get_binding_args ().size () > 0)
@@ -672,9 +708,9 @@ SubstitutionRef::get_mappings_from_generic_args (HIR::GenericArgs &args)
 	  // this resolved default might already contain default parameters
 	  if (!resolved->is_concrete ())
 	    {
-	      SubstitutionArgumentMappings intermediate (mappings,
-							 binding_arguments,
-							 args.get_locus ());
+	      SubstitutionArgumentMappings intermediate (
+		mappings, binding_arguments,
+		{used_arguments.get_regions ().size ()}, args.get_locus ());
 	      resolved = Resolver::SubstMapperInternal::Resolve (resolved,
 								 intermediate);
 
@@ -687,8 +723,10 @@ SubstitutionRef::get_mappings_from_generic_args (HIR::GenericArgs &args)
 	}
     }
 
-  return SubstitutionArgumentMappings (mappings, binding_arguments,
-				       args.get_locus ());
+  return {mappings, binding_arguments,
+	  RegionParamList::from_subst (used_arguments.get_regions ().size (),
+				       regions),
+	  args.get_locus ()};
 }
 
 BaseType *
@@ -727,6 +765,7 @@ SubstitutionRef::infer_substitions (location_t locus)
 
   SubstitutionArgumentMappings infer_arguments (std::move (args),
 						{} /* binding_arguments */,
+						used_arguments.get_regions (),
 						locus);
   return handle_substitions (infer_arguments);
 }
@@ -773,6 +812,7 @@ SubstitutionRef::adjust_mappings_for_this (
 
   return SubstitutionArgumentMappings (resolved_mappings,
 				       mappings.get_binding_args (),
+				       mappings.get_regions (),
 				       mappings.get_locus (),
 				       mappings.get_subst_cb (),
 				       mappings.trait_item_mode ());
@@ -840,6 +880,7 @@ SubstitutionRef::solve_mappings_from_receiver_for_self (
 
   return SubstitutionArgumentMappings (resolved_mappings,
 				       mappings.get_binding_args (),
+				       mappings.get_regions (),
 				       mappings.get_locus ());
 }
 
diff --git a/gcc/rust/typecheck/rust-tyty-subst.h b/gcc/rust/typecheck/rust-tyty-subst.h
index d9d179d..dbabff3 100644
--- a/gcc/rust/typecheck/rust-tyty-subst.h
+++ b/gcc/rust/typecheck/rust-tyty-subst.h
@@ -23,6 +23,9 @@
 #include "rust-location.h"
 #include "rust-hir-full-decls.h"
 #include "rust-tyty-bounds.h"
+#include "rust-tyty-region.h"
+
+#include <optional.h>
 
 namespace Rust {
 namespace TyTy {
@@ -69,6 +72,61 @@ private:
   ParamType *param;
 };
 
+/**
+ * Represents the part of the parameter list that contains lifetime
+ * parameters.
+ *
+ * ```
+ * Foo<'a, 'b, i32, 8>
+ *     ^^^^^^
+ * ```
+ *
+ * It has fixed size based on the number of lifetime parameters and they are
+ * indexed based on their order.
+ *
+ * All regions are initially set to unresolved. When type instantiation is
+ * encountered, all explicitly mentioned lifetimes are resolved to bound
+ * lifetimes. The remaining unresolved lifetimes are set to anonymous. During
+ * BIR construction, all lifetimes are replaced with free region variables.
+ * Inference of anonymous regions happens automatically using BIR subtyping
+ * pass.
+ */
+class RegionParamList
+{
+  std::vector<Region> regions;
+
+public:
+  RegionParamList (size_t num_regions) : regions (num_regions) {}
+
+  Region *begin () { return regions.data (); }
+  Region *end () { return regions.data () + regions.size (); }
+  Region &operator[] (size_t index) { return regions.at (index); }
+  const Region &operator[] (size_t index) const { return regions.at (index); }
+  WARN_UNUSED_RESULT const Region *begin () const { return regions.data (); }
+  WARN_UNUSED_RESULT const Region *end () const
+  {
+    return regions.data () + regions.size ();
+  }
+  size_t size () const { return regions.size (); }
+
+  /**
+   * Takes regions from the `subst` parameter and fills the rest with anonymous
+   * regions.
+   */
+  static RegionParamList from_subst (size_t num_regions,
+				     std::vector<Region> subst)
+  {
+    RegionParamList list (num_regions);
+    for (size_t i = 0; i < subst.size (); i++)
+      list.regions.at (i) = subst.at (i);
+    for (size_t i = subst.size (); i < num_regions; i++)
+      {
+	list.regions.at (i) = Region::make_anonymous ();
+      }
+    return list;
+  }
+};
+
 class SubstitutionArg
 {
 public:
@@ -110,7 +168,7 @@ class SubstitutionArgumentMappings
 public:
   SubstitutionArgumentMappings (std::vector<SubstitutionArg> mappings,
 				std::map<std::string, BaseType *> binding_args,
-				location_t locus,
+				RegionParamList regions, location_t locus,
 				ParamSubstCb param_subst_cb = nullptr,
 				bool trait_item_flag = false,
 				bool error_flag = false);
@@ -124,12 +182,26 @@ public:
     = default;
 
   static SubstitutionArgumentMappings error ();
-  static SubstitutionArgumentMappings empty ();
+
+  /** Creates empty substitution argument mappings with unresolved regions */
+  static SubstitutionArgumentMappings empty (size_t num_regions = 0);
+
+  static RegionParamList
+  regions_from_nullable_args (SubstitutionArgumentMappings *args)
+  {
+    if (args == nullptr)
+      return RegionParamList (0);
+
+    return args->get_regions ();
+  }
 
   bool is_error () const;
 
   bool get_argument_for_symbol (const ParamType *param_to_find,
-				SubstitutionArg *argument);
+				SubstitutionArg *argument) const;
+
+  /** Return type parameter index for symbol */
+  tl::optional<size_t> find_symbol (const ParamType &param_to_find) const;
 
   bool get_argument_at (size_t index, SubstitutionArg *argument);
 
@@ -152,6 +224,9 @@ public:
 
   const std::map<std::string, BaseType *> &get_binding_args () const;
 
+  const RegionParamList &get_regions () const;
+  RegionParamList &get_mut_regions ();
+
   std::string as_string () const;
 
   void on_param_subst (const ParamType &p, const SubstitutionArg &a) const;
@@ -163,6 +238,7 @@ public:
 private:
   std::vector<SubstitutionArg> mappings;
   std::map<std::string, BaseType *> binding_args;
+  RegionParamList regions;
   location_t locus;
   ParamSubstCb param_subst_cb;
   bool trait_item_flag;
@@ -193,6 +269,10 @@ public:
 
   size_t get_num_substitutions () const;
 
+  size_t get_num_lifetime_params () const;
+
+  size_t get_num_type_params () const;
+
   std::vector<SubstitutionParamMapping> &get_substs ();
 
   const std::vector<SubstitutionParamMapping> &get_substs () const;
@@ -221,7 +301,8 @@ public:
   // 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);
+  get_mappings_from_generic_args (HIR::GenericArgs &args,
+				  const std::vector<Region> &regions);
 
   // Recursive substitutions
   // Foo <A,B> { a:A, b: B}; Bar <X,Y,Z>{a:X, b: Foo<Y,Z>}
@@ -318,7 +399,10 @@ public:
   virtual BaseType *handle_substitions (SubstitutionArgumentMappings &mappings)
     = 0;
 
-  SubstitutionArgumentMappings get_used_arguments () const;
+  WARN_UNUSED_RESULT const SubstitutionArgumentMappings &
+  get_used_arguments () const;
+
+  WARN_UNUSED_RESULT tl::optional<SubstitutionArg> get_arg_at (size_t i) const;
 
 protected:
   std::vector<SubstitutionParamMapping> substitutions;
diff --git a/gcc/rust/typecheck/rust-tyty.cc b/gcc/rust/typecheck/rust-tyty.cc
index f1789f0..890d079 100644
--- a/gcc/rust/typecheck/rust-tyty.cc
+++ b/gcc/rust/typecheck/rust-tyty.cc
@@ -572,7 +572,8 @@ BaseType::monomorphized_clone () const
     {
       TyVar elm = ref->get_var_element_type ().monomorphized_clone ();
       return new ReferenceType (ref->get_ref (), ref->get_ty_ref (), elm,
-				ref->mutability (), ref->get_combined_refs ());
+				ref->mutability (), ref->get_region (),
+				ref->get_combined_refs ());
     }
   else if (auto tuple = x->try_as<const TupleType> ())
     {
@@ -594,7 +595,8 @@ BaseType::monomorphized_clone () const
       return new FnType (fn->get_ref (), fn->get_ty_ref (), fn->get_id (),
 			 fn->get_identifier (), fn->ident, fn->get_flags (),
 			 fn->get_abi (), std::move (cloned_params), retty,
-			 fn->clone_substs (), fn->get_combined_refs ());
+			 fn->clone_substs (), fn->get_substitution_arguments (),
+			 fn->get_combined_refs ());
     }
   else if (auto fn = x->try_as<const FnPtr> ())
     {
@@ -977,6 +979,7 @@ InferType::default_type (BaseType **type) const
   auto context = Resolver::TypeCheckContext::get ();
   bool ok = false;
 
+  // NOTE: Calling this error is misleading.
   if (default_hint.kind == TypeKind::ERROR)
     {
       switch (infer_kind)
@@ -1955,7 +1958,7 @@ FnType::clone () const
   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 ());
+		     get_substitution_arguments (), get_combined_refs ());
 }
 
 FnType *
@@ -2848,19 +2851,20 @@ CharType::clone () const
 // Reference Type
 
 ReferenceType::ReferenceType (HirId ref, TyVar base, Mutability mut,
-			      std::set<HirId> refs)
+			      Region region, std::set<HirId> refs)
   : BaseType (ref, ref, KIND,
 	      {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
-	      refs),
-    base (base), mut (mut)
+	      std::move (refs)),
+    base (base), mut (mut), region (region)
 {}
 
 ReferenceType::ReferenceType (HirId ref, HirId ty_ref, TyVar base,
-			      Mutability mut, std::set<HirId> refs)
+			      Mutability mut, Region region,
+			      std::set<HirId> refs)
   : BaseType (ref, ty_ref, KIND,
 	      {Resolver::CanonicalPath::create_empty (), BUILTINS_LOCATION},
-	      refs),
-    base (base), mut (mut)
+	      std::move (refs)),
+    base (base), mut (mut), region (region)
 {}
 
 Mutability
@@ -2874,6 +2878,11 @@ ReferenceType::is_mutable () const
 {
   return mut == Mutability::Mut;
 }
+Region
+ReferenceType::get_region () const
+{
+  return region;
+}
 
 bool
 ReferenceType::is_dyn_object () const
@@ -2982,7 +2991,7 @@ BaseType *
 ReferenceType::clone () const
 {
   return new ReferenceType (get_ref (), get_ty_ref (), base, mutability (),
-			    get_combined_refs ());
+			    get_region (), get_combined_refs ());
 }
 
 ReferenceType *
diff --git a/gcc/rust/typecheck/rust-tyty.h b/gcc/rust/typecheck/rust-tyty.h
index b04048f..7384c40 100644
--- a/gcc/rust/typecheck/rust-tyty.h
+++ b/gcc/rust/typecheck/rust-tyty.h
@@ -26,6 +26,9 @@
 #include "rust-tyty-bounds.h"
 #include "rust-tyty-util.h"
 #include "rust-tyty-subst.h"
+#include "rust-tyty-region.h"
+
+#include <limits>
 
 namespace Rust {
 
@@ -770,10 +773,10 @@ public:
 	  uint8_t flags, ABI abi,
 	  std::vector<std::pair<HIR::Pattern *, BaseType *>> params,
 	  BaseType *type, std::vector<SubstitutionParamMapping> subst_refs,
+	  SubstitutionArgumentMappings substitution_argument_mappings,
 	  std::set<HirId> refs = std::set<HirId> ())
     : CallableTypeInterface (ref, ref, TypeKind::FNDEF, ident, refs),
-      SubstitutionRef (std::move (subst_refs),
-		       SubstitutionArgumentMappings::error ()),
+      SubstitutionRef (std::move (subst_refs), substitution_argument_mappings),
       params (std::move (params)), type (type), flags (flags),
       identifier (identifier), id (id), abi (abi)
   {
@@ -785,10 +788,10 @@ public:
 	  RustIdent ident, uint8_t flags, ABI abi,
 	  std::vector<std::pair<HIR::Pattern *, BaseType *>> params,
 	  BaseType *type, std::vector<SubstitutionParamMapping> subst_refs,
+	  SubstitutionArgumentMappings substitution_argument_mappings,
 	  std::set<HirId> refs = std::set<HirId> ())
     : CallableTypeInterface (ref, ty_ref, TypeKind::FNDEF, ident, refs),
-      SubstitutionRef (std::move (subst_refs),
-		       SubstitutionArgumentMappings::error ()),
+      SubstitutionRef (std::move (subst_refs), substitution_argument_mappings),
       params (params), type (type), flags (flags), identifier (identifier),
       id (id), abi (abi)
   {
@@ -977,7 +980,7 @@ public:
 	       = std::vector<TypeBoundPredicate> ())
     : CallableTypeInterface (ref, ty_ref, TypeKind::CLOSURE, ident, refs),
       SubstitutionRef (std::move (subst_refs),
-		       SubstitutionArgumentMappings::error ()),
+		       SubstitutionArgumentMappings::error ()), // TODO
       parameters (parameters), result_type (std::move (result_type)), id (id),
       captures (captures)
   {
@@ -1365,11 +1368,13 @@ public:
 class ReferenceType : public BaseType
 {
 public:
-  static constexpr auto KIND = TypeKind::REF;
+  static constexpr auto KIND = REF;
 
   ReferenceType (HirId ref, TyVar base, Mutability mut,
+		 Region region = Region::make_anonymous (),
 		 std::set<HirId> refs = std::set<HirId> ());
   ReferenceType (HirId ref, HirId ty_ref, TyVar base, Mutability mut,
+		 Region region = Region::make_anonymous (),
 		 std::set<HirId> refs = std::set<HirId> ());
 
   BaseType *get_base () const;
@@ -1393,6 +1398,9 @@ public:
   Mutability mutability () const;
   bool is_mutable () const;
 
+  WARN_UNUSED_RESULT Region get_region () const;
+  void set_region (Region region);
+
   bool is_dyn_object () const;
   bool is_dyn_slice_type (const TyTy::SliceType **slice = nullptr) const;
   bool is_dyn_str_type (const TyTy::StrType **str = nullptr) const;
@@ -1401,6 +1409,7 @@ public:
 private:
   TyVar base;
   Mutability mut;
+  Region region;
 };
 
 class PointerType : public BaseType