gcc/d/dmd/root/array.d

   1
   2 /**
   3  * Dynamic array implementation.
   4  *
   5  * Copyright:   Copyright (C) 1999-2024 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     /// Insert 'count' copies of 'value' at 'index' position
 255     void insert(size_t index, size_t count, T value) pure nothrow
 256     {
 257         if (count == 0)
 258             return;
 259         reserve(count);
 260         if (length != index)
 261             memmove(data.ptr + index + count, data.ptr + index, (length - index) * T.sizeof);
 262         data[index .. index + count] = value;
 263         length += count;
 264     }
 265
 266     void setDim(size_t newdim) pure nothrow
 267     {
 268         if (length < newdim)
 269         {
 270             reserve(newdim - length);
 271         }
 272         length = newdim;
 273     }
 274
 275     size_t find(T ptr) const nothrow pure
 276     {
 277         foreach (i; 0 .. length)
 278             if (data[i] is ptr)
 279                 return i;
 280         return size_t.max;
 281     }
 282
 283     bool contains(T ptr) const nothrow pure
 284     {
 285         return find(ptr) != size_t.max;
 286     }
 287
 288     ref inout(T) opIndex(size_t i) inout nothrow pure
 289     {
 290         debug
 291             // This is called so often the array bounds become expensive
 292             return data[i];
 293         else
 294             return data.ptr[i];
 295     }
 296
 297     inout(T)* tdata() inout pure nothrow @nogc @trusted
 298     {
 299         return data.ptr;
 300     }
 301
 302     Array!T* copy() const pure nothrow
 303     {
 304         auto a = new Array!T();
 305         a.setDim(length);
 306         memcpy(a.data.ptr, data.ptr, length * T.sizeof);
 307         return a;
 308     }
 309
 310     void shift(T ptr) pure nothrow
 311     {
 312         reserve(1);
 313         memmove(data.ptr + 1, data.ptr, length * T.sizeof);
 314         data[0] = ptr;
 315         length++;
 316     }
 317
 318     void zero() nothrow pure @nogc
 319     {
 320         data[0 .. length] = T.init;
 321     }
 322
 323     T pop() nothrow pure @nogc
 324     {
 325         debug (stomp)
 326         {
 327             assert(length);
 328             auto result = data[length - 1];
 329             remove(length - 1);
 330             return result;
 331         }
 332         else
 333             return data[--length];
 334     }
 335
 336     extern (D) inout(T)[] opSlice() inout nothrow pure @nogc
 337     {
 338         return data[0 .. length];
 339     }
 340
 341     extern (D) inout(T)[] opSlice(size_t a, size_t b) inout nothrow pure @nogc
 342     {
 343         assert(a <= b && b <= length);
 344         return data[a .. b];
 345     }
 346
 347     /**
 348      * Sort the elements of an array
 349      *
 350      * This function relies on `qsort`.
 351      *
 352      * Params:
 353      *   pred = Predicate to use. Should be a function of type
 354      *          `int function(scope const T*  e1, scope const T* e2) nothrow`.
 355      *          The return value of this function should follow the
 356      *          usual C rule: `e1 >= e2 ? (e1 > e2) : -1`.
 357      *          The function can have D linkage.
 358      *
 359      * Returns:
 360      *   A reference to this, for easy chaining.
 361      */
 362     extern(D) ref typeof(this) sort (alias pred) () nothrow
 363     {
 364         if (this.length < 2)
 365             return this;
 366         qsort(this.data.ptr, this.length, T.sizeof, &arraySortWrapper!(T, pred));
 367         return this;
 368     }
 369
 370     /// Ditto, but use `opCmp` by default
 371     extern(D) ref typeof(this) sort () () nothrow
 372         if (is(typeof(this.data[0].opCmp(this.data[1])) : int))
 373     {
 374         return this.sort!(function (scope const(T)* pe1, scope const(T)* pe2) => pe1.opCmp(*pe2));
 375     }
 376
 377     alias opDollar = length;
 378
 379     deprecated("use `.length` instead")
 380     extern(D) size_t dim() const @nogc nothrow pure @safe { return length; }
 381 }
 382
 383 unittest
 384 {
 385     // Test for objects implementing toString()
 386     static struct S
 387     {
 388         int s = -1;
 389         string toString() const
 390         {
 391             return "S";
 392         }
 393     }
 394     auto array = Array!S(4);
 395     assert(array.toString() == "[S,S,S,S]");
 396     array.setDim(0);
 397     assert(array.toString() == "[]");
 398
 399     // Test for toDString()
 400     auto strarray = Array!(const(char)*)(2);
 401     strarray[0] = "hello";
 402     strarray[1] = "world";
 403     auto str = strarray.toString();
 404     assert(str == `["hello","world"]`);
 405     // Test presence of null terminator.
 406     assert(str.ptr[str.length] == '\0');
 407
 408     // Test printing an array of classes, which can be null
 409     static class C
 410     {
 411         override string toString() const
 412         {
 413             return "x";
 414         }
 415     }
 416     auto nullarray = Array!C(2);
 417     nullarray[0] = new C();
 418     nullarray[1] = null;
 419     assert(nullarray.toString() == `[x,null]`);
 420 }
 421
 422 unittest
 423 {
 424     auto array = Array!double(4);
 425     array.shift(10);
 426     array.push(20);
 427     array[2] = 15;
 428     assert(array[0] == 10);
 429     assert(array.find(10) == 0);
 430     assert(array.find(20) == 5);
 431     assert(!array.contains(99));
 432     array.remove(1);
 433     assert(array.length == 5);
 434     assert(array[1] == 15);
 435     assert(array.pop() == 20);
 436     assert(array.length == 4);
 437     array.insert(1, 30);
 438     assert(array[1] == 30);
 439     assert(array[2] == 15);
 440 }
 441
 442 unittest
 443 {
 444     auto arrayA = Array!int(0);
 445     int[3] buf = [10, 15, 20];
 446     arrayA.pushSlice(buf);
 447     assert(arrayA[] == buf[]);
 448     auto arrayPtr = arrayA.copy();
 449     assert(arrayPtr);
 450     assert((*arrayPtr)[] == arrayA[]);
 451     assert(arrayPtr.tdata != arrayA.tdata);
 452
 453     arrayPtr.setDim(0);
 454     int[2] buf2 = [100, 200];
 455     arrayPtr.pushSlice(buf2);
 456
 457     arrayA.append(arrayPtr);
 458     assert(arrayA[3..$] == buf2[]);
 459     arrayA.insert(0, arrayPtr);
 460     assert(arrayA[] == [100, 200, 10, 15, 20, 100, 200]);
 461
 462     arrayA.zero();
 463     foreach(e; arrayA)
 464         assert(e == 0);
 465
 466     arrayA.setDim(0);
 467     arrayA.pushSlice([5, 6]);
 468     arrayA.insert(1, [1, 2]);
 469     assert(arrayA[] == [5, 1, 2, 6]);
 470     arrayA.insert(0, [7, 8]);
 471     arrayA.insert(arrayA.length, [0, 9]);
 472     assert(arrayA[] == [7, 8, 5, 1, 2, 6, 0, 9]);
 473     arrayA.insert(4, 3, 8);
 474     assert(arrayA[] == [7, 8, 5, 1, 8, 8, 8, 2, 6, 0, 9]);
 475     arrayA.insert(0, 3, 8);
 476     assert(arrayA[] == [8, 8, 8, 7, 8, 5, 1, 8, 8, 8, 2, 6, 0, 9]);
 477     arrayA.insert(arrayA.length, 3, 8);
 478     assert(arrayA[] == [8, 8, 8, 7, 8, 5, 1, 8, 8, 8, 2, 6, 0, 9, 8, 8, 8]);
 479 }
 480
 481 /**
 482  * Exposes the given root Array as a standard D array.
 483  * Params:
 484  *  array = the array to expose.
 485  * Returns:
 486  *  The given array exposed to a standard D array.
 487  */
 488 @property inout(T)[] peekSlice(T)(inout(Array!T)* array) pure nothrow @nogc
 489 {
 490     return array ? (*array)[] : null;
 491 }
 492
 493 /**
 494  * Splits the array at $(D index) and expands it to make room for $(D length)
 495  * elements by shifting everything past $(D index) to the right.
 496  * Params:
 497  *  array = the array to split.
 498  *  index = the index to split the array from.
 499  *  length = the number of elements to make room for starting at $(D index).
 500  */
 501 void split(T)(ref Array!T array, size_t index, size_t length) pure nothrow
 502 {
 503     if (length > 0)
 504     {
 505         auto previousDim = array.length;
 506         array.setDim(array.length + length);
 507         for (size_t i = previousDim; i > index;)
 508         {
 509             i--;
 510             array[i + length] = array[i];
 511         }
 512     }
 513 }
 514 unittest
 515 {
 516     auto array = Array!int();
 517     array.split(0, 0);
 518     assert([] == array[]);
 519     array.push(1).push(3);
 520     array.split(1, 1);
 521     array[1] = 2;
 522     assert([1, 2, 3] == array[]);
 523     array.split(2, 3);
 524     array[2] = 8;
 525     array[3] = 20;
 526     array[4] = 4;
 527     assert([1, 2, 8, 20, 4, 3] == array[]);
 528     array.split(0, 0);
 529     assert([1, 2, 8, 20, 4, 3] == array[]);
 530     array.split(0, 1);
 531     array[0] = 123;
 532     assert([123, 1, 2, 8, 20, 4, 3] == array[]);
 533     array.split(0, 3);
 534     array[0] = 123;
 535     array[1] = 421;
 536     array[2] = 910;
 537     assert([123, 421, 910, 123, 1, 2, 8, 20, 4, 3] == (&array).peekSlice());
 538 }
 539
 540 /**
 541  * Reverse an array in-place.
 542  * Params:
 543  *      a = array
 544  * Returns:
 545  *      reversed a[]
 546  */
 547 T[] reverse(T)(T[] a) pure nothrow @nogc @safe
 548 {
 549     if (a.length > 1)
 550     {
 551         const mid = (a.length + 1) >> 1;
 552         foreach (i; 0 .. mid)
 553         {
 554             T e = a[i];
 555             a[i] = a[$ - 1 - i];
 556             a[$ - 1 - i] = e;
 557         }
 558     }
 559     return a;
 560 }
 561
 562 unittest
 563 {
 564     int[] a1 = [];
 565     assert(reverse(a1) == []);
 566     int[] a2 = [2];
 567     assert(reverse(a2) == [2]);
 568     int[] a3 = [2,3];
 569     assert(reverse(a3) == [3,2]);
 570     int[] a4 = [2,3,4];
 571     assert(reverse(a4) == [4,3,2]);
 572     int[] a5 = [2,3,4,5];
 573     assert(reverse(a5) == [5,4,3,2]);
 574 }
 575
 576 unittest
 577 {
 578     //test toString/toChars.  Identifier is a simple object that has a usable .toString
 579     import dmd.identifier : Identifier;
 580     import core.stdc.string : strcmp;
 581
 582     auto array = Array!Identifier();
 583     array.push(new Identifier("id1"));
 584     array.push(new Identifier("id2"));
 585
 586     string expected = "[id1,id2]";
 587     assert(array.toString == expected);
 588     assert(strcmp(array.toChars, expected.ptr) == 0);
 589 }
 590
 591 /// Predicate to wrap a D function passed to `qsort`
 592 private template arraySortWrapper(T, alias fn)
 593 {
 594     pragma(mangle, "arraySortWrapper_" ~ T.mangleof ~ "_" ~ fn.mangleof)
 595     extern(C) int arraySortWrapper(scope const void* e1, scope const void* e2)
 596     {
 597         return fn(cast(const(T*))e1, cast(const(T*))e2);
 598     }
 599 }
 600
 601 // Test sorting
 602 unittest
 603 {
 604     Array!(const(char)*) strings;
 605     strings.push("World");
 606     strings.push("Foo");
 607     strings.push("baguette");
 608     strings.push("Avocado");
 609     strings.push("Hello");
 610     // Newer frontend versions will work with (e1, e2) and infer the type
 611     strings.sort!(function (scope const char** e1, scope const char** e2) => strcmp(*e1, *e2));
 612     assert(strings[0] == "Avocado");
 613     assert(strings[1] == "Foo");
 614     assert(strings[2] == "Hello");
 615     assert(strings[3] == "World");
 616     assert(strings[4] == "baguette");
 617
 618     /// opCmp automatically supported
 619     static struct MyStruct
 620     {
 621         int a;
 622
 623         int opCmp(const ref MyStruct other) const nothrow
 624         {
 625             // Reverse order
 626             return other.a - this.a;
 627         }
 628     }
 629
 630     Array!MyStruct arr1;
 631     arr1.push(MyStruct(2));
 632     arr1.push(MyStruct(4));
 633     arr1.push(MyStruct(256));
 634     arr1.push(MyStruct(42));
 635     arr1.sort();
 636     assert(arr1[0].a == 256);
 637     assert(arr1[1].a == 42);
 638     assert(arr1[2].a == 4);
 639     assert(arr1[3].a == 2);
 640
 641     /// But only if user defined
 642     static struct OtherStruct
 643     {
 644         int a;
 645
 646         static int pred (scope const OtherStruct* pe1, scope const OtherStruct* pe2)
 647             nothrow @nogc pure @safe
 648         {
 649             return pe1.a - pe2.a;
 650         }
 651     }
 652
 653     static assert (!is(typeof(Array!(OtherStruct).init.sort())));
 654     static assert (!is(typeof(Array!(OtherStruct).init.sort!pred)));
 655 }
 656
 657 /**
 658  * Iterates the given array and calls the given callable for each element.
 659  *
 660  * Use this instead of `foreach` when the array may expand during iteration.
 661  *
 662  * Params:
 663  *  callable = the callable to call for each element
 664  *  array = the array to iterate
 665  *
 666  * See_Also: $(REF foreachDsymbol, dmd, dsymbol)
 667  */
 668 template each(alias callable, T)
 669 if (is(ReturnType!(typeof((T t) => callable(t))) == void))
 670 {
 671     void each(ref Array!T array)
 672     {
 673         // Do not use foreach, as the size of the array may expand during iteration
 674         for (size_t i = 0; i < array.length; ++i)
 675             callable(array[i]);
 676     }
 677
 678     void each(Array!T* array)
 679     {
 680         if (array)
 681             each!callable(*array);
 682     }
 683 }
 684
 685 ///
 686 @("iterate over an Array") unittest
 687 {
 688     static immutable expected = [2, 3, 4, 5];
 689
 690     Array!int array;
 691
 692     foreach (e ; expected)
 693         array.push(e);
 694
 695     int[] result;
 696     array.each!((e) {
 697         result ~= e;
 698     });
 699
 700     assert(result == expected);
 701 }
 702
 703 @("iterate over a pointer to an Array") unittest
 704 {
 705     static immutable expected = [2, 3, 4, 5];
 706
 707     auto array = new Array!int;
 708
 709     foreach (e ; expected)
 710         array.push(e);
 711
 712     int[] result;
 713     array.each!((e) {
 714         result ~= e;
 715     });
 716
 717     assert(result == expected);
 718 }
 719
 720 @("iterate while appending to the array being iterated") unittest
 721 {
 722     static immutable expected = [2, 3, 4, 5];
 723
 724     Array!int array;
 725
 726     foreach (e ; expected[0 .. $ - 1])
 727         array.push(e);
 728
 729     int[] result;
 730
 731     array.each!((e) {
 732         if (e == 2)
 733             array.push(5);
 734
 735         result ~= e;
 736     });
 737
 738     assert(array[] == expected);
 739     assert(result == expected);
 740 }
 741
 742 /**
 743  * Iterates the given array and calls the given callable for each element.
 744  *
 745  * If `callable` returns `!= 0`, it will stop the iteration and return that
 746  * value, otherwise it will return 0.
 747  *
 748  * Use this instead of `foreach` when the array may expand during iteration.
 749  *
 750  * Params:
 751  *  callable = the callable to call for each element
 752  *  array = the array to iterate
 753  *
 754  * Returns: the last value returned by `callable`
 755  * See_Also: $(REF foreachDsymbol, dmd, dsymbol)
 756  */
 757 template each(alias callable, T)
 758 if (is(ReturnType!(typeof((T t) => callable(t))) == int))
 759 {
 760     int each(ref Array!T array)
 761     {
 762         // Do not use foreach, as the size of the array may expand during iteration
 763         for (size_t i = 0; i < array.length; ++i)
 764         {
 765             if (const result = callable(array[i]))
 766                 return result;
 767         }
 768
 769         return 0;
 770     }
 771
 772     int each(Array!T* array)
 773     {
 774         return array ? each!callable(*array) : 0;
 775     }
 776 }
 777
 778 ///
 779 @("iterate over an Array and stop the iteration") unittest
 780 {
 781     Array!int array;
 782
 783     foreach (e ; [2, 3, 4, 5])
 784         array.push(e);
 785
 786     int[] result;
 787     const returnValue = array.each!((e) {
 788         result ~= e;
 789
 790         if (e == 3)
 791             return 8;
 792
 793         return 0;
 794     });
 795
 796     assert(result == [2, 3]);
 797     assert(returnValue == 8);
 798 }
 799
 800 @("iterate over an Array") unittest
 801 {
 802     static immutable expected = [2, 3, 4, 5];
 803
 804     Array!int array;
 805
 806     foreach (e ; expected)
 807         array.push(e);
 808
 809     int[] result;
 810     const returnValue = array.each!((e) {
 811         result ~= e;
 812         return 0;
 813     });
 814
 815     assert(result == expected);
 816     assert(returnValue == 0);
 817 }
 818
 819 @("iterate over a pointer to an Array and stop the iteration") unittest
 820 {
 821     auto array = new Array!int;
 822
 823     foreach (e ; [2, 3, 4, 5])
 824         array.push(e);
 825
 826     int[] result;
 827     const returnValue = array.each!((e) {
 828         result ~= e;
 829
 830         if (e == 3)
 831             return 9;
 832
 833         return 0;
 834     });
 835
 836     assert(result == [2, 3]);
 837     assert(returnValue == 9);
 838 }
 839
 840 @("iterate while appending to the array being iterated and stop the iteration") unittest
 841 {
 842     Array!int array;
 843
 844     foreach (e ; [2, 3])
 845         array.push(e);
 846
 847     int[] result;
 848
 849     const returnValue = array.each!((e) {
 850         if (e == 2)
 851             array.push(1);
 852
 853         result ~= e;
 854
 855         if (e == 1)
 856             return 7;
 857
 858         return 0;
 859     });
 860
 861     static immutable expected = [2, 3, 1];
 862
 863     assert(array[] == expected);
 864     assert(result == expected);
 865     assert(returnValue == 7);
 866 }
 867
 868 /// Returns: A static array constructed from `array`.
 869 pragma(inline, true) T[n] staticArray(T, size_t n)(auto ref T[n] array)
 870 {
 871     return array;
 872 }
 873
 874 ///
 875 pure nothrow @safe @nogc unittest
 876 {
 877     enum a = [0, 1].staticArray;
 878     static assert(is(typeof(a) == int[2]));
 879     static assert(a == [0, 1]);
 880 }
 881
 882 /// Returns: `true` if the two given ranges are equal
 883 bool equal(Range1, Range2)(Range1 range1, Range2 range2)
 884 {
 885     template isArray(T)
 886     {
 887         static if (is(T U : U[]))
 888             enum isArray = true;
 889
 890         else
 891             enum isArray = false;
 892     }
 893
 894     static if (isArray!Range1 && isArray!Range2 && is(typeof(range1 == range2)))
 895         return range1 == range2;
 896
 897     else
 898     {
 899         static if (hasLength!Range1 && hasLength!Range2 && is(typeof(r1.length == r2.length)))
 900         {
 901             if (range1.length != range2.length)
 902                 return false;
 903         }
 904
 905         for (; !range1.empty; range1.popFront(), range2.popFront())
 906         {
 907             if (range2.empty)
 908                 return false;
 909
 910             if (range1.front != range2.front)
 911                 return false;
 912         }
 913
 914         return range2.empty;
 915     }
 916 }
 917
 918 ///
 919 pure nothrow @nogc @safe unittest
 920 {
 921     enum a = [ 1, 2, 4, 3 ].staticArray;
 922     static assert(!equal(a[], a[1..$]));
 923     static assert(equal(a[], a[]));
 924
 925     // different types
 926     enum b = [ 1.0, 2, 4, 3].staticArray;
 927     static assert(!equal(a[], b[1..$]));
 928     static assert(equal(a[], b[]));
 929 }
 930
 931 pure nothrow @safe unittest
 932 {
 933     static assert(equal([1, 2, 3].map!(x => x * 2), [1, 2, 3].map!(x => x * 2)));
 934
 935     static assert(!equal([1, 2].map!(x => x * 2), [1, 2, 3].map!(x => x * 2)));
 936 }
 937
 938 /**
 939  * Lazily filters the given range based on the given predicate.
 940  *
 941  * Returns: a range containing only elements for which the predicate returns
 942  *  `true`
 943  */
 944 auto filter(alias predicate, Range)(Range range)
 945 if (isInputRange!(Unqual!Range) && isPredicateOf!(predicate, ElementType!Range))
 946 {
 947     return Filter!(predicate, Range)(range);
 948 }
 949
 950 ///
 951 pure nothrow @safe @nogc unittest
 952 {
 953     enum a = [1, 2, 3, 4].staticArray;
 954     enum result = a[].filter!(e => e > 2);
 955
 956     enum expected = [3, 4].staticArray;
 957     static assert(result.equal(expected[]));
 958 }
 959
 960 private struct Filter(alias predicate, Range)
 961 {
 962     private Range range;
 963     private bool primed;
 964
 965     private void prime()
 966     {
 967         if (primed)
 968             return;
 969
 970         while (!range.empty && !predicate(range.front))
 971             range.popFront();
 972
 973         primed = true;
 974     }
 975
 976     @property bool empty()
 977     {
 978         prime();
 979         return range.empty;
 980     }
 981
 982     @property auto front()
 983     {
 984         assert(!range.empty);
 985         prime();
 986         return range.front;
 987     }
 988
 989     void popFront()
 990     {
 991         assert(!range.empty);
 992         prime();
 993
 994         do
 995         {
 996             range.popFront();
 997         } while (!range.empty && !predicate(range.front));
 998     }
 999
1000     auto opSlice()
1001     {
1002         return this;
1003     }
1004 }
1005
1006 /**
1007  * Lazily iterates the given range and calls the given callable for each element.
1008  *
1009  * Returns: a range containing the result of each call to `callable`
1010  */
1011 auto map(alias callable, Range)(Range range)
1012 if (isInputRange!(Unqual!Range) && isCallableWith!(callable, ElementType!Range))
1013 {
1014     return Map!(callable, Range)(range);
1015 }
1016
1017 ///
1018 pure nothrow @safe @nogc unittest
1019 {
1020     enum a = [1, 2, 3, 4].staticArray;
1021     enum expected = [2, 4, 6, 8].staticArray;
1022
1023     enum result = a[].map!(e => e * 2);
1024     static assert(result.equal(expected[]));
1025 }
1026
1027 private struct Map(alias callable, Range)
1028 {
1029     private Range range;
1030
1031     @property bool empty()
1032     {
1033         return range.empty;
1034     }
1035
1036     @property auto front()
1037     {
1038         assert(!range.empty);
1039         return callable(range.front);
1040     }
1041
1042     void popFront()
1043     {
1044         assert(!range.empty);
1045         range.popFront();
1046     }
1047
1048     static if (hasLength!Range)
1049     {
1050         @property auto length()
1051         {
1052             return range.length;
1053         }
1054
1055         alias opDollar = length;
1056     }
1057 }
1058
1059 /// Returns: the length of the given range.
1060 auto walkLength(Range)(Range range)
1061 if (isInputRange!Range )
1062 {
1063     static if (hasLength!Range)
1064         return range.length;
1065     else
1066     {
1067         size_t result;
1068         for (; !range.empty; range.popFront())
1069             ++result;
1070         return result;
1071     }
1072 }
1073
1074 ///
1075 pure nothrow @safe @nogc unittest
1076 {
1077     enum a = [1, 2, 3, 4].staticArray;
1078     static assert(a[].walkLength == 4);
1079
1080     enum c = a[].filter!(e => e > 2);
1081     static assert(c.walkLength == 2);
1082 }
1083
1084 /// Evaluates to the element type of `R`.
1085 template ElementType(R)
1086 {
1087     static if (is(typeof(R.init.front.init) T))
1088         alias ElementType = T;
1089     else
1090         alias ElementType = void;
1091 }
1092
1093 /// Evaluates to `true` if the given type satisfy the input range interface.
1094 enum isInputRange(R) =
1095     is(typeof(R.init) == R)
1096     && is(ReturnType!(typeof((R r) => r.empty)) == bool)
1097     && is(typeof((return ref R r) => r.front))
1098     && !is(ReturnType!(typeof((R r) => r.front)) == void)
1099     && is(typeof((R r) => r.popFront));
1100
1101 /// Evaluates to `true` if `func` can be called with a value of `T` and returns
1102 /// a value that is convertible to `bool`.
1103 enum isPredicateOf(alias func, T) = is(typeof((T t) => !func(t)));
1104
1105 /// Evaluates to `true` if `func` be called withl a value of `T`.
1106 enum isCallableWith(alias func, T) =
1107     __traits(compiles, { auto _ = (T t) => func(t); });
1108
1109 private:
1110
1111 template ReturnType(T)
1112 {
1113     static if (is(T R == return))
1114         alias ReturnType = R;
1115     else
1116         static assert(false, "argument is not a function");
1117 }
1118
1119 alias Unqual(T) = ReturnType!(typeof((T t) => cast() t));
1120
1121 template hasLength(Range)
1122 {
1123     static if (is(typeof(((Range* r) => r.length)(null)) Length))
1124         enum hasLength = is(Length == size_t);
1125     else
1126         enum hasLength = false;
1127 }
1128
1129 /// Implements the range interface primitive `front` for built-in arrays.
1130 @property ref inout(T) front(T)(return scope inout(T)[] a) pure nothrow @nogc @safe
1131 {
1132     assert(a.length, "Attempting to fetch the front of an empty array of " ~ T.stringof);
1133     return a[0];
1134 }
1135
1136 ///
1137 pure nothrow @nogc @safe unittest
1138 {
1139     enum a = [1, 2, 3].staticArray;
1140     static assert(a[].front == 1);
1141 }
1142
1143 /// Implements the range interface primitive `empty` for types that obey $(LREF hasLength) property
1144 @property bool empty(T)(auto ref scope T a)
1145 if (is(typeof(a.length) : size_t))
1146 {
1147     return !a.length;
1148 }
1149
1150 ///
1151 pure nothrow @nogc @safe unittest
1152 {
1153     enum a = [1, 2, 3].staticArray;
1154
1155     static assert(!a.empty);
1156     static assert(a[3 .. $].empty);
1157 }
1158
1159 pure nothrow @safe unittest
1160 {
1161     int[string] b;
1162     assert(b.empty);
1163     b["zero"] = 0;
1164     assert(!b.empty);
1165 }
1166
1167 /// Implements the range interface primitive `popFront` for built-in arrays.
1168 void popFront(T)(/*scope*/ ref inout(T)[] array) pure nothrow @nogc @safe
1169 {                // does not compile with GDC 9 if this is `scope`
1170     assert(array.length, "Attempting to popFront() past the end of an array of " ~ T.stringof);
1171     array = array[1 .. $];
1172 }
1173
1174 ///
1175 pure nothrow @nogc @safe unittest
1176 {
1177     auto a = [1, 2, 3].staticArray;
1178     auto b = a[];
1179     auto expected = [2, 3].staticArray;
1180
1181     b.popFront();
1182     assert(b == expected[]);
1183 }