1
use std::fmt;
2

            
3
/// The index type for a label.
4
pub type LabelIndex = usize;
5

            
6
/// The index for a state.
7
pub type StateIndex = usize;
8

            
9
/// Represents a labelled transition system consisting of states with directed
10
/// labelled edges.
11
#[derive(PartialEq, Eq)]
12
pub struct LabelledTransitionSystem {
13
    states: Vec<State>,
14
    transitions: Vec<(LabelIndex, StateIndex)>,
15

            
16
    labels: Vec<String>,
17
    hidden_labels: Vec<String>,
18

            
19
    initial_state: StateIndex,
20

            
21
    num_of_transitions: usize,
22
}
23

            
24
impl LabelledTransitionSystem {
25

            
26
    /// Creates a new a labelled transition system with the given transitions, labels, and hidden labels.
27
    /// 
28
    /// The initial state is the state with the given index.
29
    /// num_of_states is the number of states in the LTS, if known. If None then deadlock states without incoming transitions are removed.
30
207
    pub fn new<I, F>(
31
207
        initial_state: StateIndex,
32
207
        num_of_states: Option<usize>,
33
207
        transition_iter: F,
34
207
        mut labels: Vec<String>,
35
207
        hidden_labels: Vec<String>,
36
207
    ) -> LabelledTransitionSystem 
37
207
    where F: Fn() -> I,
38
207
          I:Iterator<Item = (StateIndex, LabelIndex, StateIndex)> {
39
207

            
40
207
        let mut states = Vec::new();
41
207
        if let Some(num_of_states) = num_of_states {
42
206
            states.resize_with(num_of_states, Default::default);
43
206
        }
44

            
45
        // Count the number of transitions for every state
46
207
        let mut num_of_transitions = 0;
47
1635588
        for (from, _, to) in transition_iter() {
48
            // Ensure that the states vector is large enough.
49
1635593
            while states.len() <= from.max(to) {
50
5
                states.push(State::default());
51
5
            }
52

            
53
1635588
            states[from].outgoing_end += 1;
54
1635588
            num_of_transitions += 1;
55
        }
56

            
57
        // Track the number of transitions before every state.
58
942199
        states.iter_mut().fold(0, |count, state| {
59
942199
            let result = count + state.outgoing_end;
60
942199
            state.outgoing_start = count;
61
942199
            state.outgoing_end = count;
62
942199
            result
63
942199
        });
64
207
        
65
207
        // Place the transitions, and increment the end for every state.
66
207
        let mut transitions = vec![(0, 0); num_of_transitions];
67
1635588
        for (from, label, to) in transition_iter() {
68
1635588
            transitions[states[from].outgoing_end] = (label, to);
69
1635588
            states[from].outgoing_end += 1;
70
1635588
        }
71

            
72
        // Keep track of which label indexes are hidden labels.
73
207
        let mut hidden_indices: Vec<usize> = Vec::new();
74
756
        for label in &hidden_labels {
75
556581
            if let Some(index) = labels.iter().position(|other| other == label) {
76
423
                hidden_indices.push(index);
77
423
            }
78
        }
79
207
        hidden_indices.sort();
80

            
81
        // Make an implicit tau label the first label.
82
207
        let introduced_tau = if hidden_indices.contains(&0) {
83
185
            labels[0] = "tau".to_string();
84
185
            false
85
        } else {
86
22
            labels.insert(0, "tau".to_string());
87
22
            true
88
        };
89

            
90
        // Remap all hidden actions to zero.
91
942406
        for state in &mut states {
92
1635607
            for (label, _) in &mut transitions[state.outgoing_start..state.outgoing_end] {
93
1635588
                if hidden_indices.binary_search(label).is_ok() {
94
544193
                    *label = 0;
95
544193
                } 
96
1091395
                else if introduced_tau
97
132147
                {
98
132147
                    // Remap the zero action to the original first hidden index.
99
132147
                    *label += 1;
100
959248
                }
101
            }
102
        } 
103

            
104
207
        LabelledTransitionSystem {
105
207
            initial_state,
106
207
            labels,
107
207
            hidden_labels,
108
207
            states,
109
207
            num_of_transitions: transitions.len(),
110
207
            transitions,
111
207
        }
112
207
    }
113

            
114
    /// Returns the index of the initial state
115
404
    pub fn initial_state_index(&self) -> StateIndex {
116
404
        self.initial_state
117
404
    }
118

            
119
    /// Returns the set of outgoing transitions for the given state.
120
84286973
    pub fn outgoing_transitions(&self, state_index: usize) -> impl Iterator<Item = &(LabelIndex, StateIndex)> {
121
84286973
        let state = &self.states[state_index];
122
84286973
        self.transitions[state.outgoing_start..state.outgoing_end].iter()
123
84286973
    }
124

            
125
    /// Iterate over all state_index in the labelled transition system
126
1789
    pub fn iter_states(&self) -> impl Iterator<Item = StateIndex> {
127
1789
        0..self.states.len()
128
1789
    }
129

            
130
    /// Returns the number of states.
131
2222
    pub fn num_of_states(&self) -> StateIndex {
132
2222
        self.states.len()
133
2222
    }
134

            
135
    /// Returns the number of labels.
136
378025
    pub fn num_of_labels(&self) -> LabelIndex {
137
378025
        self.labels.len()
138
378025
    }
139

            
140
    /// Returns the number of transitions.
141
64
    pub fn num_of_transitions(&self) -> usize {
142
64
        self.num_of_transitions
143
64
    }
144

            
145
    /// Returns the list of labels.
146
452
    pub fn labels(&self) -> &[String] {
147
452
        &self.labels[0..]
148
452
    }
149

            
150
    /// Returns the list of hidden labels.
151
173
    pub fn hidden_labels(&self) -> &[String] {
152
173
        &self.hidden_labels[0..]
153
173
    }
154

            
155
    /// Returns true iff the given label index is a hidden label.
156
232093145
    pub fn is_hidden_label(&self, label_index: LabelIndex) -> bool {
157
232093145
        label_index == 0
158
232093145
    }
159
}
160

            
161
/// A single state in the LTS, containing a vector of outgoing edges.
162
#[derive(Clone, Default, PartialEq, Eq)]
163
struct State {
164
    outgoing_start: usize,
165
    outgoing_end: usize,
166
}
167

            
168
impl fmt::Display for LabelledTransitionSystem {
169
3
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
170
3
        // Print some information about the LTS.
171
3
        writeln!(f, "Number of states: {}", self.states.len())?;
172
3
        writeln!(f, "Number of action labels: {}", self.labels.len())?;
173
3
        write!(f, "Number of transitions: {}", self.num_of_transitions)
174
3
    }
175
}
176

            
177
impl fmt::Debug for LabelledTransitionSystem {
178
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
179
        writeln!(f, "{}", self)?;
180
        writeln!(f, "Initial state: {}", self.initial_state)?;
181
        writeln!(f, "Hidden labels: {:?}", self.hidden_labels)?;
182

            
183
        for state_index in self.iter_states() {
184
            for &(label, to) in self.outgoing_transitions(state_index) {
185
                let label_name = &self.labels[label];
186

            
187
                writeln!(f, "{state_index} --[{label_name}]-> {to}")?;
188
            }
189
        }
190

            
191
        Ok(())
192
    }
193
}