Implement ordering chaining

[rednum]

As discussed in: rust-lang/rfcs#1677

I've already started working on this and will open a PR soon.

[apasel422]

Reopening because this is a tracking issue.

[sfackler]

@rfcbot fcp merge

[SimonSapin]

Looks like @rfcbot missed @sfackler’s message?

I also think this addition looks good, and would like it to be stabilized.

[aturon]

@rfcbot fcp merge

[rfcbot]

Team member @aturon has proposed to merge this. The next step is review by the rest of the tagged teams:

• @BurntSushi
• @Kimundi
• @alexcrichton
• @aturon
• @brson
• @sfackler

No concerns currently listed.

Once these reviewers reach consensus, this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[alexcrichton]

ping @BurntSushi (checkbox)

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[rfcbot]

The final comment period is now complete.

[jongiddy]

I have some reservations about this change.

I changed the code at https://github.com/jongiddy/gidsort/blob/229720e12ac9602b844c623e584dd6f876d1e3a3/src/lib.rs#L71-L74

        let mut leg = compare(value, &buffer[trial]);
        if leg == Ordering::Equal {
            leg = when_equal;
        };

to https://github.com/jongiddy/gidsort/blob/2e0280362e36d7ca257d9057f2141a25b83dba6f/src/lib.rs#L73

        let leg = compare(value, &buffer[trial]).then(when_equal);

First, it's nice to have fewer lines and one less mut.

But the benchmark penalty was surprising. The most appropriate benchmark, large_ascending_gidsort, which calls the insertion_point function a lot but does not do much other work, went from 23,733 ns/iter (+/- 1,835) to 39,037 ns/iter (+/- 1,719).

Also, the big plus for the explicit version is that a non-Rust programmer could easily understand it. then is meaningless. As a fairly uncommon method, something like when_equal would be more obvious. this also allows the calling version to be when_equal_then, which is more consistent with Option and_then than the new then_with form.

[ghost]

@jongiddy I diagnosed and fixed the problem - we were simply missing #[inline] attributes :)