Section 10: Command line representation

The shell grammar defines the underlying hierarchical structure of command lines. The overall structure of a line, as described by the grammar, is:

• A list is composed of conditionals joined by ; or & (and the last command in the list might or might not end with &).
• A conditional is composed of pipelines joined by && or ||.
• A pipeline is composed of commands joined by |.
• A command is composed of words and redirections.

So lists are comprised of conditionals, which are comprised of pipelines, which are comprised of commands.

There are two common ways to represent our parsed command line in a data structure appropriate for our shell, a tree representation and a list representation. Students often are biased toward the tree representation, which precisely represents the structure of the grammar, but the list representation is simpler in some ways. It’s useful to consider them both.

Neither the tree representation nor the list representation will exactly match the parent/child relationships implied by parent process IDs for the shell process and its children! In-memory command line representations should be designed for ease of traversal; parent/child process relationships are determined by other constraints, such as which processes need to wait for others.

About grammars

Before going further:

EXERCISE SET. Work through the BNF grammar exercises.

Tree representation

The following tree-formatted data structure precisely represents this grammar structure.

• A command contains its executable, arguments, and any redirections.
• A pipeline is a linked list of commands, all of which are joined by |.
• A conditional is a linked list of pipelines. But since adjacent conditionals can be connected by either && or ||, we need to store whether the link is && or ||.
• A list is a linked list of conditionals, each flagged as foreground (i.e., joined by ;) or background (i.e., joined by &). Note that while the conditional link type doesn’t matter for the last pipeline in a conditional, the background flag does matter for the last conditional in a list, since the last conditional in a list might be run in the foreground or background.

For instance, consider this tree structure for a command line (the words and redirections that are there, but not being shown for the sake of simplifying the image somewhat):

EXERCISE. Assuming that a, b, c, d, e, and f are distinct commands, what could be a command line that would produce this tree structure?

a & b | c && d ; e | f &

EXERCISE. Sketch C++ structure definitions corresponding to this design, starting from this:

struct command {
    std::vector<std::string> args;
    command* next_in_pipeline = nullptr;
    command* prev_in_pipeline = nullptr;
};

Here’s one:

struct pipeline {
    command* command_child = nullptr;
    pipeline* next_in_conditional = nullptr;
    bool next_is_or = false;
};
struct conditional {
    pipeline* pipeline_child = nullptr;
    conditional* next_in_list = nullptr;
    bool is_background = false;
};

There are many other solutions. Logically, we need a struct for conditional chains that indicates whether the chain should be run in the foreground or background; a struct for pipelines; and a struct for commands. Each struct needs to hold the necessary pointers to form a linked list of siblings. Furthermore, conditionals and pipelines need a pointer to the first item of their sublists.

EXERCISE. Given a C++ structure corresponding to a conditional chain, explain how to tell whether that chain should be executed in the foreground or the background.

For our solution, that’s as simple as c->is_background.

EXERCISE. Given a C++ structure corresponding to a command, how can one determine whether the command is on the left-hand side of a pipe?

For our solution, a command c is on the left-hand side of a pipe iff c->next_in_pipeline != nullptr.

EXERCISE. Given a C++ structure corresponding to a command, how can one determine whether the command is on the right-hand side of a pipe?

If c->prev_in_pipeline != nullptr.

EXERCISE. How should we destroy a conditional, in other words, free all its memory and the memory of related structures? How should the conditional::~conditional() destructor function be implemented?

Linked list representation

Alternatively, we can create a single linked list of all of the commands. In this case, we also store the connecting operator (one of & ; | && or ||). For our example command line above, the flat linked list structure might look something like:

Traversing this structure is slightly more time-consuming than in the tree representation, but the structure is much easier to build, and the additional CPU time spent traversing it is in the noise given how short command lines typically are.

EXERCISE. Write C++ structure definitions corresponding to this design.

Here’s an example:

struct command {
    std::vector<std::string> args;
    command* next = nullptr;
    command* prev = nullptr;
    int link = TYPE_SEQUENCE;  // Operator following this command.
                    // Always TYPE_SEQUENCE or TYPE_BACKGROUND for last in list.
};

Much simpler!

Another good one, with fewer pointers and thus fewer opportunities for memory mistakes, but harder to traverse (you need C++ iterators):

struct command {
    std::vector<std::string> args;
    int op;         // as above
};
using command_list = std::list<command>;

EXERCISE. Given a C++ structure corresponding to a conditional chain, explain how to tell whether that chain should be executed in the foreground or the background.

bool chain_in_background(command* c) {
    while (c->op != TYPE_SEQUENCE && c->op != TYPE_BACKGROUND) {
        c = c->next;
    }
    return c->op == TYPE_BACKGROUND;
}

Things are slightly more complicated with a flat linked list. We are still executing commands sequentially, but some subsequences of commands may need to be executed in the foreground or the background. During parsing, we can skip ahead in the command line to find the end of our current list (i.e., our current chain of conditionals).

EXERCISE. Given a C++ structure corresponding to a command, how can one determine whether the command is on the left-hand side of a pipe?

If c->op == TYPE_PIPE.

EXERCISE. Given a C++ structure corresponding to a command, how can one determine whether the command is on the right-hand side of a pipe?

If c->prev != nullptr && c->prev->op == TYPE_PIPE.

EXERCISE. Sketch out code for parsing a command line into these C++ structures.

This solution builds up the command linked list in chead.

command* parse_line(const char* s) {
    shell_parser parser(s);
    command* chead = nullptr;    // first command in list
    command* clast = nullptr;    // last command in list
    command* ccur = nullptr;     // current command being built
    for (auto it = parser.begin(); it != parser.end(); ++it) {
        switch (it.type()) {
        case TYPE_NORMAL:
            // Add a new argument to the current command.
            // Might require creating a new command.
            if (!ccur) {
                ccur = new command;
                if (clast) {
                    clast->next = ccur;
                    ccur->prev = clast;
                } else {
                    chead = ccur;
                }
            }
            ccur->args.push_back(it.str());
            break;
        case TYPE_SEQUENCE:
        case TYPE_BACKGROUND:
        case TYPE_PIPE:
        case TYPE_AND:
        case TYPE_OR:
            // These operators terminate the current command.
            assert(ccur);
            clast = ccur;
            clast->op = it.type();
            ccur = nullptr;
            break;
        }
    }
    return chead;
}

Testing your shell

In our experience, students experience two different kinds of error with this problem set: first, creating incorrect parsed representations for a command line; and second, executing incorrect system calls for a given representation. It is worth thinking explicitly with your peers about how you will test these aspects of your problem set! There’s no one right answer.

EXERCISE. Discuss what general tools you might use for testing your code. Are there kinds of error the compiler might help you find?

Sanitizers can catch many kinds of undefined behavior error, including missing nullptr assignments, use-after-free bugs, and so forth. Try make SAN=1 check!

EXERCISE. Discuss how you might test your parsing function, parse_line. What does it mean for the function to be correct? How could you test it for different kinds of error?

parse_line is correct if it parses command lines into the corresponding representations, without executing undefined behavior or leak memory.

(We promise that we never provide unparsable strings to parse_line, but a maximally robust parse_line would also check for input errors. If the user provided an invalid command line, such as “&& echo foo”, parse_line would report the error.)

One example plan to test that parse_line produces the right representations would be to add functions to your representation that unparse the representation into string format. For instance, these functions unparse the tree representation:

std::string command::unparse() {
    std::string s = "", separator = "";
    for (auto arg : this->args) {
        s += separator + arg;
        separator = " ";
    }
    if (this->next_in_pipeline) {
        s += " | " + this->next_in_pipeline->unparse();
    }
    return s;
}

std::string pipeline::unparse() {
    std::string s = this->command->unparse();
    if (this->next_in_conditional) {
        s += (this->next_is_or ? " || " : " && ");
        s += this->next_in_conditional->unparse();
    }
    return s;
}

std::string conditional::unparse() {
    std::string s = this->pipeline->unparse();
    if (this->next_in_list) {
        s += (this->is_background ? " & " : " ; ");
        s += this->next_in_list->unparse();
    } else if (this->is_background) {
        s += " &";
    }
    return s;
}

Then you could write a test function that, for each of a set of sample command line strings, (1) parses the string into a representation, (2) unparses the representation into a string, and (3) validates that the string and the representation string are equal.

EXERCISE. Discuss how you might test your execution functions, command::run and run_list. What does it mean for the functions to be correct? How could you test it for different kinds of error?

Since you’re aiming to implement a shell compatible with the normal Unix shells, these functions are correct if they call roughly the same system calls as the normal shell. And our friend strace is a good way to investigate these system calls!

For example, say you’re curious about how the shell executes the command chain cat /dev/null | wc. Then try this:

$ strace -f -b execve -o s.out sh -c "cat /dev/null | wc"

Here’s what the arguments mean:

• -f: Follow forks. This causes the strace to follow forked children, so you can see exactly what the forked child processes do.
• -b execve: Detach when execve is encountered. This causes strace to stop following a child once it loads a new program image.

When -f is provided, every line in the strace starts with the process ID of the relevant process. It’s important to remember this or you may get confused about which actions are being taken in child processes as opposed to the parent shell! Consider sorting the strace by process ID, so that all of a process’s actions are brought together:

$ sort -sk1,1 s.out | less

Here’s what the arguments mean:

• -k1,1: Sort by the first blank-separated key, which is the process ID.
• -s: Stable sort. This means that sort will not reorder lines that have the same process ID.

You will also need to know that some system calls have different names in strace than in the standard library. For instance:

• The fork system call appears as clone.
• The _exit system call appears as exit_group.
• The waitpid system call appears as wait4.

Putting all this together, here is a part of the sorted strace -f -b execve output for the command sh -c "/bin/echo foo | /usr/bin/wc". (Providing full pathnames for the commands avoids uninteresting calls to stat.) Compare these system calls to the pipe dance!

249   pipe([3, 4])                      = 0
249   clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f6dd7a48850) = 250
249   close(4 <unfinished ...>
249   <... close resumed>)              = 0
249   clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD <unfinished ...>
249   <... clone resumed>, child_tidptr=0x7f6dd7a48850) = 251
249   close(3 <unfinished ...>
249   <... close resumed>)              = 0
249   close(-1 <unfinished ...>
249   <... close resumed>)              = -1 EBADF (Bad file descriptor)
249   wait4(-1,  <unfinished ...>
249   <... wait4 resumed>[{WIFEXITED(s) && WEXITSTATUS(s) == 0}], 0, NULL) = 250
249   --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=250, si_uid=1000, si_status=0, si_utime=0, si_stime=0} ---
249   rt_sigreturn({mask=[]})           = 250
249   --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=251, si_uid=1000, si_status=0, si_utime=0, si_stime=0} ---
249   rt_sigreturn({mask=[]})           = 250
249   wait4(-1, [{WIFEXITED(s) && WEXITSTATUS(s) == 0}], 0, NULL) = 251
249   exit_group(0)                     = ?
249   +++ exited with 0 +++
250   close(3 <unfinished ...>
250   <... close resumed>)              = 0
250   dup2(4, 1 <unfinished ...>
250   <... dup2 resumed>)               = 1
250   close(4 <unfinished ...>
250   <... close resumed>)              = 0
250   execve("/bin/echo", ["/bin/echo", "foo"], 0x564ffc49fc38 /* 13 vars */ <unfinished ...>
251   dup2(3, 0 <unfinished ...>
251   <... dup2 resumed>)               = 0
251   close(3)                          = 0
251   execve("/usr/bin/wc", ["/usr/bin/wc"], 0x564ffc49fc18 /* 13 vars */ <unfinished ...>

Inferring properties of command lines

Some properties of command line execution can be observed by executing carefully-constructed command lines of common Unix utilities, such as these:

Program	Description
true	Silently succeed (exit with status 0).
false	Silently fail (exit with status 1).
cat	Write file(s) to standard output.
wc	Count lines, words, and characters in standard input.
head -n N	Print first N lines of standard input.
tail -n N	Print last N lines of standard input.
yes	Print y (or any arguments) forever.
sleep N	Pause for N seconds.
exit [STATUS]	Exit the shell with status STATUS (default 0).
sh -c "COMMANDLINE"	Run another shell executing "COMMANDLINE".

For example, the behaviors of the && and || conditional operators can be explored with different combinations of false, true, and echo, among other programs.

# Demonstrate that `A && B` runs `B` iff `A` exits with status 0
$ true && echo X
X
$ false && echo X
$ sh -c "exit 2" && echo X

# Demonstrate that `A || B` runs `B` iff `A` does not exit with status 0
$ true || echo X
$ false || echo X
X
$ sh -c "exit 2" || echo X
X

In these exercises, you’ll attempt to explore more complex shell properties.

EXERCISE. Demonstrate that the exit status of a conditional equals the exit status of the last-executed command in that conditional.

Hint: The $? shell variable equals the exit status of the most-recently-executed foreground conditional. For instance:

$ true
$ echo $?
0
$ false
$ echo $?
1
$ sh -c "exit 2"
$ echo $?
2

$ true && false
$ echo $?
1
$ true && sh -c "exit 2"
$ echo $?
2
$ sh -c "exit 3" && true
$ echo $?
3

EXERCISE. Demonstrate that a conditional chain, such as A && B || C, executes from left to right.

$ true && true || echo foo
$ true && false || echo foo
foo
$ false && true || echo foo
foo
$ true || true && echo foo
foo
$ true || false && echo foo
foo
$ false || true && echo foo
foo

The above results can be explained by reasoning from left to right. For example, in the third command list, false has status 1, so false && true has status 1, so echo foo is executed. If conditional chains were executed in some other way we would expect different results.

EXERCISE. Demonstrate that in a two-process pipeline, such as A | B, processes A and B execute in parallel.

# If the right-hand command started after the left-hand command finished,
# then `foo` would never appear. It appears immediately.
$ yes | echo foo
foo

# If the left-hand command started after the right-hand command finished,
# then the error message would appear after 10 seconds (but it appears immediately).
$ cat /tmp/nonexistentfile | sleep 10
cat: /tmp/nonexistentfile: No such file or directory

EXERCISE. Demonstrate the same thing for three-or-more-process pipelines.

EXERCISE. Demonstrate that the exit status of a pipeline equals the exit status of its rightmost command. (Try to avoid using $?.)

Conditionals can broadly test a command’s exit status (in the sense of “zero or not”).

$ false | false | false | false | true && echo foo
foo
$ false | false | true || echo foo
$ true | true | false && echo foo
$ true | true | false || echo foo
foo

Subprocess

Finally, this exercise (which is not about command line representation) will test your understanding of file descriptor system calls as well as processes.

EXERCISE. Write a function that implements a version of Python’s subprocess.Popen functionality. Your function should have the following signature:

// subprocess(file, argv, pfd)
//    Run the command `file` with arguments `argv` in a child process.
//    Three pipes are opened between this process and the child process:
//    one for the child’s standard input, one for its standard output,
//    and one for its standard error. The `pfd` argument is populated
//    with this process’s pipe ends.
//
//    * Data written by this process to `pfd[0]` is read from the child’s
//      standard input.
//    * Data written to the child’s standard output is read by this
//      process from `pfd[1]`.
//    * Data written to the child’s standard error is read by this
//      process from `pfd[2]`.
//
//    Returns the process ID of the child or -1 on error.
pid_t subprocess(const char* file, char* const argv[], int pfd[3]);

You will use the pipe and dup2 system calls, among others.

Here’s one solution. It uses a common pattern in C programs called “goto error”: all the error handling code is in one place, and goto is used to jump to that place from multiple locations where errors could occur.

pid_t subprocess(const char* file, char* const argv[], int pfd[3]) {
    // create pipes
    int inpfd[2] = {-1, -1}, outpfd[2] = {-1, -1}, errpfd[2] = {-1, -1};
    pid_t p = -1;
    if (pipe(inpfd) < 0
        || pipe(outpfd) < 0
        || pipe(errpfd) < 0) {
        goto error;
    }

    // create child
    p = fork();
    if (p == 0) {
        dup2(inpfd[0], STDIN_FILENO);
        close(inpfd[0]);
        close(inpfd[1]);
        dup2(outpfd[1], STDOUT_FILENO);
        close(outpfd[0]);
        close(outpfd[1]);
        dup2(errpfd[1], STDERR_FILENO);
        close(errpfd[0]);
        close(errpfd[1]);
        execvp(file, argv);
        _exit(1);
    } else if (p < 0) {
        goto error;
    }

    // clean up file descriptors
    close(inpfd[0]);
    pfd[0] = inpfd[1];
    close(outpfd[1]);
    pfd[1] = outpfd[0];
    close(errpfd[1]);
    pfd[2] = errpfd[0];

    // return pid
    return p;

  error:
    if (inpfd[0] >= 0) {
        close(inpfd[0]);
        close(inpfd[1]);
    }
    if (outpfd[0] >= 0) {
        close(outpfd[0]);
        close(outpfd[1]);
    }
    if (errpfd[0] >= 0) {
        close(errpfd[0]);
        close(errpfd[1]);
    }
    return -1;
}