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