Skip to content

Ghidrust provides a hyper fast, AI native reverse engineering platform built in Rust, inspired by Ghidra. Includes experimental GPU kernels to rapidly decompile large files, a decryption suite, and network monitor for packet to binary reverse engineering.

66.8 KB
Raw Blame
//! **Ghidrust structuring** — turn a [`Cfg`] + [`SsaFunction`] into a tree
//! of high-level [`Region`]s (`Seq`, `IfThen`, `IfThenElse`, `While`,
//! `DoWhile`, `Loop`, `Return`) suitable for structured C emission.
//!
//! `/Features/Decompiler` and Cifuentes' 1994 thesis are the
//! *reference*; the code below is hand-rolled per the workspace dependency
//! policy.
//!
//! # Algorithm outline
//!
//! 1. **Reducibility & dominators** — reuse the CFG dominator array to walk
//!    the graph in reverse post-order and compute immediate post-dominators.
//! 2. **Natural loops** — for each back-edge `u → v` (where `v` dominates
//!    `u`), the loop body is the set reachable backwards from `u` without
//!    passing through `v`. Loops that have their `CBranch` at the header
//!    become `While { header, body }`; loops whose exit sits at the latch
//!    become `DoWhile`.
//! 3. **If regions** — for a header block ending in `CBranch` with two
//!    successors that both reach a common immediate post-dominator without
//!    forming a loop, emit `IfThen` (one arm empty) or `IfThenElse`.
//! 4. **Sequence** — everything else falls through as a `Seq` node linking
//!    the region for the current block to the region for its (single)
//!    successor.
//!
//! Regions that don't fit these patterns fall through to a `Goto` node —
//! matching Stage-0 fallback semantics.
//!
//! ## Switch structuring (`switch-recovery` roadmap todo)
//!
//! When the caller passes a [`StructureHints`] populated with
//! [`SwitchHint`]s (typically sourced from `Program.analysis.switches`, i.e.
//! the shipped `Decompiler Switch Analysis` analyzer), structuring will
//! detect blocks whose terminator is a computed jump matching a known
//! `jump_va` and emit [`Region::Switch`] with per-case body regions rather
//! than dropping to a raw `Goto`. This is the wired-up path for the
//! equivalent "switch analyzer + decompiler switch case rendering"
//! contract.
//!
//! ## Short-circuit flattening (`switch-recovery` roadmap todo, `&&`/`||`)
//!
//! A post-pass [`flatten_short_circuit`] scans the built region tree for
//! nested `if` chains that collapse into `if (A && B)` / `if (A || B)`
//! predicates and rewrites them so Stage-1 emit can render a single
//! compound condition. The scan is deliberately conservative — anything
//! ambiguous is left alone so we never fabricate a wrong condition.

use ghidrust_ir::{AddrSpace, OpCode};
use ghidrust_ssa::{Cfg, SsaBlock, SsaFunction, ENTRY_BLOCK};
use serde::{Deserialize, Serialize};
use std::collections::{BTreeMap, BTreeSet, HashSet, VecDeque};

/// Optional analysis hints supplied by the caller: switch-table data (from
/// `Decompiler Switch Analysis`) and any other future joins between the
/// upstream analyzer stack and the structurer. Kept in this crate to avoid
/// a `ghidrust-core` dependency here.
#[derive(Debug, Clone, Default, Serialize, Deserialize)]
pub struct StructureHints {
    /// One entry per recovered jump-table / switch site.
    pub switches: Vec<SwitchHint>,
}

/// A single switch site hint: the computed-jump instruction address and the
/// (case_index, target_va) list. Mirrors `ghidrust_core::SwitchInfo` but
/// lives here so the structurer stays core-free.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct SwitchHint {
    /// Address of the branching instruction (source addr of the `BranchInd`).
    pub jump_va: u64,
    /// `(case_index, target_va)` — order matches the address table.
    pub cases: Vec<(i64, u64)>,
}

impl StructureHints {
    pub fn new() -> Self {
        Self::default()
    }
    pub fn with_switches(switches: Vec<SwitchHint>) -> Self {
        Self { switches }
    }
    pub fn is_empty(&self) -> bool {
        self.switches.is_empty()
    }
}

/// A structured region node. Leaves reference SSA block ids; internal nodes
/// nest regions for the C-like control-flow constructs Stage-1 emits.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub enum Region {
    /// A single [`SsaBlock`] — emit its ops in order.
    Block(u32),
    /// Two-or-more region children evaluated in order (linear fallthrough).
    Seq(Vec<Region>),
    /// `if (cond) { then }` — one-armed conditional.
    IfThen {
        header: u32,
        then_branch: Box<Region>,
    },
    /// `if (cond) { then } else { else }` — two-armed conditional.
    IfThenElse {
        header: u32,
        then_branch: Box<Region>,
        else_branch: Box<Region>,
    },
    /// `while (cond) { body }` — CBranch is at the loop header.
    While { header: u32, body: Box<Region> },
    /// `do { body } while (cond)` — CBranch is at the latch.
    DoWhile {
        header: u32,
        body: Box<Region>,
        latch: u32,
    },
    /// `for (;;) { body }` — infinite loop with no explicit exit.
    Loop { header: u32, body: Box<Region> },
    /// `return;` — a block whose terminator is [`OpCode::Return`].
    Return(u32),
    /// `break;` — an edge from inside a natural loop to the loop's
    /// canonical exit block. Emitted by the structurer when the target of
    /// what would otherwise be a `Goto(exit)` is exactly the enclosing
    /// loop's exit successor. Falls back to `Goto` when the exit set is
    /// ambiguous.
    Break,
    /// `continue;` — an edge from inside a natural loop back to the loop
    /// header that isn't the natural latch. Rendered by Stage-1 as a bare
    /// `continue;` inside the enclosing `while`/`for`/`do-while`.
    Continue,
    /// `goto block_<id>;` — unstructured fallback for edges that don't fit
    /// any pattern (irreducible graphs, unresolved indirect branches).
    Goto(u32),
    /// `switch (var) { case K: … }` — recovered from a computed jump at the
    /// header whose targets are supplied via [`StructureHints::switches`].
    ///
    /// `header` is the SSA block ending in the `BranchInd`; each case
    /// carries its integer selector and the block region it enters.
    /// `default` is the fall-through block region if the switch has an
    /// out-of-table exit.
    Switch {
        header: u32,
        cases: Vec<SwitchCase>,
        default: Option<Box<Region>>,
    },
    /// Compound short-circuit conditional: `if (parts...) { then } else? { else }`.
    ///
    /// Each `ShortCircuitClause` carries a header block whose CBranch is
    /// combined via `&&` / `||` with its neighbour. This is the output of
    /// [`flatten_short_circuit`] — the base structurer never produces it
    /// directly.
    ShortCircuit {
        parts: Vec<ShortCircuitClause>,
        then_branch: Box<Region>,
        else_branch: Option<Box<Region>>,
    },
}

/// One arm of a recovered `switch`. `selector` is the integer case value
/// , `body` is a full
/// [`Region`] the case falls into. Terminating with `break` is Stage-1
/// emit's responsibility (via `Region::Goto` / `Region::Return`).
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct SwitchCase {
    pub selector: i64,
    /// Target SSA block id the case jumps to.
    pub target: u32,
    pub body: Box<Region>,
}

/// One clause of a short-circuit chain: a header SSA block whose CBranch
/// contributes to the compound condition, joined to the next clause by
/// `kind` (`&&` or `||`).
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct ShortCircuitClause {
    pub header: u32,
    /// `And` means "this clause and the next are joined by `&&`"; the last
    /// clause carries [`ShortCircuitKind::Terminal`] (no operator after).
    pub kind: ShortCircuitKind,
    /// `true` when the header's CBranch was structurally *inverted* against
    /// the composite (i.e. the recovered condition should read `!cond`).
    pub negated: bool,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum ShortCircuitKind {
    And,
    Or,
    Terminal,
}

impl Region {
    /// Structural leaf count — helpful for tests and diagnostics.
    pub fn block_count(&self) -> usize {
        match self {
            Region::Block(_) | Region::Return(_) | Region::Goto(_) => 1,
            Region::Break | Region::Continue => 1,
            Region::Seq(rs) => rs.iter().map(|r| r.block_count()).sum(),
            Region::IfThen { then_branch, .. } => 1 + then_branch.block_count(),
            Region::IfThenElse {
                then_branch,
                else_branch,
                ..
            } => 1 + then_branch.block_count() + else_branch.block_count(),
            Region::While { body, .. } | Region::Loop { body, .. } => 1 + body.block_count(),
            Region::DoWhile { body, .. } => 2 + body.block_count(),
            Region::Switch { cases, default, .. } => {
                1 + cases.iter().map(|c| c.body.block_count()).sum::<usize>()
                    + default.as_ref().map(|d| d.block_count()).unwrap_or(0)
            }
            Region::ShortCircuit {
                parts,
                then_branch,
                else_branch,
            } => {
                parts.len()
                    + then_branch.block_count()
                    + else_branch.as_ref().map(|e| e.block_count()).unwrap_or(0)
            }
        }
    }

    /// Depth of nested control-flow constructs.
    pub fn depth(&self) -> usize {
        match self {
            Region::Block(_) | Region::Return(_) | Region::Goto(_) => 0,
            Region::Break | Region::Continue => 0,
            Region::Seq(rs) => rs.iter().map(|r| r.depth()).max().unwrap_or(0),
            Region::IfThen { then_branch, .. } => 1 + then_branch.depth(),
            Region::IfThenElse {
                then_branch,
                else_branch,
                ..
            } => 1 + then_branch.depth().max(else_branch.depth()),
            Region::While { body, .. }
            | Region::DoWhile { body, .. }
            | Region::Loop { body, .. } => 1 + body.depth(),
            Region::Switch { cases, default, .. } => {
                1 + cases
                    .iter()
                    .map(|c| c.body.depth())
                    .chain(default.iter().map(|d| d.depth()))
                    .max()
                    .unwrap_or(0)
            }
            Region::ShortCircuit {
                then_branch,
                else_branch,
                ..
            } => {
                1 + then_branch
                    .depth()
                    .max(else_branch.as_ref().map(|e| e.depth()).unwrap_or(0))
            }
        }
    }

    /// Walk the tree and collect every SSA block id referenced (leaf, header,
    /// or latch).
    pub fn touched_blocks(&self) -> BTreeSet<u32> {
        let mut set = BTreeSet::new();
        self.collect_blocks(&mut set);
        set
    }

    fn collect_blocks(&self, set: &mut BTreeSet<u32>) {
        match self {
            Region::Block(b) | Region::Return(b) | Region::Goto(b) => {
                set.insert(*b);
            }
            Region::Break | Region::Continue => {}
            Region::Seq(rs) => rs.iter().for_each(|r| r.collect_blocks(set)),
            Region::IfThen {
                header,
                then_branch,
            } => {
                set.insert(*header);
                then_branch.collect_blocks(set);
            }
            Region::IfThenElse {
                header,
                then_branch,
                else_branch,
            } => {
                set.insert(*header);
                then_branch.collect_blocks(set);
                else_branch.collect_blocks(set);
            }
            Region::While { header, body } | Region::Loop { header, body } => {
                set.insert(*header);
                body.collect_blocks(set);
            }
            Region::DoWhile {
                header,
                body,
                latch,
            } => {
                set.insert(*header);
                set.insert(*latch);
                body.collect_blocks(set);
            }
            Region::Switch {
                header,
                cases,
                default,
            } => {
                set.insert(*header);
                for c in cases {
                    set.insert(c.target);
                    c.body.collect_blocks(set);
                }
                if let Some(d) = default {
                    d.collect_blocks(set);
                }
            }
            Region::ShortCircuit {
                parts,
                then_branch,
                else_branch,
            } => {
                for p in parts {
                    set.insert(p.header);
                }
                then_branch.collect_blocks(set);
                if let Some(e) = else_branch {
                    e.collect_blocks(set);
                }
            }
        }
    }
}

/// Analysis products from [`structure_function`].
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct StructureReport {
    pub region: Region,
    pub loops: Vec<NaturalLoop>,
    pub post_dominators: Vec<u32>,
}

/// A single natural loop: `header → … → latch → header`, plus all body
/// blocks between them.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct NaturalLoop {
    pub header: u32,
    pub latch: u32,
    pub body: BTreeSet<u32>,
}

/// Entry point: build a [`Region`] tree from CFG + SSA. `cfg` is the pre-SSA
/// CFG (source of edges + dominators); `ssa` provides opcode metadata for
/// leaf classification (return vs. goto). The two must correspond block-by-
/// block (as produced by [`ghidrust_ssa::build_ssa`]).
pub fn structure_function(cfg: &Cfg, ssa: &SsaFunction) -> StructureReport {
    structure_function_with_hints(cfg, ssa, &StructureHints::default())
}

/// Hint-aware entry point. Same output shape as [`structure_function`],
/// but with switch tables from [`StructureHints::switches`] promoted to
/// [`Region::Switch`] instead of being dropped to a raw `goto` for the
/// first indirect-branch successor. Also runs [`flatten_short_circuit`]
/// as a post-pass so callers get compound `&&` / `||` conditions.
pub fn structure_function_with_hints(
    cfg: &Cfg,
    ssa: &SsaFunction,
    hints: &StructureHints,
) -> StructureReport {
    let n = cfg.blocks.len();
    if n == 0 {
        return StructureReport {
            region: Region::Seq(Vec::new()),
            loops: Vec::new(),
            post_dominators: Vec::new(),
        };
    }
    let dom = cfg.dominators();
    let loops = natural_loops(cfg, &dom);
    let pdom = post_dominators(cfg);
    let switch_targets = collect_switch_targets(cfg, ssa, hints);
    let mut ctx = StructCtx {
        cfg,
        ssa,
        dom: &dom,
        pdom: &pdom,
        loops: &loops,
        switches: &switch_targets,
        loop_stack: Vec::new(),
    };
    let mut visited: HashSet<u32> = HashSet::new();
    let raw = ctx.build_region_from(ENTRY_BLOCK, None, &mut visited);
    let flattened = flatten_short_circuit(raw, ssa);
    // R3: `if (cond) goto return_block` → `if (cond) return` when the
    // target leaf is a Return region (early-exit polish).
    let polished = promote_early_returns(flattened, ssa);
    StructureReport {
        region: polished,
        loops,
        post_dominators: pdom,
    }
}

/// Rewrite `IfThen { h, Goto(t) }` / `IfThenElse` arms into `Return(t)` when
/// block `t` is a return terminator. Reduces unstructured gotos on early-exit
/// patterns common in real binaries.
pub fn promote_early_returns(r: Region, ssa: &SsaFunction) -> Region {
    match r {
        Region::Seq(rs) => Region::Seq(
            rs.into_iter()
                .map(|c| promote_early_returns(c, ssa))
                .collect(),
        ),
        Region::IfThen {
            header,
            then_branch,
        } => Region::IfThen {
            header,
            then_branch: Box::new(promote_goto_to_return(
                promote_early_returns(*then_branch, ssa),
                ssa,
            )),
        },
        Region::IfThenElse {
            header,
            then_branch,
            else_branch,
        } => Region::IfThenElse {
            header,
            then_branch: Box::new(promote_goto_to_return(
                promote_early_returns(*then_branch, ssa),
                ssa,
            )),
            else_branch: Box::new(promote_goto_to_return(
                promote_early_returns(*else_branch, ssa),
                ssa,
            )),
        },
        Region::While { header, body } => Region::While {
            header,
            body: Box::new(promote_early_returns(*body, ssa)),
        },
        Region::DoWhile {
            header,
            body,
            latch,
        } => Region::DoWhile {
            header,
            body: Box::new(promote_early_returns(*body, ssa)),
            latch,
        },
        Region::Loop { header, body } => Region::Loop {
            header,
            body: Box::new(promote_early_returns(*body, ssa)),
        },
        Region::Switch {
            header,
            cases,
            default,
        } => Region::Switch {
            header,
            cases: cases
                .into_iter()
                .map(|c| SwitchCase {
                    selector: c.selector,
                    target: c.target,
                    body: Box::new(promote_early_returns(*c.body, ssa)),
                })
                .collect(),
            default: default.map(|d| Box::new(promote_early_returns(*d, ssa))),
        },
        Region::ShortCircuit {
            parts,
            then_branch,
            else_branch,
        } => Region::ShortCircuit {
            parts,
            then_branch: Box::new(promote_early_returns(*then_branch, ssa)),
            else_branch: else_branch.map(|e| Box::new(promote_early_returns(*e, ssa))),
        },
        other => promote_goto_to_return(other, ssa),
    }
}

fn promote_goto_to_return(r: Region, ssa: &SsaFunction) -> Region {
    match r {
        Region::Goto(t) => {
            if ssa
                .block(t)
                .and_then(|b| b.ops.last())
                .map(|o| o.opcode == OpCode::Return)
                .unwrap_or(false)
            {
                Region::Return(t)
            } else {
                Region::Goto(t)
            }
        }
        other => other,
    }
}

/// Resolved switch metadata keyed by the SSA block whose terminator drives
/// the computed jump. Entries here shortcut [`StructCtx::build_region_from`]
/// straight to a [`Region::Switch`] with per-case bodies. `header` is
/// redundant with the map key but kept for future debug dumping.
#[derive(Debug, Clone)]
struct ResolvedSwitch {
    #[allow(dead_code)]
    header: u32,
    cases: Vec<(i64, u32)>,
    default: Option<u32>,
}

fn collect_switch_targets(
    cfg: &Cfg,
    ssa: &SsaFunction,
    hints: &StructureHints,
) -> BTreeMap<u32, ResolvedSwitch> {
    let mut out: BTreeMap<u32, ResolvedSwitch> = BTreeMap::new();
    if hints.switches.is_empty() {
        return out;
    }
    // Enumerate every SSA block whose terminator is an indirect branch —
    // those are the switch header candidates.
    let indirect_blocks: Vec<u32> = ssa
        .blocks
        .iter()
        .filter_map(|b| match b.ops.last().map(|o| o.opcode) {
            Some(OpCode::BranchInd) | Some(OpCode::CallInd) => Some(b.id),
            _ => None,
        })
        .collect();
    if indirect_blocks.is_empty() {
        return out;
    }

    for sw in &hints.switches {
        // Deduplicate identical case targets while preserving order.
        let mut seen: BTreeSet<u32> = BTreeSet::new();
        let mut cases: Vec<(i64, u32)> = Vec::new();
        for (idx, va) in &sw.cases {
            let Some(tid) = cfg.block_of_addr.get(va).copied() else {
                continue;
            };
            if seen.insert(tid) {
                cases.push((*idx, tid));
            }
        }
        if cases.is_empty() {
            continue;
        }
        // Match hint to a header block. Preferred: the switch's jump_va
        // falls inside the block's address range (the analyzer recorded
        // the branching instruction). Fallback: exactly one indirect
        // terminator block whose successor set includes at least one of
        // the recovered case blocks — Cifuentes-style heuristic used when
        // the analyzer only records the jump *table* base.
        let case_targets: BTreeSet<u32> = cases.iter().map(|(_, t)| *t).collect();
        let matched = block_containing_addr(ssa, sw.jump_va)
            .filter(|bid| indirect_blocks.contains(bid))
            .or_else(|| {
                let candidates: Vec<u32> = indirect_blocks
                    .iter()
                    .copied()
                    .filter(|bid| {
                        cfg.blocks[*bid as usize]
                            .successors
                            .iter()
                            .any(|s| case_targets.contains(s))
                    })
                    .collect();
                if candidates.len() == 1 {
                    Some(candidates[0])
                } else if candidates.is_empty() && indirect_blocks.len() == 1 {
                    Some(indirect_blocks[0])
                } else {
                    None
                }
            });
        let Some(bid) = matched else {
            continue;
        };
        if out.contains_key(&bid) {
            continue;
        }
        // Fall-through / default: any CFG successor not already covered.
        let succs = &cfg.blocks[bid as usize].successors;
        let default = succs.iter().copied().find(|s| !case_targets.contains(s));
        out.insert(
            bid,
            ResolvedSwitch {
                header: bid,
                cases,
                default,
            },
        );
    }
    out
}

fn block_containing_addr(ssa: &SsaFunction, addr: u64) -> Option<u32> {
    for b in &ssa.blocks {
        let start = b.start?;
        let end = b.end.unwrap_or(start + 1);
        if addr >= start && addr < end {
            return Some(b.id);
        }
    }
    None
}

struct StructCtx<'a> {
    cfg: &'a Cfg,
    ssa: &'a SsaFunction,
    // `dom` is kept for future refinements (e.g. distinguishing
    // dominance-frontier joins from post-dominator joins). Silence the
    // dead-code warning without dropping the wiring.
    #[allow(dead_code)]
    dom: &'a [u32],
    pdom: &'a [u32],
    loops: &'a [NaturalLoop],
    switches: &'a BTreeMap<u32, ResolvedSwitch>,
    /// Stack of enclosing loops so nested regions can emit `break;` /
    /// `continue;` instead of goto when they hit the loop's canonical exit
    /// or its header. The innermost loop is at the top of the stack.
    loop_stack: Vec<LoopFrame>,
}

#[derive(Debug, Clone)]
struct LoopFrame {
    header: u32,
    /// Canonical exit block for this loop (first successor of any body
    /// block that leaves the loop). `None` means the loop has no natural
    /// exit successor and `Break` won't be synthesised.
    exit: Option<u32>,
}

impl<'a> StructCtx<'a> {
    fn build_region_from(
        &mut self,
        start: u32,
        stop_at: Option<u32>,
        visited: &mut HashSet<u32>,
    ) -> Region {
        let mut seq: Vec<Region> = Vec::new();
        let mut cur = Some(start);
        while let Some(b) = cur {
            if Some(b) == stop_at {
                break;
            }
            if !visited.insert(b) {
                // Already emitted somewhere else. Prefer break/continue
                // over goto when the target matches the enclosing loop's
                // exit or header — that keeps the printed structure
                // gotoless for the common Cifuentes shapes.
                seq.push(self.loop_terminator_for(b));
                break;
            }

            // Loop handling.
            if let Some(l) = self.loop_at(b) {
                let region = self.build_loop(l, visited);
                seq.push(region);
                cur = self.loop_exit(l);
                continue;
            }

            // Switch handling (Decompiler Switch Analysis hint).
            if let Some(sw) = self.switches.get(&b).cloned() {
                let stop = sw.default.or_else(|| {
                    self.pdom
                        .get(b as usize)
                        .copied()
                        .filter(|p| *p != u32::MAX && *p != b)
                });
                let cases: Vec<SwitchCase> = sw
                    .cases
                    .iter()
                    .map(|(sel, tgt)| {
                        let mut case_visited: HashSet<u32> = HashSet::new();
                        case_visited.insert(b);
                        let body = self.build_region_from(*tgt, stop, &mut case_visited);
                        for cb in case_visited {
                            visited.insert(cb);
                        }
                        SwitchCase {
                            selector: *sel,
                            target: *tgt,
                            body: Box::new(body),
                        }
                    })
                    .collect();
                let default_region = sw.default.map(|d| {
                    if visited.contains(&d) {
                        Box::new(Region::Goto(d))
                    } else {
                        let mut dv: HashSet<u32> = HashSet::new();
                        dv.insert(b);
                        let r = self.build_region_from(d, stop, &mut dv);
                        for cb in dv {
                            visited.insert(cb);
                        }
                        Box::new(r)
                    }
                });
                seq.push(Region::Switch {
                    header: b,
                    cases,
                    default: default_region,
                });
                cur = stop;
                continue;
            }

            // Return / terminator.
            let block = &self.ssa.blocks[b as usize];
            if is_return_block(block) {
                seq.push(Region::Return(b));
                cur = None;
                continue;
            }

            let succs = &self.cfg.blocks[b as usize].successors;

            // Conditional if(-else).
            if succs.len() == 2 && ends_in_cbranch(block) {
                let (then_id, else_id) = (succs[0], succs[1]);
                let join = self.if_join(then_id, else_id, stop_at);
                let then_branch = Box::new(self.build_region_from(then_id, join, visited));
                let else_branch = if let Some(join) = join {
                    if else_id == join {
                        None
                    } else {
                        Some(Box::new(self.build_region_from(
                            else_id,
                            Some(join),
                            visited,
                        )))
                    }
                } else {
                    // No shared join — emit both branches with unbounded expansion.
                    Some(Box::new(self.build_region_from(else_id, None, visited)))
                };
                seq.push(match else_branch {
                    Some(else_branch) => Region::IfThenElse {
                        header: b,
                        then_branch,
                        else_branch,
                    },
                    None => Region::IfThen {
                        header: b,
                        then_branch,
                    },
                });
                cur = join;
                continue;
            }

            // Plain block, then continue to the (single) successor.
            seq.push(Region::Block(b));
            let next: Option<u32> = match succs.as_slice() {
                [] => None,
                [s] => {
                    // If this single-successor edge would leave the
                    // enclosing loop, emit a `break;` instead of a
                    // fall-through so the loop body stays gotoless.
                    if let Some(term) = self.loop_exit_terminator(*s) {
                        seq.push(term);
                        None
                    } else {
                        Some(*s)
                    }
                }
                _ => {
                    // >2 successors (e.g. switch, indirect) — fall through
                    // to goto for the first, others are unreachable at this
                    // stage. Switch structuring is deferred.
                    seq.push(self.loop_terminator_for(succs[0]));
                    None
                }
            };
            cur = next;
        }
        collapse_seq(seq)
    }

    /// Pick the "cheapest" terminator for a control-flow edge from the
    /// current context to `target`: prefer `Continue` when the target is
    /// the innermost enclosing loop header, `Break` when it's that
    /// loop's canonical exit, an inline `Return(target)` when the target
    /// is a return-only block (Cifuentes' return-duplication rule keeps
    /// gotos out of arms that would otherwise re-emit the same trivial
    /// return), and fall back to `Goto` otherwise.
    fn loop_terminator_for(&self, target: u32) -> Region {
        for frame in self.loop_stack.iter().rev() {
            if frame.header == target {
                return Region::Continue;
            }
            if frame.exit == Some(target) {
                return Region::Break;
            }
        }
        if self.is_trivial_return_block(target) {
            return Region::Return(target);
        }
        Region::Goto(target)
    }

    /// A "trivial" return block has zero side-effecting ops before its
    /// terminating `Return` — safe to duplicate inline in place of a
    /// `goto block_<id>;` that would otherwise re-target the same
    /// register-writing return. Intermediate Return ops (from post-ret
    /// dead-code that the leader analysis chose not to split off) are
    /// accepted because the emitted `return;` collapses them.
    fn is_trivial_return_block(&self, b: u32) -> bool {
        let Some(block) = self.ssa.blocks.get(b as usize) else {
            return false;
        };
        if !matches!(block.ops.last().map(|o| o.opcode), Some(OpCode::Return)) {
            return false;
        }
        for op in block.ops.iter().take(block.ops.len().saturating_sub(1)) {
            match op.opcode {
                OpCode::Nop | OpCode::Return => {}
                OpCode::Copy
                | OpCode::IntXor
                | OpCode::IntAnd
                | OpCode::IntOr
                | OpCode::IntAdd
                | OpCode::IntSub
                | OpCode::IntEqual
                | OpCode::IntNotEqual
                | OpCode::IntLess
                | OpCode::IntLessEqual
                | OpCode::IntSLess
                | OpCode::IntSLessEqual
                | OpCode::IntSExt
                | OpCode::IntZExt => {
                    if op.output.is_none() {
                        return false;
                    }
                }
                _ => return false,
            }
        }
        true
    }

    /// When `succ` is the innermost enclosing loop's exit, return
    /// `Some(Break)`. Otherwise return `None` so the caller keeps the
    /// natural fall-through.
    fn loop_exit_terminator(&self, succ: u32) -> Option<Region> {
        let frame = self.loop_stack.last()?;
        if frame.exit == Some(succ) {
            Some(Region::Break)
        } else if frame.header == succ {
            Some(Region::Continue)
        } else {
            None
        }
    }

    /// Find the loop whose header is `b`, if any.
    fn loop_at(&self, b: u32) -> Option<&'a NaturalLoop> {
        self.loops.iter().find(|l| l.header == b)
    }

    /// A loop is a `While` when the header ends in a `CBranch`, a `DoWhile`
    /// when only the latch does, and a `Loop` otherwise.
    fn build_loop(&mut self, l: &NaturalLoop, visited: &mut HashSet<u32>) -> Region {
        // Mark header + latch visited to break the back-edge cycle.
        let outer_visited = std::mem::take(visited);
        let mut inner_visited: HashSet<u32> = HashSet::new();
        inner_visited.insert(l.header);

        let header_block = &self.ssa.blocks[l.header as usize];
        let latch_block = &self.ssa.blocks[l.latch as usize];
        let header_cbr = ends_in_cbranch(header_block);
        let latch_cbr = ends_in_cbranch(latch_block);

        // Compute the "in-loop successor" for header: the first successor
        // that's part of the loop body.
        let succs = &self.cfg.blocks[l.header as usize].successors;
        let in_body = succs
            .iter()
            .copied()
            .find(|s| l.body.contains(s))
            .unwrap_or(l.header);

        // Push a loop frame so descendant regions can emit `break;` /
        // `continue;` for edges that hit the exit / header.
        let exit = self.loop_exit(l);
        self.loop_stack.push(LoopFrame {
            header: l.header,
            exit,
        });

        let body_region = if header_cbr {
            // Emit body starting from the loop-body successor, stopping at the
            // header itself (natural back-edge).
            self.build_region_from(in_body, Some(l.header), &mut inner_visited)
        } else {
            // Body is everything reachable from header inside the loop.
            self.build_region_from(l.header, Some(l.header), &mut inner_visited)
        };

        self.loop_stack.pop();

        // Restore the outer visited set + record the whole loop body.
        *visited = outer_visited;
        for b in &l.body {
            visited.insert(*b);
        }
        visited.insert(l.latch);
        visited.insert(l.header);

        if header_cbr {
            Region::While {
                header: l.header,
                body: Box::new(body_region),
            }
        } else if latch_cbr {
            Region::DoWhile {
                header: l.header,
                body: Box::new(body_region),
                latch: l.latch,
            }
        } else {
            Region::Loop {
                header: l.header,
                body: Box::new(body_region),
            }
        }
    }

    /// Compute the exit block for a natural loop — the first successor of a
    /// body block that isn't in the loop body.
    fn loop_exit(&self, l: &NaturalLoop) -> Option<u32> {
        for &b in &l.body {
            for &s in &self.cfg.blocks[b as usize].successors {
                if !l.body.contains(&s) {
                    return Some(s);
                }
            }
        }
        None
    }

    /// Pick the join point for an if header. Falls back to the immediate
    /// post-dominator of the header block.
    fn if_join(&self, then_id: u32, else_id: u32, stop_at: Option<u32>) -> Option<u32> {
        let post_then = self.pdom.get(then_id as usize).copied();
        let post_else = self.pdom.get(else_id as usize).copied();
        let candidates = [post_then, post_else];
        let mut best: Option<u32> = None;
        for c in candidates.into_iter().flatten() {
            if c == u32::MAX || c == then_id || c == else_id {
                continue;
            }
            if Some(c) == stop_at {
                continue;
            }
            best = Some(c);
        }
        best
    }
}

fn is_return_block(b: &SsaBlock) -> bool {
    matches!(b.ops.last().map(|o| o.opcode), Some(OpCode::Return))
}

fn ends_in_cbranch(b: &SsaBlock) -> bool {
    matches!(b.ops.last().map(|o| o.opcode), Some(OpCode::CBranch))
}

fn collapse_seq(mut seq: Vec<Region>) -> Region {
    if seq.len() == 1 {
        return seq.pop().unwrap();
    }
    Region::Seq(seq)
}

/// Enumerate natural loops in a reducible CFG by finding back-edges
/// (`u → v` with `v ∈ dominators(u)`) and computing the body via reverse-
/// BFS from `u` up to (but excluding) `v`.
pub fn natural_loops(cfg: &Cfg, idom: &[u32]) -> Vec<NaturalLoop> {
    let mut loops = Vec::new();
    for u in 0..cfg.blocks.len() as u32 {
        for &v in &cfg.blocks[u as usize].successors {
            if dominates(idom, v, u) {
                let body = loop_body(cfg, v, u);
                loops.push(NaturalLoop {
                    header: v,
                    latch: u,
                    body,
                });
            }
        }
    }
    loops
}

fn dominates(idom: &[u32], a: u32, mut b: u32) -> bool {
    if a as usize >= idom.len() {
        return false;
    }
    loop {
        if b == a {
            return true;
        }
        let next = idom[b as usize];
        if next == u32::MAX || next == b {
            return false;
        }
        b = next;
    }
}

fn loop_body(cfg: &Cfg, header: u32, latch: u32) -> BTreeSet<u32> {
    let mut body: BTreeSet<u32> = BTreeSet::new();
    body.insert(header);
    let mut work: VecDeque<u32> = VecDeque::new();
    if latch != header {
        body.insert(latch);
        work.push_back(latch);
    }
    while let Some(b) = work.pop_front() {
        for p in cfg.predecessors(b) {
            if !body.contains(&p) {
                body.insert(p);
                work.push_back(p);
            }
        }
    }
    body
}

/// Immediate post-dominators computed via the same Cooper–Harvey–Kennedy
/// iteration used for dominators, but on the reversed CFG. Sinks (return
/// blocks) are seeded to a virtual "exit" node; here we pick the highest-
/// id sink and treat it as the post-dominator root for simplicity. When
/// multiple sinks exist the result may be conservative — sufficient for
/// Stage-1 if/else detection where over-approximation costs nothing (we
/// just drop back to the plain-block sequential path).
pub fn post_dominators(cfg: &Cfg) -> Vec<u32> {
    let n = cfg.blocks.len();
    if n == 0 {
        return Vec::new();
    }
    let sinks: Vec<u32> = (0..n as u32)
        .filter(|&b| cfg.blocks[b as usize].successors.is_empty())
        .collect();
    if sinks.is_empty() {
        return vec![u32::MAX; n];
    }
    // Reverse post-order over the reversed graph = post-order over successors
    // ending at a sink. We build it by DFS from every sink combined.
    let mut rpo: Vec<u32> = Vec::new();
    let mut visited = vec![false; n];
    for &s in &sinks {
        dfs_reverse_post(cfg, s, &mut visited, &mut rpo);
    }
    rpo.reverse();
    let mut rpo_of = vec![u32::MAX; n];
    for (i, &b) in rpo.iter().enumerate() {
        rpo_of[b as usize] = i as u32;
    }
    let mut pdom = vec![u32::MAX; n];
    for &s in &sinks {
        pdom[s as usize] = s;
    }
    let mut changed = true;
    while changed {
        changed = false;
        for &b in rpo.iter() {
            if sinks.contains(&b) {
                continue;
            }
            let succs: Vec<u32> = cfg.blocks[b as usize]
                .successors
                .iter()
                .copied()
                .filter(|s| pdom[*s as usize] != u32::MAX)
                .collect();
            let Some(mut new_pdom) = succs.first().copied() else {
                continue;
            };
            for &s in succs.iter().skip(1) {
                new_pdom = intersect_pdom(&pdom, &rpo_of, new_pdom, s);
                if new_pdom == u32::MAX {
                    break;
                }
            }
            if pdom[b as usize] != new_pdom {
                pdom[b as usize] = new_pdom;
                changed = true;
            }
        }
    }
    pdom
}

fn dfs_reverse_post(cfg: &Cfg, start: u32, visited: &mut [bool], order: &mut Vec<u32>) {
    let n = visited.len();
    let mut stack: Vec<(u32, bool)> = vec![(start, false)];
    while let Some((b, processed)) = stack.pop() {
        if processed {
            order.push(b);
            continue;
        }
        if visited[b as usize] {
            continue;
        }
        visited[b as usize] = true;
        stack.push((b, true));
        for p in cfg.predecessors(b) {
            if (p as usize) < n && !visited[p as usize] {
                stack.push((p, false));
            }
        }
    }
}

fn intersect_pdom(pdom: &[u32], rpo_of: &[u32], mut b1: u32, mut b2: u32) -> u32 {
    // Cooper–Harvey–Kennedy `intersect` adapted for post-dominators. If
    // neither finger can advance and the two are still distinct (common in
    // multi-sink CFGs where the case bodies don't share a real join), we
    // bail out with `u32::MAX` — callers treat that as "no post-dominator"
    // rather than fabricating a bogus join.
    while b1 != b2 {
        let mut advanced = false;
        while rpo_of[b1 as usize] > rpo_of[b2 as usize] {
            let next = pdom[b1 as usize];
            if next == b1 || next == u32::MAX {
                break;
            }
            b1 = next;
            advanced = true;
        }
        while rpo_of[b2 as usize] > rpo_of[b1 as usize] {
            let next = pdom[b2 as usize];
            if next == b2 || next == u32::MAX {
                break;
            }
            b2 = next;
            advanced = true;
        }
        if !advanced {
            return u32::MAX;
        }
    }
    b1
}

/// Render a region as an indented pseudo-C skeleton for tests / diagnostics.
pub fn dump_region(r: &Region) -> String {
    let mut s = String::new();
    render(r, 0, &mut s);
    s
}

fn render(r: &Region, indent: usize, out: &mut String) {
    let pad = "  ".repeat(indent);
    match r {
        Region::Block(b) => out.push_str(&format!("{pad}block_{b};\n")),
        Region::Return(b) => out.push_str(&format!("{pad}return; // block_{b}\n")),
        Region::Break => out.push_str(&format!("{pad}break;\n")),
        Region::Continue => out.push_str(&format!("{pad}continue;\n")),
        Region::Goto(b) => out.push_str(&format!("{pad}goto block_{b};\n")),
        Region::Seq(rs) => {
            for r in rs {
                render(r, indent, out);
            }
        }
        Region::IfThen {
            header,
            then_branch,
        } => {
            out.push_str(&format!("{pad}if (cond_of_{header}) {{\n"));
            render(then_branch, indent + 1, out);
            out.push_str(&format!("{pad}}}\n"));
        }
        Region::IfThenElse {
            header,
            then_branch,
            else_branch,
        } => {
            out.push_str(&format!("{pad}if (cond_of_{header}) {{\n"));
            render(then_branch, indent + 1, out);
            out.push_str(&format!("{pad}}} else {{\n"));
            render(else_branch, indent + 1, out);
            out.push_str(&format!("{pad}}}\n"));
        }
        Region::While { header, body } => {
            out.push_str(&format!("{pad}while (cond_of_{header}) {{\n"));
            render(body, indent + 1, out);
            out.push_str(&format!("{pad}}}\n"));
        }
        Region::DoWhile {
            header: _,
            body,
            latch,
        } => {
            out.push_str(&format!("{pad}do {{\n"));
            render(body, indent + 1, out);
            out.push_str(&format!("{pad}}} while (cond_of_{latch});\n"));
        }
        Region::Loop { header, body } => {
            out.push_str(&format!("{pad}for (;;) {{ // header block_{header}\n"));
            render(body, indent + 1, out);
            out.push_str(&format!("{pad}}}\n"));
        }
        Region::Switch {
            header,
            cases,
            default,
        } => {
            out.push_str(&format!("{pad}switch (cond_of_{header}) {{\n"));
            for c in cases {
                out.push_str(&format!(
                    "{pad}  case {}: // → block_{}\n",
                    c.selector, c.target
                ));
                render(&c.body, indent + 2, out);
                out.push_str(&format!("{pad}    break;\n"));
            }
            if let Some(d) = default {
                out.push_str(&format!("{pad}  default:\n"));
                render(d, indent + 2, out);
                out.push_str(&format!("{pad}    break;\n"));
            }
            out.push_str(&format!("{pad}}}\n"));
        }
        Region::ShortCircuit {
            parts,
            then_branch,
            else_branch,
        } => {
            let mut expr = String::new();
            for (i, p) in parts.iter().enumerate() {
                if i > 0 {
                    match parts[i - 1].kind {
                        ShortCircuitKind::And => expr.push_str(" && "),
                        ShortCircuitKind::Or => expr.push_str(" || "),
                        ShortCircuitKind::Terminal => expr.push_str(" ? "),
                    }
                }
                if p.negated {
                    expr.push('!');
                }
                expr.push_str(&format!("cond_of_{}", p.header));
            }
            out.push_str(&format!("{pad}if ({expr}) {{\n"));
            render(then_branch, indent + 1, out);
            if let Some(e) = else_branch {
                out.push_str(&format!("{pad}}} else {{\n"));
                render(e, indent + 1, out);
            }
            out.push_str(&format!("{pad}}}\n"));
        }
    }
}

/// Post-pass short-circuit `&&` / `||` recovery.
///
/// Recognises two textbook patterns produced by the Cifuentes-style
/// if/else structurer:
///
/// * `IfThen { A, IfThen { B, then } }`  →  `if (A && B) { then }`
/// * `IfThenElse { A, then, IfThen { B, then2 } }` where the two `then`
///   bodies collapse into a common continuation → `if (A || B) { then }`.
///
/// The pass is intentionally conservative: it only rewrites when the
/// inner header is a *pure predicate* (a single-block region with no
/// side effects other than the CBranch itself). Anything richer is
/// preserved verbatim.
pub fn flatten_short_circuit(r: Region, ssa: &SsaFunction) -> Region {
    match r {
        Region::Seq(rs) => Region::Seq(
            rs.into_iter()
                .map(|c| flatten_short_circuit(c, ssa))
                .collect(),
        ),
        Region::IfThen {
            header,
            then_branch,
        } => flatten_and(header, *then_branch, ssa),
        Region::IfThenElse {
            header,
            then_branch,
            else_branch,
        } => flatten_or(header, *then_branch, *else_branch, ssa),
        Region::While { header, body } => Region::While {
            header,
            body: Box::new(flatten_short_circuit(*body, ssa)),
        },
        Region::DoWhile {
            header,
            body,
            latch,
        } => Region::DoWhile {
            header,
            body: Box::new(flatten_short_circuit(*body, ssa)),
            latch,
        },
        Region::Loop { header, body } => Region::Loop {
            header,
            body: Box::new(flatten_short_circuit(*body, ssa)),
        },
        Region::Switch {
            header,
            cases,
            default,
        } => Region::Switch {
            header,
            cases: cases
                .into_iter()
                .map(|c| SwitchCase {
                    selector: c.selector,
                    target: c.target,
                    body: Box::new(flatten_short_circuit(*c.body, ssa)),
                })
                .collect(),
            default: default.map(|d| Box::new(flatten_short_circuit(*d, ssa))),
        },
        Region::ShortCircuit {
            parts,
            then_branch,
            else_branch,
        } => Region::ShortCircuit {
            parts,
            then_branch: Box::new(flatten_short_circuit(*then_branch, ssa)),
            else_branch: else_branch.map(|e| Box::new(flatten_short_circuit(*e, ssa))),
        },
        leaf @ (Region::Block(_)
        | Region::Return(_)
        | Region::Goto(_)
        | Region::Break
        | Region::Continue) => leaf,
    }
}

fn is_pure_predicate_block(ssa: &SsaFunction, block: u32) -> bool {
    let Some(b) = ssa.block(block) else {
        return false;
    };
    // Body must be a single CBranch (possibly preceded by trivial condition
    // ops). We approximate "pure predicate" as: last op is CBranch and no
    // op has an output outside the Unique / Register-flag space.
    if !matches!(b.ops.last().map(|o| o.opcode), Some(OpCode::CBranch)) {
        return false;
    }
    for op in b.ops.iter().take(b.ops.len().saturating_sub(1)) {
        if let Some(out) = op.output {
            match out.space {
                AddrSpace::Unique => {}
                AddrSpace::Register if is_flag_register_offset(out.offset) => {}
                _ => return false,
            }
        }
    }
    true
}

fn is_flag_register_offset(offset: u64) -> bool {
    (0x100..=0x106).contains(&offset)
}

fn flatten_and(header: u32, inner: Region, ssa: &SsaFunction) -> Region {
    let inner = flatten_short_circuit(inner, ssa);
    match inner {
        Region::IfThen {
            header: inner_h,
            then_branch,
        } if is_pure_predicate_block(ssa, inner_h) => Region::ShortCircuit {
            parts: vec![
                ShortCircuitClause {
                    header,
                    kind: ShortCircuitKind::And,
                    negated: false,
                },
                ShortCircuitClause {
                    header: inner_h,
                    kind: ShortCircuitKind::Terminal,
                    negated: false,
                },
            ],
            then_branch,
            else_branch: None,
        },
        Region::ShortCircuit {
            mut parts,
            then_branch,
            else_branch,
        } if parts
            .first()
            .map(|p| is_pure_predicate_block(ssa, p.header))
            .unwrap_or(false) =>
        {
            parts.insert(
                0,
                ShortCircuitClause {
                    header,
                    kind: ShortCircuitKind::And,
                    negated: false,
                },
            );
            Region::ShortCircuit {
                parts,
                then_branch,
                else_branch,
            }
        }
        other => Region::IfThen {
            header,
            then_branch: Box::new(other),
        },
    }
}

fn flatten_or(header: u32, then_branch: Region, else_branch: Region, ssa: &SsaFunction) -> Region {
    let then_branch = flatten_short_circuit(then_branch, ssa);
    let else_branch = flatten_short_circuit(else_branch, ssa);
    // Pattern: else arm is `if (B) same_then` — collapse to `A || B`.
    if let Region::IfThen {
        header: else_h,
        then_branch: else_then,
    } = &else_branch
    {
        if is_pure_predicate_block(ssa, *else_h)
            && region_bodies_equivalent(&then_branch, else_then)
        {
            return Region::ShortCircuit {
                parts: vec![
                    ShortCircuitClause {
                        header,
                        kind: ShortCircuitKind::Or,
                        negated: false,
                    },
                    ShortCircuitClause {
                        header: *else_h,
                        kind: ShortCircuitKind::Terminal,
                        negated: false,
                    },
                ],
                then_branch: Box::new(then_branch),
                else_branch: None,
            };
        }
    }
    Region::IfThenElse {
        header,
        then_branch: Box::new(then_branch),
        else_branch: Box::new(else_branch),
    }
}

fn region_bodies_equivalent(a: &Region, b: &Region) -> bool {
    // Cheap structural fingerprint. Full alpha-equivalence would need
    // SSA-aware comparison; this suffices for the common "both branches
    // fall through to the same block" case Cifuentes-style structuring
    // produces.
    let mut sa: Vec<u32> = a.touched_blocks().into_iter().collect();
    let mut sb: Vec<u32> = b.touched_blocks().into_iter().collect();
    sa.sort();
    sb.sort();
    sa == sb
}

/// Convenience: total number of natural loops recognised.
pub fn loop_count(report: &StructureReport) -> usize {
    report.loops.len()
}

/// Count of `Region::Goto` leaves in the recovered structure tree — the
/// primary "unstructured escape" indicator. Break/Continue don't count
/// (they're structured escapes). Combined with [`region_leaf_count`] this
/// yields the `goto_rate` metric.
pub fn goto_count(region: &Region) -> usize {
    match region {
        Region::Goto(_) => 1,
        Region::Seq(rs) => rs.iter().map(goto_count).sum(),
        Region::IfThen { then_branch, .. } => goto_count(then_branch),
        Region::IfThenElse {
            then_branch,
            else_branch,
            ..
        } => goto_count(then_branch) + goto_count(else_branch),
        Region::While { body, .. } | Region::DoWhile { body, .. } | Region::Loop { body, .. } => {
            goto_count(body)
        }
        Region::Switch { cases, default, .. } => {
            cases.iter().map(|c| goto_count(&c.body)).sum::<usize>()
                + default.as_ref().map(|d| goto_count(d)).unwrap_or(0)
        }
        Region::ShortCircuit {
            then_branch,
            else_branch,
            ..
        } => goto_count(then_branch) + else_branch.as_ref().map(|e| goto_count(e)).unwrap_or(0),
        _ => 0,
    }
}

/// Count of every leaf statement in a region — used as the denominator
/// for the `goto_rate` metric. Every terminal region (Block, Return, Goto,
/// Break, Continue) counts as one leaf.
pub fn region_leaf_count(region: &Region) -> usize {
    match region {
        Region::Block(_)
        | Region::Return(_)
        | Region::Goto(_)
        | Region::Break
        | Region::Continue => 1,
        Region::Seq(rs) => rs.iter().map(region_leaf_count).sum(),
        Region::IfThen { then_branch, .. } => 1 + region_leaf_count(then_branch),
        Region::IfThenElse {
            then_branch,
            else_branch,
            ..
        } => 1 + region_leaf_count(then_branch) + region_leaf_count(else_branch),
        Region::While { body, .. } | Region::DoWhile { body, .. } | Region::Loop { body, .. } => {
            1 + region_leaf_count(body)
        }
        Region::Switch { cases, default, .. } => {
            1 + cases
                .iter()
                .map(|c| region_leaf_count(&c.body))
                .sum::<usize>()
                + default.as_ref().map(|d| region_leaf_count(d)).unwrap_or(0)
        }
        Region::ShortCircuit {
            then_branch,
            else_branch,
            ..
        } => {
            1 + region_leaf_count(then_branch)
                + else_branch
                    .as_ref()
                    .map(|e| region_leaf_count(e))
                    .unwrap_or(0)
        }
    }
}

/// `goto_rate = goto_count / max(1, region_leaf_count)`. The goto_rate gate
/// is < 0.15 on the lab fixture; consumers can also report this metric
/// on shared-entry corpora.
pub fn goto_rate(region: &Region) -> f32 {
    let leaves = region_leaf_count(region).max(1);
    goto_count(region) as f32 / leaves as f32
}

/// Convenience: how many distinct blocks the structured tree references.
pub fn coverage(report: &StructureReport) -> usize {
    report.region.touched_blocks().len()
}

/// Convenience: build a `BTreeMap<u32, Region>` keyed by header block for
/// selective render (used by Stage-1 emit).
pub fn header_index(region: &Region) -> BTreeMap<u32, Region> {
    let mut map = BTreeMap::new();
    walk(region, &mut map);
    map
}

fn walk(r: &Region, map: &mut BTreeMap<u32, Region>) {
    match r {
        Region::IfThen { header, .. }
        | Region::IfThenElse { header, .. }
        | Region::While { header, .. }
        | Region::Loop { header, .. } => {
            map.insert(*header, r.clone());
        }
        Region::DoWhile { header, .. } => {
            map.insert(*header, r.clone());
        }
        Region::Switch {
            header,
            cases,
            default,
        } => {
            map.insert(*header, r.clone());
            for c in cases {
                walk(&c.body, map);
            }
            if let Some(d) = default {
                walk(d, map);
            }
        }
        Region::ShortCircuit {
            parts,
            then_branch,
            else_branch,
        } => {
            if let Some(p) = parts.first() {
                map.insert(p.header, r.clone());
            }
            walk(then_branch, map);
            if let Some(e) = else_branch {
                walk(e, map);
            }
        }
        Region::Seq(rs) => rs.iter().for_each(|r| walk(r, map)),
        _ => {}
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use ghidrust_decode::decode_bytes;
    use ghidrust_ir::{IrSequence, PcodeOp, Varnode};
    use ghidrust_lift::lift_instructions;
    use ghidrust_ssa::{build_cfg, build_ssa};

    fn structure_bytes(bytes: &[u8], base: u64) -> StructureReport {
        let insns = decode_bytes(bytes, base, 64).unwrap();
        let last = insns.last().unwrap();
        let end = last.address + last.length as u64;
        let seq = lift_instructions(&insns);
        let cfg = build_cfg(&seq, base, end);
        let ssa = build_ssa(&cfg);
        structure_function(&cfg, &ssa)
    }

    #[test]
    fn structure_linear_prologue_is_return_leaf() {
        // push rbp; mov rbp,rsp; xor eax,eax; pop rbp; ret
        let bytes = [0x55, 0x48, 0x89, 0xe5, 0x31, 0xc0, 0x5d, 0xc3];
        let rep = structure_bytes(&bytes, 0x1000);
        assert!(rep.loops.is_empty());
        let text = dump_region(&rep.region);
        assert!(
            text.contains("return"),
            "linear region should emit return: {text}"
        );
    }

    #[test]
    fn structure_diamond_produces_if_else() {
        // cmp ecx, eax; je +2; xor eax, eax; ret; xor ecx, ecx; ret
        // Bytes: 39 c1 74 02 31 c0 c3 31 c9 c3
        let bytes = [0x39, 0xc1, 0x74, 0x02, 0x31, 0xc0, 0xc3, 0x31, 0xc9, 0xc3];
        let rep = structure_bytes(&bytes, 0x2000);
        let text = dump_region(&rep.region);
        assert!(
            text.contains("if (") && text.contains("return"),
            "diamond should structure to if/return: {text}"
        );
    }

    #[test]
    fn natural_loop_detected_in_synthetic_backedge() {
        // Synthetic contiguous CFG:
        //  0x0 (b0): Branch → 0x2 (b1, loop header)
        //  0x2 (b1): CBranch (cond, target=0x6) → 0x6 exit, fall through 0x4
        //  0x4 (b2): Branch → 0x2 (back-edge / latch)
        //  0x6 (b3): Return
        let mut seq = IrSequence::new();
        seq.push_addressed(
            0x0,
            2,
            PcodeOp::new(OpCode::Branch, None, vec![Varnode::constant(0x2, 8)]),
        );
        seq.push_addressed(
            0x2,
            2,
            PcodeOp::new(
                OpCode::CBranch,
                None,
                vec![Varnode::unique(0, 1), Varnode::constant(0x6, 8)],
            ),
        );
        seq.push_addressed(
            0x4,
            2,
            PcodeOp::new(OpCode::Branch, None, vec![Varnode::constant(0x2, 8)]),
        );
        seq.push_addressed(0x6, 1, PcodeOp::new(OpCode::Return, None, vec![]));

        let cfg = build_cfg(&seq, 0x0, 0x7);
        let ssa = build_ssa(&cfg);
        let rep = structure_function(&cfg, &ssa);
        assert!(!rep.loops.is_empty(), "should detect back-edge loop");
        let l = &rep.loops[0];
        assert_eq!(l.header, cfg.block_of_addr[&0x2]);
        assert_eq!(l.latch, cfg.block_of_addr[&0x4]);
        assert!(l.body.contains(&l.header));
        assert!(l.body.contains(&l.latch));
        let text = dump_region(&rep.region);
        assert!(
            text.contains("while") || text.contains("for (;;)"),
            "loop should structure to while/for: {text}"
        );
    }

    #[test]
    fn coverage_touches_every_block() {
        let bytes = [0x39, 0xc1, 0x74, 0x02, 0x31, 0xc0, 0xc3, 0x31, 0xc9, 0xc3];
        let rep = structure_bytes(&bytes, 0x2000);
        let touched = coverage(&rep);
        assert!(touched >= 2);
    }

    #[test]
    fn region_depth_and_block_count() {
        let bytes = [0x39, 0xc1, 0x74, 0x02, 0x31, 0xc0, 0xc3, 0x31, 0xc9, 0xc3];
        let rep = structure_bytes(&bytes, 0x2000);
        assert!(rep.region.depth() >= 1);
        assert!(rep.region.block_count() >= 2);
    }

    #[test]
    fn switch_hint_promotes_indirect_branch_to_switch_region() {
        use ghidrust_ssa::build_cfg_with_leaders;
        // Synthetic switch: block 0 ends in BranchInd; targets 0x100/0x200
        // are hit by hint. Both cases return.
        let mut seq = IrSequence::new();
        seq.push_addressed(
            0x0,
            2,
            PcodeOp::new(OpCode::BranchInd, None, vec![Varnode::register(0, 8)]),
        );
        seq.push_addressed(0x100, 1, PcodeOp::new(OpCode::Return, None, vec![]));
        seq.push_addressed(0x200, 1, PcodeOp::new(OpCode::Return, None, vec![]));
        // Feed switch targets as extra leaders so build_cfg splits blocks
        // and wires the BranchInd successors correctly.
        let extras = [0x100u64, 0x200u64];
        let cfg = build_cfg_with_leaders(&seq, 0x0, 0x201, &extras);
        let ssa = build_ssa(&cfg);
        let hints = StructureHints::with_switches(vec![SwitchHint {
            jump_va: 0x0,
            cases: vec![(0, 0x100), (1, 0x200)],
        }]);
        let rep = structure_function_with_hints(&cfg, &ssa, &hints);
        let text = dump_region(&rep.region);
        assert!(text.contains("switch"), "expected switch region:\n{text}");
        assert!(text.contains("case 0"));
        assert!(text.contains("case 1"));
    }

    #[test]
    fn short_circuit_and_flattens_nested_if_then() {
        // Manually construct: IfThen{ A, IfThen{ B, Return } } where both
        // A and B are pure predicate blocks.
        let a_body = Region::Return(2);
        let inner = Region::IfThen {
            header: 1,
            then_branch: Box::new(a_body),
        };
        let outer = Region::IfThen {
            header: 0,
            then_branch: Box::new(inner),
        };
        // Build a tiny SSA function with two CBranch-only blocks so
        // `is_pure_predicate_block` returns true for both.
        let mut ssa = SsaFunction::default();
        ssa.blocks = vec![
            SsaBlock {
                id: 0,
                ops: vec![ghidrust_ssa::SsaOp {
                    opcode: OpCode::CBranch,
                    output: None,
                    inputs: vec![],
                    note: None,
                }],
                ..Default::default()
            },
            SsaBlock {
                id: 1,
                ops: vec![ghidrust_ssa::SsaOp {
                    opcode: OpCode::CBranch,
                    output: None,
                    inputs: vec![],
                    note: None,
                }],
                ..Default::default()
            },
            SsaBlock {
                id: 2,
                ops: vec![ghidrust_ssa::SsaOp {
                    opcode: OpCode::Return,
                    output: None,
                    inputs: vec![],
                    note: None,
                }],
                ..Default::default()
            },
        ];
        let flattened = flatten_short_circuit(outer, &ssa);
        match &flattened {
            Region::ShortCircuit { parts, .. } => {
                assert_eq!(parts.len(), 2);
                assert_eq!(parts[0].kind, ShortCircuitKind::And);
                assert_eq!(parts[1].kind, ShortCircuitKind::Terminal);
            }
            other => panic!("expected ShortCircuit, got {other:?}"),
        }
        let text = dump_region(&flattened);
        assert!(text.contains("&&"), "compound && should render:\n{text}");
    }

    #[test]
    fn loop_with_body_exit_emits_break_instead_of_goto() {
        // 0x0: unconditional jmp → 0x2 (loop header, block b1)
        // 0x2: cbranch to 0x8 (exit) fallthrough 0x4
        // 0x4: unconditional jmp → 0x6 (body block)
        // 0x6: unconditional jmp → 0x2 (latch)
        // 0x8: return
        // Body path (0x4→0x6→0x2) forms the loop; an artificial "escape" is
        // not present in this shape but the header cbranch itself already
        // exits to 0x8 → the exit is 0x8. The re-visit of the header from
        // the latch should be a Continue.
        let mut seq = IrSequence::new();
        seq.push_addressed(
            0x0,
            2,
            PcodeOp::new(OpCode::Branch, None, vec![Varnode::constant(0x2, 8)]),
        );
        seq.push_addressed(
            0x2,
            2,
            PcodeOp::new(
                OpCode::CBranch,
                None,
                vec![Varnode::unique(0, 1), Varnode::constant(0x8, 8)],
            ),
        );
        seq.push_addressed(
            0x4,
            2,
            PcodeOp::new(OpCode::Branch, None, vec![Varnode::constant(0x6, 8)]),
        );
        seq.push_addressed(
            0x6,
            2,
            PcodeOp::new(OpCode::Branch, None, vec![Varnode::constant(0x2, 8)]),
        );
        seq.push_addressed(0x8, 1, PcodeOp::new(OpCode::Return, None, vec![]));
        let cfg = build_cfg(&seq, 0x0, 0x9);
        let ssa = build_ssa(&cfg);
        let rep = structure_function(&cfg, &ssa);
        let text = dump_region(&rep.region);
        // With break/continue plumbing, the structured region should be a
        // While over the header with no `goto block_` in the body.
        assert!(text.contains("while"), "expected while:\n{text}");
        assert!(
            goto_count(&rep.region) == 0,
            "expected zero gotos, tree:\n{text}"
        );
    }

    #[test]
    fn goto_rate_zero_on_diamond() {
        let bytes = [0x39, 0xc1, 0x74, 0x02, 0x31, 0xc0, 0xc3, 0x31, 0xc9, 0xc3];
        let rep = structure_bytes(&bytes, 0x2000);
        let rate = goto_rate(&rep.region);
        assert!(
            rate < 0.15,
            "diamond should have goto_rate <0.15, got {}\nRegion tree:\n{}",
            rate,
            dump_region(&rep.region)
        );
    }

    #[test]
    fn short_circuit_or_flattens_matching_then_bodies() {
        // IfThenElse { A, then=Return(2), else = IfThen { B, Return(2) } } → A || B
        let a_then = Region::Return(2);
        let b_then = Region::Return(2);
        let outer = Region::IfThenElse {
            header: 0,
            then_branch: Box::new(a_then),
            else_branch: Box::new(Region::IfThen {
                header: 1,
                then_branch: Box::new(b_then),
            }),
        };
        let mut ssa = SsaFunction::default();
        ssa.blocks = vec![
            SsaBlock {
                id: 0,
                ops: vec![ghidrust_ssa::SsaOp {
                    opcode: OpCode::CBranch,
                    output: None,
                    inputs: vec![],
                    note: None,
                }],
                ..Default::default()
            },
            SsaBlock {
                id: 1,
                ops: vec![ghidrust_ssa::SsaOp {
                    opcode: OpCode::CBranch,
                    output: None,
                    inputs: vec![],
                    note: None,
                }],
                ..Default::default()
            },
            SsaBlock {
                id: 2,
                ops: vec![ghidrust_ssa::SsaOp {
                    opcode: OpCode::Return,
                    output: None,
                    inputs: vec![],
                    note: None,
                }],
                ..Default::default()
            },
        ];
        let flattened = flatten_short_circuit(outer, &ssa);
        match &flattened {
            Region::ShortCircuit { parts, .. } => {
                assert_eq!(parts[0].kind, ShortCircuitKind::Or);
            }
            other => panic!("expected ShortCircuit, got {other:?}"),
        }
        let text = dump_region(&flattened);
        assert!(text.contains("||"), "compound || should render:\n{text}");
    }
}