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