1 files changed, 87 insertions, 20 deletions
diff --git a/src/vm/mod.rs b/src/vm/mod.rs
index 21fec73..eb9a2a3 100644
--- a/src/vm/mod.rs
+++ b/src/vm/mod.rs
@@ -9,9 +9,11 @@ use std::borrow::Cow;
 use std::cell::Cell;
 use std::cell::RefCell;
 use std::collections::BTreeMap;
+use std::collections::VecDeque;
 use std::marker::PhantomData;
 
 use indexmap::IndexMap;
+use indexmap::IndexSet;
 use regex::Regex;
 use serde::Serialize;
 
@@ -37,7 +39,7 @@ pub(crate) struct PatternConstants<O: Serialize> {
     pub(crate) protos: Vec<Vec<PatternElement>>,
     // Note that we can borrow these when creating the output map.
     // https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=da26f9175e96273fa0b94971a4e6172f
-    pub(crate) strings: Vec<String>,
+    pub(crate) strings: IndexSet<String>,
     pub(crate) regices: Vec<Regex>,
     pub(crate) predicates: Vec<Box<Predicate>>,
     pub(crate) defs: Vec<O>,
@@ -348,7 +350,6 @@ where
     fn into_deserializer(self) -> Self::Deserializer {
         Self::Deserializer {
             obj: self,
-            value: None,
             _e: PhantomData,
         }
     }
@@ -357,15 +358,25 @@ where
 /// Packed serde objects and datafu internal representation.
 ///
 /// This is an iterative store of key-value pairs.
+///
+/// It's effectively a tree node.
 #[derive(Clone, Debug, Default)]
 pub struct Pack<'pat, 'de> {
-    subpacks: Vec<IndexMap<&'pat str, (Pack<'pat, 'de>, SerdeObject<'de>)>>,
+    subpacks: VecDeque<(IndexMap<&'pat str, SerdeObject<'de>>, Pack<'pat, 'de>)>,
 }
 
 impl<'pat, 'de> Pack<'pat, 'de> {
-    /// Merges two packs, with elements from `other` coming after `self`, as if
-    /// parts of the same iteration.
-    fn merge_breadth(&mut self, mut other: Self) {
+    /// Adds the elements of the `other` pack to the matching iterarions of the
+    /// current pack. If either pack is empty, pick the non-empty pack.
+    ///
+    /// The current pack will have the same number of iterations, but will
+    /// contain captures from both packs. In case of captures of the same name,
+    /// `other` will override `self`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the packs have different iteration lengths.
+    fn zip(&mut self, mut other: Self) {
         match (self.subpacks.len(), other.subpacks.len()) {
             (0, _) => {
                 *self = other;
@@ -373,26 +384,82 @@ impl<'pat, 'de> Pack<'pat, 'de> {
             (_, 0) => {},
             (a, b) if a == b => {
                 for (l, r) in self.subpacks.iter_mut().zip(other.subpacks) {
-                    l.extend(r)
+                    // note that we can't actually recurse deeper than the VM
+                    // actually does itself, so we don't need to worry about
+                    // blowing the stack.
+                    l.0.extend(r.0);
+                    l.1.zip(r.1);
                 }
             },
-            _ => unreachable!("merge_breadth unbalanced iterations"),
+            _ => unreachable!("zip unbalanced iterations"),
         }
     }
 
-    /// Merges two packs, with elements from `other` coming inside the last
-    /// element of `self` recursively, if any.
-    fn merge_depth(&mut self, mut other: Self) {
-        // note that we can't actually recurse deeper than the VM
-        // actually does itself, so we don't need to worry about
-        // blowing the stack.
-        if let Some(into) = self.subpacks.iter_mut().rev().filter(|map| {
-            !map.is_empty()
-        }).next() {
-            into.last_mut().unwrap().1.0.merge_depth(other);
-        } else {
-            *self = other;
+    /// Adds the elements of the `other` pack to all iterations captured by
+    /// this pack, such as to form a cartesian product. If either pack is
+    /// empty, pick the non-empty pack. If both packs have a length of 1, merge
+    /// their captures.
+    ///
+    /// The current pack will contain captures from both packs. In case of
+    /// captures of the same name, `other` will override `self`.
+    fn cartesian_product(&mut self, mut other: Self) {
+        match (self.subpacks.len(), other.subpacks.len()) {
+            (_, 0) => {
+                return;
+            },
+            (0, _) => {
+                *self = other;
+                return;
+            },
+            (1, 1) => {
+                let (robjects, rpack) = other.subpacks.pop_back().unwrap();
+                let (ref mut lobjects, ref mut lpack) = self.subpacks[0];
+                lobjects.extend(robjects);
+                lpack.cartesian_product(rpack);
+                return;
+            },
+            (1, _) => {
+                self.subpacks[0].1.cartesian_product(other);
+                return;
+            },
+            (_, 1) => {
+                // FIXME: need to be careful with this one.
+                // we want `other` to override entries from `self`, so we need
+                // to scan `self` for captures of the same name as those in
+                // `other`, and remove those captures. only then can we swap
+                // `self` and `other` and merge them.
+                // for now we can just do the inefficient thing tho.
+            },
+            _ => {},
         }
+        // FIXME instead of doing this, perhaps we should find the smaller one,
+        // and put clones of the larger one into it?
+        self.subpacks.iter_mut().for_each(|&mut (_, ref mut lpack)| {
+            lpack.cartesian_product(other.clone())
+        });
+    }
+
+    /// Returns the serde object with the given name at the given iteration of
+    /// this pack.
+    #[cfg(test)]
+    fn get_object_at(
+        &self,
+        iter: usize,
+        name: &str,
+    ) -> Option<&SerdeObject<'de>> {
+        self.subpacks.get(iter).map(|x| &x.0).and_then(|x| x.get(name))
+    }
+
+    /// Returns the subpack related to the given name at the given iteration of
+    /// this pack.
+    #[cfg(test)]
+    fn get_subpack_at(
+        &self,
+        iter: usize,
+        name: &str,
+    ) -> Option<&Pack<'pat, 'de>> {
+        let _ = name;
+        self.subpacks.get(iter).map(|x| &x.1)
     }
 }