java-topology/whitepaper/outreach/gyp.md

GYP — CWE-407 Disclosure Brief (gyp-0001)

2026-04-13 · Patch available — awaiting upstream merge

Finding

One O(n²) defect in GYP's dependency graph cycle detection. The CircularDependencies() method in DependencyGraphNode uses a Python list for path membership checking inside a recursive DFS traversal, causing O(D*P) total cost where D = depth and P = path length.

The Defect

gyp-0001 (PATCHED — MEDIUM): pylib/gyp/input.py:1600 in DependencyGraphNode.CircularDependencies()

def Visit(node, path):
    for child in node.dependents:
        if child in path:  # O(P) list membership test
            results.append([child] + path[:path.index(child) + 1])
        elif not child in visited:
            visited.add(child)
            Visit(child, [child] + path)

The child in path check is O(P) on a Python list where P = current DFS path length. For deep dependency trees with many nodes, total cost across all recursive calls reaches O(N*D) where N = nodes and D = average depth.

Complexity Proof

At N=1,000 nodes with D=50 average depth:

• Defective: each Visit checks child in path at O(D), across N visits = O(N*D²)
• Fixed: child in path_set at O(1), across N visits = O(N*D)
• ~50× op reduction at D=50.

Impact

GYP (Generate Your Projects) is a build configuration tool historically used by Chromium and Node.js. Cycle detection fires during dependency resolution for every build configuration. Large projects with deep dependency chains hit this path.

The Fix

Add a companion path_set (Python set) alongside the path list for O(1) membership testing:

# After
def Visit(node, path, path_set):
    for child in node.dependents:
        if child in path_set:  # O(1) set membership
            results.append([child] + path[:path.index(child) + 1])
        elif not child in visited:
            visited.add(child)
            path_set.add(child)
            Visit(child, [child] + path, path_set)
            path_set.discard(child)

Patch

Fix available: defects/gyp/patch/gyp-0001-path-set.patch

Single-file patch in pylib/gyp/input.py. Path list retained for cycle extraction (path.index), set used for O(1) membership. ~50× speedup at depth 50.

What We Ask

A patch is ready for review.

1. Confirm receipt and assign a GitHub issue reference.
2. Assess severity — fires during every dependency resolution pass.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the GYP team in the public disclosure. Preferred acknowledgment format welcome.

Contact: see cover email. This brief is confidential until coordinated disclosure.