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