pddl_rs/
compiler.rs

1use std::{collections::HashMap, ops::Range, slice::Iter};
2
3mod maps;
4use enumset::{EnumSet, EnumSetType};
5mod passes;
6
7// optimization mods
8pub mod action_graph;
9mod inertia;
10
11pub use crate::parser::{
12    ast::{name::Name, *},
13    *,
14};
15use crate::{Error, ErrorKind};
16
17use self::{
18    action_graph::ActionGraph,
19    maps::{map_objects, validate_problem},
20    passes::Compiler,
21};
22
23pub type PredicateUsize = u16;
24pub type ASTActionUsize = u16;
25pub type CompiledActionUsize = u32;
26pub type StateUsize = u16;
27pub type IntValue = i64;
28
29/// Primitive bytecode needed to check action preconditions and apply effects to a "state"(memory).
30#[derive(Debug, PartialEq, Clone, Copy)]
31pub enum Instruction {
32    ReadState(StateUsize),
33    SetState(StateUsize),
34    ReadFunction(StateUsize),
35    SetFunction(StateUsize),
36    And(PredicateUsize),
37    Not,
38    Or,
39    Add,
40    Sub,
41    /// Push immediate
42    Push(IntValue),
43}
44
45/// [`Instruction`] interpreter has stack of this type to help safety of different storage types.
46enum Value {
47    Bool(bool),
48    Int(IntValue),
49}
50
51impl Default for Value {
52    fn default() -> Self {
53        Self::Bool(false)
54    }
55}
56
57impl Value {
58    pub fn unwrap_bool(&self) -> bool {
59        match self {
60            Self::Bool(b) => *b,
61            _ => panic!("Expected bool stack item."),
62        }
63    }
64    pub fn unwrap_int(&self) -> IntValue {
65        match self {
66            Self::Int(i) => *i,
67            _ => panic!("Expected int stack item."),
68        }
69    }
70}
71
72/// Helper trait to easier manage `Vec<Instruction>` fields of actions.
73pub trait Runnable {
74    fn run(self, state: &[bool], functions: &[IntValue]) -> bool;
75    fn run_mut(self, state: &mut [bool], functions: &mut [IntValue]);
76    fn state_miss_count(self, state: &[bool]) -> IntValue;
77    fn disasm(self) -> String;
78    fn decomp(self, memory_map: &Vec<AtomicFormula<Name>>) -> String;
79}
80
81impl Runnable for &[Instruction] {
82    fn run(self, state: &[bool], _: &[IntValue]) -> bool {
83        let mut stack = Vec::<Value>::with_capacity(512);
84        for instruction in self {
85            match instruction {
86                Instruction::ReadState(addr) => stack.push(Value::Bool(state[*addr as usize])),
87                Instruction::SetState(_) => panic!("Instructions try to chane immutable state."),
88                Instruction::ReadFunction(_) => todo!(),
89                Instruction::SetFunction(_) => todo!(),
90                Instruction::And(count) => {
91                    let mut result = true;
92                    let mut count = *count;
93                    while count > 0 {
94                        result &= stack.pop().unwrap().unwrap_bool();
95                        count -= 1;
96                    }
97                    stack.push(Value::Bool(result));
98                }
99                Instruction::Not => {
100                    if let Some(v) = stack.pop() {
101                        stack.push(Value::Bool(!v.unwrap_bool()));
102                    } else {
103                        stack.push(Value::Bool(false))
104                    }
105                }
106                Instruction::Or => todo!(),
107                Instruction::Add => todo!(),
108                Instruction::Sub => todo!(),
109                Instruction::Push(n) => stack.push(Value::Int(*n)),
110            }
111        }
112        stack.pop().unwrap_or_default().unwrap_bool()
113    }
114
115    fn run_mut(self, state: &mut [bool], functions: &mut [i64]) {
116        let mut stack = Vec::<Value>::with_capacity(512);
117        for instruction in self {
118            match instruction {
119                Instruction::SetState(addr) => {
120                    if let Some(v) = stack.pop() {
121                        state[*addr as usize] = v.unwrap_bool()
122                    } else {
123                        state[*addr as usize] = true
124                    }
125                }
126                Instruction::ReadState(addr) => stack.push(Value::Bool(state[*addr as usize])),
127                Instruction::ReadFunction(addr) => {
128                    stack.push(Value::Int(functions[*addr as usize]))
129                } // todo
130                Instruction::SetFunction(addr) => {
131                    functions[*addr as usize] = stack.pop().unwrap().unwrap_int();
132                } // todo
133                Instruction::And(count) => {
134                    let mut result = true;
135                    let mut count = *count;
136                    while count > 0 {
137                        result &= stack.pop().unwrap().unwrap_bool();
138                        count -= 1;
139                    }
140                    stack.push(Value::Bool(result));
141                }
142                Instruction::Not => {
143                    if let Some(v) = stack.pop() {
144                        stack.push(Value::Bool(!v.unwrap_bool()));
145                    } else {
146                        stack.push(Value::Bool(false))
147                    }
148                }
149                Instruction::Or => todo!(),
150                Instruction::Add => {
151                    let s = stack.pop().unwrap().unwrap_int() + stack.pop().unwrap().unwrap_int();
152                    stack.push(Value::Int(s));
153                }
154                Instruction::Sub => todo!(),
155                Instruction::Push(n) => stack.push(Value::Int(*n)),
156            }
157        }
158    }
159
160    fn state_miss_count(self, state: &[bool]) -> i64 {
161        let mut stack = Vec::<Value>::with_capacity(512);
162        let mut state_miss_count = 0;
163        for instruction in self {
164            match instruction {
165                Instruction::ReadState(addr) => stack.push(Value::Bool(state[*addr as usize])),
166                Instruction::SetState(_) => todo!(),
167                Instruction::ReadFunction(_) => todo!(),
168                Instruction::SetFunction(_) => todo!(),
169                Instruction::And(count) => {
170                    let mut result = true;
171                    let mut count = *count;
172                    while count > 0 {
173                        let sv = stack.pop().unwrap().unwrap_bool();
174                        if !sv {
175                            state_miss_count += 1
176                        }
177                        result &= sv;
178                        count -= 1;
179                    }
180                    stack.push(Value::Bool(result));
181                }
182                Instruction::Not => {
183                    let s = !stack.pop().unwrap().unwrap_bool();
184                    stack.push(Value::Bool(s));
185                }
186                Instruction::Or => todo!(),
187                Instruction::Add => todo!(),
188                Instruction::Sub => todo!(),
189                Instruction::Push(_) => todo!(),
190            }
191        }
192        if state_miss_count == 0 && !stack.pop().unwrap_or_default().unwrap_bool() {
193            state_miss_count += 1;
194        }
195        state_miss_count
196    }
197
198    fn disasm(self) -> String {
199        let mut result = String::with_capacity(self.len() * 6);
200        for instruction in self {
201            if result.len() > 0 {
202                result.push_str(", ");
203            }
204            match instruction {
205                Instruction::ReadState(addr) => result.push_str(&format!("RS({})", *addr)),
206                Instruction::SetState(addr) => result.push_str(&format!("WS({})", *addr)),
207                Instruction::ReadFunction(addr) => result.push_str(&format!("RF({})", *addr)),
208                Instruction::SetFunction(addr) => result.push_str(&format!("WF({})", *addr)),
209                Instruction::And(count) => result.push_str(&format!("AND_{}", *count)),
210                Instruction::Not => result.push_str("NOT"),
211                Instruction::Or => result.push_str("OR"),
212                Instruction::Add => result.push_str("ADD"),
213                Instruction::Sub => result.push_str("SUB"),
214                Instruction::Push(value) => result.push_str(&format!("PUSH({})", *value)),
215            }
216        }
217        result
218    }
219
220    fn decomp(self, memory_map: &Vec<AtomicFormula<Name>>) -> String {
221        let mut result = String::with_capacity(self.len() * 6);
222        for instruction in self {
223            if result.len() > 0 {
224                result.push_str(", ");
225            }
226            match instruction {
227                Instruction::ReadState(addr) => {
228                    result.push_str(&format!("RS({})", memory_map[*addr as usize]))
229                }
230                Instruction::SetState(addr) => {
231                    result.push_str(&format!("WS({})", memory_map[*addr as usize]))
232                }
233                Instruction::ReadFunction(addr) => result.push_str(&format!("RF({})", *addr)),
234                Instruction::SetFunction(addr) => result.push_str(&format!("WF({})", *addr)),
235                Instruction::And(count) => result.push_str(&format!("AND_{}", *count)),
236                Instruction::Not => result.push_str("NOT"),
237                Instruction::Or => result.push_str("OR"),
238                Instruction::Add => result.push_str("ADD"),
239                Instruction::Sub => result.push_str("SUB"),
240                Instruction::Push(value) => result.push_str(&format!("PUSH({})", *value)),
241            }
242        }
243        result
244    }
245}
246
247/// Flatenned problem ready for solving
248/// All instrutions use shared memory offsets
249/// no larger than `self.memory_size`
250#[derive(Debug, PartialEq)]
251pub struct CompiledProblem<'src> {
252    /// How many bits needed to fully represent this problem's state
253    /// (Actual memory used depends on type used to represent state.
254    /// A Vec<bool> will use `memory_size` bytes.)
255    pub memory_size: StateUsize,
256    /// Out of `memory_size` memory used, `constants_size` will never change during the search.
257    pub constants_size: StateUsize,
258    /// All compiled actions for this problem. Each domain action compiles into
259    /// multiple [`CompiledAction`]s due to object permutations for various predicates and types.
260    pub actions: Vec<CompiledAction>,
261    /// Mapping of domain action index to a range of compiled actions representing those actions for all used problem objects
262    pub domain_action_ranges: Vec<Range<CompiledActionUsize>>,
263    /// Executable bytecode to set initial conditions
264    pub init: Vec<Instruction>,
265    /// Executable bytecode to check if the goal is met
266    pub goal: Vec<Instruction>,
267    /// Priority list of compiled actions to try
268    pub action_graph: ActionGraph<'src>,
269}
270
271/// Flatenned representation of Actions inside [`CompiledProblem`]s
272/// All instruction offsets point to shared memory
273#[derive(Debug, PartialEq)]
274pub struct CompiledAction {
275    /// Offset into [`Domain`].actions vector pointing to source of this action,
276    /// in case you need to display a message pointing to that PDDL code location).
277    pub domain_action_idx: ASTActionUsize,
278    /// Exact object arguments bound to this action. PDDL actions use types to permutate themselves
279    /// over various objects. CompiledActions are bound to exact objcts. First u16 is the offset in
280    /// problem.objects list. Second u16 is the offset in that list's variables.
281    pub args: Vec<(PredicateUsize, PredicateUsize)>,
282    /// Executable bytecode to check if action's preconditions are met.
283    pub precondition: Vec<Instruction>,
284    /// Executable bytecode to apply action effects.
285    pub effect: Vec<Instruction>,
286}
287
288impl CompiledAction {
289    pub fn new() -> Self {
290        Self {
291            domain_action_idx: 0,
292            args: Vec::new(),
293            precondition: Vec::new(),
294            effect: Vec::new(),
295        }
296    }
297}
298
299/// Enumeration of various optimizations implemented in the compiler
300/// to allow for automatic swithching of them on and off.
301#[derive(EnumSetType, Debug)]
302pub enum Optimization {
303    // /// Following the Koehler, Jana, and Jörg Hoffmann. "On the Instantiation of ADL Operators Involving Arbitrary First-Order Formulas." PuK. 2000. [paper](https://www.researchgate.net/profile/Jana-Koehler-2/publication/220916196_On_the_Instantiation_of_ADL_Operators_Involving_Arbitrary_First-Order_Formulas/links/53f5c12c0cf2fceacc6f65e0/On-the-Instantiation-of-ADL-Operators-Involving-Arbitrary-First-Order-Formulas.pdf),
304    // /// Inertia allows us to start pruning unused states, actions, and instatiate basic action-graphs allowing us to skip many dead-end states.
305    // Inertia,
306}
307
308impl Optimization {
309    pub const NONE: EnumSet<Self> = EnumSet::EMPTY;
310    pub const ALL: EnumSet<Self> = EnumSet::ALL;
311}
312
313/// Compile and optimize parsed [`Domain`] and [`Problem`] structures into a compiled problem ready for using in search methods.
314/// Load them from a file using [`parse_domain`] and [`parse_problem`] functions.
315pub fn compile_problem<'src, 'ast>(
316    domain: &'ast Domain<'src>,
317    problem: &'ast Problem<'src>,
318) -> Result<CompiledProblem<'src>, Vec<Error>>
319where
320    'ast: 'src,
321{
322    validate_problem(domain, problem)?;
323    let maps = map_objects(domain, problem)?;
324    let mut compiler = Compiler::new(domain, problem, maps);
325    compiler.compile()
326}
327
328/// Given a list of types, use a type to object map and generate all possible
329/// permutations of the objects fitting the list.
330///
331/// # Arguments
332/// * `type_to_objects` - a map of type names to vector of all world objects of that type.
333/// * `list` - the argument list that needs to be populated with world objects.
334/// * `f` - closure that gets all permutations of objects populated the `list` in a form of a slice
335///     mapping `list`'s items to world object indexes - `&[(ListItemName, (row, col))]`
336fn for_all_type_object_permutations<'src, F, O>(
337    type_to_objects: &HashMap<&'src str, Vec<(PredicateUsize, PredicateUsize)>>,
338    list: &[List<'src>],
339    mut f: F,
340) -> Result<Vec<O>, Error>
341where
342    F: FnMut(&[(Name<'src>, (PredicateUsize, PredicateUsize))]) -> Result<Option<O>, Error>,
343{
344    use ErrorKind::UndefinedType;
345
346    fn _has_collition<'parent, 'src>(
347        args: &[(Name<'src>, (PredicateUsize, PredicateUsize))],
348        iterators: &[(&'src str, Iter<'parent, (PredicateUsize, PredicateUsize)>)],
349    ) -> bool {
350        for i in 0..iterators.len() {
351            for j in 0..iterators.len() {
352                if args[i].1 .1 == args[j].1 .1 && i != j && iterators[i].0 == iterators[j].0 {
353                    return true;
354                }
355            }
356        }
357        false
358    }
359    /// Call the next iterator at the right position.
360    /// If you think about converting binary to decimal:
361    /// Position == 0 is the least significant iterator
362    /// Position == iterators.len()-1 is the most significant iterator.
363    /// Except binary bit can only be 1 or 0, and our iterator bits
364    /// can go for however many objects of that type there are.
365    /// # Arguments:
366    /// * `type_to_objects` - map of type names to vector of world objects of that type
367    /// * `iterators` - iterators over object vectors in `type_to_objects` map.
368    /// * `args` - "output" vector that's populated by world object permutations each
369    /// time this function is called.
370    /// # Return:
371    /// Returns false when it's impossible to iterate more, true when we can keep going.
372    fn _args_iter<'parent, 'src>(
373        type_to_objects: &'parent HashMap<&'src str, Vec<(PredicateUsize, PredicateUsize)>>,
374        iterators: &mut [(&'src str, Iter<'parent, (PredicateUsize, PredicateUsize)>)],
375        args: &mut [(Name<'src>, (PredicateUsize, PredicateUsize))],
376        pos: usize,
377    ) -> bool {
378        if let Some(arg) = iterators[pos].1.next() {
379            args[pos].1 = *arg;
380            if pos == 0 && _has_collition(args, iterators) {
381                _args_iter(type_to_objects, iterators, args, pos)
382            } else {
383                true
384            }
385            // _no_collisions(type_to_objects, args, iterators, pos)
386        } else if pos + 1 < iterators.len() {
387            let kind = iterators[pos].0;
388            if let Some(vec) = type_to_objects.get(kind) {
389                iterators[pos].1 = vec.iter();
390                if let Some(arg) = iterators[pos].1.next() {
391                    args[pos].1 = *arg;
392                }
393            }
394            let r = _args_iter(type_to_objects, iterators, args, pos + 1);
395            if r && pos == 0 && _has_collition(args, iterators) {
396                _args_iter(type_to_objects, iterators, args, pos)
397            } else {
398                r
399            }
400        } else {
401            // We're done permutating
402            false
403        }
404    }
405
406    let mut iterators = Vec::new();
407    let mut args = Vec::new();
408    // We need to create `objects_vec.len()`` many args - one per object of this type.
409    // First, create an iterator per argument type
410    for List { items, kind } in list {
411        match kind {
412            Type::Exact(kind) => {
413                if let Some(objects_vec) = type_to_objects.get(kind.1) {
414                    for item in items {
415                        iterators.push((kind.1, objects_vec.iter()));
416                        if let Some(next) = iterators.last_mut().unwrap().1.next() {
417                            args.push((*item, *next));
418                        } else {
419                            // Not enough objects to populate this list
420                            todo!()
421                        }
422                    }
423                } else {
424                    return Err(Error {
425                        // input: None,
426                        kind: UndefinedType,
427                        chain: None,
428                        span: kind.0,
429                    });
430                }
431            }
432            Type::None => {
433                let objects_vec = type_to_objects.get("object").unwrap();
434                for item in items {
435                    iterators.push(("object", objects_vec.iter()));
436                    if let Some(next) = iterators.last_mut().unwrap().1.next() {
437                        args.push((*item, *next));
438                    } else {
439                        // Not enough objects to populate this list
440                        todo!()
441                    }
442                }
443            }
444            Type::Either(_) => todo!(),
445        }
446    }
447    // Itereate until the most significant iterator is done, calling closure over populated args
448    let r = if _has_collition(&args, &iterators) {
449        _args_iter(
450            type_to_objects,
451            iterators.as_mut_slice(),
452            args.as_mut_slice(),
453            0,
454        )
455    } else {
456        true
457    };
458    let mut result = if let Some(v) = f(args.as_slice())? {
459        vec![v]
460    } else {
461        Vec::new()
462    };
463
464    if !r {
465        return Ok(result);
466    }
467    while _args_iter(
468        type_to_objects,
469        iterators.as_mut_slice(),
470        args.as_mut_slice(),
471        0,
472    ) {
473        if let Some(v) = f(args.as_slice())? {
474            result.push(v);
475        }
476    }
477    Ok(result)
478}
479
480#[cfg(test)]
481pub mod tests {
482    use lazy_static::lazy_static;
483
484    use crate::{
485        compiler::{CompiledAction, Instruction},
486        Sources,
487    };
488
489    use super::*;
490
491    pub const TINY_DOMAIN_SRC: &str = "(define (domain unit-test)
492    (:predicates (a ?one) (b ?one ?two))
493    (:action aOne :parameters(?one ?two) 
494        :precondition(and (a ?one) (b ?one ?two) (a ?two))
495        :effect (and (not (a ?one)) (not (a ?two)))
496    ))";
497    pub const TINY_PROBLEM_SRC: &str = "(define (problem unit-test)
498    (:domain unit-test)
499    (:objects a b c)
500    (:init (a a) (a b) (b a b))
501    (:goal (not (a a)))
502    )";
503
504    lazy_static! {
505        pub static ref TINY_SOURCES: Sources = Sources {
506            domain_path: "stdin_domain".into(),
507            problem_path: "stdin_problem".into(),
508            domain_ad: ariadne::Source::from(TINY_DOMAIN_SRC),
509            problem_ad: ariadne::Source::from(TINY_PROBLEM_SRC),
510            domain_src: TINY_DOMAIN_SRC.into(),
511            problem_src: TINY_PROBLEM_SRC.into()
512        };
513    }
514
515    #[test]
516    fn test_permutations() {
517        let type_to_objects = HashMap::from([("object", vec![(0, 0), (0, 1), (0, 2), (0, 3)])]);
518        let list = vec![List {
519            items: vec![
520                Name::new(0..0, "var1"),
521                Name::new(0..0, "var2"),
522                Name::new(0..0, "var3"),
523            ],
524            kind: Type::None,
525        }];
526        let result = for_all_type_object_permutations(&type_to_objects, &list, |args| {
527            assert_eq!(args.len(), 3);
528            Ok(Some((args[0].1 .1, args[1].1 .1, args[2].1 .1)))
529        })
530        .unwrap();
531        assert_eq!(
532            result,
533            vec![
534                // (0, 0, 0),
535                // (1, 0, 0),
536                // (2, 0, 0),
537                // (3, 0, 0),
538                // (0, 1, 0),
539                // (1, 1, 0),
540                (2, 1, 0),
541                (3, 1, 0),
542                // (0, 2, 0),
543                (1, 2, 0),
544                // (2, 2, 0),
545                (3, 2, 0),
546                // (0, 3, 0),
547                (1, 3, 0),
548                (2, 3, 0),
549                // (3, 3, 0),
550                // (0, 0, 1),
551                // (1, 0, 1),
552                (2, 0, 1),
553                (3, 0, 1),
554                // (0, 1, 1),
555                // (1, 1, 1),
556                // (2, 1, 1),
557                // (3, 1, 1),
558                (0, 2, 1),
559                // (1, 2, 1),
560                // (2, 2, 1),
561                (3, 2, 1),
562                (0, 3, 1),
563                // (1, 3, 1),
564                (2, 3, 1),
565                // (3, 3, 1),
566                // (0, 0, 2),
567                (1, 0, 2),
568                // (2, 0, 2),
569                (3, 0, 2),
570                (0, 1, 2),
571                // (1, 1, 2),
572                // (2, 1, 2),
573                (3, 1, 2),
574                // (0, 2, 2),
575                // (1, 2, 2),
576                // (2, 2, 2),
577                // (3, 2, 2),
578                (0, 3, 2),
579                (1, 3, 2),
580                // (2, 3, 2),
581                // (3, 3, 2),
582                // (0, 0, 3),
583                (1, 0, 3),
584                (2, 0, 3),
585                // (3, 0, 3),
586                (0, 1, 3),
587                // (1, 1, 3),
588                (2, 1, 3),
589                // (3, 1, 3),
590                (0, 2, 3),
591                (1, 2, 3),
592                // (2, 2, 3),
593                // (3, 2, 3),
594                // (0, 3, 3),
595                // (1, 3, 3),
596                // (2, 3, 3),
597                // (3, 3, 3),
598            ]
599        );
600    }
601
602    #[test]
603    #[ignore = "New compiler has undeterministic memory mapping. This test fails half-the time."]
604    fn test_action() {
605        use Instruction::*;
606        let (domain, problem) = TINY_SOURCES.parse();
607        let problem = TINY_SOURCES.compile(&domain, &problem);
608        assert_eq!(problem.memory_size, 2);
609        assert_eq!(problem.init, vec![SetState(0), SetState(1)]);
610        assert_eq!(problem.goal, vec![ReadState(0), Not]);
611        assert_eq!(problem.actions.len(), 1);
612        assert_eq!(
613            problem.actions[0],
614            CompiledAction {
615                domain_action_idx: 0,
616                args: vec![(0, 0), (0, 1)], // b a
617                precondition: vec![ReadState(1), ReadState(0), And(2)],
618                effect: vec![Not, SetState(1), Not, SetState(1)],
619                // action_graph: ActionGraph { priority: vec![] },
620            }
621        );
622    }
623
624    #[test]
625    fn test_basic_execution() {
626        use Instruction::*;
627        let instructions = vec![ReadState(0), Not, ReadState(1), And(2)];
628        let mut state = vec![false, true];
629        let mut functions = vec![0];
630        assert_eq!(instructions.run(&state, &functions), true);
631        let instructions = vec![ReadState(0), ReadState(1), And(2)];
632        assert_eq!(instructions.run(&state, &functions), false);
633        let instructions = vec![ReadState(0), SetState(1)];
634        instructions.run_mut(&mut state, &mut functions);
635        assert_eq!(state[0], false);
636        assert_eq!(state[1], false);
637    }
638}
pddl_rs/compiler.rs

pddl_rs/
compiler.rs
