I implemented worstsort in Rust:
fn bubblesort<T: PartialOrd>(l: &mut [T]) {
for i in 1..l.len() {
for j in 0..l.len() - i {
if l[j + 1] < l[j] {
l.swap(j + 1, j);
}
}
}
}
fn permutations<T: Clone>(l: &[T]) -> Vec<Vec<T>> {
if l.len() <= 1 {
return vec![l.to_vec()];
}
let mut res = Vec::new();
for i in 0..l.len() {
let mut lcopy = l.to_vec();
lcopy.remove(i);
let p = permutations(&lcopy);
for perm in p {
let mut fullperm = vec![l[i].clone()];
fullperm.extend(perm);
res.push(fullperm);
}
}
res
}
pub fn badsort<T: PartialOrd + Clone>(k: usize, l: &mut [T]) {
if k == 0 {
bubblesort(l);
} else {
let mut p = permutations(l);
badsort(k - 1, &mut p);
l.clone_from_slice(&p[0]);
}
}
pub fn worstsort<T, F>(l: &mut [T], f: F)
where
T: PartialOrd + Clone,
F: FnOnce(usize) -> usize,
{
badsort(f(l.len()), l);
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn badsort_zero() {
let mut unsorted = vec![8, 3, 5];
badsort(0, &mut unsorted);
assert_eq!(unsorted, vec![3, 5, 8]);
}
#[test]
fn worstsort_id() {
let mut unsorted = vec![8, 3, 5];
worstsort(&mut unsorted, |n| n);
assert_eq!(unsorted, vec![3, 5, 8]);
}
}
It compiles and checks fine, until I tried to write tests that actually calling the worstsort
and badsort
functions, and cargo test
gives an error:
error: reached the recursion limit while instantiating `badsort::<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<i32>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
I get this error even when calling badsort(0, l)
, which should just be bubblesort, with no recursive calls whatsoever. My assumption is that rustc is trying to generate monomorphised versions of badsort
for every possible usize
(I swapped the type to u8
and got the same error), but I don't understand why: it errors whatever the argument is, even when it doesn't recursively call itself at all! I tried setting the recursion limit all the way up to #![recursion_limit="1024"]
, but it still hits this limit and fails, even with u8
.
Is my guess correct? Is there a way to get this (admittedly perverse) code to compile and run at all?
badsort
calls itself on aVec<Vec<T>>
, which is going to call itself on aVec<Vec<Vec<Vec<T>>>>
which is going to call itself etc etcbadsort
withk
larger than some small value, it doesn't need to generate that many type specialisations.k
to resolve the types in your function.