russell@unturf.com
7af6b9c89f
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).
114 lines
3.4 KiB
Markdown
114 lines
3.4 KiB
Markdown
# 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.
|
|
|
|
```javascript
|
|
// 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:
|
|
|
|
```javascript
|
|
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).
|
|
|
|
```javascript
|
|
// 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.
|