This PR adds implementation of `Ord, Eq, PartialOrd, PartialEq` traits
for [`HashAndNumber`
](https://github.com/paritytech/polkadot-sdk/blob/6e645915

/substrate/primitives/blockchain/src/header_metadata.rs#L149-L154)
struct.

---------

Co-authored-by: cmd[bot] <41898282+github-actions[bot]@users.noreply.github.com>

Previously, block gaps could only be created by warp sync, but block
gaps will also be generated by fast sync once #5406 is fixed. This PR is
part 1 of the detailed implementation plan in
https://github.com/paritytech/polkadot-sdk/issues/5406#issuecomment-2325064863:
refactor `BlockGap`.

This refactor converts the existing `(NumberFor<Block>,
NumberFor<Block>)` into a dedicated `BlockGap<NumberFor<Block>>` struct.
This change is purely structural and does not alter existing logic, but
lays the groundwork for the follow-up PR.

The compatibility concern caused by the new structure is addressed in
the second commit.

cc @dmitry-markin



---------

Co-authored-by: Bastian Köcher <git@kchr.de>

This PR effectively skips over cases where the blockchain reports the
genesis block as leaf.

The issue manifests as the blockchain getting stuck and not importing
blocks after a while.
Although the root-cause of why the blockchain reports the genesis as
leaf is not scoped, this hot-fix is unblocking the new release.

While at it, added some extra debug logs to identify issues more easily
in the future.

### Issue

```
2024-07-22 10:06:08.708 DEBUG tokio-runtime-worker db::blockchain: Checking for displaced leaves after finalization. leaves=[0xd62aea69664b74c55b7e79ab5855b117d213156a5e9ab05ad0737772aaf42c14, 0xb0a8d493285c2df73290dfb7e61f870f17b41801197a149ca93654499ea3dafe] finalized_block_hash=0x8f8e…7f34 finalized_block_number=24148459
2024-07-22 10:06:08.708 DEBUG tokio-runtime-worker db::blockchain: Handle displaced leaf 0xd62aea69664b74c55b7e79ab5855b117d213156a5e9ab05ad0737772aaf42c14 (elapsed 25.74µs) leaf_number=24148577
2024-07-22 10:06:08.709 DEBUG tokio-runtime-worker db::blockchain: Leaf points to the finalized header 0xd62aea69664b74c55b7e79ab5855b117d213156a5e9ab05ad0737772aaf42c14, skipping for now (elapsed 70.72µs)


// This is Kusama genesis
2024-07-22 10:06:08.709 DEBUG tokio-runtime-worker db::blockchain: Handle displaced leaf 0xb0a8d493285c2df73290dfb7e61f870f17b41801197a149ca93654499ea3dafe (elapsed 127.271µs) leaf_number=0
2024-07-22 10:06:08.709 DEBUG tokio-runtime-worker db::blockchain: Skip more blocks until we get all blocks on finalized chain until the height of the parent block current_hash=0xb0a8d493285c2df73290dfb7e61f870f17b41801197a149ca93654499ea3dafe current_num=0 finalized_num=24148458
```

### Before

```
2024-07-20 00:45:00.234  INFO tokio-runtime-worker substrate: ️  Preparing  0.0 bps, target=#24116589 (50 peers), best: #24116498 (0xb846…8720), finalized #24116493 (0x50b6…2445),  2.3MiB/s  2.6kiB/s    
   
...

2024-07-20 14:05:18.572  INFO tokio-runtime-worker substrate: ️  Syncing  0.0 bps, target=#24124495 (51 peers), best: #24119976 (0x6970…aeb3), finalized #24119808 (0xd900…abe4),  2.2MiB/s  3.1kiB/s    
2024-07-20 14:05:23.573  INFO tokio-runtime-worker substrate: ️  Syncing  0.0 bps, target=#24124495 (51 peers), best: #24119976 (0x6970…aeb3), finalized #24119808 (0xd900…abe4),  2.2MiB/s  5.8kiB/s    
```

### After

```
2024-07-22 10:41:10.897 DEBUG tokio-runtime-worker db::blockchain: Handle displaced leaf 0x4e8cf3ff18e7d13ff7fec28f9fc8ce6eff5492ed8dc046e961b76dec5c0cfddf (elapsed 39.26µs) leaf_number=24150969
2024-07-22 10:41:10.897 DEBUG tokio-runtime-worker db::blockchain: Leaf points to the finalized header 0x4e8cf3ff18e7d13ff7fec28f9fc8ce6eff5492ed8dc046e961b76dec5c0cfddf, skipping for now (elapsed 49.69µs)
2024-07-22 10:41:10.897 DEBUG tokio-runtime-worker db::blockchain: Skip genesis block 0xb0a8d493285c2df73290dfb7e61f870f17b41801197a149ca93654499ea3dafe reporterd as leaf (elapsed 54.57µs)
2024-07-22 10:41:10.897 DEBUG tokio-runtime-worker db::blockchain: Finished with result DisplacedLeavesAfterFinalization { displaced_leaves: [], displaced_blocks: [] } (elapsed 58.78µs) finalized_block_hash=0x02b3…5338 finalized_block_number=24150967
2024-07-22 10:41:12.357  INFO tokio-runtime-worker substrate:  Imported #24150970 (0x4e8c…fddf → 0x3637…56bb)
2024-07-22 10:41:12.862  INFO tokio-runtime-worker substrate:  Idle (50 peers), best: #24150970 (0x3637…56bb), finalized #24150967 (0x02b3…5338),  2.0MiB/s  804.7kiB/s
2024-07-22 10:41:14.772 DEBUG tokio-runtime-worker db::blockchain: Checking for displaced leaves after finalization. leaves=[0x363763b16c23fc20a84f38f67014fa7ae6ba9c708fc074890016699e5ca756bb, 0xb0a8d493285c2df73290dfb7e61f870f17b41801197a149ca93654499ea3dafe] finalized_block_hash=0xa1534a105b90e7036a18ac1c646cd2bd6c41c66cc055817f4f51209ab9070e5c finalized_block_number=24150968
2024-07-22 10:41:14.772 DEBUG tokio-runtime-worker db::blockchain: Handle displaced leaf 0x363763b16c23fc20a84f38f67014fa7ae6ba9c708fc074890016699e5ca756bb (elapsed 62.48µs) leaf_number=24150970
2024-07-22 10:41:14.772 DEBUG tokio-runtime-worker db::blockchain: Leaf points to the finalized header 0x363763b16c23fc20a84f38f67014fa7ae6ba9c708fc074890016699e5ca756bb, skipping for now (elapsed 71.76µs)
2024-07-22 10:41:14.772 DEBUG tokio-runtime-worker db::blockchain: Skip genesis block 0xb0a8d493285c2df73290dfb7e61f870f17b41801197a149ca93654499ea3dafe reporterd as leaf (elapsed 75.96µs)
2024-07-22 10:41:14.772 DEBUG tokio-runtime-worker db::blockchain: Finished with result DisplacedLeavesAfterFinalization { displaced_leaves: [], displaced_blocks: [] } (elapsed 80.27µs) finalized_block_hash=0xa153…0e5c finalized_block_number=24150968
2024-07-22 10:41:14.795 DEBUG tokio-runtime-worker db::blockchain: Checking for displaced leaves after finalization. leaves=[0x363763b16c23fc20a84f38f67014fa7ae6ba9c708fc074890016699e5ca756bb, 0xb0a8d493285c2df73290dfb7e61f870f17b41801197a149ca93654499ea3dafe] finalized_block_hash=0xa1534a105b90e7036a18ac1c646cd2bd6c41c66cc055817f4f51209ab9070e5c finalized_block_number=24150968
2024-07-22 10:41:14.795 DEBUG tokio-runtime-worker db::blockchain: Handle displaced leaf 0x363763b16c23fc20a84f38f67014fa7ae6ba9c708fc074890016699e5ca756bb (elapsed 39.67µs) leaf_number=24150970
2024-07-22 10:41:14.795 DEBUG tokio-runtime-worker db::blockchain: Leaf points to the finalized header 0x363763b16c23fc20a84f38f67014fa7ae6ba9c708fc074890016699e5ca756bb, skipping for now (elapsed 50.3µs)
2024-07-22 10:41:14.795 DEBUG tokio-runtime-worker db::blockchain: Skip genesis block 0xb0a8d493285c2df73290dfb7e61f870f17b41801197a149ca93654499ea3dafe reporterd as leaf (elapsed 54.52µs)
2024-07-22 10:41:14.795 DEBUG tokio-runtime-worker db::blockchain: Finished with result DisplacedLeavesAfterFinalization { displaced_leaves: [], displaced_blocks: [] } (elapsed 58.66µs) finalized_block_hash=0xa153…0e5c finalized_block_number=24150968
2024-07-22 10:41:17.863  INFO tokio-runtime-worker substrate:  Idle (50 peers), best: #24150970 (0x3637…56bb), finalized #24150968 (0xa153…0e5c),  1.2MiB/s  815.0kiB/s
2024-07-22 10:41:18.399  INFO tokio-runtime-worker substrate: 

 Imported #24150971 (0x3637…56bb → 0x4ee3…5f7c)
```

Closes: https://github.com/paritytech/polkadot-sdk/issues/5088

---------

Signed-off-by: Alexandru Vasile <alexandru.vasile@parity.io>
Co-authored-by: Bastian Köcher <git@kchr.de>

Due to `LruMap` usage it is not actually possible to leverage read
feature of `RwLock`, hence change to `Mutex` that is faster

After the merge of #4922 we saw failing zombienet tests with the
following error:
```
2024-07-09 10:30:09 Error applying finality to block (0xb9e1d3d9cb2047fe61667e28a0963e0634a7b29781895bc9ca40c898027b4c09, 56685): UnknownBlock: Header was not found in the database: 0x0000000000000000000000000000000000000000000000000000000000000000    
2024-07-09 10:30:09 GRANDPA voter error: could not complete a round on disk: UnknownBlock: Header was not found in the database: 0x0000000000000000000000000000000000000000000000000000000000000000    
```

[Example](https://gitlab.parity.io/parity/mirrors/polkadot-sdk/-/jobs/6662262)

The crashing situation is warp-sync related. After warp syncing, it can
happen that there are gaps in block ancestry where we don't have the
header. At the same time, the genesis hash is in the set of leaves. In
`displaced_leaves_after_finalizing` we then iterate from the finalized
block backwards until we hit an unknown block, crashing the node.

This PR makes the detection of displaced branches resilient against
unknown block in the finalized block chain.

cc @nazar-pc (github won't let me request a review from you)

---------

Co-authored-by: Bastian Köcher <git@kchr.de>
Co-authored-by: command-bot <>

This PR largely fixes
https://github.com/paritytech/polkadot-sdk/issues/4903 by addressing it
from a few different directions.

The high-level observation is that complexity of finalization was
unfortunately roughly `O(n^3)`. Not only
`displaced_leaves_after_finalizing` was extremely inefficient on its
own, especially when large ranges of blocks were involved, it was called
once upfront and then on every single block that was finalized over and
over again.

The first commit refactores code adjacent to
`displaced_leaves_after_finalizing` to optimize memory allocations. For
example things like `BTreeMap<_, Vec<_>>` were very bad in terms of
number of allocations and after analyzing code paths was completely
unnecessary and replaced with `Vec<(_, _)>`. In other places allocations
of known size were not done upfront and some APIs required unnecessary
cloning of vectors.

I checked invariants and didn't find anything that was violated after
refactoring.

Second commit completely replaces `displaced_leaves_after_finalizing`
implementation with a much more efficient one. In my case with ~82k
blocks and ~13k leaves it takes ~5.4s to finish
`client.apply_finality()` now.

The idea is to avoid querying the same blocks over and over again as
well as introducing temporary local cache for blocks related to leaves
above block that is being finalized as well as local cache of the
finalized branch of the chain. I left some comments in the code and
wrote tests that I belive should check all code invariants for
correctness. `lowest_common_ancestor_multiblock` was removed as
unnecessary and not great in terms of performance API, domain-specific
code should be written instead like done in
`displaced_leaves_after_finalizing`.

After these changes I noticed finalization is still horribly slow,
turned out that even though `displaced_leaves_after_finalizing` was way
faster that before (probably order of magnitude), it was called for
every single of those 82k blocks 



The quick hack I came up with in the third commit to handle this edge
case was to not call it when finalizing multiple blocks at once until
the very last moment. It works and allows to finish the whole
finalization in just 14 seconds (5.4+5.4 of which are two calls to
`displaced_leaves_after_finalizing`). I'm really not happy with the fact
that `displaced_leaves_after_finalizing` is called twice, but much
heavier refactoring would be necessary to get rid of second call.

---

Next steps:
* assuming the changes are acceptable I'll write prdoc
* https://github.com/paritytech/polkadot-sdk/pull/4920 or something
similar in spirit should be implemented to unleash efficient parallelsm
with rayon in `displaced_leaves_after_finalizing`, which will allow to
further (and significant!) scale its performance rather that being
CPU-bound on a single core, also reading database sequentially should
ideally be avoided
* someone should look into removal of the second
`displaced_leaves_after_finalizing` call
* further cleanups are possible if `undo_finalization` can be removed

---

Polkadot Address: 1vSxzbyz2cJREAuVWjhXUT1ds8vBzoxn2w4asNpusQKwjJd

---------

Co-authored-by: Sebastian Kunert <skunert49@gmail.com>

## Issue

Currently, syncing parachains from scratch can lead to a very long
finalization time once they reach the tip of the chain. The problem is
that we try to finalize everything from 0 to the tip, which can be
thousands or even millions of blocks.

We finalize sequentially and try to compute displaced branches during
finalization. So for every block on the way, we compute an expensive
tree route.

## Proposed Improvements

In this PR, I propose improvements that solve this situation:

- **Skip tree route calculation if `leaves().len() == 1`:** This should
be enough for 90% of cases where there is only one leaf after sync.
- **Optimize finalization for long distances:** It can happen that the
parachain has imported some leaf and then receives a relay chain
notification with the finalized block. In that case, the previous
optimization will not trigger. A second mechanism should ensure that we
do not need to compute the full tree route. If the finalization distance
is long, we check the lowest common ancestor of all the leaves. If it is
above the to-be-finalized block, we know that there are no displaced
leaves. This is fast because forks are short and close to the tip, so we
can leverage the header cache.

## Alternative Approach

- The problem was introduced in #3962. Reverting that PR is another
possible strategy.
- We could store for every fork where it begins, however sounds a bit
more involved to me.


fixes #4614

- unit tests for pov-recovery
- elastic scaling support (recovering multiple candidates in a single
relay chain block)
- also some small cleanups
- also switches to candidates_pending_availability in
`handle_empty_block_announce_data`

Fixes https://github.com/paritytech/polkadot-sdk/issues/3577

After https://github.com/paritytech/polkadot-sdk/pull/4097 is merged, we
should also add a zombienet test, similar to the existing
`0002-pov_recovery.toml` but which has a single collator using elastic
scaling on multiple cores.

This PR changes the fork calculation and pruning algorithm to enable
future block header pruning. It's required because the previous
algorithm relied on the block header persistence. It follows the
[related
discussion](https://github.com/paritytech/polkadot-sdk/issues/1570)

The previous code contained this comment describing the situation:
```
	/// Note a block height finalized, displacing all leaves with number less than the finalized
	/// block's.
	///
	/// Although it would be more technically correct to also prune out leaves at the
	/// same number as the finalized block, but with different hashes, the current behavior
	/// is simpler and our assumptions about how finalization works means that those leaves
	/// will be pruned soon afterwards anyway.
	pub fn finalize_height(&mut self, number: N) -> FinalizationOutcome<H, N> {
```

The previous algorithm relied on the existing block headers to prune
forks later and to enable block header pruning we need to clear ...

**Update:** Pushed additional changes based on the review comments.

**This pull request fixes various spelling mistakes in this
repository.**

Most of the changes are contained in the first **3** commits:

- `Fix spelling mistakes in comments and docs`

- `Fix spelling mistakes in test names`

- `Fix spelling mistakes in error messages, panic messages, logs and
tracing`

Other source code spelling mistakes are separated into individual
commits for easier reviewing:

- `Fix the spelling of 'authority'`

- `Fix the spelling of 'REASONABLE_HEADERS_IN_JUSTIFICATION_ANCESTRY'`

- `Fix the spelling of 'prev_enqueud_messages'`

- `Fix the spelling of 'endpoint'`

- `Fix the spelling of 'children'`

- `Fix the spelling of 'PenpalSiblingSovereignAccount'`

- `Fix the spelling of 'PenpalSudoAccount'`

- `Fix the spelling of 'insufficient'`

- `Fix the spelling of 'PalletXcmExtrinsicsBenchmark'`

- `Fix the spelling of 'subtracted'`

- `Fix the spelling of '...

* Added ECIES encryption

* tweaks

* fmt

* Make clippy happy

* Use local keystore

* qed

* WIP Statement store

* Sync with networking changes in master

* WIP statement pallet

* Statement validation

* pallet tests

* Validation queue

* Store maintenance

* Basic statement refactoring + tests + docs

* Store metrics

* Store tests

* Store maintenance test

* cargo fmt

* Build fix

* OCW Api

* Offchain worker

* Enable host functions

* fmt

* Minor tweaks

* Fixed a warning

* Removed tracing

* Manual expiration

* Reworked constraint management

* Updated pallet constraint calculation

* Added small test

* Added remove function to the APIs

* Copy-paste spec into readme

* Comments

* Made the store optional

* Removed network protocol controller

* fmt

* Clippy fixes

* fmt

* fmt

* More clippy fixes

* More clippy fixes

* More clippy fixes

* Update client/statement-store/README.md

Co-authored-by: cheme <emericchevalier.pro@gmail.com>

* Apply suggestions from code review

Co-authored-by: Bastian Köcher <git@kchr.de>

* Removed sstore from node-template

* Sort out data path

* Added offline check

* Removed dispatch_statement

* Renamed into_generic

* Fixed commit placement

* Use HashSet for tracking peers/statements

* fmt

* Use ExtendedHostFunctions

* Fixed benches

* Tweaks

* Apply suggestions from code review

Co-authored-by: cheme <emericchevalier.pro@gmail.com>

* Fixed priority mixup

* Rename

* newtypes for priorities

* Added MAX_TOPICS

* Fixed key filtering logic

* Remove empty entrie

* Removed prefix from signing

* More documentation

* fmt

* Moved store setup from sc-service to node

* Handle maintenance task in sc-statement-store

* Use statement iterator

* Renamed runtime API mod

* fmt

* Remove dump_encoded

* fmt

* Apply suggestions from code review

Co-authored-by: Bastian Köcher <git@kchr.de>

* Apply suggestions from code review

Co-authored-by: Bastian Köcher <git@kchr.de>

* Fixed build after applying review suggestions

* License exceptions

* fmt

* Store options

* Moved pallet consts to config trait

* Removed global priority

* Validate fields when decoding

* Limit validation channel size

* Made a comment into module doc

* Removed submit_encoded

---------

Co-authored-by: cheme <emericchevalier.pro@gmail.com>
Co-authored-by: Bastian Köcher <git@kchr.de>

* consensus: remove caching functionality from block import pipeline

* client: update docs on Verifier::verify

* node: fix block production benchmark

* Change copyright year to 2023 from 2022

* Fix incorrect update of copyright year

* Remove years from copy right header

* Fix remaining files

* Fix typo in a header and remove update-copyright.sh

* Finalization target should be chosed as some ancestor of SelectChain::best_chain

* More test assertions

* Improve docs

* Removed stale docs

* Rename 'target' to 'base' in lookup method

* Fix typo

* Apply suggestions from code review

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

* Rename 'target_hash' to 'base_hash' in 'SelectChain::finality_target()'

* Apply suggestions from code review

Co-authored-by: Anton <anton.kalyaev@gmail.com>

* Docs improvement

* Doc fix

* Apply suggestions from code review

Co-authored-by: Bastian Köcher <git@kchr.de>

* Apply more code suggestions

---------

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>
Co-authored-by: Anton <anton.kalyaev@gmail.com>
Co-authored-by: Bastian Köcher <git@kchr.de>

* Expose `UnknownBlock` error via `ApiError`

In [certain cases](https://github.com/paritytech/polkadot/issues/5885) a
runtime api is called for an unknown block. For example a block which is
already pruned or on an abandon fork.

In such cases the correct error is returned but it is wrapped in
`ApiError::Application` and the only way to figure out what is the
problem is to inspect the actual message in the error. In polkadot for
example this usually happens when the runtime api version is being
queried. It's beneficial to be able to clearly separate such errors so i
that when they occur the client side can handle them more gracefully.
E.g. log less stressful error message than `State already discarded for
BlockId` or cancel any pending work related on this block.

* Update primitives/api/src/lib.rs

Co-authored-by: Bastian Köcher <git@kchr.de>

Co-authored-by: Bastian Köcher <git@kchr.de>

It changes the arguments of `HeaderBackend::status` method from: `BlockId<Block>` to: `Block::Hash`

This PR is part of BlockId::Number refactoring analysis (paritytech/substrate#11292)

Co-authored-by: parity-processbot <>

* BlockId removal: refactor: HeaderBackend::header

It changes the arguments of:
- `HeaderBackend::header`,
- `Client::header`,
- `PeersClient::header`
- `ChainApi::block_header`

methods from: `BlockId<Block>` to: `Block::Hash`

This PR is part of BlockId::Number refactoring analysis (paritytech/substrate#11292)

* non-trivial usages of haeder(block_id) refactored

This may required introduction of dedicated function:
header_for_block_num

* fmt

* fix

* doc fixed

* ".git/.scripts/fmt.sh"

* BlockId removal: refactor: HeaderBackend::expect_header

It changes the arguments of `HeaderBackend::expect_header` method from: `BlockId<Block>` to: `Block::Hash`

* ".git/.scripts/fmt.sh"

* readme updated

* ".git/.scripts/fmt.sh"

* fix

Co-authored-by: parity-processbot <>

* Move MMR utils methods from pallet to primitives

Signed-off-by: Serban Iorga <serban@parity.io>

* Add method to MmrApi

* Move forks expanding logic from babe to primitives

* Implement MMR gadget

* Remove prunning logic from the MMR pallet

* Code review changes: 1st iteration

* Replace MaybeCanonEngine with CanonEngineBuilder

* fix mmr_leaves_count() for kitchen sink demo

* Update client/merkle-mountain-range/src/canon_engine.rs

Co-authored-by: Adrian Catangiu <adrian@parity.io>

* Code review changes: 2nd iteration

* fix INDEXING_PREFIX

* impl review comments

* add documentation and minor rename

Signed-off-by: Serban Iorga <serban@parity.io>
Co-authored-by: Adrian Catangiu <adrian@parity.io>

* Safe TreeRoute constructor
* Remove test duplicate
* Better tree route error info

* sc-client-babe/sp-arithmetic-fuzzer: update num-bigint and num-rational to v0.4

* update lru 0.7.5 ==> v0.8.1

* pallet-example-offchain-worker: update lite-json v0.1.3 ==> v0.2.0

* update hyper 0.14.16 ==> 0.14.20, num-fromat 0.4.0 ==> 0.4.3

* pallet-mmr: update ckb-merkle-mountain-range v0.3.2 ==> v0.5.2

* update handlebars v4.2.2 ==> v4.3.5

* `runtime_cache_size` must always be at least 1

Signed-off-by: koushiro <koushiro.cqx@gmail.com>

* default cache size with .min(1)

Signed-off-by: koushiro <koushiro.cqx@gmail.com>

* update hyper 0.14.20 ==> 0.14.22

Signed-off-by: koushiro <koushiro.cqx@gmail.com>

* update lru 0.8.0 ==> 0.8.1

Signed-off-by: koushiro <koushiro.cqx@gmail.com>

* Apply suggestions from code review

* Apply suggestions from code review

* Fix Cargo.lock

Signed-off-by: koushiro <koushiro.cqx@gmail.com>
Co-authored-by: Bastian Köcher <git@kchr.de>
Co-authored-by: Bastian Köcher <info@kchr.de>

It changes &Block::Hash argument to Block::Hash.

This PR is part of BlockId::Number refactoring analysis (paritytech/substrate#11292)

* BlockId removal: refactor: Backend::block_indexed_body

It changes the arguments of `Backend::block_indexed_body` method from: `BlockId<Block>` to: `&Block::Hash`

This PR is part of BlockId::Number refactoring analysis (paritytech/substrate#11292)

* trigger CI job

* BlockId removal: refactor: Backend::justifications

It changes the arguments of `Backend::justifications` method from: `BlockId<Block>` to: `&Block::Hash`

This PR is part of BlockId::Number refactoring analysis (paritytech/substrate#11292)

* trigger CI job

* trigger CI job

* bug fix

* match -> if

Co-authored-by: Adrian Catangiu <adrian@parity.io>

Co-authored-by: Adrian Catangiu <adrian@parity.io>

It changes the arguments of `Backend::body` method from: `BlockId<Block>` to: `&Block::Hash`

This PR is part of BlockId::Number refactoring analysis (paritytech/substrate#11292)

Co-authored-by: parity-processbot <>

* Minor naming improved

* BlockId removal refactor: Backend::state_at

* formatting

* finalized block event triggers tx maintanance

* tx-pool: enactment helper introduced

* tx-pool: ChainApi: added tree_route method

* enactment logic implemented + tests

Signed-off-by: Michal Kucharczyk <1728078+michalkucharczyk@users.noreply.github.com>

* Some additional tests

* minor improvements

* trigger CI job

* fix compilation errors

ChainApi::tree_route return type changed to Result<Option<..>>, as some
implementations (tests) are not required to provide this tree route.

* formatting

* trait removed

* implementation slightly simplified

(thanks to @koute

)

* get rid of Arc<> in EnactmentState return value

* minor improvement

* Apply suggestions from code review

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

* Apply suggestions from code review

* comment updated + formatting

* Apply suggestions from code review

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>
Co-authored-by: Davide Galassi <davxy@datawok.net>

* formatting

* finalization notification bug fix

+ new test case
+ log::warn message when finalized block is being retracted by new event

* added error message on tree_route failure

* Apply suggestions from code review

Co-authored-by: Bastian Köcher <git@kchr.de>

* use provided tree_route in Finalized event

* Option removed from ChainApi::tree_route

* doc added, test and logs improved

* handle_enactment aligned with original implementation

* use async-await

* Apply suggestions from code review

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

* Apply suggestions from code review

Co-authored-by: Bastian Köcher <git@kchr.de>

* formatting + warn->debug

* compilation error fix

* enactment_state initializers added

* enactment_state: Option removed

* manual-seal: compilation & tests fix

* manual-seal: tests fixed

* tests cleanup

* another compilation error fixed

* TreeRoute::new added

* get rid of pub hack

* one more test added

* formatting

* TreeRoute::new doc added + formatting

* Apply suggestions from code review

Co-authored-by: Davide Galassi <davxy@datawok.net>

* (bool,Option) simplified to Option

* log message improved

* yet another review suggestions applied

* get rid of hash in handle_enactment

* Apply suggestions from code review

Co-authored-by: Bastian Köcher <git@kchr.de>

* Update client/transaction-pool/src/lib.rs

Co-authored-by: Bastian Köcher <git@kchr.de>

* minor corrections

* EnactmentState moved to new file

* File header corrected

* error formatting aligned with codebase

* Apply suggestions from code review

Co-authored-by: Bastian Köcher <git@kchr.de>

* remove commented code

* small nits

Signed-off-by: Michal Kucharczyk <1728078+michalkucharczyk@users.noreply.github.com>
Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>
Co-authored-by: Davide Galassi <davxy@datawok.net>
Co-authored-by: Bastian Köcher <git@kchr.de>
Co-authored-by: André Silva <andrerfosilva@gmail.com>

* Apply some clippy hints

* Revert clippy ci changes

* Update client/cli/src/commands/generate.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update client/cli/src/commands/inspect_key.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update client/db/src/bench.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update client/db/src/bench.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update client/service/src/client/block_rules.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update client/service/src/client/block_rules.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update client/network/src/transactions.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update client/network/src/protocol.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Revert due to missing `or_default` function.

* Fix compilation and simplify code

* Undo change that corrupts benchmark.

* fix clippy

* Update client/service/test/src/lib.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update client/state-db/src/noncanonical.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update client/state-db/src/noncanonical.rs

remove leftovers!

* Update client/tracing/src/logging/directives.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update utils/fork-tree/src/lib.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* added needed ref

* Update frame/referenda/src/benchmarking.rs

* Simplify byte-vec creation

* let's just not overlap the ranges

* Correction

* cargo fmt

* Update utils/frame/benchmarking-cli/src/shared/stats.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update utils/frame/benchmarking-cli/src/pallet/command.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update utils/frame/benchmarking-cli/src/pallet/command.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>
Co-authored-by: Giles Cope <gilescope@gmail.com>

* Finality notification: Optimize calculation of stale heads

While looking into some problem on Versi where a collator seemed to be stuck. I found out that it
was not stuck but there was a huge gap between last finalized and best block. This lead to a lot
leaves and it was basically trapped inside some loop of reading block headers from the db to find
the stale heads. While looking into this I found out that `leaves` already supports the feature to
give us the stale heads relative easily. However, the semantics change a little bit. Instead of
returning all stale heads of blocks that are not reachable anymore after finalizing a block, we
currently only return heads with a number lower than the finalized block. This should be no problem,
because these other leaves that are stale will be returned later when a block gets finalized which
number is bigger than the block number of these leaves.

While doing that, I also changed `tree_route` of the `FinalityNotification` to include the
`old_finalized`. Based on the comment I assumed that this was already part of it. However, if
wanted, I can revert this change.

* FMT

* Update client/service/src/client/client.rs

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

* Do not include the last finalized block

* Rename function

* FMT

* Fix tests

* Update figure

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

* Clean obsolete BABE weight data
* Take out test assertion from check closure
* Optimize metadata access using `HeaderMetadata` trait
* Apply suggestions from code review
* Introduce finalize and import pre-commit synchronous actions
* Do not hold locks between internal methods calls
* Remove unused generic bound
* Apply suggestions from code review
* Register BABE's pre-commit actions on `block_import` instead of `start_babe`
* PreCommit actions should be `Fn` instead of `FnMut`
* More robust safenet in case of malformed finality notifications

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>
Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

Add a new host function for reporting fatal errors; make WASM backtraces readable when printing out errors (#10741)

* Add a new host function for reporting fatal errors

* Fix one of the wasmtime executor tests

* Have `#[runtime_interface(wasm_only)]` actually mean WASM-only, and not no_std-only

* Print out errors through `Display` instead of `Debug`

* Switch one more trait to require `Error` for its error instead of only `Debug`

* Align to review comments

* Fast sync fixes

* Fix gap blocks validation

* Updated test

* Formatting

* Networking test

* Remove light client, change tries and CHTs

* Update tests

* fmt

* Restore changes_root

* Fixed benches

* Cargo fmt

* fmt

* fmt

* Gap sync

* Gap epoch test

* Simplified network requests

* Update client/db/src/utils.rs

Co-authored-by: cheme <emericchevalier.pro@gmail.com>

* Fixed v1 migration and added some comments

* Next epoch is always regular

* Removed fork tree change

* Apply suggestions from code review

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Added a comment and converted assert to error

Co-authored-by: cheme <emericchevalier.pro@gmail.com>
Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* reformat everything again

* manual formatting

* last manual fix

* Fix build

* moved client code out of primitives

* bump ci

* Fixup from merge.

* Removed unused deps thanks to review feedback

* Removing unneeded deps

* updating lock file

* note about rustfmt

* fixed typo to bump ci

* Move lonely CacheKeyId to parent

* cargo fmt

* updating import style

* Update docs/STYLE_GUIDE.md

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

* Fix metadata updates on existing headers

* Fail set_head on ancient blocks

* Fmt unrelated code