Struct chalk_ir::DebruijnIndex

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

References the binder at the given depth. The index is a de Bruijn index, so it counts back through the in-scope binders, with 0 being the innermost binder. This is used in impls and the like. For example, if we had a rule like for<T> { (T: Clone) :- (T: Copy) }, then T would be represented as a BoundVar(0) (as the for is the innermost binder).

Fields

depth: u32

Implementations

impl DebruijnIndex

pub const INNERMOST: DebruijnIndex = _

Innermost index.

pub const ONE: DebruijnIndex = _

One level higher than the innermost index.

pub fn new(depth: u32) -> Self

Creates a new de Bruijn index with a given depth.

pub fn depth(self) -> u32

Depth of the De Bruijn index, counting from 0 starting with the innermost binder.

pub fn within(self, outer_binder: DebruijnIndex) -> bool

True if the binder identified by this index is within the binder identified by the index outer_binder.

Example

Imagine you have the following binders in scope

forall<a> forall<b> forall<c>

then the Debruijn index for c would be 0, the index for b would be 1, and so on. Now consider the following calls:

• c.within(a) = true
• b.within(a) = true
• a.within(a) = false
• a.within(c) = false

pub fn shifted_in(self) -> DebruijnIndex

Returns the resulting index when this value is moved into through one binder.

pub fn shift_in(&mut self)

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

pub fn shifted_in_from(self, outer_binder: DebruijnIndex) -> DebruijnIndex

Adds outer_binder levels to the self index. Intuitively, this shifts the self index, which was valid at the outer binder, so that it is valid at the innermost binder.

Example: Assume that the following binders are in scope:

for<A> for<B> for<C> for<D>
           ^ outer binder

Assume further that the outer_binder argument is 2, which means that it is referring to the for<B> binder (since D would be the innermost binder).

This means that self is relative to the binder B – so if self is 0 (INNERMOST), then it refers to B, and if self is 1, then it refers to A.

We will return as follows:

• 0.shifted_in_from(2) = 2 – i.e., B, when shifted in to the binding level D, has index 2
• 1.shifted_in_from(2) = 3 – i.e., A, when shifted in to the binding level D, has index 3
• 2.shifted_in_from(1) = 3 – here, we changed the outer_binder to refer to C. Therefore 2 (relative to C) refers to A, so the result is still 3 (since A, relative to the innermost binder, has index 3).

pub fn shifted_out(self) -> Option<DebruijnIndex>

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

pub fn shift_out(&mut self)

Update in place by shifting out from amount binders.

pub fn shifted_out_to( self, outer_binder: DebruijnIndex, ) -> Option<DebruijnIndex>

Subtracts outer_binder levels from the self index. Intuitively, this shifts the self index, which was valid at the innermost binder, to one that is valid at the binder outer_binder.

This will return None if the self index is internal to the outer binder (i.e., if self < outer_binder).

Example: Assume that the following binders are in scope:

for<A> for<B> for<C> for<D>
           ^ outer binder

Assume further that the outer_binder argument is 2, which means that it is referring to the for<B> binder (since D would be the innermost binder).

This means that the result is relative to the binder B – so if self is 0 (INNERMOST), then it refers to B, and if self is 1, then it refers to A.

We will return as follows:

• 1.shifted_out_to(2) = None – i.e., the binder for C can’t be named from the binding level B
• 3.shifted_out_to(2) = Some(1) – i.e., A, when shifted out to the binding level B, has index 1

Trait Implementations

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 Hash for DebruijnIndex

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

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 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 + PartialOrd,

Restrict a value to a certain interval.

impl PartialEq for DebruijnIndex

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

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

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.

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

This method tests less than (for self and other) and is used by the < operator.

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

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

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

This method tests greater than (for self and other) and is used by the > operator.

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

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

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

fn try_fold_with<E>( self, _folder: &mut dyn FallibleTypeFolder<I, Error = E>, _outer_binder: DebruijnIndex, ) -> Result<Self, E>

Apply the given folder folder to self; binders is the number of binders that are in scope when beginning the folder. Typically binders starts as 0, but is adjusted when we encounter Binders<T> in the IR or other similar constructs.

fn fold_with( self, folder: &mut dyn TypeFolder<I>, outer_binder: DebruijnIndex, ) -> Self

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: Interner> TypeVisitable<I> for DebruijnIndex

fn visit_with<B>( &self, _visitor: &mut dyn TypeVisitor<I, BreakTy = B>, _outer_binder: DebruijnIndex, ) -> ControlFlow<B>

Apply the given visitor visitor to self; binders is the number of binders that are in scope when beginning the visitor. Typically binders starts as 0, but is adjusted when we encounter Binders<T> in the IR or other similar constructs.

impl Copy for DebruijnIndex

impl Eq for DebruijnIndex

impl StructuralPartialEq for DebruijnIndex