bindgen/ir/analysis/
has_type_param_in_array.rs

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 HasTypeParameterInArray<'_> {
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 |
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!("inserting {id:?} into the has_type_parameter_in_array set");
69
70        let was_not_already_in_set =
71            self.has_type_parameter_in_array.insert(id);
72        assert!(
73            was_not_already_in_set,
74            "We shouldn't try and insert {id:?} twice because if it was \
75             already in the set, `constrain` should have exited early."
76        );
77
78        ConstrainResult::Changed
79    }
80}
81
82impl<'ctx> MonotoneFramework for HasTypeParameterInArray<'ctx> {
83    type Node = ItemId;
84    type Extra = &'ctx BindgenContext;
85    type Output = HashSet<ItemId>;
86
87    fn new(ctx: &'ctx BindgenContext) -> HasTypeParameterInArray<'ctx> {
88        let has_type_parameter_in_array = HashSet::default();
89        let dependencies = generate_dependencies(ctx, Self::consider_edge);
90
91        HasTypeParameterInArray {
92            ctx,
93            has_type_parameter_in_array,
94            dependencies,
95        }
96    }
97
98    fn initial_worklist(&self) -> Vec<ItemId> {
99        self.ctx.allowlisted_items().iter().copied().collect()
100    }
101
102    fn constrain(&mut self, id: ItemId) -> ConstrainResult {
103        trace!("constrain: {id:?}");
104
105        if self.has_type_parameter_in_array.contains(&id) {
106            trace!("    already know it do not have array");
107            return ConstrainResult::Same;
108        }
109
110        let item = self.ctx.resolve_item(id);
111        let Some(ty) = item.as_type() else {
112            trace!("    not a type; ignoring");
113            return ConstrainResult::Same;
114        };
115
116        match *ty.kind() {
117            // Handle the simple cases. These cannot have array in type parameter
118            // without further information.
119            TypeKind::Void |
120            TypeKind::NullPtr |
121            TypeKind::Int(..) |
122            TypeKind::Float(..) |
123            TypeKind::Vector(..) |
124            TypeKind::Complex(..) |
125            TypeKind::Function(..) |
126            TypeKind::Enum(..) |
127            TypeKind::Reference(..) |
128            TypeKind::TypeParam |
129            TypeKind::Opaque |
130            TypeKind::Pointer(..) |
131            TypeKind::UnresolvedTypeRef(..) |
132            TypeKind::ObjCInterface(..) |
133            TypeKind::ObjCId |
134            TypeKind::ObjCSel => {
135                trace!("    simple type that do not have array");
136                ConstrainResult::Same
137            }
138
139            TypeKind::Array(t, _) => {
140                let inner_ty =
141                    self.ctx.resolve_type(t).canonical_type(self.ctx);
142                if let TypeKind::TypeParam = *inner_ty.kind() {
143                    trace!("    Array with Named type has type parameter");
144                    self.insert(id)
145                } else {
146                    trace!(
147                        "    Array without Named type does have type parameter"
148                    );
149                    ConstrainResult::Same
150                }
151            }
152
153            TypeKind::ResolvedTypeRef(t) |
154            TypeKind::TemplateAlias(t, _) |
155            TypeKind::Alias(t) |
156            TypeKind::BlockPointer(t) => {
157                if self.has_type_parameter_in_array.contains(&t.into()) {
158                    trace!(
159                        "    aliases and type refs to T which have array \
160                         also have array"
161                    );
162                    self.insert(id)
163                } else {
164                    trace!(
165                        "    aliases and type refs to T which do not have array \
166                            also do not have array"
167                    );
168                    ConstrainResult::Same
169                }
170            }
171
172            TypeKind::Comp(ref info) => {
173                let bases_have = info.base_members().iter().any(|base| {
174                    self.has_type_parameter_in_array.contains(&base.ty.into())
175                });
176                if bases_have {
177                    trace!("    bases have array, so we also have");
178                    return self.insert(id);
179                }
180                let fields_have = info.fields().iter().any(|f| match *f {
181                    Field::DataMember(ref data) => self
182                        .has_type_parameter_in_array
183                        .contains(&data.ty().into()),
184                    Field::Bitfields(..) => false,
185                });
186                if fields_have {
187                    trace!("    fields have array, so we also have");
188                    return self.insert(id);
189                }
190
191                trace!("    comp doesn't have array");
192                ConstrainResult::Same
193            }
194
195            TypeKind::TemplateInstantiation(ref template) => {
196                let args_have =
197                    template.template_arguments().iter().any(|arg| {
198                        self.has_type_parameter_in_array.contains(&arg.into())
199                    });
200                if args_have {
201                    trace!(
202                        "    template args have array, so \
203                         instantiation also has array"
204                    );
205                    return self.insert(id);
206                }
207
208                let def_has = self
209                    .has_type_parameter_in_array
210                    .contains(&template.template_definition().into());
211                if def_has {
212                    trace!(
213                        "    template definition has array, so \
214                         instantiation also has"
215                    );
216                    return self.insert(id);
217                }
218
219                trace!("    template instantiation do not have array");
220                ConstrainResult::Same
221            }
222        }
223    }
224
225    fn each_depending_on<F>(&self, id: ItemId, mut f: F)
226    where
227        F: FnMut(ItemId),
228    {
229        if let Some(edges) = self.dependencies.get(&id) {
230            for item in edges {
231                trace!("enqueue {item:?} into worklist");
232                f(*item);
233            }
234        }
235    }
236}
237
238impl<'ctx> From<HasTypeParameterInArray<'ctx>> for HashSet<ItemId> {
239    fn from(analysis: HasTypeParameterInArray<'ctx>) -> Self {
240        analysis.has_type_parameter_in_array
241    }
242}
bindgen/ir/analysis/has_type_param_in_array.rs

bindgen/ir/analysis/
has_type_param_in_array.rs
