Module 5 — Debugging¶

This module produces the first failure in the course that the compiler cannot see. A comparator that is not a strict weak ordering compiles, runs, and gives an answer — sometimes the right one. The technique that finds it is to stop testing the sort and start testing the relation.

The technique this module adds¶

Test the comparator as a relation, not through an algorithm¶

std::sort is a terrible instrument for finding a bad comparator. It is allowed to do anything, including look correct on the input you happen to have. Ask the properties directly instead:

// test_comparator.cpp — the whole technique, in twelve lines
std::vector<Book> sample{Book(1, "a"), Book(2, "b"), Book(2, "b"), Book(3, "c"),
                         Book(3, "c"), Book(4, "d")};

for (const Book& a : sample) {
    assert(!(a < a));                       // 1. irreflexive
    for (const Book& b : sample) {
        assert(!(a < b) || !(b < a));       // 2. asymmetric
        if (a < b) {
            for (const Book& c : sample) {
                if (b < c) {
                    assert(a < c);          // 3. transitive
                }
            }
        }
    }
}

Twenty lines, no algorithm involved, and it fails loudly on the exact bug that std::sort hides. Include a duplicate in the sample — Book(2, "b") appears twice above on purpose. A comparator that uses <= passes every test on a sample of distinct values.

Instrument the comparison¶

When you do not know whether the problem is the comparator or the algorithm, count:

bool operator<(const Book& other) const {
    ++comparisons;                          // a static counter, Module 5's other half
    assert(title_ != other.title_ || id_ < other.id_);   // fires when `a < a`
    return id_ < other.id_;
}

The counter also answers a design question: sort 1,000 books and read the number. It should be roughly n log n — tens of thousands, not millions. A comparator that copies its parameter (bool operator<(Book other)) shows up here as a time cost that scales with the size of Book, not with n.

Read template errors from the bottom¶

std::sort's error messages are forty lines of library internals with the useful error: at the end. The pattern is always the same:

error: no match for 'operator<' (operand types are 'Book' and 'Book')

That last line names the missing operation. If instead you see a wall of note: lines about _Compare, __first and predefined_ops.h, read the first error: and the last error: and ignore the middle.

The routine¶

Write the comparator's sentence. "Two books are ordered by identifier." If the sentence needs an "and", you have more than one order and the second one belongs somewhere else (§11 of Concepts).
Test it against the three properties, with a duplicate in the sample.
Count the comparisons if the answer differs from expectation — that distinguishes a wrong rule from a wrong signature.
Only then run the sort, on a list whose order you can verify by hand.
Look for the second place. == and < and printing all encode what identity means. A bug in one is usually a disagreement with another.

The three failures this module produces¶

Failure A — works, and is wrong¶

Symptom. The sort produces an order. It is not the order you wanted, and on a second run it is a different wrong order.

Cause. The comparator is not a strict weak ordering. In practice this is almost always <= instead of <, or a comparison of several fields where one of them is compared with <=.

What to do. Apply the reference/property test above. Then fix the rule, not the call site: adding std::stable_sort or sorting twice makes the symptom move.

Failure B — the type is consistent with itself and not with the caller¶

Symptom. std::find returns nothing, although the element is visibly in the list. Or two items "equal by ==" print differently.

Cause. == compares identifiers; printing shows the title; std::map uses < which compares titles. Three different notions of identity in one type.

What to do. Write the sentence, pick one, and make all three use it. If you genuinely need two orders (by identifier and by title), overload < for the natural one and pass the other explicitly:

std::sort(books.begin(), books.end(), [](const Book& a, const Book& b) {
    return a.title() < b.title();
});

That is the honest way to have two orders: one is the type's, the others are the caller's, and the call site says which.

Failure C — the linker, not the compiler¶

Symptom. Everything compiles. The link fails, naming something that clearly exists in a header.

Cause. A static data member declared and never defined, or a member function declared and never defined in a .cpp.

What to do. Read the name in the error: it tells you exactly which declaration has no definition. Add the definition, or make the member inline (C++17).

# to confirm it is a link problem and not a compile problem:
g++ -std=c++17 -Wall -Wextra -c main.cpp -o main.o    # succeeds
g++ main.o -o main                                    # fails, and names the symbol

The escalation ladder¶

Rung 1 is where you start; go further only when the one you are on does not work. This module works at rungs 2, 5 and 6 unusually often.

Rung 1 — State the invariant out loud¶

For this module: "< orders books by identifier, and two books with the same identifier are equivalent." If you cannot say it, the comparator has no rule to be wrong about.

Rung 2 — Check the failure's class¶

Three classes, three different instincts:

Class	Sign	Your instinct
compile error	the program does not exist	read the last `error:`; usually a missing operator or a wrong operand
link error	it compiled, the program does not exist	a declaration with no definition
wrong answer	it runs, the answer is wrong	the relation is wrong, or two notions of identity disagree

Rung 3 — Reduce to the smallest type that has the problem¶

Ten lines: one class, one field, an operator<, and a main that sorts three values including a duplicate. If the bug survives, you have found it. If it does not, the bug is in the fields you left out.

Rung 4 — Ask the compiler and the library¶

-Wall -Wextra catches the signature mistakes: a missing const, an override that does not override, a missing case.
assert catches the property mistakes: an irreflexive comparator, a relation that is not transitive.
The library's own debug modes are not required for this module; property tests are cheaper and they name your comparator in the message.

Rung 5 — Chase the disagreement, not the symptom¶

If two things disagree about identity, fix the definition of identity and let both places follow it. Adding a special case at one call site makes the two definitions drift further apart.

Rung 6 — Say the comparison in words¶

"I am saying that a comes before b if a's title is less than or equal to b's title." Say it out loud and the bug is audible: less than or equal**. This rung is unusually effective in this module, and costs twenty seconds.

Rung 7 — Ask for a design review, with the sample¶

Bring the comparator, the sentence, and the failing sample. A reviewer who sees <= will say so in one second; a reviewer given "the sort does not work" has to reconstruct everything you already know.

Rung 8 — When the problem is downstream¶

If the comparator is provably correct and the wrong order still appears, the values being compared are not what you think. Print both sides inside the comparator once, check the field that is out of place, and then remove the print — a comparator that writes to std::cout is itself a bug, because it runs hundreds of thousands of times inside an algorithm.

What good looks like, at this point in the course¶

By the end of this module you should be able to:

look at a std::sort error and name the missing operator from the last line;
say whether a given operator must be a member, without looking it up, because you asked "what is the left operand?";
write a comparator with const, const&, and < as reflexes;
test a comparator in twenty lines instead of debugging a sort for an hour;
spot a static member's missing definition from a link error;
see static in a signature and know which of its three meanings is in play.

Next: Exercises — three tiers, each with its level and its observable success criterion. · All modules