Synchronize with Rust 1.62.0

[clint-white]

This PR is an attempt to synchronize as much as possible the BinaryHeap in this crate with that in the Rust standard library as of 1.62.0.

There have been numerous changes to the standard library implementation since this crate forked from Rust 1.24.0. A few of those have already been ported here, a few more propsed in #32, but there remain many more that have not, resulting in this admittedly very large PR.

I proceeded by simply comparing binary_heap.rs in binary-heap-plus 0.4.1 with that in rust-lang/rust as of version 1.62.0, and then began updating the former in steps consisting of what seemed to me to be related changes. What resulted was the following (at present) 18 commits. While the total diff introduced by this PR is somewhat overwhelming, the intent is that the individual commits are easier to follow as each is focussed on a particular kind of change (e.g., safety, documentation, adding #[must_use], etc.) Then, for each commit, I looked at the history of the changes in rust-lang/rust from 1.24.0 to 1.62.0 that were involved in those changes and documented the relevant upstream PRs in the commit messages I wrote here. I tried to be as complete as I could in doing that, but given the extent of that range of history there could be some that I missed.

There are a few aspects of this PR that I want to highlight which I think warrant extra attention when reviewing it; these are elaborated below:

1. The addition of a build script and conditional inclusion of certain features.
2. The removal of the trait bound C: Compare<T> from the definition of struct BinaryHeap<T, C>.
3. The removal of the license header from the top of the file binary_heap.rs.
4. Whether to increase the MSRV.

First, the build script came about as follows. A result of the upstream changes to use narrowly scoped unsafe blocks in the private sifting methods, together with the change to declare those sifting methods to be unsafe fns, were compiler warnings from the unused_unsafe lint since by default the body of an unsafe function is treated as if inside an implicit unsafe block already. This situation was avoided in #32 because that PR only introduced the narrowly scoped unsafe blocks inside what are still declared to be safe functions. However, the sifting functions are clearly not safe to call; they perform unsafe operations without checking any safety invariants for those operations, instead passing that responsability on to their own callers. As I noted in this comment, upstream now declares the sifting functions as unsafe. But doing so also means we now have unsafe blocks in unsafe functions, and by default that produces the unused_unsafe warnings.

Rust 1.52.0 stabilized the lint unsafe_op_in_unsafe_fn; by setting this to deny, unsafe blocks are required for performing unsafe operations inside unsafe functions, eliminating the unused_unsafe warnings. This is the desired situation and what is done in Rust's liballoc. But it is only available starting with Rust 1.52.0. For earler versions of Rust, the best I could think of was to set unused_unsafe to level allow to suppress these warnings.

A build script to detect the compiler version was the best way I could think of to get rid of the unused_unsafe warnings, by conditionally setting #[deny(unsafe_op_in_unsafe_fn)] on 1.52.0 or later, otherwise settting #[allow(unused_unsafe)]. The alternatives seemed to be either to just ignore the warnings (since cargo will suppress these anyway when this crate is built as a dependency of another), or raise the MSRV to 1.52.0. I didn't like either of those, but please see if you agree or if you can think of another way to handle this.

Once I added the build script for this purpose, I found a few other places where it was useful to check the compiler version; these are noted in the comments in the script as well as the relevant commits included here. This allows keeping the MSRV at 1.36.0, while still providing some more recent functionality available in the standard library which users might also expect here. But conditionally providing features based on the compiler version could perhaps become cumbersome in the future, so please consider whether this is something you really wish to support in this project in general as well as whether the particular places where I propose it are warranted in your opinion. Maybe it is better to keep the API consistent across all supported versions of Rust.

Second, regarding relaxing the trait bound C: Compare<T> on the definition of BinaryHeap<T>. I am not sure the reason why it was included in the first place; the analogous bound T: Ord was not present in the standard library's code in 1.24.0 when this crate forked. The T: Ord bound was of course included on the impl block defining the methods of BinaryHeap<T>. But since the fork, upstream split that impl block into two so that the bound could be removed from those methods which do not need it. As a result, it is now somewhat difficult to simply diff the code here with that in std and compare the methods which are present since those upstream have been reorded by the use of now two impl blocks. I decided to match closely the upstream code and thus split the single large impl block defining all of the BinaryHeap<T, C>'s methods into two, one with and one without the C: Compare<T> bound. But of course that requires removing the bound from the struct definition. It also allows relaxing that bound on several trait implementations, again more closely aligning with the standard library.

I do not think this is a backwards incompatible change since we are removing rather than adding a trait bound, and this crate is not yet at version 1.0 anyway, but nonetheless perhaps a minor version bump would be warranted anyway?

Third, upstream changes in rust-lang/rust since 1.24.0 removed the license headers from the various source files in favor of the license files located in the repository root directory. I went ahead and did the same here, but again this is something that you should make sure you are comfortable with before merging. I think that commit could easily be reverted if you wished to retain the license header in binary_heap.rs. The upstream PRs where this was discussed and decided are noted in the commit message.

Finally, there is the question of whether to raise the MSRV. This is related to the first point where it was noted that build script allowed keeping the MSRV at 1.36.0. No change is required. However I will point out a few options for raising the MSRV that would eliminate some special cases and simplify maintenance, and you can see if you wish to go for any of these:

• 1.41.0: relaxed orphan rules allow implementing From<BinaryHeap<T, C>> for Vec<T>; this would eliminate one of the special cases;
• 1.48.0: stabilization of intra-doc links; this would allow more easily porting future documentation changes from the standard library without having to adjust any internal links to the older style;
• 1.52.0: stabilization of unused_op_in_unsafe_fn, the original motivation for adding the build script; by raising the MSRV to 1.52.0 and giving up on two things that require 1.56.0 one could forgoe a build script and any conditional compilation (at least for now).

[clint-white]

The CI job failure looks like it is due to a network error while trying to download the crates.io registry. Can you try it again?

[sekineh]

@clint-white , thanks for the great work. I have re-run the CI jobs. I’m still in the process of learning the whole diffs. I’ll get back within a week.

[sekineh]

@clint-white , Sorry for to be late. I'm back (finally).

The addition of a build script and conditional inclusion of certain features. The removal of the trait bound C: Compare from the definition of struct BinaryHeap<T, C>. The removal of the license header from the top of the file binary_heap.rs.

The above sounds all reasonable to me.

Whether to increase the MSRV.

It's OK to increase MSRV. The PR is big, so I'll bump the crate version like 0.5.x.

Can you edit the CI file? https://github.com/sekineh/binary-heap-plus-rs/blob/fec9e24925bf40aeda3418288dd6948e7f760623/.github/workflows/rust.yml#L23

My guess is that the following lines will test the all conditional compilation.

        include:
          - os: ubuntu-latest
            rust: nightly
            cargo_args: ""
          - os: ubuntu-latest
            rust: 1.xx
            cargo_args: ""
          - os: ubuntu-latest
            rust: 1.yy
            cargo_args: ""
          - os: ubuntu-latest
            rust: 1.zz
            cargo_args: ""
          :

[clint-white]

@sekineh , While I was reviewing the conditional compilation I noticed an error in one of the cfg value names. I just added a commit fixing this.

You said its OK to increase the MSRV, but do you have a preference as to what to raise it to? It could stay at 1.36.0, or some of the special cases could be removed by increasing it. The first such case would be a From impl at 1.41.0 which is not a large increase. After that, 1.52.0 is probably the next place but that is a bigger jump.

Once the MSRV is decided, I will make any necessary final adjustments based on that and then update the CI file to test any of the remaining versions with conditional compilation.

[sekineh]

For MSRV, I think 1.52 is OK because older rustc users can always use older version of crates.

Another candidate is 1.56 which introduced edition 2021. Both is fine.

[clint-white]

I went ahead and updated the CI file to include running the tests on versions of Rust where there is conditional compilation. For now this is based on an MSRV of 1.36.0. See if this is what you had in mind. I just saw that you want to increase to 1.52.0. I will make those changes and push and update when they are ready.

[clint-white]

I updated the MSRV to 1.52.0, which allowed removing two of the Rust version checks. This now unconditionally sets deny(unsafe_op_in_unsafe_fn) and implements From<BinaryHeap<T, C>> for Vec<T>.

Migrating to the 2021 edition would be nice. At that point the build.rs script would not be needed (unless you want to later add conditional support for the methods newly stabilized in 1.63.0). It would also allow migrating the doc examples to use arrays instead of Vec when constructing binary heaps, which is what is now done in std.

But maybe that should be a another PR after this one is merged, but before releasing 0.5.0?

[sekineh]

Looks good, I merge this first.

[sekineh]

I updated the MSRV to 1.52.0, which allowed removing two of the Rust version checks. This now unconditionally sets deny(unsafe_op_in_unsafe_fn) and implements From<BinaryHeap<T, C>> for Vec<T>.

Thanks for removing conditional compilation.

Migrating to the 2021 edition would be nice. At that point the build.rs script would not be needed (unless you want to later add conditional support for the methods newly stabilized in 1.63.0). It would also allow migrating the doc examples to use arrays instead of Vec when constructing binary heaps, which is what is now done in std.

But maybe that should be a another PR after this one is merged, but before releasing 0.5.0?

I agree, It’s a great idea to migrate to edition 2021 version.