Repository: rust-lang/rust
File: library/alloc/src/collections/btree/map/tests.rs (Rust)

Code before:
// Two leafs where the second one ends up underfull and needs stealing at the end.
create_merge_test!(test_merge_14, 14);
// Two leafs where the second one ends up empty because the insertion finished at the root.
create_merge_test!(test_merge_12, 12);
// Three levels; insertion finished at the root.
create_merge_test!(test_merge_144, 144);
// Three levels; insertion finished at leaf while there is an empty node on the second level.
create_merge_test!(test_merge_145, 145);
// Tests for several randomly chosen sizes.
create_merge_test!(test_merge_170, 170);
create_merge_test!(test_merge_181, 181);
#[cfg(not(miri))] // Miri is too slow
create_merge_test!(test_merge_239, 239);
#[cfg(not(miri))] // Miri is too slow
create_merge_test!(test_merge_1700, 1700);

#[test]
#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
fn test_append_drop_leak() {
    let a = CrashTestDummy::new(0);
    let b = CrashTestDummy::new(1);
    let c = CrashTestDummy::new(2);
    let mut left = BTreeMap::new();
    let mut right = BTreeMap::new();
    left.insert(a.spawn(Panic::Never), ());
    left.insert(b.spawn(Panic::Never), ());
    left.insert(c.spawn(Panic::Never), ());
    right.insert(b.spawn(Panic::InDrop), ()); // first duplicate key, dropped during append
    right.insert(c.spawn(Panic::Never), ());

    catch_unwind(move || left.append(&mut right)).unwrap_err();
    assert_eq!(a.dropped(), 1);
    assert_eq!(b.dropped(), 1); // should be 2 were it not for Rust issue #47949
    assert_eq!(c.dropped(), 2);
}

#[test]
fn test_append_ord_chaos() {
    let mut map1 = BTreeMap::new();
    map1.insert(Cyclic3::A, ());
    map1.insert(Cyclic3::B, ());
    let mut map2 = BTreeMap::new();
    map2.insert(Cyclic3::A, ());
    map2.insert(Cyclic3::B, ());
    map2.insert(Cyclic3::C, ()); // lands first, before A
    map2.insert(Cyclic3::B, ()); // lands first, before C
    map1.check();
    map2.check(); // keys are not unique but still strictly ascending
    assert_eq!(map1.len(), 2);
    assert_eq!(map2.len(), 4);
    map1.append(&mut map2);

Review comment (suggestion):
There should also be a test where the conflict function panics, look at `test_append_drop_leak` below for some example code that you can adapt.

Code after:
    };
}

// These are mostly for testing the algorithm that "fixes" the right edge after insertion.
// Single node, merge conflicting key values.
create_merge_test!(test_merge_7, 7);
// Single node.
create_merge_test!(test_merge_9, 9);
// Two leafs that don't need fixing.
create_merge_test!(test_merge_17, 17);
// Two leafs where the second one ends up underfull and needs stealing at the end.
create_merge_test!(test_merge_14, 14);
// Two leafs where the second one ends up empty because the insertion finished at the root.
create_merge_test!(test_merge_12, 12);
// Three levels; insertion finished at the root.
create_merge_test!(test_merge_144, 144);
// Three levels; insertion finished at leaf while there is an empty node on the second level.
create_merge_test!(test_merge_145, 145);
// Tests for several randomly chosen sizes.
create_merge_test!(test_merge_170, 170);
create_merge_test!(test_merge_181, 181);
#[cfg(not(miri))] // Miri is too slow
create_merge_test!(test_merge_239, 239);
#[cfg(not(miri))] // Miri is too slow
create_merge_test!(test_merge_1700, 1700);

#[test]
#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
fn test_append_drop_leak() {
    let a = CrashTestDummy::new(0);
    let b = CrashTestDummy::new(1);
    let c = CrashTestDummy::new(2);
    let mut left = BTreeMap::new();
    let mut right = BTreeMap::new();
    left.insert(a.spawn(Panic::Never), ());
    left.insert(b.spawn(Panic::Never), ());
    left.insert(c.spawn(Panic::Never), ());
    right.insert(b.spawn(Panic::InDrop), ()); // first duplicate key, dropped during append
    right.insert(c.spawn(Panic::Never), ());

    catch_unwind(move || left.append(&mut right)).unwrap_err();
    assert_eq!(a.dropped(), 1);
    assert_eq!(b.dropped(), 1); // should be 2 were it not for Rust issue #47949
    assert_eq!(c.dropped(), 2);
}

#[test]
fn test_append_ord_chaos() {
    let mut map1 = BTreeMap::new();
    map1.insert(Cyclic3::A, ());
    map1.insert(Cyclic3::B, ());