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);
14static void ptree(struct op *, int, struct shf *);
15static void pioact(struct shf *, int, struct ioword *);
16static void tputC(int, struct shf *);
17static void tputS(char *, struct shf *);
18static void vfptreef(struct shf *, int, const char *, va_list);
19static struct ioword **iocopy(struct ioword **, Area *);
20static void iofree(struct ioword **, Area *);
21
22/*
23 * print a command tree
24 */
25
26static void
27ptree(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
191static void
192pioact(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
248static void
249tputC(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
261static void
262tputS(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
336void
337fptreef(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
346char *
347snptreef(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
361static void
362vfptreef(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
434struct op *
435tcopy(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
483char *
484wdcopy(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 */
491char *
492wdscan(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 */
545char *
546wdstrip(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
610static struct ioword **
611iocopy(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
643void
644tfree(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
674static void
675iofree(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}
