When creating a package sort dependencies in such a way that if dependency

A depends on dependency B then dependency A will be in all cases listed
before B, so ``pkg_add -r'' will fetch/install packages in the correct order.

Previously dependencies were sorted just by its names, which is why
``pkg_add -r'' never actually worked properly.

To be usefull, hovewer, this fix requires that all packages have been
rebuilt, so it will take some time until users would be able to feel
posititive improvements. For the same reasons it is desirable to propagate
these changes to the 4-stable package building cluster *before* 4.3 ports
freeze, so packages for 4.3-RELEASE would be properly prepared.

Prompted by:			kris
Insanely appreciated by:	obrien
Silently approved by:		jkh, -ports

5 files changed, 152 insertions, 74 deletions

diff --git a/usr.sbin/pkg_install/create/perform.c b/usr.sbin/pkg_install/create/perform.c
index 5307698..8d073e4 100644
--- a/usr.sbin/pkg_install/create/perform.c
+++ b/usr.sbin/pkg_install/create/perform.c
@@ -97,16 +97,41 @@ pkg_perform(char **pkgs)
 
     /* Stick the dependencies, if any, at the top */
     if (Pkgdeps) {
+	char **deps;
+	int i;
+	int ndeps = 0;
+
 	if (Verbose && !PlistOnly)
 	    printf("Registering depends:");
-	while (Pkgdeps) {
-	    cp = strsep(&Pkgdeps, " \t\n");
-	    if (*cp) {
-		add_plist_top(&plist, PLIST_PKGDEP, cp);
+
+	/* Count number of dependencies */
+	for (cp = Pkgdeps; cp != NULL && *cp != '\0';
+			   cp = strpbrk(++cp, " \t\n")) {
+	    ndeps++;
+	}
+
+	if (ndeps != 0) {
+	    /* Create easy to use NULL-terminated list */
+	    deps = alloca(sizeof(*deps) * ndeps + 1);
+	    if (deps == NULL) {
+		errx(2, "%s: alloca() failed", __FUNCTION__);
+		/* Not reached */
+	    }
+	    for (i = 0; Pkgdeps; i++) {
+		cp = strsep(&Pkgdeps, " \t\n");
+		if (*cp)
+		    deps[i] = cp;
+	    }
+	    deps[ndeps] = NULL;
+
+	    sortdeps(deps);
+	    for (i = 0; i < ndeps; i++) {
+		add_plist_top(&plist, PLIST_PKGDEP, deps[i]);
 		if (Verbose && !PlistOnly)
-		    printf(" %s", cp);
+		    printf(" %s", deps[i]);
 	    }
 	}
+
 	if (Verbose && !PlistOnly)
 	    printf(".\n");
     }
diff --git a/usr.sbin/pkg_install/delete/perform.c b/usr.sbin/pkg_install/delete/perform.c
index d5fe32a..120622c 100644
--- a/usr.sbin/pkg_install/delete/perform.c
+++ b/usr.sbin/pkg_install/delete/perform.c
@@ -30,7 +30,6 @@ static const char rcsid[] =
 static int pkg_do(char *);
 static void sanity_check(char *);
 static void undepend(PackingList, char *);
-static int chkifdepends(char *pkgname1, char *pkgname2);
 static char LogDir[FILENAME_MAX];
 
 
@@ -38,10 +37,9 @@ int
 pkg_perform(char **pkgs)
 {
     char **matched;
-    char *tmp;
-    int i, j;
+    int i;
     int err_cnt = 0;
-    int loop_cnt, errcode;
+    int errcode;
 
     if (MatchType != MATCH_EXACT) {
 	matched = matchinstalled(MatchType, pkgs, &errcode);
@@ -65,36 +63,8 @@ pkg_perform(char **pkgs)
 	}
     }
 
+    err_cnt += sortdeps(pkgs);
     for (i = 0; pkgs[i]; i++) {
-	/*
-	 * Check to see if any other package in pkgs[i+1:] depends
-	 * on pkgs[i] and deffer removal of pkgs[i] if so.
-	 */
-	loop_cnt = 0;
-	for (j = i + 1; pkgs[j]; j++) {
-	    if (chkifdepends(pkgs[j], pkgs[i]) == 1) {
-		/*
-		 * Try to avoid deadlock if package A depends on B which in
-		 * turn depends on C and C due to an error depends on A.
-		 * Use ugly but simple method, becase it Should Never
-		 * Happen[tm] in the real life anyway.
-		 */
-		if (loop_cnt > 4096) {
-		    warnx("dependency loop detected for package %s", pkgs[j]);
-		    err_cnt++;
-		    break;
-		}
-		loop_cnt++;
-		tmp = pkgs[i];
-		pkgs[i] = pkgs[j];
-		pkgs[j] = tmp;
-		/*
-		 * Another iteration requred to check if new pkgs[i]
-		 * itself has any packages that depend on it
-		 */
-		j = i + 1;
-	    }
-	}
 	err_cnt += pkg_do(pkgs[i]);
     }
 
@@ -364,38 +334,3 @@ undepend(PackingList p, char *pkgname)
      return;
 }
 
-/*
- * Check to see if pkgname1 depends on pkgname2.
- * Returns 1 if depends, 0 if not, and -1 if error occured.
- */ 
-static int
-chkifdepends(char *pkgname1, char *pkgname2)
-{
-    FILE *fp;
-    char fname[FILENAME_MAX];
-    char fbuf[FILENAME_MAX];
-    char *tmp;
-    int retval;
-
-    sprintf(fname, "%s/%s/%s",
-	    (tmp = getenv(PKG_DBDIR)) ? tmp : DEF_LOG_DIR,
-	    pkgname2, REQUIRED_BY_FNAME);
-    fp = fopen(fname, "r");
-    if (fp == NULL) {
-	/* Probably pkgname2 doesn't have any packages that depend on it */
-	return 0;
-    }
-
-    retval = 0;
-    while (fgets(fbuf, sizeof(fbuf), fp) != NULL) {
-	if (fbuf[strlen(fbuf)-1] == '\n')
-	    fbuf[strlen(fbuf)-1] = '\0';
-	if (strcmp(fbuf, pkgname1) == 0) {	/* match */
-	    retval = 1;
-	    break;
-	}
-    }
-
-    fclose(fp);
-    return retval;
-}
diff --git a/usr.sbin/pkg_install/lib/Makefile b/usr.sbin/pkg_install/lib/Makefile
index 990bfe3..0fb00b2 100644
--- a/usr.sbin/pkg_install/lib/Makefile
+++ b/usr.sbin/pkg_install/lib/Makefile
@@ -1,7 +1,8 @@
 # $FreeBSD$
 
 LIB=	install
-SRCS=	file.c msg.c plist.c str.c exec.c global.c pen.c match.c
+SRCS=	file.c msg.c plist.c str.c exec.c global.c pen.c match.c \
+	deps.c
 CFLAGS+= ${DEBUG}
 NOPROFILE= yes
 NOPIC=	yes
diff --git a/usr.sbin/pkg_install/lib/deps.c b/usr.sbin/pkg_install/lib/deps.c
new file mode 100644
index 0000000..4c06da8
--- /dev/null
+++ b/usr.sbin/pkg_install/lib/deps.c
@@ -0,0 +1,113 @@
+#ifndef lint
+static const char rcsid[] =
+  "$FreeBSD$";
+#endif
+
+/*
+ * FreeBSD install - a package for the installation and maintainance
+ * of non-core utilities.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * Maxim Sobolev
+ * 14 March 2001
+ *
+ * Routines used to do various operations with dependencies
+ * among installed packages.
+ *
+ */
+
+#include "lib.h"
+
+#include <err.h>
+#include <stdio.h>
+
+/*
+ * Sort given NULL-terminated list of installed packages (pkgs) in
+ * such a way that if package A depends on package B then after
+ * sorting A will be listed before B no matter how they were
+ * originally positioned in the list.
+ */
+int
+sortdeps(char **pkgs)
+{
+    char *tmp;
+    int i, j, loop_cnt;
+    int err_cnt = 0;
+
+    for (i = 0; pkgs[i]; i++) {
+	/*
+	 * Check to see if any other package in pkgs[i+1:] depends
+	 * on pkgs[i] and swap those two packages if so.
+	 */
+	loop_cnt = 0;
+	for (j = i + 1; pkgs[j]; j++) {
+	    if (chkifdepends(pkgs[j], pkgs[i]) == 1) {
+		/*
+		 * Try to avoid deadlock if package A depends on B which in
+		 * turn depends on C and C due to an error depends on A.
+		 * Use ugly but simple method, becase it Should Never
+		 * Happen[tm] in the real life anyway.
+		 */
+		if (loop_cnt > 4096) {
+		    warnx("dependency loop detected for package %s", pkgs[j]);
+		    err_cnt++;
+		    break;
+		}
+		loop_cnt++;
+		tmp = pkgs[i];
+		pkgs[i] = pkgs[j];
+		pkgs[j] = tmp;
+		/*
+		 * Another iteration requred to check if new pkgs[i]
+		 * itself has any packages that depend on it
+		 */
+		j = i + 1;
+	    }
+	}
+    }
+    return err_cnt;
+}
+
+/*
+ * Check to see if pkgname1 depends on pkgname2.
+ * Returns 1 if depends, 0 if not, and -1 if error occured.
+ */ 
+int
+chkifdepends(char *pkgname1, char *pkgname2)
+{
+    FILE *fp;
+    char fname[FILENAME_MAX];
+    char fbuf[FILENAME_MAX];
+    char *tmp;
+    int retval;
+
+    sprintf(fname, "%s/%s/%s",
+	    (tmp = getenv(PKG_DBDIR)) ? tmp : DEF_LOG_DIR,
+	    pkgname2, REQUIRED_BY_FNAME);
+    fp = fopen(fname, "r");
+    if (fp == NULL) {
+	/* Probably pkgname2 doesn't have any packages that depend on it */
+	return 0;
+    }
+
+    retval = 0;
+    while (fgets(fbuf, sizeof(fbuf), fp) != NULL) {
+	if (fbuf[strlen(fbuf)-1] == '\n')
+	    fbuf[strlen(fbuf)-1] = '\0';
+	if (strcmp(fbuf, pkgname1) == 0) {	/* match */
+	    retval = 1;
+	    break;
+	}
+    }
+
+    fclose(fp);
+    return retval;
+}
diff --git a/usr.sbin/pkg_install/lib/lib.h b/usr.sbin/pkg_install/lib/lib.h
index fae802d..0ed6899 100644
--- a/usr.sbin/pkg_install/lib/lib.h
+++ b/usr.sbin/pkg_install/lib/lib.h
@@ -177,6 +177,10 @@ int		pkg_perform(char **);
 /* Query installed packages */
 char		**matchinstalled(match_t, char **, int *);
 
+/* Dependencies */
+int		sortdeps(char **);
+int		chkifdepends(char *, char *);
+
 /* Externs */
 extern Boolean	Verbose;
 extern Boolean	Fake;