neodyn_xc 0.4.0

//! In-memory, structured representation of a Neodyn Exchange value tree.

use std::io;
use std::str;
use std::str::FromStr;
use std::iter::FromIterator;
use std::convert::{ TryFrom, TryInto };
use std::borrow::Cow;
use std::collections::{ BTreeSet, BTreeMap, HashSet, HashMap };
use std::fmt::{ Display, Formatter, Result as FmtResult };
use ordered_float::{ NotNan, OrderedFloat };
use serde::{
    ser::{ Serialize, Serializer },
    de::{
        Deserialize, Deserializer, Visitor,
        SeqAccess, MapAccess,
        Unexpected, Error as DeError,
    },
};
#[cfg(feature = "serde_json")]
use serde_json::{
    Number as JsonNumber,
    Value as JsonValue,
    Map as JsonMap,
};
#[cfg(feature = "chrono")]
use chrono::prelude::*;
#[cfg(feature = "uuid")]
use uuid::Uuid;
#[cfg(feature = "quickcheck")]
use quickcheck::{ Arbitrary, Gen };
use crate::error::{ Error, ResultExt };

/// In-memory, structured representation of a Neodyn Exchange value tree.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Value {
    /// No value (an optional value that is not present).
    Null,
    /// An optional value that is present.
    Opt(Box<Value>),
    /// A Boolean value.
    Bool(bool),
    /// A signed 64-bit integer value.
    Int(i64),
    /// An unsigned 64-bit integer value.
    Uint(u64),
    /// A 64-bit canonicalized floating-point value that is not `NaN`.
    Float(NotNan<f64>),
    /// A UTF-8 string value.
    String(String),
    /// Raw binary data.
    Blob(Vec<u8>),
    /// An array of Neodyn Exchange values.
    Array(Vec<Value>),
    /// A collection of key-value pairs, mapping `Value`s to other `Value`s.
    Map(BTreeMap<Value, Value>),
}

impl Value {
    /// Returns the dynamic type tag of this value.
    #[must_use]
    pub const fn value_type(&self) -> ValueType {
        match *self {
            Value::Null      => ValueType::Null,
            Value::Opt(_)    => ValueType::Opt,
            Value::Bool(_)   => ValueType::Bool,
            Value::Int(_)    => ValueType::Int,
            Value::Uint(_)   => ValueType::Uint,
            Value::Float(_)  => ValueType::Float,
            Value::String(_) => ValueType::String,
            Value::Blob(_)   => ValueType::Blob,
            Value::Array(_)  => ValueType::Array,
            Value::Map(_)    => ValueType::Map,
        }
    }

    /// Returns true if and only if this value is null.
    #[must_use]
    pub const fn is_null(&self) -> bool {
        matches!(*self, Value::Null)
    }

    /// Returns true if and only if this value is an `Opt` containing a value.
    #[must_use]
    pub const fn is_opt(&self) -> bool {
        matches!(*self, Value::Opt(_))
    }

    /// Returns true iff this value is either null or an `Opt`.
    #[must_use]
    pub const fn is_null_or_opt(&self) -> bool {
        self.is_null() || self.is_opt()
    }

    /// Returns true if and only if this value is a bool.
    #[must_use]
    pub const fn is_bool(&self) -> bool {
        matches!(*self, Value::Bool(_))
    }

    /// Returns true if and only if this value is a signed integer.
    #[must_use]
    pub const fn is_int(&self) -> bool {
        matches!(*self, Value::Int(_))
    }

    /// Returns true if and only if this value is an unsigned integer.
    #[must_use]
    pub const fn is_uint(&self) -> bool {
        matches!(*self, Value::Uint(_))
    }

    /// Returns true if and only if this value is floating-point.
    #[must_use]
    pub const fn is_float(&self) -> bool {
        matches!(*self, Value::Float(_))
    }

    /// Returns true if and only if this value is any type of number,
    /// i.e. signed integer, unsigned integer, or floating-point.
    #[must_use]
    pub const fn is_number(&self) -> bool {
        self.is_int() || self.is_uint() || self.is_float()
    }

    /// Returns true if and only if this value is a string.
    #[must_use]
    pub const fn is_string(&self) -> bool {
        matches!(*self, Value::String(_))
    }

    /// Returns true if and only if this value is a BLOB.
    #[must_use]
    pub const fn is_blob(&self) -> bool {
        matches!(*self, Value::Blob(_))
    }

    /// Returns true if and only if this value is an array.
    #[must_use]
    pub const fn is_array(&self) -> bool {
        matches!(*self, Value::Array(_))
    }

    /// Returns true if and only if this value is a map.
    #[must_use]
    pub const fn is_map(&self) -> bool {
        matches!(*self, Value::Map(_))
    }

    /// Private helper method for constructing a type error.
    fn type_error<T>(&self, expected: ValueType) -> Result<T, Error> {
        Err(Error::new(
            format!("expected: {}, actual: {}", expected, self.value_type())
        ))
    }

    /// This only exists for reasons of symmetry.
    pub fn as_null(&self) -> Result<(), Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match *self {
            Value::Null => Ok(()),
            _ => self.type_error(ValueType::Null),
        }
    }

    /// Borrows the inner value of an optional.
    ///
    /// Returns `None` if `self` is `Null`, `Some` if it's `Opt`.
    pub fn as_opt(&self) -> Result<Option<&Value>, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match *self {
            Value::Null => Ok(None),
            Value::Opt(ref inner) => Ok(Some(inner)),
            _ => self.type_error(ValueType::Opt),
        }
    }

    /// Returns the inner value of an optional, consuming the value.
    ///
    /// Returns `None` if `self` is `Null`, `Some` if it's `Opt`.
    pub fn into_opt(self) -> Result<Option<Value>, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match self {
            Value::Null => Ok(None),
            Value::Opt(inner) => Ok(Some(*inner)),
            _ => self.type_error(ValueType::Opt),
        }
    }

    /// Returns the boolean value.
    pub fn as_bool(&self) -> Result<bool, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match *self {
            Value::Bool(b) => Ok(b),
            _ => self.type_error(ValueType::Bool),
        }
    }

    /// Returns the signed integer value.
    pub fn as_int(&self) -> Result<i64, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match *self {
            Value::Int(i) => Ok(i),
            _ => self.type_error(ValueType::Int),
        }
    }

    /// Returns the unsigned integer value.
    pub fn as_uint(&self) -> Result<u64, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match *self {
            Value::Uint(u) => Ok(u),
            _ => self.type_error(ValueType::Uint),
        }
    }

    /// Returns the floating-point value.
    pub fn as_float(&self) -> Result<f64, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match *self {
            Value::Float(f) => Ok(f.into_inner()),
            _ => self.type_error(ValueType::Float),
        }
    }

    /// Borrows the string value.
    pub fn as_str(&self) -> Result<&str, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match *self {
            Value::String(ref s) => Ok(s),
            _ => self.type_error(ValueType::String),
        }
    }

    /// Mutably borrows the string value.
    pub fn as_mut_string(&mut self) -> Result<&mut String, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match *self {
            Value::String(ref mut s) => Ok(s),
            _ => self.type_error(ValueType::String),
        }
    }

    /// Returns the string, consuming the value.
    pub fn into_string(self) -> Result<String, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match self {
            Value::String(s) => Ok(s),
            _ => self.type_error(ValueType::String),
        }
    }

    /// Borrows the blob value.
    pub fn as_blob(&self) -> Result<&[u8], Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match *self {
            Value::Blob(ref bytes) => Ok(bytes),
            _ => self.type_error(ValueType::Blob),
        }
    }

    /// Mutably borrows the blob value.
    pub fn as_mut_blob(&mut self) -> Result<&mut Vec<u8>, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match *self {
            Value::Blob(ref mut bytes) => Ok(bytes),
            _ => self.type_error(ValueType::Blob),
        }
    }

    /// Returns the blob, consuming the value.
    pub fn into_blob(self) -> Result<Vec<u8>, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match self {
            Value::Blob(bytes) => Ok(bytes),
            _ => self.type_error(ValueType::Blob),
        }
    }

    /// Borrows the array value.
    pub fn as_array(&self) -> Result<&[Value], Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match *self {
            Value::Array(ref array) => Ok(array),
            _ => self.type_error(ValueType::Array),
        }
    }

    /// Mutably borrows the array value.
    pub fn as_mut_array(&mut self) -> Result<&mut Vec<Value>, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match *self {
            Value::Array(ref mut array) => Ok(array),
            _ => self.type_error(ValueType::Array),
        }
    }

    /// Returns the array, consuming the value.
    pub fn into_array(self) -> Result<Vec<Value>, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match self {
            Value::Array(array) => Ok(array),
            _ => self.type_error(ValueType::Array),
        }
    }

    /// Borrows the map value.
    pub fn as_map(&self) -> Result<&BTreeMap<Value, Value>, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match *self {
            Value::Map(ref map) => Ok(map),
            _ => self.type_error(ValueType::Map),
        }
    }

    /// Mutably borrows the map value.
    pub fn as_mut_map(&mut self) -> Result<&mut BTreeMap<Value, Value>, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match *self {
            Value::Map(ref mut map) => Ok(map),
            _ => self.type_error(ValueType::Map),
        }
    }

    /// Returns the map, consuming the value.
    pub fn into_map(self) -> Result<BTreeMap<Value, Value>, Error> {
        #[allow(clippy::wildcard_enum_match_arm)]
        match self {
            Value::Map(map) => Ok(map),
            _ => self.type_error(ValueType::Map),
        }
    }

}

///////////////////////////////
// Constructors, conversions //
///////////////////////////////

/// The default value is `null`.
impl Default for Value {
    fn default() -> Self {
        Value::Null
    }
}

/// Creating a `Value` from unit yields `null`.
impl From<()> for Value {
    fn from(_: ()) -> Self {
        Value::Null
    }
}

impl<T> From<Option<T>> for Value
    where
        T: Into<Value>,
{
    fn from(value: Option<T>) -> Self {
        value.map_or(Value::Null, |v| Value::Opt(v.into().into()))
    }
}

impl From<bool> for Value {
    fn from(value: bool) -> Self {
        Value::Bool(value)
    }
}

impl From<i8> for Value {
    fn from(value: i8) -> Self {
        Value::Int(value.into())
    }
}

impl From<i16> for Value {
    fn from(value: i16) -> Self {
        Value::Int(value.into())
    }
}

impl From<i32> for Value {
    fn from(value: i32) -> Self {
        Value::Int(value.into())
    }
}

impl From<i64> for Value {
    fn from(value: i64) -> Self {
        Value::Int(value)
    }
}

impl TryFrom<i128> for Value {
    type Error = Error;

    fn try_from(value: i128) -> Result<Self, Self::Error> {
        i64::try_from(value).map(Value::Int).conv_err()
    }
}

impl TryFrom<isize> for Value {
    type Error = Error;

    fn try_from(value: isize) -> Result<Self, Self::Error> {
        i64::try_from(value).map(Value::Int).conv_err()
    }
}

impl From<u8> for Value {
    fn from(value: u8) -> Self {
        Value::Uint(value.into())
    }
}

impl From<u16> for Value {
    fn from(value: u16) -> Self {
        Value::Uint(value.into())
    }
}

impl From<u32> for Value {
    fn from(value: u32) -> Self {
        Value::Uint(value.into())
    }
}

impl From<u64> for Value {
    fn from(value: u64) -> Self {
        Value::Uint(value)
    }
}

impl TryFrom<u128> for Value {
    type Error = Error;

    fn try_from(value: u128) -> Result<Self, Self::Error> {
        u64::try_from(value).map(Value::Uint).conv_err()
    }
}

impl TryFrom<usize> for Value {
    type Error = Error;

    fn try_from(value: usize) -> Result<Self, Self::Error> {
        u64::try_from(value).map(Value::Uint).conv_err()
    }
}

/// `NaN` is not permitted in Neodyn Exchange values. It will be converted
/// to `Value::Null` if it is ever encountered.
impl From<f32> for Value {
    fn from(value: f32) -> Self {
        Value::from(f64::from(value))
    }
}

/// `NaN` is not permitted in Neodyn Exchange values. It will be converted
/// to `Value::Null` if it is ever encountered.
impl From<f64> for Value {
    fn from(value: f64) -> Self {
        NotNan::try_from(value).map_or(Value::Null, Value::Float)
    }
}

/// `NaN` is not permitted in Neodyn Exchange values. It will be converted
/// to `Value::Null` if it is ever encountered.
impl From<OrderedFloat<f32>> for Value {
    fn from(value: OrderedFloat<f32>) -> Self {
        Value::from(value.into_inner())
    }
}

/// `NaN` is not permitted in Neodyn Exchange values. It will be converted
/// to `Value::Null` if it is ever encountered.
impl From<OrderedFloat<f64>> for Value {
    fn from(value: OrderedFloat<f64>) -> Self {
        Value::from(value.into_inner())
    }
}

impl From<NotNan<f32>> for Value {
    fn from(value: NotNan<f32>) -> Self {
        Value::Float(value.into())
    }
}

impl From<NotNan<f64>> for Value {
    fn from(value: NotNan<f64>) -> Self {
        Value::Float(value)
    }
}

#[cfg(feature = "serde_json")]
impl From<JsonNumber> for Value {
    fn from(value: JsonNumber) -> Self {
        if let Some(u) = value.as_u64() {
            u.into()
        } else if let Some(i) = value.as_i64() {
            i.into()
        } else if let Some(f) = value.as_f64() {
            f.into()
        } else {
            unreachable!("number `{}` is neither u64, i64, nor f64", value)
        }
    }
}

impl From<&str> for Value {
    fn from(value: &str) -> Self {
        Value::String(value.into())
    }
}

impl From<String> for Value {
    fn from(value: String) -> Self {
        Value::String(value)
    }
}

impl From<Cow<'_, str>> for Value {
    fn from(value: Cow<'_, str>) -> Self {
        Value::String(value.into_owned())
    }
}

impl From<Box<str>> for Value {
    fn from(value: Box<str>) -> Self {
        Value::String(value.into())
    }
}

/// Converts a `char` to a single-character string representation.
impl From<char> for Value {
    fn from(value: char) -> Self {
        Value::String(value.to_string())
    }
}

/// Formats the date as an RFC3339 string.
#[cfg(feature = "chrono")]
impl<Tz: TimeZone> From<DateTime<Tz>> for Value {
    fn from(value: DateTime<Tz>) -> Self {
        // The `Debug` format for `DateTime` is explicitly documented.
        Value::String(format!("{:?}", value))
    }
}

/// Formats the UUID as a hexadecimal, hyphen-separated (canonical) string.
#[cfg(feature = "uuid")]
impl From<Uuid> for Value {
    fn from(value: Uuid) -> Self {
        Value::String(value.to_string())
    }
}

/// Creates an array.
impl<T> From<Vec<T>> for Value
    where
        T: Into<Value>,
{
    fn from(value: Vec<T>) -> Self {
        value.into_iter().collect()
    }
}

impl<T> From<&[T]> for Value
    where
        T: ToOwned,
        T::Owned: Into<Value>,
{
    fn from(value: &[T]) -> Self {
        value.iter().map(ToOwned::to_owned).collect()
    }
}

impl<T> From<Box<[T]>> for Value
    where
        T: Into<Value>,
{
    fn from(value: Box<[T]>) -> Self {
        value.into_vec().into()
    }
}

impl<T> From<Cow<'_, [T]>> for Value
    where
        [T]: ToOwned<Owned = Vec<T>>,
        T: Into<Value>,
{
    fn from(value: Cow<[T]>) -> Self {
        value.into_owned().into()
    }
}

impl<T> From<BTreeSet<T>> for Value
    where
        T: Into<Value>,
{
    fn from(value: BTreeSet<T>) -> Self {
        value.into_iter().collect()
    }
}

impl<T, S> From<HashSet<T, S>> for Value
    where
        T: Into<Value>,
{
    fn from(value: HashSet<T, S>) -> Self {
        value.into_iter().collect()
    }
}

/// Creates a `map`.
impl<K, V> From<BTreeMap<K, V>> for Value
    where
        K: Into<Value>,
        V: Into<Value>,
{
    fn from(value: BTreeMap<K, V>) -> Self {
        value.into_iter().collect()
    }
}

/// Creates a `map`.
impl<K, V, S> From<HashMap<K, V, S>> for Value
    where
        K: Into<Value>,
        V: Into<Value>,
{
    fn from(value: HashMap<K, V, S>) -> Self {
        value.into_iter().collect()
    }
}

/// Creates a `map` (with all-string keys) from a JSON object.
#[cfg(feature = "serde_json")]
impl From<JsonMap<String, JsonValue>> for Value {
    fn from(value: JsonMap<String, JsonValue>) -> Self {
        value.into_iter().collect()
    }
}

/// Converts a JSON `Value` to a Neodyn Exchange `Value`.
#[cfg(feature = "serde_json")]
impl From<JsonValue> for Value {
    fn from(value: JsonValue) -> Self {
        match value {
            JsonValue::Null => Value::Null,
            JsonValue::Bool(b) => b.into(),
            JsonValue::Number(n) => n.into(),
            JsonValue::String(s) => s.into(),
            JsonValue::Array(array) => array.into(),
            JsonValue::Object(map) => map.into(),
        }
    }
}

/// Attempts to convert a Neodyn Exchange `Value` to a JSON `Value`.
/// This is not always possible because JSON values aren't capable of
/// representing e.g. maps with non-string keys or infinite numbers.
///
/// This is a best-effort attempt; it only fails when there really is no
/// sensible way to proceed. This means that it is a **lossy conversion,**
/// so **a round-trip through a JSON `Value` will not in general preserve
/// the exact structure of the Neodyn Exchange `Value`.** In particular:
///
///   * Explicit optionals will be mapped to their inner value.
///   * Blobs will be mapped to an array of unsigned integers.
///   * Infinite floats will result in an error.
///   * Maps with non-`String` keys will result in an error.
///
/// Therefore, **this conversion should only be used for debugging
/// or otherwise excactness-insensitive purposes. It should NOT be
/// relied upon as the first tool you reach for.** Generally, if a
/// Neodyn Exchange value is to be sent between parties, it should
/// rather be serialized directly to its own text or binary format.
#[cfg(feature = "serde_json")]
impl TryFrom<Value> for JsonValue {
    type Error = Error;

    fn try_from(value: Value) -> Result<Self, Self::Error> {
        match value {
            Value::Null => Ok(JsonValue::Null),
            Value::Opt(inner) => JsonValue::try_from(*inner),
            Value::Bool(b) => Ok(JsonValue::Bool(b)),
            Value::Int(i) => Ok(JsonValue::from(i)),
            Value::Uint(u) => Ok(JsonValue::from(u)),
            Value::Float(f) => {
                JsonNumber::from_f64(f.into()).map_or_else(
                    || Err(Error::new("infinite floating-point number")),
                    |n| Ok(JsonValue::Number(n)),
                )
            },
            Value::String(s) => Ok(JsonValue::String(s)),
            Value::Blob(bytes) => Ok(JsonValue::from(bytes)),
            Value::Array(items) => {
                items
                    .into_iter()
                    .map(TryFrom::try_from)
                    .collect::<Result<_, _>>()
                    .map(JsonValue::Array)
            },
            Value::Map(entries) => {
                entries
                    .into_iter()
                    .map(|(k, v)| if let Value::String(key) = k {
                        let value = JsonValue::try_from(v)?;
                        Ok((key, value))
                    } else {
                        Err(Error::new("non-string key in map"))
                    })
                    .collect::<Result<_, _>>()
                    .map(JsonValue::Object)
            },
        }
    }
}

/// Creates an array from an iterator over single values.
impl<T> FromIterator<T> for Value
    where
        T: Into<Value>,
{
    fn from_iter<I>(iter: I) -> Self
        where
            I: IntoIterator<Item = T>,
    {
        Value::Array(iter.into_iter().map(Into::into).collect())
    }
}

/// Creates a map from an iterator over key-value pairs.
impl<K, V> FromIterator<(K, V)> for Value
    where
        K: Into<Value>,
        V: Into<Value>,
{
    fn from_iter<I>(iter: I) -> Self
        where
            I: IntoIterator<Item = (K, V)>,
    {
        let map = iter
            .into_iter()
            .map(|(key, val)| (key.into(), val.into()))
            .collect();

        Value::Map(map)
    }
}

///////////////////////////////////////////////////////////
// Parsing and pretty-printing the human-readable format //
///////////////////////////////////////////////////////////

impl FromStr for Value {
    type Err = Error;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        crate::from_str(s)
    }
}

/// Formats the value using the human-readable text representation.
///
/// By default, the value will be pretty-printed. Specifying the alternate
/// flag (`{:#}`) has the effect of outputting a compact format instead.
impl Display for Value {
    fn fmt(&self, formatter: &mut Formatter) -> FmtResult {
        /// Wraps a `Formatter` in an `io::Write`.
        struct TextIo<'a, 'b>(&'a mut Formatter<'b>);

        impl<'a, 'b> io::Write for TextIo<'a, 'b> {
            fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
                let s = str::from_utf8(buf).map_err(
                    |e| io::Error::new(io::ErrorKind::Other, e)
                )?;
                self.0.write_str(s).map_err(
                    |e| io::Error::new(io::ErrorKind::Other, e)
                )?;
                Ok(buf.len())
            }

            fn flush(&mut self) -> io::Result<()> {
                Ok(())
            }
        }

        let padding = if formatter.alternate() {
            None
        } else {
            Some("    ")
        };

        crate::ser::text::to_writer(
            &mut TextIo(formatter),
            self,
            padding,
        ).map_err(
            |_error| std::fmt::Error // can't do anything with IO error here
        )
    }
}

///////////////////////////////
// Serialize and Deserialize //
///////////////////////////////

impl Serialize for Value {
    fn serialize<S: Serializer>(&self, ser: S) -> Result<S::Ok, S::Error> {
        match *self {
            Value::Null => ser.serialize_none(),
            Value::Opt(ref inner) => ser.serialize_some(inner),
            Value::Bool(b) => ser.serialize_bool(b),
            Value::Int(i) => ser.serialize_i64(i),
            Value::Uint(u) => ser.serialize_u64(u),
            Value::Float(f) => ser.serialize_f64(f.into_inner()),
            Value::String(ref string) => ser.serialize_str(string),
            Value::Blob(ref bytes) => ser.serialize_bytes(bytes),
            Value::Array(ref values) => ser.collect_seq(values),
            Value::Map(ref items) => ser.collect_map(items),
        }
    }
}

impl<'a> Deserialize<'a> for Value {
    fn deserialize<D: Deserializer<'a>>(de: D) -> Result<Self, D::Error> {
        de.deserialize_any(ValueVisitor)
    }
}

/// Visitor for deserializing a `Value`.
#[derive(Debug, Clone, Copy)]
struct ValueVisitor;

impl<'a> Visitor<'a> for ValueVisitor {
    type Value = Value;

    fn expecting(&self, formatter: &mut Formatter) -> FmtResult {
        formatter.pad("a Neodyn Exchange value")
    }

    fn visit_bool<E>(self, v: bool) -> Result<Self::Value, E> {
        Ok(v.into())
    }

    fn visit_i64<E>(self, v: i64) -> Result<Self::Value, E> {
        Ok(v.into())
    }

    fn visit_i128<E: DeError>(self, v: i128) -> Result<Self::Value, E> {
        v.try_into().map_err(|_error| { // construct a better error message
            E::invalid_value(
                Unexpected::Other(&format!("i128 `{}`", v)),
                &"signed integer fitting into i64",
            )
        })
    }

    fn visit_u64<E>(self, v: u64) -> Result<Self::Value, E> {
        Ok(v.into())
    }

    fn visit_u128<E: DeError>(self, v: u128) -> Result<Self::Value, E> {
        v.try_into().map_err(|_error| { // construct a better error message
            E::invalid_value(
                Unexpected::Other(&format!("u128 `{}`", v)),
                &"unsigned integer fitting into u64",
            )
        })
    }

    fn visit_f64<E>(self, v: f64) -> Result<Self::Value, E> {
        Ok(v.into())
    }

    fn visit_str<E>(self, v: &str) -> Result<Self::Value, E> {
        Ok(v.into())
    }

    /// This method is implemented for performance reasons only,
    /// so that no spurious copying of an already-owned string happens.
    fn visit_string<E>(self, v: String) -> Result<Self::Value, E> {
        Ok(v.into())
    }

    fn visit_bytes<E>(self, v: &[u8]) -> Result<Self::Value, E> {
        Ok(Value::Blob(v.to_vec()))
    }

    /// This method is implemented for performance reasons only,
    /// so that no spurious copying of an already-owned BLOB happens.
    fn visit_byte_buf<E>(self, v: Vec<u8>) -> Result<Self::Value, E> {
        Ok(Value::Blob(v))
    }

    fn visit_none<E>(self) -> Result<Self::Value, E> {
        Ok(Value::Null)
    }

    fn visit_some<D: Deserializer<'a>>(self, de: D) -> Result<Self::Value, D::Error> {
        Deserialize::deserialize(de).map(|v| Value::Opt(Box::new(v)))
    }

    fn visit_unit<E>(self) -> Result<Self::Value, E> {
        Ok(Value::Null)
    }

    fn visit_newtype_struct<D: Deserializer<'a>>(self, de: D) -> Result<Self::Value, D::Error> {
        Deserialize::deserialize(de)
    }

    fn visit_seq<A: SeqAccess<'a>>(self, mut seq: A) -> Result<Self::Value, A::Error> {
        let len = seq.size_hint().unwrap_or(0);
        let mut values = Vec::with_capacity(len);

        while let Some(value) = seq.next_element()? {
            values.push(value);
        }

        Ok(Value::Array(values))
    }

    fn visit_map<A: MapAccess<'a>>(self, mut map: A) -> Result<Self::Value, A::Error> {
        let mut values = BTreeMap::new();

        while let Some((key, value)) = map.next_entry()? {
            values.insert(key, value);
        }

        Ok(Value::Map(values))
    }
}

/// Quickcheck support for `Value`.
#[cfg(feature = "quickcheck")]
impl Arbitrary for Value {
    fn arbitrary(g: &mut Gen) -> Self {
        // A simple way for generating a Value tree is to treat it
        // as a branching process. However, that would require
        // computing sufficiently small probabilities based on the
        // size parameter of the generator and the children of each
        // recursive value type (optional, array, map), in order
        // not to overflow the stack. Concretely, we would want:
        //
        //     P(map) + 0.5 * P(array) <= (1 - P(optional)) / (size - 1)
        //
        // from which a simplified choice is
        //
        //     P(map) = (1 - P(optional)) / (3 * size)
        //     P(array) = 2 * p(map)
        //
        // (For an explanation, see:
        // https://en.wikipedia.org/wiki/Branching_process)
        //
        // In fact, we used to perform this calculation, but with
        // the upgrade to quickcheck 1.0, it turns out that the
        // definition of `Gen::size()` changed in a non-obvious way,
        // so our results no longer hold, and we could not correct
        // them. This lead to `Value::arbitrary()` causing infinite
        // recursion and a stack overflow more often than not.
        //
        // Therefore, we had to find another way, so we now generate
        // a tree with an exact, explicit upper bound on its depth,
        // instead of relying on the process ending probabilistically.
        //
        // We solve `(n / 2) ^ n == g.size()` approximately:
        // a tree of maximal branching factor `n`, uniformly
        // sampled, has an expected branching factor of `n / 2`.
        // If we allow that to grow through `n` levels, the
        // expected number of total nodes grows approximately
        // as `(n / 2) ^ n`. It's not exact, but good enough.
        #[allow(clippy::cast_possible_truncation)]
        let max = (0..32)
            .find(|&n: &u32| (g.size() as u32) << n <= n.pow(n))
            .unwrap_or(32);

        random_value_tree(g, max, max)
    }

    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
        /// Wraps every returned shrunken item in a `Value`.
        fn shrink_map_value<A>(arb: &A) -> Box<dyn Iterator<Item = Value>>
            where
                A: Arbitrary + Into<Value>,
        {
            Box::new(arb.shrink().map(Into::into))
        }

        match *self {
            Value::Null => quickcheck::empty_shrinker(),
            Value::Opt(ref inner) => {
                let copy = (**inner).clone();

                // * First, try the same structure, i.e. keep the optional
                //   wrapper but shrink the inner value.
                // * Next, decrease height by one by removing the optional
                //   wrapper and just providing the inner value
                // * Finally, shrink Opt to Null (i.e. no contained value)
                Box::new(inner
                         .shrink()
                         .map(Value::Opt)
                         .chain(vec![copy, Value::Null]))
            },
            Value::Bool(b) => shrink_map_value(&b),
            Value::Int(i) => shrink_map_value(&i),
            Value::Uint(u) => shrink_map_value(&u),
            Value::Float(f) => {
                Box::new(f.into_inner().shrink().map(f64::into))
            },
            Value::String(ref s) => shrink_map_value(s),
            Value::Blob(ref bytes) => {
                Box::new(bytes.shrink().map(Value::Blob))
            },
            Value::Array(ref array) => shrink_map_value(array),
            Value::Map(ref map) => shrink_map_value(map),
        }
    }
}

/// Generate a random tree of `Value`s (scalars and containers)
/// of maximal depth `max_depth`, where each non-leaf node has
/// at most `max_branch` children.
#[cfg(feature = "quickcheck")]
fn random_value_tree(g: &mut Gen, max_depth: u32, max_branch: u32) -> Value {
    /// Generates an `Arbitrary` float, but excludes `NaN`.
    fn not_nan_float(g: &mut Gen) -> NotNan<f64> {
        loop {
            let x = f64::arbitrary(g);

            if let Ok(value) = NotNan::try_from(x) {
                break value;
            }
        }
    }

    /// Generates a random non-container `Value`, i.e.
    /// anything except an `Opt`, an `Array` or a `Map`.
    fn random_scalar_value(g: &mut Gen) -> Value {
        match u8::arbitrary(g) {
            0  ..=  4 => Value::Null,
            5  ..= 15 => Value::Bool(bool::arbitrary(g)),
            16 ..= 63 => Value::Int(i64::arbitrary(g)),
            64 ..=111 => Value::Uint(u64::arbitrary(g)),
            112..=159 => Value::Float(not_nan_float(g)),
            160..=207 => Value::String(String::arbitrary(g)),
            208..=255 => Value::Blob(Vec::arbitrary(g)),
        }
    }

    // we ran out of allowed depth or breadth, so just make a leaf
    if max_depth == 0 || max_branch == 0 {
        return random_scalar_value(g);
    }

    let num_children = u32::arbitrary(g) % max_branch;

    // instead of an empty container, sometimes generate a
    // scalar leaf in order to get scalars at random depths,
    // not only at the very last level
    if num_children == 0 && bool::arbitrary(g) {
        return random_scalar_value(g);
    }

    // if the number of children is 1, the container can be
    // an optional. (It can't be an optional unless it has
    // exactly one child!)
    if num_children == 1 && bool::arbitrary(g) {
        let child = random_value_tree(g, max_depth - 1, max_branch);
        return Value::Opt(Box::new(child));
    }

    // choose whether the container is a map or an array
    if bool::arbitrary(g) {
        (0..num_children)
            .map(|_| random_value_tree(g, max_depth - 1, max_branch))
            .collect()
    } else {
        (0..num_children)
            .map(|_| {
                let key = random_value_tree(g, max_depth - 1, max_branch);
                let val = random_value_tree(g, max_depth - 1, max_branch);
                (key, val)
            })
            .collect()
    }
}

/// Describes the dynamic type tag of a `Value`.
#[allow(clippy::module_name_repetitions)]
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum ValueType {
    /// No value (an optional value that is not present).
    Null,
    /// An optional value that is present.
    Opt,
    /// A Boolean value.
    Bool,
    /// A signed 64-bit integer value.
    Int,
    /// An unsigned 64-bit integer value.
    Uint,
    /// A 64-bit canonicalized floating-point value that is not `NaN`.
    Float,
    /// A UTF-8 string value.
    String,
    /// Raw binary data.
    Blob,
    /// An array of Neodyn Exchange values.
    Array,
    /// A collection of key-value pairs, mapping `Value`s to other `Value`s.
    Map,
}

impl ValueType {
    /// Returns a string representation of this type.
    #[must_use]
    pub const fn as_str(self) -> &'static str {
        match self {
            ValueType::Null   => "null",
            ValueType::Opt    => "opt",
            ValueType::Bool   => "bool",
            ValueType::Int    => "int",
            ValueType::Uint   => "uint",
            ValueType::Float  => "float",
            ValueType::String => "string",
            ValueType::Blob   => "blob",
            ValueType::Array  => "array",
            ValueType::Map    => "map",
        }
    }
}

impl Display for ValueType {
    fn fmt(&self, f: &mut Formatter) -> FmtResult {
        f.pad(self.as_str())
    }
}

impl FromStr for ValueType {
    type Err = Error;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        Ok(match s {
            "null"   => ValueType::Null,
            "opt"    => ValueType::Opt,
            "bool"   => ValueType::Bool,
            "int"    => ValueType::Int,
            "uint"   => ValueType::Uint,
            "float"  => ValueType::Float,
            "string" => ValueType::String,
            "blob"   => ValueType::Blob,
            "array"  => ValueType::Array,
            "map"    => ValueType::Map,
            _        => return Err(Error::custom(
                format_args!("invalid value type `{}`", s),
            )),
        })
    }
}

impl Serialize for ValueType {
    fn serialize<S: Serializer>(&self, ser: S) -> Result<S::Ok, S::Error> {
        ser.serialize_str(self.as_str())
    }
}

impl<'a> Deserialize<'a> for ValueType {
    fn deserialize<D: Deserializer<'a>>(de: D) -> Result<Self, D::Error> {
        de.deserialize_str(ValueTypeVisitor)
    }
}

/// A Serde visitor for deserializing a `ValueType`.
#[derive(Debug, Clone, Copy)]
struct ValueTypeVisitor;

impl<'a> Visitor<'a> for ValueTypeVisitor {
    type Value = ValueType;

    fn expecting(&self, f: &mut Formatter) -> FmtResult {
        f.pad("a type string for a Neodyn Exchange value")
    }

    fn visit_str<E: DeError>(self, v: &str) -> Result<Self::Value, E> {
        ValueType::from_str(v).map_err(E::custom)
    }
}

impl<'a> From<&'a Value> for Unexpected<'a> {
    fn from(value: &'a Value) -> Self {
        match *value {
            Value::Null            => Unexpected::Unit,
            Value::Opt(_)          => Unexpected::Option,
            Value::Bool(b)         => Unexpected::Bool(b),
            Value::Int(i)          => Unexpected::Signed(i),
            Value::Uint(u)         => Unexpected::Unsigned(u),
            Value::Float(f)        => Unexpected::Float(f.into()),
            Value::String(ref s)   => Unexpected::Str(s),
            Value::Blob(ref bytes) => Unexpected::Bytes(bytes),
            Value::Array(_)        => Unexpected::Seq,
            Value::Map(_)          => Unexpected::Map,
        }
    }
}