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