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