Struct mz_transform::analysis::equivalences::EquivalenceClasses

pub struct EquivalenceClasses {
    pub classes: Vec<Vec<MirScalarExpr>>,
    remap: BTreeMap<MirScalarExpr, MirScalarExpr>,
}

A compact representation of classes of expressions that must be equivalent.

Each “class” contains a list of expressions, each of which must be Eq::eq equal. Ideally, the first element is the “simplest”, e.g. a literal or column reference, and any other element of that list can be replaced by it.

The classes are meant to be minimized, with each expression as reduced as it can be, and all classes sharing an element merged.

Fields

classes: Vec<Vec<MirScalarExpr>>

Multiple lists of equivalent expressions, each representing an equivalence class.

The first element should be the “canonical” simplest element, that any other element can be replaced by. These classes are unified whenever possible, to minimize the number of classes. They are only guaranteed to form an equivalence relation after a call to minimimize, which refreshes both self.classes and self.remap.

remap: BTreeMap<MirScalarExpr, MirScalarExpr>

An expression simplification map.

This map reflects an equivalence relation based on a prior version of self.classes. As users may add to self.classes, self.remap may become stale. We refresh remap only in self.refresh(), to the equivalence relation that derives from self.classes.

It is important to self.remap.clear() if you invalidate it by mutating rather than appending to self.classes. This will be corrected in the next call to self.refresh(), but until then remap could be arbitrarily wrong. This should be improved in the future.

Implementations

impl EquivalenceClasses

pub fn mir_scalar_expr_complexity( e1: &MirScalarExpr, e2: &MirScalarExpr, ) -> Ordering

Comparator function for the complexity of scalar expressions. Simpler expressions are smaller. Can be used when we need to decide which of several equivalent expressions to use.

fn tidy(&mut self)

Sorts and deduplicates each class, removing literal errors.

This method does not ensure equivalence relation structure, but instead performs only minimal structural clean-up.

fn refresh(&mut self) -> bool

Restore equivalence relation structure to self.classes and refresh self.remap.

This method takes roughly linear time, and returns true iff self.remap has changed. This is the only method that refreshes self.remap, and is a perfect place to decide whether the equivalence classes it represents have experienced any changes since the last refresh.

pub fn minimize(&mut self, columns: &Option<Vec<ColumnType>>)

Update self to maintain the same equivalences which potentially reducing along Ord::le.

Informally this means simplifying constraints, removing redundant constraints, and unifying equivalence classes.

fn minimize_once(&mut self, columns: &Option<Vec<ColumnType>>) -> bool

A single iteration of minimization, which we expect to repeat but benefit from factoring out.

This invocation should take roughly linear time. It starts with equivalence class invariants maintained (closed under transitivity), and then

1. Performs per-expression reduction, including the class structure to replace subexpressions.
2. Applies idiom detection to e.g. unpack expressions equivalence to literal true or false.
3. Restores the equivalence class invariants.

pub fn union(&self, other: &Self) -> Self

Produce the equivalences present in both inputs.

pub fn union_many<'a, I>(&self, others: I) -> Self

where I: IntoIterator<Item = &'a Self>,

The equivalence classes of terms equivalent in all inputs.

This method relies on the remap member of each input, and bases the intersection on these rather than classes. This means one should ensure minimize() has been called on all inputs, or risk getting a stale, but conservatively correct, result.

This method currently misses opportunities, because it only looks for exactly matches in expressions, which may not include all possible matches. For example, f(#1) == g(#1) may exist in one class, but in another class where #0 == #1 it may exist as f(#0) == g(#0).

pub fn permute(&mut self, permutation: &[usize])

Permutes each expression, looking up each column reference in permutation and replacing with what it finds.

pub fn project<I>(&mut self, output_columns: I)

where I: IntoIterator<Item = usize> + Clone,

Subject the constraints to the column projection, reworking and removing equivalences.

This method should also introduce equivalences representing any repeated columns.

fn replace(&self, expr: &mut MirScalarExpr) -> bool

Perform any exact replacement for expr, report if it had an effect.

This method is only used internal to Equivalences, and should eventually be replaced by the use of self.remap or something akin to it. The linear scan is not appropriate.

fn reduce_expr(&self, expr: &mut MirScalarExpr) -> bool

Perform any simplification, report if effective.

This method is only used internal to Equivalences, and should eventually be replaced by the use of self.remap or something akin to it. The linear scan is not appropriate.

fn reduce_child(&self, expr: &mut MirScalarExpr) -> bool

Perform any simplification on children, report if effective.

This method is only used internal to Equivalences, and should eventually be replaced by the use of self.remap or something akin to it. The linear scan is not appropriate.

pub fn unsatisfiable(&self) -> bool

True if any equivalence class contains two distinct non-error literals.

pub fn reducer(&self) -> &BTreeMap<MirScalarExpr, MirScalarExpr>

Returns a map that can be used to replace (sub-)expressions.

Trait Implementations

impl Clone for EquivalenceClasses

fn clone(&self) -> EquivalenceClasses

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for EquivalenceClasses

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

Formats the value using the given formatter.

impl Default for EquivalenceClasses

fn default() -> EquivalenceClasses

Returns the “default value” for a type.

impl Ord for EquivalenceClasses

fn cmp(&self, other: &EquivalenceClasses) -> 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 EquivalenceClasses

fn eq(&self, other: &EquivalenceClasses) -> 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 EquivalenceClasses

fn partial_cmp(&self, other: &EquivalenceClasses) -> 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 Eq for EquivalenceClasses

impl StructuralPartialEq for EquivalenceClasses