lib/libdemangle-sys/cxx_util.c

   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 }