aboutsummaryrefslogtreecommitdiff
path: root/helix-core/src/selection.rs
diff options
context:
space:
mode:
Diffstat (limited to 'helix-core/src/selection.rs')
-rw-r--r--helix-core/src/selection.rs446
1 files changed, 334 insertions, 112 deletions
diff --git a/helix-core/src/selection.rs b/helix-core/src/selection.rs
index d99e2aff..5f77d7ad 100644
--- a/helix-core/src/selection.rs
+++ b/helix-core/src/selection.rs
@@ -1,8 +1,13 @@
-//! Selections are the primary editing construct. Even a single cursor is defined as an empty
-//! single selection range.
+//! Selections are the primary editing construct. Even a single cursor is
+//! defined as a single empty or 1-wide selection range.
//!
//! All positioning is done via `char` offsets into the buffer.
-use crate::{Assoc, ChangeSet, RopeSlice};
+use crate::{
+ graphemes::{
+ ensure_grapheme_boundary_next, ensure_grapheme_boundary_prev, next_grapheme_boundary,
+ },
+ Assoc, ChangeSet, RopeSlice,
+};
use smallvec::{smallvec, SmallVec};
use std::borrow::Cow;
@@ -15,16 +20,39 @@ fn abs_difference(x: usize, y: usize) -> usize {
}
}
-/// A single selection range. Anchor-inclusive, head-exclusive.
+/// A single selection range.
+///
+/// The range consists of an "anchor" and "head" position in
+/// the text. The head is the part that the user moves when
+/// directly extending the selection. The head and anchor
+/// can be in any order: either can precede or follow the
+/// other in the text, and they can share the same position
+/// for a zero-width range.
+///
+/// Below are some example `Range` configurations to better
+/// illustrate. The anchor and head indices are show as
+/// "(anchor, head)", followed by example text with "[" and "]"
+/// inserted to visually represent the anchor and head positions:
+///
+/// - (0, 3): [Som]e text.
+/// - (3, 0): ]Som[e text.
+/// - (2, 7): So[me te]xt.
+/// - (1, 1): S[]ome text.
+///
+/// Ranges are considered to be inclusive on the left and
+/// exclusive on the right, regardless of anchor-head ordering.
+/// This means, for example, that non-zero-width ranges that
+/// are directly adjecent, sharing an edge, do not overlap.
+/// However, a zero-width range will overlap with the shared
+/// left-edge of another range.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Range {
- // TODO: optimize into u32
/// The anchor of the range: the side that doesn't move when extending.
pub anchor: usize,
/// The head of the range, moved when extending.
pub head: usize,
pub horiz: Option<u32>,
-} // TODO: might be cheaper to store normalized as from/to and an inverted flag
+}
impl Range {
pub fn new(anchor: usize, head: usize) -> Self {
@@ -62,25 +90,14 @@ impl Range {
/// Check two ranges for overlap.
#[must_use]
pub fn overlaps(&self, other: &Self) -> bool {
- // cursor overlap is checked differently
- if self.is_empty() {
- let pos = self.head;
- pos >= other.from() && other.to() >= pos
- } else {
- self.to() > other.from() && other.to() > self.from()
- }
+ // To my eye, it's non-obvious why this works, but I arrived
+ // at it after transforming the slower version that explicitly
+ // enumerated more cases. The unit tests are thorough.
+ self.from() == other.from() || (self.to() > other.from() && other.to() > self.from())
}
pub fn contains(&self, pos: usize) -> bool {
- if self.is_empty() {
- return false;
- }
-
- if self.anchor < self.head {
- self.anchor <= pos && pos < self.head
- } else {
- self.head < pos && pos <= self.anchor
- }
+ self.from() <= pos && pos < self.to()
}
/// Map a range through a set of changes. Returns a new range representing the same position
@@ -89,10 +106,10 @@ impl Range {
let anchor = changes.map_pos(self.anchor, Assoc::After);
let head = changes.map_pos(self.head, Assoc::After);
- // TODO: possibly unnecessary
- if self.anchor == anchor && self.head == head {
- return self;
- }
+ // We want to return a new `Range` with `horiz == None` every time,
+ // even if the anchor and head haven't changed, because we don't
+ // know if the *visual* position hasn't changed due to
+ // character-width or grapheme changes earlier in the text.
Self {
anchor,
head,
@@ -103,22 +120,100 @@ impl Range {
/// Extend the range to cover at least `from` `to`.
#[must_use]
pub fn extend(&self, from: usize, to: usize) -> Self {
- if from <= self.anchor && to >= self.anchor {
- return Self {
- anchor: from,
- head: to,
+ debug_assert!(from <= to);
+
+ if self.anchor <= self.head {
+ Self {
+ anchor: self.anchor.min(from),
+ head: self.head.max(to),
+ horiz: None,
+ }
+ } else {
+ Self {
+ anchor: self.anchor.max(to),
+ head: self.head.min(from),
horiz: None,
- };
+ }
}
+ }
- Self {
- anchor: self.anchor,
- head: if abs_difference(from, self.anchor) > abs_difference(to, self.anchor) {
- from
+ /// Returns a range that encompasses both input ranges.
+ ///
+ /// This is like `extend()`, but tries to negotiate the
+ /// anchor/head ordering between the two input ranges.
+ #[must_use]
+ pub fn merge(&self, other: Self) -> Self {
+ if self.anchor > self.head && other.anchor > other.head {
+ Range {
+ anchor: self.anchor.max(other.anchor),
+ head: self.head.min(other.head),
+ horiz: None,
+ }
+ } else {
+ Range {
+ anchor: self.from().min(other.from()),
+ head: self.to().max(other.to()),
+ horiz: None,
+ }
+ }
+ }
+
+ /// Compute a possibly new range from this range, attempting to ensure
+ /// a minimum range width of 1 char by shifting the head in the forward
+ /// direction as needed.
+ ///
+ /// This method will never shift the anchor, and will only shift the
+ /// head in the forward direction. Therefore, this method can fail
+ /// at ensuring the minimum width if and only if the passed range is
+ /// both zero-width and at the end of the `RopeSlice`.
+ ///
+ /// If the input range is grapheme-boundary aligned, the returned range
+ /// will also be. Specifically, if the head needs to shift to achieve
+ /// the minimum width, it will shift to the next grapheme boundary.
+ #[must_use]
+ #[inline]
+ pub fn min_width_1(&self, slice: RopeSlice) -> Self {
+ if self.anchor == self.head {
+ Range {
+ anchor: self.anchor,
+ head: next_grapheme_boundary(slice, self.head),
+ horiz: self.horiz,
+ }
+ } else {
+ *self
+ }
+ }
+
+ /// Compute a possibly new range from this range, with its ends
+ /// shifted as needed to align with grapheme boundaries.
+ ///
+ /// Zero-width ranges will always stay zero-width, and non-zero-width
+ /// ranges will never collapse to zero-width.
+ #[must_use]
+ pub fn grapheme_aligned(&self, slice: RopeSlice) -> Self {
+ use std::cmp::Ordering;
+ let (new_anchor, new_head) = match self.anchor.cmp(&self.head) {
+ Ordering::Equal => {
+ let pos = ensure_grapheme_boundary_prev(slice, self.anchor);
+ (pos, pos)
+ }
+ Ordering::Less => (
+ ensure_grapheme_boundary_prev(slice, self.anchor),
+ ensure_grapheme_boundary_next(slice, self.head),
+ ),
+ Ordering::Greater => (
+ ensure_grapheme_boundary_next(slice, self.anchor),
+ ensure_grapheme_boundary_prev(slice, self.head),
+ ),
+ };
+ Range {
+ anchor: new_anchor,
+ head: new_head,
+ horiz: if new_anchor == self.anchor {
+ self.horiz
} else {
- to
+ None
},
- horiz: None,
}
}
@@ -126,7 +221,7 @@ impl Range {
#[inline]
pub fn fragment<'a, 'b: 'a>(&'a self, text: RopeSlice<'b>) -> Cow<'b, str> {
- Cow::from(text.slice(self.from()..self.to() + 1))
+ text.slice(self.from()..self.to()).into()
}
}
@@ -165,10 +260,8 @@ impl Selection {
}
pub fn push(mut self, range: Range) -> Self {
- let index = self.ranges.len();
self.ranges.push(range);
-
- Self::normalize(self.ranges, index)
+ self.normalize()
}
// replace_range
@@ -214,80 +307,68 @@ impl Selection {
Self::single(pos, pos)
}
- fn normalize(mut ranges: SmallVec<[Range; 1]>, mut primary_index: usize) -> Self {
- let primary = ranges[primary_index];
- ranges.sort_unstable_by_key(Range::from);
- primary_index = ranges.iter().position(|&range| range == primary).unwrap();
-
- let mut result = SmallVec::with_capacity(ranges.len()); // approx
-
- // TODO: we could do with one vec by removing elements as we mutate
-
- let mut i = 0;
-
- for range in ranges.into_iter() {
- // if previous value exists
- if let Some(prev) = result.last_mut() {
- // and we overlap it
-
- // TODO: we used to simply check range.from() <(=) prev.to()
- // avoiding two comparisons
- if range.overlaps(prev) {
- let from = prev.from();
- let to = std::cmp::max(range.to(), prev.to());
-
- if i <= primary_index {
- primary_index -= 1
- }
-
- // merge into previous
- if range.anchor > range.head {
- prev.anchor = to;
- prev.head = from;
- } else {
- prev.anchor = from;
- prev.head = to;
- }
- continue;
+ /// Normalizes a `Selection`.
+ fn normalize(mut self) -> Self {
+ let primary = self.ranges[self.primary_index];
+ self.ranges.sort_unstable_by_key(Range::from);
+ self.primary_index = self
+ .ranges
+ .iter()
+ .position(|&range| range == primary)
+ .unwrap();
+
+ let mut prev_i = 0;
+ for i in 1..self.ranges.len() {
+ if self.ranges[prev_i].overlaps(&self.ranges[i]) {
+ if i == self.primary_index {
+ self.primary_index = prev_i;
}
+ self.ranges[prev_i] = self.ranges[prev_i].merge(self.ranges[i]);
+ } else {
+ prev_i += 1;
+ self.ranges[prev_i] = self.ranges[i];
}
-
- result.push(range);
- i += 1
}
- Self {
- ranges: result,
- primary_index,
- }
+ self.ranges.truncate(prev_i + 1);
+
+ self
}
// TODO: consume an iterator or a vec to reduce allocations?
#[must_use]
pub fn new(ranges: SmallVec<[Range; 1]>, primary_index: usize) -> Self {
assert!(!ranges.is_empty());
+ debug_assert!(primary_index < ranges.len());
- // fast path for a single selection (cursor)
- if ranges.len() == 1 {
- return Self {
- ranges,
- primary_index: 0,
- };
+ let mut selection = Self {
+ ranges,
+ primary_index,
+ };
+
+ if selection.ranges.len() > 1 {
+ // TODO: only normalize if needed (any ranges out of order)
+ selection = selection.normalize();
}
- // TODO: only normalize if needed (any ranges out of order)
- Self::normalize(ranges, primary_index)
+ selection
}
- /// Takes a closure and maps each selection over the closure.
- pub fn transform<F>(&self, f: F) -> Self
+ /// Takes a closure and maps each `Range` over the closure.
+ pub fn transform<F>(mut self, f: F) -> Self
where
F: Fn(Range) -> Range,
{
- Self::new(
- self.ranges.iter().copied().map(f).collect(),
- self.primary_index,
- )
+ for range in self.ranges.iter_mut() {
+ *range = f(*range)
+ }
+
+ self.normalize()
+ }
+
+ /// A convenience short-cut for `transform(|r| r.min_width_1(text))`.
+ pub fn min_width_1(mut self, text: RopeSlice) -> Self {
+ self.transform(|r| r.min_width_1(text))
}
pub fn fragments<'a>(&'a self, text: RopeSlice<'a>) -> impl Iterator<Item = Cow<str>> + 'a {
@@ -353,7 +434,7 @@ pub fn select_on_matches(
let start = text.byte_to_char(start_byte + mat.start());
let end = text.byte_to_char(start_byte + mat.end());
- result.push(Range::new(start, end.saturating_sub(1)));
+ result.push(Range::new(start, end));
}
}
@@ -374,6 +455,12 @@ pub fn split_on_matches(
let mut result = SmallVec::with_capacity(selection.len());
for sel in selection {
+ // Special case: zero-width selection.
+ if sel.from() == sel.to() {
+ result.push(*sel);
+ continue;
+ }
+
// TODO: can't avoid occasional allocations since Regex can't operate on chunks yet
let fragment = sel.fragment(text);
@@ -386,13 +473,12 @@ pub fn split_on_matches(
for mat in regex.find_iter(&fragment) {
// TODO: retain range direction
-
let end = text.byte_to_char(start_byte + mat.start());
- result.push(Range::new(start, end.saturating_sub(1)));
+ result.push(Range::new(start, end));
start = text.byte_to_char(start_byte + mat.end());
}
- if start <= sel_end {
+ if start < sel_end {
result.push(Range::new(start, sel_end));
}
}
@@ -474,7 +560,7 @@ mod test {
.collect::<Vec<String>>()
.join(",");
- assert_eq!(res, "8/10,10/12");
+ assert_eq!(res, "8/10,10/12,12/12");
}
#[test]
@@ -488,35 +574,171 @@ mod test {
assert_eq!(range.contains(13), false);
let range = Range::new(9, 6);
- assert_eq!(range.contains(9), true);
+ assert_eq!(range.contains(9), false);
assert_eq!(range.contains(7), true);
- assert_eq!(range.contains(6), false);
+ assert_eq!(range.contains(6), true);
+ }
+
+ #[test]
+ fn test_overlaps() {
+ fn overlaps(a: (usize, usize), b: (usize, usize)) -> bool {
+ Range::new(a.0, a.1).overlaps(&Range::new(b.0, b.1))
+ }
+
+ // Two non-zero-width ranges, no overlap.
+ assert!(!overlaps((0, 3), (3, 6)));
+ assert!(!overlaps((0, 3), (6, 3)));
+ assert!(!overlaps((3, 0), (3, 6)));
+ assert!(!overlaps((3, 0), (6, 3)));
+ assert!(!overlaps((3, 6), (0, 3)));
+ assert!(!overlaps((3, 6), (3, 0)));
+ assert!(!overlaps((6, 3), (0, 3)));
+ assert!(!overlaps((6, 3), (3, 0)));
+
+ // Two non-zero-width ranges, overlap.
+ assert!(overlaps((0, 4), (3, 6)));
+ assert!(overlaps((0, 4), (6, 3)));
+ assert!(overlaps((4, 0), (3, 6)));
+ assert!(overlaps((4, 0), (6, 3)));
+ assert!(overlaps((3, 6), (0, 4)));
+ assert!(overlaps((3, 6), (4, 0)));
+ assert!(overlaps((6, 3), (0, 4)));
+ assert!(overlaps((6, 3), (4, 0)));
+
+ // Zero-width and non-zero-width range, no overlap.
+ assert!(!overlaps((0, 3), (3, 3)));
+ assert!(!overlaps((3, 0), (3, 3)));
+ assert!(!overlaps((3, 3), (0, 3)));
+ assert!(!overlaps((3, 3), (3, 0)));
+
+ // Zero-width and non-zero-width range, overlap.
+ assert!(overlaps((1, 4), (1, 1)));
+ assert!(overlaps((4, 1), (1, 1)));
+ assert!(overlaps((1, 1), (1, 4)));
+ assert!(overlaps((1, 1), (4, 1)));
+
+ assert!(overlaps((1, 4), (3, 3)));
+ assert!(overlaps((4, 1), (3, 3)));
+ assert!(overlaps((3, 3), (1, 4)));
+ assert!(overlaps((3, 3), (4, 1)));
+
+ // Two zero-width ranges, no overlap.
+ assert!(!overlaps((0, 0), (1, 1)));
+ assert!(!overlaps((1, 1), (0, 0)));
+
+ // Two zero-width ranges, overlap.
+ assert!(overlaps((1, 1), (1, 1)));
+ }
+
+ #[test]
+ fn test_graphem_aligned() {
+ let r = Rope::from_str("\r\nHi\r\n");
+ let s = r.slice(..);
+
+ // Zero-width.
+ assert_eq!(Range::new(0, 0).grapheme_aligned(s), Range::new(0, 0));
+ assert_eq!(Range::new(1, 1).grapheme_aligned(s), Range::new(0, 0));
+ assert_eq!(Range::new(2, 2).grapheme_aligned(s), Range::new(2, 2));
+ assert_eq!(Range::new(3, 3).grapheme_aligned(s), Range::new(3, 3));
+ assert_eq!(Range::new(4, 4).grapheme_aligned(s), Range::new(4, 4));
+ assert_eq!(Range::new(5, 5).grapheme_aligned(s), Range::new(4, 4));
+ assert_eq!(Range::new(6, 6).grapheme_aligned(s), Range::new(6, 6));
+
+ // Forward.
+ assert_eq!(Range::new(0, 1).grapheme_aligned(s), Range::new(0, 2));
+ assert_eq!(Range::new(1, 2).grapheme_aligned(s), Range::new(0, 2));
+ assert_eq!(Range::new(2, 3).grapheme_aligned(s), Range::new(2, 3));
+ assert_eq!(Range::new(3, 4).grapheme_aligned(s), Range::new(3, 4));
+ assert_eq!(Range::new(4, 5).grapheme_aligned(s), Range::new(4, 6));
+ assert_eq!(Range::new(5, 6).grapheme_aligned(s), Range::new(4, 6));
+
+ assert_eq!(Range::new(0, 2).grapheme_aligned(s), Range::new(0, 2));
+ assert_eq!(Range::new(1, 3).grapheme_aligned(s), Range::new(0, 3));
+ assert_eq!(Range::new(2, 4).grapheme_aligned(s), Range::new(2, 4));
+ assert_eq!(Range::new(3, 5).grapheme_aligned(s), Range::new(3, 6));
+ assert_eq!(Range::new(4, 6).grapheme_aligned(s), Range::new(4, 6));
+
+ // Reverse.
+ assert_eq!(Range::new(1, 0).grapheme_aligned(s), Range::new(2, 0));
+ assert_eq!(Range::new(2, 1).grapheme_aligned(s), Range::new(2, 0));
+ assert_eq!(Range::new(3, 2).grapheme_aligned(s), Range::new(3, 2));
+ assert_eq!(Range::new(4, 3).grapheme_aligned(s), Range::new(4, 3));
+ assert_eq!(Range::new(5, 4).grapheme_aligned(s), Range::new(6, 4));
+ assert_eq!(Range::new(6, 5).grapheme_aligned(s), Range::new(6, 4));
+
+ assert_eq!(Range::new(2, 0).grapheme_aligned(s), Range::new(2, 0));
+ assert_eq!(Range::new(3, 1).grapheme_aligned(s), Range::new(3, 0));
+ assert_eq!(Range::new(4, 2).grapheme_aligned(s), Range::new(4, 2));
+ assert_eq!(Range::new(5, 3).grapheme_aligned(s), Range::new(6, 3));
+ assert_eq!(Range::new(6, 4).grapheme_aligned(s), Range::new(6, 4));
+ }
+
+ #[test]
+ fn test_min_width_1() {
+ let r = Rope::from_str("\r\nHi\r\n");
+ let s = r.slice(..);
+
+ // Zero-width.
+ assert_eq!(Range::new(0, 0).min_width_1(s), Range::new(0, 2));
+ assert_eq!(Range::new(1, 1).min_width_1(s), Range::new(1, 2));
+ assert_eq!(Range::new(2, 2).min_width_1(s), Range::new(2, 3));
+ assert_eq!(Range::new(3, 3).min_width_1(s), Range::new(3, 4));
+ assert_eq!(Range::new(4, 4).min_width_1(s), Range::new(4, 6));
+ assert_eq!(Range::new(5, 5).min_width_1(s), Range::new(5, 6));
+ assert_eq!(Range::new(6, 6).min_width_1(s), Range::new(6, 6));
+
+ // Forward.
+ assert_eq!(Range::new(0, 1).min_width_1(s), Range::new(0, 1));
+ assert_eq!(Range::new(1, 2).min_width_1(s), Range::new(1, 2));
+ assert_eq!(Range::new(2, 3).min_width_1(s), Range::new(2, 3));
+ assert_eq!(Range::new(3, 4).min_width_1(s), Range::new(3, 4));
+ assert_eq!(Range::new(4, 5).min_width_1(s), Range::new(4, 5));
+ assert_eq!(Range::new(5, 6).min_width_1(s), Range::new(5, 6));
+
+ // Reverse.
+ assert_eq!(Range::new(1, 0).min_width_1(s), Range::new(1, 0));
+ assert_eq!(Range::new(2, 1).min_width_1(s), Range::new(2, 1));
+ assert_eq!(Range::new(3, 2).min_width_1(s), Range::new(3, 2));
+ assert_eq!(Range::new(4, 3).min_width_1(s), Range::new(4, 3));
+ assert_eq!(Range::new(5, 4).min_width_1(s), Range::new(5, 4));
+ assert_eq!(Range::new(6, 5).min_width_1(s), Range::new(6, 5));
}
#[test]
fn test_split_on_matches() {
use crate::regex::Regex;
- let text = Rope::from("abcd efg wrs xyz 123 456");
+ let text = Rope::from(" abcd efg wrs xyz 123 456");
- let selection = Selection::new(smallvec![Range::new(0, 8), Range::new(10, 19),], 0);
+ let selection = Selection::new(smallvec![Range::new(0, 9), Range::new(11, 20),], 0);
let result = split_on_matches(text.slice(..), &selection, &Regex::new(r"\s+").unwrap());
assert_eq!(
result.ranges(),
&[
- Range::new(0, 3),
- Range::new(5, 7),
- Range::new(10, 11),
- Range::new(15, 17),
- Range::new(19, 19),
+ // TODO: rather than this behavior, maybe we want it
+ // to be based on which side is the anchor?
+ //
+ // We get a leading zero-width range when there's
+ // a leading match because ranges are inclusive on
+ // the left. Imagine, for example, if the entire
+ // selection range were matched: you'd still want
+ // at least one range to remain after the split.
+ Range::new(0, 0),
+ Range::new(1, 5),
+ Range::new(6, 9),
+ Range::new(11, 13),
+ Range::new(16, 19),
+ // In contrast to the comment above, there is no
+ // _trailing_ zero-width range despite the trailing
+ // match, because ranges are exclusive on the right.
]
);
assert_eq!(
result.fragments(text.slice(..)).collect::<Vec<_>>(),
- &["abcd", "efg", "rs", "xyz", "1"]
+ &["", "abcd", "efg", "rs", "xyz"]
);
}
}
generated by cgit v1.2.3-70-g09d2 (git 2.47.1) at 2024-12-27 11:46:57 +0000