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

rustc_type_ir/
binder.rs
