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
use oxidd::ldd::LDDManagerRef;
14
use oxidd::ldd::Value;
15
use oxidd::util::OutOfMemory;
16

            
17
use merc_data::DataExpression;
18
use merc_utilities::MercError;
19
use oxidd::ldd::LDDFunction;
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
504
    pub fn from_symbolic_lts<L: SymbolicLTS>(
70
504
        manager: &LDDManagerRef,
71
504
        manager_bdd: &BDDManagerRef,
72
504
        lts: &L,
73
504
    ) -> Result<Self, MercError> {
74
504
        info!("Converting symbolic LTS from LDD to BDD representation...");
75

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

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

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

            
88
            action_label_highest =
89
2570
                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
23380
            for (ldd_level, var) in group
95
2570
                .read_indices()
96
2570
                .iter()
97
2570
                .merge(group.write_indices().iter())
98
2570
                .enumerate()
99
23380
            {
100
23380
                let var = *var as usize;
101
23380
                state_highest[var] = state_highest[var].max(highest[ldd_level]);
102
23380
            }
103
        }
104

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

            
108
504
        let action_label_bits = required_bits(action_label_highest);
109
504
        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
504
        let mut vars = Vec::new();
116

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

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

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

            
143
        // A BDD manager can only hold the variables for a single symbolic LTS.
144
504
        if manager_bdd.with_manager_shared(|manager| manager.num_vars()) != 0 {
145
            return Err("BDD manager must not contain any variables yet".into());
146
504
        }
147

            
148
        // Create variables in the BDD manager
149
504
        let number_of_vars = vars.len();
150
504
        let variables = manager_bdd
151
504
            .with_manager_exclusive(|manager| -> Result<Range<VarNo>, DuplicateVarName> {
152
504
                manager.add_named_vars(vars)
153
504
            })
154
504
            .map_err(|e| format!("Failed to create variables: {e}"))?;
155

            
156
504
        assert!(variables.clone().is_sorted(), "Variables must be added in sorted order");
157
504
        assert!(
158
504
            variables.len() == number_of_vars,
159
            "Number of created variables does not match"
160
        );
161

            
162
        // Convert the states to a BDD representation.
163
504
        let bits_dd = manager.with_manager_shared(|m| LDDFunction::singleton(m, &state_bits))?;
164
504
        let all_state_variables_bits: Vec<VarNo> = state_variables_bits.iter().flatten().cloned().collect();
165
504
        let states = ldd_to_bdd(manager, manager_bdd, lts.states(), &bits_dd, &all_state_variables_bits)?;
166
504
        let initial_state = ldd_to_bdd(
167
504
            manager,
168
504
            manager_bdd,
169
504
            lts.initial_state(),
170
504
            &bits_dd,
171
504
            &all_state_variables_bits,
172
        )?;
173

            
174
504
        let mut transition_groups = Vec::new();
175
2582
        for (index, group) in lts.transition_groups().iter().enumerate() {
176
            // Determine the number of bits used for each layer.
177
2582
            let mut relation_bits = Vec::new();
178

            
179
            // Determine all the variables used in this relation.
180
2582
            let mut variables = Vec::new();
181

            
182
2582
            let mut read_variable_indices: Vec<VarNo> = Vec::new();
183
2582
            let mut write_variable_indices: Vec<VarNo> = Vec::new();
184

            
185
25954
            for (var, bits) in state_bits.iter().enumerate() {
186
25954
                if group.read_indices().contains(&(var as VarNo)) {
187
                    // The transition group reads this state variable
188
11436
                    relation_bits.push(*bits);
189
11436
                    variables.extend(state_variables_bits[var].iter());
190
11436
                    read_variable_indices.extend(state_variables_bits[var].iter())
191
14518
                }
192

            
193
25954
                if group.write_indices().contains(&(var as VarNo)) {
194
                    // The transition group writes this state variable
195
12022
                    relation_bits.push(*bits);
196
12022
                    variables.extend(next_state_variables_bits[var].iter());
197
12022
                    write_variable_indices.extend(next_state_variables_bits[var].iter())
198
13932
                }
199
            }
200

            
201
            // Append action label bits (between read and write segments) if present
202
2582
            if let Some(_action_index) = group.action_label_index() {
203
2582
                // TODO: This currently assumes that action label bits are at the end.
204
2582
                variables.extend(action_labels_vars.iter());
205
2582
            }
206

            
207
            // Append action label bits
208
2582
            relation_bits.push(action_label_bits);
209
2582
            debug!(
210
                "Transition group {}, {:?} uses number of bits {:?}, and variables: {:?}",
211
                index, group, relation_bits, variables
212
            );
213

            
214
2582
            let bits_dd = manager.with_manager_shared(|m| LDDFunction::singleton(m, &relation_bits))?;
215
2582
            let relation_bdd = ldd_to_bdd(manager, manager_bdd, group.relation(), &bits_dd, &variables)?;
216

            
217
2582
            transition_groups.push(SummandGroupBdd::new(
218
2582
                relation_bdd,
219
2582
                read_variable_indices,
220
2582
                write_variable_indices,
221
            ));
222
        }
223

            
224
        // Compute the BDDs representing the state variables and next state variables.
225
504
        let all_next_state_variables_bits = next_state_variables_bits
226
504
            .iter()
227
504
            .flatten()
228
504
            .cloned()
229
504
            .collect::<Vec<VarNo>>();
230

            
231
504
        debug!("State bits {all_state_variables_bits:?}, and next state bits {all_next_state_variables_bits:?}");
232

            
233
504
        info!("Finished conversion.");
234
504
        Ok(Self {
235
504
            action_variable_indices: action_labels_vars,
236
504
            states,
237
504
            initial_state,
238
504
            transition_groups,
239
504
            state_variable_num_of_bits: state_bits,
240
504
            state_variable_indices: all_state_variables_bits,
241
504
            next_state_variables_indices: all_next_state_variables_bits,
242
504
            action_labels: lts.action_labels().to_vec(),
243
504
            parameter_values: lts.parameter_values().to_vec(),
244
504
        })
245
504
    }
246

            
247
    /// Constructs a new symbolic LTS with the given transition groups.
248
302
    pub fn with_transition_groups(lts: &Self, transition_groups: Vec<SummandGroupBdd>) -> Self {
249
302
        Self {
250
302
            states: lts.states.clone(),
251
302
            initial_state: lts.initial_state.clone(),
252
302
            state_variable_num_of_bits: lts.state_variable_num_of_bits.clone(),
253
302
            state_variable_indices: lts.state_variable_indices.clone(),
254
302
            next_state_variables_indices: lts.next_state_variables_indices.clone(),
255
302
            action_variable_indices: lts.action_variable_indices.clone(),
256
302
            action_labels: lts.action_labels.clone(),
257
302
            parameter_values: lts.parameter_values.clone(),
258
302
            transition_groups,
259
302
        }
260
302
    }
261

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

            
287
    /// Returns the BDD representing the set of states.
288
1307
    pub fn states(&self) -> &BDDFunction {
289
1307
        &self.states
290
1307
    }
291

            
292
    /// Returns the BDD representing the set of initial states.
293
501
    pub fn initial_state(&self) -> &BDDFunction {
294
501
        &self.initial_state
295
501
    }
296

            
297
    /// Returns the number of bits used for each state variable.
298
402
    pub fn state_variable_num_of_bits(&self) -> &[Value] {
299
402
        &self.state_variable_num_of_bits
300
402
    }
301

            
302
    /// Returns the BDD variables used to represent the state variables.
303
8885
    pub fn state_variables(&self) -> &[VarNo] {
304
8885
        &self.state_variable_indices
305
8885
    }
306

            
307
    /// Returns the variable numbers used to represent the next state variables.
308
9624
    pub fn next_state_variables(&self) -> &[VarNo] {
309
9624
        &self.next_state_variables_indices
310
9624
    }
311

            
312
    /// Returns the transition groups representing the disjunctive transition relation.
313
17805
    pub fn transition_groups(&self) -> &[SummandGroupBdd] {
314
17805
        &self.transition_groups
315
17805
    }
316

            
317
    /// Returns the action variable indices used to represent the action labels.
318
1003
    pub fn action_variables(&self) -> &[VarNo] {
319
1003
        &self.action_variable_indices
320
1003
    }
321

            
322
    /// Returns the action labels of the LTS.
323
204912
    pub fn action_labels(&self) -> &[String] {
324
204912
        &self.action_labels
325
204912
    }
326

            
327
    /// Returns the possible values for each process parameter.
328
    pub fn parameter_values(&self) -> &[Vec<DataExpression>] {
329
        &self.parameter_values
330
    }
331
}
332

            
333
pub struct SummandGroupBdd {
334
    /// The BDD representing the transition relation for this summand group.
335
    relation: BDDFunction,
336

            
337
    /// The indices of the read variables for this summand group.
338
    read_variables: Vec<VarNo>,
339

            
340
    /// The indices of the write variables for this summand group.
341
    write_variables: Vec<VarNo>,
342
}
343

            
344
impl SummandGroupBdd {
345
    /// Creates a new summand group with the given transition relation.
346
    ///
347
    /// Read variables are current state variables, and write variables are next state variables.
348
4644
    pub fn new(relation: BDDFunction, read_variables: Vec<VarNo>, write_variables: Vec<VarNo>) -> Self {
349
4644
        Self {
350
4644
            relation,
351
4644
            read_variables,
352
4644
            write_variables,
353
4644
        }
354
4644
    }
355

            
356
    /// Returns the BDD representing the transition relation for this summand group.
357
65598
    pub fn relation(&self) -> &BDDFunction {
358
65598
        &self.relation
359
65598
    }
360

            
361
    /// Returns the indices of the read variables for this summand group.
362
973256
    pub fn read_variables(&self) -> &[VarNo] {
363
973256
        &self.read_variables
364
973256
    }
365

            
366
    /// Returns the indices of the write variables for this summand group.
367
210046
    pub fn write_variables(&self) -> &[VarNo] {
368
210046
        &self.write_variables
369
210046
    }
370
}
371

            
372
/// Creates BDD of variables for the given variable numbers.
373
3214
pub fn compute_vars_bdd(
374
3214
    manager_ref: &BDDManagerRef,
375
3214
    vars: &[VarNo],
376
3214
) -> Result<(Vec<BDDFunction>, BDDFunction), OutOfMemory> {
377
3214
    manager_ref.with_manager_shared(|manager| -> Result<_, OutOfMemory> {
378
3214
        let mut vector = Vec::new();
379
3214
        let mut bdd: BDDFunction = BDDFunction::t(manager);
380

            
381
38120
        for var in vars {
382
38120
            let var = BDDFunction::var(manager, *var)?;
383
38120
            vector.push(var.clone());
384
38120
            bdd = bdd.and(&var)?;
385
        }
386

            
387
3214
        Ok((vector, bdd))
388
3214
    })
389
3214
}
390

            
391
#[cfg(test)]
392
mod tests {
393
    use merc_utilities::test_logger;
394

            
395
    use crate::SymbolicLtsBdd;
396
    use crate::read_symbolic_lts;
397

            
398
    #[test]
399
    #[cfg_attr(miri, ignore)] // Oxidd does not work with miri
400
1
    fn test_from_symbolic_lts_bdd_abp() {
401
1
        test_logger();
402

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

            
405
1
        let ldd_manager = oxidd::ldd::new_manager(2048, 1024, 1);
406
1
        let bdd_manager = oxidd::bdd::new_manager(2048, 1024, 1);
407
1
        let symbolic_lts = read_symbolic_lts(&ldd_manager, &input[..]).unwrap();
408

            
409
        // This only tests that the conversion does not panic.
410
1
        SymbolicLtsBdd::from_symbolic_lts(&ldd_manager, &bdd_manager, &symbolic_lts).unwrap();
411
1
    }
412
}