1/*	$NetBSD: expand.c,v 1.17 2009/04/13 04:35:36 lukem Exp $	*/
2
3/*
4 * Copyright (c) 1983, 1993
5 *	The Regents of the University of California.  All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 *    notice, this list of conditions and the following disclaimer in the
14 *    documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the University nor the names of its contributors
16 *    may be used to endorse or promote products derived from this software
17 *    without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 */
31
32#include <sys/cdefs.h>
33#ifndef lint
34#if 0
35static char sccsid[] = "@(#)expand.c	8.1 (Berkeley) 6/9/93";
36#else
37__RCSID("$NetBSD: expand.c,v 1.17 2009/04/13 04:35:36 lukem Exp $");
38#endif
39#endif /* not lint */
40
41#include <sys/types.h>
42
43#include <errno.h>
44#include <pwd.h>
45
46#include "defs.h"
47
48#define	GAVSIZ	NCARGS / 6
49#define LC '{'
50#define RC '}'
51
52static char	shchars[] = "${[*?";
53
54int	which;		/* bit mask of types to expand */
55int	eargc;		/* expanded arg count */
56char	**eargv;	/* expanded arg vectors */
57char	*path;
58char	*pathp;
59char	*lastpathp;
60const char *tilde;		/* "~user" if not expanding tilde, else "" */
61char	*tpathp;
62int	nleft;
63
64int	expany;		/* any expansions done? */
65char	*entp;
66char	**sortbase;
67
68#define sort()	qsort((char *)sortbase, &eargv[eargc] - sortbase, \
69		      sizeof(*sortbase), argcmp), sortbase = &eargv[eargc]
70
71static void	Cat(const char *, const char *);
72static void	addpath(int);
73static int	amatch(char *, char *);
74static int	argcmp(const void *, const void *);
75static int	execbrc(char *, char *);
76static void	expsh(char *);
77static void	expstr(char *);
78static int	match(char *, char *);
79static void	matchdir(char *);
80
81/*
82 * Take a list of names and expand any macros, etc.
83 * wh = E_VARS if expanding variables.
84 * wh = E_SHELL if expanding shell characters.
85 * wh = E_TILDE if expanding `~'.
86 * or any of these or'ed together.
87 *
88 * Major portions of this were snarfed from csh/sh.glob.c.
89 */
90struct namelist *
91expand(struct namelist *list, int wh)
92{
93	struct namelist *nl, *prev;
94	int n;
95	char pathbuf[BUFSIZ];
96	char *argvbuf[GAVSIZ];
97
98	if (debug) {
99		printf("expand(%lx, %d)\nlist = ", (long)list, wh);
100		prnames(list);
101	}
102
103	if (wh == 0) {
104		char *cp;
105
106		for (nl = list; nl != NULL; nl = nl->n_next)
107			for (cp = nl->n_name; *cp; cp++)
108				*cp = *cp & TRIM;
109		return(list);
110	}
111
112	which = wh;
113	path = tpathp = pathp = pathbuf;
114	*pathp = '\0';
115	lastpathp = &path[sizeof pathbuf - 2];
116	tilde = "";
117	eargc = 0;
118	eargv = sortbase = argvbuf;
119	*eargv = 0;
120	nleft = NCARGS - 4;
121	/*
122	 * Walk the name list and expand names into eargv[];
123	 */
124	for (nl = list; nl != NULL; nl = nl->n_next)
125		expstr(nl->n_name);
126	/*
127	 * Take expanded list of names from eargv[] and build a new list.
128	 */
129	list = prev = NULL;
130	for (n = 0; n < eargc; n++) {
131		nl = makenl(NULL);
132		nl->n_name = eargv[n];
133		if (prev == NULL)
134			list = prev = nl;
135		else {
136			prev->n_next = nl;
137			prev = nl;
138		}
139	}
140	if (debug) {
141		printf("expanded list = ");
142		prnames(list);
143	}
144	return(list);
145}
146
147static void
148expstr(char *s)
149{
150	char *cp, *cp1;
151	struct namelist *tp;
152	char *tail;
153	char expbuf[BUFSIZ];
154	int savec, oeargc;
155	extern char homedir[];
156
157	if (s == NULL || *s == '\0')
158		return;
159
160	if ((which & E_VARS) && (cp = strchr(s, '$')) != NULL) {
161		*cp++ = '\0';
162		if (*cp == '\0') {
163			yyerror("no variable name after '$'");
164			return;
165		}
166		if (*cp == LC) {
167			cp++;
168			if ((tail = strchr(cp, RC)) == NULL) {
169				yyerror("unmatched '{'");
170				return;
171			}
172			*tail++ = savec = '\0';
173			if (*cp == '\0') {
174				yyerror("no variable name after '$'");
175				return;
176			}
177		} else {
178			tail = cp + 1;
179			savec = *tail;
180			*tail = '\0';
181		}
182		tp = lookup(cp, 0, 0);
183		if (savec != '\0')
184			*tail = savec;
185		if (tp != NULL) {
186			for (; tp != NULL; tp = tp->n_next) {
187				snprintf(expbuf, sizeof(expbuf), "%s%s%s", s,
188				    tp->n_name, tail);
189				expstr(expbuf);
190			}
191			return;
192		}
193		snprintf(expbuf, sizeof(expbuf), "%s%s", s, tail);
194		expstr(expbuf);
195		return;
196	}
197	if ((which & ~E_VARS) == 0 || !strcmp(s, "{") || !strcmp(s, "{}")) {
198		Cat(s, "");
199		sort();
200		return;
201	}
202	if (*s == '~') {
203		cp = ++s;
204		if (*cp == '\0' || *cp == '/') {
205			tilde = "~";
206			cp1 = homedir;
207		} else {
208			tilde = cp1 = expbuf;
209			*cp1++ = '~';
210			do
211				*cp1++ = *cp++;
212			while (*cp && *cp != '/');
213			*cp1 = '\0';
214			if (pw == NULL || strcmp(pw->pw_name, expbuf+1) != 0) {
215				if ((pw = getpwnam(expbuf+1)) == NULL) {
216					strlcat(expbuf, ": unknown user name",
217					    sizeof(expbuf));
218					yyerror(expbuf+1);
219					return;
220				}
221			}
222			cp1 = pw->pw_dir;
223			s = cp;
224		}
225		for (cp = path; (*cp++ = *cp1++) != 0; )
226			;
227		tpathp = pathp = cp - 1;
228	} else {
229		tpathp = pathp = path;
230		tilde = "";
231	}
232	*pathp = '\0';
233	if (!(which & E_SHELL)) {
234		if (which & E_TILDE)
235			Cat(path, s);
236		else
237			Cat(tilde, s);
238		sort();
239		return;
240	}
241	oeargc = eargc;
242	expany = 0;
243	expsh(s);
244	if (eargc == oeargc)
245		Cat(s, "");		/* "nonomatch" is set */
246	sort();
247}
248
249static int
250argcmp(const void *a1, const void *a2)
251{
252
253	return (strcmp(*(const char * const *)a1, *(const char * const *)a2));
254}
255
256/*
257 * If there are any Shell meta characters in the name,
258 * expand into a list, after searching directory
259 */
260static void
261expsh(char *s)
262{
263	char *cp;
264	char *spathp, *oldcp;
265	struct stat stb;
266
267	spathp = pathp;
268	cp = s;
269	while (!any(*cp, shchars)) {
270		if (*cp == '\0') {
271			if (!expany || stat(path, &stb) >= 0) {
272				if (which & E_TILDE)
273					Cat(path, "");
274				else
275					Cat(tilde, tpathp);
276			}
277			goto endit;
278		}
279		addpath(*cp++);
280	}
281	oldcp = cp;
282	while (cp > s && *cp != '/')
283		cp--, pathp--;
284	if (*cp == '/')
285		cp++, pathp++;
286	*pathp = '\0';
287	if (*oldcp == '{') {
288		execbrc(cp, NULL);
289		return;
290	}
291	matchdir(cp);
292endit:
293	pathp = spathp;
294	*pathp = '\0';
295}
296
297static void
298matchdir(char *pattern)
299{
300	struct stat stb;
301	struct dirent *dp;
302	DIR *dirp;
303
304	dirp = opendir(path);
305	if (dirp == NULL) {
306		if (expany)
307			return;
308		goto patherr2;
309	}
310	if (fstat(dirp->dd_fd, &stb) < 0)
311		goto patherr1;
312	if (!S_ISDIR(stb.st_mode)) {
313		errno = ENOTDIR;
314		goto patherr1;
315	}
316	while ((dp = readdir(dirp)) != NULL)
317		if (match(dp->d_name, pattern)) {
318			if (which & E_TILDE)
319				Cat(path, dp->d_name);
320			else {
321				strcpy(pathp, dp->d_name);
322				Cat(tilde, tpathp);
323				*pathp = '\0';
324			}
325		}
326	closedir(dirp);
327	return;
328
329patherr1:
330	closedir(dirp);
331patherr2:
332	strcat(path, ": ");
333	strcat(path, strerror(errno));
334	yyerror(path);
335}
336
337static int
338execbrc(char *p, char *s)
339{
340	char restbuf[BUFSIZ + 2];
341	char *pe, *pm, *pl;
342	int brclev = 0;
343	char *lm, savec, *spathp;
344
345	for (lm = restbuf; *p != '{'; *lm++ = *p++)
346		continue;
347	for (pe = ++p; *pe; pe++)
348		switch (*pe) {
349
350		case '{':
351			brclev++;
352			continue;
353
354		case '}':
355			if (brclev == 0)
356				goto pend;
357			brclev--;
358			continue;
359
360		case '[':
361			for (pe++; *pe && *pe != ']'; pe++)
362				continue;
363			if (!*pe)
364				yyerror("Missing ']'");
365			continue;
366		}
367pend:
368	if (brclev || !*pe) {
369		yyerror("Missing '}'");
370		return (0);
371	}
372	for (pl = pm = p; pm <= pe; pm++)
373		switch (*pm & (QUOTE|TRIM)) {
374
375		case '{':
376			brclev++;
377			continue;
378
379		case '}':
380			if (brclev) {
381				brclev--;
382				continue;
383			}
384			goto doit;
385
386		case ',':
387			if (brclev)
388				continue;
389doit:
390			savec = *pm;
391			*pm = 0;
392			strlcpy(lm, pl, sizeof(restbuf) - (lm - restbuf));
393			strlcat(restbuf, pe + 1, sizeof(restbuf));
394			*pm = savec;
395			if (s == 0) {
396				spathp = pathp;
397				expsh(restbuf);
398				pathp = spathp;
399				*pathp = 0;
400			} else if (amatch(s, restbuf))
401				return (1);
402			sort();
403			pl = pm + 1;
404			continue;
405
406		case '[':
407			for (pm++; *pm && *pm != ']'; pm++)
408				continue;
409			if (!*pm)
410				yyerror("Missing ']'");
411			continue;
412		}
413	return (0);
414}
415
416static int
417match(char *s, char *p)
418{
419	int c;
420	char *sentp;
421	char sexpany = expany;
422
423	if (*s == '.' && *p != '.')
424		return (0);
425	sentp = entp;
426	entp = s;
427	c = amatch(s, p);
428	entp = sentp;
429	expany = sexpany;
430	return (c);
431}
432
433static int
434amatch(char *s, char *p)
435{
436	int scc;
437	int ok, lc;
438	char *spathp;
439	struct stat stb;
440	int c, cc;
441
442	expany = 1;
443	for (;;) {
444		scc = *s++ & TRIM;
445		switch (c = *p++) {
446
447		case '{':
448			return (execbrc(p - 1, s - 1));
449
450		case '[':
451			ok = 0;
452			lc = 077777;
453			while ((cc = *p++) != 0) {
454				if (cc == ']') {
455					if (ok)
456						break;
457					return (0);
458				}
459				if (cc == '-') {
460					if (lc <= scc && scc <= *p++)
461						ok++;
462				} else
463					if (scc == (lc = cc))
464						ok++;
465			}
466			if (cc == 0) {
467				yyerror("Missing ']'");
468				return (0);
469			}
470			continue;
471
472		case '*':
473			if (!*p)
474				return (1);
475			if (*p == '/') {
476				p++;
477				goto slash;
478			}
479			for (s--; *s; s++)
480				if (amatch(s, p))
481					return (1);
482			return (0);
483
484		case '\0':
485			return (scc == '\0');
486
487		default:
488			if ((c & TRIM) != scc)
489				return (0);
490			continue;
491
492		case '?':
493			if (scc == '\0')
494				return (0);
495			continue;
496
497		case '/':
498			if (scc)
499				return (0);
500slash:
501			s = entp;
502			spathp = pathp;
503			while (*s)
504				addpath(*s++);
505			addpath('/');
506			if (stat(path, &stb) == 0 && S_ISDIR(stb.st_mode)) {
507				if (*p == '\0') {
508					if (which & E_TILDE)
509						Cat(path, "");
510					else
511						Cat(tilde, tpathp);
512				} else
513					expsh(p);
514			}
515			pathp = spathp;
516			*pathp = '\0';
517			return (0);
518		}
519	}
520}
521
522static void
523Cat(const char *s1, const char *s2)
524{
525	int len = strlen(s1) + strlen(s2) + 1;
526	char *s;
527
528	nleft -= len;
529	if (nleft <= 0 || ++eargc >= GAVSIZ)
530		yyerror("Arguments too long");
531	eargv[eargc] = 0;
532	eargv[eargc - 1] = s = malloc(len);
533	if (s == NULL)
534		fatal("ran out of memory\n");
535	while ((*s++ = *s1++ & TRIM) != 0)
536		;
537	s--;
538	while ((*s++ = *s2++ & TRIM) != 0)
539		;
540}
541
542static void
543addpath(int c)
544{
545
546	if (pathp >= lastpathp)
547		yyerror("Pathname too long");
548	else {
549		*pathp++ = c & TRIM;
550		*pathp = '\0';
551	}
552}
553
554/*
555 * Expand file names beginning with `~' into the
556 * user's home directory path name. Return a pointer in buf to the
557 * part corresponding to `file'.
558 */
559char *
560exptilde(char *expbuf, char *file)
561{
562	char *s1, *s2, *s3;
563	extern char homedir[];
564
565	if (*file != '~') {
566		strcpy(expbuf, file);
567		return(expbuf);
568	}
569	if (*++file == '\0') {
570		s2 = homedir;
571		s3 = NULL;
572	} else if (*file == '/') {
573		s2 = homedir;
574		s3 = file;
575	} else {
576		s3 = file;
577		while (*s3 && *s3 != '/')
578			s3++;
579		if (*s3 == '/')
580			*s3 = '\0';
581		else
582			s3 = NULL;
583		if (pw == NULL || strcmp(pw->pw_name, file) != 0) {
584			if ((pw = getpwnam(file)) == NULL) {
585				error("%s: unknown user name\n", file);
586				if (s3 != NULL)
587					*s3 = '/';
588				return(NULL);
589			}
590		}
591		if (s3 != NULL)
592			*s3 = '/';
593		s2 = pw->pw_dir;
594	}
595	for (s1 = expbuf; (*s1++ = *s2++) != 0; )
596		;
597	s2 = --s1;
598	if (s3 != NULL) {
599		s2++;
600		while ((*s1++ = *s3++) != 0)
601			;
602	}
603	return(s2);
604}
605