russell@unturf.com 3bf7ed2cec freecad+kicad: 5-MOAD scan; 3 CWE-407 defects, MOAD 0002-0005 CLEAN

freecad-0003: CrossSection::removeDuplicates O(W^2*E) wire dedup via
std::find_if over growing list; fix: hash-keyed seen-set O(W*E log E).
Severity MEDIUM-HIGH, ~200x at W=400 duplicate wires.

freecad-0004: SketchAnalysis::detectMissingEqualityConstraints O(C*M^2)
std::find_if over std::list of equal-line/radius candidates; fix:
unordered_multimap keyed on canonical (GeoId,GeoId) pair, O(C).
Severity MEDIUM-HIGH, ~5x at C=50/M=50, grows with M^2.

kicad-0003: BOARD_NETLIST_UPDATER::testConnectivity calls FindPadByNumber
(O(P) linear scan) for each of N pins per footprint; fix: build
unordered_map<padNumber,PAD*> once per footprint, O(P+N) total.
Severity HIGH, ~19x at P=256 pads, ~512x at P=512 pads.

MOAD-0002/0003/0004/0005: CLEAN for both projects (documented in SCAN-NOTES).

2026-03-31 22:09:45 -04:00

1.6 KiB

Raw Permalink Blame History

freecad-0003 — CrossSection::removeDuplicates O(W^2 * E)

Location

src/Mod/Part/App/CrossSection.cpp — CrossSection::removeDuplicates()

Pattern

MOAD-0001 (CWE-407): std::find_if linear scan inside a loop.

For each of W wires produced by a cross-section slice, removeDuplicates performs a std::find_if over wires_reduce (currently up to W entries). Each comparison reconstructs edge maps for both wires and iterates E edges.

Complexity

Outer loop: O(W) wires
Inner find_if: O(W) linear scan over wires_reduce
Per-comparison: O(E) edge iteration
Total: O(W^2 * E)

At W=200, E=8: 320,000 operations vs 1,600 with a hash-keyed seen-set (~200x).

Fix

Build a canonical key for each wire (sorted vector of TShape pointers, O(E log E)) and store it in an unordered_set. Membership test is O(1). Total: O(W * E log E).

Severity

MEDIUM-HIGH — triggered on every Section() operation on a complex solid. Complex assemblies (lattice parts, fasteners) generate many coincident wires.

MOAD-0002/0003/0004/0005

MOAD-0002: FreeCAD App::Document is a large coordinator, but CrossSection is a standalone algorithm class. No actionable new coupling found.
MOAD-0003: ViewProviderLink.cpp uses static thread_local for transform re-entrancy guard (not request-scoped identity). CLEAN.
MOAD-0004: AddonManager module not included in our sparse clone. No credential logging found in Part/Sketcher/FEM modules scanned. CLEAN in scanned scope.
MOAD-0005: FreeCAD document model is single-threaded (Python GIL + Qt main thread). No unsynchronized concurrent cache write found. CLEAN.

1.6 KiB Raw Permalink Blame History