Debugging lab: trie bugs

Why this matters

Some trie bugs stop the program with an error message. Others let the program run and print answers that look normal but are wrong. A word you stored is reported as missing. A word you never stored is reported as present. These wrong answers are harder to find than crashes, because nothing in the output says that something went wrong.

A trie is a tree that stores words one letter at a time. Each step down the tree adds one letter, and each node has a flag that says whether a word ends there. Because every word is spread over many nodes, a small mistake in one step affects only the words that pass through that step. That is why a trie can pass a test with a few words and still fail with others.

This lab gives you one trie with three bugs. You will build it, run it, read each crash or wrong line, find the cause, and fix it. The three bugs are common in hand-written tries:

1. A letter is turned into a slot number with the wrong formula.
2. The end flag is set in the wrong place.
3. The code uses a child that does not exist, because it does not check for an empty slot first.

The lab assumes you know what insert and search do. The lessons earlier in this module explain the trie structure and prefix search. This lab only covers what goes wrong.

Terms used in this lab

• Pointer: a variable that holds the memory address of a value. nullptr is a pointer that points to nothing.
• Node: one box in the trie. Each node here has 26 child slots, one for each letter from a to z, and one flag.
• Child: the node stored in a slot. A slot is either a node or empty.
• Index: a slot number. 'a' is index 0, 'b' is index 1, and 'z' is index 25.
• Null: the value of an empty slot. In C++ it is written nullptr. Reading a field through a null pointer is the most common cause of a crash in code like this.
• End flag: a true or false value in each node. It is true when a word ends at that node.
• std::array: a fixed-size list from the C++ standard library. Its at(i) function checks that i is in range and throws an error if it is not. Its [i] operator usually does not check.
• Exception: an error that the program throws. If nothing catches it, the program stops and prints the message.
• Exit code: the number a program gives back when it ends. Zero means success. In a Linux shell, 134 means the program stopped because of an abort, and 139 means it stopped because it read memory it was not allowed to read.
• AddressSanitizer (ASan): a compiler option, -fsanitize=address, that checks memory use while the program runs. When it finds a bad read or write, it prints a report with the file and line.

The buggy program

The program below defines a Trie class. The Trie owns a root node through std::unique_ptr, a smart pointer that deletes what it owns when it goes out of scope, so there is no delete to forget.

The program contains the three bugs. Try to find them before you read the explanations.

#include <array>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
 
struct TrieNode {
    std::array<std::unique_ptr<TrieNode>, 26> children{};
    bool is_end = false;
};
 
class Trie {
public:
    void insert(const std::string& word) {
        TrieNode* node = root_.get();
        for (char c : word) {
            int idx = c - 'A';
            std::unique_ptr<TrieNode>& next = node->children.at(idx);
            if (!next) {
                next = std::make_unique<TrieNode>();
                if (c == word.back()) {
                    next->is_end = true;
                }
            }
            node = next.get();
        }
    }
 
    bool search(const std::string& word) const {
        const TrieNode* node = root_.get();
        for (char c : word) {
            node = node->children.at(c - 'a').get();
        }
        return node->is_end;
    }
 
    bool starts_with(const std::string& prefix) const {
        const TrieNode* node = root_.get();
        for (char c : prefix) {
            node = node->children.at(c - 'a').get();
            if (node == nullptr) {
                return false;
            }
        }
        return true;
    }
 
    std::vector<std::string> words() const {
        std::vector<std::string> out;
        std::string prefix;
        collect(root_.get(), prefix, out);
        return out;
    }
 
private:
    void collect(const TrieNode* node, std::string& prefix, std::vector<std::string>& out) const {
        if (node->is_end) {
            out.push_back(prefix);
        }
        for (int i = 0; i < 26; ++i) {
            const TrieNode* child = node->children[i].get();
            if (child == nullptr) {
                continue;
            }
            prefix.push_back(static_cast<char>('a' + i));
            collect(child, prefix, out);
            prefix.pop_back();
        }
    }
 
    std::unique_ptr<TrieNode> root_ = std::make_unique<TrieNode>();
};
 
void check(bool got, bool expected, const std::string& label) {
    std::cout << (got == expected ? "ok   " : "FAIL ") << label
              << " -> " << std::boolalpha << got
              << " (expected " << expected << ")\n";
}
 
int main() {
    Trie trie;
    for (const std::string w : {"tea", "te", "ten", "inn", "in"}) {
        trie.insert(w);
    }
 
    std::cout << "stored words:";
    for (const auto& w : trie.words()) {
        std::cout << ' ' << w;
    }
    std::cout << "\n";
    std::cout << "expected:    in inn te tea ten\n";
 
    check(trie.search("tea"), true, "search tea");
    check(trie.search("te"), true, "search te");
    check(trie.search("t"), false, "search t");
    check(trie.search("ten"), true, "search ten");
    check(trie.search("in"), true, "search in");
    check(trie.starts_with("te"), true, "starts_with te");
    check(trie.search("dog"), false, "search dog");
    check(trie.search("xyz"), false, "search xyz");
    return 0;
}

Save the program as trie_lab.cpp. Compile it with the standard flag for C++20 and the warning flag:

g++ -std=c++20 -Wall -o trie_lab trie_lab.cpp
./trie_lab

The compile step prints no warnings for this program. Run the program. It stops during the first insert, and the message it prints is the first clue.

The program is built to fail in a fixed order. The first bug stops it before any output. Once that bug is fixed, the second bug produces wrong lines. The third bug stops the program near the end. Fix them in the order the program reports them.

Method

For each run, do these four things:

1. Read the first line of the error or the first line that is wrong. Ignore the rest until you understand that line.
2. Find the line of code that the message points to, or the function that handles the failing input.
3. Trace one short word through that code by hand. Write down the slot number and the node for each letter.
4. Change one thing, compile, and run again. If you change two things at once, you cannot tell which one fixed the problem.

Bug 1: a letter index that is off

Run the buggy program. The first line of output is not a check result. It is an error:

terminate called after throwing an instance of 'std::out_of_range'
  what():  array::at: __n (which is 51) >= _Nm (which is 26)

The program exits with code 134, which is what a shell reports after an abort. Nothing else was printed, so the program stopped during the first call to insert.

Read the message in parts:

• std::out_of_range is the type of error. The at function throws it when an index is outside the array.
• array::at names the function that failed.
• __n (which is 51) is the index the code asked for.
• _Nm (which is 26) is the size of the array. It has 26 slots, so valid indexes are 0 through 25.

The index is 51, so the code computed 51 from the first letter of "tea", which is 't'. The formula in insert is c - 'A'. The letter 'A' is code 65 and 't' is code 116, so 116 - 65 is 51. The formula subtracts the wrong base. Lowercase letters need 'a' as the base. The search and starts_with functions already use 'a', so only insert is wrong.

The fix is one line:

int idx = c - 'a';

Compile and run again. The program no longer throws. It now runs far enough to print output, but the output is not complete yet. Run with unbuffered output to see every line. This is needed here because of the next point.

g++ -std=c++20 -Wall -o trie_stage1 trie_lab.cpp
stdbuf -o0 ./trie_stage1

Without stdbuf -o0, a program that writes to a pipe or a file collects its text in a memory buffer and writes the buffer in chunks. When the program crashes before the buffer is flushed, the text is lost. In this lab, running without stdbuf printed nothing and exited with code 139. The stdbuf command turns off that buffering for the run, so every line appears before the crash. Writing std::endl instead of "\n" also flushes the output, which is another way to get the same effect in your own code.

The unbuffered run prints this:

stored words: in inn tea ten
expected:    in inn te tea ten
ok   search tea -> true (expected true)
FAIL search te -> false (expected true)
ok   search t -> false (expected false)
ok   search ten -> true (expected true)
ok   search in -> true (expected true)
ok   starts_with te -> true (expected true)

The program then stops with code 139. That is Bug 3, and it is covered below.

Bug 2: the end flag is set in the wrong place

The is_end flag is the only thing that tells the trie a word ends at a node. Many nodes exist only because a longer word passes through them. For example, the node for t, e exists because of "tea", but the word "te" only counts if the node for e has is_end set to true.

Look at the buggy insert. It sets the flag only in the branch that creates a new node. That branch runs only the first time a node is made. This gives two problems.

First, if a node already exists, the flag is never set. Trace "tea" followed by "te":

After "tea" and "te", the node for e has no flag. So "te" is lost. That is the missing end flag. It is the FAIL search te line in the output above.

Second, the code compares the letter with the last letter of the word, using c == word.back(). It should compare the position. The check asks whether this letter matches the last letter, which is not the same question. Trace "inn":

The middle n gets a flag, so the trie now holds "in", which was never inserted at this point. The line stored words: in inn tea ten shows this. The word "in" appears in the output. It is only there because the flag was set by accident. If "in" had not been inserted at all, it would still be reported as stored. You can check this with a short program that inserts only "inn". Its output is only inn inserted, stored: in inn, which is wrong because "in" was never inserted.

The fix is to set the flag once, after the loop, on the node that the last letter reached. That node is always the node for the whole word, whether it was created in this call or not:

void insert(const std::string& word) {
    TrieNode* node = root_.get();
    for (char c : word) {
        int idx = c - 'a';
        std::unique_ptr<TrieNode>& next = node->children.at(idx);
        if (!next) {
            next = std::make_unique<TrieNode>();
        }
        node = next.get();
    }
    node->is_end = true;
}

Compile and run this version:

g++ -std=c++20 -Wall -o trie_stage2 trie_lab.cpp
stdbuf -o0 ./trie_stage2

The output now shows every stored word correctly, and search te passes. The program still stops at the end, because of Bug 3.

stored words: in inn te tea ten
expected:    in inn te tea ten
ok   search tea -> true (expected true)
ok   search te -> true (expected true)
ok   search t -> false (expected false)
ok   search ten -> true (expected true)
ok   search in -> true (expected true)
ok   starts_with te -> true (expected true)

The stored words line now matches the expected line. Keep that comparison in mind. Checking the words the trie holds is often faster than checking each search result by hand.

Bug 3: a missing null check in search

The search function walks down the trie one letter at a time. At each step it moves to the child in the next slot. If that slot is empty, the child is nullptr. The buggy search moves to that null pointer and then reads from it on the next step.

Trace search("dog") in the buggy code. The root has no child for d in this trie, so node becomes nullptr after the first letter. The next letter is o. The code evaluates node->children, which reads a field through a null pointer. The operating system stops the program with a segmentation fault, a crash caused by reading memory the program may not use. On Linux the exit code is 139.

This bug only appears for words that are missing from the trie and whose path goes through an empty slot. The lab checks "tea", "te" and "ten", which all exist, so they never reach an empty slot. That is why the bug was hidden until "dog" and "xyz" were tested.

Look at starts_with. It already checks for null after each step. search needs the same check. Add it inside the loop, before the next step uses the pointer:

bool search(const std::string& word) const {
    const TrieNode* node = root_.get();
    for (char c : word) {
        node = node->children.at(c - 'a').get();
        if (node == nullptr) {
            return false;
        }
    }
    return node->is_end;
}

After the loop, node cannot be null, because a null value would have returned already. So reading node->is_end is safe.

Compile and run the final version:

g++ -std=c++20 -Wall -o trie_stage3 trie_lab.cpp
./trie_stage3

The program now prints every check and exits with code 0:

stored words: in inn te tea ten
expected:    in inn te tea ten
ok   search tea -> true (expected true)
ok   search te -> true (expected true)
ok   search t -> false (expected false)
ok   search ten -> true (expected true)
ok   search in -> true (expected true)
ok   starts_with te -> true (expected true)
ok   search dog -> false (expected false)
ok   search xyz -> false (expected false)

The three fixes are small. One formula changes in insert, the flag moves out of the loop in insert, and search gets a three-line check. Nothing else changed.

Two more examples

These examples use the same kind of bugs, with inputs that make them harder to see. Each one shows the message from a real run.

Example 1: a capital letter in the input

Insert the word "Cat" into a trie that expects lowercase letters. The code is the same as the fixed insert, with the word changed:

for (char c : word) {
    std::unique_ptr<TrieNode>& next = node->children.at(c - 'a');
    // ...
}

The first letter is 'C', which is code 67. The formula c - 'a' gives 67 - 97, which is -30. The at function takes an unsigned size, so the -30 turns into a very large positive number. The run prints:

terminate called after throwing an instance of 'std::out_of_range'
  what():  array::at: __n (which is 18446744073709551586) >= _Nm (which is 26)

The number 18446744073709551586 is 2 to the power of 64, minus 30. A huge index like this in the message usually means the index was negative. Two fixes are possible. You can convert the word to lowercase before inserting it, or you can reject any character outside a to z and report it to the caller. The choice depends on what the trie is for. A search box might lowercase the input. A stored dictionary might reject it.

Example 2: the last letter is one too far

A common off-by-one error uses c - 'a' + 1. It puts every letter one slot too far. The letter 'a' goes to slot 1, and the letter 'z' goes to slot 26, one past the end of an array of 26 slots. Insert the word "z" with that formula:

int idx = c - 'a' + 1;
std::unique_ptr<TrieNode>& next = node->children.at(idx);

The run prints:

terminate called after throwing an instance of 'std::out_of_range'
  what():  array::at: __n (which is 26) >= _Nm (which is 26)

The message says the index is 26 and the array size is 26. The index must be less than the size, so 26 is not valid.

The word "a" does not crash. It is stored in slot 1, and a search that uses the correct formula looks in slot 0 and does not find it. So a wrong index can hide without a crash, which is why the stored-words check in exercise 5 is useful.

Example 3: a traversal that reads a null child

The words function visits every node. It must skip empty slots. Suppose the null check in collect is removed:

for (int i = 0; i < 26; ++i) {
    const TrieNode* child = node->children[i].get();
    prefix.push_back(static_cast<char>('a' + i));
    collect(child, prefix, out);
    prefix.pop_back();
}

Save the lab's trie with the null check in collect removed as example_extra.cpp. Its main inserts only "cat" and prints words(). Compile with debugging information and AddressSanitizer:

g++ -std=c++20 -Wall -g -fsanitize=address -o example_extra_asan example_extra.cpp
./example_extra_asan

The report contains this line. The process number and addresses change on every run:

==266206==ERROR: AddressSanitizer: SEGV on unknown address 0x0000000000d0 (pc 0x55c6fe898653 bp 0x7ffc7a399030 sp 0x7ffc7a399000 T0)

The report then lists the call stack, the chain of functions that were running. The top frame is Trie::collect, on the line if (node->is_end). The next frame is Trie::collect again, on its recursive call (a function that calls itself). The line numbers in your report depend on your file. The final SUMMARY line names the same file and line. So the bad read is on node->is_end, and node was a null child passed in from the loop. The fix is the same null check as in Bug 3:

if (child == nullptr) {
    continue;
}

This is harder than the first two examples, because the crash is in a different function from the one that made the mistake. The line that caused it is the loop in collect, but the crash points to the first line of collect. Read the stack from the top, then look up to the caller to find the bad value.

This machine has no gdb installed, so the report above comes from AddressSanitizer. On a machine with gdb, running gdb -batch -ex run -ex bt ./program prints the same stack.

Common mistakes

Mixing up the two index bases. 'A' and 'a' are different codes. If insert uses one and search uses the other, a word is stored in one set of slots and searched in another. The first run of this lab stopped with the message array::at: __n (which is 51) >= _Nm (which is 26). The message named the slot, and the number told you the base was wrong.

Using [] where a check is needed. The [] operator may not check the index. With this compiler's standard library, an index of 26 causes an assertion that stops the program:

...Assertion '__n < this->size()' failed.

Other compilers may do something different, such as read memory outside the array. Use at while you learn the trie, so the error names the index and the size.

Setting the flag inside the create branch. The flag must be set after the loop, on the node for the whole word. Setting it inside the if (!next) branch skips nodes that already exist, and comparing letters with word.back() marks the wrong node when a letter repeats.

Checking null after using the pointer. node = node->children[i].get(); if (node == nullptr) is correct. Writing if (node->is_end) before the null check reads through a null pointer. The segmentation fault gives exit code 139 and no message from your code.

Returning the wrong thing at the end of search. return node != nullptr; is true for every node that exists in the trie, not only for words that were inserted. The output for "ca" shows this, and the exercise below asks you to find it.

Testing only words that exist. The buggy search passes every check for words in the trie. Add at least one word that is missing, and one that shares a prefix with a stored word but is not stored itself.

Practice

Each exercise has an answer. Try it on paper before you read the answer. Where a program is involved, the answer shows the output that the program printed.

Exercise 1

Start from the final version of insert and search in this lab. Insert "cat", then insert "ca". What does search("ca") return, and why does the "cat" insert not affect it?

Show the answer

search("ca") returns true. The first insert creates the nodes for c, a and t, and sets the flag on t. The node for a exists but has no flag at that point. The second insert walks the same nodes, finds them all, and sets the flag on the node for a after the loop. The flag on t is not changed. In a test program using the same logic, the output was ex1 search ca: true.

Exercise 2

Insert the words "bat", "b" and "bad" into a trie that uses the final insert. Print the result of words(). Write the exact output line.

Show the answer

The output is b bad bat. The b node is marked, so b comes first. Its child a is visited next. Under a, the child d comes before t because d has index 3 and t has index 19. A test program printed this line after a label.

Exercise 3

This version of search has one bug. Find it, and say what result it gives for "ca" after "cat" is inserted.

bool search(const std::string& word) const {
    const TrieNode* node = root_.get();
    for (char c : word) {
        const TrieNode* next = node->children[c - 'a'].get();
        if (next == nullptr) return false;
        node = next;
    }
    return node != nullptr;
}

Show the answer

The last line checks whether the node exists, not whether a word ends there. It should be return node->is_end;. For "ca" after "cat", the node for a exists, so the function returns true even though "ca" was never inserted. The test program printed ex3 buggy search ca: true. The same program printed false for "dog", because that path ends at a null slot.

Exercise 4

The insert function is changed to use int idx = c - 'a' + 1; and the word "z" is inserted into a trie with 26 slots. Write the message the program prints, and say why the index is wrong.

Show the answer

The program prints terminate called after throwing an instance of 'std::out_of_range' and then what(): array::at: __n (which is 26) >= _Nm (which is 26). The index for 'z' is 26, but the valid indexes are 0 to 25. Every other letter is also one slot too far, so the words stored in the trie are placed in the wrong slots even when no error is thrown.

Exercise 5

Add a check to main that compares the stored words with the list of words you inserted, so you do not have to read the output by eye. Write the code and the line it prints when the trie is correct.

Show the answer

Add this code before the first check call:

const std::vector<std::string> expected_words = {"in", "inn", "te", "tea", "ten"};
check(trie.words() == expected_words, true, "stored words match");

With the final trie, the line printed is ok stored words match -> true (expected true). The check fails with FAIL if the flag is set in the wrong place, because the word list then differs from the expected list.

Summary

• A message like array::at: __n (which is 51) >= _Nm (which is 26) gives the bad index and the array size, so you can find the formula that made the index.
• Set the end flag once, after the loop, on the node that the last letter reaches. Do not set it only when a node is created, and do not compare letters with word.back().
• Check for a null child before the next step uses it. A search for a missing word is the case that exposes a missing check.
• Compare the list of stored words with the list you inserted. A wrong flag shows up there even when every search answer looks right.
• Run with stdbuf -o0 or flush the output, or the lines printed before a crash are lost.