POSIX arithmetic expansion

Question

I understand that a shell should be able to perform arithmetic expansion. My shell can do it:

$ echo $((1+2*3+4*5))
27

My solution uses the lemon parser where I used a calculator example from SO:

https://stackoverflow.com/questions/34918631/use-lemon-parserlalr-generate-a-calulator-how-to-get-param-from-expressions

My problem was how to access the result and not just print it because if you follow the link above, it only prints the result and doesn't use the result. To make an arithmetic expansion I actually must replace the expression $((1+2*3+4*5)) with the result instead of printing it directly. So it is like having an argv that I must update. That is done in this code, with snippets from the answer linked above.

char * expand_calc(char *shellcommand) {
    char mystring[CMD_LEN];
    char *line;
    void *pParser;
    char *c;
    /* TODO use regex for between digits only */
    shellcommand = str_replace(shellcommand, "+", " + ");
    shellcommand = str_replace(shellcommand, "*", " * ");
    shellcommand = str_replace(shellcommand, "/", " / ");
    shellcommand = str_replace(shellcommand, "-", " - ");
    strcpy(mystring, shellcommand);
    line = strstr(mystring, "$((");
    pParser = (void *) ParseAlloc(malloc);
    int value;
    if (line) {
        if (line && line[0] == '$' && line[1] == '(') {
            /* TODO: find condition for not remove brackets here e g when setting a shell variable */
            ++line;
            ++line;
            ++line;
            line[strlen(line) - 2] = 0;
            /* end TODO */
            char *buf[64];
            char **ptr1 = str_split(buf, line, ' ');
            struct SToken v[32];
            int j = 0;
            for (j = 0; ptr1[j]; j++) {
                c = ptr1[j];
                v[j].token = c;
                switch (*c) {
                    case '0':
                    case '1':
                    case '2':
                    case '3':
                    case '4':
                    case '5':
                    case '6':
                    case '7':
                    case '8':
                    case '9':
                        for (value = 0; *c && *c >= '0' && *c <= '9'; c++)
                            value = value * 10 + (*c - '0');
                        v[j].value = value;
                        Parse(pParser, INTEGER, &v[j]);

                        break;

                    case '+':
                        Parse(pParser, PLUS, NULL);
                        break;

                    case '-':
                        Parse(pParser, MINUS, NULL);
                        break;

                    case '*':
                        Parse(pParser, TIMES, NULL);
                        break;

                    case '/':
                        Parse(pParser, DIVIDE, NULL);
                        break;

                    case '(':
                        Parse(pParser, LPAR, NULL);
                        break;
                    case '>':
                        Parse(pParser, LARGER, NULL);
                        break;
                    case '<':
                        Parse(pParser, SMALLER, NULL);
                        break;
                    case '=':
                        Parse(pParser, EQEQ, NULL);
                        break;
                    case ')':
                        Parse(pParser, RPAR, NULL);
                        break;

                    default:
                        if (strlen(c) > 4 && !strcmp("while", c)) {
                            Parse(pParser, WHILE, NULL);
                        }
                        else if (strlen(c) > 1 && !strcmp("==", c)) {
                            Parse(pParser, EQEQ, NULL);
                        }
                        else if (strlen(c) > 1 && !strcmp("!=", c)) {
                            Parse(pParser, NOTEQ, NULL);
                        }
                        else if (strlen(c) > 1 && !strcmp("for", c)) {
                            Parse(pParser, FOR, NULL);
                        }
                        else fprintf(stderr, "Unexpected token %s\n", c);
                }
            }
            Parse(pParser, 0, NULL);
        }
    }
    strcpy(mystring, shellcommand);
    char *cp;
    strcpy(mystring, shellcommand);
    cp = strstr(mystring, "$((");
    int position = cp - mystring;
    //int quote = isBetweenQuotes(position, mystring);
    if (cp) {
        char str[32];
        sprintf(str, "%d", result);
        shellcommand = str_replace(shellcommand, cp, str);
    }
    return shellcommand;
}

My grammar looks like the following, where the trick is the setresult(A); where I use a global variable to make the result know - maybe not perfect but it was the only way I could make the result known from the evaluation in the grammar.

%include
{
#include "types.h"
#include "openshell.h"
#include "assert.h"
}
%syntax_error { fprintf(stderr, "Syntax error\n"); }
%token_type { struct SToken* }
%type expr { int }

%nonassoc EQEQ NOTEQ SET LARGER SMALLER.
%left FOR WHILE.
%left PLUS MINUS.
%left TIMES DIVIDE.

program ::= expr(A). { setresult(A); /*printf("%d\n", A);*/ }
expr(A) ::= expr(B) PLUS expr(C). {A = B + C; }
expr(A) ::= expr(B) MINUS expr(C). {A = B - C; }
expr(A) ::= expr(B) TIMES expr(C). {A = B * C; }
expr(A) ::= expr(B) EQEQ expr(C). {if(B==C) {A=1;} else A=0;}
expr(A) ::= expr(B) NOTEQ expr(C). {if(B==C) {A=0;} else A=1;}
expr(A) ::= expr(B) LARGER expr(C). {if(B>C) {A=1;} else A=0;}
expr(A) ::= expr(B) SMALLER expr(C). {if(B<C) {A=1;} else A=0;}

expr(A) ::= expr(B) SET expr(C).  {A=C;B=C;}


expr(A) ::= FOR LPAR expr(B) SEMICOLON expr(C) SEMICOLON expr(D) RPAR expr(E). {A = D*B*E*C+1; } /* $((for ( 1 == 1 ; 2 == 2 ; 3 == 3 ) 55)) */
expr(A) ::= WHILE LPAR expr(B) RPAR expr(C).
{
while (B) { printf("%d", C);
}
A=C;printf("\n");
}
expr(A) ::= expr(B) DIVIDE expr(C).
{
    if (C != 0)
    {
        A = B / C;
    }
    else
    {
        fprintf(stderr, "divide by 0");
    }
}
expr(A) ::= LPAR expr(B) RPAR. { A = B; }
expr(A) ::= INTEGER(B).
{
//printf("the result = %s\n", B->token);
    A = B->value;
    //printf("Passed argument: %s\n", B->token);
}
/* http://my.safaribooksonline.com/book/operating-systems-and-server-administration/unix/1565923472/syntax/lbs.appd.div.3 */

/* http://wiki.bash-hackers.org/syntax/basicgrammar */

My main function:

int main(int argc, char *argv[]) {
    bool donotrun = false;
    struct sigaction new_action, old_action;
    hashtable_t *hashtable = ht_create(65536);
    /* Set up the structure to specify the new action. */
    new_action.sa_handler = termination_handler;
    sigemptyset(&new_action.sa_mask);
    new_action.sa_flags = 0;

    sigaction(SIGINT, NULL, &old_action);
    if (old_action.sa_handler != SIG_IGN)
        sigaction(SIGINT, &new_action, NULL);
    sigaction(SIGHUP, NULL, &old_action);
    if (old_action.sa_handler != SIG_IGN)
        sigaction(SIGHUP, &new_action, NULL);
    sigaction(SIGTERM, NULL, &old_action);
    if (old_action.sa_handler != SIG_IGN)
        sigaction(SIGTERM, &new_action, NULL);

    int value;
    void *pParser;
    char *c;
    // struct SToken v[argc];

    int index = 0;
    int i;
    char *cvalue = NULL;
    const char *commandFile;
    bool quietFlag;

    while (1) {
        index = 0;
        i = getopt_long(argc, argv, "pc:vh",
                        options, &index);
        if (i == -1)
            break;
        switch (i) {
            case 'p': {
                exit(EXIT_SUCCESS);
            }
            case 'v': {
                printf("sh OpenShell version 0.1(a)\n");
                printf("Version: %s\n", VERSION);
                exit(EXIT_SUCCESS);

            }
            case 'h': {
                printf("Usage: ./shell\n");
                exit(EXIT_SUCCESS);

            }
            case 'c': {
                cvalue = optarg;
                command(cvalue, hashtable);
                exit(EXIT_SUCCESS);
            }

            case 'f':
                /*
                 * Execute commands from file.
                 * This is used for osh script files.
                 * The quiet flag is also set.
                 */
                if ((argc != 1) || commandFile)
                    usage();

                quietFlag = true;
                argc--;

                break;


            case '?':
                if (optopt == 'c')
                    fprintf(stderr, "Option -%c requires an argument.\n", optopt);
                else if (isprint (optopt))
                    fprintf(stderr, "Unknown option `-%c'.\n", optopt);
                else
                    fprintf(stderr,
                            "Unknown option character `\\x%x'.\n",
                            optopt);
            default: {
                return 1;
            }
        }
    }
    getPath();
    pParser = (void *) ParseAlloc(malloc);
    char *copy;

    for (; ;) {
        bool scanning = true;
        bool calc = true;
        while (scanning) {
            char *line = NULL;
            line = readline("$ ");
            //return 0;
            copy = strdup(line);

            if (strstr(line, "=")) {
                donotrun = true;
                char str[128];
                char *ptr;
                strcpy(str, line);
                strtok_r (str, "=", &ptr);
                ht_set(hashtable, str, ptr);
            }

            if (!scanning)
                break;

            if (!isatty(fileno(stdin))) {
                *argv++;
                readFile(*argv++, hashtable);
                free(line);
                exit(0);
            }
            else {

                if (!donotrun) {
                    command(line, hashtable);
                }
                donotrun = false;
                add_history(copy);
            }
        }
    }
    //  ParseFree(pParser, free);FIXME: where should this go?
    return 0;
}

helper function:

/*
 * Parse and execute one null-terminated command line string.
 * This breaks the command line up into words, checks to see if the
 * command is an alias, and expands wildcards.
 */
int command(char *cmd, hashtable_t *hashtable) {

    const char *endCmd;
    char cmdName[CMD_LEN];
    freeChunks();
    //printf("cmd %s\n", cmd);
    /*
     * Skip leading blanks.
     */
    if (cmd) {
        while (isBlank(*cmd))
            cmd++;
        /*
         * If the command is empty or is a comment then ignore it.
         */

        if ((*cmd == '\0') || (*cmd == '#'))
            return 0;
        /*
         * Look for the end of the command name and then copy the
         * command name to a buffer so we can null terminate it.
         */
        endCmd = cmd;

        while (*endCmd && !isBlank(*endCmd))
            endCmd++;

        memcpy(cmdName, cmd, endCmd - cmd);
        cmdName[endCmd - cmd] = '\0';
        /*
         * Expand simple environment variables
         */
        while (!strstr(cmd, "((") && strstr(cmd, "$("))
            expandVariable((char *) cmd, hashtable);

        /*
        * Expand POSIX variable expansion e g $ echo $str
        */
        while (!strstr(cmd, "((") && strstr(cmd, "$")) {
            if (!expand_parameter((char *) cmd, hashtable))
                break;
        }
        /*
        * Expand POSIX arithemtic expansion
        */
        while (strstr(cmd, "$((")) {
            if (cmd = expand_calc((char *) cmd))
                break;
        }
        /*
          * Now look for the command in the builtin table, and execute
          * the command if found.
          */
        if (exec_builtin(cmd)) {
            return 0;
        }
        /*
         * The command is not a built-in, so run the program along
         * the PATH list.
         */
        return run_cmd(cmd);
    }
    else return 0;
}

Test

#!/usr/bin/env osh
echo HELLO
echo "*** YOU SHOULD SEE HELLO ABOVE ***"
ls *
echo "*** YOU SHOULD SEE THE OUTPUT FROM ls * ABOVE ***"
who|awk '{print $1}'
echo "*** YOU SHOULD SEE THE OUTPUT FROM who ABOVE ***"
echo $((1 + 2 * 3 + 4))
echo "*** YOU SHOULD SEE THE NUMBER 11 ABOVE ***"

Test output

$ ./shell < ../tst_exp.sh 
'PATH' is set to /usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/snap/bin.
HELLO
*** YOU SHOULD SEE HELLO ABOVE ***
CMakeCache.txt            hello_2.7-0ubuntu1.dsc  not
cmake_install.cmake       hello_2.7.orig.tar.gz   osh
hello_2.7-0ubuntu1_amd64.changes  hello-2.7.tar.gz    script.sh
hello_2.7-0ubuntu1_amd64.deb      jeff            shell
hello_2.7-0ubuntu1.diff.gz    Makefile        testresult.txt

build-area:
hello_2.7-0ubuntu1_amd64.build    hello_2.7-0ubuntu1.diff.gz
hello_2.7-0ubuntu1_amd64.changes  hello_2.7-0ubuntu1.dsc
hello_2.7-0ubuntu1_amd64.deb      hello_2.7.orig.tar.gz

.bzr:
branch  branch-format  branch-lock  checkout  README  repository

CMakeFiles:
3.5.1                CMakeTmp       Makefile.cmake
cmake.check_cache        feature_tests.bin  progress.marks
CMakeDirectoryInformation.cmake  feature_tests.c    shell.dir
CMakeOutput.log          feature_tests.cxx  shellparser.dir
CMakeRuleHashes.txt      Makefile2      TargetDirectories.txt

hello:
ABOUT-NLS   ChangeLog    configure.ac  doc      Makefile.in  README  TODO
aclocal.m4  ChangeLog.O  contrib       gnulib       man      src
AUTHORS     config.in    COPYING       INSTALL      NEWS     tests
build-aux   configure    debian        Makefile.am  po       THANKS

hello-2.7:
ABOUT-NLS   ChangeLog.O    configure     gnulib       man     src
aclocal.m4  config.h       configure.ac  INSTALL      NEWS    stamp-h1
AUTHORS     config.in      contrib   Makefile     osh     tests
build-aux   config.log     COPYING   Makefile.am  po      THANKS
ChangeLog   config.status  doc       Makefile.in  README  TODO
*** YOU SHOULD SEE THE OUTPUT FROM ls * ABOVE ***
[32086] 
dac
*** YOU SHOULD SEE THE OUTPUT FROM who ABOVE ***
11
*** YOU SHOULD SEE THE NUMBER 11 ABOVE ***

The test output is expected, and I can also add my own shebang #!/usr/bin/env osh if I install the shell in usr/local/bin/osh.

Answer 1

1. Error checking

Consider this line of code:

line = readline("$ ");

If you read the manual for readline, you'll see that it says:

readline returns the text of the line read. A blank line returns the empty string. If EOF is encountered while reading a line, and the line is empty, NULL is returned.

So it might be the case that after this call, the value of line is NULL. But the next thing the code does is:

copy = strdup(line);

If you pass NULL to strdup, the program will crash.

So after calling readline, you need to check the value of line for the exceptional case:

line = readline("$ ");
if (line == NULL) {
    /* No more lines, so exit the loop. */
    break;
}

This is just one example. You need to check the result of every function that might fail. For another example, the specification for strdup says:

The strdup() function shall return a pointer to a new string on success. Otherwise, it shall return a null pointer and set errno to indicate the error.

So after calling strdup, you need to check the value of copy:

copy = strdup(line);
if (copy == NULL) {
    perror("strdup");
    exit(EXIT_FAILURE);
}

And so on, for all the other functions that might fail (str_replace, str_split, Parse, and no doubt many others).

2. Copying

Consider this code:

char * expand_calc(char *shellcommand) {
    char mystring[CMD_LEN];
    /* ... */
    strcpy(mystring, shellcommand);

Here you are copying shellcommand, a string whose length you don't know, into mystring, an array with length CMD_LEN. So there an obvious concern here: what happens if shellcommand has more than CMD_LEN characters? In that case, mystring will be filled up, but strcpy won't stop: it will keep copying characters from shellcommand into whatever region of memory follows after the end of mystring. This will overwrite and corrupt whatever was stored in that region of memory.

This is known as a buffer overflow, and nearly every program that has a buffer overflow is vulnerable to a buffer overflow attack.

Every use of the functions strcpy and sprintf is suspicious because there is no control over how many characters get written. You should get into the habit of using strncpy or snprintf instead. So in the example above you could have written:

strncpy(mystring, shellcommand, sizeof mystring);
mystring[(sizeof mystring) - 1] = '\0';

or alternatively:

snprintf(mystring, sizeof mystring, "%s", shellcommand);

but actually, since you never modify mystring, there was no point in doing this copy at all, and you could just remove this code.