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