[PATCH 1/2] git-commit: Disallow unchanged tree in non-merge mode

[PATCH 1/2] git-commit: Disallow unchanged tree in non-merge mode

[Dmitry V. Levin]

Do not commit an unchanged tree in non-merge mode.

While regular mode is already handled by git-runstatus, this cheap check
allows to avoid costly git-runstatus later.  Also, amend mode needs
special attention, because git-runstatus return value is ignored.
The idea is that amend should not commit an unchanged tree,
one should just remove the top commit using git-reset instead.

Signed-off-by: Dmitry V. Levin <ldv@altlinux.org>
---
 git-commit.sh |   10 ++++++++++
 1 files changed, 10 insertions(+), 0 deletions(-)

diff --git a/git-commit.sh b/git-commit.sh
index 1d04f1f..800f96c 100755
--- a/git-commit.sh
+++ b/git-commit.sh
@@ -629,6 +629,16 @@ then
 		tree=$(GIT_INDEX_FILE="$TMP_INDEX" git write-tree) &&
 		rm -f "$TMP_INDEX"
 	fi &&
+	if test -n "$current" -a ! -f "$GIT_DIR/MERGE_HEAD"
+	then
+		current_tree="$(git cat-file commit "$current${amend:+^}" 2>/dev/null |
+				sed -e '/^tree \+/!d' -e 's///' -e q)"
+		if test "$tree" = "$current_tree"
+		then
+			echo >&2 "nothing to commit${amend:+ (use \"git reset HEAD^\" to remove the top commit)}"
+			false
+		fi
+	fi &&
 	commit=$(git commit-tree $tree $PARENTS <"$GIT_DIR/COMMIT_MSG") &&
 	rlogm=$(sed -e 1q "$GIT_DIR"/COMMIT_MSG) &&
 	git update-ref -m "$GIT_REFLOG_ACTION: $rlogm" HEAD $commit "$current" &&
-- 
ldv

Re: [PATCH 1/2] git-commit: Disallow unchanged tree in non-merge mode

[Shawn O. Pearce]

"Dmitry V. Levin" <ldv@altlinux.org> wrote:
> Do not commit an unchanged tree in non-merge mode.

A laudable goal.  git-gui also does this.  Turns out the other
checks within git-gui prevent the user from ever getting that far.
I probably should remove the empty tree check as it costs CPU time
to get the old tree.  But I'd rather have the safety check.
 
> The idea is that amend should not commit an unchanged tree,
> one should just remove the top commit using git-reset instead.

NO.  `git commit --amend` is *often* used for fixing the commit
message.  Or adding additional detail.  Forcing the user to do
a `git reset --soft HEAD^ && git commit --amend` just because
you don't want git-commit to make an "empty commit" (which it
doesn't usually like to do now anyway!) is a major step back
in functionality.

NACK.
 
> diff --git a/git-commit.sh b/git-commit.sh
> index 1d04f1f..800f96c 100755
> --- a/git-commit.sh
> +++ b/git-commit.sh
> @@ -629,6 +629,16 @@ then
>  		tree=$(GIT_INDEX_FILE="$TMP_INDEX" git write-tree) &&
>  		rm -f "$TMP_INDEX"
>  	fi &&
> +	if test -n "$current" -a ! -f "$GIT_DIR/MERGE_HEAD"
> +	then
> +		current_tree="$(git cat-file commit "$current${amend:+^}" 2>/dev/null |
> +				sed -e '/^tree \+/!d' -e 's///' -e q)"

The better way to get the old tree would be this:

		current_tree="$(git rev-parse "$current${amend:+^}^{tree}" 2>/dev/null

as it avoids the tool from needing to know about the internal
representation of a commit object.  It also avoids an entire
fork+exec of a sed process.

> +		if test "$tree" = "$current_tree"
> +		then
> +			echo >&2 "nothing to commit${amend:+ (use \"git reset HEAD^\" to remove the top commit)}"

That message is a bad idea.  Doing a mixed mode reset will also
reset the index, causing the user to lose any changes that had
already been staged.  This may actually be difficult for him/her to
recover from if they have used `git add -i` or git-gui to stage only
certain hunks of files, or if their working tree has been further
modified after the commit but they want to go back and amend the
message only of the prior commit.

-- 
Shawn.

Re: [PATCH 1/2] git-commit: Disallow unchanged tree in non-merge mode

[Dmitry V. Levin]

[-- Attachment #1: Type: text/plain, Size: 2474 bytes --]

On Wed, Sep 05, 2007 at 10:25:39PM -0400, Shawn O. Pearce wrote:
> "Dmitry V. Levin" <ldv@altlinux.org> wrote:
> > Do not commit an unchanged tree in non-merge mode.
> 
> A laudable goal.  git-gui also does this.  Turns out the other
> checks within git-gui prevent the user from ever getting that far.
> I probably should remove the empty tree check as it costs CPU time
> to get the old tree.  But I'd rather have the safety check.
>  
> > The idea is that amend should not commit an unchanged tree,
> > one should just remove the top commit using git-reset instead.
> 
> NO.  `git commit --amend` is *often* used for fixing the commit
> message.

You see, my proposed change does not affect this usage case at all.

> Or adding additional detail.

If that "additional" detail just undoes the latest commit, why should
"git commit --amend" welcome such thing?  I did not get your pint here.

> Forcing the user to do
> a `git reset --soft HEAD^ && git commit --amend` just because
> you don't want git-commit to make an "empty commit" (which it
> doesn't usually like to do now anyway!) is a major step back
> in functionality.

I suppose that helping users to avoid doing really stupid things
does not look as a major step back in functionality, just otherwise.

> > +		current_tree="$(git cat-file commit "$current${amend:+^}" 2>/dev/null |
> > +				sed -e '/^tree \+/!d' -e 's///' -e q)"
> 
> The better way to get the old tree would be this:
> 
> 		current_tree="$(git rev-parse "$current${amend:+^}^{tree}" 2>/dev/null
> 
> as it avoids the tool from needing to know about the internal
> representation of a commit object.  It also avoids an entire
> fork+exec of a sed process.

Agreed.

> > +		if test "$tree" = "$current_tree"
> > +		then
> > +			echo >&2 "nothing to commit${amend:+ (use \"git reset HEAD^\" to remove the top commit)}"
> 
> That message is a bad idea.  Doing a mixed mode reset will also
> reset the index, causing the user to lose any changes that had
> already been staged.  This may actually be difficult for him/her to
> recover from if they have used `git add -i` or git-gui to stage only
> certain hunks of files, or if their working tree has been further
> modified after the commit but they want to go back and amend the
> message only of the prior commit.

Would "git reset --soft HEAD^" advice be better than first one?
Could you suggest a better message, please?


-- 
ldv

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 1/2] git-commit: Disallow unchanged tree in non-merge mode

[Linus Torvalds]

On Thu, 13 Sep 2007, Linus Torvalds wrote:
> 
> Ok, I'm downloading those tar-balls to reproduce and hopefully see what's 
> going on, but I'm not going to be able to get at it today.

Ok, I'm seeing it, and there are serious problems in the diffcore-rename 
code.

The problems include things like actual overflow in 31 bits (a signed 
integer) from the multiplication of "num_create * num_src".

But you'll almost certainly never even get there, because you'd long since 
have given up on the O(n^2) behaviour of the "cheap tests", that aren't 
really cheap enough, if only because even just comparing the 20-byte SHA1 
hashes will basically take forever since they will always miss in the 
cache for lots of names.

So yes, we really *have* to have a rename limit, even if it's only to 
avoid the technical bug of overflowing the multiplication.

Testing this actually showed another bug too: "git diff" would actually 
never call "diff_setup_done() at all, if "diffopt.output_format" had been 
set explicitly to something. So doing a "git diff --stat" would totally 
ignore all the sanity checks (and, what caused me to find it, the 
initialization of "diffopt.rename_limit") that diff_setup_done() is 
supposed to do!

So I'm going to send out two patches - one to fix the "diff_setup_done()" 
bug, and one that replaces the default rename_limit with something saner. 
Both seem to be real bugs.

			Linus

[PATCH 1/2] Fix "git diff" setup code

[Linus Torvalds]

For some inexplicable reason, "git diff" would call "diff_setup_done()" 
iff we hadn't given an explicit output format.

That makes no sense, since much of what diff_setup_done() does is exactly 
about checking the output format!

This just moves the call to "diff_setup_done()" out of the conditional, 
and to where we've actually done all of the diffopt changes.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 builtin-diff.c |    7 +++----
 1 files changed, 3 insertions(+), 4 deletions(-)

diff --git a/builtin-diff.c b/builtin-diff.c
index f77352b..cb4743b 100644
--- a/builtin-diff.c
+++ b/builtin-diff.c
@@ -252,13 +252,12 @@ int cmd_diff(int argc, const char **argv, const char *prefix)
 		argc = 0;
 	else
 		argc = setup_revisions(argc, argv, &rev, NULL);
-	if (!rev.diffopt.output_format) {
+	if (!rev.diffopt.output_format)
 		rev.diffopt.output_format = DIFF_FORMAT_PATCH;
-		if (diff_setup_done(&rev.diffopt) < 0)
-			die("diff_setup_done failed");
-	}
 	rev.diffopt.allow_external = 1;
 	rev.diffopt.recursive = 1;
+	if (diff_setup_done(&rev.diffopt) < 0)
+		die("diff_setup_done failed");
 
 	/* If the user asked for our exit code then don't start a
 	 * pager or we would end up reporting its exit code instead.

[PATCH 2/2] Fix the rename detection limit checking

[Linus Torvalds]

This adds more proper rename detection limits. Instead of just checking 
the limit against the number of potential rename destinations, we verify 
that the rename matrix (which is what really matters) doesn't grow 
ridiculously large, and we also make sure that we don't overflow when 
doing the matrix size calculation.

This also changes the default limits from unlimited, to a rename matrix 
that is limited to 100 entries on a side. You can raise it with the config 
entry, or by using the "-l<n>" command line flag, but at least the default 
is now a sane number that avoids spending lots of time (and memory) in 
situations that likely don't merit it.

The choice of default value is of course very debatable. Limiting the 
rename matrix to a 100x100 size will mean that even if you have just one 
obvious rename, but you also create (or delete) 10,000 files, the rename 
matrix will be so big that we disable the heuristics. Sounds reasonable to 
me, but let's see if people hit this (and, perhaps more importantly, 
actually *care*) in real life.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

Due to the overflow issue (and yes, Dmitry's test-case actually triggered 
an overflow even on 64-bit machines, because the math was done on "int" 
types), I really think this was a real bug.

Now, whether this is necessarily the right way to fix it, I dunno, but it 
also *does* fix the old broken limit handling that was based just on the 
number of target files, and didn't take the number of potential source 
files into account.

But the fix to that logic also means that the meaning of "-l<n>" changes 
subtly. For the better, I think, but changes nonetheless.

I'd also like to apologize to the change in wt-status.c, but that code 
doesn't use the regular diffopt setup logic, so it really is a special 
case and needs to be handled as such. Do we want to teach "git runstatus" 
to actually honor command line flags for diff generation etc? That's a 
separate question, this patch just makes it use the same rename default as 
the normal diffs now do.

 diff.c            |    2 +-
 diffcore-rename.c |   19 +++++++++++++++++--
 wt-status.c       |    1 +
 3 files changed, 19 insertions(+), 3 deletions(-)

diff --git a/diff.c b/diff.c
index 1aca5df..0ee9ea1 100644
--- a/diff.c
+++ b/diff.c
@@ -17,7 +17,7 @@
 #endif
 
 static int diff_detect_rename_default;
-static int diff_rename_limit_default = -1;
+static int diff_rename_limit_default = 100;
 static int diff_use_color_default;
 int diff_auto_refresh_index = 1;
 
diff --git a/diffcore-rename.c b/diffcore-rename.c
index 6bde439..41b35c3 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -298,10 +298,25 @@ void diffcore_rename(struct diff_options *options)
 		else if (detect_rename == DIFF_DETECT_COPY)
 			register_rename_src(p->one, 1, p->score);
 	}
-	if (rename_dst_nr == 0 || rename_src_nr == 0 ||
-	    (0 < rename_limit && rename_limit < rename_dst_nr))
+	if (rename_dst_nr == 0 || rename_src_nr == 0)
 		goto cleanup; /* nothing to do */
 
+	/*
+	 * This basically does a test for the rename matrix not
+	 * growing larger than a "rename_limit" square matrix, ie:
+	 *
+	 *    rename_dst_nr * rename_src_nr > rename_limit * rename_limit
+	 *
+	 * but handles the potential overflow case specially (and we
+	 * assume at least 32-bit integers)
+	 */
+	if (rename_limit <= 0 || rename_limit > 32767)
+		rename_limit = 32767;
+	if (rename_dst_nr > rename_limit && rename_src_nr > rename_limit)
+		goto cleanup;
+	if (rename_dst_nr * rename_src_nr > rename_limit * rename_limit)
+		goto cleanup;
+
 	/* We really want to cull the candidates list early
 	 * with cheap tests in order to avoid doing deltas.
 	 * The first round matches up the up-to-date entries,
diff --git a/wt-status.c b/wt-status.c
index 5205420..10ce6ee 100644
--- a/wt-status.c
+++ b/wt-status.c
@@ -227,6 +227,7 @@ static void wt_status_print_updated(struct wt_status *s)
 	rev.diffopt.format_callback = wt_status_print_updated_cb;
 	rev.diffopt.format_callback_data = s;
 	rev.diffopt.detect_rename = 1;
+	rev.diffopt.rename_limit = 100;
 	wt_read_cache(s);
 	run_diff_index(&rev, 1);
 }

Re: [PATCH 1/2] Fix "git diff" setup code

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> For some inexplicable reason, "git diff" would call "diff_setup_done()" 
> iff we hadn't given an explicit output format.
>
> That makes no sense, since much of what diff_setup_done() does is exactly 
> about checking the output format!

We did not even have _any_ setup_done() call in "git diff"
itself in the original, because setup_revisions() has its own
call to setup_done(), and it always called setup_revisions()
before you reached that part of the code you have in your patch.
Commit 047fbe906b375e8a3a7564ad0e4443f62dd528a2 ("builtin-diff:
turn recursive on when defaulting to --patch format.") added the
call to setup_done() only when we are defaulting to output
format, to re-validate the consistency of output format options.

The screw-up was commit fcfa33ec905fcde1c16e7cbbe00d7147b89f1f01
(diff: make more cases implicit --no-index) that made the call
to setup_revisions() conditional if setup_diff_no_index()
decides to take over, but it forgot that setup_diff_no_index()
does not call setup_done().

So I tend to think the attached is a better fix.

---
 diff-lib.c |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)

diff --git a/diff-lib.c b/diff-lib.c
index f5568c3..da55713 100644
--- a/diff-lib.c
+++ b/diff-lib.c
@@ -298,6 +298,8 @@ int setup_diff_no_index(struct rev_info *revs,
 	revs->diffopt.nr_paths = 2;
 	revs->diffopt.no_index = 1;
 	revs->max_count = -2;
+	if (diff_setup_done(&revs->diffopt) < 0)
+		die("diff_setup_done failed");
 	return 0;
 }
 

Re: [PATCH 1/2] git-commit: Disallow unchanged tree in non-merge mode

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> Yeah, we should probably:
>  - default to something larger but still reasonably sane (ie not 100, but 
>    perhaps 1000)
>  - special-case the "identical rename", and have a higher limit for that 
>    (we already handle the identicals as a separate pass before we even 
>    start doing the similarity analysis - and it's the similarity analysis 
>    that can be the really expensive part)
>
> There's really no point in trying to do rename analysis for tons and tons 
> of files - even if we find perfect renames, the diff is going to be 
> unreadable by a human, so realistically nobody is ever going to care! A 
> machine won't care whether it was done as a create/delete or a rename, and 
> a human won't be bothered to read about thousands of renames, so we're 
> just wasting time trying to make it prettier.
>
> So quite arguably, the only case we really care about for renames is when 
> the numbers are small enough to be human-readable.

I agree with that.  At the same time we might want to revisit
the earlier "build a full matrix and pick the best ones"
approach commit 5c97558c9a813a0a775c438a79cfc438def00c22 (Detect
renames in diff family) introduced.

A tangent.

I've been thinking about updating the diffcore-rename for some
time to give bonus points to a filepair whose neighbors are
detected to be renames.  E.g. if you have this pair of preimage
and postimage:

	(preimage)		(postimage)

	arch/i386/foo.c		arch/x86/foo-32.c
	arch/i386/bar.c		arch/x86/bar-32.c
	arch/i386/baz.c		arch/x86/baz-32.c

and if foo.c and bar.c are found to be very similar to foo-32.c
and bar-32.c while baz.c and baz-32.c are not that much, we may
want to take hints from the movement of neighbouring files and
boost the similarity score between baz.c and baz-32.c pair.

It would be a quite an interesting coding challenge for anybody
who wants to get his hands dirty.  Would this be worth it in
practice?  I dunno.




        

Re: [PATCH 1/2] Fix "git diff" setup code

[Linus Torvalds]

On Fri, 14 Sep 2007, Junio C Hamano wrote:
> 
> So I tend to think the attached is a better fix.

Ahh, yes, that explains the conditional. 

But whatever gets us to actually verify our options, and fill in the right 
defaults is ok by me!

		Linus

Re: [PATCH 2/2] Fix the rename detection limit checking

[Linus Torvalds]

On Fri, 14 Sep 2007, Linus Torvalds wrote:
>
> ... and we also make sure that we don't overflow when doing the matrix 
> size calculation.

Side note: by "make sure", I don't really mean a total guarantee.

We could be even more careful here. In particular:

 - we later do end up allocating the matrix with 

	sizeof(*mx) * num_create * num_src

   and I didn't actually fix the overflow that is possible due to the
   "sizeof(*mx)" multiplication.

 - even after we've checked that not *both* of the source and destination 
   counts are larger than the rename_limit, we could still overflow the 
   multiplication in just the limit check.

.. but with the rename_limit being set to 100, in practice neither of 
these are really even close to realistic (ie you'd need to have less than 
100 new files, and deleted over twenty million files to overflow, or vice 
versa).

So with a rename_limit of 100, it's all good (I'm pretty sure you'd have 
*other* issues long before you'd hit the integer overflows on renames ;)

But if somebody sets the rename_limit to something bigger, it gets 
increasingly easier to screw it up.

If somebody wants to be *really* careful, they'd need to do something like

	unsigned long max;

	/* This isn't going to overflow, since we limited 'rename_limit' */
	max = rename_limit * rename_limit;

	/*
	 * But we should also check that multiplying by "sizeof(*mx)" 
	 * won't make it overlof either..
	 */
	while ((sizeof(*mx) * max) / sizeof(*mx) != max)
		max >>= 1;

	/*
	 * And then avoid multiplying "rename_dst_nr" and "rename_src_nr"
	 * together by turning it into a division instead
	 */
	if (max / rename_dst_nr > rename_src_nr)
		goto cleanup;

but the patch I sent out was the "obvious" first one that at least avoided 
the overflow for the triggerable case that Dmitry had, and as per above 
likely in all reasonable cases...

			Linus

Re: [PATCH 2/2] Fix the rename detection limit checking

[Linus Torvalds]

On Fri, 14 Sep 2007, Linus Torvalds wrote:
> 
> but the patch I sent out was the "obvious" first one that at least avoided 
> the overflow for the triggerable case that Dmitry had, and as per above 
> likely in all reasonable cases...

Final note (I promise): the patch I sent out took "git runstatus" times on 
the workload I replicated from Dmitry down from "so long you'd ^C it" to 
about two seconds..

So I wanted to point out that this was not just the correctness issue of 
the overflow, but that the rename limiting really does need to be done for 
purely practical time reasons - doing the math in 64 bits would have 
avoided the overflow, but wouldn't have avoided the real reason for not 
wanting to do these kinds of things in the first place!

		Linus

Re: [PATCH 1/2] Fix "git diff" setup code

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> On Fri, 14 Sep 2007, Junio C Hamano wrote:
>> 
>> So I tend to think the attached is a better fix.
>
> Ahh, yes, that explains the conditional. 
>
> But whatever gets us to actually verify our options, and fill in the right 
> defaults is ok by me!

Sorry, my explanation only explains about missing setup_done()
when --no-index is used, but does not explain _if_ you actually
found that setup_done() was not called for you when you did a
real life test.  Was it only from code inspection, or did you
hit a case where setup_done() is not run?  If the latter then
there is something else going on, as I cannot think of a way to
call setup_revisions() and not have it call setup_done()...

Re: [PATCH 1/2] Fix "git diff" setup code

[Linus Torvalds]

On Fri, 14 Sep 2007, Junio C Hamano wrote:
> 
> Sorry, my explanation only explains about missing setup_done()
> when --no-index is used, but does not explain _if_ you actually
> found that setup_done() was not called for you when you did a
> real life test.  Was it only from code inspection, or did you
> hit a case where setup_done() is not run?

Hmm. Mea culpa. What seems to have happened is that I ran things under 
gdb, and noticed that the default rename_limit hadn't been correctly set: 
but now that I look more at it, that particular session was probably from 
"git runstatus", not "git diff".

So yeah, ignore my 1/2. It was almost certainly based on a bogus debugging 
session, before I noticed that wt-status.c doesn't use the normal diff 
stuff at all..

			Linus