Grcov report - sort_topological.rs

1

#![forbid(unsafe_code)]

2

3

use log::trace;

4

5

use merc_lts::LTS;

6

use merc_lts::LabelIndex;

7

use merc_lts::StateIndex;

8

use merc_utilities::MercError;

9

use merc_utilities::is_valid_permutation;

10

11

/// Returns a topological ordering of the states of the given LTS, ensuring that `s` occurs before

12

/// `t` if there is a transition from `s` to `t` that satisfies the filter.

13

///

14

/// An error is returned if the LTS contains a cycle.

15

///     - filter: Only transitions satisfying the filter are considered part of the graph.

16

///     - reverse: If true, the topological ordering is reversed, i.e. `t` before the state `s`.

17

5319

pub fn sort_topological<F, L>(lts: &L, filter: F, reverse: bool) -> Result<Vec<StateIndex>, MercError>

18

5319

where

19

5319

    F: Fn(LabelIndex, StateIndex) -> bool,

20

5319

    L: LTS,

21

22

    // The resulting order of states.

23

5319

    let mut stack = Vec::new();

24

25

5319

    let mut visited = vec![false; lts.num_of_states()];

26

5319

    let mut depth_stack = Vec::new();

27

5319

    let mut marks = vec![None; lts.num_of_states()];

28

29

1650707

    for state_index in lts.iter_states() {

30

1650707

        if marks[state_index].is_none()

31

1642116

            && !sort_topological_visit(

32

1642116

                lts,

33

1642116

                &filter,

34

1642116

                state_index,

35

1642116

                &mut depth_stack,

36

1642116

                &mut marks,

37

1642116

                &mut visited,

38

1642116

                &mut stack,

39

1642116

40

41

84

            trace!("There is a cycle from state {state_index} on path {stack:?}");

42

84

            return Err("Labelled transition system contains a cycle".into());

43

1650623

44

45

46

5235

    if !reverse {

47

116

        stack.reverse();

48

5119

49

5235

    trace!("Topological order: {stack:?}");

50

51

    // Turn the stack into a permutation.

52

5235

    let mut reorder = vec![StateIndex::new(0); lts.num_of_states()];

53

1647802

    for (i, &state_index) in stack.iter().enumerate() {

54

1647802

        reorder[state_index] = StateIndex::new(i);

55

1647802

56

57

5235

    debug_assert!(

58

7155417

        is_topologically_sorted(lts, filter, |i| reorder[i], reverse),

59

        "The permutation {reorder:?} is not a valid topological ordering for the states of the given LTS"

60

);

61

62

5235

    Ok(reorder)

63

5319

64

65

// The mark of a state in the depth first search.

66

#[derive(Debug, Clone, Copy, PartialEq, Eq)]

67

enum Mark {

68

    Temporary,

69

    Permanent,

70

71

72

/// Visits the given state in a depth first search.

73

///

74

/// Returns false if a cycle is detected.

75

1642116

fn sort_topological_visit<F, L>(

76

1642116

    lts: &L,

77

1642116

    filter: &F,

78

1642116

    state_index: StateIndex,

79

1642116

    depth_stack: &mut Vec<StateIndex>,

80

1642116

    marks: &mut [Option<Mark>],

81

1642116

    visited: &mut [bool],

82

1642116

    stack: &mut Vec<StateIndex>,

83

1642116

) -> bool

84

1642116

where

85

1642116

    F: Fn(LabelIndex, StateIndex) -> bool,

86

1642116

    L: LTS,

87

88

    // Perform a depth first search.

89

1642116

    depth_stack.push(state_index);

90

91

4959645

    while let Some(state) = depth_stack.pop() {

92

3317613

        match marks[state] {

93

            None => {

94

1659371

                marks[state] = Some(Mark::Temporary);

95

1659371

                depth_stack.push(state); // Re-add to stack to mark as permanent later

96

1659371

                for transition in lts

97

1659371

                    .outgoing_transitions(state)

98

1696114

                    .filter(|transition| state != transition.to && filter(transition.label, transition.to))

99

100

                    // If it was marked temporary, then a cycle is detected.

101

575751

                    if marks[transition.to] == Some(Mark::Temporary) {

102

84

                        return false;

103

575667

104

575667

                    if marks[transition.to].is_none() {

105

17635

                        depth_stack.push(transition.to);

106

558032

107

108

109

1658227

            Some(Mark::Temporary) => {

110

1658227

                marks[state] = Some(Mark::Permanent);

111

1658227

                visited[state] = true;

112

1658227

                stack.push(state);

113

1658227

114

15

            Some(Mark::Permanent) => {}

115

116

117

118

1642032

    true

119

1642116

120

121

/// Returns true if the given permutation is a topological ordering of the states of the given LTS.

122

5251

fn is_topologically_sorted<F, P, L>(lts: &L, filter: F, permutation: P, reverse: bool) -> bool

123

5251

where

124

5251

    F: Fn(LabelIndex, StateIndex) -> bool,

125

5251

    P: Fn(StateIndex) -> StateIndex,

126

5251

    L: LTS,

127

128

5251

    debug_assert!(is_valid_permutation(

129

4991406

        |i| permutation(StateIndex::new(i)).value(),

130

5251

        lts.num_of_states()

131

));

132

133

    // Check that each vertex appears before its successors.

134

1663802

    for state_index in lts.iter_states() {

135

1663802

        let state_order = permutation(state_index);

136

1663802

        for transition in lts

137

1663802

            .outgoing_transitions(state_index)

138

1700418

            .filter(|transition| state_index != transition.to && filter(transition.label, transition.to))

139

140

580053

            if reverse {

141

515159

                if state_order <= permutation(transition.to) {

142

                    return false;

143

515159

144

64894

            } else if state_order >= permutation(transition.to) {

145

                return false;

146

64894

147

148

149

150

5251

    true

151

5251

152

153

#[cfg(test)]

154

mod tests {

155

156

    use merc_io::DumpFiles;

157

    use merc_lts::LabelledTransitionSystem;

158

    use merc_lts::random_lts;

159

    use merc_lts::write_aut;

160

    use merc_utilities::random_test;

161

    use rand::seq::SliceRandom;

162

    use test_log::test;

163

164

    use super::LTS;

165

    use super::StateIndex;

166

    use super::is_topologically_sorted;

167

    use super::sort_topological;

168

169

    #[test]

170

    #[cfg_attr(miri, ignore)] // Test is too slow under miri

171

1

    fn test_random_sort_topological_with_cycles() {

172

100

        random_test(100, |rng| {

173

100

            let lts = random_lts::<String, _>(rng, 1000, 3);

174

100

            if let Ok(order) = sort_topological(&lts, |_, _| true, false) {

175

79844

                assert!(is_topologically_sorted(&lts, |_, _| true, |i| order[i], false))

176

84

177

100

});

178

1

179

180

    #[test]

181

    #[cfg_attr(miri, ignore)] // Test is too slow under miri

182

1

    fn test_random_reorder_states() {

183

100

        random_test(100, |rng| {

184

100

            let files = DumpFiles::new("test_random_reorder_states");

185

186

100

            let lts = random_lts::<String, _>(rng, 1000, 3);

187

100

            files.dump("input.aut", |f| write_aut(f, &lts)).unwrap();

188

189

            // Generate a random permutation.

190

100

            let mut rng = rand::rng();

191

100

            let order: Vec<StateIndex> = {

192

100

                let mut order: Vec<StateIndex> = (0..lts.num_of_states()).map(StateIndex::new).collect();

193

100

                order.shuffle(&mut rng);

194

100

                order

195

};

196

197

200417

            let new_lts = LabelledTransitionSystem::new_from_permutation(lts.clone(), |i| order[i]);

198

100

            files.dump("reordered.aut", |f| write_aut(f, &new_lts)).unwrap();

199

200

100

            assert_eq!(new_lts.num_of_labels(), lts.num_of_labels());

201

100

});

202

1

203