Update semver to have `^` be the default operator
Split out encoding from `core::resolver` to a submodule

Same exported hierarchy, just some internal orgainzational changes.
Implement resolution of version requirements

This commit extends the support in cargo's resolver to start resolving packages
with multiple versions as well as package requirements. This is a crucial step
forward when impelmenting the cargo registry as multiple versions will be
uploaded to the registry quite quickly!

This implements a fairly naive solution which should at least help cargo get out
the gates initially. This impelments a depth-first-search of the pacakage
dependency graph with a few sorting heuristics along the way to help out
resolution as it goes along.

Resolution errors will likely improve over time, but this commit does make an
effort to try to get some good error messages right off the bat.
Make PackageId cheap to clone

These are cloned a massive number of times during resolution, so let's make them
much cheaper to clone with an Arc. This uses Arc instead of Rc because the
fiddly bits in job_queue have a PackageId cross task boundaries for parallelism.
Make SourceId cheap to clone

Like PackageId, these are cloned quite often, so this moves them into an Arc to
make them cheap to clone. This also removes the public fields in favor of
accessors.
Continue reducing clone costs

Share the `visited` hash set among all contexts, just be sure to maintain it
across failures. Also put all Summary structures into an `Rc` as they're cloned
quite frequently.
source changes
Avoid visiting deps too often in resolve

If we're activating an already-active version of a dependency, then there's no
need to actually recurse into it. Instead, we can skip it if we're not enabling
any extra features in it to avoid extraneous recursion.
Make to_url public for rustc
auto merge of #717 : alexcrichton/cargo/souped-up-resolve, r=wycats

This series of commits is rebased on top of https://github.com/rust-lang/cargo/pull/712 to avoid conflicts, and it adds the ability to solve version constraints as part of the resolution process. This is a critical step forward in bringing the registry online as it makes it possible for cargo to figure out what to do in the face of many uploaded versions of a package to the registry.

r? @wycats
Add a metadata section to the lockfile

In terms of future compatibility, Cargo may wish to add more information to
lockfiles in the future. For example, the minimum required Rust version may one
day be encoded into a lockfile.

One of the major goals of a lockfile is for it to rarely change, and when it
does change the diffs should be minimal. In terms of adding more information to
the lockfile in the future, this presents a problem for older Cargo clients:

1. Cargo 2.0 adds a minimum required version of rust under the metadata.rustc
   key of the lockfile.
2. Cargo 1.0 is then used to update the `foo` dependency in the lockfile. When
   regenerating the lockfile, Cargo 1.0 discards the metadata inserted by Cargo
   2.0.

In order to future-proof ourselves in allowing new metadata in the future, Cargo
is growing support now for transporting an opaque payload of metadata from one
version of a lockfile to a new versions. This should solve the problem presented
above.

This metadata section is designed to be safely ignored by older Cargo versions
(may just have some surprising behavior), while still allowing newer versions of
Cargo to process the data. For example Cargo 2.0 would gracefully fail on an
out-of-date rustc, while Cargo 1.0 may just present an obscure error message.