Skip to main content

ferro_jtype/types/
inference.rs

1use std::cmp::Ordering;
2
3use crate::hierarchy::{TypeHierarchy, common_supertype};
4use crate::{ClassName, IntegralTypeSet, PrimitiveType, TypeDescriptor};
5
6/// Inferred state for a JVM reference value.
7///
8/// [`Self::Unknown`] is reserved for values whose class bytes do not supply
9/// enough information to establish a reference type.
10#[derive(Debug, Clone, PartialEq, Eq, Hash)]
11pub enum ReferenceType {
12    /// A reference whose bytecode supplies this static class type.
13    ///
14    /// This is not a claim about the object's exact runtime subclass. For
15    /// example, an `Object`-returning method still has this static type when
16    /// its implementation happens to return a `String`.
17    Exact(ClassName),
18    /// A reference known to be an array of the described type.
19    Array(TypeDescriptor),
20    /// The JVM `null` value.
21    Null,
22    /// A reference whose precise type could not be preserved.
23    Unknown,
24}
25
26impl ReferenceType {
27    /// Creates an exact reference type for `class_name`.
28    #[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/// Abstract JVM type inferred for a local variable or operand-stack value.
60///
61/// `boolean`, `byte`, `char`, `short`, and `int` share the integral JVM
62/// verification category. [`Self::Integral`] retains source-level candidates
63/// when bytecode supplies evidence more precise than that category.
64#[derive(Debug, Clone, PartialEq, Eq, Hash)]
65pub enum InferredType {
66    /// No control-flow path has supplied a value for this position yet.
67    Bottom,
68    /// A JVM integral value with exact `int` evidence.
69    Int,
70    /// A JVM integral value with one or more compatible source-level candidates.
71    Integral(IntegralTypeSet),
72    /// A category-one JVM floating-point value.
73    Float,
74    /// A category-two JVM integral value.
75    Long,
76    /// A category-two JVM floating-point value.
77    Double,
78    /// A JVM reference value.
79    Reference(ReferenceType),
80    /// An object produced by `new` before its constructor has completed.
81    Uninitialized {
82        /// Class allocated by the `new` instruction.
83        class_name: ClassName,
84        /// Bytecode offset of the allocation instruction.
85        allocation_offset: u16,
86    },
87    /// The receiver of an instance constructor before its parent constructor
88    /// has completed.
89    UninitializedThis {
90        /// Class whose constructor owns this receiver.
91        class_name: ClassName,
92    },
93    /// A return address used by legacy `jsr` and `ret` bytecode.
94    ReturnAddress,
95    /// Distinct possible types observed for one value.
96    ///
97    /// Reference alternatives preserve known candidates at a control-flow merge
98    /// when no supplied hierarchy proves a common supertype. Alternatives may
99    /// also describe a reused local-variable slot.
100    Alternatives(Vec<InferredType>),
101    /// Incompatible values reached the same control-flow position.
102    Conflict,
103}
104
105/// Joins local-variable types while preserving independent slot lifetimes.
106#[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    /// Returns source-level candidates for an integral JVM value.
306    ///
307    /// `None` means this value is not in the integral JVM verification
308    /// category. [`IntegralTypeSet::ALL`] means the bytecode did not preserve a
309    /// unique source-level type.
310    #[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    /// Conservatively joins two types at a control-flow merge point.
328    ///
329    /// Compatible values preserve their type. Incompatible primitive or
330    /// uninitialized values become [`Self::Conflict`]. Incompatible known
331    /// references become [`Self::Alternatives`] unless a supplied hierarchy
332    /// proves their common supertype.
333    #[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}