1 //! Contains the logic to lower rustc types into Chalk types
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
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`).
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.
24 //! ## `Const` lowering
25 //! Chalk doesn't handle consts currently, so consts are currently lowered to
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`.
35 use rustc_middle
::traits
::{ChalkEnvironmentAndGoal, ChalkRustInterner as RustInterner}
;
36 use rustc_middle
::ty
::fold
::TypeFolder
;
37 use rustc_middle
::ty
::subst
::{GenericArg, GenericArgKind, SubstsRef}
;
38 use rustc_middle
::ty
::{
39 self, Binder
, BoundRegion
, Region
, RegionKind
, Ty
, TyCtxt
, TypeFoldable
, TypeVisitor
,
41 use rustc_span
::def_id
::DefId
;
43 use chalk_ir
::{FnSig, ForeignDefId}
;
44 use rustc_hir
::Unsafety
;
45 use std
::collections
::btree_map
::{BTreeMap, Entry}
;
46 use std
::ops
::ControlFlow
;
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
;
54 impl<'tcx
> LowerInto
<'tcx
, chalk_ir
::Substitution
<RustInterner
<'tcx
>>> for SubstsRef
<'tcx
> {
57 interner
: &RustInterner
<'tcx
>,
58 ) -> chalk_ir
::Substitution
<RustInterner
<'tcx
>> {
59 chalk_ir
::Substitution
::from_iter(interner
, self.iter().map(|s
| s
.lower_into(interner
)))
63 impl<'tcx
> LowerInto
<'tcx
, SubstsRef
<'tcx
>> for &chalk_ir
::Substitution
<RustInterner
<'tcx
>> {
64 fn lower_into(self, interner
: &RustInterner
<'tcx
>) -> SubstsRef
<'tcx
> {
65 interner
.tcx
.mk_substs(self.iter(interner
).map(|subst
| subst
.lower_into(interner
)))
69 impl<'tcx
> LowerInto
<'tcx
, chalk_ir
::AliasTy
<RustInterner
<'tcx
>>> for ty
::ProjectionTy
<'tcx
> {
70 fn lower_into(self, interner
: &RustInterner
<'tcx
>) -> chalk_ir
::AliasTy
<RustInterner
<'tcx
>> {
71 chalk_ir
::AliasTy
::Projection(chalk_ir
::ProjectionTy
{
72 associated_ty_id
: chalk_ir
::AssocTypeId(self.item_def_id
),
73 substitution
: self.substs
.lower_into(interner
),
78 impl<'tcx
> LowerInto
<'tcx
, chalk_ir
::InEnvironment
<chalk_ir
::Goal
<RustInterner
<'tcx
>>>>
79 for ChalkEnvironmentAndGoal
<'tcx
>
83 interner
: &RustInterner
<'tcx
>,
84 ) -> chalk_ir
::InEnvironment
<chalk_ir
::Goal
<RustInterner
<'tcx
>>> {
85 let clauses
= self.environment
.into_iter().map(|predicate
| {
86 let (predicate
, binders
, _named_regions
) = collect_bound_vars(
89 &predicate
.bound_atom_with_opt_escaping(interner
.tcx
),
91 let consequence
= match predicate
{
92 ty
::PredicateAtom
::TypeWellFormedFromEnv(ty
) => {
93 chalk_ir
::DomainGoal
::FromEnv(chalk_ir
::FromEnv
::Ty(ty
.lower_into(interner
)))
95 ty
::PredicateAtom
::Trait(predicate
, _
) => chalk_ir
::DomainGoal
::FromEnv(
96 chalk_ir
::FromEnv
::Trait(predicate
.trait_ref
.lower_into(interner
)),
98 ty
::PredicateAtom
::RegionOutlives(predicate
) => chalk_ir
::DomainGoal
::Holds(
99 chalk_ir
::WhereClause
::LifetimeOutlives(chalk_ir
::LifetimeOutlives
{
100 a
: predicate
.0.lower_into(interner
),
101 b
: predicate
.1.lower_into(interner
),
104 ty
::PredicateAtom
::TypeOutlives(predicate
) => chalk_ir
::DomainGoal
::Holds(
105 chalk_ir
::WhereClause
::TypeOutlives(chalk_ir
::TypeOutlives
{
106 ty
: predicate
.0.lower_into(interner
),
107 lifetime
: predicate
.1.lower_into(interner
),
110 ty
::PredicateAtom
::Projection(predicate
) => chalk_ir
::DomainGoal
::Holds(
111 chalk_ir
::WhereClause
::AliasEq(predicate
.lower_into(interner
)),
113 ty
::PredicateAtom
::WellFormed(..)
114 | ty
::PredicateAtom
::ObjectSafe(..)
115 | ty
::PredicateAtom
::ClosureKind(..)
116 | ty
::PredicateAtom
::Subtype(..)
117 | ty
::PredicateAtom
::ConstEvaluatable(..)
118 | ty
::PredicateAtom
::ConstEquate(..) => bug
!("unexpected predicate {}", predicate
),
120 let value
= chalk_ir
::ProgramClauseImplication
{
122 conditions
: chalk_ir
::Goals
::empty(interner
),
123 priority
: chalk_ir
::ClausePriority
::High
,
124 constraints
: chalk_ir
::Constraints
::empty(interner
),
126 chalk_ir
::ProgramClauseData(chalk_ir
::Binders
::new(binders
, value
)).intern(interner
)
129 let goal
: chalk_ir
::GoalData
<RustInterner
<'tcx
>> = self.goal
.lower_into(&interner
);
130 chalk_ir
::InEnvironment
{
131 environment
: chalk_ir
::Environment
{
132 clauses
: chalk_ir
::ProgramClauses
::from_iter(&interner
, clauses
),
134 goal
: goal
.intern(&interner
),
139 impl<'tcx
> LowerInto
<'tcx
, chalk_ir
::GoalData
<RustInterner
<'tcx
>>> for ty
::Predicate
<'tcx
> {
140 fn lower_into(self, interner
: &RustInterner
<'tcx
>) -> chalk_ir
::GoalData
<RustInterner
<'tcx
>> {
141 let (predicate
, binders
, _named_regions
) = collect_bound_vars(
144 &self.bound_atom_with_opt_escaping(interner
.tcx
),
147 let value
= match predicate
{
148 ty
::PredicateAtom
::Trait(predicate
, _
) => {
149 chalk_ir
::GoalData
::DomainGoal(chalk_ir
::DomainGoal
::Holds(
150 chalk_ir
::WhereClause
::Implemented(predicate
.trait_ref
.lower_into(interner
)),
153 ty
::PredicateAtom
::RegionOutlives(predicate
) => {
154 chalk_ir
::GoalData
::DomainGoal(chalk_ir
::DomainGoal
::Holds(
155 chalk_ir
::WhereClause
::LifetimeOutlives(chalk_ir
::LifetimeOutlives
{
156 a
: predicate
.0.lower_into(interner
),
157 b
: predicate
.1.lower_into(interner
),
161 ty
::PredicateAtom
::TypeOutlives(predicate
) => {
162 chalk_ir
::GoalData
::DomainGoal(chalk_ir
::DomainGoal
::Holds(
163 chalk_ir
::WhereClause
::TypeOutlives(chalk_ir
::TypeOutlives
{
164 ty
: predicate
.0.lower_into(interner
),
165 lifetime
: predicate
.1.lower_into(interner
),
169 ty
::PredicateAtom
::Projection(predicate
) => {
170 chalk_ir
::GoalData
::DomainGoal(chalk_ir
::DomainGoal
::Holds(
171 chalk_ir
::WhereClause
::AliasEq(predicate
.lower_into(interner
)),
174 ty
::PredicateAtom
::WellFormed(arg
) => match arg
.unpack() {
175 GenericArgKind
::Type(ty
) => match ty
.kind() {
176 // FIXME(chalk): In Chalk, a placeholder is WellFormed if it
177 // `FromEnv`. However, when we "lower" Params, we don't update
179 ty
::Placeholder(..) => {
180 chalk_ir
::GoalData
::All(chalk_ir
::Goals
::empty(interner
))
183 _
=> chalk_ir
::GoalData
::DomainGoal(chalk_ir
::DomainGoal
::WellFormed(
184 chalk_ir
::WellFormed
::Ty(ty
.lower_into(interner
)),
187 // FIXME(chalk): handle well formed consts
188 GenericArgKind
::Const(..) => {
189 chalk_ir
::GoalData
::All(chalk_ir
::Goals
::empty(interner
))
191 GenericArgKind
::Lifetime(lt
) => bug
!("unexpect well formed predicate: {:?}", lt
),
194 ty
::PredicateAtom
::ObjectSafe(t
) => chalk_ir
::GoalData
::DomainGoal(
195 chalk_ir
::DomainGoal
::ObjectSafe(chalk_ir
::TraitId(t
)),
198 // FIXME(chalk): other predicates
200 // We can defer this, but ultimately we'll want to express
201 // some of these in terms of chalk operations.
202 ty
::PredicateAtom
::ClosureKind(..)
203 | ty
::PredicateAtom
::Subtype(..)
204 | ty
::PredicateAtom
::ConstEvaluatable(..)
205 | ty
::PredicateAtom
::ConstEquate(..) => {
206 chalk_ir
::GoalData
::All(chalk_ir
::Goals
::empty(interner
))
208 ty
::PredicateAtom
::TypeWellFormedFromEnv(ty
) => chalk_ir
::GoalData
::DomainGoal(
209 chalk_ir
::DomainGoal
::FromEnv(chalk_ir
::FromEnv
::Ty(ty
.lower_into(interner
))),
213 chalk_ir
::GoalData
::Quantified(
214 chalk_ir
::QuantifierKind
::ForAll
,
215 chalk_ir
::Binders
::new(binders
, value
.intern(interner
)),
220 impl<'tcx
> LowerInto
<'tcx
, chalk_ir
::TraitRef
<RustInterner
<'tcx
>>>
221 for rustc_middle
::ty
::TraitRef
<'tcx
>
223 fn lower_into(self, interner
: &RustInterner
<'tcx
>) -> chalk_ir
::TraitRef
<RustInterner
<'tcx
>> {
225 trait_id
: chalk_ir
::TraitId(self.def_id
),
226 substitution
: self.substs
.lower_into(interner
),
231 impl<'tcx
> LowerInto
<'tcx
, chalk_ir
::AliasEq
<RustInterner
<'tcx
>>>
232 for rustc_middle
::ty
::ProjectionPredicate
<'tcx
>
234 fn lower_into(self, interner
: &RustInterner
<'tcx
>) -> chalk_ir
::AliasEq
<RustInterner
<'tcx
>> {
236 ty
: self.ty
.lower_into(interner
),
237 alias
: self.projection_ty
.lower_into(interner
),
242 impl<'tcx
> LowerInto
<'tcx
, chalk_ir
::Ty
<RustInterner
<'tcx
>>> for Ty
<'tcx
> {
243 fn lower_into(self, interner
: &RustInterner
<'tcx
>) -> chalk_ir
::Ty
<RustInterner
<'tcx
>> {
244 use rustc_ast
as ast
;
246 let int
= |i
| chalk_ir
::TyKind
::Scalar(chalk_ir
::Scalar
::Int(i
));
247 let uint
= |i
| chalk_ir
::TyKind
::Scalar(chalk_ir
::Scalar
::Uint(i
));
248 let float
= |f
| chalk_ir
::TyKind
::Scalar(chalk_ir
::Scalar
::Float(f
));
251 ty
::Bool
=> chalk_ir
::TyKind
::Scalar(chalk_ir
::Scalar
::Bool
),
252 ty
::Char
=> chalk_ir
::TyKind
::Scalar(chalk_ir
::Scalar
::Char
),
253 ty
::Int(ty
) => match ty
{
254 ast
::IntTy
::Isize
=> int(chalk_ir
::IntTy
::Isize
),
255 ast
::IntTy
::I8
=> int(chalk_ir
::IntTy
::I8
),
256 ast
::IntTy
::I16
=> int(chalk_ir
::IntTy
::I16
),
257 ast
::IntTy
::I32
=> int(chalk_ir
::IntTy
::I32
),
258 ast
::IntTy
::I64
=> int(chalk_ir
::IntTy
::I64
),
259 ast
::IntTy
::I128
=> int(chalk_ir
::IntTy
::I128
),
261 ty
::Uint(ty
) => match ty
{
262 ast
::UintTy
::Usize
=> uint(chalk_ir
::UintTy
::Usize
),
263 ast
::UintTy
::U8
=> uint(chalk_ir
::UintTy
::U8
),
264 ast
::UintTy
::U16
=> uint(chalk_ir
::UintTy
::U16
),
265 ast
::UintTy
::U32
=> uint(chalk_ir
::UintTy
::U32
),
266 ast
::UintTy
::U64
=> uint(chalk_ir
::UintTy
::U64
),
267 ast
::UintTy
::U128
=> uint(chalk_ir
::UintTy
::U128
),
269 ty
::Float(ty
) => match ty
{
270 ast
::FloatTy
::F32
=> float(chalk_ir
::FloatTy
::F32
),
271 ast
::FloatTy
::F64
=> float(chalk_ir
::FloatTy
::F64
),
273 ty
::Adt(def
, substs
) => {
274 chalk_ir
::TyKind
::Adt(chalk_ir
::AdtId(def
), substs
.lower_into(interner
))
276 ty
::Foreign(def_id
) => chalk_ir
::TyKind
::Foreign(ForeignDefId(def_id
)),
277 ty
::Str
=> chalk_ir
::TyKind
::Str
,
278 ty
::Array(ty
, len
) => {
279 chalk_ir
::TyKind
::Array(ty
.lower_into(interner
), len
.lower_into(interner
))
281 ty
::Slice(ty
) => chalk_ir
::TyKind
::Slice(ty
.lower_into(interner
)),
284 chalk_ir
::TyKind
::Raw(ptr
.mutbl
.lower_into(interner
), ptr
.ty
.lower_into(interner
))
286 ty
::Ref(region
, ty
, mutability
) => chalk_ir
::TyKind
::Ref(
287 mutability
.lower_into(interner
),
288 region
.lower_into(interner
),
289 ty
.lower_into(interner
),
291 ty
::FnDef(def_id
, substs
) => {
292 chalk_ir
::TyKind
::FnDef(chalk_ir
::FnDefId(def_id
), substs
.lower_into(interner
))
295 let (inputs_and_outputs
, binders
, _named_regions
) =
296 collect_bound_vars(interner
, interner
.tcx
, &sig
.inputs_and_output());
297 chalk_ir
::TyKind
::Function(chalk_ir
::FnPointer
{
298 num_binders
: binders
.len(interner
),
299 sig
: sig
.lower_into(interner
),
300 substitution
: chalk_ir
::Substitution
::from_iter(
302 inputs_and_outputs
.iter().map(|ty
| {
303 chalk_ir
::GenericArgData
::Ty(ty
.lower_into(interner
)).intern(interner
)
308 ty
::Dynamic(predicates
, region
) => chalk_ir
::TyKind
::Dyn(chalk_ir
::DynTy
{
309 bounds
: predicates
.lower_into(interner
),
310 lifetime
: region
.lower_into(interner
),
312 ty
::Closure(def_id
, substs
) => {
313 chalk_ir
::TyKind
::Closure(chalk_ir
::ClosureId(def_id
), substs
.lower_into(interner
))
315 ty
::Generator(_def_id
, _substs
, _
) => unimplemented
!(),
316 ty
::GeneratorWitness(_
) => unimplemented
!(),
317 ty
::Never
=> chalk_ir
::TyKind
::Never
,
318 ty
::Tuple(substs
) => chalk_ir
::TyKind
::Tuple(substs
.len(), substs
.lower_into(interner
)),
319 ty
::Projection(proj
) => chalk_ir
::TyKind
::Alias(proj
.lower_into(interner
)),
320 ty
::Opaque(def_id
, substs
) => {
321 chalk_ir
::TyKind
::Alias(chalk_ir
::AliasTy
::Opaque(chalk_ir
::OpaqueTy
{
322 opaque_ty_id
: chalk_ir
::OpaqueTyId(def_id
),
323 substitution
: substs
.lower_into(interner
),
326 // This should have been done eagerly prior to this, and all Params
327 // should have been substituted to placeholders
328 ty
::Param(_
) => panic
!("Lowering Param when not expected."),
329 ty
::Bound(db
, bound
) => chalk_ir
::TyKind
::BoundVar(chalk_ir
::BoundVar
::new(
330 chalk_ir
::DebruijnIndex
::new(db
.as_u32()),
333 ty
::Placeholder(_placeholder
) => {
334 chalk_ir
::TyKind
::Placeholder(chalk_ir
::PlaceholderIndex
{
335 ui
: chalk_ir
::UniverseIndex { counter: _placeholder.universe.as_usize() }
,
336 idx
: _placeholder
.name
.as_usize(),
339 ty
::Infer(_infer
) => unimplemented
!(),
340 ty
::Error(_
) => chalk_ir
::TyKind
::Error
,
346 impl<'tcx
> LowerInto
<'tcx
, Ty
<'tcx
>> for &chalk_ir
::Ty
<RustInterner
<'tcx
>> {
347 fn lower_into(self, interner
: &RustInterner
<'tcx
>) -> Ty
<'tcx
> {
348 use chalk_ir
::TyKind
;
350 let kind
= match self.kind(interner
) {
351 TyKind
::Adt(struct_id
, substitution
) => {
352 ty
::Adt(struct_id
.0, substitution
.lower_into(interner
))
354 TyKind
::Scalar(scalar
) => match scalar
{
355 chalk_ir
::Scalar
::Bool
=> ty
::Bool
,
356 chalk_ir
::Scalar
::Char
=> ty
::Char
,
357 chalk_ir
::Scalar
::Int(int_ty
) => match int_ty
{
358 chalk_ir
::IntTy
::Isize
=> ty
::Int(ast
::IntTy
::Isize
),
359 chalk_ir
::IntTy
::I8
=> ty
::Int(ast
::IntTy
::I8
),
360 chalk_ir
::IntTy
::I16
=> ty
::Int(ast
::IntTy
::I16
),
361 chalk_ir
::IntTy
::I32
=> ty
::Int(ast
::IntTy
::I32
),
362 chalk_ir
::IntTy
::I64
=> ty
::Int(ast
::IntTy
::I64
),
363 chalk_ir
::IntTy
::I128
=> ty
::Int(ast
::IntTy
::I128
),
365 chalk_ir
::Scalar
::Uint(int_ty
) => match int_ty
{
366 chalk_ir
::UintTy
::Usize
=> ty
::Uint(ast
::UintTy
::Usize
),
367 chalk_ir
::UintTy
::U8
=> ty
::Uint(ast
::UintTy
::U8
),
368 chalk_ir
::UintTy
::U16
=> ty
::Uint(ast
::UintTy
::U16
),
369 chalk_ir
::UintTy
::U32
=> ty
::Uint(ast
::UintTy
::U32
),
370 chalk_ir
::UintTy
::U64
=> ty
::Uint(ast
::UintTy
::U64
),
371 chalk_ir
::UintTy
::U128
=> ty
::Uint(ast
::UintTy
::U128
),
373 chalk_ir
::Scalar
::Float(float_ty
) => match float_ty
{
374 chalk_ir
::FloatTy
::F32
=> ty
::Float(ast
::FloatTy
::F32
),
375 chalk_ir
::FloatTy
::F64
=> ty
::Float(ast
::FloatTy
::F64
),
378 TyKind
::Array(ty
, c
) => {
379 let ty
= ty
.lower_into(interner
);
380 let c
= c
.lower_into(interner
);
381 ty
::Array(ty
, interner
.tcx
.mk_const(c
))
383 TyKind
::FnDef(id
, substitution
) => ty
::FnDef(id
.0, substitution
.lower_into(interner
)),
384 TyKind
::Closure(closure
, substitution
) => {
385 ty
::Closure(closure
.0, substitution
.lower_into(interner
))
387 TyKind
::Generator(..) => unimplemented
!(),
388 TyKind
::GeneratorWitness(..) => unimplemented
!(),
389 TyKind
::Never
=> ty
::Never
,
390 TyKind
::Tuple(_len
, substitution
) => ty
::Tuple(substitution
.lower_into(interner
)),
391 TyKind
::Slice(ty
) => ty
::Slice(ty
.lower_into(interner
)),
392 TyKind
::Raw(mutbl
, ty
) => ty
::RawPtr(ty
::TypeAndMut
{
393 ty
: ty
.lower_into(interner
),
394 mutbl
: mutbl
.lower_into(interner
),
396 TyKind
::Ref(mutbl
, lifetime
, ty
) => ty
::Ref(
397 lifetime
.lower_into(interner
),
398 ty
.lower_into(interner
),
399 mutbl
.lower_into(interner
),
401 TyKind
::Str
=> ty
::Str
,
402 TyKind
::OpaqueType(opaque_ty
, substitution
) => {
403 ty
::Opaque(opaque_ty
.0, substitution
.lower_into(interner
))
405 TyKind
::AssociatedType(assoc_ty
, substitution
) => ty
::Projection(ty
::ProjectionTy
{
406 substs
: substitution
.lower_into(interner
),
407 item_def_id
: assoc_ty
.0,
409 TyKind
::Foreign(def_id
) => ty
::Foreign(def_id
.0),
410 TyKind
::Error
=> return interner
.tcx
.ty_error(),
411 TyKind
::Placeholder(placeholder
) => ty
::Placeholder(ty
::Placeholder
{
412 universe
: ty
::UniverseIndex
::from_usize(placeholder
.ui
.counter
),
413 name
: ty
::BoundVar
::from_usize(placeholder
.idx
),
415 TyKind
::Alias(alias_ty
) => match alias_ty
{
416 chalk_ir
::AliasTy
::Projection(projection
) => ty
::Projection(ty
::ProjectionTy
{
417 item_def_id
: projection
.associated_ty_id
.0,
418 substs
: projection
.substitution
.lower_into(interner
),
420 chalk_ir
::AliasTy
::Opaque(opaque
) => {
421 ty
::Opaque(opaque
.opaque_ty_id
.0, opaque
.substitution
.lower_into(interner
))
424 TyKind
::Function(_quantified_ty
) => unimplemented
!(),
425 TyKind
::BoundVar(_bound
) => ty
::Bound(
426 ty
::DebruijnIndex
::from_usize(_bound
.debruijn
.depth() as usize),
428 var
: ty
::BoundVar
::from_usize(_bound
.index
),
429 kind
: ty
::BoundTyKind
::Anon
,
432 TyKind
::InferenceVar(_
, _
) => unimplemented
!(),
433 TyKind
::Dyn(_
) => unimplemented
!(),
435 interner
.tcx
.mk_ty(kind
)
439 impl<'tcx
> LowerInto
<'tcx
, chalk_ir
::Lifetime
<RustInterner
<'tcx
>>> for Region
<'tcx
> {
440 fn lower_into(self, interner
: &RustInterner
<'tcx
>) -> chalk_ir
::Lifetime
<RustInterner
<'tcx
>> {
441 use rustc_middle
::ty
::RegionKind
::*;
445 panic
!("Should have already been substituted.");
447 ReLateBound(db
, br
) => match br
{
448 ty
::BoundRegion
::BrAnon(var
) => {
449 chalk_ir
::LifetimeData
::BoundVar(chalk_ir
::BoundVar
::new(
450 chalk_ir
::DebruijnIndex
::new(db
.as_u32()),
455 ty
::BoundRegion
::BrNamed(_def_id
, _name
) => unimplemented
!(),
456 ty
::BrEnv
=> unimplemented
!(),
458 ReFree(_
) => unimplemented
!(),
459 ReStatic
=> chalk_ir
::LifetimeData
::Static
.intern(interner
),
460 ReVar(_
) => unimplemented
!(),
461 RePlaceholder(placeholder_region
) => {
462 chalk_ir
::LifetimeData
::Placeholder(chalk_ir
::PlaceholderIndex
{
463 ui
: chalk_ir
::UniverseIndex { counter: placeholder_region.universe.index() }
,
468 ReEmpty(_
) => unimplemented
!(),
469 // FIXME(chalk): need to handle ReErased
470 ReErased
=> unimplemented
!(),
475 impl<'tcx
> LowerInto
<'tcx
, Region
<'tcx
>> for &chalk_ir
::Lifetime
<RustInterner
<'tcx
>> {
476 fn lower_into(self, interner
: &RustInterner
<'tcx
>) -> Region
<'tcx
> {
477 let kind
= match self.data(interner
) {
478 chalk_ir
::LifetimeData
::BoundVar(var
) => ty
::RegionKind
::ReLateBound(
479 ty
::DebruijnIndex
::from_u32(var
.debruijn
.depth()),
480 ty
::BoundRegion
::BrAnon(var
.index
as u32),
482 chalk_ir
::LifetimeData
::InferenceVar(_var
) => unimplemented
!(),
483 chalk_ir
::LifetimeData
::Placeholder(p
) => {
484 ty
::RegionKind
::RePlaceholder(ty
::Placeholder
{
485 universe
: ty
::UniverseIndex
::from_usize(p
.ui
.counter
),
486 name
: ty
::BoundRegion
::BrAnon(p
.idx
as u32),
489 chalk_ir
::LifetimeData
::Static
=> ty
::RegionKind
::ReStatic
,
490 chalk_ir
::LifetimeData
::Phantom(_
, _
) => unimplemented
!(),
492 interner
.tcx
.mk_region(kind
)
496 impl<'tcx
> LowerInto
<'tcx
, chalk_ir
::Const
<RustInterner
<'tcx
>>> for ty
::Const
<'tcx
> {
497 fn lower_into(self, interner
: &RustInterner
<'tcx
>) -> chalk_ir
::Const
<RustInterner
<'tcx
>> {
498 let ty
= self.ty
.lower_into(interner
);
499 let value
= match self.val
{
500 ty
::ConstKind
::Value(val
) => {
501 chalk_ir
::ConstValue
::Concrete(chalk_ir
::ConcreteConst { interned: val }
)
503 ty
::ConstKind
::Bound(db
, bound
) => chalk_ir
::ConstValue
::BoundVar(
504 chalk_ir
::BoundVar
::new(chalk_ir
::DebruijnIndex
::new(db
.as_u32()), bound
.index()),
506 _
=> unimplemented
!("Const not implemented. {:?}", self),
508 chalk_ir
::ConstData { ty, value }
.intern(interner
)
512 impl<'tcx
> LowerInto
<'tcx
, ty
::Const
<'tcx
>> for &chalk_ir
::Const
<RustInterner
<'tcx
>> {
513 fn lower_into(self, interner
: &RustInterner
<'tcx
>) -> ty
::Const
<'tcx
> {
514 let data
= self.data(interner
);
515 let ty
= data
.ty
.lower_into(interner
);
516 let val
= match data
.value
{
517 chalk_ir
::ConstValue
::BoundVar(var
) => ty
::ConstKind
::Bound(
518 ty
::DebruijnIndex
::from_u32(var
.debruijn
.depth()),
519 ty
::BoundVar
::from_u32(var
.index
as u32),
521 chalk_ir
::ConstValue
::InferenceVar(_var
) => unimplemented
!(),
522 chalk_ir
::ConstValue
::Placeholder(_p
) => unimplemented
!(),
523 chalk_ir
::ConstValue
::Concrete(c
) => ty
::ConstKind
::Value(c
.interned
),
525 ty
::Const { ty, val }
529 impl<'tcx
> LowerInto
<'tcx
, chalk_ir
::GenericArg
<RustInterner
<'tcx
>>> for GenericArg
<'tcx
> {
530 fn lower_into(self, interner
: &RustInterner
<'tcx
>) -> chalk_ir
::GenericArg
<RustInterner
<'tcx
>> {
531 match self.unpack() {
532 ty
::subst
::GenericArgKind
::Type(ty
) => {
533 chalk_ir
::GenericArgData
::Ty(ty
.lower_into(interner
))
535 ty
::subst
::GenericArgKind
::Lifetime(lifetime
) => {
536 chalk_ir
::GenericArgData
::Lifetime(lifetime
.lower_into(interner
))
538 ty
::subst
::GenericArgKind
::Const(c
) => {
539 chalk_ir
::GenericArgData
::Const(c
.lower_into(interner
))
546 impl<'tcx
> LowerInto
<'tcx
, ty
::subst
::GenericArg
<'tcx
>>
547 for &chalk_ir
::GenericArg
<RustInterner
<'tcx
>>
549 fn lower_into(self, interner
: &RustInterner
<'tcx
>) -> ty
::subst
::GenericArg
<'tcx
> {
550 match self.data(interner
) {
551 chalk_ir
::GenericArgData
::Ty(ty
) => {
552 let t
: Ty
<'tcx
> = ty
.lower_into(interner
);
555 chalk_ir
::GenericArgData
::Lifetime(lifetime
) => {
556 let r
: Region
<'tcx
> = lifetime
.lower_into(interner
);
559 chalk_ir
::GenericArgData
::Const(c
) => {
560 let c
: ty
::Const
<'tcx
> = c
.lower_into(interner
);
561 interner
.tcx
.mk_const(c
).into()
567 // We lower into an Option here since there are some predicates which Chalk
568 // doesn't have a representation for yet (as a `WhereClause`), but are so common
569 // that we just are accepting the unsoundness for now. The `Option` will
570 // eventually be removed.
571 impl<'tcx
> LowerInto
<'tcx
, Option
<chalk_ir
::QuantifiedWhereClause
<RustInterner
<'tcx
>>>>
572 for ty
::Predicate
<'tcx
>
576 interner
: &RustInterner
<'tcx
>,
577 ) -> Option
<chalk_ir
::QuantifiedWhereClause
<RustInterner
<'tcx
>>> {
578 let (predicate
, binders
, _named_regions
) = collect_bound_vars(
581 &self.bound_atom_with_opt_escaping(interner
.tcx
),
583 let value
= match predicate
{
584 ty
::PredicateAtom
::Trait(predicate
, _
) => {
585 Some(chalk_ir
::WhereClause
::Implemented(predicate
.trait_ref
.lower_into(interner
)))
587 ty
::PredicateAtom
::RegionOutlives(predicate
) => {
588 Some(chalk_ir
::WhereClause
::LifetimeOutlives(chalk_ir
::LifetimeOutlives
{
589 a
: predicate
.0.lower_into(interner
),
590 b
: predicate
.1.lower_into(interner
),
593 ty
::PredicateAtom
::TypeOutlives(predicate
) => {
594 Some(chalk_ir
::WhereClause
::TypeOutlives(chalk_ir
::TypeOutlives
{
595 ty
: predicate
.0.lower_into(interner
),
596 lifetime
: predicate
.1.lower_into(interner
),
599 ty
::PredicateAtom
::Projection(predicate
) => {
600 Some(chalk_ir
::WhereClause
::AliasEq(predicate
.lower_into(interner
)))
602 ty
::PredicateAtom
::WellFormed(_ty
) => None
,
604 ty
::PredicateAtom
::ObjectSafe(..)
605 | ty
::PredicateAtom
::ClosureKind(..)
606 | ty
::PredicateAtom
::Subtype(..)
607 | ty
::PredicateAtom
::ConstEvaluatable(..)
608 | ty
::PredicateAtom
::ConstEquate(..)
609 | ty
::PredicateAtom
::TypeWellFormedFromEnv(..) => {
610 bug
!("unexpected predicate {}", &self)
613 value
.map(|value
| chalk_ir
::Binders
::new(binders
, value
))
617 impl<'tcx
> LowerInto
<'tcx
, chalk_ir
::Binders
<chalk_ir
::QuantifiedWhereClauses
<RustInterner
<'tcx
>>>>
618 for Binder
<&'tcx ty
::List
<ty
::ExistentialPredicate
<'tcx
>>>
622 interner
: &RustInterner
<'tcx
>,
623 ) -> chalk_ir
::Binders
<chalk_ir
::QuantifiedWhereClauses
<RustInterner
<'tcx
>>> {
624 // `Self` has one binder:
625 // Binder<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>>
626 // The return type has two:
627 // Binders<&[Binders<WhereClause<I>>]>
628 // This means that any variables that are escaping `self` need to be
629 // shifted in by one so that they are still escaping.
630 let shifted_predicates
= ty
::fold
::shift_vars(interner
.tcx
, &self, 1);
632 let (predicates
, binders
, _named_regions
) =
633 collect_bound_vars(interner
, interner
.tcx
, &shifted_predicates
);
634 let self_ty
= interner
.tcx
.mk_ty(ty
::Bound(
635 // This is going to be wrapped in a binder
636 ty
::DebruijnIndex
::from_usize(1),
637 ty
::BoundTy { var: ty::BoundVar::from_usize(0), kind: ty::BoundTyKind::Anon }
,
639 let where_clauses
= predicates
.into_iter().map(|predicate
| match predicate
{
640 ty
::ExistentialPredicate
::Trait(ty
::ExistentialTraitRef { def_id, substs }
) => {
641 chalk_ir
::Binders
::new(
643 chalk_ir
::WhereClause
::Implemented(chalk_ir
::TraitRef
{
644 trait_id
: chalk_ir
::TraitId(def_id
),
645 substitution
: interner
647 .mk_substs_trait(self_ty
, substs
)
648 .lower_into(interner
),
652 ty
::ExistentialPredicate
::Projection(predicate
) => chalk_ir
::Binders
::new(
654 chalk_ir
::WhereClause
::AliasEq(chalk_ir
::AliasEq
{
655 alias
: chalk_ir
::AliasTy
::Projection(chalk_ir
::ProjectionTy
{
656 associated_ty_id
: chalk_ir
::AssocTypeId(predicate
.item_def_id
),
657 substitution
: interner
659 .mk_substs_trait(self_ty
, predicate
.substs
)
660 .lower_into(interner
),
662 ty
: predicate
.ty
.lower_into(interner
),
665 ty
::ExistentialPredicate
::AutoTrait(def_id
) => chalk_ir
::Binders
::new(
667 chalk_ir
::WhereClause
::Implemented(chalk_ir
::TraitRef
{
668 trait_id
: chalk_ir
::TraitId(def_id
),
669 substitution
: interner
.tcx
.mk_substs_trait(self_ty
, &[]).lower_into(interner
),
674 // Binder for the bound variable representing the concrete underlying type.
675 let existential_binder
= chalk_ir
::VariableKinds
::from1(
677 chalk_ir
::VariableKind
::Ty(chalk_ir
::TyVariableKind
::General
),
679 let value
= chalk_ir
::QuantifiedWhereClauses
::from_iter(interner
, where_clauses
);
680 chalk_ir
::Binders
::new(existential_binder
, value
)
684 impl<'tcx
> LowerInto
<'tcx
, chalk_ir
::FnSig
<RustInterner
<'tcx
>>> for ty
::Binder
<ty
::FnSig
<'tcx
>> {
685 fn lower_into(self, _interner
: &RustInterner
<'_
>) -> FnSig
<RustInterner
<'tcx
>> {
688 safety
: match self.unsafety() {
689 Unsafety
::Normal
=> chalk_ir
::Safety
::Safe
,
690 Unsafety
::Unsafe
=> chalk_ir
::Safety
::Unsafe
,
692 variadic
: self.c_variadic(),
697 // We lower into an Option here since there are some predicates which Chalk
698 // doesn't have a representation for yet (as an `InlineBound`). The `Option` will
699 // eventually be removed.
700 impl<'tcx
> LowerInto
<'tcx
, Option
<chalk_solve
::rust_ir
::QuantifiedInlineBound
<RustInterner
<'tcx
>>>>
701 for ty
::Predicate
<'tcx
>
705 interner
: &RustInterner
<'tcx
>,
706 ) -> Option
<chalk_solve
::rust_ir
::QuantifiedInlineBound
<RustInterner
<'tcx
>>> {
707 let (predicate
, binders
, _named_regions
) = collect_bound_vars(
710 &self.bound_atom_with_opt_escaping(interner
.tcx
),
713 ty
::PredicateAtom
::Trait(predicate
, _
) => Some(chalk_ir
::Binders
::new(
715 chalk_solve
::rust_ir
::InlineBound
::TraitBound(
716 predicate
.trait_ref
.lower_into(interner
),
719 ty
::PredicateAtom
::Projection(predicate
) => Some(chalk_ir
::Binders
::new(
721 chalk_solve
::rust_ir
::InlineBound
::AliasEqBound(predicate
.lower_into(interner
)),
723 ty
::PredicateAtom
::TypeOutlives(_predicate
) => None
,
724 ty
::PredicateAtom
::WellFormed(_ty
) => None
,
726 ty
::PredicateAtom
::RegionOutlives(..)
727 | ty
::PredicateAtom
::ObjectSafe(..)
728 | ty
::PredicateAtom
::ClosureKind(..)
729 | ty
::PredicateAtom
::Subtype(..)
730 | ty
::PredicateAtom
::ConstEvaluatable(..)
731 | ty
::PredicateAtom
::ConstEquate(..)
732 | ty
::PredicateAtom
::TypeWellFormedFromEnv(..) => {
733 bug
!("unexpected predicate {}", &self)
739 impl<'tcx
> LowerInto
<'tcx
, chalk_solve
::rust_ir
::TraitBound
<RustInterner
<'tcx
>>>
740 for ty
::TraitRef
<'tcx
>
744 interner
: &RustInterner
<'tcx
>,
745 ) -> chalk_solve
::rust_ir
::TraitBound
<RustInterner
<'tcx
>> {
746 chalk_solve
::rust_ir
::TraitBound
{
747 trait_id
: chalk_ir
::TraitId(self.def_id
),
748 args_no_self
: self.substs
[1..].iter().map(|arg
| arg
.lower_into(interner
)).collect(),
753 impl<'tcx
> LowerInto
<'tcx
, chalk_ir
::Mutability
> for ast
::Mutability
{
754 fn lower_into(self, _interner
: &RustInterner
<'tcx
>) -> chalk_ir
::Mutability
{
756 rustc_ast
::Mutability
::Mut
=> chalk_ir
::Mutability
::Mut
,
757 rustc_ast
::Mutability
::Not
=> chalk_ir
::Mutability
::Not
,
762 impl<'tcx
> LowerInto
<'tcx
, ast
::Mutability
> for chalk_ir
::Mutability
{
763 fn lower_into(self, _interner
: &RustInterner
<'tcx
>) -> ast
::Mutability
{
765 chalk_ir
::Mutability
::Mut
=> ast
::Mutability
::Mut
,
766 chalk_ir
::Mutability
::Not
=> ast
::Mutability
::Not
,
771 impl<'tcx
> LowerInto
<'tcx
, chalk_solve
::rust_ir
::Polarity
> for ty
::ImplPolarity
{
772 fn lower_into(self, _interner
: &RustInterner
<'tcx
>) -> chalk_solve
::rust_ir
::Polarity
{
774 ty
::ImplPolarity
::Positive
=> chalk_solve
::rust_ir
::Polarity
::Positive
,
775 ty
::ImplPolarity
::Negative
=> chalk_solve
::rust_ir
::Polarity
::Negative
,
776 // FIXME(chalk) reservation impls
777 ty
::ImplPolarity
::Reservation
=> chalk_solve
::rust_ir
::Polarity
::Negative
,
782 impl<'tcx
> LowerInto
<'tcx
, chalk_solve
::rust_ir
::AliasEqBound
<RustInterner
<'tcx
>>>
783 for ty
::ProjectionPredicate
<'tcx
>
787 interner
: &RustInterner
<'tcx
>,
788 ) -> chalk_solve
::rust_ir
::AliasEqBound
<RustInterner
<'tcx
>> {
789 let trait_ref
= self.projection_ty
.trait_ref(interner
.tcx
);
790 chalk_solve
::rust_ir
::AliasEqBound
{
791 trait_bound
: trait_ref
.lower_into(interner
),
792 associated_ty_id
: chalk_ir
::AssocTypeId(self.projection_ty
.item_def_id
),
793 parameters
: self.projection_ty
.substs
[trait_ref
.substs
.len()..]
795 .map(|arg
| arg
.lower_into(interner
))
797 value
: self.ty
.lower_into(interner
),
802 /// To collect bound vars, we have to do two passes. In the first pass, we
803 /// collect all `BoundRegion`s and `ty::Bound`s. In the second pass, we then
804 /// replace `BrNamed` into `BrAnon`. The two separate passes are important,
805 /// since we can only replace `BrNamed` with `BrAnon`s with indices *after* all
806 /// "real" `BrAnon`s.
808 /// It's important to note that because of prior substitution, we may have
809 /// late-bound regions, even outside of fn contexts, since this is the best way
810 /// to prep types for chalk lowering.
811 crate fn collect_bound_vars
<'a
, 'tcx
, T
: TypeFoldable
<'tcx
>>(
812 interner
: &RustInterner
<'tcx
>,
815 ) -> (T
, chalk_ir
::VariableKinds
<RustInterner
<'tcx
>>, BTreeMap
<DefId
, u32>) {
816 let mut bound_vars_collector
= BoundVarsCollector
::new();
817 ty
.as_ref().skip_binder().visit_with(&mut bound_vars_collector
);
818 let mut parameters
= bound_vars_collector
.parameters
;
819 let named_parameters
: BTreeMap
<DefId
, u32> = bound_vars_collector
823 .map(|(i
, def_id
)| (def_id
, (i
+ parameters
.len()) as u32))
826 let mut bound_var_substitutor
= NamedBoundVarSubstitutor
::new(tcx
, &named_parameters
);
827 let new_ty
= ty
.as_ref().skip_binder().fold_with(&mut bound_var_substitutor
);
829 for var
in named_parameters
.values() {
830 parameters
.insert(*var
, chalk_ir
::VariableKind
::Lifetime
);
833 (0..parameters
.len()).for_each(|i
| {
836 .or_else(|| bug
!("Skipped bound var index: ty={:?}, parameters={:?}", ty
, parameters
));
840 chalk_ir
::VariableKinds
::from_iter(interner
, parameters
.into_iter().map(|(_
, v
)| v
));
842 (new_ty
, binders
, named_parameters
)
845 crate struct BoundVarsCollector
<'tcx
> {
846 binder_index
: ty
::DebruijnIndex
,
847 crate parameters
: BTreeMap
<u32, chalk_ir
::VariableKind
<RustInterner
<'tcx
>>>,
848 crate named_parameters
: Vec
<DefId
>,
851 impl<'tcx
> BoundVarsCollector
<'tcx
> {
852 crate fn new() -> Self {
854 binder_index
: ty
::INNERMOST
,
855 parameters
: BTreeMap
::new(),
856 named_parameters
: vec
![],
861 impl<'tcx
> TypeVisitor
<'tcx
> for BoundVarsCollector
<'tcx
> {
862 fn visit_binder
<T
: TypeFoldable
<'tcx
>>(&mut self, t
: &Binder
<T
>) -> ControlFlow
<()> {
863 self.binder_index
.shift_in(1);
864 let result
= t
.super_visit_with(self);
865 self.binder_index
.shift_out(1);
869 fn visit_ty(&mut self, t
: Ty
<'tcx
>) -> ControlFlow
<()> {
871 ty
::Bound(debruijn
, bound_ty
) if debruijn
== self.binder_index
=> {
872 match self.parameters
.entry(bound_ty
.var
.as_u32()) {
873 Entry
::Vacant(entry
) => {
874 entry
.insert(chalk_ir
::VariableKind
::Ty(chalk_ir
::TyVariableKind
::General
));
876 Entry
::Occupied(entry
) => match entry
.get() {
877 chalk_ir
::VariableKind
::Ty(_
) => {}
886 t
.super_visit_with(self)
889 fn visit_region(&mut self, r
: Region
<'tcx
>) -> ControlFlow
<()> {
891 ty
::ReLateBound(index
, br
) if *index
== self.binder_index
=> match br
{
892 ty
::BoundRegion
::BrNamed(def_id
, _name
) => {
893 if self.named_parameters
.iter().find(|d
| *d
== def_id
).is_none() {
894 self.named_parameters
.push(*def_id
);
898 ty
::BoundRegion
::BrAnon(var
) => match self.parameters
.entry(*var
) {
899 Entry
::Vacant(entry
) => {
900 entry
.insert(chalk_ir
::VariableKind
::Lifetime
);
902 Entry
::Occupied(entry
) => match entry
.get() {
903 chalk_ir
::VariableKind
::Lifetime
=> {}
908 ty
::BrEnv
=> unimplemented
!(),
911 ty
::ReEarlyBound(_re
) => {
912 // FIXME(chalk): jackh726 - I think we should always have already
913 // substituted away `ReEarlyBound`s for `ReLateBound`s, but need to confirm.
920 r
.super_visit_with(self)
924 /// This is used to replace `BoundRegion::BrNamed` with `BoundRegion::BrAnon`.
925 /// Note: we assume that we will always have room for more bound vars. (i.e. we
926 /// won't ever hit the `u32` limit in `BrAnon`s).
927 struct NamedBoundVarSubstitutor
<'a
, 'tcx
> {
929 binder_index
: ty
::DebruijnIndex
,
930 named_parameters
: &'a BTreeMap
<DefId
, u32>,
933 impl<'a
, 'tcx
> NamedBoundVarSubstitutor
<'a
, 'tcx
> {
934 fn new(tcx
: TyCtxt
<'tcx
>, named_parameters
: &'a BTreeMap
<DefId
, u32>) -> Self {
935 NamedBoundVarSubstitutor { tcx, binder_index: ty::INNERMOST, named_parameters }
939 impl<'a
, 'tcx
> TypeFolder
<'tcx
> for NamedBoundVarSubstitutor
<'a
, 'tcx
> {
940 fn tcx
<'b
>(&'b
self) -> TyCtxt
<'tcx
> {
944 fn fold_binder
<T
: TypeFoldable
<'tcx
>>(&mut self, t
: &Binder
<T
>) -> Binder
<T
> {
945 self.binder_index
.shift_in(1);
946 let result
= t
.super_fold_with(self);
947 self.binder_index
.shift_out(1);
951 fn fold_region(&mut self, r
: Region
<'tcx
>) -> Region
<'tcx
> {
953 ty
::ReLateBound(index
, br
) if *index
== self.binder_index
=> match br
{
954 ty
::BoundRegion
::BrNamed(def_id
, _name
) => {
955 match self.named_parameters
.get(def_id
) {
957 return self.tcx
.mk_region(RegionKind
::ReLateBound(
959 BoundRegion
::BrAnon(*idx
),
962 None
=> panic
!("Missing `BrNamed`."),
965 ty
::BrEnv
=> unimplemented
!(),
966 ty
::BoundRegion
::BrAnon(_
) => {}
971 r
.super_fold_with(self)
975 /// Used to substitute `Param`s with placeholders. We do this since Chalk
976 /// have a notion of `Param`s.
977 crate struct ParamsSubstitutor
<'tcx
> {
979 binder_index
: ty
::DebruijnIndex
,
980 list
: Vec
<rustc_middle
::ty
::ParamTy
>,
981 next_ty_placeholder
: usize,
982 crate params
: rustc_data_structures
::fx
::FxHashMap
<usize, rustc_middle
::ty
::ParamTy
>,
983 crate named_regions
: BTreeMap
<DefId
, u32>,
986 impl<'tcx
> ParamsSubstitutor
<'tcx
> {
987 crate fn new(tcx
: TyCtxt
<'tcx
>, next_ty_placeholder
: usize) -> Self {
990 binder_index
: ty
::INNERMOST
,
993 params
: rustc_data_structures
::fx
::FxHashMap
::default(),
994 named_regions
: BTreeMap
::default(),
999 impl<'tcx
> TypeFolder
<'tcx
> for ParamsSubstitutor
<'tcx
> {
1000 fn tcx
<'b
>(&'b
self) -> TyCtxt
<'tcx
> {
1004 fn fold_binder
<T
: TypeFoldable
<'tcx
>>(&mut self, t
: &Binder
<T
>) -> Binder
<T
> {
1005 self.binder_index
.shift_in(1);
1006 let result
= t
.super_fold_with(self);
1007 self.binder_index
.shift_out(1);
1011 fn fold_ty(&mut self, t
: Ty
<'tcx
>) -> Ty
<'tcx
> {
1013 // FIXME(chalk): currently we convert params to placeholders starting at
1014 // index `0`. To support placeholders, we'll actually need to do a
1015 // first pass to collect placeholders. Then we can insert params after.
1016 ty
::Placeholder(_
) => unimplemented
!(),
1017 ty
::Param(param
) => match self.list
.iter().position(|r
| r
== ¶m
) {
1018 Some(idx
) => self.tcx
.mk_ty(ty
::Placeholder(ty
::PlaceholderType
{
1019 universe
: ty
::UniverseIndex
::from_usize(0),
1020 name
: ty
::BoundVar
::from_usize(idx
),
1023 self.list
.push(param
);
1024 let idx
= self.list
.len() - 1 + self.next_ty_placeholder
;
1025 self.params
.insert(idx
, param
);
1026 self.tcx
.mk_ty(ty
::Placeholder(ty
::PlaceholderType
{
1027 universe
: ty
::UniverseIndex
::from_usize(0),
1028 name
: ty
::BoundVar
::from_usize(idx
),
1033 _
=> t
.super_fold_with(self),
1037 fn fold_region(&mut self, r
: Region
<'tcx
>) -> Region
<'tcx
> {
1039 // FIXME(chalk) - jackh726 - this currently isn't hit in any tests.
1040 // This covers any region variables in a goal, right?
1041 ty
::ReEarlyBound(_re
) => match self.named_regions
.get(&_re
.def_id
) {
1042 Some(idx
) => self.tcx
.mk_region(RegionKind
::ReLateBound(
1044 BoundRegion
::BrAnon(*idx
),
1047 let idx
= self.named_regions
.len() as u32;
1048 self.named_regions
.insert(_re
.def_id
, idx
);
1049 self.tcx
.mk_region(RegionKind
::ReLateBound(
1051 BoundRegion
::BrAnon(idx
),
1056 _
=> r
.super_fold_with(self),
1061 /// Used to collect `Placeholder`s.
1062 crate struct PlaceholdersCollector
{
1063 universe_index
: ty
::UniverseIndex
,
1064 crate next_ty_placeholder
: usize,
1065 crate next_anon_region_placeholder
: u32,
1068 impl PlaceholdersCollector
{
1069 crate fn new() -> Self {
1070 PlaceholdersCollector
{
1071 universe_index
: ty
::UniverseIndex
::ROOT
,
1072 next_ty_placeholder
: 0,
1073 next_anon_region_placeholder
: 0,
1078 impl<'tcx
> TypeVisitor
<'tcx
> for PlaceholdersCollector
{
1079 fn visit_ty(&mut self, t
: Ty
<'tcx
>) -> ControlFlow
<()> {
1081 ty
::Placeholder(p
) if p
.universe
== self.universe_index
=> {
1082 self.next_ty_placeholder
= self.next_ty_placeholder
.max(p
.name
.as_usize() + 1);
1088 t
.super_visit_with(self)
1091 fn visit_region(&mut self, r
: Region
<'tcx
>) -> ControlFlow
<()> {
1093 ty
::RePlaceholder(p
) if p
.universe
== self.universe_index
=> {
1094 if let ty
::BoundRegion
::BrAnon(anon
) = p
.name
{
1095 self.next_anon_region_placeholder
= self.next_anon_region_placeholder
.max(anon
);
1102 r
.super_visit_with(self)
1106 /// Used to substitute specific `Regions`s with placeholders.
1107 crate struct RegionsSubstitutor
<'tcx
> {
1109 reempty_placeholder
: ty
::Region
<'tcx
>,
1112 impl<'tcx
> RegionsSubstitutor
<'tcx
> {
1113 crate fn new(tcx
: TyCtxt
<'tcx
>, reempty_placeholder
: ty
::Region
<'tcx
>) -> Self {
1114 RegionsSubstitutor { tcx, reempty_placeholder }
1118 impl<'tcx
> TypeFolder
<'tcx
> for RegionsSubstitutor
<'tcx
> {
1119 fn tcx
<'b
>(&'b
self) -> TyCtxt
<'tcx
> {
1123 fn fold_region(&mut self, r
: Region
<'tcx
>) -> Region
<'tcx
> {
1125 ty
::ReEmpty(ui
) => {
1126 assert_eq
!(ui
.as_usize(), 0);
1127 self.reempty_placeholder
1130 _
=> r
.super_fold_with(self),