How is fixed point used for overriding nixpkgs packages?

Help
4

I’ve been struggling with these same basics, so here’s my take, but take it with a grain (or more like a pound) of salt as this may be a “blind leading the blind” scenario. (Linking the fixed-point combinator wikipedia because it helped somewhat.)

For starters, a reminder to self, here’s fix from Nixpkgs’ lib:

fix = f: let x = f x; in x;

Taking a simpler and shorter example than the one in Nix Pills:

f = self: { a = 27; b = self.a; }

fix f    #=> { a = 27; b = 27; }

because fix f evaluates to

= f(
    f( 
      f(...)))

In this case, evaluating 3 levels is enough

f (f f)

because

     ┏━━━━━━━━━━━━━━━━━━┓
     ┃                  ∨
= (self: { a = 27; b = self.a; }) (
  ---∧----------f-------┃-------- ( 
     ┃                  ┃
     ┗━ (self: { a = 27; b = self.a; }) (
        --------------f-┃-------------- (
                        ┃
              (self: { a = 27; b = self.a; }) (...)))
              ----------┃---f---------------- (...)))
                        ┃
                        ∨

= { a = 27;
    b = (
             ┏━━━━━━━━━━━━━━━━━━┓
             ┃                  ∨
          (self: { a = 27; b = self.a; }) (
          ---∧----------f-------┃-------- ( 
             ┃                  ┃
             ┗━ (self: { a = 27; b = self.a; }) (
                --------------f-┃-------------- (
        ).a                     ┃
  }                             ┃
                                ∨

= { a = 27;
    b = 
        { a = 27;

          # Nix is lazy, so this can happily keep
          # recursing  as `b` is never requested,
          # only `a`, which is now ready.
          b = ( (self: ... (self: ... ( ...))).a
        }.a
  }

1. Question 1

What does it mean by the following? Could you explain that in terms of the example in 17.3.1?

We’ve seen how to override attributes in a set such that they get recursively picked by dependant attributes.

To recap:

fix = f: let x = f x; in x;
f = self: { a = 27; b = self.a; }

fix f    #=> { a = 27; b = 27; }

1.1 Overriding the output

Taking the first newpkgs example in section 17.3.1 and re-writing it using f and a set to update the initial attribute a:

let newpkgs = pkgs (newpkgs // overrides); in newpkgs
let newpkgs =   f  (newpkgs // { a = 9; };  in newpkgs =
                -----------┃------------         ∧
                           ┗━━━━━━━━━━━━━━━━━━━━━┛

     ┏━━━━━━━━━━━━━━━━━━┓
     ┃                  ∨
= (self: { a = 27; b = self.a; }) (newpkgs // { a = 9; }) = 
   --∧----------f---------------   ----------┃----------
     ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

                    ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
                    ∨                             ┃                  
= { a = 27; b = (newpkgs // { a = 9; }).a; } = newpkgs =

= { a = 27; b = ({ a = 27; b = (newpkgs // { a = 9; }).a; } // { a = 9; }).a; } =
                 ---------------newpkgs--------------------
  ------------------------------newpkgs----------------------------------------                  
= { a = 27; b = ({ a = 27; b = ... } // { a = 9; }).a; } =
                 ----newpkgs--------
= { a = 27; b = ({ a = 9; b = ... }).a; } =
                 ----newpkgs-------
= { a = 27; b = 9; }

1.2 Overriding both input & output

Adding explicit parentheses to the second newpkgs example in section 17.3.1 makes it easier to see that it simply updates the resulting attribute set with the same “overriding” attribute set:

let newpkgs = pkgs (newpkgs // overrides); in newpkgs // overrides
let newpkgs =   f  (newpkgs // { a = 9; };  in newpkgs   // { a = 9; } =
            = ( f  (newpkgs // { a = 9; };  in newpkgs ) // { a = 9; } =
            # ...reduction steps in section 1.1 above...
            = { a = 27; b = 9; } // { a = 9; } =
            = { a = 9; b = 9; }

1.3 “Overridable” fixes

newpkgs can be generalized as an “overridable” fix:

overridable_fix  = f: overrides: let x = f (x // overrides); in x
overridable_fix' = f: overrides: overridable_fix f overrides // overrides

override = { a = 9; }
overridable_fix  f override   #=> { a = 27; b = 9; }
overridable_fix' f override   #=> { a = 9;  b = 9; }

2. Remaining questions

TODO: These are mostly notes for myself to figure out the answers, because I’ve been asking the same things for years.

  • What does it mean by “nixpkgs returns a fixed point of the package set”?

    Not sure how accurate this is, but I imagine Nixpkgs’ “fixed points” the same way as in math where the invariant points are fully resolved Nix expressions that only need to be realized.
    image

  • Isn’t a fixed point something belonging to a function, and the package set isn’t a function?

    I remember reading somewhere that package sets are functions, but not sure, so leaving these here:

    • Why does nixpkgs return a fixed point? Is nixpkgs something similar to the example let newpkgs = pkgs (newpkgs // overrides); in newpkgs in 17.3.1.?

    (Yeah, I would love to see high-level architectural diagrams on how Nixpkgs relates to concepts such as fixed points.)

  • What does it mean by “packageOverrides is used to inject the overrides”?

    Again, have no answer, but the Nixpkgs issue #43266 “Deprecate packageOverrides?” has tons of info.

  • Why “Then pkgs.asciidoc-full is a derivation that has graphviz input”?

  • Why “The newly built asciidoc will depend on the new graphviz”, and “old asciidoc will keep using the old graphviz undisturbed”?

3 Likes