1use 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
25pub 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 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 pub axiom_layer: Option<u32>,
47 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 pub name: String,
56 pub prevail: Vec<Fact>,
58 pub effects: Vec<SasEffect>,
59 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 pub conditions: Vec<Fact>,
68 pub var: VarId,
69 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#[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 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 pub fn fact_name(&self, fact: Fact) -> &str {
115 &self.variables[fact.var].values[fact.value as usize]
116 }
117
118 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 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 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 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
201impl 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 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 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 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}