java-topology/defects/prusaslicer-0002/test/PrusaSlicerSupportIslandWorklistTest.java

import java.util.*;

/**
 * Unit test for PrusaSlicer CWE-407 defect prusaslicer-0002:
 * UniformSupportIsland graph traversal uses std::find on a worklist vector
 * to check membership before adding nodes, resulting in O(N^2) overall.
 * Fix: maintain a parallel unordered_set for O(1) membership checks.
 *
 * Defect location: src/libslic3r/SLA/SupportIslands/UniformSupportIsland.cpp
 * Pattern: std::find(process.begin(), process.end(), item_index) in while-true graph loop
 */
public class PrusaSlicerSupportIslandWorklistTest {

    // --- DEFECTIVE: O(N^2) worklist with linear membership check ---
    static int processWorklistDefective(int N) {
        List<Integer> process = new ArrayList<>();
        for (int i = 0; i < N; i++) process.add(i);
        int ops = 0;

        // Simulate the graph traversal checking membership for each neighbor
        for (int current = 0; current < N; current++) {
            // Each node has ~3 neighbors to check
            for (int d = 0; d < 3; d++) {
                int neighbor = (current * 3 + d) % N;
                if (process.contains(neighbor)) {  // O(N) linear scan
                    ops++;
                }
            }
        }
        return ops;
    }

    // --- FIXED: O(N) worklist with hash set membership ---
    static int processWorklistFixed(int N) {
        List<Integer> process = new ArrayList<>();
        Set<Integer> processSet = new HashSet<>();
        for (int i = 0; i < N; i++) {
            process.add(i);
            processSet.add(i);
        }
        int ops = 0;

        for (int current = 0; current < N; current++) {
            for (int d = 0; d < 3; d++) {
                int neighbor = (current * 3 + d) % N;
                if (processSet.contains(neighbor)) {  // O(1) hash lookup
                    ops++;
                }
            }
        }
        return ops;
    }

    public static void main(String[] args) {
        // Correctness
        int rDef = processWorklistDefective(100);
        int rFix = processWorklistFixed(100);
        assert rDef == rFix : "Operation count must match: " + rDef + " vs " + rFix;
        System.out.println("PASS correctness: " + rFix + " operations");

        int N = 20_000;

        // Warmup
        for (int i = 0; i < 3; i++) {
            processWorklistDefective(N);
            processWorklistFixed(N);
        }

        long t0 = System.nanoTime();
        int rDefLarge = processWorklistDefective(N);
        long t1 = System.nanoTime();
        int rFixLarge = processWorklistFixed(N);
        long t2 = System.nanoTime();

        double defMs = (t1 - t0) / 1e6;
        double fixMs = (t2 - t1) / 1e6;
        double ratio = defMs / fixMs;

        assert rDefLarge == rFixLarge : "Large results must match";
        System.out.printf("PASS defective: %.1f ms, fixed: %.1f ms, ratio: %.1fx%n", defMs, fixMs, ratio);
        assert ratio > 2.0 : "Fixed should be at least 2x faster, got " + ratio + "x";
        System.out.println("PASS performance: ratio " + String.format("%.1f", ratio) + "x");
        System.out.println("ALL TESTS PASSED");
    }
}