1use super::*;
2use clock::ReplicaId;
3use rand::prelude::*;
4use std::{
5 cmp::Ordering,
6 env,
7 iter::Iterator,
8 time::{Duration, Instant},
9};
10
11#[cfg(test)]
12#[ctor::ctor]
13fn init_logger() {
14 // std::env::set_var("RUST_LOG", "info");
15 env_logger::init();
16}
17
18#[test]
19fn test_edit() {
20 let mut buffer = Buffer::new(0, 0, History::new("abc".into()));
21 assert_eq!(buffer.text(), "abc");
22 buffer.edit(vec![3..3], "def");
23 assert_eq!(buffer.text(), "abcdef");
24 buffer.edit(vec![0..0], "ghi");
25 assert_eq!(buffer.text(), "ghiabcdef");
26 buffer.edit(vec![5..5], "jkl");
27 assert_eq!(buffer.text(), "ghiabjklcdef");
28 buffer.edit(vec![6..7], "");
29 assert_eq!(buffer.text(), "ghiabjlcdef");
30 buffer.edit(vec![4..9], "mno");
31 assert_eq!(buffer.text(), "ghiamnoef");
32}
33
34#[gpui::test(iterations = 100)]
35fn test_random_edits(mut rng: StdRng) {
36 let operations = env::var("OPERATIONS")
37 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
38 .unwrap_or(10);
39
40 let reference_string_len = rng.gen_range(0..3);
41 let mut reference_string = RandomCharIter::new(&mut rng)
42 .take(reference_string_len)
43 .collect::<String>();
44 let mut buffer = Buffer::new(0, 0, History::new(reference_string.clone().into()));
45 buffer.history.group_interval = Duration::from_millis(rng.gen_range(0..=200));
46 let mut buffer_versions = Vec::new();
47 log::info!(
48 "buffer text {:?}, version: {:?}",
49 buffer.text(),
50 buffer.version()
51 );
52
53 for _i in 0..operations {
54 let (old_ranges, new_text, _) = buffer.randomly_edit(&mut rng, 5);
55 for old_range in old_ranges.iter().rev() {
56 reference_string.replace_range(old_range.clone(), &new_text);
57 }
58 assert_eq!(buffer.text(), reference_string);
59 log::info!(
60 "buffer text {:?}, version: {:?}",
61 buffer.text(),
62 buffer.version()
63 );
64
65 if rng.gen_bool(0.25) {
66 buffer.randomly_undo_redo(&mut rng);
67 reference_string = buffer.text();
68 log::info!(
69 "buffer text {:?}, version: {:?}",
70 buffer.text(),
71 buffer.version()
72 );
73 }
74
75 let range = buffer.random_byte_range(0, &mut rng);
76 assert_eq!(
77 buffer.text_summary_for_range::<TextSummary, _>(range.clone()),
78 TextSummary::from(&reference_string[range])
79 );
80
81 buffer.check_invariants();
82
83 if rng.gen_bool(0.3) {
84 buffer_versions.push((buffer.clone(), buffer.subscribe()));
85 }
86 }
87
88 for (old_buffer, subscription) in buffer_versions {
89 let edits = buffer
90 .edits_since::<usize>(&old_buffer.version)
91 .collect::<Vec<_>>();
92
93 log::info!(
94 "applying edits since version {:?} to old text: {:?}: {:?}",
95 old_buffer.version(),
96 old_buffer.text(),
97 edits,
98 );
99
100 let mut text = old_buffer.visible_text.clone();
101 for edit in edits {
102 let new_text: String = buffer.text_for_range(edit.new.clone()).collect();
103 text.replace(edit.new.start..edit.new.start + edit.old.len(), &new_text);
104 }
105 assert_eq!(text.to_string(), buffer.text());
106
107 for _ in 0..5 {
108 let end_ix = old_buffer.clip_offset(rng.gen_range(0..=old_buffer.len()), Bias::Right);
109 let start_ix = old_buffer.clip_offset(rng.gen_range(0..=end_ix), Bias::Left);
110 let range = old_buffer.anchor_before(start_ix)..old_buffer.anchor_after(end_ix);
111 let mut old_text = old_buffer.text_for_range(range.clone()).collect::<String>();
112 let edits = buffer
113 .edits_since_in_range::<usize>(&old_buffer.version, range.clone())
114 .collect::<Vec<_>>();
115 log::info!(
116 "applying edits since version {:?} to old text in range {:?}: {:?}: {:?}",
117 old_buffer.version(),
118 start_ix..end_ix,
119 old_text,
120 edits,
121 );
122
123 let new_text = buffer.text_for_range(range).collect::<String>();
124 for edit in edits {
125 old_text.replace_range(
126 edit.new.start..edit.new.start + edit.old_len(),
127 &new_text[edit.new],
128 );
129 }
130 assert_eq!(old_text, new_text);
131 }
132
133 let subscription_edits = subscription.consume();
134 log::info!(
135 "applying subscription edits since version {:?} to old text: {:?}: {:?}",
136 old_buffer.version(),
137 old_buffer.text(),
138 subscription_edits,
139 );
140
141 let mut text = old_buffer.visible_text.clone();
142 for edit in subscription_edits.into_inner() {
143 let new_text: String = buffer.text_for_range(edit.new.clone()).collect();
144 text.replace(edit.new.start..edit.new.start + edit.old.len(), &new_text);
145 }
146 assert_eq!(text.to_string(), buffer.text());
147 }
148}
149
150#[test]
151fn test_line_len() {
152 let mut buffer = Buffer::new(0, 0, History::new("".into()));
153 buffer.edit(vec![0..0], "abcd\nefg\nhij");
154 buffer.edit(vec![12..12], "kl\nmno");
155 buffer.edit(vec![18..18], "\npqrs\n");
156 buffer.edit(vec![18..21], "\nPQ");
157
158 assert_eq!(buffer.line_len(0), 4);
159 assert_eq!(buffer.line_len(1), 3);
160 assert_eq!(buffer.line_len(2), 5);
161 assert_eq!(buffer.line_len(3), 3);
162 assert_eq!(buffer.line_len(4), 4);
163 assert_eq!(buffer.line_len(5), 0);
164}
165
166#[test]
167fn test_text_summary_for_range() {
168 let buffer = Buffer::new(0, 0, History::new("ab\nefg\nhklm\nnopqrs\ntuvwxyz".into()));
169 assert_eq!(
170 buffer.text_summary_for_range::<TextSummary, _>(1..3),
171 TextSummary {
172 bytes: 2,
173 lines: Point::new(1, 0),
174 lines_utf16: PointUtf16::new(1, 0),
175 first_line_chars: 1,
176 last_line_chars: 0,
177 longest_row: 0,
178 longest_row_chars: 1,
179 }
180 );
181 assert_eq!(
182 buffer.text_summary_for_range::<TextSummary, _>(1..12),
183 TextSummary {
184 bytes: 11,
185 lines: Point::new(3, 0),
186 lines_utf16: PointUtf16::new(3, 0),
187 first_line_chars: 1,
188 last_line_chars: 0,
189 longest_row: 2,
190 longest_row_chars: 4,
191 }
192 );
193 assert_eq!(
194 buffer.text_summary_for_range::<TextSummary, _>(0..20),
195 TextSummary {
196 bytes: 20,
197 lines: Point::new(4, 1),
198 lines_utf16: PointUtf16::new(4, 1),
199 first_line_chars: 2,
200 last_line_chars: 1,
201 longest_row: 3,
202 longest_row_chars: 6,
203 }
204 );
205 assert_eq!(
206 buffer.text_summary_for_range::<TextSummary, _>(0..22),
207 TextSummary {
208 bytes: 22,
209 lines: Point::new(4, 3),
210 lines_utf16: PointUtf16::new(4, 3),
211 first_line_chars: 2,
212 last_line_chars: 3,
213 longest_row: 3,
214 longest_row_chars: 6,
215 }
216 );
217 assert_eq!(
218 buffer.text_summary_for_range::<TextSummary, _>(7..22),
219 TextSummary {
220 bytes: 15,
221 lines: Point::new(2, 3),
222 lines_utf16: PointUtf16::new(2, 3),
223 first_line_chars: 4,
224 last_line_chars: 3,
225 longest_row: 1,
226 longest_row_chars: 6,
227 }
228 );
229}
230
231#[test]
232fn test_chars_at() {
233 let mut buffer = Buffer::new(0, 0, History::new("".into()));
234 buffer.edit(vec![0..0], "abcd\nefgh\nij");
235 buffer.edit(vec![12..12], "kl\nmno");
236 buffer.edit(vec![18..18], "\npqrs");
237 buffer.edit(vec![18..21], "\nPQ");
238
239 let chars = buffer.chars_at(Point::new(0, 0));
240 assert_eq!(chars.collect::<String>(), "abcd\nefgh\nijkl\nmno\nPQrs");
241
242 let chars = buffer.chars_at(Point::new(1, 0));
243 assert_eq!(chars.collect::<String>(), "efgh\nijkl\nmno\nPQrs");
244
245 let chars = buffer.chars_at(Point::new(2, 0));
246 assert_eq!(chars.collect::<String>(), "ijkl\nmno\nPQrs");
247
248 let chars = buffer.chars_at(Point::new(3, 0));
249 assert_eq!(chars.collect::<String>(), "mno\nPQrs");
250
251 let chars = buffer.chars_at(Point::new(4, 0));
252 assert_eq!(chars.collect::<String>(), "PQrs");
253
254 // Regression test:
255 let mut buffer = Buffer::new(0, 0, History::new("".into()));
256 buffer.edit(vec![0..0], "[workspace]\nmembers = [\n \"xray_core\",\n \"xray_server\",\n \"xray_cli\",\n \"xray_wasm\",\n]\n");
257 buffer.edit(vec![60..60], "\n");
258
259 let chars = buffer.chars_at(Point::new(6, 0));
260 assert_eq!(chars.collect::<String>(), " \"xray_wasm\",\n]\n");
261}
262
263#[test]
264fn test_anchors() {
265 let mut buffer = Buffer::new(0, 0, History::new("".into()));
266 buffer.edit(vec![0..0], "abc");
267 let left_anchor = buffer.anchor_before(2);
268 let right_anchor = buffer.anchor_after(2);
269
270 buffer.edit(vec![1..1], "def\n");
271 assert_eq!(buffer.text(), "adef\nbc");
272 assert_eq!(left_anchor.to_offset(&buffer), 6);
273 assert_eq!(right_anchor.to_offset(&buffer), 6);
274 assert_eq!(left_anchor.to_point(&buffer), Point { row: 1, column: 1 });
275 assert_eq!(right_anchor.to_point(&buffer), Point { row: 1, column: 1 });
276
277 buffer.edit(vec![2..3], "");
278 assert_eq!(buffer.text(), "adf\nbc");
279 assert_eq!(left_anchor.to_offset(&buffer), 5);
280 assert_eq!(right_anchor.to_offset(&buffer), 5);
281 assert_eq!(left_anchor.to_point(&buffer), Point { row: 1, column: 1 });
282 assert_eq!(right_anchor.to_point(&buffer), Point { row: 1, column: 1 });
283
284 buffer.edit(vec![5..5], "ghi\n");
285 assert_eq!(buffer.text(), "adf\nbghi\nc");
286 assert_eq!(left_anchor.to_offset(&buffer), 5);
287 assert_eq!(right_anchor.to_offset(&buffer), 9);
288 assert_eq!(left_anchor.to_point(&buffer), Point { row: 1, column: 1 });
289 assert_eq!(right_anchor.to_point(&buffer), Point { row: 2, column: 0 });
290
291 buffer.edit(vec![7..9], "");
292 assert_eq!(buffer.text(), "adf\nbghc");
293 assert_eq!(left_anchor.to_offset(&buffer), 5);
294 assert_eq!(right_anchor.to_offset(&buffer), 7);
295 assert_eq!(left_anchor.to_point(&buffer), Point { row: 1, column: 1 },);
296 assert_eq!(right_anchor.to_point(&buffer), Point { row: 1, column: 3 });
297
298 // Ensure anchoring to a point is equivalent to anchoring to an offset.
299 assert_eq!(
300 buffer.anchor_before(Point { row: 0, column: 0 }),
301 buffer.anchor_before(0)
302 );
303 assert_eq!(
304 buffer.anchor_before(Point { row: 0, column: 1 }),
305 buffer.anchor_before(1)
306 );
307 assert_eq!(
308 buffer.anchor_before(Point { row: 0, column: 2 }),
309 buffer.anchor_before(2)
310 );
311 assert_eq!(
312 buffer.anchor_before(Point { row: 0, column: 3 }),
313 buffer.anchor_before(3)
314 );
315 assert_eq!(
316 buffer.anchor_before(Point { row: 1, column: 0 }),
317 buffer.anchor_before(4)
318 );
319 assert_eq!(
320 buffer.anchor_before(Point { row: 1, column: 1 }),
321 buffer.anchor_before(5)
322 );
323 assert_eq!(
324 buffer.anchor_before(Point { row: 1, column: 2 }),
325 buffer.anchor_before(6)
326 );
327 assert_eq!(
328 buffer.anchor_before(Point { row: 1, column: 3 }),
329 buffer.anchor_before(7)
330 );
331 assert_eq!(
332 buffer.anchor_before(Point { row: 1, column: 4 }),
333 buffer.anchor_before(8)
334 );
335
336 // Comparison between anchors.
337 let anchor_at_offset_0 = buffer.anchor_before(0);
338 let anchor_at_offset_1 = buffer.anchor_before(1);
339 let anchor_at_offset_2 = buffer.anchor_before(2);
340
341 assert_eq!(
342 anchor_at_offset_0
343 .cmp(&anchor_at_offset_0, &buffer)
344 .unwrap(),
345 Ordering::Equal
346 );
347 assert_eq!(
348 anchor_at_offset_1
349 .cmp(&anchor_at_offset_1, &buffer)
350 .unwrap(),
351 Ordering::Equal
352 );
353 assert_eq!(
354 anchor_at_offset_2
355 .cmp(&anchor_at_offset_2, &buffer)
356 .unwrap(),
357 Ordering::Equal
358 );
359
360 assert_eq!(
361 anchor_at_offset_0
362 .cmp(&anchor_at_offset_1, &buffer)
363 .unwrap(),
364 Ordering::Less
365 );
366 assert_eq!(
367 anchor_at_offset_1
368 .cmp(&anchor_at_offset_2, &buffer)
369 .unwrap(),
370 Ordering::Less
371 );
372 assert_eq!(
373 anchor_at_offset_0
374 .cmp(&anchor_at_offset_2, &buffer)
375 .unwrap(),
376 Ordering::Less
377 );
378
379 assert_eq!(
380 anchor_at_offset_1
381 .cmp(&anchor_at_offset_0, &buffer)
382 .unwrap(),
383 Ordering::Greater
384 );
385 assert_eq!(
386 anchor_at_offset_2
387 .cmp(&anchor_at_offset_1, &buffer)
388 .unwrap(),
389 Ordering::Greater
390 );
391 assert_eq!(
392 anchor_at_offset_2
393 .cmp(&anchor_at_offset_0, &buffer)
394 .unwrap(),
395 Ordering::Greater
396 );
397}
398
399#[test]
400fn test_anchors_at_start_and_end() {
401 let mut buffer = Buffer::new(0, 0, History::new("".into()));
402 let before_start_anchor = buffer.anchor_before(0);
403 let after_end_anchor = buffer.anchor_after(0);
404
405 buffer.edit(vec![0..0], "abc");
406 assert_eq!(buffer.text(), "abc");
407 assert_eq!(before_start_anchor.to_offset(&buffer), 0);
408 assert_eq!(after_end_anchor.to_offset(&buffer), 3);
409
410 let after_start_anchor = buffer.anchor_after(0);
411 let before_end_anchor = buffer.anchor_before(3);
412
413 buffer.edit(vec![3..3], "def");
414 buffer.edit(vec![0..0], "ghi");
415 assert_eq!(buffer.text(), "ghiabcdef");
416 assert_eq!(before_start_anchor.to_offset(&buffer), 0);
417 assert_eq!(after_start_anchor.to_offset(&buffer), 3);
418 assert_eq!(before_end_anchor.to_offset(&buffer), 6);
419 assert_eq!(after_end_anchor.to_offset(&buffer), 9);
420}
421
422#[test]
423fn test_undo_redo() {
424 let mut buffer = Buffer::new(0, 0, History::new("1234".into()));
425 // Set group interval to zero so as to not group edits in the undo stack.
426 buffer.history.group_interval = Duration::from_secs(0);
427
428 buffer.edit(vec![1..1], "abx");
429 buffer.edit(vec![3..4], "yzef");
430 buffer.edit(vec![3..5], "cd");
431 assert_eq!(buffer.text(), "1abcdef234");
432
433 let transactions = buffer.history.undo_stack.clone();
434 assert_eq!(transactions.len(), 3);
435
436 buffer.undo_or_redo(transactions[0].clone()).unwrap();
437 assert_eq!(buffer.text(), "1cdef234");
438 buffer.undo_or_redo(transactions[0].clone()).unwrap();
439 assert_eq!(buffer.text(), "1abcdef234");
440
441 buffer.undo_or_redo(transactions[1].clone()).unwrap();
442 assert_eq!(buffer.text(), "1abcdx234");
443 buffer.undo_or_redo(transactions[2].clone()).unwrap();
444 assert_eq!(buffer.text(), "1abx234");
445 buffer.undo_or_redo(transactions[1].clone()).unwrap();
446 assert_eq!(buffer.text(), "1abyzef234");
447 buffer.undo_or_redo(transactions[2].clone()).unwrap();
448 assert_eq!(buffer.text(), "1abcdef234");
449
450 buffer.undo_or_redo(transactions[2].clone()).unwrap();
451 assert_eq!(buffer.text(), "1abyzef234");
452 buffer.undo_or_redo(transactions[0].clone()).unwrap();
453 assert_eq!(buffer.text(), "1yzef234");
454 buffer.undo_or_redo(transactions[1].clone()).unwrap();
455 assert_eq!(buffer.text(), "1234");
456}
457
458#[test]
459fn test_history() {
460 let mut now = Instant::now();
461 let mut buffer = Buffer::new(0, 0, History::new("123456".into()));
462
463 let set_id = if let Operation::UpdateSelections { set_id, .. } =
464 buffer.add_selection_set(&buffer.selections_from_ranges(vec![4..4]).unwrap())
465 {
466 set_id
467 } else {
468 unreachable!()
469 };
470 buffer.start_transaction_at(Some(set_id), now).unwrap();
471 buffer.edit(vec![2..4], "cd");
472 buffer.end_transaction_at(Some(set_id), now).unwrap();
473 assert_eq!(buffer.text(), "12cd56");
474 assert_eq!(buffer.selection_ranges(set_id).unwrap(), vec![4..4]);
475
476 buffer.start_transaction_at(Some(set_id), now).unwrap();
477 buffer
478 .update_selection_set(set_id, &buffer.selections_from_ranges(vec![1..3]).unwrap())
479 .unwrap();
480 buffer.edit(vec![4..5], "e");
481 buffer.end_transaction_at(Some(set_id), now).unwrap();
482 assert_eq!(buffer.text(), "12cde6");
483 assert_eq!(buffer.selection_ranges(set_id).unwrap(), vec![1..3]);
484
485 now += buffer.history.group_interval + Duration::from_millis(1);
486 buffer.start_transaction_at(Some(set_id), now).unwrap();
487 buffer
488 .update_selection_set(set_id, &buffer.selections_from_ranges(vec![2..2]).unwrap())
489 .unwrap();
490 buffer.edit(vec![0..1], "a");
491 buffer.edit(vec![1..1], "b");
492 buffer.end_transaction_at(Some(set_id), now).unwrap();
493 assert_eq!(buffer.text(), "ab2cde6");
494 assert_eq!(buffer.selection_ranges(set_id).unwrap(), vec![3..3]);
495
496 // Last transaction happened past the group interval, undo it on its
497 // own.
498 buffer.undo();
499 assert_eq!(buffer.text(), "12cde6");
500 assert_eq!(buffer.selection_ranges(set_id).unwrap(), vec![1..3]);
501
502 // First two transactions happened within the group interval, undo them
503 // together.
504 buffer.undo();
505 assert_eq!(buffer.text(), "123456");
506 assert_eq!(buffer.selection_ranges(set_id).unwrap(), vec![4..4]);
507
508 // Redo the first two transactions together.
509 buffer.redo();
510 assert_eq!(buffer.text(), "12cde6");
511 assert_eq!(buffer.selection_ranges(set_id).unwrap(), vec![1..3]);
512
513 // Redo the last transaction on its own.
514 buffer.redo();
515 assert_eq!(buffer.text(), "ab2cde6");
516 assert_eq!(buffer.selection_ranges(set_id).unwrap(), vec![3..3]);
517
518 buffer.start_transaction_at(None, now).unwrap();
519 assert!(buffer.end_transaction_at(None, now).is_none());
520 buffer.undo();
521 assert_eq!(buffer.text(), "12cde6");
522}
523
524#[test]
525fn test_concurrent_edits() {
526 let text = "abcdef";
527
528 let mut buffer1 = Buffer::new(1, 0, History::new(text.into()));
529 let mut buffer2 = Buffer::new(2, 0, History::new(text.into()));
530 let mut buffer3 = Buffer::new(3, 0, History::new(text.into()));
531
532 let buf1_op = buffer1.edit(vec![1..2], "12");
533 assert_eq!(buffer1.text(), "a12cdef");
534 let buf2_op = buffer2.edit(vec![3..4], "34");
535 assert_eq!(buffer2.text(), "abc34ef");
536 let buf3_op = buffer3.edit(vec![5..6], "56");
537 assert_eq!(buffer3.text(), "abcde56");
538
539 buffer1.apply_op(Operation::Edit(buf2_op.clone())).unwrap();
540 buffer1.apply_op(Operation::Edit(buf3_op.clone())).unwrap();
541 buffer2.apply_op(Operation::Edit(buf1_op.clone())).unwrap();
542 buffer2.apply_op(Operation::Edit(buf3_op.clone())).unwrap();
543 buffer3.apply_op(Operation::Edit(buf1_op.clone())).unwrap();
544 buffer3.apply_op(Operation::Edit(buf2_op.clone())).unwrap();
545
546 assert_eq!(buffer1.text(), "a12c34e56");
547 assert_eq!(buffer2.text(), "a12c34e56");
548 assert_eq!(buffer3.text(), "a12c34e56");
549}
550
551#[gpui::test(iterations = 100)]
552fn test_random_concurrent_edits(mut rng: StdRng) {
553 let peers = env::var("PEERS")
554 .map(|i| i.parse().expect("invalid `PEERS` variable"))
555 .unwrap_or(5);
556 let operations = env::var("OPERATIONS")
557 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
558 .unwrap_or(10);
559
560 let base_text_len = rng.gen_range(0..10);
561 let base_text = RandomCharIter::new(&mut rng)
562 .take(base_text_len)
563 .collect::<String>();
564 let mut replica_ids = Vec::new();
565 let mut buffers = Vec::new();
566 let mut network = Network::new(rng.clone());
567
568 for i in 0..peers {
569 let mut buffer = Buffer::new(i as ReplicaId, 0, History::new(base_text.clone().into()));
570 buffer.history.group_interval = Duration::from_millis(rng.gen_range(0..=200));
571 buffers.push(buffer);
572 replica_ids.push(i as u16);
573 network.add_peer(i as u16);
574 }
575
576 log::info!("initial text: {:?}", base_text);
577
578 let mut mutation_count = operations;
579 loop {
580 let replica_index = rng.gen_range(0..peers);
581 let replica_id = replica_ids[replica_index];
582 let buffer = &mut buffers[replica_index];
583 match rng.gen_range(0..=100) {
584 0..=50 if mutation_count != 0 => {
585 let ops = buffer.randomly_mutate(&mut rng);
586 network.broadcast(buffer.replica_id, ops);
587 log::info!("buffer {} text: {:?}", buffer.replica_id, buffer.text());
588 mutation_count -= 1;
589 }
590 51..=70 if mutation_count != 0 => {
591 let ops = buffer.randomly_undo_redo(&mut rng);
592 network.broadcast(buffer.replica_id, ops);
593 mutation_count -= 1;
594 }
595 71..=100 if network.has_unreceived(replica_id) => {
596 let ops = network.receive(replica_id);
597 if !ops.is_empty() {
598 log::info!(
599 "peer {} applying {} ops from the network.",
600 replica_id,
601 ops.len()
602 );
603 buffer.apply_ops(ops).unwrap();
604 }
605 }
606 _ => {}
607 }
608 buffer.check_invariants();
609
610 if mutation_count == 0 && network.is_idle() {
611 break;
612 }
613 }
614
615 let first_buffer = &buffers[0];
616 for buffer in &buffers[1..] {
617 assert_eq!(
618 buffer.text(),
619 first_buffer.text(),
620 "Replica {} text != Replica 0 text",
621 buffer.replica_id
622 );
623 assert_eq!(
624 buffer.selection_sets().collect::<HashMap<_, _>>(),
625 first_buffer.selection_sets().collect::<HashMap<_, _>>()
626 );
627 assert_eq!(
628 buffer
629 .all_selection_ranges::<usize>()
630 .collect::<HashMap<_, _>>(),
631 first_buffer
632 .all_selection_ranges::<usize>()
633 .collect::<HashMap<_, _>>()
634 );
635 buffer.check_invariants();
636 }
637}
638
639#[derive(Clone)]
640struct Envelope<T: Clone> {
641 message: T,
642 sender: ReplicaId,
643}
644
645struct Network<T: Clone, R: rand::Rng> {
646 inboxes: std::collections::BTreeMap<ReplicaId, Vec<Envelope<T>>>,
647 all_messages: Vec<T>,
648 rng: R,
649}
650
651impl Buffer {
652 fn check_invariants(&self) {
653 // Ensure every fragment is ordered by locator in the fragment tree and corresponds
654 // to an insertion fragment in the insertions tree.
655 let mut prev_fragment_id = Locator::min();
656 for fragment in self.snapshot.fragments.items(&None) {
657 assert!(fragment.id > prev_fragment_id);
658 prev_fragment_id = fragment.id.clone();
659
660 let insertion_fragment = self
661 .snapshot
662 .insertions
663 .get(
664 &InsertionFragmentKey {
665 timestamp: fragment.insertion_timestamp.local(),
666 split_offset: fragment.insertion_offset,
667 },
668 &(),
669 )
670 .unwrap();
671 assert_eq!(insertion_fragment.fragment_id, fragment.id);
672 }
673
674 let mut cursor = self.snapshot.fragments.cursor::<Option<&Locator>>();
675 for insertion_fragment in self.snapshot.insertions.cursor::<()>() {
676 cursor.seek(&Some(&insertion_fragment.fragment_id), Bias::Left, &None);
677 let fragment = cursor.item().unwrap();
678 assert_eq!(insertion_fragment.fragment_id, fragment.id);
679 assert_eq!(insertion_fragment.split_offset, fragment.insertion_offset);
680 }
681 }
682}
683
684impl<T: Clone, R: rand::Rng> Network<T, R> {
685 fn new(rng: R) -> Self {
686 Network {
687 inboxes: Default::default(),
688 all_messages: Vec::new(),
689 rng,
690 }
691 }
692
693 fn add_peer(&mut self, id: ReplicaId) {
694 self.inboxes.insert(id, Vec::new());
695 }
696
697 fn is_idle(&self) -> bool {
698 self.inboxes.values().all(|i| i.is_empty())
699 }
700
701 fn broadcast(&mut self, sender: ReplicaId, messages: Vec<T>) {
702 for (replica, inbox) in self.inboxes.iter_mut() {
703 if *replica != sender {
704 for message in &messages {
705 let min_index = inbox
706 .iter()
707 .enumerate()
708 .rev()
709 .find_map(|(index, envelope)| {
710 if sender == envelope.sender {
711 Some(index + 1)
712 } else {
713 None
714 }
715 })
716 .unwrap_or(0);
717
718 // Insert one or more duplicates of this message *after* the previous
719 // message delivered by this replica.
720 for _ in 0..self.rng.gen_range(1..4) {
721 let insertion_index = self.rng.gen_range(min_index..inbox.len() + 1);
722 inbox.insert(
723 insertion_index,
724 Envelope {
725 message: message.clone(),
726 sender,
727 },
728 );
729 }
730 }
731 }
732 }
733 self.all_messages.extend(messages);
734 }
735
736 fn has_unreceived(&self, receiver: ReplicaId) -> bool {
737 !self.inboxes[&receiver].is_empty()
738 }
739
740 fn receive(&mut self, receiver: ReplicaId) -> Vec<T> {
741 let inbox = self.inboxes.get_mut(&receiver).unwrap();
742 let count = self.rng.gen_range(0..inbox.len() + 1);
743 inbox
744 .drain(0..count)
745 .map(|envelope| envelope.message)
746 .collect()
747 }
748}