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(&copy, n->nm_ops);
 437                 if (!str_pair_copy(src_sp, &copy)) {
 438                         str_pair_fini(&copy);
 439                         name_fini(dest);
 440                         return (B_FALSE);
 441                 }
 442 
 443                 VERIFY(name_add_str(dest, &copy.strp_l, &copy.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, &copy))
 463                         goto fail;
 464 
 465                 if (!name_add_str(n, &copy.strp_l, &copy.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 }