Allow circular dependencies on the root source in Pub.

utils/pub/version_solver.dart

 // Copyright (c) 2012, 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.
 
 /**
  * Attempts to resolve a set of version constraints for a package dependency
  * graph and select an appropriate set of best specific versions for all
  * dependent packages. It works iteratively and tries to reach a stable
  * solution where the constraints of all dependencies are met. If it fails to
  * reach a solution after a certain number of iterations, it assumes the
@@ skipping 165 matching lines @@
 
   /**
    * Looks for a package that depends (transitively) on [dependency] and has its
    * version locked in the lockfile. If one is found, enqueues an
    * [UnlockPackage] work item for it and returns true. Otherwise, returns
    * false.
    *
    * This does a breadth-first search; immediate dependers will be unlocked
    * first, followed by transitive dependers.
    */
-  bool tryUnlockDepender(Dependency dependency) {
+  bool tryUnlockDepender(Dependency dependency, [Set<String> seen]) {
+    if (seen == null) seen = new Set();
+    if (seen.contains(dependency.name)) return false;

[Bob Nystrom, 2012/09/20 01:19:54]

How about a comment: // Avoid infinite loop if the graph has cycles.

[nweiz, 2012/09/24 22:31:16]

Done.

+    seen.add(dependency.name);
+
     for (var dependerName in dependency.dependers) {
       var depender = getDependency(dependerName);
       var locked = lockFile.packages[dependerName];
       if (locked != null && depender.version == locked.version) {
         enqueue(new UnlockPackage(depender));
         return true;
       }
     }
-    return dependency.dependers.map(getDependency).some(tryUnlockDepender);
+    
+    return dependency.dependers.map(getDependency).some((subdependency) =>
+        tryUnlockDepender(subdependency, seen));
   }
 
   List<PackageId> buildResults() {
     return _packages.getValues().filter((dep) => dep.isDependedOn).map((dep) {
       var description = dep.description;
 
       // If the lockfile contains a fully-resolved description for the package,
       // use that. This allows e.g. Git to ensure that the same commit is used.
       var lockedPackage = lockFile.packages[dep.name];
       if (lockedPackage != null && lockedPackage.version == dep.version &&
@@ skipping 310 matching lines @@
    */
   final String name;
 
   /**
    * The [PackageRefs] that represent constraints that depending packages have
    * placed on this one.
    */
   final Map<String, PackageRef> _refs;
 
   /**
-   * The source of this dependency's package.
-   *
-   * All constraints in [_refs] must have this as their source.
-   */
-  Source source;
-
-  /**
-   * The description of this dependency's package.
-   *
-   * All constraints in [_refs] must have a description equivalent to this one
-   * according to [source].
-   */
-  var description;
-
-  /**
    * The currently-selected best version for this dependency.
    */
   Version version;
 
   /**
    * Whether this dependency should always select the latest version.
    */
   bool useLatestVersion = false;
 
   /**
@@ skipping 10 matching lines @@
    * Gets the overall constraint that all packages are placing on this one.
    * If no packages have a constraint on this one (which can happen when this
    * package is in the process of being added to the graph), returns `null`.
    */
   VersionConstraint get constraint {
     if (_refs.isEmpty()) return null;
     return new VersionConstraint.intersect(
         _refs.getValues().map((ref) => ref.constraint));
   }
 
+  /// The source of this dependency's package.
+  Source get source {
+     var canonical = _canonicalRef();
+     if (canonical == null) return null;
+     return canonical.source;
+  }
+
+  /// The description of this dependency's package.
+  get description {
+     var canonical = _canonicalRef();
+     if (canonical == null) return null;
+     return canonical.description;
+  }
+
+  /// Return the PackageRef that has the canonical source and description for
+  /// this package. If any dependency requires that this package come from a
+  /// [RootSource], that will be used; otherwise, it will be the source and
+  /// description that all dependencies agree upon.
+  PackageRef _canonicalRef() {
+    if (_refs.isEmpty()) return null;
+    var refs = _refs.getValues();
+    for (var ref in refs) {
+      if (ref is RootSource) return ref;
+    }
+    return refs[0];
+  }
+
   Dependency(this.name)
       : _refs = <String, PackageRef>{};
 
   Dependency._clone(Dependency other)
       : name = other.name,
-        source = other.source,
-        description = other.description,
         version = other.version,
         _refs = new Map<String, PackageRef>.from(other._refs);
 
   /** Creates a copy of this dependency. */
   Dependency clone() => new Dependency._clone(this);
 
   /// Return a list of available versions for this dependency.
   Future<List<Version>> getVersions() => source.getVersions(name, description);
 
   /**
    * Places [ref] as a constraint from [package] onto this.
    */
   void placeConstraint(String package, PackageRef ref) {
-    // If this isn't the first constraint placed on this package, make sure it
-    // matches the source and description of past constraints.
-    if (_refs.isEmpty()) {
-      source = ref.source;
-      description = ref.description;
-    } else if (source.name != ref.source.name) {
-      throw new SourceMismatchException(name, source, ref.source);
-    } else if (!source.descriptionsEqual(description, ref.description)) {
-      throw new DescriptionMismatchException(
-          name, description, ref.description);
+    var required = _requiredRef();
+    if (required != null) {
+      if (required.source.name != ref.source.name) {
+        throw new SourceMismatchException(name, required.source, ref.source);
+      } else if (!required.source.descriptionsEqual(
+                     required.description, ref.description)) {
+        throw new DescriptionMismatchException(
+            name, required.description, ref.description);
+      }
     }
 
     _refs[package] = ref;
   }
 
+  /// Returns a PackageRef whose source and description any new constraints are
+  /// required to match. Returns null if there are no requirements on new
+  /// constraints.
+  PackageRef _requiredRef() {
+    if (_refs.isEmpty()) return null;
+    var refs = _refs.getValues();
+    var first = refs[0];
+    if (refs.length == 1) {
+      if (first.source is RootSource) return null;
+      return first;
+    }
+    return refs[1];
+  }
+
   /**
    * Removes the constraint from [package] onto this.
    */
-  PackageRef removeConstraint(String package) {
-    var removed = _refs.remove(package);
-
-    if (_refs.isEmpty()) {
-      source = null;
-      description = null;
-    }
-
-    return removed;
-  }
+  PackageRef removeConstraint(String package) => _refs.remove(package);
 }
 
 // TODO(rnystrom): Report the last of depending packages and their constraints.
 /**
  * Exception thrown when the [VersionConstraint] used to match a package is
  * valid (i.e. non-empty), but there are no released versions of the package
  * that fit that constraint.
  */
 class NoVersionException implements Exception {
   final String package;
@@ skipping 73 matching lines @@
   final description1;
   final description2;
 
   DescriptionMismatchException(this.package, this.description1,
       this.description2);
 
   // TODO(nweiz): Dump to YAML when that's supported
   String toString() => "Package '$package' has conflicting descriptions "
     "'${JSON.stringify(description1)}' and '${JSON.stringify(description2)}'";
 }