referrerpolicy=no-referrer-when-downgrade

frame_support/traits/
members.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//! Traits for dealing with the idea of membership.
19
20use alloc::vec::Vec;
21use core::marker::PhantomData;
22use impl_trait_for_tuples::impl_for_tuples;
23use sp_arithmetic::traits::AtLeast16BitUnsigned;
24use sp_runtime::DispatchResult;
25
26/// A trait for querying whether a type can be said to "contain" a value.
27pub trait Contains<T> {
28	/// Return `true` if this "contains" the given value `t`.
29	fn contains(t: &T) -> bool;
30}
31
32#[cfg_attr(all(not(feature = "tuples-96"), not(feature = "tuples-128")), impl_for_tuples(64))]
33#[cfg_attr(all(feature = "tuples-96", not(feature = "tuples-128")), impl_for_tuples(96))]
34#[cfg_attr(feature = "tuples-128", impl_for_tuples(128))]
35impl<T> Contains<T> for Tuple {
36	fn contains(t: &T) -> bool {
37		for_tuples!( #(
38			if Tuple::contains(t) { return true }
39		)* );
40		false
41	}
42}
43
44/// A trait for querying whether a type can be said to "contain" a pair-value.
45pub trait ContainsPair<A, B> {
46	/// Return `true` if this "contains" the pair-value `(a, b)`.
47	fn contains(a: &A, b: &B) -> bool;
48}
49
50#[cfg_attr(all(not(feature = "tuples-96"), not(feature = "tuples-128")), impl_for_tuples(64))]
51#[cfg_attr(all(feature = "tuples-96", not(feature = "tuples-128")), impl_for_tuples(96))]
52#[cfg_attr(feature = "tuples-128", impl_for_tuples(128))]
53impl<A, B> ContainsPair<A, B> for Tuple {
54	fn contains(a: &A, b: &B) -> bool {
55		for_tuples!( #(
56			if Tuple::contains(a, b) { return true }
57		)* );
58		false
59	}
60}
61
62/// Converter `struct` to use a `ContainsPair` implementation for a `Contains` bound.
63pub struct FromContainsPair<CP>(PhantomData<CP>);
64impl<A, B, CP: ContainsPair<A, B>> Contains<(A, B)> for FromContainsPair<CP> {
65	fn contains((ref a, ref b): &(A, B)) -> bool {
66		CP::contains(a, b)
67	}
68}
69
70/// A [`ContainsPair`] implementation that has a `Contains` implementation for each member of the
71/// pair.
72pub struct FromContains<CA, CB>(PhantomData<(CA, CB)>);
73impl<A, B, CA: Contains<A>, CB: Contains<B>> ContainsPair<A, B> for FromContains<CA, CB> {
74	fn contains(a: &A, b: &B) -> bool {
75		CA::contains(a) && CB::contains(b)
76	}
77}
78
79/// A [`Contains`] implementation that contains every value.
80pub enum Everything {}
81impl<T> Contains<T> for Everything {
82	fn contains(_: &T) -> bool {
83		true
84	}
85}
86impl<A, B> ContainsPair<A, B> for Everything {
87	fn contains(_: &A, _: &B) -> bool {
88		true
89	}
90}
91
92/// A [`Contains`] implementation that contains no value.
93pub enum Nothing {}
94impl<T> Contains<T> for Nothing {
95	fn contains(_: &T) -> bool {
96		false
97	}
98}
99impl<A, B> ContainsPair<A, B> for Nothing {
100	fn contains(_: &A, _: &B) -> bool {
101		false
102	}
103}
104
105/// A [`Contains`] implementation that contains everything except the values in `Exclude`.
106pub struct EverythingBut<Exclude>(PhantomData<Exclude>);
107impl<T, Exclude: Contains<T>> Contains<T> for EverythingBut<Exclude> {
108	fn contains(t: &T) -> bool {
109		!Exclude::contains(t)
110	}
111}
112impl<A, B, Exclude: ContainsPair<A, B>> ContainsPair<A, B> for EverythingBut<Exclude> {
113	fn contains(a: &A, b: &B) -> bool {
114		!Exclude::contains(a, b)
115	}
116}
117
118/// A [`Contains`] implementation that contains all members of `These` excepting any members in
119/// `Except`.
120pub struct TheseExcept<These, Except>(PhantomData<(These, Except)>);
121impl<T, These: Contains<T>, Except: Contains<T>> Contains<T> for TheseExcept<These, Except> {
122	fn contains(t: &T) -> bool {
123		These::contains(t) && !Except::contains(t)
124	}
125}
126impl<A, B, These: ContainsPair<A, B>, Except: ContainsPair<A, B>> ContainsPair<A, B>
127	for TheseExcept<These, Except>
128{
129	fn contains(a: &A, b: &B) -> bool {
130		These::contains(a, b) && !Except::contains(a, b)
131	}
132}
133
134/// A [`Contains`] implementation which contains all members of `These` which are also members of
135/// `Those`.
136pub struct InsideBoth<These, Those>(PhantomData<(These, Those)>);
137impl<T, These: Contains<T>, Those: Contains<T>> Contains<T> for InsideBoth<These, Those> {
138	fn contains(t: &T) -> bool {
139		These::contains(t) && Those::contains(t)
140	}
141}
142impl<A, B, These: ContainsPair<A, B>, Those: ContainsPair<A, B>> ContainsPair<A, B>
143	for InsideBoth<These, Those>
144{
145	fn contains(a: &A, b: &B) -> bool {
146		These::contains(a, b) && Those::contains(a, b)
147	}
148}
149
150/// An implementation of [`Contains`] which contains only equal members to `T`.
151pub struct Equals<T>(PhantomData<T>);
152impl<X: PartialEq, T: super::Get<X>> Contains<X> for Equals<T> {
153	fn contains(t: &X) -> bool {
154		t == &T::get()
155	}
156}
157
158/// Create a type which implements the `Contains` trait for a particular type with syntax similar
159/// to `matches!`.
160#[macro_export]
161macro_rules! match_types {
162	(
163		pub type $n:ident: impl Contains<$t:ty> = {
164			$phead:pat_param $( | $ptail:pat )*
165		};
166		$( $rest:tt )*
167	) => {
168		pub struct $n;
169		impl $crate::traits::Contains<$t> for $n {
170			fn contains(l: &$t) -> bool {
171				matches!(l, $phead $( | $ptail )* )
172			}
173		}
174		$crate::match_types!( $( $rest )* );
175	};
176	(
177		pub type $n:ident: impl ContainsPair<$a:ty, $b:ty> = {
178			$phead:pat_param $( | $ptail:pat )*
179		};
180		$( $rest:tt )*
181	) => {
182		pub struct $n;
183		impl $crate::traits::ContainsPair<$a, $b> for $n {
184			fn contains(a: &$a, b: &$b) -> bool {
185				matches!((a, b), $phead $( | $ptail )* )
186			}
187		}
188		$crate::match_types!( $( $rest )* );
189	};
190	() => {}
191}
192
193/// Create a type which implements the `Contains` trait for a particular type with syntax similar
194/// to `matches!`.
195#[macro_export]
196#[deprecated = "Use `match_types!` instead"]
197macro_rules! match_type {
198	($( $x:tt )*) => { $crate::match_types!( $( $x )* ); }
199}
200
201#[deprecated = "Use `Everything` instead"]
202pub type AllowAll = Everything;
203#[deprecated = "Use `Nothing` instead"]
204pub type DenyAll = Nothing;
205#[deprecated = "Use `Contains` instead"]
206pub trait Filter<T> {
207	fn filter(t: &T) -> bool;
208}
209#[allow(deprecated)]
210impl<T, C: Contains<T>> Filter<T> for C {
211	fn filter(t: &T) -> bool {
212		Self::contains(t)
213	}
214}
215
216#[cfg(test)]
217mod tests {
218	use super::*;
219
220	match_types! {
221		pub type OneOrTenToTwenty: impl Contains<u8> = { 1 | 10..=20 };
222	}
223
224	#[test]
225	fn match_types_works() {
226		for i in 0..=255 {
227			assert_eq!(OneOrTenToTwenty::contains(&i), i == 1 || i >= 10 && i <= 20);
228		}
229	}
230}
231
232/// A trait for a set which can enumerate its members in order.
233pub trait SortedMembers<T: Ord> {
234	/// Get a vector of all members in the set, ordered.
235	fn sorted_members() -> Vec<T>;
236
237	/// Return `true` if this "contains" the given value `t`.
238	fn contains(t: &T) -> bool {
239		Self::sorted_members().binary_search(t).is_ok()
240	}
241
242	/// Get the number of items in the set.
243	fn count() -> usize {
244		Self::sorted_members().len()
245	}
246
247	/// Add an item that would satisfy `contains`. It does not make sure any other
248	/// state is correctly maintained or generated.
249	///
250	/// **Should be used for benchmarking only!!!**
251	#[cfg(feature = "runtime-benchmarks")]
252	fn add(_t: &T) {
253		unimplemented!()
254	}
255}
256
257/// Adapter struct for turning an `OrderedMembership` impl into a `Contains` impl.
258pub struct AsContains<OM>(PhantomData<(OM,)>);
259impl<T: Ord + Eq, OM: SortedMembers<T>> Contains<T> for AsContains<OM> {
260	fn contains(t: &T) -> bool {
261		OM::contains(t)
262	}
263}
264
265/// Trivial utility for implementing `Contains`/`OrderedMembership` with a `Vec`.
266pub struct IsInVec<T>(PhantomData<T>);
267impl<X: Eq, T: super::Get<Vec<X>>> Contains<X> for IsInVec<T> {
268	fn contains(t: &X) -> bool {
269		T::get().contains(t)
270	}
271}
272impl<X: Ord + PartialOrd, T: super::Get<Vec<X>>> SortedMembers<X> for IsInVec<T> {
273	fn sorted_members() -> Vec<X> {
274		let mut r = T::get();
275		r.sort();
276		r
277	}
278}
279
280/// A trait for querying bound for the length of an implementation of `Contains`
281pub trait ContainsLengthBound {
282	/// Minimum number of elements contained
283	fn min_len() -> usize;
284	/// Maximum number of elements contained
285	fn max_len() -> usize;
286}
287
288/// Ranked membership data structure.
289pub trait RankedMembers {
290	type AccountId;
291	type Rank: AtLeast16BitUnsigned;
292
293	/// The lowest rank possible in this membership organisation.
294	fn min_rank() -> Self::Rank;
295
296	/// Return the rank of the given ID, or `None` if they are not a member.
297	fn rank_of(who: &Self::AccountId) -> Option<Self::Rank>;
298
299	/// Add a member to the group at the `min_rank()`.
300	fn induct(who: &Self::AccountId) -> DispatchResult;
301
302	/// Promote a member to the next higher rank.
303	fn promote(who: &Self::AccountId) -> DispatchResult;
304
305	/// Demote a member to the next lower rank; demoting beyond the `min_rank` removes the
306	/// member entirely.
307	fn demote(who: &Self::AccountId) -> DispatchResult;
308}
309
310/// Handler that can deal with the swap of two members.
311#[impl_trait_for_tuples::impl_for_tuples(16)]
312pub trait RankedMembersSwapHandler<AccountId, Rank> {
313	/// Member `old` was swapped with `new` at `rank`.
314	fn swapped(who: &AccountId, new_who: &AccountId, rank: Rank);
315}
316
317/// Trait for type that can handle the initialization of account IDs at genesis.
318pub trait InitializeMembers<AccountId> {
319	/// Initialize the members to the given `members`.
320	fn initialize_members(members: &[AccountId]);
321}
322
323impl<T> InitializeMembers<T> for () {
324	fn initialize_members(_: &[T]) {}
325}
326
327/// Trait for type that can handle incremental changes to a set of account IDs.
328pub trait ChangeMembers<AccountId: Clone + Ord> {
329	/// A number of members `incoming` just joined the set and replaced some `outgoing` ones. The
330	/// new set is given by `new`, and need not be sorted.
331	///
332	/// This resets any previous value of prime.
333	fn change_members(incoming: &[AccountId], outgoing: &[AccountId], mut new: Vec<AccountId>) {
334		new.sort();
335		Self::change_members_sorted(incoming, outgoing, &new[..]);
336	}
337
338	/// A number of members `_incoming` just joined the set and replaced some `_outgoing` ones. The
339	/// new set is thus given by `sorted_new` and **must be sorted**.
340	///
341	/// NOTE: This is the only function that needs to be implemented in `ChangeMembers`.
342	///
343	/// This resets any previous value of prime.
344	fn change_members_sorted(
345		incoming: &[AccountId],
346		outgoing: &[AccountId],
347		sorted_new: &[AccountId],
348	);
349
350	/// Set the new members; they **must already be sorted**. This will compute the diff and use it
351	/// to call `change_members_sorted`.
352	///
353	/// This resets any previous value of prime.
354	fn set_members_sorted(new_members: &[AccountId], old_members: &[AccountId]) {
355		let (incoming, outgoing) = Self::compute_members_diff_sorted(new_members, old_members);
356		Self::change_members_sorted(&incoming[..], &outgoing[..], new_members);
357	}
358
359	/// Compute diff between new and old members; they **must already be sorted**.
360	///
361	/// Returns incoming and outgoing members.
362	fn compute_members_diff_sorted(
363		new_members: &[AccountId],
364		old_members: &[AccountId],
365	) -> (Vec<AccountId>, Vec<AccountId>) {
366		let mut old_iter = old_members.iter();
367		let mut new_iter = new_members.iter();
368		let mut incoming = Vec::new();
369		let mut outgoing = Vec::new();
370		let mut old_i = old_iter.next();
371		let mut new_i = new_iter.next();
372		loop {
373			match (old_i, new_i) {
374				(None, None) => break,
375				(Some(old), Some(new)) if old == new => {
376					old_i = old_iter.next();
377					new_i = new_iter.next();
378				},
379				(Some(old), Some(new)) if old < new => {
380					outgoing.push(old.clone());
381					old_i = old_iter.next();
382				},
383				(Some(old), None) => {
384					outgoing.push(old.clone());
385					old_i = old_iter.next();
386				},
387				(_, Some(new)) => {
388					incoming.push(new.clone());
389					new_i = new_iter.next();
390				},
391			}
392		}
393		(incoming, outgoing)
394	}
395
396	/// Set the prime member.
397	fn set_prime(_prime: Option<AccountId>) {}
398
399	/// Get the current prime.
400	fn get_prime() -> Option<AccountId> {
401		None
402	}
403}
404
405impl<T: Clone + Ord> ChangeMembers<T> for () {
406	fn change_members(_: &[T], _: &[T], _: Vec<T>) {}
407	fn change_members_sorted(_: &[T], _: &[T], _: &[T]) {}
408	fn set_members_sorted(_: &[T], _: &[T]) {}
409	fn set_prime(_: Option<T>) {}
410}