1
#![forbid(unsafe_code)]
2

            
3
use std::borrow::Borrow;
4
use std::f64::consts::LOG10_2;
5
use std::hash::Hash;
6
use std::io::BufWriter;
7
use std::io::Seek;
8
use std::io::SeekFrom;
9
use std::io::Write;
10
use std::marker::PhantomData;
11

            
12
use merc_utilities::MercError;
13

            
14
use crate::AUT_TAU_LABEL;
15
use crate::LtsBuilder;
16
use crate::MCRL2_TAU_LABEL;
17
use crate::StateIndex;
18
use crate::TransitionLabel;
19

            
20
/// A stream writer for the AUT format, which allows writing an LTS to a file
21
/// without keeping the entire LTS in memory. The header of the AUT file is
22
/// written at the end, after all transitions have been added, to ensure that
23
/// the correct number of states and transitions is included in the header.
24
pub struct AutStream<W: Write, L> {
25
    writer: BufWriter<W>,
26

            
27
    /// The dialect to use when writing tau labels.
28
    format: AutFormat,
29

            
30
    /// Keep track of the number of transitions added.
31
    number_of_transitions: usize,
32

            
33
    /// Keep track of the number of states added.
34
    number_of_states: usize,
35

            
36
    /// Number of bytes reserved for the header line (including its trailing
37
    /// newline). The real header is padded to exactly this width in
38
    /// [`AutStream::finish`] so the placeholder is fully overwritten.
39
    header_len: usize,
40

            
41
    /// Records the label type without affecting the auto traits of the stream:
42
    /// the labels themselves are never stored, so an `AutStream` stays `Send`
43
    /// and `Sync` (so it can be wrapped in a [`crate::MutexLtsBuilder`] and shared
44
    /// across worker threads) even when `L` is neither — for example mCRL2
45
    /// multi-action labels backed by a thread-local `ATerm`.
46
    _marker: PhantomData<fn() -> L>,
47
}
48

            
49
impl<W: Write, L> AutStream<W, L> {
50
    /// Creates a new AUT stream writer in the standard Aldebaran format
51
    /// (`i` is used as the tau label).
52
    ///
53
    /// Note that the writer is buffered internally using a `BufWriter`. Writing
54
    /// the placeholder header can fail, so this returns a [`Result`].
55
101
    pub fn new(writer: W) -> Result<Self, MercError> {
56
101
        Self::with_format(writer, AutFormat::Aut)
57
101
    }
58

            
59
    /// Creates a new AUT stream writer in the mCRL2 dialect
60
    /// (`tau` is used as the tau label).
61
    pub fn new_mcrl2(writer: W) -> Result<Self, MercError> {
62
        Self::with_format(writer, AutFormat::AutMcrl2)
63
    }
64

            
65
    /// Creates a new AUT stream writer using the given format.
66
101
    pub fn with_format(writer: W, format: AutFormat) -> Result<Self, MercError> {
67
101
        let mut writer = BufWriter::new(writer);
68
        // Write a placeholder for the header, which will be filled in later.
69
        // Reserve enough space for the header using the number of bits of
70
        // usize. This avoids overwriting transition bytes when the final header
71
        // is longer.
72
101
        let max_usize_digits = (usize::BITS as f64 * LOG10_2).ceil() as usize;
73
101
        let header_len = format!("des ({0:<1$}, {0:<1$}, {0:<1$})\n", " ", max_usize_digits).len();
74
101
        writer.write_all(" ".repeat(header_len).as_bytes())?;
75

            
76
101
        Ok(Self {
77
101
            writer,
78
101
            format,
79
101
            number_of_transitions: 0,
80
101
            number_of_states: 0,
81
101
            header_len,
82
101
            _marker: PhantomData,
83
101
        })
84
101
    }
85
}
86

            
87
impl<W: Write + Seek, L: TransitionLabel> LtsBuilder<L> for AutStream<W, L> {
88
    type LTS = ();
89

            
90
100582
    fn add_transition<Q>(&mut self, from: StateIndex, label: &Q, to: StateIndex) -> Result<(), MercError>
91
100582
    where
92
100582
        L: Borrow<Q>,
93
100582
        Q: ?Sized + ToOwned<Owned = L> + Eq + Hash,
94
    {
95
100582
        self.number_of_transitions += 1;
96
100582
        self.number_of_states = self.number_of_states.max(from.value() + 1).max(to.value() + 1);
97

            
98
100582
        let owned = label.to_owned();
99
100582
        if owned.is_tau_label() {
100
33276
            writeln!(self.writer, "({}, \"{}\", {})", from, self.format.tau_label_str(), to)?;
101
        } else {
102
67306
            writeln!(self.writer, "({}, \"{}\", {})", from, owned, to)?;
103
        }
104
100582
        Ok(())
105
100582
    }
106

            
107
101
    fn finish(&mut self, initial_state: StateIndex) -> Result<Self::LTS, MercError> {
108
        // Flush to ensure all buffered transitions are written
109
101
        self.writer.flush()?;
110

            
111
        // Seek to the start and overwrite the header. The real header is padded
112
        // with trailing spaces to fill the entire reserved region (its trailing
113
        // newline lands as the last reserved byte), so no leftover placeholder
114
        // spaces remain to form a spurious, invalid transition line on read —
115
        // which matters in particular when there are no transitions at all.
116
101
        self.writer.seek(SeekFrom::Start(0))?;
117
101
        let header = format!(
118
            "des ({}, {}, {})",
119
            initial_state, self.number_of_transitions, self.number_of_states
120
        );
121
101
        writeln!(self.writer, "{:<1$}", header, self.header_len - 1)?;
122

            
123
        // Flush the updated header
124
101
        self.writer.flush()?;
125
101
        Ok(())
126
101
    }
127

            
128
    /// Returns the number of transitions added to the builder.
129
    fn num_of_transitions(&self) -> usize {
130
        self.number_of_transitions
131
    }
132

            
133
    /// Returns the number of states added to the builder.
134
    fn num_of_states(&self) -> usize {
135
        self.number_of_states
136
    }
137

            
138
    /// Sets the number of states to at least the given number. All states
139
    /// without transitions simply become deadlock states.
140
101
    fn require_num_of_states(&mut self, num_states: usize) {
141
101
        if num_states > self.number_of_states {
142
17
            self.number_of_states = num_states;
143
84
        }
144
101
    }
145
}
146

            
147
/// The dialect of the AUT format, which controls the textual label used for
148
/// internal (tau) transitions.
149
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
150
#[cfg_attr(feature = "clap", derive(clap::ValueEnum))]
151
pub enum AutFormat {
152
    /// The standard Aldebaran format, which uses `i` for tau transitions.
153
    Aut,
154
    /// The mCRL2 dialect of the Aldebaran format, which uses `tau` for tau transitions.
155
    AutMcrl2,
156
}
157

            
158
impl AutFormat {
159
    /// Returns the string that represents the tau label in this format.
160
33276
    fn tau_label_str(self) -> &'static str {
161
33276
        match self {
162
33276
            AutFormat::Aut => AUT_TAU_LABEL,
163
            AutFormat::AutMcrl2 => MCRL2_TAU_LABEL,
164
        }
165
33276
    }
166
}
167

            
168
#[cfg(test)]
169
mod tests {
170
    use std::io::Cursor;
171

            
172
    use merc_utilities::random_test;
173

            
174
    use crate::AutStream;
175
    use crate::LTS;
176
    use crate::LtsBuilder;
177
    use crate::random_lts;
178
    use crate::read_aut;
179

            
180
    #[test]
181
    #[cfg_attr(miri, ignore)] // Test is too slow under Miri
182
1
    fn test_random_aut_stream_io() {
183
100
        random_test(100, |rng| {
184
100
            let lts = random_lts::<String, _>(rng, 1000, 3);
185

            
186
100
            let mut buffer = Cursor::new(Vec::new());
187
            {
188
100
                let mut stream = AutStream::new(&mut buffer).unwrap();
189

            
190
                // Write all the transitions to the stream.
191
100000
                for state_index in lts.iter_states() {
192
100582
                    for transition in lts.outgoing_transitions(state_index) {
193
100582
                        stream
194
100582
                            .add_transition(state_index, &lts.labels()[transition.label.value()], transition.to)
195
100582
                            .unwrap();
196
100582
                    }
197
                }
198

            
199
100
                stream.require_num_of_states(lts.num_of_states());
200
100
                stream.finish(lts.initial_state_index()).unwrap();
201
            }
202

            
203
            // Rewind the buffer to the beginning before reading.
204
100
            buffer.set_position(0);
205
100
            let result_lts = read_aut(&mut buffer).unwrap();
206

            
207
100
            crate::check_equivalent(&lts, &result_lts);
208
100
        })
209
1
    }
210

            
211
    /// An LTS with no transitions (a single deadlock state) must round-trip:
212
    /// the header placeholder must be fully overwritten so no line of leftover
213
    /// padding spaces is left behind for the reader to choke on.
214
    #[test]
215
1
    fn test_aut_stream_no_transitions() {
216
1
        let mut buffer = Cursor::new(Vec::new());
217
1
        {
218
1
            let mut stream: AutStream<_, String> = AutStream::new(&mut buffer).unwrap();
219
1
            stream.require_num_of_states(1);
220
1
            stream.finish(crate::StateIndex::new(0)).unwrap();
221
1
        }
222

            
223
1
        buffer.set_position(0);
224
1
        let result_lts = read_aut(&mut buffer).unwrap();
225

            
226
1
        assert_eq!(result_lts.num_of_states(), 1);
227
1
        assert_eq!(result_lts.num_of_transitions(), 0);
228
1
    }
229
}