ab_core_primitives/
shard.rs

1//! Shard-related primitives
2
3use ab_io_type::trivial_type::TrivialType;
4use core::num::{NonZeroU32, NonZeroU128};
5use derive_more::Display;
6#[cfg(feature = "scale-codec")]
7use parity_scale_codec::{Decode, Encode, MaxEncodedLen};
8#[cfg(feature = "scale-codec")]
9use scale_info::TypeInfo;
10#[cfg(feature = "serde")]
11use serde::{Deserialize, Serialize};
12
13/// A kind of shard.
14///
15/// Schematically, the hierarchy of shards is as follows:
16/// ```text
17///                          Beacon chain
18///                          /          \
19///      Intermediate shard 1            Intermediate shard 2
20///              /  \                            /  \
21/// Leaf shard 11   Leaf shard 12   Leaf shard 22   Leaf shard 22
22/// ```
23///
24/// Beacon chain has index 0, intermediate shards indices 1..=1023. Leaf shards share the same least
25/// significant 10 bits as their respective intermediate shards, so leaf shards of intermediate
26/// shard 1 have indices like 1025,2049,3097,etc.
27///
28/// If represented as least significant bits first (as it will be in the formatted address):
29/// ```text
30/// Intermediate shard bits
31///     \            /
32///      1000_0000_0001_0000_0000
33///                 /            \
34///                Leaf shard bits
35/// ```
36///
37/// Note that shards that have 10 least significant bits set to 0 (corresponds to the beacon chain)
38/// are not leaf shards, in fact, they are not even physical shards that have nodes in general. The
39/// meaning of these shards is TBD, currently they are called "phantom" shards and may end up
40/// containing some system contracts with special meaning, but no blocks will ever exist for such
41/// shards.
42#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
43pub enum ShardKind {
44    /// Beacon chain shard
45    BeaconChain,
46    /// Intermediate shard directly below the beacon chain that has child shards
47    IntermediateShard,
48    /// Leaf shard, doesn't have child shards
49    LeafShard,
50    /// TODO
51    Phantom,
52    /// Invalid shard kind (if decoded from invalid bit pattern)
53    Invalid,
54}
55
56/// Shard index
57#[derive(Debug, Display, Copy, Clone, Hash, Ord, PartialOrd, Eq, PartialEq, TrivialType)]
58#[cfg_attr(
59    feature = "scale-codec",
60    derive(Encode, Decode, TypeInfo, MaxEncodedLen)
61)]
62#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
63#[repr(C)]
64pub struct ShardIndex(u32);
65
66impl ShardIndex {
67    /// Beacon chain
68    pub const BEACON_CHAIN: Self = Self(0);
69    /// Max possible shard index
70    pub const MAX_SHARD_INDEX: u32 = Self::MAX_SHARDS.get() - 1;
71    /// Max possible number of shards
72    pub const MAX_SHARDS: NonZeroU32 = NonZeroU32::new(2u32.pow(20)).expect("Not zero; qed");
73    /// Max possible number of addresses per shard
74    pub const MAX_ADDRESSES_PER_SHARD: NonZeroU128 =
75        NonZeroU128::new(2u128.pow(108)).expect("Not zero; qed");
76
77    // TODO: Remove once traits work in const environment and `From` could be used
78    /// Create shard index from `u32`.
79    ///
80    /// Returns `None` if `shard_index > ShardIndex::MAX_SHARD_INDEX`
81    ///
82    /// This is typically only necessary for low-level code.
83    #[inline(always)]
84    pub const fn new(shard_index: u32) -> Option<Self> {
85        if shard_index > Self::MAX_SHARD_INDEX {
86            return None;
87        }
88
89        Some(Self(shard_index))
90    }
91
92    // TODO: Remove once traits work in const environment and `From` could be used
93    /// Convert shard index to `u32`.
94    ///
95    /// This is typically only necessary for low-level code.
96    #[inline(always)]
97    pub const fn as_u32(self) -> u32 {
98        self.0
99    }
100
101    /// Whether the shard index corresponds to the beacon chain
102    #[inline(always)]
103    pub const fn is_beacon_chain(&self) -> bool {
104        self.0 == Self::BEACON_CHAIN.0
105    }
106
107    /// Whether the shard index corresponds to an intermediate shard
108    #[inline(always)]
109    pub const fn is_intermediate_shard(&self) -> bool {
110        self.0 >= 1 && self.0 <= 1023
111    }
112
113    /// Whether the shard index corresponds to an intermediate shard
114    #[inline(always)]
115    pub const fn is_leaf_shard(&self) -> bool {
116        if self.0 <= 1023 || self.0 > Self::MAX_SHARD_INDEX {
117            return false;
118        }
119
120        self.0 & 0b11_1111_1111 != 0
121    }
122
123    /// Whether the shard index corresponds to a phantom shard
124    #[inline(always)]
125    pub const fn is_phantom_shard(&self) -> bool {
126        if self.0 <= 1023 || self.0 > Self::MAX_SHARD_INDEX {
127            return false;
128        }
129
130        self.0 & 0b11_1111_1111 == 0
131    }
132
133    /// Check if this shard is a child shard of `parent`
134    #[inline]
135    pub const fn is_child_of(self, parent: Self) -> bool {
136        match self.shard_kind() {
137            ShardKind::BeaconChain => false,
138            ShardKind::IntermediateShard | ShardKind::Phantom => parent.is_beacon_chain(),
139            ShardKind::LeafShard => {
140                // Check that least significant bits match
141                self.0 & 0b11_1111_1111 == parent.0 & 0b11_1111_1111
142            }
143            ShardKind::Invalid => false,
144        }
145    }
146
147    /// Get shard kind
148    #[inline(always)]
149    pub const fn shard_kind(&self) -> ShardKind {
150        match self.0 {
151            0 => ShardKind::BeaconChain,
152            1..=1023 => ShardKind::IntermediateShard,
153            shard_index => {
154                if shard_index > Self::MAX_SHARD_INDEX {
155                    return ShardKind::Invalid;
156                }
157
158                // Check if least significant bits correspond to the beacon chain
159                if shard_index & 0b11_1111_1111 == 0 {
160                    ShardKind::Phantom
161                } else {
162                    ShardKind::LeafShard
163                }
164            }
165        }
166    }
167}
ab_core_primitives/shard.rs

ab_core_primitives/
shard.rs
