bin/ksh/tree.c

   1 /*      $OpenBSD: tree.c,v 1.34 2018/04/09 17:53:36 tobias Exp $        */
   2
   3 /*
   4  * command tree climbing
   5  */
   6
   7 #include <string.h>
   8
   9 #include "sh.h"
  10
  11 #define INDENT  4
  12
  13 #define tputc(c, shf)   shf_putchar(c, shf);
  14 static void     ptree(struct op *, int, struct shf *);
  15 static void     pioact(struct shf *, int, struct ioword *);
  16 static void     tputC(int, struct shf *);
  17 static void     tputS(char *, struct shf *);
  18 static void     vfptreef(struct shf *, int, const char *, va_list);
  19 static struct ioword **iocopy(struct ioword **, Area *);
  20 static void     iofree(struct ioword **, Area *);
  21
  22 /*
  23  * print a command tree
  24  */
  25
  26 static void
  27 ptree(struct op *t, int indent, struct shf *shf)
  28 {
  29         char **w;
  30         struct ioword **ioact;
  31         struct op *t1;
  32
  33  Chain:
  34         if (t == NULL)
  35                 return;
  36         switch (t->type) {
  37         case TCOM:
  38                 if (t->vars)
  39                         for (w = t->vars; *w != NULL; )
  40                                 fptreef(shf, indent, "%S ", *w++);
  41                 else
  42                         fptreef(shf, indent, "#no-vars# ");
  43                 if (t->args)
  44                         for (w = t->args; *w != NULL; )
  45                                 fptreef(shf, indent, "%S ", *w++);
  46                 else
  47                         fptreef(shf, indent, "#no-args# ");
  48                 break;
  49         case TEXEC:
  50                 t = t->left;
  51                 goto Chain;
  52         case TPAREN:
  53                 fptreef(shf, indent + 2, "( %T) ", t->left);
  54                 break;
  55         case TPIPE:
  56                 fptreef(shf, indent, "%T| ", t->left);
  57                 t = t->right;
  58                 goto Chain;
  59         case TLIST:
  60                 fptreef(shf, indent, "%T%;", t->left);
  61                 t = t->right;
  62                 goto Chain;
  63         case TOR:
  64         case TAND:
  65                 fptreef(shf, indent, "%T%s %T",
  66                     t->left, (t->type==TOR) ? "||" : "&&", t->right);
  67                 break;
  68         case TBANG:
  69                 fptreef(shf, indent, "! ");
  70                 t = t->right;
  71                 goto Chain;
  72         case TDBRACKET:
  73           {
  74                 int i;
  75
  76                 fptreef(shf, indent, "[[");
  77                 for (i = 0; t->args[i]; i++)
  78                         fptreef(shf, indent, " %S", t->args[i]);
  79                 fptreef(shf, indent, " ]] ");
  80                 break;
  81           }
  82         case TSELECT:
  83                 fptreef(shf, indent, "select %s ", t->str);
  84                 /* FALLTHROUGH */
  85         case TFOR:
  86                 if (t->type == TFOR)
  87                         fptreef(shf, indent, "for %s ", t->str);
  88                 if (t->vars != NULL) {
  89                         fptreef(shf, indent, "in ");
  90                         for (w = t->vars; *w; )
  91                                 fptreef(shf, indent, "%S ", *w++);
  92                         fptreef(shf, indent, "%;");
  93                 }
  94                 fptreef(shf, indent + INDENT, "do%N%T", t->left);
  95                 fptreef(shf, indent, "%;done ");
  96                 break;
  97         case TCASE:
  98                 fptreef(shf, indent, "case %S in", t->str);
  99                 for (t1 = t->left; t1 != NULL; t1 = t1->right) {
 100                         fptreef(shf, indent, "%N(");
 101                         for (w = t1->vars; *w != NULL; w++)
 102                                 fptreef(shf, indent, "%S%c", *w,
 103                                     (w[1] != NULL) ? '|' : ')');
 104                         fptreef(shf, indent + INDENT, "%;%T%N;;", t1->left);
 105                 }
 106                 fptreef(shf, indent, "%Nesac ");
 107                 break;
 108         case TIF:
 109         case TELIF:
 110                 /* 3 == strlen("if ") */
 111                 fptreef(shf, indent + 3, "if %T", t->left);
 112                 for (;;) {
 113                         t = t->right;
 114                         if (t->left != NULL) {
 115                                 fptreef(shf, indent, "%;");
 116                                 fptreef(shf, indent + INDENT, "then%N%T",
 117                                     t->left);
 118                         }
 119                         if (t->right == NULL || t->right->type != TELIF)
 120                                 break;
 121                         t = t->right;
 122                         fptreef(shf, indent, "%;");
 123                         /* 5 == strlen("elif ") */
 124                         fptreef(shf, indent + 5, "elif %T", t->left);
 125                 }
 126                 if (t->right != NULL) {
 127                         fptreef(shf, indent, "%;");
 128                         fptreef(shf, indent + INDENT, "else%;%T", t->right);
 129                 }
 130                 fptreef(shf, indent, "%;fi ");
 131                 break;
 132         case TWHILE:
 133         case TUNTIL:
 134                 /* 6 == strlen("while"/"until") */
 135                 fptreef(shf, indent + 6, "%s %T",
 136                     (t->type==TWHILE) ? "while" : "until",
 137                     t->left);
 138                 fptreef(shf, indent, "%;do");
 139                 fptreef(shf, indent + INDENT, "%;%T", t->right);
 140                 fptreef(shf, indent, "%;done ");
 141                 break;
 142         case TBRACE:
 143                 fptreef(shf, indent + INDENT, "{%;%T", t->left);
 144                 fptreef(shf, indent, "%;} ");
 145                 break;
 146         case TCOPROC:
 147                 fptreef(shf, indent, "%T|& ", t->left);
 148                 break;
 149         case TASYNC:
 150                 fptreef(shf, indent, "%T& ", t->left);
 151                 break;
 152         case TFUNCT:
 153                 fptreef(shf, indent,
 154                     t->u.ksh_func ? "function %s %T" : "%s() %T",
 155                     t->str, t->left);
 156                 break;
 157         case TTIME:
 158                 fptreef(shf, indent, "time %T", t->left);
 159                 break;
 160         default:
 161                 fptreef(shf, indent, "<botch>");
 162                 break;
 163         }
 164         if ((ioact = t->ioact) != NULL) {
 165                 int     need_nl = 0;
 166
 167                 while (*ioact != NULL)
 168                         pioact(shf, indent, *ioact++);
 169                 /* Print here documents after everything else... */
 170                 for (ioact = t->ioact; *ioact != NULL; ) {
 171                         struct ioword *iop = *ioact++;
 172
 173                         /* heredoc is 0 when tracing (set -x) */
 174                         if ((iop->flag & IOTYPE) == IOHERE && iop->heredoc) {
 175                                 tputc('\n', shf);
 176                                 shf_puts(iop->heredoc, shf);
 177                                 fptreef(shf, indent, "%s",
 178                                     evalstr(iop->delim, 0));
 179                                 need_nl = 1;
 180                         }
 181                 }
 182                 /* Last delimiter must be followed by a newline (this often
 183                  * leads to an extra blank line, but its not worth worrying
 184                  * about)
 185                  */
 186                 if (need_nl)
 187                         tputc('\n', shf);
 188         }
 189 }
 190
 191 static void
 192 pioact(struct shf *shf, int indent, struct ioword *iop)
 193 {
 194         int flag = iop->flag;
 195         int type = flag & IOTYPE;
 196         int expected;
 197
 198         expected = (type == IOREAD || type == IORDWR || type == IOHERE) ? 0 :
 199             (type == IOCAT || type == IOWRITE) ? 1 :
 200             (type == IODUP && (iop->unit == !(flag & IORDUP))) ? iop->unit :
 201             iop->unit + 1;
 202         if (iop->unit != expected)
 203                 tputc('0' + iop->unit, shf);
 204
 205         switch (type) {
 206         case IOREAD:
 207                 fptreef(shf, indent, "< ");
 208                 break;
 209         case IOHERE:
 210                 if (flag&IOSKIP)
 211                         fptreef(shf, indent, "<<- ");
 212                 else
 213                         fptreef(shf, indent, "<< ");
 214                 break;
 215         case IOCAT:
 216                 fptreef(shf, indent, ">> ");
 217                 break;
 218         case IOWRITE:
 219                 if (flag&IOCLOB)
 220                         fptreef(shf, indent, ">| ");
 221                 else
 222                         fptreef(shf, indent, "> ");
 223                 break;
 224         case IORDWR:
 225                 fptreef(shf, indent, "<> ");
 226                 break;
 227         case IODUP:
 228                 if (flag & IORDUP)
 229                         fptreef(shf, indent, "<&");
 230                 else
 231                         fptreef(shf, indent, ">&");
 232                 break;
 233         }
 234         /* name/delim are 0 when printing syntax errors */
 235         if (type == IOHERE) {
 236                 if (iop->delim)
 237                         fptreef(shf, indent, "%S ", iop->delim);
 238         } else if (iop->name)
 239                 fptreef(shf, indent, (iop->flag & IONAMEXP) ? "%s " : "%S ",
 240                     iop->name);
 241 }
 242
 243
 244 /*
 245  * variants of fputc, fputs for ptreef and snptreef
 246  */
 247
 248 static void
 249 tputC(int c, struct shf *shf)
 250 {
 251         if ((c&0x60) == 0) {            /* C0|C1 */
 252                 tputc((c&0x80) ? '$' : '^', shf);
 253                 tputc(((c&0x7F)|0x40), shf);
 254         } else if ((c&0x7F) == 0x7F) {  /* DEL */
 255                 tputc((c&0x80) ? '$' : '^', shf);
 256                 tputc('?', shf);
 257         } else
 258                 tputc(c, shf);
 259 }
 260
 261 static void
 262 tputS(char *wp, struct shf *shf)
 263 {
 264         int c, quoted=0;
 265
 266         /* problems:
 267          *      `...` -> $(...)
 268          *      'foo' -> "foo"
 269          * could change encoding to:
 270          *      OQUOTE ["'] ... CQUOTE ["']
 271          *      COMSUB [(`] ...\0       (handle $ ` \ and maybe " in `...` case)
 272          */
 273         while (1)
 274                 switch ((c = *wp++)) {
 275                 case EOS:
 276                         return;
 277                 case CHAR:
 278                         tputC(*wp++, shf);
 279                         break;
 280                 case QCHAR:
 281                         c = *wp++;
 282                         if (!quoted || (c == '"' || c == '`' || c == '$'))
 283                                 tputc('\\', shf);
 284                         tputC(c, shf);
 285                         break;
 286                 case COMSUB:
 287                         tputc('$', shf);
 288                         tputc('(', shf);
 289                         while (*wp != 0)
 290                                 tputC(*wp++, shf);
 291                         tputc(')', shf);
 292                         wp++;
 293                         break;
 294                 case EXPRSUB:
 295                         tputc('$', shf);
 296                         tputc('(', shf);
 297                         tputc('(', shf);
 298                         while (*wp != 0)
 299                                 tputC(*wp++, shf);
 300                         tputc(')', shf);
 301                         tputc(')', shf);
 302                         wp++;
 303                         break;
 304                 case OQUOTE:
 305                         quoted = 1;
 306                         tputc('"', shf);
 307                         break;
 308                 case CQUOTE:
 309                         quoted = 0;
 310                         tputc('"', shf);
 311                         break;
 312                 case OSUBST:
 313                         tputc('$', shf);
 314                         if (*wp++ == '{')
 315                                 tputc('{', shf);
 316                         while ((c = *wp++) != 0)
 317                                 tputC(c, shf);
 318                         break;
 319                 case CSUBST:
 320                         if (*wp++ == '}')
 321                                 tputc('}', shf);
 322                         break;
 323                 case OPAT:
 324                         tputc(*wp++, shf);
 325                         tputc('(', shf);
 326                         break;
 327                 case SPAT:
 328                         tputc('|', shf);
 329                         break;
 330                 case CPAT:
 331                         tputc(')', shf);
 332                         break;
 333                 }
 334 }
 335
 336 void
 337 fptreef(struct shf *shf, int indent, const char *fmt, ...)
 338 {
 339   va_list       va;
 340
 341   va_start(va, fmt);
 342   vfptreef(shf, indent, fmt, va);
 343   va_end(va);
 344 }
 345
 346 char *
 347 snptreef(char *s, int n, const char *fmt, ...)
 348 {
 349   va_list va;
 350   struct shf shf;
 351
 352   shf_sopen(s, n, SHF_WR | (s ? 0 : SHF_DYNAMIC), &shf);
 353
 354   va_start(va, fmt);
 355   vfptreef(&shf, 0, fmt, va);
 356   va_end(va);
 357
 358   return shf_sclose(&shf); /* null terminates */
 359 }
 360
 361 static void
 362 vfptreef(struct shf *shf, int indent, const char *fmt, va_list va)
 363 {
 364         int c;
 365
 366         while ((c = *fmt++)) {
 367                 if (c == '%') {
 368                         int64_t n;
 369                         char *p;
 370                         int neg;
 371
 372                         switch ((c = *fmt++)) {
 373                         case 'c':
 374                                 tputc(va_arg(va, int), shf);
 375                                 break;
 376                         case 'd': /* decimal */
 377                                 n = va_arg(va, int);
 378                                 neg = n < 0;
 379                                 p = u64ton(neg ? -n : n, 10);
 380                                 if (neg)
 381                                         *--p = '-';
 382                                 while (*p)
 383                                         tputc(*p++, shf);
 384                                 break;
 385                         case 's':
 386                                 p = va_arg(va, char *);
 387                                 while (*p)
 388                                         tputc(*p++, shf);
 389                                 break;
 390                         case 'S':       /* word */
 391                                 p = va_arg(va, char *);
 392                                 tputS(p, shf);
 393                                 break;
 394                         case 'u': /* unsigned decimal */
 395                                 p = u64ton(va_arg(va, unsigned int), 10);
 396                                 while (*p)
 397                                         tputc(*p++, shf);
 398                                 break;
 399                         case 'T':       /* format tree */
 400                                 ptree(va_arg(va, struct op *), indent, shf);
 401                                 break;
 402                         case ';':       /* newline or ; */
 403                         case 'N':       /* newline or space */
 404                                 if (shf->flags & SHF_STRING) {
 405                                         if (c == ';')
 406                                                 tputc(';', shf);
 407                                         tputc(' ', shf);
 408                                 } else {
 409                                         int i;
 410
 411                                         tputc('\n', shf);
 412                                         for (i = indent; i >= 8; i -= 8)
 413                                                 tputc('\t', shf);
 414                                         for (; i > 0; --i)
 415                                                 tputc(' ', shf);
 416                                 }
 417                                 break;
 418                         case 'R':
 419                                 pioact(shf, indent, va_arg(va, struct ioword *));
 420                                 break;
 421                         default:
 422                                 tputc(c, shf);
 423                                 break;
 424                         }
 425                 } else
 426                         tputc(c, shf);
 427         }
 428 }
 429
 430 /*
 431  * copy tree (for function definition)
 432  */
 433
 434 struct op *
 435 tcopy(struct op *t, Area *ap)
 436 {
 437         struct op *r;
 438         char **tw, **rw;
 439
 440         if (t == NULL)
 441                 return NULL;
 442
 443         r = alloc(sizeof(struct op), ap);
 444
 445         r->type = t->type;
 446         r->u.evalflags = t->u.evalflags;
 447
 448         r->str = t->type == TCASE ? wdcopy(t->str, ap) : str_save(t->str, ap);
 449
 450         if (t->vars == NULL)
 451                 r->vars = NULL;
 452         else {
 453                 for (tw = t->vars; *tw++ != NULL; )
 454                         ;
 455                 rw = r->vars = areallocarray(NULL, tw - t->vars + 1,
 456                     sizeof(*tw), ap);
 457                 for (tw = t->vars; *tw != NULL; )
 458                         *rw++ = wdcopy(*tw++, ap);
 459                 *rw = NULL;
 460         }
 461
 462         if (t->args == NULL)
 463                 r->args = NULL;
 464         else {
 465                 for (tw = t->args; *tw++ != NULL; )
 466                         ;
 467                 rw = r->args = areallocarray(NULL, tw - t->args + 1,
 468                     sizeof(*tw), ap);
 469                 for (tw = t->args; *tw != NULL; )
 470                         *rw++ = wdcopy(*tw++, ap);
 471                 *rw = NULL;
 472         }
 473
 474         r->ioact = (t->ioact == NULL) ? NULL : iocopy(t->ioact, ap);
 475
 476         r->left = tcopy(t->left, ap);
 477         r->right = tcopy(t->right, ap);
 478         r->lineno = t->lineno;
 479
 480         return r;
 481 }
 482
 483 char *
 484 wdcopy(const char *wp, Area *ap)
 485 {
 486         size_t len = wdscan(wp, EOS) - wp;
 487         return memcpy(alloc(len, ap), wp, len);
 488 }
 489
 490 /* return the position of prefix c in wp plus 1 */
 491 char *
 492 wdscan(const char *wp, int c)
 493 {
 494         int nest = 0;
 495
 496         while (1)
 497                 switch (*wp++) {
 498                 case EOS:
 499                         return (char *) wp;
 500                 case CHAR:
 501                 case QCHAR:
 502                         wp++;
 503                         break;
 504                 case COMSUB:
 505                 case EXPRSUB:
 506                         while (*wp++ != 0)
 507                                 ;
 508                         break;
 509                 case OQUOTE:
 510                 case CQUOTE:
 511                         break;
 512                 case OSUBST:
 513                         nest++;
 514                         while (*wp++ != '\0')
 515                                 ;
 516                         break;
 517                 case CSUBST:
 518                         wp++;
 519                         if (c == CSUBST && nest == 0)
 520                                 return (char *) wp;
 521                         nest--;
 522                         break;
 523                 case OPAT:
 524                         nest++;
 525                         wp++;
 526                         break;
 527                 case SPAT:
 528                 case CPAT:
 529                         if (c == wp[-1] && nest == 0)
 530                                 return (char *) wp;
 531                         if (wp[-1] == CPAT)
 532                                 nest--;
 533                         break;
 534                 default:
 535                         internal_warningf(
 536                             "%s: unknown char 0x%x (carrying on)",
 537                             __func__, wp[-1]);
 538                 }
 539 }
 540
 541 /* return a copy of wp without any of the mark up characters and
 542  * with quote characters (" ' \) stripped.
 543  * (string is allocated from ATEMP)
 544  */
 545 char *
 546 wdstrip(const char *wp)
 547 {
 548         struct shf shf;
 549         int c;
 550
 551         shf_sopen(NULL, 32, SHF_WR | SHF_DYNAMIC, &shf);
 552
 553         /* problems:
 554          *      `...` -> $(...)
 555          *      x${foo:-"hi"} -> x${foo:-hi}
 556          *      x${foo:-'hi'} -> x${foo:-hi}
 557          */
 558         while (1)
 559                 switch ((c = *wp++)) {
 560                 case EOS:
 561                         return shf_sclose(&shf); /* null terminates */
 562                 case CHAR:
 563                 case QCHAR:
 564                         shf_putchar(*wp++, &shf);
 565                         break;
 566                 case COMSUB:
 567                         shf_putchar('$', &shf);
 568                         shf_putchar('(', &shf);
 569                         while (*wp != 0)
 570                                 shf_putchar(*wp++, &shf);
 571                         shf_putchar(')', &shf);
 572                         break;
 573                 case EXPRSUB:
 574                         shf_putchar('$', &shf);
 575                         shf_putchar('(', &shf);
 576                         shf_putchar('(', &shf);
 577                         while (*wp != 0)
 578                                 shf_putchar(*wp++, &shf);
 579                         shf_putchar(')', &shf);
 580                         shf_putchar(')', &shf);
 581                         break;
 582                 case OQUOTE:
 583                         break;
 584                 case CQUOTE:
 585                         break;
 586                 case OSUBST:
 587                         shf_putchar('$', &shf);
 588                         if (*wp++ == '{')
 589                             shf_putchar('{', &shf);
 590                         while ((c = *wp++) != 0)
 591                                 shf_putchar(c, &shf);
 592                         break;
 593                 case CSUBST:
 594                         if (*wp++ == '}')
 595                                 shf_putchar('}', &shf);
 596                         break;
 597                 case OPAT:
 598                         shf_putchar(*wp++, &shf);
 599                         shf_putchar('(', &shf);
 600                         break;
 601                 case SPAT:
 602                         shf_putchar('|', &shf);
 603                         break;
 604                 case CPAT:
 605                         shf_putchar(')', &shf);
 606                         break;
 607                 }
 608 }
 609
 610 static  struct ioword **
 611 iocopy(struct ioword **iow, Area *ap)
 612 {
 613         struct ioword **ior;
 614         int i;
 615
 616         for (ior = iow; *ior++ != NULL; )
 617                 ;
 618         ior = areallocarray(NULL, ior - iow + 1, sizeof(*ior), ap);
 619
 620         for (i = 0; iow[i] != NULL; i++) {
 621                 struct ioword *p, *q;
 622
 623                 p = iow[i];
 624                 q = alloc(sizeof(*p), ap);
 625                 ior[i] = q;
 626                 *q = *p;
 627                 if (p->name != NULL)
 628                         q->name = wdcopy(p->name, ap);
 629                 if (p->delim != NULL)
 630                         q->delim = wdcopy(p->delim, ap);
 631                 if (p->heredoc != NULL)
 632                         q->heredoc = str_save(p->heredoc, ap);
 633         }
 634         ior[i] = NULL;
 635
 636         return ior;
 637 }
 638
 639 /*
 640  * free tree (for function definition)
 641  */
 642
 643 void
 644 tfree(struct op *t, Area *ap)
 645 {
 646         char **w;
 647
 648         if (t == NULL)
 649                 return;
 650
 651         afree(t->str, ap);
 652
 653         if (t->vars != NULL) {
 654                 for (w = t->vars; *w != NULL; w++)
 655                         afree(*w, ap);
 656                 afree(t->vars, ap);
 657         }
 658
 659         if (t->args != NULL) {
 660                 for (w = t->args; *w != NULL; w++)
 661                         afree(*w, ap);
 662                 afree(t->args, ap);
 663         }
 664
 665         if (t->ioact != NULL)
 666                 iofree(t->ioact, ap);
 667
 668         tfree(t->left, ap);
 669         tfree(t->right, ap);
 670
 671         afree(t, ap);
 672 }
 673
 674 static  void
 675 iofree(struct ioword **iow, Area *ap)
 676 {
 677         struct ioword **iop;
 678         struct ioword *p;
 679
 680         for (iop = iow; (p = *iop++) != NULL; ) {
 681                 afree(p->name, ap);
 682                 afree(p->delim, ap);
 683                 afree(p->heredoc, ap);
 684                 afree(p, ap);
 685         }
 686         afree(iow, ap);
 687 }