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