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