rustc_type_ir/
binder.rs

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

rustc_type_ir/
binder.rs
