java-topology/tests/freecad/FreeCADCwe407Test.java

import java.util.*;

/**
 * CWE-407 simulation tests for FreeCAD defects.
 *
 * freecad-0001: ifc_generator.py done-list O(N^2) dedup in generate_shape/generate_coin
 * freecad-0002: importDXF.py processededges list O(E^2) membership
 */
public class FreeCADCwe407Test {

    // ---- freecad-0001: IFC generator done-list dedup ----

    /** DEFECTIVE: done = list, item.id not in done → O(N) per check, O(N^2) total */
    static int ifcGeneratorDoneList_defective(int N) {
        List<Integer> done = new ArrayList<>();
        int ops = 0;
        for (int i = 0; i < N; i++) {
            int id = i; // simulate unique IFC element IDs
            // O(N) linear scan
            boolean found = false;
            for (int j = 0; j < done.size(); j++) {
                ops++;
                if (done.get(j) == id) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                done.add(id);
            }
        }
        return ops;
    }

    /** PATCHED: done = set, item.id not in done → O(1) per check, O(N) total */
    static int ifcGeneratorDoneSet_patched(int N) {
        Set<Integer> done = new HashSet<>();
        int ops = 0;
        for (int i = 0; i < N; i++) {
            int id = i;
            ops++; // O(1) hash lookup
            if (!done.contains(id)) {
                done.add(id);
            }
        }
        return ops;
    }

    // ---- freecad-0002: DXF processededges list membership ----

    /** DEFECTIVE: processededges = list, hashCode not in processededges → O(E^2) */
    static int dxfProcessedEdges_defective(int E) {
        List<Integer> processededges = new ArrayList<>();
        int ops = 0;
        // Phase 1: build processededges from wires
        int wiresEdges = E * 3 / 4; // 75% edges in wires
        for (int i = 0; i < wiresEdges; i++) {
            processededges.add(i); // hashCode of edge
        }
        // Phase 2: find lone edges via linear scan
        for (int i = 0; i < E; i++) {
            int hashCode = i;
            for (int j = 0; j < processededges.size(); j++) {
                ops++;
                if (processededges.get(j) == hashCode) {
                    break;
                }
            }
        }
        return ops;
    }

    /** PATCHED: processededges = set → O(1) lookup per edge */
    static int dxfProcessedEdges_patched(int E) {
        Set<Integer> processededges = new HashSet<>();
        int ops = 0;
        int wiresEdges = E * 3 / 4;
        for (int i = 0; i < wiresEdges; i++) {
            processededges.add(i);
        }
        for (int i = 0; i < E; i++) {
            ops++; // O(1) hash lookup
            processededges.contains(i);
        }
        return ops;
    }

    public static void main(String[] args) {
        int passed = 0;
        int failed = 0;

        // --- freecad-0001 tests ---
        {
            int N = 1000;
            int defOps = ifcGeneratorDoneList_defective(N);
            int patOps = ifcGeneratorDoneSet_patched(N);
            double ratio = (double) defOps / patOps;

            System.out.printf("freecad-0001 IFC generator done-list (N=%d):%n", N);
            System.out.printf("  defective ops: %d%n", defOps);
            System.out.printf("  patched ops:   %d%n", patOps);
            System.out.printf("  ratio:         %.1fx%n", ratio);

            // defective should be O(N^2/2) ≈ 499,500 ops; patched = N = 1000
            if (ratio > 100) {
                System.out.println("  PASS: ratio > 100x confirms O(N^2) vs O(N)");
                passed++;
            } else {
                System.out.println("  FAIL: expected ratio > 100x, got " + ratio);
                failed++;
            }
        }

        // --- freecad-0002 tests ---
        {
            int E = 1000;
            int defOps = dxfProcessedEdges_defective(E);
            int patOps = dxfProcessedEdges_patched(E);
            double ratio = (double) defOps / patOps;

            System.out.printf("freecad-0002 DXF processededges (E=%d):%n", E);
            System.out.printf("  defective ops: %d%n", defOps);
            System.out.printf("  patched ops:   %d%n", patOps);
            System.out.printf("  ratio:         %.1fx%n", ratio);

            if (ratio > 50) {
                System.out.println("  PASS: ratio > 50x confirms O(E^2) vs O(E)");
                passed++;
            } else {
                System.out.println("  FAIL: expected ratio > 50x, got " + ratio);
                failed++;
            }
        }

        System.out.printf("%n%d/%d tests passed%n", passed, passed + failed);
        if (failed > 0) {
            System.exit(1);
        }
    }
}