package unit;

import java.util.*;

/**
 * Standalone unit test for grafana-0002: CWE-407.
 *
 * grafana-0002: Folder/dashboard permission UID deduplication O(P²)
 *   slow() mirrors the defective pattern: for each of P permission strings,
 *         calls slices.Contains on the growing result slice — O(P) per iteration.
 *         Total cost: O(P²).
 *   fast() uses a HashMap seen-set for O(1) membership; total cost O(P).
 *   Assert: slowOps > fastOps * 5x for P=500 permissions (all distinct UIDs).
 *
 * Models four affected sites in folder.go (lines 253, 451, 544) and
 * dashboard_service.go (line 1534).
 */
public class Grafana0002FolderPermDedupTest {

    static final String SCOPE_PREFIX = "folders:uid:";

    /**
     * Slow path — slices.Contains on growing result slice: O(P²).
     */
    static long slowPermDedup(List<String> permissions) {
        long ops = 0;
        List<String> uids = new ArrayList<>();
        for (String p : permissions) {
            if (p.startsWith(SCOPE_PREFIX)) {
                String uid = p.substring(SCOPE_PREFIX.length());
                // slices.Contains(uids, uid) — O(uids.size()) linear scan
                boolean found = false;
                for (String existing : uids) {
                    ops++;
                    if (existing.equals(uid)) { found = true; break; }
                }
                if (!found) {
                    uids.add(uid);
                }
            }
        }
        return ops;
    }

    /**
     * Fast path — HashMap seen-set: O(P) total.
     */
    static long fastPermDedup(List<String> permissions) {
        long ops = 0;
        Map<String, Boolean> seen = new HashMap<>();
        List<String> uids = new ArrayList<>();
        for (String p : permissions) {
            if (p.startsWith(SCOPE_PREFIX)) {
                String uid = p.substring(SCOPE_PREFIX.length());
                ops++;  // O(1) map lookup
                if (!seen.containsKey(uid)) {
                    seen.put(uid, true);
                    uids.add(uid);
                }
            }
        }
        return ops;
    }

    static void testFolderPermDedup() {
        int P = 500;  // permission entries — all distinct UIDs (worst case, no dupes)

        List<String> perms = new ArrayList<>(P);
        for (int i = 0; i < P; i++) {
            perms.add(SCOPE_PREFIX + "folder-uid-" + i);
        }

        long sOps = slowPermDedup(perms);
        long fOps = fastPermDedup(perms);

        int minRatio = 5;
        boolean pass = sOps > fOps * minRatio;
        System.out.printf("grafana-0002 [P=%d all-distinct]: slow=%d fast=%d ratio=%.1fx — %s%n",
                P, sOps, fOps, (double) sOps / fOps, pass ? "PASS" : "FAIL");
        if (!pass) throw new AssertionError("grafana-0002 FAIL: slow=" + sOps + " fast=" + fOps);
    }

    static void testFolderPermDedupWithDuplicates() {
        int P = 500;  // permission entries — 50 unique UIDs, 10 dupes each
        int UNIQUE = 50;

        List<String> perms = new ArrayList<>(P);
        for (int i = 0; i < P; i++) {
            perms.add(SCOPE_PREFIX + "folder-uid-" + (i % UNIQUE));
        }

        long sOps = slowPermDedup(perms);
        long fOps = fastPermDedup(perms);

        // With duplicates, slow still scans the full seen-slice for each entry
        // After the first UNIQUE entries are collected, each subsequent entry
        // scans all UNIQUE already-collected items before finding the hit.
        int minRatio = 5;
        boolean pass = sOps > fOps * minRatio;
        System.out.printf("grafana-0002 [P=%d 50-unique 10x-dupes]: slow=%d fast=%d ratio=%.1fx — %s%n",
                P, sOps, fOps, (double) sOps / fOps, pass ? "PASS" : "FAIL");
        if (!pass) throw new AssertionError("grafana-0002 dup FAIL: slow=" + sOps + " fast=" + fOps);
    }

    public static void main(String[] args) {
        testFolderPermDedup();
        testFolderPermDedupWithDuplicates();
        System.out.println("2/2 PASS");
    }
}