bindgen/ir/analysis/
has_vtable.rs

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, 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 HasVtableAnalysis<'_> {
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) {
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().copied().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 {item:?} into worklist");
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}
bindgen/ir/analysis/has_vtable.rs

bindgen/ir/analysis/
has_vtable.rs
