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