nxt.mangling source code

1 /** ELF Symbol Name (De)Mangling.
2 	Copyright: Per Nordlöw 2022-.
3 	License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
4 	Authors: $(WEB Per Nordlöw)
5 	See_Also: https://mentorembedded.github.io/cxx-abi/abi.html
6 
7 	TODO: Only check for emptyness before any optionals.
8 
9 	TODO: Search for pattern "X> <Y" and assure that they all use
10 	return r.tryEvery(X, Y).
11 
12 	TODO: 1. Replace calls to decode ~ decode with separate decodes
13 	TODO: 2 : Replace calls to decode ~ decode with a sequence call.
14 
15 	TODO: Detect recursion:
16 		  See: http://forum.dlang.org/thread/edaduxaxmihvzkoudeqa@forum.dlang.org#post-edaduxaxmihvzkoudeqa:40forum.dlang.org
17 		  See: http://code.dlang.org/packages/backtrace-d
18 
19 	TODO: What role does _ZL have? See localFlag for details.
20  */
21 module nxt.mangling;
22 
23 // version = show;
24 
25 import std.range.primitives: empty, front, popFront, moveFront, popFrontExactly, isInputRange;
26 import std.algorithm: joiner, min;
27 import std.conv: to;
28 import std.ascii: isDigit;
29 
30 import std.algorithm.comparison : either;
31 import nxt.algorithm.searching : startsWith, skipOver;
32 import nxt.algorithm_ex: tryEvery, split, splitBefore;
33 
34 @safe:
35 
36 /** C++ Demangler. */
37 extern(C++) class Demangler(R) if (isInputRange!R) {
38 extern(D):
39 	this(R r,
40 		 bool explicitVoidParameter = false,
41 		 bool show = false)
42 	{
43 		this.r = r;
44 		this.explicitVoidParameter = explicitVoidParameter;
45 		this.show = show;
46 	}
47 	R r;
48 	bool show = false;
49 	bool explicitVoidParameter = false; // set to true make void parameters explicit
50 private:
51 	string[] sourceNames;
52 	CxxType[] ids; // ids demangled so far
53 	R scopeSeparator = "::";
54 }
55 auto demangler(T...)(T args) if (isInputRange!(T[0])) => new Demangler!(T[0])(args);
56 
57 /** Like $(D skipOver) but return $(D string) instead of $(D bool).
58 	Bool-conversion of returned value gives same result as r.skipOver(lit).
59 */
60 string skipLiteral(R, E)(Demangler!R x, E lit) if (isInputRange!R) => x.r.skipOver(lit) ? "" : null;
61 
62 /** Decode Unqualified C++ Type at $(D r).
63 	See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangling-type
64 */
65 R decodeCxxUnqualifiedType(R)(Demangler!R x) if (isInputRange!R)
66 {
67 	return either(x.decodeCxxBuiltinType(),
68 				  x.decodeCxxSubstitution(),
69 				  x.decodeCxxFunctionType());
70 }
71 
72 struct CxxType
73 {
74 	string typeName;
75 	bool isRef = false;	  // & <ref-qualifier>
76 	bool isRvalueRef = false;	// && ref-qualifier (C++11)
77 	bool isComplexPair = false;	// complex pair (C 2000)
78 	bool isImaginary = false;	// imaginary (C 2000)
79 	byte pointyness = 0;		   // pointer level
80 	CXXCVQualifiers cvQ;
81 
82 	void toString(Sink)(ref scope Sink sink) const
83 	{
84 		if (cvQ.isVolatile) { sink("volatile "); }
85 		if (cvQ.isRestrict) { sink("restrict "); }
86 
87 		sink(typeName);
88 
89 		if (cvQ.isConst) { sink(" const"); }
90 
91 		// suffix qualifiers
92 		foreach (immutable _; 0 .. pointyness)
93 		{
94 			sink(`*`);// str ~= "*".replicate(pointyness);
95 		}
96 		if (isRef) { sink(`&`); }
97 		if (isRvalueRef) { sink(`&&`); }
98 	}
99 }
100 
101 /** Decode C++ Type at $(D r).
102 	See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangling-type
103 */
104 R decodeCxxType(R)(Demangler!R x)
105 if (isInputRange!R)
106 {
107 
108 	const packExpansion = x.r.skipOver(`Dp`); // (C++11)
109 
110 	CxxType cxxType;
111 
112 	while (!x.r.empty)
113 	{
114 		if (const cvQ_ = x.r.decodeCxxCVQualifiers()) /+ TODO: Optimize +/
115 		{
116 			cxxType.cvQ.isRestrict |= cvQ_.isRestrict;
117 			cxxType.cvQ.isVolatile |= cvQ_.isVolatile;
118 			cxxType.cvQ.isConst |= cvQ_.isConst;
119 			continue;
120 		}
121 		else
122 		{
123 			auto miss = false;
124 			switch (x.r[0])
125 			{
126 				case 'P': x.r.popFront(); cxxType.pointyness++; break;
127 					// <ref-qualifier>: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.ref-qualifier
128 				case 'R': x.r.popFront(); cxxType.isRef = true; break;
129 				case 'O': x.r.popFront(); cxxType.isRvalueRef = true; break;
130  				case 'C': x.r.popFront(); cxxType.isComplexPair = true; assert(0, "TODO: Handle complex pair (C 2000)"); break;
131 				case 'G': x.r.popFront(); cxxType.isImaginary = true; assert(0, "TODO: Handle imaginary (C 2000)"); break;
132 				case 'U': x.r.popFront();
133 					const sourceName = x.decodeCxxSourceName();
134 					cxxType.typeName = sourceName ~ x.decodeCxxType();
135 					// "TODO: Handle vendor extended type qualifier <source-name>", x.r
136 					break;
137 				default: miss = true; break;
138 			}
139 			if (miss)
140 			{
141 				break;
142 			}
143 		}
144 	}
145 	assert(!(cxxType.isRef && cxxType.isRvalueRef));
146 
147 	if (x.r.empty) { return cxxType.to!string; }
148 
149 	cxxType.typeName = either(x.decodeCxxBuiltinType(),
150 							  x.decodeCxxFunctionType(),
151 							  x.decodeCxxClassEnumType(),
152 							  x.decodeCxxArrayType(),
153 							  x.decodeCxxPointerToMemberType(),
154 							  x.decodeCxxTemplateTemplateParamAndArgs(),
155 							  x.decodeCxxDecltype(),
156 							  x.decodeCxxSubstitution());
157 
158 	x.ids ~= cxxType;
159 
160 	return cxxType.to!string;
161 }
162 
163 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.class-enum-type */
164 R decodeCxxClassEnumType(R)(Demangler!R x)
165 if (isInputRange!R)
166 {
167 	R type;
168 	R prefix;
169 	enum n = 2;
170 	if (x.r.length >= n)
171 	{
172 		switch (x.r[0..n])
173 		{
174 			case `Ts`: prefix = `struct `; break;
175 			case `Tu`: prefix = `union `; break;
176 			case `Te`: prefix = `enum `; break;
177 			default: break;
178 		}
179 		if (prefix)
180 		{
181 			x.r.popFrontExactly(n);
182 		}
183 	}
184 	const name = x.decodeCxxName();
185 	if (name)
186 	{
187 		type = prefix ~ name;
188 	}
189 	else
190 	{
191 		assert(!prefix); // if we failed to decode name prefix should not have existed either
192 	}
193 	return type;
194 }
195 
196 R decodeCxxExpression(R)(Demangler!R x)
197 if (isInputRange!R)
198 {
199 	R exp;
200 	assert(0, "TODO");
201 }
202 
203 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.array-type */
204 R decodeCxxArrayType(R)(Demangler!R x)
205 if (isInputRange!R)
206 {
207 	R type;
208 	if (x.r.skipOver('A'))
209 	{
210 		if (const num = x.decodeCxxNumber())
211 		{
212 			assert(x.r.skipOver('_'));
213 			type = x.decodeCxxType() ~ `[]` ~ num ~ `[]`;
214 		}
215 		else
216 		{
217 			const dimensionExpression = x.decodeCxxExpression();
218 			assert(x.r.skipOver('_'));
219 			type = x.decodeCxxType() ~ `[]` ~ dimensionExpression ~ `[]`;
220 		}
221 	}
222 	return type;
223 }
224 
225 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.pointer-to-member-type */
226 R decodeCxxPointerToMemberType(R)(Demangler!R x)
227 if (isInputRange!R)
228 {
229 	R type;
230 	if (x.r.skipOver('M'))
231 	{
232 		const classType = x.decodeCxxType(); // <class type>
233 		const memberType = x.decodeCxxType(); // <mmeber type>
234 		type = classType ~ memberType;
235 	}
236 	return type;
237 }
238 
239 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.template-param */
240 R decodeCxxTemplateParam(R)(Demangler!R x)
241 if (isInputRange!R)
242 {
243 	R param;
244 	if (x.r.skipOver('T'))
245 	{
246 		if (x.r.skipOver('_'))
247 		{
248 			param = `first template parameter`;
249 		}
250 		else
251 		{
252 			param = x.decodeCxxNumber();
253 			assert(x.r.skipOver('_'));
254 		}
255 	}
256 	return param;
257 }
258 
259 R decodeCxxTemplateTemplateParamAndArgs(R)(Demangler!R x)
260 if (isInputRange!R)
261 {
262 	R value;
263 	if (const param = either(x.decodeCxxTemplateParam(),
264 							 x.decodeCxxSubstitution()))
265 	{
266 		auto args = x.decodeCxxTemplateArgs();
267 		value = param ~ args.joiner(`, `).to!R;
268 	}
269 	return value;
270 }
271 
272 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.decltype */
273 R decodeCxxDecltype(R)(Demangler!R x)
274 if (isInputRange!R)
275 {
276 	R type;
277 	if (x.r.skipOver(`Dt`) ||
278 		x.r.skipOver(`DT`))
279 	{
280 		type = x.decodeCxxExpression();
281 		assert(x.r.skipOver('E'));
282 	}
283 	return type;
284 }
285 
286 R decodeCxxDigit(R)(Demangler!R x)
287 if (isInputRange!R)
288 {
289 	auto digit = x.r[0..1];
290 	x.r.popFront();
291 	return digit;
292 }
293 
294 /** Try to Decode C++ Operator at $(D r).
295 	See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangling-operator
296 */
297 R decodeCxxOperatorName(R)(Demangler!R x)
298 if (isInputRange!R)
299 {
300 
301 	if (x.r.skipOver('v'))	 // vendor extended operator
302 	{
303 		const digit = x.decodeCxxDigit();
304 		const sourceName = x.decodeCxxSourceName();
305 		return digit ~ sourceName;
306 	}
307 
308 	R op;
309 	enum n = 2;
310 	if (x.r.length < n) { return typeof(return).init; }
311 	const code = x.r[0..n];
312 	switch (code)
313 	{
314 		case `nw`: op = `operator new`; break;
315 		case `na`: op = `operator new[]`; break;
316 		case `dl`: op = `operator delete`; break;
317 		case `da`: op = `operator delete[]`; break;
318 		case `ps`: op = `operator+`; break; // unary plus
319 		case `ng`: op = `operator-`; break; // unary minus
320 
321 		case `ad`: op = `operator&`; break; // address of
322 		case `de`: op = `operator*`; break; // dereference
323 
324 		case `co`: op = `operator~`; break; // bitwise complement
325 		case `pl`: op = `operator+`; break; // plus
326 		case `mi`: op = `operator-`; break; // minus
327 
328 		case `ml`: op = `operator*`; break; // multiplication
329 		case `dv`: op = `operator/`; break; // division
330 		case `rm`: op = `operator%`; break; // remainder
331 
332 		case `an`: op = `operator&`; break; // bitwise and
333 		case `or`: op = `operator|`; break; // bitwise of
334 
335 		case `eo`: op = `operator^`; break;
336 		case `aS`: op = `operator=`; break;
337 
338 		case `pL`: op = `operator+=`; break;
339 		case `mI`: op = `operator-=`; break;
340 		case `mL`: op = `operator*=`; break;
341 		case `dV`: op = `operator/=`; break;
342 		case `rM`: op = `operator%=`; break;
343 
344 		case `aN`: op = `operator&=`; break;
345 		case `oR`: op = `operator|=`; break;
346 		case `eO`: op = `operator^=`; break;
347 
348 		case `ls`: op = `operator<<`; break;
349 		case `rs`: op = `operator>>`; break;
350 		case `lS`: op = `operator<<=`; break;
351 		case `rS`: op = `operator>>=`; break;
352 
353 		case `eq`: op = `operator==`; break;
354 		case `ne`: op = `operator!=`; break;
355 		case `lt`: op = `operator<`; break;
356 		case `gt`: op = `operator>`; break;
357 		case `le`: op = `operator<=`; break;
358 		case `ge`: op = `operator>=`; break;
359 
360 		case `nt`: op = `operator!`; break;
361 		case `aa`: op = `operator&&`; break;
362 		case `oo`: op = `operator||`; break;
363 
364 		case `pp`: op = `operator++`; break; // (postfix in <expression> context)
365 		case `mm`: op = `operator--`; break; // (postfix in <expression> context)
366 
367 		case `cm`: op = `operator,`; break;
368 
369 		case `pm`: op = `operator->*`; break;
370 		case `pt`: op = `operator->`; break;
371 
372 		case `cl`: op = `operator()`; break;
373 		case `ix`: op = `operator[]`; break;
374 		case `qu`: op = `operator?`; break;
375 		case `cv`: op = `(cast)`; break;
376 		case `li`: op = `operator""`; break;
377 		default: break;
378 	}
379 
380 	if (op)
381 	{
382 		x.r.popFrontExactly(n); // digest it
383 	}
384 
385 	switch (code)
386 	{
387 		case `cv`: op = '(' ~ x.decodeCxxType() ~ ')'; break;
388 		case `li`: op = (`operator ""` ~ x.decodeCxxSourceName()); break;
389 		default: break;
390 	}
391 
392 	return op;
393 }
394 
395 /** Try to Decode C++ Builtin Type at $(D r).
396 	See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.builtin-type
397 */
398 R decodeCxxBuiltinType(R)(Demangler!R x)
399 if (isInputRange!R)
400 {
401 	R type;
402 	enum n = 1;
403 	if (x.r.length < n) { return type; }
404 	switch (x.r[0])
405 	{
406 		case 'v': x.r.popFront(); type = `void`; break;
407 		case 'w': x.r.popFront(); type = `wchar_t`; break;
408 
409 		case 'b': x.r.popFront(); type = `bool`; break;
410 
411 		case 'c': x.r.popFront(); type = `char`; break;
412 		case 'a': x.r.popFront(); type = `signed char`; break;
413 		case 'h': x.r.popFront(); type = `unsigned char`; break;
414 
415 		case 's': x.r.popFront(); type = `short`; break;
416 		case 't': x.r.popFront(); type = `unsigned short`; break;
417 
418 		case 'i': x.r.popFront(); type = `int`; break;
419 		case 'j': x.r.popFront(); type = `unsigned int`; break;
420 
421 		case 'l': x.r.popFront(); type = `long`; break;
422 		case 'm': x.r.popFront(); type = `unsigned long`; break;
423 
424 		case 'x': x.r.popFront(); type = `long long`; break;  // __int64
425 		case 'y': x.r.popFront(); type = `unsigned long long`; break; // __int64
426 
427 		case 'n': x.r.popFront(); type = `__int128`; break;
428 		case 'o': x.r.popFront(); type = `unsigned __int128`; break;
429 
430 		case 'f': x.r.popFront(); type = `float`; break;
431 		case 'd': x.r.popFront(); type = `double`; break;
432 		case 'e': x.r.popFront(); type = `long double`; break; // __float80
433 		case 'g': x.r.popFront(); type = `__float128`; break;
434 
435 		case 'z': x.r.popFront(); type = `...`; break; // ellipsis
436 
437 		case 'D':
438 			x.r.popFront();
439 			assert(!x.r.empty); // need one more
440 			switch (x.r[0])
441 			{
442 				case 'd': x.r.popFront(); type = `IEEE 754r decimal floating point (64 bits)`; break;
443 				case 'e': x.r.popFront(); type = `IEEE 754r decimal floating point (128 bits)`; break;
444 				case 'f': x.r.popFront(); type = `IEEE 754r decimal floating point (32 bits)`; break;
445 				case 'h': x.r.popFront(); type = `IEEE 754r half-precision floating point (16 bits)`; break;
446 				case 'i': x.r.popFront(); type = `char32_t`; break;
447 				case 's': x.r.popFront(); type = `char16_t`; break;
448 				case 'a': x.r.popFront(); type = `auto`; break;
449 				case 'c': x.r.popFront(); type = `decltype(auto)`; break;
450 				case 'n': x.r.popFront(); type = `std::nullptr_t`; break; // (i.e., decltype(nullptr))
451 				default: assert(0, `TODO: Handle `);
452 			}
453 			break;
454 
455 			/* TODO: */
456 			/* ::= u <source-name>	# vendor extended type */
457 
458 		default:
459 			break;
460 	}
461 
462 	return type;
463 }
464 
465 /** Decode C++ Substitution Type at $(D r).
466 	See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.substitution
467 */
468 R decodeCxxSubstitution(R)(Demangler!R x, R stdPrefix = `::std::`)
469 if (isInputRange!R)
470 {
471 	R type;
472 	if (x.r.skipOver('S'))
473 	{
474 		if (x.r.front == '_') // See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.seq-id
475 		{
476 			type = x.ids[0].to!R;
477 			x.r.popFront();
478 		}
479 		else if ('0' <= x.r.front && x.r.front <= '9') // See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.seq-id
480 		{
481 			const ix = (x.r.front - '0');
482 			auto ids_ = x.ids[min(x.ids.length - 1, ix + 1)]; /+ TODO: Use of min here is hacky. Investigate. +/
483 			if (ix == 0)
484 			{
485 				/* NOTE: Undocumented: decrease pointyness.
486 				   See for example: parse_arch(size_t argc, const char** argv, const char* arch)
487 				   in dmd/src/mars.c
488 				*/
489 				ids_.pointyness = ids_.pointyness >= 1 ? cast(byte)(ids_.pointyness - 1): 0;
490 			}
491 			type = ids_.to!R;
492 			x.r.popFront();
493 			x.r.skipOver('_'); /+ TODO: Relaxed this to optional by removing surrounding assert. Investigate. +/
494 		}
495 		else if ('A' <= x.r.front && x.r.front <= 'Z') // See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.seq-id
496 		{
497 			const ix = (x.r.front - 'A' + 11);
498 			type = x.ids[ix].to!R;
499 			x.r.popFront();
500 			assert(x.r.skipOver('_'));
501 		}
502 		else
503 		{
504 			type = stdPrefix;
505 			switch (x.r.front)
506 			{
507 				case 't': x.r.popFront(); type ~= `ostream`; break;
508 				case 'a': x.r.popFront(); type ~= `allocator`; break;
509 				case 'b': x.r.popFront(); type ~= `basic_string`; break;
510 				case 's': x.r.popFront(); type ~= `basic_string<char, std::char_traits<char>, std::allocator<char> >`; break;
511 				case 'i': x.r.popFront(); type ~= `istream`; break;
512 				case 'o': x.r.popFront(); type ~= `ostream`; break;
513 				case 'd': x.r.popFront(); type ~= `iostream`; break;
514 
515 				default:
516 					assert(0, `Cannot handle C++ standard prefix character`);
517 					x.r.popFront();
518 					break;
519 			}
520 		}
521 	}
522 	return type;
523 }
524 
525 /** Try to Decode C++ Function Type at $(D r).
526 	See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.function-type
527 */
528 R decodeCxxFunctionType(R)(Demangler!R x)
529 if (isInputRange!R) {
530 	auto restLookAhead = x.r; // needed for lookahead parsing of CV-qualifiers
531 	const cvQ = restLookAhead.decodeCxxCVQualifiers();
532 	R type;
533 	if (restLookAhead.skipOver('F')) {
534 		x.r = restLookAhead; // we have found it
535 		x.r.skipOver('Y'); // optional
536 		type = x.decodeCxxBareFunctionType().to!R;
537 		const refQ = x.decodeCxxRefQualifier();
538 		type ~= refQ.toCxxString;
539 
540 	}
541 	return type;
542 }
543 
544 struct CxxBareFunctionType(R)
545 if (isInputRange!R) {
546 	R[] types; // optional return and parameter types
547 	bool explicitVoidParameter = false; // set to true make void parameters explicit
548 	R toString() pure {				/+ TODO: use sink +/
549 		R value;
550 		if (!types.empty) {
551 			value ~= `(`;
552 			if (this.explicitVoidParameter ||
553 				!(types.length == 1 && types.front == "void")) {
554 				value ~= types.joiner(`, `).to!R;
555 			}
556 			value ~= `)`;
557 		}
558 		return value;
559 	}
560 }
561 
562 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.bare-function-type */
563 CxxBareFunctionType!R decodeCxxBareFunctionType(R)(Demangler!R x)
564 if (isInputRange!R) {
565 	typeof(return) bareFunctionType;
566 	bareFunctionType.explicitVoidParameter = x.explicitVoidParameter;
567 
568 	/* TODO: This behaviour may not follow grammar. */
569 	if (const firstType = x.decodeCxxType()) {
570 		bareFunctionType.types ~= firstType;
571 	}
572 
573 	while (!x.r.empty) {
574 		auto type = x.decodeCxxType();
575 		if (type)
576 			bareFunctionType.types ~= type;
577 		else
578 			break;
579 	}
580 
581 	return bareFunctionType;
582 }
583 
584 struct CXXCVQualifiers
585 {
586 	bool isRestrict; // (C99)
587 	bool isVolatile; // volatile
588 	bool isConst; // const
589 	auto opCast(T : bool)() pure nothrow const
590 		=> (isRestrict ||
591 			isVolatile ||
592 			isConst);
593 	void toString(Sink)(ref scope Sink sink) const {
594 		if (isRestrict) sink(`restrict `);
595 		if (isVolatile) sink(`volatile `);
596 		if (isConst)	sink(`const `);
597 	}
598 }
599 
600 /** Decode <CV-qualifiers>
601 	See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.CV-qualifiers
602 */
603 CXXCVQualifiers decodeCxxCVQualifiers(R)(ref R r)
604 if (isInputRange!R) {
605 	typeof(return) cvQ;
606 	if (r.skipOver('r')) { cvQ.isRestrict = true; }
607 	if (r.skipOver('V')) { cvQ.isVolatile = true; }
608 	if (r.skipOver('K')) { cvQ.isConst	= true; }
609 	return cvQ;
610 }
611 
612 enum CxxRefQualifier {
613 	none,
614 	normalRef,
615 	rvalueRef
616 }
617 
618 /* See_Also: http://forum.dlang.org/thread/cvhapzsrhjdnpkdspavg@forum.dlang.org#post-cvhapzsrhjdnpkdspavg:40forum.dlang.org */
619 string toCxxString(CxxRefQualifier refQ) pure nothrow {
620 	final switch (refQ) {
621 		case CxxRefQualifier.none: return "";
622 		case CxxRefQualifier.normalRef: return "&";
623 		case CxxRefQualifier.rvalueRef: return "&&";
624 	}
625 }
626 
627 /** Decode <ref-qualifier>
628 	See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.ref-qualifier
629 */
630 CxxRefQualifier decodeCxxRefQualifier(R)(Demangler!R x)
631 if (isInputRange!R) {
632 	if (x.r.skipOver('R'))
633 		return CxxRefQualifier.normalRef;
634 	else if (x.r.skipOver('O'))
635 		return CxxRefQualifier.rvalueRef;
636 	else
637 		return CxxRefQualifier.none;
638 }
639 
640 /** Decode Identifier <source-name>.
641 	See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.source-name
642 */
643 R decodeCxxSourceName(R)(Demangler!R x)
644 if (isInputRange!R) {
645 	R id;
646 	const sign = x.r.skipOver('n'); // if negative number
647 	assert(!sign);
648 	const match = x.r.splitBefore!(a => !a.isDigit);
649 	const digits = match[0];
650 	x.r = match[1];
651 	if (!digits.empty) { // digit prefix
652 		/+ TODO: Functionize these three lines +/
653 		const num = digits.to!uint;
654 		id = x.r[0..num]; // identifier, x.r.take(num)
655 		x.r = x.r[num..$]; // x.r.drop(num);
656 		x.sourceNames ~= id;
657 	}
658 	return id;
659 }
660 
661 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.nested-name
662    Note: Second alternative
663    <template-prefix> <template-args>
664    in
665    <nested-name>
666    is redundant as it is included in <prefix> and is skipped here.
667  */
668 R decodeCxxNestedName(R)(Demangler!R x)
669 if (isInputRange!R) {
670 	if (x.r.skipOver('N')) // nested name: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.nested-name
671 	{
672 		const cvQ = x.r.decodeCxxCVQualifiers();
673 		const refQ = x.decodeCxxRefQualifier();
674 		const prefix = x.decodeCxxPrefix();
675 		const name = x.decodeCxxUnqualifiedName();
676 		assert(x.r.skipOver('E'));
677 		auto ret = (cvQ.to!R ~
678 					prefix ~
679 					name ~
680 					refQ.toCxxString);
681 		return ret;
682 	}
683 	return null;
684 }
685 
686 /** TODO: Use this
687 	See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.ctor-dtor-name
688  */
689 enum CtorDtorName
690 {
691 	completeObjectConstructor,
692 	baseObjectConstructor,
693 	completeObjectAllocatingConstructor,
694 	deletingDestructor,
695 	completeObjectDestructor,
696 	baseObjectDestructor
697 }
698 
699 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.ctor-dtor-name */
700 R decodeCxxCtorDtorName(R)(Demangler!R x)
701 if (isInputRange!R) {
702 	R name;
703 	enum n = 2;
704 	if (x.r.length < n) { return typeof(return).init; }
705 	import std.array: back;
706 	switch (x.r[0..n]) {
707 		case `C1`: name = x.sourceNames.back; break; // complete object constructor
708 		case `C2`: name = x.sourceNames.back; break; // base object constructor
709 		case `C3`: name = x.sourceNames.back; break; // complete object allocating constructor
710 		case `D0`: name = '~' ~ x.sourceNames.back; break; // deleting destructor
711 		case `D1`: name = '~' ~ x.sourceNames.back; break; // complete object destructor
712 		case `D2`: name = '~' ~ x.sourceNames.back; break; // base object destructor
713 		default: break;
714 	}
715 	if (name)
716 		x.r.popFrontExactly(n);
717 	return name;
718 }
719 
720 /** https://mentorembedded.github.io/cxx-abi/abi.html#mangle.unqualified-name */
721 R decodeCxxUnqualifiedName(R)(Demangler!R x)
722 if (isInputRange!R) {
723 	return either(x.decodeCxxOperatorName(),
724 				  x.decodeCxxSourceName(),
725 				  x.decodeCxxCtorDtorName(),
726 				  x.decodeCxxUnnamedTypeName());
727 }
728 
729 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.unnamed-type-name */
730 R decodeCxxUnnamedTypeName(R)(Demangler!R x)
731 if (isInputRange!R) {
732 	R type;
733 	if (x.r.skipOver(`Ut`)) {
734 		type = x.decodeCxxNumber();
735 		assert(x.r.skipOver('_'));
736 	}
737 	return type;
738 }
739 
740 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.template-prefix
741  */
742 R decodeCxxTemplatePrefix(R)(Demangler!R x)
743 if (isInputRange!R) {
744 	// NOTE: Removed <prefix> because of recursion
745 	return either(x.decodeCxxUnqualifiedName(),
746 				  x.decodeCxxTemplateParam(),
747 				  x.decodeCxxSubstitution());
748 }
749 
750 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.template-args */
751 R[] decodeCxxTemplateArgs(R)(Demangler!R x)
752 if (isInputRange!R) {
753 	typeof(return) args;
754 	if (x.r.skipOver('I')) {
755 		args ~= x.decodeCxxTemplateArg();
756 		while (!x.r.empty) {
757 			auto arg = x.decodeCxxTemplateArg();
758 			if (arg)
759 				args ~= arg;
760 			else
761 				break;
762 		}
763 		assert(x.r.skipOver('E'));
764 	}
765 	return args;
766 }
767 
768 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.mangled-name */
769 R decodeCxxMangledName(R)(Demangler!R x)
770 if (isInputRange!R) {
771 	R name;
772 	if (x.r.skipOver(`_Z`))
773 		return x.decodeCxxEncoding();
774 	return name;
775 }
776 
777 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.expr-primary */
778 R decodeCxxExprPrimary(R)(Demangler!R x)
779 if (isInputRange!R) {
780 	R expr;
781 	if (x.r.skipOver('L')) {
782 		expr = x.decodeCxxMangledName();
783 		if (!expr) {
784 			auto number = x.decodeCxxNumber();
785 			/+ TODO: Howto demangle <float>? +/
786 			/+ TODO: Howto demangle <float> _ <float> E +/
787 			expr = x.decodeCxxType(); // <R>, <nullptr>, <pointer> type
788 			bool pointerType = x.r.skipOver('0'); // null pointer template argument
789 		}
790 		assert(x.r.skipOver('E'));
791 	}
792 	return expr;
793 }
794 
795 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.template-arg */
796 R decodeCxxTemplateArg(R)(Demangler!R x)
797 if (isInputRange!R)
798 {
799 	R arg;
800 	if (x.r.skipOver('X')) {
801 		arg = x.decodeCxxExpression();
802 		assert(x.r.skipOver('E'));
803 	} else if (x.r.skipOver('J')) {
804 		R[] args;
805 		while (!x.r.empty) {
806 			const subArg = x.decodeCxxTemplateArg();
807 			if (subArg)
808 				args ~= subArg;
809 			else
810 				break;
811 		}
812 		arg = args.joiner(`, `).to!R;
813 		assert(x.r.skipOver('E'));
814 	}
815 	else
816 		arg = either(x.decodeCxxExprPrimary(),
817 					 x.decodeCxxType());
818 	return arg;
819 }
820 
821 R decodeCxxTemplatePrefixAndArgs(R)(Demangler!R x)
822 if (isInputRange!R) {
823 	auto restBackup = x.r;
824 	if (const prefix = x.decodeCxxTemplatePrefix()) {
825 		auto args = x.decodeCxxTemplateArgs();
826 		if (args)
827 			return prefix ~ args.joiner(`, `).to!R;
828 	}
829 	x.r = restBackup; // restore upon failure
830 	return typeof(return).init;
831 }
832 
833 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.prefix */
834 R decodeCxxPrefix(R)(Demangler!R x)
835 if (isInputRange!R) {
836 	typeof(return) prefix;
837 	for (size_t i = 0; !x.r.empty; ++i) { // NOTE: Turned self-recursion into iteration
838 		if (const name = x.decodeCxxUnqualifiedName()) {
839 			if (i >= 1)
840 				prefix ~= x.scopeSeparator;
841 			prefix ~= name;
842 			continue;
843 		} else if (const name = x.decodeCxxTemplatePrefixAndArgs()) {
844 			prefix ~= name;
845 			continue;
846 		} else if (const templateParam = x.decodeCxxTemplateParam()) {
847 			prefix ~= templateParam;
848 			continue;
849 		} else if (const decltype = x.decodeCxxDecltype()) {
850 			prefix ~= decltype;
851 			continue;
852 		} else if (const subst = x.decodeCxxSubstitution()) {
853 			prefix ~= subst;
854 			continue;
855 		}
856 		else
857 			break;
858 	}
859 	return prefix;
860 }
861 
862 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.unscoped-name */
863 R decodeCxxUnscopedName(R)(Demangler!R x)
864 if (isInputRange!R) {
865 	auto restBackup = x.r;
866 	const prefix = x.r.skipOver(`St`) ? "::std::" : null;
867 	if (const name = x.decodeCxxUnqualifiedName())
868 		return prefix ~ name;
869 	else {
870 		x.r = restBackup; // restore
871 		return typeof(return).init;
872 	}
873 }
874 
875 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.unscoped-template-name */
876 R decodeCxxUnscopedTemplateName(R)(Demangler!R x)
877 if (isInputRange!R)
878 {
879 	return either(x.decodeCxxSubstitution(), // faster backtracking with substitution
880 				  x.decodeCxxUnscopedName());
881 }
882 
883 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.unscoped-template-name */
884 R decodeCxxUnscopedTemplateNameAndArgs(R)(Demangler!R x)
885 if (isInputRange!R) {
886 	R nameAndArgs;
887 	if (const name = x.decodeCxxUnscopedTemplateName()) {
888 		nameAndArgs = name;
889 		if (auto args = x.decodeCxxTemplateArgs())
890 			nameAndArgs ~= args.joiner(`, `).to!R;
891 	}
892 	return nameAndArgs;
893 }
894 
895 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.number */
896 R decodeCxxNumber(R)(Demangler!R x)
897 if (isInputRange!R) {
898 	R number;
899 	const prefix = x.r.skipOver('n'); // optional prefix
900 	auto split = x.r.splitBefore!(a => !a.isDigit());
901 	if (prefix || !split[0].empty) { // if complete match
902 		x.r = split[1];
903 		number = split[0];
904 	}
905 	return number;
906 }
907 
908 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.discriminator */
909 R decodeCxxDescriminator(R)(Demangler!R x)
910 if (isInputRange!R) {
911 	R descriminator;
912 	if (x.r.skipOver('_')) {
913 		if (x.r.skipOver('_')) { // number >= 10
914 			descriminator = x.decodeCxxNumber();
915 			assert(x.r.skipOver('_')); // suffix
916 		} else {					// number < 10
917 			x.r.skipOver('n'); // optional prefix
918 			/* TODO: Merge these two into a variant of popFront() that returns
919 			 the popped element. What is best out of:
920 			 - General: x.r.takeOne().to!R
921 			 - Arrays only: r[0..1]
922 			 - Needs cast: x.r.front
923 			 and are we in need of a combined variant of front() and popFront()
924 			 say takeFront() that may fail and requires a cast.
925 			 */
926 			/* descriminator = r[0..1]; // single digit */
927 			/* x.r.popFront(); */
928 			descriminator = x.r.moveFront().to!R;
929 		}
930 	}
931 	return descriminator;
932 }
933 
934 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.local-name */
935 R decodeCxxLocalName(R)(Demangler!R x)
936 if (isInputRange!R) {
937 	if (x.r.skipOver('Z')) {
938 		const functionEncoding = x.decodeCxxEncoding();
939 		x.r.skipOver('E');
940 		if (x.r.skipOver('D'))
941 			assert(0, "TODO: Decode C++0x Closure Type (lambda)"); // see https://mentorembedded.github.io/cxx-abi/abi.html#closure-types
942 		else {
943 			const entityNameMaybe = either(x.skipLiteral('s'), // NOTE: Literal first to speed up
944 										   x.decodeCxxName());
945 			const discriminator = x.decodeCxxDescriminator(); // optional
946 			return (functionEncoding ~
947 					x.scopeSeparator ~
948 					entityNameMaybe ~
949 					discriminator.to!R); /+ TODO: Optional +/
950 		}
951 	}
952 	return R.init;
953 }
954 
955 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.name */
956 R decodeCxxName(R)(Demangler!R x)
957 if (isInputRange!R) {
958 	return either(x.decodeCxxNestedName(),
959 				  x.decodeCxxUnscopedName(),
960 				  x.decodeCxxLocalName(), /+ TODO: order flipped +/
961 				  x.decodeCxxUnscopedTemplateNameAndArgs()); // NOTE: order flipped
962 }
963 
964 R decodeCxxNVOffset(R)(Demangler!R x)
965 if (isInputRange!R) {
966 	return x.decodeCxxNumber();
967 }
968 
969 R decodeCxxVOffset(R)(Demangler!R x)
970 if (isInputRange!R) {
971 	auto offset = x.decodeCxxNumber();
972 	assert(x.r.skipOver('_'));
973 	return offset ~ x.decodeCxxNumber();
974 }
975 
976 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.call-offset */
977 R decodeCxxCallOffset(R)(Demangler!R x)
978 if (isInputRange!R) {
979 	typeof(return) offset;
980 	if (x.r.skipOver('h')) {
981 		offset = x.decodeCxxNVOffset();
982 		assert(x.r.skipOver('_'));
983 	} else if (x.r.skipOver('v')) {
984 		offset = x.decodeCxxVOffset();
985 		assert(x.r.skipOver('_'));
986 	}
987 	return offset;
988 }
989 
990 /** See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.special-name */
991 R decodeCxxSpecialName(R)(Demangler!R x)
992 if (isInputRange!R) {
993 	auto restBackup = x.r;
994 	typeof(return) name;
995 	if (x.r.skipOver('S')) {
996 		switch (x.r.moveFront) {
997 			case 'V': name = "virtual table: "; break;
998 			case 'T': name = "VTT structure: "; break;
999 			case 'I': name = "typeinfo structure: "; break;
1000 			case 'S': name = "typeinfo name (null-terminated byte R): "; break;
1001 			default:
1002 				x.r = restBackup; // restore
1003 				return name;
1004 		}
1005 		name ~= x.decodeCxxType();
1006 	}
1007 	else if (x.r.skipOver(`GV`))
1008 		name = x.decodeCxxName();
1009 	else if (x.r.skipOver('T')) {
1010 		if (x.r.skipOver('c'))
1011 			name = x.r.tryEvery(x.decodeCxxCallOffset(),
1012 								x.decodeCxxCallOffset(),
1013 								x.decodeCxxEncoding()).joiner(` `).to!R;
1014 		else
1015 			name = x.r.tryEvery(x.decodeCxxCallOffset(),
1016 								x.decodeCxxEncoding()).joiner(` `).to!R;
1017 	}
1018 	return name;
1019 }
1020 
1021 /* Decode C++ Symbol.
1022    See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.encoding
1023  */
1024 R decodeCxxEncoding(R)(Demangler!R x) /* pure nothrow @nogc */ if (isInputRange!R)
1025 {
1026 	const localFlag = x.r.skipOver('L'); /+ TODO: What role does the L have in symbols starting with _ZL have? +/
1027 	if (const name = x.decodeCxxSpecialName())
1028 		return name;
1029 	const name = x.decodeCxxName();
1030 	auto type = x.decodeCxxBareFunctionType();
1031 	return name ~ type.to!R;
1032 }
1033 
1034 /** Demangled Expression. */
1035 alias Expr = string;
1036 
1037 alias LanguageT = ubyte;
1038 
1039 /** Mangled language. */
1040 enum Language : LanguageT {
1041 	unknown, nullValue = unknown, // `HybridHashMap` null support
1042 	c,
1043 	d,
1044 	cxx,
1045 	holeValue = LanguageT.max,				  // `HybridHashMap` hole support
1046 }
1047 
1048 struct Demangling {
1049 	Language language;
1050 	Expr unmangled;
1051 	auto opCast(T : bool)() const scope pure nothrow @nogc => expr !is null;
1052 }
1053 
1054 /** Demangle Symbol $(D r) and Detect Language.
1055 	See_Also: https://en.wikipedia.org/wiki/Name_mangling
1056 	See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangling
1057 	See_Also: https://gcc.gnu.org/onlinedocs/libstdc++/manual/ext_demangling.html
1058 */
1059 Demangling decodeSymbol(R)(Demangler!R x) /* pure nothrow @nogc */
1060 if (isInputRange!R) {
1061 	if (x.r.empty)
1062 		return Demangling(Language.init, x.r);
1063 	if (!x.r.startsWith('_'))
1064 		return Demangling(Language.c, x.r); // assume C
1065 	// See_Also: https://mentorembedded.github.io/cxx-abi/abi.html#mangle.mangled-name
1066 	if (x.r.skipOver(`_Z`))
1067 		return Demangling(Language.cxx, x.decodeCxxEncoding());
1068 	else {
1069 		import core.demangle: demangle;
1070 		const symAsD = x.r.demangle;
1071 		import std.conv: to;
1072 		if (symAsD != x.r) /+ TODO: Why doesn't (symAsD is r) work here? +/
1073 			return Demangling(Language.d, symAsD.to!R);
1074 		else
1075 			return Demangling(Language.init, x.r);
1076 	}
1077 }
1078 
1079 @trusted unittest {
1080 	import nxt.assert_ex;
1081 
1082 	assertEqual(demangler(`memcpy`).decodeSymbol(),
1083 				Demangling(Language.c, `memcpy`));
1084 
1085 	assertEqual(demangler(`memcpy`).decodeSymbol(),
1086 				Demangling(Language.c, `memcpy`));
1087 
1088 	assertEqual(demangler(`_Z1hi`).decodeSymbol(),
1089 				Demangling(Language.cxx, `h(int)`));
1090 
1091 	assertEqual(demangler(`_Z3foo3bar`).decodeSymbol(),
1092 				Demangling(Language.cxx, `foo(bar)`));
1093 
1094 	assertEqual(demangler(`_ZN1N1fE`).decodeSymbol(),
1095 				Demangling(Language.cxx, `N::f`));
1096 
1097 	assertEqual(demangler(`_ZN3Foo3BarEv`).decodeSymbol(),
1098 				Demangling(Language.cxx, `Foo::Bar()`));
1099 
1100 	assertEqual(demangler(`_ZN3FooC1Ev`).decodeSymbol(),
1101 				Demangling(Language.cxx, `Foo::Foo()`));
1102 
1103 	assertEqual(demangler(`_ZN9wikipedia7article6formatE`).decodeSymbol(),
1104 				Demangling(Language.cxx, `wikipedia::article::format`));
1105 
1106 	assertEqual(demangler(`_ZSt5state`).decodeSymbol(),
1107 				Demangling(Language.cxx, `::std::state`));
1108 
1109 	assertEqual(demangler(`_ZN9wikipedia7article8print_toERSo`).decodeSymbol(),
1110 				Demangling(Language.cxx, `wikipedia::article::print_to(::std::ostream&)`));
1111 
1112 	assertEqual(demangler(`_ZN9wikipedia7article8print_toEOSo`).decodeSymbol(),
1113 				Demangling(Language.cxx, `wikipedia::article::print_to(::std::ostream&&)`));
1114 
1115 	assertEqual(demangler(`_ZN9wikipedia7article6formatEv`, true).decodeSymbol(),
1116 				Demangling(Language.cxx, `wikipedia::article::format(void)`));
1117 
1118 	assertEqual(demangler(`_ZN9wikipedia7article6formatEv`, false).decodeSymbol(),
1119 				Demangling(Language.cxx, `wikipedia::article::format()`));
1120 
1121 	assertEqual(demangler(`_ZL8next_argRPPc`).decodeSymbol(),
1122 				Demangling(Language.cxx, `next_arg(char**&)`));
1123 
1124 	assertEqual(demangler(`_ZL10parse_archmPPKcS0_`, true).decodeSymbol(),
1125 				Demangling(Language.cxx, `parse_arch(unsigned long, char const**, char const*)`));
1126 
1127 	assertEqual(demangler(`_ZN5LexerC2EP6ModulePKhmmii`, true).decodeSymbol(),
1128 				Demangling(Language.cxx, `Lexer::Lexer(Module*, unsigned char const*, unsigned long, unsigned long, int, int)`));
1129 
1130 	assertEqual(demangler(`_Zrm1XS_`).decodeSymbol(),
1131 				Demangling(Language.cxx, `operator%(X, X)`));
1132 
1133 	assertEqual(demangler(`_ZZL8next_argRPPcE4keys`).decodeSymbol(),
1134 				Demangling(Language.cxx, `next_arg(char**&)::keys`));
1135 
1136 	assertEqual(demangler(`_ZN12ExpStatement9scopeCodeEP5ScopePP9StatementS4_S4`).decodeSymbol(),
1137 				Demangling(Language.cxx, `ExpStatement::scopeCode(Scope*, Statement**, Statement**, Statement**)`));
1138 
1139 	assertEqual(demangler(`_ZZ8genCmainP5ScopeE9cmaincode`).decodeSymbol(),
1140 				Demangling(Language.cxx, `genCmain(Scope*)::cmaincode`));
1141 
1142 	assertEqual(demangler("_Z7DtoLValP6DValue").decodeSymbol(),
1143 				Demangling(Language.cxx, `DtoLVal(DValue*)`));
1144 }