Document install algorithm better.

Thanks to @ded for the prod:
https://twitter.com/ded/status/112215356692639744

1 files changed, 67 insertions, 12 deletions

diff --git a/html/doc/install.html b/html/doc/install.html
index 5d80b136a..3a7308f7f 100644
--- a/html/doc/install.html
+++ b/html/doc/install.html
@@ -25,34 +25,40 @@ npm install &lt;name&gt;@&lt;version range&gt;</code></pre>
 
 <p>A <code>package</code> is:</p>
 
-<ul><li>a) a folder containing a program described by a package.json file</li><li>b) a gzipped tarball containing (a)</li><li>c) a url that resolves to (b)</li><li>d) a <code>&lt;name&gt;@&lt;version&gt;</code> that is published on the registry with (c)</li><li>e) a <code>&lt;name&gt;@&lt;tag&gt;</code> that points to (d)</li><li>f) a <code>&lt;name&gt;</code> that has a "latest" tag satisfying (e)</li></ul>
+<ul><li>a) a folder containing a program described by a package.json file</li><li>b) a gzipped tarball containing (a)</li><li>c) a url that resolves to (b)</li><li>d) a <code>&lt;name&gt;@&lt;version&gt;</code> that is published on the registry with (c)</li><li>e) a <code>&lt;name&gt;@&lt;tag&gt;</code> that points to (d)</li><li>f) a <code>&lt;name&gt;</code> that has a "latest" tag satisfying (e)</li><li>g) a <code>&lt;git remote url&gt;</code> that resolves to (b)</li></ul>
 
 <p>Even if you never publish your package, you can still get a lot of
 benefits of using npm if you just want to write a node program (a), and
 perhaps if you also want to be able to easily install it elsewhere
 after packing it up into a tarball (b).</p>
 
-<ul><li><p>npm install (in package directory, no arguments):
+<ul><li><p><code>npm install</code> (in package directory, no arguments):
 Install the dependencies in the local node_modules folder.</p><p>In global mode (ie, with <code>-g</code> or <code>--global</code> appended to the command),
 it installs the current package context (ie, the current working
-directory) as a global package.</p></li><li><p>npm install <code>&lt;folder&gt;</code>:
-Install a package that is sitting in a folder on the filesystem.</p></li><li><p>npm install <code>&lt;tarball file&gt;</code>:
+directory) as a global package.</p></li><li><p><code>npm install &lt;folder&gt;</code>:
+Install a package that is sitting in a folder on the filesystem.</p></li><li><p><code>npm install &lt;tarball file&gt;</code>:
 Install a package that is sitting on the filesystem.  Note: if you just want
 to link a dev directory into your npm root, you can do this more easily by
-using <code>npm link</code>.</p><p>In order to distinguish between this and remote installs, the argument
-must either be "." or contain a "/" in it.</p><p>Example:</p><pre><code>npm install ./package.tgz</code></pre></li><li><p>npm install <code>&lt;tarball url&gt;</code>:
+using <code>npm link</code>.</p><p>Example:</p><pre><code>npm install ./package.tgz</code></pre></li><li><p><code>npm install &lt;tarball url&gt;</code>:
 Fetch the tarball url, and then install it.  In order to distinguish between
-this and other options, the argument must start with "http://" or "https://"</p><p>Example:</p><pre><code>npm install http://github.com/waveto/node-crypto/tarball/v0.0.5</code></pre></li><li><p>npm install <code>&lt;name&gt;</code>:
+this and other options, the argument must start with "http://" or "https://"</p><p>Example:</p><pre><code>npm install https://github.com/indexzero/forever/tarball/v0.5.6</code></pre></li><li><p><code>npm install &lt;name&gt;</code>:
 Do a <code>&lt;name&gt;@&lt;tag&gt;</code> install, where <code>&lt;tag&gt;</code> is the "tag" config. (See
-<code><a href="config.html">config</a></code>)</p><p>Example:</p><pre><code>npm install sax</code></pre></li><li><p>npm install <code>&lt;name&gt;@&lt;tag&gt;</code>:
+<code><a href="config.html">config</a></code>)</p><p>Example:</p><pre><code>npm install sax</code></pre><p><strong>Note</strong>: If there is a file or folder named <code>&lt;name&gt;</code> in the current
+working directory, then it will try to install that, and only try to
+fetch the package by name if it is not valid.</p></li><li><p><code>npm install &lt;name&gt;@&lt;tag&gt;</code>:
 Install the version of the package that is referenced by the specified tag.
 If the tag does not exist in the registry data for that package, then this
-will fail.</p><p>Example:</p><pre><code>npm install sax@stable</code></pre></li><li><p>npm install <code>&lt;name&gt;@&lt;version&gt;</code>:
+will fail.</p><p>Example:</p><pre><code>npm install sax@latest</code></pre></li><li><p><code>npm install &lt;name&gt;@&lt;version&gt;</code>:
 Install the specified version of the package.  This will fail if the version
-has not been published to the registry.</p><p>Example:</p><pre><code>npm install sax@0.1.1</code></pre></li><li><p>npm install <code>&lt;name&gt;@&lt;version range&gt;</code>:
+has not been published to the registry.</p><p>Example:</p><pre><code>npm install sax@0.1.1</code></pre></li><li><p><code>npm install &lt;name&gt;@&lt;version range&gt;</code>:
 Install a version of the package matching the specified version range.  This
 will follow the same rules for resolving dependencies described in <code><a href="json.html">json</a></code>.</p><p>Note that most version ranges must be put in quotes so that your shell will
-treat it as a single argument.</p><p>Example:</p><pre><code>npm install sax@"&gt;=0.1.0 &lt;0.2.0"</code></pre></li></ul>
+treat it as a single argument.</p><p>Example:</p><pre><code>npm install sax@"&gt;=0.1.0 &lt;0.2.0"</code></pre></li><li><p><code>npm install &lt;git remote url&gt;</code>:</p><p>Install a package by cloning a git remote url.  The format of the git
+url is:</p><pre><code>&lt;protocol&gt;://[&lt;user&gt;@]&lt;hostname&gt;&lt;separator&gt;&lt;path&gt;[#&lt;commit-ish&gt;]</code></pre><p><code>&lt;protocol&gt;</code> is one of <code>git</code>, <code>git+ssh</code>, <code>git+http</code>, or
+<code>git+https</code>.  If no <code>&lt;commit-ish&gt;</code> is specified, then <code>master</code> is
+used.</p><p>Examples:</p><pre><code>git+ssh://git@github.com:isaacs/npm.git#v1.0.27
+git+https://isaacs@github.com/isaacs/npm.git
+git://github.com/isaacs/npm.git#v1.0.27</code></pre></li></ul>
 
 <p>You may combine multiple arguments, and even multiple types of arguments.
 For example:</p>
@@ -75,9 +81,58 @@ local space in some cases.</p>
 <p>See <code><a href="config.html">config</a></code>.  Many of the configuration params have some
 effect on installation, since that's most of what npm does.</p>
 
+<h2 id="ALGORITHM">ALGORITHM</h2>
+
+<p>To install a package, npm uses the following algorithm:</p>
+
+<pre><code>install(where, what, family, ancestors)
+fetch what, unpack to &lt;where&gt;/node_modules/&lt;what&gt;
+for each dep in what.dependencies
+  resolve dep to precise version
+for each dep@version in what.dependencies
+    not in &lt;where&gt;/node_modules/&lt;what&gt;/node_modules/*
+    and not in &lt;family&gt;
+  add precise version deps to &lt;family&gt;
+  install(&lt;where&gt;/node_modules/&lt;what&gt;, dep, family)</code></pre>
+
+<p>For this <code>package{dep}</code> structure: <code>A{B,C}, B{C}, C{D}</code>,
+this algorithm produces:</p>
+
+<pre><code>A
++-- B
+`-- C
+    `-- D</code></pre>
+
+<p>That is, the dependency from B to C is satisfied by the fact that A
+already caused C to be installed at a higher level.</p>
+
+<p>See <a href="folders.html">folders</a> for a more detailed description of the specific
+folder structures that npm creates.</p>
+
+<h3 id="Limitations-of-npm-s-Install-Algorithm">Limitations of npm's Install Algorithm</h3>
+
+<p>There are some very rare and pathological edge-cases where a cycle can
+cause npm to try to install a never-ending tree of packages.  Here is
+the simplest case:</p>
+
+<pre><code>A -&gt; B -&gt; A' -&gt; B' -&gt; A -&gt; B -&gt; A' -&gt; B' -&gt; A -&gt; ...</code></pre>
+
+<p>where <code>A</code> is some version of a package, and <code>A'</code> is a different version
+of the same package.  Because <code>B</code> depends on a different version of <code>A</code>
+than the one that is already in the tree, it must install a separate
+copy.  The same is true of <code>A'</code>, which must install <code>B'</code>.  Because <code>B'</code>
+depends on the original version of <code>A</code>, which has been overridden, the
+cycle falls into infinite regress.</p>
+
+<p>To avoid this situation, npm flat-out refuses to install any
+<code>name@version</code> that is already present anywhere in the tree of package
+folder ancestors.  A more correct, but more complex, solution would be
+to symlink the existing version into the new location.  If this ever
+affects a real use-case, it will be investigated.</p>
+
 <h2 id="SEE-ALSO">SEE ALSO</h2>
 
-<ul><li><a href="update.html">update</a></li><li><a href="link.html">link</a></li><li><a href="rebuild.html">rebuild</a></li><li><a href="scripts.html">scripts</a></li><li><a href="build.html">build</a></li><li><a href="config.html">config</a></li><li><a href="registry.html">registry</a></li><li><a href="folders.html">folders</a></li><li><a href="tag.html">tag</a></li><li><a href="rm.html">rm</a></li></ul>
+<ul><li><a href="folders.html">folders</a></li><li><a href="update.html">update</a></li><li><a href="link.html">link</a></li><li><a href="rebuild.html">rebuild</a></li><li><a href="scripts.html">scripts</a></li><li><a href="build.html">build</a></li><li><a href="config.html">config</a></li><li><a href="registry.html">registry</a></li><li><a href="folders.html">folders</a></li><li><a href="tag.html">tag</a></li><li><a href="rm.html">rm</a></li></ul>
 </div>
 <p id="footer">install &mdash; npm@1.0.28-pre-DEV-UNSTABLE</p>
 <script>