Home | History | Annotate | Line # | Download | only in sets
culldeps revision 1.3
      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 SCRATCH="$(${MKTEMP} -d "/var/tmp/${prog}.XXXXXX")"
     24 NEXTLEFTOVERS="${SCRATCH}/leftovers0"
     25 LASTJOIN="${SCRATCH}/join0"
     26 NEXTJOIN="${SCRATCH}/join1"
     27 TAB="	"
     28 
     29 ${SORT} -k 1 > "${LASTJOIN}"
     30 
     31 LEFTOVERS="${LASTJOIN}"
     32 
     33 while [ "$(${WC} -l "${LASTJOIN}" | ${AWK} '{ print $1; }')" -ne 0 ]; do
     34 
     35 	#
     36 	# From dependencies X-requires-Y in ${LEFTOVERS} and Y-requires-Z in
     37 	# ${LASTJOIN}, produce dependencies X-requires-Z and write them to
     38 	# ${NEXTJOIN}.
     39 	#
     40 	${SORT} -k 2 < "${LEFTOVERS}" | \
     41 	    ${JOIN} -1 2 -2 1 -o '1.1 2.2' - "${LASTJOIN}" | \
     42 	    ${SORT} -u > "${NEXTJOIN}"
     43 	if [ ${DEBUG:-0} -gt 0 ]; then
     44 		echo "### filtered ###" 1>&2
     45 		${JOIN} -t "${TAB}" "${NEXTJOIN}" "${LEFTOVERS}" | ${SORT} 1>&2
     46 		echo "###" 1>&2
     47 	fi
     48 
     49 	#
     50 	# Filter out of ${LEFTOVERS} all of the dependencies X-requires-Z, which
     51 	# were produced in the previous step. Write the new leftovers to
     52 	# ${NEXTLEFTOVERS}.
     53 	#
     54 	${JOIN} -v 2 -t "${TAB}" "${NEXTJOIN}" "${LEFTOVERS}" | \
     55 		${SORT} -u > "${NEXTLEFTOVERS}"
     56 
     57 	#
     58 	# Swap output files before repeating. 
     59 	#
     60 	LASTJOIN="${NEXTJOIN}"
     61 	if [ "$(basename "${NEXTJOIN}")" = join0 ]; then
     62 		NEXTJOIN="${SCRATCH}/join1"
     63 	else
     64 		NEXTJOIN="${SCRATCH}/join0"
     65 	fi
     66 	LEFTOVERS="${NEXTLEFTOVERS}"
     67 	if [ "$(basename "${NEXTLEFTOVERS}")" = leftovers0 ]; then
     68 		NEXTLEFTOVERS="${SCRATCH}/leftovers1"
     69 	else
     70 		NEXTLEFTOVERS="${SCRATCH}/leftovers0"
     71 	fi
     72 done
     73 
     74 #
     75 # Output all of the dependencies that were not culled and clean up.
     76 #
     77 cat "${LEFTOVERS}"
     78 rm -r "${SCRATCH}"
     79