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