Skip to main content

sas_plus/
fdr.rs

1//! Reader and writer for Fast Downward's translator output format
2//! (`output.sas`, file version 3).
3//!
4//! Fast Downward's translator grounds PDDL into a finite-domain
5//! representation (FDR / SAS+). [`SasFile`] mirrors that file faithfully,
6//! including mutex groups, conditional effects and axioms. It writes back
7//! byte-for-byte what it reads, and [`SasFile::to_task`] converts it to a
8//! plain [`Task`] when the task uses neither of the latter two.
9//!
10//! ```no_run
11//! let text = std::fs::read_to_string("output.sas")?;
12//! let file: sas_plus::fdr::SasFile = text.parse()?;
13//! let task = file.to_task()?;
14//! # Ok::<(), Box<dyn std::error::Error>>(())
15//! ```
16
17use alloc::format;
18use alloc::string::{String, ToString};
19use alloc::vec::Vec;
20use core::fmt::{self, Write as _};
21use core::str::FromStr;
22
23use crate::{Fact, OpId, Operator, State, Task, Value, VarId, Variable};
24
25/// The only file version this module understands (Fast Downward ≥ 20.06).
26pub const SAS_FILE_VERSION: u32 = 3;
27
28#[derive(Clone, Debug, PartialEq, Eq)]
29pub struct SasFile {
30    /// `false` means unit costs: every operator costs 1 whatever its cost field says.
31    pub use_metric: bool,
32    pub variables: Vec<SasVariable>,
33    pub mutex_groups: Vec<Vec<Fact>>,
34    pub initial: Vec<Value>,
35    pub goal: Vec<Fact>,
36    pub operators: Vec<SasOperator>,
37    pub axioms: Vec<SasAxiom>,
38}
39
40#[derive(Clone, Debug, PartialEq, Eq)]
41pub struct SasVariable {
42    pub name: String,
43    /// `None` for ordinary state variables, `Some(layer)` for derived variables.
44    pub axiom_layer: Option<u32>,
45    /// One name per value, e.g. `Atom at(ball1, rooma)` or `<none of those>`.
46    pub values: Vec<String>,
47}
48
49#[derive(Clone, Debug, PartialEq, Eq)]
50pub struct SasOperator {
51    /// Ground action name without parentheses, e.g. `pick ball1 rooma left`.
52    pub name: String,
53    /// Preconditions on variables the operator does not change.
54    pub prevail: Vec<Fact>,
55    pub effects: Vec<SasEffect>,
56    /// The cost field as written; see [`SasFile::operator_cost`].
57    pub cost: u32,
58}
59
60#[derive(Clone, Debug, PartialEq, Eq)]
61pub struct SasEffect {
62    /// Effect conditions; non-empty only for conditional effects.
63    pub conditions: Vec<Fact>,
64    pub var: VarId,
65    /// Required value before the effect (`None` = no precondition, written `-1`).
66    pub pre: Option<Value>,
67    pub post: Value,
68}
69
70#[derive(Clone, Debug, PartialEq, Eq)]
71pub struct SasAxiom {
72    pub conditions: Vec<Fact>,
73    pub var: VarId,
74    pub pre: Value,
75    pub post: Value,
76}
77
78/// A syntax or consistency error, with the 1-based line it was found on.
79#[derive(Clone, Debug, PartialEq, Eq)]
80pub struct ParseError {
81    pub line: usize,
82    pub message: String,
83}
84
85impl fmt::Display for ParseError {
86    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
87        write!(f, "output.sas line {}: {}", self.line, self.message)
88    }
89}
90
91impl core::error::Error for ParseError {}
92
93/// Why a [`SasFile`] cannot be represented as a plain [`Task`].
94#[derive(Clone, Debug, PartialEq, Eq)]
95pub enum ConversionError {
96    ConditionalEffect { operator: String },
97    Axioms { count: usize },
98    DerivedVariable { var: VarId },
99}
100
101impl fmt::Display for ConversionError {
102    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
103        match self {
104            Self::ConditionalEffect { operator } => {
105                write!(f, "operator `{operator}` has a conditional effect")
106            }
107            Self::Axioms { count } => write!(f, "task has {count} axiom rules"),
108            Self::DerivedVariable { var } => write!(f, "variable {var} is derived"),
109        }
110    }
111}
112
113impl core::error::Error for ConversionError {}
114
115impl SasFile {
116    pub fn parse(text: &str) -> Result<Self, ParseError> {
117        Parser::new(text).file()
118    }
119
120    /// The cost search should use for operator `op`.
121    pub fn operator_cost(&self, op: OpId) -> u32 {
122        if self.use_metric {
123            self.operators[op].cost
124        } else {
125            1
126        }
127    }
128
129    /// The name of a fact, e.g. `Atom at(ball1, rooma)`.
130    pub fn fact_name(&self, fact: Fact) -> &str {
131        &self.variables[fact.var].values[fact.value as usize]
132    }
133
134    /// Converts to a plain SAS+ task. Prevail conditions and effect
135    /// preconditions become operator preconditions; costs follow the metric.
136    pub fn to_task(&self) -> Result<Task, ConversionError> {
137        if !self.axioms.is_empty() {
138            return Err(ConversionError::Axioms {
139                count: self.axioms.len(),
140            });
141        }
142        if let Some(var) = self.variables.iter().position(|v| v.axiom_layer.is_some()) {
143            return Err(ConversionError::DerivedVariable { var });
144        }
145        let operators = self
146            .operators
147            .iter()
148            .enumerate()
149            .map(|(id, op)| {
150                if op.effects.iter().any(|e| !e.conditions.is_empty()) {
151                    return Err(ConversionError::ConditionalEffect {
152                        operator: op.name.clone(),
153                    });
154                }
155                let mut pre = op.prevail.clone();
156                pre.extend(
157                    op.effects
158                        .iter()
159                        .filter_map(|e| Some(Fact::new(e.var, e.pre?))),
160                );
161                pre.sort_unstable();
162                Ok(Operator {
163                    name: op.name.clone(),
164                    pre,
165                    eff: op
166                        .effects
167                        .iter()
168                        .map(|e| Fact::new(e.var, e.post))
169                        .collect(),
170                    cost: self.operator_cost(id),
171                })
172            })
173            .collect::<Result<_, _>>()?;
174        Ok(Task {
175            variables: self
176                .variables
177                .iter()
178                .map(|v| Variable {
179                    name: v.name.clone(),
180                    domain_size: v.values.len() as u32,
181                })
182                .collect(),
183            operators,
184            initial: State(self.initial.clone()),
185            goal: self.goal.clone(),
186        })
187    }
188
189    /// Formats a plan the way Fast Downward writes `sas_plan`, for use with
190    /// plan validators such as VAL.
191    pub fn format_plan(&self, plan: &[OpId]) -> String {
192        let mut out = String::new();
193        for &op in plan {
194            let _ = writeln!(out, "({})", self.operators[op].name);
195        }
196        let cost: u64 = plan
197            .iter()
198            .map(|&op| u64::from(self.operator_cost(op)))
199            .sum();
200        // Fast Downward labels by the costs themselves, not by the metric flag.
201        let unit = (0..self.operators.len()).all(|op| self.operator_cost(op) == 1);
202        let kind = if unit { "unit cost" } else { "general cost" };
203        let _ = writeln!(out, "; cost = {cost} ({kind})");
204        out
205    }
206}
207
208impl FromStr for SasFile {
209    type Err = ParseError;
210    fn from_str(s: &str) -> Result<Self, ParseError> {
211        Self::parse(s)
212    }
213}
214
215/// Writes the file exactly as Fast Downward's translator does.
216impl fmt::Display for SasFile {
217    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
218        writeln!(f, "begin_version\n{SAS_FILE_VERSION}\nend_version")?;
219        writeln!(f, "begin_metric\n{}\nend_metric", u8::from(self.use_metric))?;
220        writeln!(f, "{}", self.variables.len())?;
221        for v in &self.variables {
222            let layer = v.axiom_layer.map_or(-1, i64::from);
223            writeln!(f, "begin_variable\n{}\n{layer}\n{}", v.name, v.values.len())?;
224            for value in &v.values {
225                writeln!(f, "{value}")?;
226            }
227            writeln!(f, "end_variable")?;
228        }
229        writeln!(f, "{}", self.mutex_groups.len())?;
230        for group in &self.mutex_groups {
231            writeln!(f, "begin_mutex_group\n{}", group.len())?;
232            write_facts(f, group)?;
233            writeln!(f, "end_mutex_group")?;
234        }
235        writeln!(f, "begin_state")?;
236        for v in &self.initial {
237            writeln!(f, "{v}")?;
238        }
239        writeln!(f, "end_state\nbegin_goal\n{}", self.goal.len())?;
240        write_facts(f, &self.goal)?;
241        writeln!(f, "end_goal\n{}", self.operators.len())?;
242        for op in &self.operators {
243            writeln!(f, "begin_operator\n{}\n{}", op.name, op.prevail.len())?;
244            write_facts(f, &op.prevail)?;
245            writeln!(f, "{}", op.effects.len())?;
246            for e in &op.effects {
247                write!(f, "{} ", e.conditions.len())?;
248                for c in &e.conditions {
249                    write!(f, "{} {} ", c.var, c.value)?;
250                }
251                let pre = e.pre.map_or(-1, i64::from);
252                writeln!(f, "{} {pre} {}", e.var, e.post)?;
253            }
254            writeln!(f, "{}\nend_operator", op.cost)?;
255        }
256        writeln!(f, "{}", self.axioms.len())?;
257        for a in &self.axioms {
258            writeln!(f, "begin_rule\n{}", a.conditions.len())?;
259            write_facts(f, &a.conditions)?;
260            writeln!(f, "{} {} {}\nend_rule", a.var, a.pre, a.post)?;
261        }
262        Ok(())
263    }
264}
265
266fn write_facts(f: &mut fmt::Formatter<'_>, facts: &[Fact]) -> fmt::Result {
267    facts
268        .iter()
269        .try_for_each(|x| writeln!(f, "{} {}", x.var, x.value))
270}
271
272struct Parser<'a> {
273    lines: core::str::Lines<'a>,
274    line: usize,
275    /// Domain sizes of the variables read so far, for range checks.
276    domains: Vec<u32>,
277}
278
279impl<'a> Parser<'a> {
280    fn new(text: &'a str) -> Self {
281        Self {
282            lines: text.lines(),
283            line: 0,
284            domains: Vec::new(),
285        }
286    }
287
288    fn error<T>(&self, message: impl Into<String>) -> Result<T, ParseError> {
289        Err(ParseError {
290            line: self.line,
291            message: message.into(),
292        })
293    }
294
295    fn next(&mut self) -> Result<&'a str, ParseError> {
296        self.line += 1;
297        match self.lines.next() {
298            Some(l) => Ok(l.trim_end_matches('\r')),
299            None => self.error("unexpected end of file"),
300        }
301    }
302
303    fn expect(&mut self, keyword: &str) -> Result<(), ParseError> {
304        let l = self.next()?;
305        if l.trim() == keyword {
306            Ok(())
307        } else {
308            self.error(format!("expected `{keyword}`, found `{l}`"))
309        }
310    }
311
312    fn numbers(&mut self) -> Result<Vec<i64>, ParseError> {
313        let l = self.next()?;
314        l.split_whitespace()
315            .map(|t| t.parse::<i64>())
316            .collect::<Result<_, _>>()
317            .or_else(|_| self.error(format!("expected integers, found `{l}`")))
318    }
319
320    fn number<T: TryFrom<i64>>(&mut self, what: &str) -> Result<T, ParseError> {
321        match self.numbers()?.as_slice() {
322            &[n] => T::try_from(n).or_else(|_| self.error(format!("{what} out of range: {n}"))),
323            _ => self.error(format!("expected a single integer ({what})")),
324        }
325    }
326
327    fn var(&self, n: i64) -> Result<VarId, ParseError> {
328        match usize::try_from(n) {
329            Ok(v) if v < self.domains.len() => Ok(v),
330            _ => self.error(format!("variable {n} does not exist")),
331        }
332    }
333
334    fn value(&self, var: VarId, n: i64) -> Result<Value, ParseError> {
335        match u32::try_from(n) {
336            Ok(v) if v < self.domains[var] => Ok(v),
337            _ => self.error(format!("value {n} out of range for variable {var}")),
338        }
339    }
340
341    fn fact_from(&self, var: i64, value: i64) -> Result<Fact, ParseError> {
342        let var = self.var(var)?;
343        Ok(Fact::new(var, self.value(var, value)?))
344    }
345
346    fn fact(&mut self) -> Result<Fact, ParseError> {
347        match self.numbers()?.as_slice() {
348            &[var, value] => self.fact_from(var, value),
349            _ => self.error("expected `<var> <value>`"),
350        }
351    }
352
353    fn facts(&mut self, what: &str) -> Result<Vec<Fact>, ParseError> {
354        let n: usize = self.number(what)?;
355        (0..n).map(|_| self.fact()).collect()
356    }
357
358    fn file(mut self) -> Result<SasFile, ParseError> {
359        self.expect("begin_version")?;
360        let version: u32 = self.number("version")?;
361        if version != SAS_FILE_VERSION {
362            return self.error(format!(
363                "unsupported file version {version} (expected {SAS_FILE_VERSION})"
364            ));
365        }
366        self.expect("end_version")?;
367
368        self.expect("begin_metric")?;
369        let use_metric = match self.number::<i64>("metric")? {
370            0 => false,
371            1 => true,
372            m => return self.error(format!("metric must be 0 or 1, found {m}")),
373        };
374        self.expect("end_metric")?;
375
376        let num_vars: usize = self.number("number of variables")?;
377        let variables = (0..num_vars)
378            .map(|_| self.variable())
379            .collect::<Result<Vec<_>, _>>()?;
380
381        let num_mutex: usize = self.number("number of mutex groups")?;
382        let mutex_groups = (0..num_mutex)
383            .map(|_| {
384                self.expect("begin_mutex_group")?;
385                let facts = self.facts("mutex group size")?;
386                self.expect("end_mutex_group")?;
387                Ok(facts)
388            })
389            .collect::<Result<_, ParseError>>()?;
390
391        self.expect("begin_state")?;
392        let initial = (0..num_vars)
393            .map(|var| {
394                let n = self.number::<i64>("initial value")?;
395                self.value(var, n)
396            })
397            .collect::<Result<_, _>>()?;
398        self.expect("end_state")?;
399
400        self.expect("begin_goal")?;
401        let goal = self.facts("number of goal facts")?;
402        self.expect("end_goal")?;
403
404        let num_ops: usize = self.number("number of operators")?;
405        let operators = (0..num_ops)
406            .map(|_| self.operator())
407            .collect::<Result<_, _>>()?;
408
409        let num_axioms: usize = self.number("number of axioms")?;
410        let axioms = (0..num_axioms)
411            .map(|_| self.axiom())
412            .collect::<Result<_, _>>()?;
413
414        while let Some(extra) = self.lines.next() {
415            self.line += 1;
416            if !extra.trim().is_empty() {
417                return self.error(format!(
418                    "unexpected content after the last axiom: `{extra}`"
419                ));
420            }
421        }
422        Ok(SasFile {
423            use_metric,
424            variables,
425            mutex_groups,
426            initial,
427            goal,
428            operators,
429            axioms,
430        })
431    }
432
433    fn variable(&mut self) -> Result<SasVariable, ParseError> {
434        self.expect("begin_variable")?;
435        let name = self.next()?.to_string();
436        let axiom_layer = match self.number::<i64>("axiom layer")? {
437            -1 => None,
438            l => {
439                Some(u32::try_from(l).or_else(|_| self.error(format!("invalid axiom layer {l}")))?)
440            }
441        };
442        let size: u32 = self.number("domain size")?;
443        if size == 0 {
444            return self.error("empty variable domain");
445        }
446        let values = (0..size)
447            .map(|_| self.next().map(str::to_string))
448            .collect::<Result<_, _>>()?;
449        self.expect("end_variable")?;
450        self.domains.push(size);
451        Ok(SasVariable {
452            name,
453            axiom_layer,
454            values,
455        })
456    }
457
458    fn operator(&mut self) -> Result<SasOperator, ParseError> {
459        self.expect("begin_operator")?;
460        let name = self.next()?.to_string();
461        let prevail = self.facts("number of prevail conditions")?;
462        let num_effects: usize = self.number("number of effects")?;
463        let effects = (0..num_effects)
464            .map(|_| self.effect())
465            .collect::<Result<_, _>>()?;
466        let cost: u32 = self.number("operator cost")?;
467        self.expect("end_operator")?;
468        Ok(SasOperator {
469            name,
470            prevail,
471            effects,
472            cost,
473        })
474    }
475
476    /// `<#conds> [<var> <val>]* <var> <pre> <post>` on one line.
477    fn effect(&mut self) -> Result<SasEffect, ParseError> {
478        let nums = self.numbers()?;
479        let Some((&count, rest)) = nums.split_first() else {
480            return self.error("empty effect line");
481        };
482        let count = usize::try_from(count).or_else(|_| self.error("negative condition count"))?;
483        if rest.len() != 2 * count + 3 {
484            return self.error(format!(
485                "effect with {count} conditions needs {} integers",
486                2 * count + 4
487            ));
488        }
489        let conditions = rest[..2 * count]
490            .chunks(2)
491            .map(|c| self.fact_from(c[0], c[1]))
492            .collect::<Result<_, _>>()?;
493        let var = self.var(rest[2 * count])?;
494        let pre = match rest[2 * count + 1] {
495            -1 => None,
496            p => Some(self.value(var, p)?),
497        };
498        let post = self.value(var, rest[2 * count + 2])?;
499        Ok(SasEffect {
500            conditions,
501            var,
502            pre,
503            post,
504        })
505    }
506
507    fn axiom(&mut self) -> Result<SasAxiom, ParseError> {
508        self.expect("begin_rule")?;
509        let conditions = self.facts("number of axiom conditions")?;
510        let (var, pre, post) = match self.numbers()?.as_slice() {
511            &[var, pre, post] => {
512                let var = self.var(var)?;
513                (var, self.value(var, pre)?, self.value(var, post)?)
514            }
515            _ => return self.error("expected `<var> <pre> <post>`"),
516        };
517        self.expect("end_rule")?;
518        Ok(SasAxiom {
519            conditions,
520            var,
521            pre,
522            post,
523        })
524    }
525}