neo-decompiler 0.10.1

use std::collections::{BTreeMap, BTreeSet};

use crate::decompiler::cfg::{BlockId, Cfg};

/// The parent of `b` in the idom map, except for the entry block sentinel.
pub(super) fn idom_parent(
    idom: &BTreeMap<BlockId, Option<BlockId>>,
    block: BlockId,
) -> Option<BlockId> {
    let parent = idom.get(&block).copied().flatten();
    match parent {
        Some(parent) if parent == block => None,
        other => other,
    }
}

/// Get blocks in reverse post-order.
pub(super) fn reverse_post_order(cfg: &Cfg) -> Vec<BlockId> {
    let mut visited = BTreeSet::new();
    let mut order = Vec::new();

    let entry_id = cfg.entry_block().map(|b| b.id);
    if let Some(entry) = entry_id {
        dfs_post_order(cfg, entry, &mut visited, &mut order);
    }

    order.reverse();
    order
}

fn dfs_post_order(
    cfg: &Cfg,
    entry: BlockId,
    visited: &mut BTreeSet<BlockId>,
    order: &mut Vec<BlockId>,
) {
    let mut stack: Vec<(BlockId, usize)> = Vec::new();

    if !visited.insert(entry) {
        return;
    }
    stack.push((entry, 0));

    while let Some((block, next_idx)) = stack.last_mut() {
        let successors = cfg.successors(*block);
        if *next_idx < successors.len() {
            let succ = successors[*next_idx];
            *next_idx += 1;
            if visited.insert(succ) {
                stack.push((succ, 0));
            }
        } else {
            let (block, _) = stack.pop().expect("stack is non-empty");
            order.push(block);
        }
    }
}