Symbolizer support for mingw and cygwin (#208)
[platform/upstream/glog.git] / src / demangle.cc
1 // Copyright (c) 2006, Google Inc.
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
6 // met:
7 //
8 //     * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 //     * Redistributions in binary form must reproduce the above
11 // copyright notice, this list of conditions and the following disclaimer
12 // in the documentation and/or other materials provided with the
13 // distribution.
14 //     * Neither the name of Google Inc. nor the names of its
15 // contributors may be used to endorse or promote products derived from
16 // this software without specific prior written permission.
17 //
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // Author: Satoru Takabayashi
31 //
32 // For reference check out:
33 // http://www.codesourcery.com/public/cxx-abi/abi.html#mangling
34 //
35 // Note that we only have partial C++0x support yet.
36
37 #include <stdio.h>  // for NULL
38 #include "utilities.h"
39 #include "demangle.h"
40
41 #if defined(OS_WINDOWS)
42 #include <DbgHelp.h>
43 #pragma comment(lib, "DbgHelp")
44 #endif
45
46 _START_GOOGLE_NAMESPACE_
47
48 #if !defined(OS_WINDOWS)
49 typedef struct {
50   const char *abbrev;
51   const char *real_name;
52 } AbbrevPair;
53
54 // List of operators from Itanium C++ ABI.
55 static const AbbrevPair kOperatorList[] = {
56   { "nw", "new" },
57   { "na", "new[]" },
58   { "dl", "delete" },
59   { "da", "delete[]" },
60   { "ps", "+" },
61   { "ng", "-" },
62   { "ad", "&" },
63   { "de", "*" },
64   { "co", "~" },
65   { "pl", "+" },
66   { "mi", "-" },
67   { "ml", "*" },
68   { "dv", "/" },
69   { "rm", "%" },
70   { "an", "&" },
71   { "or", "|" },
72   { "eo", "^" },
73   { "aS", "=" },
74   { "pL", "+=" },
75   { "mI", "-=" },
76   { "mL", "*=" },
77   { "dV", "/=" },
78   { "rM", "%=" },
79   { "aN", "&=" },
80   { "oR", "|=" },
81   { "eO", "^=" },
82   { "ls", "<<" },
83   { "rs", ">>" },
84   { "lS", "<<=" },
85   { "rS", ">>=" },
86   { "eq", "==" },
87   { "ne", "!=" },
88   { "lt", "<" },
89   { "gt", ">" },
90   { "le", "<=" },
91   { "ge", ">=" },
92   { "nt", "!" },
93   { "aa", "&&" },
94   { "oo", "||" },
95   { "pp", "++" },
96   { "mm", "--" },
97   { "cm", "," },
98   { "pm", "->*" },
99   { "pt", "->" },
100   { "cl", "()" },
101   { "ix", "[]" },
102   { "qu", "?" },
103   { "st", "sizeof" },
104   { "sz", "sizeof" },
105   { NULL, NULL },
106 };
107
108 // List of builtin types from Itanium C++ ABI.
109 static const AbbrevPair kBuiltinTypeList[] = {
110   { "v", "void" },
111   { "w", "wchar_t" },
112   { "b", "bool" },
113   { "c", "char" },
114   { "a", "signed char" },
115   { "h", "unsigned char" },
116   { "s", "short" },
117   { "t", "unsigned short" },
118   { "i", "int" },
119   { "j", "unsigned int" },
120   { "l", "long" },
121   { "m", "unsigned long" },
122   { "x", "long long" },
123   { "y", "unsigned long long" },
124   { "n", "__int128" },
125   { "o", "unsigned __int128" },
126   { "f", "float" },
127   { "d", "double" },
128   { "e", "long double" },
129   { "g", "__float128" },
130   { "z", "ellipsis" },
131   { NULL, NULL }
132 };
133
134 // List of substitutions Itanium C++ ABI.
135 static const AbbrevPair kSubstitutionList[] = {
136   { "St", "" },
137   { "Sa", "allocator" },
138   { "Sb", "basic_string" },
139   // std::basic_string<char, std::char_traits<char>,std::allocator<char> >
140   { "Ss", "string"},
141   // std::basic_istream<char, std::char_traits<char> >
142   { "Si", "istream" },
143   // std::basic_ostream<char, std::char_traits<char> >
144   { "So", "ostream" },
145   // std::basic_iostream<char, std::char_traits<char> >
146   { "Sd", "iostream" },
147   { NULL, NULL }
148 };
149
150 // State needed for demangling.
151 typedef struct {
152   const char *mangled_cur;  // Cursor of mangled name.
153   char *out_cur;            // Cursor of output string.
154   const char *out_begin;    // Beginning of output string.
155   const char *out_end;      // End of output string.
156   const char *prev_name;    // For constructors/destructors.
157   int prev_name_length;     // For constructors/destructors.
158   short nest_level;         // For nested names.
159   bool append;              // Append flag.
160   bool overflowed;          // True if output gets overflowed.
161 } State;
162
163 // We don't use strlen() in libc since it's not guaranteed to be async
164 // signal safe.
165 static size_t StrLen(const char *str) {
166   size_t len = 0;
167   while (*str != '\0') {
168     ++str;
169     ++len;
170   }
171   return len;
172 }
173
174 // Returns true if "str" has at least "n" characters remaining.
175 static bool AtLeastNumCharsRemaining(const char *str, int n) {
176   for (int i = 0; i < n; ++i) {
177     if (str[i] == '\0') {
178       return false;
179     }
180   }
181   return true;
182 }
183
184 // Returns true if "str" has "prefix" as a prefix.
185 static bool StrPrefix(const char *str, const char *prefix) {
186   size_t i = 0;
187   while (str[i] != '\0' && prefix[i] != '\0' &&
188          str[i] == prefix[i]) {
189     ++i;
190   }
191   return prefix[i] == '\0';  // Consumed everything in "prefix".
192 }
193
194 static void InitState(State *state, const char *mangled,
195                       char *out, int out_size) {
196   state->mangled_cur = mangled;
197   state->out_cur = out;
198   state->out_begin = out;
199   state->out_end = out + out_size;
200   state->prev_name  = NULL;
201   state->prev_name_length = -1;
202   state->nest_level = -1;
203   state->append = true;
204   state->overflowed = false;
205 }
206
207 // Returns true and advances "mangled_cur" if we find "one_char_token"
208 // at "mangled_cur" position.  It is assumed that "one_char_token" does
209 // not contain '\0'.
210 static bool ParseOneCharToken(State *state, const char one_char_token) {
211   if (state->mangled_cur[0] == one_char_token) {
212     ++state->mangled_cur;
213     return true;
214   }
215   return false;
216 }
217
218 // Returns true and advances "mangled_cur" if we find "two_char_token"
219 // at "mangled_cur" position.  It is assumed that "two_char_token" does
220 // not contain '\0'.
221 static bool ParseTwoCharToken(State *state, const char *two_char_token) {
222   if (state->mangled_cur[0] == two_char_token[0] &&
223       state->mangled_cur[1] == two_char_token[1]) {
224     state->mangled_cur += 2;
225     return true;
226   }
227   return false;
228 }
229
230 // Returns true and advances "mangled_cur" if we find any character in
231 // "char_class" at "mangled_cur" position.
232 static bool ParseCharClass(State *state, const char *char_class) {
233   const char *p = char_class;
234   for (; *p != '\0'; ++p) {
235     if (state->mangled_cur[0] == *p) {
236       ++state->mangled_cur;
237       return true;
238     }
239   }
240   return false;
241 }
242
243 // This function is used for handling an optional non-terminal.
244 static bool Optional(bool) {
245   return true;
246 }
247
248 // This function is used for handling <non-terminal>+ syntax.
249 typedef bool (*ParseFunc)(State *);
250 static bool OneOrMore(ParseFunc parse_func, State *state) {
251   if (parse_func(state)) {
252     while (parse_func(state)) {
253     }
254     return true;
255   }
256   return false;
257 }
258
259 // This function is used for handling <non-terminal>* syntax. The function
260 // always returns true and must be followed by a termination token or a
261 // terminating sequence not handled by parse_func (e.g.
262 // ParseOneCharToken(state, 'E')).
263 static bool ZeroOrMore(ParseFunc parse_func, State *state) {
264   while (parse_func(state)) {
265   }
266   return true;
267 }
268
269 // Append "str" at "out_cur".  If there is an overflow, "overflowed"
270 // is set to true for later use.  The output string is ensured to
271 // always terminate with '\0' as long as there is no overflow.
272 static void Append(State *state, const char * const str, const int length) {
273   int i;
274   for (i = 0; i < length; ++i) {
275     if (state->out_cur + 1 < state->out_end) {  // +1 for '\0'
276       *state->out_cur = str[i];
277       ++state->out_cur;
278     } else {
279       state->overflowed = true;
280       break;
281     }
282   }
283   if (!state->overflowed) {
284     *state->out_cur = '\0';  // Terminate it with '\0'
285   }
286 }
287
288 // We don't use equivalents in libc to avoid locale issues.
289 static bool IsLower(char c) {
290   return c >= 'a' && c <= 'z';
291 }
292
293 static bool IsAlpha(char c) {
294   return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
295 }
296
297 static bool IsDigit(char c) {
298   return c >= '0' && c <= '9';
299 }
300
301 // Returns true if "str" is a function clone suffix.  These suffixes are used
302 // by GCC 4.5.x and later versions to indicate functions which have been
303 // cloned during optimization.  We treat any sequence (.<alpha>+.<digit>+)+ as
304 // a function clone suffix.
305 static bool IsFunctionCloneSuffix(const char *str) {
306   size_t i = 0;
307   while (str[i] != '\0') {
308     // Consume a single .<alpha>+.<digit>+ sequence.
309     if (str[i] != '.' || !IsAlpha(str[i + 1])) {
310       return false;
311     }
312     i += 2;
313     while (IsAlpha(str[i])) {
314       ++i;
315     }
316     if (str[i] != '.' || !IsDigit(str[i + 1])) {
317       return false;
318     }
319     i += 2;
320     while (IsDigit(str[i])) {
321       ++i;
322     }
323   }
324   return true;  // Consumed everything in "str".
325 }
326
327 // Append "str" with some tweaks, iff "append" state is true.
328 // Returns true so that it can be placed in "if" conditions.
329 static void MaybeAppendWithLength(State *state, const char * const str,
330                                   const int length) {
331   if (state->append && length > 0) {
332     // Append a space if the output buffer ends with '<' and "str"
333     // starts with '<' to avoid <<<.
334     if (str[0] == '<' && state->out_begin < state->out_cur  &&
335         state->out_cur[-1] == '<') {
336       Append(state, " ", 1);
337     }
338     // Remember the last identifier name for ctors/dtors.
339     if (IsAlpha(str[0]) || str[0] == '_') {
340       state->prev_name = state->out_cur;
341       state->prev_name_length = length;
342     }
343     Append(state, str, length);
344   }
345 }
346
347 // A convenient wrapper arount MaybeAppendWithLength().
348 static bool MaybeAppend(State *state, const char * const str) {
349   if (state->append) {
350     int length = StrLen(str);
351     MaybeAppendWithLength(state, str, length);
352   }
353   return true;
354 }
355
356 // This function is used for handling nested names.
357 static bool EnterNestedName(State *state) {
358   state->nest_level = 0;
359   return true;
360 }
361
362 // This function is used for handling nested names.
363 static bool LeaveNestedName(State *state, short prev_value) {
364   state->nest_level = prev_value;
365   return true;
366 }
367
368 // Disable the append mode not to print function parameters, etc.
369 static bool DisableAppend(State *state) {
370   state->append = false;
371   return true;
372 }
373
374 // Restore the append mode to the previous state.
375 static bool RestoreAppend(State *state, bool prev_value) {
376   state->append = prev_value;
377   return true;
378 }
379
380 // Increase the nest level for nested names.
381 static void MaybeIncreaseNestLevel(State *state) {
382   if (state->nest_level > -1) {
383     ++state->nest_level;
384   }
385 }
386
387 // Appends :: for nested names if necessary.
388 static void MaybeAppendSeparator(State *state) {
389   if (state->nest_level >= 1) {
390     MaybeAppend(state, "::");
391   }
392 }
393
394 // Cancel the last separator if necessary.
395 static void MaybeCancelLastSeparator(State *state) {
396   if (state->nest_level >= 1 && state->append &&
397       state->out_begin <= state->out_cur - 2) {
398     state->out_cur -= 2;
399     *state->out_cur = '\0';
400   }
401 }
402
403 // Returns true if the identifier of the given length pointed to by
404 // "mangled_cur" is anonymous namespace.
405 static bool IdentifierIsAnonymousNamespace(State *state, int length) {
406   static const char anon_prefix[] = "_GLOBAL__N_";
407   return (length > (int)sizeof(anon_prefix) - 1 &&  // Should be longer.
408           StrPrefix(state->mangled_cur, anon_prefix));
409 }
410
411 // Forward declarations of our parsing functions.
412 static bool ParseMangledName(State *state);
413 static bool ParseEncoding(State *state);
414 static bool ParseName(State *state);
415 static bool ParseUnscopedName(State *state);
416 static bool ParseUnscopedTemplateName(State *state);
417 static bool ParseNestedName(State *state);
418 static bool ParsePrefix(State *state);
419 static bool ParseUnqualifiedName(State *state);
420 static bool ParseSourceName(State *state);
421 static bool ParseLocalSourceName(State *state);
422 static bool ParseNumber(State *state, int *number_out);
423 static bool ParseFloatNumber(State *state);
424 static bool ParseSeqId(State *state);
425 static bool ParseIdentifier(State *state, int length);
426 static bool ParseOperatorName(State *state);
427 static bool ParseSpecialName(State *state);
428 static bool ParseCallOffset(State *state);
429 static bool ParseNVOffset(State *state);
430 static bool ParseVOffset(State *state);
431 static bool ParseCtorDtorName(State *state);
432 static bool ParseType(State *state);
433 static bool ParseCVQualifiers(State *state);
434 static bool ParseBuiltinType(State *state);
435 static bool ParseFunctionType(State *state);
436 static bool ParseBareFunctionType(State *state);
437 static bool ParseClassEnumType(State *state);
438 static bool ParseArrayType(State *state);
439 static bool ParsePointerToMemberType(State *state);
440 static bool ParseTemplateParam(State *state);
441 static bool ParseTemplateTemplateParam(State *state);
442 static bool ParseTemplateArgs(State *state);
443 static bool ParseTemplateArg(State *state);
444 static bool ParseExpression(State *state);
445 static bool ParseExprPrimary(State *state);
446 static bool ParseLocalName(State *state);
447 static bool ParseDiscriminator(State *state);
448 static bool ParseSubstitution(State *state);
449
450 // Implementation note: the following code is a straightforward
451 // translation of the Itanium C++ ABI defined in BNF with a couple of
452 // exceptions.
453 //
454 // - Support GNU extensions not defined in the Itanium C++ ABI
455 // - <prefix> and <template-prefix> are combined to avoid infinite loop
456 // - Reorder patterns to shorten the code
457 // - Reorder patterns to give greedier functions precedence
458 //   We'll mark "Less greedy than" for these cases in the code
459 //
460 // Each parsing function changes the state and returns true on
461 // success.  Otherwise, don't change the state and returns false.  To
462 // ensure that the state isn't changed in the latter case, we save the
463 // original state before we call more than one parsing functions
464 // consecutively with &&, and restore the state if unsuccessful.  See
465 // ParseEncoding() as an example of this convention.  We follow the
466 // convention throughout the code.
467 //
468 // Originally we tried to do demangling without following the full ABI
469 // syntax but it turned out we needed to follow the full syntax to
470 // parse complicated cases like nested template arguments.  Note that
471 // implementing a full-fledged demangler isn't trivial (libiberty's
472 // cp-demangle.c has +4300 lines).
473 //
474 // Note that (foo) in <(foo) ...> is a modifier to be ignored.
475 //
476 // Reference:
477 // - Itanium C++ ABI
478 //   <http://www.codesourcery.com/cxx-abi/abi.html#mangling>
479
480 // <mangled-name> ::= _Z <encoding>
481 static bool ParseMangledName(State *state) {
482   return ParseTwoCharToken(state, "_Z") && ParseEncoding(state);
483 }
484
485 // <encoding> ::= <(function) name> <bare-function-type>
486 //            ::= <(data) name>
487 //            ::= <special-name>
488 static bool ParseEncoding(State *state) {
489   State copy = *state;
490   if (ParseName(state) && ParseBareFunctionType(state)) {
491     return true;
492   }
493   *state = copy;
494
495   if (ParseName(state) || ParseSpecialName(state)) {
496     return true;
497   }
498   return false;
499 }
500
501 // <name> ::= <nested-name>
502 //        ::= <unscoped-template-name> <template-args>
503 //        ::= <unscoped-name>
504 //        ::= <local-name>
505 static bool ParseName(State *state) {
506   if (ParseNestedName(state) || ParseLocalName(state)) {
507     return true;
508   }
509
510   State copy = *state;
511   if (ParseUnscopedTemplateName(state) &&
512       ParseTemplateArgs(state)) {
513     return true;
514   }
515   *state = copy;
516
517   // Less greedy than <unscoped-template-name> <template-args>.
518   if (ParseUnscopedName(state)) {
519     return true;
520   }
521   return false;
522 }
523
524 // <unscoped-name> ::= <unqualified-name>
525 //                 ::= St <unqualified-name>
526 static bool ParseUnscopedName(State *state) {
527   if (ParseUnqualifiedName(state)) {
528     return true;
529   }
530
531   State copy = *state;
532   if (ParseTwoCharToken(state, "St") &&
533       MaybeAppend(state, "std::") &&
534       ParseUnqualifiedName(state)) {
535     return true;
536   }
537   *state = copy;
538   return false;
539 }
540
541 // <unscoped-template-name> ::= <unscoped-name>
542 //                          ::= <substitution>
543 static bool ParseUnscopedTemplateName(State *state) {
544   return ParseUnscopedName(state) || ParseSubstitution(state);
545 }
546
547 // <nested-name> ::= N [<CV-qualifiers>] <prefix> <unqualified-name> E
548 //               ::= N [<CV-qualifiers>] <template-prefix> <template-args> E
549 static bool ParseNestedName(State *state) {
550   State copy = *state;
551   if (ParseOneCharToken(state, 'N') &&
552       EnterNestedName(state) &&
553       Optional(ParseCVQualifiers(state)) &&
554       ParsePrefix(state) &&
555       LeaveNestedName(state, copy.nest_level) &&
556       ParseOneCharToken(state, 'E')) {
557     return true;
558   }
559   *state = copy;
560   return false;
561 }
562
563 // This part is tricky.  If we literally translate them to code, we'll
564 // end up infinite loop.  Hence we merge them to avoid the case.
565 //
566 // <prefix> ::= <prefix> <unqualified-name>
567 //          ::= <template-prefix> <template-args>
568 //          ::= <template-param>
569 //          ::= <substitution>
570 //          ::= # empty
571 // <template-prefix> ::= <prefix> <(template) unqualified-name>
572 //                   ::= <template-param>
573 //                   ::= <substitution>
574 static bool ParsePrefix(State *state) {
575   bool has_something = false;
576   while (true) {
577     MaybeAppendSeparator(state);
578     if (ParseTemplateParam(state) ||
579         ParseSubstitution(state) ||
580         ParseUnscopedName(state)) {
581       has_something = true;
582       MaybeIncreaseNestLevel(state);
583       continue;
584     }
585     MaybeCancelLastSeparator(state);
586     if (has_something && ParseTemplateArgs(state)) {
587       return ParsePrefix(state);
588     } else {
589       break;
590     }
591   }
592   return true;
593 }
594
595 // <unqualified-name> ::= <operator-name>
596 //                    ::= <ctor-dtor-name>
597 //                    ::= <source-name>
598 //                    ::= <local-source-name>
599 static bool ParseUnqualifiedName(State *state) {
600   return (ParseOperatorName(state) ||
601           ParseCtorDtorName(state) ||
602           ParseSourceName(state) ||
603           ParseLocalSourceName(state));
604 }
605
606 // <source-name> ::= <positive length number> <identifier>
607 static bool ParseSourceName(State *state) {
608   State copy = *state;
609   int length = -1;
610   if (ParseNumber(state, &length) && ParseIdentifier(state, length)) {
611     return true;
612   }
613   *state = copy;
614   return false;
615 }
616
617 // <local-source-name> ::= L <source-name> [<discriminator>]
618 //
619 // References:
620 //   http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31775
621 //   http://gcc.gnu.org/viewcvs?view=rev&revision=124467
622 static bool ParseLocalSourceName(State *state) {
623   State copy = *state;
624   if (ParseOneCharToken(state, 'L') && ParseSourceName(state) &&
625       Optional(ParseDiscriminator(state))) {
626     return true;
627   }
628   *state = copy;
629   return false;
630 }
631
632 // <number> ::= [n] <non-negative decimal integer>
633 // If "number_out" is non-null, then *number_out is set to the value of the
634 // parsed number on success.
635 static bool ParseNumber(State *state, int *number_out) {
636   int sign = 1;
637   if (ParseOneCharToken(state, 'n')) {
638     sign = -1;
639   }
640   const char *p = state->mangled_cur;
641   int number = 0;
642   for (;*p != '\0'; ++p) {
643     if (IsDigit(*p)) {
644       number = number * 10 + (*p - '0');
645     } else {
646       break;
647     }
648   }
649   if (p != state->mangled_cur) {  // Conversion succeeded.
650     state->mangled_cur = p;
651     if (number_out != NULL) {
652       *number_out = number * sign;
653     }
654     return true;
655   }
656   return false;
657 }
658
659 // Floating-point literals are encoded using a fixed-length lowercase
660 // hexadecimal string.
661 static bool ParseFloatNumber(State *state) {
662   const char *p = state->mangled_cur;
663   for (;*p != '\0'; ++p) {
664     if (!IsDigit(*p) && !(*p >= 'a' && *p <= 'f')) {
665       break;
666     }
667   }
668   if (p != state->mangled_cur) {  // Conversion succeeded.
669     state->mangled_cur = p;
670     return true;
671   }
672   return false;
673 }
674
675 // The <seq-id> is a sequence number in base 36,
676 // using digits and upper case letters
677 static bool ParseSeqId(State *state) {
678   const char *p = state->mangled_cur;
679   for (;*p != '\0'; ++p) {
680     if (!IsDigit(*p) && !(*p >= 'A' && *p <= 'Z')) {
681       break;
682     }
683   }
684   if (p != state->mangled_cur) {  // Conversion succeeded.
685     state->mangled_cur = p;
686     return true;
687   }
688   return false;
689 }
690
691 // <identifier> ::= <unqualified source code identifier> (of given length)
692 static bool ParseIdentifier(State *state, int length) {
693   if (length == -1 ||
694       !AtLeastNumCharsRemaining(state->mangled_cur, length)) {
695     return false;
696   }
697   if (IdentifierIsAnonymousNamespace(state, length)) {
698     MaybeAppend(state, "(anonymous namespace)");
699   } else {
700     MaybeAppendWithLength(state, state->mangled_cur, length);
701   }
702   state->mangled_cur += length;
703   return true;
704 }
705
706 // <operator-name> ::= nw, and other two letters cases
707 //                 ::= cv <type>  # (cast)
708 //                 ::= v  <digit> <source-name> # vendor extended operator
709 static bool ParseOperatorName(State *state) {
710   if (!AtLeastNumCharsRemaining(state->mangled_cur, 2)) {
711     return false;
712   }
713   // First check with "cv" (cast) case.
714   State copy = *state;
715   if (ParseTwoCharToken(state, "cv") &&
716       MaybeAppend(state, "operator ") &&
717       EnterNestedName(state) &&
718       ParseType(state) &&
719       LeaveNestedName(state, copy.nest_level)) {
720     return true;
721   }
722   *state = copy;
723
724   // Then vendor extended operators.
725   if (ParseOneCharToken(state, 'v') && ParseCharClass(state, "0123456789") &&
726       ParseSourceName(state)) {
727     return true;
728   }
729   *state = copy;
730
731   // Other operator names should start with a lower alphabet followed
732   // by a lower/upper alphabet.
733   if (!(IsLower(state->mangled_cur[0]) &&
734         IsAlpha(state->mangled_cur[1]))) {
735     return false;
736   }
737   // We may want to perform a binary search if we really need speed.
738   const AbbrevPair *p;
739   for (p = kOperatorList; p->abbrev != NULL; ++p) {
740     if (state->mangled_cur[0] == p->abbrev[0] &&
741         state->mangled_cur[1] == p->abbrev[1]) {
742       MaybeAppend(state, "operator");
743       if (IsLower(*p->real_name)) {  // new, delete, etc.
744         MaybeAppend(state, " ");
745       }
746       MaybeAppend(state, p->real_name);
747       state->mangled_cur += 2;
748       return true;
749     }
750   }
751   return false;
752 }
753
754 // <special-name> ::= TV <type>
755 //                ::= TT <type>
756 //                ::= TI <type>
757 //                ::= TS <type>
758 //                ::= Tc <call-offset> <call-offset> <(base) encoding>
759 //                ::= GV <(object) name>
760 //                ::= T <call-offset> <(base) encoding>
761 // G++ extensions:
762 //                ::= TC <type> <(offset) number> _ <(base) type>
763 //                ::= TF <type>
764 //                ::= TJ <type>
765 //                ::= GR <name>
766 //                ::= GA <encoding>
767 //                ::= Th <call-offset> <(base) encoding>
768 //                ::= Tv <call-offset> <(base) encoding>
769 //
770 // Note: we don't care much about them since they don't appear in
771 // stack traces.  The are special data.
772 static bool ParseSpecialName(State *state) {
773   State copy = *state;
774   if (ParseOneCharToken(state, 'T') &&
775       ParseCharClass(state, "VTIS") &&
776       ParseType(state)) {
777     return true;
778   }
779   *state = copy;
780
781   if (ParseTwoCharToken(state, "Tc") && ParseCallOffset(state) &&
782       ParseCallOffset(state) && ParseEncoding(state)) {
783     return true;
784   }
785   *state = copy;
786
787   if (ParseTwoCharToken(state, "GV") &&
788       ParseName(state)) {
789     return true;
790   }
791   *state = copy;
792
793   if (ParseOneCharToken(state, 'T') && ParseCallOffset(state) &&
794       ParseEncoding(state)) {
795     return true;
796   }
797   *state = copy;
798
799   // G++ extensions
800   if (ParseTwoCharToken(state, "TC") && ParseType(state) &&
801       ParseNumber(state, NULL) && ParseOneCharToken(state, '_') &&
802       DisableAppend(state) &&
803       ParseType(state)) {
804     RestoreAppend(state, copy.append);
805     return true;
806   }
807   *state = copy;
808
809   if (ParseOneCharToken(state, 'T') && ParseCharClass(state, "FJ") &&
810       ParseType(state)) {
811     return true;
812   }
813   *state = copy;
814
815   if (ParseTwoCharToken(state, "GR") && ParseName(state)) {
816     return true;
817   }
818   *state = copy;
819
820   if (ParseTwoCharToken(state, "GA") && ParseEncoding(state)) {
821     return true;
822   }
823   *state = copy;
824
825   if (ParseOneCharToken(state, 'T') && ParseCharClass(state, "hv") &&
826       ParseCallOffset(state) && ParseEncoding(state)) {
827     return true;
828   }
829   *state = copy;
830   return false;
831 }
832
833 // <call-offset> ::= h <nv-offset> _
834 //               ::= v <v-offset> _
835 static bool ParseCallOffset(State *state) {
836   State copy = *state;
837   if (ParseOneCharToken(state, 'h') &&
838       ParseNVOffset(state) && ParseOneCharToken(state, '_')) {
839     return true;
840   }
841   *state = copy;
842
843   if (ParseOneCharToken(state, 'v') &&
844       ParseVOffset(state) && ParseOneCharToken(state, '_')) {
845     return true;
846   }
847   *state = copy;
848
849   return false;
850 }
851
852 // <nv-offset> ::= <(offset) number>
853 static bool ParseNVOffset(State *state) {
854   return ParseNumber(state, NULL);
855 }
856
857 // <v-offset>  ::= <(offset) number> _ <(virtual offset) number>
858 static bool ParseVOffset(State *state) {
859   State copy = *state;
860   if (ParseNumber(state, NULL) && ParseOneCharToken(state, '_') &&
861       ParseNumber(state, NULL)) {
862     return true;
863   }
864   *state = copy;
865   return false;
866 }
867
868 // <ctor-dtor-name> ::= C1 | C2 | C3
869 //                  ::= D0 | D1 | D2
870 static bool ParseCtorDtorName(State *state) {
871   State copy = *state;
872   if (ParseOneCharToken(state, 'C') &&
873       ParseCharClass(state, "123")) {
874     const char * const prev_name = state->prev_name;
875     const int prev_name_length = state->prev_name_length;
876     MaybeAppendWithLength(state, prev_name, prev_name_length);
877     return true;
878   }
879   *state = copy;
880
881   if (ParseOneCharToken(state, 'D') &&
882       ParseCharClass(state, "012")) {
883     const char * const prev_name = state->prev_name;
884     const int prev_name_length = state->prev_name_length;
885     MaybeAppend(state, "~");
886     MaybeAppendWithLength(state, prev_name, prev_name_length);
887     return true;
888   }
889   *state = copy;
890   return false;
891 }
892
893 // <type> ::= <CV-qualifiers> <type>
894 //        ::= P <type>   # pointer-to
895 //        ::= R <type>   # reference-to
896 //        ::= O <type>   # rvalue reference-to (C++0x)
897 //        ::= C <type>   # complex pair (C 2000)
898 //        ::= G <type>   # imaginary (C 2000)
899 //        ::= U <source-name> <type>  # vendor extended type qualifier
900 //        ::= <builtin-type>
901 //        ::= <function-type>
902 //        ::= <class-enum-type>
903 //        ::= <array-type>
904 //        ::= <pointer-to-member-type>
905 //        ::= <template-template-param> <template-args>
906 //        ::= <template-param>
907 //        ::= <substitution>
908 //        ::= Dp <type>          # pack expansion of (C++0x)
909 //        ::= Dt <expression> E  # decltype of an id-expression or class
910 //                               # member access (C++0x)
911 //        ::= DT <expression> E  # decltype of an expression (C++0x)
912 //
913 static bool ParseType(State *state) {
914   // We should check CV-qualifers, and PRGC things first.
915   State copy = *state;
916   if (ParseCVQualifiers(state) && ParseType(state)) {
917     return true;
918   }
919   *state = copy;
920
921   if (ParseCharClass(state, "OPRCG") && ParseType(state)) {
922     return true;
923   }
924   *state = copy;
925
926   if (ParseTwoCharToken(state, "Dp") && ParseType(state)) {
927     return true;
928   }
929   *state = copy;
930
931   if (ParseOneCharToken(state, 'D') && ParseCharClass(state, "tT") &&
932       ParseExpression(state) && ParseOneCharToken(state, 'E')) {
933     return true;
934   }
935   *state = copy;
936
937   if (ParseOneCharToken(state, 'U') && ParseSourceName(state) &&
938       ParseType(state)) {
939     return true;
940   }
941   *state = copy;
942
943   if (ParseBuiltinType(state) ||
944       ParseFunctionType(state) ||
945       ParseClassEnumType(state) ||
946       ParseArrayType(state) ||
947       ParsePointerToMemberType(state) ||
948       ParseSubstitution(state)) {
949     return true;
950   }
951
952   if (ParseTemplateTemplateParam(state) &&
953       ParseTemplateArgs(state)) {
954     return true;
955   }
956   *state = copy;
957
958   // Less greedy than <template-template-param> <template-args>.
959   if (ParseTemplateParam(state)) {
960     return true;
961   }
962
963   return false;
964 }
965
966 // <CV-qualifiers> ::= [r] [V] [K]
967 // We don't allow empty <CV-qualifiers> to avoid infinite loop in
968 // ParseType().
969 static bool ParseCVQualifiers(State *state) {
970   int num_cv_qualifiers = 0;
971   num_cv_qualifiers += ParseOneCharToken(state, 'r');
972   num_cv_qualifiers += ParseOneCharToken(state, 'V');
973   num_cv_qualifiers += ParseOneCharToken(state, 'K');
974   return num_cv_qualifiers > 0;
975 }
976
977 // <builtin-type> ::= v, etc.
978 //                ::= u <source-name>
979 static bool ParseBuiltinType(State *state) {
980   const AbbrevPair *p;
981   for (p = kBuiltinTypeList; p->abbrev != NULL; ++p) {
982     if (state->mangled_cur[0] == p->abbrev[0]) {
983       MaybeAppend(state, p->real_name);
984       ++state->mangled_cur;
985       return true;
986     }
987   }
988
989   State copy = *state;
990   if (ParseOneCharToken(state, 'u') && ParseSourceName(state)) {
991     return true;
992   }
993   *state = copy;
994   return false;
995 }
996
997 // <function-type> ::= F [Y] <bare-function-type> E
998 static bool ParseFunctionType(State *state) {
999   State copy = *state;
1000   if (ParseOneCharToken(state, 'F') &&
1001       Optional(ParseOneCharToken(state, 'Y')) &&
1002       ParseBareFunctionType(state) && ParseOneCharToken(state, 'E')) {
1003     return true;
1004   }
1005   *state = copy;
1006   return false;
1007 }
1008
1009 // <bare-function-type> ::= <(signature) type>+
1010 static bool ParseBareFunctionType(State *state) {
1011   State copy = *state;
1012   DisableAppend(state);
1013   if (OneOrMore(ParseType, state)) {
1014     RestoreAppend(state, copy.append);
1015     MaybeAppend(state, "()");
1016     return true;
1017   }
1018   *state = copy;
1019   return false;
1020 }
1021
1022 // <class-enum-type> ::= <name>
1023 static bool ParseClassEnumType(State *state) {
1024   return ParseName(state);
1025 }
1026
1027 // <array-type> ::= A <(positive dimension) number> _ <(element) type>
1028 //              ::= A [<(dimension) expression>] _ <(element) type>
1029 static bool ParseArrayType(State *state) {
1030   State copy = *state;
1031   if (ParseOneCharToken(state, 'A') && ParseNumber(state, NULL) &&
1032       ParseOneCharToken(state, '_') && ParseType(state)) {
1033     return true;
1034   }
1035   *state = copy;
1036
1037   if (ParseOneCharToken(state, 'A') && Optional(ParseExpression(state)) &&
1038       ParseOneCharToken(state, '_') && ParseType(state)) {
1039     return true;
1040   }
1041   *state = copy;
1042   return false;
1043 }
1044
1045 // <pointer-to-member-type> ::= M <(class) type> <(member) type>
1046 static bool ParsePointerToMemberType(State *state) {
1047   State copy = *state;
1048   if (ParseOneCharToken(state, 'M') && ParseType(state) &&
1049       ParseType(state)) {
1050     return true;
1051   }
1052   *state = copy;
1053   return false;
1054 }
1055
1056 // <template-param> ::= T_
1057 //                  ::= T <parameter-2 non-negative number> _
1058 static bool ParseTemplateParam(State *state) {
1059   if (ParseTwoCharToken(state, "T_")) {
1060     MaybeAppend(state, "?");  // We don't support template substitutions.
1061     return true;
1062   }
1063
1064   State copy = *state;
1065   if (ParseOneCharToken(state, 'T') && ParseNumber(state, NULL) &&
1066       ParseOneCharToken(state, '_')) {
1067     MaybeAppend(state, "?");  // We don't support template substitutions.
1068     return true;
1069   }
1070   *state = copy;
1071   return false;
1072 }
1073
1074
1075 // <template-template-param> ::= <template-param>
1076 //                           ::= <substitution>
1077 static bool ParseTemplateTemplateParam(State *state) {
1078   return (ParseTemplateParam(state) ||
1079           ParseSubstitution(state));
1080 }
1081
1082 // <template-args> ::= I <template-arg>+ E
1083 static bool ParseTemplateArgs(State *state) {
1084   State copy = *state;
1085   DisableAppend(state);
1086   if (ParseOneCharToken(state, 'I') &&
1087       OneOrMore(ParseTemplateArg, state) &&
1088       ParseOneCharToken(state, 'E')) {
1089     RestoreAppend(state, copy.append);
1090     MaybeAppend(state, "<>");
1091     return true;
1092   }
1093   *state = copy;
1094   return false;
1095 }
1096
1097 // <template-arg>  ::= <type>
1098 //                 ::= <expr-primary>
1099 //                 ::= I <template-arg>* E        # argument pack
1100 //                 ::= X <expression> E
1101 static bool ParseTemplateArg(State *state) {
1102   State copy = *state;
1103   if (ParseOneCharToken(state, 'I') &&
1104       ZeroOrMore(ParseTemplateArg, state) &&
1105       ParseOneCharToken(state, 'E')) {
1106     return true;
1107   }
1108   *state = copy;
1109
1110   if (ParseType(state) ||
1111       ParseExprPrimary(state)) {
1112     return true;
1113   }
1114   *state = copy;
1115
1116   if (ParseOneCharToken(state, 'X') && ParseExpression(state) &&
1117       ParseOneCharToken(state, 'E')) {
1118     return true;
1119   }
1120   *state = copy;
1121   return false;
1122 }
1123
1124 // <expression> ::= <template-param>
1125 //              ::= <expr-primary>
1126 //              ::= <unary operator-name> <expression>
1127 //              ::= <binary operator-name> <expression> <expression>
1128 //              ::= <trinary operator-name> <expression> <expression>
1129 //                  <expression>
1130 //              ::= st <type>
1131 //              ::= sr <type> <unqualified-name> <template-args>
1132 //              ::= sr <type> <unqualified-name>
1133 static bool ParseExpression(State *state) {
1134   if (ParseTemplateParam(state) || ParseExprPrimary(state)) {
1135     return true;
1136   }
1137
1138   State copy = *state;
1139   if (ParseOperatorName(state) &&
1140       ParseExpression(state) &&
1141       ParseExpression(state) &&
1142       ParseExpression(state)) {
1143     return true;
1144   }
1145   *state = copy;
1146
1147   if (ParseOperatorName(state) &&
1148       ParseExpression(state) &&
1149       ParseExpression(state)) {
1150     return true;
1151   }
1152   *state = copy;
1153
1154   if (ParseOperatorName(state) &&
1155       ParseExpression(state)) {
1156     return true;
1157   }
1158   *state = copy;
1159
1160   if (ParseTwoCharToken(state, "st") && ParseType(state)) {
1161     return true;
1162   }
1163   *state = copy;
1164
1165   if (ParseTwoCharToken(state, "sr") && ParseType(state) &&
1166       ParseUnqualifiedName(state) &&
1167       ParseTemplateArgs(state)) {
1168     return true;
1169   }
1170   *state = copy;
1171
1172   if (ParseTwoCharToken(state, "sr") && ParseType(state) &&
1173       ParseUnqualifiedName(state)) {
1174     return true;
1175   }
1176   *state = copy;
1177   return false;
1178 }
1179
1180 // <expr-primary> ::= L <type> <(value) number> E
1181 //                ::= L <type> <(value) float> E
1182 //                ::= L <mangled-name> E
1183 //                // A bug in g++'s C++ ABI version 2 (-fabi-version=2).
1184 //                ::= LZ <encoding> E
1185 static bool ParseExprPrimary(State *state) {
1186   State copy = *state;
1187   if (ParseOneCharToken(state, 'L') && ParseType(state) &&
1188       ParseNumber(state, NULL) &&
1189       ParseOneCharToken(state, 'E')) {
1190     return true;
1191   }
1192   *state = copy;
1193
1194   if (ParseOneCharToken(state, 'L') && ParseType(state) &&
1195       ParseFloatNumber(state) &&
1196       ParseOneCharToken(state, 'E')) {
1197     return true;
1198   }
1199   *state = copy;
1200
1201   if (ParseOneCharToken(state, 'L') && ParseMangledName(state) &&
1202       ParseOneCharToken(state, 'E')) {
1203     return true;
1204   }
1205   *state = copy;
1206
1207   if (ParseTwoCharToken(state, "LZ") && ParseEncoding(state) &&
1208       ParseOneCharToken(state, 'E')) {
1209     return true;
1210   }
1211   *state = copy;
1212
1213   return false;
1214 }
1215
1216 // <local-name> := Z <(function) encoding> E <(entity) name>
1217 //                 [<discriminator>]
1218 //              := Z <(function) encoding> E s [<discriminator>]
1219 static bool ParseLocalName(State *state) {
1220   State copy = *state;
1221   if (ParseOneCharToken(state, 'Z') && ParseEncoding(state) &&
1222       ParseOneCharToken(state, 'E') && MaybeAppend(state, "::") &&
1223       ParseName(state) && Optional(ParseDiscriminator(state))) {
1224     return true;
1225   }
1226   *state = copy;
1227
1228   if (ParseOneCharToken(state, 'Z') && ParseEncoding(state) &&
1229       ParseTwoCharToken(state, "Es") && Optional(ParseDiscriminator(state))) {
1230     return true;
1231   }
1232   *state = copy;
1233   return false;
1234 }
1235
1236 // <discriminator> := _ <(non-negative) number>
1237 static bool ParseDiscriminator(State *state) {
1238   State copy = *state;
1239   if (ParseOneCharToken(state, '_') && ParseNumber(state, NULL)) {
1240     return true;
1241   }
1242   *state = copy;
1243   return false;
1244 }
1245
1246 // <substitution> ::= S_
1247 //                ::= S <seq-id> _
1248 //                ::= St, etc.
1249 static bool ParseSubstitution(State *state) {
1250   if (ParseTwoCharToken(state, "S_")) {
1251     MaybeAppend(state, "?");  // We don't support substitutions.
1252     return true;
1253   }
1254
1255   State copy = *state;
1256   if (ParseOneCharToken(state, 'S') && ParseSeqId(state) &&
1257       ParseOneCharToken(state, '_')) {
1258     MaybeAppend(state, "?");  // We don't support substitutions.
1259     return true;
1260   }
1261   *state = copy;
1262
1263   // Expand abbreviations like "St" => "std".
1264   if (ParseOneCharToken(state, 'S')) {
1265     const AbbrevPair *p;
1266     for (p = kSubstitutionList; p->abbrev != NULL; ++p) {
1267       if (state->mangled_cur[0] == p->abbrev[1]) {
1268         MaybeAppend(state, "std");
1269         if (p->real_name[0] != '\0') {
1270           MaybeAppend(state, "::");
1271           MaybeAppend(state, p->real_name);
1272         }
1273         ++state->mangled_cur;
1274         return true;
1275       }
1276     }
1277   }
1278   *state = copy;
1279   return false;
1280 }
1281
1282 // Parse <mangled-name>, optionally followed by either a function-clone suffix
1283 // or version suffix.  Returns true only if all of "mangled_cur" was consumed.
1284 static bool ParseTopLevelMangledName(State *state) {
1285   if (ParseMangledName(state)) {
1286     if (state->mangled_cur[0] != '\0') {
1287       // Drop trailing function clone suffix, if any.
1288       if (IsFunctionCloneSuffix(state->mangled_cur)) {
1289         return true;
1290       }
1291       // Append trailing version suffix if any.
1292       // ex. _Z3foo@@GLIBCXX_3.4
1293       if (state->mangled_cur[0] == '@') {
1294         MaybeAppend(state, state->mangled_cur);
1295         return true;
1296       }
1297       return false;  // Unconsumed suffix.
1298     }
1299     return true;
1300   }
1301   return false;
1302 }
1303 #endif
1304
1305 // The demangler entry point.
1306 bool Demangle(const char *mangled, char *out, int out_size) {
1307 #if defined(OS_WINDOWS)
1308   // When built with incremental linking, the Windows debugger
1309   // library provides a more complicated `Symbol->Name` with the
1310   // Incremental Linking Table offset, which looks like
1311   // `@ILT+1105(?func@Foo@@SAXH@Z)`. However, the demangler expects
1312   // only the mangled symbol, `?func@Foo@@SAXH@Z`. Fortunately, the
1313   // mangled symbol is guaranteed not to have parentheses,
1314   // so we search for `(` and extract up to `)`.
1315   //
1316   // Since we may be in a signal handler here, we cannot use `std::string`.
1317   char buffer[1024];  // Big enough for a sane symbol.
1318   const char *lparen = strchr(mangled, '(');
1319   if (lparen) {
1320     // Extract the string `(?...)`
1321     const char *rparen = strchr(lparen, ')');
1322     size_t length = rparen - lparen - 1;
1323     strncpy(buffer, lparen + 1, length);
1324     buffer[length] = '\0';
1325     mangled = buffer;
1326   } // Else the symbol wasn't inside a set of parentheses
1327   // We use the ANSI version to ensure the string type is always `char *`.
1328   return UnDecorateSymbolName(mangled, out, out_size, UNDNAME_COMPLETE);
1329 #else
1330   State state;
1331   InitState(&state, mangled, out, out_size);
1332   return ParseTopLevelMangledName(&state) && !state.overflowed;
1333 #endif
1334 }
1335
1336 _END_GOOGLE_NAMESPACE_