loro_internal/
undo.rs

1use std::{collections::VecDeque, sync::Arc};
2
3use crate::sync::{AtomicU64, Mutex};
4use either::Either;
5use fxhash::FxHashMap;
6use loro_common::{
7    ContainerID, Counter, CounterSpan, HasIdSpan, IdSpan, LoroResult, LoroValue, PeerID,
8};
9use tracing::{debug_span, info_span, instrument};
10
11use crate::{
12    change::{get_sys_timestamp, Timestamp},
13    cursor::{AbsolutePosition, Cursor},
14    delta::TreeExternalDiff,
15    event::{Diff, EventTriggerKind},
16    version::Frontiers,
17    ContainerDiff, DiffEvent, DocDiff, LoroDoc, Subscription,
18};
19
20/// A batch of diffs.
21///
22/// You can use `loroDoc.apply_diff(diff)` to apply the diff to the document.
23#[derive(Debug, Clone, Default)]
24pub struct DiffBatch {
25    pub cid_to_events: FxHashMap<ContainerID, Diff>,
26    pub order: Vec<ContainerID>,
27}
28
29impl DiffBatch {
30    pub fn new(diff: Vec<DocDiff>) -> Self {
31        let mut map: FxHashMap<ContainerID, Diff> = Default::default();
32        let mut order: Vec<ContainerID> = Vec::with_capacity(diff.len());
33        for d in diff.into_iter() {
34            for item in d.diff.into_iter() {
35                let old = map.insert(item.id.clone(), item.diff);
36                assert!(old.is_none());
37                order.push(item.id.clone());
38            }
39        }
40
41        Self {
42            cid_to_events: map,
43            order,
44        }
45    }
46
47    pub fn compose(&mut self, other: &Self) {
48        if other.cid_to_events.is_empty() {
49            return;
50        }
51
52        for (id, diff) in other.iter() {
53            if let Some(this_diff) = self.cid_to_events.get_mut(id) {
54                this_diff.compose_ref(diff);
55            } else {
56                self.cid_to_events.insert(id.clone(), diff.clone());
57                self.order.push(id.clone());
58            }
59        }
60    }
61
62    pub fn transform(&mut self, other: &Self, left_priority: bool) {
63        if other.cid_to_events.is_empty() || self.cid_to_events.is_empty() {
64            return;
65        }
66
67        for (idx, diff) in self.cid_to_events.iter_mut() {
68            if let Some(b_diff) = other.cid_to_events.get(idx) {
69                diff.transform(b_diff, left_priority);
70            }
71        }
72    }
73
74    pub fn clear(&mut self) {
75        self.cid_to_events.clear();
76        self.order.clear();
77    }
78
79    pub fn iter(&self) -> impl Iterator<Item = (&ContainerID, &Diff)> + '_ {
80        self.order
81            .iter()
82            .map(|cid| (cid, self.cid_to_events.get(cid).unwrap()))
83    }
84
85    #[allow(clippy::should_implement_trait)]
86    pub fn into_iter(self) -> impl Iterator<Item = (ContainerID, Diff)> {
87        let mut cid_to_events = self.cid_to_events;
88        self.order.into_iter().map(move |cid| {
89            let d = cid_to_events.remove(&cid).unwrap();
90            (cid, d)
91        })
92    }
93}
94
95fn transform_cursor(
96    cursor_with_pos: &mut CursorWithPos,
97    remote_diff: &DiffBatch,
98    doc: &LoroDoc,
99    container_remap: &FxHashMap<ContainerID, ContainerID>,
100) {
101    let mut cid = &cursor_with_pos.cursor.container;
102    while let Some(new_cid) = container_remap.get(cid) {
103        cid = new_cid;
104    }
105
106    if let Some(diff) = remote_diff.cid_to_events.get(cid) {
107        let new_pos = diff.transform_cursor(cursor_with_pos.pos.pos, false);
108        cursor_with_pos.pos.pos = new_pos;
109    };
110
111    let new_pos = cursor_with_pos.pos.pos;
112    match doc.get_handler(cid.clone()).unwrap() {
113        crate::handler::Handler::Text(h) => {
114            let Some(new_cursor) = h.get_cursor_internal(new_pos, cursor_with_pos.pos.side, false)
115            else {
116                return;
117            };
118
119            cursor_with_pos.cursor = new_cursor;
120        }
121        crate::handler::Handler::List(h) => {
122            let Some(new_cursor) = h.get_cursor(new_pos, cursor_with_pos.pos.side) else {
123                return;
124            };
125
126            cursor_with_pos.cursor = new_cursor;
127        }
128        crate::handler::Handler::MovableList(h) => {
129            let Some(new_cursor) = h.get_cursor(new_pos, cursor_with_pos.pos.side) else {
130                return;
131            };
132
133            cursor_with_pos.cursor = new_cursor;
134        }
135        crate::handler::Handler::Map(_) => {}
136        crate::handler::Handler::Tree(_) => {}
137        crate::handler::Handler::Unknown(_) => {}
138        #[cfg(feature = "counter")]
139        crate::handler::Handler::Counter(_) => {}
140    }
141}
142
143/// UndoManager is responsible for managing undo/redo from the current peer's perspective.
144///
145/// Undo/local is local: it cannot be used to undone the changes made by other peers.
146/// If you want to undo changes made by other peers, you may need to use the time travel feature.
147///
148/// PeerID cannot be changed during the lifetime of the UndoManager
149pub struct UndoManager {
150    peer: Arc<AtomicU64>,
151    container_remap: Arc<Mutex<FxHashMap<ContainerID, ContainerID>>>,
152    inner: Arc<Mutex<UndoManagerInner>>,
153    _peer_id_change_sub: Subscription,
154    _undo_sub: Subscription,
155    doc: LoroDoc,
156}
157
158impl std::fmt::Debug for UndoManager {
159    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
160        f.debug_struct("UndoManager")
161            .field("peer", &self.peer)
162            .field("container_remap", &self.container_remap)
163            .field("inner", &self.inner)
164            .finish()
165    }
166}
167
168#[derive(Debug, Clone, Copy, PartialEq, Eq)]
169pub enum UndoOrRedo {
170    Undo,
171    Redo,
172}
173
174impl UndoOrRedo {
175    fn opposite(&self) -> UndoOrRedo {
176        match self {
177            Self::Undo => Self::Redo,
178            Self::Redo => Self::Undo,
179        }
180    }
181}
182
183/// When a undo/redo item is pushed, the undo manager will call the on_push callback to get the meta data of the undo item.
184/// The returned cursors will be recorded for a new pushed undo item.
185pub type OnPush = Box<
186    dyn for<'a> Fn(UndoOrRedo, CounterSpan, Option<DiffEvent<'a>>) -> UndoItemMeta + Send + Sync,
187>;
188pub type OnPop = Box<dyn Fn(UndoOrRedo, CounterSpan, UndoItemMeta) + Send + Sync>;
189
190struct UndoManagerInner {
191    next_counter: Option<Counter>,
192    undo_stack: Stack,
193    redo_stack: Stack,
194    processing_undo: bool,
195    last_undo_time: i64,
196    merge_interval_in_ms: i64,
197    max_stack_size: usize,
198    exclude_origin_prefixes: Vec<Box<str>>,
199    last_popped_selection: Option<Vec<CursorWithPos>>,
200    on_push: Option<OnPush>,
201    on_pop: Option<OnPop>,
202}
203
204impl std::fmt::Debug for UndoManagerInner {
205    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
206        f.debug_struct("UndoManagerInner")
207            .field("latest_counter", &self.next_counter)
208            .field("undo_stack", &self.undo_stack)
209            .field("redo_stack", &self.redo_stack)
210            .field("processing_undo", &self.processing_undo)
211            .field("last_undo_time", &self.last_undo_time)
212            .field("merge_interval", &self.merge_interval_in_ms)
213            .field("max_stack_size", &self.max_stack_size)
214            .field("exclude_origin_prefixes", &self.exclude_origin_prefixes)
215            .finish()
216    }
217}
218
219#[derive(Debug)]
220struct Stack {
221    stack: VecDeque<(VecDeque<StackItem>, Arc<Mutex<DiffBatch>>)>,
222    size: usize,
223}
224
225#[derive(Debug, Clone)]
226struct StackItem {
227    span: CounterSpan,
228    meta: UndoItemMeta,
229}
230
231/// The metadata of an undo item.
232///
233/// The cursors inside the metadata will be transformed by remote operations as well.
234/// So that when the item is popped, users can restore the cursors position correctly.
235#[derive(Debug, Default, Clone)]
236pub struct UndoItemMeta {
237    pub value: LoroValue,
238    pub cursors: Vec<CursorWithPos>,
239}
240
241#[derive(Debug, Clone)]
242pub struct CursorWithPos {
243    pub cursor: Cursor,
244    pub pos: AbsolutePosition,
245}
246
247impl UndoItemMeta {
248    pub fn new() -> Self {
249        Self {
250            value: LoroValue::Null,
251            cursors: Default::default(),
252        }
253    }
254
255    /// It's assumed that the cursor is just acquired before the ops that
256    /// need to be undo/redo.
257    ///
258    /// We need to rely on the validity of the original pos value
259    pub fn add_cursor(&mut self, cursor: &Cursor) {
260        self.cursors.push(CursorWithPos {
261            cursor: cursor.clone(),
262            pos: AbsolutePosition {
263                pos: cursor.origin_pos,
264                side: cursor.side,
265            },
266        });
267    }
268
269    pub fn set_value(&mut self, value: LoroValue) {
270        self.value = value;
271    }
272}
273
274impl Stack {
275    pub fn new() -> Self {
276        let mut stack = VecDeque::new();
277        stack.push_back((VecDeque::new(), Arc::new(Mutex::new(Default::default()))));
278        Stack { stack, size: 0 }
279    }
280
281    pub fn pop(&mut self) -> Option<(StackItem, Arc<Mutex<DiffBatch>>)> {
282        while self.stack.back().unwrap().0.is_empty() && self.stack.len() > 1 {
283            let (_, diff) = self.stack.pop_back().unwrap();
284            let diff = diff.lock().unwrap();
285            if !diff.cid_to_events.is_empty() {
286                self.stack
287                    .back_mut()
288                    .unwrap()
289                    .1
290                    .lock()
291                    .unwrap()
292                    .compose(&diff);
293            }
294        }
295
296        if self.stack.len() == 1 && self.stack.back().unwrap().0.is_empty() {
297            // If the stack is empty, we need to clear the remote diff
298            self.stack.back_mut().unwrap().1.lock().unwrap().clear();
299            return None;
300        }
301
302        self.size -= 1;
303        let last = self.stack.back_mut().unwrap();
304        last.0.pop_back().map(|x| (x, last.1.clone()))
305        // If this row in stack is empty, we don't pop it right away
306        // Because we still need the remote diff to be available.
307        // Cursor position transformation relies on the remote diff in the same row.
308    }
309
310    pub fn push(&mut self, span: CounterSpan, meta: UndoItemMeta) {
311        self.push_with_merge(span, meta, false)
312    }
313
314    pub fn push_with_merge(&mut self, span: CounterSpan, meta: UndoItemMeta, can_merge: bool) {
315        let last = self.stack.back_mut().unwrap();
316        let last_remote_diff = last.1.lock().unwrap();
317        if !last_remote_diff.cid_to_events.is_empty() {
318            // If the remote diff is not empty, we cannot merge
319            drop(last_remote_diff);
320            let mut v = VecDeque::new();
321            v.push_back(StackItem { span, meta });
322            self.stack
323                .push_back((v, Arc::new(Mutex::new(DiffBatch::default()))));
324
325            self.size += 1;
326        } else {
327            if can_merge {
328                if let Some(last_span) = last.0.back_mut() {
329                    if last_span.span.end == span.start {
330                        // merge the span
331                        last_span.span.end = span.end;
332                        return;
333                    }
334                }
335            }
336
337            self.size += 1;
338            last.0.push_back(StackItem { span, meta });
339        }
340    }
341
342    pub fn compose_remote_event(&mut self, diff: &[&ContainerDiff]) {
343        if self.is_empty() {
344            return;
345        }
346
347        let remote_diff = &mut self.stack.back_mut().unwrap().1;
348        let mut remote_diff = remote_diff.lock().unwrap();
349        for e in diff {
350            if let Some(d) = remote_diff.cid_to_events.get_mut(&e.id) {
351                d.compose_ref(&e.diff);
352            } else {
353                remote_diff
354                    .cid_to_events
355                    .insert(e.id.clone(), e.diff.clone());
356                remote_diff.order.push(e.id.clone());
357            }
358        }
359    }
360
361    pub fn transform_based_on_this_delta(&mut self, diff: &DiffBatch) {
362        if self.is_empty() {
363            return;
364        }
365        let remote_diff = &mut self.stack.back_mut().unwrap().1;
366        remote_diff.lock().unwrap().transform(diff, false);
367    }
368
369    pub fn clear(&mut self) {
370        self.stack = VecDeque::new();
371        self.stack.push_back((VecDeque::new(), Default::default()));
372        self.size = 0;
373    }
374
375    pub fn is_empty(&self) -> bool {
376        self.size == 0
377    }
378
379    pub fn len(&self) -> usize {
380        self.size
381    }
382
383    fn pop_front(&mut self) {
384        if self.is_empty() {
385            return;
386        }
387
388        self.size -= 1;
389        let first = self.stack.front_mut().unwrap();
390        let f = first.0.pop_front();
391        assert!(f.is_some());
392        if first.0.is_empty() {
393            self.stack.pop_front();
394        }
395    }
396}
397
398impl Default for Stack {
399    fn default() -> Self {
400        Stack::new()
401    }
402}
403
404impl UndoManagerInner {
405    fn new(last_counter: Counter) -> Self {
406        Self {
407            next_counter: Some(last_counter),
408            undo_stack: Default::default(),
409            redo_stack: Default::default(),
410            processing_undo: false,
411            merge_interval_in_ms: 0,
412            last_undo_time: 0,
413            max_stack_size: usize::MAX,
414            exclude_origin_prefixes: vec![],
415            last_popped_selection: None,
416            on_pop: None,
417            on_push: None,
418        }
419    }
420
421    fn record_checkpoint(&mut self, latest_counter: Counter, event: Option<DiffEvent>) {
422        if Some(latest_counter) == self.next_counter {
423            return;
424        }
425
426        if self.next_counter.is_none() {
427            self.next_counter = Some(latest_counter);
428            return;
429        }
430
431        assert!(self.next_counter.unwrap() < latest_counter);
432        let now = get_sys_timestamp() as Timestamp;
433        let span = CounterSpan::new(self.next_counter.unwrap(), latest_counter);
434        let meta = self
435            .on_push
436            .as_ref()
437            .map(|x| x(UndoOrRedo::Undo, span, event))
438            .unwrap_or_default();
439
440        if !self.undo_stack.is_empty() && now - self.last_undo_time < self.merge_interval_in_ms {
441            self.undo_stack.push_with_merge(span, meta, true);
442        } else {
443            self.last_undo_time = now;
444            self.undo_stack.push(span, meta);
445        }
446
447        self.next_counter = Some(latest_counter);
448        self.redo_stack.clear();
449        while self.undo_stack.len() > self.max_stack_size {
450            self.undo_stack.pop_front();
451        }
452    }
453}
454
455fn get_counter_end(doc: &LoroDoc, peer: PeerID) -> Counter {
456    doc.oplog()
457        .lock()
458        .unwrap()
459        .vv()
460        .get(&peer)
461        .cloned()
462        .unwrap_or(0)
463}
464
465impl UndoManager {
466    pub fn new(doc: &LoroDoc) -> Self {
467        let peer = Arc::new(AtomicU64::new(doc.peer_id()));
468        let peer_clone = peer.clone();
469        let peer_clone2 = peer.clone();
470        let inner = Arc::new(Mutex::new(UndoManagerInner::new(get_counter_end(
471            doc,
472            doc.peer_id(),
473        ))));
474        let inner_clone = inner.clone();
475        let inner_clone2 = inner.clone();
476        let remap_containers = Arc::new(Mutex::new(FxHashMap::default()));
477        let remap_containers_clone = remap_containers.clone();
478        let undo_sub = doc.subscribe_root(Arc::new(move |event| match event.event_meta.by {
479            EventTriggerKind::Local => {
480                // TODO: PERF undo can be significantly faster if we can get
481                // the DiffBatch for undo here
482                let Ok(mut inner) = inner_clone.lock() else {
483                    return;
484                };
485                if inner.processing_undo {
486                    return;
487                }
488                if let Some(id) = event
489                    .event_meta
490                    .to
491                    .iter()
492                    .find(|x| x.peer == peer_clone.load(std::sync::atomic::Ordering::Relaxed))
493                {
494                    if inner
495                        .exclude_origin_prefixes
496                        .iter()
497                        .any(|x| event.event_meta.origin.starts_with(&**x))
498                    {
499                        // If the event is from the excluded origin, we don't record it
500                        // in the undo stack. But we need to record its effect like it's
501                        // a remote event.
502                        inner.undo_stack.compose_remote_event(event.events);
503                        inner.redo_stack.compose_remote_event(event.events);
504                        inner.next_counter = Some(id.counter + 1);
505                    } else {
506                        inner.record_checkpoint(id.counter + 1, Some(event));
507                    }
508                }
509            }
510            EventTriggerKind::Import => {
511                let mut inner = inner_clone.lock().unwrap();
512
513                for e in event.events {
514                    if let Diff::Tree(tree) = &e.diff {
515                        for item in &tree.diff {
516                            let target = item.target;
517                            if let TreeExternalDiff::Create { .. } = &item.action {
518                                // If the concurrent event is a create event, it may bring the deleted tree node back,
519                                // so we need to remove it from the remap of the container.
520                                remap_containers_clone
521                                    .lock()
522                                    .unwrap()
523                                    .remove(&target.associated_meta_container());
524                            }
525                        }
526                    }
527                }
528
529                inner.undo_stack.compose_remote_event(event.events);
530                inner.redo_stack.compose_remote_event(event.events);
531            }
532            EventTriggerKind::Checkout => {
533                let mut inner = inner_clone.lock().unwrap();
534                inner.undo_stack.clear();
535                inner.redo_stack.clear();
536                inner.next_counter = None;
537            }
538        }));
539
540        let sub = doc.subscribe_peer_id_change(Box::new(move |id| {
541            let mut inner = inner_clone2.lock().unwrap();
542            inner.undo_stack.clear();
543            inner.redo_stack.clear();
544            inner.next_counter = Some(id.counter);
545            peer_clone2.store(id.peer, std::sync::atomic::Ordering::Relaxed);
546            true
547        }));
548
549        UndoManager {
550            peer,
551            container_remap: remap_containers,
552            inner,
553            _peer_id_change_sub: sub,
554            _undo_sub: undo_sub,
555            doc: doc.clone(),
556        }
557    }
558
559    pub fn peer(&self) -> PeerID {
560        self.peer.load(std::sync::atomic::Ordering::Relaxed)
561    }
562
563    pub fn set_merge_interval(&mut self, interval: i64) {
564        self.inner.lock().unwrap().merge_interval_in_ms = interval;
565    }
566
567    pub fn set_max_undo_steps(&mut self, size: usize) {
568        self.inner.lock().unwrap().max_stack_size = size;
569    }
570
571    pub fn add_exclude_origin_prefix(&mut self, prefix: &str) {
572        self.inner
573            .lock()
574            .unwrap()
575            .exclude_origin_prefixes
576            .push(prefix.into());
577    }
578
579    pub fn record_new_checkpoint(&mut self) -> LoroResult<()> {
580        self.doc.commit_then_renew();
581        let counter = get_counter_end(&self.doc, self.peer());
582        self.inner.lock().unwrap().record_checkpoint(counter, None);
583        Ok(())
584    }
585
586    #[instrument(skip_all)]
587    pub fn undo(&mut self) -> LoroResult<bool> {
588        self.perform(
589            |x| &mut x.undo_stack,
590            |x| &mut x.redo_stack,
591            UndoOrRedo::Undo,
592        )
593    }
594
595    #[instrument(skip_all)]
596    pub fn redo(&mut self) -> LoroResult<bool> {
597        self.perform(
598            |x| &mut x.redo_stack,
599            |x| &mut x.undo_stack,
600            UndoOrRedo::Redo,
601        )
602    }
603
604    fn perform(
605        &mut self,
606        get_stack: impl Fn(&mut UndoManagerInner) -> &mut Stack,
607        get_opposite: impl Fn(&mut UndoManagerInner) -> &mut Stack,
608        kind: UndoOrRedo,
609    ) -> LoroResult<bool> {
610        let doc = &self.doc.clone();
611        // When in the undo/redo loop, the new undo/redo stack item should restore the selection
612        // to the state it was in before the item that was popped two steps ago from the stack.
613        //
614        //                          ┌────────────┐
615        //                          │Selection 1 │
616        //                          └─────┬──────┘
617        //                                │   Some
618        //                                ▼   ops
619        //                          ┌────────────┐
620        //                          │Selection 2 │
621        //                          └─────┬──────┘
622        //                                │   Some
623        //                                ▼   ops
624        //                          ┌────────────┐
625        //                          │Selection 3 │◁ ─ ─ ─ ─ ─ ─ ─  Restore  ─ ─ ─
626        //                          └─────┬──────┘                               │
627        //                                │
628        //                                │                                      │
629        //                                │                              ┌ ─ ─ ─ ─ ─ ─ ─
630        //           Enter the            │   Undo ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─▶   Push Redo   │
631        //           undo/redo ─ ─ ─ ▶    ▼                              └ ─ ─ ─ ─ ─ ─ ─
632        //             loop         ┌────────────┐                               │
633        //                          │Selection 2 │◁─ ─ ─  Restore  ─
634        //                          └─────┬──────┘                  │            │
635        //                                │
636        //                                │                         │            │
637        //                                │                 ┌ ─ ─ ─ ─ ─ ─ ─
638        //                                │   Undo ─ ─ ─ ─ ▶   Push Redo   │     │
639        //                                ▼                 └ ─ ─ ─ ─ ─ ─ ─
640        //                          ┌────────────┐                  │            │
641        //                          │Selection 1 │
642        //                          └─────┬──────┘                  │            │
643        //                                │   Redo ◀ ─ ─ ─ ─ ─ ─ ─ ─
644        //                                ▼                                      │
645        //                          ┌────────────┐
646        //         ┌   Restore   ─ ▷│Selection 2 │                               │
647        //                          └─────┬──────┘
648        //         │                      │                                      │
649        // ┌ ─ ─ ─ ─ ─ ─ ─                │
650        //    Push Undo   │◀─ ─ ─ ─ ─ ─ ─ │   Redo ◀ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘
651        // └ ─ ─ ─ ─ ─ ─ ─                ▼
652        //         │                ┌────────────┐
653        //                          │Selection 3 │
654        //         │                └─────┬──────┘
655        //          ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ▶ │   Undo
656        //                                ▼
657        //                          ┌────────────┐
658        //                          │Selection 2 │
659        //                          └────────────┘
660        //
661        // Because users may change the selections during the undo/redo loop, it's
662        // more stable to keep the selection stored in the last stack item
663        // rather than using the current selection directly.
664        self.record_new_checkpoint()?;
665        let end_counter = get_counter_end(doc, self.peer());
666        let mut top = {
667            let mut inner = self.inner.lock().unwrap();
668            inner.processing_undo = true;
669            get_stack(&mut inner).pop()
670        };
671
672        let mut executed = false;
673        while let Some((mut span, remote_diff)) = top {
674            let mut next_push_selection = None;
675            {
676                let inner = self.inner.clone();
677                // We need to clone this because otherwise <transform_delta> will be applied to the same remote diff
678                let remote_change_clone = remote_diff.lock().unwrap().clone();
679                let commit = doc.undo_internal(
680                    IdSpan {
681                        peer: self.peer(),
682                        counter: span.span,
683                    },
684                    &mut self.container_remap.lock().unwrap(),
685                    Some(&remote_change_clone),
686                    &mut |diff| {
687                        info_span!("transform remote diff").in_scope(|| {
688                            let mut inner = inner.lock().unwrap();
689                            // <transform_delta>
690                            get_stack(&mut inner).transform_based_on_this_delta(diff);
691                        });
692                    },
693                )?;
694                drop(commit);
695                let mut inner = self.inner.lock().unwrap();
696                if let Some(x) = inner.on_pop.as_ref() {
697                    for cursor in span.meta.cursors.iter_mut() {
698                        // <cursor_transform> We need to transform cursor here.
699                        // Note that right now <transform_delta> is already done,
700                        // remote_diff is also transformed by it now (that's what we need).
701                        transform_cursor(
702                            cursor,
703                            &remote_diff.lock().unwrap(),
704                            doc,
705                            &self.container_remap.lock().unwrap(),
706                        );
707                    }
708
709                    x(kind, span.span, span.meta.clone());
710                    let take = inner.last_popped_selection.take();
711                    next_push_selection = take;
712                    inner.last_popped_selection = Some(span.meta.cursors);
713                }
714            }
715            let new_counter = get_counter_end(doc, self.peer());
716            if end_counter != new_counter {
717                let mut inner = self.inner.lock().unwrap();
718                let mut meta = inner
719                    .on_push
720                    .as_ref()
721                    .map(|x| {
722                        x(
723                            kind.opposite(),
724                            CounterSpan::new(end_counter, new_counter),
725                            None,
726                        )
727                    })
728                    .unwrap_or_default();
729                if matches!(kind, UndoOrRedo::Undo) && get_opposite(&mut inner).is_empty() {
730                    // If it's the first undo, we use the cursors from the users
731                } else if let Some(inner) = next_push_selection.take() {
732                    // Otherwise, we use the cursors from the undo/redo loop
733                    meta.cursors = inner;
734                }
735
736                get_opposite(&mut inner).push(CounterSpan::new(end_counter, new_counter), meta);
737                inner.next_counter = Some(new_counter);
738                executed = true;
739                break;
740            } else {
741                // continue to pop the undo item as this undo is a no-op
742                top = get_stack(&mut self.inner.lock().unwrap()).pop();
743                continue;
744            }
745        }
746
747        self.inner.lock().unwrap().processing_undo = false;
748        Ok(executed)
749    }
750
751    pub fn can_undo(&self) -> bool {
752        !self.inner.lock().unwrap().undo_stack.is_empty()
753    }
754
755    pub fn can_redo(&self) -> bool {
756        !self.inner.lock().unwrap().redo_stack.is_empty()
757    }
758
759    pub fn set_on_push(&self, on_push: Option<OnPush>) {
760        self.inner.lock().unwrap().on_push = on_push;
761    }
762
763    pub fn set_on_pop(&self, on_pop: Option<OnPop>) {
764        self.inner.lock().unwrap().on_pop = on_pop;
765    }
766
767    pub fn clear(&self) {
768        self.inner.lock().unwrap().undo_stack.clear();
769        self.inner.lock().unwrap().redo_stack.clear();
770    }
771}
772
773/// Undo the given spans of operations.
774///
775/// # Parameters
776///
777/// - `spans`: A vector of tuples where each tuple contains an `IdSpan` and its associated `Frontiers`.
778///   - `IdSpan`: Represents a span of operations identified by an ID.
779///   - `Frontiers`: Represents the deps of the given id_span
780/// - `latest_frontiers`: The latest frontiers of the document
781/// - `calc_diff`: A closure that takes two `Frontiers` and calculates the difference between them, returning a `DiffBatch`.
782///
783/// # Returns
784///
785/// - `DiffBatch`: Applying this batch on the `latest_frontiers` will undo the ops in the given spans.
786pub(crate) fn undo(
787    spans: Vec<(IdSpan, Frontiers)>,
788    last_frontiers_or_last_bi: Either<&Frontiers, &DiffBatch>,
789    calc_diff: impl Fn(&Frontiers, &Frontiers) -> DiffBatch,
790    on_last_event_a: &mut dyn FnMut(&DiffBatch),
791) -> DiffBatch {
792    // The process of performing undo is:
793    //
794    // 0. Split the span into a series of continuous spans. There is no external dep within each continuous span.
795    //
796    // For each continuous span_i:
797    //
798    // 1. a. Calculate the event of checkout from id_span.last to id_span.deps, call it Ai. It undo the ops in the current span.
799    //    b. Calculate A'i = Ai + T(Ci-1, Ai) if i > 0, otherwise A'i = Ai.
800    //       NOTE: A'i can undo the ops in the current span and the previous spans, if it's applied on the id_span.last version.
801    // 2. Calculate the event of checkout from id_span.last to [the next span's last id] or [the latest version], call it Bi.
802    // 3. Transform event A'i based on Bi, call it Ci
803    // 4. If span_i is the last span, apply Ci to the current state.
804
805    // -------------------------------------------------------
806    // 0. Split the span into a series of continuous spans
807    // -------------------------------------------------------
808
809    let mut last_ci: Option<DiffBatch> = None;
810    for i in 0..spans.len() {
811        debug_span!("Undo", ?i, "Undo span {:?}", &spans[i]).in_scope(|| {
812            let (this_id_span, this_deps) = &spans[i];
813            // ---------------------------------------
814            // 1.a Calc event A_i
815            // ---------------------------------------
816            let mut event_a_i = debug_span!("1. Calc event A_i").in_scope(|| {
817                // Checkout to the last id of the id_span
818                calc_diff(&this_id_span.id_last().into(), this_deps)
819            });
820
821            // println!("event_a_i: {:?}", event_a_i);
822
823            // ---------------------------------------
824            // 2. Calc event B_i
825            // ---------------------------------------
826            let stack_diff_batch;
827            let event_b_i = 'block: {
828                let next = if i + 1 < spans.len() {
829                    spans[i + 1].0.id_last().into()
830                } else {
831                    match last_frontiers_or_last_bi {
832                        Either::Left(last_frontiers) => last_frontiers.clone(),
833                        Either::Right(right) => break 'block right,
834                    }
835                };
836                stack_diff_batch = Some(calc_diff(&this_id_span.id_last().into(), &next));
837                stack_diff_batch.as_ref().unwrap()
838            };
839
840            // println!("event_b_i: {:?}", event_b_i);
841
842            // event_a_prime can undo the ops in the current span and the previous spans
843            let mut event_a_prime = if let Some(mut last_ci) = last_ci.take() {
844                // ------------------------------------------------------------------------------
845                // 1.b Transform and apply Ci-1 based on Ai, call it A'i
846                // ------------------------------------------------------------------------------
847                last_ci.transform(&event_a_i, true);
848
849                event_a_i.compose(&last_ci);
850                event_a_i
851            } else {
852                event_a_i
853            };
854            if i == spans.len() - 1 {
855                on_last_event_a(&event_a_prime);
856            }
857            // --------------------------------------------------
858            // 3. Transform event A'_i based on B_i, call it C_i
859            // --------------------------------------------------
860            event_a_prime.transform(event_b_i, true);
861
862            // println!("event_a_prime: {:?}", event_a_prime);
863
864            let c_i = event_a_prime;
865            last_ci = Some(c_i);
866        });
867    }
868
869    last_ci.unwrap()
870}
loro_internal/undo.rs

loro_internal/
undo.rs
