gcc/cp/mangle.c

   1 /* Name mangling for the 3.0 C++ ABI.
   2    Copyright (C) 2000-2014 Free Software Foundation, Inc.
   3    Written by Alex Samuel <samuel@codesourcery.com>
   4
   5    This file is part of GCC.
   6
   7    GCC is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3, or (at your option)
  10    any later version.
  11
  12    GCC is distributed in the hope that it will be useful, but
  13    WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15    General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* This file implements mangling of C++ names according to the IA64
  22    C++ ABI specification.  A mangled name encodes a function or
  23    variable's name, scope, type, and/or template arguments into a text
  24    identifier.  This identifier is used as the function's or
  25    variable's linkage name, to preserve compatibility between C++'s
  26    language features (templates, scoping, and overloading) and C
  27    linkers.
  28
  29    Additionally, g++ uses mangled names internally.  To support this,
  30    mangling of types is allowed, even though the mangled name of a
  31    type should not appear by itself as an exported name.  Ditto for
  32    uninstantiated templates.
  33
  34    The primary entry point for this module is mangle_decl, which
  35    returns an identifier containing the mangled name for a decl.
  36    Additional entry points are provided to build mangled names of
  37    particular constructs when the appropriate decl for that construct
  38    is not available.  These are:
  39
  40      mangle_typeinfo_for_type:          typeinfo data
  41      mangle_typeinfo_string_for_type:   typeinfo type name
  42      mangle_vtbl_for_type:              virtual table data
  43      mangle_vtt_for_type:               VTT data
  44      mangle_ctor_vtbl_for_type:         `C-in-B' constructor virtual table data
  45      mangle_thunk:                      thunk function or entry  */
  46
  47 #include "config.h"
  48 #include "system.h"
  49 #include "coretypes.h"
  50 #include "tm.h"
  51 #include "tree.h"
  52 #include "stor-layout.h"
  53 #include "stringpool.h"
  54 #include "tm_p.h"
  55 #include "cp-tree.h"
  56 #include "obstack.h"
  57 #include "flags.h"
  58 #include "target.h"
  59 #include "cgraph.h"
  60 #include "wide-int.h"
  61
  62 /* Debugging support.  */
  63
  64 /* Define DEBUG_MANGLE to enable very verbose trace messages.  */
  65 #ifndef DEBUG_MANGLE
  66 #define DEBUG_MANGLE 0
  67 #endif
  68
  69 /* Macros for tracing the write_* functions.  */
  70 #if DEBUG_MANGLE
  71 # define MANGLE_TRACE(FN, INPUT) \
  72   fprintf (stderr, "  %-24s: %-24s\n", (FN), (INPUT))
  73 # define MANGLE_TRACE_TREE(FN, NODE) \
  74   fprintf (stderr, "  %-24s: %-24s (%p)\n", \
  75            (FN), get_tree_code_name (TREE_CODE (NODE)), (void *) (NODE))
  76 #else
  77 # define MANGLE_TRACE(FN, INPUT)
  78 # define MANGLE_TRACE_TREE(FN, NODE)
  79 #endif
  80
  81 /* Nonzero if NODE is a class template-id.  We can't rely on
  82    CLASSTYPE_USE_TEMPLATE here because of tricky bugs in the parser
  83    that hard to distinguish A<T> from A, where A<T> is the type as
  84    instantiated outside of the template, and A is the type used
  85    without parameters inside the template.  */
  86 #define CLASSTYPE_TEMPLATE_ID_P(NODE)                                   \
  87   (TYPE_LANG_SPECIFIC (NODE) != NULL                                    \
  88    && (TREE_CODE (NODE) == BOUND_TEMPLATE_TEMPLATE_PARM                 \
  89        || (CLASSTYPE_TEMPLATE_INFO (NODE) != NULL                       \
  90            && (PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (NODE))))))
  91
  92 /* Things we only need one of.  This module is not reentrant.  */
  93 typedef struct GTY(()) globals {
  94   /* An array of the current substitution candidates, in the order
  95      we've seen them.  */
  96   vec<tree, va_gc> *substitutions;
  97
  98   /* The entity that is being mangled.  */
  99   tree GTY ((skip)) entity;
 100
 101   /* How many parameter scopes we are inside.  */
 102   int parm_depth;
 103
 104   /* True if the mangling will be different in a future version of the
 105      ABI.  */
 106   bool need_abi_warning;
 107 } globals;
 108
 109 static GTY (()) globals G;
 110
 111 /* The obstack on which we build mangled names.  */
 112 static struct obstack *mangle_obstack;
 113
 114 /* The obstack on which we build mangled names that are not going to
 115    be IDENTIFIER_NODEs.  */
 116 static struct obstack name_obstack;
 117
 118 /* The first object on the name_obstack; we use this to free memory
 119    allocated on the name_obstack.  */
 120 static void *name_base;
 121
 122 /* Indices into subst_identifiers.  These are identifiers used in
 123    special substitution rules.  */
 124 typedef enum
 125 {
 126   SUBID_ALLOCATOR,
 127   SUBID_BASIC_STRING,
 128   SUBID_CHAR_TRAITS,
 129   SUBID_BASIC_ISTREAM,
 130   SUBID_BASIC_OSTREAM,
 131   SUBID_BASIC_IOSTREAM,
 132   SUBID_MAX
 133 }
 134 substitution_identifier_index_t;
 135
 136 /* For quick substitution checks, look up these common identifiers
 137    once only.  */
 138 static GTY(()) tree subst_identifiers[SUBID_MAX];
 139
 140 /* Single-letter codes for builtin integer types, defined in
 141    <builtin-type>.  These are indexed by integer_type_kind values.  */
 142 static const char
 143 integer_type_codes[itk_none] =
 144 {
 145   'c',  /* itk_char */
 146   'a',  /* itk_signed_char */
 147   'h',  /* itk_unsigned_char */
 148   's',  /* itk_short */
 149   't',  /* itk_unsigned_short */
 150   'i',  /* itk_int */
 151   'j',  /* itk_unsigned_int */
 152   'l',  /* itk_long */
 153   'm',  /* itk_unsigned_long */
 154   'x',  /* itk_long_long */
 155   'y',  /* itk_unsigned_long_long */
 156   'n',  /* itk_int128 */
 157   'o',  /* itk_unsigned_int128  */
 158 };
 159
 160 static int decl_is_template_id (const tree, tree* const);
 161
 162 /* Functions for handling substitutions.  */
 163
 164 static inline tree canonicalize_for_substitution (tree);
 165 static void add_substitution (tree);
 166 static inline int is_std_substitution (const tree,
 167                                        const substitution_identifier_index_t);
 168 static inline int is_std_substitution_char (const tree,
 169                                             const substitution_identifier_index_t);
 170 static int find_substitution (tree);
 171 static void mangle_call_offset (const tree, const tree);
 172
 173 /* Functions for emitting mangled representations of things.  */
 174
 175 static void write_mangled_name (const tree, bool);
 176 static void write_encoding (const tree);
 177 static void write_name (tree, const int);
 178 static void write_abi_tags (tree);
 179 static void write_unscoped_name (const tree);
 180 static void write_unscoped_template_name (const tree);
 181 static void write_nested_name (const tree);
 182 static void write_prefix (const tree);
 183 static void write_template_prefix (const tree);
 184 static void write_unqualified_name (tree);
 185 static void write_conversion_operator_name (const tree);
 186 static void write_source_name (tree);
 187 static void write_literal_operator_name (tree);
 188 static void write_unnamed_type_name (const tree);
 189 static void write_closure_type_name (const tree);
 190 static int hwint_to_ascii (unsigned HOST_WIDE_INT, const unsigned int, char *,
 191                            const unsigned int);
 192 static void write_number (unsigned HOST_WIDE_INT, const int,
 193                           const unsigned int);
 194 static void write_compact_number (int num);
 195 static void write_integer_cst (const tree);
 196 static void write_real_cst (const tree);
 197 static void write_identifier (const char *);
 198 static void write_special_name_constructor (const tree);
 199 static void write_special_name_destructor (const tree);
 200 static void write_type (tree);
 201 static int write_CV_qualifiers_for_type (const tree);
 202 static void write_builtin_type (tree);
 203 static void write_function_type (const tree);
 204 static void write_bare_function_type (const tree, const int, const tree);
 205 static void write_method_parms (tree, const int, const tree);
 206 static void write_class_enum_type (const tree);
 207 static void write_template_args (tree);
 208 static void write_expression (tree);
 209 static void write_template_arg_literal (const tree);
 210 static void write_template_arg (tree);
 211 static void write_template_template_arg (const tree);
 212 static void write_array_type (const tree);
 213 static void write_pointer_to_member_type (const tree);
 214 static void write_template_param (const tree);
 215 static void write_template_template_param (const tree);
 216 static void write_substitution (const int);
 217 static int discriminator_for_local_entity (tree);
 218 static int discriminator_for_string_literal (tree, tree);
 219 static void write_discriminator (const int);
 220 static void write_local_name (tree, const tree, const tree);
 221 static void dump_substitution_candidates (void);
 222 static tree mangle_decl_string (const tree);
 223 static int local_class_index (tree);
 224
 225 /* Control functions.  */
 226
 227 static inline void start_mangling (const tree);
 228 static tree mangle_special_for_type (const tree, const char *);
 229
 230 /* Foreign language functions.  */
 231
 232 static void write_java_integer_type_codes (const tree);
 233
 234 /* Append a single character to the end of the mangled
 235    representation.  */
 236 #define write_char(CHAR)                                                \
 237   obstack_1grow (mangle_obstack, (CHAR))
 238
 239 /* Append a sized buffer to the end of the mangled representation.  */
 240 #define write_chars(CHAR, LEN)                                          \
 241   obstack_grow (mangle_obstack, (CHAR), (LEN))
 242
 243 /* Append a NUL-terminated string to the end of the mangled
 244    representation.  */
 245 #define write_string(STRING)                                            \
 246   obstack_grow (mangle_obstack, (STRING), strlen (STRING))
 247
 248 /* Nonzero if NODE1 and NODE2 are both TREE_LIST nodes and have the
 249    same purpose (context, which may be a type) and value (template
 250    decl).  See write_template_prefix for more information on what this
 251    is used for.  */
 252 #define NESTED_TEMPLATE_MATCH(NODE1, NODE2)                             \
 253   (TREE_CODE (NODE1) == TREE_LIST                                       \
 254    && TREE_CODE (NODE2) == TREE_LIST                                    \
 255    && ((TYPE_P (TREE_PURPOSE (NODE1))                                   \
 256         && same_type_p (TREE_PURPOSE (NODE1), TREE_PURPOSE (NODE2)))    \
 257        || TREE_PURPOSE (NODE1) == TREE_PURPOSE (NODE2))                 \
 258    && TREE_VALUE (NODE1) == TREE_VALUE (NODE2))
 259
 260 /* Write out an unsigned quantity in base 10.  */
 261 #define write_unsigned_number(NUMBER)                                   \
 262   write_number ((NUMBER), /*unsigned_p=*/1, 10)
 263
 264 /* If DECL is a template instance, return nonzero and, if
 265    TEMPLATE_INFO is non-NULL, set *TEMPLATE_INFO to its template info.
 266    Otherwise return zero.  */
 267
 268 static int
 269 decl_is_template_id (const tree decl, tree* const template_info)
 270 {
 271   if (TREE_CODE (decl) == TYPE_DECL)
 272     {
 273       /* TYPE_DECLs are handled specially.  Look at its type to decide
 274          if this is a template instantiation.  */
 275       const tree type = TREE_TYPE (decl);
 276
 277       if (CLASS_TYPE_P (type) && CLASSTYPE_TEMPLATE_ID_P (type))
 278         {
 279           if (template_info != NULL)
 280             /* For a templated TYPE_DECL, the template info is hanging
 281                off the type.  */
 282             *template_info = TYPE_TEMPLATE_INFO (type);
 283           return 1;
 284         }
 285     }
 286   else
 287     {
 288       /* Check if this is a primary template.  */
 289       if (DECL_LANG_SPECIFIC (decl) != NULL
 290           && DECL_USE_TEMPLATE (decl)
 291           && PRIMARY_TEMPLATE_P (DECL_TI_TEMPLATE (decl))
 292           && TREE_CODE (decl) != TEMPLATE_DECL)
 293         {
 294           if (template_info != NULL)
 295             /* For most templated decls, the template info is hanging
 296                off the decl.  */
 297             *template_info = DECL_TEMPLATE_INFO (decl);
 298           return 1;
 299         }
 300     }
 301
 302   /* It's not a template id.  */
 303   return 0;
 304 }
 305
 306 /* Produce debugging output of current substitution candidates.  */
 307
 308 static void
 309 dump_substitution_candidates (void)
 310 {
 311   unsigned i;
 312   tree el;
 313
 314   fprintf (stderr, "  ++ substitutions  ");
 315   FOR_EACH_VEC_ELT (*G.substitutions, i, el)
 316     {
 317       const char *name = "???";
 318
 319       if (i > 0)
 320         fprintf (stderr, "                    ");
 321       if (DECL_P (el))
 322         name = IDENTIFIER_POINTER (DECL_NAME (el));
 323       else if (TREE_CODE (el) == TREE_LIST)
 324         name = IDENTIFIER_POINTER (DECL_NAME (TREE_VALUE (el)));
 325       else if (TYPE_NAME (el))
 326         name = TYPE_NAME_STRING (el);
 327       fprintf (stderr, " S%d_ = ", i - 1);
 328       if (TYPE_P (el) &&
 329           (CP_TYPE_RESTRICT_P (el)
 330            || CP_TYPE_VOLATILE_P (el)
 331            || CP_TYPE_CONST_P (el)))
 332         fprintf (stderr, "CV-");
 333       fprintf (stderr, "%s (%s at %p)\n",
 334                name, get_tree_code_name (TREE_CODE (el)), (void *) el);
 335     }
 336 }
 337
 338 /* Both decls and types can be substitution candidates, but sometimes
 339    they refer to the same thing.  For instance, a TYPE_DECL and
 340    RECORD_TYPE for the same class refer to the same thing, and should
 341    be treated accordingly in substitutions.  This function returns a
 342    canonicalized tree node representing NODE that is used when adding
 343    and substitution candidates and finding matches.  */
 344
 345 static inline tree
 346 canonicalize_for_substitution (tree node)
 347 {
 348   /* For a TYPE_DECL, use the type instead.  */
 349   if (TREE_CODE (node) == TYPE_DECL)
 350     node = TREE_TYPE (node);
 351   if (TYPE_P (node)
 352       && TYPE_CANONICAL (node) != node
 353       && TYPE_MAIN_VARIANT (node) != node)
 354     {
 355       tree orig = node;
 356       /* Here we want to strip the topmost typedef only.
 357          We need to do that so is_std_substitution can do proper
 358          name matching.  */
 359       if (TREE_CODE (node) == FUNCTION_TYPE)
 360         /* Use build_qualified_type and TYPE_QUALS here to preserve
 361            the old buggy mangling of attribute noreturn with abi<5.  */
 362         node = build_qualified_type (TYPE_MAIN_VARIANT (node),
 363                                      TYPE_QUALS (node));
 364       else
 365         node = cp_build_qualified_type (TYPE_MAIN_VARIANT (node),
 366                                         cp_type_quals (node));
 367       if (TREE_CODE (node) == FUNCTION_TYPE
 368           || TREE_CODE (node) == METHOD_TYPE)
 369         node = build_ref_qualified_type (node, type_memfn_rqual (orig));
 370     }
 371   return node;
 372 }
 373
 374 /* Add NODE as a substitution candidate.  NODE must not already be on
 375    the list of candidates.  */
 376
 377 static void
 378 add_substitution (tree node)
 379 {
 380   tree c;
 381
 382   if (DEBUG_MANGLE)
 383     fprintf (stderr, "  ++ add_substitution (%s at %10p)\n",
 384              get_tree_code_name (TREE_CODE (node)), (void *) node);
 385
 386   /* Get the canonicalized substitution candidate for NODE.  */
 387   c = canonicalize_for_substitution (node);
 388   if (DEBUG_MANGLE && c != node)
 389     fprintf (stderr, "  ++ using candidate (%s at %10p)\n",
 390              get_tree_code_name (TREE_CODE (node)), (void *) node);
 391   node = c;
 392
 393 #if ENABLE_CHECKING
 394   /* Make sure NODE isn't already a candidate.  */
 395   {
 396     int i;
 397     tree candidate;
 398
 399     FOR_EACH_VEC_SAFE_ELT (G.substitutions, i, candidate)
 400       {
 401         gcc_assert (!(DECL_P (node) && node == candidate));
 402         gcc_assert (!(TYPE_P (node) && TYPE_P (candidate)
 403                       && same_type_p (node, candidate)));
 404       }
 405   }
 406 #endif /* ENABLE_CHECKING */
 407
 408   /* Put the decl onto the varray of substitution candidates.  */
 409   vec_safe_push (G.substitutions, node);
 410
 411   if (DEBUG_MANGLE)
 412     dump_substitution_candidates ();
 413 }
 414
 415 /* Helper function for find_substitution.  Returns nonzero if NODE,
 416    which may be a decl or a CLASS_TYPE, is a template-id with template
 417    name of substitution_index[INDEX] in the ::std namespace.  */
 418
 419 static inline int
 420 is_std_substitution (const tree node,
 421                      const substitution_identifier_index_t index)
 422 {
 423   tree type = NULL;
 424   tree decl = NULL;
 425
 426   if (DECL_P (node))
 427     {
 428       type = TREE_TYPE (node);
 429       decl = node;
 430     }
 431   else if (CLASS_TYPE_P (node))
 432     {
 433       type = node;
 434       decl = TYPE_NAME (node);
 435     }
 436   else
 437     /* These are not the droids you're looking for.  */
 438     return 0;
 439
 440   return (DECL_NAMESPACE_STD_P (CP_DECL_CONTEXT (decl))
 441           && TYPE_LANG_SPECIFIC (type)
 442           && TYPE_TEMPLATE_INFO (type)
 443           && (DECL_NAME (TYPE_TI_TEMPLATE (type))
 444               == subst_identifiers[index]));
 445 }
 446
 447 /* Helper function for find_substitution.  Returns nonzero if NODE,
 448    which may be a decl or a CLASS_TYPE, is the template-id
 449    ::std::identifier<char>, where identifier is
 450    substitution_index[INDEX].  */
 451
 452 static inline int
 453 is_std_substitution_char (const tree node,
 454                           const substitution_identifier_index_t index)
 455 {
 456   tree args;
 457   /* Check NODE's name is ::std::identifier.  */
 458   if (!is_std_substitution (node, index))
 459     return 0;
 460   /* Figure out its template args.  */
 461   if (DECL_P (node))
 462     args = DECL_TI_ARGS (node);
 463   else if (CLASS_TYPE_P (node))
 464     args = CLASSTYPE_TI_ARGS (node);
 465   else
 466     /* Oops, not a template.  */
 467     return 0;
 468   /* NODE's template arg list should be <char>.  */
 469   return
 470     TREE_VEC_LENGTH (args) == 1
 471     && TREE_VEC_ELT (args, 0) == char_type_node;
 472 }
 473
 474 /* Check whether a substitution should be used to represent NODE in
 475    the mangling.
 476
 477    First, check standard special-case substitutions.
 478
 479      <substitution> ::= St
 480          # ::std
 481
 482                     ::= Sa
 483          # ::std::allocator
 484
 485                     ::= Sb
 486          # ::std::basic_string
 487
 488                     ::= Ss
 489          # ::std::basic_string<char,
 490                                ::std::char_traits<char>,
 491                                ::std::allocator<char> >
 492
 493                     ::= Si
 494          # ::std::basic_istream<char, ::std::char_traits<char> >
 495
 496                     ::= So
 497          # ::std::basic_ostream<char, ::std::char_traits<char> >
 498
 499                     ::= Sd
 500          # ::std::basic_iostream<char, ::std::char_traits<char> >
 501
 502    Then examine the stack of currently available substitution
 503    candidates for entities appearing earlier in the same mangling
 504
 505    If a substitution is found, write its mangled representation and
 506    return nonzero.  If none is found, just return zero.  */
 507
 508 static int
 509 find_substitution (tree node)
 510 {
 511   int i;
 512   const int size = vec_safe_length (G.substitutions);
 513   tree decl;
 514   tree type;
 515
 516   if (DEBUG_MANGLE)
 517     fprintf (stderr, "  ++ find_substitution (%s at %p)\n",
 518              get_tree_code_name (TREE_CODE (node)), (void *) node);
 519
 520   /* Obtain the canonicalized substitution representation for NODE.
 521      This is what we'll compare against.  */
 522   node = canonicalize_for_substitution (node);
 523
 524   /* Check for builtin substitutions.  */
 525
 526   decl = TYPE_P (node) ? TYPE_NAME (node) : node;
 527   type = TYPE_P (node) ? node : TREE_TYPE (node);
 528
 529   /* Check for std::allocator.  */
 530   if (decl
 531       && is_std_substitution (decl, SUBID_ALLOCATOR)
 532       && !CLASSTYPE_USE_TEMPLATE (TREE_TYPE (decl)))
 533     {
 534       write_string ("Sa");
 535       return 1;
 536     }
 537
 538   /* Check for std::basic_string.  */
 539   if (decl && is_std_substitution (decl, SUBID_BASIC_STRING))
 540     {
 541       if (TYPE_P (node))
 542         {
 543           /* If this is a type (i.e. a fully-qualified template-id),
 544              check for
 545                  std::basic_string <char,
 546                                     std::char_traits<char>,
 547                                     std::allocator<char> > .  */
 548           if (cp_type_quals (type) == TYPE_UNQUALIFIED
 549               && CLASSTYPE_USE_TEMPLATE (type))
 550             {
 551               tree args = CLASSTYPE_TI_ARGS (type);
 552               if (TREE_VEC_LENGTH (args) == 3
 553                   && same_type_p (TREE_VEC_ELT (args, 0), char_type_node)
 554                   && is_std_substitution_char (TREE_VEC_ELT (args, 1),
 555                                                SUBID_CHAR_TRAITS)
 556                   && is_std_substitution_char (TREE_VEC_ELT (args, 2),
 557                                                SUBID_ALLOCATOR))
 558                 {
 559                   write_string ("Ss");
 560                   return 1;
 561                 }
 562             }
 563         }
 564       else
 565         /* Substitute for the template name only if this isn't a type.  */
 566         {
 567           write_string ("Sb");
 568           return 1;
 569         }
 570     }
 571
 572   /* Check for basic_{i,o,io}stream.  */
 573   if (TYPE_P (node)
 574       && cp_type_quals (type) == TYPE_UNQUALIFIED
 575       && CLASS_TYPE_P (type)
 576       && CLASSTYPE_USE_TEMPLATE (type)
 577       && CLASSTYPE_TEMPLATE_INFO (type) != NULL)
 578     {
 579       /* First, check for the template
 580          args <char, std::char_traits<char> > .  */
 581       tree args = CLASSTYPE_TI_ARGS (type);
 582       if (TREE_VEC_LENGTH (args) == 2
 583           && TYPE_P (TREE_VEC_ELT (args, 0))
 584           && same_type_p (TREE_VEC_ELT (args, 0), char_type_node)
 585           && is_std_substitution_char (TREE_VEC_ELT (args, 1),
 586                                        SUBID_CHAR_TRAITS))
 587         {
 588           /* Got them.  Is this basic_istream?  */
 589           if (is_std_substitution (decl, SUBID_BASIC_ISTREAM))
 590             {
 591               write_string ("Si");
 592               return 1;
 593             }
 594           /* Or basic_ostream?  */
 595           else if (is_std_substitution (decl, SUBID_BASIC_OSTREAM))
 596             {
 597               write_string ("So");
 598               return 1;
 599             }
 600           /* Or basic_iostream?  */
 601           else if (is_std_substitution (decl, SUBID_BASIC_IOSTREAM))
 602             {
 603               write_string ("Sd");
 604               return 1;
 605             }
 606         }
 607     }
 608
 609   /* Check for namespace std.  */
 610   if (decl && DECL_NAMESPACE_STD_P (decl))
 611     {
 612       write_string ("St");
 613       return 1;
 614     }
 615
 616   /* Now check the list of available substitutions for this mangling
 617      operation.  */
 618   for (i = 0; i < size; ++i)
 619     {
 620       tree candidate = (*G.substitutions)[i];
 621       /* NODE is a matched to a candidate if it's the same decl node or
 622          if it's the same type.  */
 623       if (decl == candidate
 624           || (TYPE_P (candidate) && type && TYPE_P (node)
 625               && same_type_p (type, candidate))
 626           || NESTED_TEMPLATE_MATCH (node, candidate))
 627         {
 628           write_substitution (i);
 629           return 1;
 630         }
 631     }
 632
 633   /* No substitution found.  */
 634   return 0;
 635 }
 636
 637
 638 /* TOP_LEVEL is true, if this is being called at outermost level of
 639   mangling. It should be false when mangling a decl appearing in an
 640   expression within some other mangling.
 641
 642   <mangled-name>      ::= _Z <encoding>  */
 643
 644 static void
 645 write_mangled_name (const tree decl, bool top_level)
 646 {
 647   MANGLE_TRACE_TREE ("mangled-name", decl);
 648
 649   if (/* The names of `extern "C"' functions are not mangled.  */
 650       DECL_EXTERN_C_FUNCTION_P (decl)
 651       /* But overloaded operator names *are* mangled.  */
 652       && !DECL_OVERLOADED_OPERATOR_P (decl))
 653     {
 654     unmangled_name:;
 655
 656       if (top_level)
 657         write_string (IDENTIFIER_POINTER (DECL_NAME (decl)));
 658       else
 659         {
 660           /* The standard notes: "The <encoding> of an extern "C"
 661              function is treated like global-scope data, i.e. as its
 662              <source-name> without a type."  We cannot write
 663              overloaded operators that way though, because it contains
 664              characters invalid in assembler.  */
 665           write_string ("_Z");
 666           write_source_name (DECL_NAME (decl));
 667         }
 668     }
 669   else if (VAR_P (decl)
 670            /* The names of non-static global variables aren't mangled.  */
 671            && DECL_EXTERNAL_LINKAGE_P (decl)
 672            && (CP_DECL_CONTEXT (decl) == global_namespace
 673                /* And neither are `extern "C"' variables.  */
 674                || DECL_EXTERN_C_P (decl)))
 675     {
 676       goto unmangled_name;
 677     }
 678   else
 679     {
 680       write_string ("_Z");
 681       write_encoding (decl);
 682     }
 683 }
 684
 685 /*   <encoding>         ::= <function name> <bare-function-type>
 686                         ::= <data name>  */
 687
 688 static void
 689 write_encoding (const tree decl)
 690 {
 691   MANGLE_TRACE_TREE ("encoding", decl);
 692
 693   if (DECL_LANG_SPECIFIC (decl) && DECL_EXTERN_C_FUNCTION_P (decl))
 694     {
 695       /* For overloaded operators write just the mangled name
 696          without arguments.  */
 697       if (DECL_OVERLOADED_OPERATOR_P (decl))
 698         write_name (decl, /*ignore_local_scope=*/0);
 699       else
 700         write_source_name (DECL_NAME (decl));
 701       return;
 702     }
 703
 704   write_name (decl, /*ignore_local_scope=*/0);
 705   if (TREE_CODE (decl) == FUNCTION_DECL)
 706     {
 707       tree fn_type;
 708       tree d;
 709
 710       if (decl_is_template_id (decl, NULL))
 711         {
 712           fn_type = get_mostly_instantiated_function_type (decl);
 713           /* FN_TYPE will not have parameter types for in-charge or
 714              VTT parameters.  Therefore, we pass NULL_TREE to
 715              write_bare_function_type -- otherwise, it will get
 716              confused about which artificial parameters to skip.  */
 717           d = NULL_TREE;
 718         }
 719       else
 720         {
 721           fn_type = TREE_TYPE (decl);
 722           d = decl;
 723         }
 724
 725       write_bare_function_type (fn_type,
 726                                 (!DECL_CONSTRUCTOR_P (decl)
 727                                  && !DECL_DESTRUCTOR_P (decl)
 728                                  && !DECL_CONV_FN_P (decl)
 729                                  && decl_is_template_id (decl, NULL)),
 730                                 d);
 731     }
 732 }
 733
 734 /* Lambdas can have a bit more context for mangling, specifically VAR_DECL
 735    or PARM_DECL context, which doesn't belong in DECL_CONTEXT.  */
 736
 737 static tree
 738 decl_mangling_context (tree decl)
 739 {
 740   tree tcontext = targetm.cxx.decl_mangling_context (decl);
 741
 742   if (tcontext != NULL_TREE)
 743     return tcontext;
 744
 745   if (TREE_CODE (decl) == TYPE_DECL
 746       && LAMBDA_TYPE_P (TREE_TYPE (decl)))
 747     {
 748       tree extra = LAMBDA_TYPE_EXTRA_SCOPE (TREE_TYPE (decl));
 749       if (extra)
 750         return extra;
 751     }
 752     else if (TREE_CODE (decl) == TYPE_DECL
 753              && TREE_CODE (TREE_TYPE (decl)) == TEMPLATE_TYPE_PARM)
 754      /* template type parms have no mangling context.  */
 755       return NULL_TREE;
 756   return CP_DECL_CONTEXT (decl);
 757 }
 758
 759 /* <name> ::= <unscoped-name>
 760           ::= <unscoped-template-name> <template-args>
 761           ::= <nested-name>
 762           ::= <local-name>
 763
 764    If IGNORE_LOCAL_SCOPE is nonzero, this production of <name> is
 765    called from <local-name>, which mangles the enclosing scope
 766    elsewhere and then uses this function to mangle just the part
 767    underneath the function scope.  So don't use the <local-name>
 768    production, to avoid an infinite recursion.  */
 769
 770 static void
 771 write_name (tree decl, const int ignore_local_scope)
 772 {
 773   tree context;
 774
 775   MANGLE_TRACE_TREE ("name", decl);
 776
 777   if (TREE_CODE (decl) == TYPE_DECL)
 778     {
 779       /* In case this is a typedef, fish out the corresponding
 780          TYPE_DECL for the main variant.  */
 781       decl = TYPE_NAME (TYPE_MAIN_VARIANT (TREE_TYPE (decl)));
 782     }
 783
 784   context = decl_mangling_context (decl);
 785
 786   gcc_assert (context != NULL_TREE);
 787
 788   if (abi_version_crosses (7)
 789       && ignore_local_scope
 790       && TREE_CODE (context) == PARM_DECL)
 791     G.need_abi_warning = 1;
 792
 793   /* A decl in :: or ::std scope is treated specially.  The former is
 794      mangled using <unscoped-name> or <unscoped-template-name>, the
 795      latter with a special substitution.  Also, a name that is
 796      directly in a local function scope is also mangled with
 797      <unscoped-name> rather than a full <nested-name>.  */
 798   if (context == global_namespace
 799       || DECL_NAMESPACE_STD_P (context)
 800       || (ignore_local_scope
 801           && (TREE_CODE (context) == FUNCTION_DECL
 802               || (abi_version_at_least (7)
 803                   && TREE_CODE (context) == PARM_DECL))))
 804     {
 805       tree template_info;
 806       /* Is this a template instance?  */
 807       if (decl_is_template_id (decl, &template_info))
 808         {
 809           /* Yes: use <unscoped-template-name>.  */
 810           write_unscoped_template_name (TI_TEMPLATE (template_info));
 811           write_template_args (TI_ARGS (template_info));
 812         }
 813       else
 814         /* Everything else gets an <unqualified-name>.  */
 815         write_unscoped_name (decl);
 816     }
 817   else
 818     {
 819       /* Handle local names, unless we asked not to (that is, invoked
 820          under <local-name>, to handle only the part of the name under
 821          the local scope).  */
 822       if (!ignore_local_scope)
 823         {
 824           /* Scan up the list of scope context, looking for a
 825              function.  If we find one, this entity is in local
 826              function scope.  local_entity tracks context one scope
 827              level down, so it will contain the element that's
 828              directly in that function's scope, either decl or one of
 829              its enclosing scopes.  */
 830           tree local_entity = decl;
 831           while (context != global_namespace)
 832             {
 833               /* Make sure we're always dealing with decls.  */
 834               if (TYPE_P (context))
 835                 context = TYPE_NAME (context);
 836               /* Is this a function?  */
 837               if (TREE_CODE (context) == FUNCTION_DECL
 838                   || TREE_CODE (context) == PARM_DECL)
 839                 {
 840                   /* Yes, we have local scope.  Use the <local-name>
 841                      production for the innermost function scope.  */
 842                   write_local_name (context, local_entity, decl);
 843                   return;
 844                 }
 845               /* Up one scope level.  */
 846               local_entity = context;
 847               context = decl_mangling_context (context);
 848             }
 849
 850           /* No local scope found?  Fall through to <nested-name>.  */
 851         }
 852
 853       /* Other decls get a <nested-name> to encode their scope.  */
 854       write_nested_name (decl);
 855     }
 856 }
 857
 858 /* <unscoped-name> ::= <unqualified-name>
 859                    ::= St <unqualified-name>   # ::std::  */
 860
 861 static void
 862 write_unscoped_name (const tree decl)
 863 {
 864   tree context = decl_mangling_context (decl);
 865
 866   MANGLE_TRACE_TREE ("unscoped-name", decl);
 867
 868   /* Is DECL in ::std?  */
 869   if (DECL_NAMESPACE_STD_P (context))
 870     {
 871       write_string ("St");
 872       write_unqualified_name (decl);
 873     }
 874   else
 875     {
 876       /* If not, it should be either in the global namespace, or directly
 877          in a local function scope.  A lambda can also be mangled in the
 878          scope of a default argument.  */
 879       gcc_assert (context == global_namespace
 880                   || TREE_CODE (context) == PARM_DECL
 881                   || TREE_CODE (context) == FUNCTION_DECL);
 882
 883       write_unqualified_name (decl);
 884     }
 885 }
 886
 887 /* <unscoped-template-name> ::= <unscoped-name>
 888                             ::= <substitution>  */
 889
 890 static void
 891 write_unscoped_template_name (const tree decl)
 892 {
 893   MANGLE_TRACE_TREE ("unscoped-template-name", decl);
 894
 895   if (find_substitution (decl))
 896     return;
 897   write_unscoped_name (decl);
 898   add_substitution (decl);
 899 }
 900
 901 /* Write the nested name, including CV-qualifiers, of DECL.
 902
 903    <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E
 904                  ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix> <template-args> E
 905
 906    <ref-qualifier> ::= R # & ref-qualifier
 907                    ::= O # && ref-qualifier
 908    <CV-qualifiers> ::= [r] [V] [K]  */
 909
 910 static void
 911 write_nested_name (const tree decl)
 912 {
 913   tree template_info;
 914
 915   MANGLE_TRACE_TREE ("nested-name", decl);
 916
 917   write_char ('N');
 918
 919   /* Write CV-qualifiers, if this is a member function.  */
 920   if (TREE_CODE (decl) == FUNCTION_DECL
 921       && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
 922     {
 923       if (DECL_VOLATILE_MEMFUNC_P (decl))
 924         write_char ('V');
 925       if (DECL_CONST_MEMFUNC_P (decl))
 926         write_char ('K');
 927       if (FUNCTION_REF_QUALIFIED (TREE_TYPE (decl)))
 928         {
 929           if (FUNCTION_RVALUE_QUALIFIED (TREE_TYPE (decl)))
 930             write_char ('O');
 931           else
 932             write_char ('R');
 933         }
 934     }
 935
 936   /* Is this a template instance?  */
 937   if (decl_is_template_id (decl, &template_info))
 938     {
 939       /* Yes, use <template-prefix>.  */
 940       write_template_prefix (decl);
 941       write_template_args (TI_ARGS (template_info));
 942     }
 943   else if (TREE_CODE (TREE_TYPE (decl)) == TYPENAME_TYPE)
 944     {
 945       tree name = TYPENAME_TYPE_FULLNAME (TREE_TYPE (decl));
 946       if (TREE_CODE (name) == TEMPLATE_ID_EXPR)
 947         {
 948           write_template_prefix (decl);
 949           write_template_args (TREE_OPERAND (name, 1));
 950         }
 951       else
 952         {
 953           write_prefix (decl_mangling_context (decl));
 954           write_unqualified_name (decl);
 955         }
 956     }
 957   else
 958     {
 959       /* No, just use <prefix>  */
 960       write_prefix (decl_mangling_context (decl));
 961       write_unqualified_name (decl);
 962     }
 963   write_char ('E');
 964 }
 965
 966 /* <prefix> ::= <prefix> <unqualified-name>
 967             ::= <template-param>
 968             ::= <template-prefix> <template-args>
 969             ::= <decltype>
 970             ::= # empty
 971             ::= <substitution>  */
 972
 973 static void
 974 write_prefix (const tree node)
 975 {
 976   tree decl;
 977   /* Non-NULL if NODE represents a template-id.  */
 978   tree template_info = NULL;
 979
 980   if (node == NULL
 981       || node == global_namespace)
 982     return;
 983
 984   MANGLE_TRACE_TREE ("prefix", node);
 985
 986   if (TREE_CODE (node) == DECLTYPE_TYPE)
 987     {
 988       write_type (node);
 989       return;
 990     }
 991
 992   if (find_substitution (node))
 993     return;
 994
 995   if (DECL_P (node))
 996     {
 997       /* If this is a function or parm decl, that means we've hit function
 998          scope, so this prefix must be for a local name.  In this
 999          case, we're under the <local-name> production, which encodes
1000          the enclosing function scope elsewhere.  So don't continue
1001          here.  */
1002       if (TREE_CODE (node) == FUNCTION_DECL
1003           || TREE_CODE (node) == PARM_DECL)
1004         return;
1005
1006       decl = node;
1007       decl_is_template_id (decl, &template_info);
1008     }
1009   else
1010     {
1011       /* Node is a type.  */
1012       decl = TYPE_NAME (node);
1013       if (CLASSTYPE_TEMPLATE_ID_P (node))
1014         template_info = TYPE_TEMPLATE_INFO (node);
1015     }
1016
1017   if (TREE_CODE (node) == TEMPLATE_TYPE_PARM)
1018     write_template_param (node);
1019   else if (template_info != NULL)
1020     /* Templated.  */
1021     {
1022       write_template_prefix (decl);
1023       write_template_args (TI_ARGS (template_info));
1024     }
1025   else if (TREE_CODE (TREE_TYPE (decl)) == TYPENAME_TYPE)
1026     {
1027       tree name = TYPENAME_TYPE_FULLNAME (TREE_TYPE (decl));
1028       if (TREE_CODE (name) == TEMPLATE_ID_EXPR)
1029         {
1030           write_template_prefix (decl);
1031           write_template_args (TREE_OPERAND (name, 1));
1032         }
1033       else
1034         {
1035           write_prefix (decl_mangling_context (decl));
1036           write_unqualified_name (decl);
1037         }
1038     }
1039   else
1040     /* Not templated.  */
1041     {
1042       write_prefix (decl_mangling_context (decl));
1043       write_unqualified_name (decl);
1044       if (VAR_P (decl)
1045           || TREE_CODE (decl) == FIELD_DECL)
1046         {
1047           /* <data-member-prefix> := <member source-name> M */
1048           write_char ('M');
1049           return;
1050         }
1051     }
1052
1053   add_substitution (node);
1054 }
1055
1056 /* <template-prefix> ::= <prefix> <template component>
1057                      ::= <template-param>
1058                      ::= <substitution>  */
1059
1060 static void
1061 write_template_prefix (const tree node)
1062 {
1063   tree decl = DECL_P (node) ? node : TYPE_NAME (node);
1064   tree type = DECL_P (node) ? TREE_TYPE (node) : node;
1065   tree context = decl_mangling_context (decl);
1066   tree template_info;
1067   tree templ;
1068   tree substitution;
1069
1070   MANGLE_TRACE_TREE ("template-prefix", node);
1071
1072   /* Find the template decl.  */
1073   if (decl_is_template_id (decl, &template_info))
1074     templ = TI_TEMPLATE (template_info);
1075   else if (TREE_CODE (type) == TYPENAME_TYPE)
1076     /* For a typename type, all we have is the name.  */
1077     templ = DECL_NAME (decl);
1078   else
1079     {
1080       gcc_assert (CLASSTYPE_TEMPLATE_ID_P (type));
1081
1082       templ = TYPE_TI_TEMPLATE (type);
1083     }
1084
1085   /* For a member template, though, the template name for the
1086      innermost name must have all the outer template levels
1087      instantiated.  For instance, consider
1088
1089        template<typename T> struct Outer {
1090          template<typename U> struct Inner {};
1091        };
1092
1093      The template name for `Inner' in `Outer<int>::Inner<float>' is
1094      `Outer<int>::Inner<U>'.  In g++, we don't instantiate the template
1095      levels separately, so there's no TEMPLATE_DECL available for this
1096      (there's only `Outer<T>::Inner<U>').
1097
1098      In order to get the substitutions right, we create a special
1099      TREE_LIST to represent the substitution candidate for a nested
1100      template.  The TREE_PURPOSE is the template's context, fully
1101      instantiated, and the TREE_VALUE is the TEMPLATE_DECL for the inner
1102      template.
1103
1104      So, for the example above, `Outer<int>::Inner' is represented as a
1105      substitution candidate by a TREE_LIST whose purpose is `Outer<int>'
1106      and whose value is `Outer<T>::Inner<U>'.  */
1107   if (TYPE_P (context))
1108     substitution = build_tree_list (context, templ);
1109   else
1110     substitution = templ;
1111
1112   if (find_substitution (substitution))
1113     return;
1114
1115   if (TREE_TYPE (templ)
1116       && TREE_CODE (TREE_TYPE (templ)) == TEMPLATE_TEMPLATE_PARM)
1117     write_template_param (TREE_TYPE (templ));
1118   else
1119     {
1120       write_prefix (context);
1121       write_unqualified_name (decl);
1122     }
1123
1124   add_substitution (substitution);
1125 }
1126
1127 /* We don't need to handle thunks, vtables, or VTTs here.  Those are
1128    mangled through special entry points.
1129
1130     <unqualified-name>  ::= <operator-name>
1131                         ::= <special-name>
1132                         ::= <source-name>
1133                         ::= <unnamed-type-name>
1134                         ::= <local-source-name>
1135
1136     <local-source-name> ::= L <source-name> <discriminator> */
1137
1138 static void
1139 write_unqualified_id (tree identifier)
1140 {
1141   if (IDENTIFIER_TYPENAME_P (identifier))
1142     write_conversion_operator_name (TREE_TYPE (identifier));
1143   else if (IDENTIFIER_OPNAME_P (identifier))
1144     {
1145       int i;
1146       const char *mangled_name = NULL;
1147
1148       /* Unfortunately, there is no easy way to go from the
1149          name of the operator back to the corresponding tree
1150          code.  */
1151       for (i = 0; i < MAX_TREE_CODES; ++i)
1152         if (operator_name_info[i].identifier == identifier)
1153           {
1154             /* The ABI says that we prefer binary operator
1155                names to unary operator names.  */
1156             if (operator_name_info[i].arity == 2)
1157               {
1158                 mangled_name = operator_name_info[i].mangled_name;
1159                 break;
1160               }
1161             else if (!mangled_name)
1162               mangled_name = operator_name_info[i].mangled_name;
1163           }
1164         else if (assignment_operator_name_info[i].identifier
1165                  == identifier)
1166           {
1167             mangled_name
1168               = assignment_operator_name_info[i].mangled_name;
1169             break;
1170           }
1171       write_string (mangled_name);
1172     }
1173   else if (UDLIT_OPER_P (identifier))
1174     write_literal_operator_name (identifier);
1175   else
1176     write_source_name (identifier);
1177 }
1178
1179 static void
1180 write_unqualified_name (tree decl)
1181 {
1182   MANGLE_TRACE_TREE ("unqualified-name", decl);
1183
1184   if (identifier_p (decl))
1185     {
1186       write_unqualified_id (decl);
1187       return;
1188     }
1189
1190   bool found = false;
1191
1192   if (DECL_NAME (decl) == NULL_TREE)
1193     {
1194       found = true;
1195       gcc_assert (DECL_ASSEMBLER_NAME_SET_P (decl));
1196       write_source_name (DECL_ASSEMBLER_NAME (decl));
1197     }
1198   else if (DECL_DECLARES_FUNCTION_P (decl))
1199     {
1200       found = true;
1201       if (DECL_CONSTRUCTOR_P (decl))
1202         write_special_name_constructor (decl);
1203       else if (DECL_DESTRUCTOR_P (decl))
1204         write_special_name_destructor (decl);
1205       else if (DECL_CONV_FN_P (decl))
1206         {
1207           /* Conversion operator. Handle it right here.
1208              <operator> ::= cv <type>  */
1209           tree type;
1210           if (decl_is_template_id (decl, NULL))
1211             {
1212               tree fn_type;
1213               fn_type = get_mostly_instantiated_function_type (decl);
1214               type = TREE_TYPE (fn_type);
1215             }
1216           else if (FNDECL_USED_AUTO (decl))
1217             type = (DECL_STRUCT_FUNCTION (decl)->language
1218                     ->x_auto_return_pattern);
1219           else
1220             type = DECL_CONV_FN_TYPE (decl);
1221           write_conversion_operator_name (type);
1222         }
1223       else if (DECL_OVERLOADED_OPERATOR_P (decl))
1224         {
1225           operator_name_info_t *oni;
1226           if (DECL_ASSIGNMENT_OPERATOR_P (decl))
1227             oni = assignment_operator_name_info;
1228           else
1229             oni = operator_name_info;
1230
1231           write_string (oni[DECL_OVERLOADED_OPERATOR_P (decl)].mangled_name);
1232         }
1233       else if (UDLIT_OPER_P (DECL_NAME (decl)))
1234         write_literal_operator_name (DECL_NAME (decl));
1235       else
1236         found = false;
1237     }
1238
1239   if (found)
1240     /* OK */;
1241   else if (VAR_OR_FUNCTION_DECL_P (decl) && ! TREE_PUBLIC (decl)
1242            && DECL_NAMESPACE_SCOPE_P (decl)
1243            && decl_linkage (decl) == lk_internal)
1244     {
1245       MANGLE_TRACE_TREE ("local-source-name", decl);
1246       write_char ('L');
1247       write_source_name (DECL_NAME (decl));
1248       /* The default discriminator is 1, and that's all we ever use,
1249          so there's no code to output one here.  */
1250     }
1251   else
1252     {
1253       tree type = TREE_TYPE (decl);
1254
1255       if (TREE_CODE (decl) == TYPE_DECL
1256           && TYPE_ANONYMOUS_P (type))
1257         write_unnamed_type_name (type);
1258       else if (TREE_CODE (decl) == TYPE_DECL
1259                && LAMBDA_TYPE_P (type))
1260         write_closure_type_name (type);
1261       else
1262         write_source_name (DECL_NAME (decl));
1263     }
1264
1265   /* We use the ABI tags from the primary template, ignoring tags on any
1266      specializations.  This is necessary because C++ doesn't require a
1267      specialization to be declared before it is used unless the use
1268      requires a complete type, but we need to get the tags right on
1269      incomplete types as well.  */
1270   if (tree tmpl = most_general_template (decl))
1271     decl = DECL_TEMPLATE_RESULT (tmpl);
1272   /* Don't crash on an unbound class template.  */
1273   if (decl)
1274     {
1275       tree attrs = (TREE_CODE (decl) == TYPE_DECL
1276                     ? TYPE_ATTRIBUTES (TREE_TYPE (decl))
1277                     : DECL_ATTRIBUTES (decl));
1278       write_abi_tags (lookup_attribute ("abi_tag", attrs));
1279     }
1280 }
1281
1282 /* Write the unqualified-name for a conversion operator to TYPE.  */
1283
1284 static void
1285 write_conversion_operator_name (const tree type)
1286 {
1287   write_string ("cv");
1288   write_type (type);
1289 }
1290
1291 /* Non-terminal <source-name>.  IDENTIFIER is an IDENTIFIER_NODE.
1292
1293      <source-name> ::= </length/ number> <identifier>  */
1294
1295 static void
1296 write_source_name (tree identifier)
1297 {
1298   MANGLE_TRACE_TREE ("source-name", identifier);
1299
1300   /* Never write the whole template-id name including the template
1301      arguments; we only want the template name.  */
1302   if (IDENTIFIER_TEMPLATE (identifier))
1303     identifier = IDENTIFIER_TEMPLATE (identifier);
1304
1305   write_unsigned_number (IDENTIFIER_LENGTH (identifier));
1306   write_identifier (IDENTIFIER_POINTER (identifier));
1307 }
1308
1309 /* Compare two TREE_STRINGs like strcmp.  */
1310
1311 int
1312 tree_string_cmp (const void *p1, const void *p2)
1313 {
1314   if (p1 == p2)
1315     return 0;
1316   tree s1 = *(const tree*)p1;
1317   tree s2 = *(const tree*)p2;
1318   return strcmp (TREE_STRING_POINTER (s1),
1319                  TREE_STRING_POINTER (s2));
1320 }
1321
1322 /* ID is the name of a function or type with abi_tags attribute TAGS.
1323    Write out the name, suitably decorated.  */
1324
1325 static void
1326 write_abi_tags (tree tags)
1327 {
1328   if (tags == NULL_TREE)
1329     return;
1330
1331   tags = TREE_VALUE (tags);
1332
1333   vec<tree, va_gc> * vec = make_tree_vector();
1334
1335   for (tree t = tags; t; t = TREE_CHAIN (t))
1336     {
1337       if (ABI_TAG_IMPLICIT (t))
1338         continue;
1339       tree str = TREE_VALUE (t);
1340       vec_safe_push (vec, str);
1341     }
1342
1343   vec->qsort (tree_string_cmp);
1344
1345   unsigned i; tree str;
1346   FOR_EACH_VEC_ELT (*vec, i, str)
1347     {
1348       write_string ("B");
1349       write_unsigned_number (TREE_STRING_LENGTH (str) - 1);
1350       write_identifier (TREE_STRING_POINTER (str));
1351     }
1352
1353   release_tree_vector (vec);
1354 }
1355
1356 /* Write a user-defined literal operator.
1357           ::= li <source-name>    # "" <source-name>
1358    IDENTIFIER is an LITERAL_IDENTIFIER_NODE.  */
1359
1360 static void
1361 write_literal_operator_name (tree identifier)
1362 {
1363   const char* suffix = UDLIT_OP_SUFFIX (identifier);
1364   write_identifier (UDLIT_OP_MANGLED_PREFIX);
1365   write_unsigned_number (strlen (suffix));
1366   write_identifier (suffix);
1367 }
1368
1369 /* Encode 0 as _, and 1+ as n-1_.  */
1370
1371 static void
1372 write_compact_number (int num)
1373 {
1374   if (num > 0)
1375     write_unsigned_number (num - 1);
1376   write_char ('_');
1377 }
1378
1379 /* Return how many unnamed types precede TYPE in its enclosing class.  */
1380
1381 static int
1382 nested_anon_class_index (tree type)
1383 {
1384   int index = 0;
1385   tree member = TYPE_FIELDS (TYPE_CONTEXT (type));
1386   for (; member; member = DECL_CHAIN (member))
1387     if (DECL_IMPLICIT_TYPEDEF_P (member))
1388       {
1389         tree memtype = TREE_TYPE (member);
1390         if (memtype == type)
1391           return index;
1392         else if (TYPE_ANONYMOUS_P (memtype))
1393           ++index;
1394       }
1395
1396   gcc_unreachable ();
1397 }
1398
1399 /* <unnamed-type-name> ::= Ut [ <nonnegative number> ] _ */
1400
1401 static void
1402 write_unnamed_type_name (const tree type)
1403 {
1404   int discriminator;
1405   MANGLE_TRACE_TREE ("unnamed-type-name", type);
1406
1407   if (TYPE_FUNCTION_SCOPE_P (type))
1408     discriminator = local_class_index (type);
1409   else if (TYPE_CLASS_SCOPE_P (type))
1410     discriminator = nested_anon_class_index (type);
1411   else
1412     {
1413       gcc_assert (no_linkage_check (type, /*relaxed_p=*/true));
1414       /* Just use the old mangling at namespace scope.  */
1415       write_source_name (TYPE_IDENTIFIER (type));
1416       return;
1417     }
1418
1419   write_string ("Ut");
1420   write_compact_number (discriminator);
1421 }
1422
1423 /* <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
1424    <lambda-sig> ::= <parameter type>+  # Parameter types or "v" if the lambda has no parameters */
1425
1426 static void
1427 write_closure_type_name (const tree type)
1428 {
1429   tree fn = lambda_function (type);
1430   tree lambda = CLASSTYPE_LAMBDA_EXPR (type);
1431   tree parms = TYPE_ARG_TYPES (TREE_TYPE (fn));
1432
1433   MANGLE_TRACE_TREE ("closure-type-name", type);
1434
1435   write_string ("Ul");
1436   write_method_parms (parms, /*method_p=*/1, fn);
1437   write_char ('E');
1438   write_compact_number (LAMBDA_EXPR_DISCRIMINATOR (lambda));
1439 }
1440
1441 /* Convert NUMBER to ascii using base BASE and generating at least
1442    MIN_DIGITS characters. BUFFER points to the _end_ of the buffer
1443    into which to store the characters. Returns the number of
1444    characters generated (these will be laid out in advance of where
1445    BUFFER points).  */
1446
1447 static int
1448 hwint_to_ascii (unsigned HOST_WIDE_INT number, const unsigned int base,
1449                 char *buffer, const unsigned int min_digits)
1450 {
1451   static const char base_digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
1452   unsigned digits = 0;
1453
1454   while (number)
1455     {
1456       unsigned HOST_WIDE_INT d = number / base;
1457
1458       *--buffer = base_digits[number - d * base];
1459       digits++;
1460       number = d;
1461     }
1462   while (digits < min_digits)
1463     {
1464       *--buffer = base_digits[0];
1465       digits++;
1466     }
1467   return digits;
1468 }
1469
1470 /* Non-terminal <number>.
1471
1472      <number> ::= [n] </decimal integer/>  */
1473
1474 static void
1475 write_number (unsigned HOST_WIDE_INT number, const int unsigned_p,
1476               const unsigned int base)
1477 {
1478   char buffer[sizeof (HOST_WIDE_INT) * 8];
1479   unsigned count = 0;
1480
1481   if (!unsigned_p && (HOST_WIDE_INT) number < 0)
1482     {
1483       write_char ('n');
1484       number = -((HOST_WIDE_INT) number);
1485     }
1486   count = hwint_to_ascii (number, base, buffer + sizeof (buffer), 1);
1487   write_chars (buffer + sizeof (buffer) - count, count);
1488 }
1489
1490 /* Write out an integral CST in decimal. Most numbers are small, and
1491    representable in a HOST_WIDE_INT. Occasionally we'll have numbers
1492    bigger than that, which we must deal with.  */
1493
1494 static inline void
1495 write_integer_cst (const tree cst)
1496 {
1497   int sign = tree_int_cst_sgn (cst);
1498   widest_int abs_value = wi::abs (wi::to_widest (cst));
1499   if (!wi::fits_uhwi_p (abs_value))
1500     {
1501       /* A bignum. We do this in chunks, each of which fits in a
1502          HOST_WIDE_INT.  */
1503       char buffer[sizeof (HOST_WIDE_INT) * 8 * 2];
1504       unsigned HOST_WIDE_INT chunk;
1505       unsigned chunk_digits;
1506       char *ptr = buffer + sizeof (buffer);
1507       unsigned count = 0;
1508       tree n, base, type;
1509       int done;
1510
1511       /* HOST_WIDE_INT must be at least 32 bits, so 10^9 is
1512          representable.  */
1513       chunk = 1000000000;
1514       chunk_digits = 9;
1515
1516       if (sizeof (HOST_WIDE_INT) >= 8)
1517         {
1518           /* It is at least 64 bits, so 10^18 is representable.  */
1519           chunk_digits = 18;
1520           chunk *= chunk;
1521         }
1522
1523       type = c_common_signed_or_unsigned_type (1, TREE_TYPE (cst));
1524       base = build_int_cstu (type, chunk);
1525       n = wide_int_to_tree (type, cst);
1526
1527       if (sign < 0)
1528         {
1529           write_char ('n');
1530           n = fold_build1_loc (input_location, NEGATE_EXPR, type, n);
1531         }
1532       do
1533         {
1534           tree d = fold_build2_loc (input_location, FLOOR_DIV_EXPR, type, n, base);
1535           tree tmp = fold_build2_loc (input_location, MULT_EXPR, type, d, base);
1536           unsigned c;
1537
1538           done = integer_zerop (d);
1539           tmp = fold_build2_loc (input_location, MINUS_EXPR, type, n, tmp);
1540           c = hwint_to_ascii (TREE_INT_CST_LOW (tmp), 10, ptr,
1541                               done ? 1 : chunk_digits);
1542           ptr -= c;
1543           count += c;
1544           n = d;
1545         }
1546       while (!done);
1547       write_chars (ptr, count);
1548     }
1549   else
1550     {
1551       /* A small num.  */
1552       if (sign < 0)
1553         write_char ('n');
1554       write_unsigned_number (abs_value.to_uhwi ());
1555     }
1556 }
1557
1558 /* Write out a floating-point literal.
1559
1560     "Floating-point literals are encoded using the bit pattern of the
1561     target processor's internal representation of that number, as a
1562     fixed-length lowercase hexadecimal string, high-order bytes first
1563     (even if the target processor would store low-order bytes first).
1564     The "n" prefix is not used for floating-point literals; the sign
1565     bit is encoded with the rest of the number.
1566
1567     Here are some examples, assuming the IEEE standard representation
1568     for floating point numbers.  (Spaces are for readability, not
1569     part of the encoding.)
1570
1571         1.0f                    Lf 3f80 0000 E
1572        -1.0f                    Lf bf80 0000 E
1573         1.17549435e-38f         Lf 0080 0000 E
1574         1.40129846e-45f         Lf 0000 0001 E
1575         0.0f                    Lf 0000 0000 E"
1576
1577    Caller is responsible for the Lx and the E.  */
1578 static void
1579 write_real_cst (const tree value)
1580 {
1581   long target_real[4];  /* largest supported float */
1582   char buffer[9];       /* eight hex digits in a 32-bit number */
1583   int i, limit, dir;
1584
1585   tree type = TREE_TYPE (value);
1586   int words = GET_MODE_BITSIZE (TYPE_MODE (type)) / 32;
1587
1588   real_to_target (target_real, &TREE_REAL_CST (value),
1589                   TYPE_MODE (type));
1590
1591   /* The value in target_real is in the target word order,
1592      so we must write it out backward if that happens to be
1593      little-endian.  write_number cannot be used, it will
1594      produce uppercase.  */
1595   if (FLOAT_WORDS_BIG_ENDIAN)
1596     i = 0, limit = words, dir = 1;
1597   else
1598     i = words - 1, limit = -1, dir = -1;
1599
1600   for (; i != limit; i += dir)
1601     {
1602       sprintf (buffer, "%08lx", (unsigned long) target_real[i]);
1603       write_chars (buffer, 8);
1604     }
1605 }
1606
1607 /* Non-terminal <identifier>.
1608
1609      <identifier> ::= </unqualified source code identifier>  */
1610
1611 static void
1612 write_identifier (const char *identifier)
1613 {
1614   MANGLE_TRACE ("identifier", identifier);
1615   write_string (identifier);
1616 }
1617
1618 /* Handle constructor productions of non-terminal <special-name>.
1619    CTOR is a constructor FUNCTION_DECL.
1620
1621      <special-name> ::= C1   # complete object constructor
1622                     ::= C2   # base object constructor
1623                     ::= C3   # complete object allocating constructor
1624
1625    Currently, allocating constructors are never used.  */
1626
1627 static void
1628 write_special_name_constructor (const tree ctor)
1629 {
1630   if (DECL_BASE_CONSTRUCTOR_P (ctor))
1631     write_string ("C2");
1632   /* This is the old-style "[unified]" constructor.
1633      In some cases, we may emit this function and call
1634      it from the clones in order to share code and save space.  */
1635   else if (DECL_MAYBE_IN_CHARGE_CONSTRUCTOR_P (ctor))
1636     write_string ("C4");
1637   else
1638     {
1639       gcc_assert (DECL_COMPLETE_CONSTRUCTOR_P (ctor));
1640       write_string ("C1");
1641     }
1642 }
1643
1644 /* Handle destructor productions of non-terminal <special-name>.
1645    DTOR is a destructor FUNCTION_DECL.
1646
1647      <special-name> ::= D0 # deleting (in-charge) destructor
1648                     ::= D1 # complete object (in-charge) destructor
1649                     ::= D2 # base object (not-in-charge) destructor  */
1650
1651 static void
1652 write_special_name_destructor (const tree dtor)
1653 {
1654   if (DECL_DELETING_DESTRUCTOR_P (dtor))
1655     write_string ("D0");
1656   else if (DECL_BASE_DESTRUCTOR_P (dtor))
1657     write_string ("D2");
1658   else if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (dtor))
1659     /* This is the old-style "[unified]" destructor.
1660        In some cases, we may emit this function and call
1661        it from the clones in order to share code and save space.  */
1662     write_string ("D4");
1663   else
1664     {
1665       gcc_assert (DECL_COMPLETE_DESTRUCTOR_P (dtor));
1666       write_string ("D1");
1667     }
1668 }
1669
1670 /* Scan the vector of local classes and return how many others with the
1671    same name (or same no name) and context precede ENTITY.  */
1672
1673 static int
1674 local_class_index (tree entity)
1675 {
1676   int ix, discriminator = 0;
1677   tree name = (TYPE_ANONYMOUS_P (entity) ? NULL_TREE
1678                : TYPE_IDENTIFIER (entity));
1679   tree ctx = TYPE_CONTEXT (entity);
1680   for (ix = 0; ; ix++)
1681     {
1682       tree type = (*local_classes)[ix];
1683       if (type == entity)
1684         return discriminator;
1685       if (TYPE_CONTEXT (type) == ctx
1686           && (name ? TYPE_IDENTIFIER (type) == name
1687               : TYPE_ANONYMOUS_P (type)))
1688         ++discriminator;
1689     }
1690   gcc_unreachable ();
1691 }
1692
1693 /* Return the discriminator for ENTITY appearing inside
1694    FUNCTION.  The discriminator is the lexical ordinal of VAR among
1695    entities with the same name in the same FUNCTION.  */
1696
1697 static int
1698 discriminator_for_local_entity (tree entity)
1699 {
1700   if (DECL_DISCRIMINATOR_P (entity))
1701     {
1702       if (DECL_DISCRIMINATOR_SET_P (entity))
1703         return DECL_DISCRIMINATOR (entity);
1704       else
1705         /* The first entity with a particular name doesn't get
1706            DECL_DISCRIMINATOR set up.  */
1707         return 0;
1708     }
1709   else if (TREE_CODE (entity) == TYPE_DECL)
1710     {
1711       /* Scan the list of local classes.  */
1712       entity = TREE_TYPE (entity);
1713
1714       /* Lambdas and unnamed types have their own discriminators.  */
1715       if (LAMBDA_TYPE_P (entity) || TYPE_ANONYMOUS_P (entity))
1716         return 0;
1717
1718       return local_class_index (entity);
1719     }
1720   else
1721     gcc_unreachable ();
1722 }
1723
1724 /* Return the discriminator for STRING, a string literal used inside
1725    FUNCTION.  The discriminator is the lexical ordinal of STRING among
1726    string literals used in FUNCTION.  */
1727
1728 static int
1729 discriminator_for_string_literal (tree /*function*/,
1730                                   tree /*string*/)
1731 {
1732   /* For now, we don't discriminate amongst string literals.  */
1733   return 0;
1734 }
1735
1736 /*   <discriminator> := _ <number>
1737
1738    The discriminator is used only for the second and later occurrences
1739    of the same name within a single function. In this case <number> is
1740    n - 2, if this is the nth occurrence, in lexical order.  */
1741
1742 static void
1743 write_discriminator (const int discriminator)
1744 {
1745   /* If discriminator is zero, don't write anything.  Otherwise...  */
1746   if (discriminator > 0)
1747     {
1748       write_char ('_');
1749       write_unsigned_number (discriminator - 1);
1750     }
1751 }
1752
1753 /* Mangle the name of a function-scope entity.  FUNCTION is the
1754    FUNCTION_DECL for the enclosing function, or a PARM_DECL for lambdas in
1755    default argument scope.  ENTITY is the decl for the entity itself.
1756    LOCAL_ENTITY is the entity that's directly scoped in FUNCTION_DECL,
1757    either ENTITY itself or an enclosing scope of ENTITY.
1758
1759      <local-name> := Z <function encoding> E <entity name> [<discriminator>]
1760                   := Z <function encoding> E s [<discriminator>]
1761                   := Z <function encoding> Ed [ <parameter number> ] _ <entity name> */
1762
1763 static void
1764 write_local_name (tree function, const tree local_entity,
1765                   const tree entity)
1766 {
1767   tree parm = NULL_TREE;
1768
1769   MANGLE_TRACE_TREE ("local-name", entity);
1770
1771   if (TREE_CODE (function) == PARM_DECL)
1772     {
1773       parm = function;
1774       function = DECL_CONTEXT (parm);
1775     }
1776
1777   write_char ('Z');
1778   write_encoding (function);
1779   write_char ('E');
1780
1781   /* For this purpose, parameters are numbered from right-to-left.  */
1782   if (parm)
1783     {
1784       tree t;
1785       int i = 0;
1786       for (t = DECL_ARGUMENTS (function); t; t = DECL_CHAIN (t))
1787         {
1788           if (t == parm)
1789             i = 1;
1790           else if (i)
1791             ++i;
1792         }
1793       write_char ('d');
1794       write_compact_number (i - 1);
1795     }
1796
1797   if (TREE_CODE (entity) == STRING_CST)
1798     {
1799       write_char ('s');
1800       write_discriminator (discriminator_for_string_literal (function,
1801                                                              entity));
1802     }
1803   else
1804     {
1805       /* Now the <entity name>.  Let write_name know its being called
1806          from <local-name>, so it doesn't try to process the enclosing
1807          function scope again.  */
1808       write_name (entity, /*ignore_local_scope=*/1);
1809       write_discriminator (discriminator_for_local_entity (local_entity));
1810     }
1811 }
1812
1813 /* Non-terminals <type> and <CV-qualifier>.
1814
1815      <type> ::= <builtin-type>
1816             ::= <function-type>
1817             ::= <class-enum-type>
1818             ::= <array-type>
1819             ::= <pointer-to-member-type>
1820             ::= <template-param>
1821             ::= <substitution>
1822             ::= <CV-qualifier>
1823             ::= P <type>    # pointer-to
1824             ::= R <type>    # reference-to
1825             ::= C <type>    # complex pair (C 2000)
1826             ::= G <type>    # imaginary (C 2000)     [not supported]
1827             ::= U <source-name> <type>   # vendor extended type qualifier
1828
1829    C++0x extensions
1830
1831      <type> ::= RR <type>   # rvalue reference-to
1832      <type> ::= Dt <expression> # decltype of an id-expression or
1833                                 # class member access
1834      <type> ::= DT <expression> # decltype of an expression
1835      <type> ::= Dn              # decltype of nullptr
1836
1837    TYPE is a type node.  */
1838
1839 static void
1840 write_type (tree type)
1841 {
1842   /* This gets set to nonzero if TYPE turns out to be a (possibly
1843      CV-qualified) builtin type.  */
1844   int is_builtin_type = 0;
1845
1846   MANGLE_TRACE_TREE ("type", type);
1847
1848   if (type == error_mark_node)
1849     return;
1850
1851   type = canonicalize_for_substitution (type);
1852   if (find_substitution (type))
1853     return;
1854
1855
1856   if (write_CV_qualifiers_for_type (type) > 0)
1857     /* If TYPE was CV-qualified, we just wrote the qualifiers; now
1858        mangle the unqualified type.  The recursive call is needed here
1859        since both the qualified and unqualified types are substitution
1860        candidates.  */
1861     {
1862       tree t = TYPE_MAIN_VARIANT (type);
1863       if (TREE_CODE (t) == FUNCTION_TYPE
1864           || TREE_CODE (t) == METHOD_TYPE)
1865         {
1866           t = build_ref_qualified_type (t, type_memfn_rqual (type));
1867           if (abi_version_at_least (8))
1868             /* Avoid adding the unqualified function type as a substitution.  */
1869             write_function_type (t);
1870           else
1871             write_type (t);
1872           if (abi_version_crosses (8))
1873             G.need_abi_warning = 1;
1874         }
1875       else
1876         write_type (t);
1877     }
1878   else if (TREE_CODE (type) == ARRAY_TYPE)
1879     /* It is important not to use the TYPE_MAIN_VARIANT of TYPE here
1880        so that the cv-qualification of the element type is available
1881        in write_array_type.  */
1882     write_array_type (type);
1883   else
1884     {
1885       tree type_orig = type;
1886
1887       /* See through any typedefs.  */
1888       type = TYPE_MAIN_VARIANT (type);
1889       if (TREE_CODE (type) == FUNCTION_TYPE
1890           || TREE_CODE (type) == METHOD_TYPE)
1891         type = build_ref_qualified_type (type, type_memfn_rqual (type_orig));
1892
1893       /* According to the C++ ABI, some library classes are passed the
1894          same as the scalar type of their single member and use the same
1895          mangling.  */
1896       if (TREE_CODE (type) == RECORD_TYPE && TYPE_TRANSPARENT_AGGR (type))
1897         type = TREE_TYPE (first_field (type));
1898
1899       if (TYPE_PTRDATAMEM_P (type))
1900         write_pointer_to_member_type (type);
1901       else
1902         {
1903           /* Handle any target-specific fundamental types.  */
1904           const char *target_mangling
1905             = targetm.mangle_type (type_orig);
1906
1907           if (target_mangling)
1908             {
1909               write_string (target_mangling);
1910               /* Add substitutions for types other than fundamental
1911                  types.  */
1912               if (!VOID_TYPE_P (type)
1913                   && TREE_CODE (type) != INTEGER_TYPE
1914                   && TREE_CODE (type) != REAL_TYPE
1915                   && TREE_CODE (type) != BOOLEAN_TYPE)
1916                 add_substitution (type);
1917               return;
1918             }
1919
1920           switch (TREE_CODE (type))
1921             {
1922             case VOID_TYPE:
1923             case BOOLEAN_TYPE:
1924             case INTEGER_TYPE:  /* Includes wchar_t.  */
1925             case REAL_TYPE:
1926             case FIXED_POINT_TYPE:
1927               {
1928                 /* If this is a typedef, TYPE may not be one of
1929                    the standard builtin type nodes, but an alias of one.  Use
1930                    TYPE_MAIN_VARIANT to get to the underlying builtin type.  */
1931                 write_builtin_type (TYPE_MAIN_VARIANT (type));
1932                 ++is_builtin_type;
1933               }
1934               break;
1935
1936             case COMPLEX_TYPE:
1937               write_char ('C');
1938               write_type (TREE_TYPE (type));
1939               break;
1940
1941             case FUNCTION_TYPE:
1942             case METHOD_TYPE:
1943               write_function_type (type);
1944               break;
1945
1946             case UNION_TYPE:
1947             case RECORD_TYPE:
1948             case ENUMERAL_TYPE:
1949               /* A pointer-to-member function is represented as a special
1950                  RECORD_TYPE, so check for this first.  */
1951               if (TYPE_PTRMEMFUNC_P (type))
1952                 write_pointer_to_member_type (type);
1953               else
1954                 write_class_enum_type (type);
1955               break;
1956
1957             case TYPENAME_TYPE:
1958             case UNBOUND_CLASS_TEMPLATE:
1959               /* We handle TYPENAME_TYPEs and UNBOUND_CLASS_TEMPLATEs like
1960                  ordinary nested names.  */
1961               write_nested_name (TYPE_STUB_DECL (type));
1962               break;
1963
1964             case POINTER_TYPE:
1965             case REFERENCE_TYPE:
1966               if (TYPE_PTR_P (type))
1967                 write_char ('P');
1968               else if (TYPE_REF_IS_RVALUE (type))
1969                 write_char ('O');
1970               else
1971                 write_char ('R');
1972               {
1973                 tree target = TREE_TYPE (type);
1974                 /* Attribute const/noreturn are not reflected in mangling.
1975                    We strip them here rather than at a lower level because
1976                    a typedef or template argument can have function type
1977                    with function-cv-quals (that use the same representation),
1978                    but you can't have a pointer/reference to such a type.  */
1979                 if (TREE_CODE (target) == FUNCTION_TYPE)
1980                   {
1981                     if (abi_version_crosses (5)
1982                         && TYPE_QUALS (target) != TYPE_UNQUALIFIED)
1983                       G.need_abi_warning = 1;
1984                     if (abi_version_at_least (5))
1985                       target = build_qualified_type (target, TYPE_UNQUALIFIED);
1986                   }
1987                 write_type (target);
1988               }
1989               break;
1990
1991             case TEMPLATE_TYPE_PARM:
1992               if (is_auto (type))
1993                 {
1994                   if (AUTO_IS_DECLTYPE (type))
1995                     write_identifier ("Dc");
1996                   else
1997                     write_identifier ("Da");
1998                   ++is_builtin_type;
1999                   break;
2000                 }
2001               /* else fall through.  */
2002             case TEMPLATE_PARM_INDEX:
2003               write_template_param (type);
2004               break;
2005
2006             case TEMPLATE_TEMPLATE_PARM:
2007               write_template_template_param (type);
2008               break;
2009
2010             case BOUND_TEMPLATE_TEMPLATE_PARM:
2011               write_template_template_param (type);
2012               write_template_args
2013                 (TI_ARGS (TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (type)));
2014               break;
2015
2016             case VECTOR_TYPE:
2017               if (abi_version_at_least (4))
2018                 {
2019                   write_string ("Dv");
2020                   /* Non-constant vector size would be encoded with
2021                      _ expression, but we don't support that yet.  */
2022                   write_unsigned_number (TYPE_VECTOR_SUBPARTS (type));
2023                   write_char ('_');
2024                 }
2025               else
2026                 write_string ("U8__vector");
2027               if (abi_version_crosses (4))
2028                 G.need_abi_warning = 1;
2029               write_type (TREE_TYPE (type));
2030               break;
2031
2032             case TYPE_PACK_EXPANSION:
2033               write_string ("Dp");
2034               write_type (PACK_EXPANSION_PATTERN (type));
2035               break;
2036
2037             case DECLTYPE_TYPE:
2038               /* These shouldn't make it into mangling.  */
2039               gcc_assert (!DECLTYPE_FOR_LAMBDA_CAPTURE (type)
2040                           && !DECLTYPE_FOR_LAMBDA_PROXY (type));
2041
2042               /* In ABI <5, we stripped decltype of a plain decl.  */
2043               if (DECLTYPE_TYPE_ID_EXPR_OR_MEMBER_ACCESS_P (type))
2044                 {
2045                   tree expr = DECLTYPE_TYPE_EXPR (type);
2046                   tree etype = NULL_TREE;
2047                   switch (TREE_CODE (expr))
2048                     {
2049                     case VAR_DECL:
2050                     case PARM_DECL:
2051                     case RESULT_DECL:
2052                     case FUNCTION_DECL:
2053                     case CONST_DECL:
2054                     case TEMPLATE_PARM_INDEX:
2055                       etype = TREE_TYPE (expr);
2056                       break;
2057
2058                     default:
2059                       break;
2060                     }
2061
2062                   if (etype && !type_uses_auto (etype))
2063                     {
2064                       if (abi_version_crosses (5))
2065                         G.need_abi_warning = 1;
2066                       if (!abi_version_at_least (5))
2067                         {
2068                           write_type (etype);
2069                           return;
2070                         }
2071                     }
2072                 }
2073
2074               write_char ('D');
2075               if (DECLTYPE_TYPE_ID_EXPR_OR_MEMBER_ACCESS_P (type))
2076                 write_char ('t');
2077               else
2078                 write_char ('T');
2079               ++cp_unevaluated_operand;
2080               write_expression (DECLTYPE_TYPE_EXPR (type));
2081               --cp_unevaluated_operand;
2082               write_char ('E');
2083               break;
2084
2085             case NULLPTR_TYPE:
2086               write_string ("Dn");
2087               if (abi_version_at_least (7))
2088                 ++is_builtin_type;
2089               if (abi_version_crosses (7))
2090                 G.need_abi_warning = 1;
2091               break;
2092
2093             case TYPEOF_TYPE:
2094               sorry ("mangling typeof, use decltype instead");
2095               break;
2096
2097             case UNDERLYING_TYPE:
2098               sorry ("mangling __underlying_type");
2099               break;
2100
2101             case LANG_TYPE:
2102               /* fall through.  */
2103
2104             default:
2105               gcc_unreachable ();
2106             }
2107         }
2108     }
2109
2110   /* Types other than builtin types are substitution candidates.  */
2111   if (!is_builtin_type)
2112     add_substitution (type);
2113 }
2114
2115 /* Non-terminal <CV-qualifiers> for type nodes.  Returns the number of
2116    CV-qualifiers written for TYPE.
2117
2118      <CV-qualifiers> ::= [r] [V] [K]  */
2119
2120 static int
2121 write_CV_qualifiers_for_type (const tree type)
2122 {
2123   int num_qualifiers = 0;
2124
2125   /* The order is specified by:
2126
2127        "In cases where multiple order-insensitive qualifiers are
2128        present, they should be ordered 'K' (closest to the base type),
2129        'V', 'r', and 'U' (farthest from the base type) ..."
2130
2131      Note that we do not use cp_type_quals below; given "const
2132      int[3]", the "const" is emitted with the "int", not with the
2133      array.  */
2134   cp_cv_quals quals = TYPE_QUALS (type);
2135
2136   if (quals & TYPE_QUAL_RESTRICT)
2137     {
2138       write_char ('r');
2139       ++num_qualifiers;
2140     }
2141   if (quals & TYPE_QUAL_VOLATILE)
2142     {
2143       write_char ('V');
2144       ++num_qualifiers;
2145     }
2146   if (quals & TYPE_QUAL_CONST)
2147     {
2148       write_char ('K');
2149       ++num_qualifiers;
2150     }
2151
2152   return num_qualifiers;
2153 }
2154
2155 /* Non-terminal <builtin-type>.
2156
2157      <builtin-type> ::= v   # void
2158                     ::= b   # bool
2159                     ::= w   # wchar_t
2160                     ::= c   # char
2161                     ::= a   # signed char
2162                     ::= h   # unsigned char
2163                     ::= s   # short
2164                     ::= t   # unsigned short
2165                     ::= i   # int
2166                     ::= j   # unsigned int
2167                     ::= l   # long
2168                     ::= m   # unsigned long
2169                     ::= x   # long long, __int64
2170                     ::= y   # unsigned long long, __int64
2171                     ::= n   # __int128
2172                     ::= o   # unsigned __int128
2173                     ::= f   # float
2174                     ::= d   # double
2175                     ::= e   # long double, __float80
2176                     ::= g   # __float128          [not supported]
2177                     ::= u <source-name>  # vendor extended type */
2178
2179 static void
2180 write_builtin_type (tree type)
2181 {
2182   if (TYPE_CANONICAL (type))
2183     type = TYPE_CANONICAL (type);
2184
2185   switch (TREE_CODE (type))
2186     {
2187     case VOID_TYPE:
2188       write_char ('v');
2189       break;
2190
2191     case BOOLEAN_TYPE:
2192       write_char ('b');
2193       break;
2194
2195     case INTEGER_TYPE:
2196       /* TYPE may still be wchar_t, char16_t, or char32_t, since that
2197          isn't in integer_type_nodes.  */
2198       if (type == wchar_type_node)
2199         write_char ('w');
2200       else if (type == char16_type_node)
2201         write_string ("Ds");
2202       else if (type == char32_type_node)
2203         write_string ("Di");
2204       else if (TYPE_FOR_JAVA (type))
2205         write_java_integer_type_codes (type);
2206       else
2207         {
2208           size_t itk;
2209           /* Assume TYPE is one of the shared integer type nodes.  Find
2210              it in the array of these nodes.  */
2211         iagain:
2212           for (itk = 0; itk < itk_none; ++itk)
2213             if (integer_types[itk] != NULL_TREE
2214                 && type == integer_types[itk])
2215               {
2216                 /* Print the corresponding single-letter code.  */
2217                 write_char (integer_type_codes[itk]);
2218                 break;
2219               }
2220
2221           if (itk == itk_none)
2222             {
2223               tree t = c_common_type_for_mode (TYPE_MODE (type),
2224                                                TYPE_UNSIGNED (type));
2225               if (type != t)
2226                 {
2227                   type = t;
2228                   goto iagain;
2229                 }
2230
2231               if (TYPE_PRECISION (type) == 128)
2232                 write_char (TYPE_UNSIGNED (type) ? 'o' : 'n');
2233               else
2234                 {
2235                   /* Allow for cases where TYPE is not one of the shared
2236                      integer type nodes and write a "vendor extended builtin
2237                      type" with a name the form intN or uintN, respectively.
2238                      Situations like this can happen if you have an
2239                      __attribute__((__mode__(__SI__))) type and use exotic
2240                      switches like '-mint8' on AVR.  Of course, this is
2241                      undefined by the C++ ABI (and '-mint8' is not even
2242                      Standard C conforming), but when using such special
2243                      options you're pretty much in nowhere land anyway.  */
2244                   const char *prefix;
2245                   char prec[11];        /* up to ten digits for an unsigned */
2246
2247                   prefix = TYPE_UNSIGNED (type) ? "uint" : "int";
2248                   sprintf (prec, "%u", (unsigned) TYPE_PRECISION (type));
2249                   write_char ('u');     /* "vendor extended builtin type" */
2250                   write_unsigned_number (strlen (prefix) + strlen (prec));
2251                   write_string (prefix);
2252                   write_string (prec);
2253                 }
2254             }
2255         }
2256       break;
2257
2258     case REAL_TYPE:
2259       if (type == float_type_node
2260           || type == java_float_type_node)
2261         write_char ('f');
2262       else if (type == double_type_node
2263                || type == java_double_type_node)
2264         write_char ('d');
2265       else if (type == long_double_type_node)
2266         write_char ('e');
2267       else if (type == dfloat32_type_node)
2268         write_string ("Df");
2269       else if (type == dfloat64_type_node)
2270         write_string ("Dd");
2271       else if (type == dfloat128_type_node)
2272         write_string ("De");
2273       else
2274         gcc_unreachable ();
2275       break;
2276
2277     case FIXED_POINT_TYPE:
2278       write_string ("DF");
2279       if (GET_MODE_IBIT (TYPE_MODE (type)) > 0)
2280         write_unsigned_number (GET_MODE_IBIT (TYPE_MODE (type)));
2281       if (type == fract_type_node
2282           || type == sat_fract_type_node
2283           || type == accum_type_node
2284           || type == sat_accum_type_node)
2285         write_char ('i');
2286       else if (type == unsigned_fract_type_node
2287                || type == sat_unsigned_fract_type_node
2288                || type == unsigned_accum_type_node
2289                || type == sat_unsigned_accum_type_node)
2290         write_char ('j');
2291       else if (type == short_fract_type_node
2292                || type == sat_short_fract_type_node
2293                || type == short_accum_type_node
2294                || type == sat_short_accum_type_node)
2295         write_char ('s');
2296       else if (type == unsigned_short_fract_type_node
2297                || type == sat_unsigned_short_fract_type_node
2298                || type == unsigned_short_accum_type_node
2299                || type == sat_unsigned_short_accum_type_node)
2300         write_char ('t');
2301       else if (type == long_fract_type_node
2302                || type == sat_long_fract_type_node
2303                || type == long_accum_type_node
2304                || type == sat_long_accum_type_node)
2305         write_char ('l');
2306       else if (type == unsigned_long_fract_type_node
2307                || type == sat_unsigned_long_fract_type_node
2308                || type == unsigned_long_accum_type_node
2309                || type == sat_unsigned_long_accum_type_node)
2310         write_char ('m');
2311       else if (type == long_long_fract_type_node
2312                || type == sat_long_long_fract_type_node
2313                || type == long_long_accum_type_node
2314                || type == sat_long_long_accum_type_node)
2315         write_char ('x');
2316       else if (type == unsigned_long_long_fract_type_node
2317                || type == sat_unsigned_long_long_fract_type_node
2318                || type == unsigned_long_long_accum_type_node
2319                || type == sat_unsigned_long_long_accum_type_node)
2320         write_char ('y');
2321       else
2322         sorry ("mangling unknown fixed point type");
2323       write_unsigned_number (GET_MODE_FBIT (TYPE_MODE (type)));
2324       if (TYPE_SATURATING (type))
2325         write_char ('s');
2326       else
2327         write_char ('n');
2328       break;
2329
2330     default:
2331       gcc_unreachable ();
2332     }
2333 }
2334
2335 /* Non-terminal <function-type>.  NODE is a FUNCTION_TYPE or
2336    METHOD_TYPE.  The return type is mangled before the parameter
2337    types.
2338
2339      <function-type> ::= F [Y] <bare-function-type> [<ref-qualifier>] E   */
2340
2341 static void
2342 write_function_type (const tree type)
2343 {
2344   MANGLE_TRACE_TREE ("function-type", type);
2345
2346   /* For a pointer to member function, the function type may have
2347      cv-qualifiers, indicating the quals for the artificial 'this'
2348      parameter.  */
2349   if (TREE_CODE (type) == METHOD_TYPE)
2350     {
2351       /* The first parameter must be a POINTER_TYPE pointing to the
2352          `this' parameter.  */
2353       tree this_type = class_of_this_parm (type);
2354       write_CV_qualifiers_for_type (this_type);
2355     }
2356
2357   write_char ('F');
2358   /* We don't track whether or not a type is `extern "C"'.  Note that
2359      you can have an `extern "C"' function that does not have
2360      `extern "C"' type, and vice versa:
2361
2362        extern "C" typedef void function_t();
2363        function_t f; // f has C++ linkage, but its type is
2364                      // `extern "C"'
2365
2366        typedef void function_t();
2367        extern "C" function_t f; // Vice versa.
2368
2369      See [dcl.link].  */
2370   write_bare_function_type (type, /*include_return_type_p=*/1,
2371                             /*decl=*/NULL);
2372   if (FUNCTION_REF_QUALIFIED (type))
2373     {
2374       if (FUNCTION_RVALUE_QUALIFIED (type))
2375         write_char ('O');
2376       else
2377         write_char ('R');
2378     }
2379   write_char ('E');
2380 }
2381
2382 /* Non-terminal <bare-function-type>.  TYPE is a FUNCTION_TYPE or
2383    METHOD_TYPE.  If INCLUDE_RETURN_TYPE is nonzero, the return value
2384    is mangled before the parameter types.  If non-NULL, DECL is
2385    FUNCTION_DECL for the function whose type is being emitted.
2386
2387    If DECL is a member of a Java type, then a literal 'J'
2388    is output and the return type is mangled as if INCLUDE_RETURN_TYPE
2389    were nonzero.
2390
2391      <bare-function-type> ::= [J]</signature/ type>+  */
2392
2393 static void
2394 write_bare_function_type (const tree type, const int include_return_type_p,
2395                           const tree decl)
2396 {
2397   int java_method_p;
2398
2399   MANGLE_TRACE_TREE ("bare-function-type", type);
2400
2401   /* Detect Java methods and emit special encoding.  */
2402   if (decl != NULL
2403       && DECL_FUNCTION_MEMBER_P (decl)
2404       && TYPE_FOR_JAVA (DECL_CONTEXT (decl))
2405       && !DECL_CONSTRUCTOR_P (decl)
2406       && !DECL_DESTRUCTOR_P (decl)
2407       && !DECL_CONV_FN_P (decl))
2408     {
2409       java_method_p = 1;
2410       write_char ('J');
2411     }
2412   else
2413     {
2414       java_method_p = 0;
2415     }
2416
2417   /* Mangle the return type, if requested.  */
2418   if (include_return_type_p || java_method_p)
2419     write_type (TREE_TYPE (type));
2420
2421   /* Now mangle the types of the arguments.  */
2422   ++G.parm_depth;
2423   write_method_parms (TYPE_ARG_TYPES (type),
2424                       TREE_CODE (type) == METHOD_TYPE,
2425                       decl);
2426   --G.parm_depth;
2427 }
2428
2429 /* Write the mangled representation of a method parameter list of
2430    types given in PARM_TYPES.  If METHOD_P is nonzero, the function is
2431    considered a non-static method, and the this parameter is omitted.
2432    If non-NULL, DECL is the FUNCTION_DECL for the function whose
2433    parameters are being emitted.  */
2434
2435 static void
2436 write_method_parms (tree parm_types, const int method_p, const tree decl)
2437 {
2438   tree first_parm_type;
2439   tree parm_decl = decl ? DECL_ARGUMENTS (decl) : NULL_TREE;
2440
2441   /* Assume this parameter type list is variable-length.  If it ends
2442      with a void type, then it's not.  */
2443   int varargs_p = 1;
2444
2445   /* If this is a member function, skip the first arg, which is the
2446      this pointer.
2447        "Member functions do not encode the type of their implicit this
2448        parameter."
2449
2450      Similarly, there's no need to mangle artificial parameters, like
2451      the VTT parameters for constructors and destructors.  */
2452   if (method_p)
2453     {
2454       parm_types = TREE_CHAIN (parm_types);
2455       parm_decl = parm_decl ? DECL_CHAIN (parm_decl) : NULL_TREE;
2456
2457       while (parm_decl && DECL_ARTIFICIAL (parm_decl))
2458         {
2459           parm_types = TREE_CHAIN (parm_types);
2460           parm_decl = DECL_CHAIN (parm_decl);
2461         }
2462     }
2463
2464   for (first_parm_type = parm_types;
2465        parm_types;
2466        parm_types = TREE_CHAIN (parm_types))
2467     {
2468       tree parm = TREE_VALUE (parm_types);
2469       if (parm == void_type_node)
2470         {
2471           /* "Empty parameter lists, whether declared as () or
2472              conventionally as (void), are encoded with a void parameter
2473              (v)."  */
2474           if (parm_types == first_parm_type)
2475             write_type (parm);
2476           /* If the parm list is terminated with a void type, it's
2477              fixed-length.  */
2478           varargs_p = 0;
2479           /* A void type better be the last one.  */
2480           gcc_assert (TREE_CHAIN (parm_types) == NULL);
2481         }
2482       else
2483         write_type (parm);
2484     }
2485
2486   if (varargs_p)
2487     /* <builtin-type> ::= z  # ellipsis  */
2488     write_char ('z');
2489 }
2490
2491 /* <class-enum-type> ::= <name>  */
2492
2493 static void
2494 write_class_enum_type (const tree type)
2495 {
2496   write_name (TYPE_NAME (type), /*ignore_local_scope=*/0);
2497 }
2498
2499 /* Non-terminal <template-args>.  ARGS is a TREE_VEC of template
2500    arguments.
2501
2502      <template-args> ::= I <template-arg>* E  */
2503
2504 static void
2505 write_template_args (tree args)
2506 {
2507   int i;
2508   int length = 0;
2509
2510   MANGLE_TRACE_TREE ("template-args", args);
2511
2512   write_char ('I');
2513
2514   if (args)
2515     length = TREE_VEC_LENGTH (args);
2516
2517   if (args && TREE_CODE (TREE_VEC_ELT (args, 0)) == TREE_VEC)
2518     {
2519       /* We have nested template args.  We want the innermost template
2520          argument list.  */
2521       args = TREE_VEC_ELT (args, length - 1);
2522       length = TREE_VEC_LENGTH (args);
2523     }
2524   for (i = 0; i < length; ++i)
2525     write_template_arg (TREE_VEC_ELT (args, i));
2526
2527   write_char ('E');
2528 }
2529
2530 /* Write out the
2531    <unqualified-name>
2532    <unqualified-name> <template-args>
2533    part of SCOPE_REF or COMPONENT_REF mangling.  */
2534
2535 static void
2536 write_member_name (tree member)
2537 {
2538   if (identifier_p (member))
2539     write_unqualified_id (member);
2540   else if (DECL_P (member))
2541     write_unqualified_name (member);
2542   else if (TREE_CODE (member) == TEMPLATE_ID_EXPR)
2543     {
2544       tree name = TREE_OPERAND (member, 0);
2545       if (TREE_CODE (name) == OVERLOAD)
2546         name = OVL_FUNCTION (name);
2547       write_member_name (name);
2548       write_template_args (TREE_OPERAND (member, 1));
2549     }
2550   else
2551     write_expression (member);
2552 }
2553
2554 /* <expression> ::= <unary operator-name> <expression>
2555                 ::= <binary operator-name> <expression> <expression>
2556                 ::= <expr-primary>
2557
2558    <expr-primary> ::= <template-param>
2559                   ::= L <type> <value number> E         # literal
2560                   ::= L <mangled-name> E                # external name
2561                   ::= st <type>                         # sizeof
2562                   ::= sr <type> <unqualified-name>      # dependent name
2563                   ::= sr <type> <unqualified-name> <template-args> */
2564
2565 static void
2566 write_expression (tree expr)
2567 {
2568   enum tree_code code = TREE_CODE (expr);
2569
2570   /* Skip NOP_EXPRs.  They can occur when (say) a pointer argument
2571      is converted (via qualification conversions) to another
2572      type.  */
2573   while (TREE_CODE (expr) == NOP_EXPR
2574          /* Parentheses aren't mangled.  */
2575          || code == PAREN_EXPR
2576          || TREE_CODE (expr) == NON_LVALUE_EXPR)
2577     {
2578       expr = TREE_OPERAND (expr, 0);
2579       code = TREE_CODE (expr);
2580     }
2581
2582   if (code == BASELINK
2583       && (!type_unknown_p (expr)
2584           || !BASELINK_QUALIFIED_P (expr)))
2585     {
2586       expr = BASELINK_FUNCTIONS (expr);
2587       code = TREE_CODE (expr);
2588     }
2589
2590   /* Handle pointers-to-members by making them look like expression
2591      nodes.  */
2592   if (code == PTRMEM_CST)
2593     {
2594       expr = build_nt (ADDR_EXPR,
2595                        build_qualified_name (/*type=*/NULL_TREE,
2596                                              PTRMEM_CST_CLASS (expr),
2597                                              PTRMEM_CST_MEMBER (expr),
2598                                              /*template_p=*/false));
2599       code = TREE_CODE (expr);
2600     }
2601
2602   /* Handle template parameters.  */
2603   if (code == TEMPLATE_TYPE_PARM
2604       || code == TEMPLATE_TEMPLATE_PARM
2605       || code == BOUND_TEMPLATE_TEMPLATE_PARM
2606       || code == TEMPLATE_PARM_INDEX)
2607     write_template_param (expr);
2608   /* Handle literals.  */
2609   else if (TREE_CODE_CLASS (code) == tcc_constant
2610            || code == CONST_DECL)
2611     write_template_arg_literal (expr);
2612   else if (code == PARM_DECL && DECL_ARTIFICIAL (expr))
2613     {
2614       gcc_assert (!strcmp ("this", IDENTIFIER_POINTER (DECL_NAME (expr))));
2615       write_string ("fpT");
2616     }
2617   else if (code == PARM_DECL)
2618     {
2619       /* A function parameter used in a late-specified return type.  */
2620       int index = DECL_PARM_INDEX (expr);
2621       int level = DECL_PARM_LEVEL (expr);
2622       int delta = G.parm_depth - level + 1;
2623       gcc_assert (index >= 1);
2624       write_char ('f');
2625       if (delta != 0)
2626         {
2627           if (abi_version_at_least (5))
2628             {
2629               /* Let L be the number of function prototype scopes from the
2630                  innermost one (in which the parameter reference occurs) up
2631                  to (and including) the one containing the declaration of
2632                  the referenced parameter.  If the parameter declaration
2633                  clause of the innermost function prototype scope has been
2634                  completely seen, it is not counted (in that case -- which
2635                  is perhaps the most common -- L can be zero).  */
2636               write_char ('L');
2637               write_unsigned_number (delta - 1);
2638             }
2639           if (abi_version_crosses (5))
2640             G.need_abi_warning = true;
2641         }
2642       write_char ('p');
2643       write_compact_number (index - 1);
2644     }
2645   else if (DECL_P (expr))
2646     {
2647       write_char ('L');
2648       write_mangled_name (expr, false);
2649       write_char ('E');
2650     }
2651   else if (TREE_CODE (expr) == SIZEOF_EXPR
2652            && SIZEOF_EXPR_TYPE_P (expr))
2653     {
2654       write_string ("st");
2655       write_type (TREE_TYPE (TREE_OPERAND (expr, 0)));
2656     }
2657   else if (TREE_CODE (expr) == SIZEOF_EXPR
2658            && TYPE_P (TREE_OPERAND (expr, 0)))
2659     {
2660       write_string ("st");
2661       write_type (TREE_OPERAND (expr, 0));
2662     }
2663   else if (TREE_CODE (expr) == ALIGNOF_EXPR
2664            && TYPE_P (TREE_OPERAND (expr, 0)))
2665     {
2666       write_string ("at");
2667       write_type (TREE_OPERAND (expr, 0));
2668     }
2669   else if (code == SCOPE_REF
2670            || code == BASELINK)
2671     {
2672       tree scope, member;
2673       if (code == SCOPE_REF)
2674         {
2675           scope = TREE_OPERAND (expr, 0);
2676           member = TREE_OPERAND (expr, 1);
2677         }
2678       else
2679         {
2680           scope = BINFO_TYPE (BASELINK_ACCESS_BINFO (expr));
2681           member = BASELINK_FUNCTIONS (expr);
2682         }
2683
2684       /* If the MEMBER is a real declaration, then the qualifying
2685          scope was not dependent.  Ideally, we would not have a
2686          SCOPE_REF in those cases, but sometimes we do.  If the second
2687          argument is a DECL, then the name must not have been
2688          dependent.  */
2689       if (DECL_P (member))
2690         write_expression (member);
2691       else
2692         {
2693           write_string ("sr");
2694           write_type (scope);
2695           write_member_name (member);
2696         }
2697     }
2698   else if (INDIRECT_REF_P (expr)
2699            && TREE_TYPE (TREE_OPERAND (expr, 0))
2700            && TREE_CODE (TREE_TYPE (TREE_OPERAND (expr, 0))) == REFERENCE_TYPE)
2701     {
2702       write_expression (TREE_OPERAND (expr, 0));
2703     }
2704   else if (identifier_p (expr))
2705     {
2706       /* An operator name appearing as a dependent name needs to be
2707          specially marked to disambiguate between a use of the operator
2708          name and a use of the operator in an expression.  */
2709       if (IDENTIFIER_OPNAME_P (expr))
2710         write_string ("on");
2711       write_unqualified_id (expr);
2712     }
2713   else if (TREE_CODE (expr) == TEMPLATE_ID_EXPR)
2714     {
2715       tree fn = TREE_OPERAND (expr, 0);
2716       if (is_overloaded_fn (fn))
2717         fn = DECL_NAME (get_first_fn (fn));
2718       if (IDENTIFIER_OPNAME_P (fn))
2719         write_string ("on");
2720       write_unqualified_id (fn);
2721       write_template_args (TREE_OPERAND (expr, 1));
2722     }
2723   else if (TREE_CODE (expr) == MODOP_EXPR)
2724     {
2725       enum tree_code subop = TREE_CODE (TREE_OPERAND (expr, 1));
2726       const char *name = (assignment_operator_name_info[(int) subop]
2727                           .mangled_name);
2728       write_string (name);
2729       write_expression (TREE_OPERAND (expr, 0));
2730       write_expression (TREE_OPERAND (expr, 2));
2731     }
2732   else if (code == NEW_EXPR || code == VEC_NEW_EXPR)
2733     {
2734       /* ::= [gs] nw <expression>* _ <type> E
2735          ::= [gs] nw <expression>* _ <type> <initializer>
2736          ::= [gs] na <expression>* _ <type> E
2737          ::= [gs] na <expression>* _ <type> <initializer>
2738          <initializer> ::= pi <expression>* E  */
2739       tree placement = TREE_OPERAND (expr, 0);
2740       tree type = TREE_OPERAND (expr, 1);
2741       tree nelts = TREE_OPERAND (expr, 2);
2742       tree init = TREE_OPERAND (expr, 3);
2743       tree t;
2744
2745       gcc_assert (code == NEW_EXPR);
2746       if (TREE_OPERAND (expr, 2))
2747         code = VEC_NEW_EXPR;
2748
2749       if (NEW_EXPR_USE_GLOBAL (expr))
2750         write_string ("gs");
2751
2752       write_string (operator_name_info[(int) code].mangled_name);
2753
2754       for (t = placement; t; t = TREE_CHAIN (t))
2755         write_expression (TREE_VALUE (t));
2756
2757       write_char ('_');
2758
2759       if (nelts)
2760         {
2761           tree domain;
2762           ++processing_template_decl;
2763           domain = compute_array_index_type (NULL_TREE, nelts,
2764                                              tf_warning_or_error);
2765           type = build_cplus_array_type (type, domain);
2766           --processing_template_decl;
2767         }
2768       write_type (type);
2769
2770       if (init && TREE_CODE (init) == TREE_LIST
2771           && DIRECT_LIST_INIT_P (TREE_VALUE (init)))
2772         write_expression (TREE_VALUE (init));
2773       else
2774         {
2775           if (init)
2776             write_string ("pi");
2777           if (init && init != void_node)
2778             for (t = init; t; t = TREE_CHAIN (t))
2779               write_expression (TREE_VALUE (t));
2780           write_char ('E');
2781         }
2782     }
2783   else if (code == DELETE_EXPR || code == VEC_DELETE_EXPR)
2784     {
2785       gcc_assert (code == DELETE_EXPR);
2786       if (DELETE_EXPR_USE_VEC (expr))
2787         code = VEC_DELETE_EXPR;
2788
2789       if (DELETE_EXPR_USE_GLOBAL (expr))
2790         write_string ("gs");
2791
2792       write_string (operator_name_info[(int) code].mangled_name);
2793
2794       write_expression (TREE_OPERAND (expr, 0));
2795     }
2796   else if (code == THROW_EXPR)
2797     {
2798       tree op = TREE_OPERAND (expr, 0);
2799       if (op)
2800         {
2801           write_string ("tw");
2802           write_expression (op);
2803         }
2804       else
2805         write_string ("tr");
2806     }
2807   else if (code == CONSTRUCTOR)
2808     {
2809       vec<constructor_elt, va_gc> *elts = CONSTRUCTOR_ELTS (expr);
2810       unsigned i; tree val;
2811
2812       if (BRACE_ENCLOSED_INITIALIZER_P (expr))
2813         write_string ("il");
2814       else
2815         {
2816           write_string ("tl");
2817           write_type (TREE_TYPE (expr));
2818         }
2819       FOR_EACH_CONSTRUCTOR_VALUE (elts, i, val)
2820         write_expression (val);
2821       write_char ('E');
2822     }
2823   else if (dependent_name (expr))
2824     {
2825       write_unqualified_id (dependent_name (expr));
2826     }
2827   else
2828     {
2829       int i, len;
2830       const char *name;
2831
2832       /* When we bind a variable or function to a non-type template
2833          argument with reference type, we create an ADDR_EXPR to show
2834          the fact that the entity's address has been taken.  But, we
2835          don't actually want to output a mangling code for the `&'.  */
2836       if (TREE_CODE (expr) == ADDR_EXPR
2837           && TREE_TYPE (expr)
2838           && TREE_CODE (TREE_TYPE (expr)) == REFERENCE_TYPE)
2839         {
2840           expr = TREE_OPERAND (expr, 0);
2841           if (DECL_P (expr))
2842             {
2843               write_expression (expr);
2844               return;
2845             }
2846
2847           code = TREE_CODE (expr);
2848         }
2849
2850       if (code == COMPONENT_REF)
2851         {
2852           tree ob = TREE_OPERAND (expr, 0);
2853
2854           if (TREE_CODE (ob) == ARROW_EXPR)
2855             {
2856               write_string (operator_name_info[(int)code].mangled_name);
2857               ob = TREE_OPERAND (ob, 0);
2858             }
2859           else
2860             write_string ("dt");
2861
2862           write_expression (ob);
2863           write_member_name (TREE_OPERAND (expr, 1));
2864           return;
2865         }
2866
2867       /* If it wasn't any of those, recursively expand the expression.  */
2868       name = operator_name_info[(int) code].mangled_name;
2869
2870       /* We used to mangle const_cast and static_cast like a C cast.  */
2871       if (code == CONST_CAST_EXPR
2872           || code == STATIC_CAST_EXPR)
2873         {
2874           if (abi_version_crosses (6))
2875             G.need_abi_warning = 1;
2876           if (!abi_version_at_least (6))
2877             name = operator_name_info[CAST_EXPR].mangled_name;
2878         }
2879
2880       if (name == NULL)
2881         {
2882           switch (code)
2883             {
2884             case TRAIT_EXPR:
2885               error ("use of built-in trait %qE in function signature; "
2886                      "use library traits instead", expr);
2887               break;
2888
2889             default:
2890               sorry ("mangling %C", code);
2891               break;
2892             }
2893           return;
2894         }
2895       else
2896         write_string (name);
2897
2898       switch (code)
2899         {
2900         case CALL_EXPR:
2901           {
2902             tree fn = CALL_EXPR_FN (expr);
2903
2904             if (TREE_CODE (fn) == ADDR_EXPR)
2905               fn = TREE_OPERAND (fn, 0);
2906
2907             /* Mangle a dependent name as the name, not whatever happens to
2908                be the first function in the overload set.  */
2909             if ((TREE_CODE (fn) == FUNCTION_DECL
2910                  || TREE_CODE (fn) == OVERLOAD)
2911                 && type_dependent_expression_p_push (expr))
2912               fn = DECL_NAME (get_first_fn (fn));
2913
2914             write_expression (fn);
2915           }
2916
2917           for (i = 0; i < call_expr_nargs (expr); ++i)
2918             write_expression (CALL_EXPR_ARG (expr, i));
2919           write_char ('E');
2920           break;
2921
2922         case CAST_EXPR:
2923           write_type (TREE_TYPE (expr));
2924           if (list_length (TREE_OPERAND (expr, 0)) == 1)
2925             write_expression (TREE_VALUE (TREE_OPERAND (expr, 0)));
2926           else
2927             {
2928               tree args = TREE_OPERAND (expr, 0);
2929               write_char ('_');
2930               for (; args; args = TREE_CHAIN (args))
2931                 write_expression (TREE_VALUE (args));
2932               write_char ('E');
2933             }
2934           break;
2935
2936         case DYNAMIC_CAST_EXPR:
2937         case REINTERPRET_CAST_EXPR:
2938         case STATIC_CAST_EXPR:
2939         case CONST_CAST_EXPR:
2940           write_type (TREE_TYPE (expr));
2941           write_expression (TREE_OPERAND (expr, 0));
2942           break;
2943
2944         case PREINCREMENT_EXPR:
2945         case PREDECREMENT_EXPR:
2946           if (abi_version_at_least (6))
2947             write_char ('_');
2948           if (abi_version_crosses (6))
2949             G.need_abi_warning = 1;
2950           /* Fall through.  */
2951
2952         default:
2953           /* In the middle-end, some expressions have more operands than
2954              they do in templates (and mangling).  */
2955           len = cp_tree_operand_length (expr);
2956
2957           for (i = 0; i < len; ++i)
2958             {
2959               tree operand = TREE_OPERAND (expr, i);
2960               /* As a GNU extension, the middle operand of a
2961                  conditional may be omitted.  Since expression
2962                  manglings are supposed to represent the input token
2963                  stream, there's no good way to mangle such an
2964                  expression without extending the C++ ABI.  */
2965               if (code == COND_EXPR && i == 1 && !operand)
2966                 {
2967                   error ("omitted middle operand to %<?:%> operand "
2968                          "cannot be mangled");
2969                   continue;
2970                 }
2971               write_expression (operand);
2972             }
2973         }
2974     }
2975 }
2976
2977 /* Literal subcase of non-terminal <template-arg>.
2978
2979      "Literal arguments, e.g. "A<42L>", are encoded with their type
2980      and value. Negative integer values are preceded with "n"; for
2981      example, "A<-42L>" becomes "1AILln42EE". The bool value false is
2982      encoded as 0, true as 1."  */
2983
2984 static void
2985 write_template_arg_literal (const tree value)
2986 {
2987   write_char ('L');
2988   write_type (TREE_TYPE (value));
2989
2990   /* Write a null member pointer value as (type)0, regardless of its
2991      real representation.  */
2992   if (null_member_pointer_value_p (value))
2993     write_integer_cst (integer_zero_node);
2994   else
2995     switch (TREE_CODE (value))
2996       {
2997       case CONST_DECL:
2998         write_integer_cst (DECL_INITIAL (value));
2999         break;
3000
3001       case INTEGER_CST:
3002         gcc_assert (!same_type_p (TREE_TYPE (value), boolean_type_node)
3003                     || integer_zerop (value) || integer_onep (value));
3004         write_integer_cst (value);
3005         break;
3006
3007       case REAL_CST:
3008         write_real_cst (value);
3009         break;
3010
3011       case COMPLEX_CST:
3012         if (TREE_CODE (TREE_REALPART (value)) == INTEGER_CST
3013             && TREE_CODE (TREE_IMAGPART (value)) == INTEGER_CST)
3014           {
3015             write_integer_cst (TREE_REALPART (value));
3016             write_char ('_');
3017             write_integer_cst (TREE_IMAGPART (value));
3018           }
3019         else if (TREE_CODE (TREE_REALPART (value)) == REAL_CST
3020                  && TREE_CODE (TREE_IMAGPART (value)) == REAL_CST)
3021           {
3022             write_real_cst (TREE_REALPART (value));
3023             write_char ('_');
3024             write_real_cst (TREE_IMAGPART (value));
3025           }
3026         else
3027           gcc_unreachable ();
3028         break;
3029
3030       case STRING_CST:
3031         sorry ("string literal in function template signature");
3032         break;
3033
3034       default:
3035         gcc_unreachable ();
3036       }
3037
3038   write_char ('E');
3039 }
3040
3041 /* Non-terminal <template-arg>.
3042
3043      <template-arg> ::= <type>                          # type
3044                     ::= L <type> </value/ number> E     # literal
3045                     ::= LZ <name> E                     # external name
3046                     ::= X <expression> E                # expression  */
3047
3048 static void
3049 write_template_arg (tree node)
3050 {
3051   enum tree_code code = TREE_CODE (node);
3052
3053   MANGLE_TRACE_TREE ("template-arg", node);
3054
3055   /* A template template parameter's argument list contains TREE_LIST
3056      nodes of which the value field is the actual argument.  */
3057   if (code == TREE_LIST)
3058     {
3059       node = TREE_VALUE (node);
3060       /* If it's a decl, deal with its type instead.  */
3061       if (DECL_P (node))
3062         {
3063           node = TREE_TYPE (node);
3064           code = TREE_CODE (node);
3065         }
3066     }
3067
3068   if (TREE_CODE (node) == NOP_EXPR
3069       && TREE_CODE (TREE_TYPE (node)) == REFERENCE_TYPE)
3070     {
3071       /* Template parameters can be of reference type. To maintain
3072          internal consistency, such arguments use a conversion from
3073          address of object to reference type.  */
3074       gcc_assert (TREE_CODE (TREE_OPERAND (node, 0)) == ADDR_EXPR);
3075       node = TREE_OPERAND (TREE_OPERAND (node, 0), 0);
3076     }
3077
3078   if (TREE_CODE (node) == BASELINK
3079       && !type_unknown_p (node))
3080     {
3081       if (abi_version_at_least (6))
3082         node = BASELINK_FUNCTIONS (node);
3083       if (abi_version_crosses (6))
3084         /* We wrongly wrapped a class-scope function in X/E.  */
3085         G.need_abi_warning = 1;
3086     }
3087
3088   if (ARGUMENT_PACK_P (node))
3089     {
3090       /* Expand the template argument pack. */
3091       tree args = ARGUMENT_PACK_ARGS (node);
3092       int i, length = TREE_VEC_LENGTH (args);
3093       if (abi_version_at_least (6))
3094         write_char ('J');
3095       else
3096         write_char ('I');
3097       if (abi_version_crosses (6))
3098         G.need_abi_warning = 1;
3099       for (i = 0; i < length; ++i)
3100         write_template_arg (TREE_VEC_ELT (args, i));
3101       write_char ('E');
3102     }
3103   else if (TYPE_P (node))
3104     write_type (node);
3105   else if (code == TEMPLATE_DECL)
3106     /* A template appearing as a template arg is a template template arg.  */
3107     write_template_template_arg (node);
3108   else if ((TREE_CODE_CLASS (code) == tcc_constant && code != PTRMEM_CST)
3109            || code == CONST_DECL
3110            || null_member_pointer_value_p (node))
3111     write_template_arg_literal (node);
3112   else if (DECL_P (node))
3113     {
3114       write_char ('L');
3115       /* Until ABI version 3, the underscore before the mangled name
3116          was incorrectly omitted.  */
3117       if (!abi_version_at_least (3))
3118         write_char ('Z');
3119       else
3120         write_string ("_Z");
3121       if (abi_version_crosses (3))
3122         G.need_abi_warning = 1;
3123       write_encoding (node);
3124       write_char ('E');
3125     }
3126   else
3127     {
3128       /* Template arguments may be expressions.  */
3129       write_char ('X');
3130       write_expression (node);
3131       write_char ('E');
3132     }
3133 }
3134
3135 /*  <template-template-arg>
3136                         ::= <name>
3137                         ::= <substitution>  */
3138
3139 static void
3140 write_template_template_arg (const tree decl)
3141 {
3142   MANGLE_TRACE_TREE ("template-template-arg", decl);
3143
3144   if (find_substitution (decl))
3145     return;
3146   write_name (decl, /*ignore_local_scope=*/0);
3147   add_substitution (decl);
3148 }
3149
3150
3151 /* Non-terminal <array-type>.  TYPE is an ARRAY_TYPE.
3152
3153      <array-type> ::= A [</dimension/ number>] _ </element/ type>
3154                   ::= A <expression> _ </element/ type>
3155
3156      "Array types encode the dimension (number of elements) and the
3157      element type. For variable length arrays, the dimension (but not
3158      the '_' separator) is omitted."  */
3159
3160 static void
3161 write_array_type (const tree type)
3162 {
3163   write_char ('A');
3164   if (TYPE_DOMAIN (type))
3165     {
3166       tree index_type;
3167       tree max;
3168
3169       index_type = TYPE_DOMAIN (type);
3170       /* The INDEX_TYPE gives the upper and lower bounds of the
3171          array.  */
3172       max = TYPE_MAX_VALUE (index_type);
3173       if (TREE_CODE (max) == INTEGER_CST)
3174         {
3175           /* The ABI specifies that we should mangle the number of
3176              elements in the array, not the largest allowed index.  */
3177           offset_int wmax = wi::to_offset (max) + 1;
3178           /* Truncate the result - this will mangle [0, SIZE_INT_MAX]
3179              number of elements as zero.  */
3180           wmax = wi::zext (wmax, TYPE_PRECISION (TREE_TYPE (max)));
3181           gcc_assert (wi::fits_uhwi_p (wmax));
3182           write_unsigned_number (wmax.to_uhwi ());
3183         }
3184       else
3185         {
3186           max = TREE_OPERAND (max, 0);
3187           write_expression (max);
3188         }
3189
3190     }
3191   write_char ('_');
3192   write_type (TREE_TYPE (type));
3193 }
3194
3195 /* Non-terminal <pointer-to-member-type> for pointer-to-member
3196    variables.  TYPE is a pointer-to-member POINTER_TYPE.
3197
3198      <pointer-to-member-type> ::= M </class/ type> </member/ type>  */
3199
3200 static void
3201 write_pointer_to_member_type (const tree type)
3202 {
3203   write_char ('M');
3204   write_type (TYPE_PTRMEM_CLASS_TYPE (type));
3205   write_type (TYPE_PTRMEM_POINTED_TO_TYPE (type));
3206 }
3207
3208 /* Non-terminal <template-param>.  PARM is a TEMPLATE_TYPE_PARM,
3209    TEMPLATE_TEMPLATE_PARM, BOUND_TEMPLATE_TEMPLATE_PARM or a
3210    TEMPLATE_PARM_INDEX.
3211
3212      <template-param> ::= T </parameter/ number> _  */
3213
3214 static void
3215 write_template_param (const tree parm)
3216 {
3217   int parm_index;
3218
3219   MANGLE_TRACE_TREE ("template-parm", parm);
3220
3221   switch (TREE_CODE (parm))
3222     {
3223     case TEMPLATE_TYPE_PARM:
3224     case TEMPLATE_TEMPLATE_PARM:
3225     case BOUND_TEMPLATE_TEMPLATE_PARM:
3226       parm_index = TEMPLATE_TYPE_IDX (parm);
3227       break;
3228
3229     case TEMPLATE_PARM_INDEX:
3230       parm_index = TEMPLATE_PARM_IDX (parm);
3231       break;
3232
3233     default:
3234       gcc_unreachable ();
3235     }
3236
3237   write_char ('T');
3238   /* NUMBER as it appears in the mangling is (-1)-indexed, with the
3239      earliest template param denoted by `_'.  */
3240   write_compact_number (parm_index);
3241 }
3242
3243 /*  <template-template-param>
3244                         ::= <template-param>
3245                         ::= <substitution>  */
3246
3247 static void
3248 write_template_template_param (const tree parm)
3249 {
3250   tree templ = NULL_TREE;
3251
3252   /* PARM, a TEMPLATE_TEMPLATE_PARM, is an instantiation of the
3253      template template parameter.  The substitution candidate here is
3254      only the template.  */
3255   if (TREE_CODE (parm) == BOUND_TEMPLATE_TEMPLATE_PARM)
3256     {
3257       templ
3258         = TI_TEMPLATE (TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (parm));
3259       if (find_substitution (templ))
3260         return;
3261     }
3262
3263   /* <template-param> encodes only the template parameter position,
3264      not its template arguments, which is fine here.  */
3265   write_template_param (parm);
3266   if (templ)
3267     add_substitution (templ);
3268 }
3269
3270 /* Non-terminal <substitution>.
3271
3272       <substitution> ::= S <seq-id> _
3273                      ::= S_  */
3274
3275 static void
3276 write_substitution (const int seq_id)
3277 {
3278   MANGLE_TRACE ("substitution", "");
3279
3280   write_char ('S');
3281   if (seq_id > 0)
3282     write_number (seq_id - 1, /*unsigned=*/1, 36);
3283   write_char ('_');
3284 }
3285
3286 /* Start mangling ENTITY.  */
3287
3288 static inline void
3289 start_mangling (const tree entity)
3290 {
3291   G.entity = entity;
3292   G.need_abi_warning = false;
3293   obstack_free (&name_obstack, name_base);
3294   mangle_obstack = &name_obstack;
3295   name_base = obstack_alloc (&name_obstack, 0);
3296 }
3297
3298 /* Done with mangling. If WARN is true, and the name of G.entity will
3299    be mangled differently in a future version of the ABI, issue a
3300    warning.  */
3301
3302 static void
3303 finish_mangling_internal (void)
3304 {
3305   /* Clear all the substitutions.  */
3306   vec_safe_truncate (G.substitutions, 0);
3307
3308   /* Null-terminate the string.  */
3309   write_char ('\0');
3310 }
3311
3312
3313 /* Like finish_mangling_internal, but return the mangled string.  */
3314
3315 static inline const char *
3316 finish_mangling (void)
3317 {
3318   finish_mangling_internal ();
3319   return (const char *) obstack_finish (mangle_obstack);
3320 }
3321
3322 /* Like finish_mangling_internal, but return an identifier.  */
3323
3324 static tree
3325 finish_mangling_get_identifier (void)
3326 {
3327   finish_mangling_internal ();
3328   /* Don't obstack_finish here, and the next start_mangling will
3329      remove the identifier.  */
3330   return get_identifier ((const char *) obstack_base (mangle_obstack));
3331 }
3332
3333 /* Initialize data structures for mangling.  */
3334
3335 void
3336 init_mangle (void)
3337 {
3338   gcc_obstack_init (&name_obstack);
3339   name_base = obstack_alloc (&name_obstack, 0);
3340   vec_alloc (G.substitutions, 0);
3341
3342   /* Cache these identifiers for quick comparison when checking for
3343      standard substitutions.  */
3344   subst_identifiers[SUBID_ALLOCATOR] = get_identifier ("allocator");
3345   subst_identifiers[SUBID_BASIC_STRING] = get_identifier ("basic_string");
3346   subst_identifiers[SUBID_CHAR_TRAITS] = get_identifier ("char_traits");
3347   subst_identifiers[SUBID_BASIC_ISTREAM] = get_identifier ("basic_istream");
3348   subst_identifiers[SUBID_BASIC_OSTREAM] = get_identifier ("basic_ostream");
3349   subst_identifiers[SUBID_BASIC_IOSTREAM] = get_identifier ("basic_iostream");
3350 }
3351
3352 /* Generate the mangled name of DECL.  */
3353
3354 static tree
3355 mangle_decl_string (const tree decl)
3356 {
3357   tree result;
3358   location_t saved_loc = input_location;
3359   tree saved_fn = NULL_TREE;
3360   bool template_p = false;
3361
3362   /* We shouldn't be trying to mangle an uninstantiated template.  */
3363   gcc_assert (!type_dependent_expression_p (decl));
3364
3365   if (DECL_LANG_SPECIFIC (decl) && DECL_USE_TEMPLATE (decl))
3366     {
3367       struct tinst_level *tl = current_instantiation ();
3368       if ((!tl || tl->decl != decl)
3369           && push_tinst_level (decl))
3370         {
3371           template_p = true;
3372           saved_fn = current_function_decl;
3373           current_function_decl = NULL_TREE;
3374         }
3375     }
3376   input_location = DECL_SOURCE_LOCATION (decl);
3377
3378   start_mangling (decl);
3379
3380   if (TREE_CODE (decl) == TYPE_DECL)
3381     write_type (TREE_TYPE (decl));
3382   else
3383     write_mangled_name (decl, true);
3384
3385   result = finish_mangling_get_identifier ();
3386   if (DEBUG_MANGLE)
3387     fprintf (stderr, "mangle_decl_string = '%s'\n\n",
3388              IDENTIFIER_POINTER (result));
3389
3390   if (template_p)
3391     {
3392       pop_tinst_level ();
3393       current_function_decl = saved_fn;
3394     }
3395   input_location = saved_loc;
3396
3397   return result;
3398 }
3399
3400 /* Return an identifier for the external mangled name of DECL.  */
3401
3402 static tree
3403 get_mangled_id (tree decl)
3404 {
3405   tree id = mangle_decl_string (decl);
3406   return targetm.mangle_decl_assembler_name (decl, id);
3407 }
3408
3409 /* Create an identifier for the external mangled name of DECL.  */
3410
3411 void
3412 mangle_decl (const tree decl)
3413 {
3414   tree id;
3415   bool dep;
3416
3417   /* Don't bother mangling uninstantiated templates.  */
3418   ++processing_template_decl;
3419   if (TREE_CODE (decl) == TYPE_DECL)
3420     dep = dependent_type_p (TREE_TYPE (decl));
3421   else
3422     dep = (DECL_LANG_SPECIFIC (decl) && DECL_TEMPLATE_INFO (decl)
3423            && any_dependent_template_arguments_p (DECL_TI_ARGS (decl)));
3424   --processing_template_decl;
3425   if (dep)
3426     return;
3427
3428   id = get_mangled_id (decl);
3429   SET_DECL_ASSEMBLER_NAME (decl, id);
3430
3431   if (G.need_abi_warning
3432       /* Don't do this for a fake symbol we aren't going to emit anyway.  */
3433       && TREE_CODE (decl) != TYPE_DECL
3434       && !DECL_MAYBE_IN_CHARGE_CONSTRUCTOR_P (decl)
3435       && !DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (decl))
3436     {
3437       /* If the mangling will change in the future, emit an alias with the
3438          future mangled name for forward-compatibility.  */
3439       int save_ver;
3440       tree id2;
3441
3442       SET_IDENTIFIER_GLOBAL_VALUE (id, decl);
3443       if (IDENTIFIER_GLOBAL_VALUE (id) != decl)
3444         inform (DECL_SOURCE_LOCATION (decl), "a later -fabi-version= (or =0) "
3445                 "avoids this error with a change in mangling");
3446
3447       save_ver = flag_abi_version;
3448       flag_abi_version = flag_abi_compat_version;
3449       id2 = mangle_decl_string (decl);
3450       id2 = targetm.mangle_decl_assembler_name (decl, id2);
3451       flag_abi_version = save_ver;
3452
3453       if (id2 == id)
3454         return;
3455
3456       if (warn_abi)
3457         {
3458           if (flag_abi_compat_version != 0
3459               && abi_version_at_least (flag_abi_compat_version))
3460             warning (OPT_Wabi, "the mangled name of %q+D changed between "
3461                      "-fabi-version=%d (%D) and -fabi-version=%d (%D)",
3462                      G.entity, flag_abi_compat_version, id2,
3463                      flag_abi_version, id);
3464           else
3465             warning (OPT_Wabi, "the mangled name of %q+D changes between "
3466                      "-fabi-version=%d (%D) and -fabi-version=%d (%D)",
3467                      G.entity, flag_abi_version, id,
3468                      flag_abi_compat_version, id2);
3469         }
3470
3471 #ifdef ASM_OUTPUT_DEF
3472       if (flag_abi_compat_version != 0
3473           && IDENTIFIER_GLOBAL_VALUE (id2))
3474         return;
3475
3476       tree alias = make_alias_for (decl, id2);
3477       SET_IDENTIFIER_GLOBAL_VALUE (id2, alias);
3478       DECL_IGNORED_P (alias) = 1;
3479       TREE_PUBLIC (alias) = TREE_PUBLIC (decl);
3480       DECL_VISIBILITY (alias) = DECL_VISIBILITY (decl);
3481       if (vague_linkage_p (decl))
3482         DECL_WEAK (alias) = 1;
3483       if (TREE_CODE (decl) == FUNCTION_DECL)
3484         {
3485           /* Don't create an alias to an unreferenced function.  */
3486           if (struct cgraph_node *n = cgraph_get_node (decl))
3487             cgraph_same_body_alias (n, alias, decl);
3488         }
3489       else
3490         varpool_extra_name_alias (alias, decl);
3491 #endif
3492     }
3493 }
3494
3495 /* Generate the mangled representation of TYPE.  */
3496
3497 const char *
3498 mangle_type_string (const tree type)
3499 {
3500   const char *result;
3501
3502   start_mangling (type);
3503   write_type (type);
3504   result = finish_mangling ();
3505   if (DEBUG_MANGLE)
3506     fprintf (stderr, "mangle_type_string = '%s'\n\n", result);
3507   return result;
3508 }
3509
3510 /* Create an identifier for the mangled name of a special component
3511    for belonging to TYPE.  CODE is the ABI-specified code for this
3512    component.  */
3513
3514 static tree
3515 mangle_special_for_type (const tree type, const char *code)
3516 {
3517   tree result;
3518
3519   /* We don't have an actual decl here for the special component, so
3520      we can't just process the <encoded-name>.  Instead, fake it.  */
3521   start_mangling (type);
3522
3523   /* Start the mangling.  */
3524   write_string ("_Z");
3525   write_string (code);
3526
3527   /* Add the type.  */
3528   write_type (type);
3529   result = finish_mangling_get_identifier ();
3530
3531   if (DEBUG_MANGLE)
3532     fprintf (stderr, "mangle_special_for_type = %s\n\n",
3533              IDENTIFIER_POINTER (result));
3534
3535   return result;
3536 }
3537
3538 /* Create an identifier for the mangled representation of the typeinfo
3539    structure for TYPE.  */
3540
3541 tree
3542 mangle_typeinfo_for_type (const tree type)
3543 {
3544   return mangle_special_for_type (type, "TI");
3545 }
3546
3547 /* Create an identifier for the mangled name of the NTBS containing
3548    the mangled name of TYPE.  */
3549
3550 tree
3551 mangle_typeinfo_string_for_type (const tree type)
3552 {
3553   return mangle_special_for_type (type, "TS");
3554 }
3555
3556 /* Create an identifier for the mangled name of the vtable for TYPE.  */
3557
3558 tree
3559 mangle_vtbl_for_type (const tree type)
3560 {
3561   return mangle_special_for_type (type, "TV");
3562 }
3563
3564 /* Returns an identifier for the mangled name of the VTT for TYPE.  */
3565
3566 tree
3567 mangle_vtt_for_type (const tree type)
3568 {
3569   return mangle_special_for_type (type, "TT");
3570 }
3571
3572 /* Return an identifier for a construction vtable group.  TYPE is
3573    the most derived class in the hierarchy; BINFO is the base
3574    subobject for which this construction vtable group will be used.
3575
3576    This mangling isn't part of the ABI specification; in the ABI
3577    specification, the vtable group is dumped in the same COMDAT as the
3578    main vtable, and is referenced only from that vtable, so it doesn't
3579    need an external name.  For binary formats without COMDAT sections,
3580    though, we need external names for the vtable groups.
3581
3582    We use the production
3583
3584     <special-name> ::= CT <type> <offset number> _ <base type>  */
3585
3586 tree
3587 mangle_ctor_vtbl_for_type (const tree type, const tree binfo)
3588 {
3589   tree result;
3590
3591   start_mangling (type);
3592
3593   write_string ("_Z");
3594   write_string ("TC");
3595   write_type (type);
3596   write_integer_cst (BINFO_OFFSET (binfo));
3597   write_char ('_');
3598   write_type (BINFO_TYPE (binfo));
3599
3600   result = finish_mangling_get_identifier ();
3601   if (DEBUG_MANGLE)
3602     fprintf (stderr, "mangle_ctor_vtbl_for_type = %s\n\n",
3603              IDENTIFIER_POINTER (result));
3604   return result;
3605 }
3606
3607 /* Mangle a this pointer or result pointer adjustment.
3608
3609    <call-offset> ::= h <fixed offset number> _
3610                  ::= v <fixed offset number> _ <virtual offset number> _ */
3611
3612 static void
3613 mangle_call_offset (const tree fixed_offset, const tree virtual_offset)
3614 {
3615   write_char (virtual_offset ? 'v' : 'h');
3616
3617   /* For either flavor, write the fixed offset.  */
3618   write_integer_cst (fixed_offset);
3619   write_char ('_');
3620
3621   /* For a virtual thunk, add the virtual offset.  */
3622   if (virtual_offset)
3623     {
3624       write_integer_cst (virtual_offset);
3625       write_char ('_');
3626     }
3627 }
3628
3629 /* Return an identifier for the mangled name of a this-adjusting or
3630    covariant thunk to FN_DECL.  FIXED_OFFSET is the initial adjustment
3631    to this used to find the vptr.  If VIRTUAL_OFFSET is non-NULL, this
3632    is a virtual thunk, and it is the vtbl offset in
3633    bytes. THIS_ADJUSTING is nonzero for a this adjusting thunk and
3634    zero for a covariant thunk. Note, that FN_DECL might be a covariant
3635    thunk itself. A covariant thunk name always includes the adjustment
3636    for the this pointer, even if there is none.
3637
3638    <special-name> ::= T <call-offset> <base encoding>
3639                   ::= Tc <this_adjust call-offset> <result_adjust call-offset>
3640                                         <base encoding>  */
3641
3642 tree
3643 mangle_thunk (tree fn_decl, const int this_adjusting, tree fixed_offset,
3644               tree virtual_offset)
3645 {
3646   tree result;
3647
3648   start_mangling (fn_decl);
3649
3650   write_string ("_Z");
3651   write_char ('T');
3652
3653   if (!this_adjusting)
3654     {
3655       /* Covariant thunk with no this adjustment */
3656       write_char ('c');
3657       mangle_call_offset (integer_zero_node, NULL_TREE);
3658       mangle_call_offset (fixed_offset, virtual_offset);
3659     }
3660   else if (!DECL_THUNK_P (fn_decl))
3661     /* Plain this adjusting thunk.  */
3662     mangle_call_offset (fixed_offset, virtual_offset);
3663   else
3664     {
3665       /* This adjusting thunk to covariant thunk.  */
3666       write_char ('c');
3667       mangle_call_offset (fixed_offset, virtual_offset);
3668       fixed_offset = ssize_int (THUNK_FIXED_OFFSET (fn_decl));
3669       virtual_offset = THUNK_VIRTUAL_OFFSET (fn_decl);
3670       if (virtual_offset)
3671         virtual_offset = BINFO_VPTR_FIELD (virtual_offset);
3672       mangle_call_offset (fixed_offset, virtual_offset);
3673       fn_decl = THUNK_TARGET (fn_decl);
3674     }
3675
3676   /* Scoped name.  */
3677   write_encoding (fn_decl);
3678
3679   result = finish_mangling_get_identifier ();
3680   if (DEBUG_MANGLE)
3681     fprintf (stderr, "mangle_thunk = %s\n\n", IDENTIFIER_POINTER (result));
3682   return result;
3683 }
3684
3685 /* This hash table maps TYPEs to the IDENTIFIER for a conversion
3686    operator to TYPE.  The nodes are IDENTIFIERs whose TREE_TYPE is the
3687    TYPE.  */
3688
3689 static GTY ((param_is (union tree_node))) htab_t conv_type_names;
3690
3691 /* Hash a node (VAL1) in the table.  */
3692
3693 static hashval_t
3694 hash_type (const void *val)
3695 {
3696   return (hashval_t) TYPE_UID (TREE_TYPE ((const_tree) val));
3697 }
3698
3699 /* Compare VAL1 (a node in the table) with VAL2 (a TYPE).  */
3700
3701 static int
3702 compare_type (const void *val1, const void *val2)
3703 {
3704   return TREE_TYPE ((const_tree) val1) == (const_tree) val2;
3705 }
3706
3707 /* Return an identifier for the mangled unqualified name for a
3708    conversion operator to TYPE.  This mangling is not specified by the
3709    ABI spec; it is only used internally.  */
3710
3711 tree
3712 mangle_conv_op_name_for_type (const tree type)
3713 {
3714   void **slot;
3715   tree identifier;
3716
3717   if (type == error_mark_node)
3718     return error_mark_node;
3719
3720   if (conv_type_names == NULL)
3721     conv_type_names = htab_create_ggc (31, &hash_type, &compare_type, NULL);
3722
3723   slot = htab_find_slot_with_hash (conv_type_names, type,
3724                                    (hashval_t) TYPE_UID (type), INSERT);
3725   identifier = (tree)*slot;
3726   if (!identifier)
3727     {
3728       char buffer[64];
3729
3730        /* Create a unique name corresponding to TYPE.  */
3731       sprintf (buffer, "operator %lu",
3732                (unsigned long) htab_elements (conv_type_names));
3733       identifier = get_identifier (buffer);
3734       *slot = identifier;
3735
3736       /* Hang TYPE off the identifier so it can be found easily later
3737          when performing conversions.  */
3738       TREE_TYPE (identifier) = type;
3739
3740       /* Set bits on the identifier so we know later it's a conversion.  */
3741       IDENTIFIER_OPNAME_P (identifier) = 1;
3742       IDENTIFIER_TYPENAME_P (identifier) = 1;
3743     }
3744
3745   return identifier;
3746 }
3747
3748 /* Write out the appropriate string for this variable when generating
3749    another mangled name based on this one.  */
3750
3751 static void
3752 write_guarded_var_name (const tree variable)
3753 {
3754   if (DECL_NAME (variable)
3755       && strncmp (IDENTIFIER_POINTER (DECL_NAME (variable)), "_ZGR", 4) == 0)
3756     /* The name of a guard variable for a reference temporary should refer
3757        to the reference, not the temporary.  */
3758     write_string (IDENTIFIER_POINTER (DECL_NAME (variable)) + 4);
3759   else
3760     write_name (variable, /*ignore_local_scope=*/0);
3761 }
3762
3763 /* Return an identifier for the name of an initialization guard
3764    variable for indicated VARIABLE.  */
3765
3766 tree
3767 mangle_guard_variable (const tree variable)
3768 {
3769   start_mangling (variable);
3770   write_string ("_ZGV");
3771   write_guarded_var_name (variable);
3772   return finish_mangling_get_identifier ();
3773 }
3774
3775 /* Return an identifier for the name of a thread_local initialization
3776    function for VARIABLE.  */
3777
3778 tree
3779 mangle_tls_init_fn (const tree variable)
3780 {
3781   start_mangling (variable);
3782   write_string ("_ZTH");
3783   write_guarded_var_name (variable);
3784   return finish_mangling_get_identifier ();
3785 }
3786
3787 /* Return an identifier for the name of a thread_local wrapper
3788    function for VARIABLE.  */
3789
3790 #define TLS_WRAPPER_PREFIX "_ZTW"
3791
3792 tree
3793 mangle_tls_wrapper_fn (const tree variable)
3794 {
3795   start_mangling (variable);
3796   write_string (TLS_WRAPPER_PREFIX);
3797   write_guarded_var_name (variable);
3798   return finish_mangling_get_identifier ();
3799 }
3800
3801 /* Return true iff FN is a thread_local wrapper function.  */
3802
3803 bool
3804 decl_tls_wrapper_p (const tree fn)
3805 {
3806   if (TREE_CODE (fn) != FUNCTION_DECL)
3807     return false;
3808   tree name = DECL_NAME (fn);
3809   return strncmp (IDENTIFIER_POINTER (name), TLS_WRAPPER_PREFIX,
3810                   strlen (TLS_WRAPPER_PREFIX)) == 0;
3811 }
3812
3813 /* Return an identifier for the name of a temporary variable used to
3814    initialize a static reference.  This isn't part of the ABI, but we might
3815    as well call them something readable.  */
3816
3817 static GTY(()) int temp_count;
3818
3819 tree
3820 mangle_ref_init_variable (const tree variable)
3821 {
3822   start_mangling (variable);
3823   write_string ("_ZGR");
3824   write_name (variable, /*ignore_local_scope=*/0);
3825   /* Avoid name clashes with aggregate initialization of multiple
3826      references at once.  */
3827   write_unsigned_number (temp_count++);
3828   return finish_mangling_get_identifier ();
3829 }
3830 \f
3831
3832 /* Foreign language type mangling section.  */
3833
3834 /* How to write the type codes for the integer Java type.  */
3835
3836 static void
3837 write_java_integer_type_codes (const tree type)
3838 {
3839   if (type == java_int_type_node)
3840     write_char ('i');
3841   else if (type == java_short_type_node)
3842     write_char ('s');
3843   else if (type == java_byte_type_node)
3844     write_char ('c');
3845   else if (type == java_char_type_node)
3846     write_char ('w');
3847   else if (type == java_long_type_node)
3848     write_char ('x');
3849   else if (type == java_boolean_type_node)
3850     write_char ('b');
3851   else
3852     gcc_unreachable ();
3853 }
3854
3855 /* Given a CLASS_TYPE, such as a record for std::bad_exception this
3856    function generates a mangled name for the vtable map variable of
3857    the class type.  For example, if the class type is
3858    "std::bad_exception", the mangled name for the class is
3859    "St13bad_exception".  This function would generate the name
3860    "_ZN4_VTVISt13bad_exceptionE12__vtable_mapE", which unmangles as:
3861    "_VTV<std::bad_exception>::__vtable_map".  */
3862
3863
3864 char *
3865 get_mangled_vtable_map_var_name (tree class_type)
3866 {
3867   char *var_name = NULL;
3868   const char *prefix = "_ZN4_VTVI";
3869   const char *postfix = "E12__vtable_mapE";
3870
3871   gcc_assert (TREE_CODE (class_type) == RECORD_TYPE);
3872
3873   tree class_id = DECL_ASSEMBLER_NAME (TYPE_NAME (class_type));
3874   unsigned int len = strlen (IDENTIFIER_POINTER (class_id)) +
3875                      strlen (prefix) +
3876                      strlen (postfix) + 1;
3877
3878   var_name = (char *) xmalloc (len);
3879
3880   sprintf (var_name, "%s%s%s", prefix, IDENTIFIER_POINTER (class_id), postfix);
3881
3882   return var_name;
3883 }
3884
3885 #include "gt-cp-mangle.h"