Unexpected rebuilds on contentAddressedByDefault = true; nix

[trofi]

Here is my experiment in contentAddressedByDefault = true;:

1. Build R package
2. Patch bash (core package) in a way that it changes only derivation
3. Rebuild R package

Expected result: only bash package will get rebuild a few times. The rest will reuse the same CA store.
Actual result: bash and R get rebuilt again (and nothing else).

Session log in nixpkgs checkout staging branch (master has the same behaviour):

$ nix-build -A R --arg config '{ contentAddressedByDefault = true; }'
these 677 derivations will be built:
... <built ok, took a while>

$ <patch bash with patch below>

$ time nix-build -A R --arg config '{ contentAddressedByDefault = true; }'
these 673 derivations will be built:
...
<bash-is-rebuilt, ok>
Resolved derivation: '/nix/store/...-python3-minimal-3.9.6.drv' -> '/nix/store/...-python3-minimal-3.9.6.drv'...
<bash output did not change, rest of packages reuses CA entries>
...
<texlive-combined, unexpected!>
<R-is-rebuilt, unexpected!>

Is it expected that R gets rebuilt? Or it's a bug?

bash patch:

--- a/pkgs/shells/bash/5.1.nix
+++ b/pkgs/shells/bash/5.1.nix
@@ -89,6 +89,7 @@ stdenv.mkDerivation rec {
   postInstall = ''
     ln -s bash "$out/bin/sh"
     rm -f $out/lib/bash/Makefile.inc
+    echo foo
   '';

   postFixup =

CC @regnat

[trofi]

I think it happens because .drv file for texlive-combined has unstable inputDrvs ordering even if there is no material difference in them:

# unmodified:
$ nix-instantiate -E 'with import ./. {}; texlive.combine { inherit (texlive) scheme-small inconsolata helvetic texinfo fancyvrb cm-super; }'
/nix/store/3v4099yr4l20ibz5f9iiivx6apqlf20b-texlive-combined-2021.drv

# patch bash
# modified
$ nix-instantiate -E 'with import ./. {}; texlive.combine { inherit (texlive) scheme-small inconsolata helvetic texinfo fancyvrb cm-super; }'
/nix/store/4ypzxm2yd1ncvvd8qr7262v4xzwx87m5-texlive-combined-2021.drv

$ diff -u \
  <(nix show-derivation /nix/store/3v4099yr4l20ibz5f9iiivx6apqlf20b-texlive-combined-2021.drv) \
  <(nix show-derivation /nix/store/4ypzxm2yd1ncvvd8qr7262v4xzwx87m5-texlive-combined-2021.drv) \
  | sed -r 's@/nix/store/[0-9a-z]{32}-@/<<NIX>>/@g'
--- /dev/fd/63  2021-10-05 09:59:57.717183638 +0100
+++ /dev/fd/62  2021-10-05 09:59:57.717183638 +0100
@@ -1,5 +1,5 @@
 {
-  "/<<NIX>>/texlive-combined-2021.drv": {
+  "/<<NIX>>/texlive-combined-2021.drv": {
     "outputs": {
       "out": {
         "hashAlgo": "r:sha256"
@@ -9,941 +9,941 @@
       "/<<NIX>>/default-builder.sh"
     ],
     "inputDrvs": {
-      "/<<NIX>>/hyphens.sed.drv": [
+      "/<<NIX>>/texlive-simple-resume-cv-43057.drv": [
         "out"
       ],
-      "/<<NIX>>/texlive-attachfile2-2.11.drv": [
+      "/<<NIX>>/texlive-realscripts-0.3d.drv": [
         "out"
       ],
-      "/<<NIX>>/texlive-dehyph-48599.drv": [
+      "/<<NIX>>/texlive-ptext-1.1.drv": [
         "out"
       ],

I suspect that we currently sort inputDrvs based on store path of derivations and that reshuffles them to the point they have to be rebuild.

Would it be possible not to reshuffle them? Say, if we would list them in .drv files in order written by user in nix expressions.

The downside is that it would probably make attribute order unstable WRT seeingly immaterial changes. Currently it's stable:

nix-repl> let d1 = stdenv.mkDerivation { name = "d1"; }; d2 = stdenv.mkDerivation { name = "d1"; }; in stdenv.mkDerivation { name = "combined"; e1_path = "${d1}"; e2_path = "${d2}"; }
«derivation /nix/store/1vd98pdsar99cj00dv2dxb0hp8lgnwiv-combined.drv»

nix-repl> let d1 = stdenv.mkDerivation { name = "d1"; }; d2 = stdenv.mkDerivation { name = "d1"; }; in stdenv.mkDerivation { name = "combined"; e2_path = "${d2}"; e1_path = "${d1}"; }
«derivation /nix/store/1vd98pdsar99cj00dv2dxb0hp8lgnwiv-combined.drv»

[trofi]

Would it be possible not to reshuffle them? Say, if we would list them in .drv files in order written by user in nix expressions.

Or even better: re-sort inputDrvs after applying content-addressed rewrites and use that as a key to detect if we already have realization for such a .drv.

[thufschmitt]

So after looking at things a bit more deeply, it’s indeed an ordering problem. Not of inputDrvs (these one are removed during the “resolution” phase), but inside the Nix code. The build script for texlive-combined does something morally equivalent to

postBuild = ''
  concatMapStrings (path: ''doSomethingOn ${path}'') (sort (a: b: a < b)) (map (p: p.outPath) inputs)
''

The call to sort means that the inputs of concatMapStrings will be sorted, accorded to their outPath field, which at eval-time is just an (input-dependent) placeholder. So each build will yield a different postBuild, explaining why it gets rebuilt each time.

So in a way, this is another instance of #4764 .

I wonder now why the call to sort (here). I suspect there’s no strong reason for it to be there and it could just be dropped without any downside but I didn’t test it so far.

[trofi]

Oh, that's tricky! Looks like sort was intended to have stable ordering of combined package names.

I think cheapest fix would be to tweak it to sort by p.name for output paths. I'll test locally and prepare a PR.

[trofi]

Proposed the change as NixOS/nixpkgs#140619