ferro-jtype 0.2.8

Type inference for Java class bytecode without JDK symbols
Documentation
use std::collections::{BTreeMap, BTreeSet};

use la_arena::Arena;
use rust_asm::opcodes as op;

use crate::cfg::{BasicBlock, BlockId, ControlFlowGraph, Edge, EdgeKind, ExceptionEdge};
use crate::ir::{InstructionOperandIr, MethodIr};
use crate::{Diagnostic, DiagnosticKind, DiagnosticLocation, DiagnosticSeverity};

pub(crate) struct CfgBuildResult {
    pub(crate) graph: ControlFlowGraph,
    pub(crate) diagnostics: Vec<Diagnostic>,
}

pub(crate) fn build_cfg(method: &MethodIr) -> CfgBuildResult {
    if method.instructions.is_empty() {
        return CfgBuildResult {
            graph: ControlFlowGraph {
                blocks: Arena::new(),
                entry: None,
                blocks_by_offset: BTreeMap::new(),
            },
            diagnostics: Vec::new(),
        };
    }

    let instruction_positions = method
        .instructions
        .iter()
        .enumerate()
        .map(|(index, instruction)| (instruction.offset, index))
        .collect::<BTreeMap<_, _>>();
    let mut starts = BTreeSet::from([method.instructions[0].offset]);
    let mut diagnostics = Vec::new();

    for (index, instruction) in method.instructions.iter().enumerate() {
        let has_next = method.instructions.get(index + 1).map(|next| next.offset);
        let control_targets = instruction_targets(instruction);

        for target in control_targets {
            add_start_if_instruction(
                &mut starts,
                &instruction_positions,
                target,
                method,
                instruction.offset,
                &mut diagnostics,
            );
        }

        if ends_block(instruction.opcode)
            && let Some(next_offset) = has_next
        {
            starts.insert(next_offset);
        }
    }

    for handler in &method.exception_handlers {
        add_start_if_instruction(
            &mut starts,
            &instruction_positions,
            i32::from(handler.start_offset),
            method,
            handler.start_offset,
            &mut diagnostics,
        );
        add_start_if_instruction(
            &mut starts,
            &instruction_positions,
            i32::from(handler.handler_offset),
            method,
            handler.handler_offset,
            &mut diagnostics,
        );
        if instruction_positions.contains_key(&handler.end_offset) {
            starts.insert(handler.end_offset);
        }
    }

    let ordered_starts = starts.into_iter().collect::<Vec<_>>();
    let mut blocks = Arena::with_capacity(ordered_starts.len());
    let mut block_by_offset = BTreeMap::new();

    for (index, start_offset) in ordered_starts.iter().copied().enumerate() {
        let start_index = instruction_positions[&start_offset];
        let end_index = ordered_starts
            .get(index + 1)
            .and_then(|next_offset| instruction_positions.get(next_offset).copied())
            .unwrap_or(method.instructions.len());
        let block = blocks.alloc(BasicBlock {
            start_offset,
            instruction_range: start_index..end_index,
            successors: Vec::new(),
            exception_successors: Vec::new(),
        });
        block_by_offset.insert(start_offset, block);
    }

    for (_, block) in blocks.iter_mut() {
        let last_index = block.instruction_range.end - 1;
        let last_instruction = &method.instructions[last_index];
        let successors = ordinary_successors(last_instruction, &instruction_positions);

        for (target, kind) in successors {
            if let Some(target) = resolve_block(&block_by_offset, target) {
                push_edge(&mut block.successors, target, kind);
            } else {
                diagnostics.push(invalid_target_diagnostic(
                    method,
                    last_instruction.offset,
                    target,
                ));
            }
        }

        for instruction in &method.instructions[block.instruction_range.clone()] {
            if !may_throw(instruction.opcode) {
                continue;
            }

            for handler in &method.exception_handlers {
                if instruction.offset >= handler.start_offset
                    && instruction.offset < handler.end_offset
                    && let Some(target) = block_by_offset.get(&handler.handler_offset).copied()
                {
                    push_exception_edge(
                        &mut block.exception_successors,
                        instruction.offset,
                        target,
                        handler.catch_type.clone(),
                    );
                }
            }
        }
    }

    let entry = block_by_offset.get(&method.instructions[0].offset).copied();
    CfgBuildResult {
        graph: ControlFlowGraph {
            blocks,
            entry,
            blocks_by_offset: block_by_offset,
        },
        diagnostics,
    }
}

fn add_start_if_instruction(
    starts: &mut BTreeSet<u16>,
    instruction_positions: &BTreeMap<u16, usize>,
    target: i32,
    method: &MethodIr,
    source_offset: u16,
    diagnostics: &mut Vec<Diagnostic>,
) {
    let Ok(target) = u16::try_from(target) else {
        diagnostics.push(invalid_target_diagnostic(method, source_offset, target));
        return;
    };

    if instruction_positions.contains_key(&target) {
        starts.insert(target);
    } else {
        diagnostics.push(invalid_target_diagnostic(
            method,
            source_offset,
            i32::from(target),
        ));
    }
}

fn instruction_targets(instruction: &crate::ir::InstructionIr) -> Vec<i32> {
    match &instruction.operand {
        InstructionOperandIr::Branch { target } => vec![*target],
        InstructionOperandIr::TableSwitch {
            default_target,
            targets,
        } => std::iter::once(*default_target)
            .chain(targets.iter().copied())
            .collect(),
        InstructionOperandIr::LookupSwitch {
            default_target,
            targets,
        } => std::iter::once(*default_target)
            .chain(targets.iter().map(|(_, target)| *target))
            .collect(),
        _ => Vec::new(),
    }
}

fn ordinary_successors(
    instruction: &crate::ir::InstructionIr,
    instruction_positions: &BTreeMap<u16, usize>,
) -> Vec<(i32, EdgeKind)> {
    let fall_through = instruction_positions
        .range((
            std::ops::Bound::Excluded(instruction.offset),
            std::ops::Bound::Unbounded,
        ))
        .next()
        .map(|(offset, _)| i32::from(*offset));

    match &instruction.operand {
        InstructionOperandIr::Branch { target } if is_unconditional_branch(instruction.opcode) => {
            vec![(*target, EdgeKind::Branch)]
        }
        InstructionOperandIr::Branch { target } if is_subroutine_branch(instruction.opcode) => {
            vec![(*target, EdgeKind::Branch)]
        }
        InstructionOperandIr::Branch { target } => {
            let mut successors = vec![(*target, EdgeKind::Branch)];
            if let Some(fall_through) = fall_through {
                successors.push((fall_through, EdgeKind::FallThrough));
            }
            successors
        }
        InstructionOperandIr::TableSwitch {
            default_target,
            targets,
        } => std::iter::once((*default_target, EdgeKind::Switch))
            .chain(
                targets
                    .iter()
                    .copied()
                    .map(|target| (target, EdgeKind::Switch)),
            )
            .collect(),
        InstructionOperandIr::LookupSwitch {
            default_target,
            targets,
        } => std::iter::once((*default_target, EdgeKind::Switch))
            .chain(
                targets
                    .iter()
                    .map(|(_, target)| (*target, EdgeKind::Switch)),
            )
            .collect(),
        _ if terminates_execution(instruction.opcode) || is_ret(instruction.opcode) => Vec::new(),
        _ => fall_through
            .map(|target| vec![(target, EdgeKind::FallThrough)])
            .unwrap_or_default(),
    }
}

fn resolve_block(block_by_offset: &BTreeMap<u16, BlockId>, offset: i32) -> Option<BlockId> {
    u16::try_from(offset)
        .ok()
        .and_then(|offset| block_by_offset.get(&offset).copied())
}

fn push_edge(edges: &mut Vec<Edge>, target: BlockId, kind: EdgeKind) {
    if !edges
        .iter()
        .any(|edge| edge.target == target && edge.kind == kind)
    {
        edges.push(Edge { target, kind });
    }
}

fn push_exception_edge(
    edges: &mut Vec<ExceptionEdge>,
    instruction_offset: u16,
    target: BlockId,
    catch_type: Option<crate::ClassName>,
) {
    if !edges.iter().any(|edge| {
        edge.instruction_offset == instruction_offset
            && edge.target == target
            && edge.catch_type == catch_type
    }) {
        edges.push(ExceptionEdge {
            instruction_offset,
            target,
            catch_type,
        });
    }
}

fn invalid_target_diagnostic(method: &MethodIr, source_offset: u16, target: i32) -> Diagnostic {
    Diagnostic::new(
        DiagnosticSeverity::Warning,
        DiagnosticKind::InvalidControlFlow,
        DiagnosticLocation::method(&method.name, &method.descriptor_text).at_offset(source_offset),
        format!("control-flow target {target} does not identify an instruction"),
    )
}

const fn ends_block(opcode: u8) -> bool {
    matches!(
        opcode,
        op::IFEQ..=op::RET
            | op::TABLESWITCH
            | op::LOOKUPSWITCH
            | op::IRETURN..=op::RETURN
            | op::ATHROW
            | op::IFNULL..=op::JSR_W
    )
}

const fn terminates_execution(opcode: u8) -> bool {
    matches!(opcode, op::IRETURN..=op::RETURN | op::ATHROW)
}

const fn is_unconditional_branch(opcode: u8) -> bool {
    matches!(opcode, op::GOTO | op::GOTO_W)
}

const fn is_subroutine_branch(opcode: u8) -> bool {
    matches!(opcode, op::JSR | op::JSR_W)
}

const fn is_ret(opcode: u8) -> bool {
    opcode == op::RET
}

const fn 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::ATHROW
            | op::CHECKCAST..=op::MONITOREXIT
            | op::MULTIANEWARRAY
    )
}