referrerpolicy=no-referrer-when-downgrade

frame_election_provider_support/
traits.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// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14// distributed under the License is distributed on an "AS IS" BASIS,
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18//! Traits for the election operations.
19
20use crate::{Assignment, IdentifierT, IndexAssignmentOf, PerThing128, VoteWeight};
21use alloc::vec::Vec;
22use codec::Encode;
23use core::fmt::Debug;
24use scale_info::TypeInfo;
25use sp_arithmetic::traits::{Bounded, UniqueSaturatedInto};
26use sp_npos_elections::{ElectionScore, Error, EvaluateSupport};
27
28/// An opaque index-based, NPoS solution type.
29pub trait NposSolution
30where
31	Self: Sized + for<'a> TryFrom<&'a [IndexAssignmentOf<Self>], Error = Error>,
32{
33	/// The maximum number of votes that are allowed.
34	const LIMIT: usize;
35
36	/// The voter type. Needs to be an index (convert to usize).
37	type VoterIndex: UniqueSaturatedInto<usize>
38		+ TryInto<usize>
39		+ TryFrom<usize>
40		+ Debug
41		+ Copy
42		+ Clone
43		+ Bounded
44		+ Encode
45		+ Ord
46		+ PartialOrd
47		+ TypeInfo;
48
49	/// The target type. Needs to be an index (convert to usize).
50	type TargetIndex: UniqueSaturatedInto<usize>
51		+ TryInto<usize>
52		+ TryFrom<usize>
53		+ Debug
54		+ Copy
55		+ Clone
56		+ Bounded
57		+ Encode
58		+ Ord
59		+ PartialOrd
60		+ TypeInfo;
61
62	/// The weight/accuracy type of each vote.
63	type Accuracy: PerThing128;
64
65	/// Get the length of all the voters that this type is encoding.
66	///
67	/// This is basically the same as the number of assignments, or number of active voters.
68	fn voter_count(&self) -> usize;
69
70	/// Get the total count of edges.
71	///
72	/// This is effectively in the range of {[`Self::voter_count`], [`Self::voter_count`] *
73	/// [`Self::LIMIT`]}.
74	fn edge_count(&self) -> usize;
75
76	/// Get the number of unique targets in the whole struct.
77	///
78	/// Once presented with a list of winners, this set and the set of winners must be
79	/// equal.
80	fn unique_targets(&self) -> Vec<Self::TargetIndex>;
81
82	/// Get the average edge count.
83	fn average_edge_count(&self) -> usize {
84		self.edge_count().checked_div(self.voter_count()).unwrap_or(0)
85	}
86
87	/// Compute the score of this solution type.
88	fn score<A, FS>(
89		self,
90		stake_of: FS,
91		voter_at: impl Fn(Self::VoterIndex) -> Option<A>,
92		target_at: impl Fn(Self::TargetIndex) -> Option<A>,
93	) -> Result<ElectionScore, Error>
94	where
95		for<'r> FS: Fn(&'r A) -> VoteWeight,
96		A: IdentifierT,
97	{
98		let ratio = self.into_assignment(voter_at, target_at)?;
99		let staked =
100			sp_npos_elections::helpers::assignment_ratio_to_staked_normalized(ratio, stake_of)?;
101		let supports = sp_npos_elections::to_supports(&staked);
102		Ok(supports.evaluate())
103	}
104
105	/// Remove a certain voter.
106	///
107	/// This will only search until the first instance of `to_remove`, and return true. If
108	/// no instance is found (no-op), then it returns false.
109	///
110	/// In other words, if this return true, exactly **one** element must have been removed self.
111	fn remove_voter(&mut self, to_remove: Self::VoterIndex) -> bool;
112
113	/// Build self from a list of assignments.
114	fn from_assignment<FV, FT, A>(
115		assignments: &[Assignment<A, Self::Accuracy>],
116		voter_index: FV,
117		target_index: FT,
118	) -> Result<Self, Error>
119	where
120		A: IdentifierT,
121		for<'r> FV: Fn(&'r A) -> Option<Self::VoterIndex>,
122		for<'r> FT: Fn(&'r A) -> Option<Self::TargetIndex>;
123
124	/// Convert self into a `Vec<Assignment<A, Self::Accuracy>>`
125	fn into_assignment<A: IdentifierT>(
126		self,
127		voter_at: impl Fn(Self::VoterIndex) -> Option<A>,
128		target_at: impl Fn(Self::TargetIndex) -> Option<A>,
129	) -> Result<Vec<Assignment<A, Self::Accuracy>>, Error>;
130
131	/// Sort self by the means of the given function.
132	///
133	/// This might be helpful to allow for easier trimming.
134	fn sort<F>(&mut self, voter_stake: F)
135	where
136		F: FnMut(&Self::VoterIndex) -> VoteWeight;
137
138	/// Remove the least staked voter.
139	///
140	/// This is ONLY sensible to do if [`Self::sort`] has been called on the struct at least once.
141	fn remove_weakest_sorted<F>(&mut self, voter_stake: F) -> Option<Self::VoterIndex>
142	where
143		F: FnMut(&Self::VoterIndex) -> VoteWeight;
144
145	/// Make this solution corrupt. This should set the index of a voter to `Bounded::max_value()`.
146	///
147	/// Obviously, this is only useful for testing.
148	fn corrupt(&mut self);
149}