sp_npos_elections/
assignments.rs

1// This file is part of Substrate.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18//! Structs and helpers for distributing a voter's stake among various winners.
19
20use crate::{ExtendedBalance, IdentifierT, PerThing128};
21use alloc::vec::Vec;
22#[cfg(feature = "serde")]
23use codec::{Decode, Encode};
24use sp_arithmetic::{
25	traits::{Bounded, Zero},
26	Normalizable, PerThing,
27};
28use sp_core::RuntimeDebug;
29
30/// A voter's stake assignment among a set of targets, represented as ratios.
31#[derive(RuntimeDebug, Clone, Default)]
32#[cfg_attr(feature = "serde", derive(PartialEq, Eq, Encode, Decode))]
33pub struct Assignment<AccountId, P: PerThing> {
34	/// Voter's identifier.
35	pub who: AccountId,
36	/// The distribution of the voter's stake.
37	pub distribution: Vec<(AccountId, P)>,
38}
39
40impl<AccountId: IdentifierT, P: PerThing128> Assignment<AccountId, P> {
41	/// Convert from a ratio assignment into one with absolute values aka. [`StakedAssignment`].
42	///
43	/// It needs `stake` which is the total budget of the voter.
44	///
45	/// Note that this might create _un-normalized_ assignments, due to accuracy loss of `P`. Call
46	/// site might compensate by calling `try_normalize()` on the returned `StakedAssignment` as a
47	/// post-precessing.
48	///
49	/// If an edge ratio is [`Bounded::min_value()`], it is dropped. This edge can never mean
50	/// anything useful.
51	pub fn into_staked(self, stake: ExtendedBalance) -> StakedAssignment<AccountId> {
52		let distribution = self
53			.distribution
54			.into_iter()
55			.filter_map(|(target, p)| {
56				// if this ratio is zero, then skip it.
57				if p.is_zero() {
58					None
59				} else {
60					// NOTE: this mul impl will always round to the nearest number, so we might both
61					// overflow and underflow.
62					let distribution_stake = p * stake;
63					Some((target, distribution_stake))
64				}
65			})
66			.collect::<Vec<(AccountId, ExtendedBalance)>>();
67
68		StakedAssignment { who: self.who, distribution }
69	}
70
71	/// Try and normalize this assignment.
72	///
73	/// If `Ok(())` is returned, then the assignment MUST have been successfully normalized to 100%.
74	///
75	/// ### Errors
76	///
77	/// This will return only if the internal `normalize` fails. This can happen if sum of
78	/// `self.distribution.map(|p| p.deconstruct())` fails to fit inside `UpperOf<P>`. A user of
79	/// this crate may statically assert that this can never happen and safely `expect` this to
80	/// return `Ok`.
81	pub fn try_normalize(&mut self) -> Result<(), &'static str> {
82		self.distribution
83			.iter()
84			.map(|(_, p)| *p)
85			.collect::<Vec<_>>()
86			.normalize(P::one())
87			.map(|normalized_ratios| {
88				self.distribution.iter_mut().zip(normalized_ratios).for_each(
89					|((_, old), corrected)| {
90						*old = corrected;
91					},
92				)
93			})
94	}
95}
96
97/// A voter's stake assignment among a set of targets, represented as absolute values in the scale
98/// of [`ExtendedBalance`].
99#[derive(RuntimeDebug, Clone, Default)]
100#[cfg_attr(feature = "serde", derive(PartialEq, Eq, Encode, Decode))]
101pub struct StakedAssignment<AccountId> {
102	/// Voter's identifier
103	pub who: AccountId,
104	/// The distribution of the voter's stake.
105	pub distribution: Vec<(AccountId, ExtendedBalance)>,
106}
107
108impl<AccountId> StakedAssignment<AccountId> {
109	/// Converts self into the normal [`Assignment`] type.
110	///
111	/// NOTE: This will always round down, and thus the results might be less than a full 100% `P`.
112	/// Use a normalization post-processing to fix this. The data type returned here will
113	/// potentially get used to create a compact type; a compact type requires sum of ratios to be
114	/// less than 100% upon un-compacting.
115	///
116	/// If an edge stake is so small that it cannot be represented in `T`, it is ignored. This edge
117	/// can never be re-created and does not mean anything useful anymore.
118	pub fn into_assignment<P: PerThing>(self) -> Assignment<AccountId, P>
119	where
120		AccountId: IdentifierT,
121	{
122		let stake = self.total();
123		// most likely, the size of the staked assignment and normal assignments will be the same,
124		// so we pre-allocate it to prevent a sudden 2x allocation. `filter_map` starts with a size
125		// of 0 by default.
126		// https://www.reddit.com/r/rust/comments/3spfh1/does_collect_allocate_more_than_once_while/
127		let mut distribution = Vec::<(AccountId, P)>::with_capacity(self.distribution.len());
128		self.distribution.into_iter().for_each(|(target, w)| {
129			let per_thing = P::from_rational(w, stake);
130			if per_thing != Bounded::min_value() {
131				distribution.push((target, per_thing));
132			}
133		});
134
135		Assignment { who: self.who, distribution }
136	}
137
138	/// Try and normalize this assignment.
139	///
140	/// If `Ok(())` is returned, then the assignment MUST have been successfully normalized to
141	/// `stake`.
142	///
143	/// NOTE: current implementation of `.normalize` is almost safe to `expect()` upon. The only
144	/// error case is when the input cannot fit in `T`, or the sum of input cannot fit in `T`.
145	/// Sadly, both of these are dependent upon the implementation of `VoteLimit`, i.e. the limit of
146	/// edges per voter which is enforced from upstream. Hence, at this crate, we prefer returning a
147	/// result and a use the name prefix `try_`.
148	pub fn try_normalize(&mut self, stake: ExtendedBalance) -> Result<(), &'static str> {
149		self.distribution
150			.iter()
151			.map(|(_, ref weight)| *weight)
152			.collect::<Vec<_>>()
153			.normalize(stake)
154			.map(|normalized_weights| {
155				self.distribution.iter_mut().zip(normalized_weights.into_iter()).for_each(
156					|((_, weight), corrected)| {
157						*weight = corrected;
158					},
159				)
160			})
161	}
162
163	/// Get the total stake of this assignment (aka voter budget).
164	pub fn total(&self) -> ExtendedBalance {
165		self.distribution.iter().fold(Zero::zero(), |a, b| a.saturating_add(b.1))
166	}
167}
sp_npos_elections/assignments.rs

sp_npos_elections/
assignments.rs
