Grcov report - lts

1

use std::borrow::Borrow;

2

use std::collections::HashMap;

3

use std::fmt;

4

use std::hash::Hash;

5

6

use merc_collections::ByteCompressedVec;

7

use merc_collections::CompressedEntry;

8

9

use crate::LabelIndex;

10

use crate::LabelledTransitionSystem;

11

use crate::StateIndex;

12

use crate::TransitionLabel;

13

14

/// This struct helps in building a labelled transition system by accumulating

15

/// transitions efficiently.

16

///

17

/// # Details

18

///

19

/// When labels are added via `add_transition`, they are mapped to `LabelIndex`

20

/// values internally. The mapping is maintained in a `HashMap<String,

21

/// LabelIndex>`, and new labels are assigned the next available index.

22

/// Alternatively, labels can be added directly using `add_transition_index` an

23

///

24

pub struct LtsBuilder<L> {

25

    transition_from: ByteCompressedVec<StateIndex>,

26

    transition_labels: ByteCompressedVec<LabelIndex>,

27

    transition_to: ByteCompressedVec<StateIndex>,

28

29

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

30

    labels_index: HashMap<L, LabelIndex>,

31

    labels: Vec<L>,

32

33

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

34

    num_of_states: usize,

35

36

37

impl<L: TransitionLabel> LtsBuilder<L> {

38

    /// Initializes a new empty builder.

39

101

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

40

101

        Self::with_capacity(labels, hidden_labels, 0, 0, 0)

41

101

42

43

    /// Initializes the builder with pre-allocated capacity for states and transitions. The number of labels

44

    /// can be used when labels are added dynamically.

45

211

    pub fn with_capacity(

46

211

        mut labels: Vec<L>,

47

211

        hidden_labels: Vec<String>,

48

211

        num_of_labels: usize,

49

211

        num_of_states: usize,

50

211

        num_of_transitions: usize,

51

211

    ) -> Self {

52

        // Remove duplicates from the labels.

53

211

        labels.sort();

54

211

        labels.dedup();

55

56

        // Introduce the fixed 0-indexed tau label.

57

211

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

58

            labels.swap(0, tau_pos);

59

211

        } else {

60

211

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

61

211

62

63

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

64

211

        let mut labels_index = HashMap::new();

65

211

        labels_index.insert(L::tau_label(), LabelIndex::new(0));

66

211

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

67

211

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

68

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

69

211

            } else {

70

211

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

71

211

72

73

74

211

        Self {

75

211

            transition_from: ByteCompressedVec::with_capacity(num_of_transitions, num_of_states.bytes_required()),

76

211

            transition_labels: ByteCompressedVec::with_capacity(

77

211

                num_of_transitions,

78

211

                num_of_labels.max(labels.len()).bytes_required(),

79

211

),

80

211

            transition_to: ByteCompressedVec::with_capacity(num_of_transitions, num_of_states.bytes_required()),

81

211

            labels_index,

82

211

            labels,

83

211

            num_of_states: 0,

84

211

85

211

86

87

    /// Adds a transition to the builder. For efficiently reasons, we can use

88

    /// another type `Q` for the label.

89

190589

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

90

190589

    where

91

190589

        L: Borrow<Q>,

92

190589

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

93

94

190589

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

95

189947

            index

96

        } else {

97

642

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

98

642

            self.labels_index.insert(label.to_owned(), index);

99

642

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

100

642

            index

101

};

102

103

190589

        self.transition_from.push(from);

104

190589

        self.transition_labels.push(label_index);

105

190589

        self.transition_to.push(to);

106

107

        // Update the number of states.

108

190589

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

109

190589

110

111

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

112

211

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

113

211

        LabelledTransitionSystem::new(

114

211

            initial_state,

115

211

            Some(self.num_of_states),

116

422

            || self.iter(),

117

211

            self.labels.clone(),

118

119

211

120

121

    /// Returns the number of transitions added to the builder.

122

190589

    pub fn num_of_transitions(&self) -> usize {

123

190589

        self.transition_from.len()

124

190589

125

126

    /// Returns the number of states added to the builder.

127

    pub fn num_of_states(&self) -> usize {

128

        self.num_of_states

129

130

131

    /// Ensures that the builder has at least the given number of states.

132

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

133

        if num_of_states > self.num_of_states {

134

            self.num_of_states = num_of_states;

135

136

137

138

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

139

422

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

140

422

        self.transition_from

141

422

            .iter()

142

422

            .zip(self.transition_labels.iter())

143

422

            .zip(self.transition_to.iter())

144

381178

            .map(|((from, label), to)| (from, label, to))

145

422

146

147

148

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

149

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

150

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

151

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

152

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

153

154

        Ok(())

155

156