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