GPU-accelerated UI toolkit (Vulkan)
git clone https://git.lucas.co/cce-ui.git
src/widget/doc_editor/buffer.rs (15.3K)
1 //! The editor's text: a vector of lines (no `\n` stored), a caret and a
2 //! selection anchor, and edits that can be undone.
3 //!
4 //! Lines rather than a rope: every edit is O(length of the lines it
5 //! touches) plus a splice of line pointers, line access is O(1), and the
6 //! layout caches per line — so a change reports exactly which lines it
7 //! replaced ([`Change`]) and only those are shaped again. A 100k-line file
8 //! moves 2.4 MB of pointers on a line insert, well under a frame.
9 //!
10 //! Positions are (line, byte column) and always sit on a char boundary.
11
12 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Default, Hash)]
13 pub struct Pos {
14 pub line: usize,
15 /// Byte offset into the line, on a char boundary.
16 pub col: usize,
17 }
18
19 impl Pos {
20 pub fn new(line: usize, col: usize) -> Pos {
21 Pos { line, col }
22 }
23 }
24
25 /// Lines `first .. first + removed` were replaced by `inserted` lines.
26 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
27 pub struct Change {
28 pub first: usize,
29 pub removed: usize,
30 pub inserted: usize,
31 }
32
33 /// How an edit groups for undo: a run of typing (or of deleting) undoes
34 /// as one step; anything else is a step of its own.
35 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
36 pub enum EditKind {
37 Typing,
38 Deleting,
39 Other,
40 }
41
42 #[derive(Clone, Debug)]
43 struct Edit {
44 start: Pos,
45 removed: String,
46 inserted: String,
47 caret_before: (Pos, Option<Pos>),
48 caret_after: (Pos, Option<Pos>),
49 kind: EditKind,
50 }
51
52 /// Where `text` inserted at `start` ends.
53 fn end_of(start: Pos, text: &str) -> Pos {
54 match text.rfind('\n') {
55 Some(i) => Pos::new(start.line + text.matches('\n').count(), text.len() - i - 1),
56 None => Pos::new(start.line, start.col + text.len()),
57 }
58 }
59
60 pub struct Buffer {
61 lines: Vec<String>,
62 pub caret: Pos,
63 /// The other end of the selection, when there is one.
64 pub anchor: Option<Pos>,
65 undo: Vec<Edit>,
66 redo: Vec<Edit>,
67 changes: Vec<Change>,
68 /// Bumped on every change to the text.
69 pub revision: u64,
70 }
71
72 impl Buffer {
73 pub fn new(text: &str) -> Buffer {
74 let mut b = Buffer { lines: Vec::new(), caret: Pos::default(), anchor: None, undo: Vec::new(), redo: Vec::new(), changes: Vec::new(), revision: 0 };
75 b.set_text(text);
76 b
77 }
78
79 /// Replace everything: caret to the start, history and changes cleared
80 /// (the layout is rebuilt whole).
81 pub fn set_text(&mut self, text: &str) {
82 let text = text.replace("\r\n", "\n");
83 self.lines = text.split('\n').map(String::from).collect();
84 self.caret = Pos::default();
85 self.anchor = None;
86 self.undo.clear();
87 self.redo.clear();
88 self.changes.clear();
89 self.changes.push(Change { first: 0, removed: usize::MAX, inserted: self.lines.len() });
90 self.revision += 1;
91 }
92
93 pub fn text(&self) -> String {
94 self.lines.join("\n")
95 }
96
97 pub fn line_count(&self) -> usize {
98 self.lines.len()
99 }
100
101 pub fn line(&self, i: usize) -> &str {
102 self.lines.get(i).map(String::as_str).unwrap_or("")
103 }
104
105 pub fn lines(&self) -> &[String] {
106 &self.lines
107 }
108
109 /// What changed since the last call, in order. A `removed` of
110 /// `usize::MAX` means everything.
111 pub fn take_changes(&mut self) -> Vec<Change> {
112 std::mem::take(&mut self.changes)
113 }
114
115 pub fn clamp(&self, p: Pos) -> Pos {
116 let line = p.line.min(self.lines.len().saturating_sub(1));
117 let s = self.line(line);
118 let mut col = p.col.min(s.len());
119 while !s.is_char_boundary(col) {
120 col -= 1;
121 }
122 Pos::new(line, col)
123 }
124
125 pub fn end(&self) -> Pos {
126 let last = self.lines.len() - 1;
127 Pos::new(last, self.lines[last].len())
128 }
129
130 /// The selection, ordered, when it is not empty.
131 pub fn selection(&self) -> Option<(Pos, Pos)> {
132 let a = self.anchor?;
133 if a == self.caret {
134 return None;
135 }
136 Some((a.min(self.caret), a.max(self.caret)))
137 }
138
139 pub fn text_range(&self, a: Pos, b: Pos) -> String {
140 let (a, b) = (a.min(b), a.max(b));
141 if a.line == b.line {
142 return self.line(a.line)[a.col..b.col].to_string();
143 }
144 let mut out = self.line(a.line)[a.col..].to_string();
145 for l in a.line + 1..b.line {
146 out.push('\n');
147 out.push_str(self.line(l));
148 }
149 out.push('\n');
150 out.push_str(&self.line(b.line)[..b.col]);
151 out
152 }
153
154 pub fn selected_text(&self) -> Option<String> {
155 self.selection().map(|(a, b)| self.text_range(a, b))
156 }
157
158 /// Replace `a..b` with `text`, no history. Returns where the inserted
159 /// text ends.
160 fn raw_replace(&mut self, a: Pos, b: Pos, text: &str) -> Pos {
161 let (a, b) = (a.min(b), a.max(b));
162 let head = self.lines[a.line][..a.col].to_string();
163 let tail = self.lines[b.line][b.col..].to_string();
164 let mut new: Vec<String> = text.split('\n').map(String::from).collect();
165 let n = new.len();
166 let end = if n == 1 { Pos::new(a.line, a.col + new[0].len()) } else { Pos::new(a.line + n - 1, new[n - 1].len()) };
167 new[0].insert_str(0, &head);
168 new[n - 1].push_str(&tail);
169 self.lines.splice(a.line..=b.line, new);
170 self.changes.push(Change { first: a.line, removed: b.line - a.line + 1, inserted: n });
171 self.revision += 1;
172 end
173 }
174
175 /// Replace `a..b` with `text` as one undoable edit; the caret lands at
176 /// the end of the inserted text, and the selection goes.
177 pub fn replace(&mut self, a: Pos, b: Pos, text: &str, kind: EditKind) {
178 let (a, b) = (self.clamp(a.min(b)), self.clamp(a.max(b)));
179 let removed = self.text_range(a, b);
180 if removed.is_empty() && text.is_empty() {
181 return;
182 }
183 let before = (self.caret, self.anchor);
184 let end = self.raw_replace(a, b, text);
185 self.caret = end;
186 self.anchor = None;
187 self.redo.clear();
188 let edit = Edit { start: a, removed, inserted: text.to_string(), caret_before: before, caret_after: (end, None), kind };
189 // A run of typing (or deleting) is one undo step.
190 if let Some(last) = self.undo.last_mut() {
191 let joins = match kind {
192 EditKind::Typing => {
193 last.kind == EditKind::Typing
194 && edit.removed.is_empty()
195 && !text.contains('\n')
196 && end_of(last.start, &last.inserted) == a
197 }
198 EditKind::Deleting => last.kind == EditKind::Deleting && edit.inserted.is_empty() && (last.start == b || last.start == a),
199 EditKind::Other => false,
200 };
201 if joins {
202 match kind {
203 EditKind::Typing => last.inserted.push_str(text),
204 _ if last.start == b => {
205 // Backspacing: the new text removed sits before.
206 last.removed.insert_str(0, &edit.removed);
207 last.start = a;
208 }
209 _ => last.removed.push_str(&edit.removed),
210 }
211 last.caret_after = edit.caret_after;
212 return;
213 }
214 }
215 self.undo.push(edit);
216 }
217
218 /// Type `text` over the selection, or at the caret.
219 pub fn insert(&mut self, text: &str, kind: EditKind) {
220 let (a, b) = self.selection().unwrap_or((self.caret, self.caret));
221 self.replace(a, b, text, kind);
222 }
223
224 pub fn delete_selection(&mut self) -> bool {
225 match self.selection() {
226 Some((a, b)) => {
227 self.replace(a, b, "", EditKind::Other);
228 true
229 }
230 None => false,
231 }
232 }
233
234 pub fn backspace(&mut self, word: bool) {
235 if self.delete_selection() {
236 return;
237 }
238 let to = if word { self.word_left(self.caret) } else { self.prev(self.caret) };
239 if to != self.caret {
240 self.replace(to, self.caret, "", EditKind::Deleting);
241 }
242 }
243
244 pub fn delete_forward(&mut self, word: bool) {
245 if self.delete_selection() {
246 return;
247 }
248 let to = if word { self.word_right(self.caret) } else { self.next(self.caret) };
249 if to != self.caret {
250 let at = self.caret;
251 self.replace(at, to, "", EditKind::Deleting);
252 self.caret = at;
253 }
254 }
255
256 pub fn undo(&mut self) -> bool {
257 let Some(e) = self.undo.pop() else { return false };
258 let end = end_of(e.start, &e.inserted);
259 self.raw_replace(e.start, end, &e.removed);
260 (self.caret, self.anchor) = e.caret_before;
261 self.redo.push(e);
262 true
263 }
264
265 pub fn redo(&mut self) -> bool {
266 let Some(e) = self.redo.pop() else { return false };
267 let end = end_of(e.start, &e.removed);
268 self.raw_replace(e.start, end, &e.inserted);
269 (self.caret, self.anchor) = e.caret_after;
270 self.undo.push(e);
271 true
272 }
273
274 /// Break the current typing run, so the next keystroke starts a new
275 /// undo step (a caret move between them, a pause).
276 pub fn seal(&mut self) {
277 if let Some(last) = self.undo.last_mut() {
278 last.kind = EditKind::Other;
279 }
280 }
281
282 /// Move the caret, extending the selection when `select`.
283 pub fn set_caret(&mut self, p: Pos, select: bool) {
284 let p = self.clamp(p);
285 if select {
286 if self.anchor.is_none() {
287 self.anchor = Some(self.caret);
288 }
289 } else {
290 self.anchor = None;
291 }
292 self.caret = p;
293 self.seal();
294 }
295
296 pub fn select_all(&mut self) {
297 self.anchor = Some(Pos::default());
298 self.caret = self.end();
299 }
300
301 // ---- boundaries ----------------------------------------------------
302
303 pub fn prev(&self, p: Pos) -> Pos {
304 if p.col == 0 {
305 return if p.line == 0 { p } else { Pos::new(p.line - 1, self.line(p.line - 1).len()) };
306 }
307 let s = self.line(p.line);
308 let col = s[..p.col].char_indices().next_back().map(|(i, _)| i).unwrap_or(0);
309 Pos::new(p.line, col)
310 }
311
312 pub fn next(&self, p: Pos) -> Pos {
313 let s = self.line(p.line);
314 if p.col >= s.len() {
315 return if p.line + 1 >= self.lines.len() { p } else { Pos::new(p.line + 1, 0) };
316 }
317 let c = s[p.col..].chars().next().map(char::len_utf8).unwrap_or(1);
318 Pos::new(p.line, p.col + c)
319 }
320
321 /// The start of the word before `p` (skipping spaces first), or the
322 /// end of the previous line at a line start.
323 pub fn word_left(&self, p: Pos) -> Pos {
324 if p.col == 0 {
325 return self.prev(p);
326 }
327 let s = &self.line(p.line)[..p.col];
328 let chars: Vec<(usize, char)> = s.char_indices().collect();
329 let mut i = chars.len();
330 while i > 0 && chars[i - 1].1.is_whitespace() {
331 i -= 1;
332 }
333 let word = |c: char| c.is_alphanumeric() || c == '_';
334 if i > 0 {
335 let in_word = word(chars[i - 1].1);
336 while i > 0 && !chars[i - 1].1.is_whitespace() && word(chars[i - 1].1) == in_word {
337 i -= 1;
338 }
339 }
340 Pos::new(p.line, chars.get(i).map(|(b, _)| *b).unwrap_or(0))
341 }
342
343 pub fn word_right(&self, p: Pos) -> Pos {
344 let s = self.line(p.line);
345 if p.col >= s.len() {
346 return self.next(p);
347 }
348 let rest: Vec<(usize, char)> = s[p.col..].char_indices().collect();
349 let mut i = 0;
350 while i < rest.len() && rest[i].1.is_whitespace() {
351 i += 1;
352 }
353 let word = |c: char| c.is_alphanumeric() || c == '_';
354 if i < rest.len() {
355 let in_word = word(rest[i].1);
356 while i < rest.len() && !rest[i].1.is_whitespace() && word(rest[i].1) == in_word {
357 i += 1;
358 }
359 }
360 Pos::new(p.line, p.col + rest.get(i).map(|(b, _)| *b).unwrap_or(s.len() - p.col))
361 }
362
363 /// The word around `p` (a double-click's selection).
364 pub fn word_at(&self, p: Pos) -> (Pos, Pos) {
365 let s = self.line(p.line);
366 let word = |c: char| c.is_alphanumeric() || c == '_';
367 let mut a = p.col;
368 while a > 0 {
369 let prev = s[..a].chars().next_back().unwrap();
370 if !word(prev) {
371 break;
372 }
373 a -= prev.len_utf8();
374 }
375 let mut b = p.col;
376 while let Some(c) = s[b..].chars().next() {
377 if !word(c) {
378 break;
379 }
380 b += c.len_utf8();
381 }
382 (Pos::new(p.line, a), Pos::new(p.line, b))
383 }
384 }
385
386 #[cfg(test)]
387 mod tests {
388 use super::*;
389
390 #[test]
391 fn insert_newlines_and_changes() {
392 let mut b = Buffer::new("ab\ncd");
393 b.take_changes();
394 b.caret = Pos::new(0, 1);
395 b.insert("X\nY", EditKind::Other);
396 assert_eq!(b.text(), "aX\nYb\ncd");
397 assert_eq!(b.caret, Pos::new(1, 1));
398 assert_eq!(b.take_changes(), [Change { first: 0, removed: 1, inserted: 2 }]);
399 b.set_caret(Pos::new(0, 1), false);
400 b.set_caret(Pos::new(2, 1), true);
401 assert_eq!(b.selected_text().as_deref(), Some("X\nYb\nc"));
402 b.insert("", EditKind::Other);
403 assert_eq!(b.text(), "ad");
404 }
405
406 #[test]
407 fn typing_undoes_as_one_step_and_redoes() {
408 let mut b = Buffer::new("");
409 for c in ["h", "e", "y"] {
410 b.insert(c, EditKind::Typing);
411 }
412 b.insert("\n", EditKind::Other);
413 b.insert("x", EditKind::Typing);
414 assert_eq!(b.text(), "hey\nx");
415 assert!(b.undo());
416 assert_eq!(b.text(), "hey\n");
417 assert!(b.undo());
418 assert!(b.undo());
419 assert_eq!(b.text(), "");
420 assert!(!b.undo());
421 assert!(b.redo());
422 assert_eq!(b.text(), "hey");
423 assert_eq!(b.caret, Pos::new(0, 3));
424 }
425
426 #[test]
427 fn backspace_runs_join_and_restore() {
428 let mut b = Buffer::new("héllo wörld");
429 b.caret = b.end();
430 for _ in 0..3 {
431 b.backspace(false);
432 }
433 assert_eq!(b.text(), "héllo wö");
434 b.backspace(true);
435 assert_eq!(b.text(), "héllo ");
436 assert!(b.undo());
437 assert_eq!(b.text(), "héllo wörld");
438 // At a line start, backspace joins lines.
439 let mut b = Buffer::new("a\nb");
440 b.caret = Pos::new(1, 0);
441 b.backspace(false);
442 assert_eq!(b.text(), "ab");
443 assert_eq!(b.caret, Pos::new(0, 1));
444 }
445
446 #[test]
447 fn words_and_boundaries() {
448 let b = Buffer::new("foo bar_baz qux.");
449 assert_eq!(b.word_right(Pos::new(0, 0)), Pos::new(0, 3));
450 assert_eq!(b.word_right(Pos::new(0, 3)), Pos::new(0, 11));
451 assert_eq!(b.word_left(Pos::new(0, 13)), Pos::new(0, 4));
452 assert_eq!(b.word_at(Pos::new(0, 6)), (Pos::new(0, 4), Pos::new(0, 11)));
453 let b = Buffer::new("é");
454 assert_eq!(b.next(Pos::new(0, 0)), Pos::new(0, 2));
455 assert_eq!(b.clamp(Pos::new(0, 1)), Pos::new(0, 0));
456 }
457
458 #[test]
459 fn delete_forward_keeps_the_caret() {
460 let mut b = Buffer::new("abc");
461 b.caret = Pos::new(0, 1);
462 b.delete_forward(false);
463 b.delete_forward(false);
464 assert_eq!(b.text(), "a");
465 assert_eq!(b.caret, Pos::new(0, 1));
466 assert!(b.undo());
467 assert_eq!(b.text(), "abc");
468 }
469 }