100 tasks from the HWE arm-linux code-gen pool (outside the lk/man/pth range given to batch 22), each with at least one independent contract-edge defect and plain public docs. Claude reviewed 100/100 USABLE against current digests; no ID or source overlap with main or batch 22. Difficulty is unmeasured. progress.md records the wrap-up: all Codex sessions and Qwen schedulers stopped for the user's rollout, Qwen results so far (57 HARD of 373), and what is left on each batch branch. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
773 lines
21 KiB
C++
773 lines
21 KiB
C++
#include "audit.hpp"
|
|
#include <algorithm>
|
|
#include <array>
|
|
#include <cstddef>
|
|
#include <fstream>
|
|
#include <map>
|
|
#include <queue>
|
|
#include <set>
|
|
#include <tuple>
|
|
#include <utility>
|
|
#include <vector>
|
|
|
|
namespace {
|
|
enum Status {
|
|
OK = 0,
|
|
RANGE = 1,
|
|
EXISTS = 2,
|
|
MISSING = 3,
|
|
FULL = 4,
|
|
BUSY = 5,
|
|
OWNER = 6,
|
|
CYCLE = 7,
|
|
INVALID = 8
|
|
};
|
|
using Result = std::vector<long long>;
|
|
using Node = std::pair<int, int>;
|
|
using Edge = std::array<int, 4>;
|
|
|
|
bool id_ok(int value) {
|
|
return value >= 1 && value <= 1000000;
|
|
}
|
|
|
|
class Graph {
|
|
public:
|
|
explicit Graph(int size) : arcs(size) {}
|
|
|
|
bool direct(int from, int to) const {
|
|
return arcs[from].count(to) != 0;
|
|
}
|
|
|
|
void insert(int from, int to) {
|
|
arcs[from].insert(to);
|
|
}
|
|
|
|
void retire(int vertex) {
|
|
arcs[vertex].clear();
|
|
for (auto& successors : arcs) {
|
|
successors.erase(vertex);
|
|
}
|
|
}
|
|
|
|
void clear() {
|
|
for (auto& successors : arcs) {
|
|
successors.clear();
|
|
}
|
|
}
|
|
|
|
bool reaches(int from, int to) const {
|
|
std::set<int> visited;
|
|
std::queue<int> frontier;
|
|
frontier.push(from);
|
|
while (!frontier.empty()) {
|
|
int current = frontier.front();
|
|
frontier.pop();
|
|
if (!visited.insert(current).second) {
|
|
continue;
|
|
}
|
|
if (current == to) {
|
|
return true;
|
|
}
|
|
for (int next : arcs[current]) {
|
|
if (!visited.count(next)) {
|
|
frontier.push(next);
|
|
}
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
private:
|
|
std::vector<std::set<int>> arcs;
|
|
};
|
|
|
|
struct Instance {
|
|
int key = 0;
|
|
int owner = 0;
|
|
int subclass = -1;
|
|
long long ticket = 0;
|
|
};
|
|
|
|
struct History {
|
|
long long acquired = 0;
|
|
long long released = 0;
|
|
long long aborted = 0;
|
|
long long next_ticket = 1;
|
|
};
|
|
}
|
|
|
|
struct Audit {
|
|
int class_limit;
|
|
int instance_limit;
|
|
int thread_limit;
|
|
int subclass_limit;
|
|
int depth_limit;
|
|
std::map<int, int> classes;
|
|
std::map<int, Instance> instances;
|
|
std::vector<std::vector<int>> held;
|
|
Graph graph;
|
|
History history;
|
|
|
|
Audit(int c, int i, int t, int s, int d)
|
|
: class_limit(c), instance_limit(i), thread_limit(t),
|
|
subclass_limit(s), depth_limit(d), held(t + 1), graph(c * s) {}
|
|
|
|
bool thread_ok(int thread) const {
|
|
return thread >= 1 && thread <= thread_limit;
|
|
}
|
|
|
|
bool subclass_ok(int subclass) const {
|
|
return subclass >= 0 && subclass < subclass_limit;
|
|
}
|
|
|
|
bool has_key(int key) const {
|
|
return classes.find(key) != classes.end();
|
|
}
|
|
|
|
bool has_instance(int instance) const {
|
|
return instances.find(instance) != instances.end();
|
|
}
|
|
|
|
int vertex(int key, int subclass) const {
|
|
return classes.at(key) * subclass_limit + subclass;
|
|
}
|
|
|
|
int instance_vertex(int instance) const {
|
|
const Instance& item = instances.at(instance);
|
|
return vertex(item.key, item.subclass);
|
|
}
|
|
|
|
int free_class_slot() const {
|
|
std::vector<unsigned char> used(class_limit, 0);
|
|
for (const auto& item : classes) {
|
|
used[item.second] = 1;
|
|
}
|
|
for (int slot = 0; slot < class_limit; ++slot) {
|
|
if (!used[slot]) {
|
|
return slot;
|
|
}
|
|
}
|
|
return -1;
|
|
}
|
|
|
|
int count_bound(int key) const {
|
|
int count = 0;
|
|
for (const auto& item : instances) {
|
|
if (item.second.key == key) {
|
|
++count;
|
|
}
|
|
}
|
|
return count;
|
|
}
|
|
|
|
int count_owned(int key) const {
|
|
int count = 0;
|
|
for (const auto& item : instances) {
|
|
if (item.second.key == key && item.second.owner != 0) {
|
|
++count;
|
|
}
|
|
}
|
|
return count;
|
|
}
|
|
|
|
int held_count() const {
|
|
int count = 0;
|
|
for (int thread = 1; thread <= thread_limit; ++thread) {
|
|
count += static_cast<int>(held[thread].size());
|
|
}
|
|
return count;
|
|
}
|
|
|
|
std::vector<Node> nodes() const {
|
|
std::vector<Node> result;
|
|
result.reserve(classes.size() * subclass_limit);
|
|
for (const auto& item : classes) {
|
|
for (int subclass = 0; subclass < subclass_limit; ++subclass) {
|
|
result.emplace_back(item.first, subclass);
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
|
|
std::vector<Edge> edges() const {
|
|
std::vector<Edge> result;
|
|
const auto live = nodes();
|
|
for (const auto& from : live) {
|
|
int source = vertex(from.first, from.second);
|
|
for (const auto& to : live) {
|
|
int target = vertex(to.first, to.second);
|
|
if (graph.direct(source, target)) {
|
|
result.push_back({from.first, from.second, to.first, to.second});
|
|
}
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
|
|
Result counters() const {
|
|
Result result{OK};
|
|
result.push_back(static_cast<long long>(classes.size()));
|
|
result.push_back(static_cast<long long>(instances.size()));
|
|
result.push_back(held_count());
|
|
result.push_back(static_cast<long long>(edges().size()));
|
|
result.push_back(history.acquired);
|
|
result.push_back(history.released);
|
|
result.push_back(history.aborted);
|
|
result.push_back(history.next_ticket);
|
|
return result;
|
|
}
|
|
|
|
void append_instance(Result& result, int id) const {
|
|
const Instance& item = instances.at(id);
|
|
result.push_back(id);
|
|
result.push_back(item.key);
|
|
result.push_back(item.owner);
|
|
result.push_back(item.subclass);
|
|
result.push_back(item.ticket);
|
|
}
|
|
|
|
void append_held(Result& result, int thread) const {
|
|
result.push_back(static_cast<long long>(held[thread].size()));
|
|
for (int id : held[thread]) {
|
|
const Instance& item = instances.at(id);
|
|
result.push_back(id);
|
|
result.push_back(item.key);
|
|
result.push_back(item.subclass);
|
|
result.push_back(item.ticket);
|
|
}
|
|
}
|
|
|
|
void append_edges(Result& result) const {
|
|
const auto listed = edges();
|
|
result.push_back(static_cast<long long>(listed.size()));
|
|
for (const auto& edge : listed) {
|
|
for (int field : edge) {
|
|
result.push_back(field);
|
|
}
|
|
}
|
|
}
|
|
|
|
Result snapshot() const {
|
|
Result result = counters();
|
|
result.push_back(static_cast<long long>(classes.size()));
|
|
for (const auto& item : classes) {
|
|
result.push_back(item.first);
|
|
}
|
|
result.push_back(static_cast<long long>(instances.size()));
|
|
for (const auto& item : instances) {
|
|
append_instance(result, item.first);
|
|
}
|
|
result.push_back(thread_limit);
|
|
for (int thread = 1; thread <= thread_limit; ++thread) {
|
|
result.push_back(thread);
|
|
append_held(result, thread);
|
|
}
|
|
append_edges(result);
|
|
return result;
|
|
}
|
|
|
|
Status register_key(int key) {
|
|
if (!id_ok(key)) {
|
|
return RANGE;
|
|
}
|
|
if (has_key(key)) {
|
|
return EXISTS;
|
|
}
|
|
int slot = free_class_slot();
|
|
if (slot < 0) {
|
|
return FULL;
|
|
}
|
|
classes.emplace(key, slot);
|
|
return OK;
|
|
}
|
|
|
|
Status unregister_key(int key) {
|
|
if (!id_ok(key)) {
|
|
return RANGE;
|
|
}
|
|
auto found = classes.find(key);
|
|
if (found == classes.end()) {
|
|
return MISSING;
|
|
}
|
|
if (count_bound(key) != 0) {
|
|
return BUSY;
|
|
}
|
|
for (int subclass = 0; subclass < subclass_limit; ++subclass) {
|
|
graph.retire(vertex(key, subclass));
|
|
}
|
|
classes.erase(found);
|
|
return OK;
|
|
}
|
|
|
|
Status create_instance(int id, int key) {
|
|
if (!id_ok(id)) {
|
|
return RANGE;
|
|
}
|
|
if (!id_ok(key)) {
|
|
return RANGE;
|
|
}
|
|
if (has_instance(id)) {
|
|
return EXISTS;
|
|
}
|
|
if (!has_key(key)) {
|
|
return MISSING;
|
|
}
|
|
if (static_cast<int>(instances.size()) == instance_limit) {
|
|
return FULL;
|
|
}
|
|
Instance fresh;
|
|
fresh.key = key;
|
|
instances.emplace(id, fresh);
|
|
return OK;
|
|
}
|
|
|
|
Status destroy_instance(int id) {
|
|
if (!id_ok(id)) {
|
|
return RANGE;
|
|
}
|
|
auto found = instances.find(id);
|
|
if (found == instances.end()) {
|
|
return MISSING;
|
|
}
|
|
if (found->second.owner != 0) {
|
|
return BUSY;
|
|
}
|
|
instances.erase(found);
|
|
return OK;
|
|
}
|
|
|
|
Status reclassify(int id, int key) {
|
|
if (!id_ok(id)) {
|
|
return RANGE;
|
|
}
|
|
if (!id_ok(key)) {
|
|
return RANGE;
|
|
}
|
|
auto found = instances.find(id);
|
|
if (found == instances.end()) {
|
|
return MISSING;
|
|
}
|
|
if (!has_key(key)) {
|
|
return MISSING;
|
|
}
|
|
if (found->second.owner != 0) {
|
|
return BUSY;
|
|
}
|
|
found->second.key = key;
|
|
return OK;
|
|
}
|
|
|
|
Status acquire(int thread, int id, int subclass) {
|
|
if (!thread_ok(thread)) {
|
|
return RANGE;
|
|
}
|
|
if (!id_ok(id)) {
|
|
return RANGE;
|
|
}
|
|
if (!subclass_ok(subclass)) {
|
|
return RANGE;
|
|
}
|
|
auto found = instances.find(id);
|
|
if (found == instances.end()) {
|
|
return MISSING;
|
|
}
|
|
if (found->second.owner != 0) {
|
|
return BUSY;
|
|
}
|
|
if (static_cast<int>(held[thread].size()) == depth_limit) {
|
|
return FULL;
|
|
}
|
|
int target = vertex(found->second.key, subclass);
|
|
for (int previous : held[thread]) {
|
|
int source = instance_vertex(previous);
|
|
if (graph.reaches(target, source)) {
|
|
return CYCLE;
|
|
}
|
|
}
|
|
for (int previous : held[thread]) {
|
|
graph.insert(instance_vertex(previous), target);
|
|
}
|
|
found->second.owner = thread;
|
|
found->second.subclass = subclass;
|
|
found->second.ticket = history.next_ticket;
|
|
held[thread].push_back(id);
|
|
++history.next_ticket;
|
|
++history.acquired;
|
|
return OK;
|
|
}
|
|
|
|
Status release(int thread, int id) {
|
|
if (!thread_ok(thread)) {
|
|
return RANGE;
|
|
}
|
|
if (!id_ok(id)) {
|
|
return RANGE;
|
|
}
|
|
auto found = instances.find(id);
|
|
if (found == instances.end()) {
|
|
return MISSING;
|
|
}
|
|
if (found->second.owner != thread) {
|
|
return OWNER;
|
|
}
|
|
auto& stack = held[thread];
|
|
auto position = std::find(stack.begin(), stack.end(), id);
|
|
stack.erase(position);
|
|
found->second.owner = 0;
|
|
found->second.subclass = -1;
|
|
found->second.ticket = 0;
|
|
++history.released;
|
|
return OK;
|
|
}
|
|
|
|
Result abort_thread(int thread) {
|
|
if (!thread_ok(thread)) {
|
|
return {RANGE};
|
|
}
|
|
long long count = static_cast<long long>(held[thread].size());
|
|
while (!held[thread].empty()) {
|
|
int id = held[thread].back();
|
|
release(thread, id);
|
|
}
|
|
++history.aborted;
|
|
return {OK, count};
|
|
}
|
|
|
|
Status erase_history(int key) {
|
|
if (key < 0 || key > 1000000) {
|
|
return RANGE;
|
|
}
|
|
if (key != 0 && !has_key(key)) {
|
|
return MISSING;
|
|
}
|
|
if (held_count() != 0) {
|
|
return BUSY;
|
|
}
|
|
if (key == 0) {
|
|
graph.clear();
|
|
} else {
|
|
for (int subclass = 0; subclass < subclass_limit; ++subclass) {
|
|
graph.retire(vertex(key, subclass));
|
|
}
|
|
}
|
|
return OK;
|
|
}
|
|
|
|
Status validate_path(const std::vector<int>& args) const {
|
|
if (!id_ok(args[0])) {
|
|
return RANGE;
|
|
}
|
|
if (!subclass_ok(args[1])) {
|
|
return RANGE;
|
|
}
|
|
if (!id_ok(args[2])) {
|
|
return RANGE;
|
|
}
|
|
if (!subclass_ok(args[3])) {
|
|
return RANGE;
|
|
}
|
|
if (!has_key(args[0])) {
|
|
return MISSING;
|
|
}
|
|
if (!has_key(args[2])) {
|
|
return MISSING;
|
|
}
|
|
return OK;
|
|
}
|
|
|
|
Result reachable(const std::vector<int>& args) const {
|
|
Status status = validate_path(args);
|
|
if (status != OK) {
|
|
return {status};
|
|
}
|
|
int from = vertex(args[0], args[1]);
|
|
int to = vertex(args[2], args[3]);
|
|
return {OK, graph.reaches(from, to) ? 1 : 0};
|
|
}
|
|
|
|
Result witness(const std::vector<int>& args) const {
|
|
Status status = validate_path(args);
|
|
if (status != OK) {
|
|
return {status};
|
|
}
|
|
auto live = nodes();
|
|
Node source{args[0], args[1]};
|
|
Node target{args[2], args[3]};
|
|
int source_index = static_cast<int>(std::find(live.begin(), live.end(), source) - live.begin());
|
|
int target_index = static_cast<int>(std::find(live.begin(), live.end(), target) - live.begin());
|
|
std::vector<int> parent(live.size(), -1);
|
|
std::queue<int> pending;
|
|
parent[source_index] = source_index;
|
|
pending.push(source_index);
|
|
while (!pending.empty() && parent[target_index] == -1) {
|
|
int current = pending.front();
|
|
pending.pop();
|
|
int from = vertex(live[current].first, live[current].second);
|
|
for (std::size_t next = 0; next < live.size(); ++next) {
|
|
int to = vertex(live[next].first, live[next].second);
|
|
if (parent[next] == -1 && graph.direct(from, to)) {
|
|
parent[next] = current;
|
|
pending.push(static_cast<int>(next));
|
|
}
|
|
}
|
|
}
|
|
if (parent[target_index] == -1) {
|
|
return {OK, 0};
|
|
}
|
|
std::vector<Node> path;
|
|
int current = target_index;
|
|
while (current != source_index) {
|
|
path.push_back(live[current]);
|
|
current = parent[current];
|
|
}
|
|
path.push_back(source);
|
|
std::reverse(path.begin(), path.end());
|
|
Result result{OK, static_cast<long long>(path.size())};
|
|
for (const auto& node : path) {
|
|
result.push_back(node.first);
|
|
result.push_back(node.second);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
Result acquire_batch(const std::vector<int>& args) {
|
|
int thread = args[0];
|
|
if (!thread_ok(thread)) {
|
|
return {RANGE, 0};
|
|
}
|
|
Audit saved = *this;
|
|
int count = static_cast<int>((args.size() - 1) / 2);
|
|
for (int index = 0; index < count; ++index) {
|
|
int id = args[1 + 2 * index];
|
|
int subclass = args[2 + 2 * index];
|
|
Status status = acquire(thread, id, subclass);
|
|
if (status != OK) {
|
|
*this = std::move(saved);
|
|
return {status, index};
|
|
}
|
|
}
|
|
return {OK, count};
|
|
}
|
|
|
|
Result release_batch(const std::vector<int>& args) {
|
|
int thread = args[0];
|
|
if (!thread_ok(thread)) {
|
|
return {RANGE, 0};
|
|
}
|
|
Audit saved = *this;
|
|
int count = static_cast<int>(args.size() - 1);
|
|
for (int index = 0; index < count; ++index) {
|
|
Status status = release(thread, args[index + 1]);
|
|
if (status != OK) {
|
|
*this = std::move(saved);
|
|
return {status, index};
|
|
}
|
|
}
|
|
return {OK, count};
|
|
}
|
|
|
|
Result key_info(int key) const {
|
|
if (!id_ok(key)) {
|
|
return {RANGE};
|
|
}
|
|
if (!has_key(key)) {
|
|
return {MISSING};
|
|
}
|
|
int incoming = 0;
|
|
int outgoing = 0;
|
|
for (const auto& edge : edges()) {
|
|
if (edge[0] == key) {
|
|
++outgoing;
|
|
}
|
|
if (edge[2] == key) {
|
|
++incoming;
|
|
}
|
|
}
|
|
return {OK, key, count_bound(key), count_owned(key), incoming, outgoing};
|
|
}
|
|
|
|
Result instance_info(int id) const {
|
|
if (!id_ok(id)) {
|
|
return {RANGE};
|
|
}
|
|
if (!has_instance(id)) {
|
|
return {MISSING};
|
|
}
|
|
Result result{OK};
|
|
append_instance(result, id);
|
|
return result;
|
|
}
|
|
|
|
Result thread_info(int thread) const {
|
|
if (!thread_ok(thread)) {
|
|
return {RANGE};
|
|
}
|
|
Result result{OK};
|
|
append_held(result, thread);
|
|
return result;
|
|
}
|
|
|
|
Result edge_info() const {
|
|
Result result{OK};
|
|
append_edges(result);
|
|
return result;
|
|
}
|
|
|
|
Result topological() const {
|
|
const auto live = nodes();
|
|
std::vector<int> incoming(live.size(), 0);
|
|
std::vector<std::vector<int>> outgoing(live.size());
|
|
for (std::size_t source = 0; source < live.size(); ++source) {
|
|
int from = vertex(live[source].first, live[source].second);
|
|
for (std::size_t target = 0; target < live.size(); ++target) {
|
|
int to = vertex(live[target].first, live[target].second);
|
|
if (graph.direct(from, to)) {
|
|
outgoing[source].push_back(static_cast<int>(target));
|
|
++incoming[target];
|
|
}
|
|
}
|
|
}
|
|
std::set<int> ready;
|
|
for (std::size_t node = 0; node < live.size(); ++node) {
|
|
if (incoming[node] == 0) {
|
|
ready.insert(static_cast<int>(node));
|
|
}
|
|
}
|
|
std::vector<int> ordered;
|
|
while (!ready.empty()) {
|
|
int current = *ready.begin();
|
|
ready.erase(ready.begin());
|
|
ordered.push_back(current);
|
|
for (int next : outgoing[current]) {
|
|
--incoming[next];
|
|
if (incoming[next] == 0) {
|
|
ready.insert(next);
|
|
}
|
|
}
|
|
}
|
|
if (ordered.size() != live.size()) {
|
|
return {CYCLE};
|
|
}
|
|
Result result{OK, static_cast<long long>(ordered.size())};
|
|
for (int index : ordered) {
|
|
result.push_back(live[index].first);
|
|
result.push_back(live[index].second);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
bool shape_ok(int opcode, std::size_t size) const {
|
|
switch (opcode) {
|
|
case 1:
|
|
case 2:
|
|
case 4:
|
|
case 8:
|
|
case 9:
|
|
case 14:
|
|
case 15:
|
|
case 16:
|
|
return size == 1;
|
|
case 3:
|
|
case 5:
|
|
case 7:
|
|
return size == 2;
|
|
case 6:
|
|
return size == 3;
|
|
case 10:
|
|
case 19:
|
|
return size == 4;
|
|
case 11:
|
|
case 17:
|
|
case 18:
|
|
case 20:
|
|
return size == 0;
|
|
case 12:
|
|
return size >= 3 && size <= 33 && size % 2 == 1;
|
|
case 13:
|
|
return size >= 2 && size <= 17;
|
|
default:
|
|
return false;
|
|
}
|
|
}
|
|
|
|
Result apply(int opcode, const std::vector<int>& args) {
|
|
if (!shape_ok(opcode, args.size())) {
|
|
return {INVALID};
|
|
}
|
|
switch (opcode) {
|
|
case 1:
|
|
return {register_key(args[0])};
|
|
case 2:
|
|
return {unregister_key(args[0])};
|
|
case 3:
|
|
return {create_instance(args[0], args[1])};
|
|
case 4:
|
|
return {destroy_instance(args[0])};
|
|
case 5:
|
|
return {reclassify(args[0], args[1])};
|
|
case 6:
|
|
return {acquire(args[0], args[1], args[2])};
|
|
case 7:
|
|
return {release(args[0], args[1])};
|
|
case 8:
|
|
return abort_thread(args[0]);
|
|
case 9:
|
|
return {erase_history(args[0])};
|
|
case 10:
|
|
return reachable(args);
|
|
case 11:
|
|
return snapshot();
|
|
case 12:
|
|
return acquire_batch(args);
|
|
case 13:
|
|
return release_batch(args);
|
|
case 14:
|
|
return key_info(args[0]);
|
|
case 15:
|
|
return instance_info(args[0]);
|
|
case 16:
|
|
return thread_info(args[0]);
|
|
case 17:
|
|
return edge_info();
|
|
case 18:
|
|
return counters();
|
|
case 19:
|
|
return witness(args);
|
|
case 20:
|
|
return topological();
|
|
default:
|
|
return {INVALID};
|
|
}
|
|
}
|
|
};
|
|
|
|
Audit *audit_create(int classes, int instances, int threads, int subclasses, int depth) {
|
|
if (classes < 1 || classes > 16) {
|
|
return nullptr;
|
|
}
|
|
if (instances < 1 || instances > 32) {
|
|
return nullptr;
|
|
}
|
|
if (threads < 1 || threads > 8) {
|
|
return nullptr;
|
|
}
|
|
if (subclasses < 1 || subclasses > 8) {
|
|
return nullptr;
|
|
}
|
|
if (depth < 1 || depth > 16) {
|
|
return nullptr;
|
|
}
|
|
return new Audit(classes, instances, threads, subclasses, depth);
|
|
}
|
|
|
|
void audit_destroy(Audit *audit) {
|
|
delete audit;
|
|
}
|
|
|
|
std::vector<long long> audit_apply(Audit *audit, int opcode, const std::vector<int>& args) {
|
|
if (audit == nullptr) {
|
|
return {INVALID};
|
|
}
|
|
return audit->apply(opcode, args);
|
|
}
|