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 }