K&R Exercise 1-21. Write a program `entab` that replaces strings of blanks with tabs

Question

Intro

I'm going through the K&R book (2nd edition, ANSI C ver.) and want to get the most from it: learn (outdated) C and practice problem-solving at the same time. I believe that the author's intention was to give the reader a good exercise, to make him think hard about what he can do with the tools introduced, so I'm sticking to program features introduced so far and using "future" features and standards only if they don't change the program logic.

Compiling with gcc -Wall -Wextra -Wconversion -pedantic -std=c99.

K&R Exercise 1-21

Write a program entab that replaces strings of blanks by the minimum number of tabs and blanks to achieve the same spacing. Use the same tab stops as for detab. When either a tab or a single blank would suffice to reach a tab stop, which should be given preference?

Solution

The solution attempts to reuse functions coded in the previous exercises (getline & copy) and make the solution reusable as well. In that spirit, a new function size_t entab(char s[], size_t tw); is coded to solve the problem. For lines that can fit in the buffer, the solution is straightforward. However, what if they can't? The main routine deals with that, and most of the lines are treating the special case where we must merge the blanks from 2 getline calls. This exercise is just after the chapter where extern variables are introduced, and they really are convenient here enabling the entab function to be aware of the column we're at.

Code

/* Exercise 1-21. Write a program `entab` that replaces strings of
 * blanks by the minimum number of tabs and blanks to achieve the same
 * spacing. Use the same tab stops as for `detab`. When either a tab or
 * a single blank would suffice to reach a tab stop, which should be
 * given preference?
 */

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

#define MAXTW   4       // max. tab stop width
#define LINEBUF MAXTW   // line buffer size, must be >=MAXTW

size_t col = 0;         // current column
size_t tcol = 0;        // target column

size_t getline(char line[], size_t sz);
void copy(char * restrict to, char const * restrict from);
size_t entab(char s[], size_t tw);

int main(void)
{
    extern size_t col;                  // current column
    extern size_t tcol;                 // target column

    char line[LINEBUF];                 // input buffer
    size_t len;                         // input buffer string length

    size_t tw = 4;                      // tab width

    if (tw > MAXTW) {
        return -1;
    }

    len = getline(line, LINEBUF);
    while (len > 0) {
        len = entab(line, tw);
        if (line[len-1] == '\n') {
            // base case, working with a full, properly terminated line
            // or a tail of one; we can safely print it
            col = 0;
            tcol = 0;
            printf("%s", line);
            len = getline(line, LINEBUF);
        }
        else if (line[len-1] != ' ') {
            // could be part of a bigger line or end of stream and we
            // don't have dangling blanks; we can safely print it
            printf("%s", line);
            len = getline(line, LINEBUF);
        }
        else {
            // we have some dangling blanks and must peek ahead to
            // know whether we can merge them into a tab or not
            bool cantab = false;
            char pline[LINEBUF];    // peek buffer
            size_t plen;            // peek buffer string length
            plen = getline(pline, LINEBUF);
            if (plen > 0) {
                if (pline[0] == ' ') {
                    // count spaces in the peek; pspc = 1 because if
                    // we're here then we already know pline[0] == ' '
                    size_t pspc;
                    for (pspc = 1; (pline[pspc] == ' ' ||
                    pline[pspc] == '\t') && pspc < plen &&
                    pspc < tw; ++pspc) {
                        if (pline[pspc] == '\t') {
                            cantab = true;
                        }
                    }
                    // enough to warrant a tab stop?
                    if (col + pspc >= (col + tw)/tw*tw) {
                        cantab = true;
                    }
                }
                else if (pline[0] == '\t') {
                    cantab = true;
                }
            } // else we got EOF and those spaces have to stay
            if (cantab) {
                // pop the spaces and adjust current column accordingly
                while (len > 0 && line[--len] == ' ') {
                    --col;
                    line[len] = '\0';
                } // no need to fix len, as it gets reset below
            }
            printf("%s", line);
            len = plen;
            copy(line, pline);
        }
    }
    return 0;
}

/* entab: process string from `s`, replace in-place spaces with tabs.
 * Assume '\0' terminated string. Relies on extern variable for column
 * alignment.
 * tw - tab width
 */
size_t entab(char s[], size_t tw)
{
    extern size_t col;  // current column
    extern size_t tcol; // target column
    size_t j = 0;
    bool gotnul = false;
    for (size_t i = 0; !gotnul; ++i) {
        // on blank or tab just continue reading and move our target
        // column forward
        if (s[i] == ' ') {
            ++tcol;
        }
        else if (s[i] == '\t') {
            tcol = (tcol+tw)/tw*tw;
        }
        else {
            // on non-blank char, if we're lagging behind target fill-up
            // with tabs & spaces and then write the char, else just
            // write the char
            if (tcol > col) {
                for (size_t at = (tcol/tw*tw-col/tw*tw)/tw; at > 0;
                --at) {
                    s[j] = '\t';
                    ++j;
                    col = (col+tw)/tw*tw;
                }
                for (size_t as = tcol-col; as > 0; --as) {
                    s[j] = ' ';
                    ++j;
                    ++col;
                }
            }
            s[j] = s[i];
            if (s[j] == '\0') {
                gotnul = true;
            }
            else {
                ++j;
                ++col;
                ++tcol;
            }
        }
    }
    return j;
}

/* getline: read a line into `s`, return string length;
 * `sz` must be >1 to accomodate at least one character and string
 * termination '\0'
 */
size_t getline(char s[], size_t sz)
{
    int c;
    size_t i = 0;
    bool el = false;
    while (i + 1 < sz && !el) {
        c = getchar();
        if (c == EOF) {
            el = true; // note: `break` not introduced yet
        }
        else {
            s[i] = (char) c;
            ++i;
            if (c == '\n') {
                el = true;
            }
        }
    }
    if (i < sz) {
        if (c == EOF && !feof(stdin)) { // EOF due to read error
            i = 0;
        }
        s[i] = '\0';
    }
    return i;
}

/* copy: copy a '\0' terminated string `from` into `to`;
 * assume `to` is big enough;
 */
void copy(char * restrict to, char const * restrict from)
{
    size_t i;
    for (i = 0; from[i] != '\0'; ++i) {
        to[i] = from[i];
    }
    to[i] = '\0';
}

Test

Input

                                        sdas                
    a   a   aaa aasa      aaa               d   dfsdf           aaa ss  s       g
aa      asd        s    f   f  f    X   
         asf                 

Showing the tabs as ^I:

$ cat -T test.txt 
                                        sdas                
    a   a   aaa aasa^I  aaa^I            d   dfsdf           aaa ss  s       g
aa^I  ^Iasd^I       s^If^If  f^IX  ^I
     ^I asf ^I^I^I ^I 

Output

                                        sdas                
    a   a   aaa aasa      aaa               d   dfsdf           aaa ss  s       g
aa      asd        s    f   f  f    X   
         asf                 

Showing the tabs as ^I:

$ cat -T out.txt 
^I^I^I^I^I^I^I^I^I^Isdas^I^I^I^I
^Ia^Ia^Iaaa^Iaasa^I  aaa^I^I^I^Id^Idfsdf^I^I^Iaaa^Iss^Is^I^Ig
aa^I^Iasd^I^I   s^If^If  f^IX^I
^I^I asf^I^I^I^I 

Answer 1

OP only asked a few direct questions.

When either a tab or a single blank would suffice to reach a tab stop, which should be given preference?

Use blanks ' '.

Developers Who Use Spaces Make More Money Than Those Who Use Tabs

---

For lines that can fit in the buffer, the solution is straightforward. However, what if they can't?

Use a generous buffer. And when the line does not fit in the buffer, exit with a failure message.

Let us go deeper ...

When memory was expensive, too often code used fixed size small buffers, leading to problems with expanded uses.

With cheap memory, code could be written to allow for re-allocated read buffers sizes, virtually unlimited yet technically limited to SIZE_MAX.

This value can readily exceed the memory capacity of the platform.

Now we live in an era of code security vs. hacking. A program that allows external input to readily consume system resources is a hacker target as part of an exploitation. For the purpose of en-tabbing a line, why support 1 Gbyte long lines? Say code limited lines to 1 MByte. Yes once in a great while some application will die due to a long line and a Defect Report may ensue - and go to the bottom of the list in resolution handling. Risk vs. reward: handling ever larger lines vs. greater exploitation risk.

In any case, C has an Environmental limit,

An implementation shall support text files with lines containing at least 254 characters, including the terminating new-line character. The value of the macro BUFSIZ shall be at least 256. C11dr §7.21.2 7

Any code working with lines much larger than BUFSIZ runs into that limitation and so risks UB.

I recommend:

• Use buffers 2x the largest expected need for that task. In this case, consider #define LINEBUF (BUFSIZ+1u) or #define LINEBUF (BUFSIZ*2u) and allocate char *line.
• Treat long input as non-compliant and either reject the partial line and the rest of the line OR fail the code with a message.

Note: On many platforms, code can allocate very large buffers with *alloc() and not truly consume resources until needed. Why is malloc not “using up” the memory on my computer? .

---

For lines that can fit in the buffer, the solution is straightforward. However, what if they can't? (Take 2)

Entab only requires about a few bytes. Think state machine. Re-write code. See below.

---

Other

Conditions

Conditions like LINEBUF >= MAXTW can be made into a compile time check

#if !(LINEBUF >= MAXTW)
  #error Buffer size too small
#endif

Also research Static assert in C.

Overview

Nice format and good style.

getline()

ssize_t getline(char **, size_t *, FILE *) is a popular *nix function that conflicts with OP's size_t getline(char s[], size_t sz). Consider a different name my_getline().

Suggested alternative with, IMO, improvements. (Ignoring "break not introduced yet")

size_t my_getline(char s[], size_t sz) {
  if (sz <= 0) { // Handle this pathological case right away
    return 0;
  }
  sz--;

  int c = 0;
  size_t i = 0;
  while (i < sz && (c = getchar()) != EOF) {
    s[i++] = (char) c;
    if (c == '\n') {
      break;
    }
  }

  if (c == EOF && !feof(stdin)) { // EOF due to read error
    i = 0;
  }
  s[i] = '\0';
  return i;
}

Note: OP's code has UB in the pathological case sz == 1 as it tests uninitialized c with c == EOF.

copy()

Alternative code for consideration:

void copy(char * restrict to, char const * restrict from) {
  while ((*to++ = *from++));
}

entab()

Alternative code for consideration:

With the following there is no limitation on tab width, line length (other than int). No LINEBUF or MAXTW buffers needed. Just 3 int.

#define PRT_TAB "^I"
#define TAB_WIDTH 4
#define FAVORRED ' '

void entab(FILE *istream) {
  int queued_spaces = 0;
  int tab_position = 0;
  int ch;
  while ((ch = fgetc(istream))  != EOF) {
    if (ch == ' ') {
      queued_spaces++;
      tab_position++;
      if (tab_position == TAB_WIDTH) {
#if FAVORRED == '\t'
        putchar('\t');
#else
        if (queued_spaces == 1) putchar(' ');
        else fputs(PRT_TAB, stdout);
#endif
        queued_spaces = 0;
        tab_position = 0;
      }
    } else if (ch == '\t') {
      fputs(PRT_TAB, stdout);
      queued_spaces = 0;
      tab_position = 0;
    } else {
      while (queued_spaces > 0) {
        putchar(' ');
        queued_spaces--;
        tab_position++;
      }
      putchar(ch);
      tab_position++;
      tab_position %= TAB_WIDTH;
    }
  }
  while (queued_spaces > 0) {
    putchar(' ');
    queued_spaces--;
  }
}

int main(void) {
  int ch;
  FILE *istream = fopen("Input", "rb");
  assert(istream);
  puts("Input");
  while ((ch = fgetc(istream))  != EOF) {
    putchar(ch);
  }
  rewind(istream);
  puts("");

  puts("Output");
  entab(istream);
  fclose(istream);
}