1use gpui::{App, Context, Entity};
2use language::{self, Buffer, TransactionId};
3use std::{
4 collections::HashMap,
5 ops::{AddAssign, Range, Sub},
6 time::{Duration, Instant},
7};
8use sum_tree::Bias;
9use text::BufferId;
10
11use crate::{BufferState, MultiBufferDimension};
12
13use super::{Event, ExcerptSummary, 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<D>(
318 &self,
319 transaction_id: TransactionId,
320 cx: &App,
321 ) -> Vec<Range<D>>
322 where
323 D: MultiBufferDimension
324 + Ord
325 + Sub<D, Output = D::TextDimension>
326 + AddAssign<D::TextDimension>,
327 D::TextDimension: PartialOrd + Sub<D::TextDimension, Output = D::TextDimension>,
328 {
329 let Some(transaction) = self.history.transaction(transaction_id) else {
330 return Vec::new();
331 };
332
333 let mut ranges = Vec::new();
334 let snapshot = self.read(cx);
335 let mut cursor = snapshot.excerpts.cursor::<ExcerptSummary>(());
336
337 for (buffer_id, buffer_transaction) in &transaction.buffer_transactions {
338 let Some(buffer_state) = self.buffers.get(buffer_id) else {
339 continue;
340 };
341
342 let buffer = buffer_state.buffer.read(cx);
343 for range in
344 buffer.edited_ranges_for_transaction_id::<D::TextDimension>(*buffer_transaction)
345 {
346 for excerpt_id in &buffer_state.excerpts {
347 cursor.seek(excerpt_id, Bias::Left);
348 if let Some(excerpt) = cursor.item()
349 && excerpt.locator == *excerpt_id
350 {
351 let excerpt_buffer_start = excerpt
352 .range
353 .context
354 .start
355 .summary::<D::TextDimension>(buffer);
356 let excerpt_buffer_end = excerpt
357 .range
358 .context
359 .end
360 .summary::<D::TextDimension>(buffer);
361 let excerpt_range = excerpt_buffer_start..excerpt_buffer_end;
362 if excerpt_range.contains(&range.start)
363 && excerpt_range.contains(&range.end)
364 {
365 let excerpt_start = D::from_summary(&cursor.start().text);
366
367 let mut start = excerpt_start;
368 start += range.start - excerpt_buffer_start;
369 let mut end = excerpt_start;
370 end += range.end - excerpt_buffer_start;
371
372 ranges.push(start..end);
373 break;
374 }
375 }
376 }
377 }
378 }
379
380 ranges.sort_by_key(|range| range.start);
381 ranges
382 }
383
384 pub fn merge_transactions(
385 &mut self,
386 transaction: TransactionId,
387 destination: TransactionId,
388 cx: &mut Context<Self>,
389 ) {
390 if let Some(buffer) = self.as_singleton() {
391 buffer.update(cx, |buffer, _| {
392 buffer.merge_transactions(transaction, destination)
393 });
394 } else if let Some(transaction) = self.history.forget(transaction)
395 && let Some(destination) = self.history.transaction_mut(destination)
396 {
397 for (buffer_id, buffer_transaction_id) in transaction.buffer_transactions {
398 if let Some(destination_buffer_transaction_id) =
399 destination.buffer_transactions.get(&buffer_id)
400 {
401 if let Some(state) = self.buffers.get(&buffer_id) {
402 state.buffer.update(cx, |buffer, _| {
403 buffer.merge_transactions(
404 buffer_transaction_id,
405 *destination_buffer_transaction_id,
406 )
407 });
408 }
409 } else {
410 destination
411 .buffer_transactions
412 .insert(buffer_id, buffer_transaction_id);
413 }
414 }
415 }
416 }
417
418 pub fn finalize_last_transaction(&mut self, cx: &mut Context<Self>) {
419 self.history.finalize_last_transaction();
420 for BufferState { buffer, .. } in self.buffers.values() {
421 buffer.update(cx, |buffer, _| {
422 buffer.finalize_last_transaction();
423 });
424 }
425 }
426
427 pub fn push_transaction<'a, T>(&mut self, buffer_transactions: T, cx: &Context<Self>)
428 where
429 T: IntoIterator<Item = (&'a Entity<Buffer>, &'a language::Transaction)>,
430 {
431 self.history
432 .push_transaction(buffer_transactions, Instant::now(), cx);
433 self.history.finalize_last_transaction();
434 }
435
436 pub fn group_until_transaction(
437 &mut self,
438 transaction_id: TransactionId,
439 cx: &mut Context<Self>,
440 ) {
441 if let Some(buffer) = self.as_singleton() {
442 buffer.update(cx, |buffer, _| {
443 buffer.group_until_transaction(transaction_id)
444 });
445 } else {
446 self.history.group_until(transaction_id);
447 }
448 }
449 pub fn undo(&mut self, cx: &mut Context<Self>) -> Option<TransactionId> {
450 let mut transaction_id = None;
451 if let Some(buffer) = self.as_singleton() {
452 transaction_id = buffer.update(cx, |buffer, cx| buffer.undo(cx));
453 } else {
454 while let Some(transaction) = self.history.pop_undo() {
455 let mut undone = false;
456 for (buffer_id, buffer_transaction_id) in &mut transaction.buffer_transactions {
457 if let Some(BufferState { buffer, .. }) = self.buffers.get(buffer_id) {
458 undone |= buffer.update(cx, |buffer, cx| {
459 let undo_to = *buffer_transaction_id;
460 if let Some(entry) = buffer.peek_undo_stack() {
461 *buffer_transaction_id = entry.transaction_id();
462 }
463 buffer.undo_to_transaction(undo_to, cx)
464 });
465 }
466 }
467
468 if undone {
469 transaction_id = Some(transaction.id);
470 break;
471 }
472 }
473 }
474
475 if let Some(transaction_id) = transaction_id {
476 cx.emit(Event::TransactionUndone { transaction_id });
477 }
478
479 transaction_id
480 }
481
482 pub fn redo(&mut self, cx: &mut Context<Self>) -> Option<TransactionId> {
483 if let Some(buffer) = self.as_singleton() {
484 return buffer.update(cx, |buffer, cx| buffer.redo(cx));
485 }
486
487 while let Some(transaction) = self.history.pop_redo() {
488 let mut redone = false;
489 for (buffer_id, buffer_transaction_id) in transaction.buffer_transactions.iter_mut() {
490 if let Some(BufferState { buffer, .. }) = self.buffers.get(buffer_id) {
491 redone |= buffer.update(cx, |buffer, cx| {
492 let redo_to = *buffer_transaction_id;
493 if let Some(entry) = buffer.peek_redo_stack() {
494 *buffer_transaction_id = entry.transaction_id();
495 }
496 buffer.redo_to_transaction(redo_to, cx)
497 });
498 }
499 }
500
501 if redone {
502 return Some(transaction.id);
503 }
504 }
505
506 None
507 }
508
509 pub fn undo_transaction(&mut self, transaction_id: TransactionId, cx: &mut Context<Self>) {
510 if let Some(buffer) = self.as_singleton() {
511 buffer.update(cx, |buffer, cx| buffer.undo_transaction(transaction_id, cx));
512 } else if let Some(transaction) = self.history.remove_from_undo(transaction_id) {
513 for (buffer_id, transaction_id) in &transaction.buffer_transactions {
514 if let Some(BufferState { buffer, .. }) = self.buffers.get(buffer_id) {
515 buffer.update(cx, |buffer, cx| {
516 buffer.undo_transaction(*transaction_id, cx)
517 });
518 }
519 }
520 }
521 }
522
523 pub fn forget_transaction(&mut self, transaction_id: TransactionId, cx: &mut Context<Self>) {
524 if let Some(buffer) = self.as_singleton() {
525 buffer.update(cx, |buffer, _| {
526 buffer.forget_transaction(transaction_id);
527 });
528 } else if let Some(transaction) = self.history.forget(transaction_id) {
529 for (buffer_id, buffer_transaction_id) in transaction.buffer_transactions {
530 if let Some(state) = self.buffers.get_mut(&buffer_id) {
531 state.buffer.update(cx, |buffer, _| {
532 buffer.forget_transaction(buffer_transaction_id);
533 });
534 }
535 }
536 }
537 }
538}