From patchwork Sun Feb 10 21:02:50 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Iain Buclaw X-Patchwork-Id: 1039491 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-495748-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=gdcproject.org Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="vcXah9Qu"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 43yLxD5wCMz9s5c for ; Mon, 11 Feb 2019 08:03:28 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:from:date:message-id:subject:to:content-type; q= dns; s=default; b=MK6GuCj2EL8ZcLu/3vXWCnClXeJbeWe0WD5wl8GszWSi2L x07BI/v9i1AOoxotW0lV1fRDNE23Krp47K+bRhaf+aEqI3nSTIMt1Le3YC51/SDX s3B59xmzp0Z4Jw9NC6yKRvBcBpSq8YdmyUVCyFEGJMoMAOwAeKUBGNPv5OZr8= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:from:date:message-id:subject:to:content-type; s= default; bh=/pgfwQqCNMRVTE5FsgHbvrsZlHQ=; b=vcXah9QuSUld7naDvHor YVA13Tg6yNuyrsMTQItcUFT7zz+pnAUTC0LHlJjkJUIZlJe7CLLK7VFHgOewCNSs 6QvMY2itp+y4MrilCo+s0FfPVBRDeNwQIzuhzRKLsxRiIsqxHc1wasPPyc0KEZqz 0AXnr4RqzaZVr0PpdeprSqk= Received: (qmail 100933 invoked by alias); 10 Feb 2019 21:03:15 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 100923 invoked by uid 89); 10 Feb 2019 21:03:15 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, FREEMAIL_FROM, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS, TIME_LIMIT_EXCEEDED autolearn=unavailable version=3.3.2 spammy=data!, moreover, trusted, Month X-HELO: mail-qt1-f170.google.com Received: from mail-qt1-f170.google.com (HELO mail-qt1-f170.google.com) (209.85.160.170) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 10 Feb 2019 21:03:04 +0000 Received: by mail-qt1-f170.google.com with SMTP id b8so10032863qtr.9 for ; Sun, 10 Feb 2019 13:03:04 -0800 (PST) MIME-Version: 1.0 From: Iain Buclaw Date: Sun, 10 Feb 2019 22:02:50 +0100 Message-ID: Subject: [PATCH, libphobos] Committed backport internal.hash from upstream To: gcc-patches X-IsSubscribed: yes Hi, This patch is a backport of the internal associative array/hash implementation from druntime version 2.084. This being a prerequisite to an earlier patch sent on this mailing list to fix hashing of complex reals, the original did an incomplete backport of upstream - just enough to make things pass. This instead directly applies all changes so there's no deviation when it comes to merging latter versions of the druntime library. Bootstrapped and tested on x86_64-linux-gnu. Committed to trunk as r268754. 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 +# . + +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 +# . + +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); +}