1
use std::ops::Range;
2

            
3
use itertools::Itertools;
4
use log::debug;
5
use log::info;
6
use oxidd::BooleanFunction;
7
use oxidd::Manager;
8
use oxidd::ManagerRef;
9
use oxidd::VarNo;
10
use oxidd::bdd::BDDFunction;
11
use oxidd::bdd::BDDManagerRef;
12
use oxidd::error::DuplicateVarName;
13

            
14
use merc_data::DataExpression;
15
use merc_ldd::Storage;
16
use merc_ldd::Value;
17
use merc_ldd::singleton;
18
use merc_utilities::MercError;
19
use oxidd::util::OutOfMemory;
20

            
21
use crate::SymbolicLTS;
22
use crate::TransitionGroup;
23
use crate::compute_bits;
24
use crate::compute_highest;
25
use crate::ldd_to_bdd;
26
use crate::required_bits;
27

            
28
/// A symbolic LTS that uses BDDs for the symbolic representation, instead of
29
/// LDDs as done in [crate::SymbolicLts].
30
pub struct SymbolicLtsBdd {
31
    /// The BDD representing the set of states.
32
    states: BDDFunction,
33

            
34
    /// The BDD representing the set of initial states.
35
    initial_state: BDDFunction,
36

            
37
    /// The transition groups representing the disjunctive transition relation.
38
    transition_groups: Vec<SummandGroupBdd>,
39

            
40
    /// The number of bits used for each state variable.
41
    state_variable_num_of_bits: Vec<Value>,
42

            
43
    /// The variable numbers used to represent the state variables.
44
    state_variable_indices: Vec<VarNo>,
45

            
46
    /// The variable numbers used to represent the next state variables.
47
    next_state_variables_indices: Vec<VarNo>,
48

            
49
    /// The action variable indices used to represent the action labels.
50
    action_variable_indices: Vec<VarNo>,
51

            
52
    /// The action labels of the LTS, stored as their string representation,
53
    /// their position corresponds to the LDD values.
54
    action_labels: Vec<String>,
55

            
56
    /// The possible values for each process parameter, their position
57
    /// corresponds to the LDD values.
58
    parameter_values: Vec<Vec<DataExpression>>,
59
}
60

            
61
impl SymbolicLtsBdd {
62
    /// Converts a symbolic LTS using LDDs into a symbolic LTS using BDDs.
63
    ///
64
    /// # Details
65
    ///
66
    /// The resulting BDD is assumed to only be valid for the reachable states
67
    /// of the LDD symbolic LTS, as unreachable states may not be representable
68
    /// with the number of bits assigned to each state variable.
69
303
    pub fn from_symbolic_lts<L: SymbolicLTS>(
70
303
        storage: &mut Storage,
71
303
        manager_ref: &BDDManagerRef,
72
303
        lts: &L,
73
303
    ) -> Result<Self, MercError> {
74
303
        info!("Converting symbolic LTS from LDD to BDD representation...");
75

            
76
        // Determine the highest values for every state variable.
77
303
        let mut state_highest = compute_highest(storage, lts.states());
78

            
79
303
        let mut action_label_highest = 0u32;
80
1530
        for group in lts.transition_groups() {
81
1530
            let highest = compute_highest(storage, group.relation());
82

            
83
            // Deal with the special empty case.
84
1530
            if highest.is_empty() {
85
                continue;
86
1530
            }
87

            
88
            action_label_highest =
89
1530
                action_label_highest.max(highest[group.action_label_index().ok_or("Action label index not found")?]);
90

            
91
            // Also consider the highest values read or written for the state
92
            // variables in the relation. LDD levels follow the sorted merge of
93
            // read and write indices (read before write at the same variable).
94
13489
            for (ldd_level, var) in group
95
1530
                .read_indices()
96
1530
                .iter()
97
1530
                .merge(group.write_indices().iter())
98
1530
                .enumerate()
99
13489
            {
100
13489
                let var = *var as usize;
101
13489
                state_highest[var] = state_highest[var].max(highest[ldd_level]);
102
13489
            }
103
        }
104

            
105
303
        let state_bits = compute_bits(&state_highest);
106
303
        debug!("Determined number of bits for state variables: {:?}", state_bits);
107

            
108
303
        let action_label_bits = required_bits(action_label_highest);
109
303
        debug!(
110
            "Highest action label: {}, bits: {}",
111
            action_label_highest, action_label_bits
112
        );
113

            
114
        // Create the state variables, with interleaved primed variables for write parameters
115
303
        let mut vars = Vec::new();
116

            
117
        // Keep track of the bits per state variable.
118
303
        let mut state_variables_bits: Vec<Vec<VarNo>> = Vec::new();
119
303
        let mut next_state_variables_bits: Vec<Vec<VarNo>> = Vec::new();
120
3033
        for (i, &bits) in state_bits.iter().enumerate() {
121
3033
            let mut state_var_bits = Vec::new();
122
3033
            let mut next_state_var_bits = Vec::new();
123
9035
            for k in 0..bits {
124
9035
                // Add variable for the state variable
125
9035
                state_var_bits.push(vars.len() as VarNo);
126
9035
                vars.push(format!("s{}_{}", i, k));
127
9035

            
128
9035
                // Add a primed version for the write parameters
129
9035
                next_state_var_bits.push(vars.len() as VarNo);
130
9035
                vars.push(format!("s{}'_{}", i, k));
131
9035
            }
132
3033
            state_variables_bits.push(state_var_bits);
133
3033
            next_state_variables_bits.push(next_state_var_bits);
134
        }
135

            
136
        // Create action label variables
137
303
        let mut action_labels_vars = Vec::new();
138
915
        for k in 0..action_label_bits {
139
915
            action_labels_vars.push(vars.len() as VarNo);
140
915
            vars.push(format!("a_{}", k));
141
915
        }
142

            
143
        // Check for existing variables.
144
303
        if manager_ref.with_manager_shared(|manager| manager.num_vars()) != 0 {
145
            return Err("BDD manager must not contain any variables yet".into());
146
303
        }
147

            
148
        // Ensure that the BDD manager is empty.
149
303
        manager_ref.with_manager_exclusive(|manager| {
150
303
            debug_assert_eq!(
151
303
                manager.num_vars(),
152
                0,
153
                "A BDD manager can only hold the variables for a single symbolic LTS"
154
            )
155
303
        });
156

            
157
        // Create variables in the BDD manager
158
303
        let number_of_vars = vars.len();
159
303
        let variables = manager_ref
160
303
            .with_manager_exclusive(|manager| -> Result<Range<VarNo>, DuplicateVarName> {
161
303
                manager.add_named_vars(vars)
162
303
            })
163
303
            .map_err(|e| format!("Failed to create variables: {e}"))?;
164

            
165
303
        assert!(variables.clone().is_sorted(), "Variables must be added in sorted order");
166
303
        assert!(
167
303
            variables.len() == number_of_vars,
168
            "Number of created variables does not match"
169
        );
170

            
171
        // Convert the states to a BDD representation.
172
303
        let bits_dd = singleton(storage, &state_bits);
173
303
        let all_state_variables_bits: Vec<VarNo> = state_variables_bits.iter().flatten().cloned().collect();
174
303
        let states = ldd_to_bdd(storage, manager_ref, lts.states(), &bits_dd, &all_state_variables_bits)?;
175
303
        let initial_state = ldd_to_bdd(
176
303
            storage,
177
303
            manager_ref,
178
303
            lts.initial_state(),
179
303
            &bits_dd,
180
303
            &all_state_variables_bits,
181
        )?;
182

            
183
303
        let mut transition_groups = Vec::new();
184
1530
        for (index, group) in lts.transition_groups().iter().enumerate() {
185
            // Determine the number of bits used for each layer.
186
1530
            let mut relation_bits = Vec::new();
187

            
188
            // Determine all the variables used in this relation.
189
1530
            let mut variables = Vec::new();
190

            
191
1530
            let mut read_variable_indices: Vec<VarNo> = Vec::new();
192
1530
            let mut write_variable_indices: Vec<VarNo> = Vec::new();
193

            
194
15330
            for (var, bits) in state_bits.iter().enumerate() {
195
15330
                if group.read_indices().contains(&(var as VarNo)) {
196
                    // The transition group reads this state variable
197
6744
                    relation_bits.push(*bits);
198
6744
                    variables.extend(state_variables_bits[var].iter());
199
6744
                    read_variable_indices.extend(state_variables_bits[var].iter())
200
8586
                }
201

            
202
15330
                if group.write_indices().contains(&(var as VarNo)) {
203
                    // The transition group writes this state variable
204
6745
                    relation_bits.push(*bits);
205
6745
                    variables.extend(next_state_variables_bits[var].iter());
206
6745
                    write_variable_indices.extend(next_state_variables_bits[var].iter())
207
8585
                }
208
            }
209

            
210
            // Append action label bits (between read and write segments) if present
211
1530
            if let Some(_action_index) = group.action_label_index() {
212
1530
                // TODO: This currently assumes that action label bits are at the end.
213
1530
                variables.extend(action_labels_vars.iter());
214
1530
            }
215

            
216
            // Append action label bits
217
1530
            relation_bits.push(action_label_bits);
218
1530
            debug!(
219
                "Transition group {}, {:?} uses number of bits {:?}, and variables: {:?}",
220
                index, group, relation_bits, variables
221
            );
222

            
223
1530
            let bits_dd = singleton(storage, &relation_bits);
224
1530
            let relation_bdd = ldd_to_bdd(storage, manager_ref, group.relation(), &bits_dd, &variables)?;
225

            
226
1530
            transition_groups.push(SummandGroupBdd::new(
227
1530
                relation_bdd,
228
1530
                read_variable_indices,
229
1530
                write_variable_indices,
230
            ));
231
        }
232

            
233
        // Compute the BDDs representing the state variables and next state variables.
234
303
        let all_next_state_variables_bits = next_state_variables_bits
235
303
            .iter()
236
303
            .flatten()
237
303
            .cloned()
238
303
            .collect::<Vec<VarNo>>();
239

            
240
303
        debug!("State bits {all_state_variables_bits:?}, and next state bits {all_next_state_variables_bits:?}");
241

            
242
303
        info!("Finished conversion.");
243
303
        Ok(Self {
244
303
            action_variable_indices: action_labels_vars,
245
303
            states,
246
303
            initial_state,
247
303
            transition_groups,
248
303
            state_variable_num_of_bits: state_bits,
249
303
            state_variable_indices: all_state_variables_bits,
250
303
            next_state_variables_indices: all_next_state_variables_bits,
251
303
            action_labels: lts.action_labels().to_vec(),
252
303
            parameter_values: lts.parameter_values().to_vec(),
253
303
        })
254
303
    }
255

            
256
    /// Constructs a new symbolic LTS with the given transition groups.
257
101
    pub fn with_transition_groups(lts: &Self, transition_groups: Vec<SummandGroupBdd>) -> Self {
258
101
        Self {
259
101
            states: lts.states.clone(),
260
101
            initial_state: lts.initial_state.clone(),
261
101
            state_variable_num_of_bits: lts.state_variable_num_of_bits.clone(),
262
101
            state_variable_indices: lts.state_variable_indices.clone(),
263
101
            next_state_variables_indices: lts.next_state_variables_indices.clone(),
264
101
            action_variable_indices: lts.action_variable_indices.clone(),
265
101
            action_labels: lts.action_labels.clone(),
266
101
            parameter_values: lts.parameter_values.clone(),
267
101
            transition_groups,
268
101
        }
269
101
    }
270

            
271
    /// Constructs a quotient symbolic LTS that reuses the action labels of `lts`
272
    /// but encodes states and transitions over fresh state and next-state variables
273
    /// (typically block-index variables produced by sigref).
274
100
    pub fn with_quotient_state(
275
100
        lts: &Self,
276
100
        states: BDDFunction,
277
100
        initial_state: BDDFunction,
278
100
        transition_groups: Vec<SummandGroupBdd>,
279
100
        state_variable_indices: Vec<VarNo>,
280
100
        next_state_variables_indices: Vec<VarNo>,
281
100
        state_variable_num_of_bits: Vec<Value>,
282
100
    ) -> Self {
283
100
        Self {
284
100
            states,
285
100
            initial_state,
286
100
            transition_groups,
287
100
            state_variable_num_of_bits,
288
100
            state_variable_indices,
289
100
            next_state_variables_indices,
290
100
            action_variable_indices: lts.action_variable_indices.clone(),
291
100
            action_labels: lts.action_labels.clone(),
292
100
            parameter_values: Vec::new(),
293
100
        }
294
100
    }
295

            
296
    /// Returns the BDD representing the set of states.
297
905
    pub fn states(&self) -> &BDDFunction {
298
905
        &self.states
299
905
    }
300

            
301
    /// Returns the BDD representing the set of initial states.
302
501
    pub fn initial_state(&self) -> &BDDFunction {
303
501
        &self.initial_state
304
501
    }
305

            
306
    /// Returns the number of bits used for each state variable.
307
402
    pub fn state_variable_num_of_bits(&self) -> &[Value] {
308
402
        &self.state_variable_num_of_bits
309
402
    }
310

            
311
    /// Returns the BDD variables used to represent the state variables.
312
7938
    pub fn state_variables(&self) -> &[VarNo] {
313
7938
        &self.state_variable_indices
314
7938
    }
315

            
316
    /// Returns the variable numbers used to represent the next state variables.
317
7966
    pub fn next_state_variables(&self) -> &[VarNo] {
318
7966
        &self.next_state_variables_indices
319
7966
    }
320

            
321
    /// Returns the transition groups representing the disjunctive transition relation.
322
22488
    pub fn transition_groups(&self) -> &[SummandGroupBdd] {
323
22488
        &self.transition_groups
324
22488
    }
325

            
326
    /// Returns the action variable indices used to represent the action labels.
327
802
    pub fn action_variables(&self) -> &[VarNo] {
328
802
        &self.action_variable_indices
329
802
    }
330

            
331
    /// Returns the action labels of the LTS.
332
295837
    pub fn action_labels(&self) -> &[String] {
333
295837
        &self.action_labels
334
295837
    }
335

            
336
    /// Returns the possible values for each process parameter.
337
    pub fn parameter_values(&self) -> &[Vec<DataExpression>] {
338
        &self.parameter_values
339
    }
340
}
341

            
342
pub struct SummandGroupBdd {
343
    /// The BDD representing the transition relation for this summand group.
344
    relation: BDDFunction,
345

            
346
    /// The indices of the read variables for this summand group.
347
    read_variables: Vec<VarNo>,
348

            
349
    /// The indices of the write variables for this summand group.
350
    write_variables: Vec<VarNo>,
351
}
352

            
353
impl SummandGroupBdd {
354
    /// Creates a new summand group with the given transition relation.
355
    ///
356
    /// Read variables are current state variables, and write variables are next state variables.
357
2540
    pub fn new(relation: BDDFunction, read_variables: Vec<VarNo>, write_variables: Vec<VarNo>) -> Self {
358
2540
        Self {
359
2540
            relation,
360
2540
            read_variables,
361
2540
            write_variables,
362
2540
        }
363
2540
    }
364

            
365
    /// Returns the BDD representing the transition relation for this summand group.
366
102475
    pub fn relation(&self) -> &BDDFunction {
367
102475
        &self.relation
368
102475
    }
369

            
370
    /// Returns the indices of the read variables for this summand group.
371
950649
    pub fn read_variables(&self) -> &[VarNo] {
372
950649
        &self.read_variables
373
950649
    }
374

            
375
    /// Returns the indices of the write variables for this summand group.
376
298867
    pub fn write_variables(&self) -> &[VarNo] {
377
298867
        &self.write_variables
378
298867
    }
379
}
380

            
381
/// Creates BDD of variables for the given variable numbers.
382
1961
pub fn compute_vars_bdd(
383
1961
    manager_ref: &BDDManagerRef,
384
1961
    vars: &[VarNo],
385
1961
) -> Result<(Vec<BDDFunction>, BDDFunction), OutOfMemory> {
386
1961
    manager_ref.with_manager_shared(|manager| -> Result<_, OutOfMemory> {
387
1961
        let mut vector = Vec::new();
388
1961
        let mut bdd: BDDFunction = BDDFunction::t(manager);
389

            
390
21688
        for var in vars {
391
21688
            let var = BDDFunction::var(manager, *var)?;
392
21688
            vector.push(var.clone());
393
21688
            bdd = bdd.and(&var)?;
394
        }
395

            
396
1961
        Ok((vector, bdd))
397
1961
    })
398
1961
}
399

            
400
#[cfg(test)]
401
mod tests {
402
    use merc_ldd::Storage;
403
    use merc_utilities::test_logger;
404

            
405
    use crate::SymbolicLtsBdd;
406
    use crate::read_symbolic_lts;
407

            
408
    #[test]
409
    #[cfg_attr(miri, ignore)] // Oxidd does not work with miri
410
1
    fn test_from_symbolic_lts_bdd_abp() {
411
1
        test_logger();
412

            
413
1
        let input = include_bytes!("../../../examples/lts/abp.sym");
414

            
415
1
        let mut storage = Storage::new();
416
1
        let manager_ref = oxidd::bdd::new_manager(2048, 1024, 1);
417
1
        let symbolic_lts = read_symbolic_lts(&mut storage, &input[..]).unwrap();
418

            
419
        // This only tests that the conversion does not panic.
420
1
        SymbolicLtsBdd::from_symbolic_lts(&mut storage, &manager_ref, &symbolic_lts).unwrap();
421
1
    }
422
}