1//! Determining which types has typed parameters in array.
2
3use super::{generate_dependencies, ConstrainResult, MonotoneFramework};
4use crate::ir::comp::Field;
5use crate::ir::comp::FieldMethods;
6use crate::ir::context::{BindgenContext, ItemId};
7use crate::ir::traversal::EdgeKind;
8use crate::ir::ty::TypeKind;
9use crate::{HashMap, HashSet};
10
11/// An analysis that finds for each IR item whether it has array or not.
12///
13/// We use the monotone constraint function `has_type_parameter_in_array`,
14/// defined as follows:
15///
16/// * If T is Array type with type parameter, T trivially has.
17/// * If T is a type alias, a templated alias or an indirection to another type,
18/// it has type parameter in array if the type T refers to has.
19/// * If T is a compound type, it has array if any of base memter or field
20/// has type parameter in array.
21/// * If T is an instantiation of an abstract template definition, T has
22/// type parameter in array if any of the template arguments or template definition
23/// has.
24#[derive(Debug, Clone)]
25pub(crate) struct HasTypeParameterInArray<'ctx> {
26 ctx: &'ctx BindgenContext,
27
28 // The incremental result of this analysis's computation. Everything in this
29 // set has array.
30 has_type_parameter_in_array: HashSet<ItemId>,
31
32 // Dependencies saying that if a key ItemId has been inserted into the
33 // `has_type_parameter_in_array` 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 array or not.
39 dependencies: HashMap<ItemId, Vec<ItemId>>,
40}
41
42impl<'ctx> HasTypeParameterInArray<'ctx> {
43 fn consider_edge(kind: EdgeKind) -> bool {
44 match kind {
45 // These are the only edges that can affect whether a type has type parameter
46 // in array or not.
47 EdgeKind::BaseMember |
48 EdgeKind::Field |
49 EdgeKind::TypeReference |
50 EdgeKind::VarType |
51 EdgeKind::TemplateArgument |
52 EdgeKind::TemplateDeclaration |
53 EdgeKind::TemplateParameterDefinition => true,
54
55 EdgeKind::Constructor |
56 EdgeKind::Destructor |
57 EdgeKind::FunctionReturn |
58 EdgeKind::FunctionParameter |
59 EdgeKind::InnerType |
60 EdgeKind::InnerVar |
61 EdgeKind::Method => false,
62 EdgeKind::Generic => false,
63 }
64 }
65
66 fn insert<Id: Into<ItemId>>(&mut self, id: Id) -> ConstrainResult {
67 let id = id.into();
68 trace!(
69 "inserting {:?} into the has_type_parameter_in_array set",
70 id
71 );
72
73 let was_not_already_in_set =
74 self.has_type_parameter_in_array.insert(id);
75 assert!(
76 was_not_already_in_set,
77 "We shouldn't try and insert {:?} twice because if it was \
78 already in the set, `constrain` should have exited early.",
79 id
80 );
81
82 ConstrainResult::Changed
83 }
84}
85
86impl<'ctx> MonotoneFramework for HasTypeParameterInArray<'ctx> {
87 type Node = ItemId;
88 type Extra = &'ctx BindgenContext;
89 type Output = HashSet<ItemId>;
90
91 fn new(ctx: &'ctx BindgenContext) -> HasTypeParameterInArray<'ctx> {
92 let has_type_parameter_in_array = HashSet::default();
93 let dependencies = generate_dependencies(ctx, Self::consider_edge);
94
95 HasTypeParameterInArray {
96 ctx,
97 has_type_parameter_in_array,
98 dependencies,
99 }
100 }
101
102 fn initial_worklist(&self) -> Vec<ItemId> {
103 self.ctx.allowlisted_items().iter().cloned().collect()
104 }
105
106 fn constrain(&mut self, id: ItemId) -> ConstrainResult {
107 trace!("constrain: {:?}", id);
108
109 if self.has_type_parameter_in_array.contains(&id) {
110 trace!(" already know it do not have array");
111 return ConstrainResult::Same;
112 }
113
114 let item = self.ctx.resolve_item(id);
115 let ty = match item.as_type() {
116 Some(ty) => ty,
117 None => {
118 trace!(" not a type; ignoring");
119 return ConstrainResult::Same;
120 }
121 };
122
123 match *ty.kind() {
124 // Handle the simple cases. These cannot have array in type parameter
125 // without further information.
126 TypeKind::Void |
127 TypeKind::NullPtr |
128 TypeKind::Int(..) |
129 TypeKind::Float(..) |
130 TypeKind::Vector(..) |
131 TypeKind::Complex(..) |
132 TypeKind::Function(..) |
133 TypeKind::Enum(..) |
134 TypeKind::Reference(..) |
135 TypeKind::TypeParam |
136 TypeKind::Opaque |
137 TypeKind::Pointer(..) |
138 TypeKind::UnresolvedTypeRef(..) |
139 TypeKind::ObjCInterface(..) |
140 TypeKind::ObjCId |
141 TypeKind::ObjCSel => {
142 trace!(" simple type that do not have array");
143 ConstrainResult::Same
144 }
145
146 TypeKind::Array(t, _) => {
147 let inner_ty =
148 self.ctx.resolve_type(t).canonical_type(self.ctx);
149 match *inner_ty.kind() {
150 TypeKind::TypeParam => {
151 trace!(" Array with Named type has type parameter");
152 self.insert(id)
153 }
154 _ => {
155 trace!(
156 " Array without Named type does have type parameter"
157 );
158 ConstrainResult::Same
159 }
160 }
161 }
162
163 TypeKind::ResolvedTypeRef(t) |
164 TypeKind::TemplateAlias(t, _) |
165 TypeKind::Alias(t) |
166 TypeKind::BlockPointer(t) => {
167 if self.has_type_parameter_in_array.contains(&t.into()) {
168 trace!(
169 " aliases and type refs to T which have array \
170 also have array"
171 );
172 self.insert(id)
173 } else {
174 trace!(
175 " aliases and type refs to T which do not have array \
176 also do not have array"
177 );
178 ConstrainResult::Same
179 }
180 }
181
182 TypeKind::Comp(ref info) => {
183 let bases_have = info.base_members().iter().any(|base| {
184 self.has_type_parameter_in_array.contains(&base.ty.into())
185 });
186 if bases_have {
187 trace!(" bases have array, so we also have");
188 return self.insert(id);
189 }
190 let fields_have = info.fields().iter().any(|f| match *f {
191 Field::DataMember(ref data) => self
192 .has_type_parameter_in_array
193 .contains(&data.ty().into()),
194 Field::Bitfields(..) => false,
195 });
196 if fields_have {
197 trace!(" fields have array, so we also have");
198 return self.insert(id);
199 }
200
201 trace!(" comp doesn't have array");
202 ConstrainResult::Same
203 }
204
205 TypeKind::TemplateInstantiation(ref template) => {
206 let args_have =
207 template.template_arguments().iter().any(|arg| {
208 self.has_type_parameter_in_array.contains(&arg.into())
209 });
210 if args_have {
211 trace!(
212 " template args have array, so \
213 insantiation also has array"
214 );
215 return self.insert(id);
216 }
217
218 let def_has = self
219 .has_type_parameter_in_array
220 .contains(&template.template_definition().into());
221 if def_has {
222 trace!(
223 " template definition has array, so \
224 insantiation also has"
225 );
226 return self.insert(id);
227 }
228
229 trace!(" template instantiation do not have array");
230 ConstrainResult::Same
231 }
232 }
233 }
234
235 fn each_depending_on<F>(&self, id: ItemId, mut f: F)
236 where
237 F: FnMut(ItemId),
238 {
239 if let Some(edges) = self.dependencies.get(&id) {
240 for item in edges {
241 trace!("enqueue {:?} into worklist", item);
242 f(*item);
243 }
244 }
245 }
246}
247
248impl<'ctx> From<HasTypeParameterInArray<'ctx>> for HashSet<ItemId> {
249 fn from(analysis: HasTypeParameterInArray<'ctx>) -> Self {
250 analysis.has_type_parameter_in_array
251 }
252}
253