compiler/rustc_traits/src/chalk/lowering.rs

   1 //! Contains the logic to lower rustc types into Chalk types
   2 //!
   3 //! In many cases there is a 1:1 relationship between a rustc type and a Chalk type.
   4 //! For example, a `SubstsRef` maps almost directly to a `Substitution`. In some
   5 //! other cases, such as `Param`s, there is no Chalk type, so we have to handle
   6 //! accordingly.
   7 //!
   8 //! ## `Ty` lowering
   9 //! Much of the `Ty` lowering is 1:1 with Chalk. (Or will be eventually). A
  10 //! helpful table for what types lower to what can be found in the
  11 //! [Chalk book](http://rust-lang.github.io/chalk/book/types/rust_types.html).
  12 //! The most notable difference lies with `Param`s. To convert from rustc to
  13 //! Chalk, we eagerly and deeply convert `Param`s to placeholders (in goals) or
  14 //! bound variables (for clause generation through functions in `db`).
  15 //!
  16 //! ## `Region` lowering
  17 //! Regions are handled in rustc and Chalk is quite differently. In rustc, there
  18 //! is a difference between "early bound" and "late bound" regions, where only
  19 //! the late bound regions have a `DebruijnIndex`. Moreover, in Chalk all
  20 //! regions (Lifetimes) have an associated index. In rustc, only `BrAnon`s have
  21 //! an index, whereas `BrNamed` don't. In order to lower regions to Chalk, we
  22 //! convert all regions into `BrAnon` late-bound regions.
  23 //!
  24 //! ## `Const` lowering
  25 //! Chalk doesn't handle consts currently, so consts are currently lowered to
  26 //! an empty tuple.
  27 //!
  28 //! ## Bound variable collection
  29 //! Another difference between rustc and Chalk lies in the handling of binders.
  30 //! Chalk requires that we store the bound parameter kinds, whereas rustc does
  31 //! not. To lower anything wrapped in a `Binder`, we first deeply find any bound
  32 //! variables from the current `Binder`.
  33
  34 use rustc_ast::ast;
  35 use rustc_middle::traits::{ChalkEnvironmentAndGoal, ChalkRustInterner as RustInterner};
  36 use rustc_middle::ty::fold::TypeFolder;
  37 use rustc_middle::ty::subst::{GenericArg, GenericArgKind, SubstsRef};
  38 use rustc_middle::ty::{self, Binder, Region, RegionKind, Ty, TyCtxt, TypeFoldable, TypeVisitor};
  39 use rustc_span::def_id::DefId;
  40
  41 use chalk_ir::{FnSig, ForeignDefId};
  42 use rustc_hir::Unsafety;
  43 use std::collections::btree_map::{BTreeMap, Entry};
  44 use std::ops::ControlFlow;
  45
  46 /// Essentially an `Into` with a `&RustInterner` parameter
  47 crate trait LowerInto<'tcx, T> {
  48     /// Lower a rustc construct (e.g., `ty::TraitPredicate`) to a chalk type, consuming `self`.
  49     fn lower_into(self, interner: &RustInterner<'tcx>) -> T;
  50 }
  51
  52 impl<'tcx> LowerInto<'tcx, chalk_ir::Substitution<RustInterner<'tcx>>> for SubstsRef<'tcx> {
  53     fn lower_into(
  54         self,
  55         interner: &RustInterner<'tcx>,
  56     ) -> chalk_ir::Substitution<RustInterner<'tcx>> {
  57         chalk_ir::Substitution::from_iter(interner, self.iter().map(|s| s.lower_into(interner)))
  58     }
  59 }
  60
  61 impl<'tcx> LowerInto<'tcx, SubstsRef<'tcx>> for &chalk_ir::Substitution<RustInterner<'tcx>> {
  62     fn lower_into(self, interner: &RustInterner<'tcx>) -> SubstsRef<'tcx> {
  63         interner.tcx.mk_substs(self.iter(interner).map(|subst| subst.lower_into(interner)))
  64     }
  65 }
  66
  67 impl<'tcx> LowerInto<'tcx, chalk_ir::AliasTy<RustInterner<'tcx>>> for ty::ProjectionTy<'tcx> {
  68     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::AliasTy<RustInterner<'tcx>> {
  69         chalk_ir::AliasTy::Projection(chalk_ir::ProjectionTy {
  70             associated_ty_id: chalk_ir::AssocTypeId(self.item_def_id),
  71             substitution: self.substs.lower_into(interner),
  72         })
  73     }
  74 }
  75
  76 impl<'tcx> LowerInto<'tcx, chalk_ir::InEnvironment<chalk_ir::Goal<RustInterner<'tcx>>>>
  77     for ChalkEnvironmentAndGoal<'tcx>
  78 {
  79     fn lower_into(
  80         self,
  81         interner: &RustInterner<'tcx>,
  82     ) -> chalk_ir::InEnvironment<chalk_ir::Goal<RustInterner<'tcx>>> {
  83         let clauses = self.environment.into_iter().map(|predicate| {
  84             let (predicate, binders, _named_regions) = collect_bound_vars(
  85                 interner,
  86                 interner.tcx,
  87                 predicate.bound_atom_with_opt_escaping(interner.tcx),
  88             );
  89             let consequence = match predicate {
  90                 ty::PredicateAtom::TypeWellFormedFromEnv(ty) => {
  91                     chalk_ir::DomainGoal::FromEnv(chalk_ir::FromEnv::Ty(ty.lower_into(interner)))
  92                 }
  93                 ty::PredicateAtom::Trait(predicate, _) => chalk_ir::DomainGoal::FromEnv(
  94                     chalk_ir::FromEnv::Trait(predicate.trait_ref.lower_into(interner)),
  95                 ),
  96                 ty::PredicateAtom::RegionOutlives(predicate) => chalk_ir::DomainGoal::Holds(
  97                     chalk_ir::WhereClause::LifetimeOutlives(chalk_ir::LifetimeOutlives {
  98                         a: predicate.0.lower_into(interner),
  99                         b: predicate.1.lower_into(interner),
 100                     }),
 101                 ),
 102                 ty::PredicateAtom::TypeOutlives(predicate) => chalk_ir::DomainGoal::Holds(
 103                     chalk_ir::WhereClause::TypeOutlives(chalk_ir::TypeOutlives {
 104                         ty: predicate.0.lower_into(interner),
 105                         lifetime: predicate.1.lower_into(interner),
 106                     }),
 107                 ),
 108                 ty::PredicateAtom::Projection(predicate) => chalk_ir::DomainGoal::Holds(
 109                     chalk_ir::WhereClause::AliasEq(predicate.lower_into(interner)),
 110                 ),
 111                 ty::PredicateAtom::WellFormed(..)
 112                 | ty::PredicateAtom::ObjectSafe(..)
 113                 | ty::PredicateAtom::ClosureKind(..)
 114                 | ty::PredicateAtom::Subtype(..)
 115                 | ty::PredicateAtom::ConstEvaluatable(..)
 116                 | ty::PredicateAtom::ConstEquate(..) => bug!("unexpected predicate {}", predicate),
 117             };
 118             let value = chalk_ir::ProgramClauseImplication {
 119                 consequence,
 120                 conditions: chalk_ir::Goals::empty(interner),
 121                 priority: chalk_ir::ClausePriority::High,
 122                 constraints: chalk_ir::Constraints::empty(interner),
 123             };
 124             chalk_ir::ProgramClauseData(chalk_ir::Binders::new(binders, value)).intern(interner)
 125         });
 126
 127         let goal: chalk_ir::GoalData<RustInterner<'tcx>> = self.goal.lower_into(&interner);
 128         chalk_ir::InEnvironment {
 129             environment: chalk_ir::Environment {
 130                 clauses: chalk_ir::ProgramClauses::from_iter(&interner, clauses),
 131             },
 132             goal: goal.intern(&interner),
 133         }
 134     }
 135 }
 136
 137 impl<'tcx> LowerInto<'tcx, chalk_ir::GoalData<RustInterner<'tcx>>> for ty::Predicate<'tcx> {
 138     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::GoalData<RustInterner<'tcx>> {
 139         let (predicate, binders, _named_regions) = collect_bound_vars(
 140             interner,
 141             interner.tcx,
 142             self.bound_atom_with_opt_escaping(interner.tcx),
 143         );
 144
 145         let value = match predicate {
 146             ty::PredicateAtom::Trait(predicate, _) => {
 147                 chalk_ir::GoalData::DomainGoal(chalk_ir::DomainGoal::Holds(
 148                     chalk_ir::WhereClause::Implemented(predicate.trait_ref.lower_into(interner)),
 149                 ))
 150             }
 151             ty::PredicateAtom::RegionOutlives(predicate) => {
 152                 chalk_ir::GoalData::DomainGoal(chalk_ir::DomainGoal::Holds(
 153                     chalk_ir::WhereClause::LifetimeOutlives(chalk_ir::LifetimeOutlives {
 154                         a: predicate.0.lower_into(interner),
 155                         b: predicate.1.lower_into(interner),
 156                     }),
 157                 ))
 158             }
 159             ty::PredicateAtom::TypeOutlives(predicate) => {
 160                 chalk_ir::GoalData::DomainGoal(chalk_ir::DomainGoal::Holds(
 161                     chalk_ir::WhereClause::TypeOutlives(chalk_ir::TypeOutlives {
 162                         ty: predicate.0.lower_into(interner),
 163                         lifetime: predicate.1.lower_into(interner),
 164                     }),
 165                 ))
 166             }
 167             ty::PredicateAtom::Projection(predicate) => {
 168                 chalk_ir::GoalData::DomainGoal(chalk_ir::DomainGoal::Holds(
 169                     chalk_ir::WhereClause::AliasEq(predicate.lower_into(interner)),
 170                 ))
 171             }
 172             ty::PredicateAtom::WellFormed(arg) => match arg.unpack() {
 173                 GenericArgKind::Type(ty) => match ty.kind() {
 174                     // FIXME(chalk): In Chalk, a placeholder is WellFormed if it
 175                     // `FromEnv`. However, when we "lower" Params, we don't update
 176                     // the environment.
 177                     ty::Placeholder(..) => {
 178                         chalk_ir::GoalData::All(chalk_ir::Goals::empty(interner))
 179                     }
 180
 181                     _ => chalk_ir::GoalData::DomainGoal(chalk_ir::DomainGoal::WellFormed(
 182                         chalk_ir::WellFormed::Ty(ty.lower_into(interner)),
 183                     )),
 184                 },
 185                 // FIXME(chalk): handle well formed consts
 186                 GenericArgKind::Const(..) => {
 187                     chalk_ir::GoalData::All(chalk_ir::Goals::empty(interner))
 188                 }
 189                 GenericArgKind::Lifetime(lt) => bug!("unexpect well formed predicate: {:?}", lt),
 190             },
 191
 192             ty::PredicateAtom::ObjectSafe(t) => chalk_ir::GoalData::DomainGoal(
 193                 chalk_ir::DomainGoal::ObjectSafe(chalk_ir::TraitId(t)),
 194             ),
 195
 196             // FIXME(chalk): other predicates
 197             //
 198             // We can defer this, but ultimately we'll want to express
 199             // some of these in terms of chalk operations.
 200             ty::PredicateAtom::ClosureKind(..)
 201             | ty::PredicateAtom::Subtype(..)
 202             | ty::PredicateAtom::ConstEvaluatable(..)
 203             | ty::PredicateAtom::ConstEquate(..) => {
 204                 chalk_ir::GoalData::All(chalk_ir::Goals::empty(interner))
 205             }
 206             ty::PredicateAtom::TypeWellFormedFromEnv(ty) => chalk_ir::GoalData::DomainGoal(
 207                 chalk_ir::DomainGoal::FromEnv(chalk_ir::FromEnv::Ty(ty.lower_into(interner))),
 208             ),
 209         };
 210
 211         chalk_ir::GoalData::Quantified(
 212             chalk_ir::QuantifierKind::ForAll,
 213             chalk_ir::Binders::new(binders, value.intern(interner)),
 214         )
 215     }
 216 }
 217
 218 impl<'tcx> LowerInto<'tcx, chalk_ir::TraitRef<RustInterner<'tcx>>>
 219     for rustc_middle::ty::TraitRef<'tcx>
 220 {
 221     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::TraitRef<RustInterner<'tcx>> {
 222         chalk_ir::TraitRef {
 223             trait_id: chalk_ir::TraitId(self.def_id),
 224             substitution: self.substs.lower_into(interner),
 225         }
 226     }
 227 }
 228
 229 impl<'tcx> LowerInto<'tcx, chalk_ir::AliasEq<RustInterner<'tcx>>>
 230     for rustc_middle::ty::ProjectionPredicate<'tcx>
 231 {
 232     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::AliasEq<RustInterner<'tcx>> {
 233         chalk_ir::AliasEq {
 234             ty: self.ty.lower_into(interner),
 235             alias: self.projection_ty.lower_into(interner),
 236         }
 237     }
 238 }
 239
 240 impl<'tcx> LowerInto<'tcx, chalk_ir::Ty<RustInterner<'tcx>>> for Ty<'tcx> {
 241     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::Ty<RustInterner<'tcx>> {
 242         use rustc_ast as ast;
 243
 244         let int = |i| chalk_ir::TyKind::Scalar(chalk_ir::Scalar::Int(i));
 245         let uint = |i| chalk_ir::TyKind::Scalar(chalk_ir::Scalar::Uint(i));
 246         let float = |f| chalk_ir::TyKind::Scalar(chalk_ir::Scalar::Float(f));
 247
 248         match *self.kind() {
 249             ty::Bool => chalk_ir::TyKind::Scalar(chalk_ir::Scalar::Bool),
 250             ty::Char => chalk_ir::TyKind::Scalar(chalk_ir::Scalar::Char),
 251             ty::Int(ty) => match ty {
 252                 ast::IntTy::Isize => int(chalk_ir::IntTy::Isize),
 253                 ast::IntTy::I8 => int(chalk_ir::IntTy::I8),
 254                 ast::IntTy::I16 => int(chalk_ir::IntTy::I16),
 255                 ast::IntTy::I32 => int(chalk_ir::IntTy::I32),
 256                 ast::IntTy::I64 => int(chalk_ir::IntTy::I64),
 257                 ast::IntTy::I128 => int(chalk_ir::IntTy::I128),
 258             },
 259             ty::Uint(ty) => match ty {
 260                 ast::UintTy::Usize => uint(chalk_ir::UintTy::Usize),
 261                 ast::UintTy::U8 => uint(chalk_ir::UintTy::U8),
 262                 ast::UintTy::U16 => uint(chalk_ir::UintTy::U16),
 263                 ast::UintTy::U32 => uint(chalk_ir::UintTy::U32),
 264                 ast::UintTy::U64 => uint(chalk_ir::UintTy::U64),
 265                 ast::UintTy::U128 => uint(chalk_ir::UintTy::U128),
 266             },
 267             ty::Float(ty) => match ty {
 268                 ast::FloatTy::F32 => float(chalk_ir::FloatTy::F32),
 269                 ast::FloatTy::F64 => float(chalk_ir::FloatTy::F64),
 270             },
 271             ty::Adt(def, substs) => {
 272                 chalk_ir::TyKind::Adt(chalk_ir::AdtId(def), substs.lower_into(interner))
 273             }
 274             ty::Foreign(def_id) => chalk_ir::TyKind::Foreign(ForeignDefId(def_id)),
 275             ty::Str => chalk_ir::TyKind::Str,
 276             ty::Array(ty, len) => {
 277                 chalk_ir::TyKind::Array(ty.lower_into(interner), len.lower_into(interner))
 278             }
 279             ty::Slice(ty) => chalk_ir::TyKind::Slice(ty.lower_into(interner)),
 280
 281             ty::RawPtr(ptr) => {
 282                 chalk_ir::TyKind::Raw(ptr.mutbl.lower_into(interner), ptr.ty.lower_into(interner))
 283             }
 284             ty::Ref(region, ty, mutability) => chalk_ir::TyKind::Ref(
 285                 mutability.lower_into(interner),
 286                 region.lower_into(interner),
 287                 ty.lower_into(interner),
 288             ),
 289             ty::FnDef(def_id, substs) => {
 290                 chalk_ir::TyKind::FnDef(chalk_ir::FnDefId(def_id), substs.lower_into(interner))
 291             }
 292             ty::FnPtr(sig) => {
 293                 let (inputs_and_outputs, binders, _named_regions) =
 294                     collect_bound_vars(interner, interner.tcx, sig.inputs_and_output());
 295                 chalk_ir::TyKind::Function(chalk_ir::FnPointer {
 296                     num_binders: binders.len(interner),
 297                     sig: sig.lower_into(interner),
 298                     substitution: chalk_ir::Substitution::from_iter(
 299                         interner,
 300                         inputs_and_outputs.iter().map(|ty| {
 301                             chalk_ir::GenericArgData::Ty(ty.lower_into(interner)).intern(interner)
 302                         }),
 303                     ),
 304                 })
 305             }
 306             ty::Dynamic(predicates, region) => chalk_ir::TyKind::Dyn(chalk_ir::DynTy {
 307                 bounds: predicates.lower_into(interner),
 308                 lifetime: region.lower_into(interner),
 309             }),
 310             ty::Closure(def_id, substs) => {
 311                 chalk_ir::TyKind::Closure(chalk_ir::ClosureId(def_id), substs.lower_into(interner))
 312             }
 313             ty::Generator(_def_id, _substs, _) => unimplemented!(),
 314             ty::GeneratorWitness(_) => unimplemented!(),
 315             ty::Never => chalk_ir::TyKind::Never,
 316             ty::Tuple(substs) => chalk_ir::TyKind::Tuple(substs.len(), substs.lower_into(interner)),
 317             ty::Projection(proj) => chalk_ir::TyKind::Alias(proj.lower_into(interner)),
 318             ty::Opaque(def_id, substs) => {
 319                 chalk_ir::TyKind::Alias(chalk_ir::AliasTy::Opaque(chalk_ir::OpaqueTy {
 320                     opaque_ty_id: chalk_ir::OpaqueTyId(def_id),
 321                     substitution: substs.lower_into(interner),
 322                 }))
 323             }
 324             // This should have been done eagerly prior to this, and all Params
 325             // should have been substituted to placeholders
 326             ty::Param(_) => panic!("Lowering Param when not expected."),
 327             ty::Bound(db, bound) => chalk_ir::TyKind::BoundVar(chalk_ir::BoundVar::new(
 328                 chalk_ir::DebruijnIndex::new(db.as_u32()),
 329                 bound.var.index(),
 330             )),
 331             ty::Placeholder(_placeholder) => {
 332                 chalk_ir::TyKind::Placeholder(chalk_ir::PlaceholderIndex {
 333                     ui: chalk_ir::UniverseIndex { counter: _placeholder.universe.as_usize() },
 334                     idx: _placeholder.name.as_usize(),
 335                 })
 336             }
 337             ty::Infer(_infer) => unimplemented!(),
 338             ty::Error(_) => chalk_ir::TyKind::Error,
 339         }
 340         .intern(interner)
 341     }
 342 }
 343
 344 impl<'tcx> LowerInto<'tcx, Ty<'tcx>> for &chalk_ir::Ty<RustInterner<'tcx>> {
 345     fn lower_into(self, interner: &RustInterner<'tcx>) -> Ty<'tcx> {
 346         use chalk_ir::TyKind;
 347
 348         let kind = match self.kind(interner) {
 349             TyKind::Adt(struct_id, substitution) => {
 350                 ty::Adt(struct_id.0, substitution.lower_into(interner))
 351             }
 352             TyKind::Scalar(scalar) => match scalar {
 353                 chalk_ir::Scalar::Bool => ty::Bool,
 354                 chalk_ir::Scalar::Char => ty::Char,
 355                 chalk_ir::Scalar::Int(int_ty) => match int_ty {
 356                     chalk_ir::IntTy::Isize => ty::Int(ast::IntTy::Isize),
 357                     chalk_ir::IntTy::I8 => ty::Int(ast::IntTy::I8),
 358                     chalk_ir::IntTy::I16 => ty::Int(ast::IntTy::I16),
 359                     chalk_ir::IntTy::I32 => ty::Int(ast::IntTy::I32),
 360                     chalk_ir::IntTy::I64 => ty::Int(ast::IntTy::I64),
 361                     chalk_ir::IntTy::I128 => ty::Int(ast::IntTy::I128),
 362                 },
 363                 chalk_ir::Scalar::Uint(int_ty) => match int_ty {
 364                     chalk_ir::UintTy::Usize => ty::Uint(ast::UintTy::Usize),
 365                     chalk_ir::UintTy::U8 => ty::Uint(ast::UintTy::U8),
 366                     chalk_ir::UintTy::U16 => ty::Uint(ast::UintTy::U16),
 367                     chalk_ir::UintTy::U32 => ty::Uint(ast::UintTy::U32),
 368                     chalk_ir::UintTy::U64 => ty::Uint(ast::UintTy::U64),
 369                     chalk_ir::UintTy::U128 => ty::Uint(ast::UintTy::U128),
 370                 },
 371                 chalk_ir::Scalar::Float(float_ty) => match float_ty {
 372                     chalk_ir::FloatTy::F32 => ty::Float(ast::FloatTy::F32),
 373                     chalk_ir::FloatTy::F64 => ty::Float(ast::FloatTy::F64),
 374                 },
 375             },
 376             TyKind::Array(ty, c) => {
 377                 let ty = ty.lower_into(interner);
 378                 let c = c.lower_into(interner);
 379                 ty::Array(ty, interner.tcx.mk_const(c))
 380             }
 381             TyKind::FnDef(id, substitution) => ty::FnDef(id.0, substitution.lower_into(interner)),
 382             TyKind::Closure(closure, substitution) => {
 383                 ty::Closure(closure.0, substitution.lower_into(interner))
 384             }
 385             TyKind::Generator(..) => unimplemented!(),
 386             TyKind::GeneratorWitness(..) => unimplemented!(),
 387             TyKind::Never => ty::Never,
 388             TyKind::Tuple(_len, substitution) => ty::Tuple(substitution.lower_into(interner)),
 389             TyKind::Slice(ty) => ty::Slice(ty.lower_into(interner)),
 390             TyKind::Raw(mutbl, ty) => ty::RawPtr(ty::TypeAndMut {
 391                 ty: ty.lower_into(interner),
 392                 mutbl: mutbl.lower_into(interner),
 393             }),
 394             TyKind::Ref(mutbl, lifetime, ty) => ty::Ref(
 395                 lifetime.lower_into(interner),
 396                 ty.lower_into(interner),
 397                 mutbl.lower_into(interner),
 398             ),
 399             TyKind::Str => ty::Str,
 400             TyKind::OpaqueType(opaque_ty, substitution) => {
 401                 ty::Opaque(opaque_ty.0, substitution.lower_into(interner))
 402             }
 403             TyKind::AssociatedType(assoc_ty, substitution) => ty::Projection(ty::ProjectionTy {
 404                 substs: substitution.lower_into(interner),
 405                 item_def_id: assoc_ty.0,
 406             }),
 407             TyKind::Foreign(def_id) => ty::Foreign(def_id.0),
 408             TyKind::Error => return interner.tcx.ty_error(),
 409             TyKind::Placeholder(placeholder) => ty::Placeholder(ty::Placeholder {
 410                 universe: ty::UniverseIndex::from_usize(placeholder.ui.counter),
 411                 name: ty::BoundVar::from_usize(placeholder.idx),
 412             }),
 413             TyKind::Alias(alias_ty) => match alias_ty {
 414                 chalk_ir::AliasTy::Projection(projection) => ty::Projection(ty::ProjectionTy {
 415                     item_def_id: projection.associated_ty_id.0,
 416                     substs: projection.substitution.lower_into(interner),
 417                 }),
 418                 chalk_ir::AliasTy::Opaque(opaque) => {
 419                     ty::Opaque(opaque.opaque_ty_id.0, opaque.substitution.lower_into(interner))
 420                 }
 421             },
 422             TyKind::Function(_quantified_ty) => unimplemented!(),
 423             TyKind::BoundVar(_bound) => ty::Bound(
 424                 ty::DebruijnIndex::from_usize(_bound.debruijn.depth() as usize),
 425                 ty::BoundTy {
 426                     var: ty::BoundVar::from_usize(_bound.index),
 427                     kind: ty::BoundTyKind::Anon,
 428                 },
 429             ),
 430             TyKind::InferenceVar(_, _) => unimplemented!(),
 431             TyKind::Dyn(_) => unimplemented!(),
 432         };
 433         interner.tcx.mk_ty(kind)
 434     }
 435 }
 436
 437 impl<'tcx> LowerInto<'tcx, chalk_ir::Lifetime<RustInterner<'tcx>>> for Region<'tcx> {
 438     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::Lifetime<RustInterner<'tcx>> {
 439         use rustc_middle::ty::RegionKind::*;
 440
 441         match self {
 442             ReEarlyBound(_) => {
 443                 panic!("Should have already been substituted.");
 444             }
 445             ReLateBound(db, br) => match br.kind {
 446                 ty::BoundRegionKind::BrAnon(var) => {
 447                     chalk_ir::LifetimeData::BoundVar(chalk_ir::BoundVar::new(
 448                         chalk_ir::DebruijnIndex::new(db.as_u32()),
 449                         var as usize,
 450                     ))
 451                     .intern(interner)
 452                 }
 453                 ty::BoundRegionKind::BrNamed(_def_id, _name) => unimplemented!(),
 454                 ty::BrEnv => unimplemented!(),
 455             },
 456             ReFree(_) => unimplemented!(),
 457             ReStatic => chalk_ir::LifetimeData::Static.intern(interner),
 458             ReVar(_) => unimplemented!(),
 459             RePlaceholder(placeholder_region) => {
 460                 chalk_ir::LifetimeData::Placeholder(chalk_ir::PlaceholderIndex {
 461                     ui: chalk_ir::UniverseIndex { counter: placeholder_region.universe.index() },
 462                     idx: 0,
 463                 })
 464                 .intern(interner)
 465             }
 466             ReEmpty(_) => unimplemented!(),
 467             // FIXME(chalk): need to handle ReErased
 468             ReErased => unimplemented!(),
 469         }
 470     }
 471 }
 472
 473 impl<'tcx> LowerInto<'tcx, Region<'tcx>> for &chalk_ir::Lifetime<RustInterner<'tcx>> {
 474     fn lower_into(self, interner: &RustInterner<'tcx>) -> Region<'tcx> {
 475         let kind = match self.data(interner) {
 476             chalk_ir::LifetimeData::BoundVar(var) => ty::RegionKind::ReLateBound(
 477                 ty::DebruijnIndex::from_u32(var.debruijn.depth()),
 478                 ty::BoundRegion { kind: ty::BrAnon(var.index as u32) },
 479             ),
 480             chalk_ir::LifetimeData::InferenceVar(_var) => unimplemented!(),
 481             chalk_ir::LifetimeData::Placeholder(p) => {
 482                 ty::RegionKind::RePlaceholder(ty::Placeholder {
 483                     universe: ty::UniverseIndex::from_usize(p.ui.counter),
 484                     name: ty::BoundRegionKind::BrAnon(p.idx as u32),
 485                 })
 486             }
 487             chalk_ir::LifetimeData::Static => ty::RegionKind::ReStatic,
 488             chalk_ir::LifetimeData::Phantom(_, _) => unimplemented!(),
 489         };
 490         interner.tcx.mk_region(kind)
 491     }
 492 }
 493
 494 impl<'tcx> LowerInto<'tcx, chalk_ir::Const<RustInterner<'tcx>>> for ty::Const<'tcx> {
 495     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::Const<RustInterner<'tcx>> {
 496         let ty = self.ty.lower_into(interner);
 497         let value = match self.val {
 498             ty::ConstKind::Value(val) => {
 499                 chalk_ir::ConstValue::Concrete(chalk_ir::ConcreteConst { interned: val })
 500             }
 501             ty::ConstKind::Bound(db, bound) => chalk_ir::ConstValue::BoundVar(
 502                 chalk_ir::BoundVar::new(chalk_ir::DebruijnIndex::new(db.as_u32()), bound.index()),
 503             ),
 504             _ => unimplemented!("Const not implemented. {:?}", self),
 505         };
 506         chalk_ir::ConstData { ty, value }.intern(interner)
 507     }
 508 }
 509
 510 impl<'tcx> LowerInto<'tcx, ty::Const<'tcx>> for &chalk_ir::Const<RustInterner<'tcx>> {
 511     fn lower_into(self, interner: &RustInterner<'tcx>) -> ty::Const<'tcx> {
 512         let data = self.data(interner);
 513         let ty = data.ty.lower_into(interner);
 514         let val = match data.value {
 515             chalk_ir::ConstValue::BoundVar(var) => ty::ConstKind::Bound(
 516                 ty::DebruijnIndex::from_u32(var.debruijn.depth()),
 517                 ty::BoundVar::from_u32(var.index as u32),
 518             ),
 519             chalk_ir::ConstValue::InferenceVar(_var) => unimplemented!(),
 520             chalk_ir::ConstValue::Placeholder(_p) => unimplemented!(),
 521             chalk_ir::ConstValue::Concrete(c) => ty::ConstKind::Value(c.interned),
 522         };
 523         ty::Const { ty, val }
 524     }
 525 }
 526
 527 impl<'tcx> LowerInto<'tcx, chalk_ir::GenericArg<RustInterner<'tcx>>> for GenericArg<'tcx> {
 528     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::GenericArg<RustInterner<'tcx>> {
 529         match self.unpack() {
 530             ty::subst::GenericArgKind::Type(ty) => {
 531                 chalk_ir::GenericArgData::Ty(ty.lower_into(interner))
 532             }
 533             ty::subst::GenericArgKind::Lifetime(lifetime) => {
 534                 chalk_ir::GenericArgData::Lifetime(lifetime.lower_into(interner))
 535             }
 536             ty::subst::GenericArgKind::Const(c) => {
 537                 chalk_ir::GenericArgData::Const(c.lower_into(interner))
 538             }
 539         }
 540         .intern(interner)
 541     }
 542 }
 543
 544 impl<'tcx> LowerInto<'tcx, ty::subst::GenericArg<'tcx>>
 545     for &chalk_ir::GenericArg<RustInterner<'tcx>>
 546 {
 547     fn lower_into(self, interner: &RustInterner<'tcx>) -> ty::subst::GenericArg<'tcx> {
 548         match self.data(interner) {
 549             chalk_ir::GenericArgData::Ty(ty) => {
 550                 let t: Ty<'tcx> = ty.lower_into(interner);
 551                 t.into()
 552             }
 553             chalk_ir::GenericArgData::Lifetime(lifetime) => {
 554                 let r: Region<'tcx> = lifetime.lower_into(interner);
 555                 r.into()
 556             }
 557             chalk_ir::GenericArgData::Const(c) => {
 558                 let c: ty::Const<'tcx> = c.lower_into(interner);
 559                 interner.tcx.mk_const(c).into()
 560             }
 561         }
 562     }
 563 }
 564
 565 // We lower into an Option here since there are some predicates which Chalk
 566 // doesn't have a representation for yet (as a `WhereClause`), but are so common
 567 // that we just are accepting the unsoundness for now. The `Option` will
 568 // eventually be removed.
 569 impl<'tcx> LowerInto<'tcx, Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>>>
 570     for ty::Predicate<'tcx>
 571 {
 572     fn lower_into(
 573         self,
 574         interner: &RustInterner<'tcx>,
 575     ) -> Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>> {
 576         let (predicate, binders, _named_regions) = collect_bound_vars(
 577             interner,
 578             interner.tcx,
 579             self.bound_atom_with_opt_escaping(interner.tcx),
 580         );
 581         let value = match predicate {
 582             ty::PredicateAtom::Trait(predicate, _) => {
 583                 Some(chalk_ir::WhereClause::Implemented(predicate.trait_ref.lower_into(interner)))
 584             }
 585             ty::PredicateAtom::RegionOutlives(predicate) => {
 586                 Some(chalk_ir::WhereClause::LifetimeOutlives(chalk_ir::LifetimeOutlives {
 587                     a: predicate.0.lower_into(interner),
 588                     b: predicate.1.lower_into(interner),
 589                 }))
 590             }
 591             ty::PredicateAtom::TypeOutlives(predicate) => {
 592                 Some(chalk_ir::WhereClause::TypeOutlives(chalk_ir::TypeOutlives {
 593                     ty: predicate.0.lower_into(interner),
 594                     lifetime: predicate.1.lower_into(interner),
 595                 }))
 596             }
 597             ty::PredicateAtom::Projection(predicate) => {
 598                 Some(chalk_ir::WhereClause::AliasEq(predicate.lower_into(interner)))
 599             }
 600             ty::PredicateAtom::WellFormed(_ty) => None,
 601
 602             ty::PredicateAtom::ObjectSafe(..)
 603             | ty::PredicateAtom::ClosureKind(..)
 604             | ty::PredicateAtom::Subtype(..)
 605             | ty::PredicateAtom::ConstEvaluatable(..)
 606             | ty::PredicateAtom::ConstEquate(..)
 607             | ty::PredicateAtom::TypeWellFormedFromEnv(..) => {
 608                 bug!("unexpected predicate {}", &self)
 609             }
 610         };
 611         value.map(|value| chalk_ir::Binders::new(binders, value))
 612     }
 613 }
 614
 615 impl<'tcx> LowerInto<'tcx, chalk_ir::Binders<chalk_ir::QuantifiedWhereClauses<RustInterner<'tcx>>>>
 616     for &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>
 617 {
 618     fn lower_into(
 619         self,
 620         interner: &RustInterner<'tcx>,
 621     ) -> chalk_ir::Binders<chalk_ir::QuantifiedWhereClauses<RustInterner<'tcx>>> {
 622         // `Self` has one binder:
 623         // Binder<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>>
 624         // The return type has two:
 625         // Binders<&[Binders<WhereClause<I>>]>
 626         // This means that any variables that are escaping `self` need to be
 627         // shifted in by one so that they are still escaping.
 628         let predicates = ty::fold::shift_vars(interner.tcx, self, 1);
 629
 630         let self_ty = interner.tcx.mk_ty(ty::Bound(
 631             // This is going to be wrapped in a binder
 632             ty::DebruijnIndex::from_usize(1),
 633             ty::BoundTy { var: ty::BoundVar::from_usize(0), kind: ty::BoundTyKind::Anon },
 634         ));
 635         let where_clauses = predicates.into_iter().map(|predicate| {
 636             let (predicate, binders, _named_regions) =
 637                 collect_bound_vars(interner, interner.tcx, predicate);
 638             match predicate {
 639                 ty::ExistentialPredicate::Trait(ty::ExistentialTraitRef { def_id, substs }) => {
 640                     chalk_ir::Binders::new(
 641                         binders.clone(),
 642                         chalk_ir::WhereClause::Implemented(chalk_ir::TraitRef {
 643                             trait_id: chalk_ir::TraitId(def_id),
 644                             substitution: interner
 645                                 .tcx
 646                                 .mk_substs_trait(self_ty, substs)
 647                                 .lower_into(interner),
 648                         }),
 649                     )
 650                 }
 651                 ty::ExistentialPredicate::Projection(predicate) => chalk_ir::Binders::new(
 652                     binders.clone(),
 653                     chalk_ir::WhereClause::AliasEq(chalk_ir::AliasEq {
 654                         alias: chalk_ir::AliasTy::Projection(chalk_ir::ProjectionTy {
 655                             associated_ty_id: chalk_ir::AssocTypeId(predicate.item_def_id),
 656                             substitution: interner
 657                                 .tcx
 658                                 .mk_substs_trait(self_ty, predicate.substs)
 659                                 .lower_into(interner),
 660                         }),
 661                         ty: predicate.ty.lower_into(interner),
 662                     }),
 663                 ),
 664                 ty::ExistentialPredicate::AutoTrait(def_id) => chalk_ir::Binders::new(
 665                     binders.clone(),
 666                     chalk_ir::WhereClause::Implemented(chalk_ir::TraitRef {
 667                         trait_id: chalk_ir::TraitId(def_id),
 668                         substitution: interner
 669                             .tcx
 670                             .mk_substs_trait(self_ty, &[])
 671                             .lower_into(interner),
 672                     }),
 673                 ),
 674             }
 675         });
 676
 677         // Binder for the bound variable representing the concrete underlying type.
 678         let existential_binder = chalk_ir::VariableKinds::from1(
 679             interner,
 680             chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General),
 681         );
 682         let value = chalk_ir::QuantifiedWhereClauses::from_iter(interner, where_clauses);
 683         chalk_ir::Binders::new(existential_binder, value)
 684     }
 685 }
 686
 687 impl<'tcx> LowerInto<'tcx, chalk_ir::FnSig<RustInterner<'tcx>>> for ty::Binder<ty::FnSig<'tcx>> {
 688     fn lower_into(self, _interner: &RustInterner<'_>) -> FnSig<RustInterner<'tcx>> {
 689         chalk_ir::FnSig {
 690             abi: self.abi(),
 691             safety: match self.unsafety() {
 692                 Unsafety::Normal => chalk_ir::Safety::Safe,
 693                 Unsafety::Unsafe => chalk_ir::Safety::Unsafe,
 694             },
 695             variadic: self.c_variadic(),
 696         }
 697     }
 698 }
 699
 700 // We lower into an Option here since there are some predicates which Chalk
 701 // doesn't have a representation for yet (as an `InlineBound`). The `Option` will
 702 // eventually be removed.
 703 impl<'tcx> LowerInto<'tcx, Option<chalk_solve::rust_ir::QuantifiedInlineBound<RustInterner<'tcx>>>>
 704     for ty::Predicate<'tcx>
 705 {
 706     fn lower_into(
 707         self,
 708         interner: &RustInterner<'tcx>,
 709     ) -> Option<chalk_solve::rust_ir::QuantifiedInlineBound<RustInterner<'tcx>>> {
 710         let (predicate, binders, _named_regions) = collect_bound_vars(
 711             interner,
 712             interner.tcx,
 713             self.bound_atom_with_opt_escaping(interner.tcx),
 714         );
 715         match predicate {
 716             ty::PredicateAtom::Trait(predicate, _) => Some(chalk_ir::Binders::new(
 717                 binders,
 718                 chalk_solve::rust_ir::InlineBound::TraitBound(
 719                     predicate.trait_ref.lower_into(interner),
 720                 ),
 721             )),
 722             ty::PredicateAtom::Projection(predicate) => Some(chalk_ir::Binders::new(
 723                 binders,
 724                 chalk_solve::rust_ir::InlineBound::AliasEqBound(predicate.lower_into(interner)),
 725             )),
 726             ty::PredicateAtom::TypeOutlives(_predicate) => None,
 727             ty::PredicateAtom::WellFormed(_ty) => None,
 728
 729             ty::PredicateAtom::RegionOutlives(..)
 730             | ty::PredicateAtom::ObjectSafe(..)
 731             | ty::PredicateAtom::ClosureKind(..)
 732             | ty::PredicateAtom::Subtype(..)
 733             | ty::PredicateAtom::ConstEvaluatable(..)
 734             | ty::PredicateAtom::ConstEquate(..)
 735             | ty::PredicateAtom::TypeWellFormedFromEnv(..) => {
 736                 bug!("unexpected predicate {}", &self)
 737             }
 738         }
 739     }
 740 }
 741
 742 impl<'tcx> LowerInto<'tcx, chalk_solve::rust_ir::TraitBound<RustInterner<'tcx>>>
 743     for ty::TraitRef<'tcx>
 744 {
 745     fn lower_into(
 746         self,
 747         interner: &RustInterner<'tcx>,
 748     ) -> chalk_solve::rust_ir::TraitBound<RustInterner<'tcx>> {
 749         chalk_solve::rust_ir::TraitBound {
 750             trait_id: chalk_ir::TraitId(self.def_id),
 751             args_no_self: self.substs[1..].iter().map(|arg| arg.lower_into(interner)).collect(),
 752         }
 753     }
 754 }
 755
 756 impl<'tcx> LowerInto<'tcx, chalk_ir::Mutability> for ast::Mutability {
 757     fn lower_into(self, _interner: &RustInterner<'tcx>) -> chalk_ir::Mutability {
 758         match self {
 759             rustc_ast::Mutability::Mut => chalk_ir::Mutability::Mut,
 760             rustc_ast::Mutability::Not => chalk_ir::Mutability::Not,
 761         }
 762     }
 763 }
 764
 765 impl<'tcx> LowerInto<'tcx, ast::Mutability> for chalk_ir::Mutability {
 766     fn lower_into(self, _interner: &RustInterner<'tcx>) -> ast::Mutability {
 767         match self {
 768             chalk_ir::Mutability::Mut => ast::Mutability::Mut,
 769             chalk_ir::Mutability::Not => ast::Mutability::Not,
 770         }
 771     }
 772 }
 773
 774 impl<'tcx> LowerInto<'tcx, chalk_solve::rust_ir::Polarity> for ty::ImplPolarity {
 775     fn lower_into(self, _interner: &RustInterner<'tcx>) -> chalk_solve::rust_ir::Polarity {
 776         match self {
 777             ty::ImplPolarity::Positive => chalk_solve::rust_ir::Polarity::Positive,
 778             ty::ImplPolarity::Negative => chalk_solve::rust_ir::Polarity::Negative,
 779             // FIXME(chalk) reservation impls
 780             ty::ImplPolarity::Reservation => chalk_solve::rust_ir::Polarity::Negative,
 781         }
 782     }
 783 }
 784
 785 impl<'tcx> LowerInto<'tcx, chalk_solve::rust_ir::AliasEqBound<RustInterner<'tcx>>>
 786     for ty::ProjectionPredicate<'tcx>
 787 {
 788     fn lower_into(
 789         self,
 790         interner: &RustInterner<'tcx>,
 791     ) -> chalk_solve::rust_ir::AliasEqBound<RustInterner<'tcx>> {
 792         let trait_ref = self.projection_ty.trait_ref(interner.tcx);
 793         chalk_solve::rust_ir::AliasEqBound {
 794             trait_bound: trait_ref.lower_into(interner),
 795             associated_ty_id: chalk_ir::AssocTypeId(self.projection_ty.item_def_id),
 796             parameters: self.projection_ty.substs[trait_ref.substs.len()..]
 797                 .iter()
 798                 .map(|arg| arg.lower_into(interner))
 799                 .collect(),
 800             value: self.ty.lower_into(interner),
 801         }
 802     }
 803 }
 804
 805 /// To collect bound vars, we have to do two passes. In the first pass, we
 806 /// collect all `BoundRegionKind`s and `ty::Bound`s. In the second pass, we then
 807 /// replace `BrNamed` into `BrAnon`. The two separate passes are important,
 808 /// since we can only replace `BrNamed` with `BrAnon`s with indices *after* all
 809 /// "real" `BrAnon`s.
 810 ///
 811 /// It's important to note that because of prior substitution, we may have
 812 /// late-bound regions, even outside of fn contexts, since this is the best way
 813 /// to prep types for chalk lowering.
 814 crate fn collect_bound_vars<'tcx, T: TypeFoldable<'tcx>>(
 815     interner: &RustInterner<'tcx>,
 816     tcx: TyCtxt<'tcx>,
 817     ty: Binder<T>,
 818 ) -> (T, chalk_ir::VariableKinds<RustInterner<'tcx>>, BTreeMap<DefId, u32>) {
 819     let mut bound_vars_collector = BoundVarsCollector::new();
 820     ty.as_ref().skip_binder().visit_with(&mut bound_vars_collector);
 821     let mut parameters = bound_vars_collector.parameters;
 822     let named_parameters: BTreeMap<DefId, u32> = bound_vars_collector
 823         .named_parameters
 824         .into_iter()
 825         .enumerate()
 826         .map(|(i, def_id)| (def_id, (i + parameters.len()) as u32))
 827         .collect();
 828
 829     let mut bound_var_substitutor = NamedBoundVarSubstitutor::new(tcx, &named_parameters);
 830     let new_ty = ty.skip_binder().fold_with(&mut bound_var_substitutor);
 831
 832     for var in named_parameters.values() {
 833         parameters.insert(*var, chalk_ir::VariableKind::Lifetime);
 834     }
 835
 836     (0..parameters.len()).for_each(|i| {
 837         parameters
 838             .get(&(i as u32))
 839             .or_else(|| bug!("Skipped bound var index: parameters={:?}", parameters));
 840     });
 841
 842     let binders =
 843         chalk_ir::VariableKinds::from_iter(interner, parameters.into_iter().map(|(_, v)| v));
 844
 845     (new_ty, binders, named_parameters)
 846 }
 847
 848 crate struct BoundVarsCollector<'tcx> {
 849     binder_index: ty::DebruijnIndex,
 850     crate parameters: BTreeMap<u32, chalk_ir::VariableKind<RustInterner<'tcx>>>,
 851     crate named_parameters: Vec<DefId>,
 852 }
 853
 854 impl<'tcx> BoundVarsCollector<'tcx> {
 855     crate fn new() -> Self {
 856         BoundVarsCollector {
 857             binder_index: ty::INNERMOST,
 858             parameters: BTreeMap::new(),
 859             named_parameters: vec![],
 860         }
 861     }
 862 }
 863
 864 impl<'tcx> TypeVisitor<'tcx> for BoundVarsCollector<'tcx> {
 865     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> ControlFlow<Self::BreakTy> {
 866         self.binder_index.shift_in(1);
 867         let result = t.super_visit_with(self);
 868         self.binder_index.shift_out(1);
 869         result
 870     }
 871
 872     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 873         match *t.kind() {
 874             ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => {
 875                 match self.parameters.entry(bound_ty.var.as_u32()) {
 876                     Entry::Vacant(entry) => {
 877                         entry.insert(chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General));
 878                     }
 879                     Entry::Occupied(entry) => match entry.get() {
 880                         chalk_ir::VariableKind::Ty(_) => {}
 881                         _ => panic!(),
 882                     },
 883                 }
 884             }
 885
 886             _ => (),
 887         };
 888
 889         t.super_visit_with(self)
 890     }
 891
 892     fn visit_region(&mut self, r: Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 893         match r {
 894             ty::ReLateBound(index, br) if *index == self.binder_index => match br.kind {
 895                 ty::BoundRegionKind::BrNamed(def_id, _name) => {
 896                     if self.named_parameters.iter().find(|d| **d == def_id).is_none() {
 897                         self.named_parameters.push(def_id);
 898                     }
 899                 }
 900
 901                 ty::BoundRegionKind::BrAnon(var) => match self.parameters.entry(var) {
 902                     Entry::Vacant(entry) => {
 903                         entry.insert(chalk_ir::VariableKind::Lifetime);
 904                     }
 905                     Entry::Occupied(entry) => match entry.get() {
 906                         chalk_ir::VariableKind::Lifetime => {}
 907                         _ => panic!(),
 908                     },
 909                 },
 910
 911                 ty::BrEnv => unimplemented!(),
 912             },
 913
 914             ty::ReEarlyBound(_re) => {
 915                 // FIXME(chalk): jackh726 - I think we should always have already
 916                 // substituted away `ReEarlyBound`s for `ReLateBound`s, but need to confirm.
 917                 unimplemented!();
 918             }
 919
 920             _ => (),
 921         };
 922
 923         r.super_visit_with(self)
 924     }
 925 }
 926
 927 /// This is used to replace `BoundRegionKind::BrNamed` with `BoundRegionKind::BrAnon`.
 928 /// Note: we assume that we will always have room for more bound vars. (i.e. we
 929 /// won't ever hit the `u32` limit in `BrAnon`s).
 930 struct NamedBoundVarSubstitutor<'a, 'tcx> {
 931     tcx: TyCtxt<'tcx>,
 932     binder_index: ty::DebruijnIndex,
 933     named_parameters: &'a BTreeMap<DefId, u32>,
 934 }
 935
 936 impl<'a, 'tcx> NamedBoundVarSubstitutor<'a, 'tcx> {
 937     fn new(tcx: TyCtxt<'tcx>, named_parameters: &'a BTreeMap<DefId, u32>) -> Self {
 938         NamedBoundVarSubstitutor { tcx, binder_index: ty::INNERMOST, named_parameters }
 939     }
 940 }
 941
 942 impl<'a, 'tcx> TypeFolder<'tcx> for NamedBoundVarSubstitutor<'a, 'tcx> {
 943     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 944         self.tcx
 945     }
 946
 947     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: Binder<T>) -> Binder<T> {
 948         self.binder_index.shift_in(1);
 949         let result = t.super_fold_with(self);
 950         self.binder_index.shift_out(1);
 951         result
 952     }
 953
 954     fn fold_region(&mut self, r: Region<'tcx>) -> Region<'tcx> {
 955         match r {
 956             ty::ReLateBound(index, br) if *index == self.binder_index => match br.kind {
 957                 ty::BrNamed(def_id, _name) => match self.named_parameters.get(&def_id) {
 958                     Some(idx) => {
 959                         let new_br = ty::BoundRegion { kind: ty::BrAnon(*idx) };
 960                         return self.tcx.mk_region(RegionKind::ReLateBound(*index, new_br));
 961                     }
 962                     None => panic!("Missing `BrNamed`."),
 963                 },
 964                 ty::BrEnv => unimplemented!(),
 965                 ty::BrAnon(_) => {}
 966             },
 967             _ => (),
 968         };
 969
 970         r.super_fold_with(self)
 971     }
 972 }
 973
 974 /// Used to substitute `Param`s with placeholders. We do this since Chalk
 975 /// have a notion of `Param`s.
 976 crate struct ParamsSubstitutor<'tcx> {
 977     tcx: TyCtxt<'tcx>,
 978     binder_index: ty::DebruijnIndex,
 979     list: Vec<rustc_middle::ty::ParamTy>,
 980     next_ty_placeholder: usize,
 981     crate params: rustc_data_structures::fx::FxHashMap<usize, rustc_middle::ty::ParamTy>,
 982     crate named_regions: BTreeMap<DefId, u32>,
 983 }
 984
 985 impl<'tcx> ParamsSubstitutor<'tcx> {
 986     crate fn new(tcx: TyCtxt<'tcx>, next_ty_placeholder: usize) -> Self {
 987         ParamsSubstitutor {
 988             tcx,
 989             binder_index: ty::INNERMOST,
 990             list: vec![],
 991             next_ty_placeholder,
 992             params: rustc_data_structures::fx::FxHashMap::default(),
 993             named_regions: BTreeMap::default(),
 994         }
 995     }
 996 }
 997
 998 impl<'tcx> TypeFolder<'tcx> for ParamsSubstitutor<'tcx> {
 999     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
1000         self.tcx
1001     }
1002
1003     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: Binder<T>) -> Binder<T> {
1004         self.binder_index.shift_in(1);
1005         let result = t.super_fold_with(self);
1006         self.binder_index.shift_out(1);
1007         result
1008     }
1009
1010     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
1011         match *t.kind() {
1012             // FIXME(chalk): currently we convert params to placeholders starting at
1013             // index `0`. To support placeholders, we'll actually need to do a
1014             // first pass to collect placeholders. Then we can insert params after.
1015             ty::Placeholder(_) => unimplemented!(),
1016             ty::Param(param) => match self.list.iter().position(|r| r == &param) {
1017                 Some(idx) => self.tcx.mk_ty(ty::Placeholder(ty::PlaceholderType {
1018                     universe: ty::UniverseIndex::from_usize(0),
1019                     name: ty::BoundVar::from_usize(idx),
1020                 })),
1021                 None => {
1022                     self.list.push(param);
1023                     let idx = self.list.len() - 1 + self.next_ty_placeholder;
1024                     self.params.insert(idx, param);
1025                     self.tcx.mk_ty(ty::Placeholder(ty::PlaceholderType {
1026                         universe: ty::UniverseIndex::from_usize(0),
1027                         name: ty::BoundVar::from_usize(idx),
1028                     }))
1029                 }
1030             },
1031
1032             _ => t.super_fold_with(self),
1033         }
1034     }
1035
1036     fn fold_region(&mut self, r: Region<'tcx>) -> Region<'tcx> {
1037         match r {
1038             // FIXME(chalk) - jackh726 - this currently isn't hit in any tests.
1039             // This covers any region variables in a goal, right?
1040             ty::ReEarlyBound(_re) => match self.named_regions.get(&_re.def_id) {
1041                 Some(idx) => {
1042                     let br = ty::BoundRegion { kind: ty::BrAnon(*idx) };
1043                     self.tcx.mk_region(RegionKind::ReLateBound(self.binder_index, br))
1044                 }
1045                 None => {
1046                     let idx = self.named_regions.len() as u32;
1047                     let br = ty::BoundRegion { kind: ty::BrAnon(idx) };
1048                     self.named_regions.insert(_re.def_id, idx);
1049                     self.tcx.mk_region(RegionKind::ReLateBound(self.binder_index, br))
1050                 }
1051             },
1052
1053             _ => r.super_fold_with(self),
1054         }
1055     }
1056 }
1057
1058 /// Used to collect `Placeholder`s.
1059 crate struct PlaceholdersCollector {
1060     universe_index: ty::UniverseIndex,
1061     crate next_ty_placeholder: usize,
1062     crate next_anon_region_placeholder: u32,
1063 }
1064
1065 impl PlaceholdersCollector {
1066     crate fn new() -> Self {
1067         PlaceholdersCollector {
1068             universe_index: ty::UniverseIndex::ROOT,
1069             next_ty_placeholder: 0,
1070             next_anon_region_placeholder: 0,
1071         }
1072     }
1073 }
1074
1075 impl<'tcx> TypeVisitor<'tcx> for PlaceholdersCollector {
1076     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
1077         match t.kind() {
1078             ty::Placeholder(p) if p.universe == self.universe_index => {
1079                 self.next_ty_placeholder = self.next_ty_placeholder.max(p.name.as_usize() + 1);
1080             }
1081
1082             _ => (),
1083         };
1084
1085         t.super_visit_with(self)
1086     }
1087
1088     fn visit_region(&mut self, r: Region<'tcx>) -> ControlFlow<Self::BreakTy> {
1089         match r {
1090             ty::RePlaceholder(p) if p.universe == self.universe_index => {
1091                 if let ty::BoundRegionKind::BrAnon(anon) = p.name {
1092                     self.next_anon_region_placeholder = self.next_anon_region_placeholder.max(anon);
1093                 }
1094             }
1095
1096             _ => (),
1097         };
1098
1099         r.super_visit_with(self)
1100     }
1101 }
1102
1103 /// Used to substitute specific `Regions`s with placeholders.
1104 crate struct RegionsSubstitutor<'tcx> {
1105     tcx: TyCtxt<'tcx>,
1106     reempty_placeholder: ty::Region<'tcx>,
1107 }
1108
1109 impl<'tcx> RegionsSubstitutor<'tcx> {
1110     crate fn new(tcx: TyCtxt<'tcx>, reempty_placeholder: ty::Region<'tcx>) -> Self {
1111         RegionsSubstitutor { tcx, reempty_placeholder }
1112     }
1113 }
1114
1115 impl<'tcx> TypeFolder<'tcx> for RegionsSubstitutor<'tcx> {
1116     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
1117         self.tcx
1118     }
1119
1120     fn fold_region(&mut self, r: Region<'tcx>) -> Region<'tcx> {
1121         match r {
1122             ty::ReEmpty(ui) => {
1123                 assert_eq!(ui.as_usize(), 0);
1124                 self.reempty_placeholder
1125             }
1126
1127             _ => r.super_fold_with(self),
1128         }
1129     }
1130 }