/*
 * Ported from LLVM's libcxxabi trunk/src/cxa_demangle.cpp
 * LICENSE.TXT contents is available as ../THIRDPARTYLICENSE
 *
 *                     The LLVM Compiler Infrastructure
 *
 * This file is dual licensed under the MIT and the University of Illinois Open
 * Source Licenses. See LICENSE.TXT for details.
 *
 */

/*
 * Copyright 2021 Jason King.
 */
#include <errno.h>
#include <note.h>
#include <string.h>
#include <setjmp.h>
#include <stdio.h>
#include <stdlib.h>
#include "demangle-sys.h"
#include "demangle_int.h"
#include "cxx.h"

#define CPP_QUAL_CONST          (1U)
#define CPP_QUAL_VOLATILE       (2U)
#define CPP_QUAL_RESTRICT       (4U)

typedef struct cpp_db_s {
        sysdem_ops_t    *cpp_ops;
        jmp_buf         cpp_jmp;
        name_t          cpp_name;
        sub_t           cpp_subs;
        templ_t         cpp_templ;
        unsigned        cpp_cv;
        unsigned        cpp_ref;
        unsigned        cpp_depth;
        boolean_t       cpp_parsed_ctor_dtor_cv;
        boolean_t       cpp_tag_templates;
        boolean_t       cpp_fix_forward_references;
        boolean_t       cpp_try_to_parse_template_args;
} cpp_db_t;

#define CK(x)                                           \
        do {                                            \
                if (!(x)) {                             \
                        longjmp(db->cpp_jmp, 1);        \
                }                                       \
        NOTE(CONSTCOND)                                 \
        } while (0)

#define TOP_L(db) (&(name_top(&(db)->cpp_name)->strp_l))
#define RLEN(f, l) ((size_t)((l) - (f)))
#define NAMT(db, n) (nlen(db) - n)

static inline boolean_t is_xdigit(int);

static boolean_t nempty(cpp_db_t *);
static size_t nlen(cpp_db_t *);
static void nadd_l(cpp_db_t *, const char *, size_t);
static void njoin(cpp_db_t *, size_t, const char *);
static void nfmt(cpp_db_t *, const char *, const char *);

static void save_top(cpp_db_t *, size_t);
static void sub(cpp_db_t *, size_t);

static boolean_t tempty(const cpp_db_t *);
static size_t ttlen(const cpp_db_t *);

static void tsub(cpp_db_t *, size_t);
static void tpush(cpp_db_t *);
static void tpop(cpp_db_t *);
static void tsave(cpp_db_t *, size_t);

static void db_init(cpp_db_t *, sysdem_ops_t *);
static void db_fini(cpp_db_t *);
static void dump(cpp_db_t *, FILE *);

static void demangle(const char *, const char *, cpp_db_t *);

static const char *parse_type(const char *, const char *, cpp_db_t *);
static const char *parse_builtin_type(const char *, const char *, cpp_db_t *);
static const char *parse_qual_type(const char *, const char *, cpp_db_t *);
static const char *parse_encoding(const char *, const char *, cpp_db_t *);
static const char *parse_dot_suffix(const char *, const char *, cpp_db_t *);
static const char *parse_block_invoke(const char *, const char *, cpp_db_t *);
static const char *parse_special_name(const char *, const char *, cpp_db_t *);
static const char *parse_name(const char *, const char *, boolean_t *,
    cpp_db_t *);
static const char *parse_call_offset(const char *, const char *);
static const char *parse_number(const char *, const char *);
static const char *parse_nested_name(const char *, const char *, boolean_t *,
    cpp_db_t *);
static const char *parse_local_name(const char *, const char *, boolean_t *,
    cpp_db_t *);
static const char *parse_unscoped_name(const char *, const char *, cpp_db_t *);
static const char *parse_template_args(const char *, const char *, cpp_db_t *);
static const char *parse_substitution(const char *, const char *, cpp_db_t *);
static const char *parse_discriminator(const char *, const char *);
static const char *parse_cv_qualifiers(const char *, const char *, unsigned *);
static const char *parse_template_param(const char *, const char *, cpp_db_t *);
static const char *parse_decltype(const char *, const char *, cpp_db_t *);
static const char *parse_template_args(const char *, const char *, cpp_db_t *);
static const char *parse_unqualified_name(const char *, const char *,
    cpp_db_t *);
static const char *parse_template_arg(const char *, const char *, cpp_db_t *);
static const char *parse_expression(const char *, const char *, cpp_db_t *);
static const char *parse_expr_primary(const char *, const char *, cpp_db_t *);
static const char *parse_binary_expr(const char *, const char *,
    const char *, cpp_db_t *);
static const char *parse_prefix_expr(const char *, const char *,
    const char *, cpp_db_t *);
static const char *parse_gs(const char *, const char *, cpp_db_t *);
static const char *parse_idx_expr(const char *, const char *, cpp_db_t *);
static const char *parse_mm_expr(const char *, const char *, cpp_db_t *);
static const char *parse_pp_expr(const char *, const char *, cpp_db_t *);
static const char *parse_trinary_expr(const char *, const char *, cpp_db_t *);
static const char *parse_new_expr(const char *, const char *, cpp_db_t *);
static const char *parse_del_expr(const char *, const char *, cpp_db_t *);
static const char *parse_cast_expr(const char *, const char *, cpp_db_t *);
static const char *parse_sizeof_param_pack_expr(const char *, const char *,
    cpp_db_t *);
static const char *parse_typeid_expr(const char *, const char *, cpp_db_t *);
static const char *parse_throw_expr(const char *, const char *, cpp_db_t *);
static const char *parse_dot_star_expr(const char *, const char *, cpp_db_t *);
static const char *parse_dot_expr(const char *, const char *, cpp_db_t *);
static const char *parse_call_expr(const char *, const char *, cpp_db_t *);
static const char *parse_arrow_expr(const char *, const char *, cpp_db_t *);
static const char *parse_conv_expr(const char *, const char *, cpp_db_t *);
static const char *parse_function_param(const char *, const char *, cpp_db_t *);
static const char *parse_base_unresolved_name(const char *, const char *,
    cpp_db_t *);
static const char *parse_unresolved_name(const char *, const char *,
    cpp_db_t *);
static const char *parse_noexcept_expr(const char *, const char *, cpp_db_t *);
static const char *parse_alignof(const char *, const char *, cpp_db_t *);
static const char *parse_sizeof(const char *, const char *, cpp_db_t *);
static const char *parse_unnamed_type_name(const char *, const char *,
    cpp_db_t *);
static const char *parse_ctor_dtor_name(const char *, const char *, cpp_db_t *);
static const char *parse_source_name(const char *, const char *, cpp_db_t *);
static const char *parse_operator_name(const char *, const char *, cpp_db_t *);
static const char *parse_pack_expansion(const char *, const char *, cpp_db_t *);
static const char *parse_unresolved_type(const char *, const char *,
    cpp_db_t *);
static const char *parse_unresolved_qualifier_level(const char *, const char *,
    cpp_db_t *);
static const char *parse_destructor_name(const char *, const char *,
    cpp_db_t *);
static const char *parse_function_type(const char *, const char *, cpp_db_t *);
static const char *parse_array_type(const char *, const char *, cpp_db_t *);
static const char *parse_pointer_to_member_type(const char *, const char *,
    cpp_db_t *);
static const char *parse_vector_type(const char *, const char *, cpp_db_t *);

size_t cpp_name_max_depth = 1024;       /* max depth of name stack */

char *
cpp_demangle(const char *src, size_t srclen, sysdem_ops_t *ops)
{
        char *volatile result = NULL;
        cpp_db_t db;

        db_init(&db, ops);

        if (setjmp(db.cpp_jmp) != 0)
                goto done;

        errno = 0;
        demangle(src, src + srclen, &db);

        if (errno == 0 && db.cpp_fix_forward_references &&
            !templ_empty(&db.cpp_templ) &&
            !sub_empty(&db.cpp_templ.tpl_items[0])) {
                db.cpp_fix_forward_references = B_FALSE;
                db.cpp_tag_templates = B_FALSE;
                name_clear(&db.cpp_name);
                sub_clear(&db.cpp_subs);

                if (setjmp(db.cpp_jmp) != 0)
                        goto done;

                demangle(src, src + srclen, &db);

                if (db.cpp_fix_forward_references) {
                        errno = EINVAL;
                        goto done;
                }
        }

        if (errno != 0)
                goto done;

        if (nempty(&db)) {
                errno = EINVAL;
                goto done;
        }

        njoin(&db, 1, "");

        if (nlen(&db) > 0) {
                str_t *s = TOP_L(&db);
                char *res = zalloc(ops, s->str_len + 1);
                if (res == NULL)
                        goto done;

                (void) memcpy(res, s->str_s, s->str_len);
                result = res;
        }

done:
        if (demangle_debug)
                dump(&db, stdout);

        db_fini(&db);
        return (result);
}

static void
demangle(const char *first, const char *last, cpp_db_t *db)
{
        const char *t = NULL;

        if (first >= last) {
                errno = EINVAL;
                return;
        }

        if (first[0] != '_') {
                t = parse_type(first, last, db);
                if (t == first) {
                        errno = EINVAL;
                        return;
                }
                goto done;
        }

        if (last - first < 4) {
                errno = EINVAL;
                return;
        }

        if (first[1] == 'Z') {
                t = parse_encoding(first + 2, last, db);

                if (t != first + 2 && t != last && t[0] == '.') {
                        t = parse_dot_suffix(t, last, db);
                        if (nlen(db) > 1)
                                njoin(db, 2, "");
                }

                goto done;
        }

        if (first[1] != '_' || first[2] != '_' || first[3] != 'Z')
                goto done;

        t = parse_encoding(first + 4, last, db);
        if (t != first + 4 && t != last)
                t = parse_block_invoke(t, last, db);

done:
        if (t != last)
                errno = EINVAL;
}

static const char *
parse_dot_suffix(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (first == last || first[0] != '.')
                return (first);

        if (nempty(db))
                return (first);

        nadd_l(db, first, RLEN(first, last));
        nfmt(db, " ({0})", NULL);

        return (last);
}

/*
 * _block_invoke
 * _block_invoke<digit>*
 * _block_invoke_<digit>+
 */
static const char *
parse_block_invoke(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 13)
                return (first);

        const char test[] = "_block_invoke";
        const char *t = first;

        if (strncmp(first, test, sizeof (test) - 1) != 0)
                return (first);

        t += sizeof (test);
        if (t == last)
                goto done;

        if (t[0] == '_') {
                /* need at least one digit */
                if (t + 1 == last || ISDIGIT(t[1]))
                        return (first);
                t += 2;
        }

        while (t < last && ISDIGIT(t[0]))
                t++;

done:
        if (nempty(db))
                return (first);

        nfmt(db, "invocation function for block in {0}", NULL);
        return (t);
}

/*
 * <encoding> ::= <function name><bare-function-type>
 *            ::= <data name>
 *            ::= <special name>
 */
static const char *
parse_encoding(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (first == last)
                return (first);

        const char *t = NULL;
        const char *t2 = NULL;
        unsigned cv = 0;
        unsigned ref = 0;
        boolean_t tag_templ_save = db->cpp_tag_templates;

        if (++db->cpp_depth > 1)
                db->cpp_tag_templates = B_TRUE;

        if (first[0] == 'G' || first[0] == 'T') {
                t = parse_special_name(first, last, db);
                goto done;
        }

        boolean_t ends_with_template_args = B_FALSE;
        t = parse_name(first, last, &ends_with_template_args, db);
        if (t == first)
                goto fail;

        cv = db->cpp_cv;
        ref = db->cpp_ref;

        if (t == last || t[0] == 'E' || t[0] == '.')
                goto done;

        db->cpp_tag_templates = B_FALSE;
        if (nempty(db) || str_length(TOP_L(db)) == 0)
                goto fail;

        if (!db->cpp_parsed_ctor_dtor_cv && ends_with_template_args) {
                t2 = parse_type(t, last, db);
                if (t2 == t || nlen(db) < 2)
                        goto fail;

                str_pair_t *sp = name_top(&db->cpp_name);

                if (str_length(&sp->strp_r) == 0)
                        (void) str_append(&sp->strp_l, " ", 1);

                nfmt(db, "{0:L}{1:L}", "{1:R}{0:R}");
                t = t2;
        }

        if (t == last || nempty(db))
                goto fail;

        size_t n = nlen(db);

        if (t[0] == 'v') {
                t++;
        } else {
                for (;;) {
                        t2 = parse_type(t, last, db);
                        if (t2 == t || t == last)
                                break;

                        t = t2;
                }
        }

        /*
         * a bit of a hack, but a template substitution can apparently be
         * an empty string at the end of an argument list, so avoid
         * <...., >
         */
        if (NAMT(db, n) > 1 && str_pair_len(name_top(&db->cpp_name)) == 0)
                name_pop(&db->cpp_name, NULL);

        njoin(db, NAMT(db, n), ", ");
        nfmt(db, "({0})", NULL);

        str_t *s = TOP_L(db);

        if (cv & CPP_QUAL_CONST) {
                CK(str_append(s, " const", 0));
        }
        if (cv & CPP_QUAL_VOLATILE) {
                CK(str_append(s, " volatile", 0));
        }
        if (cv & CPP_QUAL_RESTRICT) {
                CK(str_append(s, " restrict", 0));
        }
        if (ref == 1) {
                CK(str_append(s, " &", 0));
        }
        if (ref == 2) {
                CK(str_append(s, " &&", 0));
        }

        nfmt(db, "{1:L}{0}{1:R}", NULL);

done:
        db->cpp_tag_templates = tag_templ_save;
        db->cpp_depth--;
        return (t);

fail:
        db->cpp_tag_templates = tag_templ_save;
        db->cpp_depth--;
        return (first);
}

/*
 * <special-name> ::= TV <type>    # virtual table
 *                ::= TT <type>    # VTT structure (construction vtable index)
 *                ::= TI <type>    # typeinfo structure
 *                ::= TS <type>    # typeinfo name (null-terminated byte string)
 *                ::= Tc <call-offset> <call-offset> <base encoding>
 *                    # base is the nominal target function of thunk
 *                    # first call-offset is 'this' adjustment
 *                    # second call-offset is result adjustment
 *                ::= T <call-offset> <base encoding>
 *                    # base is the nominal target function of thunk
 *                ::= GV <object name> # Guard variable for one-time init
 *                                     # No <type>
 *                ::= TW <object name> # Thread-local wrapper
 *                ::= TH <object name> # Thread-local initialization
 *      extension ::= TC <first type> <number> _ <second type>
 *                                     # construction vtable for second-in-first
 *      extension ::= GR <object name> # reference temporary for object
 */
static const char *
parse_special_name(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        const char *t = first;
        const char *t1 = NULL;
        size_t n = nlen(db);

        if (last - first < 2)
                return (first);

        switch (t[0]) {
        case 'T':
                switch (t[1]) {
                case 'V':
                        nadd_l(db, "vtable for", 0);
                        t = parse_type(first + 2, last, db);
                        break;
                case 'T':
                        nadd_l(db, "VTT for", 0);
                        t = parse_type(first + 2, last, db);
                        break;
                case 'I':
                        nadd_l(db, "typeinfo for", 0);
                        t = parse_type(first + 2, last, db);
                        break;
                case 'S':
                        nadd_l(db, "typeinfo name for", 0);
                        t = parse_type(first + 2, last, db);
                        break;
                case 'c':
                        nadd_l(db, "covariant return thunk to", 0);
                        t1 = parse_call_offset(first + 2, last);
                        if (t1 == t)
                                return (first);
                        t = parse_call_offset(t1, last);
                        if (t == t1)
                                return (first);
                        t1 = parse_encoding(t, last, db);
                        if (t1 == t)
                                return (first);
                        break;
                case 'C':
                        t = parse_type(first + 2, last, db);
                        if (t == first + 2)
                                return (first);
                        t1 = parse_number(t, last);
                        if (*t1 != '_')
                                return (first);
                        t = parse_type(t1 + 1, last, db);
                        if (t == t1 + 1 || nlen(db) < 2)
                                return (first);
                        nfmt(db, "construction vtable for {0}-in-{1}", NULL);
                        return (t);
                case 'W':
                        nadd_l(db, "thread-local wrapper routine for", 0);
                        t = parse_name(first + 2, last, NULL, db);
                        break;
                case 'H':
                        nadd_l(db, "thread-local initialization routine for",
                            0);
                        t = parse_name(first + 2, last, NULL, db);
                        break;
                default:
                        if (first[1] == 'v') {
                                nadd_l(db, "virtual thunk to", 0);
                        } else {
                                nadd_l(db, "non-virtual thunk to", 0);
                        }

                        t = parse_call_offset(first + 1, last);
                        if (t == first + 1)
                                return (first);
                        t1 = parse_encoding(t, last, db);
                        if (t == t1)
                                return (first);
                        t = t1;
                        break;
                }
                break;
        case 'G':
                switch (first[1]) {
                case 'V':
                        nadd_l(db, "guard variable for", 0);
                        t = parse_name(first + 2, last, NULL, db);
                        break;
                case 'R':
                        nadd_l(db, "reference temporary for", 0);
                        t = parse_name(first + 2, last, NULL, db);
                        break;
                default:
                        return (first);
                }
                break;
        default:
                return (first);
        }

        size_t amt = NAMT(db, n);
        if (t == first + 2 || amt < 2)
                return (first);

        njoin(db, amt, " ");
        return (t);
}

/*
 * <call-offset> ::= h <nv-offset> _
 *               ::= v <v-offset> _
 *
 * <nv-offset> ::= <offset number>
 *               # non-virtual base override
 *
 * <v-offset>  ::= <offset number> _ <virtual offset number>
 *               # virtual base override, with vcall offset
 */
static const char *
parse_call_offset(const char *first, const char *last)
{
        VERIFY3P(first, <=, last);

        const char *t = NULL;
        const char *t1 = NULL;

        if (first == last)
                return (first);

        if (first[0] != 'h' && first[0] != 'v')
                return (first);

        t = parse_number(first + 1, last);
        if (t == first + 1 || t == last || t[0] != '_')
                return (first);

        /* skip _ */
        t++;

        if (first[0] == 'h')
                return (t);

        t1 = parse_number(t, last);
        if (t == t1 || t1 == last || t1[0] != '_')
                return (first);

        /* skip _ */
        t1++;

        return (t1);
}

/*
 * <name> ::= <nested-name> // N
 *        ::= <local-name> # See Scope Encoding below  // Z
 *        ::= <unscoped-template-name> <template-args>
 *        ::= <unscoped-name>
 *
 * <unscoped-template-name> ::= <unscoped-name>
 *                          ::= <substitution>
 */
static const char *
parse_name(const char *first, const char *last,
    boolean_t *ends_with_template_args, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        const char *t = first;
        const char *t1 = NULL;

        if (last - first < 2)
                return (first);

        /* extension: ignore L here */
        if (t[0] == 'L')
                t++;

        switch (t[0]) {
        case 'N':
                t1 = parse_nested_name(t, last, ends_with_template_args, db);
                return ((t == t1) ? first : t1);
        case 'Z':
                t1 = parse_local_name(t, last, ends_with_template_args, db);
                return ((t == t1) ? first : t1);
        }

        /*
         * <unscoped-name>
         * <unscoped-name> <template-args>
         * <substitution> <template-args>
         */
        t1 = parse_unscoped_name(t, last, db);

        /* <unscoped-name> */
        if (t != t1 && t1[0] != 'I')
                return (t1);

        if (t == t1) {
                t1 = parse_substitution(t, last, db);
                if (t == t1 || t1 == last || t1[0] != 'I')
                        return (first);
        } else {
                save_top(db, 1);
        }

        t = parse_template_args(t1, last, db);
        if (t1 == t || nlen(db) < 2)
                return (first);

        nfmt(db, "{1:L}{0}", "{1:R}");

        if (ends_with_template_args != NULL)
                *ends_with_template_args = B_TRUE;

        return (t);
}

/* BEGIN CSTYLED */
/*
 * <local-name> := Z <function encoding> E <entity name> [<discriminator>]
 *              := Z <function encoding> E s [<discriminator>]
 *              := Z <function encoding> Ed [ <parameter number> ] _ <entity name>
 */
/* END CSTYLED */
const char *
parse_local_name(const char *first, const char *last,
    boolean_t *ends_with_template_args, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        const char *t = NULL;
        const char *t1 = NULL;
        const char *t2 = NULL;

        if (first == last || first[0] != 'Z')
                return (first);

        t = parse_encoding(first + 1, last, db);
        if (t == first + 1 || t == last || t[0] != 'E')
                return (first);

        VERIFY(!nempty(db));

        /* skip E */
        t++;

        if (t[0] == 's') {
                nfmt(db, "{0:L}::string literal", "{0:R}");
                return (parse_discriminator(t, last));
        }

        if (t[0] == 'd') {
                t1 = parse_number(t + 1, last);
                if (t1[0] != '_')
                        return (first);
                t1++;
        } else {
                t1 = t;
        }

        t2 = parse_name(t1, last, ends_with_template_args, db);
        if (t2 == t1)
                return (first);

        nfmt(db, "{1:L}::{0}", "{1:R}");

        /* parsed, but ignored */
        if (t[0] != 'd')
                t2 = parse_discriminator(t2, last);

        return (t2);
}

/* BEGIN CSTYLED */
/*
 * <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E
 *               ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix> <template-args> E
 *
 * <prefix> ::= <prefix> <unqualified-name>
 *          ::= <template-prefix> <template-args>
 *          ::= <template-param>
 *          ::= <decltype>
 *          ::= # empty
 *          ::= <substitution>
 *          ::= <prefix> <data-member-prefix>
 *  extension ::= L
 *
 * <template-prefix> ::= <prefix> <template unqualified-name>
 *                   ::= <template-param>
 *                   ::= <substitution>
 */
/* END CSTYLED */
static const char *
parse_nested_name(const char *first, const char *last,
    boolean_t *ends_with_template_args, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (first == last || first[0] != 'N')
                return (first);

        unsigned cv = 0;
        const char *t = parse_cv_qualifiers(first + 1, last, &cv);

        if (t == last)
                return (first);

        boolean_t more = B_FALSE;

        switch (t[0]) {
        case 'R':
                db->cpp_ref = 1;
                t++;
                break;
        case 'O':
                db->cpp_ref = 2;
                t++;
                break;
        case 'S':
                if (last - first < 2 || t[1] != 't')
                        break;
                if (last - first == 2)
                        return (first);
                nadd_l(db, "std", 3);
                more = B_TRUE;
                t += 2;
                break;
        }

        boolean_t pop_subs = B_FALSE;
        boolean_t component_ends_with_template_args = B_FALSE;

        while (t[0] != 'E' && t != last) {
                const char *t1 = NULL;
                size_t n = nlen(db);
                component_ends_with_template_args = B_FALSE;

                switch (t[0]) {
                case 'S':
                        if (t + 1 != last && t[1] == 't')
                                break;

                        t1 = parse_substitution(t, last, db);
                        if (t1 == t || t1 == last || NAMT(db, n) != 1)
                                return (first);

                        if (!more) {
                                nfmt(db, "{0}", NULL);
                        } else {
                                VERIFY3U(nlen(db), >, 1);
                                nfmt(db, "{1:L}::{0}", "{1:R}");
                                save_top(db, 1);
                        }

                        more = B_TRUE;
                        pop_subs = B_TRUE;
                        t = t1;
                        continue;

                case 'T':
                        t1 = parse_template_param(t, last, db);
                        if (t1 == t || t1 == last || NAMT(db, n) != 1)
                                return (first);

                        if (!more) {
                                nfmt(db, "{0}", NULL);
                        } else {
                                VERIFY3U(nlen(db), >, 1);
                                nfmt(db, "{1:L}::{0}", "{1:R}");
                        }

                        save_top(db, 1);
                        more = B_TRUE;
                        pop_subs = B_TRUE;
                        t = t1;
                        continue;

                case 'D':
                        if (t + 1 != last && t[1] != 't' && t[1] != 'T')
                                break;
                        t1 = parse_decltype(t, last, db);
                        if (t1 == t || t1 == last || NAMT(db, n) != 1)
                                return (first);

                        if (!more) {
                                nfmt(db, "{0}", NULL);
                        } else {
                                VERIFY3U(nlen(db), >, 1);
                                nfmt(db, "{1:L}::{0}", "{1:R}");
                        }

                        save_top(db, 1);
                        more = B_TRUE;
                        pop_subs = B_TRUE;
                        t = t1;
                        continue;

                case 'I':
                        /*
                         * Must have at least one component before
                         * <template-args>
                         */
                        if (!more)
                                return (first);

                        t1 = parse_template_args(t, last, db);
                        if (t1 == t || t1 == last)
                                return (first);

                        VERIFY3U(nlen(db), >, 1);
                        nfmt(db, "{1:L}{0}", "{1:R}");
                        save_top(db, 1);
                        t = t1;
                        component_ends_with_template_args = B_TRUE;
                        continue;

                case 'L':
                        if (t + 1 == last)
                                return (first);
                        t++;
                        continue;

                default:
                        break;
                }

                t1 = parse_unqualified_name(t, last, db);
                if (t1 == t || t1 == last || NAMT(db, n) != 1)
                        return (first);

                if (!more) {
                        nfmt(db, "{0}", NULL);
                } else {
                        VERIFY3U(nlen(db), >, 1);
                        nfmt(db, "{1:L}::{0}", "{1:R}");
                }

                save_top(db, 1);
                more = B_TRUE;
                pop_subs = B_TRUE;
                t = t1;
        }

        /* need to parse at least one thing */
        if (!more)
                return (first);

        db->cpp_cv = cv;
        if (pop_subs && !sub_empty(&db->cpp_subs))
                sub_pop(&db->cpp_subs);

        if (ends_with_template_args != NULL)
                *ends_with_template_args = component_ends_with_template_args;

        if (t[0] != 'E')
                return (first);

        return (t + 1);
}

/*
 * <template-arg> ::= <type>                   # type or template
 *                ::= X <expression> E         # expression
 *                ::= <expr-primary>           # simple expressions
 *                ::= J <template-arg>* E      # argument pack
 *                ::= LZ <encoding> E          # extension
 */
static const char *
parse_template_arg(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        const char *t = NULL;
        const char *t1 = NULL;

        if (first == last)
                return (first);

        switch (first[0]) {
        case 'X':
                t = parse_expression(first + 1, last, db);
                if (t == first + 1 || t[0] != 'E')
                        return (first);

                /* E */
                t++;
                break;

        case 'J':
                t = first + 1;
                if (t == last)
                        return (first);

                while (t[0] != 'E') {
                        t1 = parse_template_arg(t, last, db);
                        if (t == t1)
                                return (first);
                        t = t1;
                }

                /* E */
                t++;
                break;

        case 'L':
                if (first + 1 == last || first[1] != 'Z') {
                        t = parse_expr_primary(first, last, db);
                } else {
                        t = parse_encoding(first + 2, last, db);
                        if (t == first + 2 || t == last || t[0] != 'E')
                                return (first);

                        /* E */
                        t++;
                }
                break;

        default:
                t = parse_type(first, last, db);
        }

        return (t);
}

/* BEGIN CSTYLED */
/*
 * <expression> ::= <unary operator-name> <expression>
 *              ::= <binary operator-name> <expression> <expression>
 *              ::= <ternary operator-name> <expression> <expression> <expression>
 *              ::= cl <expression>+ E                                   # call
 *              ::= cv <type> <expression>                               # conversion with one argument
 *              ::= cv <type> _ <expression>* E                          # conversion with a different number of arguments
 *              ::= [gs] nw <expression>* _ <type> E                     # new (expr-list) type
 *              ::= [gs] nw <expression>* _ <type> <initializer>         # new (expr-list) type (init)
 *              ::= [gs] na <expression>* _ <type> E                     # new[] (expr-list) type
 *              ::= [gs] na <expression>* _ <type> <initializer>         # new[] (expr-list) type (init)
 *              ::= [gs] dl <expression>                                 # delete expression
 *              ::= [gs] da <expression>                                 # delete[] expression
 *              ::= pp_ <expression>                                     # prefix ++
 *              ::= mm_ <expression>                                     # prefix --
 *              ::= ti <type>                                            # typeid (type)
 *              ::= te <expression>                                      # typeid (expression)
 *              ::= dc <type> <expression>                               # dynamic_cast<type> (expression)
 *              ::= sc <type> <expression>                               # static_cast<type> (expression)
 *              ::= cc <type> <expression>                               # const_cast<type> (expression)
 *              ::= rc <type> <expression>                               # reinterpret_cast<type> (expression)
 *              ::= st <type>                                            # sizeof (a type)
 *              ::= sz <expression>                                      # sizeof (an expression)
 *              ::= at <type>                                            # alignof (a type)
 *              ::= az <expression>                                      # alignof (an expression)
 *              ::= nx <expression>                                      # noexcept (expression)
 *              ::= <template-param>
 *              ::= <function-param>
 *              ::= dt <expression> <unresolved-name>                    # expr.name
 *              ::= pt <expression> <unresolved-name>                    # expr->name
 *              ::= ds <expression> <expression>                         # expr.*expr
 *              ::= sZ <template-param>                                  # size of a parameter pack
 *              ::= sZ <function-param>                                  # size of a function parameter pack
 *              ::= sp <expression>                                      # pack expansion
 *              ::= tw <expression>                                      # throw expression
 *              ::= tr                                                   # throw with no operand (rethrow)
 *              ::= <unresolved-name>                                    # f(p), N::f(p), ::f(p),
 *                                                                       # freestanding dependent name (e.g., T::x),
 *                                                                       # objectless nonstatic member reference
 *              ::= <expr-primary>
 */
/* END CSTYLED */

#define PA(cd, arg, fn) {       \
        .code = cd,             \
        .p.parse_expr_arg = fn, \
        .fntype = EXPR_ARG,     \
        .val = arg              \
}

#define PN(cd, fn) {                    \
        .code = cd,                     \
        .p.parse_expr_noarg = fn,       \
        .fntype = EXPR_NOARG            \
}

static struct {
        const char code[3];
        union {
                const char *(*parse_expr_arg)(const char *, const char *,
                    const char *, cpp_db_t *);
                const char *(*parse_expr_noarg)(const char *, const char *,
                    cpp_db_t *);
        } p;
        enum {
                EXPR_ARG,
                EXPR_NOARG
        } fntype;
        const char val[4];
} expr_tbl[] = {
        PA("aN", "&=", parse_binary_expr),
        PA("aS", "=", parse_binary_expr),
        PA("aa", "&&", parse_binary_expr),
        PA("ad", "&", parse_prefix_expr),
        PA("an", "&", parse_binary_expr),
        PN("at", parse_alignof),
        PN("az", parse_alignof),
        PN("cc", parse_cast_expr),
        PN("cl", parse_call_expr),
        PA("cm", ",", parse_binary_expr),
        PA("co", "~", parse_prefix_expr),
        PN("cv", parse_conv_expr),
        PN("da", parse_del_expr),
        PA("dV", "/=", parse_binary_expr),
        PN("dc", parse_cast_expr),
        PA("de", "*", parse_prefix_expr),
        PN("dl", parse_del_expr),
        PN("dn", parse_unresolved_name),
        PN("ds", parse_dot_star_expr),
        PN("dt", parse_dot_expr),
        PA("dv", "/", parse_binary_expr),
        PA("eO", "^=", parse_binary_expr),
        PA("eo", "^", parse_binary_expr),
        PA("eq", "==", parse_binary_expr),
        PA("ge", ">=", parse_binary_expr),
        PN("gs", parse_gs),
        PA("gt", ">", parse_binary_expr),
        PN("ix", parse_idx_expr),
        PA("lS", "<<=", parse_binary_expr),
        PA("le", "<=", parse_binary_expr),
        PA("ls", "<<", parse_binary_expr),
        PA("lt", "<", parse_binary_expr),
        PA("mI", "-=", parse_binary_expr),
        PA("mL", "*=", parse_binary_expr),
        PN("mm", parse_mm_expr),
        PA("mi", "-", parse_binary_expr),
        PA("ml", "*", parse_binary_expr),
        PN("na", parse_new_expr),
        PA("ne", "!=", parse_binary_expr),
        PA("ng", "-", parse_prefix_expr),
        PA("nt", "!", parse_prefix_expr),
        PN("nw", parse_new_expr),
        PN("nx", parse_noexcept_expr),
        PA("oR", "|=", parse_binary_expr),
        PN("on", parse_unresolved_name),
        PA("oo", "||", parse_binary_expr),
        PA("or", "|", parse_binary_expr),
        PA("pL", "+=", parse_binary_expr),
        PA("pl", "+", parse_binary_expr),
        PA("pm", "->*", parse_binary_expr),
        PN("pp", parse_pp_expr),
        PA("ps", "+", parse_prefix_expr),
        PN("pt", parse_arrow_expr),
        PN("qu", parse_trinary_expr),
        PA("rM", "%=", parse_binary_expr),
        PA("rS", ">>=", parse_binary_expr),
        PN("rc", parse_cast_expr),
        PA("rm", "%", parse_binary_expr),
        PA("rs", ">>", parse_binary_expr),
        PN("sc", parse_cast_expr),
        PN("sp", parse_pack_expansion),
        PN("sr", parse_unresolved_name),
        PN("st", parse_sizeof),
        PN("sz", parse_sizeof),
        PN("sZ", parse_sizeof_param_pack_expr),
        PN("te", parse_typeid_expr),
        PN("tr", parse_throw_expr),
        PN("tw", parse_throw_expr)
};
#undef PA
#undef PN

static const char *
parse_expression(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2)
                return (first);

        for (size_t i = 0; i < ARRAY_SIZE(expr_tbl); i++) {
                if (strncmp(expr_tbl[i].code, first, 2) != 0)
                        continue;
                switch (expr_tbl[i].fntype) {
                case EXPR_ARG:
                        return (expr_tbl[i].p.parse_expr_arg(first, last,
                            expr_tbl[i].val, db));
                case EXPR_NOARG:
                        return (expr_tbl[i].p.parse_expr_noarg(first, last,
                            db));
                }
        }

        switch (first[0]) {
        case 'L':
                return (parse_expr_primary(first, last, db));
        case 'T':
                return (parse_template_param(first, last, db));
        case 'f':
                return (parse_function_param(first, last, db));
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
                return (parse_unresolved_name(first, last, db));
        }

        return (first);
}

static const char *
parse_binary_expr(const char *first, const char *last, const char *op,
    cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2)
                return (first);

        size_t n = nlen(db);

        const char *t1 = parse_expression(first + 2, last, db);
        if (t1 == first + 2)
                return (first);

        nadd_l(db, op, 0);

        const char *t2 = parse_expression(t1, last, db);
        if (t2 == t1)
                return (first);

        if (NAMT(db, n) != 3)
                return (first);

        VERIFY3U(nlen(db), >, 2);

        nfmt(db, "({2}) {1} ({0})", NULL);
        if (strcmp(op, ">") == 0)
                nfmt(db, "({0})", NULL);

        return (t2);
}

static const char *
parse_prefix_expr(const char *first, const char *last, const char *op,
    cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2)
                return (first);

        nadd_l(db, op, 0);

        const char *t = parse_expression(first + 2, last, db);
        if (t == first + 2) {
                return (first);
        }

        VERIFY3U(nlen(db), >, 1);

        nfmt(db, "{1}({0})", NULL);
        return (t);
}

static const char *
parse_gs(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        const char *t = NULL;

        if (last - first < 4)
                return (first);

        if (first[2] == 'n' && (first[3] == 'a' || first[3] == 'w'))
                t = parse_new_expr(first + 2, last, db);
        else if (first[2] == 'd' && (first[3] == 'l' || first[3] == 'a'))
                t = parse_del_expr(first + 2, last, db);
        else
                return (first);

        if (t == first + 2)
                return (first);

        VERIFY3U(nlen(db), >, 0);

        nfmt(db, "::{0}", NULL);
        return (t);
}

/*
 * [gs] nw <expression>* _ <type> E             # new (expr-list) type
 * [gs] nw <expression>* _ <type> <initializer> # new (expr-list) type (init)
 * [gs] na <expression>* _ <type> E             # new[] (expr-list) type
 * [gs] na <expression>* _ <type> <initializer> # new[] (expr-list) type (init)
 * <initializer> ::= pi <expression>* E         # parenthesized initialization
 */
static const char *
parse_new_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        /* note [gs] is already handled by parse_gs() */
        if (last - first < 3)
                return (first);

        VERIFY3U(first[0], ==, 'n');
        VERIFY(first[1] == 'a' || first[1] == 'w');

        const char *t1 = first + 2;
        const char *t2 = NULL;
        size_t n = nlen(db);

        nadd_l(db, (first[1] == 'w') ? "new" : "new[]", 0);

        while (t1 != last && t1[0] != '_') {
                t2 = parse_expression(t1, last, db);
                VERIFY3P(t2, !=, NULL);
                if (t2 == t1)
                        return (first);
                t1 = t2;
        }
        if (t1 == last)
                return (first);

        if (NAMT(db, n) > 1) {
                njoin(db, NAMT(db, n) - 1, ", ");
                nfmt(db, "({0})", NULL);
        }

        t2 = parse_type(t1 + 1, last, db);
        if (t1 + 1 == t2)
                return (first);

        if (t2[0] != 'E') {
                if (last - t2 < 3)
                        return (first);
                if (t2[0] != 'p' && t2[1] != 'i')
                        return (first);

                t2 += 2;
                const char *t3 = t2;
                size_t n1 = nlen(db);

                while (t2[0] != 'E' && t2 != last) {
                        t3 = parse_expression(t2, last, db);

                        if (t2 == t3)
                                return (first);
                        t2 = t3;
                }
                if (t3 == last || t3[0] != 'E')
                        return (first);

                if (NAMT(db, n1) > 0) {
                        njoin(db, NAMT(db, n1), ", ");
                        nfmt(db, "({0})", NULL);
                }
        }

        njoin(db, NAMT(db, n), " ");
        return (t2 + 1);
}

static const char *
parse_del_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 3)
                return (first);

        VERIFY3U(first[0], ==, 'd');
        VERIFY(first[1] == 'l' || first[1] == 'a');

        size_t n = nlen(db);
        const char *t = parse_expression(first + 2, last, db);
        if (t == first + 2 || NAMT(db, n) != 1)
                return (first);

        nfmt(db, (first[1] == 'a') ? "delete[] {0}" : "delete {0}", NULL);
        return (t);
}

static const char *
parse_idx_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);
        VERIFY3U(first[0], ==, 'i');
        VERIFY3U(first[1], ==, 'x');

        size_t n = nlen(db);
        const char *t1 = parse_expression(first + 2, last, db);
        if (t1 == first + 2)
                return (first);

        const char *t2 = parse_expression(t1, last, db);
        if (t2 == t1 || NAMT(db, n) != 2)
                return (first);

        nfmt(db, "({0})[{1}]", NULL);
        return (t2);
}

static const char *
parse_ppmm_expr(const char *first, const char *last, const char *fmt,
    cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 3)
                return (first);

        const char *t = NULL;
        size_t n = nlen(db);

        if (first[2] == '_') {
                t = parse_binary_expr(first + 3, last, "--", db);
                if (t == first + 3)
                        return (first);
                return (t);
        }

        t = parse_expression(first + 2, last, db);
        if (t == first + 2 || NAMT(db, n) < 1)
                return (first);

        nfmt(db, fmt, NULL);
        return (t);
}

static const char *
parse_mm_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);
        VERIFY3U(first[0], ==, 'm');
        VERIFY3U(first[1], ==, 'm');

        return (parse_ppmm_expr(first, last, "({0})--", db));
}

static const char *
parse_pp_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        VERIFY3U(first[0], ==, 'p');
        VERIFY3U(first[0], ==, 'p');

        return (parse_ppmm_expr(first, last, "({0})++", db));
}

static const char *
parse_trinary_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        const char *t1, *t2, *t3;
        size_t n = nlen(db);

        if (last - first < 2)
                return (first);

        t1 = parse_expression(first + 2, last, db);
        if (t1 == first + 2)
                return (first);
        t2 = parse_expression(t1, last, db);
        if (t1 == t2)
                return (first);
        t3 = parse_expression(t2, last, db);
        if (t3 == t2)
                return (first);

        if (NAMT(db, n) != 3)
                return (first);

        nfmt(db, "({2}) ? ({1}) : ({0})", NULL);
        return (t3);
}

static const char *
parse_noexcept_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2)
                return (first);

        size_t n = nlen(db);
        const char *t = parse_expression(first + 2, last, db);
        if (t == first + 2 || NAMT(db, n) != 1)
                return (first);

        nfmt(db, "noexcept ({0})", NULL);
        return (t);
}

/*
 * cc <type> <expression>       # const_cast<type> (expression)
 * dc <type> <expression>       # dynamic_cast<type> (expression)
 * rc <type> <expression>       # reinterpret_cast<type> (expression)
 * sc <type> <expression>       # static_cast<type> (expression)
 */
static const char *
parse_cast_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2)
                return (first);

        const char *fmt = NULL;
        switch (first[0]) {
        case 'c':
                fmt = "const_cast<{1}> ({0})";
                break;
        case 'd':
                fmt = "dynamic_cast<{1}> ({0})";
                break;
        case 'r':
                fmt = "reinterpret_cast<{1}> ({0})";
                break;
        case 's':
                fmt = "static_cast<{1}> ({0})";
                break;
        default:
                return (first);
        }

        VERIFY3U(first[1], ==, 'c');

        const char *t1 = parse_type(first + 2, last, db);
        if (t1 == first + 2)
                return (first);

        const char *t2 = parse_expression(t1, last, db);
        if (t2 == t1)
                return (first);

        VERIFY3U(nlen(db), >, 1);

        nfmt(db, fmt, NULL);
        return (t2);
}

/* pt <expression> <expression>         # expr->name */
static const char *
parse_arrow_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 4)
                return (first);

        size_t n = nlen(db);

        const char *t1 = parse_expression(first + 2, last, db);
        if (t1 == first + 2)
                return (first);

        const char *t2 = parse_expression(t1, last, db);
        if (t2 == t1 || NAMT(db, n) != 2)
                return (first);

        nfmt(db, "{1}->{0}", NULL);
        return (t2);
}

/* wrap value in () when necessary */
static void
paren(str_pair_t *sp)
{
        str_t *l = &sp->strp_l;
        str_t *r = &sp->strp_r;

        if (str_length(r) > 1 &&
            r->str_s[0] == ' ' && r->str_s[1] == '[') {
                (void) str_append(l, " (", 2);
                (void) str_insert(r, 0, ")", 1);
        } else if (str_length(r) > 0 && r->str_s[0] == '(') {
                (void) str_append(l, "(", 1);
                (void) str_insert(r, 0, ")", 1);
        }
}

/* BEGIN CSTYLED */
/*
 * <type> ::= <builtin-type>
 *        ::= <function-type>
 *        ::= <class-enum-type>
 *        ::= <array-type>
 *        ::= <pointer-to-member-type>
 *        ::= <template-param>
 *        ::= <template-template-param> <template-args>
 *        ::= <decltype>
 *        ::= <substitution>
 *        ::= <CV-qualifiers> <type>
 *        ::= P <type>        # pointer-to
 *        ::= R <type>        # reference-to
 *        ::= O <type>        # rvalue reference-to (C++0x)
 *        ::= C <type>        # complex pair (C 2000)
 *        ::= G <type>        # imaginary (C 2000)
 *        ::= Dp <type>       # pack expansion (C++0x)
 *        ::= U <source-name> <type>  # vendor extended type qualifier
 * extension := U <objc-name> <objc-type>  # objc-type<identifier>
 * extension := <vector-type> # <vector-type> starts with Dv
 *
 * <objc-name> ::= <k0 number> objcproto <k1 number> <identifier>  # k0 = 9 + <number of digits in k1> + k1
 * <objc-type> := <source-name>  # PU<11+>objcproto 11objc_object<source-name> 11objc_object -> id<source-name>
 */
/* END CSTYLED */
static const char *
parse_type(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (first == last)
                return (first);

        switch (first[0]) {
        case 'r':
        case 'V':
        case 'K':
                return (parse_qual_type(first, last, db));
        }

        const char *t = first;
        const char *t1 = NULL;
        str_pair_t *sp = NULL;
        size_t n = nlen(db);
        size_t amt = 0;

        t = parse_builtin_type(first, last, db);
        if (t != first)
                return (t);

        switch (first[0]) {
        case 'A':
                t = parse_array_type(first, last, db);
                if (t == first || NAMT(db, n) == 0)
                        return (first);
                save_top(db, 1);
                return (t);

        case 'C':
                t = parse_type(first + 1, last, db);
                if (t == first + 1 || NAMT(db, n) == 0)
                        return (first);

                (void) str_append(TOP_L(db), " complex", 8);
                save_top(db, 1);
                return (t);

        case 'F':
                t = parse_function_type(first, last, db);
                if (t == first || NAMT(db, n) == 0)
                        return (first);
                save_top(db, 1);
                return (t);

        case 'G':
                t = parse_type(first + 1, last, db);
                if (t == first + 1 || NAMT(db, n) == 0)
                        return (first);

                (void) str_append(TOP_L(db), " imaginary", 10);
                save_top(db, 1);
                return (t);

        case 'M':
                t = parse_pointer_to_member_type(first, last, db);
                if (t == first || NAMT(db, n) == 0)
                        return (first);
                save_top(db, 1);
                return (t);

        case 'O':
                t = parse_type(first + 1, last, db);
                amt = NAMT(db, n);
                if (t == first + 1 || amt == 0)
                        return (first);

                sp = name_at(&db->cpp_name, amt - 1);
                for (size_t i = 0; i < amt; i++, sp++) {
                        paren(sp);
                        if (str_pair_len(sp) > 0)
                                (void) str_append(&sp->strp_l, "&&", 2);
                }

                save_top(db, amt);
                return (t);

        case 'P':
                t = parse_type(first + 1, last, db);
                amt = NAMT(db, n);
                if (t == first + 1 || amt == 0)
                        return (first);

                sp = name_at(&db->cpp_name, amt - 1);
                for (size_t i = 0; i < amt; i++, sp++) {
                        str_t *l = &sp->strp_l;

                        if (str_pair_len(sp) == 0)
                                continue;

                        paren(sp);
                        if (first[1] != 'U' ||
                            strncmp(l->str_s, "objc_object<", 12) != 0) {
                                (void) str_append(l, "*", 1);
                        } else {
                                (void) str_erase(l, 0, 11);
                                (void) str_insert(l, 0, "id", 2);
                        }
                }
                save_top(db, amt);
                return (t);

        case 'R':
                t = parse_type(first + 1, last, db);
                amt = NAMT(db, n);
                if (t == first + 1 || amt == 0)
                        return (first);

                sp = name_at(&db->cpp_name, amt - 1);
                for (size_t i = 0; i < amt; i++, sp++) {
                        if (str_length(&sp->strp_l) == 0 &&
                            str_length(&sp->strp_r) == 0)
                                continue;

                        paren(sp);
                        (void) str_append(&sp->strp_l, "&", 1);
                }

                save_top(db, amt);
                return (t);

        case 'T':
                t = parse_template_param(first, last, db);
                if (t == first)
                        return (first);

                amt = NAMT(db, n);
                save_top(db, amt);
                if (!db->cpp_try_to_parse_template_args || amt != 1)
                        return (t);

                t1 = parse_template_args(t, last, db);
                if (t1 == t)
                        return (t);

                nfmt(db, "{1:L}{0}", "{1:R}");
                save_top(db, 1);
                return (t1);

        case 'U':
                if (first + 1 == last)
                        return (first);

                t = parse_source_name(first + 1, last, db);
                if (t == first + 1)
                        return (first);

                nfmt(db, "{0}", NULL);

                t1 = parse_type(t, last, db);
                if (t1 == t || NAMT(db, n) < 2)
                        return (first);

                const str_t *name = &name_at(&db->cpp_name, 1)->strp_l;

                if (str_length(name) > 0 &&
                    strncmp(name->str_s, "objcproto", 9) != 0) {
                        nfmt(db, "{0} {1}", NULL);
                } else {
                        t = parse_source_name(name->str_s + 9,
                            name->str_s + name->str_len, db);
                        if (t != name->str_s + 9) {
                                nfmt(db, "{1}<{0}>", NULL);

                                str_pair_t save = {0};

                                name_pop(&db->cpp_name, &save);

                                /* get rid of 'objcproto' */
                                name_pop(&db->cpp_name, NULL);
                                CK(name_add_str(&db->cpp_name, &save.strp_l,
                                    &save.strp_r));
                        } else {
                                nfmt(db, "{1} {0}", NULL);
                        }
                }

                save_top(db, 1);
                return (t1);

        case 'S':
                if (first + 1 != last && first[1] == 't') {
                        t = parse_name(first, last, NULL, db);
                        if (t == first || NAMT(db, n) == 0)
                                return (first);

                        save_top(db, 1);
                        return (t);
                }

                t = parse_substitution(first, last, db);
                if (t == first)
                        return (first);

                /*
                 * If the substitution is a <template-param>, it might
                 * be followed by <template-args>
                 */
                t1 = parse_template_args(t, last, db);
                if (t1 == t)
                        return (t);

                if (NAMT(db, n) < 2)
                        return (t);

                nfmt(db, "{1:L}{0}", "{1:R}");
                save_top(db, 1);
                return (t1);

        case 'D':
                if (first + 1 == last)
                        return (first);

                switch (first[1]) {
                case 'p':
                        t = parse_type(first + 2, last, db);
                        if (t == first + 2)
                                break;

                        save_top(db, NAMT(db, n));
                        return (t);

                case 't':
                case 'T':
                        t = parse_decltype(first, last, db);
                        if (first == t)
                                break;

                        save_top(db, 1);
                        return (t);

                case 'v':
                        t = parse_vector_type(first, last, db);
                        if (first == t)
                                break;

                        if (NAMT(db, n) == 0)
                                return (first);

                        save_top(db, 1);
                        return (t);
                }
                break;
        }

        /*
         * must check for builtin-types before class-enum-types to avoid
         * ambiguities with operator-names
         */
        t = parse_builtin_type(first, last, db);
        if (t != first)
                return (t);

        t = parse_name(first, last, NULL, db);
        if (t == first || NAMT(db, n) == 0)
                return (first);

        save_top(db, 1);
        return (t);
}

static const char *
parse_qual_type(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        const char *t = NULL;
        const char *t1 = NULL;
        unsigned cv = 0;

        t = parse_cv_qualifiers(first, last, &cv);
        if (t == first)
                return (first);

        size_t n = nlen(db);
        boolean_t is_func = !!(t[0] == 'F');

        t1 = parse_type(t, last, db);
        size_t amt = NAMT(db, n);
        if (t == t1 || amt == 0)
                return (first);

        if (is_func)
                sub_pop(&db->cpp_subs);

        str_pair_t *sp = name_at(&db->cpp_name, amt - 1);

        for (size_t i = 0; i < amt; i++, sp++) {
                str_t *s = NULL;

                if (!is_func) {
                        s = &sp->strp_l;

                        if (str_length(s) == 0)
                                continue;

                        if (cv & 1)
                                (void) str_append(s, " const", 6);
                        if (cv & 2)
                                (void) str_append(s, " volatile", 9);
                        if (cv & 4)
                                (void) str_append(s, " restrict", 9);

                        continue;
                }

                s = &sp->strp_r;
                size_t pos = str_length(s);

                if (pos > 0 && s->str_s[pos - 1] == '&') {
                        pos--;
                        if (s->str_s[pos - 1] == '&')
                                pos--;
                }

                if (cv & 1) {
                        (void) str_insert(s, pos, " const", 6);
                        pos += 6;
                }
                if (cv & 2) {
                        (void) str_insert(s, pos, " volatile", 9);
                        pos += 9;
                }
                if (cv & 4) {
                        (void) str_insert(s, pos, " restrict", 9);
                }
        }

        save_top(db, amt);
        return (t1);
}

/*
 * at <type>            # alignof (a type)
 * az <expression>      # alignof (a expression)
 */
static const char *
parse_alignof(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2)
                return (first);

        const char *(*fn)(const char *, const char *, cpp_db_t *);

        fn = (first[1] == 't') ? parse_type : parse_expression;

        size_t n = nlen(db);
        const char *t = fn(first + 2, last, db);
        if (t == first + 2 || NAMT(db, n) != 1)
                return (first);

        nfmt(db, "alignof ({0})", NULL);
        return (t);
}

/*
 * st <type>    # sizeof (a type)
 * sz <expr>    # sizeof (a expression)
 */
static const char *
parse_sizeof(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2)
                return (first);

        VERIFY3U(first[0], ==, 's');

        const char *t = NULL;
        size_t n = nlen(db);

        switch (first[1]) {
        case 't':
                t = parse_type(first + 2, last, db);
                break;
        case 'z':
                t = parse_expression(first + 2, last, db);
                break;
        default:
                return (first);
        }
        if (t == first + 2 || NAMT(db, n) != 1)
                return (first);

        nfmt(db, "sizeof ({0})", NULL);
        return (t);
}

/* BEGIN CSTYLED */
/*
 * <function-param> ::= fp <top-level CV-qualifiers> _                                     # L == 0, first parameter
 *                  ::= fp <top-level CV-qualifiers> <parameter-2 non-negative number> _   # L == 0, second and later parameters
 *                  ::= fL <L-1 non-negative number> p <top-level CV-qualifiers> _         # L > 0, first parameter
 *                  ::= fL <L-1 non-negative number> p <top-level CV-qualifiers> <parameter-2 non-negative number> _   # L > 0, second and later parameters
 */
/* END CSTYLED */
static const char *
parse_function_param(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 3 || first[0] != 'f')
                return (first);

        const char *t1 = first + 2;
        const char *t2 = NULL;
        unsigned cv = 0;

        if (first[1] == 'L') {
                t2 = parse_number(t1, last);
                if (t2 == last || t2[0] != 'p')
                        return (first);
                t1 = t2;
        }

        if (first[1] != 'p')
                return (first);

        t1 = parse_cv_qualifiers(t1, last, &cv);
        t2 = parse_number(t1, last);
        if (t2 == last || t2[0] != '_')
                return (first);

        if (t2 - t1 > 0)
                nadd_l(db, t1, (size_t)(t2 - t1));
        else
                nadd_l(db, "", 0);

        nfmt(db, "fp{0}", NULL);
        return (t2 + 1);
}

/*
 * sZ <template-param>          # size of a parameter pack
 * sZ <function-param>          # size of a function parameter pack
 */
static const char *
parse_sizeof_param_pack_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 3)
                return (first);

        VERIFY3U(first[0], ==, 's');
        VERIFY3U(first[1], ==, 'Z');

        if (first[2] != 'T' && first[2] != 'f')
                return (first);

        const char *t = NULL;
        size_t n = nlen(db);

        if (first[2] == 'T')
                t = parse_template_param(first + 2, last, db);
        else
                t = parse_function_param(first + 2, last, db);

        if (t == first + 2)
                return (first);

        njoin(db, NAMT(db, n), ", ");
        nfmt(db, "sizeof...({0})", NULL);
        return (t);
}

/*
 * te <expression>                                      # typeid (expression)
 * ti <type>                                            # typeid (type)
 */
static const char *
parse_typeid_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 3)
                return (first);

        VERIFY3U(first[0], ==, 't');
        VERIFY(first[1] == 'e' || first[1] == 'i');

        const char *t = NULL;
        size_t n = nlen(db);

        if (first[1] == 'e')
                t = parse_expression(first + 2, last, db);
        else
                t = parse_type(first + 2, last, db);

        if (t == first + 2 || NAMT(db, n) != 1)
                return (first);

        nfmt(db, "typeid ({0})", NULL);
        return (t);
}

/*
 * tr                                                   # throw
 * tw <expression>                                      # throw expression
 */
static const char *
parse_throw_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 3)
                return (first);

        VERIFY3U(first[0], ==, 't');
        VERIFY(first[1] == 'w' || first[1] == 'r');

        if (first[1] == 'r') {
                nadd_l(db, "throw", 0);
                return (first + 2);
        }

        size_t n = nlen(db);
        const char *t = parse_expression(first + 2, last, db);
        if (t == first + 2 || NAMT(db, n) != 1)
                return (first);

        nfmt(db, "throw {0}", NULL);
        return (t);
}

/* ds <expression> <expression>         # expr.*expr */
static const char *
parse_dot_star_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 3)
                return (first);

        VERIFY3U(first[0], ==, 'd');
        VERIFY3U(first[1], ==, 's');

        size_t n = nlen(db);
        const char *t = parse_expression(first + 2, last, db);
        if (t == first + 2)
                return (first);

        const char *t2 = parse_expression(t, last, db);
        if (t == t2 || NAMT(db, n) != 2)
                return (first);

        nfmt(db, "{1}.*{0}", NULL);
        return (t2);
}

/* dt <expression> <unresolved-name>            # expr.name */
static const char *
parse_dot_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 3)
                return (first);

        VERIFY3U(first[0], ==, 'd');
        VERIFY3U(first[1], ==, 't');

        const char *t = parse_expression(first + 2, last, db);
        if (t == first + 2)
                return (first);

        const char *t1 = parse_unresolved_name(t, last, db);
        if (t1 == t)
                return (first);

        nfmt(db, "{1}.{0}", NULL);
        return (t1);
}

/* cl <expression>+ E           # call */
static const char *
parse_call_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 4)
                return (first);

        VERIFY3U(first[0], ==, 'c');
        VERIFY3U(first[1], ==, 'l');

        const char *t = first + 2;
        const char *t1 = NULL;
        size_t n = nlen(db);

        for (t = first + 2; t != last && t[0] != 'E'; t = t1) {
                t1 = parse_expression(t, last, db);
                if (t1 == t)
                        return (first);
        }

        size_t amt = NAMT(db, n);

        if (t == last || amt == 0)
                return (first);

        njoin(db, amt - 1, ", ");
        nfmt(db, "{1}({0})", NULL);

        VERIFY3U(t[0], ==, 'E');
        return (t + 1);
}

/* BEGIN CSTYLED */
/*
 * cv <type> <expression>       # conversion with one argument
 * cv <type> _ <expression>* E  # conversion with a different number of arguments
 */
/* END CSTYLED */
static const char *
parse_conv_expr(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 3)
                return (first);

        VERIFY3U(first[0], ==, 'c');
        VERIFY3U(first[1], ==, 'v');

        const char *t = NULL;
        const char *t1 = NULL;
        size_t n = nlen(db);

        boolean_t try_to_parse_template_args =
            db->cpp_try_to_parse_template_args;

        db->cpp_try_to_parse_template_args = B_FALSE;
        t = parse_type(first + 2, last, db);
        db->cpp_try_to_parse_template_args = try_to_parse_template_args;

        if (t == first + 2)
                return (first);

        if (t[0] != '_') {
                t1 = parse_expression(t, last, db);
                if (t1 == t)
                        return (first);

                t = t1;
        } else {
                size_t n1 = nlen(db);

                /* skip _ */
                t++;
                while (t[0] != 'E' && t != last) {
                        t1 = parse_expression(t, last, db);
                        if (t1 == t)
                                return (first);
                        t1 = t;
                }

                /* E */
                t++;

                njoin(db, NAMT(db, n1), ", ");
        }

        if (NAMT(db, n) < 2)
                return (first);

        nfmt(db, "({1})({0})", NULL);
        return (t);
}

/* <simple-id> ::= <source-name> [ <template-args> ] */
static const char *
parse_simple_id(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        const char *t = parse_source_name(first, last, db);
        if (t == first)
                return (t);

        const char *t1 = parse_template_args(t, last, db);
        if (t == t1)
                return (t);

        nfmt(db, "{1}{0}", NULL);
        return (t1);
}

/*
 * <unresolved-type> ::= <template-param>
 *                   ::= <decltype>
 *                   ::= <substitution>
 */
static const char *
parse_unresolved_type(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (first == last)
                return (first);

        const char *t = first;
        size_t n = nlen(db);

        switch (first[0]) {
        case 'T':
                t = parse_template_param(first, last, db);
                if (t == first || NAMT(db, n) != 1) {
                        for (size_t i = 0; i < NAMT(db, n); i++)
                                name_pop(&db->cpp_name, NULL);
                        return (first);
                }
                save_top(db, 1);
                return (t);

        case 'D':
                t = parse_decltype(first, last, db);
                if (t == first || NAMT(db, n) == 0)
                        return (first);
                save_top(db, 1);
                return (t);

        case 'S':
                t = parse_substitution(first, last, db);
                if (t != first)
                        return (t);

                if (last - first < 2 || first[1] != 't')
                        return (first);

                t = parse_unqualified_name(first + 2, last, db);
                if (t == first + 2 || NAMT(db, n) == 0)
                        return (first);

                nfmt(db, "std::{0:L}", "{0:R}");
                save_top(db, 1);
                return (t);
        }

        return (first);
}

/* sp <expression>              # pack expansion */
static const char *
parse_pack_expansion(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 3)
                return (first);

        VERIFY3U(first[0], ==, 's');
        VERIFY3U(first[1], ==, 'p');

        const char *t = parse_expression(first + 2, last, db);
        if (t == first +2)
                return (first);

        return (t);
}

/*
 * <unscoped-name> ::= <unqualified-name>
 *                 ::= St <unqualified-name>   # ::std::
 * extension       ::= StL<unqualified-name>
 */
static const char *
parse_unscoped_name(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2)
                return (first);

        const char *t = first;
        const char *t1 = NULL;
        boolean_t st = B_FALSE;

        if (first[0] == 'S' && first[1] == 't') {
                st = B_TRUE;
                t = first + 2;

                if (first + 3 != last && first[2] == 'L')
                        t++;
        }

        t1 = parse_unqualified_name(t, last, db);
        if (t == t1)
                return (first);

        if (st)
                nfmt(db, "std::{0}", NULL);

        return (t1);
}

/*
 * <unqualified-name> ::= <operator-name>
 *                    ::= <ctor-dtor-name>
 *                    ::= <source-name>
 *                    ::= <unnamed-type-name>
 */
const char *
parse_unqualified_name(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (first == last)
                return (first);

        switch (*first) {
        case 'C':
        case 'D':
                return (parse_ctor_dtor_name(first, last, db));
        case 'U':
                return (parse_unnamed_type_name(first, last, db));

        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
                return (parse_source_name(first, last, db));
        default:
                return (parse_operator_name(first, last, db));
        }
}

/*
 * <unnamed-type-name> ::= Ut [ <nonnegative number> ] _
 *                     ::= <closure-type-name>
 *
 * <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
 *
 * <lambda-sig> ::= <parameter type>+
 *                      # Parameter types or "v" if the lambda has no parameters
 */
static const char *
parse_unnamed_type_name(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2 || first[0] != 'U')
                return (first);

        if (first[1] != 't' && first[1] != 'l')
                return (first);

        const char *t1 = first + 2;
        const char *t2 = NULL;

        if (first[1] == 't') {
                while (t1 != last && t1[0] != '_' && ISDIGIT(t1[0]))
                        t1++;

                if (t1[0] != '_')
                        return (first);

                if (t1 == first + 2)
                        nadd_l(db, "", 0);
                else
                        nadd_l(db, first + 2, (size_t)(t1 - first - 2));

                nfmt(db, "'unnamed{0}'", NULL);
                return (t1 + 1);
        }

        size_t n = nlen(db);

        if (first[2] != 'v') {
                do {
                        t2 = parse_type(t1, last, db);
                        if (t1 == t2)
                                return (first);
                        t1 = t2;
                } while (t1 != last && t1[0] != 'E');

                if (t1 == last || NAMT(db, n) < 1)
                        return (first);

                if (NAMT(db, n) < 1)
                        return (first);
        } else {
                t1++;
                if (t1[0] != 'E')
                        return (first);
        }

        njoin(db, NAMT(db, n), ", ");

        /* E */
        t1++;

        t2 = t1;
        while (t2 != last && t2[0] != '_') {
                char c = *t2++;
                if (!ISDIGIT(c))
                        return (first);
        }

        if (t2[0] != '_')
                return (first);

        if (t2 - t1 > 0)
                nadd_l(db, t1, (size_t)(t2 - t1));
        else
                nadd_l(db, "", 0);

        nfmt(db, "'lambda{0}'({1})", NULL);

        /* _ */
        return (t2 + 1);
}

static struct {
        const char *alias;
        const char *fullname;
        const char *basename;
} aliases[] = {
        {
                "std::string",
                "std::basic_string<char, std::char_traits<char>, "
                    "std::allocator<char> >",
                "basic_string"
        },
        {
                "std::istream",
                "std::basic_istream<char, std::char_traits<char> >",
                "basic_istream"
        },
        {
                "std::ostream",
                "std::basic_ostream<char, std::char_traits<char> >",
                "basic_ostream"
        },
        {
                "std::iostream",
                "std::basic_iostream<char, std::char_traits<char> >",
                "basic_iostream"
        }
};

static void
basename(cpp_db_t *db)
{
        str_t *s = TOP_L(db);

        for (size_t i = 0; i < ARRAY_SIZE(aliases); i++) {
                if (str_length(s) != strlen(aliases[i].alias))
                        continue;
                if (strncmp(aliases[i].alias, s->str_s, str_length(s)) != 0)
                        continue;

                /* swap out alias for full name */
                sysdem_ops_t *ops = s->str_ops;
                str_fini(s);
                str_init(s, ops);
                str_set(s, aliases[i].fullname, 0);

                nadd_l(db, aliases[i].basename, 0);
                return;
        }

        const char *start = s->str_s;
        const char *end = s->str_s + s->str_len;

        /*
         * if name ends with a template i.e. <.....> back up to start
         * of outermost template
         */
        unsigned c = 0;

        if (end[-1] == '>') {
                for (; end > start; end--) {
                        switch (end[-1]) {
                        case '<':
                                if (--c == 0) {
                                        end--;
                                        goto out;
                                }
                                break;
                        case '>':
                                c++;
                                break;
                        }
                }
        }

out:
        VERIFY3P(end, >=, start);

        if (end - start < 2) {
                nadd_l(db, "", 0);
                return;
        }

        for (start = end - 1; start > s->str_s; start--) {
                if (start[0] == ':') {
                        start++;
                        break;
                }
        }

        VERIFY3P(end, >=, start);

        nadd_l(db, start, (size_t)(end - start));
}

/*
 * <ctor-dtor-name> ::= C1    # complete object constructor
 *                  ::= C2    # base object constructor
 *                  ::= C3    # complete object allocating constructor
 *   extension      ::= C5    # ?
 *                  ::= D0    # deleting destructor
 *                  ::= D1    # complete object destructor
 *                  ::= D2    # base object destructor
 *   extension      ::= D5    # ?
 */
static const char *
parse_ctor_dtor_name(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2 || nempty(db) || str_length(TOP_L(db)) == 0)
                return (first);

        switch (first[0]) {
        case 'C':
                switch (first[1]) {
                case '1':
                case '2':
                case '3':
                case '5':
                        basename(db);
                        break;
                default:
                        return (first);
                }
                break;
        case 'D':
                switch (first[1]) {
                case '0':
                case '1':
                case '2':
                case '5':
                        basename(db);
                        (void) str_insert(TOP_L(db), 0, "~", 1);
                        break;
                default:
                        return (first);
                }
                break;
        default:
                return (first);
        }

        db->cpp_parsed_ctor_dtor_cv = B_TRUE;
        return (first + 2);
}

static const char *
parse_integer_literal(const char *first, const char *last, const char *fmt,
    cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        const char *t = parse_number(first, last);
        const char *start = first;

        if (t == first || t == last || t[0] != 'E')
                return (first);

        if (first[0] == 'n')
                start++;

        nadd_l(db, start, (size_t)(t - start));
        if (start != first)
                nfmt(db, "-{0}", NULL);

        nfmt(db, fmt, NULL);
        return (t + 1);
}

static struct float_data_s {
        const char *spec;
        size_t mangled_size;
        size_t max_demangled_size;
        char type;
} float_info[] = {
        { "%af", 8, 24, 'f' },          /* float */
        { "%a", 16, 32, 'd' },          /* double */
        { "%LaL", 20, 40, 'e' }         /* long double */
};

static const char *
parse_floating_literal(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);
        VERIFY(first[0] == 'f' || first[0] == 'd' || first[0] == 'e');

        const struct float_data_s *fd = NULL;

        for (size_t i = 0; i < ARRAY_SIZE(float_info); i++) {
                if (float_info[i].type != first[0])
                        continue;

                fd = &float_info[i];
                break;
        }

        if (fd == NULL || (size_t)(last - first) < fd->mangled_size)
                return (first);

        union {
                union {
                        float v;
                        char buf[sizeof (float)];
                } f;
                union {
                        double v;
                        char buf[sizeof (double)];
                } d;
                union {
                        long double v;
                        char buf[sizeof (long double)];
                } ld;
        } conv;

        const char *t = NULL;
        char *e = NULL;

        switch (first[0]) {
        case 'f':
                e = conv.f.buf;
                break;
        case 'd':
                e = conv.d.buf;
                break;
        case 'e':
                e = conv.ld.buf;
                break;
        }
        last = first + fd->mangled_size + 1;

#if defined(_BIG_ENDIAN)
        for (t = first + 1; t != last; t++, e++) {
                if (!is_xdigit(t[0]))
                        return (first);

                unsigned d1 = ISDIGIT(t[0]) ?  t[0] - '0' : t[0] - 'a' + 10;
                t++;
                unsigned d0 = ISDIGIT(t[0]) ?  t[0] - '0' : t[0] - 'a' + 10;

                *e = (d1 << 4) + d0;
        }
#elif defined(_LITTLE_ENDIAN)
        for (t = last - 1; t > first; t--, e++) {
                if (!is_xdigit(t[0]))
                        return (first);

                unsigned d0 = ISDIGIT(t[0]) ?  t[0] - '0' : t[0] - 'a' + 10;
                t--;
                unsigned d1 = ISDIGIT(t[0]) ?  t[0] - '0' : t[0] - 'a' + 10;

                *e = (d1 << 4) + d0;
        }
        t = last;
#else
#error One of _BIG_ENDIAN or _LITTLE_ENDIAN must be defined
#endif

        if (t[0] != 'E')
                return (first);

        str_t num = { 0 };
        str_init(&num, db->cpp_ops);

        num.str_size = fd->max_demangled_size + 1;
        num.str_s = zalloc(db->cpp_ops, num.str_size);
        CK(num.str_s != NULL);

        int n = 0;

        switch (first[0]) {
        case 'f':
                n = snprintf(num.str_s, fd->max_demangled_size, fd->spec,
                    conv.f.v);
                break;
        case 'd':
                n = snprintf(num.str_s, fd->max_demangled_size, fd->spec,
                    conv.d.v);
                break;
        case 'e':
                n = snprintf(num.str_s, fd->max_demangled_size, fd->spec,
                    conv.ld.v);
        }

        if (n >= fd->max_demangled_size || n <= 0) {
                str_fini(&num);
                return (first);
        }

        num.str_len = n;
        (void) name_add_str(&db->cpp_name, &num, NULL);

        return (t + 1);
}

/*
 * <expr-primary> ::= L <type> <value number> E # integer literal
 *                ::= L <type> <value float> E  # floating literal
 *                ::= L <string type> E         # string literal
 *                ::= L <nullptr type> E        # nullptr literal (i.e., "LDnE")
 *
 *                ::= L <type> <real-part float> _ <imag-part float> E
 *                                              # complex floating point
 *                                              # literal (C 2000)
 *
 *                ::= L <mangled-name> E        # external name
 */
static struct {
        int             c;
        const char      *fmt;
} int_lits[] = {
        { 'a', "(signed char){0}" },
        { 'c', "(char){0}" },
        { 'h', "(unsigned char){0}" },
        { 'i', "{0}" },
        { 'j', "{0}u" },
        { 'l', "{0}l" },
        { 'm', "{0}ul" },
        { 'n', "(__int128){0}" },
        { 'o', "(unsigned __int128){0}" },
        { 's', "(short){0}" },
        { 't', "(unsigned short){0}" },
        { 'w', "(wchar_t){0}" },
        { 'x', "{0}ll" },
        { 'y', "{0}ull" }
};

static const char *
parse_expr_primary(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 4 || first[0] != 'L')
                return (first);

        const char *t = NULL;

        for (size_t i = 0; i < ARRAY_SIZE(int_lits); i++) {
                if (first[1] == int_lits[i].c) {
                        t = parse_integer_literal(first + 2, last,
                            int_lits[i].fmt, db);
                        return ((t == first + 2) ? first : t);
                }
        }

        switch (first[1]) {
        case 'b':
                if (first[3] != 'E')
                        return (first);

                switch (first[2]) {
                case '0':
                        nadd_l(db, "false", 5);
                        break;
                case '1':
                        nadd_l(db, "true", 4);
                        break;
                default:
                        return (first);
                }
                return (first + 4);
        case 'd':       /* double */
        case 'e':       /* long double */
        case 'f':       /* float */
                t = parse_floating_literal(first + 1, last, db);
                return ((t == first + 1) ? first : t);
        case 'T':
/* BEGIN CSTYLED */
                /*
                 * Invalid mangled name per
                 *   http://sourcerytools.com/pipermail/cxx-abi-dev/2011-August/002422.html
                 *
                 */
/* END CSTYLED */
                return (first);
        case '_':
                if (first[2] != 'Z')
                        return (first);

                t = parse_encoding(first + 3, last, db);
                if (t == first + 3 || t == last || t[0] != 'E')
                        return (first);

                /* skip E */
                return (t + 1);
        default:
                t = parse_type(first + 1, last, db);
                if (t == first + 1 || t == last)
                        return (first);

                if (t[0] == 'E')
                        return (t + 1);

                const char *n;
                for (n = t; n != last && ISDIGIT(n[0]); n++)
                        ;
                if (n == last || nempty(db) || n[0] != 'E')
                        return (first);
                if (n == t)
                        return (t);

                nadd_l(db, t, (size_t)(n - t));
                nfmt(db, "({1}){0}", NULL);

                return (n + 1);
        }
}

/*
 *   <operator-name>
 *                   ::= aa    # &&
 *                   ::= ad    # & (unary)
 *                   ::= an    # &
 *                   ::= aN    # &=
 *                   ::= aS    # =
 *                   ::= cl    # ()
 *                   ::= cm    # ,
 *                   ::= co    # ~
 *                   ::= cv <type>    # (cast)
 *                   ::= da    # delete[]
 *                   ::= de    # * (unary)
 *                   ::= dl    # delete
 *                   ::= dv    # /
 *                   ::= dV    # /=
 *                   ::= eo    # ^
 *                   ::= eO    # ^=
 *                   ::= eq    # ==
 *                   ::= ge    # >=
 *                   ::= gt    # >
 *                   ::= ix    # []
 *                   ::= le    # <=
 *                   ::= li <source-name>       # operator ""
 *                   ::= ls    # <<
 *                   ::= lS    # <<=
 *                   ::= lt    # <
 *                   ::= mi    # -
 *                   ::= mI    # -=
 *                   ::= ml    # *
 *                   ::= mL    # *=
 *                   ::= mm    # -- (postfix in <expression> context)
 *                   ::= na    # new[]
 *                   ::= ne    # !=
 *                   ::= ng    # - (unary)
 *                   ::= nt    # !
 *                   ::= nw    # new
 *                   ::= oo    # ||
 *                   ::= or    # |
 *                   ::= oR    # |=
 *                   ::= pm    # ->*
 *                   ::= pl    # +
 *                   ::= pL    # +=
 *                   ::= pp    # ++ (postfix in <expression> context)
 *                   ::= ps    # + (unary)
 *                   ::= pt    # ->
 *                   ::= qu    # ?
 *                   ::= rm    # %
 *                   ::= rM    # %=
 *                   ::= rs    # >>
 *                   ::= rS    # >>=
 *                   ::= v <digit> <source-name> # vendor extended operator
 */
static struct {
        const char code[3];
        const char *op;
} op_tbl[] = {
        { "aa", "operator&&" },
        { "ad", "operator&" },
        { "an", "operator&" },
        { "aN", "operator&=" },
        { "aS", "operator=" },
        { "cl", "operator()" },
        { "cm", "operator," },
        { "co", "operator~" },
        { "da", "operator delete[]" },
        { "de", "operator*" },
        { "dl", "operator delete" },
        { "dv", "operator/" },
        { "dV", "operator/=" },
        { "eo", "operator^" },
        { "eO", "operator^=" },
        { "eq", "operator==" },
        { "ge", "operator>=" },
        { "gt", "operator>" },
        { "ix", "operator[]" },
        { "le", "operator<=" },
        { "ls", "operator<<" },
        { "lS", "operator<<=" },
        { "lt", "operator<" },
        { "mi", "operator-" },
        { "mI", "operator-=" },
        { "ml", "operator*" },
        { "mL", "operator*=" },
        { "mm", "operator--" },
        { "na", "operator new[]" },
        { "ne", "operator!=" },
        { "ng", "operator-" },
        { "nt", "operator!" },
        { "nw", "operator new" },
        { "oo", "operator||" },
        { "or", "operator|" },
        { "oR", "operator|=" },
        { "pm", "operator->*" },
        { "pl", "operator+" },
        { "pL", "operator+=" },
        { "pp", "operator++" },
        { "ps", "operator+" },
        { "pt", "operator->" },
        { "qu", "operator?" },
        { "rm", "operator%" },
        { "rM", "operator%=" },
        { "rs", "operator>>" },
        { "rS", "operator>>=" }
};

static const char *
parse_operator_name(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2)
                return (first);

        for (size_t i = 0; i < ARRAY_SIZE(op_tbl); i++) {
                if (strncmp(first, op_tbl[i].code, 2) != 0)
                        continue;

                nadd_l(db, op_tbl[i].op, 0);
                return (first + 2);
        }

        const char *t = NULL;

        if (first[0] == 'l' && first[1] == 'i') {
                t = parse_source_name(first + 2, last, db);
                if (t == first + 2 || nempty(db))
                        return (first);

                nfmt(db, "operator\"\" {0}", NULL);
                return (t);
        }

        if (first[0] == 'v') {
                if (!ISDIGIT(first[1]))
                        return (first);

                t = parse_source_name(first + 2, last, db);
                if (t == first + 2)
                        return (first);

                nfmt(db, "operator {0}", NULL);
                return (t);
        }

        if (first[0] != 'c' && first[1] != 'v')
                return (first);

        boolean_t try_to_parse_template_args =
            db->cpp_try_to_parse_template_args;

        db->cpp_try_to_parse_template_args = B_FALSE;
        t = parse_type(first + 2, last, db);
        db->cpp_try_to_parse_template_args = try_to_parse_template_args;

        if (t == first + 2 || nempty(db))
                return (first);

        nfmt(db, "operator {0}", NULL);
        db->cpp_parsed_ctor_dtor_cv = B_TRUE;
        return (t);
}

struct type_tbl_s {
        int code;
        const char *name;
};

static struct type_tbl_s type_tbl1[] = {
        { 'a', "signed char" },
        { 'b', "bool" },
        { 'c', "char" },
        { 'd', "double" },
        { 'e', "long double" },
        { 'f', "float" },
        { 'g', "__float128" },
        { 'h', "unsigned char" },
        { 'i', "int" },
        { 'j', "unsigned int" },
        { 'l', "long" },
        { 'm', "unsigned long" },
        { 'n', "__int128" },
        { 'o', "unsigned __int128" },
        { 's', "short" },
        { 't', "unsigned short" },
        { 'v', "void" },
        { 'w', "wchar_t" },
        { 'x', "long long" },
        { 'y', "unsigned long long" },
        { 'z', "..." }
};

static struct type_tbl_s type_tbl2[] = {
        { 'a', "auto" },
        { 'c', "decltype(auto)" },
        { 'd', "decimal64" },
        { 'e', "decimal128" },
        { 'f', "decimal32" },
        { 'h', "decimal16" },
        { 'i', "char32_t" },
        { 'n', "std::nullptr_t" },
        { 's', "char16_t" }
};

static const char *
parse_builtin_type(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (first == last)
                return (first);

        size_t i;

        for (i = 0; i < ARRAY_SIZE(type_tbl1); i++) {
                if (first[0] == type_tbl1[i].code) {
                        nadd_l(db, type_tbl1[i].name, 0);
                        return (first + 1);
                }
        }

        if (first[0] == 'D') {
                if (first + 1 == last)
                        return (first);
                for (i = 0; i < ARRAY_SIZE(type_tbl2); i++) {
                        if (first[1] == type_tbl2[i].code) {
                                nadd_l(db, type_tbl2[i].name, 0);
                                return (first + 2);
                        }
                }
        }

        if (first[0] == 'u') {
                const char *t = parse_source_name(first + 1, last, db);
                if (t == first + 1)
                        return (first);
                return (t);
        }

        return (first);
}

static const char *
parse_base36(const char *first, const char *last, size_t *val)
{
        VERIFY3P(first, <=, last);

        const char *t;

        for (t = first, *val = 0; t != last; t++) {
                if (!ISDIGIT(t[0]) && !ISUPPER(t[0]))
                        return (t);

                *val *= 36;

                if (ISDIGIT(t[0]))
                        *val += t[0] - '0';
                else
                        *val += t[0] - 'A' + 10;
        }
        return (t);
}

static struct type_tbl_s sub_tbl[] = {
        { 'a', "std::allocator" },
        { 'b', "std::basic_string" },
        { 's', "std::string" },
        { 'i', "std::istream" },
        { 'o', "std::ostream" },
        { 'd', "std::iostream" }
};

static const char *
parse_substitution(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (first == last || last - first < 2)
                return (first);

        if (first[0] != 'S')
                return (first);

        for (size_t i = 0; i < ARRAY_SIZE(sub_tbl); i++) {
                if (first[1] == sub_tbl[i].code) {
                        nadd_l(db, sub_tbl[i].name, 0);
                        return (first + 2);
                }
        }

        const char *t = first + 1;
        size_t n = 0;

        if (t[0] != '_') {
                t = parse_base36(first + 1, last, &n);
                if (t == first + 1 || t[0] != '_')
                        return (first);

                /*
                 * S_ == substitution 0,
                 * S0_ == substituion 1,
                 * ...
                 */
                n++;
        }

        if (n >= sub_len(&db->cpp_subs))
                return (first);

        sub(db, n);

        /* skip _ */
        VERIFY3U(t[0], ==, '_');

        return (t + 1);
}

static const char *
parse_source_name(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (first == last)
                return (first);

        const char *t = NULL;
        size_t n = 0;

        for (t = first; t != last && ISDIGIT(t[0]); t++) {
                /* make sure we don't overflow */
                size_t nn = n * 10;
                if (nn < n)
                        return (first);

                nn += t[0] - '0';
                if (nn < n)
                        return (first);

                n = nn;
        }

        if (n == 0 || t == last || t + n > last ||
            (uintptr_t)t + n < (uintptr_t)t)
                return (first);

        if (strncmp(t, "_GLOBAL__N", 10) == 0)
                nadd_l(db, "(anonymous namespace)", 0);
        else
                nadd_l(db, t, n);

        return (t + n);
}

/*
 * extension:
 * <vector-type>           ::= Dv <positive dimension number> _
 *                                    <extended element type>
 *                         ::= Dv [<dimension expression>] _ <element type>
 * <extended element type> ::= <element type>
 *                         ::= p # AltiVec vector pixel
 */
static const char *
parse_vector_type(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 3)
                return (first);

        VERIFY3U(first[0], ==, 'D');
        VERIFY3U(first[1], ==, 'v');

        const char *t = first + 2;
        const char *t1 = NULL;

        if (ISDIGIT(first[2]) && first[2] != '0') {
                t1 = parse_number(t, last);
                if (t1 == last || t1 + 1 == last || t1[0] != '_')
                        return (first);

                nadd_l(db, t, (size_t)(t1 - t));

                /* skip _ */
                t = t1 + 1;

                if (t[0] != 'p') {
                        t1 = parse_type(t, last, db);
                        if (t1 == t)
                                return (first);

                        nfmt(db, "{0} vector[{1}]", NULL);
                        return (t1);
                }
                nfmt(db, "{0} pixel vector[{1}]", NULL);
                return (t1);
        }

        if (first[2] != '_') {
                t1 = parse_expression(first + 2, last, db);
                if (first == last || t1 == first + 2 || t1[0] != '_')
                        return (first);

                /* skip _ */
                t = t1 + 1;
        } else {
                nadd_l(db, "", 0);
        }

        t1 = parse_type(t, last, db);
        if (t == t1)
                return (first);

        nfmt(db, "{1:L} vector[{0}]", "{1:R}");
        return (t1);
}

/* BEGIN CSTYLED */
/*
 * <decltype>  ::= Dt <expression> E  # decltype of an id-expression or class member access (C++0x)
 *             ::= DT <expression> E  # decltype of an expression (C++0x)
 */
/* END CSTYLED */
static const char *
parse_decltype(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 4)
                return (first);

        VERIFY3U(first[0], ==, 'D');

        if (first[1] != 't' && first[1] != 'T')
                return (first);

        size_t n = nlen(db);
        const char *t = parse_expression(first + 2, last, db);
        if (NAMT(db, n) != 1 || t == first + 2 || t == last || t[0] != 'E')
                return (first);

        nfmt(db, "decltype({0})", NULL);

        /* skip E */
        return (t + 1);
}

/*
 * <array-type> ::= A <positive dimension number> _ <element type>
 *              ::= A [<dimension expression>] _ <element type>
 */
static const char *
parse_array_type(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);
        VERIFY3U(first[0], ==, 'A');

        if (last - first < 3)
                return (first);

        const char *t = first + 1;
        const char *t1 = NULL;
        size_t n = nlen(db);

        if (t[0] != '_') {
                if (ISDIGIT(t[0]) && t[0] != '0') {
                        t1 = parse_number(t, last);
                        if (t1 == last)
                                return (first);

                        nadd_l(db, t, (size_t)(t1 - t));
                } else {
                        t1 = parse_expression(t, last, db);
                        if (t1 == last || t == t1)
                                return (first);
                }

                if (t1[0] != '_')
                        return (first);

                t = t1;
        } else {
                nadd_l(db, "", 0);
        }

        VERIFY3U(t[0], ==, '_');

        t1 = parse_type(t + 1, last, db);
        if (t1 == t + 1 || NAMT(db, n) != 2)
                return (first);

        /*
         * if we have  " [xxx]" already, want new result to be
         * " [yyy][xxx]"
         */
        str_t *r = &name_top(&db->cpp_name)->strp_r;
        if (r->str_len > 1 && r->str_s[0] == ' ' && r->str_s[1] == '[')
                (void) str_erase(r, 0, 1);

        nfmt(db, "{0:L}", " [{1}]{0:R}");
        return (t1);
}

/* <pointer-to-member-type> ::= M <class type> <member type> */
static const char *
parse_pointer_to_member_type(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 3)
                return (first);

        VERIFY3U(first[0], ==, 'M');

        const char *t1 = first + 1;
        const char *t2 = NULL;
        size_t n = nlen(db);

        t2 = parse_type(t1, last, db);
        if (t1 == t2)
                return (first);

        t1 = t2;
        t2 = parse_type(t1, last, db);
        if (t1 == t2)
                return (first);

        if (NAMT(db, n) != 2)
                return (first);

        str_pair_t *func = name_top(&db->cpp_name);

        if (str_length(&func->strp_r) > 0 && func->strp_r.str_s[0] == '(')
                nfmt(db, "{0:L}({1}::*", "){0:R}");
        else
                nfmt(db, "{0:L} {1}::*", "{0:R}");

        return (t2);
}

/* BEGIN CSTYLED */
/*
 * <unresolved-name>
 *  extension        ::= srN <unresolved-type> [<template-args>] <unresolved-qualifier-level>* E <base-unresolved-name>
 *                   ::= [gs] <base-unresolved-name>                     # x or (with "gs") ::x
 *                   ::= [gs] sr <unresolved-qualifier-level>+ E <base-unresolved-name>
 *                                                                       # A::x, N::y, A<T>::z; "gs" means leading "::"
 *                   ::= sr <unresolved-type> <base-unresolved-name>     # T::x / decltype(p)::x
 *  extension        ::= sr <unresolved-type> <template-args> <base-unresolved-name>
 *                                                                       # T::N::x /decltype(p)::N::x
 *  (ignored)        ::= srN <unresolved-type>  <unresolved-qualifier-level>+ E <base-unresolved-name>
 */
/* END CSTYLED */
static const char *
parse_unresolved_name(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2)
                return (first);

        const char *t = first;
        const char *t2 = NULL;
        boolean_t global = B_FALSE;
        size_t n;

        if (t[0] == 'g' && t[1] == 's') {
                global = B_TRUE;
                t += 2;
        }
        if (t == last)
                return (first);

        t2 = parse_base_unresolved_name(t, last, db);
        if (t != t2) {
                if (global) {
                        if (nempty(db))
                                return (first);

                        (void) str_insert(TOP_L(db), 0, "::", 2);
                }
                return (t2);
        }

        if (t[0] != 's' || t[1] != 'r' || last - t < 2)
                return (first);

        n = nlen(db);
        if (t[2] == 'N') {
                t += 3;
                t2 = parse_unresolved_type(t, last, db);
                if (t2 == t || t2 == last)
                        return (first);
                t = t2;

                t2 = parse_template_args(t, last, db);
                if (t2 != t) {
                        if (NAMT(db, n) < 2 || t2 == last)
                                return (first);

                        nfmt(db, "{1:L}{0}", "{1:R}");
                        t = t2;
                }

                VERIFY3U(NAMT(db, n), ==, 1);

                while (t[0] != 'E') {
                        size_t nn = nlen(db);
                        t2 = parse_unresolved_qualifier_level(t, last, db);
                        if (t == t2 || t == last || NAMT(db, nn) != 1)
                                return (first);

                        t = t2;
                }

                /* skip E */
                t++;

                t2 = parse_base_unresolved_name(t, last, db);
                if (t == t2 || NAMT(db, n) < 2)
                        return (first);

                njoin(db, NAMT(db, n), "::");
                return (t2);
        }

        t += 2;

        t2 = parse_unresolved_type(t, last, db);
        if (t != t2) {
                t = t2;
                t2 = parse_template_args(t, last, db);
                if (t2 != t)
                        nfmt(db, "{1:L}{0}", "{1:R}");
                t = t2;

                t2 = parse_base_unresolved_name(t, last, db);
                if (t == t2 || nlen(db) < 2)
                        return (first);

                nfmt(db, "{1:L}::{0}", "{1:R}");
                return (t2);
        }

        t2 = parse_unresolved_qualifier_level(t, last, db);
        if (t2 == t || t2 == last)
                return (first);

        t = t2;
        if (global && nlen(db) > 0)
                nfmt(db, "::{0:L}", "{0:R}");

        while (t[0] != 'E') {
                t2 = parse_unresolved_qualifier_level(t, last, db);
                if (t == t2 || t == last || nlen(db) < 2)
                        return (first);

                t = t2;
        }

        /* skip E */
        t++;

        t2 = parse_base_unresolved_name(t, last, db);
        if (t == t2 || nlen(db) < 2)
                return (first);

        njoin(db, NAMT(db, n), "::");
        return (t2);
}

/* <unresolved-qualifier-level> ::= <simple-id> */
static const char *
parse_unresolved_qualifier_level(const char *first, const char *last,
    cpp_db_t *db)
{
        VERIFY3P(first, <=, last);
        return (parse_simple_id(first, last, db));
}

/* BEGIN CSTYLED */
/*
 * <base-unresolved-name> ::= <simple-id>                                # unresolved name
 *          extension     ::= <operator-name>                            # unresolved operator-function-id
 *          extension     ::= <operator-name> <template-args>            # unresolved operator template-id
 *                        ::= on <operator-name>                         # unresolved operator-function-id
 *                        ::= on <operator-name> <template-args>         # unresolved operator template-id
 *                        ::= dn <destructor-name>                       # destructor or pseudo-destructor;
 *                                                                       # e.g. ~X or ~X<N-1>
 */
/* END CSTYLED */
static const char *
parse_base_unresolved_name(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2)
                return (first);

        const char *t = NULL;
        const char *t1 = NULL;

        if ((first[0] != 'o' && first[0] != 'd') || first[1] != 'n') {
                t = parse_simple_id(first, last, db);
                if (t != first)
                        return (t);

                t = parse_operator_name(first, last, db);
                if (t == first)
                        return (first);

                t1 = parse_template_args(t, last, db);
                if (t1 != t) {
                        if (nlen(db) < 2)
                                return (first);
                        nfmt(db, "{1:L}{0}", "{1:R}");
                }

                return (t1);
        }

        if (first[0] == 'd') {
                t = parse_destructor_name(first + 2, last, db);
                return ((t != first + 2) ? t : first);
        }

        t = parse_operator_name(first + 2, last, db);
        if (t == first + 2)
                return (first);

        t1 = parse_template_args(t, last, db);
        if (t1 != t)
                nfmt(db, "{1:L}{0}", "{1:R}");
        return (t1);
}

/*
 * <destructor-name> ::= <unresolved-type>      # e.g., ~T or ~decltype(f())
 *                   ::= <simple-id>            # e.g., ~A<2*N>
 */
static const char *
parse_destructor_name(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (first == last)
                return (first);

        const char *t = parse_unresolved_type(first, last, db);

        if (t == first)
                t = parse_simple_id(first, last, db);

        if (t == first)
                return (first);

        nfmt(db, "~{0:L}", "{0:R}");
        return (t);
}

/*
 *  <ref-qualifier> ::= R                   # & ref-qualifier
 *  <ref-qualifier> ::= O                   # && ref-qualifier
 *
 * <function-type> ::= F [Y] <bare-function-type> [<ref-qualifier>] E
 */
static const char *
parse_function_type(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2)
                return (first);

        VERIFY3U(first[0], ==, 'F');

        const char *t = first + 1;

        /* extern "C" */
        if (t[0] == 'Y')
                t++;

        const char *t1 = parse_type(t, last, db);
        if (t1 == t)
                return (first);

        size_t n = nlen(db);
        int ref_qual = 0;

        t = t1;

        while (t != last && t[0] != 'E') {
                if (t[0] == 'v') {
                        t++;
                        continue;
                }

                if (t[0] == 'R' && t + 1 != last && t[1] == 'E') {
                        ref_qual = 1;
                        t++;
                        continue;
                }

                if (t[0] == 'O' && t + 1 != last && t[1] == 'E') {
                        ref_qual = 2;
                        t++;
                        continue;
                }


                t1 = parse_type(t, last, db);
                if (t1 == t || t == last)
                        return (first);

                t = t1;
        }

        if (t == last)
                return (first);

        njoin(db, NAMT(db, n), ", ");
        nfmt(db, "({0})", NULL);

        switch (ref_qual) {
        case 1:
                nfmt(db, "{0} &", NULL);
                break;
        case 2:
                nfmt(db, "{0} &&", NULL);
                break;
        }

        nfmt(db, "{1:L} ", "{0}{1:R}");

        /* skip E */
        return (t + 1);
}

/*
 * <template-param> ::= T_    # first template parameter
 *                  ::= T <parameter-2 non-negative number> _
 */
static const char *
parse_template_param(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2 || first[0] != 'T')
                return (first);

        const char *t = first + 1;
        size_t idx = 0;

        while (t != last && t[0] != '_') {
                if (!ISDIGIT(t[0]))
                        return (first);

                idx *= 10;
                idx += t[0] - '0';
                t++;
        }

        if (t == last)
                return (first);

        VERIFY3U(t[0], ==, '_');

        /*
         * T_ -> idx 0
         * T0 -> idx 1
         * T1 -> idx 2
         * ...
         */
        if (first[1] != '_')
                idx++;

        /* skip _ */
        t++;

        if (tempty(db))
                return (first);

        if (idx >= ttlen(db)) {
                nadd_l(db, first, (size_t)(t - first));
                db->cpp_fix_forward_references = B_TRUE;
                return (t);
        }

        tsub(db, idx);
        return (t);
}

/*
 * <template-args> ::= I <template-arg>* E
 *     extension, the abi says <template-arg>+
 */
static const char *
parse_template_args(const char *first, const char *last, cpp_db_t *db)
{
        VERIFY3P(first, <=, last);

        if (last - first < 2 || first[0] != 'I')
                return (first);

        if (db->cpp_tag_templates)
                sub_clear(templ_top(&db->cpp_templ));

        const char *t = first + 1;
        size_t n = nlen(db);

        while (t[0] != 'E') {
                if (db->cpp_tag_templates)
                        tpush(db);

                size_t n1 = nlen(db);
                const char *t1 = parse_template_arg(t, last, db);

                if (db->cpp_tag_templates)
                        tpop(db);

                if (t1 == t || t == last)
                        return (first);

                if (db->cpp_tag_templates)
                        tsave(db, NAMT(db, n1));

                t = t1;
        }

        /*
         * ugly, but if the last thing pushed was an empty string,
         * get rid of it so we dont get "<..., >"
         */
        if (NAMT(db, n) > 1 &&
            str_pair_len(name_top(&db->cpp_name)) == 0)
                name_pop(&db->cpp_name, NULL);

        njoin(db, NAMT(db, n), ", ");

        VERIFY3U(nlen(db), >, 0);

        /* make sure we don't bitshift ourselves into oblivion */
        str_t *top = TOP_L(db);
        if (str_length(top) > 0 &&
            top->str_s[top->str_len - 1] == '>')
                nfmt(db, "<{0} >", NULL);
        else
                nfmt(db, "<{0}>", NULL);

        /* skip E */
        return (t + 1);
}

/*
 * <discriminator> := _ <non-negative number>      # when number < 10
 *                 := __ <non-negative number> _   # when number >= 10
 *  extension      := decimal-digit+               # at the end of string
 */
static const char *
parse_discriminator(const char *first, const char *last)
{
        VERIFY3P(first, <=, last);

        const char *t = NULL;

        if (first == last)
                return (first);

        if (ISDIGIT(first[0])) {
                for (t = first; t != last && ISDIGIT(t[0]); t++)
                        ;

                /* not at the end of the string */
                if (t != last)
                        return (first);

                return (t);
        } else if (first[0] != '_' || first + 1 == last) {
                return (first);
        }

        t = first + 1;
        if (ISDIGIT(t[0]))
                return (t + 1);

        if (t[0] != '_' || t + 1 == last)
                return (first);

        for (t++; t != last && ISDIGIT(t[0]); t++)
                ;
        if (t == last || t[0] != '_')
                return (first);

        return (t);
}

/* <CV-qualifiers> ::= [r] [V] [K] */
const char *
parse_cv_qualifiers(const char *first, const char *last, unsigned *cv)
{
        VERIFY3P(first, <=, last);

        if (first == last)
                return (first);

        *cv = 0;
        if (first[0] == 'r') {
                *cv |= CPP_QUAL_RESTRICT;
                first++;
        }
        if (first != last && first[0] == 'V') {
                *cv |= CPP_QUAL_VOLATILE;
                first++;
        }
        if (first != last && first[0] == 'K') {
                *cv |= CPP_QUAL_CONST;
                first++;
        }

        return (first);
}

/*
 * <number> ::= [n] <non-negative decimal integer>
 */
static const char *
parse_number(const char *first, const char *last)
{
        VERIFY3P(first, <=, last);

        const char *t = first;

        if (first == last || (first[0] != 'n' && !ISDIGIT(first[0])))
                return (first);

        if (t[0] == 'n')
                t++;

        if (t[0] == '0')
                return (t + 1);

        while (ISDIGIT(t[0]))
                t++;

        return (t);
}

/*
 * Like isxdigit(3C), except we can only accept lower case letters as
 * that's only what is allowed when [de]mangling floating point constants into
 * their hex representation.
 */
static inline boolean_t
is_xdigit(int c)
{
        if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'f'))
                return (B_TRUE);
        return (B_FALSE);
}

static boolean_t
nempty(cpp_db_t *db)
{
        return (name_empty(&db->cpp_name));
}

static size_t
nlen(cpp_db_t *db)
{
        return (name_len(&db->cpp_name));
}

static void
nadd_l(cpp_db_t *db, const char *s, size_t len)
{
        CK(name_add(&db->cpp_name, s, len, NULL, 0));
}

static void
njoin(cpp_db_t *db, size_t amt, const char *sep)
{
        name_t *nm = &db->cpp_name;

        CK(name_join(nm, amt, sep));
}

static void
nfmt(cpp_db_t *db, const char *fmt_l, const char *fmt_r)
{
        CK(name_fmt(&db->cpp_name, fmt_l, fmt_r));
}

static void
save_top(cpp_db_t *db, size_t amt)
{
        CK(sub_save(&db->cpp_subs, &db->cpp_name, amt));
}

static void
sub(cpp_db_t *db, size_t n)
{
        CK(sub_substitute(&db->cpp_subs, n, &db->cpp_name));
}

static boolean_t
tempty(const cpp_db_t *db)
{
        return (templ_empty(&db->cpp_templ) ? B_TRUE : B_FALSE);
}

static size_t
ttlen(const cpp_db_t *db)
{
        return (templ_top_len(&db->cpp_templ));
}

static void
tsub(cpp_db_t *db, size_t n)
{
        CK(templ_sub(&db->cpp_templ, n, &db->cpp_name));
}

static void
tpush(cpp_db_t *db)
{
        CK(templ_push(&db->cpp_templ));
}

static void
tpop(cpp_db_t *db)
{
        templ_pop(&db->cpp_templ);
}

static void
tsave(cpp_db_t *db, size_t amt)
{
        CK(templ_save(&db->cpp_name, amt, &db->cpp_templ));
}

static void
db_init(cpp_db_t *db, sysdem_ops_t *ops)
{
        (void) memset(db, 0, sizeof (*db));
        db->cpp_ops = ops;
        name_init(&db->cpp_name, ops);
        sub_init(&db->cpp_subs, ops);
        templ_init(&db->cpp_templ, ops);
        db->cpp_tag_templates = B_TRUE;
        db->cpp_try_to_parse_template_args = B_TRUE;
        tpush(db);
}

static void
db_fini(cpp_db_t *db)
{
        name_fini(&db->cpp_name);
        sub_fini(&db->cpp_subs);
        templ_fini(&db->cpp_templ);
        (void) memset(db, 0, sizeof (*db));
}

static void
print_sp(const str_pair_t *sp, FILE *out)
{
        (void) fprintf(out, "{%.*s#%.*s}",
            (int)sp->strp_l.str_len, sp->strp_l.str_s,
            (int)sp->strp_r.str_len, sp->strp_r.str_s);
}

static void
print_name(const name_t *n, FILE *out)
{
        const str_pair_t *sp;
        size_t i;

        (void) fprintf(out, "Name:\n");

        if (name_len(n) == 0)
                return;

        sp = name_top((name_t *)n);

        for (i = 0; i < n->nm_len; i++, sp--) {
                (void) fprintf(out, "  [%02zu] ", i);
                print_sp(sp, out);
                (void) fputc('\n', out);
        }

        (void) fputc('\n', out);
}

/* Print a base-36 number (for substitutions) */
static char *
base36(char *buf, size_t val)
{
        char tmp[16] = { 0 };
        char *p = tmp;

        if (val == 0) {
                buf[0] = '0';
                buf[1] = '\0';
                return (buf);
        }

        while (val > 0) {
                size_t r = val % 36;

                if (r < 10)
                        *p++ = r + '0';
                else
                        *p++ = r - 10 + 'A';

                val /= 36;
        }

        char *q = buf;
        while (--p >= tmp)
                *q++ = *p;

        return (buf);
}

static void
print_sub(const sub_t *sub, FILE *out)
{
        const name_t *n = sub->sub_items;

        (void) fprintf(out, "Substitutions:\n");

        if (sub->sub_len == 0)
                return;

        for (size_t i = 0; i < sub->sub_len; i++, n++) {
                (void) printf("  ");
                if (i == 0) {
                        (void) fprintf(out, "%-4s", "S_");
                } else {
                        char buf[16] = { 0 };
                        char buf2[16] = { 0 };

                        (void) snprintf(buf, sizeof (buf), "S%s_",
                            base36(buf2, i));
                        (void) fprintf(out, "%-4s", buf);
                }
                (void) fprintf(out, " = ");

                (void) fputc('{', out);
                for (size_t j = 0; j < n->nm_len; j++) {
                        if (j > 0)
                                (void) fputc(' ', out);
                        print_sp(&n->nm_items[j], out);
                }
                (void) fputc('}', out);

                (void) fputc('\n', out);
        }
        (void) fputc('\n', out);
}

static void
print_templ(const templ_t *tpl, FILE *out)
{

        (void) fprintf(out, "Template\n");

        const sub_t *s = templ_top((templ_t *)tpl);

        for (size_t i = 0; i < s->sub_len; i++) {
                char buf[16] = { 0 };

                if (i == 0)
                        (void) snprintf(buf, sizeof (buf), "%s", "T_");
                else
                        (void) snprintf(buf, sizeof (buf), "T%zu_", i - 1);

                (void) fprintf(out, "  %-4s = ", buf);

                (void) fputc('{', out);

                const name_t *n = &s->sub_items[i];
                for (size_t j = 0; j < n->nm_len; j++) {
                        const str_pair_t *sp = &n->nm_items[j];

                        if (j > 0)
                                (void) fputc(' ', out);

                        (void) fprintf(out, "{%.*s#%.*s}",
                            (int)sp->strp_l.str_len, sp->strp_l.str_s,
                            (int)sp->strp_r.str_len, sp->strp_r.str_s);
                }
                (void) fprintf(out, "}\n");
        }
        (void) fprintf(out, "\n");
}

static void
dump(cpp_db_t *db, FILE *out)
{
        print_name(&db->cpp_name, out);
        print_sub(&db->cpp_subs, out);
        print_templ(&db->cpp_templ, out);
}