11.1Sdyoung#!/bin/sh
21.1Sdyoung#
31.1Sdyoung# culldeps
41.1Sdyoung#
51.1Sdyoung# Filter redundant dependencies.
61.1Sdyoung#
71.6Sapb# Each line of input and output contains two syspkg names,
81.6Sapb# where the first syspkg depends on the second syspkg.
91.6Sapb#
101.1Sdyoung# Emit all the dependencies on the standard input to the standard
111.1Sdyoung# output EXCEPT the dependencies which can be derived from other
121.1Sdyoung# dependencies by the transitive rule. For example, omit both A C
131.1Sdyoung# and A D from
141.1Sdyoung#
151.1Sdyoung# 	A B
161.1Sdyoung# 	B C
171.1Sdyoung# 	C D
181.1Sdyoung# 	A C
191.1Sdyoung# 	A D
201.1Sdyoung#
211.1Sdyoung# because A C can be derived from A B and B C by transitivity,
221.1Sdyoung# and A D can be derived from A B, B C, C D by transitivity.
231.1Sdyoung#
241.1Sdyoung
251.3Sapbprog="${0##*/}"
261.4Sapbrundir="$(dirname "$0")" # ${0%/*} isn't good enough when there's no "/"
271.4Sapb. "${rundir}/sets.subr"
281.4Sapb
291.3SapbSCRATCH="$(${MKTEMP} -d "/var/tmp/${prog}.XXXXXX")"
301.3SapbNEXTLEFTOVERS="${SCRATCH}/leftovers0"
311.3SapbLASTJOIN="${SCRATCH}/join0"
321.3SapbNEXTJOIN="${SCRATCH}/join1"
331.1SdyoungTAB="	"
341.1Sdyoung
351.3Sapb${SORT} -k 1 > "${LASTJOIN}"
361.1Sdyoung
371.3SapbLEFTOVERS="${LASTJOIN}"
381.1Sdyoung
391.3Sapbwhile [ "$(${WC} -l "${LASTJOIN}" | ${AWK} '{ print $1; }')" -ne 0 ]; do
401.1Sdyoung
411.1Sdyoung	#
421.3Sapb	# From dependencies X-requires-Y in ${LEFTOVERS} and Y-requires-Z in
431.3Sapb	# ${LASTJOIN}, produce dependencies X-requires-Z and write them to
441.3Sapb	# ${NEXTJOIN}.
451.1Sdyoung	#
461.3Sapb	${SORT} -k 2 < "${LEFTOVERS}" | \
471.3Sapb	    ${JOIN} -1 2 -2 1 -o '1.1 2.2' - "${LASTJOIN}" | \
481.3Sapb	    ${SORT} -u > "${NEXTJOIN}"
491.1Sdyoung	if [ ${DEBUG:-0} -gt 0 ]; then
501.5Sapb		echo >&2 "${prog}: ### begin filtered results ###"
511.3Sapb		${JOIN} -t "${TAB}" "${NEXTJOIN}" "${LEFTOVERS}" | ${SORT} 1>&2
521.5Sapb		echo >&2 "${prog}: ### end filtered results ###"
531.1Sdyoung	fi
541.1Sdyoung
551.1Sdyoung	#
561.3Sapb	# Filter out of ${LEFTOVERS} all of the dependencies X-requires-Z, which
571.1Sdyoung	# were produced in the previous step. Write the new leftovers to
581.3Sapb	# ${NEXTLEFTOVERS}.
591.1Sdyoung	#
601.3Sapb	${JOIN} -v 2 -t "${TAB}" "${NEXTJOIN}" "${LEFTOVERS}" | \
611.3Sapb		${SORT} -u > "${NEXTLEFTOVERS}"
621.1Sdyoung
631.1Sdyoung	#
641.1Sdyoung	# Swap output files before repeating. 
651.1Sdyoung	#
661.3Sapb	LASTJOIN="${NEXTJOIN}"
671.3Sapb	if [ "$(basename "${NEXTJOIN}")" = join0 ]; then
681.3Sapb		NEXTJOIN="${SCRATCH}/join1"
691.1Sdyoung	else
701.3Sapb		NEXTJOIN="${SCRATCH}/join0"
711.1Sdyoung	fi
721.3Sapb	LEFTOVERS="${NEXTLEFTOVERS}"
731.3Sapb	if [ "$(basename "${NEXTLEFTOVERS}")" = leftovers0 ]; then
741.3Sapb		NEXTLEFTOVERS="${SCRATCH}/leftovers1"
751.1Sdyoung	else
761.3Sapb		NEXTLEFTOVERS="${SCRATCH}/leftovers0"
771.1Sdyoung	fi
781.1Sdyoungdone
791.1Sdyoung
801.1Sdyoung#
811.1Sdyoung# Output all of the dependencies that were not culled and clean up.
821.1Sdyoung#
831.3Sapbcat "${LEFTOVERS}"
841.3Sapbrm -r "${SCRATCH}"
85