brillig/
lengths.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
use std::{
    iter::Sum,
    ops::{Add, AddAssign, Div, Mul},
};

use serde::{Deserialize, Serialize};

/// Represents the length of an array or vector as seen from a user's perspective.
/// For example in the array `[(u8, u16, [u32; 4]); 8]`, the semantic length is 8.
#[derive(Debug, Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Serialize, Deserialize, Hash)]
pub struct SemanticLength(pub u32);

impl SemanticLength {
    pub fn to_usize(self) -> usize {
        assert_usize(self.0)
    }
}

impl Add<SemanticLength> for SemanticLength {
    type Output = SemanticLength;

    /// Computes the sum of two semantic lengths.
    fn add(self, rhs: SemanticLength) -> Self::Output {
        SemanticLength(self.0 + rhs.0)
    }
}

impl AddAssign for SemanticLength {
    /// Adds another semantic length to this one.
    fn add_assign(&mut self, rhs: Self) {
        self.0 += rhs.0;
    }
}

impl Mul<ElementTypesLength> for SemanticLength {
    type Output = SemiFlattenedLength;

    /// Computes the semi-flattened length by multiplying the semantic length
    /// by the element types length.
    fn mul(self, rhs: ElementTypesLength) -> Self::Output {
        SemiFlattenedLength(self.0 * rhs.0)
    }
}

impl std::fmt::Display for SemanticLength {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

/// Represents the number of types of a single element inside a vector or array, without
/// taking into account the vector or array length.
/// For example, in the array `[(u8, u16, [u32; 4]); 8]`, the element types length is 3:
/// 1. u8
/// 2. u16
/// 3. [u32; 4]
#[derive(Debug, Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Serialize, Deserialize, Hash)]
pub struct ElementTypesLength(pub u32);

impl ElementTypesLength {
    pub fn to_usize(self) -> usize {
        assert_usize(self.0)
    }
}

impl Mul<SemanticLength> for ElementTypesLength {
    type Output = SemiFlattenedLength;

    /// Computes the semi-flattened length by multiplying the semantic length
    /// by the element types length.
    fn mul(self, rhs: SemanticLength) -> Self::Output {
        SemiFlattenedLength(self.0 * rhs.0)
    }
}

impl Mul<ElementsFlattenedLength> for SemanticLength {
    type Output = FlattenedLength;

    /// Computes the flattened length by multiplying the semantic length
    /// by the elements flattened length.
    fn mul(self, rhs: ElementsFlattenedLength) -> Self::Output {
        FlattenedLength(self.0 * rhs.0)
    }
}

impl std::fmt::Display for ElementTypesLength {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

/// Represents the number of value/memory slots required to represent an array or vector.
/// The semi-flattened length can be computed by multiplying the semantic length by
/// the element types length.
///
/// For example in the array `[(u8, u16, [u32; 4]); 8]`:
/// - The semantic length is 8
/// - The element types length is 3
/// - The semi-flattened length is 24 (8 * 3)
///
/// The reason the semi-flattened length is required, and different than the semantic length,
/// is that in our SSA tuples are flattened so the number of value slots needed to represent an
/// array is different than the semantic length
///
/// Note that this is different from the fully flattened length, which would be 8 * (1 + 1 + 4) = 48.
#[derive(Debug, Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Serialize, Deserialize, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub struct SemiFlattenedLength(pub u32);

impl SemiFlattenedLength {
    pub fn to_usize(self) -> usize {
        assert_usize(self.0)
    }
}

impl std::fmt::Display for SemiFlattenedLength {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl Div<ElementTypesLength> for SemiFlattenedLength {
    type Output = SemanticLength;

    fn div(self, rhs: ElementTypesLength) -> Self::Output {
        if self.0 % rhs.0 != 0 {
            panic!(
                "Division of SemiFlattenedLength {} by ElementTypesLength {} has remainder",
                self.0, rhs.0
            );
        }
        SemanticLength(self.0 / rhs.0)
    }
}

/// Represents the total number of fields required to represent a single entry of an array or vector.
/// For example in the array `[(u8, u16, [u32; 4]); 8]` the elements flattened length is 6:
/// 1. u8 (1)
/// 2. u16 (1)
/// 3. [u32; 4] (4)
#[derive(Debug, Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Serialize, Deserialize, Hash)]
pub struct ElementsFlattenedLength(pub u32);

impl ElementsFlattenedLength {
    pub fn to_usize(self) -> usize {
        assert_usize(self.0)
    }
}

impl std::fmt::Display for ElementsFlattenedLength {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl Mul<SemanticLength> for ElementsFlattenedLength {
    type Output = FlattenedLength;

    /// Computes the flattened length by multiplying the semantic length
    /// by the elements flattened length.
    fn mul(self, rhs: SemanticLength) -> Self::Output {
        FlattenedLength(self.0 * rhs.0)
    }
}

impl From<FlattenedLength> for ElementsFlattenedLength {
    /// Assumes this flattened length represents a single entry in an array or vector,
    fn from(flattened_length: FlattenedLength) -> Self {
        Self(flattened_length.0)
    }
}

/// Represents the total number of fields required to represent the entirety of an array or vector.
/// For example in the array `[(u8, u16, [u32; 4]); 8]` the flattened length is 48: 8 * (1 + 1 + 4).
#[derive(Debug, Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Serialize, Deserialize, Hash)]
pub struct FlattenedLength(pub u32);

impl FlattenedLength {
    pub fn to_usize(self) -> usize {
        assert_usize(self.0)
    }
}

impl std::fmt::Display for FlattenedLength {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl Add for FlattenedLength {
    type Output = FlattenedLength;

    fn add(self, rhs: Self) -> Self::Output {
        FlattenedLength(self.0 + rhs.0)
    }
}

impl AddAssign for FlattenedLength {
    fn add_assign(&mut self, rhs: Self) {
        self.0 += rhs.0;
    }
}

impl Sum for FlattenedLength {
    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.fold(FlattenedLength(0), |acc, x| acc + x)
    }
}

impl Div<ElementsFlattenedLength> for FlattenedLength {
    type Output = SemanticLength;

    fn div(self, rhs: ElementsFlattenedLength) -> Self::Output {
        if self.0 % rhs.0 != 0 {
            panic!(
                "Division of FlattenedLength {} by ElementsFlattenedLength {} has remainder",
                self.0, rhs.0
            );
        }

        SemanticLength(self.0 / rhs.0)
    }
}

/// Converts a u32 value to usize, panicking if the conversion fails.
fn assert_usize(value: u32) -> usize {
    value.try_into().expect("Failed conversion from u32 to usize")
}