chromium/base/third_party/symbolize/demangle.cc

// Copyright (c) 2006, Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// Author: Satoru Takabayashi
//
// For reference check out:
// http://itanium-cxx-abi.github.io/cxx-abi/abi.html#mangling
//
// Note that we only have partial C++0x support yet.

#include "demangle.h"

#if defined(GLOG_OS_WINDOWS)
#include <dbghelp.h>
#else
#include <cstdint>
#include <cstdio>
#include <limits>
#endif

_START_GOOGLE_NAMESPACE_

#if !defined(GLOG_OS_WINDOWS)
AbbrevPair;

// List of operators from Itanium C++ ABI.
static const AbbrevPair kOperatorList[] = …;

// List of builtin types from Itanium C++ ABI.
//
// Invariant: only one- or two-character type abbreviations here.
static const AbbrevPair kBuiltinTypeList[] = …;

// List of substitutions Itanium C++ ABI.
static const AbbrevPair kSubstitutionList[] = …;

// State needed for demangling.  This struct is copied in almost every stack
// frame, so every byte counts.
ParseState;

static_assert …;

// One-off state for demangling that's not subject to backtracking -- either
// constant data, data that's intentionally immune to backtracking (steps), or
// data that would never be changed by backtracking anyway (recursion_depth).
//
// Only one copy of this exists for each call to Demangle, so the size of this
// struct is nearly inconsequential.
State;

namespace {
// Prevent deep recursion / stack exhaustion.
// Also prevent unbounded handling of complex inputs.
class ComplexityGuard { … };
}  // namespace

// We don't use strlen() in libc since it's not guaranteed to be async
// signal safe.
static size_t StrLen(const char *str) { … }

// Returns true if "str" has at least "n" characters remaining.
static bool AtLeastNumCharsRemaining(const char* str, size_t n) { … }

// Returns true if "str" has "prefix" as a prefix.
static bool StrPrefix(const char *str, const char *prefix) { … }

static void InitState(State* state,
                      const char* mangled,
                      char* out,
                      size_t out_size) { … }

static inline const char* RemainingInput(State* state) { … }

// Returns true and advances "mangled_idx" if we find "one_char_token"
// at "mangled_idx" position.  It is assumed that "one_char_token" does
// not contain '\0'.
static bool ParseOneCharToken(State *state, const char one_char_token) { … }

// Returns true and advances "mangled_cur" if we find "two_char_token"
// at "mangled_cur" position.  It is assumed that "two_char_token" does
// not contain '\0'.
static bool ParseTwoCharToken(State *state, const char *two_char_token) { … }

// Returns true and advances "mangled_cur" if we find any character in
// "char_class" at "mangled_cur" position.
static bool ParseCharClass(State *state, const char *char_class) { … }

static bool ParseDigit(State* state, int* digit) { … }

// This function is used for handling an optional non-terminal.
static bool Optional(bool /*status*/) { … }

// This function is used for handling <non-terminal>+ syntax.
ParseFunc;
static bool OneOrMore(ParseFunc parse_func, State *state) { … }

// This function is used for handling <non-terminal>* syntax. The function
// always returns true and must be followed by a termination token or a
// terminating sequence not handled by parse_func (e.g.
// ParseOneCharToken(state, 'E')).
static bool ZeroOrMore(ParseFunc parse_func, State *state) { … }

// Append "str" at "out_cur_idx".  If there is an overflow, out_cur_idx is
// set to out_end_idx+1.  The output string is ensured to
// always terminate with '\0' as long as there is no overflow.
static void Append(State* state, const char* const str, const size_t length) { … }

// We don't use equivalents in libc to avoid locale issues.
static bool IsLower(char c) { … }

static bool IsAlpha(char c) { … }

static bool IsDigit(char c) { … }

// Returns true if "str" is a function clone suffix.  These suffixes are used
// by GCC 4.5.x and later versions (and our locally-modified version of GCC
// 4.4.x) to indicate functions which have been cloned during optimization.
// We treat any sequence (.<alpha>+.<digit>+)+ as a function clone suffix.
// Additionally, '_' is allowed along with the alphanumeric sequence.
static bool IsFunctionCloneSuffix(const char *str) { … }

static bool EndsWith(State* state, const char chr) { … }

// Append "str" with some tweaks, iff "append" state is true.
static void MaybeAppendWithLength(State* state,
                                  const char* const str,
                                  const size_t length) { … }

// Appends a positive decimal number to the output if appending is enabled.
static bool MaybeAppendDecimal(State* state, int val) { … }

// A convenient wrapper around MaybeAppendWithLength().
// Returns true so that it can be placed in "if" conditions.
static bool MaybeAppend(State* state, const char* const str) { … }

// This function is used for handling nested names.
static bool EnterNestedName(State *state) { … }

// This function is used for handling nested names.
static bool LeaveNestedName(State* state, int16_t prev_value) { … }

// Disable the append mode not to print function parameters, etc.
static bool DisableAppend(State *state) { … }

// Restore the append mode to the previous state.
static bool RestoreAppend(State *state, bool prev_value) { … }

// Increase the nest level for nested names.
static void MaybeIncreaseNestLevel(State *state) { … }

// Appends :: for nested names if necessary.
static void MaybeAppendSeparator(State *state) { … }

// Cancel the last separator if necessary.
static void MaybeCancelLastSeparator(State *state) { … }

// Returns true if the identifier of the given length pointed to by
// "mangled_cur" is anonymous namespace.
static bool IdentifierIsAnonymousNamespace(State* state, size_t length) { … }

// Forward declarations of our parsing functions.
static bool ParseMangledName(State *state);
static bool ParseEncoding(State *state);
static bool ParseName(State *state);
static bool ParseUnscopedName(State* state);
static bool ParseNestedName(State *state);
static bool ParsePrefix(State *state);
static bool ParseUnqualifiedName(State *state);
static bool ParseSourceName(State *state);
static bool ParseLocalSourceName(State *state);
static bool ParseUnnamedTypeName(State* state);
static bool ParseNumber(State *state, int *number_out);
static bool ParseFloatNumber(State *state);
static bool ParseSeqId(State *state);
static bool ParseIdentifier(State* state, size_t length);
static bool ParseOperatorName(State* state, int* arity);
static bool ParseSpecialName(State *state);
static bool ParseCallOffset(State *state);
static bool ParseNVOffset(State *state);
static bool ParseVOffset(State *state);
static bool ParseAbiTags(State* state);
static bool ParseCtorDtorName(State *state);
static bool ParseDecltype(State* state);
static bool ParseType(State *state);
static bool ParseCVQualifiers(State *state);
static bool ParseBuiltinType(State *state);
static bool ParseFunctionType(State *state);
static bool ParseBareFunctionType(State *state);
static bool ParseClassEnumType(State *state);
static bool ParseArrayType(State *state);
static bool ParsePointerToMemberType(State *state);
static bool ParseTemplateParam(State *state);
static bool ParseTemplateTemplateParam(State *state);
static bool ParseTemplateArgs(State *state);
static bool ParseTemplateArg(State *state);
static bool ParseBaseUnresolvedName(State* state);
static bool ParseUnresolvedName(State* state);
static bool ParseExpression(State *state);
static bool ParseExprPrimary(State *state);
static bool ParseExprCastValue(State* state);
static bool ParseLocalName(State *state);
static bool ParseLocalNameSuffix(State* state);
static bool ParseDiscriminator(State *state);
static bool ParseSubstitution(State* state, bool accept_std);

// Implementation note: the following code is a straightforward
// translation of the Itanium C++ ABI defined in BNF with a couple of
// exceptions.
//
// - Support GNU extensions not defined in the Itanium C++ ABI
// - <prefix> and <template-prefix> are combined to avoid infinite loop
// - Reorder patterns to shorten the code
// - Reorder patterns to give greedier functions precedence
//   We'll mark "Less greedy than" for these cases in the code
//
// Each parsing function changes the parse state and returns true on
// success, or returns false and doesn't change the parse state (note:
// the parse-steps counter increases regardless of success or failure).
// To ensure that the parse state isn't changed in the latter case, we
// save the original state before we call multiple parsing functions
// consecutively with &&, and restore it if unsuccessful.  See
// ParseEncoding() as an example of this convention.  We follow the
// convention throughout the code.
//
// Originally we tried to do demangling without following the full ABI
// syntax but it turned out we needed to follow the full syntax to
// parse complicated cases like nested template arguments.  Note that
// implementing a full-fledged demangler isn't trivial (libiberty's
// cp-demangle.c has +4300 lines).
//
// Note that (foo) in <(foo) ...> is a modifier to be ignored.
//
// Reference:
// - Itanium C++ ABI
//   <https://itanium-cxx-abi.github.io/cxx-abi/abi.html#mangling>

// <mangled-name> ::= _Z <encoding>
static bool ParseMangledName(State *state) { … }

// <encoding> ::= <(function) name> <bare-function-type>
//            ::= <(data) name>
//            ::= <special-name>
static bool ParseEncoding(State *state) { … }

// <name> ::= <nested-name>
//        ::= <unscoped-template-name> <template-args>
//        ::= <unscoped-name>
//        ::= <local-name>
static bool ParseName(State *state) { … }

// <unscoped-name> ::= <unqualified-name>
//                 ::= St <unqualified-name>
static bool ParseUnscopedName(State *state) { … }

// <ref-qualifer> ::= R // lvalue method reference qualifier
//                ::= O // rvalue method reference qualifier
static inline bool ParseRefQualifier(State* state) { … }

// <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix>
//                   <unqualified-name> E
//               ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix>
//                   <template-args> E
static bool ParseNestedName(State *state) { … }

// This part is tricky.  If we literally translate them to code, we'll
// end up infinite loop.  Hence we merge them to avoid the case.
//
// <prefix> ::= <prefix> <unqualified-name>
//          ::= <template-prefix> <template-args>
//          ::= <template-param>
//          ::= <substitution>
//          ::= # empty
// <template-prefix> ::= <prefix> <(template) unqualified-name>
//                   ::= <template-param>
//                   ::= <substitution>
static bool ParsePrefix(State *state) { … }

// <unqualified-name> ::= <operator-name> [<abi-tags>]
//                    ::= <ctor-dtor-name> [<abi-tags>]
//                    ::= <source-name> [<abi-tags>]
//                    ::= <local-source-name> [<abi-tags>]
//                    ::= <unnamed-type-name> [<abi-tags>]
//
// <local-source-name> is a GCC extension; see below.
static bool ParseUnqualifiedName(State *state) { … }

// <abi-tags> ::= <abi-tag> [<abi-tags>]
// <abi-tag>  ::= B <source-name>
static bool ParseAbiTags(State* state) { … }

// <source-name> ::= <positive length number> <identifier>
static bool ParseSourceName(State *state) { … }

// <local-source-name> ::= L <source-name> [<discriminator>]
//
// References:
//   https://gcc.gnu.org/bugzilla/show_bug.cgi?id=31775
//   https://gcc.gnu.org/viewcvs?view=rev&revision=124467
static bool ParseLocalSourceName(State *state) { … }

// <unnamed-type-name> ::= Ut [<(nonnegative) number>] _
//                     ::= <closure-type-name>
// <closure-type-name> ::= Ul <lambda-sig> E [<(nonnegative) number>] _
// <lambda-sig>        ::= <(parameter) type>+
static bool ParseUnnamedTypeName(State* state) { … }

// <number> ::= [n] <non-negative decimal integer>
// If "number_out" is non-null, then *number_out is set to the value of the
// parsed number on success.
static bool ParseNumber(State *state, int *number_out) { … }

// Floating-point literals are encoded using a fixed-length lowercase
// hexadecimal string.
static bool ParseFloatNumber(State *state) { … }

// The <seq-id> is a sequence number in base 36,
// using digits and upper case letters
static bool ParseSeqId(State *state) { … }

// <identifier> ::= <unqualified source code identifier> (of given length)
static bool ParseIdentifier(State* state, size_t length) { … }

// <operator-name> ::= nw, and other two letters cases
//                 ::= cv <type>  # (cast)
//                 ::= v  <digit> <source-name> # vendor extended operator
static bool ParseOperatorName(State* state, int* arity) { … }

// <special-name> ::= TV <type>
//                ::= TT <type>
//                ::= TI <type>
//                ::= TS <type>
//                ::= TH <type>  # thread-local
//                ::= Tc <call-offset> <call-offset> <(base) encoding>
//                ::= GV <(object) name>
//                ::= T <call-offset> <(base) encoding>
// G++ extensions:
//                ::= TC <type> <(offset) number> _ <(base) type>
//                ::= TF <type>
//                ::= TJ <type>
//                ::= GR <name>
//                ::= GA <encoding>
//                ::= Th <call-offset> <(base) encoding>
//                ::= Tv <call-offset> <(base) encoding>
//
// Note: we don't care much about them since they don't appear in
// stack traces.  The are special data.
static bool ParseSpecialName(State *state) { … }

// <call-offset> ::= h <nv-offset> _
//               ::= v <v-offset> _
static bool ParseCallOffset(State *state) { … }

// <nv-offset> ::= <(offset) number>
static bool ParseNVOffset(State *state) { … }

// <v-offset>  ::= <(offset) number> _ <(virtual offset) number>
static bool ParseVOffset(State *state) { … }

// <ctor-dtor-name> ::= C1 | C2 | C3 | CI1 <base-class-type> | CI2
// <base-class-type>
//                  ::= D0 | D1 | D2
// # GCC extensions: "unified" constructor/destructor.  See
// #
// https://github.com/gcc-mirror/gcc/blob/7ad17b583c3643bd4557f29b8391ca7ef08391f5/gcc/cp/mangle.c#L1847
//                  ::= C4 | D4
static bool ParseCtorDtorName(State *state) { … }

// <decltype> ::= Dt <expression> E  # decltype of an id-expression or class
//                                   # member access (C++0x)
//            ::= DT <expression> E  # decltype of an expression (C++0x)
static bool ParseDecltype(State* state) { … }

// <type> ::= <CV-qualifiers> <type>
//        ::= P <type>   # pointer-to
//        ::= R <type>   # reference-to
//        ::= O <type>   # rvalue reference-to (C++0x)
//        ::= C <type>   # complex pair (C 2000)
//        ::= G <type>   # imaginary (C 2000)
//        ::= U <source-name> <type>  # vendor extended type qualifier
//        ::= <builtin-type>
//        ::= <function-type>
//        ::= <class-enum-type>  # note: just an alias for <name>
//        ::= <array-type>
//        ::= <pointer-to-member-type>
//        ::= <template-template-param> <template-args>
//        ::= <template-param>
//        ::= <decltype>
//        ::= <substitution>
//        ::= Dp <type>          # pack expansion of (C++0x)
//        ::= Dv <num-elems> _   # GNU vector extension
//
static bool ParseType(State *state) { … }

// <CV-qualifiers> ::= [r] [V] [K]
// We don't allow empty <CV-qualifiers> to avoid infinite loop in
// ParseType().
static bool ParseCVQualifiers(State *state) { … }

// <builtin-type> ::= v, etc.  # single-character builtin types
//                ::= u <source-name>
//                ::= Dd, etc.  # two-character builtin types
//
// Not supported:
//                ::= DF <number> _ # _FloatN (N bits)
//
static bool ParseBuiltinType(State *state) { … }

//  <exception-spec> ::= Do                # non-throwing
//                                           exception-specification (e.g.,
//                                           noexcept, throw())
//                   ::= DO <expression> E # computed (instantiation-dependent)
//                                           noexcept
//                   ::= Dw <type>+ E      # dynamic exception specification
//                                           with instantiation-dependent types
static bool ParseExceptionSpec(State* state) { … }

// <function-type> ::= [exception-spec] F [Y] <bare-function-type> [O] E
static bool ParseFunctionType(State *state) { … }

// <bare-function-type> ::= <(signature) type>+
static bool ParseBareFunctionType(State *state) { … }

// <class-enum-type> ::= <name>
static bool ParseClassEnumType(State *state) { … }

// <array-type> ::= A <(positive dimension) number> _ <(element) type>
//              ::= A [<(dimension) expression>] _ <(element) type>
static bool ParseArrayType(State *state) { … }

// <pointer-to-member-type> ::= M <(class) type> <(member) type>
static bool ParsePointerToMemberType(State *state) { … }

// <template-param> ::= T_
//                  ::= T <parameter-2 non-negative number> _
static bool ParseTemplateParam(State *state) { … }

// <template-template-param> ::= <template-param>
//                           ::= <substitution>
static bool ParseTemplateTemplateParam(State *state) { … }

// <template-args> ::= I <template-arg>+ E
static bool ParseTemplateArgs(State *state) { … }

// <template-arg>  ::= <type>
//                 ::= <expr-primary>
//                 ::= J <template-arg>* E        # argument pack
//                 ::= X <expression> E
static bool ParseTemplateArg(State *state) { … }

// <unresolved-type> ::= <template-param> [<template-args>]
//                   ::= <decltype>
//                   ::= <substitution>
static inline bool ParseUnresolvedType(State* state) { … }

// <simple-id> ::= <source-name> [<template-args>]
static inline bool ParseSimpleId(State* state) { … }

// <base-unresolved-name> ::= <source-name> [<template-args>]
//                        ::= on <operator-name> [<template-args>]
//                        ::= dn <destructor-name>
static bool ParseBaseUnresolvedName(State* state) { … }

// <unresolved-name> ::= [gs] <base-unresolved-name>
//                   ::= sr <unresolved-type> <base-unresolved-name>
//                   ::= srN <unresolved-type> <unresolved-qualifier-level>+ E
//                         <base-unresolved-name>
//                   ::= [gs] sr <unresolved-qualifier-level>+ E
//                         <base-unresolved-name>
static bool ParseUnresolvedName(State* state) { … }

// <expression> ::= <1-ary operator-name> <expression>
//              ::= <2-ary operator-name> <expression> <expression>
//              ::= <3-ary operator-name> <expression> <expression> <expression>
//              ::= cl <expression>+ E
//              ::= cp <simple-id> <expression>* E # Clang-specific.
//              ::= cv <type> <expression>      # type (expression)
//              ::= cv <type> _ <expression>* E # type (expr-list)
//              ::= st <type>
//              ::= <template-param>
//              ::= <function-param>
//              ::= <expr-primary>
//              ::= dt <expression> <unresolved-name> # expr.name
//              ::= pt <expression> <unresolved-name> # expr->name
//              ::= sp <expression>         # argument pack expansion
//              ::= sr <type> <unqualified-name> <template-args>
//              ::= sr <type> <unqualified-name>
// <function-param> ::= fp <(top-level) CV-qualifiers> _
//                  ::= fp <(top-level) CV-qualifiers> <number> _
//                  ::= fL <number> p <(top-level) CV-qualifiers> _
//                  ::= fL <number> p <(top-level) CV-qualifiers> <number> _
static bool ParseExpression(State *state) { … }

// <expr-primary> ::= L <type> <(value) number> E
//                ::= L <type> <(value) float> E
//                ::= L <mangled-name> E
//                // A bug in g++'s C++ ABI version 2 (-fabi-version=2).
//                ::= LZ <encoding> E
//
// Warning, subtle: the "bug" LZ production above is ambiguous with the first
// production where <type> starts with <local-name>, which can lead to
// exponential backtracking in two scenarios:
//
// - When whatever follows the E in the <local-name> in the first production is
//   not a name, we backtrack the whole <encoding> and re-parse the whole thing.
//
// - When whatever follows the <local-name> in the first production is not a
//   number and this <expr-primary> may be followed by a name, we backtrack the
//   <name> and re-parse it.
//
// Moreover this ambiguity isn't always resolved -- for example, the following
// has two different parses:
//
//   _ZaaILZ4aoeuE1x1EvE
//   => operator&&<aoeu, x, E, void>
//   => operator&&<(aoeu::x)(1), void>
//
// To resolve this, we just do what GCC's demangler does, and refuse to parse
// casts to <local-name> types.
static bool ParseExprPrimary(State *state) { … }

// <number> or <float>, followed by 'E', as described above ParseExprPrimary.
static bool ParseExprCastValue(State* state) { … }

// <local-name> ::= Z <(function) encoding> E <(entity) name> [<discriminator>]
//              ::= Z <(function) encoding> E s [<discriminator>]
//
// Parsing a common prefix of these two productions together avoids an
// exponential blowup of backtracking.  Parse like:
//   <local-name> := Z <encoding> E <local-name-suffix>
//   <local-name-suffix> ::= s [<discriminator>]
//                       ::= <name> [<discriminator>]

static bool ParseLocalNameSuffix(State* state) { … }

static bool ParseLocalName(State* state) { … }

// <discriminator> := _ <(non-negative) number>
static bool ParseDiscriminator(State *state) { … }

// <substitution> ::= S_
//                ::= S <seq-id> _
//                ::= St, etc.
//
// "St" is special in that it's not valid as a standalone name, and it *is*
// allowed to precede a name without being wrapped in "N...E".  This means that
// if we accept it on its own, we can accept "St1a" and try to parse
// template-args, then fail and backtrack, accept "St" on its own, then "1a" as
// an unqualified name and re-parse the same template-args.  To block this
// exponential backtracking, we disable it with 'accept_std=false' in
// problematic contexts.
static bool ParseSubstitution(State* state, bool accept_std) { … }

// Parse <mangled-name>, optionally followed by either a function-clone suffix
// or version suffix.  Returns true only if all of "mangled_cur" was consumed.
static bool ParseTopLevelMangledName(State *state) { … }

static bool Overflowed(const State* state) { … }
#endif

// The demangler entry point.
bool Demangle(const char* mangled, char* out, size_t out_size) { … }

_END_GOOGLE_NAMESPACE_