Struct chalk_ir::DebruijnIndex

source ·
pub struct DebruijnIndex {
    pub(crate) depth: u32,
}
Expand description

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§

source§

impl DebruijnIndex

source

pub const INNERMOST: DebruijnIndex = _

Innermost index.

source

pub const ONE: DebruijnIndex = _

One level higher than the innermost index.

source

pub fn new(depth: u32) -> Self

Creates a new de Bruijn index with a given depth.

source

pub fn depth(self) -> u32

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

source

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
source

pub fn shifted_in(self) -> DebruijnIndex

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

source

pub fn shift_in(&mut self)

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

source

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

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

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

source

pub fn shift_out(&mut self)

Update in place by shifting out from amount binders.

source

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§

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

source§

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

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 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) -> Selfwhere Self: Sized,

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

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

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

fn clamp(self, min: Self, max: Self) -> Selfwhere 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<I: Interner> TypeFoldable<I> for DebruijnIndex

source§

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

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

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

source§

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

impl Copy for DebruijnIndex

source§

impl Eq for DebruijnIndex

source§

impl StructuralEq for DebruijnIndex

source§

impl StructuralPartialEq for DebruijnIndex

Auto Trait Implementations§

Blanket Implementations§

source§

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

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

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

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

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

source§

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

Mutably borrows from an owned value. Read more
source§

impl<T> Cast for T

source§

fn cast<U>(self, interner: U::Interner) -> Uwhere Self: CastTo<U>, U: HasInterner,

Cast a value to type U using CastTo.
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere 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, I> Shift<I> for Twhere T: TypeFoldable<I>, I: Interner,

source§

fn shifted_in(self, interner: I) -> T

Shifts this term in one level of binders.
source§

fn shifted_in_from(self, interner: I, source_binder: DebruijnIndex) -> T

Shifts a term valid at outer_binder so that it is valid at the innermost binder. See DebruijnIndex::shifted_in_from for a detailed explanation.
source§

fn shifted_out_to( self, interner: I, target_binder: DebruijnIndex ) -> Result<T, NoSolution>

Shifts a term valid at the innermost binder so that it is valid at outer_binder. See DebruijnIndex::shifted_out_to for a detailed explanation.
source§

fn shifted_out(self, interner: I) -> Result<T, NoSolution>

Shifts this term out one level of binders.
source§

impl<T> ToOwned for Twhere 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 Twhere 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 Twhere 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<T, I> VisitExt<I> for Twhere I: Interner, T: TypeVisitable<I>,

source§

fn has_free_vars(&self, interner: I) -> bool

Check whether there are free (non-bound) variables.