The OpenD Programming Language

1 // Written in the D programming language.
2 /**
3 Functions and types that manipulate built-in arrays and associative arrays.
4 
5 This module provides all kinds of functions to create, manipulate or convert arrays:
6 
7 $(SCRIPT inhibitQuickIndex = 1;)
8 $(DIVC quickindex,
9 $(BOOKTABLE ,
10 $(TR $(TH Function Name) $(TH Description)
11 )
12     $(TR $(TD $(LREF array))
13         $(TD Returns a copy of the input in a newly allocated dynamic array.
14     ))
15     $(TR $(TD $(LREF appender))
16         $(TD Returns a new $(LREF Appender) or $(LREF RefAppender) initialized with a given array.
17     ))
18     $(TR $(TD $(LREF assocArray))
19         $(TD Returns a newly allocated associative array from a range of key/value tuples.
20     ))
21     $(TR $(TD $(LREF byPair))
22         $(TD Construct a range iterating over an associative array by key/value tuples.
23     ))
24     $(TR $(TD $(LREF insertInPlace))
25         $(TD Inserts into an existing array at a given position.
26     ))
27     $(TR $(TD $(LREF join))
28         $(TD Concatenates a range of ranges into one array.
29     ))
30     $(TR $(TD $(LREF minimallyInitializedArray))
31         $(TD Returns a new array of type `T`.
32     ))
33     $(TR $(TD $(LREF replace))
34         $(TD Returns a new array with all occurrences of a certain subrange replaced.
35     ))
36     $(TR $(TD $(LREF replaceFirst))
37         $(TD Returns a new array with the first occurrence of a certain subrange replaced.
38     ))
39     $(TR $(TD $(LREF replaceInPlace))
40         $(TD Replaces all occurrences of a certain subrange and puts the result into a given array.
41     ))
42     $(TR $(TD $(LREF replaceInto))
43         $(TD Replaces all occurrences of a certain subrange and puts the result into an output range.
44     ))
45     $(TR $(TD $(LREF replaceLast))
46         $(TD Returns a new array with the last occurrence of a certain subrange replaced.
47     ))
48     $(TR $(TD $(LREF replaceSlice))
49         $(TD Returns a new array with a given slice replaced.
50     ))
51     $(TR $(TD $(LREF replicate))
52         $(TD Creates a new array out of several copies of an input array or range.
53     ))
54     $(TR $(TD $(LREF sameHead))
55         $(TD Checks if the initial segments of two arrays refer to the same
56         place in memory.
57     ))
58     $(TR $(TD $(LREF sameTail))
59         $(TD Checks if the final segments of two arrays refer to the same place
60         in memory.
61     ))
62     $(TR $(TD $(LREF split))
63         $(TD Eagerly split a range or string into an array.
64     ))
65     $(TR $(TD $(LREF staticArray))
66         $(TD Creates a new static array from given data.
67     ))
68     $(TR $(TD $(LREF uninitializedArray))
69         $(TD Returns a new array of type `T` without initializing its elements.
70     ))
71 ))
72 
73 Copyright: Copyright Andrei Alexandrescu 2008- and Jonathan M Davis 2011-.
74 
75 License:   $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
76 
77 Authors:   $(HTTP erdani.org, Andrei Alexandrescu) and
78            $(HTTP jmdavisprog.com, Jonathan M Davis)
79 
80 Source: $(PHOBOSSRC std/array.d)
81 */
82 module std.array;
83 
84 import std.functional;
85 import std.meta;
86 import std.traits;
87 
88 import std.range.primitives;
89 public import std.range.primitives : save, empty, popFront, popBack, front, back;
90 
91 /**
92  * Allocates an array and initializes it with copies of the elements
93  * of range `r`.
94  *
95  * Narrow strings are handled as follows:
96  * - If autodecoding is turned on (default), then they are handled as a separate overload.
97  * - If autodecoding is turned off, then this is equivalent to duplicating the array.
98  *
99  * Params:
100  *      r = range (or aggregate with `opApply` function) whose elements are copied into the allocated array
101  * Returns:
102  *      allocated and initialized array
103  */
104 ForeachType!Range[] array(Range)(Range r)
105 if (isIterable!Range && !isAutodecodableString!Range && !isInfinite!Range)
106 {
107     if (__ctfe)
108     {
109         // Compile-time version to avoid memcpy calls.
110         // Also used to infer attributes of array().
111         typeof(return) result;
112         foreach (e; r)
113             result ~= e;
114         return result;
115     }
116 
117     alias E = ForeachType!Range;
118     static if (hasLength!Range)
119     {
120         const length = r.length;
121         if (length == 0)
122             return null;
123 
124         import core.internal.lifetime : emplaceRef;
125 
126         auto result = (() @trusted => uninitializedArray!(Unqual!E[])(length))();
127 
128         // Every element of the uninitialized array must be initialized
129         size_t cnt; //Number of elements that have been initialized
130         try
131         {
132             foreach (e; r)
133             {
134                 emplaceRef!E(result[cnt], e);
135                 ++cnt;
136             }
137         } catch (Exception e)
138         {
139             //https://issues.dlang.org/show_bug.cgi?id=22185
140             //Make any uninitialized elements safely destructible.
141             foreach (ref elem; result[cnt..$])
142             {
143                 import core.internal.lifetime : emplaceInitializer;
144                 emplaceInitializer(elem);
145             }
146             throw e;
147         }
148         /*
149             https://issues.dlang.org/show_bug.cgi?id=22673
150 
151             We preallocated an array, we should ensure that enough range elements
152             were gathered such that every slot in the array is filled. If not, the GC
153             will collect the allocated array, leading to the `length - cnt` left over elements
154             being collected too - despite their contents having no guarantee of destructibility.
155          */
156         assert(length == cnt,
157                "Range .length property was not equal to the length yielded by the range before becoming empty");
158         return (() @trusted => cast(E[]) result)();
159     }
160     else
161     {
162         auto a = appender!(E[])();
163         foreach (e; r)
164         {
165             a.put(e);
166         }
167         return a.data;
168     }
169 }
170 
171 /// ditto
172 ForeachType!(typeof((*Range).init))[] array(Range)(Range r)
173 if (is(Range == U*, U) && isIterable!U && !isAutodecodableString!Range && !isInfinite!Range)
174 {
175     return array(*r);
176 }
177 
178 ///
179 @safe pure nothrow unittest
180 {
181     auto a = array([1, 2, 3, 4, 5][]);
182     assert(a == [ 1, 2, 3, 4, 5 ]);
183 }
184 
185 @safe pure nothrow unittest
186 {
187     import std.algorithm.comparison : equal;
188     struct Foo
189     {
190         int a;
191     }
192     auto a = array([Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)][]);
193     assert(equal(a, [Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)]));
194 }
195 
196 @safe pure nothrow unittest
197 {
198     struct MyRange
199     {
200         enum front = 123;
201         enum empty = true;
202         void popFront() {}
203     }
204 
205     auto arr = (new MyRange).array;
206     assert(arr.empty);
207 }
208 
209 @safe pure nothrow unittest
210 {
211     immutable int[] a = [1, 2, 3, 4];
212     auto b = (&a).array;
213     assert(b == a);
214 }
215 
216 @safe pure nothrow unittest
217 {
218     import std.algorithm.comparison : equal;
219     struct Foo
220     {
221         int a;
222         noreturn opAssign(Foo)
223         {
224             assert(0);
225         }
226         auto opEquals(Foo foo)
227         {
228             return a == foo.a;
229         }
230     }
231     auto a = array([Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)][]);
232     assert(equal(a, [Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)]));
233 }
234 
235 // https://issues.dlang.org/show_bug.cgi?id=12315
236 @safe pure nothrow unittest
237 {
238     static struct Bug12315 { immutable int i; }
239     enum bug12315 = [Bug12315(123456789)].array();
240     static assert(bug12315[0].i == 123456789);
241 }
242 
243 @safe pure nothrow unittest
244 {
245     import std.range;
246     static struct S{int* p;}
247     auto a = array(immutable(S).init.repeat(5));
248     assert(a.length == 5);
249 }
250 
251 // https://issues.dlang.org/show_bug.cgi?id=18995
252 @system unittest
253 {
254     import core.memory : __delete;
255     int nAlive = 0;
256     struct S
257     {
258         bool alive;
259         this(int) { alive = true; ++nAlive; }
260         this(this) { nAlive += alive; }
261         ~this() { nAlive -= alive; alive = false; }
262     }
263 
264     import std.algorithm.iteration : map;
265     import std.range : iota;
266 
267     auto arr = iota(3).map!(a => S(a)).array;
268     assert(nAlive == 3);
269 
270     // No good way to ensure the GC frees this, just call the lifetime function
271     // directly.
272     __delete(arr);
273 
274     assert(nAlive == 0);
275 }
276 
277 @safe pure nothrow @nogc unittest
278 {
279     //Turn down infinity:
280     static assert(!is(typeof(
281         repeat(1).array()
282     )));
283 }
284 
285 // https://issues.dlang.org/show_bug.cgi?id=20937
286 @safe pure nothrow unittest
287 {
288     struct S {int* x;}
289     struct R
290     {
291         immutable(S) front;
292         bool empty;
293         @safe pure nothrow void popFront(){empty = true;}
294     }
295     R().array;
296 }
297 
298 /**
299 Convert a narrow autodecoding string to an array type that fully supports
300 random access.  This is handled as a special case and always returns an array
301 of `dchar`
302 
303 NOTE: This function is never used when autodecoding is turned off.
304 
305 Params:
306     str = `isNarrowString` to be converted to an array of `dchar`
307 Returns:
308     a `dchar[]`, `const(dchar)[]`, or `immutable(dchar)[]` depending on the constness of
309     the input.
310 */
311 CopyTypeQualifiers!(ElementType!String,dchar)[] array(String)(scope String str)
312 if (isAutodecodableString!String)
313 {
314     import std.utf : toUTF32;
315     auto temp = str.toUTF32;
316     /* Unsafe cast. Allowed because toUTF32 makes a new array
317        and copies all the elements.
318      */
319     return () @trusted { return cast(CopyTypeQualifiers!(ElementType!String, dchar)[]) temp; } ();
320 }
321 
322 ///
323 @safe pure nothrow unittest
324 {
325     import std.range.primitives : isRandomAccessRange;
326     import std.traits : isAutodecodableString;
327 
328     // note that if autodecoding is turned off, `array` will not transcode these.
329     static if (isAutodecodableString!string)
330         assert("Hello D".array == "Hello D"d);
331     else
332         assert("Hello D".array == "Hello D");
333 
334     static if (isAutodecodableString!wstring)
335         assert("Hello D"w.array == "Hello D"d);
336     else
337         assert("Hello D"w.array == "Hello D"w);
338 
339     static assert(isRandomAccessRange!dstring == true);
340 }
341 
342 @safe unittest
343 {
344     import std.conv : to;
345 
346     static struct TestArray { int x; string toString() @safe { return to!string(x); } }
347 
348     static struct OpAssign
349     {
350         uint num;
351         this(uint num) { this.num = num; }
352 
353         // Templating opAssign to make sure the bugs with opAssign being
354         // templated are fixed.
355         void opAssign(T)(T rhs) { this.num = rhs.num; }
356     }
357 
358     static struct OpApply
359     {
360         int opApply(scope int delegate(ref int) @safe dg)
361         {
362             int res;
363             foreach (i; 0 .. 10)
364             {
365                 res = dg(i);
366                 if (res) break;
367             }
368 
369             return res;
370         }
371     }
372 
373     auto a = array([1, 2, 3, 4, 5][]);
374     assert(a == [ 1, 2, 3, 4, 5 ]);
375 
376     auto b = array([TestArray(1), TestArray(2)][]);
377     assert(b == [TestArray(1), TestArray(2)]);
378 
379     class C
380     {
381         int x;
382         this(int y) { x = y; }
383         override string toString() const @safe { return to!string(x); }
384     }
385     auto c = array([new C(1), new C(2)][]);
386     assert(c[0].x == 1);
387     assert(c[1].x == 2);
388 
389     auto d = array([1.0, 2.2, 3][]);
390     assert(is(typeof(d) == double[]));
391     assert(d == [1.0, 2.2, 3]);
392 
393     auto e = [OpAssign(1), OpAssign(2)];
394     auto f = array(e);
395     assert(e == f);
396 
397     assert(array(OpApply.init) == [0,1,2,3,4,5,6,7,8,9]);
398     static if (isAutodecodableString!string)
399     {
400         assert(array("ABC") == "ABC"d);
401         assert(array("ABC".dup) == "ABC"d.dup);
402     }
403 }
404 
405 // https://issues.dlang.org/show_bug.cgi?id=8233
406 @safe pure nothrow unittest
407 {
408     assert(array("hello world"d) == "hello world"d);
409     immutable a = [1, 2, 3, 4, 5];
410     assert(array(a) == a);
411     const b = a;
412     assert(array(b) == a);
413 
414     //To verify that the opAssign branch doesn't get screwed up by using Unqual.
415     //EDIT: array no longer calls opAssign.
416     struct S
417     {
418         ref S opAssign(S)(const ref S rhs)
419         {
420             assert(0);
421         }
422 
423         int i;
424     }
425 
426     static foreach (T; AliasSeq!(S, const S, immutable S))
427     {{
428         auto arr = [T(1), T(2), T(3), T(4)];
429         assert(array(arr) == arr);
430     }}
431 }
432 
433 // https://issues.dlang.org/show_bug.cgi?id=9824
434 @safe pure nothrow unittest
435 {
436     static struct S
437     {
438         @disable void opAssign(S);
439         int i;
440     }
441     auto arr = [S(0), S(1), S(2)];
442     arr.array();
443 }
444 
445 // https://issues.dlang.org/show_bug.cgi?id=10220
446 @safe pure nothrow unittest
447 {
448     import std.algorithm.comparison : equal;
449     import std.exception;
450     import std.range : repeat;
451 
452     static struct S
453     {
454         int val;
455 
456         @disable this();
457         this(int v) { val = v; }
458     }
459     assertCTFEable!(
460     {
461         auto r = S(1).repeat(2).array();
462         assert(equal(r, [S(1), S(1)]));
463     });
464 }
465 //https://issues.dlang.org/show_bug.cgi?id=22673
466 @system unittest
467 {
468     struct LyingRange
469     {
470         enum size_t length = 100;
471         enum theRealLength = 50;
472         size_t idx = 0;
473         bool empty()
474         {
475             return idx <= theRealLength;
476         }
477         void popFront()
478         {
479             ++idx;
480         }
481         size_t front()
482         {
483             return idx;
484         }
485     }
486     static assert(hasLength!LyingRange);
487     LyingRange rng;
488     import std.exception : assertThrown;
489     assertThrown!Error(array(rng));
490 }
491 //https://issues.dlang.org/show_bug.cgi?id=22185
492 @system unittest
493 {
494     import std.stdio;
495     static struct ThrowingCopy
496     {
497         int x = 420;
498         this(ref return scope ThrowingCopy rhs)
499         {
500             rhs.x = 420;
501             //
502             throw new Exception("This throws");
503         }
504         ~this()
505         {
506             /*
507                 Any time this destructor runs, it should be running on "valid"
508                 data. This is is mimicked by having a .init other than 0 (the value the memory
509                 practically will be from the GC).
510             */
511             if (x != 420)
512             {
513                 //This will only trigger during GC finalization so avoid writefln for now.
514                 printf("Destructor failure in ThrowingCopy(%d) @ %p", x, &this);
515                 assert(x == 420, "unittest destructor failed");
516             }
517         }
518     }
519     static struct LyingThrowingRange
520     {
521         enum size_t length = 100;
522         enum size_t evilRealLength = 50;
523         size_t idx;
524         ThrowingCopy front()
525         {
526             return ThrowingCopy(12);
527         }
528         bool empty()
529         {
530             return idx == evilRealLength;
531         }
532         void popFront()
533         {
534             ++idx;
535         }
536     }
537     static assert(hasLength!LyingThrowingRange);
538     import std.exception : assertThrown;
539     {
540         assertThrown(array(LyingThrowingRange()));
541     }
542     import core.memory : GC;
543     /*
544         Force a collection early. Doesn't always actually finalize the bad objects
545         but trying to collect soon after the allocation is thrown away means any potential failures
546         will happen earlier.
547     */
548     GC.collect();
549 }
550 
551 /**
552 Returns a newly allocated associative array from a range of key/value tuples
553 or from a range of keys and a range of values.
554 
555 Params:
556     r = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
557     of tuples of keys and values.
558     keys = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of keys
559     values = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of values
560 
561 Returns:
562 
563     A newly allocated associative array out of elements of the input
564     range, which must be a range of tuples (Key, Value) or
565     a range of keys and a range of values. If given two ranges of unequal
566     lengths after the elements of the shorter are exhausted the remaining
567     elements of the longer will not be considered.
568     Returns a null associative array reference when given an empty range.
569     Duplicates: Associative arrays have unique keys. If r contains duplicate keys,
570     then the result will contain the value of the last pair for that key in r.
571 
572 See_Also: $(REF Tuple, std,typecons), $(REF zip, std,range)
573  */
574 
575 auto assocArray(Range)(Range r)
576 if (isInputRange!Range)
577 {
578     import std.typecons : isTuple;
579 
580     alias E = ElementType!Range;
581     static assert(isTuple!E, "assocArray: argument must be a range of tuples,"
582         ~" but was a range of "~E.stringof);
583     static assert(E.length == 2, "assocArray: tuple dimension must be 2");
584     alias KeyType = E.Types[0];
585     alias ValueType = E.Types[1];
586     static assert(isMutable!ValueType, "assocArray: value type must be mutable");
587 
588     ValueType[KeyType] aa;
589     foreach (ref t; r)
590         aa[t[0]] = t[1];
591     return aa;
592 }
593 
594 /// ditto
595 auto assocArray(Keys, Values)(Keys keys, Values values)
596 if (isInputRange!Values && isInputRange!Keys)
597 {
598     static if (isDynamicArray!Keys && isDynamicArray!Values
599         && !isNarrowString!Keys && !isNarrowString!Values)
600     {
601         void* aa;
602         {
603             // aaLiteral is nothrow when the destructors don't throw
604             static if (is(typeof(() nothrow
605             {
606                 import std.range : ElementType;
607                 import std.traits : hasElaborateDestructor;
608                 alias KeyElement = ElementType!Keys;
609                 static if (hasElaborateDestructor!KeyElement)
610                     KeyElement.init.__xdtor();
611 
612                 alias ValueElement = ElementType!Values;
613                 static if (hasElaborateDestructor!ValueElement)
614                     ValueElement.init.__xdtor();
615             })))
616             {
617                 scope(failure) assert(false, "aaLiteral must not throw");
618             }
619             if (values.length > keys.length)
620                 values = values[0 .. keys.length];
621             else if (keys.length > values.length)
622                 keys = keys[0 .. values.length];
623             aa = aaLiteral(keys, values);
624         }
625         alias Key = typeof(keys[0]);
626         alias Value = typeof(values[0]);
627         return (() @trusted => cast(Value[Key]) aa)();
628     }
629     else
630     {
631         // zip is not always able to infer nothrow
632         alias Key = ElementType!Keys;
633         alias Value = ElementType!Values;
634         static assert(isMutable!Value, "assocArray: value type must be mutable");
635         Value[Key] aa;
636         foreach (key; keys)
637         {
638             if (values.empty) break;
639 
640             // aa[key] is incorrectly not @safe if the destructor throws
641             // https://issues.dlang.org/show_bug.cgi?id=18592
642             static if (is(typeof(() @safe
643             {
644                 import std.range : ElementType;
645                 import std.traits : hasElaborateDestructor;
646                 alias KeyElement = ElementType!Keys;
647                 static if (hasElaborateDestructor!KeyElement)
648                     KeyElement.init.__xdtor();
649 
650                 alias ValueElement = ElementType!Values;
651                 static if (hasElaborateDestructor!ValueElement)
652                     ValueElement.init.__xdtor();
653             })))
654             {
655                 () @trusted {
656                     aa[key] = values.front;
657                 }();
658             }
659             else
660             {
661                 aa[key] = values.front;
662             }
663             values.popFront();
664         }
665         return aa;
666     }
667 }
668 
669 ///
670 @safe pure /*nothrow*/ unittest
671 {
672     import std.range : repeat, zip;
673     import std.typecons : tuple;
674     import std.range.primitives : autodecodeStrings;
675     auto a = assocArray(zip([0, 1, 2], ["a", "b", "c"])); // aka zipMap
676     static assert(is(typeof(a) == string[int]));
677     assert(a == [0:"a", 1:"b", 2:"c"]);
678 
679     auto b = assocArray([ tuple("foo", "bar"), tuple("baz", "quux") ]);
680     static assert(is(typeof(b) == string[string]));
681     assert(b == ["foo":"bar", "baz":"quux"]);
682 
683     static if (autodecodeStrings)
684         alias achar = dchar;
685     else
686         alias achar = immutable(char);
687     auto c = assocArray("ABCD", true.repeat);
688     static assert(is(typeof(c) == bool[achar]));
689     bool[achar] expected = ['D':true, 'A':true, 'B':true, 'C':true];
690     assert(c == expected);
691 }
692 
693 // Cannot be version (StdUnittest) - recursive instantiation error
694 // https://issues.dlang.org/show_bug.cgi?id=11053
695 @safe pure nothrow unittest
696 {
697     import std.typecons;
698     static assert(!__traits(compiles, [ 1, 2, 3 ].assocArray()));
699     static assert(!__traits(compiles, [ tuple("foo", "bar", "baz") ].assocArray()));
700     static assert(!__traits(compiles, [ tuple("foo") ].assocArray()));
701     assert([ tuple("foo", "bar") ].assocArray() == ["foo": "bar"]);
702 }
703 
704 // https://issues.dlang.org/show_bug.cgi?id=13909
705 @safe pure nothrow unittest
706 {
707     import std.typecons;
708     auto a = [tuple!(const string, string)("foo", "bar")];
709     auto b = [tuple!(string, const string)("foo", "bar")];
710     assert(a == b);
711     assert(assocArray(a) == [cast(const(string)) "foo": "bar"]);
712     static assert(!__traits(compiles, assocArray(b)));
713 }
714 
715 // https://issues.dlang.org/show_bug.cgi?id=5502
716 @safe pure nothrow unittest
717 {
718     auto a = assocArray([0, 1, 2], ["a", "b", "c"]);
719     static assert(is(typeof(a) == string[int]));
720     assert(a == [0:"a", 1:"b", 2:"c"]);
721 
722     auto b = assocArray([0, 1, 2], [3L, 4, 5]);
723     static assert(is(typeof(b) == long[int]));
724     assert(b == [0: 3L, 1: 4, 2: 5]);
725 }
726 
727 // https://issues.dlang.org/show_bug.cgi?id=5502
728 @safe pure unittest
729 {
730     import std.algorithm.iteration : filter, map;
731     import std.range : enumerate;
732     import std.range.primitives : autodecodeStrings;
733 
734     auto r = "abcde".enumerate.filter!(a => a.index == 2);
735     auto a = assocArray(r.map!(a => a.value), r.map!(a => a.index));
736     static if (autodecodeStrings)
737         alias achar = dchar;
738     else
739         alias achar = immutable(char);
740     static assert(is(typeof(a) == size_t[achar]));
741     assert(a == [achar('c'): size_t(2)]);
742 }
743 
744 @safe nothrow pure unittest
745 {
746     import std.range : iota;
747     auto b = assocArray(3.iota, 3.iota(6));
748     static assert(is(typeof(b) == int[int]));
749     assert(b == [0: 3, 1: 4, 2: 5]);
750 
751     b = assocArray([0, 1, 2], [3, 4, 5]);
752     assert(b == [0: 3, 1: 4, 2: 5]);
753 }
754 
755 @safe unittest
756 {
757     struct ThrowingElement
758     {
759         int i;
760         static bool b;
761         ~this(){
762             if (b)
763                 throw new Exception("");
764         }
765     }
766     static assert(!__traits(compiles, () nothrow { assocArray([ThrowingElement()], [0]);}));
767     assert(assocArray([ThrowingElement()], [0]) == [ThrowingElement(): 0]);
768 
769     static assert(!__traits(compiles, () nothrow { assocArray([0], [ThrowingElement()]);}));
770     assert(assocArray([0], [ThrowingElement()]) == [0: ThrowingElement()]);
771 
772     import std.range : iota;
773     static assert(!__traits(compiles, () nothrow { assocArray(1.iota, [ThrowingElement()]);}));
774     assert(assocArray(1.iota, [ThrowingElement()]) == [0: ThrowingElement()]);
775 }
776 
777 @system unittest
778 {
779     import std.range : iota;
780     struct UnsafeElement
781     {
782         int i;
783         static bool b;
784         ~this(){
785             int[] arr;
786             void* p = arr.ptr + 1; // unsafe
787         }
788     }
789     static assert(!__traits(compiles, () @safe { assocArray(1.iota, [UnsafeElement()]);}));
790     assert(assocArray(1.iota, [UnsafeElement()]) == [0: UnsafeElement()]);
791 }
792 
793 /**
794 Construct a range iterating over an associative array by key/value tuples.
795 
796 Params:
797     aa = The associative array to iterate over.
798 
799 Returns: A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
800 of Tuple's of key and value pairs from the given associative array. The members
801 of each pair can be accessed by name (`.key` and `.value`). or by integer
802 index (0 and 1 respectively).
803 */
804 auto byPair(AA)(AA aa)
805 if (isAssociativeArray!AA)
806 {
807     import std.algorithm.iteration : map;
808     import std.typecons : tuple;
809 
810     return aa.byKeyValue
811         .map!(pair => tuple!("key", "value")(pair.key, pair.value));
812 }
813 
814 ///
815 @safe pure nothrow unittest
816 {
817     import std.algorithm.sorting : sort;
818     import std.typecons : tuple, Tuple;
819 
820     auto aa = ["a": 1, "b": 2, "c": 3];
821     Tuple!(string, int)[] pairs;
822 
823     // Iteration over key/value pairs.
824     foreach (pair; aa.byPair)
825     {
826         if (pair.key == "b")
827             pairs ~= tuple("B", pair.value);
828         else
829             pairs ~= pair;
830     }
831 
832     // Iteration order is implementation-dependent, so we should sort it to get
833     // a fixed order.
834     pairs.sort();
835     assert(pairs == [
836         tuple("B", 2),
837         tuple("a", 1),
838         tuple("c", 3)
839     ]);
840 }
841 
842 @safe pure nothrow unittest
843 {
844     import std.typecons : tuple, Tuple;
845     import std.meta : AliasSeq;
846 
847     auto aa = ["a":2];
848     auto pairs = aa.byPair();
849 
850     alias PT = typeof(pairs.front);
851     static assert(is(PT : Tuple!(string,int)));
852     static assert(PT.fieldNames == AliasSeq!("key", "value"));
853     static assert(isForwardRange!(typeof(pairs)));
854 
855     assert(!pairs.empty);
856     assert(pairs.front == tuple("a", 2));
857 
858     auto savedPairs = pairs.save;
859 
860     pairs.popFront();
861     assert(pairs.empty);
862     assert(!savedPairs.empty);
863     assert(savedPairs.front == tuple("a", 2));
864 }
865 
866 // https://issues.dlang.org/show_bug.cgi?id=17711
867 @safe pure nothrow unittest
868 {
869     const(int[string]) aa = [ "abc": 123 ];
870 
871     // Ensure that byKeyValue is usable with a const AA.
872     auto kv = aa.byKeyValue;
873     assert(!kv.empty);
874     assert(kv.front.key == "abc" && kv.front.value == 123);
875     kv.popFront();
876     assert(kv.empty);
877 
878     // Ensure byPair is instantiable with const AA.
879     auto r = aa.byPair;
880     static assert(isInputRange!(typeof(r)));
881     assert(!r.empty && r.front[0] == "abc" && r.front[1] == 123);
882     r.popFront();
883     assert(r.empty);
884 }
885 
886 private template blockAttribute(T)
887 {
888     import core.memory;
889     static if (hasIndirections!(T) || is(T == void))
890     {
891         enum blockAttribute = 0;
892     }
893     else
894     {
895         enum blockAttribute = GC.BlkAttr.NO_SCAN;
896     }
897 }
898 
899 @safe unittest
900 {
901     import core.memory : UGC = GC;
902     static assert(!(blockAttribute!void & UGC.BlkAttr.NO_SCAN));
903 }
904 
905 // Returns the number of dimensions in an array T.
906 private template nDimensions(T)
907 {
908     static if (isArray!T)
909     {
910         enum nDimensions = 1 + nDimensions!(typeof(T.init[0]));
911     }
912     else
913     {
914         enum nDimensions = 0;
915     }
916 }
917 
918 @safe unittest
919 {
920     static assert(nDimensions!(uint[]) == 1);
921     static assert(nDimensions!(float[][]) == 2);
922 }
923 
924 /++
925 Returns a new array of type `T` allocated on the garbage collected heap
926 without initializing its elements. This can be a useful optimization if every
927 element will be immediately initialized. `T` may be a multidimensional
928 array. In this case sizes may be specified for any number of dimensions from 0
929 to the number in `T`.
930 
931 uninitializedArray is `nothrow` and weakly `pure`.
932 
933 uninitializedArray is `@system` if the uninitialized element type has pointers.
934 
935 Params:
936     T = The type of the resulting array elements
937     sizes = The length dimension(s) of the resulting array
938 Returns:
939     An array of `T` with `I.length` dimensions.
940 +/
941 auto uninitializedArray(T, I...)(I sizes) nothrow @system
942 if (isDynamicArray!T && allSatisfy!(isIntegral, I) && hasIndirections!(ElementEncodingType!T))
943 {
944     enum isSize_t(E) = is (E : size_t);
945     alias toSize_t(E) = size_t;
946 
947     static assert(allSatisfy!(isSize_t, I),
948         "Argument types in "~I.stringof~" are not all convertible to size_t: "
949         ~Filter!(templateNot!(isSize_t), I).stringof);
950 
951     //Eagerlly transform non-size_t into size_t to avoid template bloat
952     alias ST = staticMap!(toSize_t, I);
953 
954     return arrayAllocImpl!(false, T, ST)(sizes);
955 }
956 
957 /// ditto
958 auto uninitializedArray(T, I...)(I sizes) nothrow @trusted
959 if (isDynamicArray!T && allSatisfy!(isIntegral, I) && !hasIndirections!(ElementEncodingType!T))
960 {
961     enum isSize_t(E) = is (E : size_t);
962     alias toSize_t(E) = size_t;
963 
964     static assert(allSatisfy!(isSize_t, I),
965         "Argument types in "~I.stringof~" are not all convertible to size_t: "
966         ~Filter!(templateNot!(isSize_t), I).stringof);
967 
968     //Eagerlly transform non-size_t into size_t to avoid template bloat
969     alias ST = staticMap!(toSize_t, I);
970 
971     return arrayAllocImpl!(false, T, ST)(sizes);
972 }
973 ///
974 @system nothrow pure unittest
975 {
976     double[] arr = uninitializedArray!(double[])(100);
977     assert(arr.length == 100);
978 
979     double[][] matrix = uninitializedArray!(double[][])(42, 31);
980     assert(matrix.length == 42);
981     assert(matrix[0].length == 31);
982 
983     char*[] ptrs = uninitializedArray!(char*[])(100);
984     assert(ptrs.length == 100);
985 }
986 
987 /++
988 Returns a new array of type `T` allocated on the garbage collected heap.
989 
990 Partial initialization is done for types with indirections, for preservation
991 of memory safety. Note that elements will only be initialized to 0, but not
992 necessarily the element type's `.init`.
993 
994 minimallyInitializedArray is `nothrow` and weakly `pure`.
995 
996 Params:
997     T = The type of the array elements
998     sizes = The length dimension(s) of the resulting array
999 Returns:
1000     An array of `T` with `I.length` dimensions.
1001 +/
1002 auto minimallyInitializedArray(T, I...)(I sizes) nothrow @trusted
1003 if (isDynamicArray!T && allSatisfy!(isIntegral, I))
1004 {
1005     enum isSize_t(E) = is (E : size_t);
1006     alias toSize_t(E) = size_t;
1007 
1008     static assert(allSatisfy!(isSize_t, I),
1009         "Argument types in "~I.stringof~" are not all convertible to size_t: "
1010         ~Filter!(templateNot!(isSize_t), I).stringof);
1011     //Eagerlly transform non-size_t into size_t to avoid template bloat
1012     alias ST = staticMap!(toSize_t, I);
1013 
1014     return arrayAllocImpl!(true, T, ST)(sizes);
1015 }
1016 
1017 ///
1018 @safe pure nothrow unittest
1019 {
1020     import std.algorithm.comparison : equal;
1021     import std.range : repeat;
1022 
1023     auto arr = minimallyInitializedArray!(int[])(42);
1024     assert(arr.length == 42);
1025 
1026     // Elements aren't necessarily initialized to 0, so don't do this:
1027     // assert(arr.equal(0.repeat(42)));
1028     // If that is needed, initialize the array normally instead:
1029     auto arr2 = new int[42];
1030     assert(arr2.equal(0.repeat(42)));
1031 }
1032 
1033 @safe pure nothrow unittest
1034 {
1035     cast(void) minimallyInitializedArray!(int[][][][][])();
1036     double[] arr = minimallyInitializedArray!(double[])(100);
1037     assert(arr.length == 100);
1038 
1039     double[][] matrix = minimallyInitializedArray!(double[][])(42);
1040     assert(matrix.length == 42);
1041     foreach (elem; matrix)
1042     {
1043         assert(elem.ptr is null);
1044     }
1045 }
1046 
1047 // from rt/lifetime.d
1048 private extern(C) void[] _d_newarrayU(const TypeInfo ti, size_t length) pure nothrow;
1049 
1050 // from rt/tracegc.d
1051 version (D_ProfileGC)
1052 private extern (C) void[] _d_newarrayUTrace(string file, size_t line,
1053     string funcname, const scope TypeInfo ti, size_t length) pure nothrow;
1054 
1055 private auto arrayAllocImpl(bool minimallyInitialized, T, I...)(I sizes) nothrow
1056 {
1057     static assert(I.length <= nDimensions!T,
1058         I.length.stringof~"dimensions specified for a "~nDimensions!T.stringof~" dimensional array.");
1059 
1060     alias E = ElementEncodingType!T;
1061 
1062     E[] ret;
1063 
1064     static if (I.length != 0)
1065     {
1066         static assert(is(I[0] == size_t), "I[0] must be of type size_t not "
1067                 ~ I[0].stringof);
1068         alias size = sizes[0];
1069     }
1070 
1071     static if (I.length == 1)
1072     {
1073         if (__ctfe)
1074         {
1075             static if (__traits(compiles, new E[](size)))
1076                 ret = new E[](size);
1077             else static if (__traits(compiles, ret ~= E.init))
1078             {
1079                 try
1080                 {
1081                     //Issue: if E has an impure postblit, then all of arrayAllocImpl
1082                     //Will be impure, even during non CTFE.
1083                     foreach (i; 0 .. size)
1084                         ret ~= E.init;
1085                 }
1086                 catch (Exception e)
1087                     assert(0, e.msg);
1088             }
1089             else
1090                 assert(0, "No postblit nor default init on " ~ E.stringof ~
1091                     ": At least one is required for CTFE.");
1092         }
1093         else
1094         {
1095             import core.stdc.string : memset;
1096 
1097             /+
1098               NOTES:
1099               _d_newarrayU is part of druntime, and creates an uninitialized
1100               block, just like GC.malloc. However, it also sets the appropriate
1101               bits, and sets up the block as an appendable array of type E[],
1102               which will inform the GC how to destroy the items in the block
1103               when it gets collected.
1104 
1105               _d_newarrayU returns a void[], but with the length set according
1106               to E.sizeof.
1107             +/
1108             version (D_ProfileGC)
1109             {
1110                 // FIXME: file, line, function should be propagated from the
1111                 // caller, not here.
1112                 *(cast(void[]*)&ret) = _d_newarrayUTrace(__FILE__, __LINE__,
1113                     __FUNCTION__, typeid(E[]), size);
1114             }
1115             else
1116                 *(cast(void[]*)&ret) = _d_newarrayU(typeid(E[]), size);
1117             static if (minimallyInitialized && hasIndirections!E)
1118                 // _d_newarrayU would have asserted if the multiplication below
1119                 // had overflowed, so we don't have to check it again.
1120                 memset(ret.ptr, 0, E.sizeof * ret.length);
1121         }
1122     }
1123     else static if (I.length > 1)
1124     {
1125         ret = arrayAllocImpl!(false, E[])(size);
1126         foreach (ref elem; ret)
1127             elem = arrayAllocImpl!(minimallyInitialized, E)(sizes[1..$]);
1128     }
1129 
1130     return ret;
1131 }
1132 
1133 @safe nothrow pure unittest
1134 {
1135     auto s1 = uninitializedArray!(int[])();
1136     auto s2 = minimallyInitializedArray!(int[])();
1137     assert(s1.length == 0);
1138     assert(s2.length == 0);
1139 }
1140 
1141 // https://issues.dlang.org/show_bug.cgi?id=9803
1142 @safe nothrow pure unittest
1143 {
1144     auto a = minimallyInitializedArray!(int*[])(1);
1145     assert(a[0] == null);
1146     auto b = minimallyInitializedArray!(int[][])(1);
1147     assert(b[0].empty);
1148     auto c = minimallyInitializedArray!(int*[][])(1, 1);
1149     assert(c[0][0] == null);
1150 }
1151 
1152 // https://issues.dlang.org/show_bug.cgi?id=10637
1153 @safe pure nothrow unittest
1154 {
1155     static struct S
1156     {
1157         static struct I{int i; alias i this;}
1158         int* p;
1159         this() @disable;
1160         this(int i)
1161         {
1162             p = &(new I(i)).i;
1163         }
1164         this(this)
1165         {
1166             p = &(new I(*p)).i;
1167         }
1168         ~this()
1169         {
1170             // note, this assert is invalid -- a struct should always be able
1171             // to run its dtor on the .init value, I'm leaving it here
1172             // commented out because the original test case had it. I'm not
1173             // sure what it's trying to prove.
1174             //
1175             // What happens now that minimallyInitializedArray adds the
1176             // destructor run to the GC, is that this assert would fire in the
1177             // GC, which triggers an invalid memory operation.
1178             //assert(p != null);
1179         }
1180     }
1181     auto a = minimallyInitializedArray!(S[])(1);
1182     assert(a[0].p == null);
1183     enum b = minimallyInitializedArray!(S[])(1);
1184     assert(b[0].p == null);
1185 }
1186 
1187 @safe pure nothrow unittest
1188 {
1189     static struct S1
1190     {
1191         this() @disable;
1192         this(this) @disable;
1193     }
1194     auto a1 = minimallyInitializedArray!(S1[][])(2, 2);
1195     assert(a1);
1196     static struct S2
1197     {
1198         this() @disable;
1199         //this(this) @disable;
1200     }
1201     auto a2 = minimallyInitializedArray!(S2[][])(2, 2);
1202     assert(a2);
1203     enum b2 = minimallyInitializedArray!(S2[][])(2, 2);
1204     assert(b2 !is null);
1205     static struct S3
1206     {
1207         //this() @disable;
1208         this(this) @disable;
1209     }
1210     auto a3 = minimallyInitializedArray!(S3[][])(2, 2);
1211     assert(a3);
1212     enum b3 = minimallyInitializedArray!(S3[][])(2, 2);
1213     assert(b3 !is null);
1214 }
1215 
1216 /++
1217 Returns the overlapping portion, if any, of two arrays. Unlike `equal`,
1218 `overlap` only compares the pointers and lengths in the
1219 ranges, not the values referred by them. If `r1` and `r2` have an
1220 overlapping slice, returns that slice. Otherwise, returns the null
1221 slice.
1222 
1223 Params:
1224     a = The first array to compare
1225     b = The second array to compare
1226 Returns:
1227     The overlapping portion of the two arrays.
1228 +/
1229 CommonType!(T[], U[]) overlap(T, U)(T[] a, U[] b) @trusted
1230 if (is(typeof(a.ptr < b.ptr) == bool))
1231 {
1232     import std.algorithm.comparison : min;
1233 
1234     auto end = min(a.ptr + a.length, b.ptr + b.length);
1235     // CTFE requires pairing pointer comparisons, which forces a
1236     // slightly inefficient implementation.
1237     if (a.ptr <= b.ptr && b.ptr < a.ptr + a.length)
1238     {
1239         return b.ptr[0 .. end - b.ptr];
1240     }
1241 
1242     if (b.ptr <= a.ptr && a.ptr < b.ptr + b.length)
1243     {
1244         return a.ptr[0 .. end - a.ptr];
1245     }
1246 
1247     return null;
1248 }
1249 
1250 ///
1251 @safe pure nothrow unittest
1252 {
1253     int[] a = [ 10, 11, 12, 13, 14 ];
1254     int[] b = a[1 .. 3];
1255     assert(overlap(a, b) == [ 11, 12 ]);
1256     b = b.dup;
1257     // overlap disappears even though the content is the same
1258     assert(overlap(a, b).empty);
1259 
1260     static test()() @nogc
1261     {
1262         auto a = "It's three o'clock"d;
1263         auto b = a[5 .. 10];
1264         return b.overlap(a);
1265     }
1266 
1267     //works at compile-time
1268     static assert(test == "three"d);
1269 }
1270 
1271 @safe pure nothrow unittest
1272 {
1273     static void test(L, R)(L l, R r)
1274     {
1275         assert(overlap(l, r) == [ 100, 12 ]);
1276 
1277         assert(overlap(l, l[0 .. 2]) is l[0 .. 2]);
1278         assert(overlap(l, l[3 .. 5]) is l[3 .. 5]);
1279         assert(overlap(l[0 .. 2], l) is l[0 .. 2]);
1280         assert(overlap(l[3 .. 5], l) is l[3 .. 5]);
1281     }
1282 
1283     int[] a = [ 10, 11, 12, 13, 14 ];
1284     int[] b = a[1 .. 3];
1285     a[1] = 100;
1286 
1287     immutable int[] c = a.idup;
1288     immutable int[] d = c[1 .. 3];
1289 
1290     test(a, b);
1291     assert(overlap(a, b.dup).empty);
1292     test(c, d);
1293     assert(overlap(c, d.dup.idup).empty);
1294 }
1295 
1296  // https://issues.dlang.org/show_bug.cgi?id=9836
1297 @safe pure nothrow unittest
1298 {
1299     // range primitives for array should work with alias this types
1300     struct Wrapper
1301     {
1302         int[] data;
1303         alias data this;
1304 
1305         @property Wrapper save() { return this; }
1306     }
1307     auto w = Wrapper([1,2,3,4]);
1308     std.array.popFront(w); // should work
1309 
1310     static assert(isInputRange!Wrapper);
1311     static assert(isForwardRange!Wrapper);
1312     static assert(isBidirectionalRange!Wrapper);
1313     static assert(isRandomAccessRange!Wrapper);
1314 }
1315 
1316 private void copyBackwards(T)(T[] src, T[] dest)
1317 {
1318     import core.stdc.string : memmove;
1319     import std.format : format;
1320 
1321     assert(src.length == dest.length, format!
1322             "src.length %s must equal dest.length %s"(src.length, dest.length));
1323 
1324     if (!__ctfe || hasElaborateCopyConstructor!T)
1325     {
1326         /* insertInPlace relies on dest being uninitialized, so no postblits allowed,
1327          * as this is a MOVE that overwrites the destination, not a COPY.
1328          * BUG: insertInPlace will not work with ctfe and postblits
1329          */
1330         memmove(dest.ptr, src.ptr, src.length * T.sizeof);
1331     }
1332     else
1333     {
1334         immutable len = src.length;
1335         for (size_t i = len; i-- > 0;)
1336         {
1337             dest[i] = src[i];
1338         }
1339     }
1340 }
1341 
1342 /++
1343     Inserts `stuff` (which must be an input range or any number of
1344     implicitly convertible items) in `array` at position `pos`.
1345 
1346     Params:
1347         array = The array that `stuff` will be inserted into.
1348         pos   = The position in `array` to insert the `stuff`.
1349         stuff = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives),
1350         or any number of implicitly convertible items to insert into `array`.
1351  +/
1352 void insertInPlace(T, U...)(ref T[] array, size_t pos, U stuff)
1353 if (!isSomeString!(T[])
1354     && allSatisfy!(isInputRangeOrConvertible!T, U) && U.length > 0)
1355 {
1356     static if (allSatisfy!(isInputRangeWithLengthOrConvertible!T, U))
1357     {
1358         import core.internal.lifetime : emplaceRef;
1359 
1360         immutable oldLen = array.length;
1361 
1362         size_t to_insert = 0;
1363         foreach (i, E; U)
1364         {
1365             static if (is(E : T)) //a single convertible value, not a range
1366                 to_insert += 1;
1367             else
1368                 to_insert += stuff[i].length;
1369         }
1370         if (to_insert)
1371         {
1372             array.length += to_insert;
1373 
1374             // Takes arguments array, pos, stuff
1375             // Spread apart array[] at pos by moving elements
1376             (() @trusted { copyBackwards(array[pos .. oldLen], array[pos+to_insert..$]); })();
1377 
1378             // Initialize array[pos .. pos+to_insert] with stuff[]
1379             auto j = 0;
1380             foreach (i, E; U)
1381             {
1382                 static if (is(E : T))
1383                 {
1384                     emplaceRef!T(array[pos + j++], stuff[i]);
1385                 }
1386                 else
1387                 {
1388                     foreach (v; stuff[i])
1389                     {
1390                         emplaceRef!T(array[pos + j++], v);
1391                     }
1392                 }
1393             }
1394         }
1395     }
1396     else
1397     {
1398         // stuff has some InputRanges in it that don't have length
1399         // assume that stuff to be inserted is typically shorter
1400         // then the array that can be arbitrary big
1401         // TODO: needs a better implementation as there is no need to build an _array_
1402         // a singly-linked list of memory blocks (rope, etc.) will do
1403         auto app = appender!(T[])();
1404         foreach (i, E; U)
1405             app.put(stuff[i]);
1406         insertInPlace(array, pos, app.data);
1407     }
1408 }
1409 
1410 /// Ditto
1411 void insertInPlace(T, U...)(ref T[] array, size_t pos, U stuff)
1412 if (isSomeString!(T[]) && allSatisfy!(isCharOrStringOrDcharRange, U))
1413 {
1414     static if (is(Unqual!T == T)
1415         && allSatisfy!(isInputRangeWithLengthOrConvertible!dchar, U))
1416     {
1417         import std.utf : codeLength, byDchar;
1418         // mutable, can do in place
1419         //helper function: re-encode dchar to Ts and store at *ptr
1420         static T* putDChar(T* ptr, dchar ch)
1421         {
1422             static if (is(T == dchar))
1423             {
1424                 *ptr++ = ch;
1425                 return ptr;
1426             }
1427             else
1428             {
1429                 import std.utf : encode;
1430                 T[dchar.sizeof/T.sizeof] buf;
1431                 immutable len = encode(buf, ch);
1432                 final switch (len)
1433                 {
1434                     static if (T.sizeof == char.sizeof)
1435                     {
1436                 case 4:
1437                         ptr[3] = buf[3];
1438                         goto case;
1439                 case 3:
1440                         ptr[2] = buf[2];
1441                         goto case;
1442                     }
1443                 case 2:
1444                     ptr[1] = buf[1];
1445                     goto case;
1446                 case 1:
1447                     ptr[0] = buf[0];
1448                 }
1449                 ptr += len;
1450                 return ptr;
1451             }
1452         }
1453         size_t to_insert = 0;
1454         //count up the number of *codeunits* to insert
1455         foreach (i, E; U)
1456             to_insert += codeLength!T(stuff[i]);
1457         array.length += to_insert;
1458 
1459         @trusted static void moveToRight(T[] arr, size_t gap)
1460         {
1461             static assert(!hasElaborateCopyConstructor!T,
1462                     "T must not have an elaborate copy constructor");
1463             import core.stdc.string : memmove;
1464             if (__ctfe)
1465             {
1466                 for (size_t i = arr.length - gap; i; --i)
1467                     arr[gap + i - 1] = arr[i - 1];
1468             }
1469             else
1470                 memmove(arr.ptr + gap, arr.ptr, (arr.length - gap) * T.sizeof);
1471         }
1472         moveToRight(array[pos .. $], to_insert);
1473         auto ptr = array.ptr + pos;
1474         foreach (i, E; U)
1475         {
1476             static if (is(E : dchar))
1477             {
1478                 ptr = putDChar(ptr, stuff[i]);
1479             }
1480             else
1481             {
1482                 foreach (ch; stuff[i].byDchar)
1483                     ptr = putDChar(ptr, ch);
1484             }
1485         }
1486         assert(ptr == array.ptr + pos + to_insert, "(ptr == array.ptr + pos + to_insert) is false");
1487     }
1488     else
1489     {
1490         // immutable/const, just construct a new array
1491         auto app = appender!(T[])();
1492         app.put(array[0 .. pos]);
1493         foreach (i, E; U)
1494             app.put(stuff[i]);
1495         app.put(array[pos..$]);
1496         array = app.data;
1497     }
1498 }
1499 
1500 ///
1501 @safe pure unittest
1502 {
1503     int[] a = [ 1, 2, 3, 4 ];
1504     a.insertInPlace(2, [ 1, 2 ]);
1505     assert(a == [ 1, 2, 1, 2, 3, 4 ]);
1506     a.insertInPlace(3, 10u, 11);
1507     assert(a == [ 1, 2, 1, 10, 11, 2, 3, 4]);
1508 
1509     union U
1510     {
1511         float a = 3.0;
1512         int b;
1513     }
1514 
1515     U u1 = { b : 3 };
1516     U u2 = { b : 4 };
1517     U u3 = { b : 5 };
1518     U[] unionArr = [u2, u3];
1519     unionArr.insertInPlace(2, [u1]);
1520     assert(unionArr == [u2, u3, u1]);
1521     unionArr.insertInPlace(0, [u3, u2]);
1522     assert(unionArr == [u3, u2, u2, u3, u1]);
1523 
1524     static class C
1525     {
1526         int a;
1527         float b;
1528 
1529         this(int a, float b) { this.a = a; this.b = b; }
1530     }
1531 
1532     C c1 = new C(42, 1.0);
1533     C c2 = new C(0, 0.0);
1534     C c3 = new C(int.max, float.init);
1535 
1536     C[] classArr = [c1, c2, c3];
1537     insertInPlace(classArr, 3, [c2, c3]);
1538     C[5] classArr1 = classArr;
1539     assert(classArr1 == [c1, c2, c3, c2, c3]);
1540     insertInPlace(classArr, 0, c3, c1);
1541     C[7] classArr2 = classArr;
1542     assert(classArr2 == [c3, c1, c1, c2, c3, c2, c3]);
1543 }
1544 
1545 //constraint helpers
1546 private template isInputRangeWithLengthOrConvertible(E)
1547 {
1548     template isInputRangeWithLengthOrConvertible(R)
1549     {
1550         //hasLength not defined for char[], wchar[] and dchar[]
1551         enum isInputRangeWithLengthOrConvertible =
1552             (isInputRange!R && is(typeof(R.init.length))
1553                 && is(ElementType!R : E))  || is(R : E);
1554     }
1555 }
1556 
1557 //ditto
1558 private template isCharOrStringOrDcharRange(T)
1559 {
1560     enum isCharOrStringOrDcharRange = isSomeString!T || isSomeChar!T ||
1561         (isInputRange!T && is(ElementType!T : dchar));
1562 }
1563 
1564 //ditto
1565 private template isInputRangeOrConvertible(E)
1566 {
1567     template isInputRangeOrConvertible(R)
1568     {
1569         enum isInputRangeOrConvertible =
1570             (isInputRange!R && is(ElementType!R : E))  || is(R : E);
1571     }
1572 }
1573 
1574 @system unittest
1575 {
1576     // @system due to insertInPlace
1577     import core.exception;
1578     import std.algorithm.comparison : equal;
1579     import std.algorithm.iteration : filter;
1580     import std.conv : to;
1581     import std.exception;
1582 
1583 
1584     bool test(T, U, V)(T orig, size_t pos, U toInsert, V result)
1585     {
1586         {
1587             static if (is(T == typeof(T.init.dup)))
1588                 auto a = orig.dup;
1589             else
1590                 auto a = orig.idup;
1591 
1592             a.insertInPlace(pos, toInsert);
1593             if (!equal(a, result))
1594                 return false;
1595         }
1596 
1597         static if (isInputRange!U)
1598         {
1599             orig.insertInPlace(pos, filter!"true"(toInsert));
1600             return equal(orig, result);
1601         }
1602         else
1603             return true;
1604     }
1605 
1606 
1607     assert(test([1, 2, 3, 4], 0, [6, 7], [6, 7, 1, 2, 3, 4]));
1608     assert(test([1, 2, 3, 4], 2, [8, 9], [1, 2, 8, 9, 3, 4]));
1609     assert(test([1, 2, 3, 4], 4, [10, 11], [1, 2, 3, 4, 10, 11]));
1610 
1611     assert(test([1, 2, 3, 4], 0, 22, [22, 1, 2, 3, 4]));
1612     assert(test([1, 2, 3, 4], 2, 23, [1, 2, 23, 3, 4]));
1613     assert(test([1, 2, 3, 4], 4, 24, [1, 2, 3, 4, 24]));
1614 
1615     void testStr(T, U)(string file = __FILE__, size_t line = __LINE__)
1616     {
1617 
1618         auto l = to!T("hello");
1619         auto r = to!U(" વિશ્વ");
1620 
1621         enforce(test(l, 0, r, " વિશ્વhello"),
1622                 new AssertError("testStr failure 1", file, line));
1623         enforce(test(l, 3, r, "hel વિશ્વlo"),
1624                 new AssertError("testStr failure 2", file, line));
1625         enforce(test(l, l.length, r, "hello વિશ્વ"),
1626                 new AssertError("testStr failure 3", file, line));
1627     }
1628 
1629     static foreach (T; AliasSeq!(char, wchar, dchar,
1630         immutable(char), immutable(wchar), immutable(dchar)))
1631     {
1632         static foreach (U; AliasSeq!(char, wchar, dchar,
1633             immutable(char), immutable(wchar), immutable(dchar)))
1634         {
1635             testStr!(T[], U[])();
1636         }
1637 
1638     }
1639 
1640     // variadic version
1641     bool testVar(T, U...)(T orig, size_t pos, U args)
1642     {
1643         static if (is(T == typeof(T.init.dup)))
1644             auto a = orig.dup;
1645         else
1646             auto a = orig.idup;
1647         auto result = args[$-1];
1648 
1649         a.insertInPlace(pos, args[0..$-1]);
1650         if (!equal(a, result))
1651             return false;
1652         return true;
1653     }
1654     assert(testVar([1, 2, 3, 4], 0, 6, 7u, [6, 7, 1, 2, 3, 4]));
1655     assert(testVar([1L, 2, 3, 4], 2, 8, 9L, [1, 2, 8, 9, 3, 4]));
1656     assert(testVar([1L, 2, 3, 4], 4, 10L, 11, [1, 2, 3, 4, 10, 11]));
1657     assert(testVar([1L, 2, 3, 4], 4, [10, 11], 40L, 42L,
1658                     [1, 2, 3, 4, 10, 11, 40, 42]));
1659     assert(testVar([1L, 2, 3, 4], 4, 10, 11, [40L, 42],
1660                     [1, 2, 3, 4, 10, 11, 40, 42]));
1661     assert(testVar("t".idup, 1, 'e', 's', 't', "test"));
1662     assert(testVar("!!"w.idup, 1, "\u00e9ll\u00f4", 'x', "TTT"w, 'y',
1663                     "!\u00e9ll\u00f4xTTTy!"));
1664     assert(testVar("flipflop"d.idup, 4, '_',
1665                     "xyz"w, '\U00010143', '_', "abc"d, "__",
1666                     "flip_xyz\U00010143_abc__flop"));
1667 }
1668 
1669 @system unittest
1670 {
1671     import std.algorithm.comparison : equal;
1672     // insertInPlace interop with postblit
1673     static struct Int
1674     {
1675         int* payload;
1676         this(int k)
1677         {
1678             payload = new int;
1679             *payload = k;
1680         }
1681         this(this)
1682         {
1683             int* np = new int;
1684             *np = *payload;
1685             payload = np;
1686         }
1687         ~this()
1688         {
1689             if (payload)
1690                 *payload = 0; //'destroy' it
1691         }
1692         @property int getPayload(){ return *payload; }
1693         alias getPayload this;
1694     }
1695 
1696     Int[] arr = [Int(1), Int(4), Int(5)];
1697     assert(arr[0] == 1);
1698     insertInPlace(arr, 1, Int(2), Int(3));
1699     assert(equal(arr, [1, 2, 3, 4, 5]));  //check it works with postblit
1700 }
1701 
1702 @safe unittest
1703 {
1704     import std.exception;
1705     assertCTFEable!(
1706     {
1707         int[] a = [1, 2];
1708         a.insertInPlace(2, 3);
1709         a.insertInPlace(0, -1, 0);
1710         return a == [-1, 0, 1, 2, 3];
1711     });
1712 }
1713 
1714 // https://issues.dlang.org/show_bug.cgi?id=6874
1715 @system unittest
1716 {
1717     import core.memory;
1718     // allocate some space
1719     byte[] a;
1720     a.length = 1;
1721 
1722     // fill it
1723     a.length = a.capacity;
1724 
1725     // write beyond
1726     byte[] b = a[$ .. $];
1727     b.insertInPlace(0, a);
1728 
1729     // make sure that reallocation has happened
1730     assert(GC.addrOf(&b[0]) == GC.addrOf(&b[$-1]));
1731 }
1732 
1733 
1734 /++
1735     Returns whether the `front`s of `lhs` and `rhs` both refer to the
1736     same place in memory, making one of the arrays a slice of the other which
1737     starts at index `0`.
1738 
1739     Params:
1740         lhs = the first array to compare
1741         rhs = the second array to compare
1742     Returns:
1743         `true` if $(D lhs.ptr == rhs.ptr), `false` otherwise.
1744   +/
1745 @safe
1746 pure nothrow @nogc bool sameHead(T)(in T[] lhs, in T[] rhs)
1747 {
1748     return lhs.ptr == rhs.ptr;
1749 }
1750 
1751 ///
1752 @safe pure nothrow unittest
1753 {
1754     auto a = [1, 2, 3, 4, 5];
1755     auto b = a[0 .. 2];
1756 
1757     assert(a.sameHead(b));
1758 }
1759 
1760 
1761 /++
1762     Returns whether the `back`s of `lhs` and `rhs` both refer to the
1763     same place in memory, making one of the arrays a slice of the other which
1764     end at index `$`.
1765 
1766     Params:
1767         lhs = the first array to compare
1768         rhs = the second array to compare
1769     Returns:
1770         `true` if both arrays are the same length and $(D lhs.ptr == rhs.ptr),
1771         `false` otherwise.
1772   +/
1773 @trusted
1774 pure nothrow @nogc bool sameTail(T)(in T[] lhs, in T[] rhs)
1775 {
1776     return lhs.ptr + lhs.length == rhs.ptr + rhs.length;
1777 }
1778 
1779 ///
1780 @safe pure nothrow unittest
1781 {
1782     auto a = [1, 2, 3, 4, 5];
1783     auto b = a[3..$];
1784 
1785     assert(a.sameTail(b));
1786 }
1787 
1788 @safe pure nothrow unittest
1789 {
1790     static foreach (T; AliasSeq!(int[], const(int)[], immutable(int)[], const int[], immutable int[]))
1791     {{
1792         T a = [1, 2, 3, 4, 5];
1793         T b = a;
1794         T c = a[1 .. $];
1795         T d = a[0 .. 1];
1796         T e = null;
1797 
1798         assert(sameHead(a, a));
1799         assert(sameHead(a, b));
1800         assert(!sameHead(a, c));
1801         assert(sameHead(a, d));
1802         assert(!sameHead(a, e));
1803 
1804         assert(sameTail(a, a));
1805         assert(sameTail(a, b));
1806         assert(sameTail(a, c));
1807         assert(!sameTail(a, d));
1808         assert(!sameTail(a, e));
1809 
1810         //verifies R-value compatibilty
1811         assert(a.sameHead(a[0 .. 0]));
1812         assert(a.sameTail(a[$ .. $]));
1813     }}
1814 }
1815 
1816 /**
1817 Params:
1818     s = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1819     or a dynamic array
1820     n = number of times to repeat `s`
1821 
1822 Returns:
1823     An array that consists of `s` repeated `n` times. This function allocates, fills, and
1824     returns a new array.
1825 
1826 See_Also:
1827     For a lazy version, refer to $(REF repeat, std,range).
1828  */
1829 ElementEncodingType!S[] replicate(S)(S s, size_t n)
1830 if (isDynamicArray!S)
1831 {
1832     alias RetType = ElementEncodingType!S[];
1833 
1834     // Optimization for return join(std.range.repeat(s, n));
1835     if (n == 0)
1836         return RetType.init;
1837     if (n == 1)
1838         return cast(RetType) s;
1839     auto r = new Unqual!(typeof(s[0]))[n * s.length];
1840     if (s.length == 1)
1841         r[] = s[0];
1842     else
1843     {
1844         immutable len = s.length, nlen = n * len;
1845         for (size_t i = 0; i < nlen; i += len)
1846         {
1847             r[i .. i + len] = s[];
1848         }
1849     }
1850     return r;
1851 }
1852 
1853 /// ditto
1854 ElementType!S[] replicate(S)(S s, size_t n)
1855 if (isInputRange!S && !isDynamicArray!S)
1856 {
1857     import std.range : repeat;
1858     return join(std.range.repeat(s, n));
1859 }
1860 
1861 
1862 ///
1863 @safe unittest
1864 {
1865     auto a = "abc";
1866     auto s = replicate(a, 3);
1867 
1868     assert(s == "abcabcabc");
1869 
1870     auto b = [1, 2, 3];
1871     auto c = replicate(b, 3);
1872 
1873     assert(c == [1, 2, 3, 1, 2, 3, 1, 2, 3]);
1874 
1875     auto d = replicate(b, 0);
1876 
1877     assert(d == []);
1878 }
1879 
1880 @safe unittest
1881 {
1882     import std.conv : to;
1883 
1884     static foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[]))
1885     {{
1886         immutable S t = "abc";
1887 
1888         assert(replicate(to!S("1234"), 0) is null);
1889         assert(replicate(to!S("1234"), 0) is null);
1890         assert(replicate(to!S("1234"), 1) == "1234");
1891         assert(replicate(to!S("1234"), 2) == "12341234");
1892         assert(replicate(to!S("1"), 4) == "1111");
1893         assert(replicate(t, 3) == "abcabcabc");
1894         assert(replicate(cast(S) null, 4) is null);
1895     }}
1896 }
1897 
1898 /++
1899 Eagerly splits `range` into an array, using `sep` as the delimiter.
1900 
1901 When no delimiter is provided, strings are split into an array of words,
1902 using whitespace as delimiter.
1903 Runs of whitespace are merged together (no empty words are produced).
1904 
1905 The `range` must be a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives).
1906 The separator can be a value of the same type as the elements in `range`
1907 or it can be another forward `range`.
1908 
1909 Params:
1910     s = the string to split by word if no separator is given
1911     range = the range to split
1912     sep = a value of the same type as the elements of `range` or another
1913     isTerminator = a predicate that splits the range when it returns `true`.
1914 
1915 Returns:
1916     An array containing the divided parts of `range` (or the words of `s`).
1917 
1918 See_Also:
1919 $(REF splitter, std,algorithm,iteration) for a lazy version without allocating memory.
1920 
1921 $(REF splitter, std,regex) for a version that splits using a regular
1922 expression defined separator.
1923 +/
1924 S[] split(S)(S s) @safe pure
1925 if (isSomeString!S)
1926 {
1927     size_t istart;
1928     bool inword = false;
1929     auto result = appender!(S[]);
1930 
1931     foreach (i, dchar c ; s)
1932     {
1933         import std.uni : isWhite;
1934         if (isWhite(c))
1935         {
1936             if (inword)
1937             {
1938                 put(result, s[istart .. i]);
1939                 inword = false;
1940             }
1941         }
1942         else
1943         {
1944             if (!inword)
1945             {
1946                 istart = i;
1947                 inword = true;
1948             }
1949         }
1950     }
1951     if (inword)
1952         put(result, s[istart .. $]);
1953     return result.data;
1954 }
1955 
1956 ///
1957 @safe unittest
1958 {
1959     import std.uni : isWhite;
1960     assert("Learning,D,is,fun".split(",") == ["Learning", "D", "is", "fun"]);
1961     assert("Learning D is fun".split!isWhite == ["Learning", "D", "is", "fun"]);
1962     assert("Learning D is fun".split(" D ") == ["Learning", "is fun"]);
1963 }
1964 
1965 ///
1966 @safe unittest
1967 {
1968     string str = "Hello World!";
1969     assert(str.split == ["Hello", "World!"]);
1970 
1971     string str2 = "Hello\t\tWorld\t!";
1972     assert(str2.split == ["Hello", "World", "!"]);
1973 }
1974 
1975 @safe unittest
1976 {
1977     import std.conv : to;
1978     import std.format : format;
1979     import std.typecons;
1980 
1981     static auto makeEntry(S)(string l, string[] r)
1982     {return tuple(l.to!S(), r.to!(S[])());}
1983 
1984     static foreach (S; AliasSeq!(string, wstring, dstring,))
1985     {{
1986         auto entries =
1987         [
1988             makeEntry!S("", []),
1989             makeEntry!S(" ", []),
1990             makeEntry!S("hello", ["hello"]),
1991             makeEntry!S(" hello ", ["hello"]),
1992             makeEntry!S("  h  e  l  l  o ", ["h", "e", "l", "l", "o"]),
1993             makeEntry!S("peter\t\npaul\rjerry", ["peter", "paul", "jerry"]),
1994             makeEntry!S(" \t\npeter paul\tjerry \n", ["peter", "paul", "jerry"]),
1995             makeEntry!S("\u2000日\u202F本\u205F語\u3000", ["日", "本", "語"]),
1996             makeEntry!S("  哈・郎博尔德}    ___一个", ["哈・郎博尔德}", "___一个"])
1997         ];
1998         foreach (entry; entries)
1999             assert(entry[0].split() == entry[1], format("got: %s, expected: %s.", entry[0].split(), entry[1]));
2000     }}
2001 
2002     //Just to test that an immutable is split-able
2003     immutable string s = " \t\npeter paul\tjerry \n";
2004     assert(split(s) == ["peter", "paul", "jerry"]);
2005 }
2006 
2007 @safe unittest //purity, ctfe ...
2008 {
2009     import std.exception;
2010     void dg() @safe pure {
2011         assert(split("hello world"c) == ["hello"c, "world"c]);
2012         assert(split("hello world"w) == ["hello"w, "world"w]);
2013         assert(split("hello world"d) == ["hello"d, "world"d]);
2014     }
2015     dg();
2016     assertCTFEable!dg;
2017 }
2018 
2019 ///
2020 @safe unittest
2021 {
2022     assert(split("hello world") == ["hello","world"]);
2023     assert(split("192.168.0.1", ".") == ["192", "168", "0", "1"]);
2024 
2025     auto a = split([1, 2, 3, 4, 5, 1, 2, 3, 4, 5], [2, 3]);
2026     assert(a == [[1], [4, 5, 1], [4, 5]]);
2027 }
2028 
2029 ///ditto
2030 auto split(Range, Separator)(Range range, Separator sep)
2031 if (isForwardRange!Range && (
2032     is(typeof(ElementType!Range.init == Separator.init)) ||
2033     is(typeof(ElementType!Range.init == ElementType!Separator.init)) && isForwardRange!Separator
2034     ))
2035 {
2036     import std.algorithm.iteration : splitter;
2037     return range.splitter(sep).array;
2038 }
2039 ///ditto
2040 auto split(alias isTerminator, Range)(Range range)
2041 if (isForwardRange!Range && is(typeof(unaryFun!isTerminator(range.front))))
2042 {
2043     import std.algorithm.iteration : splitter;
2044     return range.splitter!isTerminator.array;
2045 }
2046 
2047 @safe unittest
2048 {
2049     import std.algorithm.comparison : cmp;
2050     import std.conv;
2051 
2052     static foreach (S; AliasSeq!(string, wstring, dstring,
2053                     immutable(string), immutable(wstring), immutable(dstring),
2054                     char[], wchar[], dchar[],
2055                     const(char)[], const(wchar)[], const(dchar)[],
2056                     const(char[]), immutable(char[])))
2057     {{
2058         S s = to!S(",peter,paul,jerry,");
2059 
2060         auto words = split(s, ",");
2061         assert(words.length == 5, text(words.length));
2062         assert(cmp(words[0], "") == 0);
2063         assert(cmp(words[1], "peter") == 0);
2064         assert(cmp(words[2], "paul") == 0);
2065         assert(cmp(words[3], "jerry") == 0);
2066         assert(cmp(words[4], "") == 0);
2067 
2068         auto s1 = s[0 .. s.length - 1];   // lop off trailing ','
2069         words = split(s1, ",");
2070         assert(words.length == 4);
2071         assert(cmp(words[3], "jerry") == 0);
2072 
2073         auto s2 = s1[1 .. s1.length];   // lop off leading ','
2074         words = split(s2, ",");
2075         assert(words.length == 3);
2076         assert(cmp(words[0], "peter") == 0);
2077 
2078         auto s3 = to!S(",,peter,,paul,,jerry,,");
2079 
2080         words = split(s3, ",,");
2081         assert(words.length == 5);
2082         assert(cmp(words[0], "") == 0);
2083         assert(cmp(words[1], "peter") == 0);
2084         assert(cmp(words[2], "paul") == 0);
2085         assert(cmp(words[3], "jerry") == 0);
2086         assert(cmp(words[4], "") == 0);
2087 
2088         auto s4 = s3[0 .. s3.length - 2];    // lop off trailing ',,'
2089         words = split(s4, ",,");
2090         assert(words.length == 4);
2091         assert(cmp(words[3], "jerry") == 0);
2092 
2093         auto s5 = s4[2 .. s4.length];    // lop off leading ',,'
2094         words = split(s5, ",,");
2095         assert(words.length == 3);
2096         assert(cmp(words[0], "peter") == 0);
2097     }}
2098 }
2099 
2100 /+
2101    Conservative heuristic to determine if a range can be iterated cheaply.
2102    Used by `join` in decision to do an extra iteration of the range to
2103    compute the resultant length. If iteration is not cheap then precomputing
2104    length could be more expensive than using `Appender`.
2105 
2106    For now, we only assume arrays are cheap to iterate.
2107  +/
2108 private enum bool hasCheapIteration(R) = isArray!R;
2109 
2110 /++
2111    Eagerly concatenates all of the ranges in `ror` together (with the GC)
2112    into one array using `sep` as the separator if present.
2113 
2114    Params:
2115         ror = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
2116         of input ranges
2117         sep = An input range, or a single element, to join the ranges on
2118 
2119    Returns:
2120         An array of elements
2121 
2122    See_Also:
2123         For a lazy version, see $(REF joiner, std,algorithm,iteration)
2124   +/
2125 ElementEncodingType!(ElementType!RoR)[] join(RoR, R)(RoR ror, R sep)
2126 if (isInputRange!RoR &&
2127     isInputRange!(Unqual!(ElementType!RoR)) &&
2128     isInputRange!R &&
2129     (is(immutable ElementType!(ElementType!RoR) == immutable ElementType!R) ||
2130      (isSomeChar!(ElementType!(ElementType!RoR)) && isSomeChar!(ElementType!R))
2131     ))
2132 {
2133     alias RetType = typeof(return);
2134     alias RetTypeElement = Unqual!(ElementEncodingType!RetType);
2135     alias RoRElem = ElementType!RoR;
2136 
2137     if (ror.empty)
2138         return RetType.init;
2139 
2140     // Constraint only requires input range for sep.
2141     // This converts sep to an array (forward range) if it isn't one,
2142     // and makes sure it has the same string encoding for string types.
2143     static if (isSomeString!RetType &&
2144                !is(immutable ElementEncodingType!RetType == immutable ElementEncodingType!R))
2145     {
2146         import std.conv : to;
2147         auto sepArr = to!RetType(sep);
2148     }
2149     else static if (!isArray!R)
2150         auto sepArr = array(sep);
2151     else
2152         alias sepArr = sep;
2153 
2154     static if (hasCheapIteration!RoR && (hasLength!RoRElem || isNarrowString!RoRElem))
2155     {
2156         import core.internal.lifetime : emplaceRef;
2157         size_t length;          // length of result array
2158         size_t rorLength;       // length of range ror
2159         foreach (r; ror.save)
2160         {
2161             length += r.length;
2162             ++rorLength;
2163         }
2164         if (!rorLength)
2165             return null;
2166         length += (rorLength - 1) * sepArr.length;
2167 
2168         auto result = (() @trusted => uninitializedArray!(RetTypeElement[])(length))();
2169         size_t len;
2170         foreach (e; ror.front)
2171             emplaceRef(result[len++], e);
2172         ror.popFront();
2173         foreach (r; ror)
2174         {
2175             foreach (e; sepArr)
2176                 emplaceRef(result[len++], e);
2177             foreach (e; r)
2178                 emplaceRef(result[len++], e);
2179         }
2180         assert(len == result.length);
2181         return (() @trusted => cast(RetType) result)();
2182     }
2183     else
2184     {
2185         auto result = appender!RetType();
2186         put(result, ror.front);
2187         ror.popFront();
2188         for (; !ror.empty; ror.popFront())
2189         {
2190             put(result, sepArr);
2191             put(result, ror.front);
2192         }
2193         return result.data;
2194     }
2195 }
2196 
2197 // https://issues.dlang.org/show_bug.cgi?id=14230
2198 @safe unittest
2199 {
2200    string[] ary = ["","aa","bb","cc"]; // leaded by _empty_ element
2201    assert(ary.join(" @") == " @aa @bb @cc"); // OK in 2.067b1 and olders
2202 }
2203 
2204 // https://issues.dlang.org/show_bug.cgi?id=21337
2205 @system unittest
2206 {
2207     import std.algorithm.iteration : map;
2208 
2209     static class Once
2210     {
2211         bool empty;
2212 
2213         void popFront()
2214         {
2215             empty = true;
2216         }
2217 
2218         int front()
2219         {
2220             return 0;
2221         }
2222     }
2223 
2224     assert([1, 2].map!"[a]".join(new Once) == [1, 0, 2]);
2225 }
2226 
2227 /// Ditto
2228 ElementEncodingType!(ElementType!RoR)[] join(RoR, E)(RoR ror, scope E sep)
2229 if (isInputRange!RoR &&
2230     isInputRange!(Unqual!(ElementType!RoR)) &&
2231     ((is(E : ElementType!(ElementType!RoR))) ||
2232      (!autodecodeStrings && isSomeChar!(ElementType!(ElementType!RoR)) &&
2233       isSomeChar!E)))
2234 {
2235     alias RetType = typeof(return);
2236     alias RetTypeElement = Unqual!(ElementEncodingType!RetType);
2237     alias RoRElem = ElementType!RoR;
2238 
2239     if (ror.empty)
2240         return RetType.init;
2241 
2242     static if (hasCheapIteration!RoR && (hasLength!RoRElem || isNarrowString!RoRElem))
2243     {
2244         static if (isSomeChar!E && isSomeChar!RetTypeElement && E.sizeof > RetTypeElement.sizeof)
2245         {
2246             import std.utf : encode;
2247             RetTypeElement[4 / RetTypeElement.sizeof] encodeSpace;
2248             immutable size_t sepArrLength = encode(encodeSpace, sep);
2249             return join(ror, encodeSpace[0 .. sepArrLength]);
2250         }
2251         else
2252         {
2253             import core.internal.lifetime : emplaceRef;
2254             import std.format : format;
2255             size_t length;
2256             size_t rorLength;
2257             foreach (r; ror.save)
2258             {
2259                 length += r.length;
2260                 ++rorLength;
2261             }
2262             if (!rorLength)
2263                 return null;
2264             length += rorLength - 1;
2265             auto result = uninitializedArray!(RetTypeElement[])(length);
2266 
2267 
2268             size_t len;
2269             foreach (e; ror.front)
2270                 emplaceRef(result[len++], e);
2271             ror.popFront();
2272             foreach (r; ror)
2273             {
2274                 emplaceRef(result[len++], sep);
2275                 foreach (e; r)
2276                     emplaceRef(result[len++], e);
2277             }
2278             assert(len == result.length, format!
2279                     "len %s must equal result.lenght %s"(len, result.length));
2280             return (() @trusted => cast(RetType) result)();
2281         }
2282     }
2283     else
2284     {
2285         auto result = appender!RetType();
2286         put(result, ror.front);
2287         ror.popFront();
2288         for (; !ror.empty; ror.popFront())
2289         {
2290             put(result, sep);
2291             put(result, ror.front);
2292         }
2293         return result.data;
2294     }
2295 }
2296 
2297 // https://issues.dlang.org/show_bug.cgi?id=14230
2298 @safe unittest
2299 {
2300    string[] ary = ["","aa","bb","cc"];
2301    assert(ary.join('@') == "@aa@bb@cc");
2302 }
2303 
2304 /// Ditto
2305 ElementEncodingType!(ElementType!RoR)[] join(RoR)(RoR ror)
2306 if (isInputRange!RoR &&
2307     isInputRange!(Unqual!(ElementType!RoR)))
2308 {
2309     alias RetType = typeof(return);
2310     alias ConstRetTypeElement = ElementEncodingType!RetType;
2311     static if (isAssignable!(Unqual!ConstRetTypeElement, ConstRetTypeElement))
2312     {
2313         alias RetTypeElement = Unqual!ConstRetTypeElement;
2314     }
2315     else
2316     {
2317         alias RetTypeElement = ConstRetTypeElement;
2318     }
2319     alias RoRElem = ElementType!RoR;
2320 
2321     if (ror.empty)
2322         return RetType.init;
2323 
2324     static if (hasCheapIteration!RoR && (hasLength!RoRElem || isNarrowString!RoRElem))
2325     {
2326         import core.internal.lifetime : emplaceRef;
2327         size_t length;
2328         foreach (r; ror.save)
2329             length += r.length;
2330 
2331         auto result = (() @trusted => uninitializedArray!(RetTypeElement[])(length))();
2332         size_t len;
2333         foreach (r; ror)
2334             foreach (e; r)
2335                 emplaceRef!RetTypeElement(result[len++], e);
2336         assert(len == result.length,
2337                 "emplaced an unexpected number of elements");
2338         return (() @trusted => cast(RetType) result)();
2339     }
2340     else
2341     {
2342         auto result = appender!RetType();
2343         for (; !ror.empty; ror.popFront())
2344             put(result, ror.front);
2345         return result.data;
2346     }
2347 }
2348 
2349 ///
2350 @safe pure nothrow unittest
2351 {
2352     assert(join(["hello", "silly", "world"], " ") == "hello silly world");
2353     assert(join(["hello", "silly", "world"]) == "hellosillyworld");
2354 
2355     assert(join([[1, 2, 3], [4, 5]], [72, 73]) == [1, 2, 3, 72, 73, 4, 5]);
2356     assert(join([[1, 2, 3], [4, 5]]) == [1, 2, 3, 4, 5]);
2357 
2358     const string[] arr = ["apple", "banana"];
2359     assert(arr.join(",") == "apple,banana");
2360     assert(arr.join() == "applebanana");
2361 }
2362 
2363 @safe pure unittest
2364 {
2365     import std.conv : to;
2366     import std.range.primitives : autodecodeStrings;
2367 
2368     static foreach (T; AliasSeq!(string,wstring,dstring))
2369     {{
2370         auto arr2 = "Здравствуй Мир Unicode".to!(T);
2371         auto arr = ["Здравствуй", "Мир", "Unicode"].to!(T[]);
2372         assert(join(arr) == "ЗдравствуйМирUnicode");
2373         static foreach (S; AliasSeq!(char,wchar,dchar))
2374         {{
2375             auto jarr = arr.join(to!S(' '));
2376             static assert(is(typeof(jarr) == T));
2377             assert(jarr == arr2);
2378         }}
2379         static foreach (S; AliasSeq!(string,wstring,dstring))
2380         {{
2381             auto jarr = arr.join(to!S(" "));
2382             static assert(is(typeof(jarr) == T));
2383             assert(jarr == arr2);
2384         }}
2385     }}
2386 
2387     static foreach (T; AliasSeq!(string,wstring,dstring))
2388     {{
2389         auto arr2 = "Здравствуй\u047CМир\u047CUnicode".to!(T);
2390         auto arr = ["Здравствуй", "Мир", "Unicode"].to!(T[]);
2391         static foreach (S; AliasSeq!(wchar,dchar))
2392         {{
2393             auto jarr = arr.join(to!S('\u047C'));
2394             static assert(is(typeof(jarr) == T));
2395             assert(jarr == arr2);
2396         }}
2397     }}
2398 
2399     const string[] arr = ["apple", "banana"];
2400     assert(arr.join(',') == "apple,banana");
2401 }
2402 
2403 @safe unittest
2404 {
2405     class A { }
2406 
2407     const A[][] array;
2408     auto result = array.join; // can't remove constness, so don't try
2409 
2410     static assert(is(typeof(result) == const(A)[]));
2411 }
2412 
2413 @safe unittest
2414 {
2415     import std.algorithm;
2416     import std.conv : to;
2417     import std.range;
2418 
2419     static foreach (R; AliasSeq!(string, wstring, dstring))
2420     {{
2421         R word1 = "日本語";
2422         R word2 = "paul";
2423         R word3 = "jerry";
2424         R[] words = [word1, word2, word3];
2425 
2426         auto filteredWord1    = filter!"true"(word1);
2427         auto filteredLenWord1 = takeExactly(filteredWord1, word1.walkLength());
2428         auto filteredWord2    = filter!"true"(word2);
2429         auto filteredLenWord2 = takeExactly(filteredWord2, word2.walkLength());
2430         auto filteredWord3    = filter!"true"(word3);
2431         auto filteredLenWord3 = takeExactly(filteredWord3, word3.walkLength());
2432         auto filteredWordsArr = [filteredWord1, filteredWord2, filteredWord3];
2433         auto filteredLenWordsArr = [filteredLenWord1, filteredLenWord2, filteredLenWord3];
2434         auto filteredWords    = filter!"true"(filteredWordsArr);
2435 
2436         static foreach (S; AliasSeq!(string, wstring, dstring))
2437         {{
2438             assert(join(filteredWords, to!S(", ")) == "日本語, paul, jerry");
2439             assert(join(filteredWords, to!(ElementType!S)(',')) == "日本語,paul,jerry");
2440             assert(join(filteredWordsArr, to!(ElementType!(S))(',')) == "日本語,paul,jerry");
2441             assert(join(filteredWordsArr, to!S(", ")) == "日本語, paul, jerry");
2442             assert(join(filteredWordsArr, to!(ElementType!(S))(',')) == "日本語,paul,jerry");
2443             assert(join(filteredLenWordsArr, to!S(", ")) == "日本語, paul, jerry");
2444             assert(join(filter!"true"(words), to!S(", ")) == "日本語, paul, jerry");
2445             assert(join(words, to!S(", ")) == "日本語, paul, jerry");
2446 
2447             assert(join(filteredWords, to!S("")) == "日本語pauljerry");
2448             assert(join(filteredWordsArr, to!S("")) == "日本語pauljerry");
2449             assert(join(filteredLenWordsArr, to!S("")) == "日本語pauljerry");
2450             assert(join(filter!"true"(words), to!S("")) == "日本語pauljerry");
2451             assert(join(words, to!S("")) == "日本語pauljerry");
2452 
2453             assert(join(filter!"true"([word1]), to!S(", ")) == "日本語");
2454             assert(join([filteredWord1], to!S(", ")) == "日本語");
2455             assert(join([filteredLenWord1], to!S(", ")) == "日本語");
2456             assert(join(filter!"true"([filteredWord1]), to!S(", ")) == "日本語");
2457             assert(join([word1], to!S(", ")) == "日本語");
2458 
2459             assert(join(filteredWords, to!S(word1)) == "日本語日本語paul日本語jerry");
2460             assert(join(filteredWordsArr, to!S(word1)) == "日本語日本語paul日本語jerry");
2461             assert(join(filteredLenWordsArr, to!S(word1)) == "日本語日本語paul日本語jerry");
2462             assert(join(filter!"true"(words), to!S(word1)) == "日本語日本語paul日本語jerry");
2463             assert(join(words, to!S(word1)) == "日本語日本語paul日本語jerry");
2464 
2465             auto filterComma = filter!"true"(to!S(", "));
2466             assert(join(filteredWords, filterComma) == "日本語, paul, jerry");
2467             assert(join(filteredWordsArr, filterComma) == "日本語, paul, jerry");
2468             assert(join(filteredLenWordsArr, filterComma) == "日本語, paul, jerry");
2469             assert(join(filter!"true"(words), filterComma) == "日本語, paul, jerry");
2470             assert(join(words, filterComma) == "日本語, paul, jerry");
2471         }}
2472 
2473         assert(join(filteredWords) == "日本語pauljerry");
2474         assert(join(filteredWordsArr) == "日本語pauljerry");
2475         assert(join(filteredLenWordsArr) == "日本語pauljerry");
2476         assert(join(filter!"true"(words)) == "日本語pauljerry");
2477         assert(join(words) == "日本語pauljerry");
2478 
2479         assert(join(filteredWords, filter!"true"(", ")) == "日本語, paul, jerry");
2480         assert(join(filteredWordsArr, filter!"true"(", ")) == "日本語, paul, jerry");
2481         assert(join(filteredLenWordsArr, filter!"true"(", ")) == "日本語, paul, jerry");
2482         assert(join(filter!"true"(words), filter!"true"(", ")) == "日本語, paul, jerry");
2483         assert(join(words, filter!"true"(", ")) == "日本語, paul, jerry");
2484 
2485         assert(join(filter!"true"(cast(typeof(filteredWordsArr))[]), ", ").empty);
2486         assert(join(cast(typeof(filteredWordsArr))[], ", ").empty);
2487         assert(join(cast(typeof(filteredLenWordsArr))[], ", ").empty);
2488         assert(join(filter!"true"(cast(R[])[]), ", ").empty);
2489         assert(join(cast(R[])[], ", ").empty);
2490 
2491         assert(join(filter!"true"(cast(typeof(filteredWordsArr))[])).empty);
2492         assert(join(cast(typeof(filteredWordsArr))[]).empty);
2493         assert(join(cast(typeof(filteredLenWordsArr))[]).empty);
2494 
2495         assert(join(filter!"true"(cast(R[])[])).empty);
2496         assert(join(cast(R[])[]).empty);
2497     }}
2498 
2499     assert(join([[1, 2], [41, 42]], [5, 6]) == [1, 2, 5, 6, 41, 42]);
2500     assert(join([[1, 2], [41, 42]], cast(int[])[]) == [1, 2, 41, 42]);
2501     assert(join([[1, 2]], [5, 6]) == [1, 2]);
2502     assert(join(cast(int[][])[], [5, 6]).empty);
2503 
2504     assert(join([[1, 2], [41, 42]]) == [1, 2, 41, 42]);
2505     assert(join(cast(int[][])[]).empty);
2506 
2507     alias f = filter!"true";
2508     assert(join([[1, 2], [41, 42]],          [5, 6]) == [1, 2, 5, 6, 41, 42]);
2509     assert(join(f([[1, 2], [41, 42]]),       [5, 6]) == [1, 2, 5, 6, 41, 42]);
2510     assert(join([f([1, 2]), f([41, 42])],    [5, 6]) == [1, 2, 5, 6, 41, 42]);
2511     assert(join(f([f([1, 2]), f([41, 42])]), [5, 6]) == [1, 2, 5, 6, 41, 42]);
2512     assert(join([[1, 2], [41, 42]],          f([5, 6])) == [1, 2, 5, 6, 41, 42]);
2513     assert(join(f([[1, 2], [41, 42]]),       f([5, 6])) == [1, 2, 5, 6, 41, 42]);
2514     assert(join([f([1, 2]), f([41, 42])],    f([5, 6])) == [1, 2, 5, 6, 41, 42]);
2515     assert(join(f([f([1, 2]), f([41, 42])]), f([5, 6])) == [1, 2, 5, 6, 41, 42]);
2516 }
2517 
2518 // https://issues.dlang.org/show_bug.cgi?id=10683
2519 @safe unittest
2520 {
2521     import std.range : join;
2522     import std.typecons : tuple;
2523     assert([[tuple(1)]].join == [tuple(1)]);
2524     assert([[tuple("x")]].join == [tuple("x")]);
2525 }
2526 
2527 // https://issues.dlang.org/show_bug.cgi?id=13877
2528 @safe unittest
2529 {
2530     // Test that the range is iterated only once.
2531     import std.algorithm.iteration : map;
2532     int c = 0;
2533     auto j1 = [1, 2, 3].map!(_ => [c++]).join;
2534     assert(c == 3);
2535     assert(j1 == [0, 1, 2]);
2536 
2537     c = 0;
2538     auto j2 = [1, 2, 3].map!(_ => [c++]).join(9);
2539     assert(c == 3);
2540     assert(j2 == [0, 9, 1, 9, 2]);
2541 
2542     c = 0;
2543     auto j3 = [1, 2, 3].map!(_ => [c++]).join([9]);
2544     assert(c == 3);
2545     assert(j3 == [0, 9, 1, 9, 2]);
2546 }
2547 
2548 
2549 /++
2550     Replace occurrences of `from` with `to` in `subject` in a new array.
2551 
2552     Params:
2553         subject = the array to scan
2554         from = the item to replace
2555         to = the item to replace all instances of `from` with
2556 
2557     Returns:
2558         A new array without changing the contents of `subject`, or the original
2559         array if no match is found.
2560 
2561     See_Also:
2562         $(REF substitute, std,algorithm,iteration) for a lazy replace.
2563  +/
2564 E[] replace(E, R1, R2)(E[] subject, R1 from, R2 to)
2565 if ((isForwardRange!R1 && isForwardRange!R2 && (hasLength!R2 || isSomeString!R2)) ||
2566     is(Unqual!E : Unqual!R1))
2567 {
2568     size_t changed = 0;
2569     return replace(subject, from, to, changed);
2570 }
2571 
2572 ///
2573 @safe unittest
2574 {
2575     assert("Hello Wörld".replace("o Wö", "o Wo") == "Hello World");
2576     assert("Hello Wörld".replace("l", "h") == "Hehho Wörhd");
2577 }
2578 
2579 @safe unittest
2580 {
2581     assert([1, 2, 3, 4, 2].replace([2], [5]) == [1, 5, 3, 4, 5]);
2582     assert([3, 3, 3].replace([3], [0]) == [0, 0, 0]);
2583     assert([3, 3, 4, 3].replace([3, 3], [1, 1, 1]) == [1, 1, 1, 4, 3]);
2584 }
2585 
2586 // https://issues.dlang.org/show_bug.cgi?id=18215
2587 @safe unittest
2588 {
2589     auto arr = ["aaa.dd", "b"];
2590     arr = arr.replace("aaa.dd", ".");
2591     assert(arr == [".", "b"]);
2592 
2593     arr = ["_", "_", "aaa.dd", "b", "c", "aaa.dd", "e"];
2594     arr = arr.replace("aaa.dd", ".");
2595     assert(arr == ["_", "_", ".", "b", "c", ".", "e"]);
2596 }
2597 
2598 // https://issues.dlang.org/show_bug.cgi?id=18215
2599 @safe unittest
2600 {
2601     assert([[0], [1, 2], [0], [3]].replace([0], [4]) == [[4], [1, 2], [4], [3]]);
2602     assert([[0], [1, 2], [0], [3], [1, 2]]
2603             .replace([1, 2], [0]) == [[0], [0], [0], [3], [0]]);
2604     assert([[0], [1, 2], [0], [3], [1, 2], [0], [1, 2]]
2605             .replace([[0], [1, 2]], [[4]]) == [[4], [0], [3], [1, 2], [4]]);
2606 }
2607 
2608 // https://issues.dlang.org/show_bug.cgi?id=10930
2609 @safe unittest
2610 {
2611     assert([0, 1, 2].replace(1, 4) == [0, 4, 2]);
2612     assert("äbö".replace('ä', 'a') == "abö");
2613 }
2614 
2615 // empty array
2616 @safe unittest
2617 {
2618     int[] arr;
2619     assert(replace(arr, 1, 2) == []);
2620 }
2621 
2622 /++
2623     Replace occurrences of `from` with `to` in `subject` in a new array.
2624     `changed` counts how many replacements took place.
2625 
2626     Params:
2627         subject = the array to scan
2628         from = the item to replace
2629         to = the item to replace all instances of `from` with
2630         changed = the number of replacements
2631 
2632     Returns:
2633         A new array without changing the contents of `subject`, or the original
2634         array if no match is found.
2635  +/
2636 E[] replace(E, R1, R2)(E[] subject, R1 from, R2 to, ref size_t changed)
2637 if ((isForwardRange!R1 && isForwardRange!R2 && (hasLength!R2 || isSomeString!R2)) ||
2638     is(Unqual!E : Unqual!R1))
2639 {
2640     import std.algorithm.searching : find;
2641     import std.range : dropOne;
2642 
2643     static if (isInputRange!R1)
2644     {
2645         if (from.empty) return subject;
2646         alias rSave = a => a.save;
2647     }
2648     else
2649     {
2650         alias rSave = a => a;
2651     }
2652 
2653     auto balance = find(subject, rSave(from));
2654     if (balance.empty)
2655         return subject;
2656 
2657     auto app = appender!(E[])();
2658     app.put(subject[0 .. subject.length - balance.length]);
2659     app.put(rSave(to));
2660     ++changed;
2661     // replacing an element in an array is different to a range replacement
2662     static if (is(Unqual!E : Unqual!R1))
2663         replaceInto(app, balance.dropOne, from, to, changed);
2664     else
2665         replaceInto(app, balance[from.length .. $], from, to, changed);
2666 
2667     return app.data;
2668 }
2669 
2670 ///
2671 @safe unittest
2672 {
2673     size_t changed = 0;
2674     assert("Hello Wörld".replace("o Wö", "o Wo", changed) == "Hello World");
2675     assert(changed == 1);
2676 
2677     changed = 0;
2678     assert("Hello Wörld".replace("l", "h", changed) == "Hehho Wörhd");
2679     import std.stdio : writeln;
2680     writeln(changed);
2681     assert(changed == 3);
2682 }
2683 
2684 /++
2685     Replace occurrences of `from` with `to` in `subject` and output the result into
2686     `sink`.
2687 
2688     Params:
2689         sink = an $(REF_ALTTEXT output range, isOutputRange, std,range,primitives)
2690         subject = the array to scan
2691         from = the item to replace
2692         to = the item to replace all instances of `from` with
2693 
2694     See_Also:
2695         $(REF substitute, std,algorithm,iteration) for a lazy replace.
2696  +/
2697 void replaceInto(E, Sink, R1, R2)(Sink sink, E[] subject, R1 from, R2 to)
2698 if (isOutputRange!(Sink, E) &&
2699     ((isForwardRange!R1 && isForwardRange!R2 && (hasLength!R2 || isSomeString!R2)) ||
2700     is(Unqual!E : Unqual!R1)))
2701 {
2702     size_t changed = 0;
2703     replaceInto(sink, subject, from, to, changed);
2704 }
2705 
2706 ///
2707 @safe unittest
2708 {
2709     auto arr = [1, 2, 3, 4, 5];
2710     auto from = [2, 3];
2711     auto to = [4, 6];
2712     auto sink = appender!(int[])();
2713 
2714     replaceInto(sink, arr, from, to);
2715 
2716     assert(sink.data == [1, 4, 6, 4, 5]);
2717 }
2718 
2719 // empty array
2720 @safe unittest
2721 {
2722     auto sink = appender!(int[])();
2723     int[] arr;
2724     replaceInto(sink, arr, 1, 2);
2725     assert(sink.data == []);
2726 }
2727 
2728 @safe unittest
2729 {
2730     import std.algorithm.comparison : cmp;
2731     import std.conv : to;
2732 
2733     static foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[]))
2734     {
2735         static foreach (T; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[]))
2736         {{
2737             auto s = to!S("This is a foo foo list");
2738             auto from = to!T("foo");
2739             auto into = to!S("silly");
2740             S r;
2741             int i;
2742 
2743             r = replace(s, from, into);
2744             i = cmp(r, "This is a silly silly list");
2745             assert(i == 0);
2746 
2747             r = replace(s, to!S(""), into);
2748             i = cmp(r, "This is a foo foo list");
2749             assert(i == 0);
2750 
2751             assert(replace(r, to!S("won't find this"), to!S("whatever")) is r);
2752         }}
2753     }
2754 
2755     immutable s = "This is a foo foo list";
2756     assert(replace(s, "foo", "silly") == "This is a silly silly list");
2757 }
2758 
2759 @safe unittest
2760 {
2761     import std.algorithm.searching : skipOver;
2762     import std.conv : to;
2763 
2764     struct CheckOutput(C)
2765     {
2766         C[] desired;
2767         this(C[] arr){ desired = arr; }
2768         void put(C[] part){ assert(skipOver(desired, part)); }
2769     }
2770     static foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[]))
2771     {{
2772         alias Char = ElementEncodingType!S;
2773         S s = to!S("yet another dummy text, yet another ...");
2774         S from = to!S("yet another");
2775         S into = to!S("some");
2776         replaceInto(CheckOutput!(Char)(to!S("some dummy text, some ..."))
2777                     , s, from, into);
2778     }}
2779 }
2780 
2781 // https://issues.dlang.org/show_bug.cgi?id=10930
2782 @safe unittest
2783 {
2784     auto sink = appender!(int[])();
2785     replaceInto(sink, [0, 1, 2], 1, 5);
2786     assert(sink.data == [0, 5, 2]);
2787 
2788     auto sink2 = appender!(dchar[])();
2789     replaceInto(sink2, "äbö", 'ä', 'a');
2790     assert(sink2.data == "abö");
2791 }
2792 
2793 /++
2794     Replace occurrences of `from` with `to` in `subject` and output the result into
2795     `sink`. `changed` counts how many replacements took place.
2796 
2797     Params:
2798         sink = an $(REF_ALTTEXT output range, isOutputRange, std,range,primitives)
2799         subject = the array to scan
2800         from = the item to replace
2801         to = the item to replace all instances of `from` with
2802         changed = the number of replacements
2803  +/
2804 void replaceInto(E, Sink, R1, R2)(Sink sink, E[] subject, R1 from, R2 to, ref size_t changed)
2805 if (isOutputRange!(Sink, E) &&
2806     ((isForwardRange!R1 && isForwardRange!R2 && (hasLength!R2 || isSomeString!R2)) ||
2807     is(Unqual!E : Unqual!R1)))
2808 {
2809     import std.algorithm.searching : find;
2810     import std.range : dropOne;
2811 
2812     static if (isInputRange!R1)
2813     {
2814         if (from.empty)
2815         {
2816             sink.put(subject);
2817             return;
2818         }
2819         alias rSave = a => a.save;
2820     }
2821     else
2822     {
2823         alias rSave = a => a;
2824     }
2825     for (;;)
2826     {
2827         auto balance = find(subject, rSave(from));
2828         if (balance.empty)
2829         {
2830             sink.put(subject);
2831             break;
2832         }
2833         sink.put(subject[0 .. subject.length - balance.length]);
2834         sink.put(rSave(to));
2835         ++changed;
2836         // replacing an element in an array is different to a range replacement
2837         static if (is(Unqual!E : Unqual!R1))
2838             subject = balance.dropOne;
2839         else
2840             subject = balance[from.length .. $];
2841     }
2842 }
2843 
2844 ///
2845 @safe unittest
2846 {
2847     auto arr = [1, 2, 3, 4, 5];
2848     auto from = [2, 3];
2849     auto to = [4, 6];
2850     auto sink = appender!(int[])();
2851 
2852     size_t changed = 0;
2853     replaceInto(sink, arr, from, to, changed);
2854 
2855     assert(sink.data == [1, 4, 6, 4, 5]);
2856     assert(changed == 1);
2857 }
2858 
2859 /++
2860     Replaces elements from `array` with indices ranging from `from`
2861     (inclusive) to `to` (exclusive) with the range `stuff`.
2862 
2863     Params:
2864         subject = the array to scan
2865         from = the starting index
2866         to = the ending index
2867         stuff = the items to replace in-between `from` and `to`
2868 
2869     Returns:
2870         A new array without changing the contents of `subject`.
2871 
2872     See_Also:
2873         $(REF substitute, std,algorithm,iteration) for a lazy replace.
2874  +/
2875 T[] replace(T, Range)(T[] subject, size_t from, size_t to, Range stuff)
2876 if (isInputRange!Range &&
2877     (is(ElementType!Range : T) ||
2878     isSomeString!(T[]) && is(ElementType!Range : dchar)))
2879 {
2880     static if (hasLength!Range && is(ElementEncodingType!Range : T))
2881     {
2882         import std.algorithm.mutation : copy;
2883         assert(from <= to, "from must be before or equal to to");
2884         immutable sliceLen = to - from;
2885         auto retval = new Unqual!(T)[](subject.length - sliceLen + stuff.length);
2886         retval[0 .. from] = subject[0 .. from];
2887 
2888         if (!stuff.empty)
2889             copy(stuff, retval[from .. from + stuff.length]);
2890 
2891         retval[from + stuff.length .. $] = subject[to .. $];
2892         static if (is(T == const) || is(T == immutable))
2893         {
2894             return () @trusted { return cast(T[]) retval; } ();
2895         }
2896         else
2897         {
2898             return cast(T[]) retval;
2899         }
2900     }
2901     else
2902     {
2903         auto app = appender!(T[])();
2904         app.put(subject[0 .. from]);
2905         app.put(stuff);
2906         app.put(subject[to .. $]);
2907         return app.data;
2908     }
2909 }
2910 
2911 ///
2912 @safe unittest
2913 {
2914     auto a = [ 1, 2, 3, 4 ];
2915     auto b = a.replace(1, 3, [ 9, 9, 9 ]);
2916     assert(a == [ 1, 2, 3, 4 ]);
2917     assert(b == [ 1, 9, 9, 9, 4 ]);
2918 }
2919 
2920 @system unittest
2921 {
2922     import core.exception;
2923     import std.algorithm.iteration : filter;
2924     import std.conv : to;
2925     import std.exception;
2926 
2927 
2928     auto a = [ 1, 2, 3, 4 ];
2929     assert(replace(a, 0, 0, [5, 6, 7]) == [5, 6, 7, 1, 2, 3, 4]);
2930     assert(replace(a, 0, 2, cast(int[])[]) == [3, 4]);
2931     assert(replace(a, 0, 4, [5, 6, 7]) == [5, 6, 7]);
2932     assert(replace(a, 0, 2, [5, 6, 7]) == [5, 6, 7, 3, 4]);
2933     assert(replace(a, 2, 4, [5, 6, 7]) == [1, 2, 5, 6, 7]);
2934 
2935     assert(replace(a, 0, 0, filter!"true"([5, 6, 7])) == [5, 6, 7, 1, 2, 3, 4]);
2936     assert(replace(a, 0, 2, filter!"true"(cast(int[])[])) == [3, 4]);
2937     assert(replace(a, 0, 4, filter!"true"([5, 6, 7])) == [5, 6, 7]);
2938     assert(replace(a, 0, 2, filter!"true"([5, 6, 7])) == [5, 6, 7, 3, 4]);
2939     assert(replace(a, 2, 4, filter!"true"([5, 6, 7])) == [1, 2, 5, 6, 7]);
2940     assert(a == [ 1, 2, 3, 4 ]);
2941 
2942     void testStr(T, U)(string file = __FILE__, size_t line = __LINE__)
2943     {
2944 
2945         auto l = to!T("hello");
2946         auto r = to!U(" world");
2947 
2948         enforce(replace(l, 0, 0, r) == " worldhello",
2949                 new AssertError("testStr failure 1", file, line));
2950         enforce(replace(l, 0, 3, r) == " worldlo",
2951                 new AssertError("testStr failure 2", file, line));
2952         enforce(replace(l, 3, l.length, r) == "hel world",
2953                 new AssertError("testStr failure 3", file, line));
2954         enforce(replace(l, 0, l.length, r) == " world",
2955                 new AssertError("testStr failure 4", file, line));
2956         enforce(replace(l, l.length, l.length, r) == "hello world",
2957                 new AssertError("testStr failure 5", file, line));
2958     }
2959 
2960     testStr!(string, string)();
2961     testStr!(string, wstring)();
2962     testStr!(string, dstring)();
2963     testStr!(wstring, string)();
2964     testStr!(wstring, wstring)();
2965     testStr!(wstring, dstring)();
2966     testStr!(dstring, string)();
2967     testStr!(dstring, wstring)();
2968     testStr!(dstring, dstring)();
2969 
2970     enum s = "0123456789";
2971     enum w = "⁰¹²³⁴⁵⁶⁷⁸⁹"w;
2972     enum d = "⁰¹²³⁴⁵⁶⁷⁸⁹"d;
2973 
2974     assert(replace(s, 0, 0, "***") == "***0123456789");
2975     assert(replace(s, 10, 10, "***") == "0123456789***");
2976     assert(replace(s, 3, 8, "1012") == "012101289");
2977     assert(replace(s, 0, 5, "43210") == "4321056789");
2978     assert(replace(s, 5, 10, "43210") == "0123443210");
2979 
2980     assert(replace(w, 0, 0, "***"w) == "***⁰¹²³⁴⁵⁶⁷⁸⁹"w);
2981     assert(replace(w, 10, 10, "***"w) == "⁰¹²³⁴⁵⁶⁷⁸⁹***"w);
2982     assert(replace(w, 3, 8, "¹⁰¹²"w) == "⁰¹²¹⁰¹²⁸⁹"w);
2983     assert(replace(w, 0, 5, "⁴³²¹⁰"w) == "⁴³²¹⁰⁵⁶⁷⁸⁹"w);
2984     assert(replace(w, 5, 10, "⁴³²¹⁰"w) == "⁰¹²³⁴⁴³²¹⁰"w);
2985 
2986     assert(replace(d, 0, 0, "***"d) == "***⁰¹²³⁴⁵⁶⁷⁸⁹"d);
2987     assert(replace(d, 10, 10, "***"d) == "⁰¹²³⁴⁵⁶⁷⁸⁹***"d);
2988     assert(replace(d, 3, 8, "¹⁰¹²"d) == "⁰¹²¹⁰¹²⁸⁹"d);
2989     assert(replace(d, 0, 5, "⁴³²¹⁰"d) == "⁴³²¹⁰⁵⁶⁷⁸⁹"d);
2990     assert(replace(d, 5, 10, "⁴³²¹⁰"d) == "⁰¹²³⁴⁴³²¹⁰"d);
2991 }
2992 
2993 // https://issues.dlang.org/show_bug.cgi?id=18166
2994 @safe pure unittest
2995 {
2996     auto str = replace("aaaaa"d, 1, 4, "***"d);
2997     assert(str == "a***a");
2998 }
2999 
3000 /++
3001     Replaces elements from `array` with indices ranging from `from`
3002     (inclusive) to `to` (exclusive) with the range `stuff`. Expands or
3003     shrinks the array as needed.
3004 
3005     Params:
3006         array = the array to scan
3007         from = the starting index
3008         to = the ending index
3009         stuff = the items to replace in-between `from` and `to`
3010  +/
3011 void replaceInPlace(T, Range)(ref T[] array, size_t from, size_t to, Range stuff)
3012 if (is(typeof(replace(array, from, to, stuff))))
3013 {
3014     static if (isDynamicArray!Range &&
3015               is(Unqual!(ElementEncodingType!Range) == T) &&
3016               !isNarrowString!(T[]))
3017     {
3018         // optimized for homogeneous arrays that can be overwritten.
3019         import std.algorithm.mutation : remove;
3020         import std.typecons : tuple;
3021 
3022         if (overlap(array, stuff).length)
3023         {
3024             // use slower/conservative method
3025             array = array[0 .. from] ~ stuff ~ array[to .. $];
3026         }
3027         else if (stuff.length <= to - from)
3028         {
3029             // replacement reduces length
3030             immutable stuffEnd = from + stuff.length;
3031             array[from .. stuffEnd] = stuff[];
3032             if (stuffEnd < to)
3033                 array = remove(array, tuple(stuffEnd, to));
3034         }
3035         else
3036         {
3037             // replacement increases length
3038             // @@@TODO@@@: optimize this
3039             immutable replaceLen = to - from;
3040             array[from .. to] = stuff[0 .. replaceLen];
3041             insertInPlace(array, to, stuff[replaceLen .. $]);
3042         }
3043     }
3044     else
3045     {
3046         // default implementation, just do what replace does.
3047         array = replace(array, from, to, stuff);
3048     }
3049 }
3050 
3051 ///
3052 @safe unittest
3053 {
3054     int[] a = [1, 4, 5];
3055     replaceInPlace(a, 1u, 2u, [2, 3, 4]);
3056     assert(a == [1, 2, 3, 4, 5]);
3057     replaceInPlace(a, 1u, 2u, cast(int[])[]);
3058     assert(a == [1, 3, 4, 5]);
3059     replaceInPlace(a, 1u, 3u, a[2 .. 4]);
3060     assert(a == [1, 4, 5, 5]);
3061 }
3062 
3063 // https://issues.dlang.org/show_bug.cgi?id=12889
3064 @safe unittest
3065 {
3066     int[1][] arr = [[0], [1], [2], [3], [4], [5], [6]];
3067     int[1][] stuff = [[0], [1]];
3068     replaceInPlace(arr, 4, 6, stuff);
3069     assert(arr == [[0], [1], [2], [3], [0], [1], [6]]);
3070 }
3071 
3072 @system unittest
3073 {
3074     // https://issues.dlang.org/show_bug.cgi?id=14925
3075     char[] a = "mon texte 1".dup;
3076     char[] b = "abc".dup;
3077     replaceInPlace(a, 4, 9, b);
3078     assert(a == "mon abc 1");
3079 
3080     // ensure we can replace in place with different encodings
3081     string unicoded = "\U00010437";
3082     string unicodedLong = "\U00010437aaaaa";
3083     string base = "abcXXXxyz";
3084     string result = "abc\U00010437xyz";
3085     string resultLong = "abc\U00010437aaaaaxyz";
3086     size_t repstart = 3;
3087     size_t repend = 3 + 3;
3088 
3089     void testStringReplaceInPlace(T, U)()
3090     {
3091         import std.algorithm.comparison : equal;
3092         import std.conv;
3093         auto a = unicoded.to!(U[]);
3094         auto b = unicodedLong.to!(U[]);
3095 
3096         auto test = base.to!(T[]);
3097 
3098         test.replaceInPlace(repstart, repend, a);
3099         assert(equal(test, result), "Failed for types " ~ T.stringof ~ " and " ~ U.stringof);
3100 
3101         test = base.to!(T[]);
3102 
3103         test.replaceInPlace(repstart, repend, b);
3104         assert(equal(test, resultLong), "Failed for types " ~ T.stringof ~ " and " ~ U.stringof);
3105     }
3106 
3107     import std.meta : AliasSeq;
3108     alias allChars = AliasSeq!(char, immutable(char), const(char),
3109                          wchar, immutable(wchar), const(wchar),
3110                          dchar, immutable(dchar), const(dchar));
3111     foreach (T; allChars)
3112         foreach (U; allChars)
3113             testStringReplaceInPlace!(T, U)();
3114 
3115     void testInout(inout(int)[] a)
3116     {
3117         // will be transferred to the 'replace' function
3118         replaceInPlace(a, 1, 2, [1,2,3]);
3119     }
3120 }
3121 
3122 @safe unittest
3123 {
3124     // the constraint for the first overload used to match this, which wouldn't compile.
3125     import std.algorithm.comparison : equal;
3126     long[] a = [1L, 2, 3];
3127     int[] b = [4, 5, 6];
3128     a.replaceInPlace(1, 2, b);
3129     assert(equal(a, [1L, 4, 5, 6, 3]));
3130 }
3131 
3132 @system unittest
3133 {
3134     import core.exception;
3135     import std.algorithm.comparison : equal;
3136     import std.algorithm.iteration : filter;
3137     import std.conv : to;
3138     import std.exception;
3139 
3140 
3141     bool test(T, U, V)(T orig, size_t from, size_t to, U toReplace, V result)
3142     {
3143         {
3144             static if (is(T == typeof(T.init.dup)))
3145                 auto a = orig.dup;
3146             else
3147                 auto a = orig.idup;
3148 
3149             a.replaceInPlace(from, to, toReplace);
3150             if (!equal(a, result))
3151                 return false;
3152         }
3153 
3154         static if (isInputRange!U)
3155         {
3156             orig.replaceInPlace(from, to, filter!"true"(toReplace));
3157             return equal(orig, result);
3158         }
3159         else
3160             return true;
3161     }
3162 
3163     assert(test([1, 2, 3, 4], 0, 0, [5, 6, 7], [5, 6, 7, 1, 2, 3, 4]));
3164     assert(test([1, 2, 3, 4], 0, 2, cast(int[])[], [3, 4]));
3165     assert(test([1, 2, 3, 4], 0, 4, [5, 6, 7], [5, 6, 7]));
3166     assert(test([1, 2, 3, 4], 0, 2, [5, 6, 7], [5, 6, 7, 3, 4]));
3167     assert(test([1, 2, 3, 4], 2, 4, [5, 6, 7], [1, 2, 5, 6, 7]));
3168 
3169     assert(test([1, 2, 3, 4], 0, 0, filter!"true"([5, 6, 7]), [5, 6, 7, 1, 2, 3, 4]));
3170     assert(test([1, 2, 3, 4], 0, 2, filter!"true"(cast(int[])[]), [3, 4]));
3171     assert(test([1, 2, 3, 4], 0, 4, filter!"true"([5, 6, 7]), [5, 6, 7]));
3172     assert(test([1, 2, 3, 4], 0, 2, filter!"true"([5, 6, 7]), [5, 6, 7, 3, 4]));
3173     assert(test([1, 2, 3, 4], 2, 4, filter!"true"([5, 6, 7]), [1, 2, 5, 6, 7]));
3174 
3175     void testStr(T, U)(string file = __FILE__, size_t line = __LINE__)
3176     {
3177 
3178         auto l = to!T("hello");
3179         auto r = to!U(" world");
3180 
3181         enforce(test(l, 0, 0, r, " worldhello"),
3182                 new AssertError("testStr failure 1", file, line));
3183         enforce(test(l, 0, 3, r, " worldlo"),
3184                 new AssertError("testStr failure 2", file, line));
3185         enforce(test(l, 3, l.length, r, "hel world"),
3186                 new AssertError("testStr failure 3", file, line));
3187         enforce(test(l, 0, l.length, r, " world"),
3188                 new AssertError("testStr failure 4", file, line));
3189         enforce(test(l, l.length, l.length, r, "hello world"),
3190                 new AssertError("testStr failure 5", file, line));
3191     }
3192 
3193     testStr!(string, string)();
3194     testStr!(string, wstring)();
3195     testStr!(string, dstring)();
3196     testStr!(wstring, string)();
3197     testStr!(wstring, wstring)();
3198     testStr!(wstring, dstring)();
3199     testStr!(dstring, string)();
3200     testStr!(dstring, wstring)();
3201     testStr!(dstring, dstring)();
3202 }
3203 
3204 /++
3205     Replaces the first occurrence of `from` with `to` in `subject`.
3206 
3207     Params:
3208         subject = the array to scan
3209         from = the item to replace
3210         to = the item to replace `from` with
3211 
3212     Returns:
3213         A new array without changing the contents of `subject`, or the original
3214         array if no match is found.
3215  +/
3216 E[] replaceFirst(E, R1, R2)(E[] subject, R1 from, R2 to)
3217 if (isDynamicArray!(E[]) &&
3218     isForwardRange!R1 && is(typeof(appender!(E[])().put(from[0 .. 1]))) &&
3219     isForwardRange!R2 && is(typeof(appender!(E[])().put(to[0 .. 1]))))
3220 {
3221     if (from.empty) return subject;
3222     static if (isSomeString!(E[]))
3223     {
3224         import std.string : indexOf;
3225         immutable idx = subject.indexOf(from);
3226     }
3227     else
3228     {
3229         import std.algorithm.searching : countUntil;
3230         immutable idx = subject.countUntil(from);
3231     }
3232     if (idx == -1)
3233         return subject;
3234 
3235     auto app = appender!(E[])();
3236     app.put(subject[0 .. idx]);
3237     app.put(to);
3238 
3239     static if (isSomeString!(E[]) && isSomeString!R1)
3240     {
3241         import std.utf : codeLength;
3242         immutable fromLength = codeLength!(Unqual!E, R1)(from);
3243     }
3244     else
3245         immutable fromLength = from.length;
3246 
3247     app.put(subject[idx + fromLength .. $]);
3248 
3249     return app.data;
3250 }
3251 
3252 ///
3253 @safe unittest
3254 {
3255     auto a = [1, 2, 2, 3, 4, 5];
3256     auto b = a.replaceFirst([2], [1337]);
3257     assert(b == [1, 1337, 2, 3, 4, 5]);
3258 
3259     auto s = "This is a foo foo list";
3260     auto r = s.replaceFirst("foo", "silly");
3261     assert(r == "This is a silly foo list");
3262 }
3263 
3264 @safe unittest
3265 {
3266     import std.algorithm.comparison : cmp;
3267     import std.conv : to;
3268 
3269     static foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[],
3270                           const(char[]), immutable(char[])))
3271     {
3272         static foreach (T; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[],
3273                               const(char[]), immutable(char[])))
3274         {{
3275             auto s = to!S("This is a foo foo list");
3276             auto s2 = to!S("Thüs is a ßöö foo list");
3277             auto from = to!T("foo");
3278             auto from2 = to!T("ßöö");
3279             auto into = to!T("silly");
3280             auto into2 = to!T("sälly");
3281 
3282             S r1 = replaceFirst(s, from, into);
3283             assert(cmp(r1, "This is a silly foo list") == 0);
3284 
3285             S r11 = replaceFirst(s2, from2, into2);
3286             assert(cmp(r11, "Thüs is a sälly foo list") == 0,
3287                 to!string(r11) ~ " : " ~ S.stringof ~ " " ~ T.stringof);
3288 
3289             S r2 = replaceFirst(r1, from, into);
3290             assert(cmp(r2, "This is a silly silly list") == 0);
3291 
3292             S r3 = replaceFirst(s, to!T(""), into);
3293             assert(cmp(r3, "This is a foo foo list") == 0);
3294 
3295             assert(replaceFirst(r3, to!T("won't find"), to!T("whatever")) is r3);
3296         }}
3297     }
3298 }
3299 
3300 // https://issues.dlang.org/show_bug.cgi?id=8187
3301 @safe unittest
3302 {
3303     auto res = ["a", "a"];
3304     assert(replace(res, "a", "b") == ["b", "b"]);
3305     assert(replaceFirst(res, "a", "b") == ["b", "a"]);
3306 }
3307 
3308 /++
3309     Replaces the last occurrence of `from` with `to` in `subject`.
3310 
3311     Params:
3312         subject = the array to scan
3313         from = the item to replace
3314         to = the item to replace `from` with
3315 
3316     Returns:
3317         A new array without changing the contents of `subject`, or the original
3318         array if no match is found.
3319  +/
3320 E[] replaceLast(E, R1, R2)(E[] subject, R1 from , R2 to)
3321 if (isDynamicArray!(E[]) &&
3322     isForwardRange!R1 && is(typeof(appender!(E[])().put(from[0 .. 1]))) &&
3323     isForwardRange!R2 && is(typeof(appender!(E[])().put(to[0 .. 1]))))
3324 {
3325     import std.range : retro;
3326     if (from.empty) return subject;
3327     static if (isSomeString!(E[]))
3328     {
3329         import std.string : lastIndexOf;
3330         auto idx = subject.lastIndexOf(from);
3331     }
3332     else
3333     {
3334         import std.algorithm.searching : countUntil;
3335         auto idx = retro(subject).countUntil(retro(from));
3336     }
3337 
3338     if (idx == -1)
3339         return subject;
3340 
3341     static if (isSomeString!(E[]) && isSomeString!R1)
3342     {
3343         import std.utf : codeLength;
3344         auto fromLength = codeLength!(Unqual!E, R1)(from);
3345     }
3346     else
3347         auto fromLength = from.length;
3348 
3349     auto app = appender!(E[])();
3350     static if (isSomeString!(E[]))
3351         app.put(subject[0 .. idx]);
3352     else
3353         app.put(subject[0 .. $ - idx - fromLength]);
3354 
3355     app.put(to);
3356 
3357     static if (isSomeString!(E[]))
3358         app.put(subject[idx+fromLength .. $]);
3359     else
3360         app.put(subject[$ - idx .. $]);
3361 
3362     return app.data;
3363 }
3364 
3365 ///
3366 @safe unittest
3367 {
3368     auto a = [1, 2, 2, 3, 4, 5];
3369     auto b = a.replaceLast([2], [1337]);
3370     assert(b == [1, 2, 1337, 3, 4, 5]);
3371 
3372     auto s = "This is a foo foo list";
3373     auto r = s.replaceLast("foo", "silly");
3374     assert(r == "This is a foo silly list", r);
3375 }
3376 
3377 @safe unittest
3378 {
3379     import std.algorithm.comparison : cmp;
3380     import std.conv : to;
3381 
3382     static foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[],
3383                           const(char[]), immutable(char[])))
3384     {
3385         static foreach (T; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[],
3386                               const(char[]), immutable(char[])))
3387         {{
3388             auto s = to!S("This is a foo foo list");
3389             auto s2 = to!S("Thüs is a ßöö ßöö list");
3390             auto from = to!T("foo");
3391             auto from2 = to!T("ßöö");
3392             auto into = to!T("silly");
3393             auto into2 = to!T("sälly");
3394 
3395             S r1 = replaceLast(s, from, into);
3396             assert(cmp(r1, "This is a foo silly list") == 0, to!string(r1));
3397 
3398             S r11 = replaceLast(s2, from2, into2);
3399             assert(cmp(r11, "Thüs is a ßöö sälly list") == 0,
3400                 to!string(r11) ~ " : " ~ S.stringof ~ " " ~ T.stringof);
3401 
3402             S r2 = replaceLast(r1, from, into);
3403             assert(cmp(r2, "This is a silly silly list") == 0);
3404 
3405             S r3 = replaceLast(s, to!T(""), into);
3406             assert(cmp(r3, "This is a foo foo list") == 0);
3407 
3408             assert(replaceLast(r3, to!T("won't find"), to!T("whatever")) is r3);
3409         }}
3410     }
3411 }
3412 
3413 /++
3414     Creates a new array such that the items in `slice` are replaced with the
3415     items in `replacement`. `slice` and `replacement` do not need to be the
3416     same length. The result will grow or shrink based on the items given.
3417 
3418     Params:
3419         s = the base of the new array
3420         slice = the slice of `s` to be replaced
3421         replacement = the items to replace `slice` with
3422 
3423     Returns:
3424         A new array that is `s` with `slice` replaced by
3425         `replacement[]`.
3426 
3427     See_Also:
3428         $(REF substitute, std,algorithm,iteration) for a lazy replace.
3429  +/
3430 inout(T)[] replaceSlice(T)(inout(T)[] s, in T[] slice, in T[] replacement)
3431 in
3432 {
3433     // Verify that slice[] really is a slice of s[]
3434     assert(overlap(s, slice) is slice, "slice[] is not a subslice of s[]");
3435 }
3436 do
3437 {
3438     auto result = new T[s.length - slice.length + replacement.length];
3439     immutable so = &slice[0] - &s[0];
3440     result[0 .. so] = s[0 .. so];
3441     result[so .. so + replacement.length] = replacement[];
3442     result[so + replacement.length .. result.length] =
3443         s[so + slice.length .. s.length];
3444 
3445     return () @trusted inout {
3446         return cast(inout(T)[]) result;
3447     }();
3448 }
3449 
3450 ///
3451 @safe unittest
3452 {
3453     auto a = [1, 2, 3, 4, 5];
3454     auto b = replaceSlice(a, a[1 .. 4], [0, 0, 0]);
3455 
3456     assert(b == [1, 0, 0, 0, 5]);
3457 }
3458 
3459 @safe unittest
3460 {
3461     import std.algorithm.comparison : cmp;
3462 
3463     string s = "hello";
3464     string slice = s[2 .. 4];
3465 
3466     auto r = replaceSlice(s, slice, "bar");
3467     int i;
3468     i = cmp(r, "hebaro");
3469     assert(i == 0);
3470 }
3471 
3472 /**
3473 Implements an output range that appends data to an array. This is
3474 recommended over $(D array ~= data) when appending many elements because it is more
3475 efficient. `Appender` maintains its own array metadata locally, so it can avoid
3476 the $(DDSUBLINK spec/arrays, capacity-reserve, performance hit of looking up slice `capacity`)
3477 for each append.
3478 
3479 Params:
3480     A = the array type to simulate.
3481 
3482 See_Also: $(LREF appender)
3483  */
3484 struct Appender(A)
3485 if (isDynamicArray!A)
3486 {
3487     import core.memory : GC;
3488 
3489     private alias T = ElementEncodingType!A;
3490 
3491     private struct Data
3492     {
3493         size_t capacity;
3494         Unqual!T[] arr;
3495         bool tryExtendBlock = false;
3496     }
3497 
3498     private Data* _data;
3499 
3500     /**
3501      * Constructs an `Appender` with a given array.  Note that this does not copy the
3502      * data.  If the array has a larger capacity as determined by `arr.capacity`,
3503      * it will be used by the appender.  After initializing an appender on an array,
3504      * appending to the original array will reallocate.
3505      */
3506     this(A arr) @trusted
3507     {
3508         // initialize to a given array.
3509         _data = new Data;
3510         _data.arr = cast(Unqual!T[]) arr; //trusted
3511 
3512         if (__ctfe)
3513             return;
3514 
3515         // We want to use up as much of the block the array is in as possible.
3516         // if we consume all the block that we can, then array appending is
3517         // safe WRT built-in append, and we can use the entire block.
3518         // We only do this for mutable types that can be extended.
3519         static if (isMutable!T && is(typeof(arr.length = size_t.max)))
3520         {
3521             immutable cap = arr.capacity; //trusted
3522             // Replace with "GC.setAttr( Not Appendable )" once pure (and fixed)
3523             if (cap > arr.length)
3524                 arr.length = cap;
3525         }
3526         _data.capacity = arr.length;
3527     }
3528 
3529     /**
3530      * Reserve at least newCapacity elements for appending.  Note that more elements
3531      * may be reserved than requested. If `newCapacity <= capacity`, then nothing is
3532      * done.
3533      *
3534      * Params:
3535      *     newCapacity = the capacity the `Appender` should have
3536      */
3537     void reserve(size_t newCapacity)
3538     {
3539         if (_data)
3540         {
3541             if (newCapacity > _data.capacity)
3542                 ensureAddable(newCapacity - _data.arr.length);
3543         }
3544         else
3545         {
3546             ensureAddable(newCapacity);
3547         }
3548     }
3549 
3550     /**
3551      * Returns: the capacity of the array (the maximum number of elements the
3552      * managed array can accommodate before triggering a reallocation). If any
3553      * appending will reallocate, `0` will be returned.
3554      */
3555     @property size_t capacity() const
3556     {
3557         return _data ? _data.capacity : 0;
3558     }
3559 
3560     /**
3561      * Use opSlice() from now on.
3562      * Returns: The managed array.
3563      */
3564     @property inout(T)[] data() inout @trusted
3565     {
3566         return this[];
3567     }
3568 
3569     /**
3570      * Returns: The managed array.
3571      */
3572     @property inout(T)[] opSlice() inout @trusted
3573     {
3574         /* @trusted operation:
3575          * casting Unqual!T[] to inout(T)[]
3576          */
3577         return cast(typeof(return))(_data ? _data.arr : null);
3578     }
3579 
3580     // ensure we can add nelems elements, resizing as necessary
3581     private void ensureAddable(size_t nelems)
3582     {
3583         if (!_data)
3584             _data = new Data;
3585         immutable len = _data.arr.length;
3586         immutable reqlen = len + nelems;
3587 
3588         if (_data.capacity >= reqlen)
3589             return;
3590 
3591         // need to increase capacity
3592         if (__ctfe)
3593         {
3594             static if (__traits(compiles, new Unqual!T[1]))
3595             {
3596                 _data.arr.length = reqlen;
3597             }
3598             else
3599             {
3600                 // avoid restriction of @disable this()
3601                 _data.arr = _data.arr[0 .. _data.capacity];
3602                 foreach (i; _data.capacity .. reqlen)
3603                     _data.arr ~= Unqual!T.init;
3604             }
3605             _data.arr = _data.arr[0 .. len];
3606             _data.capacity = reqlen;
3607         }
3608         else
3609         {
3610             // Time to reallocate.
3611             // We need to almost duplicate what's in druntime, except we
3612             // have better access to the capacity field.
3613             auto newlen = appenderNewCapacity!(T.sizeof)(_data.capacity, reqlen);
3614             // first, try extending the current block
3615             if (_data.tryExtendBlock)
3616             {
3617                 immutable u = (() @trusted => GC.extend(_data.arr.ptr, nelems * T.sizeof, (newlen - len) * T.sizeof))();
3618                 if (u)
3619                 {
3620                     // extend worked, update the capacity
3621                     _data.capacity = u / T.sizeof;
3622                     return;
3623                 }
3624             }
3625 
3626 
3627             // didn't work, must reallocate
3628             import core.checkedint : mulu;
3629             bool overflow;
3630             const nbytes = mulu(newlen, T.sizeof, overflow);
3631             if (overflow) assert(false, "the reallocation would exceed the "
3632                     ~ "available pointer range");
3633 
3634             auto bi = (() @trusted => GC.qalloc(nbytes, blockAttribute!T))();
3635             _data.capacity = bi.size / T.sizeof;
3636             import core.stdc.string : memcpy;
3637             if (len)
3638                 () @trusted { memcpy(bi.base, _data.arr.ptr, len * T.sizeof); }();
3639             _data.arr = (() @trusted => (cast(Unqual!T*) bi.base)[0 .. len])();
3640             _data.tryExtendBlock = true;
3641             // leave the old data, for safety reasons
3642         }
3643     }
3644 
3645     private template canPutItem(U)
3646     {
3647         enum bool canPutItem =
3648             is(Unqual!U : Unqual!T) ||
3649             isSomeChar!T && isSomeChar!U;
3650     }
3651     private template canPutConstRange(Range)
3652     {
3653         enum bool canPutConstRange =
3654             isInputRange!(Unqual!Range) &&
3655             !isInputRange!Range &&
3656             is(typeof(Appender.init.put(Range.init.front)));
3657     }
3658     private template canPutRange(Range)
3659     {
3660         enum bool canPutRange =
3661             isInputRange!Range &&
3662             is(typeof(Appender.init.put(Range.init.front)));
3663     }
3664 
3665     /**
3666      * Appends `item` to the managed array. Performs encoding for
3667      * `char` types if `A` is a differently typed `char` array.
3668      *
3669      * Params:
3670      *     item = the single item to append
3671      */
3672     void put(U)(U item) if (canPutItem!U)
3673     {
3674         static if (isSomeChar!T && isSomeChar!U && T.sizeof < U.sizeof)
3675         {
3676             /* may throwable operation:
3677              * - std.utf.encode
3678              */
3679             // must do some transcoding around here
3680             import std.utf : encode;
3681             Unqual!T[T.sizeof == 1 ? 4 : 2] encoded;
3682             auto len = encode(encoded, item);
3683             put(encoded[0 .. len]);
3684         }
3685         else
3686         {
3687             import core.lifetime : emplace;
3688 
3689             ensureAddable(1);
3690             immutable len = _data.arr.length;
3691 
3692             auto bigData = (() @trusted => _data.arr.ptr[0 .. len + 1])();
3693             auto itemUnqual = (() @trusted => & cast() item)();
3694             emplace(&bigData[len], *itemUnqual);
3695             //We do this at the end, in case of exceptions
3696             _data.arr = bigData;
3697         }
3698     }
3699 
3700     // Const fixing hack.
3701     void put(Range)(Range items) if (canPutConstRange!Range)
3702     {
3703         alias p = put!(Unqual!Range);
3704         p(items);
3705     }
3706 
3707     /**
3708      * Appends an entire range to the managed array. Performs encoding for
3709      * `char` elements if `A` is a differently typed `char` array.
3710      *
3711      * Params:
3712      *     items = the range of items to append
3713      */
3714     void put(Range)(Range items) if (canPutRange!Range)
3715     {
3716         // note, we disable this branch for appending one type of char to
3717         // another because we can't trust the length portion.
3718         static if (!(isSomeChar!T && isSomeChar!(ElementType!Range) &&
3719                      !is(immutable Range == immutable T[])) &&
3720                     is(typeof(items.length) == size_t))
3721         {
3722             // optimization -- if this type is something other than a string,
3723             // and we are adding exactly one element, call the version for one
3724             // element.
3725             static if (!isSomeChar!T)
3726             {
3727                 if (items.length == 1)
3728                 {
3729                     put(items.front);
3730                     return;
3731                 }
3732             }
3733 
3734             // make sure we have enough space, then add the items
3735             auto bigDataFun(size_t extra)
3736             {
3737                 ensureAddable(extra);
3738                 return (() @trusted => _data.arr.ptr[0 .. _data.arr.length + extra])();
3739             }
3740             auto bigData = bigDataFun(items.length);
3741 
3742             immutable len = _data.arr.length;
3743             immutable newlen = bigData.length;
3744 
3745             alias UT = Unqual!T;
3746 
3747             static if (is(typeof(_data.arr[] = items[])) &&
3748                 !hasElaborateAssign!UT && isAssignable!(UT, ElementEncodingType!Range))
3749             {
3750                 bigData[len .. newlen] = items[];
3751             }
3752             else
3753             {
3754                 import core.internal.lifetime : emplaceRef;
3755                 foreach (ref it ; bigData[len .. newlen])
3756                 {
3757                     emplaceRef!T(it, items.front);
3758                     items.popFront();
3759                 }
3760             }
3761 
3762             //We do this at the end, in case of exceptions
3763             _data.arr = bigData;
3764         }
3765         else static if (isSomeChar!T && isSomeChar!(ElementType!Range) &&
3766                         !is(immutable T == immutable ElementType!Range))
3767         {
3768             // need to decode and encode
3769             import std.utf : decodeFront;
3770             while (!items.empty)
3771             {
3772                 auto c = items.decodeFront;
3773                 put(c);
3774             }
3775         }
3776         else
3777         {
3778             //pragma(msg, Range.stringof);
3779             // Generic input range
3780             for (; !items.empty; items.popFront())
3781             {
3782                 put(items.front);
3783             }
3784         }
3785     }
3786 
3787     /**
3788      * Appends to the managed array.
3789      *
3790      * See_Also: $(LREF Appender.put)
3791      */
3792     alias opOpAssign(string op : "~") = put;
3793 
3794     // only allow overwriting data on non-immutable and non-const data
3795     static if (isMutable!T)
3796     {
3797         /**
3798          * Clears the managed array.  This allows the elements of the array to be reused
3799          * for appending.
3800          *
3801          * Note: clear is disabled for immutable or const element types, due to the
3802          * possibility that `Appender` might overwrite immutable data.
3803          */
3804         void clear() @trusted pure nothrow
3805         {
3806             if (_data)
3807             {
3808                 _data.arr = _data.arr.ptr[0 .. 0];
3809             }
3810         }
3811 
3812         /**
3813          * Shrinks the managed array to the given length.
3814          *
3815          * Throws: `Exception` if newlength is greater than the current array length.
3816          * Note: shrinkTo is disabled for immutable or const element types.
3817          */
3818         void shrinkTo(size_t newlength) @trusted pure
3819         {
3820             import std.exception : enforce;
3821             if (_data)
3822             {
3823                 enforce(newlength <= _data.arr.length, "Attempting to shrink Appender with newlength > length");
3824                 _data.arr = _data.arr.ptr[0 .. newlength];
3825             }
3826             else
3827                 enforce(newlength == 0, "Attempting to shrink empty Appender with non-zero newlength");
3828         }
3829     }
3830 
3831     /**
3832      * Gives a string in the form of `Appender!(A)(data)`.
3833      *
3834      * Params:
3835      *     w = A `char` accepting
3836      *     $(REF_ALTTEXT output range, isOutputRange, std, range, primitives).
3837      *     fmt = A $(REF FormatSpec, std, format) which controls how the array
3838      *     is formatted.
3839      * Returns:
3840      *     A `string` if `writer` is not set; `void` otherwise.
3841      */
3842     string toString()() const
3843     {
3844         import std.format.spec : singleSpec;
3845 
3846         auto app = appender!string();
3847         auto spec = singleSpec("%s");
3848         immutable len = _data ? _data.arr.length : 0;
3849         // different reserve lengths because each element in a
3850         // non-string-like array uses two extra characters for `, `.
3851         static if (isSomeString!A)
3852         {
3853             app.reserve(len + 25);
3854         }
3855         else
3856         {
3857             // Multiplying by three is a very conservative estimate of
3858             // length, as it assumes each element is only one char
3859             app.reserve((len * 3) + 25);
3860         }
3861         toString(app, spec);
3862         return app.data;
3863     }
3864 
3865     import std.format.spec : FormatSpec;
3866 
3867     /// ditto
3868     template toString(Writer)
3869     if (isOutputRange!(Writer, char))
3870     {
3871         void toString(ref Writer w, scope const ref FormatSpec!char fmt) const
3872         {
3873             import std.format.write : formatValue;
3874             import std.range.primitives : put;
3875             put(w, Unqual!(typeof(this)).stringof);
3876             put(w, '(');
3877             formatValue(w, data, fmt);
3878             put(w, ')');
3879         }
3880     }
3881 }
3882 
3883 ///
3884 @safe pure nothrow unittest
3885 {
3886     auto app = appender!string();
3887     string b = "abcdefg";
3888     foreach (char c; b)
3889         app.put(c);
3890     assert(app[] == "abcdefg");
3891 
3892     int[] a = [ 1, 2 ];
3893     auto app2 = appender(a);
3894     app2.put(3);
3895     app2.put([ 4, 5, 6 ]);
3896     assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
3897 }
3898 
3899 @safe pure unittest
3900 {
3901     import std.format : format;
3902     import std.format.spec : singleSpec;
3903 
3904     auto app = appender!(int[])();
3905     app.put(1);
3906     app.put(2);
3907     app.put(3);
3908     assert("%s".format(app) == "Appender!(int[])(%s)".format([1,2,3]));
3909 
3910     auto app2 = appender!string();
3911     auto spec = singleSpec("%s");
3912     app.toString(app2, spec);
3913     assert(app2[] == "Appender!(int[])([1, 2, 3])");
3914 
3915     auto app3 = appender!string();
3916     spec = singleSpec("%(%04d, %)");
3917     app.toString(app3, spec);
3918     assert(app3[] == "Appender!(int[])(0001, 0002, 0003)");
3919 }
3920 
3921 // https://issues.dlang.org/show_bug.cgi?id=17251
3922 @safe pure nothrow unittest
3923 {
3924     static struct R
3925     {
3926         int front() const { return 0; }
3927         bool empty() const { return true; }
3928         void popFront() {}
3929     }
3930 
3931     auto app = appender!(R[]);
3932     const(R)[1] r;
3933     app.put(r[0]);
3934     app.put(r[]);
3935 }
3936 
3937 // https://issues.dlang.org/show_bug.cgi?id=13300
3938 @safe pure nothrow unittest
3939 {
3940     static test(bool isPurePostblit)()
3941     {
3942         static if (!isPurePostblit)
3943             static int i;
3944 
3945         struct Simple
3946         {
3947             @disable this(); // Without this, it works.
3948             static if (!isPurePostblit)
3949                 this(this) { i++; }
3950             else
3951                 pure this(this) { }
3952 
3953             private:
3954             this(int tmp) { }
3955         }
3956 
3957         struct Range
3958         {
3959             @property Simple front() { return Simple(0); }
3960             void popFront() { count++; }
3961             @property empty() { return count < 3; }
3962             size_t count;
3963         }
3964 
3965         Range r;
3966         auto a = r.array();
3967     }
3968 
3969     static assert(__traits(compiles, () pure { test!true(); }));
3970     static assert(!__traits(compiles, () pure { test!false(); }));
3971 }
3972 
3973 // https://issues.dlang.org/show_bug.cgi?id=19572
3974 @safe pure nothrow unittest
3975 {
3976     static struct Struct
3977     {
3978         int value;
3979 
3980         int fun() const { return 23; }
3981 
3982         alias fun this;
3983     }
3984 
3985     Appender!(Struct[]) appender;
3986 
3987     appender.put(const(Struct)(42));
3988 
3989     auto result = appender[][0];
3990 
3991     assert(result.value != 23);
3992 }
3993 
3994 @safe pure unittest
3995 {
3996     import std.conv : to;
3997     import std.utf : byCodeUnit;
3998     auto str = "ウェブサイト";
3999     auto wstr = appender!wstring();
4000     put(wstr, str.byCodeUnit);
4001     assert(wstr.data == str.to!wstring);
4002 }
4003 
4004 // https://issues.dlang.org/show_bug.cgi?id=21256
4005 @safe pure unittest
4006 {
4007     Appender!string app1;
4008     app1.toString();
4009 
4010     Appender!(int[]) app2;
4011     app2.toString();
4012 }
4013 
4014 //Calculates an efficient growth scheme based on the old capacity
4015 //of data, and the minimum requested capacity.
4016 //arg curLen: The current length
4017 //arg reqLen: The length as requested by the user
4018 //ret sugLen: A suggested growth.
4019 private size_t appenderNewCapacity(size_t TSizeOf)(size_t curLen, size_t reqLen)
4020 {
4021     import core.bitop : bsr;
4022     import std.algorithm.comparison : max;
4023     if (curLen == 0)
4024         return max(reqLen,8);
4025     ulong mult = 100 + (1000UL) / (bsr(curLen * TSizeOf) + 1);
4026     // limit to doubling the length, we don't want to grow too much
4027     if (mult > 200)
4028         mult = 200;
4029     auto sugLen = cast(size_t)((curLen * mult + 99) / 100);
4030     return max(reqLen, sugLen);
4031 }
4032 
4033 /**
4034  * A version of $(LREF Appender) that can update an array in-place.
4035  * It forwards all calls to an underlying appender implementation.
4036  * Any calls made to the appender also update the pointer to the
4037  * original array passed in.
4038  *
4039  * Tip: Use the `arrayPtr` overload of $(LREF appender) for construction with type-inference.
4040  *
4041  * Params:
4042  *     A = The array type to simulate
4043  */
4044 struct RefAppender(A)
4045 if (isDynamicArray!A)
4046 {
4047     private alias T = ElementEncodingType!A;
4048 
4049     private
4050     {
4051         Appender!A impl;
4052         A* arr;
4053     }
4054 
4055     /**
4056      * Constructs a `RefAppender` with a given array reference.  This does not copy the
4057      * data.  If the array has a larger capacity as determined by `arr.capacity`, it
4058      * will be used by the appender.
4059      *
4060      * Note: Do not use built-in appending (i.e. `~=`) on the original array
4061      * until you are done with the appender, because subsequent calls to the appender
4062      * will reallocate the array data without those appends.
4063      *
4064      * Params:
4065      * arr = Pointer to an array. Must not be _null.
4066      */
4067     this(A* arr)
4068     {
4069         impl = Appender!A(*arr);
4070         this.arr = arr;
4071     }
4072 
4073     /** Wraps remaining `Appender` methods such as $(LREF put).
4074      * Params:
4075      * fn = Method name to call.
4076      * args = Arguments to pass to the method.
4077      */
4078     void opDispatch(string fn, Args...)(Args args)
4079     if (__traits(compiles, (Appender!A a) => mixin("a." ~ fn ~ "(args)")))
4080     {
4081         // we do it this way because we can't cache a void return
4082         scope(exit) *this.arr = impl[];
4083         mixin("return impl." ~ fn ~ "(args);");
4084     }
4085 
4086     /**
4087      * Appends `rhs` to the managed array.
4088      * Params:
4089      * rhs = Element or range.
4090      */
4091     void opOpAssign(string op : "~", U)(U rhs)
4092     if (__traits(compiles, (Appender!A a){ a.put(rhs); }))
4093     {
4094         scope(exit) *this.arr = impl[];
4095         impl.put(rhs);
4096     }
4097 
4098     /**
4099      * Returns the capacity of the array (the maximum number of elements the
4100      * managed array can accommodate before triggering a reallocation).  If any
4101      * appending will reallocate, `capacity` returns `0`.
4102      */
4103     @property size_t capacity() const
4104     {
4105         return impl.capacity;
4106     }
4107 
4108     /* Use opSlice() instead.
4109      * Returns: the managed array.
4110      */
4111     @property inout(T)[] data() inout
4112     {
4113         return impl[];
4114     }
4115 
4116     /**
4117      * Returns: the managed array.
4118      */
4119     @property inout(ElementEncodingType!A)[] opSlice() inout
4120     {
4121         return impl[];
4122     }
4123 }
4124 
4125 ///
4126 @safe pure nothrow
4127 unittest
4128 {
4129     int[] a = [1, 2];
4130     auto app2 = appender(&a);
4131     assert(app2[] == [1, 2]);
4132     assert(a == [1, 2]);
4133     app2 ~= 3;
4134     app2 ~= [4, 5, 6];
4135     assert(app2[] == [1, 2, 3, 4, 5, 6]);
4136     assert(a == [1, 2, 3, 4, 5, 6]);
4137 
4138     app2.reserve(5);
4139     assert(app2.capacity >= 5);
4140 }
4141 
4142 /++
4143     Convenience function that returns an $(LREF Appender) instance,
4144     optionally initialized with `array`.
4145  +/
4146 Appender!A appender(A)()
4147 if (isDynamicArray!A)
4148 {
4149     return Appender!A(null);
4150 }
4151 /// ditto
4152 Appender!(E[]) appender(A : E[], E)(auto ref A array)
4153 {
4154     static assert(!isStaticArray!A || __traits(isRef, array),
4155         "Cannot create Appender from an rvalue static array");
4156 
4157     return Appender!(E[])(array);
4158 }
4159 
4160 @safe pure nothrow unittest
4161 {
4162     auto app = appender!(char[])();
4163     string b = "abcdefg";
4164     foreach (char c; b) app.put(c);
4165     assert(app[] == "abcdefg");
4166 }
4167 
4168 @safe pure nothrow unittest
4169 {
4170     auto app = appender!(char[])();
4171     string b = "abcdefg";
4172     foreach (char c; b) app ~= c;
4173     assert(app[] == "abcdefg");
4174 }
4175 
4176 @safe pure nothrow unittest
4177 {
4178     int[] a = [ 1, 2 ];
4179     auto app2 = appender(a);
4180     assert(app2[] == [ 1, 2 ]);
4181     app2.put(3);
4182     app2.put([ 4, 5, 6 ][]);
4183     assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
4184     app2.put([ 7 ]);
4185     assert(app2[] == [ 1, 2, 3, 4, 5, 6, 7 ]);
4186 }
4187 
4188 @safe pure nothrow unittest
4189 {
4190     auto app4 = appender([]);
4191     try // shrinkTo may throw
4192     {
4193         app4.shrinkTo(0);
4194     }
4195     catch (Exception) assert(0);
4196 }
4197 
4198 // https://issues.dlang.org/show_bug.cgi?id=5663
4199 // https://issues.dlang.org/show_bug.cgi?id=9725
4200 @safe pure nothrow unittest
4201 {
4202     import std.exception : assertNotThrown;
4203 
4204     static foreach (S; AliasSeq!(char[], const(char)[], string))
4205     {
4206         {
4207             Appender!S app5663i;
4208             assertNotThrown(app5663i.put("\xE3"));
4209             assert(app5663i[] == "\xE3");
4210 
4211             Appender!S app5663c;
4212             assertNotThrown(app5663c.put(cast(const(char)[])"\xE3"));
4213             assert(app5663c[] == "\xE3");
4214 
4215             Appender!S app5663m;
4216             assertNotThrown(app5663m.put("\xE3".dup));
4217             assert(app5663m[] == "\xE3");
4218         }
4219         // ditto for ~=
4220         {
4221             Appender!S app5663i;
4222             assertNotThrown(app5663i ~= "\xE3");
4223             assert(app5663i[] == "\xE3");
4224 
4225             Appender!S app5663c;
4226             assertNotThrown(app5663c ~= cast(const(char)[])"\xE3");
4227             assert(app5663c[] == "\xE3");
4228 
4229             Appender!S app5663m;
4230             assertNotThrown(app5663m ~= "\xE3".dup);
4231             assert(app5663m[] == "\xE3");
4232         }
4233     }
4234 }
4235 
4236 // https://issues.dlang.org/show_bug.cgi?id=10122
4237 @safe pure nothrow unittest
4238 {
4239     import std.exception : assertCTFEable;
4240 
4241     static struct S10122
4242     {
4243         int val;
4244 
4245         @disable this();
4246         this(int v) @safe pure nothrow { val = v; }
4247     }
4248     assertCTFEable!(
4249     {
4250         auto w = appender!(S10122[])();
4251         w.put(S10122(1));
4252         assert(w[].length == 1 && w[][0].val == 1);
4253     });
4254 }
4255 
4256 @safe pure nothrow unittest
4257 {
4258     import std.exception : assertThrown;
4259 
4260     int[] a = [ 1, 2 ];
4261     auto app2 = appender(a);
4262     assert(app2[] == [ 1, 2 ]);
4263     app2 ~= 3;
4264     app2 ~= [ 4, 5, 6 ][];
4265     assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
4266     app2 ~= [ 7 ];
4267     assert(app2[] == [ 1, 2, 3, 4, 5, 6, 7 ]);
4268 
4269     app2.reserve(5);
4270     assert(app2.capacity >= 5);
4271 
4272     try // shrinkTo may throw
4273     {
4274         app2.shrinkTo(3);
4275     }
4276     catch (Exception) assert(0);
4277     assert(app2[] == [ 1, 2, 3 ]);
4278     assertThrown(app2.shrinkTo(5));
4279 
4280     const app3 = app2;
4281     assert(app3.capacity >= 3);
4282     assert(app3[] == [1, 2, 3]);
4283 }
4284 
4285 ///
4286 @safe pure nothrow
4287 unittest
4288 {
4289     auto w = appender!string;
4290     // pre-allocate space for at least 10 elements (this avoids costly reallocations)
4291     w.reserve(10);
4292     assert(w.capacity >= 10);
4293 
4294     w.put('a'); // single elements
4295     w.put("bc"); // multiple elements
4296 
4297     // use the append syntax
4298     w ~= 'd';
4299     w ~= "ef";
4300 
4301     assert(w[] == "abcdef");
4302 }
4303 
4304 @safe pure nothrow unittest
4305 {
4306     auto w = appender!string();
4307     w.reserve(4);
4308     cast(void) w.capacity;
4309     cast(void) w[];
4310     try
4311     {
4312         wchar wc = 'a';
4313         dchar dc = 'a';
4314         w.put(wc);    // decoding may throw
4315         w.put(dc);    // decoding may throw
4316     }
4317     catch (Exception) assert(0);
4318 }
4319 
4320 @safe pure nothrow unittest
4321 {
4322     auto w = appender!(int[])();
4323     w.reserve(4);
4324     cast(void) w.capacity;
4325     cast(void) w[];
4326     w.put(10);
4327     w.put([10]);
4328     w.clear();
4329     try
4330     {
4331         w.shrinkTo(0);
4332     }
4333     catch (Exception) assert(0);
4334 
4335     struct N
4336     {
4337         int payload;
4338         alias payload this;
4339     }
4340     w.put(N(1));
4341     w.put([N(2)]);
4342 
4343     struct S(T)
4344     {
4345         @property bool empty() { return true; }
4346         @property T front() { return T.init; }
4347         void popFront() {}
4348     }
4349     S!int r;
4350     w.put(r);
4351 }
4352 
4353 // https://issues.dlang.org/show_bug.cgi?id=10690
4354 @safe pure nothrow unittest
4355 {
4356     import std.algorithm.iteration : filter;
4357     import std.typecons : tuple;
4358     [tuple(1)].filter!(t => true).array; // No error
4359     [tuple("A")].filter!(t => true).array; // error
4360 }
4361 
4362 @safe pure nothrow unittest
4363 {
4364     import std.range;
4365     //Coverage for put(Range)
4366     struct S1
4367     {
4368     }
4369     struct S2
4370     {
4371         void opAssign(S2){}
4372     }
4373     auto a1 = Appender!(S1[])();
4374     auto a2 = Appender!(S2[])();
4375     auto au1 = Appender!(const(S1)[])();
4376     a1.put(S1().repeat().take(10));
4377     a2.put(S2().repeat().take(10));
4378     auto sc1 = const(S1)();
4379     au1.put(sc1.repeat().take(10));
4380 }
4381 
4382 @system pure unittest
4383 {
4384     import std.range;
4385     struct S2
4386     {
4387         void opAssign(S2){}
4388     }
4389     auto au2 = Appender!(const(S2)[])();
4390     auto sc2 = const(S2)();
4391     au2.put(sc2.repeat().take(10));
4392 }
4393 
4394 @system pure nothrow unittest
4395 {
4396     struct S
4397     {
4398         int* p;
4399     }
4400 
4401     auto a0 = Appender!(S[])();
4402     auto a1 = Appender!(const(S)[])();
4403     auto a2 = Appender!(immutable(S)[])();
4404     auto s0 = S(null);
4405     auto s1 = const(S)(null);
4406     auto s2 = immutable(S)(null);
4407     a1.put(s0);
4408     a1.put(s1);
4409     a1.put(s2);
4410     a1.put([s0]);
4411     a1.put([s1]);
4412     a1.put([s2]);
4413     a0.put(s0);
4414     static assert(!is(typeof(a0.put(a1))));
4415     static assert(!is(typeof(a0.put(a2))));
4416     a0.put([s0]);
4417     static assert(!is(typeof(a0.put([a1]))));
4418     static assert(!is(typeof(a0.put([a2]))));
4419     static assert(!is(typeof(a2.put(a0))));
4420     static assert(!is(typeof(a2.put(a1))));
4421     a2.put(s2);
4422     static assert(!is(typeof(a2.put([a0]))));
4423     static assert(!is(typeof(a2.put([a1]))));
4424     a2.put([s2]);
4425 }
4426 
4427 // https://issues.dlang.org/show_bug.cgi?id=9528
4428 @safe pure nothrow unittest
4429 {
4430     const(E)[] fastCopy(E)(E[] src) {
4431             auto app = appender!(const(E)[])();
4432             foreach (i, e; src)
4433                     app.put(e);
4434             return app[];
4435     }
4436 
4437     static class C {}
4438     static struct S { const(C) c; }
4439     S[] s = [ S(new C) ];
4440 
4441     auto t = fastCopy(s); // Does not compile
4442     assert(t.length == 1);
4443 }
4444 
4445 // https://issues.dlang.org/show_bug.cgi?id=10753
4446 @safe pure unittest
4447 {
4448     import std.algorithm.iteration : map;
4449     struct Foo {
4450        immutable dchar d;
4451     }
4452     struct Bar {
4453        immutable int x;
4454     }
4455     "12".map!Foo.array;
4456     [1, 2].map!Bar.array;
4457 }
4458 
4459 @safe pure nothrow unittest
4460 {
4461     import std.algorithm.comparison : equal;
4462 
4463     //New appender signature tests
4464     alias mutARR = int[];
4465     alias conARR = const(int)[];
4466     alias immARR = immutable(int)[];
4467 
4468     mutARR mut;
4469     conARR con;
4470     immARR imm;
4471 
4472     auto app1 = Appender!mutARR(mut);                //Always worked. Should work. Should not create a warning.
4473     app1.put(7);
4474     assert(equal(app1[], [7]));
4475     static assert(!is(typeof(Appender!mutARR(con)))); //Never worked.  Should not work.
4476     static assert(!is(typeof(Appender!mutARR(imm)))); //Never worked.  Should not work.
4477 
4478     auto app2 = Appender!conARR(mut); //Always worked. Should work. Should not create a warning.
4479     app2.put(7);
4480     assert(equal(app2[], [7]));
4481     auto app3 = Appender!conARR(con); //Didn't work.   Now works.   Should not create a warning.
4482     app3.put(7);
4483     assert(equal(app3[], [7]));
4484     auto app4 = Appender!conARR(imm); //Didn't work.   Now works.   Should not create a warning.
4485     app4.put(7);
4486     assert(equal(app4[], [7]));
4487 
4488     //{auto app = Appender!immARR(mut);}                //Worked. Will cease to work. Creates warning.
4489     //static assert(!is(typeof(Appender!immARR(mut)))); //Worked. Will cease to work. Uncomment me after full deprecation.
4490     static assert(!is(typeof(Appender!immARR(con))));   //Never worked. Should not work.
4491     auto app5 = Appender!immARR(imm);                  //Didn't work.  Now works. Should not create a warning.
4492     app5.put(7);
4493     assert(equal(app5[], [7]));
4494 
4495     //Deprecated. Please uncomment and make sure this doesn't work:
4496     //char[] cc;
4497     //static assert(!is(typeof(Appender!string(cc))));
4498 
4499     //This should always work:
4500     auto app6 = appender!string(null);
4501     assert(app6[] == null);
4502     auto app7 = appender!(const(char)[])(null);
4503     assert(app7[] == null);
4504     auto app8 = appender!(char[])(null);
4505     assert(app8[] == null);
4506 }
4507 
4508 @safe pure nothrow unittest //Test large allocations (for GC.extend)
4509 {
4510     import std.algorithm.comparison : equal;
4511     import std.range;
4512     Appender!(char[]) app;
4513     app.reserve(1); //cover reserve on non-initialized
4514     foreach (_; 0 .. 100_000)
4515         app.put('a');
4516     assert(equal(app[], 'a'.repeat(100_000)));
4517 }
4518 
4519 @safe pure nothrow unittest
4520 {
4521     auto reference = new ubyte[](2048 + 1); //a number big enough to have a full page (EG: the GC extends)
4522     auto arr = reference.dup;
4523     auto app = appender(arr[0 .. 0]);
4524     app.reserve(1); //This should not trigger a call to extend
4525     app.put(ubyte(1)); //Don't clobber arr
4526     assert(reference[] == arr[]);
4527 }
4528 
4529 @safe pure nothrow unittest // clear method is supported only for mutable element types
4530 {
4531     Appender!string app;
4532     app.put("foo");
4533     static assert(!__traits(compiles, app.clear()));
4534     assert(app[] == "foo");
4535 }
4536 
4537 @safe pure nothrow unittest
4538 {
4539     static struct D//dynamic
4540     {
4541         int[] i;
4542         alias i this;
4543     }
4544     static struct S//static
4545     {
4546         int[5] i;
4547         alias i this;
4548     }
4549     static assert(!is(Appender!(char[5])));
4550     static assert(!is(Appender!D));
4551     static assert(!is(Appender!S));
4552 
4553     enum int[5] a = [];
4554     int[5] b;
4555     D d;
4556     S s;
4557     int[5] foo(){return a;}
4558 
4559     static assert(!is(typeof(appender(a))));
4560     static assert( is(typeof(appender(b))));
4561     static assert( is(typeof(appender(d))));
4562     static assert( is(typeof(appender(s))));
4563     static assert(!is(typeof(appender(foo()))));
4564 }
4565 
4566 @system unittest
4567 {
4568     // https://issues.dlang.org/show_bug.cgi?id=13077
4569     static class A {}
4570 
4571     // reduced case
4572     auto w = appender!(shared(A)[])();
4573     w.put(new shared A());
4574 
4575     // original case
4576     import std.range;
4577     InputRange!(shared A) foo()
4578     {
4579         return [new shared A].inputRangeObject;
4580     }
4581     auto res = foo.array;
4582     assert(res.length == 1);
4583 }
4584 
4585 /++
4586     Convenience function that returns a $(LREF RefAppender) instance initialized
4587     with `arrayPtr`. Don't use null for the array pointer, use the other
4588     version of `appender` instead.
4589  +/
4590 RefAppender!(E[]) appender(P : E[]*, E)(P arrayPtr)
4591 {
4592     return RefAppender!(E[])(arrayPtr);
4593 }
4594 
4595 ///
4596 @safe pure nothrow
4597 unittest
4598 {
4599     int[] a = [1, 2];
4600     auto app2 = appender(&a);
4601     assert(app2[] == [1, 2]);
4602     assert(a == [1, 2]);
4603     app2 ~= 3;
4604     app2 ~= [4, 5, 6];
4605     assert(app2[] == [1, 2, 3, 4, 5, 6]);
4606     assert(a == [1, 2, 3, 4, 5, 6]);
4607 
4608     app2.reserve(5);
4609     assert(app2.capacity >= 5);
4610 }
4611 
4612 @safe pure nothrow unittest
4613 {
4614     auto arr = new char[0];
4615     auto app = appender(&arr);
4616     string b = "abcdefg";
4617     foreach (char c; b) app.put(c);
4618     assert(app[] == "abcdefg");
4619     assert(arr == "abcdefg");
4620 }
4621 
4622 @safe pure nothrow unittest
4623 {
4624     auto arr = new char[0];
4625     auto app = appender(&arr);
4626     string b = "abcdefg";
4627     foreach (char c; b) app ~= c;
4628     assert(app[] == "abcdefg");
4629     assert(arr == "abcdefg");
4630 }
4631 
4632 @safe pure nothrow unittest
4633 {
4634     int[] a = [ 1, 2 ];
4635     auto app2 = appender(&a);
4636     assert(app2[] == [ 1, 2 ]);
4637     assert(a == [ 1, 2 ]);
4638     app2.put(3);
4639     app2.put([ 4, 5, 6 ][]);
4640     assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
4641     assert(a == [ 1, 2, 3, 4, 5, 6 ]);
4642 }
4643 
4644 @safe pure nothrow unittest
4645 {
4646     import std.exception : assertThrown;
4647 
4648     int[] a = [ 1, 2 ];
4649     auto app2 = appender(&a);
4650     assert(app2[] == [ 1, 2 ]);
4651     assert(a == [ 1, 2 ]);
4652     app2 ~= 3;
4653     app2 ~= [ 4, 5, 6 ][];
4654     assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
4655     assert(a == [ 1, 2, 3, 4, 5, 6 ]);
4656 
4657     app2.reserve(5);
4658     assert(app2.capacity >= 5);
4659 
4660     try // shrinkTo may throw
4661     {
4662         app2.shrinkTo(3);
4663     }
4664     catch (Exception) assert(0);
4665     assert(app2[] == [ 1, 2, 3 ]);
4666     assertThrown(app2.shrinkTo(5));
4667 
4668     const app3 = app2;
4669     assert(app3.capacity >= 3);
4670     assert(app3[] == [1, 2, 3]);
4671 }
4672 
4673 // https://issues.dlang.org/show_bug.cgi?id=14605
4674 @safe pure nothrow unittest
4675 {
4676     static assert(isOutputRange!(Appender!(int[]), int));
4677     static assert(isOutputRange!(RefAppender!(int[]), int));
4678 }
4679 
4680 @safe pure nothrow unittest
4681 {
4682     Appender!(int[]) app;
4683     short[] range = [1, 2, 3];
4684     app.put(range);
4685     assert(app[] == [1, 2, 3]);
4686 }
4687 
4688 @safe pure nothrow unittest
4689 {
4690     string s = "hello".idup;
4691     char[] a = "hello".dup;
4692     auto appS = appender(s);
4693     auto appA = appender(a);
4694     put(appS, 'w');
4695     put(appA, 'w');
4696     s ~= 'a'; //Clobbers here?
4697     a ~= 'a'; //Clobbers here?
4698     assert(appS[] == "hellow");
4699     assert(appA[] == "hellow");
4700 }
4701 
4702 /++
4703 Constructs a static array from a dynamic array whose length is known at compile-time.
4704 The element type can be inferred or specified explicitly:
4705 
4706 * $(D [1, 2].staticArray) returns `int[2]`
4707 * $(D [1, 2].staticArray!float) returns `float[2]`
4708 
4709 Note: `staticArray` returns by value, so expressions involving large arrays may be inefficient.
4710 
4711 Params:
4712     a = The input array.
4713 
4714 Returns: A static array constructed from `a`.
4715 +/
4716 pragma(inline, true) T[n] staticArray(T, size_t n)(auto ref T[n] a)
4717 {
4718     return a;
4719 }
4720 
4721 /// static array from array literal
4722 nothrow pure @safe @nogc unittest
4723 {
4724     auto a = [0, 1].staticArray;
4725     static assert(is(typeof(a) == int[2]));
4726     assert(a == [0, 1]);
4727 }
4728 
4729 /// ditto
4730 pragma(inline, true) U[n] staticArray(U, T, size_t n)(auto ref T[n] a)
4731 if (!is(T == U) && is(T : U))
4732 {
4733     return a[].staticArray!(U[n]);
4734 }
4735 
4736 /// static array from array with implicit casting of elements
4737 nothrow pure @safe @nogc unittest
4738 {
4739     auto b = [0, 1].staticArray!long;
4740     static assert(is(typeof(b) == long[2]));
4741     assert(b == [0, 1]);
4742 }
4743 
4744 nothrow pure @safe @nogc unittest
4745 {
4746     int val = 3;
4747     static immutable gold = [1, 2, 3];
4748     [1, 2, val].staticArray.checkStaticArray!int([1, 2, 3]);
4749 
4750     @nogc void checkNogc()
4751     {
4752         [1, 2, val].staticArray.checkStaticArray!int(gold);
4753     }
4754 
4755     checkNogc();
4756 
4757     [1, 2, val].staticArray!double.checkStaticArray!double(gold);
4758     [1, 2, 3].staticArray!int.checkStaticArray!int(gold);
4759 
4760     [1, 2, 3].staticArray!(const(int)).checkStaticArray!(const(int))(gold);
4761     [1, 2, 3].staticArray!(const(double)).checkStaticArray!(const(double))(gold);
4762     {
4763         const(int)[3] a2 = [1, 2, 3].staticArray;
4764     }
4765 
4766     [cast(byte) 1, cast(byte) 129].staticArray.checkStaticArray!byte([1, -127]);
4767 }
4768 
4769 /**
4770 Constructs a static array from a range.
4771 When `a.length` is not known at compile time, the number of elements must be
4772 given as a template argument (e.g. `myrange.staticArray!2`).
4773 Size and type can be combined, if the source range elements are implicitly
4774 convertible to the requested element type (eg: `2.iota.staticArray!(long[2])`).
4775 
4776 When the range `a` is known at compile time, it can be given as a
4777 template argument to avoid having to specify the number of elements
4778 (e.g.: `staticArray!(2.iota)` or `staticArray!(double, 2.iota)`).
4779 
4780 Params:
4781     a = The input range. If there are less elements than the specified length of the static array,
4782     the rest of it is default-initialized. If there are more than specified, the first elements
4783     up to the specified length are used.
4784     rangeLength = Output for the number of elements used from `a`. Optional.
4785 */
4786 auto staticArray(size_t n, T)(scope T a)
4787 if (isInputRange!T)
4788 {
4789     alias U = ElementType!T;
4790     return staticArray!(U[n], U, n)(a);
4791 }
4792 
4793 /// ditto
4794 auto staticArray(size_t n, T)(scope T a, out size_t rangeLength)
4795 if (isInputRange!T)
4796 {
4797     alias U = ElementType!T;
4798     return staticArray!(U[n], U, n)(a, rangeLength);
4799 }
4800 
4801 /// ditto
4802 auto staticArray(Un : U[n], U, size_t n, T)(scope T a)
4803 if (isInputRange!T && is(ElementType!T : U))
4804 {
4805     size_t extraStackSpace;
4806     return staticArray!(Un, U, n)(a, extraStackSpace);
4807 }
4808 
4809 /// ditto
4810 auto staticArray(Un : U[n], U, size_t n, T)(scope T a, out size_t rangeLength)
4811 if (isInputRange!T && is(ElementType!T : U))
4812 {
4813     import std.algorithm.mutation : uninitializedFill;
4814     import std.range : take;
4815     import core.internal.lifetime : emplaceRef;
4816 
4817     if (__ctfe)
4818     {
4819         size_t i;
4820         // Compile-time version to avoid unchecked memory access.
4821         Unqual!U[n] ret;
4822         for (auto iter = a.take(n); !iter.empty; iter.popFront())
4823         {
4824             ret[i] = iter.front;
4825             i++;
4826         }
4827 
4828         rangeLength = i;
4829         return (() @trusted => cast(U[n]) ret)();
4830     }
4831 
4832     auto ret = (() @trusted
4833     {
4834         Unqual!U[n] theArray = void;
4835         return theArray;
4836     }());
4837 
4838     size_t i;
4839     if (true)
4840     {
4841         // ret was void-initialized so let's initialize the unfilled part manually.
4842         // also prevents destructors to be called on uninitialized memory if
4843         // an exception is thrown
4844         scope (exit) ret[i .. $].uninitializedFill(U.init);
4845 
4846         for (auto iter = a.take(n); !iter.empty; iter.popFront())
4847         {
4848             emplaceRef!U(ret[i++], iter.front);
4849         }
4850     }
4851 
4852     rangeLength = i;
4853     return (() @trusted => cast(U[n]) ret)();
4854 }
4855 
4856 /// static array from range + size
4857 nothrow pure @safe @nogc unittest
4858 {
4859     import std.range : iota;
4860 
4861     auto input = 3.iota;
4862     auto a = input.staticArray!2;
4863     static assert(is(typeof(a) == int[2]));
4864     assert(a == [0, 1]);
4865     auto b = input.staticArray!(long[4]);
4866     static assert(is(typeof(b) == long[4]));
4867     assert(b == [0, 1, 2, 0]);
4868 }
4869 
4870 // Tests that code compiles when there is an elaborate destructor and exceptions
4871 // are thrown. Unfortunately can't test that memory is initialized
4872 // before having a destructor called on it.
4873 @safe nothrow unittest
4874 {
4875     // exists only to allow doing something in the destructor. Not tested
4876     // at the end because value appears to depend on implementation of the.
4877     // function.
4878     static int preventersDestroyed = 0;
4879 
4880     static struct CopyPreventer
4881     {
4882         bool on = false;
4883         this(this)
4884         {
4885             if (on) throw new Exception("Thou shalt not copy past me!");
4886         }
4887 
4888         ~this()
4889         {
4890             preventersDestroyed++;
4891         }
4892     }
4893     auto normalArray =
4894     [
4895         CopyPreventer(false),
4896         CopyPreventer(false),
4897         CopyPreventer(true),
4898         CopyPreventer(false),
4899         CopyPreventer(true),
4900     ];
4901 
4902     try
4903     {
4904         auto staticArray = normalArray.staticArray!5;
4905         assert(false);
4906     }
4907     catch (Exception e){}
4908 }
4909 
4910 
4911 nothrow pure @safe @nogc unittest
4912 {
4913     auto a = [1, 2].staticArray;
4914     assert(is(typeof(a) == int[2]) && a == [1, 2]);
4915 
4916     import std.range : iota;
4917 
4918     2.iota.staticArray!2.checkStaticArray!int([0, 1]);
4919     2.iota.staticArray!(double[2]).checkStaticArray!double([0, 1]);
4920     2.iota.staticArray!(long[2]).checkStaticArray!long([0, 1]);
4921 }
4922 
4923 nothrow pure @safe @nogc unittest
4924 {
4925     import std.range : iota;
4926     size_t copiedAmount;
4927     2.iota.staticArray!1(copiedAmount);
4928     assert(copiedAmount == 1);
4929     2.iota.staticArray!3(copiedAmount);
4930     assert(copiedAmount == 2);
4931 }
4932 
4933 /// ditto
4934 auto staticArray(alias a)()
4935 if (isInputRange!(typeof(a)))
4936 {
4937     return .staticArray!(size_t(a.length))(a);
4938 }
4939 
4940 /// ditto
4941 auto staticArray(U, alias a)()
4942 if (isInputRange!(typeof(a)))
4943 {
4944     return .staticArray!(U[size_t(a.length)])(a);
4945 }
4946 
4947 /// static array from CT range
4948 nothrow pure @safe @nogc unittest
4949 {
4950     import std.range : iota;
4951 
4952     enum a = staticArray!(2.iota);
4953     static assert(is(typeof(a) == int[2]));
4954     assert(a == [0, 1]);
4955 
4956     enum b = staticArray!(long, 2.iota);
4957     static assert(is(typeof(b) == long[2]));
4958     assert(b == [0, 1]);
4959 }
4960 
4961 nothrow pure @safe @nogc unittest
4962 {
4963     import std.range : iota;
4964 
4965     enum a = staticArray!(2.iota);
4966     staticArray!(2.iota).checkStaticArray!int([0, 1]);
4967     staticArray!(double, 2.iota).checkStaticArray!double([0, 1]);
4968     staticArray!(long, 2.iota).checkStaticArray!long([0, 1]);
4969 }
4970 
4971 version (StdUnittest) private void checkStaticArray(T, T1, T2)(T1 a, T2 b) nothrow @safe pure @nogc
4972 {
4973     static assert(is(T1 == T[T1.length]));
4974     assert(a == b, "a must be equal to b");
4975 }