package unit;

import java.util.*;

/**
 * GoEthereumTest — CWE-407 benchmark for go-ethereum-0001
 *
 * go-ethereum-0001: txpool/legacypool lookup.addAuthorities() — auths slice O(N²)
 *   Real code (core/txpool/legacypool/legacypool.go):
 *     auths map[common.Address][]common.Hash  // slice per authority
 *
 *     func (t *lookup) addAuthorities(tx *types.Transaction) {
 *         for _, addr := range tx.SetCodeAuthorities() {
 *             list, ok := t.auths[addr]
 *             if !ok { list = []common.Hash{} }
 *             if slices.Contains(list, tx.Hash()) {  // O(N) scan
 *                 continue
 *             }
 *             list = append(list, tx.Hash())
 *             t.auths[addr] = list
 *         }
 *     }
 *
 *   When many txs share the same authority address, the slice for that address
 *   grows to length N and each Contains() call scans the whole list: O(N) per
 *   insertion, O(N²) total.
 *
 * Fix: change auths to map[common.Address]map[common.Hash]struct{} — O(1) lookup.
 *
 *   func (t *lookup) addAuthorities(tx *types.Transaction) {
 *       for _, addr := range tx.SetCodeAuthorities() {
 *           set, ok := t.auths[addr]
 *           if !ok {
 *               set = make(map[common.Hash]struct{})
 *               t.auths[addr] = set
 *           }
 *           if _, dup := set[tx.Hash()]; dup { continue }
 *           set[tx.Hash()] = struct{}{}
 *       }
 *   }
 */
public class GoEthereumTest {

    // --- Defective implementation: auths as map[addr][]hash (slice) ---

    /**
     * Simulates lookup.addAuthorities() with a slice per authority address.
     *
     * @param N   number of distinct tx hashes to add under one authority
     * @return    total comparison operations performed (slices.Contains scans)
     */
    static long slowAddAuthorities(int N) {
        // auths: map[address][]hash — one entry, one authority address
        Map<String, List<String>> auths = new HashMap<>();
        long ops = 0;
        for (int i = 0; i < N; i++) {
            String addr = "authority_0";
            String hash = "tx_hash_" + i;
            List<String> list = auths.computeIfAbsent(addr, k -> new ArrayList<>());
            // slices.Contains — O(current list length)
            boolean dup = false;
            for (int j = 0; j < list.size(); j++) {
                ops++;
                if (list.get(j).equals(hash)) { dup = true; break; }
            }
            if (!dup) list.add(hash);
        }
        return ops;
    }

    /**
     * Simulates lookup.addAuthorities() with a set per authority address (the fix).
     *
     * @param N   number of distinct tx hashes to add under one authority
     * @return    total comparison operations performed (map probes, each O(1))
     */
    static long fastAddAuthorities(int N) {
        // auths: map[address]map[hash]struct{} — O(1) lookup
        Map<String, Set<String>> auths = new HashMap<>();
        long ops = 0;
        for (int i = 0; i < N; i++) {
            String addr = "authority_0";
            String hash = "tx_hash_" + i;
            Set<String> set = auths.computeIfAbsent(addr, k -> new HashSet<>());
            ops++;  // one O(1) probe (contains + add combined)
            set.add(hash);
        }
        return ops;
    }

    // --- Benchmark harness ---

    static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
        // warm up
        slow.run(); fast.run();
        long t0 = System.nanoTime(); slow.run(); long sMs = (System.nanoTime() - t0) / 1_000_000;
        long t1 = System.nanoTime(); fast.run(); long fMs = (System.nanoTime() - t1) / 1_000_000;
        double ratio = (double) sOps / Math.max(fOps, 1);
        System.out.printf("  %-55s  slow: %5dms (%,d ops)  fast: %5dms (%,d ops)  op-ratio: %.0fx%n",
                label, sMs, sOps, fMs, fOps, ratio);
    }

    public static void main(String[] args) {
        System.out.println("GoEthereumTest — go-ethereum-0001: txpool lookup.addAuthorities() slice O(N²) vs map O(N)");
        System.out.println();

        System.out.println("  [go-ethereum-0001: addAuthorities() dedup check]");
        int[] cases = {100, 500, 1000};
        for (int N : cases) {
            long sOps = slowAddAuthorities(N);
            long fOps = fastAddAuthorities(N);
            bench(
                String.format("N=%d txs, 1 authority address", N),
                () -> slowAddAuthorities(N),
                () -> fastAddAuthorities(N),
                sOps, fOps
            );
        }

        System.out.println();

        // --- Assertions ---
        int pass = 0;

        // 1. Slice approach is O(N²): total ops for N unique hashes = 0+1+2+…+(N-1) = N*(N-1)/2
        //    For N=1000 that's 499,500 ops. Map is N=1000 ops. Ratio ~500x.
        {
            int N = 1000;
            long sOps = slowAddAuthorities(N);
            long fOps = fastAddAuthorities(N);
            long expected_slow = (long) N * (N - 1) / 2;  // 499500
            assert sOps == expected_slow
                : "go-ethereum-0001 slow op count mismatch: got=" + sOps + " expected=" + expected_slow;
            assert fOps == N
                : "go-ethereum-0001 fast op count mismatch: got=" + fOps + " expected=" + N;
            double ratio = (double) sOps / fOps;
            assert ratio > 200
                : "go-ethereum-0001 expected >200x op-ratio; got " + ratio;
            System.out.printf("  PASS go-ethereum-0001: N=%d, slow=%,d ops, fast=%,d ops, ratio=%.0fx%n",
                    N, sOps, fOps, ratio);
            pass++;
        }

        // 2. Duplicate insertion: slice and map both reject duplicates, same count
        {
            // Add same hash twice — only one should be retained
            Map<String, List<String>> sliceMap = new HashMap<>();
            List<String> list = sliceMap.computeIfAbsent("addr", k -> new ArrayList<>());
            String hash = "tx_0";
            if (!list.contains(hash)) list.add(hash);
            if (!list.contains(hash)) list.add(hash);
            assert list.size() == 1 : "slice dedup failed: size=" + list.size();

            Map<String, Set<String>> setMap = new HashMap<>();
            Set<String> set = setMap.computeIfAbsent("addr", k -> new HashSet<>());
            set.add(hash);
            set.add(hash);
            assert set.size() == 1 : "map dedup failed: size=" + set.size();

            System.out.printf("  PASS duplicate-rejection: slice.size=%d, set.size=%d%n",
                    list.size(), set.size());
            pass++;
        }

        // 3. Remove: map supports O(1) delete vs slice's O(N) index scan
        //    Verify correctness of remove-by-key semantics
        {
            Map<String, Set<String>> setMap = new HashMap<>();
            Set<String> set = setMap.computeIfAbsent("addr", k -> new HashSet<>());
            for (int i = 0; i < 5; i++) set.add("tx_" + i);
            set.remove("tx_2");
            assert !set.contains("tx_2") : "map remove failed";
            assert set.size() == 4 : "map remove size wrong: " + set.size();
            if (set.isEmpty()) setMap.remove("addr");
            set.clear();
            setMap.computeIfAbsent("addr", k -> new HashSet<>());
            setMap.get("addr").add("tx_x");
            setMap.get("addr").remove("tx_x");
            if (setMap.get("addr").isEmpty()) setMap.remove("addr");
            assert !setMap.containsKey("addr") : "empty-set cleanup failed";
            System.out.printf("  PASS remove-authority: O(1) delete, empty-cleanup correct%n");
            pass++;
        }

        System.out.println();
        System.out.printf("%d/3 PASS%n", pass);
        System.out.printf("go-ethereum-0001: txpool lookup.addAuthorities() auths []hash → map[hash]struct{} O(N²) → O(N)%n");
        System.out.printf("Hotpath: every EIP-7702 set-code tx added to pool; worst case O(T×I) per authority%n");
        if (pass < 3) {
            System.out.println("FAIL");
            System.exit(1);
        }
        System.out.println("ALL PASS");
    }
}