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