<commit_before>// This Source Code Form is subject to the terms of
// the Mozilla Public License, v. 2.0. If a copy of
// the MPL was not distributed with this file, You
// can obtain one at http://mozilla.org/MPL/2.0/.

//! CBOR ([RFC 7049](http://tools.ietf.org/html/rfc7049))
//! decoder implementation supporting the following features:
//!
//! - Generic decoding using an intermediate representation
//! - Tag validation
//! - Resource limits (e.g. maximum nesting level)
//! - Direct decoding into Rust types
//! - Indefinite sized bytes, strings, arrays and objects
//!
//! The module is structured as follows:
//!
//! 1. `Kernel` contains the basic decoding functionality, capable of
//! decoding simple unstructured types.
//! 2. `Decoder` directly decodes into native Rust types.
//! 3. `GenericDecoder` handles arbitrary CBOR items and decodes them
//! into an `Value` AST.
//!
//! # Example 1: Direct decoding
//!
//! ```
//! use cbor::{Config, Decoder};
//! use std::io::Cursor;
//!
//! let mut d = Decoder::new(Config::default(), Cursor::new(vec![0u8]));
//! assert_eq!(Some(0), d.u64().ok())
//! ```
//!
//! # Example 2: Direct decoding (nested array)
//!
//! ```
//! extern crate cbor;
//! extern crate rustc_serialize;
//!
//! use cbor::{Config, Decoder};
//! use rustc_serialize::hex::FromHex;
//! use std::io::Cursor;
//!
//! fn main() {
//!     let input   = Cursor::new("828301020383010203".from_hex().unwrap());
//!     let mut dec = Decoder::new(Config::default(), input);
//!     let mut res = Vec::new();
//!     for _ in 0 .. dec.array().unwrap() {
//!         let mut vec = Vec::new();
//!         for _ in 0 .. dec.array().unwrap() {
//!             vec.push(dec.u8().unwrap())
//!         }
//!         res.push(vec)
//!     }
//!     assert_eq!(vec![vec![1, 2, 3], vec![1, 2, 3]], res)
//! }
//! ```
//!
//! # Example 3: Generic decoding
//!
//! ```
//! extern crate cbor;
//! extern crate rustc_serialize;
//!
//! use cbor::{Config, GenericDecoder};
//! use cbor::value::{self, Key};
//! use rustc_serialize::hex::FromHex;
//! use std::io::Cursor;
//!
//! fn main() {
//!     let input = Cursor::new("a2616101028103".from_hex().unwrap());
//!     let mut d = GenericDecoder::new(Config::default(), input);
//!     let value = d.value().unwrap();
//!     let     c = value::Cursor::new(&value);
//!     assert_eq!(Some(1), c.field("a").u8());
//!     assert_eq!(Some(3), c.get(Key::U8(2)).at(0).u8())
//! }
//! ```
//!
//! # Example 4: Direct decoding (optional value)
//!
//! ```
//! use cbor::{opt, Config, Decoder};
//! use std::io::Cursor;
//!
//! let mut d = Decoder::new(Config::default(), Cursor::new(vec![0xF6]));
//! assert_eq!(None, opt(d.u8()).unwrap())
//! ```

use byteorder::{self, BigEndian, ReadBytesExt};
use std::collections::{BTreeMap, LinkedList};
use std::cmp::Eq;
use std::error::Error;
use std::f32;
use std::fmt::{self, Debug};
use std::io;
use std::string;
use skip::Skip;
use types::{Tag, Type};
use value::{self, Bytes, Key, Simple, Text, Value};

// Decoder Configuration ////////////////////////////////////////////////////

/// `Config` contains various settings which limit resource consumption
/// or enable certain validation options. Please note that the various
/// maximum length/size values apply to an individual element only.
///
/// This is mainly to prevent attackers from providing CBOR values whose
/// length is larger than the available memory. In combination the memory
/// consumption can still become large and it is best to limit the incoming
/// bytes to a specific upper bound, e.g. by using `std::io::Take`.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Config {
    /// Maximum number of array elements
    pub max_len_array: usize,
    /// Maximum length of a byte string
    pub max_len_bytes: usize,
    /// Maximum length of a string
    pub max_len_text: usize,
    /// Maximum number of object fields
    pub max_size_map: usize,
    /// Maximum recursion steps when decoder `Value`s
    pub max_nesting: usize,
    /// Ignore `Tag`s when decoding `Value`s
    pub skip_tags: bool,
    /// Validate `Value` type matches `Tag`.
    pub check_tags: bool
}

const DEFAULT_CONFIG: Config = Config
    { max_len_array: 1000
    , max_len_bytes: 0x500000
    , max_len_text: 0x500000
    , max_size_map: 1000
    , max_nesting: 16
    , skip_tags: false
    , check_tags: true
    };

impl Config {
    /// Create default configuration with
    ///
    /// - `max_len_array` = 1000
    /// - `max_len_bytes` = 5 MB
    /// - `max_len_text` = 5 MB
    /// - `max_size_map` = 1000
    /// - `max_nesting` = 16
    /// - `skip_tags` = false
    /// - `check_tags` = true
    pub fn default() -> Config { DEFAULT_CONFIG }
}

// Decode Error Type ////////////////////////////////////////////////////////

pub type DecodeResult<A> = Result<A, DecodeError>;

#[derive(Debug)]
pub enum DecodeError {
    /// An object contains the same key multiple times
    DuplicateKey(Box<Debug>),
    /// The decoded `Value` can not serve as a `Key` in an object
    InvalidKey(Value),
    /// The type of `Value` is not what is expected for a `Tag`
    InvalidTag(Value),
    /// The string is not encoded in UTF-8
    InvalidUtf8(string::FromUtf8Error),
    /// Some I/O error
    IoError(io::Error),
    /// The maximum configured length is exceeded
    TooLong { max: usize, actual: u64 },
    /// `Value`s are nested deeper than the configured maximum
    TooNested,
    /// The end of file has been encountered unexpectedly
    UnexpectedEOF,
    /// And unexpected type has been encountered
    UnexpectedType { datatype: Type, info: u8 },
    /// A break was encountered at some unexpected point while
    /// decoding an indefinite object.
    UnexpectedBreak
}

/// When decoding an optional item, i.e. a `Null` value has to be
/// considered, this function will map `Null` to `None` and any
/// other value to `Some(value)`.
pub fn opt<A>(r: DecodeResult<A>) -> DecodeResult<Option<A>> {
    match r {
        Ok(x)  => Ok(Some(x)),
        Err(e) => if is_null(&e) { Ok(None) } else { Err(e) }
    }
}

/// When decoding an item which may be `Undefined` this function
/// will map `Undefined` to `None` and any other value to `Some(value)`.
pub fn maybe<A>(r: DecodeResult<A>) -> DecodeResult<Option<A>> {
    match r {
        Ok(x)  => Ok(Some(x)),
        Err(e) => if is_undefined(&e) { Ok(None) } else { Err(e) }
    }
}

/// When decoding an indefinite item, every element item can be a `Break`
/// value. By wrapping it in `or_break`, this case can be handled more
/// conveniently.
pub fn or_break<A>(r: DecodeResult<A>) -> DecodeResult<Option<A>> {
    match r {
        Ok(x)  => Ok(Some(x)),
        Err(e) => if is_break(&e) { Ok(None) } else { Err(e) }
    }
}

fn is_break(e: &DecodeError) -> bool {
    match *e {
        DecodeError::UnexpectedType { datatype: Type::Break, .. } => true,
        _ => false
    }
}

fn is_null(e: &DecodeError) -> bool {
    match *e {
        DecodeError::UnexpectedType { datatype: Type::Null, .. } => true,
        _ => false
    }
}

fn is_undefined(e: &DecodeError) -> bool {
    match *e {
        DecodeError::UnexpectedType { datatype: Type::Undefined, .. } => true,
        _ => false
    }
}

impl fmt::Display for DecodeError {
    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        match *self {
            DecodeError::DuplicateKey(ref k) => write!(f, "DecodeError: duplicate key: {:?}", *k),
            DecodeError::InvalidKey(ref k)   => write!(f, "DecodeError: unsuitable map key: {:?}", *k),
            DecodeError::InvalidTag(ref v)   => write!(f, "DecodeError: value does not match tag: {:?}", *v),
            DecodeError::InvalidUtf8(ref e)  => write!(f, "DecodeError: Invalid UTF-8 encoding: {}", *e),
            DecodeError::IoError(ref e)      => write!(f, "DecodeError: I/O error: {}", *e),
            DecodeError::TooNested           => write!(f, "DecodeError: value is too nested"),
            DecodeError::UnexpectedEOF       => write!(f, "DecodeError: unexpected end-of-file"),
            DecodeError::UnexpectedBreak     => write!(f, "DecodeError: unexpected break"),
            DecodeError::TooLong{max:m, actual:a} => write!(f, "DecodeError: value is too long {} (max={})", a, m),
            DecodeError::UnexpectedType{datatype:t, info:i} => write!(f, "DecodeError: unexpected type {:?} (info={})", t, i)
        }
    }
}

impl Error for DecodeError {
    fn description(&self) -> &str {
        "DecodeError"
    }

    fn cause(&self) -> Option<&Error> {
        match *self {
            DecodeError::IoError(ref e)     => Some(e),
            DecodeError::InvalidUtf8(ref e) => Some(e),
            _                               => None
        }
    }
}

impl From<byteorder::Error> for DecodeError {
    fn from(e: byteorder::Error) -> DecodeError {
        match e {
            byteorder::Error::UnexpectedEOF => DecodeError::UnexpectedEOF,
            byteorder::Error::Io(e)         => DecodeError::IoError(e)
        }
    }
}

impl From<io::Error> for DecodeError {
    fn from(e: io::Error) -> DecodeError {
        DecodeError::IoError(e)
    }
}

impl From<string::FromUtf8Error> for DecodeError {
    fn from(e: string::FromUtf8Error) -> DecodeError {
        DecodeError::InvalidUtf8(e)
    }
}

// Decoder Kernel ///////////////////////////////////////////////////////////

pub type TypeInfo = (Type, u8);

/// This decoding kernel reads from an underlying `std::io::Read` type
/// primitive CBOR values such as unsigned and signed integers as well
/// as raw bytes.
/// It forms the basis on which `Decoder` and `GenericDecoder` add logic
/// for handling `Tag`s, heterogenous data and generic value decoding.
pub struct Kernel<R> {
    reader: R
}

impl<R: ReadBytesExt> Kernel<R> {
    pub fn new(r: R) -> Kernel<R> {
        Kernel { reader: r }
    }

    pub fn into_reader(self) -> R {
        self.reader
    }

    pub fn typeinfo(&mut self) -> DecodeResult<TypeInfo> {
        Type::read(&mut self.reader).map_err(From::from)
    }

    pub fn simple(&mut self, ti: &TypeInfo) -> DecodeResult<Simple> {
        match ti.0 {
            Type::Unassigned { major: 7, info: a } => Ok(Simple::Unassigned(a)),
            Type::Reserved   { major: 7, info: a } => Ok(Simple::Reserved(a)),
            _                                      => unexpected_type(ti)
        }
    }

    pub fn bool(&mut self, ti: &TypeInfo) -> DecodeResult<bool> {
        match *ti {
            (Type::Bool, 20) => Ok(false),
            (Type::Bool, 21) => Ok(true),
            _                => unexpected_type(ti)
        }
    }

    pub fn u8(&mut self, ti: &TypeInfo) -> DecodeResult<u8> {
        match *ti {
            (Type::UInt8, n @ 0...23) => Ok(n),
            (Type::UInt8, 24) => self.reader.read_u8().map_err(From::from),
            _                 => unexpected_type(ti)
        }
    }

    pub fn u16(&mut self, ti: &TypeInfo) -> DecodeResult<u16> {
        match *ti {
            (Type::UInt8, n @ 0...23) => Ok(n as u16),
            (Type::UInt8, 24)  => self.reader.read_u8().map(|n| n as u16).map_err(From::from),
            (Type::UInt16, 25) => self.reader.read_u16::<BigEndian>().map_err(From::from),
            _                  => unexpected_type(ti)
        }
    }

    pub fn u32(&mut self, ti: &TypeInfo) -> DecodeResult<u32> {
        match *ti {
            (Type::UInt8, n @ 0...23) => Ok(n as u32),
            (Type::UInt8, 24)  => self.reader.read_u8().map(|n| n as u32).map_err(From::from),
            (Type::UInt16, 25) => self.reader.read_u16::<BigEndian>().map(|n| n as u32).map_err(From::from),
            (Type::UInt32, 26) => self.reader.read_u32::<BigEndian>().map_err(From::from),
            _                  => unexpected_type(ti)
        }
    }

    pub fn u64(&mut self, ti: &TypeInfo) -> DecodeResult<u64> {
        match *ti {
            (Type::UInt8, n @ 0...23) => Ok(n as u64),
            (Type::UInt8, 24)  => self.reader.read_u8().map(|n| n as u64).map_err(From::from),
            (Type::UInt16, 25) => self.reader.read_u16::<BigEndian>().map(|n| n as u64).map_err(From::from),
            (Type::UInt32, 26) => self.reader.read_u32::<BigEndian>().map(|n| n as u64).map_err(From::from),
            (Type::UInt64, 27) => self.reader.read_u64::<BigEndian>().map_err(From::from),
            _                  => unexpected_type(ti)
        }
    }

    pub fn i8(&mut self, ti: &TypeInfo) -> DecodeResult<i8> {
        match *ti {
            (Type::Int8, n @ 0...23) => Ok(-1 - n as i8),
            (Type::Int8, 24) => self.reader.read_u8().map(|n| -1 - n as i8).map_err(From::from),
            _                => unexpected_type(ti)
        }
    }

    pub fn i16(&mut self, ti: &TypeInfo) -> DecodeResult<i16> {
        match *ti {
            (Type::Int8, n @ 0...23) => Ok(-1 - n as i16),
            (Type::Int8, 24)  => self.reader.read_u8().map(|n| -1 - n as i16).map_err(From::from),
            (Type::Int16, 25) => self.reader.read_u16::<BigEndian>().map(|n| -1 - n as i16).map_err(From::from),
            _                 => unexpected_type(ti)
        }
    }

    pub fn i32(&mut self, ti: &TypeInfo) -> DecodeResult<i32> {
        match *ti {
            (Type::Int8, n @ 0...23) => Ok(-1 - n as i32),
            (Type::Int8, 24)  => self.reader.read_u8().map(|n| -1 - n as i32).map_err(From::from),
            (Type::Int16, 25) => self.reader.read_u16::<BigEndian>().map(|n| -1 - n as i32).map_err(From::from),
            (Type::Int32, 26) => self.reader.read_u32::<BigEndian>().map(|n| -1 - n as i32).map_err(From::from),
            _                 => unexpected_type(ti)
        }
    }

    pub fn i64(&mut self, ti: &TypeInfo) -> DecodeResult<i64> {
        match *ti {
            (Type::Int8, n @ 0...23) => Ok(-1 - n as i64),
            (Type::Int8, 24)  => self.reader.read_u8().map(|n| -1 - n as i64).map_err(From::from),
            (Type::Int16, 25) => self.reader.read_u16::<BigEndian>().map(|n| -1 - n as i64).map_err(From::from),
            (Type::Int32, 26) => self.reader.read_u32::<BigEndian>().map(|n| -1 - n as i64).map_err(From::from),
            (Type::Int64, 27) => self.reader.read_u64::<BigEndian>().map(|n| -1 - n as i64).map_err(From::from),
            _                 => unexpected_type(ti)
        }
    }

    pub fn f16(&mut self, ti: &TypeInfo) -> DecodeResult<f32> {
        match ti.0 {
            Type::Float16 => {
                // Copied from RFC 7049 Appendix D:
                let half  = try!(self.reader.read_u16::<BigEndian>());
                let exp   = half >> 10 & 0x1F;
                let mant  = half & 0x3FF;
                let value = match exp {
                    0  => ffi::c_ldexpf(mant as f32, -24),
                    31 => if mant == 0 { f32::INFINITY } else { f32::NAN },
                    _  => ffi::c_ldexpf(mant as f32 + 1024.0, exp as isize - 25)
                };
                Ok(if half & 0x8000 == 0 { value } else { - value })
            }
            _ => unexpected_type(ti)
        }
    }

    pub fn f32(&mut self, ti: &TypeInfo) -> DecodeResult<f32> {
        match ti.0 {
            Type::Float32 => self.reader.read_f32::<BigEndian>().map_err(From::from),
            _             => unexpected_type(ti)
        }
    }

    pub fn f64(&mut self, ti: &TypeInfo) -> DecodeResult<f64> {
        match ti.0 {
            Type::Float64 => self.reader.read_f64::<BigEndian>().map_err(From::from),
            _             => unexpected_type(ti)
        }
    }

    /// Decode `first` and potentially the following bytes as an
    /// unsigned value following the rules of major type 0.
    pub fn unsigned(&mut self, first: u8) -> DecodeResult<u64> {
        match first {
            n @ 0...23 => Ok(n as u64),
            24 => self.reader.read_u8().map(|n| n as u64).map_err(From::from),
            25 => self.reader.read_u16::<BigEndian>().map(|n| n as u64).map_err(From::from),
            26 => self.reader.read_u32::<BigEndian>().map(|n| n as u64).map_err(From::from),
            27 => self.reader.read_u64::<BigEndian>().map_err(From::from),
            _  => unexpected_type(&(Type::UInt64, first))
        }
    }

    /// Read `begin` as the length and return that many raw bytes.
    /// If length is greater than the given `max_len`, `DecodeError::TooLong`
    /// is returned instead.
    pub fn raw_data(&mut self, begin: u8, max_len: usize) -> DecodeResult<Vec<u8>> {
        let len = try!(self.unsigned(begin));
        if len > max_len as u64 {
            return Err(DecodeError::TooLong { max: max_len, actual: len })
        }
        let n = len as usize;
        let mut v = vec![0u8; n];
        let mut i = 0;
        while i < n {
            match self.reader.read(&mut v[i..]) {
                Ok(0)  => return Err(DecodeError::UnexpectedEOF),
                Ok(j)  => i += j,
                Err(e) =>
                    if e.kind() != io::ErrorKind::Interrupted {
                        return Err(DecodeError::IoError(e))
                    }
            }
        }
        Ok(v)
    }
}

// Workaround to not require the currently unstable `f32::ldexp`:
mod ffi {
    use libc::c_int;

    extern {
        pub fn ldexpf(x: f32, exp: c_int) -> f32;
    }

    #[inline]
    pub fn c_ldexpf(x: f32, exp: isize) -> f32 {
        unsafe { ldexpf(x, exp as c_int) }
    }
}

fn unexpected_type<A>(ti: &TypeInfo) -> DecodeResult<A> {
    Err(DecodeError::UnexpectedType { datatype: ti.0, info: ti.1 })
}

// Decoder //////////////////////////////////////////////////////////////////

/// The actual decoder type definition
pub struct Decoder<R> {
    kernel: Kernel<R>,
    config: Config
}

impl<R: ReadBytesExt> Decoder<R> {
    pub fn new(c: Config, r: R) -> Decoder<R> {
        Decoder { kernel: Kernel::new(r), config: c }
    }

    pub fn into_reader(self) -> R {
        self.kernel.into_reader()
    }

    pub fn simple(&mut self) -> DecodeResult<Simple> {
        self.typeinfo().and_then(|ti| self.kernel.simple(&ti))
    }

    pub fn bool(&mut self) -> DecodeResult<bool> {
        self.typeinfo().and_then(|ti| self.kernel.bool(&ti))
    }<commit_msg>Expose kernel object in Decoder (fixes #4)<commit_after>// This Source Code Form is subject to the terms of
// the Mozilla Public License, v. 2.0. If a copy of
// the MPL was not distributed with this file, You
// can obtain one at http://mozilla.org/MPL/2.0/.

//! CBOR ([RFC 7049](http://tools.ietf.org/html/rfc7049))
//! decoder implementation supporting the following features:
//!
//! - Generic decoding using an intermediate representation
//! - Tag validation
//! - Resource limits (e.g. maximum nesting level)
//! - Direct decoding into Rust types
//! - Indefinite sized bytes, strings, arrays and objects
//!
//! The module is structured as follows:
//!
//! 1. `Kernel` contains the basic decoding functionality, capable of
//! decoding simple unstructured types.
//! 2. `Decoder` directly decodes into native Rust types.
//! 3. `GenericDecoder` handles arbitrary CBOR items and decodes them
//! into an `Value` AST.
//!
//! # Example 1: Direct decoding
//!
//! ```
//! use cbor::{Config, Decoder};
//! use std::io::Cursor;
//!
//! let mut d = Decoder::new(Config::default(), Cursor::new(vec![0u8]));
//! assert_eq!(Some(0), d.u64().ok())
//! ```
//!
//! # Example 2: Direct decoding (nested array)
//!
//! ```
//! extern crate cbor;
//! extern crate rustc_serialize;
//!
//! use cbor::{Config, Decoder};
//! use rustc_serialize::hex::FromHex;
//! use std::io::Cursor;
//!
//! fn main() {
//!     let input   = Cursor::new("828301020383010203".from_hex().unwrap());
//!     let mut dec = Decoder::new(Config::default(), input);
//!     let mut res = Vec::new();
//!     for _ in 0 .. dec.array().unwrap() {
//!         let mut vec = Vec::new();
//!         for _ in 0 .. dec.array().unwrap() {
//!             vec.push(dec.u8().unwrap())
//!         }
//!         res.push(vec)
//!     }
//!     assert_eq!(vec![vec![1, 2, 3], vec![1, 2, 3]], res)
//! }
//! ```
//!
//! # Example 3: Generic decoding
//!
//! ```
//! extern crate cbor;
//! extern crate rustc_serialize;
//!
//! use cbor::{Config, GenericDecoder};
//! use cbor::value::{self, Key};
//! use rustc_serialize::hex::FromHex;
//! use std::io::Cursor;
//!
//! fn main() {
//!     let input = Cursor::new("a2616101028103".from_hex().unwrap());
//!     let mut d = GenericDecoder::new(Config::default(), input);
//!     let value = d.value().unwrap();
//!     let     c = value::Cursor::new(&value);
//!     assert_eq!(Some(1), c.field("a").u8());
//!     assert_eq!(Some(3), c.get(Key::U8(2)).at(0).u8())
//! }
//! ```
//!
//! # Example 4: Direct decoding (optional value)
//!
//! ```
//! use cbor::{opt, Config, Decoder};
//! use std::io::Cursor;
//!
//! let mut d = Decoder::new(Config::default(), Cursor::new(vec![0xF6]));
//! assert_eq!(None, opt(d.u8()).unwrap())
//! ```

use byteorder::{self, BigEndian, ReadBytesExt};
use std::collections::{BTreeMap, LinkedList};
use std::cmp::Eq;
use std::error::Error;
use std::f32;
use std::fmt::{self, Debug};
use std::io;
use std::string;
use skip::Skip;
use types::{Tag, Type};
use value::{self, Bytes, Key, Simple, Text, Value};

// Decoder Configuration ////////////////////////////////////////////////////

/// `Config` contains various settings which limit resource consumption
/// or enable certain validation options. Please note that the various
/// maximum length/size values apply to an individual element only.
///
/// This is mainly to prevent attackers from providing CBOR values whose
/// length is larger than the available memory. In combination the memory
/// consumption can still become large and it is best to limit the incoming
/// bytes to a specific upper bound, e.g. by using `std::io::Take`.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Config {
    /// Maximum number of array elements
    pub max_len_array: usize,
    /// Maximum length of a byte string
    pub max_len_bytes: usize,
    /// Maximum length of a string
    pub max_len_text: usize,
    /// Maximum number of object fields
    pub max_size_map: usize,
    /// Maximum recursion steps when decoder `Value`s
    pub max_nesting: usize,
    /// Ignore `Tag`s when decoding `Value`s
    pub skip_tags: bool,
    /// Validate `Value` type matches `Tag`.
    pub check_tags: bool
}

const DEFAULT_CONFIG: Config = Config
    { max_len_array: 1000
    , max_len_bytes: 0x500000
    , max_len_text: 0x500000
    , max_size_map: 1000
    , max_nesting: 16
    , skip_tags: false
    , check_tags: true
    };

impl Config {
    /// Create default configuration with
    ///
    /// - `max_len_array` = 1000
    /// - `max_len_bytes` = 5 MB
    /// - `max_len_text` = 5 MB
    /// - `max_size_map` = 1000
    /// - `max_nesting` = 16
    /// - `skip_tags` = false
    /// - `check_tags` = true
    pub fn default() -> Config { DEFAULT_CONFIG }
}

// Decode Error Type ////////////////////////////////////////////////////////

pub type DecodeResult<A> = Result<A, DecodeError>;

#[derive(Debug)]
pub enum DecodeError {
    /// An object contains the same key multiple times
    DuplicateKey(Box<Debug>),
    /// The decoded `Value` can not serve as a `Key` in an object
    InvalidKey(Value),
    /// The type of `Value` is not what is expected for a `Tag`
    InvalidTag(Value),
    /// The string is not encoded in UTF-8
    InvalidUtf8(string::FromUtf8Error),
    /// Some I/O error
    IoError(io::Error),
    /// The maximum configured length is exceeded
    TooLong { max: usize, actual: u64 },
    /// `Value`s are nested deeper than the configured maximum
    TooNested,
    /// The end of file has been encountered unexpectedly
    UnexpectedEOF,
    /// And unexpected type has been encountered
    UnexpectedType { datatype: Type, info: u8 },
    /// A break was encountered at some unexpected point while
    /// decoding an indefinite object.
    UnexpectedBreak
}

/// When decoding an optional item, i.e. a `Null` value has to be
/// considered, this function will map `Null` to `None` and any
/// other value to `Some(value)`.
pub fn opt<A>(r: DecodeResult<A>) -> DecodeResult<Option<A>> {
    match r {
        Ok(x)  => Ok(Some(x)),
        Err(e) => if is_null(&e) { Ok(None) } else { Err(e) }
    }
}

/// When decoding an item which may be `Undefined` this function
/// will map `Undefined` to `None` and any other value to `Some(value)`.
pub fn maybe<A>(r: DecodeResult<A>) -> DecodeResult<Option<A>> {
    match r {
        Ok(x)  => Ok(Some(x)),
        Err(e) => if is_undefined(&e) { Ok(None) } else { Err(e) }
    }
}

/// When decoding an indefinite item, every element item can be a `Break`
/// value. By wrapping it in `or_break`, this case can be handled more
/// conveniently.
pub fn or_break<A>(r: DecodeResult<A>) -> DecodeResult<Option<A>> {
    match r {
        Ok(x)  => Ok(Some(x)),
        Err(e) => if is_break(&e) { Ok(None) } else { Err(e) }
    }
}

fn is_break(e: &DecodeError) -> bool {
    match *e {
        DecodeError::UnexpectedType { datatype: Type::Break, .. } => true,
        _ => false
    }
}

fn is_null(e: &DecodeError) -> bool {
    match *e {
        DecodeError::UnexpectedType { datatype: Type::Null, .. } => true,
        _ => false
    }
}

fn is_undefined(e: &DecodeError) -> bool {
    match *e {
        DecodeError::UnexpectedType { datatype: Type::Undefined, .. } => true,
        _ => false
    }
}

impl fmt::Display for DecodeError {
    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        match *self {
            DecodeError::DuplicateKey(ref k) => write!(f, "DecodeError: duplicate key: {:?}", *k),
            DecodeError::InvalidKey(ref k)   => write!(f, "DecodeError: unsuitable map key: {:?}", *k),
            DecodeError::InvalidTag(ref v)   => write!(f, "DecodeError: value does not match tag: {:?}", *v),
            DecodeError::InvalidUtf8(ref e)  => write!(f, "DecodeError: Invalid UTF-8 encoding: {}", *e),
            DecodeError::IoError(ref e)      => write!(f, "DecodeError: I/O error: {}", *e),
            DecodeError::TooNested           => write!(f, "DecodeError: value is too nested"),
            DecodeError::UnexpectedEOF       => write!(f, "DecodeError: unexpected end-of-file"),
            DecodeError::UnexpectedBreak     => write!(f, "DecodeError: unexpected break"),
            DecodeError::TooLong{max:m, actual:a} => write!(f, "DecodeError: value is too long {} (max={})", a, m),
            DecodeError::UnexpectedType{datatype:t, info:i} => write!(f, "DecodeError: unexpected type {:?} (info={})", t, i)
        }
    }
}

impl Error for DecodeError {
    fn description(&self) -> &str {
        "DecodeError"
    }

    fn cause(&self) -> Option<&Error> {
        match *self {
            DecodeError::IoError(ref e)     => Some(e),
            DecodeError::InvalidUtf8(ref e) => Some(e),
            _                               => None
        }
    }
}

impl From<byteorder::Error> for DecodeError {
    fn from(e: byteorder::Error) -> DecodeError {
        match e {
            byteorder::Error::UnexpectedEOF => DecodeError::UnexpectedEOF,
            byteorder::Error::Io(e)         => DecodeError::IoError(e)
        }
    }
}

impl From<io::Error> for DecodeError {
    fn from(e: io::Error) -> DecodeError {
        DecodeError::IoError(e)
    }
}

impl From<string::FromUtf8Error> for DecodeError {
    fn from(e: string::FromUtf8Error) -> DecodeError {
        DecodeError::InvalidUtf8(e)
    }
}

// Decoder Kernel ///////////////////////////////////////////////////////////

pub type TypeInfo = (Type, u8);

/// This decoding kernel reads from an underlying `std::io::Read` type
/// primitive CBOR values such as unsigned and signed integers as well
/// as raw bytes.
/// It forms the basis on which `Decoder` and `GenericDecoder` add logic
/// for handling `Tag`s, heterogenous data and generic value decoding.
pub struct Kernel<R> {
    reader: R
}

impl<R: ReadBytesExt> Kernel<R> {
    pub fn new(r: R) -> Kernel<R> {
        Kernel { reader: r }
    }

    pub fn into_reader(self) -> R {
        self.reader
    }

    pub fn typeinfo(&mut self) -> DecodeResult<TypeInfo> {
        Type::read(&mut self.reader).map_err(From::from)
    }

    pub fn simple(&mut self, ti: &TypeInfo) -> DecodeResult<Simple> {
        match ti.0 {
            Type::Unassigned { major: 7, info: a } => Ok(Simple::Unassigned(a)),
            Type::Reserved   { major: 7, info: a } => Ok(Simple::Reserved(a)),
            _                                      => unexpected_type(ti)
        }
    }

    pub fn bool(&mut self, ti: &TypeInfo) -> DecodeResult<bool> {
        match *ti {
            (Type::Bool, 20) => Ok(false),
            (Type::Bool, 21) => Ok(true),
            _                => unexpected_type(ti)
        }
    }

    pub fn u8(&mut self, ti: &TypeInfo) -> DecodeResult<u8> {
        match *ti {
            (Type::UInt8, n @ 0...23) => Ok(n),
            (Type::UInt8, 24) => self.reader.read_u8().map_err(From::from),
            _                 => unexpected_type(ti)
        }
    }

    pub fn u16(&mut self, ti: &TypeInfo) -> DecodeResult<u16> {
        match *ti {
            (Type::UInt8, n @ 0...23) => Ok(n as u16),
            (Type::UInt8, 24)  => self.reader.read_u8().map(|n| n as u16).map_err(From::from),
            (Type::UInt16, 25) => self.reader.read_u16::<BigEndian>().map_err(From::from),
            _                  => unexpected_type(ti)
        }
    }

    pub fn u32(&mut self, ti: &TypeInfo) -> DecodeResult<u32> {
        match *ti {
            (Type::UInt8, n @ 0...23) => Ok(n as u32),
            (Type::UInt8, 24)  => self.reader.read_u8().map(|n| n as u32).map_err(From::from),
            (Type::UInt16, 25) => self.reader.read_u16::<BigEndian>().map(|n| n as u32).map_err(From::from),
            (Type::UInt32, 26) => self.reader.read_u32::<BigEndian>().map_err(From::from),
            _                  => unexpected_type(ti)
        }
    }

    pub fn u64(&mut self, ti: &TypeInfo) -> DecodeResult<u64> {
        match *ti {
            (Type::UInt8, n @ 0...23) => Ok(n as u64),
            (Type::UInt8, 24)  => self.reader.read_u8().map(|n| n as u64).map_err(From::from),
            (Type::UInt16, 25) => self.reader.read_u16::<BigEndian>().map(|n| n as u64).map_err(From::from),
            (Type::UInt32, 26) => self.reader.read_u32::<BigEndian>().map(|n| n as u64).map_err(From::from),
            (Type::UInt64, 27) => self.reader.read_u64::<BigEndian>().map_err(From::from),
            _                  => unexpected_type(ti)
        }
    }

    pub fn i8(&mut self, ti: &TypeInfo) -> DecodeResult<i8> {
        match *ti {
            (Type::Int8, n @ 0...23) => Ok(-1 - n as i8),
            (Type::Int8, 24) => self.reader.read_u8().map(|n| -1 - n as i8).map_err(From::from),
            _                => unexpected_type(ti)
        }
    }

    pub fn i16(&mut self, ti: &TypeInfo) -> DecodeResult<i16> {
        match *ti {
            (Type::Int8, n @ 0...23) => Ok(-1 - n as i16),
            (Type::Int8, 24)  => self.reader.read_u8().map(|n| -1 - n as i16).map_err(From::from),
            (Type::Int16, 25) => self.reader.read_u16::<BigEndian>().map(|n| -1 - n as i16).map_err(From::from),
            _                 => unexpected_type(ti)
        }
    }

    pub fn i32(&mut self, ti: &TypeInfo) -> DecodeResult<i32> {
        match *ti {
            (Type::Int8, n @ 0...23) => Ok(-1 - n as i32),
            (Type::Int8, 24)  => self.reader.read_u8().map(|n| -1 - n as i32).map_err(From::from),
            (Type::Int16, 25) => self.reader.read_u16::<BigEndian>().map(|n| -1 - n as i32).map_err(From::from),
            (Type::Int32, 26) => self.reader.read_u32::<BigEndian>().map(|n| -1 - n as i32).map_err(From::from),
            _                 => unexpected_type(ti)
        }
    }

    pub fn i64(&mut self, ti: &TypeInfo) -> DecodeResult<i64> {
        match *ti {
            (Type::Int8, n @ 0...23) => Ok(-1 - n as i64),
            (Type::Int8, 24)  => self.reader.read_u8().map(|n| -1 - n as i64).map_err(From::from),
            (Type::Int16, 25) => self.reader.read_u16::<BigEndian>().map(|n| -1 - n as i64).map_err(From::from),
            (Type::Int32, 26) => self.reader.read_u32::<BigEndian>().map(|n| -1 - n as i64).map_err(From::from),
            (Type::Int64, 27) => self.reader.read_u64::<BigEndian>().map(|n| -1 - n as i64).map_err(From::from),
            _                 => unexpected_type(ti)
        }
    }

    pub fn f16(&mut self, ti: &TypeInfo) -> DecodeResult<f32> {
        match ti.0 {
            Type::Float16 => {
                // Copied from RFC 7049 Appendix D:
                let half  = try!(self.reader.read_u16::<BigEndian>());
                let exp   = half >> 10 & 0x1F;
                let mant  = half & 0x3FF;
                let value = match exp {
                    0  => ffi::c_ldexpf(mant as f32, -24),
                    31 => if mant == 0 { f32::INFINITY } else { f32::NAN },
                    _  => ffi::c_ldexpf(mant as f32 + 1024.0, exp as isize - 25)
                };
                Ok(if half & 0x8000 == 0 { value } else { - value })
            }
            _ => unexpected_type(ti)
        }
    }

    pub fn f32(&mut self, ti: &TypeInfo) -> DecodeResult<f32> {
        match ti.0 {
            Type::Float32 => self.reader.read_f32::<BigEndian>().map_err(From::from),
            _             => unexpected_type(ti)
        }
    }

    pub fn f64(&mut self, ti: &TypeInfo) -> DecodeResult<f64> {
        match ti.0 {
            Type::Float64 => self.reader.read_f64::<BigEndian>().map_err(From::from),
            _             => unexpected_type(ti)
        }
    }

    /// Decode `first` and potentially the following bytes as an
    /// unsigned value following the rules of major type 0.
    pub fn unsigned(&mut self, first: u8) -> DecodeResult<u64> {
        match first {
            n @ 0...23 => Ok(n as u64),
            24 => self.reader.read_u8().map(|n| n as u64).map_err(From::from),
            25 => self.reader.read_u16::<BigEndian>().map(|n| n as u64).map_err(From::from),
            26 => self.reader.read_u32::<BigEndian>().map(|n| n as u64).map_err(From::from),
            27 => self.reader.read_u64::<BigEndian>().map_err(From::from),
            _  => unexpected_type(&(Type::UInt64, first))
        }
    }

    /// Read `begin` as the length and return that many raw bytes.
    /// If length is greater than the given `max_len`, `DecodeError::TooLong`
    /// is returned instead.
    pub fn raw_data(&mut self, begin: u8, max_len: usize) -> DecodeResult<Vec<u8>> {
        let len = try!(self.unsigned(begin));
        if len > max_len as u64 {
            return Err(DecodeError::TooLong { max: max_len, actual: len })
        }
        let n = len as usize;
        let mut v = vec![0u8; n];
        let mut i = 0;
        while i < n {
            match self.reader.read(&mut v[i..]) {
                Ok(0)  => return Err(DecodeError::UnexpectedEOF),
                Ok(j)  => i += j,
                Err(e) =>
                    if e.kind() != io::ErrorKind::Interrupted {
                        return Err(DecodeError::IoError(e))
                    }
            }
        }
        Ok(v)
    }
}

// Workaround to not require the currently unstable `f32::ldexp`:
mod ffi {
    use libc::c_int;

    extern {
        pub fn ldexpf(x: f32, exp: c_int) -> f32;
    }

    #[inline]
    pub fn c_ldexpf(x: f32, exp: isize) -> f32 {
        unsafe { ldexpf(x, exp as c_int) }
    }
}

fn unexpected_type<A>(ti: &TypeInfo) -> DecodeResult<A> {
    Err(DecodeError::UnexpectedType { datatype: ti.0, info: ti.1 })
}

// Decoder //////////////////////////////////////////////////////////////////

/// The actual decoder type definition
pub struct Decoder<R> {
    kernel: Kernel<R>,
    config: Config
}

impl<R: ReadBytesExt> Decoder<R> {
    pub fn new(c: Config, r: R) -> Decoder<R> {
        Decoder { kernel: Kernel::new(r), config: c }
    }

    pub fn into_reader(self) -> R {
        self.kernel.into_reader()
    }

    pub fn kernel<'x>(&'x mut self) -> &'x mut Kernel<R> {
        &mut self.kernel
    }

    pub fn simple(&mut self) -> DecodeResult<Simple> {
        self.typeinfo().and_then(|ti| self.kernel.simple(&ti))
    }

    pub fn bool(&mut self) -> DecodeResult<bool> {
        self.typeinfo().and_then(|ti| self.kernel.bool(&ti))
    }
{'fraction_non_alphanumeric': 0.1818579952920567, 'fraction_numerical': 0.025756829254940602, 'mean_word_length': 2.1805519282667363, 'pattern_counts': {'":': 0, '<': 143, '<?xml version=': 0, '>': 398, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4842887', 'n_tokens_mistral': 12649, 'n_tokens_neox': 11864, 'n_words': 3070}