catch3
Progmasoft Catch3: an independently maintained C++17 test framework with a parallel runner, property checks, snapshots and structured results.
Clonegit clone https://git.progmasoft.com/catch3
develroot / src / Progmasoft / ChoiceShrinker.cpp
// Copyright (c) 2026 Progmasoft.
// SPDX-License-Identifier: LGPL-3.0-or-later
#include <Progmasoft/Catch3/Strategy/Engine.hpp>
#include <algorithm>
#include <array>
#include <charconv>
#include <cstddef>
#include <cstdint>
#include <string>
#include <utility>
namespace Progmasoft::Catch3::Detail
{
bool
IsSimpler(const std::vector<std::uint64_t> &candidate,
const std::vector<std::uint64_t> ¤t) noexcept
{
if (candidate.size() != current.size())
{
return candidate.size() < current.size();
}
return std::lexicographical_compare(
candidate.begin(), candidate.end(), current.begin(), current.end());
}
namespace
{
constexpr std::string_view kTokenPrefix = "c3.";
/// Replays candidates against the current best and keeps the
/// simplest failing one. Every replay counts against the budget.
class Shrinker final
{
public:
using StillFails
= std::function<std::optional<std::vector<std::uint64_t>>(
const std::vector<std::uint64_t> &)>;
Shrinker(std::vector<std::uint64_t> failing,
std::size_t budget,
const StillFails &stillFails)
: current_(std::move(failing))
, budget_(budget)
, stillFails_(stillFails)
{}
[[nodiscard]] std::vector<std::uint64_t>
Run(std::size_t &calls)
{
bool improved = true;
while (improved && !Spent())
{
improved = false;
improved |= DeleteBlocks();
improved |= ZeroBlocks();
improved |= MinimizeChoices();
improved |= SortNeighbours();
improved |= MoveBetweenNeighbours();
}
calls = calls_;
return current_;
}
private:
static constexpr std::array<std::size_t, 5> kBlockSizes
= { 16, 8, 4, 2, 1 };
[[nodiscard]] bool
Spent() const noexcept
{
return calls_ >= budget_;
}
/// Replays a candidate; true when it fails and the sequence it
/// consumed is simpler than the current one, which it replaces.
bool
Try(const std::vector<std::uint64_t> &candidate)
{
if (Spent() || !IsSimpler(candidate, current_))
{
return false;
}
++calls_;
auto consumed = stillFails_(candidate);
if (!consumed.has_value() || !IsSimpler(*consumed, current_))
{
return false;
}
current_ = std::move(*consumed);
return true;
}
bool
DeleteBlocks()
{
bool improved = false;
for (const std::size_t block : kBlockSizes)
{
// From the end, so that a deletion does not move the
// blocks still to be tried.
for (std::size_t index = current_.size();
index-- > 0 && !Spent();)
{
if (index + block > current_.size())
{
continue;
}
auto candidate = current_;
candidate.erase(
candidate.begin()
+ static_cast<std::ptrdiff_t>(index),
candidate.begin()
+ static_cast<std::ptrdiff_t>(index + block));
improved |= Try(candidate);
}
}
return improved;
}
bool
ZeroBlocks()
{
bool improved = false;
for (const std::size_t block : kBlockSizes)
{
for (std::size_t index = 0;
index + block <= current_.size() && !Spent();
++index)
{
const auto first = current_.begin()
+ static_cast<std::ptrdiff_t>(index);
if (std::all_of(first,
first
+ static_cast<std::ptrdiff_t>(block),
[](std::uint64_t value) {
return value == 0;
}))
{
continue;
}
auto candidate = current_;
std::fill_n(candidate.begin()
+ static_cast<std::ptrdiff_t>(index),
block,
0U);
improved |= Try(candidate);
}
}
return improved;
}
/// Lowers each choice as far as the failure allows, assuming
/// that a smaller choice is usually still failing when a larger
/// one is: a binary search between 0 and the current value.
bool
MinimizeChoices()
{
bool improved = false;
for (std::size_t index = 0;
index < current_.size() && !Spent();
++index)
{
std::uint64_t high = current_[index];
if (high == 0)
{
continue;
}
if (TryValue(index, 0))
{
improved = true;
continue;
}
std::uint64_t low = 0;
while (low + 1U < high && !Spent()
&& index < current_.size())
{
const std::uint64_t middle = low + (high - low) / 2U;
if (TryValue(index, middle))
{
high = middle;
improved = true;
}
// Binary search assumes that failures are monotone
// in the choice; a filter or a parity condition
// breaks that, so the neighbour gets a chance too:
// with only even values passing a filter, an odd
// middle would otherwise stop the search.
else if (middle + 1U < high
&& TryValue(index, middle + 1U))
{
high = middle + 1U;
improved = true;
}
else
{
low = middle + 1U;
}
}
// A few single steps below the result, once: 104 -> 102
// when only even values pass. The next round of passes
// repeats the search from there.
for (std::uint64_t step = 1; step <= 8 && !Spent()
&& index < current_.size()
&& current_[index] >= step;
++step)
{
if (TryValue(index, current_[index] - step))
{
improved = true;
break;
}
}
}
return improved;
}
bool
TryValue(std::size_t index, std::uint64_t value)
{
if (index >= current_.size() || current_[index] <= value)
{
return false;
}
auto candidate = current_;
candidate[index] = value;
return Try(candidate);
}
bool
SortNeighbours()
{
bool improved = false;
for (std::size_t index = 0;
index + 1U < current_.size() && !Spent();
++index)
{
if (current_[index] <= current_[index + 1U])
{
continue;
}
auto candidate = current_;
std::swap(candidate[index], candidate[index + 1U]);
improved |= Try(candidate);
}
return improved;
}
/// Moves one unit from a choice to one of the next few: the
/// sequence gets lexicographically smaller while a sum such as
/// x + y > 10 keeps failing.
bool
MoveBetweenNeighbours()
{
bool improved = false;
for (std::size_t index = 0;
index < current_.size() && !Spent();
++index)
{
for (std::size_t offset = 1;
offset <= 4 && index + offset < current_.size()
&& !Spent();
++offset)
{
if (current_[index] == 0
|| current_[index + offset] == UINT64_MAX)
{
break;
}
auto candidate = current_;
--candidate[index];
++candidate[index + offset];
improved |= Try(candidate);
}
}
return improved;
}
std::vector<std::uint64_t> current_;
std::size_t budget_;
std::size_t calls_ = 0;
const StillFails &stillFails_;
};
} // namespace
std::vector<std::uint64_t>
ShrinkChoices(
std::vector<std::uint64_t> failing,
std::size_t budget,
const std::function<std::optional<std::vector<std::uint64_t>>(
const std::vector<std::uint64_t> &)> &stillFails,
std::size_t &calls)
{
Shrinker shrinker(std::move(failing), budget, stillFails);
return shrinker.Run(calls);
}
std::string
EncodeChoices(std::size_t size, const std::vector<std::uint64_t> &choices)
{
// c3.<size>.<choice>-<choice>-... with each number in base 36: short
// enough to paste from a CI log, and only characters that survive
// shells and C++ string literals unescaped.
std::string token(kTokenPrefix);
std::array<char, 24> buffer{};
const auto append = [&](std::uint64_t value) {
const auto end = std::to_chars(
buffer.data(), buffer.data() + buffer.size(),
value, 36)
.ptr;
token.append(buffer.data(), end);
};
append(size);
token += '.';
for (std::size_t index = 0; index < choices.size(); ++index)
{
if (index != 0)
{
token += '-';
}
append(choices[index]);
}
return token;
}
std::optional<DecodedChoices>
DecodeChoices(std::string_view token)
{
if (token.substr(0, kTokenPrefix.size()) != kTokenPrefix)
{
return std::nullopt;
}
token.remove_prefix(kTokenPrefix.size());
const auto parse = [](std::string_view text)
-> std::optional<std::uint64_t> {
std::uint64_t value = 0;
const auto result = std::from_chars(
text.data(), text.data() + text.size(), value, 36);
if (text.empty() || result.ec != std::errc()
|| result.ptr != text.data() + text.size())
{
return std::nullopt;
}
return value;
};
const auto dot = token.find('.');
if (dot == std::string_view::npos)
{
return std::nullopt;
}
const auto size = parse(token.substr(0, dot));
if (!size.has_value() || *size > 100U)
{
return std::nullopt;
}
DecodedChoices decoded;
decoded.Size = static_cast<std::size_t>(*size);
std::string_view rest = token.substr(dot + 1U);
while (!rest.empty())
{
const auto dash = rest.find('-');
const auto value = parse(rest.substr(0, dash));
if (!value.has_value())
{
return std::nullopt;
}
decoded.Choices.push_back(*value);
if (dash == std::string_view::npos)
{
break;
}
rest.remove_prefix(dash + 1U);
if (rest.empty())
{
return std::nullopt;
}
}
return decoded;
}
} // namespace Progmasoft::Catch3::Detail