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  * `hybrid_hashmap` and `hybrid_hashmap`) and their ranges.
6  */
7 module nxt.container.traits;
8 
9 public import nxt.gc_traits;
10 
11 @safe:
12 
13 /++ Is true iff a `T` can be a assigned from an `U` l-value. +/
14 enum isLvalueAssignable(T, U = T) = __traits(compiles, { T t; U u; t = u; });
15 
16 /++ Is true iff a `T` can be a assigned from an `U` r-value
17 	Opposite to `std.traits.isRvalueAssignable` this correctly handles
18 	uncopyable types.
19  +/
20 template isRvalueAssignable(T, U = T) {
21 	static if (__traits(isCopyable, T))
22 		// needed as special cases such as T=int, U=long
23 		enum isRvalueAssignable = __traits(compiles, { T t; U u; t = u; });
24 	else
25 		// value range propagation (VRP) makes this true for `T=int`, `U=long` because of:
26 		enum isRvalueAssignable = __traits(compiles, { T t; t = U.init; });
27 }
28 
29 @safe pure unittest {
30 	static assert(isRvalueAssignable!(int, int));
31 	static assert(!isRvalueAssignable!(int, string));
32 	static assert(!isRvalueAssignable!(int, long));
33 	alias E = Uncopyable;
34 	static assert(isRvalueAssignable!(E, E));
35 }
36 
37 /** Is `true` iff `T` is a memory address (either a `class` or a pointer).
38 	TODO: Replace with __traits(isAddress, T) when it's added.
39  */
40 enum bool isAddress(T) = (is(T == class) ||
41 						  (is(T == U*, U) &&
42 						   T.sizeof == size_t.sizeof &&
43 						   // exclude alias this:
44 						   !(is(T == struct) ||
45 							 is(T == union) ||
46 							 is(T == interface))));
47 
48 ///
49 pure nothrow @safe @nogc unittest {
50 	static assert( isAddress!(int*));
51 	static assert(!isAddress!(int));
52 
53 	class C {}
54 	static assert( isAddress!(C));
55 
56 	struct S {}
57 	static assert(!isAddress!(S));
58 	static assert( isAddress!(S*));
59 }
60 
61 /** Is `true` iff `T` can and (for performance reasons) should be passed by value.
62  *
63  * @kinke: "The builtin `__argTypes` is (currently) only used/populated for Posix x64
64  * (and AArch64 for LDC), and not used by GDC at all AFAIK".
65  *
66  * See_Also: https://github.com/dlang/dmd/pull/11000
67  * See_Also: https://github.com/dlang/dmd/pull/11000#issuecomment-671103778
68  */
69 enum shouldBePassedByValue(T) = (__traits(isPOD, T) && is(T U == __argTypes) && U.length >= 1);
70 
71 /** True if the last reference of a `T` in the scope of its lifetime should be
72  * passed by move instead of by copy either because
73  *
74  * - it cannot be copied or
75  * - because it has an elaborate constructor or elaborate destructor that can be
76  *   elided via a move.
77  *
78  * This excludes arrays and classes.
79  *
80  * Note that `__traits(isPOD, T)` implies
81  * `core.internal.traits.hasElaborateAssign!T ||
82  *  core.internal.traits.hasElaborateDestructor!T`.
83  *
84  * See_Also: `std.traits.hasElaborateMove`.
85  */
86 enum bool shouldMove(T) = !__traits(isPOD, T);
87 
88 ///
89 pure @safe unittest {
90 	static assert(!shouldMove!(char));
91 	static assert(!shouldMove!(int));
92 	static assert(!shouldMove!(string));
93 	static assert(!shouldMove!(int[]));
94 
95 	class C {}
96 	static assert(!shouldMove!(C));
97 
98 	struct POD {}
99 	static assert(!shouldMove!(POD));
100 
101 	static assert(shouldMove!(Uncopyable));
102 
103 	struct WithDtor { ~this() nothrow {} }
104 	static assert(shouldMove!(WithDtor));
105 }
106 
107 /+ TODO: this can be simplified for faster compilation +/
108 template ContainerElementType(ContainerType, ElementType) {
109 	import std.traits : isMutable, hasIndirections, PointerTarget, isPointer,
110 		Unqual;
111 
112 	template ET(bool isConst, T) {
113 		static if (isPointer!ElementType) {
114 			enum PointerIsConst = is(ElementType == const);
115 			enum PointerIsImmutable = is(ElementType == immutable);
116 			enum DataIsConst = is(PointerTarget!ElementType == const);
117 			enum DataIsImmutable = is(PointerTarget!ElementType == immutable);
118 			static if (isConst) {
119 				static if (PointerIsConst)
120 					alias ET = ElementType;
121 				else static if (PointerIsImmutable)
122 					alias ET = ElementType;
123 				else
124 					alias ET = const(PointerTarget!ElementType)*;
125 			}
126 			else
127 			{
128 				static assert(DataIsImmutable,
129 							  "An immutable container cannot reference const or mutable data");
130 				static if (PointerIsConst)
131 					alias ET = immutable(PointerTarget!ElementType)*;
132 				else
133 					alias ET = ElementType;
134 			}
135 		}
136 		else
137 		{
138 			static if (isConst) {
139 				static if (is(ElementType == immutable))
140 					alias ET = ElementType;
141 				else
142 					alias ET = const(Unqual!ElementType);
143 			}
144 			else
145 				alias ET = immutable(Unqual!ElementType);
146 		}
147 	}
148 
149 	static if (isMutable!ContainerType)
150 		alias ContainerElementType = ElementType;
151 	else
152 	{
153 		static if (hasIndirections!ElementType)
154 			alias ContainerElementType = ET!(is(ContainerType == const), ElementType);
155 		else
156 			alias ContainerElementType = ElementType;
157 	}
158 }
159 
160 /// Returns: `true` iff `T` is a template instance, `false` otherwise.
161 private template isTemplateInstance(T) {
162 	import std.traits : TemplateOf;
163 	enum isTemplateInstance = is(typeof(TemplateOf!(T)));
164 }
165 
166 /** Is `true` iff `T` is a set like container. */
167 template isSet(T) {
168 	import std.range.primitives : hasLength;
169 	enum isSet = (__traits(hasMember, T, "insert") && /+ TODO: assert O(1) +/
170 				  __traits(hasMember, T, "remove") && /+ TODO: assert O(1) +/
171 				  __traits(compiles, { auto _ = T.init.byElement; }));
172 }
173 
174 /** Is `true` iff `T` is a set like container with elements of type `E`. */
175 template isSetOf(T, E) {
176 	import std.range.primitives : hasLength;
177 	enum isSetOf = (is(typeof(T.init.insert(E.init))) && /+ TODO: assert O(1) +/
178 					is(typeof(T.init.remove(E.init))) && /+ TODO: assert O(1) +/
179 					__traits(compiles, { auto _ = T.init.byElement; }));
180 }
181 
182 /** Allocate an array of `T`-elements of length `length` using `allocator`.
183  */
184 T[] makeInitZeroArray(T, alias allocator)(const size_t length) @trusted
185 {
186 	version (none)			   /+ TODO: activate +/
187 	{
188 		// See: https://github.com/dlang/phobos/pull/6411
189 		import std.experimental.allocator.gc_allocator : GCAllocator;
190 		static if (__traits(hasMember, GCAllocator, "allocateZeroed")) {
191 			static assert(0, "Use std.experimental.allocator.package.make!(T) instead because it makes use of allocateZeroed.");
192 		}
193 	}
194 	immutable byteCount = T.sizeof * length;
195 	/* when possible prefer call to calloc before malloc+memset:
196 	 * https://stackoverflow.com/questions/2688466/why-mallocmemset-is-slower-than-calloc */
197 	static if (__traits(hasMember, allocator, "allocateZeroed")) {
198 		version (D_Coverage) {} else pragma(inline, true);
199 		return cast(typeof(return))allocator.allocateZeroed(byteCount);
200 	}
201 	else
202 	{
203 		auto array = cast(typeof(return))allocator.allocate(byteCount);
204 		import core.stdc.string : memset;
205 		memset(array.ptr, 0, byteCount);
206 		return array;
207 	}
208 }
209 
210 /** Variant of `hasElaborateDestructor` that also checks for destructor when `S`
211  * is a `class`.
212  *
213  * See_Also: https://github.com/dlang/phobos/pull/4119
214  */
215 template hasElaborateDestructorNew(S) {
216 	static if (is(S == struct) ||
217 			   is(S == class)) // check also class
218 	{
219 		static if (__traits(hasMember, S, "__dtor"))
220 			enum bool hasElaborateDestructorNew = true;
221 		else
222 		{
223 			import std.traits : FieldTypeTuple;
224 			import std.meta : anySatisfy;
225 			enum hasElaborateDestructorNew = anySatisfy!(.hasElaborateDestructorNew, FieldTypeTuple!S);
226 		}
227 	}
228 	else
229 	{
230 		static if (__traits(isStaticArray, S) && S.length)
231 			enum bool hasElaborateDestructorNew = hasElaborateDestructorNew!(typeof(S.init[0]));
232 		else
233 			enum bool hasElaborateDestructorNew = false;
234 	}
235 }
236 
237 version (unittest) {
238 	private static struct Uncopyable { this(this) @disable; int _x; }
239 }