1//! Determining which types has vtable
2
3use 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;
10
11/// The result of the `HasVtableAnalysis` for an individual item.
12#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
13pub(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
25impl Default for HasVtableResult {
26 fn default() -> Self {
27 HasVtableResult::No
28 }
29}
30
31impl HasVtableResult {
32 /// Take the least upper bound of `self` and `rhs`.
33 pub(crate) fn join(self, rhs: Self) -> Self {
34 cmp::max(self, v2:rhs)
35 }
36}
37
38impl ops::BitOr for HasVtableResult {
39 type Output = Self;
40
41 fn bitor(self, rhs: HasVtableResult) -> Self::Output {
42 self.join(rhs)
43 }
44}
45
46impl 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)]
63pub(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
80impl<'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
133impl<'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
215impl<'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.
233pub(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}
241