1use super::Point;
2use arrayvec::ArrayString;
3use smallvec::SmallVec;
4use std::{cmp, ops::Range, str};
5use sum_tree::{self, 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 chunks<'a>(&'a self) -> Chunks<'a> {
119 self.chunks_in_range(0..self.len())
120 }
121
122 pub fn chunks_in_range<'a>(&'a self, range: Range<usize>) -> Chunks<'a> {
123 Chunks::new(self, range)
124 }
125
126 pub fn to_point(&self, offset: usize) -> Point {
127 assert!(offset <= self.summary().bytes);
128 let mut cursor = self.chunks.cursor::<(usize, Point)>();
129 cursor.seek(&offset, Bias::Left, &());
130 let overshoot = offset - cursor.start().0;
131 cursor.start().1
132 + cursor
133 .item()
134 .map_or(Point::zero(), |chunk| chunk.to_point(overshoot))
135 }
136
137 pub fn to_offset(&self, point: Point) -> usize {
138 assert!(point <= self.summary().lines);
139 let mut cursor = self.chunks.cursor::<(Point, usize)>();
140 cursor.seek(&point, Bias::Left, &());
141 let overshoot = point - cursor.start().0;
142 cursor.start().1 + cursor.item().map_or(0, |chunk| chunk.to_offset(overshoot))
143 }
144
145 pub fn clip_offset(&self, mut offset: usize, bias: Bias) -> usize {
146 let mut cursor = self.chunks.cursor::<usize>();
147 cursor.seek(&offset, Bias::Left, &());
148 if let Some(chunk) = cursor.item() {
149 let mut ix = offset - cursor.start();
150 while !chunk.0.is_char_boundary(ix) {
151 match bias {
152 Bias::Left => {
153 ix -= 1;
154 offset -= 1;
155 }
156 Bias::Right => {
157 ix += 1;
158 offset += 1;
159 }
160 }
161 }
162 offset
163 } else {
164 self.summary().bytes
165 }
166 }
167
168 pub fn clip_point(&self, point: Point, bias: Bias) -> Point {
169 let mut cursor = self.chunks.cursor::<Point>();
170 cursor.seek(&point, Bias::Right, &());
171 if let Some(chunk) = cursor.item() {
172 let overshoot = point - cursor.start();
173 *cursor.start() + chunk.clip_point(overshoot, bias)
174 } else {
175 self.summary().lines
176 }
177 }
178}
179
180impl<'a> From<&'a str> for Rope {
181 fn from(text: &'a str) -> Self {
182 let mut rope = Self::new();
183 rope.push(text);
184 rope
185 }
186}
187
188impl Into<String> for Rope {
189 fn into(self) -> String {
190 self.chunks().collect()
191 }
192}
193
194pub struct Cursor<'a> {
195 rope: &'a Rope,
196 chunks: sum_tree::Cursor<'a, Chunk, usize>,
197 offset: usize,
198}
199
200impl<'a> Cursor<'a> {
201 pub fn new(rope: &'a Rope, offset: usize) -> Self {
202 let mut chunks = rope.chunks.cursor();
203 chunks.seek(&offset, Bias::Right, &());
204 Self {
205 rope,
206 chunks,
207 offset,
208 }
209 }
210
211 pub fn seek_forward(&mut self, end_offset: usize) {
212 debug_assert!(end_offset >= self.offset);
213
214 self.chunks.seek_forward(&end_offset, Bias::Right, &());
215 self.offset = end_offset;
216 }
217
218 pub fn slice(&mut self, end_offset: usize) -> Rope {
219 debug_assert!(
220 end_offset >= self.offset,
221 "cannot slice backwards from {} to {}",
222 self.offset,
223 end_offset
224 );
225
226 let mut slice = Rope::new();
227 if let Some(start_chunk) = self.chunks.item() {
228 let start_ix = self.offset - self.chunks.start();
229 let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
230 slice.push(&start_chunk.0[start_ix..end_ix]);
231 }
232
233 if end_offset > self.chunks.end(&()) {
234 self.chunks.next(&());
235 slice.append(Rope {
236 chunks: self.chunks.slice(&end_offset, Bias::Right, &()),
237 });
238 if let Some(end_chunk) = self.chunks.item() {
239 let end_ix = end_offset - self.chunks.start();
240 slice.push(&end_chunk.0[..end_ix]);
241 }
242 }
243
244 self.offset = end_offset;
245 slice
246 }
247
248 pub fn summary(&mut self, end_offset: usize) -> TextSummary {
249 debug_assert!(end_offset >= self.offset);
250
251 let mut summary = TextSummary::default();
252 if let Some(start_chunk) = self.chunks.item() {
253 let start_ix = self.offset - self.chunks.start();
254 let end_ix = cmp::min(end_offset, self.chunks.end(&())) - self.chunks.start();
255 summary = TextSummary::from(&start_chunk.0[start_ix..end_ix]);
256 }
257
258 if end_offset > self.chunks.end(&()) {
259 self.chunks.next(&());
260 summary += &self.chunks.summary(&end_offset, Bias::Right, &());
261 if let Some(end_chunk) = self.chunks.item() {
262 let end_ix = end_offset - self.chunks.start();
263 summary += TextSummary::from(&end_chunk.0[..end_ix]);
264 }
265 }
266
267 summary
268 }
269
270 pub fn suffix(mut self) -> Rope {
271 self.slice(self.rope.chunks.extent(&()))
272 }
273
274 pub fn offset(&self) -> usize {
275 self.offset
276 }
277}
278
279pub struct Chunks<'a> {
280 chunks: sum_tree::Cursor<'a, Chunk, usize>,
281 range: Range<usize>,
282}
283
284impl<'a> Chunks<'a> {
285 pub fn new(rope: &'a Rope, range: Range<usize>) -> Self {
286 let mut chunks = rope.chunks.cursor();
287 chunks.seek(&range.start, Bias::Right, &());
288 Self { chunks, range }
289 }
290
291 pub fn offset(&self) -> usize {
292 self.range.start.max(*self.chunks.start())
293 }
294
295 pub fn seek(&mut self, offset: usize) {
296 if offset >= self.chunks.end(&()) {
297 self.chunks.seek_forward(&offset, Bias::Right, &());
298 } else {
299 self.chunks.seek(&offset, Bias::Right, &());
300 }
301 self.range.start = offset;
302 }
303
304 pub fn peek(&self) -> Option<&'a str> {
305 if let Some(chunk) = self.chunks.item() {
306 let offset = *self.chunks.start();
307 if self.range.end > offset {
308 let start = self.range.start.saturating_sub(*self.chunks.start());
309 let end = self.range.end - self.chunks.start();
310 return Some(&chunk.0[start..chunk.0.len().min(end)]);
311 }
312 }
313 None
314 }
315}
316
317impl<'a> Iterator for Chunks<'a> {
318 type Item = &'a str;
319
320 fn next(&mut self) -> Option<Self::Item> {
321 let result = self.peek();
322 if result.is_some() {
323 self.chunks.next(&());
324 }
325 result
326 }
327}
328
329#[derive(Clone, Debug, Default)]
330struct Chunk(ArrayString<{ 2 * CHUNK_BASE }>);
331
332impl Chunk {
333 fn to_point(&self, target: usize) -> Point {
334 let mut offset = 0;
335 let mut point = Point::new(0, 0);
336 for ch in self.0.chars() {
337 if offset >= target {
338 break;
339 }
340
341 if ch == '\n' {
342 point.row += 1;
343 point.column = 0;
344 } else {
345 point.column += ch.len_utf8() as u32;
346 }
347 offset += ch.len_utf8();
348 }
349 point
350 }
351
352 fn to_offset(&self, target: Point) -> usize {
353 let mut offset = 0;
354 let mut point = Point::new(0, 0);
355 for ch in self.0.chars() {
356 if point >= target {
357 if point > target {
358 panic!("point {:?} is inside of character {:?}", target, ch);
359 }
360 break;
361 }
362
363 if ch == '\n' {
364 point.row += 1;
365 point.column = 0;
366 } else {
367 point.column += ch.len_utf8() as u32;
368 }
369 offset += ch.len_utf8();
370 }
371 offset
372 }
373
374 fn clip_point(&self, target: Point, bias: Bias) -> Point {
375 for (row, line) in self.0.split('\n').enumerate() {
376 if row == target.row as usize {
377 let mut column = target.column.min(line.len() as u32);
378 while !line.is_char_boundary(column as usize) {
379 match bias {
380 Bias::Left => column -= 1,
381 Bias::Right => column += 1,
382 }
383 }
384 return Point::new(row as u32, column);
385 }
386 }
387 unreachable!()
388 }
389}
390
391impl sum_tree::Item for Chunk {
392 type Summary = TextSummary;
393
394 fn summary(&self) -> Self::Summary {
395 TextSummary::from(self.0.as_str())
396 }
397}
398
399#[derive(Clone, Debug, Default, Eq, PartialEq)]
400pub struct TextSummary {
401 pub bytes: usize,
402 pub lines: Point,
403 pub first_line_chars: u32,
404 pub last_line_chars: u32,
405 pub longest_row: u32,
406 pub longest_row_chars: u32,
407}
408
409impl<'a> From<&'a str> for TextSummary {
410 fn from(text: &'a str) -> Self {
411 let mut lines = Point::new(0, 0);
412 let mut first_line_chars = 0;
413 let mut last_line_chars = 0;
414 let mut longest_row = 0;
415 let mut longest_row_chars = 0;
416 for c in text.chars() {
417 if c == '\n' {
418 lines.row += 1;
419 lines.column = 0;
420 last_line_chars = 0;
421 } else {
422 lines.column += c.len_utf8() as u32;
423 last_line_chars += 1;
424 }
425
426 if lines.row == 0 {
427 first_line_chars = last_line_chars;
428 }
429
430 if last_line_chars > longest_row_chars {
431 longest_row = lines.row;
432 longest_row_chars = last_line_chars;
433 }
434 }
435
436 TextSummary {
437 bytes: text.len(),
438 lines,
439 first_line_chars,
440 last_line_chars,
441 longest_row,
442 longest_row_chars,
443 }
444 }
445}
446
447impl sum_tree::Summary for TextSummary {
448 type Context = ();
449
450 fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
451 *self += summary;
452 }
453}
454
455impl<'a> std::ops::AddAssign<&'a Self> for TextSummary {
456 fn add_assign(&mut self, other: &'a Self) {
457 let joined_chars = self.last_line_chars + other.first_line_chars;
458 if joined_chars > self.longest_row_chars {
459 self.longest_row = self.lines.row;
460 self.longest_row_chars = joined_chars;
461 }
462 if other.longest_row_chars > self.longest_row_chars {
463 self.longest_row = self.lines.row + other.longest_row;
464 self.longest_row_chars = other.longest_row_chars;
465 }
466
467 if self.lines.row == 0 {
468 self.first_line_chars += other.first_line_chars;
469 }
470
471 if other.lines.row == 0 {
472 self.last_line_chars += other.first_line_chars;
473 } else {
474 self.last_line_chars = other.last_line_chars;
475 }
476
477 self.bytes += other.bytes;
478 self.lines += &other.lines;
479 }
480}
481
482impl std::ops::AddAssign<Self> for TextSummary {
483 fn add_assign(&mut self, other: Self) {
484 *self += &other;
485 }
486}
487
488impl<'a> sum_tree::Dimension<'a, TextSummary> for usize {
489 fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
490 *self += summary.bytes;
491 }
492}
493
494impl<'a> sum_tree::Dimension<'a, TextSummary> for Point {
495 fn add_summary(&mut self, summary: &'a TextSummary, _: &()) {
496 *self += &summary.lines;
497 }
498}
499
500fn find_split_ix(text: &str) -> usize {
501 let mut ix = text.len() / 2;
502 while !text.is_char_boundary(ix) {
503 if ix < 2 * CHUNK_BASE {
504 ix += 1;
505 } else {
506 ix = (text.len() / 2) - 1;
507 break;
508 }
509 }
510 while !text.is_char_boundary(ix) {
511 ix -= 1;
512 }
513
514 debug_assert!(ix <= 2 * CHUNK_BASE);
515 debug_assert!(text.len() - ix <= 2 * CHUNK_BASE);
516 ix
517}
518
519#[cfg(test)]
520mod tests {
521 use super::*;
522 use crate::random_char_iter::RandomCharIter;
523 use rand::prelude::*;
524 use std::env;
525 use Bias::{Left, Right};
526
527 #[test]
528 fn test_all_4_byte_chars() {
529 let mut rope = Rope::new();
530 let text = "🏀".repeat(256);
531 rope.push(&text);
532 assert_eq!(rope.text(), text);
533 }
534
535 #[gpui::test(iterations = 100)]
536 fn test_random(mut rng: StdRng) {
537 let operations = env::var("OPERATIONS")
538 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
539 .unwrap_or(10);
540
541 let mut expected = String::new();
542 let mut actual = Rope::new();
543 for _ in 0..operations {
544 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
545 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
546 let len = rng.gen_range(0..=64);
547 let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
548
549 let mut new_actual = Rope::new();
550 let mut cursor = actual.cursor(0);
551 new_actual.append(cursor.slice(start_ix));
552 new_actual.push(&new_text);
553 cursor.seek_forward(end_ix);
554 new_actual.append(cursor.suffix());
555 actual = new_actual;
556
557 expected.replace_range(start_ix..end_ix, &new_text);
558
559 assert_eq!(actual.text(), expected);
560 log::info!("text: {:?}", expected);
561
562 for _ in 0..5 {
563 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
564 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
565 assert_eq!(
566 actual.chunks_in_range(start_ix..end_ix).collect::<String>(),
567 &expected[start_ix..end_ix]
568 );
569 }
570
571 let mut point = Point::new(0, 0);
572 for (ix, ch) in expected.char_indices().chain(Some((expected.len(), '\0'))) {
573 assert_eq!(actual.to_point(ix), point, "to_point({})", ix);
574 assert_eq!(actual.to_offset(point), ix, "to_offset({:?})", point);
575 if ch == '\n' {
576 point.row += 1;
577 point.column = 0
578 } else {
579 point.column += ch.len_utf8() as u32;
580 }
581 }
582
583 for _ in 0..5 {
584 let end_ix = clip_offset(&expected, rng.gen_range(0..=expected.len()), Right);
585 let start_ix = clip_offset(&expected, rng.gen_range(0..=end_ix), Left);
586 assert_eq!(
587 actual.cursor(start_ix).summary(end_ix),
588 TextSummary::from(&expected[start_ix..end_ix])
589 );
590 }
591 }
592 }
593
594 fn clip_offset(text: &str, mut offset: usize, bias: Bias) -> usize {
595 while !text.is_char_boundary(offset) {
596 match bias {
597 Bias::Left => offset -= 1,
598 Bias::Right => offset += 1,
599 }
600 }
601 offset
602 }
603
604 impl Rope {
605 fn text(&self) -> String {
606 let mut text = String::new();
607 for chunk in self.chunks.cursor::<()>() {
608 text.push_str(&chunk.0);
609 }
610 text
611 }
612 }
613}