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

source

pub const MAX_AS_U32: u32 = 4_294_967_040u32

Maximum value the index can take, as a u32.

source

pub const MAX: DebruijnIndex = _

Maximum value the index can take.

source

pub const ZERO: DebruijnIndex = _

Zero value of the index.

source

pub const fn from_usize(value: usize) -> DebruijnIndex

Creates a new index from a given usize.

§Panics

Will panic if value exceeds MAX.

source

pub const fn from_u32(value: u32) -> DebruijnIndex

Creates a new index from a given u32.

§Panics

Will panic if value exceeds MAX.

source

pub const fn from_u16(value: u16) -> DebruijnIndex

Creates a new index from a given u16.

§Panics

Will panic if value exceeds MAX.

source

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

pub const fn index(self) -> usize

Extracts the value of this index as a usize.

source

pub const fn as_u32(self) -> u32

Extracts the value of this index as a u32.

source

pub const fn as_usize(self) -> usize

Extracts the value of this index as a usize.

source§

impl DebruijnIndex

source

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.

source

pub fn shift_in(&mut self, amount: u32)

Update this index in place by shifting it “in” through amount number of binders.

source

pub fn shifted_out(self, amount: u32) -> DebruijnIndex

Returns the resulting index when this value is moved out from amount number of new binders.

source

pub fn shift_out(&mut self, amount: u32)

Update in place by shifting out from amount binders.

source

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

§

type Output = DebruijnIndex

The resulting type after applying the + operator.
source§

fn add(self, other: usize) -> DebruijnIndex

Performs the + operation. Read more
source§

impl Clone for DebruijnIndex

source§

fn clone(&self) -> DebruijnIndex

Returns a copy of the value. Read more
1.0.0 · source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
source§

impl Debug for DebruijnIndex

source§

fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter. Read more
source§

impl<D> Decodable<D> for DebruijnIndex
where D: Decoder,

source§

impl<E> Encodable<E> for DebruijnIndex
where E: Encoder,

source§

fn encode(&self, e: &mut E)

source§

impl From<u32> for DebruijnIndex

source§

fn from(value: u32) -> DebruijnIndex

Converts to this type from the input type.
source§

impl From<usize> for DebruijnIndex

source§

fn from(value: usize) -> DebruijnIndex

Converts to this type from the input type.
source§

impl Hash for DebruijnIndex

source§

fn hash<__H>(&self, state: &mut __H)
where __H: Hasher,

Feeds this value into the given Hasher. Read more
1.3.0 · source§

fn hash_slice<H>(data: &[Self], state: &mut H)
where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher. Read more
source§

impl<__CTX> HashStable<__CTX> for DebruijnIndex

source§

fn hash_stable( &self, __hcx: &mut __CTX, __hasher: &mut StableHasher<SipHasher128>, )

source§

impl Idx for DebruijnIndex

source§

fn new(value: usize) -> DebruijnIndex

source§

fn index(self) -> usize

source§

fn increment_by(&mut self, amount: usize)

source§

fn plus(self, amount: usize) -> Self

source§

impl Ord for DebruijnIndex

source§

fn cmp(&self, other: &DebruijnIndex) -> Ordering

This method returns an Ordering between self and other. Read more
1.21.0 · source§

fn max(self, other: Self) -> Self
where Self: Sized,

Compares and returns the maximum of two values. Read more
1.21.0 · source§

fn min(self, other: Self) -> Self
where Self: Sized,

Compares and returns the minimum of two values. Read more
1.50.0 · source§

fn clamp(self, min: Self, max: Self) -> Self
where Self: Sized + PartialOrd,

Restrict a value to a certain interval. Read more
source§

impl PartialEq for DebruijnIndex

source§

fn eq(&self, other: &DebruijnIndex) -> bool

This method tests for self and other values to be equal, and is used by ==.
1.0.0 · source§

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
source§

impl PartialOrd for DebruijnIndex

source§

fn partial_cmp(&self, other: &DebruijnIndex) -> Option<Ordering>

This method returns an ordering between self and other values if one exists. Read more
1.0.0 · source§

fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator. Read more
1.0.0 · source§

fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator. Read more
1.0.0 · source§

fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator. Read more
1.0.0 · source§

fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator. Read more
source§

impl Step for DebruijnIndex

source§

fn steps_between(start: &DebruijnIndex, end: &DebruijnIndex) -> Option<usize>

🔬This is a nightly-only experimental API. (step_trait)
Returns the number of successor steps required to get from start to end. Read more
source§

fn forward_checked(start: DebruijnIndex, u: usize) -> Option<DebruijnIndex>

🔬This is a nightly-only experimental API. (step_trait)
Returns the value that would be obtained by taking the successor of self count times. Read more
source§

fn backward_checked(start: DebruijnIndex, u: usize) -> Option<DebruijnIndex>

🔬This is a nightly-only experimental API. (step_trait)
Returns the value that would be obtained by taking the predecessor of self count times. Read more
source§

fn forward(start: Self, count: usize) -> Self

🔬This is a nightly-only experimental API. (step_trait)
Returns the value that would be obtained by taking the successor of self count times. Read more
source§

unsafe fn forward_unchecked(start: Self, count: usize) -> Self

🔬This is a nightly-only experimental API. (step_trait)
Returns the value that would be obtained by taking the successor of self count times. Read more
source§

fn backward(start: Self, count: usize) -> Self

🔬This is a nightly-only experimental API. (step_trait)
Returns the value that would be obtained by taking the predecessor of self count times. Read more
source§

unsafe fn backward_unchecked(start: Self, count: usize) -> Self

🔬This is a nightly-only experimental API. (step_trait)
Returns the value that would be obtained by taking the predecessor of self count times. Read more
source§

impl<I> TypeFoldable<I> for DebruijnIndex
where I: Interner,

source§

fn try_fold_with<F>( self, _: &mut F, ) -> Result<DebruijnIndex, <F as FallibleTypeFolder<I>>::Error>
where F: FallibleTypeFolder<I>,

The entry point for folding. To fold a value t with a folder f call: t.try_fold_with(f). Read more
source§

fn fold_with<F>(self, _: &mut F) -> DebruijnIndex
where F: TypeFolder<I>,

A convenient alternative to 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 DebruijnIndex
where I: Interner,

source§

fn visit_with<F>(&self, _: &mut F) -> <F as TypeVisitor<I>>::Result
where F: TypeVisitor<I>,

The entry point for visiting. To visit a value t with a visitor v call: t.visit_with(v). Read more
source§

impl Copy for DebruijnIndex

source§

impl Eq for DebruijnIndex

source§

impl StructuralPartialEq for DebruijnIndex

Auto Trait Implementations§

Blanket Implementations§

source§

impl<T> Aligned for T

source§

const ALIGN: Alignment = _

Alignment of Self.
source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> AnyEq for T
where T: Any + PartialEq,

source§

fn equals(&self, other: &(dyn Any + 'static)) -> bool

source§

fn as_any(&self) -> &(dyn Any + 'static)

source§

impl<'tcx, T> ArenaAllocatable<'tcx, IsCopy> for T
where T: Copy,

source§

fn allocate_on<'a>(self, arena: &'a Arena<'tcx>) -> &'a mut T

source§

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 T
where T: Copy,

source§

fn allocate_on<'a>(self, arena: &'a Arena<'tcx>) -> &'a mut T

source§

fn allocate_from_iter<'a>( arena: &'a Arena<'tcx>, iter: impl IntoIterator<Item = T>, ) -> &'a mut [T]

source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> CloneToUninit for T
where T: Copy,

source§

unsafe fn clone_to_uninit(&self, dst: *mut T)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. Read more
source§

impl<T> CloneToUninit for T
where T: Clone,

source§

default unsafe fn clone_to_uninit(&self, dst: *mut T)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. Read more
source§

impl<T, R> CollectAndApply<T, R> for T

source§

fn collect_and_apply<I, F>(iter: I, f: F) -> R
where I: Iterator<Item = T>, F: FnOnce(&[T]) -> R,

Equivalent to f(&iter.collect::<Vec<_>>()).

§

type Output = R

source§

impl<Q, K> Comparable<K> for Q
where Q: Ord + ?Sized, K: Borrow<Q> + ?Sized,

source§

fn compare(&self, key: &K) -> Ordering

Compare self to key and return their ordering.
source§

impl<Tcx, T> DepNodeParams<Tcx> for T
where Tcx: DepContext, T: for<'a> HashStable<StableHashingContext<'a>> + Debug,

source§

default fn fingerprint_style() -> FingerprintStyle

source§

default fn to_fingerprint(&self, tcx: Tcx) -> Fingerprint

This method turns the parameters of a DepNodeConstructor into an opaque Fingerprint to be used in DepNode. Not all DepNodeParams support being turned into a Fingerprint (they don’t need to if the corresponding DepNode is anonymous).
source§

default fn to_debug_str(&self, _: Tcx) -> String

source§

default fn recover(_: Tcx, _: &DepNode) -> Option<T>

This method tries to recover the query key from the given DepNode, something which is needed when forcing DepNodes 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
where Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

source§

fn equivalent(&self, key: &K) -> bool

Checks if this value is equivalent to the given key. Read more
source§

impl<Q, K> Equivalent<K> for Q
where Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

source§

fn equivalent(&self, key: &K) -> bool

Checks if this value is equivalent to the given key. Read more
source§

impl<Q, K> Equivalent<K> for Q
where Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

source§

fn equivalent(&self, key: &K) -> bool

Compare self to key and return true if they are equal.
source§

impl<T> Filterable for T

source§

fn filterable( self, filter_name: &'static str, ) -> RequestFilterDataProvider<T, fn(_: DataRequest<'_>) -> bool>

Creates a filterable data provider with the given name for debugging. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T> Instrument for T

source§

fn instrument(self, span: Span) -> Instrumented<Self>

Instruments this type with the provided Span, returning an Instrumented wrapper. Read more
source§

fn in_current_span(self) -> Instrumented<Self>

Instruments this type with the current Span, returning an Instrumented wrapper. Read more
source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> IntoEither for T

source§

fn into_either(self, into_left: bool) -> Either<Self, Self>

Converts 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 more
source§

fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
where F: FnOnce(&Self) -> bool,

Converts 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 more
source§

impl<P> IntoQueryParam<P> for P

source§

impl<'tcx, T> IsSuggestable<'tcx> for T
where T: TypeVisitable<TyCtxt<'tcx>> + TypeFoldable<TyCtxt<'tcx>>,

source§

fn is_suggestable(self, tcx: TyCtxt<'tcx>, infer_suggestable: bool) -> bool

Whether this makes sense to suggest in a diagnostic. Read more
source§

fn make_suggestable( self, tcx: TyCtxt<'tcx>, infer_suggestable: bool, placeholder: Option<Ty<'tcx>>, ) -> Option<T>

source§

impl<T> MaybeResult<T> for T

§

type Error = !

source§

fn from(_: Result<T, <T as MaybeResult<T>>::Error>) -> T

source§

fn to_result(self) -> Result<T, <T as MaybeResult<T>>::Error>

source§

impl<T> Same for T

§

type Output = T

Should always be Self
source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
source§

impl<I, T> TypeVisitableExt<I> for T
where I: Interner, T: TypeVisitable<I>,

source§

fn has_type_flags(&self, flags: TypeFlags) -> bool

source§

fn has_vars_bound_at_or_above(&self, binder: DebruijnIndex) -> bool

Returns 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.
source§

fn error_reported(&self) -> Result<(), <I as Interner>::ErrorGuaranteed>

source§

fn has_vars_bound_above(&self, binder: DebruijnIndex) -> bool

Returns 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

Return 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 more
source§

fn has_aliases(&self) -> bool

source§

fn has_inherent_projections(&self) -> bool

source§

fn has_opaque_types(&self) -> bool

source§

fn has_coroutines(&self) -> bool

source§

fn references_error(&self) -> bool

source§

fn has_non_region_param(&self) -> bool

source§

fn has_infer_regions(&self) -> bool

source§

fn has_infer_types(&self) -> bool

source§

fn has_non_region_infer(&self) -> bool

source§

fn has_infer(&self) -> bool

source§

fn has_placeholders(&self) -> bool

source§

fn has_non_region_placeholders(&self) -> bool

source§

fn has_param(&self) -> bool

source§

fn has_free_regions(&self) -> bool

“Free” regions in this context means that it has any region that is not (a) erased or (b) late-bound.
source§

fn has_erased_regions(&self) -> bool

source§

fn has_erasable_regions(&self) -> bool

True if there are any un-erased free regions.
source§

fn is_global(&self) -> bool

Indicates whether this value references only ‘global’ generic parameters that are the same regardless of what fn we are in. This is used for caching.
source§

fn has_bound_regions(&self) -> bool

True if there are any late-bound regions
source§

fn has_non_region_bound_vars(&self) -> bool

True if there are any late-bound non-region variables
source§

fn has_bound_vars(&self) -> bool

True if there are any bound variables
source§

fn still_further_specializable(&self) -> bool

Indicates whether this value still has parameters/placeholders/inference variables which could be replaced later, in a way that would change the results of impl specialization.
source§

impl<I, T, U> Upcast<I, U> for T
where U: UpcastFrom<I, T>,

source§

fn upcast(self, interner: I) -> U

source§

impl<I, T> UpcastFrom<I, T> for T

source§

fn upcast_from(from: T, _tcx: I) -> T

source§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

source§

fn vzip(self) -> V

source§

impl<Tcx, T> Value<Tcx> for T
where Tcx: DepContext,

source§

default fn from_cycle_error( tcx: Tcx, cycle_error: &CycleError, _guar: ErrorGuaranteed, ) -> T

source§

impl<T> WithSubscriber for T

source§

fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
where S: Into<Dispatch>,

Attaches the provided Subscriber to this type, returning a WithDispatch wrapper. Read more
source§

fn with_current_subscriber(self) -> WithDispatch<Self>

Attaches the current default Subscriber to this type, returning a WithDispatch wrapper. Read more
source§

impl<'a, T> Captures<'a> for T
where T: ?Sized,

source§

impl<T> ErasedDestructor for T
where T: 'static,

source§

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