]>
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`] | |
9c376795 | 29 | //! and [`MeetSemiLattice`] do not have [`PartialOrd`] as a supertrait. This |
1b1a35ee XL |
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 | ||
5e7ed085 FG |
41 | use crate::framework::BitSetExt; |
42 | use rustc_index::bit_set::{BitSet, ChunkedBitSet, HybridBitSet}; | |
1b1a35ee | 43 | use rustc_index::vec::{Idx, IndexVec}; |
cdc7bbd5 | 44 | use std::iter; |
1b1a35ee XL |
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 | ||
487cf647 FG |
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 | ||
1b1a35ee XL |
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 | ||
487cf647 FG |
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 | ||
1b1a35ee XL |
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; | |
cdc7bbd5 | 137 | for (a, b) in iter::zip(self, other) { |
1b1a35ee XL |
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; | |
cdc7bbd5 | 149 | for (a, b) in iter::zip(self, other) { |
1b1a35ee XL |
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 | ||
5e7ed085 FG |
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 | ||
1b1a35ee XL |
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 | ||
5e7ed085 FG |
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); | |
1b1a35ee | 204 | } |
1b1a35ee | 205 | |
5e7ed085 FG |
206 | fn subtract(&mut self, other: &HybridBitSet<T>) { |
207 | self.0.subtract(other); | |
1b1a35ee XL |
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 | |
064997fb FG |
224 | /// value of `T` is comparable with any other. |
225 | /// | |
226 | /// A flat set has the following [Hasse diagram]: | |
1b1a35ee XL |
227 | /// |
228 | /// ```text | |
064997fb FG |
229 | /// top |
230 | /// / ... / / \ \ ... \ | |
1b1a35ee | 231 | /// all possible values of `T` |
064997fb FG |
232 | /// \ ... \ \ / / ... / |
233 | /// bottom | |
1b1a35ee XL |
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 | } | |
487cf647 FG |
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 | } |