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                 struct_ty(RustDefId::Array),
 315                 chalk_ir::Substitution::from1(
 316                     interner,
 317                     chalk_ir::GenericArgData::Ty(ty.lower_into(interner)).intern(interner),
 318                 ),
 319             ),
 320             Slice(ty) => apply(
 321                 chalk_ir::TypeName::Slice,
 322                 chalk_ir::Substitution::from1(
 323                     interner,
 324                     chalk_ir::GenericArgData::Ty(ty.lower_into(interner)).intern(interner),
 325                 ),
 326             ),
 327             RawPtr(ptr) => {
 328                 let name = match ptr.mutbl {
 329                     ast::Mutability::Mut => chalk_ir::TypeName::Raw(chalk_ir::Mutability::Mut),
 330                     ast::Mutability::Not => chalk_ir::TypeName::Raw(chalk_ir::Mutability::Not),
 331                 };
 332                 apply(name, chalk_ir::Substitution::from1(interner, ptr.ty.lower_into(interner)))
 333             }
 334             Ref(region, ty, mutability) => {
 335                 let name = match mutability {
 336                     ast::Mutability::Mut => chalk_ir::TypeName::Ref(chalk_ir::Mutability::Mut),
 337                     ast::Mutability::Not => chalk_ir::TypeName::Ref(chalk_ir::Mutability::Not),
 338                 };
 339                 apply(
 340                     name,
 341                     chalk_ir::Substitution::from(
 342                         interner,
 343                         &[
 344                             chalk_ir::GenericArgData::Lifetime(region.lower_into(interner))
 345                                 .intern(interner),
 346                             chalk_ir::GenericArgData::Ty(ty.lower_into(interner)).intern(interner),
 347                         ],
 348                     ),
 349                 )
 350             }
 351             FnDef(def_id, _) => apply(struct_ty(RustDefId::FnDef(def_id)), empty()),
 352             FnPtr(sig) => {
 353                 let (inputs_and_outputs, binders, _named_regions) =
 354                     collect_bound_vars(interner, interner.tcx, &sig.inputs_and_output());
 355                 TyData::Function(chalk_ir::Fn {
 356                     num_binders: binders.len(interner),
 357                     substitution: chalk_ir::Substitution::from(
 358                         interner,
 359                         inputs_and_outputs.iter().map(|ty| {
 360                             chalk_ir::GenericArgData::Ty(ty.lower_into(interner)).intern(interner)
 361                         }),
 362                     ),
 363                 })
 364                 .intern(interner)
 365             }
 366             // FIXME(chalk): add region
 367             Dynamic(predicates, _region) => {
 368                 TyData::Dyn(chalk_ir::DynTy { bounds: predicates.lower_into(interner) })
 369                     .intern(interner)
 370             }
 371             Closure(_def_id, _) => unimplemented!(),
 372             Generator(_def_id, _substs, _) => unimplemented!(),
 373             GeneratorWitness(_) => unimplemented!(),
 374             Never => apply(struct_ty(RustDefId::Never), empty()),
 375             Tuple(substs) => {
 376                 apply(chalk_ir::TypeName::Tuple(substs.len()), substs.lower_into(interner))
 377             }
 378             Projection(proj) => TyData::Alias(proj.lower_into(interner)).intern(interner),
 379             Opaque(def_id, substs) => {
 380                 TyData::Alias(chalk_ir::AliasTy::Opaque(chalk_ir::OpaqueTy {
 381                     opaque_ty_id: chalk_ir::OpaqueTyId(RustDefId::Opaque(def_id)),
 382                     substitution: substs.lower_into(interner),
 383                 }))
 384                 .intern(interner)
 385             }
 386             // This should have been done eagerly prior to this, and all Params
 387             // should have been substituted to placeholders
 388             Param(_) => panic!("Lowering Param when not expected."),
 389             Bound(db, bound) => TyData::BoundVar(chalk_ir::BoundVar::new(
 390                 chalk_ir::DebruijnIndex::new(db.as_u32()),
 391                 bound.var.index(),
 392             ))
 393             .intern(interner),
 394             Placeholder(_placeholder) => TyData::Placeholder(chalk_ir::PlaceholderIndex {
 395                 ui: chalk_ir::UniverseIndex { counter: _placeholder.universe.as_usize() },
 396                 idx: _placeholder.name.as_usize(),
 397             })
 398             .intern(interner),
 399             Infer(_infer) => unimplemented!(),
 400             Error(_) => apply(chalk_ir::TypeName::Error, empty()),
 401         }
 402     }
 403 }
 404
 405 impl<'tcx> LowerInto<'tcx, chalk_ir::Lifetime<RustInterner<'tcx>>> for Region<'tcx> {
 406     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::Lifetime<RustInterner<'tcx>> {
 407         use rustc_middle::ty::RegionKind::*;
 408
 409         match self {
 410             ReEarlyBound(_) => {
 411                 panic!("Should have already been substituted.");
 412             }
 413             ReLateBound(db, br) => match br {
 414                 ty::BoundRegion::BrAnon(var) => {
 415                     chalk_ir::LifetimeData::BoundVar(chalk_ir::BoundVar::new(
 416                         chalk_ir::DebruijnIndex::new(db.as_u32()),
 417                         *var as usize,
 418                     ))
 419                     .intern(interner)
 420                 }
 421                 ty::BoundRegion::BrNamed(_def_id, _name) => unimplemented!(),
 422                 ty::BrEnv => unimplemented!(),
 423             },
 424             ReFree(_) => unimplemented!(),
 425             // FIXME(chalk): need to handle ReStatic
 426             ReStatic => unimplemented!(),
 427             ReVar(_) => unimplemented!(),
 428             RePlaceholder(placeholder_region) => {
 429                 chalk_ir::LifetimeData::Placeholder(chalk_ir::PlaceholderIndex {
 430                     ui: chalk_ir::UniverseIndex { counter: placeholder_region.universe.index() },
 431                     idx: 0,
 432                 })
 433                 .intern(interner)
 434             }
 435             ReEmpty(_) => unimplemented!(),
 436             // FIXME(chalk): need to handle ReErased
 437             ReErased => unimplemented!(),
 438         }
 439     }
 440 }
 441
 442 impl<'tcx> LowerInto<'tcx, chalk_ir::GenericArg<RustInterner<'tcx>>> for GenericArg<'tcx> {
 443     fn lower_into(self, interner: &RustInterner<'tcx>) -> chalk_ir::GenericArg<RustInterner<'tcx>> {
 444         match self.unpack() {
 445             ty::subst::GenericArgKind::Type(ty) => {
 446                 chalk_ir::GenericArgData::Ty(ty.lower_into(interner))
 447             }
 448             ty::subst::GenericArgKind::Lifetime(lifetime) => {
 449                 chalk_ir::GenericArgData::Lifetime(lifetime.lower_into(interner))
 450             }
 451             ty::subst::GenericArgKind::Const(_) => chalk_ir::GenericArgData::Ty(
 452                 chalk_ir::TyData::Apply(chalk_ir::ApplicationTy {
 453                     name: chalk_ir::TypeName::Tuple(0),
 454                     substitution: chalk_ir::Substitution::empty(interner),
 455                 })
 456                 .intern(interner),
 457             ),
 458         }
 459         .intern(interner)
 460     }
 461 }
 462
 463 // We lower into an Option here since there are some predicates which Chalk
 464 // doesn't have a representation for yet (as a `WhereClause`), but are so common
 465 // that we just are accepting the unsoundness for now. The `Option` will
 466 // eventually be removed.
 467 impl<'tcx> LowerInto<'tcx, Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>>>
 468     for ty::Predicate<'tcx>
 469 {
 470     fn lower_into(
 471         self,
 472         interner: &RustInterner<'tcx>,
 473     ) -> Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>> {
 474         match &self.kind() {
 475             ty::PredicateKind::Trait(predicate, _) => {
 476                 let (predicate, binders, _named_regions) =
 477                     collect_bound_vars(interner, interner.tcx, predicate);
 478
 479                 Some(chalk_ir::Binders::new(
 480                     binders,
 481                     chalk_ir::WhereClause::Implemented(predicate.trait_ref.lower_into(interner)),
 482                 ))
 483             }
 484             ty::PredicateKind::RegionOutlives(_predicate) => None,
 485             ty::PredicateKind::TypeOutlives(_predicate) => None,
 486             ty::PredicateKind::Projection(_predicate) => None,
 487             ty::PredicateKind::WellFormed(_ty) => None,
 488
 489             ty::PredicateKind::ObjectSafe(..)
 490             | ty::PredicateKind::ClosureKind(..)
 491             | ty::PredicateKind::Subtype(..)
 492             | ty::PredicateKind::ConstEvaluatable(..)
 493             | ty::PredicateKind::ConstEquate(..) => bug!("unexpected predicate {}", &self),
 494         }
 495     }
 496 }
 497
 498 impl<'tcx> LowerInto<'tcx, chalk_ir::Binders<chalk_ir::QuantifiedWhereClauses<RustInterner<'tcx>>>>
 499     for Binder<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>>
 500 {
 501     fn lower_into(
 502         self,
 503         interner: &RustInterner<'tcx>,
 504     ) -> chalk_ir::Binders<chalk_ir::QuantifiedWhereClauses<RustInterner<'tcx>>> {
 505         let (predicates, binders, _named_regions) =
 506             collect_bound_vars(interner, interner.tcx, &self);
 507         let where_clauses = predicates.into_iter().map(|predicate| match predicate {
 508             ty::ExistentialPredicate::Trait(ty::ExistentialTraitRef { def_id, substs }) => {
 509                 chalk_ir::Binders::new(
 510                     chalk_ir::VariableKinds::new(interner),
 511                     chalk_ir::WhereClause::Implemented(chalk_ir::TraitRef {
 512                         trait_id: chalk_ir::TraitId(RustDefId::Trait(*def_id)),
 513                         substitution: substs.lower_into(interner),
 514                     }),
 515                 )
 516             }
 517             ty::ExistentialPredicate::Projection(_predicate) => unimplemented!(),
 518             ty::ExistentialPredicate::AutoTrait(def_id) => chalk_ir::Binders::new(
 519                 chalk_ir::VariableKinds::new(interner),
 520                 chalk_ir::WhereClause::Implemented(chalk_ir::TraitRef {
 521                     trait_id: chalk_ir::TraitId(RustDefId::Trait(*def_id)),
 522                     substitution: chalk_ir::Substitution::empty(interner),
 523                 }),
 524             ),
 525         });
 526         let value = chalk_ir::QuantifiedWhereClauses::from(interner, where_clauses);
 527         chalk_ir::Binders::new(binders, value)
 528     }
 529 }
 530
 531 /// To collect bound vars, we have to do two passes. In the first pass, we
 532 /// collect all `BoundRegion`s and `ty::Bound`s. In the second pass, we then
 533 /// replace `BrNamed` into `BrAnon`. The two separate passes are important,
 534 /// since we can only replace `BrNamed` with `BrAnon`s with indices *after* all
 535 /// "real" `BrAnon`s.
 536 ///
 537 /// It's important to note that because of prior substitution, we may have
 538 /// late-bound regions, even outside of fn contexts, since this is the best way
 539 /// to prep types for chalk lowering.
 540 crate fn collect_bound_vars<'a, 'tcx, T: TypeFoldable<'tcx>>(
 541     interner: &RustInterner<'tcx>,
 542     tcx: TyCtxt<'tcx>,
 543     ty: &'a Binder<T>,
 544 ) -> (T, chalk_ir::VariableKinds<RustInterner<'tcx>>, BTreeMap<DefId, u32>) {
 545     let mut bound_vars_collector = BoundVarsCollector::new();
 546     ty.skip_binder().visit_with(&mut bound_vars_collector);
 547     let mut parameters = bound_vars_collector.parameters;
 548     let named_parameters: BTreeMap<DefId, u32> = bound_vars_collector
 549         .named_parameters
 550         .into_iter()
 551         .enumerate()
 552         .map(|(i, def_id)| (def_id, (i + parameters.len()) as u32))
 553         .collect();
 554
 555     let mut bound_var_substitutor = NamedBoundVarSubstitutor::new(tcx, &named_parameters);
 556     let new_ty = ty.skip_binder().fold_with(&mut bound_var_substitutor);
 557
 558     for var in named_parameters.values() {
 559         parameters.insert(*var, chalk_ir::VariableKind::Lifetime);
 560     }
 561
 562     (0..parameters.len()).for_each(|i| {
 563         parameters.get(&(i as u32)).expect("Skipped bound var index.");
 564     });
 565
 566     let binders = chalk_ir::VariableKinds::from(interner, parameters.into_iter().map(|(_, v)| v));
 567
 568     (new_ty, binders, named_parameters)
 569 }
 570
 571 crate struct BoundVarsCollector<'tcx> {
 572     binder_index: ty::DebruijnIndex,
 573     crate parameters: BTreeMap<u32, chalk_ir::VariableKind<RustInterner<'tcx>>>,
 574     crate named_parameters: Vec<DefId>,
 575 }
 576
 577 impl<'tcx> BoundVarsCollector<'tcx> {
 578     crate fn new() -> Self {
 579         BoundVarsCollector {
 580             binder_index: ty::INNERMOST,
 581             parameters: BTreeMap::new(),
 582             named_parameters: vec![],
 583         }
 584     }
 585 }
 586
 587 impl<'tcx> TypeVisitor<'tcx> for BoundVarsCollector<'tcx> {
 588     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool {
 589         self.binder_index.shift_in(1);
 590         let result = t.super_visit_with(self);
 591         self.binder_index.shift_out(1);
 592         result
 593     }
 594
 595     fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
 596         match t.kind {
 597             ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => {
 598                 match self.parameters.entry(bound_ty.var.as_u32()) {
 599                     Entry::Vacant(entry) => {
 600                         entry.insert(chalk_ir::VariableKind::Ty(chalk_ir::TyKind::General));
 601                     }
 602                     Entry::Occupied(entry) => match entry.get() {
 603                         chalk_ir::VariableKind::Ty(_) => {}
 604                         _ => panic!(),
 605                     },
 606                 }
 607             }
 608
 609             _ => (),
 610         };
 611
 612         t.super_visit_with(self)
 613     }
 614
 615     fn visit_region(&mut self, r: Region<'tcx>) -> bool {
 616         match r {
 617             ty::ReLateBound(index, br) if *index == self.binder_index => match br {
 618                 ty::BoundRegion::BrNamed(def_id, _name) => {
 619                     if self.named_parameters.iter().find(|d| *d == def_id).is_none() {
 620                         self.named_parameters.push(*def_id);
 621                     }
 622                 }
 623
 624                 ty::BoundRegion::BrAnon(var) => match self.parameters.entry(*var) {
 625                     Entry::Vacant(entry) => {
 626                         entry.insert(chalk_ir::VariableKind::Lifetime);
 627                     }
 628                     Entry::Occupied(entry) => match entry.get() {
 629                         chalk_ir::VariableKind::Lifetime => {}
 630                         _ => panic!(),
 631                     },
 632                 },
 633
 634                 ty::BrEnv => unimplemented!(),
 635             },
 636
 637             ty::ReEarlyBound(_re) => {
 638                 // FIXME(chalk): jackh726 - I think we should always have already
 639                 // substituted away `ReEarlyBound`s for `ReLateBound`s, but need to confirm.
 640                 unimplemented!();
 641             }
 642
 643             _ => (),
 644         };
 645
 646         r.super_visit_with(self)
 647     }
 648 }
 649
 650 /// This is used to replace `BoundRegion::BrNamed` with `BoundRegion::BrAnon`.
 651 /// Note: we assume that we will always have room for more bound vars. (i.e. we
 652 /// won't ever hit the `u32` limit in `BrAnon`s).
 653 struct NamedBoundVarSubstitutor<'a, 'tcx> {
 654     tcx: TyCtxt<'tcx>,
 655     binder_index: ty::DebruijnIndex,
 656     named_parameters: &'a BTreeMap<DefId, u32>,
 657 }
 658
 659 impl<'a, 'tcx> NamedBoundVarSubstitutor<'a, 'tcx> {
 660     fn new(tcx: TyCtxt<'tcx>, named_parameters: &'a BTreeMap<DefId, u32>) -> Self {
 661         NamedBoundVarSubstitutor { tcx, binder_index: ty::INNERMOST, named_parameters }
 662     }
 663 }
 664
 665 impl<'a, 'tcx> TypeFolder<'tcx> for NamedBoundVarSubstitutor<'a, 'tcx> {
 666     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 667         self.tcx
 668     }
 669
 670     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> Binder<T> {
 671         self.binder_index.shift_in(1);
 672         let result = t.super_fold_with(self);
 673         self.binder_index.shift_out(1);
 674         result
 675     }
 676
 677     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 678         t.super_fold_with(self)
 679     }
 680
 681     fn fold_region(&mut self, r: Region<'tcx>) -> Region<'tcx> {
 682         match r {
 683             ty::ReLateBound(index, br) if *index == self.binder_index => match br {
 684                 ty::BoundRegion::BrNamed(def_id, _name) => {
 685                     match self.named_parameters.get(def_id) {
 686                         Some(idx) => {
 687                             return self.tcx.mk_region(RegionKind::ReLateBound(
 688                                 *index,
 689                                 BoundRegion::BrAnon(*idx),
 690                             ));
 691                         }
 692                         None => panic!("Missing `BrNamed`."),
 693                     }
 694                 }
 695                 ty::BrEnv => unimplemented!(),
 696                 ty::BoundRegion::BrAnon(_) => {}
 697             },
 698             _ => (),
 699         };
 700
 701         r.super_fold_with(self)
 702     }
 703 }
 704
 705 /// Used to substitute `Param`s with placeholders. We do this since Chalk
 706 /// have a notion of `Param`s.
 707 crate struct ParamsSubstitutor<'tcx> {
 708     tcx: TyCtxt<'tcx>,
 709     binder_index: ty::DebruijnIndex,
 710     list: Vec<rustc_middle::ty::ParamTy>,
 711     crate params: rustc_data_structures::fx::FxHashMap<usize, rustc_middle::ty::ParamTy>,
 712     crate named_regions: BTreeMap<DefId, u32>,
 713 }
 714
 715 impl<'tcx> ParamsSubstitutor<'tcx> {
 716     crate fn new(tcx: TyCtxt<'tcx>) -> Self {
 717         ParamsSubstitutor {
 718             tcx,
 719             binder_index: ty::INNERMOST,
 720             list: vec![],
 721             params: rustc_data_structures::fx::FxHashMap::default(),
 722             named_regions: BTreeMap::default(),
 723         }
 724     }
 725 }
 726
 727 impl<'tcx> TypeFolder<'tcx> for ParamsSubstitutor<'tcx> {
 728     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 729         self.tcx
 730     }
 731
 732     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> Binder<T> {
 733         self.binder_index.shift_in(1);
 734         let result = t.super_fold_with(self);
 735         self.binder_index.shift_out(1);
 736         result
 737     }
 738
 739     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 740         match t.kind {
 741             // FIXME(chalk): currently we convert params to placeholders starting at
 742             // index `0`. To support placeholders, we'll actually need to do a
 743             // first pass to collect placeholders. Then we can insert params after.
 744             ty::Placeholder(_) => unimplemented!(),
 745             ty::Param(param) => match self.list.iter().position(|r| r == &param) {
 746                 Some(_idx) => self.tcx.mk_ty(ty::Placeholder(ty::PlaceholderType {
 747                     universe: ty::UniverseIndex::from_usize(0),
 748                     name: ty::BoundVar::from_usize(_idx),
 749                 })),
 750                 None => {
 751                     self.list.push(param);
 752                     let idx = self.list.len() - 1;
 753                     self.params.insert(idx, param);
 754                     self.tcx.mk_ty(ty::Placeholder(ty::PlaceholderType {
 755                         universe: ty::UniverseIndex::from_usize(0),
 756                         name: ty::BoundVar::from_usize(idx),
 757                     }))
 758                 }
 759             },
 760
 761             _ => t.super_fold_with(self),
 762         }
 763     }
 764
 765     fn fold_region(&mut self, r: Region<'tcx>) -> Region<'tcx> {
 766         match r {
 767             // FIXME(chalk) - jackh726 - this currently isn't hit in any tests.
 768             // This covers any region variables in a goal, right?
 769             ty::ReEarlyBound(_re) => match self.named_regions.get(&_re.def_id) {
 770                 Some(idx) => self.tcx.mk_region(RegionKind::ReLateBound(
 771                     self.binder_index,
 772                     BoundRegion::BrAnon(*idx),
 773                 )),
 774                 None => {
 775                     let idx = self.named_regions.len() as u32;
 776                     self.named_regions.insert(_re.def_id, idx);
 777                     self.tcx.mk_region(RegionKind::ReLateBound(
 778                         self.binder_index,
 779                         BoundRegion::BrAnon(idx),
 780                     ))
 781                 }
 782             },
 783
 784             _ => r.super_fold_with(self),
 785         }
 786     }
 787 }