rust-lang
Implement partial_sort_unstable for slice
r? @scottmcm
rustbot has assigned @scottmcm. They will have a look at your PR within the next two weeks and either review your PR or reassign to another reviewer.
Use r? to explicitly pick a reviewer
The job aarch64-gnu-llvm-20-2 failed! Check out the build log: (web) (plain enhanced) (plain)
Click to see the possible cause of the failure (guessed by this bot)
[RUSTC-TIMING] build_script_build test:false 0.311
error[E0618]: expected function, found `R`
--> library/core/src/slice/mod.rs:3267:36
|
3261 | pub fn partial_sort_unstable_by<F, R>(&mut self, range: R, mut compare: F)
| ----- `range` has type `R`
...
3267 | let Range { start, end } = range(range, ..len);
| ^^^^^--------------
| |
| call expression requires function
|
::: library/core/src/slice/index.rs:908:1
|
908 | / pub const fn range<R>(range: R, bounds: ops::RangeTo<usize>) -> ops::Range<usize>
909 | | where
910 | | R: [const] ops::RangeBounds<usize> + [const] Destruct,
| |__________________________________________________________- this function of the same name is available here, but it's shadowed by the local binding
For more information about this error, try `rustc --explain E0618`.
[RUSTC-TIMING] core test:false 23.486
error: could not compile `core` (lib) due to 1 previous error
The job x86_64-gnu-gcc failed! Check out the build log: (web) (plain enhanced) (plain)
Click to see the possible cause of the failure (guessed by this bot)
[RUSTC-TIMING] profiler_builtins test:false 0.024
error[E0382]: use of moved value: `is_less`
--> library/core/src/slice/mod.rs:3299:76
|
3291 | let (_, _, slice) = sort::select::partition_at_index(self, index, is_less);
| ------- value moved here
...
3299 | let (slice, _, _) = sort::select::partition_at_index(slice, index, is_less);
| ^^^^^^^ value used here after move
|
note: closure cannot be moved more than once as it is not `Copy` due to moving the variable `compare` out of its environment
--> library/core/src/slice/mod.rs:3288:38
|
3288 | let is_less = |a: &T, b: &T| compare(a, b) == Less;
| ^^^^^^^
help: consider mutably borrowing `is_less`
|
3291 | let (_, _, slice) = sort::select::partition_at_index(self, index, &mut is_less);
| ++++
error[E0382]: borrow of moved value: `is_less`
--> library/core/src/slice/mod.rs:3300:37
|
3299 | let (slice, _, _) = sort::select::partition_at_index(slice, index, is_less);
| ------- value moved here
3300 | sort::unstable::sort(slice, &mut is_less);
| ^^^^^^^^^^^^ value borrowed here after move
|
note: closure cannot be moved more than once as it is not `Copy` due to moving the variable `compare` out of its environment
--> library/core/src/slice/mod.rs:3288:38
|
3288 | let is_less = |a: &T, b: &T| compare(a, b) == Less;
| ^^^^^^^
help: consider mutably borrowing `is_less`
|
3299 | let (slice, _, _) = sort::select::partition_at_index(slice, index, &mut is_less);
| ++++
error[E0596]: cannot borrow `is_less` as mutable, as it is not declared as mutable
--> library/core/src/slice/mod.rs:3300:37
|
3288 | let is_less = |a: &T, b: &T| compare(a, b) == Less;
| ------- calling `is_less` requires mutable binding due to mutable borrow of `compare`
...
3300 | sort::unstable::sort(slice, &mut is_less);
| ^^^^^^^^^^^^ cannot borrow as mutable
|
help: consider changing this to be mutable
|
3288 | let mut is_less = |a: &T, b: &T| compare(a, b) == Less;
| +++
Some errors have detailed explanations: E0382, E0596.
For more information about an error, try `rustc --explain E0382`.
[RUSTC-TIMING] core test:false 14.205
For more information how to resolve CI failures of this job, visit this link.
I do note a lack of tests?
Doc tests cover most branches. I don't find a dedicated file to cover its cousin sort_unstable. If you can point me to one, I'm glad to add cases there.
The examples can change at any time. And you didn't test, for example, the post-condition that all elements ..start are less than or equal to the elements start..end and that those are less than or equal to the elements end.., including for the zero-length case.
The examples can change at any time. And you didn't test, for example, the post-condition that all elements
..startare less than or equal to the elementsstart..endand that those are less than or equal to the elementsend.., including for the zero-length case.
Thanks and yes. Do you know where the unit tests of sort/sort_unstable locate?
I believe the bulk is found in https://github.com/rust-lang/rust/blob/main/library/alloctests/tests/sort/tests.rs.
What I suggested in the ACP was a sketch implementation, I did some more thinking and I think the following handles all corner cases nicely:
pub fn partial_sort<T, F, R>(mut v: &mut [T], range: R, is_less: &mut F)
where
F: FnMut(&T, &T) -> bool,
R: RangeBounds<usize>,
{
let len = v.len();
let Range { start, end } = slice::range(range, ..len);
if end - start <= 1 {
// Can be resolved in at most a single partition_at_index call, without
// further sorting. Do nothing if it is an empty range at start or end.
if start != len && end != 0 {
sort::select::partition_at_index(v, start, is_less);
}
return;
}
// Don't bother reducing the slice to sort if it eliminates fewer than 8 elements.
if end + 8 <= len {
v = sort::select::partition_at_index(v, end - 1, is_less).0;
}
if start >= 8 {
v = sort::select::partition_at_index(v, start, is_less).2;
}
sort::unstable::sort(v, is_less);
}
And to formalize the post-conditions, I think the following should hold after a call to v.partial_sort_unstable(b..e):
for i in 0..b {
for j in b..n {
assert!(v[i] <= v[j]);
}
}
for i in 0..e {
for j in e..n {
assert!(v[i] <= v[j]);
}
}
for i in b..e {
for j in i..e {
assert!(v[i] <= v[j]);
}
}
And to formalize the post-conditions, I think the following should hold after a call to
v.partial_sort_unstable(b..e):
A lot of those individual comparisons are implied by transitivity of the ordering, so it can be reduced to choosing the maximum of the prefix (if any), the minimum of the suffix (if any), and then asserting that the concatenation is sorted.
Informally, max(v[..b]) <= v[b] <= v[b + 1] <= ... <= v[e-1] <= min(v[e..]), or in code:
let max_before = v[..b].iter().max().into_iter();
let sorted_range = v[b..e].iter();
let min_after = v[e..].iter().min().into_iter();
let seq = max_before.chain(sorted_range).chain(min_after);
assert!(seq.is_sorted());
That's pretty much what you said in https://github.com/rust-lang/libs-team/issues/685#issuecomment-3494102871 , just using transitivity of the comparison. Without assuming that, the implementation couldn't guarantee the universally quantified property anyway.
This PR was rebased onto a different main commit. Here's a range-diff highlighting what actually changed.
Rebasing is a normal part of keeping PRs up to date, so no action is needed—this note is just to help reviewers.
Pushed a new implementation.
I'm writing tests but perhaps we'd have a new mod under library/alloctests/tests/partial_sort rather than patch the existing library/alloctests/tests/sort/tests.rs. Since the sort tests are heavily depending on macros while partial sorts assertions are quite different.
Pushed a new implementation.
I'm writing tests but perhaps we'd have a new mod under
library/alloctests/tests/partial_sortrather than patch the existing library/alloctests/tests/sort/tests.rs. Since the sort tests are heavily depending on macros while partial sorts assertions are quite different.
cc @Amanieu for early review for the direction and advice on where to organize the tests.
The job pr-check-2 failed! Check out the build log: (web) (plain enhanced) (plain)
Click to see the possible cause of the failure (guessed by this bot)
stderr:
thread 'main' (143592) panicked at library/core/src/slice/mod.rs:16:4:
assertion failed: v[i] <= v[2]
stack backtrace:
0: __rustc::rust_begin_unwind
1: core::panicking::panic_fmt
2: core::panicking::panic
3: rust_out::main::_doctest_main_library_core_src_slice_mod_rs_3335_0
4: rust_out::main
5: <fn() as core::ops::function::FnOnce<()>>::call_once
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
---- library/core/src/slice/mod.rs - slice::[T]::partial_sort_unstable_by (line 3335) stdout end ----
The job aarch64-gnu-llvm-20-1 failed! Check out the build log: (web) (plain enhanced) (plain)
Click to see the possible cause of the failure (guessed by this bot)
[RUSTC-TIMING] build_script_build test:false 0.310
error[E0308]: mismatched types
--> library/core/src/slice/sort/unstable/mod.rs:104:13
|
67 | pub fn partial_sort<T, F, R>(v: &mut [T], range: R, mut is_less: F)
| - found this type parameter
...
104 | sort(v, is_less);
| ---- ^^^^^^^ expected `&mut _`, found type parameter `F`
| |
| arguments to this function are incorrect
|
= note: expected mutable reference `&mut _`
found type parameter `F`
note: function defined here
--> library/core/src/slice/sort/unstable/mod.rs:23:8
|
23 | pub fn sort<T, F>(v: &mut [T], is_less: &mut F)
| ^^^^ ---------------
help: consider mutably borrowing here
|
104 | sort(v, &mut is_less);
| ++++
For more information about this error, try `rustc --explain E0308`.
[RUSTC-TIMING] core test:false 24.596
error: could not compile `core` (lib) due to 1 previous error
Regarding the tests I'm happy with either a separate file or as part of the existing tests as you see fit.
Pushed some basic test cases at https://github.com/rust-lang/rust/pull/149318/commits/01bfcc05322896da4cbc24835aa61e244fa3e391.
The existing sort tests have many assumptions, like checked_sort always sorts the whole range (for sure), and this helper is tightly coupled in cases. I can hardly insert the range concept in the current sort tests set up.
I added the basic test cases and will try to leverage the pattern functions in the sort module to generate more cases. But this patch itself should be mergeable as long as the implementation looks good, since now we have the test structure, which can be improved continuously.
