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