rustc_type_ir/
binder.rs

1use std::fmt::Debug;
2use std::hash::Hash;
3use std::marker::PhantomData;
4use std::ops::{ControlFlow, Deref};
5
6use derive_where::derive_where;
7#[cfg(feature = "nightly")]
8use rustc_macros::{Decodable_NoContext, Encodable_NoContext, HashStable_NoContext};
9use tracing::instrument;
10
11use crate::data_structures::SsoHashSet;
12use crate::fold::{FallibleTypeFolder, TypeFoldable, TypeFolder, TypeSuperFoldable};
13use crate::inherent::*;
14use crate::lift::Lift;
15use crate::visit::{Flags, TypeSuperVisitable, TypeVisitable, TypeVisitableExt, TypeVisitor};
16use crate::{self as ty, Interner};
17
18/// Binder is a binder for higher-ranked lifetimes or types. It is part of the
19/// compiler's representation for things like `for<'a> Fn(&'a isize)`
20/// (which would be represented by the type `PolyTraitRef ==
21/// Binder<I, TraitRef>`). Note that when we instantiate,
22/// erase, or otherwise "discharge" these bound vars, we change the
23/// type from `Binder<I, T>` to just `T` (see
24/// e.g., `liberate_late_bound_regions`).
25///
26/// `Decodable` and `Encodable` are implemented for `Binder<T>` using the `impl_binder_encode_decode!` macro.
27#[derive_where(Clone; I: Interner, T: Clone)]
28#[derive_where(Copy; I: Interner, T: Copy)]
29#[derive_where(Hash; I: Interner, T: Hash)]
30#[derive_where(PartialEq; I: Interner, T: PartialEq)]
31#[derive_where(Eq; I: Interner, T: Eq)]
32#[derive_where(Debug; I: Interner, T: Debug)]
33#[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
34pub struct Binder<I: Interner, T> {
35    value: T,
36    bound_vars: I::BoundVarKinds,
37}
38
39// FIXME: We manually derive `Lift` because the `derive(Lift_Generic)` doesn't
40// understand how to turn `T` to `T::Lifted` in the output `type Lifted`.
41impl<I: Interner, U: Interner, T> Lift<U> for Binder<I, T>
42where
43    T: Lift<U>,
44    I::BoundVarKinds: Lift<U, Lifted = U::BoundVarKinds>,
45{
46    type Lifted = Binder<U, T::Lifted>;
47
48    fn lift_to_interner(self, cx: U) -> Option<Self::Lifted> {
49        Some(Binder {
50            value: self.value.lift_to_interner(cx)?,
51            bound_vars: self.bound_vars.lift_to_interner(cx)?,
52        })
53    }
54}
55
56#[cfg(feature = "nightly")]
57macro_rules! impl_binder_encode_decode {
58    ($($t:ty),+ $(,)?) => {
59        $(
60            impl<I: Interner, E: rustc_serialize::Encoder> rustc_serialize::Encodable<E> for ty::Binder<I, $t>
61            where
62                $t: rustc_serialize::Encodable<E>,
63                I::BoundVarKinds: rustc_serialize::Encodable<E>,
64            {
65                fn encode(&self, e: &mut E) {
66                    self.bound_vars().encode(e);
67                    self.as_ref().skip_binder().encode(e);
68                }
69            }
70            impl<I: Interner, D: rustc_serialize::Decoder> rustc_serialize::Decodable<D> for ty::Binder<I, $t>
71            where
72                $t: TypeVisitable<I> + rustc_serialize::Decodable<D>,
73                I::BoundVarKinds: rustc_serialize::Decodable<D>,
74            {
75                fn decode(decoder: &mut D) -> Self {
76                    let bound_vars = rustc_serialize::Decodable::decode(decoder);
77                    ty::Binder::bind_with_vars(rustc_serialize::Decodable::decode(decoder), bound_vars)
78                }
79            }
80        )*
81    }
82}
83
84#[cfg(feature = "nightly")]
85impl_binder_encode_decode! {
86    ty::FnSig<I>,
87    ty::FnSigTys<I>,
88    ty::TraitPredicate<I>,
89    ty::ExistentialPredicate<I>,
90    ty::TraitRef<I>,
91    ty::ExistentialTraitRef<I>,
92    ty::HostEffectPredicate<I>,
93}
94
95impl<I: Interner, T> Binder<I, T>
96where
97    T: TypeVisitable<I>,
98{
99    /// Wraps `value` in a binder, asserting that `value` does not
100    /// contain any bound vars that would be bound by the
101    /// binder. This is commonly used to 'inject' a value T into a
102    /// different binding level.
103    #[track_caller]
104    pub fn dummy(value: T) -> Binder<I, T> {
105        assert!(
106            !value.has_escaping_bound_vars(),
107            "`{value:?}` has escaping bound vars, so it cannot be wrapped in a dummy binder."
108        );
109        Binder { value, bound_vars: Default::default() }
110    }
111
112    pub fn bind_with_vars(value: T, bound_vars: I::BoundVarKinds) -> Binder<I, T> {
113        if cfg!(debug_assertions) {
114            let mut validator = ValidateBoundVars::new(bound_vars);
115            let _ = value.visit_with(&mut validator);
116        }
117        Binder { value, bound_vars }
118    }
119}
120
121impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Binder<I, T> {
122    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
123        folder.try_fold_binder(self)
124    }
125}
126
127impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Binder<I, T> {
128    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
129        visitor.visit_binder(self)
130    }
131}
132
133impl<I: Interner, T: TypeFoldable<I>> TypeSuperFoldable<I> for Binder<I, T> {
134    fn try_super_fold_with<F: FallibleTypeFolder<I>>(
135        self,
136        folder: &mut F,
137    ) -> Result<Self, F::Error> {
138        self.try_map_bound(|ty| ty.try_fold_with(folder))
139    }
140}
141
142impl<I: Interner, T: TypeVisitable<I>> TypeSuperVisitable<I> for Binder<I, T> {
143    fn super_visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
144        self.as_ref().skip_binder().visit_with(visitor)
145    }
146}
147
148impl<I: Interner, T> Binder<I, T> {
149    /// Skips the binder and returns the "bound" value. This is a
150    /// risky thing to do because it's easy to get confused about
151    /// De Bruijn indices and the like. It is usually better to
152    /// discharge the binder using `no_bound_vars` or
153    /// `instantiate_bound_regions` or something like
154    /// that. `skip_binder` is only valid when you are either
155    /// extracting data that has nothing to do with bound vars, you
156    /// are doing some sort of test that does not involve bound
157    /// regions, or you are being very careful about your depth
158    /// accounting.
159    ///
160    /// Some examples where `skip_binder` is reasonable:
161    ///
162    /// - extracting the `DefId` from a PolyTraitRef;
163    /// - comparing the self type of a PolyTraitRef to see if it is equal to
164    ///   a type parameter `X`, since the type `X` does not reference any regions
165    pub fn skip_binder(self) -> T {
166        self.value
167    }
168
169    pub fn bound_vars(&self) -> I::BoundVarKinds {
170        self.bound_vars
171    }
172
173    pub fn as_ref(&self) -> Binder<I, &T> {
174        Binder { value: &self.value, bound_vars: self.bound_vars }
175    }
176
177    pub fn as_deref(&self) -> Binder<I, &T::Target>
178    where
179        T: Deref,
180    {
181        Binder { value: &self.value, bound_vars: self.bound_vars }
182    }
183
184    pub fn map_bound_ref<F, U: TypeVisitable<I>>(&self, f: F) -> Binder<I, U>
185    where
186        F: FnOnce(&T) -> U,
187    {
188        self.as_ref().map_bound(f)
189    }
190
191    pub fn map_bound<F, U: TypeVisitable<I>>(self, f: F) -> Binder<I, U>
192    where
193        F: FnOnce(T) -> U,
194    {
195        let Binder { value, bound_vars } = self;
196        let value = f(value);
197        if cfg!(debug_assertions) {
198            let mut validator = ValidateBoundVars::new(bound_vars);
199            let _ = value.visit_with(&mut validator);
200        }
201        Binder { value, bound_vars }
202    }
203
204    pub fn try_map_bound<F, U: TypeVisitable<I>, E>(self, f: F) -> Result<Binder<I, U>, E>
205    where
206        F: FnOnce(T) -> Result<U, E>,
207    {
208        let Binder { value, bound_vars } = self;
209        let value = f(value)?;
210        if cfg!(debug_assertions) {
211            let mut validator = ValidateBoundVars::new(bound_vars);
212            let _ = value.visit_with(&mut validator);
213        }
214        Ok(Binder { value, bound_vars })
215    }
216
217    /// Wraps a `value` in a binder, using the same bound variables as the
218    /// current `Binder`. This should not be used if the new value *changes*
219    /// the bound variables. Note: the (old or new) value itself does not
220    /// necessarily need to *name* all the bound variables.
221    ///
222    /// This currently doesn't do anything different than `bind`, because we
223    /// don't actually track bound vars. However, semantically, it is different
224    /// because bound vars aren't allowed to change here, whereas they are
225    /// in `bind`. This may be (debug) asserted in the future.
226    pub fn rebind<U>(&self, value: U) -> Binder<I, U>
227    where
228        U: TypeVisitable<I>,
229    {
230        Binder::bind_with_vars(value, self.bound_vars)
231    }
232
233    /// Unwraps and returns the value within, but only if it contains
234    /// no bound vars at all. (In other words, if this binder --
235    /// and indeed any enclosing binder -- doesn't bind anything at
236    /// all.) Otherwise, returns `None`.
237    ///
238    /// (One could imagine having a method that just unwraps a single
239    /// binder, but permits late-bound vars bound by enclosing
240    /// binders, but that would require adjusting the debruijn
241    /// indices, and given the shallow binding structure we often use,
242    /// would not be that useful.)
243    pub fn no_bound_vars(self) -> Option<T>
244    where
245        T: TypeVisitable<I>,
246    {
247        // `self.value` is equivalent to `self.skip_binder()`
248        if self.value.has_escaping_bound_vars() { None } else { Some(self.skip_binder()) }
249    }
250}
251
252impl<I: Interner, T> Binder<I, Option<T>> {
253    pub fn transpose(self) -> Option<Binder<I, T>> {
254        let Binder { value, bound_vars } = self;
255        value.map(|value| Binder { value, bound_vars })
256    }
257}
258
259impl<I: Interner, T: IntoIterator> Binder<I, T> {
260    pub fn iter(self) -> impl Iterator<Item = Binder<I, T::Item>> {
261        let Binder { value, bound_vars } = self;
262        value.into_iter().map(move |value| Binder { value, bound_vars })
263    }
264}
265
266pub struct ValidateBoundVars<I: Interner> {
267    bound_vars: I::BoundVarKinds,
268    binder_index: ty::DebruijnIndex,
269    // We may encounter the same variable at different levels of binding, so
270    // this can't just be `Ty`
271    visited: SsoHashSet<(ty::DebruijnIndex, I::Ty)>,
272}
273
274impl<I: Interner> ValidateBoundVars<I> {
275    pub fn new(bound_vars: I::BoundVarKinds) -> Self {
276        ValidateBoundVars {
277            bound_vars,
278            binder_index: ty::INNERMOST,
279            visited: SsoHashSet::default(),
280        }
281    }
282}
283
284impl<I: Interner> TypeVisitor<I> for ValidateBoundVars<I> {
285    type Result = ControlFlow<()>;
286
287    fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &Binder<I, T>) -> Self::Result {
288        self.binder_index.shift_in(1);
289        let result = t.super_visit_with(self);
290        self.binder_index.shift_out(1);
291        result
292    }
293
294    fn visit_ty(&mut self, t: I::Ty) -> Self::Result {
295        if t.outer_exclusive_binder() < self.binder_index
296            || !self.visited.insert((self.binder_index, t))
297        {
298            return ControlFlow::Break(());
299        }
300        match t.kind() {
301            ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => {
302                let idx = bound_ty.var().as_usize();
303                if self.bound_vars.len() <= idx {
304                    panic!("Not enough bound vars: {:?} not found in {:?}", t, self.bound_vars);
305                }
306                bound_ty.assert_eq(self.bound_vars.get(idx).unwrap());
307            }
308            _ => {}
309        };
310
311        t.super_visit_with(self)
312    }
313
314    fn visit_region(&mut self, r: I::Region) -> Self::Result {
315        match r.kind() {
316            ty::ReBound(index, br) if index == self.binder_index => {
317                let idx = br.var().as_usize();
318                if self.bound_vars.len() <= idx {
319                    panic!("Not enough bound vars: {:?} not found in {:?}", r, self.bound_vars);
320                }
321                br.assert_eq(self.bound_vars.get(idx).unwrap());
322            }
323
324            _ => (),
325        };
326
327        ControlFlow::Continue(())
328    }
329}
330
331/// Similar to [`super::Binder`] except that it tracks early bound generics, i.e. `struct Foo<T>(T)`
332/// needs `T` instantiated immediately. This type primarily exists to avoid forgetting to call
333/// `instantiate`.
334///
335/// If you don't have anything to `instantiate`, you may be looking for
336/// [`instantiate_identity`](EarlyBinder::instantiate_identity) or [`skip_binder`](EarlyBinder::skip_binder).
337#[derive_where(Clone; I: Interner, T: Clone)]
338#[derive_where(Copy; I: Interner, T: Copy)]
339#[derive_where(PartialEq; I: Interner, T: PartialEq)]
340#[derive_where(Eq; I: Interner, T: Eq)]
341#[derive_where(Ord; I: Interner, T: Ord)]
342#[derive_where(PartialOrd; I: Interner, T: Ord)]
343#[derive_where(Hash; I: Interner, T: Hash)]
344#[derive_where(Debug; I: Interner, T: Debug)]
345#[cfg_attr(
346    feature = "nightly",
347    derive(Encodable_NoContext, Decodable_NoContext, HashStable_NoContext)
348)]
349pub struct EarlyBinder<I: Interner, T> {
350    value: T,
351    #[derive_where(skip(Debug))]
352    _tcx: PhantomData<I>,
353}
354
355/// For early binders, you should first call `instantiate` before using any visitors.
356#[cfg(feature = "nightly")]
357impl<I: Interner, T> !TypeFoldable<I> for ty::EarlyBinder<I, T> {}
358
359/// For early binders, you should first call `instantiate` before using any visitors.
360#[cfg(feature = "nightly")]
361impl<I: Interner, T> !TypeVisitable<I> for ty::EarlyBinder<I, T> {}
362
363impl<I: Interner, T> EarlyBinder<I, T> {
364    pub fn bind(value: T) -> EarlyBinder<I, T> {
365        EarlyBinder { value, _tcx: PhantomData }
366    }
367
368    pub fn as_ref(&self) -> EarlyBinder<I, &T> {
369        EarlyBinder { value: &self.value, _tcx: PhantomData }
370    }
371
372    pub fn map_bound_ref<F, U>(&self, f: F) -> EarlyBinder<I, U>
373    where
374        F: FnOnce(&T) -> U,
375    {
376        self.as_ref().map_bound(f)
377    }
378
379    pub fn map_bound<F, U>(self, f: F) -> EarlyBinder<I, U>
380    where
381        F: FnOnce(T) -> U,
382    {
383        let value = f(self.value);
384        EarlyBinder { value, _tcx: PhantomData }
385    }
386
387    pub fn try_map_bound<F, U, E>(self, f: F) -> Result<EarlyBinder<I, U>, E>
388    where
389        F: FnOnce(T) -> Result<U, E>,
390    {
391        let value = f(self.value)?;
392        Ok(EarlyBinder { value, _tcx: PhantomData })
393    }
394
395    pub fn rebind<U>(&self, value: U) -> EarlyBinder<I, U> {
396        EarlyBinder { value, _tcx: PhantomData }
397    }
398
399    /// Skips the binder and returns the "bound" value.
400    /// This can be used to extract data that does not depend on generic parameters
401    /// (e.g., getting the `DefId` of the inner value or getting the number of
402    /// arguments of an `FnSig`). Otherwise, consider using
403    /// [`instantiate_identity`](EarlyBinder::instantiate_identity).
404    ///
405    /// To skip the binder on `x: &EarlyBinder<I, T>` to obtain `&T`, leverage
406    /// [`EarlyBinder::as_ref`](EarlyBinder::as_ref): `x.as_ref().skip_binder()`.
407    ///
408    /// See also [`Binder::skip_binder`](super::Binder::skip_binder), which is
409    /// the analogous operation on [`super::Binder`].
410    pub fn skip_binder(self) -> T {
411        self.value
412    }
413}
414
415impl<I: Interner, T> EarlyBinder<I, Option<T>> {
416    pub fn transpose(self) -> Option<EarlyBinder<I, T>> {
417        self.value.map(|value| EarlyBinder { value, _tcx: PhantomData })
418    }
419}
420
421impl<I: Interner, Iter: IntoIterator> EarlyBinder<I, Iter>
422where
423    Iter::Item: TypeFoldable<I>,
424{
425    pub fn iter_instantiated<A>(self, cx: I, args: A) -> IterInstantiated<I, Iter, A>
426    where
427        A: SliceLike<Item = I::GenericArg>,
428    {
429        IterInstantiated { it: self.value.into_iter(), cx, args }
430    }
431
432    /// Similar to [`instantiate_identity`](EarlyBinder::instantiate_identity),
433    /// but on an iterator of `TypeFoldable` values.
434    pub fn iter_identity(self) -> Iter::IntoIter {
435        self.value.into_iter()
436    }
437}
438
439pub struct IterInstantiated<I: Interner, Iter: IntoIterator, A> {
440    it: Iter::IntoIter,
441    cx: I,
442    args: A,
443}
444
445impl<I: Interner, Iter: IntoIterator, A> Iterator for IterInstantiated<I, Iter, A>
446where
447    Iter::Item: TypeFoldable<I>,
448    A: SliceLike<Item = I::GenericArg>,
449{
450    type Item = Iter::Item;
451
452    fn next(&mut self) -> Option<Self::Item> {
453        Some(
454            EarlyBinder { value: self.it.next()?, _tcx: PhantomData }
455                .instantiate(self.cx, self.args),
456        )
457    }
458
459    fn size_hint(&self) -> (usize, Option<usize>) {
460        self.it.size_hint()
461    }
462}
463
464impl<I: Interner, Iter: IntoIterator, A> DoubleEndedIterator for IterInstantiated<I, Iter, A>
465where
466    Iter::IntoIter: DoubleEndedIterator,
467    Iter::Item: TypeFoldable<I>,
468    A: SliceLike<Item = I::GenericArg>,
469{
470    fn next_back(&mut self) -> Option<Self::Item> {
471        Some(
472            EarlyBinder { value: self.it.next_back()?, _tcx: PhantomData }
473                .instantiate(self.cx, self.args),
474        )
475    }
476}
477
478impl<I: Interner, Iter: IntoIterator, A> ExactSizeIterator for IterInstantiated<I, Iter, A>
479where
480    Iter::IntoIter: ExactSizeIterator,
481    Iter::Item: TypeFoldable<I>,
482    A: SliceLike<Item = I::GenericArg>,
483{
484}
485
486impl<'s, I: Interner, Iter: IntoIterator> EarlyBinder<I, Iter>
487where
488    Iter::Item: Deref,
489    <Iter::Item as Deref>::Target: Copy + TypeFoldable<I>,
490{
491    pub fn iter_instantiated_copied(
492        self,
493        cx: I,
494        args: &'s [I::GenericArg],
495    ) -> IterInstantiatedCopied<'s, I, Iter> {
496        IterInstantiatedCopied { it: self.value.into_iter(), cx, args }
497    }
498
499    /// Similar to [`instantiate_identity`](EarlyBinder::instantiate_identity),
500    /// but on an iterator of values that deref to a `TypeFoldable`.
501    pub fn iter_identity_copied(self) -> IterIdentityCopied<Iter> {
502        IterIdentityCopied { it: self.value.into_iter() }
503    }
504}
505
506pub struct IterInstantiatedCopied<'a, I: Interner, Iter: IntoIterator> {
507    it: Iter::IntoIter,
508    cx: I,
509    args: &'a [I::GenericArg],
510}
511
512impl<I: Interner, Iter: IntoIterator> Iterator for IterInstantiatedCopied<'_, I, Iter>
513where
514    Iter::Item: Deref,
515    <Iter::Item as Deref>::Target: Copy + TypeFoldable<I>,
516{
517    type Item = <Iter::Item as Deref>::Target;
518
519    fn next(&mut self) -> Option<Self::Item> {
520        self.it.next().map(|value| {
521            EarlyBinder { value: *value, _tcx: PhantomData }.instantiate(self.cx, self.args)
522        })
523    }
524
525    fn size_hint(&self) -> (usize, Option<usize>) {
526        self.it.size_hint()
527    }
528}
529
530impl<I: Interner, Iter: IntoIterator> DoubleEndedIterator for IterInstantiatedCopied<'_, I, Iter>
531where
532    Iter::IntoIter: DoubleEndedIterator,
533    Iter::Item: Deref,
534    <Iter::Item as Deref>::Target: Copy + TypeFoldable<I>,
535{
536    fn next_back(&mut self) -> Option<Self::Item> {
537        self.it.next_back().map(|value| {
538            EarlyBinder { value: *value, _tcx: PhantomData }.instantiate(self.cx, self.args)
539        })
540    }
541}
542
543impl<I: Interner, Iter: IntoIterator> ExactSizeIterator for IterInstantiatedCopied<'_, I, Iter>
544where
545    Iter::IntoIter: ExactSizeIterator,
546    Iter::Item: Deref,
547    <Iter::Item as Deref>::Target: Copy + TypeFoldable<I>,
548{
549}
550
551pub struct IterIdentityCopied<Iter: IntoIterator> {
552    it: Iter::IntoIter,
553}
554
555impl<Iter: IntoIterator> Iterator for IterIdentityCopied<Iter>
556where
557    Iter::Item: Deref,
558    <Iter::Item as Deref>::Target: Copy,
559{
560    type Item = <Iter::Item as Deref>::Target;
561
562    fn next(&mut self) -> Option<Self::Item> {
563        self.it.next().map(|i| *i)
564    }
565
566    fn size_hint(&self) -> (usize, Option<usize>) {
567        self.it.size_hint()
568    }
569}
570
571impl<Iter: IntoIterator> DoubleEndedIterator for IterIdentityCopied<Iter>
572where
573    Iter::IntoIter: DoubleEndedIterator,
574    Iter::Item: Deref,
575    <Iter::Item as Deref>::Target: Copy,
576{
577    fn next_back(&mut self) -> Option<Self::Item> {
578        self.it.next_back().map(|i| *i)
579    }
580}
581
582impl<Iter: IntoIterator> ExactSizeIterator for IterIdentityCopied<Iter>
583where
584    Iter::IntoIter: ExactSizeIterator,
585    Iter::Item: Deref,
586    <Iter::Item as Deref>::Target: Copy,
587{
588}
589pub struct EarlyBinderIter<I, T> {
590    t: T,
591    _tcx: PhantomData<I>,
592}
593
594impl<I: Interner, T: IntoIterator> EarlyBinder<I, T> {
595    pub fn transpose_iter(self) -> EarlyBinderIter<I, T::IntoIter> {
596        EarlyBinderIter { t: self.value.into_iter(), _tcx: PhantomData }
597    }
598}
599
600impl<I: Interner, T: Iterator> Iterator for EarlyBinderIter<I, T> {
601    type Item = EarlyBinder<I, T::Item>;
602
603    fn next(&mut self) -> Option<Self::Item> {
604        self.t.next().map(|value| EarlyBinder { value, _tcx: PhantomData })
605    }
606
607    fn size_hint(&self) -> (usize, Option<usize>) {
608        self.t.size_hint()
609    }
610}
611
612impl<I: Interner, T: TypeFoldable<I>> ty::EarlyBinder<I, T> {
613    pub fn instantiate<A>(self, cx: I, args: A) -> T
614    where
615        A: SliceLike<Item = I::GenericArg>,
616    {
617        let mut folder = ArgFolder { cx, args: args.as_slice(), binders_passed: 0 };
618        self.value.fold_with(&mut folder)
619    }
620
621    /// Makes the identity replacement `T0 => T0, ..., TN => TN`.
622    /// Conceptually, this converts universally bound variables into placeholders
623    /// when inside of a given item.
624    ///
625    /// For example, consider `for<T> fn foo<T>(){ .. }`:
626    /// - Outside of `foo`, `T` is bound (represented by the presence of `EarlyBinder`).
627    /// - Inside of the body of `foo`, we treat `T` as a placeholder by calling
628    /// `instantiate_identity` to discharge the `EarlyBinder`.
629    pub fn instantiate_identity(self) -> T {
630        self.value
631    }
632
633    /// Returns the inner value, but only if it contains no bound vars.
634    pub fn no_bound_vars(self) -> Option<T> {
635        if !self.value.has_param() { Some(self.value) } else { None }
636    }
637}
638
639///////////////////////////////////////////////////////////////////////////
640// The actual instantiation engine itself is a type folder.
641
642struct ArgFolder<'a, I: Interner> {
643    cx: I,
644    args: &'a [I::GenericArg],
645
646    /// Number of region binders we have passed through while doing the instantiation
647    binders_passed: u32,
648}
649
650impl<'a, I: Interner> TypeFolder<I> for ArgFolder<'a, I> {
651    #[inline]
652    fn cx(&self) -> I {
653        self.cx
654    }
655
656    fn fold_binder<T: TypeFoldable<I>>(&mut self, t: ty::Binder<I, T>) -> ty::Binder<I, T> {
657        self.binders_passed += 1;
658        let t = t.super_fold_with(self);
659        self.binders_passed -= 1;
660        t
661    }
662
663    fn fold_region(&mut self, r: I::Region) -> I::Region {
664        // Note: This routine only handles regions that are bound on
665        // type declarations and other outer declarations, not those
666        // bound in *fn types*. Region instantiation of the bound
667        // regions that appear in a function signature is done using
668        // the specialized routine `ty::replace_late_regions()`.
669        match r.kind() {
670            ty::ReEarlyParam(data) => {
671                let rk = self.args.get(data.index() as usize).map(|k| k.kind());
672                match rk {
673                    Some(ty::GenericArgKind::Lifetime(lt)) => self.shift_region_through_binders(lt),
674                    Some(other) => self.region_param_expected(data, r, other),
675                    None => self.region_param_out_of_range(data, r),
676                }
677            }
678            ty::ReBound(..)
679            | ty::ReLateParam(_)
680            | ty::ReStatic
681            | ty::RePlaceholder(_)
682            | ty::ReErased
683            | ty::ReError(_) => r,
684            ty::ReVar(_) => panic!("unexpected region: {r:?}"),
685        }
686    }
687
688    fn fold_ty(&mut self, t: I::Ty) -> I::Ty {
689        if !t.has_param() {
690            return t;
691        }
692
693        match t.kind() {
694            ty::Param(p) => self.ty_for_param(p, t),
695            _ => t.super_fold_with(self),
696        }
697    }
698
699    fn fold_const(&mut self, c: I::Const) -> I::Const {
700        if let ty::ConstKind::Param(p) = c.kind() {
701            self.const_for_param(p, c)
702        } else {
703            c.super_fold_with(self)
704        }
705    }
706}
707
708impl<'a, I: Interner> ArgFolder<'a, I> {
709    fn ty_for_param(&self, p: I::ParamTy, source_ty: I::Ty) -> I::Ty {
710        // Look up the type in the args. It really should be in there.
711        let opt_ty = self.args.get(p.index() as usize).map(|k| k.kind());
712        let ty = match opt_ty {
713            Some(ty::GenericArgKind::Type(ty)) => ty,
714            Some(kind) => self.type_param_expected(p, source_ty, kind),
715            None => self.type_param_out_of_range(p, source_ty),
716        };
717
718        self.shift_vars_through_binders(ty)
719    }
720
721    #[cold]
722    #[inline(never)]
723    fn type_param_expected(&self, p: I::ParamTy, ty: I::Ty, kind: ty::GenericArgKind<I>) -> ! {
724        panic!(
725            "expected type for `{:?}` ({:?}/{}) but found {:?} when instantiating, args={:?}",
726            p,
727            ty,
728            p.index(),
729            kind,
730            self.args,
731        )
732    }
733
734    #[cold]
735    #[inline(never)]
736    fn type_param_out_of_range(&self, p: I::ParamTy, ty: I::Ty) -> ! {
737        panic!(
738            "type parameter `{:?}` ({:?}/{}) out of range when instantiating, args={:?}",
739            p,
740            ty,
741            p.index(),
742            self.args,
743        )
744    }
745
746    fn const_for_param(&self, p: I::ParamConst, source_ct: I::Const) -> I::Const {
747        // Look up the const in the args. It really should be in there.
748        let opt_ct = self.args.get(p.index() as usize).map(|k| k.kind());
749        let ct = match opt_ct {
750            Some(ty::GenericArgKind::Const(ct)) => ct,
751            Some(kind) => self.const_param_expected(p, source_ct, kind),
752            None => self.const_param_out_of_range(p, source_ct),
753        };
754
755        self.shift_vars_through_binders(ct)
756    }
757
758    #[cold]
759    #[inline(never)]
760    fn const_param_expected(
761        &self,
762        p: I::ParamConst,
763        ct: I::Const,
764        kind: ty::GenericArgKind<I>,
765    ) -> ! {
766        panic!(
767            "expected const for `{:?}` ({:?}/{}) but found {:?} when instantiating args={:?}",
768            p,
769            ct,
770            p.index(),
771            kind,
772            self.args,
773        )
774    }
775
776    #[cold]
777    #[inline(never)]
778    fn const_param_out_of_range(&self, p: I::ParamConst, ct: I::Const) -> ! {
779        panic!(
780            "const parameter `{:?}` ({:?}/{}) out of range when instantiating args={:?}",
781            p,
782            ct,
783            p.index(),
784            self.args,
785        )
786    }
787
788    #[cold]
789    #[inline(never)]
790    fn region_param_expected(
791        &self,
792        ebr: I::EarlyParamRegion,
793        r: I::Region,
794        kind: ty::GenericArgKind<I>,
795    ) -> ! {
796        panic!(
797            "expected region for `{:?}` ({:?}/{}) but found {:?} when instantiating args={:?}",
798            ebr,
799            r,
800            ebr.index(),
801            kind,
802            self.args,
803        )
804    }
805
806    #[cold]
807    #[inline(never)]
808    fn region_param_out_of_range(&self, ebr: I::EarlyParamRegion, r: I::Region) -> ! {
809        panic!(
810            "region parameter `{:?}` ({:?}/{}) out of range when instantiating args={:?}",
811            ebr,
812            r,
813            ebr.index(),
814            self.args,
815        )
816    }
817
818    /// It is sometimes necessary to adjust the De Bruijn indices during instantiation. This occurs
819    /// when we are instantiating a type with escaping bound vars into a context where we have
820    /// passed through binders. That's quite a mouthful. Let's see an example:
821    ///
822    /// ```
823    /// type Func<A> = fn(A);
824    /// type MetaFunc = for<'a> fn(Func<&'a i32>);
825    /// ```
826    ///
827    /// The type `MetaFunc`, when fully expanded, will be
828    /// ```ignore (illustrative)
829    /// for<'a> fn(fn(&'a i32))
830    /// //      ^~ ^~ ^~~
831    /// //      |  |  |
832    /// //      |  |  DebruijnIndex of 2
833    /// //      Binders
834    /// ```
835    /// Here the `'a` lifetime is bound in the outer function, but appears as an argument of the
836    /// inner one. Therefore, that appearance will have a DebruijnIndex of 2, because we must skip
837    /// over the inner binder (remember that we count De Bruijn indices from 1). However, in the
838    /// definition of `MetaFunc`, the binder is not visible, so the type `&'a i32` will have a
839    /// De Bruijn index of 1. It's only during the instantiation that we can see we must increase the
840    /// depth by 1 to account for the binder that we passed through.
841    ///
842    /// As a second example, consider this twist:
843    ///
844    /// ```
845    /// type FuncTuple<A> = (A,fn(A));
846    /// type MetaFuncTuple = for<'a> fn(FuncTuple<&'a i32>);
847    /// ```
848    ///
849    /// Here the final type will be:
850    /// ```ignore (illustrative)
851    /// for<'a> fn((&'a i32, fn(&'a i32)))
852    /// //          ^~~         ^~~
853    /// //          |           |
854    /// //   DebruijnIndex of 1 |
855    /// //               DebruijnIndex of 2
856    /// ```
857    /// As indicated in the diagram, here the same type `&'a i32` is instantiated once, but in the
858    /// first case we do not increase the De Bruijn index and in the second case we do. The reason
859    /// is that only in the second case have we passed through a fn binder.
860    #[instrument(level = "trace", skip(self), fields(binders_passed = self.binders_passed), ret)]
861    fn shift_vars_through_binders<T: TypeFoldable<I>>(&self, val: T) -> T {
862        if self.binders_passed == 0 || !val.has_escaping_bound_vars() {
863            val
864        } else {
865            ty::shift_vars(self.cx, val, self.binders_passed)
866        }
867    }
868
869    fn shift_region_through_binders(&self, region: I::Region) -> I::Region {
870        if self.binders_passed == 0 || !region.has_escaping_bound_vars() {
871            region
872        } else {
873            ty::shift_region(self.cx, region, self.binders_passed)
874        }
875    }
876}
rustc_type_ir/binder.rs

rustc_type_ir/
binder.rs
