1 module nxt.owned;
2 
3 /** Return wrapper around container `Container` that can be safely sliced, by
4     tracking number of read borrowed ranges and whether it's currently write
5     borrowed.
6 
7     Only relevant when `Container` implements referenced access over
8     <ul>
9     <li> `opSlice` and
10     <li> `opIndex`
11     </ul>
12 
13     TODO: Iterate and wrap all @unsafe accessors () and wrapped borrow
14     checks for all modifying members of `Container`?
15 */
16 struct Owned(Container)
17     if (needsOwnership!Container)
18 {
19     import std.range.primitives : hasSlicing;
20     import std.traits : isMutable;
21 
22     /// Type of range of `Container`.
23     alias Range = typeof(Container.init[]);
24 
25 pragma(inline):
26 
27     ~this() nothrow @nogc
28     {
29         assert(!_writeBorrowed, "This is still write-borrowed, cannot release!");
30         assert(_readBorrowCount == 0, "This is still read-borrowed, cannot release!");
31     }
32 
33     /// Move `this` into a returned r-value.
34     typeof(this) move()
35     {
36         assert(!_writeBorrowed, "This is still write-borrowed, cannot move!");
37         assert(_readBorrowCount == 0, "This is still read-borrowed, cannot move!");
38         import core.lifetime : move;
39         return move(this);
40     }
41 
42     /** Checked overload for `std.algorithm.mutation.move`. */
43     void move(ref typeof(this) dst) pure nothrow @nogc
44     {
45         assert(!_writeBorrowed, "Source is still write-borrowed, cannot move!");
46         assert(_readBorrowCount == 0, "Source is still read-borrowed, cannot move!");
47 
48         assert(!dst._writeBorrowed, "Destination is still write-borrowed, cannot move!");
49         assert(dst._readBorrowCount == 0, "Destination is still read-borrowed, cannot move!");
50 
51         import core.lifetime : move;
52         move(this, dst);
53     }
54 
55     /** Checked overload for `std.algorithm.mutation.moveEmplace`. */
56     void moveEmplace(ref typeof(this) dst) pure nothrow @nogc
57     {
58         assert(!_writeBorrowed, "Source is still write-borrowed, cannot moveEmplace!");
59         assert(_readBorrowCount == 0, "Source is still read-borrowed, cannot moveEmplace!");
60 
61         import core.lifetime : moveEmplace;
62         moveEmplace(this, dst);
63     }
64 
65     static if (true/*TODO: hasUnsafeSlicing!Container*/)
66     {
67         import nxt.borrowed : ReadBorrowed, WriteBorrowed;
68 
69         // TODO: can all these definitions be reduce somehow?
70 
71         /// Get full read-only slice.
72         ReadBorrowed!(Range, Owned) sliceRO() const @trusted
73         {
74             import core.internal.traits : Unqual;
75             assert(!_writeBorrowed, "This is already write-borrowed");
76             return typeof(return)(_container.opSlice,
77                                   cast(Unqual!(typeof(this))*)(&this)); // trusted unconst casta
78         }
79 
80         /// Get read-only slice in range `i` .. `j`.
81         ReadBorrowed!(Range, Owned) sliceRO(size_t i, size_t j) const @trusted
82         {
83             import core.internal.traits : Unqual;
84             assert(!_writeBorrowed, "This is already write-borrowed");
85             return typeof(return)(_container.opSlice[i .. j],
86                                   cast(Unqual!(typeof(this))*)(&this)); // trusted unconst cast
87         }
88 
89         /// Get full read-write slice.
90         WriteBorrowed!(Range, Owned) sliceRW() @trusted
91         {
92             assert(!_writeBorrowed, "This is already write-borrowed");
93             assert(_readBorrowCount == 0, "This is already read-borrowed");
94             return typeof(return)(_container.opSlice, &this);
95         }
96 
97         /// Get read-write slice in range `i` .. `j`.
98         WriteBorrowed!(Range, Owned) sliceRW(size_t i, size_t j) @trusted
99         {
100             assert(!_writeBorrowed, "This is already write-borrowed");
101             assert(_readBorrowCount == 0, "This is already read-borrowed");
102             return typeof(return)(_container.opSlice[i .. j], &this);
103         }
104 
105         /// Get read-only slice in range `i` .. `j`.
106         auto opSlice(size_t i, size_t j) const
107         {
108             return sliceRO(i, j);
109         }
110         /// Get read-write slice in range `i` .. `j`.
111         auto opSlice(size_t i, size_t j)
112         {
113             return sliceRW(i, j);
114         }
115 
116         /// Get read-only full slice.
117         auto opSlice() const
118         {
119             return sliceRO();
120         }
121         /// Get read-write full slice.
122         auto opSlice()
123         {
124             return sliceRW();
125         }
126     }
127 
128     @safe pure nothrow @nogc:
129 
130     @property:
131 
132     /// Returns: `true` iff `this` is either write or read borrowed.
133     bool isBorrowed() const { return _writeBorrowed || _readBorrowCount >= 1; }
134 
135     /// Returns: `true` iff owned container is write borrowed.
136     bool isWriteBorrowed() const { return _writeBorrowed; }
137 
138     /// Returns: number of read-only borrowers of owned container.
139     uint readBorrowCount() const { return _readBorrowCount; }
140 
141     Container _container;            /// wrapped container
142     alias _container this;
143 
144 public:
145     bool _writeBorrowed = false; /// `true` iff `_container` is currently referred to
146     uint _readBorrowCount = 0; /// number of readable borrowers. TODO: use `size_t` minus one bit instead in `size_t _stats`
147     enum readBorrowCountMax = typeof(_readBorrowCount).max;
148 }
149 
150 /** Checked overload for `std.algorithm.mutation.move`.
151 
152     TODO: Can we somehow prevent users of Owned from accidentally using
153     `std.algorithm.mutation.move` instead of this wrapper?
154  */
155 void move(Owner)(ref Owner src, ref Owner dst) @safe pure nothrow @nogc
156     if (isInstanceOf!(Owned, Owner))
157 {
158     src.move(dst);              // reuse member function
159 }
160 
161 /** Checked overload for `std.algorithm.mutation.moveEmplace`.
162 
163     TODO: Can we somehow prevent users of Owned from accidentally using
164     `std.algorithm.mutation.moveEmplace` instead of this wrapper?
165 */
166 void moveEmplace(Owner)(ref Owner src, ref Owner dst) @safe pure nothrow @nogc
167     if (isInstanceOf!(Owned, Owner))
168 {
169     src.moveEmplace(dst);   // reuse member function
170 }
171 
172 template needsOwnership(Container)
173 {
174     import std.range.primitives : hasSlicing;
175     // TODO: activate when array_ex : UniqueArray
176     // enum needsOwnership = hasSlicing!Container; // TODO: extend to check if it's not @safe
177     enum needsOwnership = is(Container == struct);
178 }
179 
180 pure unittest
181 {
182     alias A = UniqueArray!int;
183     const Owned!A co;          // const owner
184 
185     import std.traits : isMutable;
186     static assert(!isMutable!(typeof(co)));
187 
188     const cos = co[];
189 }
190 
191 @safe pure unittest
192 {
193     alias A = UniqueArray!int;
194     A a = A.init;
195     a = A.init;
196     // TODO: a ~= A.init;
197 }
198 
199 pure unittest
200 {
201     import std.traits : isInstanceOf;
202     import std.exception: assertThrown;
203     import core.exception : AssertError;
204 
205     import nxt.borrowed : ReadBorrowed, WriteBorrowed;
206 
207     alias A = UniqueArray!int;
208 
209     Owned!A oa;
210 
211     Owned!A ob;
212     oa.move(ob);                // ok to move unborrowed
213 
214     Owned!A od = void;
215     oa.moveEmplace(od);         // ok to moveEmplace unborrowed
216 
217     oa ~= 1;
218     oa ~= 2;
219     assert(oa[] == [1, 2]);
220     assert(oa[0 .. 1] == [1]);
221     assert(oa[1 .. 2] == [2]);
222     assert(oa[0 .. 2] == [1, 2]);
223     assert(!oa.isWriteBorrowed);
224     assert(!oa.isBorrowed);
225     assert(oa.readBorrowCount == 0);
226 
227     {
228         const wb = oa.sliceRW;
229 
230         Owned!A oc;
231         assertThrown!AssertError(oa.move()); // cannot move write borrowed
232 
233         assert(wb.length == 2);
234         static assert(!__traits(compiles, { auto wc = wb; })); // write borrows cannot be copied
235         assert(oa.isBorrowed);
236         assert(oa.isWriteBorrowed);
237         assert(oa.readBorrowCount == 0);
238         assertThrown!AssertError(oa.opSlice); // one more write borrow is not allowed
239     }
240 
241     // ok to write borrow again in separate scope
242     {
243         const wb = oa.sliceRW;
244 
245         assert(wb.length == 2);
246         assert(oa.isBorrowed);
247         assert(oa.isWriteBorrowed);
248         assert(oa.readBorrowCount == 0);
249     }
250 
251     // ok to write borrow again in separate scope
252     {
253         const wb = oa.sliceRW(0, 2);
254         assert(wb.length == 2);
255         assert(oa.isBorrowed);
256         assert(oa.isWriteBorrowed);
257         assert(oa.readBorrowCount == 0);
258     }
259 
260     // multiple read-only borrows are allowed
261     {
262         const rb1 = oa.sliceRO;
263 
264         Owned!A oc;
265         assertThrown!AssertError(oa.move(oc)); // cannot move read borrowed
266 
267         assert(rb1.length == oa.length);
268         assert(oa.readBorrowCount == 1);
269 
270         const rb2 = oa.sliceRO;
271         assert(rb2.length == oa.length);
272         assert(oa.readBorrowCount == 2);
273 
274         const rb3 = oa.sliceRO;
275         assert(rb3.length == oa.length);
276         assert(oa.readBorrowCount == 3);
277 
278         const rb_ = rb3;
279         assert(rb_.length == oa.length);
280         assert(oa.readBorrowCount == 4);
281         assertThrown!AssertError(oa.sliceRW); // single write borrow is not allowed
282     }
283 
284     // test modification via write borrow
285     {
286         auto wb = oa.sliceRW;
287         wb[0] = 11;
288         wb[1] = 12;
289         assert(wb.length == oa.length);
290         assert(oa.isWriteBorrowed);
291         assert(oa.readBorrowCount == 0);
292         assertThrown!AssertError(oa.sliceRO);
293     }
294     assert(oa[] == [11, 12]);
295     assert(oa.sliceRO(0, 2) == [11, 12]);
296 
297     // test mutable slice
298     static assert(isInstanceOf!(WriteBorrowed, typeof(oa.sliceRW())));
299     static assert(isInstanceOf!(WriteBorrowed, typeof(oa[])));
300     foreach (ref e; oa.sliceRW)
301     {
302         assertThrown!AssertError(oa.sliceRO); // one more write borrow is not allowed
303         assertThrown!AssertError(oa.sliceRW); // one more write borrow is not allowed
304         assertThrown!AssertError(oa[]); // one more write borrow is not allowed
305     }
306 
307     // test readable slice
308     static assert(isInstanceOf!(ReadBorrowed, typeof(oa.sliceRO())));
309     foreach (const ref e; oa.sliceRO)
310     {
311         assert(oa.sliceRO.length == oa.length);
312         assert(oa.sliceRO[0 .. 0].length == 0);
313         assert(oa.sliceRO[0 .. 1].length == 1);
314         assert(oa.sliceRO[0 .. 2].length == oa.length);
315         assertThrown!AssertError(oa.sliceRW); // write borrow during iteration is not allowed
316         assertThrown!AssertError(oa.move());  // move not allowed when borrowed
317     }
318 
319     // move semantics
320     auto oaMove1 = oa.move();
321     auto oaMove2 = oaMove1.move();
322     assert(oaMove2[] == [11, 12]);
323 
324     // constness propagation from owner to borrower
325     Owned!A mo;          // mutable owner
326     assert(mo.sliceRO.ptr == mo.ptr);
327     assert(mo.sliceRO(0, 0).ptr == mo.ptr);
328     static assert(isInstanceOf!(ReadBorrowed, typeof(mo.sliceRO())));
329 
330     const Owned!A co;          // const owner
331     assert(co.sliceRO.ptr == co.ptr);
332     static assert(isInstanceOf!(ReadBorrowed, typeof(co.sliceRO())));
333 }
334 
335 nothrow unittest
336 {
337     import std.algorithm.sorting : sort;
338     alias E = int;
339     alias A = UniqueArray!E;
340     A a;
341     sort(a[]);         // TODO: make this work
342 }
343 
344 // y = sort(x.move()), where x and y are instances of unsorted Array
345 @safe nothrow unittest
346 {
347     import std.algorithm.sorting : sort;
348     import std.range.primitives : isInputRange, isForwardRange, isRandomAccessRange, hasSlicing;
349 
350     alias E = int;
351     alias A = UniqueArray!E;
352     alias O = Owned!A;
353 
354     O o;
355     o ~= [42, 43];
356 
357     assert(o.length == 2);
358 
359     scope os = o.sliceRO;
360 
361     alias OS = typeof(os);
362     static assert(isInputRange!(OS));
363     static assert(isForwardRange!(OS));
364     static assert(hasSlicing!(OS));
365     static assert(isRandomAccessRange!OS);
366 
367     assert(!os.empty);
368     assert(os.length == 2);
369     os.popFront();
370     assert(!os.empty);
371     assert(os.length == 1);
372     os.popFront();
373     assert(os.empty);
374 
375     // TODO: scope oss = os[];            // no op
376     // TODO: assert(oss.empty);
377 }
378 
379 // check write-borrow
380 @safe nothrow unittest
381 {
382     import std.algorithm.sorting : sort;
383     import std.range.primitives : isInputRange, isForwardRange, isRandomAccessRange, hasSlicing;
384 
385     alias E = int;
386     alias A = UniqueArray!E;
387     alias O = Owned!A;
388 
389     const O co;
390     auto cos = co[0 .. 0];
391     const ccos = co[0 .. 0];
392 
393     // TODO: const coc = co[].save();
394 
395     O o;
396     o ~= [42, 43];
397     auto os = o.sliceRW;
398     alias OS = typeof(os);
399     static assert(isInputRange!(OS));
400 
401     // static assert(isForwardRange!(OS));
402     // static assert(hasSlicing!(OS));
403     // static assert(isRandomAccessRange!OS);
404     // import std.algorithm.sorting : sort;
405     // sort(o[]);
406 }
407 
408 version(unittest)
409 {
410     import nxt.container.dynamic_array : UniqueArray = DynamicArray;
411     import nxt.dbgio;
412 }