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