1 /**
2 This module is a submodule of $(MREF std, range).
3 
4 It defines the bidirectional and forward range primitives for arrays:
5 $(LREF empty), $(LREF front), $(LREF back), $(LREF popFront), $(LREF popBack) and $(LREF save).
6 
7 It provides basic range functionality by defining several templates for testing
8 whether a given object is a range, and what kind of range it is:
9 
10 $(SCRIPT inhibitQuickIndex = 1;)
11 $(DIVC quickindex,
12 $(BOOKTABLE ,
13     $(TR $(TD $(LREF isInputRange))
14         $(TD Tests if something is an $(I input range), defined to be
15         something from which one can sequentially read data using the
16         primitives `front`, `popFront`, and `empty`.
17     ))
18     $(TR $(TD $(LREF isOutputRange))
19         $(TD Tests if something is an $(I output range), defined to be
20         something to which one can sequentially write data using the
21         $(LREF put) primitive.
22     ))
23     $(TR $(TD $(LREF isForwardRange))
24         $(TD Tests if something is a $(I forward range), defined to be an
25         input range with the additional capability that one can save one's
26         current position with the `save` primitive, thus allowing one to
27         iterate over the same range multiple times.
28     ))
29     $(TR $(TD $(LREF isBidirectionalRange))
30         $(TD Tests if something is a $(I bidirectional range), that is, a
31         forward range that allows reverse traversal using the primitives $(D
32         back) and `popBack`.
33     ))
34     $(TR $(TD $(LREF isRandomAccessRange))
35         $(TD Tests if something is a $(I random access range), which is a
36         bidirectional range that also supports the array subscripting
37         operation via the primitive `opIndex`.
38     ))
39 ))
40 
41 It also provides number of templates that test for various range capabilities:
42 
43 $(BOOKTABLE ,
44     $(TR $(TD $(LREF hasMobileElements))
45         $(TD Tests if a given range's elements can be moved around using the
46         primitives `moveFront`, `moveBack`, or `moveAt`.
47     ))
48     $(TR $(TD $(LREF ElementType))
49         $(TD Returns the element type of a given range.
50     ))
51     $(TR $(TD $(LREF ElementEncodingType))
52         $(TD Returns the encoding element type of a given range.
53     ))
54     $(TR $(TD $(LREF hasSwappableElements))
55         $(TD Tests if a range is a forward range with swappable elements.
56     ))
57     $(TR $(TD $(LREF hasAssignableElements))
58         $(TD Tests if a range is a forward range with mutable elements.
59     ))
60     $(TR $(TD $(LREF hasLvalueElements))
61         $(TD Tests if a range is a forward range with elements that can be
62         passed by reference and have their address taken.
63     ))
64     $(TR $(TD $(LREF hasLength))
65         $(TD Tests if a given range has the `length` attribute.
66     ))
67     $(TR $(TD $(LREF isInfinite))
68         $(TD Tests if a given range is an $(I infinite range).
69     ))
70     $(TR $(TD $(LREF hasSlicing))
71         $(TD Tests if a given range supports the array slicing operation $(D
72         R[x .. y]).
73     ))
74 )
75 
76 Finally, it includes some convenience functions for manipulating ranges:
77 
78 $(BOOKTABLE ,
79     $(TR $(TD $(LREF popFrontN))
80         $(TD Advances a given range by up to $(I n) elements.
81     ))
82     $(TR $(TD $(LREF popBackN))
83         $(TD Advances a given bidirectional range from the right by up to
84         $(I n) elements.
85     ))
86     $(TR $(TD $(LREF popFrontExactly))
87         $(TD Advances a given range by up exactly $(I n) elements.
88     ))
89     $(TR $(TD $(LREF popBackExactly))
90         $(TD Advances a given bidirectional range from the right by exactly
91         $(I n) elements.
92     ))
93     $(TR $(TD $(LREF moveFront))
94         $(TD Removes the front element of a range.
95     ))
96     $(TR $(TD $(LREF moveBack))
97         $(TD Removes the back element of a bidirectional range.
98     ))
99     $(TR $(TD $(LREF moveAt))
100         $(TD Removes the $(I i)'th element of a random-access range.
101     ))
102     $(TR $(TD $(LREF walkLength))
103         $(TD Computes the length of any range in O(n) time.
104     ))
105     $(TR $(TD $(LREF put))
106         $(TD Outputs element `e` to a range.
107     ))
108 )
109 
110 Source: $(PHOBOSSRC std/range/primitives.d)
111 
112 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
113 
114 Authors: $(HTTP erdani.com, Andrei Alexandrescu), David Simcha, and
115          $(HTTP jmdavisprog.com, Jonathan M Davis). Credit for some of the ideas
116          in building this module goes to
117          $(HTTP fantascienza.net/leonardo/so/, Leonardo Maffi).
118 */
119 module std.range.primitives;
120 
121 import std.traits;
122 
123 /**
124 Returns `true` if `R` is an input range. An input range must
125 define the primitives `empty`, `popFront`, and `front`. The
126 following code should compile for any input range.
127 
128 ----
129 R r;              // can define a range object
130 if (r.empty) {}   // can test for empty
131 r.popFront();     // can invoke popFront()
132 auto h = r.front; // can get the front of the range of non-void type
133 ----
134 
135 The following are rules of input ranges are assumed to hold true in all
136 Phobos code. These rules are not checkable at compile-time, so not conforming
137 to these rules when writing ranges or range based code will result in
138 undefined behavior.
139 
140 $(UL
141     $(LI `r.empty` returns `false` if and only if there is more data
142     available in the range.)
143     $(LI `r.empty` evaluated multiple times, without calling
144     `r.popFront`, or otherwise mutating the range object or the
145     underlying data, yields the same result for every evaluation.)
146     $(LI `r.front` returns the current element in the range.
147     It may return by value or by reference.)
148     $(LI `r.front` can be legally evaluated if and only if evaluating
149     `r.empty` has, or would have, equaled `false`.)
150     $(LI `r.front` evaluated multiple times, without calling
151     `r.popFront`, or otherwise mutating the range object or the
152     underlying data, yields the same result for every evaluation.)
153     $(LI `r.popFront` advances to the next element in the range.)
154     $(LI `r.popFront` can be called if and only if evaluating `r.empty`
155     has, or would have, equaled `false`.)
156 )
157 
158 Also, note that Phobos code assumes that the primitives `r.front` and
159 `r.empty` are $(BIGOH 1) time complexity wise or "cheap" in terms of
160 running time. $(BIGOH) statements in the documentation of range functions
161 are made with this assumption.
162 
163 See_Also:
164     The header of $(MREF std,range) for tutorials on ranges.
165 
166 Params:
167     R = type to be tested
168     E = if present, the elements of the range must be
169         $(DDSUBLINK spec/const3, implicit_qualifier_conversions, qualifier-convertible)
170         to this type
171 
172 Returns:
173     `true` if R is an input range (possibly with element type `E`), `false` if not
174  */
175 enum bool isInputRange(R) =
176     is(typeof(R.init) == R)
177     && is(typeof((R r) { return r.empty; } (R.init)) == bool)
178     && (is(typeof((return ref R r) => r.front)) || is(typeof(ref (return ref R r) => r.front)))
179     && !is(typeof((R r) { return r.front; } (R.init)) == void)
180     && is(typeof((R r) => r.popFront));
181 
182 /// ditto
183 enum bool isInputRange(R, E) =
184     .isInputRange!R && isQualifierConvertible!(ElementType!R, E);
185 
186 ///
187 @safe unittest
188 {
189     struct A {}
190     struct B
191     {
192         void popFront();
193         @property bool empty();
194         @property int front();
195     }
196     static assert(!isInputRange!A);
197     static assert( isInputRange!B);
198     static assert( isInputRange!(int[]));
199     static assert( isInputRange!(char[]));
200     static assert(!isInputRange!(char[4]));
201     static assert( isInputRange!(inout(int)[]));
202     static assert(!isInputRange!(int[], string));
203     static assert( isInputRange!(int[], int));
204     static assert( isInputRange!(int[], const int));
205     static assert(!isInputRange!(int[], immutable int));
206 
207     static assert(!isInputRange!(const(int)[], int));
208     static assert( isInputRange!(const(int)[], const int));
209     static assert(!isInputRange!(const(int)[], immutable int));
210 
211     static assert(!isInputRange!(immutable(int)[], int));
212     static assert( isInputRange!(immutable(int)[], const int));
213     static assert( isInputRange!(immutable(int)[], immutable int));
214 
215     static struct NotDefaultConstructible
216     {
217         @disable this();
218         void popFront();
219         @property bool empty();
220         @property int front();
221     }
222     static assert( isInputRange!NotDefaultConstructible);
223 
224     static struct NotDefaultConstructibleOrCopyable
225     {
226         @disable this();
227         @disable this(this);
228         void popFront();
229         @property bool empty();
230         @property int front();
231     }
232     static assert(isInputRange!NotDefaultConstructibleOrCopyable);
233 
234     static struct Frontless
235     {
236         void popFront();
237         @property bool empty();
238     }
239     static assert(!isInputRange!Frontless);
240 
241     static struct VoidFront
242     {
243         void popFront();
244         @property bool empty();
245         void front();
246     }
247     static assert(!isInputRange!VoidFront);
248 }
249 // https://issues.dlang.org/show_bug.cgi?id=16034
250 @safe unittest
251 {
252     struct One
253     {
254         int entry = 1;
255         @disable this(this);
256     }
257 
258     assert(isInputRange!(One[]));
259 }
260 
261 @safe unittest
262 {
263     import std.algorithm.comparison : equal;
264 
265     static struct R
266     {
267         static struct Front
268         {
269             R* impl;
270             @property int value() { return impl._front; }
271             alias value this;
272         }
273 
274         int _front;
275 
276         @property bool empty() { return _front >= 3; }
277         @property auto front() { return Front(&this); }
278         void popFront() { _front++; }
279     }
280     R r;
281 
282     static assert(isInputRange!R);
283     assert(r.equal([ 0, 1, 2 ]));
284 }
285 
286 /+
287 puts the whole raw element `e` into `r`. doPut will not attempt to
288 iterate, slice or transcode `e` in any way shape or form. It will $(B only)
289 call the correct primitive (`r.put(e)`,  $(D r.front = e) or
290 `r(e)` once.
291 
292 This can be important when `e` needs to be placed in `r` unchanged.
293 Furthermore, it can be useful when working with `InputRange`s, as doPut
294 guarantees that no more than a single element will be placed.
295 +/
296 private void doPut(R, E)(ref R r, auto ref E e)
297 {
298     static if (is(PointerTarget!R == struct))
299         enum usingPut = hasMember!(PointerTarget!R, "put");
300     else
301         enum usingPut = hasMember!(R, "put");
302 
303     static if (usingPut)
304     {
305         static assert(is(typeof(r.put(e))),
306             "Cannot put a " ~ E.stringof ~ " into a " ~ R.stringof ~ ".");
307         r.put(e);
308     }
309     else static if (isNarrowString!R && is(const(E) == const(typeof(r[0]))))
310     {
311         // one character, we can put it
312         r[0] = e;
313         r = r[1 .. $];
314     }
315     else static if (isNarrowString!R && isNarrowString!E && is(typeof(r[] = e)))
316     {
317         // slice assign. Note that this is a duplicate from put, but because
318         // putChar uses doPut exclusively, we have to copy it here.
319         immutable len = e.length;
320         r[0 .. len] = e;
321         r = r[len .. $];
322     }
323     else static if (isInputRange!R)
324     {
325         static assert(is(typeof(r.front = e)),
326             "Cannot put a " ~ E.stringof ~ " into a " ~ R.stringof ~ ".");
327         r.front = e;
328         r.popFront();
329     }
330     else static if (is(typeof(r(e))))
331     {
332         r(e);
333     }
334     else
335     {
336         static assert(false,
337             "Cannot put a " ~ E.stringof ~ " into a " ~ R.stringof ~ ".");
338     }
339 }
340 
341 @safe unittest
342 {
343     static assert(!isNativeOutputRange!(int,     int));
344     static assert( isNativeOutputRange!(int[],   int));
345     static assert(!isNativeOutputRange!(int[][], int));
346 
347     static assert(!isNativeOutputRange!(int,     int[]));
348     static assert(!isNativeOutputRange!(int[],   int[]));
349     static assert( isNativeOutputRange!(int[][], int[]));
350 
351     static assert(!isNativeOutputRange!(int,     int[][]));
352     static assert(!isNativeOutputRange!(int[],   int[][]));
353     static assert(!isNativeOutputRange!(int[][], int[][]));
354 
355     static assert(!isNativeOutputRange!(int[4],   int));
356     static assert( isNativeOutputRange!(int[4][], int)); //Scary!
357     static assert( isNativeOutputRange!(int[4][], int[4]));
358 
359     static assert( isNativeOutputRange!( char[],   char));
360     static assert(!isNativeOutputRange!( char[],  dchar));
361     static assert( isNativeOutputRange!(dchar[],   char));
362     static assert( isNativeOutputRange!(dchar[],  dchar));
363 
364 }
365 
366 /++
367 Outputs `e` to `r`. The exact effect is dependent upon the two
368 types. Several cases are accepted, as described below. The code snippets
369 are attempted in order, and the first to compile "wins" and gets
370 evaluated.
371 
372 In this table "doPut" is a method that places `e` into `r`, using the
373 correct primitive: `r.put(e)` if `R` defines `put`, $(D r.front = e)
374 if `r` is an input range (followed by `r.popFront()`), or `r(e)`
375 otherwise.
376 
377 $(BOOKTABLE ,
378     $(TR
379         $(TH Code Snippet)
380         $(TH Scenario)
381     )
382     $(TR
383         $(TD `r.doPut(e);`)
384         $(TD `R` specifically accepts an `E`.)
385     )
386     $(TR
387         $(TD $(D r.doPut([ e ]);))
388         $(TD `R` specifically accepts an `E[]`.)
389     )
390     $(TR
391         $(TD `r.putChar(e);`)
392         $(TD `R` accepts some form of string or character. put will
393             transcode the character `e` accordingly.)
394     )
395     $(TR
396         $(TD $(D for (; !e.empty; e.popFront()) put(r, e.front);))
397         $(TD Copying range `E` into `R`.)
398     )
399 )
400 
401 Tip: `put` should $(I not) be used "UFCS-style", e.g. `r.put(e)`.
402 Doing this may call `R.put` directly, by-passing any transformation
403 feature provided by `Range.put`. $(D put(r, e)) is prefered.
404  +/
405 void put(R, E)(ref R r, E e)
406 {
407     //First level: simply straight up put.
408     static if (is(typeof(doPut(r, e))))
409     {
410         doPut(r, e);
411     }
412     //Optional optimization block for straight up array to array copy.
413     else static if (isDynamicArray!R &&
414                     !isAutodecodableString!R &&
415                     isDynamicArray!E &&
416                     is(typeof(r[] = e[])))
417     {
418         immutable len = e.length;
419         r[0 .. len] = e[];
420         r = r[len .. $];
421     }
422     //Accepts E[] ?
423     else static if (is(typeof(doPut(r, [e]))) && !isDynamicArray!R)
424     {
425         if (__ctfe)
426         {
427             E[1] arr = [e];
428             doPut(r, arr[]);
429         }
430         else
431             doPut(r, (ref e) @trusted { return (&e)[0 .. 1]; }(e));
432     }
433     //special case for char to string.
434     else static if (isSomeChar!E && is(typeof(putChar(r, e))))
435     {
436         putChar(r, e);
437     }
438     //Extract each element from the range
439     //We can use "put" here, so we can recursively test a RoR of E.
440     else static if (isInputRange!E && is(typeof(put(r, e.front))))
441     {
442         //Special optimization: If E is a narrow string, and r accepts characters no-wider than the string's
443         //Then simply feed the characters 1 by 1.
444         static if (isAutodecodableString!E && !isAggregateType!E && (
445             (is(E : const  char[]) && is(typeof(doPut(r,  char.max))) && !is(typeof(doPut(r, dchar.max))) &&
446                 !is(typeof(doPut(r, wchar.max)))) ||
447             (is(E : const wchar[]) && is(typeof(doPut(r, wchar.max))) && !is(typeof(doPut(r, dchar.max)))) ) )
448         {
449             foreach (c; e)
450                 doPut(r, c);
451         }
452         else
453         {
454             for (; !e.empty; e.popFront())
455                 put(r, e.front);
456         }
457     }
458     else
459     {
460         static assert(false, "Cannot put a " ~ E.stringof ~ " into a " ~ R.stringof ~ ".");
461     }
462 }
463 
464 /**
465  * When an output range's `put` method only accepts elements of type
466  * `T`, use the global `put` to handle outputting a `T[]` to the range
467  * or vice-versa.
468  */
469 @safe pure unittest
470 {
471     import std.traits : isSomeChar;
472 
473     static struct A
474     {
475         string data;
476 
477         void put(C)(C c)
478         if (isSomeChar!C)
479         {
480             data ~= c;
481         }
482     }
483     static assert(isOutputRange!(A, char));
484 
485     auto a = A();
486     put(a, "Hello");
487     assert(a.data == "Hello");
488 }
489 
490 /**
491  * `put` treats dynamic arrays as array slices, and will call `popFront`
492  * on the slice after an element has been copied.
493  *
494  * Be sure to save the position of the array before calling `put`.
495  */
496 @safe pure nothrow unittest
497 {
498     int[] a = [1, 2, 3], b = [10, 20];
499     auto c = a;
500     put(a, b);
501     assert(c == [10, 20, 3]);
502     // at this point, a was advanced twice, so it only contains
503     // its last element while c represents the whole array
504     assert(a == [3]);
505 }
506 
507 /**
508  * It's also possible to `put` any width strings or characters into narrow
509  * strings -- put does the conversion for you.
510  *
511  * Note that putting the same width character as the target buffer type is
512  * `nothrow`, but transcoding can throw a $(REF UTFException, std, utf).
513  */
514 @safe pure unittest
515 {
516     // the elements must be mutable, so using string or const(char)[]
517     // won't compile
518     char[] s1 = new char[13];
519     auto r1 = s1;
520     put(r1, "Hello, World!"w);
521     assert(s1 == "Hello, World!");
522 }
523 
524 @safe pure nothrow unittest
525 {
526     // same thing, just using same character width.
527     char[] s1 = new char[13];
528     auto r1 = s1;
529     put(r1, "Hello, World!");
530     assert(s1 == "Hello, World!");
531 }
532 
533 
534 @safe pure nothrow @nogc unittest
535 {
536     static struct R() { void put(scope const(char)[]) {} }
537     R!() r;
538     put(r, 'a');
539 }
540 
541 //Helper function to handle chars as quickly and as elegantly as possible
542 //Assumes r.put(e)/r(e) has already been tested
543 private void putChar(R, E)(ref R r, E e)
544 if (isSomeChar!E)
545 {
546     // https://issues.dlang.org/show_bug.cgi?id=9186: Can't use (E[]).init
547     enum csCond = is(typeof(doPut(r, (){ ref const( char)[] cstringInit(); return cstringInit(); }())));
548     enum wsCond = is(typeof(doPut(r, (){ ref const(wchar)[] wstringInit(); return wstringInit(); }())));
549     enum dsCond = is(typeof(doPut(r, (){ ref const(dchar)[] dstringInit(); return dstringInit(); }())));
550 
551     //Use "max" to avoid static type demotion
552     enum ccCond = is(typeof(doPut(r,  char.max)));
553     enum wcCond = is(typeof(doPut(r, wchar.max)));
554     //enum dcCond = is(typeof(doPut(r, dchar.max)));
555 
556     //Fast transform a narrow char into a wider string
557     static if ((wsCond && E.sizeof < wchar.sizeof) || (dsCond && E.sizeof < dchar.sizeof))
558     {
559         enum w = wsCond && E.sizeof < wchar.sizeof;
560         Select!(w, wchar, dchar) c = e;
561         typeof(c)[1] arr = [c];
562         doPut(r, arr[]);
563     }
564     //Encode a wide char into a narrower string
565     else static if (wsCond || csCond)
566     {
567         import std.utf : encode;
568         /+static+/ Select!(wsCond, wchar[2], char[4]) buf; //static prevents purity.
569         doPut(r, buf[0 .. encode(buf, e)]);
570     }
571     //Slowly encode a wide char into a series of narrower chars
572     else static if (wcCond || ccCond)
573     {
574         import std.encoding : encode;
575         alias C = Select!(wcCond, wchar, char);
576         encode!(C, R)(e, r);
577     }
578     else
579     {
580         static assert(false, "Cannot put a " ~ E.stringof ~ " into a " ~ R.stringof ~ ".");
581     }
582 }
583 
584 pure @safe unittest
585 {
586     auto f = delegate (const(char)[]) {};
587     putChar(f, cast(dchar)'a');
588 }
589 
590 
591 @safe pure unittest
592 {
593     static struct R() { void put(scope const(char)[]) {} }
594     R!() r;
595     putChar(r, 'a');
596 }
597 
598 @safe unittest
599 {
600     struct A {}
601     static assert(!isInputRange!(A));
602     struct B
603     {
604         void put(int) {}
605     }
606     B b;
607     put(b, 5);
608 }
609 
610 @safe unittest
611 {
612     int[] a = new int[10];
613     int b;
614     static assert(isInputRange!(typeof(a)));
615     put(a, b);
616 }
617 
618 @safe unittest
619 {
620     void myprint(scope const(char)[] s) { }
621     auto r = &myprint;
622     put(r, 'a');
623 }
624 
625 @safe unittest
626 {
627     int[] a = new int[10];
628     static assert(!__traits(compiles, put(a, 1.0L)));
629     put(a, 1);
630     assert(a.length == 9);
631     /*
632      * a[0] = 65;       // OK
633      * a[0] = 'A';      // OK
634      * a[0] = "ABC"[0]; // OK
635      * put(a, "ABC");   // OK
636      */
637     put(a, "ABC");
638     assert(a.length == 6);
639 }
640 
641 @safe unittest
642 {
643     char[] a = new char[10];
644     static assert(!__traits(compiles, put(a, 1.0L)));
645     static assert(!__traits(compiles, put(a, 1)));
646     //char[] is now an output range for char, wchar, dchar, and ranges of such.
647     static assert(__traits(compiles, putChar(a, 'a')));
648     static assert(__traits(compiles, put(a, wchar('a'))));
649     static assert(__traits(compiles, put(a, dchar('a'))));
650     static assert(__traits(compiles, put(a, "ABC")));
651     static assert(__traits(compiles, put(a, "ABC"w)));
652     static assert(__traits(compiles, put(a, "ABC"d)));
653 }
654 
655 @safe unittest
656 {
657     // attempt putting into narrow strings by transcoding
658     char[] a = new char[10];
659     auto b = a;
660     put(a, "ABC"w);
661     assert(b[0 .. 3] == "ABC");
662     assert(a.length == 7);
663 
664     a = b; // reset
665     put(a, 'λ');
666     assert(b[0 .. 2] == "λ");
667     assert(a.length == 8);
668 
669     a = b; // reset
670     put(a, "ABC"d);
671     assert(b[0 .. 3] == "ABC");
672     assert(a.length == 7);
673 
674     a = b; // reset
675     put(a, '𐐷');
676     assert(b[0 .. 4] == "𐐷");
677     assert(a.length == 6);
678 
679     wchar[] aw = new wchar[10];
680     auto bw = aw;
681     put(aw, "ABC");
682     assert(bw[0 .. 3] == "ABC"w);
683     assert(aw.length == 7);
684 
685     aw = bw; // reset
686     put(aw, 'λ');
687     assert(bw[0 .. 1] == "λ"w);
688     assert(aw.length == 9);
689 
690     aw = bw; // reset
691     put(aw, "ABC"d);
692     assert(bw[0 .. 3] == "ABC"w);
693     assert(aw.length == 7);
694 
695     aw = bw; // reset
696     put(aw, '𐐷');
697     assert(bw[0 .. 2] == "𐐷"w);
698     assert(aw.length == 8);
699 
700     aw = bw; // reset
701     put(aw, "𐐷"); // try transcoding from char[]
702     assert(bw[0 .. 2] == "𐐷"w);
703     assert(aw.length == 8);
704 }
705 
706 @safe unittest
707 {
708     int[][] a = new int[][10];
709     int[]   b = new int[10];
710     int     c;
711     put(b, c);
712     assert(b.length == 9);
713     put(a, b);
714     assert(a.length == 9);
715     static assert(!__traits(compiles, put(a, c)));
716 }
717 
718 @safe unittest
719 {
720     int[][] a = new int[][](3);
721     int[]   b = [1];
722     auto aa = a;
723     put(aa, b);
724     assert(aa == [[], []]);
725     assert(a  == [[1], [], []]);
726     int[][3] c = [2];
727     aa = a;
728     put(aa, c[]);
729     assert(aa.empty);
730     assert(a == [[2], [2], [2]]);
731 }
732 
733 @safe unittest
734 {
735     // Test fix for bug 7476.
736     struct LockingTextWriter
737     {
738         void put(dchar c){}
739     }
740     struct RetroResult
741     {
742         bool end = false;
743         @property bool empty() const { return end; }
744         @property dchar front(){ return 'a'; }
745         void popFront(){ end = true; }
746     }
747     LockingTextWriter w;
748     RetroResult re;
749     put(w, re);
750 }
751 
752 @system unittest
753 {
754     import std.conv : to;
755     import std.meta : AliasSeq;
756     import std.typecons : tuple;
757 
758     static struct PutC(C)
759     {
760         string result;
761         void put(const(C) c) { result ~= to!string((&c)[0 .. 1]); }
762     }
763     static struct PutS(C)
764     {
765         string result;
766         void put(const(C)[] s) { result ~= to!string(s); }
767     }
768     static struct PutSS(C)
769     {
770         string result;
771         void put(const(C)[][] ss)
772         {
773             foreach (s; ss)
774                 result ~= to!string(s);
775         }
776     }
777 
778     PutS!char p;
779     putChar(p, cast(dchar)'a');
780 
781     //Source Char
782     static foreach (SC; AliasSeq!(char, wchar, dchar))
783     {{
784         SC ch = 'I';
785         dchar dh = '♥';
786         immutable(SC)[] s = "日本語!";
787         immutable(SC)[][] ss = ["日本語", "が", "好き", "ですか", "?"];
788 
789         //Target Char
790         static foreach (TC; AliasSeq!(char, wchar, dchar))
791         {
792             //Testing PutC and PutS
793             static foreach (Type; AliasSeq!(PutC!TC, PutS!TC))
794             {{
795                 Type type;
796                 auto sink = new Type();
797 
798                 //Testing put and sink
799                 foreach (value ; tuple(type, sink))
800                 {
801                     put(value, ch);
802                     assert(value.result == "I");
803                     put(value, dh);
804                     assert(value.result == "I♥");
805                     put(value, s);
806                     assert(value.result == "I♥日本語!");
807                     put(value, ss);
808                     assert(value.result == "I♥日本語!日本語が好きですか?");
809                 }
810             }}
811         }
812     }}
813 }
814 
815 @safe unittest
816 {
817     static struct CharRange
818     {
819         char c;
820         enum empty = false;
821         void popFront(){}
822         ref char front() return @property
823         {
824             return c;
825         }
826     }
827     CharRange c;
828     put(c, cast(dchar)'H');
829     put(c, "hello"d);
830 }
831 
832 // https://issues.dlang.org/show_bug.cgi?id=9823
833 @system unittest
834 {
835     const(char)[] r;
836     void delegate(const(char)[]) dg = (s) { r = s; };
837     put(dg, ["ABC"]);
838     assert(r == "ABC");
839 }
840 
841 // https://issues.dlang.org/show_bug.cgi?id=10571
842 @safe unittest
843 {
844     import std.format.write : formattedWrite;
845     string buf;
846     formattedWrite((scope const(char)[] s) { buf ~= s; }, "%s", "hello");
847     assert(buf == "hello");
848 }
849 
850 @safe unittest
851 {
852     import std.format.write : formattedWrite;
853     import std.meta : AliasSeq;
854     struct PutC(C)
855     {
856         void put(C){}
857     }
858     struct PutS(C)
859     {
860         void put(const(C)[]){}
861     }
862     struct CallC(C)
863     {
864         void opCall(C){}
865     }
866     struct CallS(C)
867     {
868         void opCall(const(C)[]){}
869     }
870     struct FrontC(C)
871     {
872         enum empty = false;
873         auto front()@property{return C.init;}
874         void front(C)@property{}
875         void popFront(){}
876     }
877     struct FrontS(C)
878     {
879         enum empty = false;
880         auto front()@property{return C[].init;}
881         void front(const(C)[])@property{}
882         void popFront(){}
883     }
884     void foo()
885     {
886         static foreach (C; AliasSeq!(char, wchar, dchar))
887         {{
888             formattedWrite((C c){},        "", 1, 'a', cast(wchar)'a', cast(dchar)'a', "a"c, "a"w, "a"d);
889             formattedWrite((const(C)[]){}, "", 1, 'a', cast(wchar)'a', cast(dchar)'a', "a"c, "a"w, "a"d);
890             formattedWrite(PutC!C(),       "", 1, 'a', cast(wchar)'a', cast(dchar)'a', "a"c, "a"w, "a"d);
891             formattedWrite(PutS!C(),       "", 1, 'a', cast(wchar)'a', cast(dchar)'a', "a"c, "a"w, "a"d);
892             CallC!C callC;
893             CallS!C callS;
894             formattedWrite(callC,          "", 1, 'a', cast(wchar)'a', cast(dchar)'a', "a"c, "a"w, "a"d);
895             formattedWrite(callS,          "", 1, 'a', cast(wchar)'a', cast(dchar)'a', "a"c, "a"w, "a"d);
896             formattedWrite(FrontC!C(),     "", 1, 'a', cast(wchar)'a', cast(dchar)'a', "a"c, "a"w, "a"d);
897             formattedWrite(FrontS!C(),     "", 1, 'a', cast(wchar)'a', cast(dchar)'a', "a"c, "a"w, "a"d);
898         }}
899         formattedWrite((dchar[]).init,     "", 1, 'a', cast(wchar)'a', cast(dchar)'a', "a"c, "a"w, "a"d);
900     }
901 }
902 
903 /+
904 Returns `true` if `R` is a native output range for elements of type
905 `E`. An output range is defined functionally as a range that
906 supports the operation $(D doPut(r, e)) as defined above. if $(D doPut(r, e))
907 is valid, then `put(r,e)` will have the same behavior.
908 
909 The two guarantees isNativeOutputRange gives over the larger `isOutputRange`
910 are:
911 1: `e` is $(B exactly) what will be placed (not `[e]`, for example).
912 2: if `E` is a non $(empty) `InputRange`, then placing `e` is
913 guaranteed to not overflow the range.
914  +/
915 package(std) enum bool isNativeOutputRange(R, E) =
916     is(typeof(doPut(lvalueOf!R, lvalueOf!E)));
917 
918 @safe unittest
919 {
920     int[] r = new int[](4);
921     static assert(isInputRange!(int[]));
922     static assert( isNativeOutputRange!(int[], int));
923     static assert(!isNativeOutputRange!(int[], int[]));
924     static assert( isOutputRange!(int[], int[]));
925 
926     if (!r.empty)
927         put(r, 1); //guaranteed to succeed
928     if (!r.empty)
929         put(r, [1, 2]); //May actually error out.
930 }
931 
932 /++
933 Returns `true` if `R` is an output range for elements of type
934 `E`. An output range is defined functionally as a range that
935 supports the operation $(D put(r, e)) as defined above.
936 
937 See_Also:
938     The header of $(MREF std,range) for tutorials on ranges.
939  +/
940 enum bool isOutputRange(R, E) =
941     is(typeof(put(lvalueOf!R, lvalueOf!E)));
942 
943 ///
944 @safe unittest
945 {
946     void myprint(scope const(char)[] s) { }
947     static assert(isOutputRange!(typeof(&myprint), char));
948 
949     static assert( isOutputRange!(char[], char));
950     static assert( isOutputRange!(dchar[], wchar));
951     static assert( isOutputRange!(dchar[], dchar));
952 }
953 
954 @safe unittest
955 {
956     import std.array;
957     import std.stdio : writeln;
958 
959     auto app = appender!string();
960     string s;
961     static assert( isOutputRange!(Appender!string, string));
962     static assert( isOutputRange!(Appender!string*, string));
963     static assert(!isOutputRange!(Appender!string, int));
964     static assert( isOutputRange!(wchar[], wchar));
965     static assert( isOutputRange!(dchar[], char));
966     static assert( isOutputRange!(dchar[], string));
967     static assert( isOutputRange!(dchar[], wstring));
968     static assert( isOutputRange!(dchar[], dstring));
969 
970     static assert(!isOutputRange!(const(int)[], int));
971     static assert(!isOutputRange!(inout(int)[], int));
972 }
973 
974 
975 /**
976 Returns `true` if `R` is a forward range. A forward range is an
977 input range `r` that can save "checkpoints" by saving `r.save`
978 to another value of type `R`. Notable examples of input ranges that
979 are $(I not) forward ranges are file/socket ranges; copying such a
980 range will not save the position in the stream, and they most likely
981 reuse an internal buffer as the entire stream does not sit in
982 memory. Subsequently, advancing either the original or the copy will
983 advance the stream, so the copies are not independent.
984 
985 The following code should compile for any forward range.
986 
987 ----
988 static assert(isInputRange!R);
989 R r1;
990 auto s1 = r1.save;
991 static assert(is(typeof(s1) == R));
992 ----
993 
994 Saving a range is not duplicating it; in the example above, `r1`
995 and `r2` still refer to the same underlying data. They just
996 navigate that data independently.
997 
998 The semantics of a forward range (not checkable during compilation)
999 are the same as for an input range, with the additional requirement
1000 that backtracking must be possible by saving a copy of the range
1001 object with `save` and using it later.
1002 
1003 `save` behaves in many ways like a copy constructor, and its
1004 implementation typically is done using copy construction.
1005 
1006 The existence of a copy constructor, however, does not imply
1007 the range is a forward range. For example, a range that reads
1008 from a TTY consumes its input and cannot save its place and
1009 read it again, and so cannot be a forward range and cannot
1010 have a `save` function.
1011 
1012 
1013 See_Also:
1014     The header of $(MREF std,range) for tutorials on ranges.
1015 
1016 Params:
1017     R = type to be tested
1018     E = if present, the elements of the range must be
1019         $(DDSUBLINK spec/const3, implicit_qualifier_conversions, qualifier-convertible)
1020         to this type
1021 
1022 Returns:
1023     `true` if R is a forward range (possibly with element type `E`), `false` if not
1024  */
1025 enum bool isForwardRange(R) = isInputRange!R
1026     && is(typeof((R r) { return r.save; } (R.init)) == R);
1027 
1028 /// ditto
1029 enum bool isForwardRange(R, E) =
1030     .isForwardRange!R && isQualifierConvertible!(ElementType!R, E);
1031 
1032 ///
1033 @safe unittest
1034 {
1035     static assert(!isForwardRange!(int));
1036     static assert( isForwardRange!(int[]));
1037     static assert( isForwardRange!(inout(int)[]));
1038 
1039     static assert( isForwardRange!(int[], const int));
1040     static assert(!isForwardRange!(int[], immutable int));
1041 
1042     static assert(!isForwardRange!(const(int)[], int));
1043     static assert( isForwardRange!(const(int)[], const int));
1044     static assert(!isForwardRange!(const(int)[], immutable int));
1045 
1046     static assert(!isForwardRange!(immutable(int)[], int));
1047     static assert( isForwardRange!(immutable(int)[], const int));
1048     static assert( isForwardRange!(immutable(int)[], immutable int));
1049 }
1050 
1051 @safe unittest
1052 {
1053     // BUG 14544
1054     struct R14544
1055     {
1056         int front() { return 0;}
1057         void popFront() {}
1058         bool empty() { return false; }
1059         R14544 save() {return this;}
1060     }
1061 
1062     static assert( isForwardRange!R14544 );
1063 }
1064 
1065 /**
1066 Returns `true` if `R` is a bidirectional range. A bidirectional
1067 range is a forward range that also offers the primitives `back` and
1068 `popBack`. The following code should compile for any bidirectional
1069 range.
1070 
1071 The semantics of a bidirectional range (not checkable during
1072 compilation) are assumed to be the following (`r` is an object of
1073 type `R`):
1074 
1075 $(UL $(LI `r.back` returns (possibly a reference to) the last
1076 element in the range. Calling `r.back` is allowed only if calling
1077 `r.empty` has, or would have, returned `false`.))
1078 
1079 See_Also:
1080     The header of $(MREF std,range) for tutorials on ranges.
1081 
1082 Params:
1083     R = type to be tested
1084     E = if present, the elements of the range must be
1085         $(DDSUBLINK spec/const3, implicit_qualifier_conversions, qualifier-convertible)
1086         to this type
1087 
1088 Returns:
1089     `true` if R is a bidirectional range (possibly with element type `E`), `false` if not
1090  */
1091 enum bool isBidirectionalRange(R) = isForwardRange!R
1092     && is(typeof((R r) => r.popBack))
1093     && (is(typeof((return ref R r) => r.back)) || is(typeof(ref (return ref R r) => r.back)))
1094     && is(typeof(R.init.back.init) == ElementType!R);
1095 
1096 /// ditto
1097 enum bool isBidirectionalRange(R, E) =
1098     .isBidirectionalRange!R && isQualifierConvertible!(ElementType!R, E);
1099 
1100 ///
1101 @safe unittest
1102 {
1103     alias R = int[];
1104     R r = [0,1];
1105     static assert(isForwardRange!R);           // is forward range
1106     r.popBack();                               // can invoke popBack
1107     auto t = r.back;                           // can get the back of the range
1108     auto w = r.front;
1109     static assert(is(typeof(t) == typeof(w))); // same type for front and back
1110 
1111     // Checking the element type
1112     static assert( isBidirectionalRange!(int[], const int));
1113     static assert(!isBidirectionalRange!(int[], immutable int));
1114 
1115     static assert(!isBidirectionalRange!(const(int)[], int));
1116     static assert( isBidirectionalRange!(const(int)[], const int));
1117     static assert(!isBidirectionalRange!(const(int)[], immutable int));
1118 
1119     static assert(!isBidirectionalRange!(immutable(int)[], int));
1120     static assert( isBidirectionalRange!(immutable(int)[], const int));
1121     static assert( isBidirectionalRange!(immutable(int)[], immutable int));
1122 }
1123 
1124 @safe unittest
1125 {
1126     struct A {}
1127     struct B
1128     {
1129         void popFront();
1130         @property bool empty();
1131         @property int front();
1132     }
1133     struct C
1134     {
1135         @property bool empty();
1136         @property C save();
1137         void popFront();
1138         @property int front();
1139         void popBack();
1140         @property int back();
1141     }
1142     static assert(!isBidirectionalRange!(A));
1143     static assert(!isBidirectionalRange!(B));
1144     static assert( isBidirectionalRange!(C));
1145     static assert( isBidirectionalRange!(int[]));
1146     static assert( isBidirectionalRange!(char[]));
1147     static assert( isBidirectionalRange!(inout(int)[]));
1148 }
1149 
1150 /**
1151 Returns `true` if `R` is a random-access range. A random-access
1152 range is a bidirectional range that also offers the primitive $(D
1153 opIndex), OR an infinite forward range that offers `opIndex`. In
1154 either case, the range must either offer `length` or be
1155 infinite. The following code should compile for any random-access
1156 range.
1157 
1158 The semantics of a random-access range (not checkable during
1159 compilation) are assumed to be the following (`r` is an object of
1160 type `R`): $(UL $(LI `r.opIndex(n)` returns a reference to the
1161 `n`th element in the range.))
1162 
1163 Although `char[]` and `wchar[]` (as well as their qualified
1164 versions including `string` and `wstring`) are arrays, $(D
1165 isRandomAccessRange) yields `false` for them because they use
1166 variable-length encodings (UTF-8 and UTF-16 respectively). These types
1167 are bidirectional ranges only.
1168 
1169 See_Also:
1170     The header of $(MREF std,range) for tutorials on ranges.
1171 
1172 Params:
1173     R = type to be tested
1174     E = if present, the elements of the range must be
1175         $(DDSUBLINK spec/const3, implicit_qualifier_conversions, qualifier-convertible)
1176         to this type
1177 
1178 Returns:
1179     `true` if R is a random-access range (possibly with element type `E`), `false` if not
1180  */
1181 enum bool isRandomAccessRange(R) =
1182     is(typeof(lvalueOf!R[1]) == ElementType!R)
1183     && !(isAutodecodableString!R && !isAggregateType!R)
1184     && isForwardRange!R
1185     && (isBidirectionalRange!R || isInfinite!R)
1186     && (hasLength!R || isInfinite!R)
1187     && (isInfinite!R || !is(typeof(lvalueOf!R[$ - 1]))
1188         || is(typeof(lvalueOf!R[$ - 1]) == ElementType!R));
1189 
1190 /// ditto
1191 enum bool isRandomAccessRange(R, E) =
1192     .isRandomAccessRange!R && isQualifierConvertible!(ElementType!R, E);
1193 
1194 ///
1195 @safe unittest
1196 {
1197     import std.traits : isAggregateType, isAutodecodableString;
1198 
1199     alias R = int[];
1200 
1201     // range is finite and bidirectional or infinite and forward.
1202     static assert(isBidirectionalRange!R ||
1203                   isForwardRange!R && isInfinite!R);
1204 
1205     R r = [0,1];
1206     auto e = r[1]; // can index
1207     auto f = r.front;
1208     static assert(is(typeof(e) == typeof(f))); // same type for indexed and front
1209     static assert(!(isAutodecodableString!R && !isAggregateType!R)); // narrow strings cannot be indexed as ranges
1210     static assert(hasLength!R || isInfinite!R); // must have length or be infinite
1211 
1212     // $ must work as it does with arrays if opIndex works with $
1213     static if (is(typeof(r[$])))
1214     {
1215         static assert(is(typeof(f) == typeof(r[$])));
1216 
1217         // $ - 1 doesn't make sense with infinite ranges but needs to work
1218         // with finite ones.
1219         static if (!isInfinite!R)
1220             static assert(is(typeof(f) == typeof(r[$ - 1])));
1221     }
1222 
1223     // Checking the element type
1224     static assert( isRandomAccessRange!(int[], const int));
1225     static assert(!isRandomAccessRange!(int[], immutable int));
1226 
1227     static assert(!isRandomAccessRange!(const(int)[], int));
1228     static assert( isRandomAccessRange!(const(int)[], const int));
1229     static assert(!isRandomAccessRange!(const(int)[], immutable int));
1230 
1231     static assert(!isRandomAccessRange!(immutable(int)[], int));
1232     static assert( isRandomAccessRange!(immutable(int)[], const int));
1233     static assert( isRandomAccessRange!(immutable(int)[], immutable int));
1234 }
1235 
1236 @safe unittest
1237 {
1238     struct A {}
1239     struct B
1240     {
1241         void popFront();
1242         @property bool empty();
1243         @property int front();
1244     }
1245     struct C
1246     {
1247         void popFront();
1248         @property bool empty();
1249         @property int front();
1250         void popBack();
1251         @property int back();
1252     }
1253     struct D
1254     {
1255         @property bool empty();
1256         @property D save();
1257         @property int front();
1258         void popFront();
1259         @property int back();
1260         void popBack();
1261         ref int opIndex(uint);
1262         @property size_t length();
1263         alias opDollar = length;
1264         //int opSlice(uint, uint);
1265     }
1266     struct E
1267     {
1268         bool empty();
1269         E save();
1270         int front();
1271         void popFront();
1272         int back();
1273         void popBack();
1274         ref int opIndex(uint);
1275         size_t length();
1276         alias opDollar = length;
1277         //int opSlice(uint, uint);
1278     }
1279     static assert(!isRandomAccessRange!(A));
1280     static assert(!isRandomAccessRange!(B));
1281     static assert(!isRandomAccessRange!(C));
1282     static assert( isRandomAccessRange!(D));
1283     static assert( isRandomAccessRange!(E));
1284     static assert( isRandomAccessRange!(int[]));
1285     static assert( isRandomAccessRange!(inout(int)[]));
1286 }
1287 
1288 @safe unittest
1289 {
1290     // Test fix for bug 6935.
1291     struct R
1292     {
1293         @disable this();
1294 
1295         @property bool empty() const { return false; }
1296         @property int front() const { return 0; }
1297         void popFront() {}
1298 
1299         @property R save() { return this; }
1300 
1301         @property int back() const { return 0; }
1302         void popBack(){}
1303 
1304         int opIndex(size_t n) const { return 0; }
1305         @property size_t length() const { return 0; }
1306         alias opDollar = length;
1307 
1308         void put(int e){  }
1309     }
1310     static assert(isInputRange!R);
1311     static assert(isForwardRange!R);
1312     static assert(isBidirectionalRange!R);
1313     static assert(isRandomAccessRange!R);
1314     static assert(isOutputRange!(R, int));
1315 }
1316 
1317 /**
1318 Returns `true` iff `R` is an input range that supports the
1319 `moveFront` primitive, as well as `moveBack` and `moveAt` if it's a
1320 bidirectional or random access range. These may be explicitly implemented, or
1321 may work via the default behavior of the module level functions `moveFront`
1322 and friends. The following code should compile for any range
1323 with mobile elements.
1324 
1325 ----
1326 alias E = ElementType!R;
1327 R r;
1328 static assert(isInputRange!R);
1329 static assert(is(typeof(moveFront(r)) == E));
1330 static if (isBidirectionalRange!R)
1331     static assert(is(typeof(moveBack(r)) == E));
1332 static if (isRandomAccessRange!R)
1333     static assert(is(typeof(moveAt(r, 0)) == E));
1334 ----
1335  */
1336 enum bool hasMobileElements(R) =
1337     isInputRange!R
1338     && is(typeof(moveFront(lvalueOf!R)) == ElementType!R)
1339     && (!isBidirectionalRange!R
1340         || is(typeof(moveBack(lvalueOf!R)) == ElementType!R))
1341     && (!isRandomAccessRange!R
1342         || is(typeof(moveAt(lvalueOf!R, 0)) == ElementType!R));
1343 
1344 ///
1345 @safe unittest
1346 {
1347     import std.algorithm.iteration : map;
1348     import std.range : iota, repeat;
1349 
1350     static struct HasPostblit
1351     {
1352         this(this) {}
1353     }
1354 
1355     auto nonMobile = map!"a"(repeat(HasPostblit.init));
1356     static assert(!hasMobileElements!(typeof(nonMobile)));
1357     static assert( hasMobileElements!(int[]));
1358     static assert( hasMobileElements!(inout(int)[]));
1359     static assert( hasMobileElements!(typeof(iota(1000))));
1360 
1361     static assert( hasMobileElements!( string));
1362     static assert( hasMobileElements!(dstring));
1363     static assert( hasMobileElements!( char[]));
1364     static assert( hasMobileElements!(dchar[]));
1365 }
1366 
1367 /**
1368 The element type of `R`. `R` does not have to be a range. The
1369 element type is determined as the type yielded by `r.front` for an
1370 object `r` of type `R`. For example, `ElementType!(T[])` is
1371 `T` if `T[]` isn't a narrow string; if it is, the element type is
1372 `dchar`. If `R` doesn't have `front`, `ElementType!R` is
1373 `void`.
1374  */
1375 template ElementType(R)
1376 {
1377     static if (is(typeof(R.init.front.init) T))
1378         alias ElementType = T;
1379     else
1380         alias ElementType = void;
1381 }
1382 
1383 ///
1384 @safe unittest
1385 {
1386     import std.range : iota;
1387 
1388     // Standard arrays: returns the type of the elements of the array
1389     static assert(is(ElementType!(int[]) == int));
1390 
1391     // Accessing .front retrieves the decoded dchar
1392     static assert(is(ElementType!(char[])  == dchar)); // rvalue
1393     static assert(is(ElementType!(dchar[]) == dchar)); // lvalue
1394 
1395     // Ditto
1396     static assert(is(ElementType!(string) == dchar));
1397     static assert(is(ElementType!(dstring) == immutable(dchar)));
1398 
1399     // For ranges it gets the type of .front.
1400     auto range = iota(0, 10);
1401     static assert(is(ElementType!(typeof(range)) == int));
1402 }
1403 
1404 @safe unittest
1405 {
1406     static assert(is(ElementType!(byte[]) == byte));
1407     static assert(is(ElementType!(wchar[]) == dchar)); // rvalue
1408     static assert(is(ElementType!(wstring) == dchar));
1409 }
1410 
1411 @safe unittest
1412 {
1413     enum XYZ : string { a = "foo" }
1414     auto x = XYZ.a.front;
1415     immutable char[3] a = "abc";
1416     int[] i;
1417     void[] buf;
1418     static assert(is(ElementType!(XYZ) == dchar));
1419     static assert(is(ElementType!(typeof(a)) == dchar));
1420     static assert(is(ElementType!(typeof(i)) == int));
1421     static assert(is(ElementType!(typeof(buf)) == void));
1422     static assert(is(ElementType!(inout(int)[]) == inout(int)));
1423     static assert(is(ElementType!(inout(int[])) == inout(int)));
1424 }
1425 
1426 @safe unittest
1427 {
1428     static assert(is(ElementType!(int[5]) == int));
1429     static assert(is(ElementType!(int[0]) == int));
1430     static assert(is(ElementType!(char[5]) == dchar));
1431     static assert(is(ElementType!(char[0]) == dchar));
1432 }
1433 
1434 // https://issues.dlang.org/show_bug.cgi?id=11336
1435 @safe unittest
1436 {
1437     static struct S
1438     {
1439         this(this) @disable;
1440     }
1441     static assert(is(ElementType!(S[]) == S));
1442 }
1443 
1444 // https://issues.dlang.org/show_bug.cgi?id=11401
1445 @safe unittest
1446 {
1447     // ElementType should also work for non-@propety 'front'
1448     struct E { ushort id; }
1449     struct R
1450     {
1451         E front() { return E.init; }
1452     }
1453     static assert(is(ElementType!R == E));
1454 }
1455 
1456 /**
1457 The encoding element type of `R`. For narrow strings (`char[]`,
1458 `wchar[]` and their qualified variants including `string` and
1459 `wstring`), `ElementEncodingType` is the character type of the
1460 string. For all other types, `ElementEncodingType` is the same as
1461 `ElementType`.
1462  */
1463 template ElementEncodingType(R)
1464 {
1465     static if (is(StringTypeOf!R) && is(R : E[], E))
1466         alias ElementEncodingType = E;
1467     else
1468         alias ElementEncodingType = ElementType!R;
1469 }
1470 
1471 ///
1472 @safe unittest
1473 {
1474     import std.range : iota;
1475     // internally the range stores the encoded type
1476     static assert(is(ElementEncodingType!(char[])  == char));
1477 
1478     static assert(is(ElementEncodingType!(wstring) == immutable(wchar)));
1479 
1480     static assert(is(ElementEncodingType!(byte[]) == byte));
1481 
1482     auto range = iota(0, 10);
1483     static assert(is(ElementEncodingType!(typeof(range)) == int));
1484 }
1485 
1486 @safe unittest
1487 {
1488     static assert(is(ElementEncodingType!(wchar[]) == wchar));
1489     static assert(is(ElementEncodingType!(dchar[]) == dchar));
1490     static assert(is(ElementEncodingType!(string)  == immutable(char)));
1491     static assert(is(ElementEncodingType!(dstring) == immutable(dchar)));
1492     static assert(is(ElementEncodingType!(int[])  == int));
1493 }
1494 
1495 @safe unittest
1496 {
1497     enum XYZ : string { a = "foo" }
1498     auto x = XYZ.a.front;
1499     immutable char[3] a = "abc";
1500     int[] i;
1501     void[] buf;
1502     static assert(is(ElementType!(XYZ) : dchar));
1503     static assert(is(ElementEncodingType!(char[]) == char));
1504     static assert(is(ElementEncodingType!(string) == immutable char));
1505     static assert(is(ElementType!(typeof(a)) : dchar));
1506     static assert(is(ElementType!(typeof(i)) == int));
1507     static assert(is(ElementEncodingType!(typeof(i)) == int));
1508     static assert(is(ElementType!(typeof(buf)) : void));
1509 
1510     static assert(is(ElementEncodingType!(inout char[]) : inout(char)));
1511 }
1512 
1513 @safe unittest
1514 {
1515     static assert(is(ElementEncodingType!(int[5]) == int));
1516     static assert(is(ElementEncodingType!(int[0]) == int));
1517     static assert(is(ElementEncodingType!(char[5]) == char));
1518     static assert(is(ElementEncodingType!(char[0]) == char));
1519 }
1520 
1521 /**
1522 Returns `true` if `R` is an input range and has swappable
1523 elements. The following code should compile for any range
1524 with swappable elements.
1525 
1526 ----
1527 R r;
1528 static assert(isInputRange!R);
1529 swap(r.front, r.front);
1530 static if (isBidirectionalRange!R) swap(r.back, r.front);
1531 static if (isRandomAccessRange!R) swap(r[0], r.front);
1532 ----
1533  */
1534 template hasSwappableElements(R)
1535 {
1536     import std.algorithm.mutation : swap;
1537     enum bool hasSwappableElements = isInputRange!R
1538         && is(typeof((ref R r) => swap(r.front, r.front)))
1539         && (!isBidirectionalRange!R
1540             || is(typeof((ref R r) => swap(r.back, r.front))))
1541         && (!isRandomAccessRange!R
1542             || is(typeof((ref R r) => swap(r[0], r.front))));
1543 }
1544 
1545 ///
1546 @safe unittest
1547 {
1548     static assert(!hasSwappableElements!(const int[]));
1549     static assert(!hasSwappableElements!(const(int)[]));
1550     static assert(!hasSwappableElements!(inout(int)[]));
1551     static assert( hasSwappableElements!(int[]));
1552 
1553     static assert(!hasSwappableElements!( string));
1554     static assert(!hasSwappableElements!(dstring));
1555     static assert(!hasSwappableElements!( char[]));
1556     static assert( hasSwappableElements!(dchar[]));
1557 }
1558 
1559 /**
1560 Returns `true` if `R` is an input range and has mutable
1561 elements. The following code should compile for any range
1562 with assignable elements.
1563 
1564 ----
1565 R r;
1566 static assert(isInputRange!R);
1567 r.front = r.front;
1568 static if (isBidirectionalRange!R) r.back = r.front;
1569 static if (isRandomAccessRange!R) r[0] = r.front;
1570 ----
1571  */
1572 enum bool hasAssignableElements(R) = isInputRange!R
1573     && is(typeof(lvalueOf!R.front = lvalueOf!R.front))
1574     && (!isBidirectionalRange!R
1575         || is(typeof(lvalueOf!R.back = lvalueOf!R.back)))
1576     && (!isRandomAccessRange!R
1577         || is(typeof(lvalueOf!R[0] = lvalueOf!R.front)));
1578 
1579 ///
1580 @safe unittest
1581 {
1582     static assert(!hasAssignableElements!(const int[]));
1583     static assert(!hasAssignableElements!(const(int)[]));
1584     static assert( hasAssignableElements!(int[]));
1585     static assert(!hasAssignableElements!(inout(int)[]));
1586 
1587     static assert(!hasAssignableElements!( string));
1588     static assert(!hasAssignableElements!(dstring));
1589     static assert(!hasAssignableElements!( char[]));
1590     static assert( hasAssignableElements!(dchar[]));
1591 }
1592 
1593 /**
1594 Tests whether the range `R` has lvalue elements. These are defined as
1595 elements that can be passed by reference and have their address taken.
1596 The following code should compile for any range with lvalue elements.
1597 ----
1598 void passByRef(ref ElementType!R stuff);
1599 ...
1600 static assert(isInputRange!R);
1601 passByRef(r.front);
1602 static if (isBidirectionalRange!R) passByRef(r.back);
1603 static if (isRandomAccessRange!R) passByRef(r[0]);
1604 ----
1605 */
1606 enum bool hasLvalueElements(R) = isInputRange!R
1607     && is(typeof(isLvalue(lvalueOf!R.front)))
1608     && (!isBidirectionalRange!R
1609         || is(typeof(isLvalue(lvalueOf!R.back))))
1610     && (!isRandomAccessRange!R
1611         || is(typeof(isLvalue(lvalueOf!R[0]))));
1612 
1613 /* Compile successfully if argument of type T is an lvalue
1614  */
1615 private void isLvalue(T)(T)
1616 if (0);
1617 
1618 private void isLvalue(T)(ref T)
1619 if (1);
1620 
1621 ///
1622 @safe unittest
1623 {
1624     import std.range : iota, chain;
1625 
1626     static assert( hasLvalueElements!(int[]));
1627     static assert( hasLvalueElements!(const(int)[]));
1628     static assert( hasLvalueElements!(inout(int)[]));
1629     static assert( hasLvalueElements!(immutable(int)[]));
1630     static assert(!hasLvalueElements!(typeof(iota(3))));
1631 
1632     static assert(!hasLvalueElements!( string));
1633     static assert( hasLvalueElements!(dstring));
1634     static assert(!hasLvalueElements!( char[]));
1635     static assert( hasLvalueElements!(dchar[]));
1636 
1637     auto c = chain([1, 2, 3], [4, 5, 6]);
1638     static assert( hasLvalueElements!(typeof(c)));
1639 }
1640 
1641 @safe unittest
1642 {
1643     // bugfix 6336
1644     struct S { immutable int value; }
1645     static assert( isInputRange!(S[]));
1646     static assert( hasLvalueElements!(S[]));
1647 }
1648 
1649 /**
1650 Yields `true` if `R` has a `length` member that returns a value of `size_t`
1651 type. `R` does not have to be a range. If `R` is a range, algorithms in the
1652 standard library are only guaranteed to support `length` with type `size_t`.
1653 
1654 Note that `length` is an optional primitive as no range must implement it. Some
1655 ranges do not store their length explicitly, some cannot compute it without
1656 actually exhausting the range (e.g. socket streams), and some other ranges may
1657 be infinite.
1658 
1659 Although narrow string types (`char[]`, `wchar[]`, and their qualified
1660 derivatives) do define a `length` property, `hasLength` yields `false` for them.
1661 This is because a narrow string's length does not reflect the number of
1662 characters, but instead the number of encoding units, and as such is not useful
1663 with range-oriented algorithms. To use strings as random-access ranges with
1664 length, use $(REF representation, std, string) or $(REF byCodeUnit, std, utf).
1665 */
1666 template hasLength(R)
1667 {
1668     static if (is(typeof(((R* r) => r.length)(null)) Length))
1669         enum bool hasLength = is(Length == size_t) &&
1670                               !(isAutodecodableString!R && !isAggregateType!R);
1671     else
1672         enum bool hasLength = false;
1673 }
1674 
1675 ///
1676 @safe unittest
1677 {
1678     static assert(!hasLength!(char[]));
1679     static assert( hasLength!(int[]));
1680     static assert( hasLength!(inout(int)[]));
1681 
1682     struct A { size_t length() { return 0; } }
1683     struct B { @property size_t length() { return 0; } }
1684     static assert( hasLength!(A));
1685     static assert( hasLength!(B));
1686 }
1687 
1688 // test combinations which are invalid on some platforms
1689 @safe unittest
1690 {
1691     struct A { ulong length; }
1692     struct B { @property uint length() { return 0; } }
1693 
1694     static if (is(size_t == uint))
1695     {
1696         static assert(!hasLength!(A));
1697         static assert(hasLength!(B));
1698     }
1699     else static if (is(size_t == ulong))
1700     {
1701         static assert(hasLength!(A));
1702         static assert(!hasLength!(B));
1703     }
1704 }
1705 
1706 // test combinations which are invalid on all platforms
1707 @safe unittest
1708 {
1709     struct A { long length; }
1710     struct B { int length; }
1711     struct C { ubyte length; }
1712     struct D { char length; }
1713     static assert(!hasLength!(A));
1714     static assert(!hasLength!(B));
1715     static assert(!hasLength!(C));
1716     static assert(!hasLength!(D));
1717 }
1718 
1719 /**
1720 Returns `true` if `R` is an infinite input range. An
1721 infinite input range is an input range that has a statically-defined
1722 enumerated member called `empty` that is always `false`,
1723 for example:
1724 
1725 ----
1726 struct MyInfiniteRange
1727 {
1728     enum bool empty = false;
1729     ...
1730 }
1731 ----
1732  */
1733 
1734 template isInfinite(R)
1735 {
1736     static if (isInputRange!R && __traits(compiles, { enum e = R.empty; }))
1737         enum bool isInfinite = !R.empty;
1738     else
1739         enum bool isInfinite = false;
1740 }
1741 
1742 ///
1743 @safe unittest
1744 {
1745     import std.range : Repeat;
1746     static assert(!isInfinite!(int[]));
1747     static assert( isInfinite!(Repeat!(int)));
1748 }
1749 
1750 /**
1751 Returns `true` if `R` offers a slicing operator with integral boundaries
1752 that returns a forward range type.
1753 
1754 For finite ranges, the result of `opSlice` must be of the same type as the
1755 original range type. If the range defines `opDollar`, then it must support
1756 subtraction.
1757 
1758 For infinite ranges, when $(I not) using `opDollar`, the result of `opSlice`
1759 may be a forward range of any type. However, when using `opDollar`, the result
1760 of `opSlice` must be of the same type as the original range type.
1761 
1762 The following expression must be true for `hasSlicing` to be `true`:
1763 
1764 ----
1765     isForwardRange!R
1766     && !(isAutodecodableString!R && !isAggregateType!R)
1767     && is(typeof((R r) { return r[1 .. 1].length; } (R.init)) == size_t)
1768     && (is(typeof(lvalueOf!R[1 .. 1]) == R) || isInfinite!R)
1769     && (!is(typeof(lvalueOf!R[0 .. $])) || is(typeof(lvalueOf!R[0 .. $]) == R))
1770     && (!is(typeof(lvalueOf!R[0 .. $])) || isInfinite!R
1771         || is(typeof(lvalueOf!R[0 .. $ - 1]) == R))
1772     && is(typeof((ref R r)
1773     {
1774         static assert(isForwardRange!(typeof(r[1 .. 2])));
1775     }));
1776 ----
1777  */
1778 enum bool hasSlicing(R) = isForwardRange!R
1779     && !(isAutodecodableString!R && !isAggregateType!R)
1780     && is(typeof((R r) { return r[1 .. 1].length; } (R.init)) == size_t)
1781     && (is(typeof(lvalueOf!R[1 .. 1]) == R) || isInfinite!R)
1782     && (!is(typeof(lvalueOf!R[0 .. $])) || is(typeof(lvalueOf!R[0 .. $]) == R))
1783     && (!is(typeof(lvalueOf!R[0 .. $])) || isInfinite!R
1784         || is(typeof(lvalueOf!R[0 .. $ - 1]) == R))
1785     && is(typeof((ref R r)
1786     {
1787         static assert(isForwardRange!(typeof(r[1 .. 2])));
1788     }));
1789 
1790 ///
1791 @safe unittest
1792 {
1793     import std.range : takeExactly;
1794     static assert( hasSlicing!(int[]));
1795     static assert( hasSlicing!(const(int)[]));
1796     static assert(!hasSlicing!(const int[]));
1797     static assert( hasSlicing!(inout(int)[]));
1798     static assert(!hasSlicing!(inout int []));
1799     static assert( hasSlicing!(immutable(int)[]));
1800     static assert(!hasSlicing!(immutable int[]));
1801     static assert(!hasSlicing!string);
1802     static assert( hasSlicing!dstring);
1803 
1804     enum rangeFuncs = "@property int front();" ~
1805                       "void popFront();" ~
1806                       "@property bool empty();" ~
1807                       "@property auto save() { return this; }" ~
1808                       "@property size_t length();";
1809 
1810     struct A { mixin(rangeFuncs); int opSlice(size_t, size_t); }
1811     struct B { mixin(rangeFuncs); B opSlice(size_t, size_t); }
1812     struct C { mixin(rangeFuncs); @disable this(); C opSlice(size_t, size_t); }
1813     struct D { mixin(rangeFuncs); int[] opSlice(size_t, size_t); }
1814     static assert(!hasSlicing!(A));
1815     static assert( hasSlicing!(B));
1816     static assert( hasSlicing!(C));
1817     static assert(!hasSlicing!(D));
1818 
1819     struct InfOnes
1820     {
1821         enum empty = false;
1822         void popFront() {}
1823         @property int front() { return 1; }
1824         @property InfOnes save() { return this; }
1825         auto opSlice(size_t i, size_t j) { return takeExactly(this, j - i); }
1826         auto opSlice(size_t i, Dollar d) { return this; }
1827 
1828         struct Dollar {}
1829         Dollar opDollar() const { return Dollar.init; }
1830     }
1831 
1832     static assert(hasSlicing!InfOnes);
1833 }
1834 
1835 // https://issues.dlang.org/show_bug.cgi?id=24348
1836 @safe unittest
1837 {
1838     static struct Slice
1839     {
1840         size_t length;
1841         bool empty() => length == 0;
1842         int front() => 0;
1843         void popFront() { --length; }
1844         Slice save() => this;
1845     }
1846 
1847     static struct InfZeros
1848     {
1849         enum empty = false;
1850         int front() => 0;
1851         void popFront() {}
1852         InfZeros save() => this;
1853 
1854         Slice opIndex(size_t[2] bounds)
1855         {
1856             size_t i = bounds[0], j = bounds[1];
1857             size_t length = i <= j ? j - i : 0;
1858             return Slice(length);
1859         }
1860 
1861         size_t[2] opSlice(size_t dim : 0)(size_t i, size_t j) => [i, j];
1862     }
1863 
1864     static assert(hasSlicing!InfZeros);
1865 }
1866 
1867 /**
1868 This is a best-effort implementation of `length` for any kind of
1869 range.
1870 
1871 If `hasLength!Range`, simply returns `range.length` without
1872 checking `upTo` (when specified).
1873 
1874 Otherwise, walks the range through its length and returns the number
1875 of elements seen. Performes $(BIGOH n) evaluations of `range.empty`
1876 and `range.popFront()`, where `n` is the effective length of $(D
1877 range).
1878 
1879 The `upTo` parameter is useful to "cut the losses" in case
1880 the interest is in seeing whether the range has at least some number
1881 of elements. If the parameter `upTo` is specified, stops if $(D
1882 upTo) steps have been taken and returns `upTo`.
1883 
1884 Infinite ranges are compatible, provided the parameter `upTo` is
1885 specified, in which case the implementation simply returns upTo.
1886  */
1887 auto walkLength(Range)(Range range)
1888 if (isInputRange!Range && !isInfinite!Range)
1889 {
1890     static if (hasLength!Range)
1891         return range.length;
1892     else
1893     {
1894         size_t result;
1895         static if (autodecodeStrings && isNarrowString!Range)
1896         {
1897             import std.utf : codeUnitLimit;
1898             result = range.length;
1899             foreach (const i, const c; range)
1900             {
1901                 if (c >= codeUnitLimit!Range)
1902                 {
1903                     result = i;
1904                     break;
1905                 }
1906             }
1907             range = range[result .. $];
1908         }
1909         for ( ; !range.empty ; range.popFront() )
1910             ++result;
1911         return result;
1912     }
1913 }
1914 /// ditto
1915 auto walkLength(Range)(Range range, const size_t upTo)
1916 if (isInputRange!Range)
1917 {
1918     static if (hasLength!Range)
1919         return range.length;
1920     else static if (isInfinite!Range)
1921         return upTo;
1922     else
1923     {
1924         size_t result;
1925         static if (autodecodeStrings && isNarrowString!Range)
1926         {
1927             import std.utf : codeUnitLimit;
1928             result = upTo > range.length ? range.length : upTo;
1929             foreach (const i, const c; range[0 .. result])
1930             {
1931                 if (c >= codeUnitLimit!Range)
1932                 {
1933                     result = i;
1934                     break;
1935                 }
1936             }
1937             range = range[result .. $];
1938         }
1939         for ( ; result < upTo && !range.empty ; range.popFront() )
1940             ++result;
1941         return result;
1942     }
1943 }
1944 
1945 ///
1946 @safe unittest
1947 {
1948     import std.range : iota;
1949 
1950     assert(10.iota.walkLength == 10);
1951     // iota has a length function, and therefore the
1952     // doesn't have to be walked, and the upTo
1953     // parameter is ignored
1954     assert(10.iota.walkLength(5) == 10);
1955 }
1956 
1957 @safe unittest
1958 {
1959     import std.algorithm.iteration : filter;
1960     import std.range : recurrence, take;
1961 
1962     //hasLength Range
1963     int[] a = [ 1, 2, 3 ];
1964     assert(walkLength(a) == 3);
1965     assert(walkLength(a, 0) == 3);
1966     assert(walkLength(a, 2) == 3);
1967     assert(walkLength(a, 4) == 3);
1968 
1969     //Forward Range
1970     auto b = filter!"true"([1, 2, 3, 4]);
1971     assert(b.walkLength() == 4);
1972     assert(b.walkLength(0) == 0);
1973     assert(b.walkLength(2) == 2);
1974     assert(b.walkLength(4) == 4);
1975     assert(b.walkLength(6) == 4);
1976 
1977     //Infinite Range
1978     auto fibs = recurrence!"a[n-1] + a[n-2]"(1, 1);
1979     assert(!__traits(compiles, fibs.walkLength()));
1980     assert(fibs.take(10).walkLength() == 10);
1981     assert(fibs.walkLength(55) == 55);
1982 }
1983 
1984 /**
1985     `popFrontN` eagerly advances `r` itself (not a copy) up to `n` times
1986     (by calling `r.popFront`). `popFrontN` takes `r` by `ref`,
1987     so it mutates the original range. Completes in $(BIGOH 1) steps for ranges
1988     that support slicing and have length.
1989     Completes in $(BIGOH n) time for all other ranges.
1990 
1991     `popBackN` behaves the same as `popFrontN` but instead removes
1992     elements from the back of the (bidirectional) range instead of the front.
1993 
1994     Returns:
1995     How much `r` was actually advanced, which may be less than `n` if
1996     `r` did not have at least `n` elements.
1997 
1998     See_Also: $(REF drop, std, range), $(REF dropBack, std, range)
1999 */
2000 size_t popFrontN(Range)(ref Range r, size_t n)
2001 if (isInputRange!Range)
2002 {
2003     static if (hasLength!Range)
2004     {
2005         n = cast(size_t) (n < r.length ? n : r.length);
2006     }
2007 
2008     static if (hasSlicing!Range && is(typeof(r = r[n .. $])))
2009     {
2010         r = r[n .. $];
2011     }
2012     else static if (hasSlicing!Range && hasLength!Range) //TODO: Remove once hasSlicing forces opDollar.
2013     {
2014         r = r[n .. r.length];
2015     }
2016     else
2017     {
2018         static if (hasLength!Range)
2019         {
2020             foreach (i; 0 .. n)
2021                 r.popFront();
2022         }
2023         else
2024         {
2025             foreach (i; 0 .. n)
2026             {
2027                 if (r.empty) return i;
2028                 r.popFront();
2029             }
2030         }
2031     }
2032     return n;
2033 }
2034 
2035 /// ditto
2036 size_t popBackN(Range)(ref Range r, size_t n)
2037 if (isBidirectionalRange!Range)
2038 {
2039     static if (hasLength!Range)
2040     {
2041         n = cast(size_t) (n < r.length ? n : r.length);
2042     }
2043 
2044     static if (hasSlicing!Range && is(typeof(r = r[0 .. $ - n])))
2045     {
2046         r = r[0 .. $ - n];
2047     }
2048     else static if (hasSlicing!Range && hasLength!Range) //TODO: Remove once hasSlicing forces opDollar.
2049     {
2050         r = r[0 .. r.length - n];
2051     }
2052     else
2053     {
2054         static if (hasLength!Range)
2055         {
2056             foreach (i; 0 .. n)
2057                 r.popBack();
2058         }
2059         else
2060         {
2061             foreach (i; 0 .. n)
2062             {
2063                 if (r.empty) return i;
2064                 r.popBack();
2065             }
2066         }
2067     }
2068     return n;
2069 }
2070 
2071 ///
2072 @safe unittest
2073 {
2074     int[] a = [ 1, 2, 3, 4, 5 ];
2075     a.popFrontN(2);
2076     assert(a == [ 3, 4, 5 ]);
2077     a.popFrontN(7);
2078     assert(a == [ ]);
2079 }
2080 
2081 ///
2082 @safe unittest
2083 {
2084     import std.algorithm.comparison : equal;
2085     import std.range : iota;
2086     auto LL = iota(1L, 7L);
2087     auto r = popFrontN(LL, 2);
2088     assert(equal(LL, [3L, 4L, 5L, 6L]));
2089     assert(r == 2);
2090 }
2091 
2092 ///
2093 @safe unittest
2094 {
2095     int[] a = [ 1, 2, 3, 4, 5 ];
2096     a.popBackN(2);
2097     assert(a == [ 1, 2, 3 ]);
2098     a.popBackN(7);
2099     assert(a == [ ]);
2100 }
2101 
2102 ///
2103 @safe unittest
2104 {
2105     import std.algorithm.comparison : equal;
2106     import std.range : iota;
2107     auto LL = iota(1L, 7L);
2108     auto r = popBackN(LL, 2);
2109     assert(equal(LL, [1L, 2L, 3L, 4L]));
2110     assert(r == 2);
2111 }
2112 
2113 /**
2114     Eagerly advances `r` itself (not a copy) exactly `n` times (by
2115     calling `r.popFront`). `popFrontExactly` takes `r` by `ref`,
2116     so it mutates the original range. Completes in $(BIGOH 1) steps for ranges
2117     that support slicing, and have either length or are infinite.
2118     Completes in $(BIGOH n) time for all other ranges.
2119 
2120     Note: Unlike $(LREF popFrontN), `popFrontExactly` will assume that the
2121     range holds at least `n` elements. This makes `popFrontExactly`
2122     faster than `popFrontN`, but it also means that if `range` does
2123     not contain at least `n` elements, it will attempt to call `popFront`
2124     on an empty range, which is undefined behavior. So, only use
2125     `popFrontExactly` when it is guaranteed that `range` holds at least
2126     `n` elements.
2127 
2128     `popBackExactly` will behave the same but instead removes elements from
2129     the back of the (bidirectional) range instead of the front.
2130 
2131     See_Also: $(REF dropExactly, std, range), $(REF dropBackExactly, std, range)
2132 */
2133 void popFrontExactly(Range)(ref Range r, size_t n)
2134 if (isInputRange!Range)
2135 {
2136     static if (hasLength!Range)
2137         assert(n <= r.length, "range is smaller than amount of items to pop");
2138 
2139     static if (hasSlicing!Range && is(typeof(r = r[n .. $])))
2140         r = r[n .. $];
2141     else static if (hasSlicing!Range && hasLength!Range) //TODO: Remove once hasSlicing forces opDollar.
2142         r = r[n .. r.length];
2143     else
2144         foreach (i; 0 .. n)
2145             r.popFront();
2146 }
2147 
2148 /// ditto
2149 void popBackExactly(Range)(ref Range r, size_t n)
2150 if (isBidirectionalRange!Range)
2151 {
2152     static if (hasLength!Range)
2153         assert(n <= r.length, "range is smaller than amount of items to pop");
2154 
2155     static if (hasSlicing!Range && is(typeof(r = r[0 .. $ - n])))
2156         r = r[0 .. $ - n];
2157     else static if (hasSlicing!Range && hasLength!Range) //TODO: Remove once hasSlicing forces opDollar.
2158         r = r[0 .. r.length - n];
2159     else
2160         foreach (i; 0 .. n)
2161             r.popBack();
2162 }
2163 
2164 ///
2165 @safe unittest
2166 {
2167     import std.algorithm.comparison : equal;
2168     import std.algorithm.iteration : filterBidirectional;
2169 
2170     auto a = [1, 2, 3];
2171     a.popFrontExactly(1);
2172     assert(a == [2, 3]);
2173     a.popBackExactly(1);
2174     assert(a == [2]);
2175 
2176     string s = "日本語";
2177     s.popFrontExactly(1);
2178     assert(s == "本語");
2179     s.popBackExactly(1);
2180     assert(s == "本");
2181 
2182     auto bd = filterBidirectional!"true"([1, 2, 3]);
2183     bd.popFrontExactly(1);
2184     assert(bd.equal([2, 3]));
2185     bd.popBackExactly(1);
2186     assert(bd.equal([2]));
2187 }
2188 
2189 /**
2190    Moves the front of `r` out and returns it.
2191 
2192    If `r.front` is a struct with a destructor or copy constructor defined, it
2193    is reset to its `.init` value after its value is moved. Otherwise, it is
2194    left unchanged.
2195 
2196    In either case, `r.front` is left in a destroyable state that does not
2197    allocate any resources.
2198 */
2199 ElementType!R moveFront(R)(R r)
2200 {
2201     static if (is(typeof(&r.moveFront)))
2202     {
2203         return r.moveFront();
2204     }
2205     else static if (!hasElaborateCopyConstructor!(ElementType!R))
2206     {
2207         return r.front;
2208     }
2209     else static if (is(typeof(&(r.front())) == ElementType!R*))
2210     {
2211         import std.algorithm.mutation : move;
2212         return move(r.front);
2213     }
2214     else
2215     {
2216         static assert(0,
2217                 "Cannot move front of a range with a postblit and an rvalue front.");
2218     }
2219 }
2220 
2221 ///
2222 @safe unittest
2223 {
2224     auto a = [ 1, 2, 3 ];
2225     assert(moveFront(a) == 1);
2226     assert(a.length == 3);
2227 
2228     // define a perfunctory input range
2229     struct InputRange
2230     {
2231         enum bool empty = false;
2232         enum int front = 7;
2233         void popFront() {}
2234         int moveFront() { return 43; }
2235     }
2236     InputRange r;
2237     // calls r.moveFront
2238     assert(moveFront(r) == 43);
2239 }
2240 
2241 @safe unittest
2242 {
2243     struct R
2244     {
2245         @property ref int front() { static int x = 42; return x; }
2246         this(this){}
2247     }
2248     R r;
2249     assert(moveFront(r) == 42);
2250 }
2251 
2252 /**
2253    Moves the back of `r` out and returns it. Leaves `r.back` in a
2254    destroyable state that does not allocate any resources (usually equal
2255    to its `.init` value).
2256 */
2257 ElementType!R moveBack(R)(R r)
2258 {
2259     static if (is(typeof(&r.moveBack)))
2260     {
2261         return r.moveBack();
2262     }
2263     else static if (!hasElaborateCopyConstructor!(ElementType!R))
2264     {
2265         return r.back;
2266     }
2267     else static if (is(typeof(&(r.back())) == ElementType!R*))
2268     {
2269         import std.algorithm.mutation : move;
2270         return move(r.back);
2271     }
2272     else
2273     {
2274         static assert(0,
2275                 "Cannot move back of a range with a postblit and an rvalue back.");
2276     }
2277 }
2278 
2279 ///
2280 @safe unittest
2281 {
2282     struct TestRange
2283     {
2284         int payload = 5;
2285         @property bool empty() { return false; }
2286         @property TestRange save() { return this; }
2287         @property ref int front() return { return payload; }
2288         @property ref int back() return { return payload; }
2289         void popFront() { }
2290         void popBack() { }
2291     }
2292     static assert(isBidirectionalRange!TestRange);
2293     TestRange r;
2294     auto x = moveBack(r);
2295     assert(x == 5);
2296 }
2297 
2298 /**
2299    Moves element at index `i` of `r` out and returns it. Leaves $(D
2300    r[i]) in a destroyable state that does not allocate any resources
2301    (usually equal to its `.init` value).
2302 */
2303 ElementType!R moveAt(R)(R r, size_t i)
2304 {
2305     static if (is(typeof(&r.moveAt)))
2306     {
2307         return r.moveAt(i);
2308     }
2309     else static if (!hasElaborateCopyConstructor!(ElementType!(R)))
2310     {
2311         return r[i];
2312     }
2313     else static if (is(typeof(&r[i]) == ElementType!R*))
2314     {
2315         import std.algorithm.mutation : move;
2316         return move(r[i]);
2317     }
2318     else
2319     {
2320         static assert(0,
2321                 "Cannot move element of a range with a postblit and rvalue elements.");
2322     }
2323 }
2324 
2325 ///
2326 @safe unittest
2327 {
2328     auto a = [1,2,3,4];
2329     foreach (idx, it; a)
2330     {
2331         assert(it == moveAt(a, idx));
2332     }
2333 }
2334 
2335 @safe unittest
2336 {
2337     import std.internal.test.dummyrange;
2338 
2339     foreach (DummyType; AllDummyRanges)
2340     {
2341         auto d = DummyType.init;
2342         assert(moveFront(d) == 1);
2343 
2344         static if (isBidirectionalRange!DummyType)
2345         {
2346             assert(moveBack(d) == 10);
2347         }
2348 
2349         static if (isRandomAccessRange!DummyType)
2350         {
2351             assert(moveAt(d, 2) == 3);
2352         }
2353     }
2354 }
2355 
2356 /**
2357 Implements the range interface primitive `empty` for types that
2358 obey $(LREF hasLength) property and for narrow strings. Due to the
2359 fact that nonmember functions can be called with the first argument
2360 using the dot notation, `a.empty` is equivalent to `empty(a)`.
2361  */
2362 @property bool empty(T)(auto ref scope T a)
2363 if (is(typeof(a.length) : size_t))
2364 {
2365     return !a.length;
2366 }
2367 
2368 ///
2369 @safe pure nothrow unittest
2370 {
2371     auto a = [ 1, 2, 3 ];
2372     assert(!a.empty);
2373     assert(a[3 .. $].empty);
2374 
2375     int[string] b;
2376     assert(b.empty);
2377     b["zero"] = 0;
2378     assert(!b.empty);
2379 }
2380 
2381 /**
2382 Implements the range interface primitive `save` for built-in
2383 arrays. Due to the fact that nonmember functions can be called with
2384 the first argument using the dot notation, `array.save` is
2385 equivalent to `save(array)`. The function does not duplicate the
2386 content of the array, it simply returns its argument.
2387  */
2388 @property inout(T)[] save(T)(return scope inout(T)[] a) @safe pure nothrow @nogc
2389 {
2390     return a;
2391 }
2392 
2393 ///
2394 @safe pure nothrow unittest
2395 {
2396     auto a = [ 1, 2, 3 ];
2397     auto b = a.save;
2398     assert(b is a);
2399 }
2400 
2401 /**
2402 Implements the range interface primitive `popFront` for built-in
2403 arrays. Due to the fact that nonmember functions can be called with
2404 the first argument using the dot notation, `array.popFront` is
2405 equivalent to `popFront(array)`. For $(GLOSSARY narrow strings),
2406 `popFront` automatically advances to the next $(GLOSSARY code
2407 point).
2408 */
2409 void popFront(T)(scope ref inout(T)[] a) @safe pure nothrow @nogc
2410 if (!isAutodecodableString!(T[]) && !is(T[] == void[]))
2411 {
2412     assert(a.length, "Attempting to popFront() past the end of an array of " ~ T.stringof);
2413     a = a[1 .. $];
2414 }
2415 
2416 ///
2417 @safe pure nothrow unittest
2418 {
2419     auto a = [ 1, 2, 3 ];
2420     a.popFront();
2421     assert(a == [ 2, 3 ]);
2422 }
2423 
2424 @safe unittest
2425 {
2426     static assert(!is(typeof({          int[4] a; popFront(a); })));
2427     static assert(!is(typeof({ immutable int[] a; popFront(a); })));
2428     static assert(!is(typeof({          void[] a; popFront(a); })));
2429 }
2430 
2431 /// ditto
2432 void popFront(C)(scope ref inout(C)[] str) @trusted pure nothrow
2433 if (isAutodecodableString!(C[]))
2434 {
2435     import std.algorithm.comparison : min;
2436 
2437     assert(str.length, "Attempting to popFront() past the end of an array of " ~ C.stringof);
2438 
2439     static if (is(immutable C == immutable char))
2440     {
2441         static immutable ubyte[] charWidthTab = [
2442             2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2443             2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2444             3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
2445             4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 1, 1
2446         ];
2447 
2448         immutable c = str[0];
2449         immutable charWidth = c < 192 ? 1 : charWidthTab.ptr[c - 192];
2450         str = str.ptr[min(str.length, charWidth) .. str.length];
2451     }
2452     else static if (is(immutable C == immutable wchar))
2453     {
2454         immutable u = str[0];
2455         immutable seqLen = 1 + (u >= 0xD800 && u <= 0xDBFF);
2456         str = str.ptr[min(seqLen, str.length) .. str.length];
2457     }
2458     else static assert(0, "Bad template constraint.");
2459 }
2460 
2461 @safe pure unittest
2462 {
2463     import std.meta : AliasSeq;
2464 
2465     static foreach (S; AliasSeq!(string, wstring, dstring))
2466     {{
2467         S s = "\xC2\xA9hello";
2468         s.popFront();
2469         assert(s == "hello");
2470 
2471         S str = "hello\U00010143\u0100\U00010143";
2472         foreach (dchar c; ['h', 'e', 'l', 'l', 'o', '\U00010143', '\u0100', '\U00010143'])
2473         {
2474             assert(str.front == c);
2475             str.popFront();
2476         }
2477         assert(str.empty);
2478 
2479         static assert(!is(typeof({          immutable S a; popFront(a); })));
2480         static assert(!is(typeof({ typeof(S.init[0])[4] a; popFront(a); })));
2481     }}
2482 
2483     C[] _eatString(C)(C[] str)
2484     {
2485         while (!str.empty)
2486             str.popFront();
2487 
2488         return str;
2489     }
2490     enum checkCTFE = _eatString("ウェブサイト@La_Verité.com");
2491     static assert(checkCTFE.empty);
2492     enum checkCTFEW = _eatString("ウェブサイト@La_Verité.com"w);
2493     static assert(checkCTFEW.empty);
2494 }
2495 
2496 // https://issues.dlang.org/show_bug.cgi?id=16090
2497 @safe unittest
2498 {
2499     string s = "\u00E4";
2500     assert(s.length == 2);
2501     s = s[0 .. 1];
2502     assert(s.length == 1);
2503     s.popFront;
2504     assert(s.empty);
2505 }
2506 
2507 @safe unittest
2508 {
2509     wstring s = "\U00010000";
2510     assert(s.length == 2);
2511     s = s[0 .. 1];
2512     assert(s.length == 1);
2513     s.popFront;
2514     assert(s.empty);
2515 }
2516 
2517 /**
2518 Implements the range interface primitive `popBack` for built-in
2519 arrays. Due to the fact that nonmember functions can be called with
2520 the first argument using the dot notation, `array.popBack` is
2521 equivalent to `popBack(array)`. For $(GLOSSARY narrow strings), $(D
2522 popFront) automatically eliminates the last $(GLOSSARY code point).
2523 */
2524 void popBack(T)(scope ref inout(T)[] a) @safe pure nothrow @nogc
2525 if (!isAutodecodableString!(T[]) && !is(T[] == void[]))
2526 {
2527     assert(a.length);
2528     a = a[0 .. $ - 1];
2529 }
2530 
2531 ///
2532 @safe pure nothrow unittest
2533 {
2534     auto a = [ 1, 2, 3 ];
2535     a.popBack();
2536     assert(a == [ 1, 2 ]);
2537 }
2538 
2539 @safe unittest
2540 {
2541     static assert(!is(typeof({ immutable int[] a; popBack(a); })));
2542     static assert(!is(typeof({          int[4] a; popBack(a); })));
2543     static assert(!is(typeof({          void[] a; popBack(a); })));
2544 }
2545 
2546 /// ditto
2547 void popBack(T)(scope ref inout(T)[] a) @safe pure
2548 if (isAutodecodableString!(T[]))
2549 {
2550     import std.utf : strideBack;
2551     assert(a.length, "Attempting to popBack() past the front of an array of " ~ T.stringof);
2552     a = a[0 .. $ - strideBack(a, $)];
2553 }
2554 
2555 @safe pure unittest
2556 {
2557     import std.meta : AliasSeq;
2558 
2559     static foreach (S; AliasSeq!(string, wstring, dstring))
2560     {{
2561         S s = "hello\xE2\x89\xA0";
2562         s.popBack();
2563         assert(s == "hello");
2564         S s3 = "\xE2\x89\xA0";
2565         auto c = s3.back;
2566         assert(c == cast(dchar)'\u2260');
2567         s3.popBack();
2568         assert(s3 == "");
2569 
2570         S str = "\U00010143\u0100\U00010143hello";
2571         foreach (dchar ch; ['o', 'l', 'l', 'e', 'h', '\U00010143', '\u0100', '\U00010143'])
2572         {
2573             assert(str.back == ch);
2574             str.popBack();
2575         }
2576         assert(str.empty);
2577 
2578         static assert(!is(typeof({          immutable S a; popBack(a); })));
2579         static assert(!is(typeof({ typeof(S.init[0])[4] a; popBack(a); })));
2580     }}
2581 }
2582 
2583 /**
2584 EXPERIMENTAL: to try out removing autodecoding, set the version
2585 `NoAutodecodeStrings`. Most things are expected to fail with this version
2586 currently.
2587 */
2588 version (NoAutodecodeStrings)
2589 {
2590     enum autodecodeStrings = false;
2591 }
2592 else
2593 {
2594     ///
2595     enum autodecodeStrings = true;
2596 }
2597 
2598 /**
2599 Implements the range interface primitive `front` for built-in
2600 arrays. Due to the fact that nonmember functions can be called with
2601 the first argument using the dot notation, `array.front` is
2602 equivalent to `front(array)`. For $(GLOSSARY narrow strings), $(D
2603 front) automatically returns the first $(GLOSSARY code point) as _a $(D
2604 dchar).
2605 */
2606 @property ref inout(T) front(T)(return scope inout(T)[] a) @safe pure nothrow @nogc
2607 if (!isAutodecodableString!(T[]) && !is(T[] == void[]))
2608 {
2609     assert(a.length, "Attempting to fetch the front of an empty array of " ~ T.stringof);
2610     return a[0];
2611 }
2612 
2613 ///
2614 @safe pure nothrow unittest
2615 {
2616     int[] a = [ 1, 2, 3 ];
2617     assert(a.front == 1);
2618 }
2619 
2620 @safe pure nothrow unittest
2621 {
2622     auto a = [ 1, 2 ];
2623     a.front = 4;
2624     assert(a.front == 4);
2625     assert(a == [ 4, 2 ]);
2626 
2627     immutable b = [ 1, 2 ];
2628     assert(b.front == 1);
2629 
2630     int[2] c = [ 1, 2 ];
2631     assert(c.front == 1);
2632 }
2633 
2634 /// ditto
2635 @property dchar front(T)(scope const(T)[] a) @safe pure
2636 if (isAutodecodableString!(T[]))
2637 {
2638     import std.utf : decode;
2639     assert(a.length, "Attempting to fetch the front of an empty array of " ~ T.stringof);
2640     size_t i = 0;
2641     return decode(a, i);
2642 }
2643 
2644 /**
2645 Implements the range interface primitive `back` for built-in
2646 arrays. Due to the fact that nonmember functions can be called with
2647 the first argument using the dot notation, `array.back` is
2648 equivalent to `back(array)`. For $(GLOSSARY narrow strings), $(D
2649 back) automatically returns the last $(GLOSSARY code point) as _a $(D
2650 dchar).
2651 */
2652 @property ref inout(T) back(T)(return scope inout(T)[] a) @safe pure nothrow @nogc
2653 if (!isAutodecodableString!(T[]) && !is(T[] == void[]))
2654 {
2655     assert(a.length, "Attempting to fetch the back of an empty array of " ~ T.stringof);
2656     return a[$ - 1];
2657 }
2658 
2659 ///
2660 @safe pure nothrow unittest
2661 {
2662     int[] a = [ 1, 2, 3 ];
2663     assert(a.back == 3);
2664     a.back += 4;
2665     assert(a.back == 7);
2666 }
2667 
2668 @safe pure nothrow unittest
2669 {
2670     immutable b = [ 1, 2, 3 ];
2671     assert(b.back == 3);
2672 
2673     int[3] c = [ 1, 2, 3 ];
2674     assert(c.back == 3);
2675 }
2676 
2677 /// ditto
2678 // Specialization for strings
2679 @property dchar back(T)(scope const(T)[] a) @safe pure
2680 if (isAutodecodableString!(T[]))
2681 {
2682     import std.utf : decode, strideBack;
2683     assert(a.length, "Attempting to fetch the back of an empty array of " ~ T.stringof);
2684     size_t i = a.length - strideBack(a, a.length);
2685     return decode(a, i);
2686 }
2687 
2688 /*
2689 Implements `length` for a range by forwarding it to `member`.
2690 */
2691 package(std) mixin template ImplementLength(alias member)
2692 {
2693     static if (hasLength!(typeof(member)))
2694     {
2695         @property auto length()
2696         {
2697             return member.length;
2698         }
2699         alias opDollar = length;
2700     }
2701 }
2702 
2703 @safe unittest
2704 {
2705     import std.meta : AliasSeq;
2706 
2707     foreach (alias E; AliasSeq!(noreturn, const(noreturn), immutable(noreturn) ))
2708     {
2709         alias R = E[];
2710 
2711         static assert(isInputRange!R);
2712         static assert(isForwardRange!R);
2713         static assert(isBidirectionalRange!R);
2714         static assert(isRandomAccessRange!R);
2715     }
2716 
2717     static assert(isOutputRange!(noreturn[], noreturn));
2718 }