lib.rs

// This file is part of Substrate.

// Copyright (C) 2019-2020 Parity Technologies (UK) Ltd.
// SPDX-License-Identifier: Apache-2.0

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// 	http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! # Phragmen Election Module.
//!
//! An election module based on sequential phragmen.
//!
//! ### Term and Round
//!
//! The election happens in _rounds_: every `N` blocks, all previous members are retired and a new
//! set is elected (which may or may not have an intersection with the previous set). Each round
//! lasts for some number of blocks defined by `TermDuration` storage item. The words _term_ and
//! _round_ can be used interchangeably in this context.
//!
//! `TermDuration` might change during a round. This can shorten or extend the length of the round.
//! The next election round's block number is never stored but rather always checked on the fly.
//! Based on the current block number and `TermDuration`, the condition `BlockNumber % TermDuration
//! == 0` being satisfied will always trigger a new election round.
//!
//! ### Voting
//!
//! Voters can vote for any set of the candidates by providing a list of account ids. Invalid votes
//! (voting for non-candidates) are ignored during election. Yet, a voter _might_ vote for a future
//! candidate. Voters reserve a bond as they vote. Each vote defines a `value`. This amount is
//! locked from the account of the voter and indicates the weight of the vote. Voters can update
//! their votes at any time by calling `vote()` again. This keeps the bond untouched but can
//! optionally change the locked `value`. After a round, votes are kept and might still be valid for
//! further rounds. A voter is responsible for calling `remove_voter` once they are done to have
//! their bond back and remove the lock.
//!
//! Voters also report other voters as being defunct to earn their bond. A voter is defunct once all
//! of the candidates that they have voted for are neither a valid candidate anymore nor a member.
//! Upon reporting, if the target voter is actually defunct, the reporter will be rewarded by the
//! voting bond of the target. The target will lose their bond and get removed. If the target is not
//! defunct, the reporter is slashed and removed. To prevent being reported, voters should manually
//! submit a `remove_voter()` as soon as they are in the defunct state.
//!
//! ### Candidacy and Members
//!
//! Candidates also reserve a bond as they submit candidacy. A candidate cannot take their candidacy
//! back. A candidate can end up in one of the below situations:
//!   - **Winner**: A winner is kept as a _member_. They must still have a bond in reserve and they
//!     are automatically counted as a candidate for the next election.
//!   - **Runner-up**: Runners-up are the best candidates immediately after the winners. The number
//!     of runners_up to keep is configurable. Runners-up are used, in order that they are elected,
//!     as replacements when a candidate is kicked by `[remove_member]`, or when an active member
//!     renounces their candidacy. Runners are automatically counted as a candidate for the next
//!     election.
//!   - **Loser**: Any of the candidate who are not a winner are left as losers. A loser might be an
//!     _outgoing member or runner_, meaning that they are an active member who failed to keep their
//!     spot. An outgoing will always lose their bond.
//!
//! ##### Renouncing candidacy.
//!
//! All candidates, elected or not, can renounce their candidacy. A call to [`Module::renounce_candidacy`]
//! will always cause the candidacy bond to be refunded.
//!
//! Note that with the members being the default candidates for the next round and votes persisting
//! in storage, the election system is entirely stable given no further input. This means that if
//! the system has a particular set of candidates `C` and voters `V` that lead to a set of members
//! `M` being elected, as long as `V` and `C` don't remove their candidacy and votes, `M` will keep
//! being re-elected at the end of each round.
//!
//! ### Module Information
//!
//! - [`election_sp_phragmen::Trait`](./trait.Trait.html)
//! - [`Call`](./enum.Call.html)
//! - [`Module`](./struct.Module.html)

#![cfg_attr(not(feature = "std"), no_std)]

use codec::{Encode, Decode};
use sp_std::prelude::*;
use sp_runtime::{
	DispatchError, RuntimeDebug, Perbill,
	traits::{Zero, StaticLookup, Convert},
};
use frame_support::{
	decl_storage, decl_event, ensure, decl_module, decl_error,
	weights::{Weight, constants::{WEIGHT_PER_MICROS, WEIGHT_PER_NANOS}},
	storage::{StorageMap, IterableStorageMap},
	dispatch::{DispatchResultWithPostInfo, WithPostDispatchInfo},
	traits::{
		Currency, Get, LockableCurrency, LockIdentifier, ReservableCurrency, WithdrawReasons,
		ChangeMembers, OnUnbalanced, WithdrawReason, Contains, BalanceStatus, InitializeMembers,
		ContainsLengthBound,
	}
};
use sp_phragmen::{build_support_map, ExtendedBalance, VoteWeight, PhragmenResult};
use frame_system::{self as system, ensure_signed, ensure_root};

mod benchmarking;

/// The maximum votes allowed per voter.
pub const MAXIMUM_VOTE: usize = 16;

type BalanceOf<T> =
	<<T as Trait>::Currency as Currency<<T as frame_system::Trait>::AccountId>>::Balance;
type NegativeImbalanceOf<T> =
	<<T as Trait>::Currency as Currency<<T as frame_system::Trait>::AccountId>>::NegativeImbalance;

/// An indication that the renouncing account currently has which of the below roles.
#[derive(Encode, Decode, Clone, PartialEq, RuntimeDebug)]
pub enum Renouncing {
	/// A member is renouncing.
	Member,
	/// A runner-up is renouncing.
	RunnerUp,
	/// A candidate is renouncing, while the given total number of candidates exists.
	Candidate(#[codec(compact)] u32),
}

/// Information needed to prove the defunct-ness of a voter.
#[derive(Encode, Decode, Clone, PartialEq, RuntimeDebug)]
pub struct DefunctVoter<AccountId> {
	/// the voter's who's being challenged for being defunct
	pub who: AccountId,
	/// The number of votes that `who` has placed.
	#[codec(compact)]
	pub vote_count: u32,
	/// The number of current active candidates.
	#[codec(compact)]
	pub candidate_count: u32
}

pub trait Trait: frame_system::Trait {
	/// The overarching event type.c
	type Event: From<Event<Self>> + Into<<Self as frame_system::Trait>::Event>;

	/// Identifier for the elections-phragmen pallet's lock
	type ModuleId: Get<LockIdentifier>;

	/// The currency that people are electing with.
	type Currency:
		LockableCurrency<Self::AccountId, Moment=Self::BlockNumber> +
		ReservableCurrency<Self::AccountId>;

	/// What to do when the members change.
	type ChangeMembers: ChangeMembers<Self::AccountId>;

	/// What to do with genesis members
	type InitializeMembers: InitializeMembers<Self::AccountId>;

	/// Convert a balance into a number used for election calculation.
	/// This must fit into a `u64` but is allowed to be sensibly lossy.
	type CurrencyToVote: Convert<BalanceOf<Self>, VoteWeight> + Convert<ExtendedBalance, BalanceOf<Self>>;

	/// How much should be locked up in order to submit one's candidacy.
	type CandidacyBond: Get<BalanceOf<Self>>;

	/// How much should be locked up in order to be able to submit votes.
	type VotingBond: Get<BalanceOf<Self>>;

	/// Handler for the unbalanced reduction when a candidate has lost (and is not a runner-up)
	type LoserCandidate: OnUnbalanced<NegativeImbalanceOf<Self>>;

	/// Handler for the unbalanced reduction when a reporter has submitted a bad defunct report.
	type BadReport: OnUnbalanced<NegativeImbalanceOf<Self>>;

	/// Handler for the unbalanced reduction when a member has been kicked.
	type KickedMember: OnUnbalanced<NegativeImbalanceOf<Self>>;

	/// Number of members to elect.
	type DesiredMembers: Get<u32>;

	/// Number of runners_up to keep.
	type DesiredRunnersUp: Get<u32>;

	/// How long each seat is kept. This defines the next block number at which an election
	/// round will happen. If set to zero, no elections are ever triggered and the module will
	/// be in passive mode.
	type TermDuration: Get<Self::BlockNumber>;
}

decl_storage! {
	trait Store for Module<T: Trait> as PhragmenElection {
		// ---- State
		/// The current elected membership. Sorted based on account id.
		pub Members get(fn members): Vec<(T::AccountId, BalanceOf<T>)>;
		/// The current runners_up. Sorted based on low to high merit (worse to best runner).
		pub RunnersUp get(fn runners_up): Vec<(T::AccountId, BalanceOf<T>)>;
		/// The total number of vote rounds that have happened, excluding the upcoming one.
		pub ElectionRounds get(fn election_rounds): u32 = Zero::zero();

		/// Votes and locked stake of a particular voter.
		///
		/// TWOX-NOTE: SAFE as `AccountId` is a crypto hash
		pub Voting get(fn voting): map hasher(twox_64_concat) T::AccountId => (BalanceOf<T>, Vec<T::AccountId>);

		/// The present candidate list. Sorted based on account-id. A current member or runner-up
		/// can never enter this vector and is always implicitly assumed to be a candidate.
		pub Candidates get(fn candidates): Vec<T::AccountId>;
	} add_extra_genesis {
		config(members): Vec<(T::AccountId, BalanceOf<T>)>;
		build(|config: &GenesisConfig<T>| {
			let members = config.members.iter().map(|(ref member, ref stake)| {
				// make sure they have enough stake
				assert!(
					T::Currency::free_balance(member) >= *stake,
					"Genesis member does not have enough stake",
				);

				// reserve candidacy bond and set as members.
				T::Currency::reserve(&member, T::CandidacyBond::get())
					.expect("Genesis member does not have enough balance to be a candidate");

				// Note: all members will only vote for themselves, hence they must be given exactly
				// their own stake as total backing. Any sane election should behave as such.
				// Nonetheless, stakes will be updated for term 1 onwards according to the election.
				Members::<T>::mutate(|members| {
					match members.binary_search_by(|(a, _b)| a.cmp(member)) {
						Ok(_) => panic!("Duplicate member in elections phragmen genesis: {}", member),
						Err(pos) => members.insert(pos, (member.clone(), *stake)),
					}
				});

				// set self-votes to make persistent.
				<Module<T>>::vote(
					T::Origin::from(Some(member.clone()).into()),
					vec![member.clone()],
					*stake,
				).expect("Genesis member could not vote.");

				member.clone()
			}).collect::<Vec<T::AccountId>>();

			// report genesis members to upstream, if any.
			T::InitializeMembers::initialize_members(&members);
		})
	}
}

decl_error! {
	/// Error for the elections-phragmen module.
	pub enum Error for Module<T: Trait> {
		/// Cannot vote when no candidates or members exist.
		UnableToVote,
		/// Must vote for at least one candidate.
		NoVotes,
		/// Cannot vote more than candidates.
		TooManyVotes,
		/// Cannot vote more than maximum allowed.
		MaximumVotesExceeded,
		/// Cannot vote with stake less than minimum balance.
		LowBalance,
		/// Voter can not pay voting bond.
		UnableToPayBond,
		/// Must be a voter.
		MustBeVoter,
		/// Cannot report self.
		ReportSelf,
		/// Duplicated candidate submission.
		DuplicatedCandidate,
		/// Member cannot re-submit candidacy.
		MemberSubmit,
		/// Runner cannot re-submit candidacy.
		RunnerSubmit,
		/// Candidate does not have enough funds.
		InsufficientCandidateFunds,
		/// Not a member.
		NotMember,
		/// The provided count of number of candidates is incorrect.
		InvalidCandidateCount,
		/// The provided count of number of votes is incorrect.
		InvalidVoteCount,
		/// The renouncing origin presented a wrong `Renouncing` parameter.
		InvalidRenouncing,
		/// Prediction regarding replacement after member removal is wrong.
		InvalidReplacement,
	}
}

decl_module! {
	pub struct Module<T: Trait> for enum Call where origin: T::Origin {
		type Error = Error<T>;

		fn deposit_event() = default;

		const CandidacyBond: BalanceOf<T> = T::CandidacyBond::get();
		const VotingBond: BalanceOf<T> = T::VotingBond::get();
		const DesiredMembers: u32 = T::DesiredMembers::get();
		const DesiredRunnersUp: u32 = T::DesiredRunnersUp::get();
		const TermDuration: T::BlockNumber = T::TermDuration::get();
		const ModuleId: LockIdentifier  = T::ModuleId::get();

		/// Vote for a set of candidates for the upcoming round of election. This can be called to
		/// set the initial votes, or update already existing votes.
		///
		/// Upon initial voting, `value` units of `who`'s balance is locked and a bond amount is
		/// reserved.
		///
		/// The `votes` should:
		///   - not be empty.
		///   - be less than the number of possible candidates. Note that all current members and
		///     runners-up are also automatically candidates for the next round.
		///
		/// It is the responsibility of the caller to not place all of their balance into the lock
		/// and keep some for further transactions.
		///
		/// # <weight>
		/// Base weight: 47.93 µs
		/// State reads:
		/// 	- Candidates.len() + Members.len() + RunnersUp.len()
		/// 	- Voting (is_voter)
		/// 	- [AccountBalance(who) (unreserve + total_balance)]
		/// State writes:
		/// 	- Voting
		/// 	- Lock
		/// 	- [AccountBalance(who) (unreserve -- only when creating a new voter)]
		/// # </weight>
		#[weight = 50 * WEIGHT_PER_MICROS + T::DbWeight::get().reads_writes(4, 2)]
		fn vote(
			origin,
			votes: Vec<T::AccountId>,
			#[compact] value: BalanceOf<T>,
		) {
			let who = ensure_signed(origin)?;

			ensure!(votes.len() <= MAXIMUM_VOTE, Error::<T>::MaximumVotesExceeded);
			ensure!(!votes.is_empty(), Error::<T>::NoVotes);

			let candidates_count = <Candidates<T>>::decode_len().unwrap_or(0);
			let members_count = <Members<T>>::decode_len().unwrap_or(0);
			let runners_up_count = <RunnersUp<T>>::decode_len().unwrap_or(0);

			// addition is valid: candidates, members and runners-up will never overlap.
			let allowed_votes = candidates_count + members_count + runners_up_count;

			ensure!(!allowed_votes.is_zero(), Error::<T>::UnableToVote);
			ensure!(votes.len() <= allowed_votes, Error::<T>::TooManyVotes);

			ensure!(value > T::Currency::minimum_balance(), Error::<T>::LowBalance);

			// first time voter. Reserve bond.
			if !Self::is_voter(&who) {
				T::Currency::reserve(&who, T::VotingBond::get())
					.map_err(|_| Error::<T>::UnableToPayBond)?;
			}

			// Amount to be locked up.
			let locked_balance = value.min(T::Currency::total_balance(&who));

			// lock
			T::Currency::set_lock(
				T::ModuleId::get(),
				&who,
				locked_balance,
				WithdrawReasons::except(WithdrawReason::TransactionPayment),
			);

			Voting::<T>::insert(&who, (locked_balance, votes));
		}

		/// Remove `origin` as a voter. This removes the lock and returns the bond.
		///
		/// # <weight>
		/// Base weight: 36.8 µs
		/// All state access is from do_remove_voter.
		/// State reads:
		/// 	- Voting
		/// 	- [AccountData(who)]
		/// State writes:
		/// 	- Voting
		/// 	- Locks
		/// 	- [AccountData(who)]
		/// # </weight>
		#[weight = 35 * WEIGHT_PER_MICROS + T::DbWeight::get().reads_writes(1, 2)]
		fn remove_voter(origin) {
			let who = ensure_signed(origin)?;
			ensure!(Self::is_voter(&who), Error::<T>::MustBeVoter);

			Self::do_remove_voter(&who, true);
		}

		/// Report `target` for being an defunct voter. In case of a valid report, the reporter is
		/// rewarded by the bond amount of `target`. Otherwise, the reporter itself is removed and
		/// their bond is slashed.
		///
		/// A defunct voter is defined to be:
		///   - a voter whose current submitted votes are all invalid. i.e. all of them are no
		///     longer a candidate nor an active member or a runner-up.
		///
		///
		/// The origin must provide the number of current candidates and votes of the reported target
		/// for the purpose of accurate weight calculation.
		///
		/// # <weight>
		/// No Base weight based on min square analysis.
		/// Complexity of candidate_count: 1.755 µs
		/// Complexity of vote_count: 18.51 µs
		/// State reads:
		///  	- Voting(reporter)
		///  	- Candidate.len()
		///  	- Voting(Target)
		///  	- Candidates, Members, RunnersUp (is_defunct_voter)
		/// State writes:
		/// 	- Lock(reporter || target)
		/// 	- [AccountBalance(reporter)] + AccountBalance(target)
		/// 	- Voting(reporter || target)
		/// Note: the db access is worse with respect to db, which is when the report is correct.
		/// # </weight>
		#[weight =
			Weight::from(defunct.candidate_count).saturating_mul(2 * WEIGHT_PER_MICROS)
			.saturating_add(Weight::from(defunct.vote_count).saturating_mul(19 * WEIGHT_PER_MICROS))
			.saturating_add(T::DbWeight::get().reads_writes(6, 3))
		]
		fn report_defunct_voter(
			origin,
			defunct: DefunctVoter<<T::Lookup as StaticLookup>::Source>,
		) {
			let reporter = ensure_signed(origin)?;
			let target = T::Lookup::lookup(defunct.who)?;

			ensure!(reporter != target, Error::<T>::ReportSelf);
			ensure!(Self::is_voter(&reporter), Error::<T>::MustBeVoter);

			let DefunctVoter { candidate_count, vote_count, .. }  = defunct;

			ensure!(
				<Candidates<T>>::decode_len().unwrap_or(0) as u32 <= candidate_count,
				Error::<T>::InvalidCandidateCount,
			);

			let (_, votes) = <Voting<T>>::get(&target);
			// indirect way to ensure target is a voter. We could call into `::contains()`, but it
			// would have the same effect with one extra db access. Note that votes cannot be
			// submitted with length 0. Hence, a non-zero length means that the target is a voter.
			ensure!(votes.len() > 0, Error::<T>::MustBeVoter);

			// ensure that the size of votes that need to be searched is correct.
			ensure!(
				votes.len() as u32 <= vote_count,
				Error::<T>::InvalidVoteCount,
			);

			let valid = Self::is_defunct_voter(&votes);
			if valid {
				// reporter will get the voting bond of the target
				T::Currency::repatriate_reserved(&target, &reporter, T::VotingBond::get(), BalanceStatus::Free)?;
				// remove the target. They are defunct.
				Self::do_remove_voter(&target, false);
			} else {
				// slash the bond of the reporter.
				let imbalance = T::Currency::slash_reserved(&reporter, T::VotingBond::get()).0;
				T::BadReport::on_unbalanced(imbalance);
				// remove the reporter.
				Self::do_remove_voter(&reporter, false);
			}
			Self::deposit_event(RawEvent::VoterReported(target, reporter, valid));
		}

		/// Submit oneself for candidacy.
		///
		/// A candidate will either:
		///   - Lose at the end of the term and forfeit their deposit.
		///   - Win and become a member. Members will eventually get their stash back.
		///   - Become a runner-up. Runners-ups are reserved members in case one gets forcefully
		///     removed.
		///
		/// # <weight>
		/// Base weight = 33.33 µs
		/// Complexity of candidate_count: 0.375 µs
		/// State reads:
		/// 	- Candidates.len()
		/// 	- Candidates
		/// 	- Members
		/// 	- RunnersUp
		/// 	- [AccountBalance(who)]
		/// State writes:
		/// 	- [AccountBalance(who)]
		/// 	- Candidates
		/// # </weight>
		#[weight =
			(35 * WEIGHT_PER_MICROS)
			.saturating_add(Weight::from(*candidate_count).saturating_mul(375 * WEIGHT_PER_NANOS))
			.saturating_add(T::DbWeight::get().reads_writes(4, 1))
		]
		fn submit_candidacy(origin, #[compact] candidate_count: u32) {
			let who = ensure_signed(origin)?;

			let actual_count = <Candidates<T>>::decode_len().unwrap_or(0);
			ensure!(
				actual_count as u32 <= candidate_count,
				Error::<T>::InvalidCandidateCount,
			);

			let is_candidate = Self::is_candidate(&who);
			ensure!(is_candidate.is_err(), Error::<T>::DuplicatedCandidate);

			// assured to be an error, error always contains the index.
			let index = is_candidate.unwrap_err();

			ensure!(!Self::is_member(&who), Error::<T>::MemberSubmit);
			ensure!(!Self::is_runner_up(&who), Error::<T>::RunnerSubmit);

			T::Currency::reserve(&who, T::CandidacyBond::get())
				.map_err(|_| Error::<T>::InsufficientCandidateFunds)?;

			<Candidates<T>>::mutate(|c| c.insert(index, who));
		}

		/// Renounce one's intention to be a candidate for the next election round. 3 potential
		/// outcomes exist:
		/// - `origin` is a candidate and not elected in any set. In this case, the bond is
		///   unreserved, returned and origin is removed as a candidate.
		/// - `origin` is a current runner-up. In this case, the bond is unreserved, returned and
		///   origin is removed as a runner-up.
		/// - `origin` is a current member. In this case, the bond is unreserved and origin is
		///   removed as a member, consequently not being a candidate for the next round anymore.
		///   Similar to [`remove_voter`], if replacement runners exists, they are immediately used.
		/// <weight>
		/// If a candidate is renouncing:
		/// 	Base weight: 17.28 µs
		/// 	Complexity of candidate_count: 0.235 µs
		/// 	State reads:
		/// 		- Candidates
		/// 		- [AccountBalance(who) (unreserve)]
		/// 	State writes:
		/// 		- Candidates
		/// 		- [AccountBalance(who) (unreserve)]
		/// If member is renouncing:
		/// 	Base weight: 46.25 µs
		/// 	State reads:
		/// 		- Members, RunnersUp (remove_and_replace_member),
		/// 		- [AccountData(who) (unreserve)]
		/// 	State writes:
		/// 		- Members, RunnersUp (remove_and_replace_member),
		/// 		- [AccountData(who) (unreserve)]
		/// If runner is renouncing:
		/// 	Base weight: 46.25 µs
		/// 	State reads:
		/// 		- RunnersUp (remove_and_replace_member),
		/// 		- [AccountData(who) (unreserve)]
		/// 	State writes:
		/// 		- RunnersUp (remove_and_replace_member),
		/// 		- [AccountData(who) (unreserve)]
		///
		/// Weight note: The call into changeMembers need to be accounted for.
		/// </weight>
		#[weight =  match *renouncing {
			Renouncing::Candidate(count) => {
				(18 * WEIGHT_PER_MICROS)
				.saturating_add(Weight::from(count).saturating_mul(235 * WEIGHT_PER_NANOS))
				.saturating_add(T::DbWeight::get().reads_writes(1, 1))
			},
			Renouncing::Member => {
				46 * WEIGHT_PER_MICROS +
				T::DbWeight::get().reads_writes(2, 2)
			},
			Renouncing::RunnerUp => {
				46 * WEIGHT_PER_MICROS +
				T::DbWeight::get().reads_writes(1, 1)
			}
		}]
		fn renounce_candidacy(origin, renouncing: Renouncing) {
			let who = ensure_signed(origin)?;
			match renouncing {
				Renouncing::Member => {
					// returns NoMember error in case of error.
					let _ = Self::remove_and_replace_member(&who)?;
					T::Currency::unreserve(&who, T::CandidacyBond::get());
					Self::deposit_event(RawEvent::MemberRenounced(who.clone()));
				},
				Renouncing::RunnerUp => {
					let mut runners_up_with_stake = Self::runners_up();
					if let Some(index) = runners_up_with_stake
						.iter()
						.position(|(ref r, ref _s)| r == &who)
					{
						runners_up_with_stake.remove(index);
						// unreserve the bond
						T::Currency::unreserve(&who, T::CandidacyBond::get());
						// update storage.
						<RunnersUp<T>>::put(runners_up_with_stake);
					} else {
						Err(Error::<T>::InvalidRenouncing)?;
					}
				}
				Renouncing::Candidate(count) => {
					let mut candidates = Self::candidates();
					ensure!(count >= candidates.len() as u32, Error::<T>::InvalidRenouncing);
					if let Some(index) = candidates.iter().position(|x| *x == who) {
						candidates.remove(index);
						// unreserve the bond
						T::Currency::unreserve(&who, T::CandidacyBond::get());
						// update storage.
						<Candidates<T>>::put(candidates);
					} else {
						Err(Error::<T>::InvalidRenouncing)?;
					}
				}
			};
		}

		/// Remove a particular member from the set. This is effective immediately and the bond of
		/// the outgoing member is slashed.
		///
		/// If a runner-up is available, then the best runner-up will be removed and replaces the
		/// outgoing member. Otherwise, a new phragmen round is started.
		///
		/// Note that this does not affect the designated block number of the next election.
		///
		/// # <weight>
		/// If we have a replacement:
		/// 	- Base weight: 50.93 µs
		/// 	- State reads:
		/// 		- RunnersUp.len()
		/// 		- Members, RunnersUp (remove_and_replace_member)
		/// 	- State writes:
		/// 		- Members, RunnersUp (remove_and_replace_member)
		/// Else, since this is a root call and will go into phragmen, we assume full block for now.
		/// # </weight>
		#[weight = if *has_replacement {
			50 * WEIGHT_PER_MICROS + T::DbWeight::get().reads_writes(3, 2)
		} else {
			T::MaximumBlockWeight::get()
		}]
		fn remove_member(
			origin,
			who: <T::Lookup as StaticLookup>::Source,
			has_replacement: bool,
		) -> DispatchResultWithPostInfo {
			ensure_root(origin)?;
			let who = T::Lookup::lookup(who)?;

			let will_have_replacement = <RunnersUp<T>>::decode_len().unwrap_or(0) > 0;
			if will_have_replacement != has_replacement {
				// In both cases, we will change more weight than neede. Refund and abort.
				return Err(Error::<T>::InvalidReplacement.with_weight(
					// refund. The weight value comes from a benchmark which is special to this.
					//  5.751 µs
					6 * WEIGHT_PER_MICROS + T::DbWeight::get().reads_writes(1, 0)
				));
			} // else, prediction was correct.

			Self::remove_and_replace_member(&who).map(|had_replacement| {
				let (imbalance, _) = T::Currency::slash_reserved(&who, T::CandidacyBond::get());
				T::KickedMember::on_unbalanced(imbalance);
				Self::deposit_event(RawEvent::MemberKicked(who.clone()));

				if !had_replacement {
					// if we end up here, we will charge a full block weight.
					Self::do_phragmen();
				}

				// no refund needed.
				None.into()
			}).map_err(|e| e.into())
		}

		/// What to do at the end of each block. Checks if an election needs to happen or not.
		fn on_initialize(n: T::BlockNumber) -> Weight {
			// returns the correct weight.
			Self::end_block(n)
		}
	}
}

decl_event!(
	pub enum Event<T> where
		Balance = BalanceOf<T>,
		<T as frame_system::Trait>::AccountId,
	{
		/// A new term with new members. This indicates that enough candidates existed to run the
		/// election, not that enough have has been elected. The inner value must be examined for
		/// this purpose. A `NewTerm([])` indicates that some candidates got their bond slashed and
		/// none were elected, whilst `EmptyTerm` means that no candidates existed to begin with.
		NewTerm(Vec<(AccountId, Balance)>),
		/// No (or not enough) candidates existed for this round. This is different from
		/// `NewTerm([])`. See the description of `NewTerm`.
		EmptyTerm,
		/// A member has been removed. This should always be followed by either `NewTerm` ot
		/// `EmptyTerm`.
		MemberKicked(AccountId),
		/// A member has renounced their candidacy.
		MemberRenounced(AccountId),
		/// A voter (first element) was reported (byt the second element) with the the report being
		/// successful or not (third element).
		VoterReported(AccountId, AccountId, bool),
	}
);

impl<T: Trait> Module<T> {
	/// Attempts to remove a member `who`. If a runner-up exists, it is used as the replacement and
	/// Ok(true). is returned.
	///
	/// Otherwise, `Ok(false)` is returned to signal the caller.
	///
	/// If a replacement exists, `Members` and `RunnersUp` storage is updated, where the first
	/// element of `RunnersUp` is used as the replacement and `Ok(true)` is returned. Else,
	/// `Ok(false)` is returned with no storage updated.
	///
	/// Note that this function _will_ call into `T::ChangeMembers` in case any change happens
	/// (`Ok(true)`).
	///
	/// If replacement exists, this will read and write from/into both `Members` and `RunnersUp`.
	fn remove_and_replace_member(who: &T::AccountId) -> Result<bool, DispatchError> {
		let mut members_with_stake = Self::members();
		if let Ok(index) = members_with_stake.binary_search_by(|(ref m, ref _s)| m.cmp(who)) {
			members_with_stake.remove(index);

			let next_up = <RunnersUp<T>>::mutate(|runners_up| runners_up.pop());
			let maybe_replacement = next_up.and_then(|(replacement, stake)|
				members_with_stake.binary_search_by(|(ref m, ref _s)| m.cmp(&replacement))
					.err()
					.map(|index| {
						members_with_stake.insert(index, (replacement.clone(), stake));
						replacement
					})
			);

			<Members<T>>::put(&members_with_stake);
			let members = members_with_stake.into_iter().map(|m| m.0).collect::<Vec<_>>();
			let result = Ok(maybe_replacement.is_some());
			let old = [who.clone()];
			match maybe_replacement {
				Some(new) => T::ChangeMembers::change_members_sorted(&[new], &old, &members),
				None => T::ChangeMembers::change_members_sorted(&[], &old, &members),
			}
			result
		} else {
			Err(Error::<T>::NotMember)?
		}
	}

	/// Check if `who` is a candidate. It returns the insert index if the element does not exists as
	/// an error.
	///
	/// O(LogN) given N candidates.
	fn is_candidate(who: &T::AccountId) -> Result<(), usize> {
		Self::candidates().binary_search(who).map(|_| ())
	}

	/// Check if `who` is a voter. It may or may not be a _current_ one.
	///
	/// State: O(1).
	fn is_voter(who: &T::AccountId) -> bool {
		Voting::<T>::contains_key(who)
	}

	/// Check if `who` is currently an active member.
	///
	/// O(LogN) given N members. Since members are limited, O(1).
	fn is_member(who: &T::AccountId) -> bool {
		Self::members().binary_search_by(|(a, _b)| a.cmp(who)).is_ok()
	}

	/// Check if `who` is currently an active runner-up.
	///
	/// O(LogN) given N runners-up. Since runners-up are limited, O(1).
	fn is_runner_up(who: &T::AccountId) -> bool {
		Self::runners_up().iter().position(|(a, _b)| a == who).is_some()
	}

	/// Returns number of desired members.
	fn desired_members() -> u32 {
		T::DesiredMembers::get()
	}

	/// Returns number of desired runners up.
	fn desired_runners_up() -> u32 {
		T::DesiredRunnersUp::get()
	}

	/// Returns the term duration
	fn term_duration() -> T::BlockNumber {
		T::TermDuration::get()
	}

	/// Get the members' account ids.
	fn members_ids() -> Vec<T::AccountId> {
		Self::members().into_iter().map(|(m, _)| m).collect::<Vec<T::AccountId>>()
	}

	/// The the runners' up account ids.
	fn runners_up_ids() -> Vec<T::AccountId> {
		Self::runners_up().into_iter().map(|(r, _)| r).collect::<Vec<T::AccountId>>()
	}

	/// Check if `votes` will correspond to a defunct voter. As no origin is part of the inputs,
	/// this function does not check the origin at all.
	///
	/// O(NLogM) with M candidates and `who` having voted for `N` of them.
	/// Reads Members, RunnersUp, Candidates and Voting(who) from database.
	fn is_defunct_voter(votes: &[T::AccountId]) -> bool {
		votes.iter().all(|v|
			!Self::is_member(v) && !Self::is_runner_up(v) && !Self::is_candidate(v).is_ok()
		)
	}

	/// Remove a certain someone as a voter.
	///
	/// This will clean always clean the storage associated with the voter, and remove the balance
	/// lock. Optionally, it would also return the reserved voting bond if indicated by `unreserve`.
	/// If unreserve is true, has 3 storage reads and 1 reads.
	///
	/// DB access: Voting and Lock are always written to, if unreserve, then 1 read and write added.
	fn do_remove_voter(who: &T::AccountId, unreserve: bool) {
		// remove storage and lock.
		Voting::<T>::remove(who);
		T::Currency::remove_lock(T::ModuleId::get(), who);

		if unreserve {
			T::Currency::unreserve(who, T::VotingBond::get());
		}
	}

	/// The locked stake of a voter.
	fn locked_stake_of(who: &T::AccountId) -> BalanceOf<T> {
		Voting::<T>::get(who).0
	}

	/// Check there's nothing to do this block.
	///
	/// Runs phragmen election and cleans all the previous candidate state. The voter state is NOT
	/// cleaned and voters must themselves submit a transaction to retract.
	fn end_block(block_number: T::BlockNumber) -> Weight {
		if !Self::term_duration().is_zero() {
			if (block_number % Self::term_duration()).is_zero() {
				Self::do_phragmen();
				return T::MaximumBlockWeight::get()
			}
		}
		0
	}

	/// Run the phragmen election with all required side processes and state updates.
	///
	/// Calls the appropriate `ChangeMembers` function variant internally.
	///
	/// # <weight>
	/// #### State
	/// Reads: O(C + V*E) where C = candidates, V voters and E votes per voter exits.
	/// Writes: O(M + R) with M desired members and R runners_up.
	/// # </weight>
	fn do_phragmen() {
		let desired_seats = Self::desired_members() as usize;
		let desired_runners_up = Self::desired_runners_up() as usize;
		let num_to_elect = desired_runners_up + desired_seats;

		let mut candidates = Self::candidates();
		// candidates who explicitly called `submit_candidacy`. Only these folks are at risk of
		// losing their bond.
		let exposed_candidates = candidates.clone();
		// current members are always a candidate for the next round as well.
		// this is guaranteed to not create any duplicates.
		candidates.append(&mut Self::members_ids());
		// previous runners_up are also always candidates for the next round.
		candidates.append(&mut Self::runners_up_ids());

		// helper closures to deal with balance/stake.
		let to_votes = |b: BalanceOf<T>| -> VoteWeight {
			<T::CurrencyToVote as Convert<BalanceOf<T>, VoteWeight>>::convert(b)
		};
		let to_balance = |e: ExtendedBalance| -> BalanceOf<T> {
			<T::CurrencyToVote as Convert<ExtendedBalance, BalanceOf<T>>>::convert(e)
		};
		let stake_of = |who: &T::AccountId| -> VoteWeight {
			to_votes(Self::locked_stake_of(who))
		};

		let voters_and_votes = Voting::<T>::iter()
			.map(|(voter, (stake, targets))| { (voter, to_votes(stake), targets) })
			.collect::<Vec<_>>();
		let maybe_phragmen_result = sp_phragmen::elect::<T::AccountId, Perbill>(
			num_to_elect,
			0,
			candidates,
			voters_and_votes.clone(),
		);

		if let Some(PhragmenResult { winners, assignments }) = maybe_phragmen_result {
			let old_members_ids = <Members<T>>::take().into_iter()
				.map(|(m, _)| m)
				.collect::<Vec<T::AccountId>>();
			let old_runners_up_ids = <RunnersUp<T>>::take().into_iter()
				.map(|(r, _)| r)
				.collect::<Vec<T::AccountId>>();

			// filter out those who had literally no votes at all.
			// NOTE: the need to do this is because all candidates, even those who have no
			// vote are still considered by phragmen and when good candidates are scarce, then these
			// cheap ones might get elected. We might actually want to remove the filter and allow
			// zero-voted candidates to also make it to the membership set.
			let new_set_with_approval = winners;
			let new_set = new_set_with_approval
				.into_iter()
				.filter_map(|(m, a)| if a.is_zero() { None } else { Some(m) } )
				.collect::<Vec<T::AccountId>>();

			// OPTIMISATION NOTE: we could bail out here if `new_set.len() == 0`. There isn't much
			// left to do. Yet, re-arranging the code would require duplicating the slashing of
			// exposed candidates, cleaning any previous members, and so on. For now, in favour of
			// readability and veracity, we keep it simple.

			let staked_assignments = sp_phragmen::assignment_ratio_to_staked(
				assignments,
				stake_of,
			);

			let (support_map, _) = build_support_map::<T::AccountId>(&new_set, &staked_assignments);

			let new_set_with_stake = new_set
				.into_iter()
				.map(|ref m| {
					let support = support_map.get(m)
						.expect(
							"entire new_set was given to build_support_map; en entry must be \
							created for each item; qed"
						);
					(m.clone(), to_balance(support.total))
				})
				.collect::<Vec<(T::AccountId, BalanceOf<T>)>>();

			// split new set into winners and runners up.
			let split_point = desired_seats.min(new_set_with_stake.len());
			let mut new_members = (&new_set_with_stake[..split_point]).to_vec();

			// save the runners up as-is. They are sorted based on desirability.
			// save the members, sorted based on account id.
			new_members.sort_by(|i, j| i.0.cmp(&j.0));

			let mut prime_votes: Vec<_> = new_members.iter().map(|c| (&c.0, VoteWeight::zero())).collect();
			for (_, stake, targets) in voters_and_votes.into_iter() {
				for (votes, who) in targets.iter()
					.enumerate()
					.map(|(votes, who)| ((MAXIMUM_VOTE - votes) as u32, who))
				{
					if let Ok(i) = prime_votes.binary_search_by_key(&who, |k| k.0) {
						prime_votes[i].1 += stake * votes as VoteWeight;
					}
				}
			}
			let prime = prime_votes.into_iter().max_by_key(|x| x.1).map(|x| x.0.clone());

			// new_members_ids is sorted by account id.
			let new_members_ids = new_members
				.iter()
				.map(|(m, _)| m.clone())
				.collect::<Vec<T::AccountId>>();

			let new_runners_up = &new_set_with_stake[split_point..]
				.into_iter()
				.cloned()
				.rev()
				.collect::<Vec<(T::AccountId, BalanceOf<T>)>>();
			// new_runners_up remains sorted by desirability.
			let new_runners_up_ids = new_runners_up
				.iter()
				.map(|(r, _)| r.clone())
				.collect::<Vec<T::AccountId>>();

			// report member changes. We compute diff because we need the outgoing list.
			let (incoming, outgoing) = T::ChangeMembers::compute_members_diff(
				&new_members_ids,
				&old_members_ids,
			);
			T::ChangeMembers::change_members_sorted(
				&incoming,
				&outgoing.clone(),
				&new_members_ids,
			);
			T::ChangeMembers::set_prime(prime);

			// outgoing candidates lose their bond.
			let mut to_burn_bond = outgoing.to_vec();

			// compute the outgoing of runners up as well and append them to the `to_burn_bond`
			{
				let (_, outgoing) = T::ChangeMembers::compute_members_diff(
					&new_runners_up_ids,
					&old_runners_up_ids,
				);
				to_burn_bond.extend(outgoing);
			}

			// Burn loser bond. members list is sorted. O(NLogM) (N candidates, M members)
			// runner up list is not sorted. O(K*N) given K runner ups. Overall: O(NLogM + N*K)
			// both the member and runner counts are bounded.
			exposed_candidates.into_iter().for_each(|c| {
				// any candidate who is not a member and not a runner up.
				if new_members.binary_search_by_key(&c, |(m, _)| m.clone()).is_err()
					&& !new_runners_up_ids.contains(&c)
				{
					let (imbalance, _) = T::Currency::slash_reserved(&c, T::CandidacyBond::get());
					T::LoserCandidate::on_unbalanced(imbalance);