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