diff options
| -rw-r--r-- | src/pattern.rs | 7 | ||||
| -rw-r--r-- | src/vm/de.rs | 187 | ||||
| -rw-r--r-- | src/vm/mod.rs | 66 |
3 files changed, 175 insertions, 85 deletions
diff --git a/src/pattern.rs b/src/pattern.rs index 6795481..2f7166a 100644 --- a/src/pattern.rs +++ b/src/pattern.rs @@ -50,9 +50,14 @@ impl<O: Serialize> Pattern<O> { &mut frames, //&mut output, ); - let (pack, obj) = vm::Packer::new(interp, MAX_CALLS).deserialize(der)?; + let (mut packs, obj) = vm::Packer::new( + interp, + MAX_CALLS, + ).deserialize(der)?; // this should always be None debug_assert!(obj.is_none()); + debug_assert!(packs.len() == 1); + let pack = packs.pop().unwrap(); let de = De::deserialize(vm::Unpacker::new(pack, MAX_CALLS)); todo!() } diff --git a/src/vm/de.rs b/src/vm/de.rs index 3290ab0..9583962 100644 --- a/src/vm/de.rs +++ b/src/vm/de.rs @@ -52,47 +52,9 @@ impl<'packer, 'pat> FramesMut<'packer, 'pat> { fn iter_active_mut<'a>(&'a mut self) -> impl Iterator<Item=&'a mut Frame<'pat>> where 'packer: 'a { self.iter_mut().filter(|frame| { - frame.matches() + frame.active() }) } - - /// Steps the VM into the next operation. - fn step_in(&mut self) { - self.iter_mut().for_each(|frame| { - if let Some(ref mut overstep) = frame.overstep { - *overstep += 1; - } else { - if !frame.next() { - frame.overstep = Some(1); - } else if matches!( - frame.op(), - PatternElement::ValueSubtree { .. }, - ) { - todo!() - } - } - }); - } - - fn step_out<'de>(&mut self, pack: Pack<'pat, 'de>) -> Pack<'pat, 'de> { - self.iter_mut().for_each(|frame| { - if let Some(ref mut overstep) = frame.overstep { - if *overstep > 0 { - *overstep -= 1; - } - } else { - if let Some(0) = frame.overstep { - frame.overstep = None; - } - if frame.overstep.is_none() { - if frame.prev() { - todo!(); - } - } - } - }); - pack - } } impl<'packer, 'pat> Frames<'packer, 'pat> { @@ -102,7 +64,7 @@ impl<'packer, 'pat> Frames<'packer, 'pat> { fn iter_active<'a>(&'a self) -> impl Iterator<Item=&'a Frame<'pat>> where 'packer: 'a { self.iter().filter(|frame| { - frame.matches() + frame.active() }) } } @@ -131,33 +93,118 @@ impl<'pat, 'state, 'de, O: Serialize> Packer<'pat, 'state, O> { frames: &*self.interp.frames, } } -} -// what steps do we have to take? -// -// 1. figure out what type we need to deserialize (and ask the deserializer -// for it). -// 2. visit value. figure out whether we need to store it or not? -// 3. if we need to store it how do we figure out *where* to store it? -// 4. if we *don't* need to store it, what do we do? -// 5. how do we tell if we do or don't need to store it? how do we propagate -// those requirements deeper into the Deserialize's and how do we bring -// the values back out (recursively?) to parent Deserialize's, without -// wasting time storing things we don't actually care about? -// 5.a. just have a flag in the DeserializeSeed for whether to capture the -// values. propagation is more or less trivial from there. -// 6. how do you handle value subtrees? -// 6.a. you don't. for now. -// 7. how do you handle errors? -// 7.a. put them into a "state" and raise a D::Error::custom. then -// override it in the relevant Pattern call. + /// Steps the VM into the next operation. + fn step_in(&mut self) { + // iterate up to the *live* length (i.e. the loop is allowed to modify + // the length). + // NOTE: we need to use while-let so as to not borrow anything in an + // iterator. filtering happens on the *result* of the iterator. + let mut index_iter = 0..; + while let Some(index) = index_iter.next().filter(|&i| { + i < self.interp.frames.len() + }) { + let frame = &mut self.interp.frames[index]; + if frame.overstep > 0 || !frame.matches { + // overstepped and non-matching frames + frame.overstep += 1; + } else { + if !frame.next() { + // empty/end-of frames + // 1 layer of step-in. + // step-out will undo this. + // this is correct because this branch implies overstep = 0 + frame.overstep = 1; + } else if matches!( + frame.op(), + PatternElement::SubtreeMarker, + ) { + // subtrees! + // these are tricky, because the current frame can be moved + // in memory. so we have to use indexing every time. + // tho first we set it as overstep because it has special + // handling. + frame.overstep = 1; + let mut at = index + 1; + while self.interp.frames[index].next() { + let op = self.interp.frames[index].op(); + if let PatternElement::ValueSubtree { + index: subtree, .. + } = op { + let new_frame = Frame { + ops: &self.interp.pat.protos[subtree][..], + iar: None, + overstep: 0, + matches: true, + }; + // we want the "newest" frame last, so it is + // easier to unwind back. + self.interp.frames.insert(at, new_frame); + at += 1; + } else { + unreachable!() + } + } + } + } + } + } + + /// Steps the VM back into the previous operation. + fn step_out( + &mut self, + mut packs: Vec<Pack<'pat, 'de>>, + ) -> Vec<Pack<'pat, 'de>> { + let mut index_iter = 0..; + while let Some(index) = index_iter.next().filter(|&i| { + i < self.interp.frames.len() + }) { + // iterate backwards + let index = self.interp.frames.len() - index - 1; + let frame = &mut self.interp.frames[index]; + if frame.overstep > 0 { + // handle overstep + frame.overstep -= 1; + } else { + // unwind frame + if frame.prev() { + // successfully unwound. do nothing. + } else { + // find parent frame. + let mut count = 1; + let mut target = index; + while count > 0 && target > 0 { + target -= 1; + match self.interp.frames[target].num_subtrees() { + Some(num) if num <= count => { + count -= num; + }, + Some(num) => { + count = 0; + }, + None => { + count += 1; + }, + } + } + if count == 0 { + // has parent frame + let pack = packs.remove(index); + todo!("merge packs") + } + } + } + } + packs + } +} impl<'pat, 'state, 'de, O> serde::de::DeserializeSeed<'de> for &mut Packer<'pat, 'state, O> where O: Serialize, { - type Value = (Pack<'pat, 'de>, Option<SerdeObject<'de>>); + type Value = (Vec<Pack<'pat, 'de>>, Option<SerdeObject<'de>>); fn deserialize<D>( mut self, deserializer: D, @@ -165,7 +212,7 @@ where where D: serde::Deserializer<'de> { - self.frames_mut().step_in(); + self.step_in(); let pat = self.interp.pat; let target_type = self.frames().iter_active().fold( Type::IgnoredAny, @@ -248,7 +295,7 @@ where Type::Enum { name, variants } => { deserializer.deserialize_enum(name, variants, &mut *self) }, - }.map(|(pack, obj)| (self.frames_mut().step_out(pack), obj)) + }.map(|(packs, obj)| (self.step_out(packs), obj)) } } @@ -265,16 +312,18 @@ macro_rules! vs { if self.collecting { obj = Some(SerdeObject::$obj(v)); } - let mut pack = Pack::default(); + let mut packs = Vec::new(); self.frames_mut().iter_active_mut().try_for_each(|frame| { + let mut pack = Pack::default(); let mut map = IndexMap::new(); if let Some(name) = frame.get_name(pat) { map.insert(name, (Pack::default(), SerdeObject::$obj(v))); } pack.subpacks.push(map); + packs.push(pack); Ok(()) })?; - Ok((pack, obj)) + Ok((packs, obj)) } } } @@ -284,7 +333,7 @@ for &mut Packer<'pat, 'state, O> where O: Serialize, { - type Value = (Pack<'pat, 'de>, Option<SerdeObject<'de>>); + type Value = (Vec<Pack<'pat, 'de>>, Option<SerdeObject<'de>>); fn expecting(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "unsure") } @@ -390,6 +439,7 @@ where { // FIXME subtrees let mut obj = None; + let mut packs = Vec::new(); let mut pack = Pack::default(); if self.collecting { obj = Some(SerdeObject::Unit); @@ -399,7 +449,8 @@ where // map.insert(name, (Default::default(), SerdeObject::Unit)); //} pack.subpacks.push(map); - Ok((pack, obj)) + packs.push(pack); + Ok((packs, obj)) } fn visit_newtype_struct<D>( self, @@ -633,9 +684,9 @@ mod tests { let mut frames = Default::default(); let interp = Interpreter::new(&consts, &mut err, &mut frames); let packed = Packer::new(interp, MAX_CALLS).deserialize(&mut der); - let (pack, obj) = packed.unwrap(); + let (packs, obj) = packed.unwrap(); assert!(obj.is_none()); - assert_eq!(pack.subpacks[0]["hello"].1, SerdeObject::U64(3)); + assert_eq!(packs[0].subpacks[0]["hello"].1, SerdeObject::U64(3)); } } diff --git a/src/vm/mod.rs b/src/vm/mod.rs index 8122778..dca15a9 100644 --- a/src/vm/mod.rs +++ b/src/vm/mod.rs @@ -95,6 +95,8 @@ pub(crate) enum PatternElement { /// expected value of this entry. name_and_value: These<usize, Value>, }, + /// Marks the end of pattern iteration and the start of subtrees (if any). + SubtreeMarker, /// A value subtree is a subtree for values. /// /// It is applied *after* tags, and thus any value subtrees come last in @@ -102,10 +104,10 @@ pub(crate) enum PatternElement { ValueSubtree { /// The proto index of the subtree. index: usize, - /// Whether to allow this value subtree to produce no results. + /// Whether to allow this value subtree to match nothing. /// /// By default, a datafu pattern only matches a tree if every branch of - /// the tree produces results. This enables opting out of that. + /// the tree matches something. This enables opting out of that. optional: bool, }, } @@ -292,15 +294,16 @@ pub(crate) enum SerdeObject<'de> { } impl<'de> SerdeObject<'de> { - fn check<E: serde::de::Error>(self, ty: Option<Type>) -> Result<Self, E> { + /// Checks the type of this object. + fn check<E: serde::de::Error>(&self, ty: Option<Type>) -> Result<(), E> { let ty = match ty { - None => return Ok(self), + None => return Ok(()), Some(ty) => ty, }; match (ty, self) { | (Type::Any, v) | (Type::IgnoredAny, v) - => Ok(v), + => Ok(()), | (Type::Bool, v @ SerdeObject::Bool(_)) | (Type::I8, v @ SerdeObject::I8(_)) | (Type::I16, v @ SerdeObject::I16(_)) @@ -324,7 +327,7 @@ impl<'de> SerdeObject<'de> { | (Type::Unit, v @ SerdeObject::Unit) | (Type::Seq, v @ SerdeObject::Seq(_)) | (Type::Map, v @ SerdeObject::Map(_)) - => Ok(v), + => Ok(()), _ => todo!(), } } @@ -358,8 +361,6 @@ pub(crate) struct Interpreter<'pat, 'state, O: Serialize> { error: &'state mut Option<crate::errors::MatchError>, /// The current interpreter frames. frames: &'state mut Vec<Frame<'pat>>, - ///// The final output. - //output: &'state Cell<Pack<'pat, 'de>>, } pub(crate) struct Frame<'pat> { @@ -367,10 +368,12 @@ pub(crate) struct Frame<'pat> { ops: &'pat [PatternElement], /// The instruction index being processed. iar: Option<usize>, - /// How many steps this frame has failed to match. - overstep: Option<usize>, - ///// Elements collected while processing this frame? - //path: Pack<'pat, 'de>, + /// How many steps this frame has not actually advanced for. + /// + /// This is used at end of frame and on match failure. + overstep: usize, + /// Whether this frame matches the data so far. + matches: bool, } impl<'pat, 'state, O: Serialize> Interpreter<'pat, 'state, O> { @@ -384,7 +387,8 @@ impl<'pat, 'state, O: Serialize> Interpreter<'pat, 'state, O> { frames.push(Frame { ops: &pat.protos[0], iar: None, - overstep: None, + overstep: 0, + matches: true, //path: Default::default(), }); Self { @@ -461,12 +465,42 @@ impl<'pat> Frame<'pat> { /// /// Panics if called on a non-matching frame or if iteration hasn't begun. fn op(&self) -> PatternElement { - assert!(self.matches(), "op() called on non-matching frame"); + assert!(self.active(), "op() called on inactive frame"); + self.ops[self.iar.expect("ops[iar]")] + } + + /// Counts the number of *active* subtrees, if any. + /// + /// # Panics + /// + /// Panics if iteration hasn't begun. + fn num_subtrees(&self) -> Option<usize> { + let iar = self.iar.expect("iar"); + // check if there are any subtrees + matches!( + self.ops[iar], + | PatternElement::ValueSubtree { .. } + | PatternElement::SubtreeMarker + ).then(|| { + // count the number of subtrees + self.ops[0..=iar].iter().rev().take_while(|x| { + matches!(x, PatternElement::ValueSubtree { .. }) + }).count() + }) + } + + /// Returns the raw instruction. + /// + /// # Panics + /// + /// Panics if iteration hasn't begun. + fn raw_op(&self) -> PatternElement { self.ops[self.iar.expect("ops[iar]")] } - fn matches(&self) -> bool { - self.overstep.is_none() + /// Returns whether this frame is active (not overstepped). + fn active(&self) -> bool { + self.overstep == 0 } /// Rewinds the instruction address register. |