casper_node/components/consensus/utils/
validators.rs

1use std::{
2    collections::HashMap,
3    fmt,
4    hash::Hash,
5    iter::FromIterator,
6    ops::{Add, Index, IndexMut},
7    slice, vec,
8};
9
10use datasize::DataSize;
11use derive_more::{AsRef, From};
12use itertools::Itertools;
13use serde::{Deserialize, Serialize};
14use tracing::warn;
15
16use super::Weight;
17use crate::utils::ds;
18
19/// The index of a validator, in a list of all validators, ordered by ID.
20#[derive(
21    Copy, Clone, DataSize, Debug, Eq, PartialEq, Hash, Ord, PartialOrd, Serialize, Deserialize,
22)]
23pub struct ValidatorIndex(pub u32);
24
25impl From<u32> for ValidatorIndex {
26    fn from(idx: u32) -> Self {
27        ValidatorIndex(idx)
28    }
29}
30
31/// Information about a validator: their ID and weight.
32#[derive(Clone, DataSize, Debug, Eq, PartialEq)]
33pub struct Validator<VID> {
34    weight: Weight,
35    id: VID,
36    banned: bool,
37    can_propose: bool,
38}
39
40impl<VID, W: Into<Weight>> From<(VID, W)> for Validator<VID> {
41    fn from((id, weight): (VID, W)) -> Validator<VID> {
42        Validator {
43            id,
44            weight: weight.into(),
45            banned: false,
46            can_propose: true,
47        }
48    }
49}
50
51impl<VID> Validator<VID> {
52    /// Returns the validator's ID.
53    pub fn id(&self) -> &VID {
54        &self.id
55    }
56
57    /// Returns the validator's weight.
58    pub fn weight(&self) -> Weight {
59        self.weight
60    }
61}
62
63/// The validator IDs and weight map.
64#[derive(Debug, DataSize, Clone)]
65pub struct Validators<VID>
66where
67    VID: Eq + Hash,
68{
69    index_by_id: HashMap<VID, ValidatorIndex>,
70    validators: Vec<Validator<VID>>,
71    total_weight: Weight,
72}
73
74impl<VID: Eq + Hash> Validators<VID> {
75    /// Returns the total weight of the set of validators.
76    pub fn total_weight(&self) -> Weight {
77        self.total_weight
78    }
79
80    /// Returns the weight of the validator with the given index.
81    ///
82    /// *Panics* if the validator index does not exist.
83    pub fn weight(&self, idx: ValidatorIndex) -> Weight {
84        self.validators[idx.0 as usize].weight
85    }
86
87    /// Returns `true` if the map is empty.
88    pub fn is_empty(&self) -> bool {
89        self.validators.is_empty()
90    }
91
92    /// Returns the number of validators.
93    pub fn len(&self) -> usize {
94        self.validators.len()
95    }
96
97    /// Gets the index of a validator with the given ID. Returns `None` if no such validator is in
98    /// the set.
99    pub fn get_index(&self, id: &VID) -> Option<ValidatorIndex> {
100        self.index_by_id.get(id).cloned()
101    }
102
103    /// Returns validator ID by index, or `None` if it doesn't exist.
104    pub fn id(&self, idx: ValidatorIndex) -> Option<&VID> {
105        self.validators.get(idx.0 as usize).map(Validator::id)
106    }
107
108    /// Returns an iterator over all validators, sorted by ID.
109    pub fn iter(&self) -> impl Iterator<Item = &Validator<VID>> {
110        self.validators.iter()
111    }
112
113    /// Marks the validator with that ID as banned, if it exists, and excludes it from the leader
114    /// sequence.
115    pub fn ban(&mut self, vid: &VID) {
116        if let Some(idx) = self.get_index(vid) {
117            self.validators[idx.0 as usize].banned = true;
118            self.validators[idx.0 as usize].can_propose = false;
119        }
120    }
121
122    /// Marks the validator as excluded from the leader sequence.
123    pub fn set_cannot_propose(&mut self, vid: &VID) {
124        if let Some(idx) = self.get_index(vid) {
125            self.validators[idx.0 as usize].can_propose = false;
126        }
127    }
128
129    /// Returns an iterator of all indices of banned validators.
130    pub fn iter_banned_idx(&self) -> impl Iterator<Item = ValidatorIndex> + '_ {
131        self.iter()
132            .enumerate()
133            .filter(|(_, v)| v.banned)
134            .map(|(idx, _)| ValidatorIndex::from(idx as u32))
135    }
136
137    /// Returns an iterator of all indices of validators that are not allowed to propose values.
138    pub fn iter_cannot_propose_idx(&self) -> impl Iterator<Item = ValidatorIndex> + '_ {
139        self.iter()
140            .enumerate()
141            .filter(|(_, v)| !v.can_propose)
142            .map(|(idx, _)| ValidatorIndex::from(idx as u32))
143    }
144
145    /// Returns an iterator of pairs (validator index, validator ID).
146    pub fn enumerate_ids<'a>(&'a self) -> impl Iterator<Item = (ValidatorIndex, &'a VID)> {
147        let to_idx =
148            |(idx, v): (usize, &'a Validator<VID>)| (ValidatorIndex::from(idx as u32), v.id());
149        self.iter().enumerate().map(to_idx)
150    }
151
152    pub(crate) fn ensure_nonzero_proposing_stake(&mut self) -> bool {
153        if self.total_weight.is_zero() {
154            return false;
155        }
156        if self.iter().all(|v| v.banned || v.weight.is_zero()) {
157            warn!("everyone is banned; admitting banned validators anyway");
158            for validator in &mut self.validators {
159                validator.can_propose = true;
160                validator.banned = false;
161            }
162        } else if self.iter().all(|v| !v.can_propose || v.weight.is_zero()) {
163            warn!("everyone is excluded; allowing proposers who are currently inactive");
164            for validator in &mut self.validators {
165                if !validator.banned {
166                    validator.can_propose = true;
167                }
168            }
169        }
170        true
171    }
172}
173
174impl<VID: Ord + Hash + Clone, W: Into<Weight>> FromIterator<(VID, W)> for Validators<VID> {
175    fn from_iter<I: IntoIterator<Item = (VID, W)>>(ii: I) -> Validators<VID> {
176        let mut validators: Vec<_> = ii.into_iter().map(Validator::from).collect();
177        let total_weight = validators.iter().fold(Weight(0), |sum, v| {
178            sum.checked_add(v.weight())
179                .expect("total weight must be < 2^64")
180        });
181        validators.sort_by_cached_key(|val| val.id.clone());
182        let index_by_id = validators
183            .iter()
184            .enumerate()
185            .map(|(idx, val)| (val.id.clone(), ValidatorIndex(idx as u32)))
186            .collect();
187        Validators {
188            index_by_id,
189            validators,
190            total_weight,
191        }
192    }
193}
194
195impl<VID: Ord + Hash + fmt::Debug> fmt::Display for Validators<VID> {
196    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
197        writeln!(f, "Validators: index, ID, weight")?;
198        for (i, val) in self.validators.iter().enumerate() {
199            writeln!(f, "{:3}, {:?}, {}", i, val.id(), val.weight().0)?
200        }
201        Ok(())
202    }
203}
204
205/// A map from the set of validators to some values.
206#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize, AsRef, From, Hash)]
207pub struct ValidatorMap<T>(Vec<T>);
208
209impl<T> fmt::Display for ValidatorMap<Option<T>>
210where
211    T: fmt::Display,
212{
213    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
214        let view = self
215            .0
216            .iter()
217            .map(|maybe_el| match maybe_el {
218                None => "N".to_string(),
219                Some(el) => format!("{}", el),
220            })
221            .join(", ");
222        write!(f, "ValidatorMap({})", view)?;
223        Ok(())
224    }
225}
226
227impl<T> DataSize for ValidatorMap<T>
228where
229    T: DataSize,
230{
231    const IS_DYNAMIC: bool = Vec::<T>::IS_DYNAMIC;
232
233    const STATIC_HEAP_SIZE: usize = Vec::<T>::STATIC_HEAP_SIZE;
234
235    fn estimate_heap_size(&self) -> usize {
236        ds::vec_sample(&self.0)
237    }
238}
239
240impl<T> ValidatorMap<T> {
241    /// Returns the value for the given validator, or `None` if the index is out of range.
242    pub fn get(&self, idx: ValidatorIndex) -> Option<&T> {
243        self.0.get(idx.0 as usize)
244    }
245
246    /// Returns the number of values. This must equal the number of validators.
247    pub fn len(&self) -> usize {
248        self.0.len()
249    }
250
251    /// Returns `true` if this ValidatorMap is empty.
252    pub fn is_empty(&self) -> bool {
253        self.0.is_empty()
254    }
255
256    /// Returns an iterator over all values.
257    pub fn iter(&self) -> impl Iterator<Item = &T> {
258        self.0.iter()
259    }
260
261    /// Returns an iterator over mutable references to all values.
262    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
263        self.0.iter_mut()
264    }
265
266    /// Returns an iterator over all values, by validator index.
267    pub fn enumerate(&self) -> impl Iterator<Item = (ValidatorIndex, &T)> {
268        self.iter()
269            .enumerate()
270            .map(|(idx, value)| (ValidatorIndex(idx as u32), value))
271    }
272
273    /// Returns `true` if `self` has an entry for validator number `idx`.
274    pub fn has(&self, idx: ValidatorIndex) -> bool {
275        self.0.len() > idx.0 as usize
276    }
277
278    /// Returns an iterator over all validator indices.
279    pub fn keys(&self) -> impl Iterator<Item = ValidatorIndex> {
280        (0..self.len()).map(|idx| ValidatorIndex(idx as u32))
281    }
282
283    /// Binary searches this sorted `ValidatorMap` for `x`.
284    ///
285    /// Returns the lowest index of an entry `>= x`, or `None` if `x` is greater than all entries.
286    pub fn binary_search(&self, x: &T) -> Option<ValidatorIndex>
287    where
288        T: Ord,
289    {
290        match self.0.binary_search(x) {
291            // The standard library's binary search returns `Ok(i)` if it found `x` at index `i`,
292            // but `i` is not necessarily the lowest such index.
293            Ok(i) => Some(ValidatorIndex(
294                (0..i)
295                    .rev()
296                    .take_while(|j| self.0[*j] == *x)
297                    .last()
298                    .unwrap_or(i) as u32,
299            )),
300            // It returns `Err(i)` if `x` was not found but `i` is the index where `x` would have to
301            // be inserted to keep the list. This is either the lowest index of an entry `>= x`...
302            Err(i) if i < self.len() => Some(ValidatorIndex(i as u32)),
303            // ...or the end of the list if `x` is greater than all entries.
304            Err(_) => None,
305        }
306    }
307}
308
309impl<T> IntoIterator for ValidatorMap<T> {
310    type Item = T;
311    type IntoIter = vec::IntoIter<T>;
312    fn into_iter(self) -> Self::IntoIter {
313        self.0.into_iter()
314    }
315}
316
317impl<T> FromIterator<T> for ValidatorMap<T> {
318    fn from_iter<I: IntoIterator<Item = T>>(ii: I) -> ValidatorMap<T> {
319        ValidatorMap(ii.into_iter().collect())
320    }
321}
322
323impl<T> Index<ValidatorIndex> for ValidatorMap<T> {
324    type Output = T;
325
326    fn index(&self, vidx: ValidatorIndex) -> &T {
327        &self.0[vidx.0 as usize]
328    }
329}
330
331impl<T> IndexMut<ValidatorIndex> for ValidatorMap<T> {
332    fn index_mut(&mut self, vidx: ValidatorIndex) -> &mut T {
333        &mut self.0[vidx.0 as usize]
334    }
335}
336
337impl<'a, T> IntoIterator for &'a ValidatorMap<T> {
338    type Item = &'a T;
339    type IntoIter = slice::Iter<'a, T>;
340
341    fn into_iter(self) -> Self::IntoIter {
342        self.0.iter()
343    }
344}
345
346impl<Rhs, T: Copy + Add<Rhs, Output = T>> Add<ValidatorMap<Rhs>> for ValidatorMap<T> {
347    type Output = ValidatorMap<T>;
348    fn add(mut self, rhs: ValidatorMap<Rhs>) -> Self::Output {
349        #[allow(clippy::arithmetic_side_effects)]
350        self.0
351            .iter_mut()
352            .zip(rhs)
353            .for_each(|(lhs_val, rhs_val)| *lhs_val = *lhs_val + rhs_val);
354        self
355    }
356}
357
358impl<T> ValidatorMap<Option<T>> {
359    /// Returns the keys of all validators whose value is `Some`.
360    pub fn keys_some(&self) -> impl Iterator<Item = ValidatorIndex> + '_ {
361        self.iter_some().map(|(vidx, _)| vidx)
362    }
363
364    /// Returns an iterator over all values that are present, together with their index.
365    pub fn iter_some(&self) -> impl Iterator<Item = (ValidatorIndex, &T)> + '_ {
366        self.enumerate()
367            .filter_map(|(vidx, opt)| opt.as_ref().map(|val| (vidx, val)))
368    }
369}
370
371#[cfg(test)]
372mod tests {
373    use super::*;
374
375    #[test]
376    fn from_iter() {
377        let weights = vec![
378            ("Bob".to_string(), 5u64),
379            ("Carol".to_string(), 3),
380            ("Alice".to_string(), 4),
381        ];
382        let validators = Validators::from_iter(weights);
383        assert_eq!(ValidatorIndex(0), validators.index_by_id["Alice"]);
384        assert_eq!(ValidatorIndex(1), validators.index_by_id["Bob"]);
385        assert_eq!(ValidatorIndex(2), validators.index_by_id["Carol"]);
386    }
387
388    #[test]
389    fn binary_search() {
390        let list = ValidatorMap::from(vec![2, 3, 5, 5, 5, 5, 5, 9]);
391        // Searching for 5 returns the first index, even if the standard library doesn't.
392        assert!(
393            list.0.binary_search(&5).expect("5 is in the list") > 2,
394            "test case where the std's search would return a higher index"
395        );
396        assert_eq!(Some(ValidatorIndex(2)), list.binary_search(&5));
397        // Searching for 4 also returns 2, since that is the first index of a value >= 4.
398        assert_eq!(Some(ValidatorIndex(2)), list.binary_search(&4));
399        // 3 is found again, at index 1.
400        assert_eq!(Some(ValidatorIndex(1)), list.binary_search(&3));
401        // 10 is bigger than all entries.
402        assert_eq!(None, list.binary_search(&10));
403    }
404}
casper_node/components/consensus/utils/validators.rs

casper_node/components/consensus/utils/
validators.rs
