nxt.mangling source code

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