1mod anchor;
2mod point;
3mod selection;
4mod text;
5
6pub use anchor::*;
7pub use point::*;
8use seahash::SeaHasher;
9pub use selection::*;
10pub use text::*;
11
12use crate::{
13 operation_queue::{self, OperationQueue},
14 sum_tree::{self, Cursor, FilterCursor, SeekBias, SumTree},
15 time::{self, ReplicaId},
16 util::RandomCharIter,
17 worktree::FileHandle,
18};
19use anyhow::{anyhow, Result};
20use gpui::{Entity, ModelContext, Task};
21use lazy_static::lazy_static;
22use rand::prelude::*;
23use std::{
24 cmp,
25 hash::BuildHasher,
26 iter::{self, Iterator},
27 ops::{AddAssign, Range},
28 str,
29 sync::Arc,
30 time::{Duration, Instant},
31};
32
33const UNDO_GROUP_INTERVAL: Duration = Duration::from_millis(300);
34
35#[derive(Clone, Default)]
36struct DeterministicState;
37
38impl BuildHasher for DeterministicState {
39 type Hasher = SeaHasher;
40
41 fn build_hasher(&self) -> Self::Hasher {
42 SeaHasher::new()
43 }
44}
45
46#[cfg(test)]
47type HashMap<K, V> = std::collections::HashMap<K, V, DeterministicState>;
48
49#[cfg(test)]
50type HashSet<T> = std::collections::HashSet<T, DeterministicState>;
51
52#[cfg(not(test))]
53type HashMap<K, V> = std::collections::HashMap<K, V>;
54
55#[cfg(not(test))]
56type HashSet<T> = std::collections::HashSet<T>;
57
58pub struct Buffer {
59 fragments: SumTree<Fragment>,
60 insertion_splits: HashMap<time::Local, SumTree<InsertionSplit>>,
61 pub version: time::Global,
62 saved_version: time::Global,
63 last_edit: time::Local,
64 undo_map: UndoMap,
65 history: History,
66 file: Option<FileHandle>,
67 selections: HashMap<SelectionSetId, Arc<[Selection]>>,
68 pub selections_last_update: SelectionsVersion,
69 deferred_ops: OperationQueue<Operation>,
70 deferred_replicas: HashSet<ReplicaId>,
71 replica_id: ReplicaId,
72 local_clock: time::Local,
73 lamport_clock: time::Lamport,
74}
75
76pub struct Snapshot {
77 fragments: SumTree<Fragment>,
78}
79
80#[derive(Clone)]
81struct Transaction {
82 start: time::Global,
83 buffer_was_dirty: bool,
84 edits: Vec<time::Local>,
85 selections_before: Option<(SelectionSetId, Arc<[Selection]>)>,
86 selections_after: Option<(SelectionSetId, Arc<[Selection]>)>,
87 first_edit_at: Instant,
88 last_edit_at: Instant,
89}
90
91#[derive(Clone)]
92pub struct History {
93 pub base_text: Arc<str>,
94 ops: HashMap<time::Local, EditOperation>,
95 undo_stack: Vec<Transaction>,
96 redo_stack: Vec<Transaction>,
97 transaction_depth: usize,
98 group_interval: Duration,
99}
100
101impl History {
102 pub fn new(base_text: Arc<str>) -> Self {
103 Self {
104 base_text,
105 ops: Default::default(),
106 undo_stack: Vec::new(),
107 redo_stack: Vec::new(),
108 transaction_depth: 0,
109 group_interval: UNDO_GROUP_INTERVAL,
110 }
111 }
112
113 fn push(&mut self, op: EditOperation) {
114 self.ops.insert(op.id, op);
115 }
116
117 fn start_transaction(
118 &mut self,
119 start: time::Global,
120 buffer_was_dirty: bool,
121 selections: Option<(SelectionSetId, Arc<[Selection]>)>,
122 now: Instant,
123 ) {
124 self.transaction_depth += 1;
125 if self.transaction_depth == 1 {
126 self.undo_stack.push(Transaction {
127 start,
128 buffer_was_dirty,
129 edits: Vec::new(),
130 selections_before: selections,
131 selections_after: None,
132 first_edit_at: now,
133 last_edit_at: now,
134 });
135 }
136 }
137
138 fn end_transaction(
139 &mut self,
140 selections: Option<(SelectionSetId, Arc<[Selection]>)>,
141 now: Instant,
142 ) -> Option<&Transaction> {
143 assert_ne!(self.transaction_depth, 0);
144 self.transaction_depth -= 1;
145 if self.transaction_depth == 0 {
146 let transaction = self.undo_stack.last_mut().unwrap();
147 transaction.selections_after = selections;
148 transaction.last_edit_at = now;
149 Some(transaction)
150 } else {
151 None
152 }
153 }
154
155 fn group(&mut self) {
156 let mut new_len = self.undo_stack.len();
157 let mut transactions = self.undo_stack.iter_mut();
158
159 if let Some(mut transaction) = transactions.next_back() {
160 for prev_transaction in transactions.next_back() {
161 if transaction.first_edit_at - prev_transaction.last_edit_at <= self.group_interval
162 {
163 prev_transaction.edits.append(&mut transaction.edits);
164 prev_transaction.last_edit_at = transaction.last_edit_at;
165 prev_transaction.selections_after = transaction.selections_after.take();
166 transaction = prev_transaction;
167 new_len -= 1;
168 } else {
169 break;
170 }
171 }
172 }
173
174 self.undo_stack.truncate(new_len);
175 }
176
177 fn push_undo(&mut self, edit_id: time::Local) {
178 assert_ne!(self.transaction_depth, 0);
179 self.undo_stack.last_mut().unwrap().edits.push(edit_id);
180 }
181
182 fn pop_undo(&mut self) -> Option<&Transaction> {
183 assert_eq!(self.transaction_depth, 0);
184 if let Some(transaction) = self.undo_stack.pop() {
185 self.redo_stack.push(transaction);
186 self.redo_stack.last()
187 } else {
188 None
189 }
190 }
191
192 fn pop_redo(&mut self) -> Option<&Transaction> {
193 assert_eq!(self.transaction_depth, 0);
194 if let Some(transaction) = self.redo_stack.pop() {
195 self.undo_stack.push(transaction);
196 self.undo_stack.last()
197 } else {
198 None
199 }
200 }
201}
202
203#[derive(Clone, Default, Debug)]
204struct UndoMap(HashMap<time::Local, Vec<UndoOperation>>);
205
206impl UndoMap {
207 fn insert(&mut self, undo: UndoOperation) {
208 self.0.entry(undo.edit_id).or_default().push(undo);
209 }
210
211 fn is_undone(&self, edit_id: time::Local) -> bool {
212 self.undo_count(edit_id) % 2 == 1
213 }
214
215 fn was_undone(&self, edit_id: time::Local, version: &time::Global) -> bool {
216 let undo_count = self
217 .0
218 .get(&edit_id)
219 .unwrap_or(&Vec::new())
220 .iter()
221 .filter(|undo| version.observed(undo.id))
222 .map(|undo| undo.count)
223 .max()
224 .unwrap_or(0);
225 undo_count % 2 == 1
226 }
227
228 fn undo_count(&self, edit_id: time::Local) -> u32 {
229 self.0
230 .get(&edit_id)
231 .unwrap_or(&Vec::new())
232 .iter()
233 .map(|undo| undo.count)
234 .max()
235 .unwrap_or(0)
236 }
237}
238
239#[derive(Clone)]
240pub struct CharIter<'a> {
241 fragments_cursor: Cursor<'a, Fragment, usize, usize>,
242 fragment_chars: str::Chars<'a>,
243}
244
245#[derive(Clone)]
246pub struct FragmentIter<'a> {
247 cursor: Cursor<'a, Fragment, usize, usize>,
248 started: bool,
249}
250
251struct Edits<'a, F: Fn(&FragmentSummary) -> bool> {
252 cursor: FilterCursor<'a, F, Fragment, usize>,
253 undos: &'a UndoMap,
254 since: time::Global,
255 delta: isize,
256}
257
258#[derive(Clone, Debug, Eq, PartialEq)]
259pub struct Edit {
260 pub old_range: Range<usize>,
261 pub new_range: Range<usize>,
262}
263
264impl Edit {
265 pub fn delta(&self) -> isize {
266 (self.new_range.end - self.new_range.start) as isize
267 - (self.old_range.end - self.old_range.start) as isize
268 }
269
270 pub fn old_extent(&self) -> usize {
271 self.old_range.end - self.old_range.start
272 }
273}
274
275#[derive(Clone, Eq, PartialEq, Debug)]
276pub struct Insertion {
277 id: time::Local,
278 parent_id: time::Local,
279 offset_in_parent: usize,
280 text: Text,
281 lamport_timestamp: time::Lamport,
282}
283
284#[derive(Eq, PartialEq, Clone, Debug)]
285struct Fragment {
286 id: FragmentId,
287 insertion: Insertion,
288 text: Text,
289 deletions: HashSet<time::Local>,
290 max_undos: time::Global,
291 visible: bool,
292}
293
294#[derive(Eq, PartialEq, Clone, Debug)]
295pub struct FragmentSummary {
296 text_summary: TextSummary,
297 max_fragment_id: FragmentId,
298 max_version: time::Global,
299}
300
301#[derive(Eq, PartialEq, Clone, Debug, Ord, PartialOrd)]
302struct FragmentExtent {
303 chars: usize,
304 lines: Point,
305}
306
307#[derive(Eq, PartialEq, Clone, Debug)]
308struct InsertionSplit {
309 extent: usize,
310 fragment_id: FragmentId,
311}
312
313#[derive(Eq, PartialEq, Clone, Debug)]
314struct InsertionSplitSummary {
315 extent: usize,
316}
317
318#[derive(Clone, Debug, Eq, PartialEq)]
319pub enum Operation {
320 Edit {
321 edit: EditOperation,
322 lamport_timestamp: time::Lamport,
323 },
324 Undo {
325 undo: UndoOperation,
326 lamport_timestamp: time::Lamport,
327 },
328 UpdateSelections {
329 set_id: SelectionSetId,
330 selections: Option<Arc<[Selection]>>,
331 lamport_timestamp: time::Lamport,
332 },
333}
334
335#[derive(Clone, Debug, Eq, PartialEq)]
336pub struct EditOperation {
337 id: time::Local,
338 start_id: time::Local,
339 start_offset: usize,
340 end_id: time::Local,
341 end_offset: usize,
342 version_in_range: time::Global,
343 new_text: Option<Text>,
344}
345
346#[derive(Copy, Clone, Debug, Eq, PartialEq)]
347pub struct UndoOperation {
348 id: time::Local,
349 edit_id: time::Local,
350 count: u32,
351}
352
353impl Buffer {
354 pub fn new<T: Into<Arc<str>>>(
355 replica_id: ReplicaId,
356 base_text: T,
357 ctx: &mut ModelContext<Self>,
358 ) -> Self {
359 Self::build(replica_id, History::new(base_text.into()), None, ctx)
360 }
361
362 pub fn from_history(
363 replica_id: ReplicaId,
364 history: History,
365 file: Option<FileHandle>,
366 ctx: &mut ModelContext<Self>,
367 ) -> Self {
368 Self::build(replica_id, history, file, ctx)
369 }
370
371 fn build(
372 replica_id: ReplicaId,
373 history: History,
374 file: Option<FileHandle>,
375 ctx: &mut ModelContext<Self>,
376 ) -> Self {
377 if let Some(file) = file.as_ref() {
378 file.observe_from_model(ctx, |this, file, ctx| {
379 if this.version == this.saved_version && file.is_deleted() {
380 ctx.emit(Event::Dirtied);
381 }
382 ctx.emit(Event::FileHandleChanged);
383 });
384 }
385
386 let mut insertion_splits = HashMap::default();
387 let mut fragments = SumTree::new();
388
389 let base_insertion = Insertion {
390 id: time::Local::default(),
391 parent_id: time::Local::default(),
392 offset_in_parent: 0,
393 text: history.base_text.clone().into(),
394 lamport_timestamp: time::Lamport::default(),
395 };
396
397 insertion_splits.insert(
398 base_insertion.id,
399 SumTree::from_item(
400 InsertionSplit {
401 fragment_id: FragmentId::min_value().clone(),
402 extent: 0,
403 },
404 &(),
405 ),
406 );
407 fragments.push(
408 Fragment {
409 id: FragmentId::min_value().clone(),
410 insertion: base_insertion.clone(),
411 text: base_insertion.text.slice(0..0),
412 deletions: Default::default(),
413 max_undos: Default::default(),
414 visible: true,
415 },
416 &(),
417 );
418
419 if base_insertion.text.len() > 0 {
420 let base_fragment_id =
421 FragmentId::between(&FragmentId::min_value(), &FragmentId::max_value());
422
423 insertion_splits.get_mut(&base_insertion.id).unwrap().push(
424 InsertionSplit {
425 fragment_id: base_fragment_id.clone(),
426 extent: base_insertion.text.len(),
427 },
428 &(),
429 );
430 fragments.push(
431 Fragment {
432 id: base_fragment_id,
433 text: base_insertion.text.clone(),
434 insertion: base_insertion,
435 deletions: Default::default(),
436 max_undos: Default::default(),
437 visible: true,
438 },
439 &(),
440 );
441 }
442
443 Self {
444 fragments,
445 insertion_splits,
446 version: time::Global::new(),
447 saved_version: time::Global::new(),
448 last_edit: time::Local::default(),
449 undo_map: Default::default(),
450 history,
451 file,
452 selections: HashMap::default(),
453 selections_last_update: 0,
454 deferred_ops: OperationQueue::new(),
455 deferred_replicas: HashSet::default(),
456 replica_id,
457 local_clock: time::Local::new(replica_id),
458 lamport_clock: time::Lamport::new(replica_id),
459 }
460 }
461
462 pub fn snapshot(&self) -> Snapshot {
463 Snapshot {
464 fragments: self.fragments.clone(),
465 }
466 }
467
468 pub fn file(&self) -> Option<&FileHandle> {
469 self.file.as_ref()
470 }
471
472 pub fn save(
473 &mut self,
474 new_file: Option<FileHandle>,
475 ctx: &mut ModelContext<Self>,
476 ) -> Task<Result<()>> {
477 let snapshot = self.snapshot();
478 let version = self.version.clone();
479 let file = self.file.clone();
480 let handle = ctx.handle();
481
482 ctx.spawn(|mut ctx| async move {
483 if let Some(file) = new_file.as_ref().or(file.as_ref()) {
484 let result = ctx.read(|ctx| file.save(snapshot, ctx.as_ref())).await;
485 if result.is_ok() {
486 handle.update(&mut ctx, |me, ctx| me.did_save(version, new_file, ctx));
487 }
488 result
489 } else {
490 Ok(())
491 }
492 })
493 }
494
495 fn did_save(
496 &mut self,
497 version: time::Global,
498 file: Option<FileHandle>,
499 ctx: &mut ModelContext<Buffer>,
500 ) {
501 if file.is_some() {
502 self.file = file;
503 }
504 self.saved_version = version;
505 ctx.emit(Event::Saved);
506 }
507
508 pub fn is_dirty(&self) -> bool {
509 self.version > self.saved_version || self.file.as_ref().map_or(false, |f| f.is_deleted())
510 }
511
512 pub fn version(&self) -> time::Global {
513 self.version.clone()
514 }
515
516 pub fn text_summary(&self) -> TextSummary {
517 self.fragments.extent::<TextSummary>()
518 }
519
520 pub fn text_summary_for_range(&self, range: Range<usize>) -> TextSummary {
521 let mut summary = TextSummary::default();
522
523 let mut cursor = self.fragments.cursor::<usize, usize>();
524 cursor.seek(&range.start, SeekBias::Right, &());
525
526 if let Some(fragment) = cursor.item() {
527 let summary_start = cmp::max(*cursor.start(), range.start) - cursor.start();
528 let summary_end = cmp::min(range.end - cursor.start(), fragment.len());
529 summary += fragment.text.slice(summary_start..summary_end).summary();
530 cursor.next();
531 }
532
533 if range.end > *cursor.start() {
534 summary += cursor.summary::<TextSummary>(&range.end, SeekBias::Right, &());
535
536 if let Some(fragment) = cursor.item() {
537 let summary_start = cmp::max(*cursor.start(), range.start) - cursor.start();
538 let summary_end = cmp::min(range.end - cursor.start(), fragment.len());
539 summary += fragment.text.slice(summary_start..summary_end).summary();
540 }
541 }
542
543 summary
544 }
545
546 pub fn len(&self) -> usize {
547 self.fragments.extent::<usize>()
548 }
549
550 pub fn line_len(&self, row: u32) -> Result<u32> {
551 let row_start_offset = Point::new(row, 0).to_offset(self)?;
552 let row_end_offset = if row >= self.max_point().row {
553 self.len()
554 } else {
555 Point::new(row + 1, 0).to_offset(self)? - 1
556 };
557
558 Ok((row_end_offset - row_start_offset) as u32)
559 }
560
561 pub fn rightmost_point(&self) -> Point {
562 self.fragments.summary().text_summary.rightmost_point
563 }
564
565 pub fn rightmost_point_in_range(&self, range: Range<usize>) -> Point {
566 let mut summary = TextSummary::default();
567
568 let mut cursor = self.fragments.cursor::<usize, usize>();
569 cursor.seek(&range.start, SeekBias::Right, &());
570
571 if let Some(fragment) = cursor.item() {
572 let summary_start = cmp::max(*cursor.start(), range.start) - cursor.start();
573 let summary_end = cmp::min(range.end - cursor.start(), fragment.len());
574 summary += fragment.text.slice(summary_start..summary_end).summary();
575 cursor.next();
576 }
577
578 if range.end > *cursor.start() {
579 summary += cursor.summary::<TextSummary>(&range.end, SeekBias::Right, &());
580
581 if let Some(fragment) = cursor.item() {
582 let summary_start = cmp::max(*cursor.start(), range.start) - cursor.start();
583 let summary_end = cmp::min(range.end - cursor.start(), fragment.len());
584 summary += fragment.text.slice(summary_start..summary_end).summary();
585 }
586 }
587
588 summary.rightmost_point
589 }
590
591 pub fn max_point(&self) -> Point {
592 self.fragments.extent()
593 }
594
595 pub fn line(&self, row: u32) -> Result<String> {
596 Ok(self
597 .chars_at(Point::new(row, 0))?
598 .take_while(|c| *c != '\n')
599 .collect())
600 }
601
602 pub fn text(&self) -> String {
603 self.chars().collect()
604 }
605
606 pub fn text_for_range<'a, T: ToOffset>(
607 &'a self,
608 range: Range<T>,
609 ) -> Result<impl 'a + Iterator<Item = char>> {
610 let start = range.start.to_offset(self)?;
611 let end = range.end.to_offset(self)?;
612 Ok(self.chars_at(start)?.take(end - start))
613 }
614
615 pub fn chars(&self) -> CharIter {
616 self.chars_at(0).unwrap()
617 }
618
619 pub fn chars_at<T: ToOffset>(&self, position: T) -> Result<CharIter> {
620 let offset = position.to_offset(self)?;
621 Ok(CharIter::new(&self.fragments, offset))
622 }
623
624 pub fn selections_changed_since(&self, since: SelectionsVersion) -> bool {
625 self.selections_last_update != since
626 }
627
628 pub fn edits_since<'a>(&'a self, since: time::Global) -> impl 'a + Iterator<Item = Edit> {
629 let since_2 = since.clone();
630 let cursor = self
631 .fragments
632 .filter(move |summary| summary.max_version.changed_since(&since_2));
633
634 Edits {
635 cursor,
636 undos: &self.undo_map,
637 since,
638 delta: 0,
639 }
640 }
641
642 pub fn deferred_ops_len(&self) -> usize {
643 self.deferred_ops.len()
644 }
645
646 pub fn start_transaction(&mut self, set_id: Option<SelectionSetId>) -> Result<()> {
647 self.start_transaction_at(set_id, Instant::now())
648 }
649
650 fn start_transaction_at(&mut self, set_id: Option<SelectionSetId>, now: Instant) -> Result<()> {
651 let selections = if let Some(set_id) = set_id {
652 let selections = self
653 .selections
654 .get(&set_id)
655 .ok_or_else(|| anyhow!("invalid selection set {:?}", set_id))?;
656 Some((set_id, selections.clone()))
657 } else {
658 None
659 };
660 self.history
661 .start_transaction(self.version.clone(), self.is_dirty(), selections, now);
662 Ok(())
663 }
664
665 pub fn end_transaction(
666 &mut self,
667 set_id: Option<SelectionSetId>,
668 ctx: Option<&mut ModelContext<Self>>,
669 ) -> Result<()> {
670 self.end_transaction_at(set_id, Instant::now(), ctx)
671 }
672
673 fn end_transaction_at(
674 &mut self,
675 set_id: Option<SelectionSetId>,
676 now: Instant,
677 ctx: Option<&mut ModelContext<Self>>,
678 ) -> Result<()> {
679 let selections = if let Some(set_id) = set_id {
680 let selections = self
681 .selections
682 .get(&set_id)
683 .ok_or_else(|| anyhow!("invalid selection set {:?}", set_id))?;
684 Some((set_id, selections.clone()))
685 } else {
686 None
687 };
688
689 if let Some(transaction) = self.history.end_transaction(selections, now) {
690 let since = transaction.start.clone();
691 let was_dirty = transaction.buffer_was_dirty;
692 self.history.group();
693
694 if let Some(ctx) = ctx {
695 ctx.notify();
696
697 if self.edits_since(since).next().is_some() {
698 self.did_edit(was_dirty, ctx);
699 }
700 }
701 }
702
703 Ok(())
704 }
705
706 pub fn edit<I, S, T>(
707 &mut self,
708 old_ranges: I,
709 new_text: T,
710 ctx: Option<&mut ModelContext<Self>>,
711 ) -> Result<Vec<Operation>>
712 where
713 I: IntoIterator<Item = Range<S>>,
714 S: ToOffset,
715 T: Into<Text>,
716 {
717 self.start_transaction_at(None, Instant::now())?;
718
719 let new_text = new_text.into();
720 let new_text = if new_text.len() > 0 {
721 Some(new_text)
722 } else {
723 None
724 };
725
726 let old_ranges = old_ranges
727 .into_iter()
728 .map(|range| Ok(range.start.to_offset(self)?..range.end.to_offset(self)?))
729 .collect::<Result<Vec<Range<usize>>>>()?;
730
731 let ops = self.splice_fragments(
732 old_ranges
733 .into_iter()
734 .filter(|old_range| new_text.is_some() || old_range.end > old_range.start),
735 new_text.clone(),
736 );
737
738 for op in &ops {
739 if let Operation::Edit { edit, .. } = op {
740 self.history.push(edit.clone());
741 self.history.push_undo(edit.id);
742 }
743 }
744
745 if let Some(op) = ops.last() {
746 if let Operation::Edit { edit, .. } = op {
747 self.last_edit = edit.id;
748 self.version.observe(edit.id);
749 } else {
750 unreachable!()
751 }
752 }
753
754 self.end_transaction_at(None, Instant::now(), ctx)?;
755
756 Ok(ops)
757 }
758
759 fn did_edit(&self, was_dirty: bool, ctx: &mut ModelContext<Self>) {
760 ctx.emit(Event::Edited);
761 if !was_dirty {
762 ctx.emit(Event::Dirtied);
763 }
764 }
765
766 pub fn simulate_typing<T: Rng>(&mut self, rng: &mut T) {
767 let end = rng.gen_range(0..self.len() + 1);
768 let start = rng.gen_range(0..end + 1);
769 let mut range = start..end;
770
771 let new_text_len = rng.gen_range(0..100);
772 let new_text: String = RandomCharIter::new(&mut *rng).take(new_text_len).collect();
773
774 for char in new_text.chars() {
775 self.edit(Some(range.clone()), char.to_string().as_str(), None)
776 .unwrap();
777 range = range.end + 1..range.end + 1;
778 }
779 }
780
781 pub fn randomly_edit<T>(
782 &mut self,
783 rng: &mut T,
784 old_range_count: usize,
785 ctx: Option<&mut ModelContext<Self>>,
786 ) -> (Vec<Range<usize>>, String, Vec<Operation>)
787 where
788 T: Rng,
789 {
790 let mut old_ranges: Vec<Range<usize>> = Vec::new();
791 for _ in 0..old_range_count {
792 let last_end = old_ranges.last().map_or(0, |last_range| last_range.end + 1);
793 if last_end > self.len() {
794 break;
795 }
796 let end = rng.gen_range(last_end..self.len() + 1);
797 let start = rng.gen_range(last_end..end + 1);
798 old_ranges.push(start..end);
799 }
800 let new_text_len = rng.gen_range(0..10);
801 let new_text: String = RandomCharIter::new(&mut *rng).take(new_text_len).collect();
802
803 let operations = self
804 .edit(old_ranges.iter().cloned(), new_text.as_str(), ctx)
805 .unwrap();
806
807 (old_ranges, new_text, operations)
808 }
809
810 pub fn add_selection_set(
811 &mut self,
812 selections: impl Into<Arc<[Selection]>>,
813 ctx: Option<&mut ModelContext<Self>>,
814 ) -> (SelectionSetId, Operation) {
815 let selections = selections.into();
816 let lamport_timestamp = self.lamport_clock.tick();
817 self.selections
818 .insert(lamport_timestamp, Arc::clone(&selections));
819 self.selections_last_update += 1;
820
821 if let Some(ctx) = ctx {
822 ctx.notify();
823 }
824
825 (
826 lamport_timestamp,
827 Operation::UpdateSelections {
828 set_id: lamport_timestamp,
829 selections: Some(selections),
830 lamport_timestamp,
831 },
832 )
833 }
834
835 pub fn update_selection_set(
836 &mut self,
837 set_id: SelectionSetId,
838 selections: impl Into<Arc<[Selection]>>,
839 ctx: Option<&mut ModelContext<Self>>,
840 ) -> Result<Operation> {
841 let selections = selections.into();
842 self.selections.insert(set_id, selections.clone());
843
844 let lamport_timestamp = self.lamport_clock.tick();
845 self.selections_last_update += 1;
846
847 if let Some(ctx) = ctx {
848 ctx.notify();
849 }
850
851 Ok(Operation::UpdateSelections {
852 set_id,
853 selections: Some(selections),
854 lamport_timestamp,
855 })
856 }
857
858 pub fn remove_selection_set(
859 &mut self,
860 set_id: SelectionSetId,
861 ctx: Option<&mut ModelContext<Self>>,
862 ) -> Result<Operation> {
863 self.selections
864 .remove(&set_id)
865 .ok_or_else(|| anyhow!("invalid selection set id {:?}", set_id))?;
866 let lamport_timestamp = self.lamport_clock.tick();
867 self.selections_last_update += 1;
868
869 if let Some(ctx) = ctx {
870 ctx.notify();
871 }
872
873 Ok(Operation::UpdateSelections {
874 set_id,
875 selections: None,
876 lamport_timestamp,
877 })
878 }
879
880 pub fn selections(&self, set_id: SelectionSetId) -> Result<&[Selection]> {
881 self.selections
882 .get(&set_id)
883 .map(|s| s.as_ref())
884 .ok_or_else(|| anyhow!("invalid selection set id {:?}", set_id))
885 }
886
887 pub fn apply_ops<I: IntoIterator<Item = Operation>>(
888 &mut self,
889 ops: I,
890 ctx: Option<&mut ModelContext<Self>>,
891 ) -> Result<()> {
892 let was_dirty = self.is_dirty();
893 let old_version = self.version.clone();
894
895 let mut deferred_ops = Vec::new();
896 for op in ops {
897 if self.can_apply_op(&op) {
898 self.apply_op(op)?;
899 } else {
900 self.deferred_replicas.insert(op.replica_id());
901 deferred_ops.push(op);
902 }
903 }
904 self.deferred_ops.insert(deferred_ops);
905 self.flush_deferred_ops()?;
906
907 if let Some(ctx) = ctx {
908 ctx.notify();
909 if self.edits_since(old_version).next().is_some() {
910 self.did_edit(was_dirty, ctx);
911 }
912 }
913
914 Ok(())
915 }
916
917 fn apply_op(&mut self, op: Operation) -> Result<()> {
918 match op {
919 Operation::Edit {
920 edit,
921 lamport_timestamp,
922 ..
923 } => {
924 if !self.version.observed(edit.id) {
925 self.apply_edit(
926 edit.start_id,
927 edit.start_offset,
928 edit.end_id,
929 edit.end_offset,
930 edit.new_text.as_ref().cloned(),
931 &edit.version_in_range,
932 edit.id,
933 lamport_timestamp,
934 )?;
935 self.version.observe(edit.id);
936 self.history.push(edit);
937 }
938 }
939 Operation::Undo {
940 undo,
941 lamport_timestamp,
942 } => {
943 if !self.version.observed(undo.id) {
944 self.apply_undo(undo)?;
945 self.version.observe(undo.id);
946 self.lamport_clock.observe(lamport_timestamp);
947 }
948 }
949 Operation::UpdateSelections {
950 set_id,
951 selections,
952 lamport_timestamp,
953 } => {
954 if let Some(selections) = selections {
955 self.selections.insert(set_id, selections);
956 } else {
957 self.selections.remove(&set_id);
958 }
959 self.lamport_clock.observe(lamport_timestamp);
960 self.selections_last_update += 1;
961 }
962 }
963 Ok(())
964 }
965
966 fn apply_edit(
967 &mut self,
968 start_id: time::Local,
969 start_offset: usize,
970 end_id: time::Local,
971 end_offset: usize,
972 new_text: Option<Text>,
973 version_in_range: &time::Global,
974 local_timestamp: time::Local,
975 lamport_timestamp: time::Lamport,
976 ) -> Result<()> {
977 let mut new_text = new_text.as_ref().cloned();
978 let start_fragment_id = self.resolve_fragment_id(start_id, start_offset)?;
979 let end_fragment_id = self.resolve_fragment_id(end_id, end_offset)?;
980
981 let old_fragments = self.fragments.clone();
982 let last_id = old_fragments.extent::<FragmentIdRef>().0.unwrap();
983 let last_id_ref = FragmentIdRef::new(&last_id);
984
985 let mut cursor = old_fragments.cursor::<FragmentIdRef, ()>();
986 let mut new_fragments =
987 cursor.slice(&FragmentIdRef::new(&start_fragment_id), SeekBias::Left, &());
988
989 if start_offset == cursor.item().unwrap().end_offset() {
990 new_fragments.push(cursor.item().unwrap().clone(), &());
991 cursor.next();
992 }
993
994 while let Some(fragment) = cursor.item() {
995 if new_text.is_none() && fragment.id > end_fragment_id {
996 break;
997 }
998
999 let mut fragment = fragment.clone();
1000
1001 if fragment.id == start_fragment_id || fragment.id == end_fragment_id {
1002 let split_start = if start_fragment_id == fragment.id {
1003 start_offset
1004 } else {
1005 fragment.start_offset()
1006 };
1007 let split_end = if end_fragment_id == fragment.id {
1008 end_offset
1009 } else {
1010 fragment.end_offset()
1011 };
1012 let (before_range, within_range, after_range) = self.split_fragment(
1013 cursor.prev_item().as_ref().unwrap(),
1014 &fragment,
1015 split_start..split_end,
1016 );
1017 let insertion = if let Some(new_text) = new_text.take() {
1018 Some(self.build_fragment_to_insert(
1019 before_range.as_ref().or(cursor.prev_item()).unwrap(),
1020 within_range.as_ref().or(after_range.as_ref()),
1021 new_text,
1022 local_timestamp,
1023 lamport_timestamp,
1024 ))
1025 } else {
1026 None
1027 };
1028 if let Some(fragment) = before_range {
1029 new_fragments.push(fragment, &());
1030 }
1031 if let Some(fragment) = insertion {
1032 new_fragments.push(fragment, &());
1033 }
1034 if let Some(mut fragment) = within_range {
1035 if fragment.was_visible(&version_in_range, &self.undo_map) {
1036 fragment.deletions.insert(local_timestamp);
1037 fragment.visible = false;
1038 }
1039 new_fragments.push(fragment, &());
1040 }
1041 if let Some(fragment) = after_range {
1042 new_fragments.push(fragment, &());
1043 }
1044 } else {
1045 if new_text.is_some() && lamport_timestamp > fragment.insertion.lamport_timestamp {
1046 new_fragments.push(
1047 self.build_fragment_to_insert(
1048 cursor.prev_item().as_ref().unwrap(),
1049 Some(&fragment),
1050 new_text.take().unwrap(),
1051 local_timestamp,
1052 lamport_timestamp,
1053 ),
1054 &(),
1055 );
1056 }
1057
1058 if fragment.id < end_fragment_id
1059 && fragment.was_visible(&version_in_range, &self.undo_map)
1060 {
1061 fragment.deletions.insert(local_timestamp);
1062 fragment.visible = false;
1063 }
1064 new_fragments.push(fragment, &());
1065 }
1066
1067 cursor.next();
1068 }
1069
1070 if let Some(new_text) = new_text {
1071 new_fragments.push(
1072 self.build_fragment_to_insert(
1073 cursor.prev_item().as_ref().unwrap(),
1074 None,
1075 new_text,
1076 local_timestamp,
1077 lamport_timestamp,
1078 ),
1079 &(),
1080 );
1081 }
1082
1083 new_fragments.push_tree(cursor.slice(&last_id_ref, SeekBias::Right, &()), &());
1084 self.fragments = new_fragments;
1085 self.local_clock.observe(local_timestamp);
1086 self.lamport_clock.observe(lamport_timestamp);
1087 Ok(())
1088 }
1089
1090 pub fn undo(&mut self, mut ctx: Option<&mut ModelContext<Self>>) -> Vec<Operation> {
1091 let was_dirty = self.is_dirty();
1092 let old_version = self.version.clone();
1093
1094 let mut ops = Vec::new();
1095 if let Some(transaction) = self.history.pop_undo() {
1096 let selections = transaction.selections_before.clone();
1097 for edit_id in transaction.edits.clone() {
1098 ops.push(self.undo_or_redo(edit_id).unwrap());
1099 }
1100
1101 if let Some((set_id, selections)) = selections {
1102 let _ = self.update_selection_set(set_id, selections, ctx.as_deref_mut());
1103 }
1104 }
1105
1106 if let Some(ctx) = ctx {
1107 ctx.notify();
1108 if self.edits_since(old_version).next().is_some() {
1109 self.did_edit(was_dirty, ctx);
1110 }
1111 }
1112
1113 ops
1114 }
1115
1116 pub fn redo(&mut self, mut ctx: Option<&mut ModelContext<Self>>) -> Vec<Operation> {
1117 let was_dirty = self.is_dirty();
1118 let old_version = self.version.clone();
1119
1120 let mut ops = Vec::new();
1121 if let Some(transaction) = self.history.pop_redo() {
1122 let selections = transaction.selections_after.clone();
1123 for edit_id in transaction.edits.clone() {
1124 ops.push(self.undo_or_redo(edit_id).unwrap());
1125 }
1126
1127 if let Some((set_id, selections)) = selections {
1128 let _ = self.update_selection_set(set_id, selections, ctx.as_deref_mut());
1129 }
1130 }
1131
1132 if let Some(ctx) = ctx {
1133 ctx.notify();
1134 if self.edits_since(old_version).next().is_some() {
1135 self.did_edit(was_dirty, ctx);
1136 }
1137 }
1138
1139 ops
1140 }
1141
1142 fn undo_or_redo(&mut self, edit_id: time::Local) -> Result<Operation> {
1143 let undo = UndoOperation {
1144 id: self.local_clock.tick(),
1145 edit_id,
1146 count: self.undo_map.undo_count(edit_id) + 1,
1147 };
1148 self.apply_undo(undo)?;
1149 self.version.observe(undo.id);
1150
1151 Ok(Operation::Undo {
1152 undo,
1153 lamport_timestamp: self.lamport_clock.tick(),
1154 })
1155 }
1156
1157 fn apply_undo(&mut self, undo: UndoOperation) -> Result<()> {
1158 let mut new_fragments;
1159
1160 self.undo_map.insert(undo);
1161 let edit = &self.history.ops[&undo.edit_id];
1162 let start_fragment_id = self.resolve_fragment_id(edit.start_id, edit.start_offset)?;
1163 let end_fragment_id = self.resolve_fragment_id(edit.end_id, edit.end_offset)?;
1164 let mut cursor = self.fragments.cursor::<FragmentIdRef, ()>();
1165
1166 if edit.start_id == edit.end_id && edit.start_offset == edit.end_offset {
1167 let splits = &self.insertion_splits[&undo.edit_id];
1168 let mut insertion_splits = splits.cursor::<(), ()>().map(|s| &s.fragment_id).peekable();
1169
1170 let first_split_id = insertion_splits.next().unwrap();
1171 new_fragments = cursor.slice(&FragmentIdRef::new(first_split_id), SeekBias::Left, &());
1172
1173 loop {
1174 let mut fragment = cursor.item().unwrap().clone();
1175 fragment.visible = fragment.is_visible(&self.undo_map);
1176 fragment.max_undos.observe(undo.id);
1177 new_fragments.push(fragment, &());
1178 cursor.next();
1179 if let Some(split_id) = insertion_splits.next() {
1180 new_fragments.push_tree(
1181 cursor.slice(&FragmentIdRef::new(split_id), SeekBias::Left, &()),
1182 &(),
1183 );
1184 } else {
1185 break;
1186 }
1187 }
1188 } else {
1189 new_fragments =
1190 cursor.slice(&FragmentIdRef::new(&start_fragment_id), SeekBias::Left, &());
1191 while let Some(fragment) = cursor.item() {
1192 if fragment.id > end_fragment_id {
1193 break;
1194 } else {
1195 let mut fragment = fragment.clone();
1196 if edit.version_in_range.observed(fragment.insertion.id)
1197 || fragment.insertion.id == undo.edit_id
1198 {
1199 fragment.visible = fragment.is_visible(&self.undo_map);
1200 fragment.max_undos.observe(undo.id);
1201 }
1202 new_fragments.push(fragment, &());
1203 cursor.next();
1204 }
1205 }
1206 }
1207
1208 new_fragments.push_tree(cursor.suffix(&()), &());
1209 drop(cursor);
1210 self.fragments = new_fragments;
1211
1212 Ok(())
1213 }
1214
1215 fn flush_deferred_ops(&mut self) -> Result<()> {
1216 self.deferred_replicas.clear();
1217 let mut deferred_ops = Vec::new();
1218 for op in self.deferred_ops.drain().cursor().cloned() {
1219 if self.can_apply_op(&op) {
1220 self.apply_op(op)?;
1221 } else {
1222 self.deferred_replicas.insert(op.replica_id());
1223 deferred_ops.push(op);
1224 }
1225 }
1226 self.deferred_ops.insert(deferred_ops);
1227 Ok(())
1228 }
1229
1230 fn can_apply_op(&self, op: &Operation) -> bool {
1231 if self.deferred_replicas.contains(&op.replica_id()) {
1232 false
1233 } else {
1234 match op {
1235 Operation::Edit { edit, .. } => {
1236 self.version.observed(edit.start_id)
1237 && self.version.observed(edit.end_id)
1238 && edit.version_in_range <= self.version
1239 }
1240 Operation::Undo { undo, .. } => self.version.observed(undo.edit_id),
1241 Operation::UpdateSelections { selections, .. } => {
1242 if let Some(selections) = selections {
1243 selections.iter().all(|selection| {
1244 let contains_start = match selection.start {
1245 Anchor::Middle { insertion_id, .. } => {
1246 self.version.observed(insertion_id)
1247 }
1248 _ => true,
1249 };
1250 let contains_end = match selection.end {
1251 Anchor::Middle { insertion_id, .. } => {
1252 self.version.observed(insertion_id)
1253 }
1254 _ => true,
1255 };
1256 contains_start && contains_end
1257 })
1258 } else {
1259 true
1260 }
1261 }
1262 }
1263 }
1264 }
1265
1266 fn resolve_fragment_id(&self, edit_id: time::Local, offset: usize) -> Result<FragmentId> {
1267 let split_tree = self
1268 .insertion_splits
1269 .get(&edit_id)
1270 .ok_or_else(|| anyhow!("invalid operation"))?;
1271 let mut cursor = split_tree.cursor::<usize, ()>();
1272 cursor.seek(&offset, SeekBias::Left, &());
1273 Ok(cursor
1274 .item()
1275 .ok_or_else(|| anyhow!("invalid operation"))?
1276 .fragment_id
1277 .clone())
1278 }
1279
1280 fn splice_fragments<I>(&mut self, mut old_ranges: I, new_text: Option<Text>) -> Vec<Operation>
1281 where
1282 I: Iterator<Item = Range<usize>>,
1283 {
1284 let mut cur_range = old_ranges.next();
1285 if cur_range.is_none() {
1286 return Vec::new();
1287 }
1288
1289 let mut ops = Vec::with_capacity(old_ranges.size_hint().0);
1290
1291 let old_fragments = self.fragments.clone();
1292 let mut cursor = old_fragments.cursor::<usize, usize>();
1293 let mut new_fragments = SumTree::new();
1294 new_fragments.push_tree(
1295 cursor.slice(&cur_range.as_ref().unwrap().start, SeekBias::Right, &()),
1296 &(),
1297 );
1298
1299 let mut start_id = None;
1300 let mut start_offset = None;
1301 let mut end_id = None;
1302 let mut end_offset = None;
1303 let mut version_in_range = time::Global::new();
1304
1305 let mut local_timestamp = self.local_clock.tick();
1306 let mut lamport_timestamp = self.lamport_clock.tick();
1307
1308 while cur_range.is_some() && cursor.item().is_some() {
1309 let mut fragment = cursor.item().unwrap().clone();
1310 let fragment_summary = cursor.item_summary().unwrap();
1311 let mut fragment_start = *cursor.start();
1312 let mut fragment_end = fragment_start + fragment.visible_len();
1313
1314 let old_split_tree = self
1315 .insertion_splits
1316 .remove(&fragment.insertion.id)
1317 .unwrap();
1318 let mut splits_cursor = old_split_tree.cursor::<usize, ()>();
1319 let mut new_split_tree =
1320 splits_cursor.slice(&fragment.start_offset(), SeekBias::Right, &());
1321
1322 // Find all splices that start or end within the current fragment. Then, split the
1323 // fragment and reassemble it in both trees accounting for the deleted and the newly
1324 // inserted text.
1325 while cur_range.as_ref().map_or(false, |r| r.start < fragment_end) {
1326 let range = cur_range.clone().unwrap();
1327 if range.start > fragment_start {
1328 let mut prefix = fragment.clone();
1329 prefix.set_end_offset(prefix.start_offset() + (range.start - fragment_start));
1330 prefix.id =
1331 FragmentId::between(&new_fragments.last().unwrap().id, &fragment.id);
1332 fragment.set_start_offset(prefix.end_offset());
1333 new_fragments.push(prefix.clone(), &());
1334 new_split_tree.push(
1335 InsertionSplit {
1336 extent: prefix.end_offset() - prefix.start_offset(),
1337 fragment_id: prefix.id,
1338 },
1339 &(),
1340 );
1341 fragment_start = range.start;
1342 }
1343
1344 if range.end == fragment_start {
1345 end_id = Some(new_fragments.last().unwrap().insertion.id);
1346 end_offset = Some(new_fragments.last().unwrap().end_offset());
1347 } else if range.end == fragment_end {
1348 end_id = Some(fragment.insertion.id);
1349 end_offset = Some(fragment.end_offset());
1350 }
1351
1352 if range.start == fragment_start {
1353 start_id = Some(new_fragments.last().unwrap().insertion.id);
1354 start_offset = Some(new_fragments.last().unwrap().end_offset());
1355
1356 if let Some(new_text) = new_text.clone() {
1357 let new_fragment = self.build_fragment_to_insert(
1358 &new_fragments.last().unwrap(),
1359 Some(&fragment),
1360 new_text,
1361 local_timestamp,
1362 lamport_timestamp,
1363 );
1364 new_fragments.push(new_fragment, &());
1365 }
1366 }
1367
1368 if range.end < fragment_end {
1369 if range.end > fragment_start {
1370 let mut prefix = fragment.clone();
1371 prefix.set_end_offset(prefix.start_offset() + (range.end - fragment_start));
1372 prefix.id =
1373 FragmentId::between(&new_fragments.last().unwrap().id, &fragment.id);
1374 version_in_range.observe_all(&fragment_summary.max_version);
1375 if fragment.visible {
1376 prefix.deletions.insert(local_timestamp);
1377 prefix.visible = false;
1378 }
1379 fragment.set_start_offset(prefix.end_offset());
1380 new_fragments.push(prefix.clone(), &());
1381 new_split_tree.push(
1382 InsertionSplit {
1383 extent: prefix.end_offset() - prefix.start_offset(),
1384 fragment_id: prefix.id,
1385 },
1386 &(),
1387 );
1388 fragment_start = range.end;
1389 end_id = Some(fragment.insertion.id);
1390 end_offset = Some(fragment.start_offset());
1391 }
1392 } else {
1393 version_in_range.observe_all(&fragment_summary.max_version);
1394 if fragment.visible {
1395 fragment.deletions.insert(local_timestamp);
1396 fragment.visible = false;
1397 }
1398 }
1399
1400 // If the splice ends inside this fragment, we can advance to the next splice and
1401 // check if it also intersects the current fragment. Otherwise we break out of the
1402 // loop and find the first fragment that the splice does not contain fully.
1403 if range.end <= fragment_end {
1404 ops.push(Operation::Edit {
1405 edit: EditOperation {
1406 id: local_timestamp,
1407 start_id: start_id.unwrap(),
1408 start_offset: start_offset.unwrap(),
1409 end_id: end_id.unwrap(),
1410 end_offset: end_offset.unwrap(),
1411 version_in_range,
1412 new_text: new_text.clone(),
1413 },
1414 lamport_timestamp,
1415 });
1416
1417 start_id = None;
1418 start_offset = None;
1419 end_id = None;
1420 end_offset = None;
1421 version_in_range = time::Global::new();
1422 cur_range = old_ranges.next();
1423 if cur_range.is_some() {
1424 local_timestamp = self.local_clock.tick();
1425 lamport_timestamp = self.lamport_clock.tick();
1426 }
1427 } else {
1428 break;
1429 }
1430 }
1431 new_split_tree.push(
1432 InsertionSplit {
1433 extent: fragment.end_offset() - fragment.start_offset(),
1434 fragment_id: fragment.id.clone(),
1435 },
1436 &(),
1437 );
1438 splits_cursor.next();
1439 new_split_tree.push_tree(
1440 splits_cursor.slice(&old_split_tree.extent::<usize>(), SeekBias::Right, &()),
1441 &(),
1442 );
1443 self.insertion_splits
1444 .insert(fragment.insertion.id, new_split_tree);
1445 new_fragments.push(fragment, &());
1446
1447 // Scan forward until we find a fragment that is not fully contained by the current splice.
1448 cursor.next();
1449 if let Some(range) = cur_range.clone() {
1450 while let Some(fragment) = cursor.item() {
1451 let fragment_summary = cursor.item_summary().unwrap();
1452 fragment_start = *cursor.start();
1453 fragment_end = fragment_start + fragment.visible_len();
1454 if range.start < fragment_start && range.end >= fragment_end {
1455 let mut new_fragment = fragment.clone();
1456 version_in_range.observe_all(&fragment_summary.max_version);
1457 if new_fragment.visible {
1458 new_fragment.deletions.insert(local_timestamp);
1459 new_fragment.visible = false;
1460 }
1461 new_fragments.push(new_fragment, &());
1462 cursor.next();
1463
1464 if range.end == fragment_end {
1465 end_id = Some(fragment.insertion.id);
1466 end_offset = Some(fragment.end_offset());
1467 ops.push(Operation::Edit {
1468 edit: EditOperation {
1469 id: local_timestamp,
1470 start_id: start_id.unwrap(),
1471 start_offset: start_offset.unwrap(),
1472 end_id: end_id.unwrap(),
1473 end_offset: end_offset.unwrap(),
1474 version_in_range,
1475 new_text: new_text.clone(),
1476 },
1477 lamport_timestamp,
1478 });
1479
1480 start_id = None;
1481 start_offset = None;
1482 end_id = None;
1483 end_offset = None;
1484 version_in_range = time::Global::new();
1485
1486 cur_range = old_ranges.next();
1487 if cur_range.is_some() {
1488 local_timestamp = self.local_clock.tick();
1489 lamport_timestamp = self.lamport_clock.tick();
1490 }
1491 break;
1492 }
1493 } else {
1494 break;
1495 }
1496 }
1497
1498 // If the splice we are currently evaluating starts after the end of the fragment
1499 // that the cursor is parked at, we should seek to the next splice's start range
1500 // and push all the fragments in between into the new tree.
1501 if cur_range.as_ref().map_or(false, |r| r.start > fragment_end) {
1502 new_fragments.push_tree(
1503 cursor.slice(&cur_range.as_ref().unwrap().start, SeekBias::Right, &()),
1504 &(),
1505 );
1506 }
1507 }
1508 }
1509
1510 // Handle range that is at the end of the buffer if it exists. There should never be
1511 // multiple because ranges must be disjoint.
1512 if cur_range.is_some() {
1513 debug_assert_eq!(old_ranges.next(), None);
1514 let last_fragment = new_fragments.last().unwrap();
1515 ops.push(Operation::Edit {
1516 edit: EditOperation {
1517 id: local_timestamp,
1518 start_id: last_fragment.insertion.id,
1519 start_offset: last_fragment.end_offset(),
1520 end_id: last_fragment.insertion.id,
1521 end_offset: last_fragment.end_offset(),
1522 version_in_range: time::Global::new(),
1523 new_text: new_text.clone(),
1524 },
1525 lamport_timestamp,
1526 });
1527
1528 if let Some(new_text) = new_text {
1529 let new_fragment = self.build_fragment_to_insert(
1530 &last_fragment,
1531 None,
1532 new_text,
1533 local_timestamp,
1534 lamport_timestamp,
1535 );
1536 new_fragments.push(new_fragment, &());
1537 }
1538 } else {
1539 new_fragments.push_tree(
1540 cursor.slice(&old_fragments.extent::<usize>(), SeekBias::Right, &()),
1541 &(),
1542 );
1543 }
1544
1545 self.fragments = new_fragments;
1546 ops
1547 }
1548
1549 fn split_fragment(
1550 &mut self,
1551 prev_fragment: &Fragment,
1552 fragment: &Fragment,
1553 range: Range<usize>,
1554 ) -> (Option<Fragment>, Option<Fragment>, Option<Fragment>) {
1555 debug_assert!(range.start >= fragment.start_offset());
1556 debug_assert!(range.start <= fragment.end_offset());
1557 debug_assert!(range.end <= fragment.end_offset());
1558 debug_assert!(range.end >= fragment.start_offset());
1559
1560 if range.end == fragment.start_offset() {
1561 (None, None, Some(fragment.clone()))
1562 } else if range.start == fragment.end_offset() {
1563 (Some(fragment.clone()), None, None)
1564 } else if range.start == fragment.start_offset() && range.end == fragment.end_offset() {
1565 (None, Some(fragment.clone()), None)
1566 } else {
1567 let mut prefix = fragment.clone();
1568
1569 let after_range = if range.end < fragment.end_offset() {
1570 let mut suffix = prefix.clone();
1571 suffix.set_start_offset(range.end);
1572 prefix.set_end_offset(range.end);
1573 prefix.id = FragmentId::between(&prev_fragment.id, &suffix.id);
1574 Some(suffix)
1575 } else {
1576 None
1577 };
1578
1579 let within_range = if range.start != range.end {
1580 let mut suffix = prefix.clone();
1581 suffix.set_start_offset(range.start);
1582 prefix.set_end_offset(range.start);
1583 prefix.id = FragmentId::between(&prev_fragment.id, &suffix.id);
1584 Some(suffix)
1585 } else {
1586 None
1587 };
1588
1589 let before_range = if range.start > fragment.start_offset() {
1590 Some(prefix)
1591 } else {
1592 None
1593 };
1594
1595 let old_split_tree = self
1596 .insertion_splits
1597 .remove(&fragment.insertion.id)
1598 .unwrap();
1599 let mut cursor = old_split_tree.cursor::<usize, ()>();
1600 let mut new_split_tree = cursor.slice(&fragment.start_offset(), SeekBias::Right, &());
1601
1602 if let Some(ref fragment) = before_range {
1603 new_split_tree.push(
1604 InsertionSplit {
1605 extent: range.start - fragment.start_offset(),
1606 fragment_id: fragment.id.clone(),
1607 },
1608 &(),
1609 );
1610 }
1611
1612 if let Some(ref fragment) = within_range {
1613 new_split_tree.push(
1614 InsertionSplit {
1615 extent: range.end - range.start,
1616 fragment_id: fragment.id.clone(),
1617 },
1618 &(),
1619 );
1620 }
1621
1622 if let Some(ref fragment) = after_range {
1623 new_split_tree.push(
1624 InsertionSplit {
1625 extent: fragment.end_offset() - range.end,
1626 fragment_id: fragment.id.clone(),
1627 },
1628 &(),
1629 );
1630 }
1631
1632 cursor.next();
1633 new_split_tree.push_tree(
1634 cursor.slice(&old_split_tree.extent::<usize>(), SeekBias::Right, &()),
1635 &(),
1636 );
1637
1638 self.insertion_splits
1639 .insert(fragment.insertion.id, new_split_tree);
1640
1641 (before_range, within_range, after_range)
1642 }
1643 }
1644
1645 fn build_fragment_to_insert(
1646 &mut self,
1647 prev_fragment: &Fragment,
1648 next_fragment: Option<&Fragment>,
1649 text: Text,
1650 local_timestamp: time::Local,
1651 lamport_timestamp: time::Lamport,
1652 ) -> Fragment {
1653 let new_fragment_id = FragmentId::between(
1654 &prev_fragment.id,
1655 next_fragment
1656 .map(|f| &f.id)
1657 .unwrap_or(&FragmentId::max_value()),
1658 );
1659
1660 let mut split_tree = SumTree::new();
1661 split_tree.push(
1662 InsertionSplit {
1663 extent: text.len(),
1664 fragment_id: new_fragment_id.clone(),
1665 },
1666 &(),
1667 );
1668 self.insertion_splits.insert(local_timestamp, split_tree);
1669
1670 Fragment::new(
1671 new_fragment_id,
1672 Insertion {
1673 id: local_timestamp,
1674 parent_id: prev_fragment.insertion.id,
1675 offset_in_parent: prev_fragment.end_offset(),
1676 text,
1677 lamport_timestamp,
1678 },
1679 )
1680 }
1681
1682 pub fn anchor_before<T: ToOffset>(&self, position: T) -> Result<Anchor> {
1683 self.anchor_at(position, AnchorBias::Left)
1684 }
1685
1686 pub fn anchor_after<T: ToOffset>(&self, position: T) -> Result<Anchor> {
1687 self.anchor_at(position, AnchorBias::Right)
1688 }
1689
1690 pub fn anchor_at<T: ToOffset>(&self, position: T, bias: AnchorBias) -> Result<Anchor> {
1691 let offset = position.to_offset(self)?;
1692 let max_offset = self.len();
1693 if offset > max_offset {
1694 return Err(anyhow!("offset is out of range"));
1695 }
1696
1697 let seek_bias;
1698 match bias {
1699 AnchorBias::Left => {
1700 if offset == 0 {
1701 return Ok(Anchor::Start);
1702 } else {
1703 seek_bias = SeekBias::Left;
1704 }
1705 }
1706 AnchorBias::Right => {
1707 if offset == max_offset {
1708 return Ok(Anchor::End);
1709 } else {
1710 seek_bias = SeekBias::Right;
1711 }
1712 }
1713 };
1714
1715 let mut cursor = self.fragments.cursor::<usize, usize>();
1716 cursor.seek(&offset, seek_bias, &());
1717 let fragment = cursor.item().unwrap();
1718 let offset_in_fragment = offset - cursor.start();
1719 let offset_in_insertion = fragment.start_offset() + offset_in_fragment;
1720 let anchor = Anchor::Middle {
1721 insertion_id: fragment.insertion.id,
1722 offset: offset_in_insertion,
1723 bias,
1724 };
1725 Ok(anchor)
1726 }
1727
1728 fn fragment_id_for_anchor(&self, anchor: &Anchor) -> Result<&FragmentId> {
1729 match anchor {
1730 Anchor::Start => Ok(FragmentId::max_value()),
1731 Anchor::End => Ok(FragmentId::min_value()),
1732 Anchor::Middle {
1733 insertion_id,
1734 offset,
1735 bias,
1736 ..
1737 } => {
1738 let seek_bias = match bias {
1739 AnchorBias::Left => SeekBias::Left,
1740 AnchorBias::Right => SeekBias::Right,
1741 };
1742
1743 let splits = self
1744 .insertion_splits
1745 .get(&insertion_id)
1746 .ok_or_else(|| anyhow!("split does not exist for insertion id"))?;
1747 let mut splits_cursor = splits.cursor::<usize, ()>();
1748 splits_cursor.seek(offset, seek_bias, &());
1749 splits_cursor
1750 .item()
1751 .ok_or_else(|| anyhow!("split offset is out of range"))
1752 .map(|split| &split.fragment_id)
1753 }
1754 }
1755 }
1756
1757 fn summary_for_anchor(&self, anchor: &Anchor) -> Result<TextSummary> {
1758 match anchor {
1759 Anchor::Start => Ok(TextSummary::default()),
1760 Anchor::End => Ok(self.fragments.summary().text_summary),
1761 Anchor::Middle {
1762 insertion_id,
1763 offset,
1764 bias,
1765 } => {
1766 let seek_bias = match bias {
1767 AnchorBias::Left => SeekBias::Left,
1768 AnchorBias::Right => SeekBias::Right,
1769 };
1770
1771 let splits = self
1772 .insertion_splits
1773 .get(&insertion_id)
1774 .ok_or_else(|| anyhow!("split does not exist for insertion id"))?;
1775 let mut splits_cursor = splits.cursor::<usize, ()>();
1776 splits_cursor.seek(offset, seek_bias, &());
1777 let split = splits_cursor
1778 .item()
1779 .ok_or_else(|| anyhow!("split offset is out of range"))?;
1780
1781 let mut fragments_cursor = self.fragments.cursor::<FragmentIdRef, TextSummary>();
1782 fragments_cursor.seek(&FragmentIdRef::new(&split.fragment_id), SeekBias::Left, &());
1783 let fragment = fragments_cursor
1784 .item()
1785 .ok_or_else(|| anyhow!("fragment id does not exist"))?;
1786
1787 let mut summary = fragments_cursor.start().clone();
1788 if fragment.visible {
1789 summary += fragment
1790 .text
1791 .slice(..offset - fragment.start_offset())
1792 .summary();
1793 }
1794 Ok(summary)
1795 }
1796 }
1797 }
1798
1799 #[allow(dead_code)]
1800 pub fn point_for_offset(&self, offset: usize) -> Result<Point> {
1801 let mut fragments_cursor = self.fragments.cursor::<usize, TextSummary>();
1802 fragments_cursor.seek(&offset, SeekBias::Left, &());
1803 fragments_cursor
1804 .item()
1805 .ok_or_else(|| anyhow!("offset is out of range"))
1806 .map(|fragment| {
1807 let overshoot = fragment
1808 .point_for_offset(offset - &fragments_cursor.start().chars)
1809 .unwrap();
1810 fragments_cursor.start().lines + &overshoot
1811 })
1812 }
1813}
1814
1815impl Clone for Buffer {
1816 fn clone(&self) -> Self {
1817 Self {
1818 fragments: self.fragments.clone(),
1819 insertion_splits: self.insertion_splits.clone(),
1820 version: self.version.clone(),
1821 saved_version: self.saved_version.clone(),
1822 last_edit: self.last_edit.clone(),
1823 undo_map: self.undo_map.clone(),
1824 history: self.history.clone(),
1825 selections: self.selections.clone(),
1826 selections_last_update: self.selections_last_update.clone(),
1827 deferred_ops: self.deferred_ops.clone(),
1828 file: self.file.clone(),
1829 deferred_replicas: self.deferred_replicas.clone(),
1830 replica_id: self.replica_id,
1831 local_clock: self.local_clock.clone(),
1832 lamport_clock: self.lamport_clock.clone(),
1833 }
1834 }
1835}
1836
1837impl Snapshot {
1838 pub fn fragments<'a>(&'a self) -> FragmentIter<'a> {
1839 FragmentIter::new(&self.fragments)
1840 }
1841
1842 pub fn text_summary(&self) -> TextSummary {
1843 self.fragments.summary().text_summary
1844 }
1845}
1846
1847#[derive(Clone, Debug, Eq, PartialEq)]
1848pub enum Event {
1849 Edited,
1850 Dirtied,
1851 Saved,
1852 FileHandleChanged,
1853}
1854
1855impl Entity for Buffer {
1856 type Event = Event;
1857}
1858
1859impl<'a> sum_tree::Dimension<'a, FragmentSummary> for Point {
1860 fn add_summary(&mut self, summary: &FragmentSummary) {
1861 *self += &summary.text_summary.lines;
1862 }
1863}
1864
1865impl<'a> CharIter<'a> {
1866 fn new(fragments: &'a SumTree<Fragment>, offset: usize) -> Self {
1867 let mut fragments_cursor = fragments.cursor::<usize, usize>();
1868 fragments_cursor.seek(&offset, SeekBias::Right, &());
1869 let fragment_chars = fragments_cursor.item().map_or("".chars(), |fragment| {
1870 let offset_in_fragment = offset - fragments_cursor.start();
1871 fragment.text[offset_in_fragment..].chars()
1872 });
1873 Self {
1874 fragments_cursor,
1875 fragment_chars,
1876 }
1877 }
1878}
1879
1880impl<'a> Iterator for CharIter<'a> {
1881 type Item = char;
1882
1883 fn next(&mut self) -> Option<Self::Item> {
1884 if let Some(char) = self.fragment_chars.next() {
1885 Some(char)
1886 } else {
1887 loop {
1888 self.fragments_cursor.next();
1889 if let Some(fragment) = self.fragments_cursor.item() {
1890 if fragment.visible {
1891 self.fragment_chars = fragment.text.as_str().chars();
1892 return self.fragment_chars.next();
1893 }
1894 } else {
1895 return None;
1896 }
1897 }
1898 }
1899 }
1900}
1901
1902impl<'a> FragmentIter<'a> {
1903 fn new(fragments: &'a SumTree<Fragment>) -> Self {
1904 let mut cursor = fragments.cursor::<usize, usize>();
1905 cursor.seek(&0, SeekBias::Right, &());
1906 Self {
1907 cursor,
1908 started: false,
1909 }
1910 }
1911}
1912
1913impl<'a> Iterator for FragmentIter<'a> {
1914 type Item = &'a str;
1915
1916 fn next(&mut self) -> Option<Self::Item> {
1917 loop {
1918 if self.started {
1919 self.cursor.next();
1920 } else {
1921 self.started = true;
1922 }
1923 if let Some(fragment) = self.cursor.item() {
1924 if fragment.visible {
1925 return Some(fragment.text.as_str());
1926 }
1927 } else {
1928 return None;
1929 }
1930 }
1931 }
1932}
1933
1934impl<'a, F: Fn(&FragmentSummary) -> bool> Iterator for Edits<'a, F> {
1935 type Item = Edit;
1936
1937 fn next(&mut self) -> Option<Self::Item> {
1938 let mut change: Option<Edit> = None;
1939
1940 while let Some(fragment) = self.cursor.item() {
1941 let new_offset = *self.cursor.start();
1942 let old_offset = (new_offset as isize - self.delta) as usize;
1943
1944 if !fragment.was_visible(&self.since, &self.undos) && fragment.visible {
1945 if let Some(ref mut change) = change {
1946 if change.new_range.end == new_offset {
1947 change.new_range.end += fragment.len();
1948 self.delta += fragment.len() as isize;
1949 } else {
1950 break;
1951 }
1952 } else {
1953 change = Some(Edit {
1954 old_range: old_offset..old_offset,
1955 new_range: new_offset..new_offset + fragment.len(),
1956 });
1957 self.delta += fragment.len() as isize;
1958 }
1959 } else if fragment.was_visible(&self.since, &self.undos) && !fragment.visible {
1960 if let Some(ref mut change) = change {
1961 if change.new_range.end == new_offset {
1962 change.old_range.end += fragment.len();
1963 self.delta -= fragment.len() as isize;
1964 } else {
1965 break;
1966 }
1967 } else {
1968 change = Some(Edit {
1969 old_range: old_offset..old_offset + fragment.len(),
1970 new_range: new_offset..new_offset,
1971 });
1972 self.delta -= fragment.len() as isize;
1973 }
1974 }
1975
1976 self.cursor.next();
1977 }
1978
1979 change
1980 }
1981}
1982
1983// pub fn diff(a: &[u16], b: &[u16]) -> Vec<Edit> {
1984// struct EditCollector<'a> {
1985// a: &'a [u16],
1986// b: &'a [u16],
1987// position: Point,
1988// changes: Vec<Edit>,
1989// }
1990//
1991// impl<'a> diffs::Diff for EditCollector<'a> {
1992// type Error = ();
1993//
1994// fn equal(&mut self, old: usize, _: usize, len: usize) -> Result<(), ()> {
1995// self.position += &Text::extent(&self.a[old..old + len]);
1996// Ok(())
1997// }
1998//
1999// fn delete(&mut self, old: usize, len: usize) -> Result<(), ()> {
2000// self.changes.push(Edit {
2001// range: self.position..self.position + &Text::extent(&self.a[old..old + len]),
2002// chars: Vec::new(),
2003// new_char_count: Point::zero(),
2004// });
2005// Ok(())
2006// }
2007//
2008// fn insert(&mut self, _: usize, new: usize, new_len: usize) -> Result<(), ()> {
2009// let new_char_count = Text::extent(&self.b[new..new + new_len]);
2010// self.changes.push(Edit {
2011// range: self.position..self.position,
2012// chars: Vec::from(&self.b[new..new + new_len]),
2013// new_char_count,
2014// });
2015// self.position += &new_char_count;
2016// Ok(())
2017// }
2018//
2019// fn replace(
2020// &mut self,
2021// old: usize,
2022// old_len: usize,
2023// new: usize,
2024// new_len: usize,
2025// ) -> Result<(), ()> {
2026// let old_extent = text::extent(&self.a[old..old + old_len]);
2027// let new_char_count = text::extent(&self.b[new..new + new_len]);
2028// self.changes.push(Edit {
2029// range: self.position..self.position + &old_extent,
2030// chars: Vec::from(&self.b[new..new + new_len]),
2031// new_char_count,
2032// });
2033// self.position += &new_char_count;
2034// Ok(())
2035// }
2036// }
2037//
2038// let mut collector = diffs::Replace::new(EditCollector {
2039// a,
2040// b,
2041// position: Point::zero(),
2042// changes: Vec::new(),
2043// });
2044// diffs::myers::diff(&mut collector, a, 0, a.len(), b, 0, b.len()).unwrap();
2045// collector.into_inner().changes
2046// }
2047
2048#[derive(Ord, PartialOrd, Eq, PartialEq, Clone, Debug)]
2049struct FragmentId(Arc<[u16]>);
2050
2051lazy_static! {
2052 static ref FRAGMENT_ID_EMPTY: FragmentId = FragmentId(Arc::from([]));
2053 static ref FRAGMENT_ID_MIN_VALUE: FragmentId = FragmentId(Arc::from([0 as u16]));
2054 static ref FRAGMENT_ID_MAX_VALUE: FragmentId = FragmentId(Arc::from([u16::max_value()]));
2055}
2056
2057impl Default for FragmentId {
2058 fn default() -> Self {
2059 FRAGMENT_ID_EMPTY.clone()
2060 }
2061}
2062
2063impl FragmentId {
2064 fn min_value() -> &'static Self {
2065 &FRAGMENT_ID_MIN_VALUE
2066 }
2067
2068 fn max_value() -> &'static Self {
2069 &FRAGMENT_ID_MAX_VALUE
2070 }
2071
2072 fn between(left: &Self, right: &Self) -> Self {
2073 Self::between_with_max(left, right, u16::max_value())
2074 }
2075
2076 fn between_with_max(left: &Self, right: &Self, max_value: u16) -> Self {
2077 let mut new_entries = Vec::new();
2078
2079 let left_entries = left.0.iter().cloned().chain(iter::repeat(0));
2080 let right_entries = right.0.iter().cloned().chain(iter::repeat(max_value));
2081 for (l, r) in left_entries.zip(right_entries) {
2082 let interval = r - l;
2083 if interval > 1 {
2084 new_entries.push(l + cmp::max(1, cmp::min(8, interval / 2)));
2085 break;
2086 } else {
2087 new_entries.push(l);
2088 }
2089 }
2090
2091 FragmentId(Arc::from(new_entries))
2092 }
2093}
2094
2095#[derive(Ord, PartialOrd, Eq, PartialEq, Clone, Debug, Default)]
2096struct FragmentIdRef<'a>(Option<&'a FragmentId>);
2097
2098impl<'a> FragmentIdRef<'a> {
2099 fn new(id: &'a FragmentId) -> Self {
2100 Self(Some(id))
2101 }
2102}
2103
2104impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FragmentIdRef<'a> {
2105 fn add_summary(&mut self, summary: &'a FragmentSummary) {
2106 self.0 = Some(&summary.max_fragment_id)
2107 }
2108}
2109
2110impl Fragment {
2111 fn new(id: FragmentId, insertion: Insertion) -> Self {
2112 Self {
2113 id,
2114 text: insertion.text.clone(),
2115 insertion,
2116 deletions: Default::default(),
2117 max_undos: Default::default(),
2118 visible: true,
2119 }
2120 }
2121
2122 fn start_offset(&self) -> usize {
2123 self.text.range().start
2124 }
2125
2126 fn set_start_offset(&mut self, offset: usize) {
2127 self.text = self.insertion.text.slice(offset..self.end_offset());
2128 }
2129
2130 fn end_offset(&self) -> usize {
2131 self.text.range().end
2132 }
2133
2134 fn set_end_offset(&mut self, offset: usize) {
2135 self.text = self.insertion.text.slice(self.start_offset()..offset);
2136 }
2137
2138 fn visible_len(&self) -> usize {
2139 if self.visible {
2140 self.len()
2141 } else {
2142 0
2143 }
2144 }
2145
2146 fn len(&self) -> usize {
2147 self.text.len()
2148 }
2149
2150 fn is_visible(&self, undos: &UndoMap) -> bool {
2151 !undos.is_undone(self.insertion.id) && self.deletions.iter().all(|d| undos.is_undone(*d))
2152 }
2153
2154 fn was_visible(&self, version: &time::Global, undos: &UndoMap) -> bool {
2155 (version.observed(self.insertion.id) && !undos.was_undone(self.insertion.id, version))
2156 && self
2157 .deletions
2158 .iter()
2159 .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
2160 }
2161
2162 fn point_for_offset(&self, offset: usize) -> Result<Point> {
2163 Ok(self.text.point_for_offset(offset))
2164 }
2165
2166 fn offset_for_point(&self, point: Point) -> Result<usize> {
2167 Ok(self.text.offset_for_point(point))
2168 }
2169}
2170
2171impl sum_tree::Item for Fragment {
2172 type Summary = FragmentSummary;
2173
2174 fn summary(&self) -> Self::Summary {
2175 let mut max_version = time::Global::new();
2176 max_version.observe(self.insertion.id);
2177 for deletion in &self.deletions {
2178 max_version.observe(*deletion);
2179 }
2180 max_version.observe_all(&self.max_undos);
2181
2182 if self.visible {
2183 FragmentSummary {
2184 text_summary: self.text.summary(),
2185 max_fragment_id: self.id.clone(),
2186 max_version,
2187 }
2188 } else {
2189 FragmentSummary {
2190 text_summary: TextSummary::default(),
2191 max_fragment_id: self.id.clone(),
2192 max_version,
2193 }
2194 }
2195 }
2196}
2197
2198impl sum_tree::Summary for FragmentSummary {
2199 type Context = ();
2200
2201 fn add_summary(&mut self, other: &Self, _: &()) {
2202 self.text_summary += &other.text_summary;
2203 debug_assert!(self.max_fragment_id <= other.max_fragment_id);
2204 self.max_fragment_id = other.max_fragment_id.clone();
2205 self.max_version.observe_all(&other.max_version);
2206 }
2207}
2208
2209impl Default for FragmentSummary {
2210 fn default() -> Self {
2211 FragmentSummary {
2212 text_summary: TextSummary::default(),
2213 max_fragment_id: FragmentId::min_value().clone(),
2214 max_version: time::Global::new(),
2215 }
2216 }
2217}
2218
2219impl<'a> sum_tree::Dimension<'a, FragmentSummary> for TextSummary {
2220 fn add_summary(&mut self, summary: &FragmentSummary) {
2221 *self += &summary.text_summary;
2222 }
2223}
2224
2225impl<'a> AddAssign<&'a FragmentExtent> for FragmentExtent {
2226 fn add_assign(&mut self, other: &Self) {
2227 self.chars += other.chars;
2228 self.lines += &other.lines;
2229 }
2230}
2231
2232impl Default for FragmentExtent {
2233 fn default() -> Self {
2234 FragmentExtent {
2235 lines: Point::zero(),
2236 chars: 0,
2237 }
2238 }
2239}
2240
2241impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FragmentExtent {
2242 fn add_summary(&mut self, summary: &FragmentSummary) {
2243 self.chars += summary.text_summary.chars;
2244 self.lines += &summary.text_summary.lines;
2245 }
2246}
2247
2248impl<'a> sum_tree::Dimension<'a, FragmentSummary> for usize {
2249 fn add_summary(&mut self, summary: &FragmentSummary) {
2250 *self += summary.text_summary.chars;
2251 }
2252}
2253
2254impl sum_tree::Item for InsertionSplit {
2255 type Summary = InsertionSplitSummary;
2256
2257 fn summary(&self) -> Self::Summary {
2258 InsertionSplitSummary {
2259 extent: self.extent,
2260 }
2261 }
2262}
2263
2264impl sum_tree::Summary for InsertionSplitSummary {
2265 type Context = ();
2266
2267 fn add_summary(&mut self, other: &Self, _: &()) {
2268 self.extent += other.extent;
2269 }
2270}
2271
2272impl Default for InsertionSplitSummary {
2273 fn default() -> Self {
2274 InsertionSplitSummary { extent: 0 }
2275 }
2276}
2277
2278impl<'a> sum_tree::Dimension<'a, InsertionSplitSummary> for usize {
2279 fn add_summary(&mut self, summary: &InsertionSplitSummary) {
2280 *self += &summary.extent;
2281 }
2282}
2283
2284impl Operation {
2285 fn replica_id(&self) -> ReplicaId {
2286 self.lamport_timestamp().replica_id
2287 }
2288
2289 fn lamport_timestamp(&self) -> time::Lamport {
2290 match self {
2291 Operation::Edit {
2292 lamport_timestamp, ..
2293 } => *lamport_timestamp,
2294 Operation::Undo {
2295 lamport_timestamp, ..
2296 } => *lamport_timestamp,
2297 Operation::UpdateSelections {
2298 lamport_timestamp, ..
2299 } => *lamport_timestamp,
2300 }
2301 }
2302
2303 pub fn is_edit(&self) -> bool {
2304 match self {
2305 Operation::Edit { .. } => true,
2306 _ => false,
2307 }
2308 }
2309}
2310
2311impl operation_queue::Operation for Operation {
2312 fn timestamp(&self) -> time::Lamport {
2313 self.lamport_timestamp()
2314 }
2315}
2316
2317pub trait ToOffset {
2318 fn to_offset(&self, buffer: &Buffer) -> Result<usize>;
2319}
2320
2321impl ToOffset for Point {
2322 fn to_offset(&self, buffer: &Buffer) -> Result<usize> {
2323 let mut fragments_cursor = buffer.fragments.cursor::<Point, TextSummary>();
2324 fragments_cursor.seek(self, SeekBias::Left, &());
2325 fragments_cursor
2326 .item()
2327 .ok_or_else(|| anyhow!("point is out of range"))
2328 .map(|fragment| {
2329 let overshoot = fragment
2330 .offset_for_point(*self - fragments_cursor.start().lines)
2331 .unwrap();
2332 fragments_cursor.start().chars + overshoot
2333 })
2334 }
2335}
2336
2337impl ToOffset for usize {
2338 fn to_offset(&self, _: &Buffer) -> Result<usize> {
2339 Ok(*self)
2340 }
2341}
2342
2343impl ToOffset for Anchor {
2344 fn to_offset(&self, buffer: &Buffer) -> Result<usize> {
2345 Ok(buffer.summary_for_anchor(self)?.chars)
2346 }
2347}
2348
2349impl<'a> ToOffset for &'a Anchor {
2350 fn to_offset(&self, buffer: &Buffer) -> Result<usize> {
2351 Ok(buffer.summary_for_anchor(self)?.chars)
2352 }
2353}
2354
2355pub trait ToPoint {
2356 fn to_point(&self, buffer: &Buffer) -> Result<Point>;
2357}
2358
2359impl ToPoint for Anchor {
2360 fn to_point(&self, buffer: &Buffer) -> Result<Point> {
2361 Ok(buffer.summary_for_anchor(self)?.lines)
2362 }
2363}
2364
2365impl ToPoint for usize {
2366 fn to_point(&self, buffer: &Buffer) -> Result<Point> {
2367 let mut fragments_cursor = buffer.fragments.cursor::<usize, TextSummary>();
2368 fragments_cursor.seek(&self, SeekBias::Left, &());
2369 fragments_cursor
2370 .item()
2371 .ok_or_else(|| anyhow!("offset is out of range"))
2372 .map(|fragment| {
2373 let overshoot = fragment
2374 .point_for_offset(*self - &fragments_cursor.start().chars)
2375 .unwrap();
2376 fragments_cursor.start().lines + overshoot
2377 })
2378 }
2379}
2380
2381#[cfg(test)]
2382mod tests {
2383 use super::*;
2384 use crate::{test::temp_tree, worktree::Worktree};
2385 use cmp::Ordering;
2386 use gpui::App;
2387 use serde_json::json;
2388 use std::{
2389 cell::RefCell,
2390 collections::BTreeMap,
2391 fs,
2392 rc::Rc,
2393 sync::atomic::{self, AtomicUsize},
2394 };
2395
2396 #[gpui::test]
2397 fn test_edit(ctx: &mut gpui::MutableAppContext) {
2398 ctx.add_model(|ctx| {
2399 let mut buffer = Buffer::new(0, "abc", ctx);
2400 assert_eq!(buffer.text(), "abc");
2401 buffer.edit(vec![3..3], "def", None).unwrap();
2402 assert_eq!(buffer.text(), "abcdef");
2403 buffer.edit(vec![0..0], "ghi", None).unwrap();
2404 assert_eq!(buffer.text(), "ghiabcdef");
2405 buffer.edit(vec![5..5], "jkl", None).unwrap();
2406 assert_eq!(buffer.text(), "ghiabjklcdef");
2407 buffer.edit(vec![6..7], "", None).unwrap();
2408 assert_eq!(buffer.text(), "ghiabjlcdef");
2409 buffer.edit(vec![4..9], "mno", None).unwrap();
2410 assert_eq!(buffer.text(), "ghiamnoef");
2411 buffer
2412 });
2413 }
2414
2415 #[gpui::test]
2416 fn test_edit_events(app: &mut gpui::MutableAppContext) {
2417 let mut now = Instant::now();
2418 let buffer_1_events = Rc::new(RefCell::new(Vec::new()));
2419 let buffer_2_events = Rc::new(RefCell::new(Vec::new()));
2420
2421 let buffer1 = app.add_model(|ctx| Buffer::new(0, "abcdef", ctx));
2422 let buffer2 = app.add_model(|ctx| Buffer::new(1, "abcdef", ctx));
2423 let mut buffer_ops = Vec::new();
2424 buffer1.update(app, |buffer, ctx| {
2425 let buffer_1_events = buffer_1_events.clone();
2426 ctx.subscribe(&buffer1, move |_, event, _| {
2427 buffer_1_events.borrow_mut().push(event.clone())
2428 });
2429 let buffer_2_events = buffer_2_events.clone();
2430 ctx.subscribe(&buffer2, move |_, event, _| {
2431 buffer_2_events.borrow_mut().push(event.clone())
2432 });
2433
2434 // An edit emits an edited event, followed by a dirtied event,
2435 // since the buffer was previously in a clean state.
2436 let ops = buffer.edit(Some(2..4), "XYZ", Some(ctx)).unwrap();
2437 buffer_ops.extend_from_slice(&ops);
2438
2439 // An empty transaction does not emit any events.
2440 buffer.start_transaction(None).unwrap();
2441 buffer.end_transaction(None, Some(ctx)).unwrap();
2442
2443 // A transaction containing two edits emits one edited event.
2444 now += Duration::from_secs(1);
2445 buffer.start_transaction_at(None, now).unwrap();
2446 let ops = buffer.edit(Some(5..5), "u", Some(ctx)).unwrap();
2447 buffer_ops.extend_from_slice(&ops);
2448 let ops = buffer.edit(Some(6..6), "w", Some(ctx)).unwrap();
2449 buffer_ops.extend_from_slice(&ops);
2450 buffer.end_transaction_at(None, now, Some(ctx)).unwrap();
2451
2452 // Undoing a transaction emits one edited event.
2453 let ops = buffer.undo(Some(ctx));
2454 buffer_ops.extend_from_slice(&ops);
2455 });
2456
2457 // Incorporating a set of remote ops emits a single edited event,
2458 // followed by a dirtied event.
2459 buffer2.update(app, |buffer, ctx| {
2460 buffer.apply_ops(buffer_ops, Some(ctx)).unwrap();
2461 });
2462
2463 let buffer_1_events = buffer_1_events.borrow();
2464 assert_eq!(
2465 *buffer_1_events,
2466 vec![Event::Edited, Event::Dirtied, Event::Edited, Event::Edited]
2467 );
2468
2469 let buffer_2_events = buffer_2_events.borrow();
2470 assert_eq!(*buffer_2_events, vec![Event::Edited, Event::Dirtied]);
2471 }
2472
2473 #[gpui::test]
2474 fn test_random_edits(ctx: &mut gpui::MutableAppContext) {
2475 for seed in 0..100 {
2476 println!("{:?}", seed);
2477 let mut rng = &mut StdRng::seed_from_u64(seed);
2478
2479 let reference_string_len = rng.gen_range(0..3);
2480 let mut reference_string = RandomCharIter::new(&mut rng)
2481 .take(reference_string_len)
2482 .collect::<String>();
2483 ctx.add_model(|ctx| {
2484 let mut buffer = Buffer::new(0, reference_string.as_str(), ctx);
2485 let mut buffer_versions = Vec::new();
2486 for _i in 0..10 {
2487 let (old_ranges, new_text, _) = buffer.randomly_mutate(rng, None);
2488 for old_range in old_ranges.iter().rev() {
2489 reference_string = [
2490 &reference_string[0..old_range.start],
2491 new_text.as_str(),
2492 &reference_string[old_range.end..],
2493 ]
2494 .concat();
2495 }
2496 assert_eq!(buffer.text(), reference_string);
2497
2498 if rng.gen_bool(0.25) {
2499 buffer.randomly_undo_redo(rng);
2500 reference_string = buffer.text();
2501 }
2502
2503 {
2504 let line_lengths = line_lengths_in_range(&buffer, 0..buffer.len());
2505
2506 for (len, rows) in &line_lengths {
2507 for row in rows {
2508 assert_eq!(buffer.line_len(*row).unwrap(), *len);
2509 }
2510 }
2511
2512 let (longest_column, longest_rows) =
2513 line_lengths.iter().next_back().unwrap();
2514 let rightmost_point = buffer.rightmost_point();
2515 assert_eq!(rightmost_point.column, *longest_column);
2516 assert!(longest_rows.contains(&rightmost_point.row));
2517 }
2518
2519 for _ in 0..5 {
2520 let end = rng.gen_range(0..buffer.len() + 1);
2521 let start = rng.gen_range(0..end + 1);
2522
2523 let line_lengths = line_lengths_in_range(&buffer, start..end);
2524 let (longest_column, longest_rows) =
2525 line_lengths.iter().next_back().unwrap();
2526 let range_sum = buffer.text_summary_for_range(start..end);
2527 assert_eq!(range_sum.rightmost_point.column, *longest_column);
2528 assert!(longest_rows.contains(&range_sum.rightmost_point.row));
2529 let range_text = &buffer.text()[start..end];
2530 assert_eq!(range_sum.chars, range_text.chars().count());
2531 assert_eq!(range_sum.bytes, range_text.len());
2532 }
2533
2534 if rng.gen_bool(0.3) {
2535 buffer_versions.push(buffer.clone());
2536 }
2537 }
2538
2539 for mut old_buffer in buffer_versions {
2540 let mut delta = 0_isize;
2541 for Edit {
2542 old_range,
2543 new_range,
2544 } in buffer.edits_since(old_buffer.version.clone())
2545 {
2546 let old_len = old_range.end - old_range.start;
2547 let new_len = new_range.end - new_range.start;
2548 let old_start = (old_range.start as isize + delta) as usize;
2549 let new_text: String = buffer.text_for_range(new_range).unwrap().collect();
2550 old_buffer
2551 .edit(Some(old_start..old_start + old_len), new_text, None)
2552 .unwrap();
2553
2554 delta += new_len as isize - old_len as isize;
2555 }
2556 assert_eq!(old_buffer.text(), buffer.text());
2557 }
2558
2559 buffer
2560 });
2561 }
2562 }
2563
2564 #[gpui::test]
2565 fn test_line_len(ctx: &mut gpui::MutableAppContext) {
2566 ctx.add_model(|ctx| {
2567 let mut buffer = Buffer::new(0, "", ctx);
2568 buffer.edit(vec![0..0], "abcd\nefg\nhij", None).unwrap();
2569 buffer.edit(vec![12..12], "kl\nmno", None).unwrap();
2570 buffer.edit(vec![18..18], "\npqrs\n", None).unwrap();
2571 buffer.edit(vec![18..21], "\nPQ", None).unwrap();
2572
2573 assert_eq!(buffer.line_len(0).unwrap(), 4);
2574 assert_eq!(buffer.line_len(1).unwrap(), 3);
2575 assert_eq!(buffer.line_len(2).unwrap(), 5);
2576 assert_eq!(buffer.line_len(3).unwrap(), 3);
2577 assert_eq!(buffer.line_len(4).unwrap(), 4);
2578 assert_eq!(buffer.line_len(5).unwrap(), 0);
2579 assert!(buffer.line_len(6).is_err());
2580 buffer
2581 });
2582 }
2583
2584 #[gpui::test]
2585 fn test_rightmost_point(ctx: &mut gpui::MutableAppContext) {
2586 ctx.add_model(|ctx| {
2587 let mut buffer = Buffer::new(0, "", ctx);
2588 assert_eq!(buffer.rightmost_point().row, 0);
2589 buffer.edit(vec![0..0], "abcd\nefg\nhij", None).unwrap();
2590 assert_eq!(buffer.rightmost_point().row, 0);
2591 buffer.edit(vec![12..12], "kl\nmno", None).unwrap();
2592 assert_eq!(buffer.rightmost_point().row, 2);
2593 buffer.edit(vec![18..18], "\npqrs", None).unwrap();
2594 assert_eq!(buffer.rightmost_point().row, 2);
2595 buffer.edit(vec![10..12], "", None).unwrap();
2596 assert_eq!(buffer.rightmost_point().row, 0);
2597 buffer.edit(vec![24..24], "tuv", None).unwrap();
2598 assert_eq!(buffer.rightmost_point().row, 4);
2599 buffer
2600 });
2601 }
2602
2603 #[gpui::test]
2604 fn test_text_summary_for_range(ctx: &mut gpui::MutableAppContext) {
2605 ctx.add_model(|ctx| {
2606 let buffer = Buffer::new(0, "ab\nefg\nhklm\nnopqrs\ntuvwxyz", ctx);
2607 let text = Text::from(buffer.text());
2608 assert_eq!(
2609 buffer.text_summary_for_range(1..3),
2610 text.slice(1..3).summary()
2611 );
2612 assert_eq!(
2613 buffer.text_summary_for_range(1..12),
2614 text.slice(1..12).summary()
2615 );
2616 assert_eq!(
2617 buffer.text_summary_for_range(0..20),
2618 text.slice(0..20).summary()
2619 );
2620 assert_eq!(
2621 buffer.text_summary_for_range(0..22),
2622 text.slice(0..22).summary()
2623 );
2624 assert_eq!(
2625 buffer.text_summary_for_range(7..22),
2626 text.slice(7..22).summary()
2627 );
2628 buffer
2629 });
2630 }
2631
2632 #[gpui::test]
2633 fn test_chars_at(ctx: &mut gpui::MutableAppContext) {
2634 ctx.add_model(|ctx| {
2635 let mut buffer = Buffer::new(0, "", ctx);
2636 buffer.edit(vec![0..0], "abcd\nefgh\nij", None).unwrap();
2637 buffer.edit(vec![12..12], "kl\nmno", None).unwrap();
2638 buffer.edit(vec![18..18], "\npqrs", None).unwrap();
2639 buffer.edit(vec![18..21], "\nPQ", None).unwrap();
2640
2641 let chars = buffer.chars_at(Point::new(0, 0)).unwrap();
2642 assert_eq!(chars.collect::<String>(), "abcd\nefgh\nijkl\nmno\nPQrs");
2643
2644 let chars = buffer.chars_at(Point::new(1, 0)).unwrap();
2645 assert_eq!(chars.collect::<String>(), "efgh\nijkl\nmno\nPQrs");
2646
2647 let chars = buffer.chars_at(Point::new(2, 0)).unwrap();
2648 assert_eq!(chars.collect::<String>(), "ijkl\nmno\nPQrs");
2649
2650 let chars = buffer.chars_at(Point::new(3, 0)).unwrap();
2651 assert_eq!(chars.collect::<String>(), "mno\nPQrs");
2652
2653 let chars = buffer.chars_at(Point::new(4, 0)).unwrap();
2654 assert_eq!(chars.collect::<String>(), "PQrs");
2655
2656 // Regression test:
2657 let mut buffer = Buffer::new(0, "", ctx);
2658 buffer.edit(vec![0..0], "[workspace]\nmembers = [\n \"xray_core\",\n \"xray_server\",\n \"xray_cli\",\n \"xray_wasm\",\n]\n", None).unwrap();
2659 buffer.edit(vec![60..60], "\n", None).unwrap();
2660
2661 let chars = buffer.chars_at(Point::new(6, 0)).unwrap();
2662 assert_eq!(chars.collect::<String>(), " \"xray_wasm\",\n]\n");
2663
2664 buffer
2665 });
2666 }
2667
2668 // #[test]
2669 // fn test_point_for_offset() -> Result<()> {
2670 // let text = Text::from("abc\ndefgh\nijklm\nopq");
2671 // assert_eq!(text.point_for_offset(0)?, Point { row: 0, column: 0 });
2672 // assert_eq!(text.point_for_offset(1)?, Point { row: 0, column: 1 });
2673 // assert_eq!(text.point_for_offset(2)?, Point { row: 0, column: 2 });
2674 // assert_eq!(text.point_for_offset(3)?, Point { row: 0, column: 3 });
2675 // assert_eq!(text.point_for_offset(4)?, Point { row: 1, column: 0 });
2676 // assert_eq!(text.point_for_offset(5)?, Point { row: 1, column: 1 });
2677 // assert_eq!(text.point_for_offset(9)?, Point { row: 1, column: 5 });
2678 // assert_eq!(text.point_for_offset(10)?, Point { row: 2, column: 0 });
2679 // assert_eq!(text.point_for_offset(14)?, Point { row: 2, column: 4 });
2680 // assert_eq!(text.point_for_offset(15)?, Point { row: 2, column: 5 });
2681 // assert_eq!(text.point_for_offset(16)?, Point { row: 3, column: 0 });
2682 // assert_eq!(text.point_for_offset(17)?, Point { row: 3, column: 1 });
2683 // assert_eq!(text.point_for_offset(19)?, Point { row: 3, column: 3 });
2684 // assert!(text.point_for_offset(20).is_err());
2685 //
2686 // let text = Text::from("abc");
2687 // assert_eq!(text.point_for_offset(0)?, Point { row: 0, column: 0 });
2688 // assert_eq!(text.point_for_offset(1)?, Point { row: 0, column: 1 });
2689 // assert_eq!(text.point_for_offset(2)?, Point { row: 0, column: 2 });
2690 // assert_eq!(text.point_for_offset(3)?, Point { row: 0, column: 3 });
2691 // assert!(text.point_for_offset(4).is_err());
2692 // Ok(())
2693 // }
2694
2695 // #[test]
2696 // fn test_offset_for_point() -> Result<()> {
2697 // let text = Text::from("abc\ndefgh");
2698 // assert_eq!(text.offset_for_point(Point { row: 0, column: 0 })?, 0);
2699 // assert_eq!(text.offset_for_point(Point { row: 0, column: 1 })?, 1);
2700 // assert_eq!(text.offset_for_point(Point { row: 0, column: 2 })?, 2);
2701 // assert_eq!(text.offset_for_point(Point { row: 0, column: 3 })?, 3);
2702 // assert!(text.offset_for_point(Point { row: 0, column: 4 }).is_err());
2703 // assert_eq!(text.offset_for_point(Point { row: 1, column: 0 })?, 4);
2704 // assert_eq!(text.offset_for_point(Point { row: 1, column: 1 })?, 5);
2705 // assert_eq!(text.offset_for_point(Point { row: 1, column: 5 })?, 9);
2706 // assert!(text.offset_for_point(Point { row: 1, column: 6 }).is_err());
2707 //
2708 // let text = Text::from("abc");
2709 // assert_eq!(text.offset_for_point(Point { row: 0, column: 0 })?, 0);
2710 // assert_eq!(text.offset_for_point(Point { row: 0, column: 1 })?, 1);
2711 // assert_eq!(text.offset_for_point(Point { row: 0, column: 2 })?, 2);
2712 // assert_eq!(text.offset_for_point(Point { row: 0, column: 3 })?, 3);
2713 // assert!(text.offset_for_point(Point { row: 0, column: 4 }).is_err());
2714 // Ok(())
2715 // }
2716
2717 // #[test]
2718 // fn test_longest_row_in_range() -> Result<()> {
2719 // for seed in 0..100 {
2720 // println!("{:?}", seed);
2721 // let mut rng = &mut StdRng::seed_from_u64(seed);
2722 // let string_len = rng.gen_range(1, 10);
2723 // let string = RandomCharIter(&mut rng)
2724 // .take(string_len)
2725 // .collect::<String>();
2726 // let text = Text::from(string.as_ref());
2727 //
2728 // for _i in 0..10 {
2729 // let end = rng.gen_range(1, string.len() + 1);
2730 // let start = rng.gen_range(0, end);
2731 //
2732 // let mut cur_row = string[0..start].chars().filter(|c| *c == '\n').count() as u32;
2733 // let mut cur_row_len = 0;
2734 // let mut expected_longest_row = cur_row;
2735 // let mut expected_longest_row_len = cur_row_len;
2736 // for ch in string[start..end].chars() {
2737 // if ch == '\n' {
2738 // if cur_row_len > expected_longest_row_len {
2739 // expected_longest_row = cur_row;
2740 // expected_longest_row_len = cur_row_len;
2741 // }
2742 // cur_row += 1;
2743 // cur_row_len = 0;
2744 // } else {
2745 // cur_row_len += 1;
2746 // }
2747 // }
2748 // if cur_row_len > expected_longest_row_len {
2749 // expected_longest_row = cur_row;
2750 // expected_longest_row_len = cur_row_len;
2751 // }
2752 //
2753 // assert_eq!(
2754 // text.longest_row_in_range(start..end)?,
2755 // (expected_longest_row, expected_longest_row_len)
2756 // );
2757 // }
2758 // }
2759 // Ok(())
2760 // }
2761
2762 #[test]
2763 fn test_fragment_ids() {
2764 for seed in 0..10 {
2765 let rng = &mut StdRng::seed_from_u64(seed);
2766
2767 let mut ids = vec![FragmentId(Arc::from([0])), FragmentId(Arc::from([4]))];
2768 for _i in 0..100 {
2769 let index = rng.gen_range(1..ids.len());
2770
2771 let left = ids[index - 1].clone();
2772 let right = ids[index].clone();
2773 ids.insert(index, FragmentId::between_with_max(&left, &right, 4));
2774
2775 let mut sorted_ids = ids.clone();
2776 sorted_ids.sort();
2777 assert_eq!(ids, sorted_ids);
2778 }
2779 }
2780 }
2781
2782 #[gpui::test]
2783 fn test_anchors(ctx: &mut gpui::MutableAppContext) {
2784 ctx.add_model(|ctx| {
2785 let mut buffer = Buffer::new(0, "", ctx);
2786 buffer.edit(vec![0..0], "abc", None).unwrap();
2787 let left_anchor = buffer.anchor_before(2).unwrap();
2788 let right_anchor = buffer.anchor_after(2).unwrap();
2789
2790 buffer.edit(vec![1..1], "def\n", None).unwrap();
2791 assert_eq!(buffer.text(), "adef\nbc");
2792 assert_eq!(left_anchor.to_offset(&buffer).unwrap(), 6);
2793 assert_eq!(right_anchor.to_offset(&buffer).unwrap(), 6);
2794 assert_eq!(
2795 left_anchor.to_point(&buffer).unwrap(),
2796 Point { row: 1, column: 1 }
2797 );
2798 assert_eq!(
2799 right_anchor.to_point(&buffer).unwrap(),
2800 Point { row: 1, column: 1 }
2801 );
2802
2803 buffer.edit(vec![2..3], "", None).unwrap();
2804 assert_eq!(buffer.text(), "adf\nbc");
2805 assert_eq!(left_anchor.to_offset(&buffer).unwrap(), 5);
2806 assert_eq!(right_anchor.to_offset(&buffer).unwrap(), 5);
2807 assert_eq!(
2808 left_anchor.to_point(&buffer).unwrap(),
2809 Point { row: 1, column: 1 }
2810 );
2811 assert_eq!(
2812 right_anchor.to_point(&buffer).unwrap(),
2813 Point { row: 1, column: 1 }
2814 );
2815
2816 buffer.edit(vec![5..5], "ghi\n", None).unwrap();
2817 assert_eq!(buffer.text(), "adf\nbghi\nc");
2818 assert_eq!(left_anchor.to_offset(&buffer).unwrap(), 5);
2819 assert_eq!(right_anchor.to_offset(&buffer).unwrap(), 9);
2820 assert_eq!(
2821 left_anchor.to_point(&buffer).unwrap(),
2822 Point { row: 1, column: 1 }
2823 );
2824 assert_eq!(
2825 right_anchor.to_point(&buffer).unwrap(),
2826 Point { row: 2, column: 0 }
2827 );
2828
2829 buffer.edit(vec![7..9], "", None).unwrap();
2830 assert_eq!(buffer.text(), "adf\nbghc");
2831 assert_eq!(left_anchor.to_offset(&buffer).unwrap(), 5);
2832 assert_eq!(right_anchor.to_offset(&buffer).unwrap(), 7);
2833 assert_eq!(
2834 left_anchor.to_point(&buffer).unwrap(),
2835 Point { row: 1, column: 1 },
2836 );
2837 assert_eq!(
2838 right_anchor.to_point(&buffer).unwrap(),
2839 Point { row: 1, column: 3 }
2840 );
2841
2842 // Ensure anchoring to a point is equivalent to anchoring to an offset.
2843 assert_eq!(
2844 buffer.anchor_before(Point { row: 0, column: 0 }).unwrap(),
2845 buffer.anchor_before(0).unwrap()
2846 );
2847 assert_eq!(
2848 buffer.anchor_before(Point { row: 0, column: 1 }).unwrap(),
2849 buffer.anchor_before(1).unwrap()
2850 );
2851 assert_eq!(
2852 buffer.anchor_before(Point { row: 0, column: 2 }).unwrap(),
2853 buffer.anchor_before(2).unwrap()
2854 );
2855 assert_eq!(
2856 buffer.anchor_before(Point { row: 0, column: 3 }).unwrap(),
2857 buffer.anchor_before(3).unwrap()
2858 );
2859 assert_eq!(
2860 buffer.anchor_before(Point { row: 1, column: 0 }).unwrap(),
2861 buffer.anchor_before(4).unwrap()
2862 );
2863 assert_eq!(
2864 buffer.anchor_before(Point { row: 1, column: 1 }).unwrap(),
2865 buffer.anchor_before(5).unwrap()
2866 );
2867 assert_eq!(
2868 buffer.anchor_before(Point { row: 1, column: 2 }).unwrap(),
2869 buffer.anchor_before(6).unwrap()
2870 );
2871 assert_eq!(
2872 buffer.anchor_before(Point { row: 1, column: 3 }).unwrap(),
2873 buffer.anchor_before(7).unwrap()
2874 );
2875 assert_eq!(
2876 buffer.anchor_before(Point { row: 1, column: 4 }).unwrap(),
2877 buffer.anchor_before(8).unwrap()
2878 );
2879
2880 // Comparison between anchors.
2881 let anchor_at_offset_0 = buffer.anchor_before(0).unwrap();
2882 let anchor_at_offset_1 = buffer.anchor_before(1).unwrap();
2883 let anchor_at_offset_2 = buffer.anchor_before(2).unwrap();
2884
2885 assert_eq!(
2886 anchor_at_offset_0
2887 .cmp(&anchor_at_offset_0, &buffer)
2888 .unwrap(),
2889 Ordering::Equal
2890 );
2891 assert_eq!(
2892 anchor_at_offset_1
2893 .cmp(&anchor_at_offset_1, &buffer)
2894 .unwrap(),
2895 Ordering::Equal
2896 );
2897 assert_eq!(
2898 anchor_at_offset_2
2899 .cmp(&anchor_at_offset_2, &buffer)
2900 .unwrap(),
2901 Ordering::Equal
2902 );
2903
2904 assert_eq!(
2905 anchor_at_offset_0
2906 .cmp(&anchor_at_offset_1, &buffer)
2907 .unwrap(),
2908 Ordering::Less
2909 );
2910 assert_eq!(
2911 anchor_at_offset_1
2912 .cmp(&anchor_at_offset_2, &buffer)
2913 .unwrap(),
2914 Ordering::Less
2915 );
2916 assert_eq!(
2917 anchor_at_offset_0
2918 .cmp(&anchor_at_offset_2, &buffer)
2919 .unwrap(),
2920 Ordering::Less
2921 );
2922
2923 assert_eq!(
2924 anchor_at_offset_1
2925 .cmp(&anchor_at_offset_0, &buffer)
2926 .unwrap(),
2927 Ordering::Greater
2928 );
2929 assert_eq!(
2930 anchor_at_offset_2
2931 .cmp(&anchor_at_offset_1, &buffer)
2932 .unwrap(),
2933 Ordering::Greater
2934 );
2935 assert_eq!(
2936 anchor_at_offset_2
2937 .cmp(&anchor_at_offset_0, &buffer)
2938 .unwrap(),
2939 Ordering::Greater
2940 );
2941 buffer
2942 });
2943 }
2944
2945 #[gpui::test]
2946 fn test_anchors_at_start_and_end(ctx: &mut gpui::MutableAppContext) {
2947 ctx.add_model(|ctx| {
2948 let mut buffer = Buffer::new(0, "", ctx);
2949 let before_start_anchor = buffer.anchor_before(0).unwrap();
2950 let after_end_anchor = buffer.anchor_after(0).unwrap();
2951
2952 buffer.edit(vec![0..0], "abc", None).unwrap();
2953 assert_eq!(buffer.text(), "abc");
2954 assert_eq!(before_start_anchor.to_offset(&buffer).unwrap(), 0);
2955 assert_eq!(after_end_anchor.to_offset(&buffer).unwrap(), 3);
2956
2957 let after_start_anchor = buffer.anchor_after(0).unwrap();
2958 let before_end_anchor = buffer.anchor_before(3).unwrap();
2959
2960 buffer.edit(vec![3..3], "def", None).unwrap();
2961 buffer.edit(vec![0..0], "ghi", None).unwrap();
2962 assert_eq!(buffer.text(), "ghiabcdef");
2963 assert_eq!(before_start_anchor.to_offset(&buffer).unwrap(), 0);
2964 assert_eq!(after_start_anchor.to_offset(&buffer).unwrap(), 3);
2965 assert_eq!(before_end_anchor.to_offset(&buffer).unwrap(), 6);
2966 assert_eq!(after_end_anchor.to_offset(&buffer).unwrap(), 9);
2967 buffer
2968 });
2969 }
2970
2971 #[test]
2972 fn test_is_dirty() {
2973 use crate::worktree::WorktreeHandle;
2974
2975 App::test_async((), |mut app| async move {
2976 let dir = temp_tree(json!({
2977 "file1": "",
2978 "file2": "",
2979 "file3": "",
2980 }));
2981 let tree = app.add_model(|ctx| Worktree::new(dir.path(), ctx));
2982 app.read(|ctx| tree.read(ctx).scan_complete()).await;
2983
2984 let file1 = app.read(|ctx| tree.file("file1", ctx));
2985 let buffer1 = app.add_model(|ctx| {
2986 Buffer::from_history(0, History::new("abc".into()), Some(file1), ctx)
2987 });
2988 let events = Rc::new(RefCell::new(Vec::new()));
2989
2990 // initially, the buffer isn't dirty.
2991 buffer1.update(&mut app, |buffer, ctx| {
2992 ctx.subscribe(&buffer1, {
2993 let events = events.clone();
2994 move |_, event, _| events.borrow_mut().push(event.clone())
2995 });
2996
2997 assert!(!buffer.is_dirty());
2998 assert!(events.borrow().is_empty());
2999
3000 buffer.edit(vec![1..2], "", Some(ctx)).unwrap();
3001 });
3002
3003 // after the first edit, the buffer is dirty, and emits a dirtied event.
3004 buffer1.update(&mut app, |buffer, ctx| {
3005 assert!(buffer.text() == "ac");
3006 assert!(buffer.is_dirty());
3007 assert_eq!(*events.borrow(), &[Event::Edited, Event::Dirtied]);
3008 events.borrow_mut().clear();
3009
3010 buffer.did_save(buffer.version(), None, ctx);
3011 });
3012
3013 // after saving, the buffer is not dirty, and emits a saved event.
3014 buffer1.update(&mut app, |buffer, ctx| {
3015 assert!(!buffer.is_dirty());
3016 assert_eq!(*events.borrow(), &[Event::Saved]);
3017 events.borrow_mut().clear();
3018
3019 buffer.edit(vec![1..1], "B", Some(ctx)).unwrap();
3020 buffer.edit(vec![2..2], "D", Some(ctx)).unwrap();
3021 });
3022
3023 // after editing again, the buffer is dirty, and emits another dirty event.
3024 buffer1.update(&mut app, |buffer, ctx| {
3025 assert!(buffer.text() == "aBDc");
3026 assert!(buffer.is_dirty());
3027 assert_eq!(
3028 *events.borrow(),
3029 &[Event::Edited, Event::Dirtied, Event::Edited],
3030 );
3031 events.borrow_mut().clear();
3032
3033 // TODO - currently, after restoring the buffer to its
3034 // previously-saved state, the is still considered dirty.
3035 buffer.edit(vec![1..3], "", Some(ctx)).unwrap();
3036 assert!(buffer.text() == "ac");
3037 assert!(buffer.is_dirty());
3038 });
3039
3040 assert_eq!(*events.borrow(), &[Event::Edited]);
3041
3042 // When a file is deleted, the buffer is considered dirty.
3043 let events = Rc::new(RefCell::new(Vec::new()));
3044 let file2 = app.read(|ctx| tree.file("file2", ctx));
3045 let buffer2 = app.add_model(|ctx: &mut ModelContext<Buffer>| {
3046 ctx.subscribe(&ctx.handle(), {
3047 let events = events.clone();
3048 move |_, event, _| events.borrow_mut().push(event.clone())
3049 });
3050
3051 Buffer::from_history(0, History::new("abc".into()), Some(file2), ctx)
3052 });
3053
3054 tree.flush_fs_events(&app).await;
3055 fs::remove_file(dir.path().join("file2")).unwrap();
3056 tree.update(&mut app, |tree, ctx| tree.next_scan_complete(ctx))
3057 .await;
3058 assert_eq!(
3059 *events.borrow(),
3060 &[Event::Dirtied, Event::FileHandleChanged]
3061 );
3062 app.read(|ctx| assert!(buffer2.read(ctx).is_dirty()));
3063
3064 // When a file is already dirty when deleted, we don't emit a Dirtied event.
3065 let events = Rc::new(RefCell::new(Vec::new()));
3066 let file3 = app.read(|ctx| tree.file("file3", ctx));
3067 let buffer3 = app.add_model(|ctx: &mut ModelContext<Buffer>| {
3068 ctx.subscribe(&ctx.handle(), {
3069 let events = events.clone();
3070 move |_, event, _| events.borrow_mut().push(event.clone())
3071 });
3072
3073 Buffer::from_history(0, History::new("abc".into()), Some(file3), ctx)
3074 });
3075
3076 tree.flush_fs_events(&app).await;
3077 buffer3.update(&mut app, |buffer, ctx| {
3078 buffer.edit(Some(0..0), "x", Some(ctx)).unwrap();
3079 });
3080 events.borrow_mut().clear();
3081 fs::remove_file(dir.path().join("file3")).unwrap();
3082 tree.update(&mut app, |tree, ctx| tree.next_scan_complete(ctx))
3083 .await;
3084 assert_eq!(*events.borrow(), &[Event::FileHandleChanged]);
3085 app.read(|ctx| assert!(buffer3.read(ctx).is_dirty()));
3086 });
3087 }
3088
3089 #[gpui::test]
3090 fn test_undo_redo(app: &mut gpui::MutableAppContext) {
3091 app.add_model(|ctx| {
3092 let mut buffer = Buffer::new(0, "1234", ctx);
3093
3094 let edit1 = buffer.edit(vec![1..1], "abx", None).unwrap();
3095 let edit2 = buffer.edit(vec![3..4], "yzef", None).unwrap();
3096 let edit3 = buffer.edit(vec![3..5], "cd", None).unwrap();
3097 assert_eq!(buffer.text(), "1abcdef234");
3098
3099 buffer.undo_or_redo(edit1[0].edit_id().unwrap()).unwrap();
3100 assert_eq!(buffer.text(), "1cdef234");
3101 buffer.undo_or_redo(edit1[0].edit_id().unwrap()).unwrap();
3102 assert_eq!(buffer.text(), "1abcdef234");
3103
3104 buffer.undo_or_redo(edit2[0].edit_id().unwrap()).unwrap();
3105 assert_eq!(buffer.text(), "1abcdx234");
3106 buffer.undo_or_redo(edit3[0].edit_id().unwrap()).unwrap();
3107 assert_eq!(buffer.text(), "1abx234");
3108 buffer.undo_or_redo(edit2[0].edit_id().unwrap()).unwrap();
3109 assert_eq!(buffer.text(), "1abyzef234");
3110 buffer.undo_or_redo(edit3[0].edit_id().unwrap()).unwrap();
3111 assert_eq!(buffer.text(), "1abcdef234");
3112
3113 buffer.undo_or_redo(edit3[0].edit_id().unwrap()).unwrap();
3114 assert_eq!(buffer.text(), "1abyzef234");
3115 buffer.undo_or_redo(edit1[0].edit_id().unwrap()).unwrap();
3116 assert_eq!(buffer.text(), "1yzef234");
3117 buffer.undo_or_redo(edit2[0].edit_id().unwrap()).unwrap();
3118 assert_eq!(buffer.text(), "1234");
3119
3120 buffer
3121 });
3122 }
3123
3124 #[gpui::test]
3125 fn test_history(app: &mut gpui::MutableAppContext) {
3126 app.add_model(|ctx| {
3127 let mut now = Instant::now();
3128 let mut buffer = Buffer::new(0, "123456", ctx);
3129
3130 let (set_id, _) =
3131 buffer.add_selection_set(buffer.selections_from_ranges(vec![4..4]).unwrap(), None);
3132 buffer.start_transaction_at(Some(set_id), now).unwrap();
3133 buffer.edit(vec![2..4], "cd", None).unwrap();
3134 buffer.end_transaction_at(Some(set_id), now, None).unwrap();
3135 assert_eq!(buffer.text(), "12cd56");
3136 assert_eq!(buffer.selection_ranges(set_id).unwrap(), vec![4..4]);
3137
3138 buffer.start_transaction_at(Some(set_id), now).unwrap();
3139 buffer
3140 .update_selection_set(
3141 set_id,
3142 buffer.selections_from_ranges(vec![1..3]).unwrap(),
3143 None,
3144 )
3145 .unwrap();
3146 buffer.edit(vec![4..5], "e", None).unwrap();
3147 buffer.end_transaction_at(Some(set_id), now, None).unwrap();
3148 assert_eq!(buffer.text(), "12cde6");
3149 assert_eq!(buffer.selection_ranges(set_id).unwrap(), vec![1..3]);
3150
3151 now += UNDO_GROUP_INTERVAL + Duration::from_millis(1);
3152 buffer.start_transaction_at(Some(set_id), now).unwrap();
3153 buffer
3154 .update_selection_set(
3155 set_id,
3156 buffer.selections_from_ranges(vec![2..2]).unwrap(),
3157 None,
3158 )
3159 .unwrap();
3160 buffer.edit(vec![0..1], "a", None).unwrap();
3161 buffer.edit(vec![1..1], "b", None).unwrap();
3162 buffer.end_transaction_at(Some(set_id), now, None).unwrap();
3163 assert_eq!(buffer.text(), "ab2cde6");
3164 assert_eq!(buffer.selection_ranges(set_id).unwrap(), vec![3..3]);
3165
3166 // Last transaction happened past the group interval, undo it on its
3167 // own.
3168 buffer.undo(None);
3169 assert_eq!(buffer.text(), "12cde6");
3170 assert_eq!(buffer.selection_ranges(set_id).unwrap(), vec![1..3]);
3171
3172 // First two transactions happened within the group interval, undo them
3173 // together.
3174 buffer.undo(None);
3175 assert_eq!(buffer.text(), "123456");
3176 assert_eq!(buffer.selection_ranges(set_id).unwrap(), vec![4..4]);
3177
3178 // Redo the first two transactions together.
3179 buffer.redo(None);
3180 assert_eq!(buffer.text(), "12cde6");
3181 assert_eq!(buffer.selection_ranges(set_id).unwrap(), vec![1..3]);
3182
3183 // Redo the last transaction on its own.
3184 buffer.redo(None);
3185 assert_eq!(buffer.text(), "ab2cde6");
3186 assert_eq!(buffer.selection_ranges(set_id).unwrap(), vec![3..3]);
3187
3188 buffer
3189 });
3190 }
3191
3192 #[gpui::test]
3193 fn test_random_concurrent_edits(ctx: &mut gpui::MutableAppContext) {
3194 use crate::test::Network;
3195
3196 const PEERS: usize = 5;
3197
3198 for seed in 0..100 {
3199 println!("{:?}", seed);
3200 let mut rng = &mut StdRng::seed_from_u64(seed);
3201
3202 let base_text_len = rng.gen_range(0..10);
3203 let base_text = RandomCharIter::new(&mut rng)
3204 .take(base_text_len)
3205 .collect::<String>();
3206 let mut replica_ids = Vec::new();
3207 let mut buffers = Vec::new();
3208 let mut network = Network::new();
3209 for i in 0..PEERS {
3210 let buffer =
3211 ctx.add_model(|ctx| Buffer::new(i as ReplicaId, base_text.as_str(), ctx));
3212 buffers.push(buffer);
3213 replica_ids.push(i as u16);
3214 network.add_peer(i as u16);
3215 }
3216
3217 let mut mutation_count = 10;
3218 loop {
3219 let replica_index = rng.gen_range(0..PEERS);
3220 let replica_id = replica_ids[replica_index];
3221 buffers[replica_index].update(ctx, |buffer, _| match rng.gen_range(0..=100) {
3222 0..=50 if mutation_count != 0 => {
3223 let (_, _, ops) = buffer.randomly_mutate(&mut rng, None);
3224 network.broadcast(replica_id, ops, &mut rng);
3225 mutation_count -= 1;
3226 }
3227 51..=70 if mutation_count != 0 => {
3228 let ops = buffer.randomly_undo_redo(&mut rng);
3229 network.broadcast(replica_id, ops, &mut rng);
3230 mutation_count -= 1;
3231 }
3232 71..=100 if network.has_unreceived(replica_id) => {
3233 buffer
3234 .apply_ops(network.receive(replica_id, &mut rng), None)
3235 .unwrap();
3236 }
3237 _ => {}
3238 });
3239
3240 if mutation_count == 0 && network.is_idle() {
3241 break;
3242 }
3243 }
3244
3245 let first_buffer = buffers[0].read(ctx);
3246 for buffer in &buffers[1..] {
3247 let buffer = buffer.read(ctx);
3248 assert_eq!(buffer.text(), first_buffer.text());
3249 assert_eq!(
3250 buffer.all_selections().collect::<HashMap<_, _>>(),
3251 first_buffer.all_selections().collect::<HashMap<_, _>>()
3252 );
3253 assert_eq!(
3254 buffer.all_selection_ranges().collect::<HashMap<_, _>>(),
3255 first_buffer
3256 .all_selection_ranges()
3257 .collect::<HashMap<_, _>>()
3258 );
3259 }
3260 }
3261 }
3262
3263 impl Buffer {
3264 pub fn randomly_mutate<T>(
3265 &mut self,
3266 rng: &mut T,
3267 mut ctx: Option<&mut ModelContext<Self>>,
3268 ) -> (Vec<Range<usize>>, String, Vec<Operation>)
3269 where
3270 T: Rng,
3271 {
3272 // Randomly edit
3273 let (old_ranges, new_text, mut operations) =
3274 self.randomly_edit(rng, 5, ctx.as_deref_mut());
3275
3276 // Randomly add, remove or mutate selection sets.
3277 let replica_selection_sets = &self
3278 .all_selections()
3279 .map(|(set_id, _)| *set_id)
3280 .filter(|set_id| self.replica_id == set_id.replica_id)
3281 .collect::<Vec<_>>();
3282 let set_id = replica_selection_sets.choose(rng);
3283 if set_id.is_some() && rng.gen_bool(1.0 / 6.0) {
3284 let op = self.remove_selection_set(*set_id.unwrap(), None).unwrap();
3285 operations.push(op);
3286 } else {
3287 let mut ranges = Vec::new();
3288 for _ in 0..5 {
3289 let start = rng.gen_range(0..self.len() + 1);
3290 let end = rng.gen_range(0..self.len() + 1);
3291 ranges.push(start..end);
3292 }
3293 let new_selections = self.selections_from_ranges(ranges).unwrap();
3294
3295 let op = if set_id.is_none() || rng.gen_bool(1.0 / 5.0) {
3296 self.add_selection_set(new_selections, None).1
3297 } else {
3298 self.update_selection_set(*set_id.unwrap(), new_selections, None)
3299 .unwrap()
3300 };
3301 operations.push(op);
3302 }
3303
3304 (old_ranges, new_text, operations)
3305 }
3306
3307 pub fn randomly_undo_redo(&mut self, rng: &mut impl Rng) -> Vec<Operation> {
3308 let mut ops = Vec::new();
3309 for _ in 0..rng.gen_range(1..5) {
3310 if let Some(edit_id) = self.history.ops.keys().choose(rng).copied() {
3311 ops.push(self.undo_or_redo(edit_id).unwrap());
3312 }
3313 }
3314 ops
3315 }
3316
3317 fn selections_from_ranges<I>(&self, ranges: I) -> Result<Vec<Selection>>
3318 where
3319 I: IntoIterator<Item = Range<usize>>,
3320 {
3321 static NEXT_SELECTION_ID: AtomicUsize = AtomicUsize::new(0);
3322
3323 let mut ranges = ranges.into_iter().collect::<Vec<_>>();
3324 ranges.sort_unstable_by_key(|range| range.start);
3325
3326 let mut selections = Vec::with_capacity(ranges.len());
3327 for range in ranges {
3328 if range.start > range.end {
3329 selections.push(Selection {
3330 id: NEXT_SELECTION_ID.fetch_add(1, atomic::Ordering::SeqCst),
3331 start: self.anchor_before(range.end)?,
3332 end: self.anchor_before(range.start)?,
3333 reversed: true,
3334 goal: SelectionGoal::None,
3335 });
3336 } else {
3337 selections.push(Selection {
3338 id: NEXT_SELECTION_ID.fetch_add(1, atomic::Ordering::SeqCst),
3339 start: self.anchor_after(range.start)?,
3340 end: self.anchor_before(range.end)?,
3341 reversed: false,
3342 goal: SelectionGoal::None,
3343 });
3344 }
3345 }
3346 Ok(selections)
3347 }
3348
3349 pub fn selection_ranges<'a>(&'a self, set_id: SelectionSetId) -> Result<Vec<Range<usize>>> {
3350 Ok(self
3351 .selections(set_id)?
3352 .iter()
3353 .map(move |selection| {
3354 let start = selection.start.to_offset(self).unwrap();
3355 let end = selection.end.to_offset(self).unwrap();
3356 if selection.reversed {
3357 end..start
3358 } else {
3359 start..end
3360 }
3361 })
3362 .collect())
3363 }
3364
3365 pub fn all_selections(&self) -> impl Iterator<Item = (&SelectionSetId, &[Selection])> {
3366 self.selections
3367 .iter()
3368 .map(|(set_id, selections)| (set_id, selections.as_ref()))
3369 }
3370
3371 pub fn all_selection_ranges<'a>(
3372 &'a self,
3373 ) -> impl 'a + Iterator<Item = (SelectionSetId, Vec<Range<usize>>)> {
3374 self.selections
3375 .keys()
3376 .map(move |set_id| (*set_id, self.selection_ranges(*set_id).unwrap()))
3377 }
3378 }
3379
3380 impl Operation {
3381 fn edit_id(&self) -> Option<time::Local> {
3382 match self {
3383 Operation::Edit { edit, .. } => Some(edit.id),
3384 Operation::Undo { undo, .. } => Some(undo.edit_id),
3385 Operation::UpdateSelections { .. } => None,
3386 }
3387 }
3388 }
3389
3390 fn line_lengths_in_range(buffer: &Buffer, range: Range<usize>) -> BTreeMap<u32, HashSet<u32>> {
3391 let mut lengths = BTreeMap::new();
3392 for (row, line) in buffer.text()[range].lines().enumerate() {
3393 lengths
3394 .entry(line.len() as u32)
3395 .or_insert(HashSet::default())
3396 .insert(row as u32);
3397 }
3398 if lengths.is_empty() {
3399 let mut rows = HashSet::default();
3400 rows.insert(0);
3401 lengths.insert(0, rows);
3402 }
3403 lengths
3404 }
3405}