1use super::Point;
2use crate::sum_tree::{self, SeekBias, SumTree};
3use arrayvec::ArrayString;
4use std::{cmp, ops::Range, str};
5
6#[cfg(test)]
7const CHUNK_BASE: usize = 2;
8
9#[cfg(not(test))]
10const CHUNK_BASE: usize = 8;
11
12#[derive(Clone, Default, Debug)]
13pub struct Rope {
14 chunks: SumTree<Chunk>,
15}
16
17impl Rope {
18 pub fn new() -> Self {
19 Self::default()
20 }
21
22 pub fn append(&mut self, rope: Rope) {
23 self.chunks.push_tree(rope.chunks, &());
24 }
25
26 pub fn push(&mut self, mut text: &str) {
27 let mut suffix = ArrayString::<[_; 2 * CHUNK_BASE]>::new();
28 self.chunks.with_last_mut(
29 |chunk| {
30 if chunk.0.len() + text.len() <= 2 * CHUNK_BASE {
31 chunk.0.push_str(text);
32 text = "";
33 } else {
34 let mut append_len = CHUNK_BASE.saturating_sub(chunk.0.len());
35 while !text.is_char_boundary(append_len) {
36 append_len -= 1;
37 }
38
39 if append_len > 0 {
40 let split = text.split_at(append_len);
41 chunk.0.push_str(split.0);
42 text = split.1;
43 } else {
44 let mut take_len = CHUNK_BASE;
45 while !chunk.0.is_char_boundary(take_len) {
46 take_len -= 1;
47 }
48
49 let split = chunk.0.split_at(take_len);
50 suffix.push_str(split.1);
51 chunk.0 = ArrayString::from(split.0).unwrap();
52 }
53 }
54 },
55 &(),
56 );
57
58 let mut chunks = vec![];
59 let mut chunk = ArrayString::new();
60 for ch in suffix.chars().chain(text.chars()) {
61 if chunk.len() + ch.len_utf8() > CHUNK_BASE {
62 chunks.push(Chunk(chunk));
63 chunk = ArrayString::new();
64 }
65 chunk.push(ch);
66 }
67 if !chunk.is_empty() {
68 chunks.push(Chunk(chunk));
69 }
70 self.chunks.extend(chunks, &());
71 }
72
73 pub fn slice(&self, range: Range<usize>) -> Rope {
74 let mut slice = Rope::new();
75 let mut cursor = self.chunks.cursor::<usize, usize>();
76
77 cursor.slice(&range.start, SeekBias::Left, &());
78 if let Some(start_chunk) = cursor.item() {
79 let start_ix = range.start - cursor.start();
80 let end_ix = cmp::min(range.end, cursor.end()) - cursor.start();
81 slice.push(&start_chunk.0[start_ix..end_ix]);
82 }
83
84 if range.end > cursor.end() {
85 cursor.next();
86 slice.append(Rope {
87 chunks: cursor.slice(&range.end, SeekBias::Left, &()),
88 });
89 if let Some(end_chunk) = cursor.item() {
90 slice.push(&end_chunk.0[..range.end - cursor.start()]);
91 }
92 }
93
94 slice
95 }
96
97 pub fn summary(&self) -> TextSummary {
98 self.chunks.summary()
99 }
100
101 pub fn chars(&self) -> Chars {
102 self.chars_at(0)
103 }
104
105 pub fn chars_at(&self, start: usize) -> Chars {
106 Chars::new(self, start)
107 }
108
109 fn text(&self) -> String {
110 let mut text = String::new();
111 for chunk in self.chunks.cursor::<(), ()>() {
112 text.push_str(&chunk.0);
113 }
114 text
115 }
116}
117
118impl<'a> From<&'a str> for Rope {
119 fn from(text: &'a str) -> Self {
120 let mut rope = Self::new();
121 rope.push(text);
122 rope
123 }
124}
125
126#[derive(Clone, Debug, Default)]
127struct Chunk(ArrayString<[u8; 2 * CHUNK_BASE]>);
128
129impl sum_tree::Item for Chunk {
130 type Summary = TextSummary;
131
132 fn summary(&self) -> Self::Summary {
133 let mut chars = 0;
134 let mut bytes = 0;
135 let mut lines = Point::new(0, 0);
136 let mut first_line_len = 0;
137 let mut rightmost_point = Point::new(0, 0);
138 for c in self.0.chars() {
139 chars += 1;
140 bytes += c.len_utf8();
141 if c == '\n' {
142 lines.row += 1;
143 lines.column = 0;
144 } else {
145 lines.column += 1;
146 if lines.row == 0 {
147 first_line_len = lines.column;
148 }
149 if lines.column > rightmost_point.column {
150 rightmost_point = lines;
151 }
152 }
153 }
154
155 TextSummary {
156 chars,
157 bytes,
158 lines,
159 first_line_len,
160 rightmost_point,
161 }
162 }
163}
164
165#[derive(Clone, Debug, Default, Eq, PartialEq)]
166pub struct TextSummary {
167 pub chars: usize,
168 pub bytes: usize,
169 pub lines: Point,
170 pub first_line_len: u32,
171 pub rightmost_point: Point,
172}
173
174impl sum_tree::Summary for TextSummary {
175 type Context = ();
176
177 fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
178 *self += summary;
179 }
180}
181
182impl<'a> std::ops::AddAssign<&'a Self> for TextSummary {
183 fn add_assign(&mut self, other: &'a Self) {
184 let joined_line_len = self.lines.column + other.first_line_len;
185 if joined_line_len > self.rightmost_point.column {
186 self.rightmost_point = Point::new(self.lines.row, joined_line_len);
187 }
188 if other.rightmost_point.column > self.rightmost_point.column {
189 self.rightmost_point = self.lines + &other.rightmost_point;
190 }
191
192 if self.lines.row == 0 {
193 self.first_line_len += other.first_line_len;
194 }
195
196 self.chars += other.chars;
197 self.bytes += other.bytes;
198 self.lines += &other.lines;
199 }
200}
201
202impl std::ops::AddAssign<Self> for TextSummary {
203 fn add_assign(&mut self, other: Self) {
204 *self += &other;
205 }
206}
207
208impl<'a> sum_tree::Dimension<'a, TextSummary> for usize {
209 fn add_summary(&mut self, summary: &'a TextSummary) {
210 *self += summary.chars;
211 }
212}
213
214pub struct Chars<'a> {
215 cursor: sum_tree::Cursor<'a, Chunk, usize, usize>,
216 chars: str::Chars<'a>,
217}
218
219impl<'a> Chars<'a> {
220 pub fn new(rope: &'a Rope, start: usize) -> Self {
221 let mut cursor = rope.chunks.cursor::<usize, usize>();
222 cursor.slice(&start, SeekBias::Left, &());
223 let chunk = cursor.item().expect("invalid index");
224 let chars = chunk.0[start - cursor.start()..].chars();
225 Self { cursor, chars }
226 }
227}
228
229impl<'a> Iterator for Chars<'a> {
230 type Item = char;
231
232 fn next(&mut self) -> Option<Self::Item> {
233 if let Some(ch) = self.chars.next() {
234 Some(ch)
235 } else if let Some(chunk) = self.cursor.item() {
236 self.chars = chunk.0.chars();
237 self.cursor.next();
238 Some(self.chars.next().unwrap())
239 } else {
240 None
241 }
242 }
243}
244
245#[cfg(test)]
246mod tests {
247 use crate::util::RandomCharIter;
248
249 use super::*;
250 use rand::prelude::*;
251 use std::env;
252
253 #[test]
254 fn test_random() {
255 let iterations = env::var("ITERATIONS")
256 .map(|i| i.parse().expect("invalid `ITERATIONS` variable"))
257 .unwrap_or(100);
258 let operations = env::var("OPERATIONS")
259 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
260 .unwrap_or(10);
261 let seed_range = if let Ok(seed) = env::var("SEED") {
262 let seed = seed.parse().expect("invalid `SEED` variable");
263 seed..seed + 1
264 } else {
265 0..iterations
266 };
267
268 for seed in seed_range {
269 dbg!(seed);
270 let mut rng = StdRng::seed_from_u64(seed);
271 let mut expected = String::new();
272 let mut actual = Rope::new();
273 for _ in 0..operations {
274 let end_ix = rng.gen_range(0..=expected.len());
275 let start_ix = rng.gen_range(0..=end_ix);
276 let len = rng.gen_range(0..=5);
277 let new_text: String = RandomCharIter::new(&mut rng).take(len).collect();
278
279 let mut new_actual = Rope::new();
280 new_actual.append(actual.slice(0..start_ix));
281 new_actual.push(&new_text);
282 new_actual.append(actual.slice(end_ix..actual.summary().chars));
283 actual = new_actual;
284
285 let mut new_expected = String::new();
286 new_expected.push_str(&expected[..start_ix]);
287 new_expected.push_str(&new_text);
288 new_expected.push_str(&expected[end_ix..]);
289 expected = new_expected;
290
291 assert_eq!(actual.text(), expected);
292 }
293 }
294 }
295}