Print package dependency tree

Question

Using this file, I would like to print a tree of package dependencies, given a single base package. For example, take the Bash package

@ bash
# few lines removed
requires: coreutils libintl8 libncursesw10 libreadline7 _update-info-dir cygwin

I would like find-like output of the required packages, partial example

bash
bash coreutils
bash coreutils libattr1
bash coreutils libattr1 libintl8
bash coreutils libattr1 libintl8 libiconv2
bash coreutils libattr1 libintl8 _autorebase
bash coreutils libattr1 libintl8 _autorebase rebase
bash coreutils libattr1 libintl8 _autorebase rebase dash
bash coreutils libattr1 libintl8 _autorebase rebase dash cygwin
bash coreutils libattr1 libintl8 _autorebase rebase dash cygwin base-cygwin

I have this command but it does not recurse

#!awk -f
$1 == "@" {
  pkg = $2
}
$1 == "requires:" {
  for (i=2; i<=NF; i++)
    reqs[pkg][i-1] = $i
}
END {
  query = "bash"
  for (pkg in reqs[query]) {
    print reqs[query][pkg]
  }
}

Answer 1

With Perl and no comments:

perl -lne '
  $k = $1 if /@\s*(\S+)/; 
  @r=split(); shift @r; $r{$k} = [@r] if /requires:/;
  END{
    $p = "bash"; @l = ( [$p, 0] );
    while ($p = pop @l) {
        next if $d{$p->[0]}++;
        print " " x $p->[1] . $p->[0];
        for $d(@{$r{$p->[0]}}) {
            push @l, [ $d, $p->[1]+1 ];
        }
    }
  }' setup.ini

Awk version:

awk '/^@ / { split($0, b); k = b[2]; }
     /^requires: / { a[k] = $0; }
     END {
       p[1] = "bash"; d["bash"] = 0;
       while (length(p)) {
           key = p[length(p)]; depth = d[key]; delete p[length(p)];
           if (!s[key]++) {
               printf "%*s %s\n", depth, "", key;
               split(a[key], r); delete r[1];
               for (req in r) {
                   p[length(p) + 1] = r[req]; d[r[req]] = depth + 1;
               }
           }
       }
     }
' setup.ini

Answer 2

Using GNU awk for true multi-D arrays (but can obviously be tweaked for other awks):

$ cat tst.awk
/^@/         { pkg = $2 }
/^requires:/ { for (i=2;i<=NF;i++) reqs[pkg][$i]  }
END          { prtPkg(root) }

function prtPkg(pkg,    req) {
    if (!seen[pkg]++) {
        printf "%*s%s\n", indent, "", pkg
        indent += 2
        if (pkg in reqs)
            for (req in reqs[pkg])
                prtPkg(req)
        indent -= 2
    }
}

.

$ cat file3
@ bash
whatever
requires: libgcc1 libintl8 libncursesw10 libreadline7 _update-info-dir

@ libintl8
whatever
requires: libiconv2 bash common

@ libgcc1
whatever
requires: _autorebase common

.

$ awk -v root="bash" -f tst.awk file3
bash
  libncursesw10
  libgcc1
    _autorebase
    common
  _update-info-dir
  libreadline7
  libintl8
    libiconv2

Here is what we'd need for the new output format you'd like:

$ cat file3
@ bash
requires: libgcc1 libintl8 libncursesw10 libreadline7

@ libncursesw10
requires: libgcc1 libstdc++6 terminfo libreadline7

.

$ cat tst.awk
/^@/         { pkg = $2 }
/^requires:/ { for (i=2;i<=NF;i++) reqs[pkg][i-1]=$i  }
END          { setMinDepth(root); prtPkg(root) }

function setMinDepth(pkg,    req, i) {
    depth++
    minDepth[pkg] = ( !(pkg in minDepth) || (depth < minDepth[pkg]) ?
                        depth : minDepth[pkg])

    if (depth == minDepth[pkg]) {
        if (pkg in reqs)
            for (i=1; i in reqs[pkg]; i++) {
                req = reqs[pkg][i]
                setMinDepth(req)
            }
    }
    depth--
}

function prtPkg(pkg,    req, i) {
    depth++
    if ( (depth == minDepth[pkg]) && (!seen[pkg]++) ) {
        printf "%*s%s\n", indent, "", pkg
        indent += 2
        if (pkg in reqs)
            for (i=1; i in reqs[pkg]; i++) {
                req = reqs[pkg][i]
                prtPkg(req)
            }
        indent -= 2
    }
    depth--
}

.

$ awk -v root="bash" -f tst.awk file3
bash
  libgcc1
  libintl8
  libncursesw10
    libstdc++6
    terminfo
  libreadline7