| 1 |
//! Determining which types has vtable |
| 2 |
|
| 3 |
use super::{generate_dependencies, ConstrainResult, MonotoneFramework}; |
| 4 |
use crate::ir::context::{BindgenContext, ItemId}; |
| 5 |
use crate::ir::traversal::EdgeKind; |
| 6 |
use crate::ir::ty::TypeKind; |
| 7 |
use crate::{Entry, HashMap}; |
| 8 |
use std::cmp; |
| 9 |
use std::ops; |
| 10 |
|
| 11 |
/// The result of the `HasVtableAnalysis` for an individual item. |
| 12 |
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)] |
| 13 |
pub(crate) enum HasVtableResult { |
| 14 |
/// The item does not have a vtable pointer. |
| 15 |
No, |
| 16 |
|
| 17 |
/// The item has a vtable and the actual vtable pointer is within this item. |
| 18 |
SelfHasVtable, |
| 19 |
|
| 20 |
/// The item has a vtable, but the actual vtable pointer is in a base |
| 21 |
/// member. |
| 22 |
BaseHasVtable, |
| 23 |
} |
| 24 |
|
| 25 |
impl Default for HasVtableResult { |
| 26 |
fn default() -> Self { |
| 27 |
HasVtableResult::No |
| 28 |
} |
| 29 |
} |
| 30 |
|
| 31 |
impl HasVtableResult { |
| 32 |
/// Take the least upper bound of `self` and `rhs`. |
| 33 |
pub(crate) fn join(self, rhs: Self) -> Self { |
| 34 |
cmp::max(self, rhs) |
| 35 |
} |
| 36 |
} |
| 37 |
|
| 38 |
impl ops::BitOr for HasVtableResult { |
| 39 |
type Output = Self; |
| 40 |
|
| 41 |
fn bitor(self, rhs: HasVtableResult) -> Self::Output { |
| 42 |
self.join(rhs) |
| 43 |
} |
| 44 |
} |
| 45 |
|
| 46 |
impl ops::BitOrAssign for HasVtableResult { |
| 47 |
fn bitor_assign(&mut self, rhs: HasVtableResult) { |
| 48 |
*self = self.join(rhs) |
| 49 |
} |
| 50 |
} |
| 51 |
|
| 52 |
/// An analysis that finds for each IR item whether it has vtable or not |
| 53 |
/// |
| 54 |
/// We use the monotone function `has vtable`, defined as follows: |
| 55 |
/// |
| 56 |
/// * If T is a type alias, a templated alias, an indirection to another type, |
| 57 |
/// or a reference of a type, T has vtable if the type T refers to has vtable. |
| 58 |
/// * If T is a compound type, T has vtable if we saw a virtual function when |
| 59 |
/// parsing it or any of its base member has vtable. |
| 60 |
/// * If T is an instantiation of an abstract template definition, T has |
| 61 |
/// vtable if template definition has vtable |
| 62 |
#[derive(Debug, Clone)] |
| 63 |
pub(crate) struct HasVtableAnalysis<'ctx> { |
| 64 |
ctx: &'ctx BindgenContext, |
| 65 |
|
| 66 |
// The incremental result of this analysis's computation. Everything in this |
| 67 |
// set definitely has a vtable. |
| 68 |
have_vtable: HashMap<ItemId, HasVtableResult>, |
| 69 |
|
| 70 |
// Dependencies saying that if a key ItemId has been inserted into the |
| 71 |
// `have_vtable` set, then each of the ids in Vec<ItemId> need to be |
| 72 |
// considered again. |
| 73 |
// |
| 74 |
// This is a subset of the natural IR graph with reversed edges, where we |
| 75 |
// only include the edges from the IR graph that can affect whether a type |
| 76 |
// has a vtable or not. |
| 77 |
dependencies: HashMap<ItemId, Vec<ItemId>>, |
| 78 |
} |
| 79 |
|
| 80 |
impl<'ctx> HasVtableAnalysis<'ctx> { |
| 81 |
fn consider_edge(kind: EdgeKind) -> bool { |
| 82 |
// These are the only edges that can affect whether a type has a |
| 83 |
// vtable or not. |
| 84 |
matches!( |
| 85 |
kind, |
| 86 |
EdgeKind::TypeReference | |
| 87 |
EdgeKind::BaseMember | |
| 88 |
EdgeKind::TemplateDeclaration |
| 89 |
) |
| 90 |
} |
| 91 |
|
| 92 |
fn insert<Id: Into<ItemId>>( |
| 93 |
&mut self, |
| 94 |
id: Id, |
| 95 |
result: HasVtableResult, |
| 96 |
) -> ConstrainResult { |
| 97 |
if let HasVtableResult::No = result { |
| 98 |
return ConstrainResult::Same; |
| 99 |
} |
| 100 |
|
| 101 |
let id = id.into(); |
| 102 |
match self.have_vtable.entry(id) { |
| 103 |
Entry::Occupied(mut entry) => { |
| 104 |
if *entry.get() < result { |
| 105 |
entry.insert(result); |
| 106 |
ConstrainResult::Changed |
| 107 |
} else { |
| 108 |
ConstrainResult::Same |
| 109 |
} |
| 110 |
} |
| 111 |
Entry::Vacant(entry) => { |
| 112 |
entry.insert(result); |
| 113 |
ConstrainResult::Changed |
| 114 |
} |
| 115 |
} |
| 116 |
} |
| 117 |
|
| 118 |
fn forward<Id1, Id2>(&mut self, from: Id1, to: Id2) -> ConstrainResult |
| 119 |
where |
| 120 |
Id1: Into<ItemId>, |
| 121 |
Id2: Into<ItemId>, |
| 122 |
{ |
| 123 |
let from = from.into(); |
| 124 |
let to = to.into(); |
| 125 |
|
| 126 |
match self.have_vtable.get(&from).cloned() { |
| 127 |
None => ConstrainResult::Same, |
| 128 |
Some(r) => self.insert(to, r), |
| 129 |
} |
| 130 |
} |
| 131 |
} |
| 132 |
|
| 133 |
impl<'ctx> MonotoneFramework for HasVtableAnalysis<'ctx> { |
| 134 |
type Node = ItemId; |
| 135 |
type Extra = &'ctx BindgenContext; |
| 136 |
type Output = HashMap<ItemId, HasVtableResult>; |
| 137 |
|
| 138 |
fn new(ctx: &'ctx BindgenContext) -> HasVtableAnalysis<'ctx> { |
| 139 |
let have_vtable = HashMap::default(); |
| 140 |
let dependencies = generate_dependencies(ctx, Self::consider_edge); |
| 141 |
|
| 142 |
HasVtableAnalysis { |
| 143 |
ctx, |
| 144 |
have_vtable, |
| 145 |
dependencies, |
| 146 |
} |
| 147 |
} |
| 148 |
|
| 149 |
fn initial_worklist(&self) -> Vec<ItemId> { |
| 150 |
self.ctx.allowlisted_items().iter().cloned().collect() |
| 151 |
} |
| 152 |
|
| 153 |
fn constrain(&mut self, id: ItemId) -> ConstrainResult { |
| 154 |
trace!("constrain {:?}", id); |
| 155 |
|
| 156 |
let item = self.ctx.resolve_item(id); |
| 157 |
let ty = match item.as_type() { |
| 158 |
None => return ConstrainResult::Same, |
| 159 |
Some(ty) => ty, |
| 160 |
}; |
| 161 |
|
| 162 |
// TODO #851: figure out a way to handle deriving from template type parameters. |
| 163 |
match *ty.kind() { |
| 164 |
TypeKind::TemplateAlias(t, _) | |
| 165 |
TypeKind::Alias(t) | |
| 166 |
TypeKind::ResolvedTypeRef(t) | |
| 167 |
TypeKind::Reference(t) => { |
| 168 |
trace!( |
| 169 |
" aliases and references forward to their inner type" |
| 170 |
); |
| 171 |
self.forward(t, id) |
| 172 |
} |
| 173 |
|
| 174 |
TypeKind::Comp(ref info) => { |
| 175 |
trace!(" comp considers its own methods and bases"); |
| 176 |
let mut result = HasVtableResult::No; |
| 177 |
|
| 178 |
if info.has_own_virtual_method() { |
| 179 |
trace!(" comp has its own virtual method"); |
| 180 |
result |= HasVtableResult::SelfHasVtable; |
| 181 |
} |
| 182 |
|
| 183 |
let bases_has_vtable = info.base_members().iter().any(|base| { |
| 184 |
trace!(" comp has a base with a vtable: {:?}", base); |
| 185 |
self.have_vtable.contains_key(&base.ty.into()) |
| 186 |
}); |
| 187 |
if bases_has_vtable { |
| 188 |
result |= HasVtableResult::BaseHasVtable; |
| 189 |
} |
| 190 |
|
| 191 |
self.insert(id, result) |
| 192 |
} |
| 193 |
|
| 194 |
TypeKind::TemplateInstantiation(ref inst) => { |
| 195 |
self.forward(inst.template_definition(), id) |
| 196 |
} |
| 197 |
|
| 198 |
_ => ConstrainResult::Same, |
| 199 |
} |
| 200 |
} |
| 201 |
|
| 202 |
fn each_depending_on<F>(&self, id: ItemId, mut f: F) |
| 203 |
where |
| 204 |
F: FnMut(ItemId), |
| 205 |
{ |
| 206 |
if let Some(edges) = self.dependencies.get(&id) { |
| 207 |
for item in edges { |
| 208 |
trace!("enqueue {:?} into worklist", item); |
| 209 |
f(*item); |
| 210 |
} |
| 211 |
} |
| 212 |
} |
| 213 |
} |
| 214 |
|
| 215 |
impl<'ctx> From<HasVtableAnalysis<'ctx>> for HashMap<ItemId, HasVtableResult> { |
| 216 |
fn from(analysis: HasVtableAnalysis<'ctx>) -> Self { |
| 217 |
// We let the lack of an entry mean "No" to save space. |
| 218 |
extra_assert!(analysis |
| 219 |
.have_vtable |
| 220 |
.values() |
| 221 |
.all(|v| { *v != HasVtableResult::No })); |
| 222 |
|
| 223 |
analysis.have_vtable |
| 224 |
} |
| 225 |
} |
| 226 |
|
| 227 |
/// A convenience trait for the things for which we might wonder if they have a |
| 228 |
/// vtable during codegen. |
| 229 |
/// |
| 230 |
/// This is not for _computing_ whether the thing has a vtable, it is for |
| 231 |
/// looking up the results of the HasVtableAnalysis's computations for a |
| 232 |
/// specific thing. |
| 233 |
pub(crate) trait HasVtable { |
| 234 |
/// Return `true` if this thing has vtable, `false` otherwise. |
| 235 |
fn has_vtable(&self, ctx: &BindgenContext) -> bool; |
| 236 |
|
| 237 |
/// Return `true` if this thing has an actual vtable pointer in itself, as |
| 238 |
/// opposed to transitively in a base member. |
| 239 |
fn has_vtable_ptr(&self, ctx: &BindgenContext) -> bool; |
| 240 |
} |