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