provenant/license_detection/models/
position_span.rs

1// SPDX-FileCopyrightText: nexB Inc. and others
2// SPDX-FileCopyrightText: Provenant contributors
3// SPDX-License-Identifier: Apache-2.0
4// Derived from ScanCode Toolkit (Apache-2.0); modified. See NOTICE.
5
6//! Position span types for license detection.
7
8use crate::license_detection::position_set::PositionSet;
9
10pub enum SpanIter<'a> {
11    Range(std::ops::Range<usize>),
12    Slice(std::iter::Copied<std::slice::Iter<'a, usize>>),
13}
14
15impl<'a> Iterator for SpanIter<'a> {
16    type Item = usize;
17
18    fn next(&mut self) -> Option<Self::Item> {
19        match self {
20            SpanIter::Range(range) => range.next(),
21            SpanIter::Slice(iter) => iter.next(),
22        }
23    }
24
25    fn size_hint(&self) -> (usize, Option<usize>) {
26        match self {
27            SpanIter::Range(range) => range.size_hint(),
28            SpanIter::Slice(iter) => iter.size_hint(),
29        }
30    }
31}
32
33#[derive(Debug, Clone)]
34pub enum PositionSpan {
35    Range { start: usize, end: usize },
36    Discrete(Vec<usize>),
37}
38
39impl PartialEq for PositionSpan {
40    /// Compare two PositionSpans for semantic equality.
41    ///
42    /// Returns true if both spans contain exactly the same positions,
43    /// regardless of representation (Range vs Discrete).
44    ///
45    /// Performance:
46    /// - Range vs Range: O(1)
47    /// - Discrete vs Discrete: O(n)
48    /// - Range vs Discrete: O(n) with early exit on length mismatch
49    fn eq(&self, other: &Self) -> bool {
50        match (self, other) {
51            (
52                PositionSpan::Range { start: s1, end: e1 },
53                PositionSpan::Range { start: s2, end: e2 },
54            ) => s1 == s2 && e1 == e2,
55            (PositionSpan::Discrete(p1), PositionSpan::Discrete(p2)) => p1 == p2,
56            (PositionSpan::Range { start, end }, PositionSpan::Discrete(positions)) => {
57                let range_len = end.saturating_sub(*start);
58                if range_len != positions.len() {
59                    return false;
60                }
61                if positions.is_empty() {
62                    return true;
63                }
64                positions.iter().all(|&p| *start <= p && p < *end)
65            }
66            (PositionSpan::Discrete(_), PositionSpan::Range { .. }) => other == self,
67        }
68    }
69}
70
71impl PositionSpan {
72    pub fn range(start: usize, end: usize) -> Self {
73        Self::Range { start, end }
74    }
75
76    pub fn new(start: usize, end: usize) -> Self {
77        Self::range(start, end)
78    }
79
80    pub fn from_positions(positions: impl IntoIterator<Item = usize>) -> Self {
81        let mut iter = positions.into_iter();
82        let Some(first) = iter.next() else {
83            return Self::empty();
84        };
85
86        let mut positions = vec![first];
87        positions.extend(iter);
88
89        if positions.len() == 1 {
90            return Self::Range {
91                start: positions[0],
92                end: positions[0] + 1,
93            };
94        }
95
96        positions.sort_unstable();
97        positions.dedup();
98
99        let is_contiguous = positions.windows(2).all(|w| w[1] == w[0] + 1);
100
101        if is_contiguous {
102            Self::Range {
103                start: positions[0],
104                end: positions[positions.len() - 1] + 1,
105            }
106        } else {
107            Self::Discrete(positions)
108        }
109    }
110
111    pub fn empty() -> Self {
112        Self::Range { start: 0, end: 0 }
113    }
114
115    pub fn iter(&self) -> SpanIter<'_> {
116        match self {
117            PositionSpan::Range { start, end } => SpanIter::Range(*start..*end),
118            PositionSpan::Discrete(positions) => SpanIter::Slice(positions.iter().copied()),
119        }
120    }
121
122    pub fn len(&self) -> usize {
123        match self {
124            PositionSpan::Range { start, end } => end.saturating_sub(*start),
125            PositionSpan::Discrete(positions) => positions.len(),
126        }
127    }
128
129    pub fn is_empty(&self) -> bool {
130        self.len() == 0
131    }
132
133    pub fn bounds(&self) -> (usize, usize) {
134        match self {
135            PositionSpan::Range { start, end } => (*start, *end),
136            PositionSpan::Discrete(positions) => {
137                if positions.is_empty() {
138                    return (0, 0);
139                }
140                let min = positions.iter().copied().min().unwrap_or(0);
141                let max = positions.iter().copied().max().unwrap_or(0);
142                (min, max + 1)
143            }
144        }
145    }
146
147    pub fn contains(&self, pos: usize) -> bool {
148        match self {
149            PositionSpan::Range { start, end } => *start <= pos && pos < *end,
150            PositionSpan::Discrete(positions) => positions.binary_search(&pos).is_ok(),
151        }
152    }
153
154    pub fn overlaps_set(&self, set: &PositionSet) -> bool {
155        let (my_min, my_max) = self.bounds();
156        if self.is_empty() {
157            return false;
158        }
159        if !set.may_overlap_range(my_min, my_max) {
160            return false;
161        }
162        self.iter().any(|p| set.contains(p))
163    }
164
165    pub fn to_position_set(&self) -> PositionSet {
166        match self {
167            PositionSpan::Range { start, end } => (*start..*end).collect(),
168            PositionSpan::Discrete(positions) => positions.iter().copied().collect(),
169        }
170    }
171
172    pub fn to_vec(&self) -> Vec<usize> {
173        match self {
174            PositionSpan::Range { start, end } => (*start..*end).collect(),
175            PositionSpan::Discrete(positions) => positions.clone(),
176        }
177    }
178
179    /// Returns true if the positions form a contiguous range with no gaps.
180    /// This is always true for `Range` variants, and checks adjacency for `Discrete`.
181    pub fn is_contiguous(&self) -> bool {
182        match self {
183            PositionSpan::Range { .. } => true,
184            PositionSpan::Discrete(positions) => {
185                if positions.len() <= 1 {
186                    return true;
187                }
188                positions.windows(2).all(|w| w[1] == w[0] + 1)
189            }
190        }
191    }
192}
193
194#[cfg(test)]
195mod tests {
196    use super::*;
197
198    #[test]
199    fn test_range_creation() {
200        let span = PositionSpan::range(5, 10);
201        assert_eq!(span.len(), 5);
202        assert!(!span.is_empty());
203        assert_eq!(span.bounds(), (5, 10));
204        assert!(span.is_contiguous());
205    }
206
207    #[test]
208    fn test_new_backwards_compatible() {
209        let span = PositionSpan::new(3, 7);
210        assert_eq!(span.len(), 4);
211        assert_eq!(span.to_vec(), vec![3, 4, 5, 6]);
212    }
213
214    #[test]
215    fn test_empty() {
216        let span = PositionSpan::empty();
217        assert_eq!(span.len(), 0);
218        assert!(span.is_empty());
219        assert_eq!(span.bounds(), (0, 0));
220    }
221
222    #[test]
223    fn test_from_positions_empty() {
224        let span = PositionSpan::from_positions(vec![]);
225        assert!(span.is_empty());
226    }
227
228    #[test]
229    fn test_from_positions_single() {
230        let span = PositionSpan::from_positions(vec![5]);
231        assert_eq!(span.len(), 1);
232        assert!(span.is_contiguous());
233        assert!(span.contains(5));
234    }
235
236    #[test]
237    fn test_from_positions_contiguous() {
238        let span = PositionSpan::from_positions(vec![3, 4, 5]);
239        assert!(span.is_contiguous());
240        assert_eq!(span.len(), 3);
241        assert_eq!(span.bounds(), (3, 6));
242    }
243
244    #[test]
245    fn test_from_positions_non_contiguous() {
246        let span = PositionSpan::from_positions(vec![1, 3, 5]);
247        assert!(!span.is_contiguous());
248        assert_eq!(span.len(), 3);
249        assert_eq!(span.bounds(), (1, 6));
250    }
251
252    #[test]
253    fn test_from_positions_unsorted_with_duplicates() {
254        let span = PositionSpan::from_positions(vec![5, 3, 4, 3, 5]);
255        assert!(span.is_contiguous());
256        assert_eq!(span.to_vec(), vec![3, 4, 5]);
257    }
258
259    #[test]
260    fn test_contains_range() {
261        let span = PositionSpan::range(5, 10);
262        assert!(!span.contains(4));
263        assert!(span.contains(5));
264        assert!(span.contains(7));
265        assert!(span.contains(9));
266        assert!(!span.contains(10));
267    }
268
269    #[test]
270    fn test_contains_discrete() {
271        let span = PositionSpan::from_positions(vec![1, 3, 5]);
272        assert!(span.contains(1));
273        assert!(!span.contains(2));
274        assert!(span.contains(3));
275        assert!(!span.contains(4));
276        assert!(span.contains(5));
277    }
278
279    #[test]
280    fn test_iter_range() {
281        let span = PositionSpan::range(2, 5);
282        let positions: Vec<_> = span.iter().collect();
283        assert_eq!(positions, vec![2, 3, 4]);
284    }
285
286    #[test]
287    fn test_iter_discrete() {
288        let span = PositionSpan::from_positions(vec![1, 3, 5]);
289        let positions: Vec<_> = span.iter().collect();
290        assert_eq!(positions, vec![1, 3, 5]);
291    }
292
293    #[test]
294    fn test_to_vec_range() {
295        let span = PositionSpan::range(1, 4);
296        assert_eq!(span.to_vec(), vec![1, 2, 3]);
297    }
298
299    #[test]
300    fn test_to_vec_discrete() {
301        let span = PositionSpan::from_positions(vec![2, 4, 6]);
302        assert_eq!(span.to_vec(), vec![2, 4, 6]);
303    }
304
305    #[test]
306    fn test_to_position_set() {
307        let span = PositionSpan::range(1, 4);
308        let set = span.to_position_set();
309        assert_eq!(set.len(), 3);
310        assert!(set.contains(1));
311        assert!(set.contains(2));
312        assert!(set.contains(3));
313    }
314
315    #[test]
316    fn test_is_contiguous_discrete_single() {
317        let span = PositionSpan::from_positions(vec![5]);
318        assert!(span.is_contiguous());
319    }
320
321    #[test]
322    fn test_is_contiguous_discrete_gap() {
323        let span = PositionSpan::from_positions(vec![1, 2, 4]);
324        assert!(!span.is_contiguous());
325    }
326
327    // ============================================================
328    // Comprehensive equality tests: all 2x2 combinations
329    // ============================================================
330
331    // ---- Range vs Range ----
332
333    #[test]
334    fn test_eq_range_range_both_empty() {
335        let a = PositionSpan::range(0, 0);
336        let b = PositionSpan::range(0, 0);
337        assert_eq!(a, b);
338    }
339
340    #[test]
341    fn test_eq_range_range_one_empty() {
342        let a = PositionSpan::range(0, 0);
343        let b = PositionSpan::range(0, 3);
344        assert_ne!(a, b);
345    }
346
347    #[test]
348    fn test_eq_range_range_equal() {
349        let a = PositionSpan::range(2, 5);
350        let b = PositionSpan::range(2, 5);
351        assert_eq!(a, b);
352    }
353
354    #[test]
355    fn test_eq_range_range_disjoint() {
356        let a = PositionSpan::range(0, 3);
357        let b = PositionSpan::range(5, 8);
358        assert_ne!(a, b);
359    }
360
361    #[test]
362    fn test_eq_range_range_overlapping() {
363        let a = PositionSpan::range(0, 5);
364        let b = PositionSpan::range(3, 8);
365        assert_ne!(a, b);
366    }
367
368    // ---- Discrete vs Discrete ----
369
370    #[test]
371    fn test_eq_discrete_discrete_both_empty() {
372        let a = PositionSpan::Discrete(vec![]);
373        let b = PositionSpan::Discrete(vec![]);
374        assert_eq!(a, b);
375    }
376
377    #[test]
378    fn test_eq_discrete_discrete_one_empty() {
379        let a = PositionSpan::Discrete(vec![]);
380        let b = PositionSpan::Discrete(vec![0, 1, 2]);
381        assert_ne!(a, b);
382    }
383
384    #[test]
385    fn test_eq_discrete_discrete_equal() {
386        let a = PositionSpan::Discrete(vec![0, 1, 2]);
387        let b = PositionSpan::Discrete(vec![0, 1, 2]);
388        assert_eq!(a, b);
389    }
390
391    #[test]
392    fn test_eq_discrete_discrete_disjoint() {
393        let a = PositionSpan::Discrete(vec![0, 1, 2]);
394        let b = PositionSpan::Discrete(vec![5, 6, 7]);
395        assert_ne!(a, b);
396    }
397
398    #[test]
399    fn test_eq_discrete_discrete_overlapping() {
400        let a = PositionSpan::Discrete(vec![0, 1, 2, 3]);
401        let b = PositionSpan::Discrete(vec![2, 3, 4, 5]);
402        assert_ne!(a, b);
403    }
404
405    // ---- Range vs Discrete ----
406
407    #[test]
408    fn test_eq_range_discrete_both_empty() {
409        let range = PositionSpan::range(0, 0);
410        let discrete = PositionSpan::Discrete(vec![]);
411        assert_eq!(range, discrete);
412        assert_eq!(discrete, range);
413    }
414
415    #[test]
416    fn test_eq_range_discrete_range_empty() {
417        let range = PositionSpan::range(0, 0);
418        let discrete = PositionSpan::Discrete(vec![0, 1, 2]);
419        assert_ne!(range, discrete);
420        assert_ne!(discrete, range);
421    }
422
423    #[test]
424    fn test_eq_range_discrete_discrete_empty() {
425        let range = PositionSpan::range(0, 3);
426        let discrete = PositionSpan::Discrete(vec![]);
427        assert_ne!(range, discrete);
428        assert_ne!(discrete, range);
429    }
430
431    #[test]
432    fn test_eq_range_discrete_equal() {
433        let range = PositionSpan::range(2, 5);
434        let discrete = PositionSpan::Discrete(vec![2, 3, 4]);
435        assert_eq!(range, discrete);
436        assert_eq!(discrete, range);
437    }
438
439    #[test]
440    fn test_eq_range_discrete_disjoint() {
441        let range = PositionSpan::range(0, 3);
442        let discrete = PositionSpan::Discrete(vec![5, 6, 7]);
443        assert_ne!(range, discrete);
444        assert_ne!(discrete, range);
445    }
446
447    #[test]
448    fn test_eq_range_discrete_overlapping_partial() {
449        let range = PositionSpan::range(0, 5);
450        let discrete = PositionSpan::Discrete(vec![2, 3, 4, 5, 6]);
451        assert_ne!(range, discrete);
452        assert_ne!(discrete, range);
453    }
454
455    #[test]
456    fn test_eq_range_discrete_subset() {
457        // Discrete is subset of range
458        let range = PositionSpan::range(0, 10);
459        let discrete = PositionSpan::Discrete(vec![2, 3, 4]);
460        assert_ne!(range, discrete);
461        assert_ne!(discrete, range);
462    }
463
464    #[test]
465    fn test_eq_range_discrete_superset() {
466        // Discrete extends beyond range
467        let range = PositionSpan::range(5, 10);
468        let discrete = PositionSpan::Discrete(vec![3, 4, 5, 6, 7]);
469        assert_ne!(range, discrete);
470        assert_ne!(discrete, range);
471    }
472
473    // ---- Mixed empty tests ----
474
475    #[test]
476    fn test_eq_empty_different_representation() {
477        let a = PositionSpan::range(0, 0);
478        let b = PositionSpan::Discrete(vec![]);
479        assert_eq!(a, b);
480        assert_eq!(b, a);
481    }
482}
provenant/license_detection/models/position_span.rs

provenant/license_detection/models/
position_span.rs
