bin/ksh/tree.c

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