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