pyrox.dev
1{ lib, ... }:
2rec {
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: {
164 # attributes
165 }
166 ```
167
168 where `final` refers to the lazily evaluated attribute set returned by the fixed-point function.
169
170 An overlay to such a fixed-point function has the form
171
172 ```nix
173 final: prev: {
174 # attributes
175 }
176 ```
177
178 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.
179
180 Applying an overlay is done with `extends`:
181
182 ```nix
183 let
184 f = final: {
185 # attributes
186 };
187 overlay = final: prev: {
188 # attributes
189 };
190 in extends overlay f;
191 ```
192
193 To get the value of `final`, use `lib.fix`:
194
195 ```nix
196 let
197 f = final: {
198 # attributes
199 };
200 overlay = final: prev: {
201 # attributes
202 };
203 g = extends overlay f;
204 in fix g
205 ```
206
207 :::{.note}
208 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.
209
210 The given fixed-point function is called with a separate argument than if it was evaluated with `lib.fix`.
211 :::
212
213 :::{.example}
214
215 # Extend a fixed-point function with an overlay
216
217 Define a fixed-point function `f` that expects its own output as the argument `final`:
218
219 ```nix-repl
220 f = final: {
221 # Constant value a
222 a = 1;
223
224 # b depends on the final value of a, available as final.a
225 b = final.a + 2;
226 }
227 ```
228
229 Evaluate this using [`lib.fix`](#function-library-lib.fixedPoints.fix) to get the final result:
230
231 ```nix-repl
232 fix f
233 => { a = 1; b = 3; }
234 ```
235
236 An overlay represents a modification or extension of such a fixed-point function.
237 Here's an example of an overlay:
238
239 ```nix-repl
240 overlay = final: prev: {
241 # Modify the previous value of a, available as prev.a
242 a = prev.a + 10;
243
244 # Extend the attribute set with c, letting it depend on the final values of a and b
245 c = final.a + final.b;
246 }
247 ```
248
249 Use `extends overlay f` to apply the overlay to the fixed-point function `f`.
250 This produces a new fixed-point function `g` with the combined behavior of `f` and `overlay`:
251
252 ```nix-repl
253 g = extends overlay f
254 ```
255
256 The result is a function, so we can't print it directly, but it's the same as:
257
258 ```nix-repl
259 g' = final: {
260 # The constant from f, but changed with the overlay
261 a = 1 + 10;
262
263 # Unchanged from f
264 b = final.a + 2;
265
266 # Extended in the overlay
267 c = final.a + final.b;
268 }
269 ```
270
271 Evaluate this using [`lib.fix`](#function-library-lib.fixedPoints.fix) again to get the final result:
272
273 ```nix-repl
274 fix g
275 => { a = 11; b = 13; c = 24; }
276 ```
277 :::
278
279 # Inputs
280
281 `overlay`
282
283 : The overlay to apply to the fixed-point function
284
285 `f`
286
287 : The fixed-point function
288
289 # Type
290
291 ```
292 extends :: (Attrs -> Attrs -> Attrs) # The overlay to apply to the fixed-point function
293 -> (Attrs -> Attrs) # A fixed-point function
294 -> (Attrs -> Attrs) # The resulting fixed-point function
295 ```
296
297 # Examples
298 :::{.example}
299 ## `lib.fixedPoints.extends` usage example
300
301 ```nix
302 f = final: { a = 1; b = final.a + 2; }
303
304 fix f
305 => { a = 1; b = 3; }
306
307 fix (extends (final: prev: { a = prev.a + 10; }) f)
308 => { a = 11; b = 13; }
309
310 fix (extends (final: prev: { b = final.a + 5; }) f)
311 => { a = 1; b = 6; }
312
313 fix (extends (final: prev: { c = final.a + final.b; }) f)
314 => { a = 1; b = 3; c = 4; }
315 ```
316
317 :::
318 */
319 extends =
320 overlay: f:
321 # The result should be thought of as a function, the argument of that function is not an argument to `extends` itself
322 (
323 final:
324 let
325 prev = f final;
326 in
327 prev // overlay final prev
328 );
329
330 /**
331 Compose two overlay functions and return a single overlay function that combines them.
332 For more details see: [composeManyExtensions](#function-library-lib.fixedPoints.composeManyExtensions).
333 */
334 composeExtensions =
335 f: g: final: prev:
336 let
337 fApplied = f final prev;
338 prev' = prev // fApplied;
339 in
340 fApplied // g final prev';
341
342 /**
343 Composes a list of [`overlays`](#chap-overlays) and returns a single overlay function that combines them.
344
345 :::{.note}
346 The result is produced by using the update operator `//`.
347 This means nested values of previous overlays are not merged recursively.
348 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; }`.
349 :::
350
351 # Inputs
352
353 `extensions`
354
355 : A list of overlay functions
356 :::{.note}
357 The order of the overlays in the list is important.
358 :::
359
360 : Each overlay function takes two arguments, by convention `final` and `prev`, and returns an attribute set.
361 - `final` is the result of the fixed-point function, with all overlays applied.
362 - `prev` is the result of the previous overlay function(s).
363
364 # Type
365
366 ```
367 # Pseudo code
368 let
369 # final prev
370 # ↓ ↓
371 OverlayFn = { ... } -> { ... } -> { ... };
372 in
373 composeManyExtensions :: ListOf OverlayFn -> OverlayFn
374 ```
375
376 # Examples
377 :::{.example}
378 ## `lib.fixedPoints.composeManyExtensions` usage example
379
380 ```nix
381 let
382 # The "original function" that is extended by the overlays.
383 # Note that it doesn't have prev: as argument since no overlay function precedes it.
384 original = final: { a = 1; };
385
386 # Each overlay function has 'final' and 'prev' as arguments.
387 overlayA = final: prev: { b = final.c; c = 3; };
388 overlayB = final: prev: { c = 10; x = prev.c or 5; };
389
390 extensions = composeManyExtensions [ overlayA overlayB ];
391
392 # Calculate the fixed point of all composed overlays.
393 fixedpoint = lib.fix (lib.extends extensions original );
394
395 in fixedpoint
396 =>
397 {
398 a = 1;
399 b = 10;
400 c = 10;
401 x = 3;
402 }
403 ```
404 :::
405 */
406 composeManyExtensions = lib.foldr (x: y: composeExtensions x y) (final: prev: { });
407
408 /**
409 Create an overridable, recursive attribute set. For example:
410
411 ```
412 nix-repl> obj = makeExtensible (final: { })
413
414 nix-repl> obj
415 { __unfix__ = «lambda»; extend = «lambda»; }
416
417 nix-repl> obj = obj.extend (final: prev: { foo = "foo"; })
418
419 nix-repl> obj
420 { __unfix__ = «lambda»; extend = «lambda»; foo = "foo"; }
421
422 nix-repl> obj = obj.extend (final: prev: { foo = prev.foo + " + "; bar = "bar"; foobar = final.foo + final.bar; })
423
424 nix-repl> obj
425 { __unfix__ = «lambda»; bar = "bar"; extend = «lambda»; foo = "foo + "; foobar = "foo + bar"; }
426 ```
427 */
428 makeExtensible = makeExtensibleWithCustomName "extend";
429
430 /**
431 Same as `makeExtensible` but the name of the extending attribute is
432 customized.
433
434 # Inputs
435
436 `extenderName`
437
438 : 1\. Function argument
439
440 `rattrs`
441
442 : 2\. Function argument
443 */
444 makeExtensibleWithCustomName =
445 extenderName: rattrs:
446 fix' (
447 self:
448 (rattrs self)
449 // {
450 ${extenderName} = f: makeExtensibleWithCustomName extenderName (extends f rattrs);
451 }
452 );
453
454 /**
455 Convert to an extending function (overlay).
456
457 `toExtension` is the `toFunction` for extending functions (a.k.a. extensions or overlays).
458 It converts a non-function or a single-argument function to an extending function,
459 while returning a two-argument function as-is.
460
461 That is, it takes a value of the shape `x`, `prev: x`, or `final: prev: x`,
462 and returns `final: prev: x`, assuming `x` is not a function.
463
464 This function takes care of the input to `stdenv.mkDerivation`'s
465 `overrideAttrs` function.
466 It bridges the gap between `<pkg>.overrideAttrs`
467 before and after the overlay-style support.
468
469 # Inputs
470
471 `f`
472 : The function or value to convert to an extending function.
473
474 # Type
475
476 ```
477 toExtension ::
478 b' -> Any -> Any -> b'
479 or
480 toExtension ::
481 (a -> b') -> Any -> a -> b'
482 or
483 toExtension ::
484 (a -> a -> b) -> a -> a -> b
485 where b' = ! Callable
486
487 Set a = b = b' = AttrSet & ! Callable to make toExtension return an extending function.
488 ```
489
490 # Examples
491 :::{.example}
492 ## `lib.fixedPoints.toExtension` usage example
493
494 ```nix
495 fix (final: { a = 0; c = final.a; })
496 => { a = 0; c = 0; };
497
498 fix (extends (toExtension { a = 1; b = 2; }) (final: { a = 0; c = final.a; }))
499 => { a = 1; b = 2; c = 1; };
500
501 fix (extends (toExtension (prev: { a = 1; b = prev.a; })) (final: { a = 0; c = final.a; }))
502 => { a = 1; b = 0; c = 1; };
503
504 fix (extends (toExtension (final: prev: { a = 1; b = prev.a; c = final.a + 1 })) (final: { a = 0; c = final.a; }))
505 => { a = 1; b = 0; c = 2; };
506 ```
507 :::
508 */
509 toExtension =
510 f:
511 if lib.isFunction f then
512 final: prev:
513 let
514 fPrev = f prev;
515 in
516 if lib.isFunction fPrev then
517 # f is (final: prev: { ... })
518 f final prev
519 else
520 # f is (prev: { ... })
521 fPrev
522 else
523 # f is not a function; probably { ... }
524 final: prev: f;
525}