libphobos/libdruntime/core/internal/array/comparison.d

/**
 * This module contains compiler support for comparing dynamic arrays
 *
 * Copyright: Copyright Digital Mars 2000 - 2019.
 * License: Distributed under the
 *      $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0).
 *    (See accompanying file LICENSE)
 * Source: $(DRUNTIMESRC core/internal/_array/_comparison.d)
 */

module core.internal.array.comparison;

int __cmp(T)(scope const T[] lhs, scope const T[] rhs) @trusted
    if (__traits(isScalar, T))
{
    // Compute U as the implementation type for T
    static if (is(T == ubyte) || is(T == void) || is(T == bool))
        alias U = char;
    else static if (is(T == wchar))
        alias U = ushort;
    else static if (is(T == dchar))
        alias U = uint;
    else static if (is(T == ifloat))
        alias U = float;
    else static if (is(T == idouble))
        alias U = double;
    else static if (is(T == ireal))
        alias U = real;
    else
        alias U = T;

    static if (is(U == char))
    {
        import core.internal.string : dstrcmp;
        return dstrcmp(cast(char[]) lhs, cast(char[]) rhs);
    }
    else static if (!is(U == T))
    {
        // Reuse another implementation
        return __cmp(cast(U[]) lhs, cast(U[]) rhs);
    }
    else
    {
        version (BigEndian)
        static if (__traits(isUnsigned, T) ? !is(T == __vector) : is(T : P*, P))
        {
            if (!__ctfe)
            {
                import core.stdc.string : memcmp;
                int c = memcmp(lhs.ptr, rhs.ptr, (lhs.length <= rhs.length ? lhs.length : rhs.length) * T.sizeof);
                if (c)
                    return c;
                static if (size_t.sizeof <= uint.sizeof && T.sizeof >= 2)
                    return cast(int) lhs.length - cast(int) rhs.length;
                else
                    return int(lhs.length > rhs.length) - int(lhs.length < rhs.length);
            }
        }

        immutable len = lhs.length <= rhs.length ? lhs.length : rhs.length;
        foreach (const u; 0 .. len)
        {
            auto a = lhs.ptr[u], b = rhs.ptr[u];
            static if (is(T : creal))
            {
                // Use rt.cmath2._Ccmp instead ?
                // Also: if NaN is present, numbers will appear equal.
                auto r = (a.re > b.re) - (a.re < b.re);
                if (!r) r = (a.im > b.im) - (a.im < b.im);
            }
            else
            {
                // This pattern for three-way comparison is better than conditional operators
                // See e.g. https://godbolt.org/z/3j4vh1
                const r = (a > b) - (a < b);
            }
            if (r) return r;
        }
        return (lhs.length > rhs.length) - (lhs.length < rhs.length);
    }
}

// This function is called by the compiler when dealing with array
// comparisons in the semantic analysis phase of CmpExp. The ordering
// comparison is lowered to a call to this template.
auto __cmp(T1, T2)(T1[] s1, T2[] s2)
if (!__traits(isScalar, T1) && !__traits(isScalar, T2))
{
    import core.internal.traits : Unqual;
    alias U1 = Unqual!T1;
    alias U2 = Unqual!T2;

    static if (is(U1 == void) && is(U2 == void))
        static @trusted ref inout(ubyte) at(inout(void)[] r, size_t i) { return (cast(inout(ubyte)*) r.ptr)[i]; }
    else
        static @trusted ref R at(R)(R[] r, size_t i) { return r.ptr[i]; }

    // All unsigned byte-wide types = > dstrcmp
    immutable len = s1.length <= s2.length ? s1.length : s2.length;

    foreach (const u; 0 .. len)
    {
        static if (__traits(compiles, __cmp(at(s1, u), at(s2, u))))
        {
            auto c = __cmp(at(s1, u), at(s2, u));
            if (c != 0)
                return c;
        }
        else static if (__traits(compiles, at(s1, u).opCmp(at(s2, u))))
        {
            auto c = at(s1, u).opCmp(at(s2, u));
            if (c != 0)
                return c;
        }
        else static if (__traits(compiles, at(s1, u) < at(s2, u)))
        {
            if (int result = (at(s1, u) > at(s2, u)) - (at(s1, u) < at(s2, u)))
                return result;
        }
        else
        {
            // TODO: fix this legacy bad behavior, see
            // https://issues.dlang.org/show_bug.cgi?id=17244
            static assert(is(U1 == U2), "Internal error.");
            import core.stdc.string : memcmp;
            auto c = (() @trusted => memcmp(&at(s1, u), &at(s2, u), U1.sizeof))();
            if (c != 0)
                return c;
        }
    }
    return (s1.length > s2.length) - (s1.length < s2.length);
}

// integral types
@safe unittest
{
    void compareMinMax(T)()
    {
        T[2] a = [T.max, T.max];
        T[2] b = [T.min, T.min];

        assert(__cmp(a, b) > 0);
        assert(__cmp(b, a) < 0);
    }

    compareMinMax!int;
    compareMinMax!uint;
    compareMinMax!long;
    compareMinMax!ulong;
    compareMinMax!short;
    compareMinMax!ushort;
    compareMinMax!byte;
    compareMinMax!dchar;
    compareMinMax!wchar;
}

// char types (dstrcmp)
@safe unittest
{
    void compareMinMax(T)()
    {
        T[2] a = [T.max, T.max];
        T[2] b = [T.min, T.min];

        assert(__cmp(a, b) > 0);
        assert(__cmp(b, a) < 0);
    }

    compareMinMax!ubyte;
    compareMinMax!bool;
    compareMinMax!char;
    compareMinMax!(const char);

    string s1 = "aaaa";
    string s2 = "bbbb";
    assert(__cmp(s2, s1) > 0);
    assert(__cmp(s1, s2) < 0);
}

// fp types
@safe unittest
{
    void compareMinMax(T)()
    {
        T[2] a = [T.max, T.max];
        T[2] b = [T.min_normal, T.min_normal];
        T[2] c = [T.max, T.min_normal];
        T[1] d = [T.max];

        assert(__cmp(a, b) > 0);
        assert(__cmp(b, a) < 0);
        assert(__cmp(a, c) > 0);
        assert(__cmp(a, d) > 0);
        assert(__cmp(d, c) < 0);
        assert(__cmp(c, c) == 0);
    }

    compareMinMax!real;
    compareMinMax!float;
    compareMinMax!double;

    // qualifiers
    compareMinMax!(const real);
    compareMinMax!(immutable real);
}

// void[]
@safe unittest
{
    void[] a;
    const(void)[] b;

    (() @trusted
    {
        a = cast(void[]) "bb";
        b = cast(const(void)[]) "aa";
    })();

    assert(__cmp(a, b) > 0);
    assert(__cmp(b, a) < 0);
}

// arrays of arrays with mixed modifiers
@safe unittest
{
    // https://issues.dlang.org/show_bug.cgi?id=17876
    bool less1(immutable size_t[][] a, size_t[][] b) { return a < b; }
    bool less2(const void[][] a, void[][] b) { return a < b; }
    bool less3(inout size_t[][] a, size_t[][] b) { return a < b; }

    immutable size_t[][] a = [[1, 2], [3, 4]];
    size_t[][] b = [[1, 2], [3, 5]];
    assert(less1(a, b));
    assert(less3(a, b));

    auto va = [cast(immutable void[])a[0], a[1]];
    auto vb = [cast(void[])b[0], b[1]];
    assert(less2(va, vb));
}

// custom aggregate types
@safe unittest
{
    // https://issues.dlang.org/show_bug.cgi?id=24044
    // Support float opCmp(...) with array
    static struct F
    {
        float f;
        float opCmp(F other) const { return this.f - other.f; }
    }

    F[2] a = [F(1.0f), F(float.nan)];
    F[2] b = [F(1.0f), F(1.0f)];
    F[1] c = [F(1.0f)];

    bool isNan(float f) { return f != f; }

    assert(isNan(__cmp(a, b)));
    assert(isNan(__cmp(a, a)));
    assert(__cmp(b, b) == 0);
    assert(__cmp(a, c) > 0);
}