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