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