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

/**
 * This module contains compiler support determining equality of arrays.
 *
 * Copyright: Copyright Digital Mars 2000 - 2020.
 * 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/_equality.d)
 */

module core.internal.array.equality;

// The compiler lowers `lhs == rhs` to `__equals(lhs, rhs)` for
// * dynamic arrays,
// * (most) arrays of different (unqualified) element types, and
// * arrays of structs with custom opEquals.

 // The scalar-only overload takes advantage of known properties of scalars to
 // reduce template instantiation. This is expected to be the most common case.
bool __equals(T1, T2)(scope const T1[] lhs, scope const T2[] rhs)
@nogc nothrow pure @trusted
if (__traits(isScalar, T1) && __traits(isScalar, T2))
{
    const length = lhs.length;

    static if (T1.sizeof == T2.sizeof
        // Signedness needs to match for types that promote to int.
        // (Actually it would be okay to memcmp bool[] and byte[] but that is
        // probably too uncommon to be worth checking for.)
        && (T1.sizeof >= 4 || __traits(isUnsigned, T1) == __traits(isUnsigned, T2))
        && !__traits(isFloating, T1) && !__traits(isFloating, T2))
    {
        if (__ctfe)
            return length == rhs.length && isEqual(lhs.ptr, rhs.ptr, length);
        else
        {
            // This would improperly allow equality of integers and pointers
            // but the CTFE branch will stop this function from compiling then.
            import core.stdc.string : memcmp;
            return length == rhs.length &&
                (!length || 0 == memcmp(cast(const void*) lhs.ptr, cast(const void*) rhs.ptr, length * T1.sizeof));
        }
    }
    else
    {
        return length == rhs.length && isEqual(lhs.ptr, rhs.ptr, length);
    }
}

bool __equals(T1, T2)(scope T1[] lhs, scope T2[] rhs)
if (!__traits(isScalar, T1) || !__traits(isScalar, T2))
{
    if (lhs.length != rhs.length)
        return false;

    if (lhs.length == 0)
        return true;

    static if (useMemcmp!(T1, T2))
    {
        if (!__ctfe)
        {
            static bool trustedMemcmp(scope T1[] lhs, scope T2[] rhs) @trusted @nogc nothrow pure
            {
                pragma(inline, true);
                import core.stdc.string : memcmp;
                return memcmp(cast(void*) lhs.ptr, cast(void*) rhs.ptr, lhs.length * T1.sizeof) == 0;
            }
            return trustedMemcmp(lhs, rhs);
        }
        else
        {
            foreach (const i; 0 .. lhs.length)
            {
                if (at(lhs, i) != at(rhs, i))
                    return false;
            }
            return true;
        }
    }
    else
    {
        foreach (const i; 0 .. lhs.length)
        {
            if (at(lhs, i) != at(rhs, i))
                return false;
        }
        return true;
    }
}

/******************************
 * Helper function for __equals().
 * Outlined to enable __equals() to be inlined, as dmd cannot inline loops.
 */
private
bool isEqual(T1, T2)(scope const T1* t1, scope const T2* t2, size_t length)
{
    foreach (const i; 0 .. length)
        if (t1[i] != t2[i])
            return false;
    return true;
}

@safe unittest
{
    assert(__equals([], []));
    assert(!__equals([1, 2], [1, 2, 3]));
}

@safe unittest
{
    auto a = "hello"c;

    assert(a != "hel");
    assert(a != "helloo");
    assert(a != "betty");
    assert(a == "hello");
    assert(a != "hxxxx");

    float[] fa = [float.nan];
    assert(fa != fa);
}

@safe unittest
{
    struct A
    {
        int a;
    }

    auto arr1 = [A(0), A(2)];
    auto arr2 = [A(0), A(1)];
    auto arr3 = [A(0), A(1)];

    assert(arr1 != arr2);
    assert(arr2 == arr3);
}

@safe unittest
{
    struct A
    {
        int a;
        int b;

        bool opEquals(const A other)
        {
            return this.a == other.b && this.b == other.a;
        }
    }

    auto arr1 = [A(1, 0), A(0, 1)];
    auto arr2 = [A(1, 0), A(0, 1)];
    auto arr3 = [A(0, 1), A(1, 0)];

    assert(arr1 != arr2);
    assert(arr2 == arr3);
}

// https://issues.dlang.org/show_bug.cgi?id=18252
@safe unittest
{
    string[int][] a1, a2;
    assert(__equals(a1, a2));
    assert(a1 == a2);
    a1 ~= [0: "zero"];
    a2 ~= [0: "zero"];
    assert(__equals(a1, a2));
    assert(a1 == a2);
    a2[0][1] = "one";
    assert(!__equals(a1, a2));
    assert(a1 != a2);
}


private:

// - Recursively folds static array types to their element type,
// - maps void to ubyte, and
// - pointers to size_t.
template BaseType(T)
{
    static if (__traits(isStaticArray, T))
        alias BaseType = BaseType!(typeof(T.init[0]));
    else static if (is(immutable T == immutable void))
        alias BaseType = ubyte;
    else static if (is(T == E*, E))
        alias BaseType = size_t;
    else
        alias BaseType = T;
}

// Use memcmp if the element sizes match and both base element types are integral.
// Due to int promotion, disallow small integers of diverging signed-ness though.
template useMemcmp(T1, T2)
{
    static if (T1.sizeof != T2.sizeof)
        enum useMemcmp = false;
    else
    {
        alias B1 = BaseType!T1;
        alias B2 = BaseType!T2;
        enum useMemcmp = __traits(isIntegral, B1) && __traits(isIntegral, B2)
           && !( (B1.sizeof < 4 || B2.sizeof < 4) && __traits(isUnsigned, B1) != __traits(isUnsigned, B2) );
    }
}

unittest
{
    enum E { foo, bar }

    static assert(useMemcmp!(byte, byte));
    static assert(useMemcmp!(ubyte, ubyte));
    static assert(useMemcmp!(void, const void));
    static assert(useMemcmp!(void, immutable bool));
    static assert(useMemcmp!(void, inout char));
    static assert(useMemcmp!(void, shared ubyte));
    static assert(!useMemcmp!(void, byte));       // differing signed-ness
    static assert(!useMemcmp!(char[8], byte[8])); // ditto

    static assert(useMemcmp!(short, short));
    static assert(useMemcmp!(wchar, ushort));
    static assert(!useMemcmp!(wchar, short)); // differing signed-ness

    static assert(useMemcmp!(int, uint)); // no promotion, ignoring signed-ness
    static assert(useMemcmp!(dchar, E));

    static assert(useMemcmp!(immutable void*, size_t));
    static assert(useMemcmp!(double*, ptrdiff_t));
    static assert(useMemcmp!(long[2][3], const(ulong)[2][3]));

    static assert(!useMemcmp!(float, float));
    static assert(!useMemcmp!(double[2], double[2]));
    static assert(!useMemcmp!(Object, Object));
    static assert(!useMemcmp!(int[], int[]));
}

// https://issues.dlang.org/show_bug.cgi?id=21094
unittest
{
    static class C
    {
        int a;
    }
    static struct S
    {
        bool isValid;
        C fib;

        inout(C) get() pure @safe @nogc nothrow inout
        {
            return isValid ? fib : C.init;
        }
        T opCast(T : C)() const { return null; }

        alias get this;
    }

    auto foo(S[] lhs, S[] rhs)
    {
        return lhs == rhs;
    }
}

// Returns a reference to an array element, eliding bounds check and
// casting void to ubyte.
pragma(inline, true)
ref at(T)(T[] r, size_t i) @trusted
    // exclude opaque structs due to https://issues.dlang.org/show_bug.cgi?id=20959
    if (!(is(T == struct) && !is(typeof(T.sizeof))))
{
    static if (is(immutable T == immutable void))
        return (cast(ubyte*) r.ptr)[i];
    else
        return r.ptr[i];
}