Grcov report - lts_builder

1

#![forbid(unsafe_code)]

2

3

use std::borrow::Borrow;

4

use std::collections::HashMap;

5

use std::fmt;

6

use std::hash::Hash;

7

8

use merc_utilities::MercError;

9

10

use crate::LabelIndex;

11

use crate::LabelledTransitionSystem;

12

use crate::LtsBuilder;

13

use crate::StateIndex;

14

use crate::TransitionLabel;

15

16

/// This is the same as [`crate::LtsBuilder`], but optimized for speed rather than memory usage.

17

/// So it does not use the byte compression for the transitions since somehow permuting and

18

/// sorting these take a long time (probably due to cache misses).

19

///

20

/// Perhaps that implementation can be made more efficient in the future, but for now

21

/// this works well enough.

22

pub struct LtsBuilderFast<L> {

23

    transitions: Vec<(StateIndex, LabelIndex, StateIndex)>,

24

25

    // This is used to keep track of the label to index mapping.

26

    labels_index: HashMap<L, LabelIndex>,

27

    labels: Vec<L>,

28

29

    /// The hidden labels that should be mapped to the hidden action.

30

    hidden_labels: Vec<String>,

31

32

    /// The number of states (derived from the transitions).

33

    num_of_states: usize,

34

35

36

impl<L: TransitionLabel> LtsBuilderFast<L> {

37

    /// Initializes a new empty builder.

38

1887

    pub fn new(labels: Vec<L>, hidden_labels: Vec<String>) -> Self {

39

1887

        Self::with_capacity(labels, hidden_labels, 0)

40

1887

41

42

    /// Initializes the builder with pre-allocated capacity for states and transitions.

43

15291

    pub fn with_capacity(mut labels: Vec<L>, hidden_labels: Vec<String>, num_of_transitions: usize) -> Self {

44

        // Remove duplicates from the labels.

45

15291

        labels.sort();

46

15291

        labels.dedup();

47

48

        // Introduce the fixed 0 indexed tau label.

49

49080

        if let Some(tau_pos) = labels.iter().position(|l| l.is_tau_label()) {

50

15191

            labels.swap(0, tau_pos);

51

15191

        } else {

52

100

            labels.insert(0, L::tau_label());

53

100

54

55

        // Ensure that all hidden labels are mapped to the tau action.

56

15291

        let mut labels_index = HashMap::new();

57

15291

        labels_index.insert(labels[0].clone(), LabelIndex::new(0));

58

49380

        for (index, label) in labels.iter().enumerate() {

59

49380

            if hidden_labels.iter().any(|l| label.matches_label(l)) {

60

                labels_index.insert(label.clone(), LabelIndex::new(0)); // Map hidden labels to tau

61

49380

            } else {

62

49380

                labels_index.insert(label.clone(), LabelIndex::new(index));

63

49380

64

65

66

15291

        Self {

67

15291

            transitions: Vec::with_capacity(num_of_transitions),

68

15291

            labels_index,

69

15291

            labels,

70

15291

            hidden_labels,

71

15291

            num_of_states: 0,

72

15291

73

15291

74

75

    /// Finalizes the builder and returns the constructed labelled transition system.

76

15191

    pub fn finish(&mut self, initial_state: StateIndex, remove_duplicates: bool) -> LabelledTransitionSystem<L> {

77

15191

        if remove_duplicates {

78

15191

            self.remove_duplicates();

79

15191

80

81

15191

        LabelledTransitionSystem::new(

82

15191

            initial_state,

83

15191

            Some(self.num_of_states),

84

30382

            || self.iter(),

85

15191

            self.labels.clone(),

86

87

15191

88

89

    /// Sets the number of states to at least the given number. All states without transitions

90

    /// will simply become deadlock states.

91

15132

    pub fn require_num_of_states(&mut self, num_states: usize) {

92

15132

        if num_states > self.num_of_states {

93

3640

            self.num_of_states = num_states;

94

11492

95

15132

96

97

    /// Removes duplicated transitions from the added transitions.

98

15291

    fn remove_duplicates(&mut self) {

99

15291

        self.transitions.sort();

100

15291

        self.transitions.dedup();

101

15291

102

103

    /// Returns an iterator over all transitions as (from, label, to) tuples.

104

30482

    pub fn iter(&self) -> impl Iterator<Item = (StateIndex, LabelIndex, StateIndex)> {

105

30482

        self.transitions.iter().cloned()

106

30482

107

108

109

impl<L: TransitionLabel> LtsBuilder<L> for LtsBuilderFast<L> {

110

    type LTS = LabelledTransitionSystem<L>;

111

112

6310035

    fn add_transition<Q>(&mut self, from: StateIndex, label: &Q, to: StateIndex) -> Result<(), MercError>

113

6310035

    where

114

6310035

        L: Borrow<Q>,

115

6310035

        Q: ?Sized + ToOwned<Owned = L> + Eq + Hash,

116

117

6310035

        let label_index = if let Some(&index) = self.labels_index.get(label) {

118

6310035

            index

119

        } else {

120

            // Label was not yet added, so add it to the labels and the index.

121

            let label = label.to_owned();

122

            let index = if self.hidden_labels.iter().any(|l| label.matches_label(l)) {

123

                LabelIndex::new(0) // Map hidden labels to tau

124

            } else {

125

                let idx = LabelIndex::new(self.labels.len());

126

                self.labels.push(label.clone());

127

idx

128

};

129

            self.labels_index.insert(label, index);

130

            index

131

};

132

133

6310035

        self.transitions.push((from, label_index, to));

134

135

        // Update the number of states.

136

6310035

        self.num_of_states = self.num_of_states.max(from.value() + 1).max(to.value() + 1);

137

6310035

        Ok(())

138

6310035

139

140

    fn finish(&mut self, initial_state: StateIndex) -> Result<Self::LTS, MercError> {

141

        Ok(self.finish(initial_state, false))

142

143

144

    fn num_of_transitions(&self) -> usize {

145

        self.transitions.len()

146

147

148

100

    fn num_of_states(&self) -> usize {

149

100

        self.num_of_states

150

100

151

152

153

impl<Label: TransitionLabel> fmt::Debug for LtsBuilderFast<Label> {

154

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {

155

        writeln!(f, "Transitions:")?;

156

        for (from, label, to) in self.iter() {

157

            writeln!(f, "    {:?} --[{:?}]-> {:?}", from, label, to)?;

158

159

        Ok(())

160

161

162

163

#[cfg(test)]

164

mod tests {

165

    use itertools::Itertools;

166

    use rand::RngExt;

167

168

    use merc_utilities::random_test;

169

170

    use crate::LabelIndex;

171

    use crate::LtsBuilder;

172

    use crate::LtsBuilderFast;

173

    use crate::StateIndex;

174

175

    #[test]

176

1

    fn test_random_remove_duplicates() {

177

100

        random_test(100, |rng| {

178

100

            let labels = vec!["a".to_string(), "b".to_string(), "c".to_string()];

179

100

            let mut builder = LtsBuilderFast::new(labels.clone(), Vec::new());

180

181

428

            for _ in 0..rng.random_range(0..10) {

182

428

                let from = StateIndex::new(rng.random_range(0..10));

183

428

                let label = LabelIndex::new(rng.random_range(0..2));

184

428

                let to = StateIndex::new(rng.random_range(0..10));

185

428

                builder.add_transition(from, &labels[label], to).unwrap();

186

428

187

188

100

            builder.remove_duplicates();

189

190

100

            let transitions = builder.iter().collect::<Vec<_>>();

191

100

            debug_assert!(

192

100

                transitions.iter().all_unique(),

193

                "Transitions should be unique after removing duplicates"

194

);

195

100

});

196

1

197