src/librustc_traits/chalk/lowering.rs

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