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 "sysdemangle_int.h"
22 #include "cpp.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 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 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(name_t *n, size_t idx)
155 {
156 if (n->nm_len == 0)
157 return (NULL);
158
159 ASSERT3U(idx, <=, n->nm_len);
160 return (&n->nm_items[n->nm_len - idx - 1]);
161 }
162
163 str_pair_t *
164 name_top(name_t *n)
165 {
166 return (name_at(n, 0));
167 }
168
169 str_pair_t *
170 name_pop(name_t *n, str_pair_t *sp)
171 {
172 if (n->nm_len == 0)
173 return (NULL);
174
175 str_pair_t *top = name_top(n);
176
177 if (sp != NULL) {
178 *sp = *top;
179 (void) memset(top, 0, sizeof (*top));
180 } else {
181 str_pair_fini(top);
182 }
183
184 n->nm_len--;
185 return (sp);
186 }
187
188 boolean_t
189 name_join(name_t *n, size_t amt, const char *sep)
190 {
191 str_pair_t *sp = NULL;
192 str_t res = { 0 };
193 size_t seplen = strlen(sep);
194
195 ASSERT3U(amt, <=, n->nm_len);
196
197 /*
198 * A join of 0 elements places an empty string on the stack. This
199 * simplifies code that wants to do things like:
200 * name_join(...); name_fmt(.., "({0})", ...)
201 */
202 if (amt == 0) {
203 name_add(n, "", 0, "", 0);
204 return (B_TRUE);
205 }
206
207 /* A join of 1 element just implies merging the top str_pair_t */
208 if (amt == 1) {
209 ASSERT3U(name_len(n), >, 0);
210 return (str_pair_merge(name_top(n)));
211 }
212
213 (void) str_init(&res, n->nm_ops);
214
215 sp = name_at(n, amt - 1);
216 for (size_t i = 0; i < amt; i++) {
217 if (i > 0) {
218 if (!str_append(&res, sep, seplen))
219 goto error;
220 }
221
222 if (!str_append_str(&res, &sp->strp_l))
223 goto error;
224 if (!str_append_str(&res, &sp->strp_r))
225 goto error;
226
227 sp++;
228 }
229
230 for (size_t i = 0; i < amt; i++)
231 (void) name_pop(n, NULL);
232
233 /* since we've removed at least 1 entry, this should always succeed */
234 VERIFY(name_add_str(n, &res, NULL));
235 return (B_TRUE);
236
237 error:
238 str_fini(&res);
239 return (B_FALSE);
240 }
241
242 static boolean_t
243 name_fmt_s(name_t *n, str_t *s, const char *fmt, long *maxp)
244 {
245 const char *p;
246 long max = -1;
247
248 if (fmt == NULL)
249 return (B_TRUE);
250
251 for (p = fmt; *p != '\0'; p++) {
252 if (*p != '{') {
253 str_append_c(s, *p);
254 continue;
255 }
256
257 errno = 0;
258 char *q = NULL;
259 long val = strtol(p + 1, &q, 10);
260
261 ASSERT(val != 0 || errno == 0);
262 ASSERT3U(val, <, n->nm_len);
263
264 str_pair_t *sp = name_at(n, val);
265
266 if (val > max)
267 max = val;
268
269 switch (q[0]) {
270 case '}':
271 if (!str_append_str(s, &sp->strp_l))
272 return (B_FALSE);
273 if (!str_append_str(s, &sp->strp_r))
274 return (B_FALSE);
275 p = q;
276 continue;
277 case ':':
278 switch (q[1]) {
279 case 'L':
280 if (!str_append_str(s, &sp->strp_l))
281 return (B_FALSE);
282 break;
283 case 'R':
284 if (!str_append_str(s, &sp->strp_r))
285 return (B_FALSE);
286 break;
287 }
288
289 p = q + 2;
290 VERIFY(*p == '}');
291 break;
292 }
293 }
294
295 if (*maxp < max)
296 *maxp = max;
297
298 return (B_TRUE);
299 }
300
301 /*
302 * replace a number of elements in the name stack with a formatted string
303 * for format is a plain string with optional {nnn} or {nnn:L|R} substitutions
304 * where nnn is the stack position of an element and it's contents (both
305 * left and right pieces) are inserted. Optionally, only the left or
306 * right piece can specified using :L|R e.g. {2:L}{3}{2:R} would insert
307 * the left piece of element 2, all of element 3, then the right piece of
308 * element 2.
309 *
310 * Once complete, all elements up to the deepest one references are popped
311 * off the stack, and the resulting formatted string is pushed into n.
312 *
313 * This could be done as a sequence of push & pops, but this makes the
314 * intended output far clearer to see.
315 */
316 boolean_t
317 name_fmt(name_t *n, const char *fmt_l, const char *fmt_r)
318 {
319 str_pair_t res;
320 long max = -1;
321
322 (void) str_pair_init(&res, n->nm_ops);
323
324 if (!name_reserve(n, 1))
325 return (B_FALSE);
326
327 if (!name_fmt_s(n, &res.strp_l, fmt_l, &max))
328 goto error;
329 if (!name_fmt_s(n, &res.strp_r, fmt_r, &max))
330 goto error;
331
332 if (max >= 0) {
333 for (size_t i = 0; i <= max; i++)
334 (void) name_pop(n, NULL);
335 }
336
337 n->nm_items[n->nm_len++] = res;
338 return (B_TRUE);
339
340 error:
341 str_pair_fini(&res);
342 return (B_FALSE);
343 }
344
345 /*
346 * The substitution list is a list of name_t's that get added as the
347 * demangled name is parsed. Adding a name_t to the substitution list
348 * is a copy operation, and likewise inserting a substitution into a name_t
349 * is also a copy operation.
350 */
351 void
352 sub_init(sub_t *sub, sysdem_ops_t *ops)
353 {
354 (void) memset(sub, 0, sizeof (*sub));
355 sub->sub_ops = (ops != NULL) ? ops : sysdem_ops_default;
356 }
357
358 void
359 sub_fini(sub_t *sub)
360 {
361 if (sub == NULL)
362 return;
363
364 sub_clear(sub);
365 xfree(sub->sub_ops, sub->sub_items, sub->sub_size);
366 sub->sub_items = NULL;
367 sub->sub_size = 0;
368 }
369
370 void
371 sub_clear(sub_t *sub)
372 {
373 if (sub == NULL)
374 return;
375
376 for (size_t i = 0; i < sub->sub_len; i++)
377 name_fini(&sub->sub_items[i]);
378
379 sub->sub_len = 0;
380 }
381
382 boolean_t
383 sub_empty(const sub_t *sub)
384 {
385 return ((sub->sub_len == 0) ? B_TRUE : B_FALSE);
386 }
387
388 size_t
389 sub_len(const sub_t *sub)
390 {
391 return (sub->sub_len);
392 }
393
394 static boolean_t
395 sub_reserve(sub_t *sub, size_t amt)
396 {
397 if (sub->sub_len + amt < sub->sub_size)
398 return (B_TRUE);
399
400 size_t newsize = roundup(sub->sub_size + amt, CHUNK_SIZE);
401 void *temp = xrealloc(sub->sub_ops, sub->sub_items,
402 sub->sub_size * sizeof (name_t), newsize * sizeof (name_t));
403
404 if (temp == NULL)
405 return (B_FALSE);
406
407 sub->sub_items = temp;
408 sub->sub_size = newsize;
409
410 return (B_TRUE);
411 }
412
413 /* save the element of n (up to depth elements deep) as a substitution */
414 boolean_t
415 sub_save(sub_t *sub, const name_t *n, size_t depth)
416 {
417 if (depth == 0)
418 return (B_TRUE);
419
420 if (!sub_reserve(sub, 1))
421 return (B_FALSE);
422
423 name_t *dest = &sub->sub_items[sub->sub_len++];
424 name_init(dest, sub->sub_ops);
425
426 if (!name_reserve(dest, depth)) {
427 name_fini(dest);
428 sub->sub_len--;
429 return (B_FALSE);
430 }
431
432 const str_pair_t *src_sp = name_at((name_t *)n, depth - 1);
433
434 for (size_t i = 0; i < depth; i++, src_sp++) {
435 str_pair_t copy = { 0 };
436 str_pair_init(©, n->nm_ops);
437 if (!str_pair_copy(src_sp, ©)) {
438 str_pair_fini(©);
439 name_fini(dest);
440 return (B_FALSE);
441 }
442
443 VERIFY(name_add_str(dest, ©.strp_l, ©.strp_r));
444 }
445
446 return (B_TRUE);
447 }
448
449 /* push substitution idx onto n */
450 boolean_t
451 sub_substitute(const sub_t *sub, size_t idx, name_t *n)
452 {
453 ASSERT3U(idx, <, sub->sub_len);
454
455 const name_t *src = &sub->sub_items[idx];
456 const str_pair_t *sp = src->nm_items;
457 size_t save = name_len(n);
458
459 for (size_t i = 0; i < src->nm_len; i++, sp++) {
460 str_pair_t copy = { 0 };
461
462 if (!str_pair_copy(sp, ©))
463 goto fail;
464
465 if (!name_add_str(n, ©.strp_l, ©.strp_r))
466 goto fail;
467 }
468
469 return (B_TRUE);
470
471 fail:
472 for (size_t i = 0; i < name_len(n) - save; i++)
473 (void) name_pop(n, NULL);
474 return (B_FALSE);
475 }
476
477 void
478 sub_pop(sub_t *sub)
479 {
480 name_t *top = &sub->sub_items[--sub->sub_len];
481 name_fini(top);
482 }
483
484 /*
485 * Templates can use substitutions for it's arguments (using T instead of
486 * S). Since templates can nest however, each nesting requires a new
487 * set of substitutions. As such a new, empty list of template substitutions
488 * is pushed onto cpp_templ each time templates are nested, and popped at
489 * the end of the current template argument list.
490 */
491 static boolean_t
492 templ_reserve(templ_t *tpl, size_t n)
493 {
494 if (tpl->tpl_len + n < tpl->tpl_size)
495 return (B_TRUE);
496
497 size_t newsize = tpl->tpl_size + CHUNK_SIZE;
498 void *temp = xrealloc(tpl->tpl_ops, tpl->tpl_items,
499 tpl->tpl_size * sizeof (sub_t), newsize * sizeof (sub_t));
500
501 if (temp == NULL)
502 return (B_FALSE);
503
504 tpl->tpl_items = temp;
505 tpl->tpl_size = newsize;
506 return (B_TRUE);
507 }
508
509 void
510 templ_init(templ_t *tpl, sysdem_ops_t *ops)
511 {
512 (void) memset(tpl, 0, sizeof (*tpl));
513 tpl->tpl_ops = ops;
514 }
515
516 void
517 templ_fini(templ_t *tpl)
518 {
519 if (tpl == NULL)
520 return;
521
522 for (size_t i = 0; i < tpl->tpl_len; i++)
523 sub_fini(&tpl->tpl_items[i]);
524
525 xfree(tpl->tpl_ops, tpl->tpl_items, tpl->tpl_size * sizeof (sub_t));
526 sysdem_ops_t *ops = tpl->tpl_ops;
527 (void) memset(tpl, 0, sizeof (*tpl));
528 tpl->tpl_ops = ops;
529 }
530
531 boolean_t
532 templ_push(templ_t *tpl)
533 {
534 if (!templ_reserve(tpl, 1))
535 return (B_FALSE);
536
537 sub_t *sub = &tpl->tpl_items[tpl->tpl_len++];
538 sub_init(sub, tpl->tpl_ops);
539 return (B_TRUE);
540 }
541
542 void
543 templ_pop(templ_t *tpl)
544 {
545 ASSERT(!templ_empty(tpl));
546
547 sub_t *sub = &tpl->tpl_items[--tpl->tpl_len];
548 sub_fini(sub);
549 }
550
551 sub_t *
552 templ_top(templ_t *tpl)
553 {
554 if (tpl->tpl_len == 0)
555 return (NULL);
556 return (&tpl->tpl_items[tpl->tpl_len - 1]);
557 }
558
559 boolean_t
560 templ_empty(const templ_t *tpl)
561 {
562 return ((tpl->tpl_len == 0) ? B_TRUE : B_FALSE);
563 }
564
565 size_t
566 templ_top_len(const templ_t *tpl)
567 {
568 const sub_t *sub = templ_top((templ_t *)tpl);
569
570 return (sub->sub_len);
571 }
572
573 boolean_t
574 templ_sub(const templ_t *tpl, size_t idx, name_t *n)
575 {
576 const sub_t *sub = templ_top((templ_t *)tpl);
577
578 return (sub_substitute(sub, idx, n));
579 }
580
581 boolean_t
582 templ_save(const name_t *n, size_t amt, templ_t *tpl)
583 {
584 ASSERT3U(tpl->tpl_len, >, 0);
585
586 sub_t *s = templ_top(tpl);
587 boolean_t res = B_TRUE;
588
589 /* a bit of a hack -- want an 'empty' entry when saving 0 params */
590 if (amt == 0) {
591 name_t name = { 0 };
592
593 name_init(&name, tpl->tpl_ops);
594 res &= name_add(&name, "", 0, "", 0);
595 if (res)
596 res &= sub_save(s, &name, 1);
597 name_fini(&name);
598 } else {
599 res &= sub_save(s, n, amt);
600 }
601
602 return (res);
603 }