pallet_democracy/
vote_threshold.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//! Voting thresholds.
19
20use crate::Tally;
21use codec::{Decode, DecodeWithMemTracking, Encode, MaxEncodedLen};
22use core::ops::{Add, Div, Mul, Rem};
23use scale_info::TypeInfo;
24#[cfg(feature = "std")]
25use serde::{Deserialize, Serialize};
26use sp_runtime::traits::{IntegerSquareRoot, Zero};
27
28/// A means of determining if a vote is past pass threshold.
29#[derive(
30	Clone,
31	Copy,
32	PartialEq,
33	Eq,
34	Encode,
35	DecodeWithMemTracking,
36	MaxEncodedLen,
37	Decode,
38	sp_runtime::RuntimeDebug,
39	TypeInfo,
40)]
41#[cfg_attr(feature = "std", derive(Serialize, Deserialize))]
42pub enum VoteThreshold {
43	/// A supermajority of approvals is needed to pass this vote.
44	SuperMajorityApprove,
45	/// A supermajority of rejects is needed to fail this vote.
46	SuperMajorityAgainst,
47	/// A simple majority of approvals is needed to pass this vote.
48	SimpleMajority,
49}
50
51pub trait Approved<Balance> {
52	/// Given a `tally` of votes and a total size of `electorate`, this returns `true` if the
53	/// overall outcome is in favor of approval according to `self`'s threshold method.
54	fn approved(&self, tally: Tally<Balance>, electorate: Balance) -> bool;
55}
56
57/// Return `true` iff `n1 / d1 < n2 / d2`. `d1` and `d2` may not be zero.
58fn compare_rationals<
59	T: Zero + Mul<T, Output = T> + Div<T, Output = T> + Rem<T, Output = T> + Ord + Copy,
60>(
61	mut n1: T,
62	mut d1: T,
63	mut n2: T,
64	mut d2: T,
65) -> bool {
66	// Uses a continued fractional representation for a non-overflowing compare.
67	// Detailed at https://janmr.com/blog/2014/05/comparing-rational-numbers-without-overflow/.
68	loop {
69		let q1 = n1 / d1;
70		let q2 = n2 / d2;
71		if q1 < q2 {
72			return true
73		}
74		if q2 < q1 {
75			return false
76		}
77		let r1 = n1 % d1;
78		let r2 = n2 % d2;
79		if r2.is_zero() {
80			return false
81		}
82		if r1.is_zero() {
83			return true
84		}
85		n1 = d2;
86		n2 = d1;
87		d1 = r2;
88		d2 = r1;
89	}
90}
91
92impl<
93		Balance: IntegerSquareRoot
94			+ Zero
95			+ Ord
96			+ Add<Balance, Output = Balance>
97			+ Mul<Balance, Output = Balance>
98			+ Div<Balance, Output = Balance>
99			+ Rem<Balance, Output = Balance>
100			+ Copy,
101	> Approved<Balance> for VoteThreshold
102{
103	fn approved(&self, tally: Tally<Balance>, electorate: Balance) -> bool {
104		let sqrt_voters = tally.turnout.integer_sqrt();
105		let sqrt_electorate = electorate.integer_sqrt();
106		if sqrt_voters.is_zero() {
107			return false
108		}
109		match *self {
110			VoteThreshold::SuperMajorityApprove =>
111				compare_rationals(tally.nays, sqrt_voters, tally.ayes, sqrt_electorate),
112			VoteThreshold::SuperMajorityAgainst =>
113				compare_rationals(tally.nays, sqrt_electorate, tally.ayes, sqrt_voters),
114			VoteThreshold::SimpleMajority => tally.ayes > tally.nays,
115		}
116	}
117}
118
119#[cfg(test)]
120mod tests {
121	use super::*;
122
123	#[test]
124	fn should_work() {
125		assert!(!VoteThreshold::SuperMajorityApprove
126			.approved(Tally { ayes: 60, nays: 50, turnout: 110 }, 210));
127		assert!(VoteThreshold::SuperMajorityApprove
128			.approved(Tally { ayes: 100, nays: 50, turnout: 150 }, 210));
129	}
130}
pallet_democracy/vote_threshold.rs

pallet_democracy/
vote_threshold.rs
