src/librustc_traits/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_middle::traits::{
  35     ChalkEnvironmentAndGoal, ChalkEnvironmentClause, ChalkRustDefId as RustDefId,
  36     ChalkRustInterner as RustInterner,
  37 };
  38 use rustc_middle::ty::fold::TypeFolder;
  39 use rustc_middle::ty::subst::{GenericArg, SubstsRef};
  40 use rustc_middle::ty::{
  41     self, Binder, BoundRegion, Region, RegionKind, Ty, TyCtxt, TyKind, TypeFoldable, TypeVisitor,
  42 };
  43 use rustc_span::def_id::DefId;
  44
  45 use std::collections::btree_map::{BTreeMap, Entry};
  46
  47 /// Essentially an `Into` with a `&RustInterner` parameter
  48 crate trait LowerInto<'tcx, T> {
  49     /// Lower a rustc construct (e.g., `ty::TraitPredicate`) to a chalk type, consuming `self`.
  50     fn lower_into(self, interner: &RustInterner<'tcx>) -> T;
  51 }
  52
  53 impl<'tcx> LowerInto<'tcx, chalk_ir::Substitution<RustInterner<'tcx>>> for SubstsRef<'tcx> {
  54     fn lower_into(
  55         self,
  56         interner: &RustInterner<'tcx>,
  57     ) -> chalk_ir::Substitution<RustInterner<'tcx>> {
  58         chalk_ir::Substitution::from(interner, self.iter().map(|s| s.lower_into(interner)))
  59     }
  60 }
  61
  62 impl<'tcx> LowerInto<'tcx, chalk_ir::AliasTy<RustInterner<'tcx>>> for ty::ProjectionTy<'tcx> {
  63     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::AliasTy<RustInterner<'tcx>> {
  64         chalk_ir::AliasTy::Projection(chalk_ir::ProjectionTy {
  65             associated_ty_id: chalk_ir::AssocTypeId(RustDefId::AssocTy(self.item_def_id)),
  66             substitution: self.substs.lower_into(interner),
  67         })
  68     }
  69 }
  70
  71 impl<'tcx> LowerInto<'tcx, chalk_ir::InEnvironment<chalk_ir::Goal<RustInterner<'tcx>>>>
  72     for ChalkEnvironmentAndGoal<'tcx>
  73 {
  74     fn lower_into(
  75         self,
  76         interner: &RustInterner<'tcx>,
  77     ) -> chalk_ir::InEnvironment<chalk_ir::Goal<RustInterner<'tcx>>> {
  78         let clauses = self.environment.into_iter().filter_map(|clause| match clause {
  79             ChalkEnvironmentClause::Predicate(predicate) => {
  80                 match &predicate.kind() {
  81                     ty::PredicateKind::Trait(predicate, _) => {
  82                         let (predicate, binders, _named_regions) =
  83                             collect_bound_vars(interner, interner.tcx, predicate);
  84
  85                         Some(
  86                             chalk_ir::ProgramClauseData::ForAll(chalk_ir::Binders::new(
  87                                 binders,
  88                                 chalk_ir::ProgramClauseImplication {
  89                                     consequence: chalk_ir::DomainGoal::FromEnv(
  90                                         chalk_ir::FromEnv::Trait(
  91                                             predicate.trait_ref.lower_into(interner),
  92                                         ),
  93                                     ),
  94                                     conditions: chalk_ir::Goals::new(interner),
  95                                     priority: chalk_ir::ClausePriority::High,
  96                                 },
  97                             ))
  98                             .intern(interner),
  99                         )
 100                     }
 101                     // FIXME(chalk): need to add RegionOutlives/TypeOutlives
 102                     ty::PredicateKind::RegionOutlives(_) => None,
 103                     ty::PredicateKind::TypeOutlives(_) => None,
 104                     ty::PredicateKind::Projection(predicate) => {
 105                         let (predicate, binders, _named_regions) =
 106                             collect_bound_vars(interner, interner.tcx, predicate);
 107
 108                         Some(
 109                             chalk_ir::ProgramClauseData::ForAll(chalk_ir::Binders::new(
 110                                 binders,
 111                                 chalk_ir::ProgramClauseImplication {
 112                                     consequence: chalk_ir::DomainGoal::Holds(
 113                                         chalk_ir::WhereClause::AliasEq(
 114                                             predicate.lower_into(interner),
 115                                         ),
 116                                     ),
 117                                     conditions: chalk_ir::Goals::new(interner),
 118                                     priority: chalk_ir::ClausePriority::High,
 119                                 },
 120                             ))
 121                             .intern(interner),
 122                         )
 123                     }
 124                     ty::PredicateKind::WellFormed(..)
 125                     | ty::PredicateKind::ObjectSafe(..)
 126                     | ty::PredicateKind::ClosureKind(..)
 127                     | ty::PredicateKind::Subtype(..)
 128                     | ty::PredicateKind::ConstEvaluatable(..)
 129                     | ty::PredicateKind::ConstEquate(..) => {
 130                         bug!("unexpected predicate {}", predicate)
 131                     }
 132                 }
 133             }
 134             ChalkEnvironmentClause::TypeFromEnv(ty) => Some(
 135                 chalk_ir::ProgramClauseData::Implies(chalk_ir::ProgramClauseImplication {
 136                     consequence: chalk_ir::DomainGoal::FromEnv(chalk_ir::FromEnv::Ty(
 137                         ty.lower_into(interner),
 138                     )),
 139                     conditions: chalk_ir::Goals::new(interner),
 140                     priority: chalk_ir::ClausePriority::High,
 141                 })
 142                 .intern(interner),
 143             ),
 144         });
 145
 146         let goal: chalk_ir::GoalData<RustInterner<'tcx>> = self.goal.lower_into(&interner);
 147         chalk_ir::InEnvironment {
 148             environment: chalk_ir::Environment {
 149                 clauses: chalk_ir::ProgramClauses::from(&interner, clauses),
 150             },
 151             goal: goal.intern(&interner),
 152         }
 153     }
 154 }
 155
 156 impl<'tcx> LowerInto<'tcx, chalk_ir::GoalData<RustInterner<'tcx>>> for ty::Predicate<'tcx> {
 157     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::GoalData<RustInterner<'tcx>> {
 158         match self.kind() {
 159             ty::PredicateKind::Trait(predicate, _) => predicate.lower_into(interner),
 160             // FIXME(chalk): we need to register constraints.
 161             ty::PredicateKind::RegionOutlives(_predicate) => {
 162                 chalk_ir::GoalData::All(chalk_ir::Goals::new(interner))
 163             }
 164             ty::PredicateKind::TypeOutlives(_predicate) => {
 165                 chalk_ir::GoalData::All(chalk_ir::Goals::new(interner))
 166             }
 167             ty::PredicateKind::Projection(predicate) => predicate.lower_into(interner),
 168             ty::PredicateKind::WellFormed(ty) => match ty.kind {
 169                 // These types are always WF.
 170                 ty::Str | ty::Placeholder(..) | ty::Error | ty::Never => {
 171                     chalk_ir::GoalData::All(chalk_ir::Goals::new(interner))
 172                 }
 173
 174                 // FIXME(chalk): Well-formed only if ref lifetime outlives type
 175                 ty::Ref(..) => chalk_ir::GoalData::All(chalk_ir::Goals::new(interner)),
 176
 177                 ty::Param(..) => panic!("No Params expected."),
 178
 179                 // FIXME(chalk) -- ultimately I think this is what we
 180                 // want to do, and we just have rules for how to prove
 181                 // `WellFormed` for everything above, instead of
 182                 // inlining a bit the rules of the proof here.
 183                 _ => chalk_ir::GoalData::DomainGoal(chalk_ir::DomainGoal::WellFormed(
 184                     chalk_ir::WellFormed::Ty(ty.lower_into(interner)),
 185                 )),
 186             },
 187
 188             // FIXME(chalk): other predicates
 189             //
 190             // We can defer this, but ultimately we'll want to express
 191             // some of these in terms of chalk operations.
 192             ty::PredicateKind::ObjectSafe(..)
 193             | ty::PredicateKind::ClosureKind(..)
 194             | ty::PredicateKind::Subtype(..)
 195             | ty::PredicateKind::ConstEvaluatable(..)
 196             | ty::PredicateKind::ConstEquate(..) => {
 197                 chalk_ir::GoalData::All(chalk_ir::Goals::new(interner))
 198             }
 199         }
 200     }
 201 }
 202
 203 impl<'tcx> LowerInto<'tcx, chalk_ir::TraitRef<RustInterner<'tcx>>>
 204     for rustc_middle::ty::TraitRef<'tcx>
 205 {
 206     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::TraitRef<RustInterner<'tcx>> {
 207         chalk_ir::TraitRef {
 208             trait_id: chalk_ir::TraitId(RustDefId::Trait(self.def_id)),
 209             substitution: self.substs.lower_into(interner),
 210         }
 211     }
 212 }
 213
 214 impl<'tcx> LowerInto<'tcx, chalk_ir::GoalData<RustInterner<'tcx>>>
 215     for ty::PolyTraitPredicate<'tcx>
 216 {
 217     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::GoalData<RustInterner<'tcx>> {
 218         let (ty, binders, _named_regions) = collect_bound_vars(interner, interner.tcx, &self);
 219
 220         chalk_ir::GoalData::Quantified(
 221             chalk_ir::QuantifierKind::ForAll,
 222             chalk_ir::Binders::new(
 223                 binders,
 224                 chalk_ir::GoalData::DomainGoal(chalk_ir::DomainGoal::Holds(
 225                     chalk_ir::WhereClause::Implemented(ty.trait_ref.lower_into(interner)),
 226                 ))
 227                 .intern(interner),
 228             ),
 229         )
 230     }
 231 }
 232
 233 impl<'tcx> LowerInto<'tcx, chalk_ir::AliasEq<RustInterner<'tcx>>>
 234     for rustc_middle::ty::ProjectionPredicate<'tcx>
 235 {
 236     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::AliasEq<RustInterner<'tcx>> {
 237         chalk_ir::AliasEq {
 238             ty: self.ty.lower_into(interner),
 239             alias: self.projection_ty.lower_into(interner),
 240         }
 241     }
 242 }
 243
 244 impl<'tcx> LowerInto<'tcx, chalk_ir::GoalData<RustInterner<'tcx>>>
 245     for ty::PolyProjectionPredicate<'tcx>
 246 {
 247     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::GoalData<RustInterner<'tcx>> {
 248         let (ty, binders, _named_regions) = collect_bound_vars(interner, interner.tcx, &self);
 249
 250         chalk_ir::GoalData::Quantified(
 251             chalk_ir::QuantifierKind::ForAll,
 252             chalk_ir::Binders::new(
 253                 binders,
 254                 chalk_ir::GoalData::DomainGoal(chalk_ir::DomainGoal::Holds(
 255                     chalk_ir::WhereClause::AliasEq(ty.lower_into(interner)),
 256                 ))
 257                 .intern(interner),
 258             ),
 259         )
 260     }
 261 }
 262
 263 impl<'tcx> LowerInto<'tcx, chalk_ir::Ty<RustInterner<'tcx>>> for Ty<'tcx> {
 264     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::Ty<RustInterner<'tcx>> {
 265         use chalk_ir::TyData;
 266         use rustc_ast::ast;
 267         use TyKind::*;
 268
 269         let empty = || chalk_ir::Substitution::empty(interner);
 270         let struct_ty = |def_id| chalk_ir::TypeName::Struct(chalk_ir::StructId(def_id));
 271         let apply = |name, substitution| {
 272             TyData::Apply(chalk_ir::ApplicationTy { name, substitution }).intern(interner)
 273         };
 274         let int = |i| apply(chalk_ir::TypeName::Scalar(chalk_ir::Scalar::Int(i)), empty());
 275         let uint = |i| apply(chalk_ir::TypeName::Scalar(chalk_ir::Scalar::Uint(i)), empty());
 276         let float = |f| apply(chalk_ir::TypeName::Scalar(chalk_ir::Scalar::Float(f)), empty());
 277
 278         match self.kind {
 279             Bool => apply(chalk_ir::TypeName::Scalar(chalk_ir::Scalar::Bool), empty()),
 280             Char => apply(chalk_ir::TypeName::Scalar(chalk_ir::Scalar::Char), empty()),
 281             Int(ty) => match ty {
 282                 ast::IntTy::Isize => int(chalk_ir::IntTy::Isize),
 283                 ast::IntTy::I8 => int(chalk_ir::IntTy::I8),
 284                 ast::IntTy::I16 => int(chalk_ir::IntTy::I16),
 285                 ast::IntTy::I32 => int(chalk_ir::IntTy::I32),
 286                 ast::IntTy::I64 => int(chalk_ir::IntTy::I64),
 287                 ast::IntTy::I128 => int(chalk_ir::IntTy::I128),
 288             },
 289             Uint(ty) => match ty {
 290                 ast::UintTy::Usize => uint(chalk_ir::UintTy::Usize),
 291                 ast::UintTy::U8 => uint(chalk_ir::UintTy::U8),
 292                 ast::UintTy::U16 => uint(chalk_ir::UintTy::U16),
 293                 ast::UintTy::U32 => uint(chalk_ir::UintTy::U32),
 294                 ast::UintTy::U64 => uint(chalk_ir::UintTy::U64),
 295                 ast::UintTy::U128 => uint(chalk_ir::UintTy::U128),
 296             },
 297             Float(ty) => match ty {
 298                 ast::FloatTy::F32 => float(chalk_ir::FloatTy::F32),
 299                 ast::FloatTy::F64 => float(chalk_ir::FloatTy::F64),
 300             },
 301             Adt(def, substs) => {
 302                 apply(struct_ty(RustDefId::Adt(def.did)), substs.lower_into(interner))
 303             }
 304             Foreign(_def_id) => unimplemented!(),
 305             Str => apply(struct_ty(RustDefId::Str), empty()),
 306             Array(ty, _) => apply(
 307                 struct_ty(RustDefId::Array),
 308                 chalk_ir::Substitution::from1(
 309                     interner,
 310                     chalk_ir::ParameterKind::Ty(ty.lower_into(interner)).intern(interner),
 311                 ),
 312             ),
 313             Slice(ty) => apply(
 314                 struct_ty(RustDefId::Slice),
 315                 chalk_ir::Substitution::from1(
 316                     interner,
 317                     chalk_ir::ParameterKind::Ty(ty.lower_into(interner)).intern(interner),
 318                 ),
 319             ),
 320             RawPtr(_) => apply(struct_ty(RustDefId::RawPtr), empty()),
 321             Ref(region, ty, mutability) => apply(
 322                 struct_ty(RustDefId::Ref(mutability)),
 323                 chalk_ir::Substitution::from(
 324                     interner,
 325                     [
 326                         chalk_ir::ParameterKind::Lifetime(region.lower_into(interner))
 327                             .intern(interner),
 328                         chalk_ir::ParameterKind::Ty(ty.lower_into(interner)).intern(interner),
 329                     ]
 330                     .iter(),
 331                 ),
 332             ),
 333             FnDef(def_id, _) => apply(struct_ty(RustDefId::FnDef(def_id)), empty()),
 334             FnPtr(sig) => {
 335                 let (inputs_and_outputs, binders, _named_regions) =
 336                     collect_bound_vars(interner, interner.tcx, &sig.inputs_and_output());
 337                 TyData::Function(chalk_ir::Fn {
 338                     num_binders: binders.len(interner),
 339                     substitution: chalk_ir::Substitution::from(
 340                         interner,
 341                         inputs_and_outputs.iter().map(|ty| {
 342                             chalk_ir::ParameterKind::Ty(ty.lower_into(interner)).intern(interner)
 343                         }),
 344                     ),
 345                 })
 346                 .intern(interner)
 347             }
 348             Dynamic(_, _) => unimplemented!(),
 349             Closure(_def_id, _) => unimplemented!(),
 350             Generator(_def_id, _substs, _) => unimplemented!(),
 351             GeneratorWitness(_) => unimplemented!(),
 352             Never => apply(struct_ty(RustDefId::Never), empty()),
 353             Tuple(substs) => {
 354                 apply(chalk_ir::TypeName::Tuple(substs.len()), substs.lower_into(interner))
 355             }
 356             Projection(proj) => TyData::Alias(proj.lower_into(interner)).intern(interner),
 357             Opaque(_def_id, _substs) => unimplemented!(),
 358             // This should have been done eagerly prior to this, and all Params
 359             // should have been substituted to placeholders
 360             Param(_) => panic!("Lowering Param when not expected."),
 361             Bound(db, bound) => TyData::BoundVar(chalk_ir::BoundVar::new(
 362                 chalk_ir::DebruijnIndex::new(db.as_u32()),
 363                 bound.var.index(),
 364             ))
 365             .intern(interner),
 366             Placeholder(_placeholder) => TyData::Placeholder(chalk_ir::PlaceholderIndex {
 367                 ui: chalk_ir::UniverseIndex { counter: _placeholder.universe.as_usize() },
 368                 idx: _placeholder.name.as_usize(),
 369             })
 370             .intern(interner),
 371             Infer(_infer) => unimplemented!(),
 372             Error => unimplemented!(),
 373         }
 374     }
 375 }
 376
 377 impl<'tcx> LowerInto<'tcx, chalk_ir::Lifetime<RustInterner<'tcx>>> for Region<'tcx> {
 378     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::Lifetime<RustInterner<'tcx>> {
 379         use rustc_middle::ty::RegionKind::*;
 380
 381         match self {
 382             ReEarlyBound(_) => {
 383                 panic!("Should have already been substituted.");
 384             }
 385             ReLateBound(db, br) => match br {
 386                 ty::BoundRegion::BrAnon(var) => {
 387                     chalk_ir::LifetimeData::BoundVar(chalk_ir::BoundVar::new(
 388                         chalk_ir::DebruijnIndex::new(db.as_u32()),
 389                         *var as usize,
 390                     ))
 391                     .intern(interner)
 392                 }
 393                 ty::BoundRegion::BrNamed(_def_id, _name) => unimplemented!(),
 394                 ty::BrEnv => unimplemented!(),
 395             },
 396             ReFree(_) => unimplemented!(),
 397             ReStatic => unimplemented!(),
 398             ReVar(_) => unimplemented!(),
 399             RePlaceholder(placeholder_region) => {
 400                 chalk_ir::LifetimeData::Placeholder(chalk_ir::PlaceholderIndex {
 401                     ui: chalk_ir::UniverseIndex { counter: placeholder_region.universe.index() },
 402                     idx: 0,
 403                 })
 404                 .intern(interner)
 405             }
 406             ReEmpty(_) => unimplemented!(),
 407             ReErased => unimplemented!(),
 408         }
 409     }
 410 }
 411
 412 impl<'tcx> LowerInto<'tcx, chalk_ir::Parameter<RustInterner<'tcx>>> for GenericArg<'tcx> {
 413     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::Parameter<RustInterner<'tcx>> {
 414         match self.unpack() {
 415             ty::subst::GenericArgKind::Type(ty) => {
 416                 chalk_ir::ParameterKind::Ty(ty.lower_into(interner))
 417             }
 418             ty::subst::GenericArgKind::Lifetime(lifetime) => {
 419                 chalk_ir::ParameterKind::Lifetime(lifetime.lower_into(interner))
 420             }
 421             ty::subst::GenericArgKind::Const(_) => chalk_ir::ParameterKind::Ty(
 422                 chalk_ir::TyData::Apply(chalk_ir::ApplicationTy {
 423                     name: chalk_ir::TypeName::Tuple(0),
 424                     substitution: chalk_ir::Substitution::empty(interner),
 425                 })
 426                 .intern(interner),
 427             ),
 428         }
 429         .intern(interner)
 430     }
 431 }
 432
 433 // We lower into an Option here since there are some predicates which Chalk
 434 // doesn't have a representation for yet (as a `WhereClause`), but are so common
 435 // that we just are accepting the unsoundness for now. The `Option` will
 436 // eventually be removed.
 437 impl<'tcx> LowerInto<'tcx, Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>>>
 438     for ty::Predicate<'tcx>
 439 {
 440     fn lower_into(
 441         self,
 442         interner: &RustInterner<'tcx>,
 443     ) -> Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>> {
 444         match &self.kind() {
 445             ty::PredicateKind::Trait(predicate, _) => {
 446                 let (predicate, binders, _named_regions) =
 447                     collect_bound_vars(interner, interner.tcx, predicate);
 448
 449                 Some(chalk_ir::Binders::new(
 450                     binders,
 451                     chalk_ir::WhereClause::Implemented(predicate.trait_ref.lower_into(interner)),
 452                 ))
 453             }
 454             ty::PredicateKind::RegionOutlives(_predicate) => None,
 455             ty::PredicateKind::TypeOutlives(_predicate) => None,
 456             ty::PredicateKind::Projection(_predicate) => None,
 457             ty::PredicateKind::WellFormed(_ty) => None,
 458
 459             ty::PredicateKind::ObjectSafe(..)
 460             | ty::PredicateKind::ClosureKind(..)
 461             | ty::PredicateKind::Subtype(..)
 462             | ty::PredicateKind::ConstEvaluatable(..)
 463             | ty::PredicateKind::ConstEquate(..) => bug!("unexpected predicate {}", &self),
 464         }
 465     }
 466 }
 467
 468 /// To collect bound vars, we have to do two passes. In the first pass, we
 469 /// collect all `BoundRegion`s and `ty::Bound`s. In the second pass, we then
 470 /// replace `BrNamed` into `BrAnon`. The two separate passes are important,
 471 /// since we can only replace `BrNamed` with `BrAnon`s with indices *after* all
 472 /// "real" `BrAnon`s.
 473 ///
 474 /// It's important to note that because of prior substitution, we may have
 475 /// late-bound regions, even outside of fn contexts, since this is the best way
 476 /// to prep types for chalk lowering.
 477 crate fn collect_bound_vars<'a, 'tcx, T: TypeFoldable<'tcx>>(
 478     interner: &RustInterner<'tcx>,
 479     tcx: TyCtxt<'tcx>,
 480     ty: &'a Binder<T>,
 481 ) -> (T, chalk_ir::ParameterKinds<RustInterner<'tcx>>, BTreeMap<DefId, u32>) {
 482     let mut bound_vars_collector = BoundVarsCollector::new();
 483     ty.skip_binder().visit_with(&mut bound_vars_collector);
 484     let mut parameters = bound_vars_collector.parameters;
 485     let named_parameters: BTreeMap<DefId, u32> = bound_vars_collector
 486         .named_parameters
 487         .into_iter()
 488         .enumerate()
 489         .map(|(i, def_id)| (def_id, (i + parameters.len()) as u32))
 490         .collect();
 491
 492     let mut bound_var_substitutor = NamedBoundVarSubstitutor::new(tcx, &named_parameters);
 493     let new_ty = ty.skip_binder().fold_with(&mut bound_var_substitutor);
 494
 495     for var in named_parameters.values() {
 496         parameters.insert(*var, chalk_ir::ParameterKind::Lifetime(()));
 497     }
 498
 499     (0..parameters.len()).for_each(|i| {
 500         parameters.get(&(i as u32)).expect("Skipped bound var index.");
 501     });
 502
 503     let binders = chalk_ir::ParameterKinds::from(interner, parameters.into_iter().map(|(_, v)| v));
 504
 505     (new_ty, binders, named_parameters)
 506 }
 507
 508 crate struct BoundVarsCollector {
 509     binder_index: ty::DebruijnIndex,
 510     crate parameters: BTreeMap<u32, chalk_ir::ParameterKind<()>>,
 511     crate named_parameters: Vec<DefId>,
 512 }
 513
 514 impl BoundVarsCollector {
 515     crate fn new() -> Self {
 516         BoundVarsCollector {
 517             binder_index: ty::INNERMOST,
 518             parameters: BTreeMap::new(),
 519             named_parameters: vec![],
 520         }
 521     }
 522 }
 523
 524 impl<'tcx> TypeVisitor<'tcx> for BoundVarsCollector {
 525     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool {
 526         self.binder_index.shift_in(1);
 527         let result = t.super_visit_with(self);
 528         self.binder_index.shift_out(1);
 529         result
 530     }
 531
 532     fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
 533         match t.kind {
 534             ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => {
 535                 match self.parameters.entry(bound_ty.var.as_u32()) {
 536                     Entry::Vacant(entry) => {
 537                         entry.insert(chalk_ir::ParameterKind::Ty(()));
 538                     }
 539                     Entry::Occupied(entry) => {
 540                         entry.get().assert_ty_ref();
 541                     }
 542                 }
 543             }
 544
 545             _ => (),
 546         };
 547
 548         t.super_visit_with(self)
 549     }
 550
 551     fn visit_region(&mut self, r: Region<'tcx>) -> bool {
 552         match r {
 553             ty::ReLateBound(index, br) if *index == self.binder_index => match br {
 554                 ty::BoundRegion::BrNamed(def_id, _name) => {
 555                     if self.named_parameters.iter().find(|d| *d == def_id).is_none() {
 556                         self.named_parameters.push(*def_id);
 557                     }
 558                 }
 559
 560                 ty::BoundRegion::BrAnon(var) => match self.parameters.entry(*var) {
 561                     Entry::Vacant(entry) => {
 562                         entry.insert(chalk_ir::ParameterKind::Lifetime(()));
 563                     }
 564                     Entry::Occupied(entry) => {
 565                         entry.get().assert_lifetime_ref();
 566                     }
 567                 },
 568
 569                 ty::BrEnv => unimplemented!(),
 570             },
 571
 572             ty::ReEarlyBound(_re) => {
 573                 // FIXME(chalk): jackh726 - I think we should always have already
 574                 // substituted away `ReEarlyBound`s for `ReLateBound`s, but need to confirm.
 575                 unimplemented!();
 576             }
 577
 578             _ => (),
 579         };
 580
 581         r.super_visit_with(self)
 582     }
 583 }
 584
 585 /// This is used to replace `BoundRegion::BrNamed` with `BoundRegion::BrAnon`.
 586 /// Note: we assume that we will always have room for more bound vars. (i.e. we
 587 /// won't ever hit the `u32` limit in `BrAnon`s).
 588 struct NamedBoundVarSubstitutor<'a, 'tcx> {
 589     tcx: TyCtxt<'tcx>,
 590     binder_index: ty::DebruijnIndex,
 591     named_parameters: &'a BTreeMap<DefId, u32>,
 592 }
 593
 594 impl<'a, 'tcx> NamedBoundVarSubstitutor<'a, 'tcx> {
 595     fn new(tcx: TyCtxt<'tcx>, named_parameters: &'a BTreeMap<DefId, u32>) -> Self {
 596         NamedBoundVarSubstitutor { tcx, binder_index: ty::INNERMOST, named_parameters }
 597     }
 598 }
 599
 600 impl<'a, 'tcx> TypeFolder<'tcx> for NamedBoundVarSubstitutor<'a, 'tcx> {
 601     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 602         self.tcx
 603     }
 604
 605     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> Binder<T> {
 606         self.binder_index.shift_in(1);
 607         let result = t.super_fold_with(self);
 608         self.binder_index.shift_out(1);
 609         result
 610     }
 611
 612     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 613         t.super_fold_with(self)
 614     }
 615
 616     fn fold_region(&mut self, r: Region<'tcx>) -> Region<'tcx> {
 617         match r {
 618             ty::ReLateBound(index, br) if *index == self.binder_index => match br {
 619                 ty::BoundRegion::BrNamed(def_id, _name) => {
 620                     match self.named_parameters.get(def_id) {
 621                         Some(idx) => {
 622                             return self.tcx.mk_region(RegionKind::ReLateBound(
 623                                 *index,
 624                                 BoundRegion::BrAnon(*idx),
 625                             ));
 626                         }
 627                         None => panic!("Missing `BrNamed`."),
 628                     }
 629                 }
 630                 ty::BrEnv => unimplemented!(),
 631                 ty::BoundRegion::BrAnon(_) => {}
 632             },
 633             _ => (),
 634         };
 635
 636         r.super_fold_with(self)
 637     }
 638 }
 639
 640 /// Used to substitute `Param`s with placeholders. We do this since Chalk
 641 /// have a notion of `Param`s.
 642 crate struct ParamsSubstitutor<'tcx> {
 643     tcx: TyCtxt<'tcx>,
 644     binder_index: ty::DebruijnIndex,
 645     list: Vec<rustc_middle::ty::ParamTy>,
 646     crate params: rustc_data_structures::fx::FxHashMap<usize, rustc_middle::ty::ParamTy>,
 647     crate named_regions: BTreeMap<DefId, u32>,
 648 }
 649
 650 impl<'tcx> ParamsSubstitutor<'tcx> {
 651     crate fn new(tcx: TyCtxt<'tcx>) -> Self {
 652         ParamsSubstitutor {
 653             tcx,
 654             binder_index: ty::INNERMOST,
 655             list: vec![],
 656             params: rustc_data_structures::fx::FxHashMap::default(),
 657             named_regions: BTreeMap::default(),
 658         }
 659     }
 660 }
 661
 662 impl<'tcx> TypeFolder<'tcx> for ParamsSubstitutor<'tcx> {
 663     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 664         self.tcx
 665     }
 666
 667     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> Binder<T> {
 668         self.binder_index.shift_in(1);
 669         let result = t.super_fold_with(self);
 670         self.binder_index.shift_out(1);
 671         result
 672     }
 673
 674     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 675         match t.kind {
 676             // FIXME(chalk): currently we convert params to placeholders starting at
 677             // index `0`. To support placeholders, we'll actually need to do a
 678             // first pass to collect placeholders. Then we can insert params after.
 679             ty::Placeholder(_) => unimplemented!(),
 680             ty::Param(param) => match self.list.iter().position(|r| r == &param) {
 681                 Some(_idx) => self.tcx.mk_ty(ty::Placeholder(ty::PlaceholderType {
 682                     universe: ty::UniverseIndex::from_usize(0),
 683                     name: ty::BoundVar::from_usize(_idx),
 684                 })),
 685                 None => {
 686                     self.list.push(param);
 687                     let idx = self.list.len() - 1;
 688                     self.params.insert(idx, param);
 689                     self.tcx.mk_ty(ty::Placeholder(ty::PlaceholderType {
 690                         universe: ty::UniverseIndex::from_usize(0),
 691                         name: ty::BoundVar::from_usize(idx),
 692                     }))
 693                 }
 694             },
 695
 696             _ => t.super_fold_with(self),
 697         }
 698     }
 699
 700     fn fold_region(&mut self, r: Region<'tcx>) -> Region<'tcx> {
 701         match r {
 702             // FIXME(chalk) - jackh726 - this currently isn't hit in any tests.
 703             // This covers any region variables in a goal, right?
 704             ty::ReEarlyBound(_re) => match self.named_regions.get(&_re.def_id) {
 705                 Some(idx) => self.tcx.mk_region(RegionKind::ReLateBound(
 706                     self.binder_index,
 707                     BoundRegion::BrAnon(*idx),
 708                 )),
 709                 None => {
 710                     let idx = self.named_regions.len() as u32;
 711                     self.named_regions.insert(_re.def_id, idx);
 712                     self.tcx.mk_region(RegionKind::ReLateBound(
 713                         self.binder_index,
 714                         BoundRegion::BrAnon(idx),
 715                     ))
 716                 }
 717             },
 718
 719             _ => r.super_fold_with(self),
 720         }
 721     }
 722 }