Similar to CS 31, you should implement a command line parser as a separate library that your shell will #include. The parser should build an ARGV array of tokens and identify any non-token elements of a command line. Note that you WILL need a more complex parser than you used for CS 31 to identify commands that are separated by |'s and to record I/O redirections without returning them as ARGV tokens.

For example, if the user inputs:

Your parser should identify that there are two commands, separated by a pipe, which should be run in the background:

Note that the 2> error.txt | and & portions of the command are instructions to the shell and are NOT command ARGV tokens.

To simplify parsing, you may assume that nothing other than white space (spaces, newlines, etc.) will appear after an ampersand (&), there will be at most one ampersand, and that ampersands will not appear for any reason other than to specify background tasks.

Your shell should be able to execute simple commands in the foreground and background by reading from the PATH environment variable and using execv(), which expects a full path to the program in its first argument. If the user’s command starts with /, ./, or ../ (e.g., "/bin/ls"), you can pass it to execv as-is. Otherwise, (e.g., "ls") you need to search the PATH environment variable to find and construct the full path. A call to getenv("PATH") will return to you a string of directories separated by ':' characters. You should look through those directories, in order, until you find a matching program name. You can use the access() function to check if a path contains an executable program (e.g., access("/bin/ls", X_OK)).

If the user executes "cd path", your shell should change the working directory to the specified path using chdir(). You can execute the pwd command to print the current working directory (to test if cd is working). Your shell should also terminate if the user inputs exit.

Your shell should keep a history of the most recent commands the user has entered using a circular queue (same as CS 31). If the user enters a command of "history", you should print the stored history of commands, each preceded by a number. If the user enters a command of !num (where num is an integer), it should re-execute the command that corresponds to that number.

You may assume that built-in commands (history, !num, exit, and cd) will NOT appear in the same command as a pipe or an I/O redirect. That is, despite real shells handing commands like "history | grep …​", your shell will not be asked to mix built-in commands with those features.

If the user enters a command that uses I/O redirection or pipes, the entire command should be saved in the history (the same as it was typed).

Your shell should support piping the output (standard out) from one command to the input (standard in) of another. A pipe is an inter-process communication (IPC) mechanism for two Unix processes running on the same machine. It’s a one-way communication channel between the two processes (one process always writes to one end of the pipe, the other process always reads from the other end of the pipe). The interface to a pipe is like a temporary file with two open ends — writes to one end by one process can be read from the other end by the another process. However, unlike a regular file, a read from a pipe results in the removal of data that was written by the other process.

The pipe() system call will create a pipe when given an array of two integers. It creates two file descriptors, one for the read end of the pipe (array element 0), the other for the write end of the pipe (array element 1).

Placing a pipe between two commands causes the output of the first to feed into the input of the second. For example:

Says to take the output from ls and rather than printing it, instead send it as input to sort, which will sort it and then print it.

Says to take the output from cat (the contents of file.txt) and send it to the input of grep, which searches for all lines containing the string "blah". This is a silly way to run grep, since grep can read files on its own without cat, but it works well for testing pipes.

You are not required to support multiple pipes in a single command line, although I would encourage you to think about how you might make that happen (it’s not that different).

Your shell should support I/O redirection whereby files replace a process’s standard in (0), standard out (1), or standard error (2) file descriptor streams. The user can ask to replace standard in by supplying "< filename". For example:

Says to use the file "input_file.txt" as file descriptor 0 rather than reading from terminal input and the file "output_file.txt" as file descriptor 1 rather than printing to standard out.

For output streams, the user must specify which I/O stream(s) to replace:

The user may also choose to redirect both streams, either to separate files or to the same one. To implement this functionality, most of the complexity is in the parser, since you’ll need to recognize that an I/O redirect is happening and treat the next token as the file name rather than an ARGV token. After parsing is complete and you’ve created a child process, you can use open() and dup2() to place the file at the appropriate file descriptor.

Note that most shells will assume you mean "1>" if you just say ">", but you are not required to do that. For output streams, you may assume there will be an explicit 1 or 2 preceding the ">". You may also assume that the user won’t give you nonsense numbers (e.g., 3>).

Your shell should report errors using perror() and continue executing whenever possible. If the main shell process (parent) makes a system call that fails (e.g., signal, fork, pipe) it’s fine to report the error and terminate, since you can’t really recover from those. For minor errors though (e.g., exec fails because the user’s command is invalid) a child process should terminate, but the shell should continue.

Always always always check the return value of any system call you make!

Your shell should reap all child processes when they terminate, close all file descriptors it’s no longer using, and get a clean bill of health from valgrind: no invalid memory accesses, uninitialized variables, or memory leaks.

During the lab meeting, I suggested a struct that looks like:

This struct is just a suggestion, and it resembles what I chose to do in my implementation. You’re welcome to add extra fields or change the way you record parsing information. Ultimately, what you need to know is:

If you find it helpful, it would be reasonable for you to add a flag to your struct that you can set to 0/1 depending on whether or not you find a pipe. Alternatively, you can simply set cmd2_args to NULL if you don’t find a pipe. It doesn’t really matter how you signal it as long as you know what you’ve chosen so that your shell can check for it later. You may also prefer to add a background flag to the struct rather than passing it in as a special argument. It doesn’t matter to me, and you have some flexibility in the design.

As far as the checkpoint goes, I’ll suggest something that will be useful for your debugging and for convincing me that your parser works correctly: add a function that prints a summary of the contents of your struct, whatever it happens to contain. I’ll give you some examples of what that might look like using the example struct above:

You don’t need to worry about printing the "dynamically-allocated array" stuff, I just added that to make it more clear what those things are (ARGV arrays). If you can print your structs this way, it will make it MUCH easier for you to debug your parser and convince yourself/me that it’s working correctly.

You may find it helpful to test with a program that writes to both stdout and stderr (already included in your repo). You can compile it with:

If you run it normally, (with no pipes or redirects), you’ll see that all of the output goes to your terminal, regardless of which stream is specified in fprintf. For more interesting tests, you can do things like:

The above should give you two files, each containing only one of the output streams.

You can also use pipes too:

The above should only print standard out’s line 5 to the terminal (due to grep’s text search behavior), but all of standard error should be captured to the file.

Note that you can also ask for things that don’t really make sense:

It’s not well-defined what should happen in the above case, since you’re giving two conflicting instructions about what to do with the standard out stream. This example is a user error and is not a good test case.