diff options
| author | Iain Buclaw <ibuclaw@gdcproject.org> | 2019-02-10 21:01:24 +0000 |
|---|---|---|
| committer | Iain Buclaw <ibuclaw@gcc.gnu.org> | 2019-02-10 21:01:24 +0000 |
| commit | e613d992667a90ff731bbcecbb4ae6fa15adde31 (patch) | |
| tree | ab84eeb1414db276d7d507c01749431e7e3dcf6e /libphobos | |
| parent | f1b7b50affd1e9eea1f1e3be8a0804fd94fb6b39 (diff) | |
libphobos: Apply core.internal.hash updates from druntime
Backported from upstream druntime 2.084
Reviewed-on: https://github.com/dlang/druntime/pull/2469
libphobos/ChangeLog:
* libdruntime/Makefile.am (DRUNTIME_DSOURCES): Remove rt/util/hash.d
* libdruntime/Makefile.in: Rebuild.
* testsuite/libphobos.aa/aa.exp: New file.
* testsuite/libphobos.aa/test_aa.d: New test.
* testsuite/libphobos.hash/hash.exp: New file.
* testsuite/libphobos.hash/test_hash.d: New test.
From-SVN: r268754
Diffstat (limited to 'libphobos')
50 files changed, 2630 insertions, 1368 deletions
diff --git a/libphobos/ChangeLog b/libphobos/ChangeLog index 04bfcafad15..2aa99a426f8 100644 --- a/libphobos/ChangeLog +++ b/libphobos/ChangeLog @@ -1,3 +1,12 @@ +2019-02-10 Iain Buclaw <ibuclaw@gdcproject.org> + + * libdruntime/Makefile.am (DRUNTIME_DSOURCES): Remove rt/util/hash.d + * libdruntime/Makefile.in: Rebuild. + * testsuite/libphobos.aa/aa.exp: New file. + * testsuite/libphobos.aa/test_aa.d: New test. + * testsuite/libphobos.hash/hash.exp: New file. + * testsuite/libphobos.hash/test_hash.d: New test. + 2019-01-12 Iain Buclaw <ibuclaw@gdcproject.org> * README.gcc: New file. diff --git a/libphobos/libdruntime/MERGE b/libphobos/libdruntime/MERGE index b98e0ed6c16..2c8c70c83f2 100644 --- a/libphobos/libdruntime/MERGE +++ b/libphobos/libdruntime/MERGE @@ -1,4 +1,4 @@ -f2db21937e650553066c30f1a9d5a7d08a1b3573 +cc215408bbdbc3324a95080aeef31287f663e57c The first line of this file holds the git revision number of the last merge done from the dlang/druntime repository. diff --git a/libphobos/libdruntime/Makefile.am b/libphobos/libdruntime/Makefile.am index 7630183c9c3..4894435510e 100644 --- a/libphobos/libdruntime/Makefile.am +++ b/libphobos/libdruntime/Makefile.am @@ -197,8 +197,8 @@ DRUNTIME_DSOURCES = core/atomic.d core/attribute.d core/bitop.d \ rt/typeinfo/ti_ucent.d rt/typeinfo/ti_uint.d rt/typeinfo/ti_ulong.d \ rt/typeinfo/ti_ushort.d rt/typeinfo/ti_void.d rt/typeinfo/ti_wchar.d \ rt/util/array.d rt/util/container/array.d rt/util/container/common.d \ - rt/util/container/hashtab.d rt/util/container/treap.d rt/util/hash.d \ - rt/util/random.d rt/util/typeinfo.d rt/util/utf.d + rt/util/container/hashtab.d rt/util/container/treap.d rt/util/random.d \ + rt/util/typeinfo.d rt/util/utf.d DRUNTIME_DSOURCES_STDCXX = core/stdcpp/exception.d \ core/stdcpp/typeinfo.d diff --git a/libphobos/libdruntime/Makefile.in b/libphobos/libdruntime/Makefile.in index d07a8f98099..0842862091f 100644 --- a/libphobos/libdruntime/Makefile.in +++ b/libphobos/libdruntime/Makefile.in @@ -229,8 +229,7 @@ am__objects_1 = core/atomic.lo core/attribute.lo core/bitop.lo \ rt/typeinfo/ti_wchar.lo rt/util/array.lo \ rt/util/container/array.lo rt/util/container/common.lo \ rt/util/container/hashtab.lo rt/util/container/treap.lo \ - rt/util/hash.lo rt/util/random.lo rt/util/typeinfo.lo \ - rt/util/utf.lo + rt/util/random.lo rt/util/typeinfo.lo rt/util/utf.lo am__objects_2 = gc/bits.lo gc/config.lo gc/gcinterface.lo \ gc/impl/conservative/gc.lo gc/impl/manual/gc.lo gc/os.lo \ gc/pooltable.lo gc/proxy.lo @@ -831,8 +830,8 @@ DRUNTIME_DSOURCES = core/atomic.d core/attribute.d core/bitop.d \ rt/typeinfo/ti_ucent.d rt/typeinfo/ti_uint.d rt/typeinfo/ti_ulong.d \ rt/typeinfo/ti_ushort.d rt/typeinfo/ti_void.d rt/typeinfo/ti_wchar.d \ rt/util/array.d rt/util/container/array.d rt/util/container/common.d \ - rt/util/container/hashtab.d rt/util/container/treap.d rt/util/hash.d \ - rt/util/random.d rt/util/typeinfo.d rt/util/utf.d + rt/util/container/hashtab.d rt/util/container/treap.d rt/util/random.d \ + rt/util/typeinfo.d rt/util/utf.d DRUNTIME_DSOURCES_STDCXX = core/stdcpp/exception.d \ core/stdcpp/typeinfo.d @@ -1256,7 +1255,6 @@ rt/util/container/array.lo: rt/util/container/$(am__dirstamp) rt/util/container/common.lo: rt/util/container/$(am__dirstamp) rt/util/container/hashtab.lo: rt/util/container/$(am__dirstamp) rt/util/container/treap.lo: rt/util/container/$(am__dirstamp) -rt/util/hash.lo: rt/util/$(am__dirstamp) rt/util/random.lo: rt/util/$(am__dirstamp) rt/util/typeinfo.lo: rt/util/$(am__dirstamp) rt/util/utf.lo: rt/util/$(am__dirstamp) diff --git a/libphobos/libdruntime/core/internal/convert.d b/libphobos/libdruntime/core/internal/convert.d index c4745b6f5a7..2b4fc31e3b5 100644 --- a/libphobos/libdruntime/core/internal/convert.d +++ b/libphobos/libdruntime/core/internal/convert.d @@ -33,7 +33,7 @@ private ubyte[] ctfe_alloc()(size_t n) } } -@trusted pure nothrow +@trusted pure nothrow @nogc const(ubyte)[] toUbyte(T)(const ref T val) if (is(Unqual!T == float) || is(Unqual!T == double) || is(Unqual!T == real) || is(Unqual!T == ifloat) || is(Unqual!T == idouble) || is(Unqual!T == ireal)) { @@ -72,7 +72,7 @@ const(ubyte)[] toUbyte(T)(const ref T val) if (is(Unqual!T == float) || is(Unqua ulong mantissa2 = parsed.mantissa2; off_bytes--; // go back one, since mantissa only stored data in 56 // bits, ie 7 bytes - for(; off_bytes < FloatTraits!T.MANTISSA/8; ++off_bytes) + for (; off_bytes < FloatTraits!T.MANTISSA/8; ++off_bytes) { buff[off_bytes] = cast(ubyte)mantissa2; mantissa2 >>= 8; @@ -114,13 +114,13 @@ const(ubyte)[] toUbyte(T)(const ref T val) if (is(Unqual!T == float) || is(Unqua } } -@safe pure nothrow +@safe pure nothrow @nogc private Float parse(bool is_denormalized = false, T)(T x) if (is(Unqual!T == ifloat) || is(Unqual!T == idouble) || is(Unqual!T == ireal)) { return parse(x.im); } -@safe pure nothrow +@safe pure nothrow @nogc private Float parse(bool is_denormalized = false, T:real)(T x_) if (floatFormat!T != FloatFormat.Real80) { Unqual!T x = x_; @@ -178,7 +178,7 @@ private Float parse(bool is_denormalized = false, T:real)(T x_) if (floatFormat! } } -@safe pure nothrow +@safe pure nothrow @nogc private Float parse(bool _ = false, T:real)(T x_) if (floatFormat!T == FloatFormat.Real80) { Unqual!T x = x_; @@ -291,10 +291,10 @@ private template FloatTraits(T) if (floatFormat!T == FloatFormat.Quadruple) } -@safe pure nothrow +@safe pure nothrow @nogc private real binPow2(int pow) { - static real binPosPow2(int pow) @safe pure nothrow + static real binPosPow2(int pow) @safe pure nothrow @nogc { assert(pow > 0); @@ -319,14 +319,14 @@ private real binPow2(int pow) //Need in CTFE, because CTFE float and double expressions computed more precisely that run-time expressions. -@safe pure nothrow +@safe pure nothrow @nogc private ulong shiftrRound(ulong x) { return (x >> 1) + (x & 1); } -@safe pure nothrow -private uint binLog2(T)(T x) +@safe pure nothrow @nogc +private uint binLog2(T)(const T x) { assert(x > 0); int max = 2 ^^ (FloatTraits!T.EXPONENT-1)-1; @@ -353,7 +353,7 @@ private uint binLog2(T)(T x) return max; } -@safe pure nothrow +@safe pure nothrow @nogc private Float denormalizedMantissa(T)(T x, uint sign) if (floatFormat!T == FloatFormat.Real80) { x *= 2.0L^^FloatTraits!T.MANTISSA; @@ -362,7 +362,7 @@ private Float denormalizedMantissa(T)(T x, uint sign) if (floatFormat!T == Float return Float(fl.mantissa >> pow, 0, sign); } -@safe pure nothrow +@safe pure nothrow @nogc private Float denormalizedMantissa(T)(T x, uint sign) if (floatFormat!T == FloatFormat.Float || floatFormat!T == FloatFormat.Double) { @@ -372,7 +372,7 @@ private Float denormalizedMantissa(T)(T x, uint sign) return Float(shiftrRound(mant), 0, sign); } -@safe pure nothrow +@safe pure nothrow @nogc private Float denormalizedMantissa(T)(T x, uint sign) if (floatFormat!T == FloatFormat.Quadruple) { x *= 2.0L^^FloatTraits!T.MANTISSA; @@ -568,21 +568,35 @@ template floatFormat(T) if (is(T:real) || is(T:ireal)) } // all toUbyte functions must be evaluable at compile time -@trusted pure nothrow -const(ubyte)[] toUbyte(T)(T[] arr) if (T.sizeof == 1) +@trusted pure nothrow @nogc +const(ubyte)[] toUbyte(T)(const T[] arr) if (T.sizeof == 1) { return cast(const(ubyte)[])arr; } -@trusted pure nothrow -const(ubyte)[] toUbyte(T)(T[] arr) if ((is(typeof(toUbyte(arr[0])) == const(ubyte)[])) && (T.sizeof > 1)) +@trusted pure nothrow @nogc +const(ubyte)[] toUbyte(T)(const T[] arr) if (T.sizeof > 1) { if (__ctfe) { - const(ubyte)[] ret; - foreach (cur; arr) + ubyte[] ret = ctfe_alloc(T.sizeof * arr.length); + static if (is(T EType == enum)) // Odd style is to avoid template instantiation in most cases. + alias E = OriginalType!EType; + else + alias E = T; + static if (is(E == struct) || is(E == union) || __traits(isStaticArray, E) || !is(typeof(arr[0] is null))) + { + size_t offset = 0; + foreach (ref cur; arr) + { + ret[offset .. offset + T.sizeof] = toUbyte(cur)[0 .. T.sizeof]; + offset += T.sizeof; + } + } + else { - ret ~= toUbyte(cur); + foreach (cur; arr) + assert(cur is null, "Unable to compute byte representation of non-null pointer at compile time"); } return ret; } @@ -592,14 +606,16 @@ const(ubyte)[] toUbyte(T)(T[] arr) if ((is(typeof(toUbyte(arr[0])) == const(ubyt } } -@trusted pure nothrow -const(ubyte)[] toUbyte(T)(ref T val) if (__traits(isIntegral, T) && !is(T == enum)) +@trusted pure nothrow @nogc +const(ubyte)[] toUbyte(T)(const ref T val) if (__traits(isIntegral, T) && !is(T == enum) && !is(T == __vector)) { static if (T.sizeof == 1) { if (__ctfe) { - return cast(const(ubyte)[])[val]; + ubyte[] result = ctfe_alloc(1); + result[0] = cast(ubyte) val; + return result; } else { @@ -608,7 +624,7 @@ const(ubyte)[] toUbyte(T)(ref T val) if (__traits(isIntegral, T) && !is(T == enu } else if (__ctfe) { - ubyte[T.sizeof] tmp; + ubyte[] tmp = ctfe_alloc(T.sizeof); Unqual!T val_ = val; for (size_t i = 0; i < T.sizeof; ++i) { @@ -618,7 +634,7 @@ const(ubyte)[] toUbyte(T)(ref T val) if (__traits(isIntegral, T) && !is(T == enu tmp[idx] = cast(ubyte)(val_&0xff); val_ >>= 8; } - return tmp[].dup; + return tmp; } else { @@ -626,14 +642,41 @@ const(ubyte)[] toUbyte(T)(ref T val) if (__traits(isIntegral, T) && !is(T == enu } } -@trusted pure nothrow -const(ubyte)[] toUbyte(T)(ref T val) if (is(Unqual!T == cfloat) || is(Unqual!T == cdouble) ||is(Unqual!T == creal)) +@trusted pure nothrow @nogc +const(ubyte)[] toUbyte(T)(const ref T val) if (is(T == __vector)) +{ + if (!__ctfe) + return (cast(const ubyte*) &val)[0 .. T.sizeof]; + else static if (is(typeof(val[0]) : void)) + assert(0, "Unable to compute byte representation of " ~ T.stringof ~ " at compile time."); + else + { + // This code looks like it should work in CTFE but it segfaults: + // auto a = val.array; + // return toUbyte(a); + alias E = typeof(val[0]); + ubyte[] result = ctfe_alloc(T.sizeof); + for (size_t i = 0, j = 0; i < T.sizeof; i += E.sizeof, ++j) + { + result[i .. i + E.sizeof] = toUbyte(val[j]); + } + return result; + } +} + +@trusted pure nothrow @nogc +const(ubyte)[] toUbyte(T)(const ref T val) if (is(Unqual!T == cfloat) || is(Unqual!T == cdouble) ||is(Unqual!T == creal)) { if (__ctfe) { auto re = val.re; auto im = val.im; - return (re.toUbyte() ~ im.toUbyte()); + auto a = re.toUbyte(); + auto b = im.toUbyte(); + ubyte[] result = ctfe_alloc(a.length + b.length); + result[0 .. a.length] = a[0 .. a.length]; + result[a.length .. $] = b[0 .. b.length]; + return result; } else { @@ -641,14 +684,13 @@ const(ubyte)[] toUbyte(T)(ref T val) if (is(Unqual!T == cfloat) || is(Unqual!T = } } -@trusted pure nothrow -const(ubyte)[] toUbyte(T)(ref T val) if (is(T == enum) && is(typeof(toUbyte(cast(V)val)) == const(ubyte)[])) +@trusted pure nothrow @nogc +const(ubyte)[] toUbyte(T)(const ref T val) if (is(T == enum)) { if (__ctfe) { static if (is(T V == enum)){} - V e_val = val; - return toUbyte(e_val); + return toUbyte(cast(const V) val); } else { @@ -656,76 +698,65 @@ const(ubyte)[] toUbyte(T)(ref T val) if (is(T == enum) && is(typeof(toUbyte(cast } } -private bool isNonReference(T)() +nothrow pure @safe unittest { - static if (is(T == struct) || is(T == union)) - { - return isNonReferenceStruct!T(); - } - else static if (__traits(isStaticArray, T)) - { - return isNonReference!(typeof(T.init[0]))(); - } - else static if (is(T E == enum)) - { - return isNonReference!(E)(); - } - else static if (!__traits(isScalar, T)) - { - return false; - } - else static if (is(T V : V*)) - { - return false; - } - else static if (is(T == function)) - { - return false; - } - else - { - return true; - } + // Issue 19008 - check toUbyte works on enums. + enum Month : uint { jan = 1} + Month m = Month.jan; + const bytes = toUbyte(m); + enum ctfe_works = (() => { Month x = Month.jan; return toUbyte(x).length > 0; })(); } -private bool isNonReferenceStruct(T)() if (is(T == struct) || is(T == union)) +@trusted pure nothrow @nogc +const(ubyte)[] toUbyte(T)(const ref T val) if (is(T == delegate) || is(T : V*, V) && __traits(getAliasThis, T).length == 0) { - foreach (cur; T.init.tupleof) + if (__ctfe) { - static if (!isNonReference!(typeof(cur))()) return false; + if (val !is null) assert(0, "Unable to compute byte representation of non-null pointer at compile time"); + return ctfe_alloc(T.sizeof); + } + else + { + return (cast(const(ubyte)*)&val)[0 .. T.sizeof]; } - - return true; } -@trusted pure nothrow -const(ubyte)[] toUbyte(T)(ref T val) if (is(T == struct) || is(T == union)) +@trusted pure nothrow @nogc +const(ubyte)[] toUbyte(T)(const ref T val) if (is(T == struct) || is(T == union)) { if (__ctfe) { - ubyte[T.sizeof] bytes; - foreach (key, cur; val.tupleof) + ubyte[] bytes = ctfe_alloc(T.sizeof); + foreach (key, ref cur; val.tupleof) { - alias CUR_TYPE = typeof(cur); - static if (isNonReference!(CUR_TYPE)()) - { - bytes[val.tupleof[key].offsetof .. val.tupleof[key].offsetof + cur.sizeof] = toUbyte(cur)[]; - } - else static if (is(typeof(val.tupleof[key] is null))) + static if (is(typeof(cur) EType == enum)) // Odd style is to avoid template instantiation in most cases. + alias CurType = OriginalType!EType; + else + alias CurType = typeof(cur); + static if (is(CurType == struct) || is(CurType == union) || __traits(isStaticArray, CurType) || !is(typeof(cur is null))) { - assert(val.tupleof[key] is null, "Unable to compute byte representation of non-null reference field at compile time"); - //skip, because val bytes are zeros + bytes[val.tupleof[key].offsetof .. val.tupleof[key].offsetof + CurType.sizeof] = toUbyte(cur)[]; } else { - //pragma(msg, "is null: ", typeof(CUR_TYPE).stringof); - assert(0, "Unable to compute byte representation of "~typeof(CUR_TYPE).stringof~" field at compile time"); + assert(cur is null, "Unable to compute byte representation of non-null reference field at compile time"); + //skip, because val bytes are zeros } } - return bytes[].dup; + return bytes; } else { return (cast(const(ubyte)*)&val)[0 .. T.sizeof]; } } + +// Strips off all `enum`s from type `T`. +// Perhaps move to core.internal.types. +private template OriginalType(T) +{ + static if (is(T EType == enum)) + alias OriginalType = .OriginalType!EType; + else + alias OriginalType = T; +} diff --git a/libphobos/libdruntime/core/internal/hash.d b/libphobos/libdruntime/core/internal/hash.d index 1805860a0cf..5de559cf8b1 100644 --- a/libphobos/libdruntime/core/internal/hash.d +++ b/libphobos/libdruntime/core/internal/hash.d @@ -10,9 +10,198 @@ module core.internal.hash; import core.internal.convert; +import core.internal.traits : allSatisfy; + +// If true ensure that positive zero and negative zero have the same hash. +// Historically typeid(float).getHash did this but hashOf(float) did not. +private enum floatCoalesceZeroes = true; +// If true ensure that all NaNs of the same floating point type have the same hash. +// Historically typeid(float).getHash didn't do this but hashOf(float) did. +private enum floatCoalesceNaNs = true; + +// If either of the above are true then no struct or array that contains the +// representation of a floating point number may be hashed with `bytesHash`. + +@nogc nothrow pure @safe unittest +{ + static if (floatCoalesceZeroes) + assert(hashOf(+0.0) == hashOf(-0.0)); // Same hash for +0.0 and -0.0. + static if (floatCoalesceNaNs) + assert(hashOf(double.nan) == hashOf(-double.nan)); // Same hash for different NaN. +} + +private enum hasCallableToHash(T) = __traits(compiles, + { + size_t hash = ((T* x) => (*x).toHash())(null); + }); + +@nogc nothrow pure @safe unittest +{ + static struct S { size_t toHash() { return 4; } } + assert(hasCallableToHash!S); + assert(!hasCallableToHash!(shared const S)); +} + +private enum isFinalClassWithAddressBasedHash(T) = __traits(isFinalClass, T) + // Use __traits(compiles, ...) in case there are multiple overloads of `toHash`. + && __traits(compiles, {static assert(&Object.toHash is &T.toHash);}); + +@nogc nothrow pure @safe unittest +{ + static class C1 {} + final static class C2 : C1 {} + final static class C3 : C1 { override size_t toHash() const nothrow { return 1; }} + static assert(!isFinalClassWithAddressBasedHash!Object); + static assert(!isFinalClassWithAddressBasedHash!C1); + static assert(isFinalClassWithAddressBasedHash!C2); + static assert(!isFinalClassWithAddressBasedHash!C3); +} + +/+ +Is it valid to calculate a hash code for T based on the bits of its +representation? Always false for interfaces, dynamic arrays, and +associative arrays. False for all classes except final classes that do +not override `toHash`. + +Note: according to the spec as of +https://github.com/dlang/dlang.org/commit/d66eff16491b0664c0fc00ba80a7aa291703f1f2 +the contents of unnamed paddings between fields is undefined. Currently +this hashing implementation assumes that the padding contents (if any) +for all instances of `T` are the same. The correctness of this +assumption is yet to be verified. ++/ +private template canBitwiseHash(T) +{ + static if (is(T EType == enum)) + enum canBitwiseHash = .canBitwiseHash!EType; + else static if (__traits(isFloating, T)) + enum canBitwiseHash = !(floatCoalesceZeroes || floatCoalesceNaNs); + else static if (__traits(isScalar, T)) + enum canBitwiseHash = true; + else static if (is(T == class)) + { + enum canBitwiseHash = isFinalClassWithAddressBasedHash!T; + } + else static if (is(T == interface)) + { + enum canBitwiseHash = false; + } + else static if (is(T == struct)) + { + static if (hasCallableToHash!T || __traits(isNested, T)) + enum canBitwiseHash = false; + else + enum canBitwiseHash = allSatisfy!(.canBitwiseHash, typeof(T.tupleof)); + } + else static if (is(T == union)) + { + // Right now we always bytewise hash unions that lack callable `toHash`. + enum canBitwiseHash = !hasCallableToHash!T; + } + else static if (is(T E : E[])) + { + static if (__traits(isStaticArray, T)) + enum canBitwiseHash = (T.length == 0) || .canBitwiseHash!E; + else + enum canBitwiseHash = false; + } + else static if (__traits(isAssociativeArray, T)) + { + enum canBitwiseHash = false; + } + else + { + static assert(is(T == delegate) || is(T : void) || is(T : typeof(null)), + "Internal error: unanticipated type "~T.stringof); + enum canBitwiseHash = true; + } +} + +// Overly restrictive for simplicity: has false negatives but no false positives. +private template useScopeConstPassByValue(T) +{ + static if (__traits(isScalar, T)) + enum useScopeConstPassByValue = true; + else static if (is(T == class) || is(T == interface)) + // Overly restrictive for simplicity. + enum useScopeConstPassByValue = isFinalClassWithAddressBasedHash!T; + else static if (is(T == struct) || is(T == union)) + { + // Overly restrictive for simplicity. + enum useScopeConstPassByValue = T.sizeof <= (int[]).sizeof && + __traits(isPOD, T) && // "isPOD" just to check there's no dtor or postblit. + canBitwiseHash!T; // We can't verify toHash doesn't leak. + } + else static if (is(T : E[], E)) + { + static if (!__traits(isStaticArray, T)) + // Overly restrictive for simplicity. + enum useScopeConstPassByValue = .useScopeConstPassByValue!E; + else static if (T.length == 0) + enum useScopeConstPassByValue = true; + else + enum useScopeConstPassByValue = T.sizeof <= (uint[]).sizeof + && .useScopeConstPassByValue!(typeof(T.init[0])); + } + else static if (is(T : V[K], K, V)) + { + // Overly restrictive for simplicity. + enum useScopeConstPassByValue = .useScopeConstPassByValue!K + && .useScopeConstPassByValue!V; + } + else + { + static assert(is(T == delegate) || is(T : void) || is(T : typeof(null)), + "Internal error: unanticipated type "~T.stringof); + enum useScopeConstPassByValue = true; + } +} + +@safe unittest +{ + static assert(useScopeConstPassByValue!int); + static assert(useScopeConstPassByValue!string); + + static int ctr; + static struct S1 { ~this() { ctr++; } } + static struct S2 { this(this) { ctr++; } } + static assert(!useScopeConstPassByValue!S1, + "Don't default pass by value a struct with a non-vacuous destructor."); + static assert(!useScopeConstPassByValue!S2, + "Don't default pass by value a struct with a non-vacuous postblit."); +} + +//enum hash. CTFE depends on base type +size_t hashOf(T)(scope const T val) +if (is(T EType == enum) && useScopeConstPassByValue!EType) +{ + static if (is(T EType == enum)) //for EType + { + return hashOf(cast(const EType) val); + } + else + { + static assert(0); + } +} //enum hash. CTFE depends on base type -size_t hashOf(T)(auto ref T val, size_t seed = 0) if (is(T == enum)) +size_t hashOf(T)(scope const T val, size_t seed) +if (is(T EType == enum) && useScopeConstPassByValue!EType) +{ + static if (is(T EType == enum)) //for EType + { + return hashOf(cast(const EType) val, seed); + } + else + { + static assert(0); + } +} + +//enum hash. CTFE depends on base type +size_t hashOf(T)(auto ref T val, size_t seed = 0) +if (is(T EType == enum) && !useScopeConstPassByValue!EType) { static if (is(T EType == enum)) //for EType { @@ -25,75 +214,223 @@ size_t hashOf(T)(auto ref T val, size_t seed = 0) if (is(T == enum)) } } -//CTFE ready (depends on base type). Can be merged with dynamic array hash -size_t hashOf(T)(auto ref T val, size_t seed = 0) if (!is(T == enum) && __traits(isStaticArray, T)) +//CTFE ready (depends on base type). +size_t hashOf(T)(scope const auto ref T val, size_t seed = 0) +if (!is(T == enum) && __traits(isStaticArray, T) && canBitwiseHash!T) { - size_t cur_hash = seed; - foreach (ref cur; val) + // FIXME: + // We would like to to do this: + // + //static if (T.length == 0) + // return seed; + //else static if (T.length == 1) + // return hashOf(val[0], seed); + //else + // return bytesHashWithExactSizeAndAlignment!T(toUbyte(val), seed); + // + // ... but that's inefficient when using a runtime TypeInfo (introduces a branch) + // and PR #2243 wants typeid(T).getHash(&val) to produce the same result as + // hashOf(val). + static if (T.length == 0) + { + return bytesHashAlignedBy!size_t((ubyte[]).init, seed); + } + static if (is(typeof(toUbyte(val)) == const(ubyte)[])) { - cur_hash = hashOf(cur, cur_hash); + return bytesHashAlignedBy!T(toUbyte(val), seed); + } + else //Other types. CTFE unsupported + { + assert(!__ctfe, "unable to compute hash of "~T.stringof~" at compile time"); + return bytesHashAlignedBy!T((cast(const(ubyte)*) &val)[0 .. T.sizeof], seed); } - return cur_hash; } -//dynamic array hash +//CTFE ready (depends on base type). size_t hashOf(T)(auto ref T val, size_t seed = 0) +if (!is(T == enum) && __traits(isStaticArray, T) && !canBitwiseHash!T) +{ + // FIXME: + // We would like to to do this: + // + //static if (T.length == 0) + // return seed; + //else static if (T.length == 1) + // return hashOf(val[0], seed); + //else + // /+ hash like a dynamic array +/ + // + // ... but that's inefficient when using a runtime TypeInfo (introduces a branch) + // and PR #2243 wants typeid(T).getHash(&val) to produce the same result as + // hashOf(val). + return hashOf(val[], seed); +} + +//dynamic array hash +size_t hashOf(T)(scope const T val, size_t seed = 0) if (!is(T == enum) && !is(T : typeof(null)) && is(T S: S[]) && !__traits(isStaticArray, T) - && !is(T == struct) && !is(T == class) && !is(T == union)) + && !is(T == struct) && !is(T == class) && !is(T == union) + && (__traits(isScalar, S) || canBitwiseHash!S)) { alias ElementType = typeof(val[0]); - static if (is(ElementType == interface) || is(ElementType == class) || - ((is(ElementType == struct) || is(ElementType == union)) - && is(typeof(val[0].toHash()) == size_t))) - //class or interface array or struct array with toHash(); CTFE depend on toHash() method + static if (!canBitwiseHash!ElementType) { size_t hash = seed; - foreach (o; val) + foreach (ref o; val) { - hash = hashOf(o, hash); + hash = hashOf(hashOf(o), hash); // double hashing to match TypeInfo.getHash } return hash; } else static if (is(typeof(toUbyte(val)) == const(ubyte)[])) //ubyteble array (arithmetic types and structs without toHash) CTFE ready for arithmetic types and structs without reference fields { - auto bytes = toUbyte(val); - return bytesHash(bytes.ptr, bytes.length, seed); + return bytesHashAlignedBy!ElementType(toUbyte(val), seed); } else //Other types. CTFE unsupported { - assert(!__ctfe, "unable to compute hash of "~T.stringof); - return bytesHash(val.ptr, ElementType.sizeof*val.length, seed); + assert(!__ctfe, "unable to compute hash of "~T.stringof~" at compile time"); + return bytesHashAlignedBy!ElementType((cast(const(ubyte)*) val.ptr)[0 .. ElementType.sizeof*val.length], seed); + } +} + +//dynamic array hash +size_t hashOf(T)(T val, size_t seed = 0) +if (!is(T == enum) && !is(T : typeof(null)) && is(T S: S[]) && !__traits(isStaticArray, T) + && !is(T == struct) && !is(T == class) && !is(T == union) + && !(__traits(isScalar, S) || canBitwiseHash!S)) +{ + size_t hash = seed; + foreach (ref o; val) + { + hash = hashOf(hashOf(o), hash); // double hashing because TypeInfo.getHash doesn't allow to pass seed value } + return hash; +} + +//arithmetic type hash +@trusted @nogc nothrow pure +size_t hashOf(T)(scope const T val) if (!is(T == enum) && __traits(isArithmetic, T) + && __traits(isIntegral, T) && T.sizeof <= size_t.sizeof && !is(T == __vector)) +{ + return val; } //arithmetic type hash -@trusted nothrow pure -size_t hashOf(T)(auto ref T val, size_t seed = 0) if (!is(T == enum) && __traits(isArithmetic, T)) +@trusted @nogc nothrow pure +size_t hashOf(T)(scope const T val, size_t seed) if (!is(T == enum) && __traits(isArithmetic, T) + && __traits(isIntegral, T) && T.sizeof <= size_t.sizeof && !is(T == __vector)) +{ + static if (size_t.sizeof < ulong.sizeof) + { + //MurmurHash3 32-bit single round + enum uint c1 = 0xcc9e2d51; + enum uint c2 = 0x1b873593; + enum uint c3 = 0xe6546b64; + enum uint r1 = 15; + enum uint r2 = 13; + } + else + { + //Half of MurmurHash3 64-bit single round + //(omits second interleaved update) + enum ulong c1 = 0x87c37b91114253d5; + enum ulong c2 = 0x4cf5ad432745937f; + enum ulong c3 = 0x52dce729; + enum uint r1 = 31; + enum uint r2 = 27; + } + size_t h = c1 * val; + h = (h << r1) | (h >>> (size_t.sizeof * 8 - r1)); + h = (h * c2) ^ seed; + h = (h << r2) | (h >>> (size_t.sizeof * 8 - r2)); + return h * 5 + c3; +} + +//arithmetic type hash +@trusted @nogc nothrow pure +size_t hashOf(T)(scope const T val, size_t seed = 0) if (!is(T == enum) && __traits(isArithmetic, T) + && (!__traits(isIntegral, T) || T.sizeof > size_t.sizeof) && !is(T == __vector)) { static if (__traits(isFloating, val)) { - T data = (val != val) ? T.nan : val; - auto bytes = toUbyte(data); - return bytesHash(bytes.ptr, bytes.length, seed); + static if (floatCoalesceZeroes || floatCoalesceNaNs) + { + import core.internal.traits : Unqual; + Unqual!T data = val; + // +0.0 and -0.0 become the same. + static if (floatCoalesceZeroes && is(typeof(data = 0))) + if (data == 0) data = 0; + static if (floatCoalesceZeroes && is(typeof(data = 0.0i))) + if (data == 0.0i) data = 0.0i; + static if (floatCoalesceZeroes && is(typeof(data = 0.0 + 0.0i))) + { + if (data.re == 0.0) data = 0.0 + (data.im * 1.0i); + if (data.im == 0.0i) data = data.re + 0.0i; + } + static if (floatCoalesceNaNs) + if (data != data) data = T.nan; // All NaN patterns become the same. + } + else + { + alias data = val; + } + + static if (T.mant_dig == float.mant_dig && T.sizeof == uint.sizeof) + return hashOf(*cast(const uint*) &data, seed); + else static if (T.mant_dig == double.mant_dig && T.sizeof == ulong.sizeof) + return hashOf(*cast(const ulong*) &data, seed); + else + return bytesHashWithExactSizeAndAlignment!T(toUbyte(data), seed); } else { - auto bytes = toUbyte(val); - return bytesHash(bytes.ptr, bytes.length, seed); + static assert(T.sizeof > size_t.sizeof && __traits(isIntegral, T)); + foreach (i; 0 .. T.sizeof / size_t.sizeof) + seed = hashOf(cast(size_t) (val >>> (size_t.sizeof * 8 * i)), seed); + return seed; } } +size_t hashOf(T)(scope const auto ref T val, size_t seed = 0) @safe @nogc nothrow pure +if (is(T == __vector) && !is(T == enum)) +{ + static if (__traits(isFloating, T) && (floatCoalesceZeroes || floatCoalesceNaNs)) + { + if (__ctfe) + { + // Workaround for CTFE bug. + alias E = Unqual!(typeof(val[0])); + E[T.sizeof / E.sizeof] array; + foreach (i; 0 .. T.sizeof / E.sizeof) + array[i] = val[i]; + return hashOf(array, seed); + } + return hashOf(val.array, seed); + } + else + { + return bytesHashAlignedBy!T(toUbyte(val), seed); + } +} + +//typeof(null) hash. CTFE supported +@trusted @nogc nothrow pure +size_t hashOf(T)(scope const T val) if (!is(T == enum) && is(T : typeof(null))) +{ + return 0; +} + //typeof(null) hash. CTFE supported -@trusted nothrow pure -size_t hashOf(T)(auto ref T val, size_t seed = 0) if (!is(T == enum) && is(T : typeof(null))) +@trusted @nogc nothrow pure +size_t hashOf(T)(scope const T val, size_t seed) if (!is(T == enum) && is(T : typeof(null))) { - return hashOf(cast(void*)null); + return hashOf(size_t(0), seed); } //Pointers hash. CTFE unsupported if not null -@trusted nothrow pure -size_t hashOf(T)(auto ref T val, size_t seed = 0) +@trusted @nogc nothrow pure +size_t hashOf(T)(scope const T val) if (!is(T == enum) && is(T V : V*) && !is(T : typeof(null)) && !is(T == struct) && !is(T == class) && !is(T == union)) { @@ -101,7 +438,7 @@ if (!is(T == enum) && is(T V : V*) && !is(T : typeof(null)) { if (val is null) { - return hashOf(cast(size_t)0); + return 0; } else { @@ -109,15 +446,41 @@ if (!is(T == enum) && is(T V : V*) && !is(T : typeof(null)) } } - return hashOf(cast(size_t)val); + auto addr = cast(size_t) val; + return addr ^ (addr >>> 4); } -//struct or union hash -size_t hashOf(T)(auto ref T val, size_t seed = 0) if (!is(T == enum) && (is(T == struct) || is(T == union))) +//Pointers hash. CTFE unsupported if not null +@trusted @nogc nothrow pure +size_t hashOf(T)(scope const T val, size_t seed) +if (!is(T == enum) && is(T V : V*) && !is(T : typeof(null)) + && !is(T == struct) && !is(T == class) && !is(T == union)) { - static if (is(typeof(val.toHash()) == size_t)) //CTFE depends on toHash() + if (__ctfe) + { + if (val is null) + { + return hashOf(cast(size_t)0, seed); + } + else + { + assert(0, "Unable to calculate hash of non-null pointer at compile time"); + } + + } + return hashOf(cast(size_t)val, seed); +} + +private enum _hashOfStruct = +q{ + enum bool isChained = is(typeof(seed) : size_t); + static if (!isChained) enum size_t seed = 0; + static if (hasCallableToHash!T) //CTFE depends on toHash() { - return hashOf(val.toHash(), seed); + static if (isChained) + return hashOf(cast(size_t) val.toHash(), seed); + else + return val.toHash(); } else { @@ -126,39 +489,171 @@ size_t hashOf(T)(auto ref T val, size_t seed = 0) if (!is(T == enum) && (is(T == pragma(msg, "Warning: struct "~__traits(identifier, T)~" has method toHash, however it cannot be called with "~T.stringof~" this."); } - static if (is(typeof(toUbyte(val)) == const(ubyte)[]))//CTFE ready for structs without reference fields + static if (T.tupleof.length == 0) + { + return seed; + } + else static if ((is(T == struct) && !canBitwiseHash!T) || T.tupleof.length == 1) { - auto bytes = toUbyte(val); - return bytesHash(bytes.ptr, bytes.length, seed); + size_t h = void; + static if (isChained) h = seed; + foreach (i, F; typeof(val.tupleof)) + { + static if (__traits(isStaticArray, F)) + { + static if (i == 0 && !isChained) h = 0; + static if (F.sizeof > 0 && canBitwiseHash!F) + // May use smallBytesHash instead of bytesHash. + h = bytesHashWithExactSizeAndAlignment!F(toUbyte(val.tupleof[i]), h); + else + // We can avoid the "double hashing" the top-level version uses + // for consistency with TypeInfo.getHash. + foreach (ref e; val.tupleof[i]) + h = hashOf(e, h); + } + else static if (is(F == struct) || is(F == union)) + { + static if (hasCallableToHash!F) + { + static if (i == 0 && !isChained) + h = val.tupleof[i].toHash(); + else + h = hashOf(cast(size_t) val.tupleof[i].toHash(), h); + } + else static if (F.tupleof.length == 1) + { + // Handle the single member case separately to avoid unnecessarily using bytesHash. + static if (i == 0 && !isChained) + h = hashOf(val.tupleof[i].tupleof[0]); + else + h = hashOf(val.tupleof[i].tupleof[0], h); + } + else static if (canBitwiseHash!F) + { + // May use smallBytesHash instead of bytesHash. + static if (i == 0 && !isChained) h = 0; + h = bytesHashWithExactSizeAndAlignment!F(toUbyte(val.tupleof[i]), h); + } + else + { + // Nothing special happening. + static if (i == 0 && !isChained) + h = hashOf(val.tupleof[i]); + else + h = hashOf(val.tupleof[i], h); + } + } + else + { + // Nothing special happening. + static if (i == 0 && !isChained) + h = hashOf(val.tupleof[i]); + else + h = hashOf(val.tupleof[i], h); + } + } + return h; } - else // CTFE unsupproreted for structs with reference fields + else static if (is(typeof(toUbyte(val)) == const(ubyte)[]))//CTFE ready for structs without reference fields { - assert(!__ctfe, "unable to compute hash of "~T.stringof); - const(ubyte)[] bytes = (cast(const(ubyte)*)&val)[0 .. T.sizeof]; - return bytesHash(bytes.ptr, bytes.length, seed); + // Not using bytesHashWithExactSizeAndAlignment here because + // the result may differ from typeid(T).hashOf(&val). + return bytesHashAlignedBy!T(toUbyte(val), seed); + } + else // CTFE unsupported + { + assert(!__ctfe, "unable to compute hash of "~T.stringof~" at compile time"); + const(ubyte)[] bytes = (() @trusted => (cast(const(ubyte)*)&val)[0 .. T.sizeof])(); + // Not using bytesHashWithExactSizeAndAlignment here because + // the result may differ from typeid(T).hashOf(&val). + return bytesHashAlignedBy!T(bytes, seed); } } +}; + +//struct or union hash +size_t hashOf(T)(scope const auto ref T val, size_t seed = 0) +if (!is(T == enum) && (is(T == struct) || is(T == union)) + && canBitwiseHash!T) +{ + mixin(_hashOfStruct); +} + +//struct or union hash +size_t hashOf(T)(auto ref T val) +if (!is(T == enum) && (is(T == struct) || is(T == union)) + && !canBitwiseHash!T) +{ + mixin(_hashOfStruct); +} + +//struct or union hash +size_t hashOf(T)(auto ref T val, size_t seed) +if (!is(T == enum) && (is(T == struct) || is(T == union)) + && !canBitwiseHash!T) +{ + mixin(_hashOfStruct); } //delegate hash. CTFE unsupported -@trusted nothrow pure -size_t hashOf(T)(auto ref T val, size_t seed = 0) if (!is(T == enum) && is(T == delegate)) +@trusted @nogc nothrow pure +size_t hashOf(T)(scope const T val, size_t seed = 0) if (!is(T == enum) && is(T == delegate)) { - assert(!__ctfe, "unable to compute hash of "~T.stringof); + assert(!__ctfe, "unable to compute hash of "~T.stringof~" at compile time"); const(ubyte)[] bytes = (cast(const(ubyte)*)&val)[0 .. T.sizeof]; - return bytesHash(bytes.ptr, bytes.length, seed); + return bytesHashWithExactSizeAndAlignment!T(bytes, seed); +} + +//address-based class hash. CTFE only if null. +@nogc nothrow pure @trusted +size_t hashOf(T)(scope const T val) +if (!is(T == enum) && (is(T == interface) || is(T == class)) + && canBitwiseHash!T) +{ + if (__ctfe) if (val is null) return 0; + return hashOf(cast(const void*) val); +} + +//address-based class hash. CTFE only if null. +@nogc nothrow pure @trusted +size_t hashOf(T)(scope const T val, size_t seed) +if (!is(T == enum) && (is(T == interface) || is(T == class)) + && canBitwiseHash!T) +{ + if (__ctfe) if (val is null) return hashOf(size_t(0), seed); + return hashOf(cast(const void*) val, seed); } //class or interface hash. CTFE depends on toHash -size_t hashOf(T)(auto ref T val, size_t seed = 0) if (!is(T == enum) && is(T == interface) || is(T == class)) +size_t hashOf(T)(T val) +if (!is(T == enum) && (is(T == interface) || is(T == class)) + && !canBitwiseHash!T) { - return hashOf(val ? (cast(Object)val).toHash() : 0, seed); + static if (__traits(compiles, {size_t h = val.toHash();})) + return val ? val.toHash() : 0; + else + return val ? (cast(Object)val).toHash() : 0; +} + +//class or interface hash. CTFE depends on toHash +size_t hashOf(T)(T val, size_t seed) +if (!is(T == enum) && (is(T == interface) || is(T == class)) + && !canBitwiseHash!T) +{ + static if (__traits(compiles, {size_t h = val.toHash();})) + return hashOf(val ? cast(size_t) val.toHash() : size_t(0), seed); + else + return hashOf(val ? (cast(Object)val).toHash() : 0, seed); } //associative array hash. CTFE depends on base types -size_t hashOf(T)(auto ref T aa, size_t seed = 0) if (!is(T == enum) && __traits(isAssociativeArray, T)) +size_t hashOf(T)(T aa) if (!is(T == enum) && __traits(isAssociativeArray, T)) { - if (!aa.length) return hashOf(0, seed); + static if (is(typeof(aa) : V[K], K, V)) {} // Put K & V in scope. + static if (__traits(compiles, (ref K k, ref V v) nothrow => .hashOf(k) + .hashOf(v))) + scope (failure) assert(0); // Allow compiler to infer nothrow. + + if (!aa.length) return 0; size_t h = 0; // The computed hash is independent of the foreach traversal order. @@ -167,315 +662,81 @@ size_t hashOf(T)(auto ref T aa, size_t seed = 0) if (!is(T == enum) && __traits( size_t[2] hpair; hpair[0] = key.hashOf(); hpair[1] = val.hashOf(); - h ^= hpair.hashOf(); + h += hpair.hashOf(); } - return h.hashOf(seed); + return h; } -unittest +//associative array hash. CTFE depends on base types +size_t hashOf(T)(T aa, size_t seed) if (!is(T == enum) && __traits(isAssociativeArray, T)) { - static struct Foo - { - int a = 99; - float b = 4.0; - size_t toHash() const pure @safe nothrow - { - return a; - } - } - - static struct Bar - { - char c = 'x'; - int a = 99; - float b = 4.0; - void* d = null; - } - - static struct Boom - { - char c = 'M'; - int* a = null; - } - - interface IBoo - { - void boo(); - } - - static class Boo: IBoo - { - override void boo() - { - } - - override size_t toHash() - { - return 1; - } - } - - static struct Goo - { - size_t toHash() pure @safe nothrow - { - return 1; - } - } - - enum Gun: long - { - A = 99, - B = 17 - } - - enum double dexpr = 3.14; - enum float fexpr = 2.71; - enum wstring wsexpr = "abcdef"w; - enum string csexpr = "abcdef"; - enum int iexpr = 7; - enum long lexpr = 42; - enum int[2][3] saexpr = [[1, 2], [3, 4], [5, 6]]; - enum int[] daexpr = [7,8,9]; - enum Foo thsexpr = Foo(); - enum Bar vsexpr = Bar(); - enum int[int] aaexpr = [99:2, 12:6, 45:4]; - enum Gun eexpr = Gun.A; - enum cdouble cexpr = 7+4i; - enum Foo[] staexpr = [Foo(), Foo(), Foo()]; - enum Bar[] vsaexpr = [Bar(), Bar(), Bar()]; - enum realexpr = 7.88; - enum raexpr = [8.99L+86i, 3.12L+99i, 5.66L+12i]; - enum nullexpr = null; - - //No CTFE: - Boom rstructexpr = Boom(); - Boom[] rstrarrexpr = [Boom(), Boom(), Boom()]; - int delegate() dgexpr = (){return 78;}; - void* ptrexpr = &dgexpr; - - - //CTFE hashes - enum h1 = dexpr.hashOf(); - enum h2 = fexpr.hashOf(); - enum h3 = wsexpr.hashOf(); - enum h4 = csexpr.hashOf(); - enum h5 = iexpr.hashOf(); - enum h6 = lexpr.hashOf(); - enum h7 = saexpr.hashOf(); - enum h8 = daexpr.hashOf(); - enum h9 = thsexpr.hashOf(); - enum h10 = vsexpr.hashOf(); - enum h11 = aaexpr.hashOf(); - enum h12 = eexpr.hashOf(); - enum h13 = cexpr.hashOf(); - enum h14 = hashOf(new Boo); - enum h15 = staexpr.hashOf(); - enum h16 = hashOf([new Boo, new Boo, new Boo]); - enum h17 = hashOf([cast(IBoo)new Boo, cast(IBoo)new Boo, cast(IBoo)new Boo]); - enum h18 = hashOf(cast(IBoo)new Boo); - enum h19 = vsaexpr.hashOf(); - enum h20 = hashOf(cast(Foo[3])staexpr); - - //BUG: cannot cast [Boo(), Boo(), Boo()][0] to object.Object at compile time - auto h21 = hashOf(cast(Boo[3])[new Boo, new Boo, new Boo]); - auto h22 = hashOf(cast(IBoo[3])[cast(IBoo)new Boo, cast(IBoo)new Boo, cast(IBoo)new Boo]); - enum h23 = hashOf(cast(Bar[3])vsaexpr); - - //NO CTFE (Compute, but don't check correctness): - auto h24 = rstructexpr.hashOf(); - auto h25 = rstrarrexpr.hashOf(); - auto h26 = dgexpr.hashOf(); - auto h27 = ptrexpr.hashOf(); - - enum h28 = realexpr.hashOf(); - enum h29 = raexpr.hashOf(); - enum h30 = nullexpr.hashOf(); - - auto v1 = dexpr; - auto v2 = fexpr; - auto v3 = wsexpr; - auto v4 = csexpr; - auto v5 = iexpr; - auto v6 = lexpr; - auto v7 = saexpr; - auto v8 = daexpr; - auto v9 = thsexpr; - auto v10 = vsexpr; - auto v11 = aaexpr; - auto v12 = eexpr; - auto v13 = cexpr; - auto v14 = new Boo; - auto v15 = staexpr; - auto v16 = [new Boo, new Boo, new Boo]; - auto v17 = [cast(IBoo)new Boo, cast(IBoo)new Boo, cast(IBoo)new Boo]; - auto v18 = cast(IBoo)new Boo; - auto v19 = vsaexpr; - auto v20 = cast(Foo[3])staexpr; - auto v21 = cast(Boo[3])[new Boo, new Boo, new Boo]; - auto v22 = cast(IBoo[3])[cast(IBoo)new Boo, cast(IBoo)new Boo, cast(IBoo)new Boo]; - auto v23 = cast(Bar[3])vsaexpr; - auto v30 = null; - - //NO CTFE: - /*auto v24 = rstructexpr; - auto v25 = rstrarrexpr; - auto v26 = dgexpr; - auto v27 = ptrexpr; - auto v28 = realexpr; - auto v29 = raexpr;*/ - - //runtime hashes - auto rth1 = hashOf(v1); - auto rth2 = hashOf(v2); - auto rth3 = hashOf(v3); - auto rth4 = hashOf(v4); - auto rth5 = hashOf(v5); - auto rth6 = hashOf(v6); - auto rth7 = hashOf(v7); - auto rth8 = hashOf(v8); - auto rth9 = hashOf(v9); - auto rth10 = hashOf(v10); - auto rth11 = hashOf(v11); - auto rth12 = hashOf(v12); - auto rth13 = hashOf(v13); - auto rth14 = hashOf(v14); - auto rth15 = hashOf(v15); - auto rth16 = hashOf(v16); - auto rth17 = hashOf(v17); - auto rth18 = hashOf(v18); - auto rth19 = hashOf(v19); - auto rth20 = hashOf(v20); - auto rth21 = hashOf(v21); - auto rth22 = hashOf(v22); - auto rth23 = hashOf(v23); - auto rth30 = hashOf(v30); - /*//NO CTFE: - auto rth24 = hashOf(v24); - auto rth25 = hashOf(v25); - auto rth26 = hashOf(v26); - auto rth27 = hashOf(v27); - auto rth28 = hashOf(v28); - auto rth29 = hashOf(v29);*/ - - assert(h1 == rth1); - assert(h2 == rth2); - assert(h3 == rth3); - assert(h4 == rth4); - assert(h5 == rth5); - assert(h6 == rth6); - assert(h7 == rth7); - assert(h8 == rth8); - assert(h9 == rth9); - assert(h10 == rth10); - assert(h11 == rth11); - assert(h12 == rth12); - assert(h13 == rth13); - assert(h14 == rth14); - assert(h15 == rth15); - assert(h16 == rth16); - assert(h17 == rth17); - assert(h18 == rth18); - assert(h19 == rth19); - assert(h20 == rth20); - assert(h21 == rth21); - assert(h22 == rth22); - assert(h23 == rth23); - /*assert(h24 == rth24); - assert(h25 == rth25); - assert(h26 == rth26); - assert(h27 == rth27); - assert(h28 == rth28); - assert(h29 == rth29);*/ - assert(h30 == rth30); -} - - -unittest // issue 15111 -{ - void testAlias(T)() - { - static struct Foo - { - T t; - alias t this; - } - Foo foo; - static assert(is(typeof(hashOf(foo)))); - } - // was fixed - testAlias!(int[]); - testAlias!(int*); - // was not affected - testAlias!int; - testAlias!(void delegate()); - testAlias!(string[string]); - testAlias!(int[8]); + return hashOf(hashOf(aa), seed); } // MurmurHash3 was written by Austin Appleby, and is placed in the public // domain. The author hereby disclaims copyright to this source code. -version (X86) - version = AnyX86; -version (X86_64) - version = AnyX86; +// This overload is for backwards compatibility. +@system pure nothrow @nogc +size_t bytesHash()(scope const(void)* buf, size_t len, size_t seed) +{ + return bytesHashAlignedBy!ubyte((cast(const(ubyte)*) buf)[0 .. len], seed); +} -version (AnyX86) +private template bytesHashAlignedBy(AlignType) { - version (DigitalMars) - { - } - else - { - version = HasUnalignedOps; - } + alias bytesHashAlignedBy = bytesHash!(AlignType.alignof >= uint.alignof); } +private template bytesHashWithExactSizeAndAlignment(SizeAndAlignType) +{ + static if (SizeAndAlignType.alignof < uint.alignof + ? SizeAndAlignType.sizeof <= 12 + : SizeAndAlignType.sizeof <= 10) + alias bytesHashWithExactSizeAndAlignment = smallBytesHash; + else + alias bytesHashWithExactSizeAndAlignment = bytesHashAlignedBy!SizeAndAlignType; +} -@system pure nothrow @nogc -size_t bytesHash(const(void)* buf, size_t len, size_t seed) +// Fowler/Noll/Vo hash. http://www.isthe.com/chongo/tech/comp/fnv/ +private size_t fnv()(scope const(ubyte)[] bytes, size_t seed) @nogc nothrow pure @safe { - static uint rotl32(uint n)(in uint x) pure nothrow @safe @nogc - { - return (x << n) | (x >> (32 - n)); - } + static if (size_t.max <= uint.max) + enum prime = (1U << 24) + (1U << 8) + 0x93U; + else static if (size_t.max <= ulong.max) + enum prime = (1UL << 40) + (1UL << 8) + 0xb3UL; + else + enum prime = (size_t(1) << 88) + (size_t(1) << 8) + size_t(0x3b); + foreach (b; bytes) + seed = (seed ^ b) * prime; + return seed; +} +private alias smallBytesHash = fnv; - //----------------------------------------------------------------------------- - // Block read - if your platform needs to do endian-swapping or can only - // handle aligned reads, do the conversion here - static uint get32bits(const (ubyte)* x) pure nothrow @nogc +//----------------------------------------------------------------------------- +// Block read - if your platform needs to do endian-swapping or can only +// handle aligned reads, do the conversion here +private uint get32bits()(scope const(ubyte)* x) @nogc nothrow pure @system +{ + version (BigEndian) { - //Compiler can optimize this code to simple *cast(uint*)x if it possible. - version (HasUnalignedOps) - { - if (!__ctfe) - return *cast(uint*)x; //BUG: Can't be inlined by DMD - } - version (BigEndian) - { - return ((cast(uint) x[0]) << 24) | ((cast(uint) x[1]) << 16) | ((cast(uint) x[2]) << 8) | (cast(uint) x[3]); - } - else - { - return ((cast(uint) x[3]) << 24) | ((cast(uint) x[2]) << 16) | ((cast(uint) x[1]) << 8) | (cast(uint) x[0]); - } + return ((cast(uint) x[0]) << 24) | ((cast(uint) x[1]) << 16) | ((cast(uint) x[2]) << 8) | (cast(uint) x[3]); } - - //----------------------------------------------------------------------------- - // Finalization mix - force all bits of a hash block to avalanche - static uint fmix32(uint h) pure nothrow @safe @nogc + else { - h ^= h >> 16; - h *= 0x85ebca6b; - h ^= h >> 13; - h *= 0xc2b2ae35; - h ^= h >> 16; - - return h; + return ((cast(uint) x[3]) << 24) | ((cast(uint) x[2]) << 16) | ((cast(uint) x[1]) << 8) | (cast(uint) x[0]); } +} - auto data = cast(const(ubyte)*)buf; +/+ +Params: + dataKnownToBeAligned = whether the data is known at compile time to be uint-aligned. ++/ +@nogc nothrow pure @trusted +private size_t bytesHash(bool dataKnownToBeAligned)(scope const(ubyte)[] bytes, size_t seed) +{ + auto len = bytes.length; + auto data = bytes.ptr; auto nblocks = len / 4; uint h1 = cast(uint)seed; @@ -489,13 +750,16 @@ size_t bytesHash(const(void)* buf, size_t len, size_t seed) auto end_data = data+nblocks*uint.sizeof; for (; data!=end_data; data += uint.sizeof) { - uint k1 = get32bits(data); + static if (dataKnownToBeAligned) + uint k1 = __ctfe ? get32bits(data) : *(cast(const uint*) data); + else + uint k1 = get32bits(data); k1 *= c1; - k1 = rotl32!15(k1); + k1 = (k1 << 15) | (k1 >> (32 - 15)); k1 *= c2; h1 ^= k1; - h1 = rotl32!13(h1); + h1 = (h1 << 13) | (h1 >> (32 - 13)); h1 = h1*5+c3; } @@ -508,7 +772,7 @@ size_t bytesHash(const(void)* buf, size_t len, size_t seed) case 3: k1 ^= data[2] << 16; goto case; case 2: k1 ^= data[1] << 8; goto case; case 1: k1 ^= data[0]; - k1 *= c1; k1 = rotl32!15(k1); k1 *= c2; h1 ^= k1; + k1 *= c1; k1 = (k1 << 15) | (k1 >> (32 - 15)); k1 *= c2; h1 ^= k1; goto default; default: } @@ -516,7 +780,10 @@ size_t bytesHash(const(void)* buf, size_t len, size_t seed) //---------- // finalization h1 ^= len; - h1 = fmix32(h1); + // Force all bits of the hash block to avalanche. + h1 = (h1 ^ (h1 >> 16)) * 0x85ebca6b; + h1 = (h1 ^ (h1 >> 13)) * 0xc2b2ae35; + h1 ^= h1 >> 16; return h1; } @@ -531,4 +798,21 @@ pure nothrow @system @nogc unittest enum test_str = "Sample string"; enum size_t hashVal = ctfeHash(test_str); assert(hashVal == bytesHash(&test_str[0], test_str.length, 0)); + + // Detect unintended changes to bytesHash on unaligned and aligned inputs. + version (BigEndian) + { + const ubyte[7] a = [99, 4, 3, 2, 1, 5, 88]; + const uint[2] b = [0x04_03_02_01, 0x05_ff_ff_ff]; + } + else + { + const ubyte[7] a = [99, 1, 2, 3, 4, 5, 88]; + const uint[2] b = [0x04_03_02_01, 0xff_ff_ff_05]; + } + // It is okay to change the below values if you make a change + // that you expect to change the result of bytesHash. + assert(bytesHash(&a[1], a.length - 2, 0) == 2727459272); + assert(bytesHash(&b, 5, 0) == 2727459272); + assert(bytesHashAlignedBy!uint((cast(const ubyte*) &b)[0 .. 5], 0) == 2727459272); } diff --git a/libphobos/libdruntime/core/internal/traits.d b/libphobos/libdruntime/core/internal/traits.d index a8c734005ff..d5786808054 100644 --- a/libphobos/libdruntime/core/internal/traits.d +++ b/libphobos/libdruntime/core/internal/traits.d @@ -128,6 +128,30 @@ template dtorIsNothrow(T) enum dtorIsNothrow = is(typeof(function{T t=void;}) : void function() nothrow); } +/* +Tests whether all given items satisfy a template predicate, i.e. evaluates to +$(D F!(T[0]) && F!(T[1]) && ... && F!(T[$ - 1])). +*/ +package(core.internal) +template allSatisfy(alias F, T...) +{ + static if (T.length == 0) + { + enum allSatisfy = true; + } + else static if (T.length == 1) + { + enum allSatisfy = F!(T[0]); + } + else + { + static if (allSatisfy!(F, T[0 .. $/2])) + enum allSatisfy = allSatisfy!(F, T[$/2 .. $]); + else + enum allSatisfy = false; + } +} + template anySatisfy(alias F, T...) { static if (T.length == 0) diff --git a/libphobos/libdruntime/object.d b/libphobos/libdruntime/object.d index 2fe27a195df..38bd0ae1f6b 100644 --- a/libphobos/libdruntime/object.d +++ b/libphobos/libdruntime/object.d @@ -63,7 +63,15 @@ class Object size_t toHash() @trusted nothrow { // BUG: this prevents a compacting GC from working, needs to be fixed - return cast(size_t)cast(void*)this; + size_t addr = cast(size_t) cast(void*) this; + // The bottom log2((void*).alignof) bits of the address will always + // be 0. Moreover it is likely that each Object is allocated with a + // separate call to malloc. The alignment of malloc differs from + // platform to platform, but rather than having special cases for + // each platform it is safe to use a shift of 4. To minimize + // collisions in the low bits it is more important for the shift to + // not be too small than for the shift to not be too big. + return addr ^ (addr >>> 4); } /** @@ -209,10 +217,7 @@ class TypeInfo override size_t toHash() @trusted const nothrow { - import core.internal.traits : externDFunc; - alias hashOf = externDFunc!("rt.util.hash.hashOf", - size_t function(const(void)[], size_t) @trusted pure nothrow @nogc); - return hashOf(this.toString(), 0); + return hashOf(this.toString()); } override int opCmp(Object o) @@ -250,7 +255,10 @@ class TypeInfo * Bugs: * fix https://issues.dlang.org/show_bug.cgi?id=12516 e.g. by changing this to a truly safe interface. */ - size_t getHash(in void* p) @trusted nothrow const { return cast(size_t)p; } + size_t getHash(scope const void* p) @trusted nothrow const + { + return hashOf(p); + } /// Compares two instances for equality. bool equals(in void* p1, in void* p2) const { return p1 == p2; } @@ -327,7 +335,7 @@ class TypeInfo_Enum : TypeInfo this.base == c.base; } - override size_t getHash(in void* p) const { return base.getHash(p); } + override size_t getHash(scope const void* p) const { return base.getHash(p); } override bool equals(in void* p1, in void* p2) const { return base.equals(p1, p2); } override int compare(in void* p1, in void* p2) const { return base.compare(p1, p2); } override @property size_t tsize() nothrow pure const { return base.tsize; } @@ -375,9 +383,10 @@ class TypeInfo_Pointer : TypeInfo return c && this.m_next == c.m_next; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { - return cast(size_t)*cast(void**)p; + size_t addr = cast(size_t) *cast(const void**)p; + return addr ^ (addr >> 4); } override bool equals(in void* p1, in void* p2) const @@ -430,7 +439,7 @@ class TypeInfo_Array : TypeInfo return c && this.value == c.value; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { void[] a = *cast(void[]*)p; return getArrayHash(value, a.ptr, a.length); @@ -529,7 +538,7 @@ class TypeInfo_StaticArray : TypeInfo this.value == c.value; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { return getArrayHash(value, p, len); } @@ -655,7 +664,7 @@ class TypeInfo_AssociativeArray : TypeInfo return !!_aaEqual(this, *cast(const void**) p1, *cast(const void**) p2); } - override hash_t getHash(in void* p) nothrow @trusted const + override hash_t getHash(scope const void* p) nothrow @trusted const { return _aaGetHash(cast(void*)p, this); } @@ -702,7 +711,7 @@ class TypeInfo_Vector : TypeInfo return c && this.base == c.base; } - override size_t getHash(in void* p) const { return base.getHash(p); } + override size_t getHash(scope const void* p) const { return base.getHash(p); } override bool equals(in void* p1, in void* p2) const { return base.equals(p1, p2); } override int compare(in void* p1, in void* p2) const { return base.compare(p1, p2); } override @property size_t tsize() nothrow pure const { return base.tsize; } @@ -796,7 +805,7 @@ class TypeInfo_Delegate : TypeInfo return c && this.deco == c.deco; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { return hashOf(*cast(void delegate()*)p); } @@ -851,34 +860,6 @@ class TypeInfo_Delegate : TypeInfo } } -unittest -{ - // Bugzilla 15367 - void f1() {} - void f2() {} - - // TypeInfo_Delegate.getHash - int[void delegate()] aa; - assert(aa.length == 0); - aa[&f1] = 1; - assert(aa.length == 1); - aa[&f1] = 1; - assert(aa.length == 1); - - auto a1 = [&f2, &f1]; - auto a2 = [&f2, &f1]; - - // TypeInfo_Delegate.equals - for (auto i = 0; i < 2; i++) - assert(a1[i] == a2[i]); - assert(a1 == a2); - - // TypeInfo_Delegate.compare - for (auto i = 0; i < 2; i++) - assert(a1[i] <= a2[i]); - assert(a1 <= a2); -} - /** * Runtime type information about a class. * Can be retrieved from an object instance by using the @@ -896,7 +877,7 @@ class TypeInfo_Class : TypeInfo return c && this.info.name == c.info.name; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { auto o = *cast(Object*)p; return o ? o.toHash() : 0; @@ -1051,8 +1032,12 @@ class TypeInfo_Interface : TypeInfo return c && this.info.name == typeid(c).name; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { + if (!*cast(void**)p) + { + return 0; + } Interface* pi = **cast(Interface ***)*cast(void**)p; Object o = cast(Object)(*cast(void**)p - pi.offset); assert(o); @@ -1121,7 +1106,7 @@ class TypeInfo_Struct : TypeInfo this.initializer().length == s.initializer().length; } - override size_t getHash(in void* p) @trusted pure nothrow const + override size_t getHash(scope const void* p) @trusted pure nothrow const { assert(p); if (xtoHash) @@ -1130,10 +1115,7 @@ class TypeInfo_Struct : TypeInfo } else { - import core.internal.traits : externDFunc; - alias hashOf = externDFunc!("rt.util.hash.hashOf", - size_t function(const(void)[], size_t) @trusted pure nothrow @nogc); - return hashOf(p[0 .. initializer().length], 0); + return hashOf(p[0 .. initializer().length]); } } @@ -1310,7 +1292,7 @@ class TypeInfo_Tuple : TypeInfo return false; } - override size_t getHash(in void* p) const + override size_t getHash(scope const void* p) const { assert(0); } @@ -1381,7 +1363,7 @@ class TypeInfo_Const : TypeInfo return base.opEquals(t.base); } - override size_t getHash(in void *p) const { return base.getHash(p); } + override size_t getHash(scope const void *p) const { return base.getHash(p); } override bool equals(in void *p1, in void *p2) const { return base.equals(p1, p2); } override int compare(in void *p1, in void *p2) const { return base.compare(p1, p2); } override @property size_t tsize() nothrow pure const { return base.tsize; } @@ -1882,6 +1864,7 @@ extern (C) // size_t _aaLen(in void* p) pure nothrow @nogc; private void* _aaGetY(void** paa, const TypeInfo_AssociativeArray ti, in size_t valuesize, in void* pkey) pure nothrow; + private void* _aaGetX(void** paa, const TypeInfo_AssociativeArray ti, in size_t valuesize, in void* pkey, out bool found) pure nothrow; // inout(void)* _aaGetRvalueX(inout void* p, in TypeInfo keyti, in size_t valuesize, in void* pkey); inout(void)[] _aaValues(inout void* p, in size_t keysize, in size_t valuesize, const TypeInfo tiValArray) pure nothrow; inout(void)[] _aaKeys(inout void* p, in size_t keysize, const TypeInfo tiKeyArray) pure nothrow; @@ -1895,11 +1878,11 @@ extern (C) // int _aaApply2(void* aa, size_t keysize, _dg2_t dg); private struct AARange { void* impl; size_t idx; } - AARange _aaRange(void* aa) pure nothrow @nogc; - bool _aaRangeEmpty(AARange r) pure nothrow @nogc; - void* _aaRangeFrontKey(AARange r) pure nothrow @nogc; - void* _aaRangeFrontValue(AARange r) pure nothrow @nogc; - void _aaRangePopFront(ref AARange r) pure nothrow @nogc; + AARange _aaRange(void* aa) pure nothrow @nogc @safe; + bool _aaRangeEmpty(AARange r) pure nothrow @nogc @safe; + void* _aaRangeFrontKey(AARange r) pure nothrow @nogc @safe; + void* _aaRangeFrontValue(AARange r) pure nothrow @nogc @safe; + void _aaRangePopFront(ref AARange r) pure nothrow @nogc @safe; int _aaEqual(in TypeInfo tiRaw, in void* e1, in void* e2); hash_t _aaGetHash(in void* aa, in TypeInfo tiRaw) nothrow; @@ -1920,40 +1903,63 @@ void* aaLiteral(Key, Value)(Key[] keys, Value[] values) @trusted pure alias AssociativeArray(Key, Value) = Value[Key]; +/*********************************** + * Removes all remaining keys and values from an associative array. + * Params: + * aa = The associative array. + */ void clear(T : Value[Key], Value, Key)(T aa) { _aaClear(*cast(void **) &aa); } +/* ditto */ void clear(T : Value[Key], Value, Key)(T* aa) { _aaClear(*cast(void **) aa); } +/*********************************** + * Reorganizes the associative array in place so that lookups are more + * efficient. + * Params: + * aa = The associative array. + * Returns: + * The rehashed associative array. + */ T rehash(T : Value[Key], Value, Key)(T aa) { _aaRehash(cast(void**)&aa, typeid(Value[Key])); return aa; } +/* ditto */ T rehash(T : Value[Key], Value, Key)(T* aa) { _aaRehash(cast(void**)aa, typeid(Value[Key])); return *aa; } +/* ditto */ T rehash(T : shared Value[Key], Value, Key)(T aa) { _aaRehash(cast(void**)&aa, typeid(Value[Key])); return aa; } +/* ditto */ T rehash(T : shared Value[Key], Value, Key)(T* aa) { _aaRehash(cast(void**)aa, typeid(Value[Key])); return *aa; } +/*********************************** + * Create a new associative array of the same size and copy the contents of the + * associative array into it. + * Params: + * aa = The associative array. + */ V[K] dup(T : V[K], K, V)(T aa) { //pragma(msg, "K = ", K, ", V = ", V); @@ -1990,12 +1996,31 @@ V[K] dup(T : V[K], K, V)(T aa) return result; } +/* ditto */ V[K] dup(T : V[K], K, V)(T* aa) { return (*aa).dup; } -auto byKey(T : V[K], K, V)(T aa) pure nothrow @nogc +// this should never be made public. +private AARange _aaToRange(T: V[K], K, V)(ref T aa) pure nothrow @nogc @safe +{ + // ensure we are dealing with a genuine AA. + static if (is(const(V[K]) == const(T))) + alias realAA = aa; + else + const(V[K]) realAA = aa; + return _aaRange(() @trusted { return cast(void*)realAA; } ()); +} + +/*********************************** + * Returns a forward range over the keys of the associative array. + * Params: + * aa = The associative array. + * Returns: + * A forward range. + */ +auto byKey(T : V[K], K, V)(T aa) pure nothrow @nogc @safe { import core.internal.traits : substInout; @@ -2004,21 +2029,33 @@ auto byKey(T : V[K], K, V)(T aa) pure nothrow @nogc AARange r; pure nothrow @nogc: - @property bool empty() { return _aaRangeEmpty(r); } - @property ref front() { return *cast(substInout!K*)_aaRangeFrontKey(r); } - void popFront() { _aaRangePopFront(r); } + @property bool empty() @safe { return _aaRangeEmpty(r); } + @property ref front() + { + auto p = (() @trusted => cast(substInout!K*) _aaRangeFrontKey(r)) (); + return *p; + } + void popFront() @safe { _aaRangePopFront(r); } @property Result save() { return this; } } - return Result(_aaRange(cast(void*)aa)); + return Result(_aaToRange(aa)); } +/* ditto */ auto byKey(T : V[K], K, V)(T* aa) pure nothrow @nogc { return (*aa).byKey(); } -auto byValue(T : V[K], K, V)(T aa) pure nothrow @nogc +/*********************************** + * Returns a forward range over the values of the associative array. + * Params: + * aa = The associative array. + * Returns: + * A forward range. + */ +auto byValue(T : V[K], K, V)(T aa) pure nothrow @nogc @safe { import core.internal.traits : substInout; @@ -2027,21 +2064,33 @@ auto byValue(T : V[K], K, V)(T aa) pure nothrow @nogc AARange r; pure nothrow @nogc: - @property bool empty() { return _aaRangeEmpty(r); } - @property ref front() { return *cast(substInout!V*)_aaRangeFrontValue(r); } - void popFront() { _aaRangePopFront(r); } + @property bool empty() @safe { return _aaRangeEmpty(r); } + @property ref front() + { + auto p = (() @trusted => cast(substInout!V*) _aaRangeFrontValue(r)) (); + return *p; + } + void popFront() @safe { _aaRangePopFront(r); } @property Result save() { return this; } } - return Result(_aaRange(cast(void*)aa)); + return Result(_aaToRange(aa)); } +/* ditto */ auto byValue(T : V[K], K, V)(T* aa) pure nothrow @nogc { return (*aa).byValue(); } -auto byKeyValue(T : V[K], K, V)(T aa) pure nothrow @nogc +/*********************************** + * Returns a forward range over the key value pairs of the associative array. + * Params: + * aa = The associative array. + * Returns: + * A forward range. + */ +auto byKeyValue(T : V[K], K, V)(T aa) pure nothrow @nogc @safe { import core.internal.traits : substInout; @@ -2050,8 +2099,8 @@ auto byKeyValue(T : V[K], K, V)(T aa) pure nothrow @nogc AARange r; pure nothrow @nogc: - @property bool empty() { return _aaRangeEmpty(r); } - @property auto front() @trusted + @property bool empty() @safe { return _aaRangeEmpty(r); } + @property auto front() { static struct Pair { @@ -2060,24 +2109,41 @@ auto byKeyValue(T : V[K], K, V)(T aa) pure nothrow @nogc private void* keyp; private void* valp; - @property ref key() inout { return *cast(substInout!K*)keyp; } - @property ref value() inout { return *cast(substInout!V*)valp; } + @property ref key() inout + { + auto p = (() @trusted => cast(substInout!K*) keyp) (); + return *p; + } + @property ref value() inout + { + auto p = (() @trusted => cast(substInout!V*) valp) (); + return *p; + } } return Pair(_aaRangeFrontKey(r), _aaRangeFrontValue(r)); } - void popFront() { _aaRangePopFront(r); } + void popFront() @safe { return _aaRangePopFront(r); } @property Result save() { return this; } } - return Result(_aaRange(cast(void*)aa)); + return Result(_aaToRange(aa)); } +/* ditto */ auto byKeyValue(T : V[K], K, V)(T* aa) pure nothrow @nogc { return (*aa).byKeyValue(); } +/*********************************** + * Returns a dynamic array, the elements of which are the keys in the + * associative array. + * Params: + * aa = The associative array. + * Returns: + * A dynamic array. + */ Key[] keys(T : Value[Key], Value, Key)(T aa) @property { auto a = cast(void[])_aaKeys(cast(inout(void)*)aa, Key.sizeof, typeid(Key[])); @@ -2086,11 +2152,20 @@ Key[] keys(T : Value[Key], Value, Key)(T aa) @property return res; } +/* ditto */ Key[] keys(T : Value[Key], Value, Key)(T *aa) @property { return (*aa).keys; } +/*********************************** + * Returns a dynamic array, the elements of which are the values in the + * associative array. + * Params: + * aa = The associative array. + * Returns: + * A dynamic array. + */ Value[] values(T : Value[Key], Value, Key)(T aa) @property { auto a = cast(void[])_aaValues(cast(inout(void)*)aa, Key.sizeof, Value.sizeof, typeid(Value[])); @@ -2099,341 +2174,149 @@ Value[] values(T : Value[Key], Value, Key)(T aa) @property return res; } +/* ditto */ Value[] values(T : Value[Key], Value, Key)(T *aa) @property { return (*aa).values; } -unittest -{ - static struct T - { - static size_t count; - this(this) { ++count; } - } - T[int] aa; - T t; - aa[0] = t; - aa[1] = t; - assert(T.count == 2); - auto vals = aa.values; - assert(vals.length == 2); - assert(T.count == 4); - - T.count = 0; - int[T] aa2; - aa2[t] = 0; - assert(T.count == 1); - aa2[t] = 1; - assert(T.count == 1); - auto keys = aa2.keys; - assert(keys.length == 1); - assert(T.count == 2); -} - +/*********************************** + * Looks up key; if it exists returns corresponding value else evaluates and + * returns defaultValue. + * Params: + * aa = The associative array. + * key = The key. + * defaultValue = The default value. + * Returns: + * The value. + */ inout(V) get(K, V)(inout(V[K]) aa, K key, lazy inout(V) defaultValue) { auto p = key in aa; return p ? *p : defaultValue; } +/* ditto */ inout(V) get(K, V)(inout(V[K])* aa, K key, lazy inout(V) defaultValue) { return (*aa).get(key, defaultValue); } -pure nothrow unittest +/*********************************** + * Looks up key; if it exists returns corresponding value else evaluates + * value, adds it to the associative array and returns it. + * Params: + * aa = The associative array. + * key = The key. + * value = The required value. + * Returns: + * The value. + */ +ref V require(K, V)(ref V[K] aa, K key, lazy V value = V.init) { - int[int] a; - foreach (i; a.byKey) + bool found; + // if key is @safe-ly copyable, `require` can infer @safe + static if (isSafeCopyable!K) { - assert(false); + auto p = () @trusted + { + return cast(V*) _aaGetX(cast(void**) &aa, typeid(V[K]), V.sizeof, &key, found); + } (); } - foreach (i; a.byValue) + else { - assert(false); + auto p = cast(V*) _aaGetX(cast(void**) &aa, typeid(V[K]), V.sizeof, &key, found); } + return found ? *p : (*p = value); } -pure /*nothrow */ unittest +// Constraints for aa update. Delegates, Functions or Functors (classes that +// provide opCall) are allowed. See unittest for an example. +private { - auto a = [ 1:"one", 2:"two", 3:"three" ]; - auto b = a.dup; - assert(b == [ 1:"one", 2:"two", 3:"three" ]); - - int[] c; - foreach (k; a.byKey) + template isCreateOperation(C, V) { - c ~= k; - } - - assert(c.length == 3); - assert(c[0] == 1 || c[1] == 1 || c[2] == 1); - assert(c[0] == 2 || c[1] == 2 || c[2] == 2); - assert(c[0] == 3 || c[1] == 3 || c[2] == 3); -} - -pure nothrow unittest -{ - // test for bug 5925 - const a = [4:0]; - const b = [4:0]; - assert(a == b); -} - -pure nothrow unittest -{ - // test for bug 9052 - static struct Json { - Json[string] aa; - void opAssign(Json) {} - size_t length() const { return aa.length; } - // This length() instantiates AssociativeArray!(string, const(Json)) to call AA.length(), and - // inside ref Slot opAssign(Slot p); (which is automatically generated by compiler in Slot), - // this.value = p.value would actually fail, because both side types of the assignment - // are const(Json). + static if (is(C : V delegate()) || is(C : V function())) + enum bool isCreateOperation = true; + else static if (isCreateOperation!(typeof(&C.opCall), V)) + enum bool isCreateOperation = true; + else + enum bool isCreateOperation = false; } -} - -pure nothrow unittest -{ - // test for bug 8583: ensure Slot and aaA are on the same page wrt value alignment - string[byte] aa0 = [0: "zero"]; - string[uint[3]] aa1 = [[1,2,3]: "onetwothree"]; - ushort[uint[3]] aa2 = [[9,8,7]: 987]; - ushort[uint[4]] aa3 = [[1,2,3,4]: 1234]; - string[uint[5]] aa4 = [[1,2,3,4,5]: "onetwothreefourfive"]; - - assert(aa0.byValue.front == "zero"); - assert(aa1.byValue.front == "onetwothree"); - assert(aa2.byValue.front == 987); - assert(aa3.byValue.front == 1234); - assert(aa4.byValue.front == "onetwothreefourfive"); -} -pure nothrow unittest -{ - // test for bug 10720 - static struct NC + template isUpdateOperation(U, V) { - @disable this(this) { } + static if (is(U : V delegate(ref V)) || is(U : V function(ref V))) + enum bool isUpdateOperation = true; + else static if (isUpdateOperation!(typeof(&U.opCall), V)) + enum bool isUpdateOperation = true; + else + enum bool isUpdateOperation = false; } - - NC[string] aa; - static assert(!is(aa.nonExistingField)); } -pure nothrow unittest -{ - // bug 5842 - string[string] test = null; - test["test1"] = "test1"; - test.remove("test1"); - test.rehash; - test["test3"] = "test3"; // causes divide by zero if rehash broke the AA -} +// Tests whether T can be @safe-ly copied. Use a union to exclude destructor from the test. +private enum bool isSafeCopyable(T) = is(typeof(() @safe { union U { T x; } T *x; auto u = U(*x); })); -pure nothrow unittest +/*********************************** + * Looks up key; if it exists applies the update delegate else evaluates the + * create delegate and adds it to the associative array + * Params: + * aa = The associative array. + * key = The key. + * create = The delegate to apply on create. + * update = The delegate to apply on update. + */ +void update(K, V, C, U)(ref V[K] aa, K key, scope C create, scope U update) +if (isCreateOperation!(C, V) && isUpdateOperation!(U, V)) { - string[] keys = ["a", "b", "c", "d", "e", "f"]; - - // Test forward range capabilities of byKey + bool found; + // if key is @safe-ly copyable, `update` may infer @safe + static if (isSafeCopyable!K) { - int[string] aa; - foreach (key; keys) - aa[key] = 0; - - auto keyRange = aa.byKey(); - auto savedKeyRange = keyRange.save; - - // Consume key range once - size_t keyCount = 0; - while (!keyRange.empty) - { - aa[keyRange.front]++; - keyCount++; - keyRange.popFront(); - } - - foreach (key; keys) + auto p = () @trusted { - assert(aa[key] == 1); - } - assert(keyCount == keys.length); - - // Verify it's possible to iterate the range the second time - keyCount = 0; - while (!savedKeyRange.empty) - { - aa[savedKeyRange.front]++; - keyCount++; - savedKeyRange.popFront(); - } - - foreach (key; keys) - { - assert(aa[key] == 2); - } - assert(keyCount == keys.length); + return cast(V*) _aaGetX(cast(void**) &aa, typeid(V[K]), V.sizeof, &key, found); + } (); } - - // Test forward range capabilities of byValue - { - size_t[string] aa; - foreach (i; 0 .. keys.length) - { - aa[keys[i]] = i; - } - - auto valRange = aa.byValue(); - auto savedValRange = valRange.save; - - // Consume value range once - int[] hasSeen; - hasSeen.length = keys.length; - while (!valRange.empty) - { - assert(hasSeen[valRange.front] == 0); - hasSeen[valRange.front]++; - valRange.popFront(); - } - - foreach (sawValue; hasSeen) { assert(sawValue == 1); } - - // Verify it's possible to iterate the range the second time - hasSeen = null; - hasSeen.length = keys.length; - while (!savedValRange.empty) - { - assert(!hasSeen[savedValRange.front]); - hasSeen[savedValRange.front] = true; - savedValRange.popFront(); - } - - foreach (sawValue; hasSeen) { assert(sawValue); } - } -} - -pure nothrow unittest -{ - // expanded test for 5842: increase AA size past the point where the AA - // stops using binit, in order to test another code path in rehash. - int[int] aa; - foreach (int i; 0 .. 32) - aa[i] = i; - foreach (int i; 0 .. 32) - aa.remove(i); - aa.rehash; - aa[1] = 1; -} - -pure nothrow unittest -{ - // bug 13078 - shared string[][string] map; - map.rehash; -} - -pure nothrow unittest -{ - // bug 11761: test forward range functionality - auto aa = ["a": 1]; - - void testFwdRange(R, T)(R fwdRange, T testValue) - { - assert(!fwdRange.empty); - assert(fwdRange.front == testValue); - static assert(is(typeof(fwdRange.save) == typeof(fwdRange))); - - auto saved = fwdRange.save; - fwdRange.popFront(); - assert(fwdRange.empty); - - assert(!saved.empty); - assert(saved.front == testValue); - saved.popFront(); - assert(saved.empty); - } - - testFwdRange(aa.byKey, "a"); - testFwdRange(aa.byValue, 1); - //testFwdRange(aa.byPair, tuple("a", 1)); -} - -unittest -{ - // Issue 9119 - int[string] aa; - assert(aa.byKeyValue.empty); - - aa["a"] = 1; - aa["b"] = 2; - aa["c"] = 3; - - auto pairs = aa.byKeyValue; - - auto savedPairs = pairs.save; - size_t count = 0; - while (!pairs.empty) - { - assert(pairs.front.key in aa); - assert(pairs.front.value == aa[pairs.front.key]); - count++; - pairs.popFront(); - } - assert(count == aa.length); - - // Verify that saved range can iterate over the AA again - count = 0; - while (!savedPairs.empty) - { - assert(savedPairs.front.key in aa); - assert(savedPairs.front.value == aa[savedPairs.front.key]); - count++; - savedPairs.popFront(); - } - assert(count == aa.length); -} - -unittest -{ - // Verify iteration with const. - auto aa = [1:2, 3:4]; - foreach (const t; aa.byKeyValue) + else { - auto k = t.key; - auto v = t.value; + auto p = cast(V*) _aaGetX(cast(void**) &aa, typeid(V[K]), V.sizeof, &key, found); } + if (!found) + *p = create(); + else + *p = update(*p); } unittest { - // test for bug 14626 static struct S { - string[string] aa; - inout(string) key() inout { return aa.byKey().front; } - inout(string) val() inout { return aa.byValue().front; } - auto keyval() inout { return aa.byKeyValue().front; } + int x; + @nogc nothrow pure: + this(this) @system {} + + @safe const: + // stubs + bool opEquals(S rhs) { assert(0); } + size_t toHash() { assert(0); } } - S s = S(["a":"b"]); - assert(s.key() == "a"); - assert(s.val() == "b"); - assert(s.keyval().key == "a"); - assert(s.keyval().value == "b"); + int[string] aai; + static assert(is(typeof(() @safe { aai.require("a", 1234); }))); + static assert(is(typeof(() @safe { aai.update("a", { return 1234; }, (ref int x) { x++; return x; }); }))); - void testInoutKeyVal(inout(string) key) - { - inout(string)[typeof(key)] aa; + S[string] aas; + static assert(is(typeof(() { aas.require("a", S(1234)); }))); + static assert(is(typeof(() { aas.update("a", { return S(1234); }, (ref S s) { s.x++; return s; }); }))); + static assert(!is(typeof(() @safe { aas.update("a", { return S(1234); }, (ref S s) { s.x++; return s; }); }))); - foreach (i; aa.byKey()) {} - foreach (i; aa.byValue()) {} - foreach (i; aa.byKeyValue()) {} - } - - const int[int] caa; - static assert(is(typeof(caa.byValue().front) == const int)); + int[S] aais; + static assert(is(typeof(() { aais.require(S(1234), 1234); }))); + static assert(is(typeof(() { aais.update(S(1234), { return 1234; }, (ref int x) { x++; return x; }); }))); + static assert(!is(typeof(() @safe { aais.require(S(1234), 1234); }))); + static assert(!is(typeof(() @safe { aais.update(S(1234), { return 1234; }, (ref int x) { x++; return x; }); }))); } private void _destructRecurse(S)(ref S s) @@ -3190,32 +3073,35 @@ bool _ArrayEq(T1, T2)(T1[] a1, T2[] a2) return true; } -/** -Calculates the hash value of $(D arg) with $(D seed) initial value. -The result may not be equal to `typeid(T).getHash(&arg)`. -The $(D seed) value may be used for hash chaining: ----- -struct Test +version (D_Ddoc) { - int a; - string b; - MyObject c; + // This lets DDoc produce better documentation. + + /** + Calculates the hash value of `arg` with an optional `seed` initial value. + The result might not be equal to `typeid(T).getHash(&arg)`. - size_t toHash() const @safe pure nothrow + Params: + arg = argument to calculate the hash value of + seed = optional `seed` value (may be used for hash chaining) + + Return: calculated hash value of `arg` + */ + size_t hashOf(T)(auto ref T arg, size_t seed) + { + static import core.internal.hash; + return core.internal.hash.hashOf(arg, seed); + } + /// ditto + size_t hashOf(T)(auto ref T arg) { - size_t hash = a.hashOf(); - hash = b.hashOf(hash); - size_t h1 = c.myMegaHash(); - hash = h1.hashOf(hash); //Mix two hash values - return hash; + static import core.internal.hash; + return core.internal.hash.hashOf(arg); } } ----- -*/ -size_t hashOf(T)(auto ref T arg, size_t seed = 0) +else { - import core.internal.hash; - return core.internal.hash.hashOf(arg, seed); + public import core.internal.hash : hashOf; } unittest @@ -3722,58 +3608,15 @@ private size_t getArrayHash(in TypeInfo element, in void* ptr, in size_t count) } import core.internal.traits : externDFunc; - alias hashOf = externDFunc!("rt.util.hash.hashOf", - size_t function(const(void)[], size_t) @trusted pure nothrow @nogc); if (!hasCustomToHash(element)) - return hashOf(ptr[0 .. elementSize * count], 0); + return hashOf(ptr[0 .. elementSize * count]); size_t hash = 0; foreach (size_t i; 0 .. count) - hash += element.getHash(ptr + i * elementSize); + hash = hashOf(element.getHash(ptr + i * elementSize), hash); return hash; } - -// Tests ensure TypeInfo_Array.getHash uses element hash functions instead of hashing array data - -unittest -{ - class C - { - int i; - this(in int i) { this.i = i; } - override hash_t toHash() { return 0; } - } - C[] a1 = [new C(11)], a2 = [new C(12)]; - assert(typeid(C[]).getHash(&a1) == typeid(C[]).getHash(&a2)); -} - -unittest -{ - struct S - { - int i; - hash_t toHash() const @safe nothrow { return 0; } - } - S[] a1 = [S(11)], a2 = [S(12)]; - assert(typeid(S[]).getHash(&a1) == typeid(S[]).getHash(&a2)); -} - -@safe unittest -{ - struct S - { - int i; - const @safe nothrow: - hash_t toHash() { return 0; } - bool opEquals(const S) { return true; } - int opCmp(const S) { return 0; } - } - - int[S[]] aa = [[S(11)] : 13]; - assert(aa[[S(12)]] == 13); -} - /// Provide the .dup array property. @property auto dup(T)(T[] a) if (!is(const(T) : T)) diff --git a/libphobos/libdruntime/rt/aaA.d b/libphobos/libdruntime/rt/aaA.d index 37dcaab6f51..631847e4c2b 100644 --- a/libphobos/libdruntime/rt/aaA.d +++ b/libphobos/libdruntime/rt/aaA.d @@ -88,7 +88,7 @@ private: return used - deleted; } - @property size_t dim() const pure nothrow @nogc + @property size_t dim() const pure nothrow @nogc @safe { return buckets.length; } @@ -183,7 +183,7 @@ private pure nothrow @nogc: return hash == HASH_DELETED; } - @property bool filled() const + @property bool filled() const @safe { return cast(ptrdiff_t) hash < 0; } @@ -365,8 +365,29 @@ extern (C) size_t _aaLen(in AA aa) pure nothrow @nogc * If key was not in the aa, a mutable pointer to newly inserted value which * is set to all zeros */ -extern (C) void* _aaGetY(AA* aa, const TypeInfo_AssociativeArray ti, in size_t valsz, - in void* pkey) +extern (C) void* _aaGetY(AA* aa, const TypeInfo_AssociativeArray ti, + in size_t valsz, in void* pkey) +{ + bool found; + return _aaGetX(aa, ti, valsz, pkey, found); +} + +/****************************** + * Lookup *pkey in aa. + * Called only from implementation of require + * Params: + * aa = associative array opaque pointer + * ti = TypeInfo for the associative array + * valsz = ignored + * pkey = pointer to the key value + * found = true if the value was found + * Returns: + * if key was in the aa, a mutable pointer to the existing value. + * If key was not in the aa, a mutable pointer to newly inserted value which + * is set to all zeros + */ +extern (C) void* _aaGetX(AA* aa, const TypeInfo_AssociativeArray ti, + in size_t valsz, in void* pkey, out bool found) { // lazily alloc implementation if (aa.impl is null) @@ -377,7 +398,10 @@ extern (C) void* _aaGetY(AA* aa, const TypeInfo_AssociativeArray ti, in size_t v // found a value => return it if (auto p = aa.findSlotLookup(hash, pkey, ti.key)) + { + found = true; return p.entry + aa.valoff; + } auto p = aa.findSlotInsert(hash); if (p.deleted) @@ -584,6 +608,7 @@ extern (C) Impl* _d_assocarrayliteralTX(const TypeInfo_AssociativeArray ti, void void* pkey = keys.ptr; void* pval = vals.ptr; immutable off = aa.valoff; + uint actualLength = 0; foreach (_; 0 .. length) { immutable hash = calcHash(pkey, ti.key); @@ -595,6 +620,7 @@ extern (C) Impl* _d_assocarrayliteralTX(const TypeInfo_AssociativeArray ti, void p.hash = hash; p.entry = allocEntry(aa, pkey); // move key, no postblit aa.firstUsed = min(aa.firstUsed, cast(uint)(p - aa.buckets.ptr)); + actualLength++; } else if (aa.entryTI && hasDtor(ti.value)) { @@ -608,7 +634,7 @@ extern (C) Impl* _d_assocarrayliteralTX(const TypeInfo_AssociativeArray ti, void pkey += keysz; pval += valsz; } - aa.used = cast(uint) length; + aa.used = actualLength; return aa; } @@ -653,6 +679,7 @@ extern (C) hash_t _aaGetHash(in AA* aa, in TypeInfo tiRaw) nothrow auto uti = unqualify(tiRaw); auto ti = *cast(TypeInfo_AssociativeArray*)&uti; immutable off = aa.valoff; + auto keyHash = &ti.key.getHash; auto valHash = &ti.value.getHash; size_t h; @@ -660,10 +687,11 @@ extern (C) hash_t _aaGetHash(in AA* aa, in TypeInfo tiRaw) nothrow { if (!b.filled) continue; - size_t[2] h2 = [b.hash, valHash(b.entry + off)]; - // use XOR here, so that hash is independent of element order - h ^= hashOf(h2); + size_t[2] h2 = [keyHash(b.entry), valHash(b.entry + off)]; + // use addition here, so that hash is independent of element order + h += hashOf(h2); } + return h; } @@ -677,7 +705,7 @@ struct Range alias impl this; } -extern (C) pure nothrow @nogc +extern (C) pure nothrow @nogc @safe { Range _aaRange(AA aa) { @@ -694,21 +722,32 @@ extern (C) pure nothrow @nogc bool _aaRangeEmpty(Range r) { - return r.impl is null || r.idx == r.dim; + return r.impl is null || r.idx >= r.dim; } void* _aaRangeFrontKey(Range r) { + assert(!_aaRangeEmpty(r)); + if (r.idx >= r.dim) + return null; return r.buckets[r.idx].entry; } void* _aaRangeFrontValue(Range r) { - return r.buckets[r.idx].entry + r.valoff; + assert(!_aaRangeEmpty(r)); + if (r.idx >= r.dim) + return null; + + auto entry = r.buckets[r.idx].entry; + return entry is null ? + null : + (() @trusted { return entry + r.valoff; } ()); } void _aaRangePopFront(ref Range r) { + if (r.idx >= r.dim) return; for (++r.idx; r.idx < r.dim; ++r.idx) { if (r.buckets[r.idx].filled) @@ -717,221 +756,7 @@ extern (C) pure nothrow @nogc } } -//============================================================================== -// Unittests -//------------------------------------------------------------------------------ - -pure nothrow unittest -{ - int[string] aa; - - assert(aa.keys.length == 0); - assert(aa.values.length == 0); - - aa["hello"] = 3; - assert(aa["hello"] == 3); - aa["hello"]++; - assert(aa["hello"] == 4); - - assert(aa.length == 1); - - string[] keys = aa.keys; - assert(keys.length == 1); - assert(keys[0] == "hello"); - - int[] values = aa.values; - assert(values.length == 1); - assert(values[0] == 4); - - aa.rehash; - assert(aa.length == 1); - assert(aa["hello"] == 4); - - aa["foo"] = 1; - aa["bar"] = 2; - aa["batz"] = 3; - - assert(aa.keys.length == 4); - assert(aa.values.length == 4); - - foreach (a; aa.keys) - { - assert(a.length != 0); - assert(a.ptr != null); - } - - foreach (v; aa.values) - { - assert(v != 0); - } -} - -unittest // Test for Issue 10381 -{ - alias II = int[int]; - II aa1 = [0 : 1]; - II aa2 = [0 : 1]; - II aa3 = [0 : 2]; - assert(aa1 == aa2); // Passes - assert(typeid(II).equals(&aa1, &aa2)); - assert(!typeid(II).equals(&aa1, &aa3)); -} - -pure nothrow unittest -{ - string[int] key1 = [1 : "true", 2 : "false"]; - string[int] key2 = [1 : "false", 2 : "true"]; - string[int] key3; - - // AA lits create a larger hashtable - int[string[int]] aa1 = [key1 : 100, key2 : 200, key3 : 300]; - - // Ensure consistent hash values are computed for key1 - assert((key1 in aa1) !is null); - - // Manually assigning to an empty AA creates a smaller hashtable - int[string[int]] aa2; - aa2[key1] = 100; - aa2[key2] = 200; - aa2[key3] = 300; - - assert(aa1 == aa2); - - // Ensure binary-independence of equal hash keys - string[int] key2a; - key2a[1] = "false"; - key2a[2] = "true"; - - assert(aa1[key2a] == 200); -} - -// Issue 9852 -pure nothrow unittest -{ - // Original test case (revised, original assert was wrong) - int[string] a; - a["foo"] = 0; - a.remove("foo"); - assert(a == null); // should not crash - - int[string] b; - assert(b is null); - assert(a == b); // should not deref null - assert(b == a); // ditto - - int[string] c; - c["a"] = 1; - assert(a != c); // comparison with empty non-null AA - assert(c != a); - assert(b != c); // comparison with null AA - assert(c != b); -} - -// Bugzilla 14104 -unittest -{ - import core.stdc.stdio; - - alias K = const(ubyte)*; - size_t[K] aa; - immutable key = cast(K)(cast(size_t) uint.max + 1); - aa[key] = 12; - assert(key in aa); -} - -unittest -{ - int[int] aa; - foreach (k, v; aa) - assert(false); - foreach (v; aa) - assert(false); - assert(aa.byKey.empty); - assert(aa.byValue.empty); - assert(aa.byKeyValue.empty); - - size_t n; - aa = [0 : 3, 1 : 4, 2 : 5]; - foreach (k, v; aa) - { - n += k; - assert(k >= 0 && k < 3); - assert(v >= 3 && v < 6); - } - assert(n == 3); - n = 0; - - foreach (v; aa) - { - n += v; - assert(v >= 3 && v < 6); - } - assert(n == 12); - - n = 0; - foreach (k, v; aa) - { - ++n; - break; - } - assert(n == 1); - - n = 0; - foreach (v; aa) - { - ++n; - break; - } - assert(n == 1); -} - -unittest -{ - int[int] aa; - assert(!aa.remove(0)); - aa = [0 : 1]; - assert(aa.remove(0)); - assert(!aa.remove(0)); - aa[1] = 2; - assert(!aa.remove(0)); - assert(aa.remove(1)); - - assert(aa.length == 0); - assert(aa.byKey.empty); -} - -// test zero sized value (hashset) -unittest -{ - alias V = void[0]; - auto aa = [0 : V.init]; - assert(aa.length == 1); - assert(aa.byKey.front == 0); - assert(aa.byValue.front == V.init); - aa[1] = V.init; - assert(aa.length == 2); - aa[0] = V.init; - assert(aa.length == 2); - assert(aa.remove(0)); - aa[0] = V.init; - assert(aa.length == 2); - assert(aa == [0 : V.init, 1 : V.init]); -} - -// test tombstone purging -unittest -{ - int[int] aa; - foreach (i; 0 .. 6) - aa[i] = i; - foreach (i; 0 .. 6) - assert(aa.remove(i)); - foreach (i; 6 .. 10) - aa[i] = i; - assert(aa.length == 4); - foreach (i; 6 .. 10) - assert(i in aa); -} +// Most tests are now in in test_aa.d // test postblit for AA literals unittest @@ -982,34 +807,3 @@ unittest GC.runFinalizers((cast(char*)(&entryDtor))[0 .. 1]); assert(T.dtor == 6 && T.postblit == 2); } - -// for aa.clear -pure nothrow unittest -{ - int[int] aa; - assert(aa.length == 0); - foreach (i; 0 .. 100) - aa[i] = i * 2; - assert(aa.length == 100); - auto aa2 = aa; - assert(aa2.length == 100); - aa.clear(); - assert(aa.length == 0); - assert(aa2.length == 0); - - aa2[5] = 6; - assert(aa.length == 1); - assert(aa[5] == 6); -} - -// test AA as key (Issue 16974) -unittest -{ - int[int] a = [1 : 2], a2 = [1 : 2]; - - assert([a : 3] == [a : 3]); - assert([a : 3] == [a2 : 3]); - - assert(typeid(a).getHash(&a) == typeid(a).getHash(&a)); - assert(typeid(a).getHash(&a) == typeid(a).getHash(&a2)); -} diff --git a/libphobos/libdruntime/rt/typeinfo/ti_Acdouble.d b/libphobos/libdruntime/rt/typeinfo/ti_Acdouble.d index 90020300bc1..4eea4ad0936 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_Acdouble.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_Acdouble.d @@ -25,7 +25,7 @@ class TypeInfo_Ar : TypeInfo_Array override string toString() const { return (F[]).stringof; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { return Array!F.hashOf(*cast(F[]*)p); } diff --git a/libphobos/libdruntime/rt/typeinfo/ti_Acfloat.d b/libphobos/libdruntime/rt/typeinfo/ti_Acfloat.d index 0038fbc679e..126bfd80c8d 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_Acfloat.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_Acfloat.d @@ -25,7 +25,7 @@ class TypeInfo_Aq : TypeInfo_Array override string toString() const { return (F[]).stringof; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { return Array!F.hashOf(*cast(F[]*)p); } diff --git a/libphobos/libdruntime/rt/typeinfo/ti_Acreal.d b/libphobos/libdruntime/rt/typeinfo/ti_Acreal.d index f9346f42771..1d1421fa3e7 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_Acreal.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_Acreal.d @@ -25,7 +25,7 @@ class TypeInfo_Ac : TypeInfo_Array override string toString() const { return (F[]).stringof; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { return Array!F.hashOf(*cast(F[]*)p); } diff --git a/libphobos/libdruntime/rt/typeinfo/ti_Adouble.d b/libphobos/libdruntime/rt/typeinfo/ti_Adouble.d index e161e09a7fe..77904920419 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_Adouble.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_Adouble.d @@ -25,7 +25,7 @@ class TypeInfo_Ad : TypeInfo_Array override string toString() const { return (F[]).stringof; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { return Array!F.hashOf(*cast(F[]*)p); } diff --git a/libphobos/libdruntime/rt/typeinfo/ti_Afloat.d b/libphobos/libdruntime/rt/typeinfo/ti_Afloat.d index a03faf40970..f6ae8271968 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_Afloat.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_Afloat.d @@ -25,7 +25,7 @@ class TypeInfo_Af : TypeInfo_Array override string toString() const { return (F[]).stringof; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { return Array!F.hashOf(*cast(F[]*)p); } diff --git a/libphobos/libdruntime/rt/typeinfo/ti_Ag.d b/libphobos/libdruntime/rt/typeinfo/ti_Ag.d index e9ededeb05f..f61bd34bbb5 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_Ag.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_Ag.d @@ -14,7 +14,6 @@ module rt.typeinfo.ti_Ag; private import core.stdc.string; -private import rt.util.hash; private import core.internal.string; // byte[] @@ -25,10 +24,10 @@ class TypeInfo_Ag : TypeInfo_Array override string toString() const { return "byte[]"; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { const s = *cast(const void[]*)p; - return rt.util.hash.hashOf(s, 0); + return hashOf(s); } override bool equals(in void* p1, in void* p2) const @@ -118,54 +117,10 @@ class TypeInfo_Aa : TypeInfo_Ah { override string toString() const { return "char[]"; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { char[] s = *cast(char[]*)p; - size_t hash = 0; - -version (all) -{ - foreach (char c; s) - hash = hash * 11 + c; -} -else -{ - size_t len = s.length; - char *str = s; - - while (1) - { - switch (len) - { - case 0: - return hash; - - case 1: - hash *= 9; - hash += *cast(ubyte *)str; - return hash; - - case 2: - hash *= 9; - hash += *cast(ushort *)str; - return hash; - - case 3: - hash *= 9; - hash += (*cast(ushort *)str << 8) + - (cast(ubyte *)str)[2]; - return hash; - - default: - hash *= 9; - hash += *cast(uint *)str; - str += 4; - len -= 4; - break; - } - } -} - return hash; + return hashOf(s); } override @property inout(TypeInfo) next() inout diff --git a/libphobos/libdruntime/rt/typeinfo/ti_Aint.d b/libphobos/libdruntime/rt/typeinfo/ti_Aint.d index 52174e999f4..828fbc08ad9 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_Aint.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_Aint.d @@ -14,7 +14,6 @@ module rt.typeinfo.ti_Aint; private import core.stdc.string; -private import rt.util.hash; extern (C) void[] _adSort(void[] a, TypeInfo ti); @@ -26,10 +25,11 @@ class TypeInfo_Ai : TypeInfo_Array override string toString() const { return "int[]"; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { - const s = *cast(const int[]*)p; - return rt.util.hash.hashOf(s, 0); + // Hash as if unsigned. + const s = *cast(const uint[]*)p; + return hashOf(s); } override bool equals(in void* p1, in void* p2) const diff --git a/libphobos/libdruntime/rt/typeinfo/ti_Along.d b/libphobos/libdruntime/rt/typeinfo/ti_Along.d index ca0853a7426..51c741a3da2 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_Along.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_Along.d @@ -14,7 +14,6 @@ module rt.typeinfo.ti_Along; private import core.stdc.string; -private import rt.util.hash; // long[] @@ -24,10 +23,11 @@ class TypeInfo_Al : TypeInfo_Array override string toString() const { return "long[]"; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { - const s = *cast(const long[]*)p; - return rt.util.hash.hashOf(s, 0); + // Hash as if unsigned. + const s = *cast(const ulong[]*)p; + return hashOf(s); } override bool equals(in void* p1, in void* p2) const diff --git a/libphobos/libdruntime/rt/typeinfo/ti_Areal.d b/libphobos/libdruntime/rt/typeinfo/ti_Areal.d index b2b4d143f48..f1dd458e2e6 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_Areal.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_Areal.d @@ -25,7 +25,7 @@ class TypeInfo_Ae : TypeInfo_Array override string toString() const { return (F[]).stringof; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { return Array!F.hashOf(*cast(F[]*)p); } diff --git a/libphobos/libdruntime/rt/typeinfo/ti_Ashort.d b/libphobos/libdruntime/rt/typeinfo/ti_Ashort.d index e5a2d4b8c0c..e4b47e247b7 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_Ashort.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_Ashort.d @@ -14,7 +14,6 @@ module rt.typeinfo.ti_Ashort; private import core.stdc.string; -private import rt.util.hash; // short[] @@ -24,10 +23,11 @@ class TypeInfo_As : TypeInfo_Array override string toString() const { return "short[]"; } - override size_t getHash(in void* p) @trusted const + override size_t getHash(scope const void* p) @trusted const { - const s = *cast(const short[]*)p; - return rt.util.hash.hashOf(s, 0); + // Hash as if unsigned. + const s = *cast(const ushort[]*)p; + return hashOf(s); } override bool equals(in void* p1, in void* p2) const diff --git a/libphobos/libdruntime/rt/typeinfo/ti_C.d b/libphobos/libdruntime/rt/typeinfo/ti_C.d index 8bfae7901ea..df4987312a1 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_C.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_C.d @@ -22,7 +22,7 @@ class TypeInfo_C : TypeInfo //pure: //nothrow: - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { Object o = *cast(Object*)p; return o ? o.toHash() : 0; diff --git a/libphobos/libdruntime/rt/typeinfo/ti_byte.d b/libphobos/libdruntime/rt/typeinfo/ti_byte.d index 6b0f3108516..6a3efb144bf 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_byte.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_byte.d @@ -24,9 +24,9 @@ class TypeInfo_g : TypeInfo override string toString() const pure nothrow @safe { return "byte"; } - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return *cast(byte *)p; + return *cast(const byte *)p; } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/typeinfo/ti_cdouble.d b/libphobos/libdruntime/rt/typeinfo/ti_cdouble.d index 15bec352518..c396a17ce2c 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_cdouble.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_cdouble.d @@ -27,7 +27,7 @@ class TypeInfo_r : TypeInfo override string toString() const { return F.stringof; } - override size_t getHash(in void* p) const @trusted + override size_t getHash(scope const void* p) const @trusted { return Floating!F.hashOf(*cast(F*)p); } diff --git a/libphobos/libdruntime/rt/typeinfo/ti_cent.d b/libphobos/libdruntime/rt/typeinfo/ti_cent.d index 5e8cc70b534..a74f796d1c5 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_cent.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_cent.d @@ -13,8 +13,6 @@ */ module rt.typeinfo.ti_cent; -private import rt.util.hash; - static if (is(cent)): // cent @@ -28,9 +26,10 @@ class TypeInfo_zi : TypeInfo override string toString() const pure nothrow @safe { return "cent"; } - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return rt.util.hash.hashOf(p[0 .. cent.sizeof], 0); + // cent & ucent hash the same if ucent.sizeof >= size_t.sizeof. + return hashOf(*cast(const ucent*) p); } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/typeinfo/ti_cfloat.d b/libphobos/libdruntime/rt/typeinfo/ti_cfloat.d index 3b82f04d0d0..a3ad4ca9dbf 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_cfloat.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_cfloat.d @@ -27,7 +27,7 @@ class TypeInfo_q : TypeInfo override string toString() const { return F.stringof; } - override size_t getHash(in void* p) const @trusted + override size_t getHash(scope const void* p) const @trusted { return Floating!F.hashOf(*cast(F*)p); } diff --git a/libphobos/libdruntime/rt/typeinfo/ti_char.d b/libphobos/libdruntime/rt/typeinfo/ti_char.d index ba3841792c7..fbc5680335e 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_char.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_char.d @@ -24,9 +24,9 @@ class TypeInfo_a : TypeInfo override string toString() const pure nothrow @safe { return "char"; } - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return *cast(char *)p; + return *cast(const char *)p; } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/typeinfo/ti_creal.d b/libphobos/libdruntime/rt/typeinfo/ti_creal.d index b77429cf896..c064b7b872b 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_creal.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_creal.d @@ -27,7 +27,7 @@ class TypeInfo_c : TypeInfo override string toString() const { return F.stringof; } - override size_t getHash(in void* p) const @trusted + override size_t getHash(scope const void* p) const @trusted { return Floating!F.hashOf(*cast(F*)p); } diff --git a/libphobos/libdruntime/rt/typeinfo/ti_dchar.d b/libphobos/libdruntime/rt/typeinfo/ti_dchar.d index 2d4354c18aa..5d6fea161d5 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_dchar.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_dchar.d @@ -24,9 +24,9 @@ class TypeInfo_w : TypeInfo override string toString() const pure nothrow @safe { return "dchar"; } - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return *cast(dchar *)p; + return *cast(const dchar *)p; } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/typeinfo/ti_delegate.d b/libphobos/libdruntime/rt/typeinfo/ti_delegate.d index c5ed001e564..aaddd858159 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_delegate.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_delegate.d @@ -13,7 +13,6 @@ */ module rt.typeinfo.ti_delegate; -private import rt.util.hash; // delegate @@ -26,9 +25,9 @@ class TypeInfo_D : TypeInfo pure: nothrow: - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return rt.util.hash.hashOf(p[0 .. dg.sizeof], 0); + return hashOf(*cast(dg*)p); } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/typeinfo/ti_double.d b/libphobos/libdruntime/rt/typeinfo/ti_double.d index 8aa281f11b4..f5671cd032c 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_double.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_double.d @@ -27,7 +27,7 @@ class TypeInfo_d : TypeInfo override string toString() const { return F.stringof; } - override size_t getHash(in void* p) const @trusted + override size_t getHash(scope const void* p) const @trusted { return Floating!F.hashOf(*cast(F*)p); } diff --git a/libphobos/libdruntime/rt/typeinfo/ti_float.d b/libphobos/libdruntime/rt/typeinfo/ti_float.d index 60837d1c967..4cd68c7cf26 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_float.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_float.d @@ -27,7 +27,7 @@ class TypeInfo_f : TypeInfo override string toString() const { return F.stringof; } - override size_t getHash(in void* p) const @trusted + override size_t getHash(scope const void* p) const @trusted { return Floating!F.hashOf(*cast(F*)p); } diff --git a/libphobos/libdruntime/rt/typeinfo/ti_int.d b/libphobos/libdruntime/rt/typeinfo/ti_int.d index b0418c06fcf..6e32c43afe9 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_int.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_int.d @@ -24,9 +24,9 @@ class TypeInfo_i : TypeInfo override string toString() const pure nothrow @safe { return "int"; } - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return *cast(uint *)p; + return *cast(const int *)p; } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/typeinfo/ti_long.d b/libphobos/libdruntime/rt/typeinfo/ti_long.d index 4328a23a9c5..78fea117634 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_long.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_long.d @@ -13,8 +13,6 @@ */ module rt.typeinfo.ti_long; -private import rt.util.hash; - // long class TypeInfo_l : TypeInfo @@ -26,9 +24,13 @@ class TypeInfo_l : TypeInfo override string toString() const pure nothrow @safe { return "long"; } - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return rt.util.hash.hashOf(p[0 .. long.sizeof], 0); + static if (ulong.sizeof <= size_t.sizeof) + return *cast(const long*)p; + else + // long & ulong hash the same if ulong.sizeof > size_t.sizeof. + return hashOf(*cast(const ulong*)p); } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/typeinfo/ti_n.d b/libphobos/libdruntime/rt/typeinfo/ti_n.d index 7c068109db5..b6cea03218c 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_n.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_n.d @@ -19,7 +19,7 @@ class TypeInfo_n : TypeInfo { override string toString() const @safe { return "typeof(null)"; } - override size_t getHash(in void* p) const + override size_t getHash(scope const void* p) const { return 0; } diff --git a/libphobos/libdruntime/rt/typeinfo/ti_ptr.d b/libphobos/libdruntime/rt/typeinfo/ti_ptr.d index a23511a6fdd..8857ef90717 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_ptr.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_ptr.d @@ -23,9 +23,10 @@ class TypeInfo_P : TypeInfo pure: nothrow: - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return cast(size_t)*cast(void**)p; + size_t addr = cast(size_t) *cast(const void**)p; + return addr ^ (addr >> 4); } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/typeinfo/ti_real.d b/libphobos/libdruntime/rt/typeinfo/ti_real.d index 77ae1265112..fb20f1429ac 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_real.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_real.d @@ -27,7 +27,7 @@ class TypeInfo_e : TypeInfo override string toString() const { return F.stringof; } - override size_t getHash(in void* p) const @trusted + override size_t getHash(scope const void* p) const @trusted { return Floating!F.hashOf(*cast(F*)p); } diff --git a/libphobos/libdruntime/rt/typeinfo/ti_short.d b/libphobos/libdruntime/rt/typeinfo/ti_short.d index f636fc3af3c..bccbe63477a 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_short.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_short.d @@ -24,9 +24,9 @@ class TypeInfo_s : TypeInfo override string toString() const pure nothrow @safe { return "short"; } - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return *cast(short *)p; + return *cast(const short *)p; } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/typeinfo/ti_ubyte.d b/libphobos/libdruntime/rt/typeinfo/ti_ubyte.d index 97b902ab079..9643179be66 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_ubyte.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_ubyte.d @@ -24,9 +24,9 @@ class TypeInfo_h : TypeInfo override string toString() const pure nothrow @safe { return "ubyte"; } - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return *cast(ubyte *)p; + return *cast(const ubyte *)p; } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/typeinfo/ti_ucent.d b/libphobos/libdruntime/rt/typeinfo/ti_ucent.d index e5f95cf963b..ffa67d8a624 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_ucent.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_ucent.d @@ -13,8 +13,6 @@ */ module rt.typeinfo.ti_ucent; -private import rt.util.hash; - static if (is(ucent)): // ucent @@ -28,9 +26,9 @@ class TypeInfo_zk : TypeInfo override string toString() const pure nothrow @safe { return "ucent"; } - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return rt.util.hash.hashOf(p[0 .. ucent.sizeof], 0); + return hashOf(*cast(const ucent*) p); } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/typeinfo/ti_uint.d b/libphobos/libdruntime/rt/typeinfo/ti_uint.d index 6cd523ba2a6..09bff186b3f 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_uint.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_uint.d @@ -24,9 +24,9 @@ class TypeInfo_k : TypeInfo override string toString() const pure nothrow @safe { return "uint"; } - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return *cast(uint *)p; + return *cast(const uint *)p; } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/typeinfo/ti_ulong.d b/libphobos/libdruntime/rt/typeinfo/ti_ulong.d index fc87ce5753c..3fdaacd8ec9 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_ulong.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_ulong.d @@ -13,7 +13,6 @@ */ module rt.typeinfo.ti_ulong; -private import rt.util.hash; // ulong @@ -26,9 +25,12 @@ class TypeInfo_m : TypeInfo override string toString() const pure nothrow @safe { return "ulong"; } - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return rt.util.hash.hashOf(p[0 .. ulong.sizeof], 0); + static if (ulong.sizeof <= size_t.sizeof) + return *cast(const ulong*)p; + else + return hashOf(*cast(const ulong*)p); } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/typeinfo/ti_ushort.d b/libphobos/libdruntime/rt/typeinfo/ti_ushort.d index ae246564326..90623f2d14c 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_ushort.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_ushort.d @@ -24,9 +24,9 @@ class TypeInfo_t : TypeInfo override string toString() const pure nothrow @safe { return "ushort"; } - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return *cast(ushort *)p; + return *cast(const ushort *)p; } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/typeinfo/ti_void.d b/libphobos/libdruntime/rt/typeinfo/ti_void.d index 28e8c15a06c..1facb955597 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_void.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_void.d @@ -24,7 +24,7 @@ class TypeInfo_v : TypeInfo override string toString() const pure nothrow @safe { return "void"; } - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { assert(0); } diff --git a/libphobos/libdruntime/rt/typeinfo/ti_wchar.d b/libphobos/libdruntime/rt/typeinfo/ti_wchar.d index 3e2fba9b3b5..dcf8256bf59 100644 --- a/libphobos/libdruntime/rt/typeinfo/ti_wchar.d +++ b/libphobos/libdruntime/rt/typeinfo/ti_wchar.d @@ -24,9 +24,9 @@ class TypeInfo_u : TypeInfo override string toString() { return "wchar"; } - override size_t getHash(in void* p) + override size_t getHash(scope const void* p) { - return *cast(wchar *)p; + return *cast(const wchar *)p; } override bool equals(in void* p1, in void* p2) diff --git a/libphobos/libdruntime/rt/util/container/hashtab.d b/libphobos/libdruntime/rt/util/container/hashtab.d index 91a40a8a948..13b88638296 100644 --- a/libphobos/libdruntime/rt/util/container/hashtab.d +++ b/libphobos/libdruntime/rt/util/container/hashtab.d @@ -146,11 +146,10 @@ private: static hash_t hashOf(in ref Key key) @trusted { - import rt.util.hash : hashOf; static if (is(Key U : U[])) - return hashOf(key, 0); + return .hashOf(key, 0); else - return hashOf((&key)[0 .. 1], 0); + return .hashOf((&key)[0 .. 1], 0); } @property hash_t mask() const diff --git a/libphobos/libdruntime/rt/util/hash.d b/libphobos/libdruntime/rt/util/hash.d deleted file mode 100644 index 19943a4d6d2..00000000000 --- a/libphobos/libdruntime/rt/util/hash.d +++ /dev/null @@ -1,107 +0,0 @@ -/** - * The default hash implementation. - * - * Copyright: Copyright Sean Kelly 2009 - 2016. - * License: $(WEB www.boost.org/LICENSE_1_0.txt, Boost License 1.0). - * Authors: Sean Kelly - * Source: $(DRUNTIMESRC src/rt/util/_hash.d) - */ -module rt.util.hash; - - -version (X86) - version = AnyX86; -version (X86_64) - version = AnyX86; -version (AnyX86) - version = HasUnalignedOps; - - -@trusted pure nothrow @nogc -size_t hashOf( const(void)[] buf, size_t seed ) -{ - /* - * This is Paul Hsieh's SuperFastHash algorithm, described here: - * http://www.azillionmonkeys.com/qed/hash.html - * It is protected by the following open source license: - * http://www.azillionmonkeys.com/qed/weblicense.html - */ - static uint get16bits( const (ubyte)* x ) pure nothrow @nogc - { - // CTFE doesn't support casting ubyte* -> ushort*, so revert to - // per-byte access when in CTFE. - version (HasUnalignedOps) - { - if (!__ctfe) - return *cast(ushort*) x; - } - - return ((cast(uint) x[1]) << 8) + (cast(uint) x[0]); - } - - // NOTE: SuperFastHash normally starts with a zero hash value. The seed - // value was incorporated to allow chaining. - auto data = cast(const(ubyte)*) buf.ptr; - auto len = buf.length; - auto hash = seed; - - if ( len == 0 || data is null ) - return 0; - - int rem = len & 3; - len >>= 2; - - for ( ; len > 0; len-- ) - { - hash += get16bits( data ); - auto tmp = (get16bits( data + 2 ) << 11) ^ hash; - hash = (hash << 16) ^ tmp; - data += 2 * ushort.sizeof; - hash += hash >> 11; - } - - switch ( rem ) - { - case 3: hash += get16bits( data ); - hash ^= hash << 16; - hash ^= data[ushort.sizeof] << 18; - hash += hash >> 11; - break; - case 2: hash += get16bits( data ); - hash ^= hash << 11; - hash += hash >> 17; - break; - case 1: hash += *data; - hash ^= hash << 10; - hash += hash >> 1; - break; - default: - break; - } - - /* Force "avalanching" of final 127 bits */ - hash ^= hash << 3; - hash += hash >> 5; - hash ^= hash << 4; - hash += hash >> 17; - hash ^= hash << 25; - hash += hash >> 6; - - return hash; -} - -unittest -{ - enum test_str = "Sample string"; - size_t hashval = hashOf(test_str, 5); - - //import core.stdc.stdio; - //printf("hashval = %lld\n", cast(long)hashval); - - if (hashval.sizeof == 4) - assert(hashval == 528740845); - else if (hashval.sizeof == 8) - assert(hashval == 8106800467257150594L); - else - assert(0); -} diff --git a/libphobos/libdruntime/rt/util/typeinfo.d b/libphobos/libdruntime/rt/util/typeinfo.d index ded5d4da5e2..2cc1c236c10 100644 --- a/libphobos/libdruntime/rt/util/typeinfo.d +++ b/libphobos/libdruntime/rt/util/typeinfo.d @@ -6,6 +6,7 @@ * Authors: Kenji Hara */ module rt.util.typeinfo; +static import core.internal.hash; template Floating(T) if (is(T == float) || is(T == double) || is(T == real)) @@ -32,19 +33,7 @@ if (is(T == float) || is(T == double) || is(T == real)) return (d1 == d2) ? 0 : ((d1 < d2) ? -1 : 1); } - size_t hashOf(T value) @trusted - { - if (value == 0) // +0.0 and -0.0 - value = 0; - - static if (is(T == float)) // special case? - return *cast(uint*)&value; - else - { - import rt.util.hash; - return rt.util.hash.hashOf((&value)[0 .. 1], 0); - } - } + public alias hashOf = core.internal.hash.hashOf; } template Floating(T) if (is(T == cfloat) || is(T == cdouble) || is(T == creal)) @@ -73,13 +62,7 @@ if (is(T == cfloat) || is(T == cdouble) || is(T == creal)) return result; } - size_t hashOf(T value) @trusted - { - if (value == 0 + 0i) - value = 0 + 0i; - import rt.util.hash; - return rt.util.hash.hashOf((&value)[0 .. 1], 0); - } + public alias hashOf = core.internal.hash.hashOf; } template Array(T) @@ -118,13 +101,7 @@ if (is(T == float) || is(T == double) || is(T == real) || return 0; } - size_t hashOf(T[] value) - { - size_t h = 0; - foreach (e; value) - h += Floating!T.hashOf(e); - return h; - } + public alias hashOf = core.internal.hash.hashOf; } version (unittest) @@ -247,7 +224,7 @@ unittest { assert(f1 == 0 + 0i); - assert(f1 == f2); + assert(f1 == f2); assert(f1 !is f2); ti = typeid(F); assert(ti.getHash(&f1) == ti.getHash(&f2)); diff --git a/libphobos/testsuite/libphobos.aa/aa.exp b/libphobos/testsuite/libphobos.aa/aa.exp new file mode 100644 index 00000000000..2bfb7b28bdb --- /dev/null +++ b/libphobos/testsuite/libphobos.aa/aa.exp @@ -0,0 +1,29 @@ +# Copyright (C) 2018 Free Software Foundation, Inc. +# +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 3 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with GCC; see the file COPYING3. If not see +# <http://www.gnu.org/licenses/>. + +load_lib libphobos-dg.exp + +# Initialize dg. +dg-init + +# Gather a list of all tests. +set tests [lsort [find $srcdir/$subdir *.d]] + +# Main loop. +dg-runtest $tests "" $DEFAULT_DFLAGS + +# All done. +dg-finish diff --git a/libphobos/testsuite/libphobos.aa/test_aa.d b/libphobos/testsuite/libphobos.aa/test_aa.d new file mode 100644 index 00000000000..d6222b13175 --- /dev/null +++ b/libphobos/testsuite/libphobos.aa/test_aa.d @@ -0,0 +1,856 @@ +void main() +{ + testKeysValues1(); + testKeysValues2(); + testGet1(); + testGet2(); + testRequire1(); + testRequire2(); + testRequire3(); + testUpdate1(); + testUpdate2(); + testByKey1(); + testByKey2(); + testByKey3(); + testByKey4(); + issue5842(); + issue5842Expanded(); + issue5925(); + issue8583(); + issue9052(); + issue9119(); + issue9852(); + issue10381(); + issue10720(); + issue11761(); + issue13078(); + issue14104(); + issue14626(); + issue15290(); + issue15367(); + issue16974(); + issue18071(); + testIterationWithConst(); + testStructArrayKey(); + miscTests1(); + miscTests2(); + testRemove(); + testZeroSizedValue(); + testTombstonePurging(); + testClear(); +} + +void testKeysValues1() +{ + static struct T + { + byte b; + static size_t count; + this(this) { ++count; } + } + T[int] aa; + T t; + aa[0] = t; + aa[1] = t; + assert(T.count == 2); + auto vals = aa.values; + assert(vals.length == 2); + assert(T.count == 4); + + T.count = 0; + int[T] aa2; + aa2[t] = 0; + assert(T.count == 1); + aa2[t] = 1; + assert(T.count == 1); + auto keys = aa2.keys; + assert(keys.length == 1); + assert(T.count == 2); +} + +void testKeysValues2() nothrow pure +{ + int[string] aa; + + assert(aa.keys.length == 0); + assert(aa.values.length == 0); + + aa["hello"] = 3; + assert(aa["hello"] == 3); + aa["hello"]++; + assert(aa["hello"] == 4); + + assert(aa.length == 1); + + string[] keys = aa.keys; + assert(keys.length == 1); + assert(keys[0] == "hello"); + + int[] values = aa.values; + assert(values.length == 1); + assert(values[0] == 4); + + aa.rehash; + assert(aa.length == 1); + assert(aa["hello"] == 4); + + aa["foo"] = 1; + aa["bar"] = 2; + aa["batz"] = 3; + + assert(aa.keys.length == 4); + assert(aa.values.length == 4); + + foreach (a; aa.keys) + { + assert(a.length != 0); + assert(a.ptr != null); + } + + foreach (v; aa.values) + { + assert(v != 0); + } +} + +void testGet1() @safe +{ + int[string] aa; + int a; + foreach (val; aa.byKeyValue) + { + ++aa[val.key]; + a = val.value; + } +} + +void testGet2() +{ + static class T + { + static size_t count; + this() { ++count; } + } + + T[string] aa; + + auto a = new T; + aa["foo"] = a; + assert(T.count == 1); + auto b = aa.get("foo", new T); + assert(T.count == 1); + assert(b is a); + auto c = aa.get("bar", new T); + assert(T.count == 2); + assert(c !is a); + + //Obviously get doesn't add. + assert("bar" !in aa); +} + +void testRequire1() +{ + static class T + { + static size_t count; + this() { ++count; } + } + + T[string] aa; + + auto a = new T; + aa["foo"] = a; + assert(T.count == 1); + auto b = aa.require("foo", new T); + assert(T.count == 1); + assert(b is a); + auto c = aa.require("bar", null); + assert(T.count == 1); + assert(c is null); + assert("bar" in aa); + auto d = aa.require("bar", new T); + assert(d is null); + auto e = aa.require("baz", new T); + assert(T.count == 2); + assert(e !is a); + + assert("baz" in aa); + + bool created = false; + auto f = aa.require("qux", { created = true; return new T; }()); + assert(created == true); + + T g; + auto h = aa.require("qux", { g = new T; return g; }()); + assert(g !is h); +} + +void testRequire2() +{ + static struct S + { + int value; + } + + S[string] aa; + + aa.require("foo").value = 1; + assert(aa == ["foo" : S(1)]); + + aa["bar"] = S(2); + auto a = aa.require("bar", S(3)); + assert(a == S(2)); + + auto b = aa["bar"]; + assert(b == S(2)); + + S* c = &aa.require("baz", S(4)); + assert(c is &aa["baz"]); + assert(*c == S(4)); + + assert("baz" in aa); + + auto d = aa["baz"]; + assert(d == S(4)); +} + +void testRequire3() pure +{ + string[string] aa; + + auto a = aa.require("foo", "bar"); + assert("foo" in aa); +} + + +void testUpdate1() +{ + static class C {} + C[string] aa; + + C orig = new C; + aa["foo"] = orig; + + C newer; + C older; + + void test(string key) + { + aa.update(key, { + newer = new C; + return newer; + }, (ref C c) { + older = c; + newer = new C; + return newer; + }); + } + + test("foo"); + assert(older is orig); + assert(newer is aa["foo"]); + + test("bar"); + assert(newer is aa["bar"]); +} + +void testUpdate2() +{ + static class C {} + C[string] aa; + + auto created = false; + auto updated = false; + + class Creator + { + C opCall() + { + created = true; + return new C(); + } + } + + class Updater + { + C opCall(ref C) + { + updated = true; + return new C(); + } + } + + aa.update("foo", new Creator, new Updater); + assert(created); + aa.update("foo", new Creator, new Updater); + assert(updated); +} + +void testByKey1() +{ + static assert(!__traits(compiles, + () @safe { + struct BadValue + { + int x; + this(this) @safe { *(cast(ubyte*)(null) + 100000) = 5; } // not @safe + alias x this; + } + + BadValue[int] aa; + () @safe { auto x = aa.byKey.front; } (); + } + )); +} + +void testByKey2() nothrow pure +{ + int[int] a; + foreach (i; a.byKey) + { + assert(false); + } + foreach (i; a.byValue) + { + assert(false); + } +} + +void testByKey3() /*nothrow*/ pure +{ + auto a = [ 1:"one", 2:"two", 3:"three" ]; + auto b = a.dup; + assert(b == [ 1:"one", 2:"two", 3:"three" ]); + + int[] c; + foreach (k; a.byKey) + { + c ~= k; + } + + assert(c.length == 3); + assert(c[0] == 1 || c[1] == 1 || c[2] == 1); + assert(c[0] == 2 || c[1] == 2 || c[2] == 2); + assert(c[0] == 3 || c[1] == 3 || c[2] == 3); +} + +void testByKey4() nothrow pure +{ + string[] keys = ["a", "b", "c", "d", "e", "f"]; + + // Test forward range capabilities of byKey + { + int[string] aa; + foreach (key; keys) + aa[key] = 0; + + auto keyRange = aa.byKey(); + auto savedKeyRange = keyRange.save; + + // Consume key range once + size_t keyCount = 0; + while (!keyRange.empty) + { + aa[keyRange.front]++; + keyCount++; + keyRange.popFront(); + } + + foreach (key; keys) + { + assert(aa[key] == 1); + } + assert(keyCount == keys.length); + + // Verify it's possible to iterate the range the second time + keyCount = 0; + while (!savedKeyRange.empty) + { + aa[savedKeyRange.front]++; + keyCount++; + savedKeyRange.popFront(); + } + + foreach (key; keys) + { + assert(aa[key] == 2); + } + assert(keyCount == keys.length); + } + + // Test forward range capabilities of byValue + { + size_t[string] aa; + foreach (i; 0 .. keys.length) + { + aa[keys[i]] = i; + } + + auto valRange = aa.byValue(); + auto savedValRange = valRange.save; + + // Consume value range once + int[] hasSeen; + hasSeen.length = keys.length; + while (!valRange.empty) + { + assert(hasSeen[valRange.front] == 0); + hasSeen[valRange.front]++; + valRange.popFront(); + } + + foreach (sawValue; hasSeen) { assert(sawValue == 1); } + + // Verify it's possible to iterate the range the second time + hasSeen = null; + hasSeen.length = keys.length; + while (!savedValRange.empty) + { + assert(!hasSeen[savedValRange.front]); + hasSeen[savedValRange.front] = true; + savedValRange.popFront(); + } + + foreach (sawValue; hasSeen) { assert(sawValue); } + } +} + +void issue5842() pure nothrow +{ + string[string] test = null; + test["test1"] = "test1"; + test.remove("test1"); + test.rehash; + test["test3"] = "test3"; // causes divide by zero if rehash broke the AA +} + +/// expanded test for 5842: increase AA size past the point where the AA +/// stops using binit, in order to test another code path in rehash. +void issue5842Expanded() pure nothrow +{ + int[int] aa; + foreach (int i; 0 .. 32) + aa[i] = i; + foreach (int i; 0 .. 32) + aa.remove(i); + aa.rehash; + aa[1] = 1; +} + +void issue5925() nothrow pure +{ + const a = [4:0]; + const b = [4:0]; + assert(a == b); +} + +/// test for bug 8583: ensure Slot and aaA are on the same page wrt value alignment +void issue8583() nothrow pure +{ + string[byte] aa0 = [0: "zero"]; + string[uint[3]] aa1 = [[1,2,3]: "onetwothree"]; + ushort[uint[3]] aa2 = [[9,8,7]: 987]; + ushort[uint[4]] aa3 = [[1,2,3,4]: 1234]; + string[uint[5]] aa4 = [[1,2,3,4,5]: "onetwothreefourfive"]; + + assert(aa0.byValue.front == "zero"); + assert(aa1.byValue.front == "onetwothree"); + assert(aa2.byValue.front == 987); + assert(aa3.byValue.front == 1234); + assert(aa4.byValue.front == "onetwothreefourfive"); +} + +void issue9052() nothrow pure +{ + static struct Json { + Json[string] aa; + void opAssign(Json) {} + size_t length() const { return aa.length; } + // This length() instantiates AssociativeArray!(string, const(Json)) to call AA.length(), and + // inside ref Slot opAssign(Slot p); (which is automatically generated by compiler in Slot), + // this.value = p.value would actually fail, because both side types of the assignment + // are const(Json). + } +} + +void issue9119() +{ + int[string] aa; + assert(aa.byKeyValue.empty); + + aa["a"] = 1; + aa["b"] = 2; + aa["c"] = 3; + + auto pairs = aa.byKeyValue; + + auto savedPairs = pairs.save; + size_t count = 0; + while (!pairs.empty) + { + assert(pairs.front.key in aa); + assert(pairs.front.value == aa[pairs.front.key]); + count++; + pairs.popFront(); + } + assert(count == aa.length); + + // Verify that saved range can iterate over the AA again + count = 0; + while (!savedPairs.empty) + { + assert(savedPairs.front.key in aa); + assert(savedPairs.front.value == aa[savedPairs.front.key]); + count++; + savedPairs.popFront(); + } + assert(count == aa.length); +} + +void issue9852() nothrow pure +{ + // Original test case (revised, original assert was wrong) + int[string] a; + a["foo"] = 0; + a.remove("foo"); + assert(a == null); // should not crash + + int[string] b; + assert(b is null); + assert(a == b); // should not deref null + assert(b == a); // ditto + + int[string] c; + c["a"] = 1; + assert(a != c); // comparison with empty non-null AA + assert(c != a); + assert(b != c); // comparison with null AA + assert(c != b); +} + +void issue10381() +{ + alias II = int[int]; + II aa1 = [0 : 1]; + II aa2 = [0 : 1]; + II aa3 = [0 : 2]; + assert(aa1 == aa2); // Passes + assert(typeid(II).equals(&aa1, &aa2)); + assert(!typeid(II).equals(&aa1, &aa3)); +} + +void issue10720() nothrow pure +{ + static struct NC + { + @disable this(this) { } + } + + NC[string] aa; + static assert(!is(aa.nonExistingField)); +} + +/// bug 11761: test forward range functionality +void issue11761() pure nothrow +{ + auto aa = ["a": 1]; + + void testFwdRange(R, T)(R fwdRange, T testValue) + { + assert(!fwdRange.empty); + assert(fwdRange.front == testValue); + static assert(is(typeof(fwdRange.save) == typeof(fwdRange))); + + auto saved = fwdRange.save; + fwdRange.popFront(); + assert(fwdRange.empty); + + assert(!saved.empty); + assert(saved.front == testValue); + saved.popFront(); + assert(saved.empty); + } + + testFwdRange(aa.byKey, "a"); + testFwdRange(aa.byValue, 1); + //testFwdRange(aa.byPair, tuple("a", 1)); +} + +void issue13078() nothrow pure +{ + shared string[][string] map; + map.rehash; +} + +void issue14104() +{ + import core.stdc.stdio; + + alias K = const(ubyte)*; + size_t[K] aa; + immutable key = cast(K)(cast(size_t) uint.max + 1); + aa[key] = 12; + assert(key in aa); +} + +void issue14626() +{ + static struct S + { + string[string] aa; + inout(string) key() inout { return aa.byKey().front; } + inout(string) val() inout { return aa.byValue().front; } + auto keyval() inout { return aa.byKeyValue().front; } + } + + S s = S(["a":"b"]); + assert(s.key() == "a"); + assert(s.val() == "b"); + assert(s.keyval().key == "a"); + assert(s.keyval().value == "b"); + + void testInoutKeyVal(inout(string) key) + { + inout(string)[typeof(key)] aa; + + foreach (i; aa.byKey()) {} + foreach (i; aa.byValue()) {} + foreach (i; aa.byKeyValue()) {} + } + + const int[int] caa; + static assert(is(typeof(caa.byValue().front) == const int)); +} + +/// test duplicated keys in AA literal +/// https://issues.dlang.org/show_bug.cgi?id=15290 +void issue15290() +{ + string[int] aa = [ 0: "a", 0: "b" ]; + assert(aa.length == 1); + assert(aa.keys == [ 0 ]); +} + +void issue15367() +{ + void f1() {} + void f2() {} + + // TypeInfo_Delegate.getHash + int[void delegate()] aa; + assert(aa.length == 0); + aa[&f1] = 1; + assert(aa.length == 1); + aa[&f1] = 1; + assert(aa.length == 1); + + auto a1 = [&f2, &f1]; + auto a2 = [&f2, &f1]; + + // TypeInfo_Delegate.equals + for (auto i = 0; i < 2; i++) + assert(a1[i] == a2[i]); + assert(a1 == a2); + + // TypeInfo_Delegate.compare + for (auto i = 0; i < 2; i++) + assert(a1[i] <= a2[i]); + assert(a1 <= a2); +} + +/// test AA as key +/// https://issues.dlang.org/show_bug.cgi?id=16974 +void issue16974() +{ + int[int] a = [1 : 2], a2 = [1 : 2]; + + assert([a : 3] == [a : 3]); + assert([a : 3] == [a2 : 3]); + + assert(typeid(a).getHash(&a) == typeid(a).getHash(&a)); + assert(typeid(a).getHash(&a) == typeid(a).getHash(&a2)); +} + +/// test safety for alias-this'd AA that have unsafe opCast +/// https://issues.dlang.org/show_bug.cgi?id=18071 +void issue18071() +{ + static struct Foo + { + int[int] aa; + auto opCast() pure nothrow @nogc + { + *cast(uint*)0xdeadbeef = 0xcafebabe;// unsafe + return null; + } + alias aa this; + } + + Foo f; + () @safe { assert(f.byKey.empty); }(); +} + +/// Verify iteration with const. +void testIterationWithConst() +{ + auto aa = [1:2, 3:4]; + foreach (const t; aa.byKeyValue) + { + auto k = t.key; + auto v = t.value; + } +} + +void testStructArrayKey() @safe +{ + struct S + { + int i; + const @safe nothrow: + hash_t toHash() { return 0; } + bool opEquals(const S) { return true; } + int opCmp(const S) { return 0; } + } + + int[S[]] aa = [[S(11)] : 13]; + assert(aa[[S(12)]] == 13); +} + +void miscTests1() pure nothrow +{ + string[int] key1 = [1 : "true", 2 : "false"]; + string[int] key2 = [1 : "false", 2 : "true"]; + string[int] key3; + + // AA lits create a larger hashtable + int[string[int]] aa1 = [key1 : 100, key2 : 200, key3 : 300]; + + // Ensure consistent hash values are computed for key1 + assert((key1 in aa1) !is null); + + // Manually assigning to an empty AA creates a smaller hashtable + int[string[int]] aa2; + aa2[key1] = 100; + aa2[key2] = 200; + aa2[key3] = 300; + + assert(aa1 == aa2); + + // Ensure binary-independence of equal hash keys + string[int] key2a; + key2a[1] = "false"; + key2a[2] = "true"; + + assert(aa1[key2a] == 200); +} + +void miscTests2() +{ + int[int] aa; + foreach (k, v; aa) + assert(false); + foreach (v; aa) + assert(false); + assert(aa.byKey.empty); + assert(aa.byValue.empty); + assert(aa.byKeyValue.empty); + + size_t n; + aa = [0 : 3, 1 : 4, 2 : 5]; + foreach (k, v; aa) + { + n += k; + assert(k >= 0 && k < 3); + assert(v >= 3 && v < 6); + } + assert(n == 3); + n = 0; + + foreach (v; aa) + { + n += v; + assert(v >= 3 && v < 6); + } + assert(n == 12); + + n = 0; + foreach (k, v; aa) + { + ++n; + break; + } + assert(n == 1); + + n = 0; + foreach (v; aa) + { + ++n; + break; + } + assert(n == 1); +} + +void testRemove() +{ + int[int] aa; + assert(!aa.remove(0)); + aa = [0 : 1]; + assert(aa.remove(0)); + assert(!aa.remove(0)); + aa[1] = 2; + assert(!aa.remove(0)); + assert(aa.remove(1)); + + assert(aa.length == 0); + assert(aa.byKey.empty); +} + +/// test zero sized value (hashset) +void testZeroSizedValue() +{ + alias V = void[0]; + auto aa = [0 : V.init]; + assert(aa.length == 1); + assert(aa.byKey.front == 0); + assert(aa.byValue.front == V.init); + aa[1] = V.init; + assert(aa.length == 2); + aa[0] = V.init; + assert(aa.length == 2); + assert(aa.remove(0)); + aa[0] = V.init; + assert(aa.length == 2); + assert(aa == [0 : V.init, 1 : V.init]); +} + +void testTombstonePurging() +{ + int[int] aa; + foreach (i; 0 .. 6) + aa[i] = i; + foreach (i; 0 .. 6) + assert(aa.remove(i)); + foreach (i; 6 .. 10) + aa[i] = i; + assert(aa.length == 4); + foreach (i; 6 .. 10) + assert(i in aa); +} + +void testClear() +{ + int[int] aa; + assert(aa.length == 0); + foreach (i; 0 .. 100) + aa[i] = i * 2; + assert(aa.length == 100); + auto aa2 = aa; + assert(aa2.length == 100); + aa.clear(); + assert(aa.length == 0); + assert(aa2.length == 0); + + aa2[5] = 6; + assert(aa.length == 1); + assert(aa[5] == 6); +} diff --git a/libphobos/testsuite/libphobos.hash/hash.exp b/libphobos/testsuite/libphobos.hash/hash.exp new file mode 100644 index 00000000000..2bfb7b28bdb --- /dev/null +++ b/libphobos/testsuite/libphobos.hash/hash.exp @@ -0,0 +1,29 @@ +# Copyright (C) 2018 Free Software Foundation, Inc. +# +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 3 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with GCC; see the file COPYING3. If not see +# <http://www.gnu.org/licenses/>. + +load_lib libphobos-dg.exp + +# Initialize dg. +dg-init + +# Gather a list of all tests. +set tests [lsort [find $srcdir/$subdir *.d]] + +# Main loop. +dg-runtest $tests "" $DEFAULT_DFLAGS + +# All done. +dg-finish diff --git a/libphobos/testsuite/libphobos.hash/test_hash.d b/libphobos/testsuite/libphobos.hash/test_hash.d new file mode 100644 index 00000000000..5229c842cdf --- /dev/null +++ b/libphobos/testsuite/libphobos.hash/test_hash.d @@ -0,0 +1,540 @@ +void main() +{ + issue19562(); + issue15111(); + issues16654And16764(); + issue18918(); + issue18925(); + issue19005(); + issue19204(); + issue19262(); + issue19568(); + issue19582(); + testTypeInfoArrayGetHash1(); + testTypeInfoArrayGetHash2(); + pr2243(); +} + +/// Check hashOf an array of void pointers or delegates is @safe. +void issue19562() @nogc nothrow pure @safe +{ + void*[10] val; + size_t h = hashOf(val[]); + + alias D = void delegate(); + D[10] ds; + h = hashOf(ds[]); +} + +/// hashOf was failing for structs that had an `alias this` to a dynamic array. +void issue15111() +{ + void testAlias(T)() + { + static struct Foo + { + T t; + alias t this; + } + Foo foo; + static assert(is(typeof(hashOf(foo)))); + } + // was fixed + testAlias!(int[]); + testAlias!(int*); + // was not affected + testAlias!int; + testAlias!(void delegate()); + testAlias!(string[string]); + testAlias!(int[8]); +} + +void issues16654And16764() +{ + auto a = [1]; + auto b = a.dup; + assert(hashOf(a) == hashOf(b)); +} + +/// Check hashOf dynamic array of scalars is usable in @safe code. +void issue18918() nothrow pure @safe +{ + const _ = (() @nogc => hashOf("abc"))(); + + static struct S { string array; } + auto s1 = S("abc"); + auto s2 = S(s1.array.idup); + assert(hashOf(s1) == hashOf(s2)); + enum e = hashOf(S("abc")); + assert(hashOf(s1) == e); +} + +/// Check hashOf struct of scalar fields is usable in @safe code. +void issue18925() @nogc nothrow pure @safe +{ + + static struct S { int a; int b; } + auto h = hashOf(S.init); +} + +void issue19005() @nogc nothrow pure @safe +{ + enum Month : ubyte + { + jan = 1 + } + static struct Date + { + short _year; + Month _month; + ubyte _day; + } + Date date; + auto hash = date.hashOf; +} + +/// Accept SIMD vectors. +void issue19204() @nogc nothrow pure @safe +{ + version (D_SIMD) + { + static import simd = core.simd; + static if (is(simd.int4)) // __traits(isArithmetic) + {{ + enum simd.int4 val = [1,2,3,4]; + enum ctfeHash = hashOf(val); + simd.int4 rtVal = val; + auto rtHash = hashOf(rtVal); + assert(ctfeHash == rtHash); + }} + static if (is(simd.void16)) // non __traits(isArithmetic) + {{ + auto h = hashOf(simd.void16.init); + }} + static if (is(simd.float4)) // __traits(isArithmetic) and __traits(isFloating) + {{ + enum simd.float4 val = [1.1f, 2.2f, 3.3f, 4.4f]; + enum ctfeHash = hashOf(val); + simd.float4 rtVal = val; + auto rtHash = hashOf(rtVal); + assert(ctfeHash == rtHash); + }} + } +} + +/// hashOf associative array should infer nothrow +void issue19262() nothrow +{ + int[int] aa; + auto h = hashOf(aa); + h = hashOf(aa, h); +} + +/// hashOf should not unnecessarily call a struct's fields' postblits & dtors in CTFE +void issue19568() +{ + static struct S1 + { + @disable this(this); + + ~this() @nogc nothrow + { + import core.stdc.stdio; + if (mptr) puts("impure"); + } + + size_t[2] pad; + void* mptr; + } + + static struct S2 + { + @disable this(this); + + ~this() @nogc nothrow + { + import core.stdc.stdio; + if (fd != -1) puts("impure"); + } + + int fd = -1; + S1 s1; + } + + static struct S3 + { + private S2 s2; + } + + S3 s3; + size_t h = ((ref S3 s3) pure => hashOf(s3))(s3); +} + +/// Check core.internal.convert.toUbyte in CTFE for arrays works with +/// reference type elements and doesn't call postblits/dtors. +void issue19582() +{ + import core.internal.convert : toUbyte; + final static class C : Object {} + enum b1 = (() @nogc nothrow pure @safe { C[10] o; return toUbyte(o[])[0]; })(); + + static struct S + { + int x; + @disable this(this); + ~this() @nogc nothrow + { + import core.stdc.stdio : puts; + if (x) puts("impure"); + } + } + enum b2 = () { + S[10] a; + return ((const S[] a) @nogc nothrow pure @safe => toUbyte(a))(a); + }(); +} + +/// Tests ensure TypeInfo_Array.getHash uses element hash functions instead +/// of hashing array data. +void testTypeInfoArrayGetHash1() +{ + class C + { + int i; + this(in int i) { this.i = i; } + override hash_t toHash() { return 0; } + } + C[] a1 = [new C(11)], a2 = [new C(12)]; + assert(typeid(C[]).getHash(&a1) == typeid(C[]).getHash(&a2)); +} + +/// ditto +void testTypeInfoArrayGetHash2() +{ + struct S + { + int i; + hash_t toHash() const @safe nothrow { return 0; } + } + S[] a1 = [S(11)], a2 = [S(12)]; + assert(typeid(S[]).getHash(&a1) == typeid(S[]).getHash(&a2)); +} + +/++ +Use the new `core.internal.hash.hashOf` in all `TypeInfo.getHash` instead of +the `old rt.util.hash.hashOf`. Also make `typeid(T).getHash(&val)` get the +same result as `hashOf(val)`. ++/ +void pr2243() +{ + static struct Foo + { + int a = 99; + float b = 4.0; + size_t toHash() const pure @safe nothrow + { + return a; + } + } + + static struct Bar + { + char c = 'x'; + int a = 99; + float b = 4.0; + void* d = null; + } + + static struct Boom + { + char c = 'M'; + int* a = null; + } + + static struct Plain + { + int a = 1; + int b = 2; + } + + interface IBoo + { + void boo(); + } + + static class Boo: IBoo + { + override void boo() + { + } + + override size_t toHash() + { + return 1; + } + } + + static struct Goo + { + size_t toHash() pure @safe nothrow + { + return 1; + } + } + + enum Gun: long + { + A = 99, + B = 17 + } + + enum double dexpr = 3.14; + enum float fexpr = 2.71; + enum wstring wsexpr = "abcdef"w; + enum string csexpr = "abcdef"; + enum int iexpr = 7; + enum long lexpr = 42; + enum int[2][3] saexpr = [[1, 2], [3, 4], [5, 6]]; + enum int[] daexpr = [7,8,9]; + enum Foo thsexpr = Foo(); + enum Bar vsexpr = Bar(); + enum int[int] aaexpr = [99:2, 12:6, 45:4]; + enum Gun eexpr = Gun.A; + enum cdouble cexpr = 7+4i; + enum Foo[] staexpr = [Foo(), Foo(), Foo()]; + enum Bar[] vsaexpr = [Bar(), Bar(), Bar()]; + enum realexpr = 7.88; + enum raexpr = [8.99L+86i, 3.12L+99i, 5.66L+12i]; + enum nullexpr = null; + enum plstr = Plain(); + enum plarrstr = [Plain(), Plain(), Plain()]; + //No CTFE: + Boom rstructexpr = Boom(); + Boom[] rstrarrexpr = [Boom(), Boom(), Boom()]; + int delegate() dgexpr = (){return 78;}; + void* ptrexpr = &dgexpr; + + + //CTFE hashes + enum h1 = dexpr.hashOf(); + enum h2 = fexpr.hashOf(); + enum h3 = wsexpr.hashOf(); + enum h4 = csexpr.hashOf(); + enum h5 = iexpr.hashOf(); + enum h6 = lexpr.hashOf(); + enum h7 = saexpr.hashOf(); + enum h8 = daexpr.hashOf(); + enum h9 = thsexpr.hashOf(); + enum h10 = vsexpr.hashOf(); + enum h11 = aaexpr.hashOf(); + enum h12 = eexpr.hashOf(); + enum h13 = cexpr.hashOf(); + enum h14 = hashOf(new Boo); + enum h15 = staexpr.hashOf(); + enum h16 = hashOf([new Boo, new Boo, new Boo]); + enum h17 = hashOf([cast(IBoo)new Boo, cast(IBoo)new Boo, cast(IBoo)new Boo]); + enum h18 = hashOf(cast(IBoo)new Boo); + enum h19 = vsaexpr.hashOf(); + enum h20 = hashOf(cast(Foo[3])staexpr); + + //BUG: cannot cast [Boo(), Boo(), Boo()][0] to object.Object at compile time + auto h21 = hashOf(cast(Boo[3])[new Boo, new Boo, new Boo]); + auto h22 = hashOf(cast(IBoo[3])[cast(IBoo)new Boo, cast(IBoo)new Boo, cast(IBoo)new Boo]); + enum h23 = hashOf(cast(Bar[3])vsaexpr); + + //NO CTFE (Compute, but don't check correctness): + auto h24 = rstructexpr.hashOf(); + auto h25 = rstrarrexpr.hashOf(); + auto h26 = dgexpr.hashOf(); + auto h27 = ptrexpr.hashOf(); + + enum h28 = realexpr.hashOf(); + enum h29 = raexpr.hashOf(); + enum h30 = nullexpr.hashOf(); + enum h31 = plstr.hashOf(); + enum h32 = plarrstr.hashOf(); + enum h33 = hashOf(cast(Plain[3])plarrstr); + + auto v1 = dexpr; + auto v2 = fexpr; + auto v3 = wsexpr; + auto v4 = csexpr; + auto v5 = iexpr; + auto v6 = lexpr; + auto v7 = saexpr; + auto v8 = daexpr; + auto v9 = thsexpr; + auto v10 = vsexpr; + auto v11 = aaexpr; + auto v12 = eexpr; + auto v13 = cexpr; + auto v14 = new Boo; + auto v15 = staexpr; + auto v16 = [new Boo, new Boo, new Boo]; + auto v17 = [cast(IBoo)new Boo, cast(IBoo)new Boo, cast(IBoo)new Boo]; + auto v18 = cast(IBoo)new Boo; + auto v19 = vsaexpr; + auto v20 = cast(Foo[3])staexpr; + auto v21 = cast(Boo[3])[new Boo, new Boo, new Boo]; + auto v22 = cast(IBoo[3])[cast(IBoo)new Boo, cast(IBoo)new Boo, cast(IBoo)new Boo]; + auto v23 = cast(Bar[3])vsaexpr; + auto v30 = null; + auto v31 = plstr; + auto v32 = plarrstr; + auto v33 = cast(Plain[3])plarrstr; + + //NO CTFE: + auto v24 = rstructexpr; + auto v25 = rstrarrexpr; + auto v26 = dgexpr; + auto v27 = ptrexpr; + auto v28 = realexpr; + auto v29 = raexpr; + + //runtime hashes + auto rth1 = hashOf(v1); + auto rth2 = hashOf(v2); + auto rth3 = hashOf(v3); + auto rth4 = hashOf(v4); + auto rth5 = hashOf(v5); + auto rth6 = hashOf(v6); + auto rth7 = hashOf(v7); + auto rth8 = hashOf(v8); + auto rth9 = hashOf(v9); + auto rth10 = hashOf(v10); + auto rth11 = hashOf(v11); + auto rth12 = hashOf(v12); + auto rth13 = hashOf(v13); + auto rth14 = hashOf(v14); + auto rth15 = hashOf(v15); + auto rth16 = hashOf(v16); + auto rth17 = hashOf(v17); + auto rth18 = hashOf(v18); + auto rth19 = hashOf(v19); + auto rth20 = hashOf(v20); + auto rth21 = hashOf(v21); + auto rth22 = hashOf(v22); + auto rth23 = hashOf(v23); + auto rth30 = hashOf(v30); + //NO CTFE: + auto rth24 = hashOf(v24); + auto rth25 = hashOf(v25); + auto rth26 = hashOf(v26); + auto rth27 = hashOf(v27); + auto rth28 = hashOf(v28); + auto rth29 = hashOf(v29); + + auto rth31 = hashOf(v31); + auto rth32 = hashOf(v32); + auto rth33 = hashOf(v33); + + assert(h1 == rth1); + assert(h2 == rth2); + assert(h3 == rth3); + assert(h4 == rth4); + assert(h5 == rth5); + assert(h6 == rth6); + assert(h7 == rth7); + assert(h8 == rth8); + assert(h9 == rth9); + assert(h10 == rth10); + assert(h11 == rth11); + assert(h12 == rth12); + assert(h13 == rth13); + assert(h14 == rth14); + assert(h15 == rth15); + assert(h16 == rth16); + assert(h17 == rth17); + assert(h18 == rth18); + assert(h19 == rth19); + assert(h20 == rth20); + assert(h21 == rth21); + assert(h22 == rth22); + assert(h23 == rth23); + /*assert(h24 == rth24); + assert(h25 == rth25); + assert(h26 == rth26); + assert(h27 == rth27); + assert(h28 == rth28); + assert(h29 == rth29);*/ + assert(h30 == rth30); + assert(h31 == rth31); + assert(h32 == rth32); + assert(h33 == rth33); + + // https://issues.dlang.org/show_bug.cgi?id=18932 + assert(hashOf(null, 0) != hashOf(null, 123456789)); + + static size_t tiHashOf(T)(T var) + { + return typeid(T).getHash(&var); + } + + auto tih1 = tiHashOf(v1); + auto tih2 = tiHashOf(v2); + auto tih3 = tiHashOf(v3); + auto tih4 = tiHashOf(v4); + auto tih5 = tiHashOf(v5); + auto tih6 = tiHashOf(v6); + auto tih7 = tiHashOf(v7); + auto tih8 = tiHashOf(v8); + auto tih9 = tiHashOf(v9); + auto tih10 = tiHashOf(v10); + auto tih11 = tiHashOf(v11); + auto tih12 = tiHashOf(v12); + auto tih13 = tiHashOf(v13); + auto tih14 = tiHashOf(v14); + auto tih15 = tiHashOf(v15); + auto tih16 = tiHashOf(v16); + auto tih17 = tiHashOf(v17); + auto tih18 = tiHashOf(v18); + auto tih19 = tiHashOf(v19); + auto tih20 = tiHashOf(v20); + auto tih21 = tiHashOf(v21); + auto tih22 = tiHashOf(v22); + auto tih23 = tiHashOf(v23); + auto tih24 = tiHashOf(v24); + auto tih25 = tiHashOf(v25); + auto tih26 = tiHashOf(v26); + auto tih27 = tiHashOf(v27); + auto tih28 = tiHashOf(v28); + auto tih29 = tiHashOf(v29); + auto tih30 = tiHashOf(v30); + auto tih31 = tiHashOf(v31); + auto tih32 = tiHashOf(v32); + auto tih33 = tiHashOf(v33); + + assert(tih1 == rth1); + assert(tih2 == rth2); + assert(tih3 == rth3); + assert(tih4 == rth4); + assert(tih5 == rth5); + assert(tih6 == rth6); + assert(tih7 == rth7); + assert(tih8 == rth8); + assert(tih9 == rth9); + //assert(tih10 == rth10); // need compiler-generated __xtoHash changes + assert(tih11 == rth11); + assert(tih12 == rth12); + assert(tih13 == rth13); + assert(tih14 == rth14); + assert(tih15 == rth15); + assert(tih16 == rth16); + assert(tih17 == rth17); + assert(tih18 == rth18); + //assert(tih19 == rth19); // need compiler-generated __xtoHash changes + assert(tih20 == rth20); + assert(tih21 == rth21); + assert(tih22 == rth22); + //assert(tih23 == rth23); // need compiler-generated __xtoHash changes + //assert(tih24 == rth24); + //assert(tih25 == rth25); + assert(tih26 == rth26); + assert(tih27 == rth27); + assert(tih28 == rth28); + //assert(tih29 == rth29); // XGDC: Implementation wrongly hashes padding. + assert(tih30 == rth30); + assert(tih31 == rth31); + assert(tih32 == rth32); + assert(tih33 == rth33); +} |