referrerpolicy=no-referrer-when-downgrade

pallet_referenda/
types.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//! Miscellaneous additional datatypes.
19
20use super::*;
21use alloc::borrow::Cow;
22use codec::{Compact, Decode, DecodeWithMemTracking, Encode, EncodeLike, Input, MaxEncodedLen};
23use core::fmt::Debug;
24use frame_support::{
25	traits::{schedule::v3::Anon, Bounded},
26	Parameter,
27};
28use scale_info::{Type, TypeInfo};
29use sp_arithmetic::{Rounding::*, SignedRounding::*};
30use sp_runtime::{FixedI64, PerThing};
31
32pub type BalanceOf<T, I = ()> =
33	<<T as Config<I>>::Currency as Currency<<T as frame_system::Config>::AccountId>>::Balance;
34
35pub type BlockNumberFor<T, I> =
36	<<T as Config<I>>::BlockNumberProvider as BlockNumberProvider>::BlockNumber;
37
38pub type NegativeImbalanceOf<T, I> = <<T as Config<I>>::Currency as Currency<
39	<T as frame_system::Config>::AccountId,
40>>::NegativeImbalance;
41pub type CallOf<T, I> = <T as Config<I>>::RuntimeCall;
42pub type BoundedCallOf<T, I> =
43	Bounded<<T as Config<I>>::RuntimeCall, <T as frame_system::Config>::Hashing>;
44pub type VotesOf<T, I> = <T as Config<I>>::Votes;
45pub type TallyOf<T, I> = <T as Config<I>>::Tally;
46pub type PalletsOriginOf<T> =
47	<<T as frame_system::Config>::RuntimeOrigin as OriginTrait>::PalletsOrigin;
48pub type ReferendumInfoOf<T, I> = ReferendumInfo<
49	TrackIdOf<T, I>,
50	PalletsOriginOf<T>,
51	BlockNumberFor<T, I>,
52	BoundedCallOf<T, I>,
53	BalanceOf<T, I>,
54	TallyOf<T, I>,
55	<T as frame_system::Config>::AccountId,
56	ScheduleAddressOf<T, I>,
57>;
58pub type ReferendumStatusOf<T, I> = ReferendumStatus<
59	TrackIdOf<T, I>,
60	PalletsOriginOf<T>,
61	BlockNumberFor<T, I>,
62	BoundedCallOf<T, I>,
63	BalanceOf<T, I>,
64	TallyOf<T, I>,
65	<T as frame_system::Config>::AccountId,
66	ScheduleAddressOf<T, I>,
67>;
68pub type DecidingStatusOf<T, I> = DecidingStatus<BlockNumberFor<T, I>>;
69pub type TrackInfoOf<T, I = ()> = TrackInfo<BalanceOf<T, I>, BlockNumberFor<T, I>>;
70pub type TrackIdOf<T, I> =
71	<<T as Config<I>>::Tracks as TracksInfo<BalanceOf<T, I>, BlockNumberFor<T, I>>>::Id;
72pub type ScheduleAddressOf<T, I> = <<T as Config<I>>::Scheduler as Anon<
73	BlockNumberFor<T, I>,
74	CallOf<T, I>,
75	PalletsOriginOf<T>,
76>>::Address;
77
78/// A referendum index.
79pub type ReferendumIndex = u32;
80
81pub trait InsertSorted<T> {
82	/// Inserts an item into a sorted series.
83	///
84	/// Returns `true` if it was inserted, `false` if it would belong beyond the bound of the
85	/// series.
86	fn insert_sorted_by_key<F: FnMut(&T) -> K, K: PartialOrd<K> + Ord>(
87		&mut self,
88		t: T,
89		f: F,
90	) -> bool;
91}
92impl<T: Ord, S: Get<u32>> InsertSorted<T> for BoundedVec<T, S> {
93	fn insert_sorted_by_key<F: FnMut(&T) -> K, K: PartialOrd<K> + Ord>(
94		&mut self,
95		t: T,
96		mut f: F,
97	) -> bool {
98		let index = self.binary_search_by_key::<K, F>(&f(&t), f).unwrap_or_else(|x| x);
99		self.force_insert_keep_right(index, t).is_ok()
100	}
101}
102
103#[derive(
104	Encode, Decode, DecodeWithMemTracking, Clone, PartialEq, Eq, Debug, TypeInfo, MaxEncodedLen,
105)]
106pub struct DecidingStatus<BlockNumber> {
107	/// When this referendum began being "decided". If confirming, then the
108	/// end will actually be delayed until the end of the confirmation period.
109	pub since: BlockNumber,
110	/// If `Some`, then the referendum has entered confirmation stage and will end at
111	/// the block number as long as it doesn't lose its approval in the meantime.
112	pub confirming: Option<BlockNumber>,
113}
114
115#[derive(
116	Encode, Decode, DecodeWithMemTracking, Clone, PartialEq, Eq, Debug, TypeInfo, MaxEncodedLen,
117)]
118pub struct Deposit<AccountId, Balance> {
119	pub who: AccountId,
120	pub amount: Balance,
121}
122
123pub const DEFAULT_MAX_TRACK_NAME_LEN: usize = 25;
124
125/// Helper structure to treat a `[u8; N]` array as a string.
126///
127/// This is a temporary fix (see [#7671](https://github.com/paritytech/polkadot-sdk/pull/7671)) in
128/// order to stop `polkadot.js` apps to fail when trying to decode the `name` field in `TrackInfo`.
129#[derive(Clone, Eq, DecodeWithMemTracking, PartialEq, Debug)]
130pub struct StringLike<const N: usize>(pub [u8; N]);
131
132impl<const N: usize> TypeInfo for StringLike<N> {
133	type Identity = <&'static str as TypeInfo>::Identity;
134
135	fn type_info() -> Type {
136		<&str as TypeInfo>::type_info()
137	}
138}
139
140impl<const N: usize> MaxEncodedLen for StringLike<N> {
141	fn max_encoded_len() -> usize {
142		<Compact<u32> as MaxEncodedLen>::max_encoded_len().saturating_add(N)
143	}
144}
145
146impl<const N: usize> Encode for StringLike<N> {
147	fn encode(&self) -> Vec<u8> {
148		use codec::Compact;
149		(Compact(N as u32), self.0).encode()
150	}
151}
152
153impl<const N: usize> Decode for StringLike<N> {
154	fn decode<I: Input>(input: &mut I) -> Result<Self, codec::Error> {
155		let Compact(size): Compact<u32> = Decode::decode(input)?;
156		if size != N as u32 {
157			return Err("Invalid size".into());
158		}
159
160		let bytes: [u8; N] = Decode::decode(input)?;
161		Ok(Self(bytes))
162	}
163}
164
165/// Detailed information about the configuration of a referenda track. Used for internal storage.
166pub type TrackInfo<Balance, Moment, const N: usize = DEFAULT_MAX_TRACK_NAME_LEN> =
167	TrackDetails<Balance, Moment, [u8; N]>;
168
169/// Detailed information about the configuration of a referenda track. Used for const querying.
170pub type ConstTrackInfo<Balance, Moment, const N: usize = DEFAULT_MAX_TRACK_NAME_LEN> =
171	TrackDetails<Balance, Moment, StringLike<N>>;
172
173/// Detailed information about the configuration of a referenda track
174#[derive(
175	Clone, Encode, Decode, DecodeWithMemTracking, MaxEncodedLen, TypeInfo, Eq, PartialEq, Debug,
176)]
177pub struct TrackDetails<Balance, Moment, Name> {
178	/// Name of this track.
179	pub name: Name,
180	/// A limit for the number of referenda on this track that can be being decided at once.
181	/// For Root origin this should generally be just one.
182	pub max_deciding: u32,
183	/// Amount that must be placed on deposit before a decision can be made.
184	pub decision_deposit: Balance,
185	/// Amount of time this must be submitted for before a decision can be made.
186	pub prepare_period: Moment,
187	/// Amount of time that a decision may take to be approved prior to cancellation.
188	pub decision_period: Moment,
189	/// Amount of time that the approval criteria must hold before it can be approved.
190	pub confirm_period: Moment,
191	/// Minimum amount of time that an approved proposal must be in the dispatch queue.
192	pub min_enactment_period: Moment,
193	/// Minimum aye votes as percentage of overall conviction-weighted votes needed for
194	/// approval as a function of time into decision period.
195	pub min_approval: Curve,
196	/// Minimum pre-conviction aye-votes ("support") as percentage of overall population that is
197	/// needed for approval as a function of time into decision period.
198	pub min_support: Curve,
199}
200
201/// Track groups the information of a voting track with its corresponding identifier
202#[derive(
203	Clone, Encode, Decode, DecodeWithMemTracking, MaxEncodedLen, TypeInfo, Eq, PartialEq, Debug,
204)]
205pub struct Track<Id, Balance, Moment, const N: usize = DEFAULT_MAX_TRACK_NAME_LEN> {
206	pub id: Id,
207	pub info: TrackInfo<Balance, Moment, N>,
208}
209
210/// Information on the voting tracks.
211pub trait TracksInfo<Balance, Moment, const N: usize = DEFAULT_MAX_TRACK_NAME_LEN>
212where
213	Balance: Clone + Debug + Eq + 'static,
214	Moment: Clone + Debug + Eq + 'static,
215{
216	/// The identifier for a track.
217	type Id: Copy + Parameter + Ord + PartialOrd + Send + Sync + 'static + MaxEncodedLen;
218
219	/// The origin type from which a track is implied.
220	type RuntimeOrigin;
221
222	/// Return the sorted iterable list of known tracks and their information.
223	///
224	/// The iterator MUST be sorted by `Id`. Consumers of this trait are advised to assert
225	/// [`Self::check_integrity`] prior to any use.
226	fn tracks() -> impl Iterator<Item = Cow<'static, Track<Self::Id, Balance, Moment, N>>>;
227
228	/// Determine the voting track for the given `origin`.
229	fn track_for(origin: &Self::RuntimeOrigin) -> Result<Self::Id, ()>;
230
231	/// Return the list of identifiers of the known tracks.
232	fn track_ids() -> impl Iterator<Item = Self::Id> {
233		Self::tracks().map(|x| x.id)
234	}
235
236	/// Return the track info for track `id`, by default this just looks it up in `Self::tracks()`.
237	fn info(id: Self::Id) -> Option<Cow<'static, TrackInfo<Balance, Moment, N>>> {
238		Self::tracks().find(|x| x.id == id).map(|t| match t {
239			Cow::Borrowed(x) => Cow::Borrowed(&x.info),
240			Cow::Owned(x) => Cow::Owned(x.info),
241		})
242	}
243
244	/// Check assumptions about the static data that this trait provides.
245	fn check_integrity() -> Result<(), &'static str> {
246		use core::cmp::Ordering;
247		// Adapted from Iterator::is_sorted implementation available in nightly
248		// https://github.com/rust-lang/rust/issues/53485
249		let mut iter = Self::tracks();
250		let mut last = match iter.next() {
251			Some(ref e) => e.id,
252			None => return Ok(()),
253		};
254		iter.all(|curr| {
255			let curr = curr.as_ref().id;
256			if let Ordering::Greater = last.cmp(&curr) {
257				return false;
258			}
259			last = curr;
260			true
261		})
262		.then_some(())
263		.ok_or("The tracks that were returned by `tracks` were not sorted by `Id`")
264	}
265}
266
267/// Info regarding an ongoing referendum.
268#[derive(
269	Encode, Decode, DecodeWithMemTracking, Clone, PartialEq, Eq, Debug, TypeInfo, MaxEncodedLen,
270)]
271pub struct ReferendumStatus<
272	TrackId: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
273	RuntimeOrigin: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
274	Moment: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone + EncodeLike,
275	Call: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
276	Balance: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
277	Tally: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
278	AccountId: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
279	ScheduleAddress: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
280> {
281	/// The track of this referendum.
282	pub track: TrackId,
283	/// The origin for this referendum.
284	pub origin: RuntimeOrigin,
285	/// The hash of the proposal up for referendum.
286	pub proposal: Call,
287	/// The time the proposal should be scheduled for enactment.
288	pub enactment: DispatchTime<Moment>,
289	/// The time of submission. Once `UndecidingTimeout` passes, it may be closed by anyone if
290	/// `deciding` is `None`.
291	pub submitted: Moment,
292	/// The deposit reserved for the submission of this referendum.
293	pub submission_deposit: Deposit<AccountId, Balance>,
294	/// The deposit reserved for this referendum to be decided.
295	pub decision_deposit: Option<Deposit<AccountId, Balance>>,
296	/// The status of a decision being made. If `None`, it has not entered the deciding period.
297	pub deciding: Option<DecidingStatus<Moment>>,
298	/// The current tally of votes in this referendum.
299	pub tally: Tally,
300	/// Whether we have been placed in the queue for being decided or not.
301	pub in_queue: bool,
302	/// The next scheduled wake-up, if `Some`.
303	pub alarm: Option<(Moment, ScheduleAddress)>,
304}
305
306/// Info regarding a referendum, present or past.
307#[derive(
308	Encode, Decode, DecodeWithMemTracking, Clone, PartialEq, Eq, Debug, TypeInfo, MaxEncodedLen,
309)]
310pub enum ReferendumInfo<
311	TrackId: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
312	RuntimeOrigin: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
313	Moment: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone + EncodeLike,
314	Call: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
315	Balance: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
316	Tally: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
317	AccountId: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
318	ScheduleAddress: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
319> {
320	/// Referendum has been submitted and is being voted on.
321	Ongoing(
322		ReferendumStatus<
323			TrackId,
324			RuntimeOrigin,
325			Moment,
326			Call,
327			Balance,
328			Tally,
329			AccountId,
330			ScheduleAddress,
331		>,
332	),
333	/// Referendum finished with approval. Submission deposit is held.
334	Approved(Moment, Option<Deposit<AccountId, Balance>>, Option<Deposit<AccountId, Balance>>),
335	/// Referendum finished with rejection. Submission deposit is held.
336	Rejected(Moment, Option<Deposit<AccountId, Balance>>, Option<Deposit<AccountId, Balance>>),
337	/// Referendum finished with cancellation. Submission deposit is held.
338	Cancelled(Moment, Option<Deposit<AccountId, Balance>>, Option<Deposit<AccountId, Balance>>),
339	/// Referendum finished and was never decided. Submission deposit is held.
340	TimedOut(Moment, Option<Deposit<AccountId, Balance>>, Option<Deposit<AccountId, Balance>>),
341	/// Referendum finished with a kill.
342	Killed(Moment),
343}
344
345impl<
346		TrackId: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
347		RuntimeOrigin: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
348		Moment: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone + EncodeLike,
349		Call: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
350		Balance: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
351		Tally: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
352		AccountId: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
353		ScheduleAddress: Eq + PartialEq + Debug + Encode + Decode + TypeInfo + Clone,
354	>
355	ReferendumInfo<TrackId, RuntimeOrigin, Moment, Call, Balance, Tally, AccountId, ScheduleAddress>
356{
357	/// Take the Decision Deposit from `self`, if there is one. Returns an `Err` if `self` is not
358	/// in a valid state for the Decision Deposit to be refunded.
359	pub fn take_decision_deposit(&mut self) -> Result<Option<Deposit<AccountId, Balance>>, ()> {
360		use ReferendumInfo::*;
361		match self {
362			Ongoing(x) if x.decision_deposit.is_none() => Ok(None),
363			// Cannot refund deposit if Ongoing as this breaks assumptions.
364			Ongoing(_) => Err(()),
365			Approved(_, _, d) | Rejected(_, _, d) | TimedOut(_, _, d) | Cancelled(_, _, d) => {
366				Ok(d.take())
367			},
368			Killed(_) => Ok(None),
369		}
370	}
371
372	/// Take the Submission Deposit from `self`, if there is one. Returns `None` if the deposit has
373	/// already been taken.
374	///
375	/// The caller is responsible for ensuring the referendum is in a state where the deposit can be
376	/// taken
377	pub fn take_submission_deposit(&mut self) -> Option<Deposit<AccountId, Balance>> {
378		use ReferendumInfo::*;
379		match self {
380			Approved(_, s, _) | Cancelled(_, s, _) | Rejected(_, s, _) | TimedOut(_, s, _) => {
381				s.take()
382			},
383			Ongoing(..) | Killed(..) => None,
384		}
385	}
386}
387
388/// Type for describing a curve over the 2-dimensional space of axes between 0-1, as represented
389/// by `(Perbill, Perbill)`.
390#[derive(Clone, Eq, PartialEq, Encode, Decode, DecodeWithMemTracking, TypeInfo, MaxEncodedLen)]
391#[cfg_attr(not(feature = "std"), derive(Debug))]
392pub enum Curve {
393	/// Linear curve starting at `(0, ceil)`, proceeding linearly to `(length, floor)`, then
394	/// remaining at `floor` until the end of the period.
395	LinearDecreasing { length: Perbill, floor: Perbill, ceil: Perbill },
396	/// Stepped curve, beginning at `(0, begin)`, then remaining constant for `period`, at which
397	/// point it steps down to `(period, begin - step)`. It then remains constant for another
398	/// `period` before stepping down to `(period * 2, begin - step * 2)`. This pattern continues
399	/// but the `y` component has a lower limit of `end`.
400	SteppedDecreasing { begin: Perbill, end: Perbill, step: Perbill, period: Perbill },
401	/// A recipocal (`K/(x+S)-T`) curve: `factor` is `K` and `x_offset` is `S`, `y_offset` is `T`.
402	Reciprocal { factor: FixedI64, x_offset: FixedI64, y_offset: FixedI64 },
403}
404
405/// Calculate the quadratic solution for the given curve.
406///
407/// WARNING: This is a `const` function designed for convenient use at build time and
408/// will panic on overflow. Ensure that any inputs are sensible.
409const fn pos_quad_solution(a: FixedI64, b: FixedI64, c: FixedI64) -> FixedI64 {
410	const TWO: FixedI64 = FixedI64::from_u32(2);
411	const FOUR: FixedI64 = FixedI64::from_u32(4);
412	b.neg().add(b.mul(b).sub(FOUR.mul(a).mul(c)).sqrt()).div(TWO.mul(a))
413}
414
415impl Curve {
416	/// Create a `Curve::Linear` instance from a high-level description.
417	///
418	/// WARNING: This is a `const` function designed for convenient use at build time and
419	/// will panic on overflow. Ensure that any inputs are sensible.
420	pub const fn make_linear(length: u128, period: u128, floor: FixedI64, ceil: FixedI64) -> Curve {
421		let length = FixedI64::from_rational(length, period).into_perbill();
422		let floor = floor.into_perbill();
423		let ceil = ceil.into_perbill();
424		Curve::LinearDecreasing { length, floor, ceil }
425	}
426
427	/// Create a `Curve::Reciprocal` instance from a high-level description.
428	///
429	/// WARNING: This is a `const` function designed for convenient use at build time and
430	/// will panic on overflow. Ensure that any inputs are sensible.
431	pub const fn make_reciprocal(
432		delay: u128,
433		period: u128,
434		level: FixedI64,
435		floor: FixedI64,
436		ceil: FixedI64,
437	) -> Curve {
438		let delay = FixedI64::from_rational(delay, period).into_perbill();
439		let mut bounds = (
440			(
441				FixedI64::from_u32(0),
442				Self::reciprocal_from_parts(FixedI64::from_u32(0), floor, ceil),
443				FixedI64::from_inner(i64::MAX),
444			),
445			(
446				FixedI64::from_u32(1),
447				Self::reciprocal_from_parts(FixedI64::from_u32(1), floor, ceil),
448				FixedI64::from_inner(i64::MAX),
449			),
450		);
451		const TWO: FixedI64 = FixedI64::from_u32(2);
452		while (bounds.1).0.sub((bounds.0).0).into_inner() > 1 {
453			let factor = (bounds.0).0.add((bounds.1).0).div(TWO);
454			let curve = Self::reciprocal_from_parts(factor, floor, ceil);
455			let curve_level = FixedI64::from_perbill(curve.const_threshold(delay));
456			if curve_level.into_inner() > level.into_inner() {
457				bounds = (bounds.0, (factor, curve, curve_level.sub(level)));
458			} else {
459				bounds = ((factor, curve, level.sub(curve_level)), bounds.1);
460			}
461		}
462		if (bounds.0).2.into_inner() < (bounds.1).2.into_inner() {
463			(bounds.0).1
464		} else {
465			(bounds.1).1
466		}
467	}
468
469	/// Create a `Curve::Reciprocal` instance from basic parameters.
470	///
471	/// WARNING: This is a `const` function designed for convenient use at build time and
472	/// will panic on overflow. Ensure that any inputs are sensible.
473	const fn reciprocal_from_parts(factor: FixedI64, floor: FixedI64, ceil: FixedI64) -> Self {
474		let delta = ceil.sub(floor);
475		let x_offset = pos_quad_solution(delta, delta, factor.neg());
476		let y_offset = floor.sub(factor.div(FixedI64::from_u32(1).add(x_offset)));
477		Curve::Reciprocal { factor, x_offset, y_offset }
478	}
479
480	/// Print some info on the curve.
481	#[cfg(feature = "std")]
482	pub fn info(&self, days: u32, name: impl std::fmt::Display) {
483		let hours = days * 24;
484		println!("Curve {} := {:?}:", name, self);
485		println!("   t + 0h:   {:?}", self.threshold(Perbill::zero()));
486		println!("   t + 1h:   {:?}", self.threshold(Perbill::from_rational(1, hours)));
487		println!("   t + 2h:   {:?}", self.threshold(Perbill::from_rational(2, hours)));
488		println!("   t + 3h:   {:?}", self.threshold(Perbill::from_rational(3, hours)));
489		println!("   t + 6h:   {:?}", self.threshold(Perbill::from_rational(6, hours)));
490		println!("   t + 12h:  {:?}", self.threshold(Perbill::from_rational(12, hours)));
491		println!("   t + 24h:  {:?}", self.threshold(Perbill::from_rational(24, hours)));
492		let mut l = 0;
493		for &(n, d) in [(1, 12), (1, 8), (1, 4), (1, 2), (3, 4), (1, 1)].iter() {
494			let t = days * n / d;
495			if t != l {
496				println!("   t + {}d:   {:?}", t, self.threshold(Perbill::from_rational(t, days)));
497				l = t;
498			}
499		}
500		let t = |p: Perbill| -> std::string::String {
501			if p.is_one() {
502				"never".into()
503			} else {
504				let minutes = p * (hours * 60);
505				if minutes < 60 {
506					format!("{} minutes", minutes)
507				} else if minutes < 8 * 60 && !minutes.is_multiple_of(60) {
508					format!("{} hours {} minutes", minutes / 60, minutes % 60)
509				} else if minutes < 72 * 60 {
510					format!("{} hours", minutes / 60)
511				} else if (minutes / 60).is_multiple_of(24) {
512					format!("{} days", minutes / 60 / 24)
513				} else {
514					format!("{} days {} hours", minutes / 60 / 24, minutes / 60 % 24)
515				}
516			}
517		};
518		if self.delay(Perbill::from_percent(49)) < Perbill::one() {
519			println!("   30% threshold:   {}", t(self.delay(Perbill::from_percent(30))));
520			println!("   10% threshold:   {}", t(self.delay(Perbill::from_percent(10))));
521			println!("   3% threshold:    {}", t(self.delay(Perbill::from_percent(3))));
522			println!("   1% threshold:    {}", t(self.delay(Perbill::from_percent(1))));
523			println!("   0.1% threshold:  {}", t(self.delay(Perbill::from_rational(1u32, 1_000))));
524			println!("   0.01% threshold: {}", t(self.delay(Perbill::from_rational(1u32, 10_000))));
525		} else {
526			println!(
527				"   99.9% threshold: {}",
528				t(self.delay(Perbill::from_rational(999u32, 1_000)))
529			);
530			println!("   99% threshold:   {}", t(self.delay(Perbill::from_percent(99))));
531			println!("   95% threshold:   {}", t(self.delay(Perbill::from_percent(95))));
532			println!("   90% threshold:   {}", t(self.delay(Perbill::from_percent(90))));
533			println!("   75% threshold:   {}", t(self.delay(Perbill::from_percent(75))));
534			println!("   60% threshold:   {}", t(self.delay(Perbill::from_percent(60))));
535		}
536	}
537
538	/// Determine the `y` value for the given `x` value.
539	pub fn threshold(&self, x: Perbill) -> Perbill {
540		match self {
541			Self::LinearDecreasing { length, floor, ceil } => {
542				*ceil - (x.min(*length).saturating_div(*length, Down) * (*ceil - *floor))
543			},
544			Self::SteppedDecreasing { begin, end, step, period } => {
545				(*begin - (step.int_mul(x.int_div(*period))).min(*begin)).max(*end)
546			},
547			Self::Reciprocal { factor, x_offset, y_offset } => factor
548				.checked_rounding_div(FixedI64::from(x) + *x_offset, Low)
549				.map(|yp| (yp + *y_offset).into_clamped_perthing())
550				.unwrap_or_else(Perbill::one),
551		}
552	}
553
554	/// Determine the `y` value for the given `x` value.
555	///
556	/// This is a partial implementation designed only for use in const functions.
557	const fn const_threshold(&self, x: Perbill) -> Perbill {
558		match self {
559			Self::Reciprocal { factor, x_offset, y_offset } => {
560				match factor.checked_rounding_div(FixedI64::from_perbill(x).add(*x_offset), Low) {
561					Some(yp) => (yp.add(*y_offset)).into_perbill(),
562					None => Perbill::one(),
563				}
564			},
565			_ => panic!("const_threshold cannot be used on this curve"),
566		}
567	}
568
569	/// Determine the smallest `x` value such that `passing` returns `true` when passed along with
570	/// the given `y` value.
571	///
572	/// If `passing` never returns `true` for any value of `x` when paired with `y`, then
573	/// `Perbill::one` may be returned.
574	///
575	/// ```nocompile
576	/// let c = Curve::LinearDecreasing { begin: Perbill::one(), delta: Perbill::one() };
577	/// //      ^^^ Can be any curve.
578	/// let y = Perbill::from_percent(50);
579	/// //      ^^^ Can be any value.
580	/// let x = c.delay(y);
581	/// assert!(c.passing(x, y));
582	/// ```
583	pub fn delay(&self, y: Perbill) -> Perbill {
584		match self {
585			Self::LinearDecreasing { length, floor, ceil } => {
586				if y < *floor {
587					Perbill::one()
588				} else if y > *ceil {
589					Perbill::zero()
590				} else {
591					(*ceil - y).saturating_div(*ceil - *floor, Up).saturating_mul(*length)
592				}
593			},
594			Self::SteppedDecreasing { begin, end, step, period } => {
595				if y < *end {
596					Perbill::one()
597				} else {
598					period.int_mul((*begin - y.min(*begin) + step.less_epsilon()).int_div(*step))
599				}
600			},
601			Self::Reciprocal { factor, x_offset, y_offset } => {
602				let y = FixedI64::from(y);
603				let maybe_term = factor.checked_rounding_div(y - *y_offset, High);
604				maybe_term
605					.and_then(|term| (term - *x_offset).try_into_perthing().ok())
606					.unwrap_or_else(Perbill::one)
607			},
608		}
609	}
610
611	/// Return `true` iff the `y` value is greater than the curve at the `x`.
612	pub fn passing(&self, x: Perbill, y: Perbill) -> bool {
613		y >= self.threshold(x)
614	}
615}
616
617#[cfg(feature = "std")]
618impl Debug for Curve {
619	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
620		match self {
621			Self::LinearDecreasing { length, floor, ceil } => {
622				write!(
623					f,
624					"Linear[(0%, {:?}) -> ({:?}, {:?}) -> (100%, {:?})]",
625					ceil, length, floor, floor,
626				)
627			},
628			Self::SteppedDecreasing { begin, end, step, period } => {
629				write!(
630					f,
631					"Stepped[(0%, {:?}) -> (100%, {:?}) by ({:?}, {:?})]",
632					begin, end, period, step,
633				)
634			},
635			Self::Reciprocal { factor, x_offset, y_offset } => {
636				write!(
637					f,
638					"Reciprocal[factor of {:?}, x_offset of {:?}, y_offset of {:?}]",
639					factor, x_offset, y_offset,
640				)
641			},
642		}
643	}
644}
645
646#[cfg(test)]
647mod tests {
648	use super::*;
649	use frame_support::traits::ConstU32;
650	use sp_runtime::{str_array as s, PerThing};
651
652	const fn percent(x: u128) -> FixedI64 {
653		FixedI64::from_rational(x, 100)
654	}
655
656	const TIP_APP: Curve = Curve::make_linear(10, 28, percent(50), percent(100));
657	const TIP_SUP: Curve = Curve::make_reciprocal(1, 28, percent(4), percent(0), percent(50));
658	const ROOT_APP: Curve = Curve::make_reciprocal(4, 28, percent(80), percent(50), percent(100));
659	const ROOT_SUP: Curve = Curve::make_linear(28, 28, percent(0), percent(50));
660	const WHITE_APP: Curve =
661		Curve::make_reciprocal(16, 28 * 24, percent(96), percent(50), percent(100));
662	const WHITE_SUP: Curve = Curve::make_reciprocal(1, 28, percent(20), percent(10), percent(50));
663	const SMALL_APP: Curve = Curve::make_linear(10, 28, percent(50), percent(100));
664	const SMALL_SUP: Curve = Curve::make_reciprocal(8, 28, percent(1), percent(0), percent(50));
665	const MID_APP: Curve = Curve::make_linear(17, 28, percent(50), percent(100));
666	const MID_SUP: Curve = Curve::make_reciprocal(12, 28, percent(1), percent(0), percent(50));
667	const BIG_APP: Curve = Curve::make_linear(23, 28, percent(50), percent(100));
668	const BIG_SUP: Curve = Curve::make_reciprocal(16, 28, percent(1), percent(0), percent(50));
669	const HUGE_APP: Curve = Curve::make_linear(28, 28, percent(50), percent(100));
670	const HUGE_SUP: Curve = Curve::make_reciprocal(20, 28, percent(1), percent(0), percent(50));
671	const PARAM_APP: Curve = Curve::make_reciprocal(4, 28, percent(80), percent(50), percent(100));
672	const PARAM_SUP: Curve = Curve::make_reciprocal(7, 28, percent(10), percent(0), percent(50));
673	const ADMIN_APP: Curve = Curve::make_linear(17, 28, percent(50), percent(100));
674	const ADMIN_SUP: Curve = Curve::make_reciprocal(12, 28, percent(1), percent(0), percent(50));
675
676	// TODO: ceil for linear.
677
678	#[test]
679	#[should_panic]
680	fn check_curves() {
681		TIP_APP.info(28u32, "Tip Approval");
682		TIP_SUP.info(28u32, "Tip Support");
683		ROOT_APP.info(28u32, "Root Approval");
684		ROOT_SUP.info(28u32, "Root Support");
685		WHITE_APP.info(28u32, "Whitelist Approval");
686		WHITE_SUP.info(28u32, "Whitelist Support");
687		SMALL_APP.info(28u32, "Small Spend Approval");
688		SMALL_SUP.info(28u32, "Small Spend Support");
689		MID_APP.info(28u32, "Mid Spend Approval");
690		MID_SUP.info(28u32, "Mid Spend Support");
691		BIG_APP.info(28u32, "Big Spend Approval");
692		BIG_SUP.info(28u32, "Big Spend Support");
693		HUGE_APP.info(28u32, "Huge Spend Approval");
694		HUGE_SUP.info(28u32, "Huge Spend Support");
695		PARAM_APP.info(28u32, "Mid-tier Parameter Change Approval");
696		PARAM_SUP.info(28u32, "Mid-tier Parameter Change Support");
697		ADMIN_APP.info(28u32, "Admin (e.g. Cancel Slash) Approval");
698		ADMIN_SUP.info(28u32, "Admin (e.g. Cancel Slash) Support");
699		assert!(false);
700	}
701
702	#[test]
703	fn insert_sorted_works() {
704		let mut b: BoundedVec<u32, ConstU32<6>> = vec![20, 30, 40].try_into().unwrap();
705		assert!(b.insert_sorted_by_key(10, |&x| x));
706		assert_eq!(&b[..], &[10, 20, 30, 40][..]);
707
708		assert!(b.insert_sorted_by_key(60, |&x| x));
709		assert_eq!(&b[..], &[10, 20, 30, 40, 60][..]);
710
711		assert!(b.insert_sorted_by_key(50, |&x| x));
712		assert_eq!(&b[..], &[10, 20, 30, 40, 50, 60][..]);
713
714		assert!(!b.insert_sorted_by_key(9, |&x| x));
715		assert_eq!(&b[..], &[10, 20, 30, 40, 50, 60][..]);
716
717		assert!(b.insert_sorted_by_key(11, |&x| x));
718		assert_eq!(&b[..], &[11, 20, 30, 40, 50, 60][..]);
719
720		assert!(b.insert_sorted_by_key(21, |&x| x));
721		assert_eq!(&b[..], &[20, 21, 30, 40, 50, 60][..]);
722
723		assert!(b.insert_sorted_by_key(61, |&x| x));
724		assert_eq!(&b[..], &[21, 30, 40, 50, 60, 61][..]);
725
726		assert!(b.insert_sorted_by_key(51, |&x| x));
727		assert_eq!(&b[..], &[30, 40, 50, 51, 60, 61][..]);
728	}
729
730	#[test]
731	fn translated_reciprocal_works() {
732		let c: Curve = Curve::Reciprocal {
733			factor: FixedI64::from_float(0.03125),
734			x_offset: FixedI64::from_float(0.0363306838226),
735			y_offset: FixedI64::from_float(0.139845532427),
736		};
737		c.info(28u32, "Test");
738
739		for i in 0..9_696_969u32 {
740			let query = Perbill::from_rational(i, 9_696_969);
741			// Determine the nearest point in time when the query will be above threshold.
742			let delay_needed = c.delay(query);
743			// Ensure that it actually does pass at that time, or that it will never pass.
744			assert!(delay_needed.is_one() || c.passing(delay_needed, query));
745		}
746	}
747
748	#[test]
749	fn stepped_decreasing_works() {
750		fn pc(x: u32) -> Perbill {
751			Perbill::from_percent(x)
752		}
753
754		let c =
755			Curve::SteppedDecreasing { begin: pc(80), end: pc(30), step: pc(10), period: pc(15) };
756
757		for i in 0..9_696_969u32 {
758			let query = Perbill::from_rational(i, 9_696_969);
759			// Determine the nearest point in time when the query will be above threshold.
760			let delay_needed = c.delay(query);
761			// Ensure that it actually does pass at that time, or that it will never pass.
762			assert!(delay_needed.is_one() || c.passing(delay_needed, query));
763		}
764
765		assert_eq!(c.threshold(pc(0)), pc(80));
766		assert_eq!(c.threshold(pc(15).less_epsilon()), pc(80));
767		assert_eq!(c.threshold(pc(15)), pc(70));
768		assert_eq!(c.threshold(pc(30).less_epsilon()), pc(70));
769		assert_eq!(c.threshold(pc(30)), pc(60));
770		assert_eq!(c.threshold(pc(45).less_epsilon()), pc(60));
771		assert_eq!(c.threshold(pc(45)), pc(50));
772		assert_eq!(c.threshold(pc(60).less_epsilon()), pc(50));
773		assert_eq!(c.threshold(pc(60)), pc(40));
774		assert_eq!(c.threshold(pc(75).less_epsilon()), pc(40));
775		assert_eq!(c.threshold(pc(75)), pc(30));
776		assert_eq!(c.threshold(pc(100)), pc(30));
777
778		assert_eq!(c.delay(pc(100)), pc(0));
779		assert_eq!(c.delay(pc(80)), pc(0));
780		assert_eq!(c.delay(pc(80).less_epsilon()), pc(15));
781		assert_eq!(c.delay(pc(70)), pc(15));
782		assert_eq!(c.delay(pc(70).less_epsilon()), pc(30));
783		assert_eq!(c.delay(pc(60)), pc(30));
784		assert_eq!(c.delay(pc(60).less_epsilon()), pc(45));
785		assert_eq!(c.delay(pc(50)), pc(45));
786		assert_eq!(c.delay(pc(50).less_epsilon()), pc(60));
787		assert_eq!(c.delay(pc(40)), pc(60));
788		assert_eq!(c.delay(pc(40).less_epsilon()), pc(75));
789		assert_eq!(c.delay(pc(30)), pc(75));
790		assert_eq!(c.delay(pc(30).less_epsilon()), pc(100));
791		assert_eq!(c.delay(pc(0)), pc(100));
792	}
793
794	#[test]
795	fn tracks_integrity_check_detects_unsorted() {
796		use crate::mock::RuntimeOrigin;
797
798		pub struct BadTracksInfo;
799		impl TracksInfo<u64, u64> for BadTracksInfo {
800			type Id = u8;
801			type RuntimeOrigin = <RuntimeOrigin as OriginTrait>::PalletsOrigin;
802			fn tracks() -> impl Iterator<Item = Cow<'static, Track<Self::Id, u64, u64>>> {
803				static DATA: [Track<u8, u64, u64>; 2] = [
804					Track {
805						id: 1u8,
806						info: TrackInfo {
807							name: s("root"),
808							max_deciding: 1,
809							decision_deposit: 10,
810							prepare_period: 4,
811							decision_period: 4,
812							confirm_period: 2,
813							min_enactment_period: 4,
814							min_approval: Curve::LinearDecreasing {
815								length: Perbill::from_percent(100),
816								floor: Perbill::from_percent(50),
817								ceil: Perbill::from_percent(100),
818							},
819							min_support: Curve::LinearDecreasing {
820								length: Perbill::from_percent(100),
821								floor: Perbill::from_percent(0),
822								ceil: Perbill::from_percent(100),
823							},
824						},
825					},
826					Track {
827						id: 0u8,
828						info: TrackInfo {
829							name: s("none"),
830							max_deciding: 3,
831							decision_deposit: 1,
832							prepare_period: 2,
833							decision_period: 2,
834							confirm_period: 1,
835							min_enactment_period: 2,
836							min_approval: Curve::LinearDecreasing {
837								length: Perbill::from_percent(100),
838								floor: Perbill::from_percent(95),
839								ceil: Perbill::from_percent(100),
840							},
841							min_support: Curve::LinearDecreasing {
842								length: Perbill::from_percent(100),
843								floor: Perbill::from_percent(90),
844								ceil: Perbill::from_percent(100),
845							},
846						},
847					},
848				];
849				DATA.iter().map(Cow::Borrowed)
850			}
851			fn track_for(_: &Self::RuntimeOrigin) -> Result<Self::Id, ()> {
852				unimplemented!()
853			}
854		}
855
856		assert_eq!(
857			BadTracksInfo::check_integrity(),
858			Err("The tracks that were returned by `tracks` were not sorted by `Id`")
859		);
860	}
861
862	#[test]
863	fn encoding_and_decoding_of_string_like_structure_works() {
864		let string_like = StringLike::<13>(*b"hello, world!");
865		let encoded: Vec<u8> = string_like.encode();
866
867		let decoded_as_vec: Vec<u8> =
868			Decode::decode(&mut &encoded.clone()[..]).expect("decoding as Vec<u8> should work");
869		assert_eq!(decoded_as_vec.len(), 13);
870		let decoded_as_str: alloc::string::String =
871			Decode::decode(&mut &encoded.clone()[..]).expect("decoding as str should work");
872		assert_eq!(decoded_as_str.len(), 13);
873		let decoded_as_string_like: StringLike<13> =
874			Decode::decode(&mut &encoded.clone()[..]).expect("decoding as StringLike should work");
875		assert_eq!(decoded_as_string_like.0.len(), 13);
876	}
877}