]> Untitled Git - bdk/commit
feat(chain): introduce new `list_ordered_canonical_txs`
authorLeonardo Lima <oleonardolima@users.noreply.github.com>
Tue, 23 Sep 2025 06:35:50 +0000 (03:35 -0300)
committerLeonardo Lima <oleonardolima@users.noreply.github.com>
Sat, 22 Nov 2025 04:39:23 +0000 (01:39 -0300)
commit12c107637eb46cf9674d09067f65d07d1701f60d
tree7faaddf00c3ec5eb2b8cfa8f50f76af3264d2744
parentf34117b7843f1d85a041d58601fbc7bed7695a86
feat(chain): introduce new `list_ordered_canonical_txs`

Adds a new `list_ordered_canonical_txs` method which uses the new
`TopologicalIterator` on top of the result of `list_canonical_txs`
method, yielding the canonical txs in topological spending order.

The new `list_ordered_canonical_txs` guarantees that spending
transactions appears after their inputs, in topological "spending order".

- Introduce the new `TopologicalIterator` for level-based topological
  sorting, based on Kahn's Algorithm, it uses the `ChainPosition` for
  sorting within the same graph level, and it takes an `Iterator<Item =
CanonicalTx<'a, Arc<Transaction>, A>> of canonical txs.
- Introduce the new `list_ordered_canonical_txs` method to `TxGraph`.
- Update the existing tests under `test_tx_graph.rs` to verify the
  topological ordering correctness.
- Update the existing `canonicalization` benchmark to also use the new
  `topological_ordered_txs` method.

NOTE:
- I've squashed the previous commits into a single one, as they're
changing the same files and applies to the same scope.
- Also, I've partially used Claude to help with the Kahn's Algorithm.

Co-Authored-By: Claude <noreply@anthropic.com>
crates/chain/benches/canonicalization.rs
crates/chain/src/canonical_iter.rs
crates/chain/src/tx_graph.rs
crates/chain/tests/test_indexed_tx_graph.rs
crates/chain/tests/test_tx_graph.rs
examples/example_bitcoind_rpc_polling/src/main.rs
examples/example_electrum/src/main.rs
examples/example_esplora/src/main.rs