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