1 /**
2    RAII arrays
3  */
4 module automem.unique_array;
5 
6 import automem.traits: isAllocator;
7 import automem.test_utils: TestUtils;
8 import std.experimental.allocator: theAllocator;
9 
10 version(unittest) {
11     import unit_threaded;
12     import test_allocator: TestAllocator;
13 }
14 
15 mixin TestUtils;
16 
17 /**
18    A unique array similar to C++'s std::unique_ptr<T> when T is an array
19  */
20 struct UniqueArray(Type, Allocator = typeof(theAllocator)) if(isAllocator!Allocator) {
21 
22     import std.traits: hasMember, isScalarType;
23     import std.range: isInputRange;
24 
25     enum isSingleton = hasMember!(Allocator, "instance");
26     enum isTheAllocator = is(Allocator == typeof(theAllocator));
27     enum isGlobal = isSingleton || isTheAllocator;
28 
29     static if(isGlobal) {
30 
31         /**
32            The allocator is global, so no need to pass it in to the
33            constructor
34         */
35 
36         this(size_t size) {
37             makeObjects(size);
38         }
39 
40         this(size_t size, Type init) {
41             makeObjects(size, init);
42         }
43 
44         this(R)(R range) if(isInputRange!R) {
45             makeObjects(range);
46         }
47 
48 
49     } else {
50 
51         /**
52            Non-singleton allocator, must be passed in
53          */
54 
55         this(Allocator allocator) {
56             _allocator = allocator;
57         }
58 
59         this(Allocator allocator, size_t size) {
60             _allocator = allocator;
61             makeObjects(size);
62         }
63 
64         this(Allocator allocator, size_t size, Type init) {
65             _allocator = allocator;
66             makeObjects(size, init);
67         }
68 
69         this(R)(Allocator allocator, R range) if(isInputRange!R) {
70             _allocator = allocator;
71             makeObjects(range);
72         }
73     }
74 
75 
76     this(T)(UniqueArray!(T, Allocator) other) if(is(T: Type[])) {
77         moveFrom(other);
78     }
79 
80     @disable this(this);
81 
82     ~this() {
83         deleteObjects;
84     }
85 
86     /**
87        Releases ownership and transfers it to the returned
88        Unique object.
89      */
90     UniqueArray unique() {
91         import std.algorithm: move;
92         UniqueArray u;
93         move(this, u);
94         assert(_objects.length == 0 && _objects.ptr is null);
95         return u;
96     }
97     alias move = unique;
98 
99     /**
100        "Truthiness" cast
101      */
102     bool opCast(T)() const if(is(T == bool)) {
103         return _objects.ptr !is null;
104     }
105 
106     void opAssign(T)(UniqueArray!(T, Allocator) other) if(is(T: Type[])) {
107         deleteObject;
108         moveFrom(other);
109     }
110 
111     ref inout(Type) opIndex(long i) inout nothrow {
112         return _objects[i];
113     }
114 
115     const(Type)[] opSlice(long i, long j) const nothrow {
116         return _objects[i .. j];
117     }
118 
119     const(Type)[] opSlice() const nothrow {
120         return _objects[0 .. length];
121     }
122 
123     long opDollar() const nothrow {
124         return length;
125     }
126 
127     @property long length() const nothrow {
128         return _length;
129     }
130 
131     @property void length(long size) {
132 
133         import std.experimental.allocator: expandArray, shrinkArray;
134 
135         if(_objects is null) {
136             makeObjects(size);
137         } else if(size == length) {
138             return;
139         } else if(size <= _capacity && size > length) {
140             foreach(ref obj; _objects[_length .. size])
141                 obj = obj.init;
142             _length = size;
143         } else if(size < length) {
144             _length = size;
145         } else {
146             if(size > length) {
147                 _allocator.expandArray(_objects, size - length);
148                 setLength;
149             } else
150                 assert(0);
151         }
152     }
153 
154     /**
155        Dereference. const  since this otherwise could be used to try
156        and append to the array, which would not be nice
157      */
158     const(Type[]) opUnary(string s)() const if(s == "*") {
159         return this[];
160     }
161 
162     /**
163        Append to the array
164      */
165     UniqueArray opBinary(string s)(UniqueArray other) if(s == "~") {
166         this ~= other.unique;
167         return this.unique;
168     }
169 
170     /// Append to the array
171     void opOpAssign(string op)(Type other) if(op == "~") {
172         length(length + 1);
173         _objects[$ - 1] = other;
174     }
175 
176     /// Append to the array
177     void opOpAssign(string op)(Type[] other) if(op == "~") {
178         const originalLength = length;
179         length(originalLength + other.length);
180         _objects[originalLength .. length] = other[];
181     }
182 
183     /// Append to the array
184     void opOpAssign(string op)(UniqueArray other) if(op == "~") {
185         this ~= other._objects;
186     }
187 
188     /// Assign from a slice.
189     void opAssign(Type[] other) {
190         length = other.length;
191         _objects[0 .. length] = other[0 .. length];
192     }
193 
194     /**
195        Reserves memory to prevent too many allocations
196      */
197     void reserve(in long size) {
198         import std.experimental.allocator: expandArray;
199 
200         if(_objects is null) {
201             const oldLength = length;
202             makeObjects(size); // length = capacity here
203             _length = oldLength;
204             return;
205         }
206 
207         if(size < _capacity) {
208             if(size < _length) _length = size;
209             return;
210         }
211 
212         _capacity = size;
213         _allocator.expandArray(_objects, _capacity);
214     }
215 
216     /**
217        Returns a pointer to the underlying data. @system
218      */
219     inout(Type)* ptr() inout {
220         return _objects.ptr;
221     }
222 
223     static if(isGlobal) {
224         UniqueArray dup() const {
225             return UniqueArray(_objects);
226         }
227     } else static if(isScalarType!Allocator && is(typeof(() { auto a = Allocator.init; auto b = a; }))) {
228         UniqueArray dup() const {
229             return UniqueArray(_allocator, _objects);
230         }
231     } else {
232         UniqueArray dup() {
233             return UniqueArray(_allocator, _objects);
234         }
235     }
236 
237 private:
238 
239     Type[] _objects;
240     long _length;
241     long _capacity;
242 
243     static if(isSingleton)
244         alias _allocator = Allocator.instance;
245     else static if(isTheAllocator)
246         alias _allocator = theAllocator;
247     else
248         Allocator _allocator;
249 
250     void makeObjects(size_t size) {
251         import std.experimental.allocator: makeArray;
252         _objects = _allocator.makeArray!Type(size);
253         setLength;
254     }
255 
256     void makeObjects(size_t size, Type init) {
257         import std.experimental.allocator: makeArray;
258         _objects = _allocator.makeArray!Type(size, init);
259         setLength;
260 
261     }
262 
263     void makeObjects(R)(R range) if(isInputRange!R) {
264         import std.experimental.allocator: makeArray;
265         _objects = _allocator.makeArray!Type(range);
266         setLength;
267     }
268 
269     void setLength() {
270         _capacity = _length = _objects.length;
271     }
272 
273     void deleteObjects() {
274         import std.experimental.allocator: dispose;
275         import std.traits: isPointer;
276 
277         static if(isPointer!Allocator)
278             assert((_objects.length == 0 && _objects.ptr is null) || _allocator !is null);
279 
280         if(_objects.ptr !is null) _allocator.dispose(_objects);
281         _length = 0;
282     }
283 
284     void moveFrom(T)(ref UniqueArray!(T, Allocator) other) if(is(T: Type[])) {
285         import std.algorithm: swap;
286         _object = other._object;
287         other._object = null;
288 
289         swap(_length, other._length);
290         swap(_capacity, other._capacity);
291 
292         static if(!isGlobal) {
293             import std.algorithm: move;
294             _allocator = other._allocator.move;
295         }
296     }
297 }
298 
299 
300 @("default TestAllocator")
301 @system unittest {
302     defaultTest!TestAllocator;
303 }
304 
305 
306 @("default Mallocator")
307 @system unittest {
308     import std.experimental.allocator.mallocator: Mallocator;
309     defaultTest!Mallocator;
310 }
311 
312 version(unittest) {
313 
314     void defaultTest(T)() {
315         import std.algorithm: move;
316 
317         mixin AllocatorAlias!T;
318 
319         auto ptr = makeUniqueArray!(Struct, Allocator)(allocator, 3);
320         ptr.length.shouldEqual(3);
321 
322         ptr[2].twice.shouldEqual(0);
323         ptr[2] = Struct(5);
324         ptr[2].twice.shouldEqual(10);
325 
326         ptr[1..$].shouldEqual([Struct(), Struct(5)]);
327 
328         typeof(ptr) ptr2 = ptr.move;
329 
330         ptr.length.shouldEqual(0);
331         (cast(bool)ptr).shouldBeFalse;
332         ptr2.length.shouldEqual(3);
333         (cast(bool)ptr2).shouldBeTrue;
334 
335         // not copyable
336         static assert(!__traits(compiles, ptr2 = ptr1));
337 
338         auto ptr3 = ptr2.unique;
339         ptr3.length.shouldEqual(3);
340         ptr3[].shouldEqual([Struct(), Struct(), Struct(5)]);
341         (*ptr3).shouldEqual([Struct(), Struct(), Struct(5)]);
342 
343         ptr3 ~= Struct(10);
344         ptr3[].shouldEqual([Struct(), Struct(), Struct(5), Struct(10)]);
345 
346         ptr3 ~= [Struct(11), Struct(12)];
347         ptr3[].shouldEqual([Struct(), Struct(), Struct(5), Struct(10), Struct(11), Struct(12)]);
348 
349         ptr3.length = 3;
350         ptr3[].shouldEqual([Struct(), Struct(), Struct(5)]);
351 
352         ptr3.length = 4;
353         ptr3[].shouldEqual([Struct(), Struct(), Struct(5), Struct()]);
354 
355         ptr3.length = 1;
356 
357         ptr3 ~= makeUniqueArray!(Struct, Allocator)(allocator, 1);
358 
359         ptr3[].shouldEqual([Struct(), Struct()]);
360 
361         auto ptr4 = makeUniqueArray!(Struct, Allocator)(allocator, 1);
362 
363         ptr3 ~= ptr4.unique;
364         ptr3[].shouldEqual([Struct(), Struct(), Struct()]);
365 
366         ptr3 = [Struct(7), Struct(9)];
367         ptr3[].shouldEqual([Struct(7), Struct(9)]);
368     }
369 }
370 
371 ///
372 @("@nogc")
373 @system @nogc unittest {
374 
375     import std.experimental.allocator.mallocator: Mallocator;
376 
377     auto arr = UniqueArray!(NoGcStruct, Mallocator)(2);
378     assert(arr.length == 2);
379 
380     arr[0] = NoGcStruct(1);
381     arr[1] = NoGcStruct(3);
382 
383     {
384         NoGcStruct[2] expected = [NoGcStruct(1), NoGcStruct(3)];
385         assert(arr[] == expected[]);
386     }
387 
388     auto arr2 = UniqueArray!(NoGcStruct, Mallocator)(1);
389     arr ~= arr2.unique;
390 
391     {
392         NoGcStruct[3] expected = [NoGcStruct(1), NoGcStruct(3), NoGcStruct()];
393         assert(arr[] == expected[]);
394     }
395 }
396 
397 @("@nogc @safe")
398 @safe @nogc unittest {
399     auto allocator = SafeAllocator();
400     auto arr = UniqueArray!(NoGcStruct, SafeAllocator)(SafeAllocator(), 6);
401     assert(arr.length == 6);
402 }
403 
404 
405 @("init TestAllocator")
406 @system unittest {
407     auto allocator = TestAllocator();
408     auto arr = UniqueArray!(Struct, TestAllocator*)(&allocator, 2, Struct(7));
409     arr[].shouldEqual([Struct(7), Struct(7)]);
410 }
411 
412 @("init Mallocator")
413 @system unittest {
414     import std.experimental.allocator.mallocator: Mallocator;
415     alias allocator = Mallocator.instance;
416     auto arr = UniqueArray!(Struct, Mallocator)(2, Struct(7));
417     arr[].shouldEqual([Struct(7), Struct(7)]);
418 }
419 
420 
421 @("range TestAllocator")
422 @system unittest {
423     auto allocator = TestAllocator();
424     auto arr = UniqueArray!(Struct, TestAllocator*)(&allocator, [Struct(1), Struct(2)]);
425     arr[].shouldEqual([Struct(1), Struct(2)]);
426 }
427 
428 @("range Mallocator")
429 @system unittest {
430     import std.experimental.allocator.mallocator: Mallocator;
431     auto arr = UniqueArray!(Struct, Mallocator)([Struct(1), Struct(2)]);
432     arr[].shouldEqual([Struct(1), Struct(2)]);
433 }
434 
435 
436 @("theAllocator")
437 @system unittest {
438     with(theTestAllocator) {
439         auto arr = UniqueArray!Struct(2);
440         arr[].shouldEqual([Struct(), Struct()]);
441     }
442 }
443 
444 @("issue 1 array")
445 @system unittest {
446     import std.experimental.allocator.mallocator;
447     UniqueArray!(int, Mallocator) a;
448     a ~= [0, 1];
449 }
450 
451 @("issue 1 value")
452 @system unittest {
453     import std.experimental.allocator.mallocator;
454     UniqueArray!(int, Mallocator) a;
455     a ~= 7;
456 }
457 
458 @("issue 1 UniqueArray")
459 @system unittest {
460     import std.experimental.allocator.mallocator;
461     UniqueArray!(int, Mallocator) a;
462     a ~= UniqueArray!(int, Mallocator)([1, 2, 3]);
463 }
464 
465 @("dereference")
466 unittest {
467     import std.experimental.allocator.mallocator;
468     UniqueArray!(int, Mallocator) a;
469     a ~= [0, 1];
470     (*a).shouldEqual([0, 1]);
471 }
472 
473 @("reserve from nothing")
474 @system unittest {
475     auto allocator = TestAllocator();
476     auto a = UniqueArray!(int, TestAllocator*)(&allocator);
477     a.reserve(10); //allocates here
478     a ~= [1, 2, 3]; // should not allocate
479     a ~= [4, 5, 6, 7, 8, 9]; //should not allocate
480     a[].shouldEqual([1, 2, 3, 4, 5, 6, 7, 8, 9]);
481     allocator.numAllocations.shouldEqual(1);
482 }
483 
484 @("reserve from existing expand")
485 @system unittest {
486     auto allocator = TestAllocator();
487     auto a = UniqueArray!(int, TestAllocator*)(&allocator, [1, 2]); //allocates here
488     a.reserve(10); //allocates here
489     a ~= [3, 4]; // should not allocate
490     a ~= [5, 6, 7, 8, 9]; //should not allocate
491     a[].shouldEqual([1, 2, 3, 4, 5, 6, 7, 8, 9]);
492     allocator.numAllocations.shouldEqual(2);
493 }
494 
495 @("reserve from existing reduce")
496 @system unittest {
497     auto allocator = TestAllocator();
498     auto a = UniqueArray!(int, TestAllocator*)(&allocator, [1, 2, 3, 4, 5]); //allocates here
499     a.reserve(2); // should not allocate, changes length to 2
500     a ~= [5, 6];  // should not allocate
501     a[].shouldEqual([1, 2, 5, 6]);
502     allocator.numAllocations.shouldEqual(1);
503 }
504 
505 @("Append 2 arrays")
506 @system unittest {
507     auto allocator = TestAllocator();
508     auto a = UniqueArray!(int, TestAllocator*)(&allocator, [1, 2, 3]) ~
509              UniqueArray!(int, TestAllocator*)(&allocator, [4, 5]);
510     a[].shouldEqual([1, 2, 3, 4, 5]);
511 }
512 
513 @("ptr")
514 @system unittest {
515     auto allocator = TestAllocator();
516     auto a = UniqueArray!(int, TestAllocator*)(&allocator, [1, 2, 3, 4, 5]);
517     auto ptr = a.ptr;
518     ++ptr;
519     (*ptr).shouldEqual(2);
520 }
521 
522 @("dup TestAllocator")
523 @system unittest {
524     auto allocator = TestAllocator();
525     auto a = UniqueArray!(int, TestAllocator*)(&allocator, [1, 2, 3, 4, 5]);
526     auto b = a.dup;
527     allocator.numAllocations.shouldEqual(2);
528     b[].shouldEqual([1, 2, 3, 4, 5]);
529 }
530 
531 @("dup Mallocator")
532 @system unittest {
533     import std.experimental.allocator.mallocator: Mallocator;
534     auto a = UniqueArray!(int, Mallocator)([1, 2, 3, 4, 5]);
535     auto b = a.dup;
536     b[].shouldEqual([1, 2, 3, 4, 5]);
537 }
538 
539 @("dup TestAllocator indirections")
540 @system unittest {
541     auto allocator = TestAllocator();
542     struct String { string s; }
543     auto a = UniqueArray!(String, TestAllocator*)(&allocator, [String("foo"), String("bar")]);
544     auto b = a.dup;
545     a[0] = String("quux");
546     a[1] = String("toto");
547     allocator.numAllocations.shouldEqual(2);
548     a[].shouldEqual([String("quux"), String("toto")]);
549     b[].shouldEqual([String("foo"), String("bar")]);
550 }
551 
552 @("Set length to the same length")
553 unittest {
554     auto allocator = TestAllocator();
555     auto a = UniqueArray!(Struct, TestAllocator*)(&allocator, [Struct(2), Struct(3)]);
556     a.length = 2;
557 }
558 
559 version(unittest) {
560 
561     mixin template AllocatorAlias(T) {
562         import std.traits: hasMember;
563 
564         enum isGlobal = hasMember!(T, "instance");
565 
566         static if(isGlobal) {
567             alias allocator = T.instance;
568             alias Allocator = T;
569         } else {
570             auto allocator = T();
571             alias Allocator = T*;
572         }
573     }
574 
575 
576     auto makeUniqueArray(T, A1, A2, Args...)(ref A2 allocator, Args args) {
577 
578         import std.traits: isPointer, hasMember;
579 
580         enum isGlobal = hasMember!(A1, "instance");
581 
582         static if(isGlobal)
583             return UniqueArray!(T, A1)(args);
584         else static if(isPointer!A1)
585             return UniqueArray!(T, A1)(&allocator, args);
586         else
587             return UniqueArray!(T, A1)(allocator, args);
588     }
589 
590 }