1 /*
2  * This file and its contents are supplied under the terms of the
3  * Common Development and Distribution License ("CDDL"), version 1.0.
4  * You may only use this file in accordance with the terms of version
5  * 1.0 of the CDDL.
6  *
7  * A full copy of the text of the CDDL should have accompanied this
8  * source.  A copy of the CDDL is also available via the Internet at
9  * http://www.illumos.org/license/CDDL.
10  */
11 
12 /*
13  * Copyright 2017 Jason King
14  */
15 
16 #include <sys/debug.h>
17 #include <sys/sysmacros.h>
18 #include <string.h>
19 #include <errno.h>
20 #include <stdlib.h>
21 #include "demangle_int.h"
22 #include "cxx.h"
23 
24 #define	CHUNK_SIZE  (8U)
25 
26 /*
27  * A name_t is essentially a stack of str_pair_t's.  Generally, the parsing
28  * code will push (via name_add() or the like) portions of the demangled
29  * name into a name_t, and periodically combine them via name_join().
30  *
31  * As such it should be noted that since items are added at the end of
32  * name_t->nm_items, the numbering of name_at() starts at the end
33  * of name_t->nm_items, i.e. name_at(n, 0) == &n->nm_items[n->nm_len - 1].
34  *
35  * It should also be noted that for name_t's, adding is a move operation in
36  * that it takes ownership of the passed in string/str_t/etc
37  */
38 
39 void
40 name_init(name_t *n, sysdem_ops_t *ops)
41 {
42 	(void) memset(n, 0, sizeof (*n));
43 	n->nm_ops = (ops != NULL) ? ops : sysdem_ops_default;
44 }
45 
46 void
47 name_fini(name_t *n)
48 {
49 	if (n == NULL)
50 		return;
51 
52 	name_clear(n);
53 	xfree(n->nm_ops, n->nm_items, n->nm_size);
54 	n->nm_items = NULL;
55 	n->nm_size = 0;
56 }
57 
58 size_t
59 name_len(const name_t *n)
60 {
61 	return (n->nm_len);
62 }
63 
64 boolean_t
65 name_empty(const name_t *n)
66 {
67 	return (name_len(n) == 0 ? B_TRUE : B_FALSE);
68 }
69 
70 void
71 name_clear(name_t *n)
72 {
73 	if (n == NULL)
74 		return;
75 
76 	for (size_t i = 0; i < n->nm_len; i++) {
77 		str_pair_t *sp = &n->nm_items[i];
78 		sysdem_ops_t *ops = sp->strp_l.str_ops;
79 
80 		str_pair_fini(sp);
81 		(void) str_pair_init(sp, ops);
82 	}
83 
84 	n->nm_len = 0;
85 }
86 
87 static boolean_t
88 name_reserve(name_t *n, size_t amt)
89 {
90 	size_t newlen = n->nm_len + amt;
91 
92 	if (newlen == cpp_name_max_depth) {
93 		errno = ENAMETOOLONG;
94 		return (B_FALSE);
95 	}
96 
97 	if (newlen < n->nm_size)
98 		return (B_TRUE);
99 
100 	size_t newsize = roundup(newlen, CHUNK_SIZE);
101 	if (newsize > cpp_name_max_depth)
102 		newsize = cpp_name_max_depth;
103 
104 	void *temp = xrealloc(n->nm_ops, n->nm_items,
105 	    n->nm_size * sizeof (str_pair_t), newsize * sizeof (str_pair_t));
106 
107 	if (temp == NULL)
108 		return (B_FALSE);
109 
110 	n->nm_items = temp;
111 	n->nm_size = newsize;
112 	return (B_TRUE);
113 }
114 
115 boolean_t
116 name_add(name_t *n, const char *l, size_t l_len, const char *r, size_t r_len)
117 {
118 	str_t sl = { 0 };
119 	str_t sr = { 0 };
120 
121 	str_init(&sl, n->nm_ops);
122 	str_init(&sr, n->nm_ops);
123 	str_set(&sl, l, l_len);
124 	str_set(&sr, r, r_len);
125 	return (name_add_str(n, &sl, &sr));
126 }
127 
128 boolean_t
129 name_add_str(name_t *n, str_t *l, str_t *r)
130 {
131 	str_pair_t sp;
132 
133 	(void) str_pair_init(&sp, n->nm_ops);
134 
135 	if (!name_reserve(n, 1))
136 		return (B_FALSE);
137 
138 	if (l != NULL) {
139 		sp.strp_l = *l;
140 		(void) memset(l, 0, sizeof (*l));
141 	}
142 
143 	if (r != NULL) {
144 		sp.strp_r = *r;
145 		(void) memset(r, 0, sizeof (*r));
146 	}
147 
148 	n->nm_items[n->nm_len++] = sp;
149 
150 	return (B_TRUE);
151 }
152 
153 str_pair_t *
154 name_at(const name_t *n, size_t idx)
155 {
156 	VERIFY(!name_empty(n));
157 	VERIFY3U(idx, <, n->nm_len);
158 	return (&n->nm_items[n->nm_len - idx - 1]);
159 }
160 
161 str_pair_t *
162 name_top(name_t *n)
163 {
164 	return (name_at(n, 0));
165 }
166 
167 void
168 name_pop(name_t *n, str_pair_t *sp)
169 {
170 	if (n->nm_len == 0)
171 		return;
172 
173 	str_pair_t *top = name_top(n);
174 
175 	if (sp != NULL) {
176 		*sp = *top;
177 		(void) memset(top, 0, sizeof (*top));
178 	} else {
179 		str_pair_fini(top);
180 	}
181 
182 	n->nm_len--;
183 }
184 
185 boolean_t
186 name_join(name_t *n, size_t amt, const char *sep)
187 {
188 	str_pair_t *sp = NULL;
189 	str_t res = { 0 };
190 	size_t seplen = strlen(sep);
191 
192 	VERIFY3U(amt, <=, n->nm_len);
193 
194 	/*
195 	 * A join of 0 elements places an empty string on the stack.  This
196 	 * simplifies code that wants to do things like:
197 	 *   name_join(...); name_fmt(.., "({0})", ...)
198 	 */
199 	if (amt == 0) {
200 		(void) name_add(n, "", 0, "", 0);
201 		return (B_TRUE);
202 	}
203 
204 	/* A join of 1 element just implies merging the top str_pair_t */
205 	if (amt == 1) {
206 		VERIFY3U(name_len(n), >, 0);
207 		return (str_pair_merge(name_top(n)));
208 	}
209 
210 	(void) str_init(&res, n->nm_ops);
211 
212 	sp = name_at(n, amt - 1);
213 	for (size_t i = 0; i < amt; i++) {
214 		if (i > 0) {
215 			if (!str_append(&res, sep, seplen))
216 				goto error;
217 		}
218 
219 		if (!str_append_str(&res, &sp->strp_l))
220 			goto error;
221 		if (!str_append_str(&res, &sp->strp_r))
222 			goto error;
223 
224 		sp++;
225 	}
226 
227 	for (size_t i = 0; i < amt; i++)
228 		name_pop(n, NULL);
229 
230 	/* since we've removed at least 1 entry, this should always succeed */
231 	VERIFY(name_add_str(n, &res, NULL));
232 	return (B_TRUE);
233 
234 error:
235 	str_fini(&res);
236 	return (B_FALSE);
237 }
238 
239 static boolean_t
240 name_fmt_s(name_t *n, str_t *s, const char *fmt, long *maxp)
241 {
242 	const char *p;
243 	long max = -1;
244 
245 	if (fmt == NULL)
246 		return (B_TRUE);
247 
248 	for (p = fmt; *p != '\0'; p++) {
249 		if (*p != '{') {
250 			(void) str_append_c(s, *p);
251 			continue;
252 		}
253 
254 		errno = 0;
255 		char *q = NULL;
256 		long val = strtol(p + 1, &q, 10);
257 
258 		VERIFY(val != 0 || errno == 0);
259 		VERIFY3U(val, <, n->nm_len);
260 
261 		str_pair_t *sp = name_at(n, val);
262 
263 		if (val > max)
264 			max = val;
265 
266 		switch (q[0]) {
267 		case '}':
268 			if (!str_append_str(s, &sp->strp_l))
269 				return (B_FALSE);
270 			if (!str_append_str(s, &sp->strp_r))
271 				return (B_FALSE);
272 			p = q;
273 			continue;
274 		case ':':
275 			switch (q[1]) {
276 			case 'L':
277 				if (!str_append_str(s, &sp->strp_l))
278 					return (B_FALSE);
279 				break;
280 			case 'R':
281 				if (!str_append_str(s, &sp->strp_r))
282 					return (B_FALSE);
283 				break;
284 			}
285 
286 			p = q + 2;
287 			VERIFY(*p == '}');
288 			break;
289 		}
290 	}
291 
292 	if (*maxp < max)
293 		*maxp = max;
294 
295 	return (B_TRUE);
296 }
297 
298 /*
299  * Replace a number of elements in the name stack with a formatted string
300  * for format is a plain string with optional {nnn} or {nnn:L|R} substitutions
301  * where nnn is the stack position of an element and it's contents (both
302  * left and right pieces) are inserted.  Optionally, only the left or
303  * right piece can specified using :L|R e.g. {2:L}{3}{2:R} would insert
304  * the left piece of element 2, all of element 3, then the right piece of
305  * element 2.
306  *
307  * Once complete, all elements up to the deepest one references are popped
308  * off the stack, and the resulting formatted string is pushed into n.
309  *
310  * This could be done as a sequence of push & pops, but this makes the
311  * intended output far clearer to see.
312  */
313 boolean_t
314 name_fmt(name_t *n, const char *fmt_l, const char *fmt_r)
315 {
316 	str_pair_t res;
317 	long max = -1;
318 
319 	(void) str_pair_init(&res, n->nm_ops);
320 
321 	if (!name_reserve(n, 1))
322 		return (B_FALSE);
323 
324 	if (!name_fmt_s(n, &res.strp_l, fmt_l, &max))
325 		goto error;
326 	if (!name_fmt_s(n, &res.strp_r, fmt_r, &max))
327 		goto error;
328 
329 	if (max >= 0) {
330 		for (size_t i = 0; i <= max; i++)
331 			name_pop(n, NULL);
332 	}
333 
334 	n->nm_items[n->nm_len++] = res;
335 	return (B_TRUE);
336 
337 error:
338 	str_pair_fini(&res);
339 	return (B_FALSE);
340 }
341 
342 /*
343  * The substitution list is a list of name_t's that get added as the
344  * demangled name is parsed.  Adding a name_t to the substitution list
345  * is a copy operation, and likewise inserting a substitution into a name_t
346  * is also a copy operation.
347  */
348 void
349 sub_init(sub_t *sub, sysdem_ops_t *ops)
350 {
351 	(void) memset(sub, 0, sizeof (*sub));
352 	sub->sub_ops = (ops != NULL) ? ops : sysdem_ops_default;
353 }
354 
355 void
356 sub_fini(sub_t *sub)
357 {
358 	if (sub == NULL)
359 		return;
360 
361 	sub_clear(sub);
362 	xfree(sub->sub_ops, sub->sub_items, sub->sub_size);
363 	sub->sub_items = NULL;
364 	sub->sub_size = 0;
365 }
366 
367 void
368 sub_clear(sub_t *sub)
369 {
370 	if (sub == NULL)
371 		return;
372 
373 	for (size_t i = 0; i < sub->sub_len; i++)
374 		name_fini(&sub->sub_items[i]);
375 
376 	sub->sub_len = 0;
377 }
378 
379 boolean_t
380 sub_empty(const sub_t *sub)
381 {
382 	return ((sub->sub_len == 0) ? B_TRUE : B_FALSE);
383 }
384 
385 size_t
386 sub_len(const sub_t *sub)
387 {
388 	return (sub->sub_len);
389 }
390 
391 static boolean_t
392 sub_reserve(sub_t *sub, size_t amt)
393 {
394 	if (sub->sub_len + amt < sub->sub_size)
395 		return (B_TRUE);
396 
397 	size_t newsize = roundup(sub->sub_size + amt, CHUNK_SIZE);
398 	void *temp = xrealloc(sub->sub_ops, sub->sub_items,
399 	    sub->sub_size * sizeof (name_t), newsize * sizeof (name_t));
400 
401 	if (temp == NULL)
402 		return (B_FALSE);
403 
404 	sub->sub_items = temp;
405 	sub->sub_size = newsize;
406 
407 	return (B_TRUE);
408 }
409 
410 /* save the element of n (up to depth elements deep) as a substitution */
411 boolean_t
412 sub_save(sub_t *sub, const name_t *n, size_t depth)
413 {
414 	if (depth == 0)
415 		return (B_TRUE);
416 
417 	if (!sub_reserve(sub, 1))
418 		return (B_FALSE);
419 
420 	name_t *dest = &sub->sub_items[sub->sub_len++];
421 	name_init(dest, sub->sub_ops);
422 
423 	if (!name_reserve(dest, depth)) {
424 		name_fini(dest);
425 		sub->sub_len--;
426 		return (B_FALSE);
427 	}
428 
429 	const str_pair_t *src_sp = name_at(n, depth - 1);
430 
431 	for (size_t i = 0; i < depth; i++, src_sp++) {
432 		str_pair_t copy = { 0 };
433 		(void) str_pair_init(&copy, n->nm_ops);
434 		if (!str_pair_copy(src_sp, &copy)) {
435 			str_pair_fini(&copy);
436 			name_fini(dest);
437 			return (B_FALSE);
438 		}
439 
440 		VERIFY(name_add_str(dest, &copy.strp_l, &copy.strp_r));
441 	}
442 
443 	return (B_TRUE);
444 }
445 
446 /* push substitution idx onto n */
447 boolean_t
448 sub_substitute(const sub_t *sub, size_t idx, name_t *n)
449 {
450 	VERIFY3U(idx, <, sub->sub_len);
451 
452 	const name_t *src = &sub->sub_items[idx];
453 	const str_pair_t *sp = src->nm_items;
454 	size_t save = name_len(n);
455 
456 	for (size_t i = 0; i < src->nm_len; i++, sp++) {
457 		str_pair_t copy = { 0 };
458 
459 		if (!str_pair_copy(sp, &copy))
460 			goto fail;
461 
462 		if (!name_add_str(n, &copy.strp_l, &copy.strp_r))
463 			goto fail;
464 	}
465 
466 	return (B_TRUE);
467 
468 fail:
469 	for (size_t i = 0; i < name_len(n) - save; i++)
470 		name_pop(n, NULL);
471 	return (B_FALSE);
472 }
473 
474 void
475 sub_pop(sub_t *sub)
476 {
477 	name_t *top = &sub->sub_items[--sub->sub_len];
478 	name_fini(top);
479 }
480 
481 /*
482  * Templates can use substitutions for it's arguments (using T instead of
483  * S).  Since templates can nest however, each nesting requires a new
484  * set of substitutions.  As such a new, empty list of template substitutions
485  * is pushed onto cpp_templ each time templates are nested, and popped at
486  * the end of the current template argument list.
487  */
488 static boolean_t
489 templ_reserve(templ_t *tpl, size_t n)
490 {
491 	if (tpl->tpl_len + n < tpl->tpl_size)
492 		return (B_TRUE);
493 
494 	size_t newsize = tpl->tpl_size + CHUNK_SIZE;
495 	void *temp = xrealloc(tpl->tpl_ops, tpl->tpl_items,
496 	    tpl->tpl_size * sizeof (sub_t), newsize * sizeof (sub_t));
497 
498 	if (temp == NULL)
499 		return (B_FALSE);
500 
501 	tpl->tpl_items = temp;
502 	tpl->tpl_size = newsize;
503 	return (B_TRUE);
504 }
505 
506 void
507 templ_init(templ_t *tpl, sysdem_ops_t *ops)
508 {
509 	(void) memset(tpl, 0, sizeof (*tpl));
510 	tpl->tpl_ops = ops;
511 }
512 
513 void
514 templ_fini(templ_t *tpl)
515 {
516 	if (tpl == NULL)
517 		return;
518 
519 	for (size_t i = 0; i < tpl->tpl_len; i++)
520 		sub_fini(&tpl->tpl_items[i]);
521 
522 	xfree(tpl->tpl_ops, tpl->tpl_items, tpl->tpl_size * sizeof (sub_t));
523 	sysdem_ops_t *ops = tpl->tpl_ops;
524 	(void) memset(tpl, 0, sizeof (*tpl));
525 	tpl->tpl_ops = ops;
526 }
527 
528 boolean_t
529 templ_push(templ_t *tpl)
530 {
531 	if (!templ_reserve(tpl, 1))
532 		return (B_FALSE);
533 
534 	sub_t *sub = &tpl->tpl_items[tpl->tpl_len++];
535 	sub_init(sub, tpl->tpl_ops);
536 	return (B_TRUE);
537 }
538 
539 void
540 templ_pop(templ_t *tpl)
541 {
542 	VERIFY(!templ_empty(tpl));
543 
544 	sub_t *sub = &tpl->tpl_items[--tpl->tpl_len];
545 	sub_fini(sub);
546 }
547 
548 sub_t *
549 templ_top(templ_t *tpl)
550 {
551 	if (tpl->tpl_len == 0)
552 		return (NULL);
553 	return (&tpl->tpl_items[tpl->tpl_len - 1]);
554 }
555 
556 boolean_t
557 templ_empty(const templ_t *tpl)
558 {
559 	return ((tpl->tpl_len == 0) ? B_TRUE : B_FALSE);
560 }
561 
562 size_t
563 templ_top_len(const templ_t *tpl)
564 {
565 	const sub_t *sub = templ_top((templ_t *)tpl);
566 
567 	return (sub->sub_len);
568 }
569 
570 boolean_t
571 templ_sub(const templ_t *tpl, size_t idx, name_t *n)
572 {
573 	const sub_t *sub = templ_top((templ_t *)tpl);
574 
575 	return (sub_substitute(sub, idx, n));
576 }
577 
578 boolean_t
579 templ_save(const name_t *n, size_t amt, templ_t *tpl)
580 {
581 	VERIFY3U(tpl->tpl_len, >, 0);
582 
583 	sub_t *s = templ_top(tpl);
584 	boolean_t res = B_TRUE;
585 
586 	/* a bit of a hack -- want an 'empty' entry when saving 0 params */
587 	if (amt == 0) {
588 		name_t name = { 0 };
589 
590 		name_init(&name, tpl->tpl_ops);
591 		res &= name_add(&name, "", 0, "", 0);
592 		if (res)
593 			res &= sub_save(s, &name, 1);
594 		name_fini(&name);
595 	} else {
596 		res &= sub_save(s, n, amt);
597 	}
598 
599 	return (res);
600 }
601