Initial approach to discovering package resolution for directory tree.

R=brianwilkerson@google.com, pquitslund@google.com

Review URL: https://codereview.chromium.org//1169513002.

pkgs/package_config/lib/discovery_analysis.dart

diff --git a/pkgs/package_config/lib/discovery_analysis.dart b/pkgs/package_config/lib/discovery_analysis.dart
new file mode 100644
index 0000000..f3bcac6
--- /dev/null
+++ b/pkgs/package_config/lib/discovery_analysis.dart
@@ -0,0 +1,167 @@
+// 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.
+
+/// Analyse a directory structure and find packages resolvers for each
+/// sub-directory.
+///
+/// The resolvers are generally the same that would be found by using
+/// the `discovery.dart` library on each sub-directory in turn,
+/// but more efficiently and with some heuristics for directories that
+/// wouldn't otherwise have a package resolution strategy, or that are
+/// determined to be "package directories" themselves.
+library package_config.discovery_analysis;
+
+import "dart:io" show File, Directory;
+import "dart:collection" show HashMap;
+
+import "package:path/path.dart" as path;
+
+import "packages.dart";
+import "discovery.dart";
+import "packages_file.dart" as pkgfile;
+import "src/packages_impl.dart";
+import "src/packages_io_impl.dart";
+
+/// Associates a [Packages] package resolution strategy with a directory.
+///
+/// The package resolution applies to the directory and any sub-directory
+/// that doesn't have its own overriding child [PackageContext].
+abstract class PackageContext {
+  /// The directory that introduced the [packages] resolver.
+  Directory get directory;
+
+  /// A [Packages] resolver that applies to the directory.
+  ///
+  /// Introduced either by a `.packages` file or a `packages/` directory.
+  Packages get packages;
+
+  /// Child contexts that apply to sub-directories of [directory].
+  List<PackageContext> get children;
+
+  /// Look up the [PackageContext] that applies to a specific directory.
+  ///
+  /// The directory must be inside [directory].
+  PackageContext operator[](Directory directory);
+
+  /// A map from directory to package resolver.
+  ///
+  /// Has an entry for this package context and for each child context
+  /// contained in this one.
+  Map<Directory, Packages> asMap();
+
+  /// Analyze [directory] and sub-directories for package resolution strategies.
+  ///
+  /// Returns a mapping from sub-directories to [Packages] objects.
+  ///
+  /// The analysis assumes that there are no `.packages` files in a parent
+  /// directory of `directory`. If there is, its corresponding `Packages` object
+  /// should be provided as `root`.
+  static PackageContext findAll(Directory directory,
+                                {Packages root: Packages.noPackages}) {
+    if (!directory.existsSync()) {
+      throw new ArgumentError("Directory not found: $directory");
+    }
+    List contexts = [];
+    void findRoots(Directory directory) {
+      Packages packages;
+      List oldContexts;
+      File packagesFile = new File(path.join(directory.path, ".packages"));
+      if (packagesFile.existsSync()) {
+        packages = _loadPackagesFile(packagesFile);
+        oldContexts = contexts;
+        contexts = [];
+      } else {
+        Directory packagesDir =
+            new Directory(path.join(directory.path, "packages"));
+        if (packagesDir.existsSync()) {
+          packages = new FilePackagesDirectoryPackages(packagesDir);
+          oldContexts = contexts;
+          contexts = [];
+        }
+      }
+      for (var entry in directory.listSync()) {
+        if (entry is Directory) {
+          if (packages == null || !entry.path.endsWith("/packages")) {
+            findRoots(entry);
+          }
+        }
+      }
+      if (packages != null) {
+        oldContexts.add(new _PackageContext(directory, packages, contexts));
+        contexts = oldContexts;
+      }
+    }
+    findRoots(directory);
+    // If the root is not itself context root, add a the wrapper context.
+    if (contexts.length == 1 &&
+        contexts[0].directory == directory) {
+      return contexts[0];
+    }
+    return new _PackageContext(directory, root, contexts);
+  }
+}
+
+class _PackageContext implements PackageContext {
+  final Directory directory;
+  final Packages packages;
+  final List<PackageContext> children;
+  _PackageContext(this.directory, this.packages, List<PackageContext> children)
+      : children = new List<PackageContext>.unmodifiable(children);
+
+  Map<Directory, Packages> asMap() {
+    var result = new HashMap<Directory, Packages>();
+    recurse(_PackageContext current) {
+      result[current.directory] = current.packages;
+      for (var child in current.children) {
+        recurse(child);
+      }
+    }
+    recurse(this);
+    return result;
+  }
+
+  PackageContext operator[](Directory directory) {
+    String path = directory.path;
+    if (!path.startsWith(this.directory.path)) {
+      throw new ArgumentError("Not inside $path: $directory");
+    }
+    _PackageContext current = this;
+    // The current path is know to agree with directory until deltaIndex.
+    int deltaIndex = current.directory.path.length;
+    List children = current.children;
+    int i = 0;
+    while (i < children.length) {
+      // TODO(lrn): Sort children and use binary search.
+      _PackageContext child = children[i];
+      String childPath = child.directory.path;
+      if (_stringsAgree(path, childPath, deltaIndex, childPath.length)) {
+        deltaIndex = childPath.length;
+        if (deltaIndex == path.length) {
+          return child;
+        }
+        current = child;
+        children = current.children;
+        i = 0;
+        continue;
+      }
+      i++;
+    }
+    return current;
+  }
+
+  static bool _stringsAgree(String a, String b, int start, int end) {
+    if (a.length < end || b.length < end) return false;
+    for (int i = start; i < end; i++) {
+      if (a.codeUnitAt(i) != b.codeUnitAt(i)) return false;
+    }
+    return true;
+  }
+}
+
+Packages _loadPackagesFile(File file) {
+  var uri = new Uri.file(file.path);
+  var bytes = file.readAsBytesSync();
+  var map = pkgfile.parse(bytes, uri);
+  return new MapPackages(map);
+}

pkgs/package_config/pubspec.yaml

diff --git a/pkgs/package_config/pubspec.yaml b/pkgs/package_config/pubspec.yaml
index 5eca330..0f2735b 100644
--- a/pkgs/package_config/pubspec.yaml
+++ b/pkgs/package_config/pubspec.yaml
@@ -1,5 +1,5 @@
 name: package_config
-version: 0.0.3+1
+version: 0.0.4
 description: Support for working with Package Resolution config files.
 author: Dart Team <misc@dartlang.org>
 homepage: https://github.com/dart-lang/package_config

pkgs/package_config/test/discovery_analysis_test.dart

diff --git a/pkgs/package_config/test/discovery_analysis_test.dart b/pkgs/package_config/test/discovery_analysis_test.dart
new file mode 100644
index 0000000..ad007c0
--- /dev/null
+++ b/pkgs/package_config/test/discovery_analysis_test.dart
@@ -0,0 +1,122 @@
+// 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.
+
+import "dart:async";
+import "dart:io";
+
+import "package:package_config/discovery_analysis.dart";
+import "package:package_config/packages.dart";
+import "package:path/path.dart" as path;
+import "package:test/test.dart";
+
+main() {
+  fileTest("basic",
+           {".packages": packagesFile,
+            "foo": {".packages": packagesFile},
+            "bar": {"packages": {"foo": {}, "bar":{}, "baz": {}}},
+            "baz": {}},
+           (Directory directory) {
+    var dirUri = new Uri.directory(directory.path);
+    PackageContext ctx = PackageContext.findAll(directory);
+    PackagesContext root = ctx[directory];
+    expect(root, same(ctx));
+    validatePackagesFile(root.packages, dirUri);
+    var fooDir = sub(directory, "foo");
+    PackagesContext foo = ctx[fooDir];
+    expect(identical(root, foo), isFalse);
+    validatePackagesFile(foo.packages, dirUri.resolve("foo/"));
+    var barDir = sub(directory, "bar");
+    PackagesContext bar = ctx[sub(directory, "bar")];
+    validatePackagesDir(bar.packages, dirUri.resolve("bar/"));
+    PackagesContext barbar = ctx[sub(barDir, "bar")];
+    expect(barbar, same(bar));  // inherited.
+    PackagesContext baz = ctx[sub(directory, "baz")];
+    expect(baz, same(root));  // inherited.
+
+    var map = ctx.asMap();
+    expect(map.keys.map((dir) => dir.path),
+           unorderedEquals([directory.path, fooDir.path, barDir.path]));
+  });
+}
+
+Directory sub(Directory parent, String dirName) {
+  return new Directory(path.join(parent.path, dirName));
+}
+
+const packagesFile = """
+# A comment
+foo=file:///dart/packages/foo/
+bar=http://example.com/dart/packages/bar/
+baz=packages/baz/
+""";
+
+void validatePackagesFile(Packages resolver, Uri location) {
+  expect(resolver, isNotNull);
+  expect(resolver.resolve(pkg("foo", "bar/baz")),
+         equals(Uri.parse("file:///dart/packages/foo/bar/baz")));
+  expect(resolver.resolve(pkg("bar", "baz/qux")),
+         equals(Uri.parse("http://example.com/dart/packages/bar/baz/qux")));
+  expect(resolver.resolve(pkg("baz", "qux/foo")),
+         equals(location.resolve("packages/baz/qux/foo")));
+  expect(resolver.packages, unorderedEquals(["foo", "bar", "baz"]));
+}
+
+void validatePackagesDir(Packages resolver, Uri location) {
+  // Expect three packages: foo, bar and baz
+  expect(resolver, isNotNull);
+  expect(resolver.resolve(pkg("foo", "bar/baz")),
+         equals(location.resolve("packages/foo/bar/baz")));
+  expect(resolver.resolve(pkg("bar", "baz/qux")),
+         equals(location.resolve("packages/bar/baz/qux")));
+  expect(resolver.resolve(pkg("baz", "qux/foo")),
+         equals(location.resolve("packages/baz/qux/foo")));
+  if (location.scheme == "file") {
+    expect(resolver.packages, unorderedEquals(["foo", "bar", "baz"]));
+  } else {
+    expect(() => resolver.packages, throws);
+  }
+}
+
+Uri pkg(String packageName, String packagePath) {
+  var path;
+  if (packagePath.startsWith('/')) {
+    path = "$packageName$packagePath";
+  } else {
+    path = "$packageName/$packagePath";
+  }
+  return new Uri(scheme: "package", path: path);
+}
+
+/// Create a directory structure from [description] and run [fileTest].
+///
+/// Description is a map, each key is a file entry. If the value is a map,
+/// it's a sub-dir, otherwise it's a file and the value is the content
+/// as a string.
+void fileTest(String name,
+              Map description,
+              Future fileTest(Uri directory)) {
+  group("file-test", () {
+    Directory tempDir = Directory.systemTemp.createTempSync("file-test");
+    setUp(() {
+      _createFiles(tempDir, description);
+    });
+    tearDown(() {
+      tempDir.deleteSync(recursive: true);
+    });
+    test(name, () => fileTest(tempDir));
+  });
+}
+
+void _createFiles(Directory target, Map description) {
+  description.forEach((name, content) {
+    if (content is Map) {
+      Directory subDir = new Directory(path.join(target.path, name));
+      subDir.createSync();
+      _createFiles(subDir, content);
+    } else {
+      File file = new File(path.join(target.path, name));
+      file.writeAsStringSync(content, flush: true);
+    }
+  });
+}