iwls-0.0.2 fails its test suite in Rust 1.15 beta

[brson]

Regression from 1.14.

https://github.com/alopatindev/iwls commit 7316d2125f848914e90b26d532dc2165db4054bf

brian@ip-10-145-43-250:/mnt2/dev/iwls⟫ rustc +beta -Vv
rustc 1.15.0-beta.1 (d9a0f0df7 2016-12-19)
binary: rustc
commit-hash: d9a0f0df7051c603011d6b60fbdd155318fc47f3
commit-date: 2016-12-19
host: x86_64-unknown-linux-gnu
release: 1.15.0-beta.1
LLVM version: 3.9

brian@ip-10-145-43-250:~/dev/iwls⟫ cargo +beta test
   Compiling bitflags v0.7.0
   Compiling vec_map v0.6.0
   Compiling unicode-width v0.1.4
   Compiling regex-syntax v0.3.9
   Compiling utf8-ranges v0.1.3
   Compiling rustc-serialize v0.3.22
   Compiling winapi v0.2.8
   Compiling winapi-build v0.1.1
   Compiling unicode-segmentation v0.1.3
   Compiling kernel32-sys v0.2.2
   Compiling libc v0.2.18
   Compiling order-stat v0.1.3
   Compiling ansi_term v0.9.0
   Compiling term_size v0.2.1
   Compiling users v0.5.2
   Compiling strsim v0.5.2
   Compiling clap v2.19.3
   Compiling memchr v0.1.11
   Compiling rand v0.3.15
   Compiling aho-corasick v0.5.3
   Compiling thread-id v2.0.0
   Compiling thread_local v0.2.7
   Compiling regex v0.1.80
   Compiling num-traits v0.1.36
   Compiling num-complex v0.1.35
   Compiling num-integer v0.1.32
   Compiling num-iter v0.1.32
   Compiling num-bigint v0.1.35
   Compiling num-rational v0.1.35
   Compiling num v0.1.36
   Compiling nalgebra v0.10.1
   Compiling wifiscanner v0.3.4
   Compiling iwls v0.0.2 (file:///mnt2/dev/iwls)
warning: unknown lint: `float_cmp`, #[warn(unknown_lints)] on by default
   --> src/lib.rs:402:13
    |
402 |     #[allow(float_cmp)]
    |             ^^^^^^^^^

    Finished debug [unoptimized + debuginfo] target(s) in 41.10 secs
     Running target/debug/deps/iwls-16b3454ea97ff6f7

running 6 tests
test tests::test_channels_intersect ... ok
test tests::test_parse_channel ... ok
test tests::test_to_readable_quality ... ok
test tests::test_to_readable_channel ... ok
test tests::test_signal_to_quality ... ok
test tests::test_compute_suggestion ... FAILED

failures:

---- tests::test_compute_suggestion stdout ----
        thread 'tests::test_compute_suggestion' panicked at 'assertion failed: `(left == right)` (left: `[14, 11, 6, 1, 2]`, right: `[1, 2, 3, 4, 5]`)', src/lib.rs:451
note: Run with `RUST_BACKTRACE=1` for a backtrace.


failures:
    tests::test_compute_suggestion

test result: FAILED. 5 passed; 1 failed; 0 ignored; 0 measured

error: test failed

cc @alopatindev

[alexcrichton]

Minimized:

use std::cmp;

type ChannelLoad = (ChannelId, f64);
type ChannelsLoad = Vec<ChannelLoad>;
type ChannelId = u8;

const MAX_SUGGESTIONS: usize = 5;

fn least_intersected(id: ChannelId) -> bool {
    for &i in &[1, 6, 11, 14] {
        if i == id {
            return true;
        }
    }

    false
}

fn compute_suggestion() -> Vec<ChannelId> {
    let mut channels_load: ChannelsLoad = vec![
        (1, 0.0),
        (2, 0.0),
        (3, 0.0),
        (4, 0.0),
        (5, 0.0),
        (6, 0.0),
        (7, 0.0),
        (8, 0.0),
        (9, 0.0),
        (10, 0.0),
        (11, 0.0),
        (12, 0.0),
        (13, 0.0),
        (14, 0.0),
    ];

    channels_load.sort_by(|a, _b| {
        if least_intersected(a.0) {
            cmp::Ordering::Less
        } else {
            cmp::Ordering::Equal
        }
    });

    channels_load.iter()
        .take(MAX_SUGGESTIONS)
        .map(|&(id, _)| id)
        .collect()
}

fn main() {
    assert_eq!(&[14, 11, 6, 1, 2], compute_suggestion().as_slice());
}

The cause I would guess is #38192 (cc @stjepang, @bluss) and it looks like it's just relying on particulars of our sorting algorithm.

I would hazard a guess that this isn't really a regression.

[brson]

I don't see anything obvious in the reduced case that would be perturbed by an algorithm change.

[brson]

Oh, the comparison function is very weird here, depending on only one of its arguments. I'm not sure what it's trying to capture but it's definitely capturing effects from the algorithm.

[bluss]

This seems to be the original sort closure https://github.com/alopatindev/iwls/blob/7316d2125f848914e90b26d532dc2165db4054bf/src/lib.rs#L224-L230

I think they can use .sort_by_key(|ch| (!(ch.1 < LOW_LOAD && least_intersected(ch.0)), ch.1)) instead. Tuples is a good way to do prioritized sort.

Edit: That solution was not tested, and it fails because float are not Ord! So that explains why using .sort_by is the most natural. The recommendation is still to use a tuple and compare, or maybe use Ordering::then (not quite stable yet).

According to the comparison function, these two statements are true at the same time:

• (11, 0.0) < (14, 0.0)
• (14, 0.0) < (11, 0.0)

Therefore, the function is nonsensical. There is no correct sorted order here. :)
I opened a separate issue in the original project.

This is definitely not a regression and can be closed.