96 lines
3.1 KiB
C++
96 lines
3.1 KiB
C++
/*
|
|
* Copyright (C) 2024-present ScyllaDB
|
|
*/
|
|
|
|
/*
|
|
* SPDX-License-Identifier: LicenseRef-ScyllaDB-Source-Available-1.0
|
|
*/
|
|
|
|
#include <vector>
|
|
#include <utility>
|
|
#include "utils/assert.hh"
|
|
|
|
#pragma once
|
|
|
|
// We'd like to test edge cases in the sstable reader,
|
|
// related to the handling of inexact index answers.
|
|
// (I.e. a BTI index query may return a result off by one partition
|
|
// and the reader has to handle that).
|
|
//
|
|
// Triggering those edge cases might require a specific sequence of calls to the reader
|
|
// (e.g. advancing the reader to a range, and then advancing it to a later range which
|
|
// touches the first one)
|
|
// combined with a specific sequence of answers from the index
|
|
// (e.g. first answer being accurate and second answer being off by one).
|
|
//
|
|
// Open-coding an exhaustive list of such scenarios is impractical.
|
|
// But we can write the test in a nondeterministic form:
|
|
//
|
|
// 1. Whenever queried, let the index return *some* answer within the contract.
|
|
// 2. Advance the reader to *some* range, check output.
|
|
// 3. If possible, advance the reader to *some* range later than the first one, check output.
|
|
//
|
|
// and drive this syntax by rerunning the test scenario with
|
|
// all possible values for *some* explored.
|
|
//
|
|
// This is an API for writing such nondeterministic tests.
|
|
//
|
|
// The intended usage is:
|
|
//
|
|
// ```
|
|
// nondeterministic_choice_stack ncs;
|
|
// do {
|
|
// switch (ncs.choose_up_to(3)) {
|
|
// // Fork the test scenario into 3 possible paths...
|
|
// ...
|
|
// }
|
|
// } while (ncs.rewind());
|
|
// ```
|
|
class nondeterministic_choice_stack {
|
|
std::vector<std::pair<int, bool>> choices;
|
|
int next_frame = 0;
|
|
public:
|
|
// Nondeterministically choose a non-negative integer.
|
|
// This should be followed by mark_last_choice() if
|
|
// the returned integer is the maximum value which should be chosen.
|
|
//
|
|
// Can be used if the number of possible choices isn't known in advance.
|
|
// For most uses, choose_up_to(n) is powerful enough, and is easier to use.
|
|
int choose() {
|
|
if (next_frame >= int(choices.size())) {
|
|
choices.emplace_back(0, false);
|
|
} else if (next_frame + 1 == int(choices.size())) {
|
|
choices.back().first += 1;
|
|
}
|
|
return choices[next_frame++].first;
|
|
}
|
|
// Mark the last `choose()` fork as fully explored.
|
|
void mark_last_choice() {
|
|
SCYLLA_ASSERT(next_frame > 0);
|
|
if (next_frame != int(choices.size())) {
|
|
SCYLLA_ASSERT(choices[next_frame - 1].second);
|
|
}
|
|
choices[next_frame - 1].second = true;
|
|
}
|
|
// Nondeterministically choose an integer in range [0, n]
|
|
int choose_up_to(int n) {
|
|
int result = choose();
|
|
if (result >= n) {
|
|
mark_last_choice();
|
|
}
|
|
return result;
|
|
}
|
|
// Nondeterministically choose a boolean.
|
|
bool choose_bool() {
|
|
return choose_up_to(1);
|
|
}
|
|
// Proceed to the next iteration of the test.
|
|
bool rewind() {
|
|
while (!choices.empty() && choices.back().second) {
|
|
choices.pop_back();
|
|
}
|
|
next_frame = 0;
|
|
return choices.size() > 0;
|
|
}
|
|
};
|