1 /**
2 * This module contains compiler support determining equality of arrays.
3 *
4 * Copyright: Copyright Digital Mars 2000 - 2020.
5 * License: Distributed under the
6 * $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0).
7 * (See accompanying file LICENSE)
8 * Source: $(DRUNTIMESRC core/internal/_array/_equality.d)
9 */
10
11 module core.internal.array.equality;
12
13 // The compiler lowers `lhs == rhs` to `__equals(lhs, rhs)` for
14 // * dynamic arrays,
15 // * (most) arrays of different (unqualified) element types, and
16 // * arrays of structs with custom opEquals.
17
18 // The scalar-only overload takes advantage of known properties of scalars to
19 // reduce template instantiation. This is expected to be the most common case.
20 bool __equals(T1, T2)(scope const T1[] lhs, scope const T2[] rhs)
21 @nogc nothrow pure @trusted
22 if (__traits(isScalar, T1) && __traits(isScalar, T2))
23 {
24 if (lhs.length != rhs.length)
25 return false;
26
27 static if (T1.sizeof == T2.sizeof
28 // Signedness needs to match for types that promote to int.
29 // (Actually it would be okay to memcmp bool[] and byte[] but that is
30 // probably too uncommon to be worth checking for.)
31 && (T1.sizeof >= 4 || __traits(isUnsigned, T1) == __traits(isUnsigned, T2))
32 && !__traits(isFloating, T1) && !__traits(isFloating, T2))
33 {
34 if (!__ctfe)
35 {
36 // This would improperly allow equality of integers and pointers
37 // but the CTFE branch will stop this function from compiling then.
38 import core.stdc.string : memcmp;
39 return lhs.length == 0 ||
40 0 == memcmp(cast(const void*) lhs.ptr, cast(const void*) rhs.ptr, lhs.length * T1.sizeof);
41 }
42 }
43
44 foreach (const i; 0 .. lhs.length)
45 if (lhs.ptr[i] != rhs.ptr[i])
46 return false;
47 return true;
48 }
49
50 bool __equals(T1, T2)(scope T1[] lhs, scope T2[] rhs)
51 if (!__traits(isScalar, T1) || !__traits(isScalar, T2))
52 {
53 if (lhs.length != rhs.length)
54 return false;
55
56 if (lhs.length == 0)
57 return true;
58
59 static if (useMemcmp!(T1, T2))
60 {
61 if (!__ctfe)
62 {
trustedMemcmp(scope T1[]lhs,scope T2[]rhs)63 static bool trustedMemcmp(scope T1[] lhs, scope T2[] rhs) @trusted @nogc nothrow pure
64 {
65 pragma(inline, true);
66 import core.stdc.string : memcmp;
67 return memcmp(cast(void*) lhs.ptr, cast(void*) rhs.ptr, lhs.length * T1.sizeof) == 0;
68 }
69 return trustedMemcmp(lhs, rhs);
70 }
71 else
72 {
73 foreach (const i; 0 .. lhs.length)
74 {
75 if (at(lhs, i) != at(rhs, i))
76 return false;
77 }
78 return true;
79 }
80 }
81 else
82 {
83 foreach (const i; 0 .. lhs.length)
84 {
85 if (at(lhs, i) != at(rhs, i))
86 return false;
87 }
88 return true;
89 }
90 }
91
92 @safe unittest
93 {
94 assert(__equals([], []));
95 assert(!__equals([1, 2], [1, 2, 3]));
96 }
97
98 @safe unittest
99 {
100 auto a = "hello"c;
101
102 assert(a != "hel");
103 assert(a != "helloo");
104 assert(a != "betty");
105 assert(a == "hello");
106 assert(a != "hxxxx");
107
108 float[] fa = [float.nan];
109 assert(fa != fa);
110 }
111
112 @safe unittest
113 {
114 struct A
115 {
116 int a;
117 }
118
119 auto arr1 = [A(0), A(2)];
120 auto arr2 = [A(0), A(1)];
121 auto arr3 = [A(0), A(1)];
122
123 assert(arr1 != arr2);
124 assert(arr2 == arr3);
125 }
126
127 @safe unittest
128 {
129 struct A
130 {
131 int a;
132 int b;
133
opEqualsA134 bool opEquals(const A other)
135 {
136 return this.a == other.b && this.b == other.a;
137 }
138 }
139
140 auto arr1 = [A(1, 0), A(0, 1)];
141 auto arr2 = [A(1, 0), A(0, 1)];
142 auto arr3 = [A(0, 1), A(1, 0)];
143
144 assert(arr1 != arr2);
145 assert(arr2 == arr3);
146 }
147
148 // https://issues.dlang.org/show_bug.cgi?id=18252
149 @safe unittest
150 {
151 string[int][] a1, a2;
152 assert(__equals(a1, a2));
153 assert(a1 == a2);
154 a1 ~= [0: "zero"];
155 a2 ~= [0: "zero"];
156 assert(__equals(a1, a2));
157 assert(a1 == a2);
158 a2[0][1] = "one";
159 assert(!__equals(a1, a2));
160 assert(a1 != a2);
161 }
162
163
164 private:
165
166 // - Recursively folds static array types to their element type,
167 // - maps void to ubyte, and
168 // - pointers to size_t.
BaseType(T)169 template BaseType(T)
170 {
171 static if (__traits(isStaticArray, T))
172 alias BaseType = BaseType!(typeof(T.init[0]));
173 else static if (is(immutable T == immutable void))
174 alias BaseType = ubyte;
175 else static if (is(T == E*, E))
176 alias BaseType = size_t;
177 else
178 alias BaseType = T;
179 }
180
181 // Use memcmp if the element sizes match and both base element types are integral.
182 // Due to int promotion, disallow small integers of diverging signed-ness though.
useMemcmp(T1,T2)183 template useMemcmp(T1, T2)
184 {
185 static if (T1.sizeof != T2.sizeof)
186 enum useMemcmp = false;
187 else
188 {
189 alias B1 = BaseType!T1;
190 alias B2 = BaseType!T2;
191 enum useMemcmp = __traits(isIntegral, B1) && __traits(isIntegral, B2)
192 && !( (B1.sizeof < 4 || B2.sizeof < 4) && __traits(isUnsigned, B1) != __traits(isUnsigned, B2) );
193 }
194 }
195
196 unittest
197 {
198 enum E { foo, bar }
199
200 static assert(useMemcmp!(byte, byte));
201 static assert(useMemcmp!(ubyte, ubyte));
202 static assert(useMemcmp!(void, const void));
203 static assert(useMemcmp!(void, immutable bool));
204 static assert(useMemcmp!(void, inout char));
205 static assert(useMemcmp!(void, shared ubyte));
206 static assert(!useMemcmp!(void, byte)); // differing signed-ness
207 static assert(!useMemcmp!(char[8], byte[8])); // ditto
208
209 static assert(useMemcmp!(short, short));
210 static assert(useMemcmp!(wchar, ushort));
211 static assert(!useMemcmp!(wchar, short)); // differing signed-ness
212
213 static assert(useMemcmp!(int, uint)); // no promotion, ignoring signed-ness
214 static assert(useMemcmp!(dchar, E));
215
216 static assert(useMemcmp!(immutable void*, size_t));
217 static assert(useMemcmp!(double*, ptrdiff_t));
218 static assert(useMemcmp!(long[2][3], const(ulong)[2][3]));
219
220 static assert(!useMemcmp!(float, float));
221 static assert(!useMemcmp!(double[2], double[2]));
222 static assert(!useMemcmp!(Object, Object));
223 static assert(!useMemcmp!(int[], int[]));
224 }
225
226 // Returns a reference to an array element, eliding bounds check and
227 // casting void to ubyte.
228 pragma(inline, true)
229 ref at(T)(T[] r, size_t i) @trusted
230 // exclude opaque structs due to https://issues.dlang.org/show_bug.cgi?id=20959
231 if (!(is(T == struct) && !is(typeof(T.sizeof))))
232 {
233 static if (is(immutable T == immutable void))
234 return (cast(ubyte*) r.ptr)[i];
235 else
236 return r.ptr[i];
237 }
238