Wrong first element popped in pop_first() for BTreeSet

[SetTheorist]

Summary:
When popping elements using pop_first() from a BTreeSet, the first element popped is not the min element, though remaining elements are popped in expected order.

I tried this code:

#![feature(map_first_last)]
use std::collections::BTreeSet;

type D = isize;
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct T(pub D, pub D);

pub fn main() {
    let mut s = BTreeSet::new();
    let v = vec![
        T(0, 0),
        T(63, 63),
        T(63, 252),
        T(126, 126),
        T(189, 189),
        T(252, 252),
        T(252, 441),
        T(315, 315),
        T(378, 378),
        T(441, 441),
        T(441, 503),
        T(504, 504),
    ];
    for x in &v {
        s.insert(x);
    }
    while let Some(x) = s.pop_first() {
        print!(" {:?}", x);
    }
    println!("");
}

I expected to see this happen:

 T(0, 0) T(63, 63) T(63, 252) T(126, 126) T(189, 189) T(252, 252) T(252, 441) T(315, 315) T(378, 378) T(441, 441) T(441, 503) T(504, 504)

Instead, this happened: (Note the first result).

 T(252, 441) T(0, 0) T(63, 63) T(63, 252) T(126, 126) T(189, 189) T(252, 252) T(315, 315) T(378, 378) T(441, 441) T(441, 503) T(504, 504)

For various subsets of the given inputs I tried, it appears to give the expected behaviour.

Meta

rustc --version --verbose:
rustc 1.42.0-nightly (8417d68 2020-02-03)
binary: rustc
commit-hash: 8417d68
commit-date: 2020-02-03
host: x86_64-unknown-linux-gnu
release: 1.42.0-nightly
LLVM version: 9.0

[jonas-schievink]

Thanks for the report! Do you know if this is a recent regression, or did this always happen? cc @ssomers in any case

[jonas-schievink]

Oh this is nightly-only

[SetTheorist]

It was there in [rustc 1.42.0-nightly (31dd4f4 2020-01-13)], as that is what I was using initially, but I don't know when it appeared before that.

[ssomers]

Well, your expectations are right, and play.rust-lang.org confirms it's not what happens.

[ssomers]

The implementation is completely wrong. Apparently I did not test this on anything with more than 1 node (11 elements)!?

[ssomers]

So it's always been wrong (picking the first element from the root node) and it will be right in some future nightly, hopefully a day or two from now. Thank you for the clear report.

[SetTheorist]

Thanks for the rapid response!

[runiq]

Drive-by triage: This should apparently have been closed by #68834.