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