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

// This file is part of Polkadot.

// Polkadot is free software: you can redistribute it and/or modify

// it under the terms of the GNU General Public License as published by

// the Free Software Foundation, either version 3 of the License, or

// (at your option) any later version.

// Polkadot is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License

// along with Polkadot.  If not, see <http://www.gnu.org/licenses/>.

//! Cross-Consensus Message format data structures.

use super::Junction;

use crate::v3::MultiLocation as NewMultiLocation;

use codec::{Decode, Encode, MaxEncodedLen};

use core::{mem, result};

use scale_info::TypeInfo;

/// A relative path between state-bearing consensus systems.

///

/// A location in a consensus system is defined as an *isolatable state machine* held within global

/// consensus. The location in question need not have a sophisticated consensus algorithm of its

/// own; a single account within Ethereum, for example, could be considered a location.

///

/// A very-much non-exhaustive list of types of location include:

/// - A (normal, layer-1) block chain, e.g. the Bitcoin mainnet or a parachain.

/// - A layer-0 super-chain, e.g. the Polkadot Relay chain.

/// - A layer-2 smart contract, e.g. an ERC-20 on Ethereum.

/// - A logical functional component of a chain, e.g. a single instance of a pallet on a Frame-based

///   Substrate chain.

/// - An account.

///

/// A `MultiLocation` is a *relative identifier*, meaning that it can only be used to define the

/// relative path between two locations, and cannot generally be used to refer to a location

/// universally. It is comprised of an integer number of parents specifying the number of times to

/// "escape" upwards into the containing consensus system and then a number of *junctions*, each

/// diving down and specifying some interior portion of state (which may be considered a

/// "sub-consensus" system).

///

/// This specific `MultiLocation` implementation uses a `Junctions` datatype which is a Rust `enum`

/// in order to make pattern matching easier. There are occasions where it is important to ensure

/// that a value is strictly an interior location, in those cases, `Junctions` may be used.

///

/// The `MultiLocation` value of `Null` simply refers to the interpreting consensus system.

#[scale_info(replace_segment("staging_xcm", "xcm"))]

pub struct MultiLocation {

	/// The number of parent junctions at the beginning of this `MultiLocation`.

	pub parents: u8,

	/// The interior (i.e. non-parent) junctions that this `MultiLocation` contains.

	pub interior: Junctions,

}

impl Default for MultiLocation {

}

/// A relative location which is constrained to be an interior location of the context.

///

/// See also `MultiLocation`.

pub type InteriorMultiLocation = Junctions;

impl MultiLocation {

	/// Creates a new `MultiLocation` with the given number of parents and interior junctions.

	/// Consume `self` and return the equivalent `VersionedLocation` value.

	/// Creates a new `MultiLocation` with 0 parents and a `Here` interior.

	///

	/// The resulting `MultiLocation` can be interpreted as the "current consensus system".

	/// Creates a new `MultiLocation` which evaluates to the parent context.

	/// Creates a new `MultiLocation` which evaluates to the grand parent context.

	/// Creates a new `MultiLocation` with `parents` and an empty (`Here`) interior.

	/// Whether the `MultiLocation` has no parents and has a `Here` interior.

	/// Return a reference to the interior field.

	/// Return a mutable reference to the interior field.

	/// Returns the number of `Parent` junctions at the beginning of `self`.

	/// Returns boolean indicating whether `self` contains only the specified amount of

	/// parents and no interior junctions.

	/// Returns the number of parents and junctions in `self`.

	/// Returns the first interior junction, or `None` if the location is empty or contains only

	/// parents.

	/// Returns last junction, or `None` if the location is empty or contains only parents.

	/// Splits off the first interior junction, returning the remaining suffix (first item in tuple)

	/// and the first element (second item in tuple) or `None` if it was empty.

	/// Splits off the last interior junction, returning the remaining prefix (first item in tuple)

	/// and the last element (second item in tuple) or `None` if it was empty or if `self` only

	/// contains parents.

	/// Mutates `self`, suffixing its interior junctions with `new`. Returns `Err` with `new` in

	/// case of overflow.

	/// Mutates `self`, prefixing its interior junctions with `new`. Returns `Err` with `new` in

	/// case of overflow.

	/// Consumes `self` and returns a `MultiLocation` suffixed with `new`, or an `Err` with

	/// the original value of `self` in case of overflow.

		}

	/// Consumes `self` and returns a `MultiLocation` prefixed with `new`, or an `Err` with the

	/// original value of `self` in case of overflow.

		}

	/// Returns the junction at index `i`, or `None` if the location is a parent or if the location

	/// does not contain that many elements.

	/// Returns a mutable reference to the junction at index `i`, or `None` if the location is a

	/// parent or if it doesn't contain that many elements.

	/// Decrements the parent count by 1.

	/// Removes the first interior junction from `self`, returning it

	/// (or `None` if it was empty or if `self` contains only parents).

	/// Removes the last element from `interior`, returning it (or `None` if it was empty or if

	/// `self` only contains parents).

	/// Ensures that `self` has the same number of parents as `prefix`, its junctions begins with

	/// the junctions of `prefix` and that it has a single `Junction` item following.

	/// If so, returns a reference to this `Junction` item.

	///

	/// # Example

	/// ```rust

	/// # use staging_xcm::v2::{Junctions::*, Junction::*, MultiLocation};

	/// let mut m = MultiLocation::new(1, [PalletInstance(3), OnlyChild].into());

	/// assert_eq!(

	///     m.match_and_split(&MultiLocation::new(1, [PalletInstance(3)].into())),

	///     Some(&OnlyChild),

	/// );

	/// assert_eq!(m.match_and_split(&MultiLocation::new(1, Here)), None);

	/// ```

	/// Returns whether `self` has the same number of parents as `prefix` and its junctions begins

	/// with the junctions of `prefix`.

	///

	/// # Example

	/// ```rust

	/// # use staging_xcm::v2::{Junctions::*, Junction::*, MultiLocation};

	/// let m = MultiLocation::new(1, [PalletInstance(3), OnlyChild, OnlyChild].into());

	/// assert!(m.starts_with(&MultiLocation::new(1, [PalletInstance(3)].into())));

	/// assert!(!m.starts_with(&MultiLocation::new(1, [GeneralIndex(99)].into())));

	/// assert!(!m.starts_with(&MultiLocation::new(0, [PalletInstance(3)].into())));

	/// ```

	/// Mutate `self` so that it is suffixed with `suffix`.

	///

	/// Does not modify `self` and returns `Err` with `suffix` in case of overflow.

	///

	/// # Example

	/// ```rust

	/// # use staging_xcm::v2::{Junctions::*, Junction::*, MultiLocation};

	/// let mut m = MultiLocation::new(1, [Parachain(21)].into());

	/// assert_eq!(m.append_with([PalletInstance(3)].into()), Ok(()));

	/// assert_eq!(m, MultiLocation::new(1, [Parachain(21), PalletInstance(3)].into()));

	/// ```

		}

	/// Mutate `self` so that it is prefixed with `prefix`.

	///

	/// Does not modify `self` and returns `Err` with `prefix` in case of overflow.

	///

	/// # Example

	/// ```rust

	/// # use staging_xcm::v2::{Junctions::*, Junction::*, MultiLocation};

	/// let mut m = MultiLocation::new(2, [PalletInstance(3)].into());

	/// assert_eq!(m.prepend_with(MultiLocation::new(1, [Parachain(21), OnlyChild].into())), Ok(()));

	/// assert_eq!(m, MultiLocation::new(1, [PalletInstance(3)].into()));

	/// ```

		// cancel out the final item on the prefix interior for one of the suffix's parents.

		// now we have either removed all suffix's parents or prefix interior.

		// this means we can combine the prefix's and suffix's remaining parents/interior since

		// we know that with at least one empty, the overall order will be respected:

		//     prefix     self (suffix)

		// P .. P   (I)   p .. p i .. i => P + p .. (no I) i

		//  -- or --

		// P .. P I .. I    (p)  i .. i => P (no p) .. I + i

	/// Consume `self` and return the value representing the same location from the point of view

	/// of `target`. The context of `self` is provided as `ancestry`.

	///

	/// Returns an `Err` with the unmodified `self` in the case of error.

		}

	/// Mutate `self` so that it represents the same location from the point of view of `target`.

	/// The context of `self` is provided as `ancestry`.

	///

	/// Does not modify `self` in case of overflow.

		// TODO: https://github.com/paritytech/polkadot/issues/4489 Optimize this.

		// 1. Use our `ancestry` to figure out how the `target` would address us.

		// 2. Prepend `inverted_target` to `self` to get self's location from the perspective of

		// `target`.

		// 3. Given that we know some of `target` ancestry, ensure that any parents in `self` are

		// strictly needed.

	/// Treating `self` as a context, determine how it would be referenced by a `target` location.

		use Junction::OnlyChild;

		}

	/// Remove any unneeded parents/junctions in `self` based on the given context it will be

	/// interpreted in.

			// Not enough context

			}

		}

}

impl TryFrom<NewMultiLocation> for MultiLocation {

	type Error = ();

}

/// A unit struct which can be converted into a `MultiLocation` of `parents` value 1.

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]

pub struct Parent;

impl From<Parent> for MultiLocation {

}

/// A tuple struct which can be converted into a `MultiLocation` of `parents` value 1 with the inner

/// interior.

#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Debug)]

pub struct ParentThen(pub Junctions);

impl From<ParentThen> for MultiLocation {

}

/// A unit struct which can be converted into a `MultiLocation` of the inner `parents` value.

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]

pub struct Ancestor(pub u8);

impl From<Ancestor> for MultiLocation {

}

/// A unit struct which can be converted into a `MultiLocation` of the inner `parents` value and the

/// inner interior.

#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Debug)]

pub struct AncestorThen<Interior>(pub u8, pub Interior);

impl<Interior: Into<Junctions>> From<AncestorThen<Interior>> for MultiLocation {

}

/// Maximum number of `Junction`s that a `Junctions` can contain.

const MAX_JUNCTIONS: usize = 8;

/// Non-parent junctions that can be constructed, up to the length of 8. This specific `Junctions`

/// implementation uses a Rust `enum` in order to make pattern matching easier.

///

/// Parent junctions cannot be constructed with this type. Refer to `MultiLocation` for

/// instructions on constructing parent junctions.

#[scale_info(replace_segment("staging_xcm", "xcm"))]

pub enum Junctions {

}

pub struct JunctionsIterator(Junctions);

impl Iterator for JunctionsIterator {

	type Item = Junction;

}

impl DoubleEndedIterator for JunctionsIterator {

}

pub struct JunctionsRefIterator<'a> {

	junctions: &'a Junctions,

	next: usize,

	back: usize,

}

impl<'a> Iterator for JunctionsRefIterator<'a> {

	type Item = &'a Junction;

}

impl<'a> DoubleEndedIterator for JunctionsRefIterator<'a> {

		// checked_sub here, because if the result is less than 0, we end iteration

}

impl<'a> IntoIterator for &'a Junctions {

	type Item = &'a Junction;

	type IntoIter = JunctionsRefIterator<'a>;

}

impl IntoIterator for Junctions {

	type Item = Junction;

	type IntoIter = JunctionsIterator;

}

impl Junctions {

	/// Convert `self` into a `MultiLocation` containing 0 parents.

	///

	/// Similar to `Into::into`, except that this method can be used in a const evaluation context.

	/// Convert `self` into a `MultiLocation` containing `n` parents.

	///

	/// Similar to `Self::into`, with the added ability to specify the number of parent junctions.

	/// Returns first junction, or `None` if the location is empty.

		}

	/// Returns last junction, or `None` if the location is empty.

		}

	/// Splits off the first junction, returning the remaining suffix (first item in tuple) and the

	/// first element (second item in tuple) or `None` if it was empty.

		}

	/// Splits off the last junction, returning the remaining prefix (first item in tuple) and the

	/// last element (second item in tuple) or `None` if it was empty.

		}

	/// Removes the first element from `self`, returning it (or `None` if it was empty).

	/// Removes the last element from `self`, returning it (or `None` if it was empty).

	/// Mutates `self` to be appended with `new` or returns an `Err` with `new` if would overflow.

			},

			},

		}

	/// Mutates `self` to be prepended with `new` or returns an `Err` with `new` if would overflow.

			},

			},

		}

	/// Consumes `self` and returns a `Junctions` suffixed with `new`, or an `Err` with the

	/// original value of `self` and `new` in case of overflow.

		})

	/// Consumes `self` and returns a `Junctions` prefixed with `new`, or an `Err` with the

	/// original value of `self` and `new` in case of overflow.

		})

	/// Returns the number of junctions in `self`.

		}

	/// Returns the junction at index `i`, or `None` if the location doesn't contain that many

	/// elements.

		})

	/// Returns a mutable reference to the junction at index `i`, or `None` if the location doesn't

	/// contain that many elements.

		})

	/// Returns a reference iterator over the junctions.

	/// Returns a reference iterator over the junctions in reverse.

	#[deprecated(note = "Please use iter().rev()")]

	/// Consumes `self` and returns an iterator over the junctions in reverse.

	#[deprecated(note = "Please use into_iter().rev()")]

	/// Ensures that self begins with `prefix` and that it has a single `Junction` item following.

	/// If so, returns a reference to this `Junction` item.

	///

	/// # Example

	/// ```rust

	/// # use staging_xcm::v2::{Junctions::*, Junction::*};

	/// let mut m = X3(Parachain(2), PalletInstance(3), OnlyChild);

	/// assert_eq!(m.match_and_split(&X2(Parachain(2), PalletInstance(3))), Some(&OnlyChild));

	/// assert_eq!(m.match_and_split(&X1(Parachain(2))), None);

	/// ```

	/// Returns whether `self` begins with or is equal to `prefix`.

	///

	/// # Example

	/// ```rust

	/// # use staging_xcm::v2::{Junctions::*, Junction::*};

	/// let mut j = X3(Parachain(2), PalletInstance(3), OnlyChild);

	/// assert!(j.starts_with(&X2(Parachain(2), PalletInstance(3))));

	/// assert!(j.starts_with(&j));

	/// assert!(j.starts_with(&X1(Parachain(2))));

	/// assert!(!j.starts_with(&X1(Parachain(999))));

	/// assert!(!j.starts_with(&X4(Parachain(2), PalletInstance(3), OnlyChild, OnlyChild)));

	/// ```

}

impl TryFrom<MultiLocation> for Junctions {

	type Error = ();

		} else {

		}

}

#[cfg(test)]

mod tests {

	use super::{Ancestor, AncestorThen, Junctions::*, MultiLocation, Parent, ParentThen};

	use crate::opaque::v2::{Junction::*, NetworkId::*};

	use codec::{Decode, Encode};

	#[test]

	fn inverted_works() {

		let ancestry: MultiLocation = (Parachain(1000), PalletInstance(42)).into();

		let target = (Parent, PalletInstance(69)).into();

		let expected = (Parent, PalletInstance(42)).into();

		let inverted = ancestry.inverted(&target).unwrap();

		assert_eq!(inverted, expected);

		let ancestry: MultiLocation = (Parachain(1000), PalletInstance(42), GeneralIndex(1)).into();

		let target = (Parent, Parent, PalletInstance(69), GeneralIndex(2)).into();

		let expected = (Parent, Parent, PalletInstance(42), GeneralIndex(1)).into();

		let inverted = ancestry.inverted(&target).unwrap();

		assert_eq!(inverted, expected);

	}

	#[test]

	fn simplify_basic_works() {

		let mut location: MultiLocation =

			(Parent, Parent, Parachain(1000), PalletInstance(42), GeneralIndex(69)).into();

		let context = X2(Parachain(1000), PalletInstance(42));

		let expected = GeneralIndex(69).into();

		location.simplify(&context);

		assert_eq!(location, expected);

		let mut location: MultiLocation = (Parent, PalletInstance(42), GeneralIndex(69)).into();

		let context = X1(PalletInstance(42));

		let expected = GeneralIndex(69).into();

		location.simplify(&context);

		assert_eq!(location, expected);

		let mut location: MultiLocation = (Parent, PalletInstance(42), GeneralIndex(69)).into();

		let context = X2(Parachain(1000), PalletInstance(42));

		let expected = GeneralIndex(69).into();

		location.simplify(&context);

		assert_eq!(location, expected);

		let mut location: MultiLocation =

			(Parent, Parent, Parachain(1000), PalletInstance(42), GeneralIndex(69)).into();

		let context = X3(OnlyChild, Parachain(1000), PalletInstance(42));

		let expected = GeneralIndex(69).into();

		location.simplify(&context);

		assert_eq!(location, expected);

	}

	#[test]

	fn simplify_incompatible_location_fails() {

		let mut location: MultiLocation =

			(Parent, Parent, Parachain(1000), PalletInstance(42), GeneralIndex(69)).into();

		let context = X3(Parachain(1000), PalletInstance(42), GeneralIndex(42));

		let expected =

			(Parent, Parent, Parachain(1000), PalletInstance(42), GeneralIndex(69)).into();

		location.simplify(&context);

		assert_eq!(location, expected);

		let mut location: MultiLocation =

			(Parent, Parent, Parachain(1000), PalletInstance(42), GeneralIndex(69)).into();

		let context = X1(Parachain(1000));

		let expected =

			(Parent, Parent, Parachain(1000), PalletInstance(42), GeneralIndex(69)).into();

		location.simplify(&context);

		assert_eq!(location, expected);

	}

	#[test]

	fn reanchor_works() {

		let mut id: MultiLocation = (Parent, Parachain(1000), GeneralIndex(42)).into();

		let ancestry = Parachain(2000).into();

		let target = (Parent, Parachain(1000)).into();

		let expected = GeneralIndex(42).into();

		id.reanchor(&target, &ancestry).unwrap();

		assert_eq!(id, expected);

	}

	#[test]

	fn encode_and_decode_works() {

		let m = MultiLocation {

			parents: 1,

			interior: X2(Parachain(42), AccountIndex64 { network: Any, index: 23 }),

		};

		let encoded = m.encode();

		assert_eq!(encoded, [1, 2, 0, 168, 2, 0, 92].to_vec());

		let decoded = MultiLocation::decode(&mut &encoded[..]);

		assert_eq!(decoded, Ok(m));

	}

	#[test]

	fn match_and_split_works() {

		let m = MultiLocation {

			parents: 1,

			interior: X2(Parachain(42), AccountIndex64 { network: Any, index: 23 }),

		};

		assert_eq!(m.match_and_split(&MultiLocation { parents: 1, interior: Here }), None);

		assert_eq!(

			m.match_and_split(&MultiLocation { parents: 1, interior: X1(Parachain(42)) }),

			Some(&AccountIndex64 { network: Any, index: 23 })

		);

		assert_eq!(m.match_and_split(&m), None);

	}

	#[test]

	fn starts_with_works() {

		let full: MultiLocation =

			(Parent, Parachain(1000), AccountId32 { network: Any, id: [0; 32] }).into();

		let identity: MultiLocation = full.clone();

		let prefix: MultiLocation = (Parent, Parachain(1000)).into();

		let wrong_parachain: MultiLocation = (Parent, Parachain(1001)).into();

		let wrong_account: MultiLocation =

			(Parent, Parachain(1000), AccountId32 { network: Any, id: [1; 32] }).into();

		let no_parents: MultiLocation = (Parachain(1000)).into();

		let too_many_parents: MultiLocation = (Parent, Parent, Parachain(1000)).into();

		assert!(full.starts_with(&identity));

		assert!(full.starts_with(&prefix));

		assert!(!full.starts_with(&wrong_parachain));

		assert!(!full.starts_with(&wrong_account));

		assert!(!full.starts_with(&no_parents));

		assert!(!full.starts_with(&too_many_parents));

	}

	#[test]

	fn append_with_works() {

		let acc = AccountIndex64 { network: Any, index: 23 };

		let mut m = MultiLocation { parents: 1, interior: X1(Parachain(42)) };

		assert_eq!(m.append_with(X2(PalletInstance(3), acc.clone())), Ok(()));

		assert_eq!(

			m,

			MultiLocation {

				parents: 1,

				interior: X3(Parachain(42), PalletInstance(3), acc.clone())

			}

		);

		// cannot append to create overly long multilocation

		let acc = AccountIndex64 { network: Any, index: 23 };

		let m = MultiLocation {

			parents: 254,

			interior: X5(Parachain(42), OnlyChild, OnlyChild, OnlyChild, OnlyChild),

		};

		let suffix = X4(PalletInstance(3), acc.clone(), OnlyChild, OnlyChild);

		assert_eq!(m.clone().append_with(suffix.clone()), Err(suffix));

	}

	#[test]

	fn prepend_with_works() {

		let mut m = MultiLocation {

			parents: 1,

			interior: X2(Parachain(42), AccountIndex64 { network: Any, index: 23 }),

		};

		assert_eq!(m.prepend_with(MultiLocation { parents: 1, interior: X1(OnlyChild) }), Ok(()));

		assert_eq!(

			m,

			MultiLocation {

				parents: 1,

				interior: X2(Parachain(42), AccountIndex64 { network: Any, index: 23 })

			}

		);

		// cannot prepend to create overly long multilocation

		let mut m = MultiLocation { parents: 254, interior: X1(Parachain(42)) };

		let prefix = MultiLocation { parents: 2, interior: Here };

		assert_eq!(m.prepend_with(prefix.clone()), Err(prefix));

		let prefix = MultiLocation { parents: 1, interior: Here };

		assert_eq!(m.prepend_with(prefix), Ok(()));

		assert_eq!(m, MultiLocation { parents: 255, interior: X1(Parachain(42)) });

	}

	#[test]

	fn double_ended_ref_iteration_works() {

		let m = X3(Parachain(1000), Parachain(3), PalletInstance(5));

		let mut iter = m.iter();

		let first = iter.next().unwrap();

		assert_eq!(first, &Parachain(1000));

		let third = iter.next_back().unwrap();

		assert_eq!(third, &PalletInstance(5));

		let second = iter.next_back().unwrap();

		assert_eq!(iter.next(), None);

		assert_eq!(iter.next_back(), None);

		assert_eq!(second, &Parachain(3));

		let res = Here

			.pushed_with(first.clone())

			.unwrap()

			.pushed_with(second.clone())

			.unwrap()

			.pushed_with(third.clone())

			.unwrap();

		assert_eq!(m, res);

		// make sure there's no funny business with the 0 indexing

		let m = Here;

		let mut iter = m.iter();

		assert_eq!(iter.next(), None);

		assert_eq!(iter.next_back(), None);

	}

	#[test]

	fn conversion_from_other_types_works() {

		fn takes_multilocation<Arg: Into<MultiLocation>>(_arg: Arg) {}

		takes_multilocation(Parent);

		takes_multilocation(Here);

		takes_multilocation(X1(Parachain(42)));

		takes_multilocation((255, PalletInstance(8)));

		takes_multilocation((Ancestor(5), Parachain(1), PalletInstance(3)));

		takes_multilocation((Ancestor(2), Here));

		takes_multilocation(AncestorThen(

			3,

			X2(Parachain(43), AccountIndex64 { network: Any, index: 155 }),

		));

		takes_multilocation((Parent, AccountId32 { network: Any, id: [0; 32] }));

		takes_multilocation((Parent, Here));

		takes_multilocation(ParentThen(X1(Parachain(75))));

		takes_multilocation([Parachain(100), PalletInstance(3)]);

	}

}