1 2 /** 3 * Dynamic array implementation. 4 * 5 * Copyright: Copyright (C) 1999-2023 by The D Language Foundation, All Rights Reserved 6 * Authors: $(LINK2 https://www.digitalmars.com, Walter Bright) 7 * License: $(LINK2 https://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) 8 * Source: $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/root/array.d, root/_array.d) 9 * Documentation: https://dlang.org/phobos/dmd_root_array.html 10 * Coverage: https://codecov.io/gh/dlang/dmd/src/master/src/dmd/root/array.d 11 */ 12 13 module dmd.root.array; 14 15 import core.stdc.stdlib : _compare_fp_t; 16 import core.stdc.string; 17 18 import dmd.root.rmem; 19 import dmd.root.string; 20 21 // `qsort` is only `nothrow` since 2.081.0 22 private extern(C) void qsort(scope void* base, size_t nmemb, size_t size, _compare_fp_t compar) nothrow @nogc; 23 24 25 debug 26 { 27 debug = stomp; // flush out dangling pointer problems by stomping on unused memory 28 } 29 30 extern (C++) struct Array(T) 31 { 32 size_t length; 33 34 private: 35 T[] data; 36 enum SMALLARRAYCAP = 1; 37 T[SMALLARRAYCAP] smallarray; // inline storage for small arrays 38 39 public: 40 /******************* 41 * Params: 42 * dim = initial length of array 43 */ 44 this(size_t dim) pure nothrow scope 45 { 46 reserve(dim); 47 this.length = dim; 48 } 49 50 @disable this(this); 51 52 ~this() pure nothrow 53 { 54 debug (stomp) memset(data.ptr, 0xFF, data.length); 55 if (data.ptr != &smallarray[0]) 56 mem.xfree(data.ptr); 57 } 58 ///returns elements comma separated in [] 59 extern(D) const(char)[] toString() const 60 { 61 static const(char)[] toStringImpl(alias toStringFunc, Array)(Array* a, bool quoted = false) 62 { 63 const(char)[][] buf = (cast(const(char)[]*)mem.xcalloc((char[]).sizeof, a.length))[0 .. a.length]; 64 size_t len = 2; // [ and ] 65 const seplen = quoted ? 3 : 1; // ',' or null terminator and optionally '"' 66 if (a.length == 0) 67 len += 1; // null terminator 68 else 69 { 70 foreach (u; 0 .. a.length) 71 { 72 static if (is(typeof(a.data[u] is null))) 73 { 74 if (a.data[u] is null) 75 buf[u] = "null"; 76 else 77 buf[u] = toStringFunc(a.data[u]); 78 } 79 else 80 { 81 buf[u] = toStringFunc(a.data[u]); 82 } 83 84 len += buf[u].length + seplen; 85 } 86 } 87 char[] str = (cast(char*)mem.xmalloc_noscan(len))[0..len]; 88 89 str[0] = '['; 90 char* p = str.ptr + 1; 91 foreach (u; 0 .. a.length) 92 { 93 if (u) 94 *p++ = ','; 95 if (quoted) 96 *p++ = '"'; 97 memcpy(p, buf[u].ptr, buf[u].length); 98 p += buf[u].length; 99 if (quoted) 100 *p++ = '"'; 101 } 102 *p++ = ']'; 103 *p = 0; 104 assert(p - str.ptr == str.length - 1); // null terminator 105 mem.xfree(buf.ptr); 106 return str[0 .. $-1]; 107 } 108 109 static if (is(typeof(T.init.toString()))) 110 { 111 return toStringImpl!(a => a.toString)(&this); 112 } 113 else static if (is(typeof(T.init.toDString()))) 114 { 115 return toStringImpl!(a => a.toDString)(&this, true); 116 } 117 else 118 { 119 assert(0); 120 } 121 } 122 ///ditto 123 const(char)* toChars() const 124 { 125 return toString.ptr; 126 } 127 128 ref Array push(T ptr) return pure nothrow 129 { 130 reserve(1); 131 data[length++] = ptr; 132 return this; 133 } 134 135 extern (D) ref Array pushSlice(T[] a) return pure nothrow 136 { 137 const oldLength = length; 138 setDim(oldLength + a.length); 139 memcpy(data.ptr + oldLength, a.ptr, a.length * T.sizeof); 140 return this; 141 } 142 143 ref Array append(typeof(this)* a) return pure nothrow 144 { 145 insert(length, a); 146 return this; 147 } 148 149 void reserve(size_t nentries) pure nothrow 150 { 151 //printf("Array::reserve: length = %d, data.length = %d, nentries = %d\n", cast(int)length, cast(int)data.length, cast(int)nentries); 152 153 // Cold path 154 void enlarge(size_t nentries) 155 { 156 pragma(inline, false); // never inline cold path 157 if (data.length == 0) 158 { 159 // Not properly initialized, someone memset it to zero 160 if (nentries <= SMALLARRAYCAP) 161 { 162 data = SMALLARRAYCAP ? smallarray[] : null; 163 } 164 else 165 { 166 auto p = cast(T*)mem.xmalloc(nentries * T.sizeof); 167 data = p[0 .. nentries]; 168 } 169 } 170 else if (data.length == SMALLARRAYCAP) 171 { 172 const allocdim = length + nentries; 173 auto p = cast(T*)mem.xmalloc(allocdim * T.sizeof); 174 memcpy(p, smallarray.ptr, length * T.sizeof); 175 data = p[0 .. allocdim]; 176 } 177 else 178 { 179 /* Increase size by 1.5x to avoid excessive memory fragmentation 180 */ 181 auto increment = length / 2; 182 if (nentries > increment) // if 1.5 is not enough 183 increment = nentries; 184 const allocdim = length + increment; 185 debug (stomp) 186 { 187 // always move using allocate-copy-stomp-free 188 auto p = cast(T*)mem.xmalloc(allocdim * T.sizeof); 189 memcpy(p, data.ptr, length * T.sizeof); 190 memset(data.ptr, 0xFF, data.length * T.sizeof); 191 mem.xfree(data.ptr); 192 } 193 else 194 auto p = cast(T*)mem.xrealloc(data.ptr, allocdim * T.sizeof); 195 data = p[0 .. allocdim]; 196 } 197 198 debug (stomp) 199 { 200 if (length < data.length) 201 memset(data.ptr + length, 0xFF, (data.length - length) * T.sizeof); 202 } 203 else 204 { 205 if (mem.isGCEnabled) 206 if (length < data.length) 207 memset(data.ptr + length, 0xFF, (data.length - length) * T.sizeof); 208 } 209 } 210 211 if (data.length - length < nentries) // false means hot path 212 enlarge(nentries); 213 } 214 215 void remove(size_t i) pure nothrow @nogc 216 { 217 if (length - i - 1) 218 memmove(data.ptr + i, data.ptr + i + 1, (length - i - 1) * T.sizeof); 219 length--; 220 debug (stomp) memset(data.ptr + length, 0xFF, T.sizeof); 221 } 222 223 void insert(size_t index, typeof(this)* a) pure nothrow 224 { 225 if (a) 226 { 227 size_t d = a.length; 228 reserve(d); 229 if (length != index) 230 memmove(data.ptr + index + d, data.ptr + index, (length - index) * T.sizeof); 231 memcpy(data.ptr + index, a.data.ptr, d * T.sizeof); 232 length += d; 233 } 234 } 235 236 extern (D) void insert(size_t index, T[] a) pure nothrow 237 { 238 size_t d = a.length; 239 reserve(d); 240 if (length != index) 241 memmove(data.ptr + index + d, data.ptr + index, (length - index) * T.sizeof); 242 memcpy(data.ptr + index, a.ptr, d * T.sizeof); 243 length += d; 244 } 245 246 void insert(size_t index, T ptr) pure nothrow 247 { 248 reserve(1); 249 memmove(data.ptr + index + 1, data.ptr + index, (length - index) * T.sizeof); 250 data[index] = ptr; 251 length++; 252 } 253 254 void setDim(size_t newdim) pure nothrow 255 { 256 if (length < newdim) 257 { 258 reserve(newdim - length); 259 } 260 length = newdim; 261 } 262 263 size_t find(T ptr) const nothrow pure 264 { 265 foreach (i; 0 .. length) 266 if (data[i] is ptr) 267 return i; 268 return size_t.max; 269 } 270 271 bool contains(T ptr) const nothrow pure 272 { 273 return find(ptr) != size_t.max; 274 } 275 276 ref inout(T) opIndex(size_t i) inout nothrow pure 277 { 278 debug 279 // This is called so often the array bounds become expensive 280 return data[i]; 281 else 282 return data.ptr[i]; 283 } 284 285 inout(T)* tdata() inout pure nothrow @nogc @trusted 286 { 287 return data.ptr; 288 } 289 290 Array!T* copy() const pure nothrow 291 { 292 auto a = new Array!T(); 293 a.setDim(length); 294 memcpy(a.data.ptr, data.ptr, length * T.sizeof); 295 return a; 296 } 297 298 void shift(T ptr) pure nothrow 299 { 300 reserve(1); 301 memmove(data.ptr + 1, data.ptr, length * T.sizeof); 302 data[0] = ptr; 303 length++; 304 } 305 306 void zero() nothrow pure @nogc 307 { 308 data[0 .. length] = T.init; 309 } 310 311 T pop() nothrow pure @nogc 312 { 313 debug (stomp) 314 { 315 assert(length); 316 auto result = data[length - 1]; 317 remove(length - 1); 318 return result; 319 } 320 else 321 return data[--length]; 322 } 323 324 extern (D) inout(T)[] opSlice() inout nothrow pure @nogc 325 { 326 return data[0 .. length]; 327 } 328 329 extern (D) inout(T)[] opSlice(size_t a, size_t b) inout nothrow pure @nogc 330 { 331 assert(a <= b && b <= length); 332 return data[a .. b]; 333 } 334 335 /** 336 * Sort the elements of an array 337 * 338 * This function relies on `qsort`. 339 * 340 * Params: 341 * pred = Predicate to use. Should be a function of type 342 * `int function(scope const T* e1, scope const T* e2) nothrow`. 343 * The return value of this function should follow the 344 * usual C rule: `e1 >= e2 ? (e1 > e2) : -1`. 345 * The function can have D linkage. 346 * 347 * Returns: 348 * A reference to this, for easy chaining. 349 */ 350 extern(D) ref typeof(this) sort (alias pred) () nothrow 351 { 352 if (this.length < 2) 353 return this; 354 qsort(this.data.ptr, this.length, T.sizeof, &arraySortWrapper!(T, pred)); 355 return this; 356 } 357 358 /// Ditto, but use `opCmp` by default 359 extern(D) ref typeof(this) sort () () nothrow 360 if (is(typeof(this.data[0].opCmp(this.data[1])) : int)) 361 { 362 return this.sort!(function (scope const(T)* pe1, scope const(T)* pe2) => pe1.opCmp(*pe2)); 363 } 364 365 alias opDollar = length; 366 367 deprecated("use `.length` instead") 368 extern(D) size_t dim() const @nogc nothrow pure @safe { return length; } 369 } 370 371 unittest 372 { 373 // Test for objects implementing toString() 374 static struct S 375 { 376 int s = -1; 377 string toString() const 378 { 379 return "S"; 380 } 381 } 382 auto array = Array!S(4); 383 assert(array.toString() == "[S,S,S,S]"); 384 array.setDim(0); 385 assert(array.toString() == "[]"); 386 387 // Test for toDString() 388 auto strarray = Array!(const(char)*)(2); 389 strarray[0] = "hello"; 390 strarray[1] = "world"; 391 auto str = strarray.toString(); 392 assert(str == `["hello","world"]`); 393 // Test presence of null terminator. 394 assert(str.ptr[str.length] == '\0'); 395 396 // Test printing an array of classes, which can be null 397 static class C 398 { 399 override string toString() const 400 { 401 return "x"; 402 } 403 } 404 auto nullarray = Array!C(2); 405 nullarray[0] = new C(); 406 nullarray[1] = null; 407 assert(nullarray.toString() == `[x,null]`); 408 } 409 410 unittest 411 { 412 auto array = Array!double(4); 413 array.shift(10); 414 array.push(20); 415 array[2] = 15; 416 assert(array[0] == 10); 417 assert(array.find(10) == 0); 418 assert(array.find(20) == 5); 419 assert(!array.contains(99)); 420 array.remove(1); 421 assert(array.length == 5); 422 assert(array[1] == 15); 423 assert(array.pop() == 20); 424 assert(array.length == 4); 425 array.insert(1, 30); 426 assert(array[1] == 30); 427 assert(array[2] == 15); 428 } 429 430 unittest 431 { 432 auto arrayA = Array!int(0); 433 int[3] buf = [10, 15, 20]; 434 arrayA.pushSlice(buf); 435 assert(arrayA[] == buf[]); 436 auto arrayPtr = arrayA.copy(); 437 assert(arrayPtr); 438 assert((*arrayPtr)[] == arrayA[]); 439 assert(arrayPtr.tdata != arrayA.tdata); 440 441 arrayPtr.setDim(0); 442 int[2] buf2 = [100, 200]; 443 arrayPtr.pushSlice(buf2); 444 445 arrayA.append(arrayPtr); 446 assert(arrayA[3..$] == buf2[]); 447 arrayA.insert(0, arrayPtr); 448 assert(arrayA[] == [100, 200, 10, 15, 20, 100, 200]); 449 450 arrayA.zero(); 451 foreach(e; arrayA) 452 assert(e == 0); 453 454 arrayA.setDim(0); 455 arrayA.pushSlice([5, 6]); 456 arrayA.insert(1, [1, 2]); 457 assert(arrayA[] == [5, 1, 2, 6]); 458 arrayA.insert(0, [7, 8]); 459 arrayA.insert(arrayA.length, [0, 9]); 460 assert(arrayA[] == [7, 8, 5, 1, 2, 6, 0, 9]); 461 } 462 463 /** 464 * Exposes the given root Array as a standard D array. 465 * Params: 466 * array = the array to expose. 467 * Returns: 468 * The given array exposed to a standard D array. 469 */ 470 @property inout(T)[] peekSlice(T)(inout(Array!T)* array) pure nothrow @nogc 471 { 472 return array ? (*array)[] : null; 473 } 474 475 /** 476 * Splits the array at $(D index) and expands it to make room for $(D length) 477 * elements by shifting everything past $(D index) to the right. 478 * Params: 479 * array = the array to split. 480 * index = the index to split the array from. 481 * length = the number of elements to make room for starting at $(D index). 482 */ 483 void split(T)(ref Array!T array, size_t index, size_t length) pure nothrow 484 { 485 if (length > 0) 486 { 487 auto previousDim = array.length; 488 array.setDim(array.length + length); 489 for (size_t i = previousDim; i > index;) 490 { 491 i--; 492 array[i + length] = array[i]; 493 } 494 } 495 } 496 unittest 497 { 498 auto array = Array!int(); 499 array.split(0, 0); 500 assert([] == array[]); 501 array.push(1).push(3); 502 array.split(1, 1); 503 array[1] = 2; 504 assert([1, 2, 3] == array[]); 505 array.split(2, 3); 506 array[2] = 8; 507 array[3] = 20; 508 array[4] = 4; 509 assert([1, 2, 8, 20, 4, 3] == array[]); 510 array.split(0, 0); 511 assert([1, 2, 8, 20, 4, 3] == array[]); 512 array.split(0, 1); 513 array[0] = 123; 514 assert([123, 1, 2, 8, 20, 4, 3] == array[]); 515 array.split(0, 3); 516 array[0] = 123; 517 array[1] = 421; 518 array[2] = 910; 519 assert([123, 421, 910, 123, 1, 2, 8, 20, 4, 3] == (&array).peekSlice()); 520 } 521 522 /** 523 * Reverse an array in-place. 524 * Params: 525 * a = array 526 * Returns: 527 * reversed a[] 528 */ 529 T[] reverse(T)(T[] a) pure nothrow @nogc @safe 530 { 531 if (a.length > 1) 532 { 533 const mid = (a.length + 1) >> 1; 534 foreach (i; 0 .. mid) 535 { 536 T e = a[i]; 537 a[i] = a[$ - 1 - i]; 538 a[$ - 1 - i] = e; 539 } 540 } 541 return a; 542 } 543 544 unittest 545 { 546 int[] a1 = []; 547 assert(reverse(a1) == []); 548 int[] a2 = [2]; 549 assert(reverse(a2) == [2]); 550 int[] a3 = [2,3]; 551 assert(reverse(a3) == [3,2]); 552 int[] a4 = [2,3,4]; 553 assert(reverse(a4) == [4,3,2]); 554 int[] a5 = [2,3,4,5]; 555 assert(reverse(a5) == [5,4,3,2]); 556 } 557 558 unittest 559 { 560 //test toString/toChars. Identifier is a simple object that has a usable .toString 561 import dmd.identifier : Identifier; 562 import core.stdc.string : strcmp; 563 564 auto array = Array!Identifier(); 565 array.push(new Identifier("id1")); 566 array.push(new Identifier("id2")); 567 568 string expected = "[id1,id2]"; 569 assert(array.toString == expected); 570 assert(strcmp(array.toChars, expected.ptr) == 0); 571 } 572 573 /// Predicate to wrap a D function passed to `qsort` 574 private template arraySortWrapper(T, alias fn) 575 { 576 pragma(mangle, "arraySortWrapper_" ~ T.mangleof ~ "_" ~ fn.mangleof) 577 extern(C) int arraySortWrapper(scope const void* e1, scope const void* e2) nothrow 578 { 579 return fn(cast(const(T*))e1, cast(const(T*))e2); 580 } 581 } 582 583 // Test sorting 584 unittest 585 { 586 Array!(const(char)*) strings; 587 strings.push("World"); 588 strings.push("Foo"); 589 strings.push("baguette"); 590 strings.push("Avocado"); 591 strings.push("Hello"); 592 // Newer frontend versions will work with (e1, e2) and infer the type 593 strings.sort!(function (scope const char** e1, scope const char** e2) => strcmp(*e1, *e2)); 594 assert(strings[0] == "Avocado"); 595 assert(strings[1] == "Foo"); 596 assert(strings[2] == "Hello"); 597 assert(strings[3] == "World"); 598 assert(strings[4] == "baguette"); 599 600 /// opCmp automatically supported 601 static struct MyStruct 602 { 603 int a; 604 605 int opCmp(const ref MyStruct other) const nothrow 606 { 607 // Reverse order 608 return other.a - this.a; 609 } 610 } 611 612 Array!MyStruct arr1; 613 arr1.push(MyStruct(2)); 614 arr1.push(MyStruct(4)); 615 arr1.push(MyStruct(256)); 616 arr1.push(MyStruct(42)); 617 arr1.sort(); 618 assert(arr1[0].a == 256); 619 assert(arr1[1].a == 42); 620 assert(arr1[2].a == 4); 621 assert(arr1[3].a == 2); 622 623 /// But only if user defined 624 static struct OtherStruct 625 { 626 int a; 627 628 static int pred (scope const OtherStruct* pe1, scope const OtherStruct* pe2) 629 nothrow @nogc pure @safe 630 { 631 return pe1.a - pe2.a; 632 } 633 } 634 635 static assert (!is(typeof(Array!(OtherStruct).init.sort()))); 636 static assert (!is(typeof(Array!(OtherStruct).init.sort!pred))); 637 } 638 639 /** 640 * Iterates the given array and calls the given callable for each element. 641 * 642 * Use this instead of `foreach` when the array may expand during iteration. 643 * 644 * Params: 645 * callable = the callable to call for each element 646 * array = the array to iterate 647 * 648 * See_Also: $(REF foreachDsymbol, dmd, dsymbol) 649 */ 650 template each(alias callable, T) 651 if (is(ReturnType!(typeof((T t) => callable(t))) == void)) 652 { 653 void each(ref Array!T array) 654 { 655 // Do not use foreach, as the size of the array may expand during iteration 656 for (size_t i = 0; i < array.length; ++i) 657 callable(array[i]); 658 } 659 660 void each(Array!T* array) 661 { 662 if (array) 663 each!callable(*array); 664 } 665 } 666 667 /// 668 @("iterate over an Array") unittest 669 { 670 static immutable expected = [2, 3, 4, 5]; 671 672 Array!int array; 673 674 foreach (e ; expected) 675 array.push(e); 676 677 int[] result; 678 array.each!((e) { 679 result ~= e; 680 }); 681 682 assert(result == expected); 683 } 684 685 @("iterate over a pointer to an Array") unittest 686 { 687 static immutable expected = [2, 3, 4, 5]; 688 689 auto array = new Array!int; 690 691 foreach (e ; expected) 692 array.push(e); 693 694 int[] result; 695 array.each!((e) { 696 result ~= e; 697 }); 698 699 assert(result == expected); 700 } 701 702 @("iterate while appending to the array being iterated") unittest 703 { 704 static immutable expected = [2, 3, 4, 5]; 705 706 Array!int array; 707 708 foreach (e ; expected[0 .. $ - 1]) 709 array.push(e); 710 711 int[] result; 712 713 array.each!((e) { 714 if (e == 2) 715 array.push(5); 716 717 result ~= e; 718 }); 719 720 assert(array[] == expected); 721 assert(result == expected); 722 } 723 724 /** 725 * Iterates the given array and calls the given callable for each element. 726 * 727 * If `callable` returns `!= 0`, it will stop the iteration and return that 728 * value, otherwise it will return 0. 729 * 730 * Use this instead of `foreach` when the array may expand during iteration. 731 * 732 * Params: 733 * callable = the callable to call for each element 734 * array = the array to iterate 735 * 736 * Returns: the last value returned by `callable` 737 * See_Also: $(REF foreachDsymbol, dmd, dsymbol) 738 */ 739 template each(alias callable, T) 740 if (is(ReturnType!(typeof((T t) => callable(t))) == int)) 741 { 742 int each(ref Array!T array) 743 { 744 // Do not use foreach, as the size of the array may expand during iteration 745 for (size_t i = 0; i < array.length; ++i) 746 { 747 if (const result = callable(array[i])) 748 return result; 749 } 750 751 return 0; 752 } 753 754 int each(Array!T* array) 755 { 756 return array ? each!callable(*array) : 0; 757 } 758 } 759 760 /// 761 @("iterate over an Array and stop the iteration") unittest 762 { 763 Array!int array; 764 765 foreach (e ; [2, 3, 4, 5]) 766 array.push(e); 767 768 int[] result; 769 const returnValue = array.each!((e) { 770 result ~= e; 771 772 if (e == 3) 773 return 8; 774 775 return 0; 776 }); 777 778 assert(result == [2, 3]); 779 assert(returnValue == 8); 780 } 781 782 @("iterate over an Array") unittest 783 { 784 static immutable expected = [2, 3, 4, 5]; 785 786 Array!int array; 787 788 foreach (e ; expected) 789 array.push(e); 790 791 int[] result; 792 const returnValue = array.each!((e) { 793 result ~= e; 794 return 0; 795 }); 796 797 assert(result == expected); 798 assert(returnValue == 0); 799 } 800 801 @("iterate over a pointer to an Array and stop the iteration") unittest 802 { 803 auto array = new Array!int; 804 805 foreach (e ; [2, 3, 4, 5]) 806 array.push(e); 807 808 int[] result; 809 const returnValue = array.each!((e) { 810 result ~= e; 811 812 if (e == 3) 813 return 9; 814 815 return 0; 816 }); 817 818 assert(result == [2, 3]); 819 assert(returnValue == 9); 820 } 821 822 @("iterate while appending to the array being iterated and stop the iteration") unittest 823 { 824 Array!int array; 825 826 foreach (e ; [2, 3]) 827 array.push(e); 828 829 int[] result; 830 831 const returnValue = array.each!((e) { 832 if (e == 2) 833 array.push(1); 834 835 result ~= e; 836 837 if (e == 1) 838 return 7; 839 840 return 0; 841 }); 842 843 static immutable expected = [2, 3, 1]; 844 845 assert(array[] == expected); 846 assert(result == expected); 847 assert(returnValue == 7); 848 } 849 850 /// Returns: A static array constructed from `array`. 851 pragma(inline, true) T[n] staticArray(T, size_t n)(auto ref T[n] array) 852 { 853 return array; 854 } 855 856 /// 857 pure nothrow @safe @nogc unittest 858 { 859 enum a = [0, 1].staticArray; 860 static assert(is(typeof(a) == int[2])); 861 static assert(a == [0, 1]); 862 } 863 864 /// Returns: `true` if the two given ranges are equal 865 bool equal(Range1, Range2)(Range1 range1, Range2 range2) 866 { 867 template isArray(T) 868 { 869 static if (is(T U : U[])) 870 enum isArray = true; 871 872 else 873 enum isArray = false; 874 } 875 876 static if (isArray!Range1 && isArray!Range2 && is(typeof(range1 == range2))) 877 return range1 == range2; 878 879 else 880 { 881 static if (hasLength!Range1 && hasLength!Range2 && is(typeof(r1.length == r2.length))) 882 { 883 if (range1.length != range2.length) 884 return false; 885 } 886 887 for (; !range1.empty; range1.popFront(), range2.popFront()) 888 { 889 if (range2.empty) 890 return false; 891 892 if (range1.front != range2.front) 893 return false; 894 } 895 896 return range2.empty; 897 } 898 } 899 900 /// 901 pure nothrow @nogc @safe unittest 902 { 903 enum a = [ 1, 2, 4, 3 ].staticArray; 904 static assert(!equal(a[], a[1..$])); 905 static assert(equal(a[], a[])); 906 907 // different types 908 enum b = [ 1.0, 2, 4, 3].staticArray; 909 static assert(!equal(a[], b[1..$])); 910 static assert(equal(a[], b[])); 911 } 912 913 pure nothrow @safe unittest 914 { 915 static assert(equal([1, 2, 3].map!(x => x * 2), [1, 2, 3].map!(x => x * 2))); 916 917 static assert(!equal([1, 2].map!(x => x * 2), [1, 2, 3].map!(x => x * 2))); 918 } 919 920 /** 921 * Lazily filters the given range based on the given predicate. 922 * 923 * Returns: a range containing only elements for which the predicate returns 924 * `true` 925 */ 926 auto filter(alias predicate, Range)(Range range) 927 if (isInputRange!(Unqual!Range) && isPredicateOf!(predicate, ElementType!Range)) 928 { 929 return Filter!(predicate, Range)(range); 930 } 931 932 /// 933 pure nothrow @safe @nogc unittest 934 { 935 enum a = [1, 2, 3, 4].staticArray; 936 enum result = a[].filter!(e => e > 2); 937 938 enum expected = [3, 4].staticArray; 939 static assert(result.equal(expected[])); 940 } 941 942 private struct Filter(alias predicate, Range) 943 { 944 private Range range; 945 private bool primed; 946 947 private void prime() 948 { 949 if (primed) 950 return; 951 952 while (!range.empty && !predicate(range.front)) 953 range.popFront(); 954 955 primed = true; 956 } 957 958 @property bool empty() 959 { 960 prime(); 961 return range.empty; 962 } 963 964 @property auto front() 965 { 966 assert(!range.empty); 967 prime(); 968 return range.front; 969 } 970 971 void popFront() 972 { 973 assert(!range.empty); 974 prime(); 975 976 do 977 { 978 range.popFront(); 979 } while (!range.empty && !predicate(range.front)); 980 } 981 982 auto opSlice() 983 { 984 return this; 985 } 986 } 987 988 /** 989 * Lazily iterates the given range and calls the given callable for each element. 990 * 991 * Returns: a range containing the result of each call to `callable` 992 */ 993 auto map(alias callable, Range)(Range range) 994 if (isInputRange!(Unqual!Range) && isCallableWith!(callable, ElementType!Range)) 995 { 996 return Map!(callable, Range)(range); 997 } 998 999 /// 1000 pure nothrow @safe @nogc unittest 1001 { 1002 enum a = [1, 2, 3, 4].staticArray; 1003 enum expected = [2, 4, 6, 8].staticArray; 1004 1005 enum result = a[].map!(e => e * 2); 1006 static assert(result.equal(expected[])); 1007 } 1008 1009 private struct Map(alias callable, Range) 1010 { 1011 private Range range; 1012 1013 @property bool empty() 1014 { 1015 return range.empty; 1016 } 1017 1018 @property auto front() 1019 { 1020 assert(!range.empty); 1021 return callable(range.front); 1022 } 1023 1024 void popFront() 1025 { 1026 assert(!range.empty); 1027 range.popFront(); 1028 } 1029 1030 static if (hasLength!Range) 1031 { 1032 @property auto length() 1033 { 1034 return range.length; 1035 } 1036 1037 alias opDollar = length; 1038 } 1039 } 1040 1041 /// Returns: the length of the given range. 1042 auto walkLength(Range)(Range range) 1043 if (isInputRange!Range ) 1044 { 1045 static if (hasLength!Range) 1046 return range.length; 1047 else 1048 { 1049 size_t result; 1050 for (; !range.empty; range.popFront()) 1051 ++result; 1052 return result; 1053 } 1054 } 1055 1056 /// 1057 pure nothrow @safe @nogc unittest 1058 { 1059 enum a = [1, 2, 3, 4].staticArray; 1060 static assert(a[].walkLength == 4); 1061 1062 enum c = a[].filter!(e => e > 2); 1063 static assert(c.walkLength == 2); 1064 } 1065 1066 /// Evaluates to the element type of `R`. 1067 template ElementType(R) 1068 { 1069 static if (is(typeof(R.init.front.init) T)) 1070 alias ElementType = T; 1071 else 1072 alias ElementType = void; 1073 } 1074 1075 /// Evaluates to `true` if the given type satisfy the input range interface. 1076 enum isInputRange(R) = 1077 is(typeof(R.init) == R) 1078 && is(ReturnType!(typeof((R r) => r.empty)) == bool) 1079 && is(typeof((return ref R r) => r.front)) 1080 && !is(ReturnType!(typeof((R r) => r.front)) == void) 1081 && is(typeof((R r) => r.popFront)); 1082 1083 /// Evaluates to `true` if `func` can be called with a value of `T` and returns 1084 /// a value that is convertible to `bool`. 1085 enum isPredicateOf(alias func, T) = is(typeof((T t) => !func(t))); 1086 1087 /// Evaluates to `true` if `func` be called withl a value of `T`. 1088 enum isCallableWith(alias func, T) = 1089 __traits(compiles, { auto _ = (T t) => func(t); }); 1090 1091 private: 1092 1093 template ReturnType(T) 1094 { 1095 static if (is(T R == return)) 1096 alias ReturnType = R; 1097 else 1098 static assert(false, "argument is not a function"); 1099 } 1100 1101 alias Unqual(T) = ReturnType!(typeof((T t) => cast() t)); 1102 1103 template hasLength(Range) 1104 { 1105 static if (is(typeof(((Range* r) => r.length)(null)) Length)) 1106 enum hasLength = is(Length == size_t); 1107 else 1108 enum hasLength = false; 1109 } 1110 1111 /// Implements the range interface primitive `front` for built-in arrays. 1112 @property ref inout(T) front(T)(return scope inout(T)[] a) pure nothrow @nogc @safe 1113 { 1114 assert(a.length, "Attempting to fetch the front of an empty array of " ~ T.stringof); 1115 return a[0]; 1116 } 1117 1118 /// 1119 pure nothrow @nogc @safe unittest 1120 { 1121 enum a = [1, 2, 3].staticArray; 1122 static assert(a[].front == 1); 1123 } 1124 1125 /// Implements the range interface primitive `empty` for types that obey $(LREF hasLength) property 1126 @property bool empty(T)(auto ref scope T a) 1127 if (is(typeof(a.length) : size_t)) 1128 { 1129 return !a.length; 1130 } 1131 1132 /// 1133 pure nothrow @nogc @safe unittest 1134 { 1135 enum a = [1, 2, 3].staticArray; 1136 1137 static assert(!a.empty); 1138 static assert(a[3 .. $].empty); 1139 } 1140 1141 pure nothrow @safe unittest 1142 { 1143 int[string] b; 1144 assert(b.empty); 1145 b["zero"] = 0; 1146 assert(!b.empty); 1147 } 1148 1149 /// Implements the range interface primitive `popFront` for built-in arrays. 1150 void popFront(T)(/*scope*/ ref inout(T)[] array) pure nothrow @nogc @safe 1151 { // does not compile with GDC 9 if this is `scope` 1152 assert(array.length, "Attempting to popFront() past the end of an array of " ~ T.stringof); 1153 array = array[1 .. $]; 1154 } 1155 1156 /// 1157 pure nothrow @nogc @safe unittest 1158 { 1159 auto a = [1, 2, 3].staticArray; 1160 auto b = a[]; 1161 auto expected = [2, 3].staticArray; 1162 1163 b.popFront(); 1164 assert(b == expected[]); 1165 }