1 //! Determining which types have destructors
2 
3 use super::{generate_dependencies, ConstrainResult, MonotoneFramework};
4 use crate::ir::comp::{CompKind, Field, FieldMethods};
5 use crate::ir::context::{BindgenContext, ItemId};
6 use crate::ir::traversal::EdgeKind;
7 use crate::ir::ty::TypeKind;
8 use crate::{HashMap, HashSet};
9 
10 /// An analysis that finds for each IR item whether it has a destructor or not
11 ///
12 /// We use the monotone function `has destructor`, defined as follows:
13 ///
14 /// * If T is a type alias, a templated alias, or an indirection to another type,
15 ///   T has a destructor if the type T refers to has a destructor.
16 /// * If T is a compound type, T has a destructor if we saw a destructor when parsing it,
17 ///   or if it's a struct, T has a destructor if any of its base members has a destructor,
18 ///   or if any of its fields have a destructor.
19 /// * If T is an instantiation of an abstract template definition, T has
20 ///   a destructor if its template definition has a destructor,
21 ///   or if any of the template arguments has a destructor.
22 /// * If T is the type of a field, that field has a destructor if it's not a bitfield,
23 ///   and if T has a destructor.
24 #[derive(Debug, Clone)]
25 pub(crate) struct HasDestructorAnalysis<'ctx> {
26     ctx: &'ctx BindgenContext,
27 
28     // The incremental result of this analysis's computation. Everything in this
29     // set definitely has a destructor.
30     have_destructor: HashSet<ItemId>,
31 
32     // Dependencies saying that if a key ItemId has been inserted into the
33     // `have_destructor` set, then each of the ids in Vec<ItemId> need to be
34     // considered again.
35     //
36     // This is a subset of the natural IR graph with reversed edges, where we
37     // only include the edges from the IR graph that can affect whether a type
38     // has a destructor or not.
39     dependencies: HashMap<ItemId, Vec<ItemId>>,
40 }
41 
42 impl<'ctx> HasDestructorAnalysis<'ctx> {
consider_edge(kind: EdgeKind) -> bool43     fn consider_edge(kind: EdgeKind) -> bool {
44         // These are the only edges that can affect whether a type has a
45         // destructor or not.
46         matches!(
47             kind,
48             EdgeKind::TypeReference |
49                 EdgeKind::BaseMember |
50                 EdgeKind::Field |
51                 EdgeKind::TemplateArgument |
52                 EdgeKind::TemplateDeclaration
53         )
54     }
55 
insert<Id: Into<ItemId>>(&mut self, id: Id) -> ConstrainResult56     fn insert<Id: Into<ItemId>>(&mut self, id: Id) -> ConstrainResult {
57         let id = id.into();
58         let was_not_already_in_set = self.have_destructor.insert(id);
59         assert!(
60             was_not_already_in_set,
61             "We shouldn't try and insert {:?} twice because if it was \
62              already in the set, `constrain` should have exited early.",
63             id
64         );
65         ConstrainResult::Changed
66     }
67 }
68 
69 impl<'ctx> MonotoneFramework for HasDestructorAnalysis<'ctx> {
70     type Node = ItemId;
71     type Extra = &'ctx BindgenContext;
72     type Output = HashSet<ItemId>;
73 
new(ctx: &'ctx BindgenContext) -> Self74     fn new(ctx: &'ctx BindgenContext) -> Self {
75         let have_destructor = HashSet::default();
76         let dependencies = generate_dependencies(ctx, Self::consider_edge);
77 
78         HasDestructorAnalysis {
79             ctx,
80             have_destructor,
81             dependencies,
82         }
83     }
84 
initial_worklist(&self) -> Vec<ItemId>85     fn initial_worklist(&self) -> Vec<ItemId> {
86         self.ctx.allowlisted_items().iter().cloned().collect()
87     }
88 
constrain(&mut self, id: ItemId) -> ConstrainResult89     fn constrain(&mut self, id: ItemId) -> ConstrainResult {
90         if self.have_destructor.contains(&id) {
91             // We've already computed that this type has a destructor and that can't
92             // change.
93             return ConstrainResult::Same;
94         }
95 
96         let item = self.ctx.resolve_item(id);
97         let ty = match item.as_type() {
98             None => return ConstrainResult::Same,
99             Some(ty) => ty,
100         };
101 
102         match *ty.kind() {
103             TypeKind::TemplateAlias(t, _) |
104             TypeKind::Alias(t) |
105             TypeKind::ResolvedTypeRef(t) => {
106                 if self.have_destructor.contains(&t.into()) {
107                     self.insert(id)
108                 } else {
109                     ConstrainResult::Same
110                 }
111             }
112 
113             TypeKind::Comp(ref info) => {
114                 if info.has_own_destructor() {
115                     return self.insert(id);
116                 }
117 
118                 match info.kind() {
119                     CompKind::Union => ConstrainResult::Same,
120                     CompKind::Struct => {
121                         let base_or_field_destructor =
122                             info.base_members().iter().any(|base| {
123                                 self.have_destructor.contains(&base.ty.into())
124                             }) || info.fields().iter().any(
125                                 |field| match *field {
126                                     Field::DataMember(ref data) => self
127                                         .have_destructor
128                                         .contains(&data.ty().into()),
129                                     Field::Bitfields(_) => false,
130                                 },
131                             );
132                         if base_or_field_destructor {
133                             self.insert(id)
134                         } else {
135                             ConstrainResult::Same
136                         }
137                     }
138                 }
139             }
140 
141             TypeKind::TemplateInstantiation(ref inst) => {
142                 let definition_or_arg_destructor = self
143                     .have_destructor
144                     .contains(&inst.template_definition().into()) ||
145                     inst.template_arguments().iter().any(|arg| {
146                         self.have_destructor.contains(&arg.into())
147                     });
148                 if definition_or_arg_destructor {
149                     self.insert(id)
150                 } else {
151                     ConstrainResult::Same
152                 }
153             }
154 
155             _ => ConstrainResult::Same,
156         }
157     }
158 
each_depending_on<F>(&self, id: ItemId, mut f: F) where F: FnMut(ItemId),159     fn each_depending_on<F>(&self, id: ItemId, mut f: F)
160     where
161         F: FnMut(ItemId),
162     {
163         if let Some(edges) = self.dependencies.get(&id) {
164             for item in edges {
165                 trace!("enqueue {:?} into worklist", item);
166                 f(*item);
167             }
168         }
169     }
170 }
171 
172 impl<'ctx> From<HasDestructorAnalysis<'ctx>> for HashSet<ItemId> {
from(analysis: HasDestructorAnalysis<'ctx>) -> Self173     fn from(analysis: HasDestructorAnalysis<'ctx>) -> Self {
174         analysis.have_destructor
175     }
176 }
177