compiler/rustc_data_structures/src/graph/dominators/tests.rs

use super::super::tests::TestGraph;
use super::*;

#[test]
fn diamond() {
    let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 3)]);

    let d = dominators(&graph);
    assert_eq!(d.immediate_dominator(0), None);
    assert_eq!(d.immediate_dominator(1), Some(0));
    assert_eq!(d.immediate_dominator(2), Some(0));
    assert_eq!(d.immediate_dominator(3), Some(0));
}

#[test]
fn paper() {
    // example from the paper:
    let graph = TestGraph::new(6, &[
        (6, 5),
        (6, 4),
        (5, 1),
        (4, 2),
        (4, 3),
        (1, 2),
        (2, 3),
        (3, 2),
        (2, 1),
    ]);

    let d = dominators(&graph);
    assert_eq!(d.immediate_dominator(0), None); // <-- note that 0 is not in graph
    assert_eq!(d.immediate_dominator(1), Some(6));
    assert_eq!(d.immediate_dominator(2), Some(6));
    assert_eq!(d.immediate_dominator(3), Some(6));
    assert_eq!(d.immediate_dominator(4), Some(6));
    assert_eq!(d.immediate_dominator(5), Some(6));
    assert_eq!(d.immediate_dominator(6), None);
}

#[test]
fn paper_slt() {
    // example from the paper:
    let graph = TestGraph::new(1, &[
        (1, 2),
        (1, 3),
        (2, 3),
        (2, 7),
        (3, 4),
        (3, 6),
        (4, 5),
        (5, 4),
        (6, 7),
        (7, 8),
        (8, 5),
    ]);

    dominators(&graph);
}

#[test]
fn immediate_dominator() {
    let graph = TestGraph::new(1, &[(1, 2), (2, 3)]);
    let d = dominators(&graph);
    assert_eq!(d.immediate_dominator(0), None);
    assert_eq!(d.immediate_dominator(1), None);
    assert_eq!(d.immediate_dominator(2), Some(1));
    assert_eq!(d.immediate_dominator(3), Some(2));
}

#[test]
fn transitive_dominator() {
    let graph = TestGraph::new(0, &[
        // First tree branch.
        (0, 1),
        (1, 2),
        (2, 3),
        (3, 4),
        // Second tree branch.
        (1, 5),
        (5, 6),
        // Third tree branch.
        (0, 7),
        // These links make 0 the dominator for 2 and 3.
        (7, 2),
        (5, 3),
    ]);

    let d = dominators(&graph);
    assert_eq!(d.immediate_dominator(2), Some(0));
    assert_eq!(d.immediate_dominator(3), Some(0)); // This used to return Some(1).
}