rustc_type_ir/
binder.rs

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

rustc_type_ir/
binder.rs
