Initial work on Serde VM stuff

7 files changed, 317 insertions, 16 deletions

diff --git a/Cargo.toml b/Cargo.toml
index 1a85a35..a9e6de1 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -14,6 +14,7 @@ homepage = "https://soniex2.github.io/ganarchy/project/c0b4a8a326a320ac33c5d9d6b
 [dependencies]
 regex = "1"
 impl_trait = "0.1.7"
+serde_transmute = "0.1.4"
 serde = "1.0.140"
 erased-serde = "0.3.21"
 
@@ -21,7 +22,7 @@ erased-serde = "0.3.21"
 proptest = "1.0.0"
 serde_json = "1.0.82"
 serde = {version = "1.0.140", features = ["derive"]}
-charx = "1"
+charx = "1.0.0"
 
 [features]
 default = ['stable']
diff --git a/src/errors.rs b/src/errors.rs
index b41b225..9b0025e 100644
--- a/src/errors.rs
+++ b/src/errors.rs
@@ -39,11 +39,11 @@ pub enum PatternError<'a> {
 // /// These are errors that may be returned by the matcher when matching a
 // /// pattern.
 // #[derive(Clone, Debug)]
-// pub enum MatchError {
+pub enum MatchError {
 //     /// Returned if the pattern nests too deeply.
 //     StackOverflow,
 //     /// Returned if the pattern rejects the input.
-//     ValidationError,
+     ValidationError,
 //     /// Returned if the pattern attempts an unsupported operation.
 //     ///
 //     /// In particular, if the [`PatternTypes`] doesn't support `get` or `pairs`
@@ -52,4 +52,4 @@ pub enum PatternError<'a> {
 //     UnsupportedOperation,
 //     /// Returned if an unspecified non-critical error occurred.
 //     Other
-// }
+}
diff --git a/src/lib.rs b/src/lib.rs
index a3a6e1e..f71d81c 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,6 +1,8 @@
 // Copyright (C) 2021-2022 Soni L.
 // SPDX-License-Identifier: MIT OR Apache-2.0
 
+#![warn(elided_lifetimes_in_paths)]
+
 //! Datafu is a regex-inspired query language. It was primarily
 //! designed for processing object trees parsed from configuration files, but
 //! can be used with anything that supports serde.
@@ -99,6 +101,7 @@
 //! <!-- TODO -->
 
 pub mod errors;
+pub mod type_tree;
 mod parser;
 mod pattern;
 mod vm;
@@ -107,7 +110,7 @@ pub use pattern::Pattern;
 
 /// A predicate.
 pub type Predicate = dyn (Fn(
-    &mut dyn erased_serde::Deserializer<>
+    &mut dyn erased_serde::Deserializer<'_>
 ) -> bool) + Send + Sync;
 
 /// Helper to build predicates because closure inference is the worst.
@@ -133,7 +136,7 @@ pub type Predicate = dyn (Fn(
 pub fn pred<F>(f: F) -> Box<Predicate>
 where
     F: (Fn(
-        &mut dyn erased_serde::Deserializer<>
+        &mut dyn erased_serde::Deserializer<'_>
     ) -> bool) +  Send + Sync + 'static,
 {
     Box::new(f)
diff --git a/src/pattern.rs b/src/pattern.rs
index 2e69714..fc3c8a7 100644
--- a/src/pattern.rs
+++ b/src/pattern.rs
@@ -6,16 +6,17 @@
 use std::borrow::Borrow;
 use std::collections::BTreeMap;
 
-use serde::Deserialize;
-use serde::Deserializer;
-use serde::Serialize;
+use serde::de::Deserialize;
+use serde::de::DeserializeSeed;
+use serde::de::Deserializer;
+use serde::ser::Serialize;
 
 use crate::Predicate;
 use crate::errors::PatternError;
 use crate::parser::parse;
-//use crate::vm::Matcher;
+use crate::vm;
 use crate::vm::PatternConstants;
-//use crate::vm::MAX_CALLS;
+use crate::vm::MAX_CALLS;
 
 /// A compiled Datafu pattern.
 ///
@@ -83,11 +84,13 @@ impl<O: Serialize> Pattern<O> {
     }
 
     /// Matches the pattern against an input.
-    pub fn deserialize<'de, Der, De>(&self, de: Der) -> Result<De, Der::Error>
+    pub fn deserialize<'de, Der, De>(&self, der: Der) -> Result<De, Der::Error>
     where
         Der: Deserializer<'de>,
         De: Deserialize<'de>,
     {
+        let pack = vm::Packer::new(&self.consts, MAX_CALLS).deserialize(der)?;
+        let de = De::deserialize(vm::Unpacker::new(pack, MAX_CALLS));
         todo!()
     }
 }
diff --git a/src/type_tree.rs b/src/type_tree.rs
new file mode 100644
index 0000000..8e8098b
--- /dev/null
+++ b/src/type_tree.rs
@@ -0,0 +1,70 @@
+// Copyright (C) 2021-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.
+//!
+//! 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`!
+
+// TODO
diff --git a/src/vm/de.rs b/src/vm/de.rs
index 7039ea9..4d0d097 100644
--- a/src/vm/de.rs
+++ b/src/vm/de.rs
@@ -1,6 +1,139 @@
 // Copyright (C) 2022 Soni L.
 // SPDX-License-Identifier: MIT OR Apache-2.0
 
-use crate::vm;
+//! Deserialization-related parts of the VM.
 
+use serde::Serialize;
+use serde::de::Error as _;
 
+use super::PatternConstants;
+use super::PatternElement;
+use super::Pack;
+
+/// A `DeserializeSeed` for Datafu input.
+///
+/// This converts from Serde to Datafu's internal representation (a "pack").
+pub struct Packer<'pat, O: Serialize> {
+    /// The pattern currently being processed.
+    pat: &'pat PatternConstants<O>,
+    /// The instructions/function currently being processed.
+    ops: &'pat [PatternElement],
+    /// Maximum number of calls.
+    call_limit: usize,
+}
+
+impl<'pat, O: Serialize> Packer<'pat, O> {
+    pub(crate) fn new(
+        pat: &'pat PatternConstants<O>,
+        call_limit: usize,
+    ) -> Self {
+        Self {
+            pat, call_limit, ops: &pat.protos.last().unwrap()[..],
+        }
+    }
+}
+
+impl<'pat, 'de, O> serde::de::DeserializeSeed<'de> for Packer<'pat, O>
+where
+    O: Serialize,
+{
+    type Value = Pack;
+    fn deserialize<D>(self, deserializer: D) -> Result<Pack, D::Error>
+    where
+        D: serde::Deserializer<'de>
+    {
+        // check the first op
+        let first = self.ops.first();
+        match first {
+            Some(PatternElement::ApplyPredicate(id, skippable)) => {
+                let predicate = &self.pat.predicates[*id];
+                let ok = predicate(todo!());
+                match (ok, skippable) {
+                    (true, _) => {
+                        todo!()
+                    },
+                    (false, false) => {
+                        return Err(D::Error::custom("predicate didn't match"));
+                    },
+                    (false, true) => {
+                        todo!()
+                    },
+                }
+            },
+            _ => {
+                dbg!(first);
+                todo!()
+            },
+        }
+    }
+}
+
+/// A `Deserializer` for Datafu output.
+///
+/// This converts from Datafu's internal representation (a "pack") into the
+/// desired output type.
+pub struct Unpacker {
+    pack: Pack,
+    call_limit: usize,
+}
+
+impl Unpacker {
+    /// Unpacks a Datafu "pack".
+    pub fn new(pack: Pack, call_limit: usize) -> Self {
+        Self {
+            pack, call_limit,
+        }
+    }
+}
+
+impl<'de> serde::Deserializer<'de> for Unpacker {
+    // 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>(
+        self,
+        _: &'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!() }
+}
+
+/// A Deserializer for collecting matches from [`crate::Predicate`]s.
+///
+/// What are we doing?
+/// 
+/// We certainly have regrets.
+pub struct PredicateCollector {
+}
diff --git a/src/vm.rs b/src/vm/mod.rs
index ac5c95d..92a99d7 100644
--- a/src/vm.rs
+++ b/src/vm/mod.rs
@@ -13,6 +13,9 @@ use crate::Predicate;
 
 mod de;
 
+pub use de::Unpacker;
+pub use de::Packer;
+
 /// Max depth for VM/serde recursion.
 pub(crate) const MAX_CALLS: usize = 250;
 
@@ -46,8 +49,28 @@ impl<O: Serialize> Default for PatternConstants<O> {
     }
 }
 
+impl<O: Serialize> std::fmt::Debug for PatternConstants<O> {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        f.debug_struct(
+            "PatternConstants"
+        ).field(
+            "protos", &self.protos,
+        ).field(
+            "strings", &self.strings,
+        ).field(
+            "regices", &self.regices,
+        ).field(
+            "predicates",
+            &format_args!("({} predicates)", self.predicates.len()),
+        ).field(
+            "defs",
+            &format_args!("FIXME"),
+        ).finish()
+    }
+}
+
 /// A pattern element.
-#[derive(Copy, Clone)]
+#[derive(Copy, Clone, Debug)]
 pub(crate) enum PatternElement {
     Arrow,
 
@@ -58,11 +81,79 @@ pub(crate) enum PatternElement {
     ParameterKey(usize, bool),
     KeySubtree(usize, bool),
     ValueSubtree(usize, bool),
-    ApplyPredicate(usize, bool),
 
-    End
+    /// Represents a predicate which must be applied.
+    ///
+    /// These are custom, arbitrary predicates, powered by serde. They're
+    /// represented by `:$foo` in a pattern.
+    ApplyPredicate(
+        /// The predicate index (in `PatternConstants.predicates`).
+        usize,
+        /// Whether to skip non-matching values, instead of erroring.
+        bool,
+    ),
+
+    /// Represents a type expectation.
+    ///
+    /// These are similar to predicates. They're represented by `:foo`, but are
+    /// built-in and provide functionality not supported by predicates.
+    ///
+    /// Specifically, predicates cannot ask serde for a map or a list directly.
+    /// Instead, they'd be required to parse a whole map/list/etc, which could
+    /// cause issues which datafu is designed to avoid. (Datafu is designed to
+    /// resist malicious input more so than arbitrary serde deserializers.)
+    Type(
+        /// The expected type.
+        Type,
+        /// Whether to skip non-matching values, instead of erroring.
+        bool,
+    ),
+
+    End,
+}
+
+/// The types datafu and serde currently support.
+///
+/// These are used as expectations for serde (e.g.
+/// `Deserializer::deserialize_string`).
+#[derive(Copy, Clone, Debug)]
+pub(crate) enum Type {
+    Bool,
+    I8,
+    I16,
+    I32,
+    I64,
+    I128,
+    U8,
+    U16,
+    U32,
+    U64,
+    U128,
+    F32,
+    F64,
+    Char,
+    Str,
+    String,
+    Bytes,
+    ByteBuf,
+    Option,
+    Unit,
+    Seq,
+    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,
+    },
 }
 
+pub struct Pack;
+
 //struct Frame<'a, 'b, T: PatternTypes> {
 //    //obj: RefOwn<'b, T::Ref, T::Own>,
 //    ops: &'a [PatternElement],