java-topology/defects/wesnoth-0001/test/wesnoth-0001-test.cpp

// wesnoth-0001-test.cpp
// Unit test: A* pathfinding std::find on priority queue vector (CWE-407)
//
// DEFECT: In astarsearch.cpp, the A* inner loop calls
//   std::push_heap(pq.begin(), std::find(pq.begin(), pq.end(), index), ...)
// to perform decrease-key on a node already in the open set.
// std::find scans the entire pq vector, making the per-relaxation cost O(Q)
// where Q is the priority queue size. On hex maps with varied terrain costs,
// the same hex gets relaxed multiple times, triggering the linear scan.
//
// FIX: Use lazy deletion. Always push a new entry on relaxation. When
// popping, skip nodes that have already been finalized (in == search_counter).
// This eliminates the std::find entirely.
//
// BUILD: g++ -std=c++17 -O2 -o wesnoth-0001-test wesnoth-0001-test.cpp && ./wesnoth-0001-test

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <random>

static const unsigned SEARCH_COUNTER_BASE = 100;

struct Node {
    double g;
    double t;
    int prev;
    unsigned in;
    Node() : g(1e25), t(1e25), prev(-1), in(0) {}
};

struct Comp {
    const std::vector<Node>& nodes;
    Comp(const std::vector<Node>& n) : nodes(n) {}
    bool operator()(int a, int b) const {
        return nodes[b].t < nodes[a].t;
    }
};

// Dense random graph to force many decrease-key operations
struct DenseGraph {
    int n; // number of nodes
    // adjacency: for each node, a list of (neighbor, cost) pairs
    std::vector<std::vector<std::pair<int,double>>> adj;

    void init(int nodes, int avg_edges_per_node, unsigned seed) {
        n = nodes;
        adj.resize(n);
        std::mt19937 rng(seed);
        std::uniform_int_distribution<int> node_dist(0, n-1);
        std::uniform_real_distribution<double> cost_dist(1.0, 10.0);

        // Create a connected graph with many edges to force decrease-keys
        // First create a chain
        for (int i = 0; i < n - 1; i++) {
            double c = cost_dist(rng);
            adj[i].push_back({i+1, c});
            adj[i+1].push_back({i, c});
        }
        // Then add random edges
        for (int i = 0; i < n * avg_edges_per_node; i++) {
            int u = node_dist(rng);
            int v = node_dist(rng);
            if (u != v) {
                double c = cost_dist(rng);
                adj[u].push_back({v, c});
            }
        }
    }
};

// DEFECTIVE: uses std::find for decrease-key
long long run_defective(const DenseGraph& g, int src, int dst, double* out_cost) {
    unsigned search_counter = SEARCH_COUNTER_BASE;
    std::vector<Node> nodes(g.n);
    Comp comp(nodes);

    nodes[src].g = 0;
    nodes[src].t = 0;
    nodes[src].in = search_counter + 1;

    std::vector<int> pq;
    pq.push_back(src);

    long long ops = 0;
    long long decrease_keys = 0;

    while (!pq.empty()) {
        int front_idx = pq.front();
        nodes[front_idx].in = search_counter;
        std::pop_heap(pq.begin(), pq.end(), comp);
        pq.pop_back();

        Node& n = nodes[front_idx];
        if (n.g > 1e24) break;

        for (auto& [nb, edge_cost] : g.adj[front_idx]) {
            double cost = n.g + edge_cost;
            if (nodes[nb].in == search_counter) continue;
            if (cost >= nodes[nb].g) continue;

            bool in_list = nodes[nb].in == search_counter + 1;

            nodes[nb].g = cost;
            nodes[nb].t = cost;
            nodes[nb].prev = front_idx;
            nodes[nb].in = search_counter + 1;

            if (in_list) {
                decrease_keys++;
                // DEFECT: linear scan to find position in pq
                auto it = std::find(pq.begin(), pq.end(), nb);
                ops += (long long)(it - pq.begin()) + 1;
                if (it != pq.end()) {
                    std::push_heap(pq.begin(), it + 1, comp);
                }
            } else {
                pq.push_back(nb);
                std::push_heap(pq.begin(), pq.end(), comp);
                ops++;
            }
        }
    }

    *out_cost = nodes[dst].g;
    return ops;
}

// FIXED: lazy deletion, no std::find
long long run_fixed(const DenseGraph& g, int src, int dst, double* out_cost) {
    unsigned search_counter = SEARCH_COUNTER_BASE;
    std::vector<Node> nodes(g.n);
    Comp comp(nodes);

    nodes[src].g = 0;
    nodes[src].t = 0;
    nodes[src].in = search_counter + 1;

    std::vector<int> pq;
    pq.push_back(src);

    long long ops = 0;

    while (!pq.empty()) {
        std::pop_heap(pq.begin(), pq.end(), comp);
        int front_idx = pq.back();
        pq.pop_back();

        Node& n = nodes[front_idx];

        if (n.in == search_counter) continue;
        n.in = search_counter;

        if (n.g > 1e24) break;

        for (auto& [nb, edge_cost] : g.adj[front_idx]) {
            double cost = n.g + edge_cost;
            if (nodes[nb].in == search_counter) continue;
            if (cost >= nodes[nb].g) continue;

            nodes[nb].g = cost;
            nodes[nb].t = cost;
            nodes[nb].prev = front_idx;
            nodes[nb].in = search_counter + 1;

            pq.push_back(nb);
            std::push_heap(pq.begin(), pq.end(), comp);
            ops++;
        }
    }

    *out_cost = nodes[dst].g;
    return ops;
}

int main() {
    printf("wesnoth-0001-test: A* pathfinding std::find on pq (CWE-407)\n\n");

    // Test 1: Correctness
    {
        printf("Test 1: correctness on small dense graph\n");
        DenseGraph g;
        g.init(100, 10, 42);

        double cost_d, cost_f;
        run_defective(g, 0, 99, &cost_d);
        run_fixed(g, 0, 99, &cost_f);

        assert(std::abs(cost_d - cost_f) < 1e-9);
        printf("  PASS (both find cost %.2f)\n", cost_d);
    }

    // Test 2: Performance on medium graph
    {
        printf("\nTest 2: performance on dense graph (N=2000, E~20/node)\n");
        DenseGraph g;
        g.init(2000, 20, 123);

        double cost_d, cost_f;
        long long ops_defect = run_defective(g, 0, 1999, &cost_d);
        long long ops_fixed = run_fixed(g, 0, 1999, &cost_f);

        assert(std::abs(cost_d - cost_f) < 1e-9);

        double ratio = (double)ops_defect / (double)ops_fixed;

        printf("  defective ops: %lld\n", ops_defect);
        printf("  fixed ops:     %lld\n", ops_fixed);
        printf("  ratio:         %.1fx\n", ratio);
        printf("  cost:          %.2f (both agree)\n", cost_d);
        assert(ratio > 5.0);
        printf("  PASS (ratio > 5x)\n");
    }

    // Test 3: Performance on larger graph
    {
        printf("\nTest 3: performance on dense graph (N=5000, E~20/node)\n");
        DenseGraph g;
        g.init(5000, 20, 456);

        double cost_d, cost_f;
        long long ops_defect = run_defective(g, 0, 4999, &cost_d);
        long long ops_fixed = run_fixed(g, 0, 4999, &cost_f);

        assert(std::abs(cost_d - cost_f) < 1e-9);

        double ratio = (double)ops_defect / (double)ops_fixed;

        printf("  defective ops: %lld\n", ops_defect);
        printf("  fixed ops:     %lld\n", ops_fixed);
        printf("  ratio:         %.1fx\n", ratio);
        printf("  cost:          %.2f (both agree)\n", cost_d);
        assert(ratio > 10.0);
        printf("  PASS (ratio > 10x)\n");
    }

    printf("\nAll tests PASSED.\n");
    return 0;
}