1
2 /**
3 * Dynamic array implementation.
4 *
5 * Copyright: Copyright (C) 1999-2021 by The D Language Foundation, All Rights Reserved
6 * Authors: $(LINK2 http://www.digitalmars.com, Walter Bright)
7 * License: $(LINK2 http://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
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", (int)length, (int)data.length, (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
348 unittest
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
374 unittest
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
394 unittest
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 */
439 void 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 }
452 unittest
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 */
485 T[] 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
500 unittest
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
514 unittest
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`
530 private 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
540 unittest
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 */
606 template each(alias callable, T)
607 if (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 */
695 template each(alias callable, T)
696 if (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`.
807 pragma(inline, true) T[n] staticArray(T, size_t n)(auto ref T[n] array)
808 {
809 return array;
810 }
811
812 ///
813 pure 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
821 bool 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 ///
857 pure 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
869 pure 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 */
882 auto filter(alias predicate, Range)(Range range)
883 if (isInputRange!(Unqual!Range) && isPredicateOf!(predicate, ElementType!Range))
884 {
885 return Filter!(predicate, Range)(range);
886 }
887
888 ///
889 pure 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
898 private 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 */
949 auto map(alias callable, Range)(Range range)
950 if (isInputRange!(Unqual!Range) && isCallableWith!(callable, ElementType!Range))
951 {
952 return Map!(callable, Range)(range);
953 }
954
955 ///
956 pure 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
965 private 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.
998 auto walkLength(Range)(Range range)
999 if (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 ///
1013 pure 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`.
1023 template 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.
1032 enum 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`.
1041 enum isPredicateOf(alias func, T) = is(typeof((T t) => !func(t)));
1042
1043 /// Evaluates to `true` if `func` be called withl a value of `T`.
1044 enum isCallableWith(alias func, T) =
1045 __traits(compiles, { auto _ = (T t) => func(t); });
1046
1047 private:
1048
1049 template 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
1057 alias Unqual(T) = ReturnType!(typeof((T t) => cast() t));
1058
1059 template 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 ///
1075 pure 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)
1083 if (is(typeof(a.length) : size_t))
1084 {
1085 return !a.length;
1086 }
1087
1088 ///
1089 pure 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
1097 pure 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.
1106 void 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 ///
1113 pure 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 }