1 /** Traits used by containers.
2  *
3  * TODO add `isUnorderedContainer` and `isUnorderedRange` traits and used to
4  * forbid hash algorithms to operate on unordered containers (such as
5  * `open_hashmap` and `open_hashmap`) and their ranges.
6  */
7 module nxt.container_traits;
8 
9 public import nxt.gc_traits;
10 
11 @safe:
12 
13 /** True if a `T` needs to be passed by move instead of value either because it
14  * cannot be copied or because it has an elaborate destructor.
15  *
16  * Note that `__traits(isPOD, T)` implies
17  * `core.internal.traits.hasElaborateAssign!T ||
18  *  core.internal.traits.hasElaborateDestructor!T`.
19  */
20 enum bool needsMove(T) = (!__traits(isCopyable, T) ||
21                           !__traits(isPOD, T));
22 
23 ///
24 @safe pure unittest
25 {
26     static assert(!needsMove!char);
27     static assert(!needsMove!int);
28     static assert(!needsMove!string);
29     static assert(!needsMove!(int[]));
30 
31     struct SomeUncopyable { @disable this(this); }
32     static assert(needsMove!SomeUncopyable);
33 
34     struct WithDtor { ~this() {} }
35     static assert(needsMove!WithDtor);
36 }
37 
38 // TODO this can be simplified for faster compilation
39 template ContainerElementType(ContainerType,
40                               ElementType)
41 {
42     import std.traits : isMutable, hasIndirections, PointerTarget, isPointer,
43         Unqual;
44 
45     template ET(bool isConst, T)
46     {
47         static if (isPointer!ElementType)
48         {
49             enum PointerIsConst = is(ElementType == const);
50             enum PointerIsImmutable = is(ElementType == immutable);
51             enum DataIsConst = is(PointerTarget!ElementType == const);
52             enum DataIsImmutable = is(PointerTarget!ElementType == immutable);
53             static if (isConst)
54             {
55                 static if (PointerIsConst)
56                     alias ET = ElementType;
57                 else static if (PointerIsImmutable)
58                     alias ET = ElementType;
59                 else
60                     alias ET = const(PointerTarget!ElementType)*;
61             }
62             else
63             {
64                 static assert(DataIsImmutable,
65                               "An immutable container cannot reference const or mutable data");
66                 static if (PointerIsConst)
67                     alias ET = immutable(PointerTarget!ElementType)*;
68                 else
69                     alias ET = ElementType;
70             }
71         }
72         else
73         {
74             static if (isConst)
75             {
76                 static if (is(ElementType == immutable))
77                     alias ET = ElementType;
78                 else
79                     alias ET = const(Unqual!ElementType);
80             }
81             else
82                 alias ET = immutable(Unqual!ElementType);
83         }
84     }
85 
86     static if (isMutable!ContainerType)
87         alias ContainerElementType = ElementType;
88     else
89     {
90         static if (hasIndirections!ElementType)
91             alias ContainerElementType = ET!(is(ContainerType == const), ElementType);
92         else
93             alias ContainerElementType = ElementType;
94     }
95 }
96 
97 /// Returns: `true` iff `T` is a template instance, `false` otherwise.
98 private template isTemplateInstance(T)
99 {
100     import std.traits : TemplateOf;
101     enum isTemplateInstance = is(typeof(TemplateOf!(T)));
102 }
103 
104 /** Is `true` iff `T` is a set like container. */
105 template isSet(T)
106 {
107     import std.range.primitives : hasLength;
108     enum isSet = (__traits(hasMember, T, "insert") && // TODO assert O(1)
109                   __traits(hasMember, T, "remove") && // TODO assert O(1)
110                   __traits(compiles, { auto _ = T.init.byElement; }));
111 }
112 
113 /** Is `true` iff `T` is a set like container with elements of type `E`. */
114 template isSetOf(T, E)
115 {
116     import std.range.primitives : hasLength;
117     enum isSetOf = (is(typeof(T.init.insert(E.init))) && // TODO assert O(1)
118                     is(typeof(T.init.remove(E.init))) && // TODO assert O(1)
119                     __traits(compiles, { auto _ = T.init.byElement; }));
120 }
121 
122 /** Allocate an array of `T`-elements of length `length` using `Allocator`.
123  */
124 T[] makeInitZeroArray(T, alias Allocator)(const size_t length) @trusted
125 {
126     version(none)               // TODO activate
127     {
128         // See: https://github.com/dlang/phobos/pull/6411
129         import std.experimental.allocator.gc_allocator : GCAllocator;
130         static if (__traits(hasMember, GCAllocator, "allocateZeroed"))
131         {
132             static assert(0, "Use std.experimental.allocator.package.make!(T) instead because it makes use of allocateZeroed.");
133         }
134     }
135     immutable byteCount = T.sizeof * length;
136     /* when possible prefer call to calloc before malloc+memset:
137      * https://stackoverflow.com/questions/2688466/why-mallocmemset-is-slower-than-calloc */
138     static if (__traits(hasMember, Allocator, "allocateZeroed"))
139     {
140         version(D_Coverage) {} else pragma(inline, true);
141         return cast(typeof(return))Allocator.allocateZeroed(byteCount);
142     }
143     else
144     {
145         auto array = cast(typeof(return))Allocator.allocate(byteCount);
146         import core.stdc..string : memset;
147         memset(array.ptr, 0, byteCount);
148         return array;
149     }
150 }
151 
152 /** Variant of `hasElaborateDestructor` that also checks for destructor when `S`
153  * is a `class`.
154  *
155  * See_Also: https://github.com/dlang/phobos/pull/4119
156  */
157 template hasElaborateDestructorNew(S)
158 {
159     static if (is(S == struct) ||
160                is(S == class)) // check also class
161     {
162         static if (__traits(hasMember, S, "__dtor"))
163             enum bool hasElaborateDestructorNew = true;
164         else
165         {
166             import std.traits : FieldTypeTuple;
167             import std.meta : anySatisfy;
168             enum hasElaborateDestructorNew = anySatisfy!(.hasElaborateDestructorNew, FieldTypeTuple!S);
169         }
170     }
171     else
172     {
173         import std.traits : isStaticArray;
174         static if (isStaticArray!S && S.length)
175             enum bool hasElaborateDestructorNew = hasElaborateDestructorNew!(typeof(S.init[0]));
176         else
177             enum bool hasElaborateDestructorNew = false;
178     }
179 }
180 
181 /** Is `true` iff `T` is repesented as a memory address. */
182 template isAddress(T)
183 {
184     static if (is(T == class))
185         enum isAddress = true;  // a class is memory-wise just a pointer
186     else
187     {
188         import std.traits : isPointer;
189         enum isAddress = isPointer!T;
190     }
191 }
192 
193 ///
194 @safe pure nothrow @nogc unittest
195 {
196     static assert( isAddress!(int*));
197     static assert(!isAddress!(int));
198 
199     class C {}
200     static assert( isAddress!(C));
201 
202     struct S {}
203     static assert(!isAddress!(S));
204     static assert( isAddress!(S*));
205 }