Unnamed repository; edit this file 'description' to name the repository.
Add range type to helix stdx
| -rw-r--r-- | helix-core/src/diagnostic.rs | 14 | ||||
| -rw-r--r-- | helix-core/src/selection.rs | 41 | ||||
| -rw-r--r-- | helix-stdx/src/lib.rs | 3 | ||||
| -rw-r--r-- | helix-stdx/src/range.rs | 103 |
4 files changed, 123 insertions, 38 deletions
diff --git a/helix-core/src/diagnostic.rs b/helix-core/src/diagnostic.rs index 4e89361d..333c9409 100644 --- a/helix-core/src/diagnostic.rs +++ b/helix-core/src/diagnostic.rs @@ -1,6 +1,7 @@ //! LSP diagnostic utility types. use std::fmt; +pub use helix_stdx::range::Range; use serde::{Deserialize, Serialize}; /// Describes the severity level of a [`Diagnostic`]. @@ -19,19 +20,6 @@ impl Default for Severity { } } -/// A range of `char`s within the text. -#[derive(Debug, Clone, Copy, PartialOrd, Ord, PartialEq, Eq)] -pub struct Range { - pub start: usize, - pub end: usize, -} - -impl Range { - pub fn contains(self, pos: usize) -> bool { - (self.start..self.end).contains(&pos) - } -} - #[derive(Debug, Eq, Hash, PartialEq, Clone, Deserialize, Serialize)] pub enum NumberOrString { Number(i32), diff --git a/helix-core/src/selection.rs b/helix-core/src/selection.rs index e29fcc94..76de6362 100644 --- a/helix-core/src/selection.rs +++ b/helix-core/src/selection.rs @@ -11,6 +11,7 @@ use crate::{ movement::Direction, Assoc, ChangeSet, RopeGraphemes, RopeSlice, }; +use helix_stdx::range::is_subset; use helix_stdx::rope::{self, RopeSliceExt}; use smallvec::{smallvec, SmallVec}; use std::{borrow::Cow, iter, slice}; @@ -401,6 +402,15 @@ impl From<(usize, usize)> for Range { } } +impl From<Range> for helix_stdx::Range { + fn from(range: Range) -> Self { + Self { + start: range.from(), + end: range.to(), + } + } +} + /// A selection consists of one or more selection ranges. /// invariant: A selection can never be empty (always contains at least primary range). #[derive(Debug, Clone, PartialEq, Eq)] @@ -513,6 +523,10 @@ impl Selection { } } + pub fn range_bounds(&self) -> impl Iterator<Item = helix_stdx::Range> + '_ { + self.ranges.iter().map(|&range| range.into()) + } + pub fn primary_index(&self) -> usize { self.primary_index } @@ -683,32 +697,9 @@ impl Selection { self.ranges.len() } - // returns true if self ⊇ other + /// returns true if self ⊇ other pub fn contains(&self, other: &Selection) -> bool { - let (mut iter_self, mut iter_other) = (self.iter(), other.iter()); - let (mut ele_self, mut ele_other) = (iter_self.next(), iter_other.next()); - - loop { - match (ele_self, ele_other) { - (Some(ra), Some(rb)) => { - if !ra.contains_range(rb) { - // `self` doesn't contain next element from `other`, advance `self`, we need to match all from `other` - ele_self = iter_self.next(); - } else { - // matched element from `other`, advance `other` - ele_other = iter_other.next(); - }; - } - (None, Some(_)) => { - // exhausted `self`, we can't match the reminder of `other` - return false; - } - (_, None) => { - // no elements from `other` left to match, `self` contains `other` - return true; - } - } - } + is_subset::<true>(self.range_bounds(), other.range_bounds()) } } diff --git a/helix-stdx/src/lib.rs b/helix-stdx/src/lib.rs index 19602c20..d09df587 100644 --- a/helix-stdx/src/lib.rs +++ b/helix-stdx/src/lib.rs @@ -1,4 +1,7 @@ pub mod env; pub mod faccess; pub mod path; +pub mod range; pub mod rope; + +pub use range::Range; diff --git a/helix-stdx/src/range.rs b/helix-stdx/src/range.rs new file mode 100644 index 00000000..0b241199 --- /dev/null +++ b/helix-stdx/src/range.rs @@ -0,0 +1,103 @@ +use std::ops::{self, RangeBounds}; + +/// A range of `char`s within the text. +#[derive(Debug, Clone, Copy, PartialOrd, Ord, PartialEq, Eq)] +pub struct Range<T = usize> { + pub start: T, + pub end: T, +} + +impl<T: PartialOrd> Range<T> { + pub fn contains(&self, other: Self) -> bool { + self.start <= other.start && other.end <= self.end + } + pub fn is_empty(&self) -> bool { + self.end <= self.start + } +} + +impl<T> RangeBounds<T> for Range<T> { + fn start_bound(&self) -> ops::Bound<&T> { + ops::Bound::Included(&self.start) + } + + fn end_bound(&self) -> ops::Bound<&T> { + ops::Bound::Excluded(&self.end) + } +} + +/// Returns true if all ranges yielded by `sub_set` are contained by +/// `super_set`. This is essentially an optimized implementation of +/// `sub_set.all(|rb| super_set.any(|ra| ra.contains(rb)))` that runs in O(m+n) +/// instead of O(mn) (and in many cases faster). +/// +/// Both iterators must uphold a the following invariants: +/// * ranges must not overlap (but they can be adjacent) +/// * ranges must be sorted +pub fn is_subset<const ALLOW_EMPTY: bool>( + mut super_set: impl Iterator<Item = Range>, + mut sub_set: impl Iterator<Item = Range>, +) -> bool { + let (mut super_range, mut sub_range) = (super_set.next(), sub_set.next()); + loop { + match (super_range, sub_range) { + // skip over irrelevant ranges + (Some(ra), Some(rb)) + if ra.end <= rb.start && (ra.start != rb.start || !ALLOW_EMPTY) => + { + super_range = super_set.next(); + } + (Some(ra), Some(rb)) => { + if ra.contains(rb) { + sub_range = sub_set.next(); + } else { + return false; + } + } + (None, Some(_)) => { + // exhausted `super_set`, we can't match the reminder of `sub_set` + return false; + } + (_, None) => { + // no elements from `sub_sut` left to match, `super_set` contains `sub_set` + return true; + } + } + } +} + +pub fn is_exact_subset( + mut super_set: impl Iterator<Item = Range>, + mut sub_set: impl Iterator<Item = Range>, +) -> bool { + let (mut super_range, mut sub_range) = (super_set.next(), sub_set.next()); + let mut super_range_matched = true; + loop { + match (super_range, sub_range) { + // skip over irrelevant ranges + (Some(ra), Some(rb)) if ra.end <= rb.start && ra.start < rb.start => { + if !super_range_matched { + return false; + } + super_range_matched = false; + super_range = super_set.next(); + } + (Some(ra), Some(rb)) => { + if ra.contains(rb) { + super_range_matched = true; + sub_range = sub_set.next(); + } else { + return false; + } + } + (None, Some(_)) => { + // exhausted `super_set`, we can't match the reminder of `sub_set` + return false; + } + (_, None) => { + // no elements from `sub_sut` left to match, `super_set` contains `sub_set` + return super_set.next().is_none(); + } + } + } +} |