import java.util.*;

/**
 * CWE-407 simulation tests for Neovim defects.
 *
 * neovim-0001: ins_compl_add() O(N^2) duplicate completion check
 *   (inherited from Vim — same defect pattern as vim-0001)
 */
public class NeovimTest {

    // ========================================================================
    // neovim-0001: ins_compl_add duplicate check — linked-list scan vs hash set
    // ========================================================================

    /**
     * DEFECTIVE: O(N^2) — each insertion scans the full list for duplicates.
     * Mirrors Neovim's do { strncmp } while loop in insexpand.c line 943-958.
     */
    static int complAddDefective(String[] candidates) {
        List<String> matches = new ArrayList<>();
        int ops = 0;
        for (String candidate : candidates) {
            // Linear scan for duplicate
            boolean found = false;
            for (String existing : matches) {
                ops++;
                if (existing.equals(candidate)) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                matches.add(candidate);
            }
        }
        return ops;
    }

    /**
     * PATCHED: O(N) — hash set for O(1) amortised duplicate detection.
     * Uses Neovim's map infrastructure (map_defs.h) for O(1) lookup.
     */
    static int complAddPatched(String[] candidates) {
        Set<String> seen = new HashSet<>();
        List<String> matches = new ArrayList<>();
        int ops = 0;
        for (String candidate : candidates) {
            ops++;  // hash lookup
            if (seen.add(candidate)) {
                matches.add(candidate);
            }
        }
        return ops;
    }

    static void testNeovim0001() {
        System.out.println("=== neovim-0001: ins_compl_add duplicate check ===");
        int N = 1000;
        // All unique candidates — worst case for duplicate scan
        String[] candidates = new String[N];
        for (int i = 0; i < N; i++) {
            candidates[i] = "nvim_completion_" + i;
        }

        int opsDefective = complAddDefective(candidates);
        int opsPatched = complAddPatched(candidates);
        double ratio = (double) opsDefective / opsPatched;

        System.out.printf("  N=%d candidates (all unique)%n", N);
        System.out.printf("  Defective ops: %,d%n", opsDefective);
        System.out.printf("  Patched ops:   %,d%n", opsPatched);
        System.out.printf("  Ratio:         %.1fx%n", ratio);

        // Defective: sum(0..N-1) = N*(N-1)/2 = 499,500
        // Patched: N = 1,000
        assert opsDefective >= N * (N - 1) / 2 : "Defective should be O(N^2)";
        assert opsPatched == N : "Patched should be O(N)";
        assert ratio > 100 : "Ratio should exceed 100x, got " + ratio;

        System.out.println("  PASS");
    }

    // ========================================================================
    // Main
    // ========================================================================

    public static void main(String[] args) {
        testNeovim0001();
        System.out.println("\nAll Neovim tests PASSED.");
    }
}