1 /*
   2  * Ported from LLVM's libcxxabi trunk/src/cxa_demangle.cpp
   3  * LICENSE.TXT contents is available as ../THIRDPARTYLICENSE
   4  *
   5  *                     The LLVM Compiler Infrastructure
   6  *
   7  * This file is dual licensed under the MIT and the University of Illinois Open
   8  * Source Licenses. See LICENSE.TXT for details.
   9  *
  10  */
  11 
  12 /*
  13  * Copyright 2018 Jason King.
  14  */
  15 #include <ctype.h>
  16 #include <errno.h>
  17 #include <locale.h>
  18 #include <note.h>
  19 #include <string.h>
  20 #include <setjmp.h>
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <sys/isa_defs.h>
  24 #include <sys/debug.h>
  25 #include "demangle-sys.h"
  26 #include "demangle_int.h"
  27 #include "cxx.h"
  28 
  29 #ifndef ARRAY_SIZE
  30 #define ARRAY_SIZE(x) (sizeof (x) / sizeof (x[0]))
  31 #endif
  32 
  33 #define CPP_QUAL_CONST          (1U)
  34 #define CPP_QUAL_VOLATILE       (2U)
  35 #define CPP_QUAL_RESTRICT       (4U)
  36 
  37 typedef struct cpp_db_s {
  38         sysdem_ops_t    *cpp_ops;
  39         jmp_buf         cpp_jmp;
  40         name_t          cpp_name;
  41         sub_t           cpp_subs;
  42         templ_t         cpp_templ;
  43         unsigned        cpp_cv;
  44         unsigned        cpp_ref;
  45         unsigned        cpp_depth;
  46         boolean_t       cpp_parsed_ctor_dtor_cv;
  47         boolean_t       cpp_tag_templates;
  48         boolean_t       cpp_fix_forward_references;
  49         boolean_t       cpp_try_to_parse_template_args;
  50         locale_t        cpp_loc;
  51 } cpp_db_t;
  52 
  53 #define CK(x)                                           \
  54         do {                                            \
  55                 if (!(x)) {                             \
  56                         longjmp(db->cpp_jmp, 1);     \
  57                 }                                       \
  58         NOTE(CONSTCOND)                                 \
  59         } while (0)
  60 
  61 #define TOP_L(db) (&(name_top(&(db)->cpp_name)->strp_l))
  62 #define RLEN(f, l) ((size_t)((l) - (f)))
  63 #define NAMT(db, n) (nlen(db) - n)
  64 
  65 static inline boolean_t is_xdigit(int);
  66 
  67 static boolean_t nempty(cpp_db_t *);
  68 static size_t nlen(cpp_db_t *);
  69 static void nadd_l(cpp_db_t *, const char *, size_t);
  70 static void njoin(cpp_db_t *, size_t, const char *);
  71 static void nfmt(cpp_db_t *, const char *, const char *);
  72 
  73 static void save_top(cpp_db_t *, size_t);
  74 static void sub(cpp_db_t *, size_t);
  75 
  76 static boolean_t tempty(const cpp_db_t *);
  77 static size_t ttlen(const cpp_db_t *);
  78 
  79 static void tsub(cpp_db_t *, size_t);
  80 static void tpush(cpp_db_t *);
  81 static void tpop(cpp_db_t *);
  82 static void tsave(cpp_db_t *, size_t);
  83 
  84 static boolean_t db_init(cpp_db_t *, sysdem_ops_t *);
  85 static void db_fini(cpp_db_t *);
  86 static void dump(cpp_db_t *, FILE *);
  87 
  88 static void demangle(const char *, const char *, cpp_db_t *);
  89 
  90 static const char *parse_type(const char *, const char *, cpp_db_t *);
  91 static const char *parse_builtin_type(const char *, const char *, cpp_db_t *);
  92 static const char *parse_qual_type(const char *, const char *, cpp_db_t *);
  93 static const char *parse_encoding(const char *, const char *, cpp_db_t *);
  94 static const char *parse_dot_suffix(const char *, const char *, cpp_db_t *);
  95 static const char *parse_block_invoke(const char *, const char *, cpp_db_t *);
  96 static const char *parse_special_name(const char *, const char *, cpp_db_t *);
  97 static const char *parse_name(const char *, const char *, boolean_t *,
  98     cpp_db_t *);
  99 static const char *parse_call_offset(const char *, const char *, locale_t);
 100 static const char *parse_number(const char *, const char *, locale_t);
 101 static const char *parse_nested_name(const char *, const char *, boolean_t *,
 102     cpp_db_t *);
 103 static const char *parse_local_name(const char *, const char *, boolean_t *,
 104     cpp_db_t *);
 105 static const char *parse_unscoped_name(const char *, const char *, cpp_db_t *);
 106 static const char *parse_template_args(const char *, const char *, cpp_db_t *);
 107 static const char *parse_substitution(const char *, const char *, cpp_db_t *);
 108 static const char *parse_discriminator(const char *, const char *, locale_t);
 109 static const char *parse_cv_qualifiers(const char *, const char *, unsigned *);
 110 static const char *parse_template_param(const char *, const char *, cpp_db_t *);
 111 static const char *parse_decltype(const char *, const char *, cpp_db_t *);
 112 static const char *parse_template_args(const char *, const char *, cpp_db_t *);
 113 static const char *parse_unqualified_name(const char *, const char *,
 114     cpp_db_t *);
 115 static const char *parse_template_arg(const char *, const char *, cpp_db_t *);
 116 static const char *parse_expression(const char *, const char *, cpp_db_t *);
 117 static const char *parse_expr_primary(const char *, const char *, cpp_db_t *);
 118 static const char *parse_binary_expr(const char *, const char *,
 119     const char *, cpp_db_t *);
 120 static const char *parse_prefix_expr(const char *, const char *,
 121     const char *, cpp_db_t *);
 122 static const char *parse_gs(const char *, const char *, cpp_db_t *);
 123 static const char *parse_idx_expr(const char *, const char *, cpp_db_t *);
 124 static const char *parse_mm_expr(const char *, const char *, cpp_db_t *);
 125 static const char *parse_pp_expr(const char *, const char *, cpp_db_t *);
 126 static const char *parse_trinary_expr(const char *, const char *, cpp_db_t *);
 127 static const char *parse_new_expr(const char *, const char *, cpp_db_t *);
 128 static const char *parse_del_expr(const char *, const char *, cpp_db_t *);
 129 static const char *parse_cast_expr(const char *, const char *, cpp_db_t *);
 130 static const char *parse_sizeof_param_pack_expr(const char *, const char *,
 131     cpp_db_t *);
 132 static const char *parse_typeid_expr(const char *, const char *, cpp_db_t *);
 133 static const char *parse_throw_expr(const char *, const char *, cpp_db_t *);
 134 static const char *parse_dot_star_expr(const char *, const char *, cpp_db_t *);
 135 static const char *parse_dot_expr(const char *, const char *, cpp_db_t *);
 136 static const char *parse_call_expr(const char *, const char *, cpp_db_t *);
 137 static const char *parse_arrow_expr(const char *, const char *, cpp_db_t *);
 138 static const char *parse_conv_expr(const char *, const char *, cpp_db_t *);
 139 static const char *parse_function_param(const char *, const char *, cpp_db_t *);
 140 static const char *parse_base_unresolved_name(const char *, const char *,
 141     cpp_db_t *);
 142 static const char *parse_unresolved_name(const char *, const char *,
 143     cpp_db_t *);
 144 static const char *parse_noexcept_expr(const char *, const char *, cpp_db_t *);
 145 static const char *parse_alignof(const char *, const char *, cpp_db_t *);
 146 static const char *parse_sizeof(const char *, const char *, cpp_db_t *);
 147 static const char *parse_unnamed_type_name(const char *, const char *,
 148     cpp_db_t *);
 149 static const char *parse_ctor_dtor_name(const char *, const char *, cpp_db_t *);
 150 static const char *parse_source_name(const char *, const char *, cpp_db_t *);
 151 static const char *parse_operator_name(const char *, const char *, cpp_db_t *);
 152 static const char *parse_pack_expansion(const char *, const char *, cpp_db_t *);
 153 static const char *parse_unresolved_type(const char *, const char *,
 154     cpp_db_t *);
 155 static const char *parse_unresolved_qualifier_level(const char *, const char *,
 156     cpp_db_t *);
 157 static const char *parse_destructor_name(const char *, const char *,
 158     cpp_db_t *);
 159 static const char *parse_function_type(const char *, const char *, cpp_db_t *);
 160 static const char *parse_array_type(const char *, const char *, cpp_db_t *);
 161 static const char *parse_pointer_to_member_type(const char *, const char *,
 162     cpp_db_t *);
 163 static const char *parse_vector_type(const char *, const char *, cpp_db_t *);
 164 
 165 size_t cpp_name_max_depth = 1024;       /* max depth of name stack */
 166 
 167 char *
 168 cpp_demangle(const char *src, sysdem_ops_t *ops)
 169 {
 170         char *result = NULL;
 171         cpp_db_t db;
 172         size_t srclen = strlen(src);
 173 
 174         if (!db_init(&db, ops))
 175                 goto done;
 176         if (setjmp(db.cpp_jmp) != 0)
 177                 goto done;
 178 
 179         errno = 0;
 180         demangle(src, src + srclen, &db);
 181 
 182         if (errno == 0 && db.cpp_fix_forward_references &&
 183             !templ_empty(&db.cpp_templ) &&
 184             !sub_empty(&db.cpp_templ.tpl_items[0])) {
 185                 db.cpp_fix_forward_references = B_FALSE;
 186                 db.cpp_tag_templates = B_FALSE;
 187                 name_clear(&db.cpp_name);
 188                 sub_clear(&db.cpp_subs);
 189 
 190                 if (setjmp(db.cpp_jmp) != 0)
 191                         goto done;
 192 
 193                 demangle(src, src + srclen, &db);
 194 
 195                 if (db.cpp_fix_forward_references) {
 196                         errno = EINVAL;
 197                         goto done;
 198                 }
 199         }
 200 
 201         if (errno != 0)
 202                 goto done;
 203 
 204         if (nempty(&db)) {
 205                 errno = EINVAL;
 206                 goto done;
 207         }
 208 
 209         njoin(&db, 1, "");
 210 
 211         if (nlen(&db) > 0) {
 212                 str_t *s = TOP_L(&db);
 213                 result = zalloc(ops, s->str_len + 1);
 214                 if (result == NULL)
 215                         goto done;
 216 
 217                 (void) memcpy(result, s->str_s, s->str_len);
 218         }
 219 
 220 done:
 221         if (demangle_debug)
 222                 dump(&db, stdout);
 223 
 224         db_fini(&db);
 225         return (result);
 226 }
 227 
 228 static void
 229 demangle(const char *first, const char *last, cpp_db_t *db)
 230 {
 231         const char *t = NULL;
 232 
 233         if (first >= last) {
 234                 errno = EINVAL;
 235                 return;
 236         }
 237 
 238         if (first[0] != '_') {
 239                 t = parse_type(first, last, db);
 240                 if (t == first) {
 241                         errno = EINVAL;
 242                         return;
 243                 }
 244                 goto done;
 245         }
 246 
 247         if (last - first < 4) {
 248                 errno = EINVAL;
 249                 return;
 250         }
 251 
 252         if (first[1] == 'Z') {
 253                 t = parse_encoding(first + 2, last, db);
 254 
 255                 if (t != first + 2 && t != last && t[0] == '.') {
 256                         t = parse_dot_suffix(t, last, db);
 257                         if (nlen(db) > 1)
 258                                 njoin(db, 2, "");
 259                 }
 260 
 261                 goto done;
 262         }
 263 
 264         if (first[1] != '_' || first[2] != '_' || first[3] != 'Z')
 265                 goto done;
 266 
 267         t = parse_encoding(first + 4, last, db);
 268         if (t != first + 4 && t != last)
 269                 t = parse_block_invoke(t, last, db);
 270 
 271 done:
 272         if (t != last)
 273                 errno = EINVAL;
 274 }
 275 
 276 static const char *
 277 parse_dot_suffix(const char *first, const char *last, cpp_db_t *db)
 278 {
 279         VERIFY3P(first, <=, last);
 280 
 281         if (first == last || first[0] != '.')
 282                 return (first);
 283 
 284         if (nempty(db))
 285                 return (first);
 286 
 287         nadd_l(db, first, RLEN(first, last));
 288         nfmt(db, " ({0})", NULL);
 289 
 290         return (last);
 291 }
 292 
 293 /*
 294  * _block_invoke
 295  * _block_invoke<digit>*
 296  * _block_invoke_<digit>+
 297  */
 298 static const char *
 299 parse_block_invoke(const char *first, const char *last, cpp_db_t *db)
 300 {
 301         VERIFY3P(first, <=, last);
 302 
 303         if (last - first < 13)
 304                 return (first);
 305 
 306         const char test[] = "_block_invoke";
 307         const char *t = first;
 308 
 309         if (strncmp(first, test, sizeof (test) - 1) != 0)
 310                 return (first);
 311 
 312         t += sizeof (test);
 313         if (t == last)
 314                 goto done;
 315 
 316         if (t[0] == '_') {
 317                 /* need at least one digit */
 318                 if (t + 1 == last || !isdigit_l(t[1], db->cpp_loc))
 319                         return (first);
 320                 t += 2;
 321         }
 322 
 323         while (t < last && isdigit_l(t[0], db->cpp_loc))
 324                 t++;
 325 
 326 done:
 327         if (nempty(db))
 328                 return (first);
 329 
 330         nfmt(db, "invocation function for block in {0}", NULL);
 331         return (t);
 332 }
 333 
 334 /*
 335  * <encoding> ::= <function name><bare-function-type>
 336  *            ::= <data name>
 337  *            ::= <special name>
 338  */
 339 static const char *
 340 parse_encoding(const char *first, const char *last, cpp_db_t *db)
 341 {
 342         VERIFY3P(first, <=, last);
 343 
 344         if (first == last)
 345                 return (first);
 346 
 347         const char *t = NULL;
 348         const char *t2 = NULL;
 349         unsigned cv = 0;
 350         unsigned ref = 0;
 351         boolean_t tag_templ_save = db->cpp_tag_templates;
 352 
 353         if (++db->cpp_depth > 1)
 354                 db->cpp_tag_templates = B_TRUE;
 355 
 356         if (first[0] == 'G' || first[0] == 'T') {
 357                 t = parse_special_name(first, last, db);
 358                 goto done;
 359         }
 360 
 361         boolean_t ends_with_template_args = B_FALSE;
 362         t = parse_name(first, last, &ends_with_template_args, db);
 363         if (t == first)
 364                 goto fail;
 365 
 366         cv = db->cpp_cv;
 367         ref = db->cpp_ref;
 368 
 369         if (t == last || t[0] == 'E' || t[0] == '.')
 370                 goto done;
 371 
 372         db->cpp_tag_templates = B_FALSE;
 373         if (nempty(db) || str_length(TOP_L(db)) == 0)
 374                 goto fail;
 375 
 376         if (!db->cpp_parsed_ctor_dtor_cv && ends_with_template_args) {
 377                 t2 = parse_type(t, last, db);
 378                 if (t2 == t || nlen(db) < 2)
 379                         goto fail;
 380 
 381                 str_pair_t *sp = name_top(&db->cpp_name);
 382 
 383                 if (str_length(&sp->strp_r) == 0)
 384                         (void) str_append(&sp->strp_l, " ", 1);
 385 
 386                 nfmt(db, "{0:L}{1:L}", "{1:R}{0:R}");
 387                 t = t2;
 388         }
 389 
 390         if (t == last || nempty(db))
 391                 goto fail;
 392 
 393         size_t n = nlen(db);
 394 
 395         if (t[0] == 'v') {
 396                 t++;
 397         } else {
 398                 for (;;) {
 399                         t2 = parse_type(t, last, db);
 400                         if (t2 == t || t == last)
 401                                 break;
 402 
 403                         t = t2;
 404                 }
 405         }
 406 
 407         /*
 408          * a bit of a hack, but a template substitution can apparently be
 409          * an empty string at the end of an argument list, so avoid
 410          * <...., >
 411          */
 412         if (NAMT(db, n) > 1 && str_pair_len(name_top(&db->cpp_name)) == 0)
 413                 name_pop(&db->cpp_name, NULL);
 414 
 415         njoin(db, NAMT(db, n), ", ");
 416         nfmt(db, "({0})", NULL);
 417 
 418         str_t *s = TOP_L(db);
 419 
 420         if (cv & CPP_QUAL_CONST) {
 421                 CK(str_append(s, " const", 0));
 422         }
 423         if (cv & CPP_QUAL_VOLATILE) {
 424                 CK(str_append(s, " volatile", 0));
 425         }
 426         if (cv & CPP_QUAL_RESTRICT) {
 427                 CK(str_append(s, " restrict", 0));
 428         }
 429         if (ref == 1) {
 430                 CK(str_append(s, " &", 0));
 431         }
 432         if (ref == 2) {
 433                 CK(str_append(s, " &&", 0));
 434         }
 435 
 436         nfmt(db, "{1:L}{0}{1:R}", NULL);
 437 
 438 done:
 439         db->cpp_tag_templates = tag_templ_save;
 440         db->cpp_depth--;
 441         return (t);
 442 
 443 fail:
 444         db->cpp_tag_templates = tag_templ_save;
 445         db->cpp_depth--;
 446         return (first);
 447 }
 448 
 449 /*
 450  * <special-name> ::= TV <type>    # virtual table
 451  *                ::= TT <type>    # VTT structure (construction vtable index)
 452  *                ::= TI <type>    # typeinfo structure
 453  *                ::= TS <type>    # typeinfo name (null-terminated byte string)
 454  *                ::= Tc <call-offset> <call-offset> <base encoding>
 455  *                    # base is the nominal target function of thunk
 456  *                    # first call-offset is 'this' adjustment
 457  *                    # second call-offset is result adjustment
 458  *                ::= T <call-offset> <base encoding>
 459  *                    # base is the nominal target function of thunk
 460  *                ::= GV <object name> # Guard variable for one-time init
 461  *                                     # No <type>
 462  *                ::= TW <object name> # Thread-local wrapper
 463  *                ::= TH <object name> # Thread-local initialization
 464  *      extension ::= TC <first type> <number> _ <second type>
 465  *                                     # construction vtable for second-in-first
 466  *      extension ::= GR <object name> # reference temporary for object
 467  */
 468 static const char *
 469 parse_special_name(const char *first, const char *last, cpp_db_t *db)
 470 {
 471         VERIFY3P(first, <=, last);
 472 
 473         const char *t = first;
 474         const char *t1 = NULL;
 475         size_t n = nlen(db);
 476 
 477         if (last - first < 2)
 478                 return (first);
 479 
 480         switch (t[0]) {
 481         case 'T':
 482                 switch (t[1]) {
 483                 case 'V':
 484                         nadd_l(db, "vtable for", 0);
 485                         t = parse_type(first + 2, last, db);
 486                         break;
 487                 case 'T':
 488                         nadd_l(db, "VTT for", 0);
 489                         t = parse_type(first + 2, last, db);
 490                         break;
 491                 case 'I':
 492                         nadd_l(db, "typeinfo for", 0);
 493                         t = parse_type(first + 2, last, db);
 494                         break;
 495                 case 'S':
 496                         nadd_l(db, "typeinfo name for", 0);
 497                         t = parse_type(first + 2, last, db);
 498                         break;
 499                 case 'c':
 500                         nadd_l(db, "covariant return thunk to", 0);
 501                         t1 = parse_call_offset(first + 2, last, db->cpp_loc);
 502                         if (t1 == t)
 503                                 return (first);
 504                         t = parse_call_offset(t1, last, db->cpp_loc);
 505                         if (t == t1)
 506                                 return (first);
 507                         t1 = parse_encoding(t, last, db);
 508                         if (t1 == t)
 509                                 return (first);
 510                         break;
 511                 case 'C':
 512                         t = parse_type(first + 2, last, db);
 513                         if (t == first + 2)
 514                                 return (first);
 515                         t1 = parse_number(t, last, db->cpp_loc);
 516                         if (*t1 != '_')
 517                                 return (first);
 518                         t = parse_type(t1 + 1, last, db);
 519                         if (t == t1 + 1 || nlen(db) < 2)
 520                                 return (first);
 521                         nfmt(db, "construction vtable for {0}-in-{1}", NULL);
 522                         return (t);
 523                 case 'W':
 524                         nadd_l(db, "thread-local wrapper routine for", 0);
 525                         t = parse_name(first + 2, last, NULL, db);
 526                         break;
 527                 case 'H':
 528                         nadd_l(db, "thread-local initialization routine for",
 529                             0);
 530                         t = parse_name(first + 2, last, NULL, db);
 531                         break;
 532                 default:
 533                         if (first[1] == 'v') {
 534                                 nadd_l(db, "virtual thunk to", 0);
 535                         } else {
 536                                 nadd_l(db, "non-virtual thunk to", 0);
 537                         }
 538 
 539                         t = parse_call_offset(first + 1, last, db->cpp_loc);
 540                         if (t == first + 1)
 541                                 return (first);
 542                         t1 = parse_encoding(t, last, db);
 543                         if (t == t1)
 544                                 return (first);
 545                         t = t1;
 546                         break;
 547                 }
 548                 break;
 549         case 'G':
 550                 switch (first[1]) {
 551                 case 'V':
 552                         nadd_l(db, "guard variable for", 0);
 553                         t = parse_name(first + 2, last, NULL, db);
 554                         break;
 555                 case 'R':
 556                         nadd_l(db, "reference temporary for", 0);
 557                         t = parse_name(first + 2, last, NULL, db);
 558                         break;
 559                 default:
 560                         return (first);
 561                 }
 562                 break;
 563         default:
 564                 return (first);
 565         }
 566 
 567         size_t amt = NAMT(db, n);
 568         if (t == first + 2 || amt < 2)
 569                 return (first);
 570 
 571         njoin(db, amt, " ");
 572         return (t);
 573 }
 574 
 575 /*
 576  * <call-offset> ::= h <nv-offset> _
 577  *               ::= v <v-offset> _
 578  *
 579  * <nv-offset> ::= <offset number>
 580  *               # non-virtual base override
 581  *
 582  * <v-offset>  ::= <offset number> _ <virtual offset number>
 583  *               # virtual base override, with vcall offset
 584  */
 585 static const char *
 586 parse_call_offset(const char *first, const char *last, locale_t loc)
 587 {
 588         VERIFY3P(first, <=, last);
 589 
 590         const char *t = NULL;
 591         const char *t1 = NULL;
 592 
 593         if (first == last)
 594                 return (first);
 595 
 596         if (first[0] != 'h' && first[0] != 'v')
 597                 return (first);
 598 
 599         t = parse_number(first + 1, last, loc);
 600         if (t == first + 1 || t == last || t[0] != '_')
 601                 return (first);
 602 
 603         /* skip _ */
 604         t++;
 605 
 606         if (first[0] == 'h')
 607                 return (t);
 608 
 609         t1 = parse_number(t, last, loc);
 610         if (t == t1 || t1 == last || t1[0] != '_')
 611                 return (first);
 612 
 613         /* skip _ */
 614         t1++;
 615 
 616         return (t1);
 617 }
 618 
 619 /*
 620  * <name> ::= <nested-name> // N
 621  *        ::= <local-name> # See Scope Encoding below  // Z
 622  *        ::= <unscoped-template-name> <template-args>
 623  *        ::= <unscoped-name>
 624  *
 625  * <unscoped-template-name> ::= <unscoped-name>
 626  *                          ::= <substitution>
 627  */
 628 static const char *
 629 parse_name(const char *first, const char *last,
 630     boolean_t *ends_with_template_args, cpp_db_t *db)
 631 {
 632         VERIFY3P(first, <=, last);
 633 
 634         const char *t = first;
 635         const char *t1 = NULL;
 636 
 637         if (last - first < 2)
 638                 return (first);
 639 
 640         /* extension: ignore L here */
 641         if (t[0] == 'L')
 642                 t++;
 643 
 644         switch (t[0]) {
 645         case 'N':
 646                 t1 = parse_nested_name(t, last, ends_with_template_args, db);
 647                 return ((t == t1) ? first : t1);
 648         case 'Z':
 649                 t1 = parse_local_name(t, last, ends_with_template_args, db);
 650                 return ((t == t1) ? first : t1);
 651         }
 652 
 653         /*
 654          * <unscoped-name>
 655          * <unscoped-name> <template-args>
 656          * <substitution> <template-args>
 657          */
 658         t1 = parse_unscoped_name(t, last, db);
 659 
 660         /* <unscoped-name> */
 661         if (t != t1 && t1[0] != 'I')
 662                 return (t1);
 663 
 664         if (t == t1) {
 665                 t1 = parse_substitution(t, last, db);
 666                 if (t == t1 || t1 == last || t1[0] != 'I')
 667                         return (first);
 668         } else {
 669                 save_top(db, 1);
 670         }
 671 
 672         t = parse_template_args(t1, last, db);
 673         if (t1 == t || nlen(db) < 2)
 674                 return (first);
 675 
 676         nfmt(db, "{1:L}{0}", "{1:R}");
 677 
 678         if (ends_with_template_args != NULL)
 679                 *ends_with_template_args = B_TRUE;
 680 
 681         return (t);
 682 }
 683 
 684 /* BEGIN CSTYLED */
 685 /*
 686  * <local-name> := Z <function encoding> E <entity name> [<discriminator>]
 687  *              := Z <function encoding> E s [<discriminator>]
 688  *              := Z <function encoding> Ed [ <parameter number> ] _ <entity name>
 689  */
 690 /* END CSTYLED */
 691 const char *
 692 parse_local_name(const char *first, const char *last,
 693     boolean_t *ends_with_template_args, cpp_db_t *db)
 694 {
 695         VERIFY3P(first, <=, last);
 696 
 697         const char *t = NULL;
 698         const char *t1 = NULL;
 699         const char *t2 = NULL;
 700 
 701         if (first == last || first[0] != 'Z')
 702                 return (first);
 703 
 704         t = parse_encoding(first + 1, last, db);
 705         if (t == first + 1 || t == last || t[0] != 'E')
 706                 return (first);
 707 
 708         VERIFY(!nempty(db));
 709 
 710         /* skip E */
 711         t++;
 712 
 713         if (t[0] == 's') {
 714                 nfmt(db, "{0:L}::string literal", "{0:R}");
 715                 return (parse_discriminator(t, last, db->cpp_loc));
 716         }
 717 
 718         if (t[0] == 'd') {
 719                 t1 = parse_number(t + 1, last, db->cpp_loc);
 720                 if (t1[0] != '_')
 721                         return (first);
 722                 t1++;
 723         } else {
 724                 t1 = t;
 725         }
 726 
 727         t2 = parse_name(t1, last, ends_with_template_args, db);
 728         if (t2 == t1)
 729                 return (first);
 730 
 731         nfmt(db, "{1:L}::{0}", "{1:R}");
 732 
 733         /* parsed, but ignored */
 734         if (t[0] != 'd')
 735                 t2 = parse_discriminator(t2, last, db->cpp_loc);
 736 
 737         return (t2);
 738 }
 739 
 740 /* BEGIN CSTYLED */
 741 /*
 742  * <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E
 743  *               ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix> <template-args> E
 744  *
 745  * <prefix> ::= <prefix> <unqualified-name>
 746  *          ::= <template-prefix> <template-args>
 747  *          ::= <template-param>
 748  *          ::= <decltype>
 749  *          ::= # empty
 750  *          ::= <substitution>
 751  *          ::= <prefix> <data-member-prefix>
 752  *  extension ::= L
 753  *
 754  * <template-prefix> ::= <prefix> <template unqualified-name>
 755  *                   ::= <template-param>
 756  *                   ::= <substitution>
 757  */
 758 /* END CSTYLED */
 759 static const char *
 760 parse_nested_name(const char *first, const char *last,
 761     boolean_t *ends_with_template_args, cpp_db_t *db)
 762 {
 763         VERIFY3P(first, <=, last);
 764 
 765         if (first == last || first[0] != 'N')
 766                 return (first);
 767 
 768         unsigned cv = 0;
 769         const char *t = parse_cv_qualifiers(first + 1, last, &cv);
 770 
 771         if (t == last)
 772                 return (first);
 773 
 774         boolean_t more = B_FALSE;
 775 
 776         switch (t[0]) {
 777         case 'R':
 778                 db->cpp_ref = 1;
 779                 t++;
 780                 break;
 781         case 'O':
 782                 db->cpp_ref = 2;
 783                 t++;
 784                 break;
 785         case 'S':
 786                 if (last - first < 2 || t[1] != 't')
 787                         break;
 788                 if (last - first == 2)
 789                         return (first);
 790                 nadd_l(db, "std", 3);
 791                 more = B_TRUE;
 792                 t += 2;
 793                 break;
 794         }
 795 
 796         boolean_t pop_subs = B_FALSE;
 797         boolean_t component_ends_with_template_args = B_FALSE;
 798 
 799         while (t[0] != 'E' && t != last) {
 800                 const char *t1 = NULL;
 801                 size_t n = nlen(db);
 802                 component_ends_with_template_args = B_FALSE;
 803 
 804                 switch (t[0]) {
 805                 case 'S':
 806                         if (t + 1 != last && t[1] == 't')
 807                                 break;
 808 
 809                         t1 = parse_substitution(t, last, db);
 810                         if (t1 == t || t1 == last || NAMT(db, n) != 1)
 811                                 return (first);
 812 
 813                         if (!more) {
 814                                 nfmt(db, "{0}", NULL);
 815                         } else {
 816                                 VERIFY3U(nlen(db), >, 1);
 817                                 nfmt(db, "{1:L}::{0}", "{1:R}");
 818                                 save_top(db, 1);
 819                         }
 820 
 821                         more = B_TRUE;
 822                         pop_subs = B_TRUE;
 823                         t = t1;
 824                         continue;
 825 
 826                 case 'T':
 827                         t1 = parse_template_param(t, last, db);
 828                         if (t1 == t || t1 == last || NAMT(db, n) != 1)
 829                                 return (first);
 830 
 831                         if (!more) {
 832                                 nfmt(db, "{0}", NULL);
 833                         } else {
 834                                 VERIFY3U(nlen(db), >, 1);
 835                                 nfmt(db, "{1:L}::{0}", "{1:R}");
 836                         }
 837 
 838                         save_top(db, 1);
 839                         more = B_TRUE;
 840                         pop_subs = B_TRUE;
 841                         t = t1;
 842                         continue;
 843 
 844                 case 'D':
 845                         if (t + 1 != last && t[1] != 't' && t[1] != 'T')
 846                                 break;
 847                         t1 = parse_decltype(t, last, db);
 848                         if (t1 == t || t1 == last || NAMT(db, n) != 1)
 849                                 return (first);
 850 
 851                         if (!more) {
 852                                 nfmt(db, "{0}", NULL);
 853                         } else {
 854                                 VERIFY3U(nlen(db), >, 1);
 855                                 nfmt(db, "{1:L}::{0}", "{1:R}");
 856                         }
 857 
 858                         save_top(db, 1);
 859                         more = B_TRUE;
 860                         pop_subs = B_TRUE;
 861                         t = t1;
 862                         continue;
 863 
 864                 case 'I':
 865                         /*
 866                          * Must have at least one component before
 867                          * <template-args>
 868                          */
 869                         if (!more)
 870                                 return (first);
 871 
 872                         t1 = parse_template_args(t, last, db);
 873                         if (t1 == t || t1 == last)
 874                                 return (first);
 875 
 876                         VERIFY3U(nlen(db), >, 1);
 877                         nfmt(db, "{1:L}{0}", "{1:R}");
 878                         save_top(db, 1);
 879                         t = t1;
 880                         component_ends_with_template_args = B_TRUE;
 881                         continue;
 882 
 883                 case 'L':
 884                         if (t + 1 == last)
 885                                 return (first);
 886                         t++;
 887                         continue;
 888 
 889                 default:
 890                         break;
 891                 }
 892 
 893                 t1 = parse_unqualified_name(t, last, db);
 894                 if (t1 == t || t1 == last || NAMT(db, n) != 1)
 895                         return (first);
 896 
 897                 if (!more) {
 898                         nfmt(db, "{0}", NULL);
 899                 } else {
 900                         VERIFY3U(nlen(db), >, 1);
 901                         nfmt(db, "{1:L}::{0}", "{1:R}");
 902                 }
 903 
 904                 save_top(db, 1);
 905                 more = B_TRUE;
 906                 pop_subs = B_TRUE;
 907                 t = t1;
 908         }
 909 
 910         /* need to parse at least one thing */
 911         if (!more)
 912                 return (first);
 913 
 914         db->cpp_cv = cv;
 915         if (pop_subs && !sub_empty(&db->cpp_subs))
 916                 sub_pop(&db->cpp_subs);
 917 
 918         if (ends_with_template_args != NULL)
 919                 *ends_with_template_args = component_ends_with_template_args;
 920 
 921         if (t[0] != 'E')
 922                 return (first);
 923 
 924         return (t + 1);
 925 }
 926 
 927 /*
 928  * <template-arg> ::= <type>                   # type or template
 929  *                ::= X <expression> E         # expression
 930  *                ::= <expr-primary>           # simple expressions
 931  *                ::= J <template-arg>* E      # argument pack
 932  *                ::= LZ <encoding> E          # extension
 933  */
 934 static const char *
 935 parse_template_arg(const char *first, const char *last, cpp_db_t *db)
 936 {
 937         VERIFY3P(first, <=, last);
 938 
 939         const char *t = NULL;
 940         const char *t1 = NULL;
 941 
 942         if (first == last)
 943                 return (first);
 944 
 945         switch (first[0]) {
 946         case 'X':
 947                 t = parse_expression(first + 1, last, db);
 948                 if (t == first + 1 || t[0] != 'E')
 949                         return (first);
 950 
 951                 /* E */
 952                 t++;
 953                 break;
 954 
 955         case 'J':
 956                 t = first + 1;
 957                 if (t == last)
 958                         return (first);
 959 
 960                 while (t[0] != 'E') {
 961                         t1 = parse_template_arg(t, last, db);
 962                         if (t == t1)
 963                                 return (first);
 964                         t = t1;
 965                 }
 966 
 967                 /* E */
 968                 t++;
 969                 break;
 970 
 971         case 'L':
 972                 if (first + 1 == last || first[1] != 'Z') {
 973                         t = parse_expr_primary(first, last, db);
 974                 } else {
 975                         t = parse_encoding(first + 2, last, db);
 976                         if (t == first + 2 || t == last || t[0] != 'E')
 977                                 return (first);
 978 
 979                         /* E */
 980                         t++;
 981                 }
 982                 break;
 983 
 984         default:
 985                 t = parse_type(first, last, db);
 986         }
 987 
 988         return (t);
 989 }
 990 
 991 /* BEGIN CSTYLED */
 992 /*
 993  * <expression> ::= <unary operator-name> <expression>
 994  *              ::= <binary operator-name> <expression> <expression>
 995  *              ::= <ternary operator-name> <expression> <expression> <expression>
 996  *              ::= cl <expression>+ E                                   # call
 997  *              ::= cv <type> <expression>                               # conversion with one argument
 998  *              ::= cv <type> _ <expression>* E                          # conversion with a different number of arguments
 999  *              ::= [gs] nw <expression>* _ <type> E                     # new (expr-list) type
1000  *              ::= [gs] nw <expression>* _ <type> <initializer>         # new (expr-list) type (init)
1001  *              ::= [gs] na <expression>* _ <type> E                     # new[] (expr-list) type
1002  *              ::= [gs] na <expression>* _ <type> <initializer>         # new[] (expr-list) type (init)
1003  *              ::= [gs] dl <expression>                                 # delete expression
1004  *              ::= [gs] da <expression>                                 # delete[] expression
1005  *              ::= pp_ <expression>                                     # prefix ++
1006  *              ::= mm_ <expression>                                     # prefix --
1007  *              ::= ti <type>                                            # typeid (type)
1008  *              ::= te <expression>                                      # typeid (expression)
1009  *              ::= dc <type> <expression>                               # dynamic_cast<type> (expression)
1010  *              ::= sc <type> <expression>                               # static_cast<type> (expression)
1011  *              ::= cc <type> <expression>                               # const_cast<type> (expression)
1012  *              ::= rc <type> <expression>                               # reinterpret_cast<type> (expression)
1013  *              ::= st <type>                                            # sizeof (a type)
1014  *              ::= sz <expression>                                      # sizeof (an expression)
1015  *              ::= at <type>                                            # alignof (a type)
1016  *              ::= az <expression>                                      # alignof (an expression)
1017  *              ::= nx <expression>                                      # noexcept (expression)
1018  *              ::= <template-param>
1019  *              ::= <function-param>
1020  *              ::= dt <expression> <unresolved-name>                    # expr.name
1021  *              ::= pt <expression> <unresolved-name>                    # expr->name
1022  *              ::= ds <expression> <expression>                         # expr.*expr
1023  *              ::= sZ <template-param>                                  # size of a parameter pack
1024  *              ::= sZ <function-param>                                  # size of a function parameter pack
1025  *              ::= sp <expression>                                      # pack expansion
1026  *              ::= tw <expression>                                      # throw expression
1027  *              ::= tr                                                   # throw with no operand (rethrow)
1028  *              ::= <unresolved-name>                                    # f(p), N::f(p), ::f(p),
1029  *                                                                       # freestanding dependent name (e.g., T::x),
1030  *                                                                       # objectless nonstatic member reference
1031  *              ::= <expr-primary>
1032  */
1033 /* END CSTYLED */
1034 
1035 #define PA(cd, arg, fn) {       \
1036         .code = cd,             \
1037         .p.parse_expr_arg = fn, \
1038         .fntype = EXPR_ARG,     \
1039         .val = arg              \
1040 }
1041 
1042 #define PN(cd, fn) {                    \
1043         .code = cd,                     \
1044         .p.parse_expr_noarg = fn,       \
1045         .fntype = EXPR_NOARG            \
1046 }
1047 
1048 static struct {
1049         const char code[3];
1050         union {
1051                 const char *(*parse_expr_arg)(const char *, const char *,
1052                     const char *, cpp_db_t *);
1053                 const char *(*parse_expr_noarg)(const char *, const char *,
1054                     cpp_db_t *);
1055         } p;
1056         enum {
1057                 EXPR_ARG,
1058                 EXPR_NOARG
1059         } fntype;
1060         const char val[4];
1061 } expr_tbl[] = {
1062         PA("aN", "&=", parse_binary_expr),
1063         PA("aS", "=", parse_binary_expr),
1064         PA("aa", "&&", parse_binary_expr),
1065         PA("ad", "&", parse_prefix_expr),
1066         PA("an", "&", parse_binary_expr),
1067         PN("at", parse_alignof),
1068         PN("az", parse_alignof),
1069         PN("cc", parse_cast_expr),
1070         PN("cl", parse_call_expr),
1071         PA("cm", ",", parse_binary_expr),
1072         PA("co", "~", parse_prefix_expr),
1073         PN("cv", parse_conv_expr),
1074         PN("da", parse_del_expr),
1075         PA("dV", "/=", parse_binary_expr),
1076         PN("dc", parse_cast_expr),
1077         PA("de", "*", parse_prefix_expr),
1078         PN("dl", parse_del_expr),
1079         PN("dn", parse_unresolved_name),
1080         PN("ds", parse_dot_star_expr),
1081         PN("dt", parse_dot_expr),
1082         PA("dv", "/", parse_binary_expr),
1083         PA("eO", "^=", parse_binary_expr),
1084         PA("eo", "^", parse_binary_expr),
1085         PA("eq", "==", parse_binary_expr),
1086         PA("ge", ">=", parse_binary_expr),
1087         PN("gs", parse_gs),
1088         PA("gt", ">", parse_binary_expr),
1089         PN("ix", parse_idx_expr),
1090         PA("lS", "<<=", parse_binary_expr),
1091         PA("le", "<=", parse_binary_expr),
1092         PA("ls", "<<", parse_binary_expr),
1093         PA("lt", "<", parse_binary_expr),
1094         PA("mI", "-=", parse_binary_expr),
1095         PA("mL", "*=", parse_binary_expr),
1096         PN("mm", parse_mm_expr),
1097         PA("mi", "-", parse_binary_expr),
1098         PA("ml", "*", parse_binary_expr),
1099         PN("na", parse_new_expr),
1100         PA("ne", "!=", parse_binary_expr),
1101         PA("ng", "-", parse_prefix_expr),
1102         PA("nt", "!", parse_prefix_expr),
1103         PN("nw", parse_new_expr),
1104         PN("nx", parse_noexcept_expr),
1105         PA("oR", "|=", parse_binary_expr),
1106         PN("on", parse_unresolved_name),
1107         PA("oo", "||", parse_binary_expr),
1108         PA("or", "|", parse_binary_expr),
1109         PA("pL", "+=", parse_binary_expr),
1110         PA("pl", "+", parse_binary_expr),
1111         PA("pm", "->*", parse_binary_expr),
1112         PN("pp", parse_pp_expr),
1113         PA("ps", "+", parse_prefix_expr),
1114         PN("pt", parse_arrow_expr),
1115         PN("qu", parse_trinary_expr),
1116         PA("rM", "%=", parse_binary_expr),
1117         PA("rS", ">>=", parse_binary_expr),
1118         PN("rc", parse_cast_expr),
1119         PA("rm", "%", parse_binary_expr),
1120         PA("rs", ">>", parse_binary_expr),
1121         PN("sc", parse_cast_expr),
1122         PN("sp", parse_pack_expansion),
1123         PN("sr", parse_unresolved_name),
1124         PN("st", parse_sizeof),
1125         PN("sz", parse_sizeof),
1126         PN("sZ", parse_sizeof_param_pack_expr),
1127         PN("te", parse_typeid_expr),
1128         PN("tr", parse_throw_expr),
1129         PN("tw", parse_throw_expr)
1130 };
1131 #undef PA
1132 #undef PN
1133 
1134 static const char *
1135 parse_expression(const char *first, const char *last, cpp_db_t *db)
1136 {
1137         VERIFY3P(first, <=, last);
1138 
1139         if (last - first < 2)
1140                 return (first);
1141 
1142         for (size_t i = 0; i < ARRAY_SIZE(expr_tbl); i++) {
1143                 if (strncmp(expr_tbl[i].code, first, 2) != 0)
1144                         continue;
1145                 switch (expr_tbl[i].fntype) {
1146                 case EXPR_ARG:
1147                         return (expr_tbl[i].p.parse_expr_arg(first, last,
1148                             expr_tbl[i].val, db));
1149                 case EXPR_NOARG:
1150                         return (expr_tbl[i].p.parse_expr_noarg(first, last,
1151                             db));
1152                 }
1153         }
1154 
1155         switch (first[0]) {
1156         case 'L':
1157                 return (parse_expr_primary(first, last, db));
1158         case 'T':
1159                 return (parse_template_param(first, last, db));
1160         case 'f':
1161                 return (parse_function_param(first, last, db));
1162         case '1':
1163         case '2':
1164         case '3':
1165         case '4':
1166         case '5':
1167         case '6':
1168         case '7':
1169         case '8':
1170         case '9':
1171                 return (parse_unresolved_name(first, last, db));
1172         }
1173 
1174         return (first);
1175 }
1176 
1177 static const char *
1178 parse_binary_expr(const char *first, const char *last, const char *op,
1179     cpp_db_t *db)
1180 {
1181         VERIFY3P(first, <=, last);
1182 
1183         if (last - first < 2)
1184                 return (first);
1185 
1186         size_t n = nlen(db);
1187 
1188         const char *t1 = parse_expression(first + 2, last, db);
1189         if (t1 == first + 2)
1190                 return (first);
1191 
1192         nadd_l(db, op, 0);
1193 
1194         const char *t2 = parse_expression(t1, last, db);
1195         if (t2 == t1)
1196                 return (first);
1197 
1198         if (NAMT(db, n) != 3)
1199                 return (first);
1200 
1201         VERIFY3U(nlen(db), >, 2);
1202 
1203         nfmt(db, "({2}) {1} ({0})", NULL);
1204         if (strcmp(op, ">") == 0)
1205                 nfmt(db, "({0})", NULL);
1206 
1207         return (t2);
1208 }
1209 
1210 static const char *
1211 parse_prefix_expr(const char *first, const char *last, const char *op,
1212     cpp_db_t *db)
1213 {
1214         VERIFY3P(first, <=, last);
1215 
1216         if (last - first < 2)
1217                 return (first);
1218 
1219         nadd_l(db, op, 0);
1220 
1221         const char *t = parse_expression(first + 2, last, db);
1222         if (t == first + 2) {
1223                 return (first);
1224         }
1225 
1226         VERIFY3U(nlen(db), >, 1);
1227 
1228         nfmt(db, "{1}({0})", NULL);
1229         return (t);
1230 }
1231 
1232 static const char *
1233 parse_gs(const char *first, const char *last, cpp_db_t *db)
1234 {
1235         VERIFY3P(first, <=, last);
1236 
1237         const char *t = NULL;
1238 
1239         if (last - first < 4)
1240                 return (first);
1241 
1242         if (first[2] == 'n' && (first[3] == 'a' || first[3] == 'w'))
1243                 t = parse_new_expr(first + 2, last, db);
1244         else if (first[2] == 'd' && (first[3] == 'l' || first[3] == 'a'))
1245                 t = parse_del_expr(first + 2, last, db);
1246         else
1247                 return (first);
1248 
1249         if (t == first + 2)
1250                 return (first);
1251 
1252         VERIFY3U(nlen(db), >, 0);
1253 
1254         nfmt(db, "::{0}", NULL);
1255         return (t);
1256 }
1257 
1258 /*
1259  * [gs] nw <expression>* _ <type> E         # new (expr-list) type
1260  * [gs] nw <expression>* _ <type> <initializer>       # new (expr-list) type (init)
1261  * [gs] na <expression>* _ <type> E         # new[] (expr-list) type
1262  * [gs] na <expression>* _ <type> <initializer>       # new[] (expr-list) type (init)
1263  * <initializer> ::= pi <expression>* E             # parenthesized initialization
1264  */
1265 static const char *
1266 parse_new_expr(const char *first, const char *last, cpp_db_t *db)
1267 {
1268         VERIFY3P(first, <=, last);
1269 
1270         /* note [gs] is already handled by parse_gs() */
1271         if (last - first < 3)
1272                 return (first);
1273 
1274         VERIFY3U(first[0], ==, 'n');
1275         VERIFY(first[1] == 'a' || first[1] == 'w');
1276 
1277         const char *t1 = first + 2;
1278         const char *t2 = NULL;
1279         size_t n = nlen(db);
1280 
1281         nadd_l(db, (first[1] == 'w') ? "new" : "new[]", 0);
1282 
1283         while (t1 != last && t1[0] != '_') {
1284                 t2 = parse_expression(t1, last, db);
1285                 VERIFY3P(t2, !=, NULL);
1286                 if (t2 == t1)
1287                         return (first);
1288                 t1 = t2;
1289         }
1290         if (t1 == last)
1291                 return (first);
1292 
1293         if (NAMT(db, n) > 1) {
1294                 njoin(db, NAMT(db, n) - 1, ", ");
1295                 nfmt(db, "({0})", NULL);
1296         }
1297 
1298         t2 = parse_type(t1 + 1, last, db);
1299         if (t1 + 1 == t2)
1300                 return (first);
1301 
1302         if (t2[0] != 'E') {
1303                 if (last - t2 < 3)
1304                         return (first);
1305                 if (t2[0] != 'p' && t2[1] != 'i')
1306                         return (first);
1307 
1308                 t2 += 2;
1309                 const char *t3 = t2;
1310                 size_t n1 = nlen(db);
1311 
1312                 while (t2[0] != 'E' && t2 != last) {
1313                         t3 = parse_expression(t2, last, db);
1314 
1315                         if (t2 == t3)
1316                                 return (first);
1317                         t2 = t3;
1318                 }
1319                 if (t3 == last || t3[0] != 'E')
1320                         return (first);
1321 
1322                 if (NAMT(db, n1) > 0) {
1323                         njoin(db, NAMT(db, n1), ", ");
1324                         nfmt(db, "({0})", NULL);
1325                 }
1326         }
1327 
1328         njoin(db, NAMT(db, n), " ");
1329         return (t2 + 1);
1330 }
1331 
1332 static const char *
1333 parse_del_expr(const char *first, const char *last, cpp_db_t *db)
1334 {
1335         VERIFY3P(first, <=, last);
1336 
1337         if (last - first < 3)
1338                 return (first);
1339 
1340         VERIFY3U(first[0], ==, 'd');
1341         VERIFY(first[1] == 'l' || first[1] == 'a');
1342 
1343         size_t n = nlen(db);
1344         const char *t = parse_expression(first + 2, last, db);
1345         if (t == first + 2 || NAMT(db, n) != 1)
1346                 return (first);
1347 
1348         nfmt(db, (first[1] == 'a') ? "delete[] {0}" : "delete {0}", NULL);
1349         return (t);
1350 }
1351 
1352 static const char *
1353 parse_idx_expr(const char *first, const char *last, cpp_db_t *db)
1354 {
1355         VERIFY3P(first, <=, last);
1356         VERIFY3U(first[0], ==, 'i');
1357         VERIFY3U(first[1], ==, 'x');
1358 
1359         size_t n = nlen(db);
1360         const char *t1 = parse_expression(first + 2, last, db);
1361         if (t1 == first + 2)
1362                 return (first);
1363 
1364         const char *t2 = parse_expression(t1, last, db);
1365         if (t2 == t1 || NAMT(db, n) != 2)
1366                 return (first);
1367 
1368         nfmt(db, "({0})[{1}]", NULL);
1369         return (t2);
1370 }
1371 
1372 static const char *
1373 parse_ppmm_expr(const char *first, const char *last, const char *fmt,
1374     cpp_db_t *db)
1375 {
1376         VERIFY3P(first, <=, last);
1377 
1378         if (last - first < 3)
1379                 return (first);
1380 
1381         const char *t = NULL;
1382         size_t n = nlen(db);
1383 
1384         if (first[2] == '_') {
1385                 t = parse_binary_expr(first + 3, last, "--", db);
1386                 if (t == first + 3)
1387                         return (first);
1388                 return (t);
1389         }
1390 
1391         t = parse_expression(first + 2, last, db);
1392         if (t == first + 2 || NAMT(db, n) < 1)
1393                 return (first);
1394 
1395         nfmt(db, fmt, NULL);
1396         return (t);
1397 }
1398 
1399 static const char *
1400 parse_mm_expr(const char *first, const char *last, cpp_db_t *db)
1401 {
1402         VERIFY3P(first, <=, last);
1403         VERIFY3U(first[0], ==, 'm');
1404         VERIFY3U(first[1], ==, 'm');
1405 
1406         return (parse_ppmm_expr(first, last, "({0})--", db));
1407 }
1408 
1409 static const char *
1410 parse_pp_expr(const char *first, const char *last, cpp_db_t *db)
1411 {
1412         VERIFY3P(first, <=, last);
1413 
1414         VERIFY3U(first[0], ==, 'p');
1415         VERIFY3U(first[0], ==, 'p');
1416 
1417         return (parse_ppmm_expr(first, last, "({0})++", db));
1418 }
1419 
1420 static const char *
1421 parse_trinary_expr(const char *first, const char *last, cpp_db_t *db)
1422 {
1423         VERIFY3P(first, <=, last);
1424 
1425         const char *t1, *t2, *t3;
1426         size_t n = nlen(db);
1427 
1428         if (last - first < 2)
1429                 return (first);
1430 
1431         t1 = parse_expression(first + 2, last, db);
1432         if (t1 == first + 2)
1433                 return (first);
1434         t2 = parse_expression(t1, last, db);
1435         if (t1 == t2)
1436                 return (first);
1437         t3 = parse_expression(t2, last, db);
1438         if (t3 == t2)
1439                 return (first);
1440 
1441         if (NAMT(db, n) != 3)
1442                 return (first);
1443 
1444         nfmt(db, "({2}) ? ({1}) : ({0})", NULL);
1445         return (t3);
1446 }
1447 
1448 static const char *
1449 parse_noexcept_expr(const char *first, const char *last, cpp_db_t *db)
1450 {
1451         VERIFY3P(first, <=, last);
1452 
1453         if (last - first < 2)
1454                 return (first);
1455 
1456         size_t n = nlen(db);
1457         const char *t = parse_expression(first + 2, last, db);
1458         if (t == first + 2 || NAMT(db, n) != 1)
1459                 return (first);
1460 
1461         nfmt(db, "noexcept ({0})", NULL);
1462         return (t);
1463 }
1464 
1465 /*
1466  * cc <type> <expression>   # const_cast<type> (expression)
1467  * dc <type> <expression>   # dynamic_cast<type> (expression)
1468  * rc <type> <expression>   # reinterpret_cast<type> (expression)
1469  * sc <type> <expression>   # static_cast<type> (expression)
1470  */
1471 static const char *
1472 parse_cast_expr(const char *first, const char *last, cpp_db_t *db)
1473 {
1474         VERIFY3P(first, <=, last);
1475 
1476         if (last - first < 2)
1477                 return (first);
1478 
1479         const char *fmt = NULL;
1480         switch (first[0]) {
1481         case 'c':
1482                 fmt = "const_cast<{1}> ({0})";
1483                 break;
1484         case 'd':
1485                 fmt = "dynamic_cast<{1}> ({0})";
1486                 break;
1487         case 'r':
1488                 fmt = "reinterpret_cast<{1}> ({0})";
1489                 break;
1490         case 's':
1491                 fmt = "static_cast<{1}> ({0})";
1492                 break;
1493         default:
1494                 return (first);
1495         }
1496 
1497         VERIFY3U(first[1], ==, 'c');
1498 
1499         const char *t1 = parse_type(first + 2, last, db);
1500         if (t1 == first + 2)
1501                 return (first);
1502 
1503         const char *t2 = parse_expression(t1, last, db);
1504         if (t2 == t1)
1505                 return (first);
1506 
1507         VERIFY3U(nlen(db), >, 1);
1508 
1509         nfmt(db, fmt, NULL);
1510         return (t2);
1511 }
1512 
1513 /* pt <expression> <expression>             # expr->name */
1514 static const char *
1515 parse_arrow_expr(const char *first, const char *last, cpp_db_t *db)
1516 {
1517         VERIFY3P(first, <=, last);
1518 
1519         if (last - first < 4)
1520                 return (first);
1521 
1522         size_t n = nlen(db);
1523 
1524         const char *t1 = parse_expression(first + 2, last, db);
1525         if (t1 == first + 2)
1526                 return (first);
1527 
1528         const char *t2 = parse_expression(t1, last, db);
1529         if (t2 == t1 || NAMT(db, n) != 2)
1530                 return (first);
1531 
1532         nfmt(db, "{1}->{0}", NULL);
1533         return (t2);
1534 }
1535 
1536 /* wrap value in () when necessary */
1537 static void
1538 paren(str_pair_t *sp)
1539 {
1540         str_t *l = &sp->strp_l;
1541         str_t *r = &sp->strp_r;
1542 
1543         if (str_length(r) > 1 &&
1544             r->str_s[0] == ' ' && r->str_s[1] == '[') {
1545                 (void) str_append(l, " (", 2);
1546                 (void) str_insert(r, 0, ")", 1);
1547         } else if (str_length(r) > 0 && r->str_s[0] == '(') {
1548                 (void) str_append(l, "(", 1);
1549                 (void) str_insert(r, 0, ")", 1);
1550         }
1551 }
1552 
1553 /* BEGIN CSTYLED */
1554 /*
1555  * <type> ::= <builtin-type>
1556  *        ::= <function-type>
1557  *        ::= <class-enum-type>
1558  *        ::= <array-type>
1559  *        ::= <pointer-to-member-type>
1560  *        ::= <template-param>
1561  *        ::= <template-template-param> <template-args>
1562  *        ::= <decltype>
1563  *        ::= <substitution>
1564  *        ::= <CV-qualifiers> <type>
1565  *        ::= P <type>        # pointer-to
1566  *        ::= R <type>        # reference-to
1567  *        ::= O <type>        # rvalue reference-to (C++0x)
1568  *        ::= C <type>        # complex pair (C 2000)
1569  *        ::= G <type>        # imaginary (C 2000)
1570  *        ::= Dp <type>       # pack expansion (C++0x)
1571  *        ::= U <source-name> <type>  # vendor extended type qualifier
1572  * extension := U <objc-name> <objc-type>  # objc-type<identifier>
1573  * extension := <vector-type> # <vector-type> starts with Dv
1574  *
1575  * <objc-name> ::= <k0 number> objcproto <k1 number> <identifier>  # k0 = 9 + <number of digits in k1> + k1
1576  * <objc-type> := <source-name>  # PU<11+>objcproto 11objc_object<source-name> 11objc_object -> id<source-name>
1577  */
1578 /* END CSTYLED */
1579 static const char *
1580 parse_type(const char *first, const char *last, cpp_db_t *db)
1581 {
1582         VERIFY3P(first, <=, last);
1583 
1584         if (first == last)
1585                 return (first);
1586 
1587         switch (first[0]) {
1588         case 'r':
1589         case 'V':
1590         case 'K':
1591                 return (parse_qual_type(first, last, db));
1592         }
1593 
1594         const char *t = first;
1595         const char *t1 = NULL;
1596         str_pair_t *sp = NULL;
1597         size_t n = nlen(db);
1598         size_t amt = 0;
1599 
1600         t = parse_builtin_type(first, last, db);
1601         if (t != first)
1602                 return (t);
1603 
1604         switch (first[0]) {
1605         case 'A':
1606                 t = parse_array_type(first, last, db);
1607                 if (t == first || NAMT(db, n) == 0)
1608                         return (first);
1609                 save_top(db, 1);
1610                 return (t);
1611 
1612         case 'C':
1613                 t = parse_type(first + 1, last, db);
1614                 if (t == first + 1 || NAMT(db, n) == 0)
1615                         return (first);
1616 
1617                 (void) str_append(TOP_L(db), " complex", 8);
1618                 save_top(db, 1);
1619                 return (t);
1620 
1621         case 'F':
1622                 t = parse_function_type(first, last, db);
1623                 if (t == first || NAMT(db, n) == 0)
1624                         return (first);
1625                 save_top(db, 1);
1626                 return (t);
1627 
1628         case 'G':
1629                 t = parse_type(first + 1, last, db);
1630                 if (t == first + 1 || NAMT(db, n) == 0)
1631                         return (first);
1632 
1633                 (void) str_append(TOP_L(db), " imaginary", 10);
1634                 save_top(db, 1);
1635                 return (t);
1636 
1637         case 'M':
1638                 t = parse_pointer_to_member_type(first, last, db);
1639                 if (t == first || NAMT(db, n) == 0)
1640                         return (first);
1641                 save_top(db, 1);
1642                 return (t);
1643 
1644         case 'O':
1645                 t = parse_type(first + 1, last, db);
1646                 amt = NAMT(db, n);
1647                 if (t == first + 1 || amt == 0)
1648                         return (first);
1649 
1650                 sp = name_at(&db->cpp_name, amt - 1);
1651                 for (size_t i = 0; i < amt; i++, sp++) {
1652                         paren(sp);
1653                         if (str_pair_len(sp) > 0)
1654                                 (void) str_append(&sp->strp_l, "&&", 2);
1655                 }
1656 
1657                 save_top(db, amt);
1658                 return (t);
1659 
1660         case 'P':
1661                 t = parse_type(first + 1, last, db);
1662                 amt = NAMT(db, n);
1663                 if (t == first + 1 || amt == 0)
1664                         return (first);
1665 
1666                 sp = name_at(&db->cpp_name, amt - 1);
1667                 for (size_t i = 0; i < amt; i++, sp++) {
1668                         str_t *l = &sp->strp_l;
1669 
1670                         if (str_pair_len(sp) == 0)
1671                                 continue;
1672 
1673                         paren(sp);
1674                         if (first[1] != 'U' ||
1675                             strncmp(l->str_s, "objc_object<", 12) != 0) {
1676                                 (void) str_append(l, "*", 1);
1677                         } else {
1678                                 (void) str_erase(l, 0, 11);
1679                                 (void) str_insert(l, 0, "id", 2);
1680                         }
1681                 }
1682                 save_top(db, amt);
1683                 return (t);
1684 
1685         case 'R':
1686                 t = parse_type(first + 1, last, db);
1687                 amt = NAMT(db, n);
1688                 if (t == first + 1 || amt == 0)
1689                         return (first);
1690 
1691                 sp = name_at(&db->cpp_name, amt - 1);
1692                 for (size_t i = 0; i < amt; i++, sp++) {
1693                         if (str_length(&sp->strp_l) == 0 &&
1694                             str_length(&sp->strp_r) == 0)
1695                                 continue;
1696 
1697                         paren(sp);
1698                         (void) str_append(&sp->strp_l, "&", 1);
1699                 }
1700 
1701                 save_top(db, amt);
1702                 return (t);
1703 
1704         case 'T':
1705                 t = parse_template_param(first, last, db);
1706                 if (t == first)
1707                         return (first);
1708 
1709                 amt = NAMT(db, n);
1710                 save_top(db, amt);
1711                 if (!db->cpp_try_to_parse_template_args || amt != 1)
1712                         return (t);
1713 
1714                 t1 = parse_template_args(t, last, db);
1715                 if (t1 == t)
1716                         return (t);
1717 
1718                 nfmt(db, "{1:L}{0}", "{1:R}");
1719                 save_top(db, 1);
1720                 return (t1);
1721 
1722         case 'U':
1723                 if (first + 1 == last)
1724                         return (first);
1725 
1726                 t = parse_source_name(first + 1, last, db);
1727                 if (t == first + 1)
1728                         return (first);
1729 
1730                 nfmt(db, "{0}", NULL);
1731 
1732                 t1 = parse_type(t, last, db);
1733                 if (t1 == t || NAMT(db, n) < 2)
1734                         return (first);
1735 
1736                 const str_t *name = &name_at(&db->cpp_name, 1)->strp_l;
1737 
1738                 if (str_length(name) > 0 &&
1739                     strncmp(name->str_s, "objcproto", 9) != 0) {
1740                         nfmt(db, "{0} {1}", NULL);
1741                 } else {
1742                         t = parse_source_name(name->str_s + 9,
1743                             name->str_s + name->str_len, db);
1744                         if (t != name->str_s + 9) {
1745                                 nfmt(db, "{1}<{0}>", NULL);
1746 
1747                                 str_pair_t save = {0};
1748 
1749                                 name_pop(&db->cpp_name, &save);
1750 
1751                                 /* get rid of 'objcproto' */
1752                                 name_pop(&db->cpp_name, NULL);
1753                                 CK(name_add_str(&db->cpp_name, &save.strp_l,
1754                                     &save.strp_r));
1755                         } else {
1756                                 nfmt(db, "{1} {0}", NULL);
1757                         }
1758                 }
1759 
1760                 save_top(db, 1);
1761                 return (t1);
1762 
1763         case 'S':
1764                 if (first + 1 != last && first[1] == 't') {
1765                         t = parse_name(first, last, NULL, db);
1766                         if (t == first || NAMT(db, n) == 0)
1767                                 return (first);
1768 
1769                         save_top(db, 1);
1770                         return (t);
1771                 }
1772 
1773                 t = parse_substitution(first, last, db);
1774                 if (t == first)
1775                         return (first);
1776 
1777                 /*
1778                  * If the substitution is a <template-param>, it might
1779                  * be followed by <template-args>
1780                  */
1781                 t1 = parse_template_args(t, last, db);
1782                 if (t1 == t)
1783                         return (t);
1784 
1785                 if (NAMT(db, n) < 2)
1786                         return (t);
1787 
1788                 nfmt(db, "{1:L}{0}", "{1:R}");
1789                 save_top(db, 1);
1790                 return (t1);
1791 
1792         case 'D':
1793                 if (first + 1 == last)
1794                         return (first);
1795 
1796                 switch (first[1]) {
1797                 case 'p':
1798                         t = parse_type(first + 2, last, db);
1799                         if (t == first + 2)
1800                                 break;
1801 
1802                         save_top(db, NAMT(db, n));
1803                         return (t);
1804 
1805                 case 't':
1806                 case 'T':
1807                         t = parse_decltype(first, last, db);
1808                         if (first == t)
1809                                 break;
1810 
1811                         save_top(db, 1);
1812                         return (t);
1813 
1814                 case 'v':
1815                         t = parse_vector_type(first, last, db);
1816                         if (first == t)
1817                                 break;
1818 
1819                         if (NAMT(db, n) == 0)
1820                                 return (first);
1821 
1822                         save_top(db, 1);
1823                         return (t);
1824                 }
1825                 break;
1826         }
1827 
1828         /*
1829          * must check for builtin-types before class-enum-types to avoid
1830          * ambiguities with operator-names
1831          */
1832         t = parse_builtin_type(first, last, db);
1833         if (t != first)
1834                 return (t);
1835 
1836         t = parse_name(first, last, NULL, db);
1837         if (t == first || NAMT(db, n) == 0)
1838                 return (first);
1839 
1840         save_top(db, 1);
1841         return (t);
1842 }
1843 
1844 static const char *
1845 parse_qual_type(const char *first, const char *last, cpp_db_t *db)
1846 {
1847         VERIFY3P(first, <=, last);
1848 
1849         const char *t = NULL;
1850         const char *t1 = NULL;
1851         unsigned cv = 0;
1852 
1853         t = parse_cv_qualifiers(first, last, &cv);
1854         if (t == first)
1855                 return (first);
1856 
1857         size_t n = nlen(db);
1858         boolean_t is_func = !!(t[0] == 'F');
1859 
1860         t1 = parse_type(t, last, db);
1861         size_t amt = NAMT(db, n);
1862         if (t == t1 || amt == 0)
1863                 return (first);
1864 
1865         if (is_func)
1866                 sub_pop(&db->cpp_subs);
1867 
1868         str_pair_t *sp = name_at(&db->cpp_name, amt - 1);
1869 
1870         for (size_t i = 0; i < amt; i++, sp++) {
1871                 str_t *s = NULL;
1872 
1873                 if (!is_func) {
1874                         s = &sp->strp_l;
1875 
1876                         if (str_length(s) == 0)
1877                                 continue;
1878 
1879                         if (cv & 1)
1880                                 (void) str_append(s, " const", 6);
1881                         if (cv & 2)
1882                                 (void) str_append(s, " volatile", 9);
1883                         if (cv & 4)
1884                                 (void) str_append(s, " restrict", 9);
1885 
1886                         continue;
1887                 }
1888 
1889                 s = &sp->strp_r;
1890                 size_t pos = str_length(s);
1891 
1892                 if (pos > 0 && s->str_s[pos - 1] == '&') {
1893                         pos--;
1894                         if (s->str_s[pos - 1] == '&')
1895                                 pos--;
1896                 }
1897 
1898                 if (cv & 1) {
1899                         (void) str_insert(s, pos, " const", 6);
1900                         pos += 6;
1901                 }
1902                 if (cv & 2) {
1903                         (void) str_insert(s, pos, " volatile", 9);
1904                         pos += 9;
1905                 }
1906                 if (cv & 4) {
1907                         (void) str_insert(s, pos, " restrict", 9);
1908                 }
1909         }
1910 
1911         save_top(db, amt);
1912         return (t1);
1913 }
1914 
1915 /*
1916  * at <type>              # alignof (a type)
1917  * az <expression>        # alignof (a expression)
1918  */
1919 static const char *
1920 parse_alignof(const char *first, const char *last, cpp_db_t *db)
1921 {
1922         VERIFY3P(first, <=, last);
1923 
1924         if (last - first < 2)
1925                 return (first);
1926 
1927         const char *(*fn)(const char *, const char *, cpp_db_t *);
1928 
1929         fn = (first[1] == 't') ? parse_type : parse_expression;
1930 
1931         size_t n = nlen(db);
1932         const char *t = fn(first + 2, last, db);
1933         if (t == first + 2 || NAMT(db, n) != 1)
1934                 return (first);
1935 
1936         nfmt(db, "alignof ({0})", NULL);
1937         return (t);
1938 }
1939 
1940 /*
1941  * st <type>      # sizeof (a type)
1942  * sz <expr>      # sizeof (a expression)
1943  */
1944 static const char *
1945 parse_sizeof(const char *first, const char *last, cpp_db_t *db)
1946 {
1947         VERIFY3P(first, <=, last);
1948 
1949         if (last - first < 2)
1950                 return (first);
1951 
1952         VERIFY3U(first[0], ==, 's');
1953 
1954         const char *t = NULL;
1955         size_t n = nlen(db);
1956 
1957         switch (first[1]) {
1958         case 't':
1959                 t = parse_type(first + 2, last, db);
1960                 break;
1961         case 'z':
1962                 t = parse_expression(first + 2, last, db);
1963                 break;
1964         default:
1965                 return (first);
1966         }
1967         if (t == first + 2 || NAMT(db, n) != 1)
1968                 return (first);
1969 
1970         nfmt(db, "sizeof ({0})", NULL);
1971         return (t);
1972 }
1973 
1974 /* BEGIN CSTYLED */
1975 /*
1976  * <function-param> ::= fp <top-level CV-qualifiers> _                                     # L == 0, first parameter
1977  *                  ::= fp <top-level CV-qualifiers> <parameter-2 non-negative number> _   # L == 0, second and later parameters
1978  *                  ::= fL <L-1 non-negative number> p <top-level CV-qualifiers> _         # L > 0, first parameter
1979  *                  ::= fL <L-1 non-negative number> p <top-level CV-qualifiers> <parameter-2 non-negative number> _   # L > 0, second and later parameters
1980  */
1981 /* END CSTYLED */
1982 static const char *
1983 parse_function_param(const char *first, const char *last, cpp_db_t *db)
1984 {
1985         VERIFY3P(first, <=, last);
1986 
1987         if (last - first < 3 || first[0] != 'f')
1988                 return (first);
1989 
1990         const char *t1 = first + 2;
1991         const char *t2 = NULL;
1992         unsigned cv = 0;
1993 
1994         if (first[1] == 'L') {
1995                 t2 = parse_number(t1, last, db->cpp_loc);
1996                 if (t2 == last || t2[0] != 'p')
1997                         return (first);
1998                 t1 = t2;
1999         }
2000 
2001         if (first[1] != 'p')
2002                 return (first);
2003 
2004         t1 = parse_cv_qualifiers(t1, last, &cv);
2005         t2 = parse_number(t1, last, db->cpp_loc);
2006         if (t2 == last || t2[0] != '_')
2007                 return (first);
2008 
2009         if (t2 - t1 > 0)
2010                 nadd_l(db, t1, (size_t)(t2 - t1));
2011         else
2012                 nadd_l(db, "", 0);
2013 
2014         nfmt(db, "fp{0}", NULL);
2015         return (t2 + 1);
2016 }
2017 
2018 /*
2019  * sZ <template-param>            # size of a parameter pack
2020  * sZ <function-param>            # size of a function parameter pack
2021  */
2022 static const char *
2023 parse_sizeof_param_pack_expr(const char *first, const char *last, cpp_db_t *db)
2024 {
2025         VERIFY3P(first, <=, last);
2026 
2027         if (last - first < 3)
2028                 return (first);
2029 
2030         VERIFY3U(first[0], ==, 's');
2031         VERIFY3U(first[1], ==, 'Z');
2032 
2033         if (first[2] != 'T' && first[2] != 'f')
2034                 return (first);
2035 
2036         const char *t = NULL;
2037         size_t n = nlen(db);
2038 
2039         if (first[2] == 'T')
2040                 t = parse_template_param(first + 2, last, db);
2041         else
2042                 t = parse_function_param(first + 2, last, db);
2043 
2044         if (t == first + 2)
2045                 return (first);
2046 
2047         njoin(db, NAMT(db, n), ", ");
2048         nfmt(db, "sizeof...({0})", NULL);
2049         return (t);
2050 }
2051 
2052 /*
2053  * te <expression>                                      # typeid (expression)
2054  * ti <type>                                            # typeid (type)
2055  */
2056 static const char *
2057 parse_typeid_expr(const char *first, const char *last, cpp_db_t *db)
2058 {
2059         VERIFY3P(first, <=, last);
2060 
2061         if (last - first < 3)
2062                 return (first);
2063 
2064         VERIFY3U(first[0], ==, 't');
2065         VERIFY(first[1] == 'e' || first[1] == 'i');
2066 
2067         const char *t = NULL;
2068         size_t n = nlen(db);
2069 
2070         if (first[1] == 'e')
2071                 t = parse_expression(first + 2, last, db);
2072         else
2073                 t = parse_type(first + 2, last, db);
2074 
2075         if (t == first + 2 || NAMT(db, n) != 1)
2076                 return (first);
2077 
2078         nfmt(db, "typeid ({0})", NULL);
2079         return (t);
2080 }
2081 
2082 /*
2083  * tr                                                   # throw
2084  * tw <expression>                                        # throw expression
2085  */
2086 static const char *
2087 parse_throw_expr(const char *first, const char *last, cpp_db_t *db)
2088 {
2089         VERIFY3P(first, <=, last);
2090 
2091         if (last - first < 3)
2092                 return (first);
2093 
2094         VERIFY3U(first[0], ==, 't');
2095         VERIFY(first[1] == 'w' || first[1] == 'r');
2096 
2097         if (first[1] == 'r') {
2098                 nadd_l(db, "throw", 0);
2099                 return (first + 2);
2100         }
2101 
2102         size_t n = nlen(db);
2103         const char *t = parse_expression(first + 2, last, db);
2104         if (t == first + 2 || NAMT(db, n) != 1)
2105                 return (first);
2106 
2107         nfmt(db, "throw {0}", NULL);
2108         return (t);
2109 }
2110 
2111 /* ds <expression> <expression>             # expr.*expr */
2112 static const char *
2113 parse_dot_star_expr(const char *first, const char *last, cpp_db_t *db)
2114 {
2115         VERIFY3P(first, <=, last);
2116 
2117         if (last - first < 3)
2118                 return (first);
2119 
2120         VERIFY3U(first[0], ==, 'd');
2121         VERIFY3U(first[1], ==, 's');
2122 
2123         size_t n = nlen(db);
2124         const char *t = parse_expression(first + 2, last, db);
2125         if (t == first + 2)
2126                 return (first);
2127 
2128         const char *t2 = parse_expression(t, last, db);
2129         if (t == t2 || NAMT(db, n) != 2)
2130                 return (first);
2131 
2132         nfmt(db, "{1}.*{0}", NULL);
2133         return (t2);
2134 }
2135 
2136 /* dt <expression> <unresolved-name>                # expr.name */
2137 static const char *
2138 parse_dot_expr(const char *first, const char *last, cpp_db_t *db)
2139 {
2140         VERIFY3P(first, <=, last);
2141 
2142         if (last - first < 3)
2143                 return (first);
2144 
2145         VERIFY3U(first[0], ==, 'd');
2146         VERIFY3U(first[1], ==, 't');
2147 
2148         const char *t = parse_expression(first + 2, last, db);
2149         if (t == first + 2)
2150                 return (first);
2151 
2152         const char *t1 = parse_unresolved_name(t, last, db);
2153         if (t1 == t)
2154                 return (first);
2155 
2156         nfmt(db, "{1}.{0}", NULL);
2157         return (t1);
2158 }
2159 
2160 /* cl <expression>+ E             # call */
2161 static const char *
2162 parse_call_expr(const char *first, const char *last, cpp_db_t *db)
2163 {
2164         VERIFY3P(first, <=, last);
2165 
2166         if (last - first < 4)
2167                 return (first);
2168 
2169         VERIFY3U(first[0], ==, 'c');
2170         VERIFY3U(first[1], ==, 'l');
2171 
2172         const char *t = first + 2;
2173         const char *t1 = NULL;
2174         size_t n = nlen(db);
2175 
2176         for (t = first + 2; t != last && t[0] != 'E'; t = t1) {
2177                 t1 = parse_expression(t, last, db);
2178                 if (t1 == t)
2179                         return (first);
2180         }
2181 
2182         size_t amt = NAMT(db, n);
2183 
2184         if (t == last || amt == 0)
2185                 return (first);
2186 
2187         njoin(db, amt - 1, ", ");
2188         nfmt(db, "{1}({0})", NULL);
2189 
2190         VERIFY3U(t[0], ==, 'E');
2191         return (t + 1);
2192 }
2193 
2194 /* BEGIN CSTYLED */
2195 /*
2196  * cv <type> <expression>   # conversion with one argument
2197  * cv <type> _ <expression>* E      # conversion with a different number of arguments
2198  */
2199 /* END CSTYLED */
2200 static const char *
2201 parse_conv_expr(const char *first, const char *last, cpp_db_t *db)
2202 {
2203         VERIFY3P(first, <=, last);
2204 
2205         if (last - first < 3)
2206                 return (first);
2207 
2208         VERIFY3U(first[0], ==, 'c');
2209         VERIFY3U(first[1], ==, 'v');
2210 
2211         const char *t = NULL;
2212         const char *t1 = NULL;
2213         size_t n = nlen(db);
2214 
2215         boolean_t try_to_parse_template_args =
2216             db->cpp_try_to_parse_template_args;
2217 
2218         db->cpp_try_to_parse_template_args = B_FALSE;
2219         t = parse_type(first + 2, last, db);
2220         db->cpp_try_to_parse_template_args = try_to_parse_template_args;
2221 
2222         if (t == first + 2)
2223                 return (first);
2224 
2225         if (t[0] != '_') {
2226                 t1 = parse_expression(t, last, db);
2227                 if (t1 == t)
2228                         return (first);
2229 
2230                 t = t1;
2231         } else {
2232                 size_t n1 = nlen(db);
2233 
2234                 /* skip _ */
2235                 t++;
2236                 while (t[0] != 'E' && t != last) {
2237                         t1 = parse_expression(t, last, db);
2238                         if (t1 == t)
2239                                 return (first);
2240                         t1 = t;
2241                 }
2242 
2243                 /* E */
2244                 t++;
2245 
2246                 njoin(db, NAMT(db, n1), ", ");
2247         }
2248 
2249         if (NAMT(db, n) < 2)
2250                 return (first);
2251 
2252         nfmt(db, "({1})({0})", NULL);
2253         return (t);
2254 }
2255 
2256 /* <simple-id> ::= <source-name> [ <template-args> ] */
2257 static const char *
2258 parse_simple_id(const char *first, const char *last, cpp_db_t *db)
2259 {
2260         VERIFY3P(first, <=, last);
2261 
2262         const char *t = parse_source_name(first, last, db);
2263         if (t == first)
2264                 return (t);
2265 
2266         const char *t1 = parse_template_args(t, last, db);
2267         if (t == t1)
2268                 return (t);
2269 
2270         nfmt(db, "{1}{0}", NULL);
2271         return (t1);
2272 }
2273 
2274 /*
2275  * <unresolved-type> ::= <template-param>
2276  *                   ::= <decltype>
2277  *                   ::= <substitution>
2278  */
2279 static const char *
2280 parse_unresolved_type(const char *first, const char *last, cpp_db_t *db)
2281 {
2282         VERIFY3P(first, <=, last);
2283 
2284         if (first == last)
2285                 return (first);
2286 
2287         const char *t = first;
2288         size_t n = nlen(db);
2289 
2290         switch (first[0]) {
2291         case 'T':
2292                 t = parse_template_param(first, last, db);
2293                 if (t == first || NAMT(db, n) != 1) {
2294                         for (size_t i = 0; i < NAMT(db, n); i++)
2295                                 name_pop(&db->cpp_name, NULL);
2296                         return (first);
2297                 }
2298                 save_top(db, 1);
2299                 return (t);
2300 
2301         case 'D':
2302                 t = parse_decltype(first, last, db);
2303                 if (t == first || NAMT(db, n) == 0)
2304                         return (first);
2305                 save_top(db, 1);
2306                 return (t);
2307 
2308         case 'S':
2309                 t = parse_substitution(first, last, db);
2310                 if (t != first)
2311                         return (t);
2312 
2313                 if (last - first < 2 || first[1] != 't')
2314                         return (first);
2315 
2316                 t = parse_unqualified_name(first + 2, last, db);
2317                 if (t == first + 2 || NAMT(db, n) == 0)
2318                         return (first);
2319 
2320                 nfmt(db, "std::{0:L}", "{0:R}");
2321                 save_top(db, 1);
2322                 return (t);
2323         }
2324 
2325         return (first);
2326 }
2327 
2328 /* sp <expression>                # pack expansion */
2329 static const char *
2330 parse_pack_expansion(const char *first, const char *last, cpp_db_t *db)
2331 {
2332         VERIFY3P(first, <=, last);
2333 
2334         if (last - first < 3)
2335                 return (first);
2336 
2337         VERIFY3U(first[0], ==, 's');
2338         VERIFY3U(first[1], ==, 'p');
2339 
2340         const char *t = parse_expression(first + 2, last, db);
2341         if (t == first +2)
2342                 return (first);
2343 
2344         return (t);
2345 }
2346 
2347 /*
2348  * <unscoped-name> ::= <unqualified-name>
2349  *                 ::= St <unqualified-name>   # ::std::
2350  * extension       ::= StL<unqualified-name>
2351  */
2352 static const char *
2353 parse_unscoped_name(const char *first, const char *last, cpp_db_t *db)
2354 {
2355         VERIFY3P(first, <=, last);
2356 
2357         if (last - first < 2)
2358                 return (first);
2359 
2360         const char *t = first;
2361         const char *t1 = NULL;
2362         boolean_t st = B_FALSE;
2363 
2364         if (first[0] == 'S' && first[1] == 't') {
2365                 st = B_TRUE;
2366                 t = first + 2;
2367 
2368                 if (first + 3 != last && first[2] == 'L')
2369                         t++;
2370         }
2371 
2372         t1 = parse_unqualified_name(t, last, db);
2373         if (t == t1)
2374                 return (first);
2375 
2376         if (st)
2377                 nfmt(db, "std::{0}", NULL);
2378 
2379         return (t1);
2380 }
2381 
2382 /*
2383  * <unqualified-name> ::= <operator-name>
2384  *                    ::= <ctor-dtor-name>
2385  *                    ::= <source-name>
2386  *                    ::= <unnamed-type-name>
2387  */
2388 const char *
2389 parse_unqualified_name(const char *first, const char *last, cpp_db_t *db)
2390 {
2391         VERIFY3P(first, <=, last);
2392 
2393         if (first == last)
2394                 return (first);
2395 
2396         switch (*first) {
2397         case 'C':
2398         case 'D':
2399                 return (parse_ctor_dtor_name(first, last, db));
2400         case 'U':
2401                 return (parse_unnamed_type_name(first, last, db));
2402 
2403         case '1':
2404         case '2':
2405         case '3':
2406         case '4':
2407         case '5':
2408         case '6':
2409         case '7':
2410         case '8':
2411         case '9':
2412                 return (parse_source_name(first, last, db));
2413         default:
2414                 return (parse_operator_name(first, last, db));
2415         }
2416 }
2417 
2418 /*
2419  * <unnamed-type-name> ::= Ut [ <nonnegative number> ] _
2420  *                     ::= <closure-type-name>
2421  *
2422  * <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
2423  *
2424  * <lambda-sig> ::= <parameter type>+
2425  *                      # Parameter types or "v" if the lambda has no parameters
2426  */
2427 static const char *
2428 parse_unnamed_type_name(const char *first, const char *last, cpp_db_t *db)
2429 {
2430         VERIFY3P(first, <=, last);
2431 
2432         if (last - first < 2 || first[0] != 'U')
2433                 return (first);
2434 
2435         if (first[1] != 't' && first[1] != 'l')
2436                 return (first);
2437 
2438         const char *t1 = first + 2;
2439         const char *t2 = NULL;
2440 
2441         if (first[1] == 't') {
2442                 while (t1 != last && t1[0] != '_' &&
2443                     isdigit_l(t1[0], db->cpp_loc))
2444                         t1++;
2445 
2446                 if (t1[0] != '_')
2447                         return (first);
2448 
2449                 if (t1 == first + 2)
2450                         nadd_l(db, "", 0);
2451                 else
2452                         nadd_l(db, first + 2, (size_t)(t1 - first - 2));
2453 
2454                 nfmt(db, "'unnamed{0}'", NULL);
2455                 return (t1 + 1);
2456         }
2457 
2458         size_t n = nlen(db);
2459 
2460         if (first[2] != 'v') {
2461                 do {
2462                         t2 = parse_type(t1, last, db);
2463                         if (t1 == t2)
2464                                 return (first);
2465                         t1 = t2;
2466                 } while (t1 != last && t1[0] != 'E');
2467 
2468                 if (t1 == last || NAMT(db, n) < 1)
2469                         return (first);
2470 
2471                 if (NAMT(db, n) < 1)
2472                         return (first);
2473         } else {
2474                 t1++;
2475                 if (t1[0] != 'E')
2476                         return (first);
2477         }
2478 
2479         njoin(db, NAMT(db, n), ", ");
2480 
2481         /* E */
2482         t1++;
2483 
2484         t2 = t1;
2485         while (t2 != last && t2[0] != '_') {
2486                 if (!isdigit_l(*t2++, db->cpp_loc))
2487                         return (first);
2488         }
2489 
2490         if (t2[0] != '_')
2491                 return (first);
2492 
2493         if (t2 - t1 > 0)
2494                 nadd_l(db, t1, (size_t)(t2 - t1));
2495         else
2496                 nadd_l(db, "", 0);
2497 
2498         nfmt(db, "'lambda{0}'({1})", NULL);
2499 
2500         /* _ */
2501         return (t2 + 1);
2502 }
2503 
2504 static struct {
2505         const char *alias;
2506         const char *fullname;
2507         const char *basename;
2508 } aliases[] = {
2509         {
2510                 "std::string",
2511                 "std::basic_string<char, std::char_traits<char>, "
2512                     "std::allocator<char> >",
2513                 "basic_string"
2514         },
2515         {
2516                 "std::istream",
2517                 "std::basic_istream<char, std::char_traits<char> >",
2518                 "basic_istream"
2519         },
2520         {
2521                 "std::ostream",
2522                 "std::basic_ostream<char, std::char_traits<char> >",
2523                 "basic_ostream"
2524         },
2525         {
2526                 "std::iostream",
2527                 "std::basic_iostream<char, std::char_traits<char> >",
2528                 "basic_iostream"
2529         }
2530 };
2531 
2532 static void
2533 basename(cpp_db_t *db)
2534 {
2535         str_t *s = TOP_L(db);
2536 
2537         for (size_t i = 0; i < ARRAY_SIZE(aliases); i++) {
2538                 if (str_length(s) != strlen(aliases[i].alias))
2539                         continue;
2540                 if (strncmp(aliases[i].alias, s->str_s, str_length(s)) != 0)
2541                         continue;
2542 
2543                 /* swap out alias for full name */
2544                 sysdem_ops_t *ops = s->str_ops;
2545                 str_fini(s);
2546                 str_init(s, ops);
2547                 str_set(s, aliases[i].fullname, 0);
2548 
2549                 nadd_l(db, aliases[i].basename, 0);
2550                 return;
2551         }
2552 
2553         const char *start = s->str_s;
2554         const char *end = s->str_s + s->str_len;
2555 
2556         /*
2557          * if name ends with a template i.e. <.....> back up to start
2558          * of outermost template
2559          */
2560         unsigned c = 0;
2561 
2562         if (end[-1] == '>') {
2563                 for (; end > start; end--) {
2564                         switch (end[-1]) {
2565                         case '<':
2566                                 if (--c == 0) {
2567                                         end--;
2568                                         goto out;
2569                                 }
2570                                 break;
2571                         case '>':
2572                                 c++;
2573                                 break;
2574                         }
2575                 }
2576         }
2577 
2578 out:
2579         VERIFY3P(end, >=, start);
2580 
2581         if (end - start < 2) {
2582                 nadd_l(db, "", 0);
2583                 return;
2584         }
2585 
2586         for (start = end - 1; start > s->str_s; start--) {
2587                 if (start[0] == ':') {
2588                         start++;
2589                         break;
2590                 }
2591         }
2592 
2593         VERIFY3P(end, >=, start);
2594 
2595         nadd_l(db, start, (size_t)(end - start));
2596 }
2597 
2598 /*
2599  * <ctor-dtor-name> ::= C1    # complete object constructor
2600  *                  ::= C2    # base object constructor
2601  *                  ::= C3    # complete object allocating constructor
2602  *   extension      ::= C5    # ?
2603  *                  ::= D0    # deleting destructor
2604  *                  ::= D1    # complete object destructor
2605  *                  ::= D2    # base object destructor
2606  *   extension      ::= D5    # ?
2607  */
2608 static const char *
2609 parse_ctor_dtor_name(const char *first, const char *last, cpp_db_t *db)
2610 {
2611         VERIFY3P(first, <=, last);
2612 
2613         if (last - first < 2 || nempty(db) || str_length(TOP_L(db)) == 0)
2614                 return (first);
2615 
2616         switch (first[0]) {
2617         case 'C':
2618                 switch (first[1]) {
2619                 case '1':
2620                 case '2':
2621                 case '3':
2622                 case '5':
2623                         basename(db);
2624                         break;
2625                 default:
2626                         return (first);
2627                 }
2628                 break;
2629         case 'D':
2630                 switch (first[1]) {
2631                 case '0':
2632                 case '1':
2633                 case '2':
2634                 case '5':
2635                         basename(db);
2636                         (void) str_insert(TOP_L(db), 0, "~", 1);
2637                         break;
2638                 default:
2639                         return (first);
2640                 }
2641                 break;
2642         default:
2643                 return (first);
2644         }
2645 
2646         db->cpp_parsed_ctor_dtor_cv = B_TRUE;
2647         return (first + 2);
2648 }
2649 
2650 static const char *
2651 parse_integer_literal(const char *first, const char *last, const char *fmt,
2652     cpp_db_t *db)
2653 {
2654         VERIFY3P(first, <=, last);
2655 
2656         const char *t = parse_number(first, last, db->cpp_loc);
2657         const char *start = first;
2658 
2659         if (t == first || t == last || t[0] != 'E')
2660                 return (first);
2661 
2662         if (first[0] == 'n')
2663                 start++;
2664 
2665         nadd_l(db, start, (size_t)(t - start));
2666         if (start != first)
2667                 nfmt(db, "-{0}", NULL);
2668 
2669         nfmt(db, fmt, NULL);
2670         return (t + 1);
2671 }
2672 
2673 static struct float_data_s {
2674         const char *spec;
2675         size_t mangled_size;
2676         size_t max_demangled_size;
2677         char type;
2678 } float_info[] = {
2679         { "%af", 8, 24, 'f' },          /* float */
2680         { "%a", 16, 32, 'd' },          /* double */
2681         { "%LaL", 20, 40, 'e' }         /* long double */
2682 };
2683 
2684 static const char *
2685 parse_floating_literal(const char *first, const char *last, cpp_db_t *db)
2686 {
2687         VERIFY3P(first, <=, last);
2688         VERIFY(first[0] == 'f' || first[0] == 'd' || first[0] == 'e');
2689 
2690         const struct float_data_s *fd = NULL;
2691 
2692         for (size_t i = 0; i < ARRAY_SIZE(float_info); i++) {
2693                 if (float_info[i].type != first[0])
2694                         continue;
2695 
2696                 fd = &float_info[i];
2697                 break;
2698         }
2699 
2700         if (fd == NULL || (size_t)(last - first) < fd->mangled_size)
2701                 return (first);
2702 
2703         union {
2704                 union {
2705                         float v;
2706                         char buf[sizeof (float)];
2707                 } f;
2708                 union {
2709                         double v;
2710                         char buf[sizeof (double)];
2711                 } d;
2712                 union {
2713                         long double v;
2714                         char buf[sizeof (long double)];
2715                 } ld;
2716         } conv;
2717 
2718         const char *t = NULL;
2719         char *e = NULL;
2720 
2721         switch (first[0]) {
2722         case 'f':
2723                 e = conv.f.buf;
2724                 break;
2725         case 'd':
2726                 e = conv.d.buf;
2727                 break;
2728         case 'e':
2729                 e = conv.ld.buf;
2730                 break;
2731         }
2732         last = first + fd->mangled_size + 1;
2733 
2734 #if defined(_BIG_ENDIAN)
2735         for (t = first + 1; t != last; t++, e++) {
2736                 if (!is_xdigit(t[0]))
2737                         return (first);
2738 
2739                 unsigned d1 = isdigit_l(t[0], db->cpp_loc) ? t[0] - '0' : t[0] - 'a' + 10;
2740                 t++;
2741                 unsigned d0 = isdigit_l(t[0], db->cpp_loc) ? t[0] - '0' : t[0] - 'a' + 10;
2742 
2743                 *e = (d1 << 4) + d0;
2744         }
2745 #elif defined(_LITTLE_ENDIAN)
2746         for (t = last - 1; t > first; t--, e++) {
2747                 if (!is_xdigit(t[0]))
2748                         return (first);
2749 
2750                 unsigned d0 = isdigit_l(t[0], db->cpp_loc) ? t[0] - '0' : t[0] - 'a' + 10;
2751                 t--;
2752                 unsigned d1 = isdigit_l(t[0], db->cpp_loc) ? t[0] - '0' : t[0] - 'a' + 10;
2753 
2754                 *e = (d1 << 4) + d0;
2755         }
2756         t = last;
2757 #else
2758 #error One of _BIG_ENDIAN or _LITTLE_ENDIAN must be defined
2759 #endif
2760 
2761         if (t[0] != 'E')
2762                 return (first);
2763 
2764         str_t num = { 0 };
2765         str_init(&num, db->cpp_ops);
2766 
2767         num.str_size = fd->max_demangled_size + 1;
2768         num.str_s = zalloc(db->cpp_ops, num.str_size);
2769         CK(num.str_s != NULL);
2770 
2771         int n = 0;
2772 
2773         switch (first[0]) {
2774         case 'f':
2775                 n = snprintf(num.str_s, fd->max_demangled_size, fd->spec,
2776                     conv.f.v);
2777                 break;
2778         case 'd':
2779                 n = snprintf(num.str_s, fd->max_demangled_size, fd->spec,
2780                     conv.d.v);
2781                 break;
2782         case 'e':
2783                 n = snprintf(num.str_s, fd->max_demangled_size, fd->spec,
2784                     conv.ld.v);
2785         }
2786 
2787         if (n >= fd->max_demangled_size || n <= 0) {
2788                 str_fini(&num);
2789                 return (first);
2790         }
2791 
2792         num.str_len = n;
2793         (void) name_add_str(&db->cpp_name, &num, NULL);
2794 
2795         return (t + 1);
2796 }
2797 
2798 /*
2799  * <expr-primary> ::= L <type> <value number> E       # integer literal
2800  *                ::= L <type> <value float> E      # floating literal
2801  *                ::= L <string type> E           # string literal
2802  *                ::= L <nullptr type> E  # nullptr literal (i.e., "LDnE")
2803  *
2804  *                ::= L <type> <real-part float> _ <imag-part float> E
2805  *                                              # complex floating point
2806  *                                              # literal (C 2000)
2807  *
2808  *                ::= L <mangled-name> E  # external name
2809  */
2810 static struct {
2811         int             c;
2812         const char      *fmt;
2813 } int_lits[] = {
2814         { 'a', "(signed char){0}" },
2815         { 'c', "(char){0}" },
2816         { 'h', "(unsigned char){0}" },
2817         { 'i', "{0}" },
2818         { 'j', "{0}u" },
2819         { 'l', "{0}l" },
2820         { 'm', "{0}ul" },
2821         { 'n', "(__int128){0}" },
2822         { 'o', "(unsigned __int128){0}" },
2823         { 's', "(short){0}" },
2824         { 't', "(unsigned short){0}" },
2825         { 'w', "(wchar_t){0}" },
2826         { 'x', "{0}ll" },
2827         { 'y', "{0}ull" }
2828 };
2829 
2830 static const char *
2831 parse_expr_primary(const char *first, const char *last, cpp_db_t *db)
2832 {
2833         VERIFY3P(first, <=, last);
2834 
2835         if (last - first < 4 || first[0] != 'L')
2836                 return (first);
2837 
2838         const char *t = NULL;
2839 
2840         for (size_t i = 0; i < ARRAY_SIZE(int_lits); i++) {
2841                 if (first[1] == int_lits[i].c) {
2842                         t = parse_integer_literal(first + 2, last,
2843                             int_lits[i].fmt, db);
2844                         return ((t == first + 2) ? first : t);
2845                 }
2846         }
2847 
2848         switch (first[1]) {
2849         case 'b':
2850                 if (first[3] != 'E')
2851                         return (first);
2852 
2853                 switch (first[2]) {
2854                 case '0':
2855                         nadd_l(db, "false", 5);
2856                         break;
2857                 case '1':
2858                         nadd_l(db, "true", 4);
2859                         break;
2860                 default:
2861                         return (first);
2862                 }
2863                 return (first + 4);
2864         case 'd':       /* double */
2865         case 'e':       /* long double */
2866         case 'f':       /* float */
2867                 t = parse_floating_literal(first + 1, last, db);
2868                 return ((t == first + 1) ? first : t);
2869         case 'T':
2870 /* BEGIN CSTYLED */
2871                 /*
2872                  * Invalid mangled name per
2873                  *   http://sourcerytools.com/pipermail/cxx-abi-dev/2011-August/002422.html
2874                  *
2875                  */
2876 /* END CSTYLED */
2877                 return (first);
2878         case '_':
2879                 if (first[2] != 'Z')
2880                         return (first);
2881 
2882                 t = parse_encoding(first + 3, last, db);
2883                 if (t == first + 3 || t == last || t[0] != 'E')
2884                         return (first);
2885 
2886                 /* skip E */
2887                 return (t + 1);
2888         default:
2889                 t = parse_type(first + 1, last, db);
2890                 if (t == first + 1 || t == last)
2891                         return (first);
2892 
2893                 if (t[0] == 'E')
2894                         return (t + 1);
2895 
2896                 const char *n;
2897                 for (n = t; n != last && isdigit_l(n[0], db->cpp_loc); n++)
2898                         ;
2899                 if (n == last || nempty(db) || n[0] != 'E')
2900                         return (first);
2901                 if (n == t)
2902                         return (t);
2903 
2904                 nadd_l(db, t, (size_t)(n - t));
2905                 nfmt(db, "({1}){0}", NULL);
2906 
2907                 return (n + 1);
2908         }
2909 }
2910 
2911 /*
2912  *   <operator-name>
2913  *                   ::= aa    # &&
2914  *                   ::= ad    # & (unary)
2915  *                   ::= an    # &
2916  *                   ::= aN    # &=
2917  *                   ::= aS    # =
2918  *                   ::= cl    # ()
2919  *                   ::= cm    # ,
2920  *                   ::= co    # ~
2921  *                   ::= cv <type>    # (cast)
2922  *                   ::= da    # delete[]
2923  *                   ::= de    # * (unary)
2924  *                   ::= dl    # delete
2925  *                   ::= dv    # /
2926  *                   ::= dV    # /=
2927  *                   ::= eo    # ^
2928  *                   ::= eO    # ^=
2929  *                   ::= eq    # ==
2930  *                   ::= ge    # >=
2931  *                   ::= gt    # >
2932  *                   ::= ix    # []
2933  *                   ::= le    # <=
2934  *                   ::= li <source-name> # operator ""
2935  *                   ::= ls    # <<
2936  *                   ::= lS    # <<=
2937  *                   ::= lt    # <
2938  *                   ::= mi    # -
2939  *                   ::= mI    # -=
2940  *                   ::= ml    # *
2941  *                   ::= mL    # *=
2942  *                   ::= mm    # -- (postfix in <expression> context)
2943  *                   ::= na    # new[]
2944  *                   ::= ne    # !=
2945  *                   ::= ng    # - (unary)
2946  *                   ::= nt    # !
2947  *                   ::= nw    # new
2948  *                   ::= oo    # ||
2949  *                   ::= or    # |
2950  *                   ::= oR    # |=
2951  *                   ::= pm    # ->*
2952  *                   ::= pl    # +
2953  *                   ::= pL    # +=
2954  *                   ::= pp    # ++ (postfix in <expression> context)
2955  *                   ::= ps    # + (unary)
2956  *                   ::= pt    # ->
2957  *                   ::= qu    # ?
2958  *                   ::= rm    # %
2959  *                   ::= rM    # %=
2960  *                   ::= rs    # >>
2961  *                   ::= rS    # >>=
2962  *                   ::= v <digit> <source-name> # vendor extended operator
2963  */
2964 static struct {
2965         const char code[3];
2966         const char *op;
2967 } op_tbl[] = {
2968         { "aa", "operator&&" },
2969         { "ad", "operator&" },
2970         { "an", "operator&" },
2971         { "aN", "operator&=" },
2972         { "aS", "operator=" },
2973         { "cl", "operator()" },
2974         { "cm", "operator," },
2975         { "co", "operator~" },
2976         { "da", "operator delete[]" },
2977         { "de", "operator*" },
2978         { "dl", "operator delete" },
2979         { "dv", "operator/" },
2980         { "dV", "operator/=" },
2981         { "eo", "operator^" },
2982         { "eO", "operator^=" },
2983         { "eq", "operator==" },
2984         { "ge", "operator>=" },
2985         { "gt", "operator>" },
2986         { "ix", "operator[]" },
2987         { "le", "operator<=" },
2988         { "ls", "operator<<" },
2989         { "lS", "operator<<=" },
2990         { "lt", "operator<" },
2991         { "mi", "operator-" },
2992         { "mI", "operator-=" },
2993         { "ml", "operator*" },
2994         { "mL", "operator*=" },
2995         { "mm", "operator--" },
2996         { "na", "operator new[]" },
2997         { "ne", "operator!=" },
2998         { "ng", "operator-" },
2999         { "nt", "operator!" },
3000         { "nw", "operator new" },
3001         { "oo", "operator||" },
3002         { "or", "operator|" },
3003         { "oR", "operator|=" },
3004         { "pm", "operator->*" },
3005         { "pl", "operator+" },
3006         { "pL", "operator+=" },
3007         { "pp", "operator++" },
3008         { "ps", "operator+" },
3009         { "pt", "operator->" },
3010         { "qu", "operator?" },
3011         { "rm", "operator%" },
3012         { "rM", "operator%=" },
3013         { "rs", "operator>>" },
3014         { "rS", "operator>>=" }
3015 };
3016 
3017 static const char *
3018 parse_operator_name(const char *first, const char *last, cpp_db_t *db)
3019 {
3020         VERIFY3P(first, <=, last);
3021 
3022         if (last - first < 2)
3023                 return (first);
3024 
3025         for (size_t i = 0; i < ARRAY_SIZE(op_tbl); i++) {
3026                 if (strncmp(first, op_tbl[i].code, 2) != 0)
3027                         continue;
3028 
3029                 nadd_l(db, op_tbl[i].op, 0);
3030                 return (first + 2);
3031         }
3032 
3033         const char *t = NULL;
3034 
3035         if (first[0] == 'l' && first[1] == 'i') {
3036                 t = parse_source_name(first + 2, last, db);
3037                 if (t == first + 2 || nempty(db))
3038                         return (first);
3039 
3040                 nfmt(db, "operator\"\" {0}", NULL);
3041                 return (t);
3042         }
3043 
3044         if (first[0] == 'v') {
3045                 if (!isdigit_l(first[1], db->cpp_loc))
3046                         return (first);
3047 
3048                 t = parse_source_name(first + 2, last, db);
3049                 if (t == first + 2)
3050                         return (first);
3051 
3052                 nfmt(db, "operator {0}", NULL);
3053                 return (t);
3054         }
3055 
3056         if (first[0] != 'c' && first[1] != 'v')
3057                 return (first);
3058 
3059         boolean_t try_to_parse_template_args =
3060             db->cpp_try_to_parse_template_args;
3061 
3062         db->cpp_try_to_parse_template_args = B_FALSE;
3063         t = parse_type(first + 2, last, db);
3064         db->cpp_try_to_parse_template_args = try_to_parse_template_args;
3065 
3066         if (t == first + 2 || nempty(db))
3067                 return (first);
3068 
3069         nfmt(db, "operator {0}", NULL);
3070         db->cpp_parsed_ctor_dtor_cv = B_TRUE;
3071         return (t);
3072 }
3073 
3074 struct type_tbl_s {
3075         int code;
3076         const char *name;
3077 };
3078 
3079 static struct type_tbl_s type_tbl1[] = {
3080         { 'a', "signed char" },
3081         { 'b', "bool" },
3082         { 'c', "char" },
3083         { 'd', "double" },
3084         { 'e', "long double" },
3085         { 'f', "float" },
3086         { 'g', "__float128" },
3087         { 'h', "unsigned char" },
3088         { 'i', "int" },
3089         { 'j', "unsigned int" },
3090         { 'l', "long" },
3091         { 'm', "unsigned long" },
3092         { 'n', "__int128" },
3093         { 'o', "unsigned __int128" },
3094         { 's', "short" },
3095         { 't', "unsigned short" },
3096         { 'v', "void" },
3097         { 'w', "wchar_t" },
3098         { 'x', "long long" },
3099         { 'y', "unsigned long long" },
3100         { 'z', "..." }
3101 };
3102 
3103 static struct type_tbl_s type_tbl2[] = {
3104         { 'a', "auto" },
3105         { 'c', "decltype(auto)" },
3106         { 'd', "decimal64" },
3107         { 'e', "decimal128" },
3108         { 'f', "decimal32" },
3109         { 'h', "decimal16" },
3110         { 'i', "char32_t" },
3111         { 'n', "std::nullptr_t" },
3112         { 's', "char16_t" }
3113 };
3114 
3115 static const char *
3116 parse_builtin_type(const char *first, const char *last, cpp_db_t *db)
3117 {
3118         VERIFY3P(first, <=, last);
3119 
3120         if (first == last)
3121                 return (first);
3122 
3123         size_t i;
3124 
3125         for (i = 0; i < ARRAY_SIZE(type_tbl1); i++) {
3126                 if (first[0] == type_tbl1[i].code) {
3127                         nadd_l(db, type_tbl1[i].name, 0);
3128                         return (first + 1);
3129                 }
3130         }
3131 
3132         if (first[0] == 'D') {
3133                 if (first + 1 == last)
3134                         return (first);
3135                 for (i = 0; i < ARRAY_SIZE(type_tbl2); i++) {
3136                         if (first[1] == type_tbl2[i].code) {
3137                                 nadd_l(db, type_tbl2[i].name, 0);
3138                                 return (first + 2);
3139                         }
3140                 }
3141         }
3142 
3143         if (first[0] == 'u') {
3144                 const char *t = parse_source_name(first + 1, last, db);
3145                 if (t == first + 1)
3146                         return (first);
3147                 return (t);
3148         }
3149 
3150         return (first);
3151 }
3152 
3153 static const char *
3154 parse_base36(const char *first, const char *last, size_t *val, locale_t loc)
3155 {
3156         VERIFY3P(first, <=, last);
3157 
3158         const char *t;
3159 
3160         for (t = first, *val = 0; t != last; t++) {
3161                 if (!isdigit_l(t[0], loc) && !isupper_l(t[0], loc))
3162                         return (t);
3163 
3164                 *val *= 36;
3165 
3166                 if (isdigit_l(t[0], loc))
3167                         *val += t[0] - '0';
3168                 else
3169                         *val += t[0] - 'A' + 10;
3170         }
3171         return (t);
3172 }
3173 
3174 static struct type_tbl_s sub_tbl[] = {
3175         { 'a', "std::allocator" },
3176         { 'b', "std::basic_string" },
3177         { 's', "std::string" },
3178         { 'i', "std::istream" },
3179         { 'o', "std::ostream" },
3180         { 'd', "std::iostream" }
3181 };
3182 
3183 static const char *
3184 parse_substitution(const char *first, const char *last, cpp_db_t *db)
3185 {
3186         VERIFY3P(first, <=, last);
3187 
3188         if (first == last || last - first < 2)
3189                 return (first);
3190 
3191         if (first[0] != 'S')
3192                 return (first);
3193 
3194         for (size_t i = 0; i < ARRAY_SIZE(sub_tbl); i++) {
3195                 if (first[1] == sub_tbl[i].code) {
3196                         nadd_l(db, sub_tbl[i].name, 0);
3197                         return (first + 2);
3198                 }
3199         }
3200 
3201         const char *t = first + 1;
3202         size_t n = 0;
3203 
3204         if (t[0] != '_') {
3205                 t = parse_base36(first + 1, last, &n, db->cpp_loc);
3206                 if (t == first + 1 || t[0] != '_')
3207                         return (first);
3208 
3209                 /*
3210                  * S_ == substitution 0,
3211                  * S0_ == substituion 1,
3212                  * ...
3213                  */
3214                 n++;
3215         }
3216 
3217         if (n >= sub_len(&db->cpp_subs))
3218                 return (first);
3219 
3220         sub(db, n);
3221 
3222         /* skip _ */
3223         VERIFY3U(t[0], ==, '_');
3224 
3225         return (t + 1);
3226 }
3227 
3228 static const char *
3229 parse_source_name(const char *first, const char *last, cpp_db_t *db)
3230 {
3231         VERIFY3P(first, <=, last);
3232 
3233         if (first == last)
3234                 return (first);
3235 
3236         const char *t = NULL;
3237         size_t n = 0;
3238 
3239         for (t = first; t != last && isdigit_l(t[0], db->cpp_loc); t++) {
3240                 /* make sure we don't overflow */
3241                 size_t nn = n * 10;
3242                 if (nn < n)
3243                         return (first);
3244 
3245                 nn += t[0] - '0';
3246                 if (nn < n)
3247                         return (first);
3248 
3249                 n = nn;
3250         }
3251 
3252         if (n == 0 || t == last || t + n > last ||
3253             (uintptr_t)t + n < (uintptr_t)t)
3254                 return (first);
3255 
3256         if (strncmp(t, "_GLOBAL__N", 10) == 0)
3257                 nadd_l(db, "(anonymous namespace)", 0);
3258         else
3259                 nadd_l(db, t, n);
3260 
3261         return (t + n);
3262 }
3263 
3264 /*
3265  * extension:
3266  * <vector-type>           ::= Dv <positive dimension number> _
3267  *                                    <extended element type>
3268  *                         ::= Dv [<dimension expression>] _ <element type>
3269  * <extended element type> ::= <element type>
3270  *                         ::= p # AltiVec vector pixel
3271  */
3272 static const char *
3273 parse_vector_type(const char *first, const char *last, cpp_db_t *db)
3274 {
3275         VERIFY3P(first, <=, last);
3276 
3277         if (last - first < 3)
3278                 return (first);
3279 
3280         VERIFY3U(first[0], ==, 'D');
3281         VERIFY3U(first[1], ==, 'v');
3282 
3283         const char *t = first + 2;
3284         const char *t1 = NULL;
3285 
3286         if (isdigit_l(first[2], db->cpp_loc) && first[2] != '0') {
3287                 t1 = parse_number(t, last, db->cpp_loc);
3288                 if (t1 == last || t1 + 1 == last || t1[0] != '_')
3289                         return (first);
3290 
3291                 nadd_l(db, t, (size_t)(t1 - t));
3292 
3293                 /* skip _ */
3294                 t = t1 + 1;
3295 
3296                 if (t[0] != 'p') {
3297                         t1 = parse_type(t, last, db);
3298                         if (t1 == t)
3299                                 return (first);
3300 
3301                         nfmt(db, "{0} vector[{1}]", NULL);
3302                         return (t1);
3303                 }
3304                 nfmt(db, "{0} pixel vector[{1}]", NULL);
3305                 return (t1);
3306         }
3307 
3308         if (first[2] != '_') {
3309                 t1 = parse_expression(first + 2, last, db);
3310                 if (first == last || t1 == first + 2 || t1[0] != '_')
3311                         return (first);
3312 
3313                 /* skip _ */
3314                 t = t1 + 1;
3315         } else {
3316                 nadd_l(db, "", 0);
3317         }
3318 
3319         t1 = parse_type(t, last, db);
3320         if (t == t1)
3321                 return (first);
3322 
3323         nfmt(db, "{1:L} vector[{0}]", "{1:R}");
3324         return (t1);
3325 }
3326 
3327 /* BEGIN CSTYLED */
3328 /*
3329  * <decltype>  ::= Dt <expression> E  # decltype of an id-expression or class member access (C++0x)
3330  *             ::= DT <expression> E  # decltype of an expression (C++0x)
3331  */
3332 /* END CSTYLED */
3333 static const char *
3334 parse_decltype(const char *first, const char *last, cpp_db_t *db)
3335 {
3336         VERIFY3P(first, <=, last);
3337 
3338         if (last - first < 4)
3339                 return (first);
3340 
3341         VERIFY3U(first[0], ==, 'D');
3342 
3343         if (first[1] != 't' && first[1] != 'T')
3344                 return (first);
3345 
3346         size_t n = nlen(db);
3347         const char *t = parse_expression(first + 2, last, db);
3348         if (NAMT(db, n) != 1 || t == first + 2 || t == last || t[0] != 'E')
3349                 return (first);
3350 
3351         nfmt(db, "decltype({0})", NULL);
3352 
3353         /* skip E */
3354         return (t + 1);
3355 }
3356 
3357 /*
3358  * <array-type> ::= A <positive dimension number> _ <element type>
3359  *              ::= A [<dimension expression>] _ <element type>
3360  */
3361 static const char *
3362 parse_array_type(const char *first, const char *last, cpp_db_t *db)
3363 {
3364         VERIFY3P(first, <=, last);
3365         VERIFY3U(first[0], ==, 'A');
3366 
3367         if (last - first < 3)
3368                 return (first);
3369 
3370         const char *t = first + 1;
3371         const char *t1 = NULL;
3372         size_t n = nlen(db);
3373 
3374         if (t[0] != '_') {
3375                 if (isdigit_l(t[0], db->cpp_loc) && t[0] != '0') {
3376                         t1 = parse_number(t, last, db->cpp_loc);
3377                         if (t1 == last)
3378                                 return (first);
3379 
3380                         nadd_l(db, t, (size_t)(t1 - t));
3381                 } else {
3382                         t1 = parse_expression(t, last, db);
3383                         if (t1 == last || t == t1)
3384                                 return (first);
3385                 }
3386 
3387                 if (t1[0] != '_')
3388                         return (first);
3389 
3390                 t = t1;
3391         } else {
3392                 nadd_l(db, "", 0);
3393         }
3394 
3395         VERIFY3U(t[0], ==, '_');
3396 
3397         t1 = parse_type(t + 1, last, db);
3398         if (t1 == t + 1 || NAMT(db, n) != 2)
3399                 return (first);
3400 
3401         /*
3402          * if we have  " [xxx]" already, want new result to be
3403          * " [yyy][xxx]"
3404          */
3405         str_t *r = &name_top(&db->cpp_name)->strp_r;
3406         if (r->str_len > 1 && r->str_s[0] == ' ' && r->str_s[1] == '[')
3407                 (void) str_erase(r, 0, 1);
3408 
3409         nfmt(db, "{0:L}", " [{1}]{0:R}");
3410         return (t1);
3411 }
3412 
3413 /* <pointer-to-member-type> ::= M <class type> <member type> */
3414 static const char *
3415 parse_pointer_to_member_type(const char *first, const char *last, cpp_db_t *db)
3416 {
3417         VERIFY3P(first, <=, last);
3418 
3419         if (last - first < 3)
3420                 return (first);
3421 
3422         VERIFY3U(first[0], ==, 'M');
3423 
3424         const char *t1 = first + 1;
3425         const char *t2 = NULL;
3426         size_t n = nlen(db);
3427 
3428         t2 = parse_type(t1, last, db);
3429         if (t1 == t2)
3430                 return (first);
3431 
3432         t1 = t2;
3433         t2 = parse_type(t1, last, db);
3434         if (t1 == t2)
3435                 return (first);
3436 
3437         if (NAMT(db, n) != 2)
3438                 return (first);
3439 
3440         str_pair_t *func = name_top(&db->cpp_name);
3441 
3442         if (str_length(&func->strp_r) > 0 && func->strp_r.str_s[0] == '(')
3443                 nfmt(db, "{0:L}({1}::*", "){0:R}");
3444         else
3445                 nfmt(db, "{0:L} {1}::*", "{0:R}");
3446 
3447         return (t2);
3448 }
3449 
3450 /* BEGIN CSTYLED */
3451 /*
3452  * <unresolved-name>
3453  *  extension        ::= srN <unresolved-type> [<template-args>] <unresolved-qualifier-level>* E <base-unresolved-name>
3454  *                   ::= [gs] <base-unresolved-name>                     # x or (with "gs") ::x
3455  *                   ::= [gs] sr <unresolved-qualifier-level>+ E <base-unresolved-name>
3456  *                                                                       # A::x, N::y, A<T>::z; "gs" means leading "::"
3457  *                   ::= sr <unresolved-type> <base-unresolved-name>     # T::x / decltype(p)::x
3458  *  extension        ::= sr <unresolved-type> <template-args> <base-unresolved-name>
3459  *                                                                       # T::N::x /decltype(p)::N::x
3460  *  (ignored)        ::= srN <unresolved-type>  <unresolved-qualifier-level>+ E <base-unresolved-name>
3461  */
3462 /* END CSTYLED */
3463 static const char *
3464 parse_unresolved_name(const char *first, const char *last, cpp_db_t *db)
3465 {
3466         VERIFY3P(first, <=, last);
3467 
3468         if (last - first < 2)
3469                 return (first);
3470 
3471         const char *t = first;
3472         const char *t2 = NULL;
3473         boolean_t global = B_FALSE;
3474         size_t n;
3475 
3476         if (t[0] == 'g' && t[1] == 's') {
3477                 global = B_TRUE;
3478                 t += 2;
3479         }
3480         if (t == last)
3481                 return (first);
3482 
3483         t2 = parse_base_unresolved_name(t, last, db);
3484         if (t != t2) {
3485                 if (global) {
3486                         if (nempty(db))
3487                                 return (first);
3488 
3489                         (void) str_insert(TOP_L(db), 0, "::", 2);
3490                 }
3491                 return (t2);
3492         }
3493 
3494         if (t[0] != 's' || t[1] != 'r' || last - t < 2)
3495                 return (first);
3496 
3497         n = nlen(db);
3498         if (t[2] == 'N') {
3499                 t += 3;
3500                 t2 = parse_unresolved_type(t, last, db);
3501                 if (t2 == t || t2 == last)
3502                         return (first);
3503                 t = t2;
3504 
3505                 t2 = parse_template_args(t, last, db);
3506                 if (t2 != t) {
3507                         if (NAMT(db, n) < 2 || t2 == last)
3508                                 return (first);
3509 
3510                         nfmt(db, "{1:L}{0}", "{1:R}");
3511                         t = t2;
3512                 }
3513 
3514                 VERIFY3U(NAMT(db, n), ==, 1);
3515 
3516                 while (t[0] != 'E') {
3517                         size_t nn = nlen(db);
3518                         t2 = parse_unresolved_qualifier_level(t, last, db);
3519                         if (t == t2 || t == last || NAMT(db, nn) != 1)
3520                                 return (first);
3521 
3522                         t = t2;
3523                 }
3524 
3525                 /* skip E */
3526                 t++;
3527 
3528                 t2 = parse_base_unresolved_name(t, last, db);
3529                 if (t == t2 || NAMT(db, n) < 2)
3530                         return (first);
3531 
3532                 njoin(db, NAMT(db, n), "::");
3533                 return (t2);
3534         }
3535 
3536         t += 2;
3537 
3538         t2 = parse_unresolved_type(t, last, db);
3539         if (t != t2) {
3540                 t = t2;
3541                 t2 = parse_template_args(t, last, db);
3542                 if (t2 != t)
3543                         nfmt(db, "{1:L}{0}", "{1:R}");
3544                 t = t2;
3545 
3546                 t2 = parse_base_unresolved_name(t, last, db);
3547                 if (t == t2 || nlen(db) < 2)
3548                         return (first);
3549 
3550                 nfmt(db, "{1:L}::{0}", "{1:R}");
3551                 return (t2);
3552         }
3553 
3554         t2 = parse_unresolved_qualifier_level(t, last, db);
3555         if (t2 == t || t2 == last)
3556                 return (first);
3557 
3558         t = t2;
3559         if (global && nlen(db) > 0)
3560                 nfmt(db, "::{0:L}", "{0:R}");
3561 
3562         while (t[0] != 'E') {
3563                 t2 = parse_unresolved_qualifier_level(t, last, db);
3564                 if (t == t2 || t == last || nlen(db) < 2)
3565                         return (first);
3566 
3567                 t = t2;
3568         }
3569 
3570         /* skip E */
3571         t++;
3572 
3573         t2 = parse_base_unresolved_name(t, last, db);
3574         if (t == t2 || nlen(db) < 2)
3575                 return (first);
3576 
3577         njoin(db, NAMT(db, n), "::");
3578         return (t2);
3579 }
3580 
3581 /* <unresolved-qualifier-level> ::= <simple-id> */
3582 static const char *
3583 parse_unresolved_qualifier_level(const char *first, const char *last,
3584     cpp_db_t *db)
3585 {
3586         VERIFY3P(first, <=, last);
3587         return (parse_simple_id(first, last, db));
3588 }
3589 
3590 /* BEGIN CSTYLED */
3591 /*
3592  * <base-unresolved-name> ::= <simple-id>                                # unresolved name
3593  *          extension     ::= <operator-name>                            # unresolved operator-function-id
3594  *          extension     ::= <operator-name> <template-args>            # unresolved operator template-id
3595  *                        ::= on <operator-name>                         # unresolved operator-function-id
3596  *                        ::= on <operator-name> <template-args>         # unresolved operator template-id
3597  *                        ::= dn <destructor-name>                       # destructor or pseudo-destructor;
3598  *                                                                       # e.g. ~X or ~X<N-1>
3599  */
3600 /* END CSTYLED */
3601 static const char *
3602 parse_base_unresolved_name(const char *first, const char *last, cpp_db_t *db)
3603 {
3604         VERIFY3P(first, <=, last);
3605 
3606         if (last - first < 2)
3607                 return (first);
3608 
3609         const char *t = NULL;
3610         const char *t1 = NULL;
3611 
3612         if ((first[0] != 'o' && first[0] != 'd') || first[1] != 'n') {
3613                 t = parse_simple_id(first, last, db);
3614                 if (t != first)
3615                         return (t);
3616 
3617                 t = parse_operator_name(first, last, db);
3618                 if (t == first)
3619                         return (first);
3620 
3621                 t1 = parse_template_args(t, last, db);
3622                 if (t1 != t) {
3623                         if (nlen(db) < 2)
3624                                 return (first);
3625                         nfmt(db, "{1:L}{0}", "{1:R}");
3626                 }
3627 
3628                 return (t1);
3629         }
3630 
3631         if (first[0] == 'd') {
3632                 t = parse_destructor_name(first + 2, last, db);
3633                 return ((t != first + 2) ? t : first);
3634         }
3635 
3636         t = parse_operator_name(first + 2, last, db);
3637         if (t == first + 2)
3638                 return (first);
3639 
3640         t1 = parse_template_args(t, last, db);
3641         if (t1 != t)
3642                 nfmt(db, "{1:L}{0}", "{1:R}");
3643         return (t1);
3644 }
3645 
3646 /*
3647  * <destructor-name> ::= <unresolved-type>  # e.g., ~T or ~decltype(f())
3648  *                   ::= <simple-id>              # e.g., ~A<2*N>
3649  */
3650 static const char *
3651 parse_destructor_name(const char *first, const char *last, cpp_db_t *db)
3652 {
3653         VERIFY3P(first, <=, last);
3654 
3655         if (first == last)
3656                 return (first);
3657 
3658         const char *t = parse_unresolved_type(first, last, db);
3659 
3660         if (t == first)
3661                 t = parse_simple_id(first, last, db);
3662 
3663         if (t == first)
3664                 return (first);
3665 
3666         nfmt(db, "~{0:L}", "{0:R}");
3667         return (t);
3668 }
3669 
3670 /*
3671  *  <ref-qualifier> ::= R                   # & ref-qualifier
3672  *  <ref-qualifier> ::= O                   # && ref-qualifier
3673  *
3674  * <function-type> ::= F [Y] <bare-function-type> [<ref-qualifier>] E
3675  */
3676 static const char *
3677 parse_function_type(const char *first, const char *last, cpp_db_t *db)
3678 {
3679         VERIFY3P(first, <=, last);
3680 
3681         if (last - first < 2)
3682                 return (first);
3683 
3684         VERIFY3U(first[0], ==, 'F');
3685 
3686         const char *t = first + 1;
3687 
3688         /* extern "C" */
3689         if (t[0] == 'Y')
3690                 t++;
3691 
3692         const char *t1 = parse_type(t, last, db);
3693         if (t1 == t)
3694                 return (first);
3695 
3696         size_t n = nlen(db);
3697         int ref_qual = 0;
3698 
3699         t = t1;
3700 
3701         while (t != last && t[0] != 'E') {
3702                 if (t[0] == 'v') {
3703                         t++;
3704                         continue;
3705                 }
3706 
3707                 if (t[0] == 'R' && t + 1 != last && t[1] == 'E') {
3708                         ref_qual = 1;
3709                         t++;
3710                         continue;
3711                 }
3712 
3713                 if (t[0] == 'O' && t + 1 != last && t[1] == 'E') {
3714                         ref_qual = 2;
3715                         t++;
3716                         continue;
3717                 }
3718 
3719 
3720                 t1 = parse_type(t, last, db);
3721                 if (t1 == t || t == last)
3722                         return (first);
3723 
3724                 t = t1;
3725         }
3726 
3727         if (t == last)
3728                 return (first);
3729 
3730         njoin(db, NAMT(db, n), ", ");
3731         nfmt(db, "({0})", NULL);
3732 
3733         switch (ref_qual) {
3734         case 1:
3735                 nfmt(db, "{0} &", NULL);
3736                 break;
3737         case 2:
3738                 nfmt(db, "{0} &&", NULL);
3739                 break;
3740         }
3741 
3742         nfmt(db, "{1:L} ", "{0}{1:R}");
3743 
3744         /* skip E */
3745         return (t + 1);
3746 }
3747 
3748 /*
3749  * <template-param> ::= T_    # first template parameter
3750  *                  ::= T <parameter-2 non-negative number> _
3751  */
3752 static const char *
3753 parse_template_param(const char *first, const char *last, cpp_db_t *db)
3754 {
3755         VERIFY3P(first, <=, last);
3756 
3757         if (last - first < 2 || first[0] != 'T')
3758                 return (first);
3759 
3760         const char *t = first + 1;
3761         size_t idx = 0;
3762 
3763         while (t != last && t[0] != '_') {
3764                 if (!isdigit_l(t[0], db->cpp_loc))
3765                         return (first);
3766 
3767                 idx *= 10;
3768                 idx += t[0] - '0';
3769                 t++;
3770         }
3771 
3772         if (t == last)
3773                 return (first);
3774 
3775         VERIFY3U(t[0], ==, '_');
3776 
3777         /*
3778          * T_ -> idx 0
3779          * T0 -> idx 1
3780          * T1 -> idx 2
3781          * ...
3782          */
3783         if (first[1] != '_')
3784                 idx++;
3785 
3786         /* skip _ */
3787         t++;
3788 
3789         if (tempty(db))
3790                 return (first);
3791 
3792         if (idx >= ttlen(db)) {
3793                 nadd_l(db, first, (size_t)(t - first));
3794                 db->cpp_fix_forward_references = B_TRUE;
3795                 return (t);
3796         }
3797 
3798         tsub(db, idx);
3799         return (t);
3800 }
3801 
3802 /*
3803  * <template-args> ::= I <template-arg>* E
3804  *     extension, the abi says <template-arg>+
3805  */
3806 static const char *
3807 parse_template_args(const char *first, const char *last, cpp_db_t *db)
3808 {
3809         VERIFY3P(first, <=, last);
3810 
3811         if (last - first < 2 || first[0] != 'I')
3812                 return (first);
3813 
3814         if (db->cpp_tag_templates)
3815                 sub_clear(templ_top(&db->cpp_templ));
3816 
3817         const char *t = first + 1;
3818         size_t n = nlen(db);
3819 
3820         while (t[0] != 'E') {
3821                 if (db->cpp_tag_templates)
3822                         tpush(db);
3823 
3824                 size_t n1 = nlen(db);
3825                 const char *t1 = parse_template_arg(t, last, db);
3826 
3827                 if (db->cpp_tag_templates)
3828                         tpop(db);
3829 
3830                 if (t1 == t || t == last)
3831                         return (first);
3832 
3833                 if (db->cpp_tag_templates)
3834                         tsave(db, NAMT(db, n1));
3835 
3836                 t = t1;
3837         }
3838 
3839         /*
3840          * ugly, but if the last thing pushed was an empty string,
3841          * get rid of it so we dont get "<..., >"
3842          */
3843         if (NAMT(db, n) > 1 &&
3844             str_pair_len(name_top(&db->cpp_name)) == 0)
3845                 name_pop(&db->cpp_name, NULL);
3846 
3847         njoin(db, NAMT(db, n), ", ");
3848 
3849         VERIFY3U(nlen(db), >, 0);
3850 
3851         /* make sure we don't bitshift ourselves into oblivion */
3852         str_t *top = TOP_L(db);
3853         if (str_length(top) > 0 &&
3854             top->str_s[top->str_len - 1] == '>')
3855                 nfmt(db, "<{0} >", NULL);
3856         else
3857                 nfmt(db, "<{0}>", NULL);
3858 
3859         /* skip E */
3860         return (t + 1);
3861 }
3862 
3863 /*
3864  * <discriminator> := _ <non-negative number>      # when number < 10
3865  *                 := __ <non-negative number> _   # when number >= 10
3866  *  extension      := decimal-digit+               # at the end of string
3867  */
3868 static const char *
3869 parse_discriminator(const char *first, const char *last, locale_t loc)
3870 {
3871         VERIFY3P(first, <=, last);
3872 
3873         const char *t = NULL;
3874 
3875         if (first == last)
3876                 return (first);
3877 
3878         if (isdigit_l(first[0], loc)) {
3879                 for (t = first; t != last && isdigit_l(t[0], loc); t++)
3880                         ;
3881 
3882                 /* not at the end of the string */
3883                 if (t != last)
3884                         return (first);
3885 
3886                 return (t);
3887         } else if (first[0] != '_' || first + 1 == last) {
3888                 return (first);
3889         }
3890 
3891         t = first + 1;
3892         if (isdigit_l(t[0], loc))
3893                 return (t + 1);
3894 
3895         if (t[0] != '_' || t + 1 == last)
3896                 return (first);
3897 
3898         for (t++; t != last && isdigit_l(t[0], loc); t++)
3899                 ;
3900         if (t == last || t[0] != '_')
3901                 return (first);
3902 
3903         return (t);
3904 }
3905 
3906 /* <CV-qualifiers> ::= [r] [V] [K] */
3907 const char *
3908 parse_cv_qualifiers(const char *first, const char *last, unsigned *cv)
3909 {
3910         VERIFY3P(first, <=, last);
3911 
3912         if (first == last)
3913                 return (first);
3914 
3915         *cv = 0;
3916         if (first[0] == 'r') {
3917                 *cv |= CPP_QUAL_RESTRICT;
3918                 first++;
3919         }
3920         if (first != last && first[0] == 'V') {
3921                 *cv |= CPP_QUAL_VOLATILE;
3922                 first++;
3923         }
3924         if (first != last && first[0] == 'K') {
3925                 *cv |= CPP_QUAL_CONST;
3926                 first++;
3927         }
3928 
3929         return (first);
3930 }
3931 
3932 /*
3933  * <number> ::= [n] <non-negative decimal integer>
3934  */
3935 static const char *
3936 parse_number(const char *first, const char *last, locale_t loc)
3937 {
3938         VERIFY3P(first, <=, last);
3939 
3940         const char *t = first;
3941 
3942         if (first == last || (first[0] != 'n' && !isdigit_l(first[0], loc)))
3943                 return (first);
3944 
3945         if (t[0] == 'n')
3946                 t++;
3947 
3948         if (t[0] == '0')
3949                 return (t + 1);
3950 
3951         while (isdigit_l(t[0], loc))
3952                 t++;
3953 
3954         return (t);
3955 }
3956 
3957 /*
3958  * Like isxdigit(3C), except we can only accept lower case letters as
3959  * that's only what is allowed when [de]mangling floating point constants into
3960  * their hex representation.
3961  */
3962 static inline boolean_t
3963 is_xdigit(int c)
3964 {
3965         if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'f'))
3966                 return (B_TRUE);
3967         return (B_FALSE);
3968 }
3969 
3970 static boolean_t
3971 nempty(cpp_db_t *db)
3972 {
3973         return (name_empty(&db->cpp_name));
3974 }
3975 
3976 static size_t
3977 nlen(cpp_db_t *db)
3978 {
3979         return (name_len(&db->cpp_name));
3980 }
3981 
3982 static void
3983 nadd_l(cpp_db_t *db, const char *s, size_t len)
3984 {
3985         CK(name_add(&db->cpp_name, s, len, NULL, 0));
3986 }
3987 
3988 static void
3989 njoin(cpp_db_t *db, size_t amt, const char *sep)
3990 {
3991         name_t *nm = &db->cpp_name;
3992 
3993         CK(name_join(nm, amt, sep));
3994 }
3995 
3996 static void
3997 nfmt(cpp_db_t *db, const char *fmt_l, const char *fmt_r)
3998 {
3999         CK(name_fmt(&db->cpp_name, fmt_l, fmt_r));
4000 }
4001 
4002 static void
4003 save_top(cpp_db_t *db, size_t amt)
4004 {
4005         CK(sub_save(&db->cpp_subs, &db->cpp_name, amt));
4006 }
4007 
4008 static void
4009 sub(cpp_db_t *db, size_t n)
4010 {
4011         CK(sub_substitute(&db->cpp_subs, n, &db->cpp_name));
4012 }
4013 
4014 static boolean_t
4015 tempty(const cpp_db_t *db)
4016 {
4017         return (templ_empty(&db->cpp_templ) ? B_TRUE : B_FALSE);
4018 }
4019 
4020 static size_t
4021 ttlen(const cpp_db_t *db)
4022 {
4023         return (templ_top_len(&db->cpp_templ));
4024 }
4025 
4026 static void
4027 tsub(cpp_db_t *db, size_t n)
4028 {
4029         CK(templ_sub(&db->cpp_templ, n, &db->cpp_name));
4030 }
4031 
4032 static void
4033 tpush(cpp_db_t *db)
4034 {
4035         CK(templ_push(&db->cpp_templ));
4036 }
4037 
4038 static void
4039 tpop(cpp_db_t *db)
4040 {
4041         templ_pop(&db->cpp_templ);
4042 }
4043 
4044 static void
4045 tsave(cpp_db_t *db, size_t amt)
4046 {
4047         CK(templ_save(&db->cpp_name, amt, &db->cpp_templ));
4048 }
4049 
4050 static boolean_t
4051 db_init(cpp_db_t *db, sysdem_ops_t *ops)
4052 {
4053         (void) memset(db, 0, sizeof (*db));
4054         db->cpp_ops = ops;
4055         name_init(&db->cpp_name, ops);
4056         sub_init(&db->cpp_subs, ops);
4057         templ_init(&db->cpp_templ, ops);
4058         db->cpp_tag_templates = B_TRUE;
4059         db->cpp_try_to_parse_template_args = B_TRUE;
4060         tpush(db);
4061         db->cpp_loc = newlocale(LC_CTYPE_MASK, "C", 0);
4062         return ((db->cpp_loc != NULL) ? B_TRUE : B_FALSE);
4063 }
4064 
4065 static void
4066 db_fini(cpp_db_t *db)
4067 {
4068         name_fini(&db->cpp_name);
4069         sub_fini(&db->cpp_subs);
4070         templ_fini(&db->cpp_templ);
4071         freelocale(db->cpp_loc);
4072         (void) memset(db, 0, sizeof (*db));
4073 }
4074 
4075 static void
4076 print_sp(const str_pair_t *sp, FILE *out)
4077 {
4078         (void) fprintf(out, "{%.*s#%.*s}",
4079             (int)sp->strp_l.str_len, sp->strp_l.str_s,
4080             (int)sp->strp_r.str_len, sp->strp_r.str_s);
4081 }
4082 
4083 static void
4084 print_name(const name_t *n, FILE *out)
4085 {
4086         const str_pair_t *sp = name_top((name_t *)n);
4087         size_t i;
4088 
4089         (void) fprintf(out, "Name:\n");
4090 
4091         if (name_len(n) == 0)
4092                 return;
4093 
4094         for (i = 0; i < n->nm_len; i++, sp--) {
4095                 (void) fprintf(out, "  [%02zu] ", i);
4096                 print_sp(sp, out);
4097                 (void) fputc('\n', out);
4098         }
4099 
4100         (void) fputc('\n', out);
4101 }
4102 
4103 /* Print a base-36 number (for substitutions) */
4104 static char *
4105 base36(char *buf, size_t val)
4106 {
4107         char tmp[16] = { 0 };
4108         char *p = tmp;
4109 
4110         if (val == 0) {
4111                 buf[0] = '0';
4112                 buf[1] = '\0';
4113                 return (buf);
4114         }
4115 
4116         while (val > 0) {
4117                 size_t r = val % 36;
4118 
4119                 if (r < 10)
4120                         *p++ = r + '0';
4121                 else
4122                         *p++ = r - 10 + 'A';
4123 
4124                 val /= 36;
4125         }
4126 
4127         char *q = buf;
4128         while (--p >= tmp)
4129                 *q++ = *p;
4130 
4131         return (buf);
4132 }
4133 
4134 static void
4135 print_sub(const sub_t *sub, FILE *out)
4136 {
4137         const name_t *n = sub->sub_items;
4138 
4139         (void) fprintf(out, "Substitutions:\n");
4140 
4141         if (sub->sub_len == 0)
4142                 return;
4143 
4144         for (size_t i = 0; i < sub->sub_len; i++, n++) {
4145                 (void) printf("  ");
4146                 if (i == 0) {
4147                         (void) fprintf(out, "%-4s", "S_");
4148                 } else {
4149                         char buf[16] = { 0 };
4150                         char buf2[16] = { 0 };
4151 
4152                         (void) snprintf(buf, sizeof (buf), "S%s_",
4153                             base36(buf2, i));
4154                         (void) fprintf(out, "%-4s", buf);
4155                 }
4156                 (void) fprintf(out, " = ");
4157 
4158                 (void) fputc('{', out);
4159                 for (size_t j = 0; j < n->nm_len; j++) {
4160                         if (j > 0)
4161                                 (void) fputc(' ', out);
4162                         print_sp(&n->nm_items[j], out);
4163                 }
4164                 (void) fputc('}', out);
4165 
4166                 (void) fputc('\n', out);
4167         }
4168         (void) fputc('\n', out);
4169 }
4170 
4171 static void
4172 print_templ(const templ_t *tpl, FILE *out)
4173 {
4174 
4175         (void) fprintf(out, "Template\n");
4176 
4177         const sub_t *s = templ_top((templ_t *)tpl);
4178 
4179         for (size_t i = 0; i < s->sub_len; i++) {
4180                 char buf[16] = { 0 };
4181 
4182                 if (i == 0)
4183                         (void) snprintf(buf, sizeof (buf), "%s", "T_");
4184                 else
4185                         (void) snprintf(buf, sizeof (buf), "T%zu_", i - 1);
4186 
4187                 (void) fprintf(out, "  %-4s = ", buf);
4188 
4189                 (void) fputc('{', out);
4190 
4191                 const name_t *n = &s->sub_items[i];
4192                 for (size_t j = 0; j < n->nm_len; j++) {
4193                         const str_pair_t *sp = &n->nm_items[j];
4194 
4195                         if (j > 0)
4196                                 (void) fputc(' ', out);
4197 
4198                         (void) fprintf(out, "{%.*s#%.*s}",
4199                             (int)sp->strp_l.str_len, sp->strp_l.str_s,
4200                             (int)sp->strp_r.str_len, sp->strp_r.str_s);
4201                 }
4202                 (void) fprintf(out, "}\n");
4203         }
4204         (void) fprintf(out, "\n");
4205 }
4206 
4207 static void
4208 dump(cpp_db_t *db, FILE *out)
4209 {
4210         print_name(&db->cpp_name, out);
4211         print_sub(&db->cpp_subs, out);
4212         print_templ(&db->cpp_templ, out);
4213 }