jia_parse/
ast.rs

1//! Abstract Syntax Tree (AST) for PDDL domain and problem files.
2//!
3//! Every type here is produced by the parser (see [`super::parser`]). The AST is a direct
4//! structural representation of the PDDL syntax: no semantic analysis, type checking, or
5//! planning is performed at this stage.
6
7use serde::Serialize;
8
9// ---------------------------------------------------------------------------
10// Names & identifiers
11// ---------------------------------------------------------------------------
12
13/// A symbol name: predicate/action/object names, type names, etc.
14pub type Name = String;
15
16/// A variable reference including the leading `?` (e.g. `?x`, `?from`).
17pub type Variable = String; // includes the leading '?'
18
19// ---------------------------------------------------------------------------
20// Requirements
21// ---------------------------------------------------------------------------
22
23/// PDDL requirement flags declared in the `:requirements` section of a domain.
24#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize)]
25pub enum Requirement {
26    Strips,
27    Typing,
28    NegativePreconditions,
29    DisjunctivePreconditions,
30    Equality,
31    ExistentialPreconditions,
32    UniversalPreconditions,
33    QuantifiedPreconditions,
34    ConditionalEffects,
35    Fluents,
36    NumericFluents,
37    Adl,
38    DurativeActions,
39    DurationInequalities,
40    TimedInitialLiterals,
41    Preferences,
42    Constraints,
43    ActionCosts,
44    GoalUtilities,
45    DerivedPredicates,
46    DomainAxioms,
47}
48
49// ---------------------------------------------------------------------------
50// Typed lists: "?x ?y - type1 ?z - type2"
51// ---------------------------------------------------------------------------
52
53/// A group of items sharing a common PDDL type.
54///
55/// For example, `?x ?y - location` is represented as:
56///
57/// ```text
58/// TypedGroup { items: ["?x", "?y"], type_name: Some("location") }
59/// ```
60///
61/// When no type is specified (untyped PDDL), `type_name` is `None`.
62#[derive(Debug, Clone, PartialEq, Serialize)]
63pub struct TypedGroup<T: Serialize> {
64    /// The items sharing this type.
65    pub items: Vec<T>,
66    /// The PDDL type name, or `None` for untyped items (implicitly type `object`).
67    pub type_name: Option<Name>,
68}
69
70/// A sequence of typed groups; the standard PDDL typed-list construct (e.g. `?x ?y - type1 ?z - type2`).
71pub type TypedList<T> = Vec<TypedGroup<T>>;
72
73// ---------------------------------------------------------------------------
74// Type declarations (with hierarchy)
75// ---------------------------------------------------------------------------
76
77/// Represents type declarations like `driver truck obj - locatable`.
78pub type TypeDeclarations = TypedList<Name>;
79
80// ---------------------------------------------------------------------------
81// Predicate / Function declarations
82// ---------------------------------------------------------------------------
83
84/// A predicate declaration from the `:predicates` section, with name and typed parameters.
85#[derive(Debug, Clone, PartialEq, Serialize)]
86pub struct PredicateDecl {
87    pub name: Name,
88    pub parameters: TypedList<Variable>,
89}
90
91/// A numeric function declaration from `:functions`, with optional return type.
92#[derive(Debug, Clone, PartialEq, Serialize)]
93pub struct FunctionDecl {
94    pub name: Name,
95    pub parameters: TypedList<Variable>,
96    pub return_type: Option<Name>,
97}
98
99// ---------------------------------------------------------------------------
100// Numeric expressions
101// ---------------------------------------------------------------------------
102
103/// A numeric expression tree used in preconditions, effects, durations, and metrics.
104///
105/// N-ary PDDL operators like `(+ a b c)` are desugared into nested binary operations
106/// during parsing, e.g. `(+ (+ a b) c)`.
107#[derive(Debug, Clone, PartialEq, Serialize)]
108pub enum NumericExpr {
109    /// A numeric literal (e.g. `3.14`, `0`, `100`).
110    Number(f64),
111    /// A reference to a numeric fluent (e.g. `(distance ?x ?y)`).
112    FunctionCall(FunctionTerm),
113    /// A binary arithmetic operation.
114    BinaryOp {
115        op: BinaryOp,
116        left: Box<NumericExpr>,
117        right: Box<NumericExpr>,
118    },
119    /// Unary negation (e.g. `(- expr)`).
120    Negate(Box<NumericExpr>),
121    /// The built-in `total-time` expression (plan makespan).
122    TotalTime,
123    /// The `?duration` variable inside durative action constraints.
124    Duration,
125}
126
127/// Arithmetic binary operators for [`NumericExpr::BinaryOp`].
128#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
129pub enum BinaryOp {
130    /// Addition (`+`).
131    Add,
132    /// Subtraction (`-`).
133    Sub,
134    /// Multiplication (`*`).
135    Mul,
136    /// Division (`/`).
137    Div,
138}
139
140/// A reference to a numeric function (fluent) with its arguments.
141///
142/// For example, `(distance ?from ?to)` becomes:
143///
144/// ```text
145/// FunctionTerm { name: "distance", args: [Variable("?from"), Variable("?to")] }
146/// ```
147#[derive(Debug, Clone, PartialEq, Serialize)]
148pub struct FunctionTerm {
149    /// The function (fluent) name.
150    pub name: Name,
151    /// The arguments to the function, each a constant name or variable reference.
152    pub args: Vec<Term>,
153}
154
155/// A term appearing as an argument to a predicate or function.
156#[derive(Debug, Clone, PartialEq, Serialize)]
157pub enum Term {
158    /// A constant (object) name, e.g. `city1`, `truck-a`.
159    Name(Name),
160    /// A variable reference, e.g. `?x`. Includes the leading `?`.
161    Variable(Variable),
162}
163
164// ---------------------------------------------------------------------------
165// Comparisons
166// ---------------------------------------------------------------------------
167
168/// Numeric comparison operators used in [`Condition::NumericComparison`] and
169/// [`DurationConstraint::Cmp`].
170#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
171pub enum CompareOp {
172    /// `<` -- strictly less than.
173    Lt,
174    /// `<=` -- less than or equal.
175    Lte,
176    /// `>` -- strictly greater than.
177    Gt,
178    /// `>=` -- greater than or equal.
179    Gte,
180    /// `=` -- equal.
181    Eq,
182}
183
184// ---------------------------------------------------------------------------
185// Conditions / Goal descriptions
186// ---------------------------------------------------------------------------
187
188/// A condition (goal description) in PDDL.
189///
190/// This is the central recursive type for preconditions, goals, and constraint bodies.
191/// It covers logical connectives, first-order quantifiers, predicate tests, numeric
192/// comparisons, temporal wrappers (durative actions), PDDL3 trajectory constraints,
193/// and preferences.
194#[derive(Debug, Clone, PartialEq, Serialize)]
195pub enum Condition {
196    /// Conjunction: `(and c1 c2 ...)`.
197    And(Vec<Condition>),
198    /// Disjunction: `(or c1 c2 ...)`.
199    Or(Vec<Condition>),
200    /// Negation: `(not c)`.
201    Not(Box<Condition>),
202    /// Implication: `(imply c1 c2)`.
203    Imply(Box<Condition>, Box<Condition>),
204    /// Universal quantification: `(forall (?x - type) c)`.
205    Forall {
206        variables: TypedList<Variable>,
207        condition: Box<Condition>,
208    },
209    /// Existential quantification: `(exists (?x - type) c)`.
210    Exists {
211        variables: TypedList<Variable>,
212        condition: Box<Condition>,
213    },
214    /// A positive predicate test: `(at ?x ?y)`.
215    Predicate(AtomicFormula),
216    /// Object equality: `(= ?x ?y)`.
217    Equals(Term, Term),
218    /// Numeric comparison: `(<op> <expr> <expr>)`.
219    NumericComparison {
220        op: CompareOp,
221        left: NumericExpr,
222        right: NumericExpr,
223    },
224    /// PDDL3 named preference: `(preference <name> <cond>)`.
225    Preference {
226        name: Option<Name>,
227        condition: Box<Condition>,
228    },
229
230    // -- Temporal conditions (only inside durative actions) --
231    /// `(at start <cond>)` -- holds at the action's start.
232    AtStart(Box<Condition>),
233    /// `(at end <cond>)` -- holds at the action's end.
234    AtEnd(Box<Condition>),
235    /// `(over all <cond>)` -- holds throughout the action.
236    OverAll(Box<Condition>),
237
238    // -- PDDL3 trajectory constraints --
239    /// `(always <cond>)`.
240    Always(Box<Condition>),
241    /// `(sometime <cond>)`.
242    Sometime(Box<Condition>),
243    /// `(at-most-once <cond>)`.
244    AtMostOnce(Box<Condition>),
245    /// `(within <deadline> <cond>)`.
246    Within(f64, Box<Condition>),
247    /// `(sometime-before <cond1> <cond2>)`.
248    SometimeBefore(Box<Condition>, Box<Condition>),
249    /// `(sometime-after <cond1> <cond2>)`.
250    SometimeAfter(Box<Condition>, Box<Condition>),
251    /// `(always-within <window> <cond1> <cond2>)`.
252    AlwaysWithin(f64, Box<Condition>, Box<Condition>),
253    /// `(hold-during <t1> <t2> <cond>)`.
254    HoldDuring(f64, f64, Box<Condition>),
255    /// `(hold-after <t> <cond>)`.
256    HoldAfter(f64, Box<Condition>),
257}
258
259/// A predicate applied to arguments, e.g. `(at truck1 city-a)`.
260#[derive(Debug, Clone, PartialEq, Serialize)]
261pub struct AtomicFormula {
262    /// The predicate name.
263    pub name: Name,
264    /// Arguments (constants or variables).
265    pub args: Vec<Term>,
266}
267
268// ---------------------------------------------------------------------------
269// Effects
270// ---------------------------------------------------------------------------
271
272/// An action effect.
273///
274/// Effects can add/delete predicate instances, perform numeric assignments,
275/// and include conditional (`when`) and universal (`forall`) sub-effects.
276/// Inside durative actions, effects are wrapped in temporal markers (`AtStart`, `AtEnd`).
277#[derive(Debug, Clone, PartialEq, Serialize)]
278pub enum Effect {
279    /// Conjunction: `(and e1 e2 ...)`.
280    And(Vec<Effect>),
281    /// Add (assert) a predicate instance.
282    Predicate(AtomicFormula),
283    /// Delete (negate) a predicate instance: `(not (pred ...))`.
284    NotPredicate(AtomicFormula),
285    /// Universal effect: `(forall (?x - type) <effect>)`.
286    Forall {
287        variables: TypedList<Variable>,
288        effect: Box<Effect>,
289    },
290    /// Conditional effect: `(when <condition> <effect>)`.
291    When {
292        condition: Condition,
293        effect: Box<Effect>,
294    },
295    /// Numeric assignment: `(assign/increase/decrease/scale-up/scale-down <fn> <expr>)`.
296    NumericAssign {
297        op: AssignOp,
298        function: FunctionTerm,
299        expr: NumericExpr,
300    },
301
302    // -- Temporal effects (only inside durative actions) --
303    /// `(at start <effect>)`.
304    AtStart(Box<Effect>),
305    /// `(at end <effect>)`.
306    AtEnd(Box<Effect>),
307}
308
309/// Numeric assignment operators for [`Effect::NumericAssign`].
310#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
311pub enum AssignOp {
312    /// `(assign <fn> <expr>)` -- set to value.
313    Assign,
314    /// `(scale-up <fn> <expr>)` -- multiply.
315    ScaleUp,
316    /// `(scale-down <fn> <expr>)` -- divide.
317    ScaleDown,
318    /// `(increase <fn> <expr>)` -- add.
319    Increase,
320    /// `(decrease <fn> <expr>)` -- subtract.
321    Decrease,
322}
323
324// ---------------------------------------------------------------------------
325// Duration constraints
326// ---------------------------------------------------------------------------
327
328/// Duration constraint on a durative action (e.g. `(= ?duration 5)`, `(>= ?duration (distance ?x ?y))`).
329#[derive(Debug, Clone, PartialEq, Serialize)]
330pub enum DurationConstraint {
331    /// Conjunction of multiple duration constraints.
332    And(Vec<DurationConstraint>),
333    /// A single comparison against `?duration`.
334    Cmp {
335        /// The comparison operator (`=`, `>=`, `<=`).
336        op: CompareOp,
337        /// The right-hand-side expression (left-hand side is always `?duration`).
338        expr: NumericExpr,
339    },
340}
341
342// ---------------------------------------------------------------------------
343// Actions
344// ---------------------------------------------------------------------------
345
346/// A non-temporal (instantaneous) PDDL action defined with `:action`.
347#[derive(Debug, Clone, PartialEq, Serialize)]
348pub struct BasicAction {
349    /// The action name (e.g. `"drive"`).
350    pub name: Name,
351    /// Typed parameter list. Includes any PDDL 1.2 `:vars` parameters.
352    pub parameters: TypedList<Variable>,
353    /// Optional precondition; `None` means unconditionally applicable.
354    pub precondition: Option<Condition>,
355    /// Optional effect; `None` means no state change.
356    pub effect: Option<Effect>,
357}
358
359/// A temporal PDDL action defined with `:durative-action`.
360///
361/// Conditions and effects may contain temporal wrappers (`at start`, `at end`, `over all`).
362#[derive(Debug, Clone, PartialEq, Serialize)]
363pub struct DurativeAction {
364    /// The action name (e.g. `"drive"`).
365    pub name: Name,
366    /// Typed parameter list.
367    pub parameters: TypedList<Variable>,
368    /// Duration constraint (e.g. `(= ?duration 10)`).
369    pub duration: DurationConstraint,
370    /// Optional condition with temporal annotations.
371    pub condition: Option<Condition>,
372    /// Optional effect with temporal annotations.
373    pub effect: Option<Effect>,
374}
375
376// ---------------------------------------------------------------------------
377// Derived predicates
378// ---------------------------------------------------------------------------
379
380/// A derived predicate (`:derived`) with axiom body.
381#[derive(Debug, Clone, PartialEq, Serialize)]
382pub struct DerivedPredicate {
383    pub predicate: AtomicFormula,
384    pub condition: Condition,
385}
386
387// ---------------------------------------------------------------------------
388// Init elements (problem file)
389// ---------------------------------------------------------------------------
390
391/// An element of the problem's `:init` section.
392#[derive(Debug, Clone, PartialEq, Serialize)]
393pub enum InitElement {
394    /// A predicate that holds in the initial state (e.g. `(at truck1 s0)`).
395    Predicate(AtomicFormula),
396    /// A negated predicate in the initial state (e.g. `(not (visited c1))`).
397    NotPredicate(AtomicFormula),
398    /// A numeric fluent initialization (e.g. `(= (distance a b) 10)`).
399    NumericAssignment(FunctionTerm, f64),
400    /// A timed initial literal: `(at <time> <literal>)`. The inner element is
401    /// typically a `Predicate` or `NotPredicate`.
402    At(f64, Box<InitElement>),
403}
404
405// ---------------------------------------------------------------------------
406// Metric specification
407// ---------------------------------------------------------------------------
408
409/// Optimization direction for the `:metric` specification.
410#[derive(Debug, Clone, PartialEq, Serialize)]
411pub enum Optimization {
412    /// `minimize` the metric expression.
413    Minimize,
414    /// `maximize` the metric expression.
415    Maximize,
416}
417
418/// The `:metric` specification combining optimization direction and expression.
419#[derive(Debug, Clone, PartialEq, Serialize)]
420pub struct MetricSpec {
421    pub optimization: Optimization,
422    pub expr: NumericExpr,
423}
424
425// ---------------------------------------------------------------------------
426// Top-level structures
427// ---------------------------------------------------------------------------
428
429/// A parsed PDDL domain file.
430///
431/// Produced by [`super::parser::parse_domain`] / [`super::parser::parse_domain_str`].
432#[derive(Debug, Clone, PartialEq, Serialize)]
433pub struct Domain {
434    /// The domain name from `(domain <name>)`.
435    pub name: Name,
436    /// Declared requirements (`:requirements`).
437    pub requirements: Vec<Requirement>,
438    /// Type hierarchy declarations (`:types`).
439    pub types: TypeDeclarations,
440    /// Domain-level constants (`:constants`).
441    pub constants: TypedList<Name>,
442    /// Predicate declarations (`:predicates`).
443    pub predicates: Vec<PredicateDecl>,
444    /// Numeric function declarations (`:functions`).
445    pub functions: Vec<FunctionDecl>,
446    /// Instantaneous actions (`:action`).
447    pub actions: Vec<BasicAction>,
448    /// Temporal actions (`:durative-action`).
449    pub durative_actions: Vec<DurativeAction>,
450    /// Derived predicates / axioms (`:derived`).
451    pub derived_predicates: Vec<DerivedPredicate>,
452}
453
454impl Domain {
455    /// Sort all declaration lists alphabetically by name.
456    ///
457    /// Sorts predicates, functions, actions, durative actions, derived predicates,
458    /// and items within each typed group (constants, types) for deterministic ordering.
459    pub fn sort_alphabetically(&mut self) {
460        for group in &mut self.types {
461            group.items.sort();
462        }
463        for group in &mut self.constants {
464            group.items.sort();
465        }
466        self.predicates.sort_by(|a, b| a.name.cmp(&b.name));
467        self.functions.sort_by(|a, b| a.name.cmp(&b.name));
468        self.actions.sort_by(|a, b| a.name.cmp(&b.name));
469        self.durative_actions.sort_by(|a, b| a.name.cmp(&b.name));
470        self.derived_predicates
471            .sort_by(|a, b| a.predicate.name.cmp(&b.predicate.name));
472    }
473}
474
475/// A parsed PDDL problem file.
476///
477/// Produced by [`super::parser::parse_problem`] / [`super::parser::parse_problem_str`].
478#[derive(Debug, Clone, PartialEq, Serialize)]
479pub struct Problem {
480    /// The problem name from `(problem <name>)`.
481    pub name: Name,
482    /// The domain this problem refers to, from `(:domain <name>)`.
483    pub domain_name: Name,
484    /// Declared requirements (`:requirements`), if any.
485    pub requirements: Vec<Requirement>,
486    /// Typed object list (`:objects`).
487    pub objects: TypedList<Name>,
488    /// Initial state elements (`:init`).
489    pub init: Vec<InitElement>,
490    /// Goal condition (`:goal`).
491    pub goal: Condition,
492    /// Optional optimization metric (`:metric`).
493    pub metric: Option<MetricSpec>,
494    /// Optional PDDL3 trajectory constraints (`:constraints`).
495    pub constraints: Option<Condition>,
496}
497
498impl Problem {
499    /// Sort object lists and init elements alphabetically for deterministic ordering.
500    pub fn sort_alphabetically(&mut self) {
501        for group in &mut self.objects {
502            group.items.sort();
503        }
504        self.init.sort_by_key(init_sort_key);
505    }
506}
507
508/// Format an atomic formula for sorting purposes.
509fn format_atomic_formula(af: &AtomicFormula) -> String {
510    if af.args.is_empty() {
511        af.name.clone()
512    } else {
513        let args: Vec<&str> = af.args.iter().map(term_name).collect();
514        format!("{}({})", af.name, args.join(","))
515    }
516}
517
518/// Format a function term for sorting purposes.
519fn format_function_term(ft: &FunctionTerm) -> String {
520    if ft.args.is_empty() {
521        ft.name.clone()
522    } else {
523        let args: Vec<&str> = ft.args.iter().map(term_name).collect();
524        format!("{}({})", ft.name, args.join(","))
525    }
526}
527
528/// Compute a sort key for an init element.
529fn init_sort_key(e: &InitElement) -> (u8, String) {
530    match e {
531        InitElement::Predicate(af) => (0, format_atomic_formula(af)),
532        InitElement::NotPredicate(af) => (1, format_atomic_formula(af)),
533        InitElement::NumericAssignment(ft, _) => (2, format_function_term(ft)),
534        InitElement::At(t, inner) => {
535            let (_, s) = init_sort_key(inner);
536            (3, format!("{t:.6}{s}"))
537        }
538    }
539}
540
541/// Extract the name from a Term for sorting.
542fn term_name(t: &Term) -> &str {
543    match t {
544        Term::Name(n) => n.as_str(),
545        Term::Variable(v) => v.as_str(),
546    }
547}
548
549#[cfg(test)]
550mod tests {
551    use super::*;
552
553    #[test]
554    fn domain_sort_orders_all_named_declarations() {
555        let mut domain = Domain {
556            name: "d".to_string(),
557            requirements: Vec::new(),
558            types: vec![TypedGroup {
559                items: vec!["z".to_string(), "a".to_string()],
560                type_name: None,
561            }],
562            constants: vec![TypedGroup {
563                items: vec!["c2".to_string(), "c1".to_string()],
564                type_name: None,
565            }],
566            predicates: vec![
567                PredicateDecl {
568                    name: "zpred".to_string(),
569                    parameters: Vec::new(),
570                },
571                PredicateDecl {
572                    name: "apred".to_string(),
573                    parameters: Vec::new(),
574                },
575            ],
576            functions: vec![
577                FunctionDecl {
578                    name: "zfunc".to_string(),
579                    parameters: Vec::new(),
580                    return_type: None,
581                },
582                FunctionDecl {
583                    name: "afunc".to_string(),
584                    parameters: Vec::new(),
585                    return_type: None,
586                },
587            ],
588            actions: vec![
589                BasicAction {
590                    name: "zact".to_string(),
591                    parameters: Vec::new(),
592                    precondition: None,
593                    effect: None,
594                },
595                BasicAction {
596                    name: "aact".to_string(),
597                    parameters: Vec::new(),
598                    precondition: None,
599                    effect: None,
600                },
601            ],
602            durative_actions: vec![
603                DurativeAction {
604                    name: "zdur".to_string(),
605                    parameters: Vec::new(),
606                    duration: DurationConstraint::Cmp {
607                        op: CompareOp::Eq,
608                        expr: NumericExpr::Number(1.0),
609                    },
610                    condition: None,
611                    effect: None,
612                },
613                DurativeAction {
614                    name: "adur".to_string(),
615                    parameters: Vec::new(),
616                    duration: DurationConstraint::Cmp {
617                        op: CompareOp::Eq,
618                        expr: NumericExpr::Number(1.0),
619                    },
620                    condition: None,
621                    effect: None,
622                },
623            ],
624            derived_predicates: vec![
625                DerivedPredicate {
626                    predicate: AtomicFormula {
627                        name: "zderived".to_string(),
628                        args: Vec::new(),
629                    },
630                    condition: Condition::And(Vec::new()),
631                },
632                DerivedPredicate {
633                    predicate: AtomicFormula {
634                        name: "aderived".to_string(),
635                        args: Vec::new(),
636                    },
637                    condition: Condition::And(Vec::new()),
638                },
639            ],
640        };
641
642        domain.sort_alphabetically();
643
644        assert_eq!(domain.types[0].items, ["a", "z"]);
645        assert_eq!(domain.constants[0].items, ["c1", "c2"]);
646        assert_eq!(domain.predicates[0].name, "apred");
647        assert_eq!(domain.functions[0].name, "afunc");
648        assert_eq!(domain.actions[0].name, "aact");
649        assert_eq!(domain.durative_actions[0].name, "adur");
650        assert_eq!(domain.derived_predicates[0].predicate.name, "aderived");
651    }
652
653    #[test]
654    fn problem_sort_handles_zero_arity_predicates_and_variable_terms() {
655        let mut problem = Problem {
656            name: "p".to_string(),
657            domain_name: "d".to_string(),
658            requirements: Vec::new(),
659            objects: Vec::new(),
660            init: vec![
661                InitElement::NumericAssignment(
662                    FunctionTerm {
663                        name: "cost".to_string(),
664                        args: vec![Term::Variable("?x".to_string())],
665                    },
666                    1.0,
667                ),
668                InitElement::Predicate(AtomicFormula {
669                    name: "ready".to_string(),
670                    args: Vec::new(),
671                }),
672            ],
673            goal: Condition::And(Vec::new()),
674            metric: None,
675            constraints: None,
676        };
677
678        problem.sort_alphabetically();
679        assert!(matches!(problem.init[0], InitElement::Predicate(_)));
680        assert!(matches!(
681            problem.init[1],
682            InitElement::NumericAssignment(_, _)
683        ));
684    }
685}
jia_parse/ast.rs

jia_parse/
ast.rs
