Globally optimize traversal in resolve
authorAlex Crichton <alex@alexcrichton.com>
Wed, 9 Mar 2016 00:37:00 +0000 (16:37 -0800)
committerAlex Crichton <alex@alexcrichton.com>
Wed, 9 Mar 2016 00:53:25 +0000 (16:53 -0800)
commit4ec278feff81c8cbb92e37ea3dc6811f62351c7f
treec4ca29f117f8a139a9c534ae00edb460ce1ab900
parent5cb45a93636a23e47d281fe3e53ad284f2bb63e6
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
src/cargo/core/resolver/mod.rs