Globally optimize traversal in resolve

Currently when we're attempting to resolve a dependency graph we locally
optimize the order in which we visit candidates for a resolution (most
constrained first). Once a version is activated, however, it will add a whole
mess of new dependencies that need to be activated to the global list, currently
appended at the end.

This unfortunately can lead to pathological behavior. By always popping from the
back and appending to the back of pending dependencies, super constrained
dependencies in the front end up not getting visited for quite awhile. This in
turn can cause Cargo to appear to hang for quite awhile as it's so aggressively
backtracking.

This commit switches the list of dependencies-to-activate from a `Vec` to a
`BinaryHeap`. The heap is sorted by the number of candidates for each
dependency, with the least candidates first. This ends up massively cutting down
on resolution times in practice whenever `=` dependencies are encountered
because they are resolved almost immediately instead of way near the end if
they're at the wrong place in the graph.

This alteration in traversal order ended up messing up the existing cycle
detection, so that was just removed entirely from resolution and moved to its
own dedicated pass.

Closes #2090

Auto merge of #2435 - alexcrichton:docs, r=alexcrichton

The API docs for Cargo live at doc.crates.io/cargo, not doc.crates.io in
general.

Auto merge of #2439 - jespino:issue-2402, r=alexcrichton

Add limit parameter to search command (fix issue #2402)

Auto merge of #2438 - jseyfried:subcommands, r=alexcrichton

This PR moves the subcommands in `src/bin` into their own directory and ensures future compatibility with the corrected search paths for non-inline modules (see [Rust PR #32006](https://github.com/rust-lang/rust/pull/32006)).
r? @alexcrichton

Ensure future compatibility with fixed module search paths (see rust PR #32006)

Auto merge of #2423 - alexcrichton:fix-pkgid-hash, r=brson

All crates being compiled by Cargo are identified by a unique `PackageId` instance. This ID incorporates information such as the name, version, and source from where the crate came from. Package ids are allowed to have path sources to depend on local crates on the filesystem. The package id itself encodes the path of where the crate came from.

Historically, however, the "path source" from where these packages are learned had some interesting logic. Specifically one specific source would be able to return many packages within. In other words, a path source would recursively walk crate definitions and the filesystem attempting to find crates. Each crate returned from a source has the same source id, so consequently all packages from one source path would have the same source path id.

This in turn leads to confusing an surprising behavior, for example:

* When crates are compiled the status message indicates the path of the crate root, not the crate being compiled
* When viewed from two different locations (e.g. two different crate roots) the same package would have two different source ids because the id is based on the root location.

This hash mismatch has been [papered over](https://github.com/rust-lang/cargo/pull/1697) in the past to try to fix some spurious recompiles, but it unfortunately [leaked back in](https://github.com/rust-lang/cargo/pull/2279). This is clearly indicative of the "hack" being inappropriate so instead these commits fix the root of the problem.

---

In short, these commits ensure that the package id for a package defined locally has a path that points precisely at that package. This was a relatively invasive change and had ramifications on a few specific portions which now require a bit of extra code to support.

The fundamental change here was to change `PathSource` to be non-recursive by default in terms of what packages it thinks it contains. There are still two recursive use cases, git repositories and path overrides, which are used for backwards compatibility. This meant, however, that the packaging step for crate no longer has knowledge of other crates in a repository to filter out files from. Some specific logic was added to assist in discovering a git repository as well as filtering out sibling packages.

Another ramification of this patch, however, is that special care needs to be taken when decoding a lockfile. We now need all path dependencies in the lockfile to point precisely at where the path dependency came from, and this information is not encoded in the lock file. The decoding support was altered to do a simple probe of the filesystem to recursively walk path dependencies to ensure that we can match up packages in a lock file to where they're found on the filesystem.

Overall, however, this commit closes #1697 and also addresses servo/servo#9794 where this issue was originally reported.

Add a regression test for the issue being fixed

When compiling a package from two separate locations it should be cached the
same way both times.

Fix all tests with recent changes

The package id for path dependencies now has another path component pointing
precisely to the package being compiled, so lots of tests need their output
matches to get updated.

Fix some packaging logic in path sources

Currently the packaging logic depends on the old recursive nature of path
sources for a few points:

* Discovery of a git repository of a package.
* Filtering out of sibling packages for only including the right set of files.

For a non-recursive path source (now essentially the default) we can no longer
assume that we have a listing of all packages. Subsequently this logic was
tweaked to allow:

* Instead of looking for packages at the root of a repo, we instead look for a
  Cargo.toml at the root of a git repository.
* We keep track of all Cargo.toml files found in a repository and prune out all
  files which appear to be ancestors of that package.

Fix decoding lock files with path dependencies

With the previous changes a path dependency must have the precise path to it
listed in its package id. Currently when decoding a lockfile, however, all path
dependencies have the same package id, which unfortunately causes a mismatch.

This commit alters the decoding of a lockfile to perform some simple path
traversals to probe the filesystem to understand where path dependencies are and
set the right package id for the found packages.

Ensure overrides use recursive path sources

This mirrors the behavior that they have today. The `load` method for path
sources will by default return a non-recursive `PathSource` which unfortunately
isn't what we want here.

Remove hacks when hashing package ids

Right now there's a few hacks here and there to "correctly" hash package ids by
taking a package's root path into account instead of the path store in the
package id. The purpose of this was to solve issues where the same package
referenced from two locations ended up having two different hashes.

This hack leaked, however, into the implementation of fingerprints which in
turned ended up causing spurious rebuilds. Fix this problem once and for all by
just defining hashing on package ids the natural and expected way.

Remove usage of PathSource::for_path

This does much more I/O than Package::for_path and this is also on its way out.

Update documentation link for API docs

The API docs for Cargo live at doc.crates.io/cargo, not doc.crates.io in
general.

Auto merge of #2434 - alexcrichton:bump, r=brson

Bump to 0.10.0

Auto merge of #2433 - alexcrichton:fix-lines-match, r=alexcrichton

Right now we only match a suffix of the line, assuming all lines start with
`[..]`. Instead this ensures that the first match is anchored at the start.

Fix output matching in tests

Right now we only match a suffix of the line, assuming all lines start with
`[..]`. Instead this ensures that the first match is anchored at the start.

Auto merge of #2430 - birkenfeld:doc-menu, r=alexcrichton

crates.io pull request: https://github.com/rust-lang/crates.io/pull/276

Doc header: change Documentation to Docs to conform with PR to crates.io

Auto merge of #2406 - alexcrichton:download-less, r=brson

Currently Cargo will download an entire resolution graph all at once when in fact most packages may not be relevant to a compilation. For example target-specific dependencies and dev-dependencies are unconditionally downloaded regardless of whether they're actually needed or not.

This commit alters the internals of Cargo to avoid downloading everything immediately and just switches to lazily downloading packages. This involved adding a new `LazyCell` primitive (similar to the one in use on crates.io) and also propagates `CargoResult` in a few more locations.

Overall this ended up being a pretty large refactoring so the commits are separated in bite-sized chunks as much as possible with the end goal being this PR itself.

Closes #2394

Auto merge of #2419 - dikaiosune:master, r=alexcrichton

Resolves #2417. I also reorganized the order of the items on the page and moved a little bit of text around. I think it's clearer, but critique is more than welcome.

Disambiguating docs about when environment variables are set.
Providing an example of fetching env vars at runtime in a buildscript.
Reordering the list so that examples pertain to the correct sections.

Auto merge of #2418 - alexcrichton:update-git2, r=alexcrichton

This crate was recently updated to the next release of libgit2, and I've noticed
historically that a noop `cargo build` was slow in the git2-rs repository.
Curious to see if the new libgit2 version helped speed things up at all, I
tested it out.

Before this commit, a noop `cargo build` produced 599108 syscalls. After this
commit, a noop build produced 86925 syscalls, an 85% reduction in the number of
syscalls! Needless to say it's much faster.

Update dependency on git2

This crate was recently updated to the next release of libgit2, and I've noticed
historically that a noop `cargo build` was slow in the git2-rs repository.
Curious to see if the new libgit2 version helped speed things up at all, I
tested it out.

Before this commit, a noop `cargo build` produced 599108 syscalls. After this
commit, a noop build produced 86925 syscalls, an 85% reduction in the number of
syscalls! Needless to say it's much faster.

Auto merge of #2397 - alexcrichton:config-verbose, r=brson

This commit adds configuration keys for:

    [term]
    verbose = true
    color = 'auto'

These are all meant to be proxies for the command line flags but configured on a
global basis if desired.

Add configuration keys for -v, --color

This commit adds configuration keys for:

    [term]
    verbose = true
    color = 'auto'

These are all meant to be proxies for the command line flags but configured on a
global basis if desired.

Stop downloading all packages immediately

Instead delay all downloads until just before they're needed. This should ensure
that we don't download any more packages than we really need to.

Auto merge of #2398 - alexcrichton:config-env-var, r=brson

This commit adds a more principled system to rationalize what ends up being a
configuration value versus an environment variable. This problem is solved by
just saying that they're one and the same! Similar to Bundler, this commit
supports overriding the `foo.bar` configuration value with the `CARGO_FOO_BAR`
environment variable.

Currently this is used as part of the `get_string` and `get_i64` methods on
`Config`. This means, for example, that the following environment variables can
now be used to configure Cargo:

* CARGO_BUILD_JOBS
* CARGO_HTTP_TIMEOUT
* CARGO_HTTP_PROXY

Currently it's not supported to encode a list in an environment variable, so for
example `CARGO_PATHS` would not be read when reading the global `paths`
configuration value.

cc #2362
cc #2395 -- intended to close this in tandem with #2397

Auto merge of #2415 - kamalmarhubi:doc-env-var-cargo-manifest-dir, r=alexcrichton

doc: Include CARGO_MANIFEST_DIR as being set for crates

Auto merge of #2411 - sbeckeriv:cargo-cache-doc-update-1609, r=alexcrichton

Per https://github.com/rust-lang/cargo/issues/1609 "clarify how the cache works"

Added in a single line that states that the cached packages are only
removed by running the clean command.

Please let me know if this is the wrong spot, incorrect information or just silly.
Thanks
becker

Auto merge of #2414 - sbeckeriv:document-bit-env-flag-1375, r=alexcrichton

Per https://github.com/rust-lang/cargo/issues/1375

Just add a note around the python script BIT flag.

Fix name

And move line below code block per merge request.

Add a note for the 32 bit flag

Per https://github.com/rust-lang/cargo/issues/1375

Just add a note around the python script flag

Updated text based on pull request

Auto merge of #2407 - alexcrichton:better-failed-auth-error, r=brson

This commit is an attempt to improve the error message from failed
authentication attempts as well as attempting more usernames. Right now we only
attempt one username, but there are four different possible choices we could
select (including $USER which we weren't previously trying).

This commit tweaks a bunch of this logic and just in general refactors the
with_authentication function.

Closes #2399

Auth with more usernames and improve errors

This commit is an attempt to improve the error message from failed
authentication attempts as well as attempting more usernames. Right now we only
attempt one username, but there are four different possible choices we could
select (including $USER which we weren't previously trying).

This commit tweaks a bunch of this logic and just in general refactors the
with_authentication function.

Closes #2399

Auto merge of #2400 - JIghtuse:master, r=alexcrichton

Fixes #2378

Clarify third party subcommand failure error message

Fixes #2378

Add information package caching.

Per https://github.com/rust-lang/cargo/issues/1609
Added in a single line that states that the cached packages are only
removed by running the clean command.

Auto merge of #2369 - alexcrichton:no-more-ar, r=alexcrichton

This is largely no longer needed as we bundle llvm-ar and use that (and it's
cross platform). Note that the underlying support still exists in Cargo as the
flag hasn't been removed from the compiler outright, and older compilers may
still be in use. Just no need to document it so prominently when it's no longer
needed!

Auto merge of #2404 - JIghtuse:no_rebuilds_for_local_install, r=alexcrichton

Fixes #2143

Avoid unnecessary rebuild on local installation

Fixes #2143

Move Context::get_package to returning a Result

The propagate all the `try!`-s needed upwards

Implement a fallible PackageSet::get

This function will lazily download the package specified and fill a cell with
that package. Currently this is always infallible because the `PackageSet` is
initialized with all packages, but eventually this will not be true.

Go through `layout` to get doc dir output directories

Merge the get/download methods on the Source trait

Nothing currently implements the ability to more efficiently download a set of
packages at any one point in time, and the download/get distinction isn't really
used at all. We can always refactor later, but currently there's no benefit, nor
can it really be seen what the possible benefit is, so let's just merge these
two methods into one and have them operate on one id at a time.

Remove SourceSet

This isn't used anywhere

Remove the ability to list packages in PackageSet

If we download lazily, that's excessively wasteful!

Move the `get_package` step later when calculating deps

Future calls to `get_package` may end up actually downloading a package, so we
want to defer this as late as possible to ensure that we don't download
anything.

Refactor build script output state initialization

Like with the previous refactor, remove the need to list all packages in a
package set as we only need to lazily do this for the actual packages being
compiled. Whenever a build script is requested to be executed is when we
actually go and try to see if an override was in play.

Refactor links validation to not use PackageSet

Eventually we may not have the entire set of packages resident in memory, so
refactor the implementation to validate the `links` attribute in a demand driven
way rather than all at once up front.

Fuse SourceMap and PackageSet

This commit moves the SourceMap structure into the PackageSet structure, and
simultaneously massively cuts down on the API surface area of PackageSet. It's
intended that eventually a PackageSet will be a lazily loaded set of packages so
we don't have to download everything all at once, and this is the commit in
preparation of that.

Read configuration from environment variables

This commit adds a more principled system to rationalize what ends up being a
configuration value versus an environment variable. This problem is solved by
just saying that they're one and the same! Similar to Bundler, this commit
supports overriding the `foo.bar` configuration value with the `CARGO_FOO_BAR`
environment variable.

Currently this is used as part of the `get_string` and `get_i64` methods on
`Config`. This means, for example, that the following environment variables can
now be used to configure Cargo:

* CARGO_BUILD_JOBS
* CARGO_HTTP_TIMEOUT
* CARGO_HTTP_PROXY

Currently it's not supported to encode a list in an environment variable, so for
example `CARGO_PATHS` would not be read when reading the global `paths`
configuration value.

cc #2362
cc #2395 -- intended to close this in tandem with #2397

Make Config::get private

Don't actually want to expose this, callers need to use the more concrete
methods anyway.

Refactor configuration return values

Wrap up the value/definition pair in a generic structure so we can extend it
well later.

Auto merge of #2393 - WiSaGaN:bugfix/tests-mod-naming, r=alexcrichton

In the default `lib.rs` provided by `cargo-new`, the "test" module is named "test" while Rust convention is using "tests" as the name of the module: https://doc.rust-lang.org/book/testing.html#the-tests-module
The plural form also conforms with the style used in special directories at project root such as "examples" and "tests".
This pull request conforms to the existing style.

Fix naming of tests mod in cargo new

Auto merge of #2390 - vi:conditionalize_adding_cargo_lock_to_gitignore, r=alexcrichton

For cargo new, it depends on --bin option

For cargo init, it depends on detected files
(--bin option may be used or may be ignored)

No tests conver this code so far.

cargo init: Implement test for conditional Cargo.lock ignoring

Auto merge of #2391 - alexcrichton:update, r=alexcrichton

Fixes compile on nightly

Update tar-rs dependency

Fixes compile on nightly

Auto merge of #2389 - vu3rdd:doc-init, r=alexcrichton

The commit documents the 'cargo init' sub-command in the usage string and in the manpage.

cargo new/init: Conditionalize adding Cargo.lock to gitignore

For cargo new, it depends on --bin option

For cargo init, it depends on detected files
(--bin option may be used or may be ignored)

No tests conver this code so far.

document "cargo init"

Auto merge of #2328 - alexcrichton:target-specific-deps, r=brson

This commit is an implementation of [RFC 1361][rfc] which is an extension of
Cargo's `target` section in `Cargo.toml` to allow the use of `#[cfg]`-like
expressions for target-specific dependencies. Now that the compiler has been
extended with `--print cfg` each invocation of Cargo will scrape this output and
learn about the relevant `#[cfg]` directives in play for the target being
compiled. Cargo will then use these directives to decide whether a dependency
should be activated or not.

This should allow definition of dependencies along the lines of:

    [target.'cfg(unix)'.dependencies]
    [target.'cfg(target_os = "linux")'.dependencies]
    [target.'cfg(windows)'.dependencies]

Which is much more ergonomic and robust than listing all the triples out!

Implement cfg-based target-specific dependencies

This commit is an implementation of [RFC 1361][rfc] which is an extension of
Cargo's `target` section in `Cargo.toml` to allow the use of `#[cfg]`-like
expressions for target-specific dependencies. Now that the compiler has been
extended with `--print cfg` each invocation of Cargo will scrape this output and
learn about the relevant `#[cfg]` directives in play for the target being
compiled. Cargo will then use these directives to decide whether a dependency
should be activated or not.

This should allow definition of dependencies along the lines of:

    [target.'cfg(unix)'.dependencies]
    [target.'cfg(target_os = "linux")'.dependencies]
    [target.'cfg(windows)'.dependencies]

Which is much more ergonomic and robust than listing all the triples out!

Auto merge of #2387 - alexcrichton:update, r=alexcrichton

The new bundled rust version supports unwinding on 32-bit MSVC!

Update some dependencies, plus the rust version

The new bundled rust version supports unwinding on 32-bit MSVC!

Auto merge of #2365 - japaric:env-gt-config, r=alexcrichton

This patches fixes the precedence in these cases:

- CARGO_TARGET_ROOT is now preferred over build.target-dir
- RUSTC is now preferred over build.rustc
- RUSTDOC is now preferred over build.rustdoc

r? @alexcrichton

Auto merge of #2384 - jseyfried:master, r=alexcrichton

r? @alexcrichton

Remove non-inline modules in blocks

Auto merge of #2382 - carols10cents:pointer-to-release-notes, r=alexcrichton

Connects to #1919 - just adds a note and a link to rust's release notes :) :runner:

Add a note about release notes being in Rust's release notes

Auto merge of #2370 - alexcrichton:windows-jobs, r=brson

Currently it's somewhat surprising if you're using cargo and it's then ctrl-c'd.
The child processes that Cargo spawned are likely to still be running around in
the background as they're not killed as well, and this could cause output spew
or future build failures.

This situation is handled by default on Unix because ctrl-c will end up sending
a signal to the entire *process group*, which kills everything, but on Windows
we're not as lucky (just Cargo itself is killed). By using job objects on
Windows we can ensure that the entire tree dies instead of just the top Cargo
process.

cc #2343

Use job objects on windows for ctrl-c to work

Currently it's somewhat surprising if you're using cargo and it's then ctrl-c'd.
The child processes that Cargo spawned are likely to still be running around in
the background as they're not killed as well, and this could cause output spew
or future build failures.

This situation is handled by default on Unix because ctrl-c will end up sending
a signal to the entire *process group*, which kills everything, but on Windows
we're not as lucky (just Cargo itself is killed). By using job objects on
Windows we can ensure that the entire tree dies instead of just the top Cargo
process.

cc #2343

Remove config references to the `ar` tool

This is largely no longer needed as we bundle llvm-ar and use that (and it's
cross platform). Note that the underlying support still exists in Cargo as the
flag hasn't been removed from the compiler outright, and older compilers may
still be in use. Just no need to document it so prominently when it's no longer
needed!

fix: prefer env variables over config files

This patches fixes the precedence in these cases:

- CARGO_TARGET_ROOT is now preferred over build.target-dir
- RUSTC is now preferred over build.rustc
- RUSTDOC is now preferred over build.rustdoc

Auto merge of #2315 - alexcrichton:decode-some-signals, r=brson

Instead of text that looks like

    Process failed (signal: 11)

the text now looks like:

    Process failed (signal: 11, SIGSEGV: invalid memory reference)

Closes #2315

Auto merge of #2359 - matklad:metadata-no-deps, r=alexcrichton

closes #2356. The output is not exactly the same as with `read-manifest`, because I wanted to include the `version` field.

Tests and implementation is a copy-paste from `read-manifest` except that [this line](https://github.com/rust-lang/cargo/blob/master/src/bin/read_manifest.rs#L36) is omited, because `root_package` [does update anyway](https://github.com/rust-lang/cargo/blob/master/src/cargo/sources/path.rs#L51).

metadata: add --no-deps option

The intention is to eventually deprecate `cargo read-manifest`

Auto merge of #2335 - fpgaminer:config-target, r=alexcrichton

Fixed #2332.

This PR adds `build.target` to the Cargo config file, which behaves in the same way as passing `--target` to Cargo.  Example `.cargo/config`:

```
[build]
target = "thumbv6m-none-eabi"
```

Similar to how `--jobs` overrides `build.jobs`, `--target` will override `build.target`.

I added documentation to `config.md`, and a test to `test_cargo_cross_compile.rs`.  I couldn't get cross compile working on my machine for `cargo test`.  Hopefully travis passes it.

This is my first PR against Cargo; sorry if I missed any procedures.

Auto merge of #2357 - matklad:no-more-warnings-in-tests, r=alexcrichton

Warnings from unrelated tests can be a little disturbing. Maybe we should be stricter about them?

You can always temporary `#![allow(unused, warnings)]` in the module you are writing if you are in the middle of a new development and don't want the compiler putting a spoke in the wheel.

Auto merge of #2360 - jedireza:copy-change, r=alexcrichton

Fix typo on build script page

tests: deny warnings

Auto merge of #2355 - alexcrichton:fix-ordering-bug, r=brson

Cargo needs to ensure that if a build script prints a `-L` path that it's the
first `-L` path passed to the compiler. That way the build script can be sure
that any output it generated is the first to be considered by the compiler.

Closes #2354

Fix DAG ordering of passed -L flags

Cargo needs to ensure that if a build script prints a `-L` path that it's the
first `-L` path passed to the compiler. That way the build script can be sure
that any output it generated is the first to be considered by the compiler.

Closes #2354

Auto merge of #2353 - debris:bench_no_run, r=alexcrichton

Closes #2350

fixed cargo bench --no-run

Auto merge of #2351 - rbtcollins:master, r=alexcrichton

Auto merge of #2352 - alexcrichton:new-snapshots, r=alexcrichton

The current snapshot is *super* old (305 days), but as of a few minutes ago it looks like all builds are going to fail with:

```
    Updating registry `https://github.com/rust-lang/crates.io-index`
Failed to parse registry's information for: url

Caused by:
  the given version requirement is not implemented, yet
```

I believe this is because ages ago the semver library wasn't quite fully implemented. The [most recently published url crate](https://crates.io/crates/url/0.5.4) has a version requirement that looks like `>= foo, < bar` which I believe was implemented at some point in the last year.

As a result if we want to keep building Cargo on bors we'll have to upgrade the snapshot, so this does so! For now just pick the absolute newest Cargo to run with and we reset the counters!

Register new snapshots

Fix warning about private types in API.

Auto merge of #2348 - steveklabnik:gh2337, r=alexcrichton

Fixes #2337

Add a test for this too

Auto merge of #2344 - Stebalien:upgrade-term, r=alexcrichton

This PR re-upgrades term to 0.4.3. Cargo now detects whether or not
color is supported immediately after creating the TerminfoTerminal.

Backstory:

Before v0.4, term used to return `Ok(true)` if something succeeded,
`Ok(false)` if the operation was unsupported, and `Err(io::Error)` if there
was an IO error. Now, it returns `Ok(())` if the operation succeeds and
`Err(term::Error)` if the operation fails. If the operation is unsupported,
it returns `Err(term::Error::NotSupported)`. This means that, if `op` is
unsupported, `try!(term.op())` will now return an error instead of silently
failing (well, return false but that's effectively silent).

Fixes #2338.

Don't fall back on stderr if color is unavailable

Having a TTY has no bearing on color support.