55 lines
2.3 KiB
Markdown
55 lines
2.3 KiB
Markdown
# solvespace-0001 — MOAD-0001 CWE-407
|
||
|
||
## Location
|
||
|
||
`src/entity.cpp`, `EntityBase::GenerateEquations()`, line 955
|
||
Called from `src/system.cpp`, `System::WriteEquationsExceptFor()`, line 387
|
||
|
||
## Pattern
|
||
|
||
O(E_arc × C): `System::WriteEquationsExceptFor` iterates over all entities
|
||
(`for(auto &ent : SK.entity)`). For each entity of type `ARC_OF_CIRCLE`, our
|
||
`GenerateEquations` performs a full linear scan over all constraints to check
|
||
whether our arc's endpoints are already coincidence-constrained:
|
||
|
||
```cpp
|
||
// In System::WriteEquationsExceptFor (system.cpp:383):
|
||
for(auto &ent : SK.entity) { // O(E) outer loop
|
||
e->GenerateEquations(&eq); // calls into entity.cpp
|
||
}
|
||
|
||
// In EntityBase::GenerateEquations (entity.cpp:955):
|
||
auto it = std::find_if(SK.constraint.begin(), SK.constraint.end(),
|
||
[&](ConstraintBase const &con) {
|
||
return (con.group == group) &&
|
||
(con.type == Constraint::Type::POINTS_COINCIDENT) &&
|
||
((con.ptA == point[1] && con.ptB == point[2]) || ...);
|
||
});
|
||
```
|
||
|
||
Each arc entity triggers an O(C) walk over all constraints. With A arc entities
|
||
and C total constraints, our equation generation is O(A × C).
|
||
|
||
## Severity
|
||
|
||
MEDIUM. A mechanical sketch with many arc segments and many constraints is normal
|
||
in parametric CAD. A sketch with 50 arcs and 200 constraints → 10,000 comparisons
|
||
per solve step instead of 250. Each interactive drag triggers a re-solve. At
|
||
A=100, C=500: 50,000 comparisons vs 600 with a hash set. 83x overhead.
|
||
|
||
## Fix
|
||
|
||
Build a `std::unordered_set<uint64_t>` of coincident endpoint pairs for our group
|
||
on our first arc encountered, keyed as `(ptA.v << 32) | ptB.v` with both orderings
|
||
inserted. Cache with a `static thread_local` (Solvespace is single-threaded on
|
||
our solve path; thread_local provides zero-cost per-call isolation). Lookup is O(1)
|
||
per arc. Cache is invalidated per group (hGroup key). Total cost per call is
|
||
O(C) to build once + O(A) for lookups.
|
||
|
||
## All 5 MOADs
|
||
|
||
- MOAD-0001: CONFIRMED (this defect)
|
||
- MOAD-0002: CLEAN (SK/SS globals are intentional single-user desktop CAD singletons)
|
||
- MOAD-0003: CLEAN (single-threaded solve path; no request-scoped context)
|
||
- MOAD-0004: CLEAN (no network features, no credential handling)
|
||
- MOAD-0005: CLEAN (single-threaded, no concurrent cache access)
|