npm Arborist — CWE-407 Analysis
=================================

.. contents:: :local:

Overview
--------

npm Arborist is the dependency tree builder and installer used by npm (Node Package Manager),
the package manager for the JavaScript/Node.js ecosystem. It builds an ideal dependency tree
via graph traversal and placement algorithms. Two CWE-407 defect sites were found in the
ideal-tree builder and peer-dependency placement logic. Both are unpatched.

Defect Sites
------------

npm-0001
~~~~~~~~

**File:** ``workspaces/arborist/lib/arborist/build-ideal-tree.js:63``

**Pattern:**

.. code-block:: javascript

   // Dependency queue — Array.includes() for deduplication
   class DepsQueue {
     constructor() {
       this.queue = [];
     }

     add(node) {
       if (!this.queue.includes(node)) {   // O(|queue|) per add
         this.queue.push(node);
       }
     }

     shift() {
       return this.queue.shift();
     }
   }

**Why this is O(n):** ``Array.includes()`` is O(n); called on every ``add()`` operation as
the queue fills during ideal-tree construction.

**Complexity:** ``O(K²)`` where K = number of nodes enqueued during ideal-tree build

**Patch:**

.. code-block:: javascript

   class DepsQueue {
     constructor() {
       this.queue = [];
       this.queued = new Set();   // O(1) membership
     }

     add(node) {
       if (!this.queued.has(node)) {   // O(1)
         this.queued.add(node);
         this.queue.push(node);
       }
     }

     shift() {
       const node = this.queue.shift();
       this.queued.delete(node);
       return node;
     }
   }

**Data structure change:** ``Array`` + ``includes()`` → ``Array`` + companion ``Set`` + ``has()``

**Status:** Unpatched

Benchmark Results
-----------------

.. TODO: benchmark pending patch

Complexity Proof
----------------

Let K = nodes enqueued. ``Array.includes`` on an array of up to K elements: O(K) per call.
With K calls total: O(K²). ``Set.has`` is O(1): O(K) total. QED.

References
----------

* Defect ticket: ``tools/tickets/defects/npm-0001.md``

npm-0002
~~~~~~~~

**File:** ``workspaces/arborist/lib/arborist/can-place-dep.js:370``

**Pattern:**

.. code-block:: javascript

   // Peer dependency path traversal — Array.includes() on peerPath
   canPlaceDep(dep, target, edge, peerPath = []) {
     // ...
     for (const peerEdge of target.edgesIn) {
       if (peerPath.includes(peerEdge.from)) {
         // cycle detected — O(|peerPath|) per check
         continue;
       }
       const result = this.canPlaceDep(
         dep, peerEdge.from, edge,
         [...peerPath, target]
       );
       // ...
     }
   }

**Why this is O(n):** ``Array.includes`` on the accumulated ``peerPath`` array; path length
grows with peer-dependency chain depth.

**Complexity:** ``O(depth²)`` where depth = peer dependency chain depth (MEDIUM severity —
real defect, bounded by peer dep chain length in practice)

**Patch:**

.. code-block:: javascript

   canPlaceDep(dep, target, edge, peerPath = new Set()) {
     // ...
     for (const peerEdge of target.edgesIn) {
       if (peerPath.has(peerEdge.from)) {   // O(1)
         continue;
       }
       const newPath = new Set(peerPath);
       newPath.add(target);
       const result = this.canPlaceDep(dep, peerEdge.from, edge, newPath);
       // ...
     }
   }

**Data structure change:** ``Array`` + ``includes()`` → ``Set`` + ``has()``

**Status:** Unpatched

Benchmark Results
-----------------

.. TODO: benchmark pending patch

Complexity Proof
----------------

Let depth = peer dependency chain depth. ``Array.includes`` on peerPath of up to depth
elements: O(depth) per call. With depth recursive calls: O(depth²). ``Set.has`` is O(1):
O(depth) total. QED.

References
----------

* Defect ticket: ``tools/tickets/defects/npm-0002.md``
