Home | History | Annotate | Line # | Download | only in sets 
      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}"
     85