How to implement this recursive algorithm in Nix (shared object being built up)

1

See cyclic dependencies need grouping · Issue #198 · nix-community/dream2nix · GitHub

  • given a package pkg and a set of seen = {dep = true} and a list of cycles = [ [dep...]... ] :
    • for each dependency, check if it is in seen
      • if so:
        • if dep is already in a cycle, add pkg to it (*)
        • if not, create a new cycle [dep, pkg] (*)
        • (*) note that due to siblings, pkg could already be in a cycle. In this case, the cycles have to be merged, not just the pkg.
        • (so this stops recursion)
      • if not: call this search with pkg=dep, and pass seen = seen // {pkg=true} ; the cycles need to be shared between the recursive calls

Call the algorithm on pkg with seen = {} .

So, passing a seen attribute that is recursively augmented is easy, but how to express that cycles object that should grow as the dependency tree is traversed?

2

See genericClosure

1 Like