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 * Use opSlice() from now on.
2863 * Returns: The managed array.
2864 */
2865 @property inout(ElementEncodingType!A)[] data() inout @trusted pure nothrow
2866 {
2867 return this[];
2868 }
2869
2870 /**
2871 * Returns: The managed array.
2872 */
2873 @property inout(ElementEncodingType!A)[] opSlice() inout @trusted pure nothrow
2874 {
2875 /* @trusted operation:
2876 * casting Unqual!T[] to inout(T)[]
2877 */
2878 return cast(typeof(return))(_data ? _data.arr : null);
2879 }
2880
2881 // ensure we can add nelems elements, resizing as necessary
2882 private void ensureAddable(size_t nelems) @trusted pure nothrow
2883 {
2884 if (!_data)
2885 _data = new Data;
2886 immutable len = _data.arr.length;
2887 immutable reqlen = len + nelems;
2888
2889 if (_data.capacity >= reqlen)
2890 return;
2891
2892 // need to increase capacity
2893 if (__ctfe)
2894 {
2895 static if (__traits(compiles, new Unqual!T[1]))
2896 {
2897 _data.arr.length = reqlen;
2898 }
2899 else
2900 {
2901 // avoid restriction of @disable this()
2902 _data.arr = _data.arr[0 .. _data.capacity];
2903 foreach (i; _data.capacity .. reqlen)
2904 _data.arr ~= Unqual!T.init;
2905 }
2906 _data.arr = _data.arr[0 .. len];
2907 _data.capacity = reqlen;
2908 }
2909 else
2910 {
2911 // Time to reallocate.
2912 // We need to almost duplicate what's in druntime, except we
2913 // have better access to the capacity field.
2914 auto newlen = appenderNewCapacity!(T.sizeof)(_data.capacity, reqlen);
2915 // first, try extending the current block
2916 if (_data.canExtend)
2917 {
2918 immutable u = GC.extend(_data.arr.ptr, nelems * T.sizeof, (newlen - len) * T.sizeof);
2919 if (u)
2920 {
2921 // extend worked, update the capacity
2922 _data.capacity = u / T.sizeof;
2923 return;
2924 }
2925 }
2926
2927
2928 // didn't work, must reallocate
2929 import core.checkedint : mulu;
2930 bool overflow;
2931 const nbytes = mulu(newlen, T.sizeof, overflow);
2932 if (overflow) assert(0);
2933
2934 auto bi = GC.qalloc(nbytes, blockAttribute!T);
2935 _data.capacity = bi.size / T.sizeof;
2936 import core.stdc.string : memcpy;
2937 if (len)
2938 memcpy(bi.base, _data.arr.ptr, len * T.sizeof);
2939 _data.arr = (cast(Unqual!T*) bi.base)[0 .. len];
2940 _data.canExtend = true;
2941 // leave the old data, for safety reasons
2942 }
2943 }
2944
2945 private template canPutItem(U)
2946 {
2947 enum bool canPutItem =
2948 isImplicitlyConvertible!(U, T) ||
2949 isSomeChar!T && isSomeChar!U;
2950 }
2951 private template canPutConstRange(Range)
2952 {
2953 enum bool canPutConstRange =
2954 isInputRange!(Unqual!Range) &&
2955 !isInputRange!Range &&
2956 is(typeof(Appender.init.put(Range.init.front)));
2957 }
2958 private template canPutRange(Range)
2959 {
2960 enum bool canPutRange =
2961 isInputRange!Range &&
2962 is(typeof(Appender.init.put(Range.init.front)));
2963 }
2964
2965 /**
2966 * Appends `item` to the managed array.
2967 */
2968 void put(U)(U item) if (canPutItem!U)
2969 {
2970 static if (isSomeChar!T && isSomeChar!U && T.sizeof < U.sizeof)
2971 {
2972 /* may throwable operation:
2973 * - std.utf.encode
2974 */
2975 // must do some transcoding around here
2976 import std.utf : encode;
2977 Unqual!T[T.sizeof == 1 ? 4 : 2] encoded;
2978 auto len = encode(encoded, item);
2979 put(encoded[0 .. len]);
2980 }
2981 else
2982 {
2983 import std.conv : emplaceRef;
2984
2985 ensureAddable(1);
2986 immutable len = _data.arr.length;
2987
2988 auto bigData = (() @trusted => _data.arr.ptr[0 .. len + 1])();
2989 emplaceRef!(Unqual!T)(bigData[len], cast(Unqual!T) item);
2990 //We do this at the end, in case of exceptions
2991 _data.arr = bigData;
2992 }
2993 }
2994
2995 // Const fixing hack.
2996 void put(Range)(Range items) if (canPutConstRange!Range)
2997 {
2998 alias p = put!(Unqual!Range);
2999 p(items);
3000 }
3001
3002 /**
3003 * Appends an entire range to the managed array.
3004 */
3005 void put(Range)(Range items) if (canPutRange!Range)
3006 {
3007 // note, we disable this branch for appending one type of char to
3008 // another because we can't trust the length portion.
3009 static if (!(isSomeChar!T && isSomeChar!(ElementType!Range) &&
3010 !is(immutable Range == immutable T[])) &&
3011 is(typeof(items.length) == size_t))
3012 {
3013 // optimization -- if this type is something other than a string,
3014 // and we are adding exactly one element, call the version for one
3015 // element.
3016 static if (!isSomeChar!T)
3017 {
3018 if (items.length == 1)
3019 {
3020 put(items.front);
3021 return;
3022 }
3023 }
3024
3025 // make sure we have enough space, then add the items
3026 @trusted auto bigDataFun(size_t extra)
3027 {
3028 ensureAddable(extra);
3029 return _data.arr.ptr[0 .. _data.arr.length + extra];
3030 }
3031 auto bigData = bigDataFun(items.length);
3032
3033 immutable len = _data.arr.length;
3034 immutable newlen = bigData.length;
3035
3036 alias UT = Unqual!T;
3037
3038 static if (is(typeof(_data.arr[] = items[])) &&
3039 !hasElaborateAssign!UT && isAssignable!(UT, ElementEncodingType!Range))
3040 {
3041 bigData[len .. newlen] = items[];
3042 }
3043 else
3044 {
3045 import std.conv : emplaceRef;
3046 foreach (ref it ; bigData[len .. newlen])
3047 {
3048 emplaceRef!T(it, items.front);
3049 items.popFront();
3050 }
3051 }
3052
3053 //We do this at the end, in case of exceptions
3054 _data.arr = bigData;
3055 }
3056 else
3057 {
3058 //pragma(msg, Range.stringof);
3059 // Generic input range
3060 for (; !items.empty; items.popFront())
3061 {
3062 put(items.front);
3063 }
3064 }
3065 }
3066
3067 /**
3068 * Appends `rhs` to the managed array.
3069 * Params:
3070 * rhs = Element or range.
3071 */
3072 void opOpAssign(string op : "~", U)(U rhs)
3073 if (__traits(compiles, put(rhs)))
3074 {
3075 put(rhs);
3076 }
3077
3078 // only allow overwriting data on non-immutable and non-const data
3079 static if (isMutable!T)
3080 {
3081 /**
3082 * Clears the managed array. This allows the elements of the array to be reused
3083 * for appending.
3084 *
3085 * Note: clear is disabled for immutable or const element types, due to the
3086 * possibility that $(D Appender) might overwrite immutable data.
3087 */
3088 void clear() @trusted pure nothrow
3089 {
3090 if (_data)
3091 {
3092 _data.arr = _data.arr.ptr[0 .. 0];
3093 }
3094 }
3095
3096 /**
3097 * Shrinks the managed array to the given length.
3098 *
3099 * Throws: $(D Exception) if newlength is greater than the current array length.
3100 * Note: shrinkTo is disabled for immutable or const element types.
3101 */
3102 void shrinkTo(size_t newlength) @trusted pure
3103 {
3104 import std.exception : enforce;
3105 if (_data)
3106 {
3107 enforce(newlength <= _data.arr.length, "Attempting to shrink Appender with newlength > length");
3108 _data.arr = _data.arr.ptr[0 .. newlength];
3109 }
3110 else
3111 enforce(newlength == 0, "Attempting to shrink empty Appender with non-zero newlength");
3112 }
3113 }
3114
3115 void toString(Writer)(scope Writer w)
3116 {
3117 import std.format : formattedWrite;
3118 w.formattedWrite(typeof(this).stringof ~ "(%s)", data);
3119 }
3120 }
3121
3122 ///
3123 @safe unittest
3124 {
3125 auto app = appender!string();
3126 string b = "abcdefg";
3127 foreach (char c; b)
3128 app.put(c);
3129 assert(app[] == "abcdefg");
3130
3131 int[] a = [ 1, 2 ];
3132 auto app2 = appender(a);
3133 app2.put(3);
3134 app2.put([ 4, 5, 6 ]);
3135 assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
3136 }
3137
3138 @safe unittest
3139 {
3140 import std.format : format;
3141 auto app = appender!(int[])();
3142 app.put(1);
3143 app.put(2);
3144 app.put(3);
3145 assert("%s".format(app) == "Appender!(int[])(%s)".format([1,2,3]));
3146 }
3147
3148 @safe unittest // issue 17251
3149 {
3150 static struct R
3151 {
3152 int front() const { return 0; }
3153 bool empty() const { return true; }
3154 void popFront() {}
3155 }
3156
3157 auto app = appender!(R[]);
3158 const(R)[1] r;
3159 app.put(r[0]);
3160 app.put(r[]);
3161 }
3162
3163 //Calculates an efficient growth scheme based on the old capacity
3164 //of data, and the minimum requested capacity.
3165 //arg curLen: The current length
3166 //arg reqLen: The length as requested by the user
3167 //ret sugLen: A suggested growth.
3168 private size_t appenderNewCapacity(size_t TSizeOf)(size_t curLen, size_t reqLen) @safe pure nothrow
3169 {
3170 import core.bitop : bsr;
3171 import std.algorithm.comparison : max;
3172 if (curLen == 0)
3173 return max(reqLen,8);
3174 ulong mult = 100 + (1000UL) / (bsr(curLen * TSizeOf) + 1);
3175 // limit to doubling the length, we don't want to grow too much
3176 if (mult > 200)
3177 mult = 200;
3178 auto sugLen = cast(size_t)((curLen * mult + 99) / 100);
3179 return max(reqLen, sugLen);
3180 }
3181
3182 /**
3183 * A version of $(LREF Appender) that can update an array in-place.
3184 * It forwards all calls to an underlying appender implementation.
3185 * Any calls made to the appender also update the pointer to the
3186 * original array passed in.
3187 *
3188 * Tip: Use the `arrayPtr` overload of $(LREF appender) for construction with type-inference.
3189 */
3190 struct RefAppender(A)
3191 if (isDynamicArray!A)
3192 {
3193 private
3194 {
3195 Appender!A impl;
3196 A* arr;
3197 }
3198
3199 /**
3200 * Constructs a `RefAppender` with a given array reference. This does not copy the
3201 * data. If the array has a larger capacity as determined by `arr.capacity`, it
3202 * will be used by the appender.
3203 *
3204 * Note: Do not use built-in appending (i.e. `~=`) on the original array
3205 * until you are done with the appender, because subsequent calls to the appender
3206 * will reallocate the array data without those appends.
3207 *
3208 * Params:
3209 * arr = Pointer to an array. Must not be _null.
3210 */
3211 this(A* arr)
3212 {
3213 impl = Appender!A(*arr);
3214 this.arr = arr;
3215 }
3216
3217 /** Wraps remaining `Appender` methods such as $(LREF put).
3218 * Params:
3219 * fn = Method name to call.
3220 * args = Arguments to pass to the method.
3221 */
3222 void opDispatch(string fn, Args...)(Args args)
3223 if (__traits(compiles, (Appender!A a) => mixin("a." ~ fn ~ "(args)")))
3224 {
3225 // we do it this way because we can't cache a void return
3226 scope(exit) *this.arr = impl[];
3227 mixin("return impl." ~ fn ~ "(args);");
3228 }
3229
3230 /**
3231 * Appends `rhs` to the managed array.
3232 * Params:
3233 * rhs = Element or range.
3234 */
3235 void opOpAssign(string op : "~", U)(U rhs)
3236 if (__traits(compiles, (Appender!A a){ a.put(rhs); }))
3237 {
3238 scope(exit) *this.arr = impl[];
3239 impl.put(rhs);
3240 }
3241
3242 /**
3243 * Returns the capacity of the array (the maximum number of elements the
3244 * managed array can accommodate before triggering a reallocation). If any
3245 * appending will reallocate, $(D capacity) returns $(D 0).
3246 */
capacity()3247 @property size_t capacity() const
3248 {
3249 return impl.capacity;
3250 }
3251
3252 /* Use opSlice() instead.
3253 * Returns: the managed array.
3254 */
3255 @property inout(ElementEncodingType!A)[] data() inout
3256 {
3257 return impl[];
3258 }
3259
3260 /**
3261 * Returns: the managed array.
3262 */
3263 @property inout(ElementEncodingType!A)[] opSlice() inout
3264 {
3265 return impl[];
3266 }
3267 }
3268
3269 ///
3270 @system pure nothrow
3271 unittest
3272 {
3273 int[] a = [1, 2];
3274 auto app2 = appender(&a);
3275 assert(app2[] == [1, 2]);
3276 assert(a == [1, 2]);
3277 app2 ~= 3;
3278 app2 ~= [4, 5, 6];
3279 assert(app2[] == [1, 2, 3, 4, 5, 6]);
3280 assert(a == [1, 2, 3, 4, 5, 6]);
3281
3282 app2.reserve(5);
3283 assert(app2.capacity >= 5);
3284 }
3285
3286 /++
3287 Convenience function that returns an $(LREF Appender) instance,
3288 optionally initialized with $(D array).
3289 +/
3290 Appender!A appender(A)()
3291 if (isDynamicArray!A)
3292 {
3293 return Appender!A(null);
3294 }
3295 /// ditto
3296 Appender!(E[]) appender(A : E[], E)(auto ref A array)
3297 {
3298 static assert(!isStaticArray!A || __traits(isRef, array),
3299 "Cannot create Appender from an rvalue static array");
3300
3301 return Appender!(E[])(array);
3302 }
3303
3304 @safe pure nothrow unittest
3305 {
3306 import std.exception;
3307 {
3308 auto app = appender!(char[])();
3309 string b = "abcdefg";
3310 foreach (char c; b) app.put(c);
3311 assert(app[] == "abcdefg");
3312 }
3313 {
3314 auto app = appender!(char[])();
3315 string b = "abcdefg";
3316 foreach (char c; b) app ~= c;
3317 assert(app[] == "abcdefg");
3318 }
3319 {
3320 int[] a = [ 1, 2 ];
3321 auto app2 = appender(a);
3322 assert(app2[] == [ 1, 2 ]);
3323 app2.put(3);
3324 app2.put([ 4, 5, 6 ][]);
3325 assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
3326 app2.put([ 7 ]);
3327 assert(app2[] == [ 1, 2, 3, 4, 5, 6, 7 ]);
3328 }
3329
3330 int[] a = [ 1, 2 ];
3331 auto app2 = appender(a);
3332 assert(app2[] == [ 1, 2 ]);
3333 app2 ~= 3;
3334 app2 ~= [ 4, 5, 6 ][];
3335 assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
3336 app2 ~= [ 7 ];
3337 assert(app2[] == [ 1, 2, 3, 4, 5, 6, 7 ]);
3338
3339 app2.reserve(5);
3340 assert(app2.capacity >= 5);
3341
3342 try // shrinkTo may throw
3343 {
3344 app2.shrinkTo(3);
3345 }
3346 catch (Exception) assert(0);
3347 assert(app2[] == [ 1, 2, 3 ]);
3348 assertThrown(app2.shrinkTo(5));
3349
3350 const app3 = app2;
3351 assert(app3.capacity >= 3);
3352 assert(app3[] == [1, 2, 3]);
3353
3354 auto app4 = appender([]);
3355 try // shrinkTo may throw
3356 {
3357 app4.shrinkTo(0);
3358 }
3359 catch (Exception) assert(0);
3360
3361 // Issue 5663 & 9725 tests
3362 foreach (S; AliasSeq!(char[], const(char)[], string))
3363 {
3364 {
3365 Appender!S app5663i;
3366 assertNotThrown(app5663i.put("\xE3"));
3367 assert(app5663i[] == "\xE3");
3368
3369 Appender!S app5663c;
3370 assertNotThrown(app5663c.put(cast(const(char)[])"\xE3"));
3371 assert(app5663c[] == "\xE3");
3372
3373 Appender!S app5663m;
3374 assertNotThrown(app5663m.put("\xE3".dup));
3375 assert(app5663m[] == "\xE3");
3376 }
3377 // ditto for ~=
3378 {
3379 Appender!S app5663i;
3380 assertNotThrown(app5663i ~= "\xE3");
3381 assert(app5663i[] == "\xE3");
3382
3383 Appender!S app5663c;
3384 assertNotThrown(app5663c ~= cast(const(char)[])"\xE3");
3385 assert(app5663c[] == "\xE3");
3386
3387 Appender!S app5663m;
3388 assertNotThrown(app5663m ~= "\xE3".dup);
3389 assert(app5663m[] == "\xE3");
3390 }
3391 }
3392
3393 static struct S10122
3394 {
3395 int val;
3396
3397 @disable this();
3398 this(int v) @safe pure nothrow { val = v; }
3399 }
3400 assertCTFEable!(
3401 {
3402 auto w = appender!(S10122[])();
3403 w.put(S10122(1));
3404 assert(w[].length == 1 && w[][0].val == 1);
3405 });
3406 }
3407
3408 ///
3409 @safe pure nothrow
3410 unittest
3411 {
3412 auto w = appender!string;
3413 // pre-allocate space for at least 10 elements (this avoids costly reallocations)
3414 w.reserve(10);
3415 assert(w.capacity >= 10);
3416
3417 w.put('a'); // single elements
3418 w.put("bc"); // multiple elements
3419
3420 // use the append syntax
3421 w ~= 'd';
3422 w ~= "ef";
3423
3424 assert(w[] == "abcdef");
3425 }
3426
3427 @safe pure nothrow unittest
3428 {
3429 {
3430 auto w = appender!string();
3431 w.reserve(4);
3432 cast(void) w.capacity;
3433 cast(void) w[];
3434 try
3435 {
3436 wchar wc = 'a';
3437 dchar dc = 'a';
3438 w.put(wc); // decoding may throw
3439 w.put(dc); // decoding may throw
3440 }
3441 catch (Exception) assert(0);
3442 }
3443 {
3444 auto w = appender!(int[])();
3445 w.reserve(4);
3446 cast(void) w.capacity;
3447 cast(void) w[];
3448 w.put(10);
3449 w.put([10]);
3450 w.clear();
3451 try
3452 {
3453 w.shrinkTo(0);
3454 }
3455 catch (Exception) assert(0);
3456
3457 struct N
3458 {
3459 int payload;
3460 alias payload this;
3461 }
3462 w.put(N(1));
3463 w.put([N(2)]);
3464
3465 struct S(T)
3466 {
3467 @property bool empty() { return true; }
3468 @property T front() { return T.init; }
3469 void popFront() {}
3470 }
3471 S!int r;
3472 w.put(r);
3473 }
3474 }
3475
3476 @safe unittest
3477 {
3478 import std.algorithm;
3479 import std.typecons;
3480 //10690
3481 [tuple(1)].filter!(t => true).array; // No error
3482 [tuple("A")].filter!(t => true).array; // error
3483 }
3484
3485 @system unittest
3486 {
3487 import std.range;
3488 //Coverage for put(Range)
3489 struct S1
3490 {
3491 }
3492 struct S2
3493 {
3494 void opAssign(S2){}
3495 }
3496 auto a1 = Appender!(S1[])();
3497 auto a2 = Appender!(S2[])();
3498 auto au1 = Appender!(const(S1)[])();
3499 auto au2 = Appender!(const(S2)[])();
3500 a1.put(S1().repeat().take(10));
3501 a2.put(S2().repeat().take(10));
3502 auto sc1 = const(S1)();
3503 auto sc2 = const(S2)();
3504 au1.put(sc1.repeat().take(10));
3505 au2.put(sc2.repeat().take(10));
3506 }
3507
3508 @system unittest
3509 {
3510 struct S
3511 {
3512 int* p;
3513 }
3514
3515 auto a0 = Appender!(S[])();
3516 auto a1 = Appender!(const(S)[])();
3517 auto a2 = Appender!(immutable(S)[])();
3518 auto s0 = S(null);
3519 auto s1 = const(S)(null);
3520 auto s2 = immutable(S)(null);
3521 a1.put(s0);
3522 a1.put(s1);
3523 a1.put(s2);
3524 a1.put([s0]);
3525 a1.put([s1]);
3526 a1.put([s2]);
3527 a0.put(s0);
3528 static assert(!is(typeof(a0.put(a1))));
3529 static assert(!is(typeof(a0.put(a2))));
3530 a0.put([s0]);
3531 static assert(!is(typeof(a0.put([a1]))));
3532 static assert(!is(typeof(a0.put([a2]))));
3533 static assert(!is(typeof(a2.put(a0))));
3534 static assert(!is(typeof(a2.put(a1))));
3535 a2.put(s2);
3536 static assert(!is(typeof(a2.put([a0]))));
3537 static assert(!is(typeof(a2.put([a1]))));
3538 a2.put([s2]);
3539 }
3540
3541 @safe unittest
3542 {
3543 //9528
3544 const(E)[] fastCopy(E)(E[] src) {
3545 auto app = appender!(const(E)[])();
3546 foreach (i, e; src)
3547 app.put(e);
3548 return app[];
3549 }
3550
3551 class C {}
3552 struct S { const(C) c; }
3553 S[] s = [ S(new C) ];
3554
3555 auto t = fastCopy(s); // Does not compile
3556 }
3557
3558 @safe unittest
3559 {
3560 import std.algorithm.iteration : map;
3561 //10753
3562 struct Foo {
3563 immutable dchar d;
3564 }
3565 struct Bar {
3566 immutable int x;
3567 }
3568 "12".map!Foo.array;
3569 [1, 2].map!Bar.array;
3570 }
3571
3572 @safe unittest
3573 {
3574 import std.algorithm.comparison : equal;
3575
3576 //New appender signature tests
3577 alias mutARR = int[];
3578 alias conARR = const(int)[];
3579 alias immARR = immutable(int)[];
3580
3581 mutARR mut;
3582 conARR con;
3583 immARR imm;
3584
3585 auto app1 = Appender!mutARR(mut); //Always worked. Should work. Should not create a warning.
3586 app1.put(7);
3587 assert(equal(app1[], [7]));
3588 static assert(!is(typeof(Appender!mutARR(con)))); //Never worked. Should not work.
3589 static assert(!is(typeof(Appender!mutARR(imm)))); //Never worked. Should not work.
3590
3591 auto app2 = Appender!conARR(mut); //Always worked. Should work. Should not create a warning.
3592 app2.put(7);
3593 assert(equal(app2[], [7]));
3594 auto app3 = Appender!conARR(con); //Didn't work. Now works. Should not create a warning.
3595 app3.put(7);
3596 assert(equal(app3[], [7]));
3597 auto app4 = Appender!conARR(imm); //Didn't work. Now works. Should not create a warning.
3598 app4.put(7);
3599 assert(equal(app4[], [7]));
3600
3601 //{auto app = Appender!immARR(mut);} //Worked. Will cease to work. Creates warning.
3602 //static assert(!is(typeof(Appender!immARR(mut)))); //Worked. Will cease to work. Uncomment me after full deprecation.
3603 static assert(!is(typeof(Appender!immARR(con)))); //Never worked. Should not work.
3604 auto app5 = Appender!immARR(imm); //Didn't work. Now works. Should not create a warning.
3605 app5.put(7);
3606 assert(equal(app5[], [7]));
3607
3608 //Deprecated. Please uncomment and make sure this doesn't work:
3609 //char[] cc;
3610 //static assert(!is(typeof(Appender!string(cc))));
3611
3612 //This should always work:
3613 auto app6 = appender!string(null);
3614 assert(app6[] == null);
3615 auto app7 = appender!(const(char)[])(null);
3616 assert(app7[] == null);
3617 auto app8 = appender!(char[])(null);
3618 assert(app8[] == null);
3619 }
3620
3621 @safe unittest //Test large allocations (for GC.extend)
3622 {
3623 import std.algorithm.comparison : equal;
3624 import std.range;
3625 Appender!(char[]) app;
3626 app.reserve(1); //cover reserve on non-initialized
3627 foreach (_; 0 .. 100_000)
3628 app.put('a');
3629 assert(equal(app[], 'a'.repeat(100_000)));
3630 }
3631
3632 @safe unittest
3633 {
3634 auto reference = new ubyte[](2048 + 1); //a number big enough to have a full page (EG: the GC extends)
3635 auto arr = reference.dup;
3636 auto app = appender(arr[0 .. 0]);
3637 app.reserve(1); //This should not trigger a call to extend
3638 app.put(ubyte(1)); //Don't clobber arr
3639 assert(reference[] == arr[]);
3640 }
3641
3642 @safe unittest // clear method is supported only for mutable element types
3643 {
3644 Appender!string app;
3645 app.put("foo");
3646 static assert(!__traits(compiles, app.clear()));
3647 assert(app[] == "foo");
3648 }
3649
3650 @safe unittest
3651 {
3652 static struct D//dynamic
3653 {
3654 int[] i;
3655 alias i this;
3656 }
3657 static struct S//static
3658 {
3659 int[5] i;
3660 alias i this;
3661 }
3662 static assert(!is(Appender!(char[5])));
3663 static assert(!is(Appender!D));
3664 static assert(!is(Appender!S));
3665
3666 enum int[5] a = [];
3667 int[5] b;
3668 D d;
3669 S s;
3670 int[5] foo(){return a;}
3671
3672 static assert(!is(typeof(appender(a))));
3673 static assert( is(typeof(appender(b))));
3674 static assert( is(typeof(appender(d))));
3675 static assert( is(typeof(appender(s))));
3676 static assert(!is(typeof(appender(foo()))));
3677 }
3678
3679 @system unittest
3680 {
3681 // Issue 13077
3682 static class A {}
3683
3684 // reduced case
3685 auto w = appender!(shared(A)[])();
3686 w.put(new shared A());
3687
3688 // original case
3689 import std.range;
3690 InputRange!(shared A) foo()
3691 {
3692 return [new shared A].inputRangeObject;
3693 }
3694 auto res = foo.array;
3695 }
3696
3697 /++
3698 Convenience function that returns a $(LREF RefAppender) instance initialized
3699 with `arrayPtr`. Don't use null for the array pointer, use the other
3700 version of $(D appender) instead.
3701 +/
3702 RefAppender!(E[]) appender(P : E[]*, E)(P arrayPtr)
3703 {
3704 return RefAppender!(E[])(arrayPtr);
3705 }
3706
3707 ///
3708 @system pure nothrow
3709 unittest
3710 {
3711 int[] a = [1, 2];
3712 auto app2 = appender(&a);
3713 assert(app2[] == [1, 2]);
3714 assert(a == [1, 2]);
3715 app2 ~= 3;
3716 app2 ~= [4, 5, 6];
3717 assert(app2[] == [1, 2, 3, 4, 5, 6]);
3718 assert(a == [1, 2, 3, 4, 5, 6]);
3719
3720 app2.reserve(5);
3721 assert(app2.capacity >= 5);
3722 }
3723
3724 @system unittest
3725 {
3726 import std.exception;
3727 {
3728 auto arr = new char[0];
3729 auto app = appender(&arr);
3730 string b = "abcdefg";
3731 foreach (char c; b) app.put(c);
3732 assert(app[] == "abcdefg");
3733 assert(arr == "abcdefg");
3734 }
3735 {
3736 auto arr = new char[0];
3737 auto app = appender(&arr);
3738 string b = "abcdefg";
3739 foreach (char c; b) app ~= c;
3740 assert(app[] == "abcdefg");
3741 assert(arr == "abcdefg");
3742 }
3743 {
3744 int[] a = [ 1, 2 ];
3745 auto app2 = appender(&a);
3746 assert(app2[] == [ 1, 2 ]);
3747 assert(a == [ 1, 2 ]);
3748 app2.put(3);
3749 app2.put([ 4, 5, 6 ][]);
3750 assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
3751 assert(a == [ 1, 2, 3, 4, 5, 6 ]);
3752 }
3753
3754 int[] a = [ 1, 2 ];
3755 auto app2 = appender(&a);
3756 assert(app2[] == [ 1, 2 ]);
3757 assert(a == [ 1, 2 ]);
3758 app2 ~= 3;
3759 app2 ~= [ 4, 5, 6 ][];
3760 assert(app2[] == [ 1, 2, 3, 4, 5, 6 ]);
3761 assert(a == [ 1, 2, 3, 4, 5, 6 ]);
3762
3763 app2.reserve(5);
3764 assert(app2.capacity >= 5);
3765
3766 try // shrinkTo may throw
3767 {
3768 app2.shrinkTo(3);
3769 }
3770 catch (Exception) assert(0);
3771 assert(app2[] == [ 1, 2, 3 ]);
3772 assertThrown(app2.shrinkTo(5));
3773
3774 const app3 = app2;
3775 assert(app3.capacity >= 3);
3776 assert(app3[] == [1, 2, 3]);
3777 }
3778
3779 @safe unittest // issue 14605
3780 {
3781 static assert(isOutputRange!(Appender!(int[]), int));
3782 static assert(isOutputRange!(RefAppender!(int[]), int));
3783 }
3784
3785 @safe unittest
3786 {
3787 Appender!(int[]) app;
3788 short[] range = [1, 2, 3];
3789 app.put(range);
3790 assert(app[] == [1, 2, 3]);
3791 }
3792
3793 @safe unittest
3794 {
3795 string s = "hello".idup;
3796 char[] a = "hello".dup;
3797 auto appS = appender(s);
3798 auto appA = appender(a);
3799 put(appS, 'w');
3800 put(appA, 'w');
3801 s ~= 'a'; //Clobbers here?
3802 a ~= 'a'; //Clobbers here?
3803 assert(appS[] == "hellow");
3804 assert(appA[] == "hellow");
3805 }
3806