package unit;

import java.util.HashSet;
import java.util.Set;

/**
 * CWE-407 unit test: php-0003 + php-0004
 *
 * Models PHP's interface dedup during class linking:
 *   php-0003: zend_do_implement_interfaces (zend_inheritance.c:2259-2290)
 *   php-0004: zend_do_inherit_interfaces   (zend_inheritance.c:1606-1616)
 *
 * DEFECT (php-0003): When linking a class with I new interfaces, for each
 *   new interface, a linear scan of all accumulated interfaces checks for
 *   duplicates. Total: O(P*I + I^2) where P = parent interface count.
 *
 * DEFECT (php-0004): When inheriting IF interfaces from a parent/iface,
 *   for each of IF entries, a linear scan of CE existing class interfaces
 *   checks for duplicates. Total: O(IF * CE).
 *
 * FIX: use a HashSet of interface pointers (simulated here as integer IDs)
 *   for O(1) membership test. Total: O(I) or O(IF + CE).
 *
 * Asserts: slowOps > fastOps * 5 at I=500+ (actual ratio ~250x at I=500).
 */
public class PhpInterfaceDedupAlgorithm {

    // --- php-0003: zend_do_implement_interfaces ---

    /**
     * Simulate zend_do_implement_interfaces defective path.
     * For each of numNew new interfaces, scan accumulated array for duplicates.
     *
     * @param numParent  number of interfaces already inherited from parent
     * @param numNew     number of new interfaces the class declares
     * @return           total pointer-comparison operations
     */
    static long slow0003(int numParent, int numNew) {
        // interfaces[] array: first numParent are pre-populated from parent
        int[] interfaces = new int[numParent + numNew];
        for (int k = 0; k < numParent; k++) {
            interfaces[k] = k; // simulated interface pointers as IDs
        }
        int numInterfaces = numParent;
        long ops = 0;

        for (int i = 0; i < numNew; i++) {
            int iface = numParent + i; // new interface ID
            boolean duplicate = false;

            // Inner loop: O(numInterfaces) linear scan
            for (int j = 0; j < numInterfaces; j++) {
                ops++;
                if (interfaces[j] == iface) {
                    duplicate = true;
                    break;
                }
            }

            if (!duplicate) {
                interfaces[numInterfaces] = iface;
                numInterfaces++;
            }
        }
        return ops;
    }

    /**
     * Simulate zend_do_implement_interfaces patched path.
     * Use HashSet for O(1) membership test.
     *
     * @param numParent  number of parent interfaces
     * @param numNew     number of new interfaces
     * @return           total operations
     */
    static long fast0003(int numParent, int numNew) {
        Set<Integer> ifaceSet = new HashSet<>(numParent + numNew);
        long ops = 0;

        // Pre-populate from parent — O(numParent)
        for (int k = 0; k < numParent; k++) {
            ifaceSet.add(k);
            ops++;
        }

        for (int i = 0; i < numNew; i++) {
            int iface = numParent + i;
            ops++; // O(1) hash probe
            if (!ifaceSet.contains(iface)) {
                ifaceSet.add(iface);
            }
        }
        return ops;
    }

    // --- php-0004: zend_do_inherit_interfaces ---

    /**
     * Simulate zend_do_inherit_interfaces defective path.
     * For each of ifNum parent interface entries, scan ceNum class interfaces.
     *
     * @param ifNum  number of entries in the implemented interface's interface list
     * @param ceNum  number of interfaces already on the class
     * @return       total pointer-comparison operations
     */
    static long slow0004(int ifNum, int ceNum) {
        // Class already has ceNum interfaces: IDs 0..ceNum-1
        int[] ceInterfaces = new int[ceNum + ifNum];
        for (int i = 0; i < ceNum; i++) {
            ceInterfaces[i] = i;
        }
        int ceTotal = ceNum;
        long ops = 0;

        // iface->interfaces: IDs ceNum..ceNum+ifNum-1 (all new, no overlap)
        // Worst case: none are duplicates, so every scan goes to the end
        for (int k = ifNum - 1; k >= 0; k--) {
            int entry = ceNum + k;
            boolean found = false;

            // Inner loop: O(ceNum) scan — mirrors:
            //   for (i = 0; i < ce_num; i++) { if (ce->interfaces[i] == entry) break; }
            for (int i = 0; i < ceNum; i++) {
                ops++;
                if (ceInterfaces[i] == entry) {
                    found = true;
                    break;
                }
            }

            if (!found) {
                ceInterfaces[ceTotal++] = entry;
            }
        }
        return ops;
    }

    /**
     * Simulate zend_do_inherit_interfaces patched path.
     * Pre-build HashSet of class interfaces for O(1) lookup.
     *
     * @param ifNum  number of parent interface entries
     * @param ceNum  number of existing class interfaces
     * @return       total operations
     */
    static long fast0004(int ifNum, int ceNum) {
        Set<Integer> ceSet = new HashSet<>(ceNum + ifNum);
        long ops = 0;

        // Populate set from existing class interfaces — O(ceNum)
        for (int i = 0; i < ceNum; i++) {
            ceSet.add(i);
            ops++;
        }

        for (int k = ifNum - 1; k >= 0; k--) {
            int entry = ceNum + k;
            ops++; // O(1) hash probe
            if (!ceSet.contains(entry)) {
                ceSet.add(entry);
            }
        }
        return ops;
    }

    public static void main(String[] args) {
        int passed = 0;
        int total = 0;

        // --- php-0003 tests ---

        // Test 1: php-0003 N=50, ratio >= 5x
        {
            total++;
            long sOps = slow0003(0, 50);
            long fOps = fast0003(0, 50);
            double ratio = (double) sOps / fOps;
            boolean ok = ratio >= 5.0;
            System.out.printf("Test 1 [php-0003 I=50   slow=%d fast=%d ratio=%.1fx]: %s%n",
                    sOps, fOps, ratio, ok ? "PASS" : "FAIL");
            if (ok) passed++;
        }

        // Test 2: php-0003 N=200, ratio >= 30x
        {
            total++;
            long sOps = slow0003(0, 200);
            long fOps = fast0003(0, 200);
            double ratio = (double) sOps / fOps;
            boolean ok = ratio >= 30.0;
            System.out.printf("Test 2 [php-0003 I=200  slow=%d fast=%d ratio=%.1fx]: %s%n",
                    sOps, fOps, ratio, ok ? "PASS" : "FAIL");
            if (ok) passed++;
        }

        // Test 3: php-0003 N=500, ratio >= 100x
        {
            total++;
            long sOps = slow0003(0, 500);
            long fOps = fast0003(0, 500);
            double ratio = (double) sOps / fOps;
            boolean ok = ratio >= 100.0;
            System.out.printf("Test 3 [php-0003 I=500  slow=%d fast=%d ratio=%.1fx]: %s%n",
                    sOps, fOps, ratio, ok ? "PASS" : "FAIL");
            if (ok) passed++;
        }

        // Test 4: php-0003 with 20 parent + 200 new interfaces, ratio >= 10x
        {
            total++;
            long sOps = slow0003(20, 200);
            long fOps = fast0003(20, 200);
            double ratio = (double) sOps / fOps;
            boolean ok = ratio >= 10.0;
            System.out.printf("Test 4 [php-0003 P=20+I=200 slow=%d fast=%d ratio=%.1fx]: %s%n",
                    sOps, fOps, ratio, ok ? "PASS" : "FAIL");
            if (ok) passed++;
        }

        // --- php-0004 tests ---

        // Test 5: php-0004 IF=50,CE=50, ratio >= 5x
        {
            total++;
            long sOps = slow0004(50, 50);
            long fOps = fast0004(50, 50);
            double ratio = (double) sOps / fOps;
            boolean ok = ratio >= 5.0;
            System.out.printf("Test 5 [php-0004 IF=50,CE=50   slow=%d fast=%d ratio=%.1fx]: %s%n",
                    sOps, fOps, ratio, ok ? "PASS" : "FAIL");
            if (ok) passed++;
        }

        // Test 6: php-0004 IF=200,CE=200, ratio >= 30x
        {
            total++;
            long sOps = slow0004(200, 200);
            long fOps = fast0004(200, 200);
            double ratio = (double) sOps / fOps;
            boolean ok = ratio >= 30.0;
            System.out.printf("Test 6 [php-0004 IF=200,CE=200 slow=%d fast=%d ratio=%.1fx]: %s%n",
                    sOps, fOps, ratio, ok ? "PASS" : "FAIL");
            if (ok) passed++;
        }

        // Test 7: php-0004 IF=500,CE=500, ratio >= 100x
        {
            total++;
            long sOps = slow0004(500, 500);
            long fOps = fast0004(500, 500);
            double ratio = (double) sOps / fOps;
            boolean ok = ratio >= 100.0;
            System.out.printf("Test 7 [php-0004 IF=500,CE=500 slow=%d fast=%d ratio=%.1fx]: %s%n",
                    sOps, fOps, ratio, ok ? "PASS" : "FAIL");
            if (ok) passed++;
        }

        // Test 8: correctness — no spurious dedup for non-overlapping sets
        {
            total++;
            int ifNum = 50, ceNum = 50;
            // Slow: count how many entries were added (should be all ifNum since no overlap)
            int[] ceInterfaces = new int[ceNum + ifNum];
            for (int i = 0; i < ceNum; i++) ceInterfaces[i] = i;
            int ceTotal = ceNum;
            for (int k = ifNum - 1; k >= 0; k--) {
                int entry = ceNum + k;
                boolean found = false;
                for (int i = 0; i < ceNum; i++) {
                    if (ceInterfaces[i] == entry) { found = true; break; }
                }
                if (!found) ceInterfaces[ceTotal++] = entry;
            }
            int slowAdded = ceTotal - ceNum;

            // Fast: same
            Set<Integer> ceSet = new HashSet<>();
            for (int i = 0; i < ceNum; i++) ceSet.add(i);
            int fastAdded = 0;
            for (int k = ifNum - 1; k >= 0; k--) {
                int entry = ceNum + k;
                if (!ceSet.contains(entry)) { ceSet.add(entry); fastAdded++; }
            }

            boolean ok = (slowAdded == ifNum) && (fastAdded == ifNum) && (slowAdded == fastAdded);
            System.out.printf("Test 8 [php-0004 correctness added=%d expected=%d]: %s%n",
                    slowAdded, ifNum, ok ? "PASS" : "FAIL");
            if (ok) passed++;
        }

        System.out.printf("%d/%d PASS%n", passed, total);
        if (passed != total) System.exit(1);
    }
}