Implement Packer::visit_map

2 files changed, 191 insertions, 55 deletions

diff --git a/src/vm/de.rs b/src/vm/de.rs
index 5994984..a4efad5 100644
--- a/src/vm/de.rs
+++ b/src/vm/de.rs
@@ -24,6 +24,7 @@ use super::PatternElement;
 use super::SerdeObject;
 use super::Type;
 use super::Value;
+use crate::errors::MatchError;
 
 /// A `DeserializeSeed` for Datafu input.
 ///
@@ -46,11 +47,21 @@ struct Frames<'packer, 'pat> {
 }
 
 impl<'packer, 'pat> FramesMut<'packer, 'pat> {
-    fn iter_mut<'a>(&'a mut self) -> impl Iterator<Item=&'a mut Frame<'pat>> where 'packer: 'a {
+    fn iter_mut<'a>(
+        &'a mut self,
+    ) -> impl Iterator<Item=&'a mut Frame<'pat>> + DoubleEndedIterator
+    where
+        'packer: 'a,
+    {
         self.frames.iter_mut()
     }
 
-    fn iter_active_mut<'a>(&'a mut self) -> impl Iterator<Item=&'a mut Frame<'pat>> where 'packer: 'a {
+    fn iter_active_mut<'a>(
+        &'a mut self,
+    ) -> impl Iterator<Item=&'a mut Frame<'pat>> + DoubleEndedIterator
+    where
+        'packer: 'a,
+    {
         self.iter_mut().filter(|frame| {
             frame.active()
         })
@@ -58,11 +69,21 @@ impl<'packer, 'pat> FramesMut<'packer, 'pat> {
 }
 
 impl<'packer, 'pat> Frames<'packer, 'pat> {
-    fn iter<'a>(&'a self) -> impl Iterator<Item=&'a Frame<'pat>> where 'packer: 'a {
+    fn iter<'a>(
+        &'a self,
+    ) -> impl Iterator<Item=&'a Frame<'pat>> + DoubleEndedIterator
+    where
+        'packer: 'a,
+    {
         self.frames.iter()
     }
 
-    fn iter_active<'a>(&'a self) -> impl Iterator<Item=&'a Frame<'pat>> where 'packer: 'a {
+    fn iter_active<'a>(
+        &'a self,
+    ) -> impl Iterator<Item=&'a Frame<'pat>> + DoubleEndedIterator
+    where
+        'packer: 'a,
+    {
         self.iter().filter(|frame| {
             frame.active()
         })
@@ -99,7 +120,7 @@ impl<'pat, 'state, 'de, O: Serialize> Packer<'pat, 'state, O> {
         if self.call_limit > 0 {
             self.call_limit -= 1;
         } else {
-            self.interp.error.insert(crate::errors::MatchError::StackOverflow);
+            self.interp.error.insert(MatchError::StackOverflow);
             return Err(todo!());
         }
         // iterate up to the *live* length (i.e. the loop is allowed to modify
@@ -359,29 +380,40 @@ macro_rules! vs {
                 obj = Some(SerdeObject::$obj$v);
             }
             let mut packs = Vec::new();
-            $this.frames_mut().iter_active_mut().try_for_each(|frame| {
-                let ty = frame.get_type();
-                match ty {
-                    | Some(($data_type, _))
-                    | Some((Type::Any, _))
-                    | Some((Type::IgnoredAny, _))
-                    | None
-                    => {},
-                    Some((_, false)) => {
-                        frame.matches = false;
-                        return Ok(());
-                    },
-                    Some((_, true)) => return Err(todo!()),
-                }
-                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);
-                }
-                packs.push(pack);
-                Ok(())
-            })?;
+            let result = {
+                $this.frames_mut().iter_active_mut().try_for_each(|frame| {
+                    let ty = frame.get_type();
+                    match ty {
+                        | Some(($data_type, _))
+                        | Some((Type::Any, _))
+                        | Some((Type::IgnoredAny, _))
+                        | None
+                        => {},
+                        Some((_, false)) => {
+                            frame.matches = false;
+                            return Ok(());
+                        },
+                        Some((_, true)) => {
+                            return Err(MatchError::ValidationError)
+                        },
+                    }
+                    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);
+                    }
+                    packs.push(pack);
+                    Ok(())
+                })
+            };
+            match result {
+                Err(e) => {
+                    $this.interp.error.insert(e);
+                    return Err(todo!());
+                },
+                _ => (),
+            }
             Ok((packs, obj))
         }
     };
@@ -501,13 +533,15 @@ where
                 | Some((Type::Map, _))
                 | Some((Type::Any, _))
                 | Some((Type::IgnoredAny, _))
+                | None
                 => {},
                 Some((_, false)) => {
                     frame.matches = false;
-                    todo!()
+                    return Ok(());
+                },
+                Some((_, true)) => {
+                    return Err(MatchError::ValidationError)
                 },
-                Some((_, true)) => return Err(todo!()),
-                None => unreachable!(),
             }
             if frame.get_name(pat).is_some() {
                 collecting = true;
@@ -518,20 +552,17 @@ where
         self.collecting = collecting;
         let mut subframes = Vec::new();
         self.frames().iter_active().for_each(|frame| {
-            if let PatternElement::Tag { key_subtree } = frame.op() {
-                if let Some(key_subtree) = key_subtree {
-                    subframes.push(Frame {
-                        ops: &pat.protos[key_subtree],
-                        iar: None,
-                        overstep: 0,
-                        matches: true,
-                    });
-                }
-            } else {
-                unreachable!()
+            if let Some(key_subtree) = frame.key_subtree() {
+                subframes.push(Frame {
+                    ops: &pat.protos[key_subtree],
+                    iar: None,
+                    overstep: 0,
+                    matches: true,
+                });
             }
         });
         let mut obj_inner = Vec::new();
+        let mut output_packs = Vec::new();
         while let Some(packed_key) = {
             let subinterp = Interpreter {
                 pat: pat,
@@ -546,30 +577,113 @@ where
             map.next_key_seed(&mut subpacker)?
         } {
             self.frames_mut().iter_active_mut().filter(|frame| {
-                if let PatternElement::Tag { key_subtree } = frame.op() {
-                    key_subtree.is_some()
-                } else {
-                    unreachable!()
-                }
+                frame.key_subtree().is_some()
             }).zip(&mut subframes).for_each(|(frame, subframe)| {
                 frame.matches = subframe.matches;
                 // reset subframe for next iteration
-                subframe.matches = true;
+                // 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 packed_value = map.next_value_seed(&mut *self)?;
             if self.collecting {
                 obj_inner.push(
                     (packed_key.1.unwrap(), packed_value.1.unwrap()),
                 );
             }
-            todo!("merge vecs of packs");
-            //let mut merge_pack = packed_key.0;
-            //let value_pack = packed_value.0;
-            //merge_pack.merge_from(value_pack);
-            //dbg!(merge_pack);
+            let mut key_packs_per_frame = packed_key.0.into_iter();
+            let mut value_packs_per_frame = packed_value.0;
+            // 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 value_packs_per_frame
+            let mut pack_index = 0;
+            for frame in self.frames().iter_active() {
+                // 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
+                };
+                if frame.matches && subframe.is_some() {
+                    // this already implies subframe.matches
+                    let key_pack = key_packs_per_frame.next().unwrap();
+                    let value_pack = &mut value_packs_per_frame[pack_index];
+                    key_pack.merge_into(value_pack);
+                    pack_index += 1;
+                } else if frame.matches {
+                    // value matches but there's no subframe, carry on
+                    pack_index += 1;
+                } 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 output_packs.is_empty() {
+                output_packs = value_packs_per_frame;
+            } else {
+                for (left, right) in output_packs.iter_mut().zip(
+                    value_packs_per_frame,
+                ) {
+                    left.subpacks.extend(right.subpacks)
+                }
+            }
         }
-        todo!();
+        let obj = SerdeObject::Map(obj_inner);
+        let mut final_packs = self.step_out(output_packs);
+        let mut iter_final_packs = final_packs.iter_mut();
+        self.frames_mut().iter_active_mut().zip({
+            final_packs.iter_mut()
+        }).for_each(|(frame, pack)| {
+            let ty = frame.get_type();
+            match ty {
+                | Some((Type::Map, _))
+                | Some((Type::Any, _))
+                | Some((Type::IgnoredAny, _))
+                | None
+                => {
+                    frame.matches = true;
+                },
+                _ => return,
+            }
+            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, (old_pack, obj.clone()));
+                pack.subpacks.push(map);
+            }
+        });
+        self.collecting = old_collecting;
+        Ok((final_packs, collecting.then(|| obj)))
     }
     fn visit_enum<A>(self, data: A) -> Result<Self::Value, A::Error>
     where
diff --git a/src/vm/mod.rs b/src/vm/mod.rs
index dca9faa..8f20aae 100644
--- a/src/vm/mod.rs
+++ b/src/vm/mod.rs
@@ -353,8 +353,17 @@ pub struct Pack<'pat, 'de> {
 }
 
 impl<'pat, 'de> Pack<'pat, 'de> {
+    /// Merges two packs, with elements from `other` coming after `self`.
     fn merge_from(&mut self, mut other: Self) {
-        todo!("merge packs");
+        for (left, right) in self.subpacks.iter_mut().zip(other.subpacks) {
+            left.extend(right)
+        }
+    }
+
+    /// Same as `merge_from` but borrows `other` instead of `self`.
+    fn merge_into(mut self, other: &mut Self) {
+        std::mem::swap(&mut self, other);
+        other.merge_from(self);
     }
 }
 
@@ -499,6 +508,19 @@ impl<'pat> Frame<'pat> {
         })
     }
 
+    /// Returns whether this key has a subtree.
+    ///
+    /// # 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!()
+        }
+    }
+
     /// Returns the raw instruction.
     ///
     /// # Panics