frame_election_provider_support/
bounds.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//! Types and helpers to define and handle election bounds.
19//!
20//! ### Overview
21//!
22//! This module defines and implements types that help creating and handling election bounds.
23//! [`DataProviderBounds`] encapsulates the upper limits for the results provided by `DataProvider`
24//! implementors. Those limits can be defined over two axis: number of elements returned (`count`)
25//! and/or the size of the returned SCALE encoded structure (`size`).
26//!
27//! [`ElectionBoundsBuilder`] is a helper to construct data election bounds and it aims at
28//! preventing the caller from mistake the order of size and count limits.
29//!
30//! ### Examples
31//!
32//! [`ElectionBoundsBuilder`] helps defining the size and count bounds for both voters and targets.
33//!
34//! ```
35//! use frame_election_provider_support::bounds::*;
36//!
37//! // unbounded limits are never exhausted.
38//! let unbounded = ElectionBoundsBuilder::default().build();
39//! assert!(!unbounded.targets.exhausted(SizeBound(1_000_000_000).into(), None));
40//!
41//! let bounds = ElectionBoundsBuilder::default()
42//!     .voters_count(100.into())
43//!     .voters_size(1_000.into())
44//!     .targets_count(200.into())
45//!     .targets_size(2_000.into())
46//!     .build();
47//!
48//! assert!(!bounds.targets.exhausted(SizeBound(1).into(), CountBound(1).into()));
49//! assert!(bounds.targets.exhausted(SizeBound(1).into(), CountBound(100_000).into()));
50//! ```
51//!
52//! ### Implementation details
53//!
54//! A default or `None` bound means that no bounds are enforced (i.e. unlimited result size). In
55//! general, be careful when using unbounded election bounds in production.
56
57use codec::Encode;
58use core::ops::Add;
59use sp_runtime::traits::Zero;
60
61/// Count type for data provider bounds.
62///
63/// Encapsulates the counting of things that can be bounded in an election, such as voters,
64/// targets or anything else.
65///
66/// This struct is defined mostly to prevent callers from mistakenly using `CountBound` instead of
67/// `SizeBound` and vice-versa.
68#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
69pub struct CountBound(pub u32);
70
71impl From<u32> for CountBound {
72	fn from(value: u32) -> Self {
73		CountBound(value)
74	}
75}
76
77impl Add for CountBound {
78	type Output = Self;
79	fn add(self, rhs: Self) -> Self::Output {
80		CountBound(self.0.saturating_add(rhs.0))
81	}
82}
83
84impl Zero for CountBound {
85	fn is_zero(&self) -> bool {
86		self.0 == 0u32
87	}
88	fn zero() -> Self {
89		CountBound(0)
90	}
91}
92
93/// Size type for data provider bounds.
94///
95/// Encapsulates the size limit of things that can be bounded in an election, such as voters,
96/// targets or anything else. The size unit can represent anything depending on the election
97/// logic and implementation, but it most likely will represent bytes in SCALE encoding in this
98/// context.
99///
100/// This struct is defined mostly to prevent callers from mistakenly using `CountBound` instead of
101/// `SizeBound` and vice-versa.
102#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
103pub struct SizeBound(pub u32);
104
105impl From<u32> for SizeBound {
106	fn from(value: u32) -> Self {
107		SizeBound(value)
108	}
109}
110
111impl Zero for SizeBound {
112	fn is_zero(&self) -> bool {
113		self.0 == 0u32
114	}
115	fn zero() -> Self {
116		SizeBound(0)
117	}
118}
119
120impl Add for SizeBound {
121	type Output = Self;
122	fn add(self, rhs: Self) -> Self::Output {
123		SizeBound(self.0.saturating_add(rhs.0))
124	}
125}
126
127/// Data bounds for election data.
128///
129/// Limits the data returned by `DataProvider` implementors, defined over two axis: `count`,
130/// defining the maximum number of elements returned, and `size`, defining the limit in size
131/// (bytes) of the SCALE encoded result.
132///
133/// `None` represents unlimited bounds in both `count` and `size` axis.
134#[derive(Clone, Copy, Default, Debug, Eq, PartialEq)]
135pub struct DataProviderBounds {
136	pub count: Option<CountBound>,
137	pub size: Option<SizeBound>,
138}
139
140impl DataProviderBounds {
141	///  Returns true if `given_count` exhausts `self.count`.
142	pub fn count_exhausted(self, given_count: CountBound) -> bool {
143		self.count.map_or(false, |count| given_count > count)
144	}
145
146	///  Returns true if `given_size` exhausts `self.size`.
147	pub fn size_exhausted(self, given_size: SizeBound) -> bool {
148		self.size.map_or(false, |size| given_size > size)
149	}
150
151	/// Returns true if `given_size` or `given_count` exhausts `self.size` or `self_count`,
152	/// respectively.
153	pub fn exhausted(self, given_size: Option<SizeBound>, given_count: Option<CountBound>) -> bool {
154		self.count_exhausted(given_count.unwrap_or(CountBound::zero())) ||
155			self.size_exhausted(given_size.unwrap_or(SizeBound::zero()))
156	}
157
158	/// Ensures the given encode-able slice meets both the length and count bounds.
159	///
160	/// Same as `exhausted` but a better syntax.
161	pub fn slice_exhausted<T: Encode>(self, input: &[T]) -> bool {
162		let size = Some((input.encoded_size() as u32).into());
163		let count = Some((input.len() as u32).into());
164		self.exhausted(size, count)
165	}
166
167	/// Returns an instance of `Self` that is constructed by capping both the `count` and `size`
168	/// fields. If `self` is None, overwrite it with the provided bounds.
169	pub fn max(self, bounds: DataProviderBounds) -> Self {
170		DataProviderBounds {
171			count: self
172				.count
173				.map(|c| {
174					c.clamp(CountBound::zero(), bounds.count.unwrap_or(CountBound(u32::MAX))).into()
175				})
176				.or(bounds.count),
177			size: self
178				.size
179				.map(|c| {
180					c.clamp(SizeBound::zero(), bounds.size.unwrap_or(SizeBound(u32::MAX))).into()
181				})
182				.or(bounds.size),
183		}
184	}
185}
186
187/// The voter and target bounds of an election.
188///
189/// The bounds are defined over two axis: `count` of element of the election (voters or targets) and
190/// the `size` of the SCALE encoded result snapshot.
191#[derive(Clone, Debug, Copy)]
192pub struct ElectionBounds {
193	pub voters: DataProviderBounds,
194	pub targets: DataProviderBounds,
195}
196
197impl ElectionBounds {
198	/// Returns an error if the provided `count` and `size` do not fit in the voter's election
199	/// bounds.
200	pub fn ensure_voters_limits(
201		self,
202		count: CountBound,
203		size: SizeBound,
204	) -> Result<(), &'static str> {
205		match self.voters.exhausted(Some(size), Some(count)) {
206			true => Err("Ensure voters bounds: bounds exceeded."),
207			false => Ok(()),
208		}
209	}
210
211	/// Returns an error if the provided `count` and `size` do not fit in the target's election
212	/// bounds.
213	pub fn ensure_targets_limits(
214		self,
215		count: CountBound,
216		size: SizeBound,
217	) -> Result<(), &'static str> {
218		match self.targets.exhausted(Some(size), Some(count).into()) {
219			true => Err("Ensure targets bounds: bounds exceeded."),
220			false => Ok(()),
221		}
222	}
223}
224
225/// Utility builder for [`ElectionBounds`].
226#[derive(Copy, Clone, Default)]
227pub struct ElectionBoundsBuilder {
228	voters: Option<DataProviderBounds>,
229	targets: Option<DataProviderBounds>,
230}
231
232impl From<ElectionBounds> for ElectionBoundsBuilder {
233	fn from(bounds: ElectionBounds) -> Self {
234		ElectionBoundsBuilder { voters: Some(bounds.voters), targets: Some(bounds.targets) }
235	}
236}
237
238impl ElectionBoundsBuilder {
239	/// Sets the voters count bounds.
240	pub fn voters_count(mut self, count: CountBound) -> Self {
241		self.voters = self.voters.map_or(
242			Some(DataProviderBounds { count: Some(count), size: None }),
243			|mut bounds| {
244				bounds.count = Some(count);
245				Some(bounds)
246			},
247		);
248		self
249	}
250
251	/// Sets the voters size bounds.
252	pub fn voters_size(mut self, size: SizeBound) -> Self {
253		self.voters = self.voters.map_or(
254			Some(DataProviderBounds { count: None, size: Some(size) }),
255			|mut bounds| {
256				bounds.size = Some(size);
257				Some(bounds)
258			},
259		);
260		self
261	}
262
263	/// Sets the targets count bounds.
264	pub fn targets_count(mut self, count: CountBound) -> Self {
265		self.targets = self.targets.map_or(
266			Some(DataProviderBounds { count: Some(count), size: None }),
267			|mut bounds| {
268				bounds.count = Some(count);
269				Some(bounds)
270			},
271		);
272		self
273	}
274
275	/// Sets the targets size bounds.
276	pub fn targets_size(mut self, size: SizeBound) -> Self {
277		self.targets = self.targets.map_or(
278			Some(DataProviderBounds { count: None, size: Some(size) }),
279			|mut bounds| {
280				bounds.size = Some(size);
281				Some(bounds)
282			},
283		);
284		self
285	}
286
287	/// Set the voters bounds.
288	pub fn voters(mut self, bounds: Option<DataProviderBounds>) -> Self {
289		self.voters = bounds;
290		self
291	}
292
293	/// Set the targets bounds.
294	pub fn targets(mut self, bounds: Option<DataProviderBounds>) -> Self {
295		self.targets = bounds;
296		self
297	}
298
299	/// Caps the number of the voters bounds in self to `voters` bounds. If `voters` bounds are
300	/// higher than the self bounds, keeps it. Note that `None` bounds are equivalent to maximum
301	/// and should be treated as such.
302	pub fn voters_or_lower(mut self, voters: DataProviderBounds) -> Self {
303		self.voters = match self.voters {
304			None => Some(voters),
305			Some(v) => Some(v.max(voters)),
306		};
307		self
308	}
309
310	/// Caps the number of the target bounds in self to `voters` bounds. If `voters` bounds are
311	/// higher than the self bounds, keeps it. Note that `None` bounds are equivalent to maximum
312	/// and should be treated as such.
313	pub fn targets_or_lower(mut self, targets: DataProviderBounds) -> Self {
314		self.targets = match self.targets {
315			None => Some(targets),
316			Some(t) => Some(t.max(targets)),
317		};
318		self
319	}
320
321	/// Returns an instance of `ElectionBounds` from the current state.
322	pub fn build(self) -> ElectionBounds {
323		ElectionBounds {
324			voters: self.voters.unwrap_or_default(),
325			targets: self.targets.unwrap_or_default(),
326		}
327	}
328}
329
330#[cfg(test)]
331mod test {
332	use super::*;
333
334	use frame_support::{assert_err, assert_ok};
335
336	#[test]
337	fn data_provider_bounds_unbounded_works() {
338		let bounds = DataProviderBounds::default();
339		assert!(!bounds.exhausted(None, None));
340		assert!(!bounds.exhausted(SizeBound(u32::MAX).into(), CountBound(u32::MAX).into()));
341	}
342
343	#[test]
344	fn election_bounds_builder_and_exhausted_bounds_work() {
345		// voter bounds exhausts if count > 100 or size > 1_000; target bounds exhausts if count >
346		// 200 or size > 2_000.
347		let bounds = ElectionBoundsBuilder::default()
348			.voters_count(100.into())
349			.voters_size(1_000.into())
350			.targets_count(200.into())
351			.targets_size(2_000.into())
352			.build();
353
354		assert!(!bounds.voters.exhausted(None, None));
355		assert!(!bounds.voters.exhausted(SizeBound(10).into(), CountBound(10).into()));
356		assert!(!bounds.voters.exhausted(None, CountBound(100).into()));
357		assert!(!bounds.voters.exhausted(SizeBound(1_000).into(), None));
358		// exhausts bounds.
359		assert!(bounds.voters.exhausted(None, CountBound(101).into()));
360		assert!(bounds.voters.exhausted(SizeBound(1_001).into(), None));
361
362		assert!(!bounds.targets.exhausted(None, None));
363		assert!(!bounds.targets.exhausted(SizeBound(20).into(), CountBound(20).into()));
364		assert!(!bounds.targets.exhausted(None, CountBound(200).into()));
365		assert!(!bounds.targets.exhausted(SizeBound(2_000).into(), None));
366		// exhausts bounds.
367		assert!(bounds.targets.exhausted(None, CountBound(201).into()));
368		assert!(bounds.targets.exhausted(SizeBound(2_001).into(), None));
369	}
370
371	#[test]
372	fn election_bounds_ensure_limits_works() {
373		let bounds = ElectionBounds {
374			voters: DataProviderBounds { count: Some(CountBound(10)), size: Some(SizeBound(10)) },
375			targets: DataProviderBounds { count: Some(CountBound(10)), size: Some(SizeBound(10)) },
376		};
377
378		assert_ok!(bounds.ensure_voters_limits(CountBound(1), SizeBound(1)));
379		assert_ok!(bounds.ensure_voters_limits(CountBound(1), SizeBound(1)));
380		assert_ok!(bounds.ensure_voters_limits(CountBound(10), SizeBound(10)));
381		assert_err!(
382			bounds.ensure_voters_limits(CountBound(1), SizeBound(11)),
383			"Ensure voters bounds: bounds exceeded."
384		);
385		assert_err!(
386			bounds.ensure_voters_limits(CountBound(11), SizeBound(10)),
387			"Ensure voters bounds: bounds exceeded."
388		);
389
390		assert_ok!(bounds.ensure_targets_limits(CountBound(1), SizeBound(1)));
391		assert_ok!(bounds.ensure_targets_limits(CountBound(1), SizeBound(1)));
392		assert_ok!(bounds.ensure_targets_limits(CountBound(10), SizeBound(10)));
393		assert_err!(
394			bounds.ensure_targets_limits(CountBound(1), SizeBound(11)),
395			"Ensure targets bounds: bounds exceeded."
396		);
397		assert_err!(
398			bounds.ensure_targets_limits(CountBound(11), SizeBound(10)),
399			"Ensure targets bounds: bounds exceeded."
400		);
401	}
402
403	#[test]
404	fn data_provider_max_unbounded_works() {
405		let unbounded = DataProviderBounds::default();
406
407		// max of some bounds with unbounded data provider bounds will always return the defined
408		// bounds.
409		let bounds = DataProviderBounds { count: CountBound(5).into(), size: SizeBound(10).into() };
410		assert_eq!(unbounded.max(bounds), bounds);
411
412		let bounds = DataProviderBounds { count: None, size: SizeBound(10).into() };
413		assert_eq!(unbounded.max(bounds), bounds);
414
415		let bounds = DataProviderBounds { count: CountBound(5).into(), size: None };
416		assert_eq!(unbounded.max(bounds), bounds);
417	}
418
419	#[test]
420	fn data_provider_max_bounded_works() {
421		let bounds_one =
422			DataProviderBounds { count: CountBound(10).into(), size: SizeBound(100).into() };
423		let bounds_two =
424			DataProviderBounds { count: CountBound(100).into(), size: SizeBound(10).into() };
425		let max_bounds_expected =
426			DataProviderBounds { count: CountBound(10).into(), size: SizeBound(10).into() };
427
428		assert_eq!(bounds_one.max(bounds_two), max_bounds_expected);
429		assert_eq!(bounds_two.max(bounds_one), max_bounds_expected);
430	}
431
432	#[test]
433	fn election_bounds_clamp_works() {
434		let bounds = ElectionBoundsBuilder::default()
435			.voters_count(10.into())
436			.voters_size(10.into())
437			.voters_or_lower(DataProviderBounds {
438				count: CountBound(5).into(),
439				size: SizeBound(20).into(),
440			})
441			.targets_count(20.into())
442			.targets_or_lower(DataProviderBounds {
443				count: CountBound(30).into(),
444				size: SizeBound(30).into(),
445			})
446			.build();
447
448		assert_eq!(bounds.voters.count.unwrap(), CountBound(5));
449		assert_eq!(bounds.voters.size.unwrap(), SizeBound(10));
450		assert_eq!(bounds.targets.count.unwrap(), CountBound(20));
451		assert_eq!(bounds.targets.size.unwrap(), SizeBound(30));
452
453		// note that unbounded bounds (None) are equivalent to maximum value.
454		let bounds = ElectionBoundsBuilder::default()
455			.voters_or_lower(DataProviderBounds {
456				count: CountBound(5).into(),
457				size: SizeBound(20).into(),
458			})
459			.targets_or_lower(DataProviderBounds {
460				count: CountBound(10).into(),
461				size: SizeBound(10).into(),
462			})
463			.build();
464
465		assert_eq!(bounds.voters.count.unwrap(), CountBound(5));
466		assert_eq!(bounds.voters.size.unwrap(), SizeBound(20));
467		assert_eq!(bounds.targets.count.unwrap(), CountBound(10));
468		assert_eq!(bounds.targets.size.unwrap(), SizeBound(10));
469	}
470}
frame_election_provider_support/bounds.rs

frame_election_provider_support/
bounds.rs
