1mod anchor;
2mod point;
3mod text;
4
5pub use anchor::*;
6pub use point::*;
7pub use text::*;
8
9use crate::{
10 operation_queue::{self, OperationQueue},
11 sum_tree::{self, Cursor, FilterCursor, SeekBias, SumTree},
12 time::{self, ReplicaId},
13 util::RandomCharIter,
14 worktree::FileHandle,
15};
16use anyhow::{anyhow, Result};
17use gpui::{AppContext, Entity, ModelContext};
18use lazy_static::lazy_static;
19use rand::prelude::*;
20use std::{
21 cmp::{self, Ordering},
22 collections::{HashMap, HashSet},
23 iter::{self, Iterator},
24 mem,
25 ops::{AddAssign, Range},
26 path::PathBuf,
27 str,
28 sync::Arc,
29};
30
31pub type SelectionSetId = time::Lamport;
32pub type SelectionsVersion = usize;
33
34pub struct Buffer {
35 file: Option<FileHandle>,
36 fragments: SumTree<Fragment>,
37 insertion_splits: HashMap<time::Local, SumTree<InsertionSplit>>,
38 pub version: time::Global,
39 last_edit: time::Local,
40 selections: HashMap<SelectionSetId, Vec<Selection>>,
41 pub selections_last_update: SelectionsVersion,
42 deferred_ops: OperationQueue<Operation>,
43 deferred_replicas: HashSet<ReplicaId>,
44 replica_id: ReplicaId,
45 local_clock: time::Local,
46 lamport_clock: time::Lamport,
47}
48
49#[derive(Clone)]
50pub struct History {
51 pub base_text: String,
52}
53
54#[derive(Clone, Debug, Eq, PartialEq)]
55pub struct Selection {
56 pub start: Anchor,
57 pub end: Anchor,
58 pub reversed: bool,
59}
60
61#[derive(Clone)]
62pub struct Chars<'a> {
63 fragments_cursor: Cursor<'a, Fragment, usize, usize>,
64 fragment_chars: str::Chars<'a>,
65}
66
67struct Edits<'a, F: Fn(&FragmentSummary) -> bool> {
68 cursor: FilterCursor<'a, F, Fragment, usize>,
69 since: time::Global,
70 delta: isize,
71}
72
73#[derive(Clone, Debug, Eq, PartialEq)]
74pub struct Edit {
75 pub old_range: Range<usize>,
76 pub new_range: Range<usize>,
77}
78
79impl Edit {
80 pub fn delta(&self) -> isize {
81 (self.new_range.end - self.new_range.start) as isize
82 - (self.old_range.end - self.old_range.start) as isize
83 }
84
85 pub fn old_extent(&self) -> usize {
86 self.old_range.end - self.old_range.start
87 }
88}
89
90#[derive(Clone, Eq, PartialEq, Debug)]
91pub struct Insertion {
92 id: time::Local,
93 parent_id: time::Local,
94 offset_in_parent: usize,
95 text: Text,
96 lamport_timestamp: time::Lamport,
97}
98
99#[derive(Eq, PartialEq, Clone, Debug)]
100struct Fragment {
101 id: FragmentId,
102 insertion: Insertion,
103 text: Text,
104 deletions: HashSet<time::Local>,
105}
106
107#[derive(Eq, PartialEq, Clone, Debug)]
108pub struct FragmentSummary {
109 text_summary: TextSummary,
110 max_fragment_id: FragmentId,
111 max_version: time::Global,
112}
113
114#[derive(Eq, PartialEq, Clone, Debug, Ord, PartialOrd)]
115struct FragmentExtent {
116 chars: usize,
117 lines: Point,
118}
119
120#[derive(Eq, PartialEq, Clone, Debug)]
121struct InsertionSplit {
122 extent: usize,
123 fragment_id: FragmentId,
124}
125
126#[derive(Eq, PartialEq, Clone, Debug)]
127struct InsertionSplitSummary {
128 extent: usize,
129}
130
131#[derive(Clone, Debug, Eq, PartialEq)]
132pub enum Operation {
133 Edit {
134 start_id: time::Local,
135 start_offset: usize,
136 end_id: time::Local,
137 end_offset: usize,
138 version_in_range: time::Global,
139 new_text: Option<Text>,
140 local_timestamp: time::Local,
141 lamport_timestamp: time::Lamport,
142 },
143 UpdateSelections {
144 set_id: SelectionSetId,
145 selections: Option<Vec<Selection>>,
146 lamport_timestamp: time::Lamport,
147 },
148}
149
150impl Buffer {
151 pub fn new<T: Into<String>>(replica_id: ReplicaId, base_text: T) -> Self {
152 Self::build(replica_id, None, base_text.into())
153 }
154
155 pub fn from_history(replica_id: ReplicaId, file: FileHandle, history: History) -> Self {
156 Self::build(replica_id, Some(file), history.base_text)
157 }
158
159 fn build(replica_id: ReplicaId, file: Option<FileHandle>, base_text: String) -> Self {
160 let mut insertion_splits = HashMap::new();
161 let mut fragments = SumTree::new();
162
163 let base_insertion = Insertion {
164 id: time::Local::default(),
165 parent_id: time::Local::default(),
166 offset_in_parent: 0,
167 text: base_text.into(),
168 lamport_timestamp: time::Lamport::default(),
169 };
170
171 insertion_splits.insert(
172 base_insertion.id,
173 SumTree::from_item(InsertionSplit {
174 fragment_id: FragmentId::min_value().clone(),
175 extent: 0,
176 }),
177 );
178 fragments.push(Fragment {
179 id: FragmentId::min_value().clone(),
180 insertion: base_insertion.clone(),
181 text: base_insertion.text.slice(0..0),
182 deletions: HashSet::new(),
183 });
184
185 if base_insertion.text.len() > 0 {
186 let base_fragment_id =
187 FragmentId::between(&FragmentId::min_value(), &FragmentId::max_value());
188
189 insertion_splits
190 .get_mut(&base_insertion.id)
191 .unwrap()
192 .push(InsertionSplit {
193 fragment_id: base_fragment_id.clone(),
194 extent: base_insertion.text.len(),
195 });
196 fragments.push(Fragment {
197 id: base_fragment_id,
198 text: base_insertion.text.clone(),
199 insertion: base_insertion,
200 deletions: HashSet::new(),
201 });
202 }
203
204 Self {
205 file,
206 fragments,
207 insertion_splits,
208 version: time::Global::new(),
209 last_edit: time::Local::default(),
210 selections: HashMap::default(),
211 selections_last_update: 0,
212 deferred_ops: OperationQueue::new(),
213 deferred_replicas: HashSet::new(),
214 replica_id,
215 local_clock: time::Local::new(replica_id),
216 lamport_clock: time::Lamport::new(replica_id),
217 }
218 }
219
220 pub fn path(&self, app: &AppContext) -> Option<PathBuf> {
221 self.file.as_ref().map(|file| file.path(app))
222 }
223
224 pub fn entry_id(&self) -> Option<(usize, usize)> {
225 self.file.as_ref().map(|file| file.entry_id())
226 }
227
228 pub fn is_modified(&self) -> bool {
229 self.version != time::Global::new()
230 }
231
232 pub fn text_summary(&self) -> TextSummary {
233 self.fragments.extent::<TextSummary>()
234 }
235
236 pub fn text_summary_for_range(&self, range: Range<usize>) -> TextSummary {
237 let mut summary = TextSummary::default();
238
239 let mut cursor = self.fragments.cursor::<usize, usize>();
240 cursor.seek(&range.start, SeekBias::Right);
241
242 if let Some(fragment) = cursor.item() {
243 let summary_start = cmp::max(*cursor.start(), range.start) - cursor.start();
244 let summary_end = cmp::min(range.end - cursor.start(), fragment.len());
245 summary += &fragment.text.slice(summary_start..summary_end).summary();
246 cursor.next();
247 }
248
249 if range.end > *cursor.start() {
250 summary += &cursor.summary::<TextSummary>(&range.end, SeekBias::Right);
251
252 if let Some(fragment) = cursor.item() {
253 let summary_start = cmp::max(*cursor.start(), range.start) - cursor.start();
254 let summary_end = cmp::min(range.end - cursor.start(), fragment.len());
255 summary += &fragment.text.slice(summary_start..summary_end).summary();
256 }
257 }
258
259 summary
260 }
261
262 pub fn len(&self) -> usize {
263 self.fragments.extent::<usize>()
264 }
265
266 pub fn line_len(&self, row: u32) -> Result<u32> {
267 let row_start_offset = Point::new(row, 0).to_offset(self)?;
268 let row_end_offset = if row >= self.max_point().row {
269 self.len()
270 } else {
271 Point::new(row + 1, 0).to_offset(self)? - 1
272 };
273
274 Ok((row_end_offset - row_start_offset) as u32)
275 }
276
277 pub fn rightmost_point(&self) -> Point {
278 self.fragments.summary().text_summary.rightmost_point
279 }
280
281 pub fn rightmost_point_in_range(&self, range: Range<usize>) -> Point {
282 let mut summary = TextSummary::default();
283
284 let mut cursor = self.fragments.cursor::<usize, usize>();
285 cursor.seek(&range.start, SeekBias::Right);
286
287 if let Some(fragment) = cursor.item() {
288 let summary_start = cmp::max(*cursor.start(), range.start) - cursor.start();
289 let summary_end = cmp::min(range.end - cursor.start(), fragment.len());
290 summary += &fragment.text.slice(summary_start..summary_end).summary();
291 cursor.next();
292 }
293
294 if range.end > *cursor.start() {
295 summary += &cursor.summary::<TextSummary>(&range.end, SeekBias::Right);
296
297 if let Some(fragment) = cursor.item() {
298 let summary_start = cmp::max(*cursor.start(), range.start) - cursor.start();
299 let summary_end = cmp::min(range.end - cursor.start(), fragment.len());
300 summary += &fragment.text.slice(summary_start..summary_end).summary();
301 }
302 }
303
304 summary.rightmost_point
305 }
306
307 pub fn max_point(&self) -> Point {
308 self.fragments.extent()
309 }
310
311 pub fn line(&self, row: u32) -> Result<String> {
312 Ok(self
313 .chars_at(Point::new(row, 0))?
314 .take_while(|c| *c != '\n')
315 .collect())
316 }
317
318 pub fn text(&self) -> String {
319 self.chars().collect()
320 }
321
322 pub fn text_for_range<T: ToOffset>(&self, range: Range<T>) -> Result<String> {
323 let start = range.start.to_offset(self)?;
324 let end = range.end.to_offset(self)?;
325 Ok(self.chars_at(start)?.take(end - start).collect())
326 }
327
328 pub fn chars(&self) -> Chars {
329 self.chars_at(0).unwrap()
330 }
331
332 pub fn chars_at<T: ToOffset>(&self, position: T) -> Result<Chars> {
333 let offset = position.to_offset(self)?;
334
335 let mut fragments_cursor = self.fragments.cursor::<usize, usize>();
336 fragments_cursor.seek(&offset, SeekBias::Right);
337
338 let fragment_chars = fragments_cursor.item().map_or("".chars(), |fragment| {
339 let offset_in_fragment = offset - fragments_cursor.start();
340 fragment.text[offset_in_fragment..].chars()
341 });
342
343 Ok(Chars {
344 fragments_cursor,
345 fragment_chars,
346 })
347 }
348
349 pub fn selections_changed_since(&self, since: SelectionsVersion) -> bool {
350 self.selections_last_update != since
351 }
352
353 pub fn edits_since<'a>(&'a self, since: time::Global) -> impl 'a + Iterator<Item = Edit> {
354 let since_2 = since.clone();
355 let cursor = self
356 .fragments
357 .filter(move |summary| summary.max_version.changed_since(&since_2));
358
359 Edits {
360 cursor,
361 since,
362 delta: 0,
363 }
364 }
365
366 pub fn deferred_ops_len(&self) -> usize {
367 self.deferred_ops.len()
368 }
369
370 pub fn edit<I, S, T>(
371 &mut self,
372 old_ranges: I,
373 new_text: T,
374 ctx: Option<&mut ModelContext<Self>>,
375 ) -> Result<Vec<Operation>>
376 where
377 I: IntoIterator<Item = Range<S>>,
378 S: ToOffset,
379 T: Into<Text>,
380 {
381 let new_text = new_text.into();
382 let new_text = if new_text.len() > 0 {
383 Some(new_text)
384 } else {
385 None
386 };
387
388 let old_version = self.version.clone();
389 let old_ranges = old_ranges
390 .into_iter()
391 .map(|range| Ok(range.start.to_offset(self)?..range.end.to_offset(self)?))
392 .collect::<Result<Vec<Range<usize>>>>()?;
393
394 let ops = self.splice_fragments(
395 old_ranges
396 .into_iter()
397 .filter(|old_range| new_text.is_some() || old_range.end > old_range.start),
398 new_text.clone(),
399 );
400
401 if let Some(op) = ops.last() {
402 if let Some(ctx) = ctx {
403 ctx.notify();
404 let changes = self.edits_since(old_version).collect::<Vec<_>>();
405 if !changes.is_empty() {
406 ctx.emit(Event::Edited(changes))
407 }
408 }
409
410 if let Operation::Edit {
411 local_timestamp, ..
412 } = op
413 {
414 self.last_edit = *local_timestamp;
415 self.version.observe(*local_timestamp);
416 } else {
417 unreachable!()
418 }
419 }
420
421 Ok(ops)
422 }
423
424 pub fn simulate_typing<T: Rng>(&mut self, rng: &mut T) {
425 let end = rng.gen_range(0..self.len() + 1);
426 let start = rng.gen_range(0..end + 1);
427 let mut range = start..end;
428
429 let new_text_len = rng.gen_range(0..100);
430 let new_text: String = RandomCharIter::new(&mut *rng).take(new_text_len).collect();
431
432 for char in new_text.chars() {
433 self.edit(Some(range.clone()), char.to_string().as_str(), None)
434 .unwrap();
435 range = range.end + 1..range.end + 1;
436 }
437 }
438
439 pub fn randomly_edit<T>(
440 &mut self,
441 rng: &mut T,
442 old_range_count: usize,
443 ctx: Option<&mut ModelContext<Self>>,
444 ) -> (Vec<Range<usize>>, String, Vec<Operation>)
445 where
446 T: Rng,
447 {
448 let mut old_ranges: Vec<Range<usize>> = Vec::new();
449 for _ in 0..old_range_count {
450 let last_end = old_ranges.last().map_or(0, |last_range| last_range.end + 1);
451 if last_end > self.len() {
452 break;
453 }
454 let end = rng.gen_range(last_end..self.len() + 1);
455 let start = rng.gen_range(last_end..end + 1);
456 old_ranges.push(start..end);
457 }
458 let new_text_len = rng.gen_range(0..10);
459 let new_text: String = RandomCharIter::new(&mut *rng).take(new_text_len).collect();
460
461 let operations = self
462 .edit(old_ranges.iter().cloned(), new_text.as_str(), ctx)
463 .unwrap();
464
465 (old_ranges, new_text, operations)
466 }
467
468 pub fn add_selection_set<I>(&mut self, ranges: I) -> Result<(SelectionSetId, Operation)>
469 where
470 I: IntoIterator<Item = Range<Point>>,
471 {
472 let selections = self.selections_from_ranges(ranges)?;
473 let lamport_timestamp = self.lamport_clock.tick();
474 self.selections
475 .insert(lamport_timestamp, selections.clone());
476 self.selections_last_update += 1;
477
478 Ok((
479 lamport_timestamp,
480 Operation::UpdateSelections {
481 set_id: lamport_timestamp,
482 selections: Some(selections),
483 lamport_timestamp,
484 },
485 ))
486 }
487
488 pub fn replace_selection_set<I>(
489 &mut self,
490 set_id: SelectionSetId,
491 ranges: I,
492 ) -> Result<Operation>
493 where
494 I: IntoIterator<Item = Range<Point>>,
495 {
496 self.selections
497 .remove(&set_id)
498 .ok_or_else(|| anyhow!("invalid selection set id {:?}", set_id))?;
499
500 let mut selections = self.selections_from_ranges(ranges)?;
501 self.merge_selections(&mut selections);
502 self.selections.insert(set_id, selections.clone());
503
504 let lamport_timestamp = self.lamport_clock.tick();
505 self.selections_last_update += 1;
506
507 Ok(Operation::UpdateSelections {
508 set_id,
509 selections: Some(selections),
510 lamport_timestamp,
511 })
512 }
513
514 pub fn remove_selection_set(&mut self, set_id: SelectionSetId) -> Result<Operation> {
515 self.selections
516 .remove(&set_id)
517 .ok_or_else(|| anyhow!("invalid selection set id {:?}", set_id))?;
518 let lamport_timestamp = self.lamport_clock.tick();
519 self.selections_last_update += 1;
520 Ok(Operation::UpdateSelections {
521 set_id,
522 selections: None,
523 lamport_timestamp,
524 })
525 }
526
527 pub fn selection_ranges<'a>(
528 &'a self,
529 set_id: SelectionSetId,
530 ) -> Result<impl Iterator<Item = Range<Point>> + 'a> {
531 let selections = self
532 .selections
533 .get(&set_id)
534 .ok_or_else(|| anyhow!("invalid selection set id {:?}", set_id))?;
535 Ok(selections.iter().map(move |selection| {
536 let start = selection.start.to_point(self).unwrap();
537 let end = selection.end.to_point(self).unwrap();
538 if selection.reversed {
539 end..start
540 } else {
541 start..end
542 }
543 }))
544 }
545
546 pub fn all_selections(&self) -> impl Iterator<Item = (&SelectionSetId, &Vec<Selection>)> {
547 self.selections.iter()
548 }
549
550 pub fn all_selection_ranges<'a>(
551 &'a self,
552 ) -> impl 'a + Iterator<Item = (SelectionSetId, Vec<Range<Point>>)> {
553 self.selections
554 .keys()
555 .map(move |set_id| (*set_id, self.selection_ranges(*set_id).unwrap().collect()))
556 }
557
558 fn merge_selections(&mut self, selections: &mut Vec<Selection>) {
559 let mut new_selections = Vec::with_capacity(selections.len());
560 {
561 let mut old_selections = selections.drain(..);
562 if let Some(mut prev_selection) = old_selections.next() {
563 for selection in old_selections {
564 if prev_selection.end.cmp(&selection.start, self).unwrap() >= Ordering::Equal {
565 if selection.end.cmp(&prev_selection.end, self).unwrap() > Ordering::Equal {
566 prev_selection.end = selection.end;
567 }
568 } else {
569 new_selections.push(mem::replace(&mut prev_selection, selection));
570 }
571 }
572 new_selections.push(prev_selection);
573 }
574 }
575 *selections = new_selections;
576 }
577
578 fn selections_from_ranges<I>(&self, ranges: I) -> Result<Vec<Selection>>
579 where
580 I: IntoIterator<Item = Range<Point>>,
581 {
582 let mut ranges = ranges.into_iter().collect::<Vec<_>>();
583 ranges.sort_unstable_by_key(|range| range.start);
584
585 let mut selections = Vec::with_capacity(ranges.len());
586 for range in ranges {
587 if range.start > range.end {
588 selections.push(Selection {
589 start: self.anchor_before(range.end)?,
590 end: self.anchor_before(range.start)?,
591 reversed: true,
592 });
593 } else {
594 selections.push(Selection {
595 start: self.anchor_after(range.start)?,
596 end: self.anchor_before(range.end)?,
597 reversed: false,
598 });
599 }
600 }
601 Ok(selections)
602 }
603
604 pub fn apply_ops<I: IntoIterator<Item = Operation>>(
605 &mut self,
606 ops: I,
607 ctx: Option<&mut ModelContext<Self>>,
608 ) -> Result<()> {
609 let old_version = self.version.clone();
610
611 let mut deferred_ops = Vec::new();
612 for op in ops {
613 if self.can_apply_op(&op) {
614 self.apply_op(op)?;
615 } else {
616 self.deferred_replicas.insert(op.replica_id());
617 deferred_ops.push(op);
618 }
619 }
620 self.deferred_ops.insert(deferred_ops);
621 self.flush_deferred_ops()?;
622
623 if let Some(ctx) = ctx {
624 ctx.notify();
625 let changes = self.edits_since(old_version).collect::<Vec<_>>();
626 if !changes.is_empty() {
627 ctx.emit(Event::Edited(changes));
628 }
629 }
630
631 Ok(())
632 }
633
634 fn apply_op(&mut self, op: Operation) -> Result<()> {
635 match op {
636 Operation::Edit {
637 start_id,
638 start_offset,
639 end_id,
640 end_offset,
641 new_text,
642 version_in_range,
643 local_timestamp,
644 lamport_timestamp,
645 } => {
646 if !self.version.observed(local_timestamp) {
647 self.apply_edit(
648 start_id,
649 start_offset,
650 end_id,
651 end_offset,
652 new_text.as_ref().cloned(),
653 &version_in_range,
654 local_timestamp,
655 lamport_timestamp,
656 )?;
657 self.version.observe(local_timestamp);
658 }
659 }
660 Operation::UpdateSelections {
661 set_id,
662 selections,
663 lamport_timestamp,
664 } => {
665 if let Some(selections) = selections {
666 self.selections.insert(set_id, selections);
667 } else {
668 self.selections.remove(&set_id);
669 }
670 self.lamport_clock.observe(lamport_timestamp);
671 self.selections_last_update += 1;
672 }
673 }
674 Ok(())
675 }
676
677 fn apply_edit(
678 &mut self,
679 start_id: time::Local,
680 start_offset: usize,
681 end_id: time::Local,
682 end_offset: usize,
683 new_text: Option<Text>,
684 version_in_range: &time::Global,
685 local_timestamp: time::Local,
686 lamport_timestamp: time::Lamport,
687 ) -> Result<()> {
688 let mut new_text = new_text.as_ref().cloned();
689 let start_fragment_id = self.resolve_fragment_id(start_id, start_offset)?;
690 let end_fragment_id = self.resolve_fragment_id(end_id, end_offset)?;
691
692 let old_fragments = self.fragments.clone();
693 let last_id = old_fragments.extent::<FragmentIdRef>().0.unwrap();
694 let last_id_ref = FragmentIdRef::new(&last_id);
695
696 let mut cursor = old_fragments.cursor::<FragmentIdRef, ()>();
697 let mut new_fragments =
698 cursor.slice(&FragmentIdRef::new(&start_fragment_id), SeekBias::Left);
699
700 if start_offset == cursor.item().unwrap().end_offset() {
701 new_fragments.push(cursor.item().unwrap().clone());
702 cursor.next();
703 }
704
705 while let Some(fragment) = cursor.item() {
706 if new_text.is_none() && fragment.id > end_fragment_id {
707 break;
708 }
709
710 let mut fragment = fragment.clone();
711
712 if fragment.id == start_fragment_id || fragment.id == end_fragment_id {
713 let split_start = if start_fragment_id == fragment.id {
714 start_offset
715 } else {
716 fragment.start_offset()
717 };
718 let split_end = if end_fragment_id == fragment.id {
719 end_offset
720 } else {
721 fragment.end_offset()
722 };
723 let (before_range, within_range, after_range) = self.split_fragment(
724 cursor.prev_item().as_ref().unwrap(),
725 &fragment,
726 split_start..split_end,
727 );
728 let insertion = if let Some(new_text) = new_text.take() {
729 Some(self.build_fragment_to_insert(
730 before_range.as_ref().or(cursor.prev_item()).unwrap(),
731 within_range.as_ref().or(after_range.as_ref()),
732 new_text,
733 local_timestamp,
734 lamport_timestamp,
735 ))
736 } else {
737 None
738 };
739 if let Some(fragment) = before_range {
740 new_fragments.push(fragment);
741 }
742 if let Some(fragment) = insertion {
743 new_fragments.push(fragment);
744 }
745 if let Some(mut fragment) = within_range {
746 if version_in_range.observed(fragment.insertion.id) {
747 fragment.deletions.insert(local_timestamp);
748 }
749 new_fragments.push(fragment);
750 }
751 if let Some(fragment) = after_range {
752 new_fragments.push(fragment);
753 }
754 } else {
755 if new_text.is_some() && lamport_timestamp > fragment.insertion.lamport_timestamp {
756 new_fragments.push(self.build_fragment_to_insert(
757 cursor.prev_item().as_ref().unwrap(),
758 Some(&fragment),
759 new_text.take().unwrap(),
760 local_timestamp,
761 lamport_timestamp,
762 ));
763 }
764
765 if fragment.id < end_fragment_id && version_in_range.observed(fragment.insertion.id)
766 {
767 fragment.deletions.insert(local_timestamp);
768 }
769 new_fragments.push(fragment);
770 }
771
772 cursor.next();
773 }
774
775 if let Some(new_text) = new_text {
776 new_fragments.push(self.build_fragment_to_insert(
777 cursor.prev_item().as_ref().unwrap(),
778 None,
779 new_text,
780 local_timestamp,
781 lamport_timestamp,
782 ));
783 }
784
785 new_fragments.push_tree(cursor.slice(&last_id_ref, SeekBias::Right));
786 self.fragments = new_fragments;
787 self.local_clock.observe(local_timestamp);
788 self.lamport_clock.observe(lamport_timestamp);
789 Ok(())
790 }
791
792 fn flush_deferred_ops(&mut self) -> Result<()> {
793 self.deferred_replicas.clear();
794 let mut deferred_ops = Vec::new();
795 for op in self.deferred_ops.drain().cursor().cloned() {
796 if self.can_apply_op(&op) {
797 self.apply_op(op)?;
798 } else {
799 self.deferred_replicas.insert(op.replica_id());
800 deferred_ops.push(op);
801 }
802 }
803 self.deferred_ops.insert(deferred_ops);
804 Ok(())
805 }
806
807 fn can_apply_op(&self, op: &Operation) -> bool {
808 if self.deferred_replicas.contains(&op.replica_id()) {
809 false
810 } else {
811 match op {
812 Operation::Edit {
813 start_id,
814 end_id,
815 version_in_range,
816 ..
817 } => {
818 self.version.observed(*start_id)
819 && self.version.observed(*end_id)
820 && *version_in_range <= self.version
821 }
822 Operation::UpdateSelections { selections, .. } => {
823 if let Some(selections) = selections {
824 selections.iter().all(|selection| {
825 let contains_start = match selection.start {
826 Anchor::Middle { insertion_id, .. } => {
827 self.version.observed(insertion_id)
828 }
829 _ => true,
830 };
831 let contains_end = match selection.end {
832 Anchor::Middle { insertion_id, .. } => {
833 self.version.observed(insertion_id)
834 }
835 _ => true,
836 };
837 contains_start && contains_end
838 })
839 } else {
840 true
841 }
842 }
843 }
844 }
845 }
846
847 fn resolve_fragment_id(&self, edit_id: time::Local, offset: usize) -> Result<FragmentId> {
848 let split_tree = self
849 .insertion_splits
850 .get(&edit_id)
851 .ok_or_else(|| anyhow!("invalid operation"))?;
852 let mut cursor = split_tree.cursor::<usize, ()>();
853 cursor.seek(&offset, SeekBias::Left);
854 Ok(cursor
855 .item()
856 .ok_or_else(|| anyhow!("invalid operation"))?
857 .fragment_id
858 .clone())
859 }
860
861 fn splice_fragments<I>(&mut self, mut old_ranges: I, new_text: Option<Text>) -> Vec<Operation>
862 where
863 I: Iterator<Item = Range<usize>>,
864 {
865 let mut cur_range = old_ranges.next();
866 if cur_range.is_none() {
867 return Vec::new();
868 }
869
870 let mut ops = Vec::with_capacity(old_ranges.size_hint().0);
871
872 let old_fragments = self.fragments.clone();
873 let mut cursor = old_fragments.cursor::<usize, usize>();
874 let mut new_fragments = SumTree::new();
875 new_fragments.push_tree(cursor.slice(&cur_range.as_ref().unwrap().start, SeekBias::Right));
876
877 let mut start_id = None;
878 let mut start_offset = None;
879 let mut end_id = None;
880 let mut end_offset = None;
881 let mut version_in_range = time::Global::new();
882
883 let mut local_timestamp = self.local_clock.tick();
884 let mut lamport_timestamp = self.lamport_clock.tick();
885
886 while cur_range.is_some() && cursor.item().is_some() {
887 let mut fragment = cursor.item().unwrap().clone();
888 let mut fragment_start = *cursor.start();
889 let mut fragment_end = fragment_start + fragment.visible_len();
890
891 let old_split_tree = self
892 .insertion_splits
893 .remove(&fragment.insertion.id)
894 .unwrap();
895 let mut splits_cursor = old_split_tree.cursor::<usize, ()>();
896 let mut new_split_tree = splits_cursor.slice(&fragment.start_offset(), SeekBias::Right);
897
898 // Find all splices that start or end within the current fragment. Then, split the
899 // fragment and reassemble it in both trees accounting for the deleted and the newly
900 // inserted text.
901 while cur_range.as_ref().map_or(false, |r| r.start < fragment_end) {
902 let range = cur_range.clone().unwrap();
903 if range.start > fragment_start {
904 let mut prefix = fragment.clone();
905 prefix.set_end_offset(prefix.start_offset() + (range.start - fragment_start));
906 prefix.id =
907 FragmentId::between(&new_fragments.last().unwrap().id, &fragment.id);
908 fragment.set_start_offset(prefix.end_offset());
909 new_fragments.push(prefix.clone());
910 new_split_tree.push(InsertionSplit {
911 extent: prefix.end_offset() - prefix.start_offset(),
912 fragment_id: prefix.id,
913 });
914 fragment_start = range.start;
915 }
916
917 if range.end == fragment_start {
918 end_id = Some(new_fragments.last().unwrap().insertion.id);
919 end_offset = Some(new_fragments.last().unwrap().end_offset());
920 } else if range.end == fragment_end {
921 end_id = Some(fragment.insertion.id);
922 end_offset = Some(fragment.end_offset());
923 }
924
925 if range.start == fragment_start {
926 start_id = Some(new_fragments.last().unwrap().insertion.id);
927 start_offset = Some(new_fragments.last().unwrap().end_offset());
928
929 if let Some(new_text) = new_text.clone() {
930 let new_fragment = self.build_fragment_to_insert(
931 &new_fragments.last().unwrap(),
932 Some(&fragment),
933 new_text,
934 local_timestamp,
935 lamport_timestamp,
936 );
937 new_fragments.push(new_fragment);
938 }
939 }
940
941 if range.end < fragment_end {
942 if range.end > fragment_start {
943 let mut prefix = fragment.clone();
944 prefix.set_end_offset(prefix.start_offset() + (range.end - fragment_start));
945 prefix.id =
946 FragmentId::between(&new_fragments.last().unwrap().id, &fragment.id);
947 if fragment.is_visible() {
948 prefix.deletions.insert(local_timestamp);
949 }
950 fragment.set_start_offset(prefix.end_offset());
951 new_fragments.push(prefix.clone());
952 new_split_tree.push(InsertionSplit {
953 extent: prefix.end_offset() - prefix.start_offset(),
954 fragment_id: prefix.id,
955 });
956 fragment_start = range.end;
957 end_id = Some(fragment.insertion.id);
958 end_offset = Some(fragment.start_offset());
959 version_in_range.observe(fragment.insertion.id);
960 }
961 } else {
962 version_in_range.observe(fragment.insertion.id);
963 if fragment.is_visible() {
964 fragment.deletions.insert(local_timestamp);
965 }
966 }
967
968 // If the splice ends inside this fragment, we can advance to the next splice and
969 // check if it also intersects the current fragment. Otherwise we break out of the
970 // loop and find the first fragment that the splice does not contain fully.
971 if range.end <= fragment_end {
972 ops.push(Operation::Edit {
973 start_id: start_id.unwrap(),
974 start_offset: start_offset.unwrap(),
975 end_id: end_id.unwrap(),
976 end_offset: end_offset.unwrap(),
977 version_in_range,
978 new_text: new_text.clone(),
979 local_timestamp,
980 lamport_timestamp,
981 });
982
983 start_id = None;
984 start_offset = None;
985 end_id = None;
986 end_offset = None;
987 version_in_range = time::Global::new();
988 cur_range = old_ranges.next();
989 if cur_range.is_some() {
990 local_timestamp = self.local_clock.tick();
991 lamport_timestamp = self.lamport_clock.tick();
992 }
993 } else {
994 break;
995 }
996 }
997 new_split_tree.push(InsertionSplit {
998 extent: fragment.end_offset() - fragment.start_offset(),
999 fragment_id: fragment.id.clone(),
1000 });
1001 splits_cursor.next();
1002 new_split_tree
1003 .push_tree(splits_cursor.slice(&old_split_tree.extent::<usize>(), SeekBias::Right));
1004 self.insertion_splits
1005 .insert(fragment.insertion.id, new_split_tree);
1006 new_fragments.push(fragment);
1007
1008 // Scan forward until we find a fragment that is not fully contained by the current splice.
1009 cursor.next();
1010 if let Some(range) = cur_range.clone() {
1011 while let Some(fragment) = cursor.item() {
1012 fragment_start = *cursor.start();
1013 fragment_end = fragment_start + fragment.visible_len();
1014 if range.start < fragment_start && range.end >= fragment_end {
1015 let mut new_fragment = fragment.clone();
1016 if new_fragment.is_visible() {
1017 new_fragment.deletions.insert(local_timestamp);
1018 }
1019 version_in_range.observe(new_fragment.insertion.id);
1020 new_fragments.push(new_fragment);
1021 cursor.next();
1022
1023 if range.end == fragment_end {
1024 end_id = Some(fragment.insertion.id);
1025 end_offset = Some(fragment.end_offset());
1026 ops.push(Operation::Edit {
1027 start_id: start_id.unwrap(),
1028 start_offset: start_offset.unwrap(),
1029 end_id: end_id.unwrap(),
1030 end_offset: end_offset.unwrap(),
1031 version_in_range,
1032 new_text: new_text.clone(),
1033 local_timestamp,
1034 lamport_timestamp,
1035 });
1036
1037 start_id = None;
1038 start_offset = None;
1039 end_id = None;
1040 end_offset = None;
1041 version_in_range = time::Global::new();
1042
1043 cur_range = old_ranges.next();
1044 if cur_range.is_some() {
1045 local_timestamp = self.local_clock.tick();
1046 lamport_timestamp = self.lamport_clock.tick();
1047 }
1048 break;
1049 }
1050 } else {
1051 break;
1052 }
1053 }
1054
1055 // If the splice we are currently evaluating starts after the end of the fragment
1056 // that the cursor is parked at, we should seek to the next splice's start range
1057 // and push all the fragments in between into the new tree.
1058 if cur_range.as_ref().map_or(false, |r| r.start > fragment_end) {
1059 new_fragments.push_tree(
1060 cursor.slice(&cur_range.as_ref().unwrap().start, SeekBias::Right),
1061 );
1062 }
1063 }
1064 }
1065
1066 // Handle range that is at the end of the buffer if it exists. There should never be
1067 // multiple because ranges must be disjoint.
1068 if cur_range.is_some() {
1069 debug_assert_eq!(old_ranges.next(), None);
1070 let last_fragment = new_fragments.last().unwrap();
1071 ops.push(Operation::Edit {
1072 start_id: last_fragment.insertion.id,
1073 start_offset: last_fragment.end_offset(),
1074 end_id: last_fragment.insertion.id,
1075 end_offset: last_fragment.end_offset(),
1076 version_in_range: time::Global::new(),
1077 new_text: new_text.clone(),
1078 local_timestamp,
1079 lamport_timestamp,
1080 });
1081
1082 if let Some(new_text) = new_text {
1083 let new_fragment = self.build_fragment_to_insert(
1084 &last_fragment,
1085 None,
1086 new_text,
1087 local_timestamp,
1088 lamport_timestamp,
1089 );
1090 new_fragments.push(new_fragment);
1091 }
1092 } else {
1093 new_fragments
1094 .push_tree(cursor.slice(&old_fragments.extent::<usize>(), SeekBias::Right));
1095 }
1096
1097 self.fragments = new_fragments;
1098 ops
1099 }
1100
1101 fn split_fragment(
1102 &mut self,
1103 prev_fragment: &Fragment,
1104 fragment: &Fragment,
1105 range: Range<usize>,
1106 ) -> (Option<Fragment>, Option<Fragment>, Option<Fragment>) {
1107 debug_assert!(range.start >= fragment.start_offset());
1108 debug_assert!(range.start <= fragment.end_offset());
1109 debug_assert!(range.end <= fragment.end_offset());
1110 debug_assert!(range.end >= fragment.start_offset());
1111
1112 if range.end == fragment.start_offset() {
1113 (None, None, Some(fragment.clone()))
1114 } else if range.start == fragment.end_offset() {
1115 (Some(fragment.clone()), None, None)
1116 } else if range.start == fragment.start_offset() && range.end == fragment.end_offset() {
1117 (None, Some(fragment.clone()), None)
1118 } else {
1119 let mut prefix = fragment.clone();
1120
1121 let after_range = if range.end < fragment.end_offset() {
1122 let mut suffix = prefix.clone();
1123 suffix.set_start_offset(range.end);
1124 prefix.set_end_offset(range.end);
1125 prefix.id = FragmentId::between(&prev_fragment.id, &suffix.id);
1126 Some(suffix)
1127 } else {
1128 None
1129 };
1130
1131 let within_range = if range.start != range.end {
1132 let mut suffix = prefix.clone();
1133 suffix.set_start_offset(range.start);
1134 prefix.set_end_offset(range.start);
1135 prefix.id = FragmentId::between(&prev_fragment.id, &suffix.id);
1136 Some(suffix)
1137 } else {
1138 None
1139 };
1140
1141 let before_range = if range.start > fragment.start_offset() {
1142 Some(prefix)
1143 } else {
1144 None
1145 };
1146
1147 let old_split_tree = self
1148 .insertion_splits
1149 .remove(&fragment.insertion.id)
1150 .unwrap();
1151 let mut cursor = old_split_tree.cursor::<usize, ()>();
1152 let mut new_split_tree = cursor.slice(&fragment.start_offset(), SeekBias::Right);
1153
1154 if let Some(ref fragment) = before_range {
1155 new_split_tree.push(InsertionSplit {
1156 extent: range.start - fragment.start_offset(),
1157 fragment_id: fragment.id.clone(),
1158 });
1159 }
1160
1161 if let Some(ref fragment) = within_range {
1162 new_split_tree.push(InsertionSplit {
1163 extent: range.end - range.start,
1164 fragment_id: fragment.id.clone(),
1165 });
1166 }
1167
1168 if let Some(ref fragment) = after_range {
1169 new_split_tree.push(InsertionSplit {
1170 extent: fragment.end_offset() - range.end,
1171 fragment_id: fragment.id.clone(),
1172 });
1173 }
1174
1175 cursor.next();
1176 new_split_tree
1177 .push_tree(cursor.slice(&old_split_tree.extent::<usize>(), SeekBias::Right));
1178
1179 self.insertion_splits
1180 .insert(fragment.insertion.id, new_split_tree);
1181
1182 (before_range, within_range, after_range)
1183 }
1184 }
1185
1186 fn build_fragment_to_insert(
1187 &mut self,
1188 prev_fragment: &Fragment,
1189 next_fragment: Option<&Fragment>,
1190 text: Text,
1191 local_timestamp: time::Local,
1192 lamport_timestamp: time::Lamport,
1193 ) -> Fragment {
1194 let new_fragment_id = FragmentId::between(
1195 &prev_fragment.id,
1196 next_fragment
1197 .map(|f| &f.id)
1198 .unwrap_or(&FragmentId::max_value()),
1199 );
1200
1201 let mut split_tree = SumTree::new();
1202 split_tree.push(InsertionSplit {
1203 extent: text.len(),
1204 fragment_id: new_fragment_id.clone(),
1205 });
1206 self.insertion_splits.insert(local_timestamp, split_tree);
1207
1208 Fragment::new(
1209 new_fragment_id,
1210 Insertion {
1211 id: local_timestamp,
1212 parent_id: prev_fragment.insertion.id,
1213 offset_in_parent: prev_fragment.end_offset(),
1214 text,
1215 lamport_timestamp,
1216 },
1217 )
1218 }
1219
1220 pub fn anchor_before<T: ToOffset>(&self, position: T) -> Result<Anchor> {
1221 self.anchor_at(position, AnchorBias::Left)
1222 }
1223
1224 pub fn anchor_after<T: ToOffset>(&self, position: T) -> Result<Anchor> {
1225 self.anchor_at(position, AnchorBias::Right)
1226 }
1227
1228 pub fn anchor_at<T: ToOffset>(&self, position: T, bias: AnchorBias) -> Result<Anchor> {
1229 let offset = position.to_offset(self)?;
1230 let max_offset = self.len();
1231 if offset > max_offset {
1232 return Err(anyhow!("offset is out of range"));
1233 }
1234
1235 let seek_bias;
1236 match bias {
1237 AnchorBias::Left => {
1238 if offset == 0 {
1239 return Ok(Anchor::Start);
1240 } else {
1241 seek_bias = SeekBias::Left;
1242 }
1243 }
1244 AnchorBias::Right => {
1245 if offset == max_offset {
1246 return Ok(Anchor::End);
1247 } else {
1248 seek_bias = SeekBias::Right;
1249 }
1250 }
1251 };
1252
1253 let mut cursor = self.fragments.cursor::<usize, usize>();
1254 cursor.seek(&offset, seek_bias);
1255 let fragment = cursor.item().unwrap();
1256 let offset_in_fragment = offset - cursor.start();
1257 let offset_in_insertion = fragment.start_offset() + offset_in_fragment;
1258 let anchor = Anchor::Middle {
1259 insertion_id: fragment.insertion.id,
1260 offset: offset_in_insertion,
1261 bias,
1262 };
1263 Ok(anchor)
1264 }
1265
1266 fn fragment_id_for_anchor(&self, anchor: &Anchor) -> Result<&FragmentId> {
1267 match anchor {
1268 Anchor::Start => Ok(FragmentId::max_value()),
1269 Anchor::End => Ok(FragmentId::min_value()),
1270 Anchor::Middle {
1271 insertion_id,
1272 offset,
1273 bias,
1274 ..
1275 } => {
1276 let seek_bias = match bias {
1277 AnchorBias::Left => SeekBias::Left,
1278 AnchorBias::Right => SeekBias::Right,
1279 };
1280
1281 let splits = self
1282 .insertion_splits
1283 .get(&insertion_id)
1284 .ok_or_else(|| anyhow!("split does not exist for insertion id"))?;
1285 let mut splits_cursor = splits.cursor::<usize, ()>();
1286 splits_cursor.seek(offset, seek_bias);
1287 splits_cursor
1288 .item()
1289 .ok_or_else(|| anyhow!("split offset is out of range"))
1290 .map(|split| &split.fragment_id)
1291 }
1292 }
1293 }
1294
1295 fn summary_for_anchor(&self, anchor: &Anchor) -> Result<TextSummary> {
1296 match anchor {
1297 Anchor::Start => Ok(TextSummary::default()),
1298 Anchor::End => Ok(self.fragments.summary().text_summary),
1299 Anchor::Middle {
1300 insertion_id,
1301 offset,
1302 bias,
1303 } => {
1304 let seek_bias = match bias {
1305 AnchorBias::Left => SeekBias::Left,
1306 AnchorBias::Right => SeekBias::Right,
1307 };
1308
1309 let splits = self
1310 .insertion_splits
1311 .get(&insertion_id)
1312 .ok_or_else(|| anyhow!("split does not exist for insertion id"))?;
1313 let mut splits_cursor = splits.cursor::<usize, ()>();
1314 splits_cursor.seek(offset, seek_bias);
1315 let split = splits_cursor
1316 .item()
1317 .ok_or_else(|| anyhow!("split offset is out of range"))?;
1318
1319 let mut fragments_cursor = self.fragments.cursor::<FragmentIdRef, TextSummary>();
1320 fragments_cursor.seek(&FragmentIdRef::new(&split.fragment_id), SeekBias::Left);
1321 let fragment = fragments_cursor
1322 .item()
1323 .ok_or_else(|| anyhow!("fragment id does not exist"))?;
1324
1325 let mut summary = fragments_cursor.start().clone();
1326 if fragment.is_visible() {
1327 summary += fragment
1328 .text
1329 .slice(..offset - fragment.start_offset())
1330 .summary();
1331 }
1332 Ok(summary)
1333 }
1334 }
1335 }
1336
1337 #[allow(dead_code)]
1338 pub fn point_for_offset(&self, offset: usize) -> Result<Point> {
1339 let mut fragments_cursor = self.fragments.cursor::<usize, TextSummary>();
1340 fragments_cursor.seek(&offset, SeekBias::Left);
1341 fragments_cursor
1342 .item()
1343 .ok_or_else(|| anyhow!("offset is out of range"))
1344 .map(|fragment| {
1345 let overshoot = fragment
1346 .point_for_offset(offset - &fragments_cursor.start().chars)
1347 .unwrap();
1348 fragments_cursor.start().lines + &overshoot
1349 })
1350 }
1351}
1352
1353impl Clone for Buffer {
1354 fn clone(&self) -> Self {
1355 Self {
1356 file: self.file.clone(),
1357 fragments: self.fragments.clone(),
1358 insertion_splits: self.insertion_splits.clone(),
1359 version: self.version.clone(),
1360 last_edit: self.last_edit.clone(),
1361 selections: self.selections.clone(),
1362 selections_last_update: self.selections_last_update.clone(),
1363 deferred_ops: self.deferred_ops.clone(),
1364 deferred_replicas: self.deferred_replicas.clone(),
1365 replica_id: self.replica_id,
1366 local_clock: self.local_clock.clone(),
1367 lamport_clock: self.lamport_clock.clone(),
1368 }
1369 }
1370}
1371
1372#[derive(Clone, Debug, Eq, PartialEq)]
1373pub enum Event {
1374 Edited(Vec<Edit>),
1375}
1376
1377impl Entity for Buffer {
1378 type Event = Event;
1379}
1380
1381impl<'a> sum_tree::Dimension<'a, FragmentSummary> for Point {
1382 fn add_summary(&mut self, summary: &FragmentSummary) {
1383 *self += &summary.text_summary.lines;
1384 }
1385}
1386
1387impl<'a> Iterator for Chars<'a> {
1388 type Item = char;
1389
1390 fn next(&mut self) -> Option<Self::Item> {
1391 if let Some(char) = self.fragment_chars.next() {
1392 Some(char)
1393 } else {
1394 loop {
1395 self.fragments_cursor.next();
1396 if let Some(fragment) = self.fragments_cursor.item() {
1397 if fragment.is_visible() {
1398 self.fragment_chars = fragment.text.as_str().chars();
1399 return self.fragment_chars.next();
1400 }
1401 } else {
1402 return None;
1403 }
1404 }
1405 }
1406 }
1407}
1408
1409impl<'a, F: Fn(&FragmentSummary) -> bool> Iterator for Edits<'a, F> {
1410 type Item = Edit;
1411
1412 fn next(&mut self) -> Option<Self::Item> {
1413 let mut change: Option<Edit> = None;
1414
1415 while let Some(fragment) = self.cursor.item() {
1416 let new_offset = *self.cursor.start();
1417 let old_offset = (new_offset as isize - self.delta) as usize;
1418
1419 if !fragment.was_visible(&self.since) && fragment.is_visible() {
1420 if let Some(ref mut change) = change {
1421 if change.new_range.end == new_offset {
1422 change.new_range.end += fragment.len();
1423 self.delta += fragment.len() as isize;
1424 } else {
1425 break;
1426 }
1427 } else {
1428 change = Some(Edit {
1429 old_range: old_offset..old_offset,
1430 new_range: new_offset..new_offset + fragment.len(),
1431 });
1432 self.delta += fragment.len() as isize;
1433 }
1434 } else if fragment.was_visible(&self.since) && !fragment.is_visible() {
1435 if let Some(ref mut change) = change {
1436 if change.new_range.end == new_offset {
1437 change.old_range.end += fragment.len();
1438 self.delta -= fragment.len() as isize;
1439 } else {
1440 break;
1441 }
1442 } else {
1443 change = Some(Edit {
1444 old_range: old_offset..old_offset + fragment.len(),
1445 new_range: new_offset..new_offset,
1446 });
1447 self.delta -= fragment.len() as isize;
1448 }
1449 }
1450
1451 self.cursor.next();
1452 }
1453
1454 change
1455 }
1456}
1457
1458// pub fn diff(a: &[u16], b: &[u16]) -> Vec<Edit> {
1459// struct EditCollector<'a> {
1460// a: &'a [u16],
1461// b: &'a [u16],
1462// position: Point,
1463// changes: Vec<Edit>,
1464// }
1465//
1466// impl<'a> diffs::Diff for EditCollector<'a> {
1467// type Error = ();
1468//
1469// fn equal(&mut self, old: usize, _: usize, len: usize) -> Result<(), ()> {
1470// self.position += &Text::extent(&self.a[old..old + len]);
1471// Ok(())
1472// }
1473//
1474// fn delete(&mut self, old: usize, len: usize) -> Result<(), ()> {
1475// self.changes.push(Edit {
1476// range: self.position..self.position + &Text::extent(&self.a[old..old + len]),
1477// chars: Vec::new(),
1478// new_char_count: Point::zero(),
1479// });
1480// Ok(())
1481// }
1482//
1483// fn insert(&mut self, _: usize, new: usize, new_len: usize) -> Result<(), ()> {
1484// let new_char_count = Text::extent(&self.b[new..new + new_len]);
1485// self.changes.push(Edit {
1486// range: self.position..self.position,
1487// chars: Vec::from(&self.b[new..new + new_len]),
1488// new_char_count,
1489// });
1490// self.position += &new_char_count;
1491// Ok(())
1492// }
1493//
1494// fn replace(
1495// &mut self,
1496// old: usize,
1497// old_len: usize,
1498// new: usize,
1499// new_len: usize,
1500// ) -> Result<(), ()> {
1501// let old_extent = text::extent(&self.a[old..old + old_len]);
1502// let new_char_count = text::extent(&self.b[new..new + new_len]);
1503// self.changes.push(Edit {
1504// range: self.position..self.position + &old_extent,
1505// chars: Vec::from(&self.b[new..new + new_len]),
1506// new_char_count,
1507// });
1508// self.position += &new_char_count;
1509// Ok(())
1510// }
1511// }
1512//
1513// let mut collector = diffs::Replace::new(EditCollector {
1514// a,
1515// b,
1516// position: Point::zero(),
1517// changes: Vec::new(),
1518// });
1519// diffs::myers::diff(&mut collector, a, 0, a.len(), b, 0, b.len()).unwrap();
1520// collector.into_inner().changes
1521// }
1522
1523impl Selection {
1524 pub fn head(&self) -> &Anchor {
1525 if self.reversed {
1526 &self.start
1527 } else {
1528 &self.end
1529 }
1530 }
1531
1532 pub fn set_head<S>(&mut self, buffer: &Buffer, cursor: Anchor) {
1533 if cursor.cmp(self.tail(), buffer).unwrap() < Ordering::Equal {
1534 if !self.reversed {
1535 mem::swap(&mut self.start, &mut self.end);
1536 self.reversed = true;
1537 }
1538 self.start = cursor;
1539 } else {
1540 if self.reversed {
1541 mem::swap(&mut self.start, &mut self.end);
1542 self.reversed = false;
1543 }
1544 self.end = cursor;
1545 }
1546 }
1547
1548 pub fn tail(&self) -> &Anchor {
1549 if self.reversed {
1550 &self.end
1551 } else {
1552 &self.start
1553 }
1554 }
1555
1556 pub fn is_empty(&self, buffer: &Buffer) -> bool {
1557 self.start.to_offset(buffer).unwrap() == self.end.to_offset(buffer).unwrap()
1558 }
1559
1560 pub fn anchor_range(&self) -> Range<Anchor> {
1561 self.start.clone()..self.end.clone()
1562 }
1563}
1564
1565#[derive(Ord, PartialOrd, Eq, PartialEq, Clone, Debug)]
1566struct FragmentId(Arc<[u16]>);
1567
1568lazy_static! {
1569 static ref FRAGMENT_ID_EMPTY: FragmentId = FragmentId(Arc::from([]));
1570 static ref FRAGMENT_ID_MIN_VALUE: FragmentId = FragmentId(Arc::from([0 as u16]));
1571 static ref FRAGMENT_ID_MAX_VALUE: FragmentId = FragmentId(Arc::from([u16::max_value()]));
1572}
1573
1574impl Default for FragmentId {
1575 fn default() -> Self {
1576 FRAGMENT_ID_EMPTY.clone()
1577 }
1578}
1579
1580impl FragmentId {
1581 fn min_value() -> &'static Self {
1582 &FRAGMENT_ID_MIN_VALUE
1583 }
1584
1585 fn max_value() -> &'static Self {
1586 &FRAGMENT_ID_MAX_VALUE
1587 }
1588
1589 fn between(left: &Self, right: &Self) -> Self {
1590 Self::between_with_max(left, right, u16::max_value())
1591 }
1592
1593 fn between_with_max(left: &Self, right: &Self, max_value: u16) -> Self {
1594 let mut new_entries = Vec::new();
1595
1596 let left_entries = left.0.iter().cloned().chain(iter::repeat(0));
1597 let right_entries = right.0.iter().cloned().chain(iter::repeat(max_value));
1598 for (l, r) in left_entries.zip(right_entries) {
1599 let interval = r - l;
1600 if interval > 1 {
1601 new_entries.push(l + cmp::max(1, cmp::min(8, interval / 2)));
1602 break;
1603 } else {
1604 new_entries.push(l);
1605 }
1606 }
1607
1608 FragmentId(Arc::from(new_entries))
1609 }
1610}
1611
1612#[derive(Ord, PartialOrd, Eq, PartialEq, Clone, Debug, Default)]
1613struct FragmentIdRef<'a>(Option<&'a FragmentId>);
1614
1615impl<'a> FragmentIdRef<'a> {
1616 fn new(id: &'a FragmentId) -> Self {
1617 Self(Some(id))
1618 }
1619}
1620
1621impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FragmentIdRef<'a> {
1622 fn add_summary(&mut self, summary: &'a FragmentSummary) {
1623 self.0 = Some(&summary.max_fragment_id)
1624 }
1625}
1626
1627impl Fragment {
1628 fn new(id: FragmentId, insertion: Insertion) -> Self {
1629 Self {
1630 id,
1631 text: insertion.text.clone(),
1632 insertion,
1633 deletions: HashSet::new(),
1634 }
1635 }
1636
1637 fn start_offset(&self) -> usize {
1638 self.text.range().start
1639 }
1640
1641 fn set_start_offset(&mut self, offset: usize) {
1642 self.text = self.insertion.text.slice(offset..self.end_offset());
1643 }
1644
1645 fn end_offset(&self) -> usize {
1646 self.text.range().end
1647 }
1648
1649 fn set_end_offset(&mut self, offset: usize) {
1650 self.text = self.insertion.text.slice(self.start_offset()..offset);
1651 }
1652
1653 fn visible_len(&self) -> usize {
1654 if self.is_visible() {
1655 self.len()
1656 } else {
1657 0
1658 }
1659 }
1660
1661 fn len(&self) -> usize {
1662 self.text.len()
1663 }
1664
1665 fn is_visible(&self) -> bool {
1666 self.deletions.is_empty()
1667 }
1668
1669 fn was_visible(&self, version: &time::Global) -> bool {
1670 version.observed(self.insertion.id) && self.deletions.iter().all(|d| !version.observed(*d))
1671 }
1672
1673 fn point_for_offset(&self, offset: usize) -> Result<Point> {
1674 Ok(self.text.point_for_offset(offset))
1675 }
1676
1677 fn offset_for_point(&self, point: Point) -> Result<usize> {
1678 Ok(self.text.offset_for_point(point))
1679 }
1680}
1681
1682impl sum_tree::Item for Fragment {
1683 type Summary = FragmentSummary;
1684
1685 fn summary(&self) -> Self::Summary {
1686 let mut max_version = time::Global::new();
1687 max_version.observe(self.insertion.id);
1688 for deletion in &self.deletions {
1689 max_version.observe(*deletion);
1690 }
1691
1692 if self.is_visible() {
1693 FragmentSummary {
1694 text_summary: self.text.summary(),
1695 max_fragment_id: self.id.clone(),
1696 max_version,
1697 }
1698 } else {
1699 FragmentSummary {
1700 text_summary: TextSummary::default(),
1701 max_fragment_id: self.id.clone(),
1702 max_version,
1703 }
1704 }
1705 }
1706}
1707
1708impl<'a> AddAssign<&'a FragmentSummary> for FragmentSummary {
1709 fn add_assign(&mut self, other: &Self) {
1710 self.text_summary += &other.text_summary;
1711 debug_assert!(self.max_fragment_id <= other.max_fragment_id);
1712 self.max_fragment_id = other.max_fragment_id.clone();
1713 self.max_version.observe_all(&other.max_version);
1714 }
1715}
1716
1717impl Default for FragmentSummary {
1718 fn default() -> Self {
1719 FragmentSummary {
1720 text_summary: TextSummary::default(),
1721 max_fragment_id: FragmentId::min_value().clone(),
1722 max_version: time::Global::new(),
1723 }
1724 }
1725}
1726
1727impl<'a> sum_tree::Dimension<'a, FragmentSummary> for TextSummary {
1728 fn add_summary(&mut self, summary: &FragmentSummary) {
1729 *self += &summary.text_summary;
1730 }
1731}
1732
1733impl<'a> AddAssign<&'a FragmentExtent> for FragmentExtent {
1734 fn add_assign(&mut self, other: &Self) {
1735 self.chars += other.chars;
1736 self.lines += &other.lines;
1737 }
1738}
1739
1740impl Default for FragmentExtent {
1741 fn default() -> Self {
1742 FragmentExtent {
1743 lines: Point::zero(),
1744 chars: 0,
1745 }
1746 }
1747}
1748
1749impl<'a> sum_tree::Dimension<'a, FragmentSummary> for FragmentExtent {
1750 fn add_summary(&mut self, summary: &FragmentSummary) {
1751 self.chars += summary.text_summary.chars;
1752 self.lines += &summary.text_summary.lines;
1753 }
1754}
1755
1756impl<'a> sum_tree::Dimension<'a, FragmentSummary> for usize {
1757 fn add_summary(&mut self, summary: &FragmentSummary) {
1758 *self += summary.text_summary.chars;
1759 }
1760}
1761
1762impl sum_tree::Item for InsertionSplit {
1763 type Summary = InsertionSplitSummary;
1764
1765 fn summary(&self) -> Self::Summary {
1766 InsertionSplitSummary {
1767 extent: self.extent,
1768 }
1769 }
1770}
1771
1772impl<'a> AddAssign<&'a InsertionSplitSummary> for InsertionSplitSummary {
1773 fn add_assign(&mut self, other: &Self) {
1774 self.extent += other.extent;
1775 }
1776}
1777
1778impl Default for InsertionSplitSummary {
1779 fn default() -> Self {
1780 InsertionSplitSummary { extent: 0 }
1781 }
1782}
1783
1784impl<'a> sum_tree::Dimension<'a, InsertionSplitSummary> for usize {
1785 fn add_summary(&mut self, summary: &InsertionSplitSummary) {
1786 *self += &summary.extent;
1787 }
1788}
1789
1790impl Operation {
1791 fn replica_id(&self) -> ReplicaId {
1792 self.lamport_timestamp().replica_id
1793 }
1794
1795 fn lamport_timestamp(&self) -> time::Lamport {
1796 match self {
1797 Operation::Edit {
1798 lamport_timestamp, ..
1799 } => *lamport_timestamp,
1800 Operation::UpdateSelections {
1801 lamport_timestamp, ..
1802 } => *lamport_timestamp,
1803 }
1804 }
1805
1806 pub fn is_edit(&self) -> bool {
1807 match self {
1808 Operation::Edit { .. } => true,
1809 _ => false,
1810 }
1811 }
1812}
1813
1814impl operation_queue::Operation for Operation {
1815 fn timestamp(&self) -> time::Lamport {
1816 self.lamport_timestamp()
1817 }
1818}
1819
1820pub trait ToOffset {
1821 fn to_offset(&self, buffer: &Buffer) -> Result<usize>;
1822}
1823
1824impl ToOffset for Point {
1825 fn to_offset(&self, buffer: &Buffer) -> Result<usize> {
1826 let mut fragments_cursor = buffer.fragments.cursor::<Point, TextSummary>();
1827 fragments_cursor.seek(self, SeekBias::Left);
1828 fragments_cursor
1829 .item()
1830 .ok_or_else(|| anyhow!("point is out of range"))
1831 .map(|fragment| {
1832 let overshoot = fragment
1833 .offset_for_point(*self - fragments_cursor.start().lines)
1834 .unwrap();
1835 fragments_cursor.start().chars + overshoot
1836 })
1837 }
1838}
1839
1840impl ToOffset for usize {
1841 fn to_offset(&self, _: &Buffer) -> Result<usize> {
1842 Ok(*self)
1843 }
1844}
1845
1846impl ToOffset for Anchor {
1847 fn to_offset(&self, buffer: &Buffer) -> Result<usize> {
1848 Ok(buffer.summary_for_anchor(self)?.chars)
1849 }
1850}
1851
1852pub trait ToPoint {
1853 fn to_point(&self, buffer: &Buffer) -> Result<Point>;
1854}
1855
1856impl ToPoint for Anchor {
1857 fn to_point(&self, buffer: &Buffer) -> Result<Point> {
1858 Ok(buffer.summary_for_anchor(self)?.lines)
1859 }
1860}
1861
1862impl ToPoint for usize {
1863 fn to_point(&self, buffer: &Buffer) -> Result<Point> {
1864 let mut fragments_cursor = buffer.fragments.cursor::<usize, TextSummary>();
1865 fragments_cursor.seek(&self, SeekBias::Left);
1866 fragments_cursor
1867 .item()
1868 .ok_or_else(|| anyhow!("offset is out of range"))
1869 .map(|fragment| {
1870 let overshoot = fragment
1871 .point_for_offset(*self - &fragments_cursor.start().chars)
1872 .unwrap();
1873 fragments_cursor.start().lines + overshoot
1874 })
1875 }
1876}
1877
1878#[cfg(test)]
1879mod tests {
1880 use super::*;
1881 use std::collections::BTreeMap;
1882
1883 #[test]
1884 fn test_edit() -> Result<()> {
1885 let mut buffer = Buffer::new(0, "abc");
1886 assert_eq!(buffer.text(), "abc");
1887 buffer.edit(vec![3..3], "def", None)?;
1888 assert_eq!(buffer.text(), "abcdef");
1889 buffer.edit(vec![0..0], "ghi", None)?;
1890 assert_eq!(buffer.text(), "ghiabcdef");
1891 buffer.edit(vec![5..5], "jkl", None)?;
1892 assert_eq!(buffer.text(), "ghiabjklcdef");
1893 buffer.edit(vec![6..7], "", None)?;
1894 assert_eq!(buffer.text(), "ghiabjlcdef");
1895 buffer.edit(vec![4..9], "mno", None)?;
1896 assert_eq!(buffer.text(), "ghiamnoef");
1897
1898 Ok(())
1899 }
1900
1901 #[test]
1902 fn test_edit_events() {
1903 use gpui::App;
1904 use std::{cell::RefCell, rc::Rc};
1905
1906 App::test((), |mut app| async move {
1907 let buffer_1_events = Rc::new(RefCell::new(Vec::new()));
1908 let buffer_2_events = Rc::new(RefCell::new(Vec::new()));
1909
1910 let buffer1 = app.add_model(|_| Buffer::new(0, "abcdef"));
1911 let buffer2 = app.add_model(|_| Buffer::new(1, "abcdef"));
1912 let ops = buffer1.update(&mut app, |buffer, ctx| {
1913 let buffer_1_events = buffer_1_events.clone();
1914 ctx.subscribe(&buffer1, move |_, event, _| {
1915 buffer_1_events.borrow_mut().push(event.clone())
1916 });
1917 let buffer_2_events = buffer_2_events.clone();
1918 ctx.subscribe(&buffer2, move |_, event, _| {
1919 buffer_2_events.borrow_mut().push(event.clone())
1920 });
1921
1922 buffer.edit(Some(2..4), "XYZ", Some(ctx)).unwrap()
1923 });
1924 buffer2.update(&mut app, |buffer, ctx| {
1925 buffer.apply_ops(ops, Some(ctx)).unwrap();
1926 });
1927
1928 let buffer_1_events = buffer_1_events.borrow();
1929 assert_eq!(
1930 *buffer_1_events,
1931 vec![Event::Edited(vec![Edit {
1932 old_range: 2..4,
1933 new_range: 2..5
1934 }])]
1935 );
1936
1937 let buffer_2_events = buffer_2_events.borrow();
1938 assert_eq!(
1939 *buffer_2_events,
1940 vec![Event::Edited(vec![Edit {
1941 old_range: 2..4,
1942 new_range: 2..5
1943 }])]
1944 );
1945 });
1946 }
1947
1948 #[test]
1949 fn test_random_edits() {
1950 for seed in 0..100 {
1951 println!("{:?}", seed);
1952 let mut rng = &mut StdRng::seed_from_u64(seed);
1953
1954 let reference_string_len = rng.gen_range(0..3);
1955 let mut reference_string = RandomCharIter::new(&mut rng)
1956 .take(reference_string_len)
1957 .collect::<String>();
1958 let mut buffer = Buffer::new(0, reference_string.as_str());
1959 let mut buffer_versions = Vec::new();
1960
1961 for _i in 0..10 {
1962 let (old_ranges, new_text, _) = buffer.randomly_mutate(rng, None);
1963 for old_range in old_ranges.iter().rev() {
1964 reference_string = [
1965 &reference_string[0..old_range.start],
1966 new_text.as_str(),
1967 &reference_string[old_range.end..],
1968 ]
1969 .concat();
1970 }
1971 assert_eq!(buffer.text(), reference_string);
1972
1973 {
1974 let line_lengths = line_lengths_in_range(&buffer, 0..buffer.len());
1975
1976 for (len, rows) in &line_lengths {
1977 for row in rows {
1978 assert_eq!(buffer.line_len(*row).unwrap(), *len);
1979 }
1980 }
1981
1982 let (longest_column, longest_rows) = line_lengths.iter().next_back().unwrap();
1983 let rightmost_point = buffer.rightmost_point();
1984 assert_eq!(rightmost_point.column, *longest_column);
1985 assert!(longest_rows.contains(&rightmost_point.row));
1986 }
1987
1988 for _ in 0..5 {
1989 let end = rng.gen_range(0..buffer.len() + 1);
1990 let start = rng.gen_range(0..end + 1);
1991
1992 let line_lengths = line_lengths_in_range(&buffer, start..end);
1993 let (longest_column, longest_rows) = line_lengths.iter().next_back().unwrap();
1994 let range_sum = buffer.text_summary_for_range(start..end);
1995 assert_eq!(range_sum.rightmost_point.column, *longest_column);
1996 assert!(longest_rows.contains(&range_sum.rightmost_point.row));
1997 let range_text = &buffer.text()[start..end];
1998 assert_eq!(range_sum.chars, range_text.chars().count());
1999 assert_eq!(range_sum.bytes, range_text.len());
2000 }
2001
2002 if rng.gen_bool(0.3) {
2003 buffer_versions.push(buffer.clone());
2004 }
2005 }
2006
2007 for mut old_buffer in buffer_versions {
2008 let mut delta = 0_isize;
2009 for Edit {
2010 old_range,
2011 new_range,
2012 } in buffer.edits_since(old_buffer.version.clone())
2013 {
2014 let old_len = old_range.end - old_range.start;
2015 let new_len = new_range.end - new_range.start;
2016 let old_start = (old_range.start as isize + delta) as usize;
2017
2018 old_buffer
2019 .edit(
2020 Some(old_start..old_start + old_len),
2021 buffer.text_for_range(new_range).unwrap(),
2022 None,
2023 )
2024 .unwrap();
2025
2026 delta += new_len as isize - old_len as isize;
2027 }
2028 assert_eq!(old_buffer.text(), buffer.text());
2029 }
2030 }
2031 }
2032
2033 #[test]
2034 fn test_line_len() -> Result<()> {
2035 let mut buffer = Buffer::new(0, "");
2036 buffer.edit(vec![0..0], "abcd\nefg\nhij", None)?;
2037 buffer.edit(vec![12..12], "kl\nmno", None)?;
2038 buffer.edit(vec![18..18], "\npqrs\n", None)?;
2039 buffer.edit(vec![18..21], "\nPQ", None)?;
2040
2041 assert_eq!(buffer.line_len(0)?, 4);
2042 assert_eq!(buffer.line_len(1)?, 3);
2043 assert_eq!(buffer.line_len(2)?, 5);
2044 assert_eq!(buffer.line_len(3)?, 3);
2045 assert_eq!(buffer.line_len(4)?, 4);
2046 assert_eq!(buffer.line_len(5)?, 0);
2047 assert!(buffer.line_len(6).is_err());
2048
2049 Ok(())
2050 }
2051
2052 #[test]
2053 fn test_rightmost_point() -> Result<()> {
2054 let mut buffer = Buffer::new(0, "");
2055 assert_eq!(buffer.rightmost_point().row, 0);
2056 buffer.edit(vec![0..0], "abcd\nefg\nhij", None)?;
2057 assert_eq!(buffer.rightmost_point().row, 0);
2058 buffer.edit(vec![12..12], "kl\nmno", None)?;
2059 assert_eq!(buffer.rightmost_point().row, 2);
2060 buffer.edit(vec![18..18], "\npqrs", None)?;
2061 assert_eq!(buffer.rightmost_point().row, 2);
2062 buffer.edit(vec![10..12], "", None)?;
2063 assert_eq!(buffer.rightmost_point().row, 0);
2064 buffer.edit(vec![24..24], "tuv", None)?;
2065 assert_eq!(buffer.rightmost_point().row, 4);
2066
2067 println!("{:?}", buffer.text());
2068
2069 Ok(())
2070 }
2071
2072 #[test]
2073 fn test_text_summary_for_range() {
2074 let buffer = Buffer::new(0, "ab\nefg\nhklm\nnopqrs\ntuvwxyz");
2075 let text = Text::from(buffer.text());
2076
2077 assert_eq!(
2078 buffer.text_summary_for_range(1..3),
2079 text.slice(1..3).summary()
2080 );
2081 assert_eq!(
2082 buffer.text_summary_for_range(1..12),
2083 text.slice(1..12).summary()
2084 );
2085 assert_eq!(
2086 buffer.text_summary_for_range(0..20),
2087 text.slice(0..20).summary()
2088 );
2089 assert_eq!(
2090 buffer.text_summary_for_range(0..22),
2091 text.slice(0..22).summary()
2092 );
2093 assert_eq!(
2094 buffer.text_summary_for_range(7..22),
2095 text.slice(7..22).summary()
2096 );
2097 }
2098
2099 #[test]
2100 fn test_chars_at() -> Result<()> {
2101 let mut buffer = Buffer::new(0, "");
2102 buffer.edit(vec![0..0], "abcd\nefgh\nij", None)?;
2103 buffer.edit(vec![12..12], "kl\nmno", None)?;
2104 buffer.edit(vec![18..18], "\npqrs", None)?;
2105 buffer.edit(vec![18..21], "\nPQ", None)?;
2106
2107 let chars = buffer.chars_at(Point::new(0, 0))?;
2108 assert_eq!(chars.collect::<String>(), "abcd\nefgh\nijkl\nmno\nPQrs");
2109
2110 let chars = buffer.chars_at(Point::new(1, 0))?;
2111 assert_eq!(chars.collect::<String>(), "efgh\nijkl\nmno\nPQrs");
2112
2113 let chars = buffer.chars_at(Point::new(2, 0))?;
2114 assert_eq!(chars.collect::<String>(), "ijkl\nmno\nPQrs");
2115
2116 let chars = buffer.chars_at(Point::new(3, 0))?;
2117 assert_eq!(chars.collect::<String>(), "mno\nPQrs");
2118
2119 let chars = buffer.chars_at(Point::new(4, 0))?;
2120 assert_eq!(chars.collect::<String>(), "PQrs");
2121
2122 // Regression test:
2123 let mut buffer = Buffer::new(0, "");
2124 buffer.edit(vec![0..0], "[workspace]\nmembers = [\n \"xray_core\",\n \"xray_server\",\n \"xray_cli\",\n \"xray_wasm\",\n]\n", None)?;
2125 buffer.edit(vec![60..60], "\n", None)?;
2126
2127 let chars = buffer.chars_at(Point::new(6, 0))?;
2128 assert_eq!(chars.collect::<String>(), " \"xray_wasm\",\n]\n");
2129
2130 Ok(())
2131 }
2132
2133 // #[test]
2134 // fn test_point_for_offset() -> Result<()> {
2135 // let text = Text::from("abc\ndefgh\nijklm\nopq");
2136 // assert_eq!(text.point_for_offset(0)?, Point { row: 0, column: 0 });
2137 // assert_eq!(text.point_for_offset(1)?, Point { row: 0, column: 1 });
2138 // assert_eq!(text.point_for_offset(2)?, Point { row: 0, column: 2 });
2139 // assert_eq!(text.point_for_offset(3)?, Point { row: 0, column: 3 });
2140 // assert_eq!(text.point_for_offset(4)?, Point { row: 1, column: 0 });
2141 // assert_eq!(text.point_for_offset(5)?, Point { row: 1, column: 1 });
2142 // assert_eq!(text.point_for_offset(9)?, Point { row: 1, column: 5 });
2143 // assert_eq!(text.point_for_offset(10)?, Point { row: 2, column: 0 });
2144 // assert_eq!(text.point_for_offset(14)?, Point { row: 2, column: 4 });
2145 // assert_eq!(text.point_for_offset(15)?, Point { row: 2, column: 5 });
2146 // assert_eq!(text.point_for_offset(16)?, Point { row: 3, column: 0 });
2147 // assert_eq!(text.point_for_offset(17)?, Point { row: 3, column: 1 });
2148 // assert_eq!(text.point_for_offset(19)?, Point { row: 3, column: 3 });
2149 // assert!(text.point_for_offset(20).is_err());
2150 //
2151 // let text = Text::from("abc");
2152 // assert_eq!(text.point_for_offset(0)?, Point { row: 0, column: 0 });
2153 // assert_eq!(text.point_for_offset(1)?, Point { row: 0, column: 1 });
2154 // assert_eq!(text.point_for_offset(2)?, Point { row: 0, column: 2 });
2155 // assert_eq!(text.point_for_offset(3)?, Point { row: 0, column: 3 });
2156 // assert!(text.point_for_offset(4).is_err());
2157 // Ok(())
2158 // }
2159
2160 // #[test]
2161 // fn test_offset_for_point() -> Result<()> {
2162 // let text = Text::from("abc\ndefgh");
2163 // assert_eq!(text.offset_for_point(Point { row: 0, column: 0 })?, 0);
2164 // assert_eq!(text.offset_for_point(Point { row: 0, column: 1 })?, 1);
2165 // assert_eq!(text.offset_for_point(Point { row: 0, column: 2 })?, 2);
2166 // assert_eq!(text.offset_for_point(Point { row: 0, column: 3 })?, 3);
2167 // assert!(text.offset_for_point(Point { row: 0, column: 4 }).is_err());
2168 // assert_eq!(text.offset_for_point(Point { row: 1, column: 0 })?, 4);
2169 // assert_eq!(text.offset_for_point(Point { row: 1, column: 1 })?, 5);
2170 // assert_eq!(text.offset_for_point(Point { row: 1, column: 5 })?, 9);
2171 // assert!(text.offset_for_point(Point { row: 1, column: 6 }).is_err());
2172 //
2173 // let text = Text::from("abc");
2174 // assert_eq!(text.offset_for_point(Point { row: 0, column: 0 })?, 0);
2175 // assert_eq!(text.offset_for_point(Point { row: 0, column: 1 })?, 1);
2176 // assert_eq!(text.offset_for_point(Point { row: 0, column: 2 })?, 2);
2177 // assert_eq!(text.offset_for_point(Point { row: 0, column: 3 })?, 3);
2178 // assert!(text.offset_for_point(Point { row: 0, column: 4 }).is_err());
2179 // Ok(())
2180 // }
2181
2182 // #[test]
2183 // fn test_longest_row_in_range() -> Result<()> {
2184 // for seed in 0..100 {
2185 // println!("{:?}", seed);
2186 // let mut rng = &mut StdRng::seed_from_u64(seed);
2187 // let string_len = rng.gen_range(1, 10);
2188 // let string = RandomCharIter(&mut rng)
2189 // .take(string_len)
2190 // .collect::<String>();
2191 // let text = Text::from(string.as_ref());
2192 //
2193 // for _i in 0..10 {
2194 // let end = rng.gen_range(1, string.len() + 1);
2195 // let start = rng.gen_range(0, end);
2196 //
2197 // let mut cur_row = string[0..start].chars().filter(|c| *c == '\n').count() as u32;
2198 // let mut cur_row_len = 0;
2199 // let mut expected_longest_row = cur_row;
2200 // let mut expected_longest_row_len = cur_row_len;
2201 // for ch in string[start..end].chars() {
2202 // if ch == '\n' {
2203 // if cur_row_len > expected_longest_row_len {
2204 // expected_longest_row = cur_row;
2205 // expected_longest_row_len = cur_row_len;
2206 // }
2207 // cur_row += 1;
2208 // cur_row_len = 0;
2209 // } else {
2210 // cur_row_len += 1;
2211 // }
2212 // }
2213 // if cur_row_len > expected_longest_row_len {
2214 // expected_longest_row = cur_row;
2215 // expected_longest_row_len = cur_row_len;
2216 // }
2217 //
2218 // assert_eq!(
2219 // text.longest_row_in_range(start..end)?,
2220 // (expected_longest_row, expected_longest_row_len)
2221 // );
2222 // }
2223 // }
2224 // Ok(())
2225 // }
2226
2227 #[test]
2228 fn test_fragment_ids() {
2229 for seed in 0..10 {
2230 let rng = &mut StdRng::seed_from_u64(seed);
2231
2232 let mut ids = vec![FragmentId(Arc::from([0])), FragmentId(Arc::from([4]))];
2233 for _i in 0..100 {
2234 let index = rng.gen_range(1..ids.len());
2235
2236 let left = ids[index - 1].clone();
2237 let right = ids[index].clone();
2238 ids.insert(index, FragmentId::between_with_max(&left, &right, 4));
2239
2240 let mut sorted_ids = ids.clone();
2241 sorted_ids.sort();
2242 assert_eq!(ids, sorted_ids);
2243 }
2244 }
2245 }
2246
2247 #[test]
2248 fn test_anchors() -> Result<()> {
2249 let mut buffer = Buffer::new(0, "");
2250 buffer.edit(vec![0..0], "abc", None)?;
2251 let left_anchor = buffer.anchor_before(2).unwrap();
2252 let right_anchor = buffer.anchor_after(2).unwrap();
2253
2254 buffer.edit(vec![1..1], "def\n", None)?;
2255 assert_eq!(buffer.text(), "adef\nbc");
2256 assert_eq!(left_anchor.to_offset(&buffer).unwrap(), 6);
2257 assert_eq!(right_anchor.to_offset(&buffer).unwrap(), 6);
2258 assert_eq!(
2259 left_anchor.to_point(&buffer).unwrap(),
2260 Point { row: 1, column: 1 }
2261 );
2262 assert_eq!(
2263 right_anchor.to_point(&buffer).unwrap(),
2264 Point { row: 1, column: 1 }
2265 );
2266
2267 buffer.edit(vec![2..3], "", None)?;
2268 assert_eq!(buffer.text(), "adf\nbc");
2269 assert_eq!(left_anchor.to_offset(&buffer).unwrap(), 5);
2270 assert_eq!(right_anchor.to_offset(&buffer).unwrap(), 5);
2271 assert_eq!(
2272 left_anchor.to_point(&buffer).unwrap(),
2273 Point { row: 1, column: 1 }
2274 );
2275 assert_eq!(
2276 right_anchor.to_point(&buffer).unwrap(),
2277 Point { row: 1, column: 1 }
2278 );
2279
2280 buffer.edit(vec![5..5], "ghi\n", None)?;
2281 assert_eq!(buffer.text(), "adf\nbghi\nc");
2282 assert_eq!(left_anchor.to_offset(&buffer).unwrap(), 5);
2283 assert_eq!(right_anchor.to_offset(&buffer).unwrap(), 9);
2284 assert_eq!(
2285 left_anchor.to_point(&buffer).unwrap(),
2286 Point { row: 1, column: 1 }
2287 );
2288 assert_eq!(
2289 right_anchor.to_point(&buffer).unwrap(),
2290 Point { row: 2, column: 0 }
2291 );
2292
2293 buffer.edit(vec![7..9], "", None)?;
2294 assert_eq!(buffer.text(), "adf\nbghc");
2295 assert_eq!(left_anchor.to_offset(&buffer).unwrap(), 5);
2296 assert_eq!(right_anchor.to_offset(&buffer).unwrap(), 7);
2297 assert_eq!(
2298 left_anchor.to_point(&buffer).unwrap(),
2299 Point { row: 1, column: 1 },
2300 );
2301 assert_eq!(
2302 right_anchor.to_point(&buffer).unwrap(),
2303 Point { row: 1, column: 3 }
2304 );
2305
2306 // Ensure anchoring to a point is equivalent to anchoring to an offset.
2307 assert_eq!(
2308 buffer.anchor_before(Point { row: 0, column: 0 })?,
2309 buffer.anchor_before(0)?
2310 );
2311 assert_eq!(
2312 buffer.anchor_before(Point { row: 0, column: 1 })?,
2313 buffer.anchor_before(1)?
2314 );
2315 assert_eq!(
2316 buffer.anchor_before(Point { row: 0, column: 2 })?,
2317 buffer.anchor_before(2)?
2318 );
2319 assert_eq!(
2320 buffer.anchor_before(Point { row: 0, column: 3 })?,
2321 buffer.anchor_before(3)?
2322 );
2323 assert_eq!(
2324 buffer.anchor_before(Point { row: 1, column: 0 })?,
2325 buffer.anchor_before(4)?
2326 );
2327 assert_eq!(
2328 buffer.anchor_before(Point { row: 1, column: 1 })?,
2329 buffer.anchor_before(5)?
2330 );
2331 assert_eq!(
2332 buffer.anchor_before(Point { row: 1, column: 2 })?,
2333 buffer.anchor_before(6)?
2334 );
2335 assert_eq!(
2336 buffer.anchor_before(Point { row: 1, column: 3 })?,
2337 buffer.anchor_before(7)?
2338 );
2339 assert_eq!(
2340 buffer.anchor_before(Point { row: 1, column: 4 })?,
2341 buffer.anchor_before(8)?
2342 );
2343
2344 // Comparison between anchors.
2345 let anchor_at_offset_0 = buffer.anchor_before(0).unwrap();
2346 let anchor_at_offset_1 = buffer.anchor_before(1).unwrap();
2347 let anchor_at_offset_2 = buffer.anchor_before(2).unwrap();
2348
2349 assert_eq!(
2350 anchor_at_offset_0.cmp(&anchor_at_offset_0, &buffer)?,
2351 Ordering::Equal
2352 );
2353 assert_eq!(
2354 anchor_at_offset_1.cmp(&anchor_at_offset_1, &buffer)?,
2355 Ordering::Equal
2356 );
2357 assert_eq!(
2358 anchor_at_offset_2.cmp(&anchor_at_offset_2, &buffer)?,
2359 Ordering::Equal
2360 );
2361
2362 assert_eq!(
2363 anchor_at_offset_0.cmp(&anchor_at_offset_1, &buffer)?,
2364 Ordering::Less
2365 );
2366 assert_eq!(
2367 anchor_at_offset_1.cmp(&anchor_at_offset_2, &buffer)?,
2368 Ordering::Less
2369 );
2370 assert_eq!(
2371 anchor_at_offset_0.cmp(&anchor_at_offset_2, &buffer)?,
2372 Ordering::Less
2373 );
2374
2375 assert_eq!(
2376 anchor_at_offset_1.cmp(&anchor_at_offset_0, &buffer)?,
2377 Ordering::Greater
2378 );
2379 assert_eq!(
2380 anchor_at_offset_2.cmp(&anchor_at_offset_1, &buffer)?,
2381 Ordering::Greater
2382 );
2383 assert_eq!(
2384 anchor_at_offset_2.cmp(&anchor_at_offset_0, &buffer)?,
2385 Ordering::Greater
2386 );
2387 Ok(())
2388 }
2389
2390 #[test]
2391 fn test_anchors_at_start_and_end() -> Result<()> {
2392 let mut buffer = Buffer::new(0, "");
2393 let before_start_anchor = buffer.anchor_before(0).unwrap();
2394 let after_end_anchor = buffer.anchor_after(0).unwrap();
2395
2396 buffer.edit(vec![0..0], "abc", None)?;
2397 assert_eq!(buffer.text(), "abc");
2398 assert_eq!(before_start_anchor.to_offset(&buffer).unwrap(), 0);
2399 assert_eq!(after_end_anchor.to_offset(&buffer).unwrap(), 3);
2400
2401 let after_start_anchor = buffer.anchor_after(0).unwrap();
2402 let before_end_anchor = buffer.anchor_before(3).unwrap();
2403
2404 buffer.edit(vec![3..3], "def", None)?;
2405 buffer.edit(vec![0..0], "ghi", None)?;
2406 assert_eq!(buffer.text(), "ghiabcdef");
2407 assert_eq!(before_start_anchor.to_offset(&buffer).unwrap(), 0);
2408 assert_eq!(after_start_anchor.to_offset(&buffer).unwrap(), 3);
2409 assert_eq!(before_end_anchor.to_offset(&buffer).unwrap(), 6);
2410 assert_eq!(after_end_anchor.to_offset(&buffer).unwrap(), 9);
2411
2412 Ok(())
2413 }
2414
2415 #[test]
2416 fn test_is_modified() -> Result<()> {
2417 let mut buffer = Buffer::new(0, "abc");
2418 assert!(!buffer.is_modified());
2419 buffer.edit(vec![1..2], "", None)?;
2420 assert!(buffer.is_modified());
2421
2422 Ok(())
2423 }
2424
2425 #[test]
2426 fn test_random_concurrent_edits() {
2427 use crate::test::Network;
2428
2429 const PEERS: usize = 3;
2430
2431 for seed in 0..50 {
2432 println!("{:?}", seed);
2433 let mut rng = &mut StdRng::seed_from_u64(seed);
2434
2435 let base_text_len = rng.gen_range(0..10);
2436 let base_text = RandomCharIter::new(&mut rng)
2437 .take(base_text_len)
2438 .collect::<String>();
2439 let mut replica_ids = Vec::new();
2440 let mut buffers = Vec::new();
2441 let mut network = Network::new();
2442 for i in 0..PEERS {
2443 let buffer = Buffer::new(i as ReplicaId, base_text.as_str());
2444 buffers.push(buffer);
2445 replica_ids.push(i as u16);
2446 network.add_peer(i as u16);
2447 }
2448
2449 let mut mutation_count = 10;
2450 loop {
2451 let replica_index = rng.gen_range(0..PEERS);
2452 let replica_id = replica_ids[replica_index];
2453 let buffer = &mut buffers[replica_index];
2454 if mutation_count > 0 && rng.gen() {
2455 let (_, _, ops) = buffer.randomly_mutate(&mut rng, None);
2456 network.broadcast(replica_id, ops, &mut rng);
2457 mutation_count -= 1;
2458 } else if network.has_unreceived(replica_id) {
2459 buffer
2460 .apply_ops(network.receive(replica_id, &mut rng), None)
2461 .unwrap();
2462 }
2463
2464 if mutation_count == 0 && network.is_idle() {
2465 break;
2466 }
2467 }
2468
2469 for buffer in &buffers[1..] {
2470 assert_eq!(buffer.text(), buffers[0].text());
2471 assert_eq!(
2472 buffer.all_selections().collect::<HashMap<_, _>>(),
2473 buffers[0].all_selections().collect::<HashMap<_, _>>()
2474 );
2475 assert_eq!(
2476 buffer.all_selection_ranges().collect::<HashMap<_, _>>(),
2477 buffers[0].all_selection_ranges().collect::<HashMap<_, _>>()
2478 );
2479 }
2480 }
2481 }
2482
2483 impl Buffer {
2484 pub fn randomly_mutate<T>(
2485 &mut self,
2486 rng: &mut T,
2487 ctx: Option<&mut ModelContext<Self>>,
2488 ) -> (Vec<Range<usize>>, String, Vec<Operation>)
2489 where
2490 T: Rng,
2491 {
2492 // Randomly edit
2493 let (old_ranges, new_text, mut operations) = self.randomly_edit(rng, 5, ctx);
2494
2495 // Randomly add, remove or mutate selection sets.
2496 let replica_selection_sets = &self
2497 .all_selections()
2498 .map(|(set_id, _)| *set_id)
2499 .filter(|set_id| self.replica_id == set_id.replica_id)
2500 .collect::<Vec<_>>();
2501 let set_id = replica_selection_sets.choose(rng);
2502 if set_id.is_some() && rng.gen_bool(1.0 / 6.0) {
2503 let op = self.remove_selection_set(*set_id.unwrap()).unwrap();
2504 operations.push(op);
2505 } else {
2506 let mut ranges = Vec::new();
2507 for _ in 0..5 {
2508 let start = rng.gen_range(0..self.len() + 1);
2509 let start_point = self.point_for_offset(start).unwrap();
2510 let end = rng.gen_range(0..self.len() + 1);
2511 let end_point = self.point_for_offset(end).unwrap();
2512 ranges.push(start_point..end_point);
2513 }
2514
2515 let op = if set_id.is_none() || rng.gen_bool(1.0 / 5.0) {
2516 self.add_selection_set(ranges).unwrap().1
2517 } else {
2518 self.replace_selection_set(*set_id.unwrap(), ranges)
2519 .unwrap()
2520 };
2521 operations.push(op);
2522 }
2523
2524 (old_ranges, new_text, operations)
2525 }
2526 }
2527
2528 fn line_lengths_in_range(buffer: &Buffer, range: Range<usize>) -> BTreeMap<u32, HashSet<u32>> {
2529 let mut lengths = BTreeMap::new();
2530 for (row, line) in buffer.text()[range].lines().enumerate() {
2531 lengths
2532 .entry(line.len() as u32)
2533 .or_insert(HashSet::new())
2534 .insert(row as u32);
2535 }
2536 if lengths.is_empty() {
2537 let mut rows = HashSet::new();
2538 rows.insert(0);
2539 lengths.insert(0, rows);
2540 }
2541 lengths
2542 }
2543}