use std::cmp::Ordering;
use crate::hierarchy::{TypeHierarchy, common_supertype};
use crate::{ClassName, IntegralTypeSet, PrimitiveType, TypeDescriptor};
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum ReferenceType {
Exact(ClassName),
Array(TypeDescriptor),
Null,
Unknown,
}
impl ReferenceType {
#[must_use]
pub const fn exact(class_name: ClassName) -> Self {
Self::Exact(class_name)
}
fn join(&self, other: &Self, hierarchy: Option<&dyn TypeHierarchy>) -> Option<Self> {
match (self, other) {
(Self::Null, reference) | (reference, Self::Null) => Some(reference.clone()),
(Self::Unknown, _) | (_, Self::Unknown) => Some(Self::Unknown),
(Self::Exact(left), Self::Exact(right)) if left == right => {
Some(Self::Exact(left.clone()))
}
(Self::Array(left), Self::Array(right)) if left == right => {
Some(Self::Array(left.clone()))
}
(Self::Exact(left), Self::Exact(right)) => {
common_supertype(hierarchy, left, right).map(Self::Exact)
}
(Self::Array(_), Self::Exact(name)) | (Self::Exact(name), Self::Array(_))
if matches!(
name.as_str(),
"java/lang/Object" | "java/lang/Cloneable" | "java/io/Serializable"
) =>
{
Some(Self::Exact(name.clone()))
}
_ => None,
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum InferredType {
Bottom,
Int,
Integral(IntegralTypeSet),
Float,
Long,
Double,
Reference(ReferenceType),
Uninitialized {
class_name: ClassName,
allocation_offset: u16,
},
UninitializedThis {
class_name: ClassName,
},
ReturnAddress,
Alternatives(Vec<InferredType>),
Conflict,
}
#[must_use]
pub(crate) fn join_local_types(
left: &InferredType,
right: &InferredType,
hierarchy: Option<&dyn TypeHierarchy>,
) -> InferredType {
let joined = left.join_with_hierarchy(right, hierarchy);
if !matches!(joined, InferredType::Conflict) {
return joined;
}
let mut alternatives = Vec::new();
append_alternatives(&mut alternatives, left);
append_alternatives(&mut alternatives, right);
alternatives.sort_by(compare_inferred_types);
InferredType::Alternatives(alternatives)
}
fn append_alternatives(destination: &mut Vec<InferredType>, value: &InferredType) {
match value {
InferredType::Alternatives(values) => {
for value in values {
append_alternatives(destination, value);
}
}
value if !destination.contains(value) => destination.push(value.clone()),
_ => {}
}
}
fn reference_alternatives(value: &InferredType) -> Option<Vec<ReferenceType>> {
match value {
InferredType::Reference(reference) => Some(vec![reference.clone()]),
InferredType::Alternatives(values) => values
.iter()
.map(|value| match value {
InferredType::Reference(reference) => Some(reference.clone()),
_ => None,
})
.collect(),
_ => None,
}
}
fn join_reference_alternatives(
left: &[ReferenceType],
right: &[ReferenceType],
hierarchy: Option<&dyn TypeHierarchy>,
) -> InferredType {
let mut references = left.iter().chain(right).cloned().collect::<Vec<_>>();
if references.contains(&ReferenceType::Unknown) {
return InferredType::Reference(ReferenceType::Unknown);
}
if references.len() > 1 {
references.retain(|reference| *reference != ReferenceType::Null);
}
references.sort_by(compare_references);
references.dedup();
let Some(first) = references.first().cloned() else {
return InferredType::Reference(ReferenceType::Null);
};
if references.len() == 1 {
return InferredType::Reference(first);
}
let common = references
.iter()
.skip(1)
.try_fold(first.clone(), |common, reference| {
common.join(reference, hierarchy)
});
if let Some(common) = common {
return InferredType::Reference(common);
}
InferredType::Alternatives(
references
.into_iter()
.map(InferredType::Reference)
.collect(),
)
}
fn compare_inferred_types(left: &InferredType, right: &InferredType) -> Ordering {
let rank = |value: &InferredType| match value {
InferredType::Bottom => 0,
InferredType::Int => 1,
InferredType::Integral(_) => 2,
InferredType::Float => 3,
InferredType::Long => 4,
InferredType::Double => 5,
InferredType::Reference(_) => 6,
InferredType::Uninitialized { .. } => 7,
InferredType::UninitializedThis { .. } => 8,
InferredType::ReturnAddress => 9,
InferredType::Alternatives(_) => 10,
InferredType::Conflict => 11,
};
rank(left)
.cmp(&rank(right))
.then_with(|| match (left, right) {
(InferredType::Integral(left), InferredType::Integral(right)) => left.cmp(right),
(InferredType::Reference(left), InferredType::Reference(right)) => {
compare_references(left, right)
}
(
InferredType::Uninitialized {
class_name: left_name,
allocation_offset: left_offset,
},
InferredType::Uninitialized {
class_name: right_name,
allocation_offset: right_offset,
},
) => left_name
.cmp(right_name)
.then(left_offset.cmp(right_offset)),
(
InferredType::UninitializedThis {
class_name: left_name,
},
InferredType::UninitializedThis {
class_name: right_name,
},
) => left_name.cmp(right_name),
(InferredType::Alternatives(left), InferredType::Alternatives(right)) => left
.iter()
.zip(right)
.map(|(left, right)| compare_inferred_types(left, right))
.find(|comparison| !comparison.is_eq())
.unwrap_or_else(|| left.len().cmp(&right.len())),
_ => Ordering::Equal,
})
}
fn compare_references(left: &ReferenceType, right: &ReferenceType) -> Ordering {
let rank = |value: &ReferenceType| match value {
ReferenceType::Exact(_) => 0,
ReferenceType::Array(_) => 1,
ReferenceType::Null => 2,
ReferenceType::Unknown => 3,
};
rank(left)
.cmp(&rank(right))
.then_with(|| match (left, right) {
(ReferenceType::Exact(left), ReferenceType::Exact(right)) => left.cmp(right),
(ReferenceType::Array(left), ReferenceType::Array(right)) => {
compare_descriptors(left, right)
}
_ => Ordering::Equal,
})
}
fn compare_descriptors(left: &TypeDescriptor, right: &TypeDescriptor) -> Ordering {
let rank = |value: &TypeDescriptor| match value {
TypeDescriptor::Primitive(_) => 0,
TypeDescriptor::Reference(_) => 1,
TypeDescriptor::Array { .. } => 2,
};
rank(left)
.cmp(&rank(right))
.then_with(|| match (left, right) {
(TypeDescriptor::Primitive(left), TypeDescriptor::Primitive(right)) => {
primitive_rank(*left).cmp(&primitive_rank(*right))
}
(TypeDescriptor::Reference(left), TypeDescriptor::Reference(right)) => left.cmp(right),
(
TypeDescriptor::Array {
dimensions: left_dimensions,
element: left_element,
},
TypeDescriptor::Array {
dimensions: right_dimensions,
element: right_element,
},
) => left_dimensions
.cmp(right_dimensions)
.then_with(|| compare_descriptors(left_element, right_element)),
_ => Ordering::Equal,
})
}
const fn primitive_rank(value: PrimitiveType) -> u8 {
match value {
PrimitiveType::Boolean => 0,
PrimitiveType::Byte => 1,
PrimitiveType::Char => 2,
PrimitiveType::Short => 3,
PrimitiveType::Int => 4,
PrimitiveType::Float => 5,
PrimitiveType::Long => 6,
PrimitiveType::Double => 7,
}
}
impl InferredType {
#[must_use]
pub const fn integral_types(&self) -> Option<IntegralTypeSet> {
match self {
Self::Int => Some(IntegralTypeSet::INT),
Self::Integral(types) => Some(*types),
_ => None,
}
}
pub(crate) fn from_integral_types(types: IntegralTypeSet) -> Self {
if types == IntegralTypeSet::INT {
Self::Int
} else {
Self::Integral(types)
}
}
#[must_use]
pub fn join(&self, other: &Self) -> Self {
self.join_with_hierarchy(other, None)
}
pub(crate) fn join_with_hierarchy(
&self,
other: &Self,
hierarchy: Option<&dyn TypeHierarchy>,
) -> Self {
if let (Some(left), Some(right)) =
(reference_alternatives(self), reference_alternatives(other))
{
return join_reference_alternatives(&left, &right, hierarchy);
}
if let (Some(left), Some(right)) = (self.integral_types(), other.integral_types()) {
return Self::from_integral_types(left.union(right));
}
match (self, other) {
(Self::Bottom, value) | (value, Self::Bottom) => value.clone(),
(Self::Int, Self::Int)
| (Self::Float, Self::Float)
| (Self::Long, Self::Long)
| (Self::Double, Self::Double)
| (Self::ReturnAddress, Self::ReturnAddress)
| (Self::Conflict, Self::Conflict) => self.clone(),
(
Self::Uninitialized {
class_name: left_name,
allocation_offset: left_offset,
},
Self::Uninitialized {
class_name: right_name,
allocation_offset: right_offset,
},
) if left_name == right_name && left_offset == right_offset => self.clone(),
(
Self::UninitializedThis {
class_name: left_name,
},
Self::UninitializedThis {
class_name: right_name,
},
) if left_name == right_name => self.clone(),
_ => Self::Conflict,
}
}
}