- Add `quilt graph' command for generating a dependency graph

  between patches. This requires the graphviz package for
  removing transitive edges (optional) and for rendering the
  graph. Please note that the graph command itself is minimal,
  while the underlying scripts/dependency-graph is more flexible.
- The spec file was missing the quilt.1 man page.

5 files changed, 470 insertions, 4 deletions

diff --git a/Makefile.in b/Makefile.in
index 8790446..2712f87 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -55,16 +55,16 @@ BIN :=		$(BIN_IN)
 SRC +=		$(BIN_SRC:%=bin/%)
 DIRT +=		$(BIN_IN:%=bin/%)
 
-QUILT_IN :=	add applied delete diff files import new next patches \
-		pop previous push refresh remove series setup top unapplied \
-		fold fork snapshot edit
+QUILT_IN :=	add applied delete diff edit files fold fork graph import \
+		new next patches pop previous push refresh remove series \
+		setup snapshot top unapplied
 
 QUILT_SRC :=	$(QUILT_IN:%=%.in)
 QUILT :=	$(QUILT_IN)
 SRC +=		$(QUILT_SRC:%=quilt/%)
 DIRT +=		$(QUILT_IN:%=quilt/%)
 
-SCRIPTS_IN :=	apatch rpatch patchfns parse-patch spec2series
+SCRIPTS_IN :=	apatch rpatch patchfns parse-patch spec2series dependency-graph
 SCRIPTS_SRC :=	$(SCRIPTS_IN:%=%.in)
 SCRIPTS :=	$(SCRIPTS_IN)
 SRC +=		$(SCRIPTS_SRC:%=scripts/%)
diff --git a/quilt.changes b/quilt.changes
index de6e2bc..abf8ca4 100644
--- a/quilt.changes
+++ b/quilt.changes
@@ -1,4 +1,13 @@
 -------------------------------------------------------------------
+Sat Mar 13 15:16:49 CET 2004 - agruen@suse.de
+
+- Add `quilt graph' command for generating a dependency graph
+  between patches. This requires the graphviz package for
+  removing transitive edges (optional) and for rendering the
+  graph. Please note that the graph command itself is minimal,
+  while the underlying scripts/dependency-graph is more flexible.
+
+-------------------------------------------------------------------
 Wed Mar 10 10:46:56 CET 2004 - agruen@suse.de
 
 - Quilt push/pop: exit with a non-zero status when beyond series.
diff --git a/quilt.spec.in b/quilt.spec.in
index 3907ea7..e71d5ef 100644
--- a/quilt.spec.in
+++ b/quilt.spec.in
@@ -49,6 +49,7 @@ rm -rf $RPM_BUILD_ROOT
 /usr/lib/quilt/
 /etc/bash_completion.d/quilt
 %doc %{_mandir}/man1/guards.1.gz
+%doc %{_mandir}/man1/quilt.1.gz
 %doc %{_docdir}/%{name}-%{version}/README
 %doc %{_docdir}/%{name}-%{version}/quilt.pdf
 
diff --git a/quilt/graph.in b/quilt/graph.in
new file mode 100644
index 0000000..3ce1f73
--- /dev/null
+++ b/quilt/graph.in
@@ -0,0 +1,142 @@
+#! @BASH@
+
+#  This script is free software; you can redistribute it and/or modify
+#  it under the terms of the GNU General Public License version 2 as
+#  published by the Free Software Foundation.
+#
+#  See the COPYING and AUTHORS files for more details.
+
+# Read in library functions
+if [ "$(type -t patch_file_name)" != function ]
+then
+	if ! [ -r @SCRIPTS@/patchfns ]
+	then
+		echo "Cannot read library @SCRIPTS@/patchfns" >&2
+		exit 1
+	fi
+	. @SCRIPTS@/patchfns
+fi
+
+usage()
+{
+	local redirect
+	if [ x$1 != x-h ]
+	then
+		redirect='>&2'
+	fi
+	echo $"Usage: quilt graph [-P path|--all] [--reduce] [--edge-labels=files]" $redirect
+
+	if [ x$1 = x-h ]
+	then
+		echo $"
+Generate a dot(1) directed graph showing the dependencies between
+applied patches. A patch depends on another patch if both touch the same
+file. Unless otherwise specified, the graph includes all patches that
+the topmost patch depends on.
+
+-P patch
+	Instead of the topmost patch, create a graph for the specified
+	patch. The graph will include all other patches that this patch
+	depends on, as well as all patches that depend on this patch.
+
+--all	Generate a graph including all patches and their dependencies.
+
+--reduce
+	Eliminate transitive edges from the graph.
+
+--edge-labels=files
+	Label graph edges with the file names that the adjacent patches
+	modify.
+
+-T ps	Directly produce a PostScript output file."
+		exit 0
+	else
+		exit 1
+	fi
+}
+
+options=`getopt -o P:T:h --long all,reduce,edge-labels: -- "$@"`
+
+if [ $? -ne 0 ]
+then
+	usage
+fi
+
+eval set -- "$options"
+
+while true
+do
+	case "$1" in
+	-P)
+		if ! patch=$(find_patch $2)
+		then
+			echo $"Patch $2 is not in series" >&2
+			exit 1
+		fi
+		if ! is_applied $patch
+		then
+			echo $"Patch $patch is not applied" >&2
+			exit 1
+		fi
+		shift 2 ;;
+
+	-T)	if [ "$2" != ps ]; then
+			usage
+		fi
+		opt_format=ps
+		shift 2 ;;
+
+	--all)
+		opt_all=1
+		shift ;;
+
+	--reduce)
+		opt_reduce=1
+		shift ;;
+
+	--edge-labels)
+		if [ "$2" != files ]
+		then
+			usage
+		fi
+		opt_edge_labels=$2
+		shift 2 ;;
+
+	-h)
+		usage -h ;;
+
+	--)
+		shift
+		break ;;
+	esac
+done
+
+if [ $# -ne 0 -o \( -n "$patch" -a -n "$opt_all" \) ]
+then
+	usage
+fi
+
+if [ -z "$opt_all" -a -z "$patch" ]
+then
+	patch=$(top_patch)
+	if [ -z "$patch" ]
+	then
+		echo $"No patches applied" >&2
+		exit 1
+	fi
+fi
+
+options=
+[ -n "$patch" ] && options="--select-patch $patch"
+[ -n "$opt_reduce" ] && options="$options --reduce"
+[ "$opt_edge_labels" = files ] && options="$options --edge-files"
+
+pipe=
+[ -n "$opt_format" ] && pipe="| dot -T$opt_format"
+
+applied_patches \
+| eval @SCRIPTS@/dependency-graph $options - $pipe
+### Local Variables:
+### mode: shell-script
+### End:
+# vim:filetype=sh
diff --git a/scripts/dependency-graph.in b/scripts/dependency-graph.in
new file mode 100644
index 0000000..a58e92b
--- /dev/null
+++ b/scripts/dependency-graph.in
@@ -0,0 +1,314 @@
+#!@PERL@ -w
+
+#  This script is free software; you can redistribute it and/or modify
+#  it under the terms of the GNU General Public License version 2 as
+#  published by the Free Software Foundation.
+#
+#  See the COPYING and AUTHORS files for more details.
+
+# Generate a dot-style graph of dependencies between patches.
+
+use Getopt::Long;
+use FileHandle;
+use strict;
+
+# Constants
+my $short_edge_style = "color=grey";
+my $close_node_style = "color=grey";
+my $highlighted_node_style = "style=bold";
+
+# Command line arguments
+my $help = 0;
+my $short_edge_thresh = 0;	# threshold for coloring as "short", 0 = disable
+my $long_edge_thresh = 0;	# threshold for coloring as "long",0 = disable
+my $edge_labels;		# label all edges with filenames
+my $short_edge_labels;		# label short edges with filenames
+my $long_edge_labels;		# label long edges with filenames
+my $edge_length_labels;		# distance between patches as edge labels
+my $node_numbers;		# include sequence numbers
+my $show_isolated_nodes;	# also include isolated nodes
+my $reduce;			# remove transitive edges
+my $mangle_patchnames;		# filter for compacting filenames
+my $selected_patch;		# only include patches related on this patch
+my $selected_distance = -1;	# infinity
+my @highlight_patches;		# a list of patches to highlight
+
+unless (GetOptions(
+	"h|help"		=> \$help,
+	"short-edge=i"		=> \$short_edge_thresh,
+	"long-edge=i"		=> \$long_edge_thresh,
+	"edge-files"		=> \$edge_labels,
+	"short-edge-files"	=> \$short_edge_labels,
+	"long-edge-files"	=> \$long_edge_labels,
+	"edge-length"		=> \$edge_length_labels,
+	"node-numbers"		=> \$node_numbers,
+	"isolated"		=> \$show_isolated_nodes,
+	"reduce"		=> \$reduce,
+	"mangle-patchnames=s"	=> \$mangle_patchnames,
+	"select-patch=s"	=> \$selected_patch,
+	"select-distance=i"	=> \$selected_distance,
+	"highlight=s"		=> \@highlight_patches ) && !$help) {
+    my $basename = $0;
+    $basename =~ s:.*/::;
+    my $fd = $help ? *STDOUT : *STDERR;
+    print $fd <<EOF;
+SYNOPSIS: $basename [-h] [--short-edge=num] [--long-edge=num]
+	  [--short-edge-files] [--long-edge-files] [--edge-length]
+	  [--node-numbers] [--isolated] [--reduce] [--mangle-patchnames=filter]
+	  [--select-patch=patch] [--select-distance=num] [--highlight=patch]
+
+--short-edge=num, --long-edge=num
+	Define the maximum edge length of short edges, and minimum edge
+	length of long edges. Short edges are de-emphasized, and long
+	edges are emphasized. The default is to treat all edges equally.
+
+-edge-files, --short-edge-files, --long-edge-files
+	Include conflicting filenames on all edges, short edges, or long
+	edges.
+
+--edge-length
+	Use the edge lengths as edge labels. Cannot be used together with
+	filename labels.
+
+--node-numbers
+	Include the sequence numbers of patches in the patch series in
+	node labels.
+
+--isolated
+	Do not suppress isolated nodes.
+
+--reduce
+	Remove transitive edges.
+
+--mangle-patchnames=filter
+	Define a filter command for transforming patch names into node
+	labels. The filter is passed each patch name on a separate line,
+	and must return the edge label for each patch on a separate line
+	(example: sed -e 's/^prefix//').
+
+--select-patch=patch
+	Reduce the graph to nodes that depend on the specified patch,
+	and nodes that the specified patch depends on (recursively).
+
+--select-distance=num
+	Limit the depth of recusion for --select-patch. The default is
+	to recurse exhaustively.
+
+--highlight=patch
+	Highlight the specified patch. This option can be specified more
+	than once.
+EOF
+    exit $help ? 0 : 1;
+}
+
+# Fetch the list of patches (all of them must be applied)
+my @patches;
+if (@ARGV) {
+    if (@ARGV == 1 && $ARGV[0] eq "-") {
+	@patches = map { chomp ; $_ } <STDIN>;
+    } else {
+	@patches = @ARGV;
+    }
+} else {
+    my $fh = new FileHandle("< .pc/applied-patches")
+	or die ".pc/applied-patches: $!\n";
+    @patches = map { chomp; $_ } <$fh>;
+    $fh->close();
+}
+
+# Fetch the list of files
+my @nodes;
+my $n = 0;
+foreach my $patch (@patches) {
+    if (! -d ".pc/$patch") {
+	print STDERR ".pc/$patch does not exist; skipping\n";
+	next;
+    }
+    my @files = split(/\n/, `cd .pc/$patch ; find -type f ! -name .timestamp`);
+    @files = map { s:\./::; $_ } @files;
+    push @nodes, {number=>$n++, name=>$patch, file=>$patch, files=>[ @files ] };
+}
+
+# If a patch is selected, limit the graph to nodes that depend on this patch,
+# and nodes that are dependent on this patch.
+if ($selected_patch) {
+    for ($n = 0; $n < @nodes; $n++) {
+	last if $nodes[$n]{file} eq $selected_patch;
+    }
+    die "Patch $selected_patch not included\n"
+	if ($n == @nodes);
+
+    my $selected_node = $nodes[$n];
+    push @{$selected_node->{attrs}}, $highlighted_node_style;
+
+    my %sel;
+    map { $sel{$_} = 1 } @{$selected_node->{files}};
+    map { $_->{files} = [ grep { exists $sel{$_} } @{$_->{files}} ] } @nodes;
+}
+
+# Optionally highlight a list of patches
+foreach my $patch (@highlight_patches) {
+    for ($n = 0; $n < @nodes; $n++) {
+	last if $nodes[$n]{file} eq $patch;
+    }
+    die "Patch $patch not included\n"
+	if ($n == @nodes);
+
+    my $node = $nodes[$n];
+    push @{$node->{attrs}}, $highlighted_node_style;
+    $node->{colorized} = 1;
+}
+
+# If a patch name mangling filter is selected, pipe all patchnames through
+# it.
+if ($mangle_patchnames) {
+    # FIXME: which patches ...
+    my $filter = new FileHandle("cat .pc/applied-patches | $mangle_patchnames |");
+    $n = 0;
+    foreach my $name (<$filter>) {
+	last unless $n < @nodes;
+	chomp $name;
+	if ($name eq "") {
+	    delete $nodes[$n++]{name};
+	} else {
+	    $nodes[$n++]{name} = $name;
+	}
+    }
+    $filter->close();
+}
+
+my %files_seen;		# remember the last patch that touched each file
+my %used_nodes;		# nodes to which at least one edge is attached
+my %edges;
+
+foreach my $node (@nodes) {
+    my $number = $node->{number};
+    foreach my $file (@{$node->{files}}) {
+	if (exists $files_seen{$file}) {
+	    push @{$edges{"$number:$files_seen{$file}"}{names}}, $file;
+	    $used_nodes{$number} = 1;
+	    $used_nodes{$files_seen{$file}} = 1;
+	}
+	$files_seen{$file} = $number;
+    }
+}
+
+# Create adjacency lists
+foreach my $node (@nodes) {
+    @{$node->{to}} = ();
+    @{$node->{from}} = ();
+}
+foreach my $key (keys %edges) {
+    my ($from, $to) = split /:/, $key;
+    push @{$nodes[$from]{to}}, $to;
+    push @{$nodes[$to]{from}}, $from;
+}
+
+# Colorize nodes that are close to each other
+foreach my $node (@nodes) {
+    if (!exists $node->{colorized} && !exists $used_nodes{$node->{number}}) {
+	$node->{colorized} = 1;
+	push @{$node->{attrs}}, $close_node_style;
+    }
+}
+
+# Colorize short and long edges
+foreach my $node (@nodes) {
+    my $close = 1;
+    foreach my $node2 (map {$nodes[$_]} @{$node->{to}}) {
+	if (abs($node2->{number} - $node->{number}) > $short_edge_thresh) {
+	    $close = 0
+	}
+    }
+    foreach my $node2 (map {$nodes[$_]} @{$node->{from}}) {
+	if (abs($node2->{number} - $node->{number}) > $short_edge_thresh) {
+	    $close = 0
+	}
+    }
+    if (!exists $node->{colorized} && $close) {
+	$node->{colorized} = 1;
+	push @{$node->{attrs}}, $close_node_style;
+    }
+}
+
+# Add node labels
+foreach my $node (@nodes) {
+    my @label = ();
+    push @label, $node->{number} + 1
+	if ($node_numbers);
+    push @label, $node->{name}
+	if exists $node->{name};
+    push @{$node->{attrs}}, "label=\"" . join(": ", @label) . "\"";
+}
+
+# Add edge labels
+foreach my $key (keys %edges) {
+    my ($from, $to) = split /:/, $key;
+    if ($edge_length_labels) {
+	push @{$edges{$key}->{attrs}}, "label=\"" . abs($to - $from) . "\""
+	    if abs($to - $from) > 1;
+    } elsif (abs($to - $from) < $short_edge_thresh) {
+	push @{$edges{$key}->{attrs}}, $short_edge_style;
+	if ($edge_labels || $short_edge_labels) {
+	    push @{$edges{$key}->{attrs}},
+		"label=\"" . join("\\n", @{$edges{$key}{names}}) . "\"";
+	}
+    } else {
+	if ($long_edge_thresh && abs($to - $from) > $long_edge_thresh) {
+	    push @{$edges{$key}->{attrs}}, "style=bold";
+	    if ($edge_labels || $long_edge_labels) {
+		push @{$edges{$key}->{attrs}},
+		    "label=\"" . join("\\n", @{$edges{$key}{names}}) . "\"";
+	    }
+	} else {
+	    if ($edge_labels) {
+		push @{$edges{$key}->{attrs}},
+		    "label=\"" . join("\\n", @{$edges{$key}{names}}) . "\"";
+	    }
+	}
+    }
+    # Compute a pseudo edge length so that neato works acceptably.
+    push @{$edges{$key}{attrs}}, "len=\"" .
+    	sprintf("%.2f", log(abs($to - $from) + 3)) . "\"";
+}
+
+#foreach my $node (@nodes) {
+#    push @{$node->{attrs}}, "shape=box";
+#}
+
+# Open output file / pipe
+my $out;
+if ($reduce) {
+    $out = new FileHandle("| tred")
+	or die "tred: $!\n";
+} else {
+    $out = new FileHandle("> /dev/stdout")
+	or die "$!\n";
+}
+
+# Write graph
+print $out "digraph dependencies {\n";
+#print "\tsize=\"11,8\"\n";
+foreach my $node (@nodes) {
+    next unless $show_isolated_nodes || exists $used_nodes{$node->{number}};
+    print $out "\tn$node->{number}";
+    if (exists $node->{attrs}) {
+	print $out " [" .
+	      join(",", @{$node->{attrs}}) . "]";
+    }
+    print $out ";\n";
+}
+
+sub w($) {
+    my @n = split /:/, shift;
+    return $n[0] * 10000 + $n[1];
+}
+foreach my $key (sort { w($a) <=> w($b) } keys %edges) {
+    my ($from, $to) = split /:/, $key;
+    print $out "\tn$to -> n$from";
+    if (exists $edges{$key}{attrs}) {
+	print $out " [" . join(",", @{$edges{$key}{attrs}}) . "]";
+    }
+    print $out ";\n";
+}
+print $out "}\n";