A C++ maintainer shipped an AI-authored merge_intervals patch on a Friday. Every golden file matched, and the CI badge stayed green. On Monday a caller passed the same ranges in a different order and the function returned overlapping pairs. The snapshots had all been pre-sorted. The model had learned the files, not the contract.
Static goldens still matter. They pin historical bugs. They do not survive a suite that leaked into prompts, gists, or fine-tunes, and they do not survive a generator that always emits the same shape of input. A relation grader treats those snapshots as a floor, then checks properties that stay true when the concrete lists change.
This article builds a small C++ eval harness around that split. It does not publish a leaderboard. It shows one way to catch silent failures that snapshot diffs miss.
What a metamorphic oracle actually checks
A snapshot says: for this exact input, emit this exact output. A metamorphic relation says: if the input is transformed in a known way, the outputs must stand in a known relationship. The second check does not need a stored answer key. It needs a generator, a transformation, and a comparison.
For interval merge, four relations are enough to start:
- Permutation invariance: shuffling the input list must not change the merged set.
- Idempotence: merging an already merged list must be a no-op.
- Measure preservation: the total covered length after merge equals the size of the union of the originals.
- Covering: every integer covered by an input interval is covered by some output interval, and the reverse.
A patch can fake (1) by sorting internally and still fail (3) if it drops a range. It can satisfy (3) with a sloppy union and still fail (4) if it emits a gap. The relations overlap on purpose.
Layout of the harness
Keep the candidate implementation separate from the oracle. The model may edit one translation unit. The driver, the generator, and the snapshot files stay outside the writable tree.
eval/
include/merge_intervals.hpp
candidate/merge_intervals.cpp
oracle/metamorphic_driver.cpp
goldens/case_001.in
goldens/case_001.out
tools/grade.sh
seeds/current.seed
The header is the contract. It stays short on purpose.
#pragma once
#include <utility>
#include <vector>
// Merges overlapping and touching [lo, hi) intervals.
// Empty input yields an empty vector. Output is sorted by lo and pairwise disjoint.
std::vector<std::pair<int, int>> merge_intervals(
std::vector<std::pair<int, int>> intervals);
A snapshot-only candidate that never sorts, and only walks the list in given order, will pass goldens that happen to be sorted. The metamorphic driver will not.
Step 1 — Pin three historical goldens
Goldens remain. They document bugs that already escaped once. They are not the whole spec.
goldens/case_001.in:
3
1 3
2 6
8 10
goldens/case_001.out:
2
1 6
8 10
Two further cases cover empty input and a single interval. The grader compares canonicalized text. Canonicalization sorts output pairs and rejects overlapping output as a snapshot failure too. That check is cheap. It is also leakable. Do not stop here.
Step 2 — Build a seeded generator
The generator must be deterministic given a seed, and cheap to rotate. A 64-bit integer in seeds/current.seed is enough. Changing the seed changes the concrete lists without changing the relations.
// oracle/metamorphic_driver.cpp (excerpt)
#include "merge_intervals.hpp"
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <random>
#include <set>
#include <string>
#include <vector>
using Iv = std::pair<int, int>;
static std::vector<Iv> gen_list(std::mt19937_64& rng, int n) {
std::uniform_int_distribution<int> pos(-50, 50);
std::vector<Iv> out;
out.reserve(static_cast<size_t>(n));
for (int i = 0; i < n; ++i) {
int a = pos(rng);
int b = pos(rng);
if (a > b) std::swap(a, b);
if (a == b) ++b; // keep half-open intervals non-empty
out.push_back({a, b});
}
return out;
}
The distribution is narrow so union measure stays inside a small integer set. Production suites should widen the domain and accumulate coverage in 64-bit arithmetic. This file is a teaching artifact, not a fuzzer budget.
Step 3 — Encode the four relations
Each relation returns a short reason on failure and an empty string on success. The driver fails closed. Any non-empty reason is a grade of zero.
static std::vector<Iv> normalize(std::vector<Iv> v) {
std::sort(v.begin(), v.end());
return v;
}
static bool same_set(std::vector<Iv> a, std::vector<Iv> b) {
return normalize(std::move(a)) == normalize(std::move(b));
}
static std::set<int> cover_points(const std::vector<Iv>& v) {
std::set<int> pts;
for (auto [lo, hi] : v) {
for (int x = lo; x < hi; ++x) pts.insert(x);
}
return pts;
}
static std::string check_one(std::vector<Iv> in, std::mt19937_64& rng) {
auto once = merge_intervals(in);
auto twice = merge_intervals(once);
if (!same_set(once, twice))
return "idempotence";
auto shuffled = in;
std::shuffle(shuffled.begin(), shuffled.end(), rng);
if (!same_set(merge_intervals(shuffled), once))
return "permutation";
if (static_cast<long long>(cover_points(once).size()) !=
static_cast<long long>(cover_points(in).size()))
return "measure";
if (cover_points(once) != cover_points(in))
return "cover";
for (size_t i = 1; i < once.size(); ++i) {
if (once[i].first < once[i - 1].second) return "overlap_in_output";
if (once[i].first < once[i - 1].first) return "unsorted_output";
}
return {};
}
cover_points enumerates integers in a tiny domain. That is intentional. It makes the oracle obviously correct. It does not scale to 10^9 coordinates. A sweep-line oracle belongs in a later gate, not in this first relation file.
A complete main keeps golden mode and relation mode in one binary so the compiler sees the same candidate object file for both stages.
int main(int argc, char** argv) {
std::uint64_t seed = 1;
int trials = 200;
std::string golden;
for (int i = 1; i < argc; ++i) {
std::string a = argv[i];
if (a == "--seed" && i + 1 < argc) seed = std::stoull(argv[++i]);
else if (a == "--trials" && i + 1 < argc) trials = std::stoi(argv[++i]);
else if (a == "--golden" && i + 1 < argc) golden = argv[++i];
}
if (!golden.empty()) {
int n = 0;
if (!(std::cin >> n) && n != 0) return 2;
std::vector<Iv> in(static_cast<size_t>(n));
for (int i = 0; i < n; ++i) std::cin >> in[i].first >> in[i].second;
auto out = merge_intervals(in);
std::cout << out.size() << "\n";
for (auto [lo, hi] : out) std::cout << lo << " " << hi << "\n";
return 0;
}
std::mt19937_64 rng(seed);
for (int t = 0; t < trials; ++t) {
int n = static_cast<int>(rng() % 8);
auto in = gen_list(rng, n);
auto reason = check_one(in, rng);
if (!reason.empty()) {
std::cerr << "FAIL relation=" << reason << " trial=" << t << "\n";
for (auto [lo, hi] : in) std::cerr << lo << " " << hi << "\n";
return 1;
}
}
return 0;
}
Silent assert macros disappear under some build flags. A printed relation name is the grade the eval operator actually reads.
Step 4 — Grade snapshots, then relations
The shell grader compiles the candidate, runs goldens, then runs the driver with the current seed. A green snapshot stage never skips the second stage.
#!/usr/bin/env bash
# tools/grade.sh
set -euo pipefail
ROOT="$(cd "$(dirname "$0")/.." && pwd)"
CXX="${CXX:-c++}"
CXXFLAGS="-std=c++17 -O1 -Wall -Wextra -Werror"
SEED="$(cat "$ROOT/seeds/current.seed")"
mkdir -p "$ROOT/build"
$CXX $CXXFLAGS -I "$ROOT/include" \
"$ROOT/candidate/merge_intervals.cpp" \
"$ROOT/oracle/metamorphic_driver.cpp" \
-o "$ROOT/build/driver"
for case in "$ROOT/goldens"/*.in; do
base="${case%.in}"
"$ROOT/build/driver" --golden "$case" < "$case" > "$ROOT/build/got.out"
diff -u "${base}.out" "$ROOT/build/got.out"
done
"$ROOT/build/driver" --seed "$SEED" --trials 200
echo "PASS seed=$SEED"
Store the seed next to the grade, not only in CI logs. A failing run that cannot be replayed is not an eval. It is a rumor.
Step 5 — Rotate the seed without rewriting the spec
Eval leakage is an engineering problem, not a slogan. Once a prompt, a golden file, or a public gist exists, a later model can echo the answers. Rotating the seed keeps the relations stable and the concrete cases fresh. A one-line write is the whole policy.
python3 - <<'PY'
import secrets
open("eval/seeds/current.seed", "w").write(str(secrets.randbits(64)))
PY
Replay uses the failed seed, not a new one. Rotation belongs between published eval batches, not between a crash and the debug rerun.
Snapshot vs relation vs sanitizer
The three gates catch different lies. Run them in that order so a compile error is not mistaken for a relation miss.
| Gate | Catches | Misses |
|---|---|---|
| Historical snapshots | Exact bugs that already shipped | Unseen input shapes, leaked answer keys |
| Metamorphic relations | Order dependence, dropped coverage, non-idempotent merge | Values outside the generator domain |
| ASan/UBSan | Out-of-bounds, signed overflow, use-after-free | Wrong-but-defined output |
No percentage in that table is a model score. It is a reminder of what each gate cannot see.
A patch that fools snapshots
The following candidate is the Friday patch. It assumes sorted input. It is short, and it is wrong.
#include "merge_intervals.hpp"
std::vector<std::pair<int, int>> merge_intervals(
std::vector<std::pair<int, int>> intervals) {
if (intervals.empty()) return {};
std::vector<std::pair<int, int>> out{intervals.front()};
for (size_t i = 1; i < intervals.size(); ++i) {
if (intervals[i].first <= out.back().second)
out.back().second = std::max(out.back().second, intervals[i].second);
else
out.push_back(intervals[i]);
}
return out;
}
Against case_001 this returns 1 6 and 8 10. The snapshot stage is green. Against a shuffled list the permutation relation fires. That is the entire point of stage B. No coverage percentage is required to see it.
A correct candidate sorts first, then sweeps. The relations do not encode that algorithm. They only reject results that violate the contract. Two different correct sweeps should both pass.
Where a hosted codegen path fits
A local compiler remains the grader. The model only proposes candidate/merge_intervals.cpp. When the eval operator wants that proposal loop without standing up a GPU box, MonkeyCode's free model access and free server option can host the generate-and-grade cycle. Disclosure: This article was prepared as part of MonkeyCode's product outreach. The harness above does not depend on that host. It runs under any c++ that speaks C++17. Product quotas, model names, and hardware are out of scope here because they change, and because the grade is a compiler result, not a vendor score.
The useful split is simple. Generation may be remote. Judgment stays local: compile, snapshot diff, relation driver, recorded seed.
Limitations
The integer cover-set oracle is O(width × n). It is a teaching device. It will not grade 64-bit map ranges. Floating-point intervals need a different measure. Touching versus overlapping is a spec choice; this header treats touching as mergeable because hi is exclusive and a.hi == b.lo means adjacent coverage. A library that wants a gap there must change the relation, not the seed.
Metamorphic checks do not replace negative compilation tests, sanitizer matrices, or ABI dumps. They also do not prove partial correctness. A function that always returns the empty vector fails measure and cover, but a function that merges correctly on this generator's narrow distribution can still fail on INT_MIN. Widen the generator before treating a pass as evidence.
Seed rotation does not defeat a model that has learned the relations themselves. If the prompt pastes this article into context, the candidate may sort, then sweep, then pass. That is a real ceiling. Held-out relations, a second-language shadow oracle, and human review of failing lists are the next layers. This file does not pretend to include them.
Duplicate empty ranges can hide if an oracle canonicalizes too aggressively. The normalize helper above sorts pairs; it does not drop zeros, because empty [lo, lo) intervals are already forbidden by the generator. An API that allows empty ranges needs an extra relation that states that policy in one place.
Who should not use this approach
Do not use this harness as a production fuzzer for untrusted patches that must not run on the eval host. The driver executes candidate code. Sandbox that process separately. Do not use cover-point enumeration on large domains. Do not treat a PASS on 200 trials as a proof. Do not drop historical goldens; relations miss some exact-output regressions that snapshots catch, such as an extra diagnostic interval that still covers the same points after a sloppy canonicalize.
Teams that only need a yes/no compile gate should stay on the compiler. Teams that already leak every golden into public prompts should rotate more than the seed: they should rotate the function under test.
The relation grader is a small gate, and it is honest about that. Operators who already compile patches on a free-server workflow can drop tools/grade.sh beside the candidate file and read PASS seed=... as the only score that matters.
Top comments (0)