engineering/java-topology
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
java-topology/defects/gcc/patch/CLEAN.md
russell@unturf.com bb1a6f002f diamond-scan: llvm/gcc/swift/webkit O(2^D) type hierarchy traversal 
swift-0001: QualifiedLookupRequest::evaluate (NameLookup.cpp:2860) pushes
protocol superclassDecl onto BFS stack unconditionally — visited.insert()
return not checked. Nearby ClassDecl arm (line 2833) is correctly guarded.
Diamond protocol hierarchies sharing a class superclass trigger O(2^D)
re-traversal on every qualified member lookup. Fix: check .second.

llvm, gcc, webkit: CLEAN in available sparse-clone code.
2026-03-29 20:19:38 -04:00

1.2 KiB
Raw Permalink Blame History

CLEAN — GCC

Scanned 2026-03-30 for CWE-407 diamond recursion (O(2^D)).

Scope

Sparse clone: gcc/gcc/ — 524 .cc/.c files. Includes ipa-devirt.cc, dwarf2out.cc, tree.cc, vtable-verify.cc, tree-vect-slp.cc. No cp/class.cc or cp/typeck.cc (cp/ subdirectory not in clone).

Findings

  • ipa-devirt.cc — record_target_from_binfo recurses over BINFO_BASE_ITERATE with matched_vtables->add(BINFO_VTABLE(...)) guard (line 2591). GCC hash_set::add returns true if already present (inverted from std::set). Guard is correctly applied. In addition, GCC's BINFO tree for non-virtual inheritance is a tree (not a DAG), so shared ancestors only appear once per path. For virtual inheritance BINFOs are shared objects — the matched_vtables guard prevents re-traversal. CLEAN.
  • tree-vect-slp.cc — vect_slp_analyze_node_operations uses visited_set.add(node) (returns true if already present = early-out). Correctly guarded. CLEAN.
  • dwarf2out.cc — BINFO base iteration is shallow (direct bases only, non-recursive for diamond purposes). CLEAN.
  • No visited.insert() without .second check found in any .cc file.

Result: No actionable O(2^D) diamond defects in available code.