head	1.6;
access;
symbols
	netbsd-11-0-RC7:1.6
	netbsd-11-0-RC6:1.6
	netbsd-11-0-RC5:1.6
	netbsd-11-0-RC4:1.6
	netbsd-11-0-RC3:1.6
	netbsd-11-0-RC2:1.6
	netbsd-11-0-RC1:1.6
	perseant-exfatfs-base-20250801:1.6
	netbsd-11:1.6.0.102
	netbsd-11-base:1.6
	netbsd-10-1-RELEASE:1.6
	perseant-exfatfs-base-20240630:1.6
	perseant-exfatfs:1.6.0.100
	perseant-exfatfs-base:1.6
	netbsd-8-3-RELEASE:1.6
	netbsd-9-4-RELEASE:1.6
	netbsd-10-0-RELEASE:1.6
	netbsd-10-0-RC6:1.6
	netbsd-10-0-RC5:1.6
	netbsd-10-0-RC4:1.6
	netbsd-10-0-RC3:1.6
	netbsd-10-0-RC2:1.6
	netbsd-10-0-RC1:1.6
	netbsd-10:1.6.0.98
	netbsd-10-base:1.6
	netbsd-9-3-RELEASE:1.6
	cjep_sun2x-base1:1.6
	cjep_sun2x:1.6.0.96
	cjep_sun2x-base:1.6
	cjep_staticlib_x-base1:1.6
	netbsd-9-2-RELEASE:1.6
	cjep_staticlib_x:1.6.0.94
	cjep_staticlib_x-base:1.6
	netbsd-9-1-RELEASE:1.6
	phil-wifi-20200421:1.6
	phil-wifi-20200411:1.6
	is-mlppp:1.6.0.92
	is-mlppp-base:1.6
	phil-wifi-20200406:1.6
	netbsd-8-2-RELEASE:1.6
	netbsd-9-0-RELEASE:1.6
	netbsd-9-0-RC2:1.6
	netbsd-9-0-RC1:1.6
	phil-wifi-20191119:1.6
	netbsd-9:1.6.0.90
	netbsd-9-base:1.6
	phil-wifi-20190609:1.6
	netbsd-8-1-RELEASE:1.6
	netbsd-8-1-RC1:1.6
	pgoyette-compat-merge-20190127:1.6
	pgoyette-compat-20190127:1.6
	pgoyette-compat-20190118:1.6
	pgoyette-compat-1226:1.6
	pgoyette-compat-1126:1.6
	pgoyette-compat-1020:1.6
	pgoyette-compat-0930:1.6
	pgoyette-compat-0906:1.6
	netbsd-7-2-RELEASE:1.6
	pgoyette-compat-0728:1.6
	netbsd-8-0-RELEASE:1.6
	phil-wifi:1.6.0.88
	phil-wifi-base:1.6
	pgoyette-compat-0625:1.6
	netbsd-8-0-RC2:1.6
	pgoyette-compat-0521:1.6
	pgoyette-compat-0502:1.6
	pgoyette-compat-0422:1.6
	netbsd-8-0-RC1:1.6
	pgoyette-compat-0415:1.6
	pgoyette-compat-0407:1.6
	pgoyette-compat-0330:1.6
	pgoyette-compat-0322:1.6
	pgoyette-compat-0315:1.6
	netbsd-7-1-2-RELEASE:1.6
	pgoyette-compat:1.6.0.86
	pgoyette-compat-base:1.6
	netbsd-7-1-1-RELEASE:1.6
	matt-nb8-mediatek:1.6.0.84
	matt-nb8-mediatek-base:1.6
	perseant-stdc-iso10646:1.6.0.82
	perseant-stdc-iso10646-base:1.6
	netbsd-8:1.6.0.80
	netbsd-8-base:1.6
	prg-localcount2-base3:1.6
	prg-localcount2-base2:1.6
	prg-localcount2-base1:1.6
	prg-localcount2:1.6.0.78
	prg-localcount2-base:1.6
	pgoyette-localcount-20170426:1.6
	bouyer-socketcan-base1:1.6
	pgoyette-localcount-20170320:1.6
	netbsd-7-1:1.6.0.76
	netbsd-7-1-RELEASE:1.6
	netbsd-7-1-RC2:1.6
	netbsd-7-nhusb-base-20170116:1.6
	bouyer-socketcan:1.6.0.74
	bouyer-socketcan-base:1.6
	pgoyette-localcount-20170107:1.6
	netbsd-7-1-RC1:1.6
	pgoyette-localcount-20161104:1.6
	netbsd-7-0-2-RELEASE:1.6
	localcount-20160914:1.6
	netbsd-7-nhusb:1.6.0.72
	netbsd-7-nhusb-base:1.6
	pgoyette-localcount-20160806:1.6
	pgoyette-localcount-20160726:1.6
	pgoyette-localcount:1.6.0.70
	pgoyette-localcount-base:1.6
	netbsd-7-0-1-RELEASE:1.6
	netbsd-7-0:1.6.0.68
	netbsd-7-0-RELEASE:1.6
	netbsd-7-0-RC3:1.6
	netbsd-7-0-RC2:1.6
	netbsd-7-0-RC1:1.6
	netbsd-5-2-3-RELEASE:1.6
	netbsd-5-1-5-RELEASE:1.6
	netbsd-6-0-6-RELEASE:1.6
	netbsd-6-1-5-RELEASE:1.6
	netbsd-7:1.6.0.66
	netbsd-7-base:1.6
	yamt-pagecache-base9:1.6
	yamt-pagecache-tag8:1.6
	netbsd-6-1-4-RELEASE:1.6
	netbsd-6-0-5-RELEASE:1.6
	tls-earlyentropy:1.6.0.64
	tls-earlyentropy-base:1.6
	riastradh-xf86-video-intel-2-7-1-pre-2-21-15:1.6
	riastradh-drm2-base3:1.6
	netbsd-6-1-3-RELEASE:1.6
	netbsd-6-0-4-RELEASE:1.6
	netbsd-5-2-2-RELEASE:1.6
	netbsd-5-1-4-RELEASE:1.6
	netbsd-6-1-2-RELEASE:1.6
	netbsd-6-0-3-RELEASE:1.6
	netbsd-5-2-1-RELEASE:1.6
	netbsd-5-1-3-RELEASE:1.6
	netbsd-6-1-1-RELEASE:1.6
	riastradh-drm2-base2:1.6
	riastradh-drm2-base1:1.6
	riastradh-drm2:1.6.0.56
	riastradh-drm2-base:1.6
	netbsd-6-1:1.6.0.62
	netbsd-6-0-2-RELEASE:1.6
	netbsd-6-1-RELEASE:1.6
	khorben-n900:1.6.0.60
	netbsd-6-1-RC4:1.6
	netbsd-6-1-RC3:1.6
	agc-symver:1.6.0.58
	agc-symver-base:1.6
	netbsd-6-1-RC2:1.6
	netbsd-6-1-RC1:1.6
	yamt-pagecache-base8:1.6
	netbsd-5-2:1.6.0.54
	netbsd-6-0-1-RELEASE:1.6
	yamt-pagecache-base7:1.6
	netbsd-5-2-RELEASE:1.6
	netbsd-5-2-RC1:1.6
	matt-nb6-plus-nbase:1.6
	yamt-pagecache-base6:1.6
	netbsd-6-0:1.6.0.52
	netbsd-6-0-RELEASE:1.6
	netbsd-6-0-RC2:1.6
	tls-maxphys:1.6.0.50
	tls-maxphys-base:1.6
	matt-nb6-plus:1.6.0.48
	matt-nb6-plus-base:1.6
	netbsd-6-0-RC1:1.6
	yamt-pagecache-base5:1.6
	yamt-pagecache-base4:1.6
	netbsd-6:1.6.0.46
	netbsd-6-base:1.6
	netbsd-5-1-2-RELEASE:1.6
	netbsd-5-1-1-RELEASE:1.6
	yamt-pagecache-base3:1.6
	yamt-pagecache-base2:1.6
	yamt-pagecache:1.6.0.44
	yamt-pagecache-base:1.6
	cherry-xenmp:1.6.0.42
	cherry-xenmp-base:1.6
	bouyer-quota2-nbase:1.6
	bouyer-quota2:1.6.0.40
	bouyer-quota2-base:1.6
	matt-mips64-premerge-20101231:1.6
	matt-nb5-mips64-premerge-20101231:1.6
	matt-nb5-pq3:1.6.0.38
	matt-nb5-pq3-base:1.6
	netbsd-5-1:1.6.0.36
	netbsd-5-1-RELEASE:1.6
	netbsd-5-1-RC4:1.6
	matt-nb5-mips64-k15:1.6
	netbsd-5-1-RC3:1.6
	netbsd-5-1-RC2:1.6
	netbsd-5-1-RC1:1.6
	netbsd-5-0-2-RELEASE:1.6
	matt-nb5-mips64-premerge-20091211:1.6
	matt-premerge-20091211:1.6
	matt-nb5-mips64-u2-k2-k4-k7-k8-k9:1.6
	matt-nb4-mips64-k7-u2a-k9b:1.6
	matt-nb5-mips64-u1-k1-k5:1.6
	matt-nb5-mips64:1.6.0.34
	netbsd-5-0-1-RELEASE:1.6
	jym-xensuspend-nbase:1.6
	netbsd-5-0:1.6.0.32
	netbsd-5-0-RELEASE:1.6
	netbsd-5-0-RC4:1.6
	netbsd-5-0-RC3:1.6
	netbsd-5-0-RC2:1.6
	jym-xensuspend:1.6.0.30
	jym-xensuspend-base:1.6
	netbsd-5-0-RC1:1.6
	netbsd-5:1.6.0.28
	netbsd-5-base:1.6
	matt-mips64-base2:1.6
	matt-mips64:1.6.0.26
	netbsd-4-0-1-RELEASE:1.6
	wrstuden-revivesa-base-3:1.6
	wrstuden-revivesa-base-2:1.6
	wrstuden-fixsa-newbase:1.6
	wrstuden-revivesa-base-1:1.6
	yamt-pf42-base4:1.6
	yamt-pf42-base3:1.6
	hpcarm-cleanup-nbase:1.6
	yamt-pf42-baseX:1.6
	yamt-pf42-base2:1.6
	wrstuden-revivesa:1.6.0.24
	wrstuden-revivesa-base:1.6
	yamt-pf42:1.6.0.22
	yamt-pf42-base:1.6
	mjf-devfs2:1.6.0.20
	mjf-devfs2-base:1.6
	keiichi-mipv6:1.6.0.18
	keiichi-mipv6-base:1.6
	mjf-devfs:1.6.0.16
	mjf-devfs-base:1.6
	matt-armv6-nbase:1.6
	matt-armv6-prevmlocking:1.6
	wrstuden-fixsa-base-1:1.6
	netbsd-4-0:1.6.0.14
	netbsd-4-0-RELEASE:1.6
	cube-autoconf:1.6.0.12
	cube-autoconf-base:1.6
	netbsd-4-0-RC5:1.6
	netbsd-4-0-RC4:1.6
	netbsd-4-0-RC3:1.6
	netbsd-4-0-RC2:1.6
	netbsd-4-0-RC1:1.6
	matt-armv6:1.6.0.10
	matt-armv6-base:1.6
	matt-mips64-base:1.6
	hpcarm-cleanup:1.6.0.8
	hpcarm-cleanup-base:1.6
	netbsd-3-1-1-RELEASE:1.1
	netbsd-3-0-3-RELEASE:1.1
	wrstuden-fixsa:1.6.0.6
	wrstuden-fixsa-base:1.6
	abandoned-netbsd-4-base:1.6
	abandoned-netbsd-4:1.6.0.2
	netbsd-3-1:1.1.0.12
	netbsd-3-1-RELEASE:1.1
	netbsd-3-0-2-RELEASE:1.1
	netbsd-3-1-RC4:1.1
	netbsd-3-1-RC3:1.1
	netbsd-3-1-RC2:1.1
	netbsd-3-1-RC1:1.1
	netbsd-4:1.6.0.4
	netbsd-4-base:1.6
	netbsd-3-0-1-RELEASE:1.1
	netbsd-3-0:1.1.0.10
	netbsd-3-0-RELEASE:1.1
	netbsd-3-0-RC6:1.1
	netbsd-3-0-RC5:1.1
	netbsd-3-0-RC4:1.1
	netbsd-3-0-RC3:1.1
	netbsd-3-0-RC2:1.1
	netbsd-3-0-RC1:1.1
	netbsd-2-0-3-RELEASE:1.1
	netbsd-2-1:1.1.0.8
	netbsd-2-1-RELEASE:1.1
	netbsd-2-1-RC6:1.1
	netbsd-2-1-RC5:1.1
	netbsd-2-1-RC4:1.1
	netbsd-2-1-RC3:1.1
	netbsd-2-1-RC2:1.1
	netbsd-2-1-RC1:1.1
	netbsd-2-0-2-RELEASE:1.1
	netbsd-3:1.1.0.6
	netbsd-3-base:1.1
	netbsd-2-0-1-RELEASE:1.1
	netbsd-2:1.1.0.4
	netbsd-2-base:1.1
	netbsd-2-0-RELEASE:1.1
	netbsd-2-0-RC5:1.1
	netbsd-2-0-RC4:1.1
	netbsd-2-0-RC3:1.1
	netbsd-2-0-RC2:1.1
	netbsd-2-0-RC1:1.1
	netbsd-2-0:1.1.0.2
	netbsd-2-0-base:1.1;
locks; strict;
comment	@# @;


1.6
date	2006.01.08.10.19.07;	author apb;	state Exp;
branches
	1.6.20.1;
next	1.5;

1.5
date	2006.01.08.10.10.03;	author apb;	state Exp;
branches;
next	1.4;

1.4
date	2006.01.04.13.38.18;	author apb;	state Exp;
branches;
next	1.3;

1.3
date	2006.01.03.18.31.09;	author apb;	state Exp;
branches;
next	1.2;

1.2
date	2006.01.03.16.40.16;	author apb;	state Exp;
branches;
next	1.1;

1.1
date	2003.06.23.09.02.31;	author dyoung;	state Exp;
branches;
next	;

1.6.20.1
date	2008.10.05.20.10.32;	author mjf;	state dead;
branches;
next	;


desc
@@


1.6
log
@Document input and output format for syspkgdeps and culldeps.

Approved by christos
@
text
@#!/bin/sh
#
# culldeps
#
# Filter redundant dependencies.
#
# Each line of input and output contains two syspkg names,
# where the first syspkg depends on the second syspkg.
#
# Emit all the dependencies on the standard input to the standard
# output EXCEPT the dependencies which can be derived from other
# dependencies by the transitive rule. For example, omit both A C
# and A D from
#
# 	A B
# 	B C
# 	C D
# 	A C
# 	A D
#
# because A C can be derived from A B and B C by transitivity,
# and A D can be derived from A B, B C, C D by transitivity.
#

prog="${0##*/}"
rundir="$(dirname "$0")" # ${0%/*} isn't good enough when there's no "/"
. "${rundir}/sets.subr"

SCRATCH="$(${MKTEMP} -d "/var/tmp/${prog}.XXXXXX")"
NEXTLEFTOVERS="${SCRATCH}/leftovers0"
LASTJOIN="${SCRATCH}/join0"
NEXTJOIN="${SCRATCH}/join1"
TAB="	"

${SORT} -k 1 > "${LASTJOIN}"

LEFTOVERS="${LASTJOIN}"

while [ "$(${WC} -l "${LASTJOIN}" | ${AWK} '{ print $1; }')" -ne 0 ]; do

	#
	# From dependencies X-requires-Y in ${LEFTOVERS} and Y-requires-Z in
	# ${LASTJOIN}, produce dependencies X-requires-Z and write them to
	# ${NEXTJOIN}.
	#
	${SORT} -k 2 < "${LEFTOVERS}" | \
	    ${JOIN} -1 2 -2 1 -o '1.1 2.2' - "${LASTJOIN}" | \
	    ${SORT} -u > "${NEXTJOIN}"
	if [ ${DEBUG:-0} -gt 0 ]; then
		echo >&2 "${prog}: ### begin filtered results ###"
		${JOIN} -t "${TAB}" "${NEXTJOIN}" "${LEFTOVERS}" | ${SORT} 1>&2
		echo >&2 "${prog}: ### end filtered results ###"
	fi

	#
	# Filter out of ${LEFTOVERS} all of the dependencies X-requires-Z, which
	# were produced in the previous step. Write the new leftovers to
	# ${NEXTLEFTOVERS}.
	#
	${JOIN} -v 2 -t "${TAB}" "${NEXTJOIN}" "${LEFTOVERS}" | \
		${SORT} -u > "${NEXTLEFTOVERS}"

	#
	# Swap output files before repeating. 
	#
	LASTJOIN="${NEXTJOIN}"
	if [ "$(basename "${NEXTJOIN}")" = join0 ]; then
		NEXTJOIN="${SCRATCH}/join1"
	else
		NEXTJOIN="${SCRATCH}/join0"
	fi
	LEFTOVERS="${NEXTLEFTOVERS}"
	if [ "$(basename "${NEXTLEFTOVERS}")" = leftovers0 ]; then
		NEXTLEFTOVERS="${SCRATCH}/leftovers1"
	else
		NEXTLEFTOVERS="${SCRATCH}/leftovers0"
	fi
done

#
# Output all of the dependencies that were not culled and clean up.
#
cat "${LEFTOVERS}"
rm -r "${SCRATCH}"
@


1.6.20.1
log
@Sync with HEAD.
@
text
@@


1.5
log
@When printing messages to stderr, always use
echo >&2 "${prog}: ..."

Approved by christos
@
text
@d7 3
@


1.4
log
@. "${rundir}/sets.subr", overlooked in previous commit.
@
text
@d47 1
a47 1
		echo "### filtered ###" 1>&2
d49 1
a49 1
		echo "###" 1>&2
@


1.3
log
@Ensure that (almost) all shell variables in distrib/sets/* scripts are
used with curly braces and quotes, as in "${var}".

Also ensure that command substitution is quoted, as in "$(command)", and
convert `command` to $(command).

Reviewed by agc
@
text
@d23 3
@


1.2
log
@Add shell variables defined in sets.subr for almost all commands used
by scripts in distrib/sets/*.  This is intended to be useful when cross
building.  Only trivial commands like echo, cat, and rm are excluded
from this treatment.

While I am here, make ${MTREE} and ${DB} follow the pattern used by most
other such variables.

Reviewed by agc.
@
text
@d22 5
a26 4
SCRATCH=$(${MKTEMP} -d /var/tmp/$0.XXXXXX)
NEXTLEFTOVERS=$SCRATCH/leftovers0
LASTJOIN=$SCRATCH/join0
NEXTJOIN=$SCRATCH/join1
d29 1
a29 1
${SORT} -k 1 > $LASTJOIN
d31 1
a31 1
LEFTOVERS=$LASTJOIN
d33 1
a33 1
while [ $(${WC} -l $LASTJOIN | ${AWK} '{ print $1; }') -ne 0 ]; do
d36 3
a38 3
	# From dependencies X-requires-Y in $LEFTOVERS and Y-requires-Z in
	# $LASTJOIN, produce dependencies X-requires-Z and write them to
	# $NEXTJOIN.
d40 3
a42 2
	${SORT} -k 2 < $LEFTOVERS | ${JOIN} -1 2 -2 1 -o '1.1 2.2' - $LASTJOIN | \
	    ${SORT} -u > $NEXTJOIN
d45 1
a45 1
		${JOIN} -t "$TAB" $NEXTJOIN $LEFTOVERS | ${SORT} 1>&2
d50 1
a50 1
	# Filter out of $LEFTOVERS all of the dependencies X-requires-Z, which
d52 1
a52 1
	# $NEXTLEFTOVERS.
d54 2
a55 1
	${JOIN} -v 2 -t "$TAB" $NEXTJOIN $LEFTOVERS | ${SORT} -u > $NEXTLEFTOVERS
d60 3
a62 3
	LASTJOIN=$NEXTJOIN
	if [ $(basename $NEXTJOIN) = join0 ]; then
		NEXTJOIN=$SCRATCH/join1
d64 1
a64 1
		NEXTJOIN=$SCRATCH/join0
d66 3
a68 3
	LEFTOVERS=$NEXTLEFTOVERS
	if [ $(basename $NEXTLEFTOVERS) = leftovers0 ]; then
		NEXTLEFTOVERS=$SCRATCH/leftovers1
d70 1
a70 1
		NEXTLEFTOVERS=$SCRATCH/leftovers0
d77 2
a78 2
cat $LEFTOVERS
rm -r $SCRATCH
@


1.1
log
@For System Packages, two new utilities, a subroutine library, and
a new list:

sets.subr -- The set-listing code that is common to makeplist,
	     makeflist, and regpkg has moved here.

syspkgdeps -- Compute naive dependencies for system packages based
	      on directory containment. I.e., if package A contains
	      path /p/q, and package B contains path /p, then B is
	      considered a dependency of A. As Jim Wise remarks,
	      this is not quite right: system-package dependencies
	      should indicate a functional dependency. Nevertheless,
	      these naive dependencies protect us from orphaning
	      files when pkg_delete'ing system packages.

culldeps -- Helper for syspkgdeps. Removes redundant dependencies
	    from a dependencies table.  Essentially does the opposite
	    of a transitive closure on a dependencies table: if
	    the table contains A depends-on B, B depends-on C, and
	    A depends-on C, then A depends-on C is removed because
	    it can be derived from the prior two dependencies.

deps -- Dependencies computed by syspkgdeps.
@
text
@d22 1
a22 1
SCRATCH=$(mktemp -d /var/tmp/$0.XXXXXX)
d28 1
a28 1
sort -k 1 > $LASTJOIN
d32 1
a32 1
while [ $(wc -l $LASTJOIN | awk '{ print $1; }') -ne 0 ]; do
d39 2
a40 2
	sort -k 2 < $LEFTOVERS | join -1 2 -2 1 -o '1.1 2.2' - $LASTJOIN | \
	    sort -u > $NEXTJOIN
d43 1
a43 1
		join -t "$TAB" $NEXTJOIN $LEFTOVERS | sort 1>&2
d52 1
a52 1
	join -v 2 -t "$TAB" $NEXTJOIN $LEFTOVERS | sort -u > $NEXTLEFTOVERS
@