java-topology/defects/opentoonz-0001/unit/OpentoonzAutocloseTest.java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Test for opentoonz-0001: CWE-407 spotResearchOnePoint() in autoclose.cpp
 * calls std::find on a std::vector<Segment> inside the endpoint loop.
 *
 * Pattern (toonz/sources/toonzlib/autoclose.cpp):
 *   for (int i = 0; i < (int)endpoints.size(); ++i) {  // E iterations
 *       Segment segment = ...;
 *       std::find(closingSegments.begin(), closingSegments.end(), segment); // O(C)
 *   }
 *   // C grows with each push_back — O(E * C) -> O(E^2) worst case
 *
 * Fix: use std::set<Segment> for O(log C) or std::unordered_set for O(1).
 *
 * Compile and run (no build tool required):
 *   javac defects/opentoonz-0001/unit/OpentoonzAutocloseTest.java \
 *         -d /tmp/opentoonz-0001
 *   java -cp /tmp/opentoonz-0001 OpentoonzAutocloseTest
 */
public class OpentoonzAutocloseTest {

    private static int passed = 0;
    private static int failed = 0;

    // --- Minimal Segment model (pair of integer points) ---

    static final class Segment {
        final int x1, y1, x2, y2;

        Segment(int x1, int y1, int x2, int y2) {
            this.x1 = x1; this.y1 = y1;
            this.x2 = x2; this.y2 = y2;
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Segment)) return false;
            Segment s = (Segment) o;
            return x1 == s.x1 && y1 == s.y1 && x2 == s.x2 && y2 == s.y2;
        }

        @Override
        public int hashCode() {
            int h = 17;
            h = h * 31 + x1;
            h = h * 31 + y1;
            h = h * 31 + x2;
            h = h * 31 + y2;
            return h;
        }
    }

    // --- Defective: linear scan dedup ---

    static List<Segment> deduplicateDefective(List<Segment> candidates,
                                              List<Segment> existing) {
        List<Segment> closing = new ArrayList<>(existing);
        for (Segment seg : candidates) {                // E iterations
            boolean found = false;
            for (Segment s : closing) {                 // O(C) linear scan
                if (s.equals(seg)) { found = true; break; }
            }
            if (!found) {
                closing.add(seg);                       // C grows
            }
        }
        return closing;
    }

    // --- Fixed: hash set dedup ---

    static List<Segment> deduplicateFixed(List<Segment> candidates,
                                          List<Segment> existing) {
        Set<Segment> seen = new HashSet<>(existing.size() * 2 + candidates.size() * 2);
        List<Segment> closing = new ArrayList<>(existing);
        seen.addAll(existing);

        for (Segment seg : candidates) {          // E iterations
            if (seen.add(seg)) {                  // O(1) hash set
                closing.add(seg);
            }
        }
        return closing;
    }

    // --- Helpers ---

    static List<Segment> buildSegments(int count) {
        List<Segment> segs = new ArrayList<>(count);
        for (int i = 0; i < count; i++) {
            segs.add(new Segment(i, i, i + 1, i + 1));
        }
        return segs;
    }

    static List<Segment> buildDuplicates(List<Segment> source, int dupeCount) {
        List<Segment> dupes = new ArrayList<>(dupeCount);
        for (int i = 0; i < dupeCount; i++) {
            dupes.add(source.get(i % source.size()));
        }
        return dupes;
    }

    // --- Tests ---

    static void testNoDuplicatesAdded() {
        List<Segment> existing = buildSegments(20);
        List<Segment> candidates = buildDuplicates(existing, 10);  // all duplicates

        List<Segment> defResult = deduplicateDefective(candidates, existing);
        List<Segment> fixResult = deduplicateFixed(candidates, existing);

        check("defective: no duplicates added (stays at 20)", defResult.size() == 20);
        check("fixed: no duplicates added (stays at 20)",     fixResult.size() == 20);
    }

    static void testNewSegmentsAdded() {
        List<Segment> existing = buildSegments(10);
        List<Segment> newSegs  = buildSegments(5);
        // shift them so they don't collide with existing
        List<Segment> shifted = new ArrayList<>();
        for (Segment s : newSegs) shifted.add(new Segment(s.x1 + 1000, s.y1, s.x2, s.y2));

        List<Segment> defResult = deduplicateDefective(shifted, existing);
        List<Segment> fixResult = deduplicateFixed(shifted, existing);

        check("defective: 5 new segments added (total 15)", defResult.size() == 15);
        check("fixed: 5 new segments added (total 15)",     fixResult.size() == 15);
    }

    static void testResultsMatchUnderMixedInput() {
        List<Segment> existing   = buildSegments(30);
        List<Segment> duplicates = buildDuplicates(existing, 15);
        List<Segment> newSegs    = new ArrayList<>();
        for (int i = 0; i < 10; i++) newSegs.add(new Segment(i + 5000, i, i + 1, i + 1));

        List<Segment> candidates = new ArrayList<>();
        candidates.addAll(duplicates);
        candidates.addAll(newSegs);

        List<Segment> defResult = deduplicateDefective(candidates, existing);
        List<Segment> fixResult = deduplicateFixed(candidates, existing);

        check("results match between defective and fixed (mixed input, 30+10=40 expected)",
              defResult.size() == fixResult.size() && fixResult.size() == 40);
    }

    static void testPerformanceRatio() {
        // E=500 endpoints, C grows to ~500 — simulates a complex inked frame
        // The defective impl is O(E*C) ~ O(500*500) = 250,000 comparisons
        int E = 500;
        List<Segment> existing   = new ArrayList<>();
        List<Segment> candidates = buildSegments(E);  // all unique
        int iterations = 200;

        // Warm up JIT
        for (int i = 0; i < 5; i++) {
            deduplicateDefective(candidates, existing);
            deduplicateFixed(candidates, existing);
        }

        long t0 = System.nanoTime();
        for (int i = 0; i < iterations; i++) deduplicateDefective(candidates, existing);
        long defectiveNs = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int i = 0; i < iterations; i++) deduplicateFixed(candidates, existing);
        long fixedNs = System.nanoTime() - t0;

        double ratio = (double) defectiveNs / fixedNs;
        System.out.printf("  [perf] defective=%.1fms fixed=%.1fms ratio=%.1fx%n",
            defectiveNs / 1e6, fixedNs / 1e6, ratio);
        check("fixed path is at least 2.5x faster (E=500, all unique segments)", ratio >= 2.5);
    }

    // --- Harness ---

    static void check(String desc, boolean cond) {
        if (cond) {
            System.out.println("  PASS: " + desc);
            passed++;
        } else {
            System.out.println("  FAIL: " + desc);
            failed++;
        }
    }

    public static void main(String[] args) {
        System.out.println("=== OpentoonzAutocloseTest (opentoonz-0001, CWE-407) ===\n");

        testNoDuplicatesAdded();
        testNewSegmentsAdded();
        testResultsMatchUnderMixedInput();
        testPerformanceRatio();

        System.out.println("\n--- " + passed + " passed, " + failed + " failed ---");
        if (failed > 0) System.exit(1);
    }
}