| 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. |
| 101 |
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. |
| 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. |
| 115 |
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. |
| 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 { |
| 139 |
fn default() -> Self { |
| 140 |
ConstrainResult::Same |
| 141 |
} |
| 142 |
} |
| 143 |
|
| 144 |
impl ops::BitOr for ConstrainResult { |
| 145 |
type Output = Self; |
| 146 |
|
| 147 |
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 { |
| 157 |
fn bitor_assign(&mut self, rhs: ConstrainResult) { |
| 158 |
*self = *self | rhs; |
| 159 |
} |
| 160 |
} |
| 161 |
|
| 162 |
/// Run an analysis in the monotone framework. |
| 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 |
| 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 { |
| 273 |
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 |
|
| 286 |
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 |
|
| 314 |
fn new(graph: &'a Graph) -> ReachableFrom { |
| 315 |
let reversed = graph.reverse(); |
| 316 |
ReachableFrom { |
| 317 |
reachable: Default::default(), |
| 318 |
graph, |
| 319 |
reversed, |
| 320 |
} |
| 321 |
} |
| 322 |
|
| 323 |
fn initial_worklist(&self) -> Vec<Node> { |
| 324 |
self.graph.0.keys().cloned().collect() |
| 325 |
} |
| 326 |
|
| 327 |
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 |
| 338 |
.reachable |
| 339 |
.entry(node) |
| 340 |
.or_insert_with(HashSet::default) |
| 341 |
.len(); |
| 342 |
|
| 343 |
for sub_node in self.graph.0[&node].iter() { |
| 344 |
self.reachable.get_mut(&node).unwrap().insert(*sub_node); |
| 345 |
|
| 346 |
let sub_reachable = self |
| 347 |
.reachable |
| 348 |
.entry(*sub_node) |
| 349 |
.or_insert_with(HashSet::default) |
| 350 |
.clone(); |
| 351 |
|
| 352 |
for transitive in sub_reachable { |
| 353 |
self.reachable.get_mut(&node).unwrap().insert(transitive); |
| 354 |
} |
| 355 |
} |
| 356 |
|
| 357 |
let new_size = self.reachable[&node].len(); |
| 358 |
if original_size != new_size { |
| 359 |
ConstrainResult::Changed |
| 360 |
} else { |
| 361 |
ConstrainResult::Same |
| 362 |
} |
| 363 |
} |
| 364 |
|
| 365 |
fn each_depending_on<F>(&self, node: Node, mut f: F) |
| 366 |
where |
| 367 |
F: FnMut(Node), |
| 368 |
{ |
| 369 |
for dep in self.reversed.0[&node].iter() { |
| 370 |
f(*dep); |
| 371 |
} |
| 372 |
} |
| 373 |
} |
| 374 |
|
| 375 |
impl<'a> From<ReachableFrom<'a>> for HashMap<Node, HashSet<Node>> { |
| 376 |
fn from(reachable: ReachableFrom<'a>) -> Self { |
| 377 |
reachable.reachable |
| 378 |
} |
| 379 |
} |
| 380 |
|
| 381 |
#[test] |
| 382 |
fn monotone() { |
| 383 |
let g = Graph::make_test_graph(); |
| 384 |
let reachable = analyze::<ReachableFrom>(&g); |
| 385 |
println!("reachable = {:#?}", reachable); |
| 386 |
|
| 387 |
fn nodes<A>(nodes: A) -> HashSet<Node> |
| 388 |
where |
| 389 |
A: AsRef<[usize]>, |
| 390 |
{ |
| 391 |
nodes.as_ref().iter().cloned().map(Node).collect() |
| 392 |
} |
| 393 |
|
| 394 |
let mut expected = HashMap::default(); |
| 395 |
expected.insert(Node(1), nodes([3, 4, 5, 6, 7, 8])); |
| 396 |
expected.insert(Node(2), nodes([2])); |
| 397 |
expected.insert(Node(3), nodes([3, 4, 5, 6, 7, 8])); |
| 398 |
expected.insert(Node(4), nodes([3, 4, 5, 6, 7, 8])); |
| 399 |
expected.insert(Node(5), nodes([3, 4, 5, 6, 7, 8])); |
| 400 |
expected.insert(Node(6), nodes([8])); |
| 401 |
expected.insert(Node(7), nodes([3, 4, 5, 6, 7, 8])); |
| 402 |
expected.insert(Node(8), nodes([])); |
| 403 |
println!("expected = {:#?}", expected); |
| 404 |
|
| 405 |
assert_eq!(reachable, expected); |
| 406 |
} |
| 407 |
} |