textClosureList
lib.stringsWithDeps.textClosureList
Topologically sort a collection of dependent strings.
Only the values to keys listed in arg
and their dependencies will be included in the result.
::: {.note} This function doesn't formally fulfill the definition of topological sorting, but it's good enough for our purposes in Nixpkgs. :::
Inputs
predefined
(attribute set)-
strings with annotated dependencies (strings or attribute set) A value can be a simple string if it has no dependencies. Otherwise, is can be an attribute set with the following attributes:
deps
(list of strings)text
(Any
arg
(list of strings)-
Keys for which the values in the dependency closure will be included in the result
Type
textClosureList :: { ${phase} :: { deps :: [String]; text :: String; } | String; } -> [String] -> [String]
Examples
lib.stringsWithDeps.textClosureList
usage example
textClosureList {
a = {
deps = [ "b" "c" "e" ];
text = "a: depends on b, c and e";
};
b = {
deps = [ ];
text = "b: no dependencies";
};
c = {
deps = [ "b" ];
text = "c: depends on b";
};
d = {
deps = [ "c" ];
text = "d: not being depended on by anything in `arg`";
};
e = {
deps = [ "c" ];
text = "e: depends on c, depended on by a, not in `arg`";
};
} [
"a"
"b"
"c"
]
=> [
"b: no dependencies"
"c: depends on b"
"e: depends on c, depended on by a, not in `arg`"
"a: depends on b, c and e"
]
Common real world usages are:
- Ordering the dependent phases of
system.activationScripts
- Ordering the dependent phases of
system.userActivationScripts
For further examples see: NixOS activation script
Noogle detected
Implementation
The following is the current implementation of this function.
textClosureList =
predefined: arg:
let
f =
done: todo:
if todo == [ ] then
{
result = [ ];
inherit done;
}
else
let
entry = head todo;
in
if isAttrs entry then
let
x = f done entry.deps;
y = f x.done (tail todo);
in
{
result = x.result ++ [ entry.text ] ++ y.result;
done = y.done;
}
else if done ? ${entry} then
f done (tail todo)
else
f (
done
// listToAttrs [
{
name = entry;
value = 1;
}
]
) ([ predefined.${entry} ] ++ tail todo);
in
(f { } arg).result;