Pub's version resolution goes exponential on a simple pubspec

[nex3]

The following pubspec causes pub's version resolution to go exponential:

  name: app
  dependencies:
    intl: 0.9.0
    polymer: "<=0.9.5"

This happens as of 1.2.0-edge.32615; the exponential churn involves pub's barback constraint, so it may change in future versions. The same pattern should persist, though.

This is caused by a conflicting constraint (intl and recent stack_trace versions have disjoint constraints on path), and compounded by the fact that pub tries to backtrack through every archived version of polymer. We may be able to mitigate this behavior by more aggressively checking for disjoint constraints; we may not be able to avoid checking all older polymer versions, but we can quickly discard them by noticing that their barback constraint is disjoint with pub's.

[munificent]

Removed Priority-Unassigned label.
Added Priority-Medium label.

[munificent]

Set owner to @munificent.
Added Started label.

[munificent]

I spent some time on this, but wasn't able to come up with any simple heuristics or techniques that help. Moving on for now.

---

Added Accepted label.

[nex3]

Issue #23347 has been merged into this issue.

[nex3]

I have some ideas for how to improve this, so I'm going to spend some time on it.

---

Set owner to @nex3.
Added Started label.

[DartBot]

This issue has been moved to dart-lang/pub#874.