1/*	$NetBSD: expand.c,v 1.19 2023/08/03 08:03:19 mrg 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.19 2023/08/03 08:03:19 mrg 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	sortbase = NULL;
145	eargv = NULL;
146	path = tpathp = pathp = NULL;
147	lastpathp = NULL;
148	return(list);
149}
150
151static void
152expstr(char *s)
153{
154	char *cp, *cp1;
155	struct namelist *tp;
156	char *tail;
157	char expbuf[BUFSIZ];
158	int savec, oeargc;
159	extern char homedir[];
160
161	if (s == NULL || *s == '\0')
162		return;
163
164	if ((which & E_VARS) && (cp = strchr(s, '$')) != NULL) {
165		*cp++ = '\0';
166		if (*cp == '\0') {
167			yyerror("no variable name after '$'");
168			return;
169		}
170		if (*cp == LC) {
171			cp++;
172			if ((tail = strchr(cp, RC)) == NULL) {
173				yyerror("unmatched '{'");
174				return;
175			}
176			*tail++ = savec = '\0';
177			if (*cp == '\0') {
178				yyerror("no variable name after '$'");
179				return;
180			}
181		} else {
182			tail = cp + 1;
183			savec = *tail;
184			*tail = '\0';
185		}
186		tp = lookup(cp, 0, 0);
187		if (savec != '\0')
188			*tail = savec;
189		if (tp != NULL) {
190			for (; tp != NULL; tp = tp->n_next) {
191				snprintf(expbuf, sizeof(expbuf), "%s%s%s", s,
192				    tp->n_name, tail);
193				expstr(expbuf);
194			}
195			return;
196		}
197		snprintf(expbuf, sizeof(expbuf), "%s%s", s, tail);
198		expstr(expbuf);
199		return;
200	}
201	if ((which & ~E_VARS) == 0 || !strcmp(s, "{") || !strcmp(s, "{}")) {
202		Cat(s, "");
203		sort();
204		return;
205	}
206	if (*s == '~') {
207		cp = ++s;
208		if (*cp == '\0' || *cp == '/') {
209			tilde = "~";
210			cp1 = homedir;
211		} else {
212			tilde = cp1 = expbuf;
213			*cp1++ = '~';
214			do
215				*cp1++ = *cp++;
216			while (*cp && *cp != '/');
217			*cp1 = '\0';
218			if (pw == NULL || strcmp(pw->pw_name, expbuf+1) != 0) {
219				if ((pw = getpwnam(expbuf+1)) == NULL) {
220					strlcat(expbuf, ": unknown user name",
221					    sizeof(expbuf));
222					yyerror(expbuf+1);
223					return;
224				}
225			}
226			cp1 = pw->pw_dir;
227			s = cp;
228		}
229		for (cp = path; (*cp++ = *cp1++) != 0; )
230			;
231		tpathp = pathp = cp - 1;
232	} else {
233		tpathp = pathp = path;
234		tilde = "";
235	}
236	*pathp = '\0';
237	if (!(which & E_SHELL)) {
238		if (which & E_TILDE)
239			Cat(path, s);
240		else
241			Cat(tilde, s);
242		sort();
243		return;
244	}
245	oeargc = eargc;
246	expany = 0;
247	expsh(s);
248	if (eargc == oeargc)
249		Cat(s, "");		/* "nonomatch" is set */
250	sort();
251}
252
253static int
254argcmp(const void *a1, const void *a2)
255{
256
257	return (strcmp(*(const char * const *)a1, *(const char * const *)a2));
258}
259
260/*
261 * If there are any Shell meta characters in the name,
262 * expand into a list, after searching directory
263 */
264static void
265expsh(char *s)
266{
267	char *cp;
268	char *spathp, *oldcp;
269	struct stat stb;
270
271	spathp = pathp;
272	cp = s;
273	while (!any(*cp, shchars)) {
274		if (*cp == '\0') {
275			if (!expany || stat(path, &stb) >= 0) {
276				if (which & E_TILDE)
277					Cat(path, "");
278				else
279					Cat(tilde, tpathp);
280			}
281			goto endit;
282		}
283		addpath(*cp++);
284	}
285	oldcp = cp;
286	while (cp > s && *cp != '/')
287		cp--, pathp--;
288	if (*cp == '/')
289		cp++, pathp++;
290	*pathp = '\0';
291	if (*oldcp == '{') {
292		execbrc(cp, NULL);
293		return;
294	}
295	matchdir(cp);
296endit:
297	pathp = spathp;
298	*pathp = '\0';
299}
300
301static void
302matchdir(char *pattern)
303{
304	struct stat stb;
305	struct dirent *dp;
306	DIR *dirp;
307
308	dirp = opendir(path);
309	if (dirp == NULL) {
310		if (expany)
311			return;
312		goto patherr2;
313	}
314	if (fstat(dirp->dd_fd, &stb) < 0)
315		goto patherr1;
316	if (!S_ISDIR(stb.st_mode)) {
317		errno = ENOTDIR;
318		goto patherr1;
319	}
320	while ((dp = readdir(dirp)) != NULL)
321		if (match(dp->d_name, pattern)) {
322			if (which & E_TILDE)
323				Cat(path, dp->d_name);
324			else {
325				strcpy(pathp, dp->d_name);
326				Cat(tilde, tpathp);
327				*pathp = '\0';
328			}
329		}
330	closedir(dirp);
331	return;
332
333patherr1:
334	closedir(dirp);
335patherr2:
336	strcat(path, ": ");
337	strcat(path, strerror(errno));
338	yyerror(path);
339}
340
341static int
342execbrc(char *p, char *s)
343{
344	char restbuf[BUFSIZ + 2];
345	char *pe, *pm, *pl;
346	int brclev = 0;
347	char *lm, savec, *spathp;
348
349	for (lm = restbuf; *p != '{'; *lm++ = *p++)
350		continue;
351	for (pe = ++p; *pe; pe++)
352		switch (*pe) {
353
354		case '{':
355			brclev++;
356			continue;
357
358		case '}':
359			if (brclev == 0)
360				goto pend;
361			brclev--;
362			continue;
363
364		case '[':
365			for (pe++; *pe && *pe != ']'; pe++)
366				continue;
367			if (!*pe)
368				yyerror("Missing ']'");
369			continue;
370		}
371pend:
372	if (brclev || !*pe) {
373		yyerror("Missing '}'");
374		return (0);
375	}
376	for (pl = pm = p; pm <= pe; pm++)
377		switch (*pm & (QUOTE|TRIM)) {
378
379		case '{':
380			brclev++;
381			continue;
382
383		case '}':
384			if (brclev) {
385				brclev--;
386				continue;
387			}
388			goto doit;
389
390		case ',':
391			if (brclev)
392				continue;
393doit:
394			savec = *pm;
395			*pm = 0;
396			strlcpy(lm, pl, sizeof(restbuf) - (lm - restbuf));
397			strlcat(restbuf, pe + 1, sizeof(restbuf));
398			*pm = savec;
399			if (s == 0) {
400				spathp = pathp;
401				expsh(restbuf);
402				pathp = spathp;
403				*pathp = 0;
404			} else if (amatch(s, restbuf))
405				return (1);
406			sort();
407			pl = pm + 1;
408			continue;
409
410		case '[':
411			for (pm++; *pm && *pm != ']'; pm++)
412				continue;
413			if (!*pm)
414				yyerror("Missing ']'");
415			continue;
416		}
417	return (0);
418}
419
420static int
421match(char *s, char *p)
422{
423	int c;
424	char *sentp;
425	char sexpany = expany;
426
427	if (*s == '.' && *p != '.')
428		return (0);
429	sentp = entp;
430	entp = s;
431	c = amatch(s, p);
432	entp = sentp;
433	expany = sexpany;
434	return (c);
435}
436
437static int
438amatch(char *s, char *p)
439{
440	int scc;
441	int ok, lc;
442	char *spathp;
443	struct stat stb;
444	int c, cc;
445
446	expany = 1;
447	for (;;) {
448		scc = *s++ & TRIM;
449		switch (c = *p++) {
450
451		case '{':
452			return (execbrc(p - 1, s - 1));
453
454		case '[':
455			ok = 0;
456			lc = 077777;
457			while ((cc = *p++) != 0) {
458				if (cc == ']') {
459					if (ok)
460						break;
461					return (0);
462				}
463				if (cc == '-') {
464					if (lc <= scc && scc <= *p++)
465						ok++;
466				} else
467					if (scc == (lc = cc))
468						ok++;
469			}
470			if (cc == 0) {
471				yyerror("Missing ']'");
472				return (0);
473			}
474			continue;
475
476		case '*':
477			if (!*p)
478				return (1);
479			if (*p == '/') {
480				p++;
481				goto slash;
482			}
483			for (s--; *s; s++)
484				if (amatch(s, p))
485					return (1);
486			return (0);
487
488		case '\0':
489			return (scc == '\0');
490
491		default:
492			if ((c & TRIM) != scc)
493				return (0);
494			continue;
495
496		case '?':
497			if (scc == '\0')
498				return (0);
499			continue;
500
501		case '/':
502			if (scc)
503				return (0);
504slash:
505			s = entp;
506			spathp = pathp;
507			while (*s)
508				addpath(*s++);
509			addpath('/');
510			if (stat(path, &stb) == 0 && S_ISDIR(stb.st_mode)) {
511				if (*p == '\0') {
512					if (which & E_TILDE)
513						Cat(path, "");
514					else
515						Cat(tilde, tpathp);
516				} else
517					expsh(p);
518			}
519			pathp = spathp;
520			*pathp = '\0';
521			return (0);
522		}
523	}
524}
525
526static void
527Cat(const char *s1, const char *s2)
528{
529	int len = strlen(s1) + strlen(s2) + 1;
530	char *s;
531
532	nleft -= len;
533	if (nleft <= 0 || ++eargc >= GAVSIZ)
534		yyerror("Arguments too long");
535	eargv[eargc] = 0;
536	eargv[eargc - 1] = s = malloc(len);
537	if (s == NULL)
538		fatal("ran out of memory\n");
539	while ((*s++ = *s1++ & TRIM) != 0)
540		;
541	s--;
542	while ((*s++ = *s2++ & TRIM) != 0)
543		;
544}
545
546static void
547addpath(int c)
548{
549
550	if (pathp >= lastpathp)
551		yyerror("Pathname too long");
552	else {
553		*pathp++ = c & TRIM;
554		*pathp = '\0';
555	}
556}
557
558/*
559 * Expand file names beginning with `~' into the
560 * user's home directory path name. Return a pointer in buf to the
561 * part corresponding to `file'.
562 */
563char *
564exptilde(char *expbuf, char *file)
565{
566	char *s1, *s2, *s3;
567	extern char homedir[];
568
569	if (*file != '~') {
570		strcpy(expbuf, file);
571		return(expbuf);
572	}
573	if (*++file == '\0') {
574		s2 = homedir;
575		s3 = NULL;
576	} else if (*file == '/') {
577		s2 = homedir;
578		s3 = file;
579	} else {
580		s3 = file;
581		while (*s3 && *s3 != '/')
582			s3++;
583		if (*s3 == '/')
584			*s3 = '\0';
585		else
586			s3 = NULL;
587		if (pw == NULL || strcmp(pw->pw_name, file) != 0) {
588			if ((pw = getpwnam(file)) == NULL) {
589				error("%s: unknown user name\n", file);
590				if (s3 != NULL)
591					*s3 = '/';
592				return(NULL);
593			}
594		}
595		if (s3 != NULL)
596			*s3 = '/';
597		s2 = pw->pw_dir;
598	}
599	for (s1 = expbuf; (*s1++ = *s2++) != 0; )
600		;
601	s2 = --s1;
602	if (s3 != NULL) {
603		s2++;
604		while ((*s1++ = *s3++) != 0)
605			;
606	}
607	return(s2);
608}
609