Implement fine-grained conflict handling

Tests can specify conflict keys, either in --CONFLICTS-- or
a per-directory CONFLICTS file. Non-conflicting tests may be run
in parallel.

1 files changed, 68 insertions, 70 deletions

diff --git a/run-tests.php b/run-tests.php
index b9e14f373c..3221766c1a 100755
--- a/run-tests.php
+++ b/run-tests.php
@@ -1348,73 +1348,37 @@ function run_all_tests_parallel($test_files, $env, $redir_tested) {
 	echo "====⚡️==== WELCOME TO THE FUTURE: run-tests PARALLEL EDITION ====⚡️====\n";
 	echo "====⚡️===========================================================⚡️====\n";
 
-	// Because some of the PHP test suite has not been written with
-	// parallel execution in mind, it is not safe to just run any two tests
-	// concurrently.
-	// Therefore, we divide the test set into directories and test multiple
-	// directories at once, but not multiple tests within them.
-
-	$testDirsToGo = [];
-
+	// Each test may specify a list of conflict keys. While a test that conflicts with
+	// key K is running, no other test that conflicts with K may run. Conflict keys are
+	// specified either in the --CONFLICTS-- section, or CONFLICTS file inside a directory.
+	$dirConflictsWith = [];
+	$fileConflictsWith = [];
 	foreach ($test_files as $file) {
-		$dirSeparator = strrpos($file, DIRECTORY_SEPARATOR);
-		if ($dirSeparator !== FALSE) {
-			$testDirsToGo[substr($file, 0, $dirSeparator)][] = $file;
+		$contents = file_get_contents($file);
+		if (preg_match('/^--CONFLICTS--(.+?)^--/ms', $contents, $matches)) {
+			$conflicts = array_map('trim', explode("\n", trim($matches[1])));
 		} else {
-			$testDirsToGo[""][] = $file;
-		}
-	}
-
-	// We assume most test directories should be executed in serial, but for
-	// big directories, this would waste time if they can actually be parallel.
-	// Therefore, if a directory has a special '@CAN_BE_PARALLELISED' file, we
-	// will divide it up into smaller “directories” automatically.
-	foreach ($testDirsToGo as $dir => $tests) {
-		if (count($tests) < 64 || !is_string($dir)) {
-			continue;
-		}
-		if (file_exists($dir . DIRECTORY_SEPARATOR . '@CAN_BE_PARALLELISED')) {
-			foreach (array_chunk($tests, 64) as $testsChunk) {
-				$testDirsToGo[] = $testsChunk;
+			// Cache per-directory conflicts in a separate map, so we compute these only once.
+			$dir = dirname($file);
+			if (!isset($dirConflictsWith[$dir])) {
+				$dirConflicts = [];
+				if (file_exists($dir . '/CONFLICTS')) {
+					$contents = file_get_contents($dir . '/CONFLICTS');
+					$dirConflicts = array_map('trim', explode("\n", trim($contents)));
+				}
+				$dirConflictsWith[$dir] = $dirConflicts;
 			}
-			unset($testDirsToGo[$dir]);
+			$conflicts = $dirConflictsWith[$dir];
 		}
-	}
-
-	// Sort test dirs so the biggest ones are handled first, so we spend less
-	// time waiting on workers tasked with very large dirs.
-	// This is an ascending sort because items are popped off the end.
-	// Thank you Rasmus for this idea :)
-	uasort($testDirsToGo, function ($a, $b) {
-		return count($a) <=> count($b);
-	});
-
-	$testDirsInProgress = 0;
-
-	echo "Isolated ", count($testDirsToGo), " directories to be tested in parallel.\n";
-
-	$shamedDirs = array_reverse(array_filter($testDirsToGo, function ($files) {
-		return count($files) > 100;
-	}), true);
 
-	if ($shamedDirs) {
-		$shameList = "";
-		foreach ($shamedDirs as $dir => $shame) {
-			$shameList .= "\n$dir: " .  count($shame) . " files";
-		}
-
-		echo <<<NAME_AND_SHAME
-----⚠️-----------------------------------------------------------⚠️----
-To effectively utilise parallelism, test directories should not contain
-large numbers of tests that can't be run simultaneously. The following
-directories contain more than 100 test files and do not contain a
-'@CAN_BE_PARALLELISED' file:
-$shameList
-----⚠️-----------------------------------------------------------⚠️----
-
-NAME_AND_SHAME;
+		$fileConflictsWith[$file] = $conflicts;
 	}
 
+	// Some tests assume that they are executed in a certain order. We will be popping from
+	// $test_files, so reverse its order here. This makes sure that order is preserved at least
+	// for tests with a common conflict key.
+	$test_files = array_reverse($test_files);
+
 	echo "Spawning workers… ";
 
 	// We use sockets rather than STDIN/STDOUT for comms because on Windows,
@@ -1500,9 +1464,15 @@ NAME_AND_SHAME;
 	echo "\n";
 
 	$rawMessageBuffers = [];
+	$testsInProgress = 0;
+
+	// Map from conflict key to worker ID.
+	$activeConflicts = [];
+	// Tests waiting due to conflicts. Map from conflict key to array.
+	$waitingTests = [];
 
 escape:
-	while ($testDirsToGo || ($testDirsInProgress > 0)) {
+	while ($test_files || $testsInProgress > 0) {
 		$toRead = array_values($workerSocks);
 		$toWrite = NULL;
 		$toExcept = NULL;
@@ -1532,15 +1502,43 @@ escape:
 					}
 
 					switch ($message["type"]) {
-						case "dir_finished":
-							$testDirsInProgress--;
+						case "tests_finished":
+							$testsInProgress--;
+							foreach ($activeConflicts as $key => $workerId) {
+								if ($workerId === $i) {
+									unset($activeConflicts[$key]);
+									if (isset($waitingTests[$key])) {
+										while ($test = array_pop($waitingTests[$key])) {
+											$test_files[] = $test;
+										}
+										unset($waitingTests[$key]);
+									}
+								}
+							}
 							// intentional fall-through
 						case "ready":
-							if ($testDir = array_pop($testDirsToGo)) {
-								$testDirsInProgress++;
+							// Batch multiple tests to reduce communication overhead.
+							$files = [];
+							$batchSize = 32;
+							while (count($files) <= $batchSize && $file = array_pop($test_files)) {
+								foreach ($fileConflictsWith[$file] as $conflictKey) {
+									if (isset($activeConflicts[$conflictKey])) {
+										$waitingTests[$conflictKey][] = $file;
+										continue 2;
+									}
+								}
+								$files[] = $file;
+							}
+							if ($files) {
+								foreach ($files as $file) {
+									foreach ($fileConflictsWith[$file] as $conflictKey) {
+										$activeConflicts[$conflictKey] = $i;
+									}
+								}
+								$testsInProgress++;
 								send_message($workerSocks[$i], [
 									"type" => "run_tests",
-									"test_files" => $testDir,
+									"test_files" => $files,
 									"env" => $env,
 									"redir_tested" => $redir_tested
 								]);
@@ -1609,8 +1607,8 @@ escape:
 
 	kill_children($workerProcs);
 
-	if ($testDirsInProgress < 0) {
-		error("$testDirsInProgress test directories “in progress”, which is less than zero. THIS SHOULD NOT HAPPEN.");
+	if ($testsInProgress < 0) {
+		error("$testsInProgress test batches “in progress”, which is less than zero. THIS SHOULD NOT HAPPEN.");
 	}
 }
 
@@ -1677,7 +1675,7 @@ function run_worker() {
 			case "run_tests":
 				run_all_tests($command["test_files"], $command["env"], $command["redir_tested"]);
 				send_message($workerSock, [
-					"type" => "dir_finished"
+					"type" => "tests_finished"
 				]);
 				break;
 			default:
@@ -1793,7 +1791,7 @@ TEST $file
 				'CAPTURE_STDIO', 'STDIN', 'CGI', 'PHPDBG',
 				'INI', 'ENV', 'EXTENSIONS',
 				'SKIPIF', 'XFAIL', 'CLEAN',
-				'CREDITS', 'DESCRIPTION',
+				'CREDITS', 'DESCRIPTION', 'CONFLICTS',
 			))) {
 				$bork_info = 'Unknown section "' . $section . '"';
 			}