java-topology/defects/php/unit/PhpNamedArgTest.java

package unit;

import java.util.HashMap;
import java.util.Map;

/**
 * CWE-407 unit test: php-0001 + php-0002
 *
 * Models PHP's zend_get_arg_num() / zend_get_arg_offset_by_name():
 * resolving named argument → positional index.
 *
 * DEFECT (zend_compile.c:3757, zend_execute.c:5479):
 *   For each of N named args, scan M function params linearly.
 *   Total: O(N × M).  Upstream code has explicit "TODO: Use a hash table?"
 *
 * FIX: build a HashMap<name, index> once per function signature; each lookup is O(1).
 *   Total: O(M + N).
 *
 * Asserts: slowOps > fastOps * 10 at N=M=50 (actual ratio ≈ 50×).
 */
public class PhpNamedArgTest {

    /**
     * Simulate resolving N named arguments against M function parameters
     * using linear scan (defective path).
     *
     * @param M  number of function parameters
     * @param N  number of named arguments being passed (same set as params)
     * @return   total string-comparison operations performed
     */
    static long slow(int M, int N) {
        // Build param list (function signature)
        String[] params = new String[M];
        for (int i = 0; i < M; i++) {
            params[i] = "param" + i;
        }

        // Resolve N named args in reverse order (worst case for linear scan)
        long ops = 0;
        for (int j = N - 1; j >= 0; j--) {
            String argName = "param" + j;
            // Linear scan — mirrors zend_get_arg_num loop
            for (int i = 0; i < M; i++) {
                ops++;
                if (params[i].equals(argName)) {
                    break;
                }
            }
        }
        return ops;
    }

    /**
     * Simulate the patched path: build HashMap once, then O(1) lookup per arg.
     *
     * @param M  number of function parameters
     * @param N  number of named arguments being passed
     * @return   total operations (M to build + N to lookup)
     */
    static long fast(int M, int N) {
        // Build param list
        String[] params = new String[M];
        for (int i = 0; i < M; i++) {
            params[i] = "param" + i;
        }

        // Build HashMap once — O(M)
        Map<String, Integer> nameMap = new HashMap<>(M * 2);
        long ops = 0;
        for (int i = 0; i < M; i++) {
            nameMap.put(params[i], i + 1);
            ops++;
        }

        // Resolve N named args — O(N) hash lookups
        for (int j = N - 1; j >= 0; j--) {
            String argName = "param" + j;
            ops++; // one hash probe
            nameMap.get(argName); // never null in this test
        }
        return ops;
    }

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

        // Test 1: M=N=10 — slow must be >2× more expensive
        // (worst-case sOps = 1+2+...+10 = 55; fOps = 10+10 = 20; ratio ≈ 2.8×)
        {
            total++;
            long sOps = slow(10, 10);
            long fOps = fast(10, 10);
            boolean ok = sOps > fOps * 2L;
            System.out.printf("Test 1 [M=N=10 slow=%d fast=%d ratio=%.1fx]: %s%n",
                    sOps, fOps, (double) sOps / fOps, ok ? "PASS" : "FAIL");
            if (ok) passed++;
        }

        // Test 2: M=N=50 — slow must be >10× more expensive
        {
            total++;
            long sOps = slow(50, 50);
            long fOps = fast(50, 50);
            // Expected: sOps ≈ 50*25=1250 (avg half-scan); fOps = 50+50=100
            boolean ok = sOps > fOps * 10L;
            System.out.printf("Test 2 [M=N=50 slow=%d fast=%d ratio=%.1fx]: %s%n",
                    sOps, fOps, (double) sOps / fOps, ok ? "PASS" : "FAIL");
            if (ok) passed++;
        }

        // Test 3: M=N=100 — slow must be >25× more expensive
        {
            total++;
            long sOps = slow(100, 100);
            long fOps = fast(100, 100);
            // Expected: sOps ≈ 5050 (worst-case reverse); fOps = 200
            boolean ok = sOps > fOps * 25L;
            System.out.printf("Test 3 [M=N=100 slow=%d fast=%d ratio=%.1fx]: %s%n",
                    sOps, fOps, (double) sOps / fOps, ok ? "PASS" : "FAIL");
            if (ok) passed++;
        }

        // Test 4: correctness — both return same position for each arg name
        {
            total++;
            int M = 30;
            // Defective path: resolve each param name to position
            String[] params = new String[M];
            for (int i = 0; i < M; i++) params[i] = "param" + i;

            Map<String, Integer> fastMap = new HashMap<>();
            for (int i = 0; i < M; i++) fastMap.put(params[i], i + 1);

            boolean ok = true;
            for (int j = 0; j < M; j++) {
                // slow: linear scan result
                int slowPos = -1;
                for (int i = 0; i < M; i++) {
                    if (params[i].equals("param" + j)) { slowPos = i + 1; break; }
                }
                int fastPos = fastMap.getOrDefault("param" + j, -1);
                if (slowPos != fastPos) { ok = false; break; }
            }
            System.out.printf("Test 4 [correctness M=%d match=%b]: %s%n",
                    M, ok, ok ? "PASS" : "FAIL");
            if (ok) passed++;
        }

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