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

rustc_type_ir/
binder.rs
