lib/fixed-points.nix

   1 { lib, ... }:
   2 rec {
   3   /**
   4     `fix f` computes the fixed point of the given function `f`. In other words, the return value is `x` in `x = f x`.
   5
   6     `f` must be a lazy function.
   7     This means that `x` must be a value that can be partially evaluated,
   8     such as an attribute set, a list, or a function.
   9     This way, `f` can use one part of `x` to compute another part.
  10
  11     **Relation to syntactic recursion**
  12
  13     This section explains `fix` by refactoring from syntactic recursion to a call of `fix` instead.
  14
  15     For context, Nix lets you define attributes in terms of other attributes syntactically using the [`rec { }` syntax](https://nixos.org/manual/nix/stable/language/constructs.html#recursive-sets).
  16
  17     ```nix
  18     nix-repl> rec {
  19       foo = "foo";
  20       bar = "bar";
  21       foobar = foo + bar;
  22     }
  23     { bar = "bar"; foo = "foo"; foobar = "foobar"; }
  24     ```
  25
  26     This is convenient when constructing a value to pass to a function for example,
  27     but an equivalent effect can be achieved with the `let` binding syntax:
  28
  29     ```nix
  30     nix-repl> let self = {
  31       foo = "foo";
  32       bar = "bar";
  33       foobar = self.foo + self.bar;
  34     }; in self
  35     { bar = "bar"; foo = "foo"; foobar = "foobar"; }
  36     ```
  37
  38     But in general you can get more reuse out of `let` bindings by refactoring them to a function.
  39
  40     ```nix
  41     nix-repl> f = self: {
  42       foo = "foo";
  43       bar = "bar";
  44       foobar = self.foo + self.bar;
  45     }
  46     ```
  47
  48     This is where `fix` comes in, it contains the syntactic recursion that's not in `f` anymore.
  49
  50     ```nix
  51     nix-repl> fix = f:
  52       let self = f self; in self;
  53     ```
  54
  55     By applying `fix` we get the final result.
  56
  57     ```nix
  58     nix-repl> fix f
  59     { bar = "bar"; foo = "foo"; foobar = "foobar"; }
  60     ```
  61
  62     Such a refactored `f` using `fix` is not useful by itself.
  63     See [`extends`](#function-library-lib.fixedPoints.extends) for an example use case.
  64     There `self` is also often called `final`.
  65
  66     # Inputs
  67
  68     `f`
  69
  70     : 1\. Function argument
  71
  72     # Type
  73
  74     ```
  75     fix :: (a -> a) -> a
  76     ```
  77
  78     # Examples
  79     :::{.example}
  80     ## `lib.fixedPoints.fix` usage example
  81
  82     ```nix
  83     fix (self: { foo = "foo"; bar = "bar"; foobar = self.foo + self.bar; })
  84     => { bar = "bar"; foo = "foo"; foobar = "foobar"; }
  85
  86     fix (self: [ 1 2 (elemAt self 0 + elemAt self 1) ])
  87     => [ 1 2 3 ]
  88     ```
  89
  90     :::
  91   */
  92   fix =
  93     f:
  94     let
  95       x = f x;
  96     in
  97     x;
  98
  99   /**
 100     A variant of `fix` that records the original recursive attribute set in the
 101     result, in an attribute named `__unfix__`.
 102
 103     This is useful in combination with the `extends` function to
 104     implement deep overriding.
 105
 106     # Inputs
 107
 108     `f`
 109
 110     : 1\. Function argument
 111   */
 112   fix' =
 113     f:
 114     let
 115       x = f x // {
 116         __unfix__ = f;
 117       };
 118     in
 119     x;
 120
 121   /**
 122     Return the fixpoint that `f` converges to when called iteratively, starting
 123     with the input `x`.
 124
 125     ```
 126     nix-repl> converge (x: x / 2) 16
 127     0
 128     ```
 129
 130     # Inputs
 131
 132     `f`
 133
 134     : 1\. Function argument
 135
 136     `x`
 137
 138     : 2\. Function argument
 139
 140     # Type
 141
 142     ```
 143     (a -> a) -> a -> a
 144     ```
 145   */
 146   converge =
 147     f: x:
 148     let
 149       x' = f x;
 150     in
 151     if x' == x then x else converge f x';
 152
 153   /**
 154     Extend a function using an overlay.
 155
 156     Overlays allow modifying and extending fixed-point functions, specifically ones returning attribute sets.
 157     A fixed-point function is a function which is intended to be evaluated by passing the result of itself as the argument.
 158     This is possible due to Nix's lazy evaluation.
 159
 160     A fixed-point function returning an attribute set has the form
 161
 162     ```nix
 163     final: { # attributes }
 164     ```
 165
 166     where `final` refers to the lazily evaluated attribute set returned by the fixed-point function.
 167
 168     An overlay to such a fixed-point function has the form
 169
 170     ```nix
 171     final: prev: { # attributes }
 172     ```
 173
 174     where `prev` refers to the result of the original function to `final`, and `final` is the result of the composition of the overlay and the original function.
 175
 176     Applying an overlay is done with `extends`:
 177
 178     ```nix
 179     let
 180       f = final: { # attributes };
 181       overlay = final: prev: { # attributes };
 182     in extends overlay f;
 183     ```
 184
 185     To get the value of `final`, use `lib.fix`:
 186
 187     ```nix
 188     let
 189       f = final: { # attributes };
 190       overlay = final: prev: { # attributes };
 191       g = extends overlay f;
 192     in fix g
 193     ```
 194
 195     :::{.note}
 196     The argument to the given fixed-point function after applying an overlay will *not* refer to its own return value, but rather to the value after evaluating the overlay function.
 197
 198     The given fixed-point function is called with a separate argument than if it was evaluated with `lib.fix`.
 199     :::
 200
 201     :::{.example}
 202
 203     # Extend a fixed-point function with an overlay
 204
 205     Define a fixed-point function `f` that expects its own output as the argument `final`:
 206
 207     ```nix-repl
 208     f = final: {
 209       # Constant value a
 210       a = 1;
 211
 212       # b depends on the final value of a, available as final.a
 213       b = final.a + 2;
 214     }
 215     ```
 216
 217     Evaluate this using [`lib.fix`](#function-library-lib.fixedPoints.fix) to get the final result:
 218
 219     ```nix-repl
 220     fix f
 221     => { a = 1; b = 3; }
 222     ```
 223
 224     An overlay represents a modification or extension of such a fixed-point function.
 225     Here's an example of an overlay:
 226
 227     ```nix-repl
 228     overlay = final: prev: {
 229       # Modify the previous value of a, available as prev.a
 230       a = prev.a + 10;
 231
 232       # Extend the attribute set with c, letting it depend on the final values of a and b
 233       c = final.a + final.b;
 234     }
 235     ```
 236
 237     Use `extends overlay f` to apply the overlay to the fixed-point function `f`.
 238     This produces a new fixed-point function `g` with the combined behavior of `f` and `overlay`:
 239
 240     ```nix-repl
 241     g = extends overlay f
 242     ```
 243
 244     The result is a function, so we can't print it directly, but it's the same as:
 245
 246     ```nix-repl
 247     g' = final: {
 248       # The constant from f, but changed with the overlay
 249       a = 1 + 10;
 250
 251       # Unchanged from f
 252       b = final.a + 2;
 253
 254       # Extended in the overlay
 255       c = final.a + final.b;
 256     }
 257     ```
 258
 259     Evaluate this using [`lib.fix`](#function-library-lib.fixedPoints.fix) again to get the final result:
 260
 261     ```nix-repl
 262     fix g
 263     => { a = 11; b = 13; c = 24; }
 264     ```
 265     :::
 266
 267     # Inputs
 268
 269     `overlay`
 270
 271     : The overlay to apply to the fixed-point function
 272
 273     `f`
 274
 275     : The fixed-point function
 276
 277     # Type
 278
 279     ```
 280     extends :: (Attrs -> Attrs -> Attrs) # The overlay to apply to the fixed-point function
 281             -> (Attrs -> Attrs) # A fixed-point function
 282             -> (Attrs -> Attrs) # The resulting fixed-point function
 283     ```
 284
 285     # Examples
 286     :::{.example}
 287     ## `lib.fixedPoints.extends` usage example
 288
 289     ```nix
 290     f = final: { a = 1; b = final.a + 2; }
 291
 292     fix f
 293     => { a = 1; b = 3; }
 294
 295     fix (extends (final: prev: { a = prev.a + 10; }) f)
 296     => { a = 11; b = 13; }
 297
 298     fix (extends (final: prev: { b = final.a + 5; }) f)
 299     => { a = 1; b = 6; }
 300
 301     fix (extends (final: prev: { c = final.a + final.b; }) f)
 302     => { a = 1; b = 3; c = 4; }
 303     ```
 304
 305     :::
 306   */
 307   extends =
 308     overlay: f:
 309     # The result should be thought of as a function, the argument of that function is not an argument to `extends` itself
 310     (
 311       final:
 312       let
 313         prev = f final;
 314       in
 315       prev // overlay final prev
 316     );
 317
 318   /**
 319     Compose two overlay functions and return a single overlay function that combines them.
 320     For more details see: [composeManyExtensions](#function-library-lib.fixedPoints.composeManyExtensions).
 321   */
 322   composeExtensions =
 323     f: g: final: prev:
 324     let
 325       fApplied = f final prev;
 326       prev' = prev // fApplied;
 327     in
 328     fApplied // g final prev';
 329
 330   /**
 331     Composes a list of [`overlays`](#chap-overlays) and returns a single overlay function that combines them.
 332
 333     :::{.note}
 334     The result is produced by using the update operator `//`.
 335     This means nested values of previous overlays are not merged recursively.
 336     In other words, previously defined attributes are replaced, ignoring the previous value, unless referenced by the overlay; for example `final: prev: { foo = final.foo + 1; }`.
 337     :::
 338
 339     # Inputs
 340
 341     `extensions`
 342
 343     : A list of overlay functions
 344       :::{.note}
 345       The order of the overlays in the list is important.
 346       :::
 347
 348     : Each overlay function takes two arguments, by convention `final` and `prev`, and returns an attribute set.
 349       - `final` is the result of the fixed-point function, with all overlays applied.
 350       - `prev` is the result of the previous overlay function(s).
 351
 352     # Type
 353
 354     ```
 355     # Pseudo code
 356     let
 357       #               final      prev
 358       #                 ↓          ↓
 359       OverlayFn = { ... } -> { ... } -> { ... };
 360     in
 361       composeManyExtensions :: ListOf OverlayFn -> OverlayFn
 362     ```
 363
 364     # Examples
 365     :::{.example}
 366     ## `lib.fixedPoints.composeManyExtensions` usage example
 367
 368     ```nix
 369     let
 370       # The "original function" that is extended by the overlays.
 371       # Note that it doesn't have prev: as argument since no overlay function precedes it.
 372       original = final: { a = 1; };
 373
 374       # Each overlay function has 'final' and 'prev' as arguments.
 375       overlayA = final: prev: { b = final.c; c = 3; };
 376       overlayB = final: prev: { c = 10; x = prev.c or 5; };
 377
 378       extensions = composeManyExtensions [ overlayA overlayB ];
 379
 380       # Caluculate the fixed point of all composed overlays.
 381       fixedpoint = lib.fix (lib.extends extensions original );
 382
 383     in fixedpoint
 384     =>
 385     {
 386       a = 1;
 387       b = 10;
 388       c = 10;
 389       x = 3;
 390     }
 391     ```
 392     :::
 393   */
 394   composeManyExtensions = lib.foldr (x: y: composeExtensions x y) (final: prev: { });
 395
 396   /**
 397     Create an overridable, recursive attribute set. For example:
 398
 399     ```
 400     nix-repl> obj = makeExtensible (final: { })
 401
 402     nix-repl> obj
 403     { __unfix__ = «lambda»; extend = «lambda»; }
 404
 405     nix-repl> obj = obj.extend (final: prev: { foo = "foo"; })
 406
 407     nix-repl> obj
 408     { __unfix__ = «lambda»; extend = «lambda»; foo = "foo"; }
 409
 410     nix-repl> obj = obj.extend (final: prev: { foo = prev.foo + " + "; bar = "bar"; foobar = final.foo + final.bar; })
 411
 412     nix-repl> obj
 413     { __unfix__ = «lambda»; bar = "bar"; extend = «lambda»; foo = "foo + "; foobar = "foo + bar"; }
 414     ```
 415   */
 416   makeExtensible = makeExtensibleWithCustomName "extend";
 417
 418   /**
 419     Same as `makeExtensible` but the name of the extending attribute is
 420     customized.
 421
 422     # Inputs
 423
 424     `extenderName`
 425
 426     : 1\. Function argument
 427
 428     `rattrs`
 429
 430     : 2\. Function argument
 431   */
 432   makeExtensibleWithCustomName =
 433     extenderName: rattrs:
 434     fix' (
 435       self:
 436       (rattrs self)
 437       // {
 438         ${extenderName} = f: makeExtensibleWithCustomName extenderName (extends f rattrs);
 439       }
 440     );
 441
 442   /**
 443     Convert to an extending function (overlay).
 444
 445     `toExtension` is the `toFunction` for extending functions (a.k.a. extensions or overlays).
 446     It converts a non-function or a single-argument function to an extending function,
 447     while returning a two-argument function as-is.
 448
 449     That is, it takes a value of the shape `x`, `prev: x`, or `final: prev: x`,
 450     and returns `final: prev: x`, assuming `x` is not a function.
 451
 452     This function takes care of the input to `stdenv.mkDerivation`'s
 453     `overrideAttrs` function.
 454     It bridges the gap between `<pkg>.overrideAttrs`
 455     before and after the overlay-style support.
 456
 457     # Inputs
 458
 459     `f`
 460     : The function or value to convert to an extending function.
 461
 462     # Type
 463
 464     ```
 465     toExtension ::
 466       b' -> Any -> Any -> b'
 467     or
 468     toExtension ::
 469       (a -> b') -> Any -> a -> b'
 470     or
 471     toExtension ::
 472       (a -> a -> b) -> a -> a -> b
 473     where b' = ! Callable
 474
 475     Set a = b = b' = AttrSet & ! Callable to make toExtension return an extending function.
 476     ```
 477
 478     # Examples
 479     :::{.example}
 480     ## `lib.fixedPoints.toExtension` usage example
 481
 482     ```nix
 483     fix (final: { a = 0; c = final.a; })
 484     => { a = 0; c = 0; };
 485
 486     fix (extends (toExtension { a = 1; b = 2; }) (final: { a = 0; c = final.a; }))
 487     => { a = 1; b = 2; c = 1; };
 488
 489     fix (extends (toExtension (prev: { a = 1; b = prev.a; })) (final: { a = 0; c = final.a; }))
 490     => { a = 1; b = 0; c = 1; };
 491
 492     fix (extends (toExtension (final: prev: { a = 1; b = prev.a; c = final.a + 1 })) (final: { a = 0; c = final.a; }))
 493     => { a = 1; b = 0; c = 2; };
 494     ```
 495     :::
 496   */
 497   toExtension =
 498     f:
 499     if lib.isFunction f then
 500       final: prev:
 501       let
 502         fPrev = f prev;
 503       in
 504       if lib.isFunction fPrev then
 505         # f is (final: prev: { ... })
 506         f final prev
 507       else
 508         # f is (prev: { ... })
 509         fPrev
 510     else
 511       # f is not a function; probably { ... }
 512       final: prev: f;
 513 }