Re: BUG? in --dirstat when rearranging lines in a file

Linus Torvalds [off-list ref] writes:

On Fri, Apr 8, 2011 at 7:46 AM, Johan Herland [off-list ref] wrote:

quoted

#2: Improve --dirstat-by-file. It doesn't really care about the per-file
analysis done by --dirstat, but only whether or not a file has changed
at all. Since the diff queue does not contain unchanged files (<- this
is an assumption that I hope someone with more diffcore knowledge can
verify),

Hmm.

I think that with renames, the diff queue _can_ contain unchanged
files (ie pure renames).

Also, I think -CC (aka --find-copies-harder), _every_ file ends up in
the diff queue because that's how it does the detection.

Both are correct, but the output phase happens after diffcore_std() cleans
up the unused and unchanged filepairs thrown into the queue for the
purpose of find-copies-harder, so you shouldn't have to worry about them.

When you rename a file without changing its contents, what do you want to
see in --dirstat-by-file output?  I assume that you do not want to show
anything, so it would be sufficient to compare the two object names.

Here's a reroll of the previous series. Changes since v1:

- Adopt Junio's phrasing of the differences between --dirstat and
  regular diff (--stat)

- Detect and ignore pure renames in the diff queue. This is done by
  comparing the SHA1s of each file pair, and if they are equal, we
  know the files are identical, and should not show up in --dirstat.

  As an extra bonus in this version, when the SHA1s do match, we can
  bypass the usual --dirstat analysis, because we know it would find
  no changes. Instead, we can directly set damage = 0 in that case.

I've looked at the contents of the diff queue and resulting output in
a variety of cases:

- files with no changes, rearranged lines, and other changes
- files that are copied, moved, or not moved
- unstaged changes, staged changes, committed changes
- diff options: (none), --stat, --dirstat, and --dirstat-by-file
- diff options: (none), -M, and -C -C

(324 variations in total) and I'm fairly sure about the current patches
and how they interact with the diff queue.

A remaining question AFAICS is if there's a different (i.e. better) way
to (cheaply) estimate the damage contributed by code movements within a
file. The current "damage = 1" approach is somewhat crude, but IMHO
still better that ignoring code movements altogether.


Have fun! :)

...Johan


Johan Herland (3):
  --dirstat: Describe non-obvious differences relative to --stat or regular diff
  --dirstat-by-file: Make it faster and more correct
  Teach --dirstat to not completely ignore rearranged lines within a file

 Documentation/diff-options.txt                     |    4 ++
 diff.c                                             |   40 ++++++++++++++++++--
 t/t4013-diff-various.sh                            |   27 ++++++++++---
 .../diff.diff_--dirstat-by-file_initial_rearrange  |    3 +
 t/t4013/diff.diff_--dirstat_initial_rearrange      |    3 +
 ...tch_--stdout_--cover-letter_-n_initial..master^ |    2 +-
 t/t4013/diff.log_--decorate=full_--all             |    6 +++
 t/t4013/diff.log_--decorate_--all                  |    6 +++
 8 files changed, 80 insertions(+), 11 deletions(-)
 create mode 100644 t/t4013/diff.diff_--dirstat-by-file_initial_rearrange
 create mode 100644 t/t4013/diff.diff_--dirstat_initial_rearrange

-- 
1.7.5.rc1.3.g4d7b

Also add a testcase documenting the current behavior.

Improved-by: Junio C Hamano [off-list ref]
Signed-off-by: Johan Herland <redacted>
---
 Documentation/diff-options.txt                     |    4 +++
 t/t4013-diff-various.sh                            |   27 +++++++++++++++----
 t/t4013/diff.diff_--dirstat_initial_rearrange      |    2 +
 ...tch_--stdout_--cover-letter_-n_initial..master^ |    2 +-
 t/t4013/diff.log_--decorate=full_--all             |    6 ++++
 t/t4013/diff.log_--decorate_--all                  |    6 ++++
 6 files changed, 40 insertions(+), 7 deletions(-)
 create mode 100644 t/t4013/diff.diff_--dirstat_initial_rearrange

diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt
index c93124b..23772d6 100644
--- a/Documentation/diff-options.txt
+++ b/Documentation/diff-options.txt

@@ -72,6 +72,10 @@ endif::git-format-patch[]
 	a cut-off percent (3% by default) are not shown. The cut-off percent
 	can be set with `--dirstat=<limit>`. Changes in a child directory are not
 	counted for the parent directory, unless `--cumulative` is used.
++
+Note that the `--dirstat` option computes the changes while ignoring
+pure code movements within a file.  In other words, rearranging lines
+in a file is not counted as a change.
 
 --dirstat-by-file[=<limit>]::
 	Same as `--dirstat`, but counts changed files instead of lines.

diff --git a/t/t4013-diff-various.sh b/t/t4013-diff-various.sh
index 5daa0f2..3b1b392 100755
--- a/t/t4013-diff-various.sh
+++ b/t/t4013-diff-various.sh

@@ -80,18 +80,31 @@ test_expect_success setup '
 
 	git config log.showroot false &&
 	git commit --amend &&
+
+	GIT_AUTHOR_DATE="2006-06-26 00:06:00 +0000" &&
+	GIT_COMMITTER_DATE="2006-06-26 00:06:00 +0000" &&
+	export GIT_AUTHOR_DATE GIT_COMMITTER_DATE &&
+	git checkout -b rearrange initial &&
+	for i in B A; do echo $i; done >dir/sub &&
+	git add dir/sub &&
+	git commit -m "Rearranged lines in dir/sub" &&
+	git checkout master &&
+
 	git show-branch
 '
 
 : <<\EOF
 ! [initial] Initial
  * [master] Merge branch 'side'
-  ! [side] Side
----
- -  [master] Merge branch 'side'
- *+ [side] Side
- *  [master^] Second
-+*+ [initial] Initial
+  ! [rearrange] Rearranged lines in dir/sub
+   ! [side] Side
+----
+  +  [rearrange] Rearranged lines in dir/sub
+ -   [master] Merge branch 'side'
+ * + [side] Side
+ *   [master^] Third
+ *   [master~2] Second
++*++ [initial] Initial
 EOF
 
 V=`git version | sed -e 's/^git version //' -e 's/\./\\./g'`

@@ -287,6 +300,8 @@ diff --no-index --name-status -- dir2 dir
 diff --no-index dir dir3
 diff master master^ side
 diff --dirstat master~1 master~2
+# --dirstat doesn't notice changes that simply rearrange existing lines
+diff --dirstat initial rearrange
 EOF
 
 test_expect_success 'log -S requires an argument' '

diff --git a/t/t4013/diff.diff_--dirstat_initial_rearrange b/t/t4013/diff.diff_--dirstat_initial_rearrange
new file mode 100644
index 0000000..fb2e17d
--- /dev/null
+++ b/t/t4013/diff.diff_--dirstat_initial_rearrange

@@ -0,0 +1,2 @@
+$ git diff --dirstat initial rearrange
+$

diff --git a/t/t4013/diff.format-patch_--stdout_--cover-letter_-n_initial..master^ b/t/t4013/diff.format-patch_--stdout_--cover-letter_-n_initial..master^
index 1f0f9ad..3b4e113 100644
--- a/t/t4013/diff.format-patch_--stdout_--cover-letter_-n_initial..master^
+++ b/t/t4013/diff.format-patch_--stdout_--cover-letter_-n_initial..master^

@@ -1,7 +1,7 @@
 $ git format-patch --stdout --cover-letter -n initial..master^
 From 9a6d4949b6b76956d9d5e26f2791ec2ceff5fdc0 Mon Sep 17 00:00:00 2001
 From: C O Mitter <committer@example.com>
-Date: Mon, 26 Jun 2006 00:05:00 +0000
+Date: Mon, 26 Jun 2006 00:06:00 +0000
 Subject: [DIFFERENT_PREFIX 0/2] *** SUBJECT HERE ***
 
 *** BLURB HERE ***

diff --git a/t/t4013/diff.log_--decorate=full_--all b/t/t4013/diff.log_--decorate=full_--all
index d155e0b..44d4525 100644
--- a/t/t4013/diff.log_--decorate=full_--all
+++ b/t/t4013/diff.log_--decorate=full_--all

@@ -1,4 +1,10 @@
 $ git log --decorate=full --all
+commit cd4e72fd96faed3f0ba949dc42967430374e2290 (refs/heads/rearrange)
+Author: A U Thor <author@example.com>
+Date:   Mon Jun 26 00:06:00 2006 +0000
+
+    Rearranged lines in dir/sub
+
 commit 59d314ad6f356dd08601a4cd5e530381da3e3c64 (HEAD, refs/heads/master)
 Merge: 9a6d494 c7a2ab9
 Author: A U Thor <author@example.com>

diff --git a/t/t4013/diff.log_--decorate_--all b/t/t4013/diff.log_--decorate_--all
index fd7c3e6..27d3eab 100644
--- a/t/t4013/diff.log_--decorate_--all
+++ b/t/t4013/diff.log_--decorate_--all

@@ -1,4 +1,10 @@
 $ git log --decorate --all
+commit cd4e72fd96faed3f0ba949dc42967430374e2290 (rearrange)
+Author: A U Thor <author@example.com>
+Date:   Mon Jun 26 00:06:00 2006 +0000
+
+    Rearranged lines in dir/sub
+
 commit 59d314ad6f356dd08601a4cd5e530381da3e3c64 (HEAD, master)
 Merge: 9a6d494 c7a2ab9
 Author: A U Thor <author@example.com>

-- 
1.7.5.rc1.3.g4d7b

Currently, when using --dirstat-by-file, it first does the full --dirstat
analysis (using diffcore_count_changes()), and then resets 'damage' to 1,
if any damage was found by diffcore_count_changes().

But --dirstat-by-file is not interested in the file damage per se. It only
cares if the file changed at all. In that sense it only cares if the blob
SHA1 for a file has changed. We therefore only need to compare the SHA1s
of each file pair in the diff queue. As a result, we can skip the entire
--dirstat analysis and simply set 'damage' to 1 for each entry where the
SHA1 has changed.

This makes --dirstat-by-file faster, and also bypasses --dirstat's practice
of ignoring rearranged lines within a file.

The patch also contains an added testcase verifying that --dirstat-by-file
now detects changes that only rearrange lines within a file.

Signed-off-by: Johan Herland <redacted>
---
 diff.c                                             |   25 ++++++++++++++++----
 t/t4013-diff-various.sh                            |    2 +
 .../diff.diff_--dirstat-by-file_initial_rearrange  |    3 ++
 3 files changed, 25 insertions(+), 5 deletions(-)
 create mode 100644 t/t4013/diff.diff_--dirstat-by-file_initial_rearrange

diff --git a/diff.c b/diff.c
index 9fa8410..a224048 100644
--- a/diff.c
+++ b/diff.c

@@ -1538,9 +1538,27 @@ static void show_dirstat(struct diff_options *options)
 		struct diff_filepair *p = q->queue[i];
 		const char *name;
 		unsigned long copied, added, damage;
+		int content_changed;
 
 		name = p->one->path ? p->one->path : p->two->path;
 
+		if (p->one->sha1_valid && p->two->sha1_valid)
+			content_changed = hashcmp(p->one->sha1, p->two->sha1);
+		else
+			content_changed = 1;
+
+		if (DIFF_OPT_TST(options, DIRSTAT_BY_FILE)) {
+			/*
+			 * In --dirstat-by-file mode, we don't really need to
+			 * look at the actual file contents at all.
+			 * The fact that the SHA1 changed is enough for us to
+			 * add this file to the list of results
+			 * (with each file contributing equal damage).
+			 */
+			damage = content_changed ? 1 : 0;
+			goto found_damage;
+		}
+
 		if (DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {
 			diff_populate_filespec(p->one, 0);
 			diff_populate_filespec(p->two, 0);

@@ -1563,14 +1581,11 @@ static void show_dirstat(struct diff_options *options)
 		/*
 		 * Original minus copied is the removed material,
 		 * added is the new material.  They are both damages
-		 * made to the preimage. In --dirstat-by-file mode, count
-		 * damaged files, not damaged lines. This is done by
-		 * counting only a single damaged line per file.
+		 * made to the preimage.
 		 */
 		damage = (p->one->size - copied) + added;
-		if (DIFF_OPT_TST(options, DIRSTAT_BY_FILE) && damage > 0)
-			damage = 1;
 
+found_damage:
 		ALLOC_GROW(dir.files, dir.nr + 1, dir.alloc);
 		dir.files[dir.nr].name = name;
 		dir.files[dir.nr].changed = damage;

diff --git a/t/t4013-diff-various.sh b/t/t4013-diff-various.sh
index 3b1b392..6428a90 100755
--- a/t/t4013-diff-various.sh
+++ b/t/t4013-diff-various.sh

@@ -302,6 +302,8 @@ diff master master^ side
 diff --dirstat master~1 master~2
 # --dirstat doesn't notice changes that simply rearrange existing lines
 diff --dirstat initial rearrange
+# ...but --dirstat-by-file does notice changes that only rearrange lines
+diff --dirstat-by-file initial rearrange
 EOF
 
 test_expect_success 'log -S requires an argument' '

diff --git a/t/t4013/diff.diff_--dirstat-by-file_initial_rearrange b/t/t4013/diff.diff_--dirstat-by-file_initial_rearrange
new file mode 100644
index 0000000..e48e33f
--- /dev/null
+++ b/t/t4013/diff.diff_--dirstat-by-file_initial_rearrange

@@ -0,0 +1,3 @@
+$ git diff --dirstat-by-file initial rearrange
+ 100.0% dir/
+$

-- 
1.7.5.rc1.3.g4d7b

Currently, the --dirstat analysis fails to detect when lines within a
file are rearranged, because the "damage" calculated by show_dirstat()
is 0. However, if the SHA1 sum has changed, we already now that there
should be at least some minimum amount of damage.

This patch teaches show_dirstat() to assign a minimum amount of damage
(== 1) to entries for which the analysis otherwise yields zero damage.
Obviously this is not a complete fix, but it's at least better to
underrepresent these changes, rather than simply pretending that they
don't exist.

Also, with the added SHA1 comparison, we can safely skip the --dirstat
analysis when the SHA1s do happen to match (e.g. for a pure file rename)

Signed-off-by: Johan Herland <redacted>
---
 Documentation/diff-options.txt                |    4 ++--
 diff.c                                        |   19 ++++++++++++++++++-
 t/t4013-diff-various.sh                       |    2 --
 t/t4013/diff.diff_--dirstat_initial_rearrange |    1 +
 4 files changed, 21 insertions(+), 5 deletions(-)

diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt
index 23772d6..7e4bd42 100644
--- a/Documentation/diff-options.txt
+++ b/Documentation/diff-options.txt

@@ -74,8 +74,8 @@ endif::git-format-patch[]
 	counted for the parent directory, unless `--cumulative` is used.
 +
 Note that the `--dirstat` option computes the changes while ignoring
-pure code movements within a file.  In other words, rearranging lines
-in a file is not counted as a change.
+the amount of pure code movements within a file.  In other words,
+rearranging lines in a file is not counted as much as other changes.
 
 --dirstat-by-file[=<limit>]::
 	Same as `--dirstat`, but counts changed files instead of lines.

diff --git a/diff.c b/diff.c
index a224048..3e0bc1f 100644
--- a/diff.c
+++ b/diff.c

@@ -1547,6 +1547,16 @@ static void show_dirstat(struct diff_options *options)
 		else
 			content_changed = 1;
 
+		if (!content_changed) {
+			/*
+			 * The SHA1 has not changed, so pre-/post-content is
+			 * identical. We can therefore skip looking at the
+			 * file contents altogether.
+			 */
+			damage = 0;
+			goto found_damage;
+		}
+
 		if (DIFF_OPT_TST(options, DIRSTAT_BY_FILE)) {
 			/*
 			 * In --dirstat-by-file mode, we don't really need to

@@ -1555,7 +1565,7 @@ static void show_dirstat(struct diff_options *options)
 			 * add this file to the list of results
 			 * (with each file contributing equal damage).
 			 */
-			damage = content_changed ? 1 : 0;
+			damage = 1;
 			goto found_damage;
 		}
 

@@ -1582,8 +1592,15 @@ static void show_dirstat(struct diff_options *options)
 		 * Original minus copied is the removed material,
 		 * added is the new material.  They are both damages
 		 * made to the preimage.
+		 * If the resulting damage is zero, we know that
+		 * diffcore_count_changes() considers the two entries to
+		 * be identical, but since content_changed is true, we
+		 * know that there must have been _some_ kind of change,
+		 * so we force all entries to have damage > 0.
 		 */
 		damage = (p->one->size - copied) + added;
+		if (!damage)
+			damage = 1;
 
 found_damage:
 		ALLOC_GROW(dir.files, dir.nr + 1, dir.alloc);

diff --git a/t/t4013-diff-various.sh b/t/t4013-diff-various.sh
index 6428a90..93a6f20 100755
--- a/t/t4013-diff-various.sh
+++ b/t/t4013-diff-various.sh

@@ -300,9 +300,7 @@ diff --no-index --name-status -- dir2 dir
 diff --no-index dir dir3
 diff master master^ side
 diff --dirstat master~1 master~2
-# --dirstat doesn't notice changes that simply rearrange existing lines
 diff --dirstat initial rearrange
-# ...but --dirstat-by-file does notice changes that only rearrange lines
 diff --dirstat-by-file initial rearrange
 EOF
 

diff --git a/t/t4013/diff.diff_--dirstat_initial_rearrange b/t/t4013/diff.diff_--dirstat_initial_rearrange
index fb2e17d..5fb02c1 100644
--- a/t/t4013/diff.diff_--dirstat_initial_rearrange
+++ b/t/t4013/diff.diff_--dirstat_initial_rearrange

@@ -1,2 +1,3 @@
 $ git diff --dirstat initial rearrange
+ 100.0% dir/
 $

-- 
1.7.5.rc1.3.g4d7b

On Sun, Apr 10, 2011 at 3:48 PM, Johan Herland [off-list ref] wrote:

Here's a reroll of the previous series. Changes since v1:

The series looks fine to me,

       Linus

Johan Herland [off-list ref] writes:

Currently, the --dirstat analysis fails to detect when lines within a
file are rearranged, because the "damage" calculated by show_dirstat()
is 0. However, if the SHA1 sum has changed, we already now that there
should be at least some minimum amount of damage.

This logic is sensible, modulo that "fails to detect" is actually "ignores
mere line movements on purpose".

In any case, if the object names are different, we already know that there
is _some_ damage, and it is very unintiutive to claim that there is _no_
damage.

This patch teaches show_dirstat() to assign a minimum amount of damage
(== 1) to entries for which the analysis otherwise yields zero damage.

So it is perfectly in line with the above logic to give a minimum here.
Zero was simply just unintuitive, and this is a good fix to the problem.

Obviously this is not a complete fix, but it's at least better to

I however do not understand what "a complete fix" means in this context.
You've fixed the unintuitiveness, and as far as the description in the
introductory paragraph of the problem goes, I think this already is a
complete fix.

On Monday 11 April 2011, Junio C Hamano wrote:

Johan Herland [off-list ref] writes:

quoted

Currently, the --dirstat analysis fails to detect when lines within a
file are rearranged, because the "damage" calculated by show_dirstat()
is 0. However, if the SHA1 sum has changed, we already now that there
should be at least some minimum amount of damage.

This logic is sensible, modulo that "fails to detect" is actually
"ignores mere line movements on purpose".

I apologize for my commit message not having caught up with discussion 
around this issue. I came into the discussion from the POV of "--dirstat 
does not pick up what --stat picks up; there must be a bug in --dirstat", 
and my original objective was therefore to "fix" --dirstat to be "more like 
--stat". Obviously, I now know exactly why --dirstat is different, and that 
we don't want to fundamentally change it. My commit message should have been 
rephrased in a more positive light as a result. Feel free to fix before 
applying.

In any case, if the object names are different, we already know that
there is _some_ damage, and it is very unintiutive to claim that there
is _no_ damage.

Agreed.

quoted

This patch teaches show_dirstat() to assign a minimum amount of damage
(== 1) to entries for which the analysis otherwise yields zero damage.

So it is perfectly in line with the above logic to give a minimum here.
Zero was simply just unintuitive, and this is a good fix to the problem.

quoted

Obviously this is not a complete fix, but it's at least better to

I however do not understand what "a complete fix" means in this context.
You've fixed the unintuitiveness, and as far as the description in the
introductory paragraph of the problem goes, I think this already is a
complete fix.

I still feel that a file with 1000 rearranged lines should somehow count 
"more" than a file with only 1 rearranged line, but it's hard to get there 
without futzing with diffcore_count_changes(), probably making the whole 
thing considerably more expensive... So in that sense, I agree that the 
current solution is probably as complete as we can get.


...Johan

-- 
Johan Herland, [off-list ref]
www.herland.net