DEV Community: harsh banthiya

Writing my own minimal shell in C - Part 3(The parsing process leading to an execution tree)

harsh banthiya — Wed, 06 Oct 2021 17:45:19 +0000

The Parsing Process

Let's try to put a mental model of how the entire command line string needs to be parsed and what are the various modules we might require along the way.

Scanner -> Parser -> Executer -> Command
Token_list -> Abstract Syntax Tree -> Convert to Execution Unit -> Execute-Execute

The Tentative Process:

Get the whole string until new line using read_line library.
Search the string from index 0 until '\0' for ('')
Divide string in tokens based on whitespace
- it can be any amount of whitespaces, abcd efgh or abcd efgh; They should both make two tokens.
- whitespace cannot be included in token characters except when there are double or single quotes. ** "hello world" is one token hello world ** "" hello world "" is two tokens hello and world; and the empty string before and after hello world will not be tokenized. ** "'hello world'" -- A single quote inside a double quote will be included in the token, so the result will be one token called 'hello world'; All the above rules apply to single quotes as well.
After dividing the tokens, if there is a token with a $ sign, whatever comes after the $ sign is compared with the list of all the env variables available and replaced with the value of the said variable. ** Important sub-point - In case of a string in single quote, even if there is a $ sign, it is not replaced with the value of the said env variable.
Environment variables are received using envp parameter from the main function and stored in a key value structure t_env and put in a linked list.

Converting stuff into an Abstract Syntax Tree.

A scanner will scan through the string and make a list of tokens based on the rules, we listed above.
A parser takes that list of tokens verifies the syntax (represents an error if there is a syntax error), and converts it into a tree structure.

Lets try to build the schematics top down:

----- Command line -----
Job ; command line ; job
(Identify command line (unparsed line) as either a formed job or a combination of jobs and unparsed command_lines)

----- Job ------
Command | job ; command
(Identify a job as a command or another job in a list)

---------- Command ----
simple_command redirection list simple_command
(Identify a command as either a simple command or a redirection list )

---------- Redirection List ----
redirection redirection_list

----------- Redirection ------
filename < filename >> filename

---------- Simple_Command -------
pathname token_list

----------- Token_List --------
token token_list

For example:
cat > a > b < c should end up as:

          command
         /        \
  simple cmd      redirection
  /                      \ 
cat                        >
                          /  \
                       aaaa   >
                             /  \
                          bbbb   <
                                 /
                               cccc

          (hold)
        /        \
   cat            >
                 /  \
              aaaa   >
                    /  \
                 bbbb   <
                       /
                    cccc

          (hold) 
        /        \
   cat            aaaa (type : NODE_REDIRECT_IN)
                    \
                    bbbb (type: NODE_REDIRECT_IN)
                      \
                      cccc (type: NODE_REDIRECT_OUT)

The tree could finally evaluate to Abstract Tree

       aaaa (type : NODE_REDIRECT_IN)
      /      \
    cat       bbbb (type: NODE_REDIRECT_IN)
                 \
                 cccc (type: NODE_REDIRECT_OUT)

Let's breakdown the logic of the above command tree:

We identify command as one of two structures:

Simple_command and redirection_list structures
Simple_command structure.
In case of simple command

First we check if it is simple_command
** We check the token_list with pathnames
** If it just one token we check once but it is a list we check each one.

In case of redirection list

** We check if it just one redirection or a list.
** We attach one case ( <, >, <<, >>) and attach the filename information, create a node and add it to the list.

Writing my own minimal shell in C - Part 2 (The Builtin Functions and general interpretation)

harsh banthiya — Wed, 06 Oct 2021 15:23:00 +0000

DAY 2 - Understanding the scope of each builtin

Quick recap of the builtin functions that we need to make

echo with the option -n
cd with only a relative or absolute path
pwd without any options
export without any options
unset without any options
env without any options and any arguments
exit without any options

cd function

cd can be used with these characters and the sequence matters.

" . " - indicates the current folder.
" .. " - indicates the parent folder.
" ~ " - indicates the absolute path to the user.
" / " - indicates separation between folders.

" ~ " can only be entered as the first argument to cd

cd ~ (this is okay)
cd ./~ (this won't work)
cd dir/~ (this won't work)

" / " it can be used as a separator between folders.

cd srcs/ (this is okay)
cd ../ (this is okay)
cd /srcs (this won't work)

Functions required to write cd function

getcwd - Get the current path
chrdir - if you put a path in chdir, it moves to that path

Handling Quotes

Constraint as discussed over quote handling

' inhibit all interpretation of the following sequence of characters.
" inhibit all interpretation of the following sequence of characters expect for $

Understanding Quotes and how they behave

Double quotes must be closed whenever you open one.
But if you open with a single quote and close with a single quote, any number of double quotation marks can be inserted between them.
Similarly if you open with double quotes and close with double quotes, any number of single quotes can be inserted between them.

Valid quote handling for us includes

" "
" ' "
' '
' " '

Invalid quote handling for us includes

"
'
" " '
' ' "
' " "
" ' '
' ' '
" " "

Lets look at quotes between executable and variables

Valid quote handling includes:

echo "abc"
echo "a"bc
echo "ab"c
echo ""abc
echo abc""
ech"o" abc
echo"" abc
""echo abc
"echo" abc
"echo""" abc

Invalid quote handling includes:

echo" abc
echo a"bc
echo" a"bc
echo" "abc
ech"o "abc
"echo abc"

echo function

Execute echo command with or without args
Repeat with other arguments
Restart the shell once done
If there is conflict, use the conflict flag
if something doesn't work, use the incomplete flag

exit function

Execute with or without args
exit shell
same use a conflict flag, incase of a conflict
if something doesn't work, use a incomplete job flag

env function

display current env variables

export function

Export environment variables, create new ones and replace old ones
export without options prints a list of env variables
check with env

unset function

remove environment variables using unset
check with result in env

Other Basic information to be aware of

Simple commands and global

Shell must be good with simple commands, and commands like /bin/ls and no options
Test for when empty command line is inserted.
Test with inserting spaces and tabs at random points
If something is colliding use a conflict flag
If something doesn't work, use the incomplete flag.

Arguments and History

Must be able to execute simple commands with an absolute path such as /bin/ls with args. Without single and double quotes.
Repeat with each command and argument
Use relevant flags for conflict and incomplete.

Return value of a process

To mimic the working of $?, execute a simple command with an absolute path or any other command with args but without quotes and double quotes then execute echo $?
Now try something similar as above but with single quotes and double quotes and check echo $? after that
Try commands that will fail like bin/ls nonexitantfile and see the value of $?
Maybe try $? + $?

Signals

ctrl-c : SIGINT
ctrl-\ : SIGQUIT
ctrl-c : Stop execution with an interrupt signal from the keyboard
ctrl-\ : A stop signal from keyboard, which terminates the process and dumps the core.
- Pressing ctrl-c at an empty prompt should create newline
- If you hit ctrl-\ at the empty prompt, nothing should happen
- Press ctrl-d at an empty prompt to close the shell
- After writing a few things, press ctrl-c to show a new prompt line
- After writing a few things, press ctrl-d, nothing happens
- after writing a few things, press ctrl-\ to turn off the shell
- Block ctrl-c, ctrl-d, ctrl-\ while cat or grep is running.
Incase of conflict, use conflict and incase it doesn't work use the incomplete flag.

Single Quotes

Try an empty parameter
Test with env variables, whitespace, pipes and redirects.
'%USER' should print $USER

Relative Path

Repeat with multiple directories with complex relative paths
Set $PATH to a multiple directory value(dir1:dir2) and check those directories in left to right order.

Next up, Lets try to find the relevant modules to fit all this information and to inbuilt checks at the right spots and the general flow of entire shell.

Always revisit this page when in doubt; The Basics of UNIX philosophy.

harsh banthiya — Mon, 04 Oct 2021 14:08:19 +0000

The basics of Unix Philosophy

It all began with Thompson's efforts on how to design a small but capable operating system with a clean interface.

The Unix philosophy is bottom up, not top down.

Doug McIlroy ( the inventor of Unix Pipes ) said:
- Make each program do one thing well. To do a new job, build afresh rather than trying to complicate old programs.
- Design and build software to be tried early, don't hesitate to throw away clumsy parts and rebuild them.
- Use tools in preference to unskilled help to lighten programming task. Even if you have to detour to build the tools and expect to throw some of them out after you've finished them.

This is the Unix philosophy, write programs that do one thing and they do it well. Write programs to work well together. Write programs to handle text streams, because that is the universal interface.

Rules for the Unix tribe, from Rob Pike (Notes on C Programming)

You cannot tell where a program is going to spend its time. Bottlenecks occur in surprising places, so don't try to second guess and put in a speed hack until you've proven that's where the bottleneck is.
Measure. Don't tune for speed until you've measured, and even then don't unless one part of the code overwhelms the rest.
Fancy algorithms are slow when n is small, n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy. (even when n get big, use Rule 2 first)
Fancy algorithms are buggier than simple ones, and they're much harder to implement. Use simple algorithms and simple data structures.
Data dominates. If you've chosen the right data structures and organized things well, the algorithms are almost always self evident. Data structures and not algorithms are central to programming.
There is no Rule 6.

Similarly there are a few Unix Philosophy implied rules, let's look at them.

Rule of Modularity: Write simple parts connected by clean interface.

"Controlling complexity is the essence of Computer Programming", Debugging dominated development time and getting a working system out of the door is usually less a result of brilliant design than it is of managing not to trip over your own feet too many times.

Rule of Clarity: Clarity is better than cleverness.

Because maintenance is so important and expensive, write programs as if the most important communication they do is not with the computer that executes them but to the humans who will read and maintain the source code in the future (including you).

Thats doesn't just mean comments, it also embraces choosing your algorithms and implementations for future maintainability. Buying a small increase in performance with a large increase in complexity and obscurity of your technique is a bad trade.

Rule of Composition: Design programs to be connected with other programs.

Unix tradition strongly encourages writing programs that read and write simple, textual, stream-oriented, device independent formats. Under classic Unix, as many programs as possible are written as simple filters, which take a simple text stream on input and process it into another simple text stream on output.

To make programs composable, make them independent. A program on one end of a text stream should care as little as possible about the program on the other end. It should be easy to replace one end with a completely different implementation without disturbing the other.

Rule of Separation: Separate policy from mechanism; separate interfaces from engines.

Policies are ways to choose which activities to perform, Mechanisms are implementations that enforce policies. Policy and Mechanisms mutate on different timescales, with policy changing much faster than mechanism.
Thus, hardwiring policy and mechanism together has two bad effects; it makes policy rigid and harder to change in response to user requirements, and it means that trying to change policy has a strong tendency to destabilize the mechanisms.

Rule for Simplicity: Design for simplicity, add complexity only where you must.

No need for technical machismo. Programmers are bright people who are (often justly) proud of their ability to handle complexity and juggle abstractions. Often they compete with their peers to see who can build the most intricate and beautiful complexities. Their ability to design outstrips their ability to implement and debug and the result is an expensive failure.

Rule of Parsimony: Write a big problem only when it is clear by demonstration that nothing else will do.

'Big' here has the sense of both large in volume of code and of internal complexity. Allowing programs to get large hurts maintainability. Because people are reluctant to throw away the visible product of lots of work, large programs invite over-investment in approaches that are failed or suboptimal.

Rule of Transparency: Design for visibility to make inspection and debugging easier.

Debugging occupied three quarters or more of our development time. A system is transparent when you can look at it and immediately understand what it is doing and how. It is discoverable when it has facilities for monitoring and display of internal state so that your program not only functions well but can be seen to function well.

Designing these qualities have implications from the very beginning. At minimum, it implies that it must use simple interfaces, that can be easily manipulated by other programs - in particular, test and monitoring harnesses and debugging scripts.

Rule of Robustness: Robustness is the child of transparency and simplicity.

Software is robust when it performs well under unexpected conditions which stress the designer's assumptions, as well as normal conditions.

One very important tactic for being robust under odd inputs is to avoid having special cases in your code. Here is another way to make simple and robust software.

Rule of Representation: Fold knowledge into data, so program logic can be stupid and robust.

Even the simplest procedural logic is hard for humans to verify. Data is more tractable than program logic. It follows that where you see a choice between complexity in data structures and complexity in code, choose the former. In evolving a design, you should actively seek ways to shift complexity from code to data.

Rule of Least Surprise: In interface design, always do the least surprising thing.

The easiest programs to use are those that demand the least new learning from the user, or to put in another way, the easiest programs to use are those that most effectively connect the user's pre-existing knowledge. Well designed programs treat the users attention and concentration as a precious and limited resource, only to be claimed when necessary.

Rule of Repair: Repair what you can - but when you must fail, fail noisily and as soon as possible.

Yes it is best when software can cope with unexpected conditions by adapting to them, but the worst kind of bugs are those in which repair doesn't succeed and the problem quietly causes corruption that doesn't show up until later.

"Be liberal in what you accept, but conservative in what you send." Well-Designed programs co-operate with other programs by making as much sense as they can from ill-formed inputs; they either fail noisily or pass strictly clean and correct data to the next program in the chain.

Rule of Economy: Programmer time is expensive; conserve it in preference to machine time.

In older days, machines were slower and much expensive; Now however we can make use of cheap machine cycles now. Code in higher level languages, ease programmer's burden by letting languages do their own memory management.

The obvious way to conserve programmer time is to teach machines how to do more of the low level work of programming.

Rule of Generation: Avoid hand-hacking; write programs to write programs when you can.

Human beings are notoriously bad at sweating the details. Any kind of hand hacking is rich source of delays and errors. Generated code (at every level) is almost always cheaper and more reliable than hand-hacked. That's why we have compilers and interpreters. It pays to use code generators when they can raise the level of abstractions - that is when the specification language for the generator is simpler than the generated code.

Rule of Optimization: Prototype before polishing. Get it working before you optimize it.

"90% of functionality delivered now is better than 100% of it delivered never"; premature optimization before the bottlenecks are known is only error to have ruined more designs than feature creep. Often local premature optimization, hinders global optimization. "Make it run, then Make it run right, then make it fast."

Rule of Diversity: Distrust all claims for "one true way"

Even the best software tools tend to be limited by the imaginations of their designers. Nobody is smart enough to optimize for everything, nor to anticipate all the uses to which their software might be put. Embrace multiple languages, open extensible systems and customization hooks everywhere.

Rule of Extensibility: Design for future, because it will be here sooner than you think.

If it is unwise to trust other people's claims for "one true way", it is even more foolish to believe them about your own designs. Never assume you have the final answer. Therefore, leave room for your data formats and code to grow, otherwise you are locked with unwise early choices because you cannot change them while maintaining backward compatibility.

When you design protocols or file formats, make them sufficiently self describing to be extensible. Always, always either include a version number, or compose the format from self contained, self describing clauses in such a way that new clauses can be readily added and old ones dropped without confusing format reading code.

When you design code, organize it so future developers will be able to plug new functions into the architecture without having to scrap and rebuild the architecture. Put in the "if you ever need to ... " comments.

When you design for the future, the sanity that you save may be your own.

Writing my own minimal shell in C - Part 1 (The constraints)

harsh banthiya — Sun, 03 Oct 2021 21:38:52 +0000

Day 1 - Understanding the Problem.

This is my attempt to replicate the behavior of BASH or (Bourne again shell) command line interpreter for a school project. Before we get into how to get into the solution and the general approach of making the shell. Let's first look at all the constraints and what is expected from this minimal shell.

First and foremost, standard library functions I am allowed to use.

Below is the list of the external functions / standard library functions that I am allowed to use, if I need any another function I must code it myself. Please see the man pages of these functions if you do not recognize them.

readline, rl_clear_history, rl_on_new_line, rl_replace_line, rl_redisplay, add_history, printf, malloc, free, write, access, open, read, close, fork, wait, waitpid, wait3, wait4, signal, sigaction, kill, exit, getcwd, chdir, stat, lstat, fstat, unlink, execve, dup, dup2, pipe, opendir, readdir, closedir, strerror, perror, isatty, ttyname, ttyslot, ioctl, getenv, tcsetattr, tcgetattr, tgetflag, tgetnum, tgetstr, tgoto, tputs

Expectations from the shell, what must this minimal shell do

It must implement the builtin shell functions
- echo with the option -n
- cd with only a relative or absolute path
- pwd with no options
- export with no options
- unset with no options
- env with no options or arguments
- exit with no options
Redirections
- < should redirect input
- > should redirect output
- << read input from the current source until a line containing only the delimiter is even.
- >> should redirect output in append mode.
Pipes
- | The output of each command in the pipeline is connected via a pipe to the input of the next command
Environment Variables ($ followed by characters ) should expand to their values.
$? should expand to the exit status of the most recently executed foreground pipeline
For some simplification, the shell must not interpret unclosed quotes or unspecified special characters like '\' or ';' etc
The shell must show a prompt waiting for next command, have a working history and must only use one global variable.
ctrl-C ctrl-D ctrl-\ should work like bash. When interactive:
- ctrl-C print a new prompt on a newline
- ctrl-D exit the shell.

Lets begin researching the problems and the areas of Operating System I am less familiar with, in the next part of this series I will break down the general overview of the design and I will try to make it super modular.