Zig 0.17.0-dev (Split by item)

This is an example of documentation generated by ZigDoc, an alternative to Zig's built-in Auto Doc feature. See also examples in other modes/formats. The project being documented here (as the example) is the Zig library itself.

constructGraphAndCheckForDependencyLoop

Traverse the dependency graph depth-first and make it undirected by having steps know their dependants (they only know dependencies at start). Along the way, check that there is no dependency loop, and record the steps in traversal order in step_stack. Each step has its dependencies traversed in random order, this accomplishes two things:

step_stack will be in randomized-depth-first order, so the build runner spawns initial steps in a random order
each step's dependants list is also filled in a random order, so that when it finishes executing in makeStep, it spawns next steps to run in random order

Maker.constructGraphAndCheckForDependencyLoop

fn constructGraphAndCheckForDependencyLoop(
    maker: *Maker,
    step_index: Configuration.Step.Index,
    step_stack: *std.array_hash_map.Auto(Configuration.Step.Index, void),
    rand: std.Random,
) error

File

lib/compiler/Maker.zig:2779

Code

fn constructGraphAndCheckForDependencyLoop(
    maker: *Maker,
    step_index: Configuration.Step.Index,
    step_stack: *std.array_hash_map.Auto(Configuration.Step.Index, void),
    rand: std.Random,
) error{ DependencyLoopDetected, OutOfMemory }!void {
    const c = &maker.scanned_config.configuration;
    const gpa = maker.gpa;
    const arena = maker.graph.arena;
    const make_step = maker.stepByIndex(step_index);
    switch (make_step.state) {
        .precheck_started => {
            log.err("dependency loop detected: {s}", .{step_index.ptr(c).name.slice(c)});
            return error.DependencyLoopDetected;
        },
        .precheck_unstarted => {
            make_step.state = .precheck_started;

            const step = step_index.ptr(c);
            const dependencies = step.deps.slice(c);
            try step_stack.ensureUnusedCapacity(gpa, dependencies.len);

            // We dupe to avoid shuffling the steps in the summary, it depends
            // on dependencies' order.
            const deps = try gpa.dupe(Configuration.Step.Index, dependencies);
            defer gpa.free(deps);

            rand.shuffle(Configuration.Step.Index, deps);

            for (deps) |dep| {
                const dep_step = maker.stepByIndex(dep);
                try step_stack.put(gpa, dep, {});
                try dep_step.dependants.append(arena, step_index);
                constructGraphAndCheckForDependencyLoop(maker, dep, step_stack, rand) catch |err| switch (err) {
                    error.DependencyLoopDetected => {
                        log.info("needed by: {s}", .{step_index.ptr(c).name.slice(c)});
                        return err;
                    },
                    else => return err,
                };
            }

            make_step.state = .precheck_done;
            make_step.pending_deps = @intCast(dependencies.len);
        },
        .precheck_done => {},

        // These don't happen until we actually run the step graph.
        .dependency_failure => unreachable,
        .success => unreachable,
        .failure => unreachable,
        .skipped => unreachable,
        .skipped_oom => unreachable,
    }
}