std.Build: simplify module dependency handling

At the expense of a slight special case in the build runner, we can make
the handling of dependencies between modules a little shorter and much
easier to follow.

When module and step graphs are being constructed during the "configure"
phase, we do not set up step dependencies triggered by modules. Instead,
after the configure phase, the build runner traverses the whole
step/module graph, starting from the root top-level steps, and
configures all step dependencies implied by modules. The "make" phase
then proceeds as normal. Also, the old `Module.dependencyIterator` logic
is replaced by two separate iterables. `Module.getGraph` takes the root
module of a compilation, and returns all modules in its graph; while
`Step.Compile.getCompileDependencies` takes a `*Step.Compile` and
returns all `*Step.Compile` it depends on, recursively, possibly
excluding dynamic libraries. The old `Module.dependencyIterator`
combined these two functions into one unintuitive iterator; they are now
separated, which in particular helps readability at the usage sites
which only need one or the other.

1 files changed, 45 insertions, 182 deletions

diff --git a/lib/std/Build/Module.zig b/lib/std/Build/Module.zig
index 629d90dd0f..1f2b4f3fcb 100644
--- a/lib/std/Build/Module.zig
+++ b/lib/std/Build/Module.zig
@@ -1,9 +1,5 @@
 /// The one responsible for creating this module.
 owner: *std.Build,
-/// Tracks the set of steps that depend on this `Module`. This ensures that
-/// when making this `Module` depend on other `Module` objects and `Step`
-/// objects, respective `Step` dependencies can be added.
-depending_steps: std.AutoArrayHashMapUnmanaged(*Step.Compile, void),
 root_source_file: ?LazyPath,
 /// The modules that are mapped into this module's import table.
 /// Use `addImport` rather than modifying this field directly in order to
@@ -41,6 +37,10 @@ link_libcpp: ?bool,
 /// Symbols to be exported when compiling to WebAssembly.
 export_symbol_names: []const []const u8 = &.{},
 
+/// Caches the result of `getGraph` when called multiple times.
+/// Use `getGraph` instead of accessing this field directly.
+cached_graph: Graph = .{ .modules = &.{}, .names = &.{} },
+
 pub const RPath = union(enum) {
     lazy_path: LazyPath,
     special: []const u8,
@@ -246,7 +246,6 @@ pub fn init(
     m: *Module,
     owner: *std.Build,
     value: union(enum) { options: CreateOptions, existing: *const Module },
-    compile: ?*Step.Compile,
 ) void {
     const allocator = owner.allocator;
 
@@ -254,7 +253,6 @@ pub fn init(
         .options => |options| {
             m.* = .{
                 .owner = owner,
-                .depending_steps = .{},
                 .root_source_file = if (options.root_source_file) |lp| lp.dupe(owner) else null,
                 .import_table = .{},
                 .resolved_target = options.target,
@@ -294,19 +292,11 @@ pub fn init(
             m.* = existing.*;
         },
     }
-
-    if (compile) |c| {
-        m.depending_steps.put(allocator, c, {}) catch @panic("OOM");
-    }
-
-    // This logic accesses `depending_steps` which was just modified above.
-    var it = m.iterateDependencies(null, false);
-    while (it.next()) |item| addShallowDependencies(m, item.module);
 }
 
 pub fn create(owner: *std.Build, options: CreateOptions) *Module {
     const m = owner.allocator.create(Module) catch @panic("OOM");
-    m.init(owner, .{ .options = options }, null);
+    m.init(owner, .{ .options = options });
     return m;
 }
 
@@ -314,69 +304,6 @@ pub fn create(owner: *std.Build, options: CreateOptions) *Module {
 pub fn addImport(m: *Module, name: []const u8, module: *Module) void {
     const b = m.owner;
     m.import_table.put(b.allocator, b.dupe(name), module) catch @panic("OOM");
-
-    var it = module.iterateDependencies(null, false);
-    while (it.next()) |item| addShallowDependencies(m, item.module);
-}
-
-/// Creates step dependencies and updates `depending_steps` of `dependee` so that
-/// subsequent calls to `addImport` on `dependee` will additionally create step
-/// dependencies on `m`'s `depending_steps`.
-fn addShallowDependencies(m: *Module, dependee: *Module) void {
-    if (dependee.root_source_file) |lazy_path| addLazyPathDependencies(m, dependee, lazy_path);
-    for (dependee.lib_paths.items) |lib_path| addLazyPathDependencies(m, dependee, lib_path);
-    for (dependee.rpaths.items) |rpath| switch (rpath) {
-        .lazy_path => |lp| addLazyPathDependencies(m, dependee, lp),
-        .special => {},
-    };
-
-    for (dependee.link_objects.items) |link_object| switch (link_object) {
-        .other_step => |compile| {
-            addStepDependencies(m, dependee, &compile.step);
-            addLazyPathDependenciesOnly(m, compile.getEmittedIncludeTree());
-        },
-
-        .static_path,
-        .assembly_file,
-        => |lp| addLazyPathDependencies(m, dependee, lp),
-
-        .c_source_file => |x| addLazyPathDependencies(m, dependee, x.file),
-        .win32_resource_file => |x| addLazyPathDependencies(m, dependee, x.file),
-
-        .c_source_files,
-        .system_lib,
-        => {},
-    };
-}
-
-fn addLazyPathDependencies(m: *Module, module: *Module, lazy_path: LazyPath) void {
-    addLazyPathDependenciesOnly(m, lazy_path);
-    if (m != module) {
-        for (m.depending_steps.keys()) |compile| {
-            module.depending_steps.put(m.owner.allocator, compile, {}) catch @panic("OOM");
-        }
-    }
-}
-
-fn addLazyPathDependenciesOnly(m: *Module, lazy_path: LazyPath) void {
-    for (m.depending_steps.keys()) |compile| {
-        lazy_path.addStepDependencies(&compile.step);
-    }
-}
-
-fn addStepDependencies(m: *Module, module: *Module, dependee: *Step) void {
-    addStepDependenciesOnly(m, dependee);
-    if (m != module) {
-        for (m.depending_steps.keys()) |compile| {
-            module.depending_steps.put(m.owner.allocator, compile, {}) catch @panic("OOM");
-        }
-    }
-}
-
-fn addStepDependenciesOnly(m: *Module, dependee: *Step) void {
-    for (m.depending_steps.keys()) |compile| {
-        compile.step.dependOn(dependee);
-    }
 }
 
 /// Creates a new module and adds it to be used with `@import`.
@@ -392,91 +319,6 @@ pub fn addOptions(m: *Module, module_name: []const u8, options: *Step.Options) v
     addImport(m, module_name, options.createModule());
 }
 
-pub const DependencyIterator = struct {
-    allocator: std.mem.Allocator,
-    index: usize,
-    set: std.AutoArrayHashMapUnmanaged(Key, []const u8),
-    chase_dyn_libs: bool,
-
-    pub const Key = struct {
-        /// The compilation that contains the `Module`. Note that a `Module` might be
-        /// used by more than one compilation.
-        compile: ?*Step.Compile,
-        module: *Module,
-    };
-
-    pub const Item = struct {
-        /// The compilation that contains the `Module`. Note that a `Module` might be
-        /// used by more than one compilation.
-        compile: ?*Step.Compile,
-        module: *Module,
-        name: []const u8,
-    };
-
-    pub fn deinit(it: *DependencyIterator) void {
-        it.set.deinit(it.allocator);
-        it.* = undefined;
-    }
-
-    pub fn next(it: *DependencyIterator) ?Item {
-        if (it.index >= it.set.count()) {
-            it.set.clearAndFree(it.allocator);
-            return null;
-        }
-        const key = it.set.keys()[it.index];
-        const name = it.set.values()[it.index];
-        it.index += 1;
-        const module = key.module;
-        it.set.ensureUnusedCapacity(it.allocator, module.import_table.count()) catch
-            @panic("OOM");
-        for (module.import_table.keys(), module.import_table.values()) |dep_name, dep| {
-            it.set.putAssumeCapacity(.{
-                .module = dep,
-                .compile = key.compile,
-            }, dep_name);
-        }
-
-        if (key.compile != null) {
-            for (module.link_objects.items) |link_object| switch (link_object) {
-                .other_step => |compile| {
-                    if (!it.chase_dyn_libs and compile.isDynamicLibrary()) continue;
-
-                    it.set.put(it.allocator, .{
-                        .module = compile.root_module,
-                        .compile = compile,
-                    }, "root") catch @panic("OOM");
-                },
-                else => {},
-            };
-        }
-
-        return .{
-            .compile = key.compile,
-            .module = key.module,
-            .name = name,
-        };
-    }
-};
-
-pub fn iterateDependencies(
-    m: *Module,
-    chase_steps: ?*Step.Compile,
-    chase_dyn_libs: bool,
-) DependencyIterator {
-    var it: DependencyIterator = .{
-        .allocator = m.owner.allocator,
-        .index = 0,
-        .set = .{},
-        .chase_dyn_libs = chase_dyn_libs,
-    };
-    it.set.ensureUnusedCapacity(m.owner.allocator, m.import_table.count() + 1) catch @panic("OOM");
-    it.set.putAssumeCapacity(.{
-        .module = m,
-        .compile = chase_steps,
-    }, "root");
-    return it;
-}
-
 pub const LinkSystemLibraryOptions = struct {
     /// Causes dynamic libraries to be linked regardless of whether they are
     /// actually depended on. When false, dynamic libraries with no referenced
@@ -559,7 +401,6 @@ pub fn addCSourceFiles(m: *Module, options: AddCSourceFilesOptions) void {
         .flags = b.dupeStrings(options.flags),
     };
     m.link_objects.append(allocator, .{ .c_source_files = c_source_files }) catch @panic("OOM");
-    addLazyPathDependenciesOnly(m, c_source_files.root);
 }
 
 pub fn addCSourceFile(m: *Module, source: CSourceFile) void {
@@ -568,7 +409,6 @@ pub fn addCSourceFile(m: *Module, source: CSourceFile) void {
     const c_source_file = allocator.create(CSourceFile) catch @panic("OOM");
     c_source_file.* = source.dupe(b);
     m.link_objects.append(allocator, .{ .c_source_file = c_source_file }) catch @panic("OOM");
-    addLazyPathDependenciesOnly(m, source.file);
 }
 
 /// Resource files must have the extension `.rc`.
@@ -585,22 +425,16 @@ pub fn addWin32ResourceFile(m: *Module, source: RcSourceFile) void {
     const rc_source_file = allocator.create(RcSourceFile) catch @panic("OOM");
     rc_source_file.* = source.dupe(b);
     m.link_objects.append(allocator, .{ .win32_resource_file = rc_source_file }) catch @panic("OOM");
-    addLazyPathDependenciesOnly(m, source.file);
-    for (source.include_paths) |include_path| {
-        addLazyPathDependenciesOnly(m, include_path);
-    }
 }
 
 pub fn addAssemblyFile(m: *Module, source: LazyPath) void {
     const b = m.owner;
     m.link_objects.append(b.allocator, .{ .assembly_file = source.dupe(b) }) catch @panic("OOM");
-    addLazyPathDependenciesOnly(m, source);
 }
 
 pub fn addObjectFile(m: *Module, object: LazyPath) void {
     const b = m.owner;
     m.link_objects.append(b.allocator, .{ .static_path = object.dupe(b) }) catch @panic("OOM");
-    addLazyPathDependenciesOnly(m, object);
 }
 
 pub fn addObject(m: *Module, object: *Step.Compile) void {
@@ -616,51 +450,43 @@ pub fn linkLibrary(m: *Module, library: *Step.Compile) void {
 pub fn addAfterIncludePath(m: *Module, lazy_path: LazyPath) void {
     const b = m.owner;
     m.include_dirs.append(b.allocator, .{ .path_after = lazy_path.dupe(b) }) catch @panic("OOM");
-    addLazyPathDependenciesOnly(m, lazy_path);
 }
 
 pub fn addSystemIncludePath(m: *Module, lazy_path: LazyPath) void {
     const b = m.owner;
     m.include_dirs.append(b.allocator, .{ .path_system = lazy_path.dupe(b) }) catch @panic("OOM");
-    addLazyPathDependenciesOnly(m, lazy_path);
 }
 
 pub fn addIncludePath(m: *Module, lazy_path: LazyPath) void {
     const b = m.owner;
     m.include_dirs.append(b.allocator, .{ .path = lazy_path.dupe(b) }) catch @panic("OOM");
-    addLazyPathDependenciesOnly(m, lazy_path);
 }
 
 pub fn addConfigHeader(m: *Module, config_header: *Step.ConfigHeader) void {
     const allocator = m.owner.allocator;
     m.include_dirs.append(allocator, .{ .config_header_step = config_header }) catch @panic("OOM");
-    addStepDependenciesOnly(m, &config_header.step);
 }
 
 pub fn addSystemFrameworkPath(m: *Module, directory_path: LazyPath) void {
     const b = m.owner;
     m.include_dirs.append(b.allocator, .{ .framework_path_system = directory_path.dupe(b) }) catch
         @panic("OOM");
-    addLazyPathDependenciesOnly(m, directory_path);
 }
 
 pub fn addFrameworkPath(m: *Module, directory_path: LazyPath) void {
     const b = m.owner;
     m.include_dirs.append(b.allocator, .{ .framework_path = directory_path.dupe(b) }) catch
         @panic("OOM");
-    addLazyPathDependenciesOnly(m, directory_path);
 }
 
 pub fn addLibraryPath(m: *Module, directory_path: LazyPath) void {
     const b = m.owner;
     m.lib_paths.append(b.allocator, directory_path.dupe(b)) catch @panic("OOM");
-    addLazyPathDependenciesOnly(m, directory_path);
 }
 
 pub fn addRPath(m: *Module, directory_path: LazyPath) void {
     const b = m.owner;
     m.rpaths.append(b.allocator, .{ .lazy_path = directory_path.dupe(b) }) catch @panic("OOM");
-    addLazyPathDependenciesOnly(m, directory_path);
 }
 
 pub fn addRPathSpecial(m: *Module, bytes: []const u8) void {
@@ -784,7 +610,6 @@ fn addFlag(
 fn linkLibraryOrObject(m: *Module, other: *Step.Compile) void {
     const allocator = m.owner.allocator;
     _ = other.getEmittedBin(); // Indicate there is a dependency on the outputted binary.
-    addStepDependenciesOnly(m, &other.step);
 
     if (other.rootModuleTarget().os.tag == .windows and other.isDynamicLibrary()) {
         _ = other.getEmittedImplib(); // Indicate dependency on the outputted implib.
@@ -792,8 +617,6 @@ fn linkLibraryOrObject(m: *Module, other: *Step.Compile) void {
 
     m.link_objects.append(allocator, .{ .other_step = other }) catch @panic("OOM");
     m.include_dirs.append(allocator, .{ .other_step = other }) catch @panic("OOM");
-
-    addLazyPathDependenciesOnly(m, other.getEmittedIncludeTree());
 }
 
 fn requireKnownTarget(m: *Module) std.Target {
@@ -802,6 +625,46 @@ fn requireKnownTarget(m: *Module) std.Target {
     return resolved_target.result;
 }
 
+/// Elements of `modules` and `names` are matched one-to-one.
+pub const Graph = struct {
+    modules: []const *Module,
+    names: []const []const u8,
+};
+
+/// Intended to be used during the make phase only.
+///
+/// Given that `root` is the root `Module` of a compilation, return all `Module`s
+/// in the module graph, including `root` itself. `root` is guaranteed to be the
+/// first module in the returned slice.
+pub fn getGraph(root: *Module) Graph {
+    if (root.cached_graph.modules.len != 0) {
+        return root.cached_graph;
+    }
+
+    const arena = root.owner.graph.arena;
+
+    var modules: std.AutoArrayHashMapUnmanaged(*std.Build.Module, []const u8) = .empty;
+    var next_idx: usize = 0;
+
+    modules.putNoClobber(arena, root, "root") catch @panic("OOM");
+
+    while (next_idx < modules.count()) {
+        const mod = modules.keys()[next_idx];
+        next_idx += 1;
+        modules.ensureUnusedCapacity(arena, mod.import_table.count()) catch @panic("OOM");
+        for (mod.import_table.keys(), mod.import_table.values()) |import_name, other_mod| {
+            modules.putAssumeCapacity(other_mod, import_name);
+        }
+    }
+
+    const result: Graph = .{
+        .modules = modules.keys(),
+        .names = modules.values(),
+    };
+    root.cached_graph = result;
+    return result;
+}
+
 const Module = @This();
 const std = @import("std");
 const assert = std.debug.assert;