1
use std::fmt;
2

            
3
use log::debug;
4
use log::info;
5
use log::trace;
6
use merc_data::DataExpression;
7
use merc_io::TimeProgress;
8
use merc_ldd::Ldd;
9
use merc_ldd::LddDisplay;
10
use merc_ldd::Storage;
11
use merc_ldd::len;
12
use merc_ldd::minus;
13
use merc_ldd::relational_product;
14
use merc_ldd::union;
15
use merc_utilities::MercError;
16

            
17
use crate::DependencyGraph;
18
use crate::Relation;
19

            
20
/// A generic trait representing a symbolic LTS
21
pub trait SymbolicLTS {
22
    /// Returns the LDD representing the set of states.
23
    fn states(&self) -> &Ldd;
24

            
25
    /// Returns the LDD representing the initial state.
26
    fn initial_state(&self) -> &Ldd;
27

            
28
    /// Returns an iterator over the summand groups.
29
    fn transition_groups(&self) -> &[impl TransitionGroup];
30

            
31
    /// Returns the action labels for the LTS.
32
    fn action_labels(&self) -> &[String];
33

            
34
    /// Returns the possible values for each process parameter.
35
    fn parameter_values(&self) -> &[Vec<DataExpression>];
36
    
37
    /// Computes the dependency graph of the LTS.
38
    fn dependency_graph(&self) -> DependencyGraph {
39
        let mut relations = Vec::new();
40

            
41
        for group in self.transition_groups() {
42
            relations.push(Relation::new(
43
                group.read_indices().iter().map(|i| *i as usize).collect(),
44
                group.write_indices().iter().map(|i| *i as usize).collect(),
45
            ));
46
        }
47

            
48
        DependencyGraph::new(relations)
49
    }
50
}
51

            
52
pub trait TransitionGroup: fmt::Debug {
53
    /// Returns the transition relation T' -> U' for this summand group.
54
    fn relation(&self) -> &Ldd;
55

            
56
    /// Returns the read indices for this summand group.
57
    fn read_indices(&self) -> &[u32];
58

            
59
    /// Returns the write indices for this summand group.
60
    fn write_indices(&self) -> &[u32];
61

            
62
    /// Returns the action label index for this summand group, if any.
63
    fn action_label_index(&self) -> Option<usize>;
64

            
65
    /// Returns the meta information for this summand group.
66
    fn meta(&self) -> &Ldd;
67
}
68

            
69
/// Performs reachability analysis using the given initial state and transitions read from a Sylvan file.
70
101
pub fn reachability(storage: &mut Storage, lts: &impl SymbolicLTS) -> Result<usize, MercError> {
71
101
    let mut todo = lts.initial_state().clone();
72
101
    let mut states = lts.initial_state().clone(); // The state space.
73
101
    let mut iteration = 0;
74

            
75
101
    trace!("states = {}", LddDisplay::new(storage, &states));
76
101
    let progress = TimeProgress::new(
77
2
        |iteration: usize| {
78
2
            info!("Iteration {}", iteration);
79
2
        },
80
        1,
81
    );
82

            
83
513
    while todo != *storage.empty_set() {
84
412
        debug!("Iteration {}: todo size = {}", iteration, len(storage, &todo));
85
412
        let mut todo1 = storage.empty_set().clone();
86
3599
        for transition in lts.transition_groups() {
87
3599
            let result = relational_product(storage, &todo, transition.relation(), transition.meta());
88
3599
            todo1 = union(storage, &todo1, &result);
89
3599
        }
90

            
91
412
        trace!("todo1 = {}", LddDisplay::new(storage, &todo1));
92

            
93
412
        todo = minus(storage, &todo1, &states);
94
412
        states = union(storage, &states, &todo);
95
412
        progress.print(iteration);
96
412
        iteration += 1;
97
    }
98

            
99
101
    Ok(len(storage, &states))
100
101
}