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