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 $(BOOKTABLE ,
9 $(TR $(TH Function Name) $(TH Description)
10 )
11 $(TR $(TD $(LREF _array))
12 $(TD Returns a copy of the input in a newly allocated dynamic _array.
13 ))
14 $(TR $(TD $(LREF appender))
15 $(TD Returns a new $(LREF Appender) or $(LREF RefAppender) initialized with a given _array.
16 ))
17 $(TR $(TD $(LREF assocArray))
18 $(TD Returns a newly allocated associative _array from a range of key/value tuples.
19 ))
20 $(TR $(TD $(LREF byPair))
21 $(TD Construct a range iterating over an associative _array by key/value tuples.
22 ))
23 $(TR $(TD $(LREF insertInPlace))
24 $(TD Inserts into an existing _array at a given position.
25 ))
26 $(TR $(TD $(LREF join))
27 $(TD Concatenates a range of ranges into one _array.
28 ))
29 $(TR $(TD $(LREF minimallyInitializedArray))
30 $(TD Returns a new _array of type $(D T).
31 ))
32 $(TR $(TD $(LREF replace))
33 $(TD Returns a new _array with all occurrences of a certain subrange replaced.
34 ))
35 $(TR $(TD $(LREF replaceFirst))
36 $(TD Returns a new _array with the first occurrence of a certain subrange replaced.
37 ))
38 $(TR $(TD $(LREF replaceInPlace))
39 $(TD Replaces all occurrences of a certain subrange and puts the result into a given _array.
40 ))
41 $(TR $(TD $(LREF replaceInto))
42 $(TD Replaces all occurrences of a certain subrange and puts the result into an output range.
43 ))
44 $(TR $(TD $(LREF replaceLast))
45 $(TD Returns a new _array with the last occurrence of a certain subrange replaced.
46 ))
47 $(TR $(TD $(LREF replaceSlice))
48 $(TD Returns a new _array with a given slice replaced.
49 ))
50 $(TR $(TD $(LREF replicate))
51 $(TD Creates a new _array out of several copies of an input _array or range.
52 ))
53 $(TR $(TD $(LREF sameHead))
54 $(TD Checks if the initial segments of two arrays refer to the same
55 place in memory.
56 ))
57 $(TR $(TD $(LREF sameTail))
58 $(TD Checks if the final segments of two arrays refer to the same place
59 in memory.
60 ))
61 $(TR $(TD $(LREF split))
62 $(TD Eagerly split a range or string into an _array.
63 ))
64 $(TR $(TD $(LREF uninitializedArray))
65 $(TD Returns a new _array of type $(D T) without initializing its elements.
66 ))
67 )
68
69 Copyright: Copyright Andrei Alexandrescu 2008- and Jonathan M Davis 2011-.
70
71 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
72
73 Authors: $(HTTP erdani.org, Andrei Alexandrescu) and Jonathan M Davis
74
75 Source: $(PHOBOSSRC std/_array.d)
76 */
77 module std.array;
78
79 import std.functional;
80 import std.meta;
81 import std.traits;
82
83 import std.range.primitives;
84 public import std.range.primitives : save, empty, popFront, popBack, front, back;
85
86 /**
87 * Allocates an array and initializes it with copies of the elements
88 * of range $(D r).
89 *
90 * Narrow strings are handled as a special case in an overload.
91 *
92 * Params:
93 * r = range (or aggregate with $(D opApply) function) whose elements are copied into the allocated array
94 * Returns:
95 * allocated and initialized array
96 */
97 ForeachType!Range[] array(Range)(Range r)
98 if (isIterable!Range && !isNarrowString!Range && !isInfinite!Range)
99 {
100 if (__ctfe)
101 {
102 // Compile-time version to avoid memcpy calls.
103 // Also used to infer attributes of array().
104 typeof(return) result;
105 foreach (e; r)
106 result ~= e;
107 return result;
108 }
109
110 alias E = ForeachType!Range;
111 static if (hasLength!Range)
112 {
113 auto length = r.length;
114 if (length == 0)
115 return null;
116
117 import std.conv : emplaceRef;
118
119 auto result = (() @trusted => uninitializedArray!(Unqual!E[])(length))();
120
121 // Every element of the uninitialized array must be initialized
122 size_t i;
foreach(e;r)123 foreach (e; r)
124 {
125 emplaceRef!E(result[i], e);
126 ++i;
127 }
128 return (() @trusted => cast(E[]) result)();
129 }
130 else
131 {
132 auto a = appender!(E[])();
foreach(e;r)133 foreach (e; r)
134 {
135 a.put(e);
136 }
137 return a.data;
138 }
139 }
140
141 ///
142 @safe pure nothrow unittest
143 {
144 auto a = array([1, 2, 3, 4, 5][]);
145 assert(a == [ 1, 2, 3, 4, 5 ]);
146 }
147
148 @safe pure nothrow unittest
149 {
150 import std.algorithm.comparison : equal;
151 struct Foo
152 {
153 int a;
154 }
155 auto a = array([Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)][]);
156 assert(equal(a, [Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)]));
157 }
158
159 @system unittest
160 {
161 import std.algorithm.comparison : equal;
162 struct Foo
163 {
164 int a;
opAssignFoo165 void opAssign(Foo foo)
166 {
167 assert(0);
168 }
opEqualsFoo169 auto opEquals(Foo foo)
170 {
171 return a == foo.a;
172 }
173 }
174 auto a = array([Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)][]);
175 assert(equal(a, [Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)]));
176 }
177
178 @safe unittest
179 {
180 // Issue 12315
181 static struct Bug12315 { immutable int i; }
182 enum bug12315 = [Bug12315(123456789)].array();
183 static assert(bug12315[0].i == 123456789);
184 }
185
186 @safe unittest
187 {
188 import std.range;
189 static struct S{int* p;}
190 auto a = array(immutable(S).init.repeat(5));
191 }
192
193 /**
194 Convert a narrow string to an array type that fully supports random access.
195 This is handled as a special case and always returns an array of `dchar`
196
197 Params:
198 str = `isNarrowString` to be converted to an array of `dchar`
199 Returns:
200 a $(D dchar[]), $(D const(dchar)[]), or $(D immutable(dchar)[]) depending on the constness of
201 the input.
202 */
203 @trusted ElementType!String[] array(String)(scope String str)
204 if (isNarrowString!String)
205 {
206 import std.utf : toUTF32;
207 /* This function is @trusted because the following cast
208 * is unsafe - converting a dstring[] to a dchar[], for example.
209 * Our special knowledge of toUTF32 is needed to know the cast is safe.
210 */
211 return cast(typeof(return)) str.toUTF32;
212 }
213
214 ///
215 @safe unittest
216 {
217 import std.range.primitives : isRandomAccessRange;
218
219 assert("Hello D".array == "Hello D"d);
220 static assert(isRandomAccessRange!string == false);
221
222 assert("Hello D"w.array == "Hello D"d);
223 static assert(isRandomAccessRange!dstring == true);
224 }
225
226 @system unittest
227 {
228 // @system due to array!string
229 import std.conv : to;
230
toStringTestArray231 static struct TestArray { int x; string toString() @safe { return to!string(x); } }
232
233 static struct OpAssign
234 {
235 uint num;
this(uint num)236 this(uint num) { this.num = num; }
237
238 // Templating opAssign to make sure the bugs with opAssign being
239 // templated are fixed.
opAssign(T)240 void opAssign(T)(T rhs) { this.num = rhs.num; }
241 }
242
243 static struct OpApply
244 {
opApplyOpApply245 int opApply(scope int delegate(ref int) dg)
246 {
247 int res;
248 foreach (i; 0 .. 10)
249 {
250 res = dg(i);
251 if (res) break;
252 }
253
254 return res;
255 }
256 }
257
258 auto a = array([1, 2, 3, 4, 5][]);
259 //writeln(a);
260 assert(a == [ 1, 2, 3, 4, 5 ]);
261
262 auto b = array([TestArray(1), TestArray(2)][]);
263 //writeln(b);
264
265 class C
266 {
267 int x;
this(int y)268 this(int y) { x = y; }
toString()269 override string toString() const @safe { return to!string(x); }
270 }
271 auto c = array([new C(1), new C(2)][]);
272 //writeln(c);
273
274 auto d = array([1.0, 2.2, 3][]);
275 assert(is(typeof(d) == double[]));
276 //writeln(d);
277
278 auto e = [OpAssign(1), OpAssign(2)];
279 auto f = array(e);
280 assert(e == f);
281
282 assert(array(OpApply.init) == [0,1,2,3,4,5,6,7,8,9]);
283 assert(array("ABC") == "ABC"d);
284 assert(array("ABC".dup) == "ABC"d.dup);
285 }
286
287 //Bug# 8233
288 @safe unittest
289 {
290 assert(array("hello world"d) == "hello world"d);
291 immutable a = [1, 2, 3, 4, 5];
292 assert(array(a) == a);
293 const b = a;
294 assert(array(b) == a);
295
296 //To verify that the opAssign branch doesn't get screwed up by using Unqual.
297 //EDIT: array no longer calls opAssign.
298 struct S
299 {
opAssignS300 ref S opAssign(S)(const ref S rhs)
301 {
302 assert(0);
303 }
304
305 int i;
306 }
307
308 foreach (T; AliasSeq!(S, const S, immutable S))
309 {
310 auto arr = [T(1), T(2), T(3), T(4)];
311 assert(array(arr) == arr);
312 }
313 }
314
315 @safe unittest
316 {
317 //9824
318 static struct S
319 {
320 @disable void opAssign(S);
321 int i;
322 }
323 auto arr = [S(0), S(1), S(2)];
324 arr.array();
325 }
326
327 // Bugzilla 10220
328 @safe unittest
329 {
330 import std.algorithm.comparison : equal;
331 import std.exception;
332 import std.range : repeat;
333
334 static struct S
335 {
336 int val;
337
338 @disable this();
thisS339 this(int v) { val = v; }
340 }
341 assertCTFEable!(
342 {
343 auto r = S(1).repeat(2).array();
344 assert(equal(r, [S(1), S(1)]));
345 });
346 }
347
348 @safe unittest
349 {
350 //Turn down infinity:
351 static assert(!is(typeof(
352 repeat(1).array()
353 )));
354 }
355
356 /**
357 Returns a newly allocated associative _array from a range of key/value tuples.
358
359 Params:
360 r = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
361 of tuples of keys and values.
362 Returns: A newly allocated associative array out of elements of the input
363 range, which must be a range of tuples (Key, Value). Returns a null associative
364 array reference when given an empty range.
365 Duplicates: Associative arrays have unique keys. If r contains duplicate keys,
366 then the result will contain the value of the last pair for that key in r.
367
368 See_Also: $(REF Tuple, std,typecons), $(REF zip, std,range)
369 */
370
371 auto assocArray(Range)(Range r)
372 if (isInputRange!Range)
373 {
374 import std.typecons : isTuple;
375
376 alias E = ElementType!Range;
377 static assert(isTuple!E, "assocArray: argument must be a range of tuples");
378 static assert(E.length == 2, "assocArray: tuple dimension must be 2");
379 alias KeyType = E.Types[0];
380 alias ValueType = E.Types[1];
381 static assert(isMutable!ValueType, "assocArray: value type must be mutable");
382
383 ValueType[KeyType] aa;
384 foreach (t; r)
385 aa[t[0]] = t[1];
386 return aa;
387 }
388
389 ///
390 @safe pure /*nothrow*/ unittest
391 {
392 import std.range;
393 import std.typecons;
394 auto a = assocArray(zip([0, 1, 2], ["a", "b", "c"])); // aka zipMap
395 assert(is(typeof(a) == string[int]));
396 assert(a == [0:"a", 1:"b", 2:"c"]);
397
398 auto b = assocArray([ tuple("foo", "bar"), tuple("baz", "quux") ]);
399 assert(is(typeof(b) == string[string]));
400 assert(b == ["foo":"bar", "baz":"quux"]);
401 }
402
403 // @@@11053@@@ - Cannot be version (unittest) - recursive instantiation error
404 @safe unittest
405 {
406 import std.typecons;
407 static assert(!__traits(compiles, [ tuple("foo", "bar", "baz") ].assocArray()));
408 static assert(!__traits(compiles, [ tuple("foo") ].assocArray()));
409 assert([ tuple("foo", "bar") ].assocArray() == ["foo": "bar"]);
410 }
411
412 // Issue 13909
413 @safe unittest
414 {
415 import std.typecons;
416 auto a = [tuple!(const string, string)("foo", "bar")];
417 auto b = [tuple!(string, const string)("foo", "bar")];
418 assert(assocArray(a) == [cast(const(string)) "foo": "bar"]);
419 static assert(!__traits(compiles, assocArray(b)));
420 }
421
422 /**
423 Construct a range iterating over an associative array by key/value tuples.
424
425 Params: aa = The associative array to iterate over.
426
427 Returns: A $(REF_ALTTEXT forward range, isForwardRange, std,_range,primitives)
428 of Tuple's of key and value pairs from the given associative array.
429 */
430 auto byPair(AA : Value[Key], Value, Key)(AA aa)
431 {
432 import std.algorithm.iteration : map;
433 import std.typecons : tuple;
434
435 return aa.byKeyValue.map!(pair => tuple(pair.key, pair.value));
436 }
437
438 ///
439 @system unittest
440 {
441 import std.algorithm.sorting : sort;
442 import std.typecons : tuple, Tuple;
443
444 auto aa = ["a": 1, "b": 2, "c": 3];
445 Tuple!(string, int)[] pairs;
446
447 // Iteration over key/value pairs.
448 foreach (pair; aa.byPair)
449 {
450 pairs ~= pair;
451 }
452
453 // Iteration order is implementation-dependent, so we should sort it to get
454 // a fixed order.
455 sort(pairs);
456 assert(pairs == [
457 tuple("a", 1),
458 tuple("b", 2),
459 tuple("c", 3)
460 ]);
461 }
462
463 @system unittest
464 {
465 import std.typecons : tuple, Tuple;
466
467 auto aa = ["a":2];
468 auto pairs = aa.byPair();
469
470 static assert(is(typeof(pairs.front) == Tuple!(string,int)));
471 static assert(isForwardRange!(typeof(pairs)));
472
473 assert(!pairs.empty);
474 assert(pairs.front == tuple("a", 2));
475
476 auto savedPairs = pairs.save;
477
478 pairs.popFront();
479 assert(pairs.empty);
480 assert(!savedPairs.empty);
481 assert(savedPairs.front == tuple("a", 2));
482 }
483
484 // Issue 17711
485 @system unittest
486 {
487 const(int[string]) aa = [ "abc": 123 ];
488
489 // Ensure that byKeyValue is usable with a const AA.
490 auto kv = aa.byKeyValue;
491 assert(!kv.empty);
492 assert(kv.front.key == "abc" && kv.front.value == 123);
493 kv.popFront();
494 assert(kv.empty);
495
496 // Ensure byPair is instantiable with const AA.
497 auto r = aa.byPair;
498 static assert(isInputRange!(typeof(r)));
499 assert(!r.empty && r.front[0] == "abc" && r.front[1] == 123);
500 r.popFront();
501 assert(r.empty);
502 }
503
blockAttribute(T)504 private template blockAttribute(T)
505 {
506 import core.memory;
507 static if (hasIndirections!(T) || is(T == void))
508 {
509 enum blockAttribute = 0;
510 }
511 else
512 {
513 enum blockAttribute = GC.BlkAttr.NO_SCAN;
514 }
515 }
version(unittest)516 version (unittest)
517 {
518 import core.memory : UGC = GC;
519 static assert(!(blockAttribute!void & UGC.BlkAttr.NO_SCAN));
520 }
521
522 // Returns the number of dimensions in an array T.
nDimensions(T)523 private template nDimensions(T)
524 {
525 static if (isArray!T)
526 {
527 enum nDimensions = 1 + nDimensions!(typeof(T.init[0]));
528 }
529 else
530 {
531 enum nDimensions = 0;
532 }
533 }
534
version(unittest)535 version (unittest)
536 {
537 static assert(nDimensions!(uint[]) == 1);
538 static assert(nDimensions!(float[][]) == 2);
539 }
540
541 /++
542 Returns a new array of type $(D T) allocated on the garbage collected heap
543 without initializing its elements. This can be a useful optimization if every
544 element will be immediately initialized. $(D T) may be a multidimensional
545 array. In this case sizes may be specified for any number of dimensions from 0
546 to the number in $(D T).
547
548 uninitializedArray is nothrow and weakly pure.
549
550 uninitializedArray is @system if the uninitialized element type has pointers.
551 +/
552 auto uninitializedArray(T, I...)(I sizes) nothrow @system
553 if (isDynamicArray!T && allSatisfy!(isIntegral, I) && hasIndirections!(ElementEncodingType!T))
554 {
555 enum isSize_t(E) = is (E : size_t);
556 alias toSize_t(E) = size_t;
557
558 static assert(allSatisfy!(isSize_t, I),
559 "Argument types in "~I.stringof~" are not all convertible to size_t: "
560 ~Filter!(templateNot!(isSize_t), I).stringof);
561
562 //Eagerlly transform non-size_t into size_t to avoid template bloat
563 alias ST = staticMap!(toSize_t, I);
564
565 return arrayAllocImpl!(false, T, ST)(sizes);
566 }
567
568 /// ditto
569 auto uninitializedArray(T, I...)(I sizes) nothrow @trusted
570 if (isDynamicArray!T && allSatisfy!(isIntegral, I) && !hasIndirections!(ElementEncodingType!T))
571 {
572 enum isSize_t(E) = is (E : size_t);
573 alias toSize_t(E) = size_t;
574
575 static assert(allSatisfy!(isSize_t, I),
576 "Argument types in "~I.stringof~" are not all convertible to size_t: "
577 ~Filter!(templateNot!(isSize_t), I).stringof);
578
579 //Eagerlly transform non-size_t into size_t to avoid template bloat
580 alias ST = staticMap!(toSize_t, I);
581
582 return arrayAllocImpl!(false, T, ST)(sizes);
583 }
584 ///
585 @system nothrow pure unittest
586 {
587 double[] arr = uninitializedArray!(double[])(100);
588 assert(arr.length == 100);
589
590 double[][] matrix = uninitializedArray!(double[][])(42, 31);
591 assert(matrix.length == 42);
592 assert(matrix[0].length == 31);
593
594 char*[] ptrs = uninitializedArray!(char*[])(100);
595 assert(ptrs.length == 100);
596 }
597
598 /++
599 Returns a new array of type $(D T) allocated on the garbage collected heap.
600
601 Partial initialization is done for types with indirections, for preservation
602 of memory safety. Note that elements will only be initialized to 0, but not
603 necessarily the element type's $(D .init).
604
605 minimallyInitializedArray is nothrow and weakly pure.
606 +/
607 auto minimallyInitializedArray(T, I...)(I sizes) nothrow @trusted
608 if (isDynamicArray!T && allSatisfy!(isIntegral, I))
609 {
610 enum isSize_t(E) = is (E : size_t);
611 alias toSize_t(E) = size_t;
612
613 static assert(allSatisfy!(isSize_t, I),
614 "Argument types in "~I.stringof~" are not all convertible to size_t: "
615 ~Filter!(templateNot!(isSize_t), I).stringof);
616 //Eagerlly transform non-size_t into size_t to avoid template bloat
617 alias ST = staticMap!(toSize_t, I);
618
619 return arrayAllocImpl!(true, T, ST)(sizes);
620 }
621
622 ///
623 @safe pure nothrow unittest
624 {
625 import std.algorithm.comparison : equal;
626 import std.range : repeat;
627
628 auto arr = minimallyInitializedArray!(int[])(42);
629 assert(arr.length == 42);
630 // Elements aren't necessarily initialized to 0
631 assert(!arr.equal(0.repeat(42)));
632 }
633
634 @safe pure nothrow unittest
635 {
636 cast(void) minimallyInitializedArray!(int[][][][][])();
637 double[] arr = minimallyInitializedArray!(double[])(100);
638 assert(arr.length == 100);
639
640 double[][] matrix = minimallyInitializedArray!(double[][])(42);
641 assert(matrix.length == 42);
foreach(elem;matrix)642 foreach (elem; matrix)
643 {
644 assert(elem.ptr is null);
645 }
646 }
647
arrayAllocImpl(bool minimallyInitialized,T,I...)648 private auto arrayAllocImpl(bool minimallyInitialized, T, I...)(I sizes) nothrow
649 {
650 static assert(I.length <= nDimensions!T,
651 I.length.stringof~"dimensions specified for a "~nDimensions!T.stringof~" dimensional array.");
652
653 alias E = ElementEncodingType!T;
654
655 E[] ret;
656
657 static if (I.length != 0)
658 {
659 static assert(is(I[0] == size_t));
660 alias size = sizes[0];
661 }
662
663 static if (I.length == 1)
664 {
665 if (__ctfe)
666 {
667 static if (__traits(compiles, new E[](size)))
668 ret = new E[](size);
669 else static if (__traits(compiles, ret ~= E.init))
670 {
671 try
672 {
673 //Issue: if E has an impure postblit, then all of arrayAllocImpl
674 //Will be impure, even during non CTFE.
675 foreach (i; 0 .. size)
676 ret ~= E.init;
677 }
678 catch (Exception e)
679 throw new Error(e.msg);
680 }
681 else
682 assert(0, "No postblit nor default init on " ~ E.stringof ~
683 ": At least one is required for CTFE.");
684 }
685 else
686 {
687 import core.memory : GC;
688 import core.stdc.string : memset;
689
690 import core.checkedint : mulu;
691 bool overflow;
692 const nbytes = mulu(size, E.sizeof, overflow);
693 if (overflow) assert(0);
694
695 auto ptr = cast(E*) GC.malloc(nbytes, blockAttribute!E);
696 static if (minimallyInitialized && hasIndirections!E)
697 memset(ptr, 0, nbytes);
698 ret = ptr[0 .. size];
699 }
700 }
701 else static if (I.length > 1)
702 {
703 ret = arrayAllocImpl!(false, E[])(size);
704 foreach (ref elem; ret)
705 elem = arrayAllocImpl!(minimallyInitialized, E)(sizes[1..$]);
706 }
707
708 return ret;
709 }
710
711 @safe nothrow pure unittest
712 {
713 auto s1 = uninitializedArray!(int[])();
714 auto s2 = minimallyInitializedArray!(int[])();
715 assert(s1.length == 0);
716 assert(s2.length == 0);
717 }
718
719 @safe nothrow pure unittest //@@@9803@@@
720 {
721 auto a = minimallyInitializedArray!(int*[])(1);
722 assert(a[0] == null);
723 auto b = minimallyInitializedArray!(int[][])(1);
724 assert(b[0].empty);
725 auto c = minimallyInitializedArray!(int*[][])(1, 1);
726 assert(c[0][0] == null);
727 }
728
729 @safe unittest //@@@10637@@@
730 {
731 static struct S
732 {
733 static struct I{int i; alias i this;}
734 int* p;
735 this() @disable;
thisS736 this(int i)
737 {
738 p = &(new I(i)).i;
739 }
thisS740 this(this)
741 {
742 p = &(new I(*p)).i;
743 }
~thisS744 ~this()
745 {
746 assert(p != null);
747 }
748 }
749 auto a = minimallyInitializedArray!(S[])(1);
750 assert(a[0].p == null);
751 enum b = minimallyInitializedArray!(S[])(1);
752 }
753
754 @safe nothrow unittest
755 {
756 static struct S1
757 {
758 this() @disable;
759 this(this) @disable;
760 }
761 auto a1 = minimallyInitializedArray!(S1[][])(2, 2);
762 //enum b1 = minimallyInitializedArray!(S1[][])(2, 2);
763 static struct S2
764 {
765 this() @disable;
766 //this(this) @disable;
767 }
768 auto a2 = minimallyInitializedArray!(S2[][])(2, 2);
769 enum b2 = minimallyInitializedArray!(S2[][])(2, 2);
770 static struct S3
771 {
772 //this() @disable;
773 this(this) @disable;
774 }
775 auto a3 = minimallyInitializedArray!(S3[][])(2, 2);
776 enum b3 = minimallyInitializedArray!(S3[][])(2, 2);
777 }
778
779 // overlap
780 /*
781 NOTE: Undocumented for now, overlap does not yet work with ctfe.
782 Returns the overlapping portion, if any, of two arrays. Unlike $(D
783 equal), $(D overlap) only compares the pointers in the ranges, not the
784 values referred by them. If $(D r1) and $(D r2) have an overlapping
785 slice, returns that slice. Otherwise, returns the null slice.
786 */
787 auto overlap(T, U)(T[] r1, U[] r2) @trusted pure nothrow
788 if (is(typeof(r1.ptr < r2.ptr) == bool))
789 {
790 import std.algorithm.comparison : min, max;
791 auto b = max(r1.ptr, r2.ptr);
792 auto e = min(r1.ptr + r1.length, r2.ptr + r2.length);
793 return b < e ? b[0 .. e - b] : null;
794 }
795
796 ///
797 @safe pure /*nothrow*/ unittest
798 {
799 int[] a = [ 10, 11, 12, 13, 14 ];
800 int[] b = a[1 .. 3];
801 assert(overlap(a, b) == [ 11, 12 ]);
802 b = b.dup;
803 // overlap disappears even though the content is the same
804 assert(overlap(a, b).empty);
805 }
806
807 @safe /*nothrow*/ unittest
808 {
test(L,R)809 static void test(L, R)(L l, R r)
810 {
811 import std.stdio;
812 scope(failure) writeln("Types: L %s R %s", L.stringof, R.stringof);
813
814 assert(overlap(l, r) == [ 100, 12 ]);
815
816 assert(overlap(l, l[0 .. 2]) is l[0 .. 2]);
817 assert(overlap(l, l[3 .. 5]) is l[3 .. 5]);
818 assert(overlap(l[0 .. 2], l) is l[0 .. 2]);
819 assert(overlap(l[3 .. 5], l) is l[3 .. 5]);
820 }
821
822 int[] a = [ 10, 11, 12, 13, 14 ];
823 int[] b = a[1 .. 3];
824 a[1] = 100;
825
826 immutable int[] c = a.idup;
827 immutable int[] d = c[1 .. 3];
828
829 test(a, b);
830 assert(overlap(a, b.dup).empty);
831 test(c, d);
832 assert(overlap(c, d.idup).empty);
833 }
834
835 @safe pure nothrow unittest // bugzilla 9836
836 {
837 // range primitives for array should work with alias this types
838 struct Wrapper
839 {
840 int[] data;
841 alias data this;
842
saveWrapper843 @property Wrapper save() { return this; }
844 }
845 auto w = Wrapper([1,2,3,4]);
846 std.array.popFront(w); // should work
847
848 static assert(isInputRange!Wrapper);
849 static assert(isForwardRange!Wrapper);
850 static assert(isBidirectionalRange!Wrapper);
851 static assert(isRandomAccessRange!Wrapper);
852 }
853
copyBackwards(T)854 private void copyBackwards(T)(T[] src, T[] dest)
855 {
856 import core.stdc.string : memmove;
857
858 assert(src.length == dest.length);
859
860 if (!__ctfe || hasElaborateCopyConstructor!T)
861 {
862 /* insertInPlace relies on dest being uninitialized, so no postblits allowed,
863 * as this is a MOVE that overwrites the destination, not a COPY.
864 * BUG: insertInPlace will not work with ctfe and postblits
865 */
866 memmove(dest.ptr, src.ptr, src.length * T.sizeof);
867 }
868 else
869 {
870 immutable len = src.length;
871 for (size_t i = len; i-- > 0;)
872 {
873 dest[i] = src[i];
874 }
875 }
876 }
877
878 /++
879 Inserts $(D stuff) (which must be an input range or any number of
880 implicitly convertible items) in $(D array) at position $(D pos).
881
882 Params:
883 array = The array that $(D stuff) will be inserted into.
884 pos = The position in $(D array) to insert the $(D stuff).
885 stuff = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives),
886 or any number of implicitly convertible items to insert into $(D array).
887 +/
888 void insertInPlace(T, U...)(ref T[] array, size_t pos, U stuff)
889 if (!isSomeString!(T[])
890 && allSatisfy!(isInputRangeOrConvertible!T, U) && U.length > 0)
891 {
892 static if (allSatisfy!(isInputRangeWithLengthOrConvertible!T, U))
893 {
894 import std.conv : emplaceRef;
895
896 immutable oldLen = array.length;
897
898 size_t to_insert = 0;
foreach(i,E;U)899 foreach (i, E; U)
900 {
901 static if (is(E : T)) //a single convertible value, not a range
902 to_insert += 1;
903 else
904 to_insert += stuff[i].length;
905 }
906 if (to_insert)
907 {
908 array.length += to_insert;
909
910 // Takes arguments array, pos, stuff
911 // Spread apart array[] at pos by moving elements
912 (() @trusted { copyBackwards(array[pos .. oldLen], array[pos+to_insert..$]); })();
913
914 // Initialize array[pos .. pos+to_insert] with stuff[]
915 auto j = 0;
foreach(i,E;U)916 foreach (i, E; U)
917 {
918 static if (is(E : T))
919 {
920 emplaceRef!T(array[pos + j++], stuff[i]);
921 }
922 else
923 {
924 foreach (v; stuff[i])
925 {
926 emplaceRef!T(array[pos + j++], v);
927 }
928 }
929 }
930 }
931 }
932 else
933 {
934 // stuff has some InputRanges in it that don't have length
935 // assume that stuff to be inserted is typically shorter
936 // then the array that can be arbitrary big
937 // TODO: needs a better implementation as there is no need to build an _array_
938 // a singly-linked list of memory blocks (rope, etc.) will do
939 auto app = appender!(T[])();
940 foreach (i, E; U)
941 app.put(stuff[i]);
942 insertInPlace(array, pos, app.data);
943 }
944 }
945
946 /// Ditto
947 void insertInPlace(T, U...)(ref T[] array, size_t pos, U stuff)
948 if (isSomeString!(T[]) && allSatisfy!(isCharOrStringOrDcharRange, U))
949 {
950 static if (is(Unqual!T == T)
951 && allSatisfy!(isInputRangeWithLengthOrConvertible!dchar, U))
952 {
953 import std.utf : codeLength;
954 // mutable, can do in place
955 //helper function: re-encode dchar to Ts and store at *ptr
putDChar(T * ptr,dchar ch)956 static T* putDChar(T* ptr, dchar ch)
957 {
958 static if (is(T == dchar))
959 {
960 *ptr++ = ch;
961 return ptr;
962 }
963 else
964 {
965 import std.utf : encode;
966 T[dchar.sizeof/T.sizeof] buf;
967 immutable len = encode(buf, ch);
968 final switch (len)
969 {
970 static if (T.sizeof == char.sizeof)
971 {
972 case 4:
973 ptr[3] = buf[3];
974 goto case;
975 case 3:
976 ptr[2] = buf[2];
977 goto case;
978 }
979 case 2:
980 ptr[1] = buf[1];
981 goto case;
982 case 1:
983 ptr[0] = buf[0];
984 }
985 ptr += len;
986 return ptr;
987 }
988 }
989 size_t to_insert = 0;
990 //count up the number of *codeunits* to insert
991 foreach (i, E; U)
992 to_insert += codeLength!T(stuff[i]);
993 array.length += to_insert;
994
moveToRight(T[]arr,size_t gap)995 @trusted static void moveToRight(T[] arr, size_t gap)
996 {
997 static assert(!hasElaborateCopyConstructor!T);
998 import core.stdc.string : memmove;
999 if (__ctfe)
1000 {
1001 for (size_t i = arr.length - gap; i; --i)
1002 arr[gap + i - 1] = arr[i - 1];
1003 }
1004 else
1005 memmove(arr.ptr + gap, arr.ptr, (arr.length - gap) * T.sizeof);
1006 }
1007 moveToRight(array[pos .. $], to_insert);
1008 auto ptr = array.ptr + pos;
foreach(i,E;U)1009 foreach (i, E; U)
1010 {
1011 static if (is(E : dchar))
1012 {
1013 ptr = putDChar(ptr, stuff[i]);
1014 }
1015 else
1016 {
1017 foreach (dchar ch; stuff[i])
1018 ptr = putDChar(ptr, ch);
1019 }
1020 }
1021 assert(ptr == array.ptr + pos + to_insert, "(ptr == array.ptr + pos + to_insert) is false");
1022 }
1023 else
1024 {
1025 // immutable/const, just construct a new array
1026 auto app = appender!(T[])();
1027 app.put(array[0 .. pos]);
1028 foreach (i, E; U)
1029 app.put(stuff[i]);
1030 app.put(array[pos..$]);
1031 array = app.data;
1032 }
1033 }
1034
1035 ///
1036 @safe pure unittest
1037 {
1038 int[] a = [ 1, 2, 3, 4 ];
1039 a.insertInPlace(2, [ 1, 2 ]);
1040 assert(a == [ 1, 2, 1, 2, 3, 4 ]);
1041 a.insertInPlace(3, 10u, 11);
1042 assert(a == [ 1, 2, 1, 10, 11, 2, 3, 4]);
1043 }
1044
1045 //constraint helpers
isInputRangeWithLengthOrConvertible(E)1046 private template isInputRangeWithLengthOrConvertible(E)
1047 {
1048 template isInputRangeWithLengthOrConvertible(R)
1049 {
1050 //hasLength not defined for char[], wchar[] and dchar[]
1051 enum isInputRangeWithLengthOrConvertible =
1052 (isInputRange!R && is(typeof(R.init.length))
1053 && is(ElementType!R : E)) || is(R : E);
1054 }
1055 }
1056
1057 //ditto
isCharOrStringOrDcharRange(T)1058 private template isCharOrStringOrDcharRange(T)
1059 {
1060 enum isCharOrStringOrDcharRange = isSomeString!T || isSomeChar!T ||
1061 (isInputRange!T && is(ElementType!T : dchar));
1062 }
1063
1064 //ditto
isInputRangeOrConvertible(E)1065 private template isInputRangeOrConvertible(E)
1066 {
1067 template isInputRangeOrConvertible(R)
1068 {
1069 enum isInputRangeOrConvertible =
1070 (isInputRange!R && is(ElementType!R : E)) || is(R : E);
1071 }
1072 }
1073
1074 @system unittest
1075 {
1076 // @system due to insertInPlace
1077 import core.exception;
1078 import std.algorithm.comparison : equal;
1079 import std.algorithm.iteration : filter;
1080 import std.conv : to;
1081 import std.exception;
1082
1083
test(T,U,V)1084 bool test(T, U, V)(T orig, size_t pos, U toInsert, V result,
1085 string file = __FILE__, size_t line = __LINE__)
1086 {
1087 {
1088 static if (is(T == typeof(T.init.dup)))
1089 auto a = orig.dup;
1090 else
1091 auto a = orig.idup;
1092
1093 a.insertInPlace(pos, toInsert);
1094 if (!equal(a, result))
1095 return false;
1096 }
1097
1098 static if (isInputRange!U)
1099 {
1100 orig.insertInPlace(pos, filter!"true"(toInsert));
1101 return equal(orig, result);
1102 }
1103 else
1104 return true;
1105 }
1106
1107
1108 assert(test([1, 2, 3, 4], 0, [6, 7], [6, 7, 1, 2, 3, 4]));
1109 assert(test([1, 2, 3, 4], 2, [8, 9], [1, 2, 8, 9, 3, 4]));
1110 assert(test([1, 2, 3, 4], 4, [10, 11], [1, 2, 3, 4, 10, 11]));
1111
1112 assert(test([1, 2, 3, 4], 0, 22, [22, 1, 2, 3, 4]));
1113 assert(test([1, 2, 3, 4], 2, 23, [1, 2, 23, 3, 4]));
1114 assert(test([1, 2, 3, 4], 4, 24, [1, 2, 3, 4, 24]));
1115
testStr(T,U)1116 void testStr(T, U)(string file = __FILE__, size_t line = __LINE__)
1117 {
1118
1119 auto l = to!T("hello");
1120 auto r = to!U(" વિશ્વ");
1121
1122 enforce(test(l, 0, r, " વિશ્વhello"),
1123 new AssertError("testStr failure 1", file, line));
1124 enforce(test(l, 3, r, "hel વિશ્વlo"),
1125 new AssertError("testStr failure 2", file, line));
1126 enforce(test(l, l.length, r, "hello વિશ્વ"),
1127 new AssertError("testStr failure 3", file, line));
1128 }
1129
1130 foreach (T; AliasSeq!(char, wchar, dchar,
1131 immutable(char), immutable(wchar), immutable(dchar)))
1132 {
1133 foreach (U; AliasSeq!(char, wchar, dchar,
1134 immutable(char), immutable(wchar), immutable(dchar)))
1135 {
1136 testStr!(T[], U[])();
1137 }
1138
1139 }
1140
1141 // variadic version
testVar(T,U...)1142 bool testVar(T, U...)(T orig, size_t pos, U args)
1143 {
1144 static if (is(T == typeof(T.init.dup)))
1145 auto a = orig.dup;
1146 else
1147 auto a = orig.idup;
1148 auto result = args[$-1];
1149
1150 a.insertInPlace(pos, args[0..$-1]);
1151 if (!equal(a, result))
1152 return false;
1153 return true;
1154 }
1155 assert(testVar([1, 2, 3, 4], 0, 6, 7u, [6, 7, 1, 2, 3, 4]));
1156 assert(testVar([1L, 2, 3, 4], 2, 8, 9L, [1, 2, 8, 9, 3, 4]));
1157 assert(testVar([1L, 2, 3, 4], 4, 10L, 11, [1, 2, 3, 4, 10, 11]));
1158 assert(testVar([1L, 2, 3, 4], 4, [10, 11], 40L, 42L,
1159 [1, 2, 3, 4, 10, 11, 40, 42]));
1160 assert(testVar([1L, 2, 3, 4], 4, 10, 11, [40L, 42],
1161 [1, 2, 3, 4, 10, 11, 40, 42]));
1162 assert(testVar("t".idup, 1, 'e', 's', 't', "test"));
1163 assert(testVar("!!"w.idup, 1, "\u00e9ll\u00f4", 'x', "TTT"w, 'y',
1164 "!\u00e9ll\u00f4xTTTy!"));
1165 assert(testVar("flipflop"d.idup, 4, '_',
1166 "xyz"w, '\U00010143', '_', "abc"d, "__",
1167 "flip_xyz\U00010143_abc__flop"));
1168 }
1169
1170 @system unittest
1171 {
1172 import std.algorithm.comparison : equal;
1173 // insertInPlace interop with postblit
1174 static struct Int
1175 {
1176 int* payload;
thisInt1177 this(int k)
1178 {
1179 payload = new int;
1180 *payload = k;
1181 }
thisInt1182 this(this)
1183 {
1184 int* np = new int;
1185 *np = *payload;
1186 payload = np;
1187 }
~thisInt1188 ~this()
1189 {
1190 if (payload)
1191 *payload = 0; //'destroy' it
1192 }
getPayloadInt1193 @property int getPayload(){ return *payload; }
1194 alias getPayload this;
1195 }
1196
1197 Int[] arr = [Int(1), Int(4), Int(5)];
1198 assert(arr[0] == 1);
1199 insertInPlace(arr, 1, Int(2), Int(3));
1200 assert(equal(arr, [1, 2, 3, 4, 5])); //check it works with postblit
1201
version(none)1202 version (none) // illustrates that insertInPlace() will not work with CTFE and postblit
1203 {
1204 static bool testctfe()
1205 {
1206 Int[] arr = [Int(1), Int(4), Int(5)];
1207 assert(arr[0] == 1);
1208 insertInPlace(arr, 1, Int(2), Int(3));
1209 return equal(arr, [1, 2, 3, 4, 5]); //check it works with postblit
1210 }
1211 enum E = testctfe();
1212 }
1213 }
1214
1215 @safe unittest
1216 {
1217 import std.exception;
1218 assertCTFEable!(
1219 {
1220 int[] a = [1, 2];
1221 a.insertInPlace(2, 3);
1222 a.insertInPlace(0, -1, 0);
1223 return a == [-1, 0, 1, 2, 3];
1224 });
1225 }
1226
1227 @system unittest // bugzilla 6874
1228 {
1229 import core.memory;
1230 // allocate some space
1231 byte[] a;
1232 a.length = 1;
1233
1234 // fill it
1235 a.length = a.capacity;
1236
1237 // write beyond
1238 byte[] b = a[$ .. $];
1239 b.insertInPlace(0, a);
1240
1241 // make sure that reallocation has happened
1242 assert(GC.addrOf(&b[0]) == GC.addrOf(&b[$-1]));
1243 }
1244
1245
1246 /++
1247 Returns whether the $(D front)s of $(D lhs) and $(D rhs) both refer to the
1248 same place in memory, making one of the arrays a slice of the other which
1249 starts at index $(D 0).
1250 +/
1251 @safe
sameHead(T)1252 pure nothrow bool sameHead(T)(in T[] lhs, in T[] rhs)
1253 {
1254 return lhs.ptr == rhs.ptr;
1255 }
1256
1257 ///
1258 @safe pure nothrow unittest
1259 {
1260 auto a = [1, 2, 3, 4, 5];
1261 auto b = a[0 .. 2];
1262
1263 assert(a.sameHead(b));
1264 }
1265
1266
1267 /++
1268 Returns whether the $(D back)s of $(D lhs) and $(D rhs) both refer to the
1269 same place in memory, making one of the arrays a slice of the other which
1270 end at index $(D $).
1271 +/
1272 @trusted
sameTail(T)1273 pure nothrow bool sameTail(T)(in T[] lhs, in T[] rhs)
1274 {
1275 return lhs.ptr + lhs.length == rhs.ptr + rhs.length;
1276 }
1277
1278 ///
1279 @safe pure nothrow unittest
1280 {
1281 auto a = [1, 2, 3, 4, 5];
1282 auto b = a[3..$];
1283
1284 assert(a.sameTail(b));
1285 }
1286
1287 @safe pure nothrow unittest
1288 {
1289 foreach (T; AliasSeq!(int[], const(int)[], immutable(int)[], const int[], immutable int[]))
1290 {
1291 T a = [1, 2, 3, 4, 5];
1292 T b = a;
1293 T c = a[1 .. $];
1294 T d = a[0 .. 1];
1295 T e = null;
1296
1297 assert(sameHead(a, a));
1298 assert(sameHead(a, b));
1299 assert(!sameHead(a, c));
1300 assert(sameHead(a, d));
1301 assert(!sameHead(a, e));
1302
1303 assert(sameTail(a, a));
1304 assert(sameTail(a, b));
1305 assert(sameTail(a, c));
1306 assert(!sameTail(a, d));
1307 assert(!sameTail(a, e));
1308
1309 //verifies R-value compatibilty
1310 assert(a.sameHead(a[0 .. 0]));
1311 assert(a.sameTail(a[$ .. $]));
1312 }
1313 }
1314
1315 /**
1316 Params:
1317 s = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1318 or a dynamic array
1319 n = number of times to repeat `s`
1320
1321 Returns:
1322 An array that consists of `s` repeated `n` times. This function allocates, fills, and
1323 returns a new array.
1324
1325 See_Also:
1326 For a lazy version, refer to $(REF repeat, std,range).
1327 */
1328 ElementEncodingType!S[] replicate(S)(S s, size_t n)
1329 if (isDynamicArray!S)
1330 {
1331 alias RetType = ElementEncodingType!S[];
1332
1333 // Optimization for return join(std.range.repeat(s, n));
1334 if (n == 0)
1335 return RetType.init;
1336 if (n == 1)
1337 return cast(RetType) s;
1338 auto r = new Unqual!(typeof(s[0]))[n * s.length];
1339 if (s.length == 1)
1340 r[] = s[0];
1341 else
1342 {
1343 immutable len = s.length, nlen = n * len;
1344 for (size_t i = 0; i < nlen; i += len)
1345 {
1346 r[i .. i + len] = s[];
1347 }
1348 }
1349 return r;
1350 }
1351
1352 /// ditto
1353 ElementType!S[] replicate(S)(S s, size_t n)
1354 if (isInputRange!S && !isDynamicArray!S)
1355 {
1356 import std.range : repeat;
1357 return join(std.range.repeat(s, n));
1358 }
1359
1360
1361 ///
1362 @safe unittest
1363 {
1364 auto a = "abc";
1365 auto s = replicate(a, 3);
1366
1367 assert(s == "abcabcabc");
1368
1369 auto b = [1, 2, 3];
1370 auto c = replicate(b, 3);
1371
1372 assert(c == [1, 2, 3, 1, 2, 3, 1, 2, 3]);
1373
1374 auto d = replicate(b, 0);
1375
1376 assert(d == []);
1377 }
1378
1379 @safe unittest
1380 {
1381 import std.conv : to;
1382
1383 foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[]))
1384 {
1385 S s;
1386 immutable S t = "abc";
1387
1388 assert(replicate(to!S("1234"), 0) is null);
1389 assert(replicate(to!S("1234"), 0) is null);
1390 assert(replicate(to!S("1234"), 1) == "1234");
1391 assert(replicate(to!S("1234"), 2) == "12341234");
1392 assert(replicate(to!S("1"), 4) == "1111");
1393 assert(replicate(t, 3) == "abcabcabc");
1394 assert(replicate(cast(S) null, 4) is null);
1395 }
1396 }
1397
1398 /++
1399 Eagerly split the string $(D s) into an array of words, using whitespace as
1400 delimiter. Runs of whitespace are merged together (no empty words are produced).
1401
1402 $(D @safe), $(D pure) and $(D CTFE)-able.
1403
1404 Params:
1405 s = the string to split
1406
1407 Returns:
1408 An array of each word in `s`
1409
1410 See_Also:
1411 $(REF splitter, std,algorithm,iteration) for a version that splits using any
1412 separator.
1413
1414 $(REF splitter, std,regex) for a version that splits using a regular
1415 expression defined separator.
1416 +/
1417 S[] split(S)(S s) @safe pure
1418 if (isSomeString!S)
1419 {
1420 size_t istart;
1421 bool inword = false;
1422 S[] result;
1423
foreach(i,dchar c;s)1424 foreach (i, dchar c ; s)
1425 {
1426 import std.uni : isWhite;
1427 if (isWhite(c))
1428 {
1429 if (inword)
1430 {
1431 result ~= s[istart .. i];
1432 inword = false;
1433 }
1434 }
1435 else
1436 {
1437 if (!inword)
1438 {
1439 istart = i;
1440 inword = true;
1441 }
1442 }
1443 }
1444 if (inword)
1445 result ~= s[istart .. $];
1446 return result;
1447 }
1448
1449 ///
1450 @safe unittest
1451 {
1452 string str = "Hello World!";
1453 assert(str.split == ["Hello", "World!"]);
1454
1455 string str2 = "Hello\t\tWorld\t!";
1456 assert(str2.split == ["Hello", "World", "!"]);
1457 }
1458
1459 /**
1460 * `split` allocates memory, so the same effect can be achieved lazily
1461 * using $(REF splitter, std,algorithm,iteration).
1462 */
1463 @safe unittest
1464 {
1465 import std.ascii : isWhite;
1466 import std.algorithm.comparison : equal;
1467 import std.algorithm.iteration : splitter;
1468
1469 string str = "Hello World!";
1470 assert(str.splitter!(isWhite).equal(["Hello", "World!"]));
1471 }
1472
1473 @safe unittest
1474 {
1475 import std.conv : to;
1476 import std.format;
1477 import std.typecons;
1478
makeEntry(S)1479 static auto makeEntry(S)(string l, string[] r)
1480 {return tuple(l.to!S(), r.to!(S[])());}
1481
1482 foreach (S; AliasSeq!(string, wstring, dstring,))
1483 {
1484 auto entries =
1485 [
1486 makeEntry!S("", []),
1487 makeEntry!S(" ", []),
1488 makeEntry!S("hello", ["hello"]),
1489 makeEntry!S(" hello ", ["hello"]),
1490 makeEntry!S(" h e l l o ", ["h", "e", "l", "l", "o"]),
1491 makeEntry!S("peter\t\npaul\rjerry", ["peter", "paul", "jerry"]),
1492 makeEntry!S(" \t\npeter paul\tjerry \n", ["peter", "paul", "jerry"]),
1493 makeEntry!S("\u2000日\u202F本\u205F語\u3000", ["日", "本", "語"]),
1494 makeEntry!S(" 哈・郎博尔德} ___一个", ["哈・郎博尔德}", "___一个"])
1495 ];
1496 foreach (entry; entries)
1497 assert(entry[0].split() == entry[1], format("got: %s, expected: %s.", entry[0].split(), entry[1]));
1498 }
1499
1500 //Just to test that an immutable is split-able
1501 immutable string s = " \t\npeter paul\tjerry \n";
1502 assert(split(s) == ["peter", "paul", "jerry"]);
1503 }
1504
1505 @safe unittest //purity, ctfe ...
1506 {
1507 import std.exception;
dg()1508 void dg() @safe pure {
1509 assert(split("hello world"c) == ["hello"c, "world"c]);
1510 assert(split("hello world"w) == ["hello"w, "world"w]);
1511 assert(split("hello world"d) == ["hello"d, "world"d]);
1512 }
1513 dg();
1514 assertCTFEable!dg;
1515 }
1516
1517 ///
1518 @safe unittest
1519 {
1520 assert(split("hello world") == ["hello","world"]);
1521 assert(split("192.168.0.1", ".") == ["192", "168", "0", "1"]);
1522
1523 auto a = split([1, 2, 3, 4, 5, 1, 2, 3, 4, 5], [2, 3]);
1524 assert(a == [[1], [4, 5, 1], [4, 5]]);
1525 }
1526
1527 /++
1528 Eagerly splits $(D range) into an array, using $(D sep) as the delimiter.
1529
1530 The _range must be a
1531 $(REF_ALTTEXT forward _range, isForwardRange, std,_range,primitives).
1532 The separator can be a value of the same type as the elements in $(D range)
1533 or it can be another forward _range.
1534
1535 Example:
1536 If $(D range) is a $(D string), $(D sep) can be a $(D char) or another
1537 $(D string). The return type will be an array of strings. If $(D range) is
1538 an $(D int) array, $(D sep) can be an $(D int) or another $(D int) array.
1539 The return type will be an array of $(D int) arrays.
1540
1541 Params:
1542 range = a forward _range.
1543 sep = a value of the same type as the elements of $(D range) or another
1544 forward range.
1545
1546 Returns:
1547 An array containing the divided parts of $(D range).
1548
1549 See_Also:
1550 $(REF splitter, std,algorithm,iteration) for the lazy version of this
1551 function.
1552 +/
1553 auto split(Range, Separator)(Range range, Separator sep)
1554 if (isForwardRange!Range && is(typeof(ElementType!Range.init == Separator.init)))
1555 {
1556 import std.algorithm.iteration : splitter;
1557 return range.splitter(sep).array;
1558 }
1559 ///ditto
1560 auto split(Range, Separator)(Range range, Separator sep)
1561 if (
1562 isForwardRange!Range && isForwardRange!Separator
1563 && is(typeof(ElementType!Range.init == ElementType!Separator.init)))
1564 {
1565 import std.algorithm.iteration : splitter;
1566 return range.splitter(sep).array;
1567 }
1568 ///ditto
1569 auto split(alias isTerminator, Range)(Range range)
1570 if (isForwardRange!Range && is(typeof(unaryFun!isTerminator(range.front))))
1571 {
1572 import std.algorithm.iteration : splitter;
1573 return range.splitter!isTerminator.array;
1574 }
1575
1576 ///
1577 @safe unittest
1578 {
1579 import std.uni : isWhite;
1580 assert("Learning,D,is,fun".split(",") == ["Learning", "D", "is", "fun"]);
1581 assert("Learning D is fun".split!isWhite == ["Learning", "D", "is", "fun"]);
1582 assert("Learning D is fun".split(" D ") == ["Learning", "is fun"]);
1583 }
1584
1585 @safe unittest
1586 {
1587 import std.algorithm.comparison : cmp;
1588 import std.conv;
1589
1590 foreach (S; AliasSeq!(string, wstring, dstring,
1591 immutable(string), immutable(wstring), immutable(dstring),
1592 char[], wchar[], dchar[],
1593 const(char)[], const(wchar)[], const(dchar)[],
1594 const(char[]), immutable(char[])))
1595 {
1596 S s = to!S(",peter,paul,jerry,");
1597
1598 auto words = split(s, ",");
1599 assert(words.length == 5, text(words.length));
1600 assert(cmp(words[0], "") == 0);
1601 assert(cmp(words[1], "peter") == 0);
1602 assert(cmp(words[2], "paul") == 0);
1603 assert(cmp(words[3], "jerry") == 0);
1604 assert(cmp(words[4], "") == 0);
1605
1606 auto s1 = s[0 .. s.length - 1]; // lop off trailing ','
1607 words = split(s1, ",");
1608 assert(words.length == 4);
1609 assert(cmp(words[3], "jerry") == 0);
1610
1611 auto s2 = s1[1 .. s1.length]; // lop off leading ','
1612 words = split(s2, ",");
1613 assert(words.length == 3);
1614 assert(cmp(words[0], "peter") == 0);
1615
1616 auto s3 = to!S(",,peter,,paul,,jerry,,");
1617
1618 words = split(s3, ",,");
1619 assert(words.length == 5);
1620 assert(cmp(words[0], "") == 0);
1621 assert(cmp(words[1], "peter") == 0);
1622 assert(cmp(words[2], "paul") == 0);
1623 assert(cmp(words[3], "jerry") == 0);
1624 assert(cmp(words[4], "") == 0);
1625
1626 auto s4 = s3[0 .. s3.length - 2]; // lop off trailing ',,'
1627 words = split(s4, ",,");
1628 assert(words.length == 4);
1629 assert(cmp(words[3], "jerry") == 0);
1630
1631 auto s5 = s4[2 .. s4.length]; // lop off leading ',,'
1632 words = split(s5, ",,");
1633 assert(words.length == 3);
1634 assert(cmp(words[0], "peter") == 0);
1635 }
1636 }
1637
1638 /++
1639 Conservative heuristic to determine if a range can be iterated cheaply.
1640 Used by $(D join) in decision to do an extra iteration of the range to
1641 compute the resultant length. If iteration is not cheap then precomputing
1642 length could be more expensive than using $(D Appender).
1643
1644 For now, we only assume arrays are cheap to iterate.
1645 +/
1646 private enum bool hasCheapIteration(R) = isArray!R;
1647
1648 /++
1649 Eagerly concatenates all of the ranges in `ror` together (with the GC)
1650 into one array using `sep` as the separator if present.
1651
1652 Params:
1653 ror = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
1654 of input ranges
1655 sep = An input range, or a single element, to join the ranges on
1656
1657 Returns:
1658 An array of elements
1659
1660 See_Also:
1661 For a lazy version, see $(REF joiner, std,algorithm,iteration)
1662 +/
1663 ElementEncodingType!(ElementType!RoR)[] join(RoR, R)(RoR ror, scope R sep)
1664 if (isInputRange!RoR &&
1665 isInputRange!(Unqual!(ElementType!RoR)) &&
1666 isInputRange!R &&
1667 is(Unqual!(ElementType!(ElementType!RoR)) == Unqual!(ElementType!R)))
1668 {
1669 alias RetType = typeof(return);
1670 alias RetTypeElement = Unqual!(ElementEncodingType!RetType);
1671 alias RoRElem = ElementType!RoR;
1672
1673 if (ror.empty)
1674 return RetType.init;
1675
1676 // Constraint only requires input range for sep.
1677 // This converts sep to an array (forward range) if it isn't one,
1678 // and makes sure it has the same string encoding for string types.
1679 static if (isSomeString!RetType &&
1680 !is(RetTypeElement == Unqual!(ElementEncodingType!R)))
1681 {
1682 import std.conv : to;
1683 auto sepArr = to!RetType(sep);
1684 }
1685 else static if (!isArray!R)
1686 auto sepArr = array(sep);
1687 else
1688 alias sepArr = sep;
1689
1690 static if (hasCheapIteration!RoR && (hasLength!RoRElem || isNarrowString!RoRElem))
1691 {
1692 import std.conv : emplaceRef;
1693 size_t length; // length of result array
1694 size_t rorLength; // length of range ror
1695 foreach (r; ror.save)
1696 {
1697 length += r.length;
1698 ++rorLength;
1699 }
1700 if (!rorLength)
1701 return null;
1702 length += (rorLength - 1) * sepArr.length;
1703
1704 auto result = (() @trusted => uninitializedArray!(RetTypeElement[])(length))();
1705 size_t len;
1706 foreach (e; ror.front)
1707 emplaceRef(result[len++], e);
1708 ror.popFront();
foreach(r;ror)1709 foreach (r; ror)
1710 {
1711 foreach (e; sepArr)
1712 emplaceRef(result[len++], e);
1713 foreach (e; r)
1714 emplaceRef(result[len++], e);
1715 }
1716 assert(len == result.length);
1717 return (() @trusted => cast(RetType) result)();
1718 }
1719 else
1720 {
1721 auto result = appender!RetType();
1722 put(result, ror.front);
1723 ror.popFront();
1724 for (; !ror.empty; ror.popFront())
1725 {
1726 put(result, sep);
1727 put(result, ror.front);
1728 }
1729 return result.data;
1730 }
1731 }
1732
1733 @safe unittest // Issue 14230
1734 {
1735 string[] ary = ["","aa","bb","cc"]; // leaded by _empty_ element
1736 assert(ary.join(" @") == " @aa @bb @cc"); // OK in 2.067b1 and olders
1737 }
1738
1739 /// Ditto
1740 ElementEncodingType!(ElementType!RoR)[] join(RoR, E)(RoR ror, scope E sep)
1741 if (isInputRange!RoR &&
1742 isInputRange!(Unqual!(ElementType!RoR)) &&
1743 is(E : ElementType!(ElementType!RoR)))
1744 {
1745 alias RetType = typeof(return);
1746 alias RetTypeElement = Unqual!(ElementEncodingType!RetType);
1747 alias RoRElem = ElementType!RoR;
1748
1749 if (ror.empty)
1750 return RetType.init;
1751
1752 static if (hasCheapIteration!RoR && (hasLength!RoRElem || isNarrowString!RoRElem))
1753 {
1754 static if (isSomeChar!E && isSomeChar!RetTypeElement && E.sizeof > RetTypeElement.sizeof)
1755 {
1756 import std.utf : encode;
1757 RetTypeElement[4 / RetTypeElement.sizeof] encodeSpace;
1758 immutable size_t sepArrLength = encode(encodeSpace, sep);
1759 return join(ror, encodeSpace[0 .. sepArrLength]);
1760 }
1761 else
1762 {
1763 import std.conv : emplaceRef;
1764 size_t length;
1765 size_t rorLength;
1766 foreach (r; ror.save)
1767 {
1768 length += r.length;
1769 ++rorLength;
1770 }
1771 if (!rorLength)
1772 return null;
1773 length += rorLength - 1;
1774 auto result = uninitializedArray!(RetTypeElement[])(length);
1775
1776
1777 size_t len;
1778 foreach (e; ror.front)
1779 emplaceRef(result[len++], e);
1780 ror.popFront();
foreach(r;ror)1781 foreach (r; ror)
1782 {
1783 emplaceRef(result[len++], sep);
1784 foreach (e; r)
1785 emplaceRef(result[len++], e);
1786 }
1787 assert(len == result.length);
1788 return (() @trusted => cast(RetType) result)();
1789 }
1790 }
1791 else
1792 {
1793 auto result = appender!RetType();
1794 put(result, ror.front);
1795 ror.popFront();
1796 for (; !ror.empty; ror.popFront())
1797 {
1798 put(result, sep);
1799 put(result, ror.front);
1800 }
1801 return result.data;
1802 }
1803 }
1804
1805 @safe unittest // Issue 10895
1806 {
1807 class A
1808 {
1809 string name;
1810 alias name this;
this(string name)1811 this(string name) { this.name = name; }
1812 }
1813 auto a = [new A(`foo`)];
1814 assert(a[0].length == 3);
1815 auto temp = join(a, " ");
1816 assert(a[0].length == 3);
1817 }
1818
1819 @safe unittest // Issue 14230
1820 {
1821 string[] ary = ["","aa","bb","cc"];
1822 assert(ary.join('@') == "@aa@bb@cc");
1823 }
1824
1825 /// Ditto
1826 ElementEncodingType!(ElementType!RoR)[] join(RoR)(RoR ror)
1827 if (isInputRange!RoR &&
1828 isInputRange!(Unqual!(ElementType!RoR)))
1829 {
1830 alias RetType = typeof(return);
1831 alias RetTypeElement = Unqual!(ElementEncodingType!RetType);
1832 alias RoRElem = ElementType!RoR;
1833
1834 if (ror.empty)
1835 return RetType.init;
1836
1837 static if (hasCheapIteration!RoR && (hasLength!RoRElem || isNarrowString!RoRElem))
1838 {
1839 import std.conv : emplaceRef;
1840 size_t length;
1841 foreach (r; ror.save)
1842 length += r.length;
1843
1844 auto result = (() @trusted => uninitializedArray!(RetTypeElement[])(length))();
1845 size_t len;
1846 foreach (r; ror)
1847 foreach (e; r)
1848 emplaceRef(result[len++], e);
1849 assert(len == result.length);
1850 return (() @trusted => cast(RetType) result)();
1851 }
1852 else
1853 {
1854 auto result = appender!RetType();
1855 for (; !ror.empty; ror.popFront())
1856 put(result, ror.front);
1857 return result.data;
1858 }
1859 }
1860
1861 ///
1862 @safe pure nothrow unittest
1863 {
1864 assert(join(["hello", "silly", "world"], " ") == "hello silly world");
1865 assert(join(["hello", "silly", "world"]) == "hellosillyworld");
1866
1867 assert(join([[1, 2, 3], [4, 5]], [72, 73]) == [1, 2, 3, 72, 73, 4, 5]);
1868 assert(join([[1, 2, 3], [4, 5]]) == [1, 2, 3, 4, 5]);
1869
1870 const string[] arr = ["apple", "banana"];
1871 assert(arr.join(",") == "apple,banana");
1872 assert(arr.join() == "applebanana");
1873 }
1874
1875 @safe pure unittest
1876 {
1877 import std.conv : to;
1878
1879 foreach (T; AliasSeq!(string,wstring,dstring))
1880 {
1881 auto arr2 = "Здравствуй Мир Unicode".to!(T);
1882 auto arr = ["Здравствуй", "Мир", "Unicode"].to!(T[]);
1883 assert(join(arr) == "ЗдравствуйМирUnicode");
1884 foreach (S; AliasSeq!(char,wchar,dchar))
1885 {
1886 auto jarr = arr.join(to!S(' '));
1887 static assert(is(typeof(jarr) == T));
1888 assert(jarr == arr2);
1889 }
1890 foreach (S; AliasSeq!(string,wstring,dstring))
1891 {
1892 auto jarr = arr.join(to!S(" "));
1893 static assert(is(typeof(jarr) == T));
1894 assert(jarr == arr2);
1895 }
1896 }
1897
1898 foreach (T; AliasSeq!(string,wstring,dstring))
1899 {
1900 auto arr2 = "Здравствуй\u047CМир\u047CUnicode".to!(T);
1901 auto arr = ["Здравствуй", "Мир", "Unicode"].to!(T[]);
1902 foreach (S; AliasSeq!(wchar,dchar))
1903 {
1904 auto jarr = arr.join(to!S('\u047C'));
1905 static assert(is(typeof(jarr) == T));
1906 assert(jarr == arr2);
1907 }
1908 }
1909
1910 const string[] arr = ["apple", "banana"];
1911 assert(arr.join(',') == "apple,banana");
1912 }
1913
1914 @system unittest
1915 {
1916 import std.algorithm;
1917 import std.conv : to;
1918 import std.range;
1919
1920 foreach (R; AliasSeq!(string, wstring, dstring))
1921 {
1922 R word1 = "日本語";
1923 R word2 = "paul";
1924 R word3 = "jerry";
1925 R[] words = [word1, word2, word3];
1926
1927 auto filteredWord1 = filter!"true"(word1);
1928 auto filteredLenWord1 = takeExactly(filteredWord1, word1.walkLength());
1929 auto filteredWord2 = filter!"true"(word2);
1930 auto filteredLenWord2 = takeExactly(filteredWord2, word2.walkLength());
1931 auto filteredWord3 = filter!"true"(word3);
1932 auto filteredLenWord3 = takeExactly(filteredWord3, word3.walkLength());
1933 auto filteredWordsArr = [filteredWord1, filteredWord2, filteredWord3];
1934 auto filteredLenWordsArr = [filteredLenWord1, filteredLenWord2, filteredLenWord3];
1935 auto filteredWords = filter!"true"(filteredWordsArr);
1936
1937 foreach (S; AliasSeq!(string, wstring, dstring))
1938 (){ // avoid slow optimizations for large functions @@@BUG@@@ 2396
1939 assert(join(filteredWords, to!S(", ")) == "日本語, paul, jerry");
1940 assert(join(filteredWords, to!(ElementType!S)(',')) == "日本語,paul,jerry");
1941 assert(join(filteredWordsArr, to!(ElementType!(S))(',')) == "日本語,paul,jerry");
1942 assert(join(filteredWordsArr, to!S(", ")) == "日本語, paul, jerry");
1943 assert(join(filteredWordsArr, to!(ElementType!(S))(',')) == "日本語,paul,jerry");
1944 assert(join(filteredLenWordsArr, to!S(", ")) == "日本語, paul, jerry");
1945 assert(join(filter!"true"(words), to!S(", ")) == "日本語, paul, jerry");
1946 assert(join(words, to!S(", ")) == "日本語, paul, jerry");
1947
1948 assert(join(filteredWords, to!S("")) == "日本語pauljerry");
1949 assert(join(filteredWordsArr, to!S("")) == "日本語pauljerry");
1950 assert(join(filteredLenWordsArr, to!S("")) == "日本語pauljerry");
1951 assert(join(filter!"true"(words), to!S("")) == "日本語pauljerry");
1952 assert(join(words, to!S("")) == "日本語pauljerry");
1953
1954 assert(join(filter!"true"([word1]), to!S(", ")) == "日本語");
1955 assert(join([filteredWord1], to!S(", ")) == "日本語");
1956 assert(join([filteredLenWord1], to!S(", ")) == "日本語");
1957 assert(join(filter!"true"([filteredWord1]), to!S(", ")) == "日本語");
1958 assert(join([word1], to!S(", ")) == "日本語");
1959
1960 assert(join(filteredWords, to!S(word1)) == "日本語日本語paul日本語jerry");
1961 assert(join(filteredWordsArr, to!S(word1)) == "日本語日本語paul日本語jerry");
1962 assert(join(filteredLenWordsArr, to!S(word1)) == "日本語日本語paul日本語jerry");
1963 assert(join(filter!"true"(words), to!S(word1)) == "日本語日本語paul日本語jerry");
1964 assert(join(words, to!S(word1)) == "日本語日本語paul日本語jerry");
1965
1966 auto filterComma = filter!"true"(to!S(", "));
1967 assert(join(filteredWords, filterComma) == "日本語, paul, jerry");
1968 assert(join(filteredWordsArr, filterComma) == "日本語, paul, jerry");
1969 assert(join(filteredLenWordsArr, filterComma) == "日本語, paul, jerry");
1970 assert(join(filter!"true"(words), filterComma) == "日本語, paul, jerry");
1971 assert(join(words, filterComma) == "日本語, paul, jerry");
1972 }();
1973
1974 assert(join(filteredWords) == "日本語pauljerry");
1975 assert(join(filteredWordsArr) == "日本語pauljerry");
1976 assert(join(filteredLenWordsArr) == "日本語pauljerry");
1977 assert(join(filter!"true"(words)) == "日本語pauljerry");
1978 assert(join(words) == "日本語pauljerry");
1979
1980 assert(join(filteredWords, filter!"true"(", ")) == "日本語, paul, jerry");
1981 assert(join(filteredWordsArr, filter!"true"(", ")) == "日本語, paul, jerry");
1982 assert(join(filteredLenWordsArr, filter!"true"(", ")) == "日本語, paul, jerry");
1983 assert(join(filter!"true"(words), filter!"true"(", ")) == "日本語, paul, jerry");
1984 assert(join(words, filter!"true"(", ")) == "日本語, paul, jerry");
1985
1986 assert(join(filter!"true"(cast(typeof(filteredWordsArr))[]), ", ").empty);
1987 assert(join(cast(typeof(filteredWordsArr))[], ", ").empty);
1988 assert(join(cast(typeof(filteredLenWordsArr))[], ", ").empty);
1989 assert(join(filter!"true"(cast(R[])[]), ", ").empty);
1990 assert(join(cast(R[])[], ", ").empty);
1991
1992 assert(join(filter!"true"(cast(typeof(filteredWordsArr))[])).empty);
1993 assert(join(cast(typeof(filteredWordsArr))[]).empty);
1994 assert(join(cast(typeof(filteredLenWordsArr))[]).empty);
1995
1996 assert(join(filter!"true"(cast(R[])[])).empty);
1997 assert(join(cast(R[])[]).empty);
1998 }
1999
2000 assert(join([[1, 2], [41, 42]], [5, 6]) == [1, 2, 5, 6, 41, 42]);
2001 assert(join([[1, 2], [41, 42]], cast(int[])[]) == [1, 2, 41, 42]);
2002 assert(join([[1, 2]], [5, 6]) == [1, 2]);
2003 assert(join(cast(int[][])[], [5, 6]).empty);
2004
2005 assert(join([[1, 2], [41, 42]]) == [1, 2, 41, 42]);
2006 assert(join(cast(int[][])[]).empty);
2007
2008 alias f = filter!"true";
2009 assert(join([[1, 2], [41, 42]], [5, 6]) == [1, 2, 5, 6, 41, 42]);
2010 assert(join(f([[1, 2], [41, 42]]), [5, 6]) == [1, 2, 5, 6, 41, 42]);
2011 assert(join([f([1, 2]), f([41, 42])], [5, 6]) == [1, 2, 5, 6, 41, 42]);
2012 assert(join(f([f([1, 2]), f([41, 42])]), [5, 6]) == [1, 2, 5, 6, 41, 42]);
2013 assert(join([[1, 2], [41, 42]], f([5, 6])) == [1, 2, 5, 6, 41, 42]);
2014 assert(join(f([[1, 2], [41, 42]]), f([5, 6])) == [1, 2, 5, 6, 41, 42]);
2015 assert(join([f([1, 2]), f([41, 42])], f([5, 6])) == [1, 2, 5, 6, 41, 42]);
2016 assert(join(f([f([1, 2]), f([41, 42])]), f([5, 6])) == [1, 2, 5, 6, 41, 42]);
2017 }
2018
2019 // Issue 10683
2020 @safe unittest
2021 {
2022 import std.range : join;
2023 import std.typecons : tuple;
2024 assert([[tuple(1)]].join == [tuple(1)]);
2025 assert([[tuple("x")]].join == [tuple("x")]);
2026 }
2027
2028 // Issue 13877
2029 @safe unittest
2030 {
2031 // Test that the range is iterated only once.
2032 import std.algorithm.iteration : map;
2033 int c = 0;
2034 auto j1 = [1, 2, 3].map!(_ => [c++]).join;
2035 assert(c == 3);
2036 assert(j1 == [0, 1, 2]);
2037
2038 c = 0;
2039 auto j2 = [1, 2, 3].map!(_ => [c++]).join(9);
2040 assert(c == 3);
2041 assert(j2 == [0, 9, 1, 9, 2]);
2042
2043 c = 0;
2044 auto j3 = [1, 2, 3].map!(_ => [c++]).join([9]);
2045 assert(c == 3);
2046 assert(j3 == [0, 9, 1, 9, 2]);
2047 }
2048
2049
2050 /++
2051 Replace occurrences of `from` with `to` in `subject` in a new
2052 array. If `sink` is defined, then output the new array into
2053 `sink`.
2054
2055 Params:
2056 sink = an $(REF_ALTTEXT output range, isOutputRange, std,range,primitives)
2057 subject = the array to scan
2058 from = the item to replace
2059 to = the item to replace all instances of `from` with
2060
2061 Returns:
2062 If `sink` isn't defined, a new array without changing the
2063 contents of `subject`, or the original array if no match
2064 is found.
2065
2066 See_Also:
2067 $(REF map, std,algorithm,iteration) which can act as a lazy replace
2068 +/
2069 E[] replace(E, R1, R2)(E[] subject, R1 from, R2 to)
2070 if (isDynamicArray!(E[]) && isForwardRange!R1 && isForwardRange!R2
2071 && (hasLength!R2 || isSomeString!R2))
2072 {
2073 import std.algorithm.searching : find;
2074
2075 if (from.empty) return subject;
2076
2077 auto balance = find(subject, from.save);
2078 if (balance.empty)
2079 return subject;
2080
2081 auto app = appender!(E[])();
2082 app.put(subject[0 .. subject.length - balance.length]);
2083 app.put(to.save);
2084 replaceInto(app, balance[from.length .. $], from, to);
2085
2086 return app.data;
2087 }
2088
2089 ///
2090 @safe unittest
2091 {
2092 assert("Hello Wörld".replace("o Wö", "o Wo") == "Hello World");
2093 assert("Hello Wörld".replace("l", "h") == "Hehho Wörhd");
2094 }
2095
2096 /// ditto
2097 void replaceInto(E, Sink, R1, R2)(Sink sink, E[] subject, R1 from, R2 to)
2098 if (isOutputRange!(Sink, E) && isDynamicArray!(E[])
2099 && isForwardRange!R1 && isForwardRange!R2
2100 && (hasLength!R2 || isSomeString!R2))
2101 {
2102 import std.algorithm.searching : find;
2103
2104 if (from.empty)
2105 {
2106 sink.put(subject);
2107 return;
2108 }
2109 for (;;)
2110 {
2111 auto balance = find(subject, from.save);
2112 if (balance.empty)
2113 {
2114 sink.put(subject);
2115 break;
2116 }
2117 sink.put(subject[0 .. subject.length - balance.length]);
2118 sink.put(to.save);
2119 subject = balance[from.length .. $];
2120 }
2121 }
2122
2123 ///
2124 @safe unittest
2125 {
2126 auto arr = [1, 2, 3, 4, 5];
2127 auto from = [2, 3];
2128 auto to = [4, 6];
2129 auto sink = appender!(int[])();
2130
2131 replaceInto(sink, arr, from, to);
2132
2133 assert(sink.data == [1, 4, 6, 4, 5]);
2134 }
2135
2136 @safe unittest
2137 {
2138 import std.algorithm.comparison : cmp;
2139 import std.conv : to;
2140
2141 foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[]))
2142 {
2143 foreach (T; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[]))
2144 (){ // avoid slow optimizations for large functions @@@BUG@@@ 2396
2145 auto s = to!S("This is a foo foo list");
2146 auto from = to!T("foo");
2147 auto into = to!S("silly");
2148 S r;
2149 int i;
2150
2151 r = replace(s, from, into);
2152 i = cmp(r, "This is a silly silly list");
2153 assert(i == 0);
2154
2155 r = replace(s, to!S(""), into);
2156 i = cmp(r, "This is a foo foo list");
2157 assert(i == 0);
2158
2159 assert(replace(r, to!S("won't find this"), to!S("whatever")) is r);
2160 }();
2161 }
2162
2163 immutable s = "This is a foo foo list";
2164 assert(replace(s, "foo", "silly") == "This is a silly silly list");
2165 }
2166
2167 @safe unittest
2168 {
2169 import std.algorithm.searching : skipOver;
2170 import std.conv : to;
2171
CheckOutput(C)2172 struct CheckOutput(C)
2173 {
2174 C[] desired;
2175 this(C[] arr){ desired = arr; }
2176 void put(C[] part){ assert(skipOver(desired, part)); }
2177 }
2178 foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[]))
2179 {
2180 alias Char = ElementEncodingType!S;
2181 S s = to!S("yet another dummy text, yet another ...");
2182 S from = to!S("yet another");
2183 S into = to!S("some");
2184 replaceInto(CheckOutput!(Char)(to!S("some dummy text, some ..."))
2185 , s, from, into);
2186 }
2187 }
2188
2189 /++
2190 Replaces elements from `array` with indices ranging from `from`
2191 (inclusive) to `to` (exclusive) with the range `stuff`.
2192
2193 Params:
2194 subject = the array to scan
2195 from = the starting index
2196 to = the ending index
2197 stuff = the items to replace in-between `from` and `to`
2198
2199 Returns:
2200 A new array without changing the contents of `subject`.
2201 +/
2202 T[] replace(T, Range)(T[] subject, size_t from, size_t to, Range stuff)
2203 if (isInputRange!Range &&
2204 (is(ElementType!Range : T) ||
2205 isSomeString!(T[]) && is(ElementType!Range : dchar)))
2206 {
2207 static if (hasLength!Range && is(ElementEncodingType!Range : T))
2208 {
2209 import std.algorithm.mutation : copy;
2210 assert(from <= to);
2211 immutable sliceLen = to - from;
2212 auto retval = new Unqual!(T)[](subject.length - sliceLen + stuff.length);
2213 retval[0 .. from] = subject[0 .. from];
2214
2215 if (!stuff.empty)
2216 copy(stuff, retval[from .. from + stuff.length]);
2217
2218 retval[from + stuff.length .. $] = subject[to .. $];
2219 return cast(T[]) retval;
2220 }
2221 else
2222 {
2223 auto app = appender!(T[])();
2224 app.put(subject[0 .. from]);
2225 app.put(stuff);
2226 app.put(subject[to .. $]);
2227 return app.data;
2228 }
2229 }
2230
2231 ///
2232 @safe unittest
2233 {
2234 auto a = [ 1, 2, 3, 4 ];
2235 auto b = a.replace(1, 3, [ 9, 9, 9 ]);
2236 assert(a == [ 1, 2, 3, 4 ]);
2237 assert(b == [ 1, 9, 9, 9, 4 ]);
2238 }
2239
2240 @system unittest
2241 {
2242 import core.exception;
2243 import std.algorithm.iteration : filter;
2244 import std.conv : to;
2245 import std.exception;
2246
2247
2248 auto a = [ 1, 2, 3, 4 ];
2249 assert(replace(a, 0, 0, [5, 6, 7]) == [5, 6, 7, 1, 2, 3, 4]);
2250 assert(replace(a, 0, 2, cast(int[])[]) == [3, 4]);
2251 assert(replace(a, 0, 4, [5, 6, 7]) == [5, 6, 7]);
2252 assert(replace(a, 0, 2, [5, 6, 7]) == [5, 6, 7, 3, 4]);
2253 assert(replace(a, 2, 4, [5, 6, 7]) == [1, 2, 5, 6, 7]);
2254
2255 assert(replace(a, 0, 0, filter!"true"([5, 6, 7])) == [5, 6, 7, 1, 2, 3, 4]);
2256 assert(replace(a, 0, 2, filter!"true"(cast(int[])[])) == [3, 4]);
2257 assert(replace(a, 0, 4, filter!"true"([5, 6, 7])) == [5, 6, 7]);
2258 assert(replace(a, 0, 2, filter!"true"([5, 6, 7])) == [5, 6, 7, 3, 4]);
2259 assert(replace(a, 2, 4, filter!"true"([5, 6, 7])) == [1, 2, 5, 6, 7]);
2260 assert(a == [ 1, 2, 3, 4 ]);
2261
2262 void testStr(T, U)(string file = __FILE__, size_t line = __LINE__)
2263 {
2264
2265 auto l = to!T("hello");
2266 auto r = to!U(" world");
2267
2268 enforce(replace(l, 0, 0, r) == " worldhello",
2269 new AssertError("testStr failure 1", file, line));
2270 enforce(replace(l, 0, 3, r) == " worldlo",
2271 new AssertError("testStr failure 2", file, line));
2272 enforce(replace(l, 3, l.length, r) == "hel world",
2273 new AssertError("testStr failure 3", file, line));
2274 enforce(replace(l, 0, l.length, r) == " world",
2275 new AssertError("testStr failure 4", file, line));
2276 enforce(replace(l, l.length, l.length, r) == "hello world",
2277 new AssertError("testStr failure 5", file, line));
2278 }
2279
2280 testStr!(string, string)();
2281 testStr!(string, wstring)();
2282 testStr!(string, dstring)();
2283 testStr!(wstring, string)();
2284 testStr!(wstring, wstring)();
2285 testStr!(wstring, dstring)();
2286 testStr!(dstring, string)();
2287 testStr!(dstring, wstring)();
2288 testStr!(dstring, dstring)();
2289
2290 enum s = "0123456789";
2291 enum w = "⁰¹²³⁴⁵⁶⁷⁸⁹"w;
2292 enum d = "⁰¹²³⁴⁵⁶⁷⁸⁹"d;
2293
2294 assert(replace(s, 0, 0, "***") == "***0123456789");
2295 assert(replace(s, 10, 10, "***") == "0123456789***");
2296 assert(replace(s, 3, 8, "1012") == "012101289");
2297 assert(replace(s, 0, 5, "43210") == "4321056789");
2298 assert(replace(s, 5, 10, "43210") == "0123443210");
2299
2300 assert(replace(w, 0, 0, "***"w) == "***⁰¹²³⁴⁵⁶⁷⁸⁹"w);
2301 assert(replace(w, 10, 10, "***"w) == "⁰¹²³⁴⁵⁶⁷⁸⁹***"w);
2302 assert(replace(w, 3, 8, "¹⁰¹²"w) == "⁰¹²¹⁰¹²⁸⁹"w);
2303 assert(replace(w, 0, 5, "⁴³²¹⁰"w) == "⁴³²¹⁰⁵⁶⁷⁸⁹"w);
2304 assert(replace(w, 5, 10, "⁴³²¹⁰"w) == "⁰¹²³⁴⁴³²¹⁰"w);
2305
2306 assert(replace(d, 0, 0, "***"d) == "***⁰¹²³⁴⁵⁶⁷⁸⁹"d);
2307 assert(replace(d, 10, 10, "***"d) == "⁰¹²³⁴⁵⁶⁷⁸⁹***"d);
2308 assert(replace(d, 3, 8, "¹⁰¹²"d) == "⁰¹²¹⁰¹²⁸⁹"d);
2309 assert(replace(d, 0, 5, "⁴³²¹⁰"d) == "⁴³²¹⁰⁵⁶⁷⁸⁹"d);
2310 assert(replace(d, 5, 10, "⁴³²¹⁰"d) == "⁰¹²³⁴⁴³²¹⁰"d);
2311 }
2312
2313 /++
2314 Replaces elements from `array` with indices ranging from `from`
2315 (inclusive) to `to` (exclusive) with the range `stuff`. Expands or
2316 shrinks the array as needed.
2317
2318 Params:
2319 array = the _array to scan
2320 from = the starting index
2321 to = the ending index
2322 stuff = the items to replace in-between `from` and `to`
2323 +/
2324 void replaceInPlace(T, Range)(ref T[] array, size_t from, size_t to, Range stuff)
2325 if (is(typeof(replace(array, from, to, stuff))))
2326 {
2327 static if (isDynamicArray!Range &&
2328 is(Unqual!(ElementEncodingType!Range) == T) &&
2329 !isNarrowString!(T[]))
2330 {
2331 // optimized for homogeneous arrays that can be overwritten.
2332 import std.algorithm.mutation : remove;
2333 import std.typecons : tuple;
2334
2335 if (overlap(array, stuff).length)
2336 {
2337 // use slower/conservative method
2338 array = array[0 .. from] ~ stuff ~ array[to .. $];
2339 }
2340 else if (stuff.length <= to - from)
2341 {
2342 // replacement reduces length
2343 immutable stuffEnd = from + stuff.length;
2344 array[from .. stuffEnd] = stuff[];
2345 if (stuffEnd < to)
2346 array = remove(array, tuple(stuffEnd, to));
2347 }
2348 else
2349 {
2350 // replacement increases length
2351 // @@@TODO@@@: optimize this
2352 immutable replaceLen = to - from;
2353 array[from .. to] = stuff[0 .. replaceLen];
2354 insertInPlace(array, to, stuff[replaceLen .. $]);
2355 }
2356 }
2357 else
2358 {
2359 // default implementation, just do what replace does.
2360 array = replace(array, from, to, stuff);
2361 }
2362 }
2363
2364 ///
2365 @safe unittest
2366 {
2367 int[] a = [1, 4, 5];
2368 replaceInPlace(a, 1u, 2u, [2, 3, 4]);
2369 assert(a == [1, 2, 3, 4, 5]);
2370 replaceInPlace(a, 1u, 2u, cast(int[])[]);
2371 assert(a == [1, 3, 4, 5]);
2372 replaceInPlace(a, 1u, 3u, a[2 .. 4]);
2373 assert(a == [1, 4, 5, 5]);
2374 }
2375
2376 @safe unittest
2377 {
2378 // Bug# 12889
2379 int[1][] arr = [[0], [1], [2], [3], [4], [5], [6]];
2380 int[1][] stuff = [[0], [1]];
2381 replaceInPlace(arr, 4, 6, stuff);
2382 assert(arr == [[0], [1], [2], [3], [0], [1], [6]]);
2383 }
2384
2385 @system unittest
2386 {
2387 // Bug# 14925
2388 char[] a = "mon texte 1".dup;
2389 char[] b = "abc".dup;
2390 replaceInPlace(a, 4, 9, b);
2391 assert(a == "mon abc 1");
2392
2393 // ensure we can replace in place with different encodings
2394 string unicoded = "\U00010437";
2395 string unicodedLong = "\U00010437aaaaa";
2396 string base = "abcXXXxyz";
2397 string result = "abc\U00010437xyz";
2398 string resultLong = "abc\U00010437aaaaaxyz";
2399 size_t repstart = 3;
2400 size_t repend = 3 + 3;
2401
2402 void testStringReplaceInPlace(T, U)()
2403 {
2404 import std.algorithm.comparison : equal;
2405 import std.conv;
2406 auto a = unicoded.to!(U[]);
2407 auto b = unicodedLong.to!(U[]);
2408
2409 auto test = base.to!(T[]);
2410
2411 test.replaceInPlace(repstart, repend, a);
2412 assert(equal(test, result), "Failed for types " ~ T.stringof ~ " and " ~ U.stringof);
2413
2414 test = base.to!(T[]);
2415
2416 test.replaceInPlace(repstart, repend, b);
2417 assert(equal(test, resultLong), "Failed for types " ~ T.stringof ~ " and " ~ U.stringof);
2418 }
2419
2420 import std.meta : AliasSeq;
2421 alias allChars = AliasSeq!(char, immutable(char), const(char),
2422 wchar, immutable(wchar), const(wchar),
2423 dchar, immutable(dchar), const(dchar));
2424 foreach (T; allChars)
2425 foreach (U; allChars)
2426 testStringReplaceInPlace!(T, U)();
2427
2428 void testInout(inout(int)[] a)
2429 {
2430 // will be transferred to the 'replace' function
2431 replaceInPlace(a, 1, 2, [1,2,3]);
2432 }
2433 }
2434
2435 @safe unittest
2436 {
2437 // the constraint for the first overload used to match this, which wouldn't compile.
2438 import std.algorithm.comparison : equal;
2439 long[] a = [1L, 2, 3];
2440 int[] b = [4, 5, 6];
2441 a.replaceInPlace(1, 2, b);
2442 assert(equal(a, [1L, 4, 5, 6, 3]));
2443 }
2444
2445 @system unittest
2446 {
2447 import core.exception;
2448 import std.algorithm.comparison : equal;
2449 import std.algorithm.iteration : filter;
2450 import std.conv : to;
2451 import std.exception;
2452
2453
2454 bool test(T, U, V)(T orig, size_t from, size_t to, U toReplace, V result,
2455 string file = __FILE__, size_t line = __LINE__)
2456 {
2457 {
2458 static if (is(T == typeof(T.init.dup)))
2459 auto a = orig.dup;
2460 else
2461 auto a = orig.idup;
2462
2463 a.replaceInPlace(from, to, toReplace);
2464 if (!equal(a, result))
2465 return false;
2466 }
2467
2468 static if (isInputRange!U)
2469 {
2470 orig.replaceInPlace(from, to, filter!"true"(toReplace));
2471 return equal(orig, result);
2472 }
2473 else
2474 return true;
2475 }
2476
2477 assert(test([1, 2, 3, 4], 0, 0, [5, 6, 7], [5, 6, 7, 1, 2, 3, 4]));
2478 assert(test([1, 2, 3, 4], 0, 2, cast(int[])[], [3, 4]));
2479 assert(test([1, 2, 3, 4], 0, 4, [5, 6, 7], [5, 6, 7]));
2480 assert(test([1, 2, 3, 4], 0, 2, [5, 6, 7], [5, 6, 7, 3, 4]));
2481 assert(test([1, 2, 3, 4], 2, 4, [5, 6, 7], [1, 2, 5, 6, 7]));
2482
2483 assert(test([1, 2, 3, 4], 0, 0, filter!"true"([5, 6, 7]), [5, 6, 7, 1, 2, 3, 4]));
2484 assert(test([1, 2, 3, 4], 0, 2, filter!"true"(cast(int[])[]), [3, 4]));
2485 assert(test([1, 2, 3, 4], 0, 4, filter!"true"([5, 6, 7]), [5, 6, 7]));
2486 assert(test([1, 2, 3, 4], 0, 2, filter!"true"([5, 6, 7]), [5, 6, 7, 3, 4]));
2487 assert(test([1, 2, 3, 4], 2, 4, filter!"true"([5, 6, 7]), [1, 2, 5, 6, 7]));
2488
2489 void testStr(T, U)(string file = __FILE__, size_t line = __LINE__)
2490 {
2491
2492 auto l = to!T("hello");
2493 auto r = to!U(" world");
2494
2495 enforce(test(l, 0, 0, r, " worldhello"),
2496 new AssertError("testStr failure 1", file, line));
2497 enforce(test(l, 0, 3, r, " worldlo"),
2498 new AssertError("testStr failure 2", file, line));
2499 enforce(test(l, 3, l.length, r, "hel world"),
2500 new AssertError("testStr failure 3", file, line));
2501 enforce(test(l, 0, l.length, r, " world"),
2502 new AssertError("testStr failure 4", file, line));
2503 enforce(test(l, l.length, l.length, r, "hello world"),
2504 new AssertError("testStr failure 5", file, line));
2505 }
2506
2507 testStr!(string, string)();
2508 testStr!(string, wstring)();
2509 testStr!(string, dstring)();
2510 testStr!(wstring, string)();
2511 testStr!(wstring, wstring)();
2512 testStr!(wstring, dstring)();
2513 testStr!(dstring, string)();
2514 testStr!(dstring, wstring)();
2515 testStr!(dstring, dstring)();
2516 }
2517
2518 /++
2519 Replaces the first occurrence of `from` with `to` in `subject`.
2520
2521 Params:
2522 subject = the array to scan
2523 from = the item to replace
2524 to = the item to replace `from` with
2525
2526 Returns:
2527 A new array without changing the contents of $(D subject), or the original
2528 array if no match is found.
2529 +/
2530 E[] replaceFirst(E, R1, R2)(E[] subject, R1 from, R2 to)
2531 if (isDynamicArray!(E[]) &&
2532 isForwardRange!R1 && is(typeof(appender!(E[])().put(from[0 .. 1]))) &&
2533 isForwardRange!R2 && is(typeof(appender!(E[])().put(to[0 .. 1]))))
2534 {
2535 if (from.empty) return subject;
2536 static if (isSomeString!(E[]))
2537 {
2538 import std.string : indexOf;
2539 immutable idx = subject.indexOf(from);
2540 }
2541 else
2542 {
2543 import std.algorithm.searching : countUntil;
2544 immutable idx = subject.countUntil(from);
2545 }
2546 if (idx == -1)
2547 return subject;
2548
2549 auto app = appender!(E[])();
2550 app.put(subject[0 .. idx]);
2551 app.put(to);
2552
2553 static if (isSomeString!(E[]) && isSomeString!R1)
2554 {
2555 import std.utf : codeLength;
2556 immutable fromLength = codeLength!(Unqual!E, R1)(from);
2557 }
2558 else
2559 immutable fromLength = from.length;
2560
2561 app.put(subject[idx + fromLength .. $]);
2562
2563 return app.data;
2564 }
2565
2566 ///
2567 @safe unittest
2568 {
2569 auto a = [1, 2, 2, 3, 4, 5];
2570 auto b = a.replaceFirst([2], [1337]);
2571 assert(b == [1, 1337, 2, 3, 4, 5]);
2572
2573 auto s = "This is a foo foo list";
2574 auto r = s.replaceFirst("foo", "silly");
2575 assert(r == "This is a silly foo list");
2576 }
2577
2578 @safe unittest
2579 {
2580 import std.algorithm.comparison : cmp;
2581 import std.conv : to;
2582
2583 foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[],
2584 const(char[]), immutable(char[])))
2585 {
2586 foreach (T; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[],
2587 const(char[]), immutable(char[])))
2588 (){ // avoid slow optimizations for large functions @@@BUG@@@ 2396
2589 auto s = to!S("This is a foo foo list");
2590 auto s2 = to!S("Thüs is a ßöö foo list");
2591 auto from = to!T("foo");
2592 auto from2 = to!T("ßöö");
2593 auto into = to!T("silly");
2594 auto into2 = to!T("sälly");
2595
2596 S r1 = replaceFirst(s, from, into);
2597 assert(cmp(r1, "This is a silly foo list") == 0);
2598
2599 S r11 = replaceFirst(s2, from2, into2);
2600 assert(cmp(r11, "Thüs is a sälly foo list") == 0,
2601 to!string(r11) ~ " : " ~ S.stringof ~ " " ~ T.stringof);
2602
2603 S r2 = replaceFirst(r1, from, into);
2604 assert(cmp(r2, "This is a silly silly list") == 0);
2605
2606 S r3 = replaceFirst(s, to!T(""), into);
2607 assert(cmp(r3, "This is a foo foo list") == 0);
2608
2609 assert(replaceFirst(r3, to!T("won't find"), to!T("whatever")) is r3);
2610 }();
2611 }
2612 }
2613
2614 //Bug# 8187
2615 @safe unittest
2616 {
2617 auto res = ["a", "a"];
2618 assert(replace(res, "a", "b") == ["b", "b"]);
2619 assert(replaceFirst(res, "a", "b") == ["b", "a"]);
2620 }
2621
2622 /++
2623 Replaces the last occurrence of `from` with `to` in `subject`.
2624
2625 Params:
2626 subject = the array to scan
2627 from = the item to replace
2628 to = the item to replace `from` with
2629
2630 Returns:
2631 A new array without changing the contents of $(D subject), or the original
2632 array if no match is found.
2633 +/
2634 E[] replaceLast(E, R1, R2)(E[] subject, R1 from , R2 to)
2635 if (isDynamicArray!(E[]) &&
2636 isForwardRange!R1 && is(typeof(appender!(E[])().put(from[0 .. 1]))) &&
2637 isForwardRange!R2 && is(typeof(appender!(E[])().put(to[0 .. 1]))))
2638 {
2639 import std.range : retro;
2640 if (from.empty) return subject;
2641 static if (isSomeString!(E[]))
2642 {
2643 import std.string : lastIndexOf;
2644 auto idx = subject.lastIndexOf(from);
2645 }
2646 else
2647 {
2648 import std.algorithm.searching : countUntil;
2649 auto idx = retro(subject).countUntil(retro(from));
2650 }
2651
2652 if (idx == -1)
2653 return subject;
2654
2655 static if (isSomeString!(E[]) && isSomeString!R1)
2656 {
2657 import std.utf : codeLength;
2658 auto fromLength = codeLength!(Unqual!E, R1)(from);
2659 }
2660 else
2661 auto fromLength = from.length;
2662
2663 auto app = appender!(E[])();
2664 static if (isSomeString!(E[]))
2665 app.put(subject[0 .. idx]);
2666 else
2667 app.put(subject[0 .. $ - idx - fromLength]);
2668
2669 app.put(to);
2670
2671 static if (isSomeString!(E[]))
2672 app.put(subject[idx+fromLength .. $]);
2673 else
2674 app.put(subject[$ - idx .. $]);
2675
2676 return app.data;
2677 }
2678
2679 ///
2680 @safe unittest
2681 {
2682 auto a = [1, 2, 2, 3, 4, 5];
2683 auto b = a.replaceLast([2], [1337]);
2684 assert(b == [1, 2, 1337, 3, 4, 5]);
2685
2686 auto s = "This is a foo foo list";
2687 auto r = s.replaceLast("foo", "silly");
2688 assert(r == "This is a foo silly list", r);
2689 }
2690
2691 @safe unittest
2692 {
2693 import std.algorithm.comparison : cmp;
2694 import std.conv : to;
2695
2696 foreach (S; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[],
2697 const(char[]), immutable(char[])))
2698 {
2699 foreach (T; AliasSeq!(string, wstring, dstring, char[], wchar[], dchar[],
2700 const(char[]), immutable(char[])))
2701 (){ // avoid slow optimizations for large functions @@@BUG@@@ 2396
2702 auto s = to!S("This is a foo foo list");
2703 auto s2 = to!S("Thüs is a ßöö ßöö list");
2704 auto from = to!T("foo");
2705 auto from2 = to!T("ßöö");
2706 auto into = to!T("silly");
2707 auto into2 = to!T("sälly");
2708
2709 S r1 = replaceLast(s, from, into);
2710 assert(cmp(r1, "This is a foo silly list") == 0, to!string(r1));
2711
2712 S r11 = replaceLast(s2, from2, into2);
2713 assert(cmp(r11, "Thüs is a ßöö sälly list") == 0,
2714 to!string(r11) ~ " : " ~ S.stringof ~ " " ~ T.stringof);
2715
2716 S r2 = replaceLast(r1, from, into);
2717 assert(cmp(r2, "This is a silly silly list") == 0);
2718
2719 S r3 = replaceLast(s, to!T(""), into);
2720 assert(cmp(r3, "This is a foo foo list") == 0);
2721
2722 assert(replaceLast(r3, to!T("won't find"), to!T("whatever")) is r3);
2723 }();
2724 }
2725 }
2726
2727 /++
2728 Creates a new array such that the items in `slice` are replaced with the
2729 items in `replacement`. `slice` and `replacement` do not need to be the
2730 same length. The result will grow or shrink based on the items given.
2731
2732 Params:
2733 s = the base of the new array
2734 slice = the slice of `s` to be replaced
2735 replacement = the items to replace `slice` with
2736
2737 Returns:
2738 A new array that is `s` with `slice` replaced by
2739 `replacement[]`.
2740 +/
2741 inout(T)[] replaceSlice(T)(inout(T)[] s, in T[] slice, in T[] replacement)
2742 in
2743 {
2744 // Verify that slice[] really is a slice of s[]
2745 assert(overlap(s, slice) is slice);
2746 }
2747 body
2748 {
2749 auto result = new T[s.length - slice.length + replacement.length];
2750 immutable so = slice.ptr - s.ptr;
2751 result[0 .. so] = s[0 .. so];
2752 result[so .. so + replacement.length] = replacement[];
2753 result[so + replacement.length .. result.length] =
2754 s[so + slice.length .. s.length];
2755
2756 return cast(inout(T)[]) result;
2757 }
2758
2759 ///
2760 @system unittest
2761 {
2762 auto a = [1, 2, 3, 4, 5];
2763 auto b = replaceSlice(a, a[1 .. 4], [0, 0, 0]);
2764
2765 assert(b == [1, 0, 0, 0, 5]);
2766 }
2767
2768 @system unittest
2769 {
2770 import std.algorithm.comparison : cmp;
2771
2772 string s = "hello";
2773 string slice = s[2 .. 4];
2774
2775 auto r = replaceSlice(s, slice, "bar");
2776 int i;
2777 i = cmp(r, "hebaro");
2778 assert(i == 0);
2779 }
2780
2781 /**
2782 Implements an output range that appends data to an array. This is
2783 recommended over $(D array ~= data) when appending many elements because it is more
2784 efficient. `Appender` maintains its own array metadata locally, so it can avoid
2785 global locking for each append where $(LREF capacity) is non-zero.
2786 See_Also: $(LREF appender)
2787 */
2788 struct Appender(A)
2789 if (isDynamicArray!A)
2790 {
2791 import core.memory : GC;
2792
2793 private alias T = ElementEncodingType!A;
2794
2795 private struct Data
2796 {
2797 size_t capacity;
2798 Unqual!T[] arr;
2799 bool canExtend = false;
2800 }
2801
2802 private Data* _data;
2803
2804 /**
2805 * Constructs an `Appender` with a given array. Note that this does not copy the
2806 * data. If the array has a larger capacity as determined by `arr.capacity`,
2807 * it will be used by the appender. After initializing an appender on an array,
2808 * appending to the original array will reallocate.
2809 */
2810 this(A arr) @trusted pure nothrow
2811 {
2812 // initialize to a given array.
2813 _data = new Data;
2814 _data.arr = cast(Unqual!T[]) arr; //trusted
2815
2816 if (__ctfe)
2817 return;
2818
2819 // We want to use up as much of the block the array is in as possible.
2820 // if we consume all the block that we can, then array appending is
2821 // safe WRT built-in append, and we can use the entire block.
2822 // We only do this for mutable types that can be extended.
2823 static if (isMutable!T && is(typeof(arr.length = size_t.max)))
2824 {
2825 immutable cap = arr.capacity; //trusted
2826 // Replace with "GC.setAttr( Not Appendable )" once pure (and fixed)
2827 if (cap > arr.length)
2828 arr.length = cap;
2829 }
2830 _data.capacity = arr.length;
2831 }
2832
2833 /**
2834 * Reserve at least newCapacity elements for appending. Note that more elements
2835 * may be reserved than requested. If `newCapacity <= capacity`, then nothing is
2836 * done.
2837 */
2838 void reserve(size_t newCapacity) @safe pure nothrow
2839 {
2840 if (_data)
2841 {
2842 if (newCapacity > _data.capacity)
2843 ensureAddable(newCapacity - _data.arr.length);
2844 }
2845 else
2846 {
2847 ensureAddable(newCapacity);
2848 }
2849 }
2850
2851 /**
2852 * Returns: the capacity of the array (the maximum number of elements the
2853 * managed array can accommodate before triggering a reallocation). If any
2854 * appending will reallocate, `0` will be returned.
2855 */
2856 @property size_t capacity() const @safe pure nothrow
2857 {
2858 return _data ? _data.capacity : 0;
2859 }
2860
2861 /**
2862 * Returns: The managed array.
2863 */
2864 @property inout(ElementEncodingType!A)[] data() inout @trusted pure nothrow
2865 {
2866 /* @trusted operation:
2867 * casting Unqual!T[] to inout(T)[]
2868 */
2869 return cast(typeof(return))(_data ? _data.arr : null);
2870 }
2871
2872 // ensure we can add nelems elements, resizing as necessary
2873 private void ensureAddable(size_t nelems) @trusted pure nothrow
2874 {
2875 if (!_data)
2876 _data = new Data;
2877 immutable len = _data.arr.length;
2878 immutable reqlen = len + nelems;
2879
2880 if (_data.capacity >= reqlen)
2881 return;
2882
2883 // need to increase capacity
2884 if (__ctfe)
2885 {
2886 static if (__traits(compiles, new Unqual!T[1]))
2887 {
2888 _data.arr.length = reqlen;
2889 }
2890 else
2891 {
2892 // avoid restriction of @disable this()
2893 _data.arr = _data.arr[0 .. _data.capacity];
2894 foreach (i; _data.capacity .. reqlen)
2895 _data.arr ~= Unqual!T.init;
2896 }
2897 _data.arr = _data.arr[0 .. len];
2898 _data.capacity = reqlen;
2899 }
2900 else
2901 {
2902 // Time to reallocate.
2903 // We need to almost duplicate what's in druntime, except we
2904 // have better access to the capacity field.
2905 auto newlen = appenderNewCapacity!(T.sizeof)(_data.capacity, reqlen);
2906 // first, try extending the current block
2907 if (_data.canExtend)
2908 {
2909 immutable u = GC.extend(_data.arr.ptr, nelems * T.sizeof, (newlen - len) * T.sizeof);
2910 if (u)
2911 {
2912 // extend worked, update the capacity
2913 _data.capacity = u / T.sizeof;
2914 return;
2915 }
2916 }
2917
2918
2919 // didn't work, must reallocate
2920 import core.checkedint : mulu;
2921 bool overflow;
2922 const nbytes = mulu(newlen, T.sizeof, overflow);
2923 if (overflow) assert(0);
2924
2925 auto bi = GC.qalloc(nbytes, blockAttribute!T);
2926 _data.capacity = bi.size / T.sizeof;
2927 import core.stdc.string : memcpy;
2928 if (len)
2929 memcpy(bi.base, _data.arr.ptr, len * T.sizeof);
2930 _data.arr = (cast(Unqual!T*) bi.base)[0 .. len];
2931 _data.canExtend = true;
2932 // leave the old data, for safety reasons
2933 }
2934 }
2935
2936 private template canPutItem(U)
2937 {
2938 enum bool canPutItem =
2939 isImplicitlyConvertible!(U, T) ||
2940 isSomeChar!T && isSomeChar!U;
2941 }
2942 private template canPutConstRange(Range)
2943 {
2944 enum bool canPutConstRange =
2945 isInputRange!(Unqual!Range) &&
2946 !isInputRange!Range &&
2947 is(typeof(Appender.init.put(Range.init.front)));
2948 }
2949 private template canPutRange(Range)
2950 {
2951 enum bool canPutRange =
2952 isInputRange!Range &&
2953 is(typeof(Appender.init.put(Range.init.front)));
2954 }
2955
2956 /**
2957 * Appends `item` to the managed array.
2958 */
2959 void put(U)(U item) if (canPutItem!U)
2960 {
2961 static if (isSomeChar!T && isSomeChar!U && T.sizeof < U.sizeof)
2962 {
2963 /* may throwable operation:
2964 * - std.utf.encode
2965 */
2966 // must do some transcoding around here
2967 import std.utf : encode;
2968 Unqual!T[T.sizeof == 1 ? 4 : 2] encoded;
2969 auto len = encode(encoded, item);
2970 put(encoded[0 .. len]);
2971 }
2972 else
2973 {
2974 import std.conv : emplaceRef;
2975
2976 ensureAddable(1);
2977 immutable len = _data.arr.length;
2978
2979 auto bigData = (() @trusted => _data.arr.ptr[0 .. len + 1])();
2980 emplaceRef!(Unqual!T)(bigData[len], cast(Unqual!T) item);
2981 //We do this at the end, in case of exceptions
2982 _data.arr = bigData;
2983 }
2984 }
2985
2986 // Const fixing hack.
2987 void put(Range)(Range items) if (canPutConstRange!Range)
2988 {
2989 alias p = put!(Unqual!Range);
2990 p(items);
2991 }
2992
2993 /**
2994 * Appends an entire range to the managed array.
2995 */
2996 void put(Range)(Range items) if (canPutRange!Range)
2997 {
2998 // note, we disable this branch for appending one type of char to
2999 // another because we can't trust the length portion.
3000 static if (!(isSomeChar!T && isSomeChar!(ElementType!Range) &&
3001 !is(immutable Range == immutable T[])) &&
3002 is(typeof(items.length) == size_t))
3003 {
3004 // optimization -- if this type is something other than a string,
3005 // and we are adding exactly one element, call the version for one
3006 // element.
3007 static if (!isSomeChar!T)
3008 {
3009 if (items.length == 1)
3010 {
3011 put(items.front);
3012 return;
3013 }
3014 }
3015
3016 // make sure we have enough space, then add the items
3017 @trusted auto bigDataFun(size_t extra)
3018 {
3019 ensureAddable(extra);
3020 return _data.arr.ptr[0 .. _data.arr.length + extra];
3021 }
3022 auto bigData = bigDataFun(items.length);
3023
3024 immutable len = _data.arr.length;
3025 immutable newlen = bigData.length;
3026
3027 alias UT = Unqual!T;
3028
3029 static if (is(typeof(_data.arr[] = items[])) &&
3030 !hasElaborateAssign!UT && isAssignable!(UT, ElementEncodingType!Range))
3031 {
3032 bigData[len .. newlen] = items[];
3033 }
3034 else
3035 {
3036 import std.conv : emplaceRef;
3037 foreach (ref it ; bigData[len .. newlen])
3038 {
3039 emplaceRef!T(it, items.front);
3040 items.popFront();
3041 }
3042 }
3043
3044 //We do this at the end, in case of exceptions
3045 _data.arr = bigData;
3046 }
3047 else
3048 {
3049 //pragma(msg, Range.stringof);
3050 // Generic input range
3051 for (; !items.empty; items.popFront())
3052 {
3053 put(items.front);
3054 }
3055 }
3056 }
3057
3058 /**
3059 * Appends `rhs` to the managed array.
3060 * Params:
3061 * rhs = Element or range.
3062 */
3063 void opOpAssign(string op : "~", U)(U rhs)
3064 if (__traits(compiles, put(rhs)))
3065 {
3066 put(rhs);
3067 }
3068
3069 // only allow overwriting data on non-immutable and non-const data
3070 static if (isMutable!T)
3071 {
3072 /**
3073 * Clears the managed array. This allows the elements of the array to be reused
3074 * for appending.
3075 *
3076 * Note: clear is disabled for immutable or const element types, due to the
3077 * possibility that $(D Appender) might overwrite immutable data.
3078 */
3079 void clear() @trusted pure nothrow
3080 {
3081 if (_data)
3082 {
3083 _data.arr = _data.arr.ptr[0 .. 0];
3084 }
3085 }
3086
3087 /**
3088 * Shrinks the managed array to the given length.
3089 *
3090 * Throws: $(D Exception) if newlength is greater than the current array length.
3091 * Note: shrinkTo is disabled for immutable or const element types.
3092 */
3093 void shrinkTo(size_t newlength) @trusted pure
3094 {
3095 import std.exception : enforce;
3096 if (_data)
3097 {
3098 enforce(newlength <= _data.arr.length, "Attempting to shrink Appender with newlength > length");
3099 _data.arr = _data.arr.ptr[0 .. newlength];
3100 }
3101 else
3102 enforce(newlength == 0, "Attempting to shrink empty Appender with non-zero newlength");
3103 }
3104 }
3105
3106 void toString(Writer)(scope Writer w)
3107 {
3108 import std.format : formattedWrite;
3109 w.formattedWrite(typeof(this).stringof ~ "(%s)", data);
3110 }
3111 }
3112
3113 ///
3114 @safe unittest
3115 {
3116 auto app = appender!string();
3117 string b = "abcdefg";
3118 foreach (char c; b)
3119 app.put(c);
3120 assert(app.data == "abcdefg");
3121
3122 int[] a = [ 1, 2 ];
3123 auto app2 = appender(a);
3124 app2.put(3);
3125 app2.put([ 4, 5, 6 ]);
3126 assert(app2.data == [ 1, 2, 3, 4, 5, 6 ]);
3127 }
3128
3129 @safe unittest
3130 {
3131 import std.format : format;
3132 auto app = appender!(int[])();
3133 app.put(1);
3134 app.put(2);
3135 app.put(3);
3136 assert("%s".format(app) == "Appender!(int[])(%s)".format([1,2,3]));
3137 }
3138
3139 @safe unittest // issue 17251
3140 {
3141 static struct R
3142 {
3143 int front() const { return 0; }
3144 bool empty() const { return true; }
3145 void popFront() {}
3146 }
3147
3148 auto app = appender!(R[]);
3149 const(R)[1] r;
3150 app.put(r[0]);
3151 app.put(r[]);
3152 }
3153
3154 //Calculates an efficient growth scheme based on the old capacity
3155 //of data, and the minimum requested capacity.
3156 //arg curLen: The current length
3157 //arg reqLen: The length as requested by the user
3158 //ret sugLen: A suggested growth.
3159 private size_t appenderNewCapacity(size_t TSizeOf)(size_t curLen, size_t reqLen) @safe pure nothrow
3160 {
3161 import core.bitop : bsr;
3162 import std.algorithm.comparison : max;
3163 if (curLen == 0)
3164 return max(reqLen,8);
3165 ulong mult = 100 + (1000UL) / (bsr(curLen * TSizeOf) + 1);
3166 // limit to doubling the length, we don't want to grow too much
3167 if (mult > 200)
3168 mult = 200;
3169 auto sugLen = cast(size_t)((curLen * mult + 99) / 100);
3170 return max(reqLen, sugLen);
3171 }
3172
3173 /**
3174 * A version of $(LREF Appender) that can update an array in-place.
3175 * It forwards all calls to an underlying appender implementation.
3176 * Any calls made to the appender also update the pointer to the
3177 * original array passed in.
3178 *
3179 * Tip: Use the `arrayPtr` overload of $(LREF appender) for construction with type-inference.
3180 */
3181 struct RefAppender(A)
3182 if (isDynamicArray!A)
3183 {
3184 private
3185 {
3186 Appender!A impl;
3187 A* arr;
3188 }
3189
3190 /**
3191 * Constructs a `RefAppender` with a given array reference. This does not copy the
3192 * data. If the array has a larger capacity as determined by `arr.capacity`, it
3193 * will be used by the appender.
3194 *
3195 * Note: Do not use built-in appending (i.e. `~=`) on the original array
3196 * until you are done with the appender, because subsequent calls to the appender
3197 * will reallocate the array data without those appends.
3198 *
3199 * Params:
3200 * arr = Pointer to an array. Must not be _null.
3201 */
3202 this(A* arr)
3203 {
3204 impl = Appender!A(*arr);
3205 this.arr = arr;
3206 }
3207
3208 /** Wraps remaining `Appender` methods such as $(LREF put).
3209 * Params:
3210 * fn = Method name to call.
3211 * args = Arguments to pass to the method.
3212 */
3213 void opDispatch(string fn, Args...)(Args args)
3214 if (__traits(compiles, (Appender!A a) => mixin("a." ~ fn ~ "(args)")))
3215 {
3216 // we do it this way because we can't cache a void return
3217 scope(exit) *this.arr = impl.data;
3218 mixin("return impl." ~ fn ~ "(args);");
3219 }
3220
3221 /**
3222 * Appends `rhs` to the managed array.
3223 * Params:
3224 * rhs = Element or range.
3225 */
3226 void opOpAssign(string op : "~", U)(U rhs)
3227 if (__traits(compiles, (Appender!A a){ a.put(rhs); }))
3228 {
3229 scope(exit) *this.arr = impl.data;
3230 impl.put(rhs);
3231 }
3232
3233 /**
3234 * Returns the capacity of the array (the maximum number of elements the
3235 * managed array can accommodate before triggering a reallocation). If any
3236 * appending will reallocate, $(D capacity) returns $(D 0).
3237 */
capacity()3238 @property size_t capacity() const
3239 {
3240 return impl.capacity;
3241 }
3242
3243 /**
3244 * Returns the managed array.
3245 */
3246 @property inout(ElementEncodingType!A)[] data() inout
3247 {
3248 return impl.data;
3249 }
3250 }
3251
3252 ///
3253 @system pure nothrow
3254 unittest
3255 {
3256 int[] a = [1, 2];
3257 auto app2 = appender(&a);
3258 assert(app2.data == [1, 2]);
3259 assert(a == [1, 2]);
3260 app2 ~= 3;
3261 app2 ~= [4, 5, 6];
3262 assert(app2.data == [1, 2, 3, 4, 5, 6]);
3263 assert(a == [1, 2, 3, 4, 5, 6]);
3264
3265 app2.reserve(5);
3266 assert(app2.capacity >= 5);
3267 }
3268
3269 /++
3270 Convenience function that returns an $(LREF Appender) instance,
3271 optionally initialized with $(D array).
3272 +/
3273 Appender!A appender(A)()
3274 if (isDynamicArray!A)
3275 {
3276 return Appender!A(null);
3277 }
3278 /// ditto
3279 Appender!(E[]) appender(A : E[], E)(auto ref A array)
3280 {
3281 static assert(!isStaticArray!A || __traits(isRef, array),
3282 "Cannot create Appender from an rvalue static array");
3283
3284 return Appender!(E[])(array);
3285 }
3286
3287 @safe pure nothrow unittest
3288 {
3289 import std.exception;
3290 {
3291 auto app = appender!(char[])();
3292 string b = "abcdefg";
3293 foreach (char c; b) app.put(c);
3294 assert(app.data == "abcdefg");
3295 }
3296 {
3297 auto app = appender!(char[])();
3298 string b = "abcdefg";
3299 foreach (char c; b) app ~= c;
3300 assert(app.data == "abcdefg");
3301 }
3302 {
3303 int[] a = [ 1, 2 ];
3304 auto app2 = appender(a);
3305 assert(app2.data == [ 1, 2 ]);
3306 app2.put(3);
3307 app2.put([ 4, 5, 6 ][]);
3308 assert(app2.data == [ 1, 2, 3, 4, 5, 6 ]);
3309 app2.put([ 7 ]);
3310 assert(app2.data == [ 1, 2, 3, 4, 5, 6, 7 ]);
3311 }
3312
3313 int[] a = [ 1, 2 ];
3314 auto app2 = appender(a);
3315 assert(app2.data == [ 1, 2 ]);
3316 app2 ~= 3;
3317 app2 ~= [ 4, 5, 6 ][];
3318 assert(app2.data == [ 1, 2, 3, 4, 5, 6 ]);
3319 app2 ~= [ 7 ];
3320 assert(app2.data == [ 1, 2, 3, 4, 5, 6, 7 ]);
3321
3322 app2.reserve(5);
3323 assert(app2.capacity >= 5);
3324
3325 try // shrinkTo may throw
3326 {
3327 app2.shrinkTo(3);
3328 }
3329 catch (Exception) assert(0);
3330 assert(app2.data == [ 1, 2, 3 ]);
3331 assertThrown(app2.shrinkTo(5));
3332
3333 const app3 = app2;
3334 assert(app3.capacity >= 3);
3335 assert(app3.data == [1, 2, 3]);
3336
3337 auto app4 = appender([]);
3338 try // shrinkTo may throw
3339 {
3340 app4.shrinkTo(0);
3341 }
3342 catch (Exception) assert(0);
3343
3344 // Issue 5663 & 9725 tests
3345 foreach (S; AliasSeq!(char[], const(char)[], string))
3346 {
3347 {
3348 Appender!S app5663i;
3349 assertNotThrown(app5663i.put("\xE3"));
3350 assert(app5663i.data == "\xE3");
3351
3352 Appender!S app5663c;
3353 assertNotThrown(app5663c.put(cast(const(char)[])"\xE3"));
3354 assert(app5663c.data == "\xE3");
3355
3356 Appender!S app5663m;
3357 assertNotThrown(app5663m.put("\xE3".dup));
3358 assert(app5663m.data == "\xE3");
3359 }
3360 // ditto for ~=
3361 {
3362 Appender!S app5663i;
3363 assertNotThrown(app5663i ~= "\xE3");
3364 assert(app5663i.data == "\xE3");
3365
3366 Appender!S app5663c;
3367 assertNotThrown(app5663c ~= cast(const(char)[])"\xE3");
3368 assert(app5663c.data == "\xE3");
3369
3370 Appender!S app5663m;
3371 assertNotThrown(app5663m ~= "\xE3".dup);
3372 assert(app5663m.data == "\xE3");
3373 }
3374 }
3375
3376 static struct S10122
3377 {
3378 int val;
3379
3380 @disable this();
3381 this(int v) @safe pure nothrow { val = v; }
3382 }
3383 assertCTFEable!(
3384 {
3385 auto w = appender!(S10122[])();
3386 w.put(S10122(1));
3387 assert(w.data.length == 1 && w.data[0].val == 1);
3388 });
3389 }
3390
3391 ///
3392 @safe pure nothrow
3393 unittest
3394 {
3395 auto w = appender!string;
3396 // pre-allocate space for at least 10 elements (this avoids costly reallocations)
3397 w.reserve(10);
3398 assert(w.capacity >= 10);
3399
3400 w.put('a'); // single elements
3401 w.put("bc"); // multiple elements
3402
3403 // use the append syntax
3404 w ~= 'd';
3405 w ~= "ef";
3406
3407 assert(w.data == "abcdef");
3408 }
3409
3410 @safe pure nothrow unittest
3411 {
3412 {
3413 auto w = appender!string();
3414 w.reserve(4);
3415 cast(void) w.capacity;
3416 cast(void) w.data;
3417 try
3418 {
3419 wchar wc = 'a';
3420 dchar dc = 'a';
3421 w.put(wc); // decoding may throw
3422 w.put(dc); // decoding may throw
3423 }
3424 catch (Exception) assert(0);
3425 }
3426 {
3427 auto w = appender!(int[])();
3428 w.reserve(4);
3429 cast(void) w.capacity;
3430 cast(void) w.data;
3431 w.put(10);
3432 w.put([10]);
3433 w.clear();
3434 try
3435 {
3436 w.shrinkTo(0);
3437 }
3438 catch (Exception) assert(0);
3439
3440 struct N
3441 {
3442 int payload;
3443 alias payload this;
3444 }
3445 w.put(N(1));
3446 w.put([N(2)]);
3447
3448 struct S(T)
3449 {
3450 @property bool empty() { return true; }
3451 @property T front() { return T.init; }
3452 void popFront() {}
3453 }
3454 S!int r;
3455 w.put(r);
3456 }
3457 }
3458
3459 @safe unittest
3460 {
3461 import std.algorithm;
3462 import std.typecons;
3463 //10690
3464 [tuple(1)].filter!(t => true).array; // No error
3465 [tuple("A")].filter!(t => true).array; // error
3466 }
3467
3468 @system unittest
3469 {
3470 import std.range;
3471 //Coverage for put(Range)
3472 struct S1
3473 {
3474 }
3475 struct S2
3476 {
3477 void opAssign(S2){}
3478 }
3479 auto a1 = Appender!(S1[])();
3480 auto a2 = Appender!(S2[])();
3481 auto au1 = Appender!(const(S1)[])();
3482 auto au2 = Appender!(const(S2)[])();
3483 a1.put(S1().repeat().take(10));
3484 a2.put(S2().repeat().take(10));
3485 auto sc1 = const(S1)();
3486 auto sc2 = const(S2)();
3487 au1.put(sc1.repeat().take(10));
3488 au2.put(sc2.repeat().take(10));
3489 }
3490
3491 @system unittest
3492 {
3493 struct S
3494 {
3495 int* p;
3496 }
3497
3498 auto a0 = Appender!(S[])();
3499 auto a1 = Appender!(const(S)[])();
3500 auto a2 = Appender!(immutable(S)[])();
3501 auto s0 = S(null);
3502 auto s1 = const(S)(null);
3503 auto s2 = immutable(S)(null);
3504 a1.put(s0);
3505 a1.put(s1);
3506 a1.put(s2);
3507 a1.put([s0]);
3508 a1.put([s1]);
3509 a1.put([s2]);
3510 a0.put(s0);
3511 static assert(!is(typeof(a0.put(a1))));
3512 static assert(!is(typeof(a0.put(a2))));
3513 a0.put([s0]);
3514 static assert(!is(typeof(a0.put([a1]))));
3515 static assert(!is(typeof(a0.put([a2]))));
3516 static assert(!is(typeof(a2.put(a0))));
3517 static assert(!is(typeof(a2.put(a1))));
3518 a2.put(s2);
3519 static assert(!is(typeof(a2.put([a0]))));
3520 static assert(!is(typeof(a2.put([a1]))));
3521 a2.put([s2]);
3522 }
3523
3524 @safe unittest
3525 {
3526 //9528
3527 const(E)[] fastCopy(E)(E[] src) {
3528 auto app = appender!(const(E)[])();
3529 foreach (i, e; src)
3530 app.put(e);
3531 return app.data;
3532 }
3533
3534 class C {}
3535 struct S { const(C) c; }
3536 S[] s = [ S(new C) ];
3537
3538 auto t = fastCopy(s); // Does not compile
3539 }
3540
3541 @safe unittest
3542 {
3543 import std.algorithm.iteration : map;
3544 //10753
3545 struct Foo {
3546 immutable dchar d;
3547 }
3548 struct Bar {
3549 immutable int x;
3550 }
3551 "12".map!Foo.array;
3552 [1, 2].map!Bar.array;
3553 }
3554
3555 @safe unittest
3556 {
3557 //New appender signature tests
3558 alias mutARR = int[];
3559 alias conARR = const(int)[];
3560 alias immARR = immutable(int)[];
3561
3562 mutARR mut;
3563 conARR con;
3564 immARR imm;
3565
3566 {auto app = Appender!mutARR(mut);} //Always worked. Should work. Should not create a warning.
3567 static assert(!is(typeof(Appender!mutARR(con)))); //Never worked. Should not work.
3568 static assert(!is(typeof(Appender!mutARR(imm)))); //Never worked. Should not work.
3569
3570 {auto app = Appender!conARR(mut);} //Always worked. Should work. Should not create a warning.
3571 {auto app = Appender!conARR(con);} //Didn't work. Now works. Should not create a warning.
3572 {auto app = Appender!conARR(imm);} //Didn't work. Now works. Should not create a warning.
3573
3574 //{auto app = Appender!immARR(mut);} //Worked. Will cease to work. Creates warning.
3575 //static assert(!is(typeof(Appender!immARR(mut)))); //Worked. Will cease to work. Uncomment me after full deprecation.
3576 static assert(!is(typeof(Appender!immARR(con)))); //Never worked. Should not work.
3577 {auto app = Appender!immARR(imm);} //Didn't work. Now works. Should not create a warning.
3578
3579 //Deprecated. Please uncomment and make sure this doesn't work:
3580 //char[] cc;
3581 //static assert(!is(typeof(Appender!string(cc))));
3582
3583 //This should always work:
3584 {auto app = appender!string(null);}
3585 {auto app = appender!(const(char)[])(null);}
3586 {auto app = appender!(char[])(null);}
3587 }
3588
3589 @safe unittest //Test large allocations (for GC.extend)
3590 {
3591 import std.algorithm.comparison : equal;
3592 import std.range;
3593 Appender!(char[]) app;
3594 app.reserve(1); //cover reserve on non-initialized
3595 foreach (_; 0 .. 100_000)
3596 app.put('a');
3597 assert(equal(app.data, 'a'.repeat(100_000)));
3598 }
3599
3600 @safe unittest
3601 {
3602 auto reference = new ubyte[](2048 + 1); //a number big enough to have a full page (EG: the GC extends)
3603 auto arr = reference.dup;
3604 auto app = appender(arr[0 .. 0]);
3605 app.reserve(1); //This should not trigger a call to extend
3606 app.put(ubyte(1)); //Don't clobber arr
3607 assert(reference[] == arr[]);
3608 }
3609
3610 @safe unittest // clear method is supported only for mutable element types
3611 {
3612 Appender!string app;
3613 static assert(!__traits(compiles, app.clear()));
3614 }
3615
3616 @safe unittest
3617 {
3618 static struct D//dynamic
3619 {
3620 int[] i;
3621 alias i this;
3622 }
3623 static struct S//static
3624 {
3625 int[5] i;
3626 alias i this;
3627 }
3628 static assert(!is(Appender!(char[5])));
3629 static assert(!is(Appender!D));
3630 static assert(!is(Appender!S));
3631
3632 enum int[5] a = [];
3633 int[5] b;
3634 D d;
3635 S s;
3636 int[5] foo(){return a;}
3637
3638 static assert(!is(typeof(appender(a))));
3639 static assert( is(typeof(appender(b))));
3640 static assert( is(typeof(appender(d))));
3641 static assert( is(typeof(appender(s))));
3642 static assert(!is(typeof(appender(foo()))));
3643 }
3644
3645 @system unittest
3646 {
3647 // Issue 13077
3648 static class A {}
3649
3650 // reduced case
3651 auto w = appender!(shared(A)[])();
3652 w.put(new shared A());
3653
3654 // original case
3655 import std.range;
3656 InputRange!(shared A) foo()
3657 {
3658 return [new shared A].inputRangeObject;
3659 }
3660 auto res = foo.array;
3661 }
3662
3663 /++
3664 Convenience function that returns a $(LREF RefAppender) instance initialized
3665 with `arrayPtr`. Don't use null for the array pointer, use the other
3666 version of $(D appender) instead.
3667 +/
3668 RefAppender!(E[]) appender(P : E[]*, E)(P arrayPtr)
3669 {
3670 return RefAppender!(E[])(arrayPtr);
3671 }
3672
3673 ///
3674 @system pure nothrow
3675 unittest
3676 {
3677 int[] a = [1, 2];
3678 auto app2 = appender(&a);
3679 assert(app2.data == [1, 2]);
3680 assert(a == [1, 2]);
3681 app2 ~= 3;
3682 app2 ~= [4, 5, 6];
3683 assert(app2.data == [1, 2, 3, 4, 5, 6]);
3684 assert(a == [1, 2, 3, 4, 5, 6]);
3685
3686 app2.reserve(5);
3687 assert(app2.capacity >= 5);
3688 }
3689
3690 @system unittest
3691 {
3692 import std.exception;
3693 {
3694 auto arr = new char[0];
3695 auto app = appender(&arr);
3696 string b = "abcdefg";
3697 foreach (char c; b) app.put(c);
3698 assert(app.data == "abcdefg");
3699 assert(arr == "abcdefg");
3700 }
3701 {
3702 auto arr = new char[0];
3703 auto app = appender(&arr);
3704 string b = "abcdefg";
3705 foreach (char c; b) app ~= c;
3706 assert(app.data == "abcdefg");
3707 assert(arr == "abcdefg");
3708 }
3709 {
3710 int[] a = [ 1, 2 ];
3711 auto app2 = appender(&a);
3712 assert(app2.data == [ 1, 2 ]);
3713 assert(a == [ 1, 2 ]);
3714 app2.put(3);
3715 app2.put([ 4, 5, 6 ][]);
3716 assert(app2.data == [ 1, 2, 3, 4, 5, 6 ]);
3717 assert(a == [ 1, 2, 3, 4, 5, 6 ]);
3718 }
3719
3720 int[] a = [ 1, 2 ];
3721 auto app2 = appender(&a);
3722 assert(app2.data == [ 1, 2 ]);
3723 assert(a == [ 1, 2 ]);
3724 app2 ~= 3;
3725 app2 ~= [ 4, 5, 6 ][];
3726 assert(app2.data == [ 1, 2, 3, 4, 5, 6 ]);
3727 assert(a == [ 1, 2, 3, 4, 5, 6 ]);
3728
3729 app2.reserve(5);
3730 assert(app2.capacity >= 5);
3731
3732 try // shrinkTo may throw
3733 {
3734 app2.shrinkTo(3);
3735 }
3736 catch (Exception) assert(0);
3737 assert(app2.data == [ 1, 2, 3 ]);
3738 assertThrown(app2.shrinkTo(5));
3739
3740 const app3 = app2;
3741 assert(app3.capacity >= 3);
3742 assert(app3.data == [1, 2, 3]);
3743 }
3744
3745 @safe unittest // issue 14605
3746 {
3747 static assert(isOutputRange!(Appender!(int[]), int));
3748 static assert(isOutputRange!(RefAppender!(int[]), int));
3749 }
3750
3751 @safe unittest
3752 {
3753 Appender!(int[]) app;
3754 short[] range = [1, 2, 3];
3755 app.put(range);
3756 assert(app.data == [1, 2, 3]);
3757 }
3758
3759 @safe unittest
3760 {
3761 string s = "hello".idup;
3762 char[] a = "hello".dup;
3763 auto appS = appender(s);
3764 auto appA = appender(a);
3765 put(appS, 'w');
3766 put(appA, 'w');
3767 s ~= 'a'; //Clobbers here?
3768 a ~= 'a'; //Clobbers here?
3769 assert(appS.data == "hellow");
3770 assert(appA.data == "hellow");
3771 }
3772