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