guard_core_engine/redos/
intervals.rs

1//! Dense interval sets over the Unicode code-point range.
2//!
3//! Port of the reference `_redos_intervals.py`: a normalized list of
4//! inclusive `(low, high)` code-point ranges with union, intersection,
5//! complement, and difference.
6
7/// Inclusive Unicode code-point bounds.
8pub const MIN_CODE_POINT: u32 = 0;
9pub const MAX_CODE_POINT: u32 = 0x10FFFF;
10
11/// A normalized set of inclusive code-point intervals.
12#[derive(Debug, Clone, PartialEq, Eq, Hash, Default)]
13pub struct IntervalSet {
14    intervals: Vec<(u32, u32)>,
15}
16
17impl IntervalSet {
18    /// Normalize and build from possibly overlapping, unordered intervals.
19    #[must_use]
20    pub fn new(intervals: &[(u32, u32)]) -> Self {
21        let mut ordered: Vec<(u32, u32)> = intervals.to_vec();
22        ordered.sort_unstable();
23        let mut merged: Vec<(u32, u32)> = Vec::with_capacity(ordered.len());
24        for (low, high) in ordered {
25            match merged.last_mut() {
26                Some(last) if low <= last.1.saturating_add(1) => {
27                    if high > last.1 {
28                        last.1 = high;
29                    }
30                }
31                _ => merged.push((low, high)),
32            }
33        }
34        Self { intervals: merged }
35    }
36
37    /// The empty set.
38    #[must_use]
39    pub fn empty() -> Self {
40        Self {
41            intervals: Vec::new(),
42        }
43    }
44
45    /// Every code point.
46    #[must_use]
47    pub fn full() -> Self {
48        Self {
49            intervals: vec![(MIN_CODE_POINT, MAX_CODE_POINT)],
50        }
51    }
52
53    /// A set holding one code point.
54    #[must_use]
55    pub fn single(code_point: u32) -> Self {
56        Self {
57            intervals: vec![(code_point, code_point)],
58        }
59    }
60
61    /// An inclusive range, clamped to the Unicode bounds.
62    #[must_use]
63    pub fn from_range(low: u32, high: u32) -> Self {
64        let high = high.min(MAX_CODE_POINT);
65        if low > high {
66            return Self::empty();
67        }
68        Self {
69            intervals: vec![(low, high)],
70        }
71    }
72
73    /// Build from already-normalized intervals without re-checking.
74    #[must_use]
75    pub fn from_normalized(intervals: Vec<(u32, u32)>) -> Self {
76        Self { intervals }
77    }
78
79    /// The normalized interval list.
80    #[must_use]
81    pub fn intervals(&self) -> &[(u32, u32)] {
82        &self.intervals
83    }
84
85    /// Whether the set holds no code points.
86    #[must_use]
87    pub fn is_empty(&self) -> bool {
88        self.intervals.is_empty()
89    }
90
91    /// Binary-search membership.
92    #[must_use]
93    pub fn contains(&self, code_point: u32) -> bool {
94        let intervals = &self.intervals;
95        let (mut low_bound, mut high_bound) = (0usize, intervals.len());
96        while low_bound < high_bound {
97            let mid = (low_bound + high_bound) / 2;
98            let (low, high) = intervals[mid];
99            if code_point < low {
100                high_bound = mid;
101            } else if code_point > high {
102                low_bound = mid + 1;
103            } else {
104                return true;
105            }
106        }
107        false
108    }
109
110    /// The smallest member, if any.
111    #[must_use]
112    pub fn first_member(&self) -> Option<u32> {
113        self.intervals.first().map(|(low, _)| *low)
114    }
115
116    /// The first member of every component interval.
117    #[must_use]
118    pub fn component_first_members(&self) -> Vec<u32> {
119        self.intervals.iter().map(|(low, _)| *low).collect()
120    }
121
122    /// The total number of code points in the set.
123    #[must_use]
124    pub fn member_count(&self) -> u64 {
125        self.intervals
126            .iter()
127            .map(|(low, high)| u64::from(*high) - u64::from(*low) + 1)
128            .sum()
129    }
130
131    /// Union (concatenate then renormalize).
132    #[must_use]
133    pub fn union(&self, other: &IntervalSet) -> IntervalSet {
134        let mut intervals = Vec::with_capacity(self.intervals.len() + other.intervals.len());
135        intervals.extend_from_slice(&self.intervals);
136        intervals.extend_from_slice(&other.intervals);
137        Self::new(&intervals)
138    }
139
140    /// Sweep-line intersection.
141    #[must_use]
142    pub fn intersection(&self, other: &IntervalSet) -> IntervalSet {
143        let mut result: Vec<(u32, u32)> = Vec::new();
144        let (left, right) = (&self.intervals, &other.intervals);
145        let (mut i, mut j) = (0usize, 0usize);
146        while i < left.len() && j < right.len() {
147            let (a_low, a_high) = left[i];
148            let (b_low, b_high) = right[j];
149            let low = a_low.max(b_low);
150            let high = a_high.min(b_high);
151            if low <= high {
152                result.push((low, high));
153            }
154            if a_high < b_high {
155                i += 1;
156            } else {
157                j += 1;
158            }
159        }
160        IntervalSet::from_normalized(result)
161    }
162
163    /// Every code point not in the set.
164    #[must_use]
165    pub fn complement(&self) -> IntervalSet {
166        let mut result: Vec<(u32, u32)> = Vec::new();
167        let mut cursor = MIN_CODE_POINT;
168        for (low, high) in &self.intervals {
169            if *low > cursor {
170                result.push((cursor, low - 1));
171            }
172            match high.checked_add(1) {
173                Some(next) => cursor = next,
174                None => return IntervalSet::from_normalized(result),
175            }
176        }
177        if cursor <= MAX_CODE_POINT {
178            result.push((cursor, MAX_CODE_POINT));
179        }
180        IntervalSet::from_normalized(result)
181    }
182
183    /// Members of `self` not in `other`.
184    #[must_use]
185    pub fn difference(&self, other: &IntervalSet) -> IntervalSet {
186        self.intersection(&other.complement())
187    }
188}
189
190#[cfg(test)]
191mod tests {
192    use super::*;
193
194    #[test]
195    fn empty_set_has_no_members() {
196        let empty = IntervalSet::empty();
197        assert!(empty.is_empty());
198        assert_eq!(empty.first_member(), None);
199        assert!(!empty.contains(0));
200    }
201
202    #[test]
203    fn full_set_contains_the_entire_range() {
204        let full = IntervalSet::full();
205        assert!(!full.is_empty());
206        assert!(full.contains(MIN_CODE_POINT));
207        assert!(full.contains(MAX_CODE_POINT));
208        assert_eq!(full.first_member(), Some(MIN_CODE_POINT));
209    }
210
211    #[test]
212    fn single_builds_a_one_code_point_set() {
213        let single = IntervalSet::single(65);
214        assert!(single.contains(65));
215        assert!(!single.contains(64));
216        assert!(!single.contains(66));
217        assert_eq!(single.first_member(), Some(65));
218    }
219
220    #[test]
221    fn from_range_builds_an_inclusive_range() {
222        let interval = IntervalSet::from_range(10, 20);
223        assert!(interval.contains(10));
224        assert!(interval.contains(20));
225        assert!(!interval.contains(9));
226        assert!(!interval.contains(21));
227    }
228
229    #[test]
230    fn from_range_returns_empty_when_low_exceeds_high() {
231        assert!(IntervalSet::from_range(20, 10).is_empty());
232    }
233
234    #[test]
235    fn from_range_clips_to_the_valid_code_point_span() {
236        let interval = IntervalSet::from_range(0, u32::MAX);
237        assert!(interval.contains(MIN_CODE_POINT));
238        assert!(interval.contains(MAX_CODE_POINT));
239        assert_eq!(
240            interval.intervals().last().copied(),
241            Some((0, MAX_CODE_POINT))
242        );
243    }
244
245    #[test]
246    fn union_merges_adjacent_and_overlapping_intervals() {
247        let adjacent = IntervalSet::from_range(0, 10).union(&IntervalSet::from_range(11, 20));
248        assert!(adjacent.contains(10));
249        assert!(adjacent.contains(11));
250        assert_eq!(adjacent.first_member(), Some(0));
251
252        let overlapping = IntervalSet::from_range(0, 10).union(&IntervalSet::from_range(5, 15));
253        assert!(overlapping.contains(15));
254    }
255
256    #[test]
257    fn union_keeps_disjoint_intervals_sorted() {
258        let disjoint = IntervalSet::from_range(50, 60).union(&IntervalSet::from_range(1, 5));
259        assert_eq!(disjoint.first_member(), Some(1));
260        assert_eq!(disjoint.intervals(), &[(1, 5), (50, 60)]);
261    }
262
263    #[test]
264    fn intersection_overlaps_swept_intervals() {
265        let left = IntervalSet::new(&[(0, 10), (20, 30)]);
266        let right = IntervalSet::new(&[(5, 25), (28, 40)]);
267        let both = left.intersection(&right);
268        assert_eq!(both.intervals(), &[(5, 10), (20, 25), (28, 30)]);
269    }
270
271    #[test]
272    fn intersection_of_disjoint_sets_is_empty() {
273        let left = IntervalSet::from_range(0, 5);
274        let right = IntervalSet::from_range(6, 9);
275        assert!(left.intersection(&right).is_empty());
276    }
277
278    #[test]
279    fn complement_splits_around_members() {
280        let set = IntervalSet::new(&[(5, 10), (20, 30)]);
281        let complement = set.complement();
282        assert_eq!(
283            complement.intervals(),
284            &[(0, 4), (11, 19), (31, MAX_CODE_POINT)]
285        );
286        assert!(complement.contains(0));
287        assert!(!complement.contains(5));
288        assert!(complement.contains(MAX_CODE_POINT));
289    }
290
291    #[test]
292    fn complement_of_the_full_range_is_empty() {
293        assert!(IntervalSet::full().complement().is_empty());
294    }
295
296    #[test]
297    fn complement_of_empty_is_full() {
298        assert_eq!(
299            IntervalSet::empty().complement().intervals(),
300            &[(MIN_CODE_POINT, MAX_CODE_POINT)]
301        );
302    }
303
304    #[test]
305    fn difference_is_intersection_with_complement() {
306        let left = IntervalSet::from_range(0, 20);
307        let right = IntervalSet::from_range(10, 30);
308        assert_eq!(left.difference(&right).intervals(), &[(0, 9)]);
309    }
310
311    #[test]
312    fn contains_binary_searches_sorted_components() {
313        let set = IntervalSet::new(&[(10, 12), (100, 200), (1000, 1000)]);
314        assert!(set.contains(11));
315        assert!(set.contains(150));
316        assert!(set.contains(1000));
317        assert!(!set.contains(13));
318        assert!(!set.contains(999));
319    }
320
321    #[test]
322    fn component_first_members_lists_every_component_start() {
323        let set = IntervalSet::new(&[(10, 12), (100, 200)]);
324        assert_eq!(set.component_first_members(), vec![10, 100]);
325    }
326
327    #[test]
328    fn member_count_sums_inclusive_spans() {
329        let set = IntervalSet::new(&[(0, 9), (100, 104)]);
330        assert_eq!(set.member_count(), 15);
331    }
332
333    #[test]
334    fn new_normalizes_unordered_overlapping_input() {
335        let set = IntervalSet::new(&[(30, 40), (0, 5), (6, 10), (35, 50)]);
336        assert_eq!(set.intervals(), &[(0, 10), (30, 50)]);
337    }
338
339    #[test]
340    fn complement_at_the_top_boundary_does_not_overflow() {
341        let set = IntervalSet::from_range(MAX_CODE_POINT, MAX_CODE_POINT);
342        assert_eq!(set.complement().intervals(), &[(0, MAX_CODE_POINT - 1)]);
343    }
344
345    #[test]
346    fn complement_at_the_code_point_ceilings_is_well_defined() {
347        // An interval ending at the last code point has no successor; the
348        // complement walk must stop without overflowing.
349        assert_eq!(
350            IntervalSet::single(u32::MAX).complement(),
351            IntervalSet::new(&[(0, u32::MAX - 1)])
352        );
353        let head = IntervalSet::from_range(1, u32::MAX);
354        assert_eq!(head.complement(), IntervalSet::single(0));
355        assert_eq!(IntervalSet::full().complement(), IntervalSet::empty());
356    }
357}
guard_core_engine/redos/intervals.rs

guard_core_engine/redos/
intervals.rs
