1use std::cmp::Ordering;
2
3use crate::hierarchy::{TypeHierarchy, common_supertype};
4use crate::{ClassName, IntegralTypeSet, PrimitiveType, TypeDescriptor};
5
6#[derive(Debug, Clone, PartialEq, Eq, Hash)]
11pub enum ReferenceType {
12 Exact(ClassName),
18 Array(TypeDescriptor),
20 Null,
22 Unknown,
24}
25
26impl ReferenceType {
27 #[must_use]
29 pub const fn exact(class_name: ClassName) -> Self {
30 Self::Exact(class_name)
31 }
32
33 fn join(&self, other: &Self, hierarchy: Option<&dyn TypeHierarchy>) -> Option<Self> {
34 match (self, other) {
35 (Self::Null, reference) | (reference, Self::Null) => Some(reference.clone()),
36 (Self::Unknown, _) | (_, Self::Unknown) => Some(Self::Unknown),
37 (Self::Exact(left), Self::Exact(right)) if left == right => {
38 Some(Self::Exact(left.clone()))
39 }
40 (Self::Array(left), Self::Array(right)) if left == right => {
41 Some(Self::Array(left.clone()))
42 }
43 (Self::Exact(left), Self::Exact(right)) => {
44 common_supertype(hierarchy, left, right).map(Self::Exact)
45 }
46 (Self::Array(_), Self::Exact(name)) | (Self::Exact(name), Self::Array(_))
47 if matches!(
48 name.as_str(),
49 "java/lang/Object" | "java/lang/Cloneable" | "java/io/Serializable"
50 ) =>
51 {
52 Some(Self::Exact(name.clone()))
53 }
54 _ => None,
55 }
56 }
57}
58
59#[derive(Debug, Clone, PartialEq, Eq, Hash)]
65pub enum InferredType {
66 Bottom,
68 Int,
70 Integral(IntegralTypeSet),
72 Float,
74 Long,
76 Double,
78 Reference(ReferenceType),
80 Uninitialized {
82 class_name: ClassName,
84 allocation_offset: u16,
86 },
87 UninitializedThis {
90 class_name: ClassName,
92 },
93 ReturnAddress,
95 Alternatives(Vec<InferredType>),
101 Conflict,
103}
104
105#[must_use]
107pub(crate) fn join_local_types(
108 left: &InferredType,
109 right: &InferredType,
110 hierarchy: Option<&dyn TypeHierarchy>,
111) -> InferredType {
112 let joined = left.join_with_hierarchy(right, hierarchy);
113 if !matches!(joined, InferredType::Conflict) {
114 return joined;
115 }
116
117 let mut alternatives = Vec::new();
118 append_alternatives(&mut alternatives, left);
119 append_alternatives(&mut alternatives, right);
120 alternatives.sort_by(compare_inferred_types);
121 InferredType::Alternatives(alternatives)
122}
123
124fn append_alternatives(destination: &mut Vec<InferredType>, value: &InferredType) {
125 match value {
126 InferredType::Alternatives(values) => {
127 for value in values {
128 append_alternatives(destination, value);
129 }
130 }
131 value if !destination.contains(value) => destination.push(value.clone()),
132 _ => {}
133 }
134}
135
136fn reference_alternatives(value: &InferredType) -> Option<Vec<ReferenceType>> {
137 match value {
138 InferredType::Reference(reference) => Some(vec![reference.clone()]),
139 InferredType::Alternatives(values) => values
140 .iter()
141 .map(|value| match value {
142 InferredType::Reference(reference) => Some(reference.clone()),
143 _ => None,
144 })
145 .collect(),
146 _ => None,
147 }
148}
149
150fn join_reference_alternatives(
151 left: &[ReferenceType],
152 right: &[ReferenceType],
153 hierarchy: Option<&dyn TypeHierarchy>,
154) -> InferredType {
155 let mut references = left.iter().chain(right).cloned().collect::<Vec<_>>();
156
157 if references.contains(&ReferenceType::Unknown) {
158 return InferredType::Reference(ReferenceType::Unknown);
159 }
160
161 if references.len() > 1 {
162 references.retain(|reference| *reference != ReferenceType::Null);
163 }
164 references.sort_by(compare_references);
165 references.dedup();
166
167 let Some(first) = references.first().cloned() else {
168 return InferredType::Reference(ReferenceType::Null);
169 };
170 if references.len() == 1 {
171 return InferredType::Reference(first);
172 }
173
174 let common = references
175 .iter()
176 .skip(1)
177 .try_fold(first.clone(), |common, reference| {
178 common.join(reference, hierarchy)
179 });
180 if let Some(common) = common {
181 return InferredType::Reference(common);
182 }
183
184 InferredType::Alternatives(
185 references
186 .into_iter()
187 .map(InferredType::Reference)
188 .collect(),
189 )
190}
191
192fn compare_inferred_types(left: &InferredType, right: &InferredType) -> Ordering {
193 let rank = |value: &InferredType| match value {
194 InferredType::Bottom => 0,
195 InferredType::Int => 1,
196 InferredType::Integral(_) => 2,
197 InferredType::Float => 3,
198 InferredType::Long => 4,
199 InferredType::Double => 5,
200 InferredType::Reference(_) => 6,
201 InferredType::Uninitialized { .. } => 7,
202 InferredType::UninitializedThis { .. } => 8,
203 InferredType::ReturnAddress => 9,
204 InferredType::Alternatives(_) => 10,
205 InferredType::Conflict => 11,
206 };
207 rank(left)
208 .cmp(&rank(right))
209 .then_with(|| match (left, right) {
210 (InferredType::Integral(left), InferredType::Integral(right)) => left.cmp(right),
211 (InferredType::Reference(left), InferredType::Reference(right)) => {
212 compare_references(left, right)
213 }
214 (
215 InferredType::Uninitialized {
216 class_name: left_name,
217 allocation_offset: left_offset,
218 },
219 InferredType::Uninitialized {
220 class_name: right_name,
221 allocation_offset: right_offset,
222 },
223 ) => left_name
224 .cmp(right_name)
225 .then(left_offset.cmp(right_offset)),
226 (
227 InferredType::UninitializedThis {
228 class_name: left_name,
229 },
230 InferredType::UninitializedThis {
231 class_name: right_name,
232 },
233 ) => left_name.cmp(right_name),
234 (InferredType::Alternatives(left), InferredType::Alternatives(right)) => left
235 .iter()
236 .zip(right)
237 .map(|(left, right)| compare_inferred_types(left, right))
238 .find(|comparison| !comparison.is_eq())
239 .unwrap_or_else(|| left.len().cmp(&right.len())),
240 _ => Ordering::Equal,
241 })
242}
243
244fn compare_references(left: &ReferenceType, right: &ReferenceType) -> Ordering {
245 let rank = |value: &ReferenceType| match value {
246 ReferenceType::Exact(_) => 0,
247 ReferenceType::Array(_) => 1,
248 ReferenceType::Null => 2,
249 ReferenceType::Unknown => 3,
250 };
251 rank(left)
252 .cmp(&rank(right))
253 .then_with(|| match (left, right) {
254 (ReferenceType::Exact(left), ReferenceType::Exact(right)) => left.cmp(right),
255 (ReferenceType::Array(left), ReferenceType::Array(right)) => {
256 compare_descriptors(left, right)
257 }
258 _ => Ordering::Equal,
259 })
260}
261
262fn compare_descriptors(left: &TypeDescriptor, right: &TypeDescriptor) -> Ordering {
263 let rank = |value: &TypeDescriptor| match value {
264 TypeDescriptor::Primitive(_) => 0,
265 TypeDescriptor::Reference(_) => 1,
266 TypeDescriptor::Array { .. } => 2,
267 };
268 rank(left)
269 .cmp(&rank(right))
270 .then_with(|| match (left, right) {
271 (TypeDescriptor::Primitive(left), TypeDescriptor::Primitive(right)) => {
272 primitive_rank(*left).cmp(&primitive_rank(*right))
273 }
274 (TypeDescriptor::Reference(left), TypeDescriptor::Reference(right)) => left.cmp(right),
275 (
276 TypeDescriptor::Array {
277 dimensions: left_dimensions,
278 element: left_element,
279 },
280 TypeDescriptor::Array {
281 dimensions: right_dimensions,
282 element: right_element,
283 },
284 ) => left_dimensions
285 .cmp(right_dimensions)
286 .then_with(|| compare_descriptors(left_element, right_element)),
287 _ => Ordering::Equal,
288 })
289}
290
291const fn primitive_rank(value: PrimitiveType) -> u8 {
292 match value {
293 PrimitiveType::Boolean => 0,
294 PrimitiveType::Byte => 1,
295 PrimitiveType::Char => 2,
296 PrimitiveType::Short => 3,
297 PrimitiveType::Int => 4,
298 PrimitiveType::Float => 5,
299 PrimitiveType::Long => 6,
300 PrimitiveType::Double => 7,
301 }
302}
303
304impl InferredType {
305 #[must_use]
311 pub const fn integral_types(&self) -> Option<IntegralTypeSet> {
312 match self {
313 Self::Int => Some(IntegralTypeSet::INT),
314 Self::Integral(types) => Some(*types),
315 _ => None,
316 }
317 }
318
319 pub(crate) fn from_integral_types(types: IntegralTypeSet) -> Self {
320 if types == IntegralTypeSet::INT {
321 Self::Int
322 } else {
323 Self::Integral(types)
324 }
325 }
326
327 #[must_use]
334 pub fn join(&self, other: &Self) -> Self {
335 self.join_with_hierarchy(other, None)
336 }
337
338 pub(crate) fn join_with_hierarchy(
339 &self,
340 other: &Self,
341 hierarchy: Option<&dyn TypeHierarchy>,
342 ) -> Self {
343 if let (Some(left), Some(right)) =
344 (reference_alternatives(self), reference_alternatives(other))
345 {
346 return join_reference_alternatives(&left, &right, hierarchy);
347 }
348
349 if let (Some(left), Some(right)) = (self.integral_types(), other.integral_types()) {
350 return Self::from_integral_types(left.union(right));
351 }
352
353 match (self, other) {
354 (Self::Bottom, value) | (value, Self::Bottom) => value.clone(),
355 (Self::Int, Self::Int)
356 | (Self::Float, Self::Float)
357 | (Self::Long, Self::Long)
358 | (Self::Double, Self::Double)
359 | (Self::ReturnAddress, Self::ReturnAddress)
360 | (Self::Conflict, Self::Conflict) => self.clone(),
361 (
362 Self::Uninitialized {
363 class_name: left_name,
364 allocation_offset: left_offset,
365 },
366 Self::Uninitialized {
367 class_name: right_name,
368 allocation_offset: right_offset,
369 },
370 ) if left_name == right_name && left_offset == right_offset => self.clone(),
371 (
372 Self::UninitializedThis {
373 class_name: left_name,
374 },
375 Self::UninitializedThis {
376 class_name: right_name,
377 },
378 ) if left_name == right_name => self.clone(),
379 _ => Self::Conflict,
380 }
381 }
382}