java-topology/defects/scummvm-0002/test/scummvm-0002-test.cpp

// scummvm-0002-test.cpp
// Unit test: TsAGE WalkRegions _disabledRegions O(D) linear scan in recursive pathfinding (CWE-407)
//
// DEFECT: In engines/tsage/core.cpp, calculateRestOfRoute() is a recursive
// function that finds optimal walk paths across scene regions. In the inner
// while loop it calls:
//   contains(_disabledRegions, (int)currDest)
// where contains() performs a linear O(D) scan over a Common::List<int>.
// With D disabled regions, R connected regions per walk region, and recursive
// depth up to the number of regions, the total cost per pathfinding call is
// O(D * R * depth). Also WalkRegions::indexOf() scans O(R*I) where I is
// the size of the ignored-index list passed in.
//
// FIX: Change _disabledRegions from Common::List<int> to
// std::unordered_set<int>. insert(), erase(), and find() all become O(1).
// The save/load serialization is updated to use insert() and range iteration.
//
// BUILD: g++ -std=c++17 -O2 -o scummvm-0002-test scummvm-0002-test.cpp && ./scummvm-0002-test

#include <vector>
#include <list>
#include <unordered_set>
#include <algorithm>
#include <chrono>
#include <cstdio>
#include <cassert>

// Simulated Common::List<int> contains (original defect path)
static bool list_contains(const std::list<int> &l, int v) {
    return std::find(l.begin(), l.end(), v) != l.end();
}

// Route-finding context: simulate calculateRestOfRoute with disabled region check
// Graph: nodes 1..N in a chain, each connected to next 3 nodes
static const int REGION_LIST_SIZE = 40;

struct DefectRouter {
    int N;  // total regions
    std::vector<std::vector<int>> adj;  // adjacency
    std::list<int> disabledRegions;     // O(D) linear scan

    DefectRouter(int n, const std::vector<int> &disabled) : N(n), adj(n + 1) {
        // Build adjacency: each region connects to up to 3 forward neighbors
        for (int i = 1; i <= N; i++) {
            for (int k = 1; k <= 3 && i + k <= N; k++) {
                adj[i].push_back(i + k);
            }
        }
        for (int d : disabled) disabledRegions.push_back(d);
    }

    // Returns path length or 32000 if no route
    int findRoute(int src, int dest, int depth = 0) {
        if (depth > REGION_LIST_SIZE) return 32000;
        if (src == dest) return 0;

        int best = 32000;
        for (int next : adj[src]) {
            // DEFECT: O(D) linear scan on every recursive call
            if (!list_contains(disabledRegions, next)) {
                int d = findRoute(next, dest, depth + 1);
                if (d < best) best = 1 + d;
            }
        }
        return best;
    }
};

struct FixedRouter {
    int N;
    std::vector<std::vector<int>> adj;
    std::unordered_set<int> disabledRegions;  // O(1) lookup

    FixedRouter(int n, const std::vector<int> &disabled) : N(n), adj(n + 1) {
        for (int i = 1; i <= N; i++) {
            for (int k = 1; k <= 3 && i + k <= N; k++) {
                adj[i].push_back(i + k);
            }
        }
        for (int d : disabled) disabledRegions.insert(d);
    }

    int findRoute(int src, int dest, int depth = 0) {
        if (depth > REGION_LIST_SIZE) return 32000;
        if (src == dest) return 0;

        int best = 32000;
        for (int next : adj[src]) {
            // FIX: O(1) hash lookup
            if (disabledRegions.find(next) == disabledRegions.end()) {
                int d = findRoute(next, dest, depth + 1);
                if (d < best) best = 1 + d;
            }
        }
        return best;
    }
};

static void test_correctness() {
    const int N = 20;
    // Disable every 3rd region to simulate partially blocked maps
    std::vector<int> disabled;
    for (int i = 3; i <= N; i += 3) disabled.push_back(i);

    DefectRouter dr(N, disabled);
    FixedRouter  fr(N, disabled);

    for (int src = 1; src <= N; src++) {
        for (int dst = src; dst <= N; dst++) {
            int rd = dr.findRoute(src, dst);
            int rf = fr.findRoute(src, dst);
            assert(rd == rf);
        }
    }
    printf("PASS correctness: defect and fixed agree on all region pairs\n");
}

int main() {
    printf("scummvm-0002: TsAGE _disabledRegions O(D) linear scan in pathfinding (CWE-407)\n\n");

    test_correctness();

    // Benchmark: many disabled regions, find route across map, many calls
    const int N = 30;
    std::vector<int> disabled;
    // Disable every other region -- maximizes disabled list size (D = N/2)
    for (int i = 2; i <= N; i += 2) disabled.push_back(i);

    const int CALLS = 5000;

    printf("\nBenchmark: N=%d regions, D=%zu disabled, %d route-find calls\n",
        N, disabled.size(), CALLS);

    DefectRouter dr(N, disabled);
    FixedRouter  fr(N, disabled);

    auto t0 = std::chrono::high_resolution_clock::now();
    for (int c = 0; c < CALLS; c++) {
        // Route from region 1 to region N -- traverses full map
        (void)dr.findRoute(1, N);
    }
    auto t1 = std::chrono::high_resolution_clock::now();
    long long us_defect = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();

    auto t2 = std::chrono::high_resolution_clock::now();
    for (int c = 0; c < CALLS; c++) {
        (void)fr.findRoute(1, N);
    }
    auto t3 = std::chrono::high_resolution_clock::now();
    long long us_fixed = std::chrono::duration_cast<std::chrono::microseconds>(t3 - t2).count();

    printf("  Defect (O(D*R^depth) per call): %lld us\n", us_defect);
    printf("  Fixed  (O(R^depth)   per call): %lld us\n", us_fixed);

    if (us_fixed > 0 && us_defect > 0) {
        double ratio = (double)us_defect / (double)us_fixed;
        printf("  Speedup ratio: %.1fx\n", ratio);
    }

    printf("\nPASS\n");
    return 0;
}