The OpenD Programming Language

1 /**
2  * Generic tagged union and algebraic data type implementations.
3  *
4  * Copyright: Copyright 2015-2019, Sönke Ludwig.
5  * License:   $(WEB www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
6  * Authors:   Sönke Ludwig
7 */
8 module taggedalgebraic.taggedunion;
9 
10 // scheduled for deprecation
11 static import taggedalgebraic.visit;
12 alias visit = taggedalgebraic.visit.visit;
13 
14 import std.algorithm.mutation : move, swap;
15 import std.meta;
16 import std.range : isOutputRange;
17 import std.traits : EnumMembers, FieldNameTuple, Unqual, hasUDA, isInstanceOf;
18 
19 
20 /** Implements a generic tagged union type.
21 
22 	This struct takes a `union` or `struct` declaration as an input and builds
23 	an algebraic data type from its fields, using an automatically generated
24 	`Kind` enumeration to identify which field of the union is currently used.
25 	Multiple fields with the same value are supported.
26 
27 	For each field defined by `U` a number of convenience members are generated.
28 	For a given field "foo", these fields are:
29 
30 	$(UL
31 		$(LI `static foo(value)` - returns a new tagged union with the specified value)
32 		$(LI `isFoo` - equivalent to `kind == Kind.foo`)
33 		$(LI `setFoo(value)` - equivalent to `set!(Kind.foo)(value)`)
34 		$(LI `getFoo` - equivalent to `get!(Kind.foo)`)
35 	)
36 */
37 template TaggedUnion(U) if (is(U == union) || is(U == struct) || is(U == enum)) {
38 align(commonAlignment!(UnionKindTypes!(UnionFieldEnum!U))) struct TaggedUnion
39 {
40 	import std.traits : FieldTypeTuple, FieldNameTuple, Largest,
41 		hasElaborateCopyConstructor, hasElaborateDestructor, isCopyable;
42 	import std.meta : templateOr;
43 	import std.ascii : toUpper;
44 
45 	alias FieldDefinitionType = U;
46 
47 	/// A type enum that identifies the type of value currently stored.
48 	alias Kind = UnionFieldEnum!U;
49 
50 	alias FieldTypes = UnionKindTypes!Kind;
51 	alias fieldNames = UnionKindNames!Kind;
52 
53 	static assert(FieldTypes.length > 0, "The TaggedUnions's union type must have at least one field.");
54 	static assert(FieldTypes.length == fieldNames.length);
55 
56 	package alias FieldTypeByName(string name) = FieldTypes[__traits(getMember, Kind, name)];
57 
58 	private {
59 		static if (isUnitType!(FieldTypes[0]) || __VERSION__ < 2072) {
60 			void[Largest!FieldTypes.sizeof] m_data;
61 			@property ref inout(void[Largest!FieldTypes.sizeof]) rawData() inout @safe return { return m_data; }
62 		} else {
63 			union Dummy {
64 				FieldTypes[0] initField;
65 				void[Largest!FieldTypes.sizeof] data;
66 			}
67 			Dummy m_data = { initField: FieldTypes[0].init };
68 			@property ref inout(void[Largest!FieldTypes.sizeof]) rawData() inout @trusted return { return m_data.data; }
69 		}
70 		Kind m_kind;
71 	}
72 
73 	this(TaggedUnion other)
74 	{
75 		rawSwap(this, other);
76 	}
77 
78 	void opAssign(TaggedUnion other)
79 	{
80 		rawSwap(this, other);
81 	}
82 
83 	static foreach (ti; UniqueTypes!FieldTypes)
84 		static if(!is(FieldTypes[ti] == void))
85 		{
86 			this(FieldTypes[ti] value)
87 			{
88 				static if (isUnitType!(FieldTypes[ti]))
89 					set!(cast(Kind)ti)();
90 				else
91 					set!(cast(Kind)ti)(.move(value));
92 			}
93 
94 			void opAssign(FieldTypes[ti] value)
95 			{
96 				static if (isUnitType!(FieldTypes[ti]))
97 					set!(cast(Kind)ti)();
98 				else
99 					set!(cast(Kind)ti)(.move(value));
100 			}
101 		}
102 
103 	// disable default construction if first type is not a null/Void type
104 	static if (!isUnitType!(FieldTypes[0]) && __VERSION__ < 2072) {
105 		@disable this();
106 	}
107 
108 	// postblit constructor
109 	static if (!allSatisfy!(templateOr!(isCopyable, isUnitType), FieldTypes)) {
110 		@disable this(this);
111 	} else static if (anySatisfy!(hasElaborateCopyConstructor, FieldTypes)) {
112 		this(this)
113 		{
114 			switch (m_kind) {
115 				default: break;
116 				foreach (i, tname; fieldNames) {
117 					alias T = FieldTypes[i];
118 					static if (hasElaborateCopyConstructor!T)
119 					{
120 						case __traits(getMember, Kind, tname):
121 							static if (hasUDA!(U, typeof(forceNothrowPostblit()))) {
122 								try typeid(T).postblit(cast(void*)&trustedGet!T());
123 								catch (Exception e) assert(false, e.msg);
124 							} else {
125 								typeid(T).postblit(cast(void*)&trustedGet!T());
126 							}
127 							return;
128 					}
129 				}
130 			}
131 		}
132 	}
133 
134 	// destructor
135 	static if (anySatisfy!(hasElaborateDestructor, FieldTypes)) {
136 		~this()
137 		{
138 			final switch (m_kind) {
139 				foreach (i, tname; fieldNames) {
140 					alias T = FieldTypes[i];
141 					case __traits(getMember, Kind, tname):
142 						static if (hasElaborateDestructor!T) {
143 							.destroy(trustedGet!T);
144 						}
145 						return;
146 				}
147 			}
148 		}
149 	}
150 
151 	/// Enables conversion or extraction of the stored value.
152 	T opCast(T)()
153 	{
154 		import std.conv : to;
155 
156 		final switch (m_kind) {
157 			foreach (i, FT; FieldTypes) {
158 				case __traits(getMember, Kind, fieldNames[i]):
159 					static if (is(typeof(trustedGet!FT) : T))
160 						return trustedGet!FT;
161 					else static if (is(typeof(to!T(trustedGet!FT)))) {
162 						return to!T(trustedGet!FT);
163 					} else {
164 						assert(false, "Cannot cast a " ~ fieldNames[i]
165 								~ " value of type " ~ FT.stringof ~ " to " ~ T.stringof);
166 					}
167 			}
168 		}
169 		assert(false); // never reached
170 	}
171 	/// ditto
172 	T opCast(T)() const
173 	{
174 		// this method needs to be duplicated because inout doesn't work with to!()
175 		import std.conv : to;
176 
177 		final switch (m_kind) {
178 			foreach (i, FT; FieldTypes) {
179 				case __traits(getMember, Kind, fieldNames[i]):
180 					static if (is(typeof(trustedGet!FT) : T))
181 						return trustedGet!FT;
182 					else static if (is(typeof(to!T(trustedGet!FT)))) {
183 						return to!T(trustedGet!FT);
184 					} else {
185 						assert(false, "Cannot cast a " ~ fieldNames[i]
186 								~ " value of type" ~ FT.stringof ~ " to " ~ T.stringof);
187 					}
188 			}
189 		}
190 		assert(false); // never reached
191 	}
192 
193 	/// Enables equality comparison with the stored value.
194 	bool opEquals()(auto ref inout(TaggedUnion) other)
195 	inout {
196 		if (this.kind != other.kind) return false;
197 
198 		final switch (this.kind) {
199 			foreach (i, fname; TaggedUnion!U.fieldNames)
200 				case __traits(getMember, Kind, fname):
201 					return trustedGet!(FieldTypes[i]) == other.trustedGet!(FieldTypes[i]);
202 		}
203 		assert(false); // never reached
204 	}
205 
206 	static if (allSatisfy!(isHashable, FieldTypes))
207 	{
208 		/// Enables using a tagged union value as an associative array key.
209 		size_t toHash()
210 		const @safe nothrow {
211 			size_t ret;
212 			final switch (m_kind) {
213 				foreach (i, tname; fieldNames) {
214 					alias T = FieldTypes[i];
215 					case __traits(getMember, Kind, tname):
216 						static if (!isUnitType!T) {
217 							ret = hashOf(trustedGet!T);
218 						}
219 						break;
220 				}
221 			}
222 			return ret ^ (m_kind * 0xBA7A57E3);
223 		}
224 	}
225 
226 	/// The type ID of the currently stored value.
227 	@property Kind kind() const { return m_kind; }
228 
229 	static foreach (i, name; fieldNames) {
230 		// NOTE: using getX/setX here because using just x would be prone to
231 		//       misuse (attempting to "get" a value for modification when
232 		//       a different kind is set instead of assigning a new value)
233 		mixin("alias set"~pascalCase(name)~" = set!(Kind."~name~");");
234 		mixin("@property bool is"~pascalCase(name)~"() const { return m_kind == Kind."~name~"; }");
235 
236 		static if (name[$-1] == '_') {
237 			mixin("alias set"~pascalCase(name[0 .. $-1])~" = set!(Kind."~name~");");
238 			mixin("@property bool is"~pascalCase(name[0 .. $-1])~"() const { return m_kind == Kind."~name~"; }");
239 		}
240 
241 		static if (!isUnitType!(FieldTypes[i])) {
242 			mixin("alias "~name~"Value = value!(Kind."~name~");");
243 
244 			// remove trailing underscore from names like "int_"
245 			static if (name[$-1] == '_')
246 				mixin("alias "~name[0 .. $-1]~"Value = value!(Kind."~name~");");
247 
248 			mixin("static TaggedUnion "~name~"(FieldTypes["~i.stringof~"] value)"
249 				~ "{ TaggedUnion tu; tu.set!(Kind."~name~")(.move(value)); return tu; }");
250 
251 			// TODO: define assignment operator for unique types
252 		} else {
253 			mixin("static @property TaggedUnion "~name~"() { TaggedUnion tu; tu.set!(Kind."~name~"); return tu; }");
254 		}
255 	}
256 
257 	/** Checks whether the currently stored value has a given type.
258 	*/
259 	@property bool hasType(T)()
260 	const {
261 		static assert(staticIndexOf!(T, FieldTypes) >= 0, "Type "~T.stringof~ " not part of "~FieldTypes.stringof);
262 
263 		final switch (this.kind) {
264 			static foreach (i, n; fieldNames) {
265 				case __traits(getMember, Kind, n):
266 					return is(FieldTypes[i] == T);
267 			}
268 		}
269 	}
270 
271 	/** Accesses the contained value by reference.
272 
273 		The specified `kind` must equal the current value of the `this.kind`
274 		property. Setting a different type must be done with `set` or `opAssign`
275 		instead.
276 
277 		See_Also: `set`, `opAssign`
278 	*/
279 	@property ref value(Kind kind)()
280 	inout {
281 		if (this.kind != kind) {
282 			enum msg(.string k_is) = "Attempt to get kind "~kind.stringof~" from tagged union with kind "~k_is;
283 			final switch (this.kind) {
284 				static foreach (i, n; fieldNames)
285 					case __traits(getMember, Kind, n):
286 						assert(false, msg!n);
287 			}
288 		}
289 		return trustedGet!(FieldTypes[kind]);
290 	}
291 
292 
293 	/** Accesses the contained value by reference.
294 
295 		The specified type `T` must equal the type of the currently set value.
296 		Setting a different type must be done with `set` or `opAssign` instead.
297 
298 		See_Also: `set`, `opAssign`
299 	*/
300 	@property ref inout(T) value(T)() inout
301 	{
302 		static assert(staticIndexOf!(T, FieldTypes) >= 0, "Type "~T.stringof~ " not part of "~FieldTypes.stringof);
303 
304 		final switch (this.kind) {
305 			static foreach (i, n; fieldNames) {
306 				case __traits(getMember, Kind, n):
307 					static if (is(FieldTypes[i] == T))
308 						return trustedGet!T;
309 					else assert(false, "Attempting to get type "~T.stringof
310 						~ " from a TaggedUnion with type "
311 						~ FieldTypes[__traits(getMember, Kind, n)].stringof);
312 			}
313 		}
314 	}
315 
316 	/** Sets a new value of the specified `kind`.
317 	*/
318 	ref FieldTypes[kind] set(Kind kind)(FieldTypes[kind] value)
319 		if (!isUnitType!(FieldTypes[kind]))
320 	{
321 		if (m_kind != kind) {
322 			destroy(this);
323 			this.rawData.rawEmplace(value);
324 		} else {
325 			rawSwap(trustedGet!(FieldTypes[kind]), value);
326 		}
327 		m_kind = kind;
328 
329 		return trustedGet!(FieldTypes[kind]);
330 	}
331 
332 	/** Sets a `void` value of the specified kind.
333 	*/
334 	void set(Kind kind)()
335 		if (isUnitType!(FieldTypes[kind]))
336 	{
337 		if (m_kind != kind) {
338 			destroy(this);
339 		}
340 		m_kind = kind;
341 	}
342 
343 	/** Converts the contained value to a string.
344 
345 		The format output by this method is "(kind: value)", where "kind" is
346 		the enum name of the currently stored type and "value" is the string
347 		representation of the stored value.
348 	*/
349 	void toString(W)(ref W w) const
350 		if (isOutputRange!(W, char))
351 	{
352 		import std.range.primitives : put;
353 		import std.conv : text;
354 		import std.format : FormatSpec, formatValue;
355 
356 		final switch (m_kind) {
357 			foreach (i, v; EnumMembers!Kind) {
358 				case v:
359 					enum vstr = text(v);
360 					static if (isUnitType!(FieldTypes[i])) put(w, vstr);
361 					else {
362 						// NOTE: using formatValue instead of formattedWrite
363 						//       because formattedWrite does not work for
364 						//       non-copyable types
365 						enum prefix = "(" ~ vstr ~ ": ";
366 						enum suffix = ")";
367 						put(w, prefix);
368 						FormatSpec!char spec;
369 						formatValue(w, value!v, spec);
370 						put(w, suffix);
371 					}
372 					break;
373 			}
374 		}
375 	}
376 
377 	package @trusted @property ref inout(T) trustedGet(T)() inout { return *cast(inout(T)*)this.rawData.ptr; }
378 }
379 }
380 
381 ///
382 @safe nothrow unittest {
383 	union Kinds {
384 		int count;
385 		string text;
386 	}
387 	alias TU = TaggedUnion!Kinds;
388 
389 	// default initialized to the first field defined
390 	TU tu;
391 	assert(tu.kind == TU.Kind.count);
392 	assert(tu.isCount); // equivalent to the line above
393 	assert(!tu.isText);
394 	assert(tu.value!(TU.Kind.count) == int.init);
395 
396 	// set to a specific count
397 	tu.setCount(42);
398 	assert(tu.isCount);
399 	assert(tu.countValue == 42);
400 	assert(tu.value!(TU.Kind.count) == 42);
401 	assert(tu.value!int == 42); // can also get by type
402 	assert(tu.countValue == 42);
403 
404 	// assign a new tagged algebraic value
405 	tu = TU.count(43);
406 
407 	// test equivalence with other tagged unions
408 	assert(tu == TU.count(43));
409 	assert(tu != TU.count(42));
410 	assert(tu != TU.text("hello"));
411 
412 	// modify by reference
413 	tu.countValue++;
414 	assert(tu.countValue == 44);
415 
416 	// set the second field
417 	tu.setText("hello");
418 	assert(!tu.isCount);
419 	assert(tu.isText);
420 	assert(tu.kind == TU.Kind.text);
421 	assert(tu.textValue == "hello");
422 
423 	// unique types can also be directly constructed
424 	tu = TU(12);
425 	assert(tu.countValue == 12);
426 	tu = TU("foo");
427 	assert(tu.textValue == "foo");
428 }
429 
430 ///
431 @safe nothrow unittest {
432 	// Enum annotations supported since DMD 2.082.0. The mixin below is
433 	// necessary to keep the parser happy on older versions.
434 	static if (__VERSION__ >= 2082) {
435 		alias myint = int;
436 		// tagged unions can be defined in terms of an annotated enum
437 		mixin(q{enum E {
438 			none,
439 			@string text
440 		}});
441 
442 		alias TU = TaggedUnion!E;
443 		static assert(is(TU.Kind == E));
444 
445 		TU tu;
446 		assert(tu.isNone);
447 		assert(tu.kind == E.none);
448 
449 		tu.setText("foo");
450 		assert(tu.kind == E.text);
451 		assert(tu.textValue == "foo");
452 	}
453 }
454 
455 unittest { // test for name clashes
456 	union U { .string string; }
457 	alias TU = TaggedUnion!U;
458 	TU tu;
459 	tu = TU..string("foo");
460 	assert(tu.isString);
461 	assert(tu.stringValue == "foo");
462 }
463 
464 unittest { // test woraround for Phobos issue 19696
465 	struct T {
466 		struct F { int num; }
467 		alias Payload = TaggedUnion!F;
468 		Payload payload;
469 		alias payload this;
470 	}
471 
472 	struct U {
473 		T t;
474 	}
475 
476 	alias TU = TaggedUnion!U;
477 	static assert(is(TU.FieldTypes[0] == T));
478 }
479 
480 unittest { // non-copyable types
481 	import std.traits : isCopyable;
482 
483 	struct S { @disable this(this); }
484 	struct U {
485 		int i;
486 		S s;
487 	}
488 	alias TU = TaggedUnion!U;
489 	static assert(!isCopyable!TU);
490 
491 	auto tu = TU(42);
492 	tu.setS(S.init);
493 }
494 
495 unittest { // alignment
496 	union S1 { int v; }
497 	union S2 { ulong v; }
498 	union S3 { void* v; }
499 
500 	// sanity check for the actual checks - this may differ on non-x86 architectures
501 	static assert(S1.alignof == 4);
502 	static assert(S2.alignof == 8);
503 	version (D_LP64) static assert(S3.alignof == 8);
504 	else static assert(S3.alignof == 4);
505 
506 	// test external struct alignment
507 	static assert(TaggedUnion!S1.alignof == 4);
508 	static assert(TaggedUnion!S2.alignof == 8);
509 	version (D_LP64) static assert(TaggedUnion!S3.alignof == 8);
510 	else static assert(TaggedUnion!S3.alignof == 4);
511 
512 	// test internal struct alignment
513 	TaggedUnion!S1 s1;
514 	assert((cast(ubyte*)&s1.vValue() - cast(ubyte*)&s1) % 4 == 0);
515 	TaggedUnion!S1 s2;
516 	assert((cast(ubyte*)&s2.vValue() - cast(ubyte*)&s2) % 8 == 0);
517 	TaggedUnion!S1 s3;
518 	version (D_LP64) assert((cast(ubyte*)&s3.vValue() - cast(ubyte*)&s3) % 8 == 0);
519 	else assert((cast(ubyte*)&s3.vValue() - cast(ubyte*)&s3) % 4 == 0);
520 }
521 
522 unittest { // toString
523 	import std.conv : to;
524 
525 	static struct NoCopy {
526 		@disable this(this);
527 		string toString() const { return "foo"; }
528 	}
529 
530 	union U { Void empty; int i; NoCopy noCopy; }
531 	TaggedUnion!U val;
532 	assert(val.to!string == "empty");
533 	val.setI(42);
534 	assert(val.to!string == "(i: 42)");
535 	val.setNoCopy(NoCopy.init);
536 	assert(val.to!string == "(noCopy: foo)");
537 }
538 
539 unittest { // null members should be assignable
540 	union U { int i; typeof(null) Null; }
541 	TaggedUnion!U val;
542 	val = null;
543 	assert(val.kind == val.Kind.Null);
544 	val = TaggedUnion!U(null);
545 	assert(val.kind == val.Kind.Null);
546 }
547 
548 unittest { // make sure field names don't conflict with function names
549 	union U { int to; int move; int swap; }
550 	TaggedUnion!U val;
551 	val.setMove(1);
552 }
553 
554 unittest { // support trailing underscores properly
555 	union U {
556 		int int_;
557 	}
558 	TaggedUnion!U val;
559 
560 	val = TaggedUnion!U.int_(10);
561 	assert(val.int_Value == 10);
562 	assert(val.intValue == 10);
563 	assert(val.isInt_);
564 	assert(val.isInt);
565 	val.setInt_(20);
566 	val.setInt(20);
567 	assert(val.intValue == 20);
568 }
569 
570 @safe nothrow unittest {
571 	static struct S { int i; string s; }
572 	alias TU = TaggedUnion!S;
573 
574 	static assert(is(typeof(TU.init.toHash()) == size_t));
575 
576 	int[TU] aa;
577 	aa[TU(1)] = 1;
578 	aa[TU("foo")] = 2;
579 
580 	assert(aa[TU(1)] == 1);
581 	assert(aa[TU("foo")] == 2);
582 }
583 
584 
585 @property auto forceNothrowPostblit()
586 {
587 	if (!__ctfe) assert(false, "@forceNothrowPostblit must only be used as a UDA.");
588 	static struct R {}
589 	return R.init;
590 }
591 
592 nothrow unittest {
593 	static struct S {
594 		this(this) nothrow {}
595 	}
596 
597 	@forceNothrowPostblit
598 	struct U {
599 		S s;
600 	}
601 
602 	alias TU = TaggedUnion!U;
603 
604 	TU tu, tv;
605 	tu = S.init;
606 	tv = tu;
607 }
608 
609 unittest {
610 	static struct S1 { int num; }
611 	alias T1 = TaggedUnion!S1;
612 	static assert(is(const(T1) : T1));
613 	static assert(is(typeof(T1.init.value!int) == int));
614 	static assert(is(typeof(T1.init.value!(T1.Kind.num)) == int));
615 	static assert(is(typeof(T1.init.numValue) == int));
616 	static assert(is(typeof(const(T1).init.value!int) == const(int)));
617 	static assert(is(typeof(const(T1).init.value!(T1.Kind.num)) == const(int)));
618 	static assert(is(typeof(const(T1).init.numValue) == const(int)));
619 
620 	static struct S2 { int[] nums; }
621 	alias T2 = TaggedUnion!S2;
622 	static assert(!is(const(T2) : T2));
623 }
624 
625 
626 enum isUnitType(T) = is(T == Void) || is(T == void) || is(T == typeof(null));
627 
628 
629 private string pascalCase(string camel_case)
630 {
631 	if (!__ctfe) assert(false);
632 	import std.ascii : toUpper;
633 	return camel_case[0].toUpper ~ camel_case[1 .. $];
634 }
635 
636 /** Maps a kind enumeration value to the corresponding field type.
637 
638 	`kind` must be a value of the `TaggedAlgebraic!T.Kind` enumeration.
639 */
640 template TypeOf(alias kind)
641 	if (is(typeof(kind) == enum))
642 {
643 	import std.traits : FieldTypeTuple, TemplateArgsOf;
644 	import std.typecons : ReplaceType;
645 
646 	static if (isInstanceOf!(UnionFieldEnum, typeof(kind))) {
647 		alias U = TemplateArgsOf!(typeof(kind));
648 		alias FT = FieldTypeTuple!U[kind];
649 	} else {
650 		alias U = typeof(kind);
651 		alias Types = UnionKindTypes!(typeof(kind));
652 		alias uda = AliasSeq!(__traits(getAttributes, kind));
653 		static if (uda.length == 0) alias FT = void;
654 		else alias FT = uda[0];
655 	}
656 
657 	// NOTE: ReplaceType has issues with certain types, such as a class
658 	//       declaration like this: class C : D!C {}
659 	//       For this reason, we test first if it compiles and only then use it.
660 	//       It also replaces a type with the contained "alias this" type under
661 	//       certain conditions, so we make a second check to see heuristically
662 	//       if This is actually present in FT
663 	//
664 	//       Phobos issues: 19696, 19697
665 	static if (is(ReplaceType!(This, U, FT)) && !is(ReplaceType!(This, void, FT)))
666 		alias TypeOf = ReplaceType!(This, U, FT);
667 	else alias TypeOf = FT;
668 }
669 
670 ///
671 unittest {
672 	static struct S {
673 		int a;
674 		string b;
675 		string c;
676 	}
677 	alias TU = TaggedUnion!S;
678 
679 	static assert(is(TypeOf!(TU.Kind.a) == int));
680 	static assert(is(TypeOf!(TU.Kind.b) == string));
681 	static assert(is(TypeOf!(TU.Kind.c) == string));
682 }
683 
684 unittest {
685 	struct S {
686 		TaggedUnion!This[] test;
687 	}
688 	alias TU = TaggedUnion!S;
689 
690 	TypeOf!(TU.Kind.test) a;
691 
692 	static assert(is(TypeOf!(TU.Kind.test) == TaggedUnion!S[]));
693 }
694 
695 
696 /// Convenience type that can be used for union fields that have no value (`void` is not allowed).
697 struct Void {}
698 
699 /** Special type used as a placeholder for `U` within the definition of `U` to
700 	enable self-referential types.
701 
702 	Note that this is recognized only if used as the first argument to a
703 	template type.
704 */
705 struct This { Void nothing; }
706 
707 ///
708 unittest {
709 	union U {
710 		TaggedUnion!This[] list;
711 		int number;
712 		string text;
713 	}
714 	alias Node = TaggedUnion!U;
715 
716 	auto n = Node([Node(12), Node("foo")]);
717 	assert(n.isList);
718 	assert(n.listValue == [Node(12), Node("foo")]);
719 }
720 
721 package template UnionFieldEnum(U)
722 {
723 	static if (is(U == enum)) alias UnionFieldEnum = U;
724 	else {
725 		import std.array : join;
726 		import std.traits : FieldNameTuple;
727 		mixin("enum UnionFieldEnum { " ~ [FieldNameTuple!U].join(", ") ~ " }");
728 	}
729 }
730 
731 deprecated alias TypeEnum(U) = UnionFieldEnum!U;
732 
733 package alias UnionKindTypes(FieldEnum) = staticMap!(TypeOf, EnumMembers!FieldEnum);
734 package alias UnionKindNames(FieldEnum) = AliasSeq!(__traits(allMembers, FieldEnum));
735 
736 package template UniqueTypes(Types...) {
737 	template impl(size_t i) {
738 		static if (i < Types.length) {
739 			alias T = Types[i];
740 			static if (staticIndexOf!(T, Types) == i && staticIndexOf!(T, Types[i+1 .. $]) < 0)
741 				alias impl = AliasSeq!(i, impl!(i+1));
742 			else alias impl = AliasSeq!(impl!(i+1));
743 		} else alias impl = AliasSeq!();
744 	}
745 	alias UniqueTypes = impl!0;
746 }
747 
748 package template AmbiguousTypes(Types...) {
749 	template impl(size_t i) {
750 		static if (i < Types.length) {
751 			alias T = Types[i];
752 			static if (staticIndexOf!(T, Types) == i && staticIndexOf!(T, Types[i+1 .. $]) >= 0)
753 				alias impl = AliasSeq!(i, impl!(i+1));
754 			else alias impl = impl!(i+1);
755 		} else alias impl = AliasSeq!();
756 	}
757 	alias AmbiguousTypes = impl!0;
758 }
759 
760 /// Computes the minimum alignment necessary to align all types correctly
761 private size_t commonAlignment(TYPES...)()
762 {
763 	import std.numeric : gcd;
764 
765 	size_t ret = 1;
766 	foreach (T; TYPES)
767 		ret = (T.alignof * ret) / gcd(T.alignof, ret);
768 	return ret;
769 }
770 
771 unittest {
772 	align(2) struct S1 { ubyte x; }
773 	align(4) struct S2 { ubyte x; }
774 	align(8) struct S3 { ubyte x; }
775 
776 	static if (__VERSION__ > 2076) { // DMD 2.076 ignores the alignment
777 		assert(commonAlignment!S1 == 2);
778 		assert(commonAlignment!S2 == 4);
779 		assert(commonAlignment!S3 == 8);
780 		assert(commonAlignment!(S1, S3) == 8);
781 		assert(commonAlignment!(S1, S2, S3) == 8);
782 		assert(commonAlignment!(S2, S2, S1) == 4);
783 	}
784 }
785 
786 private template isHashable(T)
787 {
788 	static if (isUnitType!T) enum isHashable = true;
789 	else static if (__traits(compiles, (ref const(T) val) @safe nothrow => hashOf(val)))
790 		enum isHashable = true;
791 	else enum isHashable = false;
792 }
793 
794 package void rawEmplace(T)(void[] dst, ref T src)
795 {
796 	T[] tdst = () @trusted { return cast(T[])dst[0 .. T.sizeof]; } ();
797 	static if (is(T == class)) {
798 		tdst[0] = src;
799 	} else {
800 		import std.conv : emplace;
801 		emplace!T(&tdst[0]);
802 		rawSwap(tdst[0], src);
803 	}
804 }
805 
806 // std.algorithm.mutation.swap sometimes fails to compile due to
807 // internal errors in hasElaborateAssign!T/isAssignable!T. This is probably
808 // caused by cyclic dependencies. However, there is no reason to do these
809 // checks in this context, so we just directly move the raw memory.
810 package void rawSwap(T)(ref T a, ref T b)
811 @trusted {
812 	void[T.sizeof] tmp = void;
813 	void[] ab = (cast(void*)&a)[0 .. T.sizeof];
814 	void[] bb = (cast(void*)&b)[0 .. T.sizeof];
815 	tmp[] = ab[];
816 	ab[] = bb[];
817 	bb[] = tmp[];
818 }