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