[REG 2.073.0] std.algorithm.searching.find on a SortedRange assumes that the comparison is the default

[schveiguy]

A SortedRange may carry with it a predicate, which means that the data is sorted according to the predicate, not the default comparison.

However, std.algorithm.searching.find has special casing for SortedRange where it assumes it can use the specialized search functions in it if the find predicate is the default. However, the correct comparison should that the predicates are identical!

A counter example:

import std.typecons;
import std.algorithm;
import std.range;

void main()
{
    auto arr = [tuple(2, 2), tuple(2, 1)];
    auto sr = arr.sort!((a, b) => a[0] < b[0]);
    assert(!arr.find(tuple(2, 1)).empty); // ok, linear search
    assert(!sr.find(tuple(2, 1)).empty); // fails
}

The relevant code is here:

phobos/std/algorithm/searching.d

Line 1818 in d6af824

static if (is(InputRange : SortedRange!TT, TT) && isDefaultPred)

[schveiguy]

It's a regression! 2.073 is around the time where it changed.

[schveiguy]

I'm looking at the code, and actually, this might be a compiler bug instead. I think the static if should not pass in this case, because SortedRange!TT should actually be using the default predicate.

To demonstrate:

    auto arr = [tuple(2, 2), tuple(2, 1)];
    auto sr = arr.sort!((a, b) => a[0] < b[0]);
    static if(is(typeof(sr) == SortedRange!T, T)) {
        SortedRange!T sr2 = sr; // fails
    }