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

rustc_type_ir/
binder.rs
