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