Struct rustc_middle::ty::DebruijnIndex
source · pub struct DebruijnIndex {
pub(crate) private_use_as_methods_instead: u32,
}
Expand description
A De Bruijn index is a standard means of representing regions (and perhaps later types) in a higher-ranked setting. In particular, imagine a type like this:
for<'a> fn(for<'b> fn(&'b isize, &'a isize), &'a char)
// ^ ^ | | |
// | | | | |
// | +------------+ 0 | |
// | | |
// +----------------------------------+ 1 |
// | |
// +----------------------------------------------+ 0
In this type, there are two binders (the outer fn and the inner fn). We need to be able to determine, for any given region, which fn type it is bound by, the inner or the outer one. There are various ways you can do this, but a De Bruijn index is one of the more convenient and has some nice properties. The basic idea is to count the number of binders, inside out. Some examples should help clarify what I mean.
Let’s start with the reference type &'b isize
that is the first
argument to the inner function. This region 'b
is assigned a De
Bruijn index of 0, meaning “the innermost binder” (in this case, a
fn). The region 'a
that appears in the second argument type (&'a isize
) would then be assigned a De Bruijn index of 1, meaning “the
second-innermost binder”. (These indices are written on the arrows
in the diagram).
What is interesting is that De Bruijn index attached to a particular
variable will vary depending on where it appears. For example,
the final type &'a char
also refers to the region 'a
declared on
the outermost fn. But this time, this reference is not nested within
any other binders (i.e., it is not an argument to the inner fn, but
rather the outer one). Therefore, in this case, it is assigned a
De Bruijn index of 0, because the innermost binder in that location
is the outer fn.
Fields§
§private_use_as_methods_instead: u32
Implementations§
source§impl DebruijnIndex
impl DebruijnIndex
sourcepub const MAX_AS_U32: u32 = 4_294_967_040u32
pub const MAX_AS_U32: u32 = 4_294_967_040u32
Maximum value the index can take, as a u32
.
sourcepub const MAX: DebruijnIndex = _
pub const MAX: DebruijnIndex = _
Maximum value the index can take.
sourcepub const ZERO: DebruijnIndex = _
pub const ZERO: DebruijnIndex = _
Zero value of the index.
sourcepub const fn from_usize(value: usize) -> DebruijnIndex
pub const fn from_usize(value: usize) -> DebruijnIndex
sourcepub const fn from_u32(value: u32) -> DebruijnIndex
pub const fn from_u32(value: u32) -> DebruijnIndex
sourcepub const fn from_u16(value: u16) -> DebruijnIndex
pub const fn from_u16(value: u16) -> DebruijnIndex
sourcepub const unsafe fn from_u32_unchecked(value: u32) -> DebruijnIndex
pub const unsafe fn from_u32_unchecked(value: u32) -> DebruijnIndex
Creates a new index from a given u32
.
§Safety
The provided value must be less than or equal to the maximum value for the newtype. Providing a value outside this range is undefined due to layout restrictions.
Prefer using from_u32
.
source§impl DebruijnIndex
impl DebruijnIndex
sourcepub fn shifted_in(self, amount: u32) -> DebruijnIndex
pub fn shifted_in(self, amount: u32) -> DebruijnIndex
Returns the resulting index when this value is moved into
amount
number of new binders. So, e.g., if you had
for<’a> fn(&’a x)
and you wanted to change it to
for<’a> fn(for<’b> fn(&’a x))
you would need to shift the index for 'a
into a new binder.
sourcepub fn shift_in(&mut self, amount: u32)
pub fn shift_in(&mut self, amount: u32)
Update this index in place by shifting it “in” through
amount
number of binders.
sourcepub fn shifted_out(self, amount: u32) -> DebruijnIndex
pub fn shifted_out(self, amount: u32) -> DebruijnIndex
Returns the resulting index when this value is moved out from
amount
number of new binders.
sourcepub fn shifted_out_to_binder(self, to_binder: DebruijnIndex) -> DebruijnIndex
pub fn shifted_out_to_binder(self, to_binder: DebruijnIndex) -> DebruijnIndex
Adjusts any De Bruijn indices so as to make to_binder
the
innermost binder. That is, if we have something bound at to_binder
,
it will now be bound at INNERMOST. This is an appropriate thing to do
when moving a region out from inside binders:
for<'a> fn(for<'b> for<'c> fn(&'a u32), _)
// Binder: D3 D2 D1 ^^
Here, the region 'a
would have the De Bruijn index D3,
because it is the bound 3 binders out. However, if we wanted
to refer to that region 'a
in the second argument (the _
),
those two binders would not be in scope. In that case, we
might invoke shift_out_to_binder(D3)
. This would adjust the
De Bruijn index of 'a
to D1 (the innermost binder).
If we invoke shift_out_to_binder
and the region is in fact
bound by one of the binders we are shifting out of, that is an
error (and should fail an assertion failure).
Trait Implementations§
source§impl Add<usize> for DebruijnIndex
impl Add<usize> for DebruijnIndex
§type Output = DebruijnIndex
type Output = DebruijnIndex
+
operator.source§impl Clone for DebruijnIndex
impl Clone for DebruijnIndex
source§fn clone(&self) -> DebruijnIndex
fn clone(&self) -> DebruijnIndex
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresource§impl Debug for DebruijnIndex
impl Debug for DebruijnIndex
source§impl<D> Decodable<D> for DebruijnIndexwhere
D: Decoder,
impl<D> Decodable<D> for DebruijnIndexwhere
D: Decoder,
fn decode(d: &mut D) -> DebruijnIndex
source§impl From<u32> for DebruijnIndex
impl From<u32> for DebruijnIndex
source§fn from(value: u32) -> DebruijnIndex
fn from(value: u32) -> DebruijnIndex
source§impl From<usize> for DebruijnIndex
impl From<usize> for DebruijnIndex
source§fn from(value: usize) -> DebruijnIndex
fn from(value: usize) -> DebruijnIndex
source§impl Hash for DebruijnIndex
impl Hash for DebruijnIndex
source§impl<__CTX> HashStable<__CTX> for DebruijnIndex
impl<__CTX> HashStable<__CTX> for DebruijnIndex
fn hash_stable( &self, __hcx: &mut __CTX, __hasher: &mut StableHasher<SipHasher128>, )
source§impl Idx for DebruijnIndex
impl Idx for DebruijnIndex
source§impl Ord for DebruijnIndex
impl Ord for DebruijnIndex
source§fn cmp(&self, other: &DebruijnIndex) -> Ordering
fn cmp(&self, other: &DebruijnIndex) -> Ordering
1.21.0 · source§fn max(self, other: Self) -> Selfwhere
Self: Sized,
fn max(self, other: Self) -> Selfwhere
Self: Sized,
source§impl PartialEq for DebruijnIndex
impl PartialEq for DebruijnIndex
source§fn eq(&self, other: &DebruijnIndex) -> bool
fn eq(&self, other: &DebruijnIndex) -> bool
self
and other
values to be equal, and is used
by ==
.source§impl PartialOrd for DebruijnIndex
impl PartialOrd for DebruijnIndex
source§fn partial_cmp(&self, other: &DebruijnIndex) -> Option<Ordering>
fn partial_cmp(&self, other: &DebruijnIndex) -> Option<Ordering>
1.0.0 · source§fn le(&self, other: &Rhs) -> bool
fn le(&self, other: &Rhs) -> bool
self
and other
) and is used by the <=
operator. Read moresource§impl Step for DebruijnIndex
impl Step for DebruijnIndex
source§fn steps_between(start: &DebruijnIndex, end: &DebruijnIndex) -> Option<usize>
fn steps_between(start: &DebruijnIndex, end: &DebruijnIndex) -> Option<usize>
step_trait
)source§fn forward_checked(start: DebruijnIndex, u: usize) -> Option<DebruijnIndex>
fn forward_checked(start: DebruijnIndex, u: usize) -> Option<DebruijnIndex>
step_trait
)source§fn backward_checked(start: DebruijnIndex, u: usize) -> Option<DebruijnIndex>
fn backward_checked(start: DebruijnIndex, u: usize) -> Option<DebruijnIndex>
step_trait
)source§fn forward(start: Self, count: usize) -> Self
fn forward(start: Self, count: usize) -> Self
step_trait
)source§unsafe fn forward_unchecked(start: Self, count: usize) -> Self
unsafe fn forward_unchecked(start: Self, count: usize) -> Self
step_trait
)source§fn backward(start: Self, count: usize) -> Self
fn backward(start: Self, count: usize) -> Self
step_trait
)source§unsafe fn backward_unchecked(start: Self, count: usize) -> Self
unsafe fn backward_unchecked(start: Self, count: usize) -> Self
step_trait
)source§impl<I> TypeFoldable<I> for DebruijnIndexwhere
I: Interner,
impl<I> TypeFoldable<I> for DebruijnIndexwhere
I: Interner,
source§fn try_fold_with<F>(
self,
_: &mut F,
) -> Result<DebruijnIndex, <F as FallibleTypeFolder<I>>::Error>where
F: FallibleTypeFolder<I>,
fn try_fold_with<F>(
self,
_: &mut F,
) -> Result<DebruijnIndex, <F as FallibleTypeFolder<I>>::Error>where
F: FallibleTypeFolder<I>,
source§fn fold_with<F>(self, _: &mut F) -> DebruijnIndexwhere
F: TypeFolder<I>,
fn fold_with<F>(self, _: &mut F) -> DebruijnIndexwhere
F: TypeFolder<I>,
try_fold_with
for use with infallible
folders. Do not override this method, to ensure coherence with
try_fold_with
.source§impl<I> TypeVisitable<I> for DebruijnIndexwhere
I: Interner,
impl<I> TypeVisitable<I> for DebruijnIndexwhere
I: Interner,
source§fn visit_with<F>(&self, _: &mut F) -> <F as TypeVisitor<I>>::Resultwhere
F: TypeVisitor<I>,
fn visit_with<F>(&self, _: &mut F) -> <F as TypeVisitor<I>>::Resultwhere
F: TypeVisitor<I>,
impl Copy for DebruijnIndex
impl Eq for DebruijnIndex
impl StructuralPartialEq for DebruijnIndex
Auto Trait Implementations§
impl Freeze for DebruijnIndex
impl RefUnwindSafe for DebruijnIndex
impl Send for DebruijnIndex
impl Sync for DebruijnIndex
impl Unpin for DebruijnIndex
impl UnwindSafe for DebruijnIndex
Blanket Implementations§
source§impl<'tcx, T> ArenaAllocatable<'tcx, IsCopy> for Twhere
T: Copy,
impl<'tcx, T> ArenaAllocatable<'tcx, IsCopy> for Twhere
T: Copy,
fn allocate_on<'a>(self, arena: &'a Arena<'tcx>) -> &'a mut T
fn allocate_from_iter<'a>( arena: &'a Arena<'tcx>, iter: impl IntoIterator<Item = T>, ) -> &'a mut [T]
source§impl<'tcx, T> ArenaAllocatable<'tcx, IsCopy> for Twhere
T: Copy,
impl<'tcx, T> ArenaAllocatable<'tcx, IsCopy> for Twhere
T: Copy,
fn allocate_on<'a>(self, arena: &'a Arena<'tcx>) -> &'a mut T
fn allocate_from_iter<'a>( arena: &'a Arena<'tcx>, iter: impl IntoIterator<Item = T>, ) -> &'a mut [T]
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Copy,
impl<T> CloneToUninit for Twhere
T: Copy,
source§unsafe fn clone_to_uninit(&self, dst: *mut T)
unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)source§impl<T, R> CollectAndApply<T, R> for T
impl<T, R> CollectAndApply<T, R> for T
source§impl<Q, K> Comparable<K> for Q
impl<Q, K> Comparable<K> for Q
source§impl<Tcx, T> DepNodeParams<Tcx> for T
impl<Tcx, T> DepNodeParams<Tcx> for T
default fn fingerprint_style() -> FingerprintStyle
source§default fn to_fingerprint(&self, tcx: Tcx) -> Fingerprint
default fn to_fingerprint(&self, tcx: Tcx) -> Fingerprint
default fn to_debug_str(&self, _: Tcx) -> String
source§default fn recover(_: Tcx, _: &DepNode) -> Option<T>
default fn recover(_: Tcx, _: &DepNode) -> Option<T>
DepNode
,
something which is needed when forcing DepNode
s during red-green
evaluation. The query system will only call this method if
fingerprint_style()
is not FingerprintStyle::Opaque
.
It is always valid to return None
here, in which case incremental
compilation will treat the query as having changed instead of forcing it.source§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
source§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
source§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
source§fn equivalent(&self, key: &K) -> bool
fn equivalent(&self, key: &K) -> bool
key
and return true
if they are equal.source§impl<T> Filterable for T
impl<T> Filterable for T
source§fn filterable(
self,
filter_name: &'static str,
) -> RequestFilterDataProvider<T, fn(_: DataRequest<'_>) -> bool>
fn filterable( self, filter_name: &'static str, ) -> RequestFilterDataProvider<T, fn(_: DataRequest<'_>) -> bool>
source§impl<T> Instrument for T
impl<T> Instrument for T
source§fn instrument(self, span: Span) -> Instrumented<Self>
fn instrument(self, span: Span) -> Instrumented<Self>
source§fn in_current_span(self) -> Instrumented<Self>
fn in_current_span(self) -> Instrumented<Self>
source§impl<T> IntoEither for T
impl<T> IntoEither for T
source§fn into_either(self, into_left: bool) -> Either<Self, Self>
fn into_either(self, into_left: bool) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left
is true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read moresource§fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left(&self)
returns true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read moresource§impl<P> IntoQueryParam<P> for P
impl<P> IntoQueryParam<P> for P
fn into_query_param(self) -> P
source§impl<'tcx, T> IsSuggestable<'tcx> for T
impl<'tcx, T> IsSuggestable<'tcx> for T
source§impl<T> MaybeResult<T> for T
impl<T> MaybeResult<T> for T
source§impl<I, T> TypeVisitableExt<I> for Twhere
I: Interner,
T: TypeVisitable<I>,
impl<I, T> TypeVisitableExt<I> for Twhere
I: Interner,
T: TypeVisitable<I>,
fn has_type_flags(&self, flags: TypeFlags) -> bool
source§fn has_vars_bound_at_or_above(&self, binder: DebruijnIndex) -> bool
fn has_vars_bound_at_or_above(&self, binder: DebruijnIndex) -> bool
true
if self
has any late-bound regions that are either
bound by binder
or bound by some binder outside of binder
.
If binder
is ty::INNERMOST
, this indicates whether
there are any late-bound regions that appear free.fn error_reported(&self) -> Result<(), <I as Interner>::ErrorGuaranteed>
source§fn has_vars_bound_above(&self, binder: DebruijnIndex) -> bool
fn has_vars_bound_above(&self, binder: DebruijnIndex) -> bool
true
if this type has any regions that escape binder
(and
hence are not bound by it).source§fn has_escaping_bound_vars(&self) -> bool
fn has_escaping_bound_vars(&self) -> bool
true
if this type has regions that are not a part of the type.
For example, for<'a> fn(&'a i32)
return false
, while fn(&'a i32)
would return true
. The latter can occur when traversing through the
former. Read morefn has_aliases(&self) -> bool
fn has_inherent_projections(&self) -> bool
fn has_opaque_types(&self) -> bool
fn has_coroutines(&self) -> bool
fn references_error(&self) -> bool
fn has_non_region_param(&self) -> bool
fn has_infer_regions(&self) -> bool
fn has_infer_types(&self) -> bool
fn has_non_region_infer(&self) -> bool
fn has_infer(&self) -> bool
fn has_placeholders(&self) -> bool
fn has_non_region_placeholders(&self) -> bool
fn has_param(&self) -> bool
source§fn has_free_regions(&self) -> bool
fn has_free_regions(&self) -> bool
fn has_erased_regions(&self) -> bool
source§fn has_erasable_regions(&self) -> bool
fn has_erasable_regions(&self) -> bool
source§fn is_global(&self) -> bool
fn is_global(&self) -> bool
source§fn has_bound_regions(&self) -> bool
fn has_bound_regions(&self) -> bool
source§fn has_non_region_bound_vars(&self) -> bool
fn has_non_region_bound_vars(&self) -> bool
source§fn has_bound_vars(&self) -> bool
fn has_bound_vars(&self) -> bool
source§fn still_further_specializable(&self) -> bool
fn still_further_specializable(&self) -> bool
impl
specialization.source§impl<I, T, U> Upcast<I, U> for Twhere
U: UpcastFrom<I, T>,
impl<I, T, U> Upcast<I, U> for Twhere
U: UpcastFrom<I, T>,
source§impl<I, T> UpcastFrom<I, T> for T
impl<I, T> UpcastFrom<I, T> for T
fn upcast_from(from: T, _tcx: I) -> T
source§impl<Tcx, T> Value<Tcx> for Twhere
Tcx: DepContext,
impl<Tcx, T> Value<Tcx> for Twhere
Tcx: DepContext,
default fn from_cycle_error( tcx: Tcx, cycle_error: &CycleError, _guar: ErrorGuaranteed, ) -> T
source§impl<T> WithSubscriber for T
impl<T> WithSubscriber for T
source§fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
source§fn with_current_subscriber(self) -> WithDispatch<Self>
fn with_current_subscriber(self) -> WithDispatch<Self>
impl<'a, T> Captures<'a> for Twhere
T: ?Sized,
impl<T> ErasedDestructor for Twhere
T: 'static,
impl<T> MaybeSendSync for T
Layout§
Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...)
attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.
Size: 4 bytes