npm / arborist / #139

push

Resolve infinite dependency nesting with a symlink

Fix #96

In a case like http://npm.im/@isaacs/pathological-dep-nesting-a we have
a dependency cycle that would nest infinitely:

```
a@1 -> b@1
a@2 -> b@2
b@1 -> a@2
b@2 -> a@1
```

When trying to reify this, we have to nest another a@2 under b@1,
because it would otherwise resolve to a@1.  Then that a@2 needs a b@2,
which has to nest or otherwise resolve to b@1, and the cycle goes on.

The actual (deduped) reified tree looks like:

```
root
+-- a@1
+-- b@1 (deduped from a@1's dep)
    +-- a@2 (overriding a@1 one level up)
    +-- b@2 (deduped from a@2's dep)
        +-- a@1 (overriding a@2 from one level up)
        +-- b@1 (deduped from a@1's dep)
            +-- a@2 (loop forever...)
```

With this commit, the loop is cut by detecting in buildIdealTree that a
node being added to resolve a problemEdge is satisfying an edge that
already has an identical node in its ancestor set.

Ie, in this example, when we get to the second a@1, we need to place b@1
to satisfy its dependency, or else it will resolve to b@2 (its parent).
Since the edge is a problem, we know that the nearest resolution is
_not_ a match (or else we wouldn't be bothering to add it).  Thus, any
node in the ancestry that matches the node we're attempting to add to
the tree is certainly going to cause an infinite regress, because its
presence has caused it to need to load another identical copy of itself.

While we could throw in this situation (and it'd certainly be better
than spinning forever trying to build an infinitely large tree), we can
do better, by instead creating a symbolic link to the matching node
further up the tree.  This is almost as efficient as throwing, and
produces a correct dependency resolution.

Thus, instead of growing infinitely, the resulting tree looks like:

```
root
+-- a@1
+-- b@1
    +-- a@2
    +-- b@2
        +-- a@1
        +-- b@1 (symlink to root/node_modules/b)
```

When using legacyBundling, the tre... (continued)

1953 of 1953 branches covered (100.0%)

Branch coverage included in aggregate %.

2872 of 2872 relevant lines covered (100.0%)

311.95 hits per line