hyperon/space/grounding/
mod.rs

1//! Atomspace implementation with in-memory atom storage
2
3use hyperon_atom::{matcher::BindingsSet, *};
4use hyperon_common::FlexRef;
5#[cfg(test)]
6use hyperon_space::DynSpace;
7
8use std::fmt::{Debug, Display};
9use std::collections::HashSet;
10use hyperon_space::{complex_query, index::{AllowDuplication, AtomIndex, DuplicationStrategy, ALLOW_DUPLICATION}, Space, SpaceCommon, SpaceEvent, SpaceMut, SpaceVisitor};
11
12// Grounding space
13
14/// In-memory space which can contain grounded atoms.
15// TODO: Clone is required by C API
16#[derive(Clone)]
17pub struct GroundingSpace<D: DuplicationStrategy = AllowDuplication> {
18    index: AtomIndex<D>,
19    common: SpaceCommon,
20    name: Option<String>,
21}
22
23impl GroundingSpace {
24    /// Constructs new empty space.
25    pub fn new() -> Self {
26        Self::with_strategy(ALLOW_DUPLICATION)
27    }
28
29    /// Constructs space from vector of atoms.
30    pub fn from_vec(atoms: Vec<Atom>) -> Self {
31        let mut index = AtomIndex::with_strategy(ALLOW_DUPLICATION);
32        for atom in atoms {
33            index.insert(atom);
34        }
35        Self{
36            index,
37            common: SpaceCommon::default(),
38            name: None,
39        }
40    }
41}
42
43impl<D: DuplicationStrategy> GroundingSpace<D> {
44    /// Constructs new empty space using duplication strategy.
45    pub fn with_strategy(strategy: D) -> Self {
46        Self {
47            index: AtomIndex::with_strategy(strategy),
48            common: SpaceCommon::default(),
49            name: None,
50        }
51    }
52
53    /// Adds `atom` into space.
54    ///
55    /// # Examples
56    ///
57    /// ```
58    /// use hyperon_atom::sym;
59    /// use hyperon_atom::matcher::BindingsSet;
60    /// use hyperon::space::grounding::GroundingSpace;
61    ///
62    /// let mut space = GroundingSpace::from_vec(vec![sym!("A")]);
63    ///
64    /// space.add(sym!("B"));
65    ///
66    /// assert_eq!(space.query(&sym!("A")), BindingsSet::single());
67    /// assert_eq!(space.query(&sym!("B")), BindingsSet::single());
68    /// assert_eq!(space.query(&sym!("C")), BindingsSet::empty());
69    /// ```
70    pub fn add(&mut self, atom: Atom) {
71        log::debug!("GroundingSpace::add: {}, atom: {}", self, atom);
72        self.index.insert(atom.clone());
73        self.common.notify_all_observers(&SpaceEvent::Add(atom));
74    }
75
76    /// Removes `atom` from space. Returns true if atom was found and removed,
77    /// and false otherwise.
78    ///
79    /// # Examples
80    ///
81    /// ```
82    /// use hyperon_atom::sym;
83    /// use hyperon_atom::matcher::BindingsSet;
84    /// use hyperon::space::grounding::GroundingSpace;
85    ///
86    /// let mut space = GroundingSpace::from_vec(vec![sym!("A")]);
87    ///
88    /// space.remove(&sym!("A"));
89    ///
90    /// assert_eq!(space.query(&sym!("A")), BindingsSet::empty());
91    /// ```
92    pub fn remove(&mut self, atom: &Atom) -> bool {
93        log::debug!("GroundingSpace::remove: {}, atom: {}", self, atom);
94        let is_removed = self.index.remove(atom);
95        if is_removed {
96            self.common.notify_all_observers(&SpaceEvent::Remove(atom.clone()));
97        }
98        is_removed
99    }
100
101    /// Replaces `from` atom to `to` atom inside space. Doesn't add `to` when
102    /// `from` is not found. Returns true if atom was found and replaced, and
103    /// false otherwise.
104    ///
105    /// # Examples
106    ///
107    /// ```
108    /// use hyperon_atom::sym;
109    /// use hyperon_atom::matcher::BindingsSet;
110    /// use hyperon::space::grounding::GroundingSpace;
111    ///
112    /// let mut space = GroundingSpace::from_vec(vec![sym!("A")]);
113    ///
114    /// space.replace(&sym!("A"), sym!("B"));
115    ///
116    /// assert_eq!(space.query(&sym!("A")), BindingsSet::empty());
117    /// assert_eq!(space.query(&sym!("B")), BindingsSet::single());
118    /// ```
119    pub fn replace(&mut self, from: &Atom, to: Atom) -> bool {
120        let is_replaced = self.index.remove(from);
121        if is_replaced {
122            self.index.insert(to.clone());
123            self.common.notify_all_observers(&SpaceEvent::Replace(from.clone(), to));
124        }
125        is_replaced
126    }
127
128    /// Executes `query` on the space and returns variable bindings found.
129    /// Query may include sub-queries glued by [COMMA_SYMBOL] symbol.
130    /// Each [Bindings](matcher::Bindings) instance in the returned [BindingsSet]
131    /// represents single result.
132    ///
133    /// # Examples
134    ///
135    /// ```
136    /// use hyperon_atom::{expr, bind_set, sym};
137    /// use hyperon_atom::matcher::BindingsSet;
138    /// use hyperon::space::grounding::GroundingSpace;
139    ///
140    /// let space = GroundingSpace::from_vec(vec![expr!("A" "B"), expr!("B" "C")]);
141    /// let query = expr!("," ("A" x) (x "C"));
142    ///
143    /// let result = space.query(&query);
144    ///
145    /// assert_eq!(result, bind_set![{x: sym!("B")}]);
146    /// ```
147    pub fn query(&self, query: &Atom) -> BindingsSet {
148        complex_query(query, |query| self.single_query(query))
149    }
150
151    /// Executes simple `query` without sub-queries on the space.
152    fn single_query(&self, query: &Atom) -> BindingsSet {
153        log::debug!("GroundingSpace::single_query: {} query: {}", self, query);
154        let mut result = BindingsSet::empty();
155        let query_vars: HashSet<&VariableAtom> = query.iter().filter_type::<&VariableAtom>().collect();
156        for bindings in self.index.query(query) {
157            let bindings = bindings.narrow_vars(&query_vars);
158            log::trace!("single_query: push result: {}", bindings);
159            result.push(bindings);
160        }
161        log::debug!("GroundinSpace::single_query: {} result: {}", self, result);
162        result
163    }
164
165    /// Sets the name property for the `GroundingSpace` which can be useful for debugging
166    pub fn set_name(&mut self, name: String) {
167        self.name = Some(name);
168    }
169
170    /// Returns the name property for the `GroundingSpace`, if one has been set
171    pub fn name(&self) -> Option<&str> {
172        self.name.as_ref().map(|s| s.as_str())
173    }
174
175    #[cfg(test)]
176    fn into_vec(&self) -> Vec<Atom> {
177        self.index.iter().map(|a| a.into_owned()).collect()
178    }
179}
180
181impl Space for GroundingSpace {
182    fn common(&self) -> FlexRef<'_, SpaceCommon> {
183        FlexRef::from_simple(&self.common)
184    }
185    fn query(&self, query: &Atom) -> BindingsSet {
186        GroundingSpace::query(self, query)
187    }
188    fn atom_count(&self) -> Option<usize> {
189        Some(self.index.iter().count())
190    }
191    fn visit(&self, v: &mut dyn SpaceVisitor) -> Result<(), ()> {
192       Ok(self.index.iter().for_each(|atom| v.accept(atom)))
193    }
194    fn as_any(&self) -> &dyn std::any::Any {
195        self
196    }
197}
198
199impl SpaceMut for GroundingSpace {
200    fn add(&mut self, atom: Atom) {
201        GroundingSpace::add(self, atom)
202    }
203    fn remove(&mut self, atom: &Atom) -> bool {
204        GroundingSpace::remove(self, atom)
205    }
206    fn replace(&mut self, from: &Atom, to: Atom) -> bool {
207        GroundingSpace::replace(self, from, to)
208    }
209    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
210        self
211    }
212}
213
214impl<D: DuplicationStrategy> Debug for GroundingSpace<D> {
215    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
216        match &self.name {
217            Some(name) => write!(f, "GroundingSpace-{name} ({self:p})"),
218            None => write!(f, "GroundingSpace-{self:p}")
219        }
220    }
221}
222
223impl<D: DuplicationStrategy> Display for GroundingSpace<D> {
224    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
225        match &self.name {
226            Some(name) => write!(f, "GroundingSpace-{name}"),
227            None => write!(f, "GroundingSpace-{self:p}")
228        }
229    }
230}
231
232#[cfg(test)]
233use crate::metta::text::*;
234
235#[cfg(test)]
236pub(crate) fn metta_space(text: &str) -> DynSpace {
237    let mut space = GroundingSpace::new();
238    let mut parser = SExprParser::new(text);
239    while let Some(atom) = parser.parse(&Tokenizer::new()).unwrap() {
240        space.add(atom);
241    }
242    space.into()
243}
244
245#[cfg(test)]
246mod test {
247    use std::borrow::Cow;
248
249    use super::*;
250    use hyperon_atom::matcher::*;
251    use hyperon_common::assert_eq_no_order;
252    use hyperon_space::SpaceObserver;
253
254    struct SpaceEventCollector {
255        events: Vec<SpaceEvent>,
256    }
257
258    impl SpaceEventCollector {
259        fn new() -> Self {
260            Self{ events: Vec::new() }
261        }
262    }
263
264    impl SpaceObserver for SpaceEventCollector {
265        fn notify(&mut self, event: &SpaceEvent) {
266            self.events.push(event.clone());
267        }
268    }
269
270    #[test]
271    fn add_atom() {
272        let mut space = GroundingSpace::new();
273        let observer = space.common.register_observer(SpaceEventCollector::new());
274
275        space.add(expr!("a"));
276        space.add(expr!("b"));
277        space.add(expr!("c"));
278
279        assert_eq_no_order!(space.into_vec(), vec![expr!("a"), expr!("b"), expr!("c")]);
280        assert_eq!(observer.borrow().events, vec![SpaceEvent::Add(sym!("a")),
281            SpaceEvent::Add(sym!("b")), SpaceEvent::Add(sym!("c"))]);
282    }
283
284    #[test]
285    fn remove_atom() {
286        let mut space = GroundingSpace::new();
287        let observer = space.common.register_observer(SpaceEventCollector::new());
288
289        space.add(expr!("a"));
290        space.add(expr!("b"));
291        space.add(expr!("c"));
292        assert_eq!(space.remove(&expr!("b")), true);
293
294        assert_eq_no_order!(space.into_vec(), vec![expr!("a"), expr!("c")]);
295        assert_eq!(observer.borrow().events, vec![SpaceEvent::Add(sym!("a")),
296            SpaceEvent::Add(sym!("b")), SpaceEvent::Add(sym!("c")),
297            SpaceEvent::Remove(sym!("b"))]);
298    }
299
300    #[test]
301    fn remove_duplicated_atom() {
302        let mut space = GroundingSpace::new();
303        let observer = space.common.register_observer(SpaceEventCollector::new());
304
305        space.add(expr!("a"));
306        space.add(expr!("a"));
307        space.add(expr!("a"));
308        assert_eq!(space.remove(&expr!("a")), true);
309
310        assert_eq_no_order!(space.into_vec(), vec![expr!("a"), expr!("a")]);
311        assert_eq!(observer.borrow().events, vec![SpaceEvent::Add(sym!("a")),
312            SpaceEvent::Add(sym!("a")), SpaceEvent::Add(sym!("a")),
313            SpaceEvent::Remove(sym!("a"))]);
314    }
315
316    #[test]
317    fn remove_atom_not_found() {
318        let mut space = GroundingSpace::new();
319        let observer = space.common.register_observer(SpaceEventCollector::new());
320
321        space.add(expr!("a"));
322        assert_eq!(space.remove(&expr!("b")), false);
323
324        assert_eq_no_order!(space.into_vec(), vec![expr!("a")]);
325        assert_eq!(observer.borrow().events, vec![SpaceEvent::Add(sym!("a"))]);
326    }
327
328    #[test]
329    fn replace_atom() {
330        let mut space = GroundingSpace::new();
331        let observer = space.common.register_observer(SpaceEventCollector::new());
332
333        space.add(expr!("a"));
334        space.add(expr!("b"));
335        space.add(expr!("c"));
336        assert_eq!(space.replace(&expr!("b"), expr!("d")), true);
337
338        assert_eq_no_order!(space.into_vec(), vec![expr!("a"), expr!("d"), expr!("c")]);
339        assert_eq!(observer.borrow().events, vec![SpaceEvent::Add(sym!("a")),
340            SpaceEvent::Add(sym!("b")), SpaceEvent::Add(sym!("c")),
341            SpaceEvent::Replace(sym!("b"), sym!("d"))]);
342    }
343
344    #[test]
345    fn replace_atom_not_found() {
346        let mut space = GroundingSpace::new();
347        let observer = space.common.register_observer(SpaceEventCollector::new());
348
349        space.add(expr!("a"));
350        assert_eq!(space.replace(&expr!("b"), expr!("d")), false);
351
352        assert_eq_no_order!(space.into_vec(), vec![expr!("a")]);
353        assert_eq!(observer.borrow().events, vec![SpaceEvent::Add(sym!("a"))]);
354    }
355
356    #[test]
357    fn remove_replaced_atom() {
358        let mut space = GroundingSpace::new();
359        let observer = space.common.register_observer(SpaceEventCollector::new());
360
361        space.add(expr!("a"));
362        space.replace(&expr!("a"), expr!("b"));
363        assert_eq!(space.remove(&expr!("b")), true);
364
365        assert_eq_no_order!(space.into_vec(), Vec::<Atom>::new());
366        assert_eq!(observer.borrow().events, vec![SpaceEvent::Add(sym!("a")),
367            SpaceEvent::Replace(expr!("a"), expr!("b")),
368            SpaceEvent::Remove(expr!("b"))]);
369    }
370
371    #[test]
372    fn get_atom_after_removed() {
373        let mut space = GroundingSpace::new();
374
375        space.add(Atom::sym("A"));
376        space.add(Atom::sym("B"));
377        space.remove(&Atom::sym("A"));
378
379        assert_eq!(space.query(&Atom::sym("B")), BindingsSet::single());
380    }
381
382    #[test]
383    fn iter_empty() {
384        let space = GroundingSpace::from_vec(vec![]);
385
386        assert_eq!(space.atom_count(), Some(0));
387    }
388
389    #[test]
390    fn iter_after_remove() {
391        let mut space = GroundingSpace::from_vec(vec![expr!("a"), expr!("b"), expr!("c")]);
392        space.remove(&expr!("b"));
393
394        let mut atoms = Vec::new();
395        assert_eq!(Ok(()), space.visit(&mut |atom: Cow<Atom>| atoms.push(atom.into_owned())));
396        assert_eq_no_order!(atoms, vec![expr!("a"), expr!("c")]);
397    }
398
399    #[test]
400    fn mut_cloned_atomspace() {
401        let mut first = GroundingSpace::new();
402        let mut second = first.clone();
403
404        first.add(expr!("b"));
405        second.add(expr!("d"));
406
407        assert_eq_no_order!(first.into_vec(), vec![expr!("b")]);
408        assert_eq_no_order!(second.into_vec(), vec![expr!("d")]);
409    }
410
411    #[test]
412    fn test_match_symbol() {
413        let mut space = GroundingSpace::new();
414        space.add(expr!("foo"));
415        assert_eq!(space.query(&expr!("foo")), BindingsSet::single());
416    }
417
418    #[test]
419    fn test_match_variable() {
420        let mut space = GroundingSpace::new();
421        space.add(expr!("foo"));
422        assert_eq!(space.query(&expr!(x)), bind_set![{x: expr!("foo")}]);
423    }
424
425    #[test]
426    fn test_match_expression() {
427        let mut space = GroundingSpace::new();
428        space.add(expr!("+" "a" ("*" "b" "c")));
429        assert_eq!(space.query(&expr!("+" "a" ("*" "b" "c"))), BindingsSet::single());
430    }
431
432    #[test]
433    fn test_match_expression_with_variables() {
434        let mut space = GroundingSpace::new();
435        space.add(expr!("+" "A" ("*" "B" "C")));
436        assert_eq!(space.query(&expr!("+" a ("*" b c))),
437        bind_set![{a: expr!("A"), b: expr!("B"), c: expr!("C") }]);
438    }
439
440    #[test]
441    fn test_match_different_value_for_variable() {
442        let mut space = GroundingSpace::new();
443        space.add(expr!("+" "A" ("*" "B" "C")));
444        assert_eq!(space.query(&expr!("+" a ("*" a c))), BindingsSet::empty());
445    }
446
447    #[test]
448    fn test_match_query_variable_has_priority() {
449        let mut space = GroundingSpace::new();
450        space.add(expr!("equals" x x));
451
452        let result = space.query(&expr!("equals" y z));
453        assert_eq!(result, bind_set![{ y: expr!(z) }]);
454    }
455
456    #[test]
457    fn test_match_query_variable_via_data_variable() {
458        let mut space = GroundingSpace::new();
459        space.add(expr!(x x));
460        assert_eq!(space.query(&expr!(y (z))), bind_set![{y: expr!((z))}]);
461    }
462
463    #[test]
464    fn test_match_if_then_with_x() {
465        let mut space = GroundingSpace::new();
466        space.add(expr!("=" ("if" "True" then) then));
467        assert_eq!(space.query(&expr!("=" ("if" "True" "42") X)),
468        bind_set![{X: expr!("42")}]);
469    }
470
471    #[test]
472    fn test_match_combined_query() {
473        let mut space = GroundingSpace::new();
474        space.add(expr!("posesses" "Sam" "baloon"));
475        space.add(expr!("likes" "Sam" ("blue" "stuff")));
476        space.add(expr!("has-color" "baloon" "blue"));
477
478        let result = space.query(&expr!("," ("posesses" "Sam" object)
479        ("likes" "Sam" (color "stuff"))
480        ("has-color" object color)));
481        assert_eq!(result, bind_set![{object: expr!("baloon"), color: expr!("blue")}]);
482    }
483
484    #[test]
485    fn test_unify_variables_inside_conjunction_query() {
486        let mut space = GroundingSpace::new();
487        space.add(expr!("lst1" ("Cons" "a1" ("Cons" "b2" "b3"))));
488        space.add(expr!("lst2" ("Cons" "a2" ("Cons" "b3" "b4"))));
489        space.add(expr!("Concat" x1 x2 x3));
490
491        let result = space.subst(
492            &expr!("," ("lst1" l1) ("lst2" l2) ("Concat" l1 "a2" "a3")),
493            &expr!(l1));
494        assert_eq!(result, vec![expr!("Cons" "a1" ("Cons" "b2" "b3"))]);
495    }
496
497    #[test]
498    fn test_type_check_in_query() {
499        let mut space = GroundingSpace::new();
500        space.add(expr!(":" "Human" "Type"));
501        space.add(expr!(":" "Socrates" "Human"));
502        space.add(expr!("Cons" "Socrates" "Nil"));
503
504        let result = space.query(&expr!("," (":" h "Human") ("Cons" h t)));
505        assert_eq!(result, bind_set![{h: expr!("Socrates"), t: expr!("Nil")}]);
506    }
507
508    #[test]
509    fn cleanup_observer() {
510        let mut space = GroundingSpace::new();
511        {
512            let _observer = space.common.register_observer(SpaceEventCollector::new());
513            assert_eq!(space.common.observers.borrow().len(), 1);
514        }
515
516        space.add(expr!("a"));
517
518        assert_eq_no_order!(space.into_vec(), vec![expr!("a")]);
519        assert_eq!(space.common.observers.borrow().len(), 0);
520    }
521
522    #[test]
523    fn complex_query_applying_bindings_to_next_pattern() {
524        let mut space = GroundingSpace::new();
525        space.add(expr!(":=" ("sum" a b) ("+" a b)));
526        space.add(expr!(":=" "a" {4}));
527
528        let result = space.query(&expr!("," (":=" "a" b) (":=" ("sum" {3} b) W)));
529
530        assert_eq!(result.len(), 1);
531        let result = &result[0];
532        assert_eq!(result.resolve(&VariableAtom::new("W")), Some(expr!("+" {3} {4})));
533        assert_eq!(result.resolve(&VariableAtom::new("b")), Some(expr!({4})));
534    }
535
536    #[test]
537    fn complex_query_chain_of_bindings() {
538        let mut space = GroundingSpace::new();
539        space.add(expr!("implies" ("B" x) ("C" x)));
540        space.add(expr!("implies" ("A" x) ("B" x)));
541        space.add(expr!("A" "Sam"));
542
543        let result = space.query(&expr!("," ("implies" ("B" x) z) ("implies" ("A" x) y) ("A" x)));
544        //assert_eq!(result, bind_set![{x: sym!("Sam"), y: expr!("B" x), z: expr!("C" x)}]);
545        assert_eq!(result.len(), 1);
546        let result = result.into_iter().next().unwrap();
547        assert_eq!(result.resolve(&VariableAtom::new("x")), Some(sym!("Sam")));
548        assert_eq!(result.resolve(&VariableAtom::new("y")), Some(expr!("B" "Sam")));
549        assert_eq!(result.resolve(&VariableAtom::new("z")), Some(expr!("C" "Sam")));
550    }
551
552    #[test]
553    fn test_match_results_with_variable_loop() {
554        let space = GroundingSpace::from_vec(vec![
555            expr!("R" a a),
556        ]);
557        let result = space.query(&expr!("R" b ("S" b)));
558        assert_eq!(result, bind_set![]);
559    }
560
561    #[test]
562    fn test_custom_match_with_space() {
563        let space = GroundingSpace::from_vec(vec![
564            expr!("A" {1} x "a"),
565            expr!("B" {1} x "b"),
566            expr!("A" {2} x "c"),
567        ]);
568        let result: BindingsSet = match_atoms(&Atom::gnd(DynSpace::new(space)), &expr!("A" {1} x x)).collect();
569        assert_eq!(result, bind_set![{x: sym!("a")}]);
570    }
571}
hyperon/space/grounding/mod.rs

hyperon/space/grounding/
mod.rs
