1use std::ops::Range;
2use std::time::{Duration, Instant};
3
4use crate::attr::{SpanAttr, StyledSpan};
5use crate::piece::TextBuffer;
6use crate::styled::StyledBuffer;
7
8#[derive(Clone, Debug, PartialEq)]
9#[non_exhaustive]
10pub enum Edit {
11 Insert {
12 pos: usize,
13 text: String,
14 },
15
16 Delete {
17 pos: usize,
18 text: String,
19 },
20
21 AttrChange {
22 range: Range<usize>,
23 before: Vec<StyledSpan>,
24 after: Vec<StyledSpan>,
25 },
26}
27
28pub type UndoGroup = Vec<Edit>;
29
30#[derive(Clone, Debug)]
31pub struct UndoStack {
32 undo: Vec<UndoGroup>,
33 redo: Vec<UndoGroup>,
34 limit: usize,
35 coalesce_window: Duration,
36 last_push: Option<Instant>,
37}
38
39impl UndoStack {
40 pub fn new(limit: usize) -> Self {
41 Self {
42 undo: Vec::new(),
43 redo: Vec::new(),
44 limit: limit.max(1),
45 coalesce_window: Duration::from_millis(0),
46 last_push: None,
47 }
48 }
49
50 pub fn coalesce_window(mut self, window: Duration) -> Self {
51 self.coalesce_window = window;
52 self
53 }
54
55 pub fn set_limit(&mut self, limit: usize) {
56 self.limit = limit.max(1);
57 while self.undo.len() > self.limit {
58 self.undo.remove(0);
59 }
60 while self.redo.len() > self.limit {
61 self.redo.remove(0);
62 }
63 }
64
65 pub fn can_undo(&self) -> bool {
66 !self.undo.is_empty()
67 }
68
69 pub fn can_redo(&self) -> bool {
70 !self.redo.is_empty()
71 }
72
73 pub fn undo_len(&self) -> usize {
74 self.undo.len()
75 }
76
77 pub fn redo_len(&self) -> usize {
78 self.redo.len()
79 }
80
81 pub fn clear(&mut self) {
82 self.undo.clear();
83 self.redo.clear();
84 self.last_push = None;
85 }
86
87 fn push_group_inner(&mut self, group: UndoGroup) {
88 if group.is_empty() {
89 return;
90 }
91 self.undo.push(group);
92 while self.undo.len() > self.limit {
93 self.undo.remove(0);
94 }
95 self.redo.clear();
96 self.last_push = Some(Instant::now());
97 }
98
99 pub fn push_insert(&mut self, pos: usize, text: &str) {
100 if text.is_empty() {
101 return;
102 }
103 let now = Instant::now();
104 if !self.coalesce_window.is_zero()
105 && let Some(last) = self.last_push
106 && now.duration_since(last) <= self.coalesce_window
107 && let Some(group) = self.undo.last_mut()
108 && let [
109 Edit::Insert {
110 pos: prev_pos,
111 text: prev_text,
112 },
113 ] = group.as_mut_slice()
114 && *prev_pos + prev_text.len() == pos
115 {
116 prev_text.push_str(text);
117 self.last_push = Some(now);
118 self.redo.clear();
119 return;
120 }
121 self.push_group_inner(vec![Edit::Insert {
122 pos,
123 text: text.to_string(),
124 }]);
125 }
126
127 pub fn push_delete(&mut self, pos: usize, text: &str) {
128 if text.is_empty() {
129 return;
130 }
131 let now = Instant::now();
132 if !self.coalesce_window.is_zero()
133 && let Some(last) = self.last_push
134 && now.duration_since(last) <= self.coalesce_window
135 && let Some(group) = self.undo.last_mut()
136 && let [
137 Edit::Delete {
138 pos: prev_pos,
139 text: prev_text,
140 },
141 ] = group.as_mut_slice()
142 {
143 if pos + text.len() == *prev_pos {
144 let mut merged = text.to_string();
145 merged.push_str(prev_text);
146 *prev_text = merged;
147 *prev_pos = pos;
148 self.last_push = Some(now);
149 self.redo.clear();
150 return;
151 }
152
153 if pos == *prev_pos + prev_text.len() {
154 prev_text.push_str(text);
155 self.last_push = Some(now);
156 self.redo.clear();
157 return;
158 }
159 }
160 self.push_group_inner(vec![Edit::Delete {
161 pos,
162 text: text.to_string(),
163 }]);
164 }
165
166 pub fn push_group(&mut self, group: UndoGroup) {
167 self.push_group_inner(group);
168 }
169
170 pub fn push_attr_change(
171 &mut self,
172 range: Range<usize>,
173 before: Vec<StyledSpan>,
174 after: Vec<StyledSpan>,
175 ) {
176 if before == after {
177 return;
178 }
179 self.push_group_inner(vec![Edit::AttrChange {
180 range,
181 before,
182 after,
183 }]);
184 }
185
186 pub fn undo(&mut self, buf: &mut TextBuffer) -> Option<(usize, usize)> {
187 let group = self.undo.pop()?;
188 let mut lo = usize::MAX;
189 let mut hi = 0usize;
190 for edit in group.iter().rev() {
191 match edit {
192 Edit::Insert { pos, text } => {
193 let end = pos + text.len();
194 buf.delete(*pos..end);
195 lo = lo.min(*pos);
196 hi = hi.max(*pos);
197 }
198 Edit::Delete { pos, text } => {
199 buf.insert(*pos, text);
200 lo = lo.min(*pos);
201 hi = hi.max(pos + text.len());
202 }
203 Edit::AttrChange { range, .. } => {
204 lo = lo.min(range.start);
205 hi = hi.max(range.end);
206 }
207 }
208 }
209 self.redo.push(group);
210 while self.redo.len() > self.limit {
211 self.redo.remove(0);
212 }
213 self.last_push = None;
214 if lo == usize::MAX {
215 return None;
216 }
217 Some((lo, hi))
218 }
219
220 pub fn redo(&mut self, buf: &mut TextBuffer) -> Option<(usize, usize)> {
221 let group = self.redo.pop()?;
222 let mut lo = usize::MAX;
223 let mut hi = 0usize;
224 for edit in &group {
225 match edit {
226 Edit::Insert { pos, text } => {
227 buf.insert(*pos, text);
228 lo = lo.min(*pos);
229 hi = hi.max(pos + text.len());
230 }
231 Edit::Delete { pos, text } => {
232 let end = pos + text.len();
233 buf.delete(*pos..end);
234 lo = lo.min(*pos);
235 hi = hi.max(*pos);
236 }
237 Edit::AttrChange { range, .. } => {
238 lo = lo.min(range.start);
239 hi = hi.max(range.end);
240 }
241 }
242 }
243 self.undo.push(group);
244 while self.undo.len() > self.limit {
245 self.undo.remove(0);
246 }
247 self.last_push = None;
248 if lo == usize::MAX {
249 return None;
250 }
251 Some((lo, hi))
252 }
253
254 pub fn undo_styled(&mut self, buf: &mut StyledBuffer) -> Option<(usize, usize)> {
255 let group = self.undo.pop()?;
256 let mut texts: Vec<&Edit> = group
257 .iter()
258 .filter(|e| matches!(e, Edit::Insert { .. } | Edit::Delete { .. }))
259 .collect();
260 let mut styles: Vec<&Edit> = group
261 .iter()
262 .filter(|e| matches!(e, Edit::AttrChange { .. }))
263 .collect();
264 texts.reverse();
265 styles.reverse();
266 let mut lo = usize::MAX;
267 let mut hi = 0usize;
268 for edit in texts {
269 match edit {
270 Edit::Insert { pos, text } => {
271 let end = pos + text.len();
272 buf.delete(*pos..end);
273 lo = lo.min(*pos);
274 hi = hi.max(*pos);
275 }
276 Edit::Delete { pos, text } => {
277 buf.insert(*pos, text, Some(SpanAttr::plain()));
278 lo = lo.min(*pos);
279 hi = hi.max(pos + text.len());
280 }
281 _ => {
282 debug_assert!(false, "future Edit variant in text undo path");
283 continue;
284 }
285 }
286 }
287 for edit in styles {
288 if let Edit::AttrChange { range, before, .. } = edit {
289 buf.apply_attr_range(range.clone(), before);
290 lo = lo.min(range.start);
291 hi = hi.max(range.end);
292 }
293 }
294 self.redo.push(group);
295 while self.redo.len() > self.limit {
296 self.redo.remove(0);
297 }
298 self.last_push = None;
299 if lo == usize::MAX {
300 return None;
301 }
302 Some((lo, hi))
303 }
304
305 pub fn redo_styled(&mut self, buf: &mut StyledBuffer) -> Option<(usize, usize)> {
306 let group = self.redo.pop()?;
307 let texts: Vec<&Edit> = group
308 .iter()
309 .filter(|e| matches!(e, Edit::Insert { .. } | Edit::Delete { .. }))
310 .collect();
311 let styles: Vec<&Edit> = group
312 .iter()
313 .filter(|e| matches!(e, Edit::AttrChange { .. }))
314 .collect();
315 let mut lo = usize::MAX;
316 let mut hi = 0usize;
317 for edit in texts {
318 match edit {
319 Edit::Insert { pos, text } => {
320 buf.insert(*pos, text, Some(SpanAttr::plain()));
321 lo = lo.min(*pos);
322 hi = hi.max(pos + text.len());
323 }
324 Edit::Delete { pos, text } => {
325 let end = pos + text.len();
326 buf.delete(*pos..end);
327 lo = lo.min(*pos);
328 hi = hi.max(*pos);
329 }
330 _ => {
331 debug_assert!(false, "future Edit variant in text redo path");
332 continue;
333 }
334 }
335 }
336 for edit in styles {
337 if let Edit::AttrChange { range, after, .. } = edit {
338 buf.apply_attr_range(range.clone(), after);
339 lo = lo.min(range.start);
340 hi = hi.max(range.end);
341 }
342 }
343 self.undo.push(group);
344 while self.undo.len() > self.limit {
345 self.undo.remove(0);
346 }
347 self.last_push = None;
348 if lo == usize::MAX {
349 return None;
350 }
351 Some((lo, hi))
352 }
353}
354
355#[cfg(test)]
356mod tests {
357 use super::*;
358 use crate::piece::TextBuffer;
359
360 #[test]
361 fn insert_undo_redo_roundtrip() {
362 let mut buf = TextBuffer::from("hello");
363 let mut undo = UndoStack::new(100);
364 buf.insert(5, " world");
365 undo.push_insert(5, " world");
366 assert_eq!(buf.to_string(), "hello world");
367 undo.undo(&mut buf);
368 assert_eq!(buf.to_string(), "hello");
369 assert!(undo.can_redo());
370 undo.redo(&mut buf);
371 assert_eq!(buf.to_string(), "hello world");
372 }
373
374 #[test]
375 fn delete_undo_restores_text() {
376 let mut buf = TextBuffer::from("hello world");
377 let removed = buf.delete(5..11);
378 let mut undo = UndoStack::new(100);
379 undo.push_delete(5, &removed);
380 assert_eq!(buf.to_string(), "hello");
381 undo.undo(&mut buf);
382 assert_eq!(buf.to_string(), "hello world");
383 }
384
385 #[test]
386 fn typing_coalesces_into_one_step() {
387 let mut buf = TextBuffer::new();
388 let mut undo = UndoStack::new(100).coalesce_window(Duration::from_secs(60));
389 for (i, c) in "abc".chars().enumerate() {
390 buf.insert(i, &c.to_string());
391 undo.push_insert(i, &c.to_string());
392 }
393 assert_eq!(undo.undo_len(), 1);
394 undo.undo(&mut buf);
395 assert_eq!(buf.to_string(), "");
396 }
397
398 #[test]
399 fn separate_bursts_stay_separate() {
400 let mut buf = TextBuffer::new();
401 let mut undo = UndoStack::new(100);
402 buf.insert(0, "a");
403 undo.push_insert(0, "a");
404 buf.insert(1, "b");
405 undo.push_insert(1, "b");
406 assert_eq!(undo.undo_len(), 2);
407 }
408
409 #[test]
410 fn group_undoes_atomically() {
411 let mut buf = TextBuffer::from("a\nb");
412 let mut undo = UndoStack::new(100);
413 buf.insert(0, " ");
414 buf.insert(4, " ");
415 undo.push_group(vec![
416 Edit::Insert {
417 pos: 0,
418 text: " ".into(),
419 },
420 Edit::Insert {
421 pos: 4,
422 text: " ".into(),
423 },
424 ]);
425 assert_eq!(buf.to_string(), " a\n b");
426 undo.undo(&mut buf);
427 assert_eq!(buf.to_string(), "a\nb");
428 undo.redo(&mut buf);
429 assert_eq!(buf.to_string(), " a\n b");
430 }
431
432 #[test]
433 fn limit_drops_oldest_and_new_edit_clears_redo() {
434 let mut buf = TextBuffer::from("");
435 let mut undo = UndoStack::new(2);
436 for c in ['a', 'b', 'c'] {
437 let pos = buf.len_bytes();
438 buf.insert(pos, &c.to_string());
439 undo.push_insert(pos, &c.to_string());
440 }
441 assert_eq!(undo.undo_len(), 2);
442 undo.undo(&mut buf);
443 assert!(undo.can_redo());
444 let pos = buf.len_bytes();
445 buf.insert(pos, "z");
446 undo.push_insert(pos, "z");
447 assert!(!undo.can_redo());
448 }
449
450 #[test]
451 fn styled_insert_undo_redo_restores_text_style_caret() {
452 use crate::attr::{SpanAttr, StyledSpan};
453 use crate::styled::StyledBuffer;
454 let mut buf = StyledBuffer::from("hello");
455 let mut undo = UndoStack::new(100);
456
457 let before: Vec<StyledSpan> = buf.spans().to_vec();
458 buf.insert(2, "X", Some(SpanAttr::bold()));
459 let after: Vec<StyledSpan> = buf.spans().to_vec();
460 undo.push_group(vec![
461 Edit::Insert {
462 pos: 2,
463 text: "X".into(),
464 },
465 Edit::AttrChange {
466 range: 0..buf.len_bytes(),
467 before,
468 after: after.clone(),
469 },
470 ]);
471 assert_eq!(buf.to_string(), "heXllo");
472 let caret = undo.undo_styled(&mut buf).expect("undo");
473 assert_eq!(buf.to_string(), "hello");
474 assert!(buf.spans().is_empty());
475 assert_eq!(caret.0.min(caret.1), 0);
476 let caret = undo.redo_styled(&mut buf).expect("redo");
477 assert_eq!(buf.to_string(), "heXllo");
478 assert_eq!(buf.spans(), &after);
479 assert!(caret.1 >= 3);
480 }
481
482 #[test]
483 fn styled_delete_undo_restores_bold() {
484 use crate::attr::{SpanAttr, StyledSpan};
485 use crate::styled::StyledBuffer;
486 let mut buf = StyledBuffer::from("hello world");
487 buf.set_attr(0..5, SpanAttr::bold());
488 let mut undo = UndoStack::new(100);
489 let before: Vec<StyledSpan> = buf.spans().to_vec();
490 let (removed, _) = buf.delete(0..5);
491 let after: Vec<StyledSpan> = buf.spans().to_vec();
492 undo.push_group(vec![
493 Edit::Delete {
494 pos: 0,
495 text: removed.clone(),
496 },
497 Edit::AttrChange {
498 range: 0..5,
499 before: before.clone(),
500 after,
501 },
502 ]);
503 assert_eq!(buf.to_string(), " world");
504 assert!(buf.spans().is_empty());
505 undo.undo_styled(&mut buf);
506 assert_eq!(buf.to_string(), "hello world");
507 assert_eq!(buf.spans(), &before);
508 undo.redo_styled(&mut buf);
509 assert_eq!(buf.to_string(), " world");
510 assert!(buf.spans().is_empty());
511 }
512
513 #[test]
514 fn styled_set_attr_undo_redo() {
515 use crate::attr::SpanAttr;
516 use crate::styled::StyledBuffer;
517 let mut buf = StyledBuffer::from("abcdef");
518 let mut undo = UndoStack::new(100);
519 buf.set_attr(0..3, SpanAttr::bold());
520 undo.push_attr_change(0..3, vec![], buf.spans().to_vec());
521 assert_eq!(buf.spans().len(), 1);
522 undo.undo_styled(&mut buf);
523 assert!(buf.spans().is_empty());
524 undo.redo_styled(&mut buf);
525 assert_eq!(buf.spans().len(), 1);
526 }
527
528 #[test]
529 fn styled_plain_typing_still_coalesces() {
530 use crate::styled::StyledBuffer;
531 let mut buf = StyledBuffer::new();
532 let mut undo = UndoStack::new(100).coalesce_window(Duration::from_secs(60));
533 for (i, c) in "abc".chars().enumerate() {
534 buf.insert(i, &c.to_string(), Some(SpanAttr::plain()));
535 undo.push_insert(i, &c.to_string());
536 }
537 assert_eq!(undo.undo_len(), 1);
538 undo.undo_styled(&mut buf);
539 assert_eq!(buf.to_string(), "");
540 }
541
542 #[test]
543 fn styled_graphemes_never_split_bytes() {
544 use crate::attr::SpanAttr;
545 use crate::styled::StyledBuffer;
546
547 let text = "a👨👩👧🇵🇱é\r\nz";
548 let mut buf = StyledBuffer::from(text);
549 let mut undo = UndoStack::new(10);
550 let len = buf.len_bytes();
551 let before = buf.spans().to_vec();
552 buf.set_attr(0..len, SpanAttr::bold());
553 undo.push_attr_change(0..len, before, buf.spans().to_vec());
554
555 let p = buf.snap(3);
556 buf.insert(p, "Q", None);
557 undo.push_insert(p, "Q");
558 assert!(buf.to_string().contains('Q'));
559 for s in buf.spans() {
560 assert_eq!(buf.snap(s.start), s.start);
561 assert_eq!(buf.snap(s.end), s.end);
562 }
563 undo.undo_styled(&mut buf);
564
565 assert!(!buf.to_string().contains('Q'));
566 assert_eq!(buf.spans().len(), 1);
567 }
568}