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