usr/src/lib/libdemangle/common/cxx.c

/*
 * 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 2018 Jason King.
 */
#include <ctype.h>
#include <errno.h>
#include <locale.h>
#include <note.h>
#include <string.h>
#include <setjmp.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/isa_defs.h>
#include <sys/debug.h>
#include "demangle-sys.h"
#include "demangle_int.h"
#include "cxx.h"

#ifndef	ARRAY_SIZE
#define	ARRAY_SIZE(x) (sizeof (x) / sizeof (x[0]))
#endif

#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;
	locale_t	cpp_loc;
} 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 boolean_t 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 *, locale_t);
static const char *parse_number(const char *, const char *, locale_t);
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 *, locale_t);
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, sysdem_ops_t *ops)
{
	char *result = NULL;
	cpp_db_t db;
	size_t srclen = strlen(src);

	if (!db_init(&db, ops))
		goto done;
	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);
		result = zalloc(ops, s->str_len + 1);
		if (result == NULL)
			goto done;

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

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_l(t[1], db->cpp_loc))
			return (first);
		t += 2;
	}

	while (t < last && isdigit_l(t[0], db->cpp_loc))
		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, db->cpp_loc);
			if (t1 == t)
				return (first);
			t = parse_call_offset(t1, last, db->cpp_loc);
			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, db->cpp_loc);
			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, db->cpp_loc);
			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, locale_t loc)
{
	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, loc);
	if (t == first + 1 || t == last || t[0] != '_')
		return (first);

	/* skip _ */
	t++;

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

	t1 = parse_number(t, last, loc);
	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, db->cpp_loc));
	}

	if (t[0] == 'd') {
		t1 = parse_number(t + 1, last, db->cpp_loc);
		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, db->cpp_loc);

	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, db->cpp_loc);
		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, db->cpp_loc);
	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_l(t1[0], db->cpp_loc))
			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] != '_') {
		if (!isdigit_l(*t2++, db->cpp_loc))
			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",