indigo_core/
rope.rs

1use indigo_kernel::{
2    display_width::DisplayWidth as _,
3    grapheme::{
4        Graphemes, ceil_grapheme_boundary, floor_grapheme_boundary, is_grapheme_boundary,
5        is_grapheme_start, next_grapheme_boundary, prev_grapheme_boundary,
6    },
7};
8use regex_cursor::{Cursor, IntoCursor};
9use ropey::{LineType, Rope, RopeSlice};
10use std::ops::{Bound, RangeBounds};
11
12pub const LINE_TYPE: LineType = LineType::LF_CR;
13
14pub trait RopeExt {
15    fn as_slice(&self) -> RopeSlice<'_>;
16
17    /// <https://docs.rs/ropey/2.0.0-beta.1/ropey/#a-note-about-line-breaks>
18    /// <https://github.com/cessen/ropey/issues/60>
19    fn len_lines_unix(&self) -> usize {
20        let rope = self.as_slice();
21        if rope.len() == 0 {
22            return 0;
23        }
24        let last_byte = rope.byte(rope.len() - 1);
25        rope.len_lines(LINE_TYPE) - if last_byte == b'\n' { 1 } else { 0 }
26    }
27
28    fn find_next_byte<R>(&self, byte_range: R, needles: &[u8]) -> Option<usize>
29    where
30        R: RangeBounds<usize> + Clone,
31    {
32        if needles.is_empty() {
33            return None;
34        }
35
36        let rope = self.as_slice().slice(byte_range.clone());
37
38        let start = match byte_range.start_bound() {
39            Bound::Included(n) => *n,
40            Bound::Excluded(_) => unreachable!("wtf"),
41            Bound::Unbounded => 0,
42        };
43
44        let mut needle_index: Option<usize> = None;
45
46        for chunk in needles.chunks(3) {
47            match chunk.len() {
48                3 => {
49                    let haystack = rope.chunks().map(|c| c.as_bytes());
50                    if let Some(pos) = memchr3(chunk[0], chunk[1], chunk[2], haystack) {
51                        needle_index = Some(needle_index.map_or(pos, |current| current.min(pos)));
52                    }
53                }
54                _ => {
55                    for &needle in chunk {
56                        let haystack = rope.chunks().map(|c| c.as_bytes());
57                        if let Some(pos) = memchr(needle, haystack) {
58                            needle_index =
59                                Some(needle_index.map_or(pos, |current| current.min(pos)));
60                        }
61                    }
62                }
63            }
64        }
65
66        needle_index.map(|byte_index| start + byte_index)
67    }
68
69    fn find_prev_byte<R>(&self, byte_range: R, needles: &[u8]) -> Option<usize>
70    where
71        R: RangeBounds<usize> + Clone,
72    {
73        if needles.is_empty() {
74            return None;
75        }
76
77        let rope = self.as_slice().slice(byte_range.clone());
78
79        let end = match byte_range.end_bound() {
80            Bound::Included(n) => *n,
81            Bound::Excluded(n) => n.saturating_sub(1),
82            Bound::Unbounded => rope.len().saturating_sub(1),
83        };
84
85        let mut needle_index: Option<usize> = None;
86
87        for chunk in needles.chunks(3) {
88            match chunk.len() {
89                3 => {
90                    let haystack = rope
91                        .chunks_at(rope.len())
92                        .0
93                        .reversed()
94                        .map(|c| c.as_bytes());
95                    if let Some(pos) = memrchr3(chunk[0], chunk[1], chunk[2], haystack) {
96                        needle_index = Some(needle_index.map_or(pos, |current| current.min(pos)));
97                    }
98                }
99                _ => {
100                    for &needle in chunk {
101                        let haystack = rope
102                            .chunks_at(rope.len())
103                            .0
104                            .reversed()
105                            .map(|c| c.as_bytes());
106                        if let Some(pos) = memrchr(needle, haystack) {
107                            needle_index =
108                                Some(needle_index.map_or(pos, |current| current.min(pos)));
109                        }
110                    }
111                }
112            }
113        }
114
115        needle_index.map(|byte_index| end - byte_index)
116    }
117
118    fn get_grapheme(&self, byte_index: usize) -> Option<RopeSlice<'_>> {
119        let rope = self.as_slice();
120        rope.next_grapheme_boundary(byte_index)
121            .map(|end| rope.slice(byte_index..end))
122    }
123
124    fn grapheme(&self, byte_index: usize) -> RopeSlice<'_> {
125        self.get_grapheme(byte_index).unwrap()
126    }
127
128    fn graphemes(&self) -> Graphemes<'_> {
129        Graphemes::new(&self.as_slice())
130    }
131
132    fn is_grapheme_boundary(&self, byte_offset: usize) -> bool {
133        is_grapheme_boundary(&self.as_slice(), byte_offset)
134    }
135
136    fn is_grapheme_start(&self, byte_index: usize) -> bool {
137        is_grapheme_start(&self.as_slice(), byte_index)
138    }
139
140    fn snap_to_grapheme_start(&self, byte_index: usize) -> Option<usize> {
141        let rope = self.as_slice();
142        let last = self.last_grapheme_start()?;
143        Some(floor_grapheme_boundary(&rope, byte_index.min(last)))
144    }
145
146    fn last_grapheme_start(&self) -> Option<usize> {
147        let rope = self.as_slice();
148        prev_grapheme_boundary(&rope, rope.len())
149    }
150
151    fn prev_grapheme_boundary(&self, byte_offset: usize) -> Option<usize> {
152        prev_grapheme_boundary(&self.as_slice(), byte_offset)
153    }
154
155    fn next_grapheme_boundary(&self, byte_offset: usize) -> Option<usize> {
156        next_grapheme_boundary(&self.as_slice(), byte_offset)
157    }
158
159    fn floor_grapheme_boundary(&self, byte_offset: usize) -> usize {
160        floor_grapheme_boundary(&self.as_slice(), byte_offset)
161    }
162
163    fn ceil_grapheme_boundary(&self, byte_offset: usize) -> usize {
164        ceil_grapheme_boundary(&self.as_slice(), byte_offset)
165    }
166
167    fn display_column(&self, byte_index: usize) -> usize {
168        let rope = self.as_slice();
169        let line_index = rope.byte_to_line_idx(byte_index, LINE_TYPE);
170        let line_byte_index = rope.line_to_byte_idx(line_index, LINE_TYPE);
171        rope.slice(line_byte_index..byte_index).display_width()
172    }
173}
174
175impl RopeExt for RopeSlice<'_> {
176    fn as_slice(&self) -> RopeSlice<'_> {
177        *self
178    }
179}
180
181impl RopeExt for Rope {
182    fn as_slice(&self) -> RopeSlice<'_> {
183        self.slice(0..)
184    }
185}
186
187#[derive(Clone, Copy)]
188enum Pos {
189    ChunkStart,
190    ChunkEnd,
191}
192
193pub struct RegexCursorInput<'a>(RopeSlice<'a>);
194
195impl<'a> From<RopeSlice<'a>> for RegexCursorInput<'a> {
196    fn from(slice: RopeSlice<'a>) -> Self {
197        Self(slice)
198    }
199}
200
201impl<'a> From<&'a Rope> for RegexCursorInput<'a> {
202    fn from(rope: &'a Rope) -> Self {
203        Self(rope.slice(..))
204    }
205}
206
207impl<'a> IntoCursor for RegexCursorInput<'a> {
208    type Cursor = RopeyCursor<'a>;
209
210    fn into_cursor(self) -> Self::Cursor {
211        RopeyCursor::new(self.0)
212    }
213}
214
215#[derive(Clone)]
216pub struct RopeyCursor<'a> {
217    iter: ropey::iter::Chunks<'a>,
218    current: &'a [u8],
219    pos: Pos,
220    len: usize,
221    offset: usize,
222}
223
224impl<'a> RopeyCursor<'a> {
225    #[must_use]
226    pub fn new(slice: RopeSlice<'a>) -> Self {
227        let iter = slice.chunks();
228        let mut res = Self {
229            current: &[],
230            iter,
231            pos: Pos::ChunkEnd,
232            len: slice.len(),
233            offset: 0,
234        };
235        res.advance();
236        res
237    }
238
239    #[must_use]
240    pub fn at(slice: RopeSlice<'a>, at: usize) -> Self {
241        let (iter, offset) = slice.chunks_at(at);
242        if offset == slice.len() {
243            let mut res = Self {
244                current: &[],
245                iter,
246                pos: Pos::ChunkStart,
247                len: slice.len(),
248                offset,
249            };
250            res.backtrack();
251            res
252        } else {
253            let mut res = Self {
254                current: &[],
255                iter,
256                pos: Pos::ChunkEnd,
257                len: slice.len(),
258                offset,
259            };
260            res.advance();
261            res
262        }
263    }
264}
265
266impl Cursor for RopeyCursor<'_> {
267    fn chunk(&self) -> &[u8] {
268        self.current
269    }
270
271    fn advance(&mut self) -> bool {
272        match self.pos {
273            Pos::ChunkStart => {
274                self.iter.next();
275                self.pos = Pos::ChunkEnd;
276            }
277            Pos::ChunkEnd => (),
278        }
279        for next in self.iter.by_ref() {
280            if next.is_empty() {
281                continue;
282            }
283            self.offset += self.current.len();
284            self.current = next.as_bytes();
285            return true;
286        }
287        false
288    }
289
290    fn backtrack(&mut self) -> bool {
291        match self.pos {
292            Pos::ChunkStart => {}
293            Pos::ChunkEnd => {
294                self.iter.prev();
295                self.pos = Pos::ChunkStart;
296            }
297        }
298        while let Some(prev) = self.iter.prev() {
299            if prev.is_empty() {
300                continue;
301            }
302            self.offset -= prev.len();
303            self.current = prev.as_bytes();
304            return true;
305        }
306        false
307    }
308
309    fn utf8_aware(&self) -> bool {
310        true
311    }
312
313    fn total_bytes(&self) -> Option<usize> {
314        Some(self.len)
315    }
316
317    fn offset(&self) -> usize {
318        self.offset
319    }
320}
321
322/// Variant of [`memchr::memchr()`] for a discontiguous haystack.
323pub fn memchr<'a>(needle: u8, haystacks: impl IntoIterator<Item = &'a [u8]>) -> Option<usize> {
324    let mut haystacks_byte_index = 0;
325    for haystack in haystacks {
326        if let Some(needle_byte_index) =
327            memchr::memchr(needle, haystack).map(|i| haystacks_byte_index + i)
328        {
329            return Some(needle_byte_index);
330        }
331        haystacks_byte_index += haystack.len();
332    }
333    None
334}
335
336/// Variant of [`memchr::memrchr()`] for a discontiguous haystack.
337///
338/// Assumes byte slices are provided in reverse order, and returned byte index is from the back. For
339/// example:
340///
341/// ```rust
342/// # use indigo_core::rope::memrchr;
343/// let haystacks = ["123", "456"].iter().rev().map(|s| s.as_bytes());
344/// assert_eq!(memrchr(b'4', haystacks), Some(2));
345/// ```
346pub fn memrchr<'a>(needle: u8, haystacks: impl IntoIterator<Item = &'a [u8]>) -> Option<usize> {
347    let mut haystacks_byte_index = 0; // Starting from the end
348    for haystack in haystacks {
349        if let Some(needle_byte_index) = memchr::memrchr(needle, haystack)
350            .map(|i| haystacks_byte_index + (haystack.len() - (i + 1)))
351        {
352            return Some(needle_byte_index);
353        }
354        haystacks_byte_index += haystack.len();
355    }
356    None
357}
358
359/// Variant of [`memchr::memchr3()`] for a discontiguous haystack. See [`memchr()`] for more info.
360pub fn memchr3<'a>(
361    needle1: u8,
362    needle2: u8,
363    needle3: u8,
364    haystacks: impl IntoIterator<Item = &'a [u8]>,
365) -> Option<usize> {
366    let mut haystacks_byte_index = 0;
367    for haystack in haystacks {
368        if let Some(needle_byte_index) =
369            memchr::memchr3(needle1, needle2, needle3, haystack).map(|i| haystacks_byte_index + i)
370        {
371            return Some(needle_byte_index);
372        }
373        haystacks_byte_index += haystack.len();
374    }
375    None
376}
377
378/// Variant of [`memchr::memrchr3()`] for a discontiguous haystack. See [`memrchr()`] for more info.
379pub fn memrchr3<'a>(
380    needle1: u8,
381    needle2: u8,
382    needle3: u8,
383    haystacks: impl IntoIterator<Item = &'a [u8]>,
384) -> Option<usize> {
385    let mut haystacks_byte_index = 0; // Starting from the end
386    for haystack in haystacks {
387        if let Some(needle_byte_index) = memchr::memrchr3(needle1, needle2, needle3, haystack)
388            .map(|i| haystacks_byte_index + (haystack.len() - (i + 1)))
389        {
390            return Some(needle_byte_index);
391        }
392        haystacks_byte_index += haystack.len();
393    }
394    None
395}
396
397#[cfg(test)]
398mod tests {
399    use super::*;
400
401    #[test]
402    fn rope_length() {
403        let rope = Rope::default();
404        assert_eq!(rope.chars().count(), 0);
405        assert_eq!(rope.len_lines(LINE_TYPE), 1);
406        assert_eq!(rope.len_lines_unix(), 0);
407
408        let rope = Rope::from_str("x");
409        assert_eq!(rope.chars().count(), 1);
410        assert_eq!(rope.len_lines(LINE_TYPE), 1);
411        assert_eq!(rope.len_lines_unix(), 1);
412
413        let rope = Rope::from_str("\n");
414        assert_eq!(rope.chars().count(), 1);
415        assert_eq!(rope.len_lines(LINE_TYPE), 2);
416        assert_eq!(rope.len_lines_unix(), 1);
417
418        let rope = Rope::from_str("x\n");
419        assert_eq!(rope.chars().count(), 2);
420        assert_eq!(rope.len_lines(LINE_TYPE), 2);
421        assert_eq!(rope.len_lines_unix(), 1);
422
423        let rope = Rope::from_str("x\ny\nz");
424        assert_eq!(rope.chars().count(), 5);
425        assert_eq!(rope.len_lines(LINE_TYPE), 3);
426        assert_eq!(rope.len_lines_unix(), 3);
427
428        let rope = Rope::from_str("x\ny\nz\n");
429        assert_eq!(rope.chars().count(), 6);
430        assert_eq!(rope.len_lines(LINE_TYPE), 4);
431        assert_eq!(rope.len_lines_unix(), 3);
432    }
433
434    #[test]
435    fn rope_char() {
436        assert_eq!(Rope::default().get_char(0).ok(), None);
437        assert_eq!(Rope::default().get_char(1).ok(), None);
438        assert_eq!(Rope::from_str("xyz").get_char(0).ok(), Some('x'));
439        assert_eq!(Rope::from_str("xyz").get_char(1).ok(), Some('y'));
440        assert_eq!(Rope::from_str("xyz").get_char(2).ok(), Some('z'));
441        assert_eq!(Rope::from_str("xyz").get_char(3).ok(), None);
442    }
443
444    #[test]
445    fn rope_line() {
446        assert_eq!(Rope::default().get_line(0, LINE_TYPE), Some("".into()));
447        assert_eq!(Rope::from_str("x\ny\nz").get_line(9, LINE_TYPE), None);
448        assert_eq!(Rope::from_str("x").get_line(0, LINE_TYPE), Some("x".into()));
449        assert_eq!(
450            Rope::from_str("x\n").get_line(0, LINE_TYPE),
451            Some("x\n".into())
452        );
453        assert_eq!(
454            Rope::from_str("\nx").get_line(0, LINE_TYPE),
455            Some("\n".into())
456        );
457        assert_eq!(
458            Rope::from_str("\nx").get_line(1, LINE_TYPE),
459            Some("x".into())
460        );
461        assert_eq!(
462            Rope::from_str("x\ny\r\nz").get_line(0, LINE_TYPE),
463            Some("x\n".into())
464        );
465        assert_eq!(
466            Rope::from_str("x\ny\r\nz").get_line(1, LINE_TYPE),
467            Some("y\r\n".into())
468        );
469        assert_eq!(
470            Rope::from_str("x\ny\r\nz").get_line(2, LINE_TYPE),
471            Some("z".into())
472        );
473    }
474
475    #[test]
476    fn test_memchr() {
477        let haystacks = || ["foo", "bar", "baz", "qux"].iter().map(|s| s.as_bytes());
478        assert_eq!(memchr(b'0', haystacks()), None);
479        assert_eq!(memchr(b'f', haystacks()), Some(0));
480        assert_eq!(memchr(b'o', haystacks()), Some(1));
481        assert_eq!(memchr(b'a', haystacks()), Some(4));
482        assert_eq!(memchr(b'x', haystacks()), Some(11));
483    }
484
485    #[test]
486    fn test_memrchr() {
487        let haystacks = || {
488            ["foo", "bar", "baz", "qux"]
489                .iter()
490                .rev()
491                .map(|s| s.as_bytes())
492        };
493        assert_eq!(memrchr(b'0', haystacks()), None);
494        assert_eq!(memrchr(b'f', haystacks()), Some(11));
495        assert_eq!(memrchr(b'o', haystacks()), Some(9));
496        assert_eq!(memrchr(b'a', haystacks()), Some(4));
497        assert_eq!(memrchr(b'x', haystacks()), Some(0));
498    }
499
500    #[test]
501    fn test_find_next_byte() {
502        let mut rope = Rope::new();
503        while rope.chunks().count() < 10 {
504            rope.insert(rope.len(), "hello");
505        }
506        let mut length = rope.len();
507        let byte_index = length / 2;
508        rope.insert(byte_index, "!?");
509        length += "!?".len();
510        assert_eq!(rope.find_next_byte(.., b"!?"), Some(byte_index));
511        assert_eq!(
512            rope.find_next_byte(0..(length / 3) * 2, b"!?"),
513            Some(byte_index)
514        );
515        assert_eq!(rope.find_next_byte(0..length / 3, b"!?"), None);
516        assert_eq!(rope.find_next_byte(0..length, b"!o"), Some(4));
517    }
518
519    // TODO: Test finding multiple needles backward.
520    #[test]
521    fn test_find_prev_byte() {
522        let mut rope = Rope::new();
523        while rope.chunks().count() < 10 {
524            rope.insert(rope.len(), "hello");
525        }
526        let mut length = rope.len();
527        let byte_index = length / 2;
528        rope.insert(byte_index, "!");
529        length += "!".len();
530        assert_eq!(rope.find_prev_byte(.., b"!"), Some(byte_index));
531        assert_eq!(
532            rope.find_prev_byte(0..(length / 3) * 2, b"!"),
533            Some(byte_index)
534        );
535        assert_eq!(rope.find_prev_byte(0..length / 3, b"!"), None);
536    }
537
538    #[test]
539    fn graphemes() {
540        let a = |text: &str| {
541            Rope::from_str(text)
542                .graphemes()
543                .map(String::from)
544                .collect::<Vec<_>>()
545        };
546        let e = |graphemes: &'static [&str]| {
547            graphemes
548                .iter()
549                .copied()
550                .map(String::from)
551                .collect::<Vec<_>>()
552        };
553        assert_eq!(a(""), e(&[]));
554        assert_eq!(a("hello"), e(&["h", "e", "l", "l", "o"]));
555        assert_eq!(a("x\t\n🇯🇵👨‍👨‍👧"), e(&["x", "\t", "\n", "🇯🇵", "👨‍👨‍👧"]));
556    }
557
558    #[test]
559    fn test_floor_ceil_grapheme_boundary_with_emoji() {
560        let text = "👩🏻‍❤️‍💋‍👩🏻";
561        let rope = Rope::from_str(text);
562        let slice = rope.slice(..);
563        for byte_index in 0..=rope.len() {
564            // These should not panic, even if byte_index is in the middle of a multi-byte char
565            let floor = floor_grapheme_boundary(&slice, byte_index);
566            let ceil = ceil_grapheme_boundary(&slice, byte_index);
567            // Floor should be <= byte_index
568            assert!(
569                floor <= byte_index,
570                "floor={floor}, byte_index={byte_index}"
571            );
572            // Ceil should be >= byte_index
573            assert!(ceil >= byte_index, "ceil={ceil}, byte_index={byte_index}");
574            // Both should be valid grapheme boundaries
575            assert!(is_grapheme_boundary(&slice, floor));
576            assert!(is_grapheme_boundary(&slice, ceil));
577        }
578    }
579
580    #[test]
581    fn grapheme_boundary_rejects_non_char_boundary() {
582        let rope = Rope::from_str("5\u{e}Չ");
583        assert!(!is_grapheme_boundary(&rope.slice(..), 3));
584    }
585
586    #[test]
587    fn test_next_prev_grapheme_boundary_with_emoji() {
588        let text = "a👩🏻‍❤️‍💋‍👩🏻b";
589        let rope = Rope::from_str(text);
590        let slice = rope.slice(..);
591        let mut pos = 0;
592        let positions = std::iter::from_fn(|| {
593            let current = pos;
594            pos = next_grapheme_boundary(&slice, pos)?;
595            Some(current)
596        })
597        .collect::<Vec<_>>();
598        // Should have 3 graphemes: "a", the complex emoji, and "b"
599        assert_eq!(positions.len(), 3);
600        // Each position should be a valid grapheme boundary
601        for &pos in &positions {
602            assert!(is_grapheme_boundary(&slice, pos));
603        }
604    }
605}
indigo_core/rope.rs

indigo_core/
rope.rs
