ra-ap-rustc_data_structures 0.28.0

Automatically published version of the package `rustc_data_structures` in the rust-lang/rust repository from commit 5113ed28ea1451a13eae3a05dca0dbabfd56f587 The publishing script for this crate lives at: https://github.com/rust-analyzer/rustc-auto-publish
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

use super::*;

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

#[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).
}