Rewrite pub's version solver.

sdk/lib/_internal/pub/lib/src/solver/version_selection.dart

Index: sdk/lib/_internal/pub/lib/src/solver/version_selection.dart
diff --git a/sdk/lib/_internal/pub/lib/src/solver/version_selection.dart b/sdk/lib/_internal/pub/lib/src/solver/version_selection.dart
new file mode 100644
index 0000000000000000000000000000000000000000..0534c32311ea5c62a937075a709ee2f68d40bb70
--- /dev/null
+++ b/sdk/lib/_internal/pub/lib/src/solver/version_selection.dart
@@ -0,0 +1,140 @@
+// Copyright (c) 2015, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+library pub.solver.version_selection;
+
+import 'dart:async';
+import 'dart:collection';
+
+import 'package:pub_semver/pub_semver.dart';
+
+import '../package.dart';
+import 'backtracking_solver.dart';
+import 'unselected_package_queue.dart';
+import 'version_solver.dart';
+
+/// A representation of the version solver's current selected versions.
+///
+/// This is used to track the joint constraints from the selected packages on
+/// other packages, as well as the set of packages that are depended on but have
+/// yet to be selected.
+///
+/// A [VersionSelection] is always expected to be internally consistent. That

[Bob Nystrom, 2015/05/14 18:09:38]

Remove "expected to be".

[nweiz, 2015/05/14 22:08:00]

Done.

+/// is, all selected packages will be compatible with dependencies on those

[Bob Nystrom, 2015/05/14 18:09:39]

Future -> present tense.

[nweiz, 2015/05/14 22:08:01]

Done.

+/// packages, no constraints will be empty, and dependencies will agree on
+/// sources and descriptions. However, the selection itself doesn't ensure this;
+/// that's up to the [BacktrackingSolver] that controls it.
+class VersionSelection {
+  /// The version solver.
+  final BacktrackingSolver _solver;
+
+  /// The packages that have been selected, in the other they were selected.

[Bob Nystrom, 2015/05/14 18:09:39]

"other" -> "order".

[nweiz, 2015/05/14 22:08:01]

Done.

+  List<PackageId> get ids => new UnmodifiableListView<PackageId>(_ids);

[Bob Nystrom, 2015/05/14 18:09:39]

Is this worth doing?

[nweiz, 2015/05/14 22:08:00]

Maybe not? I like doing it kind of as a matter of course, since I don't think it
adds much overhead at all.

[Bob Nystrom, 2015/05/14 22:13:02]

<shrug>

In general, I don't worry too much about exposing mutable objects to other parts
of the same application (public library APIs are a different matter), but if you
think it aids maintainability, sure.

+  final _ids = new List<PackageId>();

[Bob Nystrom, 2015/05/14 18:09:38]

<PackageId>[];

[nweiz, 2015/05/14 22:08:00]

Done.

+
+  /// A map from packages to all dependencies from selected packages onto those
+  /// packages.

[Bob Nystrom, 2015/05/14 18:09:39]

This sentence is a bit hard to unpack. How about something a bit more verbose,
like:

"Tracks all of the dependencies on a given package.

Each key is a package. The value is the list of dependencies placed on that
package."

[nweiz, 2015/05/14 22:08:00]

Done.

+  final _dependencies = new Map<String, List<Dependency>>();
+
+  /// A priority queue of packages that are depended on but have yet to be
+  /// selected.
+  final UnselectedPackageQueue _unselected;
+
+  /// The next package for which some version should be selected by the solver.
+  PackageRef get nextUnselected =>
+      _unselected.isEmpty ? null : _unselected.first;
+
+  VersionSelection(BacktrackingSolver solver)
+      : _solver = solver,
+        _unselected = new UnselectedPackageQueue(solver);
+
+  /// Adds [id] to the selection.

[Bob Nystrom, 2015/05/14 18:09:38]

Maybe "select()"?

[nweiz, 2015/05/14 22:08:01]

Done.

+  Future add(PackageId id) async {
+    _unselected.remove(id.toRef());
+    _ids.add(id);
+
+    // TODO(nweiz): Use a real for loop when issue 23394 is fixed.

[Bob Nystrom, 2015/05/14 18:09:39]

How about:

// Add all of id's dependencies to the selection.

[nweiz, 2015/05/14 22:08:00]

Done.

+    await Future.forEach(await _solver.depsFor(id), (dep) async {
+      var deps = getDependencies(dep.name);

[Bob Nystrom, 2015/05/14 18:09:39]

How about:

// Add the new dependency to the existing dependencies on id.

[nweiz, 2015/05/14 22:08:00]

I think this is redundant with the new comment on the loop.

+      deps.add(new Dependency(id, dep));
+
+      // If this is the first dependency on this package, add it to the
+      // unselected queue.
+      if (deps.length == 1 && dep.name != _solver.root.name) {
+        await _unselected.add(dep.toRef());
+
+        // If the package depends on barback, add pub's implicit dependency on
+        // barback and related packages as well.
+        if (dep.name == 'barback') {
+          await _unselected.add(new PackageRef.magic('pub itself'));
+        }
+      }
+    });
+  }
+
+  /// Removes the most recently selected package from the selection.
+  Future removeLast() async {

[Bob Nystrom, 2015/05/14 18:09:38]

"unselectLast()"?

[nweiz, 2015/05/14 22:08:01]

Done.

+    var id = _ids.removeLast();
+    _unselected.add(id.toRef());
+
+    for (var dep in await _solver.depsFor(id)) {
+      var deps = getDependencies(dep.name);
+      deps.removeLast();
+
+      if (deps.isEmpty) {
+        _unselected.remove(dep.toRef());
+
+        // If this was the last pakage that depended on barback, get rid of

[Bob Nystrom, 2015/05/14 18:09:39]

"pakage" -> "package"

[nweiz, 2015/05/14 22:08:00]

Done.

+        // pub's implicit dependency.
+        if (dep.name == 'barback') {
+          _unselected.remove(new PackageRef.magic('pub itself'));
+        }
+      }
+    }
+  }
+
+  /// Returns the selected id for [packageName].
+  PackageId selected(String packageName) =>
+      ids.firstWhere((id) => id.name == packageName, orElse: () => null);
+
+  /// Gets a "required" reference to the package [name].
+  ///
+  /// This is the first non-root dependency on that package. All dependencies
+  /// on a package must agree on source and description, except for references
+  /// to the root package. This will return a reference to that "canonical"
+  /// source and description, or `null` if there is no required reference yet.
+  ///
+  /// This is required because you may have a circular dependency back onto the
+  /// root package. That second dependency won't be a root dependency and it's
+  /// *that* one that other dependencies need to agree on. In other words, you
+  /// can have a bunch of dependencies back onto the root package as long as
+  /// they all agree with each other.
+  Dependency getRequiredDependency(String name) {
+    return getDependencies(name)
+        .firstWhere((dep) => !dep.dep.isRoot, orElse: () => null);
+  }
+
+  /// Gets the combined [VersionConstraint] currently placed on package [name].
+  VersionConstraint getConstraint(String name) {
+    var constraint = getDependencies(name)
+        .map((dep) => dep.dep.constraint)
+        .fold(VersionConstraint.any, (a, b) => a.intersect(b));
+
+    // The caller should ensure that no version gets added with conflicting
+    // constraints.
+    assert(!constraint.isEmpty);
+
+    return constraint;
+  }
+
+  /// Returns a string description of the dependencies on [name].
+  String describeDependencies(String name) =>
+      getDependencies(name).map((dep) => "  $dep").join('\n');
+
+  /// Gets the list of dependencies for package [name].

[Bob Nystrom, 2015/05/14 18:09:38]

"dependencies for" -> "known dependencies on"

[nweiz, 2015/05/14 22:08:00]

Done.

+  ///
+  /// Creates an empty list if needed.
+  List<Dependency> getDependencies(String name) =>

[Bob Nystrom, 2015/05/14 18:09:39]

Maybe "getDependenciesOn"?

[nweiz, 2015/05/14 22:08:00]

Done.

+      _dependencies.putIfAbsent(name, () => <Dependency>[]);
+}