import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

/**
 * Test for drone-0002: MOAD-0005 Thundering Herd in cache/ttl_cache.go TTLCache.Get().
 *
 * Location: cache/ttl_cache.go  TTLCache.Get()
 *
 * Defect pattern (CWE-362 cache stampede):
 *   1. fetch(key) — acquires RLock, returns cache miss
 *   2. getter.Find(ctx, key) — called with NO lock held
 *   3. mx.Lock(); cache[key] = item; mx.Unlock()
 *
 * Under concurrent load: C goroutines all see a cache miss simultaneously for
 * the same key, all call getter.Find() independently, all issue C database
 * round-trips for the same record. A thundering herd of DB queries results.
 *
 * Fix: wrap getter.Find() in a singleflight group keyed by the cache key.
 * Only the first goroutine issues the DB call; all others share its result.
 * Backend calls drop from C to 1 for any C concurrent misses on the same key.
 *
 * Compile and run (no build tool required):
 *   javac defects/drone-0002/test/Drone0002Test.java -d /tmp/drone-0002
 *   java -cp /tmp/drone-0002 Drone0002Test
 */
public class Drone0002Test {

    private static int passed = 0;
    private static int failed = 0;

    // --- Fake backend store with call counter ---

    static class FakeStore {
        final AtomicInteger callCount = new AtomicInteger(0);
        final long latencyMs;

        FakeStore(long latencyMs) { this.latencyMs = latencyMs; }

        String find(String key) throws InterruptedException {
            callCount.incrementAndGet();
            Thread.sleep(latencyMs);
            return "value-for-" + key;
        }
    }

    // --- Defective cache: no singleflight ---

    static class CacheDefective {
        final Map<String, String> cache = new ConcurrentHashMap<>();
        final FakeStore store;

        CacheDefective(FakeStore s) { this.store = s; }

        String get(String key) throws Exception {
            String v = cache.get(key);
            if (v != null) return v;
            // thundering herd: multiple threads all reach here simultaneously
            v = store.find(key);
            cache.put(key, v);
            return v;
        }
    }

    // --- Fixed cache: singleflight coalesces concurrent misses ---

    static class CacheFixed {
        final Map<String, String> cache = new ConcurrentHashMap<>();
        final FakeStore store;
        final ConcurrentHashMap<String, CompletableFuture<String>> inflight = new ConcurrentHashMap<>();

        CacheFixed(FakeStore s) { this.store = s; }

        String get(String key) throws Exception {
            String v = cache.get(key);
            if (v != null) return v;

            CompletableFuture<String> mine = new CompletableFuture<>();
            CompletableFuture<String> existing = inflight.putIfAbsent(key, mine);
            if (existing != null) return existing.get(); // wait for in-flight call

            try {
                v = store.find(key);
                cache.put(key, v);
                mine.complete(v);
                return v;
            } catch (Exception e) {
                mine.completeExceptionally(e);
                throw e;
            } finally {
                inflight.remove(key);
            }
        }
    }

    // --- Helpers ---

    static int countBackendCalls(boolean useFixed, int concurrent, long latencyMs)
            throws Exception {
        FakeStore store = new FakeStore(latencyMs);
        Object cache = useFixed ? new CacheFixed(store) : new CacheDefective(store);

        CountDownLatch ready = new CountDownLatch(concurrent);
        CountDownLatch start = new CountDownLatch(1);
        CountDownLatch done  = new CountDownLatch(concurrent);
        ExecutorService pool = Executors.newFixedThreadPool(concurrent);

        for (int i = 0; i < concurrent; i++) {
            pool.submit(() -> {
                ready.countDown();
                try {
                    start.await();
                    if (useFixed) ((CacheFixed) cache).get("mykey");
                    else          ((CacheDefective) cache).get("mykey");
                } catch (Exception ignored) {
                } finally { done.countDown(); }
            });
        }

        ready.await(5, TimeUnit.SECONDS); // all threads waiting at start gate
        start.countDown();               // release simultaneously
        done.await(10, TimeUnit.SECONDS);
        pool.shutdown();
        return store.callCount.get();
    }

    // --- Tests ---

    static void testDefectiveTriggersManyBackendCalls() throws Exception {
        int concurrent = 20;
        int calls = countBackendCalls(false, concurrent, 30);
        check("defective cache triggers >1 backend calls (thundering herd confirmed)",
            calls > 1);
        System.out.printf("    drone-0002 defective backend calls at C=%d: %d (expect ~%d)%n",
            concurrent, calls, concurrent);
    }

    static void testFixedTriggersExactlyOneBackendCall() throws Exception {
        int concurrent = 20;
        int calls = countBackendCalls(true, concurrent, 30);
        check("fixed cache triggers exactly 1 backend call (singleflight working)",
            calls == 1);
        System.out.printf("    drone-0002 fixed backend calls at C=%d: %d (expect 1)%n",
            concurrent, calls);
    }

    static void testFixedReturnCorrectValue() throws Exception {
        FakeStore store = new FakeStore(5);
        CacheFixed cache = new CacheFixed(store);
        String result = cache.get("mykey");
        check("fixed cache returns correct value", "value-for-mykey".equals(result));
    }

    static void testFixedSecondCallHitsCache() throws Exception {
        FakeStore store = new FakeStore(0);
        CacheFixed cache = new CacheFixed(store);
        cache.get("k1");
        int afterFirst = store.callCount.get();
        cache.get("k1"); // second call — must hit cache
        int afterSecond = store.callCount.get();
        check("second Get on same key hits cache (no backend call)",
            afterFirst == afterSecond);
    }

    static void testSpeedupRatioAtConcurrency20() throws Exception {
        int concurrent = 20;
        int defCalls = countBackendCalls(false, concurrent, 15);
        int fixCalls = countBackendCalls(true,  concurrent, 15);
        double ratio = (double) defCalls / Math.max(1, fixCalls);
        check("fixed version reduces backend calls by at least 10x at C=20",
            ratio >= 10.0);
        System.out.printf("    drone-0002 thundering herd ratio at C=%d: %.1fx fewer backend calls%n",
            concurrent, ratio);
    }

    // --- Harness ---

    static void check(String desc, boolean cond) {
        if (cond) {
            System.out.println("  PASS: " + desc);
            passed++;
        } else {
            System.out.println("  FAIL: " + desc);
            failed++;
        }
    }

    public static void main(String[] args) throws Exception {
        System.out.println("=== Drone0002Test (MOAD-0005 Thundering Herd in TTLCache.Get) ===\n");

        testDefectiveTriggersManyBackendCalls();
        testFixedTriggersExactlyOneBackendCall();
        testFixedReturnCorrectValue();
        testFixedSecondCallHitsCache();
        testSpeedupRatioAtConcurrency20();

        System.out.println("\n--- " + passed + " passed, " + failed + " failed ---");
        if (failed > 0) System.exit(1);
    }
}