#!/bin/sh -efu
#
# Copyright (C) 2006-2007  Alexey Tourbin <at@altlinux.org>
# Copyright (C) 2006       Dmitry V. Levin <ldv@altlinux.org>
#
# Optimizes package list by excluding dependent packages.
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
#

PROG=optimize_package_list

exit_handler()
{
	local rc=$1
	rm -rf -- "$workdir"
	exit $rc
}

trap 'exit 143' HUP INT QUIT PIPE TERM
workdir="$(mktemp -dt "$PROG.XXXXXXXXXX")"
trap 'exit_handler $?' EXIT

cd "$workdir"
export LC_COLLATE=C

# make list of package names
if [ $# -gt 0 ]; then
	printf %s "$*" |xargs -n1 printf '%s\n'
else
	xargs -n1 printf '%s\n'
fi >n
sort -u -o n n

# make list of requirements
rpmquery -a --qf '[%{REQUIRENAME}\t%{NAME}\n]' > Rn-all
sort -k1,1 -k2,2 -u -o Rn-all Rn-all
sort -k2,2 -o Rn-all-k2 Rn-all
join -t$'\t' -1 1 -2 2 -o '2.1 2.2' n Rn-all-k2 > Rn
sort -k1,1 -k2,2 -u -o Rn Rn

# make list of provides
rpmquery -a --qf '[%{PROVIDENAME}\t%{NAME}\n][%{FILENAMES}\t%{NAME}\n]' > Pn-all
sed -i '/^[^[:space:]]*[[:space:]][^[:space:]]*[[:space:]]/d' Pn-all
sort -k1,1 -k2,2 -u -o Pn-all Pn-all
sort -k2,2 -o Pn-all-k2 Pn-all
join -t$'\t' -1 1 -2 2 -o '2.1 2.2' n Pn-all-k2 > Pn
sort -k1,1 -k2,2 -u -o Pn Pn

# add indirect requirements and provides
cp n n-closure
while :; do
	join -j 1 -o 2.2 Rn Pn-all > n-pr
	sort -u -o n-closure+ n-closure n-pr
	rm n-pr
	if cmp -s n-closure n-closure+; then
		break
	fi
	mv n-closure+ n-closure

	join -t$'\t' -1 1 -2 2 -o '2.1 2.2' n-closure Rn-all-k2 > Rn
	sort -k1,1 -k2,2 -u -o Rn Rn

	join -t$'\t' -1 1 -2 2 -o '2.1 2.2' n-closure Pn-all-k2 > Pn
	sort -k1,1 -k2,2 -u -o Pn Pn
done
rm n-closure+ n-closure Rn-all Rn-all-k2 Pn-all Pn-all-k2

# make relation Requires(pkg1->dep->pkg2)
join -j 1 -o '1.2 0 2.2' Rn Pn |sort -u -k1,1 -k2,2 -k3,3 >nRn
rm Rn Pn

# Check if the same virtual dep resolves to different packages, e.g.
#	rpm-build	autoconf	autoconf_2.50
#	rpm-build	autoconf	autoconf_2.60
awk '{print$3,$2}' <nRn |sort -u -k2,2 -k1,1 |uniq -D -f1 |cut -d' ' -f2 >R-amb
if [ -s R-amb ]; then
	sort -u -o R-amb R-amb
	sort -k2,2 <nRn |join -12 -21 -o '1.1 1.2 1.3' - R-amb >nRn-amb
	echo "$PROG: ambiguous virtual dependencies:"
	sed -e 's/ / -> /g' <nRn-amb
	rm nRn-amb
fi >&2
rm R-amb

# Assist loop breaks.  Consider this:
#	vim-common	/usr/bin/vim	vim-console
#	vim-console	vim-common	vim-common
# We would like vim-console to take precedence,
# because vim-console explicitly requires vim-common.
awk '$2==$3{printf("%s\t%s\n",$1,$3)}' <nRn |sort -u >nn-real
awk '$2!=$3{printf("%s\t%s\n",$1,$3)}' <nRn |sort -u >nn-virt
rm nRn

# prefix packages from the original set with '*'
sed 's/^.*/&\t*&/' <n >n.map
for f in nn-real nn-virt; do
	join -t$'\t' -j1 -o2.2,1.2 $f n.map >Nn
	join -t$'\t' -j1 -v1 -o1.1,1.2 $f n.map >>Nn
	sort -k2,2 -o Nn{,}
	join -t$'\t' -12 -21 -o1.1,2.2 Nn n.map >$f
	join -t$'\t' -12 -21 -v1 -o1.1,1.2 Nn n.map >>$f
	rm Nn
	sort -u -o $f{,}
done

comm -23 nn-virt nn-real >nn-virt-only
mv -f nn-virt-only nn-virt
# nn-real:	vim-console	vim-common
# nn-virt:	vim-common	vim-console
join -t$'\t' -v1 -o1.2,1.1 nn-virt /dev/null |sort -u >reverse-nn-virt
comm -12 reverse-nn-virt nn-real >nn-real-virt-loop
rm reverse-nn-virt

# remove "vim-console *vim-common" from nn-real-virt-loop
sed -i '/^[^*[:space:]]\+[[:space:]]\+\*/d' nn-real-virt-loop

if [ -s nn-real-virt-loop ]; then
	echo "$PROG: simple RV-loop (first package takes precedence):"
	sed -e 's/	/ <-> /g' <nn-real-virt-loop
	join -t$'\t' -v1 -o1.2,1.1 nn-real-virt-loop /dev/null |sort -u >nn-virt-bad
	comm -23 nn-virt nn-virt-bad >nn-virt-good
	rm nn-virt-bad
	mv -f nn-virt-good nn-virt
fi >&2
rm nn-real-virt-loop

# make list of package pairs where first depends on second
sort -u nn-real nn-virt >nn
rm nn-real nn-virt

# tsort this list of pairs
tsort <nn >t || [ -s t ]

# make list of package names which satisfy other package requirements
awk <nn >s '
BEGIN {
	N=0
	while ((getline <"t") > 0)
		t[++N] = $1
}
{
	nn[$1,$2] = 1
}
END {
	for (i = 1; i < N; i++) {
		d = t[i]
		for (j = i+1; j <= N; j++) {
			s = t[j]
			if (nn[d,s])
				print s
		}
	}
}'
rm nn
sort -u -o s s

# substract names of packages-satisfiers from the whole list
join -12 -21 -v1 -o1.1 n.map s
