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, Default)]
13pub(crate) enum HasVtableResult {
14 /// The item does not have a vtable pointer.
15 #[default]
16 No,
17
18 /// The item has a vtable and the actual vtable pointer is within this item.
19 SelfHasVtable,
20
21 /// The item has a vtable, but the actual vtable pointer is in a base
22 /// member.
23 BaseHasVtable,
24}
25
26impl HasVtableResult {
27 /// Take the least upper bound of `self` and `rhs`.
28 pub(crate) fn join(self, rhs: Self) -> Self {
29 cmp::max(self, v2:rhs)
30 }
31}
32
33impl ops::BitOr for HasVtableResult {
34 type Output = Self;
35
36 fn bitor(self, rhs: HasVtableResult) -> Self::Output {
37 self.join(rhs)
38 }
39}
40
41impl ops::BitOrAssign for HasVtableResult {
42 fn bitor_assign(&mut self, rhs: HasVtableResult) {
43 *self = self.join(rhs)
44 }
45}
46
47/// 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,
60
61 // The incremental result of this analysis's computation. Everything in this
62 // set definitely has a vtable.
63 have_vtable: HashMap<ItemId, HasVtableResult>,
64
65 // 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.
72 dependencies: HashMap<ItemId, Vec<ItemId>>,
73}
74
75impl<'ctx> HasVtableAnalysis<'ctx> {
76 fn consider_edge(kind: EdgeKind) -> bool {
77 // These are the only edges that can affect whether a type has a
78 // vtable or not.
79 matches!(
80 kind,
81 EdgeKind::TypeReference |
82 EdgeKind::BaseMember |
83 EdgeKind::TemplateDeclaration
84 )
85 }
86
87 fn insert<Id: Into<ItemId>>(
88 &mut self,
89 id: Id,
90 result: HasVtableResult,
91 ) -> ConstrainResult {
92 if let HasVtableResult::No = result {
93 return ConstrainResult::Same;
94 }
95
96 let id = id.into();
97 match self.have_vtable.entry(id) {
98 Entry::Occupied(mut entry) => {
99 if *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 }
112
113 fn forward<Id1, Id2>(&mut self, from: Id1, to: Id2) -> ConstrainResult
114 where
115 Id1: Into<ItemId>,
116 Id2: Into<ItemId>,
117 {
118 let from = from.into();
119 let to = to.into();
120
121 match self.have_vtable.get(&from).cloned() {
122 None => ConstrainResult::Same,
123 Some(r) => self.insert(to, r),
124 }
125 }
126}
127
128impl<'ctx> MonotoneFramework for HasVtableAnalysis<'ctx> {
129 type Node = ItemId;
130 type Extra = &'ctx BindgenContext;
131 type Output = HashMap<ItemId, HasVtableResult>;
132
133 fn new(ctx: &'ctx BindgenContext) -> HasVtableAnalysis<'ctx> {
134 let have_vtable = HashMap::default();
135 let dependencies = generate_dependencies(ctx, Self::consider_edge);
136
137 HasVtableAnalysis {
138 ctx,
139 have_vtable,
140 dependencies,
141 }
142 }
143
144 fn initial_worklist(&self) -> Vec<ItemId> {
145 self.ctx.allowlisted_items().iter().cloned().collect()
146 }
147
148 fn constrain(&mut self, id: ItemId) -> ConstrainResult {
149 trace!("constrain {:?}", id);
150
151 let item = self.ctx.resolve_item(id);
152 let ty = match item.as_type() {
153 None => return ConstrainResult::Same,
154 Some(ty) => ty,
155 };
156
157 // TODO #851: figure out a way to handle deriving from template type parameters.
158 match *ty.kind() {
159 TypeKind::TemplateAlias(t, _) |
160 TypeKind::Alias(t) |
161 TypeKind::ResolvedTypeRef(t) |
162 TypeKind::Reference(t) => {
163 trace!(
164 " aliases and references forward to their inner type"
165 );
166 self.forward(t, id)
167 }
168
169 TypeKind::Comp(ref info) => {
170 trace!(" comp considers its own methods and bases");
171 let mut result = HasVtableResult::No;
172
173 if info.has_own_virtual_method() {
174 trace!(" comp has its own virtual method");
175 result |= HasVtableResult::SelfHasVtable;
176 }
177
178 let bases_has_vtable = info.base_members().iter().any(|base| {
179 trace!(" comp has a base with a vtable: {:?}", base);
180 self.have_vtable.contains_key(&base.ty.into())
181 });
182 if bases_has_vtable {
183 result |= HasVtableResult::BaseHasVtable;
184 }
185
186 self.insert(id, result)
187 }
188
189 TypeKind::TemplateInstantiation(ref inst) => {
190 self.forward(inst.template_definition(), id)
191 }
192
193 _ => ConstrainResult::Same,
194 }
195 }
196
197 fn each_depending_on<F>(&self, id: ItemId, mut f: F)
198 where
199 F: FnMut(ItemId),
200 {
201 if let Some(edges) = self.dependencies.get(&id) {
202 for item in edges {
203 trace!("enqueue {:?} into worklist", item);
204 f(*item);
205 }
206 }
207 }
208}
209
210impl<'ctx> From<HasVtableAnalysis<'ctx>> for HashMap<ItemId, HasVtableResult> {
211 fn from(analysis: HasVtableAnalysis<'ctx>) -> Self {
212 // We let the lack of an entry mean "No" to save space.
213 extra_assert!(analysis
214 .have_vtable
215 .values()
216 .all(|v| { *v != HasVtableResult::No }));
217
218 analysis.have_vtable
219 }
220}
221
222/// 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.
230 fn has_vtable(&self, ctx: &BindgenContext) -> bool;
231
232 /// Return `true` if this thing has an actual vtable pointer in itself, as
233 /// opposed to transitively in a base member.
234 fn has_vtable_ptr(&self, ctx: &BindgenContext) -> bool;
235}
236