build runner: proper threaded dependency management

After sorting the step stack so that dependencies can be popped before
their dependants are popped, there is still a situation left to handle
correctly:

Example:

A depends on:
  B
  C
D depends on:
  E
  F

They will be ordered like this:

A B C D E F

If there are 6+ cores, then all of them will be evaluated at once,
incorrectly evaluating A and D before their dependencies.

Starting evaluation of F and then E is correct, but waiting until they
are done is not correct because it should start working on B and C as
well.

This commit solves the problem by computing dependants in the dependency
loop checking logic, and then having workers queue up their dependants
when they finish their own work.

1 files changed, 20 insertions, 11 deletions

diff --git a/lib/std/Build/Step.zig b/lib/std/Build/Step.zig
index a22ea04754..1226c78c73 100644
--- a/lib/std/Build/Step.zig
+++ b/lib/std/Build/Step.zig
@@ -2,16 +2,25 @@ id: Id,
 name: []const u8,
 makeFn: *const fn (self: *Step) anyerror!void,
 dependencies: std.ArrayList(*Step),
-/// Used only during a pre-check for dependency loops.
-loop_tag: enum { unstarted, started, done },
-result: union(enum) {
-    not_done,
-    success,
-    failure: struct {
-        err_code: anyerror,
-    },
+/// This field is empty during execution of the user's build script, and
+/// then populated during dependency loop checking in the build runner.
+dependants: std.ArrayListUnmanaged(*Step),
+state: State,
+/// Populated only if state is success.
+result: struct {
+    err_code: anyerror,
 },
 
+pub const State = enum {
+    precheck_unstarted,
+    precheck_started,
+    precheck_done,
+    running,
+    dependency_failure,
+    success,
+    failure,
+};
+
 pub const Id = enum {
     top_level,
     compile,
@@ -67,8 +76,9 @@ pub fn init(
         .name = allocator.dupe(u8, name) catch @panic("OOM"),
         .makeFn = makeFn,
         .dependencies = std.ArrayList(*Step).init(allocator),
-        .loop_tag = .unstarted,
-        .result = .not_done,
+        .dependants = .{},
+        .state = .precheck_unstarted,
+        .result = undefined,
     };
 }
 
@@ -77,7 +87,6 @@ pub fn initNoOp(id: Id, name: []const u8, allocator: Allocator) Step {
 }
 
 pub fn make(self: *Step) !void {
-    assert(self.result == .not_done);
     try self.makeFn(self);
 }