1#!/bin/sh
2#
3# culldeps
4#
5# Filter redundant dependencies.
6#
7# Each line of input and output contains two syspkg names,
8# where the first syspkg depends on the second syspkg.
9#
10# Emit all the dependencies on the standard input to the standard
11# output EXCEPT the dependencies which can be derived from other
12# dependencies by the transitive rule. For example, omit both A C
13# and A D from
14#
15# 	A B
16# 	B C
17# 	C D
18# 	A C
19# 	A D
20#
21# because A C can be derived from A B and B C by transitivity,
22# and A D can be derived from A B, B C, C D by transitivity.
23#
24
25prog="${0##*/}"
26rundir="$(dirname "$0")" # ${0%/*} isn't good enough when there's no "/"
27. "${rundir}/sets.subr"
28
29SCRATCH="$(${MKTEMP} -d "/var/tmp/${prog}.XXXXXX")"
30NEXTLEFTOVERS="${SCRATCH}/leftovers0"
31LASTJOIN="${SCRATCH}/join0"
32NEXTJOIN="${SCRATCH}/join1"
33TAB="	"
34
35${SORT} -k 1 > "${LASTJOIN}"
36
37LEFTOVERS="${LASTJOIN}"
38
39while [ "$(${WC} -l "${LASTJOIN}" | ${AWK} '{ print $1; }')" -ne 0 ]; do
40
41	#
42	# From dependencies X-requires-Y in ${LEFTOVERS} and Y-requires-Z in
43	# ${LASTJOIN}, produce dependencies X-requires-Z and write them to
44	# ${NEXTJOIN}.
45	#
46	${SORT} -k 2 < "${LEFTOVERS}" | \
47	    ${JOIN} -1 2 -2 1 -o '1.1 2.2' - "${LASTJOIN}" | \
48	    ${SORT} -u > "${NEXTJOIN}"
49	if [ ${DEBUG:-0} -gt 0 ]; then
50		echo >&2 "${prog}: ### begin filtered results ###"
51		${JOIN} -t "${TAB}" "${NEXTJOIN}" "${LEFTOVERS}" | ${SORT} 1>&2
52		echo >&2 "${prog}: ### end filtered results ###"
53	fi
54
55	#
56	# Filter out of ${LEFTOVERS} all of the dependencies X-requires-Z, which
57	# were produced in the previous step. Write the new leftovers to
58	# ${NEXTLEFTOVERS}.
59	#
60	${JOIN} -v 2 -t "${TAB}" "${NEXTJOIN}" "${LEFTOVERS}" | \
61		${SORT} -u > "${NEXTLEFTOVERS}"
62
63	#
64	# Swap output files before repeating. 
65	#
66	LASTJOIN="${NEXTJOIN}"
67	if [ "$(basename "${NEXTJOIN}")" = join0 ]; then
68		NEXTJOIN="${SCRATCH}/join1"
69	else
70		NEXTJOIN="${SCRATCH}/join0"
71	fi
72	LEFTOVERS="${NEXTLEFTOVERS}"
73	if [ "$(basename "${NEXTLEFTOVERS}")" = leftovers0 ]; then
74		NEXTLEFTOVERS="${SCRATCH}/leftovers1"
75	else
76		NEXTLEFTOVERS="${SCRATCH}/leftovers0"
77	fi
78done
79
80#
81# Output all of the dependencies that were not culled and clean up.
82#
83cat "${LEFTOVERS}"
84rm -r "${SCRATCH}"
85