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

// openmw-0001-test.cpp
// CWE-407: Tarjan SCC std::find(mSCCStack) O(V^2) in pathgrid.cpp
//
// The Tarjan SCC algorithm in PathgridGraph::Builder::recursiveStrongConnect
// uses std::find(mSCCStack.begin(), mSCCStack.end(), w) to check if a vertex
// is on the stack. This is O(S) per edge where S is the stack size, making the
// overall algorithm O(V*E) instead of the correct O(V+E).
//
// Fix: add an unordered_set<size_t> mSCCOnStack for O(1) membership checks.

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

struct Edge {
    size_t index;
};

struct Node {
    int componentId = -1;
    std::vector<Edge> edges;
};

static constexpr size_t NoIndex = static_cast<size_t>(-1);

// ---------- DEFECTIVE (original): std::find on vector ----------
namespace Defective {
    struct Builder {
        std::vector<Node>& mGraph;
        int mSCCId = 0;
        size_t mSCCIndex = 0;
        std::vector<size_t> mSCCStack;
        std::vector<std::pair<size_t, size_t>> mSCCPoint;

        Builder(std::vector<Node>& g) : mGraph(g) {}

        void recursiveStrongConnect(const size_t v) {
            mSCCPoint[v].first = mSCCIndex;
            mSCCPoint[v].second = mSCCIndex;
            mSCCIndex++;
            mSCCStack.push_back(v);
            size_t w;

            for (const auto& edge : mGraph[v].edges) {
                w = edge.index;
                if (mSCCPoint[w].first == NoIndex) {
                    recursiveStrongConnect(w);
                    mSCCPoint[v].second = std::min(mSCCPoint[v].second, mSCCPoint[w].second);
                }
                // DEFECT: O(S) linear scan on the stack vector
                else if (std::find(mSCCStack.begin(), mSCCStack.end(), w) != mSCCStack.end())
                    mSCCPoint[v].second = std::min(mSCCPoint[v].second, mSCCPoint[w].first);
            }

            if (mSCCPoint[v].second == mSCCPoint[v].first) {
                do {
                    w = mSCCStack.back();
                    mSCCStack.pop_back();
                    mGraph[w].componentId = mSCCId;
                } while (w != v);
                mSCCId++;
            }
        }

        void build() {
            size_t n = mGraph.size();
            mSCCPoint.assign(n, {NoIndex, NoIndex});
            for (size_t i = 0; i < n; i++)
                if (mSCCPoint[i].first == NoIndex)
                    recursiveStrongConnect(i);
        }
    };
}

// ---------- PATCHED: unordered_set for O(1) on-stack check ----------
namespace Patched {
    struct Builder {
        std::vector<Node>& mGraph;
        int mSCCId = 0;
        size_t mSCCIndex = 0;
        std::vector<size_t> mSCCStack;
        std::unordered_set<size_t> mSCCOnStack;
        std::vector<std::pair<size_t, size_t>> mSCCPoint;

        Builder(std::vector<Node>& g) : mGraph(g) {}

        void recursiveStrongConnect(const size_t v) {
            mSCCPoint[v].first = mSCCIndex;
            mSCCPoint[v].second = mSCCIndex;
            mSCCIndex++;
            mSCCStack.push_back(v);
            mSCCOnStack.insert(v);
            size_t w;

            for (const auto& edge : mGraph[v].edges) {
                w = edge.index;
                if (mSCCPoint[w].first == NoIndex) {
                    recursiveStrongConnect(w);
                    mSCCPoint[v].second = std::min(mSCCPoint[v].second, mSCCPoint[w].second);
                }
                // PATCHED: O(1) hash set lookup
                else if (mSCCOnStack.count(w))
                    mSCCPoint[v].second = std::min(mSCCPoint[v].second, mSCCPoint[w].first);
            }

            if (mSCCPoint[v].second == mSCCPoint[v].first) {
                do {
                    w = mSCCStack.back();
                    mSCCStack.pop_back();
                    mSCCOnStack.erase(w);
                    mGraph[w].componentId = mSCCId;
                } while (w != v);
                mSCCId++;
            }
        }

        void build() {
            size_t n = mGraph.size();
            mSCCPoint.assign(n, {NoIndex, NoIndex});
            for (size_t i = 0; i < n; i++)
                if (mSCCPoint[i].first == NoIndex)
                    recursiveStrongConnect(i);
        }
    };
}

// Build a chain graph: 0->1->2->...->N-1->0 (one big cycle = one SCC)
std::vector<Node> buildChainGraph(size_t N) {
    std::vector<Node> graph(N);
    for (size_t i = 0; i < N; i++) {
        graph[i].edges.push_back(Edge{(i + 1) % N});
        // Add a back-edge every 10 nodes to increase stack probes
        if (i >= 10)
            graph[i].edges.push_back(Edge{i - 10});
    }
    return graph;
}

int main() {
    const size_t N = 2000;

    // Correctness: both must produce the same component IDs
    {
        auto g1 = buildChainGraph(N);
        auto g2 = buildChainGraph(N);

        Defective::Builder(g1).build();
        Patched::Builder(g2).build();

        for (size_t i = 0; i < N; i++)
            assert(g1[i].componentId == g2[i].componentId);

        printf("PASS correctness: component IDs match for N=%zu\n", N);
    }

    // Performance: measure defective vs patched
    auto benchDefective = [&]() {
        auto g = buildChainGraph(N);
        auto t0 = std::chrono::high_resolution_clock::now();
        Defective::Builder(g).build();
        auto t1 = std::chrono::high_resolution_clock::now();
        return std::chrono::duration<double, std::milli>(t1 - t0).count();
    };

    auto benchPatched = [&]() {
        auto g = buildChainGraph(N);
        auto t0 = std::chrono::high_resolution_clock::now();
        Patched::Builder(g).build();
        auto t1 = std::chrono::high_resolution_clock::now();
        return std::chrono::duration<double, std::milli>(t1 - t0).count();
    };

    // Warmup
    benchDefective();
    benchPatched();

    double defMs = 0, patMs = 0;
    const int runs = 5;
    for (int i = 0; i < runs; i++) {
        defMs += benchDefective();
        patMs += benchPatched();
    }
    defMs /= runs;
    patMs /= runs;

    double ratio = defMs / patMs;
    printf("Defective: %.2f ms  Patched: %.2f ms  Ratio: %.1fx (N=%zu)\n",
           defMs, patMs, ratio, N);
    assert(ratio > 2.0 && "Patched should be at least 2x faster");
    printf("PASS performance: %.1fx speedup\n", ratio);

    return 0;
}