1//===--- DLangDemangle.cpp ------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file defines a demangler for the D programming language as specified
11/// in the ABI specification, available at:
12/// https://dlang.org/spec/abi.html#name_mangling
13///
14//===----------------------------------------------------------------------===//
15
16#include "llvm/Demangle/Demangle.h"
17#include "llvm/Demangle/StringViewExtras.h"
18#include "llvm/Demangle/Utility.h"
19
20#include <cctype>
21#include <cstring>
22#include <limits>
23#include <string_view>
24
25using namespace llvm;
26using llvm::itanium_demangle::OutputBuffer;
27using llvm::itanium_demangle::starts_with;
28
29namespace {
30
31/// Demangle information structure.
32struct Demangler {
33 /// Initialize the information structure we use to pass around information.
34 ///
35 /// \param Mangled String to demangle.
36 Demangler(std::string_view Mangled);
37
38 /// Extract and demangle the mangled symbol and append it to the output
39 /// string.
40 ///
41 /// \param Demangled Output buffer to write the demangled name.
42 ///
43 /// \return The remaining string on success or nullptr on failure.
44 ///
45 /// \see https://dlang.org/spec/abi.html#name_mangling .
46 /// \see https://dlang.org/spec/abi.html#MangledName .
47 const char *parseMangle(OutputBuffer *Demangled);
48
49private:
50 /// Extract and demangle a given mangled symbol and append it to the output
51 /// string.
52 ///
53 /// \param Demangled output buffer to write the demangled name.
54 /// \param Mangled mangled symbol to be demangled.
55 ///
56 /// \see https://dlang.org/spec/abi.html#name_mangling .
57 /// \see https://dlang.org/spec/abi.html#MangledName .
58 void parseMangle(OutputBuffer *Demangled, std::string_view &Mangled);
59
60 /// Extract the number from a given string.
61 ///
62 /// \param Mangled string to extract the number.
63 /// \param Ret assigned result value.
64 ///
65 /// \note Ret larger than UINT_MAX is considered a failure.
66 ///
67 /// \see https://dlang.org/spec/abi.html#Number .
68 void decodeNumber(std::string_view &Mangled, unsigned long &Ret);
69
70 /// Extract the back reference position from a given string.
71 ///
72 /// \param Mangled string to extract the back reference position.
73 /// \param Ret assigned result value.
74 ///
75 /// \return true on success, false on error.
76 ///
77 /// \note Ret is always >= 0 on success, and unspecified on failure
78 ///
79 /// \see https://dlang.org/spec/abi.html#back_ref .
80 /// \see https://dlang.org/spec/abi.html#NumberBackRef .
81 bool decodeBackrefPos(std::string_view &Mangled, long &Ret);
82
83 /// Extract the symbol pointed by the back reference form a given string.
84 ///
85 /// \param Mangled string to extract the back reference position.
86 /// \param Ret assigned result value.
87 ///
88 /// \return true on success, false on error.
89 ///
90 /// \see https://dlang.org/spec/abi.html#back_ref .
91 bool decodeBackref(std::string_view &Mangled, std::string_view &Ret);
92
93 /// Extract and demangle backreferenced symbol from a given mangled symbol
94 /// and append it to the output string.
95 ///
96 /// \param Demangled output buffer to write the demangled name.
97 /// \param Mangled mangled symbol to be demangled.
98 ///
99 /// \see https://dlang.org/spec/abi.html#back_ref .
100 /// \see https://dlang.org/spec/abi.html#IdentifierBackRef .
101 void parseSymbolBackref(OutputBuffer *Demangled, std::string_view &Mangled);
102
103 /// Extract and demangle backreferenced type from a given mangled symbol
104 /// and append it to the output string.
105 ///
106 /// \param Mangled mangled symbol to be demangled.
107 ///
108 /// \see https://dlang.org/spec/abi.html#back_ref .
109 /// \see https://dlang.org/spec/abi.html#TypeBackRef .
110 void parseTypeBackref(OutputBuffer *Demangled, std::string_view &Mangled);
111
112 /// Check whether it is the beginning of a symbol name.
113 ///
114 /// \param Mangled string to extract the symbol name.
115 ///
116 /// \return true on success, false otherwise.
117 ///
118 /// \see https://dlang.org/spec/abi.html#SymbolName .
119 bool isSymbolName(std::string_view Mangled);
120
121 /// Extract and demangle an identifier from a given mangled symbol append it
122 /// to the output string.
123 ///
124 /// \param Demangled Output buffer to write the demangled name.
125 /// \param Mangled Mangled symbol to be demangled.
126 ///
127 /// \see https://dlang.org/spec/abi.html#SymbolName .
128 void parseIdentifier(OutputBuffer *Demangled, std::string_view &Mangled);
129
130 /// Extract and demangle the plain identifier from a given mangled symbol and
131 /// prepend/append it to the output string, with a special treatment for some
132 /// magic compiler generated symbols.
133 ///
134 /// \param Demangled Output buffer to write the demangled name.
135 /// \param Mangled Mangled symbol to be demangled.
136 /// \param Len Length of the mangled symbol name.
137 ///
138 /// \see https://dlang.org/spec/abi.html#LName .
139 void parseLName(OutputBuffer *Demangled, std::string_view &Mangled,
140 unsigned long Len);
141
142 /// Extract and demangle the qualified symbol from a given mangled symbol
143 /// append it to the output string.
144 ///
145 /// \param Demangled Output buffer to write the demangled name.
146 /// \param Mangled Mangled symbol to be demangled.
147 ///
148 /// \see https://dlang.org/spec/abi.html#QualifiedName .
149 void parseQualified(OutputBuffer *Demangled, std::string_view &Mangled);
150
151 /// Extract and demangle a type from a given mangled symbol append it to
152 /// the output string.
153 ///
154 /// \param Mangled mangled symbol to be demangled.
155 ///
156 /// \return true on success, false on error.
157 ///
158 /// \see https://dlang.org/spec/abi.html#Type .
159 bool parseType(OutputBuffer *Demangled, std::string_view &Mangled);
160
161 /// An immutable view of the string we are demangling.
162 const std::string_view Str;
163 /// The index of the last back reference.
164 int LastBackref;
165};
166
167} // namespace
168
169void Demangler::decodeNumber(std::string_view &Mangled, unsigned long &Ret) {
170 // Clear Mangled if trying to extract something that isn't a digit.
171 if (Mangled.empty()) {
172 Mangled = {};
173 return;
174 }
175
176 if (!std::isdigit(Mangled.front())) {
177 Mangled = {};
178 return;
179 }
180
181 unsigned long Val = 0;
182
183 do {
184 unsigned long Digit = Mangled[0] - '0';
185
186 // Check for overflow.
187 if (Val > (std::numeric_limits<unsigned int>::max() - Digit) / 10) {
188 Mangled = {};
189 return;
190 }
191
192 Val = Val * 10 + Digit;
193 Mangled.remove_prefix(n: 1);
194 } while (!Mangled.empty() && std::isdigit(Mangled.front()));
195
196 if (Mangled.empty()) {
197 Mangled = {};
198 return;
199 }
200
201 Ret = Val;
202}
203
204bool Demangler::decodeBackrefPos(std::string_view &Mangled, long &Ret) {
205 // Return nullptr if trying to extract something that isn't a digit
206 if (Mangled.empty()) {
207 Mangled = {};
208 return false;
209 }
210 // Any identifier or non-basic type that has been emitted to the mangled
211 // symbol before will not be emitted again, but is referenced by a special
212 // sequence encoding the relative position of the original occurrence in the
213 // mangled symbol name.
214 // Numbers in back references are encoded with base 26 by upper case letters
215 // A-Z for higher digits but lower case letters a-z for the last digit.
216 // NumberBackRef:
217 // [a-z]
218 // [A-Z] NumberBackRef
219 // ^
220 unsigned long Val = 0;
221
222 while (!Mangled.empty() && std::isalpha(Mangled.front())) {
223 // Check for overflow
224 if (Val > (std::numeric_limits<unsigned long>::max() - 25) / 26)
225 break;
226
227 Val *= 26;
228
229 if (Mangled[0] >= 'a' && Mangled[0] <= 'z') {
230 Val += Mangled[0] - 'a';
231 if ((long)Val <= 0)
232 break;
233 Ret = Val;
234 Mangled.remove_prefix(n: 1);
235 return true;
236 }
237
238 Val += Mangled[0] - 'A';
239 Mangled.remove_prefix(n: 1);
240 }
241
242 Mangled = {};
243 return false;
244}
245
246bool Demangler::decodeBackref(std::string_view &Mangled,
247 std::string_view &Ret) {
248 assert(!Mangled.empty() && Mangled.front() == 'Q' &&
249 "Invalid back reference!");
250 Ret = {};
251
252 // Position of 'Q'
253 const char *Qpos = Mangled.data();
254 long RefPos;
255 Mangled.remove_prefix(n: 1);
256
257 if (!decodeBackrefPos(Mangled, Ret&: RefPos)) {
258 Mangled = {};
259 return false;
260 }
261
262 if (RefPos > Qpos - Str.data()) {
263 Mangled = {};
264 return false;
265 }
266
267 // Set the position of the back reference.
268 Ret = Qpos - RefPos;
269
270 return true;
271}
272
273void Demangler::parseSymbolBackref(OutputBuffer *Demangled,
274 std::string_view &Mangled) {
275 // An identifier back reference always points to a digit 0 to 9.
276 // IdentifierBackRef:
277 // Q NumberBackRef
278 // ^
279 unsigned long Len;
280
281 // Get position of the back reference
282 std::string_view Backref;
283 if (!decodeBackref(Mangled, Ret&: Backref)) {
284 Mangled = {};
285 return;
286 }
287
288 // Must point to a simple identifier
289 decodeNumber(Mangled&: Backref, Ret&: Len);
290 if (Backref.empty() || Backref.length() < Len) {
291 Mangled = {};
292 return;
293 }
294
295 parseLName(Demangled, Mangled&: Backref, Len);
296 if (Backref.empty())
297 Mangled = {};
298}
299
300void Demangler::parseTypeBackref(OutputBuffer *Demangled,
301 std::string_view &Mangled) {
302 // A type back reference always points to a letter.
303 // TypeBackRef:
304 // Q NumberBackRef
305 // ^
306
307 // If we appear to be moving backwards through the mangle string, then
308 // bail as this may be a recursive back reference.
309 if (Mangled.data() - Str.data() >= LastBackref) {
310 Mangled = {};
311 return;
312 }
313
314 int SaveRefPos = LastBackref;
315 LastBackref = Mangled.data() - Str.data();
316
317 // Get position of the back reference.
318 std::string_view Backref;
319 if (!decodeBackref(Mangled, Ret&: Backref)) {
320 Mangled = {};
321 return;
322 }
323
324 // Can't decode back reference.
325 if (Backref.empty()) {
326 Mangled = {};
327 return;
328 }
329
330 // TODO: Add support for function type back references.
331 if (!parseType(Demangled, Mangled&: Backref))
332 Mangled = {};
333
334 LastBackref = SaveRefPos;
335
336 if (Backref.empty())
337 Mangled = {};
338}
339
340bool Demangler::isSymbolName(std::string_view Mangled) {
341 long Ret;
342 const char *Qref = Mangled.data();
343
344 if (std::isdigit(Mangled.front()))
345 return true;
346
347 // TODO: Handle template instances.
348
349 if (Mangled.front() != 'Q')
350 return false;
351
352 Mangled.remove_prefix(n: 1);
353 bool Valid = decodeBackrefPos(Mangled, Ret);
354 if (!Valid || Ret > Qref - Str.data())
355 return false;
356
357 return std::isdigit(Qref[-Ret]);
358}
359
360void Demangler::parseMangle(OutputBuffer *Demangled,
361 std::string_view &Mangled) {
362 // A D mangled symbol is comprised of both scope and type information.
363 // MangleName:
364 // _D QualifiedName Type
365 // _D QualifiedName Z
366 // ^
367 // The caller should have guaranteed that the start pointer is at the
368 // above location.
369 // Note that type is never a function type, but only the return type of
370 // a function or the type of a variable.
371 Mangled.remove_prefix(n: 2);
372
373 parseQualified(Demangled, Mangled);
374
375 if (Mangled.empty()) {
376 Mangled = {};
377 return;
378 }
379
380 // Artificial symbols end with 'Z' and have no type.
381 if (Mangled.front() == 'Z') {
382 Mangled.remove_prefix(n: 1);
383 } else {
384 OutputBuffer TypeBuf;
385 if (!parseType(Demangled: &TypeBuf, Mangled))
386 Mangled = {};
387 else {
388 // Insert type before the symbol name that was already appended.
389 size_t TypeLen = TypeBuf.getCurrentPosition();
390 if (TypeLen > 0) {
391 Demangled->insert(Pos: 0, S: TypeBuf.getBuffer(), N: TypeLen);
392 Demangled->insert(Pos: TypeLen, S: " ", N: 1);
393 }
394 }
395 std::free(ptr: TypeBuf.getBuffer());
396 }
397}
398
399void Demangler::parseQualified(OutputBuffer *Demangled,
400 std::string_view &Mangled) {
401 // Qualified names are identifiers separated by their encoded length.
402 // Nested functions also encode their argument types without specifying
403 // what they return.
404 // QualifiedName:
405 // SymbolFunctionName
406 // SymbolFunctionName QualifiedName
407 // ^
408 // SymbolFunctionName:
409 // SymbolName
410 // SymbolName TypeFunctionNoReturn
411 // SymbolName M TypeFunctionNoReturn
412 // SymbolName M TypeModifiers TypeFunctionNoReturn
413 // The start pointer should be at the above location.
414
415 // Whether it has more than one symbol
416 size_t NotFirst = false;
417 do {
418 // Skip over anonymous symbols.
419 if (!Mangled.empty() && Mangled.front() == '0') {
420 do
421 Mangled.remove_prefix(n: 1);
422 while (!Mangled.empty() && Mangled.front() == '0');
423
424 continue;
425 }
426
427 if (NotFirst)
428 *Demangled << '.';
429 NotFirst = true;
430
431 parseIdentifier(Demangled, Mangled);
432 } while (!Mangled.empty() && isSymbolName(Mangled));
433}
434
435void Demangler::parseIdentifier(OutputBuffer *Demangled,
436 std::string_view &Mangled) {
437 if (Mangled.empty()) {
438 Mangled = {};
439 return;
440 }
441
442 if (Mangled.front() == 'Q')
443 return parseSymbolBackref(Demangled, Mangled);
444
445 // TODO: Parse lengthless template instances.
446
447 unsigned long Len;
448 decodeNumber(Mangled, Ret&: Len);
449
450 if (Mangled.empty()) {
451 Mangled = {};
452 return;
453 }
454 if (!Len || Mangled.length() < Len) {
455 Mangled = {};
456 return;
457 }
458
459 // TODO: Parse template instances with a length prefix.
460
461 // There can be multiple different declarations in the same function that
462 // have the same mangled name. To make the mangled names unique, a fake
463 // parent in the form `__Sddd' is added to the symbol.
464 if (Len >= 4 && starts_with(haystack: Mangled, needle: "__S")) {
465 const size_t SuffixLen = Mangled.length() - Len;
466 std::string_view P = Mangled.substr(pos: 3);
467 while (P.length() > SuffixLen && std::isdigit(P.front()))
468 P.remove_prefix(n: 1);
469 if (P.length() == SuffixLen) {
470 // Skip over the fake parent.
471 Mangled.remove_prefix(n: Len);
472 return parseIdentifier(Demangled, Mangled);
473 }
474
475 // Else demangle it as a plain identifier.
476 }
477
478 parseLName(Demangled, Mangled, Len);
479}
480
481bool Demangler::parseType(OutputBuffer *Demangled, std::string_view &Mangled) {
482 if (Mangled.empty()) {
483 Mangled = {};
484 return false;
485 }
486
487 switch (Mangled.front()) {
488 // TODO: Parse type qualifiers.
489 // TODO: Parse function types.
490 // TODO: Parse compound types.
491 // TODO: Parse delegate types.
492 // TODO: Parse tuple types.
493
494 // Basic types.
495 case 'i':
496 Mangled.remove_prefix(n: 1);
497 *Demangled << "int";
498 return true;
499
500 case 'v':
501 Mangled.remove_prefix(n: 1);
502 *Demangled << "void";
503 return true;
504
505 case 'a':
506 Mangled.remove_prefix(n: 1);
507 *Demangled << "char";
508 return true;
509 case 'b':
510 Mangled.remove_prefix(n: 1);
511 *Demangled << "bool";
512 return true;
513 case 'c':
514 Mangled.remove_prefix(n: 1);
515 *Demangled << "creal";
516 return true;
517 case 'd':
518 Mangled.remove_prefix(n: 1);
519 *Demangled << "double";
520 return true;
521 case 'e':
522 Mangled.remove_prefix(n: 1);
523 *Demangled << "real";
524 return true;
525 case 'f':
526 Mangled.remove_prefix(n: 1);
527 *Demangled << "float";
528 return true;
529 case 'g':
530 Mangled.remove_prefix(n: 1);
531 *Demangled << "byte";
532 return true;
533 case 'h':
534 Mangled.remove_prefix(n: 1);
535 *Demangled << "ubyte";
536 return true;
537 case 'j':
538 Mangled.remove_prefix(n: 1);
539 *Demangled << "ireal";
540 return true;
541 case 'k':
542 Mangled.remove_prefix(n: 1);
543 *Demangled << "uint";
544 return true;
545 case 'l':
546 Mangled.remove_prefix(n: 1);
547 *Demangled << "long";
548 return true;
549 case 'm':
550 Mangled.remove_prefix(n: 1);
551 *Demangled << "ulong";
552 return true;
553 case 'n':
554 Mangled.remove_prefix(n: 1);
555 return true; // typeof(null), no output
556 case 'o':
557 Mangled.remove_prefix(n: 1);
558 *Demangled << "ifloat";
559 return true;
560 case 'p':
561 Mangled.remove_prefix(n: 1);
562 *Demangled << "idouble";
563 return true;
564 case 'q':
565 Mangled.remove_prefix(n: 1);
566 *Demangled << "cfloat";
567 return true;
568 case 'r':
569 Mangled.remove_prefix(n: 1);
570 *Demangled << "cdouble";
571 return true;
572 case 's':
573 Mangled.remove_prefix(n: 1);
574 *Demangled << "short";
575 return true;
576 case 't':
577 Mangled.remove_prefix(n: 1);
578 *Demangled << "ushort";
579 return true;
580 case 'u':
581 Mangled.remove_prefix(n: 1);
582 *Demangled << "wchar";
583 return true;
584 case 'w':
585 Mangled.remove_prefix(n: 1);
586 *Demangled << "dchar";
587 return true;
588 case 'z': // two-char: zi=cent, zk=ucent
589 if (Mangled.size() < 2) {
590 Mangled = {};
591 return false;
592 }
593 if (Mangled[1] == 'i') {
594 Mangled.remove_prefix(n: 2);
595 *Demangled << "cent";
596 return true;
597 }
598 if (Mangled[1] == 'k') {
599 Mangled.remove_prefix(n: 2);
600 *Demangled << "ucent";
601 return true;
602 }
603 Mangled = {};
604 return false;
605 case 'N':
606 if (Mangled.size() < 2) {
607 Mangled = {};
608 return false;
609 }
610 if (Mangled[1] == 'n') {
611 Mangled.remove_prefix(n: 2);
612 *Demangled << "noreturn";
613 return true;
614 }
615 Mangled = {};
616 return false;
617
618 // Back referenced type.
619 case 'Q': {
620 parseTypeBackref(Demangled, Mangled);
621 return true;
622 }
623
624 default: // unhandled.
625 Mangled = {};
626 return false;
627 }
628}
629
630void Demangler::parseLName(OutputBuffer *Demangled, std::string_view &Mangled,
631 unsigned long Len) {
632 switch (Len) {
633 case 6:
634 if (starts_with(haystack: Mangled, needle: "__initZ")) {
635 // The static initializer for a given symbol.
636 Demangled->prepend(R: "initializer for ");
637 Demangled->setCurrentPosition(Demangled->getCurrentPosition() - 1);
638 Mangled.remove_prefix(n: Len);
639 return;
640 }
641 if (starts_with(haystack: Mangled, needle: "__vtblZ")) {
642 // The vtable symbol for a given class.
643 Demangled->prepend(R: "vtable for ");
644 Demangled->setCurrentPosition(Demangled->getCurrentPosition() - 1);
645 Mangled.remove_prefix(n: Len);
646 return;
647 }
648 break;
649
650 case 7:
651 if (starts_with(haystack: Mangled, needle: "__ClassZ")) {
652 // The classinfo symbol for a given class.
653 Demangled->prepend(R: "ClassInfo for ");
654 Demangled->setCurrentPosition(Demangled->getCurrentPosition() - 1);
655 Mangled.remove_prefix(n: Len);
656 return;
657 }
658 break;
659
660 case 11:
661 if (starts_with(haystack: Mangled, needle: "__InterfaceZ")) {
662 // The interface symbol for a given class.
663 Demangled->prepend(R: "Interface for ");
664 Demangled->setCurrentPosition(Demangled->getCurrentPosition() - 1);
665 Mangled.remove_prefix(n: Len);
666 return;
667 }
668 break;
669
670 case 12:
671 if (starts_with(haystack: Mangled, needle: "__ModuleInfoZ")) {
672 // The ModuleInfo symbol for a given module.
673 Demangled->prepend(R: "ModuleInfo for ");
674 Demangled->setCurrentPosition(Demangled->getCurrentPosition() - 1);
675 Mangled.remove_prefix(n: Len);
676 return;
677 }
678 break;
679 }
680
681 *Demangled << Mangled.substr(pos: 0, n: Len);
682 Mangled.remove_prefix(n: Len);
683}
684
685Demangler::Demangler(std::string_view Mangled)
686 : Str(Mangled), LastBackref(Mangled.length()) {}
687
688const char *Demangler::parseMangle(OutputBuffer *Demangled) {
689 std::string_view M(this->Str);
690 parseMangle(Demangled, Mangled&: M);
691 return M.data();
692}
693
694char *llvm::dlangDemangle(std::string_view MangledName) {
695 if (MangledName.empty() || !starts_with(haystack: MangledName, needle: "_D"))
696 return nullptr;
697
698 OutputBuffer Demangled;
699 if (MangledName == "_Dmain") {
700 Demangled << "D main";
701 } else {
702
703 Demangler D(MangledName);
704 const char *M = D.parseMangle(Demangled: &Demangled);
705
706 // Check that the entire symbol was successfully demangled.
707 if (M == nullptr || *M != '\0') {
708 std::free(ptr: Demangled.getBuffer());
709 return nullptr;
710 }
711 }
712
713 // OutputBuffer's internal buffer is not null terminated and therefore we need
714 // to add it to comply with C null terminated strings.
715 if (Demangled.getCurrentPosition() > 0) {
716 Demangled << '\0';
717 Demangled.setCurrentPosition(Demangled.getCurrentPosition() - 1);
718 return Demangled.getBuffer();
719 }
720
721 std::free(ptr: Demangled.getBuffer());
722 return nullptr;
723}
724