1 files changed, 46 insertions, 15 deletions

diff --git a/src/vm/mod.rs b/src/vm/mod.rs
index 9f76ec5..81131c0 100644
--- a/src/vm/mod.rs
+++ b/src/vm/mod.rs
@@ -75,8 +75,7 @@ impl<O: Serialize> std::fmt::Debug for PatternConstants<O> {
     }
 }
 
-/// A pattern element.
-// FIXME: docs
+/// A datafu pattern element.
 #[derive(Copy, Clone, Debug)]
 pub(crate) enum PatternElement {
     /// A value is the core capturing element.
@@ -87,9 +86,19 @@ pub(crate) enum PatternElement {
         value: Option<Value>,
     },
     /// A tag is the core iterative element. It is always followed by a value.
+    ///
+    /// This one is empty.
+    EmptyTag,
+    /// A tag is the core iterative element. It is always followed by a value.
     Tag {
         /// The index of the (proto) key to match against.
-        key_subtree: Option<usize>,
+        key_subtree: usize,
+        /// Whether to allow this tree subtree to match nothing.
+        ///
+        /// By default, a datafu pattern only matches a tree if every branch of
+        /// the tree matches something. This enables opting out of that.
+        // TODO this isn't currently implemented.
+        optional: bool,
     },
     /// Marks the end of pattern iteration and the start of subtrees (if any).
     SubtreeMarker,
@@ -163,6 +172,7 @@ pub(crate) enum Value {
 }
 
 /// A pattern token.
+// TODO docs
 #[derive(Copy, Clone, Debug)]
 pub(crate) enum PatternToken {
     /// Start of a tag.
@@ -173,7 +183,7 @@ pub(crate) enum PatternToken {
     String(usize, bool),
     Regex(usize, bool),
     Parameter(usize, bool),
-    KeySubtree(usize),
+    KeySubtree(usize, bool),
     ValueSubtree(usize, bool),
 
     /// Represents a predicate which must be applied.
@@ -409,6 +419,8 @@ pub(crate) struct Frame<'pat> {
     overstep: usize,
     /// Whether this frame matches the data so far.
     matches: bool,
+    /// Whether this frame must not be allowed to match in the key step.
+    poison: bool,
 }
 
 impl<'pat, 'state, O: Serialize> Interpreter<'pat, 'state, O> {
@@ -416,7 +428,6 @@ impl<'pat, 'state, O: Serialize> Interpreter<'pat, 'state, O> {
         pat: &'pat PatternConstants<O>,
         error: &'state mut Option<crate::errors::MatchError>,
         frames: &'state mut Vec<Frame<'pat>>,
-        //output: &'state mut Pack<'pat, 'de>,
     ) -> Self {
         debug_assert!(frames.is_empty());
         frames.push(Frame {
@@ -424,13 +435,12 @@ impl<'pat, 'state, O: Serialize> Interpreter<'pat, 'state, O> {
             iar: None,
             overstep: 0,
             matches: true,
-            //path: Default::default(),
+            poison: false,
         });
         Self {
             pat: pat,
             error: error,
             frames: frames,
-            //output: Cell::from_mut(output),
         }
     }
 }
@@ -455,7 +465,9 @@ impl<'pat> Frame<'pat> {
                     },
                 }
             },
-            PatternElement::Tag { .. } => panic!("attempt to get type of tag"),
+            | PatternElement::EmptyTag
+            | PatternElement::Tag { .. }
+            => panic!("attempt to get type of tag"),
             _ => None,
         }
     }
@@ -470,7 +482,9 @@ impl<'pat> Frame<'pat> {
             PatternElement::Value { name: Some(name), .. } => {
                 Some(&*strings[name])
             },
-            PatternElement::Tag { .. } => panic!("attempt to get name of tag"),
+            | PatternElement::EmptyTag
+            | PatternElement::Tag { .. }
+            => panic!("attempt to get name of tag"),
             _ => None,
         }
     }
@@ -522,19 +536,35 @@ impl<'pat> Frame<'pat> {
         })
     }
 
-    /// Returns whether this key has a subtree.
+    /// Returns whether this key has a subtree, and if so, its index and
+    /// whether it is optional, as an `(index, optional)` pair.
     ///
     /// # Panics
     ///
     /// Panics if iteration hasn't begun, or this isn't a key.
-    fn key_subtree(&self) -> Option<usize> {
-        if let PatternElement::Tag { key_subtree } = self.op() {
-            key_subtree
-        } else {
-            unreachable!()
+    fn key_subtree(&self) -> Option<(usize, bool)> {
+        match self.op() {
+            PatternElement::Tag { key_subtree, optional } => {
+                Some((key_subtree, optional))
+            },
+            PatternElement::EmptyTag => None,
+            _ => unreachable!(),
         }
     }
 
+    /// Returns whether this frame is in a value operation.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the frame isn't active or iteraction hasn't begun.
+    #[inline]
+    fn is_value(&self) -> bool {
+        self.active() && matches!(
+            self.raw_op(),
+            PatternElement::Value { .. },
+        )
+    }
+
     /// Returns this value subtree, as an `(index, optional)` pair.
     ///
     /// # Panics
@@ -561,6 +591,7 @@ impl<'pat> Frame<'pat> {
     }
 
     /// Returns whether this frame is active (not overstepped).
+    #[inline]
     fn active(&self) -> bool {
         self.overstep == 0
     }