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::singleton;
15
use merc_ldd::Storage;
16
use merc_ldd::Value;
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
201
    pub fn from_symbolic_lts(
69
201
        storage: &mut Storage,
70
201
        manager_ref: &BDDManagerRef,
71
201
        lts: &impl SymbolicLTS,
72
201
    ) -> Result<Self, MercError> {
73
201
        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
201
        let state_bits = compute_bits(&compute_highest(storage, lts.states()));
77
201
        debug!("Determined number of bits for state variables: {:?}", state_bits);
78

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

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

            
90
201
        let action_label_bits = required_bits(action_label_highest);
91
201
        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
201
        let mut vars = Vec::new();
98

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

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

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

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

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

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

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

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

            
165
201
        let mut transition_groups = Vec::new();
166
1010
        for group in lts.transition_groups() {
167
            // Determine the number of bits used for each layer.
168
1010
            let mut relation_bits = Vec::new();
169

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

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

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

            
184
10110
                if group.write_indices().contains(&(var as VarNo)) {
185
                    // The transition group writes this state variable
186
4509
                    relation_bits.push(*bits);
187
4509
                    variables.extend(next_state_variables_bits[var].iter());
188
4509
                    write_variable_indices.extend(next_state_variables_bits[var].iter())
189
5601
                }
190
            }
191
            
192
            // Append action label bits (between read and write segments) if present
193
1010
            if let Some(_action_index) = group.action_label_index() {
194
1010
                // TODO: This currently assumes that action label bits are at the end.
195
1010
                variables.extend(action_labels_vars.iter());
196
1010
            }
197

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

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

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

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

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

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

            
238
    /// Returns the BDD representing the set of states.
239
200
    pub fn states(&self) -> &BDDFunction {
240
200
        &self.states
241
200
    }
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
7411
    pub fn state_variables(&self) -> &[VarNo] {
255
7411
        &self.state_variable_indices
256
7411
    }
257

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

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

            
268
    /// Returns the action variable indices used to represent the action labels.
269
600
    pub fn action_variables(&self) -> &[VarNo] {
270
600
        &self.action_variable_indices
271
600
    }
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_variable: Vec<VarNo>,
290

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

            
295
impl SummandGroupBdd {
296
    /// Creates a new summand group with the given transition relation.
297
1010
    pub fn new(
298
1010
        relation: BDDFunction,
299
1010
        read_variable: Vec<VarNo>,
300
1010
        write_variable: Vec<VarNo>,
301
1010
    ) -> Self {
302
1010
        Self {
303
1010
            relation,
304
1010
            read_variable,
305
1010
            write_variable,
306
1010
        }
307
1010
    }
308

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

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

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

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

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

            
337
1700
        Ok((vector, bdd))
338
1700
    })
339
1700
}
340

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

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

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

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

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

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