1/*	$OpenBSD: misc.c,v 1.37 2009/04/19 20:34:05 sthen Exp $	*/
2/*	$OpenBSD: path.c,v 1.12 2005/03/30 17:16:37 deraadt Exp $	*/
3
4/*-
5 * Copyright (c) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
6 *	Thorsten Glaser <tg@mirbsd.org>
7 *
8 * Provided that these terms and disclaimer and all copyright notices
9 * are retained or reproduced in an accompanying document, permission
10 * is granted to deal in this work without restriction, including un-
11 * limited rights to use, publicly perform, distribute, sell, modify,
12 * merge, give away, or sublicence.
13 *
14 * This work is provided "AS IS" and WITHOUT WARRANTY of any kind, to
15 * the utmost extent permitted by applicable law, neither express nor
16 * implied; without malicious intent or gross negligence. In no event
17 * may a licensor, author or contributor be held liable for indirect,
18 * direct, other damage, loss, or other issues arising in any way out
19 * of dealing in the work, even if advised of the possibility of such
20 * damage or existence of a defect, except proven that it results out
21 * of said person's immediate fault when using the work as intended.
22 */
23
24#include "sh.h"
25#if !HAVE_GETRUSAGE
26#include <sys/times.h>
27#endif
28#if HAVE_GRP_H
29#include <grp.h>
30#endif
31
32__RCSID("$MirOS: src/bin/mksh/misc.c,v 1.172 2011/09/07 15:24:18 tg Exp $");
33
34/* type bits for unsigned char */
35unsigned char chtypes[UCHAR_MAX + 1];
36
37static const unsigned char *pat_scan(const unsigned char *,
38    const unsigned char *, bool);
39static int do_gmatch(const unsigned char *, const unsigned char *,
40    const unsigned char *, const unsigned char *);
41static const unsigned char *cclass(const unsigned char *, int);
42#ifdef TIOCSCTTY
43static void chvt(const char *);
44#endif
45
46/*XXX this should go away */
47static int make_path(const char *, const char *, char **, XString *, int *);
48
49#ifdef SETUID_CAN_FAIL_WITH_EAGAIN
50/* we don't need to check for other codes, EPERM won't happen */
51#define DO_SETUID(func, argvec) do {					\
52	if ((func argvec) && errno == EAGAIN)				\
53		errorf("%s failed with EAGAIN, probably due to a"	\
54		    " too low process limit; aborting", #func);		\
55} while (/* CONSTCOND */ 0)
56#else
57#define DO_SETUID(func, argvec) func argvec
58#endif
59
60/*
61 * Fast character classes
62 */
63void
64setctypes(const char *s, int t)
65{
66	unsigned int i;
67
68	if (t & C_IFS) {
69		for (i = 0; i < UCHAR_MAX + 1; i++)
70			chtypes[i] &= ~C_IFS;
71		/* include \0 in C_IFS */
72		chtypes[0] |= C_IFS;
73	}
74	while (*s != 0)
75		chtypes[(unsigned char)*s++] |= t;
76}
77
78void
79initctypes(void)
80{
81	int c;
82
83	for (c = 'a'; c <= 'z'; c++)
84		chtypes[c] |= C_ALPHA;
85	for (c = 'A'; c <= 'Z'; c++)
86		chtypes[c] |= C_ALPHA;
87	chtypes['_'] |= C_ALPHA;
88	setctypes("0123456789", C_DIGIT);
89	/* \0 added automatically */
90	setctypes(" \t\n|&;<>()", C_LEX1);
91	setctypes("*@#!$-?", C_VAR1);
92	setctypes(" \t\n", C_IFSWS);
93	setctypes("=-+?", C_SUBOP1);
94	setctypes("\t\n \"#$&'()*;<=>?[\\]`|", C_QUOTE);
95}
96
97/* called from XcheckN() to grow buffer */
98char *
99Xcheck_grow_(XString *xsp, const char *xp, size_t more)
100{
101	const char *old_beg = xsp->beg;
102
103	if (more < xsp->len)
104		more = xsp->len;
105	/* (xsp->len + X_EXTRA) never overflows */
106	checkoktoadd(more, xsp->len + X_EXTRA);
107	xsp->beg = aresize(xsp->beg, (xsp->len += more) + X_EXTRA, xsp->areap);
108	xsp->end = xsp->beg + xsp->len;
109	return (xsp->beg + (xp - old_beg));
110}
111
112#define SHFLAGS_DEFNS
113#include "sh_flags.h"
114
115const struct shoption options[] = {
116#define SHFLAGS_ITEMS
117#include "sh_flags.h"
118};
119
120/*
121 * translate -o option into F* constant (also used for test -o option)
122 */
123size_t
124option(const char *n)
125{
126	size_t i;
127
128	if ((n[0] == '-' || n[0] == '+') && n[1] && !n[2]) {
129		for (i = 0; i < NELEM(options); i++)
130			if (options[i].c == n[1])
131				return (i);
132	} else for (i = 0; i < NELEM(options); i++)
133		if (options[i].name && strcmp(options[i].name, n) == 0)
134			return (i);
135
136	return ((size_t)-1);
137}
138
139struct options_info {
140	int opt_width;
141	int opts[NELEM(options)];
142};
143
144static char *options_fmt_entry(char *, size_t, int, const void *);
145static void printoptions(bool);
146
147/* format a single select menu item */
148static char *
149options_fmt_entry(char *buf, size_t buflen, int i, const void *arg)
150{
151	const struct options_info *oi = (const struct options_info *)arg;
152
153	shf_snprintf(buf, buflen, "%-*s %s",
154	    oi->opt_width, options[oi->opts[i]].name,
155	    Flag(oi->opts[i]) ? "on" : "off");
156	return (buf);
157}
158
159static void
160printoptions(bool verbose)
161{
162	size_t i = 0;
163
164	if (verbose) {
165		ssize_t n = 0, len, octs = 0;
166		struct options_info oi;
167
168		/* verbose version */
169		shf_puts("Current option settings\n", shl_stdout);
170
171		oi.opt_width = 0;
172		while (i < NELEM(options)) {
173			if (options[i].name) {
174				oi.opts[n++] = i;
175				len = strlen(options[i].name);
176				if (len > octs)
177					octs = len;
178				len = utf_mbswidth(options[i].name);
179				if (len > oi.opt_width)
180					oi.opt_width = len;
181			}
182			++i;
183		}
184		print_columns(shl_stdout, n, options_fmt_entry, &oi,
185		    octs + 4, oi.opt_width + 4, true);
186	} else {
187		/* short version like AT&T ksh93 */
188		shf_puts(Tset, shl_stdout);
189		while (i < (int)NELEM(options)) {
190			if (Flag(i) && options[i].name)
191				shprintf("%s %s %s", null, "-o",
192				    options[i].name);
193			++i;
194		}
195		shf_putc('\n', shl_stdout);
196	}
197}
198
199char *
200getoptions(void)
201{
202	size_t i;
203	char m[(int)FNFLAGS + 1];
204	char *cp = m;
205
206	for (i = 0; i < NELEM(options); i++)
207		if (options[i].c && Flag(i))
208			*cp++ = options[i].c;
209	strndupx(cp, m, cp - m, ATEMP);
210	return (cp);
211}
212
213/* change a Flag(*) value; takes care of special actions */
214void
215change_flag(enum sh_flag f, int what, unsigned int newval)
216{
217	unsigned char oldval;
218
219	oldval = Flag(f);
220	/* needed for tristates */
221	Flag(f) = newval ? 1 : 0;
222#ifndef MKSH_UNEMPLOYED
223	if (f == FMONITOR) {
224		if (what != OF_CMDLINE && newval != oldval)
225			j_change();
226	} else
227#endif
228	  if ((
229#if !MKSH_S_NOVI
230	    f == FVI ||
231#endif
232	    f == FEMACS || f == FGMACS) && newval) {
233#if !MKSH_S_NOVI
234		Flag(FVI) =
235#endif
236		    Flag(FEMACS) = Flag(FGMACS) = 0;
237		Flag(f) = (unsigned char)newval;
238	} else if (f == FPRIVILEGED && oldval && !newval) {
239		/* Turning off -p? */
240
241		/*XXX this can probably be optimised */
242		kshegid = kshgid = getgid();
243#if HAVE_SETRESUGID
244		DO_SETUID(setresgid, (kshegid, kshegid, kshegid));
245#if HAVE_SETGROUPS
246		/* setgroups doesn't EAGAIN on Linux */
247		setgroups(1, &kshegid);
248#endif
249		DO_SETUID(setresuid, (ksheuid, ksheuid, ksheuid));
250#else
251		/* seteuid, setegid, setgid don't EAGAIN on Linux */
252		seteuid(ksheuid = kshuid = getuid());
253		DO_SETUID(setuid, (ksheuid));
254		setegid(kshegid);
255		setgid(kshegid);
256#endif
257	} else if ((f == FPOSIX || f == FSH) && newval) {
258		Flag(FPOSIX) = Flag(FSH) = Flag(FBRACEEXPAND) = 0;
259		Flag(f) = (unsigned char)newval;
260	}
261	/* Changing interactive flag? */
262	if (f == FTALKING) {
263		if ((what == OF_CMDLINE || what == OF_SET) && procpid == kshpid)
264			Flag(FTALKING_I) = (unsigned char)newval;
265	}
266}
267
268/*
269 * Parse command line and set command arguments. Returns the index of
270 * non-option arguments, -1 if there is an error.
271 */
272int
273parse_args(const char **argv,
274    /* OF_CMDLINE or OF_SET */
275    int what,
276    bool *setargsp)
277{
278	static char cmd_opts[NELEM(options) + 5]; /* o:T:\0 */
279	static char set_opts[NELEM(options) + 6]; /* A:o;s\0 */
280	char set, *opts;
281	const char *array = NULL;
282	Getopt go;
283	size_t i;
284	int optc, arrayset = 0;
285	bool sortargs = false;
286
287	/* First call? Build option strings... */
288	if (cmd_opts[0] == '\0') {
289		char *p = cmd_opts, *q = set_opts;
290
291		/* see cmd_opts[] declaration */
292		*p++ = 'o';
293		*p++ = ':';
294#if !defined(MKSH_SMALL) || defined(TIOCSCTTY)
295		*p++ = 'T';
296		*p++ = ':';
297#endif
298		/* see set_opts[] declaration */
299		*q++ = 'A';
300		*q++ = ':';
301		*q++ = 'o';
302		*q++ = ';';
303		*q++ = 's';
304
305		for (i = 0; i < NELEM(options); i++) {
306			if (options[i].c) {
307				if (options[i].flags & OF_CMDLINE)
308					*p++ = options[i].c;
309				if (options[i].flags & OF_SET)
310					*q++ = options[i].c;
311			}
312		}
313		*p = '\0';
314		*q = '\0';
315	}
316
317	if (what == OF_CMDLINE) {
318		const char *p = argv[0], *q;
319		/*
320		 * Set FLOGIN before parsing options so user can clear
321		 * flag using +l.
322		 */
323		if (*p != '-')
324			for (q = p; *q; )
325				if (*q++ == '/')
326					p = q;
327		Flag(FLOGIN) = (*p == '-');
328		opts = cmd_opts;
329	} else if (what == OF_FIRSTTIME) {
330		opts = cmd_opts;
331	} else
332		opts = set_opts;
333	ksh_getopt_reset(&go, GF_ERROR|GF_PLUSOPT);
334	while ((optc = ksh_getopt(argv, &go, opts)) != -1) {
335		set = (go.info & GI_PLUS) ? 0 : 1;
336		switch (optc) {
337		case 'A':
338			if (what == OF_FIRSTTIME)
339				break;
340			arrayset = set ? 1 : -1;
341			array = go.optarg;
342			break;
343
344		case 'o':
345			if (what == OF_FIRSTTIME)
346				break;
347			if (go.optarg == NULL) {
348				/*
349				 * lone -o: print options
350				 *
351				 * Note that on the command line, -o requires
352				 * an option (ie, can't get here if what is
353				 * OF_CMDLINE).
354				 */
355				printoptions(set);
356				break;
357			}
358			i = option(go.optarg);
359			if ((i != (size_t)-1) && set == Flag(i))
360				/*
361				 * Don't check the context if the flag
362				 * isn't changing - makes "set -o interactive"
363				 * work if you're already interactive. Needed
364				 * if the output of "set +o" is to be used.
365				 */
366				;
367			else if ((i != (size_t)-1) && (options[i].flags & what))
368				change_flag((enum sh_flag)i, what, set);
369			else {
370				bi_errorf("%s: %s", go.optarg, "bad option");
371				return (-1);
372			}
373			break;
374
375#if !defined(MKSH_SMALL) || defined(TIOCSCTTY)
376		case 'T':
377			if (what != OF_FIRSTTIME)
378				break;
379#ifndef TIOCSCTTY
380			errorf("no TIOCSCTTY ioctl");
381#else
382			change_flag(FTALKING, OF_CMDLINE, 1);
383			chvt(go.optarg);
384			break;
385#endif
386#endif
387
388		case '?':
389			return (-1);
390
391		default:
392			if (what == OF_FIRSTTIME)
393				break;
394			/* -s: sort positional params (AT&T ksh stupidity) */
395			if (what == OF_SET && optc == 's') {
396				sortargs = true;
397				break;
398			}
399			for (i = 0; i < NELEM(options); i++)
400				if (optc == options[i].c &&
401				    (what & options[i].flags)) {
402					change_flag((enum sh_flag)i, what, set);
403					break;
404				}
405			if (i == NELEM(options))
406				internal_errorf("parse_args: '%c'", optc);
407		}
408	}
409	if (!(go.info & GI_MINUSMINUS) && argv[go.optind] &&
410	    (argv[go.optind][0] == '-' || argv[go.optind][0] == '+') &&
411	    argv[go.optind][1] == '\0') {
412		/* lone - clears -v and -x flags */
413		if (argv[go.optind][0] == '-')
414			Flag(FVERBOSE) = Flag(FXTRACE) = 0;
415		/* set skips lone - or + option */
416		go.optind++;
417	}
418	if (setargsp)
419		/* -- means set $#/$* even if there are no arguments */
420		*setargsp = !arrayset && ((go.info & GI_MINUSMINUS) ||
421		    argv[go.optind]);
422
423	if (arrayset) {
424		const char *ccp = NULL;
425
426		if (*array)
427			ccp = skip_varname(array, false);
428		if (!ccp || !(!ccp[0] || (ccp[0] == '+' && !ccp[1]))) {
429			bi_errorf("%s: %s", array, "is not an identifier");
430			return (-1);
431		}
432	}
433	if (sortargs) {
434		for (i = go.optind; argv[i]; i++)
435			;
436		qsort(&argv[go.optind], i - go.optind, sizeof(void *),
437		    xstrcmp);
438	}
439	if (arrayset)
440		go.optind += set_array(array, tobool(arrayset > 0),
441		    argv + go.optind);
442
443	return (go.optind);
444}
445
446/* parse a decimal number: returns 0 if string isn't a number, 1 otherwise */
447int
448getn(const char *s, int *ai)
449{
450	int i, c, rv = 0;
451	bool neg = false;
452
453	do {
454		c = *s++;
455	} while (ksh_isspace(c));
456	if (c == '-') {
457		neg = true;
458		c = *s++;
459	} else if (c == '+')
460		c = *s++;
461	*ai = i = 0;
462	do {
463		if (!ksh_isdigit(c))
464			goto getn_out;
465		i *= 10;
466		if (i < *ai)
467			/* overflow */
468			goto getn_out;
469		i += c - '0';
470		*ai = i;
471	} while ((c = *s++));
472	rv = 1;
473
474 getn_out:
475	if (neg)
476		*ai = -*ai;
477	return (rv);
478}
479
480/* getn() that prints error */
481int
482bi_getn(const char *as, int *ai)
483{
484	int rv;
485
486	if (!(rv = getn(as, ai)))
487		bi_errorf("%s: %s", as, "bad number");
488	return (rv);
489}
490
491/**
492 * pattern simplifications:
493 * - @(x) -> x (not @(x|y) though)
494 * - ** -> *
495 */
496static void *
497simplify_gmatch_pattern(const unsigned char *sp)
498{
499	uint8_t c;
500	unsigned char *cp, *dp;
501	const unsigned char *ps, *se;
502
503	cp = alloc(strlen((const void *)sp) + 1, ATEMP);
504	goto simplify_gmatch_pat1a;
505
506	/* foo@(b@(a)r)b@(a|a)z -> foobarb@(a|a)z */
507 simplify_gmatch_pat1:
508	sp = cp;
509 simplify_gmatch_pat1a:
510	dp = cp;
511	se = sp + strlen((const void *)sp);
512	while ((c = *sp++)) {
513		if (!ISMAGIC(c)) {
514			*dp++ = c;
515			continue;
516		}
517		switch ((c = *sp++)) {
518		case 0x80|'@':
519		/* simile for @ */
520		case 0x80|' ':
521			/* check whether it has only one clause */
522			ps = pat_scan(sp, se, true);
523			if (!ps || ps[-1] != /*(*/ ')')
524				/* nope */
525				break;
526			/* copy inner clause until matching close */
527			ps -= 2;
528			while ((const unsigned char *)sp < ps)
529				*dp++ = *sp++;
530			/* skip MAGIC and closing parenthesis */
531			sp += 2;
532			/* copy the rest of the pattern */
533			memmove(dp, sp, strlen((const void *)sp) + 1);
534			/* redo from start */
535			goto simplify_gmatch_pat1;
536		}
537		*dp++ = MAGIC;
538		*dp++ = c;
539	}
540	*dp = '\0';
541
542	/* collapse adjacent asterisk wildcards */
543	sp = dp = cp;
544	while ((c = *sp++)) {
545		if (!ISMAGIC(c)) {
546			*dp++ = c;
547			continue;
548		}
549		switch ((c = *sp++)) {
550		case '*':
551			while (ISMAGIC(sp[0]) && sp[1] == c)
552				sp += 2;
553			break;
554		}
555		*dp++ = MAGIC;
556		*dp++ = c;
557	}
558	*dp = '\0';
559
560	/* return the result, allocated from ATEMP */
561	return (cp);
562}
563
564/* -------- gmatch.c -------- */
565
566/*
567 * int gmatch(string, pattern)
568 * char *string, *pattern;
569 *
570 * Match a pattern as in sh(1).
571 * pattern character are prefixed with MAGIC by expand.
572 */
573int
574gmatchx(const char *s, const char *p, bool isfile)
575{
576	const char *se, *pe;
577	char *pnew;
578	int rv;
579
580	if (s == NULL || p == NULL)
581		return (0);
582
583	se = s + strlen(s);
584	pe = p + strlen(p);
585	/*
586	 * isfile is false iff no syntax check has been done on
587	 * the pattern. If check fails, just to a strcmp().
588	 */
589	if (!isfile && !has_globbing(p, pe)) {
590		size_t len = pe - p + 1;
591		char tbuf[64];
592		char *t = len <= sizeof(tbuf) ? tbuf : alloc(len, ATEMP);
593		debunk(t, p, len);
594		return (!strcmp(t, s));
595	}
596
597	/*
598	 * since the do_gmatch() engine sucks so much, we must do some
599	 * pattern simplifications
600	 */
601	pnew = simplify_gmatch_pattern((const unsigned char *)p);
602	pe = pnew + strlen(pnew);
603
604	rv = do_gmatch((const unsigned char *)s, (const unsigned char *)se,
605	    (const unsigned char *)pnew, (const unsigned char *)pe);
606	afree(pnew, ATEMP);
607	return (rv);
608}
609
610/**
611 * Returns if p is a syntacticly correct globbing pattern, false
612 * if it contains no pattern characters or if there is a syntax error.
613 * Syntax errors are:
614 *	- [ with no closing ]
615 *	- imbalanced $(...) expression
616 *	- [...] and *(...) not nested (eg, [a$(b|]c), *(a[b|c]d))
617 */
618/*XXX
619 * - if no magic,
620 *	if dest given, copy to dst
621 *	return ?
622 * - if magic && (no globbing || syntax error)
623 *	debunk to dst
624 *	return ?
625 * - return ?
626 */
627int
628has_globbing(const char *xp, const char *xpe)
629{
630	const unsigned char *p = (const unsigned char *) xp;
631	const unsigned char *pe = (const unsigned char *) xpe;
632	int c;
633	int nest = 0, bnest = 0;
634	bool saw_glob = false;
635	/* inside [...] */
636	bool in_bracket = false;
637
638	for (; p < pe; p++) {
639		if (!ISMAGIC(*p))
640			continue;
641		if ((c = *++p) == '*' || c == '?')
642			saw_glob = true;
643		else if (c == '[') {
644			if (!in_bracket) {
645				saw_glob = true;
646				in_bracket = true;
647				if (ISMAGIC(p[1]) && p[2] == NOT)
648					p += 2;
649				if (ISMAGIC(p[1]) && p[2] == ']')
650					p += 2;
651			}
652			/*XXX Do we need to check ranges here? POSIX Q */
653		} else if (c == ']') {
654			if (in_bracket) {
655				if (bnest)
656					/* [a*(b]) */
657					return (0);
658				in_bracket = false;
659			}
660		} else if ((c & 0x80) && vstrchr("*+?@! ", c & 0x7f)) {
661			saw_glob = true;
662			if (in_bracket)
663				bnest++;
664			else
665				nest++;
666		} else if (c == '|') {
667			if (in_bracket && !bnest)
668				/* *(a[foo|bar]) */
669				return (0);
670		} else if (c == /*(*/ ')') {
671			if (in_bracket) {
672				if (!bnest--)
673					/* *(a[b)c] */
674					return (0);
675			} else if (nest)
676				nest--;
677		}
678		/*
679		 * else must be a MAGIC-MAGIC, or MAGIC-!,
680		 * MAGIC--, MAGIC-], MAGIC-{, MAGIC-, MAGIC-}
681		 */
682	}
683	return (saw_glob && !in_bracket && !nest);
684}
685
686/* Function must return either 0 or 1 (assumed by code for 0x80|'!') */
687static int
688do_gmatch(const unsigned char *s, const unsigned char *se,
689    const unsigned char *p, const unsigned char *pe)
690{
691	int sc, pc;
692	const unsigned char *prest, *psub, *pnext;
693	const unsigned char *srest;
694
695	if (s == NULL || p == NULL)
696		return (0);
697	while (p < pe) {
698		pc = *p++;
699		sc = s < se ? *s : '\0';
700		s++;
701		if (!ISMAGIC(pc)) {
702			if (sc != pc)
703				return (0);
704			continue;
705		}
706		switch (*p++) {
707		case '[':
708			if (sc == 0 || (p = cclass(p, sc)) == NULL)
709				return (0);
710			break;
711
712		case '?':
713			if (sc == 0)
714				return (0);
715			if (UTFMODE) {
716				--s;
717				s += utf_ptradj((const void *)s);
718			}
719			break;
720
721		case '*':
722			if (p == pe)
723				return (1);
724			s--;
725			do {
726				if (do_gmatch(s, se, p, pe))
727					return (1);
728			} while (s++ < se);
729			return (0);
730
731		/**
732		 * [*+?@!](pattern|pattern|..)
733		 * This is also needed for ${..%..}, etc.
734		 */
735
736		/* matches one or more times */
737		case 0x80|'+':
738		/* matches zero or more times */
739		case 0x80|'*':
740			if (!(prest = pat_scan(p, pe, false)))
741				return (0);
742			s--;
743			/* take care of zero matches */
744			if (p[-1] == (0x80 | '*') &&
745			    do_gmatch(s, se, prest, pe))
746				return (1);
747			for (psub = p; ; psub = pnext) {
748				pnext = pat_scan(psub, pe, true);
749				for (srest = s; srest <= se; srest++) {
750					if (do_gmatch(s, srest, psub, pnext - 2) &&
751					    (do_gmatch(srest, se, prest, pe) ||
752					    (s != srest && do_gmatch(srest,
753					    se, p - 2, pe))))
754						return (1);
755				}
756				if (pnext == prest)
757					break;
758			}
759			return (0);
760
761		/* matches zero or once */
762		case 0x80|'?':
763		/* matches one of the patterns */
764		case 0x80|'@':
765		/* simile for @ */
766		case 0x80|' ':
767			if (!(prest = pat_scan(p, pe, false)))
768				return (0);
769			s--;
770			/* Take care of zero matches */
771			if (p[-1] == (0x80 | '?') &&
772			    do_gmatch(s, se, prest, pe))
773				return (1);
774			for (psub = p; ; psub = pnext) {
775				pnext = pat_scan(psub, pe, true);
776				srest = prest == pe ? se : s;
777				for (; srest <= se; srest++) {
778					if (do_gmatch(s, srest, psub, pnext - 2) &&
779					    do_gmatch(srest, se, prest, pe))
780						return (1);
781				}
782				if (pnext == prest)
783					break;
784			}
785			return (0);
786
787		/* matches none of the patterns */
788		case 0x80|'!':
789			if (!(prest = pat_scan(p, pe, false)))
790				return (0);
791			s--;
792			for (srest = s; srest <= se; srest++) {
793				int matched = 0;
794
795				for (psub = p; ; psub = pnext) {
796					pnext = pat_scan(psub, pe, true);
797					if (do_gmatch(s, srest, psub,
798					    pnext - 2)) {
799						matched = 1;
800						break;
801					}
802					if (pnext == prest)
803						break;
804				}
805				if (!matched &&
806				    do_gmatch(srest, se, prest, pe))
807					return (1);
808			}
809			return (0);
810
811		default:
812			if (sc != p[-1])
813				return (0);
814			break;
815		}
816	}
817	return (s == se);
818}
819
820static const unsigned char *
821cclass(const unsigned char *p, int sub)
822{
823	int c, d, notp, found = 0;
824	const unsigned char *orig_p = p;
825
826	if ((notp = (ISMAGIC(*p) && *++p == NOT)))
827		p++;
828	do {
829		c = *p++;
830		if (ISMAGIC(c)) {
831			c = *p++;
832			if ((c & 0x80) && !ISMAGIC(c)) {
833				/* extended pattern matching: *+?@! */
834				c &= 0x7F;
835				/* XXX the ( char isn't handled as part of [] */
836				if (c == ' ')
837					/* simile for @: plain (..) */
838					c = '(' /*)*/;
839			}
840		}
841		if (c == '\0')
842			/* No closing ] - act as if the opening [ was quoted */
843			return (sub == '[' ? orig_p : NULL);
844		if (ISMAGIC(p[0]) && p[1] == '-' &&
845		    (!ISMAGIC(p[2]) || p[3] != ']')) {
846			/* MAGIC- */
847			p += 2;
848			d = *p++;
849			if (ISMAGIC(d)) {
850				d = *p++;
851				if ((d & 0x80) && !ISMAGIC(d))
852					d &= 0x7f;
853			}
854			/* POSIX says this is an invalid expression */
855			if (c > d)
856				return (NULL);
857		} else
858			d = c;
859		if (c == sub || (c <= sub && sub <= d))
860			found = 1;
861	} while (!(ISMAGIC(p[0]) && p[1] == ']'));
862
863	return ((found != notp) ? p+2 : NULL);
864}
865
866/* Look for next ) or | (if match_sep) in *(foo|bar) pattern */
867static const unsigned char *
868pat_scan(const unsigned char *p, const unsigned char *pe, bool match_sep)
869{
870	int nest = 0;
871
872	for (; p < pe; p++) {
873		if (!ISMAGIC(*p))
874			continue;
875		if ((*++p == /*(*/ ')' && nest-- == 0) ||
876		    (*p == '|' && match_sep && nest == 0))
877			return (p + 1);
878		if ((*p & 0x80) && vstrchr("*+?@! ", *p & 0x7f))
879			nest++;
880	}
881	return (NULL);
882}
883
884int
885xstrcmp(const void *p1, const void *p2)
886{
887	return (strcmp(*(const char * const *)p1, *(const char * const *)p2));
888}
889
890/* Initialise a Getopt structure */
891void
892ksh_getopt_reset(Getopt *go, int flags)
893{
894	go->optind = 1;
895	go->optarg = NULL;
896	go->p = 0;
897	go->flags = flags;
898	go->info = 0;
899	go->buf[1] = '\0';
900}
901
902
903/**
904 * getopt() used for shell built-in commands, the getopts command, and
905 * command line options.
906 * A leading ':' in options means don't print errors, instead return '?'
907 * or ':' and set go->optarg to the offending option character.
908 * If GF_ERROR is set (and option doesn't start with :), errors result in
909 * a call to bi_errorf().
910 *
911 * Non-standard features:
912 *	- ';' is like ':' in options, except the argument is optional
913 *	  (if it isn't present, optarg is set to 0).
914 *	  Used for 'set -o'.
915 *	- ',' is like ':' in options, except the argument always immediately
916 *	  follows the option character (optarg is set to the null string if
917 *	  the option is missing).
918 *	  Used for 'read -u2', 'print -u2' and fc -40.
919 *	- '#' is like ':' in options, expect that the argument is optional
920 *	  and must start with a digit. If the argument doesn't start with a
921 *	  digit, it is assumed to be missing and normal option processing
922 *	  continues (optarg is set to 0 if the option is missing).
923 *	  Used for 'typeset -LZ4'.
924 *	- accepts +c as well as -c IF the GF_PLUSOPT flag is present. If an
925 *	  option starting with + is accepted, the GI_PLUS flag will be set
926 *	  in go->info.
927 */
928int
929ksh_getopt(const char **argv, Getopt *go, const char *optionsp)
930{
931	char c;
932	const char *o;
933
934	if (go->p == 0 || (c = argv[go->optind - 1][go->p]) == '\0') {
935		const char *arg = argv[go->optind], flag = arg ? *arg : '\0';
936
937		go->p = 1;
938		if (flag == '-' && arg[1] == '-' && arg[2] == '\0') {
939			go->optind++;
940			go->p = 0;
941			go->info |= GI_MINUSMINUS;
942			return (-1);
943		}
944		if (arg == NULL ||
945		    ((flag != '-' ) &&
946		    /* neither a - nor a + (if + allowed) */
947		    (!(go->flags & GF_PLUSOPT) || flag != '+')) ||
948		    (c = arg[1]) == '\0') {
949			go->p = 0;
950			return (-1);
951		}
952		go->optind++;
953		go->info &= ~(GI_MINUS|GI_PLUS);
954		go->info |= flag == '-' ? GI_MINUS : GI_PLUS;
955	}
956	go->p++;
957	if (c == '?' || c == ':' || c == ';' || c == ',' || c == '#' ||
958	    !(o = cstrchr(optionsp, c))) {
959		if (optionsp[0] == ':') {
960			go->buf[0] = c;
961			go->optarg = go->buf;
962		} else {
963			warningf(true, "%s%s-%c: %s",
964			    (go->flags & GF_NONAME) ? "" : argv[0],
965			    (go->flags & GF_NONAME) ? "" : ": ", c,
966			    "unknown option");
967			if (go->flags & GF_ERROR)
968				bi_errorfz();
969		}
970		return ('?');
971	}
972	/**
973	 * : means argument must be present, may be part of option argument
974	 *   or the next argument
975	 * ; same as : but argument may be missing
976	 * , means argument is part of option argument, and may be null.
977	 */
978	if (*++o == ':' || *o == ';') {
979		if (argv[go->optind - 1][go->p])
980			go->optarg = argv[go->optind - 1] + go->p;
981		else if (argv[go->optind])
982			go->optarg = argv[go->optind++];
983		else if (*o == ';')
984			go->optarg = NULL;
985		else {
986			if (optionsp[0] == ':') {
987				go->buf[0] = c;
988				go->optarg = go->buf;
989				return (':');
990			}
991			warningf(true, "%s%s-%c: %s",
992			    (go->flags & GF_NONAME) ? "" : argv[0],
993			    (go->flags & GF_NONAME) ? "" : ": ", c,
994			    "requires an argument");
995			if (go->flags & GF_ERROR)
996				bi_errorfz();
997			return ('?');
998		}
999		go->p = 0;
1000	} else if (*o == ',') {
1001		/* argument is attached to option character, even if null */
1002		go->optarg = argv[go->optind - 1] + go->p;
1003		go->p = 0;
1004	} else if (*o == '#') {
1005		/*
1006		 * argument is optional and may be attached or unattached
1007		 * but must start with a digit. optarg is set to 0 if the
1008		 * argument is missing.
1009		 */
1010		if (argv[go->optind - 1][go->p]) {
1011			if (ksh_isdigit(argv[go->optind - 1][go->p])) {
1012				go->optarg = argv[go->optind - 1] + go->p;
1013				go->p = 0;
1014			} else
1015				go->optarg = NULL;
1016		} else {
1017			if (argv[go->optind] && ksh_isdigit(argv[go->optind][0])) {
1018				go->optarg = argv[go->optind++];
1019				go->p = 0;
1020			} else
1021				go->optarg = NULL;
1022		}
1023	}
1024	return (c);
1025}
1026
1027/*
1028 * print variable/alias value using necessary quotes
1029 * (POSIX says they should be suitable for re-entry...)
1030 * No trailing newline is printed.
1031 */
1032void
1033print_value_quoted(const char *s)
1034{
1035	const char *p;
1036	bool inquote = false;
1037
1038	/* first, check whether any quotes are needed */
1039	for (p = s; *p; p++)
1040		if (ctype(*p, C_QUOTE))
1041			break;
1042	if (!*p) {
1043		/* nope, use the shortcut */
1044		shf_puts(s, shl_stdout);
1045		return;
1046	}
1047
1048	/* quote via state machine */
1049	for (p = s; *p; p++) {
1050		if (*p == '\'') {
1051			/*
1052			 * multiple '''s or any ' at beginning of string
1053			 * look nicer this way than when simply substituting
1054			 */
1055			if (inquote) {
1056				shf_putc('\'', shl_stdout);
1057				inquote = false;
1058			}
1059			shf_putc('\\', shl_stdout);
1060		} else if (!inquote) {
1061			shf_putc('\'', shl_stdout);
1062			inquote = true;
1063		}
1064		shf_putc(*p, shl_stdout);
1065	}
1066	if (inquote)
1067		shf_putc('\'', shl_stdout);
1068}
1069
1070/*
1071 * Print things in columns and rows - func() is called to format
1072 * the i-th element
1073 */
1074void
1075print_columns(struct shf *shf, int n,
1076    char *(*func)(char *, size_t, int, const void *),
1077    const void *arg, size_t max_oct, size_t max_colz, bool prefcol)
1078{
1079	int i, r, c, rows, cols, nspace, max_col;
1080	char *str;
1081
1082	if (n <= 0) {
1083#ifndef MKSH_SMALL
1084		internal_warningf("print_columns called with n=%d <= 0", n);
1085#endif
1086		return;
1087	}
1088
1089	if (max_colz > 2147483647) {
1090#ifndef MKSH_SMALL
1091		internal_warningf("print_columns called with max_col=%zu > INT_MAX",
1092		    max_colz);
1093#endif
1094		return;
1095	}
1096	max_col = (int)max_colz;
1097
1098	++max_oct;
1099	str = alloc(max_oct, ATEMP);
1100
1101	/* ensure x_cols is valid first */
1102	if (x_cols < MIN_COLS)
1103		change_winsz();
1104
1105	/*
1106	 * We use (max_col + 1) to consider the space separator.
1107	 * Note that no space is printed after the last column
1108	 * to avoid problems with terminals that have auto-wrap.
1109	 */
1110	cols = x_cols / (max_col + 1);
1111
1112	/* if we can only print one column anyway, skip the goo */
1113	if (cols < 2) {
1114		for (i = 0; i < n; ++i)
1115			shf_fprintf(shf, "%s \n",
1116			    (*func)(str, max_oct, i, arg));
1117		goto out;
1118	}
1119
1120	rows = (n + cols - 1) / cols;
1121	if (prefcol && cols > rows) {
1122		i = rows;
1123		rows = cols > n ? n : cols;
1124		cols = i;
1125	}
1126
1127	max_col = -max_col;
1128	nspace = (x_cols + max_col * cols) / cols;
1129	if (nspace <= 0)
1130		nspace = 1;
1131	for (r = 0; r < rows; r++) {
1132		for (c = 0; c < cols; c++) {
1133			i = c * rows + r;
1134			if (i < n) {
1135				shf_fprintf(shf, "%*s", max_col,
1136				    (*func)(str, max_oct, i, arg));
1137				if (c + 1 < cols)
1138					shf_fprintf(shf, "%*s", nspace, null);
1139			}
1140		}
1141		shf_putchar('\n', shf);
1142	}
1143 out:
1144	afree(str, ATEMP);
1145}
1146
1147/* Strip any nul bytes from buf - returns new length (nbytes - # of nuls) */
1148void
1149strip_nuls(char *buf, int nbytes)
1150{
1151	char *dst;
1152
1153	/*
1154	 * nbytes check because some systems (older FreeBSDs) have a
1155	 * buggy memchr()
1156	 */
1157	if (nbytes && (dst = memchr(buf, '\0', nbytes))) {
1158		char *end = buf + nbytes;
1159		char *p, *q;
1160
1161		for (p = dst; p < end; p = q) {
1162			/* skip a block of nulls */
1163			while (++p < end && *p == '\0')
1164				;
1165			/* find end of non-null block */
1166			if (!(q = memchr(p, '\0', end - p)))
1167				q = end;
1168			memmove(dst, p, q - p);
1169			dst += q - p;
1170		}
1171		*dst = '\0';
1172	}
1173}
1174
1175/*
1176 * Like read(2), but if read fails due to non-blocking flag,
1177 * resets flag and restarts read.
1178 */
1179ssize_t
1180blocking_read(int fd, char *buf, size_t nbytes)
1181{
1182	ssize_t ret;
1183	bool tried_reset = false;
1184
1185	while ((ret = read(fd, buf, nbytes)) < 0) {
1186		if (!tried_reset && errno == EAGAIN) {
1187			if (reset_nonblock(fd) > 0) {
1188				tried_reset = true;
1189				continue;
1190			}
1191			errno = EAGAIN;
1192		}
1193		break;
1194	}
1195	return (ret);
1196}
1197
1198/*
1199 * Reset the non-blocking flag on the specified file descriptor.
1200 * Returns -1 if there was an error, 0 if non-blocking wasn't set,
1201 * 1 if it was.
1202 */
1203int
1204reset_nonblock(int fd)
1205{
1206	int flags;
1207
1208	if ((flags = fcntl(fd, F_GETFL, 0)) < 0)
1209		return (-1);
1210	if (!(flags & O_NONBLOCK))
1211		return (0);
1212	flags &= ~O_NONBLOCK;
1213	if (fcntl(fd, F_SETFL, flags) < 0)
1214		return (-1);
1215	return (1);
1216}
1217
1218/* getcwd(3) equivalent, allocates from ATEMP but doesn't resize */
1219char *
1220ksh_get_wd(void)
1221{
1222#ifdef NO_PATH_MAX
1223	char *rv, *cp;
1224
1225	if ((cp = get_current_dir_name())) {
1226		strdupx(rv, cp, ATEMP);
1227		free_gnu_gcdn(cp);
1228	} else
1229		rv = NULL;
1230#else
1231	char *rv;
1232
1233	if (!getcwd((rv = alloc(PATH_MAX + 1, ATEMP)), PATH_MAX)) {
1234		afree(rv, ATEMP);
1235		rv = NULL;
1236	}
1237#endif
1238
1239	return (rv);
1240}
1241
1242char *
1243do_realpath(const char *upath)
1244{
1245	char *xp, *ip, *tp, *ipath, *ldest = NULL;
1246	XString xs;
1247	ptrdiff_t pos;
1248	size_t len;
1249	int llen;
1250	struct stat sb;
1251#ifdef NO_PATH_MAX
1252	size_t ldestlen = 0;
1253#define pathlen sb.st_size
1254#define pathcnd (ldestlen < (pathlen + 1))
1255#else
1256#define pathlen PATH_MAX
1257#define pathcnd (!ldest)
1258#endif
1259	/* max. recursion depth */
1260	int symlinks = 32;
1261
1262	if (upath[0] == '/') {
1263		/* upath is an absolute pathname */
1264		strdupx(ipath, upath, ATEMP);
1265	} else {
1266		/* upath is a relative pathname, prepend cwd */
1267		if ((tp = ksh_get_wd()) == NULL || tp[0] != '/')
1268			return (NULL);
1269		ipath = shf_smprintf("%s%s%s", tp, "/", upath);
1270		afree(tp, ATEMP);
1271	}
1272
1273	/* ipath and upath are in memory at the same time -> unchecked */
1274	Xinit(xs, xp, strlen(ip = ipath) + 1, ATEMP);
1275
1276	/* now jump into the deep of the loop */
1277	goto beginning_of_a_pathname;
1278
1279	while (*ip) {
1280		/* skip slashes in input */
1281		while (*ip == '/')
1282			++ip;
1283		if (!*ip)
1284			break;
1285
1286		/* get next pathname component from input */
1287		tp = ip;
1288		while (*ip && *ip != '/')
1289			++ip;
1290		len = ip - tp;
1291
1292		/* check input for "." and ".." */
1293		if (tp[0] == '.') {
1294			if (len == 1)
1295				/* just continue with the next one */
1296				continue;
1297			else if (len == 2 && tp[1] == '.') {
1298				/* strip off last pathname component */
1299				while (xp > Xstring(xs, xp))
1300					if (*--xp == '/')
1301						break;
1302				/* then continue with the next one */
1303				continue;
1304			}
1305		}
1306
1307		/* store output position away, then append slash to output */
1308		pos = Xsavepos(xs, xp);
1309		/* 1 for the '/' and len + 1 for tp and the NUL from below */
1310		XcheckN(xs, xp, 1 + len + 1);
1311		Xput(xs, xp, '/');
1312
1313		/* append next pathname component to output */
1314		memcpy(xp, tp, len);
1315		xp += len;
1316		*xp = '\0';
1317
1318		/* lstat the current output, see if it's a symlink */
1319		if (lstat(Xstring(xs, xp), &sb)) {
1320			/* lstat failed */
1321			if (errno == ENOENT) {
1322				/* because the pathname does not exist */
1323				while (*ip == '/')
1324					/* skip any trailing slashes */
1325					++ip;
1326				/* no more components left? */
1327				if (!*ip)
1328					/* we can still return successfully */
1329					break;
1330				/* more components left? fall through */
1331			}
1332			/* not ENOENT or not at the end of ipath */
1333			goto notfound;
1334		}
1335
1336		/* check if we encountered a symlink? */
1337		if (S_ISLNK(sb.st_mode)) {
1338			/* reached maximum recursion depth? */
1339			if (!symlinks--) {
1340				/* yep, prevent infinite loops */
1341				errno = ELOOP;
1342				goto notfound;
1343			}
1344
1345			/* get symlink(7) target */
1346			if (pathcnd) {
1347#ifdef NO_PATH_MAX
1348				if (notoktoadd(pathlen, 1)) {
1349					errno = ENAMETOOLONG;
1350					goto notfound;
1351				}
1352#endif
1353				ldest = aresize(ldest, pathlen + 1, ATEMP);
1354			}
1355			llen = readlink(Xstring(xs, xp), ldest, pathlen);
1356			if (llen < 0)
1357				/* oops... */
1358				goto notfound;
1359			ldest[llen] = '\0';
1360
1361			/*
1362			 * restart if symlink target is an absolute path,
1363			 * otherwise continue with currently resolved prefix
1364			 */
1365			/* append rest of current input path to link target */
1366			tp = shf_smprintf("%s%s%s", ldest, *ip ? "/" : "", ip);
1367			afree(ipath, ATEMP);
1368			ip = ipath = tp;
1369			if (ldest[0] != '/') {
1370				/* symlink target is a relative path */
1371				xp = Xrestpos(xs, xp, pos);
1372			} else {
1373				/* symlink target is an absolute path */
1374				xp = Xstring(xs, xp);
1375 beginning_of_a_pathname:
1376				/* assert: (ip == ipath)[0] == '/' */
1377				/* assert: xp == xs.beg => start of path */
1378
1379				/* exactly two leading slashes? (SUSv4 3.266) */
1380				if (ip[1] == '/' && ip[2] != '/') {
1381					/* keep them, e.g. for UNC pathnames */
1382					Xput(xs, xp, '/');
1383				}
1384			}
1385		}
1386		/* otherwise (no symlink) merely go on */
1387	}
1388
1389	/*
1390	 * either found the target and successfully resolved it,
1391	 * or found its parent directory and may create it
1392	 */
1393	if (Xlength(xs, xp) == 0)
1394		/*
1395		 * if the resolved pathname is "", make it "/",
1396		 * otherwise do not add a trailing slash
1397		 */
1398		Xput(xs, xp, '/');
1399	Xput(xs, xp, '\0');
1400
1401	/*
1402	 * if source path had a trailing slash, check if target path
1403	 * is not a non-directory existing file
1404	 */
1405	if (ip > ipath && ip[-1] == '/') {
1406		if (stat(Xstring(xs, xp), &sb)) {
1407			if (errno != ENOENT)
1408				goto notfound;
1409		} else if (!S_ISDIR(sb.st_mode)) {
1410			errno = ENOTDIR;
1411			goto notfound;
1412		}
1413		/* target now either does not exist or is a directory */
1414	}
1415
1416	/* return target path */
1417	if (ldest != NULL)
1418		afree(ldest, ATEMP);
1419	afree(ipath, ATEMP);
1420	return (Xclose(xs, xp));
1421
1422 notfound:
1423	/* save; freeing memory might trash it */
1424	llen = errno;
1425	if (ldest != NULL)
1426		afree(ldest, ATEMP);
1427	afree(ipath, ATEMP);
1428	Xfree(xs, xp);
1429	errno = llen;
1430	return (NULL);
1431
1432#undef pathlen
1433#undef pathcnd
1434}
1435
1436/**
1437 *	Makes a filename into result using the following algorithm.
1438 *	- make result NULL
1439 *	- if file starts with '/', append file to result & set cdpathp to NULL
1440 *	- if file starts with ./ or ../ append cwd and file to result
1441 *	  and set cdpathp to NULL
1442 *	- if the first element of cdpathp doesnt start with a '/' xx or '.' xx
1443 *	  then cwd is appended to result.
1444 *	- the first element of cdpathp is appended to result
1445 *	- file is appended to result
1446 *	- cdpathp is set to the start of the next element in cdpathp (or NULL
1447 *	  if there are no more elements.
1448 *	The return value indicates whether a non-null element from cdpathp
1449 *	was appended to result.
1450 */
1451static int
1452make_path(const char *cwd, const char *file,
1453    /* pointer to colon-separated list */
1454    char **cdpathp,
1455    XString *xsp,
1456    int *phys_pathp)
1457{
1458	int rval = 0;
1459	bool use_cdpath = true;
1460	char *plist;
1461	size_t len, plen = 0;
1462	char *xp = Xstring(*xsp, xp);
1463
1464	if (!file)
1465		file = null;
1466
1467	if (file[0] == '/') {
1468		*phys_pathp = 0;
1469		use_cdpath = false;
1470	} else {
1471		if (file[0] == '.') {
1472			char c = file[1];
1473
1474			if (c == '.')
1475				c = file[2];
1476			if (c == '/' || c == '\0')
1477				use_cdpath = false;
1478		}
1479
1480		plist = *cdpathp;
1481		if (!plist)
1482			use_cdpath = false;
1483		else if (use_cdpath) {
1484			char *pend;
1485
1486			for (pend = plist; *pend && *pend != ':'; pend++)
1487				;
1488			plen = pend - plist;
1489			*cdpathp = *pend ? pend + 1 : NULL;
1490		}
1491
1492		if ((!use_cdpath || !plen || plist[0] != '/') &&
1493		    (cwd && *cwd)) {
1494			len = strlen(cwd);
1495			XcheckN(*xsp, xp, len);
1496			memcpy(xp, cwd, len);
1497			xp += len;
1498			if (cwd[len - 1] != '/')
1499				Xput(*xsp, xp, '/');
1500		}
1501		*phys_pathp = Xlength(*xsp, xp);
1502		if (use_cdpath && plen) {
1503			XcheckN(*xsp, xp, plen);
1504			memcpy(xp, plist, plen);
1505			xp += plen;
1506			if (plist[plen - 1] != '/')
1507				Xput(*xsp, xp, '/');
1508			rval = 1;
1509		}
1510	}
1511
1512	len = strlen(file) + 1;
1513	XcheckN(*xsp, xp, len);
1514	memcpy(xp, file, len);
1515
1516	if (!use_cdpath)
1517		*cdpathp = NULL;
1518
1519	return (rval);
1520}
1521
1522/*-
1523 * Simplify pathnames containing "." and ".." entries.
1524 *
1525 * simplify_path(this)			= that
1526 * /a/b/c/./../d/..			/a/b
1527 * //./C/foo/bar/../baz			//C/foo/baz
1528 * /foo/				/foo
1529 * /foo/../../bar			/bar
1530 * /foo/./blah/..			/foo
1531 * .					.
1532 * ..					..
1533 * ./foo				foo
1534 * foo/../../../bar			../../bar
1535 */
1536void
1537simplify_path(char *p)
1538{
1539	char *dp, *ip, *sp, *tp;
1540	size_t len;
1541	bool needslash;
1542
1543	switch (*p) {
1544	case 0:
1545		return;
1546	case '/':
1547		/* exactly two leading slashes? (SUSv4 3.266) */
1548		if (p[1] == '/' && p[2] != '/')
1549			/* keep them, e.g. for UNC pathnames */
1550			++p;
1551		needslash = true;
1552		break;
1553	default:
1554		needslash = false;
1555	}
1556	dp = ip = sp = p;
1557
1558	while (*ip) {
1559		/* skip slashes in input */
1560		while (*ip == '/')
1561			++ip;
1562		if (!*ip)
1563			break;
1564
1565		/* get next pathname component from input */
1566		tp = ip;
1567		while (*ip && *ip != '/')
1568			++ip;
1569		len = ip - tp;
1570
1571		/* check input for "." and ".." */
1572		if (tp[0] == '.') {
1573			if (len == 1)
1574				/* just continue with the next one */
1575				continue;
1576			else if (len == 2 && tp[1] == '.') {
1577				/* parent level, but how? */
1578				if (*p == '/')
1579					/* absolute path, only one way */
1580					goto strip_last_component;
1581				else if (dp > sp) {
1582					/* relative path, with subpaths */
1583					needslash = false;
1584 strip_last_component:
1585					/* strip off last pathname component */
1586					while (dp > sp)
1587						if (*--dp == '/')
1588							break;
1589				} else {
1590					/* relative path, at its beginning */
1591					if (needslash)
1592						/* or already dotdot-slash'd */
1593						*dp++ = '/';
1594					/* keep dotdot-slash if not absolute */
1595					*dp++ = '.';
1596					*dp++ = '.';
1597					needslash = true;
1598					sp = dp;
1599				}
1600				/* then continue with the next one */
1601				continue;
1602			}
1603		}
1604
1605		if (needslash)
1606			*dp++ = '/';
1607
1608		/* append next pathname component to output */
1609		memmove(dp, tp, len);
1610		dp += len;
1611
1612		/* append slash if we continue */
1613		needslash = true;
1614		/* try next component */
1615	}
1616	if (dp == p)
1617		/* empty path -> dot */
1618		*dp++ = needslash ? '/' : '.';
1619	*dp = '\0';
1620}
1621
1622void
1623set_current_wd(const char *nwd)
1624{
1625	char *allocd = NULL;
1626
1627	if (nwd == NULL) {
1628		allocd = ksh_get_wd();
1629		nwd = allocd ? allocd : null;
1630	}
1631
1632	afree(current_wd, APERM);
1633	strdupx(current_wd, nwd, APERM);
1634
1635	afree(allocd, ATEMP);
1636}
1637
1638int
1639c_cd(const char **wp)
1640{
1641	int optc, rv, phys_path;
1642	bool physical = tobool(Flag(FPHYSICAL));
1643	/* was a node from cdpath added in? */
1644	int cdnode;
1645	/* show where we went?, error for $PWD */
1646	bool printpath = false, eflag = false;
1647	struct tbl *pwd_s, *oldpwd_s;
1648	XString xs;
1649	char *dir, *allocd = NULL, *tryp, *pwd, *cdpath;
1650
1651	while ((optc = ksh_getopt(wp, &builtin_opt, "eLP")) != -1)
1652		switch (optc) {
1653		case 'e':
1654			eflag = true;
1655			break;
1656		case 'L':
1657			physical = false;
1658			break;
1659		case 'P':
1660			physical = true;
1661			break;
1662		case '?':
1663			return (2);
1664		}
1665	wp += builtin_opt.optind;
1666
1667	if (Flag(FRESTRICTED)) {
1668		bi_errorf("restricted shell - can't cd");
1669		return (2);
1670	}
1671
1672	pwd_s = global("PWD");
1673	oldpwd_s = global("OLDPWD");
1674
1675	if (!wp[0]) {
1676		/* No arguments - go home */
1677		if ((dir = str_val(global("HOME"))) == null) {
1678			bi_errorf("no home directory (HOME not set)");
1679			return (2);
1680		}
1681	} else if (!wp[1]) {
1682		/* One argument: - or dir */
1683		strdupx(allocd, wp[0], ATEMP);
1684		if (ksh_isdash((dir = allocd))) {
1685			afree(allocd, ATEMP);
1686			allocd = NULL;
1687			dir = str_val(oldpwd_s);
1688			if (dir == null) {
1689				bi_errorf("no OLDPWD");
1690				return (2);
1691			}
1692			printpath = true;
1693		}
1694	} else if (!wp[2]) {
1695		/* Two arguments - substitute arg1 in PWD for arg2 */
1696		size_t ilen, olen, nlen, elen;
1697		char *cp;
1698
1699		if (!current_wd[0]) {
1700			bi_errorf("can't determine current directory");
1701			return (2);
1702		}
1703		/*
1704		 * substitute arg1 for arg2 in current path.
1705		 * if the first substitution fails because the cd fails
1706		 * we could try to find another substitution. For now
1707		 * we don't
1708		 */
1709		if ((cp = strstr(current_wd, wp[0])) == NULL) {
1710			bi_errorf("bad substitution");
1711			return (2);
1712		}
1713		/*-
1714		 * ilen = part of current_wd before wp[0]
1715		 * elen = part of current_wd after wp[0]
1716		 * because current_wd and wp[1] need to be in memory at the
1717		 * same time beforehand the addition can stay unchecked
1718		 */
1719		ilen = cp - current_wd;
1720		olen = strlen(wp[0]);
1721		nlen = strlen(wp[1]);
1722		elen = strlen(current_wd + ilen + olen) + 1;
1723		dir = allocd = alloc(ilen + nlen + elen, ATEMP);
1724		memcpy(dir, current_wd, ilen);
1725		memcpy(dir + ilen, wp[1], nlen);
1726		memcpy(dir + ilen + nlen, current_wd + ilen + olen, elen);
1727		printpath = true;
1728	} else {
1729		bi_errorf("too many arguments");
1730		return (2);
1731	}
1732
1733#ifdef NO_PATH_MAX
1734	/* only a first guess; make_path will enlarge xs if necessary */
1735	XinitN(xs, 1024, ATEMP);
1736#else
1737	XinitN(xs, PATH_MAX, ATEMP);
1738#endif
1739
1740	cdpath = str_val(global("CDPATH"));
1741	do {
1742		cdnode = make_path(current_wd, dir, &cdpath, &xs, &phys_path);
1743		if (physical)
1744			rv = chdir(tryp = Xstring(xs, xp) + phys_path);
1745		else {
1746			simplify_path(Xstring(xs, xp));
1747			rv = chdir(tryp = Xstring(xs, xp));
1748		}
1749	} while (rv < 0 && cdpath != NULL);
1750
1751	if (rv < 0) {
1752		if (cdnode)
1753			bi_errorf("%s: %s", dir, "bad directory");
1754		else
1755			bi_errorf("%s: %s", tryp, strerror(errno));
1756		afree(allocd, ATEMP);
1757		Xfree(xs, xp);
1758		return (2);
1759	}
1760
1761	rv = 0;
1762
1763	/* allocd (above) => dir, which is no longer used */
1764	afree(allocd, ATEMP);
1765	allocd = NULL;
1766
1767	/* Clear out tracked aliases with relative paths */
1768	flushcom(false);
1769
1770	/*
1771	 * Set OLDPWD (note: unsetting OLDPWD does not disable this
1772	 * setting in AT&T ksh)
1773	 */
1774	if (current_wd[0])
1775		/* Ignore failure (happens if readonly or integer) */
1776		setstr(oldpwd_s, current_wd, KSH_RETURN_ERROR);
1777
1778	if (Xstring(xs, xp)[0] != '/') {
1779		pwd = NULL;
1780	} else if (!physical) {
1781		goto norealpath_PWD;
1782	} else if ((pwd = allocd = do_realpath(Xstring(xs, xp))) == NULL) {
1783		if (eflag)
1784			rv = 1;
1785 norealpath_PWD:
1786		pwd = Xstring(xs, xp);
1787	}
1788
1789	/* Set PWD */
1790	if (pwd) {
1791		char *ptmp = pwd;
1792
1793		set_current_wd(ptmp);
1794		/* Ignore failure (happens if readonly or integer) */
1795		setstr(pwd_s, ptmp, KSH_RETURN_ERROR);
1796	} else {
1797		set_current_wd(null);
1798		pwd = Xstring(xs, xp);
1799		/* XXX unset $PWD? */
1800		if (eflag)
1801			rv = 1;
1802	}
1803	if (printpath || cdnode)
1804		shprintf("%s\n", pwd);
1805
1806	afree(allocd, ATEMP);
1807	Xfree(xs, xp);
1808	return (rv);
1809}
1810
1811
1812#ifdef TIOCSCTTY
1813extern void chvt_reinit(void);
1814
1815static void
1816chvt(const char *fn)
1817{
1818	char dv[20];
1819	struct stat sb;
1820	int fd;
1821
1822	if (*fn == '-') {
1823		memcpy(dv, "-/dev/null", sizeof("-/dev/null"));
1824		fn = dv + 1;
1825	} else {
1826		if (stat(fn, &sb)) {
1827			memcpy(dv, "/dev/ttyC", 9);
1828			strlcpy(dv + 9, fn, sizeof(dv) - 9);
1829			if (stat(dv, &sb)) {
1830				strlcpy(dv + 8, fn, sizeof(dv) - 8);
1831				if (stat(dv, &sb))
1832					errorf("%s: %s %s", "chvt",
1833					    "can't find tty", fn);
1834			}
1835			fn = dv;
1836		}
1837		if (!(sb.st_mode & S_IFCHR))
1838			errorf("%s %s %s", "chvt: not a char", "device", fn);
1839		if ((sb.st_uid != 0) && chown(fn, 0, 0))
1840			warningf(false, "%s: %s %s", "chvt", "can't chown root", fn);
1841		if (((sb.st_mode & 07777) != 0600) && chmod(fn, (mode_t)0600))
1842			warningf(false, "%s: %s %s", "chvt", "can't chmod 0600", fn);
1843#if HAVE_REVOKE
1844		if (revoke(fn))
1845#endif
1846			warningf(false, "%s: %s %s", "chvt",
1847			    "new shell is potentially insecure, can't revoke",
1848			    fn);
1849	}
1850	if ((fd = open(fn, O_RDWR)) == -1) {
1851		sleep(1);
1852		if ((fd = open(fn, O_RDWR)) == -1)
1853			errorf("%s: %s %s", "chvt", "can't open", fn);
1854	}
1855	switch (fork()) {
1856	case -1:
1857		errorf("%s: %s %s", "chvt", "fork", "failed");
1858	case 0:
1859		break;
1860	default:
1861		exit(0);
1862	}
1863	if (setsid() == -1)
1864		errorf("%s: %s %s", "chvt", "setsid", "failed");
1865	if (fn != dv + 1) {
1866		if (ioctl(fd, TIOCSCTTY, NULL) == -1)
1867			errorf("%s: %s %s", "chvt", "TIOCSCTTY", "failed");
1868		if (tcflush(fd, TCIOFLUSH))
1869			errorf("%s: %s %s", "chvt", "TCIOFLUSH", "failed");
1870	}
1871	ksh_dup2(fd, 0, false);
1872	ksh_dup2(fd, 1, false);
1873	ksh_dup2(fd, 2, false);
1874	if (fd > 2)
1875		close(fd);
1876	{
1877		register uint32_t h;
1878
1879		NZATInit(h);
1880		NZATUpdateMem(h, &rndsetupstate, sizeof(rndsetupstate));
1881		NZAATFinish(h);
1882		rndset((long)h);
1883	}
1884	chvt_reinit();
1885}
1886#endif
1887
1888#ifdef DEBUG
1889#define assert_eq(name, a, b) char name[a == b ? 1 : -1]
1890#define assert_ge(name, a, b) char name[a >= b ? 1 : -1]
1891assert_ge(intsize_is_okay, sizeof(int), 4);
1892assert_eq(intsizes_are_okay, sizeof(int), sizeof(unsigned int));
1893assert_ge(longsize_is_okay, sizeof(long), sizeof(int));
1894assert_eq(arisize_is_okay, sizeof(mksh_ari_t), 4);
1895assert_eq(uarisize_is_okay, sizeof(mksh_uari_t), 4);
1896assert_eq(sizesizes_are_okay, sizeof(size_t), sizeof(ssize_t));
1897assert_eq(ptrsizes_are_okay, sizeof(ptrdiff_t), sizeof(void *));
1898assert_eq(ptrsize_is_sizet, sizeof(ptrdiff_t), sizeof(size_t));
1899/* formatting routines assume this */
1900assert_ge(ptr_fits_in_long, sizeof(long), sizeof(size_t));
1901
1902char *
1903strchr(char *p, int ch)
1904{
1905	for (;; ++p) {
1906		if (*p == ch)
1907			return (p);
1908		if (!*p)
1909			return (NULL);
1910	}
1911	/* NOTREACHED */
1912}
1913
1914char *
1915strstr(char *b, const char *l)
1916{
1917	char first, c;
1918	size_t n;
1919
1920	if ((first = *l++) == '\0')
1921		return (b);
1922	n = strlen(l);
1923 strstr_look:
1924	while ((c = *b++) != first)
1925		if (c == '\0')
1926			return (NULL);
1927	if (strncmp(b, l, n))
1928		goto strstr_look;
1929	return (b - 1);
1930}
1931#endif
1932
1933#if !HAVE_STRCASESTR
1934const char *
1935stristr(const char *b, const char *l)
1936{
1937	char first, c;
1938	size_t n;
1939
1940	if ((first = *l++), ((first = ksh_tolower(first)) == '\0'))
1941		return (b);
1942	n = strlen(l);
1943 stristr_look:
1944	while ((c = *b++), ((c = ksh_tolower(c)) != first))
1945		if (c == '\0')
1946			return (NULL);
1947	if (strncasecmp(b, l, n))
1948		goto stristr_look;
1949	return (b - 1);
1950}
1951#endif
1952
1953#ifdef MKSH_SMALL
1954char *
1955strndup_(const char *src, size_t len, Area *ap)
1956{
1957	char *dst = NULL;
1958
1959	if (src != NULL) {
1960		dst = alloc(len + 1, ap);
1961		memcpy(dst, src, len);
1962		dst[len] = '\0';
1963	}
1964	return (dst);
1965}
1966
1967char *
1968strdup_(const char *src, Area *ap)
1969{
1970	return (src == NULL ? NULL : strndup_(src, strlen(src), ap));
1971}
1972#endif
1973
1974#if !HAVE_GETRUSAGE
1975#define INVTCK(r,t)	do {						\
1976	r.tv_usec = ((t) % (1000000 / CLK_TCK)) * (1000000 / CLK_TCK);	\
1977	r.tv_sec = (t) / CLK_TCK;					\
1978} while (/* CONSTCOND */ 0)
1979
1980int
1981getrusage(int what, struct rusage *ru)
1982{
1983	struct tms tms;
1984	clock_t u, s;
1985
1986	if (/* ru == NULL || */ times(&tms) == (clock_t)-1)
1987		return (-1);
1988
1989	switch (what) {
1990	case RUSAGE_SELF:
1991		u = tms.tms_utime;
1992		s = tms.tms_stime;
1993		break;
1994	case RUSAGE_CHILDREN:
1995		u = tms.tms_cutime;
1996		s = tms.tms_cstime;
1997		break;
1998	default:
1999		errno = EINVAL;
2000		return (-1);
2001	}
2002	INVTCK(ru->ru_utime, u);
2003	INVTCK(ru->ru_stime, s);
2004	return (0);
2005}
2006#endif
2007
2008/*
2009 * process the string available via fg (get a char)
2010 * and fp (put back a char) for backslash escapes,
2011 * assuming the first call to *fg gets the char di-
2012 * rectly after the backslash; return the character
2013 * (0..0xFF), Unicode (wc + 0x100), or -1 if no known
2014 * escape sequence was found
2015 */
2016int
2017unbksl(bool cstyle, int (*fg)(void), void (*fp)(int))
2018{
2019	int wc, i, c, fc;
2020
2021	fc = (*fg)();
2022	switch (fc) {
2023	case 'a':
2024		/*
2025		 * according to the comments in pdksh, \007 seems
2026		 * to be more portable than \a (due to HP-UX cc,
2027		 * Ultrix cc, old pcc, etc.) so we avoid the escape
2028		 * sequence altogether in mksh and assume ASCII
2029		 */
2030		wc = 7;
2031		break;
2032	case 'b':
2033		wc = '\b';
2034		break;
2035	case 'c':
2036		if (!cstyle)
2037			goto unknown_escape;
2038		c = (*fg)();
2039		wc = CTRL(c);
2040		break;
2041	case 'E':
2042	case 'e':
2043		wc = 033;
2044		break;
2045	case 'f':
2046		wc = '\f';
2047		break;
2048	case 'n':
2049		wc = '\n';
2050		break;
2051	case 'r':
2052		wc = '\r';
2053		break;
2054	case 't':
2055		wc = '\t';
2056		break;
2057	case 'v':
2058		/* assume ASCII here as well */
2059		wc = 11;
2060		break;
2061	case '1':
2062	case '2':
2063	case '3':
2064	case '4':
2065	case '5':
2066	case '6':
2067	case '7':
2068		if (!cstyle)
2069			goto unknown_escape;
2070		/* FALLTHROUGH */
2071	case '0':
2072		if (cstyle)
2073			(*fp)(fc);
2074		/*
2075		 * look for an octal number with up to three
2076		 * digits, not counting the leading zero;
2077		 * convert it to a raw octet
2078		 */
2079		wc = 0;
2080		i = 3;
2081		while (i--)
2082			if ((c = (*fg)()) >= '0' && c <= '7')
2083				wc = (wc << 3) + (c - '0');
2084			else {
2085				(*fp)(c);
2086				break;
2087			}
2088		break;
2089	case 'U':
2090		i = 8;
2091		if (/* CONSTCOND */ 0)
2092		/* FALLTHROUGH */
2093	case 'u':
2094		i = 4;
2095		if (/* CONSTCOND */ 0)
2096		/* FALLTHROUGH */
2097	case 'x':
2098		i = cstyle ? -1 : 2;
2099		/**
2100		 * x:	look for a hexadecimal number with up to
2101		 *	two (C style: arbitrary) digits; convert
2102		 *	to raw octet (C style: Unicode if >0xFF)
2103		 * u/U:	look for a hexadecimal number with up to
2104		 *	four (U: eight) digits; convert to Unicode
2105		 */
2106		wc = 0;
2107		while (i--) {
2108			wc <<= 4;
2109			if ((c = (*fg)()) >= '0' && c <= '9')
2110				wc += c - '0';
2111			else if (c >= 'A' && c <= 'F')
2112				wc += c - 'A' + 10;
2113			else if (c >= 'a' && c <= 'f')
2114				wc += c - 'a' + 10;
2115			else {
2116				wc >>= 4;
2117				(*fp)(c);
2118				break;
2119			}
2120		}
2121		if ((cstyle && wc > 0xFF) || fc != 'x')
2122			/* Unicode marker */
2123			wc += 0x100;
2124		break;
2125	case '\'':
2126		if (!cstyle)
2127			goto unknown_escape;
2128		wc = '\'';
2129		break;
2130	case '\\':
2131		wc = '\\';
2132		break;
2133	default:
2134 unknown_escape:
2135		(*fp)(fc);
2136		return (-1);
2137	}
2138
2139	return (wc);
2140}
2141