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