Add "--dirstat" for some directory statistics

Add "--dirstat" for some directory statistics

[Linus Torvalds]

This adds a new form of diffstat output, something that I have 
occasionally ended up doing manually (and badly, because it's actually 
pretty nasty to do), and that I think is very useful for an "overview" 
kind of thing in a project like the kernel that has a fairly deep and 
well-separated directory structure with semantic meaning.

What I mean by that is that it's often interesting from a patch standpoint 
to see which sub-directories are impacted by a patch, and to what degree.

What makes that more interesting is that the "impact" is often 
hierarchical: in the kernel, for example, something could either have a 
very localized impact to "fs/ext3/" and then it's interesting to see that 
such a patch changes mostly that subdirectory, but you could have another 
patch that changes some generic VFS-layer issue which affects _many_ 
subdirectories that are all under "fs/", but none - or perhaps just a 
couple of them - of the individual filesystems are interesting in 
themselves.

So what commonly happens is that you may have big changes in a specific 
sub-subdirectory, but still also significant separate changes to the 
subdirectory leading up to that - maybe you have significant VFS-level 
changes, but *also* changes under that VFS layer in the NFS-specific 
directories, for example. In that case, you do want the low-level parts 
that are significant to show up, but then the insignificant ones should 
show up as under the more generic top-level directory.

This patch shows all of that with "--dirstat". The output can be either 
something simple like

	commit 81772fe...
	Author: Thomas Gleixner <tglx@linutronix.de>
	Date:   Sun Feb 10 23:57:36 2008 +0100

	    x86: remove over noisy debug printk
	
	    pageattr-test.c contains a noisy debug printk that people reported.
	    The condition under which it prints (randomly tapping into a mem_map[]
	    hole and not being able to c_p_a() there) is valid behavior and not
	    interesting to report.
	
	    Remove it.
	
	    Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
	    Acked-by: Ingo Molnar <mingo@elte.hu>
	    Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
	
	 100% arch/x86/mm/
	 1 files changed, 0 insertions(+), 7 deletions(-)

or something much more complex like

	commit e231c2e...
	Author: David Howells <dhowells@redhat.com>
	Date:   Thu Feb 7 00:15:26 2008 -0800
	
	    Convert ERR_PTR(PTR_ERR(p)) instances to ERR_CAST(p)

	  20% crypto/
	   7% fs/afs/
	   7% fs/fuse/
	   7% fs/gfs2/
	   5% fs/jffs2/
	   5% fs/nfs/
	   5% fs/nfsd/
	   7% fs/reiserfs/
	  15% fs/
	   7% net/rxrpc/
	  10% security/keys/
	 28 files changed, 39 insertions(+), 39 deletions(-)

where that latter example is an example of significant work in some 
individual fs/*/ subdirectories (like the patches to reiserfs accounting 
for 7% of the whole), but then discounting those individual filesystems, 
there's also 15% other things left over under fs/ in general.

Note that the "15% fs/" mentioned above is the stuff that is under fs/ but 
that was _not_ significant enough to report on its own. So the above does 
_not_ mean that 15% of the work was under fs/ per se, because that 15% 
does *not* include the already-reported 7% of afs, 7% of fuse etc.

The reporting limit has been arbitrarily set at 3%, which seems to be a 
pretty good cut-off, but I made it an option variable in case anybody 
would ever want to make it a dynamic cutoff.

NOTE! The percentages are purely about the total lines added and removed, 
not anything smarter (or dumber) than that. Also note that you should not 
generally expect things to add up to 100%: not only does it round down, we 
don't report leftover scraps (they add up to the top-level change count, 
but we don't even bother reporting that, it only reports subdirectories).

Quite frankly, as a top-level manager this is really convenient for me, 
but it's going to be very boring for git itself since there are few 
subdirectories. Also, don't expect things to make tons of sense if you 
combine this with "-M" and there are cross-directory renames etc.

But even for git itself, you can get some fun statistics. Try out

	git log --dirstat

and see the occasional mentions of things like Documentation/, git-gui/, 
gitweb/ and gitk-git/. Or try out something like

	git diff --dirstat v1.5.0..v1.5.4

which does kind of git an overview that shows *something*. But in general, 
the output is more exciting for big projects with deeper structure, and 
doing a

	git diff --dirstat v2.6.24..v2.6.25-rc1

on the kernel is what I actually wrote this for!

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
Yeah, I'm proud of how small I could make this really cool feature. I had 
put off doing this because I always expected it to be harder than it was. 
But it was easy because I think I came up with a clever way to do it.

 diff.c |   74 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 diff.h |    2 +
 2 files changed, 75 insertions(+), 1 deletions(-)

diff --git a/diff.c b/diff.c
index 5b8afdc..da91bdd 100644
--- a/diff.c
+++ b/diff.c
@@ -980,6 +980,71 @@ static void show_numstat(struct diffstat_t* data, struct diff_options *options)
 	}
 }
 
+struct diffstat_dir {
+	struct diffstat_file **files;
+	int nr, percent;
+};
+
+static long gather_dirstat(struct diffstat_dir *dir, unsigned long changed, const char *base, int baselen)
+{
+	unsigned long this_dir = 0;
+
+	while (dir->nr) {
+		struct diffstat_file *f = *dir->files;
+		int namelen = strlen(f->name);
+		unsigned long this;
+		char *slash;
+
+		if (namelen < baselen)
+			break;
+		if (memcmp(f->name, base, baselen))
+			break;
+		slash = strchr(f->name + baselen, '/');
+		if (slash) {
+			int newbaselen = slash + 1 - f->name;
+			this = gather_dirstat(dir, changed, f->name, newbaselen);
+		} else {
+			this = f->added + f->deleted;
+			dir->files++;
+			dir->nr--;
+		}
+		this_dir += this;
+	}
+
+	if (baselen) {
+		int percent = this_dir * 100 / changed;
+		if (percent >= dir->percent) {
+			printf("%4d%% %.*s\n", percent, baselen, base);
+			return 0;
+		}
+	}
+	return this_dir;
+}
+
+static void show_dirstat(struct diffstat_t *data, struct diff_options *options)
+{
+	int i;
+	unsigned long changed;
+	struct diffstat_dir dir;
+
+	/* Calculate total changes */
+	changed = 0;
+	for (i = 0; i < data->nr; i++) {
+		changed += data->files[i]->added;
+		changed += data->files[i]->deleted;
+	}
+
+	/* This can happen even with many files, if everything was renames */
+	if (!changed)
+		return;
+
+	/* Show all directories with more than x% of the changes */
+	dir.files = data->files;
+	dir.nr = data->nr;
+	dir.percent = options->dirstat_percent;
+	gather_dirstat(&dir, changed, "", 0);
+}
+
 static void free_diffstat_info(struct diffstat_t *diffstat)
 {
 	int i;
@@ -2043,6 +2108,7 @@ void diff_setup(struct diff_options *options)
 	options->line_termination = '\n';
 	options->break_opt = -1;
 	options->rename_limit = -1;
+	options->dirstat_percent = 3;
 	options->context = 3;
 	options->msg_sep = "";
 
@@ -2084,6 +2150,7 @@ int diff_setup_done(struct diff_options *options)
 					    DIFF_FORMAT_NUMSTAT |
 					    DIFF_FORMAT_DIFFSTAT |
 					    DIFF_FORMAT_SHORTSTAT |
+					    DIFF_FORMAT_DIRSTAT |
 					    DIFF_FORMAT_SUMMARY |
 					    DIFF_FORMAT_PATCH);
 
@@ -2095,6 +2162,7 @@ int diff_setup_done(struct diff_options *options)
 				      DIFF_FORMAT_NUMSTAT |
 				      DIFF_FORMAT_DIFFSTAT |
 				      DIFF_FORMAT_SHORTSTAT |
+				      DIFF_FORMAT_DIRSTAT |
 				      DIFF_FORMAT_SUMMARY |
 				      DIFF_FORMAT_CHECKDIFF))
 		DIFF_OPT_SET(options, RECURSIVE);
@@ -2205,6 +2273,8 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)
 		options->output_format |= DIFF_FORMAT_NUMSTAT;
 	else if (!strcmp(arg, "--shortstat"))
 		options->output_format |= DIFF_FORMAT_SHORTSTAT;
+	else if (!strcmp(arg, "--dirstat"))
+		options->output_format |= DIFF_FORMAT_DIRSTAT;
 	else if (!strcmp(arg, "--check"))
 		options->output_format |= DIFF_FORMAT_CHECKDIFF;
 	else if (!strcmp(arg, "--summary"))
@@ -2923,7 +2993,7 @@ void diff_flush(struct diff_options *options)
 		separator++;
 	}
 
-	if (output_format & (DIFF_FORMAT_DIFFSTAT|DIFF_FORMAT_SHORTSTAT|DIFF_FORMAT_NUMSTAT)) {
+	if (output_format & (DIFF_FORMAT_DIFFSTAT|DIFF_FORMAT_SHORTSTAT|DIFF_FORMAT_NUMSTAT|DIFF_FORMAT_DIRSTAT)) {
 		struct diffstat_t diffstat;
 
 		memset(&diffstat, 0, sizeof(struct diffstat_t));
@@ -2933,6 +3003,8 @@ void diff_flush(struct diff_options *options)
 			if (check_pair_status(p))
 				diff_flush_stat(p, options, &diffstat);
 		}
+		if (output_format & DIFF_FORMAT_DIRSTAT)
+			show_dirstat(&diffstat, options);
 		if (output_format & DIFF_FORMAT_NUMSTAT)
 			show_numstat(&diffstat, options);
 		if (output_format & DIFF_FORMAT_DIFFSTAT)
diff --git a/diff.h b/diff.h
index 073d5cb..3181263 100644
--- a/diff.h
+++ b/diff.h
@@ -30,6 +30,7 @@ typedef void (*diff_format_fn_t)(struct diff_queue_struct *q,
 #define DIFF_FORMAT_SUMMARY	0x0008
 #define DIFF_FORMAT_PATCH	0x0010
 #define DIFF_FORMAT_SHORTSTAT	0x0020
+#define DIFF_FORMAT_DIRSTAT	0x0020
 
 /* These override all above */
 #define DIFF_FORMAT_NAME	0x0100
@@ -80,6 +81,7 @@ struct diff_options {
 	int pickaxe_opts;
 	int rename_score;
 	int rename_limit;
+	int dirstat_percent;
 	int setup;
 	int abbrev;
 	const char *msg_sep;

Re: Add "--dirstat" for some directory statistics

[Linus Torvalds]

On Mon, 11 Feb 2008, Linus Torvalds wrote:
> 
> The reporting limit has been arbitrarily set at 3%, which seems to be a 
> pretty good cut-off, but I made it an option variable in case anybody 
> would ever want to make it a dynamic cutoff.

Side note: that 3% isn't actually _too_ arbitrary.  I did actually test
things a bit. 

So it seems to be a good limit that ensures that you'll basically never
see more than one page worth of reporting (if you did, it wouldn't be a
very good summary).  So in theory, if something is _just_ right and
really balanced out across a wide variety of directories, you can get 33
lines of output, but in practice it's unusual to get more than 10-15
entries. 

In the kernel, the most spread out commit I've found so far is 18 entries:

    CONFIG_HIGHPTE vs. sub-page page tables.

   3% arch/powerpc/mm/
   5% arch/sparc/mm/
   6% arch/
   5% include/asm-alpha/
   3% include/asm-avr32/
   3% include/asm-cris/
   4% include/asm-ia64/
   6% include/asm-m68k/
   3% include/asm-mips/
   7% include/asm-powerpc/
   6% include/asm-sh/
   4% include/asm-sparc64/
   3% include/asm-um/
   6% include/asm-x86/
   3% include/asm-xtensa/
   3% include/linux/
  14% include/
   7% mm/
 53 files changed, 326 insertions(+), 132 deletions(-)

but it's not like I looked through all of them (and I'm sure you can get
more if you select just the right commit range to generate the diff).

The point being that a 4-percent cut-off would likely be so big that it
would have hidden the details in the above example.

A 2% cut-off is worth trying, though.  It does get a bit more detail,
and the likelihood of it actually causing a 50-line report is probably
vanishingly small, so it might be worth playing around with.  The above
18-entry example grows to 23 entries with a 2% limit, which is very
borderline on a traditional 80x24 terminal, but still just barely "one
page" which was my personal rule to aim for. 

			Linus

Re: Add "--dirstat" for some directory statistics

[Johannes Schindelin]

Hi,

On Mon, 11 Feb 2008, Linus Torvalds wrote:

>  #define DIFF_FORMAT_SHORTSTAT	0x0020
> +#define DIFF_FORMAT_DIRSTAT	0x0020

Certainly you meant 0x0040 for DIRSTAT, n'est-ce pas?

Also, are you sure that you do not want to make the minimal percentage 
configurable, maybe with --dirstat[=<min-percent>]?  I mean, sometimes 
even 0.01% is worth showing.

Ciao,
Dscho

Re: Add "--dirstat" for some directory statistics

[Linus Torvalds]

On Mon, 11 Feb 2008, Johannes Schindelin wrote:
> 
> Certainly you meant 0x0040 for DIRSTAT, n'est-ce pas?

Yeah, yeah.

> Also, are you sure that you do not want to make the minimal percentage 
> configurable, maybe with --dirstat[=<min-percent>]?  I mean, sometimes 
> even 0.01% is worth showing.

Well, maybe, maybe not. But yeah, at least in whole percentages. Here is a 
simple patch to fix that cut-and-past'o and add a configurable (but still 
whole-percentage-point) thing.

		Linus

---
 diff.c |    2 +-
 diff.h |    2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/diff.c b/diff.c
index da91bdd..81948e7 100644
--- a/diff.c
+++ b/diff.c
@@ -2273,7 +2273,7 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)
 		options->output_format |= DIFF_FORMAT_NUMSTAT;
 	else if (!strcmp(arg, "--shortstat"))
 		options->output_format |= DIFF_FORMAT_SHORTSTAT;
-	else if (!strcmp(arg, "--dirstat"))
+	else if (opt_arg(arg, 'X', "dirstat", &options->dirstat_percent))
 		options->output_format |= DIFF_FORMAT_DIRSTAT;
 	else if (!strcmp(arg, "--check"))
 		options->output_format |= DIFF_FORMAT_CHECKDIFF;
diff --git a/diff.h b/diff.h
index 3181263..9da6601 100644
--- a/diff.h
+++ b/diff.h
@@ -30,7 +30,7 @@ typedef void (*diff_format_fn_t)(struct diff_queue_struct *q,
 #define DIFF_FORMAT_SUMMARY	0x0008
 #define DIFF_FORMAT_PATCH	0x0010
 #define DIFF_FORMAT_SHORTSTAT	0x0020
-#define DIFF_FORMAT_DIRSTAT	0x0020
+#define DIFF_FORMAT_DIRSTAT	0x0040
 
 /* These override all above */
 #define DIFF_FORMAT_NAME	0x0100

Re: Add "--dirstat" for some directory statistics

[Linus Torvalds]

On Mon, 11 Feb 2008, Johannes Schindelin wrote:
> 
> I mean, sometimes even 0.01% is worth showing.

I tried this, and no. It's not. Not even 0.1%. If you care at that level,  
you're better off just looking at the diffstat itself. The noise factor 
with the summary makes it useless with even 0.1%.

That said, the *reporting* sometimes looks better with tenths of percents. 
This is an example of "report in tenths of percent, limit to 1%":

   4.8% arch/um/include/
   6.1% arch/um/os-Linux/drivers/
   5.7% arch/um/os-Linux/include/
   2.6% arch/um/os-Linux/skas/
   1.7% arch/um/os-Linux/sys-i386/
   9.2% arch/um/os-Linux/sys-x86_64/
  69.6% arch/um/os-Linux/

and maybe that format would be nicer (and more "future proof" in case 
people want to make the limiting go down to fractional percentages too).

If people want to play around with it, here's a trial patch (and yes, if 
you want it down to 0.1%, you can use "--dirstat=0", and it will only 
remove the ones that really round down to 0.0%, but it really isn't any 
good for summaries any more).

For summaries, I'd suggest testing with something like

	git diff --dirstat=? v2.6.23..v2.6.24

and comparing the 0% cutoff (pretty damn useless) to 1 (already *much* 
better and perhaps appropriate as a "deep summary") to 2 (probably the 
best if you actually want a short summary) to 3 (fairly similar, but 
dropped a few "2.x%" cases that were relevant).

The 1% cutoff case is already big enough that I don't think it's good as a 
summary, and while it contains "more information", it's actually likely 
much more informative in that case to do the default 3% case, and then 
noticing that "drivers" and "include" are pretty high, and at that point 
it makes sense to say "ok, let's re-do it but limiting it to that 
subdirectory", and do a

	git diff --dirstat=3 v2.6.23..v2.6.24 drivers/

where now you'll actually see *more* information than for the 1% case, but 
only as it pertains for that drivers subdirectory.

So I seriously doubt that you often want to have small percentages, and 
that it's much more productive to give people the overview and then they 
can "drill down" into that overview.

Anyway, here's the patch to try out..

		Linus

---
 diff.c |   11 ++++++++-----
 1 files changed, 7 insertions(+), 4 deletions(-)

diff --git a/diff.c b/diff.c
--- a/diff.c
+++ b/diff.c
@@ -1012,10 +1012,13 @@ static long gather_dirstat(struct diffstat_dir *dir, unsigned long changed, cons
 	}
 
 	if (baselen) {
-		int percent = this_dir * 100 / changed;
-		if (percent >= dir->percent) {
-			printf("%4d%% %.*s\n", percent, baselen, base);
-			return 0;
+		int permille = this_dir * 1000 / changed;
+		if (permille) {
+			int percent = permille / 10;
+			if (percent >= dir->percent) {
+				printf("%4d.%01d%% %.*s\n", percent, permille % 10, baselen, base);
+				return 0;
+			}
 		}
 	}
 	return this_dir;

Re: Add "--dirstat" for some directory statistics

[Linus Torvalds]

On Mon, 11 Feb 2008, Linus Torvalds wrote:
> 
> Anyway, here's the patch to try out..

Ok, one more (final, I promise!) patch..

There's another issue: I think the non-cumulative percentages are more 
interesting, but perhaps somebody disagrees. So here's a patch that allows 
you to say

	git diff --dirstat --cumulative v2.6.24..v2.6.25-rc1

and now the percentages will accumulate into the parent directory even 
when they are printed out.

Example difference:

 - without --cumulative:

	   3.2% arch/arm/
	   6.9% arch/powerpc/
	   3.2% arch/sh/
	   6.9% arch/x86/
	  11.0% arch/
	   3.7% drivers/media/
	   7.3% drivers/net/wireless/
	   6.9% drivers/net/
	  19.1% drivers/
	   3.5% fs/
	  10.3% include/
	   6.0% net/
	   3.7% sound/

 - with --cumulative:

	   3.2% arch/arm/
	   6.9% arch/powerpc/
	   3.2% arch/sh/
	   6.9% arch/x86/
	  31.3% arch/
	   3.7% drivers/media/
	   7.3% drivers/net/wireless/
	  14.3% drivers/net/
	  37.2% drivers/
	   3.5% fs/
	  10.3% include/
	   6.0% net/
	   3.7% sound/

and note how the latter may be more "logical" (ie it now says "31.3% arch" 
which simply means that about a third of the changes were somewhere under 
the arch/ subdirectory), it's obvious why I don't like it in general (even 
if it's wonderful in this case) when you start looking at other examples:

 - without --cumulative:

	 100.0% arch/x86/mm/

 - with --cumulative:

	 100.0% arch/x86/mm/
	 100.0% arch/x86/
	 100.0% arch/

which is obviously just noise and confusion, and not helpful at all.

But here's a trial patch against my original patch (ie this contains it 
all - the trivial fixes, tenths of percent reporting, and now the 
cumulative flag too). I was too lazy to try to split it up, and I hadn't 
committed the previous ones in between (bad Linus!).

		Linus

---
 diff.c |   19 +++++++++++++------
 diff.h |    3 ++-
 2 files changed, 15 insertions(+), 7 deletions(-)

diff --git a/diff.c b/diff.c
index da91bdd..e5b8baa 100644
--- a/diff.c
+++ b/diff.c
@@ -982,7 +982,7 @@ static void show_numstat(struct diffstat_t* data, struct diff_options *options)
 
 struct diffstat_dir {
 	struct diffstat_file **files;
-	int nr, percent;
+	int nr, percent, cumulative;
 };
 
 static long gather_dirstat(struct diffstat_dir *dir, unsigned long changed, const char *base, int baselen)
@@ -1012,10 +1012,14 @@ static long gather_dirstat(struct diffstat_dir *dir, unsigned long changed, cons
 	}
 
 	if (baselen) {
-		int percent = this_dir * 100 / changed;
-		if (percent >= dir->percent) {
-			printf("%4d%% %.*s\n", percent, baselen, base);
-			return 0;
+		int permille = this_dir * 1000 / changed;
+		if (permille) {
+			int percent = permille / 10;
+			if (percent >= dir->percent) {
+				printf("%4d.%01d%% %.*s\n", percent, permille % 10, baselen, base);
+				if (!dir->cumulative)
+					return 0;
+			}
 		}
 	}
 	return this_dir;
@@ -1042,6 +1046,7 @@ static void show_dirstat(struct diffstat_t *data, struct diff_options *options)
 	dir.files = data->files;
 	dir.nr = data->nr;
 	dir.percent = options->dirstat_percent;
+	dir.cumulative = options->output_format & DIFF_FORMAT_CUMULATIVE;
 	gather_dirstat(&dir, changed, "", 0);
 }
 
@@ -2273,8 +2278,10 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)
 		options->output_format |= DIFF_FORMAT_NUMSTAT;
 	else if (!strcmp(arg, "--shortstat"))
 		options->output_format |= DIFF_FORMAT_SHORTSTAT;
-	else if (!strcmp(arg, "--dirstat"))
+	else if (opt_arg(arg, 'X', "dirstat", &options->dirstat_percent))
 		options->output_format |= DIFF_FORMAT_DIRSTAT;
+	else if (!strcmp(arg, "--cumulative"))
+		options->output_format |= DIFF_FORMAT_CUMULATIVE;
 	else if (!strcmp(arg, "--check"))
 		options->output_format |= DIFF_FORMAT_CHECKDIFF;
 	else if (!strcmp(arg, "--summary"))
diff --git a/diff.h b/diff.h
index 3181263..8c6bb54 100644
--- a/diff.h
+++ b/diff.h
@@ -30,7 +30,8 @@ typedef void (*diff_format_fn_t)(struct diff_queue_struct *q,
 #define DIFF_FORMAT_SUMMARY	0x0008
 #define DIFF_FORMAT_PATCH	0x0010
 #define DIFF_FORMAT_SHORTSTAT	0x0020
-#define DIFF_FORMAT_DIRSTAT	0x0020
+#define DIFF_FORMAT_DIRSTAT	0x0040
+#define DIFF_FORMAT_CUMULATIVE	0x0080
 
 /* These override all above */
 #define DIFF_FORMAT_NAME	0x0100