1/*
2 * Copyright (c) 1983 Regents of the University of California.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms are permitted
6 * provided that the above copyright notice and this paragraph are
7 * duplicated in all such forms and that any documentation,
8 * advertising materials, and other materials related to such
9 * distribution and use acknowledge that the software was developed
10 * by the University of California, Berkeley.  The name of the
11 * University may not be used to endorse or promote products derived
12 * from this software without specific prior written permission.
13 *
14 * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
15 * Use is subject to license terms.
16 */
17#pragma ident	"%Z%%M%	%I%	%E% SMI"
18
19#include "defs.h"
20#include <string.h>
21
22#define	GAVSIZ	NCARGS / 6
23#define	LC '{'
24#define	RC '}'
25
26static char	shchars[] = "${[*?";
27
28int	which;		/* bit mask of types to expand */
29int	eargc;		/* expanded arg count */
30char	**eargv;	/* expanded arg vectors */
31char	*path;
32char	*pathp;
33char	*lastpathp;
34char	*tilde;		/* "~user" if not expanding tilde, else "" */
35char	*tpathp;
36int	nleft;
37
38int	expany;		/* any expansions done? */
39char	*entp;
40char	**sortbase;
41
42char	*index();
43
44static int argcmp(const void *arg1, const void *arg2);
45static void addpath(char c);
46static void Cat(char *s1, char *s2);
47static void matchdir(char *pattern);
48static void expsh(char *s);
49static void expstr(char *s);
50static int execbrc(char *p, char *s);
51
52#define	sort()	qsort((char *)sortbase, &eargv[eargc] - sortbase, \
53		sizeof (*sortbase), argcmp), sortbase = &eargv[eargc]
54
55#define	MIN(a, b)	((a) < (b) ? (a) : (b))
56
57/*
58 * Take a list of names and expand any macros, etc.
59 * wh = E_VARS if expanding variables.
60 * wh = E_SHELL if expanding shell characters.
61 * wh = E_TILDE if expanding `~'.
62 * or any of these or'ed together.
63 *
64 * Major portions of this were snarfed from csh/sh.glob.c.
65 */
66struct namelist *
67expand(list, wh)
68	struct namelist *list;
69	int wh;
70{
71	register struct namelist *nl, *prev;
72	register int n;
73	char pathbuf[LINESIZE];
74	char *argvbuf[GAVSIZ];
75
76	if (debug) {
77		printf("expand(%x, %d)\nlist = ", list, wh);
78		prnames(list);
79	}
80
81	if (wh == 0) {
82		register char *cp;
83
84		for (nl = list; nl != NULL; nl = nl->n_next)
85			for (cp = nl->n_name; *cp; cp++)
86				*cp = *cp & TRIM;
87		return (list);
88	}
89
90	which = wh;
91	path = tpathp = pathp = pathbuf;
92	*pathp = '\0';
93	lastpathp = &path[sizeof pathbuf - 2];
94	tilde = "";
95	eargc = 0;
96	eargv = sortbase = argvbuf;
97	*eargv = 0;
98	nleft = NCARGS - 4;
99	/*
100	 * Walk the name list and expand names into eargv[];
101	 */
102	for (nl = list; nl != NULL; nl = nl->n_next)
103		expstr(nl->n_name);
104	/*
105	 * Take expanded list of names from eargv[] and build a new list.
106	 */
107	list = prev = NULL;
108	for (n = 0; n < eargc; n++) {
109		nl = makenl(NULL);
110		nl->n_name = eargv[n];
111		if (prev == NULL)
112			list = prev = nl;
113		else {
114			prev->n_next = nl;
115			prev = nl;
116		}
117	}
118	if (debug) {
119		printf("expanded list = ");
120		prnames(list);
121	}
122	return (list);
123}
124
125static void
126expstr(s)
127	char *s;
128{
129	register char *cp, *cp1;
130	register struct namelist *tp;
131	char *tail;
132	char buf[LINESIZE];
133	int savec, oeargc;
134	extern char homedir[];
135
136	if (s == NULL || *s == '\0')
137		return;
138
139	if ((which & E_VARS) && (cp = index(s, '$')) != NULL) {
140		*cp++ = '\0';
141		if (*cp == '\0') {
142			yyerror("no variable name after '$'");
143			return;
144		}
145		if (*cp == LC) {
146			cp++;
147			if ((tail = index(cp, RC)) == NULL) {
148				yyerror("unmatched '{'");
149				return;
150			}
151			*tail++ = savec = '\0';
152			if (*cp == '\0') {
153				yyerror("no variable name after '$'");
154				return;
155			}
156		} else {
157			tail = cp + 1;
158			savec = *tail;
159			*tail = '\0';
160		}
161		tp = lookup(cp, NULL, 0);
162		if (savec != '\0')
163			*tail = savec;
164		if (tp != NULL) {
165			for (; tp != NULL; tp = tp->n_next) {
166				(void) snprintf(buf, sizeof (buf), "%s%s%s", s,
167				    tp->n_name, tail);
168				expstr(buf);
169			}
170			return;
171		}
172		(void) snprintf(buf, sizeof (buf), "%s%s", s, tail);
173		expstr(buf);
174		return;
175	}
176	if ((which & ~E_VARS) == 0 || !strcmp(s, "{") || !strcmp(s, "{}")) {
177		Cat(s, "");
178		sort();
179		return;
180	}
181	if (*s == '~') {
182		cp = ++s;
183		if (*cp == '\0' || *cp == '/') {
184			tilde = "~";
185			cp1 = homedir;
186		} else {
187			tilde = cp1 = buf;
188			*cp1++ = '~';
189			do {
190				if (cp1 >= &buf[sizeof (buf)]) {
191					yyerror("User name too long");
192					return;
193				}
194				*cp1++ = *cp++;
195			} while (*cp && *cp != '/');
196			*cp1 = '\0';
197			if (pw == NULL || strcmp(pw->pw_name, buf+1) != 0) {
198				if ((pw = getpwnam(buf+1)) == NULL) {
199					static char unknown_user[] =
200					    ": unknown user name";
201
202					cp1 = MIN(cp1,
203					    &buf[sizeof (buf)] -
204					    sizeof (unknown_user));
205					strcpy(cp1, unknown_user);
206					yyerror(buf+1);
207					return;
208				}
209			}
210			cp1 = pw->pw_dir;
211			s = cp;
212		}
213		for (cp = path; cp <= lastpathp + 1 && (*cp++ = *cp1++); )
214			;
215		tpathp = pathp = cp - 1;
216	} else {
217		tpathp = pathp = path;
218		tilde = "";
219	}
220	*pathp = '\0';
221	if (!(which & E_SHELL)) {
222		if (which & E_TILDE)
223			Cat(path, s);
224		else
225			Cat(tilde, s);
226		sort();
227		return;
228	}
229	oeargc = eargc;
230	expany = 0;
231	expsh(s);
232	if (eargc == oeargc)
233		Cat(s, "");		/* "nonomatch" is set */
234	sort();
235}
236
237static int
238argcmp(const void *arg1, const void *arg2)
239{
240	char *a1 = *(char **)arg1;
241	char *a2 = *(char **)arg2;
242
243	return (strcmp(a1, a2));
244}
245
246/*
247 * If there are any Shell meta characters in the name,
248 * expand into a list, after searching directory
249 */
250static void
251expsh(s)
252	char *s;
253{
254	register char *cp;
255	register char *spathp, *oldcp;
256	struct stat stb;
257
258	spathp = pathp;
259	cp = s;
260	while (!any(*cp, shchars)) {
261		if (*cp == '\0') {
262			if (!expany || stat(path, &stb) >= 0) {
263				if (which & E_TILDE)
264					Cat(path, "");
265				else
266					Cat(tilde, tpathp);
267			}
268			goto endit;
269		}
270		addpath(*cp++);
271	}
272	oldcp = cp;
273	while (cp > s && *cp != '/')
274		cp--, pathp--;
275	if (*cp == '/')
276		cp++, pathp++;
277	*pathp = '\0';
278	if (*oldcp == '{') {
279		execbrc(cp, NULL);
280		return;
281	}
282	matchdir(cp);
283endit:
284	pathp = spathp;
285	*pathp = '\0';
286}
287
288static void
289matchdir(pattern)
290	char *pattern;
291{
292	struct stat stb;
293	register struct dirent *dp;
294	DIR *dirp;
295
296	dirp = opendir(path);
297	if (dirp == NULL) {
298		if (expany)
299			return;
300		goto patherr2;
301	}
302	if (fstat(dirp->dd_fd, &stb) < 0)
303		goto patherr1;
304	if (!ISDIR(stb.st_mode)) {
305		errno = ENOTDIR;
306		goto patherr1;
307	}
308	while ((dp = readdir(dirp)) != NULL)
309		if (match(dp->d_name, pattern)) {
310			if (which & E_TILDE)
311				Cat(path, dp->d_name);
312			else {
313				if (pathp + strlen(dp->d_name) - 1 >
314				    lastpathp) {
315					errno = ENAMETOOLONG;
316					goto patherr1;
317				}
318				strcpy(pathp, dp->d_name);
319				Cat(tilde, tpathp);
320				*pathp = '\0';
321			}
322		}
323	closedir(dirp);
324	return;
325
326patherr1:
327	closedir(dirp);
328patherr2:
329	{
330		char *strerr = strerror(errno);
331
332		if (path + strlen(path) + strlen(strerr) + 1 > lastpathp)
333			strcpy(lastpathp - strlen(strerr) - 1, ": ");
334		else
335			strcat(path, ": ");
336		strcat(path, strerr);
337	}
338	yyerror(path);
339}
340
341static int
342execbrc(p, s)
343	char *p, *s;
344{
345	char restbuf[LINESIZE + 2];
346	register char *pe, *pm, *pl;
347	int brclev = 0;
348	char *lm, savec, *spathp;
349
350	for (lm = restbuf; *p != '{'; *lm++ = *p++) {
351		if (lm >= &restbuf[sizeof (restbuf)]) {
352			yyerror("Pathname too long");
353			return (0);
354		}
355	}
356	for (pe = ++p; *pe; pe++)
357		switch (*pe) {
358
359		case '{':
360			brclev++;
361			continue;
362
363		case '}':
364			if (brclev == 0)
365				goto pend;
366			brclev--;
367			continue;
368
369		case '[':
370			for (pe++; *pe && *pe != ']'; pe++)
371				continue;
372			if (!*pe)
373				yyerror("Missing ']'");
374			continue;
375		}
376pend:
377	if (brclev || !*pe) {
378		yyerror("Missing '}'");
379		return (0);
380	}
381	for (pl = pm = p; pm <= pe; pm++)
382		switch (*pm & (QUOTE|TRIM)) {
383
384		case '{':
385			brclev++;
386			continue;
387
388		case '}':
389			if (brclev) {
390				brclev--;
391				continue;
392			}
393			goto doit;
394
395		case ',':
396			if (brclev)
397				continue;
398doit:
399			savec = *pm;
400			*pm = 0;
401			if (lm + strlen(pl) + strlen(pe + 1) >=
402			    &restbuf[sizeof (restbuf)]) {
403				yyerror("Pathname too long");
404				return (0);
405			}
406			strcpy(lm, pl);
407			strcat(restbuf, pe + 1);
408			*pm = savec;
409			if (s == 0) {
410				spathp = pathp;
411				expsh(restbuf);
412				pathp = spathp;
413				*pathp = 0;
414			} else if (amatch(s, restbuf))
415				return (1);
416			sort();
417			pl = pm + 1;
418			continue;
419
420		case '[':
421			for (pm++; *pm && *pm != ']'; pm++)
422				continue;
423			if (!*pm)
424				yyerror("Missing ']'");
425			continue;
426		}
427	return (0);
428}
429
430int
431match(s, p)
432	char *s, *p;
433{
434	register int c;
435	register char *sentp;
436	char sexpany = expany;
437
438	if (*s == '.' && *p != '.')
439		return (0);
440	sentp = entp;
441	entp = s;
442	c = amatch(s, p);
443	entp = sentp;
444	expany = sexpany;
445	return (c);
446}
447
448int
449amatch(s, p)
450	register char *s, *p;
451{
452	register int scc;
453	int ok, lc;
454	char *spathp;
455	struct stat stb;
456	int c, cc;
457
458	expany = 1;
459	for (;;) {
460		scc = *s++ & TRIM;
461		switch (c = *p++) {
462
463		case '{':
464			return (execbrc(p - 1, s - 1));
465
466		case '[':
467			ok = 0;
468			lc = 077777;
469			while (cc = *p++) {
470				if (cc == ']') {
471					if (ok)
472						break;
473					return (0);
474				}
475				if (cc == '-') {
476					if (lc <= scc && scc <= *p++)
477						ok++;
478				} else
479					if (scc == (lc = cc))
480						ok++;
481			}
482			if (cc == 0) {
483				yyerror("Missing ']'");
484				return (0);
485			}
486			continue;
487
488		case '*':
489			if (!*p)
490				return (1);
491			if (*p == '/') {
492				p++;
493				goto slash;
494			}
495			for (s--; *s; s++)
496				if (amatch(s, p))
497					return (1);
498			return (0);
499
500		case '\0':
501			return (scc == '\0');
502
503		default:
504			if ((c & TRIM) != scc)
505				return (0);
506			continue;
507
508		case '?':
509			if (scc == '\0')
510				return (0);
511			continue;
512
513		case '/':
514			if (scc)
515				return (0);
516slash:
517			s = entp;
518			spathp = pathp;
519			while (*s)
520				addpath(*s++);
521			addpath('/');
522			if (stat(path, &stb) == 0 && ISDIR(stb.st_mode))
523				if (*p == '\0') {
524					if (which & E_TILDE)
525						Cat(path, "");
526					else
527						Cat(tilde, tpathp);
528				} else
529					expsh(p);
530			pathp = spathp;
531			*pathp = '\0';
532			return (0);
533		}
534	}
535}
536
537int
538smatch(s, p)
539	register char *s, *p;
540{
541	register int scc;
542	int ok, lc;
543	int c, cc;
544
545	for (;;) {
546		scc = *s++ & TRIM;
547		switch (c = *p++) {
548
549		case '[':
550			ok = 0;
551			lc = 077777;
552			while (cc = *p++) {
553				if (cc == ']') {
554					if (ok)
555						break;
556					return (0);
557				}
558				if (cc == '-') {
559					if (lc <= scc && scc <= *p++)
560						ok++;
561				} else
562					if (scc == (lc = cc))
563						ok++;
564			}
565			if (cc == 0) {
566				yyerror("Missing ']'");
567				return (0);
568			}
569			continue;
570
571		case '*':
572			if (!*p)
573				return (1);
574			for (s--; *s; s++)
575				if (smatch(s, p))
576					return (1);
577			return (0);
578
579		case '\0':
580			return (scc == '\0');
581
582		default:
583			if ((c & TRIM) != scc)
584				return (0);
585			continue;
586
587		case '?':
588			if (scc == 0)
589				return (0);
590			continue;
591
592		}
593	}
594}
595
596static void
597Cat(s1, s2)
598	register char *s1, *s2;
599{
600	int len = strlen(s1) + strlen(s2) + 1;
601	register char *s;
602
603	nleft -= len;
604	if (nleft <= 0 || ++eargc >= GAVSIZ)
605		fatal("Arguments too long\n");
606	eargv[eargc] = 0;
607	eargv[eargc - 1] = s = (char *)malloc(len);
608	if (s == NULL)
609		fatal("ran out of memory\n");
610	while (*s++ = *s1++ & TRIM)
611		;
612	s--;
613	while (*s++ = *s2++ & TRIM)
614		;
615}
616
617static void
618addpath(char c)
619{
620
621	if (pathp > lastpathp)
622		yyerror("Pathname too long");
623	else {
624		*pathp++ = c & TRIM;
625		*pathp = '\0';
626	}
627}
628
629/*
630 * Expand file names beginning with `~' into the
631 * user's home directory path name. Return a pointer in buf to the
632 * part corresponding to `file'.
633 */
634char *
635exptilde(buf, len, file)
636	char buf[];
637	unsigned int len;
638	register char *file;
639{
640	register char *s1, *s2, *s3;
641	extern char homedir[];
642
643	if (*file != '~') {
644		if (strlen(file) + 1 > len) {
645			error("pathname too long: %s\n", file);
646			return (NULL);
647		}
648		strcpy(buf, file);
649		return (buf);
650	}
651	if (*++file == '\0') {
652		s2 = homedir;
653		s3 = NULL;
654	} else if (*file == '/') {
655		s2 = homedir;
656		s3 = file;
657	} else {
658		s3 = file;
659		while (*s3 && *s3 != '/')
660			s3++;
661		if (*s3 == '/')
662			*s3 = '\0';
663		else
664			s3 = NULL;
665		if (pw == NULL || strcmp(pw->pw_name, file) != 0) {
666			if ((pw = getpwnam(file)) == NULL) {
667				error("%s: unknown user name\n", file);
668				if (s3 != NULL)
669					*s3 = '/';
670				return (NULL);
671			}
672		}
673		if (s3 != NULL)
674			*s3 = '/';
675		s2 = pw->pw_dir;
676	}
677	for (s1 = buf; s1 < &buf[len] && (*s1++ = *s2++); )
678		;
679	s2 = --s1;
680	if (s3 != NULL) {
681		s2++;
682		while (s1 < &buf[len] && (*s1++ = *s3++))
683			;
684	}
685	if (s1 == &buf[len]) {
686		error("pathname too long: %s\n", file - 1);
687		return (NULL);
688	}
689	return (s2);
690}
691