commonware_utils/
range.rs

1//! Utilities for linear ranges and cyclic spans.
2
3use bytes::BufMut;
4use commonware_codec::{Buf, BufsMut, EncodeSize, Error as CodecError, MaxEncodeSize, Read, Write};
5use commonware_macros::stability;
6#[stability(ALPHA)]
7use core::ops::{
8    Bound::{Excluded, Included, Unbounded},
9    RangeBounds,
10};
11use core::{fmt, ops::Range};
12
13/// Whether `key` is in the cyclic span described by the current bounds of `span`.
14///
15/// When both endpoints are bounded, a start greater than the end wraps around the key
16/// domain. Equal endpoints span the entire domain, except for the endpoint itself when
17/// both bounds exclude it. Unbounded endpoints use ordinary linear range semantics.
18///
19/// # Examples
20///
21/// ```
22/// use commonware_utils::range::contains_cyclic;
23/// use core::ops::Bound::{Excluded, Included};
24///
25/// assert!(contains_cyclic(2..6, &2));
26/// assert!(!contains_cyclic(2..6, &6));
27/// assert!(contains_cyclic((Excluded(2), Included(6)), &6));
28/// assert!(contains_cyclic(6..2, &0));
29/// assert!(contains_cyclic(3..3, &9));
30/// ```
31#[stability(ALPHA)]
32pub fn contains_cyclic<K: Ord + ?Sized>(span: impl RangeBounds<K>, key: &K) -> bool {
33    let start = span.start_bound();
34    let end = span.end_bound();
35    let after_start = match start {
36        Included(start) => key >= start,
37        Excluded(start) => key > start,
38        Unbounded => true,
39    };
40    let before_end = match end {
41        Included(end) => key <= end,
42        Excluded(end) => key < end,
43        Unbounded => true,
44    };
45    match (start, end) {
46        (Included(start) | Excluded(start), Included(end) | Excluded(end)) if start >= end => {
47            after_start || before_end
48        }
49        _ => after_start && before_end,
50    }
51}
52
53/// Error returned when attempting to create a non-empty range from an empty range.
54#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
55#[error("range is empty")]
56pub struct EmptyRange;
57
58/// A non-empty [`Range`] (`start..end`) where `start < end` is guaranteed.
59#[derive(Clone, PartialEq, Eq, Hash)]
60pub struct NonEmptyRange<Idx>(Range<Idx>);
61
62impl<Idx: fmt::Debug> fmt::Debug for NonEmptyRange<Idx> {
63    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
64        self.0.fmt(f)
65    }
66}
67
68impl<Idx: PartialOrd> NonEmptyRange<Idx> {
69    /// Creates a `NonEmptyRange` if `start < end`.
70    pub fn new(range: Range<Idx>) -> Result<Self, EmptyRange> {
71        (range.start < range.end)
72            .then_some(Self(range))
73            .ok_or(EmptyRange)
74    }
75}
76
77impl<Idx: Copy> NonEmptyRange<Idx> {
78    /// Returns the start of the range.
79    pub const fn start(&self) -> Idx {
80        self.0.start
81    }
82
83    /// Returns the end of the range (exclusive).
84    pub const fn end(&self) -> Idx {
85        self.0.end
86    }
87}
88
89impl<Idx: PartialOrd> TryFrom<Range<Idx>> for NonEmptyRange<Idx> {
90    type Error = EmptyRange;
91
92    fn try_from(range: Range<Idx>) -> Result<Self, Self::Error> {
93        Self::new(range)
94    }
95}
96
97impl<Idx> From<NonEmptyRange<Idx>> for Range<Idx> {
98    fn from(r: NonEmptyRange<Idx>) -> Self {
99        r.0
100    }
101}
102
103impl<Idx> IntoIterator for NonEmptyRange<Idx>
104where
105    Range<Idx>: Iterator,
106{
107    type Item = <Range<Idx> as Iterator>::Item;
108    type IntoIter = Range<Idx>;
109
110    fn into_iter(self) -> Self::IntoIter {
111        self.0
112    }
113}
114
115impl<Idx: Write> Write for NonEmptyRange<Idx> {
116    #[inline]
117    fn write(&self, buf: &mut impl BufMut) {
118        self.0.start.write(buf);
119        self.0.end.write(buf);
120    }
121
122    #[inline]
123    fn write_bufs(&self, buf: &mut impl BufsMut) {
124        self.0.start.write_bufs(buf);
125        self.0.end.write_bufs(buf);
126    }
127}
128
129impl<Idx: EncodeSize> EncodeSize for NonEmptyRange<Idx> {
130    #[inline]
131    fn encode_size(&self) -> usize {
132        self.0.start.encode_size() + self.0.end.encode_size()
133    }
134
135    #[inline]
136    fn encode_inline_size(&self) -> usize {
137        self.0.start.encode_inline_size() + self.0.end.encode_inline_size()
138    }
139}
140
141impl<Idx: MaxEncodeSize> MaxEncodeSize for NonEmptyRange<Idx> {
142    const MAX_ENCODE_SIZE: usize = 2 * Idx::MAX_ENCODE_SIZE;
143}
144
145impl<Idx: Read + PartialOrd> Read for NonEmptyRange<Idx> {
146    type Cfg = Idx::Cfg;
147
148    #[inline]
149    fn read_cfg(buf: &mut impl Buf, cfg: &Self::Cfg) -> Result<Self, CodecError> {
150        let start = Idx::read_cfg(buf, cfg)?;
151        let end = Idx::read_cfg(buf, cfg)?;
152        if !start.partial_cmp(&end).is_some_and(|o| o.is_lt()) {
153            return Err(CodecError::Invalid("NonEmptyRange", "start must be < end"));
154        }
155        Ok(Self(start..end))
156    }
157}
158
159#[cfg(feature = "arbitrary")]
160impl<'a, Idx: arbitrary::Arbitrary<'a> + Ord> arbitrary::Arbitrary<'a> for NonEmptyRange<Idx> {
161    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
162        let a = Idx::arbitrary(u)?;
163        let b = Idx::arbitrary(u)?;
164        let (start, end) = if a < b {
165            (a, b)
166        } else if b < a {
167            (b, a)
168        } else {
169            return Err(arbitrary::Error::IncorrectFormat);
170        };
171        Ok(Self(start..end))
172    }
173}
174
175/// A macro to create a [`NonEmptyRange`] from a range expression, panicking if the range is empty.
176#[macro_export]
177macro_rules! non_empty_range {
178    ($start:expr, $end:expr) => {
179        $crate::range::NonEmptyRange::new($start..$end).expect("range must be non-empty")
180    };
181}
182
183#[cfg(test)]
184mod tests {
185    use super::*;
186    use commonware_codec::{DecodeExt, Encode};
187
188    #[test]
189    fn test_contains_cyclic_boundaries() {
190        let cases: &[(_, &[u8])] = &[
191            ((Included(2), Excluded(6)), &[2, 3, 4, 5]),
192            ((Excluded(2), Included(6)), &[3, 4, 5, 6]),
193            ((Included(2), Included(6)), &[2, 3, 4, 5, 6]),
194            ((Excluded(2), Excluded(6)), &[3, 4, 5]),
195            ((Included(6), Excluded(2)), &[0, 1, 6, 7]),
196            ((Excluded(6), Included(2)), &[0, 1, 2, 7]),
197            ((Included(6), Included(2)), &[0, 1, 2, 6, 7]),
198            ((Excluded(6), Excluded(2)), &[0, 1, 7]),
199            ((Included(3), Excluded(3)), &[0, 1, 2, 3, 4, 5, 6, 7]),
200            ((Excluded(3), Included(3)), &[0, 1, 2, 3, 4, 5, 6, 7]),
201            ((Included(3), Included(3)), &[0, 1, 2, 3, 4, 5, 6, 7]),
202            ((Excluded(3), Excluded(3)), &[0, 1, 2, 4, 5, 6, 7]),
203            ((Unbounded, Included(3)), &[0, 1, 2, 3]),
204            ((Unbounded, Excluded(3)), &[0, 1, 2]),
205            ((Included(3), Unbounded), &[3, 4, 5, 6, 7]),
206            ((Excluded(3), Unbounded), &[4, 5, 6, 7]),
207            ((Unbounded, Unbounded), &[0, 1, 2, 3, 4, 5, 6, 7]),
208        ];
209        for &(bounds, expected) in cases {
210            let actual: Vec<_> = (0..=7).filter(|key| contains_cyclic(bounds, key)).collect();
211            assert_eq!(actual, expected, "bounds: {bounds:?}");
212        }
213    }
214
215    #[test]
216    #[allow(clippy::reversed_empty_ranges)]
217    fn test_contains_cyclic_extremes() {
218        for key in u8::MIN..=u8::MAX {
219            assert_eq!(contains_cyclic(u8::MAX..u8::MIN, &key), key == u8::MAX);
220            assert_eq!(
221                contains_cyclic((Excluded(u8::MAX), Included(u8::MIN)), &key),
222                key == u8::MIN
223            );
224            assert!(contains_cyclic(u8::MIN..u8::MIN, &key));
225            assert!(contains_cyclic(u8::MAX..u8::MAX, &key));
226            assert!(!contains_cyclic(..u8::MIN, &key));
227            assert!(!contains_cyclic((Excluded(u8::MAX), Unbounded), &key));
228        }
229    }
230
231    #[test]
232    fn test_contains_cyclic_range_syntax() {
233        let start = String::from("a");
234        let end = String::from("c");
235        let key = String::from("b");
236        assert!(contains_cyclic(&start..&end, &key));
237        assert!(!contains_cyclic(&start..&end, &end));
238        assert!(contains_cyclic(&start..=&end, &end));
239        assert!(contains_cyclic(&start.., &key));
240        assert!(!contains_cyclic(..&end, &end));
241        assert!(contains_cyclic(..=&end, &end));
242        assert!(contains_cyclic(.., &key));
243        assert!(contains_cyclic((Excluded(&start), Included(&end)), &end));
244        assert!(contains_cyclic(
245            (Included(start.as_str()), Excluded(end.as_str())),
246            key.as_str()
247        ));
248    }
249
250    #[test]
251    fn test_contains_cyclic_current_bounds() {
252        let mut span = 2..=6;
253        assert_eq!(span.next(), Some(2));
254        assert_eq!(span.next_back(), Some(6));
255        for key in 0..=7 {
256            assert_eq!(contains_cyclic(span.clone(), &key), (3..=5).contains(&key));
257        }
258    }
259
260    #[test]
261    fn test_non_empty_range_valid() {
262        let r = NonEmptyRange::new(0u32..5).unwrap();
263        assert_eq!(r.start(), 0);
264        assert_eq!(r.end(), 5);
265        assert_eq!(Range::from(r), 0..5);
266    }
267
268    #[test]
269    fn test_non_empty_range_single_element() {
270        let r = NonEmptyRange::new(3u32..4).unwrap();
271        assert_eq!(r.start(), 3);
272        assert_eq!(r.end(), 4);
273    }
274
275    #[test]
276    fn test_non_empty_range_empty() {
277        assert_eq!(NonEmptyRange::new(5u32..5), Err(EmptyRange));
278        #[allow(clippy::reversed_empty_ranges)]
279        let reversed = NonEmptyRange::new(5u32..3);
280        assert_eq!(reversed, Err(EmptyRange));
281    }
282
283    #[test]
284    fn test_non_empty_range_into() {
285        let r = NonEmptyRange::new(1u32..10).unwrap();
286        let range: Range<u32> = r.into();
287        assert_eq!(range, 1..10);
288    }
289
290    #[test]
291    fn test_non_empty_range_debug() {
292        let r = NonEmptyRange::new(1u32..5).unwrap();
293        assert_eq!(format!("{r:?}"), "1..5");
294    }
295
296    #[test]
297    fn test_non_empty_range_iter() {
298        let r = NonEmptyRange::new(0u32..4).unwrap();
299        let items: Vec<_> = r.into_iter().collect();
300        assert_eq!(items, vec![0, 1, 2, 3]);
301    }
302
303    #[test]
304    fn test_non_empty_range_encode_decode() {
305        let r = NonEmptyRange::new(10u32..20).unwrap();
306        let encoded = r.encode();
307        let decoded = NonEmptyRange::<u32>::decode(encoded).unwrap();
308        assert_eq!(r, decoded);
309    }
310
311    #[test]
312    fn test_non_empty_range_decode_invalid() {
313        for (start, end) in [(20u32, 10u32), (5, 5)] {
314            let mut buf = Vec::new();
315            buf.extend_from_slice(&start.to_be_bytes());
316            buf.extend_from_slice(&end.to_be_bytes());
317            assert!(matches!(
318                NonEmptyRange::<u32>::decode(buf),
319                Err(CodecError::Invalid("NonEmptyRange", "start must be < end"))
320            ));
321        }
322    }
323
324    #[cfg(feature = "arbitrary")]
325    mod conformance {
326        use super::*;
327        use commonware_codec::conformance::CodecConformance;
328
329        commonware_conformance::conformance_tests! {
330            CodecConformance<NonEmptyRange<u32>>,
331            CodecConformance<NonEmptyRange<u64>>,
332        }
333    }
334}
commonware_utils/range.rs

commonware_utils/
range.rs
