Rework subtrees again and update docs

2 files changed, 279 insertions, 20 deletions

diff --git a/src/vm/de.rs b/src/vm/de.rs
index 493b658..8f2aa8d 100644
--- a/src/vm/de.rs
+++ b/src/vm/de.rs
@@ -169,6 +169,7 @@ impl<'pat, 'state, 'de, O: Serialize> Packer<'pat, 'state, O> {
                                 matches: true,
                                 poison: false,
                             };
+                            debug_assert!(!new_frame.ops.is_empty());
                             // we want the "newest" frame last, so it is
                             // easier to unwind back.
                             self.interp.frames.insert(at, new_frame);
@@ -209,12 +210,13 @@ impl<'pat, 'state, 'de, O: Serialize> Packer<'pat, 'state, O> {
                     pack_index -= 1;
                 }
                 if frame.poison {
-                    if has_pack {
-                        packs.remove(pack_index);
-                    }
-                    frame.matches = false;
-                    has_pack = false;
+                    // FIXME should frame.poison always remove the pack?
                     if frame.is_value() {
+                        if has_pack {
+                            packs.remove(pack_index);
+                        }
+                        frame.matches = false;
+                        has_pack = false;
                         frame.poison = false;
                     }
                 }
@@ -260,8 +262,14 @@ impl<'pat, 'state, 'de, O: Serialize> Packer<'pat, 'state, O> {
                                 packs[target_pack].merge_breadth(pack);
                             }
                         } else {
+                            //if frame.poison {
+                            //    target_frame.poison = true;
+                            //}
                             if !optional {
-                                target_frame.poison = true;
+                                self.interp.error.insert({
+                                    MatchError::ValidationError
+                                });
+                                return Err(E::custom("subtree failed"));
                             }
                         }
                         if let Some((0, _)) = target_frame.num_subtrees() {
@@ -864,10 +872,14 @@ where
                 }
             }
         }
+        let mut poison = false;
         for (f, m) in self.frames_mut().iter_active_mut().zip(output_matches) {
-            // FIXME inspect frame.key_subtree() for optional?
-            // what is this even supposed to do again?
             f.matches = m;
+            if !m {
+                if let Some((_, false)) = f.key_subtree() {
+                    poison = true;
+                }
+            }
         }
         let obj = SerdeObject::Map(obj_inner);
         let mut final_packs = self.step_out(output_packs)?;
@@ -880,6 +892,7 @@ where
                 | Some((Type::IgnoredAny, _))
                 | None
                 => {
+                    frame.poison = poison;
                     let matched = std::mem::replace(&mut frame.matches, true);
                     if !matched {
                         final_packs.insert(
@@ -1361,6 +1374,36 @@ mod tests {
     }
 
     #[test]
+    fn test_empty_subtrees() {
+        // tests empty subtrees
+        let consts = crate::parser::parse::<&'static str, &'static str, ()>(
+            ":map()(())",
+            None,
+            None,
+        ).unwrap();
+        dbg!(&consts);
+        let data = r#"{"hello": "world"}"#;
+        let mut der = JsonDeserializer::from_str(data);
+        let mut err = Default::default();
+        let mut frames = Default::default();
+        let interp = Interpreter::new(
+            &consts,
+            &mut err,
+            &mut frames,
+            //&mut output,
+        );
+        let result = Packer::new(
+            interp,
+            MAX_CALLS,
+        ).deserialize(&mut der);
+        let (mut packs, obj) = result.unwrap();
+        assert!(obj.is_none());
+        assert_eq!(packs.len(), 1);
+        let pack = packs.pop().unwrap();
+        assert_eq!(pack.subpacks.len(), 0);
+    }
+
+    #[test]
     fn test_parser_subtrees() {
         // use a parsed pattern with subtrees to test Packer
         // also test a non-self-describing format (postcard)
@@ -1402,15 +1445,165 @@ mod tests {
     }
 
     #[test]
-    fn test_subtree_missing() {
-        // use a parsed pattern that might actually be used in the real world.
+    fn test_parser_subtrees_validation() {
+        // checks that the Packer can validate multiple keys.
+        let consts = crate::parser::parse::<&'static str, &'static str, ()>(
+            ":map(->['name'?]name:str)(->['value'?]value:u32)(->[:str]:?ignored_any)",
+            None,
+            None,
+        ).unwrap();
+        let data = &[
+            0x02, // map length (2)
+            0x04, // string length (4)
+            0x6E, 0x61, 0x6D, 0x65, // b'name'
+            0x01, // string length (1)
+            0x61, // b'a'
+            0x05, // string length (5)
+            0x76, 0x61, 0x6C, 0x75, 0x65, // b'value'
+            0x01, // 1
+        ];
+        let mut der = PostcardDeserializer::from_bytes(data);
+        let mut err = Default::default();
+        let mut frames = Default::default();
+        let interp = Interpreter::new(
+            &consts,
+            &mut err,
+            &mut frames,
+            //&mut output,
+        );
+        let result = Packer::new(
+            interp,
+            MAX_CALLS,
+        ).deserialize(&mut der);
+        let (mut packs, obj) = result.unwrap();
+        assert!(obj.is_none());
+        assert_eq!(packs.len(), 1);
+        let pack = packs.pop().unwrap();
+        assert_eq!(pack.subpacks.len(), 1);
+        assert_eq!(pack.subpacks[0]["name"].1, SerdeObject::Str(From::from("a")));
+        assert_eq!(pack.subpacks[0]["value"].1, SerdeObject::U32(1));
+    }
+
+    #[test]
+    fn test_one_or_more_subtrees_validation() {
+        // checks that the Packer supports OR-like validation semantics
+        let consts = crate::parser::parse::<&'static str, &'static str, ()>(
+            ":map((->['name'?]?name)?(->['value'?]?value)?)(->[:str]:u32)",
+            None,
+            None,
+        ).unwrap();
+        let data = &[
+            0x01, // map length (1)
+            0x04, // string length (4)
+            0x6E, 0x61, 0x6D, 0x65, // b'name'
+            0x01, // 1
+        ];
+        let mut der = PostcardDeserializer::from_bytes(data);
+        let mut err = Default::default();
+        let mut frames = Default::default();
+        let interp = Interpreter::new(
+            &consts,
+            &mut err,
+            &mut frames,
+            //&mut output,
+        );
+        let result = Packer::new(
+            interp,
+            MAX_CALLS,
+        ).deserialize(&mut der);
+        let (mut packs, obj) = result.unwrap();
+        assert!(obj.is_none());
+        assert_eq!(packs.len(), 1);
+        let pack = packs.pop().unwrap();
+        assert_eq!(pack.subpacks.len(), 1);
+        assert_eq!(pack.subpacks[0]["name"].1, SerdeObject::U32(1));
+    }
+
+    #[test]
+    fn test_one_or_more_subtrees_validation_failure() {
+        // checks that the Packer supports OR-like validation semantics
+        // (failure)
+        let consts = crate::parser::parse::<&'static str, &'static str, ()>(
+            ":map((->['name'?]?name)?(->['value'?]?value)?)(->[:str]:u32)",
+            None,
+            None,
+        ).unwrap();
+        let data = &[
+            0x01, // map length (1)
+            0x04, // string length (4)
+            0x6E, 0x65, 0x6D, 0x65, // b'neme'
+            0x01, // 1
+        ];
+        let mut der = PostcardDeserializer::from_bytes(data);
+        let mut err = Default::default();
+        let mut frames = Default::default();
+        let interp = Interpreter::new(
+            &consts,
+            &mut err,
+            &mut frames,
+            //&mut output,
+        );
+        let result = Packer::new(
+            interp,
+            MAX_CALLS,
+        ).deserialize(&mut der);
+        assert!(matches!(err, Some(MatchError::ValidationError)));
+        assert!(result.is_err());
+    }
+
+    // FIXME this should test that the map doesn't contain other keys aside
+    // from the ones requested by the pattern, but this doesn't match existing
+    // datafu semantics at all. we need new syntax for it.
+    //#[test]
+    //fn test_parser_subtrees_no_additional_keys() {
+    //    // use a parsed pattern with subtrees to test Packer
+    //    // also test a non-self-describing format (postcard)
+    //    // also require at least one subtree to match on every iteration.
+    //    // also this checks for validation error
+    //    let consts = crate::parser::parse::<&'static str, &'static str, ()>(
+    //        ":map((->['name'?]name)?(->['value'?]value)?)(->[:str]:u32)",
+    //        None,
+    //        None,
+    //    ).unwrap();
+    //    let data = &[
+    //        0x03, // map length (3)
+    //        0x04, // string length (4)
+    //        0x6E, 0x61, 0x6D, 0x65, // b'name'
+    //        0x01, // 1
+    //        0x05, // string length (5)
+    //        0x76, 0x61, 0x6C, 0x75, 0x65, // b'value'
+    //        0x01, // 1
+    //        0x05, // string length (5)
+    //        0x76, 0x65, 0x6C, 0x75, 0x65, // b'velue'
+    //        0x01, // 1
+    //    ];
+    //    let mut der = PostcardDeserializer::from_bytes(data);
+    //    let mut err = Default::default();
+    //    let mut frames = Default::default();
+    //    let interp = Interpreter::new(
+    //        &consts,
+    //        &mut err,
+    //        &mut frames,
+    //        //&mut output,
+    //    );
+    //    let result = Packer::new(
+    //        interp,
+    //        MAX_CALLS,
+    //    ).deserialize(&mut der);
+    //    assert!(matches!(err, Some(MatchError::ValidationError)));
+    //    assert!(result.is_err());
+    //}
+
+    #[test]
+    fn test_key_optionally_missing() {
+        // test a pattern with a missing key
         let consts = crate::parser::parse::<&'static str, &'static str, ()>(
             "
             :map
             ->['a'?]:map
               ->[b:?str]:?map
-                (->['x'?]x:?bool)
-                (->['y'?]y:?bool)?
+                (->['x'?]x:?bool)?
+                (->['y'?]?y:?bool)?
             ",
             None,
             None
@@ -1433,7 +1626,6 @@ mod tests {
         assert!(obj.is_none());
         assert_eq!(packs.len(), 1);
         let pack = &packs[0];
-        dbg!(pack);
         assert_eq!(pack.subpacks.len(), 1);
         let b = &pack.subpacks[0]["b"];
         assert_eq!(b.1, SerdeObject::Str(From::from("2")));
@@ -1443,16 +1635,83 @@ mod tests {
     }
 
     #[test]
+    fn test_map_without_values() {
+        // test that the map without values still collects the key
+        let consts = crate::parser::parse::<&'static str, &'static str, ()>(
+            "
+            :map
+            ->[a:?str]?:?map
+              ->[b:?str]?:?map
+            ",
+            None,
+            None
+        ).unwrap();
+        let data = r#"{"a": {}}"#;
+        let mut der = JsonDeserializer::from_str(data);
+        let mut err = Default::default();
+        let mut frames = Default::default();
+        let interp = Interpreter::new(
+            &consts,
+            &mut err,
+            &mut frames,
+            //&mut output,
+        );
+        let result = Packer::new(
+            interp,
+            MAX_CALLS,
+        ).deserialize(&mut der);
+        let (mut packs, obj) = result.unwrap();
+        assert!(obj.is_none());
+        assert_eq!(packs.len(), 1);
+        let pack = &packs[0];
+        assert_eq!(pack.subpacks.len(), 1);
+        let a = &pack.subpacks[0]["a"];
+        assert_eq!(a.1, SerdeObject::Str(From::from("a")));
+        assert_eq!(a.0.subpacks.len(), 0);
+    }
+
+    #[test]
+    fn test_guaranteed_at_least_once() {
+        // test that at least one match is required before collecting the key
+        let consts = crate::parser::parse::<&'static str, &'static str, ()>(
+            "
+            :map
+            ->[a:?str]:?map
+              ->[b:?str]:?map
+            ",
+            None,
+            None
+        ).unwrap();
+        let data = r#"{"a": {}}"#;
+        let mut der = JsonDeserializer::from_str(data);
+        let mut err = Default::default();
+        let mut frames = Default::default();
+        let interp = Interpreter::new(
+            &consts,
+            &mut err,
+            &mut frames,
+            //&mut output,
+        );
+        let result = Packer::new(
+            interp,
+            MAX_CALLS,
+        ).deserialize(&mut der);
+        let (mut packs, obj) = result.unwrap();
+        assert!(obj.is_none());
+        assert_eq!(packs.len(), 0);
+    }
+
+    #[test]
     fn test_realish_use_case() {
         // use a parsed pattern that might actually be used in the real world.
         let consts = crate::parser::parse::<&'static str, &'static str, ()>(
             "
             :map
-            ->['projects'?]?:map
-              ->[commit:?str]?:?map
-                ->[url:?str]?:?map
-                  ->[branch:?str]?:?map
-                    (->['active'?]?active:?bool)
+            ->['projects'?]:map
+              ->[commit:?str]:?map
+                ->[url:?str]:?map
+                  ->[branch:?str]:?map
+                    (->['active'?]active:?bool)?
                     (->['federate'?]?federate:?bool)?
             ",
             None,
diff --git a/src/vm/mod.rs b/src/vm/mod.rs
index 81131c0..21fec73 100644
--- a/src/vm/mod.rs
+++ b/src/vm/mod.rs
@@ -55,7 +55,7 @@ impl<O: Serialize> Default for PatternConstants<O> {
     }
 }
 
-impl<O: Serialize> std::fmt::Debug for PatternConstants<O> {
+impl<O: Serialize + std::fmt::Debug> std::fmt::Debug for PatternConstants<O> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         f.debug_struct(
             "PatternConstants"
@@ -70,7 +70,7 @@ impl<O: Serialize> std::fmt::Debug for PatternConstants<O> {
             &format_args!("({} predicates)", self.predicates.len()),
         ).field(
             "defs",
-            &format_args!("FIXME"),
+            &self.defs,
         ).finish()
     }
 }