1/**
2 This module contains support array (vector) operations
3  Copyright: Copyright Digital Mars 2000 - 2019.
4  License: Distributed under the
5       $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0).
6     (See accompanying file LICENSE)
7  Source: $(DRUNTIMESRC core/_internal/_array/_operations.d)
8*/
9module core.internal.array.operations;
10import core.internal.traits : Filter, staticMap, Unqual;
11
12version (GNU) version = GNU_OR_LDC;
13version (LDC) version = GNU_OR_LDC;
14
15/**
16 * Perform array (vector) operations and store the result in `res`.  Operand
17 * types and operations are passed as template arguments in Reverse Polish
18 * Notation (RPN).
19
20 * Operands can be slices or scalar types. The element types of all
21 * slices and all scalar types must be implicitly convertible to `T`.
22 *
23 * Operations are encoded as strings, e.g. `"+"`, `"%"`, `"*="`. Unary
24 * operations are prefixed with "u", e.g. `"u-"`, `"u~"`. Only the last
25 * operation can and must be an assignment (`"="`) or op-assignment (`"op="`).
26 *
27 * All slice operands must have the same length as the result slice.
28 *
29 * Params: T[] = type of result slice
30 *        Args = operand types and operations in RPN
31 *         res = the slice in which to store the results
32 *        args = operand values
33 *
34 * Returns: the slice containing the result
35 */
36T[] arrayOp(T : T[], Args...)(T[] res, Filter!(isType, Args) args) @trusted @nogc pure nothrow
37{
38    alias scalarizedExp = staticMap!(toElementType, Args);
39    alias check = typeCheck!(true, T, scalarizedExp); // must support all scalar ops
40
41    foreach (argsIdx, arg; typeof(args))
42    {
43        static if (is(arg == U[], U))
44        {
45            assert(res.length == args[argsIdx].length, "Mismatched array lengths for vector operation");
46        }
47    }
48
49    size_t pos;
50    static if (vectorizeable!(T[], Args))
51    {
52        alias vec = .vec!T;
53        alias load = .load!(T, vec.length);
54        alias store = .store!(T, vec.length);
55
56        // Given that there are at most as many scalars broadcast as there are
57        // operations in any `ary[] = ary[] op const op const`, it should always be
58        // worthwhile to choose vector operations.
59        if (!__ctfe && res.length >= vec.length)
60        {
61            mixin(initScalarVecs!Args);
62
63            auto n = res.length / vec.length;
64            do
65            {
66                mixin(vectorExp!Args ~ ";");
67                pos += vec.length;
68            }
69            while (--n);
70        }
71    }
72    for (; pos < res.length; ++pos)
73        mixin(scalarExp!Args ~ ";");
74
75    return res;
76}
77
78private:
79
80// SIMD helpers
81
82version (DigitalMars)
83{
84    import core.simd;
85
86    template vec(T)
87    {
88        enum regsz = 16; // SSE2
89        enum N = regsz / T.sizeof;
90        alias vec = __vector(T[N]);
91    }
92
93    void store(T, size_t N)(T* p, const scope __vector(T[N]) val)
94    {
95        pragma(inline, true);
96        alias vec = __vector(T[N]);
97
98        static if (is(T == float))
99            cast(void) __simd_sto(XMM.STOUPS, *cast(vec*) p, val);
100        else static if (is(T == double))
101            cast(void) __simd_sto(XMM.STOUPD, *cast(vec*) p, val);
102        else
103            cast(void) __simd_sto(XMM.STODQU, *cast(vec*) p, val);
104    }
105
106    const(__vector(T[N])) load(T, size_t N)(const scope T* p)
107    {
108        import core.simd;
109
110        pragma(inline, true);
111        alias vec = __vector(T[N]);
112
113        static if (is(T == float))
114            return cast(typeof(return)) __simd(XMM.LODUPS, *cast(const vec*) p);
115        else static if (is(T == double))
116            return cast(typeof(return)) __simd(XMM.LODUPD, *cast(const vec*) p);
117        else
118            return cast(typeof(return)) __simd(XMM.LODDQU, *cast(const vec*) p);
119    }
120
121    __vector(T[N]) binop(string op, T, size_t N)(const scope __vector(T[N]) a, const scope __vector(T[N]) b)
122    {
123        pragma(inline, true);
124        return mixin("a " ~ op ~ " b");
125    }
126
127    __vector(T[N]) unaop(string op, T, size_t N)(const scope __vector(T[N]) a)
128            if (op[0] == 'u')
129    {
130        pragma(inline, true);
131        return mixin(op[1 .. $] ~ "a");
132    }
133}
134
135// mixin gen
136
137/**
138Check whether operations on operand types are supported.  This
139template recursively reduces the expression tree and determines
140intermediate types.
141Type checking is done here rather than in the compiler to provide more
142detailed error messages.
143
144Params:
145    fail = whether to fail (static assert) with a human-friendly error message
146       T = type of result
147    Args = operand types and operations in RPN
148Returns:
149    The resulting type of the expression
150See_Also:
151    $(LREF arrayOp)
152*/
153template typeCheck(bool fail, T, Args...)
154{
155    enum idx = staticIndexOf!(not!isType, Args);
156    static if (isUnaryOp(Args[idx]))
157    {
158        alias UT = Args[idx - 1];
159        enum op = Args[idx][1 .. $];
160        static if (is(typeof((UT a) => mixin(op ~ "cast(int) a")) RT == return))
161            alias typeCheck = typeCheck!(fail, T, Args[0 .. idx - 1], RT, Args[idx + 1 .. $]);
162        else static if (fail)
163            static assert(0, "Unary `" ~ op ~ "` not supported for type `" ~ UT.stringof ~ "`.");
164    }
165    else static if (isBinaryOp(Args[idx]))
166    {
167        alias LHT = Args[idx - 2];
168        alias RHT = Args[idx - 1];
169        enum op = Args[idx];
170        static if (is(typeof((LHT a, RHT b) => mixin("a " ~ op ~ " b")) RT == return))
171            alias typeCheck = typeCheck!(fail, T, Args[0 .. idx - 2], RT, Args[idx + 1 .. $]);
172        else static if (fail)
173            static assert(0,
174                    "Binary `" ~ op ~ "` not supported for types `"
175                    ~ LHT.stringof ~ "` and `" ~ RHT.stringof ~ "`.");
176    }
177    else static if (Args[idx] == "=" || isBinaryAssignOp(Args[idx]))
178    {
179        alias RHT = Args[idx - 1];
180        enum op = Args[idx];
181        static if (is(T == __vector(ET[N]), ET, size_t N))
182        {
183            // no `cast(T)` before assignment for vectors
184            static if (is(typeof((T res, RHT b) => mixin("res " ~ op ~ " b")) RT == return)
185                    && // workaround https://issues.dlang.org/show_bug.cgi?id=17758
186                    (op != "=" || is(Unqual!T == Unqual!RHT)))
187                alias typeCheck = typeCheck!(fail, T, Args[0 .. idx - 1], RT, Args[idx + 1 .. $]);
188            else static if (fail)
189                static assert(0,
190                        "Binary op `" ~ op ~ "` not supported for types `"
191                        ~ T.stringof ~ "` and `" ~ RHT.stringof ~ "`.");
192        }
193        else
194        {
195            static if (is(typeof((RHT b) => mixin("cast(T) b"))))
196            {
197                static if (is(typeof((T res, T b) => mixin("res " ~ op ~ " b")) RT == return))
198                    alias typeCheck = typeCheck!(fail, T, Args[0 .. idx - 1], RT, Args[idx + 1 .. $]);
199                else static if (fail)
200                    static assert(0,
201                            "Binary op `" ~ op ~ "` not supported for types `"
202                            ~ T.stringof ~ "` and `" ~ T.stringof ~ "`.");
203            }
204            else static if (fail)
205                static assert(0,
206                        "`cast(" ~ T.stringof ~ ")` not supported for type `" ~ RHT.stringof ~ "`.");
207        }
208    }
209    else
210        static assert(0);
211}
212/// ditto
213template typeCheck(bool fail, T, ResultType)
214{
215    alias typeCheck = ResultType;
216}
217
218version (GNU_OR_LDC)
219{
220    // leave it to the auto-vectorizer
221    enum vectorizeable(E : E[], Args...) = false;
222}
223else
224{
225    // check whether arrayOp is vectorizable
226    template vectorizeable(E : E[], Args...)
227    {
228        static if (is(vec!E))
229        {
230            // type check with vector types
231            enum vectorizeable = is(typeCheck!(false, vec!E, staticMap!(toVecType, Args)));
232        }
233        else
234            enum vectorizeable = false;
235    }
236
237    version (X86_64) unittest
238    {
239        static assert(vectorizeable!(double[], const(double)[], double[], "+", "="));
240        static assert(!vectorizeable!(double[], const(ulong)[], double[], "+", "="));
241        // Vector type are (atm.) not implicitly convertible and would require
242        // lots of SIMD intrinsics. Therefor leave mixed type array ops to
243        // GDC/LDC's auto-vectorizers.
244        static assert(!vectorizeable!(double[], const(uint)[], uint, "+", "="));
245    }
246}
247
248bool isUnaryOp(scope string op) pure nothrow @safe @nogc
249{
250    return op[0] == 'u';
251}
252
253bool isBinaryOp(scope string op) pure nothrow @safe @nogc
254{
255    if (op == "^^")
256        return true;
257    if (op.length != 1)
258        return false;
259    switch (op[0])
260    {
261    case '+', '-', '*', '/', '%', '|', '&', '^':
262        return true;
263    default:
264        return false;
265    }
266}
267
268bool isBinaryAssignOp(string op)
269{
270    return op.length >= 2 && op[$ - 1] == '=' && isBinaryOp(op[0 .. $ - 1]);
271}
272
273// Generate mixin expression to perform scalar arrayOp loop expression, assumes
274// `pos` to be the current slice index, `args` to contain operand values, and
275// `res` the target slice.
276enum scalarExp(Args...) =
277(){
278    string[] stack;
279    size_t argsIdx;
280
281    static if (is(Args[0] == U[], U))
282        alias Type = U;
283    else
284        alias Type = Args[0];
285
286    foreach (i, arg; Args)
287    {
288        static if (is(arg == T[], T))
289            stack ~= "args[" ~ argsIdx++.toString ~ "][pos]";
290        else static if (is(arg))
291            stack ~= "args[" ~ argsIdx++.toString ~ "]";
292        else static if (isUnaryOp(arg))
293        {
294            auto op = arg[0] == 'u' ? arg[1 .. $] : arg;
295            // Explicitly use the old integral promotion rules
296            // See also: https://dlang.org/changelog/2.078.0.html#fix16997
297            static if (is(Type : int))
298                stack[$ - 1] = "cast(typeof(" ~ stack[$ -1] ~ "))" ~ op ~ "cast(int)("~ stack[$ - 1] ~ ")";
299            else
300                stack[$ - 1] = op ~ stack[$ - 1];
301        }
302        else static if (arg == "=")
303        {
304            stack[$ - 1] = "res[pos] = cast(T)(" ~ stack[$ - 1] ~ ")";
305        }
306        else static if (isBinaryAssignOp(arg))
307        {
308            stack[$ - 1] = "res[pos] " ~ arg ~ " cast(T)(" ~ stack[$ - 1] ~ ")";
309        }
310        else static if (isBinaryOp(arg))
311        {
312            stack[$ - 2] = "(" ~ stack[$ - 2] ~ " " ~ arg ~ " " ~ stack[$ - 1] ~ ")";
313            stack.length -= 1;
314        }
315        else
316            assert(0, "Unexpected op " ~ arg);
317    }
318    assert(stack.length == 1);
319    return stack[0];
320}();
321
322// Generate mixin statement to perform vector loop initialization, assumes
323// `args` to contain operand values.
324enum initScalarVecs(Args...) =
325() {
326    size_t scalarsIdx, argsIdx;
327    string res;
328    foreach (arg; Args)
329    {
330        static if (is(arg == T[], T))
331        {
332            ++argsIdx;
333        }
334        else static if (is(arg))
335            res ~= "immutable vec scalar" ~ scalarsIdx++.toString ~ " = args["
336                ~ argsIdx++.toString ~ "];\n";
337    }
338    return res;
339}();
340
341// Generate mixin expression to perform vector arrayOp loop expression, assumes
342// `pos` to be the current slice index, `args` to contain operand values, and
343// `res` the target slice.
344enum vectorExp(Args...) =
345() {
346    size_t scalarsIdx, argsIdx;
347    string[] stack;
348    foreach (arg; Args)
349    {
350        static if (is(arg == T[], T))
351            stack ~= "load(&args[" ~ argsIdx++.toString ~ "][pos])";
352        else static if (is(arg))
353        {
354            ++argsIdx;
355            stack ~= "scalar" ~ scalarsIdx++.toString;
356        }
357        else static if (isUnaryOp(arg))
358        {
359            auto op = arg[0] == 'u' ? arg[1 .. $] : arg;
360            stack[$ - 1] = "unaop!\"" ~ arg ~ "\"(" ~ stack[$ - 1] ~ ")";
361        }
362        else static if (arg == "=")
363        {
364            stack[$ - 1] = "store(&res[pos], " ~ stack[$ - 1] ~ ")";
365        }
366        else static if (isBinaryAssignOp(arg))
367        {
368            stack[$ - 1] = "store(&res[pos], binop!\"" ~ arg[0 .. $ - 1]
369                ~ "\"(load(&res[pos]), " ~ stack[$ - 1] ~ "))";
370        }
371        else static if (isBinaryOp(arg))
372        {
373            stack[$ - 2] = "binop!\"" ~ arg ~ "\"(" ~ stack[$ - 2] ~ ", " ~ stack[$ - 1] ~ ")";
374            stack.length -= 1;
375        }
376        else
377            assert(0, "Unexpected op " ~ arg);
378    }
379    assert(stack.length == 1);
380    return stack[0];
381}();
382
383// other helpers
384
385enum isType(T) = true;
386enum isType(alias a) = false;
387template not(alias tmlp)
388{
389    enum not(Args...) = !tmlp!Args;
390}
391/**
392Find element in `haystack` for which `pred` is true.
393
394Params:
395    pred = the template predicate
396    haystack = elements to search
397Returns:
398    The first index for which `pred!haystack[index]` is true or -1.
399 */
400template staticIndexOf(alias pred, haystack...)
401{
402    static if (pred!(haystack[0]))
403        enum staticIndexOf = 0;
404    else
405    {
406        enum next = staticIndexOf!(pred, haystack[1 .. $]);
407        enum staticIndexOf = next == -1 ? -1 : next + 1;
408    }
409}
410/// converts slice types to their element type, preserves anything else
411alias toElementType(E : E[]) = E;
412alias toElementType(S) = S;
413alias toElementType(alias op) = op;
414/// converts slice types to their element type, preserves anything else
415alias toVecType(E : E[]) = vec!E;
416alias toVecType(S) = vec!S;
417alias toVecType(alias op) = op;
418
419string toString(size_t num)
420{
421    import core.internal.string : unsignedToTempString;
422    version (D_BetterC)
423    {
424        // Workaround for https://issues.dlang.org/show_bug.cgi?id=19268
425        if (__ctfe)
426        {
427            char[20] fixedbuf = void;
428            char[] buf = unsignedToTempString(num, fixedbuf);
429            char[] result = new char[buf.length];
430            result[] = buf[];
431            return (() @trusted => cast(string) result)();
432        }
433        else
434        {
435            // Failing at execution rather than during compilation is
436            // not good, but this is in `core.internal` so it should
437            // not be used by the unwary.
438            assert(0, __FUNCTION__ ~ " not available in -betterC except during CTFE.");
439        }
440    }
441    else
442    {
443        char[20] buf = void;
444        return unsignedToTempString(num, buf).idup;
445    }
446}
447
448bool contains(T)(const scope T[] ary, const scope T[] vals...)
449{
450    foreach (v1; ary)
451        foreach (v2; vals)
452            if (v1 == v2)
453                return true;
454    return false;
455}
456
457// tests
458
459version (CoreUnittest) template TT(T...)
460{
461    alias TT = T;
462}
463
464version (CoreUnittest) template _arrayOp(Args...)
465{
466    alias _arrayOp = arrayOp!Args;
467}
468
469unittest
470{
471    static void check(string op, TA, TB, T, size_t N)(TA a, TB b, const scope ref T[N] exp)
472    {
473        T[N] res;
474        _arrayOp!(T[], TA, TB, op, "=")(res[], a, b);
475        foreach (i; 0 .. N)
476            assert(res[i] == exp[i]);
477    }
478
479    static void check2(string unaOp, string binOp, TA, TB, T, size_t N)(TA a, TB b, const scope ref T[N] exp)
480    {
481        T[N] res;
482        _arrayOp!(T[], TA, TB, unaOp, binOp, "=")(res[], a, b);
483        foreach (i; 0 .. N)
484            assert(res[i] == exp[i]);
485    }
486
487    static void test(T, string op, size_t N = 16)(T a, T b, T exp)
488    {
489        T[N] va = a, vb = b, vexp = exp;
490
491        check!op(va[], vb[], vexp);
492        check!op(va[], b, vexp);
493        check!op(a, vb[], vexp);
494    }
495
496    static void test2(T, string unaOp, string binOp, size_t N = 16)(T a, T b, T exp)
497    {
498        T[N] va = a, vb = b, vexp = exp;
499
500        check2!(unaOp, binOp)(va[], vb[], vexp);
501        check2!(unaOp, binOp)(va[], b, vexp);
502        check2!(unaOp, binOp)(a, vb[], vexp);
503    }
504
505    alias UINTS = TT!(ubyte, ushort, uint, ulong);
506    alias INTS = TT!(byte, short, int, long);
507    alias FLOATS = TT!(float, double);
508
509    foreach (T; TT!(UINTS, INTS, FLOATS))
510    {
511        test!(T, "+")(1, 2, 3);
512        test!(T, "-")(3, 2, 1);
513        static if (__traits(compiles, { import std.math; }))
514            test!(T, "^^")(2, 3, 8);
515
516        test2!(T, "u-", "+")(3, 2, 1);
517    }
518
519    foreach (T; TT!(UINTS, INTS))
520    {
521        test!(T, "|")(1, 2, 3);
522        test!(T, "&")(3, 1, 1);
523        test!(T, "^")(3, 1, 2);
524
525        test2!(T, "u~", "+")(3, cast(T)~2, 5);
526    }
527
528    foreach (T; TT!(INTS, FLOATS))
529    {
530        test!(T, "-")(1, 2, -1);
531        test2!(T, "u-", "+")(-3, -2, -1);
532        test2!(T, "u-", "*")(-3, -2, -6);
533    }
534
535    foreach (T; TT!(UINTS, INTS, FLOATS))
536    {
537        test!(T, "*")(2, 3, 6);
538        test!(T, "/")(8, 4, 2);
539        test!(T, "%")(8, 6, 2);
540    }
541}
542
543// test handling of v op= exp
544unittest
545{
546    uint[32] c;
547    arrayOp!(uint[], uint, "+=")(c[], 2);
548    foreach (v; c)
549        assert(v == 2);
550    static if (__traits(compiles, { import std.math; }))
551    {
552        arrayOp!(uint[], uint, "^^=")(c[], 3);
553        foreach (v; c)
554            assert(v == 8);
555    }
556}
557
558// proper error message for UDT lacking certain ops
559unittest
560{
561    static assert(!is(typeof(&arrayOp!(int[4][], int[4], "+="))));
562    static assert(!is(typeof(&arrayOp!(int[4][], int[4], "u-", "="))));
563
564    static struct S
565    {
566    }
567
568    static assert(!is(typeof(&arrayOp!(S[], S, "+="))));
569    static assert(!is(typeof(&arrayOp!(S[], S[], "*", S, "+="))));
570    static struct S2
571    {
572        S2 opBinary(string op)(in S2) @nogc pure nothrow
573        {
574            return this;
575        }
576
577        ref S2 opOpAssign(string op)(in S2) @nogc pure nothrow
578        {
579            return this;
580        }
581    }
582
583    static assert(is(typeof(&arrayOp!(S2[], S2[], S2[], S2, "*", "+", "="))));
584    static assert(is(typeof(&arrayOp!(S2[], S2[], S2, "*", "+="))));
585}
586
587// test mixed type array op
588unittest
589{
590    uint[32] a = 0xF;
591    float[32] res = 2.0f;
592    arrayOp!(float[], const(uint)[], uint, "&", "*=")(res[], a[], 12);
593    foreach (v; res[])
594        assert(v == 24.0f);
595}
596
597// test mixed type array op
598unittest
599{
600    static struct S
601    {
602        float opBinary(string op)(in S) @nogc const pure nothrow
603        {
604            return 2.0f;
605        }
606    }
607
608    float[32] res = 24.0f;
609    S[32] s;
610    arrayOp!(float[], const(S)[], const(S)[], "+", "/=")(res[], s[], s[]);
611    foreach (v; res[])
612        assert(v == 12.0f);
613}
614
615// test scalar after operation argument
616unittest
617{
618    float[32] res, a = 2, b = 3;
619    float c = 4;
620    arrayOp!(float[], const(float)[], const(float)[], "*", float, "+", "=")(res[], a[], b[], c);
621    foreach (v; res[])
622        assert(v == 2 * 3 + 4);
623}
624
625unittest
626{
627    // https://issues.dlang.org/show_bug.cgi?id=17964
628    uint bug(){
629        uint[] a = [1, 2, 3, 5, 6, 7];
630        uint[] b = [1, 2, 3, 5, 6, 7];
631        a[] |= ~b[];
632        return a[1];
633    }
634    enum x = bug();
635}
636
637// https://issues.dlang.org/show_bug.cgi?id=19796
638unittest
639{
640    double[] data = [0.5];
641    double[] result;
642    result.length = data.length;
643    result[] = -data[];
644    assert(result[0] == -0.5);
645}
646
647// https://issues.dlang.org/show_bug.cgi?id=21110
648unittest
649{
650    import core.exception;
651
652    static void assertThrown(T : Throwable, E)(lazy E expression, string msg)
653    {
654        try
655            expression;
656        catch (T)
657            return;
658        assert(0, "msg");
659    }
660
661    int[] dst;
662    int[] a;
663    int[] b;
664    a.length = 3;
665    b.length = 3;
666    dst.length = 4;
667
668    void func() { dst[] = a[] + b[]; }
669    assertThrown!AssertError(func(), "Array operations with mismatched lengths must throw an error");
670}
671