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