brillig/
lengths.rs

1use std::{
2    iter::Sum,
3    ops::{Add, AddAssign, Div, Mul},
4};
5
6use msgpack_tagged::MsgpackTagged;
7use serde::{Deserialize, Serialize};
8
9/// Represents the length of an array or vector as seen from a user's perspective.
10/// For example in the array `[(u8, u16, [u32; 4]); 8]`, the semantic length is 8.
11#[derive(Debug, Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Hash)]
12#[derive(Serialize, Deserialize, MsgpackTagged)]
13pub struct SemanticLength(pub u32);
14
15impl SemanticLength {
16    pub fn to_usize(self) -> usize {
17        assert_usize(self.0)
18    }
19}
20
21impl Add<SemanticLength> for SemanticLength {
22    type Output = SemanticLength;
23
24    /// Computes the sum of two semantic lengths.
25    fn add(self, rhs: SemanticLength) -> Self::Output {
26        SemanticLength(checked_add(self.0, rhs.0))
27    }
28}
29
30impl AddAssign for SemanticLength {
31    /// Adds another semantic length to this one.
32    fn add_assign(&mut self, rhs: Self) {
33        self.0 = checked_add(self.0, rhs.0);
34    }
35}
36
37impl Mul<ElementTypesLength> for SemanticLength {
38    type Output = SemiFlattenedLength;
39
40    /// Computes the semi-flattened length by multiplying the semantic length
41    /// by the element types length.
42    fn mul(self, rhs: ElementTypesLength) -> Self::Output {
43        SemiFlattenedLength(checked_mul(self.0, rhs.0))
44    }
45}
46
47impl std::fmt::Display for SemanticLength {
48    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
49        write!(f, "{}", self.0)
50    }
51}
52
53/// Represents the number of types of a single element inside a vector or array, without
54/// taking into account the vector or array length.
55/// For example, in the array `[(u8, u16, [u32; 4]); 8]`, the element types length is 3:
56/// 1. u8
57/// 2. u16
58/// 3. [u32; 4]
59#[derive(Debug, Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Serialize, Deserialize, Hash)]
60pub struct ElementTypesLength(pub u32);
61
62impl ElementTypesLength {
63    pub fn to_usize(self) -> usize {
64        assert_usize(self.0)
65    }
66}
67
68impl Mul<SemanticLength> for ElementTypesLength {
69    type Output = SemiFlattenedLength;
70
71    /// Computes the semi-flattened length by multiplying the semantic length
72    /// by the element types length.
73    fn mul(self, rhs: SemanticLength) -> Self::Output {
74        SemiFlattenedLength(checked_mul(self.0, rhs.0))
75    }
76}
77
78impl Mul<ElementsFlattenedLength> for SemanticLength {
79    type Output = FlattenedLength;
80
81    /// Computes the flattened length by multiplying the semantic length
82    /// by the elements flattened length.
83    fn mul(self, rhs: ElementsFlattenedLength) -> Self::Output {
84        FlattenedLength(checked_mul(self.0, rhs.0))
85    }
86}
87
88impl std::fmt::Display for ElementTypesLength {
89    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
90        write!(f, "{}", self.0)
91    }
92}
93
94/// Represents the number of value/memory slots required to represent an array or vector.
95/// The semi-flattened length can be computed by multiplying the semantic length by
96/// the element types length.
97///
98/// For example in the array `[(u8, u16, [u32; 4]); 8]`:
99/// - The semantic length is 8
100/// - The element types length is 3
101/// - The semi-flattened length is 24 (8 * 3)
102///
103/// The reason the semi-flattened length is required, and different than the semantic length,
104/// is that in our SSA tuples are flattened so the number of value slots needed to represent an
105/// array is different than the semantic length
106///
107/// Note that this is different from the fully flattened length, which would be 8 * (1 + 1 + 4) = 48.
108#[derive(Debug, Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Hash)]
109#[derive(Serialize, Deserialize, MsgpackTagged)]
110#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
111pub struct SemiFlattenedLength(pub u32);
112
113impl SemiFlattenedLength {
114    pub fn to_usize(self) -> usize {
115        assert_usize(self.0)
116    }
117}
118
119impl std::fmt::Display for SemiFlattenedLength {
120    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
121        write!(f, "{}", self.0)
122    }
123}
124
125impl Div<ElementTypesLength> for SemiFlattenedLength {
126    type Output = SemanticLength;
127
128    fn div(self, rhs: ElementTypesLength) -> Self::Output {
129        if !self.0.is_multiple_of(rhs.0) {
130            panic!(
131                "Division of SemiFlattenedLength {} by ElementTypesLength {} has remainder",
132                self.0, rhs.0
133            );
134        }
135        SemanticLength(self.0 / rhs.0)
136    }
137}
138
139/// Represents the total number of fields required to represent a single entry of an array or vector.
140/// For example in the array `[(u8, u16, [u32; 4]); 8]` the elements flattened length is 6:
141/// 1. u8 (1)
142/// 2. u16 (1)
143/// 3. [u32; 4] (4)
144#[derive(Debug, Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Serialize, Deserialize, Hash)]
145pub struct ElementsFlattenedLength(pub u32);
146
147impl ElementsFlattenedLength {
148    pub fn to_usize(self) -> usize {
149        assert_usize(self.0)
150    }
151}
152
153impl std::fmt::Display for ElementsFlattenedLength {
154    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
155        write!(f, "{}", self.0)
156    }
157}
158
159impl Mul<SemanticLength> for ElementsFlattenedLength {
160    type Output = FlattenedLength;
161
162    /// Computes the flattened length by multiplying the semantic length
163    /// by the elements flattened length.
164    fn mul(self, rhs: SemanticLength) -> Self::Output {
165        FlattenedLength(checked_mul(self.0, rhs.0))
166    }
167}
168
169impl From<FlattenedLength> for ElementsFlattenedLength {
170    /// Assumes this flattened length represents a single entry in an array or vector,
171    fn from(flattened_length: FlattenedLength) -> Self {
172        Self(flattened_length.0)
173    }
174}
175
176/// Represents the total number of fields required to represent the entirety of an array or vector.
177/// For example in the array `[(u8, u16, [u32; 4]); 8]` the flattened length is 48: 8 * (1 + 1 + 4).
178#[derive(Debug, Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Serialize, Deserialize, Hash)]
179pub struct FlattenedLength(pub u32);
180
181impl FlattenedLength {
182    pub fn to_usize(self) -> usize {
183        assert_usize(self.0)
184    }
185}
186
187impl std::fmt::Display for FlattenedLength {
188    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
189        write!(f, "{}", self.0)
190    }
191}
192
193impl Add for FlattenedLength {
194    type Output = FlattenedLength;
195
196    fn add(self, rhs: Self) -> Self::Output {
197        FlattenedLength(checked_add(self.0, rhs.0))
198    }
199}
200
201impl AddAssign for FlattenedLength {
202    fn add_assign(&mut self, rhs: Self) {
203        self.0 = checked_add(self.0, rhs.0);
204    }
205}
206
207impl Sum for FlattenedLength {
208    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
209        iter.fold(FlattenedLength(0), |acc, x| acc + x)
210    }
211}
212
213impl Div<ElementsFlattenedLength> for FlattenedLength {
214    type Output = SemanticLength;
215
216    fn div(self, rhs: ElementsFlattenedLength) -> Self::Output {
217        if !self.0.is_multiple_of(rhs.0) {
218            panic!(
219                "Division of FlattenedLength {} by ElementsFlattenedLength {} has remainder",
220                self.0, rhs.0
221            );
222        }
223
224        SemanticLength(self.0 / rhs.0)
225    }
226}
227
228/// Multiplies two lengths, panicking rather than wrapping.
229///
230/// A length describes how many slots a value occupies. Wrapping produces a length with no relation
231/// to the type it was derived from — `[[u8; 65536]; 65536]` becomes a zero-length array — which the
232/// consumers of these types have no way to detect.
233fn checked_mul(lhs: u32, rhs: u32) -> u32 {
234    lhs.checked_mul(rhs).unwrap_or_else(|| panic!("Length overflow multiplying {lhs} by {rhs}"))
235}
236
237/// Adds two lengths, panicking rather than wrapping. See [`checked_mul`].
238fn checked_add(lhs: u32, rhs: u32) -> u32 {
239    lhs.checked_add(rhs).unwrap_or_else(|| panic!("Length overflow adding {rhs} to {lhs}"))
240}
241
242/// Converts a u32 value to usize, panicking if the conversion fails.
243fn assert_usize(value: u32) -> usize {
244    value.try_into().expect("Failed conversion from u32 to usize")
245}
246
247#[cfg(test)]
248mod tests {
249    use super::*;
250
251    /// A wrapped length is a slot count with no relation to the type it came from:
252    /// `[[u8; 65536]; 65536]` needs 2^32 slots, which is 0 modulo 2^32, so the array looks empty.
253    #[test]
254    #[should_panic(expected = "Length overflow multiplying 65536 by 65536")]
255    fn multiplying_lengths_does_not_wrap() {
256        let _ = ElementsFlattenedLength(1 << 16) * SemanticLength(1 << 16);
257    }
258
259    #[test]
260    #[should_panic(expected = "Length overflow adding")]
261    fn adding_lengths_does_not_wrap() {
262        let _ = FlattenedLength(u32::MAX) + FlattenedLength(1);
263    }
264
265    #[test]
266    fn multiplying_lengths_in_range_is_unchanged() {
267        assert_eq!(
268            ElementsFlattenedLength(6) * SemanticLength(8),
269            FlattenedLength(48),
270            "[(u8, u16, [u32; 4]); 8] occupies 48 slots"
271        );
272    }
273
274    #[test]
275    fn flattened_length_divides_evenly_by_elements_flattened_length() {
276        assert_eq!(FlattenedLength(6) / ElementsFlattenedLength(2), SemanticLength(3));
277    }
278
279    #[test]
280    #[should_panic(
281        expected = "Division of FlattenedLength 5 by ElementsFlattenedLength 2 has remainder"
282    )]
283    fn flattened_length_division_with_remainder_panics() {
284        let _ = FlattenedLength(5) / ElementsFlattenedLength(2);
285    }
286
287    #[test]
288    fn semi_flattened_length_divides_evenly_by_element_types_length() {
289        assert_eq!(SemiFlattenedLength(6) / ElementTypesLength(3), SemanticLength(2));
290    }
291
292    #[test]
293    #[should_panic(
294        expected = "Division of SemiFlattenedLength 7 by ElementTypesLength 3 has remainder"
295    )]
296    fn semi_flattened_length_division_with_remainder_panics() {
297        let _ = SemiFlattenedLength(7) / ElementTypesLength(3);
298    }
299}
brillig/lengths.rs

brillig/
lengths.rs
