Document the resolver in online documentation

[alexcrichton]

Raised by @ehuss here it's long overdue that the general algorithm of the resolver is documented in the Cargo book (https://doc.rust-lang.org/cargo/).

I think we don't necessarily need to document the whole algorithm per se, but we should go into detail about the various constraints that the resolver is solving for and what a "human readable description" of the problem the resolver is solving is doing. This is where we'd also document the interaction of [patch] with the resolver as well.

cc @Eh2406, you're likely interested in this!

[ehuss]

Yea, I don't think the specifics of the algorithm need to be documented. I do envision adding some high-level user-oriented help for how dependencies work and the consequences of using semver versions. The following are some ideas for things I think would be nice to cover (and currently has little-to-no docs):

• Explain how semver-compatible dependencies are unified to a single version.
  • And explain what "semver-compatible" is, along with examples.
  • Add a little extra emphasis on how API-compatibility relates with "semver-compatible" (and rfc 1105).
  • Explain some of the consequences of not having unified dependencies (like linking both version 1.0 and 2.0 of a lib). For example, downcast-ref can silently break.
• Maybe document how features are unified? I'm reluctant to do so now, since the way it works currently is not great.
• How [patch] works.
• Recommendations on how to manage dependencies and versions.
• How to resolve common problems.

I'm sure we can brainstorm other ideas. I'd personally prefer to gear it towards new/intermediate users, rather than discussing algorithm details.

Here are some examples of other projects:
https://docs.microsoft.com/en-us/nuget/concepts/dependency-resolution
https://golang.github.io/dep/docs/the-solver.html
http://ant.apache.org/ivy/history/latest-milestone/principle.html

[Eh2406]

We from time to time get people that think that Cargo will only bring in 2 versions iif there is a ^ in a dependency (#6876 (comment)). And other in-corect variation on how things work. A chapter to point them to would be great!