COSI 31a: Spring 2009
Programming Assignment 1

Your task is to write a simple command line environment for interacting with the filesystem. You will use threads to implement pipes, allowing commands to send each other output, creating interesting output by combining simple commands.

You must run each command in its own thread and use inter-thread communication to implement the pipe abstraction in order to get credit for this assignment.

One of the benefits of this model is that very large files can be processed through the pipeline without loading the entire file into memory. The abstraction of pipes is very convenient for arbitrarily complex compositions of stream filters that can operate efficiently in a relatively small amount of memory.

Assigned Tasks

The Command Line

You must include a loop in your main program that prints a simple prompt, accepts a command (or multiple commands separated by pipes), and prints the output from that command (if any). This type of loop is sometimes called a read-eval-print loop, or REPL. For example: 
  > catfoo
  invalid command
  > cat foo
  this is
  a test file
  >
Your REPL must read user commands from System.in.

Working Directory

You must also support simple directory commands: ls, cd, and pwd. cd is the only command you will implement that does not use message queues, because it does not take piped input and has no useful output.

The directory from which you start the command line program should be initialized as the current working directory. The working directory can be modified with the cd command. You use the command ls to list the contents of the current working directory.

This will be a little more challenging than you might think because you can't modify the invoking environment's working directory. You'll need to manage a separate working directory for your shell.

Output Redirection

You must accept an optional output redirection operator at the end of a series of commands. This operator allows the user to specify a file into which to store output, instead of printing it to the console. The format of the operator is: 
  command 1 [ | command 2 | ... | command n] > filename
For example: 
  > cat foo > bar
  >
After executing this command, foo and bar will have the same contents. If bar existed before this command was run, its previous contents will have been replaced with the contents of foo.

Pipes

You are to implement inter-thread communication via simulated pipes. This technique is similar, but not identical, to UNIX pipes. Your threads are to use a message queue that contains one line of text per message. You do not need to handle binary files, you only need to handle text files.

The Commands

You must implement the following commands:

CommandShort DescriptionNotes
 
cat file1 [file2 file3 ...]
 Output the contents of one or more files Unlike the UNIX command cat, you do not need to accept piped input to cat. In other words, in your program, cat will always be first in a string of commands separated by pipes. 
    > cat foo bar
    this is the first
    test file
    this is the beginning
    of the second test file
    >
  
grep searchString
 Read lines from piped input and output only those lines that contain searchString You do not need to do regular expression matching. You should do a simple case-sensitive string search, and count any line containing searchString as a match. 
    > cat foo
    A common first program is
    a program that says hello
    world to the user. This
    is called hello world.
    > cat foo | grep hello
    a program that says hello
    is called hello world.
    >
  
lc
 Read lines from piped input and output a single number after reading all input lines. This number must be the number of lines in the input (which may be zero). 
    > cat foo
    A common first program is
    a program that says hello
    world to the user. This
    is called hello world.
    > cat foo | grep hello | lc
    2
    >
  
pwd
 Pipe the current working directory to the output message queue. 
    > pwd
    /home/ross/proj/cs31a/pa1
    >
  
ls
 Pipe the contents of the current directory to the output message queue.

You may want to use the Java File class (also see the slide about the File class in the slides from the first tutorial).

You do not need to allow arguments to ls, that is, ls can just always output the contents of the current working directory. You do not need to include "." or ".." in the list. You also do not need to mark directories with any special characters.

    > ls
    my_directory
    foo
    bar
    >
  
cd
 Change to another directory relative to the current directory.

Make sure you can accept the special directories "." (the current directory) and ".." (one directory up in the directory hierarchy). You do not need to support absolute paths.

    > pwd
    /home/ross/proj/cs31a/pa1
    > cd ..
    > pwd
    /home/ross/proj/cs31a
    > cd pa2
    > pwd
    /home/ross/proj/cs31a/pa2
    >

Important note: the cd command is the only command (other than quit) that does not need to participate in the piping mechanism, it can only output errors, it never accepts piped input or sends piped output. For this reason, your implementation of the cd command can be simpler than your implementation of the other commands.

 
quit
 Quit the command line. Like cd, the quit command can be very simple, and it should just end your REPL and return from your main method.

Waiting for Commands to Finish

Your REPL must print the prompt and start accepting input after the previous commands have finished and printed its output or error message. This means that you must wait for all command threads to finish before restarting the loop and printing a prompt to the user. Remember the basic thread methods that you have learned for doing this. Try not to busy-wait by continually asking a thread what its status is, there is a better thread method for accomplishing this task.

If you don't wait, your output might look like this:

  > cat foo
  > This is a
  test file containing
  three lines.

Note how the next prompt prints before the thread finishes outputting the contents of file foo. If you correctly wait for all command threads to finish, then your output will look like this:

  > cat foo
  This is a
  test file containing
  three lines.
  >

Notes

Handling Errors

You should handle errors gracefully. Exceptions thrown by Java calls should be caught and transformed into error messages for the user. After printing an error message, the user should see a new prompt. You should also handle parse errors on the command line if the user does not type a command correctly. You do not need to do sophisticated error reporting from the parse (this can be very difficult), but try to give useful hints (like "grep requires a search string argument").

Producer/Consumer

Your program uses the producer/consumer design pattern, where each command consumes piped input (unless it is the first command, like cat or ls) and produces piped output. In our case, all messages produced and consumed are strings, each representing a single line of input or output.

Commenting Your Code

Be sure that you use succinct comments to explain how your code works. We would especially like to see JavaDoc-style comments for each class and class method, describing how they work and any pre- or post-conditions that should hold.

Sample Code

To help you get started, we suggest that you use the following class to implement blocking message queues: ArrayBlockingQueue. A blocking queue causes a thread to block if it attempts to take a message from an empty queue, and automatically wake up again when the queue becomes non-empty again. If you represent each command as its own thread, and each thread runs an object which has an input and output ArrayBlockingQueue, then you will have a good framework in place for completing this project.

To help you get started here are some sample files. The first is a class called Filter, and it represents a command that can run in a thread and read from an input message queue and write to an output message queue. This class is not a complete, working example, but rather is designed to help you see how to use the ArrayBlockingQueue and how to implement Runnable.

Filter.java
import java.util.concurrent.*;

public abstract class Filter implements Runnable {
    protected BlockingQueue in;
    protected BlockingQueue out;
    protected volatile boolean done;
    
    public Filter(BlockingQueue in, BlockingQueue out) {
        this.in = in;
        this.out = out;
        this.done = false;
    }
    
    public void run() {
        Object o;
        while(! this.done) {
            o = in.take();    // read from input queue, may block
            o = transform(o); // allow filter to change message
            out.put(o);       // forward to output queue
        }
    }
    
    protected abstract Object transform(Object o);
}




Some of the modifications you will have to make:



    
  
  • Modify the run method so that it can detect when the last line
  of input has been found, and set this.done to false so that the loop
  terminates. The BlockingQueue interface does not
  have a special close message that you can send, you'll have to find
  a way to construct your own.
    • 
  
  • Filter is an abstract class designed to be extended by classes
  representing specific commands; for example, a grep class. In each
  child class, you'll need to implement the abstract transform
  method. You will need some additional methods or other techniques
  (for example, for skipping some lines as grep must do).
    • 




You will also need special versions of Filter for the first and
last commands in a chain. That is, cat only outputs but accepts no
piped input, and you also need a final command in the chain which is
not explicitly given on the command line to send the output either to
the console or to a file. One way to accomplish this is by setting
either the input or output queues to null in a child class
constructor. For example:





ShellSink.java


import java.util.concurrent.*;

public class ShellSink extends Filter {
    public ShellSink(BlockingQueue in) {
        super(in, null);
    }
    
    protected Object transform(Object o) {
        // get the string message from o and print it
        return o;
    }
}




    
  
  • Note that in orer to use ShellSink as defined above, you will
  need to modify Filter so that it doesn't try to read from a null
  BlockingQueue.
    • 




In addition to implementing the commands, you also need to write a
parser that transforms text that the user enters at
the REPL into threads
that can be
started. Scanner
is a good choice for reading lines of text from System.in. You may
wish to
use String.split
to help with this task.



Compiler Warnings



The ArrayBlockingQueue class makes use of generic
programming. Generic programming is a metaprogramming technique
that allows the compiler to customize source code to use specific
types at compile-time instead of runtime. Some of you may be familiar
with generic programming from the templating facility in C++.



You do not need to understand generic programming
to do this assignment. However, your compiler may give you a warning
that looks like this:



  Note: Some input files use unchecked or unsafe operations.
  Note: Recompile with -Xlint:unchecked for details.




You can ignore these warnings for now. If you have
used generic programming techniques before, feel free to fix the
templates so that the ArrayBlockingQueue objects are specialized for
whatever object you want to pass through them.



Sample Input and Output



Because your REPL
reads input from System.in, you can use input redirection on your
system's command line (not the command line you
implement in your Java program's REPL) to send a series of commands all at once, making
testing a lot easier. Assuming that your main method is found in class
Project1, you can load commands from a file called
"commands.txt" like this:



  java Project1 < commands.txt




The input will not appear, just the output. That is okay. Following
is a sample file of test commands and another file showing the correct
output. Important note: just because your program
works on this test file does not mean you are necessarily done. You
should write your own tests and submit them as part of your
project. We will test other cases besides what is in this file.



Commands File



    
  
  • A command file with some example
  commands: commands.txt.
    • 
  
  • What the output from running this command file should look
  like: output.txt.
    • 



You should enter these commands at least once by hand so that you can
see what they look like when a user enters them; they are hard to read
in the output file because the command input is not shown.


Where to Get More Help



You should reference your textbook and the lecture slides about
threads. You may also find
this tutorial
helpful.






  COSI 31a ::
  Brandeis University ::
  Computer Science Department