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