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