// This file is part of Substrate.

// Copyright (C) Parity Technologies (UK) Ltd.

// SPDX-License-Identifier: Apache-2.0

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

//! Merkle Mountain Range primitive types.

#![cfg_attr(not(feature = "std"), no_std)]

#![warn(missing_docs)]

extern crate alloc;

pub use mmr_lib;

#[cfg(not(feature = "std"))]

use alloc::vec::Vec;

use core::fmt;

use scale_info::TypeInfo;

use sp_debug_derive::RuntimeDebug;

use sp_runtime::traits;

pub mod utils;

/// Prefix for elements stored in the Off-chain DB via Indexing API.

pub const INDEXING_PREFIX: &'static [u8] = b"mmr";

/// A type to describe node position in the MMR (node index).

pub type NodeIndex = u64;

/// A type to describe leaf position in the MMR.

///

/// Note this is different from [`NodeIndex`], which can be applied to

/// both leafs and inner nodes. Leafs will always have consecutive `LeafIndex`,

/// but might be actually at different positions in the MMR `NodeIndex`.

pub type LeafIndex = u64;

/// A provider of the MMR's leaf data.

pub trait LeafDataProvider {

	/// A type that should end up in the leaf of MMR.

	type LeafData: FullLeaf + codec::Decode;

	/// The method to return leaf data that should be placed

	/// in the leaf node appended MMR at this block.

	///

	/// This is being called by the `on_initialize` method of

	/// this pallet at the very beginning of each block.

	fn leaf_data() -> Self::LeafData;

}

impl LeafDataProvider for () {

	type LeafData = ();

}

/// New MMR root notification hook.

pub trait OnNewRoot<Hash> {

	/// Function called by the pallet in case new MMR root has been computed.

	fn on_new_root(root: &Hash);

}

/// No-op implementation of [OnNewRoot].

impl<Hash> OnNewRoot<Hash> for () {

}

/// A full leaf content stored in the offchain-db.

pub trait FullLeaf: Clone + PartialEq + fmt::Debug {

	/// Encode the leaf either in its full or compact form.

	///

	/// NOTE the encoding returned here MUST be `Decode`able into `FullLeaf`.

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

}

impl<T: codec::Encode + codec::Decode + Clone + PartialEq + fmt::Debug> FullLeaf for T {

}

/// A helper type to allow using arbitrary SCALE-encoded leaf data in the RuntimeApi.

///

/// The point is to be able to verify MMR proofs from external MMRs, where we don't

/// know the exact leaf type, but it's enough for us to have it SCALE-encoded.

///

/// Note the leaf type should be encoded in its compact form when passed through this type.

/// See [FullLeaf] documentation for details.

///

/// This type does not implement SCALE encoding/decoding on purpose to avoid confusion,

/// it would have to be SCALE-compatible with the concrete leaf type, but due to SCALE limitations

/// it's not possible to know how many bytes the encoding of concrete leaf type uses.

pub struct OpaqueLeaf(

	/// Raw bytes of the leaf type encoded in its compact form.

	///

	/// NOTE it DOES NOT include length prefix (like `Vec<u8>` encoding would).

	#[cfg_attr(feature = "serde", serde(with = "sp_core::bytes"))]

	pub Vec<u8>,

);

impl OpaqueLeaf {

	/// Convert a concrete MMR leaf into an opaque type.

	/// Create a `OpaqueLeaf` given raw bytes of compact-encoded leaf.

	/// Attempt to decode the leaf into expected concrete type.

}

impl FullLeaf for OpaqueLeaf {

}

/// A type-safe wrapper for the concrete leaf type.

///

/// This structure serves merely to avoid passing raw `Vec<u8>` around.

/// It must be `Vec<u8>`-encoding compatible.

///

/// It is different from [`OpaqueLeaf`], because it does implement `Codec`

/// and the encoding has to match raw `Vec<u8>` encoding.

pub struct EncodableOpaqueLeaf(pub Vec<u8>);

impl EncodableOpaqueLeaf {

	/// Convert a concrete leaf into encodable opaque version.

	/// Given an opaque leaf, make it encodable.

	/// Try to convert into a [OpaqueLeaf].

}

/// An element representing either full data or its hash.

///

/// See [Compact] to see how it may be used in practice to reduce the size

/// of proofs in case multiple [LeafDataProvider]s are composed together.

/// This is also used internally by the MMR to differentiate leaf nodes (data)

/// and inner nodes (hashes).

///

/// [DataOrHash::hash] method calculates the hash of this element in its compact form,

/// so should be used instead of hashing the encoded form (which will always be non-compact).

pub enum DataOrHash<H: traits::Hash, L> {

	/// Arbitrary data in its full form.

	Data(L),

	/// A hash of some data.

	Hash(H::Output),

}

impl<H: traits::Hash, L> From<L> for DataOrHash<H, L> {

}

mod encoding {

	use super::*;

	/// A helper type to implement [codec::Codec] for [DataOrHash].

	enum Either<A, B> {

	}

	impl<H: traits::Hash, L: FullLeaf> codec::Encode for DataOrHash<H, L> {

			}

	}

	impl<H: traits::Hash, L: FullLeaf + codec::Decode> codec::Decode for DataOrHash<H, L> {

			})

	}

}

impl<H: traits::Hash, L: FullLeaf> DataOrHash<H, L> {

	/// Retrieve a hash of this item.

	///

	/// Depending on the node type it's going to either be a contained value for [DataOrHash::Hash]

	/// node, or a hash of SCALE-encoded [DataOrHash::Data] data.

		}

}

/// A composition of multiple leaf elements with compact form representation.

///

/// When composing together multiple [LeafDataProvider]s you will end up with

/// a tuple of `LeafData` that each element provides.

///

/// However this will cause the leaves to have significant size, while for some

/// use cases it will be enough to prove only one element of the tuple.

/// That's the rationale for [Compact] struct. We wrap each element of the tuple

/// into [DataOrHash] and each tuple element is hashed first before constructing

/// the final hash of the entire tuple. This allows you to replace tuple elements

/// you don't care about with their hashes.

pub struct Compact<H, T> {

	/// Internal tuple representation.

	pub tuple: T,

	_hash: core::marker::PhantomData<H>,

}

impl<H, T> core::ops::Deref for Compact<H, T> {

	type Target = T;

}

impl<H, T> Compact<H, T> {

	/// Create a new [Compact] wrapper for a tuple.

}

impl<H, T: codec::Decode> codec::Decode for Compact<H, T> {

}

macro_rules! impl_leaf_data_for_tuple {

	( $( $name:ident : $id:tt ),+ ) => {

		/// [FullLeaf] implementation for `Compact<H, (DataOrHash<H, Tuple>, ...)>`

		impl<H, $( $name ),+> FullLeaf for Compact<H, ( $( DataOrHash<H, $name>, )+ )> where

			H: traits::Hash,

			$( $name: FullLeaf ),+

		{

				} else {

				}

		}

		/// [LeafDataProvider] implementation for `Compact<H, (DataOrHash<H, Tuple>, ...)>`

		///

		/// This provides a compact-form encoding for tuples wrapped in [Compact].

		impl<H, $( $name ),+> LeafDataProvider for Compact<H, ( $( $name, )+ )> where

			H: traits::Hash,

			$( $name: LeafDataProvider ),+

		{

			type LeafData = Compact<

				H,

				( $( DataOrHash<H, $name::LeafData>, )+ ),

			>;

		}

		/// [LeafDataProvider] implementation for `(Tuple, ...)`

		///

		/// This provides regular (non-compactable) composition of [LeafDataProvider]s.

		impl<$( $name ),+> LeafDataProvider for ( $( $name, )+ ) where

			( $( $name::LeafData, )+ ): FullLeaf,

			$( $name: LeafDataProvider ),+

		{

			type LeafData = ( $( $name::LeafData, )+ );

		}

	}

}

/// Test functions implementation for `Compact<H, (DataOrHash<H, Tuple>, ...)>`

#[cfg(test)]

impl<H, A, B> Compact<H, (DataOrHash<H, A>, DataOrHash<H, B>)>

where

	H: traits::Hash,

	A: FullLeaf,

	B: FullLeaf,

{

	/// Retrieve a hash of this item in its compact form.

	pub fn hash(&self) -> H::Output {

		self.using_encoded(<H as traits::Hash>::hash, true)

	}

}

impl_leaf_data_for_tuple!(A:0);

impl_leaf_data_for_tuple!(A:0, B:1);

impl_leaf_data_for_tuple!(A:0, B:1, C:2);

impl_leaf_data_for_tuple!(A:0, B:1, C:2, D:3);

impl_leaf_data_for_tuple!(A:0, B:1, C:2, D:3, E:4);

/// An MMR proof data for a group of leaves.

pub struct LeafProof<Hash> {

	/// The indices of the leaves the proof is for.

	pub leaf_indices: Vec<LeafIndex>,

	/// Number of leaves in MMR, when the proof was generated.

	pub leaf_count: NodeIndex,

	/// Proof elements (hashes of siblings of inner nodes on the path to the leafs).

	pub items: Vec<Hash>,

}

/// An MMR ancestry proof for a prior mmr root.

pub struct AncestryProof<Hash> {

	/// Peaks of the ancestor's mmr

	pub prev_peaks: Vec<Hash>,

	/// Number of leaves in the ancestor's MMR.

	pub prev_leaf_count: u64,

	/// Number of leaves in MMR, when the proof was generated.

	pub leaf_count: NodeIndex,

	/// Proof elements

	/// (positions and hashes of siblings of inner nodes on the path to the previous peaks).

	pub items: Vec<(u64, Hash)>,

}

/// Merkle Mountain Range operation error.

pub enum Error {

}

impl Error {

	#![allow(unused_variables)]

	/// Consume given error `e` with `self` and generate a native log entry with error details.

			target: "runtime::mmr",

			self,

			e,

		);

	/// Consume given error `e` with `self` and generate a native log entry with error details.

			target: "runtime::mmr",

			self,

			e,

		);

}

#[cfg(test)]

mod tests {

	use super::*;

	use codec::Decode;

	use sp_core::H256;

	use sp_runtime::traits::Keccak256;

	pub(crate) fn hex(s: &str) -> H256 {

		s.parse().unwrap()

	}

	type Test = DataOrHash<Keccak256, String>;

	type TestCompact = Compact<Keccak256, (Test, Test)>;

	type TestProof = LeafProof<<Keccak256 as traits::Hash>::Output>;

	#[test]

	fn should_encode_decode_proof() {

		// given

		let proof: TestProof = LeafProof {

			leaf_indices: vec![5],

			leaf_count: 10,

			items: vec![

				hex("c3e7ba6b511162fead58f2c8b5764ce869ed1118011ac37392522ed16720bbcd"),

				hex("d3e7ba6b511162fead58f2c8b5764ce869ed1118011ac37392522ed16720bbcd"),

				hex("e3e7ba6b511162fead58f2c8b5764ce869ed1118011ac37392522ed16720bbcd"),

			],

		};

		// when

		let encoded = codec::Encode::encode(&proof);

		let decoded = TestProof::decode(&mut &*encoded);

		// then

		assert_eq!(decoded, Ok(proof));

	}

	#[test]

	fn should_encode_decode_correctly_if_no_compact() {

		// given

		let cases = vec![

			Test::Data("Hello World!".into()),

			Test::Hash(hex("c3e7ba6b511162fead58f2c8b5764ce869ed1118011ac37392522ed16720bbcd")),

			Test::Data("".into()),

			Test::Data("3e48d6bcd417fb22e044747242451e2c0f3e602d1bcad2767c34808621956417".into()),

		];

		// when

		let encoded = cases.iter().map(codec::Encode::encode).collect::<Vec<_>>();

		let decoded = encoded.iter().map(|x| Test::decode(&mut &**x)).collect::<Vec<_>>();

		// then

		assert_eq!(

			decoded,

			cases.into_iter().map(Result::<_, codec::Error>::Ok).collect::<Vec<_>>()

		);

		// check encoding correctness

		assert_eq!(

			&encoded[0],

			&array_bytes::hex2bytes_unchecked("00343048656c6c6f20576f726c6421")

		);

		assert_eq!(

			encoded[1].as_slice(),

			array_bytes::hex2bytes_unchecked(

				"01c3e7ba6b511162fead58f2c8b5764ce869ed1118011ac37392522ed16720bbcd"

			)

			.as_slice()

		);

	}

	#[test]

	fn should_return_the_hash_correctly() {

		// given

		let a = Test::Data("Hello World!".into());

		let b = Test::Hash(hex("c3e7ba6b511162fead58f2c8b5764ce869ed1118011ac37392522ed16720bbcd"));

		// when

		let a = a.hash();

		let b = b.hash();

		// then

		assert_eq!(a, hex("a9c321be8c24ba4dc2bd73f5300bde67dc57228ab8b68b607bb4c39c5374fac9"));

		assert_eq!(b, hex("c3e7ba6b511162fead58f2c8b5764ce869ed1118011ac37392522ed16720bbcd"));

	}

	#[test]

	fn compact_should_work() {

		// given

		let a = Test::Data("Hello World!".into());

		let b = Test::Data("".into());

		// when

		let c: TestCompact = Compact::new((a.clone(), b.clone()));

		let d: TestCompact = Compact::new((Test::Hash(a.hash()), Test::Hash(b.hash())));

		// then

		assert_eq!(c.hash(), d.hash());

	}

	#[test]

	fn compact_should_encode_decode_correctly() {

		// given

		let a = Test::Data("Hello World!".into());

		let b = Test::Data("".into());

		let c: TestCompact = Compact::new((a.clone(), b.clone()));

		let d: TestCompact = Compact::new((Test::Hash(a.hash()), Test::Hash(b.hash())));

		let cases = vec![c, d.clone()];

		// when

		let encoded_compact =

			cases.iter().map(|c| c.using_encoded(|x| x.to_vec(), true)).collect::<Vec<_>>();

		let encoded =

			cases.iter().map(|c| c.using_encoded(|x| x.to_vec(), false)).collect::<Vec<_>>();

		let decoded_compact = encoded_compact

			.iter()

			.map(|x| TestCompact::decode(&mut &**x))

			.collect::<Vec<_>>();

		let decoded = encoded.iter().map(|x| TestCompact::decode(&mut &**x)).collect::<Vec<_>>();

		// then

		assert_eq!(

			decoded,

			cases.into_iter().map(Result::<_, codec::Error>::Ok).collect::<Vec<_>>()

		);

		assert_eq!(decoded_compact, vec![Ok(d.clone()), Ok(d.clone())]);

	}

	#[test]

	fn opaque_leaves_should_be_full_leaf_compatible() {

		// given

		let a = Test::Data("Hello World!".into());

		let b = Test::Data("".into());

		let c: TestCompact = Compact::new((a.clone(), b.clone()));

		let d: TestCompact = Compact::new((Test::Hash(a.hash()), Test::Hash(b.hash())));

		let cases = vec![c, d.clone()];

		let encoded_compact = cases

			.iter()

			.map(|c| c.using_encoded(|x| x.to_vec(), true))

			.map(OpaqueLeaf::from_encoded_leaf)

			.collect::<Vec<_>>();

		let opaque = cases.iter().map(OpaqueLeaf::from_leaf).collect::<Vec<_>>();

		// then

		assert_eq!(encoded_compact, opaque);

	}

	#[test]

	fn encode_opaque_leaf_should_be_scale_compatible() {

		use codec::Encode;

		// given

		let a = Test::Data("Hello World!".into());

		let case1 = EncodableOpaqueLeaf::from_leaf(&a);

		let case2 = EncodableOpaqueLeaf::from_opaque_leaf(OpaqueLeaf(a.encode()));

		let case3 = a.encode().encode();

		// when

		let encoded = vec![&case1, &case2].into_iter().map(|x| x.encode()).collect::<Vec<_>>();

		let decoded = vec![&*encoded[0], &*encoded[1], &*case3]

			.into_iter()

			.map(|x| EncodableOpaqueLeaf::decode(&mut &*x))

			.collect::<Vec<_>>();

		// then

		assert_eq!(case1, case2);

		assert_eq!(encoded[0], encoded[1]);

		// then encoding should also match double-encoded leaf.

		assert_eq!(encoded[0], case3);

		assert_eq!(decoded[0], decoded[1]);

		assert_eq!(decoded[1], decoded[2]);

		assert_eq!(decoded[0], Ok(case2));

		assert_eq!(decoded[1], Ok(case1));

	}

}