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
22prog="${0##*/}"
23SCRATCH="$(${MKTEMP} -d "/var/tmp/${prog}.XXXXXX")"
24NEXTLEFTOVERS="${SCRATCH}/leftovers0"
25LASTJOIN="${SCRATCH}/join0"
26NEXTJOIN="${SCRATCH}/join1"
27TAB="	"
28
29${SORT} -k 1 > "${LASTJOIN}"
30
31LEFTOVERS="${LASTJOIN}"
32
33while [ "$(${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
72done
73
74#
75# Output all of the dependencies that were not culled and clean up.
76#
77cat "${LEFTOVERS}"
78rm -r "${SCRATCH}"
79