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
59#[derive(Clone, Default, Debug)]
60struct UndoMap(HashMap<time::Local, Vec<UndoOperation>>);
61
62impl UndoMap {
63 fn insert(&mut self, undo: UndoOperation) {
64 self.0.entry(undo.edit_id).or_default().push(undo);
65 }
66
67 fn is_undone(&self, edit_id: time::Local) -> bool {
68 self.undo_count(edit_id) % 2 == 1
69 }
70
71 fn was_undone(&self, edit_id: time::Local, version: &time::Global) -> bool {
72 let undo_count = self
73 .0
74 .get(&edit_id)
75 .unwrap_or(&Vec::new())
76 .iter()
77 .filter(|undo| version.observed(undo.id))
78 .map(|undo| undo.count)
79 .max()
80 .unwrap_or(0);
81 undo_count % 2 == 1
82 }
83
84 fn undo_count(&self, edit_id: time::Local) -> u32 {
85 self.0
86 .get(&edit_id)
87 .unwrap_or(&Vec::new())
88 .iter()
89 .map(|undo| undo.count)
90 .max()
91 .unwrap_or(0)
92 }
93}
94
95pub struct Buffer {
96 file: Option<FileHandle>,
97 fragments: SumTree<Fragment>,
98 insertion_splits: HashMap<time::Local, SumTree<InsertionSplit>>,
99 edit_ops: HashMap<time::Local, EditOperation>,
100 pub version: time::Global,
101 saved_version: time::Global,
102 last_edit: time::Local,
103 undo_map: UndoMap,
104 selections: HashMap<SelectionSetId, Vec<Selection>>,
105 pub selections_last_update: SelectionsVersion,
106 deferred_ops: OperationQueue<Operation>,
107 deferred_replicas: HashSet<ReplicaId>,
108 replica_id: ReplicaId,
109 local_clock: time::Local,
110 lamport_clock: time::Lamport,
111}
112
113pub struct Snapshot {
114 fragments: SumTree<Fragment>,
115}
116
117#[derive(Clone)]
118pub struct History {
119 pub base_text: String,
120}
121
122#[derive(Clone, Debug, Eq, PartialEq)]
123pub struct Selection {
124 pub start: Anchor,
125 pub end: Anchor,
126 pub reversed: bool,
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 undos: HashSet<time::Local>,
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: HashSet::default(),
276 undos: HashSet::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: HashSet::default(),
296 undos: HashSet::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(
935 &mut self,
936 edit_id: time::Local,
937 ctx: Option<&mut ModelContext<Self>>,
938 ) -> Result<Operation> {
939 let was_dirty = self.is_dirty();
940 let old_version = self.version.clone();
941 let undo = UndoOperation {
942 id: self.local_clock.tick(),
943 edit_id,
944 count: self.undo_map.undo_count(edit_id) + 1,
945 };
946 self.apply_undo(undo)?;
947 self.version.observe(undo.id);
948
949 if let Some(ctx) = ctx {
950 ctx.notify();
951 let changes = self.edits_since(old_version).collect::<Vec<_>>();
952 if !changes.is_empty() {
953 self.did_edit(changes, was_dirty, ctx);
954 }
955 }
956
957 Ok(Operation::Undo {
958 undo,
959 lamport_timestamp: self.lamport_clock.tick(),
960 })
961 }
962
963 fn apply_undo(&mut self, undo: UndoOperation) -> Result<()> {
964 let mut new_fragments;
965
966 self.undo_map.insert(undo);
967 let edit = &self.edit_ops[&undo.edit_id];
968 let start_fragment_id = self.resolve_fragment_id(edit.start_id, edit.start_offset)?;
969 let end_fragment_id = self.resolve_fragment_id(edit.end_id, edit.end_offset)?;
970 let mut cursor = self.fragments.cursor::<FragmentIdRef, ()>();
971
972 if edit.start_id == edit.end_id && edit.start_offset == edit.end_offset {
973 let splits = &self.insertion_splits[&undo.edit_id];
974 let mut insertion_splits = splits.cursor::<(), ()>().map(|s| &s.fragment_id).peekable();
975
976 let first_split_id = insertion_splits.next().unwrap();
977 new_fragments = cursor.slice(&FragmentIdRef::new(first_split_id), SeekBias::Left);
978
979 loop {
980 let mut fragment = cursor.item().unwrap().clone();
981 fragment.visible = fragment.is_visible(&self.undo_map);
982 fragment.undos.insert(undo.id);
983 new_fragments.push(fragment);
984 cursor.next();
985 if let Some(split_id) = insertion_splits.next() {
986 new_fragments
987 .push_tree(cursor.slice(&FragmentIdRef::new(split_id), SeekBias::Left));
988 } else {
989 break;
990 }
991 }
992 } else {
993 new_fragments = cursor.slice(&FragmentIdRef::new(&start_fragment_id), SeekBias::Left);
994 while let Some(fragment) = cursor.item() {
995 if fragment.id > end_fragment_id {
996 break;
997 } else {
998 let mut fragment = fragment.clone();
999 if edit.version_in_range.observed(fragment.insertion.id)
1000 || fragment.insertion.id == undo.edit_id
1001 {
1002 fragment.visible = fragment.is_visible(&self.undo_map);
1003 fragment.undos.insert(undo.id);
1004 }
1005 new_fragments.push(fragment);
1006 cursor.next();
1007 }
1008 }
1009 }
1010
1011 new_fragments.push_tree(cursor.suffix());
1012 drop(cursor);
1013 self.fragments = new_fragments;
1014
1015 Ok(())
1016 }
1017
1018 fn flush_deferred_ops(&mut self) -> Result<()> {
1019 self.deferred_replicas.clear();
1020 let mut deferred_ops = Vec::new();
1021 for op in self.deferred_ops.drain().cursor().cloned() {
1022 if self.can_apply_op(&op) {
1023 self.apply_op(op)?;
1024 } else {
1025 self.deferred_replicas.insert(op.replica_id());
1026 deferred_ops.push(op);
1027 }
1028 }
1029 self.deferred_ops.insert(deferred_ops);
1030 Ok(())
1031 }
1032
1033 fn can_apply_op(&self, op: &Operation) -> bool {
1034 if self.deferred_replicas.contains(&op.replica_id()) {
1035 false
1036 } else {
1037 match op {
1038 Operation::Edit { edit, .. } => {
1039 self.version.observed(edit.start_id)
1040 && self.version.observed(edit.end_id)
1041 && edit.version_in_range <= self.version
1042 }
1043 Operation::Undo { undo, .. } => self.version.observed(undo.edit_id),
1044 Operation::UpdateSelections { selections, .. } => {
1045 if let Some(selections) = selections {
1046 selections.iter().all(|selection| {
1047 let contains_start = match selection.start {
1048 Anchor::Middle { insertion_id, .. } => {
1049 self.version.observed(insertion_id)
1050 }
1051 _ => true,
1052 };
1053 let contains_end = match selection.end {
1054 Anchor::Middle { insertion_id, .. } => {
1055 self.version.observed(insertion_id)
1056 }
1057 _ => true,
1058 };
1059 contains_start && contains_end
1060 })
1061 } else {
1062 true
1063 }
1064 }
1065 }
1066 }
1067 }
1068
1069 fn resolve_fragment_id(&self, edit_id: time::Local, offset: usize) -> Result<FragmentId> {
1070 let split_tree = self
1071 .insertion_splits
1072 .get(&edit_id)
1073 .ok_or_else(|| anyhow!("invalid operation"))?;
1074 let mut cursor = split_tree.cursor::<usize, ()>();
1075 cursor.seek(&offset, SeekBias::Left);
1076 Ok(cursor
1077 .item()
1078 .ok_or_else(|| anyhow!("invalid operation"))?
1079 .fragment_id
1080 .clone())
1081 }
1082
1083 fn splice_fragments<I>(&mut self, mut old_ranges: I, new_text: Option<Text>) -> Vec<Operation>
1084 where
1085 I: Iterator<Item = Range<usize>>,
1086 {
1087 let mut cur_range = old_ranges.next();
1088 if cur_range.is_none() {
1089 return Vec::new();
1090 }
1091
1092 let mut ops = Vec::with_capacity(old_ranges.size_hint().0);
1093
1094 let old_fragments = self.fragments.clone();
1095 let mut cursor = old_fragments.cursor::<usize, usize>();
1096 let mut new_fragments = SumTree::new();
1097 new_fragments.push_tree(cursor.slice(&cur_range.as_ref().unwrap().start, SeekBias::Right));
1098
1099 let mut start_id = None;
1100 let mut start_offset = None;
1101 let mut end_id = None;
1102 let mut end_offset = None;
1103 let mut version_in_range = time::Global::new();
1104
1105 let mut local_timestamp = self.local_clock.tick();
1106 let mut lamport_timestamp = self.lamport_clock.tick();
1107
1108 while cur_range.is_some() && cursor.item().is_some() {
1109 let mut fragment = cursor.item().unwrap().clone();
1110 let fragment_summary = cursor.item_summary().unwrap();
1111 let mut fragment_start = *cursor.start();
1112 let mut fragment_end = fragment_start + fragment.visible_len();
1113
1114 let old_split_tree = self
1115 .insertion_splits
1116 .remove(&fragment.insertion.id)
1117 .unwrap();
1118 let mut splits_cursor = old_split_tree.cursor::<usize, ()>();
1119 let mut new_split_tree = splits_cursor.slice(&fragment.start_offset(), SeekBias::Right);
1120
1121 // Find all splices that start or end within the current fragment. Then, split the
1122 // fragment and reassemble it in both trees accounting for the deleted and the newly
1123 // inserted text.
1124 while cur_range.as_ref().map_or(false, |r| r.start < fragment_end) {
1125 let range = cur_range.clone().unwrap();
1126 if range.start > fragment_start {
1127 let mut prefix = fragment.clone();
1128 prefix.set_end_offset(prefix.start_offset() + (range.start - fragment_start));
1129 prefix.id =
1130 FragmentId::between(&new_fragments.last().unwrap().id, &fragment.id);
1131 fragment.set_start_offset(prefix.end_offset());
1132 new_fragments.push(prefix.clone());
1133 new_split_tree.push(InsertionSplit {
1134 extent: prefix.end_offset() - prefix.start_offset(),
1135 fragment_id: prefix.id,
1136 });
1137 fragment_start = range.start;
1138 }
1139
1140 if range.end == fragment_start {
1141 end_id = Some(new_fragments.last().unwrap().insertion.id);
1142 end_offset = Some(new_fragments.last().unwrap().end_offset());
1143 } else if range.end == fragment_end {
1144 end_id = Some(fragment.insertion.id);
1145 end_offset = Some(fragment.end_offset());
1146 }
1147
1148 if range.start == fragment_start {
1149 start_id = Some(new_fragments.last().unwrap().insertion.id);
1150 start_offset = Some(new_fragments.last().unwrap().end_offset());
1151
1152 if let Some(new_text) = new_text.clone() {
1153 let new_fragment = self.build_fragment_to_insert(
1154 &new_fragments.last().unwrap(),
1155 Some(&fragment),
1156 new_text,
1157 local_timestamp,
1158 lamport_timestamp,
1159 );
1160 new_fragments.push(new_fragment);
1161 }
1162 }
1163
1164 if range.end < fragment_end {
1165 if range.end > fragment_start {
1166 let mut prefix = fragment.clone();
1167 prefix.set_end_offset(prefix.start_offset() + (range.end - fragment_start));
1168 prefix.id =
1169 FragmentId::between(&new_fragments.last().unwrap().id, &fragment.id);
1170 version_in_range.observe_all(&fragment_summary.max_version);
1171 if fragment.visible {
1172 prefix.deletions.insert(local_timestamp);
1173 prefix.visible = false;
1174 }
1175 fragment.set_start_offset(prefix.end_offset());
1176 new_fragments.push(prefix.clone());
1177 new_split_tree.push(InsertionSplit {
1178 extent: prefix.end_offset() - prefix.start_offset(),
1179 fragment_id: prefix.id,
1180 });
1181 fragment_start = range.end;
1182 end_id = Some(fragment.insertion.id);
1183 end_offset = Some(fragment.start_offset());
1184 }
1185 } else {
1186 version_in_range.observe_all(&fragment_summary.max_version);
1187 if fragment.visible {
1188 fragment.deletions.insert(local_timestamp);
1189 fragment.visible = false;
1190 }
1191 }
1192
1193 // If the splice ends inside this fragment, we can advance to the next splice and
1194 // check if it also intersects the current fragment. Otherwise we break out of the
1195 // loop and find the first fragment that the splice does not contain fully.
1196 if range.end <= fragment_end {
1197 ops.push(Operation::Edit {
1198 edit: EditOperation {
1199 id: local_timestamp,
1200 start_id: start_id.unwrap(),
1201 start_offset: start_offset.unwrap(),
1202 end_id: end_id.unwrap(),
1203 end_offset: end_offset.unwrap(),
1204 version_in_range,
1205 new_text: new_text.clone(),
1206 },
1207 lamport_timestamp,
1208 });
1209
1210 start_id = None;
1211 start_offset = None;
1212 end_id = None;
1213 end_offset = None;
1214 version_in_range = time::Global::new();
1215 cur_range = old_ranges.next();
1216 if cur_range.is_some() {
1217 local_timestamp = self.local_clock.tick();
1218 lamport_timestamp = self.lamport_clock.tick();
1219 }
1220 } else {
1221 break;
1222 }
1223 }
1224 new_split_tree.push(InsertionSplit {
1225 extent: fragment.end_offset() - fragment.start_offset(),
1226 fragment_id: fragment.id.clone(),
1227 });
1228 splits_cursor.next();
1229 new_split_tree
1230 .push_tree(splits_cursor.slice(&old_split_tree.extent::<usize>(), SeekBias::Right));
1231 self.insertion_splits
1232 .insert(fragment.insertion.id, new_split_tree);
1233 new_fragments.push(fragment);
1234
1235 // Scan forward until we find a fragment that is not fully contained by the current splice.
1236 cursor.next();
1237 if let Some(range) = cur_range.clone() {
1238 while let Some(fragment) = cursor.item() {
1239 let fragment_summary = cursor.item_summary().unwrap();
1240 fragment_start = *cursor.start();
1241 fragment_end = fragment_start + fragment.visible_len();
1242 if range.start < fragment_start && range.end >= fragment_end {
1243 let mut new_fragment = fragment.clone();
1244 version_in_range.observe_all(&fragment_summary.max_version);
1245 if new_fragment.visible {
1246 new_fragment.deletions.insert(local_timestamp);
1247 new_fragment.visible = false;
1248 }
1249 new_fragments.push(new_fragment);
1250 cursor.next();
1251
1252 if range.end == fragment_end {
1253 end_id = Some(fragment.insertion.id);
1254 end_offset = Some(fragment.end_offset());
1255 ops.push(Operation::Edit {
1256 edit: EditOperation {
1257 id: local_timestamp,
1258 start_id: start_id.unwrap(),
1259 start_offset: start_offset.unwrap(),
1260 end_id: end_id.unwrap(),
1261 end_offset: end_offset.unwrap(),
1262 version_in_range,
1263 new_text: new_text.clone(),
1264 },
1265 lamport_timestamp,
1266 });
1267
1268 start_id = None;
1269 start_offset = None;
1270 end_id = None;
1271 end_offset = None;
1272 version_in_range = time::Global::new();
1273
1274 cur_range = old_ranges.next();
1275 if cur_range.is_some() {
1276 local_timestamp = self.local_clock.tick();
1277 lamport_timestamp = self.lamport_clock.tick();
1278 }
1279 break;
1280 }
1281 } else {
1282 break;
1283 }
1284 }
1285
1286 // If the splice we are currently evaluating starts after the end of the fragment
1287 // that the cursor is parked at, we should seek to the next splice's start range
1288 // and push all the fragments in between into the new tree.
1289 if cur_range.as_ref().map_or(false, |r| r.start > fragment_end) {
1290 new_fragments.push_tree(
1291 cursor.slice(&cur_range.as_ref().unwrap().start, SeekBias::Right),
1292 );
1293 }
1294 }
1295 }
1296
1297 // Handle range that is at the end of the buffer if it exists. There should never be
1298 // multiple because ranges must be disjoint.
1299 if cur_range.is_some() {
1300 debug_assert_eq!(old_ranges.next(), None);
1301 let last_fragment = new_fragments.last().unwrap();
1302 ops.push(Operation::Edit {
1303 edit: EditOperation {
1304 id: local_timestamp,
1305 start_id: last_fragment.insertion.id,
1306 start_offset: last_fragment.end_offset(),
1307 end_id: last_fragment.insertion.id,
1308 end_offset: last_fragment.end_offset(),
1309 version_in_range: time::Global::new(),
1310 new_text: new_text.clone(),
1311 },
1312 lamport_timestamp,
1313 });
1314
1315 if let Some(new_text) = new_text {
1316 let new_fragment = self.build_fragment_to_insert(
1317 &last_fragment,
1318 None,
1319 new_text,
1320 local_timestamp,
1321 lamport_timestamp,
1322 );
1323 new_fragments.push(new_fragment);
1324 }
1325 } else {
1326 new_fragments
1327 .push_tree(cursor.slice(&old_fragments.extent::<usize>(), SeekBias::Right));
1328 }
1329
1330 self.fragments = new_fragments;
1331 ops
1332 }
1333
1334 fn split_fragment(
1335 &mut self,
1336 prev_fragment: &Fragment,
1337 fragment: &Fragment,
1338 range: Range<usize>,
1339 ) -> (Option<Fragment>, Option<Fragment>, Option<Fragment>) {
1340 debug_assert!(range.start >= fragment.start_offset());
1341 debug_assert!(range.start <= fragment.end_offset());
1342 debug_assert!(range.end <= fragment.end_offset());
1343 debug_assert!(range.end >= fragment.start_offset());
1344
1345 if range.end == fragment.start_offset() {
1346 (None, None, Some(fragment.clone()))
1347 } else if range.start == fragment.end_offset() {
1348 (Some(fragment.clone()), None, None)
1349 } else if range.start == fragment.start_offset() && range.end == fragment.end_offset() {
1350 (None, Some(fragment.clone()), None)
1351 } else {
1352 let mut prefix = fragment.clone();
1353
1354 let after_range = if range.end < fragment.end_offset() {
1355 let mut suffix = prefix.clone();
1356 suffix.set_start_offset(range.end);
1357 prefix.set_end_offset(range.end);
1358 prefix.id = FragmentId::between(&prev_fragment.id, &suffix.id);
1359 Some(suffix)
1360 } else {
1361 None
1362 };
1363
1364 let within_range = if range.start != range.end {
1365 let mut suffix = prefix.clone();
1366 suffix.set_start_offset(range.start);
1367 prefix.set_end_offset(range.start);
1368 prefix.id = FragmentId::between(&prev_fragment.id, &suffix.id);
1369 Some(suffix)
1370 } else {
1371 None
1372 };
1373
1374 let before_range = if range.start > fragment.start_offset() {
1375 Some(prefix)
1376 } else {
1377 None
1378 };
1379
1380 let old_split_tree = self
1381 .insertion_splits
1382 .remove(&fragment.insertion.id)
1383 .unwrap();
1384 let mut cursor = old_split_tree.cursor::<usize, ()>();
1385 let mut new_split_tree = cursor.slice(&fragment.start_offset(), SeekBias::Right);
1386
1387 if let Some(ref fragment) = before_range {
1388 new_split_tree.push(InsertionSplit {
1389 extent: range.start - fragment.start_offset(),
1390 fragment_id: fragment.id.clone(),
1391 });
1392 }
1393
1394 if let Some(ref fragment) = within_range {
1395 new_split_tree.push(InsertionSplit {
1396 extent: range.end - range.start,
1397 fragment_id: fragment.id.clone(),
1398 });
1399 }
1400
1401 if let Some(ref fragment) = after_range {
1402 new_split_tree.push(InsertionSplit {
1403 extent: fragment.end_offset() - range.end,
1404 fragment_id: fragment.id.clone(),
1405 });
1406 }
1407
1408 cursor.next();
1409 new_split_tree
1410 .push_tree(cursor.slice(&old_split_tree.extent::<usize>(), SeekBias::Right));
1411
1412 self.insertion_splits
1413 .insert(fragment.insertion.id, new_split_tree);
1414
1415 (before_range, within_range, after_range)
1416 }
1417 }
1418
1419 fn build_fragment_to_insert(
1420 &mut self,
1421 prev_fragment: &Fragment,
1422 next_fragment: Option<&Fragment>,
1423 text: Text,
1424 local_timestamp: time::Local,
1425 lamport_timestamp: time::Lamport,
1426 ) -> Fragment {
1427 let new_fragment_id = FragmentId::between(
1428 &prev_fragment.id,
1429 next_fragment
1430 .map(|f| &f.id)
1431 .unwrap_or(&FragmentId::max_value()),
1432 );
1433
1434 let mut split_tree = SumTree::new();
1435 split_tree.push(InsertionSplit {
1436 extent: text.len(),
1437 fragment_id: new_fragment_id.clone(),
1438 });
1439 self.insertion_splits.insert(local_timestamp, split_tree);
1440
1441 Fragment::new(
1442 new_fragment_id,
1443 Insertion {
1444 id: local_timestamp,
1445 parent_id: prev_fragment.insertion.id,
1446 offset_in_parent: prev_fragment.end_offset(),
1447 text,
1448 lamport_timestamp,
1449 },
1450 )
1451 }
1452
1453 pub fn anchor_before<T: ToOffset>(&self, position: T) -> Result<Anchor> {
1454 self.anchor_at(position, AnchorBias::Left)
1455 }
1456
1457 pub fn anchor_after<T: ToOffset>(&self, position: T) -> Result<Anchor> {
1458 self.anchor_at(position, AnchorBias::Right)
1459 }
1460
1461 pub fn anchor_at<T: ToOffset>(&self, position: T, bias: AnchorBias) -> Result<Anchor> {
1462 let offset = position.to_offset(self)?;
1463 let max_offset = self.len();
1464 if offset > max_offset {
1465 return Err(anyhow!("offset is out of range"));
1466 }
1467
1468 let seek_bias;
1469 match bias {
1470 AnchorBias::Left => {
1471 if offset == 0 {
1472 return Ok(Anchor::Start);
1473 } else {
1474 seek_bias = SeekBias::Left;
1475 }
1476 }
1477 AnchorBias::Right => {
1478 if offset == max_offset {
1479 return Ok(Anchor::End);
1480 } else {
1481 seek_bias = SeekBias::Right;
1482 }
1483 }
1484 };
1485
1486 let mut cursor = self.fragments.cursor::<usize, usize>();
1487 cursor.seek(&offset, seek_bias);
1488 let fragment = cursor.item().unwrap();
1489 let offset_in_fragment = offset - cursor.start();
1490 let offset_in_insertion = fragment.start_offset() + offset_in_fragment;
1491 let anchor = Anchor::Middle {
1492 insertion_id: fragment.insertion.id,
1493 offset: offset_in_insertion,
1494 bias,
1495 };
1496 Ok(anchor)
1497 }
1498
1499 fn fragment_id_for_anchor(&self, anchor: &Anchor) -> Result<&FragmentId> {
1500 match anchor {
1501 Anchor::Start => Ok(FragmentId::max_value()),
1502 Anchor::End => Ok(FragmentId::min_value()),
1503 Anchor::Middle {
1504 insertion_id,
1505 offset,
1506 bias,
1507 ..
1508 } => {
1509 let seek_bias = match bias {
1510 AnchorBias::Left => SeekBias::Left,
1511 AnchorBias::Right => SeekBias::Right,
1512 };
1513
1514 let splits = self
1515 .insertion_splits
1516 .get(&insertion_id)
1517 .ok_or_else(|| anyhow!("split does not exist for insertion id"))?;
1518 let mut splits_cursor = splits.cursor::<usize, ()>();
1519 splits_cursor.seek(offset, seek_bias);
1520 splits_cursor
1521 .item()
1522 .ok_or_else(|| anyhow!("split offset is out of range"))
1523 .map(|split| &split.fragment_id)
1524 }
1525 }
1526 }
1527
1528 fn summary_for_anchor(&self, anchor: &Anchor) -> Result<TextSummary> {
1529 match anchor {
1530 Anchor::Start => Ok(TextSummary::default()),
1531 Anchor::End => Ok(self.fragments.summary().text_summary),
1532 Anchor::Middle {
1533 insertion_id,
1534 offset,
1535 bias,
1536 } => {
1537 let seek_bias = match bias {
1538 AnchorBias::Left => SeekBias::Left,
1539 AnchorBias::Right => SeekBias::Right,
1540 };
1541
1542 let splits = self
1543 .insertion_splits
1544 .get(&insertion_id)
1545 .ok_or_else(|| anyhow!("split does not exist for insertion id"))?;
1546 let mut splits_cursor = splits.cursor::<usize, ()>();
1547 splits_cursor.seek(offset, seek_bias);
1548 let split = splits_cursor
1549 .item()
1550 .ok_or_else(|| anyhow!("split offset is out of range"))?;
1551
1552 let mut fragments_cursor = self.fragments.cursor::<FragmentIdRef, TextSummary>();
1553 fragments_cursor.seek(&FragmentIdRef::new(&split.fragment_id), SeekBias::Left);
1554 let fragment = fragments_cursor
1555 .item()
1556 .ok_or_else(|| anyhow!("fragment id does not exist"))?;
1557
1558 let mut summary = fragments_cursor.start().clone();
1559 if fragment.visible {
1560 summary += fragment
1561 .text
1562 .slice(..offset - fragment.start_offset())
1563 .summary();
1564 }
1565 Ok(summary)
1566 }
1567 }
1568 }
1569
1570 #[allow(dead_code)]
1571 pub fn point_for_offset(&self, offset: usize) -> Result<Point> {
1572 let mut fragments_cursor = self.fragments.cursor::<usize, TextSummary>();
1573 fragments_cursor.seek(&offset, SeekBias::Left);
1574 fragments_cursor
1575 .item()
1576 .ok_or_else(|| anyhow!("offset is out of range"))
1577 .map(|fragment| {
1578 let overshoot = fragment
1579 .point_for_offset(offset - &fragments_cursor.start().chars)
1580 .unwrap();
1581 fragments_cursor.start().lines + &overshoot
1582 })
1583 }
1584}
1585
1586impl Clone for Buffer {
1587 fn clone(&self) -> Self {
1588 Self {
1589 file: self.file.clone(),
1590 fragments: self.fragments.clone(),
1591 insertion_splits: self.insertion_splits.clone(),
1592 edit_ops: self.edit_ops.clone(),
1593 version: self.version.clone(),
1594 saved_version: self.saved_version.clone(),
1595 last_edit: self.last_edit.clone(),
1596 undo_map: self.undo_map.clone(),
1597 selections: self.selections.clone(),
1598 selections_last_update: self.selections_last_update.clone(),
1599 deferred_ops: self.deferred_ops.clone(),
1600 deferred_replicas: self.deferred_replicas.clone(),
1601 replica_id: self.replica_id,
1602 local_clock: self.local_clock.clone(),
1603 lamport_clock: self.lamport_clock.clone(),
1604 }
1605 }
1606}
1607
1608impl Snapshot {
1609 pub fn fragments<'a>(&'a self) -> FragmentIter<'a> {
1610 FragmentIter::new(&self.fragments)
1611 }
1612
1613 pub fn text_summary(&self) -> TextSummary {
1614 self.fragments.summary().text_summary
1615 }
1616}
1617
1618#[derive(Clone, Debug, Eq, PartialEq)]
1619pub enum Event {
1620 Edited(Vec<Edit>),
1621 Dirtied,
1622 Saved,
1623}
1624
1625impl Entity for Buffer {
1626 type Event = Event;
1627}
1628
1629impl<'a> sum_tree::Dimension<'a, FragmentSummary> for Point {
1630 fn add_summary(&mut self, summary: &FragmentSummary) {
1631 *self += &summary.text_summary.lines;
1632 }
1633}
1634
1635impl<'a> CharIter<'a> {
1636 fn new(fragments: &'a SumTree<Fragment>, offset: usize) -> Self {
1637 let mut fragments_cursor = fragments.cursor::<usize, usize>();
1638 fragments_cursor.seek(&offset, SeekBias::Right);
1639 let fragment_chars = fragments_cursor.item().map_or("".chars(), |fragment| {
1640 let offset_in_fragment = offset - fragments_cursor.start();
1641 fragment.text[offset_in_fragment..].chars()
1642 });
1643 Self {
1644 fragments_cursor,
1645 fragment_chars,
1646 }
1647 }
1648}
1649
1650impl<'a> Iterator for CharIter<'a> {
1651 type Item = char;
1652
1653 fn next(&mut self) -> Option<Self::Item> {
1654 if let Some(char) = self.fragment_chars.next() {
1655 Some(char)
1656 } else {
1657 loop {
1658 self.fragments_cursor.next();
1659 if let Some(fragment) = self.fragments_cursor.item() {
1660 if fragment.visible {
1661 self.fragment_chars = fragment.text.as_str().chars();
1662 return self.fragment_chars.next();
1663 }
1664 } else {
1665 return None;
1666 }
1667 }
1668 }
1669 }
1670}
1671
1672impl<'a> FragmentIter<'a> {
1673 fn new(fragments: &'a SumTree<Fragment>) -> Self {
1674 let mut cursor = fragments.cursor::<usize, usize>();
1675 cursor.seek(&0, SeekBias::Right);
1676 Self {
1677 cursor,
1678 started: false,
1679 }
1680 }
1681}
1682
1683impl<'a> Iterator for FragmentIter<'a> {
1684 type Item = &'a str;
1685
1686 fn next(&mut self) -> Option<Self::Item> {
1687 loop {
1688 if self.started {
1689 self.cursor.next();
1690 } else {
1691 self.started = true;
1692 }
1693 if let Some(fragment) = self.cursor.item() {
1694 if fragment.visible {
1695 return Some(fragment.text.as_str());
1696 }
1697 } else {
1698 return None;
1699 }
1700 }
1701 }
1702}
1703
1704impl<'a, F: Fn(&FragmentSummary) -> bool> Iterator for Edits<'a, F> {
1705 type Item = Edit;
1706
1707 fn next(&mut self) -> Option<Self::Item> {
1708 let mut change: Option<Edit> = None;
1709
1710 while let Some(fragment) = self.cursor.item() {
1711 let new_offset = *self.cursor.start();
1712 let old_offset = (new_offset as isize - self.delta) as usize;
1713
1714 if !fragment.was_visible(&self.since, &self.undos) && fragment.visible {
1715 if let Some(ref mut change) = change {
1716 if change.new_range.end == new_offset {
1717 change.new_range.end += fragment.len();
1718 self.delta += fragment.len() as isize;
1719 } else {
1720 break;
1721 }
1722 } else {
1723 change = Some(Edit {
1724 old_range: old_offset..old_offset,
1725 new_range: new_offset..new_offset + fragment.len(),
1726 });
1727 self.delta += fragment.len() as isize;
1728 }
1729 } else if fragment.was_visible(&self.since, &self.undos) && !fragment.visible {
1730 if let Some(ref mut change) = change {
1731 if change.new_range.end == new_offset {
1732 change.old_range.end += fragment.len();
1733 self.delta -= fragment.len() as isize;
1734 } else {
1735 break;
1736 }
1737 } else {
1738 change = Some(Edit {
1739 old_range: old_offset..old_offset + fragment.len(),
1740 new_range: new_offset..new_offset,
1741 });
1742 self.delta -= fragment.len() as isize;
1743 }
1744 }
1745
1746 self.cursor.next();
1747 }
1748
1749 change
1750 }
1751}
1752
1753// pub fn diff(a: &[u16], b: &[u16]) -> Vec<Edit> {
1754// struct EditCollector<'a> {
1755// a: &'a [u16],
1756// b: &'a [u16],
1757// position: Point,
1758// changes: Vec<Edit>,
1759// }
1760//
1761// impl<'a> diffs::Diff for EditCollector<'a> {
1762// type Error = ();
1763//
1764// fn equal(&mut self, old: usize, _: usize, len: usize) -> Result<(), ()> {
1765// self.position += &Text::extent(&self.a[old..old + len]);
1766// Ok(())
1767// }
1768//
1769// fn delete(&mut self, old: usize, len: usize) -> Result<(), ()> {
1770// self.changes.push(Edit {
1771// range: self.position..self.position + &Text::extent(&self.a[old..old + len]),
1772// chars: Vec::new(),
1773// new_char_count: Point::zero(),
1774// });
1775// Ok(())
1776// }
1777//
1778// fn insert(&mut self, _: usize, new: usize, new_len: usize) -> Result<(), ()> {
1779// let new_char_count = Text::extent(&self.b[new..new + new_len]);
1780// self.changes.push(Edit {
1781// range: self.position..self.position,
1782// chars: Vec::from(&self.b[new..new + new_len]),
1783// new_char_count,
1784// });
1785// self.position += &new_char_count;
1786// Ok(())
1787// }
1788//
1789// fn replace(
1790// &mut self,
1791// old: usize,
1792// old_len: usize,
1793// new: usize,
1794// new_len: usize,
1795// ) -> Result<(), ()> {
1796// let old_extent = text::extent(&self.a[old..old + old_len]);
1797// let new_char_count = text::extent(&self.b[new..new + new_len]);
1798// self.changes.push(Edit {
1799// range: self.position..self.position + &old_extent,
1800// chars: Vec::from(&self.b[new..new + new_len]),
1801// new_char_count,
1802// });
1803// self.position += &new_char_count;
1804// Ok(())
1805// }
1806// }
1807//
1808// let mut collector = diffs::Replace::new(EditCollector {
1809// a,
1810// b,
1811// position: Point::zero(),
1812// changes: Vec::new(),
1813// });
1814// diffs::myers::diff(&mut collector, a, 0, a.len(), b, 0, b.len()).unwrap();
1815// collector.into_inner().changes
1816// }
1817
1818impl Selection {
1819 pub fn head(&self) -> &Anchor {
1820 if self.reversed {
1821 &self.start
1822 } else {
1823 &self.end
1824 }
1825 }
1826
1827 pub fn set_head<S>(&mut self, buffer: &Buffer, cursor: Anchor) {
1828 if cursor.cmp(self.tail(), buffer).unwrap() < Ordering::Equal {
1829 if !self.reversed {
1830 mem::swap(&mut self.start, &mut self.end);
1831 self.reversed = true;
1832 }
1833 self.start = cursor;
1834 } else {
1835 if self.reversed {
1836 mem::swap(&mut self.start, &mut self.end);
1837 self.reversed = false;
1838 }
1839 self.end = cursor;
1840 }
1841 }
1842
1843 pub fn tail(&self) -> &Anchor {
1844 if self.reversed {
1845 &self.end
1846 } else {
1847 &self.start
1848 }
1849 }
1850
1851 pub fn is_empty(&self, buffer: &Buffer) -> bool {
1852 self.start.to_offset(buffer).unwrap() == self.end.to_offset(buffer).unwrap()
1853 }
1854
1855 pub fn anchor_range(&self) -> Range<Anchor> {
1856 self.start.clone()..self.end.clone()
1857 }
1858}
1859
1860#[derive(Ord, PartialOrd, Eq, PartialEq, Clone, Debug)]
1861struct FragmentId(Arc<[u16]>);
1862
1863lazy_static! {
1864 static ref FRAGMENT_ID_EMPTY: FragmentId = FragmentId(Arc::from([]));
1865 static ref FRAGMENT_ID_MIN_VALUE: FragmentId = FragmentId(Arc::from([0 as u16]));
1866 static ref FRAGMENT_ID_MAX_VALUE: FragmentId = FragmentId(Arc::from([u16::max_value()]));
1867}
1868
1869impl Default for FragmentId {
1870 fn default() -> Self {
1871 FRAGMENT_ID_EMPTY.clone()
1872 }
1873}
1874
1875impl FragmentId {
1876 fn min_value() -> &'static Self {
1877 &FRAGMENT_ID_MIN_VALUE
1878 }
1879
1880 fn max_value() -> &'static Self {
1881 &FRAGMENT_ID_MAX_VALUE
1882 }
1883
1884 fn between(left: &Self, right: &Self) -> Self {
1885 Self::between_with_max(left, right, u16::max_value())
1886 }
1887
1888 fn between_with_max(left: &Self, right: &Self, max_value: u16) -> Self {
1889 let mut new_entries = Vec::new();
1890
1891 let left_entries = left.0.iter().cloned().chain(iter::repeat(0));
1892 let right_entries = right.0.iter().cloned().chain(iter::repeat(max_value));
1893 for (l, r) in left_entries.zip(right_entries) {
1894 let interval = r - l;
1895 if interval > 1 {
1896 new_entries.push(l + cmp::max(1, cmp::min(8, interval / 2)));
1897 break;
1898 } else {
1899 new_entries.push(l);
1900 }
1901 }
1902
1903 FragmentId(Arc::from(new_entries))
1904 }
1905}
1906
1907#[derive(Ord, PartialOrd, Eq, PartialEq, Clone, Debug, Default)]
1908struct FragmentIdRef<'a>(Option<&'a FragmentId>);
1909
1910impl<'a> FragmentIdRef<'a> {
1911 fn new(id: &'a FragmentId) -> Self {
1912 Self(Some(id))
1913 }
1914}
1915
1916impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FragmentIdRef<'a> {
1917 fn add_summary(&mut self, summary: &'a FragmentSummary) {
1918 self.0 = Some(&summary.max_fragment_id)
1919 }
1920}
1921
1922impl Fragment {
1923 fn new(id: FragmentId, insertion: Insertion) -> Self {
1924 Self {
1925 id,
1926 text: insertion.text.clone(),
1927 insertion,
1928 deletions: HashSet::default(),
1929 undos: HashSet::default(),
1930 visible: true,
1931 }
1932 }
1933
1934 fn start_offset(&self) -> usize {
1935 self.text.range().start
1936 }
1937
1938 fn set_start_offset(&mut self, offset: usize) {
1939 self.text = self.insertion.text.slice(offset..self.end_offset());
1940 }
1941
1942 fn end_offset(&self) -> usize {
1943 self.text.range().end
1944 }
1945
1946 fn set_end_offset(&mut self, offset: usize) {
1947 self.text = self.insertion.text.slice(self.start_offset()..offset);
1948 }
1949
1950 fn visible_len(&self) -> usize {
1951 if self.visible {
1952 self.len()
1953 } else {
1954 0
1955 }
1956 }
1957
1958 fn len(&self) -> usize {
1959 self.text.len()
1960 }
1961
1962 fn is_visible(&self, undos: &UndoMap) -> bool {
1963 !undos.is_undone(self.insertion.id) && self.deletions.iter().all(|d| undos.is_undone(*d))
1964 }
1965
1966 fn was_visible(&self, version: &time::Global, undos: &UndoMap) -> bool {
1967 (version.observed(self.insertion.id) && !undos.was_undone(self.insertion.id, version))
1968 && self
1969 .deletions
1970 .iter()
1971 .all(|d| !version.observed(*d) || undos.was_undone(*d, version))
1972 }
1973
1974 fn point_for_offset(&self, offset: usize) -> Result<Point> {
1975 Ok(self.text.point_for_offset(offset))
1976 }
1977
1978 fn offset_for_point(&self, point: Point) -> Result<usize> {
1979 Ok(self.text.offset_for_point(point))
1980 }
1981}
1982
1983impl sum_tree::Item for Fragment {
1984 type Summary = FragmentSummary;
1985
1986 fn summary(&self) -> Self::Summary {
1987 let mut max_version = time::Global::new();
1988 max_version.observe(self.insertion.id);
1989 for deletion in &self.deletions {
1990 max_version.observe(*deletion);
1991 }
1992 for undo in &self.undos {
1993 max_version.observe(*undo);
1994 }
1995
1996 if self.visible {
1997 FragmentSummary {
1998 text_summary: self.text.summary(),
1999 max_fragment_id: self.id.clone(),
2000 max_version,
2001 }
2002 } else {
2003 FragmentSummary {
2004 text_summary: TextSummary::default(),
2005 max_fragment_id: self.id.clone(),
2006 max_version,
2007 }
2008 }
2009 }
2010}
2011
2012impl<'a> AddAssign<&'a FragmentSummary> for FragmentSummary {
2013 fn add_assign(&mut self, other: &Self) {
2014 self.text_summary += &other.text_summary;
2015 debug_assert!(self.max_fragment_id <= other.max_fragment_id);
2016 self.max_fragment_id = other.max_fragment_id.clone();
2017 self.max_version.observe_all(&other.max_version);
2018 }
2019}
2020
2021impl Default for FragmentSummary {
2022 fn default() -> Self {
2023 FragmentSummary {
2024 text_summary: TextSummary::default(),
2025 max_fragment_id: FragmentId::min_value().clone(),
2026 max_version: time::Global::new(),
2027 }
2028 }
2029}
2030
2031impl<'a> sum_tree::Dimension<'a, FragmentSummary> for TextSummary {
2032 fn add_summary(&mut self, summary: &FragmentSummary) {
2033 *self += &summary.text_summary;
2034 }
2035}
2036
2037impl<'a> AddAssign<&'a FragmentExtent> for FragmentExtent {
2038 fn add_assign(&mut self, other: &Self) {
2039 self.chars += other.chars;
2040 self.lines += &other.lines;
2041 }
2042}
2043
2044impl Default for FragmentExtent {
2045 fn default() -> Self {
2046 FragmentExtent {
2047 lines: Point::zero(),
2048 chars: 0,
2049 }
2050 }
2051}
2052
2053impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FragmentExtent {
2054 fn add_summary(&mut self, summary: &FragmentSummary) {
2055 self.chars += summary.text_summary.chars;
2056 self.lines += &summary.text_summary.lines;
2057 }
2058}
2059
2060impl<'a> sum_tree::Dimension<'a, FragmentSummary> for usize {
2061 fn add_summary(&mut self, summary: &FragmentSummary) {
2062 *self += summary.text_summary.chars;
2063 }
2064}
2065
2066impl sum_tree::Item for InsertionSplit {
2067 type Summary = InsertionSplitSummary;
2068
2069 fn summary(&self) -> Self::Summary {
2070 InsertionSplitSummary {
2071 extent: self.extent,
2072 }
2073 }
2074}
2075
2076impl<'a> AddAssign<&'a InsertionSplitSummary> for InsertionSplitSummary {
2077 fn add_assign(&mut self, other: &Self) {
2078 self.extent += other.extent;
2079 }
2080}
2081
2082impl Default for InsertionSplitSummary {
2083 fn default() -> Self {
2084 InsertionSplitSummary { extent: 0 }
2085 }
2086}
2087
2088impl<'a> sum_tree::Dimension<'a, InsertionSplitSummary> for usize {
2089 fn add_summary(&mut self, summary: &InsertionSplitSummary) {
2090 *self += &summary.extent;
2091 }
2092}
2093
2094impl Operation {
2095 fn replica_id(&self) -> ReplicaId {
2096 self.lamport_timestamp().replica_id
2097 }
2098
2099 fn lamport_timestamp(&self) -> time::Lamport {
2100 match self {
2101 Operation::Edit {
2102 lamport_timestamp, ..
2103 } => *lamport_timestamp,
2104 Operation::Undo {
2105 lamport_timestamp, ..
2106 } => *lamport_timestamp,
2107 Operation::UpdateSelections {
2108 lamport_timestamp, ..
2109 } => *lamport_timestamp,
2110 }
2111 }
2112
2113 pub fn is_edit(&self) -> bool {
2114 match self {
2115 Operation::Edit { .. } => true,
2116 _ => false,
2117 }
2118 }
2119}
2120
2121impl operation_queue::Operation for Operation {
2122 fn timestamp(&self) -> time::Lamport {
2123 self.lamport_timestamp()
2124 }
2125}
2126
2127pub trait ToOffset {
2128 fn to_offset(&self, buffer: &Buffer) -> Result<usize>;
2129}
2130
2131impl ToOffset for Point {
2132 fn to_offset(&self, buffer: &Buffer) -> Result<usize> {
2133 let mut fragments_cursor = buffer.fragments.cursor::<Point, TextSummary>();
2134 fragments_cursor.seek(self, SeekBias::Left);
2135 fragments_cursor
2136 .item()
2137 .ok_or_else(|| anyhow!("point is out of range"))
2138 .map(|fragment| {
2139 let overshoot = fragment
2140 .offset_for_point(*self - fragments_cursor.start().lines)
2141 .unwrap();
2142 fragments_cursor.start().chars + overshoot
2143 })
2144 }
2145}
2146
2147impl ToOffset for usize {
2148 fn to_offset(&self, _: &Buffer) -> Result<usize> {
2149 Ok(*self)
2150 }
2151}
2152
2153impl ToOffset for Anchor {
2154 fn to_offset(&self, buffer: &Buffer) -> Result<usize> {
2155 Ok(buffer.summary_for_anchor(self)?.chars)
2156 }
2157}
2158
2159pub trait ToPoint {
2160 fn to_point(&self, buffer: &Buffer) -> Result<Point>;
2161}
2162
2163impl ToPoint for Anchor {
2164 fn to_point(&self, buffer: &Buffer) -> Result<Point> {
2165 Ok(buffer.summary_for_anchor(self)?.lines)
2166 }
2167}
2168
2169impl ToPoint for usize {
2170 fn to_point(&self, buffer: &Buffer) -> Result<Point> {
2171 let mut fragments_cursor = buffer.fragments.cursor::<usize, TextSummary>();
2172 fragments_cursor.seek(&self, SeekBias::Left);
2173 fragments_cursor
2174 .item()
2175 .ok_or_else(|| anyhow!("offset is out of range"))
2176 .map(|fragment| {
2177 let overshoot = fragment
2178 .point_for_offset(*self - &fragments_cursor.start().chars)
2179 .unwrap();
2180 fragments_cursor.start().lines + overshoot
2181 })
2182 }
2183}
2184
2185#[cfg(test)]
2186mod tests {
2187 use super::*;
2188 use gpui::App;
2189 use std::collections::BTreeMap;
2190 use std::{cell::RefCell, rc::Rc};
2191
2192 #[test]
2193 fn test_edit() -> Result<()> {
2194 let mut buffer = Buffer::new(0, "abc");
2195 assert_eq!(buffer.text(), "abc");
2196 buffer.edit(vec![3..3], "def", None)?;
2197 assert_eq!(buffer.text(), "abcdef");
2198 buffer.edit(vec![0..0], "ghi", None)?;
2199 assert_eq!(buffer.text(), "ghiabcdef");
2200 buffer.edit(vec![5..5], "jkl", None)?;
2201 assert_eq!(buffer.text(), "ghiabjklcdef");
2202 buffer.edit(vec![6..7], "", None)?;
2203 assert_eq!(buffer.text(), "ghiabjlcdef");
2204 buffer.edit(vec![4..9], "mno", None)?;
2205 assert_eq!(buffer.text(), "ghiamnoef");
2206
2207 Ok(())
2208 }
2209
2210 #[test]
2211 fn test_edit_events() {
2212 App::test((), |mut app| async move {
2213 let buffer_1_events = Rc::new(RefCell::new(Vec::new()));
2214 let buffer_2_events = Rc::new(RefCell::new(Vec::new()));
2215
2216 let buffer1 = app.add_model(|_| Buffer::new(0, "abcdef"));
2217 let buffer2 = app.add_model(|_| Buffer::new(1, "abcdef"));
2218 let ops = buffer1.update(&mut app, |buffer, ctx| {
2219 let buffer_1_events = buffer_1_events.clone();
2220 ctx.subscribe(&buffer1, move |_, event, _| {
2221 buffer_1_events.borrow_mut().push(event.clone())
2222 });
2223 let buffer_2_events = buffer_2_events.clone();
2224 ctx.subscribe(&buffer2, move |_, event, _| {
2225 buffer_2_events.borrow_mut().push(event.clone())
2226 });
2227
2228 buffer.edit(Some(2..4), "XYZ", Some(ctx)).unwrap()
2229 });
2230 buffer2.update(&mut app, |buffer, ctx| {
2231 buffer.apply_ops(ops, Some(ctx)).unwrap();
2232 });
2233
2234 let buffer_1_events = buffer_1_events.borrow();
2235 assert_eq!(
2236 *buffer_1_events,
2237 vec![
2238 Event::Edited(vec![Edit {
2239 old_range: 2..4,
2240 new_range: 2..5
2241 },]),
2242 Event::Dirtied
2243 ]
2244 );
2245
2246 let buffer_2_events = buffer_2_events.borrow();
2247 assert_eq!(
2248 *buffer_2_events,
2249 vec![
2250 Event::Edited(vec![Edit {
2251 old_range: 2..4,
2252 new_range: 2..5
2253 },]),
2254 Event::Dirtied
2255 ]
2256 );
2257 });
2258 }
2259
2260 #[test]
2261 fn test_random_edits() {
2262 for seed in 0..100 {
2263 println!("{:?}", seed);
2264 let mut rng = &mut StdRng::seed_from_u64(seed);
2265
2266 let reference_string_len = rng.gen_range(0..3);
2267 let mut reference_string = RandomCharIter::new(&mut rng)
2268 .take(reference_string_len)
2269 .collect::<String>();
2270 let mut buffer = Buffer::new(0, reference_string.as_str());
2271 let mut buffer_versions = Vec::new();
2272
2273 for _i in 0..10 {
2274 let (old_ranges, new_text, _) = buffer.randomly_mutate(rng, None);
2275 for old_range in old_ranges.iter().rev() {
2276 reference_string = [
2277 &reference_string[0..old_range.start],
2278 new_text.as_str(),
2279 &reference_string[old_range.end..],
2280 ]
2281 .concat();
2282 }
2283 assert_eq!(buffer.text(), reference_string);
2284
2285 {
2286 let line_lengths = line_lengths_in_range(&buffer, 0..buffer.len());
2287
2288 for (len, rows) in &line_lengths {
2289 for row in rows {
2290 assert_eq!(buffer.line_len(*row).unwrap(), *len);
2291 }
2292 }
2293
2294 let (longest_column, longest_rows) = line_lengths.iter().next_back().unwrap();
2295 let rightmost_point = buffer.rightmost_point();
2296 assert_eq!(rightmost_point.column, *longest_column);
2297 assert!(longest_rows.contains(&rightmost_point.row));
2298 }
2299
2300 for _ in 0..5 {
2301 let end = rng.gen_range(0..buffer.len() + 1);
2302 let start = rng.gen_range(0..end + 1);
2303
2304 let line_lengths = line_lengths_in_range(&buffer, start..end);
2305 let (longest_column, longest_rows) = line_lengths.iter().next_back().unwrap();
2306 let range_sum = buffer.text_summary_for_range(start..end);
2307 assert_eq!(range_sum.rightmost_point.column, *longest_column);
2308 assert!(longest_rows.contains(&range_sum.rightmost_point.row));
2309 let range_text = &buffer.text()[start..end];
2310 assert_eq!(range_sum.chars, range_text.chars().count());
2311 assert_eq!(range_sum.bytes, range_text.len());
2312 }
2313
2314 if rng.gen_bool(0.3) {
2315 buffer_versions.push(buffer.clone());
2316 }
2317 }
2318
2319 for mut old_buffer in buffer_versions {
2320 let mut delta = 0_isize;
2321 for Edit {
2322 old_range,
2323 new_range,
2324 } in buffer.edits_since(old_buffer.version.clone())
2325 {
2326 let old_len = old_range.end - old_range.start;
2327 let new_len = new_range.end - new_range.start;
2328 let old_start = (old_range.start as isize + delta) as usize;
2329
2330 old_buffer
2331 .edit(
2332 Some(old_start..old_start + old_len),
2333 buffer.text_for_range(new_range).unwrap(),
2334 None,
2335 )
2336 .unwrap();
2337
2338 delta += new_len as isize - old_len as isize;
2339 }
2340 assert_eq!(old_buffer.text(), buffer.text());
2341 }
2342 }
2343 }
2344
2345 #[test]
2346 fn test_line_len() -> Result<()> {
2347 let mut buffer = Buffer::new(0, "");
2348 buffer.edit(vec![0..0], "abcd\nefg\nhij", None)?;
2349 buffer.edit(vec![12..12], "kl\nmno", None)?;
2350 buffer.edit(vec![18..18], "\npqrs\n", None)?;
2351 buffer.edit(vec![18..21], "\nPQ", None)?;
2352
2353 assert_eq!(buffer.line_len(0)?, 4);
2354 assert_eq!(buffer.line_len(1)?, 3);
2355 assert_eq!(buffer.line_len(2)?, 5);
2356 assert_eq!(buffer.line_len(3)?, 3);
2357 assert_eq!(buffer.line_len(4)?, 4);
2358 assert_eq!(buffer.line_len(5)?, 0);
2359 assert!(buffer.line_len(6).is_err());
2360
2361 Ok(())
2362 }
2363
2364 #[test]
2365 fn test_rightmost_point() -> Result<()> {
2366 let mut buffer = Buffer::new(0, "");
2367 assert_eq!(buffer.rightmost_point().row, 0);
2368 buffer.edit(vec![0..0], "abcd\nefg\nhij", None)?;
2369 assert_eq!(buffer.rightmost_point().row, 0);
2370 buffer.edit(vec![12..12], "kl\nmno", None)?;
2371 assert_eq!(buffer.rightmost_point().row, 2);
2372 buffer.edit(vec![18..18], "\npqrs", None)?;
2373 assert_eq!(buffer.rightmost_point().row, 2);
2374 buffer.edit(vec![10..12], "", None)?;
2375 assert_eq!(buffer.rightmost_point().row, 0);
2376 buffer.edit(vec![24..24], "tuv", None)?;
2377 assert_eq!(buffer.rightmost_point().row, 4);
2378
2379 println!("{:?}", buffer.text());
2380
2381 Ok(())
2382 }
2383
2384 #[test]
2385 fn test_text_summary_for_range() {
2386 let buffer = Buffer::new(0, "ab\nefg\nhklm\nnopqrs\ntuvwxyz");
2387 let text = Text::from(buffer.text());
2388
2389 assert_eq!(
2390 buffer.text_summary_for_range(1..3),
2391 text.slice(1..3).summary()
2392 );
2393 assert_eq!(
2394 buffer.text_summary_for_range(1..12),
2395 text.slice(1..12).summary()
2396 );
2397 assert_eq!(
2398 buffer.text_summary_for_range(0..20),
2399 text.slice(0..20).summary()
2400 );
2401 assert_eq!(
2402 buffer.text_summary_for_range(0..22),
2403 text.slice(0..22).summary()
2404 );
2405 assert_eq!(
2406 buffer.text_summary_for_range(7..22),
2407 text.slice(7..22).summary()
2408 );
2409 }
2410
2411 #[test]
2412 fn test_chars_at() -> Result<()> {
2413 let mut buffer = Buffer::new(0, "");
2414 buffer.edit(vec![0..0], "abcd\nefgh\nij", None)?;
2415 buffer.edit(vec![12..12], "kl\nmno", None)?;
2416 buffer.edit(vec![18..18], "\npqrs", None)?;
2417 buffer.edit(vec![18..21], "\nPQ", None)?;
2418
2419 let chars = buffer.chars_at(Point::new(0, 0))?;
2420 assert_eq!(chars.collect::<String>(), "abcd\nefgh\nijkl\nmno\nPQrs");
2421
2422 let chars = buffer.chars_at(Point::new(1, 0))?;
2423 assert_eq!(chars.collect::<String>(), "efgh\nijkl\nmno\nPQrs");
2424
2425 let chars = buffer.chars_at(Point::new(2, 0))?;
2426 assert_eq!(chars.collect::<String>(), "ijkl\nmno\nPQrs");
2427
2428 let chars = buffer.chars_at(Point::new(3, 0))?;
2429 assert_eq!(chars.collect::<String>(), "mno\nPQrs");
2430
2431 let chars = buffer.chars_at(Point::new(4, 0))?;
2432 assert_eq!(chars.collect::<String>(), "PQrs");
2433
2434 // Regression test:
2435 let mut buffer = Buffer::new(0, "");
2436 buffer.edit(vec![0..0], "[workspace]\nmembers = [\n \"xray_core\",\n \"xray_server\",\n \"xray_cli\",\n \"xray_wasm\",\n]\n", None)?;
2437 buffer.edit(vec![60..60], "\n", None)?;
2438
2439 let chars = buffer.chars_at(Point::new(6, 0))?;
2440 assert_eq!(chars.collect::<String>(), " \"xray_wasm\",\n]\n");
2441
2442 Ok(())
2443 }
2444
2445 // #[test]
2446 // fn test_point_for_offset() -> Result<()> {
2447 // let text = Text::from("abc\ndefgh\nijklm\nopq");
2448 // assert_eq!(text.point_for_offset(0)?, Point { row: 0, column: 0 });
2449 // assert_eq!(text.point_for_offset(1)?, Point { row: 0, column: 1 });
2450 // assert_eq!(text.point_for_offset(2)?, Point { row: 0, column: 2 });
2451 // assert_eq!(text.point_for_offset(3)?, Point { row: 0, column: 3 });
2452 // assert_eq!(text.point_for_offset(4)?, Point { row: 1, column: 0 });
2453 // assert_eq!(text.point_for_offset(5)?, Point { row: 1, column: 1 });
2454 // assert_eq!(text.point_for_offset(9)?, Point { row: 1, column: 5 });
2455 // assert_eq!(text.point_for_offset(10)?, Point { row: 2, column: 0 });
2456 // assert_eq!(text.point_for_offset(14)?, Point { row: 2, column: 4 });
2457 // assert_eq!(text.point_for_offset(15)?, Point { row: 2, column: 5 });
2458 // assert_eq!(text.point_for_offset(16)?, Point { row: 3, column: 0 });
2459 // assert_eq!(text.point_for_offset(17)?, Point { row: 3, column: 1 });
2460 // assert_eq!(text.point_for_offset(19)?, Point { row: 3, column: 3 });
2461 // assert!(text.point_for_offset(20).is_err());
2462 //
2463 // let text = Text::from("abc");
2464 // assert_eq!(text.point_for_offset(0)?, Point { row: 0, column: 0 });
2465 // assert_eq!(text.point_for_offset(1)?, Point { row: 0, column: 1 });
2466 // assert_eq!(text.point_for_offset(2)?, Point { row: 0, column: 2 });
2467 // assert_eq!(text.point_for_offset(3)?, Point { row: 0, column: 3 });
2468 // assert!(text.point_for_offset(4).is_err());
2469 // Ok(())
2470 // }
2471
2472 // #[test]
2473 // fn test_offset_for_point() -> Result<()> {
2474 // let text = Text::from("abc\ndefgh");
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 // assert_eq!(text.offset_for_point(Point { row: 1, column: 0 })?, 4);
2481 // assert_eq!(text.offset_for_point(Point { row: 1, column: 1 })?, 5);
2482 // assert_eq!(text.offset_for_point(Point { row: 1, column: 5 })?, 9);
2483 // assert!(text.offset_for_point(Point { row: 1, column: 6 }).is_err());
2484 //
2485 // let text = Text::from("abc");
2486 // assert_eq!(text.offset_for_point(Point { row: 0, column: 0 })?, 0);
2487 // assert_eq!(text.offset_for_point(Point { row: 0, column: 1 })?, 1);
2488 // assert_eq!(text.offset_for_point(Point { row: 0, column: 2 })?, 2);
2489 // assert_eq!(text.offset_for_point(Point { row: 0, column: 3 })?, 3);
2490 // assert!(text.offset_for_point(Point { row: 0, column: 4 }).is_err());
2491 // Ok(())
2492 // }
2493
2494 // #[test]
2495 // fn test_longest_row_in_range() -> Result<()> {
2496 // for seed in 0..100 {
2497 // println!("{:?}", seed);
2498 // let mut rng = &mut StdRng::seed_from_u64(seed);
2499 // let string_len = rng.gen_range(1, 10);
2500 // let string = RandomCharIter(&mut rng)
2501 // .take(string_len)
2502 // .collect::<String>();
2503 // let text = Text::from(string.as_ref());
2504 //
2505 // for _i in 0..10 {
2506 // let end = rng.gen_range(1, string.len() + 1);
2507 // let start = rng.gen_range(0, end);
2508 //
2509 // let mut cur_row = string[0..start].chars().filter(|c| *c == '\n').count() as u32;
2510 // let mut cur_row_len = 0;
2511 // let mut expected_longest_row = cur_row;
2512 // let mut expected_longest_row_len = cur_row_len;
2513 // for ch in string[start..end].chars() {
2514 // if ch == '\n' {
2515 // if cur_row_len > expected_longest_row_len {
2516 // expected_longest_row = cur_row;
2517 // expected_longest_row_len = cur_row_len;
2518 // }
2519 // cur_row += 1;
2520 // cur_row_len = 0;
2521 // } else {
2522 // cur_row_len += 1;
2523 // }
2524 // }
2525 // if cur_row_len > expected_longest_row_len {
2526 // expected_longest_row = cur_row;
2527 // expected_longest_row_len = cur_row_len;
2528 // }
2529 //
2530 // assert_eq!(
2531 // text.longest_row_in_range(start..end)?,
2532 // (expected_longest_row, expected_longest_row_len)
2533 // );
2534 // }
2535 // }
2536 // Ok(())
2537 // }
2538
2539 #[test]
2540 fn test_fragment_ids() {
2541 for seed in 0..10 {
2542 let rng = &mut StdRng::seed_from_u64(seed);
2543
2544 let mut ids = vec![FragmentId(Arc::from([0])), FragmentId(Arc::from([4]))];
2545 for _i in 0..100 {
2546 let index = rng.gen_range(1..ids.len());
2547
2548 let left = ids[index - 1].clone();
2549 let right = ids[index].clone();
2550 ids.insert(index, FragmentId::between_with_max(&left, &right, 4));
2551
2552 let mut sorted_ids = ids.clone();
2553 sorted_ids.sort();
2554 assert_eq!(ids, sorted_ids);
2555 }
2556 }
2557 }
2558
2559 #[test]
2560 fn test_anchors() -> Result<()> {
2561 let mut buffer = Buffer::new(0, "");
2562 buffer.edit(vec![0..0], "abc", None)?;
2563 let left_anchor = buffer.anchor_before(2).unwrap();
2564 let right_anchor = buffer.anchor_after(2).unwrap();
2565
2566 buffer.edit(vec![1..1], "def\n", None)?;
2567 assert_eq!(buffer.text(), "adef\nbc");
2568 assert_eq!(left_anchor.to_offset(&buffer).unwrap(), 6);
2569 assert_eq!(right_anchor.to_offset(&buffer).unwrap(), 6);
2570 assert_eq!(
2571 left_anchor.to_point(&buffer).unwrap(),
2572 Point { row: 1, column: 1 }
2573 );
2574 assert_eq!(
2575 right_anchor.to_point(&buffer).unwrap(),
2576 Point { row: 1, column: 1 }
2577 );
2578
2579 buffer.edit(vec![2..3], "", None)?;
2580 assert_eq!(buffer.text(), "adf\nbc");
2581 assert_eq!(left_anchor.to_offset(&buffer).unwrap(), 5);
2582 assert_eq!(right_anchor.to_offset(&buffer).unwrap(), 5);
2583 assert_eq!(
2584 left_anchor.to_point(&buffer).unwrap(),
2585 Point { row: 1, column: 1 }
2586 );
2587 assert_eq!(
2588 right_anchor.to_point(&buffer).unwrap(),
2589 Point { row: 1, column: 1 }
2590 );
2591
2592 buffer.edit(vec![5..5], "ghi\n", None)?;
2593 assert_eq!(buffer.text(), "adf\nbghi\nc");
2594 assert_eq!(left_anchor.to_offset(&buffer).unwrap(), 5);
2595 assert_eq!(right_anchor.to_offset(&buffer).unwrap(), 9);
2596 assert_eq!(
2597 left_anchor.to_point(&buffer).unwrap(),
2598 Point { row: 1, column: 1 }
2599 );
2600 assert_eq!(
2601 right_anchor.to_point(&buffer).unwrap(),
2602 Point { row: 2, column: 0 }
2603 );
2604
2605 buffer.edit(vec![7..9], "", None)?;
2606 assert_eq!(buffer.text(), "adf\nbghc");
2607 assert_eq!(left_anchor.to_offset(&buffer).unwrap(), 5);
2608 assert_eq!(right_anchor.to_offset(&buffer).unwrap(), 7);
2609 assert_eq!(
2610 left_anchor.to_point(&buffer).unwrap(),
2611 Point { row: 1, column: 1 },
2612 );
2613 assert_eq!(
2614 right_anchor.to_point(&buffer).unwrap(),
2615 Point { row: 1, column: 3 }
2616 );
2617
2618 // Ensure anchoring to a point is equivalent to anchoring to an offset.
2619 assert_eq!(
2620 buffer.anchor_before(Point { row: 0, column: 0 })?,
2621 buffer.anchor_before(0)?
2622 );
2623 assert_eq!(
2624 buffer.anchor_before(Point { row: 0, column: 1 })?,
2625 buffer.anchor_before(1)?
2626 );
2627 assert_eq!(
2628 buffer.anchor_before(Point { row: 0, column: 2 })?,
2629 buffer.anchor_before(2)?
2630 );
2631 assert_eq!(
2632 buffer.anchor_before(Point { row: 0, column: 3 })?,
2633 buffer.anchor_before(3)?
2634 );
2635 assert_eq!(
2636 buffer.anchor_before(Point { row: 1, column: 0 })?,
2637 buffer.anchor_before(4)?
2638 );
2639 assert_eq!(
2640 buffer.anchor_before(Point { row: 1, column: 1 })?,
2641 buffer.anchor_before(5)?
2642 );
2643 assert_eq!(
2644 buffer.anchor_before(Point { row: 1, column: 2 })?,
2645 buffer.anchor_before(6)?
2646 );
2647 assert_eq!(
2648 buffer.anchor_before(Point { row: 1, column: 3 })?,
2649 buffer.anchor_before(7)?
2650 );
2651 assert_eq!(
2652 buffer.anchor_before(Point { row: 1, column: 4 })?,
2653 buffer.anchor_before(8)?
2654 );
2655
2656 // Comparison between anchors.
2657 let anchor_at_offset_0 = buffer.anchor_before(0).unwrap();
2658 let anchor_at_offset_1 = buffer.anchor_before(1).unwrap();
2659 let anchor_at_offset_2 = buffer.anchor_before(2).unwrap();
2660
2661 assert_eq!(
2662 anchor_at_offset_0.cmp(&anchor_at_offset_0, &buffer)?,
2663 Ordering::Equal
2664 );
2665 assert_eq!(
2666 anchor_at_offset_1.cmp(&anchor_at_offset_1, &buffer)?,
2667 Ordering::Equal
2668 );
2669 assert_eq!(
2670 anchor_at_offset_2.cmp(&anchor_at_offset_2, &buffer)?,
2671 Ordering::Equal
2672 );
2673
2674 assert_eq!(
2675 anchor_at_offset_0.cmp(&anchor_at_offset_1, &buffer)?,
2676 Ordering::Less
2677 );
2678 assert_eq!(
2679 anchor_at_offset_1.cmp(&anchor_at_offset_2, &buffer)?,
2680 Ordering::Less
2681 );
2682 assert_eq!(
2683 anchor_at_offset_0.cmp(&anchor_at_offset_2, &buffer)?,
2684 Ordering::Less
2685 );
2686
2687 assert_eq!(
2688 anchor_at_offset_1.cmp(&anchor_at_offset_0, &buffer)?,
2689 Ordering::Greater
2690 );
2691 assert_eq!(
2692 anchor_at_offset_2.cmp(&anchor_at_offset_1, &buffer)?,
2693 Ordering::Greater
2694 );
2695 assert_eq!(
2696 anchor_at_offset_2.cmp(&anchor_at_offset_0, &buffer)?,
2697 Ordering::Greater
2698 );
2699 Ok(())
2700 }
2701
2702 #[test]
2703 fn test_anchors_at_start_and_end() -> Result<()> {
2704 let mut buffer = Buffer::new(0, "");
2705 let before_start_anchor = buffer.anchor_before(0).unwrap();
2706 let after_end_anchor = buffer.anchor_after(0).unwrap();
2707
2708 buffer.edit(vec![0..0], "abc", None)?;
2709 assert_eq!(buffer.text(), "abc");
2710 assert_eq!(before_start_anchor.to_offset(&buffer).unwrap(), 0);
2711 assert_eq!(after_end_anchor.to_offset(&buffer).unwrap(), 3);
2712
2713 let after_start_anchor = buffer.anchor_after(0).unwrap();
2714 let before_end_anchor = buffer.anchor_before(3).unwrap();
2715
2716 buffer.edit(vec![3..3], "def", None)?;
2717 buffer.edit(vec![0..0], "ghi", None)?;
2718 assert_eq!(buffer.text(), "ghiabcdef");
2719 assert_eq!(before_start_anchor.to_offset(&buffer).unwrap(), 0);
2720 assert_eq!(after_start_anchor.to_offset(&buffer).unwrap(), 3);
2721 assert_eq!(before_end_anchor.to_offset(&buffer).unwrap(), 6);
2722 assert_eq!(after_end_anchor.to_offset(&buffer).unwrap(), 9);
2723
2724 Ok(())
2725 }
2726
2727 #[test]
2728 fn test_is_modified() -> Result<()> {
2729 App::test((), |mut app| async move {
2730 let model = app.add_model(|_| Buffer::new(0, "abc"));
2731 let events = Rc::new(RefCell::new(Vec::new()));
2732
2733 // initially, the buffer isn't dirty.
2734 model.update(&mut app, |buffer, ctx| {
2735 ctx.subscribe(&model, {
2736 let events = events.clone();
2737 move |_, event, _| events.borrow_mut().push(event.clone())
2738 });
2739
2740 assert!(!buffer.is_dirty());
2741 assert!(events.borrow().is_empty());
2742
2743 buffer.edit(vec![1..2], "", Some(ctx)).unwrap();
2744 });
2745
2746 // after the first edit, the buffer is dirty, and emits a dirtied event.
2747 model.update(&mut app, |buffer, ctx| {
2748 assert!(buffer.text() == "ac");
2749 assert!(buffer.is_dirty());
2750 assert_eq!(
2751 *events.borrow(),
2752 &[
2753 Event::Edited(vec![Edit {
2754 old_range: 1..2,
2755 new_range: 1..1
2756 }]),
2757 Event::Dirtied
2758 ]
2759 );
2760 events.borrow_mut().clear();
2761
2762 buffer.did_save(buffer.version(), ctx);
2763 });
2764
2765 // after saving, the buffer is not dirty, and emits a saved event.
2766 model.update(&mut app, |buffer, ctx| {
2767 assert!(!buffer.is_dirty());
2768 assert_eq!(*events.borrow(), &[Event::Saved]);
2769 events.borrow_mut().clear();
2770
2771 buffer.edit(vec![1..1], "B", Some(ctx)).unwrap();
2772 buffer.edit(vec![2..2], "D", Some(ctx)).unwrap();
2773 });
2774
2775 // after editing again, the buffer is dirty, and emits another dirty event.
2776 model.update(&mut app, |buffer, ctx| {
2777 assert!(buffer.text() == "aBDc");
2778 assert!(buffer.is_dirty());
2779 assert_eq!(
2780 *events.borrow(),
2781 &[
2782 Event::Edited(vec![Edit {
2783 old_range: 1..1,
2784 new_range: 1..2
2785 }]),
2786 Event::Dirtied,
2787 Event::Edited(vec![Edit {
2788 old_range: 2..2,
2789 new_range: 2..3
2790 }]),
2791 ],
2792 );
2793 events.borrow_mut().clear();
2794
2795 // TODO - currently, after restoring the buffer to its
2796 // previously-saved state, the is still considered dirty.
2797 buffer.edit(vec![1..3], "", Some(ctx)).unwrap();
2798 assert!(buffer.text() == "ac");
2799 assert!(buffer.is_dirty());
2800 });
2801
2802 model.update(&mut app, |_, _| {
2803 assert_eq!(
2804 *events.borrow(),
2805 &[Event::Edited(vec![Edit {
2806 old_range: 1..3,
2807 new_range: 1..1
2808 },])]
2809 );
2810 });
2811 });
2812 Ok(())
2813 }
2814
2815 #[test]
2816 fn test_undo_redo() -> Result<()> {
2817 let mut buffer = Buffer::new(0, "");
2818
2819 let edit1 = buffer.edit(vec![0..0], "abx", None)?;
2820 let edit2 = buffer.edit(vec![2..3], "yzef", None)?;
2821 let edit3 = buffer.edit(vec![2..4], "cd", None)?;
2822
2823 buffer.undo_or_redo(edit1[0].edit_id().unwrap(), None)?;
2824 assert_eq!(buffer.text(), "cdef");
2825 buffer.undo_or_redo(edit1[0].edit_id().unwrap(), None)?;
2826 assert_eq!(buffer.text(), "abcdef");
2827
2828 buffer.undo_or_redo(edit2[0].edit_id().unwrap(), None)?;
2829 assert_eq!(buffer.text(), "abcdx");
2830 buffer.undo_or_redo(edit3[0].edit_id().unwrap(), None)?;
2831 assert_eq!(buffer.text(), "abx");
2832 buffer.undo_or_redo(edit2[0].edit_id().unwrap(), None)?;
2833 assert_eq!(buffer.text(), "abyzef");
2834 buffer.undo_or_redo(edit3[0].edit_id().unwrap(), None)?;
2835 assert_eq!(buffer.text(), "abcdef");
2836
2837 buffer.undo_or_redo(edit3[0].edit_id().unwrap(), None)?;
2838 assert_eq!(buffer.text(), "abyzef");
2839 buffer.undo_or_redo(edit1[0].edit_id().unwrap(), None)?;
2840 assert_eq!(buffer.text(), "yzef");
2841 buffer.undo_or_redo(edit2[0].edit_id().unwrap(), None)?;
2842 assert_eq!(buffer.text(), "");
2843
2844 Ok(())
2845 }
2846
2847 #[test]
2848 fn test_random_concurrent_edits() {
2849 use crate::test::Network;
2850
2851 const PEERS: usize = 5;
2852
2853 for seed in 0..100 {
2854 println!("{:?}", seed);
2855 let mut rng = &mut StdRng::seed_from_u64(seed);
2856
2857 let base_text_len = rng.gen_range(0..10);
2858 let base_text = RandomCharIter::new(&mut rng)
2859 .take(base_text_len)
2860 .collect::<String>();
2861 let mut replica_ids = Vec::new();
2862 let mut buffers = Vec::new();
2863 let mut network = Network::new();
2864 for i in 0..PEERS {
2865 let buffer = Buffer::new(i as ReplicaId, base_text.as_str());
2866 buffers.push(buffer);
2867 replica_ids.push(i as u16);
2868 network.add_peer(i as u16);
2869 }
2870
2871 let mut mutation_count = 10;
2872 loop {
2873 let replica_index = rng.gen_range(0..PEERS);
2874 let replica_id = replica_ids[replica_index];
2875 let buffer = &mut buffers[replica_index];
2876
2877 match rng.gen_range(0..=100) {
2878 0..=50 if mutation_count != 0 => {
2879 let (_, _, ops) = buffer.randomly_mutate(&mut rng, None);
2880 network.broadcast(replica_id, ops, &mut rng);
2881 mutation_count -= 1;
2882 }
2883 51..=70 if mutation_count != 0 => {
2884 let ops = buffer.randomly_undo_redo(&mut rng, None);
2885 network.broadcast(replica_id, ops, &mut rng);
2886 mutation_count -= 1;
2887 }
2888 71..=100 if network.has_unreceived(replica_id) => {
2889 buffer
2890 .apply_ops(network.receive(replica_id, &mut rng), None)
2891 .unwrap();
2892 }
2893 _ => {}
2894 }
2895
2896 if mutation_count == 0 && network.is_idle() {
2897 break;
2898 }
2899 }
2900
2901 for buffer in &buffers[1..] {
2902 assert_eq!(buffer.text(), buffers[0].text());
2903 assert_eq!(
2904 buffer.all_selections().collect::<HashMap<_, _>>(),
2905 buffers[0].all_selections().collect::<HashMap<_, _>>()
2906 );
2907 assert_eq!(
2908 buffer.all_selection_ranges().collect::<HashMap<_, _>>(),
2909 buffers[0].all_selection_ranges().collect::<HashMap<_, _>>()
2910 );
2911 }
2912 }
2913 }
2914
2915 impl Buffer {
2916 pub fn randomly_mutate<T>(
2917 &mut self,
2918 rng: &mut T,
2919 mut ctx: Option<&mut ModelContext<Self>>,
2920 ) -> (Vec<Range<usize>>, String, Vec<Operation>)
2921 where
2922 T: Rng,
2923 {
2924 // Randomly edit
2925 let (old_ranges, new_text, mut operations) =
2926 self.randomly_edit(rng, 5, ctx.as_deref_mut());
2927
2928 // Randomly add, remove or mutate selection sets.
2929 let replica_selection_sets = &self
2930 .all_selections()
2931 .map(|(set_id, _)| *set_id)
2932 .filter(|set_id| self.replica_id == set_id.replica_id)
2933 .collect::<Vec<_>>();
2934 let set_id = replica_selection_sets.choose(rng);
2935 if set_id.is_some() && rng.gen_bool(1.0 / 6.0) {
2936 let op = self.remove_selection_set(*set_id.unwrap()).unwrap();
2937 operations.push(op);
2938 } else {
2939 let mut ranges = Vec::new();
2940 for _ in 0..5 {
2941 let start = rng.gen_range(0..self.len() + 1);
2942 let start_point = self.point_for_offset(start).unwrap();
2943 let end = rng.gen_range(0..self.len() + 1);
2944 let end_point = self.point_for_offset(end).unwrap();
2945 ranges.push(start_point..end_point);
2946 }
2947
2948 let op = if set_id.is_none() || rng.gen_bool(1.0 / 5.0) {
2949 self.add_selection_set(ranges).unwrap().1
2950 } else {
2951 self.replace_selection_set(*set_id.unwrap(), ranges)
2952 .unwrap()
2953 };
2954 operations.push(op);
2955 }
2956
2957 (old_ranges, new_text, operations)
2958 }
2959
2960 pub fn randomly_undo_redo(
2961 &mut self,
2962 rng: &mut impl Rng,
2963 mut ctx: Option<&mut ModelContext<Self>>,
2964 ) -> Vec<Operation> {
2965 let mut ops = Vec::new();
2966 for _ in 0..rng.gen_range(0..5) {
2967 if let Some(edit_id) = self.edit_ops.keys().choose(rng).copied() {
2968 ops.push(self.undo_or_redo(edit_id, ctx.as_deref_mut()).unwrap());
2969 }
2970 }
2971 ops
2972 }
2973 }
2974
2975 impl Operation {
2976 fn edit_id(&self) -> Option<time::Local> {
2977 match self {
2978 Operation::Edit { edit, .. } => Some(edit.id),
2979 Operation::Undo { undo, .. } => Some(undo.edit_id),
2980 Operation::UpdateSelections { .. } => None,
2981 }
2982 }
2983 }
2984
2985 fn line_lengths_in_range(buffer: &Buffer, range: Range<usize>) -> BTreeMap<u32, HashSet<u32>> {
2986 let mut lengths = BTreeMap::new();
2987 for (row, line) in buffer.text()[range].lines().enumerate() {
2988 lengths
2989 .entry(line.len() as u32)
2990 .or_insert(HashSet::default())
2991 .insert(row as u32);
2992 }
2993 if lengths.is_empty() {
2994 let mut rows = HashSet::default();
2995 rows.insert(0);
2996 lengths.insert(0, rows);
2997 }
2998 lengths
2999 }
3000}