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