1/*
2 * sh.parse.c: Interpret a list of tokens
3 */
4/*-
5 * Copyright (c) 1980, 1991 The Regents of the University of California.
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 *    may be used to endorse or promote products derived from this software
18 *    without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 */
32#include "sh.h"
33
34/*
35 * C shell
36 */
37static	int		 asyntax (struct wordent *, struct wordent *);
38static	int		 asyn0 	 (struct wordent *, struct wordent *);
39static	int		 asyn3	 (struct wordent *, struct wordent *);
40static	struct wordent	*freenod (struct wordent *, struct wordent *);
41static	struct command	*syn0	 (const struct wordent *, const struct wordent *, int);
42static	struct command	*syn1	 (const struct wordent *, const struct wordent *, int);
43static	struct command	*syn1a	 (const struct wordent *, const struct wordent *, int);
44static	struct command	*syn1b	 (const struct wordent *, const struct wordent *, int);
45static	struct command	*syn2	 (const struct wordent *, const struct wordent *, int);
46static	struct command	*syn3	 (const struct wordent *, const struct wordent *, int);
47
48#define ALEFT	51		/* max of 50 alias expansions	 */
49#define HLEFT	11		/* max of 10 history expansions */
50/*
51 * Perform aliasing on the word list lexp
52 * Do a (very rudimentary) parse to separate into commands.
53 * If word 0 of a command has an alias, do it.
54 * Repeat a maximum of 50 times.
55 */
56extern int hleft;
57void
58alias(struct wordent *lexp)
59{
60    int aleft;
61
62    aleft = ALEFT;
63    hleft = HLEFT;
64    do {
65	if (--aleft == 0)
66	    stderror(ERR_ALIASLOOP);
67    } while (asyntax(lexp->next, lexp) != 0);
68}
69
70static int
71asyntax(struct wordent *p1, struct wordent *p2)
72{
73    while (p1 != p2) {
74	if (!any(";&\n", p1->word[0]))
75	    return asyn0(p1, p2);
76	p1 = p1->next;
77    }
78    return 0;
79}
80
81static int
82asyn0(struct wordent *p1, struct wordent *p2)
83{
84    struct wordent *p;
85    int l = 0;
86
87    for (p = p1; p != p2; p = p->next)
88	switch (p->word[0]) {
89
90	case '(':
91	    l++;
92	    continue;
93
94	case ')':
95	    l--;
96	    if (l < 0)
97		stderror(ERR_TOOMANYRP);
98	    continue;
99
100	case '>':
101	    if (p->next != p2 && eq(p->next->word, STRand))
102		p = p->next;
103	    continue;
104
105	case '&':
106	case '|':
107	case ';':
108	case '\n':
109	    if (l != 0)
110		continue;
111	    if (asyn3(p1, p) != 0)
112		return 1;
113	    return asyntax(p->next, p2);
114
115	default:
116	    break;
117	}
118    if (l == 0)
119	return asyn3(p1, p2);
120    return 0;
121}
122
123static void
124alvec_cleanup(void *dummy)
125{
126    USE(dummy);
127    alhistp = NULL;
128    alhistt = NULL;
129    alvec = NULL;
130}
131
132static int
133asyn3(struct wordent *p1, struct wordent *p2)
134{
135    struct varent *ap;
136    struct wordent alout;
137    int redid;
138
139    if (p1 == p2)
140	return 0;
141    if (p1->word[0] == '(') {
142	for (p2 = p2->prev; p2->word[0] != ')'; p2 = p2->prev)
143	    if (p2 == p1)
144		return 0;
145	if (p2 == p1->next)
146	    return 0;
147	return asyn0(p1->next, p2);
148    }
149    ap = adrof1(p1->word, &aliases);
150    if (ap == 0)
151	return 0;
152    alhistp = p1->prev;
153    alhistt = p2;
154    alvec = ap->vec;
155    cleanup_push(&alvec, alvec_cleanup);
156    redid = lex(&alout);
157    cleanup_until(&alvec);
158    if (seterr) {
159	freelex(&alout);
160	stderror(ERR_OLD);
161    }
162    if (p1->word[0] && eq(p1->word, alout.next->word)) {
163	Char   *cp = alout.next->word;
164
165	alout.next->word = Strspl(STRQNULL, cp);
166	xfree(cp);
167    }
168    p1 = freenod(p1, redid ? p2 : p1->next);
169    if (alout.next != &alout) {
170	p1->next->prev = alout.prev->prev;
171	alout.prev->prev->next = p1->next;
172	alout.next->prev = p1;
173	p1->next = alout.next;
174	xfree(alout.prev->word);
175	xfree(alout.prev);
176    }
177    return 1;
178}
179
180static struct wordent *
181freenod(struct wordent *p1, struct wordent *p2)
182{
183    struct wordent *retp = p1->prev;
184
185    while (p1 != p2) {
186	xfree(p1->word);
187	p1 = p1->next;
188	xfree(p1->prev);
189    }
190    retp->next = p2;
191    p2->prev = retp;
192    return (retp);
193}
194
195#define	P_HERE	1
196#define	P_IN	2
197#define	P_OUT	4
198#define	P_DIAG	8
199
200/*
201 * syntax
202 *	empty
203 *	syn0
204 */
205struct command *
206syntax(const struct wordent *p1, const struct wordent *p2, int flags)
207{
208
209    while (p1 != p2)
210	if (any(";&\n", p1->word[0]))
211	    p1 = p1->next;
212	else
213	    return (syn0(p1, p2, flags));
214    return (0);
215}
216
217/*
218 * syn0
219 *	syn1
220 *	syn1 & syntax
221 */
222static struct command *
223syn0(const struct wordent *p1, const struct wordent *p2, int flags)
224{
225    const struct wordent *p;
226    struct command *t, *t1;
227    int     l;
228
229    l = 0;
230    for (p = p1; p != p2; p = p->next)
231	switch (p->word[0]) {
232
233	case '(':
234	    l++;
235	    continue;
236
237	case ')':
238	    l--;
239	    if (l < 0)
240		seterror(ERR_TOOMANYRP);
241	    continue;
242
243	case '|':
244	    if (p->word[1] == '|')
245		continue;
246	    /*FALLTHROUGH*/
247
248	case '>':
249	    if (p->next != p2 && eq(p->next->word, STRand))
250		p = p->next;
251	    continue;
252
253	case '&':
254	    if (l != 0)
255		break;
256	    if (p->word[1] == '&')
257		continue;
258	    t1 = syn1(p1, p, flags);
259	    if (t1->t_dtyp == NODE_LIST ||
260		t1->t_dtyp == NODE_AND ||
261		t1->t_dtyp == NODE_OR) {
262		t = xcalloc(1, sizeof(*t));
263		t->t_dtyp = NODE_PAREN;
264		t->t_dflg = F_AMPERSAND | F_NOINTERRUPT;
265		t->t_dspr = t1;
266		t1 = t;
267	    }
268	    else
269		t1->t_dflg |= F_AMPERSAND | F_NOINTERRUPT;
270	    t = xcalloc(1, sizeof(*t));
271	    t->t_dtyp = NODE_LIST;
272	    t->t_dflg = 0;
273	    t->t_dcar = t1;
274	    t->t_dcdr = syntax(p, p2, flags);
275	    return (t);
276	default:
277	    break;
278	}
279    if (l == 0)
280	return (syn1(p1, p2, flags));
281    seterror(ERR_TOOMANYLP);
282    return (0);
283}
284
285/*
286 * syn1
287 *	syn1a
288 *	syn1a ; syntax
289 */
290static struct command *
291syn1(const struct wordent *p1, const struct wordent *p2, int flags)
292{
293    const struct wordent *p;
294    struct command *t;
295    int     l;
296
297    l = 0;
298    for (p = p1; p != p2; p = p->next)
299	switch (p->word[0]) {
300
301	case '(':
302	    l++;
303	    continue;
304
305	case ')':
306	    l--;
307	    continue;
308
309	case ';':
310	case '\n':
311	    if (l != 0)
312		break;
313	    t = xcalloc(1, sizeof(*t));
314	    t->t_dtyp = NODE_LIST;
315	    t->t_dcar = syn1a(p1, p, flags);
316	    t->t_dcdr = syntax(p->next, p2, flags);
317	    if (t->t_dcdr == 0)
318		t->t_dcdr = t->t_dcar, t->t_dcar = 0;
319	    return (t);
320
321	default:
322	    break;
323	}
324    return (syn1a(p1, p2, flags));
325}
326
327/*
328 * syn1a
329 *	syn1b
330 *	syn1b || syn1a
331 */
332static struct command *
333syn1a(const struct wordent *p1, const struct wordent *p2, int flags)
334{
335    const struct wordent *p;
336    struct command *t;
337    int l = 0;
338
339    for (p = p1; p != p2; p = p->next)
340	switch (p->word[0]) {
341
342	case '(':
343	    l++;
344	    continue;
345
346	case ')':
347	    l--;
348	    continue;
349
350	case '|':
351	    if (p->word[1] != '|')
352		continue;
353	    if (l == 0) {
354		t = xcalloc(1, sizeof(*t));
355		t->t_dtyp = NODE_OR;
356		t->t_dcar = syn1b(p1, p, flags);
357		t->t_dcdr = syn1a(p->next, p2, flags);
358		t->t_dflg = 0;
359		return (t);
360	    }
361	    continue;
362
363	default:
364	    break;
365	}
366    return (syn1b(p1, p2, flags));
367}
368
369/*
370 * syn1b
371 *	syn2
372 *	syn2 && syn1b
373 */
374static struct command *
375syn1b(const struct wordent *p1, const struct wordent *p2, int flags)
376{
377    const struct wordent *p;
378    struct command *t;
379    int l = 0;
380
381    for (p = p1; p != p2; p = p->next)
382	switch (p->word[0]) {
383
384	case '(':
385	    l++;
386	    continue;
387
388	case ')':
389	    l--;
390	    continue;
391
392	case '&':
393	    if (p->word[1] == '&' && l == 0) {
394		t = xcalloc(1, sizeof(*t));
395		t->t_dtyp = NODE_AND;
396		t->t_dcar = syn2(p1, p, flags);
397		t->t_dcdr = syn1b(p->next, p2, flags);
398		t->t_dflg = 0;
399		return (t);
400	    }
401	    continue;
402
403	default:
404	    break;
405	}
406    return (syn2(p1, p2, flags));
407}
408
409/*
410 * syn2
411 *	syn3
412 *	syn3 | syn2
413 *	syn3 |& syn2
414 */
415static struct command *
416syn2(const struct wordent *p1, const struct wordent *p2, int flags)
417{
418    const struct wordent *p, *pn;
419    struct command *t;
420    int l = 0;
421    int     f;
422
423    for (p = p1; p != p2; p = p->next)
424	switch (p->word[0]) {
425
426	case '(':
427	    l++;
428	    continue;
429
430	case ')':
431	    l--;
432	    continue;
433
434	case '|':
435	    if (l != 0)
436		continue;
437	    t = xcalloc(1, sizeof(*t));
438	    f = flags | P_OUT;
439	    pn = p->next;
440	    if (pn != p2 && pn->word[0] == '&') {
441		f |= P_DIAG;
442		t->t_dflg |= F_STDERR;
443	    }
444	    t->t_dtyp = NODE_PIPE;
445	    t->t_dcar = syn3(p1, p, f);
446	    if (pn != p2 && pn->word[0] == '&')
447		p = pn;
448	    t->t_dcdr = syn2(p->next, p2, flags | P_IN);
449	    return (t);
450
451	default:
452	    break;
453	}
454    return (syn3(p1, p2, flags));
455}
456
457static const char RELPAR[] = {'<', '>', '(', ')', '\0'};
458
459/*
460 * syn3
461 *	( syn0 ) [ < in  ] [ > out ]
462 *	word word* [ < in ] [ > out ]
463 *	KEYWORD ( word* ) word* [ < in ] [ > out ]
464 *
465 *	KEYWORD = (@ exit foreach if set switch test while)
466 */
467static struct command *
468syn3(const struct wordent *p1, const struct wordent *p2, int flags)
469{
470    const struct wordent *p;
471    const struct wordent *lp, *rp;
472    struct command *t;
473    int l;
474    Char  **av;
475    int     n, c;
476    int    specp = 0;
477
478    if (p1 != p2) {
479	p = p1;
480again:
481	switch (srchx(p->word)) {
482
483	case TC_ELSE:
484	    p = p->next;
485	    if (p != p2)
486		goto again;
487	    break;
488
489	case TC_EXIT:
490	case TC_FOREACH:
491	case TC_IF:
492	case TC_LET:
493	case TC_SET:
494	case TC_SWITCH:
495	case TC_WHILE:
496	    specp = 1;
497	    break;
498	default:
499	    break;
500	}
501    }
502    n = 0;
503    l = 0;
504    for (p = p1; p != p2; p = p->next)
505	switch (p->word[0]) {
506
507	case '(':
508	    if (specp)
509		n++;
510	    l++;
511	    continue;
512
513	case ')':
514	    if (specp)
515		n++;
516	    l--;
517	    continue;
518
519	case '>':
520	case '<':
521	    if (l != 0) {
522		if (specp)
523		    n++;
524		continue;
525	    }
526	    if (p->next == p2)
527		continue;
528	    if (any(RELPAR, p->next->word[0]))
529		continue;
530	    n--;
531	    continue;
532
533	default:
534	    if (!specp && l != 0)
535		continue;
536	    n++;
537	    continue;
538	}
539    if (n < 0)
540	n = 0;
541    t = xcalloc(1, sizeof(*t));
542    av = xcalloc(n + 1, sizeof(Char **));
543    t->t_dcom = av;
544    n = 0;
545    if (p2->word[0] == ')')
546	t->t_dflg = F_NOFORK;
547    lp = 0;
548    rp = 0;
549    l = 0;
550    for (p = p1; p != p2; p = p->next) {
551	c = p->word[0];
552	switch (c) {
553
554	case '(':
555	    if (l == 0) {
556		if (lp != 0 && !specp)
557		    seterror(ERR_BADPLP);
558		lp = p->next;
559	    }
560	    l++;
561	    goto savep;
562
563	case ')':
564	    l--;
565	    if (l == 0)
566		rp = p;
567	    goto savep;
568
569	case '>':
570	    if (l != 0)
571		goto savep;
572	    if (p->word[1] == '>')
573		t->t_dflg |= F_APPEND;
574	    if (p->next != p2 && eq(p->next->word, STRand)) {
575		t->t_dflg |= F_STDERR, p = p->next;
576		if (flags & (P_OUT | P_DIAG)) {
577		    seterror(ERR_OUTRED);
578		    continue;
579		}
580	    }
581	    if (p->next != p2 && eq(p->next->word, STRbang))
582		t->t_dflg |= F_OVERWRITE, p = p->next;
583	    if (p->next == p2) {
584		seterror(ERR_MISRED);
585		continue;
586	    }
587	    p = p->next;
588	    if (any(RELPAR, p->word[0])) {
589		seterror(ERR_MISRED);
590		continue;
591	    }
592	    if (((flags & P_OUT) && (flags & P_DIAG) == 0) || t->t_drit)
593		seterror(ERR_OUTRED);
594	    else
595		t->t_drit = Strsave(p->word);
596	    continue;
597
598	case '<':
599	    if (l != 0)
600		goto savep;
601	    if (p->word[1] == '<')
602		t->t_dflg |= F_READ;
603	    if (p->next == p2) {
604		seterror(ERR_MISRED);
605		continue;
606	    }
607	    p = p->next;
608	    if (any(RELPAR, p->word[0])) {
609		seterror(ERR_MISRED);
610		continue;
611	    }
612	    if ((flags & P_HERE) && (t->t_dflg & F_READ))
613		seterror(ERR_REDPAR);
614	    else if ((flags & P_IN) || t->t_dlef)
615		seterror(ERR_INRED);
616	    else
617		t->t_dlef = Strsave(p->word);
618	    continue;
619
620    savep:
621	    if (!specp)
622		continue;
623	default:
624	    if (l != 0 && !specp)
625		continue;
626	    if (seterr == 0)
627		av[n] = Strsave(p->word);
628	    n++;
629	    continue;
630	}
631    }
632    if (lp != 0 && !specp) {
633	if (n != 0)
634	    seterror(ERR_BADPLPS);
635	t->t_dtyp = NODE_PAREN;
636	t->t_dspr = syn0(lp, rp, P_HERE);
637    }
638    else {
639	if (n == 0)
640	    seterror(ERR_NULLCOM);
641	t->t_dtyp = NODE_COMMAND;
642    }
643    return (t);
644}
645
646void
647freesyn(struct command *t)
648{
649    Char **v;
650
651    if (t == 0)
652	return;
653    switch (t->t_dtyp) {
654
655    case NODE_COMMAND:
656	for (v = t->t_dcom; *v; v++)
657	    xfree(*v);
658	xfree(t->t_dcom);
659	xfree(t->t_dlef);
660	xfree(t->t_drit);
661	break;
662    case NODE_PAREN:
663	freesyn(t->t_dspr);
664	xfree(t->t_dlef);
665	xfree(t->t_drit);
666	break;
667
668    case NODE_AND:
669    case NODE_OR:
670    case NODE_PIPE:
671    case NODE_LIST:
672	freesyn(t->t_dcar), freesyn(t->t_dcdr);
673	break;
674    default:
675	break;
676    }
677#ifdef DEBUG
678    memset(t, 0, sizeof(*t));
679#endif
680    xfree(t);
681}
682
683void
684syntax_cleanup(void *xt)
685{
686    struct command *t;
687
688    t = xt;
689    freesyn(t);
690}
691