sort purity

[jesse99]

The sort functions currently require a pure comparison function. Is this actually required?

For example, I need to be able to sort the results of a query where the results are not always orderable. If the comparison functions are allowed to be impure then I can add a err: @mut ~str argument to my function and see if it is set when the sort finishes. But if purity is required then I'll need to do a pass before the sort which is a) duplicating a traversal that sort has to do anyway and b) very inefficient (especially given that queries can have lots of results).

[jesse99]

Note that the work around is to use an unsafe block in the comparison function.

[graydon]

Yeah, the pure interface is best here; if you need to break the rule, that's what unsafe is for, and you can be careful to make what-you-do not interfere with any assumptions that purity might have been used to support.

Closing this as it's intended behavior. Also note, this is not substantial enough an issue to warrant the RFC tag.

[jruderman]

You can't write to anything @mut, but you can write to stack and ~ upvars that weren't borrowed by the sort.

(This is allowed intentionally, right?)

use std;

fn main()
{
    let a = ~[1, 4, 3, 5, 2];
    let mut compare_count = 0;

    std::sort::quick_sort(|x, y| { compare_count += 1; *x < *y }, a);

    error!("%d comparisons", compare_count);
    error!("%?", a);
}

[nikomatsakis]

I'm... not sure that's by design. I want to tighten up and reformulate the purity rules in a more principled way. I will open a separate issue and throw in this example.

[nikomatsakis]

See #3490