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.

#[cfg(feature = "std")]
use std::fmt;
use core::{mem, ops::Deref, marker::PhantomData, iter::FromIterator, convert::TryFrom};

use arrayvec::ArrayVec;

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

const MAX_PREALLOCATION: usize = 4 * 1024;

/// Descriptive error type
#[cfg(feature = "std")]
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct Error(&'static str);

/// Undescriptive error type when compiled for no std
#[cfg(not(feature = "std"))]
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct Error;

impl Error {
	#[cfg(feature = "std")]
	/// Error description
	///
	/// This function returns an actual error str when running in `std`
	/// environment, but `""` on `no_std`.
	pub fn what(&self) -> &'static str {
		self.0
	}

	#[cfg(not(feature = "std"))]
	/// Error description
	///
	/// This function returns an actual error str when running in `std`
	/// environment, but `""` on `no_std`.
	pub fn what(&self) -> &'static str {
		""
	}
}

#[cfg(feature = "std")]
impl std::fmt::Display for Error {
	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
		write!(f, "{}", self.0)
	}
}

#[cfg(feature = "std")]
impl std::error::Error for Error {
	fn description(&self) -> &str {
		self.0
	}
}

impl From<&'static str> for Error {
	#[cfg(feature = "std")]
	fn from(s: &'static str) -> Error {
		Error(s)
	}

	#[cfg(not(feature = "std"))]
	fn from(_s: &'static str) -> Error {
		Error
	}
}

/// 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])
	}
}

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: Unkown".into(),
		}
	}
}

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

#[cfg(feature = "std")]
impl<R: std::io::Read + std::io::Seek> Input for IoReader<R> {
	fn remaining_len(&mut self) -> Result<Option<usize>, Error> {
		use std::convert::TryInto;
		use std::io::SeekFrom;

		let old_pos = self.0.seek(SeekFrom::Current(0))?;
		let len = self.0.seek(SeekFrom::End(0))?;

		// Avoid seeking a third time when we were already at the end of the
		// stream. The branch is usually way cheaper than a seek operation.
		if old_pos != len {
			self.0.seek(SeekFrom::Start(old_pos))?;
		}

		len.saturating_sub(old_pos)
			.try_into()
			.map_err(|_| "Input cannot fit into usize length".into())
			.map(Some)
	}

	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: Sized {
	/// 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]);
	}

	/// Write encoding of given value to the output.
	fn push<V: Encode + ?Sized>(&mut self, value: &V) {
		value.encode_to(self);
	}
}

#[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");
	}
}

/// This enum must not be exported and must only be instantiable by parity-scale-codec.
/// Because implementation of Encode and Decode for u8 is done in this crate
/// and there is not other usage.
pub enum IsU8 {
	Yes,
	No,
}

/// 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 {
	#[doc(hidden)]
	// This const is used to optimise implementation of codec for Vec<u8>.
	const IS_U8: IsU8 = IsU8::No;

	/// 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>(&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())
	}
}

/// 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 {
	#[doc(hidden)]
	const IS_U8: IsU8 = IsU8::No;

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

/// 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.
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 {}

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

	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 {}

	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>(&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> {
		Ok(T::decode(input)?.into())
	}
}

/// 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>(&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()? {
			0 => Ok(Ok(T::decode(input)?)),
			1 => Ok(Err(E::decode(input)?)),
			_ => 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 core::fmt::Debug for OptionBool {
	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::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>(&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()? {
			0 => Ok(None),
			1 => Ok(Some(T::decode(input)?)),
			_ => Err("unexpecded first byte decoding Option".into()),
		}
	}
}

macro_rules! impl_array {
	( $( $n:expr, )* ) => {
		$(
			impl<T: Encode> Encode for [T; $n] {
				fn encode_to<W: Output>(&self, dest: &mut W) {
					for item in self.iter() {
						item.encode_to(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!(
	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>(&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)
	}
}

#[cfg(any(feature = "std", feature = "full"))]
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>(&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> {
		Ok(Self::from_utf8_lossy(&Vec::decode(input)?).into())
	}
}

pub(crate) fn compact_encode_len_to<W: Output>(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 {
		if let IsU8::Yes = <T as Encode>::IS_U8 {
			self.len() + mem::size_of::<u32>()
		} else {
			0
		}
	}

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

		if let IsU8::Yes= <T as Encode>::IS_U8 {
			let self_transmute = unsafe {
				core::mem::transmute::<&[T], &[u8]>(self)
			};
			dest.write(self_transmute)
		} else {
			for item in self {
				item.encode_to(dest);
			}
		}
	}
}

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)| {
			let len = len as usize;
			if let IsU8::Yes = <T as Decode>::IS_U8 {
				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 < len).unwrap_or(false) {
					return Err("Not enough data to decode vector".into())
				}

				// Note: we checked that if input_len is some then it can preallocated.
				let r = if input_len.is_some() || len < MAX_PREALLOCATION {
					// Here we pre-allocate the whole buffer.
					let mut r = vec![0; len];
					input.read(&mut r)?;

					r
				} else {
					// Here we pre-allocate only the maximum pre-allocation
					let mut r = vec![];

					let mut remains = len;
					while remains != 0 {
						let len_read = MAX_PREALLOCATION.min(remains);
						let len_filled = r.len();
						r.resize(len_filled + len_read, 0);
						input.read(&mut r[len_filled..])?;
						remains -= len_read;
					}

					r
				};

				let r = unsafe { mem::transmute::<Vec<u8>, Vec<T>>(r) };
				Ok(r)
			} else {
				let capacity = input.remaining_len()?
					.unwrap_or(MAX_PREALLOCATION)
					.checked_div(mem::size_of::<T>())
					.unwrap_or(0);
				let mut r = Vec::with_capacity(capacity);
				for _ in 0..len {
					r.push(T::decode(input)?);
				}
				Ok(r)
			}
		})
	}
}

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 encode_to<W: Output>(&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)| {
					Result::from_iter((0..len).map(|_| Decode::decode(input)))
				})
			}
		}

		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 + Ord> EncodeLike for VecDeque<T> {}
impl<T: EncodeLike<U> + Ord, U: Encode> EncodeLike<&[U]> for VecDeque<T> {}
impl<T: EncodeLike<U>, U: Encode + Ord> EncodeLike<VecDeque<U>> for &[T] {}

impl<T: Encode + Ord> Encode for VecDeque<T> {
	fn encode_to<W: Output>(&self, dest: &mut W) {
		compact_encode_len_to(dest, self.len()).expect("Compact encodes length");

		if let IsU8::Yes = <T as Encode>::IS_U8 {
			let slices = self.as_slices();
			let slices_transmute = unsafe {
				core::mem::transmute::<(&[T], &[T]), (&[u8], &[u8])>(slices)
			};
			dest.write(slices_transmute.0);
			dest.write(slices_transmute.1);
		} else {
			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>(&self, _dest: &mut W) {
	}

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

	fn encode(&self) -> Vec<u8> {
		Vec::new()
	}
}

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

macro_rules! impl_len {
	( $( $type:ident< $($g:ident),* > ),* ) => { $(
		impl<$($g),*> DecodeLength for $type<$($g),*> {
			fn len(mut self_encoded: &[u8]) -> Result<usize, Error> {
				usize::try_from(u32::from(Compact::<u32>::decode(&mut self_encoded)?))
					.map_err(|_| "Failed convert decoded size into usize.".into())
			}
		}
	)*}
}

// Collection types that support compact decode length.
impl_len!(Vec<T>, BTreeSet<T>, BTreeMap<K, V>, VecDeque<T>, BinaryHeap<T>, LinkedList<T>);

macro_rules! tuple_impl {
	(
		($one:ident, $extra:ident),
	) => {
		impl<$one: Encode> Encode for ($one,) {
			fn size_hint(&self) -> usize {
				self.0.size_hint()
			}

			fn encode_to<T: Output>(&self, dest: &mut T) {
				self.0.encode_to(dest);
			}

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

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

		impl<$one: Decode> Decode for ($one,) {
			fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
				match $one::decode(input) {
					Err(e) => Err(e),
					Ok($one) => Ok(($one,)),
				}
			}
		}

		impl<$one: EncodeLike<$extra>, $extra: Encode> crate::EncodeLike<($extra,)> for ($one,) {}
	};
	(($first:ident, $fextra:ident), $( ( $rest:ident, $rextra:ident ), )+) => {
		impl<$first: Encode, $($rest: Encode),+> Encode for ($first, $($rest),+) {
			fn size_hint(&self) -> usize {
				let (
					ref $first,
					$(ref $rest),+
				) = *self;
				$first.size_hint()
				$( + $rest.size_hint() )+
			}

			fn encode_to<T: Output>(&self, dest: &mut T) {
				let (
					ref $first,
					$(ref $rest),+
				) = *self;

				$first.encode_to(dest);
				$($rest.encode_to(dest);)+
			}
		}

		impl<$first: Decode, $($rest: Decode),+> Decode for ($first, $($rest),+) {
			fn decode<INPUT: Input>(input: &mut INPUT) -> Result<Self, super::Error> {
				Ok((
					match $first::decode(input) {
						Ok(x) => x,
						Err(e) => return Err(e),
					},
					$(match $rest::decode(input) {
						Ok(x) => x,
						Err(e) => return Err(e),
					},)+
				))
			}
		}

		impl<$first: EncodeLike<$fextra>, $fextra: Encode,
			$($rest: EncodeLike<$rextra>, $rextra: Encode),+> crate::EncodeLike<($fextra, $( $rextra ),+)>
			for ($first, $($rest),+) {}

		tuple_impl!( $( ($rest, $rextra), )+ );
	}
}

#[allow(non_snake_case)]
mod inner_tuple_impl {
	use super::*;

	tuple_impl!(
		(A0, A1), (B0, B1), (C0, C1), (D0, D1), (E0, E1), (F0, F1), (G0, G1), (H0, H1), (I0, I1),
		(J0, J1), (K0, K1), (L0, L1), (M0, M1), (N0, N1), (O0, O1), (P0, P1), (Q0, Q1), (R0, R1),
	);
}

macro_rules! impl_endians {
	( $( $t:ty ),* ) => { $(
		impl EncodeLike for $t {}

		impl Encode for $t {
			fn size_hint(&self) -> usize {
				mem::size_of::<$t>()
			}

			fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
				let buf = self.to_le_bytes();
				f(&buf[..])
			}
		}

		impl Decode for $t {
			fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
				let mut buf = [0u8; mem::size_of::<$t>()];
				input.read(&mut buf)?;
				Ok(<$t>::from_le_bytes(buf))
			}
		}
	)* }
}
macro_rules! impl_one_byte {
	( $( $t:ty $( { $is_u8:ident } )? ),* ) => { $(
		impl EncodeLike for $t {}

		impl Encode for $t {
			$( const $is_u8: IsU8 = IsU8::Yes; )?

			fn size_hint(&self) -> usize {
				mem::size_of::<$t>()
			}

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

		impl Decode for $t {
			$( const $is_u8: IsU8 = IsU8::Yes; )?

			fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
				Ok(input.read_byte()? as $t)
			}
		}
	)* }
}

impl_endians!(u16, u32, u64, u128, i16, i32, i64, i128);
impl_one_byte!(u8 {IS_U8}, i8);

impl EncodeLike for bool {}

impl Encode for bool {
	fn size_hint(&self) -> usize {
		mem::size_of::<bool>()
	}

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

impl Decode for bool {
	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
		let byte = input.read_byte()?;
		match byte {
			0 => Ok(false),
			1 => Ok(true),
			_ => Err("Invalid boolean representation".into())
		}
	}
}

#[cfg(test)]
mod tests {
	use super::*;
	use std::borrow::Cow;

	#[test]
	fn vec_is_slicable() {
		let v = b"Hello world".to_vec();
		v.using_encoded(|ref slice|
			assert_eq!(slice, &b"\x2cHello world")
		);
	}

	#[test]
	fn encode_borrowed_tuple() {
		let x = vec![1u8, 2, 3, 4];
		let y = 128i64;

		let encoded = (&x, &y).encode();

		assert_eq!((x, y), Decode::decode(&mut &encoded[..]).unwrap());
	}

	#[test]
	fn cow_works() {
		let x = &[1u32, 2, 3, 4, 5, 6][..];