How deep is your Nix dependency graph?

2024-06-03

I ran into performance issues while refactoring the graph traversal algorithm of nix2sbom. The program would take a long time to complete, mainly because the same nodes were visited multiple times. The first solution I thought of was to keep track of the visited nodes, but the whole situation made me wonder: How big is that dependency graph?

Finding the longest path

I settled on a simplified version my initial question: How long is the longest path in that dependency graph? I added an option to nix2sbom to get that information:

# Here, I'm using nix2sbom to get the longest path in the dependency graph of nix2sbom itself.
nix run github:louib/nix2sbom?rev=8ea11305d240a28a4c58520c294c627556ecee87 -- --no-meta --format stats -f github:louib/nix2sbom?rev=8ea11305d240a28a4c58520c294c627556ecee87

The answer to our question can be found in the longest_path_length field:

  "longest_path_length": {
    "/nix/store/g4bf7igwz3wmgx6qbhhz77bpbyv6lb70-nix2sbom-main.drv": 98
  },

98? Really? Here's the full path:

  "longest_path": [
    "/nix/store/g4bf7igwz3wmgx6qbhhz77bpbyv6lb70-nix2sbom-main.drv",
    "/nix/store/5hrcg3b43hgfbfi30qnygp0wp32qc06r-cargo-build-hook.sh.drv",
    "/nix/store/aq1i2qq524gs4ra3d9kd7f60anpjhym8-cargo-1.77.2.drv",
    "/nix/store/r20zd7xsl1mszq0yfzl5zvpx2a7kz35y-auditable-cargo-bootstrap-1.76.0.drv",
    "/nix/store/irv5cx83s7rabbw8a1h6mcrrfig8j9dw-cargo-auditable-0.6.2.drv",
    "/nix/store/638fxslllq7wyznwr58jga69b4mhfwyf-cargo-auditable-0.6.2-vendor.tar.gz.drv",
    "/nix/store/5a1rv39g86nij8f93ypcnf3w07lzz000-cargo-1.77.2.drv",
    "/nix/store/cwycfrkry8jggb8yw513ypwp89agjg5j-rustc-wrapper-1.77.2.drv",
    "/nix/store/d6003ik7j0m1sjxcp86k90mf1dygjwnq-rustc-1.77.2.drv",
    "/nix/store/6c0yj2k4cg8jgic13d1aa28dvwn4vys6-llvm-17.0.6.drv",
    "/nix/store/zp2813dml0ip0w7wsfwd4fmwgdkbcb17-cmake-3.29.2.drv",
    "/nix/store/7kcyc8yzbksnmwv3d1mrkhyvad71g661-libarchive-3.7.4.drv",
    "/nix/store/xy8xgydz76rq7151012vks5hidyfx97i-e2fsprogs-1.47.0.drv",
    "/nix/store/vhf8fpim8ivrbgnr2r6j01a92qyhj4ik-fuse-2.9.9.drv",
    "/nix/store/3nxwikhnxabihayysqc95ic7d40qsh9g-fuse-3.16.2.drv",
    "/nix/store/6zk1l8bcwcg7gyd4n5cbs4d291w1m5z6-meson-1.4.0.drv",
    "/nix/store/g541080x6haw68qq1nphzdabybrnnx61-ninja-1.11.1.drv",
    "/nix/store/z9i7cqx1ha7iblf21m29mp3dsjs6m7ai-asciidoc-10.2.0.drv",
    "/nix/store/2ccddwzp4qyy6jcdjpjdj39irvd9kf2q-python3.11-pytest-mock-3.14.0.drv",
    "/nix/store/08n4hv4aycw8v7g1q4v4gp2xa2nmz4g7-python3.11-pytest-asyncio-0.23.6.drv",
    "/nix/store/5bk054517v9zyjhvbmi0095nnv92sbkf-python3.11-pytest-8.1.1.drv",
    "/nix/store/43xj4imgmf339xkk9267lhxdmyzvzdkj-python3.11-iniconfig-2.0.0.drv",
    "/nix/store/ivcq7bi7mpac4zkhdr5wxwrq8yyhdmyb-python3.11-hatchling-1.24.2.drv",
    "/nix/store/yhb7j4f8js88swhwvnv64cncp1z9fr79-python3.11-trove-classifiers-2024.4.10.drv",
    "/nix/store/ag5mrwbmrw57l2ds1cgfnmk859qmxq03-python3.11-calver-2022.06.26.drv",
    "/nix/store/a2iyf2533k83f8i8ndbligv25dkknfq0-setuptools-build-hook.drv",
    "/nix/store/fcwvdb2c783bf1ccy8w4q62s2mwwki2s-python3.11-setuptools-69.5.1.drv",
    "/nix/store/xf5jvvplqg7b8ana9lvdb7v54x23mkfz-pypa-build-hook.sh.drv",
    "/nix/store/djx6rbfa0wpzzjpny7d9n2q5nrlz21r1-python3.11-build-1.2.1.drv",
    "/nix/store/h3l7791z1rz3dhydi6bfc981mdj96aqs-python3.11-pyproject-hooks-1.0.0.drv",
    "/nix/store/6wini1rym0l5sgrhkxrdplsbii07cgh5-pypa-install-hook.drv",
    "/nix/store/jsw4d7zn1avns3w68xwkdg8v5graik5y-python3.11-installer-0.7.0.drv",
    "/nix/store/zm8cigdx5z3y884wyi1s7jhm5gs593p4-python3.11-flit-core-3.9.0.drv",
    "/nix/store/56rpw0ygwz1ahk4p9g13yd3z690lfk4v-pypa-build-hook.sh.drv",
    "/nix/store/cqfl32nl1m873dfx17j6znzqbiwg83vr-python3.11-bootstrap-build-1.2.1.drv",
    "/nix/store/l4w6lwb90m224x479q0knvfkggrvmp86-python3.11-bootstrap-tomli-2.0.1.drv",
    "/nix/store/dl841pj30fbaqbs8x451ifhjnb2ffmcw-python3.11-bootstrap-installer-0.7.0.drv",
    "/nix/store/8j478smqppa3g8a88qzr16s854zbxlh5-python3.11-bootstrap-flit-core-3.9.0.drv",
    "/nix/store/xprkyi70sjkbijl5ypmq4i74qv7vmp3g-python3-3.11.9.drv",
    "/nix/store/l4007ql4y14ym43nz4rnk2xvb7i39ws1-libffi-3.4.6.drv",
    "/nix/store/npy6ckjpmjqh4qhw3587p9xi455n969g-dejagnu-1.6.3.drv",
    "/nix/store/7mval8zscx5yl4layh9a70lcmx8r7rzq-expect-5.45.4.drv",
    "/nix/store/h37ch3ni4p03imz19nwnqijhr65s8vlq-autoreconf-hook.drv",
    "/nix/store/h3s38whkgzw3z591mvzyfz2bkg87qxqm-automake-1.16.5.drv",
    "/nix/store/3dddzh9nyq9s3qbdwm8vfgnf6mckx821-autoconf-2.72.drv",
    "/nix/store/iz31y1lfjkc1h3rjzynjjiqgl8mkjcyh-texinfo-7.0.3.drv",
    "/nix/store/saakri0iydihf9awvyfn0nknrn0184rj-perl-5.38.2.drv",
    "/nix/store/b3q8zkxwifgajph2d3k4wn5pnsz8y0b8-perl-5.38.2.tar.gz.drv",
    "/nix/store/wrahlxhhvkaybyh8qs2da8xh9y6sv2c1-curl-8.7.1.drv",
    "/nix/store/c6xg8apc9wviial8swwr8yjhmywxyrpn-libkrb5-1.21.2.drv",
    "/nix/store/sr564371s1vch07y3ld940bg5gigcz1g-openssl-3.0.13.drv",
    "/nix/store/lgaz4da3mpzyvzjgfrf6q5zc4c2lmz2w-coreutils-9.5.drv",
    "/nix/store/hnws3zackragq9vhsvxycx28xkrps0qr-perl-5.38.2.drv",
    "/nix/store/pq8xbhh5syr9qzxd8kg586m4fvnnar6n-libxcrypt-4.4.36.drv",
    "/nix/store/rq8g9axnpi38491xsvg7fb5pwkjslk1m-perl-5.38.2.drv",
    "/nix/store/panbw08d4yffvkwkl7fpa2k051sjwpz0-stdenv-linux.drv",
    "/nix/store/kj60s25m64sijyzlrngnaaz4xywihg8p-gcc-wrapper-13.2.0.drv",
    "/nix/store/791xby1n843szxlzzz9c37d1h93ffvqv-binutils-wrapper-2.41.drv",
    "/nix/store/qdrm57vpbrk318i844d0pm0hvpqfibfx-gnugrep-3.11.drv",
    "/nix/store/ks4kxnnljmfjifik8fz4xyfc27bikn1p-glibc-locales-2.39-52.drv",
    "/nix/store/w0lha65nhpb8ya0xjjhb4l7jj72rd81p-python3-minimal-3.11.9.drv",
    "/nix/store/yigrqn6h5wdby20hsbc7l7jdanils595-bzip2-1.0.8.drv",
    "/nix/store/jhikqgc2lmd3cg1yv92k8qi0rj26knyr-autoreconf-hook.drv",
    "/nix/store/ll556j52p0maf8hy6p19d8vw7xckv4wd-automake-1.16.5.drv",
    "/nix/store/vy8fxc24cy7d821sp446przpwjckmxh6-autoconf-2.72.drv",
    "/nix/store/y408ng6sra3xvhq87sv2rgz3ibmmwvg4-bootstrap-stage4-stdenv-linux.drv",
    "/nix/store/27b9wfzxv7g8x43whc8krgqgfbc5hvvw-bootstrap-stage4-gcc-wrapper-13.2.0.drv",
    "/nix/store/k2mw2sd49ns63gnl6hlbi5za2pcg836a-gcc-13.2.0.drv",
    "/nix/store/hjpadr0lqa2jx69avhg6lzm1vkvv8m0r-libmpc-1.3.1.drv",
    "/nix/store/y8d0hz8s8zqcs7n296r2cxfzdmph3s0f-mpfr-4.2.1.drv",
    "/nix/store/07fpbmy07kagb9z3azdl6ssiqxzdn3cj-gmp-6.3.0.drv",
    "/nix/store/i538jwdc8mrg3zhjr0gqzrmqbgp3zr9a-bootstrap-stage3-stdenv-linux.drv",
    "/nix/store/cxw46q6wyl881m4d47fiz459rd5j5z97-bootstrap-stage3-gcc-wrapper-13.2.0.drv",
    "/nix/store/rnnv75hlrqqxcfi16knl4rc3kdx2wn38-binutils-patchelfed-ld-wrapper-2.41.drv",
    "/nix/store/458hjmxma9adq317v4g6icfj2p0q3ysi-binutils-patchelfed-ld-2.41.drv",
    "/nix/store/giq55ck4qbyhjak92g7qi60r7yy8a2mc-glibc-2.39-52.drv",
    "/nix/store/74sy46v3haa27mm4wk1xjbxs6z20y0ch-python3-minimal-3.11.9.drv",
    "/nix/store/1dwbbh9a5xf0bydfdgq0glz5b38jrqif-bzip2-1.0.8.drv",
    "/nix/store/ldsr7af4chn38qz4ffv5pw1bcpyck8cm-autoreconf-hook.drv",
    "/nix/store/hzaakzbh3npimqpkmx7qqc2pf229m9hw-libtool-2.4.7.drv",
    "/nix/store/sqbmmly1zsfkqb7va1mm24b09x3k4hd8-file-5.45.drv",
    "/nix/store/4rascx24j2597gjkcxvmwfhjld9x4pl6-zlib-1.3.1.drv",
    "/nix/store/b1n15s3mv6f3vy0n9yskx4y6hbhgc9mv-bootstrap-stage2-stdenv-linux.drv",
    "/nix/store/ci63f5znn14m5avccm6753ha5lcidc68-bootstrap-stage2-gcc-wrapper-13.2.0.drv",
    "/nix/store/fhbw1vlsc7zc1qfr047wbckhfjla1c06-xgcc-13.2.0.drv",
    "/nix/store/47drhxh4jkq1nn5pni61w3x9lr0mb9r8-libmpc-1.3.1.drv",
    "/nix/store/k44gvk6ysck2p9k43bw45s9z84davhmk-mpfr-4.2.1.drv",
    "/nix/store/9kphrq33p95zwqdy9ql6w5hc2c2b2iwq-gmp-6.3.0.drv",
    "/nix/store/7jrm912kmj6facm1dkpxx8fg52z33a71-bootstrap-stage-xgcc-stdenv-linux.drv",
    "/nix/store/5lfqd7gf9yb27jpc8f6s5l28bhlq1i6a-bootstrap-stage-xgcc-gcc-wrapper-.drv",
    "/nix/store/zwqrmdcdr6jk6p01zxdyhs8lvjcksl5w-expand-response-params.drv",
    "/nix/store/4z34260nasfrw1sh4gh6n79711yrhm97-bootstrap-stage1-stdenv-linux.drv",
    "/nix/store/d5fyamk2c6b305807npq2j1l4kbaqif1-bootstrap-stage1-gcc-wrapper-.drv",
    "/nix/store/0slmnpqn8ahqhnskf5mhqmnj5v6n9kq3-bootstrap-stage0-binutils-wrapper-.drv",
    "/nix/store/gfmqk56r8rv61yqyz9i7rbkrnab27gky-bootstrap-stage0-glibc-bootstrapFiles.drv",
    "/nix/store/hnfw75cqyly6s0ladkpdqppqllbqsapy-bootstrap-stage0-stdenv-linux.drv",
    "/nix/store/h3nkdqxk105rmz1i7ckj2swnj77h8fmr-bootstrap-tools.drv",
    "/nix/store/0m4y3j4pnivlhhpr5yqdvlly86p93fwc-busybox.drv"
  ],

Excluding build-time dependencies

The previous answer includes both runtime dependencies and build-time dependencies. Using the --runtime-only option, we can filter out build-time dependencies, and get our updated answer:

nix run github:louib/nix2sbom?rev=8ea11305d240a28a4c58520c294c627556ecee87 -- --no-meta --format stats -f github:louib/nix2sbom?rev=8ea11305d240a28a4c58520c294c627556ecee87 --runtime-only

Without the build-time dependencies, the longest path in the dependency graph is now 29.

Conclusion

I admit I didn't expect my dependency graph to be that deep. However, it's hard to compare those numbers with those we would obtain from other package managers, especially language-specific package managers like npm or cargo. Nix is language-agnostic, and the full list of dependencies for a project is included in the dependency graph, all the way up to the bootstrap binaries.

I wish I had a better conclusion for you, but I'm still trying to make sense of those numbers. Go ahead and give nix2sbom a try, you might be surprised how deep your Nix dependency graph is!