The Empty Input Wrapped the Loop Bound

The hang was not a deadlock. It was unsigned wrap in a size check.

An empty vector made size() - 1 explode. The loop then treated empty as huge. Have you audited every size() - 1 on a hot path?

I had not. I trusted English that only holds for nonempty ranges.

The symptom

The pairwise merge never returned on one fixture. CPU sat on a single core.

I expected a mutex in gdb. I found a for-loop instead. Why did empty input look busy?

No syscall. No futex. Just i climbing forever.

The reduced repro

I cut the helper out of the larger merge. The snippet compiled clean under -Wall.

This is a lab repro, not a production dump. I kept the types honest.

// lab repro: empty input, unsigned bound
#include <cstddef>
#include <cstdio>
#include <vector>

void pairwise_merge(std::vector<int>& items) {
    for (std::size_t i = 0; i < items.size() - 1; ++i) {
        items[i] += items[i + 1];
    }
}

int main() {
    std::vector<int> empty;
    std::fprintf(stderr, "size=%zu\n", empty.size());
    pairwise_merge(empty);
    std::fprintf(stderr, "returned\n");
}

Looks harmless, right? Two items merge. One item is a no-op.

Empty should also no-op. Empty does not no-op. Empty wraps.

Debugging steps

I treated this like any other hang. I did not start with a model.

I started with a frozen process and a printed bound.

1. Freeze the process, not the theory

Build without optimizations first. You want a readable bt.

g++ -std=c++17 -g -O0 -Wall -Wextra -o merge_hang merge_hang.cpp
./merge_hang

In another terminal, attach and ask where time went.

gdb -p "$(pgrep merge_hang)"
(gdb) bt
(gdb) info locals

bt showed the for-loop. i was already enormous. Still no lock.

2. Print the bound, not the body

I logged items.size() and the compared bound. Empty printed 0.

The bound printed a monster on 64-bit. That is the whole bug.

auto n = items.size();
auto bound = n - 1;
std::fprintf(stderr, "n=%zu bound=%zu\n", n, bound);

n=0. bound=18446744073709551615. That value is SIZE_MAX.

See the problem now? The < compare almost never fails.

3. Write a tripwire, not a timed test

A hang is a bad test oracle. I capped dummy steps instead.

#include <cassert>
#include <cstddef>
#include <vector>

int main() {
    std::vector<int> empty;
    std::size_t steps = 0;
    for (std::size_t i = 0; i < empty.size() - 1; ++i) {
        ++steps;
        if (steps > 8) {
            break;
        }
    }
    assert(steps == 0); // fires: unsigned compare never dies
}

The assert fired after eight dummy steps. Empty was never a no-op.

4. Ask which type did the minus

vector::size() returns size_t. size_t is unsigned.

0u - 1u wraps. The loop condition stays true for a long time.

Would a signed int have survived empty? Yes, until INT_MAX.

Different bomb. Same sloppy bound. Same missing empty case.

Root cause

The author wrote a pairwise loop. The author meant "last index".

That English only holds when size() >= 1. Empty breaks the English.

Humans emit this pattern. Models emit it too. -Wall stayed quiet.

The later items[i + 1] would be the crash. On empty you may never get there.

You just spin. Sanitizers do not always shout at the compare itself.

The fix

Guard the size before you subtract. Do not subtract from zero.

Prefer i + 1 < n over i < n - 1. Empty then does nothing.

void pairwise_merge(std::vector<int>& items) {
    if (items.size() < 2) {
        return;
    }
    for (std::size_t i = 0; i + 1 < items.size(); ++i) {
        items[i] += items[i + 1];
    }
}

Is i + 1 itself a wrap risk? Only if i is already SIZE_MAX.

A vector cannot hold that many elements. The loop condition dies first.

Decision table

I now keep this table next to unsigned loops. Empty is column one.

Check	Empty	One item	Many items	Wrap risk
i < n - 1	spin or OOB	no-op	OK	yes on empty
i + 1 < n	no-op	no-op	OK	no in practice
n >= 2 then i < n - 1	no-op	no-op	OK	no
signed int and n - 1	no-op	no-op	OK until huge n	different overflow

I grep for size() - 1 in reviews. I read the empty path first.

rg -n "size\(\)\s*-\s*1" --type cpp
rg -n "\.count\(\)\s*-\s*1" --type cpp

If the hit sits in a loop header, I add three fixtures. Empty. Singleton. Two-plus.

Compile the tripwire under sanitizers

The compare can look defined. The later index may not.

Run AddressSanitizer and UndefinedBehaviorSanitizer on the real helper.

g++ -std=c++17 -O1 -g -fsanitize=address,undefined -o merge_ok merge_ok.cpp
./merge_ok

Empty must return. Singleton must return. Two items must merge once.

If any fixture hangs, the patch is wrong. Do not argue with the tripwire.

A second list of nearby bounds

I wanted sibling greps after the fix landed. I did not want a vibe rewrite.

I used MonkeyCode's free model access and free server option to draft nearby unsigned bounds. Disclosure: This article was prepared as part of MonkeyCode's product outreach.

The useful output was not a new helper. It was a list: end - 1, count - 1, len - 1 on size_t.

I kept the list. I threw away the prose. Then I compiled every candidate against the tripwire.

The model does not run your sanitizer. You do. Free access does not change that.

Iterator form when the index is the smell

I now skip unsigned index math when an iterator pair is enough. Empty becomes boring.

#include <iterator>
#include <vector>

void pairwise_merge(std::vector<int>& items) {
    if (items.size() < 2) {
        return;
    }
    for (auto it = items.begin(); std::next(it) != items.end(); ++it) {
        *it += *std::next(it);
    }
}

Longer. Clearer. The empty path does not invent SIZE_MAX.

Would I still use indexes for cache locality notes? Yes, with i + 1 < n.

What this method will not do

Do not use a model as the oracle for a hang. A hang needs a debugger.

A model needs a failing test. Comments do not wrap. Types do.

Skip this workflow if you cannot run ASan. Skip it if the loop is generated and untestable.

Skip it if you already iterate begin to end without a minus. Those loops usually die cleanly on empty.

Unsigned wrap is silent. -Wall stayed quiet on my first build.

So the test must cover empty, singleton, and two-plus. Three cases. Not one happy path.

Did the original loop include those cases? No. That is the whole story.

If you want a second grep list for size() - 1, free model access is enough for a draft. Compile the tripwire yourself.