1
use std::fmt;
2
use std::rc::Rc;
3

            
4
use merc_collections::IndexedSet;
5
use merc_explore::LPS;
6
use merc_explore::Summand;
7
use merc_utilities::MercError;
8
use oxidd::ManagerRef;
9
use oxidd::ldd::LDDFunction;
10
use oxidd::ldd::LDDManagerRef;
11
use oxidd::ldd::RelationProductMeta;
12
use oxidd::ldd::Value;
13
use streaming_iterator::StreamingIterator;
14

            
15
use crate::SymbolicLPS;
16
use crate::TransitionGroup;
17
use crate::iter;
18

            
19
/// A symbolic LDD view of any [`merc_explore::LPS`].
20
///
21
/// This adapts the explicit-exploration abstraction (an `LPS` exposing summands
22
/// with read/write positions, a `prepare` step selecting the summands that fire
23
/// from a state, and per-summand enumeration) into the disjunctive LDD
24
/// transition relation consumed by [`crate::reachability`]. A single generic
25
/// implementation therefore drives symbolic exploration for both LPSs and PBESs
26
/// in SRF form (and anything else implementing `LPS`).
27
///
28
/// The wrapped `LPS` interns parameter values in its own space; this adapter
29
/// keeps a separate per-position interning into dense LDD values so the decision
30
/// diagrams stay compact regardless of how the `LPS` numbers its values.
31
pub struct SymbolicLps<L: LPS> {
32
    /// The wrapped `LPS` definition; the single source of summands and the
33
    /// `prepare`/`enumerate` machinery. Shared immutably with every group.
34
    lps: Rc<L>,
35

            
36
    /// One symbolic transition group per summand.
37
    groups: Vec<SymbolicLpsGroup<L>>,
38

            
39
    /// The encoded initial state.
40
    initial_state: LDDFunction,
41
}
42

            
43
/// Per-run learning state threaded through [SymbolicLpsGroup::learn_successors].
44
///
45
/// Holds the mutable state shared by all groups of one [SymbolicLps], so the
46
/// groups themselves need no interior mutability.
47
pub struct SymbolicContext<L: LPS> {
48
    /// The enumeration backend created by [`LPS::create_context`].
49
    enumerate: <L::Summand as Summand>::Context,
50

            
51
    /// Per state-vector position interning of `LPS` values into dense LDD values.
52
    columns: Vec<IndexedSet<L::Value>>,
53
}
54

            
55
impl<L: LPS> SymbolicLps<L> {
56
    /// Wraps `lps` into a symbolic LDD view, encoding its initial state.
57
    pub fn new(manager: &LDDManagerRef, lps: L) -> Result<Self, MercError> {
58
        let lps = Rc::new(lps);
59

            
60
        let initial_values = lps.initial_state();
61
        let num_positions = initial_values.len();
62

            
63
        let mut columns: Vec<IndexedSet<L::Value>> = (0..num_positions).map(|_| IndexedSet::new()).collect();
64

            
65
        // Encode the initial state, interning each value into its column.
66
        let mut initial_vector: Vec<Value> = Vec::with_capacity(num_positions);
67
        for (position, value) in initial_values.iter().enumerate() {
68
            let (index, _) = columns[position].insert(*value);
69
            initial_vector.push(*index as Value);
70
        }
71
        let initial_state = manager.with_manager_shared(|m| LDDFunction::singleton(m, &initial_vector))?;
72

            
73
        // Build one symbolic group per summand.
74
        let mut groups = Vec::with_capacity(lps.summands().len());
75
        for (index, summand) in lps.summands().iter().enumerate() {
76
            let mut read_indices: Vec<Value> = summand.read_positions().iter().map(|&p| p as Value).collect();
77
            let mut write_indices: Vec<Value> = summand.write_positions().iter().map(|&p| p as Value).collect();
78
            // The short-vector encoding requires sorted read/write indices.
79
            read_indices.sort_unstable();
80
            write_indices.sort_unstable();
81

            
82
            let (project_ldd, meta, read_positions, write_positions, relation) =
83
                manager.with_manager_shared(|m| -> Result<_, MercError> {
84
                    let project_ldd = LDDFunction::projection_meta(m, &read_indices)?;
85
                    let RelationProductMeta {
86
                        meta,
87
                        read_positions,
88
                        write_positions,
89
                    } = LDDFunction::relation_product_meta(m, &read_indices, &write_indices)?;
90
                    let relation = LDDFunction::empty_set(m)?;
91
                    Ok((project_ldd, meta, read_positions, write_positions, relation))
92
                })?;
93

            
94
            groups.push(SymbolicLpsGroup {
95
                lps: Rc::clone(&lps),
96
                index,
97
                read_indices,
98
                write_indices,
99
                read_positions,
100
                write_positions,
101
                project_ldd,
102
                meta,
103
                relation,
104
            });
105
        }
106

            
107
        Ok(SymbolicLps {
108
            lps,
109
            groups,
110
            initial_state,
111
        })
112
    }
113

            
114
    /// Builds the per-position interning seeded with the initial-state values.
115
    ///
116
    /// Re-inserting `initial_state()` into fresh per-column sets reproduces the
117
    /// exact dense indices used when [Self::new] encoded the initial LDD, so the
118
    /// learned relations stay consistent with it.
119
    fn initial_columns(&self) -> Vec<IndexedSet<L::Value>> {
120
        let initial_values = self.lps.initial_state();
121
        let mut columns: Vec<IndexedSet<L::Value>> = (0..initial_values.len()).map(|_| IndexedSet::new()).collect();
122
        for (position, value) in initial_values.iter().enumerate() {
123
            columns[position].insert(*value);
124
        }
125
        columns
126
    }
127
}
128

            
129
impl<L: LPS> SymbolicLPS for SymbolicLps<L> {
130
    type Group = SymbolicLpsGroup<L>;
131

            
132
    fn initial_state(&self) -> &LDDFunction {
133
        &self.initial_state
134
    }
135

            
136
    fn transition_groups(&self) -> &[Self::Group] {
137
        &self.groups
138
    }
139

            
140
    fn transition_groups_mut(&mut self) -> &mut [Self::Group] {
141
        &mut self.groups
142
    }
143

            
144
    fn create_context(&self) -> SymbolicContext<L> {
145
        SymbolicContext {
146
            enumerate: self.lps.create_context(),
147
            columns: self.initial_columns(),
148
        }
149
    }
150
}
151

            
152
/// A single summand of a [`SymbolicLps`], encoded as a short-vector LDD
153
/// transition relation that is learned on the fly during reachability.
154
pub struct SymbolicLpsGroup<L: LPS> {
155
    /// The wrapped `LPS`, shared immutably with [SymbolicLps].
156
    lps: Rc<L>,
157

            
158
    /// Index of this summand within `lps.summands()`.
159
    index: usize,
160

            
161
    /// Full state-vector positions read by the summand (sorted).
162
    read_indices: Vec<Value>,
163

            
164
    /// Full state-vector positions written by the summand (sorted).
165
    write_indices: Vec<Value>,
166

            
167
    /// Interleaved short-vector positions of `read_indices`.
168
    read_positions: Vec<usize>,
169

            
170
    /// Interleaved short-vector positions of `write_indices`.
171
    write_positions: Vec<usize>,
172

            
173
    /// Projection meta selecting `read_indices` from a full state.
174
    project_ldd: LDDFunction,
175

            
176
    /// Relational-product meta for `read_indices`/`write_indices`.
177
    meta: LDDFunction,
178

            
179
    /// The learned transition relation `T' -> U'`, grown on the fly.
180
    relation: LDDFunction,
181
}
182

            
183
impl<L: LPS> TransitionGroup for SymbolicLpsGroup<L> {
184
    type Context = SymbolicContext<L>;
185

            
186
    fn relation(&self) -> &LDDFunction {
187
        &self.relation
188
    }
189

            
190
    fn read_indices(&self) -> &[u32] {
191
        &self.read_indices
192
    }
193

            
194
    fn write_indices(&self) -> &[u32] {
195
        &self.write_indices
196
    }
197

            
198
    fn action_label_index(&self) -> Option<usize> {
199
        None
200
    }
201

            
202
    fn meta(&self) -> &LDDFunction {
203
        &self.meta
204
    }
205

            
206
    fn learn_successors(
207
        &mut self,
208
        context: &mut SymbolicContext<L>,
209
        storage: &LDDManagerRef,
210
        todo: &LDDFunction,
211
    ) -> Result<(), MercError> {
212
        let proj = todo.project(&self.project_ldd)?;
213

            
214
        // Borrow the backend and the interning as disjoint fields so the
215
        // enumeration callback can grow the interning while the backend call is
216
        // in progress.
217
        let SymbolicContext { enumerate, columns } = context;
218

            
219
        // Reusable full-length state buffer. Non-read positions keep the initial
220
        // state's values: they are never read by this summand (guaranteed by the
221
        // read-positions contract), so any valid value works; the read positions
222
        // are overlaid from each short state below.
223
        let mut full_state = self.lps.initial_state();
224

            
225
        // Reusable interleaved short vector for the relation singletons.
226
        let mut interleaved: Vec<Value> = vec![0; self.read_indices.len() + self.write_indices.len()];
227

            
228
        // Accumulate into a local relation so the enumeration callback does not
229
        // have to borrow `self`.
230
        let mut relation = self.relation.clone();
231

            
232
        let summand = &self.lps.summands()[self.index];
233

            
234
        let mut states = iter(&proj);
235
        while let Some(short_state) = states.next() {
236
            debug_assert_eq!(
237
                short_state.len(),
238
                self.read_indices.len(),
239
                "Projected state must have one value per read index"
240
            );
241

            
242
            // Overlay the short read values into the full state buffer and the
243
            // interleaved read positions.
244
            for (k, &value) in short_state.iter().enumerate() {
245
                let full_pos = self.read_indices[k] as usize;
246
                full_state[full_pos] = *columns[full_pos]
247
                    .get_by_index(value as usize)
248
                    .expect("read value must already be interned");
249
                interleaved[self.read_positions[k]] = value;
250
            }
251

            
252
            // Prepare the backend assignments for this state and check whether
253
            // this group's summand may fire from it.
254
            let applicable = self.lps.prepare(enumerate, &full_state).any(|i| i == self.index);
255
            if !applicable {
256
                continue;
257
            }
258

            
259
            // Enumerate the successors, building the write side of each short
260
            // transition vector and unioning it into the relation.
261
            let write_indices = &self.write_indices;
262
            let write_positions = &self.write_positions;
263
            let interleaved = &mut interleaved;
264
            let relation = &mut relation;
265

            
266
            summand.enumerate(enumerate, &full_state, |_label, next_state| {
267
                for (m, &full_pos) in write_indices.iter().enumerate() {
268
                    let (index, _) = columns[full_pos as usize].insert(next_state[full_pos as usize]);
269
                    interleaved[write_positions[m]] = *index as Value;
270
                }
271

            
272
                let cube = storage.with_manager_shared(|m| LDDFunction::singleton(m, interleaved.as_slice()))?;
273
                *relation = relation.union(&cube)?;
274
                Ok(())
275
            })?;
276
        }
277

            
278
        self.relation = relation;
279
        Ok(())
280
    }
281
}
282

            
283
impl<L: LPS> fmt::Debug for SymbolicLps<L> {
284
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
285
        writeln!(f, "SymbolicLps:")?;
286
        for (i, group) in self.groups.iter().enumerate() {
287
            writeln!(f, "  {i}: {group:?}")?;
288
        }
289
        Ok(())
290
    }
291
}
292

            
293
impl<L: LPS> fmt::Debug for SymbolicLpsGroup<L> {
294
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
295
        write!(
296
            f,
297
            "group {} (read {:?}, write {:?})",
298
            self.index, self.read_indices, self.write_indices
299
        )
300
    }
301
}