fork/home-manager
git clone https://git.julia.blue/fork/home-manager
28614ed7
master
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 { 14empty = { }; 15 16isEntry = e :e ?data && e ?after && e ?before ; 17isDag = dag : 18builtins . 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 76topoSort = dag : 77let 78dagBefore = dag :name : 79builtins . attrNames 80( filterAttrs ( n :v :builtins . elem name v . before ) dag ); 81normalizedDag = mapAttrs ( n :v :{ 82name = n ; 83data = v . data ; 84after = v . after ++ dagBefore dag n ; 85}) dag ; 86before = a :b :builtins . elem a . name b . after ; 87sorted = toposort before ( builtins . attrValues normalizedDag ); 88in if sorted ?result then { 89result = map ( v :{ inherit ( v ) name data ; }) sorted . result ; 90} else 91sorted ; 92 93# Applies a function to each element of the given DAG. 94map = f :mapAttrs ( n :v :v // { data = f n v . data ; }); 95 96entryBetween = before :after :data :{ inherit data before after ; }; 97 98# Create a DAG entry with no particular dependency information. 99entryAnywhere = hm . dag . entryBetween [ ] [ ]; 100 101entryAfter = hm . dag . entryBetween [ ]; 102entryBefore = 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. 110entriesBetween = tag : 111let 112go = i :before :after :entries : 113let 114name = " ${ tag } - ${ toString i } " ; 115i' = i + 1 ; 116in if entries == [ ] then 117hm . dag . empty 118else 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 ); 124in go 0 ; 125 126entriesAnywhere = tag :hm . dag . entriesBetween tag [ ] [ ]; 127entriesAfter = tag :hm . dag . entriesBetween tag [ ]; 128entriesBefore = tag :before :hm . dag . entriesBetween tag before [ ]; 129}