test.py: First step towards support of caching dart2js compilations across runtimes

tools/testing/dart/test_runner.dart

Index: tools/testing/dart/test_runner.dart
diff --git a/tools/testing/dart/test_runner.dart b/tools/testing/dart/test_runner.dart
index e4a51d90f8616b061faf466b27a0f21dfeaec46b..4c226300a1b1467998b7f1837fb44ecb26b1c963 100644
--- a/tools/testing/dart/test_runner.dart
+++ b/tools/testing/dart/test_runner.dart
@@ -17,6 +17,8 @@ import "dart:collection" show Queue;
 // CommandOutput.exitCode in subclasses of CommandOutput.
 import "dart:io" as io;
 import "dart:isolate";
+import "dart:math" as math;
+import 'dependency_graph.dart' as dgraph;
 import "browser_controller.dart";
 import "http_server.dart" as http_server;
 import "status_file_parser.dart";
@@ -25,10 +27,8 @@ import "test_suite.dart";
 import "utils.dart";
 import 'record_and_replay.dart';
 
-const int NO_TIMEOUT = 0;
-const int SLOW_TIMEOUT_MULTIPLIER = 4;
-
 const int CRASHING_BROWSER_EXITCODE = -10;
+const int SLOW_TIMEOUT_MULTIPLIER = 4;
 
 typedef void TestCaseEvent(TestCase testCase);
 typedef void ExitCodeEvent(int exitCode);
@@ -41,76 +41,29 @@ const List<String> EXCLUDED_ENVIRONMENT_VARIABLES =
            'HTTP_PROXY', 'HTTPS_PROXY', 'NO_PROXY'];
 
 
-/**
- * [areByteArraysEqual] compares a range of bytes from [buffer1] with a
- * range of bytes from [buffer2].
- *
- * Returns [true] if the [count] bytes in [buffer1] (starting at
- * [offset1]) match the [count] bytes in [buffer2] (starting at
- * [offset2]).
- * Otherwise [false] is returned.
- */
-bool areByteArraysEqual(List<int> buffer1, int offset1,
-                        List<int> buffer2, int offset2,
-                        int count) {
-  if ((offset1 + count) > buffer1.length ||
-      (offset2 + count) > buffer2.length) {
-    return false;
-  }
-
-  for (var i = 0; i < count; i++) {
-    if (buffer1[offset1 + i] != buffer2[offset2 + i]) {
-      return false;
-    }
-  }
-  return true;
-}
-
-/**
- * [findBytes] searches for [pattern] in [data] beginning at [startPos].
- *
- * Returns [true] if [pattern] was found in [data].
- * Otherwise [false] is returned.
- */
-int findBytes(List<int> data, List<int> pattern, [int startPos=0]) {
-  // TODO(kustermann): Use one of the fast string-matching algorithms!
-  for (int i=startPos; i < (data.length-pattern.length); i++) {
-    bool found = true;
-    for (int j=0; j<pattern.length; j++) {
-      if (data[i+j] != pattern[j]) {
-        found = false;
-      }
-    }
-    if (found) {
-      return i;
-    }
-  }
-  return -1;
-}
-
-
 /** A command executed as a step in a test case. */
 class Command {
-  static int nextHashCode = 0;
-  final int hashCode = nextHashCode++;
-  operator ==(other) => super == (other);
-
   /** Path to the executable of this command. */
   String executable;
 
+  /** The actual command line that will be executed. */
+  String commandLine;
+
+  /** A descriptive name for this command. */
+  String displayName;
+
   /** Command line arguments to the executable. */
   List<String> arguments;
 
   /** Environment for the command */
   Map<String,String> environment;
 
-  /** The actual command line that will be executed. */
-  String commandLine;
+  /** Number of times this command could be retried */

[ricow1, 2013/07/30 09:30:11]

could -> should ?

[kustermann, 2013/07/31 15:53:54]

should?
No. Normally we don't want to retry anything. But we allow retrying this command
numRetries times if it failed.

+  int get numRetries => 0;
 
-  /** A descriptive name for this command. */
-  String displayName;
+  int _cachedHashCode;

[ricow1, 2013/07/30 09:30:11]

add comment what this is

[kustermann, 2013/07/31 15:53:54]

It's a cached hashcode! :-)

Added comment.

 
-  Command(this.displayName, this.executable,
+  Command._(this.displayName, this.executable,
           this.arguments, [this.environment = null]) {
     if (io.Platform.operatingSystem == 'windows') {
       // Windows can't handle the first command if it is a .bat file or the like
@@ -124,6 +77,61 @@ class Command {
     commandLine = quotedArguments.join(' ');
   }
 
+  int get hashCode {
+    if (_cachedHashCode == null) {
+      var builder = new HashCodeBuilder();
+      _buildHashCode(builder);
+      _cachedHashCode = builder.value;
+    }
+    return _cachedHashCode;
+  }
+
+  operator ==(other) {
+    if (other is Command) {
+      return _equal(other as Command);
+    }
+    return false;
+  }
+
+  void _buildHashCode(HashCodeBuilder builder) {
+    builder.add(executable);
+    builder.add(commandLine);
+    builder.add(displayName); // FIXME(kustermann): Yes or No?
+    for (var object in arguments) builder.add(object);
+    if (environment != null) {
+      for (var key in environment.keys) builder.add(environment[key]);
+    }
+  }
+
+  bool _equal(Command other) {
+    if (executable == other.executable &&

[ricow1, 2013/07/30 09:30:11]

you could do a fast return here if other.hashCode != hashCode, even better start
with
if (hashCode != other.hashCode ||
    executable != other.executable ||
    commandLine != other.commandLine ||
    displayName != other.displayName ||
    arguments.length != other.arguments.length) {
  return false;
}

[kustermann, 2013/07/31 15:53:54]

Done.

+        commandLine == other.commandLine &&
+        displayName == other.displayName && // FIXME(kustermann): Yes or No?
+        arguments.length == other.arguments.length) {
+      if ((environment == null && other.environment != null) ||

[ricow1, 2013/07/30 09:30:11]

if ((environment != other.environment) &&
     (environment == null || other.environment == null)

[kustermann, 2013/07/31 15:53:54]

Done.

+          (environment != null && other.environment == null)) {
+        return false;
+      }
+      if (environment != null &&
+          environment.length != other.environment.length) {

[ricow1, 2013/07/30 09:30:11]

this can go bad, other.environment may be null 

[kustermann, 2013/07/31 15:53:54]

No. The check above makes sure that either both environments are null (in which
case the shortcut operator will not evaluate the ' && XXX') or both are '!=
null'!

+        return false;
+      }
+      for (var i=0; i<arguments.length; i++) {

[ricow1, 2013/07/30 09:30:11]

space around = and <

[ricow1, 2013/07/30 09:30:11]

why don't you move this up above line 111, then you can eliminate some checks
and simplify environment chekcing to:
if (other.environment == null && environment == null) return true;
if (other.environment == null || environment == null) return false;
if (other.environment.length != environment.lenght) return false;
for (var key in environment.keys) {
  if (!other.environment.containsKey(key) ||
      environment[key] != other.environment[key]) {
    return false;
  }
}
return true;

[kustermann, 2013/07/31 15:53:54]

Done.

[kustermann, 2013/07/31 15:53:54]

I moved the expensive operations down (iterating through arguments/environment)
and the fast operations up, so we can fail as fast as possible (not getting to
the expensive operations) if the commands are not equal.

I think it doesn't make a big difference though.

+        if (arguments[i] != other.arguments[i]) return false;
+      }
+      if (environment != null) {
+        for (var key in environment.keys) {
+          if (!other.environment.containsKey(key) ||

[ricow1, 2013/07/30 09:30:11]

again, other.environment may be null

[kustermann, 2013/07/31 15:53:54]

Again, no. It can't. If one environment is null and the other is not, we return
false above. So we are guaranteed that either of these two cases hold:
  env != null and other.env != null
  env == null and other.env == null

The check on line 122 rules out option 2.

+              environment[key] != other.environment[key]) {
+            return false;
+          }
+        }
+      }
+      return true;
+    }
+    return false;
+  }
+
   String toString() => commandLine;
 
   Future<bool> get outputIsUpToDate => new Future.value(false);
@@ -136,13 +144,17 @@ class CompilationCommand extends Command {
   bool _neverSkipCompilation;
   List<Uri> _bootstrapDependencies;
 
-  CompilationCommand(String displayName,
+  CompilationCommand._(String displayName,
                      this._outputFile,
                      this._neverSkipCompilation,
-                     this._bootstrapDependencies,
+                     List<String> bootstrapDependencies,
                      String executable,
                      List<String> arguments)
-      : super(displayName, executable, arguments);
+      : super._(displayName, executable, arguments) {
+    // We sort here, so we can do a fast hashCode/operator==
+    _bootstrapDependencies = new List.from(bootstrapDependencies);
+    _bootstrapDependencies.sort();
+  }
 
   Future<bool> get outputIsUpToDate {
     if (_neverSkipCompilation) return new Future.value(false);
@@ -184,6 +196,34 @@ class CompilationCommand extends Command {
       return false;
     });
   }
+
+  void _buildHashCode(HashCodeBuilder builder) {
+    super._buildHashCode(builder);
+    builder.add(_outputFile);
+    builder.add(_neverSkipCompilation);
+    for (var uri in _bootstrapDependencies) builder.add(uri);
+  }
+
+  bool _equal(Command other) {
+    if (other is CompilationCommand &&
+        super._equal(other) &&
+        _outputFile == other._outputFile &&
+        _neverSkipCompilation == other._neverSkipCompilation &&
+        _bootstrapDependencies.length == other._bootstrapDependencies.length) {
+      for (var i=0; i<_bootstrapDependencies.length; i++) {

[ricow1, 2013/07/30 09:30:11]

space around = and <

[kustermann, 2013/07/31 15:53:54]

Done.

+        if (_bootstrapDependencies[i] != other._bootstrapDependencies[i]) {
+          return false;
+        }
+      }
+      /*

[ricow1, 2013/07/30 09:30:11]

commented out code

[kustermann, 2013/07/31 15:53:54]

Done.

+      print("TRUE");
+      print("  SELF = $this");
+      print("  OTHER = $other");
+      print("");*/
+      return true;
+    }
+    return false;
+  }
 }
 
 class ContentShellCommand extends Command {
@@ -195,12 +235,12 @@ class ContentShellCommand extends Command {
    */
   io.Path expectedOutputPath;
 
-  ContentShellCommand(String executable,
-                      String htmlFile,
-                      List<String> options,
-                      List<String> dartFlags,
-                      io.Path this.expectedOutputPath)
-      : super("content_shell",
+  ContentShellCommand._(String executable,
+                       String htmlFile,

[ricow1, 2013/07/30 09:30:11]

indentation

[kustermann, 2013/07/31 15:53:54]

Done.

+                       List<String> options,
+                       List<String> dartFlags,
+                       io.Path this.expectedOutputPath)
+      : super._("content_shell",
               executable,

[ricow1, 2013/07/30 09:30:11]

indentation

[kustermann, 2013/07/31 15:53:54]

Done.

               _getArguments(options, htmlFile),
               _getEnvironment(dartFlags));
@@ -228,8 +268,169 @@ class ContentShellCommand extends Command {
   io.Path get expectedOutputFile => expectedOutputPath;
   bool get isPixelTest => (expectedOutputFile != null &&
                            expectedOutputFile.filename.endsWith(".png"));
+
+  void _buildHashCode(HashCodeBuilder builder) {
+    super._buildHashCode(builder);
+    builder.add(expectedOutputPath.toString());
+  }
+
+  bool _equal(Command other) {
+    return
+        other is ContentShellCommand &&
+        super._equal(other) &&
+        expectedOutputPath.toString() == other.expectedOutputPath.toString();
+  }
+
+  // FIXME(kustermann): Remove this once we're stable
+  int get numRetries => 2;
+}
+
+class BrowserTestCommand extends Command {
+  final String browser;
+  final String url;
+
+  BrowserTestCommand._(String _browser,
+                       this.url,
+                       String executable,
+                       List<String> arguments)
+      : super._(_browser, executable, arguments), browser = _browser;
+
+  void _buildHashCode(HashCodeBuilder builder) {
+    super._buildHashCode(builder);
+    builder.add(browser);
+    builder.add(url);
+  }
+
+  bool _equal(Command other) {
+    return
+        other is BrowserTestCommand &&
+        super._equal(other) &&
+        browser == other.browser &&
+        url == other.url;
+  }
+
+  // FIXME(kustermann): Remove this once we're stable
+  int get numRetries => 2;
 }
 
+class SeleniumTestCommand extends Command {
+  final String browser;
+  final String url;
+
+  SeleniumTestCommand._(String _browser,
+                       this.url,
+                       String executable,
+                       List<String> arguments)
+      : super._(_browser, executable, arguments), browser = _browser;
+
+  void _buildHashCode(HashCodeBuilder builder) {
+    super._buildHashCode(builder);
+    builder.add(browser);
+    builder.add(url);
+  }
+
+  bool _equal(Command other) {
+    return
+        other is SeleniumTestCommand &&
+        super._equal(other) &&
+        browser == other.browser &&
+        url == other.url;
+  }
+
+  // FIXME(kustermann): Remove this once we're stable
+  int get numRetries => 2;
+}
+
+class AnalysisCommand extends Command {
+  final String flavour;
+
+  AnalysisCommand._(
+      this.flavour, String displayName, String executable, List<String> arguments)

[ricow1, 2013/07/30 09:30:11]

long line

[kustermann, 2013/07/31 15:53:54]

Done.

+      : super._(displayName, executable, arguments);
+
+  void _buildHashCode(HashCodeBuilder builder) {
+    super._buildHashCode(builder);
+    builder.add(flavour);
+  }
+
+  bool _equal(Command other) {
+    return
+        other is AnalysisCommand &&
+        super._equal(other) &&
+        flavour == other.flavour;
+  }
+}
+
+class CommandBuilder {
+  static final instance = new CommandBuilder._();
+
+  final _cachedCommands = new Map<Command, Command>();

[ricow1, 2013/07/30 09:30:11]

you could just use a HashSet here

[kustermann, 2013/07/31 15:53:54]

By doing it this way, I do not only get equal commands but identical commands,
see "_getUniqueCommand()".

+
+  CommandBuilder._();
+
+  ContentShellCommand getContentShellCommand(String executable,
+                                             String htmlFile,
+                                             List<String> options,
+                                             List<String> dartFlags,
+                                             io.Path expectedOutputPath) {
+    ContentShellCommand command = new ContentShellCommand._(
+        executable, htmlFile, options, dartFlags, expectedOutputPath);
+    return _getUniqueCommand(command);
+  }
+
+  BrowserTestCommand getBrowserTestCommand(String browser,
+                                           String url,
+                                           String executable,
+                                           List<String> arguments) {
+    var command = new BrowserTestCommand._(
+        browser, url, executable, arguments);
+    return _getUniqueCommand(command);
+  }
+
+  SeleniumTestCommand getSeleniumTestCommand(String browser,
+                                             String url,
+                                             String executable,
+                                             List<String> arguments) {
+    var command = new SeleniumTestCommand._(
+        browser, url, executable, arguments);
+    return _getUniqueCommand(command);
+  }
+
+  CompilationCommand getCompilationCommand(String displayName,
+                                           outputFile,
+                                           neverSkipCompilation,
+                                           List<String> bootstrapDependencies,
+                                           String executable,
+                                           List<String> arguments) {
+    var command =
+        new CompilationCommand._(displayName, outputFile, neverSkipCompilation,
+                                 bootstrapDependencies, executable, arguments);
+    return _getUniqueCommand(command);
+  }
+
+  AnalysisCommand getAnalysisCommand(
+      String displayName, executable, arguments,
+      {String flavour: 'dartanalyzer'}) {
+    var command = new AnalysisCommand._(flavour, displayName, executable, arguments);

[ricow1, 2013/07/30 09:30:11]

Long line

[kustermann, 2013/07/31 15:53:54]

Done.

+    return _getUniqueCommand(command);
+  }
+
+  Command getCommand(
+      String displayName, executable, arguments, [environment = null]) {
+    var command =
+        new Command._(displayName, executable, arguments, environment);
+    return _getUniqueCommand(command);
+  }
+
+  Command _getUniqueCommand(Command command) {

[ricow1, 2013/07/30 09:30:11]

please add comment stating how this works

[kustermann, 2013/07/31 15:53:54]

Done.

+    var cachedCommand = _cachedCommands[command];
+    if (cachedCommand != null) {
+      return cachedCommand;
+    }
+    _cachedCommands[command] = command;
+    return command;
+  }
+}
 
 /**
  * TestCase contains all the information needed to run a test and evaluate
@@ -248,7 +449,7 @@ class ContentShellCommand extends Command {
  * The TestCase has a callback function, [completedHandler], that is run when
  * the test is completed.
  */
-class TestCase {
+class TestCase extends UniqueObject {
   /**
    * A list of commands to execute. Most test cases have a single command.
    * Dart2js tests have two commands, one to compile the source and another
@@ -262,69 +463,26 @@ class TestCase {
   String displayName;
   bool isNegative;
   Set<String> expectedOutcomes;
-  TestCaseEvent completedHandler;
   TestInformation info;
 
   TestCase(this.displayName,
            this.commands,
            this.configuration,
-           this.completedHandler,
            this.expectedOutcomes,
            {this.isNegative: false,
             this.info: null}) {
     if (!isNegative) {
       this.isNegative = displayName.contains("negative_test");
     }
+  }
 
-    // Special command handling. If a special command is specified
-    // we have to completely rewrite the command that we are using.
-    // We generate a new command-line that is the special command where we
-    // replace '@' with the original command executable, and generate
-    // a command formed like the following
-    // Let PREFIX be what is before the @.
-    // Let SUFFIX be what is after the @.
-    // Let EXECUTABLE be the existing executable of the command.
-    // Let ARGUMENTS be the existing arguments to the existing executable.
-    // The new command will be:
-    // PREFIX EXECUTABLE SUFFIX ARGUMENTS
-    var specialCommand = configuration['special-command'];
-    if (!specialCommand.isEmpty) {
-      if (!specialCommand.contains('@')) {
-        throw new FormatException("special-command must contain a '@' char");
-      }
-      var specialCommandSplit = specialCommand.split('@');
-      var prefix = specialCommandSplit[0].trim();
-      var suffix = specialCommandSplit[1].trim();
-      List<Command> newCommands = [];
-      for (Command c in commands) {
-        // If we don't have a new prefix we will use the existing executable.
-        var newExecutablePath = c.executable;;
-        var newArguments = [];
-
-        if (prefix.length > 0) {
-          var prefixSplit = prefix.split(' ');
-          newExecutablePath = prefixSplit[0];
-          for (int i = 1; i < prefixSplit.length; i++) {
-            var current = prefixSplit[i];
-            if (!current.isEmpty) newArguments.add(current);
-          }
-          newArguments.add(c.executable);
-        }
-
-        // Add any suffixes to the arguments of the original executable.
-        var suffixSplit = suffix.split(' ');
-        suffixSplit.forEach((e) {
-          if (!e.isEmpty) newArguments.add(e);
-        });
-
-        newArguments.addAll(c.arguments);
-        final newCommand = new Command(newExecutablePath, newArguments);
-        newCommands.add(newCommand);
-      }
-      commands = newCommands;
-    }
+  bool get unexpectedOutput {
+    //print("result = ${lastCommandOutput.result(this)}");
+    return !expectedOutcomes.contains(lastCommandOutput.result(this));
   }
 
+  String get result => lastCommandOutput.result(this);
+
   CommandOutput get lastCommandOutput {
     if (commandOutputs.length == 0) {
       throw new Exception("CommandOutputs is empty, maybe no command was run? ("
@@ -351,15 +509,10 @@ class TestCase {
     return "$compiler-$runtime$checked ${mode}_$arch";
   }
 
-  List<String> get batchRunnerArguments => ['-batch'];
   List<String> get batchTestArguments => commands.last.arguments;
 
   bool get usesWebDriver => TestUtils.usesWebDriver(configuration['runtime']);
 
-  bool get usesBrowserController => configuration['use_browser_controller'];
-
-  void completed() { completedHandler(this); }
-
   bool get isFlaky {
       if (expectedOutcomes.contains(SKIP)) {
         return false;
@@ -370,6 +523,16 @@ class TestCase {
            ..remove(SLOW);
       return flags.contains(PASS) && flags.length > 1;
   }
+
+  bool get isFinished {
+    /*

[ricow1, 2013/07/30 09:30:11]

commented out code

[kustermann, 2013/07/31 15:53:54]

Done.

+    return lastCommandOutput.didFail(this) ||
+           lastCommandOutput.hasCrashed ||
+           commands.length == commandOutputs.length;
+    */
+    return !lastCommandOutput.successfull ||
+           commands.length == commandOutputs.length;
+  }
 }
 
 
@@ -379,61 +542,17 @@ class TestCase {
  * If the compilation command fails, then the rest of the test is not run.
  */
 class BrowserTestCase extends TestCase {
-  /**
-   * Indicates the number of potential retries remaining, to compensate for
-   * flaky browser tests.
-   */
-  int numRetries;
-
-  /**
-   * True if this test is dependent on another test completing before it can
-   * star (for example, we might need to depend on some other test completing
-   * first).
-   */
-  bool waitingForOtherTest;
-
-  /**
-   * The set of test cases that wish to be notified when this test has
-   * completed.
-   */
-  List<BrowserTestCase> observers;
-
-  BrowserTestCase(displayName, commands, configuration, completedHandler,
-                  expectedOutcomes, info, isNegative, this._testingUrl,
-                  [this.waitingForOtherTest = false])
-    : super(displayName, commands, configuration, completedHandler,
-        expectedOutcomes, isNegative: isNegative, info: info) {
-    numRetries = 2; // Allow two retries to compensate for flaky browser tests.
-    observers = [];
-  }
 
-  List<String> get _lastArguments => commands.last.arguments;
-
-  List<String> get batchRunnerArguments => [_lastArguments[0], '--batch'];
-
-  List<String> get batchTestArguments => _lastArguments.sublist(1);
+  BrowserTestCase(displayName, commands, configuration,
+                  expectedOutcomes, info, isNegative, this._testingUrl)
+    : super(displayName, commands, configuration,
+        expectedOutcomes, isNegative: isNegative, info: info);

[ricow1, 2013/07/30 09:30:11]

indentation

[kustermann, 2013/07/31 15:53:54]

Done.

 
   String _testingUrl;
 
-  /** Add a test case to listen for when this current test has completed. */
-  void addObserver(BrowserTestCase testCase) {
-    observers.add(testCase);
-  }
-
-  /**
-   * Notify all of the test cases that are dependent on this one that they can
-   * proceed.
-   */
-  void notifyObservers() {
-    for (BrowserTestCase testCase in observers) {
-      testCase.waitingForOtherTest = false;
-    }
-  }
-
   String get testingUrl => _testingUrl;
 }
 
-
 /**
  * CommandOutput records the output of a completed command: the process's exit
  * code, the standard output and standard error, whether the process timed out,
@@ -441,43 +560,21 @@ class BrowserTestCase extends TestCase {
  * [TestCase] this is the output of.
  */
 abstract class CommandOutput {
-  factory CommandOutput.fromCase(TestCase testCase,
-                                 Command command,
-                                 int exitCode,
-                                 bool incomplete,
-                                 bool timedOut,
-                                 List<int> stdout,
-                                 List<int> stderr,
-                                 Duration time,
-                                 bool compilationSkipped) {
-    return new CommandOutputImpl.fromCase(testCase,
-                                          command,
-                                          exitCode,
-                                          incomplete,
-                                          timedOut,
-                                          stdout,
-                                          stderr,
-                                          time,
-                                          compilationSkipped);
-  }
-
   Command get command;
 
-  TestCase testCase;
-
-  bool get incomplete;
-
-  String get result;
-
-  bool get unexpectedOutput;
+  String result(TestCase testCase);
 
   bool get hasCrashed;
 
   bool get hasTimedOut;
 
-  bool get didFail;
+  bool didFail(testcase);
+
+  bool hasFailed(TestCase testCase);
 
-  bool requestRetry;
+  bool get canRunDependendCommands;
+
+  bool get successfull; // otherwise we might to retry running
 
   Duration get time;
 
@@ -492,16 +589,11 @@ abstract class CommandOutput {
   bool get compilationSkipped;
 }
 
-class CommandOutputImpl implements CommandOutput {
+class CommandOutputImpl extends UniqueObject implements CommandOutput {
   Command command;
-  TestCase testCase;
   int exitCode;
 
-  /// Records if all commands were run, true if they weren't.
-  final bool incomplete;
-
   bool timedOut;
-  bool failed = false;
   List<int> stdout;
   List<int> stderr;
   Duration time;
@@ -514,80 +606,19 @@ class CommandOutputImpl implements CommandOutput {
    */
   bool alreadyPrintedWarning = false;
 
-  /**
-   * Set to true if we encounter a condition in the output that indicates we
-   * need to rerun this test.
-   */
-  bool requestRetry = false;
-
-  // Don't call this constructor, call CommandOutput.fromCase() to
-  // get a new TestOutput instance.
-  CommandOutputImpl(TestCase this.testCase,
-                    Command this.command,
+  // TODO(kustermann): Remove testCase from this class.

[ricow1, 2013/07/30 09:30:11]

I think you already did

[kustermann, 2013/07/31 15:53:54]

Not completely, we still pass it in to let the CommandOutput object determine if
it failed or not.

+  CommandOutputImpl(Command this.command,
                     int this.exitCode,
-                    bool this.incomplete,
                     bool this.timedOut,
                     List<int> this.stdout,
                     List<int> this.stderr,
                     Duration this.time,
                     bool this.compilationSkipped) {
-    testCase.commandOutputs[command] = this;
     diagnostics = [];
   }
-  factory CommandOutputImpl.fromCase(TestCase testCase,
-                                     Command command,
-                                     int exitCode,
-                                     bool incomplete,
-                                     bool timedOut,
-                                     List<int> stdout,
-                                     List<int> stderr,
-                                     Duration time,
-                                     bool compilationSkipped) {
-    if (testCase.usesBrowserController) {
-      return new HTMLBrowserCommandOutputImpl(testCase,
-                                              command,
-                                              exitCode,
-                                              incomplete,
-                                              timedOut,
-                                              stdout,
-                                              stderr,
-                                              time,
-                                              compilationSkipped);
-    } else if (testCase is BrowserTestCase) {
-      return new BrowserCommandOutputImpl(testCase,
-                                          command,
-                                          exitCode,
-                                          incomplete,
-                                          timedOut,
-                                          stdout,
-                                          stderr,
-                                          time,
-                                          compilationSkipped);
-    } else if (testCase.configuration['analyzer']) {
-      return new AnalysisCommandOutputImpl(testCase,
-                                           command,
-                                           exitCode,
-                                           timedOut,
-                                           stdout,
-                                           stderr,
-                                           time,
-                                           compilationSkipped);
-    }
-    return new CommandOutputImpl(testCase,
-                                 command,
-                                 exitCode,
-                                 incomplete,
-                                 timedOut,
-                                 stdout,
-                                 stderr,
-                                 time,
-                                 compilationSkipped);
-  }
 
-  String get result =>
-      hasCrashed ? CRASH : (hasTimedOut ? TIMEOUT : (hasFailed ? FAIL : PASS));
-
-  bool get unexpectedOutput => !testCase.expectedOutcomes.contains(result);
+  String result(TestCase testCase) =>
+      hasCrashed ? CRASH : (hasTimedOut ? TIMEOUT : (hasFailed(testCase) ? FAIL : PASS));
 
   bool get hasCrashed {
     // The Java dartc runner and dart2js exits with code 253 in case
@@ -617,42 +648,61 @@ class CommandOutputImpl implements CommandOutput {
 
   bool get hasTimedOut => timedOut;
 
-  bool get didFail {
+  bool didFail(TestCase testCase) {
     return (exitCode != 0 && !hasCrashed);
   }
 
+  bool get canRunDependendCommands {
+    // FIXME(kustermann): We may need to change this
+    return !hasTimedOut && exitCode == 0;
+  }
+
+  bool get successfull {
+    // FIXME(kustermann): We may need to change this
+    return !hasTimedOut && exitCode == 0;
+  }
+
   // Reverse result of a negative test.
-  bool get hasFailed {
-    // Always fail if a runtime-error is expected and compilation failed.
-    if (testCase.info != null && testCase.info.hasRuntimeError && incomplete) {
-      return true;
+  bool hasFailed(TestCase testCase) {
+    // FIXME(kustermann): this is a hack, remove it
+    bool isCompilationCommand = testCase.commands.first == command
+        && testCase.commands.length > 1;
+    if (isCompilationCommand &&
+        testCase.info != null && testCase.info.hasRuntimeError) {
+      //print("runtime error expected: compilation was ${exitCode == 0 ? "successfull " : "failed" }");

[ricow1, 2013/07/30 09:30:11]

commented out long line :-)

[kustermann, 2013/07/31 15:53:54]

Done.

+      return exitCode != 0;
     }
-    return testCase.isNegative ? !didFail : didFail;
+    return testCase.isNegative ? !didFail(testCase) : didFail(testCase);
   }
 }
 
 class BrowserCommandOutputImpl extends CommandOutputImpl {
+  bool _failedBecauseOfMissingXDisplay;
+
   BrowserCommandOutputImpl(
-      testCase,
       command,
       exitCode,
-      incomplete,
       timedOut,
       stdout,
       stderr,
       time,
       compilationSkipped) :
-    super(testCase,
-          command,
+    super(command,
           exitCode,
-          incomplete,
           timedOut,
           stdout,
           stderr,
           time,
-          compilationSkipped);
+          compilationSkipped) {
+    _failedBecauseOfMissingXDisplay = _didFailBecauseOfMissingXDisplay();
+    if (_failedBecauseOfMissingXDisplay) {
+      DebugLogger.warning("Warning: Test failure because of missing XDisplay");
+      // If we get the X server error, or DRT crashes with a core dump, retry
+      // the test.

[ricow1, 2013/07/30 09:30:11]

we just show a warning here, we don't retry

[kustermann, 2013/07/31 15:53:54]

Yes, I removed the requestRetry side-effect from this class.

If it really turns out to be an issue, I'll add it again.
(I got rid of tons of special-casing/side-effects otherwise I would've spent too
much time on these things rather than on the general approach).

[ricow1, 2013/08/01 13:26:21]

OK, my point was that the warning we print is now probably wrong, it says we
will retry

+    }
+  }
 
-  bool get didFail {
+  bool didFail(TestCase testCase) {
     if (_failedBecauseOfMissingXDisplay) {
       return true;
     }
@@ -664,7 +714,7 @@ class BrowserCommandOutputImpl extends CommandOutputImpl {
     return _browserTestFailure;
   }
 
-  bool get _failedBecauseOfMissingXDisplay {
+  bool _didFailBecauseOfMissingXDisplay() {
     // Browser case:
     // If the browser test failed, it may have been because content shell
     // and the virtual framebuffer X server didn't hook up, or it crashed with
@@ -676,12 +726,6 @@ class BrowserCommandOutputImpl extends CommandOutputImpl {
       // This seems to happen quite frequently, we need to figure out why.
       if (line.contains('Gtk-WARNING **: cannot open display') ||
           line.contains('Failed to run command. return code=1')) {
-        // If we get the X server error, or DRT crashes with a core dump, retry
-        // the test.
-        if ((testCase as BrowserTestCase).numRetries > 0) {
-          requestRetry = true;
-        }
-        print("Warning: Test failure because of missing XDisplay");
         return true;
       }
     }
@@ -705,7 +749,6 @@ class BrowserCommandOutputImpl extends CommandOutputImpl {
      * On a layout tests, the DRT output is directly compared with the
      * content of the expected output.
      */
-    var stdout = testCase.commandOutputs[command].stdout;
     var file = new io.File.fromPath(command.expectedOutputFile);
     if (file.existsSync()) {
       var bytesContentLength = "Content-Length:".codeUnits;
@@ -754,16 +797,9 @@ class BrowserCommandOutputImpl extends CommandOutputImpl {
         case 'PASS':
           if (has_content_type) {
             if (exitCode != 0) {
-              print("Warning: All tests passed, but exitCode != 0 "
-                    "(${testCase.displayName})");
-            }
-            if (testCase.configuration['runtime'] == 'drt') {
-              // TODO(kustermann/ricow): Issue: 7563
-              // We should eventually get rid of this hack.
-              return false;
-            } else {
-              return (exitCode != 0 && !hasCrashed);
+              print("Warning: All tests passed, but exitCode != 0 ($this)");
             }
+            return (exitCode != 0 && !hasCrashed);
           }
           break;
       }
@@ -774,19 +810,15 @@ class BrowserCommandOutputImpl extends CommandOutputImpl {
 
 class HTMLBrowserCommandOutputImpl extends BrowserCommandOutputImpl {
  HTMLBrowserCommandOutputImpl(
-      testCase,
       command,
       exitCode,
-      incomplete,
       timedOut,
       stdout,
       stderr,
       time,
       compilationSkipped) :
-    super(testCase,
-          command,
+    super(command,
           exitCode,
-          incomplete,
           timedOut,
           stdout,
           stderr,
@@ -815,33 +847,31 @@ class AnalysisCommandOutputImpl extends CommandOutputImpl {
   bool alreadyComputed = false;
   bool failResult;
 
-  AnalysisCommandOutputImpl(testCase,
-                            command,
+  // TODO(kustermann): Remove testCase from this class

[ricow1, 2013/07/30 09:30:11]

I think you did

[kustermann, 2013/07/31 15:53:54]

Not completely. didFail() takes now a testCase as an argument.

+  AnalysisCommandOutputImpl(command,
                             exitCode,
                             timedOut,
                             stdout,
                             stderr,
                             time,
                             compilationSkipped) :
-    super(testCase,
-          command,
+    super(command,
           exitCode,
-          false,
           timedOut,
           stdout,
           stderr,
           time,
           compilationSkipped);
 
-  bool get didFail {
+  bool didFail(TestCase testCase) {
     if (!alreadyComputed) {
-      failResult = _didFail();
+      failResult = _didFail(testCase);
       alreadyComputed = true;
     }
     return failResult;
   }
 
-  bool _didFail() {
+  bool _didFail(TestCase testCase) {
     if (hasCrashed) return false;
 
     List<String> errors = [];
@@ -859,14 +889,16 @@ class AnalysisCommandOutputImpl extends CommandOutputImpl {
       }
       // OK to Skip error output that doesn't match the machine format
     }
+    // FIXME(kustermann): This is wrong, we should give the expectations in
+    // to command
     if (testCase.info != null
         && testCase.info.optionsFromFile['isMultitest']) {
-      return _didMultitestFail(errors, staticWarnings);
+      return _didMultitestFail(testCase, errors, staticWarnings);
     }
-    return _didStandardTestFail(errors, staticWarnings);
+    return _didStandardTestFail(testCase, errors, staticWarnings);
   }
 
-  bool _didMultitestFail(List errors, List staticWarnings) {
+  bool _didMultitestFail(TestCase testCase, List errors, List staticWarnings) {
     Set<String> outcome = testCase.info.multitestOutcome;
     if (outcome == null) throw "outcome must not be null";
     if (outcome.contains('compile-time error') && errors.length > 0) {
@@ -881,7 +913,7 @@ class AnalysisCommandOutputImpl extends CommandOutputImpl {
     return false;
   }
 
-  bool _didStandardTestFail(List errors, List staticWarnings) {
+  bool _didStandardTestFail(TestCase testCase, List errors, List staticWarnings) {
     bool hasFatalTypeErrors = false;
     int numStaticTypeAnnotations = 0;
     int numCompileTimeAnnotations = 0;
@@ -978,6 +1010,36 @@ class AnalysisCommandOutputImpl extends CommandOutputImpl {
 }
 
 
+CommandOutput createCommandOutput(Command command,
+                                  int exitCode,
+                                  bool timedOut,
+                                  List<int> stdout,
+                                  List<int> stderr,
+                                  Duration time,
+                                  bool compilationSkipped) {
+  if (command is ContentShellCommand) {
+    return new BrowserCommandOutputImpl(
+        command, exitCode, timedOut, stdout, stderr,
+        time, compilationSkipped);
+  } else if (command is BrowserTestCommand) {
+    return new HTMLBrowserCommandOutputImpl(
+        command, exitCode, timedOut, stdout, stderr,
+        time, compilationSkipped);
+  } else if (command is SeleniumTestCommand) {
+    return new BrowserCommandOutputImpl(
+        command, exitCode, timedOut, stdout, stderr,
+        time, compilationSkipped);
+  } else if (command is AnalysisCommand) {
+    return new AnalysisCommandOutputImpl(
+        command, exitCode, timedOut, stdout, stderr,
+        time, compilationSkipped);
+  }
+  return new CommandOutputImpl(
+      command, exitCode, timedOut, stdout, stderr,
+      time, compilationSkipped);
+}
+
+
 /** Modifies the --timeout=XX parameter passed to run_selenium.py */
 List<String> _modifySeleniumTimeout(List<String> arguments, int timeout) {
   return arguments.map((argument) {
@@ -1001,8 +1063,8 @@ List<String> _modifySeleniumTimeout(List<String> arguments, int timeout) {
  * be garbage collected as soon as it is done.
  */
 class RunningProcess {
-  TestCase testCase;
   Command command;
+  int timeout;
   bool timedOut = false;
   DateTime startTime;
   Timer timeoutTimer;
@@ -1011,13 +1073,9 @@ class RunningProcess {
   bool compilationSkipped = false;
   Completer<CommandOutput> completer;
 
-  RunningProcess(TestCase this.testCase, Command this.command);
-
-  Future<CommandOutput> start() {
-    if (testCase.expectedOutcomes.contains(SKIP)) {
-      throw "testCase.expectedOutcomes must not contain 'SKIP'.";
-    }
+  RunningProcess(Command this.command, this.timeout);
 
+  Future<CommandOutput> run() {
     completer = new Completer<CommandOutput>();
     startTime = new DateTime.now();
     _runCommand();
@@ -1032,7 +1090,7 @@ class RunningProcess {
       } else {
         var processEnvironment = _createProcessEnvironment();
         var commandArguments = _modifySeleniumTimeout(command.arguments,
-                                                      testCase.timeout);
+                                                      timeout);
         Future processFuture =
             io.Process.start(command.executable,
                              commandArguments,
@@ -1049,7 +1107,7 @@ class RunningProcess {
           process.exitCode.then(_commandComplete);
           _drainStream(process.stdout, stdout);
           _drainStream(process.stderr, stderr);
-          timeoutTimer = new Timer(new Duration(seconds: testCase.timeout),
+          timeoutTimer = new Timer(new Duration(seconds: timeout),
                                    timeoutHandler);
         }).catchError((e) {
           // TODO(floitsch): should we try to report the stacktrace?
@@ -1072,12 +1130,9 @@ class RunningProcess {
   }
 
   CommandOutput _createCommandOutput(Command command, int exitCode) {
-    var incomplete = command != testCase.commands.last;
-    var commandOutput = new CommandOutput.fromCase(
-        testCase,
+    var commandOutput = createCommandOutput(
         command,
         exitCode,
-        incomplete,
         timedOut,
         stdout,
         stderr,
@@ -1094,8 +1149,9 @@ class RunningProcess {
     var baseEnvironment = command.environment != null ?
         command.environment : io.Platform.environment;
     var environment = new Map<String, String>.from(baseEnvironment);
-    environment['DART_CONFIGURATION'] =
-        TestUtils.configurationDir(testCase.configuration);
+    // FIXME(kustermann): We've to fix this
+    //environment['DART_CONFIGURATION'] =
+    //    TestUtils.configurationDir(testCase.configuration);
 
     for (var excludedEnvironmentVariable in EXCLUDED_ENVIRONMENT_VARIABLES) {
       environment.remove(excludedEnvironmentVariable);
@@ -1106,9 +1162,29 @@ class RunningProcess {
 }
 
 class BatchRunnerProcess {
+  final batchRunnerTypes = {
+      'selenium' : {
+          'run_executable' : 'python',
+          'run_arguments' : ['tools/testing/run_selenium.py', '--batch'],
+          'terminate_command' : ['--terminate'],
+      },
+      'dartanalyzer' : {
+        'run_executable' : 'sdk/bin/dartanalyzer_developer', // $suffix
+        'run_arguments' : ['--batch'],
+        'terminate_command' : null,
+      },
+      'dart2analyzer' : {
+        'run_executable' : 'editor/tools/analyzer_experimental',
+        'run_arguments' : ['--batch'],
+        'terminate_command' : null,
+    },
+  };
+
+  Completer<CommandOutput> completer;

[ricow1, 2013/07/30 09:30:11]

why is this public when everything else is private - I don't see any uses
externally

[kustermann, 2013/07/31 15:53:54]

Done.

   Command _command;
   String _executable;
-  List<String> _batchArguments;
+  List<String> _arguments;
+  String _runnerType;
 
   io.Process _process;
   Completer _stdoutCompleter;
@@ -1117,47 +1193,44 @@ class BatchRunnerProcess {
   StreamSubscription<String> _stderrSubscription;
   Function _processExitHandler;
 
-  TestCase _currentTest;
+  bool _currentlyRunning = false;
   List<int> _testStdout;
   List<int> _testStderr;
   String _status;
   DateTime _startTime;
   Timer _timer;
-  bool _isWebDriver;
 
-  BatchRunnerProcess(TestCase testCase) {
-    _command = testCase.commands.last;
-    _executable = testCase.commands.last.executable;
-    _batchArguments = testCase.batchRunnerArguments;
-    _isWebDriver = testCase.usesWebDriver;
-  }
+  BatchRunnerProcess();
 
-  bool get active => _currentTest != null;
+  Future<CommandOutput> runCommand(String runnerType, Command command,
+                                   int timeout, List<String> arguments) {
+    assert(completer == null);
+    assert(!_currentlyRunning);
+
+    completer = new Completer<CommandOutput>();

[ricow1, 2013/07/30 09:30:11]

we could eliminate this if you refactor doStartTest and reportResult to return
futures instead, but I don't feel strongly about this

[kustermann, 2013/07/31 15:53:54]

Yes, but let's keep it this way for now.

+    bool sameRunnerType = _runnerType == runnerType;
+    _runnerType = runnerType;
+    _currentlyRunning = true;
+    _command = command;
+    _arguments = arguments;
 
-  void startTest(TestCase testCase) {
-    if (_currentTest != null) throw "_currentTest must be null.";
-    _currentTest = testCase;
-    _command = testCase.commands.last;
     if (_process == null) {
       // Start process if not yet started.
-      _executable = testCase.commands.last.executable;
       _startProcess(() {
-        doStartTest(testCase);
+        doStartTest(command, timeout);
       });
-    } else if (testCase.commands.last.executable != _executable) {
-      // Restart this runner with the right executable for this test
-      // if needed.
-      _executable = testCase.commands.last.executable;
-      _batchArguments = testCase.batchRunnerArguments;
+    } else if (!sameRunnerType) {
+      // Restart this runner with the right executable for this test if needed.
       _processExitHandler = (_) {
         _startProcess(() {
-          doStartTest(testCase);
+          doStartTest(command, timeout);
         });
       };
       _process.kill();
     } else {
-      doStartTest(testCase);
+      doStartTest(command, timeout);
     }
+    return completer.future;
   }
 
   Future terminate() {
@@ -1168,11 +1241,12 @@ class BatchRunnerProcess {
       if (killTimer != null) killTimer.cancel();
       completer.complete(true);
     };
-    if (_isWebDriver) {
+    var shutdownCommand = batchRunnerTypes[_runnerType]['terminate_command'];
+    if (shutdownCommand != null && !shutdownCommand.isEmpty) {
       // Use a graceful shutdown so our Selenium script can close
       // the open browser processes. On Windows, signals do not exist
       // and a kill is a hard kill.
-      _process.stdin.writeln('--terminate');
+      _process.stdin.writeln(shutdownCommand.join(' '));
 
       // In case the run_selenium process didn't close, kill it after 30s
       killTimer = new Timer(new Duration(seconds: 30), _process.kill);
@@ -1183,23 +1257,22 @@ class BatchRunnerProcess {
     return completer.future;
   }
 
-  void doStartTest(TestCase testCase) {
+  void doStartTest(Command command, int timeout) {
     _startTime = new DateTime.now();
     _testStdout = [];
     _testStderr = [];
     _status = null;
     _stdoutCompleter = new Completer();
     _stderrCompleter = new Completer();
-    _timer = new Timer(new Duration(seconds: testCase.timeout),
+    _timer = new Timer(new Duration(seconds: timeout),
                        _timeoutHandler);
 
-    if (testCase.commands.last.environment != null) {
+    if (command.environment != null) {
       print("Warning: command.environment != null, but we don't support custom "
             "environments for batch runner tests!");
     }
 
-    var line = _createArgumentsLine(testCase.batchTestArguments,
-                                    testCase.timeout);
+    var line = _createArgumentsLine(_arguments, timeout);
     _process.stdin.write(line);
     _stdoutSubscription.resume();
     _stderrSubscription.resume();
@@ -1213,30 +1286,29 @@ class BatchRunnerProcess {
   }
 
   void _reportResult() {
-    if (!active) return;
+    if (!_currentlyRunning) return;
     // _status == '>>> TEST {PASS, FAIL, OK, CRASH, FAIL, TIMEOUT}'
 
     var outcome = _status.split(" ")[2];
     var exitCode = 0;
     if (outcome == "CRASH") exitCode = CRASHING_BROWSER_EXITCODE;
     if (outcome == "FAIL" || outcome == "TIMEOUT") exitCode = 1;
-    new CommandOutput.fromCase(_currentTest,
-                               _command,
-                               exitCode,
-                               false,
-                               (outcome == "TIMEOUT"),
-                               _testStdout,
-                               _testStderr,
-                               new DateTime.now().difference(_startTime),
-                               false);
-    var test = _currentTest;
-    _currentTest = null;
-    test.completed();
+    var output = createCommandOutput(_command,
+                        exitCode,
+                        (outcome == "TIMEOUT"),
+                        _testStdout,
+                        _testStderr,
+                        new DateTime.now().difference(_startTime),
+                        false);
+    assert(completer != null);
+    completer.complete(output);
+    completer = null;
+    _currentlyRunning = false;
   }
 
   ExitCodeEvent makeExitHandler(String status) {
     void handler(int exitCode) {
-      if (active) {
+      if (_currentlyRunning) {
         if (_timer != null) _timer.cancel();
         _status = status;
         _stdoutSubscription.cancel();
@@ -1255,7 +1327,9 @@ class BatchRunnerProcess {
   }
 
   _startProcess(callback) {
-    Future processFuture = io.Process.start(_executable, _batchArguments);
+    var executable = batchRunnerTypes[_runnerType]['run_executable'];
+    var arguments = batchRunnerTypes[_runnerType]['run_arguments'];
+    Future processFuture = io.Process.start(executable, arguments);
     processFuture.then((io.Process p) {
       _process = p;
 
@@ -1312,7 +1386,7 @@ class BatchRunnerProcess {
     }).catchError((e) {
       // TODO(floitsch): should we try to report the stacktrace?
       print("Process error:");
-      print("  Command: $_executable ${_batchArguments.join(' ')}");
+      print("  Command: $executable ${arguments.join(' ')} ($_arguments)");
       print("  Error: $e");
       // If there is an error starting a batch process, chances are that
       // it will always fail. So rather than re-trying a 1000+ times, we
@@ -1323,111 +1397,30 @@ class BatchRunnerProcess {
   }
 }
 
+
 /**
- * ProcessQueue is the master control class, responsible for running all
- * the tests in all the TestSuites that have been registered.  It includes
- * a rate-limited queue to run a limited number of tests in parallel,
- * a ProgressIndicator which prints output when tests are started and
- * and completed, and a summary report when all tests are completed,
- * and counters to determine when all of the tests in all of the test suites
- * have completed.
+ * [TestCaseEnqueuer] takes a list of TestSuites, generates TestCases and
+ * builds a dependency graph of all commands in every TestSuite.
  *
- * Because multiple configurations may be run on each test suite, the
- * ProcessQueue contains a cache in which a test suite may record information
- * about its list of tests, and may retrieve that information when it is called
- * upon to enqueue its tests again.
+ * It will maintain three helper data structures

[ricow1, 2013/07/30 09:30:11]

Extend this comment to say:
The node structure is explicitly build to guarantee that objects with the same
instance variables have the same hashCode and return true in the equality
operator when the instance variables are the same

[kustermann, 2013/07/31 15:53:54]

Done.

+ *  - command2node: A mapping from a [Command] to a node in the dependency graph
+ *  - command2testCases: A mapping from [Command] to all TestCases that it is
+ *    part of
+ *  - remainingTestCases: A set of TestCases that were enqueued but are not
+ *    finished
  */
-class ProcessQueue {
-  int _numProcesses = 0;
-  int _maxProcesses;
-  int _numBrowserProcesses = 0;
-  int _maxBrowserProcesses;
-  int _numFailedTests = 0;
-  bool _allTestsWereEnqueued = false;
-
-  // Support for recording and replaying test commands.
-  TestCaseRecorder _testCaseRecorder;
-  TestCaseOutputArchive _testCaseOutputArchive;
-
-  /** The number of tests we allow to actually fail before we stop retrying. */
-  int _MAX_FAILED_NO_RETRY = 4;
-  bool _verbose;
-  bool _listTests;
-  Function _allDone;
-  Queue<TestCase> _tests;
-  List<EventListener> _eventListener;
-
-  // For dartc/selenium batch processing we keep a list of batch processes.
-  Map<String, List<BatchRunnerProcess>> _batchProcesses;
-
-  // Cache information about test cases per test suite. For multiple
-  // configurations there is no need to repeatedly search the file
-  // system, generate tests, and search test files for options.
-  Map<String, List<TestInformation>> _testCache;
-
-  Map<String, BrowserTestRunner> _browserTestRunners;
-
-  /**
-   * String indicating the browser used to run the tests. Empty if no browser
-   * used.
-   */
-  String browserUsed = '';
-
-  /**
-   * Process running the selenium server .jar (only used for Safari and Opera
-   * tests.)
-   */
-  io.Process _seleniumServer = null;
-
-  /** True if we are in the process of starting the server. */
-  bool _startingServer = false;
-
-  /** True if we find that there is already a selenium jar running. */
-  bool _seleniumAlreadyRunning = false;
-
-  ProcessQueue(this._maxProcesses,
-               this._maxBrowserProcesses,
-               DateTime startTime,
-               testSuites,
-               this._eventListener,
-               this._allDone,
-               [bool verbose = false,
-                bool listTests = false,
-                this._testCaseRecorder,
-                this._testCaseOutputArchive])
-      : _verbose = verbose,
-        _listTests = listTests,
-        _tests = new Queue<TestCase>(),
-        _batchProcesses = new Map<String, List<BatchRunnerProcess>>(),
-        _testCache = new Map<String, List<TestInformation>>(),
-        _browserTestRunners = new Map<String, BrowserTestRunner>() {
-    _runTests(testSuites);
-  }
-
-  /**
-   * Perform any cleanup needed once all tests in a TestSuite have completed
-   * and notify our progress indicator that we are done.
-   */
-  void _cleanupAndMarkDone() {
-    _allDone();
-    if (browserUsed != '' && _seleniumServer != null) {
-      _seleniumServer.kill();
-    }
-    eventAllTestsDone();
-  }
+class TestCaseEnqueuer {
+  final dgraph.Graph graph;
+  final Function _onTestCaseAdded;
 
-  void _checkDone() {
-    if (_allTestsWereEnqueued && _tests.isEmpty && _numProcesses == 0) {
-      _terminateBatchRunners().then((_) {
-        _terminateBrowserRunners().then((_) => _cleanupAndMarkDone());
-      });
-    }
-  }
+  final command2node = new Map<Command, dgraph.Node>();
+  final command2testCases = new Map<Command, List<TestCase>>();
+  final remainingTestCases = new Set<TestCase>();
 
-  void _runTests(List<TestSuite> testSuites) {
-    var newTest;
-    var allTestsKnown;
+  TestCaseEnqueuer(this.graph, this._onTestCaseAdded);
 
+  void enqueueTestSuites(List<TestSuite> testSuites) {
+    /*
     if (_testCaseRecorder != null) {
       // Mode: recording.
       newTest = _testCaseRecorder.nextTestCase;
@@ -1445,7 +1438,6 @@ class ProcessQueue {
           eventTestAdded(testCase);
           Timer.run(() {
             var output = _testCaseOutputArchive.outputOf(testCase);
-            testCase.completed();
             eventFinishedTestCase(testCase);
           });
         };
@@ -1456,207 +1448,364 @@ class ProcessQueue {
           Timer.run(() => _cleanupAndMarkDone());
         };
       } else {
-        // Mode: none (we're not recording/replaying).
-        newTest = (TestCase testCase) {
-          _tests.add(testCase);
-          eventTestAdded(testCase);
-          _runTest(testCase);
-        };
-        allTestsKnown = _checkDone;
+
+      eventTestAdded(testCase);
+
+      */

[ricow1, 2013/07/30 09:30:11]

a lot of commented out code

[kustermann, 2013/07/31 15:53:54]

Done.

+      // Mode: none (we're not recording/replaying).
+
+    void newTest(TestCase testCase) {
+      //print("adding ${testCase.displayName}");

[ricow1, 2013/07/30 09:30:11]

commented out code

[kustermann, 2013/07/31 15:53:54]

Done.

+      remainingTestCases.add(testCase);
+
+      var lastNode;
+      for (var command in testCase.commands) {
+        // Make exactly *one* node in the dependency graph for every command.
+        var node = command2node[command];
+        if (node == null) {
+          var requiredNodes = (lastNode != null) ? [lastNode] : [];
+          node = graph.newNode(command, requiredNodes);
+          command2node[command] = node;
+          command2testCases[command] = <TestCase>[];
+        }
+        // Keep mapping from command to all testCases that refer to it
+        command2testCases[command].add(testCase);
+
+        lastNode = node;
       }
+      _onTestCaseAdded(testCase);
     }
 
-    // FIXME: For some reason we cannot call this method on all test suites
-    // in parallel.
-    // If we do, not all tests get enqueued (if --arch=all was specified,
-    // we don't get twice the number of tests [tested on -rvm -cnone])
-    // Issue: 7927
+    // Cache information about test cases per test suite. For multiple
+    // configurations there is no need to repeatedly search the file
+    // system, generate tests, and search test files for options.
+    var testCache = new Map<String, List<TestInformation>>();
+
     Iterator<TestSuite> iterator = testSuites.iterator;
     void enqueueNextSuite() {
       if (!iterator.moveNext()) {
-        _allTestsWereEnqueued = true;
-        allTestsKnown();
-        eventAllTestsKnown();
+        // We're finished with building the dependency graph.
+        graph.sealGraph();
       } else {
-        iterator.current.forEachTest(newTest, _testCache, enqueueNextSuite);
+        iterator.current.forEachTest(newTest, testCache, enqueueNextSuite);
       }
     }
     enqueueNextSuite();
   }
+}
 
-  /**
-   * True if we are using a browser + platform combination that needs the
-   * Selenium server jar.
-   */
-  bool get _needsSelenium => (io.Platform.operatingSystem == 'macos' &&
-      browserUsed == 'safari') || browserUsed == 'opera';
 
-  /** True if the Selenium Server is ready to be used. */
-  bool get _isSeleniumAvailable => _seleniumServer != null ||
-      _seleniumAlreadyRunning;
+/*
+ * [CommandEnqueuer] will
+ *  - change node.state to NodeState.Enqueuing as soon as all dependencies have
+ *    a state of NodeState.Successful
+ *  - change node.state to NodeState.UnableToRun if one or more dependencies
+ *    have a state of NodeState.Failed/NodeState.UnableToRun.
+ */
+class CommandEnqueuer {
+  static final INIT_STATES = [dgraph.NodeState.Initialized,
+                              dgraph.NodeState.Waiting];
+  static final FINISHED_STATES = [dgraph.NodeState.Successfull,
+                                  dgraph.NodeState.Failed,
+                                  dgraph.NodeState.UnableToRun];
+  final dgraph.Graph _graph;
+
+  CommandEnqueuer(this._graph) {
+    var eventCondition = _graph.events.where;
+
+    eventCondition((e) => e is dgraph.NodeAddedEvent).listen((event) {
+      dgraph.Node node = event.node;
+      _changeNodeStateIfNecessary(node);
+    });
 
-  /**
-   * Restart all the processes that have been waiting/stopped for the server to
-   * start up. If we just call this once we end up with a single-"threaded" run.
-   */
-  void resumeTesting() {
-    for (int i = 0; i < _maxProcesses; i++) _tryRunTest();
+    eventCondition((e) => e is dgraph.StateChangedEvent).listen((event) {
+      if (event.from == dgraph.NodeState.Processing) {
+        assert(FINISHED_STATES.contains(event.to));
+        for (var dependendNode in event.node.neededFor) {
+          _changeNodeStateIfNecessary(dependendNode);
+        }
+      }
+    });
   }
 
-  /** Start the Selenium Server jar, if appropriate for this platform. */
-  void _ensureSeleniumServerRunning() {
-    if (!_isSeleniumAvailable && !_startingServer) {
-      _startingServer = true;
+  // Called when either a new node was added or if one of it's dependencies
+  // changed it's state.
+  void _changeNodeStateIfNecessary(dgraph.Node node) {
+    assert(INIT_STATES.contains(node.state));
+    bool allDependenciesFinished =
+        node.dependencies.every((node) => FINISHED_STATES.contains(node.state));
+    bool allDependenciesSuccessful = node.dependencies.every(

[ricow1, 2013/07/30 09:30:11]

You could move this to the if body below

[kustermann, 2013/07/31 15:53:54]

Done.

+        (dep) => dep.state == dgraph.NodeState.Successfull);
 
-      // Check to see if the jar was already running before the program started.
-      String cmd = 'ps';
-      var arg = ['aux'];
-      if (io.Platform.operatingSystem == 'windows') {
-        cmd = 'tasklist';
-        arg.add('/v');
+    var newState;
+    if (allDependenciesFinished) {
+      if (allDependenciesSuccessful) {
+        newState = dgraph.NodeState.Enqueing;
+      } else {
+        newState = dgraph.NodeState.UnableToRun;
       }
+    } else {
+      newState = dgraph.NodeState.Waiting;
+    }
+    if (node.state != newState) {
+      _graph.changeState(node, newState);
+    }
+  }
+}
 
-      Future processFuture = io.Process.start(cmd, arg);
-      processFuture.then((io.Process p) {
-        // Drain stderr to not leak resources.
-        p.stderr.listen((_) {});
-        final Stream<String> stdoutStringStream =
-            p.stdout.transform(new io.StringDecoder())
-                    .transform(new io.LineTransformer());
-        stdoutStringStream.listen((String line) {
-          var regexp = new RegExp(r".*selenium-server-standalone.*");
-          if (regexp.hasMatch(line)) {
-            _seleniumAlreadyRunning = true;
-            resumeTesting();
-          }
-          if (!_isSeleniumAvailable) {
-            _startSeleniumServer();
+
+/*
+ * [CommandQueue] will listen for nodes entering the NodeState.ENQUEUING state,
+ * queue them up and run them. While nodes are processed they will be in the
+ * NodeState.PROCESSING state. After running a command, the node will change
+ * to a state of NodeState.Successfull or NodeState.Failed.
+ *
+ * It provides a synchronous stream [completedCommands] which provides the
+ * [CommandOutputs] for the finished commands.
+ *
+ * It provides a [done] future, which will complete once there are no more
+ * nodes left in the states Initialized/Waiting/Enqueing/Processing
+ * and the [executor] has cleaned up it's resources.
+ */
+class CommandQueue {
+  final dgraph.Graph graph;
+  final CommandExecutor executor;
+  final TestCaseEnqueuer enqueuer;
+
+  final Queue<Command> _runQueue = new Queue<Command>();
+  final _commandOutputStream =  new StreamController<CommandOutput>(sync: true);
+  final _completer =  new Completer();
+
+  int _numProcesses = 0;
+  int _maxProcesses;
+  int _numBrowserProcesses = 0;
+  int _maxBrowserProcesses;
+  bool _finishing = false;
+
+  CommandQueue(this.graph, this.enqueuer, this.executor,
+               this._maxProcesses, this._maxBrowserProcesses) {
+    var eventCondition = graph.events.where;
+    eventCondition((event) => event is dgraph.StateChangedEvent)
+        .listen((event) {
+          if (event.to == dgraph.NodeState.Enqueing) {
+            assert(event.from == dgraph.NodeState.Initialized ||
+                   event.from == dgraph.NodeState.Waiting);
+            graph.changeState(event.node, dgraph.NodeState.Processing);
+            var command = event.node.userData;
+            _runQueue.add(command);
+            Timer.run(() => _tryRunNextCommand());
           }
-        });
-      }).catchError((e) {
-      // TODO(floitsch): should we try to report the stacktrace?
-        print("Error starting process:");
-        print("  Command: $cmd ${arg.join(' ')}");
-        print("  Error: $e");
-        // TODO(ahe): How to report this as a test failure?
-        io.exit(1);
-        return true;
-      });
-    }
+    });
   }
 
-  void _runTest(TestCase test) {
-    if (test.usesWebDriver) {
-      browserUsed = test.configuration['runtime'];
-      if (_needsSelenium) _ensureSeleniumServerRunning();
+  Stream<CommandOutput> get completedCommands => _commandOutputStream.stream;
+
+  Future get done => _completer.future;
+
+  void _tryRunNextCommand() {
+    _checkDone();
+
+    if (_numProcesses < _maxProcesses && !_runQueue.isEmpty) {
+      Command command = _runQueue.removeFirst();
+      var isBrowserCommand =
+          command is SeleniumTestCommand ||
+          command is BrowserTestCase;
+
+      if (isBrowserCommand && _numBrowserProcesses == _maxBrowserProcesses) {
+        // If there is no free browser runner, put it back into the queue.
+        _runQueue.add(command);
+        // Don't lose a process.
+        new Timer(new Duration(milliseconds: 100), _tryRunNextCommand);
+        return;
+      }
+
+      _numProcesses++;
+      if (isBrowserCommand) _numBrowserProcesses++;
+
+      var node = enqueuer.command2node[command];
+      Iterable<TestCase> testCases = enqueuer.command2testCases[command];
+      int timeout = testCases.map((TestCase test) => test.timeout)
+          .fold(0, math.max);
+
+      executor.runCommand(node, command, timeout).then((CommandOutput output) {
+        assert(command == output.command);
+
+        _commandOutputStream.add(output);
+        if (output.canRunDependendCommands) {
+          graph.changeState(node, dgraph.NodeState.Successfull);
+        } else {
+          graph.changeState(node, dgraph.NodeState.Failed);
+        }
+
+        _numProcesses--;
+        if (isBrowserCommand) _numBrowserProcesses--;
+
+        // Don't loose a process
+        Timer.run(() => _tryRunNextCommand());
+      });
     }
-    _tryRunTest();
   }
 
-  /**
-   * Monitor the output of the Selenium server, to know when we are ready to
-   * begin running tests.
-   * source: Output(Stream) from the Java server.
-   */
-  void seleniumServerHandler(String line) {
-    if (new RegExp(r".*Started.*Server.*").hasMatch(line) ||
-        new RegExp(r"Exception.*Selenium is already running.*").hasMatch(
-        line)) {
-      resumeTesting();
+  void _checkDone() {
+    if (!_finishing &&
+        _runQueue.isEmpty &&
+        _numProcesses == 0 &&
+        graph.isSealed &&
+        graph.stateCount(dgraph.NodeState.Initialized) == 0 &&
+        graph.stateCount(dgraph.NodeState.Waiting) == 0 &&
+        graph.stateCount(dgraph.NodeState.Enqueing) == 0 &&
+        graph.stateCount(dgraph.NodeState.Processing) == 0) {
+      _finishing = true;
+      executor.cleanup().then((_) {
+        _completer.complete();
+        _commandOutputStream.close();
+      });
     }
   }
+}
 
-  /**
-   * For browser tests using Safari or Opera, we need to use the Selenium 1.0
-   * Java server.
-   */
-  void _startSeleniumServer() {
-    // Get the absolute path to the Selenium jar.
-    String filePath = TestUtils.testScriptPath;
-    String pathSep = io.Platform.pathSeparator;
-    int index = filePath.lastIndexOf(pathSep);
-    filePath = '${filePath.substring(0, index)}${pathSep}testing${pathSep}';
-    new io.Directory(filePath).list().listen((io.FileSystemEntity fse) {
-      if (fse is io.File) {
-        String file = fse.path;
-        if (new RegExp(r"selenium-server-standalone-.*\.jar").hasMatch(file)
-            && _seleniumServer == null) {
-          Future processFuture = io.Process.start('java', ['-jar', file]);
-          processFuture.then((io.Process server) {
-            _seleniumServer = server;
-            // Heads up: there seems to an obscure data race of some form in
-            // the VM between launching the server process and launching the
-            // test tasks that disappears when you read IO (which is
-            // convenient, since that is our condition for knowing that the
-            // server is ready).
-            Stream<String> stdoutStringStream =
-                _seleniumServer.stdout.transform(new io.StringDecoder())
-                .transform(new io.LineTransformer());
-            Stream<String> stderrStringStream =
-                _seleniumServer.stderr.transform(new io.StringDecoder())
-                .transform(new io.LineTransformer());
-            stdoutStringStream.listen(seleniumServerHandler);
-            stderrStringStream.listen(seleniumServerHandler);
-          }).catchError((e) {
-            // TODO(floitsch): should we try to report the stacktrace?
-            print("Process error:");
-            print("  Command: java -jar $file");
-            print("  Error: $e");
-            // TODO(ahe): How to report this as a test failure?
-            io.exit(1);
-            return true;
-          });
-        }
+
+/*
+ * [CommandExecutor] is responsible for executing commands. It will make sure
+ * that the the following two constraints are satisfied
+ *  - [:maxProcesses < numberOfProcessesUsed:]
+ *  - [:maxBrowserProcesses < numberOfBrowserProcessesUsed:]
+ *
+ * It provides a [runCommand] method which will complete with a
+ * [CommandOutput] object.
+ *
+ * It provides a [cleanup] method to free all the allocated resources.
+ */
+abstract class CommandExecutor {
+  Future cleanup();
+  Future<CommandOutput> runCommand(node, Command command, int timeout);
+}
+
+class CommandExecutorImpl {
+  final Map globalConfiguration;
+  final int maxProcesses;
+  final int maxBrowserProcesses;
+
+  // For dartc/selenium batch processing we keep a list of batch processes.
+  final _batchProcesses = new Map<String, List<BatchRunnerProcess>>();
+  // For browser tests we keepa [BrowserTestRunner]
+  final _browserTestRunners = new Map<String, BrowserTestRunner>();
+
+  bool _finishing = false;
+
+  CommandExecutorImpl(
+      this.globalConfiguration, this.maxProcesses, this.maxBrowserProcesses);
+
+  Future cleanup() {
+    assert(!_finishing);
+    _finishing = true;
+
+    Future _terminateBatchRunners() {
+      var futures = [];
+      for (var runners in _batchProcesses.values) {
+        futures.addAll(runners.map((runner) => runner.terminate()));
       }
-    });
+      return Future.wait(futures);
+    }
+
+    Future _terminateBrowserRunners() {
+      var futures =
+          _browserTestRunners.values.map((runner) => runner.terminate());
+      return Future.wait(futures);
+    }
+
+    return Future.wait([_terminateBatchRunners(), _terminateBrowserRunners()]);
   }
 
-  Future _terminateBatchRunners() {
-    var futures = new List();
-    for (var runners in _batchProcesses.values) {
-      for (var runner in runners) {
-        futures.add(runner.terminate());
-      }
+  Future<CommandOutput> runCommand(node, Command command, int timeout) {
+    assert(!_finishing);
+
+    var completer = new Completer<CommandOutput>();
+
+    void runCommand(int retriesLeft) {

[ricow1, 2013/07/30 09:30:11]

why not remove the completer and do:
Future runCommand(int retriesLeft) {
  return _runCommand(command, timeout).then((CommandOutput output) {
    if (!output.canRunDependendCommands && retriesLeft > 0) {
      DebugLogger.warning("Rerunning Command: ($retriesLeft "
                          "attempt(s) remains) [cmd: $command]");
      return runCommand(retriesLeft - 1);
    } else
      return output;
    }
  });
  return runCommand(command.numRetries);

[kustermann, 2013/07/31 15:53:54]

Done.

+      _runCommand(command, timeout).then((CommandOutput output) {
+        if (!output.canRunDependendCommands && retriesLeft > 0) {
+          DebugLogger.warning("Rerunning Command: ($retriesLeft "
+                              "attempt(s) remains) [cmd: $command]");
+          runCommand(retriesLeft - 1);
+        } else {
+          completer.complete(output);
+        }
+      });
     }
-    // Change to Future.wait when updating binaries.
-    return Future.wait(futures);
+    runCommand(command.numRetries);
+
+    return completer.future;
   }
 
-  Future _terminateBrowserRunners() {
-    var futures = [];
-    for (BrowserTestRunner runner in _browserTestRunners.values) {
-      futures.add(runner.terminate());
+  Future<CommandOutput> _runCommand(Command command, int timeout) {
+    var completer = new Completer();

[ricow1, 2013/07/30 09:30:11]

this is unused

[kustermann, 2013/07/31 15:53:54]

Done.

+    var batchMode = !globalConfiguration['noBatch'];
+
+    if (command is BrowserTestCommand) {
+      return _startBrowserControllerTest(command, timeout);
+    } else if (command is SeleniumTestCommand && batchMode) {
+      var arguments = ['--force-refresh', '--browser=${command.browser}',
+                       '--timeout=${timeout}', '--out', '${command.url}'];
+      return _getBatchRunner(command.browser)
+          .runCommand('selenium', command, timeout, arguments);
+    } else if (command is AnalysisCommand && batchMode) {
+      return _getBatchRunner(command.flavour)
+          .runCommand(command.flavour, command, timeout, command.arguments);
+    } else {
+      return new RunningProcess(command, timeout).run();
     }
-    return Future.wait(futures);
   }
 
-  BatchRunnerProcess _getBatchRunner(TestCase test) {
+  BatchRunnerProcess _getBatchRunner(String identifier) {
     // Start batch processes if needed
-    var compiler = test.configuration['compiler'];
-    var runners = _batchProcesses[compiler];
+    var runners = _batchProcesses[identifier];
     if (runners == null) {
-      runners = new List<BatchRunnerProcess>(_maxProcesses);
-      for (int i = 0; i < _maxProcesses; i++) {
-        runners[i] = new BatchRunnerProcess(test);
+      runners = new List<BatchRunnerProcess>(maxProcesses);
+      for (int i = 0; i < maxProcesses; i++) {
+        runners[i] = new BatchRunnerProcess();
       }
-      _batchProcesses[compiler] = runners;
+      _batchProcesses[identifier] = runners;
     }
 
     for (var runner in runners) {
-      if (!runner.active) return runner;
+      if (!runner._currentlyRunning) return runner;
     }
     throw new Exception('Unable to find inactive batch runner.');
   }
 
-  Future<BrowserTestRunner> _getBrowserTestRunner(TestCase test) {
-    var local_ip = test.configuration['local_ip'];
-    var runtime = test.configuration['runtime'];
-    var num_browsers = _maxBrowserProcesses;
-    if (_browserTestRunners[runtime] == null) {
+  Future<CommandOutput> _startBrowserControllerTest(
+      BrowserTestCommand browserCommand, int timeout) {
+    var completer = new Completer<CommandOutput>();
+
+    var callback = (var output, var duration) {
+      var commandOutput = createCommandOutput(browserCommand,
+                          0,
+                          output == "TIMEOUT",
+                          encodeUtf8(output),
+                          [],
+                          duration,
+                          false);
+      completer.complete(commandOutput);
+    };
+    BrowserTest browserTest = new BrowserTest(browserCommand.url,
+                                              callback,
+                                              timeout);
+    _getBrowserTestRunner(browserCommand.browser).then((testRunner) {
+      testRunner.queueTest(browserTest);
+    });
+
+    return completer.future;
+  }
+
+  Future<BrowserTestRunner> _getBrowserTestRunner(String browser) {
+    var local_ip = globalConfiguration['local_ip'];
+    var num_browsers = maxBrowserProcesses;
+    if (_browserTestRunners[browser] == null) {
       var testRunner =
-        new BrowserTestRunner(local_ip, runtime, num_browsers);
+        new BrowserTestRunner(local_ip, browser, num_browsers);
       testRunner.logger = DebugLogger.info;
-      _browserTestRunners[runtime] = testRunner;
+      _browserTestRunners[browser] = testRunner;
       return testRunner.start().then((started) {
         if (started) {
           return testRunner;
@@ -1665,251 +1814,212 @@ class ProcessQueue {
         io.exit(1);
       });
     }
-    return new Future.value(_browserTestRunners[runtime]);
+    return new Future.value(_browserTestRunners[browser]);
   }
+}
 
-  void _startBrowserControllerTest(var test) {
-    var callback = (var output, var duration) {
-      var nextCommandIndex = test.commandOutputs.keys.length;
-      new CommandOutput.fromCase(test,
-                                 test.commands[nextCommandIndex],
-                                 0,
-                                 false,
-                                 output == "TIMEOUT",
-                                 encodeUtf8(output),
-                                 [],
-                                 duration,
-                                 false);
-      test.completedHandler(test);
-    };
-    BrowserTest browserTest = new BrowserTest(test.testingUrl,
-                                              callback,
-                                              test.timeout);
-    _getBrowserTestRunner(test).then((testRunner) {
-      testRunner.queueTest(browserTest);
-    });
+
+// TODO(kustermann): Add support for '--list' and '--verbose'!
+// TODO(kustermann): The [timeout] parameter should be a property of Command
+// TODO(kustermann): Make tthis work with TestCaseRecorder/TestCaseReplayer
+
+
+class RecordingCommandExecutor implements CommandExecutor {
+  TestCaseRecorder _recorder;
+
+  RecordingCommandExecutor(io.Path path)
+      : _recorder = new TestCaseRecorder(path);
+
+  Future<CommandOutput> runCommand(node, Command command, int timeout) {
+    assert(node.dependencies.length == 0);
+    assert(command.environment == null);
+    _recorder.nextCommand(command, timeout);
+    // Return dummy CommandOutput
+    var output =
+        createCommandOutput(command, 0, false, [], [], const Duration(), false);
+    return new Future.value(output);
   }
 
-  void _tryRunTest() {
-    _checkDone();
-    // TODO(ricow): remove most of the hacked selenium code below when
-    // we have eliminated the need.
-
-    if (_numProcesses < _maxProcesses && !_tests.isEmpty) {
-      TestCase test = _tests.removeFirst();
-      if (_listTests) {
-        var fields = [test.displayName,
-                      test.expectedOutcomes.join(','),
-                      test.isNegative.toString()];
-        fields.addAll(test.commands.last.arguments);
-        print(fields.join('\t'));
-        return;
-      }
+  Future cleanup() {
+    _recorder.finish();
+    return new Future.value();
+  }
+}
 
-      if (test.usesWebDriver && _needsSelenium && !test.usesBrowserController
-          && !_isSeleniumAvailable ||
-          (test is BrowserTestCase && test.waitingForOtherTest)) {
-        // The test is not yet ready to run. Put the test back in
-        // the queue.  Avoid spin-polling by using a timeout.
-        _tests.add(test);
-        new Timer(new Duration(milliseconds: 100),
-                  _tryRunTest);  // Don't lose a process.
-        return;
-      }
-      // Before running any commands, we print out all commands if '--verbose'
-      // was specified.
-      if (_verbose && test.commandOutputs.length == 0) {
-        int i = 1;
-        if (test is BrowserTestCase) {
-          // Additional command for rerunning the steps locally after the fact.
-          var command =
-            test.configuration["_servers_"].httpServerCommandline();
-          print('$i. $command');
-          i++;
-        }
-        for (Command command in test.commands) {
-          print('$i. $command');
-          i++;
-        }
-      }
+class ReplayingCommandExecutor implements CommandExecutor {
+  TestCaseOutputArchive _archive = new TestCaseOutputArchive();
 
-      var isLastCommand =
-          ((test.commands.length-1) == test.commandOutputs.length);
-      var isBrowserCommand = isLastCommand && (test is BrowserTestCase);
-      if (isBrowserCommand && _numBrowserProcesses == _maxBrowserProcesses) {
-        // If there is no free browser runner, put it back into the queue.
-        _tests.add(test);
-        new Timer(new Duration(milliseconds: 100),
-                  _tryRunTest);  // Don't lose a process.
-        return;
-      }
+  ReplayingCommandExecutor(io.Path path) {
+    _archive.loadFromPath(path);
+  }
 
-      eventStartTestCase(test);
-
-      // Analyzer and browser test commands can be run by a [BatchRunnerProcess]
-      var nextCommandIndex = test.commandOutputs.keys.length;
-      var numberOfCommands = test.commands.length;
-
-      var useBatchRunnerForAnalyzer =
-          test.configuration['analyzer'] &&
-          test.displayName != 'dartc/junit_tests';
-      var isWebdriverCommand = nextCommandIndex == (numberOfCommands - 1) &&
-                               test.usesWebDriver &&
-                               !test.configuration['noBatch'];
-      if (useBatchRunnerForAnalyzer || isWebdriverCommand) {
-        TestCaseEvent oldCallback = test.completedHandler;
-        void testCompleted(TestCase test_arg) {
-          _numProcesses--;
-          if (isBrowserCommand) {
-            _numBrowserProcesses--;
-          }
-          eventFinishedTestCase(test_arg);
-          if (test_arg is BrowserTestCase) {
-            (test_arg as BrowserTestCase).notifyObservers();
-          }
-          oldCallback(test_arg);
-          _tryRunTest();
-        };
-        test.completedHandler = testCompleted;
-        if (test.usesBrowserController) {
-          _startBrowserControllerTest(test);
-        } else {
-          _getBatchRunner(test).startTest(test);
-        }
-      } else {
-        // Once we've actually failed a test, technically, we wouldn't need to
-        // bother retrying any subsequent tests since the bot is already red.
-        // However, we continue to retry tests until we have actually failed
-        // four tests (arbitrarily chosen) for more debugable output, so that
-        // the developer doesn't waste his or her time trying to fix a bunch of
-        // tests that appear to be broken but were actually just flakes that
-        // didn't get retried because there had already been one failure.
-        bool allowRetry = _MAX_FAILED_NO_RETRY > _numFailedTests;
-        runNextCommandWithRetries(test, allowRetry).then((TestCase testCase) {
-          _numProcesses--;
-          if (isBrowserCommand) {
-            _numBrowserProcesses--;
-          }
-          if (isTestCaseFinished(testCase)) {
-            testCase.completed();
-            eventFinishedTestCase(testCase);
-            if (testCase is BrowserTestCase) {
-              (testCase as BrowserTestCase).notifyObservers();
+  Future cleanup() => new Future.value();
+
+  Future<CommandOutput> runCommand(node, Command command, int timeout) {
+    assert(node.dependencies.length == 0);
+    return new Future.value(_archive.outputOf(command));
+  }
+}
+
+
+/*
+ * [TestCaseCompleter] will listen for
+ * NodeState.Processing -> NodeState.{Successfull,Failed} state changes and
+ * will complete a TestCase if it is finished.
+ *
+ * It provides a stream [finishedTestCases], which will stream all TestCases
+ * once they're finished. After all TestCases are done, the stream will be
+ * closed.
+ */
+class TestCaseCompleter {
+  static final COMPLETED_STATES = [dgraph.NodeState.Failed,
+                                   dgraph.NodeState.Successfull];
+  final dgraph.Graph graph;
+  final TestCaseEnqueuer enqueuer;
+  final CommandQueue commandQueue;
+
+  Map<Command, CommandOutput> _outputs = new Map<Command, CommandOutput>();
+  StreamController<TestCase> _controller = new StreamController<TestCase>();
+
+  TestCaseCompleter(this.graph, this.enqueuer, this.commandQueue) {
+    var eventCondition = graph.events.where;
+
+    // Store all the command outputs -- they will be delivered synchronously
+    // (i.e. before state changes in the graph)
+    commandQueue.completedCommands.listen((CommandOutput output) {
+      _outputs[output.command] = output;
+    });
+
+    // Listen for NodeState.Processing -> NodeState.{Successfull,Failed}
+    // changes.
+    eventCondition((event) => event is dgraph.StateChangedEvent)
+        .listen((dgraph.StateChangedEvent event) {
+          if (event.from == dgraph.NodeState.Processing) {
+            assert(COMPLETED_STATES.contains(event.to));
+            _completeTestCasesIfPossible(event.node.userData);
+
+            if (graph.isSealed && enqueuer.remainingTestCases.isEmpty) {
+              _controller.close();
             }
-          } else {
-            _tests.addFirst(testCase);
           }
-          _tryRunTest();
-        });
+    });
+  }
+
+  Stream<TestCase> get finishedTestCases => _controller.stream;
+
+  void _completeTestCasesIfPossible(Command command) {
+    assert(_outputs[command] != null);
+
+    var testCases = enqueuer.command2testCases[command];
+
+    // Update TestCases with command outputs
+    for (TestCase test in testCases) {
+      for (var icommand in test.commands) {
+        var output = _outputs[icommand];
+        if (output != null) {
+          test.commandOutputs[icommand] = output;
+        }
       }
+    }
 
-      _numProcesses++;
-      if (isBrowserCommand) {
-        _numBrowserProcesses++;
+    void completeTestCase(TestCase testCase) {
+      if (enqueuer.remainingTestCases.contains(testCase)) {
+        _controller.add(testCase);
+        enqueuer.remainingTestCases.remove(testCase);
+      } else {
+        DebugLogger.error("${testCase.displayName} would be finished twice");
       }
     }
-  }
 
-  bool isTestCaseFinished(TestCase testCase) {
-    var numberOfCommandOutputs = testCase.commandOutputs.keys.length;
-    var numberOfCommands = testCase.commands.length;
-
-    var lastCommandCompleted = (numberOfCommandOutputs == numberOfCommands);
-    var lastCommandOutput = testCase.lastCommandOutput;
-    var lastCommand = lastCommandOutput.command;
-    var timedOut = lastCommandOutput.hasTimedOut;
-    var nonZeroExitCode = lastCommandOutput.exitCode != 0;
-    // NOTE: If this was the last command or there was unexpected output
-    // we're done with the test.
-    // Otherwise we need to enqueue it again into the test queue.
-    if (lastCommandCompleted || timedOut || nonZeroExitCode) {
-      var verbose = testCase.configuration['verbose'];
-      if (lastCommandOutput.unexpectedOutput && verbose != null && verbose) {
-        print(testCase.displayName);
-        print("stderr:");
-        print(decodeUtf8(lastCommandOutput.stderr));
-        if (!lastCommand.isPixelTest) {
-          print("stdout:");
-          print(decodeUtf8(lastCommandOutput.stdout));
-        } else {
-          print("");
-          print("DRT pixel test failed! stdout is not printed because it "
-                "contains binary data!");
-        }
+    for (var testCase in testCases) {
+      // Ask the [testCase] if it's done. Note that we assume, that
+      // [TestCase.isFinished] will return true if all commands were executed
+      // or if a previous one failed.
+      if (testCase.isFinished) {
+        completeTestCase(testCase);
       }
-      return true;
-    } else {
-      return false;
     }
   }
+}
+
 
-  Future runNextCommandWithRetries(TestCase testCase, bool allowRetry) {
-    var completer = new Completer();
 
-    var nextCommandIndex = testCase.commandOutputs.keys.length;
-    var numberOfCommands = testCase.commands.length;
-    if (nextCommandIndex >= numberOfCommands) {
-      throw "nextCommandIndex must be less than numberOfCommands";
+class ProcessQueue {
+  Map _globalConfiguration;
+
+  bool _allTestsWereEnqueued = false;
+
+  bool _verbose;
+  bool _listTests;
+  Function _allDone;
+  final dgraph.Graph _graph = new dgraph.Graph();
+  List<EventListener> _eventListener;
+
+  ProcessQueue(this._globalConfiguration,
+               maxProcesses,
+               maxBrowserProcesses,
+               DateTime startTime,
+               testSuites,
+               this._eventListener,
+               this._allDone,
+               [this._verbose = false,
+                this._listTests = false,
+                String recordingOutputFile,
+                String recordedInputFile]) {
+    bool recording = recordingOutputFile != null;
+    bool replaying = recordedInputFile != null;
+
+    // When the graph building is finished, notify event listeners.
+    _graph.events
+      .where((event) => event is dgraph.GraphSealedEvent).listen((event) {
+        eventAllTestsKnown();
+    });
+
+    // Build up the dependency graph
+    var testCaseEnqueuer = new TestCaseEnqueuer(_graph, (TestCase newTestCase) {
+      eventTestAdded(newTestCase);
+    });
+
+    // Queue commands as they become "runnable"
+    var commandEnqueuer = new CommandEnqueuer(_graph);
+
+    // CommandExecutor will execute commands
+    var executor;
+    if (recording) {
+      executor = new RecordingCommandExecutor(new io.Path(recordingOutputFile));
+    } else if (replaying) {
+      executor = new ReplayingCommandExecutor(new io.Path(recordedInputFile));
+    } else {
+      executor = new CommandExecutorImpl(
+          _globalConfiguration, maxProcesses, maxBrowserProcesses);
     }
-    var command = testCase.commands[nextCommandIndex];
-    var isLastCommand = nextCommandIndex == (numberOfCommands - 1);
-
-    void runCommand() {
-      var runningProcess = new RunningProcess(testCase, command);
-      runningProcess.start().then((CommandOutput commandOutput) {
-        if (isLastCommand) {
-          // NOTE: We need to call commandOutput.unexpectedOutput here.
-          // Calling this getter may result in the side-effect, that
-          // commandOutput.requestRetry is set to true.
-          // (BrowserCommandOutputImpl._failedBecauseOfMissingXDisplay
-          // does that for example)
-          // TODO(ricow/kustermann): Issue 8206
-          var unexpectedOutput = commandOutput.unexpectedOutput;
-          if (unexpectedOutput && allowRetry) {
-            if (testCase.usesWebDriver
-                && (testCase as BrowserTestCase).numRetries > 0) {
-              // Selenium tests can be flaky. Try rerunning.
-              commandOutput.requestRetry = true;
-            }
-            // FIXME(kustermann): Remove this condition once we figured out why
-            // content_shell is sometimes not able to fetch resources from the
-            // HttpServer.
-            var configuration  = testCase.configuration;
-            if (configuration['runtime'] == 'drt' &&
-                configuration['system'] == 'windows' &&
-                (testCase as BrowserTestCase).numRetries > 0) {
-              assert(TestUtils.isBrowserRuntime(configuration['runtime']));
-              commandOutput.requestRetry = true;
-            }
-          }
-        }
-        if (commandOutput.requestRetry) {
-          commandOutput.requestRetry = false;
-          (testCase as BrowserTestCase).numRetries--;
-          DebugLogger.warning("Rerunning Test: ${testCase.displayName} "
-                              "(${(testCase as BrowserTestCase).numRetries} "
-                              "attempt(s) remains) [cmd:$command]");
-          runCommand();
-        } else {
-          completer.complete(testCase);
+
+    // Run "runnable commands" using [executor] subject to
+    // maxProcesses/maxBrowserProcesses constraint
+    var commandQueue = new CommandQueue(
+        _graph, testCaseEnqueuer, executor, maxProcesses, maxBrowserProcesses);
+
+    // Finish test cases when all commands were run (or some failed)
+    var testCaseCompleter =
+        new TestCaseCompleter(_graph, testCaseEnqueuer, commandQueue);
+    testCaseCompleter.finishedTestCases.listen(
+      (TestCase finishedTestCase) {
+        // If we're recording, we don't report any TestCases to listeners.
+        if (!recording) {
+          eventFinishedTestCase(finishedTestCase);
         }
+      },
+      onDone: () {
+        // Wait until the commandQueue/execturo is done (it may need to stop
+        // batch runners, browser controllers, ....)
+        commandQueue.done.then((_) => eventAllTestsDone());
       });
-    }
-    runCommand();
 
-    return completer.future;
-  }
-
-  void eventStartTestCase(TestCase testCase) {
-    for (var listener in _eventListener) {
-      listener.start(testCase);
-    }
+    // Start enqueing all TestCases
+    testCaseEnqueuer.enqueueTestSuites(testSuites);
   }
 
   void eventFinishedTestCase(TestCase testCase) {
-    if (testCase.lastCommandOutput.unexpectedOutput) {
-      _numFailedTests++;
-    }
     for (var listener in _eventListener) {
       listener.done(testCase);
     }
@@ -1931,6 +2041,38 @@ class ProcessQueue {
     for (var listener in _eventListener) {
       listener.allDone();
     }
+    _allDone();
   }
 }
 
+
+
+/*

[ricow1, 2013/07/30 09:30:11]

commented out

[kustermann, 2013/07/31 15:53:54]

Done.

+// FIXME(kustermann): This is completely broken, why only printing
+// the last command, WTF?
+if (_listTests) {
+var fields = [test.displayName,
+test.expectedOutcomes.join(','),
+test.isNegative.toString()];
+fields.addAll(test.commands.last.arguments);
+print(fields.join('\t'));
+return;
+}
+
+// FIXME(kustermann): This is somewhat broken as well. We should print
+// these commands when doing "--verbose --list" or something like that.
+if (_verbose && test.commandOutputs.length == 0) {
+int i = 1;
+if (test is BrowserTestCase) {
+// Additional command for rerunning the steps locally after the fact.
+var command =
+test.configuration["_servers_"].httpServerCommandline();
+print('$i. $command');
+i++;
+}
+for (Command command in test.commands) {
+print('$i. $command');
+i++;
+}
+}
+*/