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