1 //! Traits used to represent [lattices] for use as the domain of a dataflow analysis.
5 //! The most common lattice is a powerset of some set `S`, ordered by [set inclusion]. The [Hasse
6 //! diagram] for the powerset of a set with two elements (`X` and `Y`) is shown below. Note that
7 //! distinct elements at the same height in a Hasse diagram (e.g. `{X}` and `{Y}`) are
8 //! *incomparable*, not equal.
19 //! The defining characteristic of a lattice—the one that differentiates it from a [partially
20 //! ordered set][poset]—is the existence of a *unique* least upper and greatest lower bound for
21 //! every pair of elements. The lattice join operator (`∨`) returns the least upper bound, and the
22 //! lattice meet operator (`∧`) returns the greatest lower bound. Types that implement one operator
23 //! but not the other are known as semilattices. Dataflow analysis only uses the join operator and
24 //! will work with any join-semilattice, but both should be specified when possible.
28 //! Given that they represent partially ordered sets, you may be surprised that [`JoinSemiLattice`]
29 //! and [`MeetSemiLattice`] do not have [`PartialOrd`][std::cmp::PartialOrd] as a supertrait. This
30 //! is because most standard library types use lexicographic ordering instead of set inclusion for
31 //! their `PartialOrd` impl. Since we do not actually need to compare lattice elements to run a
32 //! dataflow analysis, there's no need for a newtype wrapper with a custom `PartialOrd` impl. The
33 //! only benefit would be the ability to check that the least upper (or greatest lower) bound
34 //! returned by the lattice join (or meet) operator was in fact greater (or lower) than the inputs.
36 //! [lattices]: https://en.wikipedia.org/wiki/Lattice_(order)
37 //! [set inclusion]: https://en.wikipedia.org/wiki/Subset
38 //! [Hasse diagram]: https://en.wikipedia.org/wiki/Hasse_diagram
39 //! [poset]: https://en.wikipedia.org/wiki/Partially_ordered_set
41 use crate::framework::BitSetExt;
42 use rustc_index::bit_set::{BitSet, ChunkedBitSet, HybridBitSet};
43 use rustc_index::vec::{Idx, IndexVec};
46 /// A [partially ordered set][poset] that has a [least upper bound][lub] for any pair of elements
49 /// [lub]: https://en.wikipedia.org/wiki/Infimum_and_supremum
50 /// [poset]: https://en.wikipedia.org/wiki/Partially_ordered_set
51 pub trait JoinSemiLattice: Eq {
52 /// Computes the least upper bound of two elements, storing the result in `self` and returning
53 /// `true` if `self` has changed.
55 /// The lattice join operator is abbreviated as `∨`.
56 fn join(&mut self, other: &Self) -> bool;
59 /// A [partially ordered set][poset] that has a [greatest lower bound][glb] for any pair of
60 /// elements in the set.
62 /// Dataflow analyses only require that their domains implement [`JoinSemiLattice`], not
63 /// `MeetSemiLattice`. However, types that will be used as dataflow domains should implement both
64 /// so that they can be used with [`Dual`].
66 /// [glb]: https://en.wikipedia.org/wiki/Infimum_and_supremum
67 /// [poset]: https://en.wikipedia.org/wiki/Partially_ordered_set
68 pub trait MeetSemiLattice: Eq {
69 /// Computes the greatest lower bound of two elements, storing the result in `self` and
70 /// returning `true` if `self` has changed.
72 /// The lattice meet operator is abbreviated as `∧`.
73 fn meet(&mut self, other: &Self) -> bool;
76 /// A `bool` is a "two-point" lattice with `true` as the top element and `false` as the bottom:
83 impl JoinSemiLattice for bool {
84 fn join(&mut self, other: &Self) -> bool {
85 if let (false, true) = (*self, *other) {
94 impl MeetSemiLattice for bool {
95 fn meet(&mut self, other: &Self) -> bool {
96 if let (true, false) = (*self, *other) {
105 /// A tuple (or list) of lattices is itself a lattice whose least upper bound is the concatenation
106 /// of the least upper bounds of each element of the tuple (or list).
109 /// (A₀, A₁, ..., Aₙ) ∨ (B₀, B₁, ..., Bₙ) = (A₀∨B₀, A₁∨B₁, ..., Aₙ∨Bₙ)
110 impl<I: Idx, T: JoinSemiLattice> JoinSemiLattice for IndexVec<I, T> {
111 fn join(&mut self, other: &Self) -> bool {
112 assert_eq!(self.len(), other.len());
114 let mut changed = false;
115 for (a, b) in iter::zip(self, other) {
116 changed |= a.join(b);
122 impl<I: Idx, T: MeetSemiLattice> MeetSemiLattice for IndexVec<I, T> {
123 fn meet(&mut self, other: &Self) -> bool {
124 assert_eq!(self.len(), other.len());
126 let mut changed = false;
127 for (a, b) in iter::zip(self, other) {
128 changed |= a.meet(b);
134 /// A `BitSet` represents the lattice formed by the powerset of all possible values of
135 /// the index type `T` ordered by inclusion. Equivalently, it is a tuple of "two-point" lattices,
136 /// one for each possible value of `T`.
137 impl<T: Idx> JoinSemiLattice for BitSet<T> {
138 fn join(&mut self, other: &Self) -> bool {
143 impl<T: Idx> MeetSemiLattice for BitSet<T> {
144 fn meet(&mut self, other: &Self) -> bool {
145 self.intersect(other)
149 impl<T: Idx> JoinSemiLattice for ChunkedBitSet<T> {
150 fn join(&mut self, other: &Self) -> bool {
155 impl<T: Idx> MeetSemiLattice for ChunkedBitSet<T> {
156 fn meet(&mut self, other: &Self) -> bool {
157 self.intersect(other)
161 /// The counterpart of a given semilattice `T` using the [inverse order].
163 /// The dual of a join-semilattice is a meet-semilattice and vice versa. For example, the dual of a
164 /// powerset has the empty set as its top element and the full set as its bottom element and uses
165 /// set *intersection* as its join operator.
167 /// [inverse order]: https://en.wikipedia.org/wiki/Duality_(order_theory)
168 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
169 pub struct Dual<T>(pub T);
171 impl<T: Idx> BitSetExt<T> for Dual<BitSet<T>> {
172 fn domain_size(&self) -> usize {
176 fn contains(&self, elem: T) -> bool {
177 self.0.contains(elem)
180 fn union(&mut self, other: &HybridBitSet<T>) {
184 fn subtract(&mut self, other: &HybridBitSet<T>) {
185 self.0.subtract(other);
189 impl<T: MeetSemiLattice> JoinSemiLattice for Dual<T> {
190 fn join(&mut self, other: &Self) -> bool {
191 self.0.meet(&other.0)
195 impl<T: JoinSemiLattice> MeetSemiLattice for Dual<T> {
196 fn meet(&mut self, other: &Self) -> bool {
197 self.0.join(&other.0)
201 /// Extends a type `T` with top and bottom elements to make it a partially ordered set in which no
202 /// value of `T` is comparable with any other.
204 /// A flat set has the following [Hasse diagram]:
208 /// / ... / / \ \ ... \
209 /// all possible values of `T`
210 /// \ ... \ \ / / ... /
214 /// [Hasse diagram]: https://en.wikipedia.org/wiki/Hasse_diagram
215 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
216 pub enum FlatSet<T> {
222 impl<T: Clone + Eq> JoinSemiLattice for FlatSet<T> {
223 fn join(&mut self, other: &Self) -> bool {
224 let result = match (&*self, other) {
225 (Self::Top, _) | (_, Self::Bottom) => return false,
226 (Self::Elem(a), Self::Elem(b)) if a == b => return false,
228 (Self::Bottom, Self::Elem(x)) => Self::Elem(x.clone()),
238 impl<T: Clone + Eq> MeetSemiLattice for FlatSet<T> {
239 fn meet(&mut self, other: &Self) -> bool {
240 let result = match (&*self, other) {
241 (Self::Bottom, _) | (_, Self::Top) => return false,
242 (Self::Elem(ref a), Self::Elem(ref b)) if a == b => return false,
244 (Self::Top, Self::Elem(ref x)) => Self::Elem(x.clone()),