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(©, n->nm_ops);
434 if (!str_pair_copy(src_sp, ©)) {
435 str_pair_fini(©);
436 name_fini(dest);
437 return (B_FALSE);
438 }
439
440 VERIFY(name_add_str(dest, ©.strp_l, ©.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, ©))
460 goto fail;
461
462 if (!name_add_str(n, ©.strp_l, ©.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 }