summary refs log tree commit diff stats
path: root/src/vm
diff options
context:
space:
mode:
Diffstat (limited to 'src/vm')
-rw-r--r--src/vm/de/mod.rs (renamed from src/vm/de.rs)687
-rw-r--r--src/vm/de/unpacker.rs518
-rw-r--r--src/vm/mod.rs107
3 files changed, 1153 insertions, 159 deletions
diff --git a/src/vm/de.rs b/src/vm/de/mod.rs
index 8f2aa8d..3cba18a 100644
--- a/src/vm/de.rs
+++ b/src/vm/de/mod.rs
@@ -14,7 +14,6 @@ use serde::de::IntoDeserializer as _;
 
 use smallvec::SmallVec;
 
-
 use super::Frame;
 use super::Interpreter;
 use super::Pack;
@@ -24,6 +23,11 @@ use super::SerdeObject;
 use super::Type;
 use super::Value;
 use crate::errors::MatchError;
+use crate::errors::QueryError;
+
+mod unpacker;
+
+pub use unpacker::Unpacker;
 
 /// A `DeserializeSeed` for Datafu input.
 ///
@@ -259,7 +263,7 @@ impl<'pat, 'state, 'de, O: Serialize> Packer<'pat, 'state, O> {
                                 target_frame.matches = true;
                                 pack_index += 1;
                             } else {
-                                packs[target_pack].merge_breadth(pack);
+                                packs[target_pack].zip(pack);
                             }
                         } else {
                             //if frame.poison {
@@ -446,8 +450,8 @@ macro_rules! vs {
                     let mut pack = Pack::default();
                     if let Some(name) = frame.get_name(pat) {
                         let mut map = IndexMap::new();
-                        map.insert(name, (Pack::default(), SerdeObject::$obj$v));
-                        pack.subpacks.push(map);
+                        map.insert(name, SerdeObject::$obj$v);
+                        pack.subpacks.push_back((map, Pack::default()));
                     }
                     packs.push(pack);
                     Ok(())
@@ -551,14 +555,8 @@ where
                 let mut pack = Pack::default();
                 if let Some(name) = frame.get_name(pat) {
                     let mut map = IndexMap::new();
-                    map.insert(
-                        name,
-                        (
-                            Pack::default(),
-                            SerdeObject::Str(Cow::Owned(v.into())),
-                        ),
-                    );
-                    pack.subpacks.push(map);
+                    map.insert(name, SerdeObject::Str(Cow::Owned(v.into())));
+                    pack.subpacks.push_back((map, Pack::default()));
                 }
                 packs.push(pack);
                 Ok(())
@@ -634,14 +632,8 @@ where
                 let mut pack = Pack::default();
                 if let Some(name) = frame.get_name(pat) {
                     let mut map = IndexMap::new();
-                    map.insert(
-                        name,
-                        (
-                            Pack::default(),
-                            SerdeObject::Str(Cow::Borrowed(v)),
-                        ),
-                    );
-                    pack.subpacks.push(map);
+                    map.insert(name, SerdeObject::Str(Cow::Borrowed(v)));
+                    pack.subpacks.push_back((map, Pack::default()));
                 }
                 packs.push(pack);
                 Ok(())
@@ -709,15 +701,211 @@ where
     {
         todo!()
     }
-    fn visit_seq<A>(self, seq: A) -> Result<Self::Value, A::Error>
+    fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
     where
         A: serde::de::SeqAccess<'de>,
     {
-        let mut obj = None;
-        if self.collecting {
-            obj = Some(SerdeObject::Seq(Vec::new()));
+        let old_collecting = self.collecting;
+        let pat = self.interp.pat;
+        let mut collecting = old_collecting;
+        let typeck = self.frames_mut().iter_active_mut().try_for_each(|frame| {
+            let ty = frame.get_type();
+            match ty {
+                | Some((Type::Seq, _))
+                | Some((Type::Any, _))
+                | Some((Type::IgnoredAny, _))
+                | None
+                => {},
+                Some((_, false)) => {
+                    frame.matches = false;
+                    return Ok(());
+                },
+                Some((_, true)) => {
+                    return Err(MatchError::ValidationError)
+                },
+            }
+            if frame.get_name(pat).is_some() {
+                collecting = true;
+            }
+            Ok(())
+        });
+        match typeck {
+            Err(e) => {
+                self.interp.error.insert(e);
+                return Err(A::Error::custom("type mismatch"));
+            },
+            _ => (),
         }
-        todo!()
+        if let Err(e) = self.step_in() { return Err(e); }
+        self.collecting = collecting;
+        let mut subframes = Vec::new();
+        let mut output_matches = Vec::new();
+        self.frames().iter_active().for_each(|frame| {
+            if let Some((key_subtree, _)) = frame.key_subtree() {
+                subframes.push(Frame {
+                    ops: &pat.protos[key_subtree],
+                    iar: None,
+                    overstep: 0,
+                    matches: true,
+                    poison: false,
+                });
+            }
+            output_matches.push(false);
+        });
+        let mut obj_inner = Vec::new();
+        let mut output_packs = Vec::new();
+        let mut iter = 0..;
+        while let packed_key = {
+            let subinterp = Interpreter {
+                pat: pat,
+                frames: &mut subframes,
+                error: self.interp.error,
+            };
+            let mut subpacker = Packer {
+                interp: subinterp,
+                collecting: self.collecting,
+                call_limit: self.call_limit,
+            };
+            if subpacker.interp.frames.is_empty() {
+                // avoid overflow
+                serde::de::DeserializeSeed::deserialize(&mut subpacker, {
+                    serde::de::value::U64Deserializer::new(0)
+                })?
+            } else {
+                serde::de::DeserializeSeed::deserialize(&mut subpacker, {
+                    serde::de::value::U64Deserializer::new(iter.next().unwrap())
+                })?
+            }
+        } {
+            self.frames_mut().iter_active_mut().filter(|frame| {
+                frame.key_subtree().is_some()
+            }).zip(&mut subframes).for_each(|(frame, subframe)| {
+                frame.matches = subframe.matches;
+                // reset subframe for next iteration
+                // NOTE wait to reset subframe.matches when merging packs!!!
+                subframe.iar = None;
+            });
+            self.frames_mut().iter_active_mut().for_each(|frame| {
+                // mark every non-subtree key as matching.
+                if frame.key_subtree().is_none() {
+                    frame.matches = true;
+                }
+            });
+            let Some(packed_value) = seq.next_element_seed(&mut *self)? else {
+                break;
+            };
+            if self.collecting {
+                obj_inner.push(packed_value.1.unwrap());
+            }
+            let mut key_packs_per_frame = packed_key.0.into_iter();
+            let mut value_packs_per_frame = packed_value.0.into_iter();
+            // whatever is active in self.frames(), if matches, has a pack
+            // whatever is in subframes, if matches, has a pack
+            // count(active self.frames() with subtree which match) is always
+            // smaller than count(subframes which match) because the former
+            // gets updated by next_value_seed
+            // count(active self.frames() with subtree) == count(subframes)
+            // tl;dr: need to figure out which packs produced by subframes line
+            // up with which packs produced by self, discarding extra subframes
+            // (where the corresponding self frame doesn't match) and accepting
+            // extra packs produced by self.
+            // NOTE: key_packs_per_frame ~ subframes
+            // value_packs_per_frame ~ self
+            // keys come first tho (key.merge_from(value))
+            let mut iter_subframes = subframes.iter_mut();
+            // related to output_packs
+            let mut pack_index = 0;
+            for (frame, out_matches) in self.frames().iter_active().zip({
+                &mut output_matches
+            }) {
+                // check if this frame has an associated subframe
+                let subframe = if frame.key_subtree().is_some() {
+                    // if there are more frames with associated subframes
+                    // than there are subframes, panic
+                    Some(iter_subframes.next().unwrap())
+                } else {
+                    None
+                };
+                let mut new_pack = None;
+                if frame.matches && subframe.is_some() {
+                    // this already implies subframe.matches
+                    let mut key_pack = key_packs_per_frame.next().unwrap();
+                    let value_pack = value_packs_per_frame.next().unwrap();
+                    key_pack.cartesian_product(value_pack);
+                    new_pack = Some(key_pack);
+                } else if frame.matches {
+                    // value matches but there's no subframe, carry on
+                    let value_pack = value_packs_per_frame.next().unwrap();
+                    new_pack = Some(value_pack);
+                } else if !frame.matches && subframe.is_some() {
+                    // frame didn't match but there was a subframe
+                    let subframe = subframe.unwrap();
+                    if subframe.matches {
+                        // subframe matched, remove key pack
+                        let _ = key_packs_per_frame.next().unwrap();
+                    } else {
+                        // neither matched, no relevant packs
+                        // do reset subframe for next_key_seed tho!
+                        subframe.matches = true;
+                    }
+                } else {
+                    // no relevant packs
+                }
+                if let Some(new_pack) = new_pack {
+                    if !*out_matches {
+                        *out_matches = true;
+                        output_packs.insert(pack_index, Pack::default());
+                    }
+                    let output_pack = &mut output_packs[pack_index];
+                    output_pack.subpacks.extend(new_pack.subpacks);
+                }
+                if *out_matches {
+                    pack_index += 1;
+                }
+            }
+        }
+        let mut poison = false;
+        for (f, m) in self.frames_mut().iter_active_mut().zip(output_matches) {
+            f.matches = m;
+            if !m {
+                if let Some((_, false)) = f.key_subtree() {
+                    poison = true;
+                }
+            }
+        }
+        let obj = SerdeObject::Seq(obj_inner);
+        let mut final_packs = self.step_out(output_packs)?;
+        let mut iter_final_packs = 0..;
+        self.frames_mut().iter_active_mut().for_each(|frame| {
+            let ty = frame.get_type();
+            match ty {
+                | Some((Type::Seq, _))
+                | Some((Type::Any, _))
+                | Some((Type::IgnoredAny, _))
+                | None
+                => {
+                    frame.poison = poison;
+                    let matched = std::mem::replace(&mut frame.matches, true);
+                    if !matched {
+                        final_packs.insert(
+                            iter_final_packs.start,
+                            Pack::default(),
+                        );
+                    }
+                },
+                _ => return,
+            }
+            let pack = &mut final_packs[iter_final_packs.next().unwrap()];
+            if let Some(name) = frame.get_name(pat) {
+                // we can assume collecting == true
+                let old_pack = std::mem::take(pack);
+                let mut map = IndexMap::new();
+                map.insert(name, obj.clone());
+                pack.subpacks.push_back((map, old_pack));
+            }
+        });
+        self.collecting = old_collecting;
+        Ok((final_packs, collecting.then(|| obj)))
     }
     fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
     where
@@ -839,7 +1027,7 @@ where
                     // this already implies subframe.matches
                     let mut key_pack = key_packs_per_frame.next().unwrap();
                     let value_pack = value_packs_per_frame.next().unwrap();
-                    key_pack.merge_depth(value_pack);
+                    key_pack.cartesian_product(value_pack);
                     new_pack = Some(key_pack);
                 } else if frame.matches {
                     // value matches but there's no subframe, carry on
@@ -908,8 +1096,8 @@ where
                 // we can assume collecting == true
                 let old_pack = std::mem::take(pack);
                 let mut map = IndexMap::new();
-                map.insert(name, (old_pack, obj.clone()));
-                pack.subpacks.push(map);
+                map.insert(name, obj.clone());
+                pack.subpacks.push_back((map, old_pack));
             }
         });
         self.collecting = old_collecting;
@@ -930,73 +1118,75 @@ where
     }
 }
 
-/// A `Deserializer` for Datafu output.
-///
-/// This converts from Datafu's internal representation (a "pack") into the
-/// desired output type.
-pub struct Unpacker<'pat, 'de> {
-    pack: Pack<'pat, 'de>,
-    call_limit: usize,
+/// Deserializes a SerdeObject
+pub(crate) struct SerdeObjectDeserializer<'de, E> {
+    pub(crate) obj: SerdeObject<'de>,
+    pub(crate) _e: PhantomData<fn() -> E>,
 }
 
-impl<'pat, 'de> Unpacker<'pat, 'de> {
-    /// Unpacks a Datafu "pack".
-    pub fn new(pack: Pack<'pat, 'de>, call_limit: usize) -> Self {
-        Self {
-            pack, call_limit,
-        }
-    }
+/// Deserializes a SerdeObject::Seq
+struct SerdeObjectSeq<'de, I: Iterator<Item=SerdeObject<'de>>, E> {
+    iter: I,
+    _e: PhantomData<fn() -> E>,
 }
 
-impl<'pat, 'de> serde::Deserializer<'de> for Unpacker<'pat, 'de> {
-    // TODO datafu errors
-    type Error = serde::de::value::Error;
-    fn deserialize_any<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_bool<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_i8<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_i16<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_i32<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_i64<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_u8<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_u16<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_u32<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_u64<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_f32<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_f64<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_char<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_str<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_string<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_bytes<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_byte_buf<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_option<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_unit<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_unit_struct<V>(self, _: &'static str, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_newtype_struct<V>(self, _: &'static str, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_seq<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_tuple<V>(self, _: usize, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_tuple_struct<V>(self, _: &'static str, _: usize, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_map<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_struct<V>(
+impl<'de, E> serde::de::VariantAccess<'de> for SerdeObjectDeserializer<'de, E>
+where
+    E: serde::de::Error,
+{
+    type Error = E;
+
+    fn unit_variant(self) -> Result<(), E> {
+        todo!()
+    }
+    fn newtype_variant_seed<T>(self, seed: T) -> Result<T::Value, E>
+    where
+        T: serde::de::DeserializeSeed<'de>,
+    {
+        todo!()
+    }
+    fn tuple_variant<V>(self, len: usize, visitor: V) -> Result<V::Value, E>
+    where
+        V: serde::de::Visitor<'de>,
+    {
+        todo!()
+    }
+    fn struct_variant<V>(
         self,
-        _: &'static str,
         fields: &'static [&'static str],
         visitor: V,
-    ) -> Result<V::Value, Self::Error>
+    ) -> Result<V::Value, E>
     where
         V: serde::de::Visitor<'de>,
     {
         todo!()
     }
-    fn deserialize_enum<V>(self, _: &'static str, _: &'static [&'static str], _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_identifier<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
-    fn deserialize_ignored_any<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
 }
 
-/// Deserializes a SerdeObject
-pub(crate) struct SerdeObjectDeserializer<'de, E> {
-    pub(crate) obj: SerdeObject<'de>,
-    pub(crate) value: Option<SerdeObject<'de>>,
-    pub(crate) _e: PhantomData<fn() -> E>,
+impl<'de, E> serde::de::EnumAccess<'de> for SerdeObjectDeserializer<'de, E>
+where
+    E: serde::de::Error,
+{
+    type Error = E;
+    type Variant = Self;
+
+    fn variant_seed<V>(self, seed: V) -> Result<(V::Value, Self), E>
+    where
+        V: serde::de::DeserializeSeed<'de>,
+    {
+        match self.obj {
+            SerdeObject::Enum { variant, data } => {
+                seed.deserialize(variant.into_deserializer()).map(|it| {
+                    let data = Self {
+                        obj: *data,
+                        _e: PhantomData,
+                    };
+                    (it, data)
+                })
+            },
+            _ => unreachable!(),
+        }
+    }
 }
 
 impl<'de, E> serde::de::Deserializer<'de> for SerdeObjectDeserializer<'de, E>
@@ -1030,12 +1220,20 @@ where
             SerdeObject::Some(x) => v.visit_some(x.into_deserializer()),
             SerdeObject::None => v.visit_none(),
             SerdeObject::Unit => v.visit_unit(),
-            SerdeObject::Seq(x) => todo!(),
-            SerdeObject::Map(x) => todo!(),
+            SerdeObject::Seq(x) => {
+                let mut x = serde::de::value::SeqDeserializer::new(x.into_iter());
+                let r = v.visit_seq(&mut x);
+                x.end().and(r)
+            },
+            SerdeObject::Map(x) => {
+                let mut x = serde::de::value::MapDeserializer::new(x.into_iter());
+                let r = v.visit_map(&mut x);
+                x.end().and(r)
+            },
             SerdeObject::NewtypeStruct(x) => {
                 v.visit_newtype_struct(x.into_deserializer())
             },
-            SerdeObject::Enum { variant, data } => todo!(),
+            SerdeObject::Enum { .. } => v.visit_enum(self),
         }
     }
     fn deserialize_ignored_any<V>(self, v: V) -> Result<V::Value, Self::Error>
@@ -1110,7 +1308,7 @@ mod tests {
     fn test_simple_match() {
         // test matching a simple value
         let mut consts = PatternConstants::<()>::default();
-        consts.strings.push("hello".into());
+        consts.strings.insert("hello".into());
         consts.protos.push(vec![
             PatternElement::Value {
                 name: Some(0),
@@ -1127,14 +1325,17 @@ mod tests {
         let packed = Packer::new(interp, MAX_CALLS).deserialize(&mut der);
         let (packs, obj) = packed.unwrap();
         assert!(obj.is_none());
-        assert_eq!(packs[0].subpacks[0]["hello"].1, SerdeObject::U64(3));
+        assert_eq!(
+            packs[0].get_object_at(0, "hello").unwrap(),
+            &SerdeObject::U64(3),
+        );
     }
 
     #[test]
     fn test_simple_error() {
         // test a value that doesn't match (serde_json error)
         let mut consts = PatternConstants::<()>::default();
-        consts.strings.push("hello".into());
+        consts.strings.insert("hello".into());
         consts.protos.push(vec![
             PatternElement::Value {
                 name: Some(0),
@@ -1157,8 +1358,8 @@ mod tests {
     fn test_basic_multiframe() {
         // test multiple frames (matching and non-matching)
         let mut consts = PatternConstants::<()>::default();
-        consts.strings.push("a".into());
-        consts.strings.push("b".into());
+        consts.strings.insert("a".into());
+        consts.strings.insert("b".into());
         consts.protos.push(vec![
             PatternElement::Value {
                 name: Some(0),
@@ -1203,8 +1404,8 @@ mod tests {
         let (packs, obj) = packed.unwrap();
         assert!(obj.is_none());
         assert_eq!(
-            packs[0].subpacks[0]["a"].1,
-            SerdeObject::U64(10),
+            packs[0].get_object_at(0, "a").unwrap(),
+            &SerdeObject::U64(10),
         );
         assert_eq!(packs.len(), 1);
         assert!(frames[0].matches);
@@ -1215,8 +1416,8 @@ mod tests {
     fn test_map() {
         // test visit_map
         let mut consts = PatternConstants::<()>::default();
-        consts.strings.push("key".into());
-        consts.strings.push("value".into());
+        consts.strings.insert("key".into());
+        consts.strings.insert("value".into());
         consts.protos.push(vec![
             PatternElement::Value {
                 name: Some(0),
@@ -1251,20 +1452,22 @@ mod tests {
         let (packs, obj) = packed.unwrap();
         assert!(obj.is_none());
         assert_eq!(
-            packs[0].subpacks[0]["key"].1,
-            SerdeObject::Str("hello".into()),
+            packs[0].get_object_at(0, "key").unwrap(),
+            &SerdeObject::Str("hello".into()),
         );
         assert_eq!(
-            packs[0].subpacks[0]["key"].0.subpacks[0]["value"].1,
-            SerdeObject::U64(0),
+            packs[0]
+                .get_object_at(0, "value").unwrap(),
+            &SerdeObject::U64(0),
         );
         assert_eq!(
-            packs[0].subpacks[1]["key"].1,
-            SerdeObject::Str("world".into()),
+            packs[0].get_object_at(1, "key").unwrap(),
+            &SerdeObject::Str("world".into()),
         );
         assert_eq!(
-            packs[0].subpacks[1]["key"].0.subpacks[0]["value"].1,
-            SerdeObject::U64(1),
+            packs[0]
+                .get_object_at(1, "value").unwrap(),
+            &SerdeObject::U64(1),
         );
     }
 
@@ -1381,7 +1584,6 @@ mod tests {
             None,
             None,
         ).unwrap();
-        dbg!(&consts);
         let data = r#"{"hello": "world"}"#;
         let mut der = JsonDeserializer::from_str(data);
         let mut err = Default::default();
@@ -1440,8 +1642,14 @@ mod tests {
         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));
+        assert_eq!(
+            pack.get_object_at(0, "name").unwrap(),
+            &SerdeObject::Str(From::from("a")),
+        );
+        assert_eq!(
+            pack.get_object_at(0, "value").unwrap(),
+            &SerdeObject::U32(1),
+        );
     }
 
     #[test]
@@ -1480,8 +1688,14 @@ mod tests {
         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));
+        assert_eq!(
+            pack.get_object_at(0, "name").unwrap(),
+            &SerdeObject::Str(From::from("a")),
+        );
+        assert_eq!(
+            pack.get_object_at(0, "value").unwrap(),
+            &SerdeObject::U32(1),
+        );
     }
 
     #[test]
@@ -1516,7 +1730,10 @@ mod tests {
         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));
+        assert_eq!(
+            pack.get_object_at(0, "name").unwrap(),
+            &SerdeObject::U32(1),
+        );
     }
 
     #[test]
@@ -1627,11 +1844,18 @@ mod tests {
         assert_eq!(packs.len(), 1);
         let pack = &packs[0];
         assert_eq!(pack.subpacks.len(), 1);
-        let b = &pack.subpacks[0]["b"];
-        assert_eq!(b.1, SerdeObject::Str(From::from("2")));
-        assert_eq!(b.0.subpacks.len(), 1);
-        assert_eq!(b.0.subpacks[0]["x"].1, SerdeObject::Bool(true));
-        assert_eq!(b.0.subpacks[0]["y"].1, SerdeObject::Bool(true));
+        assert_eq!(
+            pack.get_object_at(0, "b").unwrap(),
+            &SerdeObject::Str(From::from("2")),
+        );
+        assert_eq!(
+            pack.get_object_at(0, "x").unwrap(),
+            &SerdeObject::Bool(true),
+        );
+        assert_eq!(
+            pack.get_object_at(0, "y").unwrap(),
+            &SerdeObject::Bool(true),
+        );
     }
 
     #[test]
@@ -1665,9 +1889,11 @@ mod tests {
         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);
+        assert_eq!(
+            pack.get_object_at(0, "a").unwrap(),
+            &SerdeObject::Str(From::from("a")),
+        );
+        assert_eq!(pack.get_subpack_at(0, "a").unwrap().subpacks.len(), 0);
     }
 
     #[test]
@@ -1702,6 +1928,145 @@ mod tests {
     }
 
     #[test]
+    fn test_basic_seq() {
+        // test that sequences work
+        let consts = crate::parser::parse::<&'static str, &'static str, ()>(
+            "
+            :seq
+            ->[i:u64]v:u64
+            ",
+            None,
+            None
+        ).unwrap();
+        let data = r#"[10, 11, 12]"#;
+        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(), 3);
+        assert_eq!(
+            pack.get_object_at(0, "i").unwrap(),
+            &SerdeObject::U64(0),
+        );
+        assert_eq!(
+            pack.get_object_at(0, "v").unwrap(),
+            &SerdeObject::U64(10),
+        );
+        assert_eq!(
+            pack.get_object_at(1, "i").unwrap(),
+            &SerdeObject::U64(1),
+        );
+        assert_eq!(
+            pack.get_object_at(1, "v").unwrap(),
+            &SerdeObject::U64(11),
+        );
+        assert_eq!(
+            pack.get_object_at(2, "i").unwrap(),
+            &SerdeObject::U64(2),
+        );
+        assert_eq!(
+            pack.get_object_at(2, "v").unwrap(),
+            &SerdeObject::U64(12),
+        );
+    }
+
+    #[test]
+    fn test_list_key() {
+        let consts = crate::parser::parse::<&'static str, &'static str, ()>(
+            "
+            :map
+            ->[:seq->k:u64]:seq
+              ->v:str
+            ",
+            None,
+            None
+        ).unwrap();
+        let data = &[
+            0x01, // map length (1)
+            0x03, // list length (3)
+            0x01, 0x02, 0x03, // [1, 2, 3]
+            0x02, // list length (2)
+            0x05, // string length (5)
+            b't', b'r', b'a', b'n', b's',
+            0x06, // string length (6)
+            b'r', b'i', b'g', b'h', b't', b's'
+        ];
+        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(), 3);
+        let subpack = pack.get_subpack_at(0, "k").unwrap();
+        assert_eq!(subpack.subpacks.len(), 2);
+        assert_eq!(
+            pack.get_object_at(0, "k").unwrap(),
+            &SerdeObject::U64(1),
+        );
+        assert_eq!(
+            subpack.get_object_at(0, "v").unwrap(),
+            &SerdeObject::Str(From::from("trans")),
+        );
+        assert_eq!(
+            subpack.get_object_at(1, "v").unwrap(),
+            &SerdeObject::Str(From::from("rights")),
+        );
+        let subpack = pack.get_subpack_at(1, "k").unwrap();
+        assert_eq!(subpack.subpacks.len(), 2);
+        assert_eq!(
+            pack.get_object_at(1, "k").unwrap(),
+            &SerdeObject::U64(2),
+        );
+        assert_eq!(
+            subpack.get_object_at(0, "v").unwrap(),
+            &SerdeObject::Str(From::from("trans")),
+        );
+        assert_eq!(
+            subpack.get_object_at(1, "v").unwrap(),
+            &SerdeObject::Str(From::from("rights")),
+        );
+        let subpack = pack.get_subpack_at(2, "k").unwrap();
+        assert_eq!(subpack.subpacks.len(), 2);
+        assert_eq!(
+            pack.get_object_at(2, "k").unwrap(),
+            &SerdeObject::U64(3),
+        );
+        assert_eq!(
+            subpack.get_object_at(0, "v").unwrap(),
+            &SerdeObject::Str(From::from("trans")),
+        );
+        assert_eq!(
+            subpack.get_object_at(1, "v").unwrap(),
+            &SerdeObject::Str(From::from("rights")),
+        );
+    }
+
+    #[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, ()>(
@@ -1718,7 +2083,7 @@ mod tests {
             None
         ).unwrap();
         let data = r#"
-        {"base_url": "https://ganarchy.autistic.space", "repo_list_srcs": {"https://ganarchy.autistic.space/index.toml": {"active": false}}, "projects": {"a8fb5087f79eafe312db270082c052c427b208c2": {"https://soniex2.autistic.space/git-repos/mmorfc.git": {"HEAD": {"active": true, "pinned": true}}}, "2d0b363fe3179087de59d9ef4a2d14af21d89071": {"https://soniex2.autistic.space/git-repos/chewstuff.git": {"HEAD": {"active": true, "pinned": true}}}}}
+        {"base_url": "https://ganarchy.autistic.space", "repo_list_srcs": {"https://ganarchy.autistic.space/index.toml": {"active": false}}, "projects": {"385e734a52e13949a7a5c71827f6de920dbfea43": {"https://github.com/ganarchy/GAnarchy": {"HEAD": {"active": true}}, "https://soniex2.autistic.space/git-repos/ganarchy.git": {"HEAD": {"active": true, "pinned": true}}}, "a8fb5087f79eafe312db270082c052c427b208c2": {"https://soniex2.autistic.space/git-repos/mmorfc.git": {"HEAD": {"active": true, "pinned": true}}}, "2d0b363fe3179087de59d9ef4a2d14af21d89071": {"https://soniex2.autistic.space/git-repos/chewstuff.git": {"HEAD": {"active": true, "pinned": true}}}}}
         "#;
         let mut der = JsonDeserializer::from_str(data);
         let mut err = Default::default();
@@ -1737,30 +2102,74 @@ mod tests {
         assert!(obj.is_none());
         assert_eq!(packs.len(), 1);
         let pack = &packs[0];
-        assert_eq!(pack.subpacks.len(), 2);
+        assert_eq!(pack.subpacks.len(), 3);
+
+        let commit = pack.get_subpack_at(0, "commit").unwrap();
+        assert_eq!(
+            pack.get_object_at(0, "commit").unwrap(),
+            &SerdeObject::Str(From::from("385e734a52e13949a7a5c71827f6de920dbfea43")),
+        );
+        assert_eq!(commit.subpacks.len(), 2);
+
+        assert_eq!(
+            commit.get_object_at(0, "url").unwrap(),
+            &SerdeObject::Str(From::from("https://github.com/ganarchy/GAnarchy")),
+        );
+        assert_eq!(
+            commit.get_object_at(0, "branch").unwrap(),
+            &SerdeObject::Str(From::from("HEAD")),
+        );
+        assert_eq!(
+            commit.get_object_at(0, "active").unwrap(),
+            &SerdeObject::Bool(true),
+        );
+
+        assert_eq!(
+            commit.get_object_at(1, "url").unwrap(),
+            &SerdeObject::Str(From::from("https://soniex2.autistic.space/git-repos/ganarchy.git")),
+        );
+        assert_eq!(
+            commit.get_object_at(1, "branch").unwrap(),
+            &SerdeObject::Str(From::from("HEAD")),
+        );
+        assert_eq!(
+            commit.get_object_at(1, "active").unwrap(),
+            &SerdeObject::Bool(true),
+        );
 
-        let commit = &pack.subpacks[0]["commit"];
-        assert_eq!(commit.1, SerdeObject::Str(From::from("a8fb5087f79eafe312db270082c052c427b208c2")));
-        assert_eq!(commit.0.subpacks.len(), 1);
-        let url = &commit.0.subpacks[0]["url"];
-        assert_eq!(url.1, SerdeObject::Str(From::from("https://soniex2.autistic.space/git-repos/mmorfc.git")));
-        assert_eq!(url.0.subpacks.len(), 1);
-        let branch = &url.0.subpacks[0]["branch"];
-        assert_eq!(branch.1, SerdeObject::Str(From::from("HEAD")));
-        assert_eq!(branch.0.subpacks.len(), 1);
-        let active = &branch.0.subpacks[0]["active"];
-        assert_eq!(active.1, SerdeObject::Bool(true));
-
-        let commit = &pack.subpacks[1]["commit"];
-        assert_eq!(commit.1, SerdeObject::Str(From::from("2d0b363fe3179087de59d9ef4a2d14af21d89071")));
-        assert_eq!(commit.0.subpacks.len(), 1);
-        let url = &commit.0.subpacks[0]["url"];
-        assert_eq!(url.1, SerdeObject::Str(From::from("https://soniex2.autistic.space/git-repos/chewstuff.git")));
-        assert_eq!(url.0.subpacks.len(), 1);
-        let branch = &url.0.subpacks[0]["branch"];
-        assert_eq!(branch.1, SerdeObject::Str(From::from("HEAD")));
-        assert_eq!(branch.0.subpacks.len(), 1);
-        assert_eq!(active.1, SerdeObject::Bool(true));
+        assert_eq!(
+            pack.get_object_at(1, "commit").unwrap(),
+            &SerdeObject::Str(From::from("a8fb5087f79eafe312db270082c052c427b208c2")),
+        );
+        assert_eq!(
+            pack.get_object_at(1, "url").unwrap(),
+            &SerdeObject::Str(From::from("https://soniex2.autistic.space/git-repos/mmorfc.git")),
+        );
+        assert_eq!(
+            pack.get_object_at(1, "branch").unwrap(),
+            &SerdeObject::Str(From::from("HEAD")),
+        );
+        assert_eq!(
+            pack.get_object_at(1, "active").unwrap(),
+            &SerdeObject::Bool(true),
+        );
+
+        assert_eq!(
+            pack.get_object_at(2, "commit").unwrap(),
+            &SerdeObject::Str(From::from("2d0b363fe3179087de59d9ef4a2d14af21d89071")),
+        );
+        assert_eq!(
+            pack.get_object_at(2, "url").unwrap(),
+            &SerdeObject::Str(From::from("https://soniex2.autistic.space/git-repos/chewstuff.git")),
+        );
+        assert_eq!(
+            pack.get_object_at(2, "branch").unwrap(),
+            &SerdeObject::Str(From::from("HEAD")),
+        );
+        assert_eq!(
+            pack.get_object_at(2, "active").unwrap(),
+            &SerdeObject::Bool(true),
+        );
     }
 }
 
diff --git a/src/vm/de/unpacker.rs b/src/vm/de/unpacker.rs
new file mode 100644
index 0000000..8b16aa3
--- /dev/null
+++ b/src/vm/de/unpacker.rs
@@ -0,0 +1,518 @@
+// Copyright (C) 2022 Soni L.
+// SPDX-License-Identifier: MIT OR Apache-2.0
+
+//! Unpacker-related parts of the VM.
+
+use std::collections::HashMap;
+use std::collections::hash_map::IntoIter as HMIntoIter;
+
+use serde::de::IntoDeserializer;
+use serde::de::value::StrDeserializer;
+
+use crate::errors::QueryError;
+use crate::vm::Pack;
+
+/// A `Deserializer` for Datafu output.
+///
+/// This converts from Datafu's internal representation (a "pack") into the
+/// desired output type.
+pub struct Unpacker<'pat, 'de> {
+    packs: Vec<Pack<'pat, 'de>>,
+    call_limit: usize,
+}
+
+/// Wrapper for an `&mut Unpacker<'pat, 'de>` with additional field
+/// unpacking logic.
+struct UnpackerFields<'a, 'pat, 'de> {
+    unpacker: &'a mut Unpacker<'pat, 'de>,
+    fields: HMIntoIter<&'static str, Option<crate::vm::SerdeObject<'de>>>,
+    value: Option<crate::vm::SerdeObject<'de>>,
+}
+
+impl<'pat, 'de> Unpacker<'pat, 'de> {
+    /// Creates an Unpacker for unpacking a given Pack.
+    pub fn new(pack: Pack<'pat, 'de>, call_limit: usize) -> Self {
+        // invariant: no empty packs
+        let packs = if pack.subpacks.is_empty() {
+            vec![]
+        } else {
+            vec![pack]
+        };
+        Self {
+            packs, call_limit,
+        }
+    }
+
+    /// Takes the next subpack from the last pack in the pack stack.
+    fn take_next_pack(&mut self) -> Option<Pack<'pat, 'de>> {
+        self.packs.last_mut().and_then(|x| {
+            x.subpacks.front_mut()
+        }).map(|&mut (_, ref mut pack)| {
+            std::mem::take(pack)
+        }).filter(|pack| !pack.subpacks.is_empty())
+    }
+}
+
+impl<'pat, 'de> serde::de::SeqAccess<'de> for Unpacker<'pat, 'de> {
+    type Error = QueryError;
+
+    fn next_element_seed<T: serde::de::DeserializeSeed<'de>>(
+        &mut self,
+        seed: T,
+    ) -> Result<Option<T::Value>, Self::Error> {
+        if self.packs.is_empty() {
+            return Ok(None)
+        }
+        seed.deserialize(self).map(Some)
+    }
+}
+
+impl Drop for UnpackerFields<'_, '_, '_> {
+    fn drop(&mut self) {
+        let unpacker = &mut *self.unpacker;
+        while let Some(mut pack) = unpacker.packs.pop() {
+            pack.subpacks.pop_front();
+            if !pack.subpacks.is_empty() {
+                unpacker.packs.push(pack);
+                break;
+            }
+        }
+    }
+}
+
+impl<'pat, 'de> serde::de::MapAccess<'de> for UnpackerFields<'_, 'pat, 'de> {
+    type Error = QueryError;
+    fn next_key_seed<T: serde::de::DeserializeSeed<'de>>(
+        &mut self,
+        seed: T,
+    ) -> Result<Option<T::Value>, Self::Error> {
+        while let Some((key, value)) = self.fields.next() {
+            if value.is_some() {
+                self.value = value;
+                return seed.deserialize(StrDeserializer::new(key)).map(Some)
+            }
+        }
+        Ok(None)
+    }
+
+    fn next_value_seed<T: serde::de::DeserializeSeed<'de>>(
+        &mut self,
+        seed: T,
+    ) -> Result<T::Value, Self::Error> {
+        if let Some(value) = self.value.take() {
+            seed.deserialize(value.into_deserializer())
+        } else {
+            panic!("broken visitor")
+        }
+    }
+}
+
+impl<'pat, 'de> serde::Deserializer<'de> for &mut Unpacker<'pat, 'de> {
+    type Error = QueryError;
+    fn deserialize_any<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_bool<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_i8<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_i16<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_i32<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_i64<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_u8<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_u16<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_u32<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_u64<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_f32<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_f64<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_char<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_str<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_string<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_bytes<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_byte_buf<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_option<V: serde::de::Visitor<'de>>(
+        self,
+        visitor: V,
+    ) -> Result<V::Value, Self::Error> {
+        todo!()
+    }
+    fn deserialize_unit<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_unit_struct<V>(self, _: &'static str, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_newtype_struct<V>(self, _: &'static str, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_seq<V>(self, visitor: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!(); }
+    fn deserialize_tuple<V>(self, _: usize, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_tuple_struct<V>(self, _: &'static str, _: usize, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_map<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_struct<V>(
+        self,
+        name: &'static str,
+        fields: &'static [&'static str],
+        visitor: V,
+    ) -> Result<V::Value, Self::Error>
+    where
+        V: serde::de::Visitor<'de>,
+    {
+        let _ = name;
+        let mut field_map = fields.iter().copied().map(|n| {
+            (n, None::<crate::vm::SerdeObject<'de>>)
+        }).collect::<HashMap<&'static str, Option<_>>>();
+        // unroll packs
+        while let Some(pack) = self.take_next_pack() {
+            self.packs.push(pack);
+        }
+        // roll them back up
+        'roll: while let Some(pack) = self.packs.pop() {
+            let (ref entries, _) = pack.subpacks[0];
+            for key in entries.keys().copied() {
+                if field_map.contains_key(key) {
+                    self.packs.push(pack);
+                    break 'roll;
+                }
+            }
+            match self.packs.last_mut().map(|x| &mut x.subpacks[0]) {
+                Some((_, subpack)) => {
+                    *subpack = pack;
+                },
+                None => todo!(),
+            }
+        }
+        for pack in self.packs.iter() {
+            let (ref entries, _) = pack.subpacks[0];
+            for (key, value) in entries.iter() {
+                if let Some(entry) = field_map.get_mut(*key) {
+                    *entry = Some(value.clone());
+                }
+            }
+        }
+        visitor.visit_map(UnpackerFields {
+            unpacker: self,
+            fields: field_map.into_iter(),
+            value: None,
+        })
+    }
+    fn deserialize_enum<V>(self, _: &'static str, _: &'static [&'static str], _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_identifier<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_ignored_any<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+}
+
+impl<'pat, 'de> serde::Deserializer<'de> for Unpacker<'pat, 'de> {
+    type Error = QueryError;
+    fn deserialize_any<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_bool<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_i8<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_i16<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_i32<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_i64<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_u8<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_u16<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_u32<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_u64<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_f32<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_f64<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_char<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_str<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_string<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_bytes<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_byte_buf<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_option<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_unit<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_unit_struct<V>(self, _: &'static str, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_newtype_struct<V>(self, _: &'static str, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_seq<V>(self, visitor: V) -> Result<V::Value, Self::Error>
+    where
+        V: serde::de::Visitor<'de>,
+    {
+        visitor.visit_seq(self)
+    }
+    fn deserialize_tuple<V>(self, _: usize, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_tuple_struct<V>(self, _: &'static str, _: usize, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_map<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_struct<V>(
+        self,
+        name: &'static str,
+        fields: &'static [&'static str],
+        visitor: V,
+    ) -> Result<V::Value, Self::Error>
+    where
+        V: serde::de::Visitor<'de>,
+    {
+        todo!()
+    }
+    fn deserialize_enum<V>(self, _: &'static str, _: &'static [&'static str], _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_identifier<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+    fn deserialize_ignored_any<V>(self, _: V) -> Result<V::Value, Self::Error> where V: serde::de::Visitor<'de> { todo!() }
+}
+
+//#[cfg(test)]
+//mod tests {
+//    use serde::Deserialize;
+//    use crate::vm::MAX_CALLS;
+//
+//    /// Mock struct for repo options.
+//    #[derive(Deserialize)]
+//    #[derive(Debug, PartialEq, Eq)]
+//    struct Options {
+//        active: bool,
+//        federate: Option<bool>,
+//        pinned: Option<bool>,
+//    }
+//
+//    /// Mock struct for a project branch.
+//    #[derive(Deserialize)]
+//    #[derive(Debug, PartialEq, Eq)]
+//    struct ProjectBranch {
+//        /// The project commit.
+//        commit: String,
+//        /// The URL to the repo.
+//        url: String,
+//        /// The relevant branch.
+//        branch: String,
+//        /// Branch options.
+//        options: Options,
+//    }
+//
+//    fn get_real_data() -> crate::vm::Pack<'static, 'static> {
+//        use indexmap::indexmap;
+//        use crate::vm::Pack;
+//        use crate::vm::SerdeObject;
+//        use crate::vm::SerdeObject::*;
+//
+//        fn mkstr<'a>(s: &'a str) -> SerdeObject<'a> {
+//            SerdeObject::Str(s.into())
+//        }
+//
+//        Pack {
+//            subpacks: vec![
+//                indexmap!{
+//                    "commit" => (
+//                        Pack {
+//                            subpacks: vec![
+//                                indexmap!{
+//                                    "url" => (
+//                                        Pack {
+//                                            subpacks: vec![
+//                                                indexmap!{
+//                                                    "branch" => (
+//                                                        Pack {
+//                                                            subpacks: vec![
+//                                                                indexmap!{
+//                                                                    "active" => (
+//                                                                        Pack {
+//                                                                            subpacks: vec![].into(),
+//                                                                        },
+//                                                                        Bool(
+//                                                                            true,
+//                                                                        ),
+//                                                                    ),
+//                                                                },
+//                                                            ].into(),
+//                                                        },
+//                                                        mkstr(
+//                                                            "HEAD",
+//                                                        ),
+//                                                    ),
+//                                                },
+//                                            ].into(),
+//                                        },
+//                                        mkstr(
+//                                            "https://github.com/ganarchy/GAnarchy",
+//                                        ),
+//                                    ),
+//                                },
+//                                indexmap!{
+//                                    "url" => (
+//                                        Pack {
+//                                            subpacks: vec![
+//                                                indexmap!{
+//                                                    "branch" => (
+//                                                        Pack {
+//                                                            subpacks: vec![
+//                                                                indexmap!{
+//                                                                    "pinned" => (
+//                                                                        Pack {
+//                                                                            subpacks: vec![].into(),
+//                                                                        },
+//                                                                        Bool(
+//                                                                            true,
+//                                                                        ),
+//                                                                    ),
+//                                                                    "active" => (
+//                                                                        Pack {
+//                                                                            subpacks: vec![].into(),
+//                                                                        },
+//                                                                        Bool(
+//                                                                            true,
+//                                                                        ),
+//                                                                    ),
+//                                                                },
+//                                                            ].into(),
+//                                                        },
+//                                                        mkstr(
+//                                                            "HEAD",
+//                                                        ),
+//                                                    ),
+//                                                },
+//                                            ].into(),
+//                                        },
+//                                        mkstr(
+//                                            "https://soniex2.autistic.space/git-repos/ganarchy.git",
+//                                        ),
+//                                    ),
+//                                },
+//                            ].into(),
+//                        },
+//                        mkstr(
+//                            "385e734a52e13949a7a5c71827f6de920dbfea43",
+//                        ),
+//                    ),
+//                },
+//                indexmap!{
+//                    "commit" => (
+//                        Pack {
+//                            subpacks: vec![
+//                                indexmap!{
+//                                    "url" => (
+//                                        Pack {
+//                                            subpacks: vec![
+//                                                indexmap!{
+//                                                    "branch" => (
+//                                                        Pack {
+//                                                            subpacks: vec![
+//                                                                indexmap!{
+//                                                                    "pinned" => (
+//                                                                        Pack {
+//                                                                            subpacks: vec![].into(),
+//                                                                        },
+//                                                                        Bool(
+//                                                                            true,
+//                                                                        ),
+//                                                                    ),
+//                                                                    "active" => (
+//                                                                        Pack {
+//                                                                            subpacks: vec![].into(),
+//                                                                        },
+//                                                                        Bool(
+//                                                                            true,
+//                                                                        ),
+//                                                                    ),
+//                                                                },
+//                                                            ].into(),
+//                                                        },
+//                                                        mkstr(
+//                                                            "HEAD",
+//                                                        ),
+//                                                    ),
+//                                                },
+//                                            ].into(),
+//                                        },
+//                                        mkstr(
+//                                            "https://soniex2.autistic.space/git-repos/mmorfc.git",
+//                                        ),
+//                                    ),
+//                                },
+//                            ].into(),
+//                        },
+//                        mkstr(
+//                            "a8fb5087f79eafe312db270082c052c427b208c2",
+//                        ),
+//                    ),
+//                },
+//                indexmap!{
+//                    "commit" => (
+//                        Pack {
+//                            subpacks: vec![
+//                                indexmap!{
+//                                    "url" => (
+//                                        Pack {
+//                                            subpacks: vec![
+//                                                indexmap!{
+//                                                    "branch" => (
+//                                                        Pack {
+//                                                            subpacks: vec![
+//                                                                indexmap!{
+//                                                                    "pinned" => (
+//                                                                        Pack {
+//                                                                            subpacks: vec![].into(),
+//                                                                        },
+//                                                                        Bool(
+//                                                                            true,
+//                                                                        ),
+//                                                                    ),
+//                                                                    "active" => (
+//                                                                        Pack {
+//                                                                            subpacks: vec![].into(),
+//                                                                        },
+//                                                                        Bool(
+//                                                                            true,
+//                                                                        ),
+//                                                                    ),
+//                                                                },
+//                                                            ].into(),
+//                                                        },
+//                                                        mkstr(
+//                                                            "HEAD",
+//                                                        ),
+//                                                    ),
+//                                                },
+//                                            ].into(),
+//                                        },
+//                                        mkstr(
+//                                            "https://soniex2.autistic.space/git-repos/chewstuff.git",
+//                                        ),
+//                                    ),
+//                                },
+//                            ].into(),
+//                        },
+//                        mkstr(
+//                            "2d0b363fe3179087de59d9ef4a2d14af21d89071",
+//                        ),
+//                    ),
+//                },
+//            ].into(),
+//        }
+//    }
+//
+//    #[test]
+//    fn to_vec_of_struct() {
+//        let der = super::Unpacker::new(get_real_data(), MAX_CALLS);
+//        let res: Vec<ProjectBranch> = Deserialize::deserialize(der).unwrap();
+//        assert_eq!(res, [
+//            ProjectBranch {
+//                commit: "385e734a52e13949a7a5c71827f6de920dbfea43".into(),
+//                url: "https://github.com/ganarchy/GAnarchy".into(),
+//                branch: "HEAD".into(),
+//                options: Options {
+//                    active: true,
+//                    federate: None,
+//                    pinned: None,
+//                },
+//            },
+//            ProjectBranch {
+//                commit: "385e734a52e13949a7a5c71827f6de920dbfea43".into(),
+//                url: "https://soniex2.autistic.space/git-repos/ganarchy.git".into(),
+//                branch: "HEAD".into(),
+//                options: Options {
+//                    active: true,
+//                    federate: None,
+//                    pinned: Some(true),
+//                },
+//            },
+//            ProjectBranch {
+//                commit: "a8fb5087f79eafe312db270082c052c427b208c2".into(),
+//                url: "https://soniex2.autistic.space/git-repos/mmorfc.git".into(),
+//                branch: "HEAD".into(),
+//                options: Options {
+//                    active: true,
+//                    federate: None,
+//                    pinned: Some(true),
+//                },
+//            },
+//            ProjectBranch {
+//                commit: "2d0b363fe3179087de59d9ef4a2d14af21d89071".into(),
+//                url: "https://soniex2.autistic.space/git-repos/chewstuff.git".into(),
+//                branch: "HEAD".into(),
+//                options: Options {
+//                    active: true,
+//                    federate: None,
+//                    pinned: Some(true),
+//                },
+//            },
+//        ]);
+//    }
+//}
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)
     }
 }