1
use std::ops::Range;
2

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

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

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

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

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

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

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

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

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

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

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

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

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

            
75
        // Determine the highest values for every layer in the LDD representing the states
76
401
        let state_bits = compute_bits(&compute_highest(storage, lts.states()));
77
401
        debug!("Determined number of bits for state variables: {:?}", state_bits);
78

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

            
83
            // Deal with the special empty case.
84
2010
            if !highest.is_empty() {
85
2010
                action_label_highest = action_label_highest
86
2010
                    .max(highest[group.action_label_index().ok_or("Action label index not found")?]);
87
            }
88
        }
89

            
90
401
        let action_label_bits = required_bits(action_label_highest);
91
401
        debug!(
92
            "Highest action label: {}, bits: {}",
93
            action_label_highest, action_label_bits
94
        );
95

            
96
        // Create the state variables, with interleaved primed variables for write parameters
97
401
        let mut vars = Vec::new();
98

            
99
        // Keep track of the bits per state variable.
100
401
        let mut state_variables_bits: Vec<Vec<VarNo>> = Vec::new();
101
401
        let mut next_state_variables_bits: Vec<Vec<VarNo>> = Vec::new();
102
4011
        for (i, &bits) in state_bits.iter().enumerate() {
103
4011
            let mut state_var_bits = Vec::new();
104
4011
            let mut next_state_var_bits = Vec::new();
105
12015
            for k in 0..bits {
106
12015
                // Add variable for the state variable
107
12015
                state_var_bits.push(vars.len() as VarNo);
108
12015
                vars.push(format!("s{}_{}", i, k));
109
12015

            
110
12015
                // Add a primed version for the write parameters
111
12015
                next_state_var_bits.push(vars.len() as VarNo);
112
12015
                vars.push(format!("s{}'_{}", i, k));
113
12015
            }
114
4011
            state_variables_bits.push(state_var_bits);
115
4011
            next_state_variables_bits.push(next_state_var_bits);
116
        }
117

            
118
        // Create action label variables
119
401
        let mut action_labels_vars = Vec::new();
120
1205
        for k in 0..action_label_bits {
121
1205
            action_labels_vars.push(vars.len() as VarNo);
122
1205
            vars.push(format!("a_{}", k));
123
1205
        }
124

            
125
        // Check for existing variables.
126
401
        if manager_ref.with_manager_shared(|manager| manager.num_vars()) != 0 {
127
            return Err("BDD manager must not contain any variables yet".into());
128
401
        }
129

            
130
        // Ensure that the BDD manager is empty.
131
401
        manager_ref.with_manager_exclusive(|manager| {
132
401
            debug_assert_eq!(
133
401
                manager.num_vars(),
134
                0,
135
                "A BDD manager can only hold the variables for a single symbolic LTS"
136
            )
137
401
        });
138

            
139
        // Create variables in the BDD manager
140
401
        let number_of_vars = vars.len();
141
401
        let variables = manager_ref
142
401
            .with_manager_exclusive(|manager| -> Result<Range<VarNo>, DuplicateVarName> {
143
401
                manager.add_named_vars(vars)
144
401
            })
145
401
            .map_err(|e| format!("Failed to create variables: {e}"))?;
146

            
147
401
        assert!(variables.clone().is_sorted(), "Variables must be added in sorted order");
148
401
        assert!(
149
401
            variables.len() == number_of_vars,
150
            "Number of created variables does not match"
151
        );
152

            
153
        // Convert the states to a BDD representation.
154
401
        let bits_dd = singleton(storage, &state_bits);
155
401
        let all_state_variables_bits: Vec<VarNo> = state_variables_bits.iter().flatten().cloned().collect();
156
401
        let states = ldd_to_bdd(storage, manager_ref, lts.states(), &bits_dd, &all_state_variables_bits)?;
157
401
        let initial_state = ldd_to_bdd(
158
401
            storage,
159
401
            manager_ref,
160
401
            lts.initial_state(),
161
401
            &bits_dd,
162
401
            &all_state_variables_bits,
163
        )?;
164

            
165
401
        let mut transition_groups = Vec::new();
166
2010
        for (index, group) in lts.transition_groups().iter().enumerate() {
167
            // Determine the number of bits used for each layer.
168
2010
            let mut relation_bits = Vec::new();
169

            
170
            // Determine all the variables used in this relation.
171
2010
            let mut variables = Vec::new();
172

            
173
2010
            let mut read_variable_indices: Vec<VarNo> = Vec::new();
174
2010
            let mut write_variable_indices: Vec<VarNo> = Vec::new();
175

            
176
20110
            for (var, bits) in state_bits.iter().enumerate() {
177
20110
                if group.read_indices().contains(&(var as VarNo)) {
178
                    // The transition group reads this state variable
179
8842
                    relation_bits.push(*bits);
180
8842
                    variables.extend(state_variables_bits[var].iter());
181
8842
                    read_variable_indices.extend(state_variables_bits[var].iter())
182
11268
                }
183

            
184
20110
                if group.write_indices().contains(&(var as VarNo)) {
185
                    // The transition group writes this state variable
186
8984
                    relation_bits.push(*bits);
187
8984
                    variables.extend(next_state_variables_bits[var].iter());
188
8984
                    write_variable_indices.extend(next_state_variables_bits[var].iter())
189
11126
                }
190
            }
191

            
192
            // Append action label bits (between read and write segments) if present
193
2010
            if let Some(_action_index) = group.action_label_index() {
194
2010
                // TODO: This currently assumes that action label bits are at the end.
195
2010
                variables.extend(action_labels_vars.iter());
196
2010
            }
197

            
198
            // Append action label bits
199
2010
            relation_bits.push(action_label_bits);
200
2010
            debug!(
201
                "Transition group {}, {:?} uses number of bits {:?}, and variables: {:?}",
202
                index, group, relation_bits, variables
203
            );
204

            
205
2010
            let bits_dd = singleton(storage, &relation_bits);
206
2010
            let relation_bdd = ldd_to_bdd(storage, manager_ref, group.relation(), &bits_dd, &variables)?;
207

            
208
2010
            transition_groups.push(SummandGroupBdd::new(
209
2010
                relation_bdd,
210
2010
                read_variable_indices,
211
2010
                write_variable_indices,
212
            ));
213
        }
214

            
215
        // Compute the BDDs representing the state variables and next state variables.
216
401
        let all_next_state_variables_bits = next_state_variables_bits
217
401
            .iter()
218
401
            .flatten()
219
401
            .cloned()
220
401
            .collect::<Vec<VarNo>>();
221

            
222
401
        debug!("State bits {all_state_variables_bits:?}, and next state bits {all_next_state_variables_bits:?}");
223

            
224
401
        info!("Finished conversion.");
225
401
        Ok(Self {
226
401
            action_variable_indices: action_labels_vars,
227
401
            states,
228
401
            initial_state,
229
401
            transition_groups,
230
401
            state_variable_num_of_bits: state_bits,
231
401
            state_variable_indices: all_state_variables_bits,
232
401
            next_state_variables_indices: all_next_state_variables_bits,
233
401
            action_labels: lts.action_labels().to_vec(),
234
401
            parameter_values: lts.parameter_values().to_vec(),
235
401
        })
236
401
    }
237

            
238
    /// Returns the BDD representing the set of states.
239
600
    pub fn states(&self) -> &BDDFunction {
240
600
        &self.states
241
600
    }
242

            
243
    /// Returns the BDD representing the set of initial states.
244
200
    pub fn initial_state(&self) -> &BDDFunction {
245
200
        &self.initial_state
246
200
    }
247

            
248
    /// Returns the number of bits used for each state variable.
249
    pub fn state_variable_num_of_bits(&self) -> &[Value] {
250
        &self.state_variable_num_of_bits
251
    }
252

            
253
    /// Returns the BDD variables used to represent the state variables.
254
7118
    pub fn state_variables(&self) -> &[VarNo] {
255
7118
        &self.state_variable_indices
256
7118
    }
257

            
258
    /// Returns the variable numbers used to represent the next state variables.
259
7918
    pub fn next_state_variables(&self) -> &[VarNo] {
260
7918
        &self.next_state_variables_indices
261
7918
    }
262

            
263
    /// Returns the transition groups representing the disjunctive transition relation.
264
1381
    pub fn transition_groups(&self) -> &[SummandGroupBdd] {
265
1381
        &self.transition_groups
266
1381
    }
267

            
268
    /// Returns the action variable indices used to represent the action labels.
269
800
    pub fn action_variables(&self) -> &[VarNo] {
270
800
        &self.action_variable_indices
271
800
    }
272

            
273
    /// Returns the action labels of the LTS.
274
    pub fn action_labels(&self) -> &[String] {
275
        &self.action_labels
276
    }
277

            
278
    /// Returns the possible values for each process parameter.
279
    pub fn parameter_values(&self) -> &[Vec<DataExpression>] {
280
        &self.parameter_values
281
    }
282
}
283

            
284
pub struct SummandGroupBdd {
285
    /// The BDD representing the transition relation for this summand group.
286
    relation: BDDFunction,
287

            
288
    /// The indices of the read variables for this summand group.
289
    read_variables: Vec<VarNo>,
290

            
291
    /// The indices of the write variables for this summand group.
292
    write_variables: Vec<VarNo>,
293
}
294

            
295
impl SummandGroupBdd {
296
    /// Creates a new summand group with the given transition relation.
297
    ///
298
    /// Read variables are current state variables, and write variables are next state variables.
299
2010
    pub fn new(relation: BDDFunction, read_variables: Vec<VarNo>, write_variables: Vec<VarNo>) -> Self {
300
2010
        Self {
301
2010
            relation,
302
2010
            read_variables,
303
2010
            write_variables,
304
2010
        }
305
2010
    }
306

            
307
    /// Returns the BDD representing the transition relation for this summand group.
308
4905
    pub fn relation(&self) -> &BDDFunction {
309
4905
        &self.relation
310
4905
    }
311

            
312
    /// Returns the indices of the read variables for this summand group.
313
    pub fn read_variables(&self) -> &Vec<VarNo> {
314
        &self.read_variables
315
    }
316

            
317
    /// Returns the indices of the write variables for this summand group.
318
2000
    pub fn write_variables(&self) -> &Vec<VarNo> {
319
2000
        &self.write_variables
320
2000
    }
321
}
322

            
323
/// Creates BDD of variables for the given variable numbers.
324
2850
pub fn compute_vars_bdd(
325
2850
    manager_ref: &BDDManagerRef,
326
2850
    vars: &[VarNo],
327
2850
) -> Result<(Vec<BDDFunction>, BDDFunction), OutOfMemory> {
328
2850
    manager_ref.with_manager_shared(|manager| -> Result<_, OutOfMemory> {
329
2850
        let mut vector = Vec::new();
330
2850
        let mut bdd: BDDFunction = BDDFunction::t(manager);
331

            
332
30544
        for var in vars {
333
30544
            let var = BDDFunction::var(manager, *var)?;
334
30544
            vector.push(var.clone());
335
30544
            bdd = bdd.and(&var)?;
336
        }
337

            
338
2850
        Ok((vector, bdd))
339
2850
    })
340
2850
}
341

            
342
#[cfg(test)]
343
mod tests {
344
    use merc_ldd::Storage;
345
    use merc_utilities::test_logger;
346

            
347
    use crate::SymbolicLtsBdd;
348
    use crate::read_symbolic_lts;
349

            
350
    #[test]
351
    #[cfg_attr(miri, ignore)] // Oxidd does not work with miri
352
1
    fn test_symbolic_lts_bdd() {
353
1
        test_logger();
354

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

            
357
1
        let mut storage = Storage::new();
358
1
        let manager_ref = oxidd::bdd::new_manager(2048, 1024, 1);
359
1
        let symbolic_lts = read_symbolic_lts(&mut storage, &input[..]).unwrap();
360

            
361
1
        SymbolicLtsBdd::from_symbolic_lts(&mut storage, &manager_ref, &symbolic_lts).unwrap();
362
1
    }
363
}