Struct DebruijnIndex

pub struct DebruijnIndex {
    pub(crate) private_use_as_methods_instead: u32,
}

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

impl DebruijnIndex

pub const MAX_AS_U32: u32 = 4_294_967_040u32

Maximum value the index can take, as a u32.

pub const MAX: DebruijnIndex = _

Maximum value the index can take.

pub const ZERO: DebruijnIndex = _

Zero value of the index.

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

Creates a new index from a given usize.

Panics

Will panic if value exceeds MAX.

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

Creates a new index from a given u32.

Panics

Will panic if value exceeds MAX.

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

Creates a new index from a given u16.

Panics

Will panic if value exceeds MAX.

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.

pub const fn index(self) -> usize

Extracts the value of this index as a usize.

pub const fn as_u32(self) -> u32

Extracts the value of this index as a u32.

pub const fn as_usize(self) -> usize

Extracts the value of this index as a usize.

impl 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.

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

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

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

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

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

Update in place by shifting out from amount binders.

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

impl Add<usize> for DebruijnIndex

type Output = DebruijnIndex

The resulting type after applying the + operator.

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

Performs the + operation.

impl Clone for DebruijnIndex

fn clone(&self) -> DebruijnIndex

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for DebruijnIndex

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

Formats the value using the given formatter.

impl<D> Decodable<D> for DebruijnIndex

where D: Decoder,

fn decode(d: &mut D) -> DebruijnIndex

impl<E> Encodable<E> for DebruijnIndex

where E: Encoder,

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

impl From<u32> for DebruijnIndex

fn from(value: u32) -> DebruijnIndex

Converts to this type from the input type.

impl From<usize> for DebruijnIndex

fn from(value: usize) -> DebruijnIndex

Converts to this type from the input type.

impl Hash for DebruijnIndex

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

where __H: Hasher,

Feeds this value into the given Hasher.

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

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<__CTX> HashStable<__CTX> for DebruijnIndex

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

impl Idx for DebruijnIndex

fn new(value: usize) -> DebruijnIndex

fn index(self) -> usize

fn increment_by(&mut self, amount: usize)

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

impl Ord for DebruijnIndex

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

This method returns an Ordering between self and other.

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

where Self: Sized,

Compares and returns the maximum of two values.

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

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for DebruijnIndex

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

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for DebruijnIndex

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

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Step for DebruijnIndex

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

🔬This is a nightly-only experimental API. (step_trait)

Returns the bounds on the number of successor steps required to get from start to end like Iterator::size_hint().

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.

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.

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.

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.

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.

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.

impl<I> TypeFoldable<I> for DebruijnIndex

where I: Interner,

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).

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.

impl<I> TypeVisitable<I> for DebruijnIndex

where I: Interner,

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).

impl Copy for DebruijnIndex

impl Eq for DebruijnIndex

impl StructuralPartialEq for DebruijnIndex

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