#![cfg_attr(not(feature = "std"), no_std)]
use sp_std::{prelude::*, collections::btree_map::BTreeMap, convert::TryFrom};
use sp_runtime::{
PerThing, Rational128, RuntimeDebug,
helpers_128bit::multiply_by_rational,
};
use sp_runtime::traits::{
Zero, Convert, Member, AtLeast32Bit, SaturatedConversion, Bounded, Saturating,
};
#[cfg(test)]
mod mock;
#[cfg(test)]
mod tests;
pub type ExtendedBalance = u128;
const DEN: u128 = u128::max_value();
#[derive(Clone, Default, RuntimeDebug)]
pub struct Candidate<AccountId> {
pub who: AccountId,
pub score: Rational128,
approval_stake: ExtendedBalance,
elected: bool,
}
#[derive(Clone, Default, RuntimeDebug)]
pub struct Voter<AccountId> {
who: AccountId,
edges: Vec<Edge<AccountId>>,
budget: ExtendedBalance,
load: Rational128,
}
#[derive(Clone, Default, RuntimeDebug)]
pub struct Edge<AccountId> {
who: AccountId,
load: Rational128,
candidate_index: usize,
}
pub type PhragmenAssignment<AccountId, T> = (AccountId, T);
pub type PhragmenStakedAssignment<AccountId> = (AccountId, ExtendedBalance);
#[derive(RuntimeDebug)]
pub struct PhragmenResult<AccountId, T: PerThing> {
pub winners: Vec<(AccountId, ExtendedBalance)>,
pub assignments: Vec<(AccountId, Vec<PhragmenAssignment<AccountId, T>>)>
}
#[derive(Default, RuntimeDebug)]
#[cfg_attr(feature = "std", derive(serde::Serialize, serde::Deserialize, Eq, PartialEq))]
pub struct Support<AccountId> {
pub total: ExtendedBalance,
pub voters: Vec<PhragmenStakedAssignment<AccountId>>,
}
pub type SupportMap<A> = BTreeMap<A, Support<A>>;
pub fn elect<AccountId, Balance, C, R>(
candidate_count: usize,
minimum_candidate_count: usize,
initial_candidates: Vec<AccountId>,
initial_voters: Vec<(AccountId, Balance, Vec<AccountId>)>,
) -> Option<PhragmenResult<AccountId, R>> where
AccountId: Default + Ord + Member,
Balance: Default + Copy + AtLeast32Bit,
C: Convert<Balance, u64> + Convert<u128, Balance>,
R: PerThing,
{
let to_votes = |b: Balance| <C as Convert<Balance, u64>>::convert(b) as ExtendedBalance;
let mut elected_candidates: Vec<(AccountId, ExtendedBalance)>;
let mut assigned: Vec<(AccountId, Vec<PhragmenAssignment<AccountId, R>>)>;
let mut c_idx_cache = BTreeMap::<AccountId, usize>::new();
let num_voters = initial_candidates.len() + initial_voters.len();
let mut voters: Vec<Voter<AccountId>> = Vec::with_capacity(num_voters);
let mut candidates = initial_candidates
.into_iter()
.enumerate()
.map(|(idx, who)| {
c_idx_cache.insert(who.clone(), idx);
Candidate { who, ..Default::default() }
})
.collect::<Vec<Candidate<AccountId>>>();
if candidates.len() < minimum_candidate_count { return None; }
voters.extend(initial_voters.into_iter().map(|(who, voter_stake, votes)| {
let mut edges: Vec<Edge<AccountId>> = Vec::with_capacity(votes.len());
for v in votes {
if let Some(idx) = c_idx_cache.get(&v) {
candidates[*idx].approval_stake = candidates[*idx].approval_stake
.saturating_add(to_votes(voter_stake));
edges.push(Edge { who: v.clone(), candidate_index: *idx, ..Default::default() });
}
}
Voter {
who,
edges: edges,
budget: to_votes(voter_stake),
load: Rational128::zero(),
}
}));
let to_elect = candidate_count.min(candidates.len());
elected_candidates = Vec::with_capacity(candidate_count);
assigned = Vec::with_capacity(candidate_count);
for _round in 0..to_elect {
for c in &mut candidates {
if !c.elected {
if c.approval_stake.is_zero() {
c.score = Rational128::from_unchecked(DEN, 0);
} else {
c.score = Rational128::from(DEN / c.approval_stake, DEN);
}
}
}
for n in &voters {
for e in &n.edges {
let c = &mut candidates[e.candidate_index];
if !c.elected && !c.approval_stake.is_zero() {
let temp_n = multiply_by_rational(
n.load.n(),
n.budget,
c.approval_stake,
).unwrap_or(Bounded::max_value());
let temp_d = n.load.d();
let temp = Rational128::from(temp_n, temp_d);
c.score = c.score.lazy_saturating_add(temp);
}
}
}
if let Some(winner) = candidates
.iter_mut()
.filter(|c| !c.elected)
.min_by_key(|c| c.score)
{
winner.elected = true;
for n in &mut voters {
for e in &mut n.edges {
if e.who == winner.who {
e.load = winner.score.lazy_saturating_sub(n.load);
n.load = winner.score;
}
}
}
elected_candidates.push((winner.who.clone(), winner.approval_stake));
} else {
break
}
}
for n in &mut voters {
let mut assignment = (n.who.clone(), vec![]);
for e in &mut n.edges {
if elected_candidates.iter().position(|(ref c, _)| *c == e.who).is_some() {
let per_bill_parts: R::Inner =
{
if n.load == e.load {
R::ACCURACY
} else {
if e.load.d() == n.load.d() {
let desired_scale: u128 = R::ACCURACY.saturated_into();
let parts = multiply_by_rational(
desired_scale,
e.load.n(),
n.load.n(),
)
.unwrap_or(Bounded::max_value());
TryFrom::try_from(parts)
.unwrap_or(Bounded::max_value())
} else {
Zero::zero()
}
}
};
let per_thing = R::from_parts(per_bill_parts);
assignment.1.push((e.who.clone(), per_thing));
}
}
if assignment.1.len() > 0 {
let vote_count: R::Inner = assignment.1.len().saturated_into();
let len = assignment.1.len();
let mut sum: R::Inner = Zero::zero();
assignment.1.iter().for_each(|a| sum = sum.saturating_add(a.1.deconstruct()));
let accuracy = R::ACCURACY;
let diff = accuracy.saturating_sub(sum);
let diff_per_vote = (diff / vote_count).min(accuracy);
if !diff_per_vote.is_zero() {
for i in 0..len {
let current_ratio = assignment.1[i % len].1;
let next_ratio = current_ratio
.saturating_add(R::from_parts(diff_per_vote));
assignment.1[i % len].1 = next_ratio;
}
}
let remainder = diff - diff_per_vote * vote_count;
for i in 0..remainder.saturated_into::<usize>() {
let current_ratio = assignment.1[i % len].1;
let next_ratio = current_ratio.saturating_add(R::from_parts(1u8.into()));
assignment.1[i % len].1 = next_ratio;
}
assigned.push(assignment);
}
}
Some(PhragmenResult {
winners: elected_candidates,
assignments: assigned,
})
}
pub fn build_support_map<Balance, AccountId, FS, C, R>(
elected_stashes: &Vec<AccountId>,
assignments: &Vec<(AccountId, Vec<PhragmenAssignment<AccountId, R>>)>,
stake_of: FS,
) -> SupportMap<AccountId> where
AccountId: Default + Ord + Member,
Balance: Default + Copy + AtLeast32Bit,
C: Convert<Balance, u64> + Convert<u128, Balance>,
for<'r> FS: Fn(&'r AccountId) -> Balance,
R: PerThing + sp_std::ops::Mul<ExtendedBalance, Output=ExtendedBalance>,
{
let to_votes = |b: Balance| <C as Convert<Balance, u64>>::convert(b) as ExtendedBalance;
let mut supports = <SupportMap<AccountId>>::new();
elected_stashes
.iter()
.for_each(|e| { supports.insert(e.clone(), Default::default()); });
for (n, assignment) in assignments.iter() {
for (c, per_thing) in assignment.iter() {
let nominator_stake = to_votes(stake_of(n));
let other_stake = *per_thing * nominator_stake;
if let Some(support) = supports.get_mut(c) {
support.voters.push((n.clone(), other_stake));
support.total = support.total.saturating_add(other_stake);
}
}
}
supports
}
pub fn equalize<Balance, AccountId, C, FS>(
mut assignments: Vec<(AccountId, Vec<PhragmenStakedAssignment<AccountId>>)>,
supports: &mut SupportMap<AccountId>,
tolerance: ExtendedBalance,
iterations: usize,
stake_of: FS,
) where
C: Convert<Balance, u64> + Convert<u128, Balance>,
for<'r> FS: Fn(&'r AccountId) -> Balance,
AccountId: Ord + Clone,
{
for _i in 0..iterations {
let mut max_diff = 0;
for (voter, assignment) in assignments.iter_mut() {
let voter_budget = stake_of(&voter);
let diff = do_equalize::<_, _, C>(
voter,
voter_budget,
assignment,
supports,
tolerance,
);
if diff > max_diff { max_diff = diff; }
}
if max_diff < tolerance {
break;
}
}
}
fn do_equalize<Balance, AccountId, C>(
voter: &AccountId,
budget_balance: Balance,
elected_edges: &mut Vec<PhragmenStakedAssignment<AccountId>>,
support_map: &mut SupportMap<AccountId>,
tolerance: ExtendedBalance
) -> ExtendedBalance where
C: Convert<Balance, u64> + Convert<u128, Balance>,
AccountId: Ord + Clone,
{
let to_votes = |b: Balance|
<C as Convert<Balance, u64>>::convert(b) as ExtendedBalance;
let budget = to_votes(budget_balance);
if elected_edges.is_empty() || elected_edges.len() == 1 { return 0; }
let stake_used = elected_edges
.iter()
.fold(0 as ExtendedBalance, |s, e| s.saturating_add(e.1));
let backed_stakes_iter = elected_edges
.iter()
.filter_map(|e| support_map.get(&e.0))
.map(|e| e.total);
let backing_backed_stake = elected_edges
.iter()
.filter(|e| e.1 > 0)
.filter_map(|e| support_map.get(&e.0))
.map(|e| e.total)
.collect::<Vec<ExtendedBalance>>();
let mut difference;
if backing_backed_stake.len() > 0 {
let max_stake = backing_backed_stake
.iter()
.max()
.expect("vector with positive length will have a max; qed");
let min_stake = backed_stakes_iter
.min()
.expect("iterator with positive length will have a min; qed");
difference = max_stake.saturating_sub(min_stake);
difference = difference.saturating_add(budget.saturating_sub(stake_used));
if difference < tolerance {
return difference;
}
} else {
difference = budget;
}
elected_edges.iter_mut().for_each(|e| {
if let Some(support) = support_map.get_mut(&e.0) {
support.total = support.total.saturating_sub(e.1);
support.voters.retain(|i_support| i_support.0 != *voter);
}
e.1 = 0;
});
elected_edges.sort_unstable_by_key(|e|
if let Some(e) = support_map.get(&e.0) { e.total } else { Zero::zero() }
);
let mut cumulative_stake: ExtendedBalance = 0;
let mut last_index = elected_edges.len() - 1;
let mut idx = 0usize;
for e in &mut elected_edges[..] {
if let Some(support) = support_map.get_mut(&e.0) {
let stake = support.total;
let stake_mul = stake.saturating_mul(idx as ExtendedBalance);
let stake_sub = stake_mul.saturating_sub(cumulative_stake);
if stake_sub > budget {
last_index = idx.checked_sub(1).unwrap_or(0);
break;
}
cumulative_stake = cumulative_stake.saturating_add(stake);
}
idx += 1;
}
let last_stake = elected_edges[last_index].1;
let split_ways = last_index + 1;
let excess = budget
.saturating_add(cumulative_stake)
.saturating_sub(last_stake.saturating_mul(split_ways as ExtendedBalance));
elected_edges.iter_mut().take(split_ways).for_each(|e| {
if let Some(support) = support_map.get_mut(&e.0) {
e.1 = (excess / split_ways as ExtendedBalance)
.saturating_add(last_stake)
.saturating_sub(support.total);
support.total = support.total.saturating_add(e.1);
support.voters.push((voter.clone(), e.1));
}
});
difference
}