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