# 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.