Support outputting derivations in groups of layers for optimal concurrent builds?

[arianvp]

Given some release.nix it'd be useful if nix-eval-jobs could group derivations in layers such that each layer can build all its members in parallel.

This can then be translated to generate optimal CI pipelines.

[
  {
    "layer": 1,
    "derivations": [
      {
        "name": "erofs-utils-1.8.5",
        "drvPath": "/nix/store/ya02c5b2gihfkv0wkzkl4li497ibcksi-erofs-utils-1.8.5.drv",
        "attr": "erofs-utils"
      },
      {
        "name": "linux-6.13.3",
        "drvPath": "/nix/store/bp18vwdqiszljm9jdvx9sdb2c2r0pp4k-linux-6.13.3.drv",
        "attr": "kernel"
      },
      {
        "name": "os-release",
        "drvPath": "/nix/store/p3rw22j28h36s0jqcnkl6nxpr0xx1627-os-release.drv",
        "attr": "os-release"
      },
      {
        "name": "env",
        "drvPath": "/nix/store/7ylf3mvgck764bsqfbs2z8c130m9fiz1-env.drv",
        "attr": "shell"
      },
      {
        "name": "systemd-257.2",
        "drvPath": "/nix/store/q3y2may73alam9wfx6jidkijmnl6nydv-systemd-257.2.drv",
        "attr": "systemd"
      }
    ]
  },
  {
    "layer": 2,
    "derivations": [
      {
        "name": "presets",
        "drvPath": "/nix/store/8zqm44019r8xk175nkgfigvpsmnbalgs-presets.drv",
        "attr": "presets"
      }
    ]
  },
  {
    "layer": 3,
    "derivations": [
      {
        "name": "initrd",
        "drvPath": "/nix/store/8fhxwxkxg97g48gvi7mkpnfrn6ripj6v-initrd.drv",
        "attr": "initrd"
      }
    ]
  },
  {
    "layer": 4,
    "derivations": [
      {
        "name": "uki",
        "drvPath": "/nix/store/j0iiv19c2a2s8022wmx5abnmxcvpkaf3-uki.drv",
        "attr": "uki"
      }
    ]
  },
  {
    "layer": 5,
    "derivations": [
      {
        "name": "runvm",
        "drvPath": "/nix/store/0fadmwnakg51dagwda4rdnyh3c25zq43-runvm.drv",
        "attr": "runvm"
      },
      {
        "name": "toplevel",
        "drvPath": "/nix/store/65hxj55jb1b0qsg34g8psp0gywwz9vvh-toplevel.drv",
        "attr": "toplevel"
      }
    ]
  },
  {
    "layer": 6,
    "derivations": [
      {
        "name": "sonos_0.1.0.raw",
        "drvPath": "/nix/store/srmbw2hp1l771xpgzscf7ypbfr1fxmac-sonos_0.1.0.raw.drv",
        "attr": "image"
      }
    ]
  }
]

for the input:

{"attr":"erofs-utils","attrPath":["erofs-utils"],"drvPath":"/nix/store/ya02c5b2gihfkv0wkzkl4li497ibcksi-erofs-utils-1.8.5.drv","inputDrvs":{"/nix/store/4hw5p4viyn3flj565pc36fd7pz2rmb52-xz-5.6.3.drv":["dev"],"/nix/store/537aj1pih8n6fbl0qjqxplfv5d4wn005-erofs-utils-1.8.5.tar.gz.drv":["out"],"/nix/store/81lwjm4ijn2vz1wim8b96m83a3la88l3-bash-5.2p37.drv":["out"],"/nix/store/97dqlf59z44d2x2s494a7njgqpj8n0nq-lz4-1.10.0.drv":["dev"],"/nix/store/gc2x3v0z9y5rm72lbjbbkdvqdcp8zang-stdenv-linux.drv":["out"],"/nix/store/gqq1l9hxqaqbjfa2b7kd88gpjsc8dixj-zstd-1.5.6.drv":["dev"],"/nix/store/haw4va9zw9kgrcip7m99rsaic8l9ki61-fuse-2.9.9.drv":["dev"],"/nix/store/jajcf6fwjpib2ri0caa2ggj389dw5fh4-zlib-1.3.1.drv":["dev"],"/nix/store/pbvjspa23r7ainfgaa20vb37fzwprcy1-util-linux-2.39.4.drv":["dev"],"/nix/store/q2qaw0vlzcmss0i73599s96zcpldwa4z-pkg-config-wrapper-0.29.2.drv":["out"],"/nix/store/r86s8w7hy0ibxsqhrs10bg25b0q74lwv-autoreconf-hook.drv":["out"]},"name":"erofs-utils-1.8.5","outputs":{"man":"/nix/store/88jxkjjrnh6h1bpdgx2f4wqcn8kg3nsr-erofs-utils-1.8.5-man","out":"/nix/store/c3bn8rlfazqi8azvls4vvgfjyj7lhax3-erofs-utils-1.8.5"},"system":"aarch64-linux"}
{"attr":"image","attrPath":["image"],"drvPath":"/nix/store/srmbw2hp1l771xpgzscf7ypbfr1fxmac-sonos_0.1.0.raw.drv","inputDrvs":{"/nix/store/4lvjqi1jkx0qh79hxqf1d4vcykbhmxrm-stdenv-linux.drv":["out"],"/nix/store/65hxj55jb1b0qsg34g8psp0gywwz9vvh-toplevel.drv":["out"],"/nix/store/81lwjm4ijn2vz1wim8b96m83a3la88l3-bash-5.2p37.drv":["out"],"/nix/store/97j66srp24r1zd56y9zd37x85ksj3f8z-dosfstools-4.2.drv":["out"],"/nix/store/bhxgaqhs243c2v82hrq77hl3a49d84fm-fakeroot-1.36.drv":["out"],"/nix/store/gqq1l9hxqaqbjfa2b7kd88gpjsc8dixj-zstd-1.5.6.drv":["dev"],"/nix/store/j8qpzyyqc03xj8fdz04nhyhzk8n7s13y-mtools-4.0.47.drv":["out"],"/nix/store/q3y2may73alam9wfx6jidkijmnl6nydv-systemd-257.2.drv":["dev"],"/nix/store/ya02c5b2gihfkv0wkzkl4li497ibcksi-erofs-utils-1.8.5.drv":["out"]},"name":"sonos_0.1.0.raw","outputs":{"out":"/nix/store/mnb9i4qvddgpr29rq793kk925pq7hka5-sonos_0.1.0.raw"},"system":"aarch64-linux"}
{"attr":"initrd","attrPath":["initrd"],"drvPath":"/nix/store/8fhxwxkxg97g48gvi7mkpnfrn6ripj6v-initrd.drv","inputDrvs":{"/nix/store/4lvjqi1jkx0qh79hxqf1d4vcykbhmxrm-stdenv-linux.drv":["out"],"/nix/store/7rpdnnifcczqcsmm3d9n617rjyyjjmz3-binutils-wrapper-2.43.1.drv":["out"],"/nix/store/81lwjm4ijn2vz1wim8b96m83a3la88l3-bash-5.2p37.drv":["out"],"/nix/store/8zqm44019r8xk175nkgfigvpsmnbalgs-presets.drv":["out"],"/nix/store/ahdfh2yqib4szxs8fyisc5b37lrwkb5k-make-initrd-ng-0.1.0.drv":["out"],"/nix/store/bp1sqli83rvai9bw0fyqa0ymlzxq237j-cpio-2.15.drv":["out"],"/nix/store/gqq1l9hxqaqbjfa2b7kd88gpjsc8dixj-zstd-1.5.6.drv":["bin"],"/nix/store/q3y2may73alam9wfx6jidkijmnl6nydv-systemd-257.2.drv":["out"]},"name":"initrd","outputs":{"out":"/nix/store/2jms5kd05sqhic2q35p5dw6wwn6psang-initrd"},"system":"aarch64-linux"}
{"attr":"kernel","attrPath":["kernel"],"drvPath":"/nix/store/bp18vwdqiszljm9jdvx9sdb2c2r0pp4k-linux-6.13.3.drv","inputDrvs":{"/nix/store/049078gzy0n8fgsrq9l2ssq6cmx7107g-openssl-3.3.2.drv":["dev"],"/nix/store/2c6wf4ja7aq7a46khn0bcvw73qkwijx6-elfutils-0.192.drv":["dev"],"/nix/store/2k9ziwpsawafdzdvl4rvs7amg919n1gs-libmpc-1.3.1.drv":["out"],"/nix/store/47nqw5vqxjk22k21rgnqmclssajhmv0g-pahole-1.27.drv":["out"],"/nix/store/7p4cfb6c1ngfzg973x4yag9ji30a3r9l-installkernel.drv":["out"],"/nix/store/81lwjm4ijn2vz1wim8b96m83a3la88l3-bash-5.2p37.drv":["out"],"/nix/store/942c7ivspan61bfmjx00qfsxbckzhj0n-rust-lib-src.drv":["out"],"/nix/store/9yr33q69mbwp3yga0zpi08ca9z9v1nfn-flex-2.6.4.drv":["out"],"/nix/store/axk30q6c372c3wcfhlrn74pqpjiw7w48-bison-3.8.2.drv":["out"],"/nix/store/bp1sqli83rvai9bw0fyqa0ymlzxq237j-cpio-2.15.drv":["out"],"/nix/store/g1mh26v62r4ykqaj8j4vzn5qs3smim7s-gcc-wrapper-14-20241116.drv":["out"],"/nix/store/gc2x3v0z9y5rm72lbjbbkdvqdcp8zang-stdenv-linux.drv":["out"],"/nix/store/gqq1l9hxqaqbjfa2b7kd88gpjsc8dixj-zstd-1.5.6.drv":["dev"],"/nix/store/h8a03q97ay59a8f3wg0ndz66ac3l6l1k-net-tools-2.10.drv":["out"],"/nix/store/j1gcsaglrqxvfril53cjknmhp1q9xvp3-bc-1.07.1.drv":["out"],"/nix/store/jajcf6fwjpib2ri0caa2ggj389dw5fh4-zlib-1.3.1.drv":["dev"],"/nix/store/jd73fnsn6k4rxs81zcvyz20dw31czw86-perl-5.40.0.drv":["out"],"/nix/store/jmdlqf587brc6i35346lzi7zqirp5z4c-mpfr-4.2.1.drv":["dev"],"/nix/store/l4w7ys7v00lli9iaywy05ahqzrrmlc2a-rustc-wrapper-1.84.0.drv":["out"],"/nix/store/p8lwppif6cvcy5j8w4ay0m3bwrcbp8fh-python3-minimal-3.12.8.drv":["out"],"/nix/store/plc24lplqh2h0yv474gavasxzwg885ps-linux-6.13.3.tar.xz.drv":["out"],"/nix/store/qjq7cphfav9drssvnxjw1rvzjlw613kn-gmp-with-cxx-6.3.0.drv":["dev"],"/nix/store/rszr5q6h8zfpsv5mingjrhfzj0k46g6h-kmod-31.drv":["dev"],"/nix/store/vd9k3glbpx4d54cygqwidi3n18pdn0gp-rust-bindgen-0.71.1.drv":["out"],"/nix/store/vhfsb9jsvp9l3k8wxy9xkb0pxh3489ym-rsync-3.4.1.drv":["out"],"/nix/store/vqidwd5iqm0ld5w6cxr79lh4wkssdfqi-util-linux-minimal-2.39.4.drv":["dev"],"/nix/store/z5d35478844zfnfdc8skg6vhs87sxc7h-linux-config-6.13.3.drv":["out"]},"name":"linux-6.13.3","outputs":{"dev":"/nix/store/6f91rp1d0d6c3bhbh086y5h88g63mal7-linux-6.13.3-dev","out":"/nix/store/0kyiah1an334g9kh00665nc9n9qhhg57-linux-6.13.3"},"system":"aarch64-linux"}
{"attr":"os-release","attrPath":["os-release"],"drvPath":"/nix/store/p3rw22j28h36s0jqcnkl6nxpr0xx1627-os-release.drv","inputDrvs":{"/nix/store/4lvjqi1jkx0qh79hxqf1d4vcykbhmxrm-stdenv-linux.drv":["out"],"/nix/store/81lwjm4ijn2vz1wim8b96m83a3la88l3-bash-5.2p37.drv":["out"]},"name":"os-release","outputs":{"out":"/nix/store/5ylpy05sz66a5779blvxn03l5q406rgv-os-release"},"system":"aarch64-linux"}
{"attr":"presets","attrPath":["presets"],"drvPath":"/nix/store/8zqm44019r8xk175nkgfigvpsmnbalgs-presets.drv","inputDrvs":{"/nix/store/4lvjqi1jkx0qh79hxqf1d4vcykbhmxrm-stdenv-linux.drv":["out"],"/nix/store/81lwjm4ijn2vz1wim8b96m83a3la88l3-bash-5.2p37.drv":["out"],"/nix/store/q3y2may73alam9wfx6jidkijmnl6nydv-systemd-257.2.drv":["dev"]},"name":"presets","outputs":{"out":"/nix/store/dasf4pq9d511abadihaa4ms1yd2q1vya-presets"},"system":"aarch64-linux"}
{"attr":"runvm","attrPath":["runvm"],"drvPath":"/nix/store/0fadmwnakg51dagwda4rdnyh3c25zq43-runvm.drv","inputDrvs":{"/nix/store/4lvjqi1jkx0qh79hxqf1d4vcykbhmxrm-stdenv-linux.drv":["out"],"/nix/store/81lwjm4ijn2vz1wim8b96m83a3la88l3-bash-5.2p37.drv":["out"],"/nix/store/allx00mhj23f53adqlfic545amg2qxmy-ShellCheck-0.10.0.drv":["out"],"/nix/store/b2r0w7c58mrd965djx6cd6bgm651hjxh-qemu-host-cpu-only-9.2.0.drv":["out"],"/nix/store/j0iiv19c2a2s8022wmx5abnmxcvpkaf3-uki.drv":["out"]},"name":"runvm","outputs":{"out":"/nix/store/3n9l5f4p2g6ax6fjl025nfcvpf4nl9ps-runvm"},"system":"aarch64-linux"}
{"attr":"shell","attrPath":["shell"],"drvPath":"/nix/store/7ylf3mvgck764bsqfbs2z8c130m9fiz1-env.drv","inputDrvs":{"/nix/store/4lvjqi1jkx0qh79hxqf1d4vcykbhmxrm-stdenv-linux.drv":["out"],"/nix/store/5fjfb4jbsdf30zbnqhi18p23zh0ykl80-ijq-1.1.2.drv":["out"],"/nix/store/81lwjm4ijn2vz1wim8b96m83a3la88l3-bash-5.2p37.drv":["out"],"/nix/store/jd73fnsn6k4rxs81zcvyz20dw31czw86-perl-5.40.0.drv":["out"],"/nix/store/qjqvh9fxcf9aw69ll0lz0yvph7mhnazg-builder.pl.drv":["out"],"/nix/store/s42h4p1flgaw1mcdyfj01jai3mvahann-nix-eval-jobs-2.25.0.drv":["out"],"/nix/store/wvkm6jwch6vwywq9svgzh5a5xsbc072w-jq-1.7.1.drv":["bin","man"]},"name":"env","outputs":{"out":"/nix/store/jlplpimxgakzv7z0wf0xvkjcvd40hsyg-env"},"system":"aarch64-linux"}
{"attr":"systemd","attrPath":["systemd"],"drvPath":"/nix/store/q3y2may73alam9wfx6jidkijmnl6nydv-systemd-257.2.drv","inputDrvs":{"/nix/store/049078gzy0n8fgsrq9l2ssq6cmx7107g-openssl-3.3.2.drv":["dev"],"/nix/store/22jn5whzanhwjdi9jxl9lrv55gvh5d7m-libxcrypt-4.4.38.drv":["out"],"/nix/store/3f89gng5gcvizln5bvk6klhrj1vkj4jx-ninja-1.12.1.drv":["out"],"/nix/store/407nnmml0kmxh9rnch0pny21m801dja4-cryptsetup-2.7.5.drv":["dev"],"/nix/store/7hdxanxyfahqjljpsq8yhk1q37hwvv17-gperf-3.1.drv":["out"],"/nix/store/81lwjm4ijn2vz1wim8b96m83a3la88l3-bash-5.2p37.drv":["out"],"/nix/store/bazycpif6689pa4nnlx4bg4ggz0nhha8-python3-3.12.8-env.drv":["out"],"/nix/store/d3sfx6jflhi1s37c9v4p63x1y23k5m8x-python3-3.12.8-env.drv":["out"],"/nix/store/f2ykims5i39zmkxyi3k0x8s24hspz9qa-getent-glibc-2.40-66.drv":["out"],"/nix/store/fj5x9ba70kawrghvzipj5m0rxl43gzrc-auto-patchelf-hook.drv":["out"],"/nix/store/gc2x3v0z9y5rm72lbjbbkdvqdcp8zang-stdenv-linux.drv":["out"],"/nix/store/mns0pn31rjj6wyxkfhqzz4525vj5vzci-kbd-2.7.1.drv":["dev"],"/nix/store/ng578zr6zhg8r7cj8anwq518ncz23j5i-gnum4-1.4.19.drv":["out"],"/nix/store/ps9i2sh9vps6lv8mh3lvkkm0sbiryp3h-libcap-2.73.drv":["dev"],"/nix/store/q2qaw0vlzcmss0i73599s96zcpldwa4z-pkg-config-wrapper-0.29.2.drv":["out"],"/nix/store/rdfy4hiw7q1nrgddsv973z1dywv80mw9-tpm2-tss-4.1.3.drv":["dev"],"/nix/store/rdipazca5cfsflxkfprx65b18z0dpn0b-systemd.drv":["out"],"/nix/store/vqidwd5iqm0ld5w6cxr79lh4wkssdfqi-util-linux-minimal-2.39.4.drv":["dev"],"/nix/store/x3qss4pcqk9wzgzafcph1d93hn7bvw17-meson-1.6.1.drv":["out"]},"name":"systemd-257.2","outputs":{"dev":"/nix/store/4kwz638m7agllpn9jlhw9cz5rvyl7690-systemd-257.2-dev","intermediates":"/nix/store/jx96gmd8biqxk3z2pnl7y8wibzg6y6iy-systemd-257.2-intermediates","out":"/nix/store/dngkg24lyak585flf5xz82jm8zpdfy2d-systemd-257.2"},"system":"aarch64-linux"}
{"attr":"toplevel","attrPath":["toplevel"],"drvPath":"/nix/store/65hxj55jb1b0qsg34g8psp0gywwz9vvh-toplevel.drv","inputDrvs":{"/nix/store/7qqsxlpidgqgw0bp8w37mni52zfw87hh-closure-info.drv":["out"],"/nix/store/81lwjm4ijn2vz1wim8b96m83a3la88l3-bash-5.2p37.drv":["out"],"/nix/store/gc2x3v0z9y5rm72lbjbbkdvqdcp8zang-stdenv-linux.drv":["out"],"/nix/store/j0iiv19c2a2s8022wmx5abnmxcvpkaf3-uki.drv":["out"],"/nix/store/p3rw22j28h36s0jqcnkl6nxpr0xx1627-os-release.drv":["out"]},"name":"toplevel","outputs":{"out":"/nix/store/wsc8351n5nsg75incf3rzbk2qqjnwk7i-toplevel"},"system":"aarch64-linux"}
{"attr":"uki","attrPath":["uki"],"drvPath":"/nix/store/j0iiv19c2a2s8022wmx5abnmxcvpkaf3-uki.drv","inputDrvs":{"/nix/store/4lvjqi1jkx0qh79hxqf1d4vcykbhmxrm-stdenv-linux.drv":["out"],"/nix/store/81lwjm4ijn2vz1wim8b96m83a3la88l3-bash-5.2p37.drv":["out"],"/nix/store/8fhxwxkxg97g48gvi7mkpnfrn6ripj6v-initrd.drv":["out"],"/nix/store/bp18vwdqiszljm9jdvx9sdb2c2r0pp4k-linux-6.13.3.drv":["out"],"/nix/store/p3rw22j28h36s0jqcnkl6nxpr0xx1627-os-release.drv":["out"],"/nix/store/q3y2may73alam9wfx6jidkijmnl6nydv-systemd-257.2.drv":["dev","out"]},"name":"uki","outputs":{"out":"/nix/store/91kxc36h5jxlvncai22ywcccpdbvb5g5-uki"},"system":"aarch64-linux"}

[Mic92]

I guess that would be some sort of toposort + graph slicing. Is the idea that each layer can be independently build by a different machine?

[arianvp]

This is what I came up with as post-processing at the moment:

import json
import sys
from collections import defaultdict, deque


def parse_derivation_data(data_str):
    """Parse the derivation data from the input string."""
    derivations = []
    for line in data_str.strip().split("\n"):
        if line:
            derivations.append(json.loads(line))
    return derivations


def build_dependency_graph(derivations):
    """Build a dependency graph from the derivations."""
    # Map from derivation path to its index in the derivations list
    drv_path_to_index = {}
    for i, drv in enumerate(derivations):
        drv_path_to_index[drv["drvPath"]] = i

    # Build the graph: node -> [dependencies]
    graph = defaultdict(list)
    # Build the reverse graph: node -> [dependents]
    reverse_graph = defaultdict(list)

    for i, drv in enumerate(derivations):
        for input_drv in drv["inputDrvs"]:
            if input_drv in drv_path_to_index:
                dep_idx = drv_path_to_index[input_drv]
                graph[i].append(dep_idx)
                reverse_graph[dep_idx].append(i)

    return graph, reverse_graph, drv_path_to_index


def compute_layers(derivations, graph, reverse_graph):
    """Compute layers of the build graph for maximum parallelism."""
    n = len(derivations)
    in_degree = [len(graph[i]) for i in range(n)]

    # Start with nodes that have no dependencies
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    layers = []

    while queue:
        current_layer = []
        layer_size = len(queue)

        for _ in range(layer_size):
            node = queue.popleft()
            current_layer.append(node)

            # Reduce in-degree of all dependents
            for dependent in reverse_graph[node]:
                in_degree[dependent] -= 1
                if in_degree[dependent] == 0:
                    queue.append(dependent)

        layers.append(current_layer)

    return layers


def format_output(derivations, layers):
    """Format the output with the build layers."""
    result = []

    for i, layer in enumerate(layers):
        layer_info = {"layer": i + 1, "derivations": []}

        for node_idx in layer:
            drv = derivations[node_idx]
            layer_info["derivations"].append(
                {
                    "name": drv["name"],
                    "drvPath": drv["drvPath"],
                    "attr": drv["attr"],
                }
            )

        result.append(layer_info)

    return result


def main(data_str):
    derivations = parse_derivation_data(data_str)
    graph, reverse_graph, drv_path_to_index = build_dependency_graph(
        derivations
    )
    layers = compute_layers(derivations, graph, reverse_graph)
    result = format_output(derivations, layers)

    print(json.dumps(result, indent=2))


if __name__ == "__main__":
    # Read from stdin
    data_str = sys.stdin.read()

    main(data_str)

[arianvp]

Is the idea that each layer can be independently build by a different machine?

Yes exactly.