1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933
// This file is part of Substrate.
// Copyright (C) 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.
//! Implementation of a "bags list": a semi-sorted list where ordering granularity is dictated by
//! configurable thresholds that delineate the boundaries of bags. It uses a pattern of composite
//! data structures, where multiple storage items are masked by one outer API. See
//! [`crate::ListNodes`], [`crate::ListBags`] for more information.
//!
//! The outer API of this module is the [`List`] struct. It wraps all acceptable operations on top
//! of the aggregate linked list. All operations with the bags list should happen through this
//! interface.
use crate::Config;
use alloc::{
boxed::Box,
collections::{btree_map::BTreeMap, btree_set::BTreeSet},
};
use codec::{Decode, Encode, MaxEncodedLen};
use core::{iter, marker::PhantomData};
use frame_election_provider_support::ScoreProvider;
use frame_support::{
defensive, ensure,
traits::{Defensive, DefensiveOption, Get},
DefaultNoBound, PalletError,
};
use scale_info::TypeInfo;
use sp_runtime::traits::{Bounded, Zero};
#[cfg(any(
test,
feature = "try-runtime",
feature = "fuzz",
feature = "std",
feature = "runtime-benchmarks"
))]
use alloc::vec::Vec;
#[cfg(any(test, feature = "try-runtime", feature = "fuzz"))]
use sp_runtime::TryRuntimeError;
#[derive(Debug, PartialEq, Eq, Encode, Decode, MaxEncodedLen, TypeInfo, PalletError)]
pub enum ListError {
/// A duplicate id has been detected.
Duplicate,
/// An Id does not have a greater score than another Id.
NotHeavier,
/// Attempted to place node in front of a node in another bag.
NotInSameBag,
/// Given node id was not found.
NodeNotFound,
}
#[cfg(test)]
mod tests;
/// Given a certain score, to which bag does it belong to?
///
/// Bags are identified by their upper threshold; the value returned by this function is guaranteed
/// to be a member of `T::BagThresholds`.
///
/// Note that even if the thresholds list does not have `T::Score::max_value()` as its final member,
/// this function behaves as if it does.
pub fn notional_bag_for<T: Config<I>, I: 'static>(score: T::Score) -> T::Score {
let thresholds = T::BagThresholds::get();
let idx = thresholds.partition_point(|&threshold| score > threshold);
thresholds.get(idx).copied().unwrap_or_else(T::Score::max_value)
}
/// The **ONLY** entry point of this module. All operations to the bags-list should happen through
/// this interface. It is forbidden to access other module members directly.
//
// Data structure providing efficient mostly-accurate selection of the top N id by `Score`.
//
// It's implemented as a set of linked lists. Each linked list comprises a bag of ids of
// arbitrary and unbounded length, all having a score within a particular constant range.
// This structure means that ids can be added and removed in `O(1)` time.
//
// Iteration is accomplished by chaining the iteration of each bag, from greatest to least. While
// the users within any particular bag are sorted in an entirely arbitrary order, the overall score
// decreases as successive bags are reached. This means that it is valid to truncate
// iteration at any desired point; only those ids in the lowest bag can be excluded. This
// satisfies both the desire for fairness and the requirement for efficiency.
pub struct List<T: Config<I>, I: 'static = ()>(PhantomData<(T, I)>);
impl<T: Config<I>, I: 'static> List<T, I> {
/// Remove all data associated with the list from storage.
///
/// ## WARNING
///
/// this function should generally not be used in production as it could lead to a very large
/// number of storage accesses.
pub(crate) fn unsafe_clear() {
#[allow(deprecated)]
crate::ListBags::<T, I>::remove_all(None);
#[allow(deprecated)]
crate::ListNodes::<T, I>::remove_all();
}
/// Regenerate all of the data from the given ids.
///
/// WARNING: this is expensive and should only ever be performed when the list needs to be
/// generated from scratch. Care needs to be taken to ensure
///
/// This may or may not need to be called at genesis as well, based on the configuration of the
/// pallet using this `List`.
///
/// Returns the number of ids migrated.
pub fn unsafe_regenerate(
all: impl IntoIterator<Item = T::AccountId>,
score_of: Box<dyn Fn(&T::AccountId) -> T::Score>,
) -> u32 {
// NOTE: This call is unsafe for the same reason as SortedListProvider::unsafe_regenerate.
// I.e. because it can lead to many storage accesses.
// So it is ok to call it as caller must ensure the conditions.
Self::unsafe_clear();
Self::insert_many(all, score_of)
}
/// Migrate the list from one set of thresholds to another.
///
/// This should only be called as part of an intentional migration; it's fairly expensive.
///
/// Returns the number of accounts affected.
///
/// Preconditions:
///
/// - `old_thresholds` is the previous list of thresholds.
/// - All `bag_upper` currently in storage are members of `old_thresholds`.
/// - `T::BagThresholds` has already been updated and is the new set of thresholds.
///
/// Postconditions:
///
/// - All `bag_upper` currently in storage are members of `T::BagThresholds`.
/// - No id is changed unless required to by the difference between the old threshold list and
/// the new.
/// - ids whose bags change at all are implicitly rebagged into the appropriate bag in the new
/// threshold set.
#[allow(dead_code)]
pub fn migrate(old_thresholds: &[T::Score]) -> u32 {
let new_thresholds = T::BagThresholds::get();
if new_thresholds == old_thresholds {
return 0
}
// we can't check all preconditions, but we can check one
debug_assert!(
crate::ListBags::<T, I>::iter()
.all(|(threshold, _)| old_thresholds.contains(&threshold)),
"not all `bag_upper` currently in storage are members of `old_thresholds`",
);
debug_assert!(
crate::ListNodes::<T, I>::iter()
.all(|(_, node)| old_thresholds.contains(&node.bag_upper)),
"not all `node.bag_upper` currently in storage are members of `old_thresholds`",
);
let old_set: BTreeSet<_> = old_thresholds.iter().copied().collect();
let new_set: BTreeSet<_> = new_thresholds.iter().copied().collect();
// accounts that need to be rebagged
let mut affected_accounts = BTreeSet::new();
// track affected old bags to make sure we only iterate them once
let mut affected_old_bags = BTreeSet::new();
let new_bags = new_set.difference(&old_set).copied();
// a new bag means that all accounts previously using the old bag's threshold must now
// be rebagged
for inserted_bag in new_bags {
let affected_bag = {
// this recreates `notional_bag_for` logic, but with the old thresholds.
let idx = old_thresholds.partition_point(|&threshold| inserted_bag > threshold);
old_thresholds.get(idx).copied().unwrap_or_else(T::Score::max_value)
};
if !affected_old_bags.insert(affected_bag) {
// If the previous threshold list was [10, 20], and we insert [3, 5], then there's
// no point iterating through bag 10 twice.
continue
}
if let Some(bag) = Bag::<T, I>::get(affected_bag) {
affected_accounts.extend(bag.iter().map(|node| node.id));
}
}
let removed_bags = old_set.difference(&new_set).copied();
// a removed bag means that all members of that bag must be rebagged
for removed_bag in removed_bags.clone() {
if !affected_old_bags.insert(removed_bag) {
continue
}
if let Some(bag) = Bag::<T, I>::get(removed_bag) {
affected_accounts.extend(bag.iter().map(|node| node.id));
}
}
// migrate the voters whose bag has changed
let num_affected = affected_accounts.len() as u32;
let score_of = T::ScoreProvider::score;
let _removed = Self::remove_many(&affected_accounts);
debug_assert_eq!(_removed, num_affected);
let _inserted = Self::insert_many(affected_accounts.into_iter(), score_of);
debug_assert_eq!(_inserted, num_affected);
// we couldn't previously remove the old bags because both insertion and removal assume that
// it's always safe to add a bag if it's not present. Now that that's sorted, we can get rid
// of them.
//
// it's pretty cheap to iterate this again, because both sets are in-memory and require no
// lookups.
for removed_bag in removed_bags {
debug_assert!(
!crate::ListNodes::<T, I>::iter().any(|(_, node)| node.bag_upper == removed_bag),
"no id should be present in a removed bag",
);
crate::ListBags::<T, I>::remove(removed_bag);
}
num_affected
}
/// Returns `true` if the list contains `id`, otherwise returns `false`.
pub(crate) fn contains(id: &T::AccountId) -> bool {
crate::ListNodes::<T, I>::contains_key(id)
}
/// Get the score of the given node,
pub fn get_score(id: &T::AccountId) -> Result<T::Score, ListError> {
Node::<T, I>::get(id).map(|node| node.score()).ok_or(ListError::NodeNotFound)
}
/// Iterate over all nodes in all bags in the list.
///
/// Full iteration can be expensive; it's recommended to limit the number of items with
/// `.take(n)`.
pub(crate) fn iter() -> impl Iterator<Item = Node<T, I>> {
// We need a touch of special handling here: because we permit `T::BagThresholds` to
// omit the final bound, we need to ensure that we explicitly include that threshold in the
// list.
//
// It's important to retain the ability to omit the final bound because it makes tests much
// easier; they can just configure `type BagThresholds = ()`.
let thresholds = T::BagThresholds::get();
let iter = thresholds.iter().copied();
let iter: Box<dyn Iterator<Item = T::Score>> = if thresholds.last() ==
Some(&T::Score::max_value())
{
// in the event that they included it, we can just pass the iterator through unchanged.
Box::new(iter.rev())
} else {
// otherwise, insert it here.
Box::new(iter.chain(iter::once(T::Score::max_value())).rev())
};
iter.filter_map(Bag::get).flat_map(|bag| bag.iter())
}
/// Same as `iter`, but we start from a specific node.
///
/// All items after this node are returned, excluding `start` itself.
pub(crate) fn iter_from(
start: &T::AccountId,
) -> Result<impl Iterator<Item = Node<T, I>>, ListError> {
// We chain two iterators:
// 1. from the given `start` till the end of the bag
// 2. all the bags that come after `start`'s bag.
let start_node = Node::<T, I>::get(start).ok_or(ListError::NodeNotFound)?;
let start_node_upper = start_node.bag_upper;
let start_bag = core::iter::successors(start_node.next(), |prev| prev.next());
let thresholds = T::BagThresholds::get();
let idx = thresholds.partition_point(|&threshold| start_node_upper > threshold);
let leftover_bags = thresholds
.into_iter()
.take(idx)
.copied()
.rev()
.filter_map(Bag::get)
.flat_map(|bag| bag.iter());
Ok(start_bag.chain(leftover_bags))
}
/// Insert several ids into the appropriate bags in the list. Continues with insertions
/// if duplicates are detected.
///
/// Returns the final count of number of ids inserted.
fn insert_many(
ids: impl IntoIterator<Item = T::AccountId>,
score_of: impl Fn(&T::AccountId) -> T::Score,
) -> u32 {
let mut count = 0;
ids.into_iter().for_each(|v| {
let score = score_of(&v);
if Self::insert(v, score).is_ok() {
count += 1;
}
});
count
}
/// Insert a new id into the appropriate bag in the list.
///
/// Returns an error if the list already contains `id`.
pub(crate) fn insert(id: T::AccountId, score: T::Score) -> Result<(), ListError> {
if Self::contains(&id) {
return Err(ListError::Duplicate)
}
let bag_score = notional_bag_for::<T, I>(score);
let mut bag = Bag::<T, I>::get_or_make(bag_score);
// unchecked insertion is okay; we just got the correct `notional_bag_for`.
bag.insert_unchecked(id.clone(), score);
// new inserts are always the tail, so we must write the bag.
bag.put();
crate::log!(
debug,
"inserted {:?} with score {:?} into bag {:?}, new count is {}",
id,
score,
bag_score,
crate::ListNodes::<T, I>::count(),
);
Ok(())
}
/// Remove an id from the list, returning an error if `id` does not exists.
pub(crate) fn remove(id: &T::AccountId) -> Result<(), ListError> {
if !Self::contains(id) {
return Err(ListError::NodeNotFound)
}
let _ = Self::remove_many(core::iter::once(id));
Ok(())
}
/// Remove many ids from the list.
///
/// This is more efficient than repeated calls to `Self::remove`.
///
/// Returns the final count of number of ids removed.
fn remove_many<'a>(ids: impl IntoIterator<Item = &'a T::AccountId>) -> u32 {
let mut bags = BTreeMap::new();
let mut count = 0;
for id in ids.into_iter() {
let node = match Node::<T, I>::get(id) {
Some(node) => node,
None => continue,
};
count += 1;
if !node.is_terminal() {
// this node is not a head or a tail and thus the bag does not need to be updated
node.excise()
} else {
// this node is a head or tail, so the bag needs to be updated
let bag = bags
.entry(node.bag_upper)
.or_insert_with(|| Bag::<T, I>::get_or_make(node.bag_upper));
// node.bag_upper must be correct, therefore this bag will contain this node.
bag.remove_node_unchecked(&node);
}
// now get rid of the node itself
node.remove_from_storage_unchecked()
}
for (_, bag) in bags {
bag.put();
}
count
}
/// Update a node's position in the list.
///
/// If the node was in the correct bag, no effect. If the node was in the incorrect bag, they
/// are moved into the correct bag.
///
/// Returns `Some((old_idx, new_idx))` if the node moved, otherwise `None`. In both cases, the
/// node's score is written to the `score` field. Thus, this is not a noop, even if `None`.
///
/// This operation is somewhat more efficient than simply calling [`self.remove`] followed by
/// [`self.insert`]. However, given large quantities of nodes to move, it may be more efficient
/// to call [`self.remove_many`] followed by [`self.insert_many`].
pub(crate) fn update_position_for(
mut node: Node<T, I>,
new_score: T::Score,
) -> Option<(T::Score, T::Score)> {
node.score = new_score;
if node.is_misplaced(new_score) {
let old_bag_upper = node.bag_upper;
if !node.is_terminal() {
// this node is not a head or a tail, so we can just cut it out of the list. update
// and put the prev and next of this node, we do `node.put` inside `insert_note`.
node.excise();
} else if let Some(mut bag) = Bag::<T, I>::get(node.bag_upper) {
// this is a head or tail, so the bag must be updated.
bag.remove_node_unchecked(&node);
bag.put();
} else {
frame_support::defensive!(
"Node did not have a bag; BagsList is in an inconsistent state"
);
}
// put the node into the appropriate new bag.
let new_bag_upper = notional_bag_for::<T, I>(new_score);
let mut bag = Bag::<T, I>::get_or_make(new_bag_upper);
// prev, next, and bag_upper of the node are updated inside `insert_node`, also
// `node.put` is in there.
bag.insert_node_unchecked(node);
bag.put();
Some((old_bag_upper, new_bag_upper))
} else {
// just write the new score.
node.put();
None
}
}
/// Put `heavier_id` to the position directly in front of `lighter_id`. Both ids must be in the
/// same bag and the `score_of` `lighter_id` must be less than that of `heavier_id`.
pub(crate) fn put_in_front_of(
lighter_id: &T::AccountId,
heavier_id: &T::AccountId,
) -> Result<(), ListError> {
let lighter_node = Node::<T, I>::get(&lighter_id).ok_or(ListError::NodeNotFound)?;
let heavier_node = Node::<T, I>::get(&heavier_id).ok_or(ListError::NodeNotFound)?;
ensure!(lighter_node.bag_upper == heavier_node.bag_upper, ListError::NotInSameBag);
// this is the most expensive check, so we do it last.
ensure!(
T::ScoreProvider::score(&heavier_id) > T::ScoreProvider::score(&lighter_id),
ListError::NotHeavier
);
// remove the heavier node from this list. Note that this removes the node from storage and
// decrements the node counter.
let _ =
Self::remove(&heavier_id).defensive_proof("both nodes have been checked to exist; qed");
// re-fetch `lighter_node` from storage since it may have been updated when `heavier_node`
// was removed.
let lighter_node =
Node::<T, I>::get(lighter_id).defensive_ok_or_else(|| ListError::NodeNotFound)?;
// insert `heavier_node` directly in front of `lighter_node`. This will update both nodes
// in storage and update the node counter.
Self::insert_at_unchecked(lighter_node, heavier_node);
Ok(())
}
/// Insert `node` directly in front of `at`.
///
/// WARNINGS:
/// - this is a naive function in that it does not check if `node` belongs to the same bag as
/// `at`. It is expected that the call site will check preconditions.
/// - this will panic if `at.bag_upper` is not a bag that already exists in storage.
fn insert_at_unchecked(mut at: Node<T, I>, mut node: Node<T, I>) {
// connect `node` to its new `prev`.
node.prev = at.prev.clone();
if let Some(mut prev) = at.prev() {
prev.next = Some(node.id().clone());
prev.put()
}
// connect `node` and `at`.
node.next = Some(at.id().clone());
at.prev = Some(node.id().clone());
if node.is_terminal() {
// `node` is the new head, so we make sure the bag is updated. Note,
// since `node` is always in front of `at` we know that 1) there is always at least 2
// nodes in the bag, and 2) only `node` could be the head and only `at` could be the
// tail.
let mut bag = Bag::<T, I>::get(at.bag_upper)
.expect("given nodes must always have a valid bag. qed.");
if node.prev == None {
bag.head = Some(node.id().clone())
}
bag.put()
};
// write the updated nodes to storage.
at.put();
node.put();
}
/// Check the internal state of the list.
///
/// This should be called from the call-site, whenever one of the mutating apis (e.g. `insert`)
/// is being used, after all other staking data (such as counter) has been updated. It checks:
///
/// * there are no duplicate ids,
/// * length of this list is in sync with `ListNodes::count()`,
/// * and sanity-checks all bags and nodes. This will cascade down all the checks and makes sure
/// all bags and nodes are checked per *any* update to `List`.
#[cfg(any(test, feature = "try-runtime", feature = "fuzz"))]
pub(crate) fn do_try_state() -> Result<(), TryRuntimeError> {
let mut seen_in_list = BTreeSet::new();
ensure!(
Self::iter().map(|node| node.id).all(|id| seen_in_list.insert(id)),
"duplicate identified"
);
let iter_count = Self::iter().count() as u32;
let stored_count = crate::ListNodes::<T, I>::count();
let nodes_count = crate::ListNodes::<T, I>::iter().count() as u32;
ensure!(iter_count == stored_count, "iter_count != stored_count");
ensure!(stored_count == nodes_count, "stored_count != nodes_count");
crate::log!(trace, "count of nodes: {}", stored_count);
let active_bags = {
let thresholds = T::BagThresholds::get().iter().copied();
let thresholds: Vec<T::Score> =
if thresholds.clone().last() == Some(T::Score::max_value()) {
// in the event that they included it, we don't need to make any changes
thresholds.collect()
} else {
// otherwise, insert it here.
thresholds.chain(iter::once(T::Score::max_value())).collect()
};
thresholds.into_iter().filter_map(|t| Bag::<T, I>::get(t))
};
// build map of bags and the corresponding nodes to avoid multiple lookups
let mut bags_map = BTreeMap::<T::Score, Vec<T::AccountId>>::new();
let _ = active_bags.clone().try_for_each(|b| {
bags_map.insert(
b.bag_upper,
b.iter().map(|n: Node<T, I>| n.id().clone()).collect::<Vec<_>>(),
);
b.do_try_state()
})?;
let nodes_in_bags_count =
active_bags.clone().fold(0u32, |acc, cur| acc + cur.iter().count() as u32);
ensure!(nodes_count == nodes_in_bags_count, "stored_count != nodes_in_bags_count");
crate::log!(trace, "count of active bags {}", active_bags.count());
// check that all nodes are sane. We check the `ListNodes` storage item directly in case we
// have some "stale" nodes that are not in a bag.
for (_id, node) in crate::ListNodes::<T, I>::iter() {
// check that the node is in the correct bag
let expected_bag = bags_map
.get(&node.bag_upper)
.ok_or("bag not found for the node in active bags")?;
frame_support::ensure!(expected_bag.contains(node.id()), "node not found in the bag");
// verify node state
node.do_try_state()?
}
Ok(())
}
/// Returns the nodes of all non-empty bags. For testing and benchmarks.
#[cfg(any(feature = "std", feature = "runtime-benchmarks"))]
#[allow(dead_code)]
pub(crate) fn get_bags() -> Vec<(T::Score, Vec<T::AccountId>)> {
use frame_support::traits::Get as _;
let thresholds = T::BagThresholds::get();
let iter = thresholds.iter().copied();
let iter: Box<dyn Iterator<Item = T::Score>> = if thresholds.last() ==
Some(&T::Score::max_value())
{
// in the event that they included it, we can just pass the iterator through unchanged.
Box::new(iter)
} else {
// otherwise, insert it here.
Box::new(iter.chain(core::iter::once(T::Score::max_value())))
};
iter.filter_map(|t| {
Bag::<T, I>::get(t)
.map(|bag| (t, bag.iter().map(|n| n.id().clone()).collect::<Vec<_>>()))
})
.collect::<Vec<_>>()
}
}
/// A Bag is a doubly-linked list of ids, where each id is mapped to a [`Node`].
///
/// Note that we maintain both head and tail pointers. While it would be possible to get away with
/// maintaining only a head pointer and cons-ing elements onto the front of the list, it's more
/// desirable to ensure that there is some element of first-come, first-serve to the list's
/// iteration so that there's no incentive to churn ids positioning to improve the chances of
/// appearing within the ids set.
#[derive(DefaultNoBound, Encode, Decode, MaxEncodedLen, TypeInfo)]
#[codec(mel_bound())]
#[scale_info(skip_type_params(T, I))]
#[cfg_attr(feature = "std", derive(frame_support::DebugNoBound, Clone, PartialEq))]
pub struct Bag<T: Config<I>, I: 'static = ()> {
head: Option<T::AccountId>,
tail: Option<T::AccountId>,
#[codec(skip)]
bag_upper: T::Score,
#[codec(skip)]
_phantom: PhantomData<I>,
}
impl<T: Config<I>, I: 'static> Bag<T, I> {
#[cfg(test)]
pub(crate) fn new(
head: Option<T::AccountId>,
tail: Option<T::AccountId>,
bag_upper: T::Score,
) -> Self {
Self { head, tail, bag_upper, _phantom: PhantomData }
}
/// Get a bag by its upper score.
pub(crate) fn get(bag_upper: T::Score) -> Option<Bag<T, I>> {
crate::ListBags::<T, I>::try_get(bag_upper).ok().map(|mut bag| {
bag.bag_upper = bag_upper;
bag
})
}
/// Get a bag by its upper score or make it, appropriately initialized. Does not check if
/// if `bag_upper` is a valid threshold.
fn get_or_make(bag_upper: T::Score) -> Bag<T, I> {
Self::get(bag_upper).unwrap_or(Bag { bag_upper, ..Default::default() })
}
/// `True` if self is empty.
fn is_empty(&self) -> bool {
self.head.is_none() && self.tail.is_none()
}
/// Put the bag back into storage.
fn put(self) {
if self.is_empty() {
crate::ListBags::<T, I>::remove(self.bag_upper);
} else {
crate::ListBags::<T, I>::insert(self.bag_upper, self);
}
}
/// Get the head node in this bag.
fn head(&self) -> Option<Node<T, I>> {
self.head.as_ref().and_then(|id| Node::get(id))
}
/// Get the tail node in this bag.
fn tail(&self) -> Option<Node<T, I>> {
self.tail.as_ref().and_then(|id| Node::get(id))
}
/// Iterate over the nodes in this bag.
pub(crate) fn iter(&self) -> impl Iterator<Item = Node<T, I>> {
core::iter::successors(self.head(), |prev| prev.next())
}
/// Insert a new id into this bag.
///
/// This is private on purpose because it's naive: it doesn't check whether this is the
/// appropriate bag for this id at all. Generally, use [`List::insert`] instead.
///
/// Storage note: this modifies storage, but only for the nodes. You still need to call
/// `self.put()` after use.
fn insert_unchecked(&mut self, id: T::AccountId, score: T::Score) {
// insert_node will overwrite `prev`, `next` and `bag_upper` to the proper values. As long
// as this bag is the correct one, we're good. All calls to this must come after getting the
// correct [`notional_bag_for`].
self.insert_node_unchecked(Node::<T, I> {
id,
prev: None,
next: None,
bag_upper: Zero::zero(),
score,
_phantom: PhantomData,
});
}
/// Insert a node into this bag.
///
/// This is private on purpose because it's naive; it doesn't check whether this is the
/// appropriate bag for this node at all. Generally, use [`List::insert`] instead.
///
/// Storage note: this modifies storage, but only for the node. You still need to call
/// `self.put()` after use.
fn insert_node_unchecked(&mut self, mut node: Node<T, I>) {
if let Some(tail) = &self.tail {
if *tail == node.id {
// this should never happen, but this check prevents one path to a worst case
// infinite loop.
defensive!("system logic error: inserting a node who has the id of tail");
return
};
}
// re-set the `bag_upper`. Regardless of whatever the node had previously, now it is going
// to be `self.bag_upper`.
node.bag_upper = self.bag_upper;
let id = node.id.clone();
// update this node now, treating it as the new tail.
node.prev = self.tail.clone();
node.next = None;
node.put();
// update the previous tail.
if let Some(mut old_tail) = self.tail() {
old_tail.next = Some(id.clone());
old_tail.put();
}
self.tail = Some(id.clone());
// ensure head exist. This is only set when the length of the bag is just 1, i.e. if this is
// the first insertion into the bag. In this case, both head and tail should point to the
// same node.
if self.head.is_none() {
self.head = Some(id);
debug_assert!(self.iter().count() == 1);
}
}
/// Remove a node from this bag.
///
/// This is private on purpose because it doesn't check whether this bag contains the node in
/// the first place. Generally, use [`List::remove`] instead, similar to `insert_unchecked`.
///
/// Storage note: this modifies storage, but only for adjacent nodes. You still need to call
/// `self.put()` and `ListNodes::remove(id)` to update storage for the bag and `node`.
fn remove_node_unchecked(&mut self, node: &Node<T, I>) {
// reassign neighboring nodes.
node.excise();
// clear the bag head/tail pointers as necessary.
if self.tail.as_ref() == Some(&node.id) {
self.tail = node.prev.clone();
}
if self.head.as_ref() == Some(&node.id) {
self.head = node.next.clone();
}
}
/// Check the internal state of the bag.
///
/// Should be called by the call-site, after any mutating operation on a bag. The call site of
/// this struct is always `List`.
///
/// * Ensures head has no prev.
/// * Ensures tail has no next.
/// * Ensures there are no loops, traversal from head to tail is correct.
#[cfg(any(test, feature = "try-runtime", feature = "fuzz"))]
fn do_try_state(&self) -> Result<(), TryRuntimeError> {
frame_support::ensure!(
self.head()
.map(|head| head.prev().is_none())
// if there is no head, then there must not be a tail, meaning that the bag is
// empty.
.unwrap_or_else(|| self.tail.is_none()),
"head has a prev"
);
frame_support::ensure!(
self.tail()
.map(|tail| tail.next().is_none())
// if there is no tail, then there must not be a head, meaning that the bag is
// empty.
.unwrap_or_else(|| self.head.is_none()),
"tail has a next"
);
let mut seen_in_bag = BTreeSet::new();
frame_support::ensure!(
self.iter()
.map(|node| node.id)
// each voter is only seen once, thus there is no cycle within a bag
.all(|voter| seen_in_bag.insert(voter)),
"duplicate found in bag"
);
Ok(())
}
/// Iterate over the nodes in this bag (public for tests).
#[cfg(feature = "std")]
#[allow(dead_code)]
pub fn std_iter(&self) -> impl Iterator<Item = Node<T, I>> {
core::iter::successors(self.head(), |prev| prev.next())
}
}
/// A Node is the fundamental element comprising the doubly-linked list described by `Bag`.
#[derive(Encode, Decode, MaxEncodedLen, TypeInfo)]
#[codec(mel_bound())]
#[scale_info(skip_type_params(T, I))]
#[cfg_attr(feature = "std", derive(frame_support::DebugNoBound, Clone, PartialEq))]
pub struct Node<T: Config<I>, I: 'static = ()> {
pub(crate) id: T::AccountId,
pub(crate) prev: Option<T::AccountId>,
pub(crate) next: Option<T::AccountId>,
pub(crate) bag_upper: T::Score,
pub(crate) score: T::Score,
#[codec(skip)]
pub(crate) _phantom: PhantomData<I>,
}
impl<T: Config<I>, I: 'static> Node<T, I> {
/// Get a node by id.
pub fn get(id: &T::AccountId) -> Option<Node<T, I>> {
crate::ListNodes::<T, I>::try_get(id).ok()
}
/// Put the node back into storage.
fn put(self) {
crate::ListNodes::<T, I>::insert(self.id.clone(), self);
}
/// Update neighboring nodes to point to reach other.
///
/// Only updates storage for adjacent nodes, but not `self`; so the user may need to call
/// `self.put`.
fn excise(&self) {
// Update previous node.
if let Some(mut prev) = self.prev() {
prev.next = self.next.clone();
prev.put();
}
// Update next self.
if let Some(mut next) = self.next() {
next.prev = self.prev.clone();
next.put();
}
}
/// This is a naive function that removes a node from the `ListNodes` storage item.
///
/// It is naive because it does not check if the node has first been removed from its bag.
fn remove_from_storage_unchecked(&self) {
crate::ListNodes::<T, I>::remove(&self.id)
}
/// Get the previous node in the bag.
fn prev(&self) -> Option<Node<T, I>> {
self.prev.as_ref().and_then(|id| Node::get(id))
}
/// Get the next node in the bag.
fn next(&self) -> Option<Node<T, I>> {
self.next.as_ref().and_then(|id| Node::get(id))
}
/// `true` when this voter is in the wrong bag.
pub fn is_misplaced(&self, current_score: T::Score) -> bool {
notional_bag_for::<T, I>(current_score) != self.bag_upper
}
/// `true` when this voter is a bag head or tail.
fn is_terminal(&self) -> bool {
self.prev.is_none() || self.next.is_none()
}
/// Get the underlying voter.
pub(crate) fn id(&self) -> &T::AccountId {
&self.id
}
/// Get the current vote weight of the node.
pub(crate) fn score(&self) -> T::Score {
self.score
}
/// Get the underlying voter (public fo tests).
#[cfg(feature = "std")]
#[allow(dead_code)]
pub fn std_id(&self) -> &T::AccountId {
&self.id
}
#[cfg(any(feature = "runtime-benchmarks", feature = "fuzz", test))]
pub fn set_score(&mut self, s: T::Score) {
self.score = s
}
/// The bag this nodes belongs to (public for benchmarks).
#[cfg(feature = "runtime-benchmarks")]
#[allow(dead_code)]
pub fn bag_upper(&self) -> T::Score {
self.bag_upper
}
#[cfg(any(test, feature = "try-runtime", feature = "fuzz"))]
fn do_try_state(&self) -> Result<(), TryRuntimeError> {
let expected_bag = Bag::<T, I>::get(self.bag_upper).ok_or("bag not found for node")?;
let id = self.id();
let non_terminal_check = !self.is_terminal() &&
expected_bag.head.as_ref() != Some(id) &&
expected_bag.tail.as_ref() != Some(id);
let terminal_check =
expected_bag.head.as_ref() == Some(id) || expected_bag.tail.as_ref() == Some(id);
frame_support::ensure!(
non_terminal_check || terminal_check,
"a terminal node is neither its bag head or tail"
);
Ok(())
}
}