1 /**
2    Dynamic arrays with deterministic memory usage
3    akin to C++'s std::vector or Rust's std::vec::Vec
4  */
5 module automem.vector;
6 
7 
8 import automem.traits: isGlobal;
9 import std.range.primitives: isInputRange;
10 import std.experimental.allocator: theAllocator;
11 import std.experimental.allocator.mallocator: Mallocator;
12 
13 
14 alias String = StringA!(typeof(theAllocator));
15 alias StringM = StringA!Mallocator;
16 
17 
18 template StringA(A = typeof(theAllocator)) if(isAllocator!A) {
19     alias StringA = Vector!(immutable char, A);
20 }
21 
22 /**
23    Create a vector from a variadic list of elements, inferring the type of
24    the elements and the allocator
25  */
26 auto vector(A = typeof(theAllocator), E)
27            (E[] elements...)
28     if(isAllocator!A && isGlobal!A)
29 {
30     return Vector!(E, A)(elements);
31 }
32 
33 /// ditto
34 auto vector(A = typeof(theAllocator), E)
35            (A allocator, E[] elements...)
36     if(isAllocator!A && !isGlobal!A)
37 {
38     return Vector!(E, A)(allocator, elements);
39 }
40 
41 /**
42    Create a vector from an input range, inferring the type of the elements
43    and the allocator.
44  */
45 auto vector(A = typeof(theAllocator), R)
46            (R range)
47     if(isAllocator!A && isGlobal!A && isInputRange!R)
48 {
49     import automem.vector: ElementType;
50     return Vector!(ElementType!R, A)(range);
51 }
52 
53 
54 /// ditto
55 auto vector(A = typeof(theAllocator), R)
56            (A allocator, R range)
57     if(isAllocator!A && !isGlobal!A && isInputRange!R)
58 {
59     import automem.vector: ElementType;
60     return Vector!(ElementType!R, A)(allocator, range);
61 }
62 
63 /**
64    A dynamic array with deterministic memory usage
65    akin to C++'s std::vector or Rust's std::vec::Vec
66  */
67 struct Vector(E, Allocator = typeof(theAllocator)) if(isAllocator!Allocator) {
68 
69     import automem.traits: isGlobal, isSingleton, isTheAllocator;
70     import std.traits: Unqual, isCopyable;
71 
72     alias MutE = Unqual!E;
73     enum isElementMutable = !is(E == immutable) && !is(E == const);
74 
75     static if(isGlobal!Allocator) {
76 
77         this(E[] elements...) {
78             fromElements(elements);
79         }
80 
81         this(R)(R range) if(isInputRangeOf!(R, E)) {
82             // reallocating is ok if only allocating now
83             () @trusted { this = range; }();
84         }
85 
86     } else static if(isCopyable!Allocator) {
87 
88         this(Allocator allocator, E[] elements...) {
89             _allocator = allocator;
90             fromElements(elements);
91         }
92 
93         this(R)(Allocator allocator, R range) if(isInputRangeOf!(R, E)) {
94             _allocator = allocator;
95             this = range;
96         }
97     } else {
98 
99         this(R)(R range) if(isInputRangeOf!(R, E)) {
100             this = range;
101         }
102 
103     }
104 
105     this(this) scope {
106 
107         auto oldElements = _elements;
108         _elements = createVector(_elements.length);
109 
110         static if(isElementMutable)
111             _elements[0 .. length.toSizeT] = oldElements[0 .. length.toSizeT];
112         else
113             () @trusted {
114                 cast(MutE[])(_elements)[0 .. length.toSizeT] = oldElements[0 .. length.toSizeT];
115             }();
116     }
117 
118     ~this() {
119         free;
120     }
121 
122     /// Frees the memory and returns to .init
123     void free() scope {
124         import std.experimental.allocator: dispose;
125 
126         // dispose is @system for theAllocator
127         () @trusted {
128             static if(is(E == immutable))
129                 auto elements = cast(MutE[]) _elements;
130             else
131                 alias elements = _elements;
132 
133             _allocator.dispose(elements);
134         }();
135 
136         clear;
137     }
138 
139     static if(isElementMutable) {
140         /// Pops the front element off
141         void popFront() {
142             foreach(i; 0 .. length - 1)
143                 _elements[i.toSizeT] = _elements[i.toSizeT + 1];
144 
145             popBack;
146         }
147     }
148 
149     /// Pops the last element off
150     void popBack() {
151         --_length;
152     }
153 
154     /// If the vector is empty
155     bool empty() const {
156         return length == 0;
157     }
158 
159     /// The current length of the vector
160     @property long length() const {
161         return _length;
162     }
163 
164     /// Set the length of the vector
165     @property void length(long newLength) {
166         if(capacity < newLength) reserve(newLength);
167         _length = newLength;
168     }
169 
170     /// The current memory capacity of the vector
171     long capacity() const {
172         return _elements.length;
173     }
174 
175     /// Clears the vector, resulting in an empty one
176     void clear() {
177         _length = 0;
178     }
179 
180     /// Reserve memory to avoid allocations when appending
181     void reserve(long newLength) {
182         expandMemory(newLength);
183     }
184 
185     static if(isElementMutable) {
186 
187         /// Shrink to fit the current length. Returns if shrunk.
188         bool shrink() scope {
189             return shrink(length);
190         }
191 
192         /**
193            Shrink to fit the new length given. Returns if shrunk.
194            Cannot be made @safe due to reallocation causing pointers
195            to dangle.
196         */
197         bool shrink(long newLength) scope {
198             import std.experimental.allocator: shrinkArray;
199 
200             const delta = capacity - newLength;
201             const shrunk = _allocator.shrinkArray(_elements, delta.toSizeT);
202             _length = newLength;
203 
204             return shrunk;
205         }
206     }
207 
208     /// Access the ith element. Can throw RangeError.
209     ref inout(E) opIndex(long i) scope return inout {
210         if(i < 0 || i >= length)
211             mixin(throwBoundsException);
212         return _elements[i.toSizeT];
213     }
214 
215     /// Returns a new vector after appending to the given vector.
216     Vector opBinary(string s, T)(auto ref T other) const
217         if(s == "~" && is(Unqual!T == Vector))
218     {
219         import std.range: chain;
220         // opSlice is @system , but it's ok here because we're not
221         // returning the slice but concatenating.
222         return Vector(chain(() @trusted { return this[]; }(),
223                             () @trusted { return other[]; }()));
224     }
225 
226     /// Assigns from a range.
227     void opAssign(R)(R range) scope if(isForwardRangeOf!(R, E)) {
228         import std.range.primitives: walkLength, save;
229 
230         expand(range.save.walkLength);
231 
232         long i = 0;
233         foreach(element; range)
234             _elements[toSizeT(i++)] = element;
235     }
236 
237     // make it an output range
238 
239 
240     /// Append to the vector
241     void opOpAssign(string op)
242                    (E other)
243         scope
244         if(op == "~")
245     {
246         put(other);
247     }
248 
249     void put(E other) {
250 
251         expand(length + 1);
252 
253         const lastIndex = (length - 1).toSizeT;
254 
255         static if(isElementMutable)
256             _elements[lastIndex] = other;
257         else {
258             assert(_elements[lastIndex] == E.init,
259                    "Assigning to non default initialised non mutable member");
260 
261             () @trusted { mutableElements[lastIndex] = other; }();
262         }
263     }
264 
265     /// Append to the vector from a range
266     void opOpAssign(string op, R)
267                    (scope R range)
268         scope
269         if(op == "~" && isForwardRangeOf!(R, E))
270     {
271         put(range);
272     }
273 
274     void put(R)(scope R range) if(isLengthRangeOf!(R, E)) {
275         import std.range.primitives: walkLength, save;
276 
277         long index = length;
278 
279         static if(hasLength!R)
280             const rangeLength = range.length;
281         else
282             const rangeLength = range.save.walkLength;
283 
284         expand(length + rangeLength);
285 
286         foreach(element; range) {
287             const safeIndex = toSizeT(index++);
288             static if(!isElementMutable) {
289                 assert(_elements[safeIndex] == E.init,
290                        "Assigning to non default initialised non mutable member");
291             }
292 
293             static if(isElementMutable)
294                 _elements[safeIndex] = element;
295             else {
296                 assert(_elements[safeIndex] == E.init,
297                        "Assigning to non default initialised non mutable member");
298                 () @trusted { mutableElements[safeIndex] = element; }();
299             }
300         }
301     }
302 
303     /**
304        Return a forward range of the vector contents.
305        Negative `end` values work like in Python.
306      */
307     auto range(this This)(in long start = 0, long end = -1) return scope
308         in(start >= 0)
309         in(end <= length)
310         do
311     {
312         import std.range.primitives: isForwardRange;
313 
314         static struct Range {
315             private This* self;
316             private long index;
317             private long end;
318 
319             Range save() {
320                 return this;
321             }
322 
323             auto front() {
324                 return (*self)[index];
325             }
326 
327             void popFront() {
328                 ++index;
329             }
330 
331             bool empty() const {
332                 const comp = end < 0 ? length + end + 1 : end;
333                 return index >= comp;
334             }
335 
336             auto length() const {
337                 return self.length;
338             }
339         }
340 
341         static assert(isForwardRange!Range);
342 
343         // FIXME - why isn't &this @safe?
344         return Range(() @trusted { return &this; }(),
345                      start,
346                      end);
347     }
348 
349     /**
350        Returns a slice.
351        @system because the pointer in the slice might dangle.
352      */
353     auto opSlice(this This)() @system scope return {
354         return _elements[0 .. length.toSizeT];
355     }
356 
357     /**
358        Returns a slice.
359        @system because the pointer in the slice might dangle.
360      */
361     auto opSlice(this This)(long start, long end) @system scope return {
362         if(start < 0 || start >= length)
363             mixin(throwBoundsException);
364 
365         if(end < 0 || end > length)
366             mixin(throwBoundsException);
367 
368         return _elements[start.toSizeT .. end.toSizeT];
369     }
370 
371     long opDollar() const {
372         return length;
373     }
374 
375     static if(isElementMutable) {
376         /// Assign all elements to the given value
377         void opSliceAssign(E value) {
378             _elements[] = value;
379         }
380     }
381 
382 
383     static if(isElementMutable) {
384         /// Assign all elements in the given range to the given value
385         void opSliceAssign(E value, long start, long end) {
386             if(start < 0 || start >= length)
387                 mixin(throwBoundsException);
388 
389             if(end < 0 || end >= length)
390                 mixin(throwBoundsException);
391 
392             _elements[start.toSizeT .. end.toSizeT] = value;
393         }
394     }
395 
396     static if(isElementMutable) {
397         /// Assign all elements using the given operation and the given value
398         void opSliceOpAssign(string op)(E value) scope {
399             foreach(ref elt; _elements)
400                 mixin(`elt ` ~ op ~ `= value;`);
401         }
402     }
403 
404     static if(isElementMutable) {
405         /// Assign all elements in the given range  using the given operation and the given value
406         void opSliceOpAssign(string op)(E value, long start, long end) scope {
407             if(start < 0 || start >= length)
408                 mixin(throwBoundsException);
409 
410             if(end < 0 || end >= length)
411                 mixin(throwBoundsException);
412 
413             foreach(ref elt; _elements[start.toSizeT .. end.toSizeT])
414                 mixin(`elt ` ~ op ~ `= value;`);
415         }
416     }
417 
418     bool opCast(U)() const scope if(is(U == bool)) {
419         return length > 0;
420     }
421 
422     static if(is(Unqual!E == char)) {
423 
424         /**
425            Return a null-terminated C string
426            @system since appending is not @safe.
427          */
428         auto stringz(this This)() return scope @system {
429             if(capacity == length) reserve(length + 1);
430 
431             static if(isElementMutable) {
432                 _elements[length.toSizeT] = 0;
433             } else {
434                 assert(_elements[length.toSizeT] == E.init || _elements[length.toSizeT] == 0,
435                        "Assigning to non default initialised non mutable member");
436 
437                 () @trusted { mutableElements[length.toSizeT] = 0; }();
438             }
439 
440             return &_elements[0];
441         }
442     }
443 
444     auto ptr(this This)() return scope {
445         return &_elements[0];
446     }
447 
448     bool opEquals(R)(R range) scope const
449         if(isInputRangeOf!(R, E))
450     {
451         import std.array: empty, popFront, front;
452 
453         if(length == 0 && range.empty) return true;
454 
455         foreach(i; 0 .. length) {
456             if(range.empty) return false;
457             if(range.front != this[i]) return false;
458             range.popFront;
459         }
460 
461         return range.empty;
462     }
463 
464     bool opEquals(OtherAllocator)(auto ref scope const(Vector!(E, OtherAllocator)) other) const {
465         return this == other.range;
466     }
467 
468 private:
469 
470     E[] _elements;
471     long _length;
472 
473     static if(isSingleton!Allocator)
474         alias _allocator = Allocator.instance;
475     else static if(isTheAllocator!Allocator)
476         alias _allocator = theAllocator;
477     else
478         Allocator _allocator;
479 
480     E[] createVector(long length) scope {
481         import std.experimental.allocator: makeArray;
482         // theAllocator.makeArray is @system
483         return () @trusted { return _allocator.makeArray!E(length.toSizeT); }();
484     }
485 
486     void fromElements(E[] elements) {
487 
488         _elements = createVector(elements.length);
489 
490         static if(isElementMutable)
491             _elements[] = elements[];
492         else
493             () @trusted { (cast(MutE[]) _elements)[] = elements[]; }();
494 
495         _length = elements.length;
496     }
497 
498     void expand(long newLength) scope {
499         expandMemory(newLength);
500         _length = newLength;
501     }
502 
503 
504     // @system since reallocating can cause pointers to dangle
505     void expandMemory(long newLength) scope @system {
506         import std.experimental.allocator: expandArray;
507 
508         if(newLength > capacity) {
509             if(length == 0)
510                 _elements = createVector(newLength);
511             else {
512                 const newCapacity = (newLength * 3) / 2;
513                 const delta = newCapacity - capacity;
514                 _allocator.expandArray(mutableElements, delta.toSizeT);
515             }
516         }
517     }
518 
519     ref MutE[] mutableElements() scope return @system {
520         auto ptr = &_elements;
521         return *(cast(MutE[]*) ptr);
522     }
523 }
524 
525 
526 static if (__VERSION__ >= 2082) { // version identifier D_Exceptions was added in 2.082
527     version (D_Exceptions)
528         private enum haveExceptions = true;
529     else
530         private enum haveExceptions = false;
531 } else {
532     version (D_BetterC)
533         private enum haveExceptions = false;
534     else
535         private enum haveExceptions = true;
536 }
537 
538 
539 static if (haveExceptions) {
540     private static immutable boundsException = new BoundsException("Out of bounds index");
541     private enum throwBoundsException = q{throw boundsException;};
542     class BoundsException: Exception {
543         import std.exception: basicExceptionCtors;
544 
545         mixin basicExceptionCtors;
546     }
547 } else {
548     private enum throwBoundsException = q{assert(0, "Out of bounds index");};
549 }
550 
551 
552 private template isInputRangeOf(R, E) {
553     import std.range.primitives: isInputRange;
554     enum isInputRangeOf = isInputRange!R && canAssignFrom!(R, E);
555 }
556 
557 private template isForwardRangeOf(R, E) {
558     import std.range.primitives: isForwardRange;
559     enum isForwardRangeOf = isForwardRange!R && canAssignFrom!(R, E);
560 }
561 
562 
563 private enum hasLength(R) = is(typeof({
564     import std.traits: isIntegral;
565     auto length = R.init.length;
566     static assert(isIntegral!(typeof(length)));
567 }));
568 
569 
570 private enum isLengthRangeOf(R, E) = isForwardRangeOf!(R, E) || hasLength!R;
571 
572 private template canAssignFrom(R, E) {
573     enum canAssignFrom = is(typeof({
574         import automem.vector: frontNoAutoDecode;
575         E element = R.init.frontNoAutoDecode;
576     }));
577 }
578 
579 private size_t toSizeT(long length) @safe @nogc pure nothrow {
580     static if(size_t.sizeof < long.sizeof)
581         assert(length < cast(long) size_t.max);
582     return cast(size_t) length;
583 }
584 
585 // Because autodecoding is fun
586 private template ElementType(R) {
587     import std.traits: isSomeString;
588 
589     static if(isSomeString!R) {
590         alias ElementType = typeof(R.init[0]);
591     } else {
592         import std.range.primitives: ElementType_ = ElementType;
593         alias ElementType = ElementType_!R;
594     }
595 }
596 
597 @("ElementType")
598 @safe pure unittest {
599     import automem.vector: ElementType;
600     static assert(is(ElementType!(int[]) == int));
601     static assert(is(ElementType!(char[]) == char));
602     static assert(is(ElementType!(wchar[]) == wchar));
603     static assert(is(ElementType!(dchar[]) == dchar));
604 }
605 
606 
607 // More fun with autodecoding
608 private auto frontNoAutoDecode(R)(R range) {
609     import std.traits: isSomeString;
610 
611     static if(isSomeString!R)
612         return range[0];
613     else {
614         import std.range.primitives: front;
615         return range.front;
616     }
617 }
618 
619 
620 void checkAllocator(T)() {
621     import std.experimental.allocator: dispose, shrinkArray, makeArray, expandArray;
622     import std.traits: hasMember;
623 
624     static if(hasMember!(T, "instance"))
625         alias allocator = T.instance;
626     else
627         T allocator;
628 
629     void[] bytes;
630     allocator.dispose(bytes);
631 
632     int[] ints = allocator.makeArray!int(42);
633 
634     allocator.shrinkArray(ints, size_t.init);
635     allocator.expandArray(ints, size_t.init);
636 }
637 enum isAllocator(T) = is(typeof(checkAllocator!T));
638 
639 
640 @("isAllocator")
641 @safe @nogc pure unittest {
642     import std.experimental.allocator.mallocator: Mallocator;
643     import test_allocator: TestAllocator;
644 
645     static assert( isAllocator!Mallocator);
646     static assert( isAllocator!TestAllocator);
647     static assert(!isAllocator!int);
648     static assert( isAllocator!(typeof(theAllocator)));
649 }