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