# Module rustc_mir_dataflow::lattice

Expand description

Traits used to represent lattices for use as the domain of a dataflow analysis.

## Overview

The most common lattice is a powerset of some set `S`, ordered by set inclusion. The Hasse diagram for the powerset of a set with two elements (`X` and `Y`) is shown below. Note that distinct elements at the same height in a Hasse diagram (e.g. `{X}` and `{Y}`) are incomparable, not equal.

``````     {X, Y}    <- top
/  \
{X}    {Y}
\  /
{}      <- bottom
``````

The defining characteristic of a lattice—the one that differentiates it from a partially ordered set—is the existence of a unique least upper and greatest lower bound for every pair of elements. The lattice join operator (`∨`) returns the least upper bound, and the lattice meet operator (`∧`) returns the greatest lower bound. Types that implement one operator but not the other are known as semilattices. Dataflow analysis only uses the join operator and will work with any join-semilattice, but both should be specified when possible.

### `PartialOrd`

Given that they represent partially ordered sets, you may be surprised that `JoinSemiLattice` and `MeetSemiLattice` do not have `PartialOrd` as a supertrait. This is because most standard library types use lexicographic ordering instead of set inclusion for their `PartialOrd` impl. Since we do not actually need to compare lattice elements to run a dataflow analysis, there’s no need for a newtype wrapper with a custom `PartialOrd` impl. The only benefit would be the ability to check that the least upper (or greatest lower) bound returned by the lattice join (or meet) operator was in fact greater (or lower) than the inputs.

## Structs

The counterpart of a given semilattice `T` using the inverse order.

## Enums

Extends a type `T` with top and bottom elements to make it a partially ordered set in which no value of `T` is comparable with any other.

## Traits

A set that has a “bottom” element, which is less than or equal to any other element.
A set that has a “top” element, which is greater than or equal to any other element.
A partially ordered set that has a least upper bound for any pair of elements in the set.
A partially ordered set that has a greatest lower bound for any pair of elements in the set.