[1.30 beta] Test suite of the collection crate is failing

[pietroalbini]

This is not a spurious failure (the test output is consistent between runs), but we need to investigate why this is happening.

• collection 0.1.1 regressed from stable to beta (build log) cc @krl

[pnkfelix]

visited at T-compiler triage. Assigning to self to do initial investigation.

[pnkfelix]

I have locally reproduced bug (by cloning the collection crate and running cargo test on it) on the current beta via rustup.

But the bug does not reproduce on the current nightly in rustup.

The bug also reproduces on the current nightly. (My previous claim was erroneous, as I forgot to update my nightly before running it.)

Bisecting now.

[pnkfelix]

Bisected over nightlies to determine this was injected between 7061b27 and 02cb8f2

% rustup override set nightly-2018-08-29-x86_64-unknown-linux-gnu
info: using existing install for 'nightly-2018-08-29-x86_64-unknown-linux-gnu'
info: override toolchain for '/home/pnkfelix/Dev/Mozilla/issue54477/collection' set to 'nightly-2018-08-29-x86_64-unknown-linux-gnu'

  nightly-2018-08-29-x86_64-unknown-linux-gnu unchanged - rustc 1.30.0-nightly (7061b2775 2018-08-28)

% cargo test set_remove
    Finished dev [unoptimized + debuginfo] target(s) in 0.11s
     Running target/debug/deps/collection-c314c206089f5030

running 1 test
test ops::set::tests::set_remove ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 26 filtered out

   Doc-tests collection

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

% rustup override set nightly-2018-08-30-x86_64-unknown-linux-gnu
info: using existing install for 'nightly-2018-08-30-x86_64-unknown-linux-gnu'
info: override toolchain for '/home/pnkfelix/Dev/Mozilla/issue54477/collection' set to 'nightly-2018-08-30-x86_64-unknown-linux-gnu'

  nightly-2018-08-30-x86_64-unknown-linux-gnu unchanged - rustc 1.30.0-nightly (02cb8f2a4 2018-08-29)

% cargo test set_remove
    Finished dev [unoptimized + debuginfo] target(s) in 0.10s
     Running target/debug/deps/collection-648e1050d7e72c52

running 1 test
test ops::set::tests::set_remove ... FAILED

failures:

---- ops::set::tests::set_remove stdout ----
thread 'ops::set::tests::set_remove' panicked at 'assertion failed: `(left == right)`
  left: `None`,
 right: `Some(69739)`', src/ops/set.rs:191:13
note: Run with `RUST_BACKTRACE=1` for a backtrace.


failures:
    ops::set::tests::set_remove

test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 26 filtered out

error: test failed, to rerun pass '--lib'
%

[pnkfelix]

Here's the log of bors merges over the range between 7061b27 and 02cb8f2

commit 02cb8f2a4f078025abe6ddba3cff81b383a23973
Merge: e6b35b0e11 21d2a6c986
Author: bors <bors@rust-lang.org>
Date:   Wed Aug 29 20:08:16 2018 +0000

    Auto merge of #53564 - MaloJaffre:vecdeque, r=gnzlbg

    Reoptimize VecDeque::append

    ~Unfortunately, I don't know if these changes fix the unsoundness mentioned in #53529, so it is stil a WIP.
    This is also completely untested.
    The VecDeque code contains other unsound code: one example : [reading unitialized memory](https://play.rust-lang.org/?gist=6ff47551769af61fd8adc45c44010887&version=nightly&mode=release&edition=2015) (detected by MIRI), so I think this code\
 will need a bigger refactor to make it clearer and safer.~

    Note: this is based on #53571.
    r? @SimonSapin
    Cc: #53529 #52553 @YorickPeterse @jonas-schievink @Pazzaz @shepmaster.

commit e6b35b0e1115f008796e8313574e4a4739b6d39d
Merge: ba48850409 b96fef6080
Author: bors <bors@rust-lang.org>
Date:   Wed Aug 29 13:35:25 2018 +0000

    Auto merge of #53758 - oli-obk:clippy, r=kennytm

    Update clippy submodule

    r? @Manishearth @nrc @kennytm

commit ba48850409222b2470fdc606329dc74aecbc0faa
Merge: ca0de63898 3cf6f0db1a
Author: bors <bors@rust-lang.org>
Date:   Wed Aug 29 10:55:27 2018 +0000

    Auto merge of #53245 - michaelwoerister:thinlto-rust-llvm, r=alexcrichton

    [experimental]: Build LLVM with ThinLTO enabled (2nd attempt)

    This is https://github.com/rust-lang/rust/pull/51207 revived. This time, I'd like to run actual performance tests to see if it improves compile times.

commit ca0de63898b525656ad8447cd81ccb08a05e3d6c
Merge: f4e981cfe4 025d01432f
Author: bors <bors@rust-lang.org>
Date:   Wed Aug 29 08:42:20 2018 +0000

    Auto merge of #53711 - arielb1:macro-table, r=michaelwoerister

    create a valid DefIdTable for proc macro crates

    At least the incremental compilation code, and a few other places in the
    compiler, require the CrateMetadata for a loaded target crate to contain a
    valid DefIdTable for the DefIds in the target.

    Previously, the CrateMetadata for a proc macro contained the crate's
    "host" DefIdTable, which is of course incompatible with the "target"
    DefIdTable, causing ICEs. This creates a DefIdTable that properly refers
    to the "proc macro" DefIds.

    Fixes #49482.

    r? @michaelwoerister

    Should we beta-nominate this?

commit f4e981cfe474f598b34ca07df8c8f16f042e120f
Merge: 29e6aabceb 51fd3bf6a8
Author: bors <bors@rust-lang.org>
Date:   Wed Aug 29 06:24:30 2018 +0000

    Auto merge of #53684 - alexcrichton:suggest-remove, r=oli-obk

    rustc: Suggest removing `extern crate` in 2018

    This commit updates the `unused_extern_crates` lint to make automatic
    suggestions about removing `extern crate` annotations in the 2018 edition. This
    ended up being a little easier than originally though due to what's likely been
    fixed issues in the resolver!

    Closes #52829

commit 29e6aabcebe3bdb507df22a6233024711412b343
Merge: 9d69e81e9b 8cecfa62e8
Author: bors <bors@rust-lang.org>
Date:   Wed Aug 29 04:20:01 2018 +0000

    Auto merge of #53659 - nnethercote:rm-AccumulateVec, r=Mark-Simulacrum

    Remove `AccumulateVec` and its uses.

    It's basically just a less capable version of `SmallVec`.

    FWIW, the only use of `ArrayVec` is now within `HybridIdxSet`.

    r? @Mark-Simulacrum

commit 9d69e81e9b400805b0453b9262958c8e28faa8a0
Merge: f1d02c3073 1fd45a13de
Author: bors <bors@rust-lang.org>
Date:   Wed Aug 29 02:08:02 2018 +0000

    Auto merge of #53642 - alexcrichton:fix-target-cpu-native, r=arielb1

    Fix warnings about the `native` target-cpu

    This fixes a regression from #53031 where specifying `-C target-cpu=native` is
    printing a lot of warnings from LLVM about `native` being an unknown CPU. It
    turns out that `native` is indeed an unknown CPU and we have to perform a
    mapping to an actual CPU name, but this mapping is only performed in one
    location rather than all locations we inform LLVM about the target CPU.

    This commit centralizes the mapping of `native` to LLVM's value of the native
    CPU, ensuring that all locations we inform LLVM about the `target-cpu` it's
    never `native`.

    Closes #53322

commit f1d02c307348057fd0554ad934006b186f8b6826
Merge: 7061b27757 c9b5fac7da
Author: bors <bors@rust-lang.org>
Date:   Wed Aug 29 00:02:37 2018 +0000

    Auto merge of #53671 - RalfJung:miri-refactor, r=oli-obk

    Miri engine cleanup

    * Unify the two maps in memory to store the allocation and its kind together.
    * Share the handling of statics between CTFE and miri: The miri engine always
          uses "lazy" `AllocType::Static` when encountering a static.  Acessing that
          static invokes CTFE (no matter the machine).  The machine only has any
          influence when writing to a static, which CTFE outright rejects (but miri
          makes a copy-on-write).
    * Add an `AllocId` to by-ref consts so miri can use them as operands without
          making copies.
    * Move responsibilities around for the `eval_fn_call` machine hook: The hook
          just has to find the MIR (or entirely take care of everything); pushing the
          new stack frame is taken care of by the miri engine.
    * Expose the intrinsics and lang items implemented by CTFE so miri does not
          have to reimplement them.
    * Allow Machine to hook into foreign statics (used by miri to get rid of some other hacks).
    * Clean up function calling.
    * Switch const sanity check to work on operands, not mplaces.
    * Move const_eval out of rustc_mir::interpret, to make sure that it does not access private implementation details.

    In particular, we can finally make `eval_operand` take `&self`. :-)

    Should be merged after https://github.com/rust-lang/rust/pull/53609, across which I will rebase.

[pnkfelix]

Based solely on skimming that list of PR's, I would be inclined to double-check the VecDeque change.

its possible its actually the MIRI change... but that's not my first guess.

In the meantime, I'm working on reducing the test case. I currently have it down to a single standalone file, but its still 3.6K lines...

[pnkfelix]

Okay, at this point I have confirmed that reverting #53564 fixes this bug.

We should revert #53564.

I haven't finished reducing my test case as much as I would like, but I can post what I have.

Its in this gist:
https://gist.github.com/pnkfelix/d8541c9e8ee240d02a4aa133a1fe0adc

Here's a demo of stable working:
https://play.rust-lang.org/?version=stable&gist=d8541c9e8ee240d02a4aa133a1fe0adc

And here's what happens on beta:
https://play.rust-lang.org/?version=beta&gist=d8541c9e8ee240d02a4aa133a1fe0adc

thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `None`,
 right: `Some(81)`', src/main.rs:1261:13

[pnkfelix]

Unassigning myself as I cannot devote further time to this and it seems like it should be handled by the libs team at this point.

The good idea that I just had, unfortunately too late:

make an instrumented wrapper around VecDeque that prints out every operation that is called.
that way we'd be able to narrow it to a trivial series of operations on VecDeque that reproduce the bug.

that would be a good way to reduce the test case to something really trivial.

[alexcrichton]

Thanks so much for flagging this @pietroalbini and tracking this down @pnkfelix! That's an impressive investigation @pnkfelix!

I can take it from here with reverts

[RalfJung]

Interestingly, miri does not see any UB here. Not that this makes the bug less of a problem, but this could mean it's "just" a plain functional mistake (or UB that miri cannot detect ;)

[pnkfelix]

Okay I got back from my evening at a waterpark and decided to try implementing my idea of an instruemented VecDeque to create a far reduced test case.

I've gotten as far as generating the following log from the instrumentation

created VecDeque[0] with contents: []
VecDeque[0].insert(0, Leaf(0))
VecDeque[0].insert(1, Leaf(1))
VecDeque[0].insert(2, Leaf(2))
created VecDeque[1] with contents: [Node { location: Location { ofs: 0, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(2) } }]
VecDeque[0].split_off(2)
created VecDeque[2] with contents: [Leaf(2)]
VecDeque[1].insert(0, Node { location: Location { ofs: 2, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(1) } })
VecDeque[2].insert(1, Leaf(3))
VecDeque[2].insert(2, Leaf(4))
VecDeque[2].insert(3, Leaf(5))
VecDeque[2].insert(4, Leaf(6))
VecDeque[2].insert(5, Leaf(7))
VecDeque[2].insert(6, Leaf(8))
VecDeque[2].insert(7, Leaf(9))
VecDeque[2].split_off(7)
created VecDeque[3] with contents: [Leaf(9)]
VecDeque[1].insert(1, Node { location: Location { ofs: 3, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(8) } })
VecDeque[3].insert(1, Leaf(10))
VecDeque[3].insert(2, Leaf(11))
VecDeque[3].insert(3, Leaf(12))
VecDeque[3].split_off(3)
created VecDeque[4] with contents: [Leaf(12)]
VecDeque[1].insert(2, Node { location: Location { ofs: 4, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(11) } })
VecDeque[4].insert(1, Leaf(13))
VecDeque[4].insert(2, Leaf(14))
VecDeque[4].insert(3, Leaf(15))
VecDeque[4].split_off(3)
created VecDeque[5] with contents: [Leaf(15)]
VecDeque[1].insert(3, Node { location: Location { ofs: 5, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(14) } })
VecDeque[5].insert(1, Leaf(16))
VecDeque[5].split_off(1)
created VecDeque[6] with contents: [Leaf(16)]
VecDeque[1].insert(4, Node { location: Location { ofs: 6, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(15) } })
VecDeque[6].insert(1, Leaf(17))
VecDeque[6].insert(2, Leaf(18))
VecDeque[6].insert(3, Leaf(19))
VecDeque[6].insert(4, Leaf(20))
VecDeque[6].insert(5, Leaf(21))
VecDeque[6].insert(6, Leaf(22))
VecDeque[6].insert(7, Leaf(23))
VecDeque[6].insert(8, Leaf(24))
created VecDeque[7] with contents: [Node { location: Location { ofs: 1, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(23) } }]
created VecDeque[8] with contents: [Node { location: Location { ofs: 7, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(23) } }]
VecDeque[6].split_off(8)
created VecDeque[9] with contents: [Leaf(24)]
VecDeque[1].insert(5, Node { location: Location { ofs: 9, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(23) } })
VecDeque[1].split_off(6)
created VecDeque[10] with contents: [Node { location: Location { ofs: 0, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(23) } }]
VecDeque[7].insert(0, Node { location: Location { ofs: 10, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(23) } })
VecDeque[7].split_off(1)
created VecDeque[11] with contents: [Node { location: Location { ofs: 1, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(23) } }]
VecDeque[8].insert(0, Node { location: Location { ofs: 11, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(23) } })
VecDeque[9].insert(1, Leaf(25))
VecDeque[9].split_off(1)
created VecDeque[12] with contents: [Leaf(25)]
VecDeque[10].insert(0, Node { location: Location { ofs: 12, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(24) } })
VecDeque[10].split_off(1)
created VecDeque[13] with contents: [Node { location: Location { ofs: 0, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(24) } }]
VecDeque[11].insert(0, Node { location: Location { ofs: 13, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(24) } })
VecDeque[12].insert(1, Leaf(26))
VecDeque[12].insert(2, Leaf(27))
VecDeque[12].split_off(2)
created VecDeque[14] with contents: [Leaf(27)]
VecDeque[13].insert(0, Node { location: Location { ofs: 14, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(26) } })
VecDeque[14].insert(1, Leaf(28))
VecDeque[14].insert(2, Leaf(29))
VecDeque[14].insert(3, Leaf(30))
VecDeque[14].insert(4, Leaf(31))
VecDeque[14].insert(5, Leaf(32))
VecDeque[14].insert(6, Leaf(33))
VecDeque[14].insert(7, Leaf(34))
VecDeque[14].insert(8, Leaf(35))
VecDeque[14].insert(9, Leaf(36))
VecDeque[14].insert(10, Leaf(37))
VecDeque[14].split_off(10)
created VecDeque[15] with contents: [Leaf(37)]
VecDeque[13].insert(1, Node { location: Location { ofs: 15, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(36) } })
VecDeque[15].insert(1, Leaf(38))
VecDeque[15].split_off(1)
created VecDeque[16] with contents: [Leaf(38)]
VecDeque[13].insert(2, Node { location: Location { ofs: 16, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(37) } })
VecDeque[16].insert(1, Leaf(39))
VecDeque[16].insert(2, Leaf(40))
VecDeque[16].insert(3, Leaf(41))
VecDeque[16].insert(4, Leaf(42))
VecDeque[16].insert(5, Leaf(43))
VecDeque[16].insert(6, Leaf(44))
VecDeque[16].split_off(6)
created VecDeque[17] with contents: [Leaf(44)]
VecDeque[13].insert(3, Node { location: Location { ofs: 17, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(43) } })
VecDeque[13].split_off(4)
created VecDeque[18] with contents: [Node { location: Location { ofs: 0, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(43) } }]
VecDeque[11].insert(1, Node { location: Location { ofs: 18, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(43) } })
VecDeque[17].insert(1, Leaf(45))
VecDeque[17].insert(2, Leaf(46))
VecDeque[17].insert(3, Leaf(47))
VecDeque[17].insert(4, Leaf(48))
VecDeque[17].insert(5, Leaf(49))
VecDeque[17].insert(6, Leaf(50))
VecDeque[17].insert(7, Leaf(51))
VecDeque[17].insert(8, Leaf(52))
VecDeque[17].insert(9, Leaf(53))
VecDeque[17].split_off(9)
created VecDeque[19] with contents: [Leaf(53)]
VecDeque[18].insert(0, Node { location: Location { ofs: 19, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(52) } })
VecDeque[19].insert(1, Leaf(54))
VecDeque[19].insert(2, Leaf(55))
VecDeque[19].insert(3, Leaf(56))
VecDeque[19].split_off(3)
created VecDeque[20] with contents: [Leaf(56)]
VecDeque[18].insert(1, Node { location: Location { ofs: 20, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(55) } })
VecDeque[20].insert(1, Leaf(57))
VecDeque[20].split_off(1)
created VecDeque[21] with contents: [Leaf(57)]
VecDeque[18].insert(2, Node { location: Location { ofs: 21, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(56) } })
VecDeque[21].insert(1, Leaf(58))
VecDeque[21].insert(2, Leaf(59))
VecDeque[21].insert(3, Leaf(60))
VecDeque[21].insert(4, Leaf(61))
VecDeque[21].split_off(4)
created VecDeque[22] with contents: [Leaf(61)]
VecDeque[18].insert(3, Node { location: Location { ofs: 22, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(60) } })
VecDeque[22].insert(1, Leaf(62))
VecDeque[22].split_off(1)
created VecDeque[23] with contents: [Leaf(62)]
VecDeque[18].insert(4, Node { location: Location { ofs: 23, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(61) } })
VecDeque[23].insert(1, Leaf(63))
VecDeque[23].insert(2, Leaf(64))
VecDeque[23].insert(3, Leaf(65))
VecDeque[23].insert(4, Leaf(66))
VecDeque[23].insert(5, Leaf(67))
VecDeque[23].insert(6, Leaf(68))
VecDeque[23].insert(7, Leaf(69))
VecDeque[23].split_off(7)
created VecDeque[24] with contents: [Leaf(69)]
VecDeque[18].insert(5, Node { location: Location { ofs: 24, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(68) } })
VecDeque[24].insert(1, Leaf(70))
VecDeque[24].insert(2, Leaf(71))
VecDeque[24].insert(3, Leaf(72))
VecDeque[24].insert(4, Leaf(73))
VecDeque[24].insert(5, Leaf(74))
VecDeque[24].insert(6, Leaf(75))
VecDeque[24].split_off(6)
created VecDeque[25] with contents: [Leaf(75)]
VecDeque[18].insert(6, Node { location: Location { ofs: 25, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(74) } })
VecDeque[25].insert(1, Leaf(76))
VecDeque[25].split_off(1)
created VecDeque[26] with contents: [Leaf(76)]
VecDeque[18].insert(7, Node { location: Location { ofs: 26, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(75) } })
VecDeque[18].split_off(8)
created VecDeque[27] with contents: [Node { location: Location { ofs: 0, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(75) } }]
VecDeque[11].insert(2, Node { location: Location { ofs: 27, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(75) } })
VecDeque[26].insert(1, Leaf(77))
VecDeque[26].insert(2, Leaf(78))
VecDeque[26].insert(3, Leaf(79))
VecDeque[26].insert(4, Leaf(80))
VecDeque[26].split_off(4)
created VecDeque[28] with contents: [Leaf(80)]
VecDeque[27].insert(0, Node { location: Location { ofs: 28, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(79) } })
VecDeque[27].split_off(1)
created VecDeque[29] with contents: [Node { location: Location { ofs: 0, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(79) } }]
VecDeque[11].insert(3, Node { location: Location { ofs: 29, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(79) } })
VecDeque[28].insert(1, Leaf(81))
VecDeque[28].insert(2, Leaf(82))
VecDeque[28].split_off(2)
created VecDeque[30] with contents: [Leaf(82)]
VecDeque[29].insert(0, Node { location: Location { ofs: 30, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(81) } })
VecDeque[30].insert(1, Leaf(83))
VecDeque[30].insert(2, Leaf(84))
VecDeque[30].insert(3, Leaf(85))
VecDeque[30].split_off(3)
created VecDeque[31] with contents: [Leaf(85)]
VecDeque[29].insert(1, Node { location: Location { ofs: 31, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(84) } })
VecDeque[31].insert(1, Leaf(86))
VecDeque[31].insert(2, Leaf(87))
VecDeque[31].split_off(2)
created VecDeque[32] with contents: [Leaf(87)]
VecDeque[29].insert(2, Node { location: Location { ofs: 32, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(86) } })
VecDeque[32].insert(1, Leaf(88))
VecDeque[32].insert(2, Leaf(89))
VecDeque[32].split_off(2)
created VecDeque[33] with contents: [Leaf(89)]
VecDeque[29].insert(3, Node { location: Location { ofs: 33, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(88) } })
VecDeque[33].insert(1, Leaf(90))
VecDeque[33].insert(2, Leaf(91))
VecDeque[33].split_off(2)
created VecDeque[34] with contents: [Leaf(91)]
VecDeque[29].insert(4, Node { location: Location { ofs: 34, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(90) } })
VecDeque[34].insert(1, Leaf(92))
VecDeque[34].split_off(1)
created VecDeque[35] with contents: [Leaf(92)]
VecDeque[29].insert(5, Node { location: Location { ofs: 35, depth: 0, _t: PhantomData, _m: PhantomData }, meta: CollectionMeta { _t: PhantomData, max: Max(91) } })
VecDeque[35].insert(1, Leaf(93))
VecDeque[35].insert(2, Leaf(94))
VecDeque[35].insert(3, Leaf(95))
VecDeque[35].insert(4, Leaf(96))
VecDeque[35].insert(5, Leaf(97))
VecDeque[35].insert(6, Leaf(98))
VecDeque[35].insert(7, Leaf(99))
VecDeque[0].remove(1)
VecDeque[1].remove(1)
created VecDeque[36] with contents: []
VecDeque[0].append(VecDeque[2])
VecDeque[0].remove(2)
VecDeque[0].remove(3)
VecDeque[0].remove(4)
VecDeque[3].remove(0)
VecDeque[3].remove(1)
VecDeque[1].remove(2)
created VecDeque[37] with contents: []
VecDeque[3].append(VecDeque[4])
VecDeque[3].remove(2)
VecDeque[5].remove(0)
VecDeque[1].remove(3)
created VecDeque[38] with contents: []
VecDeque[5].append(VecDeque[6])
VecDeque[5].remove(1)
VecDeque[5].remove(2)
VecDeque[5].remove(3)
VecDeque[5].remove(4)
VecDeque[8].remove(1)
created VecDeque[39] with contents: []
VecDeque[7].append(VecDeque[11])
VecDeque[7].remove(1)
created VecDeque[40] with contents: []
VecDeque[1].append(VecDeque[10])
VecDeque[1].remove(3)
created VecDeque[41] with contents: []
VecDeque[5].append(VecDeque[9])
VecDeque[12].remove(0)
VecDeque[14].remove(0)
VecDeque[14].remove(1)
VecDeque[14].remove(2)
VecDeque[14].remove(3)
VecDeque[14].remove(4)
VecDeque[15].remove(0)
VecDeque[13].remove(3)
created VecDeque[42] with contents: []
VecDeque[15].append(VecDeque[16])
VecDeque[15].remove(1)
VecDeque[15].remove(2)
VecDeque[15].remove(3)
VecDeque[7].remove(2)
created VecDeque[43] with contents: []
VecDeque[13].append(VecDeque[18])
VecDeque[13].remove(3)
created VecDeque[44] with contents: []
VecDeque[15].append(VecDeque[17])
VecDeque[15].remove(4)
VecDeque[15].remove(5)
VecDeque[15].remove(6)
VecDeque[15].remove(7)
VecDeque[19].remove(0)
VecDeque[19].remove(1)
VecDeque[13].remove(4)
created VecDeque[45] with contents: []
VecDeque[19].append(VecDeque[20])
VecDeque[21].remove(0)
VecDeque[21].remove(1)
VecDeque[22].remove(0)
VecDeque[13].remove(6)
created VecDeque[46] with contents: []
VecDeque[22].append(VecDeque[23])
VecDeque[22].remove(1)
VecDeque[22].remove(2)
VecDeque[22].remove(3)
VecDeque[24].remove(0)
VecDeque[24].remove(1)
VecDeque[24].remove(2)
VecDeque[25].remove(0)
VecDeque[7].remove(2)
created VecDeque[47] with contents: []
VecDeque[13].append(VecDeque[27])
VecDeque[13].remove(8)
created VecDeque[48] with contents: []
VecDeque[25].append(VecDeque[26])
VecDeque[25].remove(1)
VecDeque[25].remove(2)
VecDeque[7].remove(2)
created VecDeque[49] with contents: []
VecDeque[13].append(VecDeque[29])
VecDeque[13].remove(8)
created VecDeque[50] with contents: []
VecDeque[25].append(VecDeque[35])
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `None`,
 right: `Some(81)`', hacked.rs:1339:13

[pnkfelix]

Okay now I have a minimized regression test (play)

use std::collections::VecDeque;

fn main() {
    let mut vecdeque_13 = VecDeque::from(vec![ ]);
    let mut vecdeque_29 = VecDeque::from(vec![ 0 ]);
    vecdeque_29.insert(0,  30 );
    vecdeque_29.insert(1,  31 );
    vecdeque_29.insert(2,  32 );
    vecdeque_29.insert(3,  33 );
    vecdeque_29.insert(4,  34 );
    vecdeque_29.insert(5,  35 );
    println!("vecdeque_13: {:?}", vecdeque_13);
    println!("vecdeque_29: {:?}", vecdeque_29);

    println!("Invoking: `vecdeque_13.append(&mut vecdeque_29)`");
    vecdeque_13.append(&mut vecdeque_29);

    println!("vecdeque_13: {:?}", vecdeque_13);

    assert_eq!(vecdeque_13, VecDeque::from(vec![30, 31, 32, 33, 34, 35, 0]));
}

Unsurprisingly the issue is exposed by the append method. I haven't tried to delve too deeply into the erroneous optimization yet, but I'm guessing this is something where you need have different logical paths depending on whether the vecdeque's head is greater than or less than the tail...

[pnkfelix]

(it probably wouldn't be a terrible idea to try to adapt the much larger test input into a unit test for VecDeque. I removed a lot of extraneous VecDeque instances from the above minimized version, but originally my transcript from instrumenting the original code resulting in 50 VecDeques being created and modified in various ways.)

[RalfJung]

Btw, your test case still fails if I set LOTS to 30. That might make for a trace of a more manageable size?

[pietroalbini]

Fixed on beta. Closing this.

[pnkfelix]

Did a regression test land?

[pietroalbini]

Uh, I don't think so (looking at the PR).

[Shnatsel]

@pnkfelix I know I'm late to the party, but here's something that would have come in handy for testcase minimization: https://github.com/blt/bughunt-rust

It attempts to implement automated discovery crashes and incorrect behavior on Rust stdlib data structures. It's very similar to QuickCheck, but uses an instrumentation-guided fuzzer instead of PRNG as source of input. It operates on command streams and supports minimizing them, so far only by minimizing the amount of commands.

It already has a VecDeque test harness and obviously correct but not optimized implementation to cross-check std::VecDeque output against.