xref: /netbsd-src/external/gpl3/gcc/dist/libphobos/libdruntime/core/internal/array/comparison.d (revision 0a3071956a3a9fdebdbf7f338cf2d439b45fc728) 
1 /**
2  * This module contains compiler support for comparing dynamic arrays
3  *
4  * Copyright: Copyright Digital Mars 2000 - 2019.
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/_comparison.d)
9  */
10 
11 module core.internal.array.comparison;
12 
13 int __cmp(T)(scope const T[] lhs, scope const T[] rhs) @trusted
14     if (__traits(isScalar, T))
15 {
16     // Compute U as the implementation type for T
17     static if (is(T == ubyte) || is(T == void) || is(T == bool))
18         alias U = char;
19     else static if (is(T == wchar))
20         alias U = ushort;
21     else static if (is(T == dchar))
22         alias U = uint;
23     else static if (is(T == ifloat))
24         alias U = float;
25     else static if (is(T == idouble))
26         alias U = double;
27     else static if (is(T == ireal))
28         alias U = real;
29     else
30         alias U = T;
31 
32     static if (is(U == char))
33     {
34         import core.internal.string : dstrcmp;
35         return dstrcmp(cast(char[]) lhs, cast(char[]) rhs);
36     }
37     else static if (!is(U == T))
38     {
39         // Reuse another implementation
40         return __cmp(cast(U[]) lhs, cast(U[]) rhs);
41     }
42     else
43     {
44         version (BigEndian)
45         static if (__traits(isUnsigned, T) ? !is(T == __vector) : is(T : P*, P))
46         {
47             if (!__ctfe)
48             {
49                 import core.stdc.string : memcmp;
50                 int c = memcmp(lhs.ptr, rhs.ptr, (lhs.length <= rhs.length ? lhs.length : rhs.length) * T.sizeof);
51                 if (c)
52                     return c;
53                 static if (size_t.sizeof <= uint.sizeof && T.sizeof >= 2)
54                     return cast(int) lhs.length - cast(int) rhs.length;
55                 else
56                     return int(lhs.length > rhs.length) - int(lhs.length < rhs.length);
57             }
58         }
59 
60         immutable len = lhs.length <= rhs.length ? lhs.length : rhs.length;
61         foreach (const u; 0 .. len)
62         {
63             auto a = lhs.ptr[u], b = rhs.ptr[u];
64             static if (is(T : creal))
65             {
66                 // Use rt.cmath2._Ccmp instead ?
67                 // Also: if NaN is present, numbers will appear equal.
68                 auto r = (a.re > b.re) - (a.re < b.re);
69                 if (!r) r = (a.im > b.im) - (a.im < b.im);
70             }
71             else
72             {
73                 // This pattern for three-way comparison is better than conditional operators
74                 // See e.g. https://godbolt.org/z/3j4vh1
75                 const r = (a > b) - (a < b);
76             }
77             if (r) return r;
78         }
79         return (lhs.length > rhs.length) - (lhs.length < rhs.length);
80     }
81 }
82 
83 // This function is called by the compiler when dealing with array
84 // comparisons in the semantic analysis phase of CmpExp. The ordering
85 // comparison is lowered to a call to this template.
86 int __cmp(T1, T2)(T1[] s1, T2[] s2)
87 if (!__traits(isScalar, T1) && !__traits(isScalar, T2))
88 {
89     import core.internal.traits : Unqual;
90     alias U1 = Unqual!T1;
91     alias U2 = Unqual!T2;
92 
93     static if (is(U1 == void) && is(U2 == void))
inout(ubyte)94         static @trusted ref inout(ubyte) at(inout(void)[] r, size_t i) { return (cast(inout(ubyte)*) r.ptr)[i]; }
95     else
at(R)96         static @trusted ref R at(R)(R[] r, size_t i) { return r.ptr[i]; }
97 
98     // All unsigned byte-wide types = > dstrcmp
99     immutable len = s1.length <= s2.length ? s1.length : s2.length;
100 
101     foreach (const u; 0 .. len)
102     {
103         static if (__traits(compiles, __cmp(at(s1, u), at(s2, u))))
104         {
105             auto c = __cmp(at(s1, u), at(s2, u));
106             if (c != 0)
107                 return c;
108         }
109         else static if (__traits(compiles, at(s1, u).opCmp(at(s2, u))))
110         {
111             auto c = at(s1, u).opCmp(at(s2, u));
112             if (c != 0)
113                 return c;
114         }
115         else static if (__traits(compiles, at(s1, u) < at(s2, u)))
116         {
117             if (int result = (at(s1, u) > at(s2, u)) - (at(s1, u) < at(s2, u)))
118                 return result;
119         }
120         else
121         {
122             // TODO: fix this legacy bad behavior, see
123             // https://issues.dlang.org/show_bug.cgi?id=17244
124             static assert(is(U1 == U2), "Internal error.");
125             import core.stdc.string : memcmp;
126             auto c = (() @trusted => memcmp(&at(s1, u), &at(s2, u), U1.sizeof))();
127             if (c != 0)
128                 return c;
129         }
130     }
131     return (s1.length > s2.length) - (s1.length < s2.length);
132 }
133 
134 // integral types
135 @safe unittest
136 {
compareMinMax(T)137     void compareMinMax(T)()
138     {
139         T[2] a = [T.max, T.max];
140         T[2] b = [T.min, T.min];
141 
142         assert(__cmp(a, b) > 0);
143         assert(__cmp(b, a) < 0);
144     }
145 
146     compareMinMax!int;
147     compareMinMax!uint;
148     compareMinMax!long;
149     compareMinMax!ulong;
150     compareMinMax!short;
151     compareMinMax!ushort;
152     compareMinMax!byte;
153     compareMinMax!dchar;
154     compareMinMax!wchar;
155 }
156 
157 // char types (dstrcmp)
158 @safe unittest
159 {
compareMinMax(T)160     void compareMinMax(T)()
161     {
162         T[2] a = [T.max, T.max];
163         T[2] b = [T.min, T.min];
164 
165         assert(__cmp(a, b) > 0);
166         assert(__cmp(b, a) < 0);
167     }
168 
169     compareMinMax!ubyte;
170     compareMinMax!bool;
171     compareMinMax!char;
172     compareMinMax!(const char);
173 
174     string s1 = "aaaa";
175     string s2 = "bbbb";
176     assert(__cmp(s2, s1) > 0);
177     assert(__cmp(s1, s2) < 0);
178 }
179 
180 // fp types
181 @safe unittest
182 {
compareMinMax(T)183     void compareMinMax(T)()
184     {
185         T[2] a = [T.max, T.max];
186         T[2] b = [T.min_normal, T.min_normal];
187         T[2] c = [T.max, T.min_normal];
188         T[1] d = [T.max];
189 
190         assert(__cmp(a, b) > 0);
191         assert(__cmp(b, a) < 0);
192         assert(__cmp(a, c) > 0);
193         assert(__cmp(a, d) > 0);
194         assert(__cmp(d, c) < 0);
195         assert(__cmp(c, c) == 0);
196     }
197 
198     compareMinMax!real;
199     compareMinMax!float;
200     compareMinMax!double;
201 
202     // qualifiers
203     compareMinMax!(const real);
204     compareMinMax!(immutable real);
205 }
206 
207 // void[]
208 @safe unittest
209 {
210     void[] a;
211     const(void)[] b;
212 
213     (() @trusted
214     {
215         a = cast(void[]) "bb";
216         b = cast(const(void)[]) "aa";
217     })();
218 
219     assert(__cmp(a, b) > 0);
220     assert(__cmp(b, a) < 0);
221 }
222 
223 // arrays of arrays with mixed modifiers
224 @safe unittest
225 {
226     // https://issues.dlang.org/show_bug.cgi?id=17876
less1(immutable size_t[][]a,size_t[][]b)227     bool less1(immutable size_t[][] a, size_t[][] b) { return a < b; }
less2(const void[][]a,void[][]b)228     bool less2(const void[][] a, void[][] b) { return a < b; }
less3(inout size_t[][]a,size_t[][]b)229     bool less3(inout size_t[][] a, size_t[][] b) { return a < b; }
230 
231     immutable size_t[][] a = [[1, 2], [3, 4]];
232     size_t[][] b = [[1, 2], [3, 5]];
233     assert(less1(a, b));
234     assert(less3(a, b));
235 
236     auto va = [cast(immutable void[])a[0], a[1]];
237     auto vb = [cast(void[])b[0], b[1]];
238     assert(less2(va, vb));
239 }
240