sortperm segfaults with lt=(>=)

[stevengj]

Reported on discourse:

sortperm(rand(1:10,10^3), lt=(>=))

crashes with a segmentation fault. (I can reproduce on every version of Julia from 1.8 back to 0.4. In 0.3 it throws a BoundsError.)

A similar but deterministic case that reliably causes a segfault is:

a = [10, 9, 8, 9, 7, 1, 3, 10, 4, 5, 5, 4, 6, 10, 10, 2, 2, 2, 8, 9, 1, 2, 8, 6, 7, 10, 1, 3, 5, 10];
sortperm(a, lt=(>=))

[gbaraldi]

With --checkbounds=yes I get an error in

julia> sortperm(a, lt=(>=))
ERROR: BoundsError: attempt to access 30-element Vector{Int64} at index [0]
Stacktrace:
 [1] getindex
   @ ./array.jl:924 [inlined]
 [2] partition!(v::Vector{Int64}, lo::Int64, hi::Int64, o::Base.Order.Perm{Base.Order.Lt{Base.Order.var"#1#3"{typeof(>=), typeof(identity)}}, Vector{Int64}})
   @ Base.Sort ./sort.jl:557
 [3] sort!(v::Vector{Int64}, lo::Int64, hi::Int64, a::Base.Sort.QuickSortAlg, o::Base.Order.Perm{Base.Order.Lt{Base.Order.var"#1#3"{typeof(>=), typeof(identity)}}, Vector{Int64}})
   @ Base.Sort ./sort.jl:572
 [4] sort!(v::Vector{Int64}, alg::Base.Sort.QuickSortAlg, order::Base.Order.Perm{Base.Order.Lt{Base.Order.var"#1#3"{typeof(>=), typeof(identity)}}, Vector{Int64}})
   @ Base.Sort ./sort.jl:661
 [5] sortperm(v::Vector{Int64}; alg::Base.Sort.QuickSortAlg, lt::Function, by::Function, rev::Nothing, order::Base.Order.ForwardOrdering)
   @ Base.Sort ./sort.jl:927
 [6] top-level scope
   @ REPL[2]:1

[adienes]

the MWE can be (slightly) shortened to

b = [7, 1, 3, 10, 4, 5, 5, 4, 6, 10, 10, 2, 2, 2, 8, 9, 1, 2, 8, 6, 7, 10]

sort(b; lt=(>=))                        #fail
sort(b; lt=(>=), alg=InsertionSort)     #pass
sort(b; lt=(>=), alg=MergeSort)         #pass

sort(b; lt=(<=))                        #pass
sort(b; lt=(<=), rev=true)              #fail

sort(b; lt=Base.isgreater)              #pass
sort(b; lt=isless, rev=true)            #pass

sort!(b; lt=(>=))
#fail, but now
# b = [10, 1, 3, 10, 4, 5, 5, 4, 6, 10, 10, 2, 2, 2, 8, 9, 1, 2, 8, 6, 7, 7]

[sprmnt21]

I don't know if this will give any clue as to where the problem lies, but for vectors of this type longer than 22 the following problem arises

julia> bget22=repeat([1],22);

julia> sort(bget22, lt=(>=))
ERROR: BoundsError: attempt to access 22-element Vector{Int64} at index [0]

[fredrikekre]

Looks like improper use of @inbounds based on unverified user input (lt); I believe lt should only return true when values are actually "less-than" and not also when they are equal.

I can no reproduce the crash on Julia master though, but likely it gives unsurprising results still.

[LilithHafner]

Duplicate of #11429 Fixed in the upcoming release by #45222.

julia> VERSION
v"1.9.0-beta2"

julia> sortperm(rand(1:10,10^3), lt=(>=));

julia> a = [10, 9, 8, 9, 7, 1, 3, 10, 4, 5, 5, 4, 6, 10, 10, 2, 2, 2, 8, 9, 1, 2, 8, 6, 7, 10, 1, 3, 5, 10];

julia> sortperm(a, lt=(>=));

julia> b = [7, 1, 3, 10, 4, 5, 5, 4, 6, 10, 10, 2, 2, 2, 8, 9, 1, 2, 8, 6, 7, 10];

julia> sort(b; lt=(>=));                        #fail

julia> sort(b; lt=(>=), alg=InsertionSort);     #pass

julia> sort(b; lt=(>=), alg=MergeSort);         #pass

julia> sort(b; lt=(<=), rev=true);              #fail

[...]

You are supposed to use a "less than" ordering, not a "less than or equal to" ordering, so we don't guarantee correct behavior with lt=(>=). That said, a segfault is pretty bad and we have tests in place to prevent accidental regressions on this even though we don't guarantee the behavior.

The current observed behavior is that an unstable algorithm will give correct results and a stable algorithm will give correct results and reverse the order of all elements that compare equal (i.e. the exact opposite of stable), but don't count on it.

[sprmnt21]

I was finally able to get debugging working under vscode.
I had identified in the while ..v[i ]; i+=1 end loops part of the following function, inside the sort.jl module.
To complete the analysis, the problem does not arise for smaller vectors because in these cases a different sorting algorithm is used.
Is that it?

const SMALL_ALGORITHM  = InsertionSort
const SMALL_THRESHOLD  = 20


function partition!(v::AbstractVector, lo::Integer, hi::Integer, o::Ordering)
    pivot = selectpivot!(v, lo, hi, o)
    # pivot == v[lo], v[hi] > pivot
    i, j = lo, hi
    @inbounds while true
        i += 1; j -= 1
        while lt(o, v[i], pivot); i += 1; end;
        while lt(o, pivot, v[j]); j -= 1; end;
        i >= j && break
        v[i], v[j] = v[j], v[i]
    end
    v[j], v[lo] = pivot, v[j]

    # v[j] == pivot
    # v[k] >= pivot for k > j
    # v[i] <= pivot for i < j
    return j
end

[LilithHafner]

Precisely!