Line wrapping text utility using fixed-size arrays

Question

As an exercise, I've made a text processing utility that wraps arbitrarily long lines of text, but only using fixed-size arrays and other basic C features.

I have mostly programmed in Python, C++ and Java so far, and I recently picked up K&R (second edition) to learn some C. I have only gone through the first chapter so far, which is "A Tutorial Introduction". At the end of this chapter, the last paragraph says:

At this point we have covered what might be called the conventional core of C. With this handful of building blocks, it's possible to write useful programs of considerable size, and it would probably be a good idea if you paused long enough to do so. These exercises suggest programs of somewhat greater complexity than the ones earlier in the chapter.

Since I have quite a bit of time on my hands, I took this "challenge" quite literally: I set out to solve the exercises strictly using only the language features shown in that chapter.

One of these exercises (exercise 1-22) reads:

Write a program to "fold" long input lines into two or more shorter lines after the last non-blank character that occurs before the \$n\$-th column of input. Make sure your program does something intelligent with very long lines, and if there are no blanks or tabs before the specified column.

Probably the best way to deal with arbitrarily long input lines would be to use dynamically allocated character arrays, but the above restriction implies I can only use fixed-size arrays.

This took quite a bit more time than I was expecting, and the end result works, but the algorithm is a bit of a mess; this is why I'm asking for a code review. My main concern is the correctness of the algorithm and whether it can be made simpler, but anything is welcome. Next up would be possible refactorings, then readability, and then code style, probably.

Specification

Here's my specific interpretation of this exercise:

Make a program that, for each line of input:

• if the line spans a number of columns less than or equal to the maximum line length, print it unaltered;
• alternatively, if it exceeds the limit but it doesn't contain any blank separators, also print it unaltered;
• otherwise, split the line immediately before the last blank separator that occurs before the length limit, or, in its absence, the first blank separator; then:
  1. print the first part
  2. treat the remainder as if it were a new input line (i.e. apply this algorithm recursively)

Definitions

For the purposes of this question, define:

• blank character: either a space or a tab \t character
• blank separator: any sequence of blank characters that comes immediately after a non-blank character (note that this excludes leading space)
• tab size: number of columns between tab stops; fixed at 4
• maximum line length: an arbitrary positive integer that determines the desired maximum number of columns in an output line

Examples

These examples are with the maximum line length (i.e. max columns) set to 10; I've added a vertical bar | at the 11th column just to make it easier to visualize, but this character isn't actually there in the input or output shown below. Also note that , for the last two lines of input, some of the blank characters are tabs.

Input:

aaaaaaaa  |
bbbbbbbbbb|
cccccccccc|ccc
dd dd dd d|d dd dd
eeeeeeeeee|eee eeee
ffffffffff| fffffffff
gggggggggg| ggggggggg gg ggg
hhh hhhhhh|hhhhhhhhhh
    iiiiii| iiii iii
jjjjjj  jj|jjjjjjjjjjjjjjjjjj

Output:

aaaaaaaa  |
bbbbbbbbbb|
cccccccccc|ccc
dd dd dd  |
 dd dd dd |
eeeeeeeeee|eee
 eeee     |
ffffffffff|
 fffffffff|
gggggggggg|
 ggggggggg|
 gg ggg   |
hhh       |
 hhhhhhhhh|hhhhhhh
    iiiiii|
    iiii  |
 iii      |
jjjjjj    |
    jjjjjj|jjjjjjjjjjjjjj

Implementation restrictions

Due to what I've said about only using features seen in the first chapter, I had to reinvent a few wheels. Here is a concrete list of restrictions I followed (which, if you propose any code, you should follow too).

I can only use the following:

• variables, numeric literals, arithmetic expressions, equality operators, boolean operators
• while loop and for loop
• symbolic constants (i.e. #define macros with a constant value)
• getchar and putchar
• printf
• string and character constants
• if statement
• fixed-size arrays
• functions
• character arrays
• external variables (i.e. global variables)

Now, I allowed myself some exceptions that don't significantly alter the challenge, just to make life slightly easier and avoid reinventing too many wheels:

• I can use do-while loops
• I can use strcpy and strlen
• I can use puts
• I can use <stdbool.h>
• I used VLAs to be able to pass the maximum line size as an argument, defining the maximum line length as a global constant (instead of a symbolic constant), which are not technically "fixed-size arrays" (and weren't even a thing when the book was published), but the runtime size of the arrays I use is always the same throughout the lifetime of the program, so I considered this as valid.

My algorithm

This is the algorithm to deal with a single line of input which I ended up implementing. It takes into account that I can only use arrays of a fixed size.

The main idea is to only read at most \$M\$ columns of input at a time, where \$M\$ is the maximum line length, deal with that segment individually, and move on to the next one.

---

Code

One final disclaimer before you go on to read the code. I'm mainly using camelCase as a naming convention. I know this is not conventional in C, but this is only an exercise for myself, so I just picked the naming convention I find the nicest.

Function that implements the algorithm

The function that implements the algorithm above is int readLineAndPrintFolded(const int maxLength, const int tabSize) in the code below, at the very bottom, before main. I recommend you start reading from there—the rest are helper functions and their name pretty much describes what they do.

Complete, runnable code

You can copy and paste this in a text file, compile it under the C99 standard, and run it.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>

const int TAB_SIZE = 4;
const int MAX_LINE_LENGTH = 10;


/**
 * Compute the number of spaces needed to substitute a tab character.
 * @param column – zero-indexed index of the column in which the tab character starts
 * @param tabSize – number of spaces per tab
 * @return the number of spaces that, if inserted in place of a tab character, would
 *         reach the same column as the tab.
 */
int spacesToNextTabStop(int column, int tabSize) {
    return tabSize - (column % tabSize);
}


/**
 * Compute the number of columns spanned by a string.
 * @param string – string of which to compute the column length
 * @param tabSize – number of spaces per tab stop
 * @return the number of columns spanned by a string if printed at the start of a line
 */
int columnLength(const char string[], const int tabSize) {
    int col = 0;
    for (int i = 0; string[i] != '\0'; ++i)
        col += (string[i] == '\t') ? spacesToNextTabStop(col, tabSize) : 1;
    return col;
}


/**
 * Split a string into two segments, discarding the middle
 * If cutFrom or cutTo ar invalid indices, or cutFrom > cutTo, no split is performed.
 *
 * @param string – string to split
 * @param len – length of the string
 * @param cutFrom – start of the middle section to split on
 * @param cutTo – end of the middle section to split on
 * @param left – destination for left segment
 * @param right – destination for right segment
 * @return whether a split was performed
 */
bool
split(const char string[], int len, int cutFrom, int cutTo, char left[], char right[]) {
    if (!(0 <= cutFrom && cutFrom < len && 0 <= cutTo && cutTo < len
          && cutFrom <= cutTo))
        return false;

    // copy each part into the corresponding destination
    for (int i = 0; i < cutFrom; ++i)
        left[i] = string[i];
    left[cutFrom] = '\0';
    for (int i = cutTo; i < len; ++i)
        right[i - cutTo] = string[i];
    right[(len - cutTo)] = '\0';

    return true;
}


/**
 * Partition a string in two, splitting immediately before the last blank sequence
 * that appears after a non-blank character.
 *
 * If no such blank is found, does nothing.
 *
 * @param string – original string
 * @param left – destination for the first part of the string
 * @param right – destination for the second part of the string
 * @return whether a split was performed
 */
bool splitBeforeLastBlankSeparator(const char *string, char *left, char *right) {
    size_t len = strlen(string);
    // compute the split boundary
    int boundary = -1;
    int i = 0;
    while (i < len) {
        if (isblank(string[i])) {
            boundary = i;
            while (isblank(string[i])) ++i;
        }
        else ++i;
    }
    boundary = (boundary == 0) ? -1 : boundary;  // don't split on leading space
    // perform the split
    return split(string, len, boundary, boundary, left, right);
}


/**
 * Partition a string in two, splitting immediately before the first blank sequence.
 *
 * If no blank is found, does nothing.
 *
 * @param string – original string
 * @param left – destination for the first part of the string
 * @param right – destination for the second part of the string
 * @return whether a split was performed
 */
int splitBeforeFirstBlank(const char *string, char *left, char *right) {
    size_t len = strlen(string);
    // compute the split boundary
    int boundary = -1;
    for (int i = 0; i < len; ++i) {
        if (isblank(string[i])) {
            boundary = i;
            break;
        }
    }
    // perform the split
    return split(string, len, boundary, boundary, left, right);
}


/**
 * Get a line of input, up to (but not including) the next newline character or EOF.
 *
 * Reads at most `lim` columns (excluding the newline, if present)
 *
 * @param destination Buffer in which to store the input characters;
 *                    must have space for `lim + 1` characters
 * @param lim  Maximum numbers of columns to read
 * @param tabSize number of spaces per tab
 * @return Zero if a full line was read before reaching lim, 1 if it was reached,
 *         EOF if there is no input to be read
 */
int getLineContents(char *destination, int lim, int tabSize) {
    int col = 0, i = 0;
    int c;
    while (col < lim && (c = getchar()) != EOF && c != '\n') {
        destination[i++] = (char) c;
        col += (c == '\t') ? spacesToNextTabStop(col, tabSize) : 1;
    }
    destination[i] = '\0';
    return (i == 0 && c == EOF) ? EOF : col == lim;
}


/**
 * Read a line from input and output it folded format
 * Each line in the output will be at most maxLength characters long, where
 * there is the possibility to split (i.e. blank).
 * 
 * @param maxLength maximum length of lines (in columns)
 * @return the number of output lines 
 */
int readLineAndPrintFolded(const int maxLength, const int tabSize) {
    const int charArraySize = maxLength + 1;
    int lines = 0;

    // get first segment
    char segment[charArraySize];
    int hasMore = getLineContents(segment, maxLength, tabSize);
    if (hasMore == EOF) return lines;  // nothing to be read

    // while line exceeds limit, print current output line and start another
    char beforeCut[charArraySize], afterCut[charArraySize];
    while (hasMore == 1) {
        // find blank to split on
        if (!splitBeforeLastBlankSeparator(segment, beforeCut, afterCut)) {
            // while there is no blank to split on,
            // append segment (without ending the line) & reread
            do {
                if (hasMore == 1) printf("%s", segment);
                else {
                    // line is finished without having found any blank
                    puts(segment);
                    return ++lines;
                }
                hasMore = getLineContents(segment, maxLength, tabSize);
            } while (!splitBeforeFirstBlank(segment, beforeCut, afterCut));
        }

        // print the fragment before the blank and start continuation line
        puts(beforeCut);
        ++lines;

        // deal with the fragment after the cut:
        int remainderCols = columnLength(afterCut, tabSize);
        // copy the fragment after the cut into the beginning of the new segment
        strcpy(segment, afterCut);
        // read into the rest of segment until full
        if (hasMore == 1)
            hasMore = getLineContents(&segment[strlen(afterCut)],
                                      maxLength - remainderCols, tabSize);
    }

    // print last sub-line
    puts(segment);
    return ++lines;
}


int main() {
    while (readLineAndPrintFolded(MAX_LINE_LENGTH, TAB_SIZE) > 0);
}

---

Please help me, my task-completion-obsessed brain won't let me go on to the next chapter until I finish all exercises!

Answer 1

General Observations and Comments

You have obviously put in a lot of effort into this question and deserve an answer.

I have mostly programmed in Python, C++ and Java so far, and I recently picked up K&R (second edition) to learn some C. I have only gone through the first chapter so far, which is "A Tutorial Introduction".

K&R was the definition in the beginning (I used it daily for a while in the 1980's), but there are probably better sources now. K&R Second Version was for C90 (ANSII C) and not C99.

While Doxygen style comments are good for documentation, they can be overkill in some situations. A best practice is to used self documenting code and only use comments to explain why something is necessary.

When compiling the C programming language, it is better to use the -Wall switch on the compiler (report all warnings). This will find more possible issues. The line numbers for the following warnings will not work with your code because I stripped out most of the comments to get at the code. I will go into more depth for most of the warnings. The warnings I get when compile the code are:

splitLine.c(44,14): warning C4018: '<': signed/unsigned mismatch
splitLine.c(60,23): warning C4018: '<': signed/unsigned mismatch
splitLine.c(79): warning C4701: potentially uninitialized local variable 'c' used
splitLine.c(60): message : index 'i' range checked by comparison on this line
splitLine.c(61): message : feeds call on this line
splitLine.c(44): message : index 'i' range checked by comparison on this line
splitLine.c(47): message : feeds call on this line
splitLine.c(44): message : index 'i' range checked by comparison on this line
splitLine.c(45): message : feeds call on this line
splitLine.c(74): message : index 'col' range checked by comparison on this line
splitLine.c(76): message : feeds call on this line

Unlike programming in C++, when programming in C one needs to be comfortable with macros and raw pointers.

The C Programming Language Does Not Support Variable Sized Arrays

I compile C locally with a strict C definition and there are 2 lines that don't compile in my compiler (Visual Studio 2019 Professional on Windows 10 Professional). I wouldn't try any online C compilers to be strict.

This is the section of code where the two lines that don't compile in my compiler:

int readLineAndPrintFolded(const int maxLength, const int tabSize) {
    const int charArraySize = maxLength + 1;
    int lines = 0;

    // get first segment
    char segment[charArraySize];
    int hasMore = getLineContents(segment, maxLength, tabSize);
    if (hasMore == EOF) return lines;  // nothing to be read

    // while line exceeds limit, print current output line and start another
    char beforeCut[charArraySize], afterCut[charArraySize];

The two lines are

    char segment[charArraySize];

and

    char beforeCut[charArraySize], afterCut[charArraySize];

The reason they don't compile is because charArraySize is a variable and not a constant in a strict definition of C.

Initialize ALL Local Variables

The C programming language is not a friendly language and variables declared on the stack are not automatically initialized with a value. This caused the following warning message splitLine.c(79): warning C4701: potentially uninitialized local variable 'c' used. Here is the code responsible:

int getLineContents(char* destination, int lim, int tabSize) {
    int col = 0, i = 0;
    int c;
    while (col < lim && (c = getchar()) != EOF && c != '\n') {
        destination[i++] = (char)c;
        col += (c == '\t') ? spacesToNextTabStop(col, tabSize) : 1;
    }
    destination[i] = '\0';
    return (i == 0 && c == EOF) ? EOF : col == lim;
}

It is possible that the while loop will never be executed so the variable c won't have a value, it should be initialized to zero.

Use a Separate Line for Each Variable Declaration and Initialization

In the function getLineContents() above the variable col and the variable i are delcared and initialized on the same line. To make maintenance of the program easier, it is better to have each variable declared and initialized in it's own declaration.

int col = 0;
int i = 0;
int c = 0;

To add or remove a variable become much simpler in this case, simply add a line or deleted a line, not middle of the line edits.

size_t Mismatch with int

There are a number of places in the code where there is a signed/unsigned mismatch, here is one example:

int splitBeforeFirstBlank(const char* string, char* left, char* right) {
    size_t len = strlen(string);
    // compute the split boundary
    int boundary = -1;
    for (int i = 0; i < len; ++i) {
        if (isblank(string[i])) {
            boundary = i;
            break;
        }
    }
    // perform the split
    return split(string, len, boundary, boundary, left, right);
}

The variable len is declared as type size_t but the variable i is declared as int. This is causing the type mismatch warning and could potentially indicate worse problems (a negative index into an array). When using an index into an array it is best to declare the index variable as size_t, this prevents the variable from going negative. If the value returned by this function is used as an index, it might be better to return a size_t rather than an int as well.

Defining Constants and Inline Functions Using Macros

The newer versions of C allow for symbolic constants to be defined using const int VARNAME = VALUE; however, in C #define is a good way to define array sizes. In K&R I don't think you will find any const int declarations. The const int method is better if this will be compiled using a C++ compiler. Macros using #define are not type safe which is why they are avoided in C++.

In this program const int TAB_SIZE = 4; could be changed to #define TAB_SIZE 4.

Also in this program the function int spacesToNextTabStop(int column, int tabSize) could be defined as #define SPACES_TO_NEXT_TAB_STOP(col, tabsize) tabSize - (column % tabSize).

Raw Pointers for Optimization

Since C is a programming language that is sometimes considered a very high level assembler, direct addressing is supported. In early versions of C (such as K&R C) this is how a lot of optimization for arrays was handled. Newer optimizing compilers handle this, by substituting direct memory addressing into the object code when compiling using the -O3 flag (maximum optimization). The function int columnLength(const char string[], const int tabSize) can be written using pointers which would optimize the performance:

int columnLength(const char c_string[], const int tabSize)
{
    int column = 0;

    for (const char* cptr = c_string; *cptr; cptr++)
    {
        column += (*cptr == '\t') ? spacesToNextTabStop(column, tabSize) : 1;
    }

    return column;
}

Renamed Variables in the optimized example above
In the example above I renamed string to c_string because string is a keyword in C++ and many programmers compile C programs using a C++ compiler, also in many cases companies take existing C code and embed it in C++ programs to enhance the existing functioning code.

I renamed col to column because it makes the code more self-documenting and easier to read and maintain.

Answer 2

Here are some things that may help you improve your code.

Use a newer reference

K&R second edition is quite old and refers to the 1989 version of the C language. If you want to learn the C language, a more recent source would likely be more useful. The current version of the standard is C18.

Be careful with signed vs. unsigned

You are correctly using size_t as the type for len but then comparing it to i which is declated as an int. Since size_t is unsigned and int is signed, there is a potential problem in comparing them directly because they are both treated as unsigned values, per the C standard.

Consider always using braces

The code currently contains this loop:

int i = 0;
while (i < len) {
    if (isblank(string[i])) {
        boundary = i;
        while (isblank(string[i])) ++i;
    }
    else ++i;
}

Omitting the braces for the else clause is permitted by the language, but it can lead to problems. See Apple's infamous goto fail vulnerability for example.

Prefer for over while where appropriate

The loop in the previous suggestion could be rewritten as a for loop:

bool inblanks = false;
for (size_t i = 0; string[i] != '\0'; ++i) {
    if (isblank(string[i])) {
        if (!inblanks) {
            boundary = i;
            inblanks = true;
        }
    } else {
        inblanks = false;
    }
}

Note that the exit condition has been changed to look for the terminating '\0' character. This saves having to call strlen and may confer a modest performance gain.

Use all uppercase only for preprocessor macros

It's not enforced by the compiler, but common practice for decades has been to reserve all uppercase names solely for macros. It's a recommended practice also in C++. See ES.9

Think of the user

The instructions included this line:

Make sure your program does something intelligent with very long lines, and if there are no blanks or tabs before the specified column.

When I think of uses for this program, the first one that comes to mind is accomodating long lines of text on finite-size screen. With that in mind, ignoring the line length as your program does, is probably not the right thing to do. I'd suggest instead that no line of the output should exceed the set MAX_LINE_LENGTH.

An example

Using all of these things, and ignoring tabs, using only the 1989 version of C, we might have written the program like this:

#include <stdio.h>

#define MAX_LINE_LENGTH 10

int main() {
    const unsigned end = MAX_LINE_LENGTH;
    unsigned col = 0;
    unsigned lastspace = end;
    unsigned src;
    char line[MAX_LINE_LENGTH + 1];
    int ch;
    for (ch = getchar(); ch != EOF; ch = getchar()) {
        if (ch == '\n') {
            line[col] = '\0';
            puts(line);
            col = 0;
            lastspace = end;
        } else if (ch == ' ') {
            lastspace = col;
            line[col++] = ch;
        } else {
            line[col++] = ch;
        }
        if (col == MAX_LINE_LENGTH) {
            line[lastspace] = '\0';
            puts(line);
            if (lastspace == end) {  /* no spaces in segment */
                col = 0;
            } else { /* space in segment  */
                src = lastspace + 1;
                lastspace = end;
                /* copy characters after space to beginning of segment */
                for (col = 0; src < end; ++src, ++col) {
                    line[col] = line[src];
                    if (line[col] == ' ') {
                        lastspace = col;
                    }
                }
            }
        } 
    }
    return 0;
}

One way to add handling of tabs to this would be to simply make a wrapper for getchar() that turns tabs into spaces.