Add "impact" as a consideration for rebuilding packages. Impact can

either indicate how involved the rebuild process is (how many
interrelated packages can be deleted/rebuilt at once) or specific
packages you do not want to impact (like...perl?).

Welcome to 2.6.

4 files changed, 186 insertions, 23 deletions

diff --git a/pkgtools/pkgdepgraph/Makefile b/pkgtools/pkgdepgraph/Makefile
index c4d7feebf85..23a76484eb6 100644
--- a/pkgtools/pkgdepgraph/Makefile
+++ b/pkgtools/pkgdepgraph/Makefile
@@ -1,7 +1,7 @@
-# $NetBSD: Makefile,v 1.15 2004/04/11 21:31:10 jschauma Exp $
+# $NetBSD: Makefile,v 1.16 2004/06/05 06:17:37 atatat Exp $
 #
 
-DISTNAME=	pkgdepgraph-2.5
+DISTNAME=	pkgdepgraph-2.6
 CATEGORIES=	pkgtools devel
 MASTER_SITES=	# empty
 DISTFILES=	# empty
diff --git a/pkgtools/pkgdepgraph/files/pkgdepgraph.0 b/pkgtools/pkgdepgraph/files/pkgdepgraph.0
index 93cf704d79d..88fafb2b29a 100644
--- a/pkgtools/pkgdepgraph/files/pkgdepgraph.0
+++ b/pkgtools/pkgdepgraph/files/pkgdepgraph.0
@@ -4,9 +4,9 @@ NNAAMMEE
      ppkkggddeeppggrraapphh - visual representation of installed packages
 
 SSYYNNOOPPSSIISS
-     ppkkggddeeppggrraapphh [--AAaaCCccDDeeFFffggLLllooRRrrssvv] [--dd _p_k_g___d_b_d_i_r] [--KK _p_a_c_k_a_g_e_s] [--MM _m_a_k_e]
-                 [--mm _t_a_r_g_e_t] [--OO _p_a_c_k_a_g_e] [--PP _p_k_g_s_r_c_d_i_r] [--SS _p_a_c_k_a_g_e]
-                 [--tt _t_a_r_g_e_t] [--UU _p_a_c_k_a_g_e] [_d_a_t_a _._._.]
+     ppkkggddeeppggrraapphh [--AAaaCCccDDeeFFffggLLllooRRrrssvv] [--dd _p_k_g___d_b_d_i_r] [--ii _i_m_p_a_c_t] [--KK _p_a_c_k_a_g_e_s]
+                 [--MM _m_a_k_e] [--mm _t_a_r_g_e_t] [--OO _p_a_c_k_a_g_e] [--PP _p_k_g_s_r_c_d_i_r]
+                 [--SS _p_a_c_k_a_g_e] [--tt _t_a_r_g_e_t] [--UU _p_a_c_k_a_g_e] [_d_a_t_a _._._.]
 
 DDEESSCCRRIIPPTTIIOONN
      ppkkggddeeppggrraapphh emits a _d_o_t language description of the locally installed
@@ -94,7 +94,7 @@ DDEESSCCRRIIPPTTIIOONN
      --dd _p_k_g___d_b_d_i_r
               The location of the package database files.  This defaults to
               the value of the _P_K_G___D_B_D_I_R environment variable, if it is set,
-              or to _@_P_K_G___D_B_D_I_R_@.
+              or to _/_v_a_r_/_d_b_/_p_k_g.
 
      --ee       Adds an ``existence check'' to each of the lines of sh(1) style
               output so that commands can be skipped if the package is already
@@ -112,6 +112,19 @@ DDEESSCCRRIIPPTTIIOONN
               common prefix (e.g., ``p5'' or ``gimp'') in a subgraph with a
               line around it so you can visually associate packages.
 
+     --ii _i_m_p_a_c_t
+              Specify the impact you want to allow when rebuilding packages.
+              The impact of a given package being rebuilt is a number that
+              reflects the longest path from the ``top'' of the installed
+              packages (those packages upon which most other packages depend)
+              to the ``bottom'' of the installed packages (those packages upon
+              which no other packages depend).  A package that needs to be
+              rebuilt but has nothing above it in the tree requiring rebuild-
+              ing and nothing below it has an impact of 0.  Values of 10 or
+              more for _i_m_p_a_c_t will probably eliminate nothing from the rebuild
+              list.  The value for _i_m_p_a_c_t can also be the name of a package to
+              be avoided when constructing the list of things to be rebuilt.
+
      --KK _p_a_c_k_a_g_e_s
               The base location or url from which to install binary packages.
               This defaults to the value of PKG_PATH, or to PACKAGES with
@@ -154,7 +167,7 @@ DDEESSCCRRIIPPTTIIOONN
      --PP _p_k_g_s_r_c_d_i_r
               The root of the pkgsrc source tree.  This defaults to the value
               of the _P_K_G_S_R_C_D_I_R environment variable, if it is set, or to
-              _@_P_K_G_S_R_C_D_I_R_@.
+              _/_u_s_r_/_p_k_g_s_r_c.
 
      --RR       Instead of the standard graph output, emits a series of sh(1)
               commands that will rebuild all the out of date packages by
@@ -209,10 +222,10 @@ EENNVVIIRROONNMMEENNTT
      erated by the --FF and --RR output modes.
 
    PPKKGG__DDBBDDIIRR
-     Where to find registered packages instead of _@_P_K_G___D_B_D_I_R_@.
+     Where to find registered packages instead of _/_v_a_r_/_d_b_/_p_k_g.
 
    PPKKGGSSRRCCDDIIRR
-     Where the pkgsrc tree is located instead of _@_P_K_G_S_R_C_D_I_R_@.
+     Where the pkgsrc tree is located instead of _/_u_s_r_/_p_k_g_s_r_c.
 
    PPKKGG__PPAATTHH
    PPAACCKKAAGGEESS
@@ -242,6 +255,17 @@ EEXXAAMMPPLLEESS
            $ pkgdepgraph -D pkgdepgraph.in > delete_order
            $ pkgdepgraph -R pkgdepgraph.in > rebuild.sh
 
+     To rebuild everything that has no other rebuild requirements:
+
+           $ pkgdepgraph -D pkgdepgraph.in -i0 > delete_order
+           $ pkgdepgraph -R pkgdepgraph.in -i0 > rebuild.sh
+
+     Or, to rebuild everything except those things that would require rebuild-
+     ing perl:
+
+           $ pkgdepgraph -D pkgdepgraph.in -iperl > delete_order
+           $ pkgdepgraph -R pkgdepgraph.in -iperl > rebuild.sh
+
      To subsequently delete all out of date and stale packages:
 
            $ pkg_delete `cat delete_order`
@@ -316,4 +340,4 @@ BBUUGGSS
      ages that have moved within the pkgsrc tree.  It is necessary that you
      edit the rebuild script by hand to work around this.
 
-NetBSD 1.6                       March 6, 2003                      NetBSD 1.6
+NetBSD 2.0                       June 5, 2004                       NetBSD 2.0
diff --git a/pkgtools/pkgdepgraph/files/pkgdepgraph.1 b/pkgtools/pkgdepgraph/files/pkgdepgraph.1
index e2daffbd1a3..a367b73538f 100644
--- a/pkgtools/pkgdepgraph/files/pkgdepgraph.1
+++ b/pkgtools/pkgdepgraph/files/pkgdepgraph.1
@@ -1,9 +1,9 @@
-.\"	$NetBSD: pkgdepgraph.1,v 1.8 2003/04/30 03:39:17 atatat Exp $
+.\"	$NetBSD: pkgdepgraph.1,v 1.9 2004/06/05 06:17:37 atatat Exp $
 .\"
-.\" Copyright (c) 2002, 2003 by Andrew Brown <atatat@netbsd.org>
+.\" Copyright (c) 2002, 2003, 2004 by Andrew Brown <atatat@netbsd.org>
 .\" Absolutely no warranty.
 .\"
-.Dd March 6, 2003
+.Dd June 5, 2004
 .Dt PKGDEPGRAPH 1
 .Sh NAME
 .Nm pkgdepgraph
@@ -12,6 +12,7 @@
 .Nm
 .Op Fl AaCcDeFfgLloRrsv
 .Op Fl d Ar pkg_dbdir
+.Op Fl i Ar impact
 .Op Fl K Ar packages
 .Op Fl M Ar make
 .Op Fl m Ar target
@@ -184,6 +185,25 @@ or
 .Dq gimp )
 in a subgraph with a line around it so you can visually associate
 packages.
+.It Fl i Ar impact
+Specify the impact you want to allow when rebuilding packages.
+The impact of a given package being rebuilt is a number that reflects
+the longest path from the
+.Dq top
+of the installed packages (those packages upon which most other
+packages depend) to the
+.Dq bottom
+of the installed packages (those packages upon which no other packages
+depend).
+A package that needs to be rebuilt but has nothing above it in the
+tree requiring rebuilding and nothing below it has an impact of 0.
+Values of 10 or more for
+.Ar impact
+will probably eliminate nothing from the rebuild list.
+The value for
+.Ar impact
+can also be the name of a package to be avoided when constructing the
+list of things to be rebuilt.
 .It Fl K Ar packages
 The base location or url from which to install binary packages.
 This defaults to the value of PKG_PATH, or to PACKAGES with
@@ -403,6 +423,19 @@ $ pkgdepgraph -D pkgdepgraph.in \*[Gt] delete_order
 $ pkgdepgraph -R pkgdepgraph.in \*[Gt] rebuild.sh
 .Ed
 .Pp
+To rebuild everything that has no other rebuild requirements:
+.Bd -literal -offset indent
+$ pkgdepgraph -D pkgdepgraph.in -i0 \*[Gt] delete_order
+$ pkgdepgraph -R pkgdepgraph.in -i0 \*[Gt] rebuild.sh
+.Ed
+.Pp
+Or, to rebuild everything except those things that would require
+rebuilding perl:
+.Bd -literal -offset indent
+$ pkgdepgraph -D pkgdepgraph.in -iperl \*[Gt] delete_order
+$ pkgdepgraph -R pkgdepgraph.in -iperl \*[Gt] rebuild.sh
+.Ed
+.Pp
 To subsequently delete all out of date and stale packages:
 .Bd -literal -offset indent
 $ pkg_delete `cat delete_order`
diff --git a/pkgtools/pkgdepgraph/files/pkgdepgraph.pl b/pkgtools/pkgdepgraph/files/pkgdepgraph.pl
index 5e70be44f63..ce6fa67e8c6 100755
--- a/pkgtools/pkgdepgraph/files/pkgdepgraph.pl
+++ b/pkgtools/pkgdepgraph/files/pkgdepgraph.pl
@@ -1,9 +1,9 @@
 #!@PREFIX@/bin/perl
 
-# Copyright (c) 2002, 2003 by Andrew Brown <atatat@netbsd.org>
+# Copyright (c) 2002, 2003, 2004 by Andrew Brown <atatat@netbsd.org>
 # Absolutely no warranty.
 
-# $NetBSD: pkgdepgraph.pl,v 1.8 2003/04/30 03:39:18 atatat Exp $
+# $NetBSD: pkgdepgraph.pl,v 1.9 2004/06/05 06:17:37 atatat Exp $
 # pkgdepgraph: @DISTVER@
 
 use strict;
@@ -15,13 +15,14 @@ my(@opts, %opt);
 my($iam, $version, $usecolor, $group, $locations, $order, $versions);
 my($limit, $delete, $rebuild, $force, @outofdate, @update, $clean);
 my($pkg_dbdir, $pkgsrcdir, $packages, $pkgadd, $fetch, $make);
-my($all, $target, $exists, $reverse, $simple, @subgraph);
+my($all, $target, $exists, $reverse, $simple, @subgraph, @impact, %impactof);
 
 $version = '@DISTVER@';
 ($iam = $0) =~ s:.*/::;
-@opts = ('A', 'a+', 'C', 'c', 'D', 'd=s', 'e', 'F', 'f', 'g', 'K=s',
-	 'L', 'l', 'M=s', 'm=s', 'O=s', 'o', 'P=s', 'R', 'r', 'S=s',
-	 's', 't=s', 'U=s', 'v');
+@opts = ('A', 'a+', 'C', 'c', 'D', 'd=s', 'e', 'F', 'f', 'g', 'i=s',
+	 'K=s', 'L', 'l', 'M=s', 'm=s', 'O=s', 'o', 'P=s', 'R', 'r',
+	 'S=s', 's', 't=s', 'U=s', 'v');
+
 %opt = (
 	'A' => \$pkgadd,
 	'a' => \$all,
@@ -33,6 +34,7 @@ $version = '@DISTVER@';
 	'F' => \$fetch,
 	'f' => \$force,
 	'g' => \$group,
+	'i' => \@impact,
 	'K' => \$packages,
 	'L' => \$limit,
 	'l' => \$locations,
@@ -49,11 +51,13 @@ $version = '@DISTVER@';
 	'U' => \@update,
 	'v' => \$versions,
 	);
-die("usage: $iam [-AaCcDeFfgLloRrsv] [-d pkg_dbdir] [-K packages] [-M make]\n",
+die("usage: $iam [-AaCcDeFfgLloRrsv] [-d pkg_dbdir] [-i impact]\n",
+    " " x (length($iam) + 8),
+    "[-K packages] [-M make] [-m target] [-O package]\n",
     " " x (length($iam) + 8),
-    "[-m target] [-O package] [-P pkgsrcdir] [-S package]\n",
+    "[-P pkgsrcdir] [-S package] [-t target] [-U package]\n",
     " " x (length($iam) + 8),
-    "[-t target] [-U package] [data ...]\n")
+    "[data ...]\n")
     if (!GetOptions(\%opt, @opts));
 
 die("$iam: -D, -F, -m, and -R are mutually exclusive -- please pick one\n")
@@ -74,12 +78,25 @@ $make ||= $ENV{'MAKE'} || "make";
 
 my(@pkgs, $pkg, $req, %req, %dep, @reqs, @rreqs);
 my(%clusters, $cluster);
-my(%where, $pkgcnt, $num, %num, @num, %ord, @ord, $suffix);
+my(%where, $pkgcnt, $num, %num, @num, %ord, $suffix);
 my(%color, $color, %vuln);
 my(%need, %forced, $label);
 my($recolor, @graph);
 my(%vpkgs);
 
+# @pkgs		- list of all installed pkgs
+# %req		- pkg to ref to hash of pkgs that it requires
+# %dep		- pkg to ref to hash of pkgs that depend on it
+# %clusters	- pkg prefix to number of pkgs that share the prefix
+# %where	- pkg to location in source tree
+# %num/@num	- pkg to group number/group number array ref
+# %ord		- pkg to its height in the tree
+# %color	- pkg to pkg color (green, yellow, red, etc)
+# %vuln		- pkg to vulnerabilities recorded against it
+# %need		- pkg to version required (pkg is out of date) 
+# %forced	- pkg marked as "forced" to be out of date
+# %vpkgs	- pkg is viewable (part of selected subgraph)
+
 ##
 ## load out-of-date or security problem list (if given), or a graph to
 ## recolor
@@ -381,6 +398,48 @@ else {
 }
 
 ##
+## if checking for rebuild impact, also mark packages that are too
+## deeply involved as "green" so that they're not candidates for
+## destruction
+##
+if (@impact) {
+    my ($impact);
+
+    # step 1: canonicalize anything that's not a number (ie, is the
+    # name of a pkg) and eliminate duplicates (we just don't need 'em)
+    foreach (@impact) {
+	next if (/^\d+$/);
+	canonicalize($_);
+    }
+    @impact = uniq(sort(@impact));
+
+    # step 2: the "default" impact allows for anything to be rebuilt,
+    # but numeric values in @impact are also allowed, so pick the
+    # lowest one (specifying both 1 and 2 really means just 1)
+    $impact = $ord{(sort(byord @pkgs))[0]};
+    while ($impact[0] =~ /^\d+$/) {
+	$_ = shift(@impact);
+	$impact = $_ if ($_ < $impact);
+    }
+
+    # step 3: anything that would have too great an impact on the tree
+    # gets marked (the impactof() function will check the @impact
+    # array to avoid specific pkgs being rebuild)
+    foreach $pkg (keys %vpkgs) {
+	next if (impactof($impact, $pkg) <= $impact);
+	$vpkgs{$pkg} = 2;
+    }
+
+    # step 4: anything so marked gets tagged as green.  this tagging
+    # is a separate step so that we can properly judge impact over the
+    # entire tree (marking too early could prematurely split chunks
+    # that need to be rebuilt)
+    foreach $pkg (keys %vpkgs) {
+	$color{$pkg} = "green" if ($vpkgs{$pkg} == 2);
+    }
+}
+
+##
 ## translate "older" alternate output modes to the new generic version
 ##
 if ($fetch) {
@@ -436,6 +495,7 @@ foreach $pkg (sort(bynum keys %vpkgs)) {
 	$label .= "\\n[$vuln{$pkg}]";
     }
     $suffix = "\t// \#$ord{$pkg}, group $num{$pkg}, " .
+	(exists($impactof{$pkg}) ? "impact $impactof{$pkg}, " : "") .
 	scalar(@{$num[$num{$pkg}]}) . " members, $pkgcnt pkgs";
     $suffix .= ", LEAF" if ($ord{$pkg} == 1);
 
@@ -617,3 +677,49 @@ sub uniq {
     }
     @_;
 }
+
+##
+## impactof - impact of pkg delete/rebuild is the longest path (either
+## up or down the tree) that encompasses all things that need
+## rebuilding
+##
+sub impactof {
+    my ($impact, $pkg) = @_;
+    my (@in, @out);
+
+    # if we already know or it's dead-simple, get out early
+    return $impactof{$pkg} if (exists($impactof{$pkg}));
+    return $impactof{$pkg} = 0 if (color($pkg) eq "green");
+
+    # starting with the given pkg, repeatedly look up and down the
+    # tree for connected pkgs that also require a rebuild
+    @out = ($pkg);
+    do {
+	@in = @out;
+	@out = ($pkg);
+	push(@out, grep(color($_) ne "green", recurse(\%dep, @in)));
+	push(@out, grep(color($_) ne "green", recurse(\%req, @out)));
+	@out = uniq(sort(byord @out));
+    } while (@in != @out);
+
+    # check to see if the set of related pkgs intersects with the set
+    # we want to avoid and if so, mark this set as "too expensive"
+    $a = "";
+    if (@impact) {
+	foreach $b (@impact) {
+	    if (grep($_ eq $b, @out)) {
+		$a = $b;
+		$impact++;
+		last;
+	    }
+	}
+    }
+
+    # if we didn't hit anything, the impact is the one less than the
+    # highest ordered remotely connected pkg we found (the longest
+    # path from the top to the bottom of the set to be rebuilt)
+    $impact = $ord{$out[0]} - 1 if ($a eq "");
+    @impactof{@in} = ($impact) x @in;
+
+    $impactof{$pkg};
+}