/**
 * CWE-407 simulation: Firefox Sanitizer ListSet O(N×E) linear membership.
 *
 * Simulates the ListSet class from dom/security/sanitizer/SanitizerTypes.h
 * which backs the Sanitizer API's element/attribute allow/block lists.
 * The defective version uses ArrayList (linear Contains), the fixed version
 * uses HashSet (O(1) Contains).
 */
import java.util.*;

public class Firefox0001SanitizerListSetTest {

    // --- Defective: ListSet backed by ArrayList (linear scan) ---
    static class ListSetDefective<T> {
        private final List<T> values = new ArrayList<>();

        void insert(T value) {
            if (contains(value)) return;
            values.add(value);
        }

        boolean contains(T value) {
            return values.contains(value);  // O(N) linear scan
        }

        boolean isEmpty() { return values.isEmpty(); }
    }

    // --- Fixed: ListSet backed by HashSet (O(1) lookup) ---
    static class ListSetFixed<T> {
        private final List<T> values = new ArrayList<>();
        private final Set<T> lookup = new HashSet<>();

        void insert(T value) {
            if (lookup.contains(value)) return;
            values.add(value);
            lookup.add(value);
        }

        boolean contains(T value) {
            return lookup.contains(value);  // O(1) amortized
        }

        boolean isEmpty() { return values.isEmpty(); }
    }

    // Simulate sanitization: for each DOM node, check element against
    // removeElements, replaceWithChildrenElements, and elements lists.
    static long sanitizeDefective(int domNodes, int configEntries) {
        ListSetDefective<String> removeElements = new ListSetDefective<>();
        ListSetDefective<String> elements = new ListSetDefective<>();
        for (int i = 0; i < configEntries; i++) {
            removeElements.insert("remove-element-" + i);
            elements.insert("allow-element-" + i);
        }

        long ops = 0;
        for (int n = 0; n < domNodes; n++) {
            String elementName = "dom-element-" + (n % 100);
            // Check removeElements
            removeElements.contains(elementName); ops++;
            // Check elements allowlist
            if (!elements.isEmpty()) {
                elements.contains(elementName); ops++;
            }
        }
        return ops;
    }

    static long sanitizeFixed(int domNodes, int configEntries) {
        ListSetFixed<String> removeElements = new ListSetFixed<>();
        ListSetFixed<String> elements = new ListSetFixed<>();
        for (int i = 0; i < configEntries; i++) {
            removeElements.insert("remove-element-" + i);
            elements.insert("allow-element-" + i);
        }

        long ops = 0;
        for (int n = 0; n < domNodes; n++) {
            String elementName = "dom-element-" + (n % 100);
            removeElements.contains(elementName); ops++;
            if (!elements.isEmpty()) {
                elements.contains(elementName); ops++;
            }
        }
        return ops;
    }

    public static void main(String[] args) {
        System.out.println("=== Firefox-0001: Sanitizer ListSet O(N×E) vs O(N) ===\n");

        int[] domNodeCounts = {100, 500, 1000, 5000};
        int configEntries = 200;  // typical sanitizer config size

        int pass = 0, fail = 0;

        for (int N : domNodeCounts) {
            // Warmup
            sanitizeDefective(N, configEntries);
            sanitizeFixed(N, configEntries);

            long t0 = System.nanoTime();
            for (int r = 0; r < 50; r++) sanitizeDefective(N, configEntries);
            long defectiveNs = System.nanoTime() - t0;

            t0 = System.nanoTime();
            for (int r = 0; r < 50; r++) sanitizeFixed(N, configEntries);
            long fixedNs = System.nanoTime() - t0;

            double ratio = (double) defectiveNs / fixedNs;
            boolean ok = ratio > 1.5;
            System.out.printf("N=%4d, E=%3d | defective=%8.3fms  fixed=%8.3fms  ratio=%.1fx  %s%n",
                    N, configEntries,
                    defectiveNs / 1e6, fixedNs / 1e6, ratio,
                    ok ? "PASS" : "FAIL");
            if (ok) pass++; else fail++;
        }

        System.out.printf("%nResults: %d PASS, %d FAIL%n", pass, fail);
        if (fail > 0) System.exit(1);
    }
}