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 */
9 module core.internal.array.operations;
10 import core.internal.traits : Filter, staticMap, Unqual;
11
12 version (GNU) version = GNU_OR_LDC;
13 version (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 */
36 T[] 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
foreach(argsIdx,arg;typeof(args) )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
78 private:
79
80 // SIMD helpers
81
version(DigitalMars)82 version (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 /**
138 Check whether operations on operand types are supported. This
139 template recursively reduces the expression tree and determines
140 intermediate types.
141 Type checking is done here rather than in the compiler to provide more
142 detailed error messages.
143
144 Params:
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
148 Returns:
149 The resulting type of the expression
150 See_Also:
151 $(LREF arrayOp)
152 */
typeCheck(bool fail,T,Args...)153 template 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
typeCheck(bool fail,T,ResultType)213 template typeCheck(bool fail, T, ResultType)
214 {
215 alias typeCheck = ResultType;
216 }
217
version(GNU_OR_LDC)218 version (GNU_OR_LDC)
219 {
220 // leave it to the auto-vectorizer
221 enum vectorizeable(E : E[], Args...) = false;
222 }
223 else
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
version(X86_64)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
isUnaryOp(scope string op)248 bool isUnaryOp(scope string op) pure nothrow @safe @nogc
249 {
250 return op[0] == 'u';
251 }
252
isBinaryOp(scope string op)253 bool 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
isBinaryAssignOp(string op)268 bool 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.
scalarExp(Args...)276 enum 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.
initScalarVecs(Args...)324 enum 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.
vectorExp(Args...)344 enum 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
385 enum isType(T) = true;
386 enum isType(alias a) = false;
not(alias tmlp)387 template not(alias tmlp)
388 {
389 enum not(Args...) = !tmlp!Args;
390 }
391 /**
392 Find element in `haystack` for which `pred` is true.
393
394 Params:
395 pred = the template predicate
396 haystack = elements to search
397 Returns:
398 The first index for which `pred!haystack[index]` is true or -1.
399 */
staticIndexOf(alias pred,haystack...)400 template 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
411 alias toElementType(E : E[]) = E;
412 alias toElementType(S) = S;
413 alias toElementType(alias op) = op;
414 /// converts slice types to their element type, preserves anything else
415 alias toVecType(E : E[]) = vec!E;
416 alias toVecType(S) = vec!S;
417 alias toVecType(alias op) = op;
418
toString(size_t num)419 string 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
contains(T)448 bool 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
version(CoreUnittest)459 version (CoreUnittest) template TT(T...)
460 {
461 alias TT = T;
462 }
463
version(CoreUnittest)464 version (CoreUnittest) template _arrayOp(Args...)
465 {
466 alias _arrayOp = arrayOp!Args;
467 }
468
469 unittest
470 {
check(string op,TA,TB,T,size_t N)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
check2(string unaOp,string binOp,TA,TB,T,size_t N)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
544 unittest
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
559 unittest
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 {
opBinaryS2572 S2 opBinary(string op)(in S2) @nogc pure nothrow
573 {
574 return this;
575 }
576
opOpAssignS2577 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
588 unittest
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
598 unittest
599 {
600 static struct S
601 {
opBinaryS602 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
616 unittest
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
625 unittest
626 {
627 // https://issues.dlang.org/show_bug.cgi?id=17964
bug()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
638 unittest
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
648 unittest
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
func()668 void func() { dst[] = a[] + b[]; }
669 assertThrown!AssertError(func(), "Array operations with mismatched lengths must throw an error");
670 }
671