Struct Bindings

struct Bindings {
    bindings: BTreeMap<MirRelationExpr, u64>,
    rebindings: BTreeMap<LocalId, LocalId>,
    recursion_guard: RecursionGuard,
}

Maintains Let bindings in a compact, explicit representation.

The bindings map contains neither Let bindings nor two structurally equivalent expressions.

The bindings can be interpreted as an ordered sequence of let bindings, ordered by their identifier, that should be applied in order before the use of the expression from which they have been extracted.

Fields

bindings: BTreeMap<MirRelationExpr, u64>

A list of let-bound expressions and their order / identifier.

rebindings: BTreeMap<LocalId, LocalId>

Mapping from conventional local Get identifiers to new ones.

recursion_guard: RecursionGuard

Implementations

impl Bindings

fn new(rebindings: BTreeMap<LocalId, LocalId>) -> Bindings

impl Bindings

fn insert_expression( &mut self, id_gen: &mut IdGen, relation: &mut MirRelationExpr, ) -> Result<(), TransformError>

Ensures self contains bindings for all of relation’s subexpressions, including itself, and replaces relation with a reference to its corresponding identifier.

The algorithm performs a post-order traversal of the expression tree, binding each distinct expression to a new local identifier and replacing each expression with a reference to the identifier for the expression. It maintains the invariant that bindings contains no Let expressions, nor any two structurally identical expressions.

LetRec expressions are treated differently, as their expressions cannot simply be bound to Let expressions. Each LetRec expression clones the current bindings self, and then goes through its bindings in order, extending self with terms discovered in order. Importantly, when a bound term is first visited we re-introduce its identifier with a fresh identifier, to ensure that preceding references to the term are not equated with subsequent references. The LetRec::body is treated differently, as it is “outside” the scope, and should not rely on expressions from within the scope, other than those that it has coming in to the analysis. This is a limitation of our optimization pipeline at the moment, that it breaks if body gains new references to terms within the LetRec bindings (for example: JoinImplementation can break if body acquires a reference to an arranged term, as that arrangement is not available outside the loop).

fn populate_expression(self, expression: &mut MirRelationExpr)

Populates expression with necessary Let bindings.

This population may result in substantially more Let bindings that one might expect. It is very appropriate to run the NormalizeLets transformation afterwards to remove Let bindings that it deems unhelpful.

Trait Implementations

impl CheckedRecursion for Bindings

fn recursion_guard(&self) -> &RecursionGuard

Extracts a reference to the recursion guard embedded within the type.

fn checked_recur<F, T, E>(&self, f: F) -> Result<T, E>

where F: FnOnce(&Self) -> Result<T, E>, E: From<RecursionLimitError>,

Checks whether it is safe to recur and calls f if so.

fn checked_recur_mut<F, T, E>(&mut self, f: F) -> Result<T, E>

where F: FnOnce(&mut Self) -> Result<T, E>, E: From<RecursionLimitError>,

Like CheckedRecursion::checked_recur, but operates on a mutable reference to Self.

impl Clone for Bindings

fn clone(&self) -> Bindings

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Bindings

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

Formats the value using the given formatter.

impl Default for Bindings

fn default() -> Bindings

Returns the “default value” for a type.