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