ssz/
list.rs

1//! `List<T, N>` — variable-length list with compile-time cap of `N` elements.
2
3use alloc::vec::Vec;
4use core::fmt;
5use digest::Digest;
6use digest::typenum::U32;
7
8use crate::merkle::{merkleize, mix_in_length, pack_bytes};
9use crate::vector::decode_var_collection;
10use crate::{BYTES_PER_LENGTH_OFFSET, Decode, DecodeError, Encode, HashTreeRoot};
11
12/// SSZ list with a maximum length of `N` elements.
13///
14/// Invariant: `inner.len() <= N`.
15pub struct List<T, const N: u64> {
16    inner: Vec<T>,
17}
18
19impl<T, const N: u64> List<T, N> {
20    /// Build from an existing `Vec`, enforcing the cap.
21    pub fn from_vec(v: Vec<T>) -> Result<Self, DecodeError> {
22        if (v.len() as u64) > N {
23            return Err(DecodeError::BoundExceeded {
24                len: v.len() as u64,
25                bound: N,
26            });
27        }
28        Ok(Self { inner: v })
29    }
30
31    /// Build an empty list.
32    pub fn new() -> Self {
33        Self { inner: Vec::new() }
34    }
35
36    /// Borrow the underlying storage.
37    pub fn as_slice(&self) -> &[T] {
38        &self.inner
39    }
40
41    /// Length of the list.
42    pub fn len(&self) -> usize {
43        self.inner.len()
44    }
45
46    /// `true` iff the list contains no elements.
47    pub fn is_empty(&self) -> bool {
48        self.inner.is_empty()
49    }
50
51    /// Append an element. Returns an error if the cap would be exceeded.
52    pub fn push(&mut self, item: T) -> Result<(), DecodeError> {
53        if (self.inner.len() as u64) >= N {
54            return Err(DecodeError::BoundExceeded {
55                len: self.inner.len() as u64 + 1,
56                bound: N,
57            });
58        }
59        self.inner.push(item);
60        Ok(())
61    }
62
63    /// Returns the inner storage.
64    pub fn into_inner(self) -> Vec<T> {
65        self.inner
66    }
67}
68
69impl<T, const N: u64> Default for List<T, N> {
70    fn default() -> Self {
71        Self::new()
72    }
73}
74
75impl<T: Clone, const N: u64> List<T, N> {
76    /// Convenience: build from a slice.
77    pub fn from_slice(items: &[T]) -> Result<Self, DecodeError> {
78        if (items.len() as u64) > N {
79            return Err(DecodeError::BoundExceeded {
80                len: items.len() as u64,
81                bound: N,
82            });
83        }
84        let mut v: Vec<T> = Vec::with_capacity(items.len());
85        for t in items {
86            v.push(t.clone());
87        }
88        Ok(Self { inner: v })
89    }
90}
91
92impl<T, const N: u64> core::ops::Deref for List<T, N> {
93    type Target = [T];
94    fn deref(&self) -> &[T] {
95        &self.inner
96    }
97}
98
99impl<T: fmt::Debug, const N: u64> fmt::Debug for List<T, N> {
100    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
101        f.debug_struct("List")
102            .field("cap", &N)
103            .field("inner", &&self.inner[..])
104            .finish()
105    }
106}
107
108impl<T: Clone, const N: u64> Clone for List<T, N> {
109    fn clone(&self) -> Self {
110        Self {
111            inner: self.inner.clone(),
112        }
113    }
114}
115
116impl<T: PartialEq, const N: u64> PartialEq for List<T, N> {
117    fn eq(&self, other: &Self) -> bool {
118        self.inner == other.inner
119    }
120}
121
122impl<T: Eq, const N: u64> Eq for List<T, N> {}
123
124// --------------------------------------------------------------------------
125// Encode / Decode / HashTreeRoot
126// --------------------------------------------------------------------------
127
128impl<T: Encode, const N: u64> Encode for List<T, N> {
129    fn is_ssz_fixed_len() -> bool {
130        false
131    }
132    fn ssz_fixed_len() -> usize {
133        BYTES_PER_LENGTH_OFFSET
134    }
135    fn ssz_bytes_len(&self) -> usize {
136        if T::is_ssz_fixed_len() {
137            T::ssz_fixed_len() * self.inner.len()
138        } else {
139            let mut total = self.inner.len() * BYTES_PER_LENGTH_OFFSET;
140            for item in &self.inner {
141                total += item.ssz_bytes_len();
142            }
143            total
144        }
145    }
146    fn ssz_append(&self, buf: &mut Vec<u8>) {
147        if T::is_ssz_fixed_len() {
148            for item in &self.inner {
149                item.ssz_append(buf);
150            }
151        } else {
152            let items: Vec<&T> = self.inner.iter().collect();
153            encode_var_list_payloads(&items, buf);
154        }
155    }
156}
157
158impl<T: Decode, const N: u64> Decode for List<T, N> {
159    fn is_ssz_fixed_len() -> bool {
160        false
161    }
162    fn ssz_fixed_len() -> usize {
163        BYTES_PER_LENGTH_OFFSET
164    }
165    fn from_ssz_bytes(bytes: &[u8]) -> Result<Self, DecodeError> {
166        let decoded = decode_list::<T>(bytes, N)?;
167        let mut inner: Vec<T> = Vec::with_capacity(decoded.len());
168        for t in decoded {
169            inner.push(t);
170        }
171        Ok(Self { inner })
172    }
173}
174
175impl<T: HashTreeRoot + Encode, const N: u64> HashTreeRoot for List<T, N> {
176    fn hash_tree_root<D: Digest<OutputSize = U32>>(&self) -> [u8; 32] {
177        let len = self.inner.len() as u64;
178        let inner_root = if T::is_basic_type() {
179            // Basic-type list: pack encoded bytes into chunks, merkleize
180            // with limit = ceil(N * size_of_T / 32).
181            let mut buf: Vec<u8> = Vec::new();
182            for t in &self.inner {
183                t.ssz_append(&mut buf);
184            }
185            let chunks = pack_bytes(&buf);
186            let cap_bytes = (N as usize).saturating_mul(T::ssz_fixed_len());
187            let chunk_limit = cap_bytes.div_ceil(32).max(1);
188            merkleize::<D>(&chunks, chunk_limit)
189        } else {
190            let roots: Vec<[u8; 32]> = self.inner.iter().map(|t| t.hash_tree_root::<D>()).collect();
191            merkleize::<D>(&roots, (N as usize).max(1))
192        };
193        mix_in_length::<D>(inner_root, len)
194    }
195}
196
197// --------------------------------------------------------------------------
198// Helpers
199// --------------------------------------------------------------------------
200
201/// Encode a slice of variable-length items as an SSZ list payload (no
202/// length prefix — the count is recovered from the first offset on
203/// decode). Used by both `List<T, N>` (for variable T) and `FixedVector<T,
204/// N>` (for variable T).
205pub(crate) fn encode_var_list_payloads<T: Encode + ?Sized>(items: &[&T], buf: &mut Vec<u8>) {
206    let n = items.len();
207    let header_size = n * BYTES_PER_LENGTH_OFFSET;
208    // Reserve space for the offset table.
209    let initial_len = buf.len();
210    buf.resize(initial_len + header_size, 0);
211
212    let mut running = header_size as u32;
213    for (i, item) in items.iter().enumerate() {
214        let off_pos = initial_len + i * BYTES_PER_LENGTH_OFFSET;
215        let off_bytes = running.to_le_bytes();
216        buf[off_pos..off_pos + 4].copy_from_slice(&off_bytes);
217        let before = buf.len();
218        item.ssz_append(buf);
219        let after = buf.len();
220        running = running
221            .checked_add((after - before) as u32)
222            .expect("ssz offset overflow");
223    }
224}
225
226/// Decode a list from an SSZ-encoded slice. `cap` is the compile-time
227/// maximum length (in elements).
228fn decode_list<T: Decode>(bytes: &[u8], cap: u64) -> Result<Vec<T>, DecodeError> {
229    if T::is_ssz_fixed_len() {
230        let elem_size = T::ssz_fixed_len();
231        if elem_size == 0 {
232            // A list of zero-sized fixed-length elements would need an
233            // explicit length prefix to be unambiguous. SSZ doesn't define
234            // that, so reject.
235            return Err(DecodeError::Custom("zero-sized fixed-length list element"));
236        }
237        if !bytes.len().is_multiple_of(elem_size) {
238            return Err(DecodeError::LengthMismatch {
239                expected: bytes.len().div_ceil(elem_size) * elem_size,
240                actual: bytes.len(),
241            });
242        }
243        let n = bytes.len() / elem_size;
244        if (n as u64) > cap {
245            return Err(DecodeError::BoundExceeded {
246                len: n as u64,
247                bound: cap,
248            });
249        }
250        let mut out = Vec::with_capacity(n);
251        for i in 0..n {
252            let start = i * elem_size;
253            out.push(T::from_ssz_bytes(&bytes[start..start + elem_size])?);
254        }
255        Ok(out)
256    } else {
257        let out = decode_var_collection::<T>(bytes, None)?;
258        if (out.len() as u64) > cap {
259            return Err(DecodeError::BoundExceeded {
260                len: out.len() as u64,
261                bound: cap,
262            });
263        }
264        Ok(out)
265    }
266}
ssz/list.rs

ssz/
list.rs
