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