borsh/schema/container_ext/
max_size.rs

1use super::{BorshSchemaContainer, Declaration, Definition, Fields};
2use crate::__private::maybestd::{string::ToString, vec::Vec};
3
4use core::num::NonZeroUsize;
5
6/// NonZeroUsize of value one.
7// TODO: Replace usage by NonZeroUsize::MIN once MSRV is 1.70+.
8const ONE: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(1) };
9
10impl BorshSchemaContainer {
11    /// Returns the largest possible size of a serialised object based solely on its type.
12    ///
13    /// Even when if returned upper bound is correct, the theoretical value may be
14    /// *much* larger than any practical length.  For example, maximum encoded
15    /// length of `String` is 4 GiB while in practice one may encounter strings of
16    /// at most dozen of characters.
17    ///
18    /// # Example
19    ///
20    /// ```
21    /// use borsh::schema::BorshSchemaContainer;
22    ///
23    /// let schema = BorshSchemaContainer::for_type::<()>();
24    /// assert_eq!(Ok(0), schema.max_serialized_size());
25    ///
26    /// let schema = BorshSchemaContainer::for_type::<usize>();
27    /// assert_eq!(Ok(8), schema.max_serialized_size());
28    ///
29    /// // 4 bytes of length and u32::MAX for the longest possible string.
30    /// let schema = BorshSchemaContainer::for_type::<String>();
31    /// assert_eq!(Ok(4 + 4294967295), schema.max_serialized_size());
32    ///
33    /// let schema = BorshSchemaContainer::for_type::<Vec<String>>();
34    /// assert_eq!(Err(borsh::schema::SchemaMaxSerializedSizeError::Overflow),
35    ///            schema.max_serialized_size());
36    /// ```
37    pub fn max_serialized_size(&self) -> Result<usize, Error> {
38        let mut stack = Vec::new();
39        max_serialized_size_impl(ONE, self.declaration(), self, &mut stack)
40    }
41}
42
43/// Possible error when calculating theoretical maximum size of encoded type `T`.
44#[derive(Clone, PartialEq, Eq, Debug)]
45pub enum Error {
46    /// The theoretical maximum size of the encoded value overflows `usize`.
47    ///
48    /// This may happen for nested dynamically-sized types such as
49    /// `Vec<Vec<u8>>` whose maximum size is `4 + u32::MAX * (4 + u32::MAX)`.
50    Overflow,
51
52    /// The type is recursive and thus theoretical maximum size is infinite.
53    ///
54    /// Simple type in which this triggers is `struct Rec(Option<Box<Rec>>)`.
55    Recursive,
56
57    /// Some of the declared types were lacking definition making it impossible
58    /// to calculate the size.
59    MissingDefinition(Declaration),
60}
61
62/// Implementation of [`BorshSchema::max_serialized_size`].
63fn max_serialized_size_impl<'a>(
64    count: NonZeroUsize,
65    declaration: &'a str,
66    schema: &'a BorshSchemaContainer,
67    stack: &mut Vec<&'a str>,
68) -> Result<usize, Error> {
69    use core::convert::TryFrom;
70
71    /// Maximum number of elements in a vector or length of a string which can
72    /// be serialised.
73    const MAX_LEN: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(u32::MAX as usize) };
74
75    fn add(x: usize, y: usize) -> Result<usize, Error> {
76        x.checked_add(y).ok_or(Error::Overflow)
77    }
78
79    fn mul(x: NonZeroUsize, y: usize) -> Result<usize, Error> {
80        x.get().checked_mul(y).ok_or(Error::Overflow)
81    }
82
83    /// Calculates max serialised size of a tuple with given members.
84    fn tuple<'a>(
85        count: NonZeroUsize,
86        elements: impl core::iter::IntoIterator<Item = &'a Declaration>,
87        schema: &'a BorshSchemaContainer,
88        stack: &mut Vec<&'a str>,
89    ) -> Result<usize, Error> {
90        let mut sum: usize = 0;
91        for el in elements {
92            sum = add(sum, max_serialized_size_impl(ONE, el, schema, stack)?)?;
93        }
94        mul(count, sum)
95    }
96
97    if stack.contains(&declaration) {
98        return Err(Error::Recursive);
99    }
100    stack.push(declaration);
101
102    let res = match schema.get_definition(declaration).ok_or(declaration) {
103        Ok(Definition::Primitive(size)) => match size {
104            0 => Ok(0),
105            size => {
106                let count_sizes = usize::from(*size).checked_mul(count.get());
107                count_sizes.ok_or(Error::Overflow)
108            }
109        },
110        Ok(Definition::Sequence {
111            length_width,
112            length_range,
113            elements,
114        }) => {
115            // Assume sequence has the maximum number of elements.
116            let max_len = *length_range.end();
117            let sz = match usize::try_from(max_len).map(NonZeroUsize::new) {
118                Ok(Some(max_len)) => max_serialized_size_impl(max_len, elements, schema, stack)?,
119                Ok(None) => 0,
120                Err(_) if is_zero_size_impl(elements, schema, stack)? => 0,
121                Err(_) => return Err(Error::Overflow),
122            };
123            mul(count, add(sz, usize::from(*length_width))?)
124        }
125
126        Ok(Definition::Enum {
127            tag_width,
128            variants,
129        }) => {
130            let mut max = 0;
131            for (_, _, variant) in variants {
132                let sz = max_serialized_size_impl(ONE, variant, schema, stack)?;
133                max = max.max(sz);
134            }
135            add(max, usize::from(*tag_width))
136        }
137
138        // Tuples and structs sum sizes of all the members.
139        Ok(Definition::Tuple { elements }) => tuple(count, elements, schema, stack),
140        Ok(Definition::Struct { fields }) => match fields {
141            Fields::NamedFields(fields) => {
142                tuple(count, fields.iter().map(|(_, field)| field), schema, stack)
143            }
144            Fields::UnnamedFields(fields) => tuple(count, fields, schema, stack),
145            Fields::Empty => Ok(0),
146        },
147
148        Err(declaration) => Err(Error::MissingDefinition(declaration.to_string())),
149    }?;
150
151    stack.pop();
152    Ok(res)
153}
154
155/// Checks whether given declaration schema serialises to an empty string.
156///
157/// This is used by [`BorshSchemaContainer::max_serialized_size`] to handle weird types
158/// such as `[[[(); u32::MAX]; u32::MAX]; u32::MAX]` which serialises to an
159/// empty string even though its number of elements overflows `usize`.
160///
161/// Error value means that the method has been called recursively.
162/// A recursive type either has no exit, so it cannot be instantiated
163/// or it uses `Definiotion::Enum` or `Definition::Sequence` to exit from recursion
164/// which make it non-zero size
165pub(super) fn is_zero_size(
166    declaration: &Declaration,
167    schema: &BorshSchemaContainer,
168) -> Result<bool, ZeroSizeError> {
169    let mut stack = Vec::new();
170    is_zero_size_impl(declaration, schema, &mut stack)
171}
172
173#[derive(Debug, PartialEq, Eq)]
174pub(super) enum ZeroSizeError {
175    Recursive,
176    MissingDefinition(Declaration),
177}
178
179impl From<ZeroSizeError> for Error {
180    fn from(value: ZeroSizeError) -> Self {
181        match value {
182            ZeroSizeError::Recursive => Self::Recursive,
183            ZeroSizeError::MissingDefinition(declaration) => Self::MissingDefinition(declaration),
184        }
185    }
186}
187
188fn is_zero_size_impl<'a>(
189    declaration: &'a str,
190    schema: &'a BorshSchemaContainer,
191    stack: &mut Vec<&'a str>,
192) -> Result<bool, ZeroSizeError> {
193    fn all<'a, T: 'a>(
194        iter: impl Iterator<Item = T>,
195        f_key: impl Fn(&T) -> &'a Declaration,
196        schema: &'a BorshSchemaContainer,
197        stack: &mut Vec<&'a str>,
198    ) -> Result<bool, ZeroSizeError> {
199        for element in iter {
200            let declaration = f_key(&element);
201            if !is_zero_size_impl(declaration.as_str(), schema, stack)? {
202                return Ok(false);
203            }
204        }
205        Ok(true)
206    }
207
208    if stack.contains(&declaration) {
209        return Err(ZeroSizeError::Recursive);
210    }
211    stack.push(declaration);
212
213    let res = match schema.get_definition(declaration).ok_or(declaration) {
214        Ok(Definition::Primitive(size)) => *size == 0,
215        Ok(Definition::Sequence {
216            length_width,
217            length_range,
218            elements,
219        }) => {
220            if *length_width == 0 {
221                // zero-sized array
222                if length_range.clone().count() == 1 && *length_range.start() == 0 {
223                    return Ok(true);
224                }
225                if is_zero_size_impl(elements.as_str(), schema, stack)? {
226                    return Ok(true);
227                }
228            }
229            false
230        }
231        Ok(Definition::Tuple { elements }) => all(elements.iter(), |key| *key, schema, stack)?,
232        Ok(Definition::Enum {
233            tag_width: 0,
234            variants,
235        }) => all(
236            variants.iter(),
237            |(_variant_discrim, _variant_name, declaration)| declaration,
238            schema,
239            stack,
240        )?,
241        Ok(Definition::Enum { .. }) => false,
242        Ok(Definition::Struct { fields }) => match fields {
243            Fields::NamedFields(fields) => all(
244                fields.iter(),
245                |(_field_name, declaration)| declaration,
246                schema,
247                stack,
248            )?,
249            Fields::UnnamedFields(fields) => {
250                all(fields.iter(), |declaration| declaration, schema, stack)?
251            }
252            Fields::Empty => true,
253        },
254
255        Err(declaration) => {
256            return Err(ZeroSizeError::MissingDefinition(declaration.into()));
257        }
258    };
259    stack.pop();
260    Ok(res)
261}
262
263#[cfg(test)]
264mod tests {
265    use super::*;
266
267    // this is not integration test module, so can use __private for ease of imports;
268    // it cannot be made integration, as it tests `is_zero_size` function, chosen to be non-pub
269    use crate::__private::maybestd::{boxed::Box, string::ToString};
270
271    #[test]
272    fn test_is_zero_size_recursive_check_bypassed() {
273        use crate as borsh;
274
275        #[derive(::borsh_derive::BorshSchema)]
276        struct RecursiveExitSequence(Vec<RecursiveExitSequence>);
277
278        let schema = BorshSchemaContainer::for_type::<RecursiveExitSequence>();
279        assert_eq!(Ok(false), is_zero_size(schema.declaration(), &schema));
280    }
281
282    #[test]
283    fn test_is_zero_size_recursive_check_err() {
284        use crate as borsh;
285
286        #[derive(::borsh_derive::BorshSchema)]
287        struct RecursiveNoExitStructUnnamed(Box<RecursiveNoExitStructUnnamed>);
288
289        let schema = BorshSchemaContainer::for_type::<RecursiveNoExitStructUnnamed>();
290        assert_eq!(
291            Err(ZeroSizeError::Recursive),
292            is_zero_size(schema.declaration(), &schema)
293        );
294    }
295}
borsh/schema/container_ext/max_size.rs

borsh/schema/container_ext/
max_size.rs
