fork/home-manager

git clone https://git.julia.blue/fork/home-manager

Robert Helgessonlib: add functions to create DAGs from lists28614ed7

master
4.3 KiB129 linesraw
1# A generalization of Nixpkgs's `strings-with-deps.nix`.
2#
3# The main differences from the Nixpkgs version are
4#
5#  - not specific to strings, i.e., any payload is OK,
6#
7#  - the addition of the function `entryBefore` indicating a "wanted
8#    by" relationship.
9
10{ lib }:
11
12let inherit (lib) all filterAttrs head hm mapAttrs length tail toposort;
13in {
14  empty = { };
15
16  isEntry = e: e ? data && e ? after && e ? before;
17  isDag = dag:
18    builtins.isAttrs dag && all hm.dag.isEntry (builtins.attrValues dag);
19
20  # Takes an attribute set containing entries built by entryAnywhere,
21  # entryAfter, and entryBefore to a topologically sorted list of
22  # entries.
23  #
24  # Internally this function uses the `toposort` function in
25  # `<nixpkgs/lib/lists.nix>` and its value is accordingly.
26  #
27  # Specifically, the result on success is
28  #
29  #    { result = [ { name = ?; data = ?; } … ] }
30  #
31  # For example
32  #
33  #    nix-repl> topoSort {
34  #                a = entryAnywhere "1";
35  #                b = entryAfter [ "a" "c" ] "2";
36  #                c = entryBefore [ "d" ] "3";
37  #                d = entryBefore [ "e" ] "4";
38  #                e = entryAnywhere "5";
39  #              } == {
40  #                result = [
41  #                  { data = "1"; name = "a"; }
42  #                  { data = "3"; name = "c"; }
43  #                  { data = "2"; name = "b"; }
44  #                  { data = "4"; name = "d"; }
45  #                  { data = "5"; name = "e"; }
46  #                ];
47  #              }
48  #    true
49  #
50  # And the result on error is
51  #
52  #    {
53  #      cycle = [ { after = ?; name = ?; data = ? } … ];
54  #      loops = [ { after = ?; name = ?; data = ? } … ];
55  #    }
56  #
57  # For example
58  #
59  #    nix-repl> topoSort {
60  #                a = entryAnywhere "1";
61  #                b = entryAfter [ "a" "c" ] "2";
62  #                c = entryAfter [ "d" ] "3";
63  #                d = entryAfter [ "b" ] "4";
64  #                e = entryAnywhere "5";
65  #              } == {
66  #                cycle = [
67  #                  { after = [ "a" "c" ]; data = "2"; name = "b"; }
68  #                  { after = [ "d" ]; data = "3"; name = "c"; }
69  #                  { after = [ "b" ]; data = "4"; name = "d"; }
70  #                ];
71  #                loops = [
72  #                  { after = [ "a" "c" ]; data = "2"; name = "b"; }
73  #                ];
74  #              }
75  #    true
76  topoSort = dag:
77    let
78      dagBefore = dag: name:
79        builtins.attrNames
80        (filterAttrs (n: v: builtins.elem name v.before) dag);
81      normalizedDag = mapAttrs (n: v: {
82        name = n;
83        data = v.data;
84        after = v.after ++ dagBefore dag n;
85      }) dag;
86      before = a: b: builtins.elem a.name b.after;
87      sorted = toposort before (builtins.attrValues normalizedDag);
88    in if sorted ? result then {
89      result = map (v: { inherit (v) name data; }) sorted.result;
90    } else
91      sorted;
92
93  # Applies a function to each element of the given DAG.
94  map = f: mapAttrs (n: v: v // { data = f n v.data; });
95
96  entryBetween = before: after: data: { inherit data before after; };
97
98  # Create a DAG entry with no particular dependency information.
99  entryAnywhere = hm.dag.entryBetween [ ] [ ];
100
101  entryAfter = hm.dag.entryBetween [ ];
102  entryBefore = before: hm.dag.entryBetween before [ ];
103
104  # Given a list of entries, this function places them in order within the DAG.
105  # Each entry is labeled "${tag}-${entry index}" and other DAG entries can be
106  # added with 'before' or 'after' referring these indexed entries.
107  #
108  # The entries as a whole can be given a relation to other DAG nodes. All
109  # generated nodes are then placed before or after those dependencies.
110  entriesBetween = tag:
111    let
112      go = i: before: after: entries:
113        let
114          name = "${tag}-${toString i}";
115          i' = i + 1;
116        in if entries == [ ] then
117          hm.dag.empty
118        else if length entries == 1 then {
119          "${name}" = hm.dag.entryBetween before after (head entries);
120        } else
121          {
122            "${name}" = hm.dag.entryAfter after (head entries);
123          } // go (i + 1) before [ name ] (tail entries);
124    in go 0;
125
126  entriesAnywhere = tag: hm.dag.entriesBetween tag [ ] [ ];
127  entriesAfter = tag: hm.dag.entriesBetween tag [ ];
128  entriesBefore = tag: before: hm.dag.entriesBetween tag before [ ];
129}