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

   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 auto __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))
  94         static @trusted ref inout(ubyte) at(inout(void)[] r, size_t i) { return (cast(inout(ubyte)*) r.ptr)[i]; }
  95     else
  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 {
 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 {
 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 {
 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
 227     bool less1(immutable size_t[][] a, size_t[][] b) { return a < b; }
 228     bool less2(const void[][] a, void[][] b) { return a < 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
 241 // custom aggregate types
 242 @safe unittest
 243 {
 244     // https://issues.dlang.org/show_bug.cgi?id=24044
 245     // Support float opCmp(...) with array
 246     static struct F
 247     {
 248         float f;
 249         float opCmp(F other) const { return this.f - other.f; }
 250     }
 251
 252     F[2] a = [F(1.0f), F(float.nan)];
 253     F[2] b = [F(1.0f), F(1.0f)];
 254     F[1] c = [F(1.0f)];
 255
 256     bool isNan(float f) { return f != f; }
 257
 258     assert(isNan(__cmp(a, b)));
 259     assert(isNan(__cmp(a, a)));
 260     assert(__cmp(b, b) == 0);
 261     assert(__cmp(a, c) > 0);
 262 }