range_utils.rs
1 //! Range utility functions for LSP operations. 2 //! 3 //! Provides efficient range comparison, deduplication, and position checking. 4 5 use rustc_hash::FxHashSet; 6 use tower_lsp::lsp_types::{Position, Range}; 7 8 use crate::constants::RANGE_SIZE_LINE_WEIGHT; 9 10 /// A hashable key for range deduplication. 11 /// 12 /// Converts an LSP `Range` into a tuple of u32 values that can be 13 /// efficiently hashed and compared. 14 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] 15 pub struct RangeKey { 16 pub start_line: u32, 17 pub start_char: u32, 18 pub end_line: u32, 19 pub end_char: u32, 20 } 21 22 impl From<Range> for RangeKey { 23 fn from(range: Range) -> Self { 24 Self { 25 start_line: range.start.line, 26 start_char: range.start.character, 27 end_line: range.end.line, 28 end_char: range.end.character, 29 } 30 } 31 } 32 33 impl RangeKey { 34 /// Create a new RangeKey from an LSP Range. 35 #[inline] 36 pub fn new(range: Range) -> Self { 37 Self::from(range) 38 } 39 40 /// Convert back to an LSP Range. 41 #[inline] 42 pub fn to_range(self) -> Range { 43 Range::new( 44 Position::new(self.start_line, self.start_char), 45 Position::new(self.end_line, self.end_char), 46 ) 47 } 48 } 49 50 /// Helper for deduplicating ranges efficiently. 51 /// 52 /// Uses FxHashSet with RangeKey for fast O(1) lookups. 53 #[derive(Debug, Default)] 54 pub struct RangeDeduplicator { 55 seen: FxHashSet<RangeKey>, 56 } 57 58 impl RangeDeduplicator { 59 /// Create a new deduplicator. 60 pub fn new() -> Self { 61 Self::default() 62 } 63 64 /// Create a new deduplicator with pre-allocated capacity. 65 pub fn with_capacity(capacity: usize) -> Self { 66 Self { 67 seen: FxHashSet::with_capacity_and_hasher(capacity, Default::default()), 68 } 69 } 70 71 /// Try to insert a range. Returns true if the range was new, false if already seen. 72 #[inline] 73 pub fn insert(&mut self, range: Range) -> bool { 74 self.seen.insert(RangeKey::from(range)) 75 } 76 77 /// Check if a range has already been seen. 78 #[inline] 79 pub fn contains(&self, range: Range) -> bool { 80 self.seen.contains(&RangeKey::from(range)) 81 } 82 83 /// Clear all seen ranges. 84 pub fn clear(&mut self) { 85 self.seen.clear(); 86 } 87 88 /// Number of unique ranges seen. 89 pub fn len(&self) -> usize { 90 self.seen.len() 91 } 92 93 /// Check if no ranges have been seen. 94 pub fn is_empty(&self) -> bool { 95 self.seen.is_empty() 96 } 97 } 98 99 /// Check if a position is contained within a range. 100 /// 101 /// The range is treated as half-open: start is inclusive, end is exclusive. 102 #[inline] 103 pub fn contains_position(range: Range, pos: Position) -> bool { 104 if pos.line < range.start.line || pos.line > range.end.line { 105 return false; 106 } 107 if pos.line == range.start.line && pos.character < range.start.character { 108 return false; 109 } 110 111 if pos.line == range.end.line && pos.character >= range.end.character { 112 return false; 113 } 114 115 true 116 } 117 118 /// Check if an inner range is fully contained within an outer range. 119 #[inline] 120 pub fn range_contains_range(outer: Range, inner: Range) -> bool { 121 if inner.start.line < outer.start.line { 122 return false; 123 } 124 if inner.start.line == outer.start.line && inner.start.character < outer.start.character { 125 return false; 126 } 127 if inner.end.line > outer.end.line { 128 return false; 129 } 130 if inner.end.line == outer.end.line && inner.end.character > outer.end.character { 131 return false; 132 } 133 134 true 135 } 136 137 /// Check if two ranges overlap. 138 /// 139 /// Touching ranges (one ends exactly where the other starts) are not considered overlapping. 140 #[inline] 141 pub fn ranges_overlap(a: Range, b: Range) -> bool { 142 // No overlap if one ends before the other starts 143 if a.end.line < b.start.line 144 || (a.end.line == b.start.line && a.end.character <= b.start.character) 145 { 146 return false; 147 } 148 if b.end.line < a.start.line 149 || (b.end.line == a.start.line && b.end.character <= a.start.character) 150 { 151 return false; 152 } 153 154 true 155 } 156 157 /// Calculate a size metric for a range. 158 /// 159 /// Useful for finding the most specific (smallest) range containing a position. 160 /// Multi-line ranges are weighted more heavily than single-line ranges. 161 #[inline] 162 pub fn range_size(range: Range) -> u64 { 163 let lines = (range.end.line - range.start.line) as u64; 164 let chars = if range.end.line == range.start.line { 165 (range.end.character - range.start.character) as u64 166 } else { 167 range.end.character as u64 168 }; 169 lines * RANGE_SIZE_LINE_WEIGHT + chars 170 } 171 172 /// Convert a Position to a 1D point for interval tree operations. 173 /// 174 /// Uses 32-bit line number in upper bits, 32-bit character in lower bits. 175 #[inline] 176 pub fn position_to_point(pos: Position) -> u64 { 177 ((pos.line as u64) << 32) | (pos.character as u64) 178 } 179 180 /// Convert an LSP Range to an interval for interval tree operations. 181 /// 182 /// Returns a half-open range [start, end) suitable for interval trees. 183 #[inline] 184 pub fn range_to_interval(range: Range) -> std::ops::Range<u64> { 185 position_to_point(range.start)..position_to_point(range.end) 186 } 187 188 /// Expand a range by N lines in each direction. 189 /// 190 /// This is useful for incremental analysis to capture nearby declarations 191 /// that may be affected by an edit. 192 #[inline] 193 pub fn expand_range(range: Range, lines: u32) -> Range { 194 Range { 195 start: Position { 196 line: range.start.line.saturating_sub(lines), 197 character: 0, 198 }, 199 end: Position { 200 line: range.end.line.saturating_add(lines), 201 character: u32::MAX, 202 }, 203 } 204 } 205 206 #[cfg(test)] 207 mod tests { 208 use super::*; 209 210 fn make_range(start_line: u32, start_char: u32, end_line: u32, end_char: u32) -> Range { 211 Range::new( 212 Position::new(start_line, start_char), 213 Position::new(end_line, end_char), 214 ) 215 } 216 217 #[test] 218 fn test_range_key_roundtrip() { 219 let range = make_range(5, 10, 15, 20); 220 let key = RangeKey::from(range); 221 assert_eq!(key.to_range(), range); 222 } 223 224 #[test] 225 fn test_range_deduplicator() { 226 let mut dedup = RangeDeduplicator::new(); 227 let range1 = make_range(1, 0, 1, 10); 228 let range2 = make_range(2, 0, 2, 10); 229 230 assert!(dedup.insert(range1)); 231 assert!(!dedup.insert(range1)); // duplicate 232 assert!(dedup.insert(range2)); 233 assert_eq!(dedup.len(), 2); 234 } 235 236 #[test] 237 fn test_contains_position_basic() { 238 let range = make_range(5, 10, 5, 20); 239 240 // Inside 241 assert!(contains_position(range, Position::new(5, 15))); 242 243 // At start 244 assert!(contains_position(range, Position::new(5, 10))); 245 246 // At end (exclusive) 247 assert!(!contains_position(range, Position::new(5, 20))); 248 249 // Before 250 assert!(!contains_position(range, Position::new(5, 5))); 251 252 // After 253 assert!(!contains_position(range, Position::new(5, 25))); 254 } 255 256 #[test] 257 fn test_contains_position_multiline() { 258 let range = make_range(5, 10, 7, 20); 259 260 // First line 261 assert!(contains_position(range, Position::new(5, 15))); 262 263 // Middle line 264 assert!(contains_position(range, Position::new(6, 0))); 265 266 // Last line 267 assert!(contains_position(range, Position::new(7, 10))); 268 269 // Past end 270 assert!(!contains_position(range, Position::new(7, 20))); 271 } 272 273 #[test] 274 fn test_ranges_overlap() { 275 let a = make_range(5, 10, 5, 20); 276 let b = make_range(5, 15, 5, 25); 277 278 assert!(ranges_overlap(a, b)); 279 assert!(ranges_overlap(b, a)); 280 } 281 282 #[test] 283 fn test_ranges_no_overlap_touching() { 284 let a = make_range(5, 10, 5, 20); 285 let b = make_range(5, 20, 5, 30); 286 287 // Touching ranges don't overlap 288 assert!(!ranges_overlap(a, b)); 289 assert!(!ranges_overlap(b, a)); 290 } 291 292 #[test] 293 fn test_ranges_no_overlap_separate() { 294 let a = make_range(5, 10, 5, 20); 295 let b = make_range(6, 0, 6, 10); 296 297 assert!(!ranges_overlap(a, b)); 298 assert!(!ranges_overlap(b, a)); 299 } 300 301 #[test] 302 fn test_range_size_single_line() { 303 let range = make_range(5, 10, 5, 20); 304 assert_eq!(range_size(range), 10); 305 } 306 307 #[test] 308 fn test_range_size_multi_line() { 309 let range = make_range(5, 10, 8, 20); 310 let size = range_size(range); 311 // lines = 3, chars = end.character = 20 312 assert_eq!(size, 3 * RANGE_SIZE_LINE_WEIGHT + 20); 313 } 314 315 #[test] 316 fn test_position_to_point() { 317 let pos = Position::new(100, 50); 318 let point = position_to_point(pos); 319 320 // Verify line is in upper 32 bits, character in lower 32 bits 321 assert_eq!((point >> 32) as u32, 100); 322 assert_eq!(point as u32, 50); 323 } 324 325 #[test] 326 fn test_range_to_interval() { 327 let range = make_range(5, 10, 7, 20); 328 let interval = range_to_interval(range); 329 330 assert_eq!(interval.start, position_to_point(range.start)); 331 assert_eq!(interval.end, position_to_point(range.end)); 332 } 333 334 #[test] 335 fn test_range_contains_range() { 336 let outer = make_range(5, 10, 10, 20); 337 let inner = make_range(6, 0, 9, 30); 338 339 assert!(range_contains_range(outer, inner)); 340 assert!(!range_contains_range(inner, outer)); 341 } 342 343 #[test] 344 fn test_expand_range() { 345 let range = make_range(10, 5, 15, 10); 346 let expanded = expand_range(range, 3); 347 348 // Start line should be 10 - 3 = 7, character 0 349 assert_eq!(expanded.start.line, 7); 350 assert_eq!(expanded.start.character, 0); 351 352 // End line should be 15 + 3 = 18, character MAX 353 assert_eq!(expanded.end.line, 18); 354 assert_eq!(expanded.end.character, u32::MAX); 355 } 356 357 #[test] 358 fn test_expand_range_saturating() { 359 // Test that expansion near line 0 doesn't underflow 360 let range = make_range(1, 5, 3, 10); 361 let expanded = expand_range(range, 5); 362 363 assert_eq!(expanded.start.line, 0); // saturating_sub prevents underflow 364 assert_eq!(expanded.start.character, 0); 365 } 366 }