Optimize multilocation reanchoring logic in XCM

[tonyalaribe]

This PR improves the algorithm for reanchor - see https://github.com/paritytech/polkadot-sdk/issues/897 for more details.

Approach:

• We first normalize/prepend target and id with the ancestor
• We then remove any prefix nodes with both target and id share in common
• Then we convert all of target to parents, and add that to the parents of id. This gives us the path to go from target to id, without any superflous nodes, or the need for post simplification.

Question: The simplify() method which was used previously is public. Does it make sense to leave it or should it be removed if it's not used anywhere else in the polkadot codebase (except tests)? This also applies with the inverted() method on Multilocation

[muharem]

@tonyalaribe I see two not covered edge cases, here the failing tests https://github.com/paritytech/polkadot/pull/6307

[tonyalaribe]

bot rebase

[paritytech-processbot[bot]]

Rebased

[tonyalaribe]

bot merge

[paritytech-processbot[bot]]

Waiting for commit status.

[tonyalaribe]

bot rebase

[paritytech-processbot[bot]]

Rebased

[paritytech-processbot[bot]]

Merge cancelled due to error. Error: Head SHA changed from 59b949d642e1d117b4e2bd43d2a412092b7932f0 to 36db35e4efb66dbc2752b4f046baa4c9193e27ff

[tonyalaribe]

bot rebase

[paritytech-processbot[bot]]

Rebased

[tonyalaribe]

bot rebase

[paritytech-processbot[bot]]

Rebased

[tonyalaribe]

bot rebase

[paritytech-processbot[bot]]

Rebased

[dzmitry-lahoda]

I took tests from location_conversion.rs and ported to multilocation.rs on master of polkadot

	fn account20() -> Junction {
		AccountKey20 { network: Any, key: Default::default() }
	}

	fn account32() -> Junction {
		AccountId32 { network: Any, id: Default::default() }
	}

	#[test]
	fn inverter_works_in_tree() {
		let ancestry: MultiLocation = X3(Parachain(1), account20(), account20()).into();
		let target = MultiLocation::new(3, X2(Parachain(2), account32()));
		let inverted = ancestry.inverted(&target).unwrap();
		let expected = MultiLocation::new(2, X3(Parachain(1), account20(), account20()));
		assert_eq!(inverted, expected);
	}

	#[test]
	fn inverter_uses_ancestry_as_inverted_location() {
		let ancestry: MultiLocation = X2(account20(), account20()).into();
		let target = MultiLocation::grandparent();
		let inverted = ancestry.inverted(&target).unwrap();
		let expected = X2(account20(), account20()).into();
		assert_eq!(inverted, expected);
	}

	#[test]
	fn inverter_uses_only_child_on_missing_ancestry() {
		let ancestry: MultiLocation = X1(PalletInstance(5)).into();
		let target = MultiLocation::grandparent();
		let inverted = ancestry.inverted(&target).unwrap();
		let expected = X2(PalletInstance(5), OnlyChild).into();
		assert_eq!(inverted, expected);
	}

	#[test]
	fn inverter_errors_when_location_is_too_large() {
		let ancestry: MultiLocation = Here.into();
		let target = MultiLocation { parents: 99, interior: X1(Parachain(88)) };
		let inverted = ancestry.inverted(&target);
		assert_eq!(inverted, Err(()));
	}

Only one test is failing:

---- v1::multilocation::tests::inverter_uses_only_child_on_missing_ancestry stdout ----
thread 'v1::multilocation::tests::inverter_uses_only_child_on_missing_ancestry' panicked at 'assertion failed: `(left == right)`
  left: `MultiLocation { parents: 0, interior: X2(OnlyChild, PalletInstance(5)) }`,
 right: `MultiLocation { parents: 0, interior: X2(PalletInstance(5), OnlyChild) }`', xcm/src/v1/multilocation.rs:913:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

May be useful to ensure that no regression happened.