1 //! Fix-point analyses on the IR using the "monotone framework".
2 //!
3 //! A lattice is a set with a partial ordering between elements, where there is
4 //! a single least upper bound and a single greatest least bound for every
5 //! subset. We are dealing with finite lattices, which means that it has a
6 //! finite number of elements, and it follows that there exists a single top and
7 //! a single bottom member of the lattice. For example, the power set of a
8 //! finite set forms a finite lattice where partial ordering is defined by set
9 //! inclusion, that is `a <= b` if `a` is a subset of `b`. Here is the finite
10 //! lattice constructed from the set {0,1,2}:
11 //!
12 //! ```text
13 //! .----- Top = {0,1,2} -----.
14 //! / | \
15 //! / | \
16 //! / | \
17 //! {0,1} -------. {0,2} .--------- {1,2}
18 //! | \ / \ / |
19 //! | / \ |
20 //! | / \ / \ |
21 //! {0} --------' {1} `---------- {2}
22 //! \ | /
23 //! \ | /
24 //! \ | /
25 //! `------ Bottom = {} ------'
26 //! ```
27 //!
28 //! A monotone function `f` is a function where if `x <= y`, then it holds that
29 //! `f(x) <= f(y)`. It should be clear that running a monotone function to a
30 //! fix-point on a finite lattice will always terminate: `f` can only "move"
31 //! along the lattice in a single direction, and therefore can only either find
32 //! a fix-point in the middle of the lattice or continue to the top or bottom
33 //! depending if it is ascending or descending the lattice respectively.
34 //!
35 //! For a deeper introduction to the general form of this kind of analysis, see
36 //! [Static Program Analysis by Anders Møller and Michael I. Schwartzbach][spa].
37 //!
38 //! [spa]: https://cs.au.dk/~amoeller/spa/spa.pdf
39
40 // Re-export individual analyses.
41 mod template_params;
42 pub(crate) use self::template_params::UsedTemplateParameters;
43 mod derive;
44 pub use self::derive::DeriveTrait;
45 pub(crate) use self::derive::{as_cannot_derive_set, CannotDerive};
46 mod has_vtable;
47 pub(crate) use self::has_vtable::{
48 HasVtable, HasVtableAnalysis, HasVtableResult,
49 };
50 mod has_destructor;
51 pub(crate) use self::has_destructor::HasDestructorAnalysis;
52 mod has_type_param_in_array;
53 pub(crate) use self::has_type_param_in_array::HasTypeParameterInArray;
54 mod has_float;
55 pub(crate) use self::has_float::HasFloat;
56 mod sizedness;
57 pub(crate) use self::sizedness::{
58 Sizedness, SizednessAnalysis, SizednessResult,
59 };
60
61 use crate::ir::context::{BindgenContext, ItemId};
62
63 use crate::ir::traversal::{EdgeKind, Trace};
64 use crate::HashMap;
65 use std::fmt;
66 use std::ops;
67
68 /// An analysis in the monotone framework.
69 ///
70 /// Implementors of this trait must maintain the following two invariants:
71 ///
72 /// 1. The concrete data must be a member of a finite-height lattice.
73 /// 2. The concrete `constrain` method must be monotone: that is,
74 /// if `x <= y`, then `constrain(x) <= constrain(y)`.
75 ///
76 /// If these invariants do not hold, iteration to a fix-point might never
77 /// complete.
78 ///
79 /// For a simple example analysis, see the `ReachableFrom` type in the `tests`
80 /// module below.
81 pub(crate) trait MonotoneFramework: Sized + fmt::Debug {
82 /// The type of node in our dependency graph.
83 ///
84 /// This is just generic (and not `ItemId`) so that we can easily unit test
85 /// without constructing real `Item`s and their `ItemId`s.
86 type Node: Copy;
87
88 /// Any extra data that is needed during computation.
89 ///
90 /// Again, this is just generic (and not `&BindgenContext`) so that we can
91 /// easily unit test without constructing real `BindgenContext`s full of
92 /// real `Item`s and real `ItemId`s.
93 type Extra: Sized;
94
95 /// The final output of this analysis. Once we have reached a fix-point, we
96 /// convert `self` into this type, and return it as the final result of the
97 /// analysis.
98 type Output: From<Self> + fmt::Debug;
99
100 /// Construct a new instance of this analysis.
new(extra: Self::Extra) -> Self101 fn new(extra: Self::Extra) -> Self;
102
103 /// Get the initial set of nodes from which to start the analysis. Unless
104 /// you are sure of some domain-specific knowledge, this should be the
105 /// complete set of nodes.
initial_worklist(&self) -> Vec<Self::Node>106 fn initial_worklist(&self) -> Vec<Self::Node>;
107
108 /// Update the analysis for the given node.
109 ///
110 /// If this results in changing our internal state (ie, we discovered that
111 /// we have not reached a fix-point and iteration should continue), return
112 /// `ConstrainResult::Changed`. Otherwise, return `ConstrainResult::Same`.
113 /// When `constrain` returns `ConstrainResult::Same` for all nodes in the
114 /// set, we have reached a fix-point and the analysis is complete.
constrain(&mut self, node: Self::Node) -> ConstrainResult115 fn constrain(&mut self, node: Self::Node) -> ConstrainResult;
116
117 /// For each node `d` that depends on the given `node`'s current answer when
118 /// running `constrain(d)`, call `f(d)`. This informs us which new nodes to
119 /// queue up in the worklist when `constrain(node)` reports updated
120 /// information.
each_depending_on<F>(&self, node: Self::Node, f: F) where F: FnMut(Self::Node)121 fn each_depending_on<F>(&self, node: Self::Node, f: F)
122 where
123 F: FnMut(Self::Node);
124 }
125
126 /// Whether an analysis's `constrain` function modified the incremental results
127 /// or not.
128 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
129 pub(crate) enum ConstrainResult {
130 /// The incremental results were updated, and the fix-point computation
131 /// should continue.
132 Changed,
133
134 /// The incremental results were not updated.
135 Same,
136 }
137
138 impl Default for ConstrainResult {
default() -> Self139 fn default() -> Self {
140 ConstrainResult::Same
141 }
142 }
143
144 impl ops::BitOr for ConstrainResult {
145 type Output = Self;
146
bitor(self, rhs: ConstrainResult) -> Self::Output147 fn bitor(self, rhs: ConstrainResult) -> Self::Output {
148 if self == ConstrainResult::Changed || rhs == ConstrainResult::Changed {
149 ConstrainResult::Changed
150 } else {
151 ConstrainResult::Same
152 }
153 }
154 }
155
156 impl ops::BitOrAssign for ConstrainResult {
bitor_assign(&mut self, rhs: ConstrainResult)157 fn bitor_assign(&mut self, rhs: ConstrainResult) {
158 *self = *self | rhs;
159 }
160 }
161
162 /// Run an analysis in the monotone framework.
analyze<Analysis>(extra: Analysis::Extra) -> Analysis::Output where Analysis: MonotoneFramework,163 pub(crate) fn analyze<Analysis>(extra: Analysis::Extra) -> Analysis::Output
164 where
165 Analysis: MonotoneFramework,
166 {
167 let mut analysis = Analysis::new(extra);
168 let mut worklist = analysis.initial_worklist();
169
170 while let Some(node) = worklist.pop() {
171 if let ConstrainResult::Changed = analysis.constrain(node) {
172 analysis.each_depending_on(node, |needs_work| {
173 worklist.push(needs_work);
174 });
175 }
176 }
177
178 analysis.into()
179 }
180
181 /// Generate the dependency map for analysis
generate_dependencies<F>( ctx: &BindgenContext, consider_edge: F, ) -> HashMap<ItemId, Vec<ItemId>> where F: Fn(EdgeKind) -> bool,182 pub(crate) fn generate_dependencies<F>(
183 ctx: &BindgenContext,
184 consider_edge: F,
185 ) -> HashMap<ItemId, Vec<ItemId>>
186 where
187 F: Fn(EdgeKind) -> bool,
188 {
189 let mut dependencies = HashMap::default();
190
191 for &item in ctx.allowlisted_items() {
192 dependencies.entry(item).or_insert_with(Vec::new);
193
194 {
195 // We reverse our natural IR graph edges to find dependencies
196 // between nodes.
197 item.trace(
198 ctx,
199 &mut |sub_item: ItemId, edge_kind| {
200 if ctx.allowlisted_items().contains(&sub_item) &&
201 consider_edge(edge_kind)
202 {
203 dependencies
204 .entry(sub_item)
205 .or_insert_with(Vec::new)
206 .push(item);
207 }
208 },
209 &(),
210 );
211 }
212 }
213 dependencies
214 }
215
216 #[cfg(test)]
217 mod tests {
218 use super::*;
219 use crate::{HashMap, HashSet};
220
221 // Here we find the set of nodes that are reachable from any given
222 // node. This is a lattice mapping nodes to subsets of all nodes. Our join
223 // function is set union.
224 //
225 // This is our test graph:
226 //
227 // +---+ +---+
228 // | | | |
229 // | 1 | .----| 2 |
230 // | | | | |
231 // +---+ | +---+
232 // | | ^
233 // | | |
234 // | +---+ '------'
235 // '----->| |
236 // | 3 |
237 // .------| |------.
238 // | +---+ |
239 // | ^ |
240 // v | v
241 // +---+ | +---+ +---+
242 // | | | | | | |
243 // | 4 | | | 5 |--->| 6 |
244 // | | | | | | |
245 // +---+ | +---+ +---+
246 // | | | |
247 // | | | v
248 // | +---+ | +---+
249 // | | | | | |
250 // '----->| 7 |<-----' | 8 |
251 // | | | |
252 // +---+ +---+
253 //
254 // And here is the mapping from a node to the set of nodes that are
255 // reachable from it within the test graph:
256 //
257 // 1: {3,4,5,6,7,8}
258 // 2: {2}
259 // 3: {3,4,5,6,7,8}
260 // 4: {3,4,5,6,7,8}
261 // 5: {3,4,5,6,7,8}
262 // 6: {8}
263 // 7: {3,4,5,6,7,8}
264 // 8: {}
265
266 #[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
267 struct Node(usize);
268
269 #[derive(Clone, Debug, Default, PartialEq, Eq)]
270 struct Graph(HashMap<Node, Vec<Node>>);
271
272 impl Graph {
make_test_graph() -> Graph273 fn make_test_graph() -> Graph {
274 let mut g = Graph::default();
275 g.0.insert(Node(1), vec![Node(3)]);
276 g.0.insert(Node(2), vec![Node(2)]);
277 g.0.insert(Node(3), vec![Node(4), Node(5)]);
278 g.0.insert(Node(4), vec![Node(7)]);
279 g.0.insert(Node(5), vec![Node(6), Node(7)]);
280 g.0.insert(Node(6), vec![Node(8)]);
281 g.0.insert(Node(7), vec![Node(3)]);
282 g.0.insert(Node(8), vec![]);
283 g
284 }
285
reverse(&self) -> Graph286 fn reverse(&self) -> Graph {
287 let mut reversed = Graph::default();
288 for (node, edges) in self.0.iter() {
289 reversed.0.entry(*node).or_insert_with(Vec::new);
290 for referent in edges.iter() {
291 reversed
292 .0
293 .entry(*referent)
294 .or_insert_with(Vec::new)
295 .push(*node);
296 }
297 }
298 reversed
299 }
300 }
301
302 #[derive(Clone, Debug, PartialEq, Eq)]
303 struct ReachableFrom<'a> {
304 reachable: HashMap<Node, HashSet<Node>>,
305 graph: &'a Graph,
306 reversed: Graph,
307 }
308
309 impl<'a> MonotoneFramework for ReachableFrom<'a> {
310 type Node = Node;
311 type Extra = &'a Graph;
312 type Output = HashMap<Node, HashSet<Node>>;
313
new(graph: &'a Graph) -> ReachableFrom314 fn new(graph: &'a Graph) -> ReachableFrom {
315 let reversed = graph.reverse();
316 ReachableFrom {
317 reachable: Default::default(),
318 graph,
319 reversed,
320 }
321 }
322
initial_worklist(&self) -> Vec<Node>323 fn initial_worklist(&self) -> Vec<Node> {
324 self.graph.0.keys().cloned().collect()
325 }
326
constrain(&mut self, node: Node) -> ConstrainResult327 fn constrain(&mut self, node: Node) -> ConstrainResult {
328 // The set of nodes reachable from a node `x` is
329 //
330 // reachable(x) = s_0 U s_1 U ... U reachable(s_0) U reachable(s_1) U ...
331 //
332 // where there exist edges from `x` to each of `s_0, s_1, ...`.
333 //
334 // Yes, what follows is a **terribly** inefficient set union
335 // implementation. Don't copy this code outside of this test!
336
337 let original_size = self.reachable.entry(node).or_default().len();
338
339 for sub_node in self.graph.0[&node].iter() {
340 self.reachable.get_mut(&node).unwrap().insert(*sub_node);
341
342 let sub_reachable =
343 self.reachable.entry(*sub_node).or_default().clone();
344
345 for transitive in sub_reachable {
346 self.reachable.get_mut(&node).unwrap().insert(transitive);
347 }
348 }
349
350 let new_size = self.reachable[&node].len();
351 if original_size != new_size {
352 ConstrainResult::Changed
353 } else {
354 ConstrainResult::Same
355 }
356 }
357
each_depending_on<F>(&self, node: Node, mut f: F) where F: FnMut(Node),358 fn each_depending_on<F>(&self, node: Node, mut f: F)
359 where
360 F: FnMut(Node),
361 {
362 for dep in self.reversed.0[&node].iter() {
363 f(*dep);
364 }
365 }
366 }
367
368 impl<'a> From<ReachableFrom<'a>> for HashMap<Node, HashSet<Node>> {
from(reachable: ReachableFrom<'a>) -> Self369 fn from(reachable: ReachableFrom<'a>) -> Self {
370 reachable.reachable
371 }
372 }
373
374 #[test]
monotone()375 fn monotone() {
376 let g = Graph::make_test_graph();
377 let reachable = analyze::<ReachableFrom>(&g);
378 println!("reachable = {:#?}", reachable);
379
380 fn nodes<A>(nodes: A) -> HashSet<Node>
381 where
382 A: AsRef<[usize]>,
383 {
384 nodes.as_ref().iter().cloned().map(Node).collect()
385 }
386
387 let mut expected = HashMap::default();
388 expected.insert(Node(1), nodes([3, 4, 5, 6, 7, 8]));
389 expected.insert(Node(2), nodes([2]));
390 expected.insert(Node(3), nodes([3, 4, 5, 6, 7, 8]));
391 expected.insert(Node(4), nodes([3, 4, 5, 6, 7, 8]));
392 expected.insert(Node(5), nodes([3, 4, 5, 6, 7, 8]));
393 expected.insert(Node(6), nodes([8]));
394 expected.insert(Node(7), nodes([3, 4, 5, 6, 7, 8]));
395 expected.insert(Node(8), nodes([]));
396 println!("expected = {:#?}", expected);
397
398 assert_eq!(reachable, expected);
399 }
400 }
401