compiler/rustc_mir/src/dataflow/framework/lattice.rs

   1 //! Traits used to represent [lattices] for use as the domain of a dataflow analysis.
   2 //!
   3 //! # Overview
   4 //!
   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.
   9 //!
  10 //! ```text
  11 //!      {X, Y}    <- top
  12 //!       /  \
  13 //!    {X}    {Y}
  14 //!       \  /
  15 //!        {}      <- bottom
  16 //!
  17 //! ```
  18 //!
  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.
  25 //!
  26 //! ## `PartialOrd`
  27 //!
  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.
  35 //!
  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
  40
  41 use rustc_index::bit_set::BitSet;
  42 use rustc_index::vec::{Idx, IndexVec};
  43
  44 /// A [partially ordered set][poset] that has a [least upper bound][lub] for any pair of elements
  45 /// in the set.
  46 ///
  47 /// [lub]: https://en.wikipedia.org/wiki/Infimum_and_supremum
  48 /// [poset]: https://en.wikipedia.org/wiki/Partially_ordered_set
  49 pub trait JoinSemiLattice: Eq {
  50     /// Computes the least upper bound of two elements, storing the result in `self` and returning
  51     /// `true` if `self` has changed.
  52     ///
  53     /// The lattice join operator is abbreviated as `∨`.
  54     fn join(&mut self, other: &Self) -> bool;
  55 }
  56
  57 /// A [partially ordered set][poset] that has a [greatest lower bound][glb] for any pair of
  58 /// elements in the set.
  59 ///
  60 /// Dataflow analyses only require that their domains implement [`JoinSemiLattice`], not
  61 /// `MeetSemiLattice`. However, types that will be used as dataflow domains should implement both
  62 /// so that they can be used with [`Dual`].
  63 ///
  64 /// [glb]: https://en.wikipedia.org/wiki/Infimum_and_supremum
  65 /// [poset]: https://en.wikipedia.org/wiki/Partially_ordered_set
  66 pub trait MeetSemiLattice: Eq {
  67     /// Computes the greatest lower bound of two elements, storing the result in `self` and
  68     /// returning `true` if `self` has changed.
  69     ///
  70     /// The lattice meet operator is abbreviated as `∧`.
  71     fn meet(&mut self, other: &Self) -> bool;
  72 }
  73
  74 /// A `bool` is a "two-point" lattice with `true` as the top element and `false` as the bottom:
  75 ///
  76 /// ```text
  77 ///      true
  78 ///        |
  79 ///      false
  80 /// ```
  81 impl JoinSemiLattice for bool {
  82     fn join(&mut self, other: &Self) -> bool {
  83         if let (false, true) = (*self, *other) {
  84             *self = true;
  85             return true;
  86         }
  87
  88         false
  89     }
  90 }
  91
  92 impl MeetSemiLattice for bool {
  93     fn meet(&mut self, other: &Self) -> bool {
  94         if let (true, false) = (*self, *other) {
  95             *self = false;
  96             return true;
  97         }
  98
  99         false
 100     }
 101 }
 102
 103 /// A tuple (or list) of lattices is itself a lattice whose least upper bound is the concatenation
 104 /// of the least upper bounds of each element of the tuple (or list).
 105 ///
 106 /// In other words:
 107 ///     (A₀, A₁, ..., Aₙ) ∨ (B₀, B₁, ..., Bₙ) = (A₀∨B₀, A₁∨B₁, ..., Aₙ∨Bₙ)
 108 impl<I: Idx, T: JoinSemiLattice> JoinSemiLattice for IndexVec<I, T> {
 109     fn join(&mut self, other: &Self) -> bool {
 110         assert_eq!(self.len(), other.len());
 111
 112         let mut changed = false;
 113         for (a, b) in self.iter_mut().zip(other.iter()) {
 114             changed |= a.join(b);
 115         }
 116         changed
 117     }
 118 }
 119
 120 impl<I: Idx, T: MeetSemiLattice> MeetSemiLattice for IndexVec<I, T> {
 121     fn meet(&mut self, other: &Self) -> bool {
 122         assert_eq!(self.len(), other.len());
 123
 124         let mut changed = false;
 125         for (a, b) in self.iter_mut().zip(other.iter()) {
 126             changed |= a.meet(b);
 127         }
 128         changed
 129     }
 130 }
 131
 132 /// A `BitSet` represents the lattice formed by the powerset of all possible values of
 133 /// the index type `T` ordered by inclusion. Equivalently, it is a tuple of "two-point" lattices,
 134 /// one for each possible value of `T`.
 135 impl<T: Idx> JoinSemiLattice for BitSet<T> {
 136     fn join(&mut self, other: &Self) -> bool {
 137         self.union(other)
 138     }
 139 }
 140
 141 impl<T: Idx> MeetSemiLattice for BitSet<T> {
 142     fn meet(&mut self, other: &Self) -> bool {
 143         self.intersect(other)
 144     }
 145 }
 146
 147 /// The counterpart of a given semilattice `T` using the [inverse order].
 148 ///
 149 /// The dual of a join-semilattice is a meet-semilattice and vice versa. For example, the dual of a
 150 /// powerset has the empty set as its top element and the full set as its bottom element and uses
 151 /// set *intersection* as its join operator.
 152 ///
 153 /// [inverse order]: https://en.wikipedia.org/wiki/Duality_(order_theory)
 154 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
 155 pub struct Dual<T>(pub T);
 156
 157 impl<T> std::borrow::Borrow<T> for Dual<T> {
 158     fn borrow(&self) -> &T {
 159         &self.0
 160     }
 161 }
 162
 163 impl<T> std::borrow::BorrowMut<T> for Dual<T> {
 164     fn borrow_mut(&mut self) -> &mut T {
 165         &mut self.0
 166     }
 167 }
 168
 169 impl<T: MeetSemiLattice> JoinSemiLattice for Dual<T> {
 170     fn join(&mut self, other: &Self) -> bool {
 171         self.0.meet(&other.0)
 172     }
 173 }
 174
 175 impl<T: JoinSemiLattice> MeetSemiLattice for Dual<T> {
 176     fn meet(&mut self, other: &Self) -> bool {
 177         self.0.join(&other.0)
 178     }
 179 }
 180
 181 /// Extends a type `T` with top and bottom elements to make it a partially ordered set in which no
 182 /// value of `T` is comparable with any other. A flat set has the following [Hasse diagram]:
 183 ///
 184 /// ```text
 185 ///         top
 186 ///       / /  \ \
 187 /// all possible values of `T`
 188 ///       \ \  / /
 189 ///        bottom
 190 /// ```
 191 ///
 192 /// [Hasse diagram]: https://en.wikipedia.org/wiki/Hasse_diagram
 193 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
 194 pub enum FlatSet<T> {
 195     Bottom,
 196     Elem(T),
 197     Top,
 198 }
 199
 200 impl<T: Clone + Eq> JoinSemiLattice for FlatSet<T> {
 201     fn join(&mut self, other: &Self) -> bool {
 202         let result = match (&*self, other) {
 203             (Self::Top, _) | (_, Self::Bottom) => return false,
 204             (Self::Elem(a), Self::Elem(b)) if a == b => return false,
 205
 206             (Self::Bottom, Self::Elem(x)) => Self::Elem(x.clone()),
 207
 208             _ => Self::Top,
 209         };
 210
 211         *self = result;
 212         true
 213     }
 214 }
 215
 216 impl<T: Clone + Eq> MeetSemiLattice for FlatSet<T> {
 217     fn meet(&mut self, other: &Self) -> bool {
 218         let result = match (&*self, other) {
 219             (Self::Bottom, _) | (_, Self::Top) => return false,
 220             (Self::Elem(ref a), Self::Elem(ref b)) if a == b => return false,
 221
 222             (Self::Top, Self::Elem(ref x)) => Self::Elem(x.clone()),
 223
 224             _ => Self::Bottom,
 225         };
 226
 227         *self = result;
 228         true
 229     }
 230 }