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