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 @safe pure nothrow unittest
1301 {
1302     static void test(L, R)(L l, R r)
1303     {
1304         assert(overlap(l, r) == [ 100, 12 ]);
1305 
1306         assert(overlap(l, l[0 .. 2]) is l[0 .. 2]);
1307         assert(overlap(l, l[3 .. 5]) is l[3 .. 5]);
1308         assert(overlap(l[0 .. 2], l) is l[0 .. 2]);
1309         assert(overlap(l[3 .. 5], l) is l[3 .. 5]);
1310     }
1311 
1312     int[] a = [ 10, 11, 12, 13, 14 ];
1313     int[] b = a[1 .. 3];
1314     a[1] = 100;
1315 
1316     immutable int[] c = a.idup;
1317     immutable int[] d = c[1 .. 3];
1318 
1319     test(a, b);
1320     assert(overlap(a, b.dup).empty);
1321     test(c, d);
1322     assert(overlap(c, d.dup.idup).empty);
1323 }
1324 
1325  // https://issues.dlang.org/show_bug.cgi?id=9836
1326 @safe pure nothrow unittest
1327 {
1328     // range primitives for array should work with alias this types
1329     struct Wrapper
1330     {
1331         int[] data;
1332         alias data this;
1333 
1334         @property Wrapper save() { return this; }
1335     }
1336     auto w = Wrapper([1,2,3,4]);
1337     std.array.popFront(w); // should work
1338 
1339     static assert(isInputRange!Wrapper);
1340     static assert(isForwardRange!Wrapper);
1341     static assert(isBidirectionalRange!Wrapper);
1342     static assert(isRandomAccessRange!Wrapper);
1343 }
1344 
1345 private void copyBackwards(T)(T[] src, T[] dest)
1346 {
1347     import core.stdc.string : memmove;
1348     import std.format : format;
1349 
1350     assert(src.length == dest.length, format!
1351             "src.length %s must equal dest.length %s"(src.length, dest.length));
1352 
1353     if (!__ctfe || hasElaborateCopyConstructor!T)
1354     {
1355         /* insertInPlace relies on dest being uninitialized, so no postblits allowed,
1356          * as this is a MOVE that overwrites the destination, not a COPY.
1357          * BUG: insertInPlace will not work with ctfe and postblits
1358          */
1359         memmove(dest.ptr, src.ptr, src.length * T.sizeof);
1360     }
1361     else
1362     {
1363         immutable len = src.length;
1364         for (size_t i = len; i-- > 0;)
1365         {
1366             dest[i] = src[i];
1367         }
1368     }
1369 }
1370 
1371 /++
1372     Inserts `stuff` (which must be an input range or any number of
1373     implicitly convertible items) in `array` at position `pos`.
1374 
1375     Params:
1376         array = The array that `stuff` will be inserted into.
1377         pos   = The position in `array` to insert the `stuff`.
1378         stuff = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives),
1379         or any number of implicitly convertible items to insert into `array`.
1380  +/
1381 void insertInPlace(T, U...)(ref T[] array, size_t pos, U stuff)
1382 if (!isSomeString!(T[])
1383     && allSatisfy!(isInputRangeOrConvertible!T, U) && U.length > 0)
1384 {
1385     static if (allSatisfy!(isInputRangeWithLengthOrConvertible!T, U))
1386     {
1387         import core.internal.lifetime : emplaceRef;
1388 
1389         immutable oldLen = array.length;
1390 
1391         size_t to_insert = 0;
1392         foreach (i, E; U)
1393         {
1394             static if (is(E : T)) //a single convertible value, not a range
1395                 to_insert += 1;
1396             else
1397                 to_insert += stuff[i].length;
1398         }
1399         if (to_insert)
1400         {
1401             array.length += to_insert;
1402 
1403             // Takes arguments array, pos, stuff
1404             // Spread apart array[] at pos by moving elements
1405             (() @trusted { copyBackwards(array[pos .. oldLen], array[pos+to_insert..$]); })();
1406 
1407             // Initialize array[pos .. pos+to_insert] with stuff[]
1408             auto j = 0;
1409             foreach (i, E; U)
1410             {
1411                 static if (is(E : T))
1412                 {
1413                     emplaceRef!T(array[pos + j++], stuff[i]);
1414                 }
1415                 else
1416                 {
1417                     foreach (v; stuff[i])
1418                     {
1419                         emplaceRef!T(array[pos + j++], v);
1420                     }
1421                 }
1422             }
1423         }
1424     }
1425     else
1426     {
1427         // stuff has some InputRanges in it that don't have length
1428         // assume that stuff to be inserted is typically shorter
1429         // then the array that can be arbitrary big
1430         // TODO: needs a better implementation as there is no need to build an _array_
1431         // a singly-linked list of memory blocks (rope, etc.) will do
1432         auto app = appender!(T[])();
1433         foreach (i, E; U)
1434             app.put(stuff[i]);
1435         insertInPlace(array, pos, app.data);
1436     }
1437 }
1438 
1439 /// Ditto
1440 void insertInPlace(T, U...)(ref T[] array, size_t pos, U stuff)
1441 if (isSomeString!(T[]) && allSatisfy!(isCharOrStringOrDcharRange, U))
1442 {
1443     static if (is(Unqual!T == T)
1444         && allSatisfy!(isInputRangeWithLengthOrConvertible!dchar, U))
1445     {
1446         import std.utf : codeLength, byDchar;
1447         // mutable, can do in place
1448         //helper function: re-encode dchar to Ts and store at *ptr
1449         static T* putDChar(T* ptr, dchar ch)
1450         {
1451             static if (is(T == dchar))
1452             {
1453                 *ptr++ = ch;
1454                 return ptr;
1455             }
1456             else
1457             {
1458                 import std.utf : encode;
1459                 T[dchar.sizeof/T.sizeof] buf;
1460                 immutable len = encode(buf, ch);
1461                 final switch (len)
1462                 {
1463                     static if (T.sizeof == char.sizeof)
1464                     {
1465                 case 4:
1466                         ptr[3] = buf[3];
1467                         goto case;
1468                 case 3:
1469                         ptr[2] = buf[2];
1470                         goto case;
1471                     }
1472                 case 2:
1473                     ptr[1] = buf[1];
1474                     goto case;
1475                 case 1:
1476                     ptr[0] = buf[0];
1477                 }
1478                 ptr += len;
1479                 return ptr;
1480             }
1481         }
1482         size_t to_insert = 0;
1483         //count up the number of *codeunits* to insert
1484         foreach (i, E; U)
1485             to_insert += codeLength!T(stuff[i]);
1486         array.length += to_insert;
1487 
1488         @trusted static void moveToRight(T[] arr, size_t gap)
1489         {
1490             static assert(!hasElaborateCopyConstructor!T,
1491                     "T must not have an elaborate copy constructor");
1492             import core.stdc.string : memmove;
1493             if (__ctfe)
1494             {
1495                 for (size_t i = arr.length - gap; i; --i)
1496                     arr[gap + i - 1] = arr[i - 1];
1497             }
1498             else
1499                 memmove(arr.ptr + gap, arr.ptr, (arr.length - gap) * T.sizeof);
1500         }
1501         moveToRight(array[pos .. $], to_insert);
1502         auto ptr = array.ptr + pos;
1503         foreach (i, E; U)
1504         {
1505             static if (is(E : dchar))
1506             {
1507                 ptr = putDChar(ptr, stuff[i]);
1508             }
1509             else
1510             {
1511                 foreach (ch; stuff[i].byDchar)
1512                     ptr = putDChar(ptr, ch);
1513             }
1514         }
1515         assert(ptr == array.ptr + pos + to_insert, "(ptr == array.ptr + pos + to_insert) is false");
1516     }
1517     else
1518     {
1519         // immutable/const, just construct a new array
1520         auto app = appender!(T[])();
1521         app.put(array[0 .. pos]);
1522         foreach (i, E; U)
1523             app.put(stuff[i]);
1524         app.put(array[pos..$]);
1525         array = app.data;
1526     }
1527 }
1528 
1529 ///
1530 @safe pure unittest
1531 {
1532     int[] a = [ 1, 2, 3, 4 ];
1533     a.insertInPlace(2, [ 1, 2 ]);
1534     assert(a == [ 1, 2, 1, 2, 3, 4 ]);
1535     a.insertInPlace(3, 10u, 11);
1536     assert(a == [ 1, 2, 1, 10, 11, 2, 3, 4]);
1537 
1538     union U
1539     {
1540         float a = 3.0;
1541         int b;
1542     }
1543 
1544     U u1 = { b : 3 };
1545     U u2 = { b : 4 };
1546     U u3 = { b : 5 };
1547     U[] unionArr = [u2, u3];
1548     unionArr.insertInPlace(2, [u1]);
1549     assert(unionArr == [u2, u3, u1]);
1550     unionArr.insertInPlace(0, [u3, u2]);
1551     assert(unionArr == [u3, u2, u2, u3, u1]);
1552 
1553     static class C
1554     {
1555         int a;
1556         float b;
1557 
1558         this(int a, float b) { this.a = a; this.b = b; }
1559     }
1560 
1561     C c1 = new C(42, 1.0);
1562     C c2 = new C(0, 0.0);
1563     C c3 = new C(int.max, float.init);
1564 
1565     C[] classArr = [c1, c2, c3];
1566     insertInPlace(classArr, 3, [c2, c3]);
1567     C[5] classArr1 = classArr;
1568     assert(classArr1 == [c1, c2, c3, c2, c3]);
1569     insertInPlace(classArr, 0, c3, c1);
1570     C[7] classArr2 = classArr;
1571     assert(classArr2 == [c3, c1, c1, c2, c3, c2, c3]);
1572 }
1573 
1574 //constraint helpers
1575 private template isInputRangeWithLengthOrConvertible(E)
1576 {
1577     template isInputRangeWithLengthOrConvertible(R)
1578     {
1579         //hasLength not defined for char[], wchar[] and dchar[]
1580         enum isInputRangeWithLengthOrConvertible =
1581             (isInputRange!R && is(typeof(R.init.length))
1582                 && is(ElementType!R : E))  || is(R : E);
1583     }
1584 }
1585 
1586 //ditto
1587 private template isCharOrStringOrDcharRange(T)
1588 {
1589     enum isCharOrStringOrDcharRange = isSomeString!T || isSomeChar!T ||
1590         (isInputRange!T && is(ElementType!T : dchar));
1591 }
1592 
1593 //ditto
1594 private template isInputRangeOrConvertible(E)
1595 {
1596     template isInputRangeOrConvertible(R)
1597     {
1598         enum isInputRangeOrConvertible =
1599             (isInputRange!R && is(ElementType!R : E))  || is(R : E);
1600     }
1601 }
1602 
1603 @system unittest
1604 {
1605     // @system due to insertInPlace
1606     import core.exception;
1607     import std.algorithm.comparison : equal;
1608     import std.algorithm.iteration : filter;
1609     import std.conv : to;
1610     import std.exception;
1611 
1612 
1613     bool test(T, U, V)(T orig, size_t pos, U toInsert, V result)
1614     {
1615         {
1616             static if (is(T == typeof(T.init.dup)))
1617                 auto a = orig.dup;
1618             else
1619                 auto a = orig.idup;
1620 
1621             a.insertInPlace(pos, toInsert);
1622             if (!equal(a, result))
1623                 return false;
1624         }
1625 
1626         static if (isInputRange!U)
1627         {
1628             orig.insertInPlace(pos, filter!"true"(toInsert));
1629             return equal(orig, result);
1630         }
1631         else
1632             return true;
1633     }
1634 
1635 
1636     assert(test([1, 2, 3, 4], 0, [6, 7], [6, 7, 1, 2, 3, 4]));
1637     assert(test([1, 2, 3, 4], 2, [8, 9], [1, 2, 8, 9, 3, 4]));
1638     assert(test([1, 2, 3, 4], 4, [10, 11], [1, 2, 3, 4, 10, 11]));
1639 
1640     assert(test([1, 2, 3, 4], 0, 22, [22, 1, 2, 3, 4]));
1641     assert(test([1, 2, 3, 4], 2, 23, [1, 2, 23, 3, 4]));
1642     assert(test([1, 2, 3, 4], 4, 24, [1, 2, 3, 4, 24]));
1643 
1644     void testStr(T, U)(string file = __FILE__, size_t line = __LINE__)
1645     {
1646 
1647         auto l = to!T("hello");
1648         auto r = to!U(" વિશ્વ");
1649 
1650         enforce(test(l, 0, r, " વિશ્વhello"),
1651                 new AssertError("testStr failure 1", file, line));
1652         enforce(test(l, 3, r, "hel વિશ્વlo"),
1653                 new AssertError("testStr failure 2", file, line));
1654         enforce(test(l, l.length, r, "hello વિશ્વ"),
1655                 new AssertError("testStr failure 3", file, line));
1656     }
1657 
1658     static foreach (T; AliasSeq!(char, wchar, dchar,
1659         immutable(char), immutable(wchar), immutable(dchar)))
1660     {
1661         static foreach (U; AliasSeq!(char, wchar, dchar,
1662             immutable(char), immutable(wchar), immutable(dchar)))
1663         {
1664             testStr!(T[], U[])();
1665         }
1666 
1667     }
1668 
1669     // variadic version
1670     bool testVar(T, U...)(T orig, size_t pos, U args)
1671     {
1672         static if (is(T == typeof(T.init.dup)))
1673             auto a = orig.dup;
1674         else
1675             auto a = orig.idup;
1676         auto result = args[$-1];
1677 
1678         a.insertInPlace(pos, args[0..$-1]);
1679         if (!equal(a, result))
1680             return false;
1681         return true;
1682     }
1683     assert(testVar([1, 2, 3, 4], 0, 6, 7u, [6, 7, 1, 2, 3, 4]));
1684     assert(testVar([1L, 2, 3, 4], 2, 8, 9L, [1, 2, 8, 9, 3, 4]));
1685     assert(testVar([1L, 2, 3, 4], 4, 10L, 11, [1, 2, 3, 4, 10, 11]));
1686     assert(testVar([1L, 2, 3, 4], 4, [10, 11], 40L, 42L,
1687                     [1, 2, 3, 4, 10, 11, 40, 42]));
1688     assert(testVar([1L, 2, 3, 4], 4, 10, 11, [40L, 42],
1689                     [1, 2, 3, 4, 10, 11, 40, 42]));
1690     assert(testVar("t".idup, 1, 'e', 's', 't', "test"));
1691     assert(testVar("!!"w.idup, 1, "\u00e9ll\u00f4", 'x', "TTT"w, 'y',
1692                     "!\u00e9ll\u00f4xTTTy!"));
1693     assert(testVar("flipflop"d.idup, 4, '_',
1694                     "xyz"w, '\U00010143', '_', "abc"d, "__",
1695                     "flip_xyz\U00010143_abc__flop"));
1696 }
1697 
1698 @system unittest
1699 {
1700     import std.algorithm.comparison : equal;
1701     // insertInPlace interop with postblit
1702     static struct Int
1703     {
1704         int* payload;
1705         this(int k)
1706         {
1707             payload = new int;
1708             *payload = k;
1709         }
1710         this(this)
1711         {
1712             int* np = new int;
1713             *np = *payload;
1714             payload = np;
1715         }
1716         ~this()
1717         {
1718             if (payload)
1719                 *payload = 0; //'destroy' it
1720         }
1721         @property int getPayload(){ return *payload; }
1722         alias getPayload this;
1723     }
1724 
1725     Int[] arr = [Int(1), Int(4), Int(5)];
1726     assert(arr[0] == 1);
1727     insertInPlace(arr, 1, Int(2), Int(3));
1728     assert(equal(arr, [1, 2, 3, 4, 5]));  //check it works with postblit
1729 }
1730 
1731 @safe unittest
1732 {
1733     import std.exception;
1734     assertCTFEable!(
1735     {
1736         int[] a = [1, 2];
1737         a.insertInPlace(2, 3);
1738         a.insertInPlace(0, -1, 0);
1739         return a == [-1, 0, 1, 2, 3];
1740     });
1741 }
1742 
1743 // https://issues.dlang.org/show_bug.cgi?id=6874
1744 @system unittest
1745 {
1746     import core.memory;
1747     // allocate some space
1748     byte[] a;
1749     a.length = 1;
1750 
1751     // fill it
1752     a.length = a.capacity;
1753 
1754     // write beyond
1755     byte[] b = a[$ .. $];
1756     b.insertInPlace(0, a);
1757 
1758     // make sure that reallocation has happened
1759     assert(GC.addrOf(&b[0]) == GC.addrOf(&b[$-1]));
1760 }
1761 
1762 
1763 /++
1764     Returns whether the `front`s of `lhs` and `rhs` both refer to the
1765     same place in memory, making one of the arrays a slice of the other which
1766     starts at index `0`.
1767 
1768     Params:
1769         lhs = the first array to compare
1770         rhs = the second array to compare
1771     Returns:
1772         `true` if $(D lhs.ptr == rhs.ptr), `false` otherwise.
1773   +/
1774 @safe
1775 pure nothrow @nogc bool sameHead(T)(in T[] lhs, in T[] rhs)
1776 {
1777     return lhs.ptr == rhs.ptr;
1778 }
1779 
1780 ///
1781 @safe pure nothrow unittest
1782 {
1783     auto a = [1, 2, 3, 4, 5];
1784     auto b = a[0 .. 2];
1785 
1786     assert(a.sameHead(b));
1787 }
1788 
1789 
1790 /++
1791     Returns whether the `back`s of `lhs` and `rhs` both refer to the
1792     same place in memory, making one of the arrays a slice of the other which
1793     end at index `$`.
1794 
1795     Params:
1796         lhs = the first array to compare
1797         rhs = the second array to compare
1798     Returns:
1799         `true` if both arrays are the same length and $(D lhs.ptr == rhs.ptr),
1800         `false` otherwise.
1801   +/
1802 @trusted
1803 pure nothrow @nogc bool sameTail(T)(in T[] lhs, in T[] rhs)
1804 {
1805     return lhs.ptr + lhs.length == rhs.ptr + rhs.length;
1806 }
1807 
1808 ///
1809 @safe pure nothrow unittest
1810 {
1811     auto a = [1, 2, 3, 4, 5];
1812     auto b = a[3..$];
1813 
1814     assert(a.sameTail(b));
1815 }
1816 
1817 @safe pure nothrow unittest
1818 {
1819     static foreach (T; AliasSeq!(int[], const(int)[], immutable(int)[], const int[], immutable int[]))
1820     {{
1821         T a = [1, 2, 3, 4, 5];
1822         T b = a;
1823         T c = a[1 .. $];
1824         T d = a[0 .. 1];
1825         T e = null;
1826 
1827         assert(sameHead(a, a));
1828         assert(sameHead(a, b));
1829         assert(!sameHead(a, c));
1830         assert(sameHead(a, d));
1831         assert(!sameHead(a, e));
1832 
1833         assert(sameTail(a, a));
1834         assert(sameTail(a, b));
1835         assert(sameTail(a, c));
1836         assert(!sameTail(a, d));
1837         assert(!sameTail(a, e));
1838 
1839         //verifies R-value compatibilty
1840         assert(a.sameHead(a[0 .. 0]));
1841         assert(a.sameTail(a[$ .. $]));
1842     }}
1843 }
1844 
1845 /**
1846 Params:
1847     s = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1848     or a dynamic array
1849     n = number of times to repeat `s`
1850 
1851 Returns:
1852     An array that consists of `s` repeated `n` times. This function allocates, fills, and
1853     returns a new array.
1854 
1855 See_Also:
1856     For a lazy version, refer to $(REF repeat, std,range).
1857  */
1858 ElementEncodingType!S[] replicate(S)(S s, size_t n)
1859 if (isDynamicArray!S)
1860 {
1861     alias RetType = ElementEncodingType!S[];
1862 
1863     // Optimization for return join(std.range.repeat(s, n));
1864     if (n == 0)
1865         return RetType.init;
1866     if (n == 1)
1867         return cast(RetType) s;
1868     auto r = new Unqual!(typeof(s[0]))[n * s.length];
1869     if (s.length == 1)
1870         r[] = s[0];
1871     else
1872     {
1873         immutable len = s.length, nlen = n * len;
1874         for (size_t i = 0; i < nlen; i += len)
1875         {
1876             r[i .. i + len] = s[];
1877         }
1878     }
1879     return r;
1880 }
1881 
1882 /// ditto
1883 ElementType!S[] replicate(S)(S s, size_t n)
1884 if (isInputRange!S && !isDynamicArray!S)
1885 {
1886     import std.range : repeat;
1887     return join(std.range.repeat(s, n));
1888 }
1889 
1890 
1891 ///
1892 @safe unittest
1893 {
1894     auto a = "abc";
1895     auto s = replicate(a, 3);
1896 
1897     assert(s == "abcabcabc");
1898 
1899     auto b = [1, 2, 3];
1900     auto c = replicate(b, 3);
1901 
1902     assert(c == [1, 2, 3, 1, 2, 3, 1, 2, 3]);
1903 
1904     auto d = replicate(b, 0);
1905 
1906     assert(d == []);
1907 }
1908 
1909 @safe unittest
1910 {
1911     import std.conv : to;
1912 
1913     static foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[]))
1914     {{
1915         immutable S t = "abc";
1916 
1917         assert(replicate(to!S("1234"), 0) is null);
1918         assert(replicate(to!S("1234"), 0) is null);
1919         assert(replicate(to!S("1234"), 1) == "1234");
1920         assert(replicate(to!S("1234"), 2) == "12341234");
1921         assert(replicate(to!S("1"), 4) == "1111");
1922         assert(replicate(t, 3) == "abcabcabc");
1923         assert(replicate(cast(S) null, 4) is null);
1924     }}
1925 }
1926 
1927 /++
1928 Eagerly splits `range` into an array, using `sep` as the delimiter.
1929 
1930 When no delimiter is provided, strings are split into an array of words,
1931 using whitespace as delimiter.
1932 Runs of whitespace are merged together (no empty words are produced).
1933 
1934 The `range` must be a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives).
1935 The separator can be a value of the same type as the elements in `range`
1936 or it can be another forward `range`.
1937 
1938 Params:
1939     s = the string to split by word if no separator is given
1940     range = the range to split
1941     sep = a value of the same type as the elements of `range` or another
1942     isTerminator = a predicate that splits the range when it returns `true`.
1943 
1944 Returns:
1945     An array containing the divided parts of `range` (or the words of `s`).
1946 
1947 See_Also:
1948 $(REF splitter, std,algorithm,iteration) for a lazy version without allocating memory.
1949 
1950 $(REF splitter, std,regex) for a version that splits using a regular
1951 expression defined separator.
1952 +/
1953 S[] split(S)(S s) @safe pure
1954 if (isSomeString!S)
1955 {
1956     size_t istart;
1957     bool inword = false;
1958     auto result = appender!(S[]);
1959 
1960     foreach (i, dchar c ; s)
1961     {
1962         import std.uni : isWhite;
1963         if (isWhite(c))
1964         {
1965             if (inword)
1966             {
1967                 put(result, s[istart .. i]);
1968                 inword = false;
1969             }
1970         }
1971         else
1972         {
1973             if (!inword)
1974             {
1975                 istart = i;
1976                 inword = true;
1977             }
1978         }
1979     }
1980     if (inword)
1981         put(result, s[istart .. $]);
1982     return result.data;
1983 }
1984 
1985 ///
1986 @safe unittest
1987 {
1988     import std.uni : isWhite;
1989     assert("Learning,D,is,fun".split(",") == ["Learning", "D", "is", "fun"]);
1990     assert("Learning D is fun".split!isWhite == ["Learning", "D", "is", "fun"]);
1991     assert("Learning D is fun".split(" D ") == ["Learning", "is fun"]);
1992 }
1993 
1994 ///
1995 @safe unittest
1996 {
1997     string str = "Hello World!";
1998     assert(str.split == ["Hello", "World!"]);
1999 
2000     string str2 = "Hello\t\tWorld\t!";
2001     assert(str2.split == ["Hello", "World", "!"]);
2002 }
2003 
2004 @safe unittest
2005 {
2006     import std.conv : to;
2007     import std.format : format;
2008     import std.typecons;
2009 
2010     static auto makeEntry(S)(string l, string[] r)
2011     {return tuple(l.to!S(), r.to!(S[])());}
2012 
2013     static foreach (S; AliasSeq!(string, wstring, dstring,))
2014     {{
2015         auto entries =
2016         [
2017             makeEntry!S("", []),
2018             makeEntry!S(" ", []),
2019             makeEntry!S("hello", ["hello"]),
2020             makeEntry!S(" hello ", ["hello"]),
2021             makeEntry!S("  h  e  l  l  o ", ["h", "e", "l", "l", "o"]),
2022             makeEntry!S("peter\t\npaul\rjerry", ["peter", "paul", "jerry"]),
2023             makeEntry!S(" \t\npeter paul\tjerry \n", ["peter", "paul", "jerry"]),
2024             makeEntry!S("\u2000日\u202F本\u205F語\u3000", ["日", "本", "語"]),
2025             makeEntry!S("  哈・郎博尔德}    ___一个", ["哈・郎博尔德}", "___一个"])
2026         ];
2027         foreach (entry; entries)
2028             assert(entry[0].split() == entry[1], format("got: %s, expected: %s.", entry[0].split(), entry[1]));
2029     }}
2030 
2031     //Just to test that an immutable is split-able
2032     immutable string s = " \t\npeter paul\tjerry \n";
2033     assert(split(s) == ["peter", "paul", "jerry"]);
2034 }
2035 
2036 @safe unittest //purity, ctfe ...
2037 {
2038     import std.exception;
2039     void dg() @safe pure {
2040         assert(split("hello world"c) == ["hello"c, "world"c]);
2041         assert(split("hello world"w) == ["hello"w, "world"w]);
2042         assert(split("hello world"d) == ["hello"d, "world"d]);
2043     }
2044     dg();
2045     assertCTFEable!dg;
2046 }
2047 
2048 ///
2049 @safe unittest
2050 {
2051     assert(split("hello world") == ["hello","world"]);
2052     assert(split("192.168.0.1", ".") == ["192", "168", "0", "1"]);
2053 
2054     auto a = split([1, 2, 3, 4, 5, 1, 2, 3, 4, 5], [2, 3]);
2055     assert(a == [[1], [4, 5, 1], [4, 5]]);
2056 }
2057 
2058 ///ditto
2059 auto split(Range, Separator)(Range range, Separator sep)
2060 if (isForwardRange!Range && (
2061     is(typeof(ElementType!Range.init == Separator.init)) ||
2062     is(typeof(ElementType!Range.init == ElementType!Separator.init)) && isForwardRange!Separator
2063     ))
2064 {
2065     import std.algorithm.iteration : splitter;
2066     return range.splitter(sep).array;
2067 }
2068 ///ditto
2069 auto split(alias isTerminator, Range)(Range range)
2070 if (isForwardRange!Range && is(typeof(unaryFun!isTerminator(range.front))))
2071 {
2072     import std.algorithm.iteration : splitter;
2073     return range.splitter!isTerminator.array;
2074 }
2075 
2076 @safe unittest
2077 {
2078     import std.algorithm.comparison : cmp;
2079     import std.conv;
2080 
2081     static foreach (S; AliasSeq!(string, wstring, dstring,
2082                     immutable(string), immutable(wstring), immutable(dstring),
2083                     char[], wchar[], dchar[],
2084                     const(char)[], const(wchar)[], const(dchar)[],
2085                     const(char[]), immutable(char[])))
2086     {{
2087         S s = to!S(",peter,paul,jerry,");
2088 
2089         auto words = split(s, ",");
2090         assert(words.length == 5, text(words.length));
2091         assert(cmp(words[0], "") == 0);
2092         assert(cmp(words[1], "peter") == 0);
2093         assert(cmp(words[2], "paul") == 0);
2094         assert(cmp(words[3], "jerry") == 0);
2095         assert(cmp(words[4], "") == 0);
2096 
2097         auto s1 = s[0 .. s.length - 1];   // lop off trailing ','
2098         words = split(s1, ",");
2099         assert(words.length == 4);
2100         assert(cmp(words[3], "jerry") == 0);
2101 
2102         auto s2 = s1[1 .. s1.length];   // lop off leading ','
2103         words = split(s2, ",");
2104         assert(words.length == 3);
2105         assert(cmp(words[0], "peter") == 0);
2106 
2107         auto s3 = to!S(",,peter,,paul,,jerry,,");
2108 
2109         words = split(s3, ",,");
2110         assert(words.length == 5);
2111         assert(cmp(words[0], "") == 0);
2112         assert(cmp(words[1], "peter") == 0);
2113         assert(cmp(words[2], "paul") == 0);
2114         assert(cmp(words[3], "jerry") == 0);
2115         assert(cmp(words[4], "") == 0);
2116 
2117         auto s4 = s3[0 .. s3.length - 2];    // lop off trailing ',,'
2118         words = split(s4, ",,");
2119         assert(words.length == 4);
2120         assert(cmp(words[3], "jerry") == 0);
2121 
2122         auto s5 = s4[2 .. s4.length];    // lop off leading ',,'
2123         words = split(s5, ",,");
2124         assert(words.length == 3);
2125         assert(cmp(words[0], "peter") == 0);
2126     }}
2127 }
2128 
2129 /+
2130    Conservative heuristic to determine if a range can be iterated cheaply.
2131    Used by `join` in decision to do an extra iteration of the range to
2132    compute the resultant length. If iteration is not cheap then precomputing
2133    length could be more expensive than using `Appender`.
2134 
2135    For now, we only assume arrays are cheap to iterate.
2136  +/
2137 private enum bool hasCheapIteration(R) = isArray!R;
2138 
2139 /++
2140    Eagerly concatenates all of the ranges in `ror` together (with the GC)
2141    into one array using `sep` as the separator if present.
2142 
2143    Params:
2144         ror = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
2145         of input ranges
2146         sep = An input range, or a single element, to join the ranges on
2147 
2148    Returns:
2149         An array of elements
2150 
2151    See_Also:
2152         For a lazy version, see $(REF joiner, std,algorithm,iteration)
2153   +/
2154 ElementEncodingType!(ElementType!RoR)[] join(RoR, R)(RoR ror, R sep)
2155 if (isInputRange!RoR &&
2156     isInputRange!(Unqual!(ElementType!RoR)) &&
2157     isInputRange!R &&
2158     (is(immutable ElementType!(ElementType!RoR) == immutable ElementType!R) ||
2159      (isSomeChar!(ElementType!(ElementType!RoR)) && isSomeChar!(ElementType!R))
2160     ))
2161 {
2162     alias RetType = typeof(return);
2163     alias RetTypeElement = Unqual!(ElementEncodingType!RetType);
2164     alias RoRElem = ElementType!RoR;
2165 
2166     if (ror.empty)
2167         return RetType.init;
2168 
2169     // Constraint only requires input range for sep.
2170     // This converts sep to an array (forward range) if it isn't one,
2171     // and makes sure it has the same string encoding for string types.
2172     static if (isSomeString!RetType &&
2173                !is(immutable ElementEncodingType!RetType == immutable ElementEncodingType!R))
2174     {
2175         import std.conv : to;
2176         auto sepArr = to!RetType(sep);
2177     }
2178     else static if (!isArray!R)
2179         auto sepArr = array(sep);
2180     else
2181         alias sepArr = sep;
2182 
2183     static if (hasCheapIteration!RoR && (hasLength!RoRElem || isNarrowString!RoRElem))
2184     {
2185         import core.internal.lifetime : emplaceRef;
2186         size_t length;          // length of result array
2187         size_t rorLength;       // length of range ror
2188         foreach (r; ror.save)
2189         {
2190             length += r.length;
2191             ++rorLength;
2192         }
2193         if (!rorLength)
2194             return null;
2195         length += (rorLength - 1) * sepArr.length;
2196 
2197         auto result = (() @trusted => uninitializedArray!(RetTypeElement[])(length))();
2198         size_t len;
2199         foreach (e; ror.front)
2200             emplaceRef(result[len++], e);
2201         ror.popFront();
2202         foreach (r; ror)
2203         {
2204             foreach (e; sepArr)
2205                 emplaceRef(result[len++], e);
2206             foreach (e; r)
2207                 emplaceRef(result[len++], e);
2208         }
2209         assert(len == result.length);
2210         return (() @trusted => cast(RetType) result)();
2211     }
2212     else
2213     {
2214         auto result = appender!RetType();
2215         put(result, ror.front);
2216         ror.popFront();
2217         for (; !ror.empty; ror.popFront())
2218         {
2219             put(result, sepArr);
2220             put(result, ror.front);
2221         }
2222         return result.data;
2223     }
2224 }
2225 
2226 // https://issues.dlang.org/show_bug.cgi?id=14230
2227 @safe unittest
2228 {
2229    string[] ary = ["","aa","bb","cc"]; // leaded by _empty_ element
2230    assert(ary.join(" @") == " @aa @bb @cc"); // OK in 2.067b1 and olders
2231 }
2232 
2233 // https://issues.dlang.org/show_bug.cgi?id=21337
2234 @system unittest
2235 {
2236     import std.algorithm.iteration : map;
2237 
2238     static class Once
2239     {
2240         bool empty;
2241 
2242         void popFront()
2243         {
2244             empty = true;
2245         }
2246 
2247         int front()
2248         {
2249             return 0;
2250         }
2251     }
2252 
2253     assert([1, 2].map!"[a]".join(new Once) == [1, 0, 2]);
2254 }
2255 
2256 /// Ditto
2257 ElementEncodingType!(ElementType!RoR)[] join(RoR, E)(RoR ror, scope E sep)
2258 if (isInputRange!RoR &&
2259     isInputRange!(Unqual!(ElementType!RoR)) &&
2260     ((is(E : ElementType!(ElementType!RoR))) ||
2261      (!autodecodeStrings && isSomeChar!(ElementType!(ElementType!RoR)) &&
2262       isSomeChar!E)))
2263 {
2264     alias RetType = typeof(return);
2265     alias RetTypeElement = Unqual!(ElementEncodingType!RetType);
2266     alias RoRElem = ElementType!RoR;
2267 
2268     if (ror.empty)
2269         return RetType.init;
2270 
2271     static if (hasCheapIteration!RoR && (hasLength!RoRElem || isNarrowString!RoRElem))
2272     {
2273         static if (isSomeChar!E && isSomeChar!RetTypeElement && E.sizeof > RetTypeElement.sizeof)
2274         {
2275             import std.utf : encode;
2276             RetTypeElement[4 / RetTypeElement.sizeof] encodeSpace;
2277             immutable size_t sepArrLength = encode(encodeSpace, sep);
2278             return join(ror, encodeSpace[0 .. sepArrLength]);
2279         }
2280         else
2281         {
2282             import core.internal.lifetime : emplaceRef;
2283             import std.format : format;
2284             size_t length;
2285             size_t rorLength;
2286             foreach (r; ror.save)
2287             {
2288                 length += r.length;
2289                 ++rorLength;
2290             }
2291             if (!rorLength)
2292                 return null;
2293             length += rorLength - 1;
2294             auto result = uninitializedArray!(RetTypeElement[])(length);
2295 
2296 
2297             size_t len;
2298             foreach (e; ror.front)
2299                 emplaceRef(result[len++], e);
2300             ror.popFront();
2301             foreach (r; ror)
2302             {
2303                 emplaceRef(result[len++], sep);
2304                 foreach (e; r)
2305                     emplaceRef(result[len++], e);
2306             }
2307             assert(len == result.length, format!
2308                     "len %s must equal result.lenght %s"(len, result.length));
2309             return (() @trusted => cast(RetType) result)();
2310         }
2311     }
2312     else
2313     {
2314         auto result = appender!RetType();
2315         put(result, ror.front);
2316         ror.popFront();
2317         for (; !ror.empty; ror.popFront())
2318         {
2319             put(result, sep);
2320             put(result, ror.front);
2321         }
2322         return result.data;
2323     }
2324 }
2325 
2326 // https://issues.dlang.org/show_bug.cgi?id=14230
2327 @safe unittest
2328 {
2329    string[] ary = ["","aa","bb","cc"];
2330    assert(ary.join('@') == "@aa@bb@cc");
2331 }
2332 
2333 /// Ditto
2334 ElementEncodingType!(ElementType!RoR)[] join(RoR)(RoR ror)
2335 if (isInputRange!RoR &&
2336     isInputRange!(Unqual!(ElementType!RoR)))
2337 {
2338     alias RetType = typeof(return);
2339     alias ConstRetTypeElement = ElementEncodingType!RetType;
2340     static if (isAssignable!(Unqual!ConstRetTypeElement, ConstRetTypeElement))
2341     {
2342         alias RetTypeElement = Unqual!ConstRetTypeElement;
2343     }
2344     else
2345     {
2346         alias RetTypeElement = ConstRetTypeElement;
2347     }
2348     alias RoRElem = ElementType!RoR;
2349 
2350     if (ror.empty)
2351         return RetType.init;
2352 
2353     static if (hasCheapIteration!RoR && (hasLength!RoRElem || isNarrowString!RoRElem))
2354     {
2355         import core.internal.lifetime : emplaceRef;
2356         size_t length;
2357         foreach (r; ror.save)
2358             length += r.length;
2359 
2360         auto result = (() @trusted => uninitializedArray!(RetTypeElement[])(length))();
2361         size_t len;
2362         foreach (r; ror)
2363             foreach (e; r)
2364                 emplaceRef!RetTypeElement(result[len++], e);
2365         assert(len == result.length,
2366                 "emplaced an unexpected number of elements");
2367         return (() @trusted => cast(RetType) result)();
2368     }
2369     else
2370     {
2371         auto result = appender!RetType();
2372         for (; !ror.empty; ror.popFront())
2373             put(result, ror.front);
2374         return result.data;
2375     }
2376 }
2377 
2378 ///
2379 @safe pure nothrow unittest
2380 {
2381     assert(join(["hello", "silly", "world"], " ") == "hello silly world");
2382     assert(join(["hello", "silly", "world"]) == "hellosillyworld");
2383 
2384     assert(join([[1, 2, 3], [4, 5]], [72, 73]) == [1, 2, 3, 72, 73, 4, 5]);
2385     assert(join([[1, 2, 3], [4, 5]]) == [1, 2, 3, 4, 5]);
2386 
2387     const string[] arr = ["apple", "banana"];
2388     assert(arr.join(",") == "apple,banana");
2389     assert(arr.join() == "applebanana");
2390 }
2391 
2392 @safe pure unittest
2393 {
2394     import std.conv : to;
2395     import std.range.primitives : autodecodeStrings;
2396 
2397     static foreach (T; AliasSeq!(string,wstring,dstring))
2398     {{
2399         auto arr2 = "Здравствуй Мир Unicode".to!(T);
2400         auto arr = ["Здравствуй", "Мир", "Unicode"].to!(T[]);
2401         assert(join(arr) == "ЗдравствуйМирUnicode");
2402         static foreach (S; AliasSeq!(char,wchar,dchar))
2403         {{
2404             auto jarr = arr.join(to!S(' '));
2405             static assert(is(typeof(jarr) == T));
2406             assert(jarr == arr2);
2407         }}
2408         static foreach (S; AliasSeq!(string,wstring,dstring))
2409         {{
2410             auto jarr = arr.join(to!S(" "));
2411             static assert(is(typeof(jarr) == T));
2412             assert(jarr == arr2);
2413         }}
2414     }}
2415 
2416     static foreach (T; AliasSeq!(string,wstring,dstring))
2417     {{
2418         auto arr2 = "Здравствуй\u047CМир\u047CUnicode".to!(T);
2419         auto arr = ["Здравствуй", "Мир", "Unicode"].to!(T[]);
2420         static foreach (S; AliasSeq!(wchar,dchar))
2421         {{
2422             auto jarr = arr.join(to!S('\u047C'));
2423             static assert(is(typeof(jarr) == T));
2424             assert(jarr == arr2);
2425         }}
2426     }}
2427 
2428     const string[] arr = ["apple", "banana"];
2429     assert(arr.join(',') == "apple,banana");
2430 }
2431 
2432 @safe unittest
2433 {
2434     class A { }
2435 
2436     const A[][] array;
2437     auto result = array.join; // can't remove constness, so don't try
2438 
2439     static assert(is(typeof(result) == const(A)[]));
2440 }
2441 
2442 @safe unittest
2443 {
2444     import std.algorithm;
2445     import std.conv : to;
2446     import std.range;
2447 
2448     static foreach (R; AliasSeq!(string, wstring, dstring))
2449     {{
2450         R word1 = "日本語";
2451         R word2 = "paul";
2452         R word3 = "jerry";
2453         R[] words = [word1, word2, word3];
2454 
2455         auto filteredWord1    = filter!"true"(word1);
2456         auto filteredLenWord1 = takeExactly(filteredWord1, word1.walkLength());
2457         auto filteredWord2    = filter!"true"(word2);
2458         auto filteredLenWord2 = takeExactly(filteredWord2, word2.walkLength());
2459         auto filteredWord3    = filter!"true"(word3);
2460         auto filteredLenWord3 = takeExactly(filteredWord3, word3.walkLength());
2461         auto filteredWordsArr = [filteredWord1, filteredWord2, filteredWord3];
2462         auto filteredLenWordsArr = [filteredLenWord1, filteredLenWord2, filteredLenWord3];
2463         auto filteredWords    = filter!"true"(filteredWordsArr);
2464 
2465         static foreach (S; AliasSeq!(string, wstring, dstring))
2466         {{
2467             assert(join(filteredWords, to!S(", ")) == "日本語, paul, jerry");
2468             assert(join(filteredWords, to!(ElementType!S)(',')) == "日本語,paul,jerry");
2469             assert(join(filteredWordsArr, to!(ElementType!(S))(',')) == "日本語,paul,jerry");
2470             assert(join(filteredWordsArr, to!S(", ")) == "日本語, paul, jerry");
2471             assert(join(filteredWordsArr, to!(ElementType!(S))(',')) == "日本語,paul,jerry");
2472             assert(join(filteredLenWordsArr, to!S(", ")) == "日本語, paul, jerry");
2473             assert(join(filter!"true"(words), to!S(", ")) == "日本語, paul, jerry");
2474             assert(join(words, to!S(", ")) == "日本語, paul, jerry");
2475 
2476             assert(join(filteredWords, to!S("")) == "日本語pauljerry");
2477             assert(join(filteredWordsArr, to!S("")) == "日本語pauljerry");
2478             assert(join(filteredLenWordsArr, to!S("")) == "日本語pauljerry");
2479             assert(join(filter!"true"(words), to!S("")) == "日本語pauljerry");
2480             assert(join(words, to!S("")) == "日本語pauljerry");
2481 
2482             assert(join(filter!"true"([word1]), to!S(", ")) == "日本語");
2483             assert(join([filteredWord1], to!S(", ")) == "日本語");
2484             assert(join([filteredLenWord1], to!S(", ")) == "日本語");
2485             assert(join(filter!"true"([filteredWord1]), to!S(", ")) == "日本語");
2486             assert(join([word1], to!S(", ")) == "日本語");
2487 
2488             assert(join(filteredWords, to!S(word1)) == "日本語日本語paul日本語jerry");
2489             assert(join(filteredWordsArr, to!S(word1)) == "日本語日本語paul日本語jerry");
2490             assert(join(filteredLenWordsArr, to!S(word1)) == "日本語日本語paul日本語jerry");
2491             assert(join(filter!"true"(words), to!S(word1)) == "日本語日本語paul日本語jerry");
2492             assert(join(words, to!S(word1)) == "日本語日本語paul日本語jerry");
2493 
2494             auto filterComma = filter!"true"(to!S(", "));
2495             assert(join(filteredWords, filterComma) == "日本語, paul, jerry");
2496             assert(join(filteredWordsArr, filterComma) == "日本語, paul, jerry");
2497             assert(join(filteredLenWordsArr, filterComma) == "日本語, paul, jerry");
2498             assert(join(filter!"true"(words), filterComma) == "日本語, paul, jerry");
2499             assert(join(words, filterComma) == "日本語, paul, jerry");
2500         }}
2501 
2502         assert(join(filteredWords) == "日本語pauljerry");
2503         assert(join(filteredWordsArr) == "日本語pauljerry");
2504         assert(join(filteredLenWordsArr) == "日本語pauljerry");
2505         assert(join(filter!"true"(words)) == "日本語pauljerry");
2506         assert(join(words) == "日本語pauljerry");
2507 
2508         assert(join(filteredWords, filter!"true"(", ")) == "日本語, paul, jerry");
2509         assert(join(filteredWordsArr, filter!"true"(", ")) == "日本語, paul, jerry");
2510         assert(join(filteredLenWordsArr, filter!"true"(", ")) == "日本語, paul, jerry");
2511         assert(join(filter!"true"(words), filter!"true"(", ")) == "日本語, paul, jerry");
2512         assert(join(words, filter!"true"(", ")) == "日本語, paul, jerry");
2513 
2514         assert(join(filter!"true"(cast(typeof(filteredWordsArr))[]), ", ").empty);
2515         assert(join(cast(typeof(filteredWordsArr))[], ", ").empty);
2516         assert(join(cast(typeof(filteredLenWordsArr))[], ", ").empty);
2517         assert(join(filter!"true"(cast(R[])[]), ", ").empty);
2518         assert(join(cast(R[])[], ", ").empty);
2519 
2520         assert(join(filter!"true"(cast(typeof(filteredWordsArr))[])).empty);
2521         assert(join(cast(typeof(filteredWordsArr))[]).empty);
2522         assert(join(cast(typeof(filteredLenWordsArr))[]).empty);
2523 
2524         assert(join(filter!"true"(cast(R[])[])).empty);
2525         assert(join(cast(R[])[]).empty);
2526     }}
2527 
2528     assert(join([[1, 2], [41, 42]], [5, 6]) == [1, 2, 5, 6, 41, 42]);
2529     assert(join([[1, 2], [41, 42]], cast(int[])[]) == [1, 2, 41, 42]);
2530     assert(join([[1, 2]], [5, 6]) == [1, 2]);
2531     assert(join(cast(int[][])[], [5, 6]).empty);
2532 
2533     assert(join([[1, 2], [41, 42]]) == [1, 2, 41, 42]);
2534     assert(join(cast(int[][])[]).empty);
2535 
2536     alias f = filter!"true";
2537     assert(join([[1, 2], [41, 42]],          [5, 6]) == [1, 2, 5, 6, 41, 42]);
2538     assert(join(f([[1, 2], [41, 42]]),       [5, 6]) == [1, 2, 5, 6, 41, 42]);
2539     assert(join([f([1, 2]), f([41, 42])],    [5, 6]) == [1, 2, 5, 6, 41, 42]);
2540     assert(join(f([f([1, 2]), f([41, 42])]), [5, 6]) == [1, 2, 5, 6, 41, 42]);
2541     assert(join([[1, 2], [41, 42]],          f([5, 6])) == [1, 2, 5, 6, 41, 42]);
2542     assert(join(f([[1, 2], [41, 42]]),       f([5, 6])) == [1, 2, 5, 6, 41, 42]);
2543     assert(join([f([1, 2]), f([41, 42])],    f([5, 6])) == [1, 2, 5, 6, 41, 42]);
2544     assert(join(f([f([1, 2]), f([41, 42])]), f([5, 6])) == [1, 2, 5, 6, 41, 42]);
2545 }
2546 
2547 // https://issues.dlang.org/show_bug.cgi?id=10683
2548 @safe unittest
2549 {
2550     import std.range : join;
2551     import std.typecons : tuple;
2552     assert([[tuple(1)]].join == [tuple(1)]);
2553     assert([[tuple("x")]].join == [tuple("x")]);
2554 }
2555 
2556 // https://issues.dlang.org/show_bug.cgi?id=13877
2557 @safe unittest
2558 {
2559     // Test that the range is iterated only once.
2560     import std.algorithm.iteration : map;
2561     int c = 0;
2562     auto j1 = [1, 2, 3].map!(_ => [c++]).join;
2563     assert(c == 3);
2564     assert(j1 == [0, 1, 2]);
2565 
2566     c = 0;
2567     auto j2 = [1, 2, 3].map!(_ => [c++]).join(9);
2568     assert(c == 3);
2569     assert(j2 == [0, 9, 1, 9, 2]);
2570 
2571     c = 0;
2572     auto j3 = [1, 2, 3].map!(_ => [c++]).join([9]);
2573     assert(c == 3);
2574     assert(j3 == [0, 9, 1, 9, 2]);
2575 }
2576 
2577 
2578 /++
2579     Replace occurrences of `from` with `to` in `subject` in a new array.
2580 
2581     Params:
2582         subject = the array to scan
2583         from = the item to replace
2584         to = the item to replace all instances of `from` with
2585 
2586     Returns:
2587         A new array without changing the contents of `subject`, or the original
2588         array if no match is found.
2589 
2590     See_Also:
2591         $(REF substitute, std,algorithm,iteration) for a lazy replace.
2592  +/
2593 E[] replace(E, R1, R2)(E[] subject, R1 from, R2 to)
2594 if ((isForwardRange!R1 && isForwardRange!R2 && (hasLength!R2 || isSomeString!R2)) ||
2595     is(Unqual!E : Unqual!R1))
2596 {
2597     size_t changed = 0;
2598     return replace(subject, from, to, changed);
2599 }
2600 
2601 ///
2602 @safe unittest
2603 {
2604     assert("Hello Wörld".replace("o Wö", "o Wo") == "Hello World");
2605     assert("Hello Wörld".replace("l", "h") == "Hehho Wörhd");
2606 }
2607 
2608 @safe unittest
2609 {
2610     assert([1, 2, 3, 4, 2].replace([2], [5]) == [1, 5, 3, 4, 5]);
2611     assert([3, 3, 3].replace([3], [0]) == [0, 0, 0]);
2612     assert([3, 3, 4, 3].replace([3, 3], [1, 1, 1]) == [1, 1, 1, 4, 3]);
2613 }
2614 
2615 // https://issues.dlang.org/show_bug.cgi?id=18215
2616 @safe unittest
2617 {
2618     auto arr = ["aaa.dd", "b"];
2619     arr = arr.replace("aaa.dd", ".");
2620     assert(arr == [".", "b"]);
2621 
2622     arr = ["_", "_", "aaa.dd", "b", "c", "aaa.dd", "e"];
2623     arr = arr.replace("aaa.dd", ".");
2624     assert(arr == ["_", "_", ".", "b", "c", ".", "e"]);
2625 }
2626 
2627 // https://issues.dlang.org/show_bug.cgi?id=18215
2628 @safe unittest
2629 {
2630     assert([[0], [1, 2], [0], [3]].replace([0], [4]) == [[4], [1, 2], [4], [3]]);
2631     assert([[0], [1, 2], [0], [3], [1, 2]]
2632             .replace([1, 2], [0]) == [[0], [0], [0], [3], [0]]);
2633     assert([[0], [1, 2], [0], [3], [1, 2], [0], [1, 2]]
2634             .replace([[0], [1, 2]], [[4]]) == [[4], [0], [3], [1, 2], [4]]);
2635 }
2636 
2637 // https://issues.dlang.org/show_bug.cgi?id=10930
2638 @safe unittest
2639 {
2640     assert([0, 1, 2].replace(1, 4) == [0, 4, 2]);
2641     assert("äbö".replace('ä', 'a') == "abö");
2642 }
2643 
2644 // empty array
2645 @safe unittest
2646 {
2647     int[] arr;
2648     assert(replace(arr, 1, 2) == []);
2649 }
2650 
2651 /++
2652     Replace occurrences of `from` with `to` in `subject` in a new array.
2653     `changed` counts how many replacements took place.
2654 
2655     Params:
2656         subject = the array to scan
2657         from = the item to replace
2658         to = the item to replace all instances of `from` with
2659         changed = the number of replacements
2660 
2661     Returns:
2662         A new array without changing the contents of `subject`, or the original
2663         array if no match is found.
2664  +/
2665 E[] replace(E, R1, R2)(E[] subject, R1 from, R2 to, ref size_t changed)
2666 if ((isForwardRange!R1 && isForwardRange!R2 && (hasLength!R2 || isSomeString!R2)) ||
2667     is(Unqual!E : Unqual!R1))
2668 {
2669     import std.algorithm.searching : find;
2670     import std.range : dropOne;
2671 
2672     static if (isInputRange!R1)
2673     {
2674         if (from.empty) return subject;
2675         alias rSave = a => a.save;
2676     }
2677     else
2678     {
2679         alias rSave = a => a;
2680     }
2681 
2682     auto balance = find(subject, rSave(from));
2683     if (balance.empty)
2684         return subject;
2685 
2686     auto app = appender!(E[])();
2687     app.put(subject[0 .. subject.length - balance.length]);
2688     app.put(rSave(to));
2689     ++changed;
2690     // replacing an element in an array is different to a range replacement
2691     static if (is(Unqual!E : Unqual!R1))
2692         replaceInto(app, balance.dropOne, from, to, changed);
2693     else
2694         replaceInto(app, balance[from.length .. $], from, to, changed);
2695 
2696     return app.data;
2697 }
2698 
2699 ///
2700 @safe unittest
2701 {
2702     size_t changed = 0;
2703     assert("Hello Wörld".replace("o Wö", "o Wo", changed) == "Hello World");
2704     assert(changed == 1);
2705 
2706     changed = 0;
2707     assert("Hello Wörld".replace("l", "h", changed) == "Hehho Wörhd");
2708     import std.stdio : writeln;
2709     writeln(changed);
2710     assert(changed == 3);
2711 }
2712 
2713 /++
2714     Replace occurrences of `from` with `to` in `subject` and output the result into
2715     `sink`.
2716 
2717     Params:
2718         sink = an $(REF_ALTTEXT output range, isOutputRange, std,range,primitives)
2719         subject = the array to scan
2720         from = the item to replace
2721         to = the item to replace all instances of `from` with
2722 
2723     See_Also:
2724         $(REF substitute, std,algorithm,iteration) for a lazy replace.
2725  +/
2726 void replaceInto(E, Sink, R1, R2)(Sink sink, E[] subject, R1 from, R2 to)
2727 if (isOutputRange!(Sink, E) &&
2728     ((isForwardRange!R1 && isForwardRange!R2 && (hasLength!R2 || isSomeString!R2)) ||
2729     is(Unqual!E : Unqual!R1)))
2730 {
2731     size_t changed = 0;
2732     replaceInto(sink, subject, from, to, changed);
2733 }
2734 
2735 ///
2736 @safe unittest
2737 {
2738     auto arr = [1, 2, 3, 4, 5];
2739     auto from = [2, 3];
2740     auto to = [4, 6];
2741     auto sink = appender!(int[])();
2742 
2743     replaceInto(sink, arr, from, to);
2744 
2745     assert(sink.data == [1, 4, 6, 4, 5]);
2746 }
2747 
2748 // empty array
2749 @safe unittest
2750 {
2751     auto sink = appender!(int[])();
2752     int[] arr;
2753     replaceInto(sink, arr, 1, 2);
2754     assert(sink.data == []);
2755 }
2756 
2757 @safe unittest
2758 {
2759     import std.algorithm.comparison : cmp;
2760     import std.conv : to;
2761 
2762     static foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[]))
2763     {
2764         static foreach (T; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[]))
2765         {{
2766             auto s = to!S("This is a foo foo list");
2767             auto from = to!T("foo");
2768             auto into = to!S("silly");
2769             S r;
2770             int i;
2771 
2772             r = replace(s, from, into);
2773             i = cmp(r, "This is a silly silly list");
2774             assert(i == 0);
2775 
2776             r = replace(s, to!S(""), into);
2777             i = cmp(r, "This is a foo foo list");
2778             assert(i == 0);
2779 
2780             assert(replace(r, to!S("won't find this"), to!S("whatever")) is r);
2781         }}
2782     }
2783 
2784     immutable s = "This is a foo foo list";
2785     assert(replace(s, "foo", "silly") == "This is a silly silly list");
2786 }
2787 
2788 @safe unittest
2789 {
2790     import std.algorithm.searching : skipOver;
2791     import std.conv : to;
2792 
2793     struct CheckOutput(C)
2794     {
2795         C[] desired;
2796         this(C[] arr){ desired = arr; }
2797         void put(C[] part){ assert(skipOver(desired, part)); }
2798     }
2799     static foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[]))
2800     {{
2801         alias Char = ElementEncodingType!S;
2802         S s = to!S("yet another dummy text, yet another ...");
2803         S from = to!S("yet another");
2804         S into = to!S("some");
2805         replaceInto(CheckOutput!(Char)(to!S("some dummy text, some ..."))
2806                     , s, from, into);
2807     }}
2808 }
2809 
2810 // https://issues.dlang.org/show_bug.cgi?id=10930
2811 @safe unittest
2812 {
2813     auto sink = appender!(int[])();
2814     replaceInto(sink, [0, 1, 2], 1, 5);
2815     assert(sink.data == [0, 5, 2]);
2816 
2817     auto sink2 = appender!(dchar[])();
2818     replaceInto(sink2, "äbö", 'ä', 'a');
2819     assert(sink2.data == "abö");
2820 }
2821 
2822 /++
2823     Replace occurrences of `from` with `to` in `subject` and output the result into
2824     `sink`. `changed` counts how many replacements took place.
2825 
2826     Params:
2827         sink = an $(REF_ALTTEXT output range, isOutputRange, std,range,primitives)
2828         subject = the array to scan
2829         from = the item to replace
2830         to = the item to replace all instances of `from` with
2831         changed = the number of replacements
2832  +/
2833 void replaceInto(E, Sink, R1, R2)(Sink sink, E[] subject, R1 from, R2 to, ref size_t changed)
2834 if (isOutputRange!(Sink, E) &&
2835     ((isForwardRange!R1 && isForwardRange!R2 && (hasLength!R2 || isSomeString!R2)) ||
2836     is(Unqual!E : Unqual!R1)))
2837 {
2838     import std.algorithm.searching : find;
2839     import std.range : dropOne;
2840 
2841     static if (isInputRange!R1)
2842     {
2843         if (from.empty)
2844         {
2845             sink.put(subject);
2846             return;
2847         }
2848         alias rSave = a => a.save;
2849     }
2850     else
2851     {
2852         alias rSave = a => a;
2853     }
2854     for (;;)
2855     {
2856         auto balance = find(subject, rSave(from));
2857         if (balance.empty)
2858         {
2859             sink.put(subject);
2860             break;
2861         }
2862         sink.put(subject[0 .. subject.length - balance.length]);
2863         sink.put(rSave(to));
2864         ++changed;
2865         // replacing an element in an array is different to a range replacement
2866         static if (is(Unqual!E : Unqual!R1))
2867             subject = balance.dropOne;
2868         else
2869             subject = balance[from.length .. $];
2870     }
2871 }
2872 
2873 ///
2874 @safe unittest
2875 {
2876     auto arr = [1, 2, 3, 4, 5];
2877     auto from = [2, 3];
2878     auto to = [4, 6];
2879     auto sink = appender!(int[])();
2880 
2881     size_t changed = 0;
2882     replaceInto(sink, arr, from, to, changed);
2883 
2884     assert(sink.data == [1, 4, 6, 4, 5]);
2885     assert(changed == 1);
2886 }
2887 
2888 /++
2889     Replaces elements from `array` with indices ranging from `from`
2890     (inclusive) to `to` (exclusive) with the range `stuff`.
2891 
2892     Params:
2893         subject = the array to scan
2894         from = the starting index
2895         to = the ending index
2896         stuff = the items to replace in-between `from` and `to`
2897 
2898     Returns:
2899         A new array without changing the contents of `subject`.
2900 
2901     See_Also:
2902         $(REF substitute, std,algorithm,iteration) for a lazy replace.
2903  +/
2904 T[] replace(T, Range)(T[] subject, size_t from, size_t to, Range stuff)
2905 if (isInputRange!Range &&
2906     (is(ElementType!Range : T) ||
2907     isSomeString!(T[]) && is(ElementType!Range : dchar)))
2908 {
2909     static if (hasLength!Range && is(ElementEncodingType!Range : T))
2910     {
2911         import std.algorithm.mutation : copy;
2912         assert(from <= to, "from must be before or equal to to");
2913         immutable sliceLen = to - from;
2914         auto retval = new Unqual!(T)[](subject.length - sliceLen + stuff.length);
2915         retval[0 .. from] = subject[0 .. from];
2916 
2917         if (!stuff.empty)
2918             copy(stuff, retval[from .. from + stuff.length]);
2919 
2920         retval[from + stuff.length .. $] = subject[to .. $];
2921         static if (is(T == const) || is(T == immutable))
2922         {
2923             return () @trusted { return cast(T[]) retval; } ();
2924         }
2925         else
2926         {
2927             return cast(T[]) retval;
2928         }
2929     }
2930     else
2931     {
2932         auto app = appender!(T[])();
2933         app.put(subject[0 .. from]);
2934         app.put(stuff);
2935         app.put(subject[to .. $]);
2936         return app.data;
2937     }
2938 }
2939 
2940 ///
2941 @safe unittest
2942 {
2943     auto a = [ 1, 2, 3, 4 ];
2944     auto b = a.replace(1, 3, [ 9, 9, 9 ]);
2945     assert(a == [ 1, 2, 3, 4 ]);
2946     assert(b == [ 1, 9, 9, 9, 4 ]);
2947 }
2948 
2949 @system unittest
2950 {
2951     import core.exception;
2952     import std.algorithm.iteration : filter;
2953     import std.conv : to;
2954     import std.exception;
2955 
2956 
2957     auto a = [ 1, 2, 3, 4 ];
2958     assert(replace(a, 0, 0, [5, 6, 7]) == [5, 6, 7, 1, 2, 3, 4]);
2959     assert(replace(a, 0, 2, cast(int[])[]) == [3, 4]);
2960     assert(replace(a, 0, 4, [5, 6, 7]) == [5, 6, 7]);
2961     assert(replace(a, 0, 2, [5, 6, 7]) == [5, 6, 7, 3, 4]);
2962     assert(replace(a, 2, 4, [5, 6, 7]) == [1, 2, 5, 6, 7]);
2963 
2964     assert(replace(a, 0, 0, filter!"true"([5, 6, 7])) == [5, 6, 7, 1, 2, 3, 4]);
2965     assert(replace(a, 0, 2, filter!"true"(cast(int[])[])) == [3, 4]);
2966     assert(replace(a, 0, 4, filter!"true"([5, 6, 7])) == [5, 6, 7]);
2967     assert(replace(a, 0, 2, filter!"true"([5, 6, 7])) == [5, 6, 7, 3, 4]);
2968     assert(replace(a, 2, 4, filter!"true"([5, 6, 7])) == [1, 2, 5, 6, 7]);
2969     assert(a == [ 1, 2, 3, 4 ]);
2970 
2971     void testStr(T, U)(string file = __FILE__, size_t line = __LINE__)
2972     {
2973 
2974         auto l = to!T("hello");
2975         auto r = to!U(" world");
2976 
2977         enforce(replace(l, 0, 0, r) == " worldhello",
2978                 new AssertError("testStr failure 1", file, line));
2979         enforce(replace(l, 0, 3, r) == " worldlo",
2980                 new AssertError("testStr failure 2", file, line));
2981         enforce(replace(l, 3, l.length, r) == "hel world",
2982                 new AssertError("testStr failure 3", file, line));
2983         enforce(replace(l, 0, l.length, r) == " world",
2984                 new AssertError("testStr failure 4", file, line));
2985         enforce(replace(l, l.length, l.length, r) == "hello world",
2986                 new AssertError("testStr failure 5", file, line));
2987     }
2988 
2989     testStr!(string, string)();
2990     testStr!(string, wstring)();
2991     testStr!(string, dstring)();
2992     testStr!(wstring, string)();
2993     testStr!(wstring, wstring)();
2994     testStr!(wstring, dstring)();
2995     testStr!(dstring, string)();
2996     testStr!(dstring, wstring)();
2997     testStr!(dstring, dstring)();
2998 
2999     enum s = "0123456789";
3000     enum w = "⁰¹²³⁴⁵⁶⁷⁸⁹"w;
3001     enum d = "⁰¹²³⁴⁵⁶⁷⁸⁹"d;
3002 
3003     assert(replace(s, 0, 0, "***") == "***0123456789");
3004     assert(replace(s, 10, 10, "***") == "0123456789***");
3005     assert(replace(s, 3, 8, "1012") == "012101289");
3006     assert(replace(s, 0, 5, "43210") == "4321056789");
3007     assert(replace(s, 5, 10, "43210") == "0123443210");
3008 
3009     assert(replace(w, 0, 0, "***"w) == "***⁰¹²³⁴⁵⁶⁷⁸⁹"w);
3010     assert(replace(w, 10, 10, "***"w) == "⁰¹²³⁴⁵⁶⁷⁸⁹***"w);
3011     assert(replace(w, 3, 8, "¹⁰¹²"w) == "⁰¹²¹⁰¹²⁸⁹"w);
3012     assert(replace(w, 0, 5, "⁴³²¹⁰"w) == "⁴³²¹⁰⁵⁶⁷⁸⁹"w);
3013     assert(replace(w, 5, 10, "⁴³²¹⁰"w) == "⁰¹²³⁴⁴³²¹⁰"w);
3014 
3015     assert(replace(d, 0, 0, "***"d) == "***⁰¹²³⁴⁵⁶⁷⁸⁹"d);
3016     assert(replace(d, 10, 10, "***"d) == "⁰¹²³⁴⁵⁶⁷⁸⁹***"d);
3017     assert(replace(d, 3, 8, "¹⁰¹²"d) == "⁰¹²¹⁰¹²⁸⁹"d);
3018     assert(replace(d, 0, 5, "⁴³²¹⁰"d) == "⁴³²¹⁰⁵⁶⁷⁸⁹"d);
3019     assert(replace(d, 5, 10, "⁴³²¹⁰"d) == "⁰¹²³⁴⁴³²¹⁰"d);
3020 }
3021 
3022 // https://issues.dlang.org/show_bug.cgi?id=18166
3023 @safe pure unittest
3024 {
3025     auto str = replace("aaaaa"d, 1, 4, "***"d);
3026     assert(str == "a***a");
3027 }
3028 
3029 /++
3030     Replaces elements from `array` with indices ranging from `from`
3031     (inclusive) to `to` (exclusive) with the range `stuff`. Expands or
3032     shrinks the array as needed.
3033 
3034     Params:
3035         array = the array to scan
3036         from = the starting index
3037         to = the ending index
3038         stuff = the items to replace in-between `from` and `to`
3039  +/
3040 void replaceInPlace(T, Range)(ref T[] array, size_t from, size_t to, Range stuff)
3041 if (is(typeof(replace(array, from, to, stuff))))
3042 {
3043     static if (isDynamicArray!Range &&
3044               is(Unqual!(ElementEncodingType!Range) == T) &&
3045               !isNarrowString!(T[]))
3046     {
3047         // optimized for homogeneous arrays that can be overwritten.
3048         import std.algorithm.mutation : remove;
3049         import std.typecons : tuple;
3050 
3051         if (overlap(array, stuff).length)
3052         {
3053             // use slower/conservative method
3054             array = array[0 .. from] ~ stuff ~ array[to .. $];
3055         }
3056         else if (stuff.length <= to - from)
3057         {
3058             // replacement reduces length
3059             immutable stuffEnd = from + stuff.length;
3060             array[from .. stuffEnd] = stuff[];
3061             if (stuffEnd < to)
3062                 array = remove(array, tuple(stuffEnd, to));
3063         }
3064         else
3065         {
3066             // replacement increases length
3067             // @@@TODO@@@: optimize this
3068             immutable replaceLen = to - from;
3069             array[from .. to] = stuff[0 .. replaceLen];
3070             insertInPlace(array, to, stuff[replaceLen .. $]);
3071         }
3072     }
3073     else
3074     {
3075         // default implementation, just do what replace does.
3076         array = replace(array, from, to, stuff);
3077     }
3078 }
3079 
3080 ///
3081 @safe unittest
3082 {
3083     int[] a = [1, 4, 5];
3084     replaceInPlace(a, 1u, 2u, [2, 3, 4]);
3085     assert(a == [1, 2, 3, 4, 5]);
3086     replaceInPlace(a, 1u, 2u, cast(int[])[]);
3087     assert(a == [1, 3, 4, 5]);
3088     replaceInPlace(a, 1u, 3u, a[2 .. 4]);
3089     assert(a == [1, 4, 5, 5]);
3090 }
3091 
3092 // https://issues.dlang.org/show_bug.cgi?id=12889
3093 @safe unittest
3094 {
3095     int[1][] arr = [[0], [1], [2], [3], [4], [5], [6]];
3096     int[1][] stuff = [[0], [1]];
3097     replaceInPlace(arr, 4, 6, stuff);
3098     assert(arr == [[0], [1], [2], [3], [0], [1], [6]]);
3099 }
3100 
3101 @system unittest
3102 {
3103     // https://issues.dlang.org/show_bug.cgi?id=14925
3104     char[] a = "mon texte 1".dup;
3105     char[] b = "abc".dup;
3106     replaceInPlace(a, 4, 9, b);
3107     assert(a == "mon abc 1");
3108 
3109     // ensure we can replace in place with different encodings
3110     string unicoded = "\U00010437";
3111     string unicodedLong = "\U00010437aaaaa";
3112     string base = "abcXXXxyz";
3113     string result = "abc\U00010437xyz";
3114     string resultLong = "abc\U00010437aaaaaxyz";
3115     size_t repstart = 3;
3116     size_t repend = 3 + 3;
3117 
3118     void testStringReplaceInPlace(T, U)()
3119     {
3120         import std.algorithm.comparison : equal;
3121         import std.conv;
3122         auto a = unicoded.to!(U[]);
3123         auto b = unicodedLong.to!(U[]);
3124 
3125         auto test = base.to!(T[]);
3126 
3127         test.replaceInPlace(repstart, repend, a);
3128         assert(equal(test, result), "Failed for types " ~ T.stringof ~ " and " ~ U.stringof);
3129 
3130         test = base.to!(T[]);
3131 
3132         test.replaceInPlace(repstart, repend, b);
3133         assert(equal(test, resultLong), "Failed for types " ~ T.stringof ~ " and " ~ U.stringof);
3134     }
3135 
3136     import std.meta : AliasSeq;
3137     alias allChars = AliasSeq!(char, immutable(char), const(char),
3138                          wchar, immutable(wchar), const(wchar),
3139                          dchar, immutable(dchar), const(dchar));
3140     foreach (T; allChars)
3141         foreach (U; allChars)
3142             testStringReplaceInPlace!(T, U)();
3143 
3144     void testInout(inout(int)[] a)
3145     {
3146         // will be transferred to the 'replace' function
3147         replaceInPlace(a, 1, 2, [1,2,3]);
3148     }
3149 }
3150 
3151 @safe unittest
3152 {
3153     // the constraint for the first overload used to match this, which wouldn't compile.
3154     import std.algorithm.comparison : equal;
3155     long[] a = [1L, 2, 3];
3156     int[] b = [4, 5, 6];
3157     a.replaceInPlace(1, 2, b);
3158     assert(equal(a, [1L, 4, 5, 6, 3]));
3159 }
3160 
3161 @system unittest
3162 {
3163     import core.exception;
3164     import std.algorithm.comparison : equal;
3165     import std.algorithm.iteration : filter;
3166     import std.conv : to;
3167     import std.exception;
3168 
3169 
3170     bool test(T, U, V)(T orig, size_t from, size_t to, U toReplace, V result)
3171     {
3172         {
3173             static if (is(T == typeof(T.init.dup)))
3174                 auto a = orig.dup;
3175             else
3176                 auto a = orig.idup;
3177 
3178             a.replaceInPlace(from, to, toReplace);
3179             if (!equal(a, result))
3180                 return false;
3181         }
3182 
3183         static if (isInputRange!U)
3184         {
3185             orig.replaceInPlace(from, to, filter!"true"(toReplace));
3186             return equal(orig, result);
3187         }
3188         else
3189             return true;
3190     }
3191 
3192     assert(test([1, 2, 3, 4], 0, 0, [5, 6, 7], [5, 6, 7, 1, 2, 3, 4]));
3193     assert(test([1, 2, 3, 4], 0, 2, cast(int[])[], [3, 4]));
3194     assert(test([1, 2, 3, 4], 0, 4, [5, 6, 7], [5, 6, 7]));
3195     assert(test([1, 2, 3, 4], 0, 2, [5, 6, 7], [5, 6, 7, 3, 4]));
3196     assert(test([1, 2, 3, 4], 2, 4, [5, 6, 7], [1, 2, 5, 6, 7]));
3197 
3198     assert(test([1, 2, 3, 4], 0, 0, filter!"true"([5, 6, 7]), [5, 6, 7, 1, 2, 3, 4]));
3199     assert(test([1, 2, 3, 4], 0, 2, filter!"true"(cast(int[])[]), [3, 4]));
3200     assert(test([1, 2, 3, 4], 0, 4, filter!"true"([5, 6, 7]), [5, 6, 7]));
3201     assert(test([1, 2, 3, 4], 0, 2, filter!"true"([5, 6, 7]), [5, 6, 7, 3, 4]));
3202     assert(test([1, 2, 3, 4], 2, 4, filter!"true"([5, 6, 7]), [1, 2, 5, 6, 7]));
3203 
3204     void testStr(T, U)(string file = __FILE__, size_t line = __LINE__)
3205     {
3206 
3207         auto l = to!T("hello");
3208         auto r = to!U(" world");
3209 
3210         enforce(test(l, 0, 0, r, " worldhello"),
3211                 new AssertError("testStr failure 1", file, line));
3212         enforce(test(l, 0, 3, r, " worldlo"),
3213                 new AssertError("testStr failure 2", file, line));
3214         enforce(test(l, 3, l.length, r, "hel world"),
3215                 new AssertError("testStr failure 3", file, line));
3216         enforce(test(l, 0, l.length, r, " world"),
3217                 new AssertError("testStr failure 4", file, line));
3218         enforce(test(l, l.length, l.length, r, "hello world"),
3219                 new AssertError("testStr failure 5", file, line));
3220     }
3221 
3222     testStr!(string, string)();
3223     testStr!(string, wstring)();
3224     testStr!(string, dstring)();
3225     testStr!(wstring, string)();
3226     testStr!(wstring, wstring)();
3227     testStr!(wstring, dstring)();
3228     testStr!(dstring, string)();
3229     testStr!(dstring, wstring)();
3230     testStr!(dstring, dstring)();
3231 }
3232 
3233 /++
3234     Replaces the first occurrence of `from` with `to` in `subject`.
3235 
3236     Params:
3237         subject = the array to scan
3238         from = the item to replace
3239         to = the item to replace `from` with
3240 
3241     Returns:
3242         A new array without changing the contents of `subject`, or the original
3243         array if no match is found.
3244  +/
3245 E[] replaceFirst(E, R1, R2)(E[] subject, R1 from, R2 to)
3246 if (isDynamicArray!(E[]) &&
3247     isForwardRange!R1 && is(typeof(appender!(E[])().put(from[0 .. 1]))) &&
3248     isForwardRange!R2 && is(typeof(appender!(E[])().put(to[0 .. 1]))))
3249 {
3250     if (from.empty) return subject;
3251     static if (isSomeString!(E[]))
3252     {
3253         import std.string : indexOf;
3254         immutable idx = subject.indexOf(from);
3255     }
3256     else
3257     {
3258         import std.algorithm.searching : countUntil;
3259         immutable idx = subject.countUntil(from);
3260     }
3261     if (idx == -1)
3262         return subject;
3263 
3264     auto app = appender!(E[])();
3265     app.put(subject[0 .. idx]);
3266     app.put(to);
3267 
3268     static if (isSomeString!(E[]) && isSomeString!R1)
3269     {
3270         import std.utf : codeLength;
3271         immutable fromLength = codeLength!(Unqual!E, R1)(from);
3272     }
3273     else
3274         immutable fromLength = from.length;
3275 
3276     app.put(subject[idx + fromLength .. $]);
3277 
3278     return app.data;
3279 }
3280 
3281 ///
3282 @safe unittest
3283 {
3284     auto a = [1, 2, 2, 3, 4, 5];
3285     auto b = a.replaceFirst([2], [1337]);
3286     assert(b == [1, 1337, 2, 3, 4, 5]);
3287 
3288     auto s = "This is a foo foo list";
3289     auto r = s.replaceFirst("foo", "silly");
3290     assert(r == "This is a silly foo list");
3291 }
3292 
3293 @safe unittest
3294 {
3295     import std.algorithm.comparison : cmp;
3296     import std.conv : to;
3297 
3298     static foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[],
3299                           const(char[]), immutable(char[])))
3300     {
3301         static foreach (T; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[],
3302                               const(char[]), immutable(char[])))
3303         {{
3304             auto s = to!S("This is a foo foo list");
3305             auto s2 = to!S("Thüs is a ßöö foo list");
3306             auto from = to!T("foo");
3307             auto from2 = to!T("ßöö");
3308             auto into = to!T("silly");
3309             auto into2 = to!T("sälly");
3310 
3311             S r1 = replaceFirst(s, from, into);
3312             assert(cmp(r1, "This is a silly foo list") == 0);
3313 
3314             S r11 = replaceFirst(s2, from2, into2);
3315             assert(cmp(r11, "Thüs is a sälly foo list") == 0,
3316                 to!string(r11) ~ " : " ~ S.stringof ~ " " ~ T.stringof);
3317 
3318             S r2 = replaceFirst(r1, from, into);
3319             assert(cmp(r2, "This is a silly silly list") == 0);
3320 
3321             S r3 = replaceFirst(s, to!T(""), into);
3322             assert(cmp(r3, "This is a foo foo list") == 0);
3323 
3324             assert(replaceFirst(r3, to!T("won't find"), to!T("whatever")) is r3);
3325         }}
3326     }
3327 }
3328 
3329 // https://issues.dlang.org/show_bug.cgi?id=8187
3330 @safe unittest
3331 {
3332     auto res = ["a", "a"];
3333     assert(replace(res, "a", "b") == ["b", "b"]);
3334     assert(replaceFirst(res, "a", "b") == ["b", "a"]);
3335 }
3336 
3337 /++
3338     Replaces the last occurrence of `from` with `to` in `subject`.
3339 
3340     Params:
3341         subject = the array to scan
3342         from = the item to replace
3343         to = the item to replace `from` with
3344 
3345     Returns:
3346         A new array without changing the contents of `subject`, or the original
3347         array if no match is found.
3348  +/
3349 E[] replaceLast(E, R1, R2)(E[] subject, R1 from , R2 to)
3350 if (isDynamicArray!(E[]) &&
3351     isForwardRange!R1 && is(typeof(appender!(E[])().put(from[0 .. 1]))) &&
3352     isForwardRange!R2 && is(typeof(appender!(E[])().put(to[0 .. 1]))))
3353 {
3354     import std.range : retro;
3355     if (from.empty) return subject;
3356     static if (isSomeString!(E[]))
3357     {
3358         import std.string : lastIndexOf;
3359         auto idx = subject.lastIndexOf(from);
3360     }
3361     else
3362     {
3363         import std.algorithm.searching : countUntil;
3364         auto idx = retro(subject).countUntil(retro(from));
3365     }
3366 
3367     if (idx == -1)
3368         return subject;
3369 
3370     static if (isSomeString!(E[]) && isSomeString!R1)
3371     {
3372         import std.utf : codeLength;
3373         auto fromLength = codeLength!(Unqual!E, R1)(from);
3374     }
3375     else
3376         auto fromLength = from.length;
3377 
3378     auto app = appender!(E[])();
3379     static if (isSomeString!(E[]))
3380         app.put(subject[0 .. idx]);
3381     else
3382         app.put(subject[0 .. $ - idx - fromLength]);
3383 
3384     app.put(to);
3385 
3386     static if (isSomeString!(E[]))
3387         app.put(subject[idx+fromLength .. $]);
3388     else
3389         app.put(subject[$ - idx .. $]);
3390 
3391     return app.data;
3392 }
3393 
3394 ///
3395 @safe unittest
3396 {
3397     auto a = [1, 2, 2, 3, 4, 5];
3398     auto b = a.replaceLast([2], [1337]);
3399     assert(b == [1, 2, 1337, 3, 4, 5]);
3400 
3401     auto s = "This is a foo foo list";
3402     auto r = s.replaceLast("foo", "silly");
3403     assert(r == "This is a foo silly list", r);
3404 }
3405 
3406 @safe unittest
3407 {
3408     import std.algorithm.comparison : cmp;
3409     import std.conv : to;
3410 
3411     static foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[],
3412                           const(char[]), immutable(char[])))
3413     {
3414         static foreach (T; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[],
3415                               const(char[]), immutable(char[])))
3416         {{
3417             auto s = to!S("This is a foo foo list");
3418             auto s2 = to!S("Thüs is a ßöö ßöö list");
3419             auto from = to!T("foo");
3420             auto from2 = to!T("ßöö");
3421             auto into = to!T("silly");
3422             auto into2 = to!T("sälly");
3423 
3424             S r1 = replaceLast(s, from, into);
3425             assert(cmp(r1, "This is a foo silly list") == 0, to!string(r1));
3426 
3427             S r11 = replaceLast(s2, from2, into2);
3428             assert(cmp(r11, "Thüs is a ßöö sälly list") == 0,
3429                 to!string(r11) ~ " : " ~ S.stringof ~ " " ~ T.stringof);
3430 
3431             S r2 = replaceLast(r1, from, into);
3432             assert(cmp(r2, "This is a silly silly list") == 0);
3433 
3434             S r3 = replaceLast(s, to!T(""), into);
3435             assert(cmp(r3, "This is a foo foo list") == 0);
3436 
3437             assert(replaceLast(r3, to!T("won't find"), to!T("whatever")) is r3);
3438         }}
3439     }
3440 }
3441 
3442 /++
3443     Creates a new array such that the items in `slice` are replaced with the
3444     items in `replacement`. `slice` and `replacement` do not need to be the
3445     same length. The result will grow or shrink based on the items given.
3446 
3447     Params:
3448         s = the base of the new array
3449         slice = the slice of `s` to be replaced
3450         replacement = the items to replace `slice` with
3451 
3452     Returns:
3453         A new array that is `s` with `slice` replaced by
3454         `replacement[]`.
3455 
3456     See_Also:
3457         $(REF substitute, std,algorithm,iteration) for a lazy replace.
3458  +/
3459 inout(T)[] replaceSlice(T)(inout(T)[] s, in T[] slice, in T[] replacement)
3460 in
3461 {
3462     // Verify that slice[] really is a slice of s[]
3463     assert(overlap(s, slice) is slice, "slice[] is not a subslice of s[]");
3464 }
3465 do
3466 {
3467     auto result = new T[s.length - slice.length + replacement.length];
3468     immutable so = &slice[0] - &s[0];
3469     result[0 .. so] = s[0 .. so];
3470     result[so .. so + replacement.length] = replacement[];
3471     result[so + replacement.length .. result.length] =
3472         s[so + slice.length .. s.length];
3473 
3474     return () @trusted inout {
3475         return cast(inout(T)[]) result;
3476     }();
3477 }
3478 
3479 ///
3480 @safe unittest
3481 {
3482     auto a = [1, 2, 3, 4, 5];
3483     auto b = replaceSlice(a, a[1 .. 4], [0, 0, 0]);
3484 
3485     assert(b == [1, 0, 0, 0, 5]);
3486 }
3487 
3488 @safe unittest
3489 {
3490     import std.algorithm.comparison : cmp;
3491 
3492     string s = "hello";
3493     string slice = s[2 .. 4];
3494 
3495     auto r = replaceSlice(s, slice, "bar");
3496     int i;
3497     i = cmp(r, "hebaro");
3498     assert(i == 0);
3499 }
3500 
3501 /**
3502 Implements an output range that appends data to an array. This is
3503 recommended over $(D array ~= data) when appending many elements because it is more
3504 efficient. `Appender` maintains its own array metadata locally, so it can avoid
3505 the $(DDSUBLINK spec/arrays, capacity-reserve, performance hit of looking up slice `capacity`)
3506 for each append.
3507 
3508 Params:
3509     A = the array type to simulate.
3510 
3511 See_Also: $(LREF appender)
3512  */
3513 struct Appender(A)
3514 if (isDynamicArray!A)
3515 {
3516     import core.memory : GC;
3517 
3518     private alias T = ElementEncodingType!A;
3519 
3520     private struct Data
3521     {
3522         size_t capacity;
3523         Unqual!T[] arr;
3524         bool tryExtendBlock = false;
3525     }
3526 
3527     private Data* _data;
3528 
3529     /**
3530      * Constructs an `Appender` with a given array.  Note that this does not copy the
3531      * data.  If the array has a larger capacity as determined by `arr.capacity`,
3532      * it will be used by the appender.  After initializing an appender on an array,
3533      * appending to the original array will reallocate.
3534      */
3535     this(A arr) @trusted
3536     {
3537         // initialize to a given array.
3538         _data = new Data;
3539         _data.arr = cast(Unqual!T[]) arr; //trusted
3540 
3541         if (__ctfe)
3542             return;
3543 
3544         // We want to use up as much of the block the array is in as possible.
3545         // if we consume all the block that we can, then array appending is
3546         // safe WRT built-in append, and we can use the entire block.
3547         // We only do this for mutable types that can be extended.
3548         static if (isMutable!T && is(typeof(arr.length = size_t.max)))
3549         {
3550             immutable cap = arr.capacity; //trusted
3551             // Replace with "GC.setAttr( Not Appendable )" once pure (and fixed)
3552             if (cap > arr.length)
3553                 arr.length = cap;
3554         }
3555         _data.capacity = arr.length;
3556     }
3557 
3558     /**
3559      * Reserve at least newCapacity elements for appending.  Note that more elements
3560      * may be reserved than requested. If `newCapacity <= capacity`, then nothing is
3561      * done.
3562      *
3563      * Params:
3564      *     newCapacity = the capacity the `Appender` should have
3565      */
3566     void reserve(size_t newCapacity)
3567     {
3568         if (_data)
3569         {
3570             if (newCapacity > _data.capacity)
3571                 ensureAddable(newCapacity - _data.arr.length);
3572         }
3573         else
3574         {
3575             ensureAddable(newCapacity);
3576         }
3577     }
3578 
3579     /**
3580      * Returns: the capacity of the array (the maximum number of elements the
3581      * managed array can accommodate before triggering a reallocation). If any
3582      * appending will reallocate, `0` will be returned.
3583      */
3584     @property size_t capacity() const
3585     {
3586         return _data ? _data.capacity : 0;
3587     }
3588 
3589     /// Returns: The number of elements appended.
3590     @property size_t length() const => _data ? _data.arr.length : 0;
3591 
3592     /**
3593      * Use opSlice() from now on.
3594      * Returns: The managed array.
3595      */
3596     @property inout(T)[] data() inout
3597     {
3598         return this[];
3599     }
3600 
3601     /**
3602      * Returns: The managed array.
3603      */
3604     @property inout(T)[] opSlice() inout @trusted
3605     {
3606         /* @trusted operation:
3607          * casting Unqual!T[] to inout(T)[]
3608          */
3609         return cast(typeof(return))(_data ? _data.arr : null);
3610     }
3611 
3612     // ensure we can add nelems elements, resizing as necessary
3613     private void ensureAddable(size_t nelems)
3614     {
3615         if (!_data)
3616             _data = new Data;
3617         immutable len = _data.arr.length;
3618         immutable reqlen = len + nelems;
3619 
3620         if (_data.capacity >= reqlen)
3621             return;
3622 
3623         // need to increase capacity
3624         if (__ctfe)
3625         {
3626             static if (__traits(compiles, new Unqual!T[1]))
3627             {
3628                 _data.arr.length = reqlen;
3629             }
3630             else
3631             {
3632                 // avoid restriction of @disable this()
3633                 _data.arr = _data.arr[0 .. _data.capacity];
3634                 foreach (i; _data.capacity .. reqlen)
3635                     _data.arr ~= Unqual!T.init;
3636             }
3637             _data.arr = _data.arr[0 .. len];
3638             _data.capacity = reqlen;
3639         }
3640         else
3641         {
3642             // Time to reallocate.
3643             // We need to almost duplicate what's in druntime, except we
3644             // have better access to the capacity field.
3645             auto newlen = appenderNewCapacity!(T.sizeof)(_data.capacity, reqlen);
3646             // first, try extending the current block
3647             if (_data.tryExtendBlock)
3648             {
3649                 immutable u = (() @trusted => GC.extend(_data.arr.ptr, nelems * T.sizeof, (newlen - len) * T.sizeof))();
3650                 if (u)
3651                 {
3652                     // extend worked, update the capacity
3653                     _data.capacity = u / T.sizeof;
3654                     return;
3655                 }
3656             }
3657 
3658 
3659             // didn't work, must reallocate
3660             import core.checkedint : mulu;
3661             bool overflow;
3662             const nbytes = mulu(newlen, T.sizeof, overflow);
3663             if (overflow) assert(false, "the reallocation would exceed the "
3664                     ~ "available pointer range");
3665 
3666             auto bi = (() @trusted => GC.qalloc(nbytes, blockAttribute!T))();
3667             _data.capacity = bi.size / T.sizeof;
3668             import core.stdc.string : memcpy;
3669             if (len)
3670                 () @trusted { memcpy(bi.base, _data.arr.ptr, len * T.sizeof); }();
3671             _data.arr = (() @trusted => (cast(Unqual!T*) bi.base)[0 .. len])();
3672             _data.tryExtendBlock = true;
3673             // leave the old data, for safety reasons
3674         }
3675     }
3676 
3677     private template canPutItem(U)
3678     {
3679         enum bool canPutItem =
3680             is(Unqual!U : Unqual!T) ||
3681             isSomeChar!T && isSomeChar!U;
3682     }
3683     private template canPutConstRange(Range)
3684     {
3685         enum bool canPutConstRange =
3686             isInputRange!(Unqual!Range) &&
3687             !isInputRange!Range &&
3688             is(typeof(Appender.init.put(Range.init.front)));
3689     }
3690     private template canPutRange(Range)
3691     {
3692         enum bool canPutRange =
3693             isInputRange!Range &&
3694             is(typeof(Appender.init.put(Range.init.front)));
3695     }
3696 
3697     /**
3698      * Appends `item` to the managed array. Performs encoding for
3699      * `char` types if `A` is a differently typed `char` array.
3700      *
3701      * Params:
3702      *     item = the single item to append
3703      */
3704     void put(U)(U item) if (canPutItem!U)
3705     {
3706         static if (isSomeChar!T && isSomeChar!U && T.sizeof < U.sizeof)
3707         {
3708             /* may throwable operation:
3709              * - std.utf.encode
3710              */
3711             // must do some transcoding around here
3712             import std.utf : encode;
3713             Unqual!T[T.sizeof == 1 ? 4 : 2] encoded;
3714             auto len = encode(encoded, item);
3715             put(encoded[0 .. len]);
3716         }
3717         else
3718         {
3719             import core.lifetime : emplace;
3720 
3721             ensureAddable(1);
3722             immutable len = _data.arr.length;
3723 
3724             auto bigData = (() @trusted => _data.arr.ptr[0 .. len + 1])();
3725             auto itemUnqual = (() @trusted => & cast() item)();
3726             emplace(&bigData[len], *itemUnqual);
3727             //We do this at the end, in case of exceptions
3728             _data.arr = bigData;
3729         }
3730     }
3731 
3732     // Const fixing hack.
3733     void put(Range)(Range items) if (canPutConstRange!Range)
3734     {
3735         alias p = put!(Unqual!Range);
3736         p(items);
3737     }
3738 
3739     /**
3740      * Appends an entire range to the managed array. Performs encoding for
3741      * `char` elements if `A` is a differently typed `char` array.
3742      *
3743      * Params:
3744      *     items = the range of items to append
3745      */
3746     void put(Range)(Range items) if (canPutRange!Range)
3747     {
3748         // note, we disable this branch for appending one type of char to
3749         // another because we can't trust the length portion.
3750         static if (!(isSomeChar!T && isSomeChar!(ElementType!Range) &&
3751                      !is(immutable Range == immutable T[])) &&
3752                     is(typeof(items.length) == size_t))
3753         {
3754             // optimization -- if this type is something other than a string,
3755             // and we are adding exactly one element, call the version for one
3756             // element.
3757             static if (!isSomeChar!T)
3758             {
3759                 if (items.length == 1)
3760                 {
3761                     put(items.front);
3762                     return;
3763                 }
3764             }
3765 
3766             // make sure we have enough space, then add the items
3767             auto bigDataFun(size_t extra)
3768             {
3769                 ensureAddable(extra);
3770                 return (() @trusted => _data.arr.ptr[0 .. _data.arr.length + extra])();
3771             }
3772             auto bigData = bigDataFun(items.length);
3773 
3774             immutable len = _data.arr.length;
3775             immutable newlen = bigData.length;
3776 
3777             alias UT = Unqual!T;
3778 
3779             static if (is(typeof(_data.arr[] = items[])) &&
3780                 !hasElaborateAssign!UT && isAssignable!(UT, ElementEncodingType!Range))
3781             {
3782                 bigData[len .. newlen] = items[];
3783             }
3784             else
3785             {
3786                 import core.internal.lifetime : emplaceRef;
3787                 foreach (ref it ; bigData[len .. newlen])
3788                 {
3789                     emplaceRef!T(it, items.front);
3790                     items.popFront();
3791                 }
3792             }
3793 
3794             //We do this at the end, in case of exceptions
3795             _data.arr = bigData;
3796         }
3797         else static if (isSomeChar!T && isSomeChar!(ElementType!Range) &&
3798                         !is(immutable T == immutable ElementType!Range))
3799         {
3800             // need to decode and encode
3801             import std.utf : decodeFront;
3802             while (!items.empty)
3803             {
3804                 auto c = items.decodeFront;
3805                 put(c);
3806             }
3807         }
3808         else
3809         {
3810             //pragma(msg, Range.stringof);
3811             // Generic input range
3812             for (; !items.empty; items.popFront())
3813             {
3814                 put(items.front);
3815             }
3816         }
3817     }
3818 
3819     /**
3820      * Appends to the managed array.
3821      *
3822      * See_Also: $(LREF Appender.put)
3823      */
3824     alias opOpAssign(string op : "~") = put;
3825 
3826     // only allow overwriting data on non-immutable and non-const data
3827     static if (isMutable!T)
3828     {
3829         /**
3830          * Clears the managed array.  This allows the elements of the array to be reused
3831          * for appending.
3832          *
3833          * Note: clear is disabled for immutable or const element types, due to the
3834          * possibility that `Appender` might overwrite immutable data.
3835          */
3836         void clear() @trusted pure nothrow
3837         {
3838             if (_data)
3839             {
3840                 _data.arr = _data.arr.ptr[0 .. 0];
3841             }
3842         }
3843 
3844         /**
3845          * Shrinks the managed array to the given length.
3846          *
3847          * Throws: `Exception` if newlength is greater than the current array length.
3848          * Note: shrinkTo is disabled for immutable or const element types.
3849          */
3850         void shrinkTo(size_t newlength) @trusted pure
3851         {
3852             import std.exception : enforce;
3853             if (_data)
3854             {
3855                 enforce(newlength <= _data.arr.length, "Attempting to shrink Appender with newlength > length");
3856                 _data.arr = _data.arr.ptr[0 .. newlength];
3857             }
3858             else
3859                 enforce(newlength == 0, "Attempting to shrink empty Appender with non-zero newlength");
3860         }
3861     }
3862 
3863     /**
3864      * Gives a string in the form of `Appender!(A)(data)`.
3865      *
3866      * Params:
3867      *     w = A `char` accepting
3868      *     $(REF_ALTTEXT output range, isOutputRange, std, range, primitives).
3869      *     fmt = A $(REF FormatSpec, std, format) which controls how the array
3870      *     is formatted.
3871      * Returns:
3872      *     A `string` if `writer` is not set; `void` otherwise.
3873      */
3874     string toString()() const
3875     {
3876         import std.format.spec : singleSpec;
3877 
3878         auto app = appender!string();
3879         auto spec = singleSpec("%s");
3880         immutable len = _data ? _data.arr.length : 0;
3881         // different reserve lengths because each element in a
3882         // non-string-like array uses two extra characters for `, `.
3883         static if (isSomeString!A)
3884         {
3885             app.reserve(len + 25);
3886         }
3887         else
3888         {
3889             // Multiplying by three is a very conservative estimate of
3890             // length, as it assumes each element is only one char
3891             app.reserve((len * 3) + 25);
3892         }
3893         toString(app, spec);
3894         return app.data;
3895     }
3896 
3897     import std.format.spec : FormatSpec;
3898 
3899     /// ditto
3900     template toString(Writer)
3901     if (isOutputRange!(Writer, char))
3902     {
3903         void toString(ref Writer w, scope const ref FormatSpec!char fmt) const
3904         {
3905             import std.format.write : formatValue;
3906             import std.range.primitives : put;
3907             put(w, Unqual!(typeof(this)).stringof);
3908             put(w, '(');
3909             formatValue(w, data, fmt);
3910             put(w, ')');
3911         }
3912     }
3913 }
3914 
3915 ///
3916 @safe pure nothrow unittest
3917 {
3918     auto app = appender!string();
3919     string b = "abcdefg";
3920     foreach (char c; b)
3921         app.put(c);
3922     assert(app[] == "abcdefg");
3923 
3924     int[] a = [ 1, 2 ];
3925     auto app2 = appender(a);
3926     app2.put(3);
3927     assert(app2.length == 3);
3928     app2.put([ 4, 5, 6 ]);
3929     assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
3930 }
3931 
3932 @safe pure unittest
3933 {
3934     import std.format : format;
3935     import std.format.spec : singleSpec;
3936 
3937     auto app = appender!(int[])();
3938     app.put(1);
3939     app.put(2);
3940     app.put(3);
3941     assert("%s".format(app) == "Appender!(int[])(%s)".format([1,2,3]));
3942 
3943     auto app2 = appender!string();
3944     auto spec = singleSpec("%s");
3945     app.toString(app2, spec);
3946     assert(app2[] == "Appender!(int[])([1, 2, 3])");
3947 
3948     auto app3 = appender!string();
3949     spec = singleSpec("%(%04d, %)");
3950     app.toString(app3, spec);
3951     assert(app3[] == "Appender!(int[])(0001, 0002, 0003)");
3952 }
3953 
3954 // https://issues.dlang.org/show_bug.cgi?id=17251
3955 @safe pure nothrow unittest
3956 {
3957     static struct R
3958     {
3959         int front() const { return 0; }
3960         bool empty() const { return true; }
3961         void popFront() {}
3962     }
3963 
3964     auto app = appender!(R[]);
3965     const(R)[1] r;
3966     app.put(r[0]);
3967     app.put(r[]);
3968 }
3969 
3970 // https://issues.dlang.org/show_bug.cgi?id=13300
3971 @safe pure nothrow unittest
3972 {
3973     static test(bool isPurePostblit)()
3974     {
3975         static if (!isPurePostblit)
3976             static int i;
3977 
3978         struct Simple
3979         {
3980             @disable this(); // Without this, it works.
3981             static if (!isPurePostblit)
3982                 this(this) { i++; }
3983             else
3984                 pure this(this) { }
3985 
3986             private:
3987             this(int tmp) { }
3988         }
3989 
3990         struct Range
3991         {
3992             @property Simple front() { return Simple(0); }
3993             void popFront() { count++; }
3994             @property empty() { return count < 3; }
3995             size_t count;
3996         }
3997 
3998         Range r;
3999         auto a = r.array();
4000     }
4001 
4002     static assert(__traits(compiles, () pure { test!true(); }));
4003     static assert(!__traits(compiles, () pure { test!false(); }));
4004 }
4005 
4006 // https://issues.dlang.org/show_bug.cgi?id=19572
4007 @safe pure nothrow unittest
4008 {
4009     static struct Struct
4010     {
4011         int value;
4012 
4013         int fun() const { return 23; }
4014 
4015         alias fun this;
4016     }
4017 
4018     Appender!(Struct[]) appender;
4019 
4020     appender.put(const(Struct)(42));
4021 
4022     auto result = appender[][0];
4023 
4024     assert(result.value != 23);
4025 }
4026 
4027 @safe pure unittest
4028 {
4029     import std.conv : to;
4030     import std.utf : byCodeUnit;
4031     auto str = "ウェブサイト";
4032     auto wstr = appender!wstring();
4033     put(wstr, str.byCodeUnit);
4034     assert(wstr.data == str.to!wstring);
4035 }
4036 
4037 // https://issues.dlang.org/show_bug.cgi?id=21256
4038 @safe pure unittest
4039 {
4040     Appender!string app1;
4041     app1.toString();
4042 
4043     Appender!(int[]) app2;
4044     app2.toString();
4045 }
4046 
4047 //Calculates an efficient growth scheme based on the old capacity
4048 //of data, and the minimum requested capacity.
4049 //arg curLen: The current length
4050 //arg reqLen: The length as requested by the user
4051 //ret sugLen: A suggested growth.
4052 private size_t appenderNewCapacity(size_t TSizeOf)(size_t curLen, size_t reqLen)
4053 {
4054     import core.bitop : bsr;
4055     import std.algorithm.comparison : max;
4056     if (curLen == 0)
4057         return max(reqLen,8);
4058     ulong mult = 100 + (1000UL) / (bsr(curLen * TSizeOf) + 1);
4059     // limit to doubling the length, we don't want to grow too much
4060     if (mult > 200)
4061         mult = 200;
4062     auto sugLen = cast(size_t)((curLen * mult + 99) / 100);
4063     return max(reqLen, sugLen);
4064 }
4065 
4066 /**
4067  * A version of $(LREF Appender) that can update an array in-place.
4068  * It forwards all calls to an underlying appender implementation.
4069  * Any calls made to the appender also update the pointer to the
4070  * original array passed in.
4071  *
4072  * Tip: Use the `arrayPtr` overload of $(LREF appender) for construction with type-inference.
4073  *
4074  * Params:
4075  *     A = The array type to simulate
4076  */
4077 struct RefAppender(A)
4078 if (isDynamicArray!A)
4079 {
4080     private alias T = ElementEncodingType!A;
4081 
4082     private
4083     {
4084         Appender!A impl;
4085         A* arr;
4086     }
4087 
4088     /**
4089      * Constructs a `RefAppender` with a given array reference.  This does not copy the
4090      * data.  If the array has a larger capacity as determined by `arr.capacity`, it
4091      * will be used by the appender.
4092      *
4093      * Note: Do not use built-in appending (i.e. `~=`) on the original array
4094      * until you are done with the appender, because subsequent calls to the appender
4095      * will reallocate the array data without those appends.
4096      *
4097      * Params:
4098      * arr = Pointer to an array. Must not be _null.
4099      */
4100     this(A* arr)
4101     {
4102         impl = Appender!A(*arr);
4103         this.arr = arr;
4104     }
4105 
4106     /** Wraps remaining `Appender` methods such as $(LREF put).
4107      * Params:
4108      * fn = Method name to call.
4109      * args = Arguments to pass to the method.
4110      */
4111     void opDispatch(string fn, Args...)(Args args)
4112     if (__traits(compiles, (Appender!A a) => mixin("a." ~ fn ~ "(args)")))
4113     {
4114         // we do it this way because we can't cache a void return
4115         scope(exit) *this.arr = impl[];
4116         mixin("return impl." ~ fn ~ "(args);");
4117     }
4118 
4119     /**
4120      * Appends `rhs` to the managed array.
4121      * Params:
4122      * rhs = Element or range.
4123      */
4124     void opOpAssign(string op : "~", U)(U rhs)
4125     if (__traits(compiles, (Appender!A a){ a.put(rhs); }))
4126     {
4127         scope(exit) *this.arr = impl[];
4128         impl.put(rhs);
4129     }
4130 
4131     /**
4132      * Returns the capacity of the array (the maximum number of elements the
4133      * managed array can accommodate before triggering a reallocation).  If any
4134      * appending will reallocate, `capacity` returns `0`.
4135      */
4136     @property size_t capacity() const
4137     {
4138         return impl.capacity;
4139     }
4140 
4141     /// Returns: The number of elements appended.
4142     @property size_t length() const => impl.length;
4143 
4144     /* Use opSlice() instead.
4145      * Returns: the managed array.
4146      */
4147     @property inout(T)[] data() inout
4148     {
4149         return impl[];
4150     }
4151 
4152     /**
4153      * Returns: the managed array.
4154      */
4155     @property inout(ElementEncodingType!A)[] opSlice() inout
4156     {
4157         return impl[];
4158     }
4159 }
4160 
4161 ///
4162 @safe pure nothrow
4163 unittest
4164 {
4165     int[] a = [1, 2];
4166     auto app2 = appender(&a);
4167     assert(app2[] == [1, 2]);
4168     assert(a == [1, 2]);
4169     app2 ~= 3;
4170     assert(app2.length == 3);
4171     app2 ~= [4, 5, 6];
4172     assert(app2[] == [1, 2, 3, 4, 5, 6]);
4173     assert(a == [1, 2, 3, 4, 5, 6]);
4174 
4175     app2.reserve(5);
4176     assert(app2.capacity >= 5);
4177 }
4178 
4179 /++
4180     Convenience function that returns an $(LREF Appender) instance,
4181     optionally initialized with `array`.
4182  +/
4183 Appender!A appender(A)()
4184 if (isDynamicArray!A)
4185 {
4186     return Appender!A(null);
4187 }
4188 /// ditto
4189 Appender!(E[]) appender(A : E[], E)(auto ref A array)
4190 {
4191     static assert(!isStaticArray!A || __traits(isRef, array),
4192         "Cannot create Appender from an rvalue static array");
4193 
4194     return Appender!(E[])(array);
4195 }
4196 
4197 @safe pure nothrow unittest
4198 {
4199     auto app = appender!(char[])();
4200     string b = "abcdefg";
4201     foreach (char c; b) app.put(c);
4202     assert(app[] == "abcdefg");
4203 }
4204 
4205 @safe pure nothrow unittest
4206 {
4207     auto app = appender!(char[])();
4208     string b = "abcdefg";
4209     foreach (char c; b) app ~= c;
4210     assert(app[] == "abcdefg");
4211 }
4212 
4213 @safe pure nothrow unittest
4214 {
4215     int[] a = [ 1, 2 ];
4216     auto app2 = appender(a);
4217     assert(app2[] == [ 1, 2 ]);
4218     app2.put(3);
4219     app2.put([ 4, 5, 6 ][]);
4220     assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
4221     app2.put([ 7 ]);
4222     assert(app2[] == [ 1, 2, 3, 4, 5, 6, 7 ]);
4223 }
4224 
4225 @safe pure nothrow unittest
4226 {
4227     auto app4 = appender([]);
4228     try // shrinkTo may throw
4229     {
4230         app4.shrinkTo(0);
4231     }
4232     catch (Exception) assert(0);
4233 }
4234 
4235 // https://issues.dlang.org/show_bug.cgi?id=5663
4236 // https://issues.dlang.org/show_bug.cgi?id=9725
4237 @safe pure nothrow unittest
4238 {
4239     import std.exception : assertNotThrown;
4240 
4241     static foreach (S; AliasSeq!(char[], const(char)[], string))
4242     {
4243         {
4244             Appender!S app5663i;
4245             assertNotThrown(app5663i.put("\xE3"));
4246             assert(app5663i[] == "\xE3");
4247 
4248             Appender!S app5663c;
4249             assertNotThrown(app5663c.put(cast(const(char)[])"\xE3"));
4250             assert(app5663c[] == "\xE3");
4251 
4252             Appender!S app5663m;
4253             assertNotThrown(app5663m.put("\xE3".dup));
4254             assert(app5663m[] == "\xE3");
4255         }
4256         // ditto for ~=
4257         {
4258             Appender!S app5663i;
4259             assertNotThrown(app5663i ~= "\xE3");
4260             assert(app5663i[] == "\xE3");
4261 
4262             Appender!S app5663c;
4263             assertNotThrown(app5663c ~= cast(const(char)[])"\xE3");
4264             assert(app5663c[] == "\xE3");
4265 
4266             Appender!S app5663m;
4267             assertNotThrown(app5663m ~= "\xE3".dup);
4268             assert(app5663m[] == "\xE3");
4269         }
4270     }
4271 }
4272 
4273 // https://issues.dlang.org/show_bug.cgi?id=10122
4274 @safe pure nothrow unittest
4275 {
4276     import std.exception : assertCTFEable;
4277 
4278     static struct S10122
4279     {
4280         int val;
4281 
4282         @disable this();
4283         this(int v) @safe pure nothrow { val = v; }
4284     }
4285     assertCTFEable!(
4286     {
4287         auto w = appender!(S10122[])();
4288         w.put(S10122(1));
4289         assert(w[].length == 1 && w[][0].val == 1);
4290     });
4291 }
4292 
4293 @safe pure nothrow unittest
4294 {
4295     import std.exception : assertThrown;
4296 
4297     int[] a = [ 1, 2 ];
4298     auto app2 = appender(a);
4299     assert(app2[] == [ 1, 2 ]);
4300     app2 ~= 3;
4301     app2 ~= [ 4, 5, 6 ][];
4302     assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
4303     app2 ~= [ 7 ];
4304     assert(app2[] == [ 1, 2, 3, 4, 5, 6, 7 ]);
4305 
4306     app2.reserve(5);
4307     assert(app2.capacity >= 5);
4308 
4309     try // shrinkTo may throw
4310     {
4311         app2.shrinkTo(3);
4312     }
4313     catch (Exception) assert(0);
4314     assert(app2[] == [ 1, 2, 3 ]);
4315     assertThrown(app2.shrinkTo(5));
4316 
4317     const app3 = app2;
4318     assert(app3.capacity >= 3);
4319     assert(app3[] == [1, 2, 3]);
4320 }
4321 
4322 ///
4323 @safe pure nothrow
4324 unittest
4325 {
4326     auto w = appender!string;
4327     // pre-allocate space for at least 10 elements (this avoids costly reallocations)
4328     w.reserve(10);
4329     assert(w.capacity >= 10);
4330 
4331     w.put('a'); // single elements
4332     w.put("bc"); // multiple elements
4333 
4334     // use the append syntax
4335     w ~= 'd';
4336     w ~= "ef";
4337 
4338     assert(w[] == "abcdef");
4339 }
4340 
4341 @safe pure nothrow unittest
4342 {
4343     auto w = appender!string();
4344     w.reserve(4);
4345     cast(void) w.capacity;
4346     cast(void) w[];
4347     try
4348     {
4349         wchar wc = 'a';
4350         dchar dc = 'a';
4351         w.put(wc);    // decoding may throw
4352         w.put(dc);    // decoding may throw
4353     }
4354     catch (Exception) assert(0);
4355 }
4356 
4357 @safe pure nothrow unittest
4358 {
4359     auto w = appender!(int[])();
4360     w.reserve(4);
4361     cast(void) w.capacity;
4362     cast(void) w[];
4363     w.put(10);
4364     w.put([10]);
4365     w.clear();
4366     try
4367     {
4368         w.shrinkTo(0);
4369     }
4370     catch (Exception) assert(0);
4371 
4372     struct N
4373     {
4374         int payload;
4375         alias payload this;
4376     }
4377     w.put(N(1));
4378     w.put([N(2)]);
4379 
4380     struct S(T)
4381     {
4382         @property bool empty() { return true; }
4383         @property T front() { return T.init; }
4384         void popFront() {}
4385     }
4386     S!int r;
4387     w.put(r);
4388 }
4389 
4390 // https://issues.dlang.org/show_bug.cgi?id=10690
4391 @safe pure nothrow unittest
4392 {
4393     import std.algorithm.iteration : filter;
4394     import std.typecons : tuple;
4395     [tuple(1)].filter!(t => true).array; // No error
4396     [tuple("A")].filter!(t => true).array; // error
4397 }
4398 
4399 @safe pure nothrow unittest
4400 {
4401     import std.range;
4402     //Coverage for put(Range)
4403     struct S1
4404     {
4405     }
4406     struct S2
4407     {
4408         void opAssign(S2){}
4409     }
4410     auto a1 = Appender!(S1[])();
4411     auto a2 = Appender!(S2[])();
4412     auto au1 = Appender!(const(S1)[])();
4413     a1.put(S1().repeat().take(10));
4414     a2.put(S2().repeat().take(10));
4415     auto sc1 = const(S1)();
4416     au1.put(sc1.repeat().take(10));
4417 }
4418 
4419 @system pure unittest
4420 {
4421     import std.range;
4422     struct S2
4423     {
4424         void opAssign(S2){}
4425     }
4426     auto au2 = Appender!(const(S2)[])();
4427     auto sc2 = const(S2)();
4428     au2.put(sc2.repeat().take(10));
4429 }
4430 
4431 @system pure nothrow unittest
4432 {
4433     struct S
4434     {
4435         int* p;
4436     }
4437 
4438     auto a0 = Appender!(S[])();
4439     auto a1 = Appender!(const(S)[])();
4440     auto a2 = Appender!(immutable(S)[])();
4441     auto s0 = S(null);
4442     auto s1 = const(S)(null);
4443     auto s2 = immutable(S)(null);
4444     a1.put(s0);
4445     a1.put(s1);
4446     a1.put(s2);
4447     a1.put([s0]);
4448     a1.put([s1]);
4449     a1.put([s2]);
4450     a0.put(s0);
4451     static assert(!is(typeof(a0.put(a1))));
4452     static assert(!is(typeof(a0.put(a2))));
4453     a0.put([s0]);
4454     static assert(!is(typeof(a0.put([a1]))));
4455     static assert(!is(typeof(a0.put([a2]))));
4456     static assert(!is(typeof(a2.put(a0))));
4457     static assert(!is(typeof(a2.put(a1))));
4458     a2.put(s2);
4459     static assert(!is(typeof(a2.put([a0]))));
4460     static assert(!is(typeof(a2.put([a1]))));
4461     a2.put([s2]);
4462 }
4463 
4464 // https://issues.dlang.org/show_bug.cgi?id=9528
4465 @safe pure nothrow unittest
4466 {
4467     const(E)[] fastCopy(E)(E[] src) {
4468             auto app = appender!(const(E)[])();
4469             foreach (i, e; src)
4470                     app.put(e);
4471             return app[];
4472     }
4473 
4474     static class C {}
4475     static struct S { const(C) c; }
4476     S[] s = [ S(new C) ];
4477 
4478     auto t = fastCopy(s); // Does not compile
4479     assert(t.length == 1);
4480 }
4481 
4482 // https://issues.dlang.org/show_bug.cgi?id=10753
4483 @safe pure unittest
4484 {
4485     import std.algorithm.iteration : map;
4486     struct Foo {
4487        immutable dchar d;
4488     }
4489     struct Bar {
4490        immutable int x;
4491     }
4492     "12".map!Foo.array;
4493     [1, 2].map!Bar.array;
4494 }
4495 
4496 @safe pure nothrow unittest
4497 {
4498     import std.algorithm.comparison : equal;
4499 
4500     //New appender signature tests
4501     alias mutARR = int[];
4502     alias conARR = const(int)[];
4503     alias immARR = immutable(int)[];
4504 
4505     mutARR mut;
4506     conARR con;
4507     immARR imm;
4508 
4509     auto app1 = Appender!mutARR(mut);                //Always worked. Should work. Should not create a warning.
4510     app1.put(7);
4511     assert(equal(app1[], [7]));
4512     static assert(!is(typeof(Appender!mutARR(con)))); //Never worked.  Should not work.
4513     static assert(!is(typeof(Appender!mutARR(imm)))); //Never worked.  Should not work.
4514 
4515     auto app2 = Appender!conARR(mut); //Always worked. Should work. Should not create a warning.
4516     app2.put(7);
4517     assert(equal(app2[], [7]));
4518     auto app3 = Appender!conARR(con); //Didn't work.   Now works.   Should not create a warning.
4519     app3.put(7);
4520     assert(equal(app3[], [7]));
4521     auto app4 = Appender!conARR(imm); //Didn't work.   Now works.   Should not create a warning.
4522     app4.put(7);
4523     assert(equal(app4[], [7]));
4524 
4525     //{auto app = Appender!immARR(mut);}                //Worked. Will cease to work. Creates warning.
4526     //static assert(!is(typeof(Appender!immARR(mut)))); //Worked. Will cease to work. Uncomment me after full deprecation.
4527     static assert(!is(typeof(Appender!immARR(con))));   //Never worked. Should not work.
4528     auto app5 = Appender!immARR(imm);                  //Didn't work.  Now works. Should not create a warning.
4529     app5.put(7);
4530     assert(equal(app5[], [7]));
4531 
4532     //Deprecated. Please uncomment and make sure this doesn't work:
4533     //char[] cc;
4534     //static assert(!is(typeof(Appender!string(cc))));
4535 
4536     //This should always work:
4537     auto app6 = appender!string(null);
4538     assert(app6[] == null);
4539     auto app7 = appender!(const(char)[])(null);
4540     assert(app7[] == null);
4541     auto app8 = appender!(char[])(null);
4542     assert(app8[] == null);
4543 }
4544 
4545 @safe pure nothrow unittest //Test large allocations (for GC.extend)
4546 {
4547     import std.algorithm.comparison : equal;
4548     import std.range;
4549     Appender!(char[]) app;
4550     app.reserve(1); //cover reserve on non-initialized
4551     foreach (_; 0 .. 100_000)
4552         app.put('a');
4553     assert(equal(app[], 'a'.repeat(100_000)));
4554 }
4555 
4556 @safe pure nothrow unittest
4557 {
4558     auto reference = new ubyte[](2048 + 1); //a number big enough to have a full page (EG: the GC extends)
4559     auto arr = reference.dup;
4560     auto app = appender(arr[0 .. 0]);
4561     app.reserve(1); //This should not trigger a call to extend
4562     app.put(ubyte(1)); //Don't clobber arr
4563     assert(reference[] == arr[]);
4564 }
4565 
4566 @safe pure nothrow unittest // clear method is supported only for mutable element types
4567 {
4568     Appender!string app;
4569     app.put("foo");
4570     static assert(!__traits(compiles, app.clear()));
4571     assert(app[] == "foo");
4572 }
4573 
4574 @safe pure nothrow unittest
4575 {
4576     static struct D//dynamic
4577     {
4578         int[] i;
4579         alias i this;
4580     }
4581     static struct S//static
4582     {
4583         int[5] i;
4584         alias i this;
4585     }
4586     static assert(!is(Appender!(char[5])));
4587     static assert(!is(Appender!D));
4588     static assert(!is(Appender!S));
4589 
4590     enum int[5] a = [];
4591     int[5] b;
4592     D d;
4593     S s;
4594     int[5] foo(){return a;}
4595 
4596     static assert(!is(typeof(appender(a))));
4597     static assert( is(typeof(appender(b))));
4598     static assert( is(typeof(appender(d))));
4599     static assert( is(typeof(appender(s))));
4600     static assert(!is(typeof(appender(foo()))));
4601 }
4602 
4603 @system unittest
4604 {
4605     // https://issues.dlang.org/show_bug.cgi?id=13077
4606     static class A {}
4607 
4608     // reduced case
4609     auto w = appender!(shared(A)[])();
4610     w.put(new shared A());
4611 
4612     // original case
4613     import std.range;
4614     InputRange!(shared A) foo()
4615     {
4616         return [new shared A].inputRangeObject;
4617     }
4618     auto res = foo.array;
4619     assert(res.length == 1);
4620 }
4621 
4622 /++
4623     Convenience function that returns a $(LREF RefAppender) instance initialized
4624     with `arrayPtr`. Don't use null for the array pointer, use the other
4625     version of `appender` instead.
4626  +/
4627 RefAppender!(E[]) appender(P : E[]*, E)(P arrayPtr)
4628 {
4629     return RefAppender!(E[])(arrayPtr);
4630 }
4631 
4632 ///
4633 @safe pure nothrow
4634 unittest
4635 {
4636     int[] a = [1, 2];
4637     auto app2 = appender(&a);
4638     assert(app2[] == [1, 2]);
4639     assert(a == [1, 2]);
4640     app2 ~= 3;
4641     app2 ~= [4, 5, 6];
4642     assert(app2[] == [1, 2, 3, 4, 5, 6]);
4643     assert(a == [1, 2, 3, 4, 5, 6]);
4644 
4645     app2.reserve(5);
4646     assert(app2.capacity >= 5);
4647 }
4648 
4649 @safe pure nothrow unittest
4650 {
4651     auto arr = new char[0];
4652     auto app = appender(&arr);
4653     string b = "abcdefg";
4654     foreach (char c; b) app.put(c);
4655     assert(app[] == "abcdefg");
4656     assert(arr == "abcdefg");
4657 }
4658 
4659 @safe pure nothrow unittest
4660 {
4661     auto arr = new char[0];
4662     auto app = appender(&arr);
4663     string b = "abcdefg";
4664     foreach (char c; b) app ~= c;
4665     assert(app[] == "abcdefg");
4666     assert(arr == "abcdefg");
4667 }
4668 
4669 @safe pure nothrow unittest
4670 {
4671     int[] a = [ 1, 2 ];
4672     auto app2 = appender(&a);
4673     assert(app2[] == [ 1, 2 ]);
4674     assert(a == [ 1, 2 ]);
4675     app2.put(3);
4676     app2.put([ 4, 5, 6 ][]);
4677     assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
4678     assert(a == [ 1, 2, 3, 4, 5, 6 ]);
4679 }
4680 
4681 @safe pure nothrow unittest
4682 {
4683     import std.exception : assertThrown;
4684 
4685     int[] a = [ 1, 2 ];
4686     auto app2 = appender(&a);
4687     assert(app2[] == [ 1, 2 ]);
4688     assert(a == [ 1, 2 ]);
4689     app2 ~= 3;
4690     app2 ~= [ 4, 5, 6 ][];
4691     assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
4692     assert(a == [ 1, 2, 3, 4, 5, 6 ]);
4693 
4694     app2.reserve(5);
4695     assert(app2.capacity >= 5);
4696 
4697     try // shrinkTo may throw
4698     {
4699         app2.shrinkTo(3);
4700     }
4701     catch (Exception) assert(0);
4702     assert(app2[] == [ 1, 2, 3 ]);
4703     assertThrown(app2.shrinkTo(5));
4704 
4705     const app3 = app2;
4706     assert(app3.capacity >= 3);
4707     assert(app3[] == [1, 2, 3]);
4708 }
4709 
4710 // https://issues.dlang.org/show_bug.cgi?id=14605
4711 @safe pure nothrow unittest
4712 {
4713     static assert(isOutputRange!(Appender!(int[]), int));
4714     static assert(isOutputRange!(RefAppender!(int[]), int));
4715 }
4716 
4717 @safe pure nothrow unittest
4718 {
4719     Appender!(int[]) app;
4720     short[] range = [1, 2, 3];
4721     app.put(range);
4722     assert(app[] == [1, 2, 3]);
4723 }
4724 
4725 @safe pure nothrow unittest
4726 {
4727     string s = "hello".idup;
4728     char[] a = "hello".dup;
4729     auto appS = appender(s);
4730     auto appA = appender(a);
4731     put(appS, 'w');
4732     put(appA, 'w');
4733     s ~= 'a'; //Clobbers here?
4734     a ~= 'a'; //Clobbers here?
4735     assert(appS[] == "hellow");
4736     assert(appA[] == "hellow");
4737 }
4738 
4739 /++
4740 Constructs a static array from a dynamic array whose length is known at compile-time.
4741 The element type can be inferred or specified explicitly:
4742 
4743 * $(D [1, 2].staticArray) returns `int[2]`
4744 * $(D [1, 2].staticArray!float) returns `float[2]`
4745 
4746 Note: `staticArray` returns by value, so expressions involving large arrays may be inefficient.
4747 
4748 Params:
4749     a = The input array.
4750 
4751 Returns: A static array constructed from `a`.
4752 +/
4753 pragma(inline, true) T[n] staticArray(T, size_t n)(auto ref T[n] a)
4754 {
4755     return a;
4756 }
4757 
4758 /// static array from array literal
4759 nothrow pure @safe @nogc unittest
4760 {
4761     auto a = [0, 1].staticArray;
4762     static assert(is(typeof(a) == int[2]));
4763     assert(a == [0, 1]);
4764 }
4765 
4766 /// ditto
4767 pragma(inline, true) U[n] staticArray(U, T, size_t n)(auto ref T[n] a)
4768 if (!is(T == U) && is(T : U))
4769 {
4770     return a[].staticArray!(U[n]);
4771 }
4772 
4773 /// static array from array with implicit casting of elements
4774 nothrow pure @safe @nogc unittest
4775 {
4776     auto b = [0, 1].staticArray!long;
4777     static assert(is(typeof(b) == long[2]));
4778     assert(b == [0, 1]);
4779 }
4780 
4781 nothrow pure @safe @nogc unittest
4782 {
4783     int val = 3;
4784     static immutable gold = [1, 2, 3];
4785     [1, 2, val].staticArray.checkStaticArray!int([1, 2, 3]);
4786 
4787     @nogc void checkNogc()
4788     {
4789         [1, 2, val].staticArray.checkStaticArray!int(gold);
4790     }
4791 
4792     checkNogc();
4793 
4794     [1, 2, val].staticArray!double.checkStaticArray!double(gold);
4795     [1, 2, 3].staticArray!int.checkStaticArray!int(gold);
4796 
4797     [1, 2, 3].staticArray!(const(int)).checkStaticArray!(const(int))(gold);
4798     [1, 2, 3].staticArray!(const(double)).checkStaticArray!(const(double))(gold);
4799     {
4800         const(int)[3] a2 = [1, 2, 3].staticArray;
4801     }
4802 
4803     [cast(byte) 1, cast(byte) 129].staticArray.checkStaticArray!byte([1, -127]);
4804 }
4805 
4806 /**
4807 Constructs a static array from a range.
4808 When `a.length` is not known at compile time, the number of elements must be
4809 given as a template argument (e.g. `myrange.staticArray!2`).
4810 Size and type can be combined, if the source range elements are implicitly
4811 convertible to the requested element type (eg: `2.iota.staticArray!(long[2])`).
4812 
4813 When the range `a` is known at compile time, it can be given as a
4814 template argument to avoid having to specify the number of elements
4815 (e.g.: `staticArray!(2.iota)` or `staticArray!(double, 2.iota)`).
4816 
4817 Params:
4818     a = The input range. If there are less elements than the specified length of the static array,
4819     the rest of it is default-initialized. If there are more than specified, the first elements
4820     up to the specified length are used.
4821     rangeLength = Output for the number of elements used from `a`. Optional.
4822 */
4823 auto staticArray(size_t n, T)(scope T a)
4824 if (isInputRange!T)
4825 {
4826     alias U = ElementType!T;
4827     return staticArray!(U[n], U, n)(a);
4828 }
4829 
4830 /// ditto
4831 auto staticArray(size_t n, T)(scope T a, out size_t rangeLength)
4832 if (isInputRange!T)
4833 {
4834     alias U = ElementType!T;
4835     return staticArray!(U[n], U, n)(a, rangeLength);
4836 }
4837 
4838 /// ditto
4839 auto staticArray(Un : U[n], U, size_t n, T)(scope T a)
4840 if (isInputRange!T && is(ElementType!T : U))
4841 {
4842     size_t extraStackSpace;
4843     return staticArray!(Un, U, n)(a, extraStackSpace);
4844 }
4845 
4846 /// ditto
4847 auto staticArray(Un : U[n], U, size_t n, T)(scope T a, out size_t rangeLength)
4848 if (isInputRange!T && is(ElementType!T : U))
4849 {
4850     import std.algorithm.mutation : uninitializedFill;
4851     import std.range : take;
4852     import core.internal.lifetime : emplaceRef;
4853 
4854     if (__ctfe)
4855     {
4856         size_t i;
4857         // Compile-time version to avoid unchecked memory access.
4858         Unqual!U[n] ret;
4859         for (auto iter = a.take(n); !iter.empty; iter.popFront())
4860         {
4861             ret[i] = iter.front;
4862             i++;
4863         }
4864 
4865         rangeLength = i;
4866         return (() @trusted => cast(U[n]) ret)();
4867     }
4868 
4869     auto ret = (() @trusted
4870     {
4871         Unqual!U[n] theArray = void;
4872         return theArray;
4873     }());
4874 
4875     size_t i;
4876     if (true)
4877     {
4878         // ret was void-initialized so let's initialize the unfilled part manually.
4879         // also prevents destructors to be called on uninitialized memory if
4880         // an exception is thrown
4881         scope (exit) ret[i .. $].uninitializedFill(U.init);
4882 
4883         for (auto iter = a.take(n); !iter.empty; iter.popFront())
4884         {
4885             emplaceRef!U(ret[i++], iter.front);
4886         }
4887     }
4888 
4889     rangeLength = i;
4890     return (() @trusted => cast(U[n]) ret)();
4891 }
4892 
4893 /// static array from range + size
4894 nothrow pure @safe @nogc unittest
4895 {
4896     import std.range : iota;
4897 
4898     auto input = 3.iota;
4899     auto a = input.staticArray!2;
4900     static assert(is(typeof(a) == int[2]));
4901     assert(a == [0, 1]);
4902     auto b = input.staticArray!(long[4]);
4903     static assert(is(typeof(b) == long[4]));
4904     assert(b == [0, 1, 2, 0]);
4905 }
4906 
4907 // Tests that code compiles when there is an elaborate destructor and exceptions
4908 // are thrown. Unfortunately can't test that memory is initialized
4909 // before having a destructor called on it.
4910 @safe nothrow unittest
4911 {
4912     // exists only to allow doing something in the destructor. Not tested
4913     // at the end because value appears to depend on implementation of the.
4914     // function.
4915     static int preventersDestroyed = 0;
4916 
4917     static struct CopyPreventer
4918     {
4919         bool on = false;
4920         this(this)
4921         {
4922             if (on) throw new Exception("Thou shalt not copy past me!");
4923         }
4924 
4925         ~this()
4926         {
4927             preventersDestroyed++;
4928         }
4929     }
4930     auto normalArray =
4931     [
4932         CopyPreventer(false),
4933         CopyPreventer(false),
4934         CopyPreventer(true),
4935         CopyPreventer(false),
4936         CopyPreventer(true),
4937     ];
4938 
4939     try
4940     {
4941         auto staticArray = normalArray.staticArray!5;
4942         assert(false);
4943     }
4944     catch (Exception e){}
4945 }
4946 
4947 
4948 nothrow pure @safe @nogc unittest
4949 {
4950     auto a = [1, 2].staticArray;
4951     assert(is(typeof(a) == int[2]) && a == [1, 2]);
4952 
4953     import std.range : iota;
4954 
4955     2.iota.staticArray!2.checkStaticArray!int([0, 1]);
4956     2.iota.staticArray!(double[2]).checkStaticArray!double([0, 1]);
4957     2.iota.staticArray!(long[2]).checkStaticArray!long([0, 1]);
4958 }
4959 
4960 nothrow pure @safe @nogc unittest
4961 {
4962     import std.range : iota;
4963     size_t copiedAmount;
4964     2.iota.staticArray!1(copiedAmount);
4965     assert(copiedAmount == 1);
4966     2.iota.staticArray!3(copiedAmount);
4967     assert(copiedAmount == 2);
4968 }
4969 
4970 /// ditto
4971 auto staticArray(alias a)()
4972 if (isInputRange!(typeof(a)))
4973 {
4974     return .staticArray!(size_t(a.length))(a);
4975 }
4976 
4977 /// ditto
4978 auto staticArray(U, alias a)()
4979 if (isInputRange!(typeof(a)))
4980 {
4981     return .staticArray!(U[size_t(a.length)])(a);
4982 }
4983 
4984 /// static array from CT range
4985 nothrow pure @safe @nogc unittest
4986 {
4987     import std.range : iota;
4988 
4989     enum a = staticArray!(2.iota);
4990     static assert(is(typeof(a) == int[2]));
4991     assert(a == [0, 1]);
4992 
4993     enum b = staticArray!(long, 2.iota);
4994     static assert(is(typeof(b) == long[2]));
4995     assert(b == [0, 1]);
4996 }
4997 
4998 nothrow pure @safe @nogc unittest
4999 {
5000     import std.range : iota;
5001 
5002     enum a = staticArray!(2.iota);
5003     staticArray!(2.iota).checkStaticArray!int([0, 1]);
5004     staticArray!(double, 2.iota).checkStaticArray!double([0, 1]);
5005     staticArray!(long, 2.iota).checkStaticArray!long([0, 1]);
5006 }
5007 
5008 version (StdUnittest) private void checkStaticArray(T, T1, T2)(T1 a, T2 b) nothrow @safe pure @nogc
5009 {
5010     static assert(is(T1 == T[T1.length]));
5011     assert(a == b, "a must be equal to b");
5012 }