Unify stable and unstable sort implementations in same core module by Voultapher · Pull Request #104672

Unify stable and unstable sort implementations in same core module by Voultapher · Pull Request #104672 · rust-lang/rust

This moves the stable sort implementation to the core::slice::sort module. By
virtue of being in core it can't access `Vec`. The two `Vec` used by merge sort,
`buf` and `runs`, are modelled as custom types that implement the very limited
required `Vec` interface with the help of provided allocation and free
functions. This is done to allow future re-use of functions and logic between
stable and unstable sort. Such as `insert_head`.

rustbot added S-waiting-on-review

Status: Awaiting review from the assignee but also interested parties.

T-libs

Relevant to the library team, which will review and decide on the PR/issue.

labels

Nov 21, 2022

There were several unsafe blocks in the existing implementation that
were not documented with a SAFETY comment.

bors added S-waiting-on-bors

Status: Waiting on bors to run and complete tests. Bors will change the label on completion.

and removed S-waiting-on-review

Status: Awaiting review from the assignee but also interested parties.

labels

Dec 14, 2022

bors added S-waiting-on-author

Status: This is awaiting some action (such as code changes or more information) from the author.

and removed S-waiting-on-bors

Status: Waiting on bors to run and complete tests. Bors will change the label on completion.

labels

Dec 14, 2022

thomcc added S-waiting-on-review

Status: Awaiting review from the assignee but also interested parties.

and removed S-waiting-on-author

Status: This is awaiting some action (such as code changes or more information) from the author.

labels

Jan 18, 2023

bors added S-waiting-on-bors

Status: Waiting on bors to run and complete tests. Bors will change the label on completion.

and removed S-waiting-on-review

Status: Awaiting review from the assignee but also interested parties.

labels

Jan 19, 2023

compiler-errors added a commit to compiler-errors/rust that referenced this pull request

Jan 20, 2023

…homcc

Unify stable and unstable sort implementations in same core module

This moves the stable sort implementation to the core::slice::sort module. By virtue of being in core it can't access `Vec`. The two `Vec` used by merge sort, `buf` and `runs`, are modelled as custom types that implement the very limited required `Vec` interface with the help of provided allocation and free functions. This is done to allow future re-use of functions and logic between stable and unstable sort. Such as `insert_head`.

This is in preparation of rust-lang#100856 and rust-lang#104116. It only moves code, it *doesn't* change any of the sort related logic. This unlocks the ability to share `insert_head`, `insert_tail`, `swap_if_less` `merge` and more.

Tagging ``@Mark-Simulacrum`` I hope this allows progress on rust-lang#100856, by moving `merge_sort` here I hope future changes will be easier to review.

matthiaskrgr added a commit to matthiaskrgr/rust that referenced this pull request

Jan 20, 2023

…homcc

Unify stable and unstable sort implementations in same core module

This moves the stable sort implementation to the core::slice::sort module. By virtue of being in core it can't access `Vec`. The two `Vec` used by merge sort, `buf` and `runs`, are modelled as custom types that implement the very limited required `Vec` interface with the help of provided allocation and free functions. This is done to allow future re-use of functions and logic between stable and unstable sort. Such as `insert_head`.

This is in preparation of rust-lang#100856 and rust-lang#104116. It only moves code, it *doesn't* change any of the sort related logic. This unlocks the ability to share `insert_head`, `insert_tail`, `swap_if_less` `merge` and more.

Tagging ```@Mark-Simulacrum``` I hope this allows progress on rust-lang#100856, by moving `merge_sort` here I hope future changes will be easier to review.

bors added a commit to rust-lang-ci/rust that referenced this pull request

Jan 21, 2023

…mpiler-errors

Rollup of 9 pull requests

Successful merges:

 - rust-lang#104154 (Change `bindings_with_variant_name` to deny-by-default)
 - rust-lang#104347 (diagnostics: suggest changing `s@self::{macro}`@::macro`` for exported)
 - rust-lang#104672 (Unify stable and unstable sort implementations in same core module)
 - rust-lang#107048 (check for x version updates)
 - rust-lang#107061 (Implement some more new solver candidates and fix some bugs)
 - rust-lang#107095 (rustdoc: remove redundant CSS selector `.sidebar .current`)
 - rust-lang#107112 (Fix typo in opaque_types.rs)
 - rust-lang#107124 (fix check macro expansion)
 - rust-lang#107131 (rustdoc: use CSS inline layout for radio line instead of flexbox)

Failed merges:

r? `@ghost`
`@rustbot` modify labels: rollup