1use gpui::{App, Context, Entity};
2use language::{self, Buffer, TransactionId};
3use std::{
4 collections::HashMap,
5 ops::Range,
6 time::{Duration, Instant},
7};
8use sum_tree::Bias;
9use text::BufferId;
10
11use crate::{Anchor, BufferState, MultiBufferOffset};
12
13use super::{Event, MultiBuffer};
14
15#[derive(Clone)]
16pub(super) struct History {
17 next_transaction_id: TransactionId,
18 undo_stack: Vec<Transaction>,
19 redo_stack: Vec<Transaction>,
20 transaction_depth: usize,
21 group_interval: Duration,
22}
23
24impl Default for History {
25 fn default() -> Self {
26 History {
27 next_transaction_id: clock::Lamport::MIN,
28 undo_stack: Vec::new(),
29 redo_stack: Vec::new(),
30 transaction_depth: 0,
31 group_interval: Duration::from_millis(300),
32 }
33 }
34}
35
36#[derive(Clone)]
37struct Transaction {
38 id: TransactionId,
39 buffer_transactions: HashMap<BufferId, text::TransactionId>,
40 first_edit_at: Instant,
41 last_edit_at: Instant,
42 suppress_grouping: bool,
43}
44
45impl History {
46 fn start_transaction(&mut self, now: Instant) -> Option<TransactionId> {
47 self.transaction_depth += 1;
48 if self.transaction_depth == 1 {
49 let id = self.next_transaction_id.tick();
50 self.undo_stack.push(Transaction {
51 id,
52 buffer_transactions: Default::default(),
53 first_edit_at: now,
54 last_edit_at: now,
55 suppress_grouping: false,
56 });
57 Some(id)
58 } else {
59 None
60 }
61 }
62
63 fn end_transaction(
64 &mut self,
65 now: Instant,
66 buffer_transactions: HashMap<BufferId, text::TransactionId>,
67 ) -> bool {
68 assert_ne!(self.transaction_depth, 0);
69 self.transaction_depth -= 1;
70 if self.transaction_depth == 0 {
71 if buffer_transactions.is_empty() {
72 self.undo_stack.pop();
73 false
74 } else {
75 self.redo_stack.clear();
76 let transaction = self.undo_stack.last_mut().unwrap();
77 transaction.last_edit_at = now;
78 for (buffer_id, transaction_id) in buffer_transactions {
79 transaction
80 .buffer_transactions
81 .entry(buffer_id)
82 .or_insert(transaction_id);
83 }
84 true
85 }
86 } else {
87 false
88 }
89 }
90
91 fn push_transaction<'a, T>(
92 &mut self,
93 buffer_transactions: T,
94 now: Instant,
95 cx: &Context<MultiBuffer>,
96 ) where
97 T: IntoIterator<Item = (&'a Entity<Buffer>, &'a language::Transaction)>,
98 {
99 assert_eq!(self.transaction_depth, 0);
100 let transaction = Transaction {
101 id: self.next_transaction_id.tick(),
102 buffer_transactions: buffer_transactions
103 .into_iter()
104 .map(|(buffer, transaction)| (buffer.read(cx).remote_id(), transaction.id))
105 .collect(),
106 first_edit_at: now,
107 last_edit_at: now,
108 suppress_grouping: false,
109 };
110 if !transaction.buffer_transactions.is_empty() {
111 self.undo_stack.push(transaction);
112 self.redo_stack.clear();
113 }
114 }
115
116 fn finalize_last_transaction(&mut self) {
117 if let Some(transaction) = self.undo_stack.last_mut() {
118 transaction.suppress_grouping = true;
119 }
120 }
121
122 fn forget(&mut self, transaction_id: TransactionId) -> Option<Transaction> {
123 if let Some(ix) = self
124 .undo_stack
125 .iter()
126 .rposition(|transaction| transaction.id == transaction_id)
127 {
128 Some(self.undo_stack.remove(ix))
129 } else if let Some(ix) = self
130 .redo_stack
131 .iter()
132 .rposition(|transaction| transaction.id == transaction_id)
133 {
134 Some(self.redo_stack.remove(ix))
135 } else {
136 None
137 }
138 }
139
140 fn transaction(&self, transaction_id: TransactionId) -> Option<&Transaction> {
141 self.undo_stack
142 .iter()
143 .find(|transaction| transaction.id == transaction_id)
144 .or_else(|| {
145 self.redo_stack
146 .iter()
147 .find(|transaction| transaction.id == transaction_id)
148 })
149 }
150
151 fn transaction_mut(&mut self, transaction_id: TransactionId) -> Option<&mut Transaction> {
152 self.undo_stack
153 .iter_mut()
154 .find(|transaction| transaction.id == transaction_id)
155 .or_else(|| {
156 self.redo_stack
157 .iter_mut()
158 .find(|transaction| transaction.id == transaction_id)
159 })
160 }
161
162 fn pop_undo(&mut self) -> Option<&mut Transaction> {
163 assert_eq!(self.transaction_depth, 0);
164 if let Some(transaction) = self.undo_stack.pop() {
165 self.redo_stack.push(transaction);
166 self.redo_stack.last_mut()
167 } else {
168 None
169 }
170 }
171
172 fn pop_redo(&mut self) -> Option<&mut Transaction> {
173 assert_eq!(self.transaction_depth, 0);
174 if let Some(transaction) = self.redo_stack.pop() {
175 self.undo_stack.push(transaction);
176 self.undo_stack.last_mut()
177 } else {
178 None
179 }
180 }
181
182 fn remove_from_undo(&mut self, transaction_id: TransactionId) -> Option<&Transaction> {
183 let ix = self
184 .undo_stack
185 .iter()
186 .rposition(|transaction| transaction.id == transaction_id)?;
187 let transaction = self.undo_stack.remove(ix);
188 self.redo_stack.push(transaction);
189 self.redo_stack.last()
190 }
191
192 fn group(&mut self) -> Option<TransactionId> {
193 let mut count = 0;
194 let mut transactions = self.undo_stack.iter();
195 if let Some(mut transaction) = transactions.next_back() {
196 while let Some(prev_transaction) = transactions.next_back() {
197 if !prev_transaction.suppress_grouping
198 && transaction.first_edit_at - prev_transaction.last_edit_at
199 <= self.group_interval
200 {
201 transaction = prev_transaction;
202 count += 1;
203 } else {
204 break;
205 }
206 }
207 }
208 self.group_trailing(count)
209 }
210
211 fn group_until(&mut self, transaction_id: TransactionId) {
212 let mut count = 0;
213 for transaction in self.undo_stack.iter().rev() {
214 if transaction.id == transaction_id {
215 self.group_trailing(count);
216 break;
217 } else if transaction.suppress_grouping {
218 break;
219 } else {
220 count += 1;
221 }
222 }
223 }
224
225 fn group_trailing(&mut self, n: usize) -> Option<TransactionId> {
226 let new_len = self.undo_stack.len() - n;
227 let (transactions_to_keep, transactions_to_merge) = self.undo_stack.split_at_mut(new_len);
228 if let Some(last_transaction) = transactions_to_keep.last_mut() {
229 if let Some(transaction) = transactions_to_merge.last() {
230 last_transaction.last_edit_at = transaction.last_edit_at;
231 }
232 for to_merge in transactions_to_merge {
233 for (buffer_id, transaction_id) in &to_merge.buffer_transactions {
234 last_transaction
235 .buffer_transactions
236 .entry(*buffer_id)
237 .or_insert(*transaction_id);
238 }
239 }
240 }
241
242 self.undo_stack.truncate(new_len);
243 self.undo_stack.last().map(|t| t.id)
244 }
245
246 pub(super) fn transaction_depth(&self) -> usize {
247 self.transaction_depth
248 }
249
250 pub fn set_group_interval(&mut self, group_interval: Duration) {
251 self.group_interval = group_interval;
252 }
253}
254
255impl MultiBuffer {
256 pub fn start_transaction(&mut self, cx: &mut Context<Self>) -> Option<TransactionId> {
257 self.start_transaction_at(Instant::now(), cx)
258 }
259
260 pub fn start_transaction_at(
261 &mut self,
262 now: Instant,
263 cx: &mut Context<Self>,
264 ) -> Option<TransactionId> {
265 if let Some(buffer) = self.as_singleton() {
266 return buffer.update(cx, |buffer, _| buffer.start_transaction_at(now));
267 }
268
269 for BufferState { buffer, .. } in self.buffers.values() {
270 buffer.update(cx, |buffer, _| buffer.start_transaction_at(now));
271 }
272 self.history.start_transaction(now)
273 }
274
275 pub fn last_transaction_id(&self, cx: &App) -> Option<TransactionId> {
276 if let Some(buffer) = self.as_singleton() {
277 buffer
278 .read(cx)
279 .peek_undo_stack()
280 .map(|history_entry| history_entry.transaction_id())
281 } else {
282 let last_transaction = self.history.undo_stack.last()?;
283 Some(last_transaction.id)
284 }
285 }
286
287 pub fn end_transaction(&mut self, cx: &mut Context<Self>) -> Option<TransactionId> {
288 self.end_transaction_at(Instant::now(), cx)
289 }
290
291 pub fn end_transaction_at(
292 &mut self,
293 now: Instant,
294 cx: &mut Context<Self>,
295 ) -> Option<TransactionId> {
296 if let Some(buffer) = self.as_singleton() {
297 return buffer.update(cx, |buffer, cx| buffer.end_transaction_at(now, cx));
298 }
299
300 let mut buffer_transactions = HashMap::default();
301 for BufferState { buffer, .. } in self.buffers.values() {
302 if let Some(transaction_id) =
303 buffer.update(cx, |buffer, cx| buffer.end_transaction_at(now, cx))
304 {
305 buffer_transactions.insert(buffer.read(cx).remote_id(), transaction_id);
306 }
307 }
308
309 if self.history.end_transaction(now, buffer_transactions) {
310 let transaction_id = self.history.group().unwrap();
311 Some(transaction_id)
312 } else {
313 None
314 }
315 }
316
317 pub fn edited_ranges_for_transaction(
318 &self,
319 transaction_id: TransactionId,
320 cx: &App,
321 ) -> Vec<Range<MultiBufferOffset>> {
322 let Some(transaction) = self.history.transaction(transaction_id) else {
323 return Vec::new();
324 };
325
326 let snapshot = self.read(cx);
327 let mut buffer_anchors = Vec::new();
328
329 for (buffer_id, buffer_transaction) in &transaction.buffer_transactions {
330 let Some(buffer) = self.buffer(*buffer_id) else {
331 continue;
332 };
333 let Some(excerpt) = snapshot.first_excerpt_for_buffer(*buffer_id) else {
334 continue;
335 };
336 let buffer_snapshot = buffer.read(cx).snapshot();
337
338 for range in buffer
339 .read(cx)
340 .edited_ranges_for_transaction_id::<usize>(*buffer_transaction)
341 {
342 buffer_anchors.push(Anchor::in_buffer(
343 excerpt.path_key_index,
344 buffer_snapshot.anchor_at(range.start, Bias::Left),
345 ));
346 buffer_anchors.push(Anchor::in_buffer(
347 excerpt.path_key_index,
348 buffer_snapshot.anchor_at(range.end, Bias::Right),
349 ));
350 }
351 }
352 buffer_anchors.sort_unstable_by(|a, b| a.cmp(b, &snapshot));
353
354 snapshot
355 .summaries_for_anchors(buffer_anchors.iter())
356 .as_chunks::<2>()
357 .0
358 .iter()
359 .map(|&[s, e]| s..e)
360 .collect::<Vec<_>>()
361 }
362
363 pub fn merge_transactions(
364 &mut self,
365 transaction: TransactionId,
366 destination: TransactionId,
367 cx: &mut Context<Self>,
368 ) {
369 if let Some(buffer) = self.as_singleton() {
370 buffer.update(cx, |buffer, _| {
371 buffer.merge_transactions(transaction, destination)
372 });
373 } else if let Some(transaction) = self.history.forget(transaction)
374 && let Some(destination) = self.history.transaction_mut(destination)
375 {
376 for (buffer_id, buffer_transaction_id) in transaction.buffer_transactions {
377 if let Some(destination_buffer_transaction_id) =
378 destination.buffer_transactions.get(&buffer_id)
379 {
380 if let Some(state) = self.buffers.get(&buffer_id) {
381 state.buffer.update(cx, |buffer, _| {
382 buffer.merge_transactions(
383 buffer_transaction_id,
384 *destination_buffer_transaction_id,
385 )
386 });
387 }
388 } else {
389 destination
390 .buffer_transactions
391 .insert(buffer_id, buffer_transaction_id);
392 }
393 }
394 }
395 }
396
397 pub fn finalize_last_transaction(&mut self, cx: &mut Context<Self>) {
398 self.history.finalize_last_transaction();
399 for BufferState { buffer, .. } in self.buffers.values() {
400 buffer.update(cx, |buffer, _| {
401 buffer.finalize_last_transaction();
402 });
403 }
404 }
405
406 pub fn push_transaction<'a, T>(&mut self, buffer_transactions: T, cx: &Context<Self>)
407 where
408 T: IntoIterator<Item = (&'a Entity<Buffer>, &'a language::Transaction)>,
409 {
410 self.history
411 .push_transaction(buffer_transactions, Instant::now(), cx);
412 self.history.finalize_last_transaction();
413 }
414
415 pub fn group_until_transaction(
416 &mut self,
417 transaction_id: TransactionId,
418 cx: &mut Context<Self>,
419 ) {
420 if let Some(buffer) = self.as_singleton() {
421 buffer.update(cx, |buffer, _| {
422 buffer.group_until_transaction(transaction_id)
423 });
424 } else {
425 self.history.group_until(transaction_id);
426 }
427 }
428 pub fn undo(&mut self, cx: &mut Context<Self>) -> Option<TransactionId> {
429 let mut transaction_id = None;
430 if let Some(buffer) = self.as_singleton() {
431 transaction_id = buffer.update(cx, |buffer, cx| buffer.undo(cx));
432 } else {
433 while let Some(transaction) = self.history.pop_undo() {
434 let mut undone = false;
435 for (buffer_id, buffer_transaction_id) in &mut transaction.buffer_transactions {
436 if let Some(BufferState { buffer, .. }) = self.buffers.get(buffer_id) {
437 undone |= buffer.update(cx, |buffer, cx| {
438 let undo_to = *buffer_transaction_id;
439 if let Some(entry) = buffer.peek_undo_stack() {
440 *buffer_transaction_id = entry.transaction_id();
441 }
442 buffer.undo_to_transaction(undo_to, cx)
443 });
444 }
445 }
446
447 if undone {
448 transaction_id = Some(transaction.id);
449 break;
450 }
451 }
452 }
453
454 if let Some(transaction_id) = transaction_id {
455 cx.emit(Event::TransactionUndone { transaction_id });
456 }
457
458 transaction_id
459 }
460
461 pub fn redo(&mut self, cx: &mut Context<Self>) -> Option<TransactionId> {
462 if let Some(buffer) = self.as_singleton() {
463 return buffer.update(cx, |buffer, cx| buffer.redo(cx));
464 }
465
466 while let Some(transaction) = self.history.pop_redo() {
467 let mut redone = false;
468 for (buffer_id, buffer_transaction_id) in transaction.buffer_transactions.iter_mut() {
469 if let Some(BufferState { buffer, .. }) = self.buffers.get(buffer_id) {
470 redone |= buffer.update(cx, |buffer, cx| {
471 let redo_to = *buffer_transaction_id;
472 if let Some(entry) = buffer.peek_redo_stack() {
473 *buffer_transaction_id = entry.transaction_id();
474 }
475 buffer.redo_to_transaction(redo_to, cx)
476 });
477 }
478 }
479
480 if redone {
481 return Some(transaction.id);
482 }
483 }
484
485 None
486 }
487
488 pub fn undo_transaction(&mut self, transaction_id: TransactionId, cx: &mut Context<Self>) {
489 if let Some(buffer) = self.as_singleton() {
490 buffer.update(cx, |buffer, cx| buffer.undo_transaction(transaction_id, cx));
491 } else if let Some(transaction) = self.history.remove_from_undo(transaction_id) {
492 for (buffer_id, transaction_id) in &transaction.buffer_transactions {
493 if let Some(BufferState { buffer, .. }) = self.buffers.get(buffer_id) {
494 buffer.update(cx, |buffer, cx| {
495 buffer.undo_transaction(*transaction_id, cx)
496 });
497 }
498 }
499 }
500 }
501
502 pub fn forget_transaction(&mut self, transaction_id: TransactionId, cx: &mut Context<Self>) {
503 if let Some(buffer) = self.as_singleton() {
504 buffer.update(cx, |buffer, _| {
505 buffer.forget_transaction(transaction_id);
506 });
507 } else if let Some(transaction) = self.history.forget(transaction_id) {
508 for (buffer_id, buffer_transaction_id) in transaction.buffer_transactions {
509 if let Some(state) = self.buffers.get_mut(&buffer_id) {
510 state.buffer.update(cx, |buffer, _| {
511 buffer.forget_transaction(buffer_transaction_id);
512 });
513 }
514 }
515 }
516 }
517}