1
#![forbid(unsafe_code)]
2

            
3
use std::io::BufWriter;
4
use std::io::Read;
5
use std::io::Write;
6

            
7
use log::info;
8
use merc_io::LargeFormatter;
9
use regex::Regex;
10
use streaming_iterator::StreamingIterator;
11
use thiserror::Error;
12

            
13
use merc_io::LineIterator;
14
use merc_io::TimeProgress;
15
use merc_utilities::MercError;
16
use merc_utilities::debug_trace;
17

            
18
use crate::LTS;
19
use crate::LabelledTransitionSystem;
20
use crate::LtsBuilder;
21
use crate::LtsBuilderMem;
22
use crate::StateIndex;
23
use crate::TransitionLabel;
24

            
25
#[derive(Error, Debug)]
26
pub enum IOError {
27
    #[error("Invalid .aut header {0}")]
28
    InvalidHeader(&'static str),
29

            
30
    #[error("Invalid transition {0}")]
31
    InvalidTransition(String),
32
}
33

            
34
/// The label used for internal transitions in the mCRL2 format.
35
const MCRL2_TAU_LABEL: &str = "tau";
36

            
37
/// The label used for internal transitions in the Aldebaran format.
38
const AUT_TAU_LABEL: &str = "i";
39

            
40
/// Loads a labelled transition system in the [Aldebaran
41
/// format](https://cadp.inria.fr/man/aldebaran.html) from the given reader.
42
///
43
/// Note that the reader has a buffer in the form of  `BufReader`` internally.
44
///
45
/// The Aldebaran format consists of a header: `des (<initial>: Nat,
46
///     <num_of_transitions>: Nat, <num_of_states>: Nat)`
47
///     
48
/// And one line for every transition either one of these cases:
49
///  `(<from>: Nat, "<label>": Str, <to>: Nat)`
50
///  `(<from>: Nat, <label>: Str, <to>: Nat)`
51
214
pub fn read_aut<R: Read>(reader: R) -> Result<LabelledTransitionSystem<String>, MercError> {
52
214
    read_aut_impl(reader, AUT_TAU_LABEL)
53
214
}
54

            
55
/// The same as [read_aut], but with the `tau` as the internal transition, instead of `i`.
56
pub fn read_mcrl2_aut<R: Read>(reader: R) -> Result<LabelledTransitionSystem<String>, MercError> {
57
    read_aut_impl(reader, MCRL2_TAU_LABEL)
58
}
59

            
60
/// The implementation of [read_aut] and [read_aut_mcrl2].
61
///
62
/// The `tau_label` specifics which label is considered as the internal transition.
63
214
fn read_aut_impl<R: Read>(reader: R, tau_label: &str) -> Result<LabelledTransitionSystem<String>, MercError> {
64
214
    info!("Reading LTS in .aut format...");
65

            
66
214
    let mut lines = LineIterator::new(reader);
67
214
    lines.advance();
68
214
    let header = lines
69
214
        .get()
70
214
        .ok_or(IOError::InvalidHeader("The first line should be the header"))?;
71

            
72
    // Regex for des (<initial>: Nat, <num_of_states>: Nat, <num_of_transitions>: Nat)
73
214
    let header_regex = Regex::new(r#"des\s*\(\s*([0-9]*)\s*,\s*([0-9]*)\s*,\s*([0-9]*)\s*\)\s*"#)
74
214
        .expect("Regex compilation should not fail");
75

            
76
214
    let (_, [initial_txt, num_of_transitions_txt, num_of_states_txt]) = header_regex
77
214
        .captures(header)
78
214
        .ok_or(IOError::InvalidHeader(
79
214
            "does not match des (<init>, <num_of_transitions>, <num_of_states>)",
80
214
        ))?
81
212
        .extract();
82

            
83
212
    let initial_state = StateIndex::new(initial_txt.parse()?);
84
212
    let num_of_transitions: usize = num_of_transitions_txt.parse()?;
85
212
    let num_of_states: usize = num_of_states_txt.parse()?;
86

            
87
212
    let mut builder = LtsBuilderMem::with_capacity(
88
212
        Vec::new(),
89
212
        vec![tau_label.to_string()],
90
        16,
91
212
        num_of_states,
92
212
        num_of_transitions,
93
    );
94
212
    builder.require_num_of_states(num_of_states);
95

            
96
212
    let progress = TimeProgress::new(
97
        move |read: usize| {
98
            info!(
99
                "Read {} transitions {}%...",
100
                LargeFormatter(read),
101
                read * 100 / num_of_transitions
102
            )
103
        },
104
        1,
105
    );
106

            
107
202115
    while let Some(line) = lines.next() {
108
201903
        let (from_txt, label_txt, to_txt) =
109
201903
            read_transition(line).ok_or_else(|| IOError::InvalidTransition(line.clone()))?;
110

            
111
        // Parse the from and to states, with the given label.
112
201903
        let from = StateIndex::new(from_txt.parse()?);
113
201903
        let to = StateIndex::new(to_txt.parse()?);
114

            
115
201903
        debug_trace!("Read transition {from} --[{label_txt}]-> {to}");
116
201903
        builder.add_transition(from, label_txt, to)?;
117

            
118
201903
        progress.print(builder.num_of_transitions());
119
    }
120

            
121
212
    info!("Finished reading LTS");
122

            
123
212
    builder.finish(initial_state)
124
214
}
125

            
126
/// Write a labelled transition system in plain text in Aldebaran format to the
127
/// given writer, see [read_aut].
128
///
129
/// Note that the writer is buffered internally using a `BufWriter`.
130
101
pub fn write_aut<W: Write, L: LTS>(writer: &mut W, lts: &L) -> Result<(), MercError> {
131
101
    write_aut_impl(writer, lts, AUT_TAU_LABEL)
132
101
}
133

            
134
/// The same as [write_aut], but with the `tau` as the internal transition, instead of `i`.
135
pub fn write_mcrl2_aut<W: Write, L: LTS>(writer: &mut W, lts: &L) -> Result<(), MercError> {
136
    write_aut_impl(writer, lts, MCRL2_TAU_LABEL)
137
}
138

            
139
/// The implementation of [write_aut] and [write_mcrl2_aut].
140
101
fn write_aut_impl<W: Write, L: LTS>(writer: &mut W, lts: &L, tau_label: &str) -> Result<(), MercError> {
141
101
    info!("Writing LTS in .aut format...");
142

            
143
101
    let mut writer = BufWriter::new(writer);
144
101
    writeln!(
145
101
        writer,
146
        "des ({}, {}, {})",
147
101
        lts.initial_state_index(),
148
101
        lts.num_of_transitions(),
149
101
        lts.num_of_states()
150
    )?;
151

            
152
101
    let num_of_transitions = lts.num_of_transitions();
153
101
    let progress = TimeProgress::new(
154
        move |written: usize| {
155
            info!(
156
                "Wrote {} transitions {}%...",
157
                LargeFormatter(written),
158
                written * 100 / num_of_transitions
159
            )
160
        },
161
        1,
162
    );
163
101
    let mut transitions_written = 0usize;
164
100074
    for state_index in lts.iter_states() {
165
100193
        for transition in lts.outgoing_transitions(state_index) {
166
100193
            if lts.is_hidden_label(transition.label) {
167
33505
                writeln!(writer, "({}, \"{}\", {})", state_index, tau_label, transition.to)?;
168
            } else {
169
66688
                writeln!(
170
66688
                    writer,
171
                    "({}, \"{}\", {})",
172
                    state_index,
173
66688
                    lts.labels()[transition.label.value()],
174
                    transition.to
175
                )?;
176
            }
177

            
178
100193
            progress.print(transitions_written);
179
100193
            transitions_written += 1;
180
        }
181
    }
182

            
183
101
    info!("Finished writing LTS.");
184
101
    Ok(())
185
101
}
186

            
187
/// Dedicated function to parse the following transition formats:
188
///
189
/// # Details
190
///
191
/// One of the following formats:
192
///     `(<from>: Nat, "<label>": Str, <to>: Nat)`
193
///     `(<from>: Nat, <label>: Str, <to>: Nat)`
194
///
195
/// This was generally faster than the regex variant, since that one has to backtrack after
196
218359
fn read_transition(input: &str) -> Option<(&str, &str, &str)> {
197
218359
    let start_paren = input.find('(')?;
198
218359
    let start_comma = input.find(',')?;
199

            
200
    // Find the comma in the second part
201
218359
    let start_second_comma = input.rfind(',')?;
202
218359
    let end_paren = input.rfind(')')?;
203

            
204
218359
    let from = input.get(start_paren + 1..start_comma)?.trim();
205
218359
    let label = input.get(start_comma + 1..start_second_comma)?.trim();
206
218359
    let to = input.get(start_second_comma + 1..end_paren)?.trim();
207
    // Handle the special case where it has quotes.
208
218359
    if label.starts_with('"') && label.ends_with('"') {
209
218203
        return Some((from, &label[1..label.len() - 1], to));
210
156
    }
211

            
212
156
    Some((from, label, to))
213
218359
}
214

            
215
/// A trait for labels that can be used in transitions.
216
impl TransitionLabel for String {
217
883204
    fn is_tau_label(&self) -> bool {
218
883204
        self == "τ"
219
883204
    }
220

            
221
66260
    fn tau_label() -> Self {
222
66260
        "τ".to_string()
223
66260
    }
224

            
225
1944
    fn matches_label(&self, label: &str) -> bool {
226
1944
        self == label
227
1944
    }
228

            
229
115200
    fn from_index(i: usize) -> Self {
230
115200
        char::from_digit(i as u32 + 10, 36)
231
115200
            .expect("Radix is less than 37, so should not panic")
232
115200
            .to_string()
233
115200
    }
234
}
235

            
236
#[cfg(test)]
237
mod tests {
238
    use merc_utilities::random_test;
239
    use test_log::test;
240

            
241
    use crate::LTS;
242
    use crate::random_lts;
243
    use crate::read_aut;
244
    use crate::write_aut;
245

            
246
    #[test]
247
    fn test_reading_aut() {
248
        let file = include_str!("../../../examples/lts/abp.aut");
249

            
250
        let lts = read_aut(file.as_bytes()).unwrap();
251

            
252
        assert_eq!(lts.initial_state_index().value(), 0);
253
        assert_eq!(lts.num_of_transitions(), 92);
254
    }
255

            
256
    #[test]
257
    fn test_lts_failure() {
258
        let wrong_header = "
259
        des (0,2,                                     
260
            (0,\"r1(d1)\",1)
261
            (0,\"r1(d2)\",2)
262
        ";
263

            
264
        debug_assert!(read_aut(wrong_header.as_bytes()).is_err());
265

            
266
        let wrong_transition = "
267
        des (0,2,3)                           
268
            (0,\"r1(d1),1)
269
            (0,\"r1(d2)\",2)
270
        ";
271

            
272
        debug_assert!(read_aut(wrong_transition.as_bytes()).is_err());
273
    }
274

            
275
    #[test]
276
    fn test_traversal_lts() {
277
        let file = include_str!("../../../examples/lts/abp.aut");
278

            
279
        let lts = read_aut(file.as_bytes()).unwrap();
280

            
281
        // Check the number of outgoing transitions of the initial state
282
        assert_eq!(lts.outgoing_transitions(lts.initial_state_index()).count(), 2);
283
    }
284

            
285
    #[test]
286
    fn test_writing_lts() {
287
        let file = include_str!("../../../examples/lts/abp.aut");
288
        let lts_original = read_aut(file.as_bytes()).unwrap();
289

            
290
        // Check that it can be read after writing, and results in the same LTS.
291
        let mut buffer: Vec<u8> = Vec::new();
292
        write_aut(&mut buffer, &lts_original).unwrap();
293

            
294
        let lts = read_aut(&buffer[0..]).unwrap();
295

            
296
        assert!(lts.num_of_states() == lts_original.num_of_states());
297
        assert!(lts.num_of_labels() == lts_original.num_of_labels());
298
        assert!(lts.num_of_transitions() == lts_original.num_of_transitions());
299
    }
300

            
301
    #[test]
302
    #[cfg_attr(miri, ignore)] // Test is too slow under Miri
303
    fn test_random_aut_io() {
304
100
        random_test(100, |rng| {
305
100
            let lts = random_lts::<String, _>(rng, 1000, 3);
306

            
307
100
            let mut buffer: Vec<u8> = Vec::new();
308
100
            write_aut(&mut buffer, &lts).unwrap();
309

            
310
100
            let result_lts = read_aut(&buffer[0..]).unwrap();
311

            
312
100
            crate::check_equivalent(&lts, &result_lts);
313
100
        })
314
    }
315
}