java-topology/defects/wekan-0003/test/WekanCreatorMemberDedupTest.java

import java.util.*;

/**
 * Unit test for Wekan CWE-407 defect wekan-0003:
 * wekanCreator.js createBoardAndLabels() uses Array.some() inside forEach
 * for board member dedup (O(M^2)), and createCards() uses Array.find()
 * inside nested forEach inside for-of loop for card member dedup (O(C*M^2)).
 *
 * Defect locations:
 *   models/wekanCreator.js createBoardAndLabels() line ~329
 *   models/wekanCreator.js createCards() line ~419, ~438
 *
 * Pattern:
 *   boardToImport.members.forEach(m => {
 *     if (!boardToCreate.members.some(x => x.wekanId === m.wekanId)) push(m);
 *   });
 *
 *   for (card of wekanCards) {
 *     card.members.forEach(srcId => {
 *       if (!wekanMembers.find(wId => wId === wekanId)) push(wekanId);
 *     });
 *   }
 *
 * Fix: use Set for O(1) membership check.
 */
public class WekanCreatorMemberDedupTest {

    // -------------------------------------------------------------------------
    // Defect: board member dedup O(M^2) via Array.some()
    // -------------------------------------------------------------------------
    static long slowBoardMemberDedup(List<String> importMembers) {
        List<String> existing = new ArrayList<>();
        existing.add("admin-user");
        long ops = 0;
        for (String m : importMembers) {
            // .some() scans existing list -- O(E) per member
            boolean found = false;
            for (String e : existing) {  // O(E)
                ops++;
                if (e.equals(m)) { found = true; break; }
            }
            if (!found) existing.add(m);
        }
        return ops;
    }

    static long fastBoardMemberDedup(List<String> importMembers) {
        Set<String> seen = new HashSet<>();
        seen.add("admin-user");
        List<String> result = new ArrayList<>();
        result.add("admin-user");
        long ops = 0;
        for (String m : importMembers) {
            ops++;
            if (!seen.contains(m)) {  // O(1)
                seen.add(m);
                result.add(m);
            }
        }
        return ops;
    }

    // -------------------------------------------------------------------------
    // Defect: card member dedup O(C*M^2) via Array.find() in nested forEach
    // -------------------------------------------------------------------------
    static long slowCardMemberDedup(int numCards, List<String> cardMembers) {
        long ops = 0;
        for (int c = 0; c < numCards; c++) {
            List<String> wekanMembers = new ArrayList<>();
            for (String srcId : cardMembers) {
                // .find() scans wekanMembers -- O(W) per member
                boolean found = false;
                for (String wId : wekanMembers) {  // O(W)
                    ops++;
                    if (wId.equals(srcId)) { found = true; break; }
                }
                if (!found) wekanMembers.add(srcId);
            }
        }
        return ops;
    }

    static long fastCardMemberDedup(int numCards, List<String> cardMembers) {
        long ops = 0;
        for (int c = 0; c < numCards; c++) {
            Set<String> seen = new HashSet<>();
            List<String> wekanMembers = new ArrayList<>();
            for (String srcId : cardMembers) {
                ops++;
                if (!seen.contains(srcId)) {  // O(1)
                    seen.add(srcId);
                    wekanMembers.add(srcId);
                }
            }
        }
        return ops;
    }

    // -------------------------------------------------------------------------
    // Correctness: both strategies produce same deduplicated result
    // -------------------------------------------------------------------------
    static List<String> slowDedup(List<String> input) {
        List<String> result = new ArrayList<>();
        for (String s : input) {
            if (!result.contains(s)) result.add(s);
        }
        return result;
    }

    static List<String> fastDedup(List<String> input) {
        Set<String> seen = new LinkedHashSet<>(input);
        return new ArrayList<>(seen);
    }

    public static void main(String[] args) {
        System.out.println("WekanCreatorMemberDedupTest — CWE-407 wekan-0003");

        final int M  = 200;     // members per board import (realistic board size)
        final int C  = 500;     // cards per board import
        final int CM = 20;      // members per card (assignees map)

        // Board member import list (30% duplicates simulating multi-source merge)
        List<String> boardMembers = new ArrayList<>(M);
        for (int i = 0; i < M; i++) boardMembers.add("user-" + (i % (int)(M * 0.7)));

        // Card member list per card
        List<String> cardMembers = new ArrayList<>(CM);
        for (int i = 0; i < CM; i++) cardMembers.add("user-" + (i % (int)(CM * 0.7)));

        // Board member dedup benchmark
        System.out.println("\n  [wekan-0003a] board member dedup: Array.some O(M^2) vs Set O(M)");
        long slowBoardOps = slowBoardMemberDedup(boardMembers);
        long fastBoardOps = fastBoardMemberDedup(boardMembers);

        long t0 = System.nanoTime();
        for (int r = 0; r < 1000; r++) slowBoardMemberDedup(boardMembers);
        long slowBoardMs = (System.nanoTime() - t0) / 1_000_000;

        long t1 = System.nanoTime();
        for (int r = 0; r < 1000; r++) fastBoardMemberDedup(boardMembers);
        long fastBoardMs = (System.nanoTime() - t1) / 1_000_000;

        System.out.printf("    slow(Array.some): %4dms  %,d ops%n", slowBoardMs, slowBoardOps);
        System.out.printf("    fast(Set.has):    %4dms  %,d ops%n", fastBoardMs, fastBoardOps);
        double boardSpeedup = fastBoardMs > 0 ? (double)slowBoardMs/fastBoardMs : (double)slowBoardOps/fastBoardOps;
        System.out.printf("    op-count ratio: %.1fx%n", (double)slowBoardOps/Math.max(fastBoardOps,1));

        // Card member dedup benchmark
        System.out.println("\n  [wekan-0003b] card member dedup: Array.find O(C*M^2) vs Set O(C*M)");
        long slowCardOps = slowCardMemberDedup(C, cardMembers);
        long fastCardOps = fastCardMemberDedup(C, cardMembers);

        long t2 = System.nanoTime();
        for (int r = 0; r < 100; r++) slowCardMemberDedup(C, cardMembers);
        long slowCardMs = (System.nanoTime() - t2) / 1_000_000;

        long t3 = System.nanoTime();
        for (int r = 0; r < 100; r++) fastCardMemberDedup(C, cardMembers);
        long fastCardMs = (System.nanoTime() - t3) / 1_000_000;

        System.out.printf("    slow(Array.find): %4dms  %,d ops%n", slowCardMs, slowCardOps);
        System.out.printf("    fast(Set.has):    %4dms  %,d ops%n", fastCardMs, fastCardOps);
        System.out.printf("    op-count ratio: %.1fx%n", (double)slowCardOps/Math.max(fastCardOps,1));

        // Correctness check
        List<String> input = Arrays.asList("a","b","a","c","b","d","a");
        List<String> expected = Arrays.asList("a","b","c","d");
        List<String> slowResult = slowDedup(input);
        List<String> fastResult = fastDedup(input);

        int pass = 0, total = 4;

        // Test 1: slow result correct
        if (slowResult.equals(expected)) { pass++; System.out.println("\n  PASS 0003-correctness-slow: Array.contains dedup produces correct result"); }
        else System.out.println("\n  FAIL 0003-correctness-slow: got " + slowResult);

        // Test 2: fast result correct
        if (fastResult.equals(expected)) { pass++; System.out.println("  PASS 0003-correctness-fast: Set dedup produces correct result"); }
        else System.out.println("  FAIL 0003-correctness-fast: got " + fastResult);

        // Test 3: board dedup op-count reduction
        if (slowBoardOps > fastBoardOps * 3) {
            pass++;
            System.out.println("  PASS 0003a: board member slow ops >> fast ops (" + slowBoardOps + " vs " + fastBoardOps + ")");
        } else {
            System.out.println("  FAIL 0003a: expected slowBoardOps > 3*fastBoardOps, got " + slowBoardOps + " vs " + fastBoardOps);
        }

        // Test 4: card dedup op-count reduction
        if (slowCardOps > fastCardOps * 3) {
            pass++;
            System.out.println("  PASS 0003b: card member slow ops >> fast ops (" + slowCardOps + " vs " + fastCardOps + ")");
        } else {
            System.out.println("  FAIL 0003b: expected slowCardOps > 3*fastCardOps, got " + slowCardOps + " vs " + fastCardOps);
        }

        System.out.printf("%n%d/%d PASS%n", pass, total);
        if (pass < total) System.exit(1);
    }
}