textClosureList
lib.textClosureList
Docs pulled from | This Revision | about 2 hours ago
Topologically sort a collection of dependent strings.
Only the values to keys listed in arg and their dependencies will be included in the result.
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;