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

// wesnoth-0002-test.cpp
// Unit test: Server ip_log_ deque linear scan (CWE-407)
//
// DEFECT: In server.cpp, every player login checks ip_log_ (a deque of up to
// 500 connection_log entries) via std::find for duplicate IP/nick pairs.
// Every player logoff also does std::find to update log_off time.
// Both are O(N) where N is the log size (default max 500).
// Under heavy login/logoff traffic, this becomes O(L * N) where L is the
// number of login events.
//
// FIX: Add an unordered_set<connection_log> alongside the deque for O(1)
// membership lookup. Keep the deque for LRU eviction order.
//
// BUILD: g++ -std=c++17 -O2 -o wesnoth-0002-test wesnoth-0002-test.cpp && ./wesnoth-0002-test

#include <deque>
#include <unordered_set>
#include <string>
#include <algorithm>
#include <chrono>
#include <cstdio>
#include <cassert>

struct connection_log {
    std::string nick, ip;

    bool operator==(const connection_log& c) const {
        return c.nick == nick && c.ip == ip;
    }
};

struct connection_log_hash {
    std::size_t operator()(const connection_log& c) const {
        std::size_t h1 = std::hash<std::string>{}(c.nick);
        std::size_t h2 = std::hash<std::string>{}(c.ip);
        return h1 ^ (h2 << 1);
    }
};

// DEFECTIVE: linear scan on deque
struct DefectiveIpLog {
    std::deque<connection_log> ip_log_;
    std::size_t max_size_;

    DefectiveIpLog(std::size_t max_sz) : max_size_(max_sz) {}

    long long login(const std::string& nick, const std::string& ip) {
        connection_log entry{nick, ip};
        long long ops = 0;

        // Linear scan
        auto it = ip_log_.begin();
        for (; it != ip_log_.end(); ++it) {
            ops++;
            if (*it == entry) break;
        }

        if (it == ip_log_.end()) {
            ip_log_.push_back(entry);
            if (ip_log_.size() > max_size_) {
                ip_log_.pop_front();
            }
        }
        return ops;
    }
};

// FIXED: unordered_set for O(1) lookup
struct FixedIpLog {
    std::deque<connection_log> ip_log_;
    std::unordered_set<connection_log, connection_log_hash> ip_log_set_;
    std::size_t max_size_;

    FixedIpLog(std::size_t max_sz) : max_size_(max_sz) {}

    long long login(const std::string& nick, const std::string& ip) {
        connection_log entry{nick, ip};
        long long ops = 1;  // hash lookup = 1 op

        if (ip_log_set_.find(entry) == ip_log_set_.end()) {
            ip_log_.push_back(entry);
            ip_log_set_.insert(entry);
            if (ip_log_.size() > max_size_) {
                ip_log_set_.erase(ip_log_.front());
                ip_log_.pop_front();
            }
        }
        return ops;
    }
};

int main() {
    printf("wesnoth-0002-test: server ip_log_ deque linear scan (CWE-407)\n\n");

    const int MAX_LOG = 500;
    const int NUM_LOGINS = 2000;

    // Test 1: Correctness
    {
        printf("Test 1: correctness\n");
        DefectiveIpLog defective(MAX_LOG);
        FixedIpLog fixed(MAX_LOG);

        for (int i = 0; i < NUM_LOGINS; i++) {
            std::string nick = "user" + std::to_string(i % 600);
            std::string ip = "10.0." + std::to_string((i / 256) % 256) + "." + std::to_string(i % 256);
            defective.login(nick, ip);
            fixed.login(nick, ip);
        }

        // Both should have same entries
        assert(defective.ip_log_.size() == fixed.ip_log_.size());
        for (size_t i = 0; i < defective.ip_log_.size(); i++) {
            assert(defective.ip_log_[i] == fixed.ip_log_[i]);
        }
        printf("  PASS\n");
    }

    // Test 2: Performance
    {
        printf("\nTest 2: performance with %d logins, max_log=%d\n", NUM_LOGINS, MAX_LOG);

        DefectiveIpLog defective(MAX_LOG);
        FixedIpLog fixed(MAX_LOG);

        long long defect_ops = 0;
        long long fixed_ops = 0;

        for (int i = 0; i < NUM_LOGINS; i++) {
            // Mix of new and repeat logins
            std::string nick = "player" + std::to_string(i % 700);
            std::string ip = "192.168." + std::to_string((i / 256) % 256) + "." + std::to_string(i % 256);
            defect_ops += defective.login(nick, ip);
            fixed_ops += fixed.login(nick, ip);
        }

        double ratio = (double)defect_ops / (double)fixed_ops;

        printf("  defective ops: %lld\n", defect_ops);
        printf("  fixed ops:     %lld\n", fixed_ops);
        printf("  ratio:         %.1fx\n", ratio);
        assert(ratio > 50.0);
        printf("  PASS (ratio > 50x)\n");
    }

    // Test 3: Worst case (all unique logins filling the log)
    {
        printf("\nTest 3: worst case, all unique logins\n");

        DefectiveIpLog defective(MAX_LOG);
        FixedIpLog fixed(MAX_LOG);

        long long defect_ops = 0;
        long long fixed_ops = 0;

        for (int i = 0; i < NUM_LOGINS; i++) {
            std::string nick = "unique_user_" + std::to_string(i);
            std::string ip = "10." + std::to_string((i / 65536) % 256) + "." + std::to_string((i / 256) % 256) + "." + std::to_string(i % 256);
            defect_ops += defective.login(nick, ip);
            fixed_ops += fixed.login(nick, ip);
        }

        double ratio = (double)defect_ops / (double)fixed_ops;

        printf("  defective ops: %lld\n", defect_ops);
        printf("  fixed ops:     %lld\n", fixed_ops);
        printf("  ratio:         %.1fx\n", ratio);
        assert(ratio > 100.0);
        printf("  PASS (ratio > 100x)\n");
    }

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