java-topology/defects/thunderbird-0006/test/ThunderbirdSpamWhitelistTest.java

import java.util.*;

/**
 * Unit test for thunderbird-0006: nsSpamSettings::CheckWhiteList() O(M*E)
 *
 * Simulates the spam whitelist check where for each incoming message,
 * the sender's email is compared against all identity emails via linear scan.
 *
 * Defective: O(M*E) - linear scan through emails per message
 * Fixed: O(M) - HashSet pre-computed from identity emails
 */
public class ThunderbirdSpamWhitelistTest {

    // --- Defective: O(M*E) linear scan per message ---
    static int checkWhiteListDefective(List<String> incomingAuthors,
            List<String> identityEmails) {
        int whitelisted = 0;
        for (String author : incomingAuthors) {
            String authorLower = author.toLowerCase();
            // Check 1: exact email match (O(E) per message)
            boolean found = false;
            for (String email : identityEmails) {
                if (email.equalsIgnoreCase(authorLower)) {
                    found = true;
                    break;
                }
            }
            if (found) { whitelisted++; continue; }

            // Check 2: domain match (O(E) per message, with string ops)
            String authorDomain = authorLower.substring(authorLower.indexOf('@') + 1);
            for (String email : identityEmails) {
                int atPos = email.indexOf('@');
                if (atPos >= 0) {
                    String domain = email.substring(atPos + 1).toLowerCase();
                    if (domain.equals(authorDomain)) {
                        found = true;
                        break;
                    }
                }
            }
            if (found) whitelisted++;
        }
        return whitelisted;
    }

    // --- Fixed: O(M) with pre-computed sets ---
    static int checkWhiteListFixed(List<String> incomingAuthors,
            Set<String> emailSet, Set<String> domainSet) {
        int whitelisted = 0;
        for (String author : incomingAuthors) {
            String authorLower = author.toLowerCase();
            if (emailSet.contains(authorLower)) {
                whitelisted++;
                continue;
            }
            String authorDomain = authorLower.substring(authorLower.indexOf('@') + 1);
            if (domainSet.contains(authorDomain)) {
                whitelisted++;
            }
        }
        return whitelisted;
    }

    public static void main(String[] args) {
        System.out.println("=== thunderbird-0006: nsSpamSettings CheckWhiteList O(M*E) ===\n");

        // Correctness
        List<String> emails = Arrays.asList(
            "user@example.com", "admin@corp.org", "test@foo.bar");
        Set<String> emailSet = new HashSet<>();
        Set<String> domainSet = new HashSet<>();
        for (String e : emails) {
            emailSet.add(e.toLowerCase());
            domainSet.add(e.substring(e.indexOf('@') + 1).toLowerCase());
        }

        List<String> authors = Arrays.asList(
            "User@Example.com",    // exact match (case-insensitive)
            "other@corp.org",      // domain match
            "spam@evil.com",       // no match
            "test@foo.bar"         // exact match
        );

        int defCount = checkWhiteListDefective(authors, emails);
        int fixCount = checkWhiteListFixed(authors, emailSet, domainSet);
        assert defCount == fixCount : "Counts must match: " + defCount + " vs " + fixCount;
        assert defCount == 3 : "3 whitelisted: " + defCount;
        System.out.println("PASS correctness: " + defCount + " whitelisted");

        // Benchmark
        int[] emailCounts = {10, 50, 100, 500};
        int M = 1000; // messages per sync
        for (int E : emailCounts) {
            // Generate identity emails
            List<String> idEmails = new ArrayList<>();
            Set<String> eSet = new HashSet<>();
            Set<String> dSet = new HashSet<>();
            for (int i = 0; i < E; i++) {
                String e = "user" + i + "@domain" + (i % 20) + ".com";
                idEmails.add(e);
                eSet.add(e.toLowerCase());
                dSet.add("domain" + (i % 20) + ".com");
            }

            // Generate incoming messages (~10% match rate)
            Random rng = new Random(42);
            List<String> msgs = new ArrayList<>();
            for (int i = 0; i < M; i++) {
                if (rng.nextInt(10) == 0) {
                    msgs.add("user" + rng.nextInt(E) + "@domain" + rng.nextInt(20) + ".com");
                } else {
                    msgs.add("sender" + i + "@external" + rng.nextInt(100) + ".com");
                }
            }

            // Warmup
            for (int w = 0; w < 3; w++) {
                checkWhiteListDefective(msgs, idEmails);
                checkWhiteListFixed(msgs, eSet, dSet);
            }

            int iters = Math.max(1, 10000 / E);
            long t0 = System.nanoTime();
            for (int r = 0; r < iters; r++) checkWhiteListDefective(msgs, idEmails);
            long defTime = System.nanoTime() - t0;

            t0 = System.nanoTime();
            for (int r = 0; r < iters; r++) checkWhiteListFixed(msgs, eSet, dSet);
            long fixTime = System.nanoTime() - t0;

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

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