VE482-Project 1 Solved

 

1          A tough life…
As you are comfortably sleeping in your soft bed, your alarm clock loudly rings and wakes you up. Already 11 AM… It would be good to sleep a bit longer but you already hear your mum stepping in the room and widely opening the curtains. As you are blinded by the sudden burst of light you start grumbling, but she is not even paying attention to you and just says: “I told you to sleep instead of playing video games all night long! You’ve graduated two months ago and you haven’t found job yet!” The head under your pillow to protect yourself from the light you simply ignore her and start smiling as you think of last year at the same period when you had to wake up early to attend ve477 lectures. But luckily now you are home and you can sleep, so why not enjoying it? As you start to fall asleep again, she admonishes you “Wake up lazy kid! Time for you to to find a job!”

“But mum, I have already sent two CVs last week? What else do you want me to do?” you try to argue.

“What do I want you to do? Hum…I want you to start doing something with your life! If you don’t want to find a job then you’ll work here!” she orders you.

As she carries on you simply look at her disconcerted. “Yes, I found some exercises for you: you’re going to implement a shell,” and she punctuates with an ironic smile.

Totally speechless, you look at her wondering how come she knows what a shell is.

As she approaches from your bed she hands in a couple of pages to you just saying “Lets work begin!

And be sure that I’ll check on your regularly…”

While you regain your composure you manage to articulate “I’m already very busy playing video games!”

To what she firmly replies “Not anymore you’ll be busy implementing a shell!” Then she quits the room, leaving you puzzled and bitter. Why has not Lemonion call you already for an interview, you had the perfect profile? Now you are here lying in your bed with a couple of pages entitled The mumsh shell.

2          The mumsh shell
The main task of a shell is to wait for some user input, parse it and execute a command requested by the user. It should also provide support for input/output redirection and pipelining from a program into another one.

A shell simply consists of a loop that parses the user input. When waiting the shell displays a prompt, here we want our shell to display “mumsh $ ”.

When a command is input by the user it should be launched in a new process and the shell should block, waiting for the command to end.

A command line is composed of a command followed by some arguments. Arguments are space separated. The shell should exit when the user inputs exit. In case of error, such as when a command that does not exists is input, the shell should output an error on the standard error output (e.g. Error: no such file or directory).

The shell can be tested by comparing its behaviour to the result of the same commands in the regular Linux shell (e.g. sh, bash, zsh). Note that those commands are only for testing purpose, therefore they are far from being optimal and do not encompass all the features that need to be implemented.

 

The mumsh shell is expected to be running in both Linux and Minix 3.

Hints:

•     Useful system calls: fork(), execvp(), wait/waitpid(), dup2/dup(), pipe() and close().

•     A command line is not expected to be longer than 1024 characters.

•     The use of the command system or of lex and yacc is prohibited.

3          Mum’s Grading policy
Your mother has decided that you should follow a total of thirteen requirements, some with sub-tasks.

For each requirement the awarded marks are display in bold into square brackets.

Important notes:

•     In case of a final grade larger than 100, the extra marks will be saved for a bonus;

•     A 50% penalty will be applied if commands are not launched in a new process;

•     Any work that is not pushed onto the git server will be ignored;

•     An issue should be opened for each task, and there should be at least one commit to the git server per task completed (more are recommended);

•     Any task that does not exit cleanly, has memory leaks, or undefined behaviors will receive a −10% deduction;

•     The shell should only output normal characters (e.g. no escape characters such as \033 to handle color);

In the following description “requirement x” stands for requirement x, including all its sub-tasks, if any. A requirement having dependencies is considered completed if and only if it is completed together with all it’s dependencies.

1.        Write a working read/parse/execute loop and an exit command; [5]

2.        Handle single commands without arguments (e.g. ls); [5]

3.        Support commands with arguments (e.g. apt-get update or pkgin update); [5]

4.        File I/O redirection: [5+5+5+2]

4.1.         Output redirection by overwriting a file (e.g. echo 123 > 1.txt);

4.2.         Output redirection by appending to a file (e.g. echo 465 >> 1.txt);

4.3.         Input redirection (e.g. cat < 1.txt);

4.4.         Combine 4.1 and 4.2 with 4.3;

5.        Support for bash style redirection syntax (e.g. cat < 1.txt 2.txt > 3.txt 4.txt); [8]

6.        Pipes: [5+5+5+10]

6.1.         Basic pipe support (e.g. echo 123 | grep 1);

6.2.         Run all ‘stages’ of piped process in parallel. (e.g. yes ve482 | grep 482);

6.3.         Extend 6.2 to support requirements 4. and 5. (e.g. cat < 1.txt 2.txt | grep 1 > 3.txt);

6.4.         Extend 6.3 to support arbitrarily deep “cascade pipes” (e.g. echo 123 | grep 1 | grep 1 | grep 1)

Note: the sub-processes must be reaped in order to be awarded the marks.

7.        Support CTRL-D (similar to bash, when there is no/an unfinished command); [5]

8.        Internal commands: [5+5+5]

8.1.         Implement pwd as a built-in command;

8.2.         Allow changing working directory using cd;

8.3.         Allow pwd to be piped or redirected as specified in requirement 4.;

9.        Support CTRL-C: [5+3+2+10]

9.1.         Properly handle CTRL-C in the case of requirement 4.;

9.2.         Extend 9.1 to support subtasks 6.1 to 6.3;

9.3.         Extend 9.2 to support requirement 7., especially on an incomplete input;

9.4.         Extend 9.3 to support requirement 6.;

10.     Support quotes: [5+2+3+5]

10.1.     Handle single and double quotes (e.gm. echo "de'f' ghi" '123"a"bc' a b c);

10.2.     Extend 10.1 to support requirement 4. and subtasks 6.1 to 6.3;

10.3.     Extend 10.2 in the case of incomplete quotes (e.g. Input echo "de, hit enter and input cd");

10.4.     Extend 10.3 to support requirements 4. and 6., together with subtask 9.3;

11.     Wait for the command to be completed when encountering >, <, or |: [3+2]

11.1.     Support requirements 3. and 4. together with subtasks 6.1 to 6.3;

11.2.     Extend 11.1 to support requirement 10.;

12.     Handle errors for all supported features. [10]

Note: a list of test cases will be published at a later stage. Marks will be awarded based on the number of cases that are correctly handled, i.e. if only if:

•     A precise error message is displayed (e.g. simply saying “error happened!” is not enough);

•     The program continues executing normally after the error is identified and handled;

13.     A command ending with an & should be run in background. [10]

13.1.     For any background job, the shell should print out the command line, prepended with the job ID and the process ID (e.g. if the two lines /bin/ls & and /bin/ls | cat & are input the output could be the two lines [1] (32757) /bin/ls & and [2] (32758) (32759) /bin/ls | cat & );

13.2.     Implement the command jobs which prints a list of background tasks together with their running states (e.g. in the previous case output the two lines [1] done /bin/ls & and [2] running /bin/ls | cat &);

4          Mum’s schedule
As your mother wants to closely monitor you and ensure you do not play video games in secret instead of working on her shell she has decided to enforce a tight schedule:



Final shell: fully functional shell;

It seems your mother has thought of everything, she has even organised to setup an Online Judge to verify that you are respecting the milestones; To show you she is willing to be flexible she allows you to be reasonably late for the milestones as long the final submission in completed on time. More precisely m1 can be submitted until the deadline of m2, and m2 until the final deadline. Each missed deadline will incur a −30% deduction on the final project grade. Besides for m1 and m2 passing between 25% and 50% of the test cases will lead to −10%, and −20% if less than 25% of the test cases are passed.

Feeling resigned you decide to follow her advice, so you grab your computer and start working in your bed thinking it makes a very comfortable desk…