Strings recap

Chapter 4 left you with a run of same-typed objects and one unbreakable habit, which was that the run and its length travel together because nothing at run time remembers how many elements there are. This chapter kept the run and replaced the count with a convention. A string is a char array with one zero byte at the end, and that byte is the only record of where the text stops, so every function in the chapter finds the end by walking to it. Everything else falls out of that. A string of n characters needs n + 1 bytes, and the + 1 turns up in three disguises across five lessons, in an array you declare, in a malloc request you compute from strlen, and in the arithmetic that joins two pieces. The size of the destination is the fact the dangerous functions were never told and the safe ones take as an argument, so a size either travels with the buffer, as it does into fgets and snprintf, or it is computed from the source, as it is on the heap. And because a heap block outlives the frame it was made in, chapter 4's ownership question arrives here word for word with a string in it instead of an int block. Let's review each lesson before you test yourself.

C Strings and the Null Terminator

There is no string type in C, no object that knows its own length and no hidden size field, so a C string is a convention rather than a type: a contiguous run of char plus a final byte with the value zero, the null terminator, written '\0'. It is a character constant like chapter 2's 'A', and it is emphatically not '0', the digit, whose value is 48; the two look alike in source and the compiler will never question a swap, because to C both are small integers. A string literal already has this shape because the compiler appends the terminator itself, which is why "hi" looks like two characters and is three, and why a buffer for an n-character string needs n + 1 bytes. char greeting[] = "hi"; copies those three bytes into an array of your own, and this is the third decay exception chapter 4 named and deferred, a string literal initializing an array element by element rather than becoming a pointer. Since nothing records the length, finding it means walking from the start to the zero byte, and a function doing that walk takes a const char * and no count, which is the one thing the convention buys you: unlike every other array in chapter 4, a string carries its own end marker. Two numbers therefore describe one array and they differ by one every time, because a character count stops at the terminator and excludes it while sizeof on the array counts every byte and includes it, so char s[] = "hi"; has sizeof 3 against a count of 2. printf's %s is another walker, starting at the address you hand it and writing bytes until it meets the terminator, which is also chapter 1's security rule made concrete: write printf("%s", text) and never printf(text), because a string you did not write is data and must never be read as a format. The other declaration looks nearly identical and behaves nothing like it. const char *literal = "hi"; aims a pointer at the literal itself, an object with static storage duration that lives for the whole run in memory the program does not get to write, so sizeof reports a pointer rather than 3, and modifying a string literal is undefined behaviour, which this platform reported as a SEGV whose signal was caused by a WRITE at a perfectly real read-only address. Declare an array when you mean to modify and const char * when you only mean to read, and the accident becomes a compile error rather than a run you have to survive. Last, everything above depends on the terminator being there. char word[2] = {'h', 'i'}; is a legal, complete, correctly initialized array and is not a string, because there was no room left for the terminator and the initializer supplied none, so %s walks past the end and AddressSanitizer reports a stack-buffer-overflow with a READ, naming [32, 34) 'word' and an access at offset 34. Nothing about the array is wrong; what is wrong is calling two bytes a string.

The String Library

<string.h> ships that counting walk under the name strlen, which takes a const char *, returns how many characters it passed before meeting '\0', and returns it as size_t, so it prints with %zu and not %d. It is the same work your loop did, which means it costs the same: strlen is a walk, not a lookup of a stored length, so when the string is not changing, compute it once into a variable rather than once per loop iteration. Printed side by side, sizeof 3 against strlen 2 is the previous lesson's pairing with the library's name on it, and reaching for the wrong one sizes a buffer a byte short. strcmp returns negative, zero or positive, three answers rather than two, which is what a sorting routine needs and what trips up a reader expecting yes or no; only the sign is promised, so compare the result against zero and never against 1. That makes if (strcmp(a, b)) the classic misreading, since it is true precisely when the strings differ, and if (strcmp(a, b) == 0) is the spelling you want, read aloud as "if the difference is zero". This is also where chapter 2's loose end is tied, because switch needs integer constants and can never branch on strings, so a chain of strcmp tests is what C offers instead. Meanwhile == on strings compares addresses, not characters, so two separate arrays holding the same six bytes are not equal to each other; gcc catches the array spelling with -Warray-compare and says nothing at all about the pointer spelling, which is the one you actually meet because a char * parameter is what every function receives. Copying is a function call rather than an =, since arrays are not assignable, and strcpy is never told how large the destination is, so a 22-byte source writes 22 bytes into an eight-byte array and AddressSanitizer reports a stack-buffer-overflow whose operation is a WRITE, the word that separates a wrong answer from bytes landing in storage that belongs to something else. Take -Wstringop-overflow= as a gift rather than a guarantee, because it exists only where the compiler can see both sizes, and note that at -O2 the top frame said memcpy: the library function you wrote is not always the function that runs. Two fixes give the call the size it was missing. Guard it with if (strlen(source) < sizeof(destination)), where < rather than <= reserves the byte for the terminator, remembering that sizeof reports 8 only where the destination is a real array in scope, so a function that copies must take the destination size as a parameter. Or reach for snprintf(destination, sizeof(destination), "%s", source) by default, which takes the buffer's size, always writes a terminator, and returns the length it wanted rather than the length it wrote, so wanted >= size turns silent truncation into a decision you made. strncpy is not a safe strcpy: given a source at least n characters long it copies exactly n bytes and writes no terminator, leaving a buffer that the next %s or strlen walks straight off the end of, and strcat carries the same missing-size problem as strcpy.

Reading Lines with fgets

scanf("%s", word) is the input call this course stepped around, and everything visible about it can be correct while the call remains impossible to make safe, because nothing in the argument list tells scanf how large word is. That is the same absence that sank strcpy, with one difference that matters: the length is a property of the run rather than of the source, so gcc cannot warn, and the person supplying the input decides how far past the end of your array the write goes, which arrived as a WRITE of size 16 into an object of [32, 40). A field width such as %7s does bound the read but still takes one whitespace-delimited word when what you wanted was the line, and its ancestor gets could not be bounded at all and was removed from the language in C11. fgets(line, sizeof(line), stdin) is the fix, with the fix visible in the call: the buffer, the size of that buffer, and where to read from. Given the size it stops for one of three reasons, having stored a newline, having stored size - 1 characters, or the input having ended, it writes a terminator in every one of those cases, and it returns NULL when it stored nothing at all, which makes while (fgets(line, sizeof(line), stdin) != NULL) the string counterpart of chapter 2's while (scanf("%d", &value) == 1). Then the byte everybody meets once. When the whole line fits, fgets keeps the newline you typed, stored in the buffer like any other character, so a four-character word reports strlen 5, printed output gains a blank line, and strcmp(line, "quit") is not zero because quit followed by \n is a different string from quit. Nothing warns you, so strip it deliberately: measure with strlen, check that the last character really is '\n' before touching it, and overwrite that one byte with '\0', which does not shorten the array but moves the end of the string back by one. The length > 0 test is not ceremony, because the last line of a file often arrives with no newline at all, and neither is the newline test, because when the line does not fit there is no newline: fgets stores size - 1 characters, terminates them, and leaves the remainder in the input for the next call, so one typed line arrives as several strings with nothing lost and nothing overflowed. Reading is still not parsing, and sscanf is scanf aimed at a string, with the same format strings, the same & on its arguments and the same return value, the number of conversions that succeeded, so == 2 is the check that two numbers were really on the line. That pair is the point. fgets does the bounded read and sscanf does the checked parse, and because the line is out of the stream before parsing is attempted, a bad line can be reported and discarded while the good lines on either side of it are still read. A failed scanf cannot recover that way, since it converts nothing, returns 0, and leaves the offending characters exactly where they were, so calling it again meets the same text forever.

Strings on the Heap

A heap string is chapter 4's runtime-decided size and this chapter's n + 1 rule meeting in one number, the one you hand to malloc. strlen(source) is only the first half of it, because the terminator is the byte nobody asks for, nobody types, and no sizeof is standing by to add on your behalf, so malloc(strlen(source)) followed by strcpy writes nine bytes into an eight-byte block and AddressSanitizer reports a heap-buffer-overflow with a WRITE of size 9 landing 0 bytes after 8-byte region. Read that against the stack version and the real difference appears. char destination[8]; carries its size in its declaration, so there is a sizeof to consult and a number gcc knows at every call, while here the size was computed, and the only record of how big the block is is the arithmetic you wrote, which makes everything downstream confidently short by one. So write the rule into the arithmetic as malloc(strlen(source) + 1) and never the bare form. Chapter 4's count * sizeof *p has not been abandoned here, it has collapsed, because sizeof(char) is defined to be 1 and multiplying by it changes nothing; check the result against NULL every time and never cast it. Wrapping those lines in char *make_copy(const char *source) gives the ownership question a single place to be answered, since what comes back is a pointer and an obligation that nothing in the type char * records, exactly as chapter 4 described, carried by the make_ prefix and by what you wrote down. Notice that the strcpy inside it has no length check above it and is still correct, because the destination's size was computed from this very source one line earlier, so the check would compare strlen(source) against strlen(source) + 1 and a condition that cannot be false is noise rather than safety. The rule was discharged by construction, not ignored, and knowing why a rule exists is what tells you when it has been satisfied. Then the reason heap strings exist at all: char line[64] is one buffer that fgets overwrites on every iteration, so the text of the first line survives only until the second arrives, and a program that wants to remember a line has to move it somewhere sized while the program runs. When you replace what you kept, free the old block before overwriting the pointer, since assigning first orphans it and completes chapter 4's first leak shape once per improvement rather than once per program, and free(NULL) being a defined no-op is what lets the same two lines serve the first keep and every later one. Copying is the simplest computed size; building a string from pieces is the general case, and strlen(first) + strlen(second) + 2 is two bytes with two separate reasons, one for the separator going between the pieces and one for the terminator going after them, filled by snprintf with the same size so that an arithmetic slip truncates instead of overflowing.

Growing Buffers with realloc

A fresh malloc and a discarded old block is the right shape when the new string has nothing to do with the old one, and the wrong shape entirely when what you want is the old string with more added to the end. realloc(pointer, new_size) takes a block you already own and returns one of the new size holding the old contents, up to the smaller of the two sizes, and realloc(NULL, size) does what malloc(size) does, which removes the special case at the start of a growth loop. Two facts about it are load bearing. First, a successful realloc may or may not have moved your block and you do not get to know which, so the old pointer is stale the instant realloc returns, using it is chapter 4's heap-use-after-free reached without a single free in your source, and the old block is not something you free afterwards. Second, realloc returning NULL frees nothing, which is a generous contract and completely useless if you have thrown away the address, and that is exactly what p = realloc(p, n); does: it overwrites the only pointer to a live block with the NULL that reported the failure, so LeakSanitizer reports the original after a run that handled its error and exited 0. What makes this trap worse than chapter 4's is that the API springs it, because the expression that reports the failure is the expression that destroys the evidence, and every run with memory to spare looks perfect. So assign to a temporary, check the temporary, then overwrite your pointer, with the failure branch freeing the original that is still there waiting for it. A buffer that grows also needs two numbers where a fixed array needed none. Capacity is how many bytes you asked the allocator for and length is how many characters you have written, terminator not counted, and each has one job: capacity is what you compare against before writing and length is where the next write starts, at text + length. Keeping both in one variable is how buffers overrun, because "will this fit" and "where does it go" have different answers. Grow by doubling, since reaching n bytes takes about log2(n) reallocations instead of n, at the price of a buffer up to twice the size of its contents, and write the growth test as a while rather than an if, carrying this chapter's + 1, because one chunk can need several doublings. Here is the chapter in one program.

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

int main(void)
{
    char line[64];
    char *last = NULL;

    while (fgets(line, sizeof(line), stdin) != NULL)
    {
        size_t length = strlen(line);

        if (length > 0 && line[length - 1] == '\n')
        {
            line[length - 1] = '\0';
        }

        if (last == NULL || strcmp(line, last) > 0)
        {
            char *kept = malloc(strlen(line) + 1);

            if (kept == NULL)
            {
                free(last);
                printf("could not allocate\n");
                return 0;
            }

            strcpy(kept, line);
            free(last);
            last = kept;
        }
    }

    if (last == NULL)
    {
        printf("no lines\n");
        return 0;
    }

    printf("sorts last: %s (%zu characters)\n", last, strlen(last));
    free(last);

    return 0;
}

Given the four lines banana, apple, cherry and apple pie that prints sorts last: cherry (6 characters), and given no input at all it prints no lines, both with nothing on standard error. Every line of it is a rule from this chapter. fgets is handed the buffer and its size, so nobody typing gets to decide how much is written. The strip is a test rather than an assumption, guarded on length > 0 and on the last character really being a newline, and without it strcmp would be comparing against strings that all end in an invisible byte. strcmp(line, last) > 0 uses the sign of the three-way result rather than treating it as a boolean, which is the only thing the standard promises. malloc(strlen(line) + 1) computes the size from the source with the terminator included, which is why the strcpy below it needs no length check: the room was derived from the very string about to be copied into it. The NULL check decides the failure path instead of merely noticing it, and it frees last on the way out because a program that gives up still owns what it was holding. free(last); last = kept; is in the only order that works, and the first pass through it frees NULL, which is a defined no-op. And line is never freed, because it was never allocated; only the block main asked for is given back, exactly once, on every path that has one to give.

Key Terminology

  • Null terminator and the n + 1 rule: the byte with value zero that marks a string's end, written '\0' and not to be confused with the digit '0', whose presence every string operation depends on and whose byte must be counted in every buffer you size
  • String literal, and char s[] = "hi" against char *p = "hi": the first copies the literal's bytes into a writable array of your own, the second aims a pointer at an object with static storage duration that lives for the whole run, and modifying that object is undefined behaviour, so declare an array to modify and const char * to read
  • strlen against sizeof: a walk to the terminator that excludes it and returns size_t, printed with %zu, against a byte count that includes it; sizeof answers only where the array itself is in scope, since on a char * parameter it measures the pointer
  • strcmp and ==: negative, zero or positive with only the sign promised, so equality is strcmp(a, b) == 0 and a bare if (strcmp(a, b)) is true when the strings differ, while == compares two addresses and reports identical text as unequal
  • strcpy, snprintf and strncpy: a copy that is never told the destination's size and needs if (strlen(source) < sizeof(destination)) above it, a formatted write that takes the size, always terminates, and returns the length it wanted so wanted >= size detects truncation, and a fixed-width copier that leaves the buffer unterminated when the source fills it
  • fgets and its newline: buffer, size and stream, stopping on a newline, on size - 1 characters or at end of input, always terminating, returning NULL when nothing was stored, and keeping the newline when the line fits, so it is stripped on purpose and its absence means the remainder is still in the input
  • sscanf and the read and parse split: scanf aimed at a string, returning the number of conversions completed, which is what lets a bounded read hand a line to a checked parse and lets one bad line be discarded rather than met forever
  • make_copy and ownership: malloc(strlen(source) + 1) behind a name that announces the transfer, since char * records no obligation, with the caller freeing exactly once, the old block freed before the pointer is overwritten, and free(NULL) making the first replacement need no special case
  • Capacity, length and the realloc temporary: bytes you asked for against characters you have written, one to compare against and one to write at, resized through char *grown = realloc(p, n); then a check then p = grown;, because success may have moved the block and failure frees nothing

Looking Forward

You can now read input nobody measured, keep a string past the buffer it arrived in, compare and build strings without walking off the end of one, and ask every line that touches a buffer the two questions this chapter and the last one share: is there room for the terminator, and who frees this. What you cannot yet do is keep a string next to the other facts about the thing it names. Chapter 6 fixes that with the struct, which gathers values of different types under one name so that a title, a length and a price travel as one object instead of as three parameters that must be passed in the right order. Structs then meet pointers and the heap, which is where this chapter's ownership rules stop applying to a single block and start applying to a struct that owns heap strings of its own, freed in the right order. Enums give a name to each of a fixed set of states so that a program branches on state_reading rather than on 2, and unions let one region of storage hold one of several types at a time. Then the chapter turns from data to programs, splitting one file into several with headers, which is the point at which make_copy becomes something you write once and include everywhere, and also the point at which the compiler stops being able to see the malloc and the strcpy together, which is exactly why the rules in this chapter were written to hold without a diagnostic.