Support transformers that depend on other transformers.

sdk/lib/_internal/pub/lib/src/barback/load_all_transformers.dart

Index: sdk/lib/_internal/pub/lib/src/barback/load_all_transformers.dart
diff --git a/sdk/lib/_internal/pub/lib/src/barback/load_all_transformers.dart b/sdk/lib/_internal/pub/lib/src/barback/load_all_transformers.dart
new file mode 100644
index 0000000000000000000000000000000000000000..03283889692e7d4ec6f136b9ad6a7cc9d224abb4
--- /dev/null
+++ b/sdk/lib/_internal/pub/lib/src/barback/load_all_transformers.dart
@@ -0,0 +1,223 @@
+// Copyright (c) 2013, 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.load_all_transformers;
+
+import 'dart:async';
+
+import 'package:barback/barback.dart';
+
+import 'load_transformers.dart';
+import 'rewrite_import_transformer.dart';
+import 'server.dart';
+import 'watch_sources.dart';
+import '../utils.dart';
+
+/// Loads all transformers depended on by packages in [graph].
+///
+/// This uses [server] to serve the Dart files from which transformers are
+/// loaded, then adds the transformers to `server.barback`.
+Future loadAllTransformers(BarbackServer server, PackageGraph graph) {
+  // In order to determine in what order we should load transformers, we need to
+  // know which transformers depend on which others. This is different than
+  // normal package dependencies. Let's begin with some terminology:
+  //
+  // * If package A is transformed by package B, we say A has a "transformer
+  //   dependency" on B.
+  // * If A imports B we say A has a "package dependency" on B.
+  // * If A needs B's transformers to be loaded in order to load A's
+  //   transformers, we say A has an "ordering dependency" on B.
+  //
+  // In particular, an ordering dependency is defined as follows:
+  //
+  // * If A has a transformer dependency on B, A also has an ordering dependency
+  //   on B.
+  // * If A has a transitive package dependency on B and B has a transformer
+  //   dependency on C, A has an ordering dependency on C.
+  //
+  // The order that transformers are loaded is determined by each package's
+  // ordering dependencies. We treat the packages as a directed acyclic[1] graph
+  // where each package is a node and the ordering dependencies are the edges,
+  // and start loading[2] nodes with no outgoing edges first. We then work our
+  // way inward until all nodes are loaded.
+  //
+  // [1] TODO(nweiz): support cycles in some cases.
+  //
+  // [2] We use "loading a package" as a shorthand for loading that package's
+  //     transformers.

[Bob Nystrom, 2013/09/06 18:27:29]

I found this hard to grok and tried rewriting it. What do you think of:

In order to determine in what order we should load transformers, we need to
know which transformers depend on which others. This is different than
normal package dependencies. First a bit of terminolgy:

* If package A is transformed by package B, we say "B transforms A".
* If code in A imports code in B or has a regular package dependency on it we
  say "A imports B".
* If B needs A's transformers to be loaded in order to load B's
  transformers, we say "A comes before B".

In particular, "comes before" is defined as follows:

* If A transforms B, A comes before B.
* If A imports B (directly or transitively) and C transforms B, C comes before
  A.

The order that transformers are loaded is determined by each package's
"comes before" relationships. We treat the packages as a directed acyclic[1]
graph where each package is a node and the "comes before" relations are the
edges. (Another way to say this is the packages form a partially ordered set.)
Then we do a topological sort on the graph.

We start loading[2] nodes with no where no other node comes before it. We then
work our way through the graph until all nodes are loaded.

[1] TODO(nweiz): support cycles in some cases.

[2] We use "loading a package" as a shorthand for loading that package's
    transformers.

[nweiz, 2013/09/09 20:43:38]

I'm worried that these verb-based descriptions will make it more difficult to
clearly name variables and functions that deal with these dependencies. It means
there's no name for "everything that transforms a package" (or is imported by a
package, or comes before a package), which is a concept this code deals with
constantly.

I sympathize with the terminology being complex, but I think your suggestion
just shuffles around the complexity without reducing it overall. Verbs have the
advantage that they're easier to grasp immediately, but they're difficult to use
elsewhere in the code. Once you understand the nouns, it makes all the future
code and documentation much more concise and easy to understand. I think for
this code it makes sense to optimize for that.
Done, although modified to clarify that the code itself doesn't actually do a
topological sort.

[Bob Nystrom, 2013/09/09 23:34:57]

I think I tried to catch most of the comments here and suggest wording that
worked with the verbs. I don't recall having any problems.

I definitely see the value of using nouns here. The problem is its all the same
noun. It's all dependency dependency dependency. That's already a long, loaded,
confusing noun, so reusing it in additional contexts with some adjectives just
makes it harder.

It's also problematic because the nouns don't often clearly indicate direction.
If A has an "ordering dependency" on B, does that mean it must be loaded before
or after? If A has a "transformer dependency" on B, is A a transformer that is
applied to B or vice versa?

I really did have to manually rewrite this code to change the terminology before
I could even understand what it did.

How about:

"A transforms B" -> A is a "transformer" of B, B is a "transformee" of A.
"A imports B" -> A is an "importer" of B, B is an "importee" of A.
"A comes before B" -> A is an "earlier package" than B. B is a "later package"
than A.

?

[nweiz, 2013/09/10 00:47:44]

All of your rewrites were more verbose than the original wording. I also found
them harder to understand, because the lack of clearly identifiable terms failed
to call out the core concepts that were being discussed. The phrase "transformer
dependency" refers only to the notion that's been precisely defined above; the
phrase "transforms" doesn't.
But they are all dependencies. That word provides important context to
understanding the nature of these relations between packages (see below). I
don't understand the difficulty in thinking of "transformer dependency" as a
single term without confusing it with the more general notion of a dependency.
This is clearly indicated by the use of the word "dependency". If A has a
dependency on B, that means A needs B to function. This is consistently true for
all three types of dependency referred to here.
I believe this, but I suspect that it's possible that the act of rewriting the
code contributed more to your understanding than the form to which you rewrote
it. This code performs complicated analysis and transformation on relations that
have subtle distinctions between them; there's going to be a baseline difficulty
of understanding regardless of the terminology used. Given that, I want the
terminology to be maximally precise.
I really don't like the idea of overloading the word "transformer" here.
"Transformer" is a word that already has a well-defined meaning in this code, a
meaning that's completely separate from what I'm referring to as a "transformer
dependency".

"Importer"/"importee" is better, since it doesn't have an existing meaning, but
the point of package dependencies are several steps away from the fact that
they're imported by the package in question, so that makes the name a little
misleading. It's even possible (although unlikely) for a package dependency not
to be imported anywhere in the dependent package.

"Earlier package" and "later package" are similar to my terminology in that
they're an adjective modifying an already-in-use noun. Obviously I don't have a
problem with this in general, but I'm not sure what using "package" rather than
"dependency" buys us. These names also don't provide a clear name for the graph
of ordering dependencies.

+
+  // Add a rewrite transformer for each package, so that we can resolve
+  // "package:" imports while loading transformers.
+  var rewrite = new RewriteImportTransformer();
+  for (var package in graph.packages.values) {
+    server.barback.updateTransformers(package.name, [[rewrite]]);
+  }
+
+  var orderingDeps = _computeOrderingDeps(graph);
+  var packageTransformers = _computePackageTransformers(graph);
+
+  var loader = new _TransformerLoader(server, graph);
+
+  // The packages that have no incoming ordering dependencies. These packages
+  // will be loaded last, since all of their outgoing ordering dependencies need
+  // to be loaded before they're loaded. However, they'll be traversed by
+  // [loadPackage] first.

[Bob Nystrom, 2013/09/06 18:27:29]

This is confusing to me. "incoming" and "outgoing" aren't very clear. This is
the set of packages that don't need anything to be loaded before them, right?
Clarify that.

[nweiz, 2013/09/09 20:43:38]

Done.

+  var rootPackages = graph.packages.keys.toSet()
+      .difference(unionAll(orderingDeps.values));

[Bob Nystrom, 2013/09/06 18:27:29]

If there is a cyclic dependency, this may be an empty set. Add a TODO for this?

(You can also have cycles where this *isn't* an empty set too, I believe.)

[nweiz, 2013/09/09 20:43:38]

There's a TODO in _computeOrderingDeps to detect and fail on cycles.

+
+  // The Futures for packages that have been loaded or are being actively loaded
+  // by [loadPackage]. Once one of these Futures is complete, the transformers
+  // for that package will all be available from [loader].
+  var loadingPackages = new Map<String, Future>();
+
+  // A helper function that loads all the transformers that [package] uses, then
+  // all the transformers that [package] defines.
+  Future loadPackage(String package) {
+    if (loadingPackages.containsKey(package)) return loadingPackages[package];
+
+    // First, load each package upon which [package] has an ordering dependency.

[Bob Nystrom, 2013/09/06 18:27:29]

"load each package that need to come before [package]".

[nweiz, 2013/09/09 20:43:38]

See above.

+    var future = Future.wait(orderingDeps[package].map(loadPackage)).then((_) {
+      // Go through the transformers used by [package] phase-by-phase. If any
+      // phase uses a transformer defined in [package] itself, that transform
+      // should be loaded after running all previous phases.
+      var transformers = [[rewrite]];
+      return Future.forEach(graph.packages[package].pubspec.transformers,
+          (phase) {
+        return Future.wait(phase.where((id) => id.package == package)
+            .map(loader.load)).then((_) {
+          transformers.add(unionAll(phase.map(
+              (id) => loader.transformersFor(id))));
+          server.barback.updateTransformers(package, transformers);
+        });

[Bob Nystrom, 2013/09/06 18:27:29]

I don't mind not *supporting* cycles yet, but it would be good to at least
detect them. Otherwise this will crash, right?

[nweiz, 2013/09/09 20:43:38]

This will also be covered by the TODO in _computeOrderingDeps.

+      }).then((_) {
+        // Now that we've applied all the transformers used by [package] via
+        // [Barback.updateTransformers], we load any transformers defined in
+        // [package] but used elsewhere.
+        return Future.wait(packageTransformers[package].map(loader.load));
+      });
+    });
+    loadingPackages[package] = future;
+    return future;
+  }
+
+  return Future.wait(rootPackages.map(loadPackage)).then((_) {
+    /// Reset the transformers for each package to get rid of [rewrite], which
+    /// is no longer needed.
+    for (var package in graph.packages.values) {
+      var phases = package.pubspec.transformers.map((phase) {
+        return unionAll(phase.map((id) => loader.transformersFor(id)));
+      });
+      server.barback.updateTransformers(package.name, phases);
+    }
+  });
+}
+
+/// Computes and returns the graph of ordering dependencies for [graph].
+///
+/// This graph is in the form of a map whose keys are packages and whose values
+/// are those packages' ordering dependencies.

[Bob Nystrom, 2013/09/06 18:27:29]

How about:

"Returns a map where each key is a package and the value is the set of packages
that must be loaded before it. Packages that don't require any other package to
be loaded before it will not appear in the map."

Also, _computeOrderingDeps -> _computeOrderingRelations?

[nweiz, 2013/09/09 20:43:38]

See above.

+Map<String, Set<String>> _computeOrderingDeps(PackageGraph graph) {

[Bob Nystrom, 2013/09/06 18:27:29]

Using "deps" here for dependencies, transformers, and ordering relations is
confusing. How about:

orderingDeps -> orderings
deps -> ordering
packageDep -> dep

[nweiz, 2013/09/09 20:43:38]

See above. Also, using "ordering" here to refer to an unordered set that doesn't
represent an ordering seems very confusing.

+  var orderingDeps = new Map<String, Set<String>>();
+  for (var package in graph.packages.values) {
+    var deps = _transformerDeps(graph, package.name);

[Bob Nystrom, 2013/09/06 18:27:29]

// The transformers applied to this package must be loaded first.

[nweiz, 2013/09/09 20:43:38]

Done, using my terminology.

+    deps.remove(package.name);
+    for (var packageDep in _transitivePackageDeps(graph, package.name)) {

[Bob Nystrom, 2013/09/06 18:27:29]

// And everything those transformers import must therefore be loaded first too.

[nweiz, 2013/09/09 20:43:38]

That isn't quite what this code is doing, but I've added a comment.

+      deps.addAll(_transformerDeps(graph, packageDep));
+    }
+    orderingDeps[package.name] = deps;
+  }
+  // TODO(nweiz): check for cycles in orderingDeps.
+  return orderingDeps;
+}
+
+/// Returns the transitive set of package dependencies for [package].
+Set<String> _transitivePackageDeps(PackageGraph graph, String package) {

[Bob Nystrom, 2013/09/06 18:27:29]

Move this into PackageGraph?

[nweiz, 2013/09/09 20:43:38]

Done.

+  var seen = new Set<String>();
+  traverse(String package) {
+    if (seen.contains(package)) return;
+    seen.add(package);
+    for (var dep in graph.packages[package].dependencies) {
+      traverse(dep.name);
+    }
+  }
+
+  traverse(package);
+  seen.remove(package);
+  return seen;
+}
+
+/// Returns the set of transformer dependencies for [package].

[Bob Nystrom, 2013/09/06 18:27:29]

How about: "Returns the set of packages whose transformers are applied to
[package]."

?

[nweiz, 2013/09/09 20:43:38]

See above.

+Set<String> _transformerDeps(PackageGraph graph, String package) =>
+  unionAll(graph.packages[package].pubspec.transformers)
+      .map((id) => id.package).toSet();
+
+/// Returns a map from each package in [graph]'s name to the asset ids of all

[Bob Nystrom, 2013/09/06 18:27:29]

"package in [graph]'s name" -> "package name in graph"

[nweiz, 2013/09/09 20:43:38]

Done.

+/// transformers exposed by that package and used by other packages.
+Map<String, Set<AssetId>> _computePackageTransformers(PackageGraph graph) {
+  var packageTransformers = listToMap(graph.packages.values,
+      (package) => package.name, (_) => new Set<AssetId>());
+  for (var package in graph.packages.values) {
+    for (var id in unionAll(package.pubspec.transformers)) {

[Bob Nystrom, 2013/09/06 18:27:29]

Don't bother unioning here. Just do another nested loop and add them all. Since
you're ultimately adding to a Set, dupes will be filtered out anyway.

[nweiz, 2013/09/09 20:43:38]

Done.

+      packageTransformers[id.package].add(id);
+    }
+  }
+  return packageTransformers;
+}
+
+/// A class that loads transformers defined in specific files.
+class _TransformerLoader {
+  final BarbackServer _server;
+
+  /// The loaded transformers for each asset id.

[Bob Nystrom, 2013/09/06 18:27:29]

"for" is a bit ambiguous. Took me a while to realize this was the transformers
defined in the Dart library at ID. Clarify?

[nweiz, 2013/09/09 20:43:38]

Done.

+  final _transformers = new Map<AssetId, Set<Transformer>>();
+
+  /// The packages that use each transformer id.
+  ///
+  /// Used for error reporting.
+  final _transformerUsers = new Map<AssetId, List<String>>();
+
+  _TransformerLoader(this._server, PackageGraph graph) {
+    for (var package in graph.packages.values) {
+      for (var id in unionAll(package.pubspec.transformers)) {
+        _transformerUsers.putIfAbsent(id, () => <String>[]).add(package.name);
+      }
+    }
+
+    // Ensure that the transformer users are printed in a deterministic order if
+    // an error occurs.
+    for (var list in _transformerUsers.values) {
+      list.sort();
+    }
+  }
+
+  /// Loads the transformer(s) defined in the asset [id].
+  ///
+  /// Once the returned future completes, these transformers can be retrieved
+  /// using [transformersFor]. If [id] doesn't define any transformers, this
+  /// will complete to an error.
+  Future load(AssetId id) {
+    if (_transformers.containsKey(id)) return new Future.value();
+
+    return loadTransformers(_server, id).then((transformers) {
+      if (!transformers.isEmpty) {
+        _transformers[id] = transformers;
+        return;
+      }
+
+      var path = id.path.replaceFirst('lib/', '');

[Bob Nystrom, 2013/09/06 18:27:29]

Use pathos here. This would do the wrong thing on
"joke/glib/oops/lib/transformer.dart".

Maybe we should add replace()-like methods directly in pathos?

[nweiz, 2013/09/09 20:43:38]

There should be no way that [id.path] doesn't begin with "lib/". Given that, I
think it's cleaner to just use string methods here. I've added an assert to that
effect, though.

+      throw new ApplicationException(
+          "No transformers were defined in package:${id.package}/$path,\n"
+          "required by ${_transformerUsers[id].join(', ')}.");
+    });
+  }
+
+  /// Returns the set of transformers for [id].
+  ///
+  /// It's an error to call this before [load] is called with [id] and the
+  /// future it returns has completed.
+  Set<Transformers> transformersFor(AssetId id) {
+    assert(_transformers.containsKey(id));
+    return _transformers[id];
+  }
+}