tcp/
seq.rs

Help
1/// A sequence number. We use a wrapper around a `u32` to prevent mistakes involving adding or
2/// comparing sequence numbers.
3#[derive(Copy, Clone, PartialEq, Eq)]
4pub(crate) struct Seq(u32);
5
6// We don't implement `From<u32>` or `Deref` since it makes it easier to accidentally mix up
7// operating on a `u32` instead of a `Seq`. For example this can cause bugs if accidentally adding
8// using `<u32 as Add<u32>>` instead of `<Seq as Add<u32>>`, which has a different wrapping
9// behaviour. We don't implement `PartialOrd` or `Ord` since there is no ordering relation between
10// arbitrary sequence numbers modulo 2^32.
11static_assertions::assert_not_impl_any!(Seq: PartialOrd, Ord, From<u32>, std::ops::Deref);
12
13impl Seq {
14    #[inline]
15    pub fn new(x: u32) -> Self {
16        Self(x)
17    }
18}
19
20impl std::fmt::Debug for Seq {
21    #[inline]
22    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
23        self.0.fmt(f)
24    }
25}
26
27impl std::fmt::Display for Seq {
28    #[inline]
29    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
30        self.0.fmt(f)
31    }
32}
33
34impl From<Seq> for u32 {
35    #[inline]
36    fn from(x: Seq) -> Self {
37        x.0
38    }
39}
40
41impl std::ops::Add<u32> for Seq {
42    type Output = Self;
43
44    fn add(self, offset: u32) -> Self::Output {
45        Self::new(self.0.wrapping_add(offset))
46    }
47}
48
49impl std::ops::Sub<u32> for Seq {
50    type Output = Self;
51
52    fn sub(self, offset: u32) -> Self::Output {
53        Self::new(self.0.wrapping_sub(offset))
54    }
55}
56
57impl std::ops::Sub for Seq {
58    type Output = u32;
59
60    fn sub(self, other: Self) -> Self::Output {
61        self.0.wrapping_sub(other.0)
62    }
63}
64
65impl std::ops::AddAssign<u32> for Seq {
66    fn add_assign(&mut self, offset: u32) {
67        self.0 = self.0.wrapping_add(offset);
68    }
69}
70
71impl std::ops::SubAssign<u32> for Seq {
72    fn sub_assign(&mut self, offset: u32) {
73        self.0 = self.0.wrapping_sub(offset);
74    }
75}
76
77/// A half-open range of sequence numbers modulo 2<sup>32</sup> bounded inclusively by `start` and
78/// exclusively by `end`. The starting position can be greater than the ending position.
79#[derive(Copy, Clone, PartialEq, Eq)]
80pub(crate) struct SeqRange {
81    /// Inclusive starting position.
82    pub start: Seq,
83    /// Exclusive ending position.
84    pub end: Seq,
85}
86
87impl std::fmt::Debug for SeqRange {
88    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
89        self.start.fmt(f)?;
90        write!(f, "..")?;
91        self.end.fmt(f)?;
92        Ok(())
93    }
94}
95
96impl SeqRange {
97    #[inline]
98    pub fn new(start: Seq, end: Seq) -> Self {
99        Self { start, end }
100    }
101
102    #[inline]
103    pub fn len(&self) -> u32 {
104        self.end - self.start
105    }
106
107    #[inline]
108    pub fn is_empty(&self) -> bool {
109        self.len() == 0
110    }
111
112    /// Returns `true` if the sequence number is contained within this half-open range.
113    #[inline]
114    pub fn contains(&self, seq: Seq) -> bool {
115        SeqRange::new(self.start, seq).len() < self.len()
116    }
117
118    /// Returns the intersecting range if there is a single intersecting range. Returns `None` if
119    /// there is no intersection, or if there are two intersections. A range will always intersect
120    /// with itself, which also holds for empty ranges. An empty range will intersect with a
121    /// non-empty range if the empty range is contained within the non-empty range.
122    pub fn intersection(&self, other: &Self) -> Option<SeqRange> {
123        let a = self;
124        let b = other;
125
126        // handle empty ranges
127        match (a.is_empty(), b.is_empty()) {
128            // both ranges are empty, so they only intersect if they're equal
129            (true, true) => return (a == b).then_some(*a),
130            // A is empty, so they intersect if the start of A is contained within B
131            (true, false) => return b.contains(a.start).then_some(*a),
132            // B is empty, so they intersect if the start of B is contained within A
133            (false, true) => return a.contains(b.start).then_some(*b),
134            // neither range is empty, so continue to find a non-empty range
135            (false, false) => {}
136        }
137
138        // check if edges of A are in B
139        let a_0_in_b = b.contains(a.start);
140        let a_1_in_b = b.contains(a.end - 1);
141
142        match (a_0_in_b, a_1_in_b) {
143            // intersection from left edge of A to right edge of B
144            (true, false) => Some(Self::new(a.start, b.end)),
145            // intersection from left edge of B to right edge of A
146            (false, true) => Some(Self::new(b.start, a.end)),
147            (true, true) => {
148                if a.start - b.start < a.end - b.start {
149                    // A wholly contained within B
150                    Some(*a)
151                } else {
152                    // intersection from left edge of A to right edge of B, and intersection from
153                    // left edge of B to right edge of A
154                    None
155                }
156            }
157            (false, false) => {
158                // check if edges of B are in A
159                let b_0_in_a = a.contains(b.start);
160                let b_1_in_a = a.contains(b.end - 1);
161
162                if b_0_in_a && b_1_in_a {
163                    // B wholly contained within A
164                    Some(*b)
165                } else {
166                    // no intersection
167                    None
168                }
169            }
170        }
171    }
172}
173
174#[cfg(test)]
175mod tests {
176    use super::*;
177
178    // helper to make the tests fit on a single line
179    fn range(start: u32, end: u32) -> SeqRange {
180        SeqRange::new(Seq::new(start), Seq::new(end))
181    }
182
183    // helper to make the tests fit on a single line
184    fn seq(val: u32) -> Seq {
185        Seq::new(val)
186    }
187
188    #[test]
189    fn test_range_contains() {
190        // Test that `range` contains (or does not contain) `val`. Tests repeatedly with all offsets
191        // in `offset_range` to make it easier to confirm that it also works across the 32-bit
192        // wrapping point.
193        fn test_range(
194            range: SeqRange,
195            val: Seq,
196            contained: bool,
197            offset_range: std::ops::Range<i32>,
198        ) {
199            for i in offset_range {
200                // negative values will wrap to an equivalent positive offset
201                let i = i as u32;
202
203                let range = SeqRange::new(range.start + i, range.end + i);
204                let val = val + i;
205
206                assert_eq!(range.contains(val), contained);
207
208                if !range.is_empty() {
209                    let reverse_range = SeqRange::new(range.end, range.start);
210                    assert_eq!(reverse_range.contains(val), !contained);
211                }
212            }
213        }
214
215        test_range(range(0, 0), seq(0), false, -10..10);
216        test_range(range(0, 1), seq(0), true, -10..10);
217        test_range(range(0, 1), seq(1), false, -10..10);
218        test_range(range(0, 2), seq(0), true, -10..10);
219        test_range(range(0, 2), seq(1), true, -10..10);
220        test_range(range(0, 2), seq(2), false, -10..10);
221    }
222
223    #[test]
224    fn test_range_intersection() {
225        // Test that the intersection between `a` and `b` is equal to `expected`. Tests repeatedly
226        // with all offsets in `offset_range` to make it easier to confirm that it also works across
227        // the 32-bit wrapping point.
228        fn test_pair(
229            a: SeqRange,
230            b: SeqRange,
231            expected: impl Into<Option<SeqRange>>,
232            offset_range: std::ops::Range<i32>,
233        ) {
234            let expected = expected.into();
235
236            for i in offset_range {
237                // negative values will wrap to an equivalent positive offset
238                let i = i as u32;
239
240                // add the offset to the ranges
241                let a = SeqRange::new(a.start + i, a.end + i);
242                let b = SeqRange::new(b.start + i, b.end + i);
243                let expected = expected.map(|x| SeqRange::new(x.start + i, x.end + i));
244
245                // make sure it's symmetric
246                assert_eq!(a.intersection(&b), expected);
247                assert_eq!(b.intersection(&a), expected);
248            }
249        }
250
251        test_pair(range(0, 0), range(0, 0), range(0, 0), -10..10);
252        test_pair(range(0, 0), range(1, 1), None, -10..10);
253        test_pair(range(0, 0), range(0, 1), range(0, 0), -10..10);
254        test_pair(range(1, 1), range(0, 1), None, -10..10);
255        test_pair(range(0, 1), range(1, 2), None, -10..10);
256        test_pair(range(0, 2), range(1, 2), range(1, 2), -10..10);
257        test_pair(range(0, 2), range(0, 1), range(0, 1), -10..10);
258        test_pair(range(10, 12), range(10, 12), range(10, 12), -100..100);
259        test_pair(range(10, 12), range(12, 10), None, -100..100);
260
261        // second test intersects twice (16-20 and 10-12), which returns a `None`
262        test_pair(range(10, 20), range(12, 16), range(12, 16), -100..100);
263        test_pair(range(10, 20), range(16, 12), None, -100..100);
264    }
265}
tcp/seq.rs

tcp/
seq.rs
