/* vi: set sw=4 ts=4: */
/*
 * ash shell port for busybox
 *
 * This code is derived from software contributed to Berkeley by
 * Kenneth Almquist.
 *
 * Original BSD copyright notice is retained at the end of this file.
 *
 * Copyright (c) 1989, 1991, 1993, 1994
 *      The Regents of the University of California.  All rights reserved.
 *
 * Copyright (c) 1997-2005 Herbert Xu <herbert@gondor.apana.org.au>
 * was re-ported from NetBSD and debianized.
 *
 * Licensed under GPLv2 or later, see file LICENSE in this source tree.
 */
//config:config ASH
//config:       bool "ash (78 kb)"
//config:       default y
//config:       depends on !NOMMU
//config:       help
//config:       The most complete and most pedantically correct shell included with
//config:       busybox. This shell is actually a derivative of the Debian 'dash'
//config:       shell (by Herbert Xu), which was created by porting the 'ash' shell
//config:       (written by Kenneth Almquist) from NetBSD.
//config:
//config:# ash options
//config:# note: Don't remove !NOMMU part in the next line; it would break
//config:# menuconfig's indenting.
//config:if !NOMMU && (ASH || SH_IS_ASH || BASH_IS_ASH)
//config:
//config:config ASH_OPTIMIZE_FOR_SIZE
//config:       bool "Optimize for size instead of speed"
//config:       default y
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:
//config:config ASH_INTERNAL_GLOB
//config:       bool "Use internal glob() implementation"
//config:       default y       # Y is bigger, but because of uclibc glob() bug, let Y be default for now
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:       help
//config:       Do not use glob() function from libc, use internal implementation.
//config:       Use this if you are getting "glob.h: No such file or directory"
//config:       or similar build errors.
//config:       Note that as of now (2017-01), uclibc and musl glob() both have bugs
//config:       which would break ash if you select N here.
//config:
//config:config ASH_BASH_COMPAT
//config:       bool "bash-compatible extensions"
//config:       default y
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:
//config:config ASH_BASH_SOURCE_CURDIR
//config:       bool "'source' and '.' builtins search current directory after $PATH"
//config:       default n   # do not encourage non-standard behavior
//config:       depends on ASH_BASH_COMPAT
//config:       help
//config:       This is not compliant with standards. Avoid if possible.
//config:
//config:config ASH_BASH_NOT_FOUND_HOOK
//config:       bool "command_not_found_handle hook support"
//config:       default y
//config:       depends on ASH_BASH_COMPAT
//config:       help
//config:       Enable support for the 'command_not_found_handle' hook function,
//config:       from GNU bash, which allows for alternative command not found
//config:       handling.
//config:
//config:config ASH_JOB_CONTROL
//config:       bool "Job control"
//config:       default y
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:
//config:config ASH_ALIAS
//config:       bool "Alias support"
//config:       default y
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:
//config:config ASH_RANDOM_SUPPORT
//config:       bool "Pseudorandom generator and $RANDOM variable"
//config:       default y
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:       help
//config:       Enable pseudorandom generator and dynamic variable "$RANDOM".
//config:       Each read of "$RANDOM" will generate a new pseudorandom value.
//config:       You can reset the generator by using a specified start value.
//config:       After "unset RANDOM" the generator will switch off and this
//config:       variable will no longer have special treatment.
//config:
//config:config ASH_EXPAND_PRMT
//config:       bool "Expand prompt string"
//config:       default y
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:       help
//config:       $PS# may contain volatile content, such as backquote commands.
//config:       This option recreates the prompt string from the environment
//config:       variable each time it is displayed.
//config:
//config:config ASH_IDLE_TIMEOUT
//config:       bool "Idle timeout variable $TMOUT"
//config:       default y
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:       help
//config:       Enable bash-like auto-logout after $TMOUT seconds of idle time.
//config:
//config:config ASH_MAIL
//config:       bool "Check for new mail in interactive shell"
//config:       default y
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:       help
//config:       Enable "check for new mail" function:
//config:       if set, $MAIL file and $MAILPATH list of files
//config:       are checked for mtime changes, and "you have mail"
//config:       message is printed if change is detected.
//config:
//config:config ASH_ECHO
//config:       bool "echo builtin"
//config:       default y
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:
//config:config ASH_PRINTF
//config:       bool "printf builtin"
//config:       default y
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:
//config:config ASH_TEST
//config:       bool "test builtin"
//config:       default y
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:
//config:config ASH_HELP
//config:       bool "help builtin"
//config:       default y
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:
//config:config ASH_GETOPTS
//config:       bool "getopts builtin"
//config:       default y
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:
//config:config ASH_CMDCMD
//config:       bool "command builtin"
//config:       default y
//config:       depends on ASH || SH_IS_ASH || BASH_IS_ASH
//config:       help
//config:       Enable support for the 'command' builtin, which allows
//config:       you to run the specified command or builtin,
//config:       even when there is a function with the same name.
//config:
//config:endif # ash options

//applet:IF_ASH(APPLET(ash, BB_DIR_BIN, BB_SUID_DROP))
//                      APPLET_ODDNAME:name  main location    suid_type     help
//applet:IF_SH_IS_ASH(  APPLET_ODDNAME(sh,   ash, BB_DIR_BIN, BB_SUID_DROP, ash))
//applet:IF_BASH_IS_ASH(APPLET_ODDNAME(bash, ash, BB_DIR_BIN, BB_SUID_DROP, ash))

//kbuild:lib-$(CONFIG_ASH) += ash.o ash_ptr_hack.o shell_common.o
//kbuild:lib-$(CONFIG_SH_IS_ASH) += ash.o ash_ptr_hack.o shell_common.o
//kbuild:lib-$(CONFIG_BASH_IS_ASH) += ash.o ash_ptr_hack.o shell_common.o
//kbuild:lib-$(CONFIG_ASH_RANDOM_SUPPORT) += random.o

/*
 * DEBUG=1 to compile in debugging ('set -o debug' turns on)
 * DEBUG=2 to compile in and turn on debugging.
 * When debugging is on ("set -o debug" was executed, or DEBUG=2),
 * debugging info is written to ./trace, quit signal generates core dump.
 */
#define DEBUG 0
/* Tweak debug output verbosity here */
#define DEBUG_TIME 0
#define DEBUG_PID 1
#define DEBUG_SIG 1
#define DEBUG_INTONOFF 0

#define PROFILE 0

#define JOBS ENABLE_ASH_JOB_CONTROL

#include <fnmatch.h>
#include <sys/times.h>
#include <sys/utsname.h> /* for setting $HOSTNAME */
#include "busybox.h" /* for applet_names */
#if ENABLE_FEATURE_SH_EMBEDDED_SCRIPTS
# include "embedded_scripts.h"
#else
# define NUM_SCRIPTS 0
#endif

/* So far, all bash compat is controlled by one config option */
/* Separate defines document which part of code implements what */
/* function keyword */
#define    BASH_FUNCTION        ENABLE_ASH_BASH_COMPAT
#define IF_BASH_FUNCTION            IF_ASH_BASH_COMPAT
/* &>file */
#define    BASH_REDIR_OUTPUT    ENABLE_ASH_BASH_COMPAT
#define IF_BASH_REDIR_OUTPUT        IF_ASH_BASH_COMPAT
/* $'...' */
#define    BASH_DOLLAR_SQUOTE   ENABLE_ASH_BASH_COMPAT
#define IF_BASH_DOLLAR_SQUOTE       IF_ASH_BASH_COMPAT
#define    BASH_PATTERN_SUBST   ENABLE_ASH_BASH_COMPAT
#define IF_BASH_PATTERN_SUBST       IF_ASH_BASH_COMPAT
#define    BASH_SUBSTR          ENABLE_ASH_BASH_COMPAT
#define IF_BASH_SUBSTR              IF_ASH_BASH_COMPAT
/* BASH_TEST2: [[ EXPR ]]
 * Status of [[ support:
 * We replace && and || with -a and -o
 * TODO:
 * singleword+noglob expansion:
 *   v='a b'; [[ $v = 'a b' ]]; echo 0:$?
 *   [[ /bin/n* ]]; echo 0:$?
 * -a/-o are not AND/OR ops! (they are just strings)
 * quoting needs to be considered (-f is an operator, "-f" and ""-f are not; etc)
 * = is glob match operator, not equality operator: STR = GLOB
 * (in GLOB, quoting is significant on char-by-char basis: a*cd"*")
 * == same as =
 * add =~ regex match operator: STR =~ REGEX
 */
#define    BASH_TEST2           (ENABLE_ASH_BASH_COMPAT * ENABLE_ASH_TEST)
#define    BASH_SOURCE          ENABLE_ASH_BASH_COMPAT
#define    BASH_PIPEFAIL        ENABLE_ASH_BASH_COMPAT
#define    BASH_HOSTNAME_VAR    ENABLE_ASH_BASH_COMPAT
#define    BASH_EPOCH_VARS      ENABLE_ASH_BASH_COMPAT
#define    BASH_SHLVL_VAR       ENABLE_ASH_BASH_COMPAT
#define    BASH_XTRACEFD        ENABLE_ASH_BASH_COMPAT
#define    BASH_READ_D          ENABLE_ASH_BASH_COMPAT
#define IF_BASH_READ_D              IF_ASH_BASH_COMPAT
#define    BASH_WAIT_N          ENABLE_ASH_BASH_COMPAT

#if defined(__ANDROID_API__) && __ANDROID_API__ <= 24
/* Bionic at least up to version 24 has no glob() */
# undef  ENABLE_ASH_INTERNAL_GLOB
# define ENABLE_ASH_INTERNAL_GLOB 1
#endif

#if !ENABLE_ASH_INTERNAL_GLOB && defined(__UCLIBC__)
# error uClibc glob() is buggy, use ASH_INTERNAL_GLOB.
# error The bug is: for "$PWD"/<pattern> ash will escape e.g. dashes in "$PWD"
# error with backslash, even ones which do not need to be: "/a-b" -> "/a\-b"
# error glob() should unbackslash them and match. uClibc does not unbackslash,
# error fails to match dirname, subsequently not expanding <pattern> in it.
// Testcase:
// if (glob("/etc/polkit\\-1", 0, NULL, &pglob)) - this returns 0 on uclibc, no bug
// if (glob("/etc/polkit\\-1/*", 0, NULL, &pglob)) printf("uclibc bug!\n");
#endif

#if !ENABLE_ASH_INTERNAL_GLOB
# include <glob.h>
#endif

#include "unicode.h"
#include "shell_common.h"
#if ENABLE_FEATURE_SH_MATH
# include "math.h"
#else
typedef long arith_t;
# define ARITH_FMT "%ld"
#endif
#if ENABLE_ASH_RANDOM_SUPPORT
# include "random.h"
#else
# define CLEAR_RANDOM_T(rnd) ((void)0)
#endif

#include "NUM_APPLETS.h"
#if NUM_APPLETS == 1
/* STANDALONE does not make sense, and won't compile */
# undef CONFIG_FEATURE_SH_STANDALONE
# undef ENABLE_FEATURE_SH_STANDALONE
# undef IF_FEATURE_SH_STANDALONE
# undef IF_NOT_FEATURE_SH_STANDALONE
# define ENABLE_FEATURE_SH_STANDALONE 0
# define IF_FEATURE_SH_STANDALONE(...)
# define IF_NOT_FEATURE_SH_STANDALONE(...) __VA_ARGS__
#endif

#ifndef F_DUPFD_CLOEXEC
# define F_DUPFD_CLOEXEC F_DUPFD
#endif
#ifndef O_CLOEXEC
# define O_CLOEXEC 0
#endif
#ifndef PIPE_BUF
# define PIPE_BUF 4096           /* amount of buffering in a pipe */
#endif

#if !BB_MMU
# error "Do not even bother, ash will not run on NOMMU machine"
#endif

/* We use a trick to have more optimized code (fewer pointer reloads):
 *  ash.c:   extern struct globals *const ash_ptr_to_globals;
 *  ash_ptr_hack.c: struct globals *ash_ptr_to_globals;
 * This way, compiler in ash.c knows the pointer can not change.
 *
 * However, this may break on weird arches or toolchains. In this case,
 * set "-DBB_GLOBAL_CONST=''" in CONFIG_EXTRA_CFLAGS to disable
 * this optimization.
 */
#ifndef BB_GLOBAL_CONST
# define BB_GLOBAL_CONST const
#endif


/* ============ Hash table sizes. Configurable. */

#define VTABSIZE 39
#define ATABSIZE 39
#define CMDTABLESIZE 31         /* should be prime */


/* ============ Shell options */

static const char *const optletters_optnames[] = {
        "e"   "errexit",
        "f"   "noglob",
        "I"   "ignoreeof",
/* The below allowed this invocation:
 * ash -c 'set -i; echo $-; sleep 5; echo $-'
 * to be ^C-ed and get to interactive ash prompt.
 * bash does not support such "set -i".
 * In our code, this is denoted by empty long name:
 */
        "i"   "",
        "m"   "monitor",
        "n"   "noexec",
/* Ditto: bash has no "set -s" */
        "s"   "",
        "c"   "",
        "x"   "xtrace",
        "v"   "verbose",
        "C"   "noclobber",
        "a"   "allexport",
        "b"   "notify",
        "u"   "nounset",
        "\0"  "vi"
#if BASH_PIPEFAIL
        ,"\0"  "pipefail"
#endif
#if DEBUG
        ,"\0"  "nolog"
        ,"\0"  "debug"
#endif
};
//bash 4.4.23 also has these opts (with these defaults):
//braceexpand           on
//emacs                 on
//errtrace              off
//functrace             off
//hashall               on
//histexpand            off
//history               on
//interactive-comments  on
//keyword               off
//onecmd                off
//physical              off
//posix                 off
//privileged            off

#define optletters(n)  optletters_optnames[n][0]
#define optnames(n)   (optletters_optnames[n] + 1)

enum { NOPTS = ARRAY_SIZE(optletters_optnames) };


/* ============ Misc data */

#define msg_illnum "Illegal number: %s"

/*
 * We enclose jmp_buf in a structure so that we can declare pointers to
 * jump locations.  The global variable handler contains the location to
 * jump to when an exception occurs, and the global variable exception_type
 * contains a code identifying the exception.  To implement nested
 * exception handlers, the user should save the value of handler on entry
 * to an inner scope, set handler to point to a jmploc structure for the
 * inner scope, and restore handler on exit from the scope.
 */
struct jmploc {
        jmp_buf loc;
};

struct globals_misc {
        uint8_t exitstatus;     /* exit status of last command */
        uint8_t back_exitstatus;/* exit status of backquoted command */
        smallint job_warning;   /* user was warned about stopped jobs (can be 2, 1 or 0). */
        int rootpid;            /* pid of main shell */
        /* shell level: 0 for the main shell, 1 for its children, and so on */
        int shlvl;
#define rootshell (!shlvl)
        int errlinno;

        char *minusc;  /* argument to -c option */

        char *curdir; // = nullstr;     /* current working directory */
        char *physdir; // = nullstr;    /* physical working directory */

        char *arg0; /* value of $0 */

        struct jmploc *exception_handler;

        volatile int suppress_int; /* counter */
        volatile /*sig_atomic_t*/ smallint pending_int; /* 1 = got SIGINT */
        volatile /*sig_atomic_t*/ smallint got_sigchld; /* 1 = got SIGCHLD */
        volatile /*sig_atomic_t*/ smallint pending_sig; /* last pending signal */
        smallint exception_type; /* kind of exception (0..5) */
        /* exceptions */
#define EXINT 0         /* SIGINT received */
#define EXERROR 1       /* a generic error */
#define EXEXIT 4        /* exit the shell */

        char nullstr[1];        /* zero length string */

        char optlist[NOPTS];
#define eflag optlist[0]
#define fflag optlist[1]
#define Iflag optlist[2]
#define iflag optlist[3]
#define mflag optlist[4]
#define nflag optlist[5]
#define sflag optlist[6]
#define cflag optlist[7]
#define xflag optlist[8]
#define vflag optlist[9]
#define Cflag optlist[10]
#define aflag optlist[11]
#define bflag optlist[12]
#define uflag optlist[13]
#define viflag optlist[14]
#if BASH_PIPEFAIL
# define pipefail optlist[15]
#else
# define pipefail 0
#endif
#if DEBUG
# define nolog optlist[15 + BASH_PIPEFAIL]
# define debug optlist[16 + BASH_PIPEFAIL]
#endif

        /* trap handler commands */
        /*
         * Sigmode records the current value of the signal handlers for the various
         * modes.  A value of zero means that the current handler is not known.
         * S_HARD_IGN indicates that the signal was ignored on entry to the shell.
         */
        char sigmode[NSIG - 1];
#define S_DFL      1            /* default signal handling (SIG_DFL) */
#define S_CATCH    2            /* signal is caught */
#define S_IGN      3            /* signal is ignored (SIG_IGN) */
#define S_HARD_IGN 4            /* signal is ignored permanently (it was SIG_IGN on entry to shell) */

        /* indicates specified signal received */
        uint8_t gotsig[NSIG - 1]; /* offset by 1: "signal" 0 is meaningless */
        uint8_t may_have_traps; /* 0: definitely no traps are set, 1: some traps may be set */
        char *trap[NSIG];
        char **trap_ptr;        /* used only by "trap hack" */

        /* Rarely referenced stuff */
#if ENABLE_ASH_RANDOM_SUPPORT
        random_t random_gen;
#endif
        pid_t backgndpid;        /* pid of last background process */
};
extern struct globals_misc *BB_GLOBAL_CONST ash_ptr_to_globals_misc;
#define G_misc (*ash_ptr_to_globals_misc)
#define exitstatus        (G_misc.exitstatus )
#define back_exitstatus   (G_misc.back_exitstatus )
#define job_warning       (G_misc.job_warning)
#define rootpid     (G_misc.rootpid    )
#define shlvl       (G_misc.shlvl      )
#define errlinno    (G_misc.errlinno   )
#define minusc      (G_misc.minusc     )
#define curdir      (G_misc.curdir     )
#define physdir     (G_misc.physdir    )
#define arg0        (G_misc.arg0       )
#define exception_handler (G_misc.exception_handler)
#define exception_type    (G_misc.exception_type   )
#define suppress_int      (G_misc.suppress_int     )
#define pending_int       (G_misc.pending_int      )
#define got_sigchld       (G_misc.got_sigchld      )
#define pending_sig       (G_misc.pending_sig      )
#define nullstr     (G_misc.nullstr    )
#define optlist     (G_misc.optlist    )
#define sigmode     (G_misc.sigmode    )
#define gotsig      (G_misc.gotsig     )
#define may_have_traps    (G_misc.may_have_traps   )
#define trap        (G_misc.trap       )
#define trap_ptr    (G_misc.trap_ptr   )
#define random_gen  (G_misc.random_gen )
#define backgndpid  (G_misc.backgndpid )
#define INIT_G_misc() do { \
        (*(struct globals_misc**)&ash_ptr_to_globals_misc) = xzalloc(sizeof(G_misc)); \
        barrier(); \
        curdir = nullstr; \
        physdir = nullstr; \
        trap_ptr = trap; \
} while (0)


/* ============ DEBUG */
#if DEBUG
static void trace_printf(const char *fmt, ...);
static void trace_vprintf(const char *fmt, va_list va);
# define TRACE(param)    trace_printf param
# define TRACEV(param)   trace_vprintf param
# define close(fd) do { \
        int dfd = (fd); \
        if (close(dfd) < 0) \
                bb_error_msg("bug on %d: closing %d(0x%x)", \
                        __LINE__, dfd, dfd); \
} while (0)
#else
# define TRACE(param)
# define TRACEV(param)
#endif


/* ============ Utility functions */
#define is_name(c)      ((c) == '_' || isalpha((unsigned char)(c)))
#define is_in_name(c)   ((c) == '_' || isalnum((unsigned char)(c)))

static int
isdigit_str9(const char *str)
{
        int maxlen = 9 + 1; /* max 9 digits: 999999999 */
        while (--maxlen && isdigit(*str))
                str++;
        return (*str == '\0');
}

static const char *
var_end(const char *var)
{
        while (*var)
                if (*var++ == '=')
                        break;
        return var;
}


/* ============ Interrupts / exceptions */

static void exitshell(void) NORETURN;

/*
 * These macros allow the user to suspend the handling of interrupt signals
 * over a period of time.  This is similar to SIGHOLD or to sigblock, but
 * much more efficient and portable.  (But hacking the kernel is so much
 * more fun than worrying about efficiency and portability. :-))
 */
#if DEBUG_INTONOFF
# define INT_OFF do { \
        TRACE(("%s:%d INT_OFF(%d)\n", __func__, __LINE__, suppress_int)); \
        suppress_int++; \
        barrier(); \
} while (0)
#else
# define INT_OFF do { \
        suppress_int++; \
        barrier(); \
} while (0)
#endif

/*
 * Called to raise an exception.  Since C doesn't include exceptions, we
 * just do a longjmp to the exception handler.  The type of exception is
 * stored in the global variable "exception_type".
 */
static void raise_exception(int) NORETURN;
static void
raise_exception(int e)
{
#if DEBUG
        if (exception_handler == NULL)
                abort();
#endif
        INT_OFF;
        exception_type = e;
        longjmp(exception_handler->loc, 1);
}
#if DEBUG
#define raise_exception(e) do { \
        TRACE(("raising exception %d on line %d\n", (e), __LINE__)); \
        raise_exception(e); \
} while (0)
#endif

/*
 * Called when a SIGINT is received.  (If the user specifies
 * that SIGINT is to be trapped or ignored using the trap builtin, then
 * this routine is not called.)  Suppressint is nonzero when interrupts
 * are held using the INT_OFF macro.  (The test for iflag is just
 * defensive programming.)
 */
static void raise_interrupt(void) NORETURN;
static void
raise_interrupt(void)
{
        pending_int = 0;
        /* Signal is not automatically unmasked after it is raised,
         * do it ourself - unmask all signals */
        sigprocmask_allsigs(SIG_UNBLOCK);
        /* pending_sig = 0; - now done in signal_handler() */

        if (!(rootshell && iflag)) {
                /* Kill ourself with SIGINT */
                signal(SIGINT, SIG_DFL);
                raise(SIGINT);
        }
        /* bash: ^C even on empty command line sets $? */
        exitstatus = SIGINT + 128;
        raise_exception(EXINT);
        /* NOTREACHED */
}
#if DEBUG
#define raise_interrupt() do { \
        TRACE(("raising interrupt on line %d\n", __LINE__)); \
        raise_interrupt(); \
} while (0)
#endif

static IF_ASH_OPTIMIZE_FOR_SIZE(inline) void
int_on(void)
{
        barrier();
        if (--suppress_int == 0 && pending_int) {
                raise_interrupt();
        }
}
#if DEBUG_INTONOFF
# define INT_ON do { \
        TRACE(("%s:%d INT_ON(%d)\n", __func__, __LINE__, suppress_int-1)); \
        int_on(); \
} while (0)
#else
# define INT_ON int_on()
#endif
static IF_ASH_OPTIMIZE_FOR_SIZE(inline) void
force_int_on(void)
{
        barrier();
        suppress_int = 0;
        if (pending_int)
                raise_interrupt();
}
#define FORCE_INT_ON force_int_on()

#define SAVE_INT(v) ((v) = suppress_int)

#define RESTORE_INT(v) do { \
        barrier(); \
        suppress_int = (v); \
        if (suppress_int == 0 && pending_int) \
                raise_interrupt(); \
} while (0)


/* ============ Stdout/stderr output */

static void
outstr(const char *p, FILE *file)
{
        INT_OFF;
        fputs(p, file);
        INT_ON;
}

static void
flush_stdout_stderr(void)
{
        INT_OFF;
        fflush_all();
        INT_ON;
}

/* Was called outcslow(c,FILE*), but c was always '\n' */
static void
newline_and_flush(FILE *dest)
{
        INT_OFF;
        putc('\n', dest);
        fflush(dest);
        INT_ON;
}

static int out1fmt(const char *, ...) __attribute__((__format__(__printf__,1,2)));
static int
out1fmt(const char *fmt, ...)
{
        va_list ap;
        int r;

        INT_OFF;
        va_start(ap, fmt);
        r = vprintf(fmt, ap);
        va_end(ap);
        INT_ON;
        return r;
}

static int fmtstr(char *, size_t, const char *, ...) __attribute__((__format__(__printf__,3,4)));
static int
fmtstr(char *outbuf, size_t length, const char *fmt, ...)
{
        va_list ap;
        int ret;

        INT_OFF;
        va_start(ap, fmt);
        ret = vsnprintf(outbuf, length, fmt, ap);
        va_end(ap);
        INT_ON;
        return ret;
}

static void
out1str(const char *p)
{
        outstr(p, stdout);
}

static void
out2str(const char *p)
{
        outstr(p, stderr);
        flush_stdout_stderr();
}


/* ============ Parser structures */

/* control characters in argument strings */
#define CTL_FIRST CTLESC
#define CTLESC       ((unsigned char)'\201')    /* escape next character */
#define CTLVAR       ((unsigned char)'\202')    /* variable defn */
#define CTLENDVAR    ((unsigned char)'\203')
#define CTLBACKQ     ((unsigned char)'\204')
#define CTLARI       ((unsigned char)'\206')    /* arithmetic expression */
#define CTLENDARI    ((unsigned char)'\207')
#define CTLQUOTEMARK ((unsigned char)'\210')
#define CTL_LAST CTLQUOTEMARK

/* variable substitution byte (follows CTLVAR) */
#define VSTYPE  0x0f            /* type of variable substitution */
#define VSNUL   0x10            /* colon--treat the empty string as unset */

/* values of VSTYPE field */
#define VSNORMAL        0x1     /* normal variable:  $var or ${var} */
#define VSMINUS         0x2     /* ${var-text} */
#define VSPLUS          0x3     /* ${var+text} */
#define VSQUESTION      0x4     /* ${var?message} */
#define VSASSIGN        0x5     /* ${var=text} */
#define VSTRIMRIGHT     0x6     /* ${var%pattern} */
#define VSTRIMRIGHTMAX  0x7     /* ${var%%pattern} */
#define VSTRIMLEFT      0x8     /* ${var#pattern} */
#define VSTRIMLEFTMAX   0x9     /* ${var##pattern} */
#define VSLENGTH        0xa     /* ${#var} */
#if BASH_SUBSTR
#define VSSUBSTR        0xc     /* ${var:position:length} */
#endif
#if BASH_PATTERN_SUBST
#define VSREPLACE       0xd     /* ${var/pattern/replacement} */
#define VSREPLACEALL    0xe     /* ${var//pattern/replacement} */
#endif

static const char dolatstr[] ALIGN1 = {
        CTLQUOTEMARK, CTLVAR, VSNORMAL, '@', '=', CTLQUOTEMARK, '\0'
};
#define DOLATSTRLEN 6

#define NCMD      0
#define NPIPE     1
#define NREDIR    2
#define NBACKGND  3
#define NSUBSHELL 4
#define NAND      5
#define NOR       6
#define NSEMI     7
#define NIF       8
#define NWHILE    9
#define NUNTIL   10
#define NFOR     11
#define NCASE    12
#define NCLIST   13
#define NDEFUN   14
#define NARG     15
#define NTO      16
#if BASH_REDIR_OUTPUT
#define NTO2     17
#endif
#define NCLOBBER 18
#define NFROM    19
#define NFROMTO  20
#define NAPPEND  21
#define NTOFD    22
#define NFROMFD  23
#define NHERE    24
#define NXHERE   25
#define NNOT     26
#define N_NUMBER 27

union node;

struct ncmd {
        smallint type; /* Nxxxx */
        int linno;
        union node *assign;
        union node *args;
        union node *redirect;
};

struct npipe {
        smallint type;
        smallint pipe_backgnd;
        struct nodelist *cmdlist;
};

struct nredir {
        smallint type;
        int linno;
        union node *n;
        union node *redirect;
};

struct nbinary {
        smallint type;
        union node *ch1;
        union node *ch2;
};

struct nif {
        smallint type;
        union node *test;
        union node *ifpart;
        union node *elsepart;
};

struct nfor {
        smallint type;
        int linno;
        union node *args;
        union node *body;
        char *var;
};

struct ncase {
        smallint type;
        int linno;
        union node *expr;
        union node *cases;
};

struct nclist {
        smallint type;
        union node *next;
        union node *pattern;
        union node *body;
};

struct ndefun {
        smallint type;
        int linno;
        char *text;
        union node *body;
};

struct narg {
        smallint type;
        union node *next;
        char *text;
        struct nodelist *backquote;
};

/* nfile and ndup layout must match!
 * NTOFD (>&fdnum) uses ndup structure, but we may discover mid-flight
 * that it is actually NTO2 (>&file), and change its type.
 */
struct nfile {
        smallint type;
        union node *next;
        int fd;
        int _unused_dupfd;
        union node *fname;
        char *expfname;
};

struct ndup {
        smallint type;
        union node *next;
        int fd;
        int dupfd;
        union node *vname;
        char *_unused_expfname;
};

struct nhere {
        smallint type;
        union node *next;
        int fd;
        union node *doc;
};

struct nnot {
        smallint type;
        union node *com;
};

union node {
        smallint type;
        struct ncmd ncmd;
        struct npipe npipe;
        struct nredir nredir;
        struct nbinary nbinary;
        struct nif nif;
        struct nfor nfor;
        struct ncase ncase;
        struct nclist nclist;
        struct ndefun ndefun;
        struct narg narg;
        struct nfile nfile;
        struct ndup ndup;
        struct nhere nhere;
        struct nnot nnot;
};

/*
 * NODE_EOF is returned by parsecmd when it encounters an end of file.
 * It must be distinct from NULL.
 */
#define NODE_EOF ((union node *) -1L)

struct nodelist {
        struct nodelist *next;
        union node *n;
};

struct funcnode {
        int count;
        union node n;
};

/*
 * Free a parse tree.
 */
static void
freefunc(struct funcnode *f)
{
        if (f && --f->count < 0)
                free(f);
}


/* ============ Debugging output */

#if DEBUG

static FILE *tracefile;

static void
trace_printf(const char *fmt, ...)
{
        va_list va;

        if (debug != 1)
                return;
        if (DEBUG_TIME)
                fprintf(tracefile, "%u ", (int) time(NULL));
        if (DEBUG_PID)
                fprintf(tracefile, "[%u] ", (int) getpid());
        if (DEBUG_SIG)
                fprintf(tracefile, "pending s:%d i:%d(supp:%d) ", pending_sig, pending_int, suppress_int);
        va_start(va, fmt);
        vfprintf(tracefile, fmt, va);
        va_end(va);
}

static void
trace_vprintf(const char *fmt, va_list va)
{
        if (debug != 1)
                return;
        vfprintf(tracefile, fmt, va);
        fprintf(tracefile, "\n");
}

static void
trace_puts(const char *s)
{
        if (debug != 1)
                return;
        fputs(s, tracefile);
}

static void
trace_puts_quoted(char *s)
{
        char *p;
        char c;

        if (debug != 1)

                return;
        putc('"', tracefile);
        for (p = s; *p; p++) {
                switch ((unsigned char)*p) {
                case '\n': c = 'n'; goto backslash;
                case '\t': c = 't'; goto backslash;
                case '\r': c = 'r'; goto backslash;
                case '\"': c = '\"'; goto backslash;
                case '\\': c = '\\'; goto backslash;
                case CTLESC: c = 'e'; goto backslash;
                case CTLVAR: c = 'v'; goto backslash;
                case CTLBACKQ: c = 'q'; goto backslash;
 backslash:
                        putc('\\', tracefile);
                        putc(c, tracefile);
                        break;
                default:
                        if (*p >= ' ' && *p <= '~')
                                putc(*p, tracefile);
                        else {
                                putc('\\', tracefile);
                                putc((*p >> 6) & 03, tracefile);
                                putc((*p >> 3) & 07, tracefile);
                                putc(*p & 07, tracefile);
                        }
                        break;
                }
        }
        putc('"', tracefile);
}

static void
trace_puts_args(char **ap)
{
        if (debug != 1)
                return;
        if (!*ap)
                return;
        while (1) {
                trace_puts_quoted(*ap);
                if (!*++ap) {
                        putc('\n', tracefile);
                        break;
                }
                putc(' ', tracefile);
        }
}

static void
opentrace(void)
{
        char s[100];
#ifdef O_APPEND
        int flags;
#endif

        if (debug != 1) {
                if (tracefile)
                        fflush(tracefile);
                /* leave open because libedit might be using it */
                return;
        }
        strcpy(s, "./trace");
        if (tracefile) {
                if (!freopen(s, "a", tracefile)) {
                        fprintf(stderr, "Can't re-open %s\n", s);
                        debug = 0;
                        return;
                }
        } else {
                tracefile = fopen(s, "a");
                if (tracefile == NULL) {
                        fprintf(stderr, "Can't open %s\n", s);
                        debug = 0;
                        return;
                }
        }
#ifdef O_APPEND
        flags = fcntl(fileno(tracefile), F_GETFL);
        if (flags >= 0)
                fcntl(fileno(tracefile), F_SETFL, flags | O_APPEND);
#endif
        setlinebuf(tracefile);
        fputs("\nTracing started.\n", tracefile);
}

static void
indent(int amount, char *pfx, FILE *fp)
{
        int i;

        for (i = 0; i < amount; i++) {
                if (pfx && i == amount - 1)
                        fputs(pfx, fp);
                putc('\t', fp);
        }
}

/* little circular references here... */
static void shtree(union node *n, int ind, char *pfx, FILE *fp);

static void
sharg(union node *arg, FILE *fp)
{
        char *p;
        struct nodelist *bqlist;
        unsigned char subtype;

        if (arg->type != NARG) {
                out1fmt("<node type %d>\n", arg->type);
                abort();
        }
        bqlist = arg->narg.backquote;
        for (p = arg->narg.text; *p; p++) {
                switch ((unsigned char)*p) {
                case CTLESC:
                        p++;
                        putc(*p, fp);
                        break;
                case CTLVAR:
                        putc('$', fp);
                        putc('{', fp);
                        subtype = *++p;
                        if (subtype == VSLENGTH)
                                putc('#', fp);

                        while (*p != '=') {
                                putc(*p, fp);
                                p++;
                        }

                        if (subtype & VSNUL)
                                putc(':', fp);

                        switch (subtype & VSTYPE) {
                        case VSNORMAL:
                                putc('}', fp);
                                break;
                        case VSMINUS:
                                putc('-', fp);
                                break;
                        case VSPLUS:
                                putc('+', fp);
                                break;
                        case VSQUESTION:
                                putc('?', fp);
                                break;
                        case VSASSIGN:
                                putc('=', fp);
                                break;
                        case VSTRIMLEFT:
                                putc('#', fp);
                                break;
                        case VSTRIMLEFTMAX:
                                putc('#', fp);
                                putc('#', fp);
                                break;
                        case VSTRIMRIGHT:
                                putc('%', fp);
                                break;
                        case VSTRIMRIGHTMAX:
                                putc('%', fp);
                                putc('%', fp);
                                break;
                        case VSLENGTH:
                                break;
                        default:
                                out1fmt("<subtype %d>", subtype);
                        }
                        break;
                case CTLENDVAR:
                        putc('}', fp);
                        break;
                case CTLBACKQ:
                        putc('$', fp);
                        putc('(', fp);
                        shtree(bqlist->n, -1, NULL, fp);
                        putc(')', fp);
                        break;
                default:
                        putc(*p, fp);
                        break;
                }
        }
}

static void
shcmd(union node *cmd, FILE *fp)
{
        union node *np;
        int first;
        const char *s;
        int dftfd;

        first = 1;
        for (np = cmd->ncmd.args; np; np = np->narg.next) {
                if (!first)
                        putc(' ', fp);
                sharg(np, fp);
                first = 0;
        }
        for (np = cmd->ncmd.redirect; np; np = np->nfile.next) {
                if (!first)
                        putc(' ', fp);
                dftfd = 0;
                switch (np->nfile.type) {
                case NTO:      s = ">>"+1; dftfd = 1; break;
                case NCLOBBER: s = ">|"; dftfd = 1; break;
                case NAPPEND:  s = ">>"; dftfd = 1; break;
#if BASH_REDIR_OUTPUT
                case NTO2:
#endif
                case NTOFD:    s = ">&"; dftfd = 1; break;
                case NFROM:    s = "<"; break;
                case NFROMFD:  s = "<&"; break;
                case NFROMTO:  s = "<>"; break;
                default:       s = "*error*"; break;
                }
                if (np->nfile.fd != dftfd)
                        fprintf(fp, "%d", np->nfile.fd);
                fputs(s, fp);
                if (np->nfile.type == NTOFD || np->nfile.type == NFROMFD) {
                        fprintf(fp, "%d", np->ndup.dupfd);
                } else {
                        sharg(np->nfile.fname, fp);
                }
                first = 0;
        }
}

static void
shtree(union node *n, int ind, char *pfx, FILE *fp)
{
        struct nodelist *lp;
        const char *s;

        if (n == NULL)
                return;

        indent(ind, pfx, fp);

        if (n == NODE_EOF) {
                fputs("<EOF>", fp);
                return;
        }

        switch (n->type) {
        case NSEMI:
                s = "; ";
                goto binop;
        case NAND:
                s = " && ";
                goto binop;
        case NOR:
                s = " || ";
 binop:
                shtree(n->nbinary.ch1, ind, NULL, fp);
                /* if (ind < 0) */
                        fputs(s, fp);
                shtree(n->nbinary.ch2, ind, NULL, fp);
                break;
        case NCMD:
                shcmd(n, fp);
                if (ind >= 0)
                        putc('\n', fp);
                break;
        case NPIPE:
                for (lp = n->npipe.cmdlist; lp; lp = lp->next) {
                        shtree(lp->n, 0, NULL, fp);
                        if (lp->next)
                                fputs(" | ", fp);
                }
                if (n->npipe.pipe_backgnd)
                        fputs(" &", fp);
                if (ind >= 0)
                        putc('\n', fp);
                break;
        default:
                fprintf(fp, "<node type %d>", n->type);
                if (ind >= 0)
                        putc('\n', fp);
                break;
        }
}

static void
showtree(union node *n)
{
        trace_puts("showtree called\n");
        shtree(n, 1, NULL, stderr);
}

#endif /* DEBUG */


/* ============ Parser data */

/*
 * ash_vmsg() needs parsefile->fd, hence parsefile definition is moved up.
 */
struct strlist {
        struct strlist *next;
        char *text;
};

struct alias;

struct strpush {
        struct strpush *prev;   /* preceding string on stack */
        char *prev_string;
        int prev_left_in_line;
#if ENABLE_ASH_ALIAS
        struct alias *ap;       /* if push was associated with an alias */
#endif
        char *string;           /* remember the string since it may change */

        /* Remember last two characters for pungetc. */
        int lastc[2];

        /* Number of outstanding calls to pungetc. */
        int unget;
};

/*
 * The parsefile structure pointed to by the global variable parsefile
 * contains information about the current file being read.
 */
struct parsefile {
        struct parsefile *prev; /* preceding file on stack */
        int linno;              /* current line */
        int pf_fd;              /* file descriptor (or -1 if string) */
        int left_in_line;       /* number of chars left in this line */
        int left_in_buffer;     /* number of chars left in this buffer past the line */
        char *next_to_pgetc;    /* next char in buffer */
        char *buf;              /* input buffer */
        struct strpush *strpush; /* for pushing strings at this level */
        struct strpush basestrpush; /* so pushing one is fast */

        /* Remember last two characters for pungetc. */
        int lastc[2];

        /* Number of outstanding calls to pungetc. */
        int unget;
};

static struct parsefile basepf;        /* top level input file */
static struct parsefile *g_parsefile = &basepf;  /* current input file */
static char *commandname;              /* currently executing command */


/* ============ Message printing */

static void
ash_vmsg(const char *msg, va_list ap)
{
        fprintf(stderr, "%s: ", arg0);
        if (commandname) {
                if (strcmp(arg0, commandname))
                        fprintf(stderr, "%s: ", commandname);
                if (!iflag || g_parsefile->pf_fd > 0)
                        fprintf(stderr, "line %d: ", errlinno);
        }
        vfprintf(stderr, msg, ap);
        newline_and_flush(stderr);
}

/*
 * Exverror is called to raise the error exception.  If the second argument
 * is not NULL then error prints an error message using printf style
 * formatting.  It then raises the error exception.
 */
static void ash_vmsg_and_raise(int, const char *, va_list) NORETURN;
static void
ash_vmsg_and_raise(int cond, const char *msg, va_list ap)
{
#if DEBUG
        if (msg) {
                TRACE(("ash_vmsg_and_raise(%d):", cond));
                TRACEV((msg, ap));
        } else
                TRACE(("ash_vmsg_and_raise(%d):NULL\n", cond));
        if (msg)
#endif
                ash_vmsg(msg, ap);

        flush_stdout_stderr();
        raise_exception(cond);
        /* NOTREACHED */
}

static void ash_msg_and_raise_error(const char *, ...) NORETURN;
static void
ash_msg_and_raise_error(const char *msg, ...)
{
        va_list ap;

        exitstatus = 2;

        va_start(ap, msg);
        ash_vmsg_and_raise(EXERROR, msg, ap);
        /* NOTREACHED */
        va_end(ap);
}

/*
 * 'fmt' must be a string literal.
 */
#define ash_msg_and_raise_perror(fmt, ...) ash_msg_and_raise_error(fmt ": "STRERROR_FMT, ##__VA_ARGS__ STRERROR_ERRNO)

static void raise_error_syntax(const char *) NORETURN;
static void
raise_error_syntax(const char *msg)
{
        errlinno = g_parsefile->linno;
        ash_msg_and_raise_error("syntax error: %s", msg);
        /* NOTREACHED */
}

static void ash_msg_and_raise(int, const char *, ...) NORETURN;
static void
ash_msg_and_raise(int cond, const char *msg, ...)
{
        va_list ap;

        va_start(ap, msg);
        ash_vmsg_and_raise(cond, msg, ap);
        /* NOTREACHED */
        va_end(ap);
}

/*
 * error/warning routines for external builtins
 */
static void
ash_msg(const char *fmt, ...)
{
        va_list ap;

        va_start(ap, fmt);
        ash_vmsg(fmt, ap);
        va_end(ap);
}

/*
 * Return a string describing an error.  The returned string may be a
 * pointer to a static buffer that will be overwritten on the next call.
 * Action describes the operation that got the error.
 */
static const char *
errmsg(int e, const char *em)
{
        if (e == ENOENT || e == ENOTDIR) {
                return em;
        }
        return strerror(e);
}


/* ============ Memory allocation */

#if 0
/* I consider these wrappers nearly useless:
 * ok, they return you to nearest exception handler, but
 * how much memory do you leak in the process, making
 * memory starvation worse?
 */
static void *
ckrealloc(void * p, size_t nbytes)
{
        p = realloc(p, nbytes);
        if (!p)
                ash_msg_and_raise_error(bb_msg_memory_exhausted);
        return p;
}

static void *
ckmalloc(size_t nbytes)
{
        return ckrealloc(NULL, nbytes);
}

static void *
ckzalloc(size_t nbytes)
{
        return memset(ckmalloc(nbytes), 0, nbytes);
}

static char *
ckstrdup(const char *s)
{
        char *p = strdup(s);
        if (!p)
                ash_msg_and_raise_error(bb_msg_memory_exhausted);
        return p;
}
#else
/* Using bbox equivalents. They exit if out of memory */
# define ckrealloc xrealloc
# define ckmalloc  xmalloc
# define ckzalloc  xzalloc
# define ckstrdup  xstrdup
#endif

/*
 * It appears that grabstackstr() will barf with such alignments
 * because stalloc() will return a string allocated in a new stackblock.
 */
#define SHELL_ALIGN(nbytes) (((nbytes) + SHELL_SIZE) & ~SHELL_SIZE)
enum {
        /* Most machines require the value returned from malloc to be aligned
         * in some way.  The following macro will get this right
         * on many machines.  */
        SHELL_SIZE = sizeof(union { int i; char *cp; double d; }) - 1,
        /* Minimum size of a block */
        MINSIZE = SHELL_ALIGN(504),
};

struct stack_block {
        struct stack_block *prev;
        char space[MINSIZE];
};

struct stackmark {
        struct stack_block *stackp;
        char *stacknxt;
        size_t stacknleft;
};


struct globals_memstack {
        struct stack_block *g_stackp; // = &stackbase;
        char *g_stacknxt; // = stackbase.space;
        char *sstrend; // = stackbase.space + MINSIZE;
        size_t g_stacknleft; // = MINSIZE;
        struct stack_block stackbase;
};
extern struct globals_memstack *BB_GLOBAL_CONST ash_ptr_to_globals_memstack;
#define G_memstack (*ash_ptr_to_globals_memstack)
#define g_stackp     (G_memstack.g_stackp    )
#define g_stacknxt   (G_memstack.g_stacknxt  )
#define sstrend      (G_memstack.sstrend     )
#define g_stacknleft (G_memstack.g_stacknleft)
#define stackbase    (G_memstack.stackbase   )
#define INIT_G_memstack() do { \
        (*(struct globals_memstack**)&ash_ptr_to_globals_memstack) = xzalloc(sizeof(G_memstack)); \
        barrier(); \
        g_stackp = &stackbase; \
        g_stacknxt = stackbase.space; \
        g_stacknleft = MINSIZE; \
        sstrend = stackbase.space + MINSIZE; \
} while (0)


#define stackblock()     ((void *)g_stacknxt)
#define stackblocksize() g_stacknleft

/*
 * Parse trees for commands are allocated in lifo order, so we use a stack
 * to make this more efficient, and also to avoid all sorts of exception
 * handling code to handle interrupts in the middle of a parse.
 *
 * The size 504 was chosen because the Ultrix malloc handles that size
 * well.
 */
static void *
stalloc(size_t nbytes)
{
        char *p;
        size_t aligned;

        aligned = SHELL_ALIGN(nbytes);
        if (aligned > g_stacknleft) {
                size_t len;
                size_t blocksize;
                struct stack_block *sp;

                blocksize = aligned;
                if (blocksize < MINSIZE)
                        blocksize = MINSIZE;
                len = sizeof(struct stack_block) - MINSIZE + blocksize;
                if (len < blocksize)
                        ash_msg_and_raise_error(bb_msg_memory_exhausted);
                INT_OFF;
                sp = ckmalloc(len);
                sp->prev = g_stackp;
                g_stacknxt = sp->space;
                g_stacknleft = blocksize;
                sstrend = g_stacknxt + blocksize;
                g_stackp = sp;
                INT_ON;
        }
        p = g_stacknxt;
        g_stacknxt += aligned;
        g_stacknleft -= aligned;
        return p;
}

static void *
stzalloc(size_t nbytes)
{
        return memset(stalloc(nbytes), 0, nbytes);
}

static void
stunalloc(void *p)
{
#if DEBUG
        if (!p || (g_stacknxt < (char *)p) || ((char *)p < g_stackp->space)) {
                write(STDERR_FILENO, "stunalloc\n", 10);
                abort();
        }
#endif
        g_stacknleft += g_stacknxt - (char *)p;
        g_stacknxt = p;
}

/*
 * Like strdup but works with the ash stack.
 */
static char *
sstrdup(const char *p)
{
        size_t len = strlen(p) + 1;
        return memcpy(stalloc(len), p, len);
}

static ALWAYS_INLINE void
grabstackblock(size_t len)
{
        stalloc(len);
}

static void
pushstackmark(struct stackmark *mark, size_t len)
{
        mark->stackp = g_stackp;
        mark->stacknxt = g_stacknxt;
        mark->stacknleft = g_stacknleft;
        grabstackblock(len);
}

static void
setstackmark(struct stackmark *mark)
{
        pushstackmark(mark, g_stacknxt == g_stackp->space && g_stackp != &stackbase);
}

static void
popstackmark(struct stackmark *mark)
{
        struct stack_block *sp;

        if (!mark->stackp)
                return;

        INT_OFF;
        while (g_stackp != mark->stackp) {
                sp = g_stackp;
                g_stackp = sp->prev;
                free(sp);
        }
        g_stacknxt = mark->stacknxt;
        g_stacknleft = mark->stacknleft;
        sstrend = mark->stacknxt + mark->stacknleft;
        INT_ON;
}

/*
 * When the parser reads in a string, it wants to stick the string on the
 * stack and only adjust the stack pointer when it knows how big the
 * string is.  Stackblock (defined in stack.h) returns a pointer to a block
 * of space on top of the stack and stackblocklen returns the length of
 * this block.  Growstackblock will grow this space by at least one byte,
 * possibly moving it (like realloc).  Grabstackblock actually allocates the
 * part of the block that has been used.
 */
static void
growstackblock(void)
{
        size_t newlen;

        newlen = g_stacknleft * 2;
        if (newlen < g_stacknleft)
                ash_msg_and_raise_error(bb_msg_memory_exhausted);
        if (newlen < 128)
                newlen += 128;

        if (g_stacknxt == g_stackp->space && g_stackp != &stackbase) {
                struct stack_block *sp;
                struct stack_block *prevstackp;
                size_t grosslen;

                INT_OFF;
                sp = g_stackp;
                prevstackp = sp->prev;
                grosslen = newlen + sizeof(struct stack_block) - MINSIZE;
                sp = ckrealloc(sp, grosslen);
                sp->prev = prevstackp;
                g_stackp = sp;
                g_stacknxt = sp->space;
                g_stacknleft = newlen;
                sstrend = sp->space + newlen;
                INT_ON;
        } else {
                char *oldspace = g_stacknxt;
                size_t oldlen = g_stacknleft;
                char *p = stalloc(newlen);

                /* free the space we just allocated */
                g_stacknxt = memcpy(p, oldspace, oldlen);
                g_stacknleft += newlen;
        }
}

/*
 * The following routines are somewhat easier to use than the above.
 * The user declares a variable of type STACKSTR, which may be declared
 * to be a register.  The macro STARTSTACKSTR initializes things.  Then
 * the user uses the macro STPUTC to add characters to the string.  In
 * effect, STPUTC(c, p) is the same as *p++ = c except that the stack is
 * grown as necessary.  When the user is done, she can just leave the
 * string there and refer to it using stackblock().  Or she can allocate
 * the space for it using grabstackstr().  If it is necessary to allow
 * someone else to use the stack temporarily and then continue to grow
 * the string, the user should use grabstack to allocate the space, and
 * then call ungrabstr(p) to return to the previous mode of operation.
 *
 * USTPUTC is like STPUTC except that it doesn't check for overflow.
 * CHECKSTACKSPACE can be called before USTPUTC to ensure that there
 * is space for at least one character.
 */
static void *
growstackstr(void)
{
        size_t len = stackblocksize();
        growstackblock();
        return (char *)stackblock() + len;
}

/*
 * Called from CHECKSTRSPACE.
 */
static char *
makestrspace(size_t newlen, char *p)
{
        size_t len = p - g_stacknxt;
        size_t size;

        for (;;) {
                size_t nleft;

                size = stackblocksize();
                nleft = size - len;
                if (nleft >= newlen)
                        break;
                growstackblock();
        }
        return (char *)stackblock() + len;
}

static char *
stack_nputstr(const char *s, size_t n, char *p)
{
        p = makestrspace(n, p);
        p = (char *)mempcpy(p, s, n);
        return p;
}

static char *
stack_putstr(const char *s, char *p)
{
        return stack_nputstr(s, strlen(s), p);
}

static char *
_STPUTC(int c, char *p)
{
        if (p == sstrend)
                p = growstackstr();
        *p++ = c;
        return p;
}

#define STARTSTACKSTR(p)        ((p) = stackblock())
#define STPUTC(c, p)            ((p) = _STPUTC((c), (p)))
#define CHECKSTRSPACE(n, p) do { \
        char *q = (p); \
        size_t l = (n); \
        size_t m = sstrend - q; \
        if (l > m) \
                (p) = makestrspace(l, q); \
} while (0)
#define USTPUTC(c, p)           (*(p)++ = (c))
#define STACKSTRNUL(p) do { \
        if ((p) == sstrend) \
                (p) = growstackstr(); \
        *(p) = '\0'; \
} while (0)
#define STUNPUTC(p)             (--(p))
#define STTOPC(p)               ((p)[-1])
#define STADJUST(amount, p)     ((p) += (amount))

#define grabstackstr(p)         stalloc((char *)(p) - (char *)stackblock())
#define ungrabstackstr(s, p)    stunalloc(s)
#define stackstrend()           ((void *)sstrend)


/* ============ String helpers */

/*
 * prefix -- see if pfx is a prefix of string.
 */
static char *
prefix(const char *string, const char *pfx)
{
        while (*pfx) {
                if (*pfx++ != *string++)
                        return NULL;
        }
        return (char *) string;
}

/*
 * Check for a valid number.  This should be elsewhere.
 */
static int
is_number(const char *p)
{
        do {
                if (!isdigit(*p))
                        return 0;
        } while (*++p != '\0');
        return 1;
}

/*
 * Convert a string of digits to an integer, printing an error message on
 * failure.
 */
static int
number(const char *s)
{
        if (!is_number(s))
                ash_msg_and_raise_error(msg_illnum, s);
        return atoi(s);
}

/*
 * Produce a single quoted string suitable as input to the shell.
 * The return string is allocated on the stack.
 */
static char *
single_quote(const char *s)
{
        char *p;

        STARTSTACKSTR(p);

        do {
                char *q;
                size_t len;

                len = strchrnul(s, '\'') - s;

                q = p = makestrspace(len + 3, p);

                *q++ = '\'';
                q = (char *)mempcpy(q, s, len);
                *q++ = '\'';
                s += len;

                STADJUST(q - p, p);

                if (*s != '\'')
                        break;
                len = 0;
                do len++; while (*++s == '\'');

                q = p = makestrspace(len + 3, p);

                *q++ = '"';
                q = (char *)mempcpy(q, s - len, len);
                *q++ = '"';

                STADJUST(q - p, p);
        } while (*s);

        USTPUTC('\0', p);

        return stackblock();
}

/*
 * Produce a possibly single quoted string suitable as input to the shell.
 * If quoting was done, the return string is allocated on the stack,
 * otherwise a pointer to the original string is returned.
 */
static const char *
maybe_single_quote(const char *s)
{
        const char *p = s;

        while (*p) {
                /* Assuming ACSII */
                /* quote ctrl_chars space !"#$%&'()* */
                if (*p < '+')
                        goto need_quoting;
                /* quote ;<=>? */
                if (*p >= ';' && *p <= '?')
                        goto need_quoting;
                /* quote `[\ */
                if (*p == '`')
                        goto need_quoting;
                if (*p == '[')
                        goto need_quoting;
                if (*p == '\\')
                        goto need_quoting;
                /* quote {|}~ DEL and high bytes */
                if (*p > 'z')
                        goto need_quoting;
                /* Not quoting these: +,-./ 0-9 :@ A-Z ]^_ a-z */
                /* TODO: maybe avoid quoting % */
                p++;
        }
        return s;

 need_quoting:
        return single_quote(s);
}


/* ============ nextopt */

static char **argptr;                  /* argument list for builtin commands */
static char *optionarg;                /* set by nextopt (like getopt) */
static char *optptr;                   /* used by nextopt */

/*
 * XXX - should get rid of. Have all builtins use getopt(3).
 * The library getopt must have the BSD extension static variable
 * "optreset", otherwise it can't be used within the shell safely.
 *
 * Standard option processing (a la getopt) for builtin routines.
 * The only argument that is passed to nextopt is the option string;
 * the other arguments are unnecessary. It returns the character,
 * or '\0' on end of input.
 */
static int
nextopt(const char *optstring)
{
        char *p;
        const char *q;
        char c;

        p = optptr;
        if (p == NULL || *p == '\0') {
                /* We ate entire "-param", take next one */
                p = *argptr;
                if (p == NULL)
                        return '\0';
                if (*p != '-')
                        return '\0';
                if (*++p == '\0') /* just "-" ? */
                        return '\0';
                argptr++;
                if (LONE_DASH(p)) /* "--" ? */
                        return '\0';
                /* p => next "-param" */
        }
        /* p => some option char in the middle of a "-param" */
        c = *p++;
        for (q = optstring; *q != c;) {
                if (*q == '\0')
                        ash_msg_and_raise_error("illegal option -%c", c);
                if (*++q == ':')
                        q++;
        }
        if (*++q == ':') {
                if (*p == '\0') {
                        p = *argptr++;
                        if (p == NULL)
                                ash_msg_and_raise_error("no arg for -%c option", c);
                }
                optionarg = p;
                p = NULL;
        }
        optptr = p;
        return c;
}


/* ============ Shell variables */

struct shparam {
        int nparam;             /* # of positional parameters (without $0) */
#if ENABLE_ASH_GETOPTS
        int optind;             /* next parameter to be processed by getopts */
        int optoff;             /* used by getopts */
#endif
        unsigned char malloced; /* if parameter list dynamically allocated */

        char **p;               /* parameter list */
};

/*
 * Free the list of positional parameters.
 */
static void
freeparam(volatile struct shparam *param)
{
        if (param->malloced) {
                char **ap, **ap1;
                ap = ap1 = param->p;
                while (*ap)
                        free(*ap++);
                free(ap1);
        }
}

#if ENABLE_ASH_GETOPTS
static void FAST_FUNC getoptsreset(const char *value);
#endif

struct var {
        struct var *next;               /* next entry in hash list */
        int flags;                      /* flags are defined above */
        const char *var_text;           /* name=value */
        void (*var_func)(const char *) FAST_FUNC; /* function to be called when  */
                                        /* the variable gets set/unset */
};

struct localvar {
        struct localvar *next;          /* next local variable in list */
        struct var *vp;                 /* the variable that was made local */
        int flags;                      /* saved flags */
        const char *text;               /* saved text */
};

/* flags */
#define VEXPORT         0x01    /* variable is exported */
#define VREADONLY       0x02    /* variable cannot be modified */
#define VSTRFIXED       0x04    /* variable struct is statically allocated */
#define VTEXTFIXED      0x08    /* text is statically allocated */
#define VSTACK          0x10    /* text is allocated on the stack */
#define VUNSET          0x20    /* the variable is not set */
#define VNOFUNC         0x40    /* don't call the callback function */
#define VNOSET          0x80    /* do not set variable - just readonly test */
#define VNOSAVE         0x100   /* when text is on the heap before setvareq */
#if ENABLE_ASH_RANDOM_SUPPORT
# define VDYNAMIC       0x200   /* dynamic variable */
#else
# define VDYNAMIC       0
#endif


/* Need to be before varinit_data[] */
#if ENABLE_LOCALE_SUPPORT
static void FAST_FUNC
change_lc_all(const char *value)
{
        if (value && *value != '\0')
                setlocale(LC_ALL, value);
}
static void FAST_FUNC
change_lc_ctype(const char *value)
{
        if (value && *value != '\0')
                setlocale(LC_CTYPE, value);
}
#endif
#if ENABLE_ASH_MAIL
static void chkmail(void);
static void changemail(const char *var_value) FAST_FUNC;
#else
# define chkmail()  ((void)0)
#endif
static void changepath(const char *) FAST_FUNC;
#if ENABLE_ASH_RANDOM_SUPPORT
static void change_random(const char *) FAST_FUNC;
#endif
#if BASH_EPOCH_VARS
static void change_seconds(const char *) FAST_FUNC;
static void change_realtime(const char *) FAST_FUNC;
#endif

static const struct {
        int flags;
        const char *var_text;
        void (*var_func)(const char *) FAST_FUNC;
} varinit_data[] = {
        /*
         * Note: VEXPORT would not work correctly here for NOFORK applets:
         * some environment strings may be constant.
         */
        { VSTRFIXED|VTEXTFIXED       , defifsvar   , NULL            },
#if ENABLE_ASH_MAIL
        { VSTRFIXED|VTEXTFIXED|VUNSET, "MAIL"      , changemail      },
        { VSTRFIXED|VTEXTFIXED|VUNSET, "MAILPATH"  , changemail      },
#endif
        { VSTRFIXED|VTEXTFIXED       , bb_PATH_root_path, changepath },
        { VSTRFIXED|VTEXTFIXED       , "PS1=$ "    , NULL            },
        { VSTRFIXED|VTEXTFIXED       , "PS2=> "    , NULL            },
        { VSTRFIXED|VTEXTFIXED       , "PS4=+ "    , NULL            },
#if ENABLE_ASH_GETOPTS
        { VSTRFIXED|VTEXTFIXED       , defoptindvar, getoptsreset    },
#endif
        { VSTRFIXED|VTEXTFIXED       , NULL /* inited to linenovar */, NULL },
#if ENABLE_ASH_RANDOM_SUPPORT
        { VSTRFIXED|VTEXTFIXED|VUNSET|VDYNAMIC, "RANDOM", change_random },
#endif
#if BASH_EPOCH_VARS
        { VSTRFIXED|VTEXTFIXED|VUNSET|VDYNAMIC, "EPOCHSECONDS", change_seconds },
        { VSTRFIXED|VTEXTFIXED|VUNSET|VDYNAMIC, "EPOCHREALTIME", change_realtime },
#endif
#if ENABLE_LOCALE_SUPPORT
        { VSTRFIXED|VTEXTFIXED|VUNSET, "LC_ALL"    , change_lc_all   },
        { VSTRFIXED|VTEXTFIXED|VUNSET, "LC_CTYPE"  , change_lc_ctype },
#endif
#if ENABLE_FEATURE_EDITING_SAVEHISTORY
        { VSTRFIXED|VTEXTFIXED|VUNSET, "HISTFILE"  , NULL            },
#endif
};

struct redirtab;

struct globals_var {
        struct shparam shellparam;      /* $@ current positional parameters */
        struct redirtab *redirlist;
        int preverrout_fd;   /* stderr fd: usually 2, unless redirect moved it */
        struct var *vartab[VTABSIZE];
        struct var varinit[ARRAY_SIZE(varinit_data)];
        int lineno;
        char linenovar[sizeof("LINENO=") + sizeof(int)*3];
};
extern struct globals_var *BB_GLOBAL_CONST ash_ptr_to_globals_var;
#define G_var (*ash_ptr_to_globals_var)
#define shellparam    (G_var.shellparam   )
//#define redirlist     (G_var.redirlist    )
#define preverrout_fd (G_var.preverrout_fd)
#define vartab        (G_var.vartab       )
#define varinit       (G_var.varinit      )
#define lineno        (G_var.lineno       )
#define linenovar     (G_var.linenovar    )
#define vifs      varinit[0]
#if ENABLE_ASH_MAIL
# define vmail    varinit[1]
# define vmpath   varinit[2]
#endif
#define VAR_OFFSET1 (ENABLE_ASH_MAIL*2)
#define vpath     varinit[VAR_OFFSET1 + 1]
#define vps1      varinit[VAR_OFFSET1 + 2]
#define vps2      varinit[VAR_OFFSET1 + 3]
#define vps4      varinit[VAR_OFFSET1 + 4]
#if ENABLE_ASH_GETOPTS
# define voptind  varinit[VAR_OFFSET1 + 5]
#endif
#define VAR_OFFSET2 (VAR_OFFSET1 + ENABLE_ASH_GETOPTS)
#define vlineno   varinit[VAR_OFFSET2 + 5]
#if ENABLE_ASH_RANDOM_SUPPORT
# define vrandom  varinit[VAR_OFFSET2 + 6]
#endif
#define VAR_OFFSET3 (VAR_OFFSET2 + ENABLE_ASH_RANDOM_SUPPORT)
#if BASH_EPOCH_VARS
# define vepochs  varinit[VAR_OFFSET3 + 6]
# define vepochr  varinit[VAR_OFFSET3 + 7]
#endif
#define INIT_G_var() do { \
        unsigned i; \
        (*(struct globals_var**)&ash_ptr_to_globals_var) = xzalloc(sizeof(G_var)); \
        barrier(); \
        for (i = 0; i < ARRAY_SIZE(varinit_data); i++) { \
                varinit[i].flags    = varinit_data[i].flags; \
                varinit[i].var_text = varinit_data[i].var_text; \
                varinit[i].var_func = varinit_data[i].var_func; \
        } \
        strcpy(linenovar, "LINENO="); \
        vlineno.var_text = linenovar; \
} while (0)

/*
 * The following macros access the values of the above variables.
 * They have to skip over the name.  They return the null string
 * for unset variables.
 */
#define ifsval()        (vifs.var_text + 4)
#define ifsset()        ((vifs.flags & VUNSET) == 0)
#if ENABLE_ASH_MAIL
# define mailval()      (vmail.var_text + 5)
# define mpathval()     (vmpath.var_text + 9)
# define mpathset()     ((vmpath.flags & VUNSET) == 0)
#endif
#define pathval()       (vpath.var_text + 5)
#define ps1val()        (vps1.var_text + 4)
#define ps2val()        (vps2.var_text + 4)
#define ps4val()        (vps4.var_text + 4)
#if ENABLE_ASH_GETOPTS
# define optindval()    (voptind.var_text + 7)
#endif

#if ENABLE_ASH_GETOPTS
static void FAST_FUNC
getoptsreset(const char *value)
{
        shellparam.optind = 1;
        if (is_number(value))
                shellparam.optind = number(value) ?: 1;
        shellparam.optoff = -1;
}
#endif

/*
 * Compares two strings up to the first = or '\0'.  The first
 * string must be terminated by '='; the second may be terminated by
 * either '=' or '\0'.
 */
static int
varcmp(const char *p, const char *q)
{
        int c, d;

        while ((c = *p) == (d = *q)) {
                if (c == '\0' || c == '=')
                        goto out;
                p++;
                q++;
        }
        if (c == '=')
                c = '\0';
        if (d == '=')
                d = '\0';
 out:
        return c - d;
}

/*
 * Find the appropriate entry in the hash table from the name.
 */
static struct var **
hashvar(const char *p)
{
        unsigned hashval;

        hashval = ((unsigned char) *p) << 4;
        while (*p && *p != '=')
                hashval += (unsigned char) *p++;
        return &vartab[hashval % VTABSIZE];
}

static int
vpcmp(const void *a, const void *b)
{
        return varcmp(*(const char **)a, *(const char **)b);
}

/*
 * This routine initializes the builtin variables.
 */
static void
initvar(void)
{
        struct var *vp;
        struct var *end;
        struct var **vpp;

        /*
         * PS1 depends on uid
         */
#if ENABLE_FEATURE_EDITING && ENABLE_FEATURE_EDITING_FANCY_PROMPT
        vps1.var_text = "PS1=\\w \\$ ";
#else
        if (!geteuid())
                vps1.var_text = "PS1=# ";
#endif
        vp = varinit;
        end = vp + ARRAY_SIZE(varinit);
        do {
                vpp = hashvar(vp->var_text);
                vp->next = *vpp;
                *vpp = vp;
        } while (++vp < end);
}

static struct var **
findvar(struct var **vpp, const char *name)
{
        for (; *vpp; vpp = &(*vpp)->next) {
                if (varcmp((*vpp)->var_text, name) == 0) {
                        break;
                }
        }
        return vpp;
}

/*
 * Find the value of a variable.  Returns NULL if not set.
 */
static const char* FAST_FUNC
lookupvar(const char *name)
{
        struct var *v;

        v = *findvar(hashvar(name), name);
        if (v) {
#if ENABLE_ASH_RANDOM_SUPPORT || BASH_EPOCH_VARS
        /*
         * Dynamic variables are implemented roughly the same way they are
         * in bash. Namely, they're "special" so long as they aren't unset.
         * As soon as they're unset, they're no longer dynamic, and dynamic
         * lookup will no longer happen at that point. -- PFM.
         */
                if (v->flags & VDYNAMIC)
                        v->var_func(NULL);
#endif
                if (!(v->flags & VUNSET)) {
                        if (v == &vlineno && v->var_text == linenovar) {
                                fmtstr(linenovar+7, sizeof(linenovar)-7, "%d", lineno);
                        }
                        return var_end(v->var_text);
                }
        }
        return NULL;
}

#if ENABLE_UNICODE_SUPPORT
static void
reinit_unicode_for_ash(void)
{
        /* Unicode support should be activated even if LANG is set
         * _during_ shell execution, not only if it was set when
         * shell was started. Therefore, re-check LANG every time:
         */
        if (ENABLE_FEATURE_CHECK_UNICODE_IN_ENV
         || ENABLE_UNICODE_USING_LOCALE
        ) {
                const char *s = lookupvar("LC_ALL");
                if (!s) s = lookupvar("LC_CTYPE");
                if (!s) s = lookupvar("LANG");
                reinit_unicode(s);
        }
}
#else
# define reinit_unicode_for_ash() ((void)0)
#endif

/*
 * Search the environment of a builtin command.
 */
static ALWAYS_INLINE const char *
bltinlookup(const char *name)
{
        return lookupvar(name);
}

/*
 * Same as setvar except that the variable and value are passed in
 * the first argument as name=value.  Since the first argument will
 * be actually stored in the table, it should not be a string that
 * will go away.
 * Called with interrupts off.
 */
static struct var *
setvareq(char *s, int flags)
{
        struct var *vp, **vpp;

        vpp = hashvar(s);
        flags |= (VEXPORT & (((unsigned) (1 - aflag)) - 1));
        vpp = findvar(vpp, s);
        vp = *vpp;
        if (vp) {
                if ((vp->flags & (VREADONLY|VDYNAMIC)) == VREADONLY) {
                        const char *n;

                        if (flags & VNOSAVE)
                                free(s);
                        n = vp->var_text;
                        exitstatus = 1;
                        ash_msg_and_raise_error("%.*s: is read only", strchrnul(n, '=') - n, n);
                }

                if (flags & VNOSET)
                        goto out;

                if (vp->var_func && !(flags & VNOFUNC))
                        vp->var_func(var_end(s));

                if (!(vp->flags & (VTEXTFIXED|VSTACK)))
                        free((char*)vp->var_text);

                if (((flags & (VEXPORT|VREADONLY|VSTRFIXED|VUNSET)) | (vp->flags & VSTRFIXED)) == VUNSET) {
                        *vpp = vp->next;
                        free(vp);
 out_free:
                        if ((flags & (VTEXTFIXED|VSTACK|VNOSAVE)) == VNOSAVE)
                                free(s);
                        goto out;
                }

                flags |= vp->flags & ~(VTEXTFIXED|VSTACK|VNOSAVE|VUNSET);
#if ENABLE_ASH_RANDOM_SUPPORT || BASH_EPOCH_VARS
                if (flags & VUNSET)
                        flags &= ~VDYNAMIC;
#endif
        } else {
                /* variable s is not found */
                if (flags & VNOSET)
                        goto out;
                if ((flags & (VEXPORT|VREADONLY|VSTRFIXED|VUNSET)) == VUNSET)
                        goto out_free;
                vp = ckzalloc(sizeof(*vp));
                vp->next = *vpp;
                /*vp->func = NULL; - ckzalloc did it */
                *vpp = vp;
        }
        if (!(flags & (VTEXTFIXED|VSTACK|VNOSAVE)))
                s = ckstrdup(s);
        vp->var_text = s;
        vp->flags = flags;

 out:
        return vp;
}

/*
 * Set the value of a variable.  The flags argument is ored with the
 * flags of the variable.  If val is NULL, the variable is unset.
 */
static struct var *
setvar(const char *name, const char *val, int flags)
{
        const char *q;
        char *p;
        char *nameeq;
        size_t namelen;
        size_t vallen;
        struct var *vp;

        q = endofname(name);
        p = strchrnul(q, '=');
        namelen = p - name;
        if (!namelen || p != q)
                ash_msg_and_raise_error("%.*s: bad variable name", namelen, name);
        vallen = 0;
        if (val == NULL) {
                flags |= VUNSET;
        } else {
                vallen = strlen(val);
        }

        INT_OFF;
        nameeq = ckzalloc(namelen + vallen + 2);
        p = mempcpy(nameeq, name, namelen);
        if (val) {
                *p++ = '=';
                memcpy(p, val, vallen);
        }
        vp = setvareq(nameeq, flags | VNOSAVE);
        INT_ON;

        return vp;
}

static void FAST_FUNC
setvar0(const char *name, const char *val)
{
        setvar(name, val, 0);
}

/*
 * Unset the specified variable.
 */
static void
unsetvar(const char *s)
{
        setvar(s, NULL, 0);
}

/*
 * Process a linked list of variable assignments.
 */
static void
listsetvar(struct strlist *list_set_var, int flags)
{
        struct strlist *lp = list_set_var;

        if (!lp)
                return;
        INT_OFF;
        do {
                setvareq(lp->text, flags);
                lp = lp->next;
        } while (lp);
        INT_ON;
}

/*
 * Generate a list of variables satisfying the given conditions.
 */
#if !ENABLE_FEATURE_SH_NOFORK
# define listvars(on, off, lp, end) listvars(on, off, end)
#endif
static char **
listvars(int on, int off, struct strlist *lp, char ***end)
{
        struct var **vpp;
        struct var *vp;
        char **ep;
        int mask;

        STARTSTACKSTR(ep);
        vpp = vartab;
        mask = on | off;
        do {
                for (vp = *vpp; vp; vp = vp->next) {
                        if ((vp->flags & mask) == on) {
#if ENABLE_FEATURE_SH_NOFORK
                                /* If variable with the same name is both
                                 * exported and temporarily set for a command:
                                 *  export ZVAR=5
                                 *  ZVAR=6 printenv
                                 * then "ZVAR=6" will be both in vartab and
                                 * lp lists. Do not pass it twice to printenv.
                                 */
                                struct strlist *lp1 = lp;
                                while (lp1) {
                                        if (strcmp(lp1->text, vp->var_text) == 0)
                                                goto skip;
                                        lp1 = lp1->next;
                                }
#endif
                                if (ep == stackstrend())
                                        ep = growstackstr();
                                *ep++ = (char*)vp->var_text;
#if ENABLE_FEATURE_SH_NOFORK
 skip: ;
#endif
                        }
                }
        } while (++vpp < vartab + VTABSIZE);

#if ENABLE_FEATURE_SH_NOFORK
        while (lp) {
                if (ep == stackstrend())
                        ep = growstackstr();
                *ep++ = lp->text;
                lp = lp->next;
        }
#endif

        if (ep == stackstrend())
                ep = growstackstr();
        if (end)
                *end = ep;
        *ep++ = NULL;
        return grabstackstr(ep);
}


/* ============ Path search helper
 *
 * The variable path (passed by reference) should be set to the start
 * of the path before the first call; path_advance will update
 * this value as it proceeds.  Successive calls to path_advance will return
 * the possible path expansions in sequence.  If an option (indicated by
 * a percent sign) appears in the path entry then the global variable
 * pathopt will be set to point to it; otherwise pathopt will be set to
 * NULL.
 */
static const char *pathopt;     /* set by path_advance */

static char *
path_advance(const char **path, const char *name)
{
        const char *p;
        char *q;
        const char *start;
        size_t len;

        if (*path == NULL)
                return NULL;
        start = *path;
        for (p = start; *p && *p != ':' && *p != '%'; p++)
                continue;
        len = p - start + strlen(name) + 2;     /* "2" is for '/' and '\0' */
        while (stackblocksize() < len)
                growstackblock();
        q = stackblock();
        if (p != start) {
                q = mempcpy(q, start, p - start);
                *q++ = '/';
        }
        strcpy(q, name);
        pathopt = NULL;
        if (*p == '%') {
                pathopt = ++p;
                while (*p && *p != ':')
                        p++;
        }
        if (*p == ':')
                *path = p + 1;
        else
                *path = NULL;
        return stalloc(len);
}


/* ============ Prompt */

static smallint doprompt;                   /* if set, prompt the user */
static smallint needprompt;                 /* true if interactive and at start of line */

#if ENABLE_FEATURE_EDITING
static line_input_t *line_input_state;
static const char *cmdedit_prompt;
static void
putprompt(const char *s)
{
        if (ENABLE_ASH_EXPAND_PRMT) {
                free((char*)cmdedit_prompt);
                cmdedit_prompt = ckstrdup(s);
                return;
        }
        cmdedit_prompt = s;
}
#else
static void
putprompt(const char *s)
{
        out2str(s);
}
#endif

/* expandstr() needs parsing machinery, so it is far away ahead... */
static const char *expandstr(const char *ps, int syntax_type);
/* Values for syntax param */
#define BASESYNTAX 0    /* not in quotes */
#define DQSYNTAX   1    /* in double quotes */
#define SQSYNTAX   2    /* in single quotes */
#define ARISYNTAX  3    /* in arithmetic */
#if ENABLE_ASH_EXPAND_PRMT
# define PSSYNTAX  4    /* prompt. never passed to SIT() */
#endif
/* PSSYNTAX expansion is identical to DQSYNTAX, except keeping '\$' as '\$' */

/*
 * called by editline -- any expansions to the prompt should be added here.
 */
static void
setprompt_if(smallint do_set, int whichprompt)
{
        const char *prompt;
        IF_ASH_EXPAND_PRMT(struct stackmark smark;)

        if (!do_set)
                return;

        needprompt = 0;

        switch (whichprompt) {
        case 1:
                prompt = ps1val();
                break;
        case 2:
                prompt = ps2val();
                break;
        default:                        /* 0 */
                prompt = nullstr;
        }
#if ENABLE_ASH_EXPAND_PRMT
        pushstackmark(&smark, stackblocksize());
        putprompt(expandstr(prompt, PSSYNTAX));
        popstackmark(&smark);
#else
        putprompt(prompt);
#endif
}


/* ============ The cd and pwd commands */

#define CD_PHYSICAL 1
#define CD_PRINT 2

static int
cdopt(void)
{
        int flags = 0;
        int i, j;

        j = 'L';
        while ((i = nextopt("LP")) != '\0') {
                if (i != j) {
                        flags ^= CD_PHYSICAL;
                        j = i;
                }
        }

        return flags;
}

/*
 * Update curdir (the name of the current directory) in response to a
 * cd command.
 */
static const char *
updatepwd(const char *dir)
{
        char *new;
        char *p;
        char *cdcomppath;
        const char *lim;

        cdcomppath = sstrdup(dir);
        STARTSTACKSTR(new);
        if (*dir != '/') {
                if (curdir == nullstr)
                        return 0;
                new = stack_putstr(curdir, new);
        }
        new = makestrspace(strlen(dir) + 2, new);
        lim = (char *)stackblock() + 1;
        if (*dir != '/') {
                if (new[-1] != '/')
                        USTPUTC('/', new);
                if (new > lim && *lim == '/')
                        lim++;
        } else {
                USTPUTC('/', new);
                cdcomppath++;
                if (dir[1] == '/' && dir[2] != '/') {
                        USTPUTC('/', new);
                        cdcomppath++;
                        lim++;
                }
        }
        p = strtok(cdcomppath, "/");
        while (p) {
                switch (*p) {
                case '.':
                        if (p[1] == '.' && p[2] == '\0') {
                                while (new > lim) {
                                        STUNPUTC(new);
                                        if (new[-1] == '/')
                                                break;
                                }
                                break;
                        }
                        if (p[1] == '\0')
                                break;
                        /* fall through */
                default:
                        new = stack_putstr(p, new);
                        USTPUTC('/', new);
                }
                p = strtok(NULL, "/");
        }
        if (new > lim)
                STUNPUTC(new);
        *new = 0;
        return stackblock();
}

/*
 * Find out what the current directory is. If we already know the current
 * directory, this routine returns immediately.
 */
static char *
getpwd(void)
{
        char *dir = getcwd(NULL, 0); /* huh, using glibc extension? */
        return dir ? dir : nullstr;
}

static void
setpwd(const char *val, int setold)
{
        char *oldcur, *dir;

        oldcur = dir = curdir;

        if (setold) {
                setvar("OLDPWD", oldcur, VEXPORT);
        }
        INT_OFF;
        if (physdir != nullstr) {
                if (physdir != oldcur)
                        free(physdir);
                physdir = nullstr;
        }
        if (oldcur == val || !val) {
                char *s = getpwd();
                physdir = s;
                if (!val)
                        dir = s;
        } else
                dir = ckstrdup(val);
        if (oldcur != dir && oldcur != nullstr) {
                free(oldcur);
        }
        curdir = dir;
        INT_ON;
        setvar("PWD", dir, VEXPORT);
}

static void hashcd(void);

/*
 * Actually do the chdir.  We also call hashcd to let other routines
 * know that the current directory has changed.
 */
static int
docd(const char *dest, int flags)
{
        const char *dir = NULL;
        int err;

        TRACE(("docd(\"%s\", %d) called\n", dest, flags));

        INT_OFF;
        if (!(flags & CD_PHYSICAL)) {
                dir = updatepwd(dest);
                if (dir)
                        dest = dir;
        }
        err = chdir(dest);
        if (err)
                goto out;
        setpwd(dir, 1);
        hashcd();
 out:
        INT_ON;
        return err;
}

static int FAST_FUNC
cdcmd(int argc UNUSED_PARAM, char **argv UNUSED_PARAM)
{
        const char *dest;
        const char *path;
        const char *p;
        char c;
        struct stat statb;
        int flags;

        flags = cdopt();
        dest = *argptr;
        if (!dest)
                dest = bltinlookup("HOME");
        else if (LONE_DASH(dest)) {
                dest = bltinlookup("OLDPWD");
                flags |= CD_PRINT;
        }
        if (!dest)
                dest = nullstr;
        if (*dest == '/')
                goto step6;
        if (*dest == '.') {
                c = dest[1];
 dotdot:
                switch (c) {
                case '\0':
                case '/':
                        goto step6;
                case '.':
                        c = dest[2];
                        if (c != '.')
                                goto dotdot;
                }
        }
        if (!*dest)
                dest = ".";
        path = bltinlookup("CDPATH");
        while (path) {
                c = *path;
                p = path_advance(&path, dest);
                if (stat(p, &statb) >= 0 && S_ISDIR(statb.st_mode)) {
                        if (c && c != ':')
                                flags |= CD_PRINT;
 docd:
                        if (!docd(p, flags))
                                goto out;
                        goto err;
                }
        }

 step6:
        p = dest;
        goto docd;

 err:
        ash_msg_and_raise_perror("can't cd to %s", dest);
        /* NOTREACHED */
 out:
        if (flags & CD_PRINT)
                out1fmt("%s\n", curdir);
        return 0;
}

static int FAST_FUNC
pwdcmd(int argc UNUSED_PARAM, char **argv UNUSED_PARAM)
{
        int flags;
        const char *dir = curdir;

        flags = cdopt();
        if (flags) {
                if (physdir == nullstr)
                        setpwd(dir, 0);
                dir = physdir;
        }
        out1fmt("%s\n", dir);
        return 0;
}


/* ============ ... */


#define IBUFSIZ (ENABLE_FEATURE_EDITING ? CONFIG_FEATURE_EDITING_MAX_LEN : 1024)

/* Syntax classes */
#define CWORD     0             /* character is nothing special */
#define CNL       1             /* newline character */
#define CBACK     2             /* a backslash character */
#define CSQUOTE   3             /* single quote */
#define CDQUOTE   4             /* double quote */
#define CENDQUOTE 5             /* a terminating quote */
#define CBQUOTE   6             /* backwards single quote */
#define CVAR      7             /* a dollar sign */
#define CENDVAR   8             /* a '}' character */
#define CLP       9             /* a left paren in arithmetic */
#define CRP      10             /* a right paren in arithmetic */
#define CENDFILE 11             /* end of file */
#define CCTL     12             /* like CWORD, except it must be escaped */
#define CSPCL    13             /* these terminate a word */
#define CIGN     14             /* character should be ignored */

#define PEOF     256
#if ENABLE_ASH_ALIAS
# define PEOA    257
#endif

#define USE_SIT_FUNCTION ENABLE_ASH_OPTIMIZE_FOR_SIZE

#if ENABLE_FEATURE_SH_MATH
# define SIT_ITEM(a,b,c,d) (a | (b << 4) | (c << 8) | (d << 12))
#else
# define SIT_ITEM(a,b,c,d) (a | (b << 4) | (c << 8))
#endif
static const uint16_t S_I_T[] ALIGN2 = {
#if ENABLE_ASH_ALIAS
        SIT_ITEM(CSPCL   , CIGN     , CIGN , CIGN   ),    /* 0, PEOA */
#endif
        SIT_ITEM(CSPCL   , CWORD    , CWORD, CWORD  ),    /* 1, ' ' */
        SIT_ITEM(CNL     , CNL      , CNL  , CNL    ),    /* 2, \n */
        SIT_ITEM(CWORD   , CCTL     , CCTL , CWORD  ),    /* 3, !*-/:=?[]~ */
        SIT_ITEM(CDQUOTE , CENDQUOTE, CWORD, CWORD  ),    /* 4, '"' */
        SIT_ITEM(CVAR    , CVAR     , CWORD, CVAR   ),    /* 5, $ */
        SIT_ITEM(CSQUOTE , CWORD    , CENDQUOTE, CWORD),  /* 6, "'" */
        SIT_ITEM(CSPCL   , CWORD    , CWORD, CLP    ),    /* 7, ( */
        SIT_ITEM(CSPCL   , CWORD    , CWORD, CRP    ),    /* 8, ) */
        SIT_ITEM(CBACK   , CBACK    , CCTL , CBACK  ),    /* 9, \ */
        SIT_ITEM(CBQUOTE , CBQUOTE  , CWORD, CBQUOTE),    /* 10, ` */
        SIT_ITEM(CENDVAR , CENDVAR  , CWORD, CENDVAR),    /* 11, } */
#if !USE_SIT_FUNCTION
        SIT_ITEM(CENDFILE, CENDFILE , CENDFILE, CENDFILE),/* 12, PEOF */
        SIT_ITEM(CWORD   , CWORD    , CWORD, CWORD  ),    /* 13, 0-9A-Za-z */
        SIT_ITEM(CCTL    , CCTL     , CCTL , CCTL   )     /* 14, CTLESC ... */
#endif
#undef SIT_ITEM
};
/* Constants below must match table above */
enum {
#if ENABLE_ASH_ALIAS
        CSPCL_CIGN_CIGN_CIGN               , /*  0 */
#endif
        CSPCL_CWORD_CWORD_CWORD            , /*  1 */
        CNL_CNL_CNL_CNL                    , /*  2 */
        CWORD_CCTL_CCTL_CWORD              , /*  3 */
        CDQUOTE_CENDQUOTE_CWORD_CWORD      , /*  4 */
        CVAR_CVAR_CWORD_CVAR               , /*  5 */
        CSQUOTE_CWORD_CENDQUOTE_CWORD      , /*  6 */
        CSPCL_CWORD_CWORD_CLP              , /*  7 */
        CSPCL_CWORD_CWORD_CRP              , /*  8 */
        CBACK_CBACK_CCTL_CBACK             , /*  9 */
        CBQUOTE_CBQUOTE_CWORD_CBQUOTE      , /* 10 */
        CENDVAR_CENDVAR_CWORD_CENDVAR      , /* 11 */
        CENDFILE_CENDFILE_CENDFILE_CENDFILE, /* 12 */
        CWORD_CWORD_CWORD_CWORD            , /* 13 */
        CCTL_CCTL_CCTL_CCTL                , /* 14 */
};

/* c in SIT(c, syntax) must be an *unsigned char* or PEOA or PEOF,
 * caller must ensure proper cast on it if c is *char_ptr!
 */
#if USE_SIT_FUNCTION

static int
SIT(int c, int syntax)
{
        /* Used to also have '/' in this string: "\t\n !\"$&'()*-/:;<=>?[\\]`|}~" */

        static const char spec_symbls[] ALIGN1 = "\t\n !\"$&'()*-:;<=>?[\\]`|}~";
        /*
         * This causes '/' to be prepended with CTLESC in dquoted string,
         * making "./file"* treated incorrectly because we feed
         * ".\/file*" string to glob(), confusing it (see expandmeta func).
         * The "homegrown" glob implementation is okay with that,
         * but glibc one isn't. With '/' always treated as CWORD,
         * both work fine.
         */
# if ENABLE_ASH_ALIAS
        static const uint8_t syntax_index_table[] ALIGN1 = {
                1, 2, 1, 3, 4, 5, 1, 6,         /* "\t\n !\"$&'" */
                7, 8, 3, 3,/*3,*/3, 1, 1,       /* "()*-/:;<" */
                3, 1, 3, 3, 9, 3, 10, 1,        /* "=>?[\\]`|" */
                11, 3                           /* "}~" */
        };
# else
        static const uint8_t syntax_index_table[] ALIGN1 = {
                0, 1, 0, 2, 3, 4, 0, 5,         /* "\t\n !\"$&'" */
                6, 7, 2, 2,/*2,*/2, 0, 0,       /* "()*-/:;<" */
                2, 0, 2, 2, 8, 2, 9, 0,         /* "=>?[\\]`|" */
                10, 2                           /* "}~" */
        };
# endif
        const char *s;
        int indx;

        if (c == PEOF)
                return CENDFILE;
# if ENABLE_ASH_ALIAS
        if (c == PEOA)
                indx = 0;
        else
# endif
        {
                /* Cast is purely for paranoia here,
                 * just in case someone passed signed char to us */
                if ((unsigned char)c >= CTL_FIRST
                 && (unsigned char)c <= CTL_LAST
                ) {
                        return CCTL;
                }
                s = strchrnul(spec_symbls, c);
                if (*s == '\0')
                        return CWORD;
                indx = syntax_index_table[s - spec_symbls];
        }
        return (S_I_T[indx] >> (syntax*4)) & 0xf;
}

#else   /* !USE_SIT_FUNCTION */

static const uint8_t syntax_index_table[] ALIGN1 = {
        /* BASESYNTAX_DQSYNTAX_SQSYNTAX_ARISYNTAX */
        /*   0      */ CWORD_CWORD_CWORD_CWORD,
        /*   1      */ CWORD_CWORD_CWORD_CWORD,
        /*   2      */ CWORD_CWORD_CWORD_CWORD,
        /*   3      */ CWORD_CWORD_CWORD_CWORD,
        /*   4      */ CWORD_CWORD_CWORD_CWORD,
        /*   5      */ CWORD_CWORD_CWORD_CWORD,
        /*   6      */ CWORD_CWORD_CWORD_CWORD,
        /*   7      */ CWORD_CWORD_CWORD_CWORD,
        /*   8      */ CWORD_CWORD_CWORD_CWORD,
        /*   9 "\t" */ CSPCL_CWORD_CWORD_CWORD,
        /*  10 "\n" */ CNL_CNL_CNL_CNL,
        /*  11      */ CWORD_CWORD_CWORD_CWORD,
        /*  12      */ CWORD_CWORD_CWORD_CWORD,
        /*  13      */ CWORD_CWORD_CWORD_CWORD,
        /*  14      */ CWORD_CWORD_CWORD_CWORD,
        /*  15      */ CWORD_CWORD_CWORD_CWORD,
        /*  16      */ CWORD_CWORD_CWORD_CWORD,
        /*  17      */ CWORD_CWORD_CWORD_CWORD,
        /*  18      */ CWORD_CWORD_CWORD_CWORD,
        /*  19      */ CWORD_CWORD_CWORD_CWORD,
        /*  20      */ CWORD_CWORD_CWORD_CWORD,
        /*  21      */ CWORD_CWORD_CWORD_CWORD,
        /*  22      */ CWORD_CWORD_CWORD_CWORD,
        /*  23      */ CWORD_CWORD_CWORD_CWORD,
        /*  24      */ CWORD_CWORD_CWORD_CWORD,
        /*  25      */ CWORD_CWORD_CWORD_CWORD,
        /*  26      */ CWORD_CWORD_CWORD_CWORD,
        /*  27      */ CWORD_CWORD_CWORD_CWORD,
        /*  28      */ CWORD_CWORD_CWORD_CWORD,
        /*  29      */ CWORD_CWORD_CWORD_CWORD,
        /*  30      */ CWORD_CWORD_CWORD_CWORD,
        /*  31      */ CWORD_CWORD_CWORD_CWORD,
        /*  32  " " */ CSPCL_CWORD_CWORD_CWORD,
        /*  33  "!" */ CWORD_CCTL_CCTL_CWORD,
        /*  34  """ */ CDQUOTE_CENDQUOTE_CWORD_CWORD,
        /*  35  "#" */ CWORD_CWORD_CWORD_CWORD,
        /*  36  "$" */ CVAR_CVAR_CWORD_CVAR,
        /*  37  "%" */ CWORD_CWORD_CWORD_CWORD,
        /*  38  "&" */ CSPCL_CWORD_CWORD_CWORD,
        /*  39  "'" */ CSQUOTE_CWORD_CENDQUOTE_CWORD,
        /*  40  "(" */ CSPCL_CWORD_CWORD_CLP,
        /*  41  ")" */ CSPCL_CWORD_CWORD_CRP,
        /*  42  "*" */ CWORD_CCTL_CCTL_CWORD,
        /*  43  "+" */ CWORD_CWORD_CWORD_CWORD,
        /*  44  "," */ CWORD_CWORD_CWORD_CWORD,
        /*  45  "-" */ CWORD_CCTL_CCTL_CWORD,
        /*  46  "." */ CWORD_CWORD_CWORD_CWORD,
/* "/" was CWORD_CCTL_CCTL_CWORD, see comment in SIT() function why this is changed: */
        /*  47  "/" */ CWORD_CWORD_CWORD_CWORD,
        /*  48  "0" */ CWORD_CWORD_CWORD_CWORD,
        /*  49  "1" */ CWORD_CWORD_CWORD_CWORD,
        /*  50  "2" */ CWORD_CWORD_CWORD_CWORD,
        /*  51  "3" */ CWORD_CWORD_CWORD_CWORD,
        /*  52  "4" */ CWORD_CWORD_CWORD_CWORD,
        /*  53  "5" */ CWORD_CWORD_CWORD_CWORD,
        /*  54  "6" */ CWORD_CWORD_CWORD_CWORD,
        /*  55  "7" */ CWORD_CWORD_CWORD_CWORD,
        /*  56  "8" */ CWORD_CWORD_CWORD_CWORD,
        /*  57  "9" */ CWORD_CWORD_CWORD_CWORD,
        /*  58  ":" */ CWORD_CCTL_CCTL_CWORD,
        /*  59  ";" */ CSPCL_CWORD_CWORD_CWORD,
        /*  60  "<" */ CSPCL_CWORD_CWORD_CWORD,
        /*  61  "=" */ CWORD_CCTL_CCTL_CWORD,
        /*  62  ">" */ CSPCL_CWORD_CWORD_CWORD,
        /*  63  "?" */ CWORD_CCTL_CCTL_CWORD,
        /*  64  "@" */ CWORD_CWORD_CWORD_CWORD,
        /*  65  "A" */ CWORD_CWORD_CWORD_CWORD,
        /*  66  "B" */ CWORD_CWORD_CWORD_CWORD,
        /*  67  "C" */ CWORD_CWORD_CWORD_CWORD,
        /*  68  "D" */ CWORD_CWORD_CWORD_CWORD,
        /*  69  "E" */ CWORD_CWORD_CWORD_CWORD,
        /*  70  "F" */ CWORD_CWORD_CWORD_CWORD,
        /*  71  "G" */ CWORD_CWORD_CWORD_CWORD,
        /*  72  "H" */ CWORD_CWORD_CWORD_CWORD,
        /*  73  "I" */ CWORD_CWORD_CWORD_CWORD,
        /*  74  "J" */ CWORD_CWORD_CWORD_CWORD,
        /*  75  "K" */ CWORD_CWORD_CWORD_CWORD,
        /*  76  "L" */ CWORD_CWORD_CWORD_CWORD,
        /*  77  "M" */ CWORD_CWORD_CWORD_CWORD,
        /*  78  "N" */ CWORD_CWORD_CWORD_CWORD,
        /*  79  "O" */ CWORD_CWORD_CWORD_CWORD,
        /*  80  "P" */ CWORD_CWORD_CWORD_CWORD,
        /*  81  "Q" */ CWORD_CWORD_CWORD_CWORD,
        /*  82  "R" */ CWORD_CWORD_CWORD_CWORD,
        /*  83  "S" */ CWORD_CWORD_CWORD_CWORD,
        /*  84  "T" */ CWORD_CWORD_CWORD_CWORD,
        /*  85  "U" */ CWORD_CWORD_CWORD_CWORD,
        /*  86  "V" */ CWORD_CWORD_CWORD_CWORD,
        /*  87  "W" */ CWORD_CWORD_CWORD_CWORD,
        /*  88  "X" */ CWORD_CWORD_CWORD_CWORD,
        /*  89  "Y" */ CWORD_CWORD_CWORD_CWORD,
        /*  90  "Z" */ CWORD_CWORD_CWORD_CWORD,
        /*  91  "[" */ CWORD_CCTL_CCTL_CWORD,
        /*  92  "\" */ CBACK_CBACK_CCTL_CBACK,
        /*  93  "]" */ CWORD_CCTL_CCTL_CWORD,
        /*  94  "^" */ CWORD_CWORD_CWORD_CWORD,
        /*  95  "_" */ CWORD_CWORD_CWORD_CWORD,
        /*  96  "`" */ CBQUOTE_CBQUOTE_CWORD_CBQUOTE,
        /*  97  "a" */ CWORD_CWORD_CWORD_CWORD,
        /*  98  "b" */ CWORD_CWORD_CWORD_CWORD,
        /*  99  "c" */ CWORD_CWORD_CWORD_CWORD,
        /* 100  "d" */ CWORD_CWORD_CWORD_CWORD,
        /* 101  "e" */ CWORD_CWORD_CWORD_CWORD,
        /* 102  "f" */ CWORD_CWORD_CWORD_CWORD,
        /* 103  "g" */ CWORD_CWORD_CWORD_CWORD,
        /* 104  "h" */ CWORD_CWORD_CWORD_CWORD,
        /* 105  "i" */ CWORD_CWORD_CWORD_CWORD,
        /* 106  "j" */ CWORD_CWORD_CWORD_CWORD,
        /* 107  "k" */ CWORD_CWORD_CWORD_CWORD,
        /* 108  "l" */ CWORD_CWORD_CWORD_CWORD,
        /* 109  "m" */ CWORD_CWORD_CWORD_CWORD,
        /* 110  "n" */ CWORD_CWORD_CWORD_CWORD,
        /* 111  "o" */ CWORD_CWORD_CWORD_CWORD,
        /* 112  "p" */ CWORD_CWORD_CWORD_CWORD,
        /* 113  "q" */ CWORD_CWORD_CWORD_CWORD,
        /* 114  "r" */ CWORD_CWORD_CWORD_CWORD,
        /* 115  "s" */ CWORD_CWORD_CWORD_CWORD,
        /* 116  "t" */ CWORD_CWORD_CWORD_CWORD,
        /* 117  "u" */ CWORD_CWORD_CWORD_CWORD,
        /* 118  "v" */ CWORD_CWORD_CWORD_CWORD,
        /* 119  "w" */ CWORD_CWORD_CWORD_CWORD,
        /* 120  "x" */ CWORD_CWORD_CWORD_CWORD,
        /* 121  "y" */ CWORD_CWORD_CWORD_CWORD,
        /* 122  "z" */ CWORD_CWORD_CWORD_CWORD,
        /* 123  "{" */ CWORD_CWORD_CWORD_CWORD,
        /* 124  "|" */ CSPCL_CWORD_CWORD_CWORD,
        /* 125  "}" */ CENDVAR_CENDVAR_CWORD_CENDVAR,
        /* 126  "~" */ CWORD_CCTL_CCTL_CWORD,
        /* 127  del */ CWORD_CWORD_CWORD_CWORD,
        /* 128 0x80 */ CWORD_CWORD_CWORD_CWORD,
        /* 129 CTLESC       */ CCTL_CCTL_CCTL_CCTL,
        /* 130 CTLVAR       */ CCTL_CCTL_CCTL_CCTL,
        /* 131 CTLENDVAR    */ CCTL_CCTL_CCTL_CCTL,
        /* 132 CTLBACKQ     */ CCTL_CCTL_CCTL_CCTL,
        /* 133 CTLQUOTE     */ CCTL_CCTL_CCTL_CCTL,
        /* 134 CTLARI       */ CCTL_CCTL_CCTL_CCTL,
        /* 135 CTLENDARI    */ CCTL_CCTL_CCTL_CCTL,
        /* 136 CTLQUOTEMARK */ CCTL_CCTL_CCTL_CCTL,
        /* 137      */ CWORD_CWORD_CWORD_CWORD,
        /* 138      */ CWORD_CWORD_CWORD_CWORD,
        /* 139      */ CWORD_CWORD_CWORD_CWORD,
        /* 140      */ CWORD_CWORD_CWORD_CWORD,
        /* 141      */ CWORD_CWORD_CWORD_CWORD,
        /* 142      */ CWORD_CWORD_CWORD_CWORD,
        /* 143      */ CWORD_CWORD_CWORD_CWORD,
        /* 144      */ CWORD_CWORD_CWORD_CWORD,
        /* 145      */ CWORD_CWORD_CWORD_CWORD,
        /* 146      */ CWORD_CWORD_CWORD_CWORD,
        /* 147      */ CWORD_CWORD_CWORD_CWORD,
        /* 148      */ CWORD_CWORD_CWORD_CWORD,
        /* 149      */ CWORD_CWORD_CWORD_CWORD,
        /* 150      */ CWORD_CWORD_CWORD_CWORD,
        /* 151      */ CWORD_CWORD_CWORD_CWORD,
        /* 152      */ CWORD_CWORD_CWORD_CWORD,
        /* 153      */ CWORD_CWORD_CWORD_CWORD,
        /* 154      */ CWORD_CWORD_CWORD_CWORD,
        /* 155      */ CWORD_CWORD_CWORD_CWORD,
        /* 156      */ CWORD_CWORD_CWORD_CWORD,
        /* 157      */ CWORD_CWORD_CWORD_CWORD,
        /* 158      */ CWORD_CWORD_CWORD_CWORD,
        /* 159      */ CWORD_CWORD_CWORD_CWORD,
        /* 160      */ CWORD_CWORD_CWORD_CWORD,
        /* 161      */ CWORD_CWORD_CWORD_CWORD,
        /* 162      */ CWORD_CWORD_CWORD_CWORD,
        /* 163      */ CWORD_CWORD_CWORD_CWORD,
        /* 164      */ CWORD_CWORD_CWORD_CWORD,
        /* 165      */ CWORD_CWORD_CWORD_CWORD,
        /* 166      */ CWORD_CWORD_CWORD_CWORD,
        /* 167      */ CWORD_CWORD_CWORD_CWORD,
        /* 168      */ CWORD_CWORD_CWORD_CWORD,
        /* 169      */ CWORD_CWORD_CWORD_CWORD,
        /* 170      */ CWORD_CWORD_CWORD_CWORD,
        /* 171      */ CWORD_CWORD_CWORD_CWORD,
        /* 172      */ CWORD_CWORD_CWORD_CWORD,
        /* 173      */ CWORD_CWORD_CWORD_CWORD,
        /* 174      */ CWORD_CWORD_CWORD_CWORD,
        /* 175      */ CWORD_CWORD_CWORD_CWORD,
        /* 176      */ CWORD_CWORD_CWORD_CWORD,
        /* 177      */ CWORD_CWORD_CWORD_CWORD,
        /* 178      */ CWORD_CWORD_CWORD_CWORD,
        /* 179      */ CWORD_CWORD_CWORD_CWORD,
        /* 180      */ CWORD_CWORD_CWORD_CWORD,
        /* 181      */ CWORD_CWORD_CWORD_CWORD,
        /* 182      */ CWORD_CWORD_CWORD_CWORD,
        /* 183      */ CWORD_CWORD_CWORD_CWORD,
        /* 184      */ CWORD_CWORD_CWORD_CWORD,
        /* 185      */ CWORD_CWORD_CWORD_CWORD,
        /* 186      */ CWORD_CWORD_CWORD_CWORD,
        /* 187      */ CWORD_CWORD_CWORD_CWORD,
        /* 188      */ CWORD_CWORD_CWORD_CWORD,
        /* 189      */ CWORD_CWORD_CWORD_CWORD,
        /* 190      */ CWORD_CWORD_CWORD_CWORD,
        /* 191      */ CWORD_CWORD_CWORD_CWORD,
        /* 192      */ CWORD_CWORD_CWORD_CWORD,
        /* 193      */ CWORD_CWORD_CWORD_CWORD,
        /* 194      */ CWORD_CWORD_CWORD_CWORD,
        /* 195      */ CWORD_CWORD_CWORD_CWORD,
        /* 196      */ CWORD_CWORD_CWORD_CWORD,
        /* 197      */ CWORD_CWORD_CWORD_CWORD,
        /* 198      */ CWORD_CWORD_CWORD_CWORD,
        /* 199      */ CWORD_CWORD_CWORD_CWORD,
        /* 200      */ CWORD_CWORD_CWORD_CWORD,
        /* 201      */ CWORD_CWORD_CWORD_CWORD,
        /* 202      */ CWORD_CWORD_CWORD_CWORD,
        /* 203      */ CWORD_CWORD_CWORD_CWORD,
        /* 204      */ CWORD_CWORD_CWORD_CWORD,
        /* 205      */ CWORD_CWORD_CWORD_CWORD,
        /* 206      */ CWORD_CWORD_CWORD_CWORD,
        /* 207      */ CWORD_CWORD_CWORD_CWORD,
        /* 208      */ CWORD_CWORD_CWORD_CWORD,
        /* 209      */ CWORD_CWORD_CWORD_CWORD,
        /* 210      */ CWORD_CWORD_CWORD_CWORD,
        /* 211      */ CWORD_CWORD_CWORD_CWORD,
        /* 212      */ CWORD_CWORD_CWORD_CWORD,
        /* 213      */ CWORD_CWORD_CWORD_CWORD,
        /* 214      */ CWORD_CWORD_CWORD_CWORD,
        /* 215      */ CWORD_CWORD_CWORD_CWORD,
        /* 216      */ CWORD_CWORD_CWORD_CWORD,
        /* 217      */ CWORD_CWORD_CWORD_CWORD,
        /* 218      */ CWORD_CWORD_CWORD_CWORD,
        /* 219      */ CWORD_CWORD_CWORD_CWORD,
        /* 220      */ CWORD_CWORD_CWORD_CWORD,
        /* 221      */ CWORD_CWORD_CWORD_CWORD,
        /* 222      */ CWORD_CWORD_CWORD_CWORD,
        /* 223      */ CWORD_CWORD_CWORD_CWORD,
        /* 224      */ CWORD_CWORD_CWORD_CWORD,
        /* 225      */ CWORD_CWORD_CWORD_CWORD,
        /* 226      */ CWORD_CWORD_CWORD_CWORD,
        /* 227      */ CWORD_CWORD_CWORD_CWORD,
        /* 228      */ CWORD_CWORD_CWORD_CWORD,
        /* 229      */ CWORD_CWORD_CWORD_CWORD,
        /* 230      */ CWORD_CWORD_CWORD_CWORD,
        /* 231      */ CWORD_CWORD_CWORD_CWORD,
        /* 232      */ CWORD_CWORD_CWORD_CWORD,
        /* 233      */ CWORD_CWORD_CWORD_CWORD,
        /* 234      */ CWORD_CWORD_CWORD_CWORD,
        /* 235      */ CWORD_CWORD_CWORD_CWORD,
        /* 236      */ CWORD_CWORD_CWORD_CWORD,
        /* 237      */ CWORD_CWORD_CWORD_CWORD,
        /* 238      */ CWORD_CWORD_CWORD_CWORD,
        /* 239      */ CWORD_CWORD_CWORD_CWORD,
        /* 230      */ CWORD_CWORD_CWORD_CWORD,
        /* 241      */ CWORD_CWORD_CWORD_CWORD,
        /* 242      */ CWORD_CWORD_CWORD_CWORD,
        /* 243      */ CWORD_CWORD_CWORD_CWORD,
        /* 244      */ CWORD_CWORD_CWORD_CWORD,
        /* 245      */ CWORD_CWORD_CWORD_CWORD,
        /* 246      */ CWORD_CWORD_CWORD_CWORD,
        /* 247      */ CWORD_CWORD_CWORD_CWORD,
        /* 248      */ CWORD_CWORD_CWORD_CWORD,
        /* 249      */ CWORD_CWORD_CWORD_CWORD,
        /* 250      */ CWORD_CWORD_CWORD_CWORD,
        /* 251      */ CWORD_CWORD_CWORD_CWORD,
        /* 252      */ CWORD_CWORD_CWORD_CWORD,
        /* 253      */ CWORD_CWORD_CWORD_CWORD,
        /* 254      */ CWORD_CWORD_CWORD_CWORD,
        /* 255      */ CWORD_CWORD_CWORD_CWORD,
        /* PEOF */     CENDFILE_CENDFILE_CENDFILE_CENDFILE,
# if ENABLE_ASH_ALIAS
        /* PEOA */     CSPCL_CIGN_CIGN_CIGN,
# endif
};

#if 1
# define SIT(c, syntax) ((S_I_T[syntax_index_table[c]] >> ((syntax)*4)) & 0xf)
#else /* debug version, caught one signed char bug */
# define SIT(c, syntax) \
        ({ \
                if ((c) < 0 || (c) > (PEOF + ENABLE_ASH_ALIAS)) \
                        bb_error_msg_and_die("line:%d c:%d", __LINE__, (c)); \
                if ((syntax) < 0 || (syntax) > (2 + ENABLE_FEATURE_SH_MATH)) \
                        bb_error_msg_and_die("line:%d c:%d", __LINE__, (c)); \
                ((S_I_T[syntax_index_table[c]] >> ((syntax)*4)) & 0xf); \
        })
#endif

#endif  /* !USE_SIT_FUNCTION */


/* ============ Alias handling */

#if ENABLE_ASH_ALIAS

#define ALIASINUSE 1
#define ALIASDEAD  2

struct alias {
        struct alias *next;
        char *name;
        char *val;
        int flag;
};


static struct alias **atab; // [ATABSIZE];
#define INIT_G_alias() do { \
        atab = xzalloc(ATABSIZE * sizeof(atab[0])); \
} while (0)


static struct alias **
__lookupalias(const char *name)
{
        unsigned int hashval;
        struct alias **app;
        const char *p;
        unsigned int ch;

        p = name;

        ch = (unsigned char)*p;
        hashval = ch << 4;
        while (ch) {
                hashval += ch;
                ch = (unsigned char)*++p;
        }
        app = &atab[hashval % ATABSIZE];

        for (; *app; app = &(*app)->next) {
                if (strcmp(name, (*app)->name) == 0) {
                        break;
                }
        }

        return app;
}

static struct alias *
lookupalias(const char *name, int check)
{
        struct alias *ap = *__lookupalias(name);

        if (check && ap && (ap->flag & ALIASINUSE))
                return NULL;
        return ap;
}

static struct alias *
freealias(struct alias *ap)
{
        struct alias *next;

        if (ap->flag & ALIASINUSE) {
                ap->flag |= ALIASDEAD;
                return ap;
        }

        next = ap->next;
        free(ap->name);
        free(ap->val);
        free(ap);
        return next;
}

static void
setalias(const char *name, const char *val)
{
        struct alias *ap, **app;

        app = __lookupalias(name);
        ap = *app;
        INT_OFF;
        if (ap) {
                if (!(ap->flag & ALIASINUSE)) {
                        free(ap->val);
                }
                ap->val = ckstrdup(val);
                ap->flag &= ~ALIASDEAD;
        } else {
                /* not found */
                ap = ckzalloc(sizeof(struct alias));
                ap->name = ckstrdup(name);
                ap->val = ckstrdup(val);
                /*ap->flag = 0; - ckzalloc did it */
                /*ap->next = NULL;*/
                *app = ap;
        }
        INT_ON;
}

static int
unalias(const char *name)
{
        struct alias **app;

        app = __lookupalias(name);

        if (*app) {
                INT_OFF;
                *app = freealias(*app);
                INT_ON;
                return 0;
        }

        return 1;
}

static void
rmaliases(void)
{
        struct alias *ap, **app;
        int i;

        INT_OFF;
        for (i = 0; i < ATABSIZE; i++) {
                app = &atab[i];
                for (ap = *app; ap; ap = *app) {
                        *app = freealias(*app);
                        if (ap == *app) {
                                app = &ap->next;
                        }
                }
        }
        INT_ON;
}

static void
printalias(const struct alias *ap)
{
        out1fmt("%s=%s\n", ap->name, single_quote(ap->val));
}

/*
 * TODO - sort output
 */
static int FAST_FUNC
aliascmd(int argc UNUSED_PARAM, char **argv)
{
        char *n, *v;
        int ret = 0;
        struct alias *ap;

        if (!argv[1]) {
                int i;

                for (i = 0; i < ATABSIZE; i++) {
                        for (ap = atab[i]; ap; ap = ap->next) {
                                printalias(ap);
                        }
                }
                return 0;
        }
        while ((n = *++argv) != NULL) {
                v = strchr(n+1, '=');
                if (v == NULL) { /* n+1: funny ksh stuff */
                        ap = *__lookupalias(n);
                        if (ap == NULL) {
                                fprintf(stderr, "%s: %s not found\n", "alias", n);
                                ret = 1;
                        } else
                                printalias(ap);
                } else {
                        *v++ = '\0';
                        setalias(n, v);
                }
        }

        return ret;
}

static int FAST_FUNC
unaliascmd(int argc UNUSED_PARAM, char **argv UNUSED_PARAM)
{
        int i;

        while (nextopt("a") != '\0') {
                rmaliases();
                return 0;
        }
        for (i = 0; *argptr; argptr++) {
                if (unalias(*argptr)) {
                        fprintf(stderr, "%s: %s not found\n", "unalias", *argptr);
                        i = 1;
                }
        }

        return i;
}

#endif /* ASH_ALIAS */


/* Mode argument to forkshell.  Don't change FORK_FG or FORK_BG. */
#define FORK_FG    0
#define FORK_BG    1
#define FORK_NOJOB 2

/* mode flags for showjob(s) */
#define SHOW_ONLY_PGID  0x01    /* show only pgid (jobs -p) */
#define SHOW_PIDS       0x02    /* show individual pids, not just one line per job */
#define SHOW_CHANGED    0x04    /* only jobs whose state has changed */
#define SHOW_STDERR     0x08    /* print to stderr (else stdout) */

/*
 * A job structure contains information about a job.  A job is either a
 * single process or a set of processes contained in a pipeline.  In the
 * latter case, pidlist will be non-NULL, and will point to a -1 terminated
 * array of pids.
 */
struct procstat {
        pid_t   ps_pid;         /* process id */
        int     ps_status;      /* last process status from wait() */
        char    *ps_cmd;        /* text of command being run */
};

struct job {
        struct procstat ps0;    /* status of process */
        struct procstat *ps;    /* status of processes when more than one */
#if JOBS
        int stopstatus;         /* status of a stopped job */
#endif
        unsigned nprocs;        /* number of processes */

#define JOBRUNNING      0       /* at least one proc running */
#define JOBSTOPPED      1       /* all procs are stopped */
#define JOBDONE         2       /* all procs are completed */
        unsigned
                state: 8,
#if JOBS
                sigint: 1,      /* job was killed by SIGINT */
                jobctl: 1,      /* job running under job control */
#endif
                waited: 1,      /* true if this entry has been waited for */
                used: 1,        /* true if this entry is in used */
                changed: 1;     /* true if status has changed */
        struct job *prev_job;   /* previous job */
};

static struct job *makejob(/*union node *,*/ int);
static int forkshell(struct job *, union node *, int);
static int waitforjob(struct job *);

#if !JOBS
enum { doing_jobctl = 0 };
#define setjobctl(on) do {} while (0)
#else
static smallint doing_jobctl; //references:8
static void setjobctl(int);
#endif

/*
 * Ignore a signal.
 */
static void
ignoresig(int signo)
{
        /* Avoid unnecessary system calls. Is it already SIG_IGNed? */
        if (sigmode[signo - 1] != S_IGN && sigmode[signo - 1] != S_HARD_IGN) {
                /* No, need to do it */
                signal(signo, SIG_IGN);
        }
        sigmode[signo - 1] = S_HARD_IGN;
}

/*
 * Only one usage site - in setsignal()
 */
static void
signal_handler(int signo)
{
        if (signo == SIGCHLD) {
                got_sigchld = 1;
                if (!trap[SIGCHLD])
                        return;
        }

        gotsig[signo - 1] = 1;
        pending_sig = signo;

        if (signo == SIGINT && !trap[SIGINT]) {
                if (!suppress_int) {
                        pending_sig = 0;
                        raise_interrupt(); /* does not return */
                }
                pending_int = 1;
        }
}

/*
 * Set the signal handler for the specified signal.  The routine figures
 * out what it should be set to.
 */
static void
setsignal(int signo)
{
        char *t;
        char cur_act, new_act;
        struct sigaction act;

        t = trap[signo];
        new_act = S_DFL;
        if (t != NULL) { /* trap for this sig is set */
                new_act = S_CATCH;
                if (t[0] == '\0') /* trap is "": ignore this sig */
                        new_act = S_IGN;
        }

        if (rootshell && new_act == S_DFL) {
                switch (signo) {
                case SIGINT:
                        if (iflag || minusc || sflag == 0)
                                new_act = S_CATCH;
                        break;
                case SIGQUIT:
#if DEBUG
                        if (debug)
                                break;
#endif
                        /* man bash:
                         * "In all cases, bash ignores SIGQUIT. Non-builtin
                         * commands run by bash have signal handlers
                         * set to the values inherited by the shell
                         * from its parent". */
                        new_act = S_IGN;
                        break;
                case SIGTERM:
                        if (iflag)
                                new_act = S_IGN;
                        break;
#if JOBS
                case SIGTSTP:
                case SIGTTOU:
                        if (mflag)
                                new_act = S_IGN;
                        break;
#endif
                }
        }
        /* if !rootshell, we reset SIGQUIT to DFL,
         * whereas we have to restore it to what shell got on entry.
         * This is handled by the fact that if signal was IGNored on entry,
         * then cur_act is S_HARD_IGN and we never change its sigaction
         * (see code below).
         */

        if (signo == SIGCHLD)
                new_act = S_CATCH;

        t = &sigmode[signo - 1];
        cur_act = *t;
        if (cur_act == 0) {
                /* current setting is not yet known */
                if (sigaction(signo, NULL, &act)) {
                        /* pretend it worked; maybe we should give a warning,
                         * but other shells don't. We don't alter sigmode,
                         * so we retry every time.
                         * btw, in Linux it never fails. --vda */
                        return;
                }
                if (act.sa_handler == SIG_IGN) {
                        cur_act = S_HARD_IGN;
                        if (mflag
                         && (signo == SIGTSTP || signo == SIGTTIN || signo == SIGTTOU)
                        ) {
                                cur_act = S_IGN;   /* don't hard ignore these */
                        }
                }
                if (act.sa_handler == SIG_DFL && new_act == S_DFL) {
                        /* installing SIG_DFL over SIG_DFL is a no-op */
                        /* saves one sigaction call in each "sh -c SCRIPT" invocation */
                        *t = S_DFL;
                        return;
                }
        }
        if (cur_act == S_HARD_IGN || cur_act == new_act)
                return;

        *t = new_act;

        act.sa_handler = SIG_DFL;
        switch (new_act) {
        case S_CATCH:
                act.sa_handler = signal_handler;
                break;
        case S_IGN:
                act.sa_handler = SIG_IGN;
                break;
        }
        /* flags and mask matter only if !DFL and !IGN, but we do it
         * for all cases for more deterministic behavior:
         */
        act.sa_flags = 0; //TODO: why not SA_RESTART?
        sigfillset(&act.sa_mask);

        sigaction_set(signo, &act);
}

/* mode flags for set_curjob */
#define CUR_DELETE 2
#define CUR_RUNNING 1
#define CUR_STOPPED 0

#if JOBS
/* pgrp of shell on invocation */
static int initialpgrp; //references:2
static int ttyfd = -1; //5
#endif
/* array of jobs */
static struct job *jobtab; //5
/* size of array */
static unsigned njobs; //4
/* current job */
static struct job *curjob; //lots
/* number of presumed living untracked jobs */
static int jobless; //4

#if 0
/* Bash has a feature: it restores termios after a successful wait for
 * a foreground job which had at least one stopped or sigkilled member.
 * The probable rationale is that SIGSTOP and SIGKILL can preclude task from
 * properly restoring tty state. Should we do this too?
 * A reproducer: ^Z an interactive python:
 *
 * # python
 * Python 2.7.12 (...)
 * >>> ^Z
 *      { python leaves tty in -icanon -echo state. We do survive that... }
 *  [1]+  Stopped                    python
 *      { ...however, next program (python #2) does not survive it well: }
 * # python
 * Python 2.7.12 (...)
 * >>> Traceback (most recent call last):
 *      { above, I typed "qwerty<CR>", but -echo state is still in effect }
 *   File "<stdin>", line 1, in <module>
 * NameError: name 'qwerty' is not defined
 *
 * The implementation below is modeled on bash code and seems to work.
 * However, I'm not sure we should do this. For one: what if I'd fg
 * the stopped python instead? It'll be confused by "restored" tty state.
 */
static struct termios shell_tty_info;
static void
get_tty_state(void)
{
        if (rootshell && ttyfd >= 0)
                tcgetattr(ttyfd, &shell_tty_info);
}
static void
set_tty_state(void)
{
        /* if (rootshell) - caller ensures this */
        if (ttyfd >= 0)
                tcsetattr(ttyfd, TCSADRAIN, &shell_tty_info);
}
static int
job_signal_status(struct job *jp)
{
        int status;
        unsigned i;
        struct procstat *ps = jp->ps;
        for (i = 0; i < jp->nprocs; i++) {
                status = ps[i].ps_status;
                if (WIFSIGNALED(status) || WIFSTOPPED(status))
                        return status;
        }
        return 0;
}
static void
restore_tty_if_stopped_or_signaled(struct job *jp)
{
//TODO: check what happens if we come from waitforjob() in expbackq()
        if (rootshell) {
                int s = job_signal_status(jp);
                if (s) /* WIFSIGNALED(s) || WIFSTOPPED(s) */
                        set_tty_state();
        }
}
#else
# define get_tty_state() ((void)0)
# define restore_tty_if_stopped_or_signaled(jp) ((void)0)
#endif

static void
set_curjob(struct job *jp, unsigned mode)
{
        struct job *jp1;
        struct job **jpp, **curp;

        /* first remove from list */
        jpp = curp = &curjob;
        while (1) {
                jp1 = *jpp;
                if (jp1 == jp)
                        break;
                jpp = &jp1->prev_job;
        }
        *jpp = jp1->prev_job;

        /* Then re-insert in correct position */
        jpp = curp;
        switch (mode) {
        default:
#if DEBUG
                abort();
#endif
        case CUR_DELETE:
                /* job being deleted */
                break;
        case CUR_RUNNING:
                /* newly created job or backgrounded job,
                 * put after all stopped jobs.
                 */
                while (1) {
                        jp1 = *jpp;
#if JOBS
                        if (!jp1 || jp1->state != JOBSTOPPED)
#endif
                                break;
                        jpp = &jp1->prev_job;
                }
                /* FALLTHROUGH */
#if JOBS
        case CUR_STOPPED:
#endif
                /* newly stopped job - becomes curjob */
                jp->prev_job = *jpp;
                *jpp = jp;
                break;
        }
}

#if JOBS || DEBUG
static int
jobno(const struct job *jp)
{
        return jp - jobtab + 1;
}
#endif

/*
 * Convert a job name to a job structure.
 */
#if !JOBS
#define getjob(name, getctl) getjob(name)
#endif
static struct job *
getjob(const char *name, int getctl)
{
        struct job *jp;
        struct job *found;
        const char *err_msg = "%s: no such job";
        unsigned num;
        int c;
        const char *p;
        char *(*match)(const char *, const char *);

        jp = curjob;
        p = name;
        if (!p)
                goto currentjob;

        if (*p != '%')
                goto err;

        c = *++p;
        if (!c)
                goto currentjob;

        if (!p[1]) {
                if (c == '+' || c == '%') {
 currentjob:
                        err_msg = "No current job";
                        goto check;
                }
                if (c == '-') {
                        if (jp)
                                jp = jp->prev_job;
                        err_msg = "No previous job";
 check:
                        if (!jp)
                                goto err;
                        goto gotit;
                }
        }

        if (is_number(p)) {
                num = atoi(p);
                if (num > 0 && num <= njobs) {
                        jp = jobtab + num - 1;
                        if (jp->used)
                                goto gotit;
                        goto err;
                }
        }

        match = prefix;
        if (*p == '?') {
                match = strstr;
                p++;
        }

        found = NULL;
        while (jp) {
                if (match(jp->ps[0].ps_cmd, p)) {
                        if (found)
                                goto err;
                        found = jp;
                        err_msg = "%s: ambiguous";
                }
                jp = jp->prev_job;
        }
        if (!found)
                goto err;
        jp = found;

 gotit:
#if JOBS
        err_msg = "job %s not created under job control";
        if (getctl && jp->jobctl == 0)
                goto err;
#endif
        return jp;
 err:
        ash_msg_and_raise_error(err_msg, name);
}

/*
 * Mark a job structure as unused.
 */
static void
freejob(struct job *jp)
{
        struct procstat *ps;
        int i;

        INT_OFF;
        for (i = jp->nprocs, ps = jp->ps; --i >= 0; ps++) {
                if (ps->ps_cmd != nullstr)
                        free(ps->ps_cmd);
        }
        if (jp->ps != &jp->ps0)
                free(jp->ps);
        jp->used = 0;
        set_curjob(jp, CUR_DELETE);
        INT_ON;
}

#if JOBS
static void
xtcsetpgrp(int fd, pid_t pgrp)
{
        if (tcsetpgrp(fd, pgrp))
                ash_msg_and_raise_perror("can't set tty process group");
}

/*