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
22prog="${0##*/}"
23rundir="$(dirname "$0")" # ${0%/*} isn't good enough when there's no "/"
24. "${rundir}/sets.subr"
25
26SCRATCH="$(${MKTEMP} -d "/var/tmp/${prog}.XXXXXX")"
27NEXTLEFTOVERS="${SCRATCH}/leftovers0"
28LASTJOIN="${SCRATCH}/join0"
29NEXTJOIN="${SCRATCH}/join1"
30TAB="	"
31
32${SORT} -k 1 > "${LASTJOIN}"
33
34LEFTOVERS="${LASTJOIN}"
35
36while [ "$(${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
75done
76
77#
78# Output all of the dependencies that were not culled and clean up.
79#
80cat "${LEFTOVERS}"
81rm -r "${SCRATCH}"
82