java-topology/defects/bzflag-0001/test/test_event_handler_hasEvent.cpp

// Unit test for bzflag-0001: bz_EventHandler::HasEvent() O(N) vector scan
// replaced with O(1) bitset lookup.
//
// Defect: bz_EventHandler::HasEvent() used std::find on a std::vector<bz_eEventType>
// to check if a handler handles a given event type. This is called inside
// WorldEventManager::callEvents() for every handler on every event fire,
// making it O(E * H) where E = handlers, H = events per handler.
//
// Fix: Replace std::vector<bz_eEventType> HandledEvents with
// std::bitset<bz_eLastEvent> handledEventBits. HasEvent/AddEvent/RemoveEvent
// become O(1) bitset operations.

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

// Minimal reproduction of BZFlag event types
enum bz_eEventType {
    bz_eNullEvent = 0,
    bz_eCaptureEvent,
    bz_ePlayerDieEvent,
    bz_ePlayerSpawnEvent,
    bz_eZoneEntryEvent,
    bz_eZoneExitEvent,
    bz_ePlayerJoinEvent,
    bz_ePlayerPartEvent,
    bz_eRawChatMessageEvent,
    bz_eFilteredChatMessageEvent,
    bz_eUnknownSlashCommand,
    bz_eGetPlayerSpawnPosEvent,
    bz_eGetAutoTeamEvent,
    bz_eAllowPlayer,
    bz_eTickEvent,
    bz_eGetWorldEvent,
    bz_eGetPlayerInfoEvent,
    bz_eAllowSpawn,
    bz_eListServerUpdateEvent,
    bz_eBanEvent,
    bz_eHostBanModifyEvent,
    bz_eKickEvent,
    bz_eKillEvent,
    bz_ePlayerPausedEvent,
    bz_eMessageFilteredEvent,
    bz_eGamePauseEvent,
    bz_eGameResumeEvent,
    bz_eGameStartEvent,
    bz_eGameEndEvent,
    bz_eSlashCommandEvent,
    bz_ePlayerAuthEvent,
    bz_eServerMsgEvent,
    bz_eShotFiredEvent,
    bz_ePlayerUpdateEvent,
    bz_eNetDataSendEvent,
    bz_eNetDataReceiveEvent,
    bz_eLoggingEvent,
    bz_eShotEndedEvent,
    bz_eFlagTransferredEvent,
    bz_eFlagGrabbedEvent,
    bz_eFlagDroppedEvent,
    bz_eAllowCTFCaptureEvent,
    bz_eMsgDebugEvent,
    bz_eNewNonPlayerConnection,
    bz_ePluginLoaded,
    bz_ePluginUnloaded,
    bz_ePlayerScoreChanged,
    bz_eTeamScoreChanged,
    bz_eWorldFinalized,
    bz_eReportFiledEvent,
    bz_eBZDBChange,
    bz_eGetPlayerMotto,
    bz_eAllowConnection,
    bz_eAllowFlagGrab,
    bz_eAuthenticatonComplete,
    bz_eServerAddPlayer,
    bz_eAllowPollEvent,
    bz_ePollStartEvent,
    bz_ePollVoteEvent,
    bz_ePollVetoEvent,
    bz_ePollEndEvent,
    bz_eComputeHandicapEvent,
    bz_eBeginHandicapRefreshEvent,
    bz_eEndHandicapRefreshEvent,
    bz_eAutoPilotEvent,
    bz_eMuteEvent,
    bz_eUnmuteEvent,
    bz_eServerShotFiredEvent,
    bz_ePermissionModificationEvent,
    bz_eAllowServerShotFiredEvent,
    bz_ePlayerDeathFinalizedEvent,
    bz_eLastEvent
};

// BEFORE: vector-based HasEvent (original defective code)
struct EventHandlerBefore {
    std::vector<bz_eEventType> HandledEvents;

    bool HasEvent(bz_eEventType evt) {
        return std::find(HandledEvents.begin(), HandledEvents.end(), evt) != HandledEvents.end();
    }

    void AddEvent(bz_eEventType evt) {
        if (std::find(HandledEvents.begin(), HandledEvents.end(), evt) == HandledEvents.end())
            HandledEvents.push_back(evt);
    }

    void RemoveEvent(bz_eEventType evt) {
        auto itr = std::find(HandledEvents.begin(), HandledEvents.end(), evt);
        if (itr != HandledEvents.end())
            HandledEvents.erase(itr);
    }

    bool IsEmpty() const { return HandledEvents.empty(); }
};

// AFTER: bitset-based HasEvent (patched code)
struct EventHandlerAfter {
    std::bitset<bz_eLastEvent> handledEventBits;

    bool HasEvent(bz_eEventType evt) {
        return (evt >= 0 && evt < bz_eLastEvent) && handledEventBits.test(evt);
    }

    void AddEvent(bz_eEventType evt) {
        if (evt >= 0 && evt < bz_eLastEvent)
            handledEventBits.set(evt);
    }

    void RemoveEvent(bz_eEventType evt) {
        if (evt >= 0 && evt < bz_eLastEvent)
            handledEventBits.reset(evt);
    }

    bool HasNoEvents() const { return handledEventBits.none(); }
};

// Test correctness
void test_correctness() {
    EventHandlerAfter h;

    // Initially no events
    assert(!h.HasEvent(bz_eTickEvent));
    assert(!h.HasEvent(bz_eShotFiredEvent));
    assert(h.HasNoEvents());

    // Add events
    h.AddEvent(bz_eTickEvent);
    h.AddEvent(bz_eShotFiredEvent);
    h.AddEvent(bz_ePlayerUpdateEvent);
    assert(h.HasEvent(bz_eTickEvent));
    assert(h.HasEvent(bz_eShotFiredEvent));
    assert(h.HasEvent(bz_ePlayerUpdateEvent));
    assert(!h.HasEvent(bz_eCaptureEvent));
    assert(!h.HasNoEvents());

    // Idempotent add
    h.AddEvent(bz_eTickEvent);
    assert(h.HasEvent(bz_eTickEvent));

    // Remove
    h.RemoveEvent(bz_eTickEvent);
    assert(!h.HasEvent(bz_eTickEvent));
    assert(h.HasEvent(bz_eShotFiredEvent));

    // Remove all
    h.RemoveEvent(bz_eShotFiredEvent);
    h.RemoveEvent(bz_ePlayerUpdateEvent);
    assert(h.HasNoEvents());

    // Boundary: first and last valid events
    h.AddEvent(bz_eNullEvent);
    assert(h.HasEvent(bz_eNullEvent));
    h.AddEvent((bz_eEventType)(bz_eLastEvent - 1));
    assert(h.HasEvent((bz_eEventType)(bz_eLastEvent - 1)));

    printf("PASS: correctness\n");
}

// Benchmark: simulate callEvents hot path
void test_performance() {
    const int NUM_HANDLERS = 20;   // typical plugin count
    const int EVENTS_PER_HANDLER = 15; // events each handler registers for
    const int ITERATIONS = 1000000;  // event fires to simulate

    // Prepare event types each handler cares about
    std::vector<bz_eEventType> eventTypes;
    for (int i = 0; i < EVENTS_PER_HANDLER && i < bz_eLastEvent; i++)
        eventTypes.push_back((bz_eEventType)(i * 3 % bz_eLastEvent));

    // Setup BEFORE handlers
    std::vector<EventHandlerBefore> beforeHandlers(NUM_HANDLERS);
    for (auto &h : beforeHandlers)
        for (auto evt : eventTypes)
            h.AddEvent(evt);

    // Setup AFTER handlers
    std::vector<EventHandlerAfter> afterHandlers(NUM_HANDLERS);
    for (auto &h : afterHandlers)
        for (auto evt : eventTypes)
            h.AddEvent(evt);

    // Benchmark BEFORE: simulate callEvents checking HasEvent for each handler
    volatile int sink = 0;
    auto t0 = std::chrono::high_resolution_clock::now();
    for (int iter = 0; iter < ITERATIONS; iter++) {
        bz_eEventType queryEvt = (bz_eEventType)(iter % bz_eLastEvent);
        for (int h = 0; h < NUM_HANDLERS; h++) {
            if (beforeHandlers[h].HasEvent(queryEvt))
                sink++;
        }
    }
    auto t1 = std::chrono::high_resolution_clock::now();
    double before_ms = std::chrono::duration<double, std::milli>(t1 - t0).count();

    // Benchmark AFTER: same with bitset
    volatile int sink2 = 0;
    auto t2 = std::chrono::high_resolution_clock::now();
    for (int iter = 0; iter < ITERATIONS; iter++) {
        bz_eEventType queryEvt = (bz_eEventType)(iter % bz_eLastEvent);
        for (int h = 0; h < NUM_HANDLERS; h++) {
            if (afterHandlers[h].HasEvent(queryEvt))
                sink2++;
        }
    }
    auto t3 = std::chrono::high_resolution_clock::now();
    double after_ms = std::chrono::duration<double, std::milli>(t3 - t2).count();

    double ratio = before_ms / after_ms;
    printf("BEFORE: %.1f ms\n", before_ms);
    printf("AFTER:  %.1f ms\n", after_ms);
    printf("Ratio:  %.1fx speedup\n", ratio);

    // Patched version must be faster
    assert(ratio > 2.0 && "Expected at least 2x speedup from bitset vs vector find");
    printf("PASS: performance (%.1fx)\n", ratio);
}

int main() {
    test_correctness();
    test_performance();
    printf("ALL TESTS PASSED\n");
    return 0;
}