supa_mdx_lint/
location.rs

Help
1use std::cmp::Ordering;
2use std::mem;
3use std::ops::{Add, Deref, DerefMut, Range, SubAssign};
4
5use serde::{Deserialize, Serialize};
6
7use crate::context::Context;
8use crate::rope::Rope;
9
10/// An offset in the source document, accounting for frontmatter lines.
11#[derive(Debug, Default, Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Deserialize, Serialize)]
12pub(crate) struct AdjustedOffset(usize);
13
14impl Deref for AdjustedOffset {
15    type Target = usize;
16
17    fn deref(&self) -> &Self::Target {
18        &self.0
19    }
20}
21
22impl DerefMut for AdjustedOffset {
23    fn deref_mut(&mut self) -> &mut Self::Target {
24        &mut self.0
25    }
26}
27
28impl From<usize> for AdjustedOffset {
29    fn from(offset: usize) -> Self {
30        Self(offset)
31    }
32}
33
34impl From<&usize> for AdjustedOffset {
35    fn from(offset: &usize) -> Self {
36        Self(*offset)
37    }
38}
39
40impl From<AdjustedOffset> for usize {
41    fn from(offset: AdjustedOffset) -> Self {
42        offset.0
43    }
44}
45
46impl From<&AdjustedOffset> for usize {
47    fn from(offset: &AdjustedOffset) -> Self {
48        offset.0
49    }
50}
51
52impl Add for AdjustedOffset {
53    type Output = Self;
54
55    fn add(self, rhs: Self) -> Self::Output {
56        Self(self.0 + rhs.0)
57    }
58}
59
60impl SubAssign for AdjustedOffset {
61    fn sub_assign(&mut self, rhs: Self) {
62        self.0 -= rhs.0;
63    }
64}
65
66impl AdjustedOffset {
67    pub fn increment(&mut self, steps: usize) {
68        self.0 += steps;
69    }
70}
71
72impl AdjustedOffset {
73    pub(crate) fn from_unadjusted(
74        offset: UnadjustedOffset,
75        mut from_start: AdjustedOffset,
76    ) -> Self {
77        from_start.increment(offset.0);
78        from_start
79    }
80
81    pub(crate) fn from_unist(point: &markdown::unist::Point, from_start: AdjustedOffset) -> Self {
82        Self::from_unadjusted(UnadjustedOffset::from(point), from_start)
83    }
84
85    pub(crate) fn into_usize(self) -> usize {
86        Into::<usize>::into(self)
87    }
88}
89
90/// An offset in the source document, not accounting for frontmatter lines.
91#[derive(Debug, Default, Clone, Eq, PartialEq, Deserialize, Serialize)]
92pub(crate) struct UnadjustedOffset(usize);
93
94impl Deref for UnadjustedOffset {
95    type Target = usize;
96
97    fn deref(&self) -> &Self::Target {
98        &self.0
99    }
100}
101
102impl DerefMut for UnadjustedOffset {
103    fn deref_mut(&mut self) -> &mut Self::Target {
104        &mut self.0
105    }
106}
107
108impl From<usize> for UnadjustedOffset {
109    fn from(offset: usize) -> Self {
110        Self(offset)
111    }
112}
113
114impl From<&usize> for UnadjustedOffset {
115    fn from(offset: &usize) -> Self {
116        Self(*offset)
117    }
118}
119
120impl From<markdown::unist::Point> for UnadjustedOffset {
121    fn from(value: markdown::unist::Point) -> Self {
122        Self(value.offset)
123    }
124}
125
126impl From<&markdown::unist::Point> for UnadjustedOffset {
127    fn from(value: &markdown::unist::Point) -> Self {
128        Self(value.offset)
129    }
130}
131
132/// A point in the source document, accounting for frontmatter lines.
133#[derive(Debug, Default, Clone, Eq, PartialEq, Serialize, Deserialize)]
134pub(crate) struct AdjustedPoint {
135    pub row: usize,
136    pub column: usize,
137}
138
139impl PartialOrd for AdjustedPoint {
140    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
141        Some(self.cmp(other))
142    }
143}
144
145impl Ord for AdjustedPoint {
146    fn cmp(&self, other: &Self) -> Ordering {
147        match self.row.cmp(&other.row) {
148            Ordering::Less => Ordering::Less,
149            Ordering::Equal => self.column.cmp(&other.column),
150            Ordering::Greater => Ordering::Greater,
151        }
152    }
153}
154
155impl AdjustedPoint {
156    pub(crate) fn from_adjusted_offset(offset: &AdjustedOffset, rope: &Rope) -> Self {
157        let (row, column) = rope.line_column_of_byte(offset.into());
158        Self { row, column }
159    }
160}
161
162/// A range in the source document, accounting for frontmatter lines.
163/// The start point is inclusive, the end point is exclusive.
164#[derive(Debug, Default, Clone, Eq, PartialEq, Serialize, Deserialize)]
165pub(crate) struct AdjustedRange(Range<AdjustedOffset>);
166
167impl Deref for AdjustedRange {
168    type Target = Range<AdjustedOffset>;
169
170    fn deref(&self) -> &Self::Target {
171        &self.0
172    }
173}
174
175impl DerefMut for AdjustedRange {
176    fn deref_mut(&mut self) -> &mut Self::Target {
177        &mut self.0
178    }
179}
180
181impl From<AdjustedRange> for Range<usize> {
182    fn from(range: AdjustedRange) -> Self {
183        Self::from(&range)
184    }
185}
186
187impl From<&AdjustedRange> for Range<usize> {
188    fn from(range: &AdjustedRange) -> Self {
189        Self {
190            start: range.start.into(),
191            end: range.end.into(),
192        }
193    }
194}
195
196impl AdjustedRange {
197    pub(crate) fn new(start: AdjustedOffset, end: AdjustedOffset) -> Self {
198        Self(Range { start, end })
199    }
200
201    pub(crate) fn from_unadjusted_position(
202        position: &markdown::unist::Position,
203        context: &Context,
204    ) -> Self {
205        let adjusted_start =
206            AdjustedOffset::from_unist(&position.start, context.content_start_offset());
207        let adjusted_end =
208            AdjustedOffset::from_unist(&position.end, context.content_start_offset());
209        Self(Range {
210            start: adjusted_start,
211            end: adjusted_end,
212        })
213    }
214
215    pub(crate) fn span_between(first: &Self, second: &Self) -> Self {
216        let start = first.start.min(second.start);
217        let end = first.end.max(second.end);
218        Self(Range { start, end })
219    }
220
221    pub(crate) fn overlaps_or_abuts(&self, other: &Self) -> bool {
222        if self.start > other.start {
223            other.overlaps_or_abuts(self)
224        } else {
225            self.end >= other.start
226        }
227    }
228
229    // Helper method to avoid having to call the ridiculous
230    // `Into::<Range<usize>>::into` in many places.
231    pub(crate) fn to_usize_range(&self) -> Range<usize> {
232        Into::<Range<usize>>::into(self)
233    }
234}
235
236#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
237pub(crate) struct MaybeEndedLineRange(MaybeEndedRange<usize>);
238
239impl Deref for MaybeEndedLineRange {
240    type Target = MaybeEndedRange<usize>;
241
242    fn deref(&self) -> &Self::Target {
243        &self.0
244    }
245}
246
247impl DerefMut for MaybeEndedLineRange {
248    fn deref_mut(&mut self) -> &mut Self::Target {
249        &mut self.0
250    }
251}
252
253impl MaybeEndedLineRange {
254    pub(crate) fn new(start: usize, end: Option<usize>) -> Self {
255        Self(MaybeEndedRange { start, end })
256    }
257
258    pub(crate) fn overlaps_lines(&self, range: &AdjustedRange, rope: &Rope) -> bool {
259        let range_start_line = AdjustedPoint::from_adjusted_offset(&range.start, rope).row;
260        let range_end_line = AdjustedPoint::from_adjusted_offset(&range.end, rope).row;
261        self.start <= range_start_line && self.end.is_none_or(|end| end > range_start_line)
262            || self.start <= range_end_line && self.end.is_none_or(|end| end > range_end_line)
263    }
264}
265
266#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
267pub(crate) struct MaybeEndedRange<T>
268where
269    T: Ord,
270{
271    pub start: T,
272    pub end: Option<T>,
273}
274
275impl<T: Ord> MaybeEndedRange<T> {
276    pub(crate) fn is_open_ended(&self) -> bool {
277        self.end.is_none()
278    }
279
280    /**
281     * Check if two MaybeEndedRanges overlap strictly. (Strict: ranges are
282     * not considered to overlap if they are merely adjoining.)
283     */
284    pub(crate) fn overlaps_strict(&self, other: &Self) -> bool {
285        self.start <= other.start && self.end.as_ref().is_none_or(|end| *end > other.start)
286            || other.start <= self.start && other.end.as_ref().is_none_or(|end| *end > self.start)
287    }
288}
289
290#[derive(Debug, Clone, Eq, PartialEq, Deserialize, Serialize)]
291pub(crate) struct DenormalizedLocation {
292    pub offset_range: AdjustedRange,
293    pub start: AdjustedPoint,
294    pub end: AdjustedPoint,
295}
296
297impl DenormalizedLocation {
298    pub(crate) fn from_offset_range(range: AdjustedRange, context: &Context) -> Self {
299        let start = AdjustedPoint::from_adjusted_offset(&range.start, context.rope());
300        let end = AdjustedPoint::from_adjusted_offset(&range.end, context.rope());
301        Self {
302            offset_range: range,
303            start,
304            end,
305        }
306    }
307}
308
309#[derive(Debug, Default)]
310pub(crate) struct RangeSet(Vec<AdjustedRange>);
311
312impl RangeSet {
313    pub(crate) fn new() -> Self {
314        Default::default()
315    }
316
317    pub(crate) fn push(&mut self, range: AdjustedRange) {
318        match self.overlaps_impl(&range) {
319            Ok(index) => {
320                self.0[index] = AdjustedRange::span_between(&self.0[index], &range);
321                if index < self.0.len() - 1 && self.0[index].overlaps_or_abuts(&self.0[index + 1]) {
322                    let taken_vec = mem::take(&mut self.0);
323                    self.0 = taken_vec.into_iter().fold(Vec::new(), |mut accum, range| {
324                        if !accum.is_empty() {
325                            let last_index = accum.len() - 1;
326                            if accum[last_index].overlaps_or_abuts(&range) {
327                                accum[last_index] =
328                                    AdjustedRange::span_between(&accum[last_index], &range);
329                            } else {
330                                accum.push(range);
331                            }
332                        } else {
333                            accum.push(range);
334                        }
335                        accum
336                    });
337                }
338            }
339            Err(index) => {
340                self.0.insert(index, range);
341            }
342        }
343    }
344
345    pub(crate) fn completely_contains(&self, range: &AdjustedRange) -> bool {
346        match self.overlaps_impl(range) {
347            Err(_) => false,
348            Ok(index) => {
349                let potential_container = &self.0[index];
350                potential_container.start <= range.start && potential_container.end >= range.end
351            }
352        }
353    }
354
355    fn overlaps_impl(&self, range: &AdjustedRange) -> Result<usize, usize> {
356        self.0
357            .binary_search_by(|probe| {
358                if probe.end < range.start {
359                    Ordering::Less
360                } else if probe.start > range.end {
361                    Ordering::Greater
362                } else {
363                    Ordering::Equal
364                }
365            })
366            .map(|index| {
367                // Ensure we return the first matching index
368                let mut first_index = index;
369                while first_index > 0 && self.0[first_index - 1].overlaps_or_abuts(range) {
370                    first_index -= 1;
371                }
372                first_index
373            })
374    }
375}
376
377pub trait Offsets: crate::private::Sealed {
378    fn start(&self) -> usize;
379    fn end(&self) -> usize;
380}
381
382impl<T: Offsets + crate::private::Sealed> Offsets for &T {
383    fn start(&self) -> usize {
384        (*self).start()
385    }
386
387    fn end(&self) -> usize {
388        (*self).end()
389    }
390}
391
392#[cfg(test)]
393mod tests {
394    use super::{AdjustedOffset, AdjustedPoint, AdjustedRange, DenormalizedLocation};
395
396    impl DenormalizedLocation {
397        pub fn dummy(
398            start_offset: usize,
399            end_offset: usize,
400            start_row: usize,
401            start_column: usize,
402            end_row: usize,
403            end_column: usize,
404        ) -> Self {
405            Self {
406                offset_range: AdjustedRange::new(
407                    AdjustedOffset::from(start_offset),
408                    AdjustedOffset::from(end_offset),
409                ),
410                start: AdjustedPoint {
411                    row: start_row,
412                    column: start_column,
413                },
414                end: AdjustedPoint {
415                    row: end_row,
416                    column: end_column,
417                },
418            }
419        }
420    }
421
422    #[test]
423    fn test_range_set_merges_overlapping_ranges() {
424        let mut set = super::RangeSet::new();
425
426        let range1 = AdjustedRange::new(AdjustedOffset::from(0), AdjustedOffset::from(5));
427        let range2 = AdjustedRange::new(AdjustedOffset::from(3), AdjustedOffset::from(8));
428
429        set.push(range1);
430        set.push(range2);
431
432        assert_eq!(set.0.len(), 1);
433        assert_eq!(set.0[0].start, AdjustedOffset::from(0));
434        assert_eq!(set.0[0].end, AdjustedOffset::from(8));
435    }
436
437    #[test]
438    fn test_range_set_merges_multiple_overlapping_ranges() {
439        let mut set = super::RangeSet::new();
440
441        let range1 = AdjustedRange::new(AdjustedOffset::from(0), AdjustedOffset::from(5));
442        let range2 = AdjustedRange::new(AdjustedOffset::from(3), AdjustedOffset::from(18));
443        let range3 = AdjustedRange::new(AdjustedOffset::from(10), AdjustedOffset::from(15));
444        let range4 = AdjustedRange::new(AdjustedOffset::from(17), AdjustedOffset::from(20));
445        let range5 = AdjustedRange::new(AdjustedOffset::from(23), AdjustedOffset::from(25));
446
447        set.push(range1);
448        set.push(range3);
449        set.push(range4);
450        set.push(range5);
451        set.push(range2);
452
453        assert_eq!(set.0.len(), 2);
454        assert_eq!(set.0[0].start, AdjustedOffset::from(0));
455        assert_eq!(set.0[0].end, AdjustedOffset::from(20));
456    }
457
458    #[test]
459    fn test_range_set_merges_adjacent_ranges() {
460        let mut set = super::RangeSet::new();
461
462        let range1 = AdjustedRange::new(AdjustedOffset::from(0), AdjustedOffset::from(5));
463        let range2 = AdjustedRange::new(AdjustedOffset::from(5), AdjustedOffset::from(8));
464
465        set.push(range1);
466        set.push(range2);
467
468        assert_eq!(set.0.len(), 1);
469        assert_eq!(set.0[0].start, AdjustedOffset::from(0));
470        assert_eq!(set.0[0].end, AdjustedOffset::from(8));
471
472        let mut set = super::RangeSet::new();
473
474        let range1 = AdjustedRange::new(AdjustedOffset::from(5), AdjustedOffset::from(8));
475        let range2 = AdjustedRange::new(AdjustedOffset::from(0), AdjustedOffset::from(5));
476
477        set.push(range1);
478        set.push(range2);
479
480        assert_eq!(set.0.len(), 1);
481        assert_eq!(set.0[0].start, AdjustedOffset::from(0));
482        assert_eq!(set.0[0].end, AdjustedOffset::from(8));
483    }
484
485    #[test]
486    fn test_range_set_keeps_non_overlapping_ranges_separate() {
487        let mut set = super::RangeSet::new();
488
489        let range1 = AdjustedRange::new(AdjustedOffset::from(0), AdjustedOffset::from(3));
490        let range2 = AdjustedRange::new(AdjustedOffset::from(5), AdjustedOffset::from(8));
491
492        set.push(range1);
493        set.push(range2);
494
495        assert_eq!(set.0.len(), 2);
496        assert_eq!(set.0[0].start, AdjustedOffset::from(0));
497        assert_eq!(set.0[0].end, AdjustedOffset::from(3));
498        assert_eq!(set.0[1].start, AdjustedOffset::from(5));
499        assert_eq!(set.0[1].end, AdjustedOffset::from(8));
500    }
501
502    #[test]
503    fn test_range_set_completely_contains() {
504        let mut set = super::RangeSet::new();
505
506        // Add a range from 0-10
507        let container = AdjustedRange::new(AdjustedOffset::from(0), AdjustedOffset::from(10));
508        set.push(container);
509
510        // Test contained range
511        let contained = AdjustedRange::new(AdjustedOffset::from(2), AdjustedOffset::from(8));
512        assert!(set.completely_contains(&contained));
513
514        // Test partially overlapping range
515        let partial = AdjustedRange::new(AdjustedOffset::from(5), AdjustedOffset::from(12));
516        assert!(!set.completely_contains(&partial));
517
518        // Test non-overlapping range
519        let outside = AdjustedRange::new(AdjustedOffset::from(15), AdjustedOffset::from(20));
520        assert!(!set.completely_contains(&outside));
521
522        // Test exact same range
523        let same = AdjustedRange::new(AdjustedOffset::from(0), AdjustedOffset::from(10));
524        assert!(set.completely_contains(&same));
525    }
526}
supa_mdx_lint/location.rs

supa_mdx_lint/
location.rs
