codec.rs

// Copyright 2017-2018 Parity Technologies
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! Serialisation.

use core::fmt;
use core::{mem, ops::Deref, marker::PhantomData, iter::FromIterator, convert::TryFrom, time::Duration};
use core::num::{
	NonZeroI8,
	NonZeroI16,
	NonZeroI32,
	NonZeroI64,
	NonZeroI128,
	NonZeroU8,
	NonZeroU16,
	NonZeroU32,
	NonZeroU64,
	NonZeroU128,
};
use arrayvec::ArrayVec;

use byte_slice_cast::{AsByteSlice, AsMutByteSlice, ToMutByteSlice};

#[cfg(any(feature = "std", feature = "full"))]
use crate::alloc::{
	string::String,
	sync::Arc,
	rc::Rc,
};
use crate::alloc::{
	vec::Vec,
	boxed::Box,
	borrow::{Cow, ToOwned},
	collections::{
		BTreeMap, BTreeSet, VecDeque, LinkedList, BinaryHeap
	}
};
use crate::compact::Compact;
use crate::encode_like::EncodeLike;
use crate::Error;

pub(crate) const MAX_PREALLOCATION: usize = 4 * 1024;
const A_BILLION: u32 = 1_000_000_000;

/// Trait that allows reading of data into a slice.
pub trait Input {
	/// Should return the remaining length of the input data. If no information about the input
	/// length is available, `None` should be returned.
	///
	/// The length is used to constrain the preallocation while decoding. Returning a garbage
	/// length can open the doors for a denial of service attack to your application.
	/// Otherwise, returning `None` can decrease the performance of your application.
	fn remaining_len(&mut self) -> Result<Option<usize>, Error>;

	/// Read the exact number of bytes required to fill the given buffer.
	///
	/// Note that this function is similar to `std::io::Read::read_exact` and not
	/// `std::io::Read::read`.
	fn read(&mut self, into: &mut [u8]) -> Result<(), Error>;

	/// Read a single byte from the input.
	fn read_byte(&mut self) -> Result<u8, Error> {
		let mut buf = [0u8];
		self.read(&mut buf[..])?;
		Ok(buf[0])
	}

	/// Descend into nested reference when decoding.
	/// This is called when decoding a new refence-based instance,
	/// such as `Vec` or `Box`. Currently all such types are
	/// allocated on the heap.
	fn descend_ref(&mut self) -> Result<(), Error> {
		Ok(())
	}

	/// Ascend to previous structure level when decoding.
	/// This is called when decoding reference-based type is finished.
	fn ascend_ref(&mut self) {}
}

impl<'a> Input for &'a [u8] {
	fn remaining_len(&mut self) -> Result<Option<usize>, Error> {
		Ok(Some(self.len()))
	}

	fn read(&mut self, into: &mut [u8]) -> Result<(), Error> {
		if into.len() > self.len() {
			return Err("Not enough data to fill buffer".into());
		}
		let len = into.len();
		into.copy_from_slice(&self[..len]);
		*self = &self[len..];
		Ok(())
	}
}

#[cfg(feature = "std")]
impl From<std::io::Error> for Error {
	fn from(err: std::io::Error) -> Self {
		use std::io::ErrorKind::*;
		match err.kind() {
			NotFound => "io error: NotFound".into(),
			PermissionDenied => "io error: PermissionDenied".into(),
			ConnectionRefused => "io error: ConnectionRefused".into(),
			ConnectionReset => "io error: ConnectionReset".into(),
			ConnectionAborted => "io error: ConnectionAborted".into(),
			NotConnected => "io error: NotConnected".into(),
			AddrInUse => "io error: AddrInUse".into(),
			AddrNotAvailable => "io error: AddrNotAvailable".into(),
			BrokenPipe => "io error: BrokenPipe".into(),
			AlreadyExists => "io error: AlreadyExists".into(),
			WouldBlock => "io error: WouldBlock".into(),
			InvalidInput => "io error: InvalidInput".into(),
			InvalidData => "io error: InvalidData".into(),
			TimedOut => "io error: TimedOut".into(),
			WriteZero => "io error: WriteZero".into(),
			Interrupted => "io error: Interrupted".into(),
			Other => "io error: Other".into(),
			UnexpectedEof => "io error: UnexpectedEof".into(),
			_ => "io error: Unknown".into(),
		}
	}
}

/// Wrapper that implements Input for any `Read` type.
#[cfg(feature = "std")]
pub struct IoReader<R: std::io::Read>(pub R);

#[cfg(feature = "std")]
impl<R: std::io::Read> Input for IoReader<R> {
	fn remaining_len(&mut self) -> Result<Option<usize>, Error> {
		Ok(None)
	}

	fn read(&mut self, into: &mut [u8]) -> Result<(), Error> {
		self.0.read_exact(into).map_err(Into::into)
	}
}

/// Trait that allows writing of data.
pub trait Output {
	/// Write to the output.
	fn write(&mut self, bytes: &[u8]);

	/// Write a single byte to the output.
	fn push_byte(&mut self, byte: u8) {
		self.write(&[byte]);
	}
}

#[cfg(not(feature = "std"))]
impl Output for Vec<u8> {
	fn write(&mut self, bytes: &[u8]) {
		self.extend_from_slice(bytes)
	}
}

#[cfg(feature = "std")]
impl<W: std::io::Write> Output for W {
	fn write(&mut self, bytes: &[u8]) {
		(self as &mut dyn std::io::Write).write_all(bytes).expect("Codec outputs are infallible");
	}
}


/// !INTERNAL USE ONLY!
///
/// This enum provides type information to optimize encoding/decoding by doing fake specialization.
#[doc(hidden)]
#[non_exhaustive]
pub enum TypeInfo {
	/// Default value of [`Encode::TYPE_INFO`] to not require implementors to set this value in the trait.
	Unknown,
	U8,
	I8,
	U16,
	I16,
	U32,
	I32,
	U64,
	I64,
	U128,
	I128,
}

/// Trait that allows zero-copy write of value-references to slices in LE format.
///
/// Implementations should override `using_encoded` for value types and `encode_to` and `size_hint` for allocating types.
/// Wrapper types should override all methods.
pub trait Encode {
	// !INTERNAL USE ONLY!
	// This const helps SCALE to optimize the encoding/decoding by doing fake specialization.
	#[doc(hidden)]
	const TYPE_INFO: TypeInfo = TypeInfo::Unknown;

	/// If possible give a hint of expected size of the encoding.
	///
	/// This method is used inside default implementation of `encode`
	/// to avoid re-allocations.
	fn size_hint(&self) -> usize {
		0
	}

	/// Convert self to a slice and append it to the destination.
	fn encode_to<T: Output + ?Sized>(&self, dest: &mut T) {
		self.using_encoded(|buf| dest.write(buf));
	}

	/// Convert self to an owned vector.
	fn encode(&self) -> Vec<u8> {
		let mut r = Vec::with_capacity(self.size_hint());
		self.encode_to(&mut r);
		r
	}

	/// Convert self to a slice and then invoke the given closure with it.
	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
		f(&self.encode())
	}

	/// Calculates the encoded size.
	///
	/// Should be used when the encoded data isn't required.
	///
	/// # Note
	///
	/// This works by using a special [`Output`] that only tracks the size. So, there are no allocations inside the 
	/// output. However, this can not prevent allocations that some types are doing inside their own encoding. 
	fn encoded_size(&self) -> usize {
		let mut size_tracker = SizeTracker { written: 0 };
		self.encode_to(&mut size_tracker);
		size_tracker.written
	}
}

// Implements `Output` and only keeps track of the number of written bytes
struct SizeTracker {
	written: usize,
}

impl Output for SizeTracker {
	fn write(&mut self, bytes: &[u8]) {
		self.written += bytes.len();
	}

	fn push_byte(&mut self, _byte: u8) {
		self.written += 1;
	}
}

/// Trait that allows the length of a collection to be read, without having
/// to read and decode the entire elements.
pub trait DecodeLength {
	/// Return the number of elements in `self_encoded`.
	fn len(self_encoded: &[u8]) -> Result<usize, Error>;
}

/// Trait that allows zero-copy read of value-references from slices in LE format.
pub trait Decode: Sized {
	// !INTERNAL USE ONLY!
	// This const helps SCALE to optimize the encoding/decoding by doing fake specialization.
	#[doc(hidden)]
	const TYPE_INFO: TypeInfo = TypeInfo::Unknown;

	/// Attempt to deserialise the value from input.
	fn decode<I: Input>(input: &mut I) -> Result<Self, Error>;

	/// Attempt to skip the encoded value from input.
	///
	/// The default implementation of this function is just calling [`Decode::decode`].
	/// When possible, an implementation should provided a specialized implementation.
	fn skip<I: Input>(input: &mut I) -> Result<(), Error> {
		Self::decode(input).map(|_| ())
	}

	/// Returns the fixed encoded size of the type.
	///
	/// If it returns `Some(size)` then all possible values of this
	/// type have the given size (in bytes) when encoded.
	///
	/// NOTE: A type with a fixed encoded size may return `None`.
	fn encoded_fixed_size() -> Option<usize> {
		None
	}
}

/// Trait that allows zero-copy read/write of value-references to/from slices in LE format.
pub trait Codec: Decode + Encode {}
impl<S: Decode + Encode> Codec for S {}

/// Trait that bound `EncodeLike` along with `Encode`. Usefull for generic being used in function
/// with `EncodeLike` parameters.
pub trait FullEncode: Encode + EncodeLike {}
impl<S: Encode + EncodeLike> FullEncode for S {}

/// Trait that bound `EncodeLike` along with `Codec`. Usefull for generic being used in function
/// with `EncodeLike` parameters.
pub trait FullCodec: Decode + FullEncode {}
impl<S: Decode + FullEncode> FullCodec for S {}

/// A marker trait for types that wrap other encodable type.
///
/// Such types should not carry any additional information
/// that would require to be encoded, because the encoding
/// is assumed to be the same as the wrapped type.
///
/// The wrapped type that is referred to is the [`Deref::Target`].
pub trait WrapperTypeEncode: Deref {}

impl<T: ?Sized> WrapperTypeEncode for Box<T> {}
impl<T: ?Sized + Encode> EncodeLike for Box<T> {}
impl<T: Encode> EncodeLike<T> for Box<T> {}
impl<T: Encode> EncodeLike<Box<T>> for T {}

impl<T: ?Sized> WrapperTypeEncode for &T {}
impl<T: ?Sized + Encode> EncodeLike for &T {}
impl<T: Encode> EncodeLike<T> for &T {}
impl<T: Encode> EncodeLike<&T> for T {}
impl<T: Encode> EncodeLike<T> for &&T {}
impl<T: Encode> EncodeLike<&&T> for T {}

impl<T: ?Sized> WrapperTypeEncode for &mut T {}
impl<T: ?Sized + Encode> EncodeLike for &mut T {}
impl<T: Encode> EncodeLike<T> for &mut T {}
impl<T: Encode> EncodeLike<&mut T> for T {}

impl<'a, T: ToOwned + ?Sized> WrapperTypeEncode for Cow<'a, T> {}
impl<'a, T: ToOwned + Encode + ?Sized> EncodeLike for Cow<'a, T> {}
impl<'a, T: ToOwned + Encode> EncodeLike<T> for Cow<'a, T> {}
impl<'a, T: ToOwned + Encode> EncodeLike<Cow<'a, T>> for T {}

#[cfg(any(feature = "std", feature = "full"))]
mod feature_full_wrapper_type_encode {
	use super::*;

	impl<T: ?Sized> WrapperTypeEncode for Arc<T> {}
	impl<T: ?Sized + Encode> EncodeLike for Arc<T> {}
	impl<T: Encode> EncodeLike<T> for Arc<T> {}
	impl<T: Encode> EncodeLike<Arc<T>> for T {}

	impl<T: ?Sized> WrapperTypeEncode for Rc<T> {}
	impl<T: ?Sized + Encode> EncodeLike for Rc<T> {}
	impl<T: Encode> EncodeLike<T> for Rc<T> {}
	impl<T: Encode> EncodeLike<Rc<T>> for T {}

	impl WrapperTypeEncode for String {}
	impl EncodeLike for String {}
	impl EncodeLike<&str> for String {}
	impl EncodeLike<String> for &str {}
}

impl<T, X> Encode for X where
	T: Encode + ?Sized,
	X: WrapperTypeEncode<Target = T>,
{
	fn size_hint(&self) -> usize {
		(&**self).size_hint()
	}

	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
		(&**self).using_encoded(f)
	}

	fn encode(&self) -> Vec<u8> {
		(&**self).encode()
	}

	fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
		(&**self).encode_to(dest)
	}
}

/// A marker trait for types that can be created solely from other decodable types.
///
/// The decoding of such type is assumed to be the same as the wrapped type.
pub trait WrapperTypeDecode: Sized {
	/// A wrapped type.
	type Wrapped: Into<Self>;
}
impl<T> WrapperTypeDecode for Box<T> {
	type Wrapped = T;
}
#[cfg(any(feature = "std", feature = "full"))]
impl<T> WrapperTypeDecode for Arc<T> {
	type Wrapped = T;
}
#[cfg(any(feature = "std", feature = "full"))]
impl<T> WrapperTypeDecode for Rc<T> {
	type Wrapped = T;
}

impl<T, X> Decode for X where
	T: Decode + Into<X>,
	X: WrapperTypeDecode<Wrapped=T>,
{
	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
		input.descend_ref()?;
		let result = Ok(T::decode(input)?.into());
		input.ascend_ref();
		result
	}

}

/// A macro that matches on a [`TypeInfo`] and expands a given macro per variant.
///
/// The first parameter to the given macro will be the type of variant (e.g. `u8`, `u32`, etc.) and other parameters
/// given to this macro.
///
/// The last parameter is the code that should be executed for the `Unknown` type info.
macro_rules! with_type_info {
	( $type_info:expr, $macro:ident $( ( $( $params:ident ),* ) )?, { $( $unknown_variant:tt )* }, ) => {
		match $type_info {
			TypeInfo::U8 => { $macro!(u8 $( $( , $params )* )? ) },
			TypeInfo::I8 => { $macro!(i8 $( $( , $params )* )? ) },
			TypeInfo::U16 => { $macro!(u16 $( $( , $params )* )? ) },
			TypeInfo::I16 => { $macro!(i16 $( $( , $params )* )? ) },
			TypeInfo::U32 => { $macro!(u32 $( $( , $params )* )? ) },
			TypeInfo::I32 => { $macro!(i32 $( $( , $params )* )? ) },
			TypeInfo::U64 => { $macro!(u64 $( $( , $params )* )? ) },
			TypeInfo::I64 => { $macro!(i64 $( $( , $params )* )? ) },
			TypeInfo::U128 => { $macro!(u128 $( $( , $params )* )? ) },
			TypeInfo::I128 => { $macro!(i128 $( $( , $params )* )? ) },
			TypeInfo::Unknown => { $( $unknown_variant )* },
		}
	};
}

/// Something that can be encoded as a reference.
pub trait EncodeAsRef<'a, T: 'a> {
	/// The reference type that is used for encoding.
	type RefType: Encode + From<&'a T>;
}

impl<T: Encode, E: Encode> Encode for Result<T, E> {
	fn size_hint(&self) -> usize {
		1 + match *self {
			Ok(ref t) => t.size_hint(),
			Err(ref t) => t.size_hint(),
		}
	}

	fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
		match *self {
			Ok(ref t) => {
				dest.push_byte(0);
				t.encode_to(dest);
			}
			Err(ref e) => {
				dest.push_byte(1);
				e.encode_to(dest);
			}
		}
	}
}

impl<T, LikeT, E, LikeE> EncodeLike<Result<LikeT, LikeE>> for Result<T, E>
where
	T: EncodeLike<LikeT>,
	LikeT: Encode,
	E: EncodeLike<LikeE>,
	LikeE: Encode,
{}

impl<T: Decode, E: Decode> Decode for Result<T, E> {
	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
		match input.read_byte()
			.map_err(|e| e.chain("Could not result variant byte for `Result`"))?
		{
			0 => Ok(
				Ok(T::decode(input).map_err(|e| e.chain("Could not Decode `Result::Ok(T)`"))?)
			),
			1 => Ok(
				Err(E::decode(input).map_err(|e| e.chain("Could not decode `Result::Error(E)`"))?)
			),
			_ => Err("unexpected first byte decoding Result".into()),
		}
	}
}

/// Shim type because we can't do a specialised implementation for `Option<bool>` directly.
#[derive(Eq, PartialEq, Clone, Copy)]
pub struct OptionBool(pub Option<bool>);

impl fmt::Debug for OptionBool {
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
		self.0.fmt(f)
	}
}

impl Encode for OptionBool {
	fn size_hint(&self) -> usize {
		1
	}

	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
		f(&[match *self {
			OptionBool(None) => 0u8,
			OptionBool(Some(true)) => 1u8,
			OptionBool(Some(false)) => 2u8,
		}])
	}
}

impl EncodeLike for OptionBool {}

impl Decode for OptionBool {
	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
		match input.read_byte()? {
			0 => Ok(OptionBool(None)),
			1 => Ok(OptionBool(Some(true))),
			2 => Ok(OptionBool(Some(false))),
			_ => Err("unexpected first byte decoding OptionBool".into()),
		}
	}
}

impl<T: EncodeLike<U>, U: Encode> EncodeLike<Option<U>> for Option<T> {}

impl<T: Encode> Encode for Option<T> {
	fn size_hint(&self) -> usize {
		1 + match *self {
			Some(ref t) => t.size_hint(),
			None => 0,
		}
	}

	fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
		match *self {
			Some(ref t) => {
				dest.push_byte(1);
				t.encode_to(dest);
			}
			None => dest.push_byte(0),
		}
	}
}

impl<T: Decode> Decode for Option<T> {
	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
		match input.read_byte()
			.map_err(|e| e.chain("Could not decode variant byte for `Option`"))?
		{
			0 => Ok(None),
			1 => Ok(
				Some(T::decode(input).map_err(|e| e.chain("Could not decode `Option::Some(T)`"))?)
			),
			_ => Err("unexpected first byte decoding Option".into()),
		}
	}
}

macro_rules! impl_for_non_zero {
	( $( $name:ty ),* $(,)? ) => {
		$(
			impl Encode for $name {
				fn size_hint(&self) -> usize {
					self.get().size_hint()
				}

				fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
					self.get().encode_to(dest)
				}

				fn encode(&self) -> Vec<u8> {
					self.get().encode()
				}

				fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
					self.get().using_encoded(f)
				}
			}

			impl Decode for $name {
				fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
					Self::new(Decode::decode(input)?)
						.ok_or_else(|| Error::from("cannot create non-zero number from 0"))
				}
			}
		)*
	}
}

/// Encode the slice without prepending the len.
///
/// This is equivalent to encoding all the element one by one, but it is optimized for some types.
pub(crate) fn encode_slice_no_len<T: Encode, W: Output + ?Sized>(slice: &[T], dest: &mut W) {
	macro_rules! encode_to {
		( u8, $slice:ident, $dest:ident ) => {{
			let typed = unsafe { mem::transmute::<&[T], &[u8]>(&$slice[..]) };
			$dest.write(&typed)
		}};
		( i8, $slice:ident, $dest:ident ) => {{
			// `i8` has the same size as `u8`. We can just convert it here and write to the
			// dest buffer directly.
			let typed = unsafe { mem::transmute::<&[T], &[u8]>(&$slice[..]) };
			$dest.write(&typed)
		}};
		( $ty:ty, $slice:ident, $dest:ident ) => {{
			if cfg!(target_endian = "little") {
				let typed = unsafe { mem::transmute::<&[T], &[$ty]>(&$slice[..]) };
				$dest.write(<[$ty] as AsByteSlice<$ty>>::as_byte_slice(typed))
			} else {
				for item in $slice.iter() {
					item.encode_to(dest);
				}
			}
		}};
	}

	with_type_info! {
		<T as Encode>::TYPE_INFO,
		encode_to(slice, dest),
		{
			for item in slice.iter() {
				item.encode_to(dest);
			}
		},
	}
}

/// Decode the slice (without prepended the len).
///
/// This is equivalent to decode all elements one by one, but it is optimized in some
/// situation.
pub(crate) fn decode_vec_with_len<T: Decode, I: Input>(
	input: &mut I,
	len: usize,
) -> Result<Vec<T>, Error> {
	fn decode_unoptimized<I: Input, T: Decode>(
		input: &mut I,
		items_len: usize,
	) -> Result<Vec<T>, Error> {
		let input_capacity = input.remaining_len()?
			.unwrap_or(MAX_PREALLOCATION)
			.checked_div(mem::size_of::<T>())
			.unwrap_or(0);
		let mut r = Vec::with_capacity(input_capacity.min(items_len));
		input.descend_ref()?;
		for _ in 0..items_len {
			r.push(T::decode(input)?);
		}
		input.ascend_ref();
		Ok(r)
	}

	macro_rules! decode {
		( $ty:ty, $input:ident, $len:ident ) => {{
			if cfg!(target_endian = "little") || mem::size_of::<T>() == 1 {
				let vec = read_vec_from_u8s::<_, $ty>($input, $len)?;
				Ok(unsafe { mem::transmute::<Vec<$ty>, Vec<T>>(vec) })
			} else {
				decode_unoptimized($input, $len)
			}
		}};
	}

	with_type_info! {
		<T as Decode>::TYPE_INFO,
		decode(input, len),
		{
			decode_unoptimized(input, len)
		},
	}
}

impl_for_non_zero! {
	NonZeroI8,
	NonZeroI16,
	NonZeroI32,
	NonZeroI64,
	NonZeroI128,
	NonZeroU8,
	NonZeroU16,
	NonZeroU32,
	NonZeroU64,
	NonZeroU128,
}

macro_rules! impl_array {
	( $( $n:expr, )* ) => {
		$(
			impl<T: Encode> Encode for [T; $n] {
				fn size_hint(&self) -> usize {
					mem::size_of::<T>() * $n
				}

				fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
					encode_slice_no_len(&self[..], dest)
				}
			}

			impl<T: Decode> Decode for [T; $n] {
				fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
					let mut r = ArrayVec::new();
					for _ in 0..$n {
						r.push(T::decode(input)?);
					}
					let i = r.into_inner();

					match i {
						Ok(a) => Ok(a),
						Err(_) => Err("failed to get inner array from ArrayVec".into()),
					}
				}
			}

			impl<T: EncodeLike<U>, U: Encode> EncodeLike<[U; $n]> for [T; $n] {}
		)*
	}
}

impl_array!(
	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
	17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
	32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51,
	52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71,
	72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91,
	92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108,
	109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124,
	125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140,
	141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156,
	157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172,
	173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188,
	189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204,
	205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220,
	221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236,
	237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252,
	253, 254, 255, 256, 384, 512, 768, 1024, 2048, 4096, 8192, 16384, 32768,
);

impl Encode for str {
	fn size_hint(&self) -> usize {
		self.as_bytes().size_hint()
	}

	fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
		self.as_bytes().encode_to(dest)
	}

	fn encode(&self) -> Vec<u8> {
		self.as_bytes().encode()
	}

	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
		self.as_bytes().using_encoded(f)
	}
}

impl<'a, T: ToOwned + ?Sized> Decode for Cow<'a, T>
	where <T as ToOwned>::Owned: Decode,
{
	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
		Ok(Cow::Owned(Decode::decode(input)?))
	}
}

impl<T> EncodeLike for PhantomData<T> {}

impl<T> Encode for PhantomData<T> {
	fn encode_to<W: Output + ?Sized>(&self, _dest: &mut W) {}
}

impl<T> Decode for PhantomData<T> {
	fn decode<I: Input>(_input: &mut I) -> Result<Self, Error> {
		Ok(PhantomData)
	}
}

#[cfg(any(feature = "std", feature = "full"))]
impl Decode for String {
	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
		Self::from_utf8(Vec::decode(input)?).map_err(|_| "Invalid utf8 sequence".into())
	}
}

/// Writes the compact encoding of `len` do `dest`.
pub(crate) fn compact_encode_len_to<W: Output + ?Sized>(dest: &mut W, len: usize) -> Result<(), Error> {
	if len > u32::max_value() as usize {
		return Err("Attempted to serialize a collection with too many elements.".into());
	}

	Compact(len as u32).encode_to(dest);
	Ok(())
}

impl<T: Encode> Encode for [T] {
	fn size_hint(&self) -> usize {
		mem::size_of::<u32>() + mem::size_of::<T>() * self.len()
	}

	fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
		compact_encode_len_to(dest, self.len()).expect("Compact encodes length");

		encode_slice_no_len(self, dest)
	}
}

/// Create a `Vec<T>` by casting directly from a buffer of read `u8`s
///
/// The encoding of `T` must be equal to its binary representation, and size of `T` must be less or
/// equal to [`MAX_PREALLOCATION`].
pub(crate) fn read_vec_from_u8s<I, T>(input: &mut I, items_len: usize) -> Result<Vec<T>, Error>
where
	I: Input,
	T: ToMutByteSlice + Default + Clone,
{
	debug_assert!(MAX_PREALLOCATION >= mem::size_of::<T>(), "Invalid precondition");

	let byte_len = items_len.checked_mul(mem::size_of::<T>())
		.ok_or_else(|| "Item is too big and cannot be allocated")?;

	let input_len = input.remaining_len()?;

	// If there is input len and it cannot be pre-allocated then return directly.
	if input_len.map(|l| l < byte_len).unwrap_or(false) {
		return Err("Not enough data to decode vector".into())
	}

	// In both these branches we're going to be creating and resizing a Vec<T>,
	// but casting it to a &mut [u8] for reading.

	// Note: we checked that if input_len is some then it can preallocated.
	let r = if input_len.is_some() || byte_len < MAX_PREALLOCATION {
		// Here we pre-allocate the whole buffer.
		let mut items: Vec<T> = vec![Default::default(); items_len];
		let mut bytes_slice = items.as_mut_byte_slice();
		input.read(&mut bytes_slice)?;

		items
	} else {
		// An allowed number of preallocated item.
		// Note: `MAX_PREALLOCATION` is expected to be more or equal to size of `T`, precondition.
		let max_preallocated_items = MAX_PREALLOCATION / mem::size_of::<T>();

		// Here we pre-allocate only the maximum pre-allocation
		let mut items: Vec<T> = vec![];

		let mut items_remains = items_len;

		while items_remains > 0 {
			let items_len_read = max_preallocated_items.min(items_remains);

			let items_len_filled = items.len();
			let items_new_size = items_len_filled + items_len_read;

			items.reserve_exact(items_len_read);
			unsafe {
				items.set_len(items_new_size);
			}

			let bytes_slice = items.as_mut_byte_slice();
			let bytes_len_filled = items_len_filled * mem::size_of::<T>();
			input.read(&mut bytes_slice[bytes_len_filled..])?;

			items_remains = items_remains.saturating_sub(items_len_read);
		}

		items
	};

	Ok(r)
}

impl<T> WrapperTypeEncode for Vec<T> {}
impl<T: EncodeLike<U>, U: Encode> EncodeLike<Vec<U>> for Vec<T> {}
impl<T: EncodeLike<U>, U: Encode> EncodeLike<&[U]> for Vec<T> {}
impl<T: EncodeLike<U>, U: Encode> EncodeLike<Vec<U>> for &[T] {}

impl<T: Decode> Decode for Vec<T> {
	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
		<Compact<u32>>::decode(input).and_then(move |Compact(len)| {
			decode_vec_with_len(input, len as usize)
		})
	}
}

macro_rules! impl_codec_through_iterator {
	($(
		$type:ident
		{ $( $generics:ident $( : $decode_additional:ident )? ),* }
		{ $( $type_like_generics:ident ),* }
		{ $( $impl_like_generics:tt )* }
	)*) => {$(
		impl<$( $generics: Encode ),*> Encode for $type<$( $generics, )*> {
			fn size_hint(&self) -> usize {
				mem::size_of::<u32>() $( + mem::size_of::<$generics>() * self.len() )*
			}

			fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
				compact_encode_len_to(dest, self.len()).expect("Compact encodes length");

				for i in self.iter() {
					i.encode_to(dest);
				}
			}
		}

		impl<$( $generics: Decode $( + $decode_additional )? ),*> Decode
			for $type<$( $generics, )*>
		{
			fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
				<Compact<u32>>::decode(input).and_then(move |Compact(len)| {
					input.descend_ref()?;
					let result = Result::from_iter((0..len).map(|_| Decode::decode(input)));
					input.ascend_ref();
					result
				})
			}
		}

		impl<$( $impl_like_generics )*> EncodeLike<$type<$( $type_like_generics ),*>>
			for $type<$( $generics ),*> {}
		impl<$( $impl_like_generics )*> EncodeLike<&[( $( $type_like_generics, )* )]>
			for $type<$( $generics ),*> {}
		impl<$( $impl_like_generics )*> EncodeLike<$type<$( $type_like_generics ),*>>
			for &[( $( $generics, )* )] {}
	)*}
}

impl_codec_through_iterator! {
	BTreeMap { K: Ord, V } { LikeK, LikeV}
		{ K: EncodeLike<LikeK>, LikeK: Encode, V: EncodeLike<LikeV>, LikeV: Encode }
	BTreeSet { T: Ord } { LikeT }
		{ T: EncodeLike<LikeT>, LikeT: Encode }
	LinkedList { T } { LikeT }
		{ T: EncodeLike<LikeT>, LikeT: Encode }
	BinaryHeap { T: Ord } { LikeT }
		{ T: EncodeLike<LikeT>, LikeT: Encode }
}

impl<T: Encode> EncodeLike for VecDeque<T> {}
impl<T: EncodeLike<U>, U: Encode> EncodeLike<&[U]> for VecDeque<T> {}
impl<T: EncodeLike<U>, U: Encode> EncodeLike<VecDeque<U>> for &[T] {}
impl<T: EncodeLike<U>, U: Encode> EncodeLike<Vec<U>> for VecDeque<T> {}
impl<T: EncodeLike<U>, U: Encode> EncodeLike<VecDeque<U>> for Vec<T> {}

impl<T: Encode> Encode for VecDeque<T> {
	fn size_hint(&self) -> usize {
		mem::size_of::<u32>() + mem::size_of::<T>() * self.len()
	}

	fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
		compact_encode_len_to(dest, self.len()).expect("Compact encodes length");

		macro_rules! encode_to {
			( $ty:ty, $self:ident, $dest:ident ) => {{
				if cfg!(target_endian = "little") || mem::size_of::<T>() == 1 {
					let slices = $self.as_slices();
					let typed = unsafe {
						core::mem::transmute::<(&[T], &[T]), (&[$ty], &[$ty])>(slices)
					};

					$dest.write(<[$ty] as AsByteSlice<$ty>>::as_byte_slice(typed.0));
					$dest.write(<[$ty] as AsByteSlice<$ty>>::as_byte_slice(typed.1));
				} else {
					for item in $self {
						item.encode_to($dest);
					}
				}
			}};
		}

		with_type_info! {
			<T as Encode>::TYPE_INFO,
			encode_to(self, dest),
			{
				for item in self {
					item.encode_to(dest);
				}
			},
		}
	}
}

impl<T: Decode> Decode for VecDeque<T> {
	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
		Ok(<Vec<T>>::decode(input)?.into())
	}
}

impl EncodeLike for () {}

impl Encode for () {
	fn encode_to<W: Output + ?Sized>(&self, _dest: &mut W) {
	}

	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
		f(&[])