diff options
| -rw-r--r-- | src/pattern.rs | 15 | ||||
| -rw-r--r-- | src/type_tree.rs | 112 | ||||
| -rw-r--r-- | src/vm/de.rs | 259 | ||||
| -rw-r--r-- | src/vm/mod.rs | 181 |
4 files changed, 285 insertions, 282 deletions
diff --git a/src/pattern.rs b/src/pattern.rs index 0fc6acd..a0c0ec3 100644 --- a/src/pattern.rs +++ b/src/pattern.rs @@ -42,9 +42,18 @@ impl<O: Serialize> Pattern<O> { De: Deserialize<'de>, { let mut err = Default::default(); - let interp = vm::Interpreter::new(&self.consts, &mut err); - let pack = vm::Packer::new(interp, MAX_CALLS).deserialize(der)?; - let de = De::deserialize(vm::Unpacker::new(pack.0, MAX_CALLS)); + let frames = Default::default(); + //let mut output = Default::default(); + let interp = vm::Interpreter::new( + &self.consts, + &mut err, + &frames, + //&mut output, + ); + let (pack, obj) = vm::Packer::new(interp, MAX_CALLS).deserialize(der)?; + // this should always be None + debug_assert!(obj.is_none()); + let de = De::deserialize(vm::Unpacker::new(pack, MAX_CALLS)); todo!() } } diff --git a/src/type_tree.rs b/src/type_tree.rs deleted file mode 100644 index e7389d5..0000000 --- a/src/type_tree.rs +++ /dev/null @@ -1,112 +0,0 @@ -// Copyright (C) 2022 Soni L. -// SPDX-License-Identifier: MIT OR Apache-2.0 - -//! Type Tree support. -//! -//! Type Trees are a Datafu feature for extracting types from a `serde`-based -//! `Deserialize` in such a way that it can be used with Datafu patterns. -//! -//! They work by matching the `Deserialize` against some data, with the help of -//! `serde_transmute`. Datafu then collects the relevant `Deserialize` calls, -//! and uses them to infer an appropriate type tree for dynamic -//! deserialization. -//! -//! When introspecting the `Deserialize`, all matching parts are extracted, and -//! non-matching parts are ignored. Even if an error occurs, Datafu will gladly -//! infer a type tree for what it could match. -//! -//! For example, given a struct and the corresponding data: -//! -//! ``` -//! struct Foo { -//! bar: i32, -//! } -//! -//! let data = Foo { bar: 0 }; -//! ``` -//! -//! Building a type tree will first inspect the struct like so: -//! -//! 1. call `deserialize()` on `Foo`. -//! 2. inspect the `deserialize_struct` from `Foo`, storing the name and -//! fields. -//! 3. give `Foo` the appropriate visitor (from `data`), through -//! `serde_transmute`. -//! 4. inspect the `deserialize_i32` etc, also storing those. -//! -//! The resulting type tree can then be used in any pattern to effectively -//! match a `Foo`, but more efficiently than with a predicate. Another big -//! difference between predicates and type trees is how predicates are eager, -//! and can consume values that would otherwise be matched by the rest of a -//! pattern, like `IgnoredAny`. -//! -//! Type trees are pretty flexible. Consider the following example: -//! -//! ``` -//! struct Foo { -//! bar: Vec<u32>, -//! } -//! -//! let data = Foo { bar: vec![1, 2, 3] }; -//! ``` -//! -//! This will actually produce a type tree which checks that the first 3 items -//! are `u32`! Further, when using different types for the predicate and the -//! data, you can get even more flexiblity. For example, with the following -//! struct and data: -//! -//! ``` -//! struct Foo { -//! bar: Vec<u32>, -//! } -//! -//! let data = (); -//! ``` -//! -//! Datafu will actually inspect the `deserialize_struct`, and then the -//! struct visitor will error. But despite the error, it'll still create a type -//! tree for the `deserialize_struct`! - -// use serde::Deserializer; - -// /// A deserializer which attempts to fill in a type tree. -// struct TypeTreeDeserializer<'tt, D> { -// inner: D, -// tt: &'tt mut TypeTreeNode, -// } - -/// A Type Tree entry type. -/// -/// This represents a type to be deserialized with Serde, with everything that -/// comes with that. It supports the 29 core Serde types, and 2 self-describing -/// ones. -#[derive(Clone, Debug, PartialEq, Eq, Hash, Default)] -pub enum TypeTreeType { - /// An open type, which can be anything. - /// - /// This represents [`Deserializer::deserialize_any`]. - #[default] - Any, - /// A type for a value which will be ignored. - /// - /// This represents [`Deserializer::deserialize_ignored_any`]. - IgnoredAny, - Bool, -} - -/// A node of a type tree. -#[derive(Clone, Debug, PartialEq, Eq, Hash, Default)] -pub struct TypeTreeNode { - /// The type to be requested for this node. - pub node_type: TypeTreeType, - /// The types for when this node is an enum. - pub enum_nodes: (), // TODO - /// The types for when this node is a map. - pub map_nodes: (), // TODO - /// The types for when this node is a seq. - pub seq_nodes: (), // TODO - /// The type for when this node is a some. - pub some_node: Option<Box<TypeTreeNode>>, - /// The type for when this node is a newtype struct. - pub newtype_node: Option<Box<TypeTreeNode>>, -} diff --git a/src/vm/de.rs b/src/vm/de.rs index 2282484..640b1aa 100644 --- a/src/vm/de.rs +++ b/src/vm/de.rs @@ -10,11 +10,13 @@ use indexmap::IndexMap; use serde::Serialize; use serde::de::Error as _; +use serde::de::IntoDeserializer as _; use smallvec::SmallVec; use these::These; +use super::Frame; use super::Interpreter; use super::Pack; use super::PatternConstants; @@ -33,56 +35,63 @@ pub(crate) struct Packer<'pat, 'state, O: Serialize> { call_limit: usize, /// Whether we're collecting values. collecting: bool, - /// Instructions currently being processed. - ops: SmallVec<[InstructionReg<'pat>; 1]>, } -/// Instruction currently being processed. -struct InstructionReg<'pat> { - /// The (current) program sequence. - instructions: &'pat [PatternElement], - /// Whether this instruction is required to match. - required: bool, +struct FramesMut<'packer, 'pat> { + frames: std::cell::RefMut<'packer, Vec<Frame<'pat>>>, +} + +struct Frames<'packer, 'pat> { + frames: std::cell::Ref<'packer, Vec<Frame<'pat>>>, +} + +impl<'packer, 'pat> FramesMut<'packer, 'pat> { + fn iter_mut<'a>(&'a mut self) -> impl Iterator<Item=&'a mut Frame<'pat>> 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 { + self.iter_mut().filter(|frame| { + frame.matches + }) + } +} + +impl<'packer, 'pat> Frames<'packer, 'pat> { + fn iter<'a>(&'a self) -> impl Iterator<Item=&'a Frame<'pat>> where 'packer: 'a { + self.frames.iter() + } + + fn iter_active<'a>(&'a self) -> impl Iterator<Item=&'a Frame<'pat>> where 'packer: 'a { + self.iter().filter(|frame| { + frame.matches + }) + } } impl<'pat, 'state, 'de, O: Serialize> Packer<'pat, 'state, O> { + /// Creates a new Packer. pub(crate) fn new( interp: Interpreter<'pat, 'state, O>, call_limit: usize, ) -> Self { - let ops = SmallVec::from_buf([ - InstructionReg { - instructions: &interp.pat.protos.last().unwrap()[..], - required: true, - } - ]); Self { interp: interp, call_limit: call_limit, collecting: false, - ops: ops, } } - /// Extracts the name for this element. - fn get_name(&self) -> SmallVec<[&'pat str; 1]> { - let mut name = SmallVec::<[&'pat str; 1]>::new(); - for reg in &self.ops { - match reg.instructions.first() { - | Some(PatternElement::Tag { name_and_value, .. }) - | Some(PatternElement::Value { name_and_value }) - => { - if let Some(name_key) = name_and_value.here() { - name.push(&self.interp.pat.strings[name_key]); - } - }, - None => { - // FIXME is this correct? - }, - _ => unreachable!(), - } + fn frames_mut(&mut self) -> FramesMut<'_, 'pat> { + FramesMut { + frames: self.interp.frames.borrow_mut(), + } + } + + fn frames(&mut self) -> Frames<'_, 'pat> { + Frames { + frames: self.interp.frames.borrow(), } - name } } @@ -118,67 +127,85 @@ where where D: serde::Deserializer<'de> { - match &*self.ops { - [] => unreachable!(), - [InstructionReg { - instructions: [], - .. - }] => { - // FIXME is this correct? - deserializer.deserialize_ignored_any(self) + self.frames_mut().iter_mut().for_each(|frame| { + if !frame.next() { + frame.matches = false; + } + }); + let pat = self.interp.pat; + let target_type = self.frames().iter_active().fold( + Type::IgnoredAny, + |target_type, frame| { + match (target_type, frame.get_type(pat)) { + (Type::IgnoredAny, Some((ty, _))) => ty, + (ty, Some((Type::IgnoredAny, _))) => ty, + (Type::String, Some((Type::Str, _))) => { + Type::String + }, + (Type::Str, Some((Type::String, _))) => { + Type::String + }, + (Type::Bytes, Some((Type::ByteBuf, _))) => { + Type::ByteBuf + }, + (Type::ByteBuf, Some((Type::Bytes, _))) => { + Type::ByteBuf + }, + (left, Some((right, _))) if left == right => { + left + }, + _ => Type::Any, + } + }, + ); + match target_type { + Type::Any => deserializer.deserialize_any(self), + Type::IgnoredAny => deserializer.deserialize_ignored_any(self), + Type::Bool => deserializer.deserialize_bool(self), + Type::I8 => deserializer.deserialize_i8(self), + Type::I16 => deserializer.deserialize_i16(self), + Type::I32 => deserializer.deserialize_i32(self), + Type::I64 => deserializer.deserialize_i64(self), + Type::I128 => deserializer.deserialize_i128(self), + Type::U8 => deserializer.deserialize_u8(self), + Type::U16 => deserializer.deserialize_u16(self), + Type::U32 => deserializer.deserialize_u32(self), + Type::U64 => deserializer.deserialize_u64(self), + Type::U128 => deserializer.deserialize_u128(self), + Type::F32 => deserializer.deserialize_f32(self), + Type::F64 => deserializer.deserialize_f64(self), + Type::Char => deserializer.deserialize_char(self), + Type::Str if !self.collecting => { + deserializer.deserialize_str(self) + }, + Type::Str | Type::String => deserializer.deserialize_string(self), + Type::Bytes if !self.collecting => { + deserializer.deserialize_bytes(self) + }, + Type::Bytes | Type::ByteBuf => { + deserializer.deserialize_byte_buf(self) + }, + Type::Option => deserializer.deserialize_option(self), + Type::Unit => deserializer.deserialize_unit(self), + Type::Seq => deserializer.deserialize_seq(self), + Type::Map => deserializer.deserialize_map(self), + Type::Identifier => deserializer.deserialize_identifier(self), + Type::Tuple(len) => deserializer.deserialize_tuple(len, self), + Type::UnitStruct(name) => { + deserializer.deserialize_unit_struct(name, self) + }, + Type::NewtypeStruct(name) => { + deserializer.deserialize_newtype_struct(name, self) }, - [InstructionReg { - instructions: [ins, ..], - .. - }] => match ins { - | PatternElement::Tag { name_and_value, .. } - | PatternElement::Value { name_and_value } - => { - match name_and_value.there() { - | Some(Value::String { .. }) - | Some(Value::Regex { .. }) => { - if name_and_value.is_here() { - deserializer.deserialize_string(self) - } else { - deserializer.deserialize_str(self) - } - }, - Some(Value::Type { ty, .. }) => match ty { - Type::Any => deserializer.deserialize_any(self), - Type::IgnoredAny => { - deserializer.deserialize_ignored_any(self) - }, - Type::Bool => deserializer.deserialize_bool(self), - Type::I8 => deserializer.deserialize_i8(self), - Type::I16 => deserializer.deserialize_i16(self), - Type::I32 => deserializer.deserialize_i32(self), - Type::I64 => deserializer.deserialize_i64(self), - Type::I128 => deserializer.deserialize_i128(self), - Type::U8 => deserializer.deserialize_u8(self), - Type::U16 => deserializer.deserialize_u16(self), - Type::U32 => deserializer.deserialize_u32(self), - Type::U64 => deserializer.deserialize_u64(self), - Type::U128 => deserializer.deserialize_u128(self), - Type::F32 => deserializer.deserialize_f32(self), - Type::F64 => deserializer.deserialize_f64(self), - Type::Char => deserializer.deserialize_char(self), - Type::Str => deserializer.deserialize_str(self), - Type::String => deserializer.deserialize_string(self), - Type::Bytes => deserializer.deserialize_bytes(self), - Type::ByteBuf => { - deserializer.deserialize_byte_buf(self) - }, - Type::Option => deserializer.deserialize_option(self), - Type::Unit => deserializer.deserialize_unit(self), - Type::Seq => deserializer.deserialize_seq(self), - Type::Map => deserializer.deserialize_map(self), - }, - None => todo!(), - } - }, - _ => todo!(), + Type::TupleStruct { name, len } => { + deserializer.deserialize_tuple_struct(name, len, self) + }, + Type::Struct { name, fields } => { + deserializer.deserialize_struct(name, fields, self) + }, + Type::Enum { name, variants } => { + deserializer.deserialize_enum(name, variants, self) }, - _ => todo!(), } } } @@ -186,21 +213,25 @@ where /// visit method generator for simple values (primitives). macro_rules! vs { ($visit:ident $obj:ident $t:ty) => { - fn $visit<E>(self, v: $t) -> Result<Self::Value, E> + fn $visit<E>(mut self, v: $t) -> Result<Self::Value, E> where E: serde::de::Error, { - // FIXME subtrees + // FIXME filtering/errors + let pat = self.interp.pat; let mut obj = None; - let mut pack = Pack::default(); if self.collecting { obj = Some(SerdeObject::$obj(v)); } - let mut map = IndexMap::new(); - for name in self.get_name() { - map.insert(name, (Default::default(), SerdeObject::$obj(v))); - } - pack.subpacks.push(map); + let mut pack = Pack::default(); + self.frames_mut().iter_active_mut().try_for_each(|frame| { + 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); + Ok(()) + })?; Ok((pack, obj)) } } @@ -322,9 +353,9 @@ where obj = Some(SerdeObject::Unit); } let mut map = IndexMap::new(); - for name in self.get_name() { - map.insert(name, (Default::default(), SerdeObject::Unit)); - } + //for name in self.get_name() { + // map.insert(name, (Default::default(), SerdeObject::Unit)); + //} pack.subpacks.push(map); Ok((pack, obj)) } @@ -473,12 +504,14 @@ where SerdeObject::Str(Cow::Borrowed(x)) => v.visit_borrowed_str(x), SerdeObject::Bytes(Cow::Owned(x)) => v.visit_byte_buf(x), SerdeObject::Bytes(Cow::Borrowed(x)) => v.visit_borrowed_bytes(x), - SerdeObject::Some(x) => todo!(), + 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::NewtypeStruct(x) => todo!(), + SerdeObject::NewtypeStruct(x) => { + v.visit_newtype_struct(x.into_deserializer()) + }, SerdeObject::Enum { variant, data } => todo!(), } } @@ -515,7 +548,8 @@ mod tests { fn test_broken() { let consts = PatternConstants::<()>::default(); let mut err = Default::default(); - let interp = Interpreter::new(&consts, &mut err); + let frames = Default::default(); + let interp = Interpreter::new(&consts, &mut err, &frames); let _ = Packer::new(interp, MAX_CALLS); } @@ -524,7 +558,8 @@ mod tests { let mut consts = PatternConstants::<()>::default(); consts.protos.push(Vec::new()); let mut err = Default::default(); - let interp = Interpreter::new(&consts, &mut err); + let frames = Default::default(); + let interp = Interpreter::new(&consts, &mut err, &frames); let _ = Packer::new(interp, MAX_CALLS); } @@ -534,7 +569,8 @@ mod tests { consts.protos.push(Vec::new()); let mut der = JsonDeserializer::from_str("{}"); let mut err = Default::default(); - let interp = Interpreter::new(&consts, &mut err); + let frames = Default::default(); + let interp = Interpreter::new(&consts, &mut err, &frames); let pack = Packer::new(interp, MAX_CALLS).deserialize(&mut der).unwrap(); } @@ -552,8 +588,11 @@ mod tests { ]); let mut der = JsonDeserializer::from_str("3"); let mut err = Default::default(); - let interp = Interpreter::new(&consts, &mut err); - let pack = Packer::new(interp, MAX_CALLS).deserialize(&mut der).unwrap().0; + let frames = Default::default(); + let interp = Interpreter::new(&consts, &mut err, &frames); + let packed = Packer::new(interp, MAX_CALLS).deserialize(&mut der); + let (pack, obj) = packed.unwrap(); + assert!(obj.is_none()); assert_eq!(pack.subpacks[0]["hello"].1, SerdeObject::U64(3)); } } diff --git a/src/vm/mod.rs b/src/vm/mod.rs index 5f1e86c..190fa3d 100644 --- a/src/vm/mod.rs +++ b/src/vm/mod.rs @@ -7,6 +7,7 @@ use std::borrow::Cow; use std::cell::Cell; +use std::cell::RefCell; use std::collections::BTreeMap; use std::marker::PhantomData; @@ -212,7 +213,7 @@ pub(crate) enum PatternToken { /// /// These are used as expectations for serde (e.g. /// `Deserializer::deserialize_string`). -#[derive(Copy, Clone, Debug)] +#[derive(Copy, Clone, Debug, Eq, PartialEq)] pub(crate) enum Type { Any, IgnoredAny, @@ -237,17 +238,23 @@ pub(crate) enum Type { Option, Unit, Seq, - // Tuple(usize), + Tuple(usize), Map, - // // these aren't really supported: - // // UnitStruct, UnitVariant, NewtypeStruct, NewtypeVariant, TupleStruct, - // // TupleVariant, Struct, StructVariant - // // instead we use type trees for that. - // /// Adapter for Type Trees. See `crate::type_tree` for more details. - // Of { - // /// The type tree index (in `PatternConstants.type_trees`). - // type_tree: usize, - // }, + UnitStruct(&'static str), + NewtypeStruct(&'static str), + TupleStruct { + name: &'static str, + len: usize, + }, + Identifier, + Struct { + name: &'static str, + fields: &'static [&'static str], + }, + Enum { + name: &'static str, + variants: &'static [&'static str], + }, } /// The types which can be deserialized by serde. @@ -278,8 +285,6 @@ pub(crate) enum SerdeObject<'de> { // NOTE: support for multimaps! Map(Vec<(SerdeObject<'de>, SerdeObject<'de>)>), NewtypeStruct(Box<SerdeObject<'de>>), - // NOTE: currently unused! - #[allow(unused)] Enum { variant: Box<SerdeObject<'de>>, data: Box<SerdeObject<'de>>, @@ -351,69 +356,131 @@ pub(crate) struct Interpreter<'pat, 'state, O: Serialize> { pat: &'pat PatternConstants<O>, /// The error override (if any). error: &'state Cell<Option<crate::errors::MatchError>>, + /// The current interpreter frames. + frames: &'state RefCell<Vec<Frame<'pat>>>, + ///// The final output. + //output: &'state Cell<Pack<'pat, 'de>>, } -struct Frame<'pat, 'de> { +pub(crate) struct Frame<'pat> { /// The instructions/function currently being processed. ops: &'pat [PatternElement], /// The instruction index being processed. iar: Option<usize>, - /// Elements collected while processing this frame? - path: Vec<Pack<'pat, 'de>>, + /// Whether this frame matches. + matches: bool, + ///// Elements collected while processing this frame? + //path: Pack<'pat, 'de>, } impl<'pat, 'state, O: Serialize> Interpreter<'pat, 'state, O> { pub(crate) fn new( pat: &'pat PatternConstants<O>, error: &'state mut Option<crate::errors::MatchError>, + frames: &'state RefCell<Vec<Frame<'pat>>>, + //output: &'state mut Pack<'pat, 'de>, ) -> Self { + let mut mut_frames = frames.borrow_mut(); + debug_assert!(mut_frames.is_empty()); + mut_frames.push(Frame { + ops: &pat.protos[0], + iar: None, + matches: true, + //path: Default::default(), + }); + drop(mut_frames); Self { pat: pat, error: Cell::from_mut(error), - //frames: vec![ - // Frame { - // ops: &pat.protos[0], - // iar: None, - // path: Vec::new(), - // } - //], + frames: frames, + //output: Cell::from_mut(output), } } } -// -//impl<'a, 'b, T: PatternTypes> Frame<'a, 'b, T> { -// /// Advances the instruction address register. -// /// -// /// # Returns -// /// -// /// `true` if successful, `false` otherwise. -// fn next(&mut self) -> bool { -// let new = self.iar.map_or(0, |v| v + 1); -// new < self.ops.len() && { -// self.iar = Some(new); -// true -// } -// } -// -// /// Returns the current instruction. -// fn op(&self) -> PatternElement { -// self.ops[self.iar.expect("ops[iar]")] -// } -// -// /// Rewinds the instruction address register. -// /// -// /// # Returns -// /// -// /// `true` if successful, `false` otherwise. -// fn prev(&mut self) -> bool { -// let new = self.iar.expect("iar").checked_sub(1); -// new.is_some() && { -// self.iar = new; -// true -// } -// } -//} -// + +impl<'pat> Frame<'pat> { + /// Gets the type currently associated with this frame. + /// + /// Returns the type and whether it is required to match. + fn get_type<O: Serialize>( + &self, + pat: &'pat PatternConstants<O>, + ) -> Option<(Type, bool)> { + match self.op() { + | PatternElement::Value { name_and_value, .. } + | PatternElement::Tag { name_and_value, .. } + if name_and_value.is_there() + => { + match name_and_value.there() { + | Some(Value::String { skippable, .. }) + | Some(Value::Regex { skippable, .. }) + => { + Some((Type::Str, !skippable)) + }, + Some(Value::Type { ty, skippable }) => { + Some((ty, !skippable)) + }, + None => todo!(), + } + }, + _ => None, + } + } + + /// Gets the name currently associated with this frame. + fn get_name<O: Serialize>( + &self, + pat: &'pat PatternConstants<O>, + ) -> Option<&'pat str> { + let strings = &pat.strings; + match self.op() { + | PatternElement::Value { name_and_value, .. } + | PatternElement::Tag { name_and_value, .. } + if name_and_value.is_here() + => { + Some(&*strings[name_and_value.here().unwrap()]) + }, + _ => None, + } + } + + /// Advances the instruction address register. + /// + /// # Returns + /// + /// `true` if successful, `false` otherwise. + fn next(&mut self) -> bool { + let new = self.iar.map_or(0, |v| v + 1); + new < self.ops.len() && { + self.iar = Some(new); + true + } + } + + /// Returns the current instruction. + /// + /// # Panics + /// + /// 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"); + self.ops[self.iar.expect("ops[iar]")] + } + + /// Rewinds the instruction address register. + /// + /// # Returns + /// + /// `true` if successful, `false` otherwise. + fn prev(&mut self) -> bool { + let new = self.iar.expect("iar").checked_sub(1); + new.is_some() && { + self.iar = new; + true + } + } +} + ///// Stores a single match. ///// ///// See also Holder. |