distrib/sets/culldeps

   1 #!/bin/sh
   2 #
   3 # culldeps
   4 #
   5 # Filter redundant dependencies.
   6 #
   7 # Each line of input and output contains two syspkg names,
   8 # where the first syspkg depends on the second syspkg.
   9 #
  10 # Emit all the dependencies on the standard input to the standard
  11 # output EXCEPT the dependencies which can be derived from other
  12 # dependencies by the transitive rule. For example, omit both A C
  13 # and A D from
  14 #
  15 #       A B
  16 #       B C
  17 #       C D
  18 #       A C
  19 #       A D
  20 #
  21 # because A C can be derived from A B and B C by transitivity,
  22 # and A D can be derived from A B, B C, C D by transitivity.
  23 #
  24
  25 prog="${0##*/}"
  26 rundir="$(dirname "$0")" # ${0%/*} isn't good enough when there's no "/"
  27 . "${rundir}/sets.subr"
  28
  29 SCRATCH="$(${MKTEMP} -d "/var/tmp/${prog}.XXXXXX")"
  30 NEXTLEFTOVERS="${SCRATCH}/leftovers0"
  31 LASTJOIN="${SCRATCH}/join0"
  32 NEXTJOIN="${SCRATCH}/join1"
  33 TAB="   "
  34
  35 ${SORT} -k 1 > "${LASTJOIN}"
  36
  37 LEFTOVERS="${LASTJOIN}"
  38
  39 while [ "$(${WC} -l "${LASTJOIN}" | ${AWK} '{ print $1; }')" -ne 0 ]; do
  40
  41         #
  42         # From dependencies X-requires-Y in ${LEFTOVERS} and Y-requires-Z in
  43         # ${LASTJOIN}, produce dependencies X-requires-Z and write them to
  44         # ${NEXTJOIN}.
  45         #
  46         ${SORT} -k 2 < "${LEFTOVERS}" | \
  47             ${JOIN} -1 2 -2 1 -o '1.1 2.2' - "${LASTJOIN}" | \
  48             ${SORT} -u > "${NEXTJOIN}"
  49         if [ ${DEBUG:-0} -gt 0 ]; then
  50                 echo >&2 "${prog}: ### begin filtered results ###"
  51                 ${JOIN} -t "${TAB}" "${NEXTJOIN}" "${LEFTOVERS}" | ${SORT} 1>&2
  52                 echo >&2 "${prog}: ### end filtered results ###"
  53         fi
  54
  55         #
  56         # Filter out of ${LEFTOVERS} all of the dependencies X-requires-Z, which
  57         # were produced in the previous step. Write the new leftovers to
  58         # ${NEXTLEFTOVERS}.
  59         #
  60         ${JOIN} -v 2 -t "${TAB}" "${NEXTJOIN}" "${LEFTOVERS}" | \
  61                 ${SORT} -u > "${NEXTLEFTOVERS}"
  62
  63         #
  64         # Swap output files before repeating.
  65         #
  66         LASTJOIN="${NEXTJOIN}"
  67         if [ "$(basename "${NEXTJOIN}")" = join0 ]; then
  68                 NEXTJOIN="${SCRATCH}/join1"
  69         else
  70                 NEXTJOIN="${SCRATCH}/join0"
  71         fi
  72         LEFTOVERS="${NEXTLEFTOVERS}"
  73         if [ "$(basename "${NEXTLEFTOVERS}")" = leftovers0 ]; then
  74                 NEXTLEFTOVERS="${SCRATCH}/leftovers1"
  75         else
  76                 NEXTLEFTOVERS="${SCRATCH}/leftovers0"
  77         fi
  78 done
  79
  80 #
  81 # Output all of the dependencies that were not culled and clean up.
  82 #
  83 cat "${LEFTOVERS}"
  84 rm -r "${SCRATCH}"