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.5 KiB

Raw Permalink Blame History

freecad-0004 — SketchAnalysis::detectMissingEqualityConstraints O(C * E_eq)

Location

src/Mod/Sketcher/App/SketchAnalysis.cpp — SketchAnalysis::detectMissingEqualityConstraints() lines ~747–800

Pattern

MOAD-0001 (CWE-407): std::find_if on a std::list inside a loop.

for (auto it : constraint) {
    if (it->Type == Sketcher::Equal) {
        auto pos = std::find_if(equallines.begin(), equallines.end(),
                                Constraint_Equal(id));  // O(E_eq)
        if (pos != equallines.end())
            equallines.erase(pos);
        // same for equalradius
    }
}

Complexity

equallines (and equalradius) are std::list<ConstraintIds> built by EqualityConstraints::getEqualLines/getEqualRadius. For a sketch with M identical-length lines, those lists contain O(M^2) entries.

Outer loop: O(C) Equal constraints
Inner find_if: O(E_eq) = O(M^2) in worst case
Total: O(C * M^2)

At C=100, M=50 (E_eq=2,500): ~250,000 comparisons vs ~100 with a hash map.

Fix

Index each candidate in an unordered_multimap<(GeoId,GeoId), ConstraintIds> using a canonical (min,max) key. Each of the C constraint lookups becomes O(1). Total: O(E_eq + C) = O(M^2 + C).

Severity

MEDIUM-HIGH — called on every "auto-constrain" or "analyse sketch" operation. Parametric sketches with many parallel/equal features trigger extreme E_eq.

MOAD-0002/0003/0004/0005

Same conclusions as freecad-0003 SCAN-NOTES (document model is single-threaded; no thread_local request-scope carriers; no credential logging in scanned scope).

1.5 KiB Raw Permalink Blame History Unescape Escape