java-topology/defects/thunderbird-0001/test/ThunderbirdAccountManagerTest.java

import java.util.*;

/**
 * Unit test for thunderbird-0001: nsMsgAccountManager::LoadAccounts() O(N^2)
 *
 * Simulates the duplicate account detection pattern where IndexOf() is called
 * inside a loop to find the first occurrence of each element.
 *
 * Defective: O(N^2) - IndexOf per element
 * Fixed: O(N) - HashSet for seen tracking
 */
public class ThunderbirdAccountManagerTest {

    // --- Defective: O(N^2) duplicate detection via indexOf ---
    static List<String> loadAccountsDefective(String[] accountKeys) {
        List<String> accounts = new ArrayList<>(Arrays.asList(accountKeys));
        List<String> loaded = new ArrayList<>();
        for (int i = 0; i < accounts.size(); i++) {
            // indexOf scans from 0 => O(N) per call
            if (accounts.indexOf(accounts.get(i)) != i) continue; // skip duplicate
            loaded.add(accounts.get(i));
        }
        return loaded;
    }

    // --- Fixed: O(N) duplicate detection via HashSet ---
    static List<String> loadAccountsFixed(String[] accountKeys) {
        List<String> accounts = new ArrayList<>(Arrays.asList(accountKeys));
        List<String> loaded = new ArrayList<>();
        Set<String> seen = new HashSet<>();
        for (int i = 0; i < accounts.size(); i++) {
            if (!seen.add(accounts.get(i))) continue; // O(1) per call
            loaded.add(accounts.get(i));
        }
        return loaded;
    }

    // --- Defective: O(A*I^2) identity reuse scanning ---
    static boolean identityStillUsedDefective(String targetIdentity,
            List<List<String>> accountIdentities) {
        for (List<String> identities : accountIdentities) {
            // indexOf is O(I) per account
            if (identities.indexOf(targetIdentity) >= 0) {
                return true;
            }
        }
        return false;
    }

    // --- Fixed: O(A) with pre-built identity set ---
    static boolean identityStillUsedFixed(String targetIdentity,
            Set<String> allIdentityKeys) {
        return allIdentityKeys.contains(targetIdentity); // O(1)
    }

    public static void main(String[] args) {
        System.out.println("=== thunderbird-0001: nsMsgAccountManager LoadAccounts O(N^2) ===\n");

        // Test correctness
        String[] sample = {"acct1", "acct2", "acct1", "acct3", "acct2", "acct4"};
        List<String> defResult = loadAccountsDefective(sample);
        List<String> fixResult = loadAccountsFixed(sample);
        assert defResult.equals(fixResult) : "Results must match";
        assert defResult.equals(Arrays.asList("acct1", "acct2", "acct3", "acct4"));
        System.out.println("PASS correctness: both produce " + defResult);

        // Benchmark LoadAccounts dedup
        int[] sizes = {100, 500, 1000, 5000};
        for (int N : sizes) {
            // Create account list with ~20% duplicates
            String[] keys = new String[N];
            Random rng = new Random(42);
            for (int i = 0; i < N; i++) {
                keys[i] = "account" + rng.nextInt((int)(N * 0.8));
            }

            // Warmup
            for (int w = 0; w < 3; w++) {
                loadAccountsDefective(keys);
                loadAccountsFixed(keys);
            }

            // Measure defective
            int iters = Math.max(1, 50000 / N);
            long t0 = System.nanoTime();
            for (int r = 0; r < iters; r++) loadAccountsDefective(keys);
            long defTime = System.nanoTime() - t0;

            // Measure fixed
            t0 = System.nanoTime();
            for (int r = 0; r < iters; r++) loadAccountsFixed(keys);
            long fixTime = System.nanoTime() - t0;

            double ratio = (double) defTime / Math.max(1, fixTime);
            String status = ratio >= 2.0 ? "PASS" : "FAIL";
            System.out.printf("%s N=%5d  defective=%8dns  fixed=%8dns  ratio=%.1fx%n",
                    status, N, defTime / iters, fixTime / iters, ratio);
        }

        // Test identity reuse scanning correctness
        List<List<String>> acctIds = Arrays.asList(
            Arrays.asList("id1", "id2", "id3"),
            Arrays.asList("id4", "id5"),
            Arrays.asList("id6", "id7", "id8", "id9")
        );
        Set<String> allIds = new HashSet<>();
        for (List<String> ids : acctIds) allIds.addAll(ids);

        assert identityStillUsedDefective("id5", acctIds) == true;
        assert identityStillUsedFixed("id5", allIds) == true;
        assert identityStillUsedDefective("id99", acctIds) == false;
        assert identityStillUsedFixed("id99", allIds) == false;
        System.out.println("\nPASS identity reuse: both methods agree");

        System.out.println("\nAll tests passed.");
    }
}