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::{Fact, OpId, Operator, State, Task, Value, VarId, Variable};
24
25pub const SAS_FILE_VERSION: u32 = 3;
27
28#[derive(Clone, Debug, PartialEq, Eq)]
29pub struct SasFile {
30 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 pub axiom_layer: Option<u32>,
45 pub values: Vec<String>,
47}
48
49#[derive(Clone, Debug, PartialEq, Eq)]
50pub struct SasOperator {
51 pub name: String,
53 pub prevail: Vec<Fact>,
55 pub effects: Vec<SasEffect>,
56 pub cost: u32,
58}
59
60#[derive(Clone, Debug, PartialEq, Eq)]
61pub struct SasEffect {
62 pub conditions: Vec<Fact>,
64 pub var: VarId,
65 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#[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#[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 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 pub fn fact_name(&self, fact: Fact) -> &str {
131 &self.variables[fact.var].values[fact.value as usize]
132 }
133
134 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 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 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
215impl 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 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 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}