1 module nxt.container.dynamic_array; 2 3 import std.experimental.allocator.gc_allocator : GCAllocator; 4 import nxt.allocator_traits : isAllocator; 5 import nxt.my_mallocator : Mallocator; 6 7 /** Array type with deterministic control of memory. The memory allocated for 8 the array is reclaimed as soon as possible; there is no reliance on the 9 garbage collector. 10 11 A null `Allocator` means to qcmeman functions. TODO use `Mallocator` by default. 12 13 TODO: Use Allocator in place of import nxt.qcmeman : malloc, realloc, free, 14 gc_addRange, gc_removeRange; 15 16 TODO: Replace `withCapacity` with `void capacity(size_t)` like D arrays. 17 18 TODO: Generalize to bucket array either via specialized allocator to by extra 19 Storage class given as template type parameter. Integrate `nxt.bucket_array` for 20 details. 21 22 TODO: Use `std.bitmanip.BitArray` for array container storing boolean 23 values. 24 25 TODO: Add OutputRange.writer support as 26 https://github.com/burner/StringBuffer/blob/master/source/stringbuffer.d#L45 27 28 TODO: Use `std.traits.areCopyCompatibleArrays` 29 30 See also https://github.com/izabera/s 31 */ 32 @safe struct DynamicArray(T, Allocator = Mallocator, Capacity = size_t) 33 if (!is(immutable T == immutable bool) && // TODO: use `BitArray` instead 34 (is(Capacity == ulong) || // 3 64-bit words 35 is(Capacity == uint)) && // 2 64-bit words 36 isAllocator!Allocator) 37 { 38 import core.internal.traits : Unqual; 39 40 /** Growth factor P/Q. 41 https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md#memory-handling 42 Use 1.5 like Facebook's `fbvector` does. 43 */ 44 enum _growthP = 3; // numerator 45 /// ditto 46 enum _growthQ = 2; // denominator 47 48 // import core.exception : onOutOfMemoryError; 49 import core.stdc.string : memset; 50 import core.internal.traits : hasElaborateDestructor; 51 import std.experimental.allocator : makeArray; 52 import std.range.primitives : isInputRange, ElementType, hasLength, hasSlicing, isInfinite; 53 import std.traits : hasIndirections, hasAliasing, 54 isMutable, TemplateOf, isArray, isAssignable, isType, hasFunctionAttributes, isIterable, isPointer; 55 import core.lifetime : emplace, move, moveEmplace; 56 57 import nxt.qcmeman : malloc, realloc, free, gc_addRange, gc_removeRange; 58 import nxt.container.traits : mustAddGCRange; 59 60 /// Mutable element type. 61 private alias MT = Unqual!T; 62 63 /// Is `true` if `U` can be assigned to the elements of `this`. 64 enum isElementAssignable(U) = isAssignable!(MT, U); 65 66 /// Returns: an array of length `initialLength` with all elements default-initialized to `ElementType.init`. 67 static typeof(this) withLength()(in size_t initialLength) /* template-lazy */ 68 => withCapacityLengthZero(initialLength, initialLength, true); 69 70 /// Returns: an array with initial capacity `initialCapacity`. 71 static typeof(this) withCapacity()(in size_t initialCapacity) /* template-lazy */ 72 => withCapacityLengthZero(initialCapacity, 0, false); 73 74 static if (__traits(isCopyable, T)) 75 { 76 /** Construct using 77 * - initial length `length`, 78 * - and value of all elements `elementValue`. 79 */ 80 static typeof(this) withLengthElementValue()(in size_t length, T elementValue) 81 in(length <= Capacity.max) 82 { 83 version(D_Coverage) {} else pragma(inline, true); 84 return typeof(return)(Store(typeof(this).allocateWithValue(length, move(elementValue)), 85 cast(Capacity)length, 86 cast(Capacity)length)); 87 } 88 } 89 90 /** Construct using 91 - initial capacity `capacity`, 92 - initial length `length`, 93 - and default-flag `initFlag`. 94 */ 95 private static typeof(this) withCapacityLengthZero()(in size_t capacity, in size_t length, in bool initFlag) @trusted /* template-lazy */ 96 in(capacity >= length) 97 in(capacity <= Capacity.max) 98 => typeof(return)(Store(typeof(this).allocate(capacity, initFlag), 99 cast(Capacity)capacity, 100 cast(Capacity)length)); 101 102 /** Emplace `thatPtr` with elements moved from `elements`. */ 103 static ref typeof(this) emplaceWithMovedElements()(typeof(this)* thatPtr, scope T[] elements) @system /* template-lazy */ 104 { 105 immutable length = elements.length; 106 thatPtr._store.ptr = typeof(this).allocate(length, false); 107 thatPtr._store.capacity = cast(Capacity)length; 108 thatPtr._store.length = cast(Capacity)length; 109 foreach (immutable i, ref e; elements) 110 moveEmplace(e, thatPtr._mptr[i]); 111 return *thatPtr; 112 } 113 114 /** Emplace `thatPtr` with elements copied from `elements`. */ 115 static ref typeof(this) emplaceWithCopiedElements()(typeof(this)* thatPtr, scope const(T)[] elements) @system /* template-lazy */ 116 if (__traits(isCopyable, T)) 117 { 118 immutable length = elements.length; 119 thatPtr._store.ptr = typeof(this).allocate(length, false); 120 thatPtr._store.capacity = cast(Capacity)length; 121 thatPtr._store.length = cast(Capacity)length; 122 foreach (immutable i, ref e; elements) 123 thatPtr._mptr[i] = cast(T)e; // TODO: restrict this function using a 124 // T-trait where this cast can be @trusted 125 return *thatPtr; 126 } 127 128 private this(Store store) 129 { 130 _store = store; 131 } 132 133 /// Construct from uncopyable element `value`. 134 this()(T value) @trusted /* template-lazy */ 135 if (!__traits(isCopyable, T)) 136 { 137 _store.ptr = typeof(this).allocate(1, false); 138 _store.capacity = 1; 139 _store.length = 1; 140 moveEmplace(value, _mptr[0]); // TODO: remove `moveEmplace` when compiler does it for us 141 } 142 143 /// Construct from copyable element `value`. 144 this(U)(U value) @trusted 145 if (__traits(isCopyable, U) && 146 isElementAssignable!U) 147 { 148 _store.ptr = typeof(this).allocate(1, false); 149 _store.capacity = 1; 150 _store.length = 1; 151 emplace(&_mptr[0], value); 152 } 153 154 static if (__traits(isCopyable, T) && 155 !is(T == union)) // forbid copying of unions such as `HybridBin` in hashmap.d 156 { 157 static typeof(this) withElements()(scope const T[] elements) @trusted /* template-lazy */ 158 { 159 immutable length = elements.length; 160 auto ptr = typeof(this).allocate(length, false); 161 162 foreach (immutable i, const element; elements) 163 // TODO: be more strict 164 // static if (hasIndirections!T) 165 // { 166 // ptr[i] = element; 167 // } 168 // else 169 // { 170 // ptr[i] = *cast(MT*)&element; 171 // } 172 ptr[i] = *cast(MT*)&element; 173 174 // ptr[0 .. length] = elements[]; 175 return typeof(return)(Store(ptr, 176 cast(Capacity)length, 177 cast(Capacity)length)); 178 } 179 180 /// Returns: shallow duplicate of `this`. 181 @property DynamicArray!(MT, Allocator, Capacity) dup()() const @trusted /* template-lazy */ 182 => typeof(this).withElements(this[]); 183 } 184 185 /// Construct from the element(s) of the dynamic array `values`. 186 this(U)(U[] values) @trusted 187 if (isElementAssignable!(U)) 188 { 189 // TODO: use import emplace_all instead 190 191 _store.ptr = allocate(values.length, false); 192 static if (!is(Capacity == size_t)) 193 assert(values.length <= Capacity.max, 194 "Minimum capacity doesn't fit in capacity type."); 195 _store.capacity = cast(Capacity)values.length; 196 197 foreach (index; 0 .. values.length) 198 static if (__traits(isPOD, T)) 199 _mptr[index] = values[index]; 200 else 201 move(values[index], _mptr[index]); 202 203 setLengthChecked(values.length); 204 } 205 206 /// Construct from the `n` number of element(s) in the static array `values`. 207 this(uint n, U)(U[n] values) @trusted 208 if (isElementAssignable!(U)) 209 { 210 // TODO: use import emplace_all instead 211 212 _store.ptr = allocate(values.length, false); 213 static assert(values.length <= Capacity.max); 214 _store.capacity = cast(Capacity)values.length; 215 216 static foreach (index; 0 .. values.length) 217 static if (__traits(isPOD, T)) 218 _mptr[index] = values[index]; 219 else 220 move(values[index], _mptr[index]); 221 222 setLengthChecked(values.length); 223 } 224 /// ditto 225 this(R)(scope R values) @trusted 226 if (// isRefIterable!R && 227 isElementAssignable!(ElementType!R) && 228 !isArray!R) 229 { 230 static if (hasLength!R) 231 { 232 reserve(values.length); 233 size_t index = 0; 234 foreach (ref value; values) 235 _mptr[index++] = value; 236 setLengthChecked(values.length); 237 } 238 else 239 foreach (ref value; values) 240 insertBack1(value); 241 } 242 243 /** Is `true` iff the iterable container `C` can be insert to `this`. 244 */ 245 private enum isInsertableContainer(C) = (is(C == struct) && // exclude class ranges for aliasing control 246 isRefIterable!C && // elements may be non-copyable 247 !isInfinite!C && 248 isElementAssignable!(ElementType!C)); 249 250 /// Construct from the elements `values`. 251 static typeof(this) withElementsOfRange_untested(R)(R values) @trusted 252 if (isInsertableContainer!R) 253 { 254 typeof(this) result; 255 256 static if (hasLength!R) 257 result.reserve(values.length); 258 259 static if (__traits(isPOD, ElementType!R) && 260 hasLength!R && 261 hasSlicing!R) 262 { 263 import std.algorithm.mutation : copy; 264 copy(values[0 .. values.length], 265 result._mptr[0 .. values.length]); // TODO: better to use foreach instead? 266 result.setLengthChecked(values.length); 267 } 268 else 269 { 270 static if (hasLength!R) 271 { 272 size_t i = 0; 273 foreach (ref value; move(values)) // TODO: remove `move` when compiler does it for us 274 static if (__traits(isPOD, typeof(value))) 275 result._mptr[i++] = value; 276 else 277 moveEmplace(value, result._mptr[i++]); 278 result.setLengthChecked(values.length); 279 } 280 else 281 { 282 // import std.algorithm.mutation : moveEmplaceAll; 283 /* TODO: optimize with `moveEmplaceAll` that does a raw copy and 284 * zeroing of values */ 285 foreach (ref value; move(values)) // TODO: remove `move` when compiler does it for us 286 static if (__traits(isPOD, ElementType!R)) 287 result.insertBack(value); 288 else 289 result.insertBackMove(value); // steal element 290 } 291 } 292 return result; 293 } 294 295 /// No default copying. 296 @disable this(this); 297 298 // TODO: this gives error in insertBack. why? 299 // void opAssign()(typeof(this) rhs) @trusted pure nothrow @nogc /* template-lazy */ 300 // { 301 // move(rhs, this); 302 // } 303 304 /** Destruct. 305 * 306 * TODO: what effect does have here? 307 * See_Also: https://github.com/atilaneves/automem/blob/master/source/automem/vector.d#L92 308 */ 309 ~this() nothrow @nogc /*TODO: scope*/ 310 { 311 releaseElementsStore(); 312 } 313 314 /// Empty. 315 void clear() @nogc 316 { 317 releaseElementsStore(); 318 resetInternalData(); 319 } 320 321 /// Release elements and internal store. 322 private void releaseElementsStore() @nogc @trusted 323 { 324 foreach (immutable index; 0 .. _store.length) 325 static if (hasElaborateDestructor!T) 326 .destroy(_mptr[index]); 327 else static if (is(T == class) || isPointer!T || hasIndirections!T) 328 _mptr[index] = T.init; // nullify any pointers 329 freeStore(); 330 } 331 332 /// Free internal store. 333 private void freeStore() @trusted 334 { 335 static if (mustAddGCRange!T) 336 gc_removeRange(_mptr); 337 free(_mptr); 338 } 339 340 /// Reset internal data. 341 private void resetInternalData() @nogc 342 { 343 version(D_Coverage) {} else pragma(inline, true); 344 _store.ptr = null; 345 _store.capacity = 0; 346 _store.length = 0; 347 } 348 349 /** Allocate heap region with `initialCapacity` number of elements of type `T`. 350 * 351 * If `initFlag` is `true` elements will be initialized 352 */ 353 private static MT* allocate(in size_t initialCapacity, in bool initFlag) @trusted 354 { 355 immutable size_t numBytes = initialCapacity * T.sizeof; 356 357 typeof(return) ptr = null; 358 if (initFlag) 359 { 360 static if (__traits(isZeroInit, T) && 361 __traits(hasMember, Allocator, "allocateZeroed") && 362 is(typeof(allocator.allocateZeroed(numBytes)) == void[])) 363 ptr = cast(typeof(return))(allocator.allocateZeroed(numBytes).ptr); 364 else 365 { 366 ptr = cast(typeof(return))(allocator.allocate(numBytes).ptr); 367 static if (__traits(isZeroInit, T)) 368 memset(ptr, 0, numBytes); 369 else 370 foreach (i; 0 .. initialCapacity) 371 ptr[i] = MT.init; 372 } 373 } 374 else 375 ptr = cast(typeof(return))(allocator.allocate(numBytes).ptr); 376 377 if (ptr is null && 378 initialCapacity >= 1 ) 379 // TODO: onOutOfMemoryError(); 380 return null; 381 382 static if (mustAddGCRange!T) 383 gc_addRange(ptr, numBytes); 384 385 return ptr; 386 } 387 388 static if (__traits(isCopyable, T)) 389 { 390 /** Allocate heap region with `initialCapacity` number of elements of type `T` all set to `elementValue`. 391 */ 392 private static MT* allocateWithValue(in size_t initialCapacity, T elementValue) @trusted 393 { 394 immutable size_t numBytes = initialCapacity * T.sizeof; 395 396 typeof(return) ptr = null; 397 ptr = allocator.makeArray!MT(initialCapacity, elementValue).ptr; // TODO: set length 398 if (ptr is null && 399 initialCapacity >= 1) 400 // TODO: onOutOfMemoryError(); 401 return null; 402 403 static if (mustAddGCRange!T) 404 gc_addRange(ptr, numBytes); 405 406 return ptr; 407 } 408 } 409 410 /** Comparison for equality. */ 411 bool opEquals()(const auto ref typeof(this) rhs) const scope /* template-lazy */ 412 { 413 version(LDC) pragma(inline, true); 414 return opSlice() == rhs.opSlice(); 415 } 416 417 /// ditto 418 pragma(inline, true) 419 bool opEquals(U)(const scope U[] rhs) const scope 420 if (is(typeof(T[].init == U[].init))) 421 => opSlice() == rhs; 422 423 /// Calculate D associative array (AA) key hash. 424 pragma(inline, true) 425 hash_t toHash()() const scope @trusted /* template-lazy */ 426 => .hashOf(length) + .hashOf(opSlice()); 427 428 static if (__traits(isCopyable, T)) 429 { 430 /** Construct a string representation of `this` at `sink`. 431 */ 432 void toString(Sink)(ref scope Sink sink) const scope /* template-lazy */ 433 { 434 import std.conv : to; 435 sink("["); 436 foreach (immutable index, ref value; opSlice()) 437 { 438 sink(to!string(value)); 439 if (index + 1 < length) { sink(", "); } // separator 440 } 441 sink("]"); 442 } 443 } 444 445 /// Check if empty. 446 pragma(inline, true) 447 bool empty() const @property scope => _store.length == 0; 448 449 /// Get length. 450 pragma(inline, true) 451 @property size_t length() const scope => _store.length; // can't be template-lazy 452 alias opDollar = length; /// ditto 453 454 /** Set length to `newLength`. 455 * 456 * If `newLength` < `length` elements are truncate. 457 * If `newLength` > `length` default-initialized elements are appended. 458 */ 459 @property void length(in size_t newLength) @trusted scope // can't template-lazy 460 { 461 if (newLength < length) // if truncatation 462 { 463 static if (hasElaborateDestructor!T) 464 foreach (immutable index; newLength .. _store.length) 465 .destroy(_mptr[index]); 466 else static if (mustAddGCRange!T) 467 foreach (immutable index; newLength .. _store.length) 468 _mptr[index] = T.init; // avoid GC mark-phase dereference 469 } 470 else 471 { 472 reserve(newLength); 473 static if (hasElaborateDestructor!T) 474 // TODO: remove when compiler does it for us 475 foreach (immutable index; _store.length .. newLength) 476 { 477 // TODO: remove when compiler does it for us: 478 static if (__traits(isCopyable, T)) 479 emplace(&_mptr[index], T.init); 480 else 481 { 482 auto _ = T.init; 483 moveEmplace(_, _mptr[index]); 484 } 485 } 486 else 487 _mptr[_store.length .. newLength] = T.init; 488 } 489 490 setLengthChecked(newLength); 491 } 492 493 /// Set capacity, checking for overflow when `Capacity` is not `size_t`. 494 private void setLengthChecked(in size_t newLength) scope 495 { 496 static if (!is(Capacity == size_t)) 497 assert(newLength <= Capacity.max, 498 "New length doesn't fit in capacity type."); 499 _store.length = cast(Capacity)newLength; 500 } 501 502 /// Get capacity. 503 pragma(inline, true) 504 @property size_t capacity() const scope => _store.capacity; // can't be template-lazy 505 506 /** Ensures sufficient capacity to accommodate for minimumCapacity number of 507 elements. If `minimumCapacity` < `capacity`, this method does nothing. 508 */ 509 size_t reserve(in size_t minimumCapacity) @trusted scope pure nothrow @nogc 510 { 511 static if (!is(Capacity == size_t)) 512 assert(minimumCapacity <= Capacity.max, 513 "Minimum capacity doesn't fit in capacity type."); 514 515 if (minimumCapacity <= capacity) 516 return capacity; 517 518 return reallocateAndSetCapacity(_growthP * minimumCapacity / _growthQ); 519 // static if (__VERSION__ >= 2098) import std.math.algebraic : nextPow2; else import std.math : nextPow2; 520 // reallocateAndSetCapacity(minimumCapacity.nextPow2); 521 } 522 523 /// Reallocate storage. 524 private size_t reallocateAndSetCapacity()(in size_t newCapacity) @trusted /* template-lazy */ 525 { 526 static if (!is(Capacity == size_t)) 527 assert(newCapacity <= Capacity.max, 528 "New capacity doesn't fit in capacity type."); 529 530 static if (mustAddGCRange!T) 531 gc_removeRange(_store.ptr); 532 533 _store.capacity = cast(Capacity)newCapacity; 534 _store.ptr = cast(T*)realloc(_mptr, T.sizeof * _store.capacity); 535 536 if (_store.ptr is null && 537 newCapacity >= 1) 538 // TODO: onOutOfMemoryError(); 539 return _store.capacity; 540 541 static if (mustAddGCRange!T) 542 gc_addRange(_store.ptr, _store.capacity * T.sizeof); 543 544 return _store.capacity; 545 } 546 547 /// Index support. 548 pragma(inline, true) 549 ref inout(T) opIndex()(in size_t i) inout return scope /* template-lazy */ 550 => opSlice()[i]; 551 552 /// Slice support. 553 pragma(inline, true) 554 inout(T)[] opSlice()(in size_t i, in size_t j) inout return scope /* template-lazy */ 555 => opSlice()[i .. j]; 556 /// ditto 557 pragma(inline, true) 558 inout(T)[] opSlice()() inout return scope @trusted /* template-lazy */ 559 => _store.ptr[0 .. _store.length]; 560 561 /// Index assignment support. 562 ref T opIndexAssign(U)(scope U value, in size_t i) @trusted return scope 563 { 564 static if (!__traits(isPOD, T)) 565 { 566 move(*(cast(MT*)(&value)), _mptr[i]); // TODO: is this correct? 567 return opSlice()[i]; 568 } 569 else static if ((is(T == class) || isPointer!T || hasIndirections!T) && 570 !isMutable!T) 571 static assert(0, "Cannot modify constant elements with indirections"); 572 else 573 return opSlice()[i] = value; 574 } 575 576 /// Slice assignment support. 577 pragma(inline, true) 578 T[] opSliceAssign(U)(scope U value) return scope 579 => opSlice()[] = value; 580 /// ditto 581 pragma(inline, true) 582 T[] opSliceAssign(U)(scope U value, in size_t i, in size_t j) return scope 583 => opSlice()[i .. j] = value; 584 585 /// Get reference to front element. 586 pragma(inline, true) 587 @property ref inout(T) front()() inout return scope /* template-lazy */ 588 => opSlice()[0]; // range-checked by default 589 590 /// Get reference to back element. 591 pragma(inline, true) 592 @property ref inout(T) back()() inout return scope /* template-lazy */ 593 => opSlice()[_store.length - 1]; // range-checked by default 594 595 /** Move `value` into the end of the array. 596 */ 597 void insertBackMove()(scope ref T value) scope @trusted /* template-lazy */ 598 { 599 version(LDC) pragma(inline, true); 600 reserve(_store.length + 1); 601 moveEmplace(value, _mptr[_store.length]); 602 _store.length += 1; 603 } 604 605 /** Insert `value` into the end of the array. 606 */ 607 void insertBack()(scope T value) scope @trusted /* template-lazy */ 608 { 609 static if (__traits(isPOD, T)) 610 { 611 reserve(_store.length + 1); 612 _mptr[_store.length] = value; 613 _store.length += 1; 614 } 615 else 616 insertBackMove(*cast(MT*)(&value)); 617 } 618 619 alias put = insertBack; 620 621 /** Insert the elements `values` into the end of the array. 622 */ 623 void insertBack(U)(U[] values...) scope @trusted 624 if (isElementAssignable!U && 625 __traits(isCopyable, U)) // prevent accidental move of l-value `values` 626 { 627 if (values.length == 1) // TODO: branch should be detected at compile-time 628 // twice as fast as array assignment below 629 return insertBack(values[0]); 630 631 static if (is(T == immutable(T))) 632 { 633 /* An array of immutable values cannot overlap with the `this` 634 mutable array container data, which entails no need to check for 635 overlap. 636 */ 637 reserve(_store.length + values.length); 638 _mptr[_store.length .. _store.length + values.length] = values; 639 } 640 else 641 { 642 import nxt.overlapping : overlaps; 643 if (_store.ptr == values.ptr) // called for instances as: `this ~= this` 644 { 645 reserve(2*_store.length); // invalidates `values.ptr` 646 foreach (immutable i; 0 .. _store.length) 647 _mptr[_store.length + i] = _store.ptr[i]; 648 } 649 else if (overlaps(this[], values[])) 650 assert(0, `TODO: Handle overlapping arrays`); 651 else 652 { 653 reserve(_store.length + values.length); 654 _mptr[_store.length .. _store.length + values.length] = values; 655 } 656 } 657 _store.length += values.length; 658 } 659 660 /** Insert the elements `elements` into the end of the array. 661 */ 662 void insertBack(R)(scope R elements) @trusted 663 if (isInsertableContainer!R) 664 { 665 import std.range.primitives : hasLength; 666 static if (isInputRange!R && 667 hasLength!R) 668 { 669 reserve(_store.length + elements.length); 670 import std.algorithm.mutation : copy; 671 copy(elements, _mptr[_store.length .. _store.length + elements.length]); 672 _store.length += elements.length; 673 } 674 else 675 { 676 foreach (ref element; move(elements)) // TODO: remove `move` when compiler does it for us 677 static if (__traits(isCopyable, ElementType!R)) 678 insertBack(element); 679 else 680 insertBackMove(element); 681 } 682 } 683 /// ditto 684 alias put = insertBack; 685 686 /** Remove last value fromm the end of the array. 687 */ 688 void popBack()() @trusted in(!empty) /* template-lazy */ 689 { 690 version(D_Coverage) {} else pragma(inline, true); 691 _store.length -= 1; 692 static if (hasElaborateDestructor!T) 693 .destroy(_mptr[_store.length]); 694 else static if (mustAddGCRange!T) 695 _mptr[_store.length] = T.init; // avoid GC mark-phase dereference 696 } 697 698 /** Rmove `n` last values from the end of the array. 699 700 See_Also: http://mir-algorithm.libmir.org/mir_appender.html#.ScopedBuffer.popBackN 701 */ 702 void popBackN()(in size_t n) @trusted in(length >= n) /* template-lazy */ 703 { 704 _store.length -= n; 705 static if (hasElaborateDestructor!T) 706 foreach (immutable index; 0 .. n) 707 .destroy(_mptr[_store.length + index]); 708 else static if (mustAddGCRange!T) 709 foreach (immutable index; 0 .. n) 710 _mptr[_store.length + index] = T.init; // avoid GC mark-phase dereference 711 } 712 713 /** Pop back element and return it. 714 715 This is well-missed feature of C++'s `std::vector` because of problems 716 with exception handling. For more details see 717 https://stackoverflow.com/questions/12600330/pop-back-return-value. 718 */ 719 T takeBack()() @trusted in(!empty) /* template-lazy */ 720 { 721 version(D_Coverage) {} else pragma(inline, true); 722 _store.length -= 1; 723 static if (!__traits(isPOD, T)) 724 return move(_mptr[_store.length]); 725 else static if (is(T == class) || isPointer!T || hasIndirections!T) // fast, medium, slow path 726 { 727 T e = void; 728 moveEmplace(_mptr[_store.length], e); // reset any pointers at `back` 729 return e; 730 } 731 else 732 return _mptr[_store.length]; 733 } 734 735 /** Pop element at `index`. */ 736 void popAt()(in size_t index) @trusted @("complexity", "O(length)") /* template-lazy */ 737 in(index < this.length) 738 { 739 static if (hasElaborateDestructor!T) 740 .destroy(_mptr[index]); 741 else static if (mustAddGCRange!T) 742 _mptr[index] = T.init; // avoid GC mark-phase dereference 743 shiftToFrontAt(index); 744 _store.length -= 1; 745 } 746 747 /** Move element at `index` to return. */ 748 static if (isMutable!T) 749 T moveAt()(in size_t index) @trusted @("complexity", "O(length)") /* template-lazy */ 750 in(index < this.length) 751 { 752 auto value = move(_mptr[index]); 753 shiftToFrontAt(index); 754 _store.length -= 1; 755 return move(value); // TODO: remove `move` when compiler does it for us 756 } 757 758 /** Move element at front. */ 759 static if (isMutable!T) 760 pragma(inline, true) 761 T takeFront()() @("complexity", "O(length)") /* template-lazy */ 762 => moveAt(0); 763 764 private void shiftToFrontAt()(in size_t index) @trusted /* template-lazy */ 765 { 766 // TODO: use this instead: 767 // immutable si = index + 1; // source index 768 // immutable ti = index; // target index 769 // immutable restLength = this.length - (index + 1); 770 // import std.algorithm.mutation : moveEmplaceAll; 771 // moveEmplaceAll(_mptr[si .. si + restLength], 772 // _mptr[ti .. ti + restLength]); 773 foreach (immutable i; 0 .. this.length - (index + 1)) // each element index that needs to be moved 774 { 775 immutable si = index + i + 1; // source index 776 immutable ti = index + i; // target index 777 moveEmplace(_mptr[si], // TODO: remove `move` when compiler does it for us 778 _mptr[ti]); 779 } 780 } 781 782 /** Forwards to $(D insertBack(values)). 783 */ 784 void opOpAssign(string op)(T value) if (op == "~") 785 { 786 version(D_Coverage) {} else pragma(inline, true); 787 insertBackMove(value); 788 } 789 /// ditto 790 void opOpAssign(string op, U)(U[] values...) @trusted if (op == "~" && 791 isElementAssignable!U && 792 __traits(isCopyable, U)) // prevent accidental move of l-value `values` 793 { 794 version(D_Coverage) {} else pragma(inline, true); 795 insertBack(values); 796 } 797 /// ditto 798 void opOpAssign(string op, R)(R values) if (op == "~" && 799 isInputRange!R && 800 !isInfinite!R && 801 !isArray!R && 802 isElementAssignable!(ElementType!R)) 803 { 804 version(D_Coverage) {} else pragma(inline, true); 805 insertBack(values); 806 } 807 808 void opOpAssign(string op)(auto ref typeof(this) values) if (op == "~") 809 { 810 version(D_Coverage) {} else pragma(inline, true); 811 insertBack(values[]); 812 } 813 814 // typeof(this) opBinary(string op, R)(R values) if (op == "~") 815 // { 816 // // TODO: optimize 817 // typeof(this) result; 818 // result ~= this[]; 819 // assert(result.length == length); 820 // result ~= values[]; 821 // return result; 822 // } 823 824 /// Unsafe access to pointer. 825 pragma(inline, true) 826 inout(T)* ptr()() inout return @system /* template-lazy */ 827 => _store.ptr; 828 829 /// Mutable pointer. 830 pragma(inline, true) 831 private MT* _mptr() const return @trusted 832 => cast(typeof(return))_store.ptr; 833 834 private: 835 import nxt.allocator_traits : AllocatorState; 836 mixin AllocatorState!Allocator; // put first as emsi-containers do 837 838 /** For more convenient construction. */ 839 struct Store 840 { 841 static if (hasFunctionAttributes!(Allocator.allocate, "@nogc")) 842 { 843 import nxt.gc_traits : NoGc; 844 @NoGc T* ptr; // non-GC-allocated 845 } 846 else 847 T* ptr; // GC-allocated 848 Capacity capacity; // store capacity 849 Capacity length; // store length 850 } 851 852 Store _store; 853 } 854 855 import std.traits : isInstanceOf; 856 import std.functional : unaryFun; 857 858 /** Remove all elements matching `predicate`. 859 860 Returns: number of elements that were removed. 861 862 TODO: implement version that doesn't use a temporary array `tmp`, which is 863 probably faster for small arrays. 864 */ 865 size_t remove(alias predicate, C)(ref C c) @trusted @("complexity", "O(length)") 866 if (isInstanceOf!(DynamicArray, C) && 867 is(typeof(unaryFun!predicate(C.init[0])))) 868 { 869 C tmp; 870 size_t count = 0; 871 foreach (immutable i; 0 .. c.length) 872 { 873 if (unaryFun!predicate(c[i])) 874 { 875 count += 1; 876 import core.internal.traits : hasElaborateDestructor; 877 import nxt.container.traits : mustAddGCRange; 878 alias T = typeof(c[i]); 879 static if (hasElaborateDestructor!(T)) 880 .destroy(c[i]); 881 else static if (mustAddGCRange!(T)) 882 c[i] = T.init; // avoid GC mark-phase dereference 883 } 884 else 885 tmp.insertBackMove(c[i]); // TODO: remove unnecessary clearing of `_mptr[i]` 886 } 887 888 c.freeStore(); 889 890 import core.lifetime : moveEmplace; 891 moveEmplace(tmp, c); 892 893 return count; 894 } 895 896 /// construct and append from slices 897 @safe pure nothrow @nogc unittest 898 { 899 alias T = int; 900 alias A = DynamicArray!(T, Mallocator, uint); 901 static if (size_t.sizeof == 8) // only 64-bit 902 static assert(A.sizeof == 2 * size_t.sizeof); // only two words 903 904 auto a = A([10, 11, 12].s); 905 906 a ~= a[]; 907 assert(a[] == [10, 11, 12, 908 10, 11, 12].s); 909 910 a ~= false; 911 assert(a[] == [10, 11, 12, 912 10, 11, 12, 0].s); 913 } 914 915 /// 916 @safe pure nothrow @nogc unittest 917 { 918 alias T = int; 919 alias A = DynamicArray!(T); 920 921 A a; 922 923 a.length = 1; 924 assert(a.length == 1); 925 assert(a.capacity >= 1); 926 927 a[0] = 10; 928 929 a.insertBack(11, 12); 930 931 a ~= T.init; 932 a.insertBack([3].s); 933 assert(a[] == [10, 11, 12, 0, 3].s); 934 935 import std.algorithm.iteration : filter; 936 937 a.insertBack([42].s[].filter!(_ => _ is 42)); 938 assert(a[] == [10, 11, 12, 0, 3, 42].s); 939 940 a.insertBack([42].s[].filter!(_ => _ !is 42)); 941 assert(a[] == [10, 11, 12, 0, 3, 42].s); 942 943 a ~= a[]; 944 assert(a[] == [10, 11, 12, 0, 3, 42, 945 10, 11, 12, 0, 3, 42].s); 946 } 947 948 /// 949 @safe pure nothrow @nogc unittest 950 { 951 alias T = int; 952 alias A = DynamicArray!(T); 953 954 A a; // default construction allowed 955 assert(a.empty); 956 assert(a.length == 0); 957 assert(a.capacity == 0); 958 assert(a[] == []); 959 960 auto b = DynamicArray!int.withLength(3); 961 assert(!b.empty); 962 assert(b.length == 3); 963 assert(b.capacity == 3); 964 b[0] = 1; 965 b[1] = 2; 966 b[2] = 3; 967 assert(b[] == [1, 2, 3].s); 968 969 b[] = [4, 5, 6].s; 970 assert(b[] == [4, 5, 6].s); 971 972 const c = DynamicArray!int.withCapacity(3); 973 assert(c.empty); 974 assert(c.capacity == 3); 975 assert(c[] == []); 976 977 static if (hasPreviewDIP1000) 978 static assert(!__traits(compiles, { T[] f() @safe { A a; return a[]; } })); 979 980 const e = DynamicArray!int([1, 2, 3, 4].s); 981 assert(e.length == 4); 982 assert(e[] == [1, 2, 3, 4].s); 983 } 984 985 /// 986 @trusted pure nothrow @nogc unittest 987 { 988 alias T = int; 989 alias A = DynamicArray!(T); 990 991 auto a = A([1, 2, 3].s); 992 A b = a.dup; // copy construction enabled 993 994 assert(a[] == b[]); // same content 995 assert(&a[0] !is &b[0]); // but not the same 996 997 assert(b[] == [1, 2, 3].s); 998 assert(b.length == 3); 999 1000 b ~= 4; 1001 assert(a != b); 1002 a.clear(); 1003 assert(a != b); 1004 b.clear(); 1005 assert(a == b); 1006 1007 const c = A([1, 2, 3].s); 1008 assert(c.length == 3); 1009 } 1010 1011 /// DIP-1000 return ref escape analysis 1012 @safe pure nothrow @nogc unittest 1013 { 1014 alias T = int; 1015 alias A = DynamicArray!T; 1016 1017 static if (hasPreviewDIP1000) 1018 static assert(!__traits(compiles, { T[] leakSlice() @safe pure nothrow @nogc { A a; return a[]; } })); 1019 1020 T* leakPointer() @safe pure nothrow @nogc 1021 { 1022 A a; 1023 return a._store.ptr; // TODO: shouldn't compile with -dip1000 1024 } 1025 1026 const _lp = leakPointer(); // TODO: shouldn't compile with -dip1000 1027 } 1028 1029 version(unittest) 1030 { 1031 private static struct SomeUncopyable 1032 { 1033 @disable this(this); 1034 int _x; 1035 } 1036 } 1037 1038 /// construct and insert from non-copyable element type passed by value 1039 @safe pure nothrow /*@nogc*/ unittest 1040 { 1041 alias A = DynamicArray!(SomeUncopyable); 1042 1043 A a = A(SomeUncopyable(17)); 1044 assert(a[] == [SomeUncopyable(17)]); 1045 1046 a.insertBack(SomeUncopyable(18)); 1047 assert(a[] == [SomeUncopyable(17), 1048 SomeUncopyable(18)]); 1049 1050 a ~= SomeUncopyable(19); 1051 assert(a[] == [SomeUncopyable(17), 1052 SomeUncopyable(18), 1053 SomeUncopyable(19)]); 1054 } 1055 1056 /// construct from slice of uncopyable type 1057 @safe pure nothrow @nogc unittest 1058 { 1059 alias _A = DynamicArray!(SomeUncopyable); 1060 // TODO: can we safely support this?: A a = [SomeUncopyable(17)]; 1061 } 1062 1063 // construct from array with uncopyable elements 1064 @safe pure nothrow @nogc unittest 1065 { 1066 alias A = DynamicArray!(SomeUncopyable); 1067 1068 const A a; 1069 assert(a.empty); 1070 1071 // TODO: a.insertBack(A.init); 1072 assert(a.empty); 1073 1074 const _ = a.toHash; 1075 } 1076 1077 // construct from ranges of uncopyable elements 1078 @safe pure nothrow @nogc unittest 1079 { 1080 alias T = SomeUncopyable; 1081 alias A = DynamicArray!T; 1082 1083 const A a; 1084 assert(a.empty); 1085 1086 // import std.algorithm.iteration : map, filter; 1087 1088 // const b = A.withElementsOfRange_untested([10, 20, 30].s[].map!(_ => T(_^^2))); // hasLength 1089 // assert(b.length == 3); 1090 // assert(b == [T(100), T(400), T(900)].s); 1091 1092 // const c = A.withElementsOfRange_untested([10, 20, 30].s[].filter!(_ => _ == 30).map!(_ => T(_^^2))); // !hasLength 1093 // assert(c.length == 1); 1094 // assert(c[0].x == 900); 1095 } 1096 1097 // construct from ranges of copyable elements 1098 @safe pure nothrow @nogc unittest 1099 { 1100 alias T = int; 1101 alias A = DynamicArray!T; 1102 1103 const A a; 1104 assert(a.empty); 1105 1106 import std.algorithm.iteration : map, filter; 1107 1108 const b = A.withElementsOfRange_untested([10, 20, 30].s[].map!(_ => T(_^^2))); // hasLength 1109 assert(b.length == 3); 1110 assert(b == [T(100), T(400), T(900)].s); 1111 1112 () @trusted { // TODO: remove @trusted 1113 const c = A.withElementsOfRange_untested([10, 20, 30].s[].filter!(_ => _ == 30).map!(_ => T(_^^2))); // !hasLength 1114 assert(c == [T(900)].s); 1115 } (); 1116 } 1117 1118 /// construct with string as element type that needs GC-range 1119 @safe pure nothrow @nogc unittest 1120 { 1121 alias T = string; 1122 alias A = DynamicArray!(T); 1123 1124 A a; 1125 a ~= `alpha`; 1126 a ~= `beta`; 1127 a ~= [`gamma`, `delta`].s; 1128 assert(a[] == [`alpha`, `beta`, `gamma`, `delta`].s); 1129 1130 const b = [`epsilon`].s; 1131 1132 a.insertBack(b); 1133 assert(a[] == [`alpha`, `beta`, `gamma`, `delta`, `epsilon`].s); 1134 1135 a ~= b; 1136 assert(a[] == [`alpha`, `beta`, `gamma`, `delta`, `epsilon`, `epsilon`].s); 1137 } 1138 1139 /// convert to string 1140 version(none) // TODO: make this work 1141 unittest 1142 { 1143 alias T = int; 1144 alias A = DynamicArray!(T); 1145 1146 DynamicArray!char sink; 1147 A([1, 2, 3]).toString(sink.put); 1148 } 1149 1150 /// iteration over mutable elements 1151 @safe pure nothrow @nogc unittest 1152 { 1153 alias T = int; 1154 alias A = DynamicArray!(T); 1155 1156 auto a = A([1, 2, 3].s); 1157 1158 foreach (immutable i, const e; a) 1159 assert(i + 1 == e); 1160 } 1161 1162 /// iteration over `const`ant elements 1163 @safe pure nothrow @nogc unittest 1164 { 1165 alias T = const(int); 1166 alias A = DynamicArray!(T); 1167 1168 auto a = A([1, 2, 3].s); 1169 1170 foreach (immutable i, const e; a) 1171 assert(i + 1 == e); 1172 } 1173 1174 /// iteration over immutable elements 1175 @safe pure nothrow @nogc unittest 1176 { 1177 alias T = immutable(int); 1178 alias A = DynamicArray!(T); 1179 1180 auto a = A([1, 2, 3].s); 1181 1182 foreach (immutable i, const e; a) 1183 assert(i + 1 == e); 1184 } 1185 1186 /// removal 1187 @safe pure nothrow @nogc unittest 1188 { 1189 alias T = int; 1190 alias A = DynamicArray!(T); 1191 1192 auto a = A([1, 2, 3].s); 1193 assert(a == [1, 2, 3].s); 1194 1195 assert(a.takeFront() == 1); 1196 assert(a == [2, 3].s); 1197 1198 a.popAt(1); 1199 assert(a == [2].s); 1200 1201 a.popAt(0); 1202 assert(a == []); 1203 1204 a.insertBack(11); 1205 assert(a == [11].s); 1206 1207 assert(a.takeBack == 11); 1208 1209 a.insertBack(17); 1210 assert(a == [17].s); 1211 a.popBack(); 1212 assert(a.empty); 1213 1214 a.insertBack([11, 12, 13, 14, 15].s[]); 1215 a.popAt(2); 1216 assert(a == [11, 12, 14, 15].s); 1217 a.popAt(0); 1218 assert(a == [12, 14, 15].s); 1219 a.popAt(2); 1220 1221 assert(a == [12, 14].s); 1222 1223 a ~= a; 1224 } 1225 1226 /// removal 1227 @safe pure nothrow unittest 1228 { 1229 import nxt.container.traits : mustAddGCRange; 1230 1231 size_t mallocCount = 0; 1232 size_t freeCount = 0; 1233 1234 struct S 1235 { 1236 @safe pure nothrow @nogc: 1237 1238 alias E = int; 1239 1240 import nxt.qcmeman : malloc, free; 1241 1242 this(E x) @trusted 1243 { 1244 _ptr = cast(E*)malloc(E.sizeof); 1245 mallocCount += 1; 1246 *_ptr = x; 1247 } 1248 1249 @disable this(this); 1250 1251 ~this() nothrow @trusted @nogc 1252 { 1253 free(_ptr); 1254 freeCount += 1; 1255 } 1256 1257 import nxt.gc_traits : NoGc; 1258 @NoGc E* _ptr; 1259 } 1260 1261 /* D compilers cannot currently move stuff efficiently when using 1262 std.algorithm.mutation.move. A final dtor call to the cleared sourced is 1263 always done. 1264 */ 1265 const size_t extraDtor = 1; 1266 1267 alias A = DynamicArray!(S); 1268 static assert(!mustAddGCRange!A); 1269 alias AA = DynamicArray!(A); 1270 static assert(!mustAddGCRange!AA); 1271 1272 assert(mallocCount == 0); 1273 1274 { 1275 A a; 1276 a.insertBack(S(11)); 1277 assert(mallocCount == 1); 1278 assert(freeCount == extraDtor + 0); 1279 } 1280 1281 assert(freeCount == extraDtor + 1); 1282 1283 // assert(a.front !is S(11)); 1284 // assert(a.back !is S(11)); 1285 // a.insertBack(S(12)); 1286 } 1287 1288 /// test `OutputRange` behaviour with std.format 1289 version(none) // TODO: replace with other exercise of std.format 1290 @safe pure /*TODO: nothrow @nogc*/ unittest 1291 { 1292 import std.format : formattedWrite; 1293 const x = "42"; 1294 alias A = DynamicArray!(char); 1295 A a; 1296 a.formattedWrite!("x : %s")(x); 1297 assert(a == "x : 42"); 1298 } 1299 1300 /// test emplaceWithMovedElements 1301 @trusted pure nothrow @nogc unittest 1302 { 1303 alias A = DynamicArray!(char); 1304 1305 auto ae = ['a', 'b'].s; 1306 1307 A a = void; 1308 A.emplaceWithMovedElements(&a, ae[]); 1309 1310 assert(a.length == ae.length); 1311 assert(a.capacity == ae.length); 1312 assert(a[] == ae); 1313 } 1314 1315 /// test emplaceWithCopiedElements 1316 @trusted pure nothrow @nogc unittest 1317 { 1318 alias A = DynamicArray!(char); 1319 1320 auto ae = ['a', 'b'].s; 1321 1322 A a = void; 1323 A.emplaceWithCopiedElements(&a, ae[]); 1324 1325 assert(a.length == ae.length); 1326 assert(a.capacity == ae.length); 1327 assert(a[] == ae); 1328 } 1329 1330 @safe pure nothrow @nogc unittest 1331 { 1332 alias T = int; 1333 alias A = DynamicArray!(T, Mallocator, uint); 1334 const a = A(17); 1335 assert(a[] == [17].s); 1336 } 1337 1338 /// check duplication via `dup` 1339 @trusted pure nothrow @nogc unittest 1340 { 1341 alias T = int; 1342 alias A = DynamicArray!(T); 1343 1344 static assert(!__traits(compiles, { A b = a; })); // copying disabled 1345 1346 auto a = A([10, 11, 12].s); 1347 auto b = a.dup; 1348 assert(a == b); 1349 assert(&a[0] !is &b[0]); 1350 } 1351 1352 /// element type is a class 1353 @safe pure nothrow unittest 1354 { 1355 class T 1356 { 1357 this (int x) 1358 { 1359 this.x = x; 1360 } 1361 ~this() nothrow @nogc { x = 42; } 1362 int x; 1363 } 1364 alias A = DynamicArray!(T); 1365 auto a = A([new T(10), 1366 new T(11), 1367 new T(12)].s); 1368 assert(a.length == 3); 1369 a.remove!(_ => _.x == 12); 1370 assert(a.length == 2); 1371 } 1372 1373 /// check filtered removal via `remove` 1374 @safe pure nothrow @nogc unittest 1375 { 1376 struct T 1377 { 1378 int value; 1379 } 1380 1381 alias A = DynamicArray!(T); 1382 1383 static assert(!__traits(compiles, { A b = a; })); // copying disabled 1384 1385 auto a = A([T(10), T(11), T(12)].s); 1386 1387 assert(a.remove!"a.value == 13" == 0); 1388 assert(a[] == [T(10), T(11), T(12)].s); 1389 1390 assert(a.remove!"a.value >= 12" == 1); 1391 assert(a[] == [T(10), T(11)].s); 1392 1393 assert(a.remove!(_ => _.value == 10) == 1); 1394 assert(a[] == [T(11)].s); 1395 1396 assert(a.remove!(_ => _.value == 11) == 1); 1397 assert(a.empty); 1398 } 1399 1400 /// construct from map range 1401 @safe pure nothrow unittest 1402 { 1403 import std.algorithm.iteration : map; 1404 alias T = int; 1405 alias A = DynamicArray!(T); 1406 1407 A a = A.withElementsOfRange_untested([10, 20, 30].s[].map!(_ => _^^2)); 1408 assert(a[] == [100, 400, 900].s); 1409 a.popBackN(2); 1410 assert(a.length == 1); 1411 a.popBackN(1); 1412 assert(a.empty); 1413 1414 A b = A([10, 20, 30].s[].map!(_ => _^^2)); 1415 assert(b[] == [100, 400, 900].s); 1416 b.popBackN(2); 1417 assert(b.length == 1); 1418 b.popBackN(1); 1419 assert(b.empty); 1420 1421 A c = A([10, 20, 30].s[]); 1422 assert(c[] == [10, 20, 30].s); 1423 } 1424 1425 /// construct from map range 1426 @trusted pure nothrow unittest 1427 { 1428 alias T = int; 1429 alias A = DynamicArray!(T); 1430 1431 import std.typecons : RefCounted; 1432 RefCounted!A x; 1433 1434 auto z = [1, 2, 3].s; 1435 x ~= z[]; 1436 1437 auto y = x; 1438 assert(y[] == z); 1439 1440 const _ = x.toHash; 1441 } 1442 1443 /// construct from static array 1444 @trusted pure nothrow @nogc unittest 1445 { 1446 alias T = uint; 1447 alias A = DynamicArray!(T); 1448 1449 ushort[3] a = [1, 2, 3]; 1450 1451 const x = A(a); 1452 assert(x == a); 1453 assert(x == a[]); 1454 } 1455 1456 /// construct from static array slice 1457 @trusted pure nothrow @nogc unittest 1458 { 1459 alias T = uint; 1460 alias A = DynamicArray!(T); 1461 1462 ushort[3] a = [1, 2, 3]; 1463 ushort[] b = a[]; 1464 1465 const y = A(b); // cannot construct directly from `a[]` because its type is `ushort[3]` 1466 assert(y == a); 1467 assert(y == a[]); 1468 } 1469 1470 /// GCAllocator 1471 @trusted pure nothrow unittest 1472 { 1473 import std.experimental.allocator.gc_allocator : GCAllocator; 1474 alias T = int; 1475 alias A = DynamicArray!(T, GCAllocator); 1476 const A a; 1477 assert(a.length == 0); 1478 } 1479 1480 /// construct with slices as element types 1481 @trusted pure nothrow unittest 1482 { 1483 alias A = DynamicArray!(string); 1484 const A a; 1485 assert(a.length == 0); 1486 alias B = DynamicArray!(char[]); 1487 const B b; 1488 assert(b.length == 0); 1489 } 1490 1491 /** Variant of `DynamicArray` with copy construction (postblit) enabled. 1492 * 1493 * See_Also: suppressing.d 1494 * See_Also: http://forum.dlang.org/post/eitlbtfbavdphbvplnrk@forum.dlang.org 1495 */ 1496 struct BasicCopyableArray 1497 { 1498 /** TODO: implement using instructions at: 1499 * http://forum.dlang.org/post/eitlbtfbavdphbvplnrk@forum.dlang.org 1500 */ 1501 } 1502 1503 /// TODO: Move to Phobos. 1504 private enum bool isRefIterable(T) = is(typeof({ foreach (ref elem; T.init) {} })); 1505 1506 version(unittest) 1507 { 1508 import nxt.array_help : s; 1509 import nxt.dip_traits : hasPreviewDIP1000; 1510 }