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