sp_domains/
extrinsics.rs

1#[cfg(not(feature = "std"))]
2extern crate alloc;
3
4#[cfg(not(feature = "std"))]
5use alloc::vec::Vec;
6use domain_runtime_primitives::opaque::AccountId;
7use rand::seq::SliceRandom;
8use rand::SeedableRng;
9use rand_chacha::ChaCha8Rng;
10use sp_state_machine::trace;
11use sp_std::collections::btree_map::BTreeMap;
12use sp_std::collections::vec_deque::VecDeque;
13use sp_std::fmt::Debug;
14use subspace_core_primitives::Randomness;
15
16pub fn deduplicate_and_shuffle_extrinsics<Extrinsic>(
17    mut extrinsics: Vec<(Option<AccountId>, Extrinsic)>,
18    shuffling_seed: Randomness,
19) -> VecDeque<Extrinsic>
20where
21    Extrinsic: Debug + PartialEq + Clone,
22{
23    let mut seen = Vec::new();
24    extrinsics.retain(|(_, uxt)| match seen.contains(uxt) {
25        true => {
26            trace!(extrinsic = ?uxt, "Duplicated extrinsic");
27            false
28        }
29        false => {
30            seen.push(uxt.clone());
31            true
32        }
33    });
34    drop(seen);
35    trace!(?extrinsics, "Origin deduplicated extrinsics");
36    shuffle_extrinsics::<Extrinsic, AccountId>(extrinsics, shuffling_seed)
37}
38
39/// Shuffles the extrinsics in a deterministic way.
40///
41/// The extrinsics are grouped by the signer. The extrinsics without a signer, i.e., unsigned
42/// extrinsics, are considered as a special group. The items in different groups are cross shuffled,
43/// while the order of items inside the same group is still maintained.
44pub fn shuffle_extrinsics<Extrinsic: Debug, AccountId: Ord + Clone>(
45    extrinsics: Vec<(Option<AccountId>, Extrinsic)>,
46    shuffling_seed: Randomness,
47) -> VecDeque<Extrinsic> {
48    let mut rng = ChaCha8Rng::from_seed(*shuffling_seed);
49
50    let mut positions = extrinsics
51        .iter()
52        .map(|(maybe_signer, _)| maybe_signer)
53        .cloned()
54        .collect::<Vec<_>>();
55
56    // Shuffles the positions using Fisher–Yates algorithm.
57    positions.shuffle(&mut rng);
58
59    let mut grouped_extrinsics: BTreeMap<Option<AccountId>, VecDeque<_>> = extrinsics
60        .into_iter()
61        .fold(BTreeMap::new(), |mut groups, (maybe_signer, tx)| {
62            groups.entry(maybe_signer).or_default().push_back(tx);
63            groups
64        });
65
66    // The relative ordering for the items in the same group does not change.
67    let shuffled_extrinsics = positions
68        .into_iter()
69        .map(|maybe_signer| {
70            grouped_extrinsics
71                .get_mut(&maybe_signer)
72                .expect("Extrinsics are grouped correctly; qed")
73                .pop_front()
74                .expect("Extrinsic definitely exists as it's correctly grouped above; qed")
75        })
76        .collect::<VecDeque<_>>();
77
78    trace!(?shuffled_extrinsics, "Shuffled extrinsics");
79
80    shuffled_extrinsics
81}
sp_domains/extrinsics.rs

sp_domains/
extrinsics.rs
