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

1959

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

39

1959

        Self::with_capacity(labels, hidden_labels, 0)

40

1959

41

42

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

43

15382

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

44

        // Remove duplicates from the labels.

45

15382

        labels.sort();

46

15382

        labels.dedup();

47

48

        // Introduce the fixed 0 indexed tau label.

49

49485

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

50

15282

            labels.swap(0, tau_pos);

51

15282

        } 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

15382

        let mut labels_index = HashMap::new();

57

15382

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

58

49785

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

59

49785

            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

49785

            } else {

62

49785

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

63

49785

64

65

66

15382

        Self {

67

15382

            transitions: Vec::with_capacity(num_of_transitions),

68

15382

            labels_index,

69

15382

            labels,

70

15382

            hidden_labels,

71

15382

            num_of_states: 0,

72

15382

73

15382

74

75

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

76

15282

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

77

15282

        if remove_duplicates {

78

15282

            self.remove_duplicates();

79

15282

80

81

15282

        LabelledTransitionSystem::new(

82

15282

            initial_state,

83

15282

            Some(self.num_of_states),

84

30564

            || self.iter(),

85

15282

            self.labels.clone(),

86

87

15282

88

89

    /// Removes duplicated transitions from the added transitions.

90

15382

    fn remove_duplicates(&mut self) {

91

15382

        self.transitions.sort();

92

15382

        self.transitions.dedup();

93

15382

94

95

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

96

30664

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

97

30664

        self.transitions.iter().cloned()

98

30664

99

100

101

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

102

    type LTS = LabelledTransitionSystem<L>;

103

104

6315414

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

105

6315414

    where

106

6315414

        L: Borrow<Q>,

107

6315414

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

108

109

6315414

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

110

6315414

            index

111

        } else {

112

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

113

            let label = label.to_owned();

114

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

115

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

116

            } else {

117

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

118

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

119

idx

120

};

121

            self.labels_index.insert(label, index);

122

            index

123

};

124

125

6315414

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

126

127

        // Update the number of states.

128

6315414

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

129

6315414

        Ok(())

130

6315414

131

132

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

133

        Ok(self.finish(initial_state, false))

134

135

136

    fn num_of_transitions(&self) -> usize {

137

        self.transitions.len()

138

139

140

100

    fn num_of_states(&self) -> usize {

141

100

        self.num_of_states

142

100

143

144

15227

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

145

15227

        if num_states > self.num_of_states {

146

3472

            self.num_of_states = num_states;

147

11755

148

15227

149

150

151

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

152

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

153

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

154

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

155

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

156

157

        Ok(())

158

159

160

161

#[cfg(test)]

162

mod tests {

163

    use itertools::Itertools;

164

    use rand::RngExt;

165

166

    use merc_utilities::random_test;

167

168

    use crate::LabelIndex;

169

    use crate::LtsBuilder;

170

    use crate::LtsBuilderFast;

171

    use crate::StateIndex;

172

173

    #[test]

174

1

    fn test_random_remove_duplicates() {

175

100

        random_test(100, |rng| {

176

100

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

177

100

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

178

179

425

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

180

425

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

181

425

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

182

425

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

183

425

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

184

425

185

186

100

            builder.remove_duplicates();

187

188

100

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

189

100

            debug_assert!(

190

100

                transitions.iter().all_unique(),

191

                "Transitions should be unique after removing duplicates"

192

);

193

100

});

194

1

195