Skip to main content

continuity_engine/
undo.rs

1//! In-memory undo grouping, coalescing, branching, and replay.
2
3use ahash::AHashMap;
4use continuity_buffer::{compute_inverse_op, Buffer, BufferId, EditRecord, UndoGroupId};
5use continuity_text::{EditOp, Selection};
6
7use crate::change::{AppliedChange, ChangeBatch, MutationKind, UndoGroupMeta};
8use crate::engine::IdGenerator;
9use crate::{Error, RopeEditDeltaWithPoints};
10
11/// Continuous typing window.
12pub const COALESCE_WINDOW_MS: i64 = 500;
13
14/// Whether a mutation can join the current typing burst.
15#[derive(Copy, Clone, Debug, Eq, PartialEq)]
16pub enum CoalesceKind {
17    /// Join a compatible group within the coalescing window.
18    Typing,
19    /// Always create a new undo group.
20    Discrete,
21}
22
23#[derive(Debug)]
24struct CoalesceState {
25    group_id: UndoGroupId,
26    command: String,
27    last_timestamp_ms: i64,
28    selections_after: Vec<Selection>,
29}
30
31/// Caller-thread-owned in-memory undo state.
32#[derive(Debug, Default)]
33pub(crate) struct UndoManager {
34    coalesce: AHashMap<BufferId, CoalesceState>,
35}
36
37impl UndoManager {
38    pub(crate) fn forget(&mut self, buffer_id: BufferId) {
39        self.coalesce.remove(&buffer_id);
40    }
41
42    #[allow(clippy::too_many_arguments)]
43    pub(crate) fn apply_group(
44        &mut self,
45        buffer: &mut Buffer,
46        ops: &[EditOp],
47        selections_before: &[Selection],
48        selections_after: &[Selection],
49        command: &str,
50        coalesce_kind: CoalesceKind,
51        timestamp_ms: i64,
52        kind: MutationKind,
53        ids: &mut dyn IdGenerator,
54    ) -> Result<Option<ChangeBatch>, Error> {
55        if ops.is_empty() {
56            return Ok(None);
57        }
58        let buffer_id = buffer.id();
59        let revision_before = buffer.revision();
60        let (group_id, new_undo_group) = self.mint_or_coalesce_group(
61            buffer,
62            command,
63            coalesce_kind,
64            selections_before,
65            timestamp_ms,
66            ids,
67        );
68        let mut changes = Vec::with_capacity(ops.len());
69        let mut deltas = Vec::with_capacity(ops.len());
70        for op in ops {
71            deltas.push(delta_with_points_for_op(buffer, op));
72            changes.push(apply_recorded_op(
73                buffer,
74                op,
75                selections_before,
76                selections_after,
77                group_id,
78            )?);
79        }
80        buffer.set_selections(selections_after.to_vec());
81        let selections_after = buffer.selections().to_vec();
82        self.coalesce.insert(
83            buffer_id,
84            CoalesceState {
85                group_id,
86                command: command.to_string(),
87                last_timestamp_ms: timestamp_ms,
88                selections_after: selections_after.clone(),
89            },
90        );
91        Ok(Some(ChangeBatch {
92            buffer_id,
93            kind,
94            timestamp_ms,
95            command: command.to_string(),
96            revision_before,
97            revision_after: buffer.revision(),
98            undo_group_id: group_id,
99            new_undo_group,
100            selections_before: selections_before.to_vec(),
101            selections_after,
102            changes,
103            checksum_after: buffer.running_checksum(),
104            deltas,
105        }))
106    }
107
108    pub(crate) fn apply_single(
109        &mut self,
110        buffer: &mut Buffer,
111        op: &EditOp,
112        command: &str,
113        timestamp_ms: i64,
114        ids: &mut dyn IdGenerator,
115    ) -> Result<ChangeBatch, Error> {
116        let selections_before = buffer.selections().to_vec();
117        let revision_before = buffer.revision();
118        let buffer_id = buffer.id();
119        let (group_id, new_undo_group) = self.mint_or_coalesce_group(
120            buffer,
121            command,
122            CoalesceKind::Discrete,
123            &selections_before,
124            timestamp_ms,
125            ids,
126        );
127        let delta = delta_with_points_for_op(buffer, op);
128        let removed_text = buffer.capture_removed_text(op)?;
129        let op_revision_before = buffer.revision();
130        let revision_after = buffer.apply(op)?;
131        let selections_after = buffer.selections().to_vec();
132        let inverse_op = compute_inverse_op(op, &removed_text, buffer.rope())?;
133        buffer.undo_tree_mut().append_record(
134            group_id,
135            EditRecord {
136                op: op.clone(),
137                inverse_op,
138                revision_before: op_revision_before,
139                revision_after,
140                selections_before: selections_before.clone(),
141                selections_after: selections_after.clone(),
142            },
143        );
144        let checksum_after = current_checksum(buffer);
145        self.coalesce.remove(&buffer_id);
146        Ok(ChangeBatch {
147            buffer_id,
148            kind: MutationKind::RawEdit,
149            timestamp_ms,
150            command: command.to_string(),
151            revision_before,
152            revision_after,
153            undo_group_id: group_id,
154            new_undo_group,
155            selections_before: selections_before.clone(),
156            selections_after: selections_after.clone(),
157            changes: vec![AppliedChange {
158                op: op.clone(),
159                removed_text,
160                revision_before: op_revision_before,
161                revision_after,
162                selections_before,
163                selections_after,
164                checksum_after,
165            }],
166            checksum_after,
167            deltas: vec![delta],
168        })
169    }
170
171    pub(crate) fn undo(
172        &mut self,
173        buffer: &mut Buffer,
174        timestamp_ms: i64,
175    ) -> Result<Option<ChangeBatch>, Error> {
176        let Some(group) = buffer.undo_tree().group_to_undo().cloned() else {
177            return Ok(None);
178        };
179        if group.ops.is_empty() {
180            return Ok(None);
181        }
182        let target_selections = group.ops[0].selections_before.clone();
183        let ops: Vec<EditOp> = group
184            .ops
185            .iter()
186            .rev()
187            .map(|record| record.inverse_op.clone())
188            .collect();
189        let batch = apply_replay_ops(
190            buffer,
191            &ops,
192            group.id,
193            &group.command,
194            target_selections.clone(),
195            timestamp_ms,
196            MutationKind::Undo,
197        )?;
198        buffer.set_selections(target_selections);
199        buffer.undo_tree_mut().set_current(group.parent);
200        self.coalesce.remove(&buffer.id());
201        Ok(Some(batch))
202    }
203
204    pub(crate) fn redo(
205        &mut self,
206        buffer: &mut Buffer,
207        timestamp_ms: i64,
208        alternate: bool,
209    ) -> Result<Option<ChangeBatch>, Error> {
210        let target = if alternate {
211            buffer.undo_tree().group_to_redo_alternate().cloned()
212        } else {
213            buffer.undo_tree().group_to_redo().cloned()
214        };
215        let Some(group) = target else {
216            return Ok(None);
217        };
218        if group.ops.is_empty() {
219            return Ok(None);
220        }
221        let target_selections = group
222            .ops
223            .last()
224            .expect("invariant: non-empty undo group")
225            .selections_after
226            .clone();
227        let ops: Vec<EditOp> = group.ops.iter().map(|record| record.op.clone()).collect();
228        let batch = apply_replay_ops(
229            buffer,
230            &ops,
231            group.id,
232            &group.command,
233            target_selections.clone(),
234            timestamp_ms,
235            MutationKind::Redo,
236        )?;
237        buffer.set_selections(target_selections);
238        buffer.undo_tree_mut().set_current(Some(group.id));
239        self.coalesce.remove(&buffer.id());
240        Ok(Some(batch))
241    }
242
243    #[allow(clippy::too_many_arguments)]
244    fn mint_or_coalesce_group(
245        &self,
246        buffer: &mut Buffer,
247        command: &str,
248        kind: CoalesceKind,
249        selections_before: &[Selection],
250        timestamp_ms: i64,
251        ids: &mut dyn IdGenerator,
252    ) -> (UndoGroupId, Option<UndoGroupMeta>) {
253        if matches!(kind, CoalesceKind::Typing) {
254            if let Some(state) = self.coalesce.get(&buffer.id()) {
255                let is_same_command = state.command == command;
256                let is_in_window =
257                    timestamp_ms.saturating_sub(state.last_timestamp_ms) <= COALESCE_WINDOW_MS;
258                let has_no_jump = state.selections_after.as_slice() == selections_before;
259                if is_same_command && is_in_window && has_no_jump {
260                    return (state.group_id, None);
261                }
262            }
263        }
264        let parent = buffer.undo_tree().current_id();
265        let group_id = ids.next_undo_group_id();
266        buffer
267            .undo_tree_mut()
268            .insert_group(group_id, parent, timestamp_ms, command);
269        (
270            group_id,
271            Some(UndoGroupMeta {
272                id: group_id,
273                parent,
274                timestamp_ms,
275                command: command.to_string(),
276            }),
277        )
278    }
279}
280
281fn apply_recorded_op(
282    buffer: &mut Buffer,
283    op: &EditOp,
284    selections_before: &[Selection],
285    selections_after: &[Selection],
286    group_id: UndoGroupId,
287) -> Result<AppliedChange, Error> {
288    let removed_text = buffer.capture_removed_text(op)?;
289    let revision_before = buffer.revision();
290    let revision_after = buffer.apply(op)?;
291    let inverse_op = compute_inverse_op(op, &removed_text, buffer.rope())?;
292    buffer.undo_tree_mut().append_record(
293        group_id,
294        EditRecord {
295            op: op.clone(),
296            inverse_op,
297            revision_before,
298            revision_after,
299            selections_before: selections_before.to_vec(),
300            selections_after: selections_after.to_vec(),
301        },
302    );
303    Ok(AppliedChange {
304        op: op.clone(),
305        removed_text,
306        revision_before,
307        revision_after,
308        selections_before: selections_before.to_vec(),
309        selections_after: selections_after.to_vec(),
310        checksum_after: current_checksum(buffer),
311    })
312}
313
314fn apply_replay_ops(
315    buffer: &mut Buffer,
316    ops: &[EditOp],
317    group_id: UndoGroupId,
318    command: &str,
319    selections_after: Vec<Selection>,
320    timestamp_ms: i64,
321    kind: MutationKind,
322) -> Result<ChangeBatch, Error> {
323    let buffer_id = buffer.id();
324    let revision_before = buffer.revision();
325    let selections_before = buffer.selections().to_vec();
326    let mut changes = Vec::with_capacity(ops.len());
327    let mut deltas = Vec::with_capacity(ops.len());
328    for op in ops {
329        deltas.push(delta_with_points_for_op(buffer, op));
330        let removed_text = buffer.capture_removed_text(op)?;
331        let op_revision_before = buffer.revision();
332        let revision_after = buffer.apply(op)?;
333        changes.push(AppliedChange {
334            op: op.clone(),
335            removed_text,
336            revision_before: op_revision_before,
337            revision_after,
338            selections_before: Vec::new(),
339            selections_after: Vec::new(),
340            checksum_after: current_checksum(buffer),
341        });
342    }
343    Ok(ChangeBatch {
344        buffer_id,
345        kind,
346        timestamp_ms,
347        command: command.to_string(),
348        revision_before,
349        revision_after: buffer.revision(),
350        undo_group_id: group_id,
351        new_undo_group: None,
352        selections_before,
353        selections_after,
354        changes,
355        checksum_after: buffer.running_checksum(),
356        deltas,
357    })
358}
359
360fn delta_with_points_for_op(buffer: &Buffer, op: &EditOp) -> RopeEditDeltaWithPoints {
361    use continuity_text::RopeEditDelta;
362
363    let rope = buffer.rope();
364    match op {
365        EditOp::Insert { at, text } => {
366            let byte = at.to_byte_offset(rope).unwrap_or(0);
367            RopeEditDeltaWithPoints::capture(RopeEditDelta::insert(byte, text.len()), rope, text)
368        }
369        EditOp::Delete { range } => {
370            let start = range.start.to_byte_offset(rope).unwrap_or(0);
371            let end = range.end.to_byte_offset(rope).unwrap_or(start);
372            RopeEditDeltaWithPoints::capture(
373                RopeEditDelta::delete(start, end.saturating_sub(start)),
374                rope,
375                "",
376            )
377        }
378        EditOp::Replace { range, text } => {
379            let start = range.start.to_byte_offset(rope).unwrap_or(0);
380            let end = range.end.to_byte_offset(rope).unwrap_or(start);
381            RopeEditDeltaWithPoints::capture(
382                RopeEditDelta::replace(start, end.saturating_sub(start), text.len()),
383                rope,
384                text,
385            )
386        }
387    }
388}
389
390fn current_checksum(buffer: &mut Buffer) -> u64 {
391    if buffer.edits_since_verify() >= continuity_buffer::CHECKSUM_VERIFY_INTERVAL {
392        buffer.verify_running_checksum().1
393    } else {
394        buffer.running_checksum()
395    }
396}