Skip to main content

sas_plus/
projection.rs

1use alloc::vec;
2use alloc::vec::Vec;
3
4use crate::ranking::Ranking;
5use crate::{Abstraction, LabeledTransitionSystem, State, Task, Transition, Value, VarId};
6
7/// Projection of a task onto a subset of variables (a "pattern"); the
8/// abstraction underlying pattern databases.
9///
10/// Derived variables are dropped from the pattern, so conditions on them are
11/// treated as satisfiable. A conditional effect whose conditions mention
12/// variables outside the pattern may or may not fire, and both outcomes get a
13/// transition. Both keep the abstraction admissible.
14///
15/// An operator gets one transition per abstract state matching its
16/// precondition, times the product, over the pattern variables it may set
17/// through such uncertain effects, of the number of values each may end with.
18/// That is never more than the number of abstract states, but on a large
19/// pattern the transition list can grow toward
20/// `operators × abstract states × abstract states`; size patterns accordingly.
21#[derive(Clone, Debug)]
22pub struct Projection {
23    ranking: Ranking,
24    lts: LabeledTransitionSystem,
25}
26
27impl Projection {
28    pub fn new(task: &Task, mut pattern: Vec<VarId>) -> Self {
29        pattern.retain(|&v| !task.variables[v].is_derived());
30        pattern.sort_unstable();
31        pattern.dedup();
32        let ranking = Ranking::new(task, pattern);
33
34        let mut transitions = Vec::new();
35        // Per pattern position, the values it may end with; reused across states.
36        let mut outcomes: Vec<Vec<Value>> = vec![Vec::new(); ranking.vars.len()];
37        let mut touched: Vec<usize> = Vec::new();
38        let mut digits: Vec<usize> = Vec::new();
39        for (label, op) in task.operators.iter().enumerate() {
40            // Effects on pattern variables: (position, value, conditions, sure to fire if
41            // their pattern conditions hold, i.e. no conditions outside the pattern).
42            let effects: Vec<(usize, Value, &[crate::Fact], bool)> = op
43                .eff
44                .iter()
45                .filter_map(|e| {
46                    let i = ranking.position(e.fact.var)?;
47                    let sure = e
48                        .conditions
49                        .iter()
50                        .all(|c| ranking.position(c.var).is_some());
51                    Some((i, e.fact.value, e.conditions.as_slice(), sure))
52                })
53                .collect();
54            let unconditional = effects.iter().all(|e| e.2.is_empty());
55            // Only abstract states consistent with the precondition.
56            for src in ranking.matching(&op.pre) {
57                if unconditional {
58                    let dst = effects.iter().fold(src, |d, e| ranking.set(d, e.0, e.1));
59                    transitions.push(Transition { src, label, dst });
60                    continue;
61                }
62                // Effects apply in order, so a variable ends with the value of its last
63                // firing effect. A sure effect fixes that value; a maybe effect adds an
64                // alternative. Each effect sets one variable, so the variables are
65                // independent and the successors are all combinations.
66                for &i in &touched {
67                    outcomes[i].clear();
68                }
69                touched.clear();
70                for &(i, value, conditions, sure) in &effects {
71                    if !ranking.holds(src, conditions) {
72                        continue;
73                    }
74                    let values = &mut outcomes[i];
75                    if values.is_empty() {
76                        touched.push(i);
77                        values.push(ranking.value(src, i) as Value);
78                    }
79                    if sure {
80                        values.clear();
81                        values.push(value);
82                    } else if !values.contains(&value) {
83                        values.push(value);
84                    }
85                }
86                digits.clear();
87                digits.resize(touched.len(), 0);
88                loop {
89                    let dst = touched
90                        .iter()
91                        .zip(&digits)
92                        .fold(src, |d, (&i, &k)| ranking.set(d, i, outcomes[i][k]));
93                    transitions.push(Transition { src, label, dst });
94                    let Some(j) =
95                        (0..touched.len()).find(|&j| digits[j] + 1 < outcomes[touched[j]].len())
96                    else {
97                        break;
98                    };
99                    digits[j] += 1;
100                    digits[..j].fill(0);
101                }
102            }
103        }
104        let mut goal = vec![false; ranking.num_states];
105        ranking.matching(&task.goal).for_each(|s| goal[s] = true);
106        let lts = LabeledTransitionSystem {
107            num_states: ranking.num_states,
108            num_labels: task.operators.len(),
109            transitions,
110            goal,
111            initial: Some(ranking.rank(&task.initial)),
112        };
113        Self { ranking, lts }
114    }
115
116    pub fn pattern(&self) -> &[VarId] {
117        &self.ranking.vars
118    }
119
120    /// Index of the abstract state that `state` projects to.
121    pub fn rank(&self, state: &State) -> usize {
122        self.ranking.rank(state)
123    }
124}
125
126impl Abstraction for Projection {
127    fn lts(&self) -> &LabeledTransitionSystem {
128        &self.lts
129    }
130    fn abstract_state(&self, state: &State) -> Option<usize> {
131        Some(self.rank(state))
132    }
133}