Grcov report - incoming

1

#![forbid(unsafe_code)]

2

3

use std::marker::PhantomData;

4

5

use merc_collections::ByteCompressedVec;

6

use merc_collections::bytevec;

7

8

use crate::LTS;

9

use crate::LabelIndex;

10

use crate::StateIndex;

11

12

/// Stores the incoming transitions for a given labelled transition system.

13

pub struct IncomingTransitions<'a> {

14

    /// A flat list of all incoming transition labels in the LTS. They are stored in two separate

15

    /// arrays since the compression is based on the highest value.

16

    transition_labels: ByteCompressedVec<LabelIndex>,

17

    transition_from: ByteCompressedVec<StateIndex>,

18

19

    /// A mapping from the state to the `transition_labels` and

20

    /// `transition_from` that stores its incoming transitions.

21

    state2incoming: ByteCompressedVec<usize>,

22

23

    /// Marker to tie the lifetime of the incoming transitions to the LTS.

24

    _marker: PhantomData<&'a ()>,

25

26

27

impl<'a> IncomingTransitions<'a> {

28

3813

    pub fn new<L: LTS>(lts: &'a L) -> Self {

29

3813

        let mut transition_labels = bytevec![LabelIndex::new(0); lts.num_of_transitions()];

30

3813

        let mut transition_from = bytevec![StateIndex::new(0); lts.num_of_transitions()];

31

3813

        let mut state2incoming = bytevec![0usize; lts.num_of_states()];

32

33

        // Count the number of incoming transitions for each state

34

1150422

        for state_index in lts.iter_states() {

35

1938626

            for transition in lts.outgoing_transitions(state_index) {

36

1938626

                state2incoming.update(transition.to.value(), |start| *start += 1);

37

38

39

40

        // Compute the start offsets (prefix sum)

41

1150422

        state2incoming.fold(0, |offset, start| {

42

1150422

            let new_offset = offset + *start;

43

1150422

            *start = offset;

44

1150422

            new_offset

45

1150422

});

46

47

        // Place the transitions

48

1150422

        for state_index in lts.iter_states() {

49

1938626

            for transition in lts.outgoing_transitions(state_index) {

50

1938626

                state2incoming.update(transition.to.value(), |start| {

51

1938626

                    transition_labels.set(*start, transition.label);

52

1938626

                    transition_from.set(*start, state_index);

53

1938626

                    *start += 1;

54

1938626

});

55

56

57

58

1150422

        state2incoming.fold(0, |previous, start| {

59

1150422

            let result = *start;

60

1150422

            *start = previous;

61

1150422

            result

62

1150422

});

63

64

        // Add sentinel state

65

3813

        state2incoming.push(transition_labels.len());

66

67

        // Sort the incoming transitions such that silent transitions come first.

68

//

69

        // TODO: This could be more efficient by simply grouping them instead of sorting, perhaps some group using a predicate.

70

3813

        let mut pairs = Vec::new();

71

1150422

        for state_index in 0..lts.num_of_states() {

72

1150422

            let start = state2incoming.index(state_index);

73

1150422

            let end = state2incoming.index(state_index + 1);

74

75

            // Extract, sort, and put back

76

1150422

            pairs.clear();

77

1938626

            pairs.extend((start..end).map(|i| (transition_labels.index(i), transition_from.index(i))));

78

1150422

            pairs.sort_unstable_by_key(|(label, _)| *label);

79

80

1938626

            for (i, (label, from)) in pairs.iter().enumerate() {

81

1938626

                transition_labels.set(start + i, *label);

82

1938626

                transition_from.set(start + i, *from);

83

1938626

84

85

86

3813

        Self {

87

3813

            transition_labels,

88

3813

            transition_from,

89

3813

            state2incoming,

90

3813

            _marker: PhantomData,

91

3813

92

3813

93

94

    /// Returns an iterator over the incoming transitions for the given state.

95

13907991

    pub fn incoming_transitions(&self, state_index: StateIndex) -> impl Iterator<Item = FromTransition> + '_ {

96

13907991

        let start = self.state2incoming.index(state_index.value());

97

13907991

        let end = self.state2incoming.index(state_index.value() + 1);

98

13958233

        (start..end).map(move |i| FromTransition::new(self.transition_labels.index(i), self.transition_from.index(i)))

99

13907991

100

101

    // Return an iterator over the incoming silent transitions for the given state.

102

135769746

    pub fn incoming_silent_transitions(&self, state_index: StateIndex) -> impl Iterator<Item = FromTransition> + '_ {

103

135769746

        let start = self.state2incoming.index(state_index.value());

104

135769746

        let end = self.state2incoming.index(state_index.value() + 1);

105

135769746

        (start..end)

106

135769746

            .map(move |i| FromTransition::new(self.transition_labels.index(i), self.transition_from.index(i)))

107

135769746

            .take_while(|transition| transition.label == 0)

108

135769746

109

110

111

/// Represents an incoming transition in the LTS going to a known state.

112

#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]

113

pub struct FromTransition {

114

    pub label: LabelIndex,

115

    pub from: StateIndex,

116

117

118

impl FromTransition {

119

    /// Constructs a new transition.

120

130485329

    pub fn new(label: LabelIndex, from: StateIndex) -> Self {

121

130485329

        Self { label, from }

122

130485329

123

124

125

#[cfg(test)]

126

mod tests {

127

    use merc_io::DumpFiles;

128

    use merc_utilities::random_test;

129

130

    use crate::IncomingTransitions;

131

    use crate::LTS;

132

    use crate::random_lts;

133

    use crate::write_aut;

134

135

    #[test]

136

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

137

1

    fn test_random_incoming_transitions() {

138

100

        random_test(100, |rng| {

139

100

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

140

141

100

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

142

100

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

143

100

            let incoming = IncomingTransitions::new(&lts);

144

145

            // Check that for every outgoing transition there is an incoming transition.

146

100000

            for state_index in lts.iter_states() {

147

100059

                for transition in lts.outgoing_transitions(state_index) {

148

100059

                    let found = incoming

149

100059

                        .incoming_transitions(transition.to)

150

150242

                        .any(|incoming| incoming.label == transition.label && incoming.from == state_index);

151

100059

                    assert!(

152

100059

                        found,

153

                        "Outgoing transition ({state_index}, {transition:?}) should have an incoming transition"

154

);

155

156

157

158

            // Check that all incoming transitions belong to some outgoing transition.

159

100000

            for state_index in lts.iter_states() {

160

100059

                for transition in incoming.incoming_transitions(state_index) {

161

100059

                    let found = lts

162

100059

                        .outgoing_transitions(transition.from)

163

133400

                        .any(|outgoing| outgoing.label == transition.label && outgoing.to == state_index);

164

100059

                    assert!(

165

100059

                        found,

166

                        "Incoming transition ({transition:?}, {state_index}) should have an outgoing transition"

167

);

168

169

170

100

});

171

1

172