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
use std::sync::Arc;
use rustc_hash::{FxHashMap, FxHashSet};
use crate::types::{Fragment, FragmentId};
pub struct IntervalIndex {
by_path: FxHashMap<Arc<str>, Vec<(u32, u32)>>,
ids: FxHashSet<FragmentId>,
}
impl IntervalIndex {
pub fn new() -> Self {
Self {
by_path: FxHashMap::default(),
ids: FxHashSet::default(),
}
}
pub fn add(&mut self, frag: &Fragment) {
self.add_id(&frag.id);
}
pub fn add_id(&mut self, frag_id: &FragmentId) {
self.ids.insert(frag_id.clone());
let intervals = self.by_path.entry(frag_id.path.clone()).or_default();
let item = (frag_id.start_line, frag_id.end_line);
let pos = intervals.binary_search(&item).unwrap_or_else(|e| e);
intervals.insert(pos, item);
}
pub fn contains(&self, frag_id: &FragmentId) -> bool {
self.ids.contains(frag_id)
}
pub fn overlaps(&self, frag: &Fragment) -> bool {
let intervals = match self.by_path.get(&frag.id.path) {
Some(v) => v,
None => return false,
};
let upper = intervals.partition_point(|&(s, _)| s <= frag.end_line());
for i in 0..upper {
let (start, end) = intervals[i];
if start == frag.start_line() && end == frag.end_line() {
continue;
}
// Strict `>`: a fragment starting on the very last line of an
// already-selected fragment shares exactly one boundary line. We
// deliberately tolerate that one-line overlap rather than drop the
// candidate, because compact languages (Rust/Go/Scala one-liners,
// Lisp `}{` chains) routinely produce back-to-back fragments sharing
// that boundary line; rejecting them would silently discard the
// next fragment's unique content for the sake of one duplicated line.
//
// KNOWN ASYMMETRY, pinned by
// `overlaps_tolerates_a_shared_boundary_in_one_direction_only`.
// `partition_point` bounds the scan by `start <= candidate.end`
// (non-strict) while this comparison is strict, so the tolerance
// applies in one direction only: selected [1,10] vs candidate
// [10,20] is kept, but the mirrored selected [10,20] vs candidate
// [1,10] is dropped. Which side a fragment lands on depends on
// greedy visit order, not on relevance. Adding the mirrored strict
// bound (`start < frag.end_line() &&`) makes it symmetric and is
// Q-class: on the 2725-case corpus it moves 3 cases above threshold
// (javascript_059, rust_008, rust_027) and 3 below
// (frontend_010, r_lang_006, r_lang_009) — net zero, so it belongs
// to a calibration cycle boundary, not to an incidental change.
if end > frag.start_line() {
return true;
}
}
false
}
pub fn is_superset_of(&self, frag: &Fragment) -> bool {
let intervals = match self.by_path.get(&frag.id.path) {
Some(v) => v,
None => return false,
};
let upper = intervals.partition_point(|&(s, _)| s <= frag.start_line());
for i in 0..upper {
let (start, end) = intervals[i];
if start == frag.start_line() && end == frag.end_line() {
continue;
}
if start <= frag.start_line() && frag.end_line() <= end {
return true;
}
}
false
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::types::FragmentKind;
fn frag(path: &str, start: u32, end: u32) -> Fragment {
Fragment {
id: FragmentId::new(Arc::from(path), start, end),
kind: FragmentKind::Function,
content: Arc::from(""),
identifiers: FxHashSet::default(),
token_count: 1,
symbol_name: None,
}
}
fn index_with(spans: &[(u32, u32)]) -> IntervalIndex {
let mut idx = IntervalIndex::new();
for &(s, e) in spans {
idx.add(&frag("a.rs", s, e));
}
idx
}
#[test]
fn overlaps_is_true_for_genuine_intersections() {
let idx = index_with(&[(10, 20)]);
for &(s, e) in &[(15, 25), (11, 19), (9, 21), (5, 15), (10, 20 + 1)] {
assert!(
idx.overlaps(&frag("a.rs", s, e)),
"[{s},{e}] should intersect [10,20]"
);
}
}
/// Pins the known asymmetry documented on the comparison in `overlaps`.
/// The forward direction is the deliberate boundary tolerance; the mirrored
/// direction drops the candidate for the same geometry, so the verdict
/// depends on greedy visit order. Making it symmetric is Q-class (see the
/// comment for the measured corpus effect) — this test exists so the
/// current behaviour cannot change silently, in either direction.
#[test]
fn overlaps_tolerates_a_shared_boundary_in_one_direction_only() {
assert!(
!index_with(&[(1, 10)]).overlaps(&frag("a.rs", 10, 20)),
"candidate starting on the selected fragment's last line must be tolerated"
);
assert!(
index_with(&[(10, 20)]).overlaps(&frag("a.rs", 1, 10)),
"the mirrored case is currently reported as overlapping; if this now \
passes as tolerated, the symmetry fix landed — update the corpus baseline"
);
}
#[test]
fn overlaps_verdicts_are_pinned_across_the_boundary_matrix() {
// (selected, candidate) -> expected verdict. Encodes the asymmetry
// above rather than assuming symmetry, so any change to either
// comparison shows up here as a concrete diff.
let expected = [
((1, 10), (10, 20), false),
((10, 20), (1, 10), true),
((10, 20), (20, 30), false),
((20, 30), (10, 20), true),
((10, 20), (11, 19), true),
((11, 19), (10, 20), true),
((10, 20), (9, 21), true),
((9, 21), (10, 20), true),
// Another face of the same asymmetry: a one-line fragment at the
// selected span's start does not block it, but the reverse does.
((10, 20), (10, 10), true),
((10, 10), (10, 20), false),
];
for (selected, candidate, want) in expected {
let got = index_with(&[selected]).overlaps(&frag("a.rs", candidate.0, candidate.1));
assert_eq!(
got, want,
"selected {selected:?} vs candidate {candidate:?}: got {got}, want {want}"
);
}
}
#[test]
fn overlaps_ignores_other_paths() {
let idx = index_with(&[(10, 20)]);
assert!(!idx.overlaps(&frag("b.rs", 15, 16)));
}
#[test]
fn identical_span_is_reported_by_contains_not_by_overlaps() {
// The exact-span `continue` means a duplicate is NOT an overlap, so
// callers must rely on `contains` to avoid charging the budget twice.
let idx = index_with(&[(10, 20)]);
let same = frag("a.rs", 10, 20);
assert!(!idx.overlaps(&same));
assert!(idx.contains(&same.id));
}
#[test]
fn is_superset_of_detects_enclosure_and_ignores_identical_spans() {
let idx = index_with(&[(10, 30)]);
assert!(idx.is_superset_of(&frag("a.rs", 15, 25)));
assert!(idx.is_superset_of(&frag("a.rs", 10, 25)));
assert!(!idx.is_superset_of(&frag("a.rs", 10, 30)));
assert!(!idx.is_superset_of(&frag("a.rs", 5, 25)));
assert!(!idx.is_superset_of(&frag("a.rs", 25, 35)));
}
#[test]
fn add_keeps_intervals_sorted_regardless_of_insertion_order() {
let forward = index_with(&[(1, 5), (10, 20), (30, 40)]);
let shuffled = index_with(&[(30, 40), (1, 5), (10, 20)]);
let path: Arc<str> = Arc::from("a.rs");
assert_eq!(forward.by_path[&path], shuffled.by_path[&path]);
assert!(forward.by_path[&path].windows(2).all(|w| w[0] <= w[1]));
}
}