9
\$\begingroup\$

I am learning C and therefore decided to build my own, little shell. Currently I am concerned with input parsing. I want to split a line of text into tokens with delimiters. But it should be possible to escape the delimiter.

A simple example would be:

Input: "echo Hello World"
Output: [echo, Hello, World] with n=3 tokens

Input: "echo "Hello World""
Output: [echo, "Hello World"] with n=2 tokens

My current solution seems to work. But because I am coming from Python I fear to miss something out (e.g. memory leak or pointer error).

I appreciate any sorts of feedback (style, comments, performance, etc).

NOTE: The methods str_list_cat and print_2D are only debugging methods. I am mainly concerned about tokenize.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUF_SIZE 2
#define NEWLINE '\n'

/**
 * Read user input from STDIN.
 *
 * Stores the input into a self growing buffer.
 */
char *read_line()
{
    int buf_size = BUF_SIZE;
    int cur_index = 0;
    char cur_char;
    char *buffer = malloc(buf_size * sizeof(char));

    /* Could not allocate enough memory */
    if (buffer == NULL)
    {
        return NULL;
    }


    /* Store the input char by char */
    while (1)
    {
        cur_char = (char) getchar();
        /* Line end reached. Store tailing 0x0 byte and break */
        if (cur_char == EOF || cur_char == NEWLINE)
        {
            buffer[cur_index] = '\0';
            return buffer;
        }

        buffer[cur_index++] = cur_char;

        /* Reallocate memory if the buffer is full */
        if (cur_index >= buf_size)
        {
            buf_size += BUF_SIZE;
            buffer = realloc(buffer, buf_size);
            if (buffer == NULL)
            {
                return NULL;
            }
        }
    }
}

/**
 * Copy of Python's input() method.
 * Asks the user for input with a variable question.
 */
char *input(const char *q)
{
    printf("%s", q);
    char *input = read_line();
    return input;
}


/**
 * Concat a list of strings to a single string and place a delimiter between each substring.
 */
char *str_list_cat(char **strings, char delimiter)
{
    int buf_size = BUF_SIZE;
    int cur = 0;
    int pos;
    int total = 0;
    char cur_chr;
    char *str;
    char *string = malloc(buf_size * sizeof(char));

    /* Memory error */
    if (string == NULL)
    {
        return NULL;
    }

    /* Iterate over string char by char */
    while ((str = strings[cur++]) != NULL)
    {
        pos = 0;
        while (1)
        {
            cur_chr = str[pos++];
            /* Place the delimiter between the strings*/
            if (cur_chr == '\0')
            {
                string[total++] = delimiter;
                break;
            }

            /* Store the current char */
            string[total++] = cur_chr;
            if (total >= buf_size)
            {
                buf_size += BUF_SIZE;
                string = realloc(string, buf_size * sizeof(char));
                if (string == NULL)
                {
                    return NULL;
                }
            }
        }
    }
    /* Override the previous char to remove a tailing delimiter. */
    string[--total] = '\0';
    return string;
}

/**
 * Tokenize a line of text.
 * Supported delimiters: Space (' ') and Tab ('\t')
 * Escape character: Quote (")
 *
 * Return: A 2D array of tokens, each with variable width.
 */
char **tokenize(const char *line)
{
    /* Buffer sizes for both the current token and the list of tokens */
    int token_buf_siz = BUF_SIZE;
    int tokens_buf_size = BUF_SIZE;

    /* Variables for iterating over line */
    char cur_chr;

    int cur = 0, escaped = 0;
    /* Number of chars in current token */
    int tok_pos = 0;

    /* Total number of token */
    int tot_tok_num = 0;

    /* Buffers */
    char *token = malloc(token_buf_siz * sizeof(char));
    char **tokens = malloc(tokens_buf_size * sizeof(char *));
    if (tokens == NULL || token == NULL)
    {
        return NULL;
    }

    /* Iterate over line char by char */
    while ((cur_chr = line[cur++]) != '\0')
    {
        /* Check for unescaped delimiters */
        if ((cur_chr == ' ' || cur_chr == '\t') && !escaped)
        {
            if (tok_pos == 0)
            {
                /* Skip duplicate delimiters */
                continue;
            }

            /* Store the token and grow buffer if necessary */
            tokens[tot_tok_num++] = token;
            if (tot_tok_num >= tokens_buf_size)
            {
                tokens_buf_size += BUF_SIZE;
                tokens = realloc(tokens, tokens_buf_size * sizeof(char *));
                if (tokens == NULL)
                {
                    return NULL;
                }
            }

            /* Reset the token vars and allocate new space */
            token[tok_pos] = '\0';
            tok_pos = 0;
            token_buf_siz = BUF_SIZE;
            token = malloc(token_buf_siz * sizeof(char)); // IMPORTANT: Don't forget to free the old tokens later on
            if (token == NULL)
            {
                return NULL;
            }
            continue;
        }

        if (cur_chr == '\"')
        {
            /* Enter/Leave escape mode */
            escaped = 1 - escaped;
        }

        /* Store the char and grow buffer if necessary */
        token[tok_pos++] = cur_chr;
        if (tok_pos >= token_buf_siz)
        {
            token_buf_siz += BUF_SIZE;
            token = realloc(token, token_buf_siz * sizeof(char));
            if (token == NULL)
            {
                return NULL;
            }
        }
    }
    if (tok_pos)
    {
        if (escaped)
        {
            /* Catch unclosed escape sequence */
            token[tok_pos] = '\0';
        }
        /* Copy the last token if it exists */
        tokens[tot_tok_num++] = token;
        if (tot_tok_num >= tokens_buf_size)
        {
            tokens_buf_size += BUF_SIZE;
            tokens = realloc(tokens, tokens_buf_size * sizeof(char *));
            if (tokens == NULL)
            {
                return NULL;
            }
        }
    }
    tokens[tot_tok_num] = NULL;
    return tokens;
}

/**
 * Free a 2D array of strings
 */
void free_2D(char **arr)
{
    char *s;
    int cur = 0;
    while ((s = arr[cur++]) != NULL)
    {
        free(s);
    }
    free(arr);
}

void print_2D(char **tokens)
{
    printf("%s\n", str_list_cat(tokens, ','));
    free_2D(tokens);
}

int main()
{
    /* Test */
    print_2D(tokenize("echo Hello World"));
    print_2D(tokenize("echo \"Hello World\""));
    print_2D(tokenize("echo        \"Hello          World\"     "));
    print_2D(tokenize(""));
    print_2D(tokenize("\"\""));
    print_2D(tokenize("         "));
    print_2D(tokenize("echo 1          äöü "));
    print_2D(tokenize("\"touch index.html;"));
    print_2D(tokenize("\ttttttttt sdf \t"));
    print_2D(tokenize("cat text.xml | grep foo.bar"));
    return 0;
}
```
\$\endgroup\$
  • 3
    \$\begingroup\$ C is not a good languages to express lexemes with. Might be an idea to look at "Lex" as a language. You can probably express these rules with about 3 lines of "Lex" code. \$\endgroup\$ – Martin York Jan 26 at 18:24
  • 2
    \$\begingroup\$ Welcome to Code Review! I have rolled back your last edit. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Heslacher Jan 27 at 10:33
1
\$\begingroup\$

For future reference:

  1. Debug code should be embedded in

    #ifdef DEBUG
    #endif
    
  2. Having live debug code in the program means the code is not ready for code review.

  3. Having unused functions such as char *input(const char *q) means the code is not ready for code review.

Performance

Shells provide the user interface for the operating system; they need to be very fast, therefore character by character input and multiple memory reallocations are not the best way to achieve good performance in shells. The functions malloc() and realloc() are slow because they make system calls to allocate the memory; programs making system calls can be swapped out during the system call depending on system resources and usage. These calls should be minimized when speed is important. Single character input is also slow; reading the full input buffer is much faster, and string manipulation is much faster than input as well.

The C library provides an excellent function to get a line of input from the terminal; this function is fgets(char* buffer, size_t buffer_size, FILE *stream). The function fgets() could basically replace the function char *read_line(). The standard include file <stdio.h> provides a symbolic constant for input buffer sizes; this constant is BUFSIZ and it is defined as the most optimal size for getting input on your operating system. So to replace read_line() properly:

char *input(const char *q)
{
    printf("%s", q);
    char input_buffer[BUFSIZ];
    int number_of_chars_read = fgets(input_buffer, BUFSIZ, stdin);
    if (number_of_chars_read > 0)
    {
        return strdup(input_buffer);
    }

    return NULL;
}

Prior to May 2019, strdup(char *str) was not totally portable, but in May of 2019 it was added to the C programming standard.

The function fgets() properly handles EOF and newlines.

Complexity

Functions the size and complexity of char **tokenize(const char *line) are very hard to read, write, debug and maintain. I've had managers that considered any function larger than 10 lines of code to be too big, but I don't quite agree with that; any function that is more than one screen in an editor should be considered too big and too complex. There are a couple of programming principles that apply here: the Single Responsibility Principle and the KISS principle.

The KISS principle is "Keep It Simple", and applies to more than just software development.

There is also a programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

Following this principle, the function char **tokenize(const char *line) should call multiple functions to implement the tokenization.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I disagree with "malloc and realloc are slow because they make system calls". They usually use more intelligent algorithms than just a simple mmap per allocation. For example, on NetBSD, calling malloc(100) a million times results in only 117 mmap system calls. \$\endgroup\$ – Roland Illig Jan 26 at 20:55
  • \$\begingroup\$ There's no point in char *input = strdup(input_buffer); return input;; just return strdup(input_buffer);. Also, any C standard past C11 has not been standardized yet and probably won't even be fully implemented until two years past its standardization date. \$\endgroup\$ – S.S. Anne Jan 27 at 1:48
  • \$\begingroup\$ BUFSIZ is meant to notify how many characters are available in the buffers of a FILE * stream, not as a user buffer. \$\endgroup\$ – S.S. Anne Jan 27 at 1:49
  • 2
    \$\begingroup\$ @Leonleon1 You should always use library functions if you can instead of reimplementing them yourself. That's what they're for. \$\endgroup\$ – S.S. Anne Jan 27 at 12:09
  • 1
    \$\begingroup\$ It's an exaggeration to say that "programs making system calls are swapped out during the system call"; that's unlikely on a modern platform that has demand paging and/or enough RAM to keep its processes in memory. I'd change that "are" to "could be", at most. \$\endgroup\$ – Toby Speight Jan 28 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.