neo-decompiler 0.10.1

use super::*;
use crate::decompiler::cfg::{BasicBlock, BlockId, Terminator};

#[test]
fn test_dominance_empty_cfg() {
    let cfg = Cfg::new();
    let dominance = compute(&cfg);

    assert!(dominance.idom.is_empty());
    assert!(dominance.dominator_tree.is_empty());
    assert!(dominance.dominance_frontier.is_empty());
}

#[test]
fn test_dominance_single_block() {
    let mut cfg = Cfg::new();
    let block = BasicBlock::new(BlockId(0), 0, 0, 0..0, Terminator::Return);
    cfg.add_block(block);

    let dominance = compute(&cfg);

    assert_eq!(dominance.idom(BlockId::ENTRY), None);
}

#[test]
fn test_dominance_linear_chain() {
    let cfg = create_linear_cfg(3);
    let dominance = compute(&cfg);

    assert_eq!(dominance.idom(BlockId(1)), Some(BlockId(0)));
    assert_eq!(dominance.idom(BlockId(2)), Some(BlockId(1)));

    assert!(dominance.strictly_dominates(BlockId(0), BlockId(1)));
    assert!(dominance.strictly_dominates(BlockId(0), BlockId(2)));

    assert!(dominance.strictly_dominates(BlockId(1), BlockId(2)));
}

#[test]
fn test_dominance_diamond() {
    let cfg = create_diamond_cfg();
    let dominance = compute(&cfg);

    assert!(dominance.strictly_dominates(BlockId::ENTRY, BlockId(1)));
    assert!(dominance.strictly_dominates(BlockId::ENTRY, BlockId(2)));
    assert!(dominance.strictly_dominates(BlockId::ENTRY, BlockId(3)));

    assert_eq!(dominance.idom(BlockId(3)), Some(BlockId(0)));
}

#[test]
fn test_dominator_tree_structure() {
    let cfg = create_diamond_cfg();
    let dominance = compute(&cfg);

    let entry_children = dominance.children(BlockId::ENTRY);
    assert!(!entry_children.is_empty());
}

#[test]
fn diamond_cfg_dominance_frontier() {
    let cfg = create_diamond_cfg();
    let dominance = compute(&cfg);

    assert!(
        dominance.dominance_frontier_vec(BlockId(0)).is_empty(),
        "DF(BB0) should be empty for diamond entry"
    );
    assert_eq!(
        dominance.dominance_frontier_vec(BlockId(1)),
        vec![BlockId(3)],
        "DF(BB1) should be {{BB3}}"
    );
    assert_eq!(
        dominance.dominance_frontier_vec(BlockId(2)),
        vec![BlockId(3)],
        "DF(BB2) should be {{BB3}}"
    );
    assert!(
        dominance.dominance_frontier_vec(BlockId(3)).is_empty(),
        "DF(BB3) should be empty for diamond exit"
    );
}

#[test]
fn loop_cfg_dominance_frontier() {
    let cfg = create_loop_cfg();
    let dominance = compute(&cfg);

    let df0 = dominance.dominance_frontier_vec(BlockId(0));
    assert!(df0.is_empty(), "DF(BB0) should be empty (pre-header)");

    let df1 = dominance.dominance_frontier_vec(BlockId(1));
    assert_eq!(
        df1,
        vec![BlockId(1)],
        "DF(BB1) should be {{BB1}} (loop header in own DF)"
    );

    let df2 = dominance.dominance_frontier_vec(BlockId(2));
    assert_eq!(df2, vec![BlockId(1)], "DF(BB2) should be {{BB1}}");

    let df3 = dominance.dominance_frontier_vec(BlockId(3));
    assert!(df3.is_empty(), "DF(BB3) should be empty (exit block)");
}

#[test]
fn loop_latch_is_dominated_by_header_and_header_is_a_loop_header() {
    let cfg = create_loop_cfg();
    let dominance = compute(&cfg);

    assert_eq!(
        dominance.idom(BlockId(2)),
        Some(BlockId(1)),
        "loop latch (BB2) must be immediately dominated by the header (BB1)"
    );

    let mut headers = std::collections::HashSet::new();
    for block in cfg.blocks() {
        for pred in cfg.predecessors(block.id) {
            if *pred == block.id || dominance.strictly_dominates(block.id, *pred) {
                headers.insert(block.id);
                break;
            }
        }
    }
    assert!(
        headers.contains(&BlockId(1)),
        "BB1 should be detected as a loop header; got {headers:?}"
    );
}

fn create_linear_cfg(count: usize) -> Cfg {
    let mut cfg = Cfg::new();
    for i in 0..count {
        let block = BasicBlock::new(
            BlockId(i),
            i,
            i + 1,
            i..(i + 1),
            if i < count - 1 {
                Terminator::Jump {
                    target: BlockId(i + 1),
                }
            } else {
                Terminator::Return
            },
        );
        cfg.add_block(block);

        if i > 0 {
            cfg.add_edge(
                BlockId(i - 1),
                BlockId(i),
                crate::decompiler::cfg::EdgeKind::Unconditional,
            );
        }
    }
    cfg
}

fn create_loop_cfg() -> Cfg {
    let mut cfg = Cfg::new();

    let pre_header = BasicBlock::new(
        BlockId(0),
        0,
        1,
        0..1,
        Terminator::Jump { target: BlockId(1) },
    );
    cfg.add_block(pre_header);

    let header = BasicBlock::new(
        BlockId(1),
        1,
        2,
        1..2,
        Terminator::Branch {
            then_target: BlockId(2),
            else_target: BlockId(3),
        },
    );
    cfg.add_block(header);
    cfg.add_edge(
        BlockId(0),
        BlockId(1),
        crate::decompiler::cfg::EdgeKind::Unconditional,
    );

    let body = BasicBlock::new(
        BlockId(2),
        2,
        3,
        2..3,
        Terminator::Jump { target: BlockId(1) },
    );
    cfg.add_block(body);
    cfg.add_edge(
        BlockId(1),
        BlockId(2),
        crate::decompiler::cfg::EdgeKind::ConditionalTrue,
    );

    let exit = BasicBlock::new(BlockId(3), 3, 4, 3..4, Terminator::Return);
    cfg.add_block(exit);
    cfg.add_edge(
        BlockId(1),
        BlockId(3),
        crate::decompiler::cfg::EdgeKind::ConditionalFalse,
    );

    cfg.add_edge(
        BlockId(2),
        BlockId(1),
        crate::decompiler::cfg::EdgeKind::Unconditional,
    );

    cfg
}

fn create_diamond_cfg() -> Cfg {
    let mut cfg = Cfg::new();

    let entry = BasicBlock::new(
        BlockId::ENTRY,
        0,
        1,
        0..1,
        Terminator::Branch {
            then_target: BlockId(1),
            else_target: BlockId(2),
        },
    );
    cfg.add_block(entry);

    let left = BasicBlock::new(
        BlockId(1),
        1,
        2,
        1..2,
        Terminator::Jump { target: BlockId(3) },
    );
    cfg.add_block(left);
    cfg.add_edge(
        BlockId::ENTRY,
        BlockId(1),
        crate::decompiler::cfg::EdgeKind::Unconditional,
    );

    let right = BasicBlock::new(
        BlockId(2),
        2,
        3,
        2..3,
        Terminator::Jump { target: BlockId(3) },
    );
    cfg.add_block(right);
    cfg.add_edge(
        BlockId::ENTRY,
        BlockId(2),
        crate::decompiler::cfg::EdgeKind::Unconditional,
    );

    let exit = BasicBlock::new(BlockId(3), 3, 4, 3..4, Terminator::Return);
    cfg.add_block(exit);
    cfg.add_edge(
        BlockId(1),
        BlockId(3),
        crate::decompiler::cfg::EdgeKind::Unconditional,
    );
    cfg.add_edge(
        BlockId(2),
        BlockId(3),
        crate::decompiler::cfg::EdgeKind::Unconditional,
    );

    cfg
}