1
use std::collections::HashMap;
2
use std::fmt;
3
use std::io::Read;
4

            
5
use log::info;
6
use merc_utilities::MercError;
7
use oxidd::ManagerRef;
8
use oxidd::ldd::LDDFunction;
9
use oxidd::ldd::LDDManagerRef;
10
use oxidd::ldd::Value;
11

            
12
use crate::SymbolicLPS;
13
use crate::TransitionGroup;
14

            
15
/// Returns the (initial state, transitions) read from the file in Sylvan's format.
16
5
pub fn read_sylvan<R: Read>(manager: &LDDManagerRef, stream: &mut R) -> Result<SylvanLts, MercError> {
17
5
    info!("Reading symbolic LTS in Sylvan format...");
18
5
    let mut reader = SylvanReader::new();
19

            
20
5
    let _vector_length = read_u32(stream)?;
21

            
22
5
    let _unused = read_u32(stream)?; // This is called 'k' in Sylvan's ldd2bdd.c, but unused.
23
5
    let initial_state = reader.read_ldd(manager, stream)?;
24
5
    let num_transitions: usize = read_u32(stream)? as usize;
25
5
    let mut groups: Vec<SylvanTransitionGroup> = Vec::new();
26

            
27
    // Read all the transition groups.
28
5
    for _ in 0..num_transitions {
29
120
        let (read_proj, write_proj) = read_projection(stream)?;
30

            
31
120
        let (meta, empty) = manager.with_manager_shared(|m| -> Result<_, MercError> {
32
120
            let meta = LDDFunction::relation_product_meta(m, &read_proj, &write_proj)?.meta;
33
120
            Ok((meta, LDDFunction::empty_set(m)?))
34
120
        })?;
35
120
        groups.push(SylvanTransitionGroup::new(empty, meta, read_proj, write_proj));
36
    }
37

            
38
120
    for transition in groups.iter_mut().take(num_transitions) {
39
120
        transition.relation = reader.read_ldd(manager, stream)?;
40
    }
41

            
42
5
    Ok(SylvanLts::new(initial_state, groups))
43
5
}
44

            
45
/// Reads the read and write projections from the given stream.
46
120
pub fn read_projection<R: Read>(file: &mut R) -> Result<(Vec<Value>, Vec<Value>), MercError> {
47
120
    let num_read = read_u32(file)?;
48
120
    let num_write = read_u32(file)?;
49

            
50
    // Read num_read integers for the read parameters.
51
120
    let mut read_proj: Vec<Value> = Vec::new();
52
120
    for _ in 0..num_read {
53
340
        let value = read_u32(file)?;
54
340
        read_proj.push(value as Value);
55
    }
56

            
57
    // Read num_write integers for the write parameters.
58
120
    let mut write_proj: Vec<Value> = Vec::new();
59
120
    for _ in 0..num_write {
60
360
        let value = read_u32(file)?;
61
360
        write_proj.push(value as Value);
62
    }
63

            
64
120
    Ok((read_proj, write_proj))
65
120
}
66

            
67
/// A symbolic labelled transition system read from a Sylvan file.
68
pub struct SylvanLts {
69
    initial_state: LDDFunction,
70
    transition_groups: Vec<SylvanTransitionGroup>,
71
}
72

            
73
impl SylvanLts {
74
    /// Creates a new Sylvan LTS.
75
5
    pub fn new(initial_state: LDDFunction, transition_groups: Vec<SylvanTransitionGroup>) -> Self {
76
5
        Self {
77
5
            initial_state,
78
5
            transition_groups,
79
5
        }
80
5
    }
81
}
82

            
83
impl SymbolicLPS for SylvanLts {
84
    type Group = SylvanTransitionGroup;
85

            
86
10
    fn initial_state(&self) -> &LDDFunction {
87
10
        &self.initial_state
88
10
    }
89

            
90
    fn transition_groups(&self) -> &[Self::Group] {
91
        &self.transition_groups
92
    }
93

            
94
230
    fn transition_groups_mut(&mut self) -> &mut [Self::Group] {
95
230
        &mut self.transition_groups
96
230
    }
97

            
98
5
    fn create_context(&self) {}
99
}
100

            
101
/// A transition group read from a Sylvan file.
102
pub struct SylvanTransitionGroup {
103
    relation: LDDFunction,
104
    meta: LDDFunction,
105
    read_proj: Vec<u32>,
106
    write_proj: Vec<u32>,
107
}
108

            
109
impl SylvanTransitionGroup {
110
    /// Creates a new Sylvan transition group.
111
124
    pub fn new(relation: LDDFunction, meta: LDDFunction, read_proj: Vec<u32>, write_proj: Vec<u32>) -> Self {
112
124
        Self {
113
124
            relation,
114
124
            meta,
115
124
            read_proj,
116
124
            write_proj,
117
124
        }
118
124
    }
119
}
120

            
121
impl TransitionGroup for SylvanTransitionGroup {
122
    type Context = ();
123

            
124
7945
    fn relation(&self) -> &LDDFunction {
125
7945
        &self.relation
126
7945
    }
127

            
128
    fn read_indices(&self) -> &[u32] {
129
        &self.read_proj
130
    }
131

            
132
    fn write_indices(&self) -> &[u32] {
133
        &self.write_proj
134
    }
135

            
136
    fn action_label_index(&self) -> Option<usize> {
137
        None
138
    }
139

            
140
7945
    fn meta(&self) -> &LDDFunction {
141
7945
        &self.meta
142
7945
    }
143

            
144
5530
    fn learn_successors(
145
5530
        &mut self,
146
5530
        _context: &mut (),
147
5530
        _manager: &LDDManagerRef,
148
5530
        _todo: &LDDFunction,
149
5530
    ) -> Result<(), MercError> {
150
        // All states are already explored.
151
5530
        Ok(())
152
5530
    }
153
}
154

            
155
impl fmt::Debug for SylvanTransitionGroup {
156
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
157
        f.debug_struct("SylvanTransitionGroup")
158
            .field("read_proj", &self.read_proj)
159
            .field("write_proj", &self.write_proj)
160
            .finish()
161
    }
162
}
163

            
164
/// A reader for LDDs in the Sylvan .ldd format.
165
pub struct SylvanReader {
166
    indexed_set: HashMap<u64, LDDFunction>, // Assigns LDDs to every index.
167
    last_index: u64,                        // The index of the last LDD read from file.
168
}
169

            
170
impl SylvanReader {
171
5
    pub fn new() -> Self {
172
5
        Self {
173
5
            indexed_set: HashMap::new(),
174
5
            last_index: 2,
175
5
        }
176
5
    }
177

            
178
    /// Returns an LDD read from the given stream in the Sylvan format.
179
125
    pub fn read_ldd<R: Read>(&mut self, manager: &LDDManagerRef, stream: &mut R) -> Result<LDDFunction, MercError> {
180
125
        let count = read_u64(stream)?;
181

            
182
125
        for _ in 0..count {
183
            // Read a single MDD node. It has the following structure: u64 | u64
184
            // RmRR RRRR RRRR VVVV | VVVV DcDD DDDD DDDD (little endian)
185
            // Every character is 4 bits, V = value, D = down, R = right, m = marked, c = copy.
186
1025
            let a = read_u64(stream)?;
187
1025
            let b = read_u64(stream)?;
188
1025
            let right = (a & 0x0000ffffffffffff) >> 1;
189
1025
            let down = b >> 17;
190

            
191
1025
            let mut bytes: [u8; 4] = Default::default();
192
1025
            bytes[0..2].copy_from_slice(&a.to_le_bytes()[6..8]);
193
1025
            bytes[2..4].copy_from_slice(&b.to_le_bytes()[0..2]);
194
1025
            let value = u32::from_le_bytes(bytes);
195

            
196
1025
            let copy = right & 0x10000;
197
1025
            if copy != 0 {
198
                return Err("Sylvan copy nodes are not supported".into());
199
1025
            }
200

            
201
1025
            let down = self.node_from_index(manager, down)?;
202
1025
            let right = self.node_from_index(manager, right)?;
203

            
204
1025
            let ldd = manager.with_manager_shared(|m| LDDFunction::make_node(m, value as Value, &down, &right))?;
205
1025
            self.indexed_set.insert(self.last_index, ldd);
206

            
207
1025
            self.last_index += 1;
208
        }
209

            
210
125
        let result = read_u64(stream)?;
211
125
        self.node_from_index(manager, result)
212
125
    }
213

            
214
    /// Returns the LDD belonging to the given index.
215
2175
    fn node_from_index(&self, manager: &LDDManagerRef, index: u64) -> Result<LDDFunction, MercError> {
216
2175
        if index == 0 {
217
820
            Ok(manager.with_manager_shared(|m| LDDFunction::empty_set(m))?)
218
1355
        } else if index == 1 {
219
5
            Ok(manager.with_manager_shared(|m| LDDFunction::empty_vector(m))?)
220
        } else {
221
1350
            Ok(self
222
1350
                .indexed_set
223
1350
                .get(&index)
224
1350
                .ok_or_else(|| {
225
                    format!(
226
                        "LDD index {index} not found in table of {} entries",
227
                        self.indexed_set.len()
228
                    )
229
                })?
230
1350
                .clone())
231
        }
232
2175
    }
233
}
234

            
235
impl Default for SylvanReader {
236
    fn default() -> Self {
237
        Self::new()
238
    }
239
}
240

            
241
/// Returns a single u32 read from the given stream.
242
955
pub fn read_u32<R: Read>(stream: &mut R) -> Result<u32, MercError> {
243
955
    let mut buffer: [u8; 4] = Default::default();
244
955
    stream.read_exact(&mut buffer)?;
245

            
246
955
    Ok(u32::from_le_bytes(buffer))
247
955
}
248

            
249
/// Returns a single u64 read from the given stream.
250
2300
pub fn read_u64<R: Read>(stream: &mut R) -> Result<u64, MercError> {
251
2300
    let mut buffer: [u8; 8] = Default::default();
252
2300
    stream.read_exact(&mut buffer)?;
253

            
254
2300
    Ok(u64::from_le_bytes(buffer))
255
2300
}
256

            
257
#[cfg(test)]
258
mod test {
259
    use merc_utilities::Timing;
260

            
261
    use crate::reachability;
262

            
263
    use super::read_sylvan;
264

            
265
    #[test]
266
    #[cfg_attr(miri, ignore)] // Miri is too slow
267
1
    fn test_load_anderson_4() {
268
1
        let ldd_manager = oxidd::ldd::new_manager(2048, 1024, 1);
269
1
        let bytes = include_bytes!("../../../../examples/ldd/anderson.4.ldd");
270
1
        let mut lts = read_sylvan(&ldd_manager, &mut &bytes[..]).expect("Loading should work correctly");
271
1
        reachability(&ldd_manager, &mut lts, &Timing::new()).expect("Reachability should work correctly");
272
1
    }
273

            
274
    #[test]
275
    #[cfg_attr(miri, ignore)] // Miri is too slow
276
    #[cfg(not(debug_assertions))]
277
    fn test_load_collision_4() {
278
        let ldd_manager = oxidd::ldd::new_manager(2048, 1024, 1);
279
        let bytes = include_bytes!("../../../../examples/ldd/collision.4.ldd");
280
        let mut lts = read_sylvan(&ldd_manager, &mut &bytes[..]).expect("Loading should work correctly");
281
        reachability(&ldd_manager, &mut lts, &Timing::new()).expect("Reachability should work correctly");
282
    }
283
}