compiler/rustc_mir_dataflow/src/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`] 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 crate::framework::BitSetExt;
  42 use rustc_index::bit_set::{BitSet, ChunkedBitSet, HybridBitSet};
  43 use rustc_index::vec::{Idx, IndexVec};
  44 use std::iter;
  45
  46 /// A [partially ordered set][poset] that has a [least upper bound][lub] for any pair of elements
  47 /// in the set.
  48 ///
  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.
  54     ///
  55     /// The lattice join operator is abbreviated as `∨`.
  56     fn join(&mut self, other: &Self) -> bool;
  57 }
  58
  59 /// A [partially ordered set][poset] that has a [greatest lower bound][glb] for any pair of
  60 /// elements in the set.
  61 ///
  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`].
  65 ///
  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.
  71     ///
  72     /// The lattice meet operator is abbreviated as `∧`.
  73     fn meet(&mut self, other: &Self) -> bool;
  74 }
  75
  76 /// A set that has a "bottom" element, which is less than or equal to any other element.
  77 pub trait HasBottom {
  78     fn bottom() -> Self;
  79 }
  80
  81 /// A set that has a "top" element, which is greater than or equal to any other element.
  82 pub trait HasTop {
  83     fn top() -> Self;
  84 }
  85
  86 /// A `bool` is a "two-point" lattice with `true` as the top element and `false` as the bottom:
  87 ///
  88 /// ```text
  89 ///      true
  90 ///        |
  91 ///      false
  92 /// ```
  93 impl JoinSemiLattice for bool {
  94     fn join(&mut self, other: &Self) -> bool {
  95         if let (false, true) = (*self, *other) {
  96             *self = true;
  97             return true;
  98         }
  99
 100         false
 101     }
 102 }
 103
 104 impl MeetSemiLattice for bool {
 105     fn meet(&mut self, other: &Self) -> bool {
 106         if let (true, false) = (*self, *other) {
 107             *self = false;
 108             return true;
 109         }
 110
 111         false
 112     }
 113 }
 114
 115 impl HasBottom for bool {
 116     fn bottom() -> Self {
 117         false
 118     }
 119 }
 120
 121 impl HasTop for bool {
 122     fn top() -> Self {
 123         true
 124     }
 125 }
 126
 127 /// A tuple (or list) of lattices is itself a lattice whose least upper bound is the concatenation
 128 /// of the least upper bounds of each element of the tuple (or list).
 129 ///
 130 /// In other words:
 131 ///     (A₀, A₁, ..., Aₙ) ∨ (B₀, B₁, ..., Bₙ) = (A₀∨B₀, A₁∨B₁, ..., Aₙ∨Bₙ)
 132 impl<I: Idx, T: JoinSemiLattice> JoinSemiLattice for IndexVec<I, T> {
 133     fn join(&mut self, other: &Self) -> bool {
 134         assert_eq!(self.len(), other.len());
 135
 136         let mut changed = false;
 137         for (a, b) in iter::zip(self, other) {
 138             changed |= a.join(b);
 139         }
 140         changed
 141     }
 142 }
 143
 144 impl<I: Idx, T: MeetSemiLattice> MeetSemiLattice for IndexVec<I, T> {
 145     fn meet(&mut self, other: &Self) -> bool {
 146         assert_eq!(self.len(), other.len());
 147
 148         let mut changed = false;
 149         for (a, b) in iter::zip(self, other) {
 150             changed |= a.meet(b);
 151         }
 152         changed
 153     }
 154 }
 155
 156 /// A `BitSet` represents the lattice formed by the powerset of all possible values of
 157 /// the index type `T` ordered by inclusion. Equivalently, it is a tuple of "two-point" lattices,
 158 /// one for each possible value of `T`.
 159 impl<T: Idx> JoinSemiLattice for BitSet<T> {
 160     fn join(&mut self, other: &Self) -> bool {
 161         self.union(other)
 162     }
 163 }
 164
 165 impl<T: Idx> MeetSemiLattice for BitSet<T> {
 166     fn meet(&mut self, other: &Self) -> bool {
 167         self.intersect(other)
 168     }
 169 }
 170
 171 impl<T: Idx> JoinSemiLattice for ChunkedBitSet<T> {
 172     fn join(&mut self, other: &Self) -> bool {
 173         self.union(other)
 174     }
 175 }
 176
 177 impl<T: Idx> MeetSemiLattice for ChunkedBitSet<T> {
 178     fn meet(&mut self, other: &Self) -> bool {
 179         self.intersect(other)
 180     }
 181 }
 182
 183 /// The counterpart of a given semilattice `T` using the [inverse order].
 184 ///
 185 /// The dual of a join-semilattice is a meet-semilattice and vice versa. For example, the dual of a
 186 /// powerset has the empty set as its top element and the full set as its bottom element and uses
 187 /// set *intersection* as its join operator.
 188 ///
 189 /// [inverse order]: https://en.wikipedia.org/wiki/Duality_(order_theory)
 190 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
 191 pub struct Dual<T>(pub T);
 192
 193 impl<T: Idx> BitSetExt<T> for Dual<BitSet<T>> {
 194     fn domain_size(&self) -> usize {
 195         self.0.domain_size()
 196     }
 197
 198     fn contains(&self, elem: T) -> bool {
 199         self.0.contains(elem)
 200     }
 201
 202     fn union(&mut self, other: &HybridBitSet<T>) {
 203         self.0.union(other);
 204     }
 205
 206     fn subtract(&mut self, other: &HybridBitSet<T>) {
 207         self.0.subtract(other);
 208     }
 209 }
 210
 211 impl<T: MeetSemiLattice> JoinSemiLattice for Dual<T> {
 212     fn join(&mut self, other: &Self) -> bool {
 213         self.0.meet(&other.0)
 214     }
 215 }
 216
 217 impl<T: JoinSemiLattice> MeetSemiLattice for Dual<T> {
 218     fn meet(&mut self, other: &Self) -> bool {
 219         self.0.join(&other.0)
 220     }
 221 }
 222
 223 /// Extends a type `T` with top and bottom elements to make it a partially ordered set in which no
 224 /// value of `T` is comparable with any other.
 225 ///
 226 /// A flat set has the following [Hasse diagram]:
 227 ///
 228 /// ```text
 229 ///          top
 230 ///  / ... / /  \ \ ... \
 231 /// all possible values of `T`
 232 ///  \ ... \ \  / / ... /
 233 ///         bottom
 234 /// ```
 235 ///
 236 /// [Hasse diagram]: https://en.wikipedia.org/wiki/Hasse_diagram
 237 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
 238 pub enum FlatSet<T> {
 239     Bottom,
 240     Elem(T),
 241     Top,
 242 }
 243
 244 impl<T: Clone + Eq> JoinSemiLattice for FlatSet<T> {
 245     fn join(&mut self, other: &Self) -> bool {
 246         let result = match (&*self, other) {
 247             (Self::Top, _) | (_, Self::Bottom) => return false,
 248             (Self::Elem(a), Self::Elem(b)) if a == b => return false,
 249
 250             (Self::Bottom, Self::Elem(x)) => Self::Elem(x.clone()),
 251
 252             _ => Self::Top,
 253         };
 254
 255         *self = result;
 256         true
 257     }
 258 }
 259
 260 impl<T: Clone + Eq> MeetSemiLattice for FlatSet<T> {
 261     fn meet(&mut self, other: &Self) -> bool {
 262         let result = match (&*self, other) {
 263             (Self::Bottom, _) | (_, Self::Top) => return false,
 264             (Self::Elem(ref a), Self::Elem(ref b)) if a == b => return false,
 265
 266             (Self::Top, Self::Elem(ref x)) => Self::Elem(x.clone()),
 267
 268             _ => Self::Bottom,
 269         };
 270
 271         *self = result;
 272         true
 273     }
 274 }
 275
 276 impl<T> HasBottom for FlatSet<T> {
 277     fn bottom() -> Self {
 278         Self::Bottom
 279     }
 280 }
 281
 282 impl<T> HasTop for FlatSet<T> {
 283     fn top() -> Self {
 284         Self::Top
 285     }
 286 }