Auto merge of #5168 - Eh2406:faster_resolver, r=alexcrichton

Faster resolver: Cache past conflicting_activations, prevent doing the same work repeatedly.

This work is inspired by @alexcrichton's [comment](https://github.com/rust-lang/cargo/issues/4066#issuecomment-303912744) that a slow resolver can be caused by all versions of a dependency being yanked. Witch stuck in my brain as I did not understand why it would happen. If a dependency has no candidates then it will be the most constrained and will trigger backtracking in the next tick. Eventually I found a reproducible test case. If the bad dependency is deep in the tree of dependencies then we activate and backtrack `O(versions^depth)`  times. Even tho it is fast to identify the problem that is a lot of work.

**The set up:**
1. Every time we backtrack cache the (dep, `conflicting_activations`).
2. Build on the work in #5000, Fail to activate if any of its dependencies will just backtrack to this frame. I.E. for each dependency check if any of its cached `conflicting_activations` are already all activated. If so we can just skip to the next candidate. We also add that bad `conflicting_activations` to our set of  `conflicting_activations`, so that we can...

**The pay off:**
 If we fail to find any candidates that we can activate in lite of 2, then we cannot be activated in this context, add our (dep, `conflicting_activations`) to the cache so that next time our parent will not bother trying us.

I hear you saying "but the error messages, what about the error messages?" So if we are at the end `!has_another` then we disable this optimization. After we mark our dep as being not activatable then we activate anyway. It won't resolve but it will have the same error message as before this PR. If we have been activated for the error messages then skip straight to the last candidate, as that is the only backtrack that will end with the user.

I added a test in the vain of #4834. With the old code the time to run was `O(BRANCHING_FACTOR ^ DEPTH)` and took ~3min with DEPTH = 10; BRANCHING_FACTOR = 5; with the new code it runs almost instantly with 200 and 100.

more comments

Only activate for the better error messages if we will bactrack to the user

test that cashing works with constraints correctly

Auto merge of #5152 - matklad:clap, r=alexcrichton

Clap

Reopening of #5129

So, looks like all tests are :green_apple: on my machine!

I definitely want to refactor it some more, and also manually checked that we haven't regressed any help messages, but all the major parts are in place already.

make sure cashing works whether there is an answer or not

only jump to the end if our frame was made for the error message

File per command

if a frame will fail make it top priority

Use `avoid_dev_deps` for all commands

Fix spelling of quiet

Auto merge of #5167 - xftroxgpx:nosubmodules, r=matklad

Closes #5165

#5165

if we are just here_for the error_messages then only try the last candidate

cache past conflicting_activations use them to prevent doing the same work repeatedly

reduce the mut args to find_candidate

this test is slow because it runs the same searches repeatedly

Closes #5165

Auto merge of #5164 - matthiaskrgr:redundant_dep, r=alexcrichton

remove "filetime 0.1" dependency from dev profile, filetime is already a regular dep

remove "filetime 0.1" dependency from dev profile, filetime is already a regular dependency.

Cleanups

Relax tests for windows

On windows, clap prints `cargo.exe` rather than just `cargo`.

Validate the limit argument

Tweak the help message

Move `index` & `registry` to `ArgMatchesExt`

Move `new_options` to `ArgMatchesExt`

Move `compile_options` to `ArgMatchesExt`

Make `target` option owned in various configs

Move some arg parsing to ArgMatchesExt

Introduce ArgMatchesExt trait

Inline `config_from_args`

Rename CommonArgs -> AppExt

Reorganize subcommands as a separate submodule

Move command_prelude to a separate file

Introduce command_prelude module

Auto merge of #5160 - ishitatsuyuki:patch-1, r=matklad

Remove unused import

Remove unused import

Auto merge of #5159 - ishitatsuyuki:patch-1, r=Mark-Simulacrum

Remove redundant recursion_limit

Now that we have migrate from error-chain to failure, we no longer need to extend it.

Remove redundant recursion_limit

Now that we have migrate from error-chain to failure, we no longer need to extend it.

Auto merge of #5126 - gilescope:cycle-error-message, r=alexcrichton

Error message for package "depends on itself" lists the packages in the cycle.

I got a cycle while trying to build someone else's code and cargo's error message didn't point me in the right direction, just mentioned there was a cycle. I thought we could be a bit more helpful.

Don't know what you think of {:#?} as the display but it seemed minimal code so I thought I'd start with that. I could compress the output to one package per line if preferred.

Clippy complains about unused in derived code.

Auto merge of #5157 - Eh2406:more_interning, r=alexcrichton

More interning

This is a forward approach to interning. Specifically `Dependency` and `PackageId` store their names as `InternedString`s and leave that value interned as long as possible. The alternative is to make a new `interned_name` function. The advantage of this approach is that a number of places in the code are doing `deb.name() == pid.name()` and are now using the fast pointer compare instead of the string compare, without the code needing to change. The disadvantage is that lots of places need to call `deref` with `&*` to convert to an `&str` and sum need to use `.to_inner()` to get a `&'static str`.

In a test on https://github.com/rust-lang/cargo/issues/4810#issuecomment-357553286
Before we got to 10000000 ticks in ~48 sec
After we got to 10000000 ticks in ~44 sec

delay calls to `to_inner`

Dependency.name to InternedString

Make command-line arguments owned

Validate that `jobs` argument is a number

Unwind stack for cli errors

PackageId.name to InternedString

Remove dead code

Remove docopt dependency

Fix after rebase

Fix typo

Remove dead code

Fix `--explain`

Support list subcommand

All tests are green :tada:

Support aliases

Fix more tests by updating error messages

Unignore test which now passes

Disable `cargo help -h`

Fix verify-project command

Support built-in aliases

Support external subcommands

Cleanup

Restore global initialization

Use exit code 1 for command line parsing errors

Note that while we use 101 in majority of cases, sometimes we use 1 as
well.

Fix some trivially fixable tests

Drop old commands

Move the rest of the commands to clap

Move uninstall to clap

Move test to clap

Move search to clap

Don't copy-paste index argument

Don't copy-paste package argument

Move rustdoc to clap

Move rustc to clap

Move run to clap

Move read-manifest to clap

Move publish to clap

Move pkgid to clap

Move package to clap

Move owner to clap

Move new to clap

Move metadata to clap

Move login to clap

Move locate-project to clap

Move install to clap

Specify frozen & locked for all commands simultaneously

Move init to clap

Move git-checkout to clap

Move generate-lockfile to clap

Move fetch to clap

Move doc to clap

Move clean to clap

Move check to clap

Temporarly ignore some tests

Port bench and build to clap

Switch to exhaustive matches in tests.

Auto merge of #5150 - Eh2406:more_interning, r=alexcrichton

More interning

This is a small part of the unsuccessful last commit of #5121, this part removes `InternedString::new` from the innerest of loops.

This is mostly a resubmission of #5147, that I accidentally deleted while bors was testing. This one has new commits, so github will take the resubition.

intern links attribute

Auto merge of #5147 - Eh2406:restucture, r=alexcrichton

restructure `Activations` for better clone

This builds on the work in #5121 When we last met we had:
5000000 ticks in ~48 sec, 0r 104k ticks/sec
This small change brings us to:
5000000 ticks in ~21 sec, 0r 238k ticks/sec
Edit: sorry for the large diff only the last commit is new. The rest are from #5121

restructure `Activations` for better clone