nxt.bit_traits source code

1 module nxt.bit_traits;
2 
3 static if (__VERSION__ >= 2083)
4 {
5     version(LDC) static assert(!__traits(compiles, { enum _ = __traits(isZeroInit, T); }),
6                                "Remove checks for __traits(compiles, { enum _ = __traits(isZeroInit, T); }) now that it compiles with LDC");
7 }
8 
9 /** Get number of bits needed to represent the range (0 .. `length`-1).
10  */
11 template bitsNeeded(size_t length)
12 {
13     // TODO: optimize by removing need for a linear search
14     static      if (length <= 2)   { enum bitsNeeded = 1; }
15     else static if (length <= 4)   { enum bitsNeeded = 2; }
16     else static if (length <= 8)   { enum bitsNeeded = 3; }
17     else static if (length <= 16)  { enum bitsNeeded = 4; }
18     else static if (length <= 32)  { enum bitsNeeded = 5; }
19     else static if (length <= 64)  { enum bitsNeeded = 6; }
20     else static if (length <= 128) { enum bitsNeeded = 7; }
21     else static if (length <= 256) { enum bitsNeeded = 8; }
22     else static if (length <= 512) { enum bitsNeeded = 9; }
23     else                           { static assert(0, `Too large length`); }
24 }
25 
26 /** Number of bits required to store a packed instance of `T`.
27     See_Also: http://forum.dlang.org/thread/okonqhnxzqlqtxijxsfg@forum.dlang.org
28 
29     TODO: Extend to continuous version; use std.numeric.sumOfLog2s. Ask on
30     StackExchange Computer Science for the correct terminology.
31 
32     See: http://dlang.org/phobos/std_numeric.html#.sumOfLog2s
33 
34     TODO: merge with `UsageOf`
35    */
36 template packedBitSizeOf(T)
37 {
38     static if (is(T == enum))
39     {
40         static assert(T.min != T.max, "enum T must have at least two enumerators");
41         import core.bitop : bsr;
42         enum range = T.max - T.min; // TODO: use uniqueEnumMembers.length instead?
43         enum packedBitSizeOf = range.bsr + 1;
44     }
45     // TODO
46     // else static if (isAggregate!T)
47     // {
48     //     foreach (E; T.tupleof)
49     //     {
50     //         ....;
51     //     }
52     // }
53     else
54     {
55         enum packedBitSizeOf = 8*T.sizeof;
56     }
57 }
58 
59 @safe pure nothrow @nogc unittest
60 {
61     static assert(packedBitSizeOf!ubyte == 8);
62     static assert(!__traits(compiles,
63                             {
64                                 enum E1 { x } static assert(packedBitSizeOf!E1 == 1);
65                             }));
66     enum E2 { x, y }
67     static assert(packedBitSizeOf!E2 == 1);
68     enum E3 { x, y, z }
69     static assert(packedBitSizeOf!E3 == 2);
70     enum E4 { x, y, z, w }
71     static assert(packedBitSizeOf!E4 == 2);
72     enum E5 { a, b, c, d, e }
73     static assert(packedBitSizeOf!E5 == 3);
74     enum E6 { a, b, c, d, e, f }
75     static assert(packedBitSizeOf!E6 == 3);
76     enum E7 { a, b, c, d, e, f, g }
77     static assert(packedBitSizeOf!E7 == 3);
78     enum E8 { a, b, c, d, e, f, g, h }
79     static assert(packedBitSizeOf!E8 == 3);
80     enum E9 { a, b, c, d, e, f, g, h, i }
81     static assert(packedBitSizeOf!E9 == 4);
82 }
83 
84 
85 /+ Is the representation of `T.init` known at compile time to consist of nothing
86  + but zero bits? Padding between a struct's fields is not considered.
87  +/
88 template isInitAllZeroBits(T)
89 {
90     static if (__traits(compiles, { enum _ = __traits(isZeroInit, T); }))
91     {
92         enum isInitAllZeroBits = __traits(isZeroInit, T);
93         // pragma(msg, "TODO: use `enum isInitAllZeroBits = __traits(isZeroInit, T);` here and in `isAllZeroBits` and remove the test of isInitAllZeroBits");
94     }
95     else static if (T.sizeof == 0)
96     {
97         enum isInitAllZeroBits = true;
98     }
99     else
100     {
101         static if (__traits(isStaticArray, T) && __traits(compiles, T.init[0]))
102         {
103             enum isInitAllZeroBits = __traits(compiles, {
104                     static assert(isAllZeroBits!(typeof(T.init[0]), T.init[0]));
105                 });
106         }
107         else
108         {
109             enum isInitAllZeroBits = __traits(compiles, {
110                     static assert(isAllZeroBits!(T, T.init));
111                 });
112         }
113     }
114 }
115 
116 @nogc nothrow pure @safe unittest
117 {
118     static assert(isInitAllZeroBits!int);
119     static assert(isInitAllZeroBits!(Object));
120     static assert(isInitAllZeroBits!(void*));
121     static assert(isInitAllZeroBits!uint);
122     static assert(isInitAllZeroBits!(uint[2]));
123     static assert(isInitAllZeroBits!(string));
124     static assert(isInitAllZeroBits!(wstring));
125     static assert(isInitAllZeroBits!(dstring));
126 
127     static assert(!isInitAllZeroBits!float);
128     // static assert(isInitAllZeroBits!(float[0]));
129     static assert(!isInitAllZeroBits!(float[2]));
130 
131     static struct S1
132     {
133         int a;
134     }
135     static assert(isInitAllZeroBits!S1);
136 
137     static struct S2
138     {
139         int a = 1;
140     }
141     static assert(!isInitAllZeroBits!S2);
142 
143     static struct S3
144     {
145         S1 a;
146         int b;
147     }
148     static assert(isInitAllZeroBits!S3);
149     static assert(isInitAllZeroBits!(S3[2]));
150 
151     static struct S4
152     {
153         S1 a;
154         S2 b;
155     }
156     static assert(!isInitAllZeroBits!S4);
157 
158     static struct S5
159     {
160         real r = 0;
161     }
162     static assert(isInitAllZeroBits!S5);
163 
164     static struct S6
165     {
166 
167     }
168     static assert(isInitAllZeroBits!S6);
169 
170     static struct S7
171     {
172         float[0] a;
173     }
174     // TODO: static assert(isInitAllZeroBits!S7);
175 
176     static class C1
177     {
178         int a = 1;
179     }
180     static assert(isInitAllZeroBits!C1);
181 
182     // Ensure Tuple can be read.
183     import std.typecons : Tuple;
184     static assert(isInitAllZeroBits!(Tuple!(int, int)));
185     static assert(!isInitAllZeroBits!(Tuple!(float, float)));
186 
187     // Ensure private fields of structs from other modules
188     // are taken into account.
189     import std.random : Mt19937;
190     static assert(!isInitAllZeroBits!Mt19937);
191     // Check that it works with const.
192     static assert(isInitAllZeroBits!(const(Mt19937)) == isInitAllZeroBits!Mt19937);
193     static assert(isInitAllZeroBits!(const(S5)) == isInitAllZeroBits!S5);
194 }
195 
196 /+ Can the representation be determined at compile time to consist of nothing
197  + but zero bits? Padding between a struct's fields is not considered.
198  +/
199 template isAllZeroBits(T, T value)
200 {
201     static if ((is(T == class) || is(T == typeof(null))) && // need this special case
202                value is null)   // because pointer must be compared with `is` instead of `==` for `SSOString` case below
203     {
204         enum isAllZeroBits = true;
205     }
206     else static if (value == T.init && // NOTE `value is T.init` crashes compiler for `SSOString`
207                     __traits(compiles, { enum _ = __traits(isZeroInit, T); }))
208     {
209         enum isAllZeroBits = __traits(isZeroInit, T);
210     }
211     else
212     {
213         // pragma(msg, "T: ", T.stringof, " value:", value);
214         import std.traits : isDynamicArray;
215         static if (isDynamicArray!(T))
216         {
217             enum isAllZeroBits = value is null && value.length is 0;
218         }
219         else static if (is(typeof(value is null)))
220         {
221             enum isAllZeroBits = value is null;
222         }
223         else static if (is(typeof(value is 0)))
224         {
225             enum isAllZeroBits = value is 0;
226         }
227         else static if (__traits(isStaticArray, T))
228         {
229             enum isAllZeroBits = ()
230             {
231                 // Use index so this works when T.length is 0.
232                 static foreach (i; 0 .. T.length)
233                 {
234                     if (!isAllZeroBits!(typeof(value[i]), value[i]))
235                         return false;
236                 }
237                 return true;
238             }();
239         }
240         else static if (is(T == struct) ||
241                         is(T == union))
242         {
243             enum isAllZeroBits = ()
244             {
245                 static foreach (e; value.tupleof)
246                 {
247                     if (!isAllZeroBits!(typeof(e), e))
248                         return false;
249                 }
250                 return true;
251             }();
252         }
253         else
254             enum isAllZeroBits = false;
255     }
256 }
257 
258 @nogc nothrow pure @safe unittest
259 {
260     static assert(isAllZeroBits!(int, 0));
261     static assert(!isAllZeroBits!(int, 1));
262 
263     import std.meta : AliasSeq;
264     foreach (Float; AliasSeq!(float, double, real))
265     {
266         assert(isAllZeroBits!(Float, 0.0));
267         assert(!isAllZeroBits!(Float, -0.0));
268         assert(!isAllZeroBits!(Float, Float.nan));
269     }
270 
271     static assert(isAllZeroBits!(void*, null));
272     static assert(isAllZeroBits!(int*, null));
273     static assert(isAllZeroBits!(Object, null));
274 }
275 
276 /+ Can the representation be determined at compile time to consist of nothing
277 but 1 bits? This is reported as $(B false) for structs with padding between
278 their fields because `opEquals` and hashing may rely on those bits being zero.
279 
280 Note:
281 A bool occupies 8 bits so `isAllOneBits!(bool, true) == false`
282 
283 See_Also:
284 https://forum.dlang.org/post/hn11oh$1usk$1@digitalmars.com
285 https://github.com/dlang/phobos/pull/6024
286 +/
287 template isAllOneBits(T, T value)
288 {
289     import std.traits : isIntegral, isSomeChar, Unsigned;
290     static if (isIntegral!T || isSomeChar!T)
291     {
292         import core.bitop : popcnt;
293         static if (T.min < T(0))
294             enum isAllOneBits = popcnt(cast(Unsigned!T) value) == T.sizeof * 8;
295         else
296             enum isAllOneBits = popcnt(value) == T.sizeof * 8;
297     }
298     else static if (__traits(isStaticArray, typeof(value)))
299     {
300         enum isAllOneBits = ()
301         {
302             bool b = true;
303             // Use index so this works when T.length is 0.
304             static foreach (i; 0 .. T.length)
305             {
306                 b &= isAllOneBits!(typeof(value[i]), value[i]);
307                 if (b == false)
308                     return b;
309             }
310 
311             return b;
312         }();
313     }
314     else static if (is(typeof(value) == struct))
315     {
316         enum isAllOneBits = ()
317         {
318             bool b = true;
319             size_t fieldSizeSum = 0;
320 			alias v = value.tupleof;
321             static foreach (const i, e; v)
322             {
323                 b &= isAllOneBits!(typeof(e), v[i]);
324                 if (b == false)
325                     return b;
326                 fieldSizeSum += typeof(e).sizeof;
327             }
328             // If fieldSizeSum == T.sizeof then there can be no gaps
329             // between fields.
330             return b && fieldSizeSum == T.sizeof;
331         }();
332     }
333     else
334     {
335         enum isAllOneBits = false;
336     }
337 }
338 
339 @nogc nothrow pure @safe unittest
340 {
341     static assert(isAllOneBits!(char, 0xff));
342     static assert(isAllOneBits!(wchar, 0xffff));
343     static assert(isAllOneBits!(byte, cast(byte) 0xff));
344     static assert(isAllOneBits!(int, 0xffff_ffff));
345     static assert(isAllOneBits!(char[4], [0xff, 0xff, 0xff, 0xff]));
346 
347     static assert(!isAllOneBits!(bool, true));
348     static assert(!isAllOneBits!(wchar, 0xff));
349     static assert(!isAllOneBits!(Object, Object.init));
350 
351     static struct S1
352     {
353         char a;
354         char b;
355     }
356     static assert(isAllOneBits!(S1, S1.init));
357 }
358 
359 /+ Can the representation be determined at compile time to consist of nothing
360 but 1 bits? This is reported as $(B false) for structs with padding between
361 their fields because `opEquals` and hashing may rely on those bits being zero.
362 
363 See_Also:
364 https://forum.dlang.org/post/hn11oh$1usk$1@digitalmars.com
365 https://github.com/dlang/phobos/pull/6024
366 +/
367 template isInitAllOneBits(T)
368 {
369     static if (__traits(isStaticArray, T) && __traits(compiles, T.init[0])) // TODO: avoid traits compiles here
370         enum isInitAllOneBits = __traits(compiles, { // TODO: avoid traits compiles here
371             static assert(isAllOneBits!(typeof(T.init[0]), T.init[0]));
372         });
373     else
374         enum isInitAllOneBits = __traits(compiles, { // TODO: avoid traits compiles here
375             static assert(isAllOneBits!(T, T.init));
376         });
377 }
378 
379 ///
380 @nogc nothrow pure @safe unittest
381 {
382     static assert(isInitAllOneBits!char);
383     static assert(isInitAllOneBits!wchar);
384     static assert(!isInitAllOneBits!dchar);
385 
386     static assert(isInitAllOneBits!(char[4]));
387     static assert(!isInitAllOneBits!(int[4]));
388     static assert(!isInitAllOneBits!Object);
389 
390     static struct S1
391     {
392         char a;
393         char b;
394     }
395     static assert(isInitAllOneBits!S1);
396 
397     static struct S2
398     {
399         char a = 1;
400     }
401     static assert(!isInitAllOneBits!S2);
402 
403     static struct S3
404     {
405         S1 a;
406         char b;
407     }
408     static assert(isInitAllOneBits!S3);
409     static assert(isInitAllOneBits!(S3[2]));
410 
411     static struct S4
412     {
413         S1 a;
414         S2 b;
415     }
416     static assert(!isInitAllOneBits!S4);
417 
418     static struct Sshort
419     {
420         short r = cast(short)0xffff;
421     }
422 	static assert(isInitAllOneBits!Sshort);
423 
424     static struct Sint
425     {
426         int r = 0xffff_ffff;
427     }
428 	static assert(isInitAllOneBits!Sint);
429 
430     static struct Slong
431     {
432         long r = 0xffff_ffff_ffff_ffff;
433     }
434 	static assert(isInitAllOneBits!Slong);
435 
436     // Verify that when there is padding between fields isInitAllOneBits is false.
437     static struct S10
438     {
439         align(4) char a;
440         align(4) char b;
441     }
442     static assert(!isInitAllOneBits!S10);
443 
444     static class C1
445     {
446         char c;
447     }
448     static assert(!isInitAllOneBits!C1);
449 }