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