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