neo-decompiler 0.10.2

//! Structural control-flow recovery: CFG -> typed `ir::Block`.
//!
//! This is the core of the Phase-4 IR spine. It walks the CFG directly and
//! emits structured [`crate::decompiler::ir`] nodes using the optimized SSA form
//! for straight-line bodies and branch conditions.

use std::collections::HashSet;

use crate::decompiler::cfg::{BlockId, Cfg, Terminator};
use crate::decompiler::ir::{Block as IrBlock, Expr, Stmt};

use super::ssa::ssa_expr_to_ir;
use super::ssa::{SsaForm, SsaStmt};

mod branches;
mod loops;
mod switches;
mod try_blocks;
mod util;

#[cfg(test)]
mod tests;

/// Structure a whole [`SsaForm`] into a single [`IrBlock`] starting from its
/// entry block.
#[must_use]
pub fn structure(ssa: &SsaForm) -> IrBlock {
    let loop_headers = loops::compute_loop_headers(&ssa.cfg, &ssa.dominance);
    let ctx = StructCtx {
        cfg: &ssa.cfg,
        ssa,
        loop_headers,
    };
    let entry = ssa.cfg.blocks().next().map(|b| b.id);
    let mut visited = HashSet::new();
    match entry {
        Some(e) => ctx.structure_region(e, None, &mut visited, true),
        None => IrBlock::new(),
    }
}

pub(super) struct StructCtx<'a> {
    pub(super) cfg: &'a Cfg,
    pub(super) ssa: &'a SsaForm,
    pub(super) loop_headers: HashSet<BlockId>,
}

impl<'a> StructCtx<'a> {
    /// Structure the region reachable from `entry`, stopping without traversing
    /// into `boundary`.
    pub(super) fn structure_region(
        &self,
        entry: BlockId,
        boundary: Option<BlockId>,
        visited: &mut HashSet<BlockId>,
        detect_dowhile: bool,
    ) -> IrBlock {
        let mut out = IrBlock::new();
        let mut cur = Some(entry);

        while let Some(bid) = cur {
            if Some(bid) == boundary {
                break;
            }

            if detect_dowhile
                && self.loop_headers.contains(&bid)
                && !matches!(self.terminator(bid), Terminator::Branch { .. })
            {
                if let Some(next) = self.try_emit_do_while(&mut out, bid, visited) {
                    cur = next;
                    continue;
                }
            }

            if !visited.insert(bid) {
                break;
            }

            if matches!(self.terminator(bid), Terminator::Branch { .. }) {
                self.emit_body_except_last(&mut out, bid);
            } else {
                self.emit_body(&mut out, bid);
            }

            cur = match self.terminator(bid) {
                Terminator::Return
                | Terminator::Throw
                | Terminator::Abort
                | Terminator::Unknown => {
                    out.push(Stmt::Comment(format!("return/throw/abort at {:?}", bid)));
                    None
                }
                Terminator::Fallthrough { target } | Terminator::Jump { target } => Some(target),
                Terminator::Branch {
                    then_target,
                    else_target,
                } => {
                    if self.loop_headers.contains(&bid) {
                        self.emit_while_loop(&mut out, bid, then_target, else_target, visited)
                    } else {
                        self.handle_branch(
                            &mut out,
                            bid,
                            then_target,
                            else_target,
                            boundary,
                            visited,
                        )
                    }
                }
                Terminator::TryEntry {
                    body_target,
                    catch_target,
                    finally_target,
                } => self.handle_try(
                    &mut out,
                    bid,
                    body_target,
                    catch_target,
                    finally_target,
                    visited,
                ),
                Terminator::EndTry { .. } => None,
            };
        }

        out
    }

    /// Emit a block's straight-line SSA assignments as IR statements.
    pub(super) fn emit_body(&self, out: &mut IrBlock, bid: BlockId) {
        let Some(block) = self.ssa.block(bid) else {
            return;
        };
        for stmt in &block.stmts {
            if let SsaStmt::Assign { target, value } = stmt {
                out.push(Stmt::Assign {
                    target: util::var_name(target),
                    value: ssa_expr_to_ir(value),
                });
            }
        }
    }

    /// Like [`emit_body`](Self::emit_body) but suppresses the last assignment.
    pub(super) fn emit_body_except_last(&self, out: &mut IrBlock, bid: BlockId) {
        let Some(block) = self.ssa.block(bid) else {
            return;
        };
        let n = block.stmts.len();
        if n <= 1 {
            return;
        }
        for stmt in &block.stmts[..n - 1] {
            if let SsaStmt::Assign { target, value } = stmt {
                out.push(Stmt::Assign {
                    target: util::var_name(target),
                    value: ssa_expr_to_ir(value),
                });
            }
        }
    }

    /// The branch condition variable when no inlinable comparison is available.
    pub(super) fn condition_for_block(&self, bid: BlockId) -> Expr {
        if let Some(block) = self.ssa.block(bid) {
            for stmt in block.stmts.iter().rev() {
                if let SsaStmt::Assign { target, .. } = stmt {
                    return Expr::Variable(util::var_name(target));
                }
            }
        }
        Expr::Variable(format!("cond_{}", bid.0))
    }

    pub(super) fn terminator(&self, bid: BlockId) -> Terminator {
        self.cfg
            .block(bid)
            .map(|b| b.terminator.clone())
            .unwrap_or(Terminator::Unknown)
    }
}