ferro-jtype 0.2.8

Type inference for Java class bytecode without JDK symbols
Documentation
use std::collections::{HashMap, HashSet, VecDeque};

use crate::cfg::{BlockId, ControlFlowGraph, EdgeKind, ExceptionEdge};
use crate::ir::{InstructionIr, InstructionOperandIr, MethodIr};
use crate::solver::frame::Frame;
use crate::{
    Diagnostic, DiagnosticKind, DiagnosticLocation, DiagnosticSeverity, InferredType,
    ReferenceType, TypeHierarchy,
};
use rust_asm::opcodes as op;

pub(super) const fn instruction_may_throw(opcode: u8) -> bool {
    matches!(
        opcode,
        op::LDC..=op::LDC2_W
            | op::IALOAD..=op::SALOAD
            | op::IASTORE..=op::SASTORE
            | op::IDIV
            | op::LDIV
            | op::IREM
            | op::LREM
            | op::GETSTATIC..=op::INVOKEDYNAMIC
            | op::NEW..=op::MONITOREXIT
            | op::MULTIANEWARRAY
    )
}

#[derive(Debug, Clone)]
pub(super) enum BranchFact {
    InstanceOf(crate::solver::frame::InstanceOfFact),
    Null(bool),
}

pub(super) fn branch_fact(opcode: u8, frame: &Frame) -> Option<BranchFact> {
    match opcode {
        op::IFEQ | op::IFNE => frame.top_instanceof_fact().map(BranchFact::InstanceOf),
        op::IFNULL | op::IFNONNULL => {
            known_nullness(frame.top_value()?.value).map(BranchFact::Null)
        }
        _ => None,
    }
}

fn known_nullness(value: InferredType) -> Option<bool> {
    match value {
        InferredType::Reference(ReferenceType::Null) => Some(true),
        InferredType::Uninitialized { .. } | InferredType::UninitializedThis { .. } => Some(false),
        InferredType::Bottom
        | InferredType::Int
        | InferredType::Integral(_)
        | InferredType::Float
        | InferredType::Long
        | InferredType::Double
        | InferredType::Reference(
            ReferenceType::Exact(_) | ReferenceType::Array(_) | ReferenceType::Unknown,
        )
        | InferredType::ReturnAddress
        | InferredType::Alternatives(_)
        | InferredType::Conflict => None,
    }
}

pub(super) fn branch_edge_is_feasible(
    opcode: u8,
    edge_kind: &EdgeKind,
    fact: Option<&BranchFact>,
) -> bool {
    let Some(BranchFact::Null(is_null)) = fact else {
        return true;
    };
    let branch_taken = matches!(edge_kind, EdgeKind::Branch);
    match opcode {
        op::IFNULL => branch_taken == *is_null,
        op::IFNONNULL => branch_taken != *is_null,
        _ => true,
    }
}

pub(super) const fn instanceof_true_edge(opcode: u8, edge_kind: &EdgeKind) -> bool {
    matches!(
        (opcode, edge_kind),
        (op::IFEQ, EdgeKind::FallThrough) | (op::IFNE, EdgeKind::Branch)
    )
}

pub(super) struct Worklist {
    queue: VecDeque<BlockId>,
    queued: HashSet<BlockId>,
}

impl Worklist {
    pub(super) fn new(entry: BlockId) -> Self {
        Self {
            queue: VecDeque::from([entry]),
            queued: HashSet::from([entry]),
        }
    }

    pub(super) fn pop(&mut self) -> Option<BlockId> {
        let block = self.queue.pop_front()?;
        self.queued.remove(&block);
        Some(block)
    }

    fn enqueue(&mut self, block: BlockId) {
        if self.queued.insert(block) {
            self.queue.push_back(block);
        }
    }
}

pub(super) struct Propagation<'a> {
    method: &'a MethodIr,
    diagnostics: &'a mut Vec<Diagnostic>,
    worklist: &'a mut Worklist,
    hierarchy: Option<&'a dyn TypeHierarchy>,
}

impl<'a> Propagation<'a> {
    pub(super) fn new(
        method: &'a MethodIr,
        diagnostics: &'a mut Vec<Diagnostic>,
        worklist: &'a mut Worklist,
        hierarchy: Option<&'a dyn TypeHierarchy>,
    ) -> Self {
        Self {
            method,
            diagnostics,
            worklist,
            hierarchy,
        }
    }

    pub(super) fn enqueue(&mut self, block_id: BlockId) {
        self.worklist.enqueue(block_id);
    }
}

pub(super) fn propagate_exception_edges(
    edges: &[ExceptionEdge],
    instruction_offset: u16,
    before: Frame,
    incoming: &mut HashMap<BlockId, Frame>,
    propagation: &mut Propagation<'_>,
) {
    for edge in edges
        .iter()
        .filter(|edge| edge.instruction_offset == instruction_offset)
    {
        let outgoing = before.exception_frame(edge.catch_type.clone());
        if merge_frame(
            incoming,
            edge.target,
            outgoing,
            instruction_offset,
            propagation,
        ) {
            propagation.enqueue(edge.target);
        }
    }
}

pub(super) fn propagate_subroutine_return(
    graph: &ControlFlowGraph,
    instruction: &InstructionIr,
    frame: &Frame,
    incoming: &mut HashMap<BlockId, Frame>,
    propagation: &mut Propagation<'_>,
) {
    if instruction.opcode != op::RET {
        return;
    }

    let InstructionOperandIr::Local(local) = instruction.operand else {
        propagation.diagnostics.push(Diagnostic::new(
            DiagnosticSeverity::Warning,
            DiagnosticKind::InvalidControlFlow,
            location(propagation.method, instruction.offset),
            "ret instruction does not identify a local-variable slot",
        ));
        return;
    };
    let Some(targets) = frame.local_return_targets(local) else {
        propagation.diagnostics.push(Diagnostic::new(
            DiagnosticSeverity::Warning,
            DiagnosticKind::InvalidControlFlow,
            location(propagation.method, instruction.offset),
            format!("ret local slot {local} has no known return address"),
        ));
        return;
    };

    for target_offset in targets {
        let Some(target) = graph.block_at_offset(*target_offset) else {
            propagation.diagnostics.push(Diagnostic::new(
                DiagnosticSeverity::Warning,
                DiagnosticKind::InvalidControlFlow,
                location(propagation.method, instruction.offset),
                format!("ret target {target_offset} does not identify an instruction"),
            ));
            continue;
        };
        if merge_frame(
            incoming,
            target,
            frame.clone(),
            instruction.offset,
            propagation,
        ) {
            propagation.enqueue(target);
        }
    }
}

pub(super) fn merge_frame(
    incoming: &mut HashMap<BlockId, Frame>,
    target: BlockId,
    outgoing: Frame,
    offset: u16,
    propagation: &mut Propagation<'_>,
) -> bool {
    let Some(existing) = incoming.get_mut(&target) else {
        incoming.insert(target, outgoing);
        return true;
    };

    let previous = existing.clone();
    let outcome = existing.merge_from(&outgoing, propagation.hierarchy);
    if outcome.stack_height_mismatch {
        propagation.diagnostics.push(Diagnostic::new(
            DiagnosticSeverity::Warning,
            DiagnosticKind::StackHeightMismatch,
            DiagnosticLocation::method(
                &propagation.method.name,
                &propagation.method.descriptor_text,
            )
            .at_offset(offset),
            "control-flow paths reached a block with different operand-stack heights",
        ));
    }
    *existing != previous
}

pub(super) fn limit_diagnostic(method: &MethodIr, limit: &str) -> Diagnostic {
    Diagnostic::new(
        DiagnosticSeverity::Error,
        DiagnosticKind::AnalysisLimitReached,
        DiagnosticLocation::method(&method.name, &method.descriptor_text),
        format!("analysis stopped after reaching the {limit}"),
    )
}

fn location(method: &MethodIr, offset: u16) -> DiagnosticLocation {
    DiagnosticLocation::method(&method.name, &method.descriptor_text).at_offset(offset)
}