russell@unturf.com 7af6b9c89f threejs-0007: Node.traverse() diamond recursion O(2^D); CLEAN for webpack/valhalla/traefik/wasmer/wasmtime; count 621->622

UNDF-2026-000000468: three.js src/nodes/core/Node.js:351 traverse() recurses
without a visited set; on shared-node (diamond) TSL shader graphs yields 2^D
callback invocations. D=10 gives 4093× overhead. Fix: add optional visited Set
parameter, default new Set() at root call.

Unit test: 10/10 PASS (ThreeJSNodeTraverseTest.java)

CLEAN markers written for: webpack (visitedModules WeakSet throughout),
valhalla (Dijkstra+BFS, no recursive DAG traversal), traefik (traverse() has
proper visited map), wasmer (petgraph+BTreeMap), wasmtime (SCC algorithms).

2026-03-29 17:07:25 -04:00

3.4 KiB

Raw Permalink Blame History

UNDF: UNDF-2026-000000468

threejs-0007: Node.traverse() — diamond recursion O(2^D)

Classification

Field	Value
CWE	CWE-407 Inefficient Algorithmic Complexity
Severity	MEDIUM
Component	`src/nodes/core/Node.js:351`
Function	`Node.traverse()`
Hot path	Called during shader material compilation — `ContextNode.getFlowContextData()`, `TSLCore.defined()`, `UniformNode.uniform()`, `RangeNode` setup
Status	PATCHED (unit test PASS)

Defect

Node.traverse() recursively visits child nodes of a shader node graph with no visited set. TSL (Three Shader Language) node graphs are DAGs, not trees — the same node instance can be referenced by multiple parents.

On a diamond DAG (A → {B, C}, B → D, C → D), calling A.traverse(cb) invokes D.traverse(cb) twice — once via B and once via C. At depth D, the bottom node receives 2^D callback invocations.

// src/nodes/core/Node.js:351
traverse( callback ) {

    callback( this );

    for ( const childNode of this.getChildren() ) {

        childNode.traverse( callback );  // NO visited set — exponential on diamonds

    }

}

Why diamond DAGs occur

TSL explicitly encourages node reuse. The same uniform/texture node can appear as an input to multiple operators:

const sharedUniform = uniform( vec3( 1, 0, 0 ) );
// sharedUniform is now a child of BOTH mul and add nodes:
const result = add( mul( sharedUniform, factor ), div( sharedUniform, 2.0 ) );
// result.traverse(cb) → sharedUniform visited TWICE

Any context() node wrapping a complex TSL expression tree can produce a deep diamond DAG during getFlowContextData().

Call sites

Site	When triggered
`ContextNode.getFlowContextData()`	Each shader build (per material compilation)
`TSLCore.defined(value)`	TSL condition evaluation during material setup
`UniformNode.uniform(value)`	Uniform creation with node value
`RangeNode.setup()`	Range node setup during build

Complexity

Topology	Visits to bottom node
Chain of length N	1
Diamond depth 1	2
Diamond depth 3	8
Diamond depth 5	32
Diamond depth 10	1 024
Diamond depth D	2^D

Benchmark (Java simulation)

D=1  diamond: defective=5   fixed=4   ratio=1.3x
D=5  diamond: defective=125 fixed=16  ratio=7.8x
D=10 diamond: defective=4093 fixed=31 ratio=132x

TSL shared-uniform diamond:
  defective: 7 visits (sharedUniform visited twice)
  fixed:     6 visits (each node once)

Unit test: 10/10 PASS (defects/threejs/unit/unit/ThreeJSNodeTraverseTest.java)

Fix

Pass an optional visited Set through the recursion. Default to a fresh Set when called at the root (no API breakage for existing callers).

// FIXED
traverse( callback, visited = new Set() ) {

    if ( visited.has( this ) ) return;  // skip already-visited nodes
    visited.add( this );

    callback( this );

    for ( const childNode of this.getChildren() ) {

        childNode.traverse( callback, visited );

    }

}

All four call sites (ContextNode, TSLCore, UniformNode, RangeNode) call traverse(callback) with no second argument — they automatically get a new visited Set per traversal root, requiring zero changes at call sites.

3.4 KiB Raw Permalink Blame History