nxt.variant_arrays source code

1 module nxt.variant_arrays;
2 
3 @safe:
4 
5 /** Typed index (reference) into an element in `VariantArrays`.
6  */
7 private struct VariantRef(DefinedTypes...)
8 {
9     @safe:
10 
11     import std.meta : staticIndexOf;
12 
13     alias Kind = ubyte;              // kind code
14     alias Size = size_t;             // size type
15 
16     import nxt.bit_traits : bitsNeeded;
17 
18     /// Used to indicate undefined value.
19     private struct Undefined {}
20 
21     import std.meta : AliasSeq;
22 
23     alias Types = AliasSeq!(Undefined, DefinedTypes);
24 
25     /// Number of bits needed to represent kind.
26     private enum kindBits = bitsNeeded!(Types.length);
27 
28     /** Get number kind of kind type `SomeKind`.
29         TODO: make private?
30      */
31     enum nrOfKind(SomeKind) = staticIndexOf!(SomeKind, Types); // TODO: cast to ubyte if Types.length is <= 256
32 
33     /// Is `true` iff an index to a `SomeKind`-kind can be stored.
34     enum canReferenceType(SomeKind) = nrOfKind!SomeKind >= 0;
35 
36     /// Comparsion works like for integers.
37     int opCmp(in typeof(this) rhs) const @trusted
38     {
39         version(LDC) pragma(inline, true);
40         if (this.rawWord < rhs.rawWord)
41             return -1;
42         if (this.rawWord > rhs.rawWord)
43             return +1;
44         return 0;
45     }
46 
47     pragma(inline, true):
48 
49     /// Construct from mutable `that`.
50     this(in typeof(this) that)
51     {
52         rawWord = that.rawWord;
53     }
54     /// Construct from constant `that`.
55     this(typeof(this) that)
56     {
57         rawWord = that.rawWord;
58     }
59 
60     /// Construct.
61     this(Kind kind, Size index) // TODO: can ctor inferred by bitfields?
62     {
63         _kindNr = kind;
64         _index = index;
65     }
66 
67     /// Construct from raw word representation `rawWord`.
68     private this(Size rawWord)
69     {
70         this.rawWord = rawWord;
71     }
72 
73     /// Get kindNr.
74     Kind kindNr() const
75     {
76         return _kindNr;
77     }
78 
79     /// Get index.
80     Size index() const
81     {
82         return _index;
83     }
84 
85     /// Cast to `size_t`.
86     size_t opCast(T : size_t)() const
87     {
88         return rawWord;
89     }
90 
91     import core.internal.traits : Unqual;
92 
93     /// Allow cast to unqualified.
94     U opCast(U : Unqual!(typeof(this)))() const
95     {
96         return U(rawWord);
97     }
98 
99     /// The index itself is the hash.
100     hash_t toHash() const @property { return rawWord; }
101     static assert(hash_t.sizeof == rawWord.sizeof);
102 
103     /// Cast to `bool`, meaning 'true' if defined, `false` otherwise.
104     bool opCast(U : bool)() const { return isDefined(); }
105 
106     /// Returns: `true` iff is defined.
107     bool isDefined() const { return rawWord != 0; }
108 
109     /// Returns: `true` iff `this` targets a value of type `SomeKind`.
110     public bool isA(SomeKind)() const
111     {
112         return nrOfKind!(SomeKind) == _kindNr;
113     }
114 
115     @property void toString(scope void delegate(scope const(char)[]) sink) const @trusted
116     {
117         import std.format : formattedWrite;
118         if (isDefined)
119             sink.formattedWrite!`%s(%s@%s)`(Unqual!(typeof(this)).stringof, _index, _kindNr);
120         else
121             sink.formattedWrite!`%s(null)`(Unqual!(typeof(this)).stringof);
122     }
123 
124     import std.bitmanip : bitfields;
125     union
126     {
127         // TODO: big-endian machine
128         mixin(bitfields!(Kind, "_kindNr", kindBits,
129                          Size, "_index", 8*Size.sizeof - kindBits));
130         Size rawWord;           // for comparsion
131     }
132 
133     static assert(this.sizeof == Size.sizeof,
134                   `This should haven't any memory overhead compared to size_t`);
135 }
136 
137 @safe pure nothrow unittest
138 {
139     alias R = VariantRef!(int, float);
140     R r;
141     static assert(r.canReferenceType!(int));
142     static assert(r.canReferenceType!(float));
143     static assert(!r.canReferenceType!(short));
144 
145     import std.array : Appender;
146     Appender!(const(R)[]) app;
147     assert(app.data.length == 0);
148 
149     const R x;
150     R mx = x;
151     assert(x == mx);
152 
153     // TODO: app ~= x;
154 
155     // const y = [R.init, R.init];
156     // TODO: app ~= y;
157 }
158 
159 unittest
160 {
161     alias R = VariantRef!(int, float);
162     R r;
163     import std.conv : to;
164     assert(r.to!string == `VariantRef!(int, float)(null)`);
165 }
166 
167 // private mixin template VariantArrayOf(Type)
168 // {
169 //     import nxt.dynamic_array : DynamicArray;
170 //     DynamicArray!Type store;
171 // }
172 
173 /** Stores set of variants.
174 
175     Enables lightweight storage of polymorphic objects.
176 
177     Each element is indexed by a corresponding `VariantRef`.
178  */
179 struct VariantArrays(Types...)
180 {
181     @safe:
182 
183     alias Ref = VariantRef!Types;
184 
185     import nxt.dynamic_array : DynamicArray;
186 
187     /// Returns: array type (as a string) of `Type`.
188     private static immutable(string) arrayTypeStringOfIndex(uint typeIndex)()
189     {
190         pragma(inline, true);
191         return `DynamicArray!(Types[` ~ typeIndex.stringof ~ `])`;
192     }
193 
194     /** Returns: array instance (as a strinng) storing `SomeKind`.
195      * TODO: make this a template mixin
196      */
197     private static immutable(string) arrayInstanceString(SomeKind)()
198     if (Ref.canReferenceType!SomeKind)
199     {
200         pragma(inline, true);
201         return `_store` ~ Ref.nrOfKind!(SomeKind).stringof; // previously `SomeKind.mangleof`
202     }
203 
204     /// Make reference to type `SomeKind` at offset `index`.
205     static Ref makeRef(SomeKind)(Ref.Size index)
206     if (Ref.canReferenceType!SomeKind)
207     {
208         pragma(inline, true);
209         return Ref(Ref.nrOfKind!SomeKind, index);
210     }
211 
212     /** Insert `value` at back.
213      */
214     Ref insertBack(SomeKind)(SomeKind value) // TODO: add array type overload
215     if (Ref.canReferenceType!SomeKind)
216     {
217         mixin(`alias arrayInstance = ` ~ arrayInstanceString!SomeKind ~ `;`);
218         const currentIndex = arrayInstance.length;
219         arrayInstance.insertBackMove(value);
220         return Ref(Ref.nrOfKind!SomeKind,
221                    currentIndex);
222     }
223     alias put = insertBack;     // polymorphic `OutputRange` support
224 
225     /** Move (emplace) `value` into back.
226      */
227     Ref insertBackMove(SomeKind)(ref SomeKind value) // TODO: add array type overload
228     if (Ref.canReferenceType!SomeKind)
229     {
230         version(DigitalMars) pragma(inline, false); // DMD cannot inline
231         mixin(`alias arrayInstance = ` ~ arrayInstanceString!SomeKind ~ `;`);
232         const currentIndex = arrayInstance.length;
233         arrayInstance.insertBackMove(value);
234         return Ref(Ref.nrOfKind!SomeKind,
235                    currentIndex);
236     }
237 
238     /// ditto
239     void opOpAssign(string op, SomeKind)(SomeKind value) // TODO: add array type overload
240     if (op == "~" &&
241         Ref.canReferenceType!SomeKind)
242     {
243         pragma(inline, true);
244         insertBackMove(value);  // move enables uncopyable types
245     }
246 
247     /// Get reference to element of type `SomeKind` at `index`.
248     scope ref inout(SomeKind) at(SomeKind)(in size_t index) inout return
249     if (Ref.canReferenceType!SomeKind)
250     {
251         pragma(inline, true);
252         mixin(`return ` ~ arrayInstanceString!SomeKind ~ `[index];`);
253     }
254 
255     /// Get reference to element of type `SomeKind` at `ref_`.
256     scope ref inout(SomeKind) at(SomeKind)(in Ref ref_) inout return
257     if (Ref.canReferenceType!SomeKind)
258     {
259         pragma(inline, true);
260         assert(Ref.nrOfKind!SomeKind == ref_._kindNr,
261                "Ref is not of expected template type " ~ SomeKind.stringof);
262         mixin(`return ` ~ arrayInstanceString!SomeKind ~ `[ref_.index];`);
263     }
264 
265     /// Peek at element of type `SomeKind` at `ref_`.
266     inout(SomeKind)* peek(SomeKind)(in Ref ref_) inout return @system
267     if (Ref.canReferenceType!SomeKind)
268     {
269         pragma(inline, true);
270         if (Ref.nrOfKind!SomeKind == ref_._kindNr)
271             return &at!SomeKind(ref_._index);
272         else
273             return null;
274     }
275 
276     /// Constant access to all elements of type `SomeKind`.
277     scope inout(SomeKind)[] allOf(SomeKind)() inout return
278     if (Ref.canReferenceType!SomeKind)
279     {
280         pragma(inline, true);
281         mixin(`return ` ~ arrayInstanceString!SomeKind ~ `[];`);
282     }
283 
284     /// Reserve space for `newCapacity` elements of type `SomeKind`.
285     void reserve(SomeKind)(size_t newCapacity)
286     if (Ref.canReferenceType!SomeKind)
287     {
288         pragma(inline, true);
289         mixin(`alias arrayInstance = ` ~ arrayInstanceString!SomeKind ~ `;`);
290         arrayInstance.reserve(newCapacity);
291     }
292 
293     /** Returns: length of store. */
294     @property size_t length() const
295     {
296         pragma(inline, true);
297         typeof(return) lengthSum = 0;
298         foreach (Type; Types)
299             mixin(`lengthSum += ` ~ arrayInstanceString!Type ~ `.length;`);
300         return lengthSum;
301     }
302 
303     /** Check if empty. */
304     @property bool empty() const
305     {
306         pragma(inline, true);
307         return length == 0;
308     }
309 
310 private:
311     static if (false/*__VERSION__ >= 2076*/)
312     {
313         // static foreach (const typeIndex, Type; Types)
314         // {
315         //     // TODO: is it better to use?: mixin VariantArrayOf!(Type);
316         //     mixin(arrayTypeStringOfIndex!typeIndex ~ ` ` ~ arrayInstanceString!Type ~ `;`);
317         // }
318     }
319     else
320     {
321         mixin({
322                 string s = "";
323                 foreach (const typeIndex, Type; Types)
324                     s ~= arrayTypeStringOfIndex!typeIndex ~ ` ` ~ arrayInstanceString!Type ~ `;`;
325                 return s;
326             }());
327     }
328 }
329 
330 ///
331 @safe pure nothrow @nogc unittest
332 {
333     import nxt.minimal_fixed_array : MinimalFixedArray;
334 
335     alias Chars(uint capacity) = MinimalFixedArray!(char, capacity);
336     alias Chars7 = Chars!7;
337     alias Chars15 = Chars!15;
338     alias VA = VariantArrays!(ulong,
339                               Chars7,
340                               Chars15);
341 
342     VA data;
343     assert(data.length == 0);
344     assert(data.empty);
345 
346     const i0 = data.put(ulong(13));
347     assert(cast(size_t)i0 == 1);
348 
349     assert(i0.isA!ulong);
350     assert(data.at!ulong(0) == ulong(13));
351     assert(data.length == 1);
352     assert(!data.empty);
353     assert(data.allOf!ulong == [ulong(13)].s);
354 
355     const i1 = data.put(Chars7(`1234567`));
356     assert(cast(size_t)i1 == 2);
357 
358     // same order as in `Types`
359     assert(i0 < i1);
360 
361     assert(i1.isA!(Chars7));
362     assert(data.at!(Chars7)(0) == Chars7(`1234567`));
363     assert(data.allOf!(Chars7) == [Chars7(`1234567`)].s);
364     assert(data.length == 2);
365 
366     const i2 = data.put(Chars15(`123`));
367     assert(cast(size_t)i2 == 3);
368 
369     // same order as in `Types`
370     assert(i0 < i2);
371     assert(i1 < i2);
372 
373     assert(i2.isA!(Chars15));
374     assert(data.at!(Chars15)(0) == Chars15(`123`));
375     // TODO: assert(data.allOf!(Chars15) == [Chars15(`123`)].s);
376     assert(data.length == 3);
377 
378     const i3 = data.put(Chars15(`1234`));
379     assert(cast(size_t)i3 == 7);
380 
381     // same order as in `Types`
382     assert(i0 < i3);
383     assert(i1 < i3);
384     assert(i2 < i3);            // same type, i2 added before i3
385 
386     assert(i3.isA!(Chars15));
387     assert(data.at!(Chars15)(1) == Chars15(`1234`));
388     assert(data.allOf!(Chars15) == [Chars15(`123`), Chars15(`1234`)].s);
389     assert(data.length == 4);
390 }
391 
392 version = extraTests;
393 
394 version(extraTests)
395 {
396 static private:
397     alias I = VariantRef!(Rel1, Rel2, Int);
398 
399     // relations
400     struct Rel1 { I[1] args; }
401     struct Rel2 { I[2] args; }
402 
403     alias S = VariantArrays!(Rel1, Rel2,
404                              Int);
405 
406     struct Int { int value; }
407 }
408 
409 ///
410 version(extraTests)
411 @safe pure nothrow @nogc unittest
412 {
413     S s;
414 
415     const S.Ref top = s.put(Rel1(s.put(Rel1(s.put(Rel2([s.put(Int(42)),
416                                                         s.put(Int(43))]))))));
417     assert(top);
418     assert(s.allOf!Rel1.length == 2);
419     assert(s.allOf!Rel2.length == 1);
420     assert(s.allOf!Int.length == 2);
421     assert(s.length == 5);
422 }
423 
424 /// put and peek
425 version(extraTests)
426 @system pure nothrow @nogc unittest
427 {
428     S s;
429     const n = 10;
430     foreach (const i; 0 .. n)
431     {
432         S.Ref lone = s.put(Int(i));
433         Int* lonePtr = s.peek!Int(lone);
434         assert(lonePtr);
435         assert(*lonePtr == Int(i));
436     }
437     assert(s.length == 10);
438 }
439 
440 version(unittest)
441 {
442     import nxt.array_help : s;
443 }
444 
445 // version = benchmark;
446 
447 version(benchmark)
448 unittest
449 {
450     alias E = uint;
451     immutable n = 5_000_000;
452 
453     import std.stdio : writeln;
454     import std.datetime : MonoTime;
455     import std.meta : AliasSeq;
456     foreach (A; AliasSeq!(VariantArrays!(E)))
457     {
458         A a;
459 
460         immutable before = MonoTime.currTime();
461 
462         foreach (uint i; 0 .. n)
463             a ~= i;
464 
465         immutable after = MonoTime.currTime();
466 
467         writeln("Added ", n, " integer nodes into ", A.stringof, " in ", after - before);
468     }
469 
470 }