]>
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}; | |
49aad941 | 43 | use rustc_index::{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 { | |
49aad941 | 78 | const BOTTOM: Self; |
487cf647 FG |
79 | } |
80 | ||
81 | /// A set that has a "top" element, which is greater than or equal to any other element. | |
82 | pub trait HasTop { | |
49aad941 | 83 | const TOP: Self; |
487cf647 FG |
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 | 115 | impl HasBottom for bool { |
49aad941 | 116 | const BOTTOM: Self = false; |
487cf647 FG |
117 | } |
118 | ||
119 | impl HasTop for bool { | |
49aad941 | 120 | const TOP: Self = true; |
487cf647 FG |
121 | } |
122 | ||
1b1a35ee XL |
123 | /// A tuple (or list) of lattices is itself a lattice whose least upper bound is the concatenation |
124 | /// of the least upper bounds of each element of the tuple (or list). | |
125 | /// | |
126 | /// In other words: | |
127 | /// (A₀, A₁, ..., Aₙ) ∨ (B₀, B₁, ..., Bₙ) = (A₀∨B₀, A₁∨B₁, ..., Aₙ∨Bₙ) | |
128 | impl<I: Idx, T: JoinSemiLattice> JoinSemiLattice for IndexVec<I, T> { | |
129 | fn join(&mut self, other: &Self) -> bool { | |
130 | assert_eq!(self.len(), other.len()); | |
131 | ||
132 | let mut changed = false; | |
cdc7bbd5 | 133 | for (a, b) in iter::zip(self, other) { |
1b1a35ee XL |
134 | changed |= a.join(b); |
135 | } | |
136 | changed | |
137 | } | |
138 | } | |
139 | ||
140 | impl<I: Idx, T: MeetSemiLattice> MeetSemiLattice for IndexVec<I, T> { | |
141 | fn meet(&mut self, other: &Self) -> bool { | |
142 | assert_eq!(self.len(), other.len()); | |
143 | ||
144 | let mut changed = false; | |
cdc7bbd5 | 145 | for (a, b) in iter::zip(self, other) { |
1b1a35ee XL |
146 | changed |= a.meet(b); |
147 | } | |
148 | changed | |
149 | } | |
150 | } | |
151 | ||
152 | /// A `BitSet` represents the lattice formed by the powerset of all possible values of | |
153 | /// the index type `T` ordered by inclusion. Equivalently, it is a tuple of "two-point" lattices, | |
154 | /// one for each possible value of `T`. | |
155 | impl<T: Idx> JoinSemiLattice for BitSet<T> { | |
156 | fn join(&mut self, other: &Self) -> bool { | |
157 | self.union(other) | |
158 | } | |
159 | } | |
160 | ||
161 | impl<T: Idx> MeetSemiLattice for BitSet<T> { | |
162 | fn meet(&mut self, other: &Self) -> bool { | |
163 | self.intersect(other) | |
164 | } | |
165 | } | |
166 | ||
5e7ed085 FG |
167 | impl<T: Idx> JoinSemiLattice for ChunkedBitSet<T> { |
168 | fn join(&mut self, other: &Self) -> bool { | |
169 | self.union(other) | |
170 | } | |
171 | } | |
172 | ||
173 | impl<T: Idx> MeetSemiLattice for ChunkedBitSet<T> { | |
174 | fn meet(&mut self, other: &Self) -> bool { | |
175 | self.intersect(other) | |
176 | } | |
177 | } | |
178 | ||
1b1a35ee XL |
179 | /// The counterpart of a given semilattice `T` using the [inverse order]. |
180 | /// | |
181 | /// The dual of a join-semilattice is a meet-semilattice and vice versa. For example, the dual of a | |
182 | /// powerset has the empty set as its top element and the full set as its bottom element and uses | |
183 | /// set *intersection* as its join operator. | |
184 | /// | |
185 | /// [inverse order]: https://en.wikipedia.org/wiki/Duality_(order_theory) | |
186 | #[derive(Clone, Copy, Debug, PartialEq, Eq)] | |
187 | pub struct Dual<T>(pub T); | |
188 | ||
5e7ed085 FG |
189 | impl<T: Idx> BitSetExt<T> for Dual<BitSet<T>> { |
190 | fn domain_size(&self) -> usize { | |
191 | self.0.domain_size() | |
192 | } | |
193 | ||
194 | fn contains(&self, elem: T) -> bool { | |
195 | self.0.contains(elem) | |
196 | } | |
197 | ||
198 | fn union(&mut self, other: &HybridBitSet<T>) { | |
199 | self.0.union(other); | |
1b1a35ee | 200 | } |
1b1a35ee | 201 | |
5e7ed085 FG |
202 | fn subtract(&mut self, other: &HybridBitSet<T>) { |
203 | self.0.subtract(other); | |
1b1a35ee XL |
204 | } |
205 | } | |
206 | ||
207 | impl<T: MeetSemiLattice> JoinSemiLattice for Dual<T> { | |
208 | fn join(&mut self, other: &Self) -> bool { | |
209 | self.0.meet(&other.0) | |
210 | } | |
211 | } | |
212 | ||
213 | impl<T: JoinSemiLattice> MeetSemiLattice for Dual<T> { | |
214 | fn meet(&mut self, other: &Self) -> bool { | |
215 | self.0.join(&other.0) | |
216 | } | |
217 | } | |
218 | ||
219 | /// Extends a type `T` with top and bottom elements to make it a partially ordered set in which no | |
064997fb FG |
220 | /// value of `T` is comparable with any other. |
221 | /// | |
222 | /// A flat set has the following [Hasse diagram]: | |
1b1a35ee XL |
223 | /// |
224 | /// ```text | |
064997fb FG |
225 | /// top |
226 | /// / ... / / \ \ ... \ | |
1b1a35ee | 227 | /// all possible values of `T` |
064997fb FG |
228 | /// \ ... \ \ / / ... / |
229 | /// bottom | |
1b1a35ee XL |
230 | /// ``` |
231 | /// | |
232 | /// [Hasse diagram]: https://en.wikipedia.org/wiki/Hasse_diagram | |
233 | #[derive(Clone, Copy, Debug, PartialEq, Eq)] | |
234 | pub enum FlatSet<T> { | |
235 | Bottom, | |
236 | Elem(T), | |
237 | Top, | |
238 | } | |
239 | ||
240 | impl<T: Clone + Eq> JoinSemiLattice for FlatSet<T> { | |
241 | fn join(&mut self, other: &Self) -> bool { | |
242 | let result = match (&*self, other) { | |
243 | (Self::Top, _) | (_, Self::Bottom) => return false, | |
244 | (Self::Elem(a), Self::Elem(b)) if a == b => return false, | |
245 | ||
246 | (Self::Bottom, Self::Elem(x)) => Self::Elem(x.clone()), | |
247 | ||
248 | _ => Self::Top, | |
249 | }; | |
250 | ||
251 | *self = result; | |
252 | true | |
253 | } | |
254 | } | |
255 | ||
256 | impl<T: Clone + Eq> MeetSemiLattice for FlatSet<T> { | |
257 | fn meet(&mut self, other: &Self) -> bool { | |
258 | let result = match (&*self, other) { | |
259 | (Self::Bottom, _) | (_, Self::Top) => return false, | |
260 | (Self::Elem(ref a), Self::Elem(ref b)) if a == b => return false, | |
261 | ||
262 | (Self::Top, Self::Elem(ref x)) => Self::Elem(x.clone()), | |
263 | ||
264 | _ => Self::Bottom, | |
265 | }; | |
266 | ||
267 | *self = result; | |
268 | true | |
269 | } | |
270 | } | |
487cf647 FG |
271 | |
272 | impl<T> HasBottom for FlatSet<T> { | |
49aad941 | 273 | const BOTTOM: Self = Self::Bottom; |
487cf647 FG |
274 | } |
275 | ||
276 | impl<T> HasTop for FlatSet<T> { | |
49aad941 | 277 | const TOP: Self = Self::Top; |
487cf647 | 278 | } |