lib.rs

						at_relay_block_number: 0,
						head_hash: head_data(3, 10).hash()
					},
					next_imported_hash_position: 1,
				})
			);

			assert_eq!(
				ImportedParaHeads::<TestRuntime>::get(
					ParaId(1),
					initial_best_head(1).best_head_hash.head_hash
				)
				.map(|h| h.into_inner()),
				Some(stored_head_data(1, 0))
			);
			assert_eq!(
				ImportedParaHeads::<TestRuntime>::get(
					ParaId(2),
					initial_best_head(2).best_head_hash.head_hash
				)
				.map(|h| h.into_inner()),
				None
			);
			assert_eq!(
				ImportedParaHeads::<TestRuntime>::get(ParaId(3), head_hash(3, 10))
					.map(|h| h.into_inner()),
				Some(stored_head_data(3, 10))
			);

			assert_eq!(
				System::<TestRuntime>::events(),
				vec![
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Parachains(Event::UpdatedParachainHead {
							parachain: ParaId(1),
							parachain_head_hash: initial_best_head(1).best_head_hash.head_hash,
						}),
						topics: vec![],
					},
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Parachains(Event::UpdatedParachainHead {
							parachain: ParaId(3),
							parachain_head_hash: head_data(3, 10).hash(),
						}),
						topics: vec![],
					}
				],
			);
		});
	}

	#[test]
	fn imports_parachain_heads_is_able_to_progress() {
		let (state_root_5, proof_5, parachains_5) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![(1, head_data(1, 5))]);
		let (state_root_10, proof_10, parachains_10) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![(1, head_data(1, 10))]);
		run_test(|| {
			// start with relay block #0 and import head#5 of parachain#1
			initialize(state_root_5);
			let result = import_parachain_1_head(0, state_root_5, parachains_5, proof_5);
			// first parachain head is imported for free
			assert_eq!(result.unwrap().pays_fee, Pays::No);
			assert_eq!(
				ParasInfo::<TestRuntime>::get(ParaId(1)),
				Some(ParaInfo {
					best_head_hash: BestParaHeadHash {
						at_relay_block_number: 0,
						head_hash: head_data(1, 5).hash()
					},
					next_imported_hash_position: 1,
				})
			);
			assert_eq!(
				ImportedParaHeads::<TestRuntime>::get(ParaId(1), head_data(1, 5).hash())
					.map(|h| h.into_inner()),
				Some(stored_head_data(1, 5))
			);
			assert_eq!(
				ImportedParaHeads::<TestRuntime>::get(ParaId(1), head_data(1, 10).hash())
					.map(|h| h.into_inner()),
				None
			);
			assert_eq!(
				System::<TestRuntime>::events(),
				vec![EventRecord {
					phase: Phase::Initialization,
					event: TestEvent::Parachains(Event::UpdatedParachainHead {
						parachain: ParaId(1),
						parachain_head_hash: head_data(1, 5).hash(),
					}),
					topics: vec![],
				}],
			);

			// import head#10 of parachain#1 at relay block #1
			let (relay_1_hash, justification) = proceed(1, state_root_10);
			let result = import_parachain_1_head(1, state_root_10, parachains_10, proof_10);
			// second parachain head is imported for fee
			assert_eq!(result.unwrap().pays_fee, Pays::Yes);
			assert_eq!(
				ParasInfo::<TestRuntime>::get(ParaId(1)),
				Some(ParaInfo {
					best_head_hash: BestParaHeadHash {
						at_relay_block_number: 1,
						head_hash: head_data(1, 10).hash()
					},
					next_imported_hash_position: 2,
				})
			);
			assert_eq!(
				ImportedParaHeads::<TestRuntime>::get(ParaId(1), head_data(1, 5).hash())
					.map(|h| h.into_inner()),
				Some(stored_head_data(1, 5))
			);
			assert_eq!(
				ImportedParaHeads::<TestRuntime>::get(ParaId(1), head_data(1, 10).hash())
					.map(|h| h.into_inner()),
				Some(stored_head_data(1, 10))
			);
			assert_eq!(
				System::<TestRuntime>::events(),
				vec![
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Parachains(Event::UpdatedParachainHead {
							parachain: ParaId(1),
							parachain_head_hash: head_data(1, 5).hash(),
						}),
						topics: vec![],
					},
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Grandpa1(
							pallet_bridge_grandpa::Event::UpdatedBestFinalizedHeader {
								number: 1,
								hash: relay_1_hash,
								grandpa_info: StoredHeaderGrandpaInfo {
									finality_proof: justification,
									new_verification_context: None,
								},
							}
						),
						topics: vec![],
					},
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Parachains(Event::UpdatedParachainHead {
							parachain: ParaId(1),
							parachain_head_hash: head_data(1, 10).hash(),
						}),
						topics: vec![],
					}
				],
			);
		});
	}

	#[test]
	fn ignores_untracked_parachain() {
		let (state_root, proof, parachains) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![
				(1, head_data(1, 5)),
				(UNTRACKED_PARACHAIN_ID, head_data(1, 5)),
				(2, head_data(1, 5)),
			]);
		run_test(|| {
			// start with relay block #0 and try to import head#5 of parachain#1 and untracked
			// parachain
			let expected_weight =
				WeightInfo::submit_parachain_heads_weight(DbWeight::get(), &proof, 3)
					.saturating_sub(WeightInfo::parachain_head_storage_write_weight(
						DbWeight::get(),
					));
			initialize(state_root);
			let result = Pallet::<TestRuntime>::submit_parachain_heads(
				RuntimeOrigin::signed(1),
				(0, test_relay_header(0, state_root).hash()),
				parachains,
				proof,
			);
			assert_ok!(result);
			assert_eq!(result.expect("checked above").actual_weight, Some(expected_weight));
			assert_eq!(
				ParasInfo::<TestRuntime>::get(ParaId(1)),
				Some(ParaInfo {
					best_head_hash: BestParaHeadHash {
						at_relay_block_number: 0,
						head_hash: head_data(1, 5).hash()
					},
					next_imported_hash_position: 1,
				})
			);
			assert_eq!(ParasInfo::<TestRuntime>::get(ParaId(UNTRACKED_PARACHAIN_ID)), None,);
			assert_eq!(
				ParasInfo::<TestRuntime>::get(ParaId(2)),
				Some(ParaInfo {
					best_head_hash: BestParaHeadHash {
						at_relay_block_number: 0,
						head_hash: head_data(1, 5).hash()
					},
					next_imported_hash_position: 1,
				})
			);
			assert_eq!(
				System::<TestRuntime>::events(),
				vec![
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Parachains(Event::UpdatedParachainHead {
							parachain: ParaId(1),
							parachain_head_hash: head_data(1, 5).hash(),
						}),
						topics: vec![],
					},
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Parachains(Event::UntrackedParachainRejected {
							parachain: ParaId(UNTRACKED_PARACHAIN_ID),
						}),
						topics: vec![],
					},
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Parachains(Event::UpdatedParachainHead {
							parachain: ParaId(2),
							parachain_head_hash: head_data(1, 5).hash(),
						}),
						topics: vec![],
					}
				],
			);
		});
	}

	#[test]
	fn does_nothing_when_already_imported_this_head_at_previous_relay_header() {
		let (state_root, proof, parachains) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![(1, head_data(1, 0))]);
		run_test(|| {
			// import head#0 of parachain#1 at relay block#0
			initialize(state_root);
			assert_ok!(import_parachain_1_head(0, state_root, parachains.clone(), proof.clone()));
			assert_eq!(ParasInfo::<TestRuntime>::get(ParaId(1)), Some(initial_best_head(1)));
			assert_eq!(
				System::<TestRuntime>::events(),
				vec![EventRecord {
					phase: Phase::Initialization,
					event: TestEvent::Parachains(Event::UpdatedParachainHead {
						parachain: ParaId(1),
						parachain_head_hash: initial_best_head(1).best_head_hash.head_hash,
					}),
					topics: vec![],
				}],
			);

			// try to import head#0 of parachain#1 at relay block#1
			// => call succeeds, but nothing is changed
			let (relay_1_hash, justification) = proceed(1, state_root);
			assert_ok!(import_parachain_1_head(1, state_root, parachains, proof));
			assert_eq!(ParasInfo::<TestRuntime>::get(ParaId(1)), Some(initial_best_head(1)));
			assert_eq!(
				System::<TestRuntime>::events(),
				vec![
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Parachains(Event::UpdatedParachainHead {
							parachain: ParaId(1),
							parachain_head_hash: initial_best_head(1).best_head_hash.head_hash,
						}),
						topics: vec![],
					},
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Grandpa1(
							pallet_bridge_grandpa::Event::UpdatedBestFinalizedHeader {
								number: 1,
								hash: relay_1_hash,
								grandpa_info: StoredHeaderGrandpaInfo {
									finality_proof: justification,
									new_verification_context: None,
								}
							}
						),
						topics: vec![],
					},
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Parachains(Event::RejectedObsoleteParachainHead {
							parachain: ParaId(1),
							parachain_head_hash: initial_best_head(1).best_head_hash.head_hash,
						}),
						topics: vec![],
					}
				],
			);
		});
	}

	#[test]
	fn does_nothing_when_already_imported_head_at_better_relay_header() {
		let (state_root_5, proof_5, parachains_5) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![(1, head_data(1, 5))]);
		let (state_root_10, proof_10, parachains_10) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![(1, head_data(1, 10))]);
		run_test(|| {
			// start with relay block #0
			initialize(state_root_5);

			// head#10 of parachain#1 at relay block#1
			let (relay_1_hash, justification) = proceed(1, state_root_10);
			assert_ok!(import_parachain_1_head(1, state_root_10, parachains_10, proof_10));
			assert_eq!(
				ParasInfo::<TestRuntime>::get(ParaId(1)),
				Some(ParaInfo {
					best_head_hash: BestParaHeadHash {
						at_relay_block_number: 1,
						head_hash: head_data(1, 10).hash()
					},
					next_imported_hash_position: 1,
				})
			);
			assert_eq!(
				System::<TestRuntime>::events(),
				vec![
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Grandpa1(
							pallet_bridge_grandpa::Event::UpdatedBestFinalizedHeader {
								number: 1,
								hash: relay_1_hash,
								grandpa_info: StoredHeaderGrandpaInfo {
									finality_proof: justification.clone(),
									new_verification_context: None,
								}
							}
						),
						topics: vec![],
					},
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Parachains(Event::UpdatedParachainHead {
							parachain: ParaId(1),
							parachain_head_hash: head_data(1, 10).hash(),
						}),
						topics: vec![],
					}
				],
			);

			// now try to import head#5 at relay block#0
			// => nothing is changed, because better head has already been imported
			assert_ok!(import_parachain_1_head(0, state_root_5, parachains_5, proof_5));
			assert_eq!(
				ParasInfo::<TestRuntime>::get(ParaId(1)),
				Some(ParaInfo {
					best_head_hash: BestParaHeadHash {
						at_relay_block_number: 1,
						head_hash: head_data(1, 10).hash()
					},
					next_imported_hash_position: 1,
				})
			);
			assert_eq!(
				System::<TestRuntime>::events(),
				vec![
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Grandpa1(
							pallet_bridge_grandpa::Event::UpdatedBestFinalizedHeader {
								number: 1,
								hash: relay_1_hash,
								grandpa_info: StoredHeaderGrandpaInfo {
									finality_proof: justification,
									new_verification_context: None,
								}
							}
						),
						topics: vec![],
					},
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Parachains(Event::UpdatedParachainHead {
							parachain: ParaId(1),
							parachain_head_hash: head_data(1, 10).hash(),
						}),
						topics: vec![],
					},
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Parachains(Event::RejectedObsoleteParachainHead {
							parachain: ParaId(1),
							parachain_head_hash: head_data(1, 5).hash(),
						}),
						topics: vec![],
					}
				],
			);
		});
	}

	#[test]
	fn does_nothing_when_parachain_head_is_too_large() {
		let (state_root, proof, parachains) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![
				(1, head_data(1, 5)),
				(4, big_head_data(1, 5)),
			]);
		run_test(|| {
			// start with relay block #0 and try to import head#5 of parachain#1 and big parachain
			initialize(state_root);
			let result = Pallet::<TestRuntime>::submit_parachain_heads(
				RuntimeOrigin::signed(1),
				(0, test_relay_header(0, state_root).hash()),
				parachains,
				proof,
			);
			assert_ok!(result);
			assert_eq!(
				ParasInfo::<TestRuntime>::get(ParaId(1)),
				Some(ParaInfo {
					best_head_hash: BestParaHeadHash {
						at_relay_block_number: 0,
						head_hash: head_data(1, 5).hash()
					},
					next_imported_hash_position: 1,
				})
			);
			assert_eq!(ParasInfo::<TestRuntime>::get(ParaId(4)), None);
			assert_eq!(
				System::<TestRuntime>::events(),
				vec![
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Parachains(Event::UpdatedParachainHead {
							parachain: ParaId(1),
							parachain_head_hash: head_data(1, 5).hash(),
						}),
						topics: vec![],
					},
					EventRecord {
						phase: Phase::Initialization,
						event: TestEvent::Parachains(Event::RejectedLargeParachainHead {
							parachain: ParaId(4),
							parachain_head_hash: big_head_data(1, 5).hash(),
							parachain_head_size: big_stored_head_data(1, 5).encoded_size() as u32,
						}),
						topics: vec![],
					},
				],
			);
		});
	}

	#[test]
	fn prunes_old_heads() {
		run_test(|| {
			let heads_to_keep = crate::mock::HeadsToKeep::get();

			// import exactly `HeadsToKeep` headers
			for i in 0..heads_to_keep {
				let (state_root, proof, parachains) = prepare_parachain_heads_proof::<
					RegularParachainHeader,
				>(vec![(1, head_data(1, i))]);
				if i == 0 {
					initialize(state_root);
				} else {
					proceed(i, state_root);
				}

				let expected_weight = weight_of_import_parachain_1_head(&proof, false);
				let result = import_parachain_1_head(i, state_root, parachains, proof);
				assert_ok!(result);
				assert_eq!(result.expect("checked above").actual_weight, Some(expected_weight));
			}

			// nothing is pruned yet
			for i in 0..heads_to_keep {
				assert!(ImportedParaHeads::<TestRuntime>::get(ParaId(1), head_data(1, i).hash())
					.is_some());
			}

			// import next relay chain header and next parachain head
			let (state_root, proof, parachains) = prepare_parachain_heads_proof::<
				RegularParachainHeader,
			>(vec![(1, head_data(1, heads_to_keep))]);
			proceed(heads_to_keep, state_root);
			let expected_weight = weight_of_import_parachain_1_head(&proof, true);
			let result = import_parachain_1_head(heads_to_keep, state_root, parachains, proof);
			assert_ok!(result);
			assert_eq!(result.expect("checked above").actual_weight, Some(expected_weight));

			// and the head#0 is pruned
			assert!(
				ImportedParaHeads::<TestRuntime>::get(ParaId(1), head_data(1, 0).hash()).is_none()
			);
			for i in 1..=heads_to_keep {
				assert!(ImportedParaHeads::<TestRuntime>::get(ParaId(1), head_data(1, i).hash())
					.is_some());
			}
		});
	}

	#[test]
	fn fails_on_unknown_relay_chain_block() {
		let (state_root, proof, parachains) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![(1, head_data(1, 5))]);
		run_test(|| {
			// start with relay block #0
			initialize(state_root);

			// try to import head#5 of parachain#1 at unknown relay chain block #1
			assert_noop!(
				import_parachain_1_head(1, state_root, parachains, proof),
				Error::<TestRuntime>::UnknownRelayChainBlock
			);
		});
	}

	#[test]
	fn fails_on_invalid_storage_proof() {
		let (_state_root, proof, parachains) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![(1, head_data(1, 5))]);
		run_test(|| {
			// start with relay block #0
			initialize(Default::default());

			// try to import head#5 of parachain#1 at relay chain block #0
			assert_noop!(
				import_parachain_1_head(0, Default::default(), parachains, proof),
				Error::<TestRuntime>::HeaderChainStorageProof(HeaderChainError::StorageProof(
					StorageProofError::StorageRootMismatch
				))
			);
		});
	}

	#[test]
	fn is_not_rewriting_existing_head_if_failed_to_read_updated_head() {
		let (state_root_5, proof_5, parachains_5) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![(1, head_data(1, 5))]);
		let (state_root_10_at_20, proof_10_at_20, parachains_10_at_20) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![(2, head_data(2, 10))]);
		let (state_root_10_at_30, proof_10_at_30, parachains_10_at_30) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![(1, head_data(1, 10))]);
		run_test(|| {
			// we've already imported head#5 of parachain#1 at relay block#10
			initialize(state_root_5);
			import_parachain_1_head(0, state_root_5, parachains_5, proof_5).expect("ok");
			assert_eq!(
				Pallet::<TestRuntime>::best_parachain_head(ParaId(1)),
				Some(stored_head_data(1, 5))
			);

			// then if someone is pretending to provide updated head#10 of parachain#1 at relay
			// block#20, but fails to do that
			//
			// => we'll leave previous value
			proceed(20, state_root_10_at_20);
			assert_ok!(Pallet::<TestRuntime>::submit_parachain_heads(
				RuntimeOrigin::signed(1),
				(20, test_relay_header(20, state_root_10_at_20).hash()),
				parachains_10_at_20,
				proof_10_at_20,
			),);
			assert_eq!(
				Pallet::<TestRuntime>::best_parachain_head(ParaId(1)),
				Some(stored_head_data(1, 5))
			);

			// then if someone is pretending to provide updated head#10 of parachain#1 at relay
			// block#30, and actually provides it
			//
			// => we'll update value
			proceed(30, state_root_10_at_30);
			assert_ok!(Pallet::<TestRuntime>::submit_parachain_heads(
				RuntimeOrigin::signed(1),
				(30, test_relay_header(30, state_root_10_at_30).hash()),
				parachains_10_at_30,
				proof_10_at_30,
			),);
			assert_eq!(
				Pallet::<TestRuntime>::best_parachain_head(ParaId(1)),
				Some(stored_head_data(1, 10))
			);
		});
	}

	#[test]
	fn storage_keys_computed_properly() {
		assert_eq!(
			ParasInfo::<TestRuntime>::storage_map_final_key(ParaId(42)).to_vec(),
			ParasInfoKeyProvider::final_key("Parachains", &ParaId(42)).0
		);

		assert_eq!(
			ImportedParaHeads::<TestRuntime>::storage_double_map_final_key(
				ParaId(42),
				ParaHash::from([21u8; 32])
			)
			.to_vec(),
			ImportedParaHeadsKeyProvider::final_key(
				"Parachains",
				&ParaId(42),
				&ParaHash::from([21u8; 32])
			)
			.0,
		);
	}

	#[test]
	fn ignores_parachain_head_if_it_is_missing_from_storage_proof() {
		let (state_root, proof, _) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![]);
		let parachains = vec![(ParaId(2), Default::default())];
		run_test(|| {
			initialize(state_root);
			assert_ok!(Pallet::<TestRuntime>::submit_parachain_heads(
				RuntimeOrigin::signed(1),
				(0, test_relay_header(0, state_root).hash()),
				parachains,
				proof,
			));
			assert_eq!(
				System::<TestRuntime>::events(),
				vec![EventRecord {
					phase: Phase::Initialization,
					event: TestEvent::Parachains(Event::MissingParachainHead {
						parachain: ParaId(2),
					}),
					topics: vec![],
				}],
			);
		});
	}

	#[test]
	fn ignores_parachain_head_if_parachain_head_hash_is_wrong() {
		let (state_root, proof, _) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![(1, head_data(1, 0))]);
		let parachains = vec![(ParaId(1), head_data(1, 10).hash())];
		run_test(|| {
			initialize(state_root);
			assert_ok!(Pallet::<TestRuntime>::submit_parachain_heads(
				RuntimeOrigin::signed(1),
				(0, test_relay_header(0, state_root).hash()),
				parachains,
				proof,
			));
			assert_eq!(
				System::<TestRuntime>::events(),
				vec![EventRecord {
					phase: Phase::Initialization,
					event: TestEvent::Parachains(Event::IncorrectParachainHeadHash {
						parachain: ParaId(1),
						parachain_head_hash: head_data(1, 10).hash(),
						actual_parachain_head_hash: head_data(1, 0).hash(),
					}),
					topics: vec![],
				}],
			);
		});
	}

	#[test]
	fn test_bridge_parachain_call_is_correctly_defined() {
		let (state_root, proof, _) =
			prepare_parachain_heads_proof::<RegularParachainHeader>(vec![(1, head_data(1, 0))]);
		let parachains = vec![(ParaId(2), Default::default())];
		let relay_header_id = (0, test_relay_header(0, state_root).hash());

		let direct_submit_parachain_heads_call = Call::<TestRuntime>::submit_parachain_heads {
			at_relay_block: relay_header_id,
			parachains: parachains.clone(),
			parachain_heads_proof: proof.clone(),
		};
		let indirect_submit_parachain_heads_call = BridgeParachainCall::submit_parachain_heads {
			at_relay_block: relay_header_id,
			parachains,
			parachain_heads_proof: proof,
		};
		assert_eq!(
			direct_submit_parachain_heads_call.encode(),
			indirect_submit_parachain_heads_call.encode()
		);
	}

	generate_owned_bridge_module_tests!(BasicOperatingMode::Normal, BasicOperatingMode::Halted);

	#[test]
	fn maybe_max_parachains_returns_correct_value() {
		assert_eq!(MaybeMaxParachains::<TestRuntime, ()>::get(), Some(mock::TOTAL_PARACHAINS));
	}

	#[test]
	fn maybe_max_total_parachain_hashes_returns_correct_value() {
		assert_eq!(
			MaybeMaxTotalParachainHashes::<TestRuntime, ()>::get(),
			Some(mock::TOTAL_PARACHAINS * mock::HeadsToKeep::get()),
		);
	}

	#[test]
	fn submit_finality_proof_requires_signed_origin() {
		run_test(|| {
			let (state_root, proof, parachains) =
				prepare_parachain_heads_proof::<RegularParachainHeader>(vec![(1, head_data(1, 0))]);

			initialize(state_root);

			// `submit_parachain_heads()` should fail when the pallet is halted.
			assert_noop!(
				Pallet::<TestRuntime>::submit_parachain_heads(
					RuntimeOrigin::root(),
					(0, test_relay_header(0, state_root).hash()),
					parachains,
					proof,
				),
				DispatchError::BadOrigin
			);
		})
	}

	#[test]
	fn may_be_free_for_submitting_filtered_heads() {
		run_test(|| {
			let (state_root, proof, parachains) =
				prepare_parachain_heads_proof::<RegularParachainHeader>(vec![(2, head_data(2, 5))]);
			// start with relay block #0 and import head#5 of parachain#2
			initialize(state_root);
			// first submission is free
			let result = Pallet::<TestRuntime>::submit_parachain_heads(
				RuntimeOrigin::signed(1),
				(0, test_relay_header(0, state_root).hash()),
				parachains.clone(),
				proof.clone(),
			);
			assert_eq!(result.unwrap().pays_fee, Pays::No);
			// next submission is NOT free, because we haven't updated anything
			let result = Pallet::<TestRuntime>::submit_parachain_heads(
				RuntimeOrigin::signed(1),
				(0, test_relay_header(0, state_root).hash()),
				parachains,
				proof,
			);
			assert_eq!(result.unwrap().pays_fee, Pays::Yes);
		})
	}

	#[test]
	fn may_be_free_for_submitting_first_heads() {
		fn run_sub_test(pre: impl FnOnce(), heads: Vec<(u32, ParaHead)>) -> Pays {
			run_test(|| {
				let (state_root, proof, parachains) =
					prepare_parachain_heads_proof::<RegularParachainHeader>(heads);
				let relay_header_hash = initialize(state_root);
				pre();
				let result = Pallet::<TestRuntime>::submit_parachain_heads(
					RuntimeOrigin::signed(1),
					(0, relay_header_hash),
					parachains,
					proof,
				);
				result.unwrap().pays_fee
			})
		}

		// if we submit 2 heads and both are first => Pays::No
		assert_eq!(run_sub_test(|| (), vec![(1, head_data(1, 5)), (2, head_data(2, 5))]), Pays::No);
		// if we submit 2 heads and one is not first => Pays::Yes
		assert_eq!(
			run_sub_test(
				|| {
					ParasInfo::<TestRuntime, ()>::insert(
						ParaId(1),
						ParaInfo {
							best_head_hash: BestParaHeadHash {
								at_relay_block_number: 1,
								head_hash: Default::default(),
							},
							next_imported_hash_position: 1,
						},
					);
				},
				vec![(1, head_data(1, 5)), (2, head_data(2, 5))]
			),
			Pays::Yes
		);
		// if we submit 2 heads and both are not first => Pays::Yes
		assert_eq!(
			run_sub_test(
				|| {
					ParasInfo::<TestRuntime, ()>::insert(
						ParaId(1),
						ParaInfo {
							best_head_hash: BestParaHeadHash {
								at_relay_block_number: 1,
								head_hash: Default::default(),
							},
							next_imported_hash_position: 1,
						},
					);
					ParasInfo::<TestRuntime, ()>::insert(
						ParaId(2),
						ParaInfo {
							best_head_hash: BestParaHeadHash {
								at_relay_block_number: 2,
								head_hash: Default::default(),
							},
							next_imported_hash_position: 1,
						},
					);
				},
				vec![(1, head_data(1, 5)), (2, head_data(2, 5))]
			),
			Pays::Yes
		);
	}
}