1use super::Point;
2use arrayvec::ArrayString;
3use smallvec::SmallVec;
4use std::{cmp, ops::Range, str};
5use sum_tree::{Bias, SumTree};
6
7#[cfg(test)]
8const CHUNK_BASE: usize = 6;
9
10#[cfg(not(test))]
11const CHUNK_BASE: usize = 16;
12
13#[derive(Clone, Default, Debug)]
14pub struct Rope {
15 chunks: SumTree<Chunk>,
16}
17
18impl Rope {
19 pub fn new() -> Self {
20 Self::default()
21 }
22
23 pub fn append(&mut self, rope: Rope) {
24 let mut chunks = rope.chunks.cursor::<()>();
25 chunks.next(&());
26 if let Some(chunk) = chunks.item() {
27 if self.chunks.last().map_or(false, |c| c.0.len() < CHUNK_BASE)
28 || chunk.0.len() < CHUNK_BASE
29 {
30 self.push(&chunk.0);
31 chunks.next(&());
32 }
33 }
34
35 self.chunks.push_tree(chunks.suffix(&()), &());
36 self.check_invariants();
37 }
38
39 pub fn push(&mut self, text: &str) {
40 let mut new_chunks = SmallVec::<[_; 16]>::new();
41 let mut new_chunk = ArrayString::new();
42 for ch in text.chars() {
43 if new_chunk.len() + ch.len_utf8() > 2 * CHUNK_BASE {
44 new_chunks.push(Chunk(new_chunk));
45 new_chunk = ArrayString::new();
46 }
47 new_chunk.push(ch);
48 }
49 if !new_chunk.is_empty() {
50 new_chunks.push(Chunk(new_chunk));
51 }
52
53 let mut new_chunks = new_chunks.into_iter();
54 let mut first_new_chunk = new_chunks.next();
55 self.chunks.update_last(
56 |last_chunk| {
57 if let Some(first_new_chunk_ref) = first_new_chunk.as_mut() {
58 if last_chunk.0.len() + first_new_chunk_ref.0.len() <= 2 * CHUNK_BASE {
59 last_chunk.0.push_str(&first_new_chunk.take().unwrap().0);
60 } else {
61 let mut text = ArrayString::<{ 4 * CHUNK_BASE }>::new();
62 text.push_str(&last_chunk.0);
63 text.push_str(&first_new_chunk_ref.0);
64 let (left, right) = text.split_at(find_split_ix(&text));
65 last_chunk.0.clear();
66 last_chunk.0.push_str(left);
67 first_new_chunk_ref.0.clear();
68 first_new_chunk_ref.0.push_str(right);
69 }
70 }
71 },
72 &(),
73 );
74
75 self.chunks
76 .extend(first_new_chunk.into_iter().chain(new_chunks), &());
77 self.check_invariants();
78 }
79
80 fn check_invariants(&self) {
81 #[cfg(test)]
82 {
83 // Ensure all chunks except maybe the last one are not underflowing.
84 // Allow some wiggle room for multibyte characters at chunk boundaries.
85 let mut chunks = self.chunks.cursor::<()>().peekable();
86 while let Some(chunk) = chunks.next() {
87 if chunks.peek().is_some() {
88 assert!(chunk.0.len() + 3 >= CHUNK_BASE);
89 }
90 }
91 }
92 }
93
94 pub fn summary(&self) -> TextSummary {
95 self.chunks.summary()
96 }
97
98 pub fn len(&self) -> usize {
99 self.chunks.extent(&())
100 }
101
102 pub fn max_point(&self) -> Point {
103 self.chunks.extent(&())
104 }
105
106 pub fn cursor(&self, offset: usize) -> Cursor {
107 Cursor::new(self, offset)
108 }
109
110 pub fn chars(&self) -> impl Iterator<Item = char> + '_ {
111 self.chars_at(0)
112 }
113
114 pub fn chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {
115 self.chunks_in_range(start..self.len()).flat_map(str::chars)
116 }
117
118 pub fn reversed_chars_at(&self, start: usize) -> impl Iterator<Item = char> + '_ {
119 self.reversed_chunks_in_range(0..start)
120 .flat_map(|chunk| chunk.chars().rev())
121 }
122
123 pub fn bytes_at(&self, start: usize) -> impl Iterator<Item = u8> + '_ {
124 self.chunks_in_range(start..self.len()).flat_map(str::bytes)
125 }
126
127 pub fn chunks<'a>(&'a self) -> Chunks<'a> {
128 self.chunks_in_range(0..self.len())
129 }
130
131 pub fn chunks_in_range(&self, range: Range<usize>) -> Chunks {
132 Chunks::new(self, range, false)
133 }
134
135 pub fn reversed_chunks_in_range(&self, range: Range<usize>) -> Chunks {
136 Chunks::new(self, range, true)
137 }
138
139 pub fn to_point(&self, offset: usize) -> Point {
140 assert!(offset <= self.summary().bytes);
141 let mut cursor = self.chunks.cursor::<(usize, Point)>();
142 cursor.seek(&offset, Bias::Left, &());
143 let overshoot = offset - cursor.start().0;
144 cursor.start().1
145 + cursor
146 .item()
147 .map_or(Point::zero(), |chunk| chunk.to_point(overshoot))
148 }
149
150 pub fn to_offset(&self, point: Point) -> usize {
151 assert!(point <= self.summary().lines);
152 let mut cursor = self.chunks.cursor::<(Point, usize)>();
153 cursor.seek(&point, Bias::Left, &());
154 let overshoot = point - cursor.start().0;
155 cursor.start().1 + cursor.item().map_or(0, |chunk| chunk.to_offset(overshoot))
156 }
157
158 pub fn clip_offset(&self, mut offset: usize, bias: Bias) -> usize {
159 let mut cursor = self.chunks.cursor::<usize>();
160 cursor.seek(&offset, Bias::Left, &());
161 if let Some(chunk) = cursor.item() {
162 let mut ix = offset - cursor.start();
163 while !chunk.0.is_char_boundary(ix) {
164 match bias {
165 Bias::Left => {
166 ix -= 1;
167 offset -= 1;
168 }
169 Bias::Right => {
170 ix += 1;
171 offset += 1;
172 }
173 }
174 }
175 offset
176 } else {
177 self.summary().bytes
178 }
179 }
180
181 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
182 let mut cursor = self.chunks.cursor::<Point>();
183 cursor.seek(&point, Bias::Right, &());
184 if let Some(chunk) = cursor.item() {
185 let overshoot = point - cursor.start();
186 *cursor.start() + chunk.clip_point(overshoot, bias)
187 } else {
188 self.summary().lines
189 }
190 }
191}
192
193impl<'a> From<&'a str> for Rope {
194 fn from(text: &'a str) -> Self {
195 let mut rope = Self::new();
196 rope.push(text);
197 rope
198 }
199}
200
201impl Into<String> for Rope {
202 fn into(self) -> String {
203 self.chunks().collect()
204 }
205}
206
207pub struct Cursor<'a> {
208 rope: &'a Rope,
209 chunks: sum_tree::Cursor<'a, Chunk, usize>,
210 offset: usize,
211}
212
213impl<'a> Cursor<'a> {
214 pub fn new(rope: &'a Rope, offset: usize) -> Self {
215 let mut chunks = rope.chunks.cursor();
216 chunks.seek(&offset, Bias::Right, &());
217 Self {
218 rope,
219 chunks,
220 offset,
221 }
222 }
223
224 pub fn seek_forward(&mut self, end_offset: usize) {
225 debug_assert!(end_offset >= self.offset);
226
227 self.chunks.seek_forward(&end_offset, Bias::Right, &());
228 self.offset = end_offset;
229 }
230
231 pub fn slice(&mut self, end_offset: usize) -> Rope {
232 debug_assert!(
233 end_offset >= self.offset,
234 "cannot slice backwards from {} to {}",
235 self.offset,
236 end_offset
237 );
238
239 let mut slice = Rope::new();
240 if let Some(start_chunk) = self.chunks.item() {
241 let start_ix = self.offset - self.chunks.start();
242 let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
243 slice.push(&start_chunk.0[start_ix..end_ix]);
244 }
245
246 if end_offset > self.chunks.end(&()) {
247 self.chunks.next(&());
248 slice.append(Rope {
249 chunks: self.chunks.slice(&end_offset, Bias::Right, &()),
250 });
251 if let Some(end_chunk) = self.chunks.item() {
252 let end_ix = end_offset - self.chunks.start();
253 slice.push(&end_chunk.0[..end_ix]);
254 }
255 }
256
257 self.offset = end_offset;
258 slice
259 }
260
261 pub fn summary(&mut self, end_offset: usize) -> TextSummary {
262 debug_assert!(end_offset >= self.offset);
263
264 let mut summary = TextSummary::default();
265 if let Some(start_chunk) = self.chunks.item() {
266 let start_ix = self.offset - self.chunks.start();
267 let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
268 summary = TextSummary::from(&start_chunk.0[start_ix..end_ix]);
269 }
270
271 if end_offset > self.chunks.end(&()) {
272 self.chunks.next(&());
273 summary += &self.chunks.summary(&end_offset, Bias::Right, &());
274 if let Some(end_chunk) = self.chunks.item() {
275 let end_ix = end_offset - self.chunks.start();
276 summary += TextSummary::from(&end_chunk.0[..end_ix]);
277 }
278 }
279
280 self.offset = end_offset;
281 summary
282 }
283
284 pub fn suffix(mut self) -> Rope {
285 self.slice(self.rope.chunks.extent(&()))
286 }
287
288 pub fn offset(&self) -> usize {
289 self.offset
290 }
291}
292
293pub struct Chunks<'a> {
294 chunks: sum_tree::Cursor<'a, Chunk, usize>,
295 range: Range<usize>,
296 reversed: bool,
297}
298
299impl<'a> Chunks<'a> {
300 pub fn new(rope: &'a Rope, range: Range<usize>, reversed: bool) -> Self {
301 let mut chunks = rope.chunks.cursor();
302 if reversed {
303 chunks.seek(&range.end, Bias::Left, &());
304 } else {
305 chunks.seek(&range.start, Bias::Right, &());
306 }
307 Self {
308 chunks,
309 range,
310 reversed,
311 }
312 }
313
314 pub fn offset(&self) -> usize {
315 if self.reversed {
316 self.range.end.min(self.chunks.end(&()))
317 } else {
318 self.range.start.max(*self.chunks.start())
319 }
320 }
321
322 pub fn seek(&mut self, offset: usize) {
323 let bias = if self.reversed {
324 Bias::Left
325 } else {
326 Bias::Right
327 };
328
329 if offset >= self.chunks.end(&()) {
330 self.chunks.seek_forward(&offset, bias, &());
331 } else {
332 self.chunks.seek(&offset, bias, &());
333 }
334
335 if self.reversed {
336 self.range.end = offset;
337 } else {
338 self.range.start = offset;
339 }
340 }
341
342 pub fn peek(&self) -> Option<&'a str> {
343 let chunk = self.chunks.item()?;
344 if self.reversed && self.range.start >= self.chunks.end(&()) {
345 return None;
346 }
347 let chunk_start = *self.chunks.start();
348 if self.range.end <= chunk_start {
349 return None;
350 }
351
352 let start = self.range.start.saturating_sub(chunk_start);
353 let end = self.range.end - chunk_start;
354 Some(&chunk.0[start..chunk.0.len().min(end)])
355 }
356}
357
358impl<'a> Iterator for Chunks<'a> {
359 type Item = &'a str;
360
361 fn next(&mut self) -> Option<Self::Item> {
362 let result = self.peek();
363 if result.is_some() {
364 if self.reversed {
365 self.chunks.prev(&());
366 } else {
367 self.chunks.next(&());
368 }
369 }
370 result
371 }
372}
373
374#[derive(Clone, Debug, Default)]
375struct Chunk(ArrayString<{ 2 * CHUNK_BASE }>);
376
377impl Chunk {
378 fn to_point(&self, target: usize) -> Point {
379 let mut offset = 0;
380 let mut point = Point::new(0, 0);
381 for ch in self.0.chars() {
382 if offset >= target {
383 break;
384 }
385
386 if ch == '\n' {
387 point.row += 1;
388 point.column = 0;
389 } else {
390 point.column += ch.len_utf8() as u32;
391 }
392 offset += ch.len_utf8();
393 }
394 point
395 }
396
397 fn to_offset(&self, target: Point) -> usize {
398 let mut offset = 0;
399 let mut point = Point::new(0, 0);
400 for ch in self.0.chars() {
401 if point >= target {
402 if point > target {
403 panic!("point {:?} is inside of character {:?}", target, ch);
404 }
405 break;
406 }
407
408 if ch == '\n' {
409 point.row += 1;
410 point.column = 0;
411 } else {
412 point.column += ch.len_utf8() as u32;
413 }
414 offset += ch.len_utf8();
415 }
416 offset
417 }
418
419 fn clip_point(&self, target: Point, bias: Bias) -> Point {
420 for (row, line) in self.0.split('\n').enumerate() {
421 if row == target.row as usize {
422 let mut column = target.column.min(line.len() as u32);
423 while !line.is_char_boundary(column as usize) {
424 match bias {
425 Bias::Left => column -= 1,
426 Bias::Right => column += 1,
427 }
428 }
429 return Point::new(row as u32, column);
430 }
431 }
432 unreachable!()
433 }
434}
435
436impl sum_tree::Item for Chunk {
437 type Summary = TextSummary;
438
439 fn summary(&self) -> Self::Summary {
440 TextSummary::from(self.0.as_str())
441 }
442}
443
444#[derive(Clone, Debug, Default, Eq, PartialEq)]
445pub struct TextSummary {
446 pub bytes: usize,
447 pub lines: Point,
448 pub first_line_chars: u32,
449 pub last_line_chars: u32,
450 pub longest_row: u32,
451 pub longest_row_chars: u32,
452}
453
454impl<'a> From<&'a str> for TextSummary {
455 fn from(text: &'a str) -> Self {
456 let mut lines = Point::new(0, 0);
457 let mut first_line_chars = 0;
458 let mut last_line_chars = 0;
459 let mut longest_row = 0;
460 let mut longest_row_chars = 0;
461 for c in text.chars() {
462 if c == '\n' {
463 lines.row += 1;
464 lines.column = 0;
465 last_line_chars = 0;
466 } else {
467 lines.column += c.len_utf8() as u32;
468 last_line_chars += 1;
469 }
470
471 if lines.row == 0 {
472 first_line_chars = last_line_chars;
473 }
474
475 if last_line_chars > longest_row_chars {
476 longest_row = lines.row;
477 longest_row_chars = last_line_chars;
478 }
479 }
480
481 TextSummary {
482 bytes: text.len(),
483 lines,
484 first_line_chars,
485 last_line_chars,
486 longest_row,
487 longest_row_chars,
488 }
489 }
490}
491
492impl sum_tree::Summary for TextSummary {
493 type Context = ();
494
495 fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
496 *self += summary;
497 }
498}
499
500impl<'a> std::ops::AddAssign<&'a Self> for TextSummary {
501 fn add_assign(&mut self, other: &'a Self) {
502 let joined_chars = self.last_line_chars + other.first_line_chars;
503 if joined_chars > self.longest_row_chars {
504 self.longest_row = self.lines.row;
505 self.longest_row_chars = joined_chars;
506 }
507 if other.longest_row_chars > self.longest_row_chars {
508 self.longest_row = self.lines.row + other.longest_row;
509 self.longest_row_chars = other.longest_row_chars;
510 }
511
512 if self.lines.row == 0 {
513 self.first_line_chars += other.first_line_chars;
514 }
515
516 if other.lines.row == 0 {
517 self.last_line_chars += other.first_line_chars;
518 } else {
519 self.last_line_chars = other.last_line_chars;
520 }
521
522 self.bytes += other.bytes;
523 self.lines += &other.lines;
524 }
525}
526
527impl std::ops::AddAssign<Self> for TextSummary {
528 fn add_assign(&mut self, other: Self) {
529 *self += &other;
530 }
531}
532
533impl<'a> sum_tree::Dimension<'a, TextSummary> for usize {
534 fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
535 *self += summary.bytes;
536 }
537}
538
539impl<'a> sum_tree::Dimension<'a, TextSummary> for Point {
540 fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
541 *self += &summary.lines;
542 }
543}
544
545fn find_split_ix(text: &str) -> usize {
546 let mut ix = text.len() / 2;
547 while !text.is_char_boundary(ix) {
548 if ix < 2 * CHUNK_BASE {
549 ix += 1;
550 } else {
551 ix = (text.len() / 2) - 1;
552 break;
553 }
554 }
555 while !text.is_char_boundary(ix) {
556 ix -= 1;
557 }
558
559 debug_assert!(ix <= 2 * CHUNK_BASE);
560 debug_assert!(text.len() - ix <= 2 * CHUNK_BASE);
561 ix
562}
563
564#[cfg(test)]
565mod tests {
566 use super::*;
567 use crate::random_char_iter::RandomCharIter;
568 use rand::prelude::*;
569 use std::env;
570 use Bias::{Left, Right};
571
572 #[test]
573 fn test_all_4_byte_chars() {
574 let mut rope = Rope::new();
575 let text = "🏀".repeat(256);
576 rope.push(&text);
577 assert_eq!(rope.text(), text);
578 }
579
580 #[gpui::test(iterations = 100)]
581 fn test_random(mut rng: StdRng) {
582 let operations = env::var("OPERATIONS")
583 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
584 .unwrap_or(10);
585
586 let mut expected = String::new();
587 let mut actual = Rope::new();
588 for _ in 0..operations {
589 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
590 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
591 let len = rng.gen_range(0..=64);
592 let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
593
594 let mut new_actual = Rope::new();
595 let mut cursor = actual.cursor(0);
596 new_actual.append(cursor.slice(start_ix));
597 new_actual.push(&new_text);
598 cursor.seek_forward(end_ix);
599 new_actual.append(cursor.suffix());
600 actual = new_actual;
601
602 expected.replace_range(start_ix..end_ix, &new_text);
603
604 assert_eq!(actual.text(), expected);
605 log::info!("text: {:?}", expected);
606
607 for _ in 0..5 {
608 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
609 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
610 assert_eq!(
611 actual.chunks_in_range(start_ix..end_ix).collect::<String>(),
612 &expected[start_ix..end_ix]
613 );
614
615 assert_eq!(
616 actual
617 .reversed_chunks_in_range(start_ix..end_ix)
618 .collect::<Vec<&str>>()
619 .into_iter()
620 .rev()
621 .collect::<String>(),
622 &expected[start_ix..end_ix]
623 );
624 }
625
626 let mut point = Point::new(0, 0);
627 for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
628 assert_eq!(actual.to_point(ix), point, "to_point({})", ix);
629 assert_eq!(actual.to_offset(point), ix, "to_offset({:?})", point);
630 if ch == '\n' {
631 point.row += 1;
632 point.column = 0
633 } else {
634 point.column += ch.len_utf8() as u32;
635 }
636 }
637
638 for _ in 0..5 {
639 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
640 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
641 assert_eq!(
642 actual.cursor(start_ix).summary(end_ix),
643 TextSummary::from(&expected[start_ix..end_ix])
644 );
645 }
646 }
647 }
648
649 fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
650 while !text.is_char_boundary(offset) {
651 match bias {
652 Bias::Left => offset -= 1,
653 Bias::Right => offset += 1,
654 }
655 }
656 offset
657 }
658
659 impl Rope {
660 fn text(&self) -> String {
661 let mut text = String::new();
662 for chunk in self.chunks.cursor::<()>() {
663 text.push_str(&chunk.0);
664 }
665 text
666 }
667 }
668}