query
On this page

textClosureList

lib.stringsWithDeps.textClosureList

Docs pulled from | This Revision | 10 minutes 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.

::: {.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

Aliases

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;